From: adam <adam@megacz.com>
Date: Sat, 15 Jul 2006 06:31:17 +0000 (-0400)
Subject: checkpoint
X-Git-Tag: tag_for_25-Mar~134
X-Git-Url: http://git.megacz.com/?p=sbp.git;a=commitdiff_plain;h=a26089cd0d7c95cad657b745e836cb4cba35a97a

checkpoint

darcs-hash:20060715063117-5007d-6c0d0dcc86f023b2d0dc72e0516ac3789c3f5bf5.gz
---

diff --git a/src/edu/berkeley/sbp/Forest.java b/src/edu/berkeley/sbp/Forest.java
index 00f826a..7fde86e 100644
--- a/src/edu/berkeley/sbp/Forest.java
+++ b/src/edu/berkeley/sbp/Forest.java
@@ -16,35 +16,26 @@ public abstract class Forest<T> /*extends PrintableTree<Forest.Body<T>>*/
     public int toInt() { return idx; }
 
     /** assume that this forest contains exactly one tree and return it; otherwise throw an exception */
-    public final Tree<T> expand1() throws Ambiguous, ParseFailed {
-        try {
-            Iterator<Tree<T>> it = expand(true).iterator();
-            if (!it.hasNext()) throw new ParseFailed();
-            return it.next();
-        } catch (InnerAmbiguous ia) { throw new Ambiguous(ia.f); }
-    }
+    public abstract Tree<T> expand1() throws Ambiguous;
 
     /** expand this forest into a set of trees */
-    public abstract void expand(HashSet<Tree<T>> ht);
+    public void expand(HashSet<Tree<T>> ht) { expand(ht, new HashSet<Forest<T>>(), null); }
+    public abstract void expand(HashSet<Tree<T>> ht, HashSet<Forest<T>> ignore, Tree<T> bogus);
+    public abstract void gather(HashSet<Forest<T>> ignore);
     public HashSet<Tree<T>> expand(boolean toss) {
         HashSet<Tree<T>> ret = new HashSet<Tree<T>>();
         expand(ret);
         return ret;
     }
 
-    private static class InnerAmbiguous extends RuntimeException {
-        public final Forest<?> f;
-        public InnerAmbiguous(Forest<?> f) { this.f = f; }
-    }
-
-    static        <T> Forest<T> leaf(Input.Region loc, T tag) { return create(loc, tag, null, false); }
     public static <T> Forest<T> create(Input.Region loc, T tag, Forest<T>[] tokens, boolean unwrap) {
         return new Body<T>(loc, tag, tokens, unwrap);
     }
-    // Body //////////////////////////////////////////////////////////////////////////////
-
     public abstract void edges(GraphViz.Node n);
     public boolean ambiguous() { return false; }
+
+    // Body //////////////////////////////////////////////////////////////////////////////
+
     public /*protected*/ static class Body<T> extends Forest<T> /* extends PrintableTree<Forest<T>> implements */ {
 
         private final Input.Region      location;
@@ -52,6 +43,45 @@ public abstract class Forest<T> /*extends PrintableTree<Forest.Body<T>>*/
         private final Forest<T>[]       tokens;
         private final boolean           unwrap;
 
+        private Body(Input.Region loc, T tag, Forest<T>[] tokens, boolean unwrap) {
+            this.location = loc;
+            this.tag = tag;
+            this.tokens = tokens==null ? emptyForestArray : new Forest[tokens.length];
+            if (tokens != null) System.arraycopy(tokens, 0, this.tokens, 0, tokens.length);
+            if (tokens != null) for(int i=0; i<tokens.length; i++) if (tokens[i]==null) throw new Error(i+"");
+            this.unwrap = unwrap;
+        }
+
+        public Tree<T> expand1() throws Ambiguous {
+            Tree<T>[] ret = new Tree[tokens.length];
+            for(int i=0; i<tokens.length; i++)
+                ret[i] = tokens[i].expand1();
+            return new Tree<T>(location, tag, ret, unwrap);
+        }
+        public void gather(HashSet<Forest<T>> hf) {
+            hf.add(this);
+            for(Forest<T> f : tokens) f.gather(hf);
+        }
+        public void expand(HashSet<Tree<T>> ht, HashSet<Forest<T>> ignore, Tree<T> bogus) {
+            if (ignore.contains(this)) { ht.add(bogus); return; }
+            expand(0, new Tree[tokens.length], ht, ignore, bogus);
+        }
+        public void expand(final int i, Tree<T>[] ta, HashSet<Tree<T>> ht, HashSet<Forest<T>> ignore, Tree<T> bogus) {
+            if (i==tokens.length) {
+                ht.add(new Tree<T>(location, tag, ta, unwrap));
+            } else {
+                HashSet<Tree<T>> ht2 = new HashSet<Tree<T>>();
+                tokens[i].expand(ht2, ignore, bogus);
+                for(Tree<T> tc : ht2) {
+                    ta[i] = tc;
+                    expand(i+1, ta, ht, ignore, bogus);
+                    ta[i] = null;
+                }
+            }
+        }
+
+        // GraphViz, ToInt //////////////////////////////////////////////////////////////////////////////
+
         public boolean isTransparent() { return false; }
         public boolean isHidden() { return false; }
         public GraphViz.Node toGraphViz(GraphViz gv) {
@@ -59,7 +89,6 @@ public abstract class Forest<T> /*extends PrintableTree<Forest.Body<T>>*/
             GraphViz.Node n = gv.createNode(this);
             n.label = headToString()==null?"":headToString();
             n.directed = true;
-            //n.comment = reduction==null?null:reduction+"";
             edges(n);
             return n;
         }
@@ -76,32 +105,6 @@ public abstract class Forest<T> /*extends PrintableTree<Forest.Body<T>>*/
             }
         }
 
