Topologically sort types and their dependencies during lowering, report cycles

Signed-off-by: Mel <mel@rnrd.eu>

1 files changed, 158 insertions, 2 deletions

diff --git a/boot/lower.c b/boot/lower.c
index 8f41c1f..b2e6de6 100644
--- a/boot/lower.c
+++ b/boot/lower.c
@@ -411,11 +411,166 @@ lower_pass_1(struct Unit* unit, struct Tree* tree)
     lower_pass_1_fill_bodies(unit, tree);
 }
 
+// return line number for the given byte position in the source. (1-based)
+uint
+lower_span_to_line(struct String source, struct Span span)
+{
+    uint line = 1;
+    uint upto = span.start;
+    if (upto > string_length(source)) upto = string_length(source);
+    for (uint i = 0; i < upto; ++i) {
+        if (string_at(source, i) == '\n') line++;
+    }
+    return line;
+}
+
+// builds a nice & friendly cycle detection message and emits it as a diagnostic.
+// `chain` is the path we walked while looking for the cycle, and
+// `cycle_start` is the chain index at which the cycle closes.
 void
-lower_tree(struct Tree* tree, struct Source_File source, struct Unit* unit)
+lower_report_type_cycle(
+    struct Unit* unit, struct Source_File source, struct _Array* chain, uint cycle_start)
+{
+    struct String_Buffer buf = string_buffer_new(512);
+    string_buffer_append_c_str(&buf, "type cycle detected:\n");
+
+    uint chain_len = array_length(chain);
+    for (uint k = cycle_start; k < chain_len; ++k) {
+        Type_Id current_id = *array_at(Type_Id, chain, k);
+        Type_Id next_id;
+        if (k + 1 < chain_len)
+            next_id = *array_at(Type_Id, chain, k + 1);
+        else
+            next_id = *array_at(Type_Id, chain, cycle_start);
+
+        struct Type* current = *array_at(struct Type*, &unit->types.entries, current_id);
+        struct Type* next = *array_at(struct Type*, &unit->types.entries, next_id);
+        uint line = lower_span_to_line(source.source, current->span);
+
+        ascii line_buf[256];
+        snprintf(
+            line_buf, sizeof line_buf, "  %s (line %lu) depends on %s\n",
+            string_c_str(current->name), line, string_c_str(next->name));
+        string_buffer_append_c_str(&buf, line_buf);
+    }
+    string_buffer_append_c_str(
+        &buf, "hint: break the cycle with a reference (use `&T` instead of `T`). :)");
+
+    Type_Id origin_id = *array_at(Type_Id, chain, cycle_start);
+    struct Type* origin = *array_at(struct Type*, &unit->types.entries, origin_id);
+    lower_emit_error(unit, origin->span, string_buffer_to_string(&buf));
+}
+
+// topologically sorting the unit's type dependency graph.
+// implemented through kahn's algorithm.
+// see: https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm
+// final ordering for the type emission is stable, types declared earlier
+// are always first to emit when their vertex in-degree is 0.
+// cycles reported as diagnostic, partial emission order will still be completed.
+void
+lower_topological_sort_dependency_graph(struct Unit* unit, struct Source_File source)
 {
-    (void)source;
+    const uint done_sentinel = (uint)-1; // marks vertecies that have been processed
+
+    uint n = array_length(&unit->types.entries);
+    if (n == 0) return;
+
+    // for i, holds in-degree for type i.
+    Array(uint) in_degree = array_new(uint, n);
+    for (uint i = 0; i < n; ++i) {
+        struct Type* type = *array_at(struct Type*, &unit->types.entries, i);
+        uint deg = array_length(&type->depends_on);
+        array_push(&in_degree, &deg);
+    }
+
+    // for i, holds every index of types that depends on type i.
+    Array(struct _Array) reverse_deps = array_new(struct _Array, n);
+    for (uint i = 0; i < n; ++i) {
+        struct _Array slot = _array_new(sizeof(Type_Id), 16);
+        array_push(&reverse_deps, &slot);
+    }
+    for (uint i = 0; i < n; ++i) {
+        struct Type* type = *array_at(struct Type*, &unit->types.entries, i);
+        Type_Id me = (Type_Id)i;
+        FOR_EACH_ARRAY(Type_Id, dep, &type->depends_on, {
+            struct _Array* slot = array_at(struct _Array, &reverse_deps, dep);
+            _array_push(slot, &me);
+        })
+    }
+
+    uint output_count = 0;
+    while (output_count < n) {
+        Type_Id chosen = (Type_Id)-1;
+        for (uint i = 0; i < n; ++i) {
+            if (*array_at(uint, &in_degree, i) == 0) {
+                chosen = (Type_Id)i;
+                break;
+            }
+        }
+        if (chosen == (Type_Id)-1) break; // cycle
 
+        array_push(&unit->type_emission_order, &chosen);
+        output_count++;
+        *array_at(uint, &in_degree, chosen) = done_sentinel;
+
+        struct _Array* dependents = array_at(struct _Array, &reverse_deps, chosen);
+        FOR_EACH_ARRAY(Type_Id, dependent, dependents, {
+            uint* d = array_at(uint, &in_degree, dependent);
+            if (*d != done_sentinel) (*d)--;
+        })
+    }
+
+    if (output_count == n) return;
+
+    // we've got a cycle! walk starting from the lowest type that's
+    // still pending, following edges until we find type we already saw.
+    // we revisit an id.
+    Type_Id start = (Type_Id)-1;
+    for (uint i = 0; i < n; ++i) {
+        if (*array_at(uint, &in_degree, i) != done_sentinel) {
+            start = (Type_Id)i;
+            break;
+        }
+    }
+    if (start == (Type_Id)-1) return;
+
+    Array(Type_Id) chain = array_new(Type_Id, 64);
+    array_push(&chain, &start);
+    Type_Id current = start;
+
+    while (true) {
+        struct Type* type = *array_at(struct Type*, &unit->types.entries, current);
+
+        Type_Id next = (Type_Id)-1;
+        FOR_EACH_ARRAY(Type_Id, dep, &type->depends_on, {
+            if (*array_at(uint, &in_degree, dep) != done_sentinel) {
+                next = dep;
+                break;
+            }
+        })
+        if (next == (Type_Id)-1) return; // not a real cycle
+
+        uint chain_len = array_length(&chain);
+        uint found_at = chain_len;
+        for (uint k = 0; k < chain_len; ++k) {
+            if (*array_at(Type_Id, &chain, k) == next) {
+                found_at = k;
+                break;
+            }
+        }
+        if (found_at < chain_len) {
+            lower_report_type_cycle(unit, source, &chain, found_at);
+            return;
+        }
+
+        array_push(&chain, &next);
+        current = next;
+    }
+}
+
+void
+lower_tree(struct Tree* tree, struct Source_File source, struct Unit* unit)
+{
     unit->types.entries = array_new(struct Type*, 256);
     unit->types.by_hash = array_new(struct Type_Hash_To_Id, 256);
     unit->types.by_name = array_new(struct Type_Name_To_Id, 256);
@@ -438,4 +593,5 @@ lower_tree(struct Tree* tree, struct Source_File source, struct Unit* unit)
     unit->types.primitive_void_id = lower_seed_primitive(unit, "void");
 
     if (tree) lower_pass_1(unit, tree);
+    lower_topological_sort_dependency_graph(unit, source);
 }