Further fixes of substitution and use-after-free

7 files changed, 77 insertions, 50 deletions

diff --git a/inc/map.h b/inc/map.h
index 3759a27..1312ae4 100644
--- a/inc/map.h
+++ b/inc/map.h
@@ -14,6 +14,6 @@ void map_set(struct hashmap *map, struct term *term);
 void map_delete(struct hashmap *map, struct term *term);
 void map_initialize(void);
 void map_destroy(struct hashmap *map);
-void map_dump(struct hashmap *map); // TODO: remove
+void map_dump(struct hashmap *map, char all);
 
 #endif
diff --git a/inc/term.h b/inc/term.h
index f241fa2..0e5902d 100644
--- a/inc/term.h
+++ b/inc/term.h
@@ -12,6 +12,7 @@ typedef enum { INV, ABS, APP, VAR } term_type_t;
 
 struct term {
 	term_type_t type;
+
 	hash_t hash;
 	struct hashmap *parents;
 	size_t refs;
@@ -35,6 +36,7 @@ struct term {
 };
 
 struct term *term_new(term_type_t type, hash_t hash, size_t depth);
+void term_destroy_head(struct term *term, char including_parents);
 char term_is_beta_redex(struct term *term);
 void term_rehash_parents(struct term *term);
 struct term *term_rehash(struct term *term);
@@ -44,8 +46,8 @@ struct term *term_rehash_app(struct term *head, struct term *lhs,
 struct term *term_rehash_var(struct term *head, size_t index);
 void term_refer_head(struct term *term, size_t depth);
 void term_refer(struct term *term, size_t depth);
-void term_deref_head(struct term *term);
-void term_deref(struct term *term);
+char term_deref_head(struct term *term, char destroy_parents);
+char term_deref(struct term *term, char destroy_parents);
 
 void term_print(struct term *term);
 
diff --git a/src/main.c b/src/main.c
index 6a12afb..be74c2f 100644
--- a/src/main.c
+++ b/src/main.c
@@ -66,7 +66,7 @@ int main(int argc, char *argv[])
 
 	schedule();
 
-	map_dump(map_all_terms());
+	map_dump(map_all_terms(), 0);
 	map_destroy(map_all_terms());
 	schedule_destroy();
 	return 0;
diff --git a/src/map.c b/src/map.c
index c36354d..553bbde 100644
--- a/src/map.c
+++ b/src/map.c
@@ -13,7 +13,7 @@ static struct hashmap *all_terms;
 static void hashmap_free_term(void *item)
 {
 	struct term *term = *(struct term **)item;
-	term_destroy_head(term);
+	term_destroy_head(term, 1);
 }
 
 struct hashmap *map_all_terms(void)
@@ -51,14 +51,19 @@ void map_destroy(struct hashmap *map)
 	hashmap_free(map);
 }
 
-void map_dump(struct hashmap *map)
+void map_dump(struct hashmap *map, char all)
 {
 	fprintf(stderr, "\n---\nMap dump:\n");
+	fprintf(stderr, "type\trefs\thash\t\t\tterm\t\tparents\n");
 	size_t iter = 0;
 	void *iter_val;
 	while (hashmap_iter(map, &iter, &iter_val)) {
 		struct term *term = *(struct term **)iter_val;
-		fprintf(stderr, "%d\t%ld\t", term->type, term->refs);
+		/* if (!all && !term->is_program) */
+		/* 	continue; */
+
+		fprintf(stderr, "%d\t%ld\t%lx\t", term->type, term->refs,
+			term->hash);
 		term_print(term);
 		fprintf(stderr, "\t{");
 
diff --git a/src/reduce.c b/src/reduce.c
index 2ae6e8e..3fc7c48 100644
--- a/src/reduce.c
+++ b/src/reduce.c
@@ -9,25 +9,28 @@
 #include <log.h>
 #include <assert.h>
 
+// only substitutes (and therefore rehashes) -> no explicit beta reduction
 static struct term *substitute(struct term *term, struct term *substitution,
 			       size_t level)
 {
+	debug("substituting %lx with %lx\n", term->hash, substitution->hash);
 	if (term->type == VAR) {
 		if (term->u.var.index == level) {
 			return substitution;
 		} else {
-			term_refer_head(term, substitution->depth);
+			term_deref(substitution, 1);
 			return term;
 		}
 	} else if (term->type == ABS) {
-		hash_t previous = term->u.abs.term->hash;
+		struct term *previous = term->u.abs.term;
 		struct term *new =
 			substitute(term->u.abs.term, substitution, level + 1);
-		if (previous == new->hash)
-			return term; // nothing changed
+		if (previous->hash == new->hash)
+			return new; // nothing changed
 		struct term *rehashed = term_rehash_abs(term, new);
 		term_rehash_parents(rehashed);
-		term_deref_head(term->u.abs.term);
+		if (rehashed->u.abs.term->hash == substitution->hash)
+			term_deref_head(previous, 1);
 		return rehashed;
 	} else if (term->type == APP) {
 		hash_t previous_lhs = term->u.app.lhs->hash;
@@ -52,9 +55,8 @@ struct term *reduce(struct term *term)
 	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); */
+	debug("reducing %lx\n", term->hash);
+
 	struct term *reduced = substitute(term->u.app.lhs, term->u.app.rhs, -1);
-	/* term_deref_head(term); */
 	return reduced;
 }
diff --git a/src/schedule.c b/src/schedule.c
index 407c6e0..458d8a2 100644
--- a/src/schedule.c
+++ b/src/schedule.c
@@ -69,7 +69,7 @@ void schedule_add(struct term *term)
 
 void schedule_remove(struct term *term)
 {
-	if (!term_is_beta_redex(term))
+	if (!pqueue_size(queue) || !term_is_beta_redex(term))
 		return;
 
 	int error = pqueue_remove(queue, term);
@@ -78,9 +78,9 @@ void schedule_remove(struct term *term)
 
 void schedule(void)
 {
-	while (pqueue_size(queue) > 1) {
-		fprintf(stderr, "queue size: %zu\n", pqueue_size(queue));
-		map_dump(map_all_terms());
+	while (pqueue_size(queue)) {
+		debug("queue size: %zu\n", pqueue_size(queue));
+		map_dump(map_all_terms(), 1);
 
 		// TODO: check finished programs
 		size_t position = choose_position();
diff --git a/src/term.c b/src/term.c
index bf712d6..caea6f1 100644
--- a/src/term.c
+++ b/src/term.c
@@ -10,34 +10,37 @@
 #include <term.h>
 #include <map.h>
 
+static void term_destroy_parent(void *item)
+{
+	struct term *term = *(struct term **)item;
+	term_destroy_head(term, 1);
+}
+
 // doesn't care about ref count
 // this is needed to destroy possibly multiple parents
-static void term_destroy_head(struct term *term)
+void term_destroy_head(struct term *term, char including_parents)
 {
+	debug("destroying head of %lx\n", term->hash);
+
 	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);
+	if (including_parents) {
+		map_destroy(term->parents);
+
+		// remove head 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);
-}
-
 struct term *term_new(term_type_t type, hash_t hash, size_t depth)
 {
 	struct term *term = malloc(sizeof(*term));
@@ -82,6 +85,7 @@ void term_print(struct term *term)
 
 struct term *term_rehash_abs(struct term *head, struct term *term)
 {
+	debug("rehashing abs %lx\n", head->hash);
 	hash_t res =
 		hash((uint8_t *)&head->type, sizeof(head->type), term->hash);
 
@@ -91,14 +95,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, 1);
 		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, 1);
 		return new;
 	}
 }
@@ -106,6 +110,7 @@ struct term *term_rehash_abs(struct term *head, struct term *term)
 struct term *term_rehash_app(struct term *head, struct term *lhs,
 			     struct term *rhs)
 {
+	debug("rehashing app %lx\n", head->hash);
 	hash_t res =
 		hash((uint8_t *)&head->type, sizeof(head->type), lhs->hash);
 	res = hash((uint8_t *)&res, sizeof(res), rhs->hash);
@@ -116,7 +121,7 @@ struct term *term_rehash_app(struct term *head, struct term *lhs,
 	struct term *match = map_get(map_all_terms(), res);
 	if (match) { // already exists
 		term_refer_head(match, head->depth);
-		term_deref(head);
+		term_deref(head, 1);
 		return match;
 	} else { // create new
 		struct term *new = term_new(APP, res, head->depth);
@@ -125,13 +130,14 @@ struct term *term_rehash_app(struct term *head, struct term *lhs,
 		map_set(map_all_terms(), new);
 		map_set(lhs->parents, new);
 		map_set(rhs->parents, new);
-		term_deref_head(head);
+		term_deref_head(head, 1);
 		return new;
 	}
 }
 
 struct term *term_rehash_var(struct term *head, size_t index)
 {
+	debug("rehashing var %lx\n", head->hash);
 	hash_t res = hash((uint8_t *)&head->type, sizeof(head->type), index);
 
 	if (res == head->hash)
@@ -140,13 +146,13 @@ struct term *term_rehash_var(struct term *head, size_t index)
 	struct term *match = map_get(map_all_terms(), res);
 	if (match) { // already exists
 		term_refer_head(match, head->depth);
-		term_deref(head);
+		term_deref(head, 1);
 		return match;
 	} else { // create new
 		struct term *new = term_new(APP, res, head->depth);
 		new->u.var.index = index;
 		map_set(map_all_terms(), new);
-		term_deref_head(head);
+		term_deref_head(head, 1);
 		return new;
 	}
 }
@@ -170,6 +176,7 @@ void term_rehash_parents(struct term *term)
 {
 	if (!term->parents)
 		return;
+	debug("rehashing parents of %lx\n", term->hash);
 
 	// we need to convert the parent hashmap to a list
 	// so we can replace the rehashed elements while looping
@@ -210,10 +217,13 @@ void term_rehash_parents(struct term *term)
 		free(iterator);
 		iterator = next;
 	}
+	if (iterator == parents)
+		free(parents);
 }
 
 void term_refer_head(struct term *term, size_t depth)
 {
+	debug("referring head of %lx\n", term->hash);
 	term->refs++;
 	if (depth < term->depth) // lower depths are more important
 		term->depth = depth;
@@ -231,23 +241,31 @@ void term_refer(struct term *term, size_t depth)
 	term_refer_head(term, depth);
 }
 
-void term_deref_head(struct term *term)
+char term_deref_head(struct term *term, char destroy_parents)
 {
-	fprintf(stderr, "%p deref\n", term);
+	debug("dereferring head of %lx\n", term->hash);
+
 	assert(term->refs);
 	term->refs--;
-	if (!term->refs)
-		term_destroy_head(term);
+	if (!term->refs) {
+		term_destroy_head(term, destroy_parents);
+		return 1;
+	}
+	return 0;
 }
 
-void term_deref(struct term *term)
+// returns 1 if destroyed
+char term_deref(struct term *term, char destroy_parents)
 {
+	char a = 0, b = 0;
 	if (term->type == ABS) {
-		term_deref(term->u.abs.term);
+		a = term_deref(term->u.abs.term, destroy_parents);
 	} else if (term->type == APP) {
-		term_deref(term->u.app.lhs);
-		term_deref(term->u.app.rhs);
+		a = term_deref(term->u.app.lhs, destroy_parents);
+		b = term_deref(term->u.app.rhs, destroy_parents);
 	}
 
-	term_deref_head(term);
+	if (a || b)
+		return 1;
+	return term_deref_head(term, destroy_parents);
 }