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

diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java
index 743cfd3..80fbd5c 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);
         }
@@ -147,8 +149,8 @@ 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;
+            p.merge(parent, pending);
             p.parents().add(parent, true);
             if (p!=parent && !fromEmptyReduction && reducing) p.performReductions(parent);
             return true;
@@ -216,7 +218,7 @@ 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;
             }
@@ -227,7 +229,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 +271,27 @@ 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 Forest.Ref holder = new Forest.Ref();
             private boolean allqueued = false;
 
             /** what state this node is in */
@@ -278,9 +299,28 @@ 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 Forest pending() { return !Phase.this.closed ? holder : holder.resolve(); }
+            private HashMap<Node,Forest> resultMap = new HashMap<Node,Forest>();
+            public void merge(Node parent, Forest result) {
+                //holder.merge(result);
+                Forest.Ref f = (Forest.Ref)resultMap.get(parent);
+                if (f==null) { f = new Forest.Ref(); resultMap.put(parent, f); }
+                f.merge(result);
+                set.add(parent, true);
+            }
+            //public Iterable<Node> childrenFor(Forest result) { return resultMap.getAll(result); }
+            public Iterable<Forest> results() { return resultMap.values(); }
+            private Forest pending(Node n) {
+                //return !Phase.this.closed ? holder : holder.resolve();
+                /*
+                for(Forest f : resultMap)
+                    if (resultMap.contains(f, n))
+                        return f;
+                return null;
+                */
+                return resultMap.get(n);
+            }
+            public  FastSet<Node> parents() { return set; }
 
             public void performReductions() {
                 if (allqueued) return;
@@ -295,6 +335,7 @@ class GSS {
 
             public void performEmptyReductions() { state.invokeReductions(token, this, null, null); }
             public final void invoke(Position r, Node n, Node n2) {
+                //if (r.owner().lame) return;
                 if (n==null || n2==null || r.pos==0) {
                     if (r.pos==0) {
                         if (n==null) n = this;
@@ -303,38 +344,70 @@ 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, n.pending(n));
                 } else {
                     Forest[] holder = new Forest[r.pos];
                     if (r.pos<=0) throw new Error("called wrong form of reduce()");
                     int pos = r.pos-1;
-                    n.reduce(r, pos, n.phase(), holder, n2);
+                    n.reduce(r, pos, n.phase(), holder, n2, n.pending(n));
                 }
             }
 
-            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) {
+                reduce(r, pos, target, holder, null); }
             public void reduce(Position r, int pos, Phase target, Forest[] holder, Node only) {
+                reduce(r, pos, target, holder, only, this.pending());
+            }
+            */
+            public void reduce(Position r, int pos, Phase target, Forest[] holder, Node only, Forest pending) {
                 Forest old = holder[pos];
-                holder[pos] = this.pending();
+                holder[pos] = 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);
+
+                    if (only != null)  {
+                        holder[pos] = pending(only);
+                        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;
+                        if (r.pos==1)  rex = singularReductions.get(pending, r);
+                        if (rex==null) {
+                            rex = r.rewrite(phase().getLocation());
+                            if (r.pos==1) singularReductions.put(pending, r, rex);
+                        }
+                        only.finish(r, rex, target, holder);
+                    } else {
+                        for(Forest result : results()) {
+                            pending = holder[pos] = result;
+                            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;
+                            if (rex==null && r.pos==1)  rex = singularReductions.get(pending, r);
+                            if (rex==null) {
+                                rex = r.rewrite(phase().getLocation());
+                                if (r.pos==1) singularReductions.put(pending, r, rex);
+                            }
+                            for(Node child : parents()) {
+                                if (pending(child)==result)
+                                    child.finish(r, rex, target, holder);
+                            }
+                        }
                     }
-                    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);
+                    if (only != null)  {
+                        holder[pos] = pending(only);
+                        only.reduce(r, pos-1, target, holder, null, only.pending(only));
+                    } else {
+                        for(Node child : this.parents()) {
+                            holder[pos] = pending(child);
+                            child.reduce(r, pos-1, target, holder, null, child.pending(child));
+                        }
+                    }
                 }
                 holder[pos] = old;
             }
@@ -348,7 +421,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 +434,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; }
+
+    }
 }