Add basic topological sort for shared blc

2 files changed, 103 insertions, 7 deletions

diff --git a/readme.md b/readme.md
index a5a85fb..fe9f111 100644
--- a/readme.md
+++ b/readme.md
@@ -1,9 +1,9 @@
 # BLoCade
 
-[BLoC](https://github.com/marvinborner/bloc) is an optimized file format
-for binary lambda calculus (BLC).
+[BLoC](https://github.com/marvinborner/bloc) is a file format for shared
+binary lambda calculus (BLC).
 
-BLoCade is the BLoC-aid and turns BLoC files back into executable files
+BLoCade, the BLoC-aid, turns BLoC files back into executable files
 (targets). This is useful for [bruijn](https://bruijn.marvinborner.de),
 benchmarking, or general term optimization.
 
@@ -11,8 +11,9 @@ benchmarking, or general term optimization.
 
 -   BLC (sharing by abstraction): Terms having BLoC entry indices get
     abstracted and applied to the respective term. The indices get
-    converted to De Bruijn indices. Flag `bblc` (bits) and `blc` (ASCII
-    0/1).
+    converted to De Bruijn indices. The dependency graph is resolved by
+    a topological sort so De Bruijn indices won't get unnecessarily
+    large. Flag `bblc` (bits) and `blc` (ASCII 0/1).
 -   BLC (unshared): Every BLoC entry gets reinserted into the original
     term. Do not use this if you want efficiency or small files. Flag
     `unbblc` (bits) and `unblc` (ASCII 0/1).
diff --git a/src/targets/blc.c b/src/targets/blc.c
index 46d63a5..73096db 100644
--- a/src/targets/blc.c
+++ b/src/targets/blc.c
@@ -37,10 +37,105 @@ static void fprint_blc(struct term *term, struct bloc_parsed *bloc, FILE *file)
 	}
 }
 
+static void bitmap_deps(struct bloc_parsed *bloc, char *bitmap,
+			struct term *term)
+{
+	switch (term->type) {
+	case ABS:
+		bitmap_deps(bloc, bitmap, term->u.abs.term);
+		break;
+	case APP:
+		bitmap_deps(bloc, bitmap, term->u.app.lhs);
+		bitmap_deps(bloc, bitmap, term->u.app.rhs);
+		break;
+	case VAR:
+		break;
+	case REF:
+		if (term->u.ref.index + 1 >= bloc->length)
+			fatal("invalid ref index %ld\n", term->u.ref.index);
+		bitmap[bloc->length - term->u.ref.index - 2] = 1;
+		// for recursive bitmapping, not needed for DFS
+		/* bitmap_deps( */
+		/* 	bloc, bitmap, */
+		/* 	bloc->entries[bloc->length - term->u.ref.index - 2]); */
+		break;
+	default:
+		fatal("invalid type %d\n", term->type);
+	}
+}
+
+static void print_deps(size_t length, char *bitmap)
+{
+	for (size_t i = 0; i < length; i++) {
+		if (bitmap[i])
+			printf("%ld,", i);
+	}
+	printf("\n");
+}
+
+#define PERMANENT_MARK 0x1
+#define TEMPORARY_MARK 0x2
+static void visit(char **bitmaps, char *marks, size_t length, size_t n)
+{
+	if (marks[n] & PERMANENT_MARK)
+		return;
+	if (marks[n] & TEMPORARY_MARK)
+		fatal("dependency graph has a cycle (infinite term)\n");
+
+	marks[n] |= TEMPORARY_MARK;
+	for (size_t i = 0; i < length; i++) {
+		if (bitmaps[n][i]) {
+			visit(bitmaps, marks, length, i);
+		}
+	}
+	marks[n] &= ~TEMPORARY_MARK;
+
+	marks[n] |= PERMANENT_MARK;
+	printf("PUSH %ld\n", n);
+}
+
+static void topological_sort(char **bitmaps, size_t length)
+{
+	char *marks = calloc(length, 1);
+
+	int marked = 1;
+	while (marked) {
+		marked = 0;
+		for (size_t i = 0; i < length; i++) {
+			if ((marks[i] & PERMANENT_MARK) == 0)
+				marked = 1; // still has nodes without permanent
+			if (marks[i])
+				continue;
+			visit(bitmaps, marks, length, i);
+		}
+	}
+
+	free(marks);
+}
+
 static void write_blc(struct bloc_parsed *bloc, FILE *file)
 {
-	fprint_blc(bloc->entries[bloc->length - 1], bloc, file);
-	fprintf(file, "\n");
+	/* fprint_blc(bloc->entries[bloc->length - 1], bloc, file); */
+	/* fprintf(file, "\n"); */
+
+	char **bitmaps = malloc(bloc->length * sizeof(*bitmaps));
+	for (size_t i = 0; i < bloc->length; i++) {
+		char *bitmap = calloc(bloc->length, 1);
+		bitmap_deps(bloc, bitmap, bloc->entries[i]);
+
+		/* printf("entry %ld\n", bloc->length - i - 2); */
+		/* printf("entry %ld\n", i); */
+		/* print_deps(bloc->length, bitmap); */
+		bitmaps[i] = bitmap;
+	}
+	/* printf("\n"); */
+
+	topological_sort(bitmaps, bloc->length);
+
+	for (size_t i = 0; i < bloc->length; i++) {
+		free(bitmaps[i]);
+	}
+	free(bitmaps);
 }
 
 struct target_spec target_blc = {