X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FNode.java;h=b6f45851746dc32bd7add3942fb91aedee0a4a7b;hp=53782f7c65c83bb5960709499a0076e9e6a4815e;hb=2afdfe14e78fa0597186614937c679a09d74ecdf;hpb=a8478f5ddfbfbc8d910d09f27163cbd55752d3b6 diff --git a/src/edu/berkeley/sbp/Node.java b/src/edu/berkeley/sbp/Node.java index 53782f7..b6f4585 100644 --- a/src/edu/berkeley/sbp/Node.java +++ b/src/edu/berkeley/sbp/Node.java @@ -10,134 +10,134 @@ import java.util.*; import java.lang.reflect.*; /** a node in the GSS */ -final class Node implements Invokable, IntegerMappable, GraphViz.ToGraphViz { - - public static int node_idx = 0; - - private final GSS.Phase phase; - - public FastSet setx = new FastSet(); - public FastSet childs = new FastSet(); - - private boolean allqueued = false; - - /** what state this node is in */ - public final Parser.Table.State state; +final class Node + implements Invokable, + 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; } - /** which GSS.Phase this Node belongs to (node that Node is also a non-static inner class of GSS.Phase) */ - public GSS.Phase phase() { return phase; } + public int toInt() { return idx; } - private HashSet resultMap = new HashSet(); - public Iterable results() { return resultMap; } - public Iterable parents() { return setx; } - public void addParent(Node n, boolean b) { - if (n==null) return; - setx.add(n, b); - n.childs.add(this, true); - //else - //System.out.println("************ evilstate: " + this); - } - public boolean merge(Node parent, Forest result) { - // FIXME: inefficient! - for(Forest.Many f : results()) { - if (f.parents.contains(parent) /* UGLY: */ && f.parents.size()==1) { - f.merge(result); - return true; + boolean destroyed = false; + + public void check() { + if (destroyed) return; + boolean dead = true; + // - all nodes must have a parent + // - 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) + 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(); + break; } - } - Forest.Many f = new Forest.Many(); - f.parents.add(parent); - f.merge(result); - resultMap.add(f); - addParent(parent, true); - return false; - } - - public void performReductions() { - if (allqueued) return; - allqueued = true; - state.invokeReductions(phase().token(), this, this, null); + while(results.size()>0) + for(Result r : results) { + results.remove(r); + r.removeChild(this); + break; + } + results = null; + children = null; } - public void performReductions(Node n2) { - if (!allqueued) phase().reductionQueue.add(this);//performReductions(); - else state.invokeReductions(phase().token(), this, this, n2); - } + ////////////////////////////////////////////////////////////////////// - public Parser.Table.State state() { return state; } + private static int node_idx = 0; + private final int idx = node_idx++; - public void performEmptyReductions() { state.invokeReductions(phase().token, this, null, null); } - public final void invoke(Position r, Node n, Node n2) { - //reductions++; - //if (r.pos==1) single_newnode++; - //if (r.pos>1) multi_newnode++; - if (n==null || n2==null || r.pos==0) { - if (r.pos==0) { - if (n==null) n = this; - else return; - } - if (n==null) return; - Forest[] holder = new Forest[r.pos]; - if (r.pos==0) n.finish(r, r.zero(n.phase().getLocation().createRegion(n.phase().getLocation())), n.phase()); - else n.reduce(r, r.pos-1, n.phase(), null); - } else { - if (r.pos<=0) throw new Error("called wrong form of reduce()"); - int pos = r.pos-1; - n.reduce(r, pos, n.phase(), n2); + 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 children = new HashSet(); + + public final void invoke(Position r, Result only) { + boolean emptyProductions = only==null; + if (emptyProductions != (r.pos==0)) return; + if (r.pos!=0) reduce(r, r.pos-1, phase(), only); + else { + Input.Region region = phase().getLocation().createRegion(phase().getLocation()); + new Result(r.rewrite(region, phase().parser().cache()), this, r, phase()); } } - public void reduce(Position r, int pos, GSS.Phase target, Node only) { + private void reduce(Position r, int pos, GSS.Phase target, Result only) { Forest[] holder = r.holder; Forest old = holder[pos]; - - //toplevel_reductions++; - HashSet rr = new HashSet(); - for(Forest result : results()) { - rr.add(result); - } - //System.out.println(r); - for(Forest result : rr) { - for(Node child : ((Forest.Many)result).parents) { - if (only != null && child!=only) continue; - holder[pos] = result; - if (pos==0) child.finish(r, r.rewrite(child.phase().getLocation().createRegion(target.getLocation())), target); - else child.reduce(r, pos-1, target, null); + 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, phase().parser().cache()), target); + } } - } holder[pos] = old; } - public void finish(Position r, Forest result, GSS.Phase target) { - Parser.Table.State state0 = (Parser.Table.State)state.gotoSetNonTerminals.get(r.owner()); - if (result==null) throw new Error(); - if (state0!=null) - target.newNode(this, result, state0, r.pos<=0, r); - } - - Node(GSS.Phase phase, Node parent, Forest pending, State state) { + Node(GSS.Phase phase, Result result, State state, boolean fromEmptyReduction) { this.phase = phase; this.state = state; - this.merge(parent, pending); - GSS.Phase start = parent==null ? null : parent.phase(); - if (parent != null) addParent(parent, true); - if (phase.hash.get(state, start) != null) throw new Error("severe problem!"); - phase.hash.put(state, start, this); + 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); + state.invokeEpsilonReductions(phase().token, this); + } + + // Add/Remove Children/Results ////////////////////////////////////////////////////////////////////////////// + + public void removeChild(Result child) { + if (children==null) return; + children.remove(child); + 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 addResult(Result r) { + if (results.contains(r)) return; + results.add(r); + r.addChild(this); + if (!fromEmptyReduction) state.invokeReductions(phase().getToken(), this, r); } - public int toInt() { return idx; } - private final int idx = node_idx++; // GraphViz ////////////////////////////////////////////////////////////////////////////// public GraphViz.Node toGraphViz(GraphViz gv) { + if (results.size()==0) return null; if (gv.hasNode(this)) return gv.createNode(this); GraphViz.Node n = gv.createNode(this); - n.label = ""+state.toStringx(); + n.label = "state["+state.toInt()+"]"; n.shape = "rectangle"; boolean hasparents = false; - for(Node parent : parents()) { hasparents = true; n.edge(parent, ""); } - for(Forest result : results()) n.edge(result, ""); - n.color = !hasparents ? "blue" : /*state.evil ? "red" :*/ "green"; + for(Result r : results) n.edge(r, ""); + n.color = state.doomed ? "red" : "green"; ((GraphViz.Group)phase().toGraphViz(gv)).add(n); return n; }