1 // Copyright 2006 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.Position;
10 import java.lang.reflect.*;
12 /** implements Tomita's Graph Structured Stack */
16 private Parser parser;
17 public GSS(Input input, Parser parser) { this.input = input; this.parser = parser;}
18 public Input getInput() { return input; }
23 int numReductions = 0;
25 /** corresponds to a positions <i>between tokens</i> the input stream; same as Tomita's U_i's */
26 class Phase<Tok> implements Invokable<State, Result>, IntegerMappable, GraphViz.ToGraphViz, Iterable<Node> {
28 // FIXME: right now, these are the performance bottleneck
29 private HashMapBag<Integer,Sequence> performed = new HashMapBag<Integer,Sequence>();
31 public Forest.Many finalResult;
32 private PriorityQueue<Reduction> reductionQueue = new PriorityQueue<Reduction>();
34 Parser parser() { return parser; }
35 public void addReduction(Reduction r) {
36 //System.out.println("+ " + r);
38 reductionQueue.add(r);
40 public void invoke(State st, Result result) {
42 good |= next.newNode(result, st, false);
45 /** the token immediately after this phase */
49 public IntPairMap<Node> hash = new IntPairMap<Node>(); /* ALLOC */
50 private boolean good = false;
51 private Phase next = null;
53 private Input.Location location;
54 private Input.Location nextLocation;
56 private Forest forest;
58 public Phase(State startState) throws ParseFailed, IOException {
60 Result primordealResult = new Result(null, null, null);
61 newNode(primordealResult, startState, true);
63 public Phase(Phase prev, Forest forest) throws ParseFailed, IOException {
64 this.location = input.getLocation();
65 this.token = (Tok)input.next();
66 this.nextLocation = input.getLocation();
69 this.pos = prev==null ? 0 : prev.pos+1;
70 if (prev != null) prev.shift(this, forest);
73 int minPhasePos = Integer.MAX_VALUE;
75 Reduction best = null;
76 //System.out.println("==============================================================================");
77 while(!reductionQueue.isEmpty()) {
78 Reduction r = reductionQueue.poll();
79 //System.out.println("- " + r);
80 if (r.parentPhase() != null)
81 if (r.parentPhase().pos > minPhasePos)
84 if (r.parentPhase() != null) {
85 if (r.parentPhase().pos < minPhasePos) {
86 minPhasePos = r.parentPhase().pos;
87 maxOrd = r.reduction().ord;
89 } else if (r.parentPhase().pos == minPhasePos) {
91 if (best != null && Parser.mastercache.comparePositions(r.reduction(), best.reduction()) < 0)
92 throw new Error("\n"+r+"\n"+best+"\n"+
93 Parser.mastercache.comparePositions(r.reduction(), best.reduction())+"\n"+r.compareTo(best)+
94 "\n"+(r.reduction().ord-best.reduction().ord));
96 maxOrd = r.reduction().ord;
102 if (token==null) shift(null, null);
105 public boolean isDone() throws ParseFailed {
106 if (token != null) return false;
107 if (token==null && finalResult==null)
108 ParseFailed.error("unexpected end of file", this, null,
109 getLocation().createRegion(getLocation()));
113 public Input.Location getLocation() { return location; }
114 public Input.Location getNextLocation() { return nextLocation; }
115 public boolean isFrontier() { return hash!=null; }
117 /** perform all shift operations, adding promoted nodes to <tt>next</tt> */
118 private void shift(Phase next, Forest result) throws ParseFailed {
120 // this massively improves GC performance
122 IntPairMap<Node> h = prev.hash;
124 prev.performed = null;
125 for(Node n : h) n.check();
127 numOldNodes = hash.size();
128 for(Node n : hash.values()) {
129 if (token == null && n.state().isAccepting()) {
130 if (finalResult==null) finalResult = new Forest.Many();
132 finalResult.merge(r.getForest());
134 if (token == null) continue;
135 n.state().invokeShifts(token, this, new Result(result, n, null));
137 numNewNodes = next==null ? 0 : next.hash.size();
139 if (!good && token!=null) {
140 String toks = token+"";
141 if (toks.length()==1 && toks.charAt(0) == edu.berkeley.sbp.chr.CharAtom.left) {
142 ParseFailed.error("unexpected increase in indentation", this,
143 token, getRegionFromThisToNext());
144 } else if (toks.length()==1 && toks.charAt(0) == edu.berkeley.sbp.chr.CharAtom.right) {
145 ParseFailed.error("unexpected decrease in indentation", this,
146 token, getRegionFromThisToNext());
148 ParseFailed.error("unexpected character '"+ANSI.cyan(StringUtil.escapify(token+"",
150 this, token, getRegionFromThisToNext());
153 if (token==null && finalResult==null)
154 ParseFailed.error("unexpected end of file", this, null,
155 getLocation().createRegion(getLocation()));
156 for(Node n : hash) n.check();
159 Input.Region getRegionFromThisToNext() {
160 return getLocation().createRegion(getNextLocation());
163 void newNodeFromReduction(Result result, State state, Position reduction) {
164 int pos = result.phase().pos;
165 Sequence owner = reduction.owner();
166 for(Sequence s : owner.hates())
167 if (performed.contains(pos, s))
169 for(Sequence s : owner.needs())
170 if (!performed.contains(pos, s))
172 if (owner.needed_or_hated && !performed.contains(pos, owner))
173 performed.add(pos, owner);
175 newNode(result, state, reduction.pos<=0);
178 /** add a new node (merging with existing nodes if possible)
179 * @param parent the parent of the new node
180 * @param result the SPPF result corresponding to the new node
181 * @param state the state that the new node is in
182 * @param fromEmptyReduction true iff this node is being created as a result of a reduction of length zero (see GRMLR paper)
183 * @param start the earliest part of the input contributing to this node (used to make merging decisions)
185 private boolean newNode(Result result, State state, boolean fromEmptyReduction) {
186 Node p = hash.get(state, result.phase());
187 if (p != null) { p.addResult(result); return !state.doomed(); }
189 if (token != null && state.canShift(token)) break;
190 if (state.isAccepting()) break;
191 if (token==null) break;
192 if (!state.canReduce(token)) return false;
194 Node n = new Node(Phase.this, result, state, fromEmptyReduction); // ALLOC
195 for(Object s : state.conjunctStates)
196 newNode(new Result(null, n, null), (State)s, fromEmptyReduction);
197 return !n.state().doomed();
200 public int toInt() { return pos+1; }
201 public int size() { return hash==null ? 0 : hash.size(); }
202 public int pos() { return pos; }
203 public Tok getToken() { return token; }
204 public Iterator<Node> iterator() { return hash.iterator(); }
205 public GSS getGSS() { return GSS.this; }
207 // GraphViz //////////////////////////////////////////////////////////////////////////////
209 public GraphViz.Node toGraphViz(GraphViz gv) {
210 if (gv.hasNode(this)) return gv.createNode(this);
211 GraphViz.Group g = gv.createGroup(this);
212 g.label = "Phase " + pos;
217 public boolean isTransparent() { return false; }
218 public boolean isHidden() { return false; }
220 public void dumpGraphViz(String filename) throws IOException {
221 FileOutputStream fos = new FileOutputStream(filename);
222 PrintWriter p = new PrintWriter(new OutputStreamWriter(fos));
223 GraphViz gv = new GraphViz();
225 ((Node)n).toGraphViz(gv);