Add initial implementation of symbol checking

6 files changed, 221 insertions, 21 deletions

diff --git a/src/errors.c b/src/errors.c
index b93b462..2781bf5 100644
--- a/src/errors.c
+++ b/src/errors.c
@@ -15,6 +15,8 @@ static const char* error_msgs[] = {
     [ERR_NOT_A_BOOL]       = "error: expected a bool",
     [ERR_NOT_A_LPAREN]     = "error: expected opening parentheses (lparen)",
     [ERR_NOT_A_RPAREN]     = "error: expected closing parentheses (rparen)",
+    [ERR_SYMBOL_REDEF]     = "error: symbol redefinition",
+    [ERR_UNKNOWN_SYMBOL]   = "error: unknown symbol",
 };
 
 static Error current_error = {.value = ERR_OK};
diff --git a/src/errors.h b/src/errors.h
index 871711b..eb83e52 100644
--- a/src/errors.h
+++ b/src/errors.h
@@ -23,6 +23,8 @@ typedef enum ErrorValue {
     ERR_NOT_A_BOOL,
     ERR_NOT_A_LPAREN,
     ERR_NOT_A_RPAREN,
+    ERR_SYMBOL_REDEF,
+    ERR_UNKNOWN_SYMBOL,
     ERR_OK,
 } ErrorValue;
 
diff --git a/src/nodes.c b/src/nodes.c
index af3b772..a420189 100644
--- a/src/nodes.c
+++ b/src/nodes.c
@@ -6,6 +6,8 @@ alloc_node(NodeType type) {
     // TODO: Free memory!
     Node *node = malloc(sizeof(Node));
     node->type = type;
+    node->line = 0;
+    node->col = 0;
     return node;
 }
 
diff --git a/src/nodes.h b/src/nodes.h
index 4fb48a1..cf0e749 100644
--- a/src/nodes.h
+++ b/src/nodes.h
@@ -17,6 +17,8 @@ typedef enum NodeType {
 
 typedef struct Node {
     NodeType type;
+    size_t line;
+    size_t col;
 
     union {
         // Numbers.
@@ -26,7 +28,7 @@ typedef struct Node {
             size_t fractional;
         } number;
 
-        // String/symbol.
+        // String/symbol/type.
         StringView string;
 
         // Boolean.
diff --git a/src/parser.c b/src/parser.c
index ba063f1..7cd22ae 100644
--- a/src/parser.c
+++ b/src/parser.c
@@ -111,6 +111,8 @@ parse_number(Parser *parser) {
     node->number.negative = negative;
     node->number.integral = integral;
     node->number.fractional = fractional;
+    node->line = tok.line;
+    node->col = tok.col;
     return node;
 }
 
@@ -123,6 +125,8 @@ parse_string(Parser *parser) {
     }
     Node *node = alloc_node(NODE_STRING);
     node->string = tok.value;
+    node->line = tok.line;
+    node->col = tok.col;
     return node;
 }
 
@@ -135,6 +139,8 @@ parse_symbol(Parser *parser) {
     }
     Node *node = alloc_node(NODE_SYMBOL);
     node->string = tok.value;
+    node->line = tok.line;
+    node->col = tok.col;
     return node;
 }
 
@@ -145,12 +151,14 @@ parse_type(Parser *parser) {
         push_error(ERR_TYPE_PARSER, ERR_NOT_A_TYPE, tok.line, tok.col);
         return NULL;
     }
+    Node *node = alloc_node(NODE_TYPE);
+    node->line = tok.line;
+    node->col = tok.col;
     tok = next_token(parser);
     if (tok.type != TOKEN_SYMBOL) {
         push_error(ERR_TYPE_PARSER, ERR_NOT_A_TYPE, tok.line, tok.col);
         return NULL;
     }
-    Node *node = alloc_node(NODE_TYPE);
     node->string = tok.value;
     return node;
 }
@@ -164,14 +172,18 @@ parse_bool(Parser *parser) {
     }
     Node *node = alloc_node(NODE_BOOL);
     node->boolean = tok.type == TOKEN_TRUE;
