X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FGSS.java;h=8165ccdff0d4dc6f544b443b5f199a64c77a67c5;hp=d8c0fd45430a2f3cc1f020408a9a25e8ff665212;hb=6c2a17e674b32389d281261796e9e962e9d9380c;hpb=0a0227b9180534d2a431f3d6e08a398bde2244c4 diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java index d8c0fd4..8165ccd 100644 --- a/src/edu/berkeley/sbp/GSS.java +++ b/src/edu/berkeley/sbp/GSS.java @@ -21,10 +21,6 @@ import java.lang.reflect.*; // class is meant to remain simple and easy to understand; // optimizations which obscure that do not belong here (they // should go into the compiled version instead) -// -// - most of our time is now spent creating and storing Reduct instances -// - we should be able to perform Reduct's immediately after creating them... -// /** implements Tomita's Graph Structured Stack */ class GSS { @@ -43,25 +39,19 @@ class GSS { /** FIXME */ public Forest.Ref finalResult = null; - /** all reductions (pending and completed) */ - private HashSet reductions = new HashSet(); /* ALLOC */ - /** all nodes, keyed by the value returned by code() */ private HashMap hash = new HashMap(); /* ALLOC */ - /** the number of pending reductions */ - private int pendingReductions = 0; - private int totalReductions = 0; - private HashSet pendingReduct = new HashSet(); - /** the number of nodes in this phase */ private int numNodes = 0; boolean closed = false; - public Phase(Phase previous, Token token) { + private Token.Location location; + public Phase(Phase previous, Token token, Token.Location location) { this.pos = previous==null ? 0 : previous.pos+1; this.token = token; + this.location = location; } public boolean isDone() { return token == null; } @@ -72,7 +62,7 @@ class GSS { throw new Parser.Failed(error, getLocation()); } - public Token.Location getLocation() { return token==null ? null : token.getLocation(); } + public Token.Location getLocation() { return location; } /** add a new node (merging with existing nodes if possible) * @param parent the parent of the new node @@ -100,8 +90,8 @@ class GSS { int count = 0; Parser.Table.Reduction r = null; for(Parser.Table.Reduction red : token==null ? state.getEofReductions() : state.getReductions(token)) { r = red; count++; } - //if (count==0) return; -- BEWARE! this optimization is suspected to cause really nasty heisenbugs - if (count > 1) break; + //if (count==0) return; // BEWARE! this optimization is suspected to cause really nasty heisenbugs + //if (count > 1) break; //if (r.numPop == 0) break; //r.reduce(pending, parent, null, Phase.this, null); //return; @@ -109,25 +99,27 @@ class GSS { Node n = new Node(parent, pending, state, start); // ALLOC n.queueEmptyReductions(); - if (!fromEmptyReduction) n.queueReductions(); + if (!fromEmptyReduction) n.queueReductions(parent); } + + boolean reducing = false; /** perform all reduction operations */ public void reduce() { - for(Phase.Node n : hash.values()) { - n.queueEmptyReductions(); - n.queueReductions(); - } - while(pendingReduct.size()>0) - pendingReduct.iterator().next().go(); + reducing = true; + HashSet s = new HashSet(); + s.addAll(hash.values()); + for(Phase.Node n : s) n.queueEmptyReductions(); + for(Phase.Node n : s) n.queueReductions(); } /** perform all shift operations, adding promoted nodes to next */ - public void shift(Phase next) { + public void shift(Phase next, Forest result) { closed = true; Forest res = null; boolean ok = false; for(Phase.Node n : hash.values()) { + if (n.holder==null) continue; n.holder.resolve(); if (token == null && n.state.isAccepting()) { ok = true; @@ -137,7 +129,7 @@ class GSS { if (!n.holder.valid()) continue; if (token == null) continue; for(Parser.Table.State st : n.state.getShifts(token)) { - if (res == null) res = Forest.create(token.getLocation(), token.result(), null, null, false, false); + if (res == null) res = result; next.newNode(n, res, st, true, this); ok = true; } @@ -146,13 +138,13 @@ class GSS { if (!ok && token != null) { StringBuffer error = new StringBuffer(); error.append("error: unable to shift token \"" + token + "\"\n"); - error.append(" before: " +pendingReductions+ "\n"); - error.append(" before: " +totalReductions+ "\n"); - for(Phase.Node n : hash.values()) { - n.queueReductions(); - n.queueEmptyReductions(); - } - error.append(" after: " +pendingReductions+ "\n"); + //error.append(" before: " +pendingReductions+ "\n"); + //error.append(" before: " +totalReductions+ "\n"); + //for(Phase.Node n : hash.values()) { + //n.queueReductions(); + //n.queueEmptyReductions(); + //} + //error.append(" after: " +pendingReductions+ "\n"); error.append(" candidate states:\n"); for(Phase.Node n : hash.values()) { //for(Sequence.Position p : n.state) error.append(" " + p + "\n"); @@ -164,63 +156,87 @@ class GSS { } // this massively improves GC performance - reductions = null; hash = null; } // GSS Nodes ////////////////////////////////////////////////////////////////////////////// - private HashMap pcache = new HashMap(); /** a node in the GSS */ - public class Node { + public final class Node { private Forest.Ref holder = null; - private HashMap cache = null; - public HashMap cache() { return cache==null ? (cache = new HashMap()) : cache; } - public Forest.Ref holder() { return holder==null ? (holder = new Forest.Ref()) : holder; } - public Forest pending() { return Phase.this.closed ? holder().resolve() : holder; } - public FastSet parents() { return parents; } + private HashMap cache = null; - /** which Phase this Node belongs to (node that Node is also a non-static inner class of Phase) */ - public final Phase phase = Phase.this; + /** the set of nodes to which there is an edge starting at this node */ + public final FastSet parents = new FastSet(); /* ALLOC */ /** what state this node is in */ public final Parser.Table.State state; + /** which Phase this Node belongs to (node that Node is also a non-static inner class of Phase) */ + public final Phase phase = Phase.this; - /** the set of nodes to which there is an edge starting at this node */ - public final FastSet parents = new FastSet(); /* ALLOC */ + public HashMap cache() { + return cache==null ? (cache = new HashMap()) : cache; } + public Forest.Ref holder() { return holder==null ? (holder = new Forest.Ref()) : holder; } + public Forest pending() { return Phase.this.closed ? holder().resolve() : holder; } + public FastSet parents() { return parents; } /** FIXME */ public void queueReductions() { - for(Node n2 : parents) - queueReductions(n2); + if (allqueued) return; + allqueued = true; + FastSet h = new FastSet(); + for(Node n : parents) h.add(n); + for(Node n : h) queueReductions(n); } + private boolean allqueued = false; + private HashSet queued = new HashSet(); /** FIXME */ public void queueReductions(Node n2) { - new Reduct(this, n2, null); - for(Parser.Table.Reduction r : token==null ? state.getEofReductions() : state.getReductions(token)) { - + if (!allqueued) { queueReductions(); return; } + if (queued.contains(n2)) return; + queued.add(n2); + Node n = this; + for(Parser.Table.Reduction r : token==null ? n.state.getEofReductions() : n.state.getReductions(token)) { + + // UGLY HACK + // The problem here is that a "reduction of length 1" + // performed twice with different values of n2 needs + // to only create a *single* new result, but must add + // multiple parents to the node holding that result. + // The current reducer doesn't differentiate between + // the next node of an n-pop reduction and the + // ultimate parent of the last pop, so we need to + // cache instances here as a way of avoiding + // recreating them. + // currently we have this weird problem where we // have to do an individual reduct for each child // when the reduction length is one (ie the // children wind up being children of the newly // created node rather than part of the popped // sequence - - if (r.numPop == 1) new Reduct(this, n2, r); + if (r.numPop <= 0) continue; + if (r.numPop == 1) { + Forest ret = n.cache().get(r); + if (ret != null) r.reduce(n, n2, n.phase, ret); + else n.cache().put(r, r.reduce(n, n2, n.phase, null)); + } else { + r.reduce(n, n2, Phase.this, null); + } } } /** FIXME */ public void queueEmptyReductions() { - for(Parser.Table.Reduction r : token==null ? state.getEofReductions() : state.getReductions(token)) { - if (r.numPop==0) - new Reduct(this, null, r); /* ALLOC */ - } + if (reducing) + for(Parser.Table.Reduction r : token==null ? state.getEofReductions() : state.getReductions(token)) + if (r.numPop==0) + r.reduce(this, null, this.phase, r.zero()); } private Node(Node parent, Forest pending, Parser.Table.State state, Phase start) { @@ -234,83 +250,6 @@ class GSS { } } - - // Forest / Completed Reductions ////////////////////////////////////////////////////////////////////////////// - - /** a pending or completed reduction */ - class Reduct { - - /** the node from which the reduction should begin */ - public Node n = null; - - /** the node on the other end of the edge to be reduced along (either: null, the second node of the reduction, - * or the parent of the result of a length-one reduction) - */ - public Node n2 = null; - - /** true iff the reduction has already been performed */ - private boolean done = false; - - /** the reduction to be applied */ - public Parser.Table.Reduction r; - - public Tree result = null; - - public Reduct(Node n, Node n2, Parser.Table.Reduction r) { - this.n = n; - this.n2 = n2; - this.r = r; - if (reductions.contains(this)) { done = true; return; } - reductions.add(this); - pendingReduct.add(this); - pendingReductions++; - } - - /** perform the reduction */ - public void go() { - if (done) return; - done = true; - pendingReduct.remove(this); - pendingReductions--; - - // FIXME: explain this - if (r==null) { - for(Parser.Table.Reduction r : token==null ? n.state.getEofReductions() : n.state.getReductions(token)) { - if (r.numPop <= 1) continue; - r.reduce(n, n2, Phase.this, null); - } - } else if (r.numPop<=1) { - // UGLY HACK - // The problem here is that a "reduction of length 0/1" - // performed twice with different values of n2 needs - // to only create a *single* new result, but must add - // multiple parents to the node holding that result. - // The current reducer doesn't differentiate between - // the next node of an n-pop reduction and the - // ultimate parent of the last pop, so we need to - // cache instances here as a way of avoiding - // recreating them. - - Forest ret = (r.numPop==0 ? pcache : n.cache()).get(r); - if (ret != null) r.reduce(n, n2, n.phase, ret); - else (r.numPop==0 ? pcache : n.cache()).put(r, r.reduce(n, n2, n.phase, null)); - - } else { - r.reduce(n, n2, Phase.this, null); - } - } - - // FIXME: this is a PITA - public int hashCode() { return n.hashCode() ^ (r==null ? 0 : r.hashCode()) ^ (n2==null ? 0 : n2.hashCode()); } - public boolean equals(Object o) { - if (o==null) return false; - if (o==this) return true; - if (!(o instanceof Reduct)) return false; - Reduct other = (Reduct)o; - return equal(r, other.r) && equal(n, other.n) && equal(n2, other.n2); - } - } - } /** helper method */ @@ -324,5 +263,5 @@ class GSS { private static long code(Parser.Table.State state, Phase start) { return (((long)state.idx) << 32) | (start==null ? 0 : start.pos); } - + public boolean yak = false; }