Added additional optimizer

This will be useful for variadic index lengths

10 files changed, 370 insertions, 153 deletions

diff --git a/inc/optimize.h b/inc/optimize.h
new file mode 100644
index 0000000..51cb793
--- /dev/null
+++ b/inc/optimize.h
@@ -0,0 +1,11 @@
+// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de>
+// SPDX-License-Identifier: MIT
+
+#ifndef BLOC_OPTIMIZE
+#define BLOC_OPTIMIZE
+
+#include <tree.h>
+
+struct list *optimize_tree(struct tree *tree, void **all_trees);
+
+#endif
diff --git a/inc/pqueue.h b/inc/pqueue.h
index 3b4752d..c3ad021 100644
--- a/inc/pqueue.h
+++ b/inc/pqueue.h
@@ -58,6 +58,7 @@ struct pqueue {
 	size_t step; /**< growth stepping setting */
 	pqueue_cmp_pri_f cmppri; /**< callback to compare nodes */
 	pqueue_get_pri_f getpri; /**< callback to get priority of a node */
+	pqueue_set_pos_f setpos; /**< callback to set position of a node */
 	void **d; /**< The actualy queue in binary heap form */
 };
 
@@ -74,7 +75,7 @@ struct pqueue {
  * @return the handle or NULL for insufficent memory
  */
 struct pqueue *pqueue_init(size_t n, pqueue_cmp_pri_f cmppri,
-			   pqueue_get_pri_f getpri);
+			   pqueue_get_pri_f getpri, pqueue_set_pos_f set_pos);
 
 /**
  * free all memory used by the queue
diff --git a/inc/tree.h b/inc/tree.h
index 8addf7e..41ad27a 100644
--- a/inc/tree.h
+++ b/inc/tree.h
@@ -31,7 +31,8 @@ struct tree {
 			int index;
 		} var;
 		struct {
-			size_t index;
+			size_t hash;
+			int table_index;
 		} ref;
 	} u;
 };
@@ -42,7 +43,8 @@ struct list {
 	struct list *next;
 };
 
-struct list *tree_merge_duplicates(struct term *term);
+struct list *list_add(struct list *list, void *data);
+struct tree *tree_merge_duplicates(struct term *term, void **all_trees);
 void tree_destroy(struct list *table);
 
 #endif
diff --git a/src/build.c b/src/build.c
index 9fdcad4..e396407 100644
--- a/src/build.c
+++ b/src/build.c
@@ -47,7 +47,7 @@ static void rec_write_bblc(struct tree *tree, FILE *file, char *byte, int *bit)
 		write_bit(1, file, byte, bit);
 
 		// TODO: The bit-order of encoded shorts is kinda arbitrary
-		short ref = tree->u.ref.index;
+		short ref = tree->u.ref.table_index;
 		for (int i = 0; i < 16; i++)
 			write_bit((ref >> i) & 1, file, byte, bit);
 		break;
diff --git a/src/main.c b/src/main.c
index 4258281..1d0a36f 100644
--- a/src/main.c
+++ b/src/main.c
@@ -7,6 +7,7 @@
 #include <stdlib.h>
 
 #include <term.h>
+#include <optimize.h>
 #include <log.h>
 #include <print.h>
 #include <tree.h>
@@ -84,7 +85,11 @@ static void test(char *input)
 	debug("parsed original blc\n");
 
 	debug("merging duplicates\n");
-	struct list *table = tree_merge_duplicates(parsed_1);
+	void *all_trees = 0;
+	struct tree *tree = tree_merge_duplicates(parsed_1, &all_trees);
+
+	debug("optimizing tree\n");
+	struct list *table = optimize_tree(tree, &all_trees);
 
 	FILE *temp_bloc = tmpfile();
 	write_bloc(table, temp_bloc);
@@ -123,7 +128,11 @@ static void from_blc(char *input, char *output_path)
 	debug("parsed blc\n");
 
 	debug("merging duplicates\n");
-	struct list *table = tree_merge_duplicates(parsed);
+	void *all_trees = 0;
+	struct tree *tree = tree_merge_duplicates(parsed, &all_trees);
+
+	debug("optimizing tree\n");
+	struct list *table = optimize_tree(tree, &all_trees);
 
 	FILE *file = fopen(output_path, "wb");
 	write_bloc(table, file);
diff --git a/src/optimize.c b/src/optimize.c
new file mode 100644
index 0000000..a79299e
--- /dev/null
+++ b/src/optimize.c
@@ -0,0 +1,168 @@
+// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de>
+// SPDX-License-Identifier: MIT
+
+// most of the actual optimizing is done in tree.c
+// this file does some extra steps to optimize the tree even further
+
+#include <search.h>
+#include <assert.h>
+#include <stdlib.h>
+
+#include <log.h>
+#include <optimize.h>
+#include <pqueue.h>
+
+struct tree_tracker {
+	uint32_t hash;
+	struct tree *tree;
+	int count; // reference/occurrence count
+	size_t position; // in queue
+};
+
+struct hash_to_tree {
+	uint32_t hash;
+	struct tree *tree;
+};
+
+// comparison_fn_t for tsearch
+static int hash_compare(const void *_a, const void *_b)
+{
+	const struct tree_tracker *a = _a;
+	const struct tree_tracker *b = _b;
+
+	if (a->hash < b->hash)
+		return -1;
+	if (a->hash > b->hash)
+		return 1;
+	return 0;
+}
+
+// constructs a tree/map/set of all hashes and their occurrence count
+// this is needed because the index count changes (currently untracked, see README)
+// during tree invalidation and less used indices should get shorter encodings
+static void generate_index_mappings(struct tree *tree, void **all_trees,
+				    void **set)
+{
+	switch (tree->type) {
+	case ABS:
+		generate_index_mappings(tree->u.abs.term, all_trees, set);
+		break;
+	case APP:
+		generate_index_mappings(tree->u.app.lhs, all_trees, set);
+		generate_index_mappings(tree->u.app.rhs, all_trees, set);
+		break;
+	case VAR:
+		break;
+	case REF:;
+		// increase count of reference
+		struct tree_tracker *element = malloc(sizeof(*element));
+		if (!element)
+			fatal("out of memory!\n");
+		element->hash = tree->u.ref.hash;
+		struct tree_tracker **handle =
+			tsearch(element, set, hash_compare);
+		if (*handle == element) { // first of its kind
+			struct hash_to_tree *tree_element =
+				malloc(sizeof(*tree_element));
+			tree_element->hash = tree->u.ref.hash;
+			struct hash_to_tree **ref_tree =
+				tfind(element, all_trees, hash_compare);
+			if (!ref_tree)
+				fatal("referred tree not found!\n");
+			free(tree_element);
+
+			element->count = 1;
+			element->tree = (*ref_tree)->tree;
+			assert(element->tree);
+			generate_index_mappings(element->tree, all_trees, set);
+		} else {
+			free(element); // already exists, not needed
+			(*handle)->count++;
+		}
+		break;
+	default:
+		fatal("invalid type %d\n", tree->type);
+	}
+}
+
+// sets corresponding table_index of references
+static void fix_tree(struct tree *tree, void **set)
+{
+	switch (tree->type) {
+	case ABS:
+		fix_tree(tree->u.abs.term, set);
+		break;
+	case APP:
+		fix_tree(tree->u.app.lhs, set);
+		fix_tree(tree->u.app.rhs, set);
+		break;
+	case VAR:
+		break;
+	case REF:;
+		struct tree_tracker *element = malloc(sizeof(*element));
+		element->hash = tree->u.ref.hash;
+		if (!element)
+			fatal("out of memory!\n");
+		struct tree_tracker **handle =
+			tfind(element, set, hash_compare);
+		assert(handle); // must exist
+		free(element);
+		tree->u.ref.table_index = (*handle)->position;
+		fix_tree((*handle)->tree, set);
+		break;
+	default:
+		fatal("invalid type %d\n", tree->type);
+	}
+}
+
+// priority of candidate -> occurrence count
+static pqueue_pri_t get_pri(void *a)
+{
+	return ((struct tree_tracker *)a)->count;
+}
+
+static int cmp_pri(pqueue_pri_t next, pqueue_pri_t curr)
+{
+	return next < curr;
+}
+
+static void set_pos(void *a, size_t pos)
+{
+	((struct tree_tracker *)a)->position = pos - 1;
+}
+
+static struct pqueue *set_queue; // i know this is stupid but tsearch is stupider
+static void walk(void *data, VISIT which, int depth)
+{
+	(void)depth;
+	if (which != preorder && which != leaf)
+		return;
+
+	struct tree_tracker *element = *(struct tree_tracker **)data;
+	// TODO: Merge elements with =1 references
+	if (element->count) { // only insert elements with references
+		pqueue_insert(set_queue, element);
+	}
+}
+
+struct list *optimize_tree(struct tree *tree, void **all_trees)
+{
+	void *set = 0;
+	generate_index_mappings(tree, all_trees, &set);
+
+	// pqueue from mappings: hash -> tree_tracker
+	set_queue = pqueue_init(2 << 7, cmp_pri, get_pri, set_pos);
+	twalk(set, walk);
+
+	fix_tree(tree, &set);
+
+	struct list *list = list_add(0, tree);
+
+	for (size_t i = 1; i < pqueue_size(set_queue) + 1; i++) {
+		struct tree_tracker *element = set_queue->d[i];
+		list = list_add(list, element->tree);
+	}
+	pqueue_free(set_queue);
+
+	return list;
+}
diff --git a/src/pqueue.c b/src/pqueue.c
index 8e7eca7..c9b7d34 100644
--- a/src/pqueue.c
+++ b/src/pqueue.c
@@ -35,7 +35,7 @@
 #define parent(i) ((i) >> 1)
 
 struct pqueue *pqueue_init(size_t n, pqueue_cmp_pri_f cmppri,
-			   pqueue_get_pri_f getpri)
+			   pqueue_get_pri_f getpri, pqueue_set_pos_f setpos)
 {
 	struct pqueue *q;
 
@@ -52,6 +52,7 @@ struct pqueue *pqueue_init(size_t n, pqueue_cmp_pri_f cmppri,
 	q->avail = q->step = (n + 1); /* see comment above about n+1 */
 	q->cmppri = cmppri;
 	q->getpri = getpri;
