X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FStateNode.java;h=c67b1af021926ae64257e34330b855a7b45790b4;hp=acd01341c8c5293b0d2e1ed9ad1e5a6fe4a6de2b;hb=HEAD;hpb=053eb99c444844015cfdb486b03c55adb0a3cd7f diff --git a/src/edu/berkeley/sbp/StateNode.java b/src/edu/berkeley/sbp/StateNode.java index acd0134..c67b1af 100644 --- a/src/edu/berkeley/sbp/StateNode.java +++ b/src/edu/berkeley/sbp/StateNode.java @@ -12,19 +12,18 @@ import java.lang.reflect.*; /** a node in the GSS */ final class StateNode - extends Node - implements Invokable, - IntegerMappable, - Iterable { + extends Node + implements Invokable { + + private final Parser.Table.State state; /** which GSS.Phase this StateNode 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 boolean isDoomedState() { return state.doomed; } + public boolean hasPathToRoot() { + if (state.doomed) return false; + return super.hasPathToRoot(); + } public void check() { if (destroyed) return; @@ -33,115 +32,68 @@ final class StateNode // - 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(ResultNode r : successors) - if (state.doomed) { if (r.usedByAnyNode()) { dead = false; break; } } - else { if (r.usedByNonDoomedNode()) { dead = false; break; } } - dead |= results.size()==0; + if (phase().isFrontier()) dead = false; + else for(ResultNode r : successors()) + if (state.doomed) { if (r.hasSuccessors()) { dead = false; break; } } + else { if (r.hasNonDoomedSuccessors()) { dead = false; break; } } + dead |= !hasPredecessors(); if (!dead) return; - destroyed = true; if (phase() != null && phase().hash != null) - phase().hash.remove(state, predPhase); - while(successors.size()>0) - for(ResultNode r : successors) { - successors.remove(r); - r.removePred(this); - break; - } - while(results.size()>0) - for(ResultNode r : results) { - results.remove(r); - r.removeSucc(this); - break; - } - results = null; - successors = null; + phase().hash.remove(state, predecessorPhase()); + destroy(); } - ////////////////////////////////////////////////////////////////////// - - private static int node_idx = 0; - private final int idx = node_idx++; - - 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, ResultNode 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 { + if (r.numPops()==0) { Input.Region region = phase().getLocation().createRegion(phase().getLocation()); phase().newNodeFromReduction(r.rewrite(region), r, this); + } else { + // never start reductions at a node that was created via a right-nulled rule + if (only.reduction() != null && only.reduction().numPops()==0) return; + reduce(r, r.numPops()-1, phase(), only); } } private void reduce(Pos r, int pos, GSS.Phase target, ResultNode only) { - for(ResultNode res : results) + for(ResultNode res : this) if (only == null || res == only) - for(StateNode pred : res.getPreds()) - reduce2(r, pos, target, pred, res.getForest()); + for(StateNode pred : res) { + Forest[] holder = r.holder; + Forest old = pos >= holder.length ? null : holder[pos]; + if (pos < holder.length) holder[pos] = res.getForest(); + if (pos>0) pred.reduce(r, pos-1, target, null); + else new Reduction(pred, r, + pred.hasPathToRoot() + ? r.rewrite(pred.phase().getLocation().createRegion(target.getLocation())) + : null, + target); + if (pos < holder.length) holder[pos] = old; + } } - void reduce2(Pos r, int pos, GSS.Phase target, StateNode 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; - } - - StateNode(GSS.Phase phase, Forest f, Pos reduction, StateNode pred, State state, boolean fromEmptyReduction) { - this(phase, new ResultNode(f, reduction, pred), state, fromEmptyReduction); - } - StateNode(GSS.Phase phase, ResultNode pred, State state, boolean fromEmptyReduction) { - this.phase = phase; + StateNode(GSS.Phase phase, ResultNode pred, State state) { + super(phase, pred.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); - - results.add(pred); - pred.addSucc(this); - if (!fromEmptyReduction) - state.invokeReductions(phase().getToken(), this, pred); - + addPred(pred); state.invokeEpsilonReductions(phase().token, this); } - // Add/Remove Successors/Results ////////////////////////////////////////////////////////////////////////////// + // Add/Remove Successors/Predecessors ////////////////////////////////////////////////////////////////////////////// - public void removeSucc(ResultNode succ) { - successors.remove(succ); - check(); - } - public void removeResult(ResultNode result) { - results.remove(result); - check(); - } - public void addSucc(ResultNode succ) { - successors.add(succ); - } - public void addResult(Forest f, Pos reduction, StateNode pred) { - for(ResultNode r : results) + public void addPred(Forest f, Pos reduction, StateNode pred) { + for(ResultNode r : this) if (r.predecessorsContains(pred)) { r.merge(f); return; } - ResultNode result = new ResultNode(f, reduction, pred); - results.add(result); - result.addSucc(this); - if (!this.fromEmptyReduction) state.invokeReductions(phase().getToken(), this, result); + addPred(new ResultNode(f, reduction, pred)); + } + protected void addPred(ResultNode result) { + super.addPred(result); + state.invokeReductions(phase().getToken(), this, result); } }