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