X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FGSS.java;h=2e573486c9e8d3ff80cd13cfabb5d24ad489fed1;hp=7c1fb19f1e8bab3c2ac62ea828f7e5953790dca9;hb=c53fc2952c7885d727500ce404887d552c5dec5f;hpb=93b9f1a57460257f71a4cef17419a723e294550d

diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java
index 7c1fb19..2e57348 100644
--- a/src/edu/berkeley/sbp/GSS.java
+++ b/src/edu/berkeley/sbp/GSS.java
@@ -18,13 +18,16 @@ class GSS {
     public GSS(Input input, Parser parser) { this.input = input; this.parser = parser;}
     public Input getInput() { return input; }
 
+    /*
+    HashSet<Reduction> finishedReductions = new HashSet<Reduction>();
+    */
     int numNewNodes = 0;
     int numOldNodes = 0;
     int viewPos = 0;
     int numReductions = 0;
 
     /** corresponds to a positions <i>between tokens</i> the input stream; same as Tomita's U_i's */
-    class Phase<Tok> implements Invokable<State, Result>, IntegerMappable, GraphViz.ToGraphViz, Iterable<Node> {
+    class Phase<Tok> implements Invokable<State, StateNode, Forest>, IntegerMappable, GraphViz.ToGraphViz, Iterable<StateNode> {
 
         // FIXME: right now, these are the performance bottleneck
         private HashMapBag<Integer,Integer>       performed       = new HashMapBag<Integer,Integer>();
@@ -38,16 +41,16 @@ class GSS {
             parser.spin();
             reductionQueue.add(r);
         }
-        public void invoke(State st, Result result) {
+
+        public void invoke(State st, StateNode pred, Forest f) {
             parser.spin();
-            good |= next.newNode(result, st, false);
+            good |= next.newNode(f, null, pred, st, false);
         }
 
         /** the token immediately after this phase */
         final Tok token;
         final int pos;
-
-        public IntPairMap<Node> hash = new IntPairMap<Node>();  /* ALLOC */
+        public IntPairMap<StateNode> hash = new IntPairMap<StateNode>();  /* ALLOC */
         private boolean good = false;
         private Phase next = null;
         private Phase prev;
@@ -58,8 +61,7 @@ class GSS {
 
         public Phase(State startState) throws ParseFailed, IOException {
             this(null, null);
-            Result primordealResult = new Result(null, null, null);
-            newNode(primordealResult, startState, true);
+            newNode(null, null, null, startState, true);
         }
         public Phase(Phase prev, Forest forest) throws ParseFailed, IOException {
             this.location = input.getLocation();
@@ -70,6 +72,9 @@ class GSS {
             this.pos = prev==null ? 0 : prev.pos+1;
             if (prev != null) prev.shift(this, forest);
             numReductions = 0;
+            /*
+            finishedReductions.clear();
+            */
 
             int minPhasePos = Integer.MAX_VALUE;
             Reduction best = null;
@@ -77,15 +82,15 @@ class GSS {
             while(!reductionQueue.isEmpty()) {
                 Reduction r = reductionQueue.poll();
                 //System.out.println("- " + r);
-                if (r.parentPhase() != null)
-                    if (r.parentPhase().pos > minPhasePos)
+                if (r.predPhase() != null)
+                    if (r.predPhase().pos > minPhasePos)
                         throw new Error();
                 r.perform();
-                if (r.parentPhase() != null) {
-                    if (r.parentPhase().pos < minPhasePos) {
-                        minPhasePos = r.parentPhase().pos;
+                if (r.predPhase() != null) {
+                    if (r.predPhase().pos < minPhasePos) {
+                        minPhasePos = r.predPhase().pos;
                         best = r;
-                    } else if (r.parentPhase().pos == minPhasePos) {
+                    } else if (r.predPhase().pos == minPhasePos) {
                         /*
                         if (best != null && Parser.mastercache.comparePositions(r.reduction(), best.reduction()) < 0)
                             throw new Error("\n"+r+"\n"+best+"\n"+
@@ -95,6 +100,9 @@ class GSS {
                         best = r;
                     }
                 }
+                /*
+                finishedReductions.add(r);
+                */
                 numReductions++;
             }
             if (token==null) shift(null, null);
@@ -113,27 +121,28 @@ class GSS {
         public boolean        isFrontier() { return hash!=null; }
 
         /** perform all shift operations, adding promoted nodes to <tt>next</tt> */
-        private void shift(Phase next, Forest result) throws ParseFailed {
+        private void shift(Phase next, Forest f) throws ParseFailed {
             this.next = next;
             // this massively improves GC performance
             if (prev != null) {
-                IntPairMap<Node> h = prev.hash;
+                IntPairMap<StateNode> h = prev.hash;
                 prev.hash = null;
                 prev.performed = null;
-                for(Node n : h) n.check();
+                for(StateNode n : h) n.check();
             }
             numOldNodes = hash.size();
-            for(Node n : hash.values()) {
+            for(StateNode n : hash.values()) {
                 if (token == null && n.state().isAccepting()) {
                     if (finalResult==null) finalResult = new Forest.Many();
-                    for(Result r : n)
+                    for(ResultNode r : n)
                         finalResult.merge(r.getForest());
                 }
                 if (token == null) continue;
-                n.state().invokeShifts(token, this, new Result(result, n, null));
+                n.state().invokeShifts(token, this, n, f);
             }
             numNewNodes = next==null ? 0 : next.hash.size();
             viewPos = this.pos;
+
             if (!good && token!=null) {
                 String toks = token+"";
                 if (toks.length()==1 && toks.charAt(0) == edu.berkeley.sbp.chr.CharAtom.left) {
@@ -151,15 +160,15 @@ class GSS {
             if (token==null && finalResult==null)
                 ParseFailed.error("unexpected end of file", this, null,
                                   getLocation().createRegion(getLocation()));
-            for(Node n : hash) n.check();
+            for(StateNode n : hash) n.check();
         }
 
         Input.Region getRegionFromThisToNext() {
             return getLocation().createRegion(getNextLocation());
         }
 
-        void newNodeFromReduction(Result result, State state, Pos reduction) {
-            int pos = result.phase().pos;
+        void newNodeFromReduction(Forest f, Pos reduction, StateNode pred) {
+            int pos = pred.phase().pos;
             for(int s : reduction.hates())
                 if (performed.contains(pos, s))
                     return;
@@ -168,8 +177,9 @@ class GSS {
                     return;
             if (reduction.owner_needed_or_hated() && !performed.contains(pos, reduction.provides()))
                 performed.add(pos, reduction.provides());
+            Parser.Table.State state = (Parser.Table.State)pred.state().gotoSetNonTerminals.get(reduction);
             if (state!=null)
-                newNode(result, state, reduction.numPops()<=0);
+                newNode(f, reduction, pred, state, reduction.numPops()<=0);
         }
 
         /** add a new node (merging with existing nodes if possible)
@@ -179,18 +189,22 @@ class GSS {
          *  @param fromEmptyReduction true iff this node is being created as a result of a reduction of length zero (see GRMLR paper)
          *  @param start              the earliest part of the input contributing to this node (used to make merging decisions)
          */
-        private boolean newNode(Result result, State state, boolean fromEmptyReduction) {
-            Node p = hash.get(state, result.phase());
-            if (p != null) { p.addResult(result); return !state.doomed(); }
+        private boolean newNode(Forest f, Pos reduction, StateNode pred, State state, boolean fromEmptyReduction) {
+            StateNode p = pred==null ? null : hash.get(state, pred.phase());
+            if (p != null) {
+                p.addResult(f, reduction, pred);
+                return !state.doomed();
+            }
             do {
                 if (token != null && state.canShift(token)) break;
                 if (state.isAccepting()) break;
                 if (token==null) break;
                 if (!state.canReduce(token)) return false;
             } while(false);
-            Node n = new Node(Phase.this, result, state, fromEmptyReduction);  // ALLOC
+            StateNode n = new StateNode(Phase.this, f, reduction, pred, state, fromEmptyReduction);  // ALLOC
+            /** FIXME: this null-result can be used to notice bogus/dead states */
             for(Object s : state.conjunctStates)
-                newNode(new Result(null, n, null), (State)s, fromEmptyReduction);
+                newNode(null, null, n, (State)s, fromEmptyReduction);
             return !n.state().doomed();
         }
 
@@ -198,12 +212,12 @@ class GSS {
         public int size() { return hash==null ? 0 : hash.size(); }
         public int pos() { return pos; }
         public Tok getToken() { return token; }
-        public Iterator<Node> iterator() { return hash.iterator(); }
+        public Iterator<StateNode> iterator() { return hash.iterator(); }
         public GSS getGSS() { return GSS.this; }
 
         // GraphViz //////////////////////////////////////////////////////////////////////////////
 
-        public GraphViz.Node toGraphViz(GraphViz gv) {
+        public GraphViz.StateNode toGraphViz(GraphViz gv) {
             if (gv.hasNode(this)) return gv.createNode(this);
             GraphViz.Group g = gv.createGroup(this);
             g.label = "Phase " + pos;
@@ -219,7 +233,7 @@ class GSS {
             PrintWriter p = new PrintWriter(new OutputStreamWriter(fos));
             GraphViz gv = new GraphViz();
             for(Object n : this)
-                ((Node)n).toGraphViz(gv);
+                ((StateNode)n).toGraphViz(gv);
             gv.dump(p);
             p.flush();
             p.close();