make expand1() use a non-recursive descent function to avoid stack overflows

[sbp.git] / src / edu / berkeley / sbp / Forest.java

diff --git a/src/edu/berkeley/sbp/Forest.java b/src/edu/berkeley/sbp/Forest.java
index 636ad4f..073e37b 100644 (file)
--- a/src/edu/berkeley/sbp/Forest.java
+++ b/src/edu/berkeley/sbp/Forest.java
@@ -65,9 +65,10 @@ public abstract class Forest<NodeType> implements GraphViz.ToGraphViz {
         }
 
         public Tree<NodeType> expand1() throws Ambiguous {
-            Tree<NodeType>[] ret = new Tree[children.length];
-            for(int i=0; i<children.length; i++) ret[i] = children[i].expand1();
-            return new Tree<NodeType>(location, head, ret, lifts);
+            if (children.length == 0)
+                return new Tree<NodeType>(location, head);
+            else
+                return expand1ForOneAndMany((Forest<NodeType>)this);
         }
 
         void gather(HashSet<Forest<NodeType>> hf) {
@@ -138,7 +139,7 @@ public abstract class Forest<NodeType> implements GraphViz.ToGraphViz {
 
         public Input.Region getRegion() { return hp.iterator().next().getRegion(); } // all should be identical
 
-        public Tree<NodeType> expand1() throws Ambiguous {
+        Forest<NodeType> simplify() throws Ambiguous {
             touched();
             if (hp.size() > 1) {
                 HashSet<Forest<NodeType>> hf0 = new HashSet<Forest<NodeType>>();
@@ -154,7 +155,12 @@ public abstract class Forest<NodeType> implements GraphViz.ToGraphViz {
                 throw new Ambiguous((Forest<?>)this,
                                     (HashSet<Tree<?>>)(Object)ht);
             }
-            return hp.iterator().next().expand1();
+
+            return hp.iterator().next();
+        }
+
+        public Tree<NodeType> expand1() throws Ambiguous {
+            return simplify().expand1();
         }
         
         void gather(HashSet<Forest<NodeType>> ht) {
@@ -225,8 +231,87 @@ public abstract class Forest<NodeType> implements GraphViz.ToGraphViz {
         }
     }
 
+
     // Statics //////////////////////////////////////////////////////////////////////////////
 
+    /** Depth-first expansion, handling .One and .Many without recursion. */
+    private static <NodeType> Tree<NodeType> expand1ForOneAndMany(
+            Forest<NodeType> forest) throws Ambiguous {
+        List<Tree<NodeType>> nodes = new ArrayList<Tree<NodeType>>();
+        List<Tree<NodeType>> build = new ArrayList<Tree<NodeType>>();
+
+        // path stack
+        List<Forest.One<NodeType>> path = new ArrayList<Forest.One<NodeType>>();
+        List<Integer> sizes = new ArrayList<Integer>(),
+                      poss  = new ArrayList<Integer>();
+
+        // handle the left-most leaf
+        expand1Descend(path, nodes, sizes, poss, forest);
+
+        for (Forest.One<NodeType> f; path.size() > 0;) {
+            // up one
+            f = pop(path);
+            int size = pop(sizes) + 1;
+            int pos = pop(poss) + 1;
+            Forest<NodeType>[] children = f.children;
+            if (pos < children.length) {
+                // down the next branch
+                path.add(f);
+                sizes.add(new Integer(size));
+                poss.add(new Integer(pos));
+
+                // handle the left-most leaf
+                expand1Descend(path, nodes, sizes, poss, children[pos]);
+            } else {
+                if (path.size() > 0 && peek(path).lifts[peek(poss)]) {
+                    // skip assembling this node, lift children
+                    sizes.add(pop(sizes) + size - 1);
+                    continue;
+                }
+                // assemble this node
+                for (int i=size; i > 0; i--)
+                    build.add(nodes.remove(nodes.size() - i));
+                nodes.add(new Tree<NodeType>(f.location, f.head, build));
+                build.clear();
+            }
+        }
+
+        return pop(nodes);
+    }
+
+    /** Descend to the left-most leaf, building the path. */
+    private static <NodeType> void expand1Descend(
+            List<Forest.One<NodeType>> path, List<Tree<NodeType>> nodes,
+            List<Integer> sizes, List<Integer> poss, Forest<NodeType> f)
+            throws Ambiguous {
+        while (true) {
+            if (f instanceof Forest.Many)
+                f = ((Forest.Many<NodeType>)f).simplify();
+            else if (f instanceof Forest.One) {
+                Forest.One<NodeType> one = (Forest.One<NodeType>)f;
+                if (one.children.length == 0)
+                    break;
+                path.add(one);
+                sizes.add(0);
+                poss.add(0);
+                f = one.children[0];
+            } else {
+                nodes.add(f.expand1());
+                return;
+            }
+        }
+
+        if (path.size() > 0 && peek(path).lifts[peek(poss)])
+            sizes.add(pop(sizes) - 1); // ignore lifted leafs
+        else
+            nodes.add(f.expand1());
+    }
+
+    private static <T> T pop(List<T> list) {
+        return list.remove(list.size() - 1); }
+    private static <T> T peek(List<T> list) {
+        return list.get(list.size() - 1); }
+
     private static Tree[] tree_hint = new Tree[0];
     private static String[] string_hint = new String[0];
     private static final Forest[] emptyForestArray = new Forest[0];