1 package edu.berkeley.sbp;
2 import edu.berkeley.sbp.*;
3 import edu.berkeley.sbp.util.*;
4 import edu.berkeley.sbp.Sequence.Position;
5 import edu.berkeley.sbp.Parser.Table.State;
6 import edu.berkeley.sbp.Parser.Table.Reduction;
9 import java.lang.reflect.*;
11 /** implements Tomita's Graph Structured Stack */
16 private Phase.Node[] reducing_list = null;
17 public int resets = 0;
20 HashMapBag<Integer,Sequence> inhibited = new HashMapBag<Integer,Sequence>();
21 HashMapBag<Sequence,Phase.Waiting> waiting = new HashMapBag<Sequence,Phase.Waiting>();
22 HashMapBag<Integer,Sequence> performed = new HashMapBag<Integer,Sequence>();
25 public Forest.Ref finalResult;
27 /** corresponds to a positions <i>between tokens</i> the input stream; same as Tomita's U_i's */
28 public class Phase implements Invokable<State, Forest, GSS.Phase.Node>, IntegerMappable {
30 /** the token immediately after this phase */
33 private final int pos;
36 private IntPairMap<Phase.Node> hash; /* ALLOC */
37 private boolean closed;
39 private Phase next = null;
41 private Token.Location location;
42 public final Parser parser;
44 private Forest forest;
46 public Phase(Phase prev, Parser parser, Phase previous, Token token, Token.Location location, Forest forest) {
50 this.pos = previous==null ? 0 : previous.pos+1;
52 this.location = location;
60 hash = new IntPairMap<Phase.Node>();
65 if (prev != null) prev.shift(this, forest);
69 public boolean isDone() throws ParseFailed {
70 if (token != null) return false;
71 if (token==null && finalResult==null)
72 throw new ParseFailed(ParseFailed.error(ANSI.red("unexpected end of file\n"), token, hash.values()), getLocation());
76 public Token.Location getLocation() { return location; }
78 /** add a new node (merging with existing nodes if possible)
79 * @param parent the parent of the new node
80 * @param result the SPPF result corresponding to the new node
81 * @param state the state that the new node is in
82 * @param fromEmptyReduction true iff this node is being created as a result of a reduction of length zero (see GRMLR paper)
83 * @param start the earliest part of the input contributing to this node (used to make merging decisions)
85 public boolean newNode(Node parent, Forest pending, State state, boolean fromEmptyReduction) {
86 Node p = hash.get(state, parent==null?null:parent.phase());
87 if (p != null) return newNode2(p, parent, pending, state, fromEmptyReduction);
88 else return newNode3(parent, pending, state, fromEmptyReduction);
90 public void newNode(Node parent, Forest pending, State state, boolean fromEmptyReduction, Reduction reduction) {
91 int pos = parent==null?0:parent.phase()==null?0:parent.phase().pos;
92 Sequence owner = reduction==null ? null : reduction.position.owner();
93 if (reduction!=null) {
94 if (inhibited.contains(pos, owner)) return;
95 if (owner.needs != null)
96 for(Sequence s : owner.needs)
97 if (!performed.contains(pos, s)) {
98 waiting.add(s, new Waiting(parent, pending, state, fromEmptyReduction, reduction));
101 if ((owner.needed != null && owner.needed.size()>0) ||
102 (owner.hated != null && owner.hated.size()>0) ||
103 (owner.hates != null && owner.hates.size()>0))
104 performed.add(pos, owner);
107 newNode(parent, pending, state, fromEmptyReduction);
108 if (reduction!=null) inhibit(reduction, parent==null?0:parent.phase().pos);
109 if (reduction != null) {
113 for(Waiting w : waiting.getAll(owner)) {
114 if (w.parent==parent || (parent!=null&&w.parent!=null&&w.parent.phase()==parent.phase())) {
115 waiting.remove(owner, w);
124 private boolean newNode2(Node p, Node parent, Forest pending, State state, boolean fromEmptyReduction) {
125 p.holder.merge(pending);
126 if (p.parents().contains(parent)) return true;
127 p.parents().add(parent, true);
128 if (p!=parent && !fromEmptyReduction && reducing) p.queueReductions(parent);
131 private boolean newNode3(Node parent, Forest pending, State state, boolean fromEmptyReduction) {
133 if (token != null && state.canShift(token)) break;
134 if (state.isAccepting()) break;
135 if (token==null) break;
136 if (!state.canReduce(token)) return false;
137 //if (count > 1) break;
138 //if (r.numPop == 0) break;
139 //r.reduce(pending, parent, null, Phase.this, null);
143 Node n = new Node(parent, pending, state); // ALLOC
145 n.queueEmptyReductions();
146 if (!fromEmptyReduction) n.queueReductions(parent);
151 public void uninhibit(int p, Sequence s) {
153 for(Sequence s2 : s.hated)
154 inhibited.remove(p, s2);
157 public void inhibit(Reduction r, int p) {
158 if (r.position.owner().hated == null) return;
159 // remember that dead states are still allowed to shift -- just not allowed to reduce
160 boolean reset = false;
161 for(Sequence seq : r.position.owner().hated) {
162 if (performed.contains(p,seq)) {
164 //System.out.println("\nresetting due to " + r.position.owner() + " killing " + seq);
166 inhibited.add(p, seq);
167 //inhibited = new HashMapBag<Integer,Sequence>();
172 inhibited.add(p, seq);
176 /** perform all reduction operations */
177 public void reduce() {
180 if (reducing_list==null || reducing_list.length < hash.size())
181 reducing_list = new Phase.Node[hash.size() * 4];
182 hash.toArray(reducing_list);
183 int num = hash.size();
184 for(int i=0; i<num; i++) {
185 Node n = reducing_list[i];
186 n.queueEmptyReductions();
187 // INVARIANT: we never "see" a node until its parent-set is complete, modulo merges
189 for(int i=0; i<num; i++) {
190 Node n = reducing_list[i];
191 reducing_list[i] = null;
200 class Reset extends RuntimeException { }
202 public void invoke(State st, Forest result, Node n) {
203 good |= next.newNode(n, result, st, false);
206 /** perform all shift operations, adding promoted nodes to <tt>next</tt> */
207 public void shift(Phase next, Forest result) throws ParseFailed {
208 // this massively improves GC performance
209 if (prev!=null) prev.hash = null;
214 for(Phase.Node n : hash.values()) {
215 if (token == null && n.state.isAccepting()) {
216 if (finalResult==null) finalResult = new Forest.Ref();
217 finalResult.merge(n.holder);
219 if (token == null) continue;
220 n.state.invokeShifts(token, this, result, n);
223 if (!good && token!=null)
224 throw new ParseFailed(ParseFailed.error(ANSI.red("unexpected character")+" "+ANSI.purple(token)+" encountered at "+ANSI.green(getLocation())+"\n", token, hash.values()),
226 if (token==null && finalResult==null)
227 throw new ParseFailed(ParseFailed.error(ANSI.red("unexpected end of file\n"), token, hash.values()),
232 public class Waiting {
236 boolean fromEmptyReduction;
238 public Waiting(Node parent, Forest pending, State state, boolean fromEmptyReduction, Reduction reduction) {
240 this.parent = parent;
241 this.pending = pending;
243 this.fromEmptyReduction = fromEmptyReduction;
244 this.reduction = reduction;
246 public void perform() {
247 //System.out.println("performing: " + reduction.position);
248 newNode(parent, pending, state, fromEmptyReduction, reduction);
252 // Node /////////////////////////////////////////////////////////////////////////////////
254 /** a node in the GSS */
255 public final class Node extends FastSet<Node> implements Invokable<Reduction, Node, Node> {
257 private Forest.Ref holder = null;
258 private boolean allqueued = false;
260 /** what state this node is in */
261 public final State state;
263 /** which Phase this Node belongs to (node that Node is also a non-static inner class of Phase) */
264 public Phase phase() { return Phase.this; }
265 public Forest.Ref holder() { return holder==null ? (holder = new Forest.Ref()) : holder; }
266 public Forest pending() { return Phase.this.closed ? holder().resolve() : holder; }
267 public FastSet<Node> parents() { return this; }
269 public void queueReductions() {
270 if (allqueued) return;
272 state.invokeReductions(token, this, this, null);
275 public void queueReductions(Node n2) {
276 if (!allqueued) { queueReductions(); return; }
277 state.invokeReductions(token, this, this, n2);
280 public final void invoke(Reduction r, Node n, Node n2) {
282 if (r.position.pos==0) r.reduce(this);
283 } else if (r.position.pos==0) return;
284 else if (n2==null) r.reduce(n);
285 else r.reduce(n, n2);
287 public void queueEmptyReductions() { state.invokeReductions(token, this, null, null); }
289 public boolean dead = false;
290 public boolean redo = false;
291 private Node(Node parent, Forest pending, State state) {
293 this.holder().merge(pending);
294 Phase start = parent==null ? null : parent.phase();
295 if (parent != null) parents().add(parent, true);
296 if (Phase.this.hash.get(state, start) != null) throw new Error("severe problem!");
297 Phase.this.hash.put(state, start, this);
301 public int toInt() { return pos+1; }
302 public int size() { return hash==null ? 0 : hash.size(); }