X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FNode.java;h=83533849f3bc6e1b8ad7ee87004f5358ca5b38c6;hp=100f89f614587a12d5e12cb893cecfd3df367960;hb=6f1b2b1cba77222aeed1594d878b8c1250e31c1f;hpb=61566402d83d5c06d57fb850e60ca0f82c27b9a2 diff --git a/src/edu/berkeley/sbp/Node.java b/src/edu/berkeley/sbp/Node.java index 100f89f..8353384 100644 --- 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, + implements Invokable, IntegerMappable, GraphViz.ToGraphViz, Iterable { @@ -29,31 +29,33 @@ final class Node public void check() { if (destroyed) return; boolean dead = true; - // - all nodes must have a parent + // - 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 : children) + 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(children.size()>0) - for(Result r : children) { - children.remove(r); - r.destroy(); + 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.removeChild(this); + r.removeSucc(this); break; } results = null; - children = null; + successors = null; } ////////////////////////////////////////////////////////////////////// @@ -62,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 results = new FastSet(); - private HashSet results = new HashSet(); - private HashSet children = new HashSet(); + 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) { + 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()); - new Result(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 child = res.parent(); - holder[pos] = res.getForest(); - if (pos>0) child.reduce(r, pos-1, target, null); - else { - Input.Region region = child.phase().getLocation().createRegion(target.getLocation()); - new Reduction(child, 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()); } - Node(GSS.Phase phase, Result result, State state, boolean fromEmptyReduction) { + 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, result.phase()) != null) throw new Error("severe problem!"); - phase.hash.put(state, result.phase(), this); - addResult(result); + if (phase.hash.get(state, pred.phase()) != null) throw new Error("severe problem!"); + this.predPhase = pred.phase(); + phase.hash.put(state, pred.phase(), this); + + results.add(pred); + pred.addSucc(this); + if (!fromEmptyReduction) + state.invokeReductions(phase().getToken(), this, pred); + state.invokeEpsilonReductions(phase().token, this); } - // Add/Remove Children/Results ////////////////////////////////////////////////////////////////////////////// + // Add/Remove Successors/Results ////////////////////////////////////////////////////////////////////////////// - public void removeChild(Result child) { - if (children==null) return; - children.remove(child); + public void removeSucc(Result succ) { + successors.remove(succ); check(); } public void removeResult(Result result) { - if (results==null) return; results.remove(result); check(); } - public void addChild(Result child) { - if (children==null) return; // FIXME: this should not happen - children.add(child); + public void addSucc(Result succ) { + successors.add(succ); } - public void addResult(Result r) { - if (results.contains(r)) return; - results.add(r); - r.addChild(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 ////////////////////////////////////////////////////////////////////////////// @@ -136,7 +153,7 @@ final class Node GraphViz.Node n = gv.createNode(this); n.label = "state["+state.toInt()+"]"; n.shape = "rectangle"; - boolean hasparents = false; + boolean haspreds = false; for(Result r : results) n.edge(r, ""); n.color = state.doomed ? "red" : "green"; ((GraphViz.Group)phase().toGraphViz(gv)).add(n);