+	q->setpos = setpos;
 
 	return q;
 }
@@ -78,9 +79,11 @@ static void bubble_up(struct pqueue *q, size_t i)
 	     ((i > 1) && q->cmppri(q->getpri(q->d[parent_node]), moving_pri));
 	     i = parent_node, parent_node = parent(i)) {
 		q->d[i] = q->d[parent_node];
+		q->setpos(q->d[i], i);
 	}
 
 	q->d[i] = moving_node;
+	q->setpos(moving_node, i);
 }
 
 static size_t maxchild(struct pqueue *q, size_t i)
@@ -107,10 +110,12 @@ static void percolate_down(struct pqueue *q, size_t i)
 	while ((child_node = maxchild(q, i)) &&
 	       q->cmppri(moving_pri, q->getpri(q->d[child_node]))) {
 		q->d[i] = q->d[child_node];
+		q->setpos(q->d[i], i);
 		i = child_node;
 	}
 
 	q->d[i] = moving_node;
+	q->setpos(moving_node, i);
 }
 
 int pqueue_insert(struct pqueue *q, void *d)
diff --git a/src/tree.c b/src/tree.c
index 755b5e2..8fef9d1 100644
--- a/src/tree.c
+++ b/src/tree.c
@@ -50,7 +50,7 @@ static uint32_t murmur3_32(const uint8_t *key, size_t len, uint32_t seed)
 }
 
 static struct list *list_end = 0;
