From 96488b724e05f547cdee70beb4037ea361503606 Mon Sep 17 00:00:00 2001
From: Michael Williamson <mike@zwobble.org>
Date: Wed, 20 Dec 2023 18:53:49 +0000
Subject: Detect loops in namespace dependencies

---
 .../typechecker/NamespaceDependencyLineariser.java | 15 ++++++++++--
 .../errors/CircularNamespaceDependencyError.java   | 27 ++++++++++++++++++++++
 2 files changed, 40 insertions(+), 2 deletions(-)
 create mode 100644 src/main/java/org/shedlang/compiler/typechecker/errors/CircularNamespaceDependencyError.java

(limited to 'src/main/java')

diff --git a/src/main/java/org/shedlang/compiler/typechecker/NamespaceDependencyLineariser.java b/src/main/java/org/shedlang/compiler/typechecker/NamespaceDependencyLineariser.java
index bedb0070..ac7c2853 100644
--- a/src/main/java/org/shedlang/compiler/typechecker/NamespaceDependencyLineariser.java
+++ b/src/main/java/org/shedlang/compiler/typechecker/NamespaceDependencyLineariser.java
@@ -1,6 +1,8 @@
 package org.shedlang.compiler.typechecker;
 
 import org.shedlang.compiler.ast.untyped.UntypedNamespaceNode;
+import org.shedlang.compiler.sources.Sources;
+import org.shedlang.compiler.typechecker.errors.CircularNamespaceDependencyError;
 import org.shedlang.compiler.types.NamespaceName;
 
 import java.util.ArrayList;
@@ -21,19 +23,28 @@ public class NamespaceDependencyLineariser {
         var seen = new HashSet<NamespaceName>();
         var ordered = new ArrayList<UntypedNamespaceNode>();
 
-        // TODO: test this!
-        // TODO: handle infinite loops
         // TODO: handle missing namespaces
 
+        var stack = new ArrayList<NamespaceName>();
+
         var adder = new Object() {
             private void add(NamespaceName name) {
                 if (!seen.contains(name)) {
+                    var cycle = stack.contains(name);
+                    stack.add(name);
+
+                    if (cycle) {
+                        throw new CircularNamespaceDependencyError(stack, Sources.NULL);
+                    }
+
                     var untypedNamespaceNode = nodesByName.get(name);
                     for (var import_ : untypedNamespaceNode.imports()) {
                         add(import_.namespaceName());
                     }
                     seen.add(name);
                     ordered.add(untypedNamespaceNode);
+
+                    stack.removeLast();
                 }
             }
         };
diff --git a/src/main/java/org/shedlang/compiler/typechecker/errors/CircularNamespaceDependencyError.java b/src/main/java/org/shedlang/compiler/typechecker/errors/CircularNamespaceDependencyError.java
new file mode 100644
index 00000000..a37c2f4a
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/typechecker/errors/CircularNamespaceDependencyError.java
@@ -0,0 +1,27 @@
+package org.shedlang.compiler.typechecker.errors;
+
+import org.shedlang.compiler.errors.SourceError;
+import org.shedlang.compiler.sources.Source;
+import org.shedlang.compiler.types.NamespaceName;
+
+import java.util.List;
+import java.util.stream.Collectors;
+
+public class CircularNamespaceDependencyError extends SourceError {
+    private final List<NamespaceName> namespaceNames;
+
+    public CircularNamespaceDependencyError(List<NamespaceName> namespaceNames, Source source) {
+        super("Cyclic namespace dependencies: " + generateCycleDescription(namespaceNames), source);
+        this.namespaceNames = namespaceNames;
+    }
+
+    private static String generateCycleDescription(List<NamespaceName> namespaceNames) {
+        return namespaceNames.stream()
+            .map(namespaceName -> namespaceName.toString())
+            .collect(Collectors.joining(" -> "));
+    }
+
+    public List<NamespaceName> namespaceNames() {
+        return namespaceNames;
+    }
+}
-- 
cgit v1.2.3