From: adam Date: Sun, 9 Sep 2007 19:06:29 +0000 (-0400) Subject: major overhaul to institute optimal GSS sharing X-Git-Url: http://git.megacz.com/?p=sbp.git;a=commitdiff_plain;h=6f1b2b1cba77222aeed1594d878b8c1250e31c1f;ds=sidebyside major overhaul to institute optimal GSS sharing darcs-hash:20070909190629-5007d-5431d8ece0f68d075d546b30b4498db67a63e3de.gz --- diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java index bf58e64..3876d58 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(); @@ -38,15 +38,15 @@ class GSS { parser.spin(); reductionQueue.add(r); } - public void invoke(State st, Result result) { + + public void invoke(State st, Node pred, Forest f) { parser.spin(); - good |= next.newNode(result, st, false); + good |= next.newNode(f, null, pred, st, false); } /** the token immediately after this phase */ final Tok token; final int pos; - public IntPairMap hash = new IntPairMap(); /* ALLOC */ private boolean good = false; private Phase next = null; @@ -58,8 +58,7 @@ class GSS { public Phase(State startState) throws ParseFailed, IOException { this(null, null); - Result primordealResult = new Result(null, null, null); - newNode(primordealResult, startState, true); + newNode(null, null, null, startState, true); } public Phase(Phase prev, Forest forest) throws ParseFailed, IOException { this.location = input.getLocation(); @@ -130,11 +129,11 @@ class GSS { finalResult.merge(r.getForest()); } if (token == null) continue; - Result result = new Result(f, n, null); - n.state().invokeShifts(token, this, result); + n.state().invokeShifts(token, this, n, f); } numNewNodes = next==null ? 0 : next.hash.size(); viewPos = this.pos; + if (!good && token!=null) { String toks = token+""; if (toks.length()==1 && toks.charAt(0) == edu.berkeley.sbp.chr.CharAtom.left) { @@ -159,8 +158,8 @@ class GSS { return getLocation().createRegion(getNextLocation()); } - void newNodeFromReduction(Result result, State state, Pos reduction) { - int pos = result.phase().pos; + void newNodeFromReduction(Forest f, Pos reduction, Node pred) { + int pos = pred.phase().pos; for(int s : reduction.hates()) if (performed.contains(pos, s)) return; @@ -169,8 +168,9 @@ class GSS { return; if (reduction.owner_needed_or_hated() && !performed.contains(pos, reduction.provides())) performed.add(pos, reduction.provides()); + Parser.Table.State state = (Parser.Table.State)pred.state().gotoSetNonTerminals.get(reduction); if (state!=null) - newNode(result, state, reduction.numPops()<=0); + newNode(f, reduction, pred, state, reduction.numPops()<=0); } /** add a new node (merging with existing nodes if possible) @@ -180,19 +180,22 @@ class GSS { * @param fromEmptyReduction true iff this node is being created as a result of a reduction of length zero (see GRMLR paper) * @param start the earliest part of the input contributing to this node (used to make merging decisions) */ - private boolean newNode(Result result, State state, boolean fromEmptyReduction) { - Node p = hash.get(state, result.phase()); - if (p != null) { p.addResult(result); return !state.doomed(); } + private boolean newNode(Forest f, Pos reduction, Node pred, State state, boolean fromEmptyReduction) { + Node p = pred==null ? null : hash.get(state, pred.phase()); + if (p != null) { + p.addResult(f, reduction, pred); + return !state.doomed(); + } do { if (token != null && state.canShift(token)) break; if (state.isAccepting()) break; if (token==null) break; if (!state.canReduce(token)) return false; } while(false); - Node n = new Node(Phase.this, result, state, fromEmptyReduction); // ALLOC + Node n = new Node(Phase.this, f, reduction, pred, state, fromEmptyReduction); // ALLOC /** FIXME: this null-result can be used to notice bogus/dead states */ for(Object s : state.conjunctStates) - newNode(new Result(null, n, null), (State)s, fromEmptyReduction); + newNode(null, null, n, (State)s, fromEmptyReduction); return !n.state().doomed(); } diff --git a/src/edu/berkeley/sbp/Node.java b/src/edu/berkeley/sbp/Node.java index 6fe6a74..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 { @@ -45,7 +45,7 @@ final class Node while(successors.size()>0) for(Result r : successors) { successors.remove(r); - r.destroy(); + r.removePred(this); break; } while(results.size()>0) @@ -64,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 successors = 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()); - Result.newResult(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 pred = res.pred(); - 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); - } - } - holder[pos] = old; + if (only == null || res == only) + for(Node pred : res.getPreds()) + reduce2(r, pos, target, pred, res.getForest()); } + 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, pred.phase()) != null) throw new Error("severe problem!"); + this.predPhase = pred.phase(); phase.hash.put(state, pred.phase(), this); - addResult(pred); + + results.add(pred); + pred.addSucc(this); + if (!fromEmptyReduction) + state.invokeReductions(phase().getToken(), this, pred); + state.invokeEpsilonReductions(phase().token, this); } // Add/Remove Successors/Results ////////////////////////////////////////////////////////////////////////////// public void removeSucc(Result succ) { - if (successors==null) return; successors.remove(succ); check(); } public void removeResult(Result result) { - if (results==null) return; results.remove(result); check(); } public void addSucc(Result succ) { - if (successors==null) return; // FIXME: this should not happen successors.add(succ); } - public void addResult(Result r) { - if (results.contains(r)) return; - results.add(r); - r.addSucc(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 ////////////////////////////////////////////////////////////////////////////// diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java index 6b9bad7..2fc0691 100644 --- a/src/edu/berkeley/sbp/Parser.java +++ b/src/edu/berkeley/sbp/Parser.java @@ -273,8 +273,8 @@ public abstract class Parser implements Serializable { HashMap> gotoSetNonTerminals = new HashMap>(); private transient TopologicalBag> gotoSetTerminals = new TopologicalBag>(); - private TopologicalBag reductions = new TopologicalBag(); - private HashSet eofReductions = new HashSet(); + TopologicalBag reductions = new TopologicalBag(); + HashSet eofReductions = new HashSet(); private TopologicalBag> shifts = new TopologicalBag>(); private boolean accept = false; @@ -290,16 +290,16 @@ public abstract class Parser implements Serializable { Iterable positions() { return hs; } boolean canShift(Token t) { return oshifts!=null && oshifts.contains(t); } - void invokeShifts(Token t, GSS.Phase phase, Result r) { oshifts.invoke(t, phase, r); } + void invokeShifts(Token t, GSS.Phase phase, Node pred, Forest f) { oshifts.invoke(t, phase, pred, f); } boolean canReduce(Token t) { return oreductions != null && (t==null ? eofReductions.size()>0 : oreductions.contains(t)); } void invokeEpsilonReductions(Token t, Node node) { - if (t==null) for(Pos r : eofReductions) node.invoke(r, null); - else oreductions.invoke(t, node, null); + if (t==null) for(Pos r : eofReductions) node.invoke(r, null, null); + else oreductions.invoke(t, node, null, null); } void invokeReductions(Token t, Node node, Result b) { - if (t==null) for(Pos r : eofReductions) node.invoke(r, b); - else oreductions.invoke(t, node, b); + if (t==null) for(Pos r : eofReductions) node.invoke(r, b, null); + else oreductions.invoke(t, node, b, null); } // Constructor ////////////////////////////////////////////////////////////////////////////// diff --git a/src/edu/berkeley/sbp/Reduction.java b/src/edu/berkeley/sbp/Reduction.java index 4ef2013..222a168 100644 --- a/src/edu/berkeley/sbp/Reduction.java +++ b/src/edu/berkeley/sbp/Reduction.java @@ -41,7 +41,8 @@ final class Reduction implements Comparable { } public void perform() { - Result.newResult(forest, pred, reduction, phase); + if (reduction==null) return; + phase.newNodeFromReduction(forest, reduction, pred); } public GSS.Phase predPhase() { return pred.phase(); } public Pos reduction() { return reduction; } diff --git a/src/edu/berkeley/sbp/Result.java b/src/edu/berkeley/sbp/Result.java index 97f467f..c91ab76 100644 --- a/src/edu/berkeley/sbp/Result.java +++ b/src/edu/berkeley/sbp/Result.java @@ -8,19 +8,41 @@ import java.util.*; final class Result implements GraphViz.ToGraphViz { - private Forest f; - private Node pred; - private HashSet successors = new HashSet(); + private Forest.Many f = new Forest.Many(); + //private HashSet predecessors = new HashSet(); + //private HashSet successors = new HashSet(); + private FastSet predecessors = new FastSet(); + private FastSet successors = new FastSet(); private boolean destroyed = false; + private boolean primordeal; private int usedByNonDoomedNode = 0; private Pos reduction; + private GSS.Phase predPhase; - public GSS.Phase phase() { return pred==null ? null : pred.phase(); } + public boolean predecessorsContains(Node n) { + return predecessors.contains(n); + } + public Pos reduction() { return reduction; } + public void merge(Forest newf) { + this.f.merge(newf); + /* + if (predecessors.contains(pred)) return; + addPred(pred); + if (fromEmptyReduction) return; + n.state().invokeReductions(n.phase().getToken(), n, this); + */ + } + + public boolean noSuccessors() { return successors.size()==0; } + + public GSS.Phase phase() { return predPhase; } public Forest getForest() { return f; } - public Node pred() { return pred; } + public Iterable getPreds() { return predecessors; } public void addSucc(Node succ) { + if (successors.contains(succ)) return; successors.add(succ); usedByNonDoomedNode += succ.state().doomed ? 0 : 1; + if (predecessors.size() > 1) throw new Error(); } public void removeSucc(Node succ) { if (!successors.contains(succ)) return; @@ -32,33 +54,54 @@ final class Result implements GraphViz.ToGraphViz { public boolean usedByAnyNode() { return successors.size() > 0; } public boolean usedByNonDoomedNode() { return usedByNonDoomedNode > 0; } - public String toString() { return super.toString()+"->"+pred(); } + public String toString() { return super.toString()+"->"+predPhase; } - public void check() { if (successors.size()==0) destroy(); } + public void check() { + if (successors.size()==0) destroy(); + else if (predecessors.size()==0) destroy(); + } public void destroy() { if (destroyed) return; - if (pred==null) return; // never destroy the "primordeal" result + if (primordeal) return; // never destroy the "primordeal" result destroyed = true; - pred.removeSucc(this); + while(predecessors.size() > 0) + for(Node pred : predecessors) { + removePred(pred); + pred.removeSucc(this); + break; + } + predecessors = null; while(successors.size() > 0) - for(Node n : successors) { - removeSucc(n); - n.removeResult(this); + for(Node succ : successors) { + removeSucc(succ); + succ.removeResult(this); break; } + successors = null; } - public static void newResult(Forest f, Node pred, Pos reduction, GSS.Phase target) { - Result r = new Result(f, pred, reduction); - if (reduction == null) return; - Parser.Table.State state0 = (Parser.Table.State)pred.state().gotoSetNonTerminals.get(reduction); - target.newNodeFromReduction(r, state0, reduction); + public void removePred(Node pred) { + if (!predecessors.contains(pred)) return; + predecessors.remove(pred); + check(); + } + + public void addPred(Node pred) { + if (predPhase==null) predPhase = pred.phase(); + if (predPhase != pred.phase()) throw new Error(); + predecessors.add(pred); + pred.addSucc(this); + if (predecessors.size() > 1) throw new Error(); + } + + public Result() { + this(null, null, null); + this.primordeal = true; } - public Result(Forest f, Node pred, Pos reduction) { - this.f = f; - this.pred = pred; + public Result(Forest f, Pos reduction, Node pred) { + this.f.merge(f); this.reduction = reduction; - if (pred != null) pred.addSucc(this); + if (pred != null) addPred(pred); } // GraphViz ////////////////////////////////////////////////////////////////////////////// @@ -68,7 +111,7 @@ final class Result implements GraphViz.ToGraphViz { GraphViz.Node n = gv.createNode(this); n.label = ""+f; n.shape = "rectangle"; - if (pred()!=null) n.edge(pred, ""); + //if (pred()!=null) n.edge(pred, ""); n.color = "blue"; if (phase() != null) ((GraphViz.Group)phase().toGraphViz(gv)).add(n);