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 */
15 public static Queue<Node> removals = new LinkedList<Node>();
17 static String note = "";
18 static int single_newnode = 0;
19 static int toplevel_reductions = 0;
20 static int multi_newnode = 0;
21 static int waiting_newnode = 0;
22 static int shifts = 0;
25 static int reductions = 0;
31 public GSS(Input input) { this.input = input; }
33 private Node[] reducing_list = null;
35 // FIXME: right now, these are the performance bottleneck
36 HashMapBag<Sequence,Phase.Waiting> waiting = new HashMapBag<Sequence,Phase.Waiting>();
37 HashMapBag<Integer,Sequence> performed = new HashMapBag<Integer,Sequence>();
38 HashMapBag<Integer,Sequence> lastperformed = new HashMapBag<Integer,Sequence>();
39 HashMapBag<Integer,Sequence> expected = new HashMapBag<Integer,Sequence>();
42 Forest.Many finalResult;
44 /** corresponds to a positions <i>between tokens</i> the input stream; same as Tomita's U_i's */
45 class Phase<Tok> implements Invokable<State, Forest, Node>, IntegerMappable, GraphViz.ToGraphViz, Iterable<Node> {
47 public int pos() { return pos; }
48 public boolean closed() { return closed; }
49 public Tok token() { return token; }
51 public Iterator<Node> iterator() { return hash.iterator(); }
52 public void invoke(State st, Forest result, Node n) {
54 good |= next.newNode(n, result, st, false);
57 /** the token immediately after this phase */
60 private final int pos;
63 public IntPairMap<Node> hash; /* ALLOC */
64 private boolean closed;
66 private Phase next = null;
68 private Input.Location location;
69 private Input.Location nextLocation;
70 private Input.Location prevLocation;
72 public final Parser parser;
74 private Forest forest;
76 public Phase(Phase prev, Parser parser, Phase previous, Tok token, Input.Location location,
77 Input.Location nextLocation, Forest forest) throws ParseFailed {
78 this.prevLocation = prev==null ? location : prev.getLocation();
82 this.pos = previous==null ? 0 : previous.pos+1;
84 this.location = location;
85 this.nextLocation = nextLocation;
90 public void reset() throws ParseFailed {
93 lastperformed.clear();
94 lastperformed.addAll(performed);
96 hash = new IntPairMap<Node>();
102 if (prev != null) prev.shift(this, forest);
106 public boolean isDone() throws ParseFailed {
107 if (token != null) return false;
108 if (token==null && finalResult==null)
109 ParseFailed.error("unexpected end of file",
113 getLocation().createRegion(getLocation()),
119 public Input.Location getPrevLocation() { return prevLocation; }
120 public Input.Location getLocation() { return location; }
121 public Input.Region getRegion() { return getPrevLocation().createRegion(getLocation()); }
122 public Input.Location getNextLocation() { return nextLocation; }
124 /** add a new node (merging with existing nodes if possible)
125 * @param parent the parent of the new node
126 * @param result the SPPF result corresponding to the new node
127 * @param state the state that the new node is in
128 * @param fromEmptyReduction true iff this node is being created as a result of a reduction of length zero (see GRMLR paper)
129 * @param start the earliest part of the input contributing to this node (used to make merging decisions)
131 public boolean newNode(Node parent, Forest pending, State state, boolean fromEmptyReduction) {
132 Node p = hash.get(state, parent==null?null:parent.phase());
133 if (p != null) return newNode2(p, parent, pending, state, fromEmptyReduction);
134 else return newNode3(parent, pending, state, fromEmptyReduction);
136 public void newNode(Node parent, Forest pending, State state, boolean fromEmptyReduction, Position reduction) {
137 int pos = parent==null?0:parent.phase()==null?0:parent.phase().pos;
138 Sequence owner = reduction==null ? null : reduction.owner();
139 if (reduction!=null) {
140 if (owner.hates!=null) {
141 for (Sequence s : performed.getAll(pos))
142 if (owner.hates.contains(s))
144 for (Sequence s : lastperformed.getAll(pos))
145 if (owner.hates.contains(s)) {
146 //System.out.println("now expecting ["+pos+"] => " + s);
147 expected.add(pos, s);
151 if (owner.needs != null)
152 for(Sequence s : owner.needs)
153 if (!performed.contains(pos, s)) {
154 waiting.add(s, new Waiting(parent, pending, state, fromEmptyReduction, reduction));
157 if (!performed.contains(pos, owner)) {
158 performed.add(pos, owner);
159 if (owner.hated != null)
160 for(Sequence seq : owner.hated)
161 if (performed.contains(pos, seq)) {
162 performed.remove(pos, seq);
167 newNode(parent, pending, state, fromEmptyReduction);
168 if (reduction != null) {
172 for(Waiting w : waiting.getAll(owner)) {
173 if (w.parent==parent || (parent!=null&&w.parent!=null&&w.parent.phase()==parent.phase())) {
174 waiting.remove(owner, w);
184 private boolean newNode2(Node p, Node parent, Forest pending, State state, boolean fromEmptyReduction) {
185 if (p.merge(parent, pending)) return true;
186 p.addParent(parent, true);
187 if (p!=parent && !fromEmptyReduction && reducing) p.performReductions(parent);
191 private boolean newNode3(Node parent, Forest pending, State state, boolean fromEmptyReduction) {
193 if (token != null && state.canShift(token)) break;
194 if (state.isAccepting()) break;
195 if (token==null) break;
196 if (!state.canReduce(token)) return false;
197 //if (count > 1) break;
198 //if (r.numPop == 0) break;
199 //r.reduce(pending, parent, null, Phase.this, null);
203 Node n = new Node(Phase.this, parent, pending, state); // ALLOC
205 n.performEmptyReductions();
206 if (!fromEmptyReduction) n.performReductions(parent);
211 public LinkedList<Node> reductionQueue = new LinkedList<Node>();
213 /** perform all reduction operations */
214 public void reduce() throws ParseFailed {
217 if (reducing_list==null || reducing_list.length < hash.size())
218 reducing_list = new Node[hash.size() * 4];
219 hash.toArray(reducing_list);
220 int num = hash.size();
221 for(int i=0; i<num; i++) {
222 Node n = reducing_list[i];
223 n.performEmptyReductions();
224 // INVARIANT: we never "see" a node until its parent-set is complete, modulo merges
226 for(int i=0; i<num; i++) {
227 reductionQueue.add(reducing_list[i]);
228 reducing_list[i] = null;
230 while(!reductionQueue.isEmpty()) {
231 reductionQueue.remove().performReductions();
238 for(int i : expected)
239 for(Sequence s : expected.getAll(i))
240 if (!performed.contains(i, s)) {
241 //System.out.println("resetting due to pos="+i+": " + s + " " + System.identityHashCode(s));
252 private boolean reset = false;
253 class Reset extends RuntimeException { }
255 /** perform all shift operations, adding promoted nodes to <tt>next</tt> */
256 public void shift(Phase next, Forest result) throws ParseFailed {
257 // this massively improves GC performance
258 if (prev!=null && parser.helpgc) {
260 //System.out.println("\r" + /*shifts + " " + */ single_newnode /*+ "/"+multi_newnode + " " + waiting_newnode*/);
261 //System.out.println("\r" + shifts + " " + note);
262 //System.out.println("\r" + shifts);
263 //System.out.println("\r" + toplevel_reductions);
264 //System.out.println("\r" + multi_newnode);
268 toplevel_reductions = 0;
277 for(Node n : hash.values()) {
278 if (token == null && n.state().isAccepting()) {
279 if (finalResult==null) finalResult = new Forest.Many();
280 for(Object f : n.results())
281 finalResult.merge((Forest)f);
283 if (token == null) continue;
284 n.state().invokeShifts(token, this, result, n);
286 //System.out.println(next.hash.size());
287 if (!good && token!=null)
288 ParseFailed.error("unexpected character",
296 if (token==null && finalResult==null)
297 ParseFailed.error("unexpected end of file",
301 getLocation().createRegion(getLocation()),
311 boolean fromEmptyReduction;
313 public Waiting(Node parent, Forest pending, State state, boolean fromEmptyReduction, Position reduction) {
315 this.parent = parent;
316 this.pending = pending;
318 this.fromEmptyReduction = fromEmptyReduction;
319 this.reduction = reduction;
321 public void perform() {
322 //System.out.println("performing: " + reduction.position);
324 newNode(parent, pending, state, fromEmptyReduction, reduction);
329 public int toInt() { return pos+1; }
330 public int size() { return hash==null ? 0 : hash.size(); }
332 // GraphViz //////////////////////////////////////////////////////////////////////////////
334 public GraphViz.Node toGraphViz(GraphViz gv) {
335 if (gv.hasNode(this)) return gv.createNode(this);
336 GraphViz.Group g = gv.createGroup(this);
337 g.label = "Phase " + pos;
342 public boolean isTransparent() { return false; }
343 public boolean isHidden() { return false; }