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) 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, fromEmptyReduction); // ALLOC
144 n.queueEmptyReductions();
145 if (!fromEmptyReduction) n.queueReductions(parent);
149 public void uninhibit(int p, Sequence s) {
151 for(Sequence s2 : s.hated)
152 inhibited.remove(p, s2);
155 public void inhibit(Reduction r, int p) {
156 if (r.position.owner().hated == null) return;
157 // remember that dead states are still allowed to shift -- just not allowed to reduce
158 boolean reset = false;
159 for(Sequence seq : r.position.owner().hated) {
160 if (performed.contains(p,seq)) {
162 //System.out.println("\nresetting due to " + r.position.owner() + " killing " + seq);
164 inhibited.add(p, seq);
165 //inhibited = new HashMapBag<Integer,Sequence>();
170 inhibited.add(p, seq);
174 /** perform all reduction operations */
175 public void reduce() {
178 if (reducing_list==null || reducing_list.length < hash.size())
179 reducing_list = new Phase.Node[hash.size() * 4];
180 hash.toArray(reducing_list);
181 int num = hash.size();
182 for(int i=0; i<num; i++) {
183 Node n = reducing_list[i];
184 n.queueEmptyReductions();
185 // INVARIANT: we never "see" a node until its parent-set is complete, modulo merges
187 for(int i=0; i<num; i++) {
188 Node n = reducing_list[i];
189 reducing_list[i] = null;
198 class Reset extends RuntimeException { }
200 public void invoke(State st, Forest result, Node n) {
201 good |= next.newNode(n, result, st, false);
204 /** perform all shift operations, adding promoted nodes to <tt>next</tt> */
205 public void shift(Phase next, Forest result) throws ParseFailed {
206 // this massively improves GC performance
207 if (prev!=null) prev.hash = null;
212 for(Phase.Node n : hash.values()) {
213 if (token == null && n.state.isAccepting()) {
214 if (finalResult==null) finalResult = new Forest.Ref();
215 finalResult.merge(n.holder);
217 if (token == null) continue;
218 n.state.invokeShifts(token, this, result, n);
221 if (!good && token!=null)
222 throw new ParseFailed(ParseFailed.error(ANSI.red("unexpected character")+" "+ANSI.purple(token)+" encountered at "+ANSI.green(getLocation())+"\n", token, hash.values()),
224 if (token==null && finalResult==null)
225 throw new ParseFailed(ParseFailed.error(ANSI.red("unexpected end of file\n"), token, hash.values()),
230 public class Waiting {
234 boolean fromEmptyReduction;
236 public Waiting(Node parent, Forest pending, State state, boolean fromEmptyReduction, Reduction reduction) {
238 this.parent = parent;
239 this.pending = pending;
241 this.fromEmptyReduction = fromEmptyReduction;
242 this.reduction = reduction;
244 public void perform() {
245 //System.out.println("performing: " + reduction.position);
246 newNode(parent, pending, state, fromEmptyReduction, reduction);
250 // GSS Nodes //////////////////////////////////////////////////////////////////////////////
252 /** a node in the GSS */
253 public final class Node extends FastSet<Node> implements Invokable<Reduction, Node, Node> {
255 public boolean touched = false;
256 private Forest.Ref holder = null;
257 private boolean allqueued = false;
259 /** what state this node is in */
260 public final State state;
262 /** which Phase this Node belongs to (node that Node is also a non-static inner class of Phase) */
263 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 (!reducing) return;
271 if (allqueued) return;
273 int where = parents().size();
274 state.invokeReductions(token, this, this, null);
277 public void queueReductions(Node n2) {
278 if (!allqueued) { queueReductions(); return; }
279 state.invokeReductions(token, this, this, n2);
282 public final void invoke(Reduction r, Node n, Node n2) {
284 if (r.position.pos==0) r.reduce(this);
287 if (r.position.pos==0) return;
288 if (n2==null) r.reduce(n);
289 else r.reduce(n, n2);
291 public void queueEmptyReductions() {
292 if (!reducing) return;
293 state.invokeReductions(token, this, null, null);
297 public boolean dead = false;
298 public boolean redo = false;
299 private Node(Node parent, Forest pending, State state, boolean fe) {
302 this.holder().merge(pending);
303 Phase start = parent==null ? null : parent.phase();
304 if (parent != null) parents().add(parent, true);
305 if (Phase.this.hash.get(state, start) != null) throw new Error("severe problem!");
306 Phase.this.hash.put(state, start, this);
310 public int toInt() { return pos+1; }
311 public int size() { return hash==null ? 0 : hash.size(); }