Fixed some use-after-frees

7 files changed, 69 insertions, 17 deletions

diff --git a/inc/lib/pqueue.h b/inc/lib/pqueue.h
index 732002e..02988ce 100644
--- a/inc/lib/pqueue.h
+++ b/inc/lib/pqueue.h
@@ -105,7 +105,7 @@ size_t pqueue_size(struct pqueue *q);
 int pqueue_insert(struct pqueue *q, void *d);
 
 /**
- * move an existing entry to a different priority
+ * move an existing entry to a different priority.
  * @param q the queue
  * @param new_pri the new priority
  * @param d the entry
@@ -113,6 +113,14 @@ int pqueue_insert(struct pqueue *q, void *d);
 void pqueue_change_priority(struct pqueue *q, pqueue_pri_t new_pri, void *d);
 
 /**
+ * remove an item from the queue.
+ * @param q the queue
+ * @param d the item
+ * @return 0 on success
+ */
+int pqueue_remove(struct pqueue *q, void *d);
+
+/**
  * pop the highest-ranking item from the queue.
  * @param q the queue
  * @return NULL on error, otherwise the entry
diff --git a/inc/schedule.h b/inc/schedule.h
index eaf1e0c..9151d49 100644
--- a/inc/schedule.h
+++ b/inc/schedule.h
@@ -9,6 +9,7 @@
 void schedule_initialize(void);
 void schedule_sync_priorities(void);
 void schedule_add(struct term *term);
+void schedule_remove(struct term *term);
 void schedule(void);
 void schedule_destroy(void);
 
diff --git a/inc/term.h b/inc/term.h
index 62b93dd..f241fa2 100644
--- a/inc/term.h
+++ b/inc/term.h
@@ -35,6 +35,7 @@ struct term {
 };
 
 struct term *term_new(term_type_t type, hash_t hash, size_t depth);
+char term_is_beta_redex(struct term *term);
 void term_rehash_parents(struct term *term);
 struct term *term_rehash(struct term *term);
 struct term *term_rehash_abs(struct term *head, struct term *term);
diff --git a/src/lib/pqueue.c b/src/lib/pqueue.c
index cf0611f..6162cbc 100644
--- a/src/lib/pqueue.c
+++ b/src/lib/pqueue.c
@@ -160,6 +160,18 @@ void pqueue_change_priority(struct pqueue *q, pqueue_pri_t new_pri, void *d)
 		percolate_down(q, posn);
 }
 
+int pqueue_remove(struct pqueue *q, void *d)
+{
+	size_t posn = q->getpos(d);
+	q->d[posn] = q->d[--q->size];
+	if (q->cmppri(q->getpri(d), q->getpri(q->d[posn])))
+		bubble_up(q, posn);
+	else
+		percolate_down(q, posn);
+
+	return 0;
+}
+
 void *pqueue_pop(struct pqueue *q)
 {
 	void *head;
diff --git a/src/reduce.c b/src/reduce.c
index 38baf06..2ae6e8e 100644
--- a/src/reduce.c
+++ b/src/reduce.c
@@ -14,9 +14,9 @@ static struct term *substitute(struct term *term, struct term *substitution,
 {
 	if (term->type == VAR) {
 		if (term->u.var.index == level) {
-			term_deref_head(term);
 			return substitution;
 		} else {
+			term_refer_head(term, substitution->depth);
 			return term;
 		}
 	} else if (term->type == ABS) {
@@ -27,6 +27,7 @@ static struct term *substitute(struct term *term, struct term *substitution,
 			return term; // nothing changed
 		struct term *rehashed = term_rehash_abs(term, new);
 		term_rehash_parents(rehashed);
+		term_deref_head(term->u.abs.term);
 		return rehashed;
 	} else if (term->type == APP) {
 		hash_t previous_lhs = term->u.app.lhs->hash;
@@ -48,12 +49,12 @@ static struct term *substitute(struct term *term, struct term *substitution,
 // ([X] Y) -> X/Y
 struct term *reduce(struct term *term)
 {
-	if (term->type != APP || term->u.app.lhs->type != ABS)
+	if (!term_is_beta_redex(term))
 		fatal("can't reduce non-beta-redex %d\n", term->type);
 
-	map_delete(term->u.app.lhs->parents, term);
-	map_delete(term->u.app.rhs->parents, term);
+	/* map_delete(term->u.app.lhs->parents, term); */
+	/* map_delete(term->u.app.rhs->parents, term); */
 	struct term *reduced = substitute(term->u.app.lhs, term->u.app.rhs, -1);
