major overhaul to institute optimal GSS sharing

[sbp.git] / src / edu / berkeley / sbp / Node.java

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
-    implements Invokable<Pos, Result>,
+    implements Invokable<Pos, Result, Object>,
                IntegerMappable,
                GraphViz.ToGraphViz,
                Iterable<Result> {
@@ -45,7 +45,7 @@ final class Node
         while(successors.size()>0)
             for(Result r : successors) {
                 successors.remove(r);
-                r.destroy();
+                r.removePred(this);
                 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 GSS.Phase predPhase;
     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());
-            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) {
-        Forest[] holder = r.holder;
-        Forest old = holder[pos];
-        if (results==null) return;   // FIXME: this should not happen
         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!");
+        this.predPhase = pred.phase();
         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)   {
-        if (successors==null) return;
         successors.remove(succ);
         check();
     }
     public void removeResult(Result result) {
-        if (results==null) return;
         results.remove(result);
         check();
     }
     public void addSucc(Result succ)      {
-        if (successors==null) return;   // FIXME: this should not happen
         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 //////////////////////////////////////////////////////////////////////////////