Add viz for symbol tables

4 files changed, 97 insertions, 21 deletions

diff --git a/Makefile b/Makefile
index 6c898a9..6a12cc3 100644
--- a/Makefile
+++ b/Makefile
@@ -63,6 +63,9 @@ viz_par: $(BIN)
 viz_sem: $(BIN)
         $(BIN) -ps example.bdl | dot -Nfontname="Iosevka Term" -Tpng > viz.png
 
+viz_sym: $(BIN)
+        $(BIN) -pt example.bdl | dot -Nfontname="Iosevka Term" -Tpng > viz.png
+
 # Remove build directory.
 clean:
         rm -rf $(BUILD_DIR)
diff --git a/src/main.c b/src/main.c
index 56c36d7..fc991d2 100644
--- a/src/main.c
+++ b/src/main.c
@@ -17,6 +17,7 @@ typedef enum ExecMode {
     PRINT_LEX,
     PRINT_PARSE,
     PRINT_SEMANTIC,
+    PRINT_SYMTABLES,
 } ExecMode;
 
 static ExecMode mode = RUN_NORMAL;
@@ -46,12 +47,18 @@ process_source(const StringView *source, const char *file_name) {
     check_errors(file_name);
     if (mode == PRINT_PARSE) {
         viz_ast(roots);
+        return;
     }
 
     // Symbol table generation and type checking.
     ParseTree *parse_tree = semantic_analysis(roots);
     if (mode == PRINT_SEMANTIC) {
         viz_ast(parse_tree->roots);
+        return;
+    }
+    if (mode == PRINT_SYMTABLES) {
+        viz_symtables(parse_tree->scopes);
+        return;
     }
 }
 
@@ -116,7 +123,7 @@ print_usage(void) {
     printf("Usage: %s [options] <filename filename ...>\n", BIN_NAME);
     printf("\n");
     printf("\t-h \t\tShow usage.\n");
-    printf("\t-p [l | p | s]\tPrint mode for [l]exing, [p]arsing or [s]emantic analysis\n");
+    printf("\t-p [l|p|s|t]\tPrint mode for [l]exing, [p]arsing, [s]emantic analysis, symbol [t]ables\n");
     printf("\n");
 }
 
