Lowering pass lexical scope tracking

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

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);