Lower down structural (inline) type definitions into type objects

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

1 files changed, 314 insertions, 55 deletions

diff --git a/boot/lower.c b/boot/lower.c
index b2e6de6..1218281 100644
--- a/boot/lower.c
+++ b/boot/lower.c
@@ -26,6 +26,21 @@
 
 #include "catboot.h"
 
+struct Lower_Context
+{
+    // the translation unit being created
+    struct Unit* unit;
+
+    // text source of the unit in translation
+    // used for attaching diagnostics to correct lines
+    struct Source_File source;
+
+    // monotonic counter of synthesized types
+    uint synthetic_type_counter;
+
+    // TODO: add function & block scope data
+};
+
 void
 lower_emit_error(struct Unit* unit, struct Span span, struct String message)
 {
@@ -84,16 +99,253 @@ lower_seed_primitive(struct Unit* unit, const ascii* name)
     return id;
 }
 
+// structural fingerprint for a source type.
+// two type objects describing the same type shape should always
+// produce identical fingerprints.
+struct String
+lower_type_fingerprint(struct Tree_Type* tree_type)
+{
+    if (!tree_type || tree_type->type == TREE_TYPE_NONE) return string_from_static_c_string("void");
+
+    switch (tree_type->type) {
+    case TREE_TYPE_NAME:
+        return tree_type->value.name.name;
+    case TREE_TYPE_REFERENCE:
+        return string_concatenate(
+            ARG_ASCII, "ref(", ARG_STRING,
+            lower_type_fingerprint(tree_type->value.reference.referenced_type), ARG_ASCII, ")",
+            ARG_END);
+    case TREE_TYPE_MAYBE:
+        return string_concatenate(
+            ARG_ASCII, "maybe(", ARG_STRING,
+            lower_type_fingerprint(tree_type->value.maybe.inner_type), ARG_ASCII, ")", ARG_END);
+    case TREE_TYPE_ARRAY:
+        return string_concatenate(
+            ARG_ASCII, "array(", ARG_STRING,
+            lower_type_fingerprint(tree_type->value.array.element_type), ARG_ASCII, ")", ARG_END);
+    case TREE_TYPE_TUPLE: {
+        struct String_Buffer buf = string_buffer_new(256);
+        string_buffer_append_c_str(&buf, "tuple(");
+        bool first = true;
+        FOR_EACH (struct Tree_Type*, current, tree_type->value.tuple.head) {
+            if (!first) string_buffer_append_c_str(&buf, ",");
+            string_buffer_append(&buf, lower_type_fingerprint(current));
+            first = false;
+        }
+        string_buffer_append_c_str(&buf, ")");
+        return string_buffer_to_string(&buf);
+    }
+    case TREE_TYPE_STRUCTURE: {
+        struct String_Buffer buf = string_buffer_new(256);
+        string_buffer_append_c_str(&buf, "struct(");
+        bool first = true;
+        FOR_EACH (struct Tree_Type*, field, tree_type->value.structure.fields) {
+            if (!first) string_buffer_append_c_str(&buf, ",");
+            string_buffer_append(&buf, field->value_name);
+            string_buffer_append_c_str(&buf, ":");
+            string_buffer_append(&buf, lower_type_fingerprint(field));
+            first = false;
+        }
+        string_buffer_append_c_str(&buf, ")");
+        return string_buffer_to_string(&buf);
+    }
+    case TREE_TYPE_FUNCTION: {
+        struct String_Buffer buf = string_buffer_new(256);
+        string_buffer_append_c_str(&buf, "fun(");
+        string_buffer_append(
+            &buf, lower_type_fingerprint(tree_type->value.function.header.return_type));
+        string_buffer_append_c_str(&buf, ";");
+        bool first = true;
+        FOR_EACH (
+            struct Tree_Type*, param, tree_type->value.function.header.parameters_type_and_name) {
+            if (!first) string_buffer_append_c_str(&buf, ",");
+            string_buffer_append(&buf, lower_type_fingerprint(param));
+            first = false;
+        }
+        string_buffer_append_c_str(&buf, ")");
+        return string_buffer_to_string(&buf);
+    }
+    default:
+        return string_from_static_c_string("unknown");
+    }
+}
+
+struct Type_Ref lower_intern_type_ref(struct Lower_Context* ctx, struct Tree_Type* tree_type);
+
+// adds a hard dependency on a type to a type object.
+// only by-value references count as hard dependencies,
+// anything else makes this a no-op.
+void
+lower_add_dependency(struct Type* type, struct Type_Ref ref)
+{
+    if (array_length(&ref.mods) > 0) {
+        enum Type_Modifier outer = *array_at(enum Type_Modifier, &ref.mods, 0);
+        if (outer == TYPE_MOD_REFERENCE) return;
+    }
+    array_push(&type->depends_on, &ref.type_id);
+}
+
+// create a synthetic type name for a structural type.
+struct String
+lower_synthesize_type_name(struct Lower_Context* ctx)
+{
+    const ascii* synthetic_type_name_template = "__cat_type_%lu";
+
+    ascii name_buf[64];
+    snprintf(name_buf, sizeof name_buf, synthetic_type_name_template, ctx->synthetic_type_counter++);
+    return string_from_c_string(name_buf);
+}
+
+// look up an existing structural synthetic by hash, or build a fresh one.
+// inner type references are interned, contributing to dependencies.
+Type_Id
+lower_synthesize_structural(struct Lower_Context* ctx, struct Tree_Type* tree_type, uint64 hash)
+{
+    FOR_EACH_ARRAY(struct Type_Hash_To_Id, mapping, &ctx->unit->types.by_hash, {
+        if (mapping.hash == hash) return mapping.id;
+    })
+
+    Type_Id id = array_length(&ctx->unit->types.entries);
+    struct String name = lower_synthesize_type_name(ctx);
+
+    struct Type* type = type_new(id, TYPE_NONE, name, tree_type->span);
+    type->synthetic = true;
+    type->structural_hash = hash;
+    type->depends_on = array_new(Type_Id, 16);
+    array_push(&ctx->unit->types.entries, &type);
+
+    struct Type_Hash_To_Id mapping = { .hash = hash, .id = id };
+    array_push(&ctx->unit->types.by_hash, &mapping);
+
+    switch (tree_type->type) {
+    case TREE_TYPE_MAYBE: {
+        // `T?` -> `struct { bool present; T value; }`
+        type->kind = TYPE_STRUCTURE;
+
+        type->value.structure.fields = array_new(struct Field, 4);
+
+        struct Field present_f = {
+            .name = string_from_static_c_string("present"),
+            .type = {
+                .type_id = ctx->unit->types.primitive_bool_id,
+                .mods = array_new(enum Type_Modifier, 1),
+            },
+        };
+        array_push(&type->value.structure.fields, &present_f);
+        Type_Id bool_id = ctx->unit->types.primitive_bool_id;
+        array_push(&type->depends_on, &bool_id);
+
+        struct Field value_f = {
+            .name = string_from_static_c_string("value"),
+            .type = lower_intern_type_ref(ctx, tree_type->value.maybe.inner_type),
+        };
+        array_push(&type->value.structure.fields, &value_f);
+        lower_add_dependency(type, value_f.type); // possibly hard dependency
+        break;
+    }
+    case TREE_TYPE_ARRAY: {
+        // `[T]` -> `struct { &T data; uint length; }`
+        type->kind = TYPE_STRUCTURE;
+
+        type->value.structure.fields = array_new(struct Field, 4);
+
+        struct Type_Ref inner = lower_intern_type_ref(ctx, tree_type->value.array.element_type);
+        struct Type_Ref data_ref = {
+            .type_id = inner.type_id,
+            .mods = array_new(enum Type_Modifier, 4),
+        };
+        FOR_EACH_ARRAY(enum Type_Modifier, m, &inner.mods, { array_push(&data_ref.mods, &m); })
+        enum Type_Modifier ptr = TYPE_MOD_REFERENCE;
+        array_push(&data_ref.mods, &ptr);
+
+        struct Field data_f = {
+            .name = string_from_static_c_string("data"),
+            .type = data_ref,
+        };
+        array_push(&type->value.structure.fields, &data_f);
+        // no dependency
+
+        struct Field length_f = {
+            .name = string_from_static_c_string("length"),
+            .type = {
+                .type_id = ctx->unit->types.primitive_uint_id,
+                .mods = array_new(enum Type_Modifier, 1),
+            },
+        };
+        array_push(&type->value.structure.fields, &length_f);
+        Type_Id uint_id = ctx->unit->types.primitive_uint_id;
+        array_push(&type->depends_on, &uint_id);
+        break;
+    }
+    case TREE_TYPE_TUPLE: {
+        // `(T1, T2, ...)` -> `struct { T1 _0; T2 _1; ... }`
+        type->kind = TYPE_STRUCTURE;
+
+        type->value.structure.fields = array_new(struct Field, 16);
+        uint idx = 0;
+        FOR_EACH (struct Tree_Type*, current, tree_type->value.tuple.head) {
+            ascii field_buf[16];
+            snprintf(field_buf, sizeof field_buf, "_%lu", idx++);
+            struct Field f = {
+                .name = string_from_c_string(field_buf),
+                .type = lower_intern_type_ref(ctx, current),
+            };
+            array_push(&type->value.structure.fields, &f);
+            lower_add_dependency(type, f.type); // possibly hard dependency for each element
+        }
+        break;
+    }
+    case TREE_TYPE_STRUCTURE: {
+        // `{ x, y T }` -> `struct { uint x; uint y; }`
+        type->kind = TYPE_STRUCTURE;
+
+        type->value.structure.fields = array_new(struct Field, 16);
+        FOR_EACH (struct Tree_Type*, tree_field, tree_type->value.structure.fields) {
+            struct Field f = {
+                .name = tree_field->value_name,
+                .type = lower_intern_type_ref(ctx, tree_field),
+            };
+            array_push(&type->value.structure.fields, &f);
+            lower_add_dependency(type, f.type); // possibly hard dependency for each field
+        }
+        break;
+    }
+    case TREE_TYPE_FUNCTION: {
+        // `fun x(n X) Y` -> `Y x(X n) {}`
+        type->kind = TYPE_FUNCTION;
+
+        struct Tree_Function_Header* header = &tree_type->value.function.header;
+
+        type->value.function.return_type = lower_intern_type_ref(ctx, header->return_type);
+        lower_add_dependency(type, type->value.function.return_type); // possibly hard dependency on return
+
+        type->value.function.params = array_new(struct Type_Ref, 16);
+        bool variadic = false;
+        FOR_EACH (struct Tree_Type*, param, header->parameters_type_and_name) {
+            struct Type_Ref ref = lower_intern_type_ref(ctx, param);
+            array_push(&type->value.function.params, &ref);
+            lower_add_dependency(type, ref); // possibly hard dependency for parameter
+            if (param->variadic) variadic = true;
+        }
+        type->value.function.variadic = variadic;
+        break;
+    }
+    default:
+        // unreachable!
+        break;
+    }
+
+    return id;
+}
+
 // turns a source type expression into a concrete type reference object.