-static struct list *list_add(struct list *list, void *data)
+struct list *list_add(struct list *list, void *data)
 {
 	struct list *new = malloc(sizeof(*new));
 	if (!new)
@@ -62,16 +62,22 @@ static struct list *list_add(struct list *list, void *data)
 }
 
 // element of the tsearch tree
-struct set_element {
+struct hash_to_list {
 	uint32_t hash;
 	struct list *list;
 };
 
+// element of the tsearch tree
+struct hash_to_tree {
+	uint32_t hash;
+	struct tree *tree;
+};
+
 // comparison_fn_t for tsearch
 static int hash_compare(const void *_a, const void *_b)
 {
-	const struct set_element *a = _a;
-	const struct set_element *b = _b;
+	const struct hash_to_list *a = _a;
+	const struct hash_to_list *b = _b;
 
 	if (a->hash < b->hash)
 		return -1;
@@ -124,12 +130,12 @@ static struct tree *build_tree(struct term *term, void **set)
 	if (tree->size < 10) // not suitable for deduplication
 		return tree;
 
-	struct set_element *element = malloc(sizeof(*element));
+	struct hash_to_list *element = malloc(sizeof(*element));
 	if (!element)
 		fatal("out of memory!\n");
 	element->hash = tree->hash;
 
-	struct set_element **handle = tsearch(element, set, hash_compare);
+	struct hash_to_list **handle = tsearch(element, set, hash_compare);
 	if (*handle == element) { // first of its kind
 		element->list = list_add(list_end, tree);
 		return tree;
@@ -164,7 +170,6 @@ static struct tree *clone_tree_root(struct tree *tree)
 	default:
 		free(new);
 		fatal("invalid type %d\n", tree->type);
-		return 0;
 	}
 
 	return new;
@@ -230,7 +235,7 @@ static void ref_invalidated_tree(struct tree *tree)
 	if (tree->state != INVALIDATED_TREE &&
 	    tree->state != VALIDATED_TREE) { // is reffed
 		tree->type = REF;
-		tree->u.ref.index = tree->state - 1;
+		tree->u.ref.hash = tree->state;
 		tree->state = VALIDATED_TREE;
 	}
 }
@@ -247,7 +252,13 @@ static int cmp_pri(pqueue_pri_t next, pqueue_pri_t curr)
 	return next < curr;
 }
 
-struct list *tree_merge_duplicates(struct term *term)
+static void set_pos(void *a, size_t position)
+{
+	(void)a;
+	(void)position;
+}
+
+struct tree *tree_merge_duplicates(struct term *term, void **all_trees)
 {
 	debug("building the merkle tree and deduplication set\n");
 
@@ -260,22 +271,25 @@ struct list *tree_merge_duplicates(struct term *term)
 	// construct priority queue while deleting set
 	// ~> sorts the candidates by get_pri
 	debug("constructing priority queue\n");
-	struct pqueue *prioritized = pqueue_init(2 << 15, cmp_pri, get_pri);
+	struct pqueue *prioritized =
+		pqueue_init(2 << 15, cmp_pri, get_pri, set_pos);
 	if (!prioritized)
 		fatal("can't create pqueue\n");
 	while (set) {
-		struct set_element *element = *(struct set_element **)set;
+		struct hash_to_list *element = *(struct hash_to_list **)set;
 		pqueue_insert(prioritized, element->list);
 		tdelete(element, &set, hash_compare);
 		free(element);
 	}
 
-	struct list *final = list_end;
 	struct list *invalidated = list_end;
 
 	// add longest (=> blueprint/structure of expression)
 	struct list *longest = pqueue_pop(prioritized);
-	final = list_add(final, longest->data);
+	struct hash_to_tree *element = malloc(sizeof(*element));
+	element->hash = ((struct tree *)longest->data)->hash;
+	element->tree = longest->data;
+	tsearch(element, all_trees, hash_compare);
 
 	debug("iterating priority queue, invalidating duplicates\n");
 	struct list *iterator;
@@ -294,7 +308,14 @@ struct list *tree_merge_duplicates(struct term *term)
 		// clone root so it doesn't get replaced by a ref to itself
 		struct tree *cloned_head = clone_tree_root(head);
 		cloned_head->state = INVALIDATED_TREE;
-		final = list_add(final, cloned_head);
+
+		element = malloc(sizeof(*element));
+		element->hash = cloned_head->hash;
+		element->tree = cloned_head;
+		struct hash_to_tree **handle =
+			tsearch(element, all_trees, hash_compare);
+		if (*handle != element)
+			free(element); // already exists, not needed
 
 		// invalidate all subtrees
 		// invalidated trees will be replaced with a reference
@@ -303,7 +324,7 @@ struct list *tree_merge_duplicates(struct term *term)
 			invalidate_tree(list->data, list->val);
 
 			// keep a ref for later replacement
-			((struct tree *)list->data)->state = final->val - 1;
+			((struct tree *)list->data)->state = head->hash;
 
 			invalidated = list_add(invalidated, list->data);
 			list = list->next;
@@ -323,7 +344,7 @@ struct list *tree_merge_duplicates(struct term *term)
 	// destroy prioritized list
 	pqueue_free(prioritized);
 
-	return final;
+	return longest->data;
 }
 
 void tree_destroy(struct list *table)
