src/edu/berkeley/sbp/GSS.java

   1 // Copyright 2006 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.Position;
   8 import java.io.*;
   9 import java.util.*;
  10 import java.lang.reflect.*;
  11
  12 /** implements Tomita's Graph Structured Stack */
  13 class GSS {
  14
  15     Input input;
  16     private Parser parser;
  17     public GSS(Input input, Parser parser) { this.input = input; this.parser = parser;}
  18     public Input getInput() { return input; }
  19
  20     int numNewNodes = 0;
  21     int numOldNodes = 0;
  22     int viewPos = 0;
  23     int numReductions = 0;
  24
  25     /** corresponds to a positions <i>between tokens</i> the input stream; same as Tomita's U_i's */
  26     class Phase<Tok> implements Invokable<State, Result>, IntegerMappable, GraphViz.ToGraphViz, Iterable<Node> {
  27
  28         // FIXME: right now, these are the performance bottleneck
  29         private HashMapBag<Integer,Sequence>       performed       = new HashMapBag<Integer,Sequence>();
  30
  31         public Forest.Many finalResult;
  32         private PriorityQueue<Reduction> reductionQueue = new PriorityQueue<Reduction>();
  33
  34         Parser parser() { return parser; }
  35         public void addReduction(Reduction r) {
  36             //System.out.println("+ " + r);
  37             parser.spin();
  38             reductionQueue.add(r);
  39         }
  40         public void invoke(State st, Result result) {
  41             parser.spin();
  42             good |= next.newNode(result, st, false);
  43         }
  44
  45         /** the token immediately after this phase */
  46         final Tok token;
  47         final int pos;
  48
  49         public IntPairMap<Node> hash = new IntPairMap<Node>();  /* ALLOC */
  50         private boolean good = false;
  51         private Phase next = null;
  52         private Phase prev;
  53         private Input.Location location;
  54         private Input.Location nextLocation;
  55         private Input.Location prevLocation;
  56
  57         private Forest forest;
  58
  59         public Phase(State startState) throws ParseFailed, IOException {
  60             this(null, null);
  61             Result primordealResult = new Result(null, null, null);
  62             newNode(primordealResult, startState, true);
  63         }
  64         public Phase(Phase prev, Forest forest) throws ParseFailed, IOException {
  65             this.prevLocation = input.getLocation();
  66             this.token = (Tok)input.next();
  67             this.location = input.getLocation();
  68             this.prev = prev;
  69             this.forest = forest;
  70             this.pos = prev==null ? 0 : prev.pos+1;
  71             this.nextLocation = input.getLocation();
  72             if (prev != null) prev.shift(this, forest);
  73             numReductions = 0;
  74
  75             int minPhasePos = Integer.MAX_VALUE;
  76             int maxOrd = -1;
  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.parentPhase() != null)
  83                     if (r.parentPhase().pos > minPhasePos)
  84                         throw new Error();
  85                 r.perform();
  86                 if (r.parentPhase() != null) {
  87                     if (r.parentPhase().pos < minPhasePos) {
  88                         minPhasePos = r.parentPhase().pos;
  89                         maxOrd = r.reduction().ord;
  90                         best = r;
  91                     } else if (r.parentPhase().pos == minPhasePos) {
  92                         /*
  93                         if (best != null && Parser.mastercache.comparePositions(r.reduction(), best.reduction()) < 0)
  94                             throw new Error("\n"+r+"\n"+best+"\n"+
  95                                             Parser.mastercache.comparePositions(r.reduction(), best.reduction())+"\n"+r.compareTo(best)+
  96                                             "\n"+(r.reduction().ord-best.reduction().ord));
  97                         */
  98                         maxOrd = r.reduction().ord;
  99                         best = r;
 100                     }
 101                 }
 102                 numReductions++;
 103             }
 104             if (token==null) shift(null, null);
 105         }
 106
 107         public boolean isDone() throws ParseFailed {
 108             if (token != null) return false;
 109             if (token==null && finalResult==null)
 110                 ParseFailed.error("unexpected end of file", this);
 111             return true;
 112         }
 113
 114         public Input.Location getPrevLocation() { return prevLocation; }
 115         public Input.Location getLocation() { return location; }
 116         public Input.Region getRegion() { return prevLocation.createRegion(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 result) throws ParseFailed {
 122             this.next = next;
 123             // this massively improves GC performance
 124             if (prev != null) {
 125                 IntPairMap<Node> h = prev.hash;
 126                 prev.hash = null;
 127                 prev.performed = null;
 128                 for(Node n : h)
 129                     n.check();
 130             }
 131             numOldNodes = hash.size();
 132             for(Node n : hash.values()) {
 133                 if (token == null && n.state().isAccepting()) {
 134                     if (finalResult==null) finalResult = new Forest.Many();
 135                     for(Result r : n)
 136                         finalResult.merge(r.getForest());
 137                 }
 138                 if (token == null) continue;
 139                 n.state().invokeShifts(token, this, new Result(result, n, null));
 140             }
 141             numNewNodes = next==null ? 0 : next.hash.size();
 142             viewPos = this.pos;
 143             if (!good && token!=null) ParseFailed.error("unexpected character", this);
 144             if (token==null && finalResult==null) ParseFailed.error("unexpected end of file", this);
 145             for(Node n : hash) n.check();
 146         }
 147
 148         void newNodeFromReduction(Result result, State state, Position reduction) {
 149             int pos = result.phase().pos;
 150             Sequence owner = reduction.owner();
 151             for(Sequence s : owner.hates())
 152                 if (performed.contains(pos, s))
 153                     return;
 154             for(Sequence s : owner.needs())
 155                 if (!performed.contains(pos, s))
 156                     return;
 157             if (owner.needed_or_hated && !performed.contains(pos, owner))
 158                 performed.add(pos, owner);
 159             if (state!=null)
 160                 newNode(result, state, reduction.pos<=0);
 161         }
 162
 163         /** add a new node (merging with existing nodes if possible)
 164          *  @param parent             the parent of the new node
 165          *  @param result             the SPPF result corresponding to the new node
 166          *  @param state              the state that the new node is in
 167          *  @param fromEmptyReduction true iff this node is being created as a result of a reduction of length zero (see GRMLR paper)
 168          *  @param start              the earliest part of the input contributing to this node (used to make merging decisions)
 169          */
 170         private boolean newNode(Result result, State state, boolean fromEmptyReduction) {
 171             Node p = hash.get(state, result.phase());
 172             if (p != null) { p.addResult(result); return true; }
 173             do {
 174                 if (token != null && state.canShift(token)) break;
 175                 if (state.isAccepting()) break;
 176                 if (token==null) break;
 177                 if (!state.canReduce(token)) return false;
 178             } while(false);
 179             Node n = new Node(Phase.this, result, state, fromEmptyReduction);  // ALLOC
 180             for(Object s : state.conjunctStates)
 181                 newNode(new Result(null, n, null), (State)s, fromEmptyReduction);
 182             return true;
 183         }
 184
 185         public int toInt() { return pos+1; }
 186         public int size() { return hash==null ? 0 : hash.size(); }
 187         public int pos() { return pos; }
 188         public Tok getToken() { return token; }
 189         public Iterator<Node> iterator() { return hash.iterator(); }
 190         public GSS getGSS() { return GSS.this; }
 191
 192         // GraphViz //////////////////////////////////////////////////////////////////////////////
 193
 194         public GraphViz.Node toGraphViz(GraphViz gv) {
 195             if (gv.hasNode(this)) return gv.createNode(this);
 196             GraphViz.Group g = gv.createGroup(this);
 197             g.label = "Phase " + pos;
 198             g.color = "gray";
 199             g.cluster = true;
 200             return g;
 201         }
 202         public boolean isTransparent() { return false; }
 203         public boolean isHidden() { return false; }
 204
 205         public void dumpGraphViz(String filename) throws IOException {
 206             FileOutputStream fos = new FileOutputStream(filename);
 207             PrintWriter p = new PrintWriter(new OutputStreamWriter(fos));
 208             GraphViz gv = new GraphViz();
 209             for(Object n : this)
 210                 ((Node)n).toGraphViz(gv);
 211             gv.dump(p);
 212             p.flush();
 213             p.close();
 214         }
 215
 216     }
 217
 218 }