Support circular imports

4 files changed, 72 insertions, 103 deletions

diff --git a/src/main/java/org/zwobble/hobgoblin/compiler/HobgoblinCompiler.java b/src/main/java/org/zwobble/hobgoblin/compiler/HobgoblinCompiler.java
index e4622a0..6f4c65d 100644
--- a/src/main/java/org/zwobble/hobgoblin/compiler/HobgoblinCompiler.java
+++ b/src/main/java/org/zwobble/hobgoblin/compiler/HobgoblinCompiler.java
@@ -1,13 +1,11 @@
 package org.zwobble.hobgoblin.compiler;
 
-import org.zwobble.hobgoblin.compiler.ast.typed.TypedNamespaceNode;
 import org.zwobble.hobgoblin.compiler.ast.untyped.UntypedNamespaceNode;
 import org.zwobble.hobgoblin.compiler.builtins.NativeTypes;
 import org.zwobble.hobgoblin.compiler.config.ProjectConfig;
 import org.zwobble.hobgoblin.compiler.parser.Parser;
 import org.zwobble.hobgoblin.compiler.typechecker.TypeChecker;
 import org.zwobble.hobgoblin.compiler.typechecker.TypeCheckerGlobalContext;
-import org.zwobble.hobgoblin.compiler.typechecker.errors.UnknownNamespaceError;
 import org.zwobble.hobgoblin.compiler.types.NamespaceName;
 import org.zwobble.sourcetext.SourceText;
 
@@ -18,10 +16,8 @@ import java.nio.file.Files;
 import java.nio.file.Path;
 import java.nio.file.SimpleFileVisitor;
 import java.nio.file.attribute.BasicFileAttributes;
