Perform topological ordering when compiling typedefs so users don't need

to think about ordering their definitions.

5 files changed, 105 insertions, 14 deletions

diff --git a/ast.c b/ast.c
index f00ae5c1..b4a75277 100644
--- a/ast.c
+++ b/ast.c
@@ -5,7 +5,9 @@
 #include <printf.h>
 
 #include "ast.h"
+#include "stdlib/datatypes.h"
 #include "stdlib/integers.h"
+#include "stdlib/tables.h"
 #include "stdlib/text.h"
 #include "cordhelpers.h"
 
@@ -212,4 +214,83 @@ PUREFUNC bool is_idempotent(ast_t *ast)
     }
 }
 
+void _visit_topologically(ast_t *ast, Table_t definitions, Table_t *visited, Closure_t fn)
+{
+    void (*visit)(void*, ast_t*) = (void*)fn.fn;
+    if (ast->tag == StructDef) {
+        auto def = Match(ast, StructDef);
+        if (Table$str_get(*visited, def->name))
+            return;
+
+        Table$str_set(visited, def->name, (void*)_visit_topologically);
+        for (arg_ast_t *field = def->fields; field; field = field->next) {
+            if (field->type && field->type->tag == VarTypeAST) {
+                const char *field_type_name = Match(field->type, VarTypeAST)->name;
+                ast_t *dependency = Table$str_get(definitions, field_type_name);
+                if (dependency) {
+                    _visit_topologically(dependency, definitions, visited, fn);
+                }
+            }
+                
+        }
+        visit(fn.userdata, ast);
+    } else if (ast->tag == EnumDef) {
+        auto def = Match(ast, EnumDef);
+        if (Table$str_get(*visited, def->name))
+            return;
+
+        Table$str_set(visited, def->name, (void*)_visit_topologically);
+        for (tag_ast_t *tag = def->tags; tag; tag = tag->next) {
+            for (arg_ast_t *field = tag->fields; field; field = field->next) {
+                if (field->type && field->type->tag == VarTypeAST) {
+                    const char *field_type_name = Match(field->type, VarTypeAST)->name;
+                    ast_t *dependency = Table$str_get(definitions, field_type_name);
+                    if (dependency) {
+                        _visit_topologically(dependency, definitions, visited, fn);
+                    }
+                }
+            }
+        }
+        visit(fn.userdata, ast);
+    } else if (ast->tag == LangDef) {
+        auto def = Match(ast, LangDef);
+        if (Table$str_get(*visited, def->name))
+            return;
+        visit(fn.userdata, ast);
+    } else {
+        visit(fn.userdata, ast);
+    }
+}
+
+void visit_topologically(ast_list_t *asts, Closure_t fn)
+{
+    // Visit each top-level statement in topological order, where typedefs are
+    // visited first, and each typedef's referenced types are visited before it
+    // is, when applicable.
+
+    Table_t definitions = {};
+    for (ast_list_t *stmt = asts; stmt; stmt = stmt->next) {
+        if (stmt->ast->tag == StructDef) {
+            auto def = Match(stmt->ast, StructDef);
+            Table$str_set(&definitions, def->name, stmt->ast);
+        } else if (stmt->ast->tag == EnumDef) {
+            auto def = Match(stmt->ast, EnumDef);
+            Table$str_set(&definitions, def->name, stmt->ast);
+        } else if (stmt->ast->tag == LangDef) {
+            auto def = Match(stmt->ast, LangDef);
+            Table$str_set(&definitions, def->name, stmt->ast);
+        }
+    }
+
+    Table_t visited = {};
+    for (ast_list_t *stmt = asts; stmt; stmt = stmt->next) {
+        if (stmt->ast->tag == StructDef || stmt->ast->tag == EnumDef || stmt->ast->tag == LangDef)
+            _visit_topologically(stmt->ast, definitions, &visited, fn);
+    }
+    for (ast_list_t *stmt = asts; stmt; stmt = stmt->next) {
+        if (!(stmt->ast->tag == StructDef || stmt->ast->tag == EnumDef || stmt->ast->tag == LangDef))
+            _visit_topologically(stmt->ast, definitions, &visited, fn);
+    }
+}
+
 // vim: ts=4 sw=0 et cino=L2,l1,(0,W4,m1,\:0
diff --git a/ast.h b/ast.h
index 54a96d34..8a5839cb 100644
--- a/ast.h
+++ b/ast.h
@@ -8,6 +8,7 @@
 #include <stdlib.h>
 #include <printf.h>
 
+#include "stdlib/datatypes.h"
 #include "stdlib/files.h"
 #include "stdlib/util.h"
 
@@ -315,5 +316,6 @@ CORD type_ast_to_xml(type_ast_t *ast);
 int printf_ast(FILE *stream, const struct printf_info *info, const void *const args[]);
 ast_list_t *get_ast_children(ast_t *ast);
 PUREFUNC bool is_idempotent(ast_t *ast);