-// resolving named types from the type table.
-// unwraps any type modifiers (like references, arrays, etc.),
-// adding them into the type reference object.
+// resolves named types from the type table, peels out reference modifiers,
+// and synthesizes new entries for structural type shapes.
 struct Type_Ref
-lower_intern_type_ref(struct Unit* unit, struct Tree_Type* tree_type)
+lower_intern_type_ref(struct Lower_Context* ctx, struct Tree_Type* tree_type)
 {
-    // TODO: support synthetic structural types.
     struct Type_Ref ref = {
-        .type_id = unit->types.primitive_void_id,
+        .type_id = ctx->unit->types.primitive_void_id,
         .mods = array_new(enum Type_Modifier, 4),
     };
 
@@ -111,38 +363,34 @@ lower_intern_type_ref(struct Unit* unit, struct Tree_Type* tree_type)
     switch (current->type) {
     case TREE_TYPE_NAME: {
         Type_Id id;
-        // at this point we know all top-level types (independent of order),
-        // if we fail to find the type referenced by the name, we know for a fact
-        // this type does not exist.
-        if (lower_type_lookup_by_name(unit, current->value.name.name, &id)) {
+        if (lower_type_lookup_by_name(ctx->unit, current->value.name.name, &id)) {
             ref.type_id = id;
         } else {
             lower_emit_error(
-                unit, current->span,
+                ctx->unit, current->span,
                 string_concatenate(
                     ARG_ASCII, "undefined type '", ARG_STRING, current->value.name.name, ARG_ASCII,
                     "'", ARG_END));
         }
         return ref;
     }
-    default:
-        lower_emit_error_c(
-            unit, current->span,
-            "unimplemented: only named types and references are supported for now");
+    case TREE_TYPE_MAYBE:
+    case TREE_TYPE_ARRAY:
+    case TREE_TYPE_TUPLE:
+    case TREE_TYPE_STRUCTURE:
+    case TREE_TYPE_FUNCTION: {
+        struct String fp = lower_type_fingerprint(current);
+        uint64 hash = fnv1a_64(fp);
+        ref.type_id = lower_synthesize_structural(ctx, current, hash);
         return ref;
     }
-}
-
-// adds a by-value dependency. by-pointer references don't add — a forward
-// declaration of the target is enough to use it through a pointer.
-void
-lower_add_dependency(struct Type* type, struct Type_Ref ref)
-{
-    if (array_length(&ref.mods) > 0) {
-        enum Type_Modifier outer = *array_at(enum Type_Modifier, &ref.mods, 0);
-        if (outer == TYPE_MOD_REFERENCE) return;
+    case TREE_TYPE_MAP:
+        lower_emit_error_c(ctx->unit, current->span, "unimplemented: map types");
+        return ref;
+    default:
+        lower_emit_error_c(ctx->unit, current->span, "unimplemented: this type form");
+        return ref;
     }
-    array_push(&type->depends_on, &ref.type_id);
 }
 
 // is this source statement a function?
@@ -235,10 +483,10 @@ lower_register_type_shell(struct Unit* unit, struct String name, struct Span spa
 
 void
 lower_fill_function_signature(
-    struct Unit* unit, struct Function* fn, struct Tree_Expression* fn_expr)
+    struct Lower_Context* ctx, struct Function* fn, struct Tree_Expression* fn_expr)
 {
     fn->is_main = string_equals_c_str(fn->name, "main");
-    fn->return_type = lower_intern_type_ref(unit, fn_expr->value.function.header.return_type);
+    fn->return_type = lower_intern_type_ref(ctx, fn_expr->value.function.header.return_type);
     fn->params = array_new(struct Param, 16);
 
     bool variadic = false;
@@ -246,7 +494,7 @@ lower_fill_function_signature(
         struct Tree_Type*, param_type, fn_expr->value.function.header.parameters_type_and_name) {
         struct Param p = {
             .name = param_type->value_name,
-            .type = lower_intern_type_ref(unit, param_type),
+            .type = lower_intern_type_ref(ctx, param_type),
         };
         array_push(&fn->params, &p);
         if (param_type->variadic) variadic = true;
@@ -258,19 +506,19 @@ lower_fill_function_signature(
 }
 
 void
-lower_fill_type_body(struct Unit* unit, struct Type* type, struct Tree_Type* tree_type)
+lower_fill_type_body(struct Lower_Context* ctx, struct Type* type, struct Tree_Type* tree_type)
 {
     switch (tree_type->type) {
     case TREE_TYPE_NAME: {
         type->kind = TYPE_ALIAS;
         Type_Id target_id;
-        if (lower_type_lookup_by_name(unit, tree_type->value.name.name, &target_id)) {
+        if (lower_type_lookup_by_name(ctx->unit, tree_type->value.name.name, &target_id)) {
             type->value.alias.target_id = target_id;
             // aliases always need their target's full definition.
             array_push(&type->depends_on, &target_id);
         } else {
             lower_emit_error(
-                unit, tree_type->span,
+                ctx->unit, tree_type->span,
                 string_concatenate(
                     ARG_ASCII, "undefined type '", ARG_STRING, tree_type->value.name.name,
                     ARG_ASCII, "'", ARG_END));
@@ -283,7 +531,7 @@ lower_fill_type_body(struct Unit* unit, struct Type* type, struct Tree_Type* tre
         FOR_EACH (struct Tree_Type*, tree_field, tree_type->value.structure.fields) {
             struct Field f = {
                 .name = tree_field->value_name,
-                .type = lower_intern_type_ref(unit, tree_field),
+                .type = lower_intern_type_ref(ctx, tree_field),
             };
             array_push(&type->value.structure.fields, &f);
             lower_add_dependency(type, f.type);
@@ -302,7 +550,7 @@ lower_fill_type_body(struct Unit* unit, struct Type* type, struct Tree_Type* tre
                 .payload = { 0 },
             };
             if (c.has_payload) {
-                c.payload = lower_intern_type_ref(unit, tree_case);
+                c.payload = lower_intern_type_ref(ctx, tree_case);
                 lower_add_dependency(type, c.payload);
             }
             array_push(&type->value.variant.cases, &c);
@@ -312,13 +560,13 @@ lower_fill_type_body(struct Unit* unit, struct Type* type, struct Tree_Type* tre
     case TREE_TYPE_FUNCTION: {
         type->kind = TYPE_FUNCTION;
         struct Tree_Function_Header* header = &tree_type->value.function.header;
-        type->value.function.return_type = lower_intern_type_ref(unit, header->return_type);
+        type->value.function.return_type = lower_intern_type_ref(ctx, header->return_type);
         lower_add_dependency(type, type->value.function.return_type);
         type->value.function.params = array_new(struct Type_Ref, 16);
 
         bool variadic = false;
         FOR_EACH (struct Tree_Type*, param_type, header->parameters_type_and_name) {
-            struct Type_Ref ref = lower_intern_type_ref(unit, param_type);
+            struct Type_Ref ref = lower_intern_type_ref(ctx, param_type);
             array_push(&type->value.function.params, &ref);
             lower_add_dependency(type, ref);
             if (param_type->variadic) variadic = true;
@@ -327,18 +575,22 @@ lower_fill_type_body(struct Unit* unit, struct Type* type, struct Tree_Type* tre
         break;
     }
     case TREE_TYPE_CLASS:
-        lower_emit_error_c(unit, tree_type->span, "unimplemented: class types");
+        lower_emit_error_c(ctx->unit, tree_type->span, "unimplemented: class types");
         break;
-    default:
-        // structural compound forms (array, maybe, tuple, map) at top level
-        // belong to step 10 (structural canonicalization).
-        lower_emit_error_c(unit, tree_type->span, "unimplemented: this top-level type form");
+    default: {
+        // this is a type alias assigning a name to a structural type.
+        // create a new synthetic type, and point our type as alias towards it.
+        struct Type_Ref ref = lower_intern_type_ref(ctx, tree_type);
+        type->kind = TYPE_ALIAS;
+        type->value.alias.target_id = ref.type_id;
+        array_push(&type->depends_on, &ref.type_id);
         break;
     }
+    }
 }
 
 // lowering pass 1, sub-pass a
-// collection of every single declaration of a type of function,
+// collection of every single declaration of a type or function,
 // alongside with initial registration of any referenced dependencies.
 void
 lower_pass_1_register_shells(struct Unit* unit, struct Tree* tree)
@@ -366,7 +618,7 @@ lower_pass_1_register_shells(struct Unit* unit, struct Tree* tree)
 // now that sub-pass a has registered all top-level definitions, we can
 // finally build out the type reference dag within the translation unit.
 void
-lower_pass_1_fill_bodies(struct Unit* unit, struct Tree* tree)
+lower_pass_1_fill_bodies(struct Lower_Context* ctx, struct Tree* tree)
 {
     FOR_EACH (struct Tree_Statement*, stmt, tree->top_level_statements) {
         struct String name;
@@ -375,9 +627,10 @@ lower_pass_1_fill_bodies(struct Unit* unit, struct Tree* tree)
         if (lower_match_function_decl(stmt, &name, &fn_expr)) {
             Function_Id id;
             // TODO: actually go into the body, only the signature for now.
-            if (lower_function_lookup_by_name(unit, name, &id)) {
-                struct Function* fn = *array_at(struct Function*, &unit->functions.entries, id);
-                if (!fn->ast_body) lower_fill_function_signature(unit, fn, fn_expr);
+            if (lower_function_lookup_by_name(ctx->unit, name, &id)) {
+                struct Function* fn =
+                    *array_at(struct Function*, &ctx->unit->functions.entries, id);
+                if (!fn->ast_body) lower_fill_function_signature(ctx, fn, fn_expr);
             }
             continue;
         }
@@ -385,19 +638,19 @@ lower_pass_1_fill_bodies(struct Unit* unit, struct Tree* tree)
         struct Tree_Type* tree_type;
         if (lower_match_type_decl(stmt, &name, &tree_type)) {
             Type_Id id;
-            if (lower_type_lookup_by_name(unit, name, &id)) {
-                struct Type* type = *array_at(struct Type*, &unit->types.entries, id);
-                if (type->kind == TYPE_NONE) lower_fill_type_body(unit, type, tree_type);
+            if (lower_type_lookup_by_name(ctx->unit, name, &id)) {
+                struct Type* type = *array_at(struct Type*, &ctx->unit->types.entries, id);
+                if (type->kind == TYPE_NONE) lower_fill_type_body(ctx, type, tree_type);
             }
             continue;
         }
 
         if (stmt->kind == TREE_STATEMENT_PRAGMA) {
-            lower_emit_error_c(unit, stmt->span, "unimplemented: top-level pragmas");
+            lower_emit_error_c(ctx->unit, stmt->span, "unimplemented: top-level pragmas");
             continue;
         }
 
-        lower_emit_error_c(unit, stmt->span, "unsupported top-level statement");
+        lower_emit_error_c(ctx->unit, stmt->span, "unsupported top-level statement");
     }
 }
 
@@ -405,10 +658,10 @@ lower_pass_1_fill_bodies(struct Unit* unit, struct Tree* tree)
 // collects all top-level definitions into the translation unit's
 // tables and fully maps out the references between them.
 void
-lower_pass_1(struct Unit* unit, struct Tree* tree)
+lower_pass_1(struct Lower_Context* ctx, struct Tree* tree)
 {
-    lower_pass_1_register_shells(unit, tree);
-    lower_pass_1_fill_bodies(unit, tree);
+    lower_pass_1_register_shells(ctx->unit, tree);
+    lower_pass_1_fill_bodies(ctx, tree);
 }
 
 // return line number for the given byte position in the source. (1-based)
@@ -592,6 +845,12 @@ lower_tree(struct Tree* tree, struct Source_File source, struct Unit* unit)
     unit->types.primitive_ascii_id = lower_seed_primitive(unit, "ascii");
     unit->types.primitive_void_id = lower_seed_primitive(unit, "void");
 
-    if (tree) lower_pass_1(unit, tree);
+    struct Lower_Context ctx = {
+        .unit = unit,
+        .source = source,
+        .synthetic_type_counter = 0,
+    };
+
+    if (tree) lower_pass_1(&ctx, tree);
     lower_topological_sort_dependency_graph(unit, source);
 }