X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FGSS.java;h=ca8e1d505368093ab6d2f3598a6215291d9bda13;hp=1a8ef11e87627454309c566e39d587bd330950e7;hb=dc9bb3a45ed306e2e35549076842b3e74efecb48;hpb=82f9b8d4a2fadb14cb004e5cc9f14944458f2e6c diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java index 1a8ef11..ca8e1d5 100644 --- a/src/edu/berkeley/sbp/GSS.java +++ b/src/edu/berkeley/sbp/GSS.java @@ -1,3 +1,5 @@ +// Copyright 2006 all rights reserved; see LICENSE file for BSD-style license + package edu.berkeley.sbp; import edu.berkeley.sbp.*; import edu.berkeley.sbp.util.*; @@ -10,386 +12,182 @@ import java.lang.reflect.*; /** implements Tomita's Graph Structured Stack */ class GSS { - static int count = 0; - static int shifts = 0; - static int reductions = 0; - int resets = 0; - int waits = 0; - - public GSS() { } - - private Phase.Node[] reducing_list = null; + Input input; + private Parser parser; + public GSS(Input input, Parser parser) { this.input = input; this.parser = parser;} + public Input getInput() { return input; } - // FIXME: right now, these are the performance bottleneck - HashMapBag waiting = new HashMapBag(); - HashMapBag performed = new HashMapBag(); - HashMapBag lastperformed = new HashMapBag(); - HashMapBag expected = new HashMapBag(); - - /** FIXME */ - Forest.Many finalResult; + int numNewNodes = 0; + int numOldNodes = 0; + int viewPos = 0; + int numReductions = 0; /** corresponds to a positions between tokens the input stream; same as Tomita's U_i's */ - class Phase implements Invokable.Node>, 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(); + + public Forest.Many finalResult; + private PriorityQueue reductionQueue = new PriorityQueue(); - public Iterator iterator() { return hash.iterator(); } - public void invoke(State st, Forest result, Node n) { - shifts++; - good |= next.newNode(n, result, st, false); + Parser parser() { return parser; } + public void addReduction(Reduction r) { + //System.out.println("+ " + r); + parser.spin(); + reductionQueue.add(r); + } + public void invoke(State st, Result result) { + parser.spin(); + good |= next.newNode(result, st, false); } /** the token immediately after this phase */ final Tok token; + final int pos; - private final int pos; - - boolean reducing; - private IntPairMap hash; /* ALLOC */ - private boolean closed; - private boolean good; + public IntPairMap hash = new IntPairMap(); /* ALLOC */ + private boolean good = false; private Phase next = null; private Phase prev; private Input.Location location; - public final Parser parser; - + private Input.Location nextLocation; + private Input.Location prevLocation; + private Forest forest; - public Phase(Phase prev, Parser parser, Phase previous, Tok token, Input.Location location, Forest forest) throws ParseFailed { + public Phase(State startState) throws ParseFailed, IOException { + this(null, null); + Result primordealResult = new Result(null, null, null); + newNode(primordealResult, startState, true); + } + public Phase(Phase prev, Forest forest) throws ParseFailed, IOException { + this.prevLocation = input.getLocation(); + this.token = (Tok)input.next(); + this.location = input.getLocation(); this.prev = prev; this.forest = forest; - this.parser = parser; - this.pos = previous==null ? 0 : previous.pos+1; - this.token = token; - this.location = location; - performed.clear(); - reset(); - } - - public void reset() throws ParseFailed { - waiting.clear(); - expected.clear(); - lastperformed.clear(); - lastperformed.addAll(performed); - performed.clear(); - hash = new IntPairMap(); - reset = false; - good = false; - closed = false; - reducing = false; - finalResult = null; + this.pos = prev==null ? 0 : prev.pos+1; + this.nextLocation = input.getLocation(); if (prev != null) prev.shift(this, forest); + numReductions = 0; + + int minPhasePos = Integer.MAX_VALUE; + int maxOrd = -1; + Reduction best = null; + //System.out.println("=============================================================================="); + while(!reductionQueue.isEmpty()) { + Reduction r = reductionQueue.poll(); + //System.out.println("- " + r); + if (r.parentPhase() != null) + if (r.parentPhase().pos > minPhasePos) + throw new Error(); + r.perform(); + if (r.parentPhase() != null) { + if (r.parentPhase().pos < minPhasePos) { + minPhasePos = r.parentPhase().pos; + maxOrd = r.reduction().ord; + best = r; + } else if (r.parentPhase().pos == minPhasePos) { + /* + if (best != null && Parser.mastercache.comparePositions(r.reduction(), best.reduction()) < 0) + throw new Error("\n"+r+"\n"+best+"\n"+ + Parser.mastercache.comparePositions(r.reduction(), best.reduction())+"\n"+r.compareTo(best)+ + "\n"+(r.reduction().ord-best.reduction().ord)); + */ + maxOrd = r.reduction().ord; + best = r; + } + } + numReductions++; + } + if (token==null) shift(null, null); } - public boolean isDone() throws ParseFailed { if (token != null) return false; if (token==null && finalResult==null) - throw new ParseFailed(ParseFailed.error(ANSI.red("unexpected end of file\n"), token, hash.values()), getLocation()); + ParseFailed.error("unexpected end of file", this); return true; } + public Input.Location getPrevLocation() { return prevLocation; } public Input.Location getLocation() { return location; } + public Input.Region getRegion() { return prevLocation.createRegion(location); } + public Input.Location getNextLocation() { return nextLocation; } + public boolean isFrontier() { return hash!=null; } - /** add a new node (merging with existing nodes if possible) - * @param parent the parent of the new node - * @param result the SPPF result corresponding to the new node - * @param state the state that the new node is in - * @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 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, Position reduction) { - int pos = parent==null?0:parent.phase()==null?0:parent.phase().pos; - Sequence owner = reduction==null ? null : reduction.owner(); - if (reduction!=null) { - if (owner.hates!=null) { - for (Sequence s : performed.getAll(pos)) - if (owner.hates.contains(s)) - return; - for (Sequence s : lastperformed.getAll(pos)) - if (owner.hates.contains(s)) { - //System.out.println("now expecting ["+pos+"] => " + s); - expected.add(pos, s); - 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 (!performed.contains(pos, owner)) { - performed.add(pos, owner); - if (owner.hated != null) - for(Sequence seq : owner.hated) - if (performed.contains(pos, seq)) { - performed.remove(pos, seq); - reset = true; - } - } + /** perform all shift operations, adding promoted nodes to next */ + private void shift(Phase next, Forest result) throws ParseFailed { + this.next = next; + // this massively improves GC performance + if (prev != null) { + IntPairMap h = prev.hash; + prev.hash = null; + prev.performed = null; + for(Node n : h) + n.check(); } - if (!owner.lame) - newNode(parent, pending, state, fromEmptyReduction); - 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; - } - } + numOldNodes = hash.size(); + for(Node n : hash.values()) { + if (token == null && n.state().isAccepting()) { + if (finalResult==null) finalResult = new Forest.Many(); + for(Result r : n) + finalResult.merge(r.getForest()); } + if (token == null) continue; + n.state().invokeShifts(token, this, new Result(result, n, null)); } + numNewNodes = next==null ? 0 : next.hash.size(); + viewPos = this.pos; + if (!good && token!=null) ParseFailed.error("unexpected character", this); + if (token==null && finalResult==null) ParseFailed.error("unexpected end of file", this); + for(Node n : hash) n.check(); } - private boolean newNode2(Node p, Node parent, Forest pending, State state, boolean fromEmptyReduction) { - if (p.merge(parent, pending)) return true; - p.parents().add(parent, true); - if (p!=parent && !fromEmptyReduction && reducing) p.performReductions(parent); - return true; + void newNodeFromReduction(Result result, State state, Position reduction) { + int pos = result.phase().pos; + Sequence owner = reduction.owner(); + for(Sequence s : owner.hates()) + if (performed.contains(pos, s)) + return; + for(Sequence s : owner.needs()) + if (!performed.contains(pos, s)) + return; + if (owner.needed_or_hated && !performed.contains(pos, owner)) + performed.add(pos, owner); + if (state!=null) + newNode(result, state, reduction.pos<=0); } - private boolean newNode3(Node parent, Forest pending, State state, boolean fromEmptyReduction) { + /** add a new node (merging with existing nodes if possible) + * @param parent the parent of the new node + * @param result the SPPF result corresponding to the new node + * @param state the state that the new node is in + * @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 true; } do { if (token != null && state.canShift(token)) break; if (state.isAccepting()) break; if (token==null) break; 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); // ALLOC - if (reducing) { - n.performEmptyReductions(); - if (!fromEmptyReduction) n.performReductions(parent); - } + Node n = new Node(Phase.this, result, state, fromEmptyReduction); // ALLOC + for(Object s : state.conjunctStates) + newNode(new Result(null, n, null), (State)s, fromEmptyReduction); return true; } - /** perform all reduction operations */ - public void reduce() throws ParseFailed { - 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) throws ParseFailed { - // this massively improves GC performance - if (prev!=null && parser.helpgc) { - prev.hash = null; - } - this.next = next; - closed = true; - Forest res = null; - boolean ok = false; - for(Phase.Node n : hash.values()) { - if (token == null && n.state.isAccepting()) { - if (finalResult==null) finalResult = new Forest.Many(); - for(Object f : n.results()) - finalResult.merge((Forest)f); - } - if (token == null) continue; - n.state.invokeShifts(token, this, result, n); - } - - if (!good && token!=null) - throw new ParseFailed(ParseFailed.error(ANSI.red("unexpected character ")+" \'"+ - ANSI.purple(StringUtil.escapify(token+"", "\\\'\r\n"))+ - "\' encountered at "+ - ANSI.green(getLocation())+"\n", token, hash.values()), - getLocation()); - if (token==null && finalResult==null) - throw new ParseFailed(ParseFailed.error(ANSI.red("unexpected end of file\n"), token, hash.values()), - getLocation()); - } - - - class Waiting { - Node parent; - Forest pending; - State state; - boolean fromEmptyReduction; - Position reduction; - public Waiting(Node parent, Forest pending, State state, boolean fromEmptyReduction, Position 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); - } - } - - // Node ///////////////////////////////////////////////////////////////////////////////// - - /** a node in the GSS */ - final class Node implements Invokable, IntegerMappable, GraphViz.ToGraphViz { - public FastSet set = new FastSet(); - - - private boolean allqueued = false; - - /** 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 Phase phase() { return Phase.this; } - - private HashSet resultMap = new HashSet(); - public Iterable results() { return resultMap; } - public FastSet parents() { return set; } - public boolean merge(Node parent, Forest result) { - // FIXME: inefficient! - for(Forest.Many f : results()) { - if (f.parents.contains(parent) /* UGLY: */ && f.parents.size()==1) { - f.merge(result); - return true; - } - } - Forest.Many f = new Forest.Many(); - f.parents.add(parent); - f.merge(result); - resultMap.add(f); - set.add(parent, true); - return false; - } - - public void performReductions() { - if (allqueued) return; - allqueued = true; - state.invokeReductions(token, this, this, null); - } - - public void performReductions(Node n2) { - if (!allqueued) performReductions(); - else state.invokeReductions(token, this, this, n2); - } - - public void performEmptyReductions() { state.invokeReductions(token, this, null, null); } - public final void invoke(Position r, Node n, Node n2) { - reductions++; - if (n==null || n2==null || r.pos==0) { - if (r.pos==0) { - if (n==null) n = this; - else return; - } - if (n==null) return; - Forest[] holder = new Forest[r.pos]; - if (r.pos==0) n.finish(r, r.zero(), n.phase()); - else n.reduce(r, r.pos-1, n.phase(), null); - } else { - if (r.pos<=0) throw new Error("called wrong form of reduce()"); - int pos = r.pos-1; - n.reduce(r, pos, n.phase(), n2); - } - } - - public void reduce(Position r, int pos, Phase target, Node only) { - Forest[] holder = r.holder; - Forest old = holder[pos]; - - HashSet rr = new HashSet(); - for(Forest result : results()) rr.add(result); - for(Forest result : rr) - for(Node child : ((Forest.Many)result).parents) { - if (only != null && child!=only) continue; - holder[pos] = result; - if (pos==0) child.finish(r, r.rewrite(child.phase().getLocation().createRegion(phase().getLocation())), target); - else child.reduce(r, pos-1, target, null); - } - - holder[pos] = old; - } - - public void finish(Position r, Forest result, Phase target) { - Parser.Table.State state0 = state.gotoSetNonTerminals.get(r.owner()); - if (result==null) throw new Error(); - if (state0!=null) - target.newNode(this, result, state0, r.pos<=0, r); - } - - private Node(Node parent, Forest pending, State state) { - this.state = state; - this.merge(parent, 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); - } - public int toInt() { return idx; } - private final int idx = node_idx++; - - // GraphViz ////////////////////////////////////////////////////////////////////////////// - - public GraphViz.Node toGraphViz(GraphViz gv) { - if (gv.hasNode(this)) return gv.createNode(this); - GraphViz.Node n = gv.createNode(this); - n.label = ""+state.toStringx(); - n.shape = "rectangle"; - n.fill = "green"; - for(Forest result : results()) n.edge(result, ""); - for(Node parent : parents()) n.edge(parent, ""); - ((GraphViz.Group)phase().toGraphViz(gv)).add(n); - return n; - } - public boolean isTransparent() { return false; } - public boolean isHidden() { return false; } - - } - private int node_idx = 0; - public int toInt() { return pos+1; } 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 GSS getGSS() { return GSS.this; } // GraphViz ////////////////////////////////////////////////////////////////////////////// @@ -404,5 +202,17 @@ class GSS { public boolean isTransparent() { return false; } public boolean isHidden() { return false; } + public void dumpGraphViz(String filename) throws IOException { + FileOutputStream fos = new FileOutputStream(filename); + PrintWriter p = new PrintWriter(new OutputStreamWriter(fos)); + GraphViz gv = new GraphViz(); + for(Object n : this) + ((Node)n).toGraphViz(gv); + gv.dump(p); + p.flush(); + p.close(); + } + } + }