diff --git a/test/aoc.blc.dump b/test/aoc.blc.dump
index 33452fa..0cc6113 100644
--- a/test/aoc.blc.dump
+++ b/test/aoc.blc.dump
@@ -1,100 +1,100 @@
 
 === START BLOC ===
 | entries:	95
-| entry 93:	(4 3)
-| entry 92:	[(0 [[1]])]
-| entry 91:	(0 (1 3))
-| entry 90:	(0 [[[2]]])
-| entry 89:	[[[[3]]]]
-| entry 88:	([(0 [[0]])] 0)
-| entry 87:	(<92> 0)
-| entry 86:	((3 0) [[0]])
-| entry 85:	((3 0) [[1]])
-| entry 84:	(0 <89>)
-| entry 83:	((3 0) [[[0]]])
-| entry 82:	((0 [[0]]) [[1]])
-| entry 81:	[[[((0 2) 1)]]]
-| entry 80:	(((3 2) 1) 0)
-| entry 79:	[[[((2 0) 1)]]]
-| entry 78:	[[[(2 (1 0))]]]
-| entry 77:	[[[[(1 3)]]]]
-| entry 76:	((3 0) [[[1]]])
-| entry 75:	[(1 [((1 1) 0)])]
-| entry 74:	(1 <87>)
-| entry 73:	((3 0) [[[2]]])
-| entry 72:	([((3 3) 0)] 0)
-| entry 71:	[<82>]
-| entry 70:	((0 [[1]]) [[[0]]])
-| entry 69:	(<81> 0)
-| entry 68:	((2 1) <88>)
-| entry 67:	(((<93> 2) 1) 0)
-| entry 66:	[((0 [[[[[0]]]]]) [[1]])]
-| entry 65:	[(<70> [0])]
-| entry 64:	(<81> [[[2]]])
-| entry 63:	[[[[(0 <80>)]]]]
-| entry 62:	(<66> 0)
-| entry 61:	[[[[(1 <80>)]]]]
-| entry 60:	(<81> <89>)
-| entry 59:	(<62> 1)
-| entry 58:	(<63> 1)
-| entry 57:	(<81> <87>)
-| entry 56:	(<61> 1)
-| entry 55:	[((<70> [[[0]]]) [0])]
-| entry 54:	(<62> [[0]])
-| entry 53:	[[[[[(0 <67>)]]]]]
-| entry 52:	([[[[[(((<93> 1) 2) 0)]]]]] 0)
-| entry 51:	[[[[[(1 <67>)]]]]]
-| entry 50:	[[[[[(2 <67>)]]]]]
-| entry 49:	[(<75> <75>)]
-| entry 48:	(<53> 0)
-| entry 47:	((<78> <71>) 1)
-| entry 46:	(<53> 1)
-| entry 45:	[[[[[(((4 1) 0) <80>)]]]]]
-| entry 44:	(<51> 1)
-| entry 43:	(<50> 1)
-| entry 42:	(<45> 1)
-| entry 41:	([(<69> [[0]])] <87>)
-| entry 40:	(<81> <58>)
-| entry 39:	(<81> <56>)
-| entry 38:	([[((([<70>] 1) ([[[(0 2)]]] 0)) 1)]] 0)
-| entry 37:	([((<90> <77>) [[[[(0 3)]]]])] 0)
-| entry 36:	(<53> <83>)
-| entry 35:	(<51> <83>)
-| entry 34:	(<50> <83>)
-| entry 33:	(<51> <73>)
-| entry 32:	(<50> <76>)
-| entry 31:	(<81> <46>)
-| entry 30:	(<81> <44>)
-| entry 29:	(<81> <43>)
-| entry 28:	[(<42> <86>)]
-| entry 27:	[(((0 [[0]]) [((<81> [[1]]) 0)]) [((<81> [[0]]) 0)])]
-| entry 26:	[(([[[[[[((((5 2) 1) 0) <67>)]]]]]] 1) <83>)]
-| entry 25:	[((1 (<63> <85>)) (<61> <86>))]
-| entry 24:	([(0 0)] [[((<90> [(<61> <72>)]) [(<63> <72>)])]])
-| entry 23:	(<49> [[[[(<59> (((3 2) ((2 1) <87>)) <88>))]]]])
-| entry 22:	(<24> 1)
-| entry 21:	(<49> [[[(((<66> 1) 0) ((<81> (<92> 1)) ((2 ([(0 [[0]])] 1)) 0)))]]])
-| entry 20:	(<49> [[[(<54> ((<81> <74>) <68>))]]])
-| entry 19:	(((<49> [[[(<54> ((<74> <68>) 0))]]]) <47>) 0)
-| entry 18:	[(([[((0 1) [0])]] [[[0]]]) ((((0 [[1]]) [(<38> [[[2]]])]) [(<38> [[[1]]])]) [0]))]
-| entry 17:	[(((1 <36>) <32>) <35>)]
-| entry 16:	[(((1 <33>) <36>) <34>)]
-| entry 15:	(([([(1 (0 0))] [(1 (0 0))])] [[(((<84> [(<50> (2 0))]) [(<51> (2 0))]) [(<53> (2 0))])]]) 1)
-| entry 14:	((<79> (<49> [[[(<54> (((<74> <57>) [0]) <68>))]]])) <88>)
-| entry 13:	(<81> (((<49> [[[(<54> ((<74> (<57> <68>)) [[0]]))]]]) <47>) 0))
-| entry 12:	[([(0 [[0]])] (((0 (<64> [[[(1 2)]]])) [(0 [[(<39> (<63> 0))]])]) [(0 [[(<40> <56>)]])]))]
-| entry 11:	((<78> <12>) [[[[(((3 2) 0) 1)]]]])
-| entry 10:	[[(([(((0 [(<65> (<24> 0))]) [[(((0 [[0]]) [(2 0)]) [[[0]]])]]) [[(((0 (1 0)) [[[0]]]) [(2 0)])]])] 1) <37>)]]
-| entry 9:	[([(0 [[0]])] ((((0 (<60> <77>)) [(0 [[(<29> <46>)]])]) [(0 [[(<30> (<50> 0))]])]) [(0 [[(<31> <44>)]])]))]
-| entry 8:	[([(0 [[0]])] ((((0 (<60> [[[[(2 3)]]]])) [(0 [[(<29> (<51> 0))]])]) [(0 [[(<30> <46>)]])]) [(0 [[(<31> <43>)]])]))]
-| entry 7:	(2 (<9> 1))
-| entry 6:	((<49> [[[(<59> (<7> <88>))]]]) <89>)
-| entry 5:	(<49> [[[(<54> (((<55> 1) [[0]]) (<57> ((2 (<8> 1)) <88>))))]]])
-| entry 4:	[[(([([[((1 0) [[[0]]])]] ((((0 [[(((0 (<8> <15>)) (<9> <15>)) <15>)]]) [[[((((1 (<16> 1)) [(((1 (<53> <73>)) <34>) <33>)]) <26>) <16>)]]]) [[[((((1 (<17> 1)) <26>) [(((1 <35>) (<53> <76>)) <32>)]) <17>)]]]) [[[((((1 (<26> 1)) <16>) <17>) <26>)]]]))] 1) ([(((<84> [[[[[(2 4)]]]]]) [[[[[(1 4)]]]]]) [[[[[(0 4)]]]]])] 0))]]
-| entry 3:	[[((<4> 1) <52>)]]
-| entry 2:	((<23> <4>) <89>)
-| entry 1:	[[(((<78> [(<82> [[0]])]) <18>) ((<3> 1) 0))]]
-| entry 0:	[[((([[[((<49> [[((<62> 3) ((4 <87>) (1 <88>)))]]) 0)]]] <45>) [[[2]]]) ((([[[((<21> 0) (((<79> (([[[[((3 0) (2 1))]]]] <5>) (<49> [[(<69> (1 0))]]))) ([(((((<78> [(((0 [[1]]) [[0]]) [[0]])]) <18>) 0) <52>) 0)] ((<3> 2) (<6> 0)))) 1))]]] (<6> (<27> ([(<92> (((0 (<64> [[1]])) [(0 [[(<39> [[0]])]])]) [(0 [[((<81> (<90> <58>)) 0)]])]))] 1)))) [[0]]) (<27> 0)))]]
-| final:	[([(<57> (<2> ((<5> [[[[<91>]]]]) 0)))] ((<49> [[(<54> ((<21> ((<21> (1 (<14> ((<79> (<79> [[(<71> ((<1> 1) 0))]])) <87>)))) <41>)) (1 (<14> ((<79> (<79> <1>)) <87>)))))]]) ((<20> <2>) (((<49> [[[(<54> ([(<57> ((3 2) <88>))] (([[(<13> ([(<54> <88>)] <19>))]] 1) 0)))]]]) <55>) ((<20> ((<78> ((<23> [[((<4> (([[((((1 <89>) [((<3> <48>) 1)]) [((<4> <48>) 1)]) [<48>])]] [[[[(1 <91>)]]]]) 1)) 0)]]) <89>)) (<20> [(((<49> [[[(((<65> 0) 1) (<7> ([([(0 [[0]])] (((0 (<64> [[[2]]])) [(0 [[(<39> <58>)]])]) [(0 [[(<40> (<61> 0))]])]))] 0)))]]]) <89>) (([[((((<10> 0) 1) [[[2]]]) (<11> (([[(([([[((1 0) [[0]])]] (((0 [[((0 (<12> <22>)) <22>)]]) [[[(((1 (<25> 1)) [(<42> <85>)]) <25>)]]]) [[[(((1 (<28> 1)) <25>) <28>)]]]))] 1) <37>)]] ((<0> 1) 0)) (<11> ((<0> 0) 1)))))]] 0) [[[(0 (0 (0 (0 (1 (1 (0 (0 2))))))))]]]))]))) ((<49> [[([(((<66> <88>) <41>) (<57> (2 ([(0 [[0]])] <88>))))] (([[(<13> <19>)]] (<10> [[[(0 (1 (0 (1 (0 (0 (0 (0 2))))))))]]])) 0))]]) 0))))))]
+| entry 93:	[[[[(1 3)]]]]
+| entry 92:	(<20> 1)
+| entry 91:	((<9> (<2> [[[(<1> (((<18> <8>) [0]) <42>))]]])) <6>)
+| entry 90:	((3 0) [[0]])
+| entry 89:	(<0> <92>)
+| entry 88:	([(0 0)] [[((<46> [(<38> <76>)]) [(<22> <76>)])]])
+| entry 87:	((0 [[0]]) [[1]])
+| entry 86:	(2 (<39> 1))
+| entry 85:	((3 0) [[[1]]])
+| entry 84:	((3 0) [[1]])
+| entry 83:	[[[[[(((4 1) 0) <41>)]]]]]
+| entry 82:	((<19> <49>) [[[[(((3 2) 0) 1)]]]])
+| entry 81:	(<10> <85>)
+| entry 80:	(<2> [[[[(<25> (((3 2) ((2 1) <14>)) <6>))]]]])
+| entry 79:	(<0> <12>)
+| entry 78:	[(([[[[[[((((5 2) 1) 0) <5>)]]]]]] 1) <7>)]
+| entry 77:	(<83> 1)
+| entry 76:	([((3 3) 0)] 0)
+| entry 75:	[[((([[[((<2> [[((<15> 3) ((4 <14>) (1 <6>)))]]) 0)]]] <83>) [[[2]]]) ((([[[((<54> 0) (((<9> (([[[[((3 0) (2 1))]]]] <47>) (<2> [[(<52> (1 0))]]))) ([(((((<19> [(((0 [[1]]) [[0]]) [[0]])]) <44>) 0) <56>) 0)] ((<34> 2) (<61> 0)))) 1))]]] (<61> (<73> ([(<45> (((0 (<21> [[1]])) [(0 [[(<26> [[0]])]])]) [(0 [[((<0> (<46> <12>)) 0)]])]))] 1)))) [[0]]) (<73> 0)))]]
+| entry 74:	(<20> <7>)
+| entry 73:	[(((0 [[0]]) [((<0> [[1]]) 0)]) [((<0> [[0]]) 0)])]
+| entry 72:	((3 0) [[[2]]])
+| entry 71:	(4 3)
+| entry 70:	(<0> (((<2> [[[(<1> ((<18> (<8> <42>)) [[0]]))]]]) <27>) 0))
+| entry 69:	[(1 [((1 1) 0)])]
+| entry 68:	(<0> <3>)
+| entry 67:	(<20> <72>)
+| entry 66:	[<87>]
+| entry 65:	(<0> <40>)
+| entry 64:	[[(([(((0 [(<59> (<88> 0))]) [[(((0 [[0]]) [(2 0)]) [[[0]]])]]) [[(((0 (1 0)) [[[0]]]) [(2 0)])]])] 1) <55>)]]
+| entry 63:	[([(0 [[0]])] ((((0 (<68> [[[[(2 3)]]]])) [(0 [[(<37> (<20> 0))]])]) [(0 [[(<89> <40>)]])]) [(0 [[(<65> <51>)]])]))]
+| entry 62:	[((1 (<22> <84>)) (<38> <90>))]
+| entry 61:	((<2> [[[(<25> (<86> <6>))]]]) <3>)
+| entry 60:	(0 <3>)
+| entry 59:	[(<33> [0])]
+| entry 58:	(0 (1 3))
+| entry 57:	(<38> 1)
+| entry 56:	([[[[[(((<71> 1) 2) 0)]]]]] 0)
+| entry 55:	([((<46> <93>) [[[[(0 3)]]]])] 0)
+| entry 54:	(<2> [[[(((<31> 1) 0) ((<0> (<45> 1)) ((2 ([(0 [[0]])] 1)) 0)))]]])
+| entry 53:	([[((([<33>] 1) ([[[(0 2)]]] 0)) 1)]] 0)
+| entry 52:	(<0> 0)
+| entry 51:	(<10> 1)
+| entry 50:	[(<77> <90>)]
+| entry 49:	[([(0 [[0]])] (((0 (<21> [[[(1 2)]]])) [(0 [[(<26> (<22> 0))]])]) [(0 [[(<79> <57>)]])]))]
+| entry 48:	((<80> <16>) <3>)
+| entry 47:	(<2> [[[(<1> (((<32> 1) [[0]]) (<8> ((2 (<63> 1)) <6>))))]]])
+| entry 46:	(0 [[[2]]])
+| entry 45:	[(0 [[1]])]
+| entry 44:	[(([[((0 1) [0])]] [[[0]]]) ((((0 [[1]]) [(<53> [[[2]]])]) [(<53> [[[1]]])]) [0]))]
+| entry 43:	(<10> <7>)
+| entry 42:	((2 1) <6>)
+| entry 41:	(((3 2) 1) 0)
+| entry 40:	(<4> 1)
+| entry 39:	[([(0 [[0]])] ((((0 (<68> <93>)) [(0 [[(<37> <40>)]])]) [(0 [[(<89> (<10> 0))]])]) [(0 [[(<65> <92>)]])]))]
+| entry 38:	[[[[(1 <41>)]]]]
+| entry 37:	(<0> <51>)
+| entry 36:	(<4> <7>)
+| entry 35:	([(<52> [[0]])] <14>)
+| entry 34:	[[((<16> 1) <56>)]]
+| entry 33:	((0 [[1]]) [[[0]]])
+| entry 32:	[((<33> [[[0]]]) [0])]
+| entry 31:	[((0 [[[[[0]]]]]) [[1]])]
+| entry 30:	(<2> [[[(<1> ((<0> <18>) <42>))]]])
+| entry 29:	(((<2> [[[(<1> ((<18> <42>) 0))]]]) <27>) 0)
+| entry 28:	[[(((<19> [(<87> [[0]])]) <44>) ((<34> 1) 0))]]
+| entry 27:	((<19> <66>) 1)
+| entry 26:	(<0> <57>)
+| entry 25:	(<15> 1)
+| entry 24:	(<4> 0)
+| entry 23:	[(((1 <36>) <81>) <74>)]
+| entry 22:	[[[[(0 <41>)]]]]
+| entry 21:	(<0> [[[2]]])
+| entry 20:	[[[[[(1 <5>)]]]]]
+| entry 19:	[[[(2 (1 0))]]]
+| entry 18:	(1 <14>)
+| entry 17:	(([([(1 (0 0))] [(1 (0 0))])] [[(((<60> [(<10> (2 0))]) [(<20> (2 0))]) [(<4> (2 0))])]]) 1)
+| entry 16:	[[(([([[((1 0) [[[0]]])]] ((((0 [[(((0 (<63> <17>)) (<39> <17>)) <17>)]]) [[[((((1 (<11> 1)) [(((1 (<4> <72>)) <43>) <67>)]) <78>) <11>)]]]) [[[((((1 (<23> 1)) <78>) [(((1 <74>) (<4> <85>)) <81>)]) <23>)]]]) [[[((((1 (<78> 1)) <11>) <23>) <78>)]]]))] 1) ([(((<60> [[[[[(2 4)]]]]]) [[[[[(1 4)]]]]]) [[[[[(0 4)]]]]])] 0))]]
+| entry 15:	(<31> 0)
+| entry 14:	(<45> 0)
+| entry 13:	(<88> 1)
+| entry 12:	(<22> 1)
+| entry 11:	[(((1 <67>) <36>) <43>)]
+| entry 10:	[[[[[(2 <5>)]]]]]
+| entry 9:	[[[((2 0) 1)]]]
+| entry 8:	(<0> <14>)
+| entry 7:	((3 0) [[[0]]])
+| entry 6:	([(0 [[0]])] 0)
+| entry 5:	(((<71> 2) 1) 0)
+| entry 4:	[[[[[(0 <5>)]]]]]
+| entry 3:	[[[[3]]]]
+| entry 2:	[(<69> <69>)]
+| entry 1:	(<15> [[0]])
+| entry 0:	[[[((0 2) 1)]]]
+| final:	[([(<8> (<48> ((<47> [[[[<58>]]]]) 0)))] ((<2> [[(<1> ((<54> ((<54> (1 (<91> ((<9> (<9> [[(<66> ((<28> 1) 0))]])) <14>)))) <35>)) (1 (<91> ((<9> (<9> <28>)) <14>)))))]]) ((<30> <48>) (((<2> [[[(<1> ([(<8> ((3 2) <6>))] (([[(<70> ([(<1> <6>)] <29>))]] 1) 0)))]]]) <32>) ((<30> ((<19> ((<80> [[((<16> (([[((((1 <3>) [((<34> <24>) 1)]) [((<16> <24>) 1)]) [<24>])]] [[[[(1 <58>)]]]]) 1)) 0)]]) <3>)) (<30> [(((<2> [[[(((<59> 0) 1) (<86> ([([(0 [[0]])] (((0 (<21> [[[2]]])) [(0 [[(<26> <12>)]])]) [(0 [[(<79> (<38> 0))]])]))] 0)))]]]) <3>) (([[((((<64> 0) 1) [[[2]]]) (<82> (([[(([([[((1 0) [[0]])]] (((0 [[((0 (<49> <13>)) <13>)]]) [[[(((1 (<62> 1)) [(<77> <84>)]) <62>)]]]) [[[(((1 (<50> 1)) <62>) <50>)]]]))] 1) <55>)]] ((<75> 1) 0)) (<82> ((<75> 0) 1)))))]] 0) [[[(0 (0 (0 (0 (1 (1 (0 (0 2))))))))]]]))]))) ((<2> [[([(((<31> <6>) <35>) (<8> (2 ([(0 [[0]])] <6>))))] (([[(<70> <29>)]] (<64> [[[(0 (1 (0 (1 (0 (0 (0 (0 2))))))))]]])) 0))]]) 0))))))]
 === END BLOC ===
 