-import java.util.*;
-import java.util.stream.Collectors;
-
-import static org.zwobble.hobgoblin.compiler.typechecker.NamespaceNameResolution.resolveNamespaceName;
+import java.util.ArrayList;
+import java.util.List;
 
 public class HobgoblinCompiler {
     public static final String FILE_NAME_EXTENSION = ".hob";
@@ -46,8 +42,6 @@ public class HobgoblinCompiler {
             untypedNamespaceNodes.add(untypedNamespaceNode);
         }
 
-        var typedNamespaceNodes = new ArrayList<TypedNamespaceNode>();
-
         var typeCheckerContext = TypeCheckerGlobalContext.initial();
         typeCheckerContext.addNativeType(NativeTypes.BOOL);
         typeCheckerContext.addNativeType(NativeTypes.INT_8);
@@ -58,10 +52,7 @@ public class HobgoblinCompiler {
         typeCheckerContext.addNativeTypeConstructor(NativeTypes.OPTION);
         typeCheckerContext.addNativeTypeConstructor(NativeTypes.SHARED);
 
-        for (var untypedNamespaceNode : sortUntypedNamespaceNodes(untypedNamespaceNodes)) {
-            var typedNamespaceNode = TypeChecker.typeCheckNamespace(untypedNamespaceNode, typeCheckerContext);
-            typedNamespaceNodes.add(typedNamespaceNode);
-        }
+        var typedNamespaceNodes = TypeChecker.typeCheckNamespaces(untypedNamespaceNodes, typeCheckerContext);
 
         var typesInfo = typeCheckerContext.toTypesInfo();
 
@@ -70,47 +61,6 @@ public class HobgoblinCompiler {
         }
     }
 
-    private static List<UntypedNamespaceNode> sortUntypedNamespaceNodes(List<UntypedNamespaceNode> namespaceNodes) {
-        var namespaceNodesByName = namespaceNodes.stream()
-            .collect(Collectors.toMap(node -> node.namespaceName(), node -> node));
-
-        var sortedNamespaceNodes = new ArrayList<UntypedNamespaceNode>();
-        var handledNamespaceNames = new HashSet<NamespaceName>();
-        var pendingNamespaceNodes = new ArrayDeque<>(namespaceNodes);
-
-        while (!pendingNamespaceNodes.isEmpty()) {
-            var namespaceNode = pendingNamespaceNodes.removeLast();
-            // TODO: handle cycles
-            if (!handledNamespaceNames.contains(namespaceNode.namespaceName())) {
-                var unhandledDependencies = new ArrayList<UntypedNamespaceNode>();
-                for (var importNode : namespaceNode.imports()) {
-                    var importedNamespaceName = resolveNamespaceName(
-                        namespaceNode.namespaceName(),
-                        importNode.ancestorDepth(),
-                        importNode.namespaceName(),
-                        importNode.source()
-                    );
-                    if (!handledNamespaceNames.contains(importedNamespaceName)) {
-                        unhandledDependencies.add(
-                            Optional.ofNullable(namespaceNodesByName.get(importedNamespaceName))
-                                .orElseThrow(() -> new UnknownNamespaceError(importedNamespaceName, importNode.source()))
-                        );
-                    }
-                }
-
-                if (unhandledDependencies.isEmpty()) {
-                    handledNamespaceNames.add(namespaceNode.namespaceName());
-                    sortedNamespaceNodes.add(namespaceNode);
-                } else {
-                    pendingNamespaceNodes.add(namespaceNode);
-                    pendingNamespaceNodes.addAll(unhandledDependencies);
-                }
-            }
-        }
-
-        return sortedNamespaceNodes;
-    }
-
     static NamespaceName sourceFileNamespaceName(Path sourceDirectory, Path sourceFilePath) {
         var relativePath = sourceDirectory.relativize(sourceFilePath);
 
diff --git a/src/main/java/org/zwobble/hobgoblin/compiler/typechecker/TypeChecker.java b/src/main/java/org/zwobble/hobgoblin/compiler/typechecker/TypeChecker.java
index e8fc633..f448a56 100644
--- a/src/main/java/org/zwobble/hobgoblin/compiler/typechecker/TypeChecker.java
+++ b/src/main/java/org/zwobble/hobgoblin/compiler/typechecker/TypeChecker.java
@@ -9,6 +9,7 @@ import org.zwobble.hobgoblin.compiler.types.*;
 import java.util.ArrayList;
 import java.util.List;
 import java.util.Optional;
+import java.util.stream.Collectors;
 
 import static org.zwobble.hobgoblin.compiler.typechecker.NamespaceNameResolution.resolveNamespaceName;
 import static org.zwobble.hobgoblin.compiler.typechecker.TypeCheckerSubtyping.isSubtype;
@@ -18,53 +19,69 @@ public class TypeChecker {
     private TypeChecker() {
     }
 
-    public static TypedNamespaceNode typeCheckNamespace(
-        UntypedNamespaceNode untyped,
+    public static List<TypedNamespaceNode> typeCheckNamespaces(
+        List<UntypedNamespaceNode> untypedNamespaces,
         TypeCheckerGlobalContext context
     ) {
-        var namespaceContext = context.enterNamespace(untyped.namespaceName());
-
-        for (var untypedImport : untyped.imports()) {
-            var importedNamespace = resolveNamespaceName(
-                untyped.namespaceName(),
-                untypedImport.ancestorDepth(),
-                untypedImport.namespaceName(),
-                untypedImport.source()
-            );
-
-            var importedNamespaceFields = context.namespaceFields(importedNamespace)
-                .orElseThrow(() -> new UnknownNamespaceError(importedNamespace, untypedImport.source()));
-
-            for (var importedName : untypedImport.importedNames()) {
-                var fieldType = importedNamespaceFields.fieldType(importedName)
-                    .orElseThrow(() -> new UnknownNamespaceFieldError(
-                        importedName,
-                        importedNamespace,
-                        untypedImport.source()
-                    ));
-                namespaceContext.declare(importedName, fieldType, untypedImport.source());
+        var namespaceContexts = untypedNamespaces.stream()
+            .collect(Collectors.toMap(
+                untypedNamespace -> untypedNamespace.namespaceName(),
+                untypedNamespace -> context.enterNamespace(untypedNamespace.namespaceName())
+            ));
+
+        for (var untypedNamespace : untypedNamespaces) {
+            var namespaceContext = namespaceContexts.get(untypedNamespace.namespaceName());
+
+            var fields = new ArrayList<Field>();
+            for (var untypedStatement : untypedNamespace.body()) {
+                var type = declareNamespaceStatement(untypedStatement, namespaceContext);
+                var field = new Field(untypedStatement.name(), type, untypedStatement.source());
+                fields.add(field);
             }
+            context.defineNamespace(untypedNamespace.namespaceName(), fields);
         }
 
-        var fields = new ArrayList<Field>();
-        for (var untypedStatement : untyped.body()) {
-            var type = declareNamespaceStatement(untypedStatement, namespaceContext);
-            var field = new Field(untypedStatement.name(), type, untypedStatement.source());
-            fields.add(field);
-        }
-        context.defineNamespace(untyped.namespaceName(), fields);
+        var typedNamespaceNodes = new ArrayList<TypedNamespaceNode>();
+
+        for (var untypedNamespace : untypedNamespaces) {
+            var namespaceContext = namespaceContexts.get(untypedNamespace.namespaceName());
+
+            for (var untypedImport : untypedNamespace.imports()) {
+                var importedNamespace = resolveNamespaceName(
+                    untypedNamespace.namespaceName(),
+                    untypedImport.ancestorDepth(),
+                    untypedImport.namespaceName(),
+                    untypedImport.source()
+                );
 
-        var typedBody = new ArrayList<TypedNamespaceStatementNode>();
-        for (var untypedStatement : untyped.body()) {
-            var typedStatement = defineNamespaceStatement(untypedStatement, namespaceContext);
-            typedBody.add(typedStatement);
+                var importedNamespaceFields = context.namespaceFields(importedNamespace)
+                    .orElseThrow(() -> new UnknownNamespaceError(importedNamespace, untypedImport.source()));
+
+                for (var importedName : untypedImport.importedNames()) {
+                    var fieldType = importedNamespaceFields.fieldType(importedName)
+                        .orElseThrow(() -> new UnknownNamespaceFieldError(
+                            importedName,
+                            importedNamespace,
+                            untypedImport.source()
+                        ));
+                    namespaceContext.declare(importedName, fieldType, untypedImport.source());
+                }
+            }
+
+            var typedBody = new ArrayList<TypedNamespaceStatementNode>();
+            for (var untypedStatement : untypedNamespace.body()) {
+                var typedStatement = defineNamespaceStatement(untypedStatement, namespaceContext);
+                typedBody.add(typedStatement);
+            }
+
+            typedNamespaceNodes.add(new TypedNamespaceNode(
+                untypedNamespace.namespaceName(),
+                typedBody,
+                untypedNamespace.source()
+            ));
         }
 
-        return new TypedNamespaceNode(
-            untyped.namespaceName(),
-            typedBody,
-            untyped.source()
-        );
+        return typedNamespaceNodes;
     }
 
     static Type declareNamespaceStatement(
@@ -311,6 +328,8 @@ public class TypeChecker {
         Optional<List<Field>> variantTypeFields,
         TypesInfo typesInfo
     ) {
+        // TODO: check that variant and sum are in the same namespace.
+
         for (var sumTypeField : sumTypeFields) {
             var variantTypeField = variantTypeFields.flatMap(
                 fields -> fields.stream()
diff --git a/src/test/java/org/zwobble/hobgoblin/compiler/typechecker/TypeCheckerNamespaceTests.java b/src/test/java/org/zwobble/hobgoblin/compiler/typechecker/TypeCheckerNamespaceTests.java
index b5814a8..95ad671 100644
--- a/src/test/java/org/zwobble/hobgoblin/compiler/typechecker/TypeCheckerNamespaceTests.java
+++ b/src/test/java/org/zwobble/hobgoblin/compiler/typechecker/TypeCheckerNamespaceTests.java
@@ -31,9 +31,9 @@ public class TypeCheckerNamespaceTests {
             .build();
         var context = TypeCheckerContextArb.globalContext();
 
-        var typed = TypeChecker.typeCheckNamespace(untyped, context);
+        var typed = TypeChecker.typeCheckNamespaces(List.of(untyped), context);
 
-        assertThat(typed, instanceOf(
+        assertThat(typed, containsExactly(instanceOf(
             TypedNamespaceNode.class,
             has("body", TypedNamespaceNode::body, isSequence(
                 instanceOf(
@@ -45,7 +45,7 @@ public class TypeCheckerNamespaceTests {
                     )
                 )
             ))
-        ));
+        )));
         assertThat(
             context.namespaceFields(NamespaceName.of("a", "b")).orElseThrow().fieldType("X").orElseThrow(),
             isMetaType(new StructType(NamespaceName.of("a", "b"), "X"))
@@ -83,9 +83,9 @@ public class TypeCheckerNamespaceTests {
                 NullSource.INSTANCE
             )));
 
-        var typed = TypeChecker.typeCheckNamespace(untyped, context);
+        var typed = TypeChecker.typeCheckNamespaces(List.of(untyped), context);
 
-        assertThat(typed, instanceOf(
+        assertThat(typed, containsExactly(instanceOf(
             TypedNamespaceNode.class,
             has("body", TypedNamespaceNode::body, isSequence(
                 instanceOf(
@@ -97,7 +97,7 @@ public class TypeCheckerNamespaceTests {
                     )
                 )
             ))
-        ));
+        )));
         assertThat(
             context.toTypesInfo().fieldsOf(new StructType(NamespaceName.of("a", "b"), "X")),
             isOptionalOf(isSequence(
@@ -121,7 +121,7 @@ public class TypeCheckerNamespaceTests {
 
         var error = assertThrows(
             UnknownNamespaceError.class,
-            () -> TypeChecker.typeCheckNamespace(untyped, context)
+            () -> TypeChecker.typeCheckNamespaces(List.of(untyped), context)
         );
 
         assertThat(error.namespaceName(), equalTo(NamespaceName.of("a")));
@@ -143,7 +143,7 @@ public class TypeCheckerNamespaceTests {
 
         var error = assertThrows(
             UnknownNamespaceFieldError.class,
-            () -> TypeChecker.typeCheckNamespace(untyped, context)
+            () -> TypeChecker.typeCheckNamespaces(List.of(untyped), context)
         );
 
         assertThat(error.fieldName(), equalTo("A"));
diff --git a/src/test/java/org/zwobble/hobgoblin/compiler/typechecker/TypeCheckerStructDefinitionTests.java b/src/test/java/org/zwobble/hobgoblin/compiler/typechecker/TypeCheckerStructDefinitionTests.java
index d86fd59..ceb7a9b 100644
--- a/src/test/java/org/zwobble/hobgoblin/compiler/typechecker/TypeCheckerStructDefinitionTests.java
+++ b/src/test/java/org/zwobble/hobgoblin/compiler/typechecker/TypeCheckerStructDefinitionTests.java
@@ -150,9 +150,9 @@ public class TypeCheckerStructDefinitionTests {
         var context = TypeCheckerContextArb.globalContext();
         context.addNativeType(int32Type);
 
-        var typed = TypeChecker.typeCheckNamespace(untyped, context);
+        var typed = TypeChecker.typeCheckNamespaces(List.of(untyped), context);
 
-        assertThat(typed, has(
+        assertThat(typed, containsExactly(has(
             "body",
             TypedNamespaceNode::body,
             isSequence(
@@ -193,6 +193,6 @@ public class TypeCheckerStructDefinitionTests {
                     )
                 )
             )
-        ));
+        )));
     }
 }