-        private Body(Input.Region loc, T tag, Forest<T>[] tokens, boolean unwrap) {
-            this.location = loc;
-            this.tag = tag;
-            this.tokens = tokens==null ? emptyForestArray : new Forest[tokens.length];
-            if (tokens != null) System.arraycopy(tokens, 0, this.tokens, 0, tokens.length);
-            if (tokens != null) for(int i=0; i<tokens.length; i++) if (tokens[i]==null) throw new Error(i+"");
-            this.unwrap = unwrap;
-        }
-
-        public void expand(HashSet<Tree<T>> ht) {
-            expand(0, new Tree[tokens.length], ht);
-        }
-        public void expand(final int i, Tree<T>[] ta, HashSet<Tree<T>> ht) {
-            if (i==tokens.length) {
-                ht.add(new Tree<T>(location, tag, ta, unwrap));
-                return;
-            }
-            HashSet<Tree<T>> ht2 = new HashSet<Tree<T>>();
-            tokens[i].expand(ht2);
-            for(Tree<T> tc : ht2) {
-                ta[i] = tc;
-                expand(i+1, ta, ht);
-                ta[i] = null;
-            }
-        }
-
         protected String  headToString()         { return tag==null?null:tag.toString(); }
         protected String  headToJava()           { return "null"; }
         protected String  left()                 { return "{"; }
@@ -118,27 +121,40 @@ public abstract class Forest<T> /*extends PrintableTree<Forest.Body<T>>*/
      *  viewed, it becomes immutable
      */
     static class Ref<T> extends Forest<T> {
-        public void expand(HashSet<Tree<T>> ht) {
-            for (Forest<T> f : hp)
-                f.expand(ht);
-        }
         public HashSet<GSS.Phase.Node> parents = new HashSet<GSS.Phase.Node>();
-        public boolean contains(Forest f) {
-            return hp.contains(f);
+        private FastSet<Forest<T>> hp = new FastSet<Forest<T>>();
+
+        public Ref() { }
+
+        public Tree<T> expand1() throws Ambiguous {
+            if (hp.size() > 1) throw new Ambiguous(this);
+            return hp.iterator().next().expand1();
+        }
+        
+        public void gather(HashSet<Forest<T>> ht) {
+            ht.add(this);
+            for(Forest<T> f : hp) f.gather(ht);
+        }
+
+        public Forest resolve() { return this; }
+        public void expand(HashSet<Tree<T>> ht, HashSet<Forest<T>> ignore, Tree<T> bogus) {
+            if (ignore.contains(this)) { ht.add(bogus); return; }
+            for (Forest<T> f : hp) f.expand(ht, ignore, bogus);
         }
+        public boolean contains(Forest f) { return hp.contains(f); }
+        public void merge(Forest p) { if (p!=this) hp.add(p, true); }
         public boolean ambiguous() {
             if (hp.size()==0) return false;
             if (hp.size()==1) return hp.iterator().next().ambiguous();
             return true;
         }
-        private FastSet<Forest<T>> hp = new FastSet<Forest<T>>();
-        public Ref() { }
+
+        // GraphViz, ToInt //////////////////////////////////////////////////////////////////////////////
+
         public int toInt() {
             if (hp.size()==1) return hp.iterator().next().toInt();
             return super.toInt();
         }
-        public void merge(Forest p) { if (p!=this) hp.add(p, true); }
-
         public boolean isTransparent() { return hp.size()==1; }
         public boolean isHidden() { return hp.size()==0; }
         public void edges(GraphViz.Node n) {
@@ -155,8 +171,6 @@ public abstract class Forest<T> /*extends PrintableTree<Forest.Body<T>>*/
             for(Forest f : hp) n.edge(f, null);
             return n;
         }
-
-        public Forest resolve() { return this; }
     }
 
     // Statics //////////////////////////////////////////////////////////////////////////////
diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java
index 357519a..300ff27 100644
--- a/src/edu/berkeley/sbp/Parser.java
+++ b/src/edu/berkeley/sbp/Parser.java
@@ -26,7 +26,7 @@ public abstract class Parser<Tok, Result> {
         GSS gss = new GSS();
         Input.Location loc = input.getLocation();
         GSS.Phase current = gss.new Phase<Tok>(null, this, null, input.next(), loc, null);
-        current.newNode(null, Forest.leaf(null, null), pt.start, true);
+        current.newNode(null, Forest.create(null, null, null, false), pt.start, true);
         int count = 1;
         for(int idx=0;;idx++) {
             Input.Location oldloc = loc;
diff --git a/src/edu/berkeley/sbp/Sequence.java b/src/edu/berkeley/sbp/Sequence.java
index c3c259f..e5db6c8 100644
--- a/src/edu/berkeley/sbp/Sequence.java
+++ b/src/edu/berkeley/sbp/Sequence.java
@@ -184,7 +184,7 @@ public abstract class Sequence extends Element implements Iterable<Element> {
         public Constant(Element[] e, Object result) { super(e); this.result = result; }
         Sequence _clone() { return new Constant(elements, result); }
         public <T> Forest<T> postReduce(Input.Region loc, Forest<T>[] args, Position p) {
-            return (Forest<T>)Forest.leaf(loc, result);
+            return (Forest<T>)Forest.create(loc, result, null, false);
         }
         static class Drop extends Constant {
             Sequence _clone() { return new Drop(elements, lame); }