+    node->line = tok.line;
+    node->col = tok.col;
     return node;
 }
 
 Node *
 parse_builtin(Parser *parser) {
-    Token op = next_token(parser);
+    Token tok = next_token(parser);
     Node *node = alloc_node(NODE_BUILTIN);
-    node->builtin.type = op.type;
+    node->builtin.type = tok.type;
+    node->line = tok.line;
+    node->col = tok.col;
     array_init(node->builtin.args, 0);
     while (has_next(parser)) {
         Token next = peek_token(parser);
@@ -185,13 +197,13 @@ parse_builtin(Parser *parser) {
         }
         array_push(node->builtin.args, arg);
     }
-    push_error(ERR_TYPE_PARSER, ERR_UNMATCHED_PAREN, op.line, op.col);
+    push_error(ERR_TYPE_PARSER, ERR_UNMATCHED_PAREN, tok.line, tok.col);
     return NULL;
 }
 
 Node *
 parse_def(Parser *parser) {
-    next_token(parser); // Skip keyword.
+    Token tok = next_token(parser);
 
     Node *symbol = parse_symbol(parser);
     if (symbol == NULL) {
@@ -218,12 +230,14 @@ parse_def(Parser *parser) {
     node->def.symbol = symbol;
     node->def.value = value;
     node->def.type = type;
+    node->line = tok.line;
+    node->col = tok.col;
     return node;
 }
 
 Node *
 parse_set(Parser *parser) {
-    next_token(parser); // Skip keyword.
+    Token tok = next_token(parser);
 
     Node *symbol = parse_symbol(parser);
     if (symbol == NULL) {
@@ -242,12 +256,14 @@ parse_set(Parser *parser) {
     Node *node = alloc_node(NODE_SET);
     node->set.symbol = symbol;
     node->set.value = value;
+    node->line = tok.line;
+    node->col = tok.col;
     return node;
 }
 
 Node *
 parse_fun(Parser *parser) {
-    next_token(parser); // Skip keyword.
+    Token tok = next_token(parser);
 
     Node *name = parse_symbol(parser);
     if (name == NULL) {
@@ -258,6 +274,8 @@ parse_fun(Parser *parser) {
     node->fun.name = name;
     array_init(node->fun.param_names, 0);
     array_init(node->fun.param_types, 0);
+    node->line = tok.line;
+    node->col = tok.col;
 
     // Parse parameter list and return type.
     if (!consume_lparen(parser)) {
@@ -300,12 +318,14 @@ parse_fun(Parser *parser) {
 
 Node *
 parse_if(Parser *parser) {
-    next_token(parser); // Skip keyword.
+    Token tok = next_token(parser);
 
     Node *node = alloc_node(NODE_IF);
     node->ifexpr.cond = NULL;
     node->ifexpr.expr_true = NULL;
     node->ifexpr.expr_false = NULL;
+    node->line = tok.line;
+    node->col = tok.col;
 
     Node *cond = parse_next(parser);
     if (cond == NULL) {
@@ -317,7 +337,7 @@ parse_if(Parser *parser) {
     }
     node->ifexpr.cond = cond;
     node->ifexpr.expr_true = expr_true;
-    Token tok = peek_token(parser);
+    tok = peek_token(parser);
 
     // Optional else statement.
     if (tok.type != TOKEN_RPAREN) {
@@ -370,10 +390,12 @@ parse_paren(Parser *parser) {
 
 Node *
 parse_block(Parser *parser) {
-    next_token(parser); // Skip paren.
+    Token tok = next_token(parser);
 
     Node *node = alloc_node(NODE_BLOCK);
     array_init(node->block.expr, 0);
+    node->line = tok.line;
+    node->col = tok.col;
     while (true) {
         Token next = peek_token(parser);
         if (next.type == TOKEN_RCURLY) {
@@ -408,13 +430,178 @@ parse_next(Parser *parser) {
     }
 }
 
+uint64_t sym_hash(const struct HashTable *table, void *bytes) {
+    // TODO: implement
+    return 0;
+}
+
+bool sym_eq(void *a, void *b) {
+    Node *a_node = a;
+    Node *b_node = b;
+    assert(a_node->type == NODE_SYMBOL);
+    assert(b_node->type == NODE_SYMBOL);
+    return sv_equal(&a_node->string, &b_node->string);
+}
+
+Scope *
+alloc_scope(Scope *parent) {
+    Scope *scope = malloc(sizeof(Scope));
+    scope->parent = parent;
+    scope->symbols = ht_init(sym_hash, sym_eq);
+    return scope;
+}
+
 ParseTree *
 alloc_parsetree(void) {
     ParseTree *parse_tree = malloc(sizeof(ParseTree));
     array_init(parse_tree->roots, 0);
+    parse_tree->global_scope = alloc_scope(NULL);
+    parse_tree->current_scope = parse_tree->global_scope;
+    // TODO: Fill global scope with default types/symbols.
     return parse_tree;
 }
 
+bool
+insert_symbol(Parser *parser, Node *symbol) {
+    HashTable *symbols = parser->parse_tree->current_scope->symbols;
+    if (ht_lookup(symbols, symbol) != NULL) {
+        push_error(ERR_TYPE_PARSER, ERR_SYMBOL_REDEF, symbol->line, symbol->col);
+        return false;
+    }
+    ht_insert(symbols, symbol, symbol);
+    return true;
+}
+
+bool
+parse_roots(Parser *parser) {
+    while (has_next(parser)) {
+        Node *node = parse_next(parser);
+        if (node == NULL) {
+            return false;
+        }
+        array_push(parser->parse_tree->roots, node);
+    }
+    return true;
+}
+
+bool
+find_symbol(Parser *parser, Node *node) {
+    Scope *scope = parser->parse_tree->current_scope;
+    while (scope != NULL) {
+        if (ht_lookup(scope->symbols, node) != NULL) {
+            return true;
+        }
+        scope = scope->parent;
+    }
+    push_error(ERR_TYPE_PARSER, ERR_UNKNOWN_SYMBOL, node->line, node->col);
+    return false;
+}
+
+bool
+symbol_check(Parser *parser, Node *node) {
+    switch (node->type) {
+        case NODE_BUILTIN: {
+            for (size_t i = 0; i < array_size(node->builtin.args); ++i) {
+                Node *arg = node->builtin.args[i];
+                symbol_check(parser, arg);
+            }
+        } break;
+        case NODE_SYMBOL: {
+            if (!find_symbol(parser, node)) {
+                return false;
+            }
+        } break;
+        case NODE_SET: {
+            Node *symbol = node->set.symbol;
+            if (!find_symbol(parser, symbol)) {
+                return false;
+            }
+            if (!symbol_check(parser, node->set.value)) {
+                return false;
+            }
+        } break;
+        case NODE_FUN: {
+            // TODO: Store scope in Node block?
+            Scope *prev_scope = parser->parse_tree->current_scope;
+            parser->parse_tree->current_scope = alloc_scope(prev_scope);
+
+            // Parameters.
+            for (size_t i = 0; i < array_size(node->fun.param_names); ++i) {
+                Node *param = node->fun.param_names[i];
+                if (!insert_symbol(parser, param)) {
+                    return false;
+                }
+            }
+
+            // Body.
+            Node *body = node->fun.body;
+            if (body->type == NODE_BLOCK) {
+                for (size_t i = 0; i < array_size(body->block.expr); ++i) {
+                    Node *expr = body->block.expr[i];
+                    symbol_check(parser, expr);
+                }
+            } else {
+                symbol_check(parser, body);
+            }
+            parser->parse_tree->current_scope = prev_scope;
+        } break;
+        case NODE_BLOCK: {
+            // TODO: Store scope in Node block?
+            Scope *prev_scope = parser->parse_tree->current_scope;
+            parser->parse_tree->current_scope = alloc_scope(prev_scope);
+            for (size_t i = 0; i < array_size(node->block.expr); ++i) {
+                Node *expr = node->block.expr[i];
+                symbol_check(parser, expr);
+            }
+            parser->parse_tree->current_scope = prev_scope;
+        } break;
+        case NODE_IF: {
+            if (!symbol_check(parser, node->ifexpr.cond)) {
+                return false;
+            }
+            if (!symbol_check(parser, node->ifexpr.expr_true)) {
+                return false;
+            }
+            if (node->ifexpr.expr_false != NULL) {
+                if (!symbol_check(parser, node->ifexpr.expr_false)) {
+                    return false;
+                }
+            }
+        } break;
+        case NODE_DEF: {
+            if (!symbol_check(parser, node->def.value)) {
+                return false;
+            }
+            if (!insert_symbol(parser, node->def.symbol)) {
+                return false;
+            }
+        } break;
+        default: break;
+    }
+    return true;
+}
+
+bool
+semantic_analysis(Parser *parser) {
+    // Fill up global function symbols.
+    for (size_t i = 0; i < array_size(parser->parse_tree->roots); ++i) {
+        Node *root = parser->parse_tree->roots[i];
+        if (root->type == NODE_FUN) {
+            Node *name = root->fun.name;
+            if (!insert_symbol(parser, name)) {
+                return false;
+            }
+        }
+    }
+
+    // Fill up symbol tables in proper scope and check existance.
+    for (size_t i = 0; i < array_size(parser->parse_tree->roots); ++i) {
+        symbol_check(parser, parser->parse_tree->roots[i]);
+    }
+
+    return true;
+}
+
 ParseTree *
 parse(Token *tokens) {
     Parser parser = {
@@ -428,16 +615,12 @@ parse(Token *tokens) {
     print_tokens(parser.tokens);
     printf("------------\n");
 
-    while (has_next(&parser)) {
-        Node *node = parse_next(&parser);
-        if (node == NULL) {
-            return NULL;
-        }
-        // DEBUG:...
-        print_node(node);
-        printf("\n");
-
-        array_push(parser.parse_tree->roots, node);
+    if (!parse_roots(&parser)) {
+        return NULL;
+    }
+    if (!semantic_analysis(&parser)) {
+        return NULL;
     }
+
     return parser.parse_tree;
 }
diff --git a/src/parser.h b/src/parser.h
index 4d871ad..3c2dc2b 100644
--- a/src/parser.h
+++ b/src/parser.h
@@ -3,9 +3,18 @@
 
 #include "lexer.h"
 #include "nodes.h"
+#include "hashtable.h"
+
+typedef struct Scope {
+    struct Scope *parent;
+    HashTable *symbols;
+    // HashTable types;
+} Scope;
 
 typedef struct ParseTree {
     Node **roots;
+    Scope *global_scope;
+    Scope *current_scope;
 } ParseTree;
 
 typedef struct Parser {