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