Sort namespaces by imports

2 files changed, 61 insertions, 10 deletions

diff --git a/src/main/java/org/zwobble/hobgoblin/compiler/HobgoblinCompiler.java b/src/main/java/org/zwobble/hobgoblin/compiler/HobgoblinCompiler.java
index 4093938..e9a8122 100644
--- a/src/main/java/org/zwobble/hobgoblin/compiler/HobgoblinCompiler.java
+++ b/src/main/java/org/zwobble/hobgoblin/compiler/HobgoblinCompiler.java
@@ -1,6 +1,7 @@
 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;
@@ -16,8 +17,10 @@ import java.nio.file.Files;
 import java.nio.file.Path;
 import java.nio.file.SimpleFileVisitor;
 import java.nio.file.attribute.BasicFileAttributes;
-import java.util.ArrayList;
-import java.util.List;
+import java.util.*;
+import java.util.stream.Collectors;
+
+import static org.zwobble.hobgoblin.compiler.typechecker.NamespaceNameResolution.resolveNamespaceName;
 
 public class HobgoblinCompiler {
     public static final String FILE_NAME_EXTENSION = ".hob";
@@ -31,6 +34,17 @@ public class HobgoblinCompiler {
 
         var sourceDirectory = projectRoot.resolve("src");
 
+        var sourceFiles = collectSourceFiles(sourceDirectory);
+
+        var untypedNamespaceNodes = new ArrayList<UntypedNamespaceNode>();
+        for (var sourceFile : sourceFiles) {
+            var namespaceName = sourceFileNamespaceName(sourceDirectory, sourceFile);
+            var sourceContents = Files.readString(sourceFile, StandardCharsets.UTF_8);
+            var sourceText = SourceText.fromString(sourceFile.toString(), sourceContents);
+            var untypedNamespaceNode = Parser.parseNamespace(sourceText, namespaceName);
+            untypedNamespaceNodes.add(untypedNamespaceNode);
+        }
+
         var typedNamespaceNodes = new ArrayList<TypedNamespaceNode>();
 
         var typeCheckerContext = TypeCheckerGlobalContext.initial();
@@ -40,12 +54,7 @@ public class HobgoblinCompiler {
         typeCheckerContext.addNativeTypeConstructor(NativeTypes.LIST);
         typeCheckerContext.addNativeTypeConstructor(NativeTypes.OPTION);
 
-        for (var sourceFile : collectSourceFiles(sourceDirectory)) {
-            var namespaceName = sourceFileNamespaceName(sourceDirectory, sourceFile);
-            var sourceContents = Files.readString(sourceFile, StandardCharsets.UTF_8);
-            var sourceText = SourceText.fromString(sourceFile.toString(), sourceContents);
-            var untypedNamespaceNode = Parser.parseNamespace(sourceText, namespaceName);
-
+        for (var untypedNamespaceNode : sortUntypedNamespaceNodes(untypedNamespaceNodes)) {
             var typedNamespaceNode = TypeChecker.typeCheckNamespace(untypedNamespaceNode, typeCheckerContext);
             typedNamespaceNodes.add(typedNamespaceNode);
         }
@@ -57,6 +66,47 @@ 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()
+                    );
+                    if (!handledNamespaceNames.contains(importedNamespaceName)) {
+                        System.out.println(namespaceNodesByName);
+                        System.out.println(importedNamespaceName);
+                        unhandledDependencies.add(
+                            // TODO: better error
+                            Optional.ofNullable(namespaceNodesByName.get(importedNamespaceName)).orElseThrow()
+                        );
+                    }
+                }
+
+                if (unhandledDependencies.isEmpty()) {
+                    handledNamespaceNames.add(namespaceNode.namespaceName());
+                } 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/NamespaceNameResolution.java b/src/main/java/org/zwobble/hobgoblin/compiler/typechecker/NamespaceNameResolution.java
index f3f8d89..28b709f 100644
--- a/src/main/java/org/zwobble/hobgoblin/compiler/typechecker/NamespaceNameResolution.java
+++ b/src/main/java/org/zwobble/hobgoblin/compiler/typechecker/NamespaceNameResolution.java
@@ -5,10 +5,10 @@ import org.zwobble.hobgoblin.compiler.types.NamespaceName;
 import java.util.ArrayList;
 import java.util.Optional;
 
-class NamespaceNameResolution {
+public class NamespaceNameResolution {
     private NamespaceNameResolution() {}
 
-    static NamespaceName resolveNamespaceName(
+    public static NamespaceName resolveNamespaceName(
         NamespaceName current,
         Optional<Integer> importedAncestorDepth,
         NamespaceName importedNamespaceName
@@ -18,6 +18,7 @@ class NamespaceNameResolution {
         }
 
         // TODO: handle invalid depth (too large).
+        // TODO: should always skip right-most part? For instance, within src/line.hob, does ./point reference src/point.hob or src/line/point.hob?
         var parts = new ArrayList<>(current.parts().subList(0, current.parts().size() - importedAncestorDepth.get()));
         parts.addAll(importedNamespaceName.parts());
         return new NamespaceName(parts);