diff --git a/test/fac.blc.dump b/test/fac.blc.dump
index 51a658c..db72801 100644
--- a/test/fac.blc.dump
+++ b/test/fac.blc.dump
@@ -1,40 +1,40 @@
 
 === START BLOC ===
 | entries:	35
-| entry 33:	(4 3)
-| entry 32:	[[[[3]]]]
-| entry 31:	(0 <32>)
-| entry 30:	((3 0) [[[0]]])
-| entry 29:	[[[((0 2) 1)]]]
-| entry 28:	[[[[(1 3)]]]]
-| entry 27:	((3 0) [[[1]]])
-| entry 26:	[(1 [((1 1) 0)])]
-| entry 25:	((3 0) [[[2]]])
-| entry 24:	(((<33> 2) 1) 0)
-| entry 23:	(<29> <32>)
-| entry 22:	[[[[[(0 <24>)]]]]]
-| entry 21:	[[[[[(1 <24>)]]]]]
-| entry 20:	[[[[[(2 <24>)]]]]]
-| entry 19:	(<22> 0)
-| entry 18:	(<22> 1)
-| entry 17:	(<21> 1)
-| entry 16:	(<20> 1)
-| entry 15:	(<22> <30>)
-| entry 14:	(<21> <30>)
-| entry 13:	(<20> <30>)
-| entry 12:	(<20> <27>)
-| entry 11:	(<21> <25>)
-| entry 10:	(<29> <18>)
-| entry 9:	(<29> <17>)
-| entry 8:	(<29> <16>)
-| entry 7:	[(([[[[[[((((5 2) 1) 0) <24>)]]]]]] 1) <30>)]
-| entry 6:	([(((<31> [[[[[(2 4)]]]]]) [[[[[(1 4)]]]]]) [[[[[(0 4)]]]]])] 0)
-| entry 5:	[(((1 <15>) <12>) <14>)]
-| entry 4:	[(((1 <11>) <15>) <13>)]
-| entry 3:	([([(1 (0 0))] [(1 (0 0))])] [[(((<31> [(<20> (2 0))]) [(<21> (2 0))]) [(<22> (2 0))])]])
-| entry 2:	(<3> 1)
-| entry 1:	[([(0 [[0]])] ((((0 (<23> <28>)) [(0 [[(<8> <18>)]])]) [(0 [[(<9> (<20> 0))]])]) [(0 [[(<10> <17>)]])]))]
-| entry 0:	[[(([([[((1 0) [[[0]]])]] ((((0 [[(((0 ([([(0 [[0]])] ((((0 (<23> [[[[(2 3)]]]])) [(0 [[(<8> (<21> 0))]])]) [(0 [[(<9> <18>)]])]) [(0 [[(<10> <16>)]])]))] <2>)) (<1> <2>)) <2>)]]) [[[((((1 (<4> 1)) [(((1 (<22> <25>)) <13>) <11>)]) <7>) <4>)]]]) [[[((((1 (<5> 1)) <7>) [(((1 <14>) (<22> <27>)) <12>)]) <5>)]]]) [[[((((1 (<7> 1)) <4>) <5>) <7>)]]]))] 1) <6>)]]
-| final:	([((((([(<26> <26>)] [[[[[(((([[(([((((0 [([((((0 [[1]]) [[[0]]]) [[[0]]]) [0])] (<3> 0))]) [[((((0 [[0]]) [(2 0)]) [[[0]]]) [[[0]]])]]) [[((((0 [[0]]) [[[0]]]) [(2 0)]) [[[0]]])]]) [[((((0 (1 0)) [[[0]]]) [[[0]]]) [(2 0)])]])] 1) <6>)]] 2) (<1> 1)) 3) ((((4 (([[((((1 <32>) [(([[((<0> 1) ([[[[[(((<33> 1) 2) 0)]]]]] 0))]] <19>) 1)]) [((<0> <19>) 1)]) [<19>])]] 3) (0 2))) (<1> 2)) 1) 0))]]]]]) <28>) <28>) 0) [0])] [[[[(0 (1 (0 (1 3))))]]]])
+| entry 33:	(<2> <26>)
+| entry 32:	(<2> 1)
+| entry 31:	(<5> <32>)
+| entry 30:	[[(([([[((1 0) [[[0]]])]] ((((0 [[(((0 ([([(0 [[0]])] ((((0 (<27> [[[[(2 3)]]]])) [(0 [[(<13> (<2> 0))]])]) [(0 [[(<31> <12>)]])]) [(0 [[(<24> <19>)]])]))] <11>)) (<8> <11>)) <11>)]]) [[[((((1 (<10> 1)) [(((1 (<0> <26>)) <18>) <33>)]) <14>) <10>)]]]) [[[((((1 (<9> 1)) <14>) [(((1 <29>) (<0> <25>)) <17>)]) <9>)]]]) [[[((((1 (<14> 1)) <10>) <9>) <14>)]]]))] 1) <20>)]]
+| entry 29:	(<2> <1>)
+| entry 28:	(4 3)
+| entry 27:	(<5> <3>)
+| entry 26:	((3 0) [[[2]]])
+| entry 25:	((3 0) [[[1]]])
+| entry 24:	(<5> <12>)
+| entry 23:	(<0> <1>)
+| entry 22:	(<0> 0)
+| entry 21:	([([(1 (0 0))] [(1 (0 0))])] [[(((<16> [(<6> (2 0))]) [(<2> (2 0))]) [(<0> (2 0))])]])
+| entry 20:	([(((<16> [[[[[(2 4)]]]]]) [[[[[(1 4)]]]]]) [[[[[(0 4)]]]]])] 0)
+| entry 19:	(<6> 1)
+| entry 18:	(<6> <1>)
+| entry 17:	(<6> <25>)
+| entry 16:	(0 <3>)
+| entry 15:	[(1 [((1 1) 0)])]
+| entry 14:	[(([[[[[[((((5 2) 1) 0) <4>)]]]]]] 1) <1>)]
+| entry 13:	(<5> <19>)
+| entry 12:	(<0> 1)
+| entry 11:	(<21> 1)
+| entry 10:	[(((1 <33>) <23>) <18>)]
+| entry 9:	[(((1 <23>) <17>) <29>)]
+| entry 8:	[([(0 [[0]])] ((((0 (<27> <7>)) [(0 [[(<13> <12>)]])]) [(0 [[(<31> (<6> 0))]])]) [(0 [[(<24> <32>)]])]))]
+| entry 7:	[[[[(1 3)]]]]
+| entry 6:	[[[[[(2 <4>)]]]]]
+| entry 5:	[[[((0 2) 1)]]]
+| entry 4:	(((<28> 2) 1) 0)
+| entry 3:	[[[[3]]]]
+| entry 2:	[[[[[(1 <4>)]]]]]
+| entry 1:	((3 0) [[[0]]])
+| entry 0:	[[[[[(0 <4>)]]]]]
+| final:	([((((([(<15> <15>)] [[[[[(((([[(([((((0 [([((((0 [[1]]) [[[0]]]) [[[0]]]) [0])] (<21> 0))]) [[((((0 [[0]]) [(2 0)]) [[[0]]]) [[[0]]])]]) [[((((0 [[0]]) [[[0]]]) [(2 0)]) [[[0]]])]]) [[((((0 (1 0)) [[[0]]]) [[[0]]]) [(2 0)])]])] 1) <20>)]] 2) (<8> 1)) 3) ((((4 (([[((((1 <3>) [(([[((<30> 1) ([[[[[(((<28> 1) 2) 0)]]]]] 0))]] <22>) 1)]) [((<30> <22>) 1)]) [<22>])]] 3) (0 2))) (<8> 2)) 1) 0))]]]]]) <7>) <7>) 0) [0])] [[[[(0 (1 (0 (1 3))))]]]])
 === END BLOC ===