Parenting is still needed

I was certainly dumb.

This reverts commit ec2be68120e48c75b0acd2bdfb5cc8d931c70cfd.

6 files changed, 99 insertions, 17 deletions

diff --git a/inc/term.h b/inc/term.h
index 6d5732e..f241fa2 100644
--- a/inc/term.h
+++ b/inc/term.h
@@ -13,6 +13,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;
 	size_t depth;
 
@@ -34,8 +35,8 @@ struct term {
 };
 
 struct term *term_new(term_type_t type, hash_t hash, size_t depth);
-void term_destroy_head(struct term *term);
 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);
 struct term *term_rehash_app(struct term *head, struct term *lhs,
diff --git a/src/map.c b/src/map.c
index e37217d..c36354d 100644
--- a/src/map.c
+++ b/src/map.c
@@ -7,7 +7,6 @@
 #include <map.h>
 #include <parse.h>
 #include <schedule.h>
-#include <term.h>
 
 static struct hashmap *all_terms;
 
@@ -61,7 +60,16 @@ void map_dump(struct hashmap *map)
 		struct term *term = *(struct term **)iter_val;
 		fprintf(stderr, "%d\t%ld\t", term->type, term->refs);
 		term_print(term);
-		fprintf(stderr, "\n");
+		fprintf(stderr, "\t{");
+
+		size_t jiter = 0;
+		void *jiter_val;
+		while (hashmap_iter(term->parents, &jiter, &jiter_val)) {
+			struct term *parent = *(struct term **)jiter_val;
+			term_print(parent);
+			fprintf(stderr, ", ");
+		}
+		fprintf(stderr, "}\n");
 	}
 	fprintf(stderr, "---\n\n");
 }
diff --git a/src/parse.c b/src/parse.c
index f4ec69c..e2d2498 100644
--- a/src/parse.c
+++ b/src/parse.c
@@ -26,6 +26,7 @@ static struct term_handle abs_blc(char **term, size_t depth)
 		map_set(map_all_terms(), res_term);
 	}
 
+	map_set(res_term->u.abs.term->parents, res_term);
 	return (struct term_handle){ .term = res_term, .hash = res };
 }
 
@@ -48,6 +49,9 @@ static struct term_handle app_blc(char **term, size_t depth)
 		map_set(map_all_terms(), res_term);
 	}
 
+	map_set(res_term->u.app.lhs->parents, res_term);
+	map_set(res_term->u.app.rhs->parents, res_term);
+
 	return (struct term_handle){ .term = res_term, .hash = res };
 }
 
diff --git a/src/reduce.c b/src/reduce.c
index 60fa57a..2ae6e8e 100644
--- a/src/reduce.c
+++ b/src/reduce.c
@@ -26,7 +26,8 @@ static struct term *substitute(struct term *term, struct term *substitution,
 		if (previous == new->hash)
 			return term; // nothing changed
 		struct term *rehashed = term_rehash_abs(term, new);
-		/* term_deref_head(term->u.abs.term); */ // TODO: only for vars?
+		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;
@@ -38,6 +39,7 @@ static struct term *substitute(struct term *term, struct term *substitution,
 		if (previous_lhs == lhs->hash && previous_rhs == rhs->hash)
 			return term; // nothing changed
 		struct term *rehashed = term_rehash_app(term, lhs, rhs);
+		term_rehash_parents(rehashed);
 		return rehashed;
 	}
 	fatal("invalid type %d\n", term->type);
@@ -50,13 +52,9 @@ struct term *reduce(struct term *term)
 	if (!term_is_beta_redex(term))
 		fatal("can't reduce non-beta-redex %d\n", term->type);
 
-	fprintf(stderr, "reducing ");
-	term_print(term);
-	fprintf(stderr, "\n");
-
+	/* 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);
-	fprintf(stderr, "reduced ");
-	term_print(reduced);
-	fprintf(stderr, "\n");
+	/* term_deref_head(term); */
 	return reduced;
 }
diff --git a/src/schedule.c b/src/schedule.c
index 2a7a7c4..407c6e0 100644
--- a/src/schedule.c
+++ b/src/schedule.c
@@ -63,10 +63,6 @@ void schedule_add(struct term *term)
 	if (!term_is_beta_redex(term))
 		return;
 
-	fprintf(stderr, "added ");
-	term_print(term);
-	fprintf(stderr, "\n");
-
 	set_pri(term, calculate_priority(term));
 	pqueue_insert(queue, term);
 }
@@ -82,7 +78,7 @@ void schedule_remove(struct term *term)
 
 void schedule(void)
 {
-	while (pqueue_size(queue)) {
+	while (pqueue_size(queue) > 1) {
 		fprintf(stderr, "queue size: %zu\n", pqueue_size(queue));
 		map_dump(map_all_terms());
 
diff --git a/src/term.c b/src/term.c
index 5abe758..bf712d6 100644
--- a/src/term.c
+++ b/src/term.c
@@ -11,13 +11,33 @@
 #include <map.h>
 
 // doesn't care about ref count
-void term_destroy_head(struct term *term)
+// this is needed to destroy possibly multiple parents
+static void term_destroy_head(struct term *term)
 {
 	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);
+}
+
 struct term *term_new(term_type_t type, hash_t hash, size_t depth)
 {
 	struct term *term = malloc(sizeof(*term));
@@ -27,6 +47,8 @@ struct term *term_new(term_type_t type, hash_t hash, size_t depth)
 	term->refs = 1;
 	term->hash = hash;
 	term->depth = depth;
+	term->parents =
+		hashmap_new(sizeof(struct term *), 0, term_destroy_parent);
 	return term;
 }
 
@@ -69,11 +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); */
 		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); */
 		return new;
 	}
 }
@@ -98,6 +123,8 @@ struct term *term_rehash_app(struct term *head, struct term *lhs,
 		new->u.app.lhs = lhs;
 		new->u.app.rhs = rhs;
 		map_set(map_all_terms(), new);
+		map_set(lhs->parents, new);
+		map_set(rhs->parents, new);
 		term_deref_head(head);
 		return new;
 	}
@@ -138,6 +165,53 @@ struct term *term_rehash(struct term *term)
 	fatal("invalid type %d\n", term->type);
 }
 
+// returns the direct parent
+void term_rehash_parents(struct term *term)
+{
+	if (!term->parents)
+		return;
+
+	// we need to convert the parent hashmap to a list
+	// so we can replace the rehashed elements while looping
+	// TODO: Abstract list lib?
+	struct parent_list {
+		struct term *term;
+		struct parent_list *next;
+	};
+	struct parent_list *parents = calloc(sizeof(*parents), 1);
+
+	size_t iter = 0;
+	void *iter_val;
+	while (hashmap_iter(term->parents, &iter, &iter_val)) {
+		struct parent_list *new = malloc(sizeof(*parents));
+		new->term = *(struct term **)iter_val;
+		new->next = parents;
+		parents = new;
+	}
+
+	struct parent_list *iterator = parents;
+	while (iterator && iterator->term) {
+		struct term *parent = iterator->term;
+		hash_t previous = parent->hash;
+		struct term *new = term_rehash(parent);
+		if (previous == new->hash) {
+			struct parent_list *next = iterator->next;
+			free(iterator);
+			iterator = next;
+			continue;
+		}
+
+		map_delete(term->parents, parent);
+		map_set(term->parents, new);
+
+		term_rehash_parents(new);
+
+		struct parent_list *next = iterator->next;
+		free(iterator);
+		iterator = next;
+	}
+}
+
 void term_refer_head(struct term *term, size_t depth)
 {
 	term->refs++;
@@ -159,6 +233,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)