-	term_deref_head(term);
+	/* term_deref_head(term); */
 	return reduced;
 }
diff --git a/src/schedule.c b/src/schedule.c
index 1362b1e..407c6e0 100644
--- a/src/schedule.c
+++ b/src/schedule.c
@@ -4,6 +4,7 @@
 #include <math.h>
 #include <time.h>
 #include <stdlib.h>
+#include <assert.h>
 
 #include <schedule.h>
 #include <reduce.h>
@@ -59,16 +60,26 @@ static pqueue_pri_t calculate_priority(struct term *term)
 
 void schedule_add(struct term *term)
 {
-	if (!(term->type == APP && term->u.app.lhs->type == ABS))
-		return; // no beta redex
+	if (!term_is_beta_redex(term))
+		return;
 
 	set_pri(term, calculate_priority(term));
 	pqueue_insert(queue, term);
 }
 
+void schedule_remove(struct term *term)
+{
+	if (!term_is_beta_redex(term))
+		return;
+
+	int error = pqueue_remove(queue, term);
+	assert(!error);
+}
+
 void schedule(void)
 {
-	while (pqueue_size(queue) > 0) {
+	while (pqueue_size(queue) > 1) {
+		fprintf(stderr, "queue size: %zu\n", pqueue_size(queue));
 		map_dump(map_all_terms());
 
 		// TODO: check finished programs
@@ -85,10 +96,9 @@ void schedule_sync_priorities(void)
 	void *iter_val;
 	while (hashmap_iter(map_all_terms(), &iter, &iter_val)) {
 		struct term *term = *(struct term **)iter_val;
-		if (term->type == APP && term->u.app.lhs->type == ABS) {
-			pqueue_change_priority(queue, calculate_priority(term),
-					       term);
-		}
+		if (!term_is_beta_redex(term))
+			continue;
+		pqueue_change_priority(queue, calculate_priority(term), term);
 	}
 }
 
diff --git a/src/term.c b/src/term.c
index bd0868c..f4bee23 100644
--- a/src/term.c
+++ b/src/term.c
@@ -6,22 +6,35 @@
 #include <assert.h>
 
 #include <log.h>
+#include <schedule.h>
 #include <term.h>
 #include <map.h>
 
 // doesn't care about ref count
+// this is needed to destroy possibly multiple parents
 static void term_destroy_head(struct term *term)
 {
-	term_print(term);
-	fprintf(stderr, "\n");
 	map_delete(map_all_terms(), term);
+
+	// recursively destroy own parents
 	map_destroy(term->parents);
+
+	// remove term from child's parents
+	if (term->type == ABS) {
+		map_delete(term->u.abs.term->parents, term);
+	} else if (term->type == APP) {
+		map_delete(term->u.app.lhs->parents, term);
+		map_delete(term->u.app.rhs->parents, term);
+	}
+
+	schedule_remove(term);
 	free(term);
 }
 
 static void term_destroy_parent(void *item)
 {
 	struct term *term = *(struct term **)item;
+	fprintf(stderr, "%p parent\n", term);
 	term_destroy_head(term);
 }
 
@@ -39,6 +52,11 @@ struct term *term_new(term_type_t type, hash_t hash, size_t depth)
 	return term;
 }
 
+char term_is_beta_redex(struct term *term)
+{
+	return term->type == APP && term->u.app.lhs->type == ABS;
+}
+
 void term_print(struct term *term)
 {
 	switch (term->type) {
@@ -73,14 +91,14 @@ struct term *term_rehash_abs(struct term *head, struct term *term)
 	struct term *match = map_get(map_all_terms(), res);
 	if (match) { // already exists
 		term_refer_head(match, head->depth);
-		term_deref_head(head);
+		/* term_deref_head(head); */
 		return match;
 	} else { // create new
 		struct term *new = term_new(ABS, res, head->depth);
 		new->u.abs.term = term;
 		map_set(map_all_terms(), new);
 		map_set(term->parents, new);
-		term_deref_head(head);
+		/* term_deref_head(head); */
 		return new;
 	}
 }
@@ -214,6 +232,7 @@ void term_refer(struct term *term, size_t depth)
 
 void term_deref_head(struct term *term)
 {
+	fprintf(stderr, "%p deref\n", term);
 	assert(term->refs);
 	term->refs--;
 	if (!term->refs)