From: adam Date: Tue, 4 Mar 2008 04:11:41 +0000 (-0500) Subject: some new attempts at a better dead-node collection; introduces hasPathToRoot X-Git-Url: http://git.megacz.com/?p=sbp.git;a=commitdiff_plain;h=c1a7dcf0dd5b839d82215263d0f57470e905a73d some new attempts at a better dead-node collection; introduces hasPathToRoot darcs-hash:20080304041141-5007d-a1a805e822b9aca4e4bb04c2b0fff7cb91745d8a.gz --- diff --git a/TODO b/TODO index f8746d0..ecaed94 100644 --- a/TODO +++ b/TODO @@ -1,6 +1,9 @@ _____________________________________________________________________________ Immediately + - keywordification (ie globally reject from all productions? + - generalized follow-by?) + - clean up util package - currently we GC the doomed stack when the parent dies... but diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java index 7666ec2..81e4909 100644 --- a/src/edu/berkeley/sbp/GSS.java +++ b/src/edu/berkeley/sbp/GSS.java @@ -24,7 +24,7 @@ class GSS { int numReductions = 0; /** corresponds to a positions between tokens the input stream; same as Tomita's U_i's */ - class Phase implements Invokable, IntegerMappable, GraphViz.ToGraphViz, Iterable { + class Phase implements Invokable, IntegerMappable, GraphViz.ToGraphViz /*, Iterable*/ { // FIXME: right now, these are the performance bottleneck private HashMapBag performed = new HashMapBag(); @@ -128,7 +128,7 @@ class GSS { for(StateNode n : h) n.check(); } numOldNodes = hash.size(); - for(StateNode n : hash.values()) { + for(StateNode n : hash) { if (token == null && n.state().isAccepting()) { if (finalResult==null) finalResult = new Forest.Many(); for(ResultNode r : n) @@ -209,7 +209,7 @@ class GSS { public int size() { return hash==null ? 0 : hash.size(); } public int pos() { return pos; } public Tok getToken() { return token; } - public Iterator iterator() { return hash.iterator(); } + //public Iterator iterator() { return hash.iterator(); } public GSS getGSS() { return GSS.this; } // GraphViz ////////////////////////////////////////////////////////////////////////////// @@ -229,8 +229,10 @@ class GSS { FileOutputStream fos = new FileOutputStream(filename); PrintWriter p = new PrintWriter(new OutputStreamWriter(fos)); GraphViz gv = new GraphViz(); + /* for(Object n : this) ((StateNode)n).toGraphViz(gv); + */ gv.dump(p); p.flush(); p.close(); diff --git a/src/edu/berkeley/sbp/Node.java b/src/edu/berkeley/sbp/Node.java index 4feac2b..6aecefa 100644 --- a/src/edu/berkeley/sbp/Node.java +++ b/src/edu/berkeley/sbp/Node.java @@ -15,6 +15,34 @@ abstract class Node GraphViz.ToGraphViz, Iterable { + private final GSS.Phase phase; + private final GSS.Phase predecessorPhase; + protected boolean destroyed = false; + private int numNonDoomedSuccessors = 0; + private boolean hasPathToRoot = false; + + private FastSet predecessors = new FastSet(); + private FastSet successors = new FastSet(); + //protected HashSet predecessors = new HashSet(); + //protected HashSet successors = new HashSet(); + + 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(); + } + /** * Every Node has a phase; StateNodes belong to the phase in * which they were shifted, ResultNodes belong to the phase of @@ -26,21 +54,13 @@ abstract class Node this.predecessorPhase = predecessorPhase; } - private final GSS.Phase phase; - private final GSS.Phase predecessorPhase; - public GSS.Phase phase() { return phase; } - public GSS.Phase predecessorPhase() { return predecessorPhase; } - protected boolean destroyed = false; - private int numNonDoomedSuccessors = 0; - public boolean hasSuccessors() { return successors.size() > 0; } - public boolean hasNonDoomedSuccessors() { return numNonDoomedSuccessors > 0; } - /** 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 (pred.hasPathToRoot()) hasPathToRoot = true; } public void addSucc(OtherNode succ) { if (successors.contains(succ)) throw new Error("a predecessor was added twice"); @@ -48,46 +68,41 @@ abstract class Node numNonDoomedSuccessors += succ.isDoomedState() ? 0 : 1; if (predecessors.size() > 1 && (((Object)this) instanceof ResultNode)) throw new Error(); } - public void removeSucc(OtherNode succ) { - if (!successors.contains(succ)) return; - successors.remove(succ); - numNonDoomedSuccessors -= succ.isDoomedState() ? 0 : 1; - check(); - } protected void destroy() { destroyed = true; - while(predecessors.size() > 0) - for(OtherNode pred : predecessors) { - removePred(pred); - pred.removeSucc(this); - break; - } + while(predecessors.size() > 0) { + OtherNode pred = predecessors.first(); + removePred(pred); + pred.removeSucc(this); + } predecessors = null; - while(successors.size() > 0) - for(OtherNode succ : successors) { - removeSucc(succ); - succ.removePred(this); - break; - } + while(successors.size() > 0) { + OtherNode succ = successors.first(); + removeSucc(succ); + succ.removePred(this); + } successors = null; } - - public abstract boolean isDoomedState(); - protected abstract void check(); - + public void removeSucc(OtherNode succ) { + if (!successors.contains(succ)) return; + successors.remove(succ); + numNonDoomedSuccessors -= succ.isDoomedState() ? 0 : 1; + check(); + } public void removePred(OtherNode pred) { if (!predecessors.contains(pred)) return; predecessors.remove(pred); + updatePathsToRootAfterRemoval(); check(); } - protected FastSet predecessors = new FastSet(); - protected FastSet successors = new FastSet(); - //private HashSet predecessors = new HashSet(); - //private HashSet successors = new HashSet(); + + 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) { diff --git a/src/edu/berkeley/sbp/ParseFailed.java b/src/edu/berkeley/sbp/ParseFailed.java index 872ffac..fe8e247 100644 --- a/src/edu/berkeley/sbp/ParseFailed.java +++ b/src/edu/berkeley/sbp/ParseFailed.java @@ -143,7 +143,7 @@ public class ParseFailed extends Exception { static void error(String message, GSS.Phase phase, Object token, Input.Region region) throws ParseFailed { error(message, token, - phase, + /*phase*/null, region, phase.getGSS().getInput(), phase.getGSS()); @@ -184,8 +184,9 @@ public class ParseFailed extends Exception { */ } HashMap hm = new HashMap(); - for(StateNode no : nodes) - barf(hm, no, 0, false, region.getStart()); + if (nodes!=null) + for(StateNode no : nodes) + barf(hm, no, 0, false, region.getStart()); ret.append("\n expected: "); Set hs = hm.keySet(); if (hs.size() == 1) { diff --git a/src/edu/berkeley/sbp/ResultNode.java b/src/edu/berkeley/sbp/ResultNode.java index 65732a6..655b85a 100644 --- a/src/edu/berkeley/sbp/ResultNode.java +++ b/src/edu/berkeley/sbp/ResultNode.java @@ -17,11 +17,14 @@ final class ResultNode public boolean isDoomedState() { /* this is irrelevant */ return false; } public Forest getForest() { return f; } public String toString() { return super.toString()+"->"+phase(); } + public boolean hasPathToRoot() { + if (predecessorPhase()==null) return true; + return super.hasPathToRoot(); + } public void check() { if (destroyed) return; - if (successors.size()==0) destroy(); - else if (predecessors.size()==0) destroy(); + if (!hasSuccessors() || !hasPredecessors()) destroy(); } protected void destroy() { if (destroyed) return; @@ -32,7 +35,7 @@ final class ResultNode protected void addPred(StateNode pred) { super.addPred(pred); // results should have at most one predecessor - if (predecessors.size() > 1) throw new Error(); + //if (predecessors.size() > 1) throw new Error(); } public ResultNode() { this(null, null, null); } diff --git a/src/edu/berkeley/sbp/StateNode.java b/src/edu/berkeley/sbp/StateNode.java index 768d8bf..c67b1af 100644 --- a/src/edu/berkeley/sbp/StateNode.java +++ b/src/edu/berkeley/sbp/StateNode.java @@ -15,12 +15,15 @@ final class StateNode extends Node implements Invokable { - private boolean fromEmptyReduction; private final Parser.Table.State state; /** which GSS.Phase this StateNode belongs to */ public Parser.Table.State state() { return state; } public boolean isDoomedState() { return state.doomed; } + public boolean hasPathToRoot() { + if (state.doomed) return false; + return super.hasPathToRoot(); + } public void check() { if (destroyed) return; @@ -30,10 +33,10 @@ final class StateNode // - 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) + else for(ResultNode r : successors()) if (state.doomed) { if (r.hasSuccessors()) { dead = false; break; } } else { if (r.hasNonDoomedSuccessors()) { dead = false; break; } } - dead |= predecessors.size()==0; + dead |= !hasPredecessors(); if (!dead) return; if (phase() != null && phase().hash != null) phase().hash.remove(state, predecessorPhase()); @@ -48,23 +51,24 @@ final class StateNode 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().numPops()==0) return; + 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 : predecessors) + for(ResultNode res : this) if (only == null || res == only) 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 { - Input.Region region = pred.phase().getLocation().createRegion(target.getLocation()); - new Reduction(pred, r, r.rewrite(region), target); - } + else new Reduction(pred, r, + pred.hasPathToRoot() + ? r.rewrite(pred.phase().getLocation().createRegion(target.getLocation())) + : null, + target); if (pos < holder.length) holder[pos] = old; } } @@ -72,7 +76,6 @@ final class StateNode StateNode(GSS.Phase phase, ResultNode pred, State state) { super(phase, pred.phase()); this.state = state; - this.fromEmptyReduction = pred!=null && pred.reduction()!=null && pred.reduction().numPops()==0; if (phase.hash.get(state, pred.phase()) != null) throw new Error("severe problem!"); phase.hash.put(state, pred.phase(), this); addPred(pred); @@ -82,7 +85,7 @@ final class StateNode // Add/Remove Successors/Predecessors ////////////////////////////////////////////////////////////////////////////// public void addPred(Forest f, Pos reduction, StateNode pred) { - for(ResultNode r : predecessors) + for(ResultNode r : this) if (r.predecessorsContains(pred)) { r.merge(f); return;