Add a basic symbol checker

1 files changed, 271 insertions, 13 deletions

diff --git a/src/main.c b/src/main.c
index 091e57f..e5f0f29 100644
--- a/src/main.c
+++ b/src/main.c
@@ -22,21 +22,248 @@ init(void) {
     log_init_default();
 }
 
+typedef enum {
+    SYM_VAR,
+    SYM_FUN,
+    SYM_PARAM,
+    SYM_BUILTIN,
+} SymbolKind;
+
+typedef struct Symbol {
+    SymbolKind kind;
+} Symbol;
+
+MAPDEF(SymbolMap, symmap, Str, Symbol, str_hash, str_eq)
+
+typedef struct Scope {
+    sz id;
+    sz depth;
+    SymbolMap *symbols;
+    struct Scope *parent;
+} Scope;
+
+typedef struct Analyzer {
+    Arena *storage;
+    Str file_name;
+    sz scope_gen;
+    Scope **scopes;
+} Analyzer;
+
+Scope *
+scope_alloc(Analyzer *a, Scope *parent) {
+    bool is_root = parent == NULL;
+    Scope *scope = arena_malloc(sizeof(Scope), a->storage);
+    scope->id = a->scope_gen++;
+    scope->parent = parent;
+    scope->depth = is_root ? 0 : parent->depth + 1;
+    array_push(a->scopes, scope, a->storage);
+    return scope;
+}
+
+SymbolMap *
+find_symbol(Scope *scope, Str symbol) {
+    while (scope != NULL) {
+        SymbolMap *val = symmap_lookup(&scope->symbols, symbol);
+        if (val != NULL) {
+            return val;
+        }
+        scope = scope->parent;
+    }
+    return NULL;
+}
+
 void
