major overhaul to institute optimal GSS sharing

darcs-hash:20070909190629-5007d-5431d8ece0f68d075d546b30b4498db67a63e3de.gz

diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java
index bf58e64..3876d58 100644 (file)
--- a/src/edu/berkeley/sbp/GSS.java
+++ b/src/edu/berkeley/sbp/GSS.java
@@ -24,7 +24,7 @@ class GSS {
     int numReductions = 0;
 
     /** corresponds to a positions <i>between tokens</i> the input stream; same as Tomita's U_i's */
     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, Node, Forest>, IntegerMappable, GraphViz.ToGraphViz, Iterable<Node> {

 
         // FIXME: right now, these are the performance bottleneck
         private HashMapBag<Integer,Integer>       performed       = new HashMapBag<Integer,Integer>();
 
         // FIXME: right now, these are the performance bottleneck
         private HashMapBag<Integer,Integer>       performed       = new HashMapBag<Integer,Integer>();

@@ -38,15 +38,15 @@ class GSS {
             parser.spin();
             reductionQueue.add(r);
         }
             parser.spin();
             reductionQueue.add(r);
         }

-        public void invoke(State st, Result result) {
+
+        public void invoke(State st, Node pred, Forest f) {

             parser.spin();
             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;
         }
 
         /** the token immediately after this phase */
         final Tok token;
         final int pos;

-

         public IntPairMap<Node> hash = new IntPairMap<Node>();  /* ALLOC */
         private boolean good = false;
         private Phase next = null;
         public IntPairMap<Node> hash = new IntPairMap<Node>();  /* ALLOC */
         private boolean good = false;
         private Phase next = null;

@@ -58,8 +58,7 @@ class GSS {
 
         public Phase(State startState) throws ParseFailed, IOException {
             this(null, null);
 
         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();
         }
         public Phase(Phase prev, Forest forest) throws ParseFailed, IOException {
             this.location = input.getLocation();

@@ -130,11 +129,11 @@ class GSS {
                         finalResult.merge(r.getForest());
                 }
                 if (token == null) continue;
                         finalResult.merge(r.getForest());
                 }
                 if (token == null) continue;

-                Result result = new Result(f, n, null);
-                n.state().invokeShifts(token, this, result);
+                n.state().invokeShifts(token, this, n, f);

             }
             numNewNodes = next==null ? 0 : next.hash.size();
             viewPos = this.pos;
             }
             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) {
             if (!good && token!=null) {
                 String toks = token+"";
                 if (toks.length()==1 && toks.charAt(0) == edu.berkeley.sbp.chr.CharAtom.left) {

@@ -159,8 +158,8 @@ class GSS {
             return getLocation().createRegion(getNextLocation());
         }
 
             return getLocation().createRegion(getNextLocation());
         }
 

-        void newNodeFromReduction(Result result, State state, Pos reduction) {
-            int pos = result.phase().pos;
+        void newNodeFromReduction(Forest f, Pos reduction, Node pred) {
+            int pos = pred.phase().pos;

             for(int s : reduction.hates())
                 if (performed.contains(pos, s))
                     return;
             for(int s : reduction.hates())
                 if (performed.contains(pos, s))
                     return;

@@ -169,8 +168,9 @@ class GSS {
                     return;
             if (reduction.owner_needed_or_hated() && !performed.contains(pos, reduction.provides()))
                 performed.add(pos, reduction.provides());
                     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)
             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)
         }
 
         /** add a new node (merging with existing nodes if possible)

@@ -180,19 +180,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)
          */
          *  @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, Node pred, State state, boolean fromEmptyReduction) {
+            Node 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);
             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
+            Node n = new Node(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)
             /** 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();
         }
 
             return !n.state().doomed();
         }
 

diff --git a/src/edu/berkeley/sbp/Node.java b/src/edu/berkeley/sbp/Node.java
index 6fe6a74..8353384 100644 (file)
--- a/src/edu/berkeley/sbp/Node.java
+++ b/src/edu/berkeley/sbp/Node.java
@@ -12,7 +12,7 @@ import java.lang.reflect.*;
 
 /** a node in the GSS */
 final class Node
 
 /** a node in the GSS */
 final class Node

-    implements Invokable<Pos, Result>,
+    implements Invokable<Pos, Result, Object>,

                IntegerMappable,
                GraphViz.ToGraphViz,
                Iterable<Result> {
                IntegerMappable,
                GraphViz.ToGraphViz,
                Iterable<Result> {

@@ -45,7 +45,7 @@ final class Node
         while(successors.size()>0)
             for(Result r : successors) {
                 successors.remove(r);
         while(successors.size()>0)
             for(Result r : successors) {
                 successors.remove(r);

-                r.destroy();
+                r.removePred(this);

                 break;
             }
         while(results.size()>0)
                 break;
             }
         while(results.size()>0)

@@ -64,70 +64,85 @@ final class Node
     private final int idx = node_idx++;
 
     private final GSS.Phase phase;
     private final int idx = node_idx++;
 
     private final GSS.Phase phase;

+    private final GSS.Phase predPhase;

     private final Parser.Table.State state;
     private final Parser.Table.State state;

-    private final boolean fromEmptyReduction;
-    //private       FastSet<Result> results = new FastSet<Result>();
-    private       HashSet<Result> results = new HashSet<Result>();
-    private       HashSet<Result> successors = new HashSet<Result>();
+    private  boolean fromEmptyReduction;
+    private       FastSet<Result> results = new FastSet<Result>();
+    private       FastSet<Result> successors = new FastSet<Result>();
+    //private       HashSet<Result> results = new HashSet<Result>();
+    //private       HashSet<Result> successors = new HashSet<Result>();

 
 

-    public final void invoke(Pos r, Result only) {
+    public final void invoke(Pos r, Result only, Object o) {

         boolean emptyProductions = only==null;
         if (emptyProductions != (r.numPops()==0)) return;
         if (r.numPops()!=0)  reduce(r, r.numPops()-1, phase(), only);
         else {
             Input.Region region = phase().getLocation().createRegion(phase().getLocation());
         boolean emptyProductions = only==null;
         if (emptyProductions != (r.numPops()==0)) return;
         if (r.numPops()!=0)  reduce(r, r.numPops()-1, phase(), only);
         else {
             Input.Region region = phase().getLocation().createRegion(phase().getLocation());

-            Result.newResult(r.rewrite(region), this, r, phase());
+            phase().newNodeFromReduction(r.rewrite(region), r, this);

         }
     }
 
     private void reduce(Pos r, int pos, GSS.Phase target, Result only) {
         }
     }
 
     private void reduce(Pos r, int pos, GSS.Phase target, Result only) {

-        Forest[] holder = r.holder;
-        Forest old = holder[pos];
-        if (results==null) return;   // FIXME: this should not happen

         for(Result res : results)
         for(Result res : results)

-            if (only == null || res == only) {
-                Node pred = res.pred();
-                holder[pos] = res.getForest();
-                if (pos>0)  pred.reduce(r, pos-1, target, null);
-                else {
-                    Input.Region region = pred.phase().getLocation().createRegion(target.getLocation());
-                    new Reduction(pred, r, r.rewrite(region), target);
-                }
-            }
-        holder[pos] = old;
+            if (only == null || res == only)
+                for(Node pred : res.getPreds())
+                    reduce2(r, pos, target, pred, res.getForest());

     }
 
     }
 

+    void reduce2(Pos r, int pos, GSS.Phase target, Node pred, Forest f) {
+        Forest[] holder = r.holder;
+        Forest old = pos >= holder.length ? null : holder[pos];
+        if (pos < holder.length) holder[pos] = f;
+        if (pos>0)  pred.reduce(r, pos-1, target, null);
+        else {
+            Input.Region region = pred.phase().getLocation().createRegion(target.getLocation());
+            new Reduction(pred, r, r.rewrite(region), target);
+        }
+        if (pos < holder.length) holder[pos] = old;
+    }
+
+    Node(GSS.Phase phase, Forest f, Pos reduction, Node pred, State state, boolean fromEmptyReduction) {
+        this(phase, new Result(f, reduction, pred), state, fromEmptyReduction);
+    }

     Node(GSS.Phase phase, Result pred, State state, boolean fromEmptyReduction) {
         this.phase = phase;
         this.state = state;
         this.fromEmptyReduction = fromEmptyReduction;
         if (phase.hash.get(state, pred.phase()) != null) throw new Error("severe problem!");
     Node(GSS.Phase phase, Result pred, State state, boolean fromEmptyReduction) {
         this.phase = phase;
         this.state = state;
         this.fromEmptyReduction = fromEmptyReduction;
         if (phase.hash.get(state, pred.phase()) != null) throw new Error("severe problem!");

+        this.predPhase = pred.phase();

         phase.hash.put(state, pred.phase(), this);
         phase.hash.put(state, pred.phase(), this);

-        addResult(pred);
+
+        results.add(pred);
+        pred.addSucc(this);
+        if (!fromEmptyReduction)
+            state.invokeReductions(phase().getToken(), this, pred);
+

         state.invokeEpsilonReductions(phase().token, this);
     }
 
     // Add/Remove Successors/Results //////////////////////////////////////////////////////////////////////////////
 
     public void removeSucc(Result succ)   {
         state.invokeEpsilonReductions(phase().token, this);
     }
 
     // Add/Remove Successors/Results //////////////////////////////////////////////////////////////////////////////
 
     public void removeSucc(Result succ)   {

-        if (successors==null) return;

         successors.remove(succ);
         check();
     }
     public void removeResult(Result result) {
         successors.remove(succ);
         check();
     }
     public void removeResult(Result result) {

-        if (results==null) return;

         results.remove(result);
         check();
     }
     public void addSucc(Result succ)      {
         results.remove(result);
         check();
     }
     public void addSucc(Result succ)      {

-        if (successors==null) return;   // FIXME: this should not happen

         successors.add(succ);
     }
         successors.add(succ);
     }

-    public void addResult(Result r) {
-        if (results.contains(r)) return;
-        results.add(r);
-        r.addSucc(this);
-        if (!fromEmptyReduction) state.invokeReductions(phase().getToken(), this, r);
+    public void addResult(Forest f, Pos reduction, Node pred) {
+        for(Result r : results)
+            if (r.predecessorsContains(pred)) {
+                r.merge(f);
+                return;
+            }
+        Result result = new Result(f, reduction, pred);
+        results.add(result);
+        result.addSucc(this);
+        if (!this.fromEmptyReduction) state.invokeReductions(phase().getToken(), this, result);

     }
 
     // GraphViz //////////////////////////////////////////////////////////////////////////////
     }
 
     // GraphViz //////////////////////////////////////////////////////////////////////////////

diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java
index 6b9bad7..2fc0691 100644 (file)
--- a/src/edu/berkeley/sbp/Parser.java
+++ b/src/edu/berkeley/sbp/Parser.java
@@ -273,8 +273,8 @@ public abstract class Parser<Token, NodeType> implements Serializable {
             HashMap<Pos,State<Token>>      gotoSetNonTerminals = new HashMap<Pos,State<Token>>();
             private transient TopologicalBag<Token,State<Token>>  gotoSetTerminals    = new TopologicalBag<Token,State<Token>>();
 
             HashMap<Pos,State<Token>>      gotoSetNonTerminals = new HashMap<Pos,State<Token>>();
             private transient TopologicalBag<Token,State<Token>>  gotoSetTerminals    = new TopologicalBag<Token,State<Token>>();
 

-            private           TopologicalBag<Token,Pos>      reductions          = new TopologicalBag<Token,Pos>();
-            private           HashSet<Pos>                   eofReductions       = new HashSet<Pos>();
+                       TopologicalBag<Token,Pos>      reductions          = new TopologicalBag<Token,Pos>();
+                       HashSet<Pos>                   eofReductions       = new HashSet<Pos>();

             private           TopologicalBag<Token,State<Token>>  shifts              = new TopologicalBag<Token,State<Token>>();
             private           boolean                             accept              = false;
 
             private           TopologicalBag<Token,State<Token>>  shifts              = new TopologicalBag<Token,State<Token>>();
             private           boolean                             accept              = false;
 

@@ -290,16 +290,16 @@ public abstract class Parser<Token, NodeType> implements Serializable {
             Iterable<Pos>  positions()             { return hs; }
 
             boolean                    canShift(Token t)       { return oshifts!=null && oshifts.contains(t); }
             Iterable<Pos>  positions()             { return hs; }
 
             boolean                    canShift(Token t)       { return oshifts!=null && oshifts.contains(t); }

-            void                       invokeShifts(Token t, GSS.Phase phase, Result r) { oshifts.invoke(t, phase, r); }
+            void                       invokeShifts(Token t, GSS.Phase phase, Node pred, Forest f) { oshifts.invoke(t, phase, pred, f); }

             boolean                    canReduce(Token t)        {
                 return oreductions != null && (t==null ? eofReductions.size()>0 : oreductions.contains(t)); }
             void          invokeEpsilonReductions(Token t, Node node) {
             boolean                    canReduce(Token t)        {
                 return oreductions != null && (t==null ? eofReductions.size()>0 : oreductions.contains(t)); }
             void          invokeEpsilonReductions(Token t, Node node) {

-                if (t==null) for(Pos r : eofReductions) node.invoke(r, null);
-                else         oreductions.invoke(t, node, null);
+                if (t==null) for(Pos r : eofReductions) node.invoke(r, null, null);
+                else         oreductions.invoke(t, node, null, null);

             }
             void          invokeReductions(Token t, Node node, Result b) {
             }
             void          invokeReductions(Token t, Node node, Result b) {

-                if (t==null) for(Pos r : eofReductions) node.invoke(r, b);
-                else         oreductions.invoke(t, node, b);
+                if (t==null) for(Pos r : eofReductions) node.invoke(r, b, null);
+                else         oreductions.invoke(t, node, b, null);

             }
 
             // Constructor //////////////////////////////////////////////////////////////////////////////
             }
 
             // Constructor //////////////////////////////////////////////////////////////////////////////

diff --git a/src/edu/berkeley/sbp/Reduction.java b/src/edu/berkeley/sbp/Reduction.java
index 4ef2013..222a168 100644 (file)
--- a/src/edu/berkeley/sbp/Reduction.java
+++ b/src/edu/berkeley/sbp/Reduction.java
@@ -41,7 +41,8 @@ final class Reduction implements Comparable<Reduction> {
     }
 
     public void perform() {
     }
 
     public void perform() {

-        Result.newResult(forest, pred, reduction, phase);
+        if (reduction==null) return;
+        phase.newNodeFromReduction(forest, reduction, pred);

     }
     public GSS.Phase predPhase() { return pred.phase(); }
     public Pos reduction() { return reduction; }
     }
     public GSS.Phase predPhase() { return pred.phase(); }
     public Pos reduction() { return reduction; }

diff --git a/src/edu/berkeley/sbp/Result.java b/src/edu/berkeley/sbp/Result.java
index 97f467f..c91ab76 100644 (file)
--- a/src/edu/berkeley/sbp/Result.java
+++ b/src/edu/berkeley/sbp/Result.java
@@ -8,19 +8,41 @@ import java.util.*;
 
 final class Result implements GraphViz.ToGraphViz {
 
 
 final class Result implements GraphViz.ToGraphViz {
 

-    private Forest f;
-    private Node pred;
-    private HashSet<Node> successors = new HashSet<Node>();
+    private Forest.Many f = new Forest.Many();
+    //private HashSet<Node> predecessors = new HashSet<Node>();
+    //private HashSet<Node> successors = new HashSet<Node>();
+    private FastSet<Node> predecessors = new FastSet<Node>();
+    private FastSet<Node> successors = new FastSet<Node>();

     private boolean destroyed = false;
     private boolean destroyed = false;

+    private boolean primordeal;

     private int usedByNonDoomedNode = 0;
     private Pos reduction;
     private int usedByNonDoomedNode = 0;
     private Pos reduction;

+    private GSS.Phase predPhase;

 
 

-    public GSS.Phase phase() { return pred==null ? null : pred.phase(); }
+    public boolean predecessorsContains(Node n) {
+        return predecessors.contains(n);
+    }
+    public Pos reduction() { return reduction; }
+    public void merge(Forest newf) {
+        this.f.merge(newf);
+        /*
+        if (predecessors.contains(pred)) return;
+        addPred(pred);
+        if (fromEmptyReduction) return;
+        n.state().invokeReductions(n.phase().getToken(), n, this);        
+        */
+    }
+
+    public boolean noSuccessors() { return successors.size()==0; }
+
+    public GSS.Phase phase() { return predPhase; }

     public Forest getForest() { return f; }
     public Forest getForest() { return f; }

-    public Node pred() { return pred; }
+    public Iterable<Node> getPreds() { return predecessors; }

     public void addSucc(Node succ) {
     public void addSucc(Node succ) {

+        if (successors.contains(succ)) return;

         successors.add(succ);
         usedByNonDoomedNode += succ.state().doomed ? 0 : 1;
         successors.add(succ);
         usedByNonDoomedNode += succ.state().doomed ? 0 : 1;

+        if (predecessors.size() > 1) throw new Error();

     }
     public void removeSucc(Node succ) {
         if (!successors.contains(succ)) return;
     }
     public void removeSucc(Node succ) {
         if (!successors.contains(succ)) return;

@@ -32,33 +54,54 @@ final class Result implements GraphViz.ToGraphViz {
     public boolean usedByAnyNode() { return successors.size() > 0; }
     public boolean usedByNonDoomedNode() { return usedByNonDoomedNode > 0; }
 
     public boolean usedByAnyNode() { return successors.size() > 0; }
     public boolean usedByNonDoomedNode() { return usedByNonDoomedNode > 0; }
 

-    public String toString() { return super.toString()+"->"+pred(); }
+    public String toString() { return super.toString()+"->"+predPhase; }

 
 

-    public void check() { if (successors.size()==0) destroy(); }
+    public void check() {
+        if (successors.size()==0) destroy();
+        else if (predecessors.size()==0) destroy();
+    }

     public void destroy() {
         if (destroyed) return;
     public void destroy() {
         if (destroyed) return;

-        if (pred==null) return;  // never destroy the "primordeal" result
+        if (primordeal) return;  // never destroy the "primordeal" result

         destroyed = true;
         destroyed = true;

-        pred.removeSucc(this);
+        while(predecessors.size() > 0)
+            for(Node pred : predecessors) {
+                removePred(pred);
+                pred.removeSucc(this);
+                break;
+            }
+        predecessors = null;

         while(successors.size() > 0)
         while(successors.size() > 0)

-            for(Node n : successors) {
-                removeSucc(n);
-                n.removeResult(this);
+            for(Node succ : successors) {
+                removeSucc(succ);
+                succ.removeResult(this);

                 break;
             }
                 break;
             }

+        successors = null;

     }
 
     }
 

-    public static void newResult(Forest f, Node pred, Pos reduction, GSS.Phase target) {
-        Result r = new Result(f, pred, reduction);
-        if (reduction == null) return;
-        Parser.Table.State state0 = (Parser.Table.State)pred.state().gotoSetNonTerminals.get(reduction);
-        target.newNodeFromReduction(r, state0, reduction);
+    public void removePred(Node pred) {
+        if (!predecessors.contains(pred)) return;
+        predecessors.remove(pred);
+        check();
+    }
+
+    public void addPred(Node pred) {
+        if (predPhase==null) predPhase = pred.phase();
+        if (predPhase != pred.phase()) throw new Error();
+        predecessors.add(pred);
+        pred.addSucc(this);
+        if (predecessors.size() > 1) throw new Error();
+    }
+        
+    public Result() {
+        this(null, null, null);
+        this.primordeal = true;

     }
     }

-    public Result(Forest f, Node pred, Pos reduction) {
-        this.f = f;
-        this.pred = pred;
+    public Result(Forest f, Pos reduction, Node pred) {
+        this.f.merge(f);

         this.reduction = reduction;
         this.reduction = reduction;

-        if (pred != null) pred.addSucc(this);
+        if (pred != null) addPred(pred);

     }
 
     // GraphViz //////////////////////////////////////////////////////////////////////////////
     }
 
     // GraphViz //////////////////////////////////////////////////////////////////////////////

@@ -68,7 +111,7 @@ final class Result implements GraphViz.ToGraphViz {
         GraphViz.Node n = gv.createNode(this);
         n.label = ""+f;
         n.shape = "rectangle";
         GraphViz.Node n = gv.createNode(this);
         n.label = ""+f;
         n.shape = "rectangle";

-        if (pred()!=null) n.edge(pred, "");
+        //if (pred()!=null) n.edge(pred, "");

         n.color = "blue";
         if (phase() != null)
             ((GraphViz.Group)phase().toGraphViz(gv)).add(n);
         n.color = "blue";
         if (phase() != null)
             ((GraphViz.Group)phase().toGraphViz(gv)).add(n);