X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FNode.java;h=871086302859d6f4627b4d18d4afb8771b9ece68;hp=53782f7c65c83bb5960709499a0076e9e6a4815e;hb=4850d43495402e368e495707388e157a9cef9484;hpb=a8478f5ddfbfbc8d910d09f27163cbd55752d3b6 diff --git a/src/edu/berkeley/sbp/Node.java b/src/edu/berkeley/sbp/Node.java index 53782f7..8710863 100644 --- a/src/edu/berkeley/sbp/Node.java +++ b/src/edu/berkeley/sbp/Node.java @@ -10,134 +10,90 @@ import java.util.*; import java.lang.reflect.*; /** a node in the GSS */ -final class Node implements Invokable, IntegerMappable, GraphViz.ToGraphViz { +final class Node + implements Invokable, + IntegerMappable, + GraphViz.ToGraphViz, + Iterable { - 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; - - /** which GSS.Phase this Node belongs to (node that Node is also a non-static inner class of GSS.Phase) */ + /** 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 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; - } - } - Forest.Many f = new Forest.Many(); - f.parents.add(parent); - f.merge(result); - resultMap.add(f); - addParent(parent, true); - return false; - } + public int toInt() { return idx; } - public void performReductions() { - if (allqueued) return; - allqueued = true; - state.invokeReductions(phase().token(), this, this, null); + public boolean merge(Result r) { + if (results.contains(r)) return true; + results.add(r); + if (fromEmptyReduction) return false; + state.invokeReductions(phase().getToken(), this, false, r); + return false; } - 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(); + + public final void invoke(Position r, Boolean emptyProductions, Result only) { + if (emptyProductions != (r.pos==0)) return; + if (r.pos==0) finish(r, r.zero(phase().getLocation().createRegion(phase().getLocation())), phase()); + else reduce(r, r.pos-1, phase(), only); } - 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); + 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 new Reduction(child, r, r.rewrite(child.phase().getLocation().createRegion(target.getLocation())), target); } - } holder[pos] = old; } - public void finish(Position r, Forest result, GSS.Phase target) { + void finish(Position r, Forest forest, 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); + Result result = new Result(forest, this, r); + target.newNodeFromReduction(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; + results.add(result); + if (phase.hash.get(state, result.phase()) != null) throw new Error("severe problem!"); + phase.hash.put(state, result.phase(), this); + + for(Object s : state.also) + phase.newNode(result, (State)s, fromEmptyReduction); + + state.invokeReductions(phase().token, this, true, null); + if (!fromEmptyReduction) + state.invokeReductions(phase().getToken(), this, false, null); } - 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.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; }