-process_file(Str path) {
-    Arena lexer_arena = arena_create(LEXER_MEM, os_allocator);
+analyzer_symbols(Analyzer *a, Node *node, Scope *scope) {
+    assert(a);
+    assert(scope);
+    if (!node) {
+        return;
+    }
+    assert(node);
+    switch (node->kind) {
+        case NODE_FUN: {
+            if (scope->depth != 0) {
+                Str symbol = node->func_name->value.str;
+                if (symmap_lookup(&scope->symbols, symbol) != NULL) {
+                    eprintln(
+                        "%s:%d:%d: error: symbol '%s' already exists in "
+                        "current "
+                        "scope",
+                        a->file_name, node->func_name->line,
+                        node->func_name->col, symbol);
+                }
+                symmap_insert(&scope->symbols, symbol,
+                              (Symbol){.kind = SYM_FUN}, a->storage);
+            }
+
+            scope = scope_alloc(a, scope);
+            for (sz i = 0; i < array_size(node->func_params); i++) {
+                Node *param = node->func_params[i];
+                symmap_insert(&scope->symbols, param->param_name->value.str,
+                              (Symbol){.kind = SYM_PARAM}, a->storage);
+            }
+            analyzer_symbols(a, node->func_body, scope);
+        } break;
+        case NODE_COND:
+        case NODE_MATCH: {
+            if (node->match_expr) {
+                analyzer_symbols(a, node->match_expr, scope);
+            }
+            for (sz i = 0; i < array_size(node->match_cases); i++) {
+                Node *expr = node->match_cases[i];
+                analyzer_symbols(a, expr, scope);
+            }
+        } break;
+        case NODE_RETURN:
+            // TODO: Struct field initializers need to be checked... when we
+            // get to that.
+            // case NODE_VAL_FIELD:
+            // case NODE_ENUM:
+            // case NODE_STRUCT:
+            // case NODE_STRUCT_LIT:
+        case NODE_BLOCK: {
+            Scope *next = scope_alloc(a, scope);
+            for (sz i = 0; i < array_size(node->elements); i++) {
+                Node *expr = node->elements[i];
+                analyzer_symbols(a, expr, next);
+            }
+        } break;
+        case NODE_CASE: {
+            analyzer_symbols(a, node->case_value, scope);
+            if (node->case_expr) {
+                Scope *next = scope_alloc(a, scope);
+                analyzer_symbols(a, node->case_expr, next);
+            }
+        } break;
+        case NODE_IF: {
+            analyzer_symbols(a, node->cond_if, scope);
+            if (node->cond_expr) {
+                Scope *next = scope_alloc(a, scope);
+                analyzer_symbols(a, node->cond_expr, next);
+            }
+            if (node->cond_else) {
+                Scope *next = scope_alloc(a, scope);
+                analyzer_symbols(a, node->cond_else, next);
+            }
+        } break;
+        case NODE_WHILE: {
+            analyzer_symbols(a, node->while_cond, scope);
+            scope = scope_alloc(a, scope);
+            analyzer_symbols(a, node->while_expr, scope);
+        } break;
+        case NODE_FUNCALL: {
+            Str symbol = node->value.str;
+            if (find_symbol(scope, symbol) == NULL) {
+                eprintln(
+                    "%s:%d:%d: error: symbol '%s' doesn't exists in current "
+                    " scope ",
+                    a->file_name, node->line, node->col, symbol);
+            }
+            Scope *next = scope_alloc(a, scope);
+            for (sz i = 0; i < array_size(node->elements); i++) {
+                Node *expr = node->elements[i];
+                analyzer_symbols(a, expr, next);
+            }
+        } break;
+        case NODE_SYMBOL_IDX:
+        case NODE_SYMBOL: {
+            Str symbol = node->value.str;
+            if (find_symbol(scope, symbol) == NULL) {
+                eprintln(
+                    "%s:%d:%d: error: symbol '%s' doesn't exists in current "
+                    " scope ",
+                    a->file_name, node->line, node->col, symbol);
+            }
+            // TODO: Resolve symbol chains.
+        } break;
+        case NODE_SET: {
+            analyzer_symbols(a, node->var_name, scope);
+            analyzer_symbols(a, node->var_val, scope);
+        } break;
+        case NODE_LET: {
+            // Check the value first to avoid recursive symbol usage.
+            analyzer_symbols(a, node->var_val, scope);
+
+            Str symbol = node->var_name->value.str;
+            if (symmap_lookup(&scope->symbols, symbol) != NULL) {
+                eprintln(
+                    "%s:%d:%d: error: symbol '%s' already exists in current "
+                    " scope ",
+                    a->file_name, node->var_name->line, node->var_name->col,
+                    symbol);
+            }
+            symmap_insert(&scope->symbols, symbol, (Symbol){.kind = SYM_VAR},
+                          a->storage);
+        } break;
+        // Binary ops
+        case NODE_ADD:
+        case NODE_SUB:
+        case NODE_DIV:
+        case NODE_MUL:
+        case NODE_MOD:
+        case NODE_NOT:
+        case NODE_AND:
+        case NODE_OR:
+        case NODE_EQ:
+        case NODE_NEQ:
+        case NODE_LT:
+        case NODE_GT:
+        case NODE_LE:
+        case NODE_GE:
+        case NODE_BITNOT:
+        case NODE_BITAND:
+        case NODE_BITOR:
+        case NODE_BITLSHIFT:
+        case NODE_BITRSHIFT: {
+            analyzer_symbols(a, node->left, scope);
+            analyzer_symbols(a, node->right, scope);
+        } break;
+        default: break;
+    }
+}
+
+void
+symbolic_analysis(Analyzer *a, Parser *parser) {
+    Scope *scope = scope_alloc(a, NULL);
+
+    // Fill builtin functions.
+    Str builtin_functions[] = {
+        cstr("print"),
+        cstr("println"),
+    };
+    for (sz i = 0; i < LEN(builtin_functions); i++) {
+        Str symbol = builtin_functions[i];
+        symmap_insert(&scope->symbols, symbol, (Symbol){.kind = SYM_BUILTIN},
+                      a->storage);
+    }
+
+    // Find top level function declarations.
+    for (sz i = 0; i < array_size(parser->nodes); i++) {
+        Node *root = parser->nodes[i];
+        if (root->kind == NODE_FUN) {
+            Str symbol = root->func_name->value.str;
+            if (symmap_lookup(&scope->symbols, symbol) != NULL) {
+                eprintln(
+                    "%s:%d:%d: error: symbol '%s' already exists in current "
+                    "scope",
+                    a->file_name, root->func_name->line, root->func_name->col,
+                    symbol);
+            }
+            symmap_insert(&scope->symbols, symbol, (Symbol){.kind = SYM_FUN},
+                          a->storage);
+        }
+    }
 
-    StrIntMap *map = NULL;
-    strintmap_insert(&map, cstr("test"), 1, &lexer_arena);
-    strintmap_insert(&map, cstr("toast"), 9, &lexer_arena);
-    strintmap_insert(&map, cstr("waaaa"), 420, &lexer_arena);
-    strintmap_insert(&map, cstr("test"), 69, &lexer_arena);
-    StrIntMapIter iter = strintmap_iterator(map, &lexer_arena);
-    StrIntMap *val = strintmap_next(&iter, &lexer_arena);
-    while (val) {
-        println("KEY: %s value: %d", val->key, val->val);
-        val = strintmap_next(&iter, &lexer_arena);
+    // Recursively fill symbol tables.
+    for (sz i = 0; i < array_size(parser->nodes); i++) {
+        Node *root = parser->nodes[i];
+        analyzer_symbols(a, root, scope);
     }
+}
+
+void
+process_file(Str path) {
+    Arena lexer_arena = arena_create(LEXER_MEM, os_allocator);
 
     FileContents file = platform_read_file(path, &lexer_arena);
     if (file.err) {
@@ -94,7 +321,34 @@ process_file(Str path) {
         graph_ast(parser.nodes);
         goto stop;
     }
-    // TODO: Semantic analysis.
+
+    // Semantic analysis.
+    Analyzer analyzer = (Analyzer){
+        .storage = &lexer_arena,
+        .file_name = path,
+    };
+    symbolic_analysis(&analyzer, &parser);
+
+    // DEBUG: Printing all symbols on the HT.
+    // StrSetIter iter = strset_iterator(root_scope.symbols, &lexer_arena);
+    // StrSet *val = strset_next(&iter, &lexer_arena);
+    // while (val) {
+    //     println("SYMBOL: %s", val->key);
+    //     val = strset_next(&iter, &lexer_arena);
+    // }
+
+    // StrIntMap *map = NULL;
+    // strintmap_insert(&map, cstr("test"), 1, &lexer_arena);
+    // strintmap_insert(&map, cstr("toast"), 9, &lexer_arena);
+    // strintmap_insert(&map, cstr("waaaa"), 420, &lexer_arena);
+    // strintmap_insert(&map, cstr("test"), 69, &lexer_arena);
+    // StrIntMapIter iter = strintmap_iterator(map, &lexer_arena);
+    // StrIntMap *val = strintmap_next(&iter, &lexer_arena);
+    // while (val) {
+    //     println("KEY: %s value: %d", val->key, val->val);
+    //     val = strintmap_next(&iter, &lexer_arena);
+    // }
+
     // TODO: Type checking.
 
     // Compile roots.
@@ -136,6 +390,10 @@ process_file(Str path) {
     //         &(Array){.mem = (u8 *)&vm.regs, sizeof(vm.regs)});
     // disassemble_chunk(chunk);
 
+#if DEBUG == 1
+    println("Space used: %{Arena}", &lexer_arena);
+#endif
+
     // arena_destroy(&bytecode_arena, os_allocator);
 stop:
     // Free up resources.