From b336fb8bdddaea87f92505acbdbf0893a48bc34e Mon Sep 17 00:00:00 2001 From: David Crawshaw Date: Mon, 9 Jun 2008 21:20:57 -0400 Subject: [PATCH] make expand1() use a non-recursive descent function to avoid stack overflows darcs-hash:20080610012057-0c629-bd192d08a902a0b284949f751c857e72d0c4f472.gz --- src/edu/berkeley/sbp/Forest.java | 95 ++++++++++++++++++++++++++++++++++++-- src/edu/berkeley/sbp/Tree.java | 24 +++++++++- 2 files changed, 112 insertions(+), 7 deletions(-) diff --git a/src/edu/berkeley/sbp/Forest.java b/src/edu/berkeley/sbp/Forest.java index 636ad4f..073e37b 100644 --- a/src/edu/berkeley/sbp/Forest.java +++ b/src/edu/berkeley/sbp/Forest.java @@ -65,9 +65,10 @@ public abstract class Forest implements GraphViz.ToGraphViz { } public Tree expand1() throws Ambiguous { - Tree[] ret = new Tree[children.length]; - for(int i=0; i(location, head, ret, lifts); + if (children.length == 0) + return new Tree(location, head); + else + return expand1ForOneAndMany((Forest)this); } void gather(HashSet> hf) { @@ -138,7 +139,7 @@ public abstract class Forest implements GraphViz.ToGraphViz { public Input.Region getRegion() { return hp.iterator().next().getRegion(); } // all should be identical - public Tree expand1() throws Ambiguous { + Forest simplify() throws Ambiguous { touched(); if (hp.size() > 1) { HashSet> hf0 = new HashSet>(); @@ -154,7 +155,12 @@ public abstract class Forest implements GraphViz.ToGraphViz { throw new Ambiguous((Forest)this, (HashSet>)(Object)ht); } - return hp.iterator().next().expand1(); + + return hp.iterator().next(); + } + + public Tree expand1() throws Ambiguous { + return simplify().expand1(); } void gather(HashSet> ht) { @@ -225,8 +231,87 @@ public abstract class Forest implements GraphViz.ToGraphViz { } } + // Statics ////////////////////////////////////////////////////////////////////////////// + /** Depth-first expansion, handling .One and .Many without recursion. */ + private static Tree expand1ForOneAndMany( + Forest forest) throws Ambiguous { + List> nodes = new ArrayList>(); + List> build = new ArrayList>(); + + // path stack + List> path = new ArrayList>(); + List sizes = new ArrayList(), + poss = new ArrayList(); + + // handle the left-most leaf + expand1Descend(path, nodes, sizes, poss, forest); + + for (Forest.One f; path.size() > 0;) { + // up one + f = pop(path); + int size = pop(sizes) + 1; + int pos = pop(poss) + 1; + Forest[] 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(f.location, f.head, build)); + build.clear(); + } + } + + return pop(nodes); + } + + /** Descend to the left-most leaf, building the path. */ + private static void expand1Descend( + List> path, List> nodes, + List sizes, List poss, Forest f) + throws Ambiguous { + while (true) { + if (f instanceof Forest.Many) + f = ((Forest.Many)f).simplify(); + else if (f instanceof Forest.One) { + Forest.One one = (Forest.One)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 pop(List list) { + return list.remove(list.size() - 1); } + private static T peek(List 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]; diff --git a/src/edu/berkeley/sbp/Tree.java b/src/edu/berkeley/sbp/Tree.java index ab6ff7a..62dfa9d 100644 --- a/src/edu/berkeley/sbp/Tree.java +++ b/src/edu/berkeley/sbp/Tree.java @@ -12,6 +12,8 @@ public class Tree extends PrintableTree> implements Iterable> { + private static final Tree[] emptyTree = new Tree[0]; + private final Input.Region location; private final NodeType ihead; private final Tree[] children; @@ -35,8 +37,26 @@ public class Tree /** get the input region that this tree was parsed from */ public Input.Region getRegion() { return location; } - public Tree(Input.Region loc, NodeType head) { this(loc, head, new Tree[0]); } - public Tree(Input.Region loc, NodeType head, Tree[] children) { this(loc, head, children, new boolean[children==null?0:children.length]); } + public Tree(Input.Region loc, NodeType head) { + location = loc; + ihead = head; + children = emptyTree; + } + public Tree(Input.Region loc, NodeType head, List> kids){ + location = loc; + ihead = head; + if (children.size() == 0) + children = emptyTree; + else { + children = new Tree[kids.size()]; + kids.toArray(children); + } + } + public Tree(Input.Region loc, NodeType head, Tree[] kids) { + location = loc; + ihead = head; + children = (kids == null ? emptyTree : kids.clone()); + } // FIXME: fairly inefficient because we keep copying arrays /** package-private constructor, allows setting the "lift" bit */ -- 1.7.10.4