checkpoint
[sbp.git] / src / edu / berkeley / sbp / GSS.java
1 package edu.berkeley.sbp;
2 import edu.berkeley.sbp.*;
3 import edu.berkeley.sbp.util.*;
4 import edu.berkeley.sbp.Parser.Table.*;
5 import edu.berkeley.sbp.Sequence.Position;
6 import java.io.*;
7 import java.util.*;
8 import java.lang.reflect.*;
9
10 /** implements Tomita's Graph Structured Stack */
11 public class GSS {
12
13     public static int count = 0;
14     public static int shifts = 0;
15     public static int reductions = 0;
16     
17     public GSS() { }
18
19     private Phase.Node[] reducing_list = null;
20     public int resets = 0;
21     public int waits = 0;
22
23     // FIXME: right now, these are the performance bottleneck
24     HashMapBag<Sequence,Phase.Waiting> waiting         = new HashMapBag<Sequence,Phase.Waiting>();
25     HashMapBag<Integer,Sequence>       performed       = new HashMapBag<Integer,Sequence>();
26     HashMapBag<Integer,Sequence>       lastperformed   = new HashMapBag<Integer,Sequence>();
27     HashMapBag<Integer,Sequence>       expected        = new HashMapBag<Integer,Sequence>();
28     
29     /** FIXME */
30     public  Forest.Ref finalResult;
31
32     /** corresponds to a positions <i>between tokens</i> the input stream; same as Tomita's U_i's */
33     class Phase<Tok> implements Invokable<State, Forest, Phase<Tok>.Node>, IntegerMappable, GraphViz.ToGraphViz, Iterable<Phase.Node> {
34
35         public Iterator<Phase.Node> iterator() { return hash.iterator(); }
36         public void invoke(State st, Forest result, Node n) {
37             shifts++;
38             good |= next.newNode(n, result, st, false);
39         }
40
41         /** the token immediately after this phase */
42         final Tok token;
43
44         private final int pos;
45
46         boolean reducing;
47         private IntPairMap<Phase.Node> hash;  /* ALLOC */
48         private boolean closed;
49         private boolean good;
50         private Phase next = null;
51         private Phase prev;
52         private Input.Location location;
53         public final Parser parser;
54
55         private Forest forest;
56
57         public Phase(Phase prev, Parser parser, Phase previous, Tok token, Input.Location location, Forest forest) throws ParseFailed {
58             this.prev = prev;
59             this.forest = forest;
60             this.parser = parser;
61             this.pos = previous==null ? 0 : previous.pos+1;
62             this.token = token;
63             this.location = location;
64             performed.clear();
65             reset();
66         }
67
68         public void reset() throws ParseFailed {
69             waiting.clear();
70             expected.clear();
71             lastperformed.clear();
72             lastperformed.addAll(performed);
73             performed.clear();
74             hash = new IntPairMap<Phase.Node>();
75             reset = false;
76             good = false;
77             closed = false;
78             reducing = false;
79             finalResult = null;
80             if (prev != null) prev.shift(this, forest);
81         }
82
83       
84         public boolean isDone() throws ParseFailed {
85             if (token != null) return false;
86             if (token==null && finalResult==null)
87                 throw new ParseFailed(ParseFailed.error(ANSI.red("unexpected end of file\n"), token, hash.values()), getLocation());
88             return true;
89         }
90
91         public Input.Location getLocation() { return location; }
92
93         /** add a new node (merging with existing nodes if possible)
94          *  @param parent             the parent of the new node
95          *  @param result             the SPPF result corresponding to the new node
96          *  @param state              the state that the new node is in
97          *  @param fromEmptyReduction true iff this node is being created as a result of a reduction of length zero (see GRMLR paper)
98          *  @param start              the earliest part of the input contributing to this node (used to make merging decisions)
99          */
100         public boolean newNode(Node parent, Forest pending, State state, boolean fromEmptyReduction) {
101             Node p = hash.get(state, parent==null?null:parent.phase());
102             if (p != null)  return newNode2(p, parent, pending, state, fromEmptyReduction);
103             else            return newNode3(parent, pending, state, fromEmptyReduction);
104         }
105         public void newNode(Node parent, Forest pending, State state, boolean fromEmptyReduction, Position reduction) {
106             int pos = parent==null?0:parent.phase()==null?0:parent.phase().pos;
107             Sequence owner = reduction==null ? null : reduction.owner();
108             if (reduction!=null) {
109                 if (owner.hates!=null) {
110                     for (Sequence s : performed.getAll(pos))
111                         if (owner.hates.contains(s))
112                             return;
113                     for (Sequence s : lastperformed.getAll(pos))
114                         if (owner.hates.contains(s)) {
115                             //System.out.println("now expecting ["+pos+"] => " + s);
116                             expected.add(pos, s);
117                             return;
118                         }
119                 }
120                 if (owner.needs != null)
121                     for(Sequence s : owner.needs)
122                         if (!performed.contains(pos, s)) {
123                             waiting.add(s, new Waiting(parent, pending, state, fromEmptyReduction, reduction));
124                             return;
125                         }
126                 if (!performed.contains(pos, owner)) {
127                     performed.add(pos, owner);
128                     if (owner.hated != null)
129                         for(Sequence seq : owner.hated)
130                             if (performed.contains(pos, seq)) {
131                                 performed.remove(pos, seq);
132                                 reset = true;
133                             }
134                 }
135             }
136             if (!owner.lame)
137                 newNode(parent, pending, state, fromEmptyReduction);
138             if (reduction != null) {
139                 boolean redo = true;
140                 while(redo) {
141                     redo = false;
142                     for(Waiting w : waiting.getAll(owner)) {
143                         if (w.parent==parent || (parent!=null&&w.parent!=null&&w.parent.phase()==parent.phase())) {
144                             waiting.remove(owner, w);
145                             w.perform();
146                             redo = true;
147                             break;
148                         }
149                     }
150                 }
151             }
152         }
153
154         private boolean newNode2(Node p, Node parent, Forest pending, State state, boolean fromEmptyReduction) {
155             if (p.merge(parent, pending)) return true;
156             p.parents().add(parent, true);
157             if (p!=parent && !fromEmptyReduction && reducing) p.performReductions(parent);
158             return true;
159         }
160
161         private boolean newNode3(Node parent, Forest pending, State state, boolean fromEmptyReduction) {
162             do {
163                 if (token != null && state.canShift(token)) break;
164                 if (state.isAccepting()) break;
165                 if (token==null) break;
166                 if (!state.canReduce(token)) return false;
167                 //if (count > 1) break;
168                 //if (r.numPop == 0) break;
169                 //r.reduce(pending, parent, null, Phase.this, null);
170                 //return;
171             } while(false);
172
173             Node n = new Node(parent, pending, state);  // ALLOC
174             if (reducing) {
175                 n.performEmptyReductions();
176                 if (!fromEmptyReduction) n.performReductions(parent);
177             }
178             return true;
179         }
180
181         /** perform all reduction operations */
182         public void reduce() throws ParseFailed {
183             try {
184                 reducing = true;
185                 if (reducing_list==null || reducing_list.length < hash.size())
186                     reducing_list = new Phase.Node[hash.size() * 4];
187                 hash.toArray(reducing_list);
188                 int num = hash.size();
189                 for(int i=0; i<num; i++) {
190                     Node n = reducing_list[i];
191                     n.performEmptyReductions();
192                     // INVARIANT: we never "see" a node until its parent-set is complete, modulo merges
193                 }
194                 for(int i=0; i<num; i++) {
195                     Node n = reducing_list[i];
196                     reducing_list[i] = null;
197                     n.performReductions();
198                 }
199                 if (reset) {
200                     reset = false;
201                     resets++;
202                     throw new Reset();
203                 }                
204                 for(int i : expected)
205                     for(Sequence s : expected.getAll(i))
206                         if (!performed.contains(i, s)) {
207                             //System.out.println("resetting due to pos="+i+": " + s + " " + System.identityHashCode(s));
208                             resets++;
209                             throw new Reset();
210                         }
211             } catch (Reset r) {
212                 reset();
213                 reduce();
214             }
215             count = 0;
216         }
217
218         private boolean reset = false;
219         class Reset extends RuntimeException { }
220
221         /** perform all shift operations, adding promoted nodes to <tt>next</tt> */
222         public void shift(Phase next, Forest result) throws ParseFailed {
223             // this massively improves GC performance
224             if (prev!=null && parser.helpgc) {
225                 prev.hash = null;
226             }
227             this.next = next;
228             closed = true;
229             Forest res = null;
230             boolean ok = false;
231             for(Phase.Node n : hash.values()) {
232                 if (token == null && n.state.isAccepting()) {
233                     if (finalResult==null) finalResult = new Forest.Ref();
234                     for(Object f : n.results())
235                         finalResult.merge((Forest)f);
236                 }
237                 if (token == null) continue;
238                 n.state.invokeShifts(token, this, result, n);
239             }
240
241             if (!good && token!=null)
242                 throw new ParseFailed(ParseFailed.error(ANSI.red("unexpected character ")+" \'"+
243                                                         ANSI.purple(StringUtil.escapify(token+"", "\\\'\r\n"))+
244                                                         "\' encountered at "+
245                                                         ANSI.green(getLocation())+"\n", token, hash.values()),
246                                         getLocation());
247             if (token==null && finalResult==null)
248                 throw new ParseFailed(ParseFailed.error(ANSI.red("unexpected end of file\n"), token, hash.values()),
249                                         getLocation());
250         }
251
252
253         class Waiting {
254             Node parent;
255             Forest pending;
256             State state;
257             boolean fromEmptyReduction;
258             Position reduction;
259             public Waiting(Node parent, Forest pending, State state, boolean fromEmptyReduction, Position reduction) {
260                 waits++;
261                 this.parent = parent;
262                 this.pending = pending;
263                 this.state = state;
264                 this.fromEmptyReduction = fromEmptyReduction;
265                 this.reduction = reduction;
266             }
267             public void perform() {
268                 //System.out.println("performing: " + reduction.position);
269                 newNode(parent, pending, state, fromEmptyReduction, reduction);
270             }
271         }
272        
273         // Node /////////////////////////////////////////////////////////////////////////////////
274
275         /** a node in the GSS */
276         final class Node implements Invokable<Position, Node, Node>, IntegerMappable, GraphViz.ToGraphViz {
277             public FastSet<Node> set = new FastSet<Node>();
278
279            
280             private boolean allqueued = false;
281
282             /** what state this node is in */
283             public final Parser.Table<Tok>.State<Tok> state;
284
285             /** which Phase this Node belongs to (node that Node is also a non-static inner class of Phase) */
286             public  Phase phase() { return Phase.this; }
287
288             private HashSet<Forest.Ref> resultMap = new HashSet<Forest.Ref>();
289             public Iterable<Forest.Ref> results() { return resultMap; }
290             public FastSet<Node> parents() { return set; }
291             public boolean merge(Node parent, Forest result) {
292                 // FIXME: inefficient!
293                 for(Forest.Ref f : results()) {
294                     if (f.parents.contains(parent) /* UGLY: */ && f.parents.size()==1) {
295                         f.merge(result);
296                         return true;
297                     }
298                 }
299                 Forest.Ref f = new Forest.Ref();
300                 f.parents.add(parent);
301                 f.merge(result);
302                 resultMap.add(f);
303                 set.add(parent, true);
304                 return false;
305             }
306
307             public void performReductions() {
308                 if (allqueued) return;
309                 allqueued = true;
310                 state.invokeReductions(token, this, this, null);
311             }
312
313             public void performReductions(Node n2) {
314                 if (!allqueued) performReductions();
315                 else            state.invokeReductions(token, this, this, n2);
316             }
317
318             public void performEmptyReductions() { state.invokeReductions(token, this, null, null); }
319             public final void invoke(Position r, Node n, Node n2) {
320                 reductions++;
321                 if (n==null || n2==null || r.pos==0) {
322                     if (r.pos==0) {
323                         if (n==null) n = this;
324                         else return;
325                     }
326                     if (n==null) return;
327                     Forest[] holder = new Forest[r.pos];
328                     if (r.pos==0) n.finish(r, r.zero(), n.phase());
329                     else          n.reduce(r, r.pos-1,  n.phase(), null);
330                 } else {
331                     if (r.pos<=0) throw new Error("called wrong form of reduce()");
332                     int pos = r.pos-1;
333                     n.reduce(r, pos, n.phase(), n2);
334                 }
335             }
336
337             public void reduce(Position r, int pos, Phase target, Node only) {
338                 Forest[] holder = r.holder;
339                 Forest old = holder[pos];
340
341                 for(Forest result : results())
342                     for(Node child : ((Forest.Ref<?>)result).parents) {
343                         if (only != null && child!=only) continue;
344                         holder[pos] = result;
345                         if (pos==0) child.finish(r, r.rewrite(phase().getLocation()), target);
346                         else        child.reduce(r, pos-1, target, null);
347                     }
348
349                 holder[pos] = old;
350             }
351
352             public void finish(Position r, Forest result, Phase<Tok> target) {
353                 Parser.Table<Tok>.State<Tok> state0 = state.gotoSetNonTerminals.get(r.owner());
354                 if (result==null) throw new Error();
355                 if (state0!=null)
356                     target.newNode(this, result, state0, r.pos<=0, r);
357             }
358
359             private Node(Node parent, Forest pending, State state) {
360                 this.state = state;
361                 this.merge(parent, pending);
362                 Phase start = parent==null ? null : parent.phase();
363                 if (parent != null) parents().add(parent, true);
364                 if (Phase.this.hash.get(state, start) != null) throw new Error("severe problem!");
365                 Phase.this.hash.put(state, start, this);
366             }
367             public int toInt() { return idx; }
368             private final int idx = node_idx++;
369
370             // GraphViz //////////////////////////////////////////////////////////////////////////////
371
372             public GraphViz.Node toGraphViz(GraphViz gv) {
373                 if (gv.hasNode(this)) return gv.createNode(this);
374                 GraphViz.Node n = gv.createNode(this);
375                 n.label = ""+state.toStringx();
376                 n.shape = "rectangle";
377                 n.fill = "green";
378                 for(Forest result : results()) n.edge(result, "");
379                 for(Node parent : parents()) n.edge(parent, "");
380                 ((GraphViz.Group)phase().toGraphViz(gv)).add(n);
381                 return n;
382             }
383             public boolean isTransparent() { return false; }
384             public boolean isHidden() { return false; }
385
386         }
387         private int node_idx = 0;
388
389         public int toInt() { return pos+1; }
390         public int size() { return hash==null ? 0 : hash.size(); }
391
392         // GraphViz //////////////////////////////////////////////////////////////////////////////
393
394         public GraphViz.Node toGraphViz(GraphViz gv) {
395             if (gv.hasNode(this)) return gv.createNode(this);
396             GraphViz.Group g = gv.createGroup(this);
397             g.label = "Phase " + pos;
398             g.color = "gray";
399             g.cluster = true;
400             return g;
401         }
402         public boolean isTransparent() { return false; }
403         public boolean isHidden() { return false; }
404
405     }
406 }