diff options
Diffstat (limited to 'boot')
| -rw-r--r-- | boot/lower.c | 295 | ||||
| -rw-r--r-- | boot/visit/ir.c | 5 |
2 files changed, 247 insertions, 53 deletions
diff --git a/boot/lower.c b/boot/lower.c index e8bf8d0..8f41c1f 100644 --- a/boot/lower.c +++ b/boot/lower.c @@ -68,6 +68,8 @@ lower_function_lookup_by_name(struct Unit* unit, struct String name, Function_Id return false; } +// registers a basic type object for a primitive, so other types +// can depend on it and reference it in the same manner as any other type. Type_Id lower_seed_primitive(struct Unit* unit, const ascii* name) { @@ -82,12 +84,14 @@ lower_seed_primitive(struct Unit* unit, const ascii* name) return id; } -// turns a tree-side type expression into an ir Type_Ref. for now this only -// resolves simple named types (primitives + user-named types already in the -// table); compound and structural shapes get deferred to later commits. +// 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. struct Type_Ref lower_intern_type_ref(struct Unit* unit, struct Tree_Type* tree_type) { + // TODO: support synthetic structural types. struct Type_Ref ref = { .type_id = unit->types.primitive_void_id, .mods = array_new(enum Type_Modifier, 4), @@ -95,31 +99,97 @@ lower_intern_type_ref(struct Unit* unit, struct Tree_Type* tree_type) if (!tree_type || tree_type->type == TREE_TYPE_NONE) return ref; - switch (tree_type->type) { + struct Tree_Type* current = tree_type; + while (current && current->type == TREE_TYPE_REFERENCE) { + enum Type_Modifier mod = TYPE_MOD_REFERENCE; + array_push(&ref.mods, &mod); + current = current->value.reference.referenced_type; + } + + if (!current || current->type == TREE_TYPE_NONE) return ref; + + switch (current->type) { case TREE_TYPE_NAME: { Type_Id id; - if (lower_type_lookup_by_name(unit, tree_type->value.name.name, &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)) { ref.type_id = id; } else { lower_emit_error( - unit, tree_type->span, + unit, current->span, string_concatenate( - ARG_ASCII, "undefined type '", ARG_STRING, tree_type->value.name.name, - ARG_ASCII, "'", ARG_END)); + ARG_ASCII, "undefined type '", ARG_STRING, current->value.name.name, ARG_ASCII, + "'", ARG_END)); } return ref; } default: - // compound types (T?, [T], (T1, T2), &T, etc.) arrive in a later commit. lower_emit_error_c( - unit, tree_type->span, "unimplemented: only simple named types are supported for now"); + unit, current->span, + "unimplemented: only named types and references are supported for now"); 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_declare_function( - struct Unit* unit, struct String name, struct Tree_Expression* fn_expr, struct Span span) +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); +} + +// is this source statement a function? +// if it is, unwrap it and return true, otherwise false. +bool +lower_match_function_decl( + struct Tree_Statement* stmt, struct String* out_name, struct Tree_Expression** out_fn_expr) +{ + if (stmt->kind != TREE_STATEMENT_EXPRESSION) return false; + struct Tree_Expression* expr = stmt->value.expression.inner; + if (!expr || expr->kind != TREE_EXPRESSION_BINARY_OPERATION) return false; + if (expr->value.binary_operator.operation != BINARY_ASSIGN) return false; + + struct Tree_Expression* lhs = expr->value.binary_operator.left_operand; + struct Tree_Expression* rhs = expr->value.binary_operator.right_operand; + if (!lhs || lhs->kind != TREE_EXPRESSION_NAME) return false; + if (!rhs || rhs->kind != TREE_EXPRESSION_FUNCTION) return false; + + *out_name = lhs->value.name.name; + *out_fn_expr = rhs; + return true; +} + +// is this source statement a type? +// if it is, unwrap it and return true, otherwise false. +bool +lower_match_type_decl( + struct Tree_Statement* stmt, struct String* out_name, struct Tree_Type** out_tree_type) +{ + if (stmt->kind != TREE_STATEMENT_EXPRESSION) return false; + struct Tree_Expression* expr = stmt->value.expression.inner; + if (!expr || expr->kind != TREE_EXPRESSION_BINARY_OPERATION) return false; + if (expr->value.binary_operator.operation != BINARY_ASSIGN) return false; + + struct Tree_Expression* lhs = expr->value.binary_operator.left_operand; + struct Tree_Expression* rhs = expr->value.binary_operator.right_operand; + if (!lhs || lhs->kind != TREE_EXPRESSION_NAME) return false; + if (!rhs || rhs->kind != TREE_EXPRESSION_TYPE) return false; + + *out_name = lhs->value.name.name; + *out_tree_type = rhs->value.type.type; + return true; +} + +// register a function shell object, only listing a name and assigning a unique identifier. +bool +lower_register_function_shell(struct Unit* unit, struct String name, struct Span span) { Function_Id existing; if (lower_function_lookup_by_name(unit, name, &existing)) { @@ -127,13 +197,47 @@ lower_declare_function( unit, span, string_concatenate( ARG_ASCII, "duplicate function '", ARG_STRING, name, ARG_ASCII, "'", ARG_END)); - return; + return false; } Function_Id id = array_length(&unit->functions.entries); struct Function* fn = function_new(id, name); + array_push(&unit->functions.entries, &fn); + + struct Function_Name_To_Id mapping = { .name = name, .id = id }; + array_push(&unit->functions.by_name, &mapping); + return true; +} + +// register a type shell object, only listing a name and assigning a unique identifier. +// used to resolve references to types which are defined out-of-order in the source. +bool +lower_register_type_shell(struct Unit* unit, struct String name, struct Span span) +{ + Type_Id existing; + if (lower_type_lookup_by_name(unit, name, &existing)) { + lower_emit_error( + unit, span, + string_concatenate( + ARG_ASCII, "duplicate type '", ARG_STRING, name, ARG_ASCII, "'", ARG_END)); + return false; + } - fn->is_main = string_equals_c_str(name, "main"); + Type_Id id = array_length(&unit->types.entries); + struct Type* type = type_new(id, TYPE_NONE, name, span); + type->depends_on = array_new(Type_Id, 16); + array_push(&unit->types.entries, &type); + + struct Type_Name_To_Id mapping = { .name = name, .id = id }; + array_push(&unit->types.by_name, &mapping); + return true; +} + +void +lower_fill_function_signature( + struct Unit* unit, 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->params = array_new(struct Param, 16); @@ -151,65 +255,140 @@ lower_declare_function( fn->main_takes_args = fn->is_main && array_length(&fn->params) > 0; fn->ast_body = &fn_expr->value.function.body; fn->body = nil; - - array_push(&unit->functions.entries, &fn); - - struct Function_Name_To_Id mapping = { .name = name, .id = id }; - array_push(&unit->functions.by_name, &mapping); } -// extract `name = fun (...) ret { ... }` from a top-level statement, -// or return false if it's not that shape. -bool -lower_match_function_decl( - struct Tree_Statement* stmt, struct String* out_name, struct Tree_Expression** out_fn_expr) +void +lower_fill_type_body(struct Unit* unit, struct Type* type, struct Tree_Type* tree_type) { - if (stmt->kind != TREE_STATEMENT_EXPRESSION) return false; - struct Tree_Expression* expr = stmt->value.expression.inner; - if (!expr || expr->kind != TREE_EXPRESSION_BINARY_OPERATION) return false; - if (expr->value.binary_operator.operation != BINARY_ASSIGN) return false; - - struct Tree_Expression* lhs = expr->value.binary_operator.left_operand; - struct Tree_Expression* rhs = expr->value.binary_operator.right_operand; - if (!lhs || lhs->kind != TREE_EXPRESSION_NAME) return false; - if (!rhs || rhs->kind != TREE_EXPRESSION_FUNCTION) return false; + 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)) { + 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, + string_concatenate( + ARG_ASCII, "undefined type '", ARG_STRING, tree_type->value.name.name, + ARG_ASCII, "'", ARG_END)); + } + break; + } + case TREE_TYPE_STRUCTURE: { + 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(unit, tree_field), + }; + array_push(&type->value.structure.fields, &f); + lower_add_dependency(type, f.type); + } + break; + } + case TREE_TYPE_VARIANT: { + type->kind = TYPE_VARIANT; + type->value.variant.cases = array_new(struct Variant_Case, 16); + uint32 next_tag = 0; + FOR_EACH (struct Tree_Type*, tree_case, tree_type->value.variant.variants) { + struct Variant_Case c = { + .name = tree_case->value_name, + .tag = next_tag++, + .has_payload = tree_case->type != TREE_TYPE_NONE, + .payload = { 0 }, + }; + if (c.has_payload) { + c.payload = lower_intern_type_ref(unit, tree_case); + lower_add_dependency(type, c.payload); + } + array_push(&type->value.variant.cases, &c); + } + break; + } + 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); + lower_add_dependency(type, type->value.function.return_type); + type->value.function.params = array_new(struct Type_Ref, 16); - *out_name = lhs->value.name.name; - *out_fn_expr = rhs; - return true; + 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); + array_push(&type->value.function.params, &ref); + lower_add_dependency(type, ref); + if (param_type->variadic) variadic = true; + } + type->value.function.variadic = variadic; + break; + } + case TREE_TYPE_CLASS: + lower_emit_error_c(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"); + break; + } } -bool -lower_match_type_decl(struct Tree_Statement* stmt) +// lowering pass 1, sub-pass a +// collection of every single declaration of a type of function, +// alongside with initial registration of any referenced dependencies. +void +lower_pass_1_register_shells(struct Unit* unit, struct Tree* tree) { - if (stmt->kind != TREE_STATEMENT_EXPRESSION) return false; - struct Tree_Expression* expr = stmt->value.expression.inner; - if (!expr || expr->kind != TREE_EXPRESSION_BINARY_OPERATION) return false; - if (expr->value.binary_operator.operation != BINARY_ASSIGN) return false; + FOR_EACH (struct Tree_Statement*, stmt, tree->top_level_statements) { + struct String name; - struct Tree_Expression* lhs = expr->value.binary_operator.left_operand; - struct Tree_Expression* rhs = expr->value.binary_operator.right_operand; - if (!lhs || lhs->kind != TREE_EXPRESSION_NAME) return false; - if (!rhs || rhs->kind != TREE_EXPRESSION_TYPE) return false; + struct Tree_Expression* fn_expr; + if (lower_match_function_decl(stmt, &name, &fn_expr)) { + lower_register_function_shell(unit, name, stmt->span); + continue; + } - return true; + struct Tree_Type* tree_type; + if (lower_match_type_decl(stmt, &name, &tree_type)) { + lower_register_type_shell(unit, name, stmt->span); + continue; + } + } } -// pass 1 walks every top-level statement and collects declarations into -// the unit's tables. function bodies stay as raw ast for pass 2 to lower. +// lowering pass 1, sub-pass b +// walking over all top-level functions and types, fully filling out +// their definitions. +// 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(struct Unit* unit, struct Tree* tree) +lower_pass_1_fill_bodies(struct Unit* unit, struct Tree* tree) { FOR_EACH (struct Tree_Statement*, stmt, tree->top_level_statements) { struct String name; + struct Tree_Expression* fn_expr; if (lower_match_function_decl(stmt, &name, &fn_expr)) { - lower_declare_function(unit, name, fn_expr, stmt->span); + 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); + } continue; } - if (lower_match_type_decl(stmt)) { - lower_emit_error_c(unit, stmt->span, "unimplemented: type declarations"); + 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); + } continue; } @@ -222,6 +401,16 @@ lower_pass_1(struct Unit* unit, struct Tree* tree) } } +// lowering pass 1 +// 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_register_shells(unit, tree); + lower_pass_1_fill_bodies(unit, tree); +} + void lower_tree(struct Tree* tree, struct Source_File source, struct Unit* unit) { diff --git a/boot/visit/ir.c b/boot/visit/ir.c index 3880b36..20296e3 100644 --- a/boot/visit/ir.c +++ b/boot/visit/ir.c @@ -560,6 +560,11 @@ printer_visit_type(struct Visit* visit, struct Type* type) PRINT("(type %lu %s", type->id, string_c_str(type->name)); if (type->synthetic) PRINT(" synthetic"); walk_type(visit, type); + if (array_length(&type->depends_on) > 0) { + PRINT(" (depends_on"); + FOR_EACH_ARRAY(Type_Id, dep, &type->depends_on, { PRINT(" %lu", dep); }) + PRINT(")"); + } PRINT(")"); } |