+void visit_topologically(ast_list_t *ast, Closure_t fn);
 
 // vim: ts=4 sw=0 et cino=L2,l1,(0,W4,m1,\:0
diff --git a/compile.c b/compile.c
index 860c11b9..c0a5eed9 100644
--- a/compile.c
+++ b/compile.c
@@ -3912,6 +3912,16 @@ CORD compile_statement_definitions(env_t *env, ast_t *ast)
     }
 }
 
+typedef struct {
+    env_t *env;
+    CORD *header;
+} compile_typedef_info_t;
+
+static void _visit_typedef(compile_typedef_info_t *info, ast_t *ast)
+{
+    *info->header = CORD_all(*info->header, compile_statement_typedefs(info->env, ast));
+}
+
 CORD compile_header(env_t *env, ast_t *ast)
 {
     CORD header = CORD_all(
@@ -3922,14 +3932,13 @@ CORD compile_header(env_t *env, ast_t *ast)
     for (ast_list_t *stmt = Match(ast, Block)->statements; stmt; stmt = stmt->next)
         header = CORD_all(header, compile_statement_imports(env, stmt->ast));
 
-    for (ast_list_t *stmt = Match(ast, Block)->statements; stmt; stmt = stmt->next)
-        header = CORD_all(header, compile_statement_typedefs(env, stmt->ast));
+    compile_typedef_info_t info = {.env=env, .header=&header};
+    visit_topologically(Match(ast, Block)->statements, (Closure_t){.fn=(void*)_visit_typedef, &info});
 
     for (ast_list_t *stmt = Match(ast, Block)->statements; stmt; stmt = stmt->next)
         header = CORD_all(header, compile_statement_definitions(env, stmt->ast));
 
     header = CORD_all(header, "void ", env->namespace->name, "$$initialize(void);\n");
-
     return header;
 }
 
diff --git a/environment.c b/environment.c
index 8ae4611c..0c2a1d3b 100644
--- a/environment.c
+++ b/environment.c
@@ -3,11 +3,12 @@
 #include <stdlib.h>
 #include <signal.h>
 
+#include "cordhelpers.h"
+#include "environment.h"
+#include "stdlib/datatypes.h"
 #include "stdlib/tables.h"
 #include "stdlib/text.h"
 #include "stdlib/util.h"
-#include "cordhelpers.h"
-#include "environment.h"
 #include "typecheck.h"
 
 type_t *TEXT_TYPE = NULL;
@@ -421,11 +422,9 @@ env_t *load_module_env(env_t *env, ast_t *ast)
     module_env->namespace_bindings = module_env->locals;
     Table$str_set(module_env->imports, name, module_env);
 
-    for (ast_list_t *stmt = Match(ast, Block)->statements; stmt; stmt = stmt->next)
-        prebind_statement(module_env, stmt->ast);
-
-    for (ast_list_t *stmt = Match(ast, Block)->statements; stmt; stmt = stmt->next)
-        bind_statement(module_env, stmt->ast);
+    ast_list_t *statements = Match(ast, Block)->statements;
+    visit_topologically(statements, (Closure_t){.fn=(void*)prebind_statement, .userdata=module_env});
+    visit_topologically(statements, (Closure_t){.fn=(void*)bind_statement, .userdata=module_env});
 
     return module_env;
 }
diff --git a/typecheck.c b/typecheck.c
index eefd92b5..ab64bbf3 100644
--- a/typecheck.c
+++ b/typecheck.c
@@ -303,8 +303,8 @@ void bind_statement(env_t *env, ast_t *statement)
                     code_err(field_ast->type, "This is a recursive struct that would be infinitely large. Maybe you meant to use an optional '@%T?' pointer instead?", type);
                 else
                     code_err(field_ast->type, "I'm still in the process of defining the fields of %T, so I don't know how to use it as a member."
-                             "\nTry using a @%T pointer for this field or moving the definition of %T before %T in the file.",
-                             field_t, field_t, field_t, type);
+                             "\nTry using a @%T pointer for this field.",
+                             field_t, field_t);
             }
             fields = new(arg_t, .name=field_ast->name, .type=field_t, .default_val=field_ast->value, .next=fields);
         }
@@ -335,8 +335,8 @@ void bind_statement(env_t *env, ast_t *statement)
                         code_err(field_ast->type, "This is a recursive enum that would be infinitely large. Maybe you meant to use an optional '@%T?' pointer instead?", type);
                     else
                         code_err(field_ast->type, "I'm still in the process of defining the fields of %T, so I don't know how to use it as a member."
-                                 "\nTry using a @%T pointer for this field or moving the definition of %T before %T in the file.",
-                                 field_t, field_t, field_t, type);
+                                 "\nTry using a @%T pointer for this field.",
+                                 field_t, field_t);
                 }
                 fields = new(arg_t, .name=field_ast->name, .type=field_t, .default_val=field_ast->value, .next=fields);
             }