MergeSort to its own file

Allow self-recursive forward refs.
Missing progress.

4 files changed, 78 insertions, 8 deletions

diff --git a/chapter18/src/main/java/com/seaofnodes/simple/Parser.java b/chapter18/src/main/java/com/seaofnodes/simple/Parser.java
index 8f0cf493..4f19dda2 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/Parser.java
@@ -1123,10 +1123,14 @@ public class Parser {
             _scope.define(id, FRefNode.FREF_TYPE, true, XCTRL, loc());
             n = _scope.lookup(id);
         } else {
-            // Lookup worked on an out-of-function value.  No closures, so this
-            // has to be a final constant.
-            if( _scope.outOfFunction(n) && !(n._final && _scope.in(n._idx)._type.isConstant()) )
-                throw error("Variable '"+n._name+"' is out of function scope and must be a final constant");
+            // Lookup worked on an out-of-function value.
+            if( _scope.outOfFunction(n) ) {
+                // No closures, so this has to be a final constant (which
+                // includes forward refs)
+                Node def = _scope.in(n._idx);
+                if( !(def instanceof FRefNode) && !(n._final && def._type.isConstant()) )
+                    throw error("Variable '"+n._name+"' is out of function scope and must be a final constant");
+            }
         }
         return n;
     }
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/FunNode.java
index 8300d80f..1f0c76eb 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/FunNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/FunNode.java
@@ -71,7 +71,10 @@ public class FunNode extends RegionNode {
         // to collapse
         if( unknownCallers() ) return null;
         Node progress = super.idealize();
-        if( progress!=null ) IterPeeps.add( CodeGen.CODE._stop);
+        if( progress!=null ) {
+            IterPeeps.add( CodeGen.CODE._stop);
+            IterPeeps.add( _ret );
+        }
         return progress;
     }
 
diff --git a/chapter18/src/test/java/com/seaofnodes/simple/BrainFuckTest.java b/chapter18/src/test/java/com/seaofnodes/simple/BrainFuckTest.java
index 2995e89c..37ecde1c 100644
--- a/chapter18/src/test/java/com/seaofnodes/simple/BrainFuckTest.java
+++ b/chapter18/src/test/java/com/seaofnodes/simple/BrainFuckTest.java
@@ -1,10 +1,8 @@
 package com.seaofnodes.simple;
 
 import com.seaofnodes.simple.evaluator.Evaluator;
-import org.junit.Test;
-
 import java.nio.charset.StandardCharsets;
-
+import org.junit.Test;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.fail;
 
diff --git a/chapter18/src/test/java/com/seaofnodes/simple/MergeSortTest.java b/chapter18/src/test/java/com/seaofnodes/simple/MergeSortTest.java
new file mode 100644
index 00000000..d48449d5
--- /dev/null
+++ b/chapter18/src/test/java/com/seaofnodes/simple/MergeSortTest.java
@@ -0,0 +1,65 @@
+package com.seaofnodes.simple;
+
+import org.junit.Test;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.fail;
+
+public class MergeSortTest {
+
+    @Test
+    public void testMergeSort() {
+        CodeGen code = new CodeGen(
+"""
+// based on the top-down version from https://en.wikipedia.org/wiki/Merge_sort
+
+val merge_sort = { int[] a, int[] b, int n ->
+    copy_array(a, 0, n, b);
+    split_merge(a, 0, n, b);
+};
+
+val split_merge = { int[] b, int begin, int end, int[] a ->
+    if (end - begin <= 1)
+        return 0;
+    int middle = (end + begin) / 2;
+    split_merge(a, begin, middle, b);
+    split_merge(a, middle, end, b);
+    merge(b, begin, middle, end, a);
+    return 0;
+};
+
+val merge = { int[] b, int begin, int middle, int end, int[] a ->
+    int i = begin, j = middle;
+
+    for (int k = begin; k < end; k++) {
+        // && and ||
+        bool cond = false;
+        if (i < middle) {
+            if (j >= end)          cond = true;
+            else if (a[i] <= a[j]) cond = true;
+        }
+        if (cond) b[k] = a[i++];
+        else      b[k] = a[j++];
+    }
+};
+
+val copy_array = { int[] a, int begin, int end, int[] b ->
+    for (int k = begin; k < end; k++)
+        b[k] = a[k];
+};
+
+int[] !a = new int[arg];
+int[] !b = new int[a#];
+
+for (int i = 0; i < a#; i++)
+    a[i] = a# - i;
+
+merge_sort(a, b, a#);
+
+return a;
+""");
+        code.parse().opto();
+        assertEquals("Stop[ return [int]; return 0; ]", code._stop.toString());
+        assertEquals("int[ 1,2,3,4,5,6,7,8,9,10,11]", Eval2.eval(code, 11));
+    }
+
+}