1 // Copyright 2006-2007 all rights reserved; see LICENSE file for BSD-style license
3 package edu.berkeley.sbp;
4 import edu.berkeley.sbp.*;
5 import edu.berkeley.sbp.util.*;
6 import edu.berkeley.sbp.Parser.Table.*;
7 import edu.berkeley.sbp.Sequence.Pos;
8 import edu.berkeley.sbp.Sequence.Pos;
11 import java.lang.reflect.*;
13 /** implements Tomita's Graph Structured Stack */
17 private Parser parser;
18 public GSS(Input input, Parser parser) { this.input = input; this.parser = parser;}
19 public Input getInput() { return input; }
22 HashSet<Reduction> finishedReductions = new HashSet<Reduction>();
27 int numReductions = 0;
29 /** corresponds to a positions <i>between tokens</i> the input stream; same as Tomita's U_i's */
30 class Phase<Tok> implements Invokable<State, StateNode, Forest>, IntegerMappable, GraphViz.ToGraphViz, Iterable<StateNode> {
32 // FIXME: right now, these are the performance bottleneck
33 private HashMapBag<Integer,Integer> performed = new HashMapBag<Integer,Integer>();
35 public Forest.Many finalResult;
36 private PriorityQueue<Reduction> reductionQueue = new PriorityQueue<Reduction>();
38 Parser parser() { return parser; }
39 public void addReduction(Reduction r) {
40 //System.out.println("+ " + r);
42 reductionQueue.add(r);
45 public void invoke(State st, StateNode pred, Forest f) {
47 good |= next.newNode(f, null, pred, st, false);
50 /** the token immediately after this phase */
53 public IntPairMap<StateNode> hash = new IntPairMap<StateNode>(); /* ALLOC */
54 private boolean good = false;
55 private Phase next = null;
57 private Input.Location location;
58 private Input.Location nextLocation;
60 private Forest forest;
62 public Phase(State startState) throws ParseFailed, IOException {
64 newNode(null, null, null, startState, true);
66 public Phase(Phase prev, Forest forest) throws ParseFailed, IOException {
67 this.location = input.getLocation();
68 this.token = (Tok)input.next();
69 this.nextLocation = input.getLocation();
72 this.pos = prev==null ? 0 : prev.pos+1;
73 if (prev != null) prev.shift(this, forest);
76 finishedReductions.clear();
79 int minPhasePos = Integer.MAX_VALUE;
80 Reduction best = null;
81 //System.out.println("==============================================================================");
82 while(!reductionQueue.isEmpty()) {
83 Reduction r = reductionQueue.poll();
84 //System.out.println("- " + r);
85 if (r.predPhase() != null)
86 if (r.predPhase().pos > minPhasePos)
89 if (r.predPhase() != null) {
90 if (r.predPhase().pos < minPhasePos) {
91 minPhasePos = r.predPhase().pos;
93 } else if (r.predPhase().pos == minPhasePos) {
95 if (best != null && Parser.mastercache.comparePositions(r.reduction(), best.reduction()) < 0)
96 throw new Error("\n"+r+"\n"+best+"\n"+
97 Parser.mastercache.comparePositions(r.reduction(), best.reduction())+"\n"+r.compareTo(best)+
98 "\n"+(r.reduction().ord-best.reduction().ord));
104 finishedReductions.add(r);
108 if (token==null) shift(null, null);
111 public boolean isDone() throws ParseFailed {
112 if (token != null) return false;
113 if (token==null && finalResult==null)
114 ParseFailed.error("unexpected end of file", this, null,
115 getLocation().createRegion(getLocation()));
119 public Input.Location getLocation() { return location; }
120 public Input.Location getNextLocation() { return nextLocation; }
121 public boolean isFrontier() { return hash!=null; }
123 /** perform all shift operations, adding promoted nodes to <tt>next</tt> */
124 private void shift(Phase next, Forest f) throws ParseFailed {
126 // this massively improves GC performance
128 IntPairMap<StateNode> h = prev.hash;
130 prev.performed = null;
131 for(StateNode n : h) n.check();
133 numOldNodes = hash.size();
134 for(StateNode n : hash.values()) {
135 if (token == null && n.state().isAccepting()) {
136 if (finalResult==null) finalResult = new Forest.Many();
137 for(ResultNode r : n)
138 finalResult.merge(r.getForest());
140 if (token == null) continue;
141 n.state().invokeShifts(token, this, n, f);
143 numNewNodes = next==null ? 0 : next.hash.size();
146 if (!good && token!=null) {
147 String toks = token+"";
148 if (toks.length()==1 && toks.charAt(0) == edu.berkeley.sbp.chr.CharAtom.left) {
149 ParseFailed.error("unexpected increase in indentation", this,
150 token, getRegionFromThisToNext());
151 } else if (toks.length()==1 && toks.charAt(0) == edu.berkeley.sbp.chr.CharAtom.right) {
152 ParseFailed.error("unexpected decrease in indentation", this,
153 token, getRegionFromThisToNext());
155 ParseFailed.error("unexpected character '"+ANSI.cyan(StringUtil.escapify(token+"",
157 this, token, getRegionFromThisToNext());
160 if (token==null && finalResult==null)
161 ParseFailed.error("unexpected end of file", this, null,
162 getLocation().createRegion(getLocation()));
163 for(StateNode n : hash) n.check();
166 Input.Region getRegionFromThisToNext() {
167 return getLocation().createRegion(getNextLocation());
170 void newNodeFromReduction(Forest f, Pos reduction, StateNode pred) {
171 int pos = pred.phase().pos;
172 for(int s : reduction.hates())
173 if (performed.contains(pos, s))
175 for(int s : reduction.needs())
176 if (!performed.contains(pos, s))
178 if (reduction.owner_needed_or_hated() && !performed.contains(pos, reduction.provides()))
179 performed.add(pos, reduction.provides());
180 Parser.Table.State state = (Parser.Table.State)pred.state().gotoSetNonTerminals.get(reduction);
182 newNode(f, reduction, pred, state, reduction.numPops()<=0);
185 /** add a new node (merging with existing nodes if possible)
186 * @param parent the parent of the new node
187 * @param result the SPPF result corresponding to the new node
188 * @param state the state that the new node is in
189 * @param fromEmptyReduction true iff this node is being created as a result of a reduction of length zero (see GRMLR paper)
190 * @param start the earliest part of the input contributing to this node (used to make merging decisions)
192 private boolean newNode(Forest f, Pos reduction, StateNode pred, State state, boolean fromEmptyReduction) {
193 StateNode p = pred==null ? null : hash.get(state, pred.phase());
195 p.addResult(f, reduction, pred);
196 return !state.doomed();
199 if (token != null && state.canShift(token)) break;
200 if (state.isAccepting()) break;
201 if (token==null) break;
202 if (!state.canReduce(token)) return false;
204 StateNode n = new StateNode(Phase.this, f, reduction, pred, state, fromEmptyReduction); // ALLOC
205 /** FIXME: this null-result can be used to notice bogus/dead states */
206 for(Object s : state.conjunctStates)
207 newNode(null, null, n, (State)s, fromEmptyReduction);
208 return !n.state().doomed();
211 public int toInt() { return pos+1; }
212 public int size() { return hash==null ? 0 : hash.size(); }
213 public int pos() { return pos; }
214 public Tok getToken() { return token; }
215 public Iterator<StateNode> iterator() { return hash.iterator(); }
216 public GSS getGSS() { return GSS.this; }
218 // GraphViz //////////////////////////////////////////////////////////////////////////////
220 public GraphViz.StateNode toGraphViz(GraphViz gv) {
221 if (gv.hasNode(this)) return gv.createNode(this);
222 GraphViz.Group g = gv.createGroup(this);
223 g.label = "Phase " + pos;
228 public boolean isTransparent() { return false; }
229 public boolean isHidden() { return false; }
231 public void dumpGraphViz(String filename) throws IOException {
232 FileOutputStream fos = new FileOutputStream(filename);
233 PrintWriter p = new PrintWriter(new OutputStreamWriter(fos));
234 GraphViz gv = new GraphViz();
236 ((StateNode)n).toGraphViz(gv);