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

diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java
index 743cfd3..217889b 100644
--- a/src/edu/berkeley/sbp/GSS.java
+++ b/src/edu/berkeley/sbp/GSS.java
@@ -1,3 +1,5 @@
+// Copyright 2006 all rights reserved; see LICENSE file for BSD-style license
+
 package edu.berkeley.sbp;
 import edu.berkeley.sbp.*;
 import edu.berkeley.sbp.util.*;
@@ -10,25 +12,31 @@ import java.lang.reflect.*;
 /** implements Tomita's Graph Structured Stack */
 class GSS {
 
-    public static int count = 0;
+    static int count = 0;
+    static int shifts = 0;
+    static int reductions = 0;
+    int resets = 0;
+    int waits = 0;
+    
     public GSS() { }
 
     private Phase.Node[] reducing_list = null;
-    public int resets = 0;
-    public int waits = 0;
 
+    // FIXME: right now, these are the performance bottleneck
     HashMapBag<Sequence,Phase.Waiting> waiting         = new HashMapBag<Sequence,Phase.Waiting>();
     HashMapBag<Integer,Sequence>       performed       = new HashMapBag<Integer,Sequence>();
     HashMapBag<Integer,Sequence>       lastperformed   = new HashMapBag<Integer,Sequence>();
     HashMapBag<Integer,Sequence>       expected        = new HashMapBag<Integer,Sequence>();
     
     /** FIXME */
-    public  Forest.Ref finalResult;
+    Forest.Many 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) {
+            shifts++;
             good |= next.newNode(n, result, st, false);
         }
 
@@ -39,23 +47,24 @@ 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;
         private Phase prev;
         private Input.Location location;
+        private Input.Location nextLocation;
         public final Parser parser;
 
         private Forest forest;
 
-        public Phase(Phase prev, Parser parser, Phase previous, Tok token, Input.Location location, Forest forest) throws ParseFailed {
+        public Phase(Phase prev, Parser parser, Phase previous, Tok token, Input.Location location, Input.Location nextLocation, Forest forest) throws ParseFailed {
             this.prev = prev;
             this.forest = forest;
             this.parser = parser;
             this.pos = previous==null ? 0 : previous.pos+1;
             this.token = token;
             this.location = location;
+            this.nextLocation = nextLocation;
             performed.clear();
             reset();
         }
@@ -67,7 +76,6 @@ class GSS {
             lastperformed.addAll(performed);
             performed.clear();
             hash = new IntPairMap<Phase.Node>();
-            singularReductions = new IntPairMap<Forest>();
             reset = false;
             good = false;
             closed = false;
@@ -85,6 +93,7 @@ class GSS {
         }
 
         public Input.Location getLocation() { return location; }
+        public Input.Location getNextLocation() { return nextLocation; }
 
         /** add a new node (merging with existing nodes if possible)
          *  @param parent             the parent of the new node
@@ -129,8 +138,7 @@ class GSS {
                             }
                 }
             }
-            if (!owner.lame)
-                newNode(parent, pending, state, fromEmptyReduction);
+            newNode(parent, pending, state, fromEmptyReduction);
             if (reduction != null) {
                 boolean redo = true;
                 while(redo) {
@@ -146,13 +154,14 @@ 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.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 +225,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;
@@ -226,8 +234,9 @@ class GSS {
             boolean ok = false;
             for(Phase.Node n : hash.values()) {
                 if (token == null && n.state.isAccepting()) {
-                    if (finalResult==null) finalResult = new Forest.Ref();
-                    finalResult.merge(n.holder);
+                    if (finalResult==null) finalResult = new Forest.Many();
+                    for(Object f : n.results())
+                        finalResult.merge((Forest)f);
                 }
                 if (token == null) continue;
                 n.state.invokeShifts(token, this, result, n);
@@ -268,9 +277,10 @@ 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>();
 
-            private Forest.Ref holder = null;
+           
             private boolean allqueued = false;
 
             /** what state this node is in */
@@ -278,9 +288,25 @@ 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.Many> resultMap = new HashSet<Forest.Many>();
+            public Iterable<Forest.Many> results() { return resultMap; }
+            public FastSet<Node> parents() { return set; }
+            public boolean merge(Node parent, Forest result) {
+                // FIXME: inefficient!
+                for(Forest.Many f : results()) {
+                    if (f.parents.contains(parent) /* UGLY: */ && f.parents.size()==1) {
+                        f.merge(result);
+                        return true;
+                    }
+                }
+                Forest.Many f = new Forest.Many();
+                f.parents.add(parent);
+                f.merge(result);
+                resultMap.add(f);
+                set.add(parent, true);
+                return false;
+            }
 
             public void performReductions() {
                 if (allqueued) return;
@@ -295,6 +321,7 @@ class GSS {
 
             public void performEmptyReductions() { state.invokeReductions(token, this, null, null); }
             public final void invoke(Position r, Node n, Node n2) {
+                reductions++;
                 if (n==null || n2==null || r.pos==0) {
                     if (r.pos==0) {
                         if (n==null) n = this;
@@ -302,44 +329,33 @@ 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);
+                    if (r.pos==0) n.finish(r, r.zero(n.phase().getLocation().createRegion(n.phase().getLocation())), n.phase());
+                    else          n.reduce(r, r.pos-1,  n.phase(), null);
                 } 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(), n2);
                 }
             }
 
-            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) {
+            public void reduce(Position r, int pos, Phase target, Node only) {
+                Forest[] holder = r.holder;
                 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);
+
+                HashSet<Forest> rr = new HashSet<Forest>();
+                for(Forest result : results()) rr.add(result);
+                for(Forest result : rr)
+                    for(Node child : ((Forest.Many<?>)result).parents) {
+                        if (only != null && child!=only) continue;
+                        holder[pos] = result;
+                        if (pos==0) child.finish(r, r.rewrite(child.phase().getNextLocation().createRegion(target.getLocation())), target);
+                        else        child.reduce(r, pos-1, target, 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;
             }
 
-            public void finish(Position r, Forest result, Phase<Tok> target, Forest[] holder) {
+            public void finish(Position r, Forest result, Phase<Tok> target) {
                 Parser.Table<Tok>.State<Tok> state0 = state.gotoSetNonTerminals.get(r.owner());
                 if (result==null) throw new Error();
                 if (state0!=null)
@@ -348,7 +364,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!");
@@ -356,11 +372,41 @@ class GSS {
             }
             public int toInt() { return idx; }
             private final int idx = node_idx++;
+
+            // GraphViz //////////////////////////////////////////////////////////////////////////////
+
+            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";
+                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 int node_idx = 0;
 
         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; }
+
+    }
 }