X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FNode.java;h=6aecefa48260ef50cfeb0f4dbaef01c094b2a389;hp=83533849f3bc6e1b8ad7ee87004f5358ca5b38c6;hb=HEAD;hpb=6f1b2b1cba77222aeed1594d878b8c1250e31c1f diff --git a/src/edu/berkeley/sbp/Node.java b/src/edu/berkeley/sbp/Node.java index 8353384..6aecefa 100644 --- a/src/edu/berkeley/sbp/Node.java +++ b/src/edu/berkeley/sbp/Node.java @@ -10,156 +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 { - - /** 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; } - - public int toInt() { return idx; } - - 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; - if (phase() != null && phase().hash != null) - phase().hash.remove(state, predPhase); - while(successors.size()>0) - for(Result r : successors) { - successors.remove(r); - r.removePred(this); - break; - } - while(results.size()>0) - for(Result r : results) { - results.remove(r); - r.removeSucc(this); - break; - } - results = null; - successors = null; - } - - ////////////////////////////////////////////////////////////////////// - - private static int node_idx = 0; - private final int idx = node_idx++; + Iterable { private final GSS.Phase phase; - private final GSS.Phase predPhase; - private final Parser.Table.State state; - private boolean fromEmptyReduction; - private FastSet results = new FastSet(); - private FastSet successors = new FastSet(); - //private HashSet results = new HashSet(); - //private HashSet successors = new HashSet(); - - 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()); - phase().newNodeFromReduction(r.rewrite(region), r, this); - } - } + private final GSS.Phase predecessorPhase; + protected boolean destroyed = false; + private int numNonDoomedSuccessors = 0; + private boolean hasPathToRoot = false; - private void reduce(Pos r, int pos, GSS.Phase target, Result only) { - for(Result res : results) - if (only == null || res == only) - for(Node pred : res.getPreds()) - reduce2(r, pos, target, pred, res.getForest()); - } + private FastSet predecessors = new FastSet(); + private FastSet successors = new FastSet(); + //protected HashSet predecessors = new HashSet(); + //protected HashSet successors = new HashSet(); - 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; + 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(); } - 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) { + /** + * 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.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); + this.predecessorPhase = predecessorPhase; + } - results.add(pred); + /** 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 (!fromEmptyReduction) - state.invokeReductions(phase().getToken(), this, pred); - - state.invokeEpsilonReductions(phase().token, this); + if (pred.hasPathToRoot()) hasPathToRoot = true; + } + 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) { + 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) { - results.remove(result); + public void removePred(OtherNode pred) { + if (!predecessors.contains(pred)) return; + predecessors.remove(pred); + updatePathsToRootAfterRemoval(); check(); } - public void addSucc(Result succ) { - successors.add(succ); - } - 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); + + + 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