@@ -138,6 +145,8 @@ main(int argc, char *argv[]) {
                     mode = PRINT_PARSE;
                 } else if (optarg[0] == 's' && optarg[1] == '\0') {
                     mode = PRINT_SEMANTIC;
+                } else if (optarg[0] == 't' && optarg[1] == '\0') {
+                    mode = PRINT_SYMTABLES;
                 } else {
                     print_usage();
                     return EXIT_FAILURE;
diff --git a/src/semantic.c b/src/semantic.c
index 06958b9..6c9f290 100644
--- a/src/semantic.c
+++ b/src/semantic.c
@@ -1,6 +1,7 @@
 #include "hashtable.h"
 
 typedef struct Scope {
+    size_t id;
     struct Scope *parent;
     HashTable *symbols;
     HashTable *types;
@@ -8,8 +9,7 @@ typedef struct Scope {
 
 typedef struct ParseTree {
     Root *roots;
-    Scope *global_scope;
-    Scope *current_scope;
+    Scope **scopes;
 } ParseTree;
 
 typedef struct Type {
@@ -70,6 +70,7 @@ typedef struct Symbol {
     };
 } Symbol;
 
+static size_t scope_gen_id = 0;
 
 Symbol *
 alloc_symval(Node *name, SymbolType type) {
@@ -110,6 +111,7 @@ bool type_eq(void *a, void *b) {
 Scope *
 alloc_scope(Scope *parent) {
     Scope *scope = malloc(sizeof(Scope));
+    scope->id = scope_gen_id++;
     scope->parent = parent;
     scope->symbols = ht_init(sym_hash, sym_eq);
     scope->types = ht_init(type_hash, type_eq);
@@ -216,7 +218,7 @@ find_symbol(Scope *scope, Node *node) {
 }
 
 bool
-resolve_type(Scope *scope, Node *node) {
+resolve_type(ParseTree *ast, Scope *scope, Node *node) {
     if (node->expr_type != NULL) {
         return true;
     }
@@ -224,7 +226,7 @@ resolve_type(Scope *scope, Node *node) {
         case NODE_BUILTIN: {
             for (size_t i = 0; i < array_size(node->builtin.args); ++i) {
                 Node *arg = node->builtin.args[i];
-                if (!resolve_type(scope, arg)) {
+                if (!resolve_type(ast, scope, arg)) {
                     return false;
                 }
             }
@@ -311,6 +313,7 @@ resolve_type(Scope *scope, Node *node) {
         case NODE_FUN: {
             // Fill up new scope with parameters
             scope = alloc_scope(scope);
+            array_push(ast->scopes, scope);
 
             // Parameters.
             for (size_t i = 0; i < array_size(node->fun.param_names); ++i) {
@@ -328,14 +331,14 @@ resolve_type(Scope *scope, Node *node) {
             if (body->type == NODE_BLOCK) {
                 for (size_t i = 0; i < array_size(body->block.expr); ++i) {
                     Node *expr = body->block.expr[i];
-                    if (!resolve_type(scope, expr)) {
+                    if (!resolve_type(ast, scope, expr)) {
                         return false;
                     }
                 }
                 Node *last_expr = body->block.expr[array_size(body->block.expr) - 1];
                 node->expr_type = last_expr->expr_type;
             } else {
-                if (!resolve_type(scope, body)) {
+                if (!resolve_type(ast, scope, body)) {
                     return false;
                 }
             }
@@ -350,9 +353,10 @@ resolve_type(Scope *scope, Node *node) {
         } break;
         case NODE_BLOCK: {
             scope = alloc_scope(scope);
+            array_push(ast->scopes, scope);
             for (size_t i = 0; i < array_size(node->block.expr); ++i) {
                 Node *expr = node->block.expr[i];
-                if (!resolve_type(scope, expr)) {
+                if (!resolve_type(ast, scope, expr)) {
                     return false;
                 }
             }
@@ -360,16 +364,16 @@ resolve_type(Scope *scope, Node *node) {
             node->expr_type = last_expr->expr_type;
         } break;
         case NODE_IF: {
-            if (!resolve_type(scope, node->ifexpr.cond)) {
+            if (!resolve_type(ast, scope, node->ifexpr.cond)) {
                 return false;
             }
-            if (!resolve_type(scope, node->ifexpr.expr_true)) {
+            if (!resolve_type(ast, scope, node->ifexpr.expr_true)) {
                 return false;
             }
             Type *type_true = node->ifexpr.expr_true->expr_type;
             node->expr_type = type_true;
             if (node->ifexpr.expr_false != NULL) {
-                if (!resolve_type(scope, node->ifexpr.expr_false)) {
+                if (!resolve_type(ast, scope, node->ifexpr.expr_false)) {
                     return false;
                 }
             }
@@ -396,10 +400,10 @@ resolve_type(Scope *scope, Node *node) {
         } break;
         case NODE_SET: {
             node->expr_type = &default_types[TYPE_VOID];
-            if (!resolve_type(scope, node->set.symbol)) {
+            if (!resolve_type(ast, scope, node->set.symbol)) {
                 return false;
             }
-            if (!resolve_type(scope, node->set.value)) {
+            if (!resolve_type(ast, scope, node->set.value)) {
                 return false;
             }
             Node *symbol = node->set.symbol;
@@ -426,7 +430,7 @@ resolve_type(Scope *scope, Node *node) {
 
             node->expr_type = &default_types[TYPE_VOID];
             // TODO: type inference from right side when not annotated?
-            if (!resolve_type(scope, node->def.value)) {
+            if (!resolve_type(ast, scope, node->def.value)) {
                 return false;
             }
             Node *symbol = node->def.symbol;
@@ -455,7 +459,7 @@ resolve_type(Scope *scope, Node *node) {
         } break;
         case NODE_FUNCALL: {
             Symbol *val = find_symbol(scope, node->funcall.name);
-            if (!resolve_type(scope, node->funcall.name)) {
+            if (!resolve_type(ast, scope, node->funcall.name)) {
                 return false;
             }
             if (val->type != SYMBOL_FUN) {
@@ -470,7 +474,7 @@ resolve_type(Scope *scope, Node *node) {
             node->expr_type = node->funcall.name->expr_type;
             for (size_t i = 0; i < array_size(node->funcall.args); ++i) {
                 Node *arg = node->funcall.args[i];
-                if (!resolve_type(scope, arg)) {
+                if (!resolve_type(ast, scope, arg)) {
                     return false;
                 }
                 Node *expected = val->fun.param_types[i];
@@ -490,18 +494,18 @@ ParseTree *
 semantic_analysis(Root *roots) {
     ParseTree *parse_tree = malloc(sizeof(ParseTree));
     parse_tree->roots = roots;
-    parse_tree->global_scope = alloc_scope(NULL);
-    parse_tree->current_scope = parse_tree->global_scope;
+    array_init(parse_tree->scopes, 0);
+    Scope *scope = alloc_scope(NULL);
+    array_push(parse_tree->scopes, scope);
 
     // Fill global scope with default types.
-    HashTable *types = parse_tree->global_scope->types;
+    HashTable *types = scope->types;
     for (size_t i = 0; i < sizeof(default_types)/sizeof(Type); ++i) {
         Type *type = &default_types[i];
         ht_insert(types, &type->name, type);
     }
 
     // Fill up global function symbols.
-    Scope *scope = parse_tree->global_scope;
     for (size_t i = 0; i < array_size(parse_tree->roots); ++i) {
         Node *root = parse_tree->roots[i];
         if (root->type == NODE_FUN) {
@@ -518,7 +522,7 @@ semantic_analysis(Root *roots) {
     for (size_t i = 0; i < array_size(parse_tree->roots); ++i) {
         // Fill up symbol tables in proper scope and resolve type of expression
         // for all elements.
-        if (!resolve_type(scope, parse_tree->roots[i])) {
+        if (!resolve_type(parse_tree, scope, parse_tree->roots[i])) {
             return NULL;
         }
     }
diff --git a/src/viz.c b/src/viz.c
index d519d2c..c3b05f9 100644
--- a/src/viz.c
+++ b/src/viz.c
@@ -170,3 +170,63 @@ viz_ast(Root *roots) {
     printf("}\n");
 }
 
+void
+viz_symtables(Scope **scopes) {
+    printf("digraph symtables {\n");
+    printf("rankdir=RL;\n");
+    printf("ranksep=\"0.95 equally\";\n");
+    printf("nodesep=\"0.5 equally\";\n");
+    printf("overlap=scale;\n");
+    for (size_t i = 0; i < array_size(scopes); ++i) {
+        Scope *scope = scopes[i];
+        if (array_size(scope->symbols->pairs) == 0) {
+            continue;
+        }
+        printf("%zu [shape=none,label=<", scope->id);
+        printf("<table border=\"1\" cellborder=\"0\">\n");
+        printf("<tr><td>NAME</td><td>KIND</td><td>TYPE</td></tr>");
+        for (size_t j = 0; j < array_cap(scope->symbols->pairs); ++j) {
+            HashTablePair pair = scope->symbols->pairs[j];
+            if (pair.key == NULL) {
+                continue;
+            }
+            Symbol *sym = pair.value;
+            printf("<tr>");
+            printf("<td>");
+            print_node(sym->name);
+            printf("</td>");
+            switch (sym->type) {
+                case SYMBOL_VAR: {
+                    printf("<td>var</td>");
+                    printf("<td>");
+                    print_node(sym->var.type);
+                    printf("</td>");
+                } break;
+                case SYMBOL_FUN: {
+                    printf("<td>fun</td>");
+                    printf("<td>");
+                    printf("(");
+                    size_t n_params = array_size(sym->fun.param_types);
+                    for (size_t k = 0; k < n_params; ++k) {
+                        print_node(sym->fun.param_types[k]);
+                        if (k < n_params - 1) {
+                            printf(" ");
+                        }
+                    }
+                    printf(")");
+                    printf(":");
+                    print_node(sym->fun.return_type);
+                    printf("</td>");
+                } break;
+            }
+            printf("</tr>\n");
+        }
+        printf("</table>\n");
+        printf(">];\n");
+
+        if (scope->parent != NULL) {
+            printf("%zu -> %zu\n", scope->id, scope->parent->id);
+        }
+    }
+    printf("}\n");
+}