X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FGSS.java;h=2e573486c9e8d3ff80cd13cfabb5d24ad489fed1;hp=f0a4cea21c0f741f4247c0f662192bd1bdfe9840;hb=c53fc2952c7885d727500ce404887d552c5dec5f;hpb=f57e7386abbd8d301f46c0f68a32bffbb1c15253 diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java index f0a4cea..2e57348 100644 --- a/src/edu/berkeley/sbp/GSS.java +++ b/src/edu/berkeley/sbp/GSS.java @@ -1,10 +1,11 @@ -// Copyright 2006 all rights reserved; see LICENSE file for BSD-style license +// Copyright 2006-2007 all rights reserved; see LICENSE file for BSD-style license package edu.berkeley.sbp; import edu.berkeley.sbp.*; import edu.berkeley.sbp.util.*; import edu.berkeley.sbp.Parser.Table.*; -import edu.berkeley.sbp.Sequence.Position; +import edu.berkeley.sbp.Sequence.Pos; +import edu.berkeley.sbp.Sequence.Pos; import java.io.*; import java.util.*; import java.lang.reflect.*; @@ -13,131 +14,172 @@ import java.lang.reflect.*; class GSS { Input input; - public GSS(Input input) { this.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 performed = new HashMapBag(); - - /** FIXME */ - Forest.Many finalResult; + /* + HashSet finishedReductions = new HashSet(); + */ + 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, 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 ArrayList reductionQueue = new ArrayList(); + public Forest.Many finalResult; + private PriorityQueue reductionQueue = new PriorityQueue(); - public void invoke(State st, Result result, Object o) { - //shifts++; - good |= next.newNode(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, StateNode pred, Forest f) { + parser.spin(); + good |= next.newNode(f, null, pred, st, false); } /** the token immediately after this phase */ final Tok token; final int pos; - - public IntPairMap hash; /* ALLOC */ - private boolean good; + public IntPairMap hash = new IntPairMap(); /* ALLOC */ + private boolean good = false; private Phase next = null; private Phase prev; private Input.Location location; private Input.Location nextLocation; - private Input.Location prevLocation; private Forest forest; - public Phase(Phase prev, Phase previous, Tok token, Input.Location location, - Input.Location nextLocation, Forest forest) throws ParseFailed { - this.prevLocation = prev==null ? location : prev.getLocation(); + public Phase(State startState) throws ParseFailed, IOException { + this(null, null); + newNode(null, null, null, startState, true); + } + public Phase(Phase prev, Forest forest) throws ParseFailed, IOException { + this.location = input.getLocation(); + this.token = (Tok)input.next(); + this.nextLocation = input.getLocation(); this.prev = prev; this.forest = forest; - this.pos = previous==null ? 0 : previous.pos+1; - this.token = token; - this.location = location; - this.nextLocation = nextLocation; - performed.clear(); - hash = new IntPairMap(); - good = false; - finalResult = null; + this.pos = prev==null ? 0 : prev.pos+1; if (prev != null) prev.shift(this, forest); + numReductions = 0; + /* + finishedReductions.clear(); + */ + + int minPhasePos = Integer.MAX_VALUE; + Reduction best = null; + //System.out.println("=============================================================================="); + while(!reductionQueue.isEmpty()) { + Reduction r = reductionQueue.poll(); + //System.out.println("- " + r); + if (r.predPhase() != null) + if (r.predPhase().pos > minPhasePos) + throw new Error(); + r.perform(); + if (r.predPhase() != null) { + if (r.predPhase().pos < minPhasePos) { + minPhasePos = r.predPhase().pos; + best = r; + } else if (r.predPhase().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)); + */ + best = r; + } + } + /* + finishedReductions.add(r); + */ + numReductions++; + } + if (token==null) shift(null, null); } - public boolean isFrontier() { return next==null; } public boolean isDone() throws ParseFailed { if (token != null) return false; if (token==null && finalResult==null) - ParseFailed.error("unexpected end of file", this); + ParseFailed.error("unexpected end of file", this, null, + getLocation().createRegion(getLocation())); return true; } - public Input.Location getPrevLocation() { return prevLocation; } public Input.Location getLocation() { return location; } - public Input.Region getRegion() { return getPrevLocation().createRegion(getLocation()); } public Input.Location getNextLocation() { return nextLocation; } + public boolean isFrontier() { return hash!=null; } /** perform all shift operations, adding promoted nodes to next */ - public void shift(Phase next, Forest result) throws ParseFailed { - // this massively improves GC performance - if (prev!=null) prev.hash = null; + private void shift(Phase next, Forest f) throws ParseFailed { this.next = next; - for(Node n : hash.values()) { + // this massively improves GC performance + if (prev != null) { + IntPairMap h = prev.hash; + prev.hash = null; + prev.performed = null; + for(StateNode n : h) n.check(); + } + numOldNodes = hash.size(); + for(StateNode n : hash.values()) { if (token == null && n.state().isAccepting()) { if (finalResult==null) finalResult = new Forest.Many(); - for(Result r : n) + for(ResultNode r : n) finalResult.merge(r.getForest()); } if (token == null) continue; - n.state().invokeShifts(token, this, new Result(result, n, null), null); + n.state().invokeShifts(token, this, n, f); } - if (!good && token!=null) ParseFailed.error("unexpected character", this); - if (token==null && finalResult==null) ParseFailed.error("unexpected end of file", this); - } - - /** perform all reduction operations */ - public void reduce() throws ParseFailed { - Reduction last = null; - while(!reductionQueue.isEmpty()) { - Reduction r = null; - - // ugly - OUTER: for(int i=0; i 0) - continue OUTER; - } - r = reductionQueue.get(i); - reductionQueue.remove(r); - break; - } - - /* - if (last == null) last = r; - else if (r.compareTo(last) > 0) last = r; - else if (r.compareTo(last) < 0) { - if (r.targetPhase() != null) - System.out.println("err " + last.compareTo(r) + " " + last.targetPhase().pos() + - " " + r.targetPhase().pos() + " " + pos); + 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) { + ParseFailed.error("unexpected increase in indentation", this, + token, getRegionFromThisToNext()); + } else if (toks.length()==1 && toks.charAt(0) == edu.berkeley.sbp.chr.CharAtom.right) { + ParseFailed.error("unexpected decrease in indentation", this, + token, getRegionFromThisToNext()); + } else { + ParseFailed.error("unexpected character '"+ANSI.cyan(StringUtil.escapify(token+"", + "\\\'\r\n"))+"'", + this, token, getRegionFromThisToNext()); } - */ - - r.perform(); } + if (token==null && finalResult==null) + ParseFailed.error("unexpected end of file", this, null, + getLocation().createRegion(getLocation())); + for(StateNode n : hash) n.check(); + } + + Input.Region getRegionFromThisToNext() { + return getLocation().createRegion(getNextLocation()); } - public void newNodeFromReduction(Result result, State state, boolean fromEmptyReduction, Position reduction) { - int pos = result.phase().pos; - Sequence owner = reduction.owner(); - for(Sequence s : owner.hates) + void newNodeFromReduction(Forest f, Pos reduction, StateNode pred) { + int pos = pred.phase().pos; + for(int s : reduction.hates()) if (performed.contains(pos, s)) return; - for(Sequence s : owner.needs) + for(int s : reduction.needs()) if (!performed.contains(pos, s)) return; - if (owner.needed_or_hated && !performed.contains(pos, owner)) - performed.add(pos, owner); + 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, fromEmptyReduction); + newNode(f, reduction, pred, state, reduction.numPops()<=0); } /** add a new node (merging with existing nodes if possible) @@ -147,29 +189,35 @@ 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 boolean newNode(Result result, State state, boolean fromEmptyReduction) { - Node p = hash.get(state, result.phase()); - if (p != null) { p.merge(result); return true; } + private boolean newNode(Forest f, Pos reduction, StateNode pred, State state, boolean fromEmptyReduction) { + StateNode 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); - new Node(Phase.this, result, state, fromEmptyReduction); // ALLOC - return true; + StateNode n = new StateNode(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(null, null, n, (State)s, fromEmptyReduction); + return !n.state().doomed(); } 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 Iterator iterator() { return hash.iterator(); } public GSS getGSS() { return GSS.this; } // GraphViz ////////////////////////////////////////////////////////////////////////////// - public GraphViz.Node toGraphViz(GraphViz gv) { + public GraphViz.StateNode toGraphViz(GraphViz gv) { if (gv.hasNode(this)) return gv.createNode(this); GraphViz.Group g = gv.createGroup(this); g.label = "Phase " + pos; @@ -180,6 +228,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) + ((StateNode)n).toGraphViz(gv); + gv.dump(p); + p.flush(); + p.close(); + } + } }