src/edu/berkeley/sbp/GSS.java

   1 // Copyright 2006-2007 all rights reserved; see LICENSE file for BSD-style license
   2
   3 package edu.berkeley.sbp;
   4 import edu.berkeley.sbp.*;
   5 import edu.berkeley.sbp.util.*;
   6 import edu.berkeley.sbp.Parser.Table.*;
   7 import edu.berkeley.sbp.Sequence.Pos;
   8 import edu.berkeley.sbp.Sequence.Pos;
   9 import java.io.*;
  10 import java.util.*;
  11 import java.lang.reflect.*;
  12
  13 /** implements Tomita's Graph Structured Stack */
  14 class GSS {
  15
  16     Input input;
  17     private Parser parser;
  18     public GSS(Input input, Parser parser) { this.input = input; this.parser = parser;}
  19     public Input getInput() { return input; }
  20
  21     int numNewNodes = 0;
  22     int numOldNodes = 0;
  23     int viewPos = 0;
  24     int numReductions = 0;
  25
  26     /** corresponds to a positions <i>between tokens</i> the input stream; same as Tomita's U_i's */
  27     class Phase<Tok> implements Invokable<State, StateNode, Forest>, IntegerMappable, GraphViz.ToGraphViz /*, Iterable<StateNode>*/ {
  28
  29         // FIXME: right now, these are the performance bottleneck
  30         private HashMapBag<Integer,Integer>       performed       = new HashMapBag<Integer,Integer>();
  31
  32         public Forest.Many finalResult;
  33         private PriorityQueue<Reduction> reductionQueue = new PriorityQueue<Reduction>();
  34
  35         Parser parser() { return parser; }
  36         public void addReduction(Reduction r) {
  37             //System.out.println("+ " + r);
  38             parser.spin();
  39             reductionQueue.add(r);
  40         }
  41
  42         public void invoke(State st, StateNode pred, Forest f) {
  43             parser.spin();
  44             good |= next.newNode(f, null, pred, st);
  45         }
  46
  47         /** the token immediately after this phase */
  48         final Tok token;
  49         final int pos;
  50         public IntPairMap<StateNode> hash = new IntPairMap<StateNode>();  /* ALLOC */
  51         private boolean good = false;
  52         private Phase next = null;
  53         private Phase prev;
  54         private Input.Location location;
  55         private Input.Location nextLocation;
  56
  57         private Forest forest;
  58
  59         public Phase(State startState) throws ParseFailed, IOException {
  60             this(null, null);
  61             newNode(null, null, null, startState);
  62         }
  63         public Phase(Phase prev, Forest forest) throws ParseFailed, IOException {
  64             this.location = input.getLocation();
  65             this.token = (Tok)input.next();
  66             this.nextLocation = input.getLocation();
  67             this.prev = prev;
  68             this.forest = forest;
  69             this.pos = prev==null ? 0 : prev.pos+1;
  70             if (prev != null) prev.shift(this, forest);
  71             numReductions = 0;
  72             /*
  73             finishedReductions.clear();
  74             */
  75
  76             int minPhasePos = Integer.MAX_VALUE;
  77             Reduction best = null;
  78             //System.out.println("==============================================================================");
  79             while(!reductionQueue.isEmpty()) {
  80                 Reduction r = reductionQueue.poll();
  81                 //System.out.println("- " + r);
  82                 if (r.predPhase() != null)
  83                     if (r.predPhase().pos > minPhasePos)
  84                         throw new Error();
  85                 r.perform();
  86                 if (r.predPhase() != null) {
  87                     if (r.predPhase().pos < minPhasePos) {
  88                         minPhasePos = r.predPhase().pos;
  89                         best = r;
  90                     } else if (r.predPhase().pos == minPhasePos) {
  91                         /*
  92                         if (best != null && Parser.mastercache.comparePositions(r.reduction(), best.reduction()) < 0)
  93                             throw new Error("\n"+r+"\n"+best+"\n"+
  94                                             Parser.mastercache.comparePositions(r.reduction(), best.reduction())+"\n"+r.compareTo(best)+
  95                                             "\n"+(r.reduction().ord-best.reduction().ord));
  96                         */
  97                         best = r;
  98                     }
  99                 }
 100                 /*
 101                 finishedReductions.add(r);
 102                 */
 103                 numReductions++;
 104             }
 105             if (token==null) shift(null, null);
 106         }
 107
 108         public boolean isDone() throws ParseFailed {
 109             if (token != null) return false;
 110             if (token==null && finalResult==null)
 111                 ParseFailed.error("unexpected end of file", this, null,
 112                                   getLocation().createRegion(getLocation()));
 113             return true;
 114         }
 115
 116         public Input.Location getLocation() { return location; }
 117         public Input.Location getNextLocation() { return nextLocation; }
 118         public boolean        isFrontier() { return hash!=null; }
 119
 120         /** perform all shift operations, adding promoted nodes to <tt>next</tt> */
 121         private void shift(Phase next, Forest f) throws ParseFailed {
 122             this.next = next;
 123             // this massively improves GC performance
 124             if (prev != null) {
 125                 IntPairMap<StateNode> h = prev.hash;
 126                 prev.hash = null;
 127                 prev.performed = null;
 128                 for(StateNode n : h) n.check();
 129             }
 130             numOldNodes = hash.size();
 131             for(StateNode n : hash) {
 132                 if (token == null && n.state().isAccepting()) {
 133                     if (finalResult==null) finalResult = new Forest.Many();
 134                     for(ResultNode r : n)
 135                         finalResult.merge(r.getForest());
 136                 }
 137                 if (token == null) continue;
 138                 n.state().invokeShifts(token, this, n, f);
 139             }
 140             numNewNodes = next==null ? 0 : next.hash.size();
 141             viewPos = this.pos;
 142
 143             if (!good && token!=null) {
 144                 String toks = token+"";
 145                 if (toks.length()==1 && toks.charAt(0) == edu.berkeley.sbp.chr.CharAtom.left) {
 146                     ParseFailed.error("unexpected increase in indentation", this,
 147                                       token, getRegionFromThisToNext());
 148                 } else if (toks.length()==1 && toks.charAt(0) == edu.berkeley.sbp.chr.CharAtom.right) {
 149                     ParseFailed.error("unexpected decrease in indentation", this,
 150                                       token, getRegionFromThisToNext());
 151                 } else {
 152                     ParseFailed.error("unexpected character '"+ANSI.cyan(StringUtil.escapify(token+"",
 153                                                                                              "\\\'\r\n"))+"'",
 154                                       this, token, getRegionFromThisToNext());
 155                 }
 156             }
 157             if (token==null && finalResult==null)
 158                 ParseFailed.error("unexpected end of file", this, null,
 159                                   getLocation().createRegion(getLocation()));
 160             for(StateNode n : hash) n.check();
 161         }
 162
 163         Input.Region getRegionFromThisToNext() {
 164             return getLocation().createRegion(getNextLocation());
 165         }
 166
 167         void newNodeFromReduction(Forest f, Pos reduction, StateNode pred) {
 168             int pos = pred.phase().pos;
 169             for(int s : reduction.hates())
 170                 if (performed.contains(pos, s))
 171                     return;
 172             for(int s : reduction.needs())
 173                 if (!performed.contains(pos, s))
 174                     return;
 175             if (reduction.owner_needed_or_hated() && !performed.contains(pos, reduction.provides()))
 176                 performed.add(pos, reduction.provides());
 177             Parser.Table.State state = (Parser.Table.State)pred.state().gotoSetNonTerminals.get(reduction);
 178             if (state!=null)
 179                 newNode(f, reduction, pred, state);
 180         }
 181
 182         /** add a new node (merging with existing nodes if possible)
 183          *  @param parent             the parent of the new node
 184          *  @param result             the SPPF result corresponding to the new node
 185          *  @param state              the state that the new node is in
 186          *  @param start              the earliest part of the input contributing to this node (used to make merging decisions)
 187          */
 188         private boolean newNode(Forest f, Pos reduction, StateNode pred, State state) {
 189             StateNode p = pred==null ? null : hash.get(state, pred.phase());
 190             if (p != null) {
 191                 p.addPred(f, reduction, pred);
 192                 return !state.doomed();
 193             }
 194             do {
 195                 // optimizations
 196                 if (token != null && state.canShift(token)) break;
 197                 if (state.isAccepting()) break;
 198                 if (token==null) break;
 199                 if (!state.canReduce(token)) return false;
 200             } while(false);
 201             StateNode n = new StateNode(Phase.this, new ResultNode(f, reduction, pred), state);  // ALLOC
 202             /** FIXME: this null-result can be used to notice bogus/dead states */
 203             for(Object s : state.conjunctStates)
 204                 newNode(null, null, n, (State)s);
 205             return !n.state().doomed();
 206         }
 207
 208         public int toInt() { return pos+1; }
 209         public int size() { return hash==null ? 0 : hash.size(); }
 210         public int pos() { return pos; }
 211         public Tok getToken() { return token; }
 212         //public Iterator<StateNode> iterator() { return hash.iterator(); }
 213         public GSS getGSS() { return GSS.this; }
 214
 215         // GraphViz //////////////////////////////////////////////////////////////////////////////
 216
 217         public GraphViz.StateNode toGraphViz(GraphViz gv) {
 218             if (gv.hasNode(this)) return gv.createNode(this);
 219             GraphViz.Group g = gv.createGroup(this);
 220             g.label = "Phase " + pos;
 221             g.color = "gray";
 222             g.cluster = true;
 223             return g;
 224         }
 225         public boolean isTransparent() { return false; }
 226         public boolean isHidden() { return false; }
 227
 228         public void dumpGraphViz(String filename) throws IOException {
 229             FileOutputStream fos = new FileOutputStream(filename);
 230             PrintWriter p = new PrintWriter(new OutputStreamWriter(fos));
 231             GraphViz gv = new GraphViz();
 232             /*
 233             for(Object n : this)
 234                 ((StateNode)n).toGraphViz(gv);
 235             */
 236             gv.dump(p);
 237             p.flush();
 238             p.close();
 239         }
 240
 241     }
 242
 243 }