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.Sequence.Position;
   5 import edu.berkeley.sbp.Parser.Table.State;
   6 import edu.berkeley.sbp.Parser.Table.Reduction;
   7 import java.io.*;
   8 import java.util.*;
   9 import java.lang.reflect.*;
  10
  11 /** implements Tomita's Graph Structured Stack */
  12 class GSS {
  13
  14     public GSS() { }
  15
  16     private Phase.Node[] reducing_list = null;
  17     public int resets = 0;
  18     public int waits = 0;
  19
  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>();
  23
  24     /** corresponds to a positions <i>between tokens</i> the input stream; same as Tomita's U_i's */
  25     public class Phase implements Invokable<State, Forest, GSS.Phase.Node> {
  26
  27         /** the token immediately after this phase */
  28         public  final Token token;
  29
  30         boolean reducing;
  31
  32         /** currently this is necessary only for the code() hack -- it doesn't actually correspond to the input */
  33         private final int pos;
  34
  35         /** FIXME */
  36         public  Forest.Ref finalResult;
  37
  38         /** all nodes, keyed by the value returned by code() */
  39         /*private*/ HashMap<Long,Phase.Node> hash;  /* ALLOC */
  40
  41         /** the number of nodes in this phase */
  42         private int numNodes;
  43
  44         boolean closed;
  45
  46         private boolean good;
  47         private Phase next = null;
  48
  49         private Token.Location location;
  50         public final Parser parser;
  51
  52         private Forest forest;
  53         Phase prev;
  54         public Phase(Phase prev, Parser parser, Phase previous, Token token, Token.Location location, Forest forest) {
  55             this.prev = prev;
  56             this.forest = forest;
  57             this.parser = parser;
  58             this.pos = previous==null ? 0 : previous.pos+1;
  59             this.token = token;
  60             this.location = location;
  61             inhibited.clear();
  62             reset();
  63         }
  64
  65         public void reset() {
  66             waiting.clear();
  67             performed.clear();
  68             hash = new HashMap<Long,Phase.Node>();
  69             good = false;
  70             closed = false;
  71             numNodes = 0;
  72             reducing = false;
  73             finalResult = null;
  74             if (prev != null) prev.shift(this, forest);
  75         }
  76
  77         public void complain(Node n, HashMap<String,HashSet<String>> errors, boolean force) {
  78             if (n.touched) return;
  79             n.touched = true;
  80             for(Position p : n.state) {
  81                 //if (!p.isLast()) {
  82                 if (((p.isFirst() || p.isLast()) && !force) || p.owner().name==null) {
  83                     for(Node n2 : n.parents())
  84                         complain(n2, errors, force | p.isFirst());
  85                 } else {
  86                     String seqname = p.owner().name;
  87                     HashSet<String> hs = errors.get(seqname);
  88                     if (hs==null) errors.put(seqname, hs = new HashSet<String>());
  89                     hs.add(p.element()+"");
  90                     //String s = "  while parsing " + seqname + ": expected a " + p.element();
  91                         //"\n";
  92                     /*
  93                     s +=       "      parsed: ";
  94                     for(Position p2 = p.owner().firstp(); p2 != null && p2 != p && !p2.isLast(); p2 = p2.next()) s += (p2.element() + " ");
  95                     s += "\n";
  96                     s +=       "    expected: ";
  97                     for(Position p2 = p; p2 != null && !p2.isLast(); p2 = p2.next()) s += (p2.element() + " ");
  98                     */
  99                     //s += "\n";
 100                     //errors.add(s);
 101                 }
 102             }
 103         }
 104
 105         public String black(Object o) { return "\033[30m"+o+"\033[0m"; }
 106         public String red(Object o) { return "\033[31m"+o+"\033[0m"; }
 107         public String green(Object o) { return "\033[32m"+o+"\033[0m"; }
 108         public String yellow(Object o) { return "\033[33m"+o+"\033[0m"; }
 109         public String blue(Object o) { return "\033[34m"+o+"\033[0m"; }
 110         public String purple(Object o) { return "\033[35m"+o+"\033[0m"; }
 111         public String cyan(Object o) { return "\033[36m"+o+"\033[0m"; }
 112         public String el(Object e) {
 113             String s = e.toString();
 114             if (s.length()==0 || s.charAt(0)!='\"' || s.charAt(s.length()-1)!='\"') return yellow(s);
 115             s = s.substring(1);
 116             s = s.substring(0, s.length()-1);
 117             StringBuffer ret = new StringBuffer();
 118             for(int i=0; i<s.length(); i++) {
 119                 if (s.charAt(i)=='\\' && i<s.length()-1) ret.append(s.charAt(++i));
 120                 else ret.append(s);
 121             }
 122             return purple(ret.toString());
 123         }
 124         public String error(String message) {
 125             String lookAhead = token==null ? "<EOF>" : token.toString();
 126             StringBuffer ret = new StringBuffer();
 127             ret.append("\n  ");
 128             ret.append(message);
 129             HashMap<String,HashSet<String>> errors = new HashMap<String,HashSet<String>>();
 130             for(Node n : hash.values()) complain(n, errors, false);
 131             for(String s : errors.keySet()) {
 132                 ret.append("    while parsing " + yellow(s));
 133                 HashSet<String> hs = errors.get(s);
 134                 if (hs.size()==1) ret.append(" expected " + yellow(el(hs.iterator().next())) + "\n");
 135                 else {
 136                     ret.append(" expected ");
 137                     boolean first = true;
 138                     for(String s2 : hs) {
 139                         if (!first) ret.append(" or ");
 140                         first = false;
 141                         ret.append(yellow(el(s2)));
 142                     }
 143                     ret.append("\n");
 144                 }
 145             }
 146             return ret.toString();
 147         }
 148
 149         public boolean isDone() throws Parser.Failed {
 150             if (token != null) return false;
 151             if (token==null && finalResult==null)
 152                 throw new Parser.Failed(error(red("unexpected end of file\n")),
 153                                         getLocation());
 154             return true;
 155         }
 156
 157         public Token.Location getLocation() { return location; }
 158
 159         /** add a new node (merging with existing nodes if possible)
 160          *  @param parent             the parent of the new node
 161          *  @param result             the SPPF result corresponding to the new node
 162          *  @param state              the state that the new node is in
 163          *  @param fromEmptyReduction true iff this node is being created as a result of a reduction of length zero (see GRMLR paper)
 164          *  @param start              the earliest part of the input contributing to this node (used to make merging decisions)
 165          */
 166         public boolean newNode(Node parent, Forest pending, State state, boolean fromEmptyReduction) {
 167             return newNode(parent, pending, state, fromEmptyReduction, null); }
 168         public boolean newNode(Node parent, Forest pending, State state, boolean fromEmptyReduction, Reduction reduction) {
 169             int pos = parent==null?0:parent.phase()==null?0:parent.phase().pos;
 170             if (reduction!=null) {
 171                 if (inhibited.contains(pos, reduction.position.owner())) return false;
 172                 if (reduction.position.owner().needs != null) {
 173                     for(Sequence s : reduction.position.owner().needs) {
 174                         if (!performed.contains(pos, s)) {
 175                             waiting.add(s, new Waiting(parent, pending, state, fromEmptyReduction, reduction));
 176                             return false;
 177                         }
 178                     }
 179                 }
 180                 performed.add(pos, reduction.position.owner());
 181             }
 182             Node p = hash.get(code(state, parent==null?null:parent.phase()));
 183             boolean ret;
 184             if (reduction!=null) inhibit(reduction, parent==null?0:parent.phase().pos);
 185             if (p != null)  ret = newNode2(p, parent, pending, state, fromEmptyReduction, reduction);
 186             else            ret = newNode3(parent, pending, state, fromEmptyReduction, reduction);
 187             if (reduction != null) {
 188                 boolean redo = true;
 189                 while(redo) {
 190                     redo = false;
 191                     for(Waiting w : waiting.getAll(reduction.position.owner())) {
 192                         if (w.parent==parent || (parent!=null&&w.parent!=null&&w.parent.phase()==parent.phase())) {
 193                             waiting.remove(reduction.position.owner(), w);
 194                             w.perform();
 195                             redo = true;
 196                             break;
 197                         }
 198                     }
 199                 }
 200             }
 201             return ret;
 202         }
 203         private boolean newNode2(Node p, Node parent, Forest pending, State state, boolean fromEmptyReduction, Reduction reduction) {
 204             p.holder.merge(pending);
 205             if (p.parents().contains(parent)) return true;
 206             //if (p.fe && p.phase() != parent.phase()) throw new Error("yep yep");
 207             //if (!p.fe && p.phase() == parent.phase()) throw new Error("yep yep2");
 208             p.parents().add(parent, true);
 209             if (p!=parent && !fromEmptyReduction) p.queueReductions(parent);
 210             return true;
 211         }
 212         private boolean newNode3(Node parent, Forest pending, State state, boolean fromEmptyReduction, Reduction reduction) {
 213             do {
 214                 if (token != null && state.canShift(token)) break;
 215                 if (state.isAccepting()) break;
 216                 if (token==null) break;
 217                 //if (!state.canReduce(token)) return false;
 218                 //if (count > 1) break;
 219                 //if (r.numPop == 0) break;
 220                 //r.reduce(pending, parent, null, Phase.this, null);
 221                 //return;
 222             } while(false);
 223
 224             Node n = new Node(parent, pending, state, fromEmptyReduction);  // ALLOC
 225             n.queueEmptyReductions();
 226             if (!fromEmptyReduction) n.queueReductions(parent);
 227             return true;
 228         }
 229
 230         public void inhibit(Reduction r, int p) {
 231             if (r.position.owner().hated == null) return;
 232             // remember that dead states are still allowed to shift -- just not allowed to reduce
 233             for(Sequence seq : r.position.owner().hated) {
 234                 if (performed.contains(p,seq)) {
 235                     inhibited.clear();
 236                     inhibited.add(p, seq);
 237                     resets++;
 238                     throw new Reset();
 239                 }
 240                 inhibited.add(p, seq);
 241             }
 242         }
 243
 244         /** perform all reduction operations */
 245         public void reduce() {
 246             try {
 247                 reducing = true;
 248                 if (reducing_list==null || reducing_list.length < hash.size())
 249                     reducing_list = new Phase.Node[hash.size() * 4];
 250                 Collection<Node> hv = hash.values();
 251                 hv.toArray(reducing_list);
 252                 int num = hv.size();
 253                 for(int i=0; i<num; i++) {
 254                     Node n = reducing_list[i];
 255                     n.queueEmptyReductions();
 256                     // INVARIANT: we never "see" a node until its parent-set is complete, modulo merges
 257                 }
 258                 for(int i=0; i<num; i++) {
 259                     Node n = reducing_list[i];
 260                     reducing_list[i] = null;
 261                     n.queueReductions();
 262                 }
 263             } catch (Reset r) {
 264                 reset();
 265                 reduce();
 266             }
 267         }
 268
 269         class Reset extends RuntimeException { }
 270
 271         public void invoke(State st, Forest result, Node n) {
 272             good |= next.newNode(n, result, st, false);
 273         }
 274
 275         /** perform all shift operations, adding promoted nodes to <tt>next</tt> */
 276         public void shift(Phase next, Forest result) throws Parser.Failed {
 277             if (prev!=null) prev.hash = null;
 278             this.next = next;
 279             closed = true;
 280             Forest res = null;
 281             boolean ok = false;
 282             for(Phase.Node n : hash.values()) {
 283                 if (n.holder==null) continue;
 284                 n.holder.resolve();
 285                 if (token == null && n.state.isAccepting()) {
 286                     if (finalResult==null) finalResult = new Forest.Ref();
 287                     finalResult.merge(n.holder);
 288                 }
 289                 if (!n.holder.valid()) continue;
 290                 if (token == null) continue;
 291                 n.state.invokeShifts(token, this, result, n);
 292             }
 293
 294             if (!good && token!=null)
 295                 throw new Parser.Failed(error(red("unexpected character")+" "+purple(token)+" encountered at "+green(getLocation())+"\n"),
 296                                         getLocation());
 297             if (token==null && finalResult==null)
 298                 throw new Parser.Failed(error(red("unexpected end of file\n")),
 299                                         getLocation());
 300
 301             // this massively improves GC performance
 302             //hash = null;
 303         }
 304
 305
 306         public class Waiting {
 307             Node parent;
 308             Forest pending;
 309             State state;
 310             boolean fromEmptyReduction;
 311             Reduction reduction;
 312             public Waiting(Node parent, Forest pending, State state, boolean fromEmptyReduction, Reduction reduction) {
 313                 waits++;
 314                 this.parent = parent;
 315                 this.pending = pending;
 316                 this.state = state;
 317                 this.fromEmptyReduction = fromEmptyReduction;
 318                 this.reduction = reduction;
 319             }
 320             public void perform() {
 321                 System.out.println("performing: " + reduction.position);
 322                 newNode(parent, pending, state, fromEmptyReduction, reduction);
 323             }
 324         }
 325
 326         // GSS Nodes //////////////////////////////////////////////////////////////////////////////
 327
 328         /** a node in the GSS */
 329         public final class Node extends FastSet<Node> implements Invokable<Reduction, Node, Node> {
 330
 331             public boolean touched = false;
 332             private Forest.Ref holder = null;
 333             private boolean allqueued = false;
 334
 335             /** what state this node is in */
 336             public final State state;
 337
 338             /** which Phase this Node belongs to (node that Node is also a non-static inner class of Phase) */
 339             public Phase phase() { return Phase.this; }
 340
 341             public  Forest.Ref holder() { return holder==null ? (holder = new Forest.Ref()) : holder; }
 342             public  Forest pending() { return Phase.this.closed ? holder().resolve() : holder; }
 343             public  FastSet<Node> parents() { return this; }
 344
 345             public void queueReductions() {
 346                 if (!reducing) return;
 347                 if (allqueued) return;
 348                 allqueued = true;
 349                 int where = parents().size();
 350                 state.invokeReductions(token, this, this, null);
 351             }
 352
 353             public void queueReductions(Node n2) {
 354                 if (!allqueued) { queueReductions(); return; }
 355                 state.invokeReductions(token, this, this, n2);
 356             }
 357
 358             public final void invoke(Reduction r, Node n, Node n2) {
 359                 if (n==null) {
 360                     if (r.numPop==0) r.reduce(this);
 361                     return;
 362                 }
 363                 if (r.numPop==0) return;
 364                 if (n2==null) r.reduce(n);
 365                 else          r.reduce(n, n2);
 366             }
 367             public void queueEmptyReductions() {
 368                 if (!reducing) return;
 369                 state.invokeReductions(token, this, null, null);
 370             }
 371
 372             private boolean fe;
 373             public boolean dead = false;
 374             public boolean redo = false;
 375             private Node(Node parent, Forest pending, State state, boolean fe) {
 376                 this.fe = fe;
 377                 this.state = state;
 378                 for(Position p : state) {
 379                     if (p.owner().needs!=null)
 380                         for(Sequence s : p.owner().needs) {
 381                             //dead = true;
 382                             //redo = false;
 383                         }
 384                 }
 385                 Phase start = parent==null ? null : parent.phase();
 386                 if (pending != null) this.holder().merge(pending);
 387                 if (parent != null) parents().add(parent, true);
 388                 if (Phase.this.hash.get(code(state, start)) != null) throw new Error("severe problem!");
 389                 Phase.this.hash.put(code(state, start), this);
 390                 Phase.this.numNodes++;
 391                 if (parent==null) holder().valid = true; // hack to make sure that the "base" node is always considered valid
 392             }
 393         }
 394
 395     }
 396
 397     /** helper method */
 398     private static boolean equal(Object a, Object b) {
 399         if (a==null && b==null) return true;
 400         if (a==null || b==null) return false;
 401         return a.equals(b);
 402     }
 403
 404     /** this is something of a hack right now */
 405     private static long code(State state, Phase start) {
 406         return (((long)state.idx) << 32) | (start==null ? 0 : (start.pos+1));
 407     }
 408 }