X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FNode.java;h=6aecefa48260ef50cfeb0f4dbaef01c094b2a389;hp=740d8a6d49bcac0e4410de67809ddc6fff6cd03b;hb=HEAD;hpb=8cf79c4b9e5a26ef65bd4af600946b45dbf28a8a diff --git a/src/edu/berkeley/sbp/Node.java b/src/edu/berkeley/sbp/Node.java index 740d8a6..6aecefa 100644 --- a/src/edu/berkeley/sbp/Node.java +++ b/src/edu/berkeley/sbp/Node.java @@ -10,139 +10,133 @@ import java.io.*; import java.util.*; import java.lang.reflect.*; -/** a node in the GSS */ -final class Node - implements Invokable, - IntegerMappable, +abstract class Node + implements IntegerMappable, GraphViz.ToGraphViz, - Iterable { + Iterable { - /** which GSS.Phase this Node belongs to */ - public GSS.Phase phase() { return phase; } - public Iterator iterator() { return results.iterator(); } - public Parser.Table.State state() { return state; } + private final GSS.Phase phase; + private final GSS.Phase predecessorPhase; + protected boolean destroyed = false; + private int numNonDoomedSuccessors = 0; + private boolean hasPathToRoot = false; - public int toInt() { return idx; } + private FastSet predecessors = new FastSet(); + private FastSet successors = new FastSet(); + //protected HashSet predecessors = new HashSet(); + //protected HashSet successors = new HashSet(); - boolean destroyed = false; - - public void check() { - if (destroyed) return; - boolean dead = true; - // - all nodes must have a predecessor - // - non-doomed nodes must either: - // - be on the frontier or - // - have a non-doomed node closer to the frontier than themself - if (phase.isFrontier()) dead = false; - else for(Result r : successors) - if (state.doomed) { if (r.usedByAnyNode()) { dead = false; break; } } - else { if (r.usedByNonDoomedNode()) { dead = false; break; } } - dead |= results.size()==0; - if (!dead) return; - destroyed = true; - while(successors.size()>0) - for(Result r : successors) { - successors.remove(r); - r.destroy(); - break; - } - while(results.size()>0) - for(Result r : results) { - results.remove(r); - r.removeSucc(this); - break; - } - results = null; - successors = null; + public GSS.Phase phase() { return phase; } + public GSS.Phase predecessorPhase() { return predecessorPhase; } + public boolean hasPredecessors() { return predecessors.size() > 0; } + public boolean hasSuccessors() { return successors.size() > 0; } + public boolean hasNonDoomedSuccessors() { return numNonDoomedSuccessors > 0; } + + public boolean hasPathToRoot() { return hasPathToRoot; } + public void updatePathsToRootAfterRemoval() { + if (!hasPathToRoot()) return; + for(OtherNode on : predecessors) + if (on.hasPathToRoot()) + return; + hasPathToRoot = false; + for(OtherNode on : successors) + on.updatePathsToRootAfterRemoval(); } - ////////////////////////////////////////////////////////////////////// - - private static int node_idx = 0; - private final int idx = node_idx++; - - private final GSS.Phase phase; - private final Parser.Table.State state; - private final boolean fromEmptyReduction; - //private FastSet results = new FastSet(); - private HashSet results = new HashSet(); - private HashSet successors = new HashSet(); - - public final void invoke(Pos r, Result only) { - 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()); - } + /** + * Every Node has a phase; StateNodes belong to the phase in + * which they were shifted, ResultNodes belong to the phase of + * their predecessors. All of the predecessors of a given node + * must belong to the same phase + */ + public Node(GSS.Phase phase, GSS.Phase predecessorPhase) { + this.phase = phase; + this.predecessorPhase = predecessorPhase; } - 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; + /** only to be invoked (or overridden as public) by the subclass */ + protected void addPred(OtherNode pred) { + if (predecessors.contains(pred)) throw new Error("a predecessor was added twice"); + if (pred.phase() != predecessorPhase()) throw new Error(); + predecessors.add(pred); + pred.addSucc(this); + if (pred.hasPathToRoot()) hasPathToRoot = true; } - - 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!"); - phase.hash.put(state, pred.phase(), this); - addResult(pred); - state.invokeEpsilonReductions(phase().token, this); + public void addSucc(OtherNode succ) { + if (successors.contains(succ)) throw new Error("a predecessor was added twice"); + successors.add(succ); + numNonDoomedSuccessors += succ.isDoomedState() ? 0 : 1; + if (predecessors.size() > 1 && (((Object)this) instanceof ResultNode)) throw new Error(); } - // Add/Remove Successors/Results ////////////////////////////////////////////////////////////////////////////// - - public void removeSucc(Result succ) { - if (successors==null) return; + protected void destroy() { + destroyed = true; + while(predecessors.size() > 0) { + OtherNode pred = predecessors.first(); + removePred(pred); + pred.removeSucc(this); + } + predecessors = null; + while(successors.size() > 0) { + OtherNode succ = successors.first(); + removeSucc(succ); + succ.removePred(this); + } + successors = null; + } + public void removeSucc(OtherNode succ) { + if (!successors.contains(succ)) return; successors.remove(succ); + numNonDoomedSuccessors -= succ.isDoomedState() ? 0 : 1; check(); } - public void removeResult(Result result) { - if (results==null) return; - results.remove(result); + public void removePred(OtherNode pred) { + if (!predecessors.contains(pred)) return; + predecessors.remove(pred); + updatePathsToRootAfterRemoval(); 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 abstract boolean isDoomedState(); + protected abstract void check(); + + public Iterator iterator() { return predecessors.iterator(); } + public Iterable successors() { return successors; } + + public boolean noSuccessors() { return successors.size()==0; } + public boolean predecessorsContains(OtherNode n) { + return predecessors.contains(n); } // GraphViz ////////////////////////////////////////////////////////////////////////////// - public GraphViz.Node toGraphViz(GraphViz gv) { - if (results.size()==0) return null; + public GraphViz.StateNode toGraphViz(GraphViz gv) { if (gv.hasNode(this)) return gv.createNode(this); - GraphViz.Node n = gv.createNode(this); + GraphViz.StateNode n = gv.createNode(this); + /* + n.label = ""+f; + n.shape = "rectangle"; + //if (pred()!=null) n.edge(pred, ""); + n.color = "blue"; + if (phase() != null) + ((GraphViz.Group)phase().toGraphViz(gv)).add(n); n.label = "state["+state.toInt()+"]"; n.shape = "rectangle"; boolean haspreds = false; - for(Result r : results) n.edge(r, ""); + for(ResultNode r : results) n.edge(r, ""); n.color = state.doomed ? "red" : "green"; ((GraphViz.Group)phase().toGraphViz(gv)).add(n); + */ return n; } public boolean isTransparent() { return false; } public boolean isHidden() { return false; } -} + // IntegerMappable //////////////////////////////////////////////////////////// + + private static int node_idx = 0; + private final int idx = node_idx++; + public int toInt() { return idx; } + +} \ No newline at end of file