X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;ds=sidebyside;f=src%2Fedu%2Fberkeley%2Fsbp%2FGSS.java;h=9b091a7f1db0d485a2055707d5dabab7d93da986;hb=dd9286cb6cab28051289fbab244d4b6a19619886;hp=743cfd381622afc430958b743fe5ac622ccb203a;hpb=225993309e6183afa9a88fc13d39df56be54b992;p=sbp.git

diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java
index 743cfd3..9b091a7 100644
--- a/src/edu/berkeley/sbp/GSS.java
+++ b/src/edu/berkeley/sbp/GSS.java
@@ -11,6 +11,7 @@ import java.lang.reflect.*;
 class GSS {
 
     public static int count = 0;
+    
     public GSS() { }
 
     private Phase.Node[] reducing_list = null;
@@ -26,8 +27,9 @@ class GSS {
     public  Forest.Ref finalResult;
 
     /** corresponds to a positions <i>between tokens</i> the input stream; same as Tomita's U_i's */
-    class Phase<Tok> implements Invokable<State, Forest, Phase<Tok>.Node>, IntegerMappable {
+    class Phase<Tok> implements Invokable<State, Forest, Phase<Tok>.Node>, IntegerMappable, GraphViz.ToGraphViz, Iterable<Phase.Node> {
 
+        public Iterator<Phase.Node> iterator() { return hash.iterator(); }
         public void invoke(State st, Forest result, Node n) {
             good |= next.newNode(n, result, st, false);
         }
@@ -39,7 +41,6 @@ class GSS {
 
         boolean reducing;
         private IntPairMap<Phase.Node> hash;  /* ALLOC */
-        private IntPairMap<Forest> singularReductions;  /* ALLOC */
         private boolean closed;
         private boolean good;
         private Phase next = null;
@@ -67,7 +68,6 @@ class GSS {
             lastperformed.addAll(performed);
             performed.clear();
             hash = new IntPairMap<Phase.Node>();
-            singularReductions = new IntPairMap<Forest>();
             reset = false;
             good = false;
             closed = false;
@@ -146,13 +146,15 @@ class GSS {
                 }
             }
         }
+
         private boolean newNode2(Node p, Node parent, Forest pending, State state, boolean fromEmptyReduction) {
-            p.holder.merge(pending);
-            if (p.parents().contains(parent)) return true;
+            //if (p.parents().contains(parent)) return true;
+            if (p.merge(parent, pending)) return true;
             p.parents().add(parent, true);
             if (p!=parent && !fromEmptyReduction && reducing) p.performReductions(parent);
             return true;
         }
+
         private boolean newNode3(Node parent, Forest pending, State state, boolean fromEmptyReduction) {
             do {
                 if (token != null && state.canShift(token)) break;
@@ -216,9 +218,8 @@ class GSS {
         /** perform all shift operations, adding promoted nodes to <tt>next</tt> */
         public void shift(Phase next, Forest result) throws ParseFailed {
             // this massively improves GC performance
-            if (prev!=null) {
+            if (prev!=null && parser.helpgc) {
                 prev.hash = null;
-                prev.singularReductions = null;
             }
             this.next = next;
             closed = true;
@@ -227,7 +228,8 @@ class GSS {
             for(Phase.Node n : hash.values()) {
                 if (token == null && n.state.isAccepting()) {
                     if (finalResult==null) finalResult = new Forest.Ref();
-                    finalResult.merge(n.holder);
+                    for(Object f : n.results())
+                        finalResult.merge((Forest)f);
                 }
                 if (token == null) continue;
                 n.state.invokeShifts(token, this, result, n);
@@ -268,9 +270,25 @@ class GSS {
         // Node /////////////////////////////////////////////////////////////////////////////////
 
         /** a node in the GSS */
-        final class Node extends FastSet<Node> implements Invokable<Position, Node, Node>, IntegerMappable {
+        final class Node implements Invokable<Position, Node, Node>, IntegerMappable, GraphViz.ToGraphViz {
+            public FastSet<Node> set = new FastSet<Node>();
+
+        public GraphViz.Node toGraphViz(GraphViz gv) {
+            if (gv.hasNode(this)) return gv.createNode(this);
+            GraphViz.Node n = gv.createNode(this);
+            n.label = ""+state.toStringx();
+            n.shape = "rectangle";
+            n.fill = "green";
+            //GraphViz.Node f = pending().toGraphViz(gv);
+            //n.add(f);
+            for(Forest result : results()) n.edge(result, "");
+            for(Node parent : parents()) n.edge(parent, "");
+            ((GraphViz.Group)phase().toGraphViz(gv)).add(n);
+            return n;
+        }
+        public boolean isTransparent() { return false; }
+        public boolean isHidden() { return false; }
 
-            private Forest.Ref holder = null;
             private boolean allqueued = false;
 
             /** what state this node is in */
@@ -278,9 +296,24 @@ class GSS {
 
             /** which Phase this Node belongs to (node that Node is also a non-static inner class of Phase) */
             public  Phase phase() { return Phase.this; }
-            public  Forest.Ref holder() { return holder==null ? (holder = new Forest.Ref()) : holder; }
-            public  Forest pending() { return Phase.this.closed ? holder().resolve() : holder; }
-            public  FastSet<Node> parents() { return this; }
+
+            private HashSet<Forest.Ref> resultMap = new HashSet<Forest.Ref>();
+            public Iterable<Forest.Ref> results() { return resultMap; }
+            public FastSet<Node> parents() { return set; }
+            public boolean merge(Node parent, Forest result) {
+                for(Forest.Ref f : results()) {
+                    if (f.parents.contains(parent) /* UGLY: */ && f.parents.size()==1) {
+                        f.merge(result);
+                        return true;
+                    }
+                }
+                Forest.Ref f = new Forest.Ref();
+                f.parents.add(parent);
+                f.merge(result);
+                resultMap.add(f);
+                set.add(parent, true);
+                return false;
+            }
 
             public void performReductions() {
                 if (allqueued) return;
@@ -303,7 +336,7 @@ class GSS {
                     if (n==null) return;
                     Forest[] holder = new Forest[r.pos];
                     if (r.pos==0) n.finish(r, r.zero(), n.phase(), holder);
-                    else                   n.reduce(r, r.pos-1, n.phase(), holder);
+                    else          n.reduce(r, r.pos-1,  n.phase(), holder, null);
                 } else {
                     Forest[] holder = new Forest[r.pos];
                     if (r.pos<=0) throw new Error("called wrong form of reduce()");
@@ -312,30 +345,22 @@ class GSS {
                 }
             }
 
-            public void reduce(Position r, int pos, Phase target, Forest[] holder) { reduce(r, pos, target, holder, null); }
             public void reduce(Position r, int pos, Phase target, Forest[] holder, Node only) {
                 Forest old = holder[pos];
-                holder[pos] = this.pending();
-                if (pos==0) {
-                    System.arraycopy(holder, 0, r.holder, 0, holder.length);
-                    for(int i=0; i<r.pos; i++) if (r.holder[i]==null) throw new Error("realbad");
-                    Forest rex = null;
-
-                    // FIXME: I'm unsure about this -- basically we want to deal with the case where
-                    //        there are two nodes, each of whose Ref points to the same Forest instance.
-                    //        Some node in the next phase has both of these as parents.  This might happen
-                    //        since the same reduction can appear in more than one state.
-                    if (r.pos==1)  rex = singularReductions.get(this.pending(), r);
-                    if (rex==null) {
-                        rex = r.rewrite(phase().getLocation());
-                        if (r.pos==1) singularReductions.put(this.pending(), r, rex);
+
+                for(Forest result : results())
+                    for(Node child : ((Forest.Ref<?>)result).parents) {
+                        if (only != null && child!=only) continue;
+                        holder[pos] = result;
+                        if (pos==0) {
+                            System.arraycopy(holder, 0, r.holder, 0, holder.length);
+                            for(int i=0; i<r.pos; i++) if (r.holder[i]==null) throw new Error("realbad");
+                            child.finish(r, r.rewrite(phase().getLocation()), target, holder);
+                        } else {
+                            child.reduce(r, pos-1, target, holder, null);
+                        }
                     }
-                    if (only != null)  only.finish(r, rex, target, holder);
-                    else               for(Node child : this.parents()) child.finish(r, rex, target, holder);
-                } else {
-                    if (only != null)  only.reduce(r, pos-1, target, holder);
-                    else               for(Node child : this.parents()) child.reduce(r, pos-1, target, holder);
-                }
+
                 holder[pos] = old;
             }
 
@@ -348,7 +373,7 @@ class GSS {
 
             private Node(Node parent, Forest pending, State state) {
                 this.state = state;
-                this.holder().merge(pending);
+                this.merge(parent, pending);
                 Phase start = parent==null ? null : parent.phase();
                 if (parent != null) parents().add(parent, true);
                 if (Phase.this.hash.get(state, start) != null) throw new Error("severe problem!");
@@ -361,6 +386,19 @@ class GSS {
 
         public int toInt() { return pos+1; }
         public int size() { return hash==null ? 0 : hash.size(); }
-    }
 
+        // GraphViz //////////////////////////////////////////////////////////////////////////////
+
+        public GraphViz.Node toGraphViz(GraphViz gv) {
+            if (gv.hasNode(this)) return gv.createNode(this);
+            GraphViz.Group g = gv.createGroup(this);
+            g.label = "Phase " + pos;
+            g.color = "gray";
+            g.cluster = true;
+            return g;
+        }
+        public boolean isTransparent() { return false; }
+        public boolean isHidden() { return false; }
+
+    }
 }