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                 if ((reduction.position.owner().needed != null && reduction.position.owner().needed.size()>0) ||
 181                     (reduction.position.owner().hated != null && reduction.position.owner().hated.size()>0) ||
 182                     (reduction.position.owner().hates != null && reduction.position.owner().hates.size()>0))
 183                     performed.add(pos, reduction.position.owner());
 184             }
 185             Node p = hash.get(code(state, parent==null?null:parent.phase()));
 186             boolean ret;
 187             if (reduction!=null) inhibit(reduction, parent==null?0:parent.phase().pos);
 188             if (p != null)  ret = newNode2(p, parent, pending, state, fromEmptyReduction, reduction);
 189             else            ret = newNode3(parent, pending, state, fromEmptyReduction, reduction);
 190             if (reduction != null) {
 191                 boolean redo = true;
 192                 while(redo) {
 193                     redo = false;
 194                     for(Waiting w : waiting.getAll(reduction.position.owner())) {
 195                         if (w.parent==parent || (parent!=null&&w.parent!=null&&w.parent.phase()==parent.phase())) {
 196                             waiting.remove(reduction.position.owner(), w);
 197                             w.perform();
 198                             redo = true;
 199                             break;
 200                         }
 201                     }
 202                 }
 203             }
 204             return ret;
 205         }
 206         private boolean newNode2(Node p, Node parent, Forest pending, State state, boolean fromEmptyReduction, Reduction reduction) {
 207             p.holder.merge(pending);
 208             if (p.parents().contains(parent)) return true;
 209             //if (p.fe && p.phase() != parent.phase()) throw new Error("yep yep");
 210             //if (!p.fe && p.phase() == parent.phase()) throw new Error("yep yep2");
 211             p.parents().add(parent, true);
 212             if (p!=parent && !fromEmptyReduction) p.queueReductions(parent);
 213             return true;
 214         }
 215         private boolean newNode3(Node parent, Forest pending, State state, boolean fromEmptyReduction, Reduction reduction) {
 216             do {
 217                 if (token != null && state.canShift(token)) break;
 218                 if (state.isAccepting()) break;
 219                 if (token==null) break;
 220                 //if (!state.canReduce(token)) return false;
 221                 //if (count > 1) break;
 222                 //if (r.numPop == 0) break;
 223                 //r.reduce(pending, parent, null, Phase.this, null);
 224                 //return;
 225             } while(false);
 226
 227             Node n = new Node(parent, pending, state, fromEmptyReduction);  // ALLOC
 228             n.queueEmptyReductions();
 229             if (!fromEmptyReduction) n.queueReductions(parent);
 230             return true;
 231         }
 232
 233         public void uninhibit(int p, Sequence s) {
 234             if (s.hated!=null)
 235                 for(Sequence s2 : s.hated)
 236                     inhibited.remove(p, s2);
 237         }
 238
 239         public void inhibit(Reduction r, int p) {
 240             if (r.position.owner().hated == null) return;
 241             // remember that dead states are still allowed to shift -- just not allowed to reduce
 242             boolean reset = false;
 243             for(Sequence seq : r.position.owner().hated) {
 244                 if (performed.contains(p,seq)) {
 245                     uninhibit(p, seq);
 246                     //System.out.println("\nresetting due to " + r.position.owner() + " killing " + seq);
 247                     if (!reset) inhibited.add(p, seq);
 248                     reset = true;
 249                 }
 250                 if (!reset) inhibited.add(p, seq);
 251             }
 252             if (reset) {
 253                 resets++;
 254                 throw new Reset();
 255             }
 256         }
 257
 258         /** perform all reduction operations */
 259         public void reduce() {
 260             try {
 261                 reducing = true;
 262                 if (reducing_list==null || reducing_list.length < hash.size())
 263                     reducing_list = new Phase.Node[hash.size() * 4];
 264                 Collection<Node> hv = hash.values();
 265                 hv.toArray(reducing_list);
 266                 int num = hv.size();
 267                 for(int i=0; i<num; i++) {
 268                     Node n = reducing_list[i];
 269                     n.queueEmptyReductions();
 270                     // INVARIANT: we never "see" a node until its parent-set is complete, modulo merges
 271                 }
 272                 for(int i=0; i<num; i++) {
 273                     Node n = reducing_list[i];
 274                     reducing_list[i] = null;
 275                     n.queueReductions();
 276                 }
 277             } catch (Reset r) {
 278                 reset();
 279                 reduce();
 280             }
 281         }
 282
 283         class Reset extends RuntimeException { }
 284
 285         public void invoke(State st, Forest result, Node n) {
 286             good |= next.newNode(n, result, st, false);
 287         }
 288
 289         /** perform all shift operations, adding promoted nodes to <tt>next</tt> */
 290         public void shift(Phase next, Forest result) throws Parser.Failed {
 291             if (prev!=null) prev.hash = null;
 292             this.next = next;
 293             closed = true;
 294             Forest res = null;
 295             boolean ok = false;
 296             for(Phase.Node n : hash.values()) {
 297                 if (n.holder==null) continue;
 298                 n.holder.resolve();
 299                 if (token == null && n.state.isAccepting()) {
 300                     if (finalResult==null) finalResult = new Forest.Ref();
 301                     finalResult.merge(n.holder);
 302                 }
 303                 if (!n.holder.valid()) continue;
 304                 if (token == null) continue;
 305                 n.state.invokeShifts(token, this, result, n);
 306             }
 307
 308             if (!good && token!=null)
 309                 throw new Parser.Failed(error(red("unexpected character")+" "+purple(token)+" encountered at "+green(getLocation())+"\n"),
 310                                         getLocation());
 311             if (token==null && finalResult==null)
 312                 throw new Parser.Failed(error(red("unexpected end of file\n")),
 313                                         getLocation());
 314
 315             // this massively improves GC performance
 316             //hash = null;
 317         }
 318
 319
 320         public class Waiting {
 321             Node parent;
 322             Forest pending;
 323             State state;
 324             boolean fromEmptyReduction;
 325             Reduction reduction;
 326             public Waiting(Node parent, Forest pending, State state, boolean fromEmptyReduction, Reduction reduction) {
 327                 waits++;
 328                 this.parent = parent;
 329                 this.pending = pending;
 330                 this.state = state;
 331                 this.fromEmptyReduction = fromEmptyReduction;
 332                 this.reduction = reduction;
 333             }
 334             public void perform() {
 335                 //System.out.println("performing: " + reduction.position);
 336                 newNode(parent, pending, state, fromEmptyReduction, reduction);
 337             }
 338         }
 339
 340         // GSS Nodes //////////////////////////////////////////////////////////////////////////////
 341
 342         /** a node in the GSS */
 343         public final class Node extends FastSet<Node> implements Invokable<Reduction, Node, Node> {
 344
 345             public boolean touched = false;
 346             private Forest.Ref holder = null;
 347             private boolean allqueued = false;
 348
 349             /** what state this node is in */
 350             public final State state;
 351
 352             /** which Phase this Node belongs to (node that Node is also a non-static inner class of Phase) */
 353             public Phase phase() { return Phase.this; }
 354
 355             public  Forest.Ref holder() { return holder==null ? (holder = new Forest.Ref()) : holder; }
 356             public  Forest pending() { return Phase.this.closed ? holder().resolve() : holder; }
 357             public  FastSet<Node> parents() { return this; }
 358
 359             public void queueReductions() {
 360                 if (!reducing) return;
 361                 if (allqueued) return;
 362                 allqueued = true;
 363                 int where = parents().size();
 364                 state.invokeReductions(token, this, this, null);
 365             }
 366
 367             public void queueReductions(Node n2) {
 368                 if (!allqueued) { queueReductions(); return; }
 369                 state.invokeReductions(token, this, this, n2);
 370             }
 371
 372             public final void invoke(Reduction r, Node n, Node n2) {
 373                 if (n==null) {
 374                     if (r.numPop==0) r.reduce(this);
 375                     return;
 376                 }
 377                 if (r.numPop==0) return;
 378                 if (n2==null) r.reduce(n);
 379                 else          r.reduce(n, n2);
 380             }
 381             public void queueEmptyReductions() {
 382                 if (!reducing) return;
 383                 state.invokeReductions(token, this, null, null);
 384             }
 385
 386             private boolean fe;
 387             public boolean dead = false;
 388             public boolean redo = false;
 389             private Node(Node parent, Forest pending, State state, boolean fe) {
 390                 this.fe = fe;
 391                 this.state = state;
 392                 for(Position p : state) {
 393                     if (p.owner().needs!=null)
 394                         for(Sequence s : p.owner().needs) {
 395                             //dead = true;
 396                             //redo = false;
 397                         }
 398                 }
 399                 Phase start = parent==null ? null : parent.phase();
 400                 if (pending != null) this.holder().merge(pending);
 401                 if (parent != null) parents().add(parent, true);
 402                 if (Phase.this.hash.get(code(state, start)) != null) throw new Error("severe problem!");
 403                 Phase.this.hash.put(code(state, start), this);
 404                 Phase.this.numNodes++;
 405                 if (parent==null) holder().valid = true; // hack to make sure that the "base" node is always considered valid
 406             }
 407         }
 408
 409     }
 410
 411     /** helper method */
 412     private static boolean equal(Object a, Object b) {
 413         if (a==null && b==null) return true;
 414         if (a==null || b==null) return false;
 415         return a.equals(b);
 416     }
 417
 418     /** this is something of a hack right now */
 419     private static long code(State state, Phase start) {
 420         return (((long)state.idx) << 32) | (start==null ? 0 : (start.pos+1));
 421     }
 422 }