1 files changed, 97 insertions, 2 deletions

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 = {