diff options
| -rw-r--r-- | boot/lower.c | 369 |
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); } |