X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FGSS.java;h=8053ae8a8b7a014f259dbdd81c8a30dac879fa46;hp=7dbb29c11e26fde7e9fc5136f8f06dce4936bed0;hb=a22c5074e705e3ffcf03e9f9d174aed8ef79fc91;hpb=db08cd7213a2dbaa5146448d4d6f96b3f12e09b5 diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java index 7dbb29c..8053ae8 100644 --- a/src/edu/berkeley/sbp/GSS.java +++ b/src/edu/berkeley/sbp/GSS.java @@ -1,78 +1,165 @@ package edu.berkeley.sbp; import edu.berkeley.sbp.*; -import edu.berkeley.sbp.*; -import edu.berkeley.sbp.*; import edu.berkeley.sbp.util.*; +import edu.berkeley.sbp.Sequence.Position; +import edu.berkeley.sbp.Parser.Table.State; +import edu.berkeley.sbp.Parser.Table.Reduction; import java.io.*; import java.util.*; import java.lang.reflect.*; -////////////////////////////////////////////////////////////////////////////// -// TODO: -// -// - fix public/package/private status -// - -////////////////////////////////////////////////////////////////////////////// -// Optimizations to add -// -// ** NOTE: not all of these are appropriate for this class -- it is -// simply a list of optimizations not implemented. This -// 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 { public GSS() { } + private Phase.Node[] reducing_list = null; + public int resets = 0; + public int waits = 0; + + HashMapBag inhibited = new HashMapBag(); + HashMapBag assumed = new HashMapBag(); + HashMapBag waiting = new HashMapBag(); + HashMapBag performed = new HashMapBag(); + HashSet tail = new HashSet(); + /** corresponds to a positions between tokens the input stream; same as Tomita's U_i's */ - public class Phase { + public class Phase implements Invokable, IntegerMappable { + public int toInt() { return pos+1; } /** the token immediately after this phase */ public final Token token; + boolean reducing; + /** currently this is necessary only for the code() hack -- it doesn't actually correspond to the input */ private final int pos; /** FIXME */ - public Forest.Ref finalResult = null; + public Forest.Ref finalResult; - /** 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(); - private LinkedList pendingReduct = new LinkedList(); + /*private*/ IntPairMap hash; /* ALLOC */ /** the number of nodes in this phase */ - private int numNodes = 0; + private int numNodes; + + boolean closed; - boolean closed = false; + private boolean good; + private Phase next = null; private Token.Location location; - public Phase(Phase previous, Token token, Token.Location location) { + public final Parser parser; + + private Forest forest; + Phase prev; + public Phase(Phase prev, Parser parser, Phase previous, Token token, Token.Location location, Forest forest) { + this.prev = prev; + this.forest = forest; + this.parser = parser; this.pos = previous==null ? 0 : previous.pos+1; this.token = token; this.location = location; + inhibited.clear(); + assumed.clear(); + reset(); } - public boolean isDone() { return token == null; } + public void reset() { + tail.clear(); + waiting.clear(); + performed.clear(); + hash = new IntPairMap(); + good = false; + closed = false; + numNodes = 0; + reducing = false; + finalResult = null; + if (prev != null) prev.shift(this, forest); + } - private String error = "generic syntax error"; - public void checkFailure() throws Parser.Failed { - if (numNodes <= 0) - throw new Parser.Failed(error, getLocation()); + public void complain(Node n, HashMap> errors, boolean force) { + if (n.touched) return; + n.touched = true; + for(Position p : n.state) { + //if (!p.isLast()) { + if (((p.isFirst() || p.isLast()) && !force) || p.owner().name==null) { + for(Node n2 : n.parents()) + complain(n2, errors, force | p.isFirst()); + } else { + String seqname = p.owner().name; + HashSet hs = errors.get(seqname); + if (hs==null) errors.put(seqname, hs = new HashSet()); + hs.add(p.element()+""); + //String s = " while parsing " + seqname + ": expected a " + p.element(); + //"\n"; + /* + s += " parsed: "; + for(Position p2 = p.owner().firstp(); p2 != null && p2 != p && !p2.isLast(); p2 = p2.next()) s += (p2.element() + " "); + s += "\n"; + s += " expected: "; + for(Position p2 = p; p2 != null && !p2.isLast(); p2 = p2.next()) s += (p2.element() + " "); + */ + //s += "\n"; + //errors.add(s); + } + } + } + + public String black(Object o) { return "\033[30m"+o+"\033[0m"; } + public String red(Object o) { return "\033[31m"+o+"\033[0m"; } + public String green(Object o) { return "\033[32m"+o+"\033[0m"; } + public String yellow(Object o) { return "\033[33m"+o+"\033[0m"; } + public String blue(Object o) { return "\033[34m"+o+"\033[0m"; } + public String purple(Object o) { return "\033[35m"+o+"\033[0m"; } + public String cyan(Object o) { return "\033[36m"+o+"\033[0m"; } + public String el(Object e) { + String s = e.toString(); + if (s.length()==0 || s.charAt(0)!='\"' || s.charAt(s.length()-1)!='\"') return yellow(s); + s = s.substring(1); + s = s.substring(0, s.length()-1); + StringBuffer ret = new StringBuffer(); + for(int i=0; i" : token.toString(); + StringBuffer ret = new StringBuffer(); + ret.append("\n "); + ret.append(message); + HashMap> errors = new HashMap>(); + for(Node n : hash.values()) { + //System.out.println(n.state); + complain(n, errors, false); + } + for(String s : errors.keySet()) { + ret.append(" while parsing " + yellow(s)); + HashSet hs = errors.get(s); + if (hs.size()==1) ret.append(" expected " + yellow(el(hs.iterator().next())) + "\n"); + else { + ret.append(" expected "); + boolean first = true; + for(String s2 : hs) { + if (!first) ret.append(" or "); + first = false; + ret.append(yellow(el(s2))); + } + ret.append("\n"); + } + } + return ret.toString(); + } + + public boolean isDone() throws ParseFailed { + if (token != null) return false; + if (token==null && finalResult==null) + throw new ParseFailed(error(red("unexpected end of file\n")), + getLocation()); + return true; } public Token.Location getLocation() { return location; } @@ -84,265 +171,244 @@ 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) */ - public void newNode(Node parent, Forest pending, Parser.Table.State state, boolean fromEmptyReduction, Phase start) { - Node p = hash.get(code(state, start)); - if (p != null) newNode2(p, parent, pending, state, fromEmptyReduction, start); - else newNode3(parent, pending, state, fromEmptyReduction, start); + public boolean newNode(Node parent, Forest pending, State state, boolean fromEmptyReduction) { + Node p = hash.get(state, parent==null?null:parent.phase()); + if (p != null) return newNode2(p, parent, pending, state, fromEmptyReduction); + else return newNode3(parent, pending, state, fromEmptyReduction); + } + public void newNode(Node parent, Forest pending, State state, boolean fromEmptyReduction, Reduction reduction) { + int pos = parent==null?0:parent.phase()==null?0:parent.phase().pos; + Sequence owner = reduction==null ? null : reduction.position.owner(); + if (reduction!=null) { + if (inhibited.contains(pos, owner)) return; + /* + if (assumed.contains(pos, owner)) { + tail.add(new Waiting(parent, pending, state, fromEmptyReduction, reduction)); + return; + } + */ + if (owner.needs != null) + for(Sequence s : owner.needs) + if (!performed.contains(pos, s)) { + waiting.add(s, new Waiting(parent, pending, state, fromEmptyReduction, reduction)); + return; + } + if ((owner.needed != null && owner.needed.size()>0) || + (owner.hated != null && owner.hated.size()>0) || + (owner.hates != null && owner.hates.size()>0)) + performed.add(pos, owner); + } + if (!owner.lame) + newNode(parent, pending, state, fromEmptyReduction); + if (reduction!=null) inhibit(reduction, parent==null?0:parent.phase().pos); + if (reduction != null) { + boolean redo = true; + while(redo) { + redo = false; + for(Waiting w : waiting.getAll(owner)) { + if (w.parent==parent || (parent!=null&&w.parent!=null&&w.parent.phase()==parent.phase())) { + waiting.remove(owner, w); + w.perform(); + redo = true; + break; + } + } + } + } } - private void newNode2(Node p, Node parent, Forest pending, Parser.Table.State state, boolean fromEmptyReduction, Phase start) { + private boolean newNode2(Node p, Node parent, Forest pending, State state, boolean fromEmptyReduction) { p.holder.merge(pending); - if (p.parents.contains(parent)) return; - p.parents.add(parent, true); + if (p.parents().contains(parent)) return true; + p.parents().add(parent, true); if (p!=parent && !fromEmptyReduction) p.queueReductions(parent); + return true; } - private void newNode3(Node parent, Forest pending, Parser.Table.State state, boolean fromEmptyReduction, Phase start) { + private boolean newNode3(Node parent, Forest pending, State state, boolean fromEmptyReduction) { do { if (token != null && state.canShift(token)) break; if (state.isAccepting()) break; if (token==null) break; - 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 (!state.canReduce(token)) return false; //if (count > 1) break; //if (r.numPop == 0) break; //r.reduce(pending, parent, null, Phase.this, null); //return; } while(false); - Node n = new Node(parent, pending, state, start); // ALLOC + Node n = new Node(parent, pending, state, fromEmptyReduction); // ALLOC n.queueEmptyReductions(); - if (!fromEmptyReduction) n.queueReductions(); + if (!fromEmptyReduction) n.queueReductions(parent); + return true; } + public void uninhibit(int p, Sequence s) { + if (s.hated!=null) + for(Sequence s2 : s.hated) + inhibited.remove(p, s2); + } + + public void inhibit(Reduction r, int p) { + if (r.position.owner().hated == null) return; + // remember that dead states are still allowed to shift -- just not allowed to reduce + boolean reset = false; + for(Sequence seq : r.position.owner().hated) { + if (performed.contains(p,seq)) { + uninhibit(p, seq); + //System.out.println("\nresetting due to " + r.position.owner() + " killing " + seq); + //inhibited.clear(); + inhibited.add(p, seq); + //assumed = inhibited; + //inhibited = new HashMapBag(); + reset = true; + resets++; + throw new Reset(); + } + inhibited.add(p, seq); + } + } - boolean reducing = false; /** perform all reduction operations */ public void reduce() { - reducing = true; - HashSet s = new HashSet(); - s.addAll(hash.values()); - //while(pendingReduct.size()>0) - //pendingReduct.removeFirst().go(); - for(Phase.Node n : s) n.queueEmptyReductions(); - for(Phase.Node n : s) n.queueReductions(); + try { + reducing = true; + if (reducing_list==null || reducing_list.length < hash.size()) + reducing_list = new Phase.Node[hash.size() * 4]; + hash.toArray(reducing_list); + int num = hash.size(); + for(int i=0; inext */ - public void shift(Phase next, Forest result) { + public void shift(Phase next, Forest result) throws ParseFailed { + if (prev!=null) prev.hash = null; + this.next = next; 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; if (finalResult==null) finalResult = new Forest.Ref(); finalResult.merge(n.holder); } - if (!n.holder.valid()) continue; if (token == null) continue; - for(Parser.Table.State st : n.state.getShifts(token)) { - if (res == null) res = result; - next.newNode(n, res, st, true, this); - ok = true; - } + n.state.invokeShifts(token, this, result, n); } - 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(" candidate states:\n"); - for(Phase.Node n : hash.values()) { - //for(Sequence.Position p : n.state) error.append(" " + p + "\n"); - //error.append(" --\n"); - for(Parser.Table.Reduction r : n.state.getReductions(token)) error.append(" " + r + "\n"); - //error.append(" ==\n"); - } - next.error = error.toString(); - } + if (!good && token!=null) + throw new ParseFailed(error(red("unexpected character")+" "+purple(token)+" encountered at "+green(getLocation())+"\n"), + getLocation()); + if (token==null && finalResult==null) + throw new ParseFailed(error(red("unexpected end of file\n")), + getLocation()); // this massively improves GC performance - reductions = null; - hash = null; + //hash = null; } + + public class Waiting { + Node parent; + Forest pending; + State state; + boolean fromEmptyReduction; + Reduction reduction; + public Waiting(Node parent, Forest pending, State state, boolean fromEmptyReduction, Reduction reduction) { + waits++; + this.parent = parent; + this.pending = pending; + this.state = state; + this.fromEmptyReduction = fromEmptyReduction; + this.reduction = reduction; + } + public void perform() { + //System.out.println("performing: " + reduction.position); + newNode(parent, pending, state, fromEmptyReduction, reduction); + } + } // GSS Nodes ////////////////////////////////////////////////////////////////////////////// - //private HashMap pcache = new HashMap(); /** a node in the GSS */ - public final class Node { + public final class Node extends FastSet implements Invokable { + public boolean touched = false; private Forest.Ref holder = null; - - private HashMap cache = null; - - /** the set of nodes to which there is an edge starting at this node */ - public final FastSet parents = new FastSet(); /* ALLOC */ + private boolean allqueued = false; /** what state this node is in */ - public final Parser.Table.State state; + public final 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; + public Phase phase() { return Phase.this; } - 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; } + public FastSet parents() { return this; } - /** FIXME */ public void queueReductions() { - for(Node n2 : parents) - queueReductions(n2); + if (!reducing) return; + if (allqueued) return; + allqueued = true; + int where = parents().size(); + state.invokeReductions(token, this, this, null); } - private HashSet queued = new HashSet(); - /** FIXME */ public void queueReductions(Node n2) { - 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 <= 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); - } - } + if (!allqueued) { queueReductions(); return; } + state.invokeReductions(token, this, this, n2); } - - /** FIXME */ + public final void invoke(Reduction r, Node n, Node n2) { + if (n==null) { + if (r.numPop==0) r.reduce(this); + return; + } + if (r.numPop==0) return; + if (n2==null) r.reduce(n); + else r.reduce(n, n2); + } public void queueEmptyReductions() { - 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()); + if (!reducing) return; + state.invokeReductions(token, this, null, null); } - private Node(Node parent, Forest pending, Parser.Table.State state, Phase start) { + private boolean fe; + public boolean dead = false; + public boolean redo = false; + private Node(Node parent, Forest pending, State state, boolean fe) { + this.fe = fe; this.state = state; - if (pending != null) this.holder().merge(pending); - if (parent != null) parents.add(parent, true); - if (Phase.this.hash.get(code(state, start)) != null) throw new Error("severe problem!"); - Phase.this.hash.put(code(state, start), this); + this.holder().merge(pending); + Phase start = parent==null ? null : parent.phase(); + if (parent != null) parents().add(parent, true); + if (Phase.this.hash.get(state, start) != null) throw new Error("severe problem!"); + Phase.this.hash.put(state, start, this); Phase.this.numNodes++; - if (parent==null) holder().valid = true; // hack to make sure that the "base" node is always considered valid - } - } - - // 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.addFirst(this); - //pendingReductions++; - go(); - } - - /** perform the reduction */ - public void go() { - if (done) return; - done = true; - //pendingReduct.remove(this); - //pendingReductions--; - - if (r==null) { - 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 <= 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); - } - } - } else if (r.numPop != 1) { - 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); } } @@ -354,10 +420,4 @@ class GSS { if (a==null || b==null) return false; return a.equals(b); } - - /** this is something of a hack right now */ - private static long code(Parser.Table.State state, Phase start) { - return (((long)state.idx) << 32) | (start==null ? 0 : start.pos); - } - public boolean yak = false; }