diff options
| -rw-r--r-- | boot/lower.c | 197 |
1 files changed, 193 insertions, 4 deletions
diff --git a/boot/lower.c b/boot/lower.c index 03cdef5..4a831d9 100644 --- a/boot/lower.c +++ b/boot/lower.c @@ -26,6 +26,48 @@ #include "catboot.h" +// a single local variable visible in the current scope. +struct Local_Variable +{ + struct String name; + struct Type_Ref type; // TODO: type-check & fill out empty +}; + +// what kind of scope is this? +// declared on every lexical scope so we can make sure that the scopes are balanced. +enum Scope_Type +{ + SCOPE_TYPE_NONE, + + // the persistent top-level scope. never removed! + SCOPE_TYPE_UNIT, + + // pushed for each function body, holds parameters. + SCOPE_TYPE_FUNCTION, + + // any kind of nested block, can hold anything. + SCOPE_TYPE_BLOCK, +}; + +// a single lexical scope, pushed onto the context's stack when entering +// a block and popped when leaving it. +// the scope controls the visibility of every single language +// object (functions, types and variables). +// all objects are present in the unit's global object tables, however +// just because an object is registered does not mean that the current code +// block is allowed to use it. the scope decides the actual visibility of +// the objects, every top-level declaration is listed in the bottom-most +// scope, while other scopes contain local variables, types and functions. +// NOTE: though all top-most declarations are order-independent, the local +// objects have to be declared in the correct order, just like any other +// statements. +struct Scope +{ + enum Scope_Type type; + Array(struct Local_Variable) variables; + // TODO: add local closure functions & local types. +}; + struct Lower_Context { // the translation unit being created @@ -38,7 +80,9 @@ struct Lower_Context // monotonic counter of synthesized types uint synthetic_type_counter; - // TODO: add function & block scope data + // stack of lexical scopes. + // all top-level declarations are stored are stored in the first unit scope. + Array(struct Scope) scope_stack; }; void @@ -817,18 +861,141 @@ lower_expression(struct Lower_Context* ctx, struct Tree_Expression* tree_expr) } } +// push a fresh lexical scope onto the lowering stack. +// do not forget to also pop this scope once we leave it! +void +lower_push_scope(struct Lower_Context* ctx, enum Scope_Type type) +{ + struct Scope s = { + .type = type, + .variables = array_new(struct Local_Variable, 16), + }; + array_push(&ctx->scope_stack, &s); +} + +// pop the latest (inner-most) scope off the stack. +// the expected type must match the popped scope! +void +lower_pop_scope(struct Lower_Context* ctx, enum Scope_Type expected) +{ + check(ctx->scope_stack.length > 1, "lowering pass tried popping top-level unit scope"); + + struct Scope* top = array_at(struct Scope, &ctx->scope_stack, ctx->scope_stack.length - 1); + + check(top->type == expected, "scope type mismatch on pop: expected %d, got %d", (int)expected, (int)top->type); + check(expected != SCOPE_TYPE_UNIT, "lowering pass tried popping top-level unit scope"); + + --ctx->scope_stack.length; +} + +// declare a local variable in the current (inner-most) scope. +void +lower_declare_local(struct Lower_Context* ctx, struct String name, struct Type_Ref type) +{ + check(ctx->scope_stack.length > 0, "no active scope"); + + struct Local_Variable v = { .name = name, .type = type }; + + struct Scope* top = array_at(struct Scope, &ctx->scope_stack, ctx->scope_stack.length - 1); + array_push(&top->variables, &v); +} + +// check whether `name` is already known within any active scope. +// all shadowing is disallowed in catskill/catboot. +bool +lower_is_shadowing(struct Lower_Context* ctx, struct String name) +{ + for (uint i = ctx->scope_stack.length; i > 0; --i) { + struct Scope* scope = array_at(struct Scope, &ctx->scope_stack, i - 1); + + FOR_EACH_ARRAY (struct Local_Variable, var, &scope->variables) { + if (string_equals(var->name, name)) return true; + } + } + + return false; +} + // turns a source statement into the lowered form. struct Statement* lower_statement(struct Lower_Context* ctx, struct Tree_Statement* tree_stmt) { - // TODO: implement all the statements switch (tree_stmt->kind) { case TREE_STATEMENT_RETURN: { union Statement_Value v = { 0 }; if (tree_stmt->value.return_value.value) v.return_value.value = lower_expression(ctx, tree_stmt->value.return_value.value); + return statement_new(STATEMENT_RETURN, v, tree_stmt->span); } + case TREE_STATEMENT_DECLARATION: { + struct Tree_Bare_Declaration* decl = &tree_stmt->value.declaration.inner; + + // multi-name decls (`var a, b int = …`) need either splitting into N + // sibling declarations (no side effect on the initializer) or a + // temporary; both are deferred for now. + if (array_length(&decl->names) != 1) { + lower_emit_error_c( + ctx->unit, tree_stmt->span, "unimplemented: multi-name declarations"); + return nil; + } + + struct String name = *array_at(struct String, &decl->names, 0); + if (lower_is_shadowing(ctx, name)) { + lower_emit_error( + ctx->unit, tree_stmt->span, + string_concatenate( + ARG_ASCII, "name '", ARG_STRING, name, ARG_ASCII, + "' shadows an existing binding", ARG_END)); + return nil; + } + struct Type_Ref type = lower_intern_type_ref(ctx, decl->type); + lower_declare_local(ctx, name, type); + + union Statement_Value v = { 0 }; + v.declaration.name = name; + v.declaration.type = type; + if (decl->initializer) + v.declaration.initializer = lower_expression(ctx, decl->initializer); + + return statement_new(STATEMENT_DECLARATION, v, tree_stmt->span); + } + case TREE_STATEMENT_EXPRESSION: { + struct Tree_Expression* inner = tree_stmt->value.expression.inner; + + // TODO: compound assignments! + if (inner && inner->kind == TREE_EXPRESSION_BINARY_OPERATION) { + enum Binary_Operation op = inner->value.binary_operator.operation; + if (op == BINARY_ASSIGN) { + union Statement_Value v = { 0 }; + v.assign.lhs = lower_expression(ctx, inner->value.binary_operator.left_operand); + v.assign.rhs = lower_expression(ctx, inner->value.binary_operator.right_operand); + return statement_new(STATEMENT_ASSIGN, v, tree_stmt->span); + } + if (op > BINARY_ASSIGN) { + lower_emit_error_c( + ctx->unit, tree_stmt->span, "unimplemented: compound assignment"); + return nil; + } + } + if (inner && inner->kind == TREE_EXPRESSION_INCREMENT_DECREMENT) { + lower_emit_error_c( + ctx->unit, tree_stmt->span, + "unimplemented: increment/decrement at statement position"); + return nil; + } + + union Statement_Value v = { 0 }; + v.expression.inner = lower_expression(ctx, inner); + + return statement_new(STATEMENT_EXPRESSION, v, tree_stmt->span); + } + case TREE_STATEMENT_BLOCK: { + union Statement_Value v = { 0 }; + v.block.inner = lower_block(ctx, &tree_stmt->value.block.inner); + + return statement_new(STATEMENT_BLOCK, v, tree_stmt->span); + } default: lower_emit_error_c(ctx->unit, tree_stmt->span, "unimplemented: this statement kind"); return nil; @@ -836,16 +1003,20 @@ lower_statement(struct Lower_Context* ctx, struct Tree_Statement* tree_stmt) } // turns a source block of statements into the lowered form of a block. +// pushes a fresh lexical scope for the duration of the block. struct Block* lower_block(struct Lower_Context* ctx, struct Tree_Block* tree_block) { + lower_push_scope(ctx, SCOPE_TYPE_BLOCK); + struct Block* block = block_new(); block->statements = array_new(struct Statement*, 16); - FOR_EACH (struct Tree_Statement*, tree_stmt, tree_block->statements) { struct Statement* stmt = lower_statement(ctx, tree_stmt); if (stmt) array_push(&block->statements, &stmt); } + + lower_pop_scope(ctx, SCOPE_TYPE_BLOCK); return block; } @@ -855,7 +1026,20 @@ void lower_pass_2(struct Lower_Context* ctx) { FOR_EACH_ARRAY (struct Function*, fn, &ctx->unit->functions.entries) { - if ((*fn)->ast_body) (*fn)->body = lower_block(ctx, (*fn)->ast_body); + if (!(*fn)->ast_body) continue; + + // push a function-level scope on top of the persistent top-level + // scope, holding the parameter names. + // the function body will also push a new block scope, + // separating the parameters and the local declarations. + lower_push_scope(ctx, SCOPE_TYPE_FUNCTION); + FOR_EACH_ARRAY (struct Param, param, &(*fn)->params) { + lower_declare_local(ctx, param->name, param->type); + } + + (*fn)->body = lower_block(ctx, (*fn)->ast_body); + + lower_pop_scope(ctx, SCOPE_TYPE_FUNCTION); } } @@ -1044,8 +1228,13 @@ lower_tree(struct Tree* tree, struct Source_File source, struct Unit* unit) .unit = unit, .source = source, .synthetic_type_counter = 0, + .scope_stack = array_new(struct Scope, 32), }; + // push the persistent top-level scope, where all top-level + // language object declarations of a translation unit live. + lower_push_scope(&ctx, SCOPE_TYPE_UNIT); + if (tree) { lower_pass_1(&ctx, tree); lower_pass_2(&ctx); |