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     public GSS(Input input) { this.input = input; }
  17     public Input getInput() { return input; }
  18
  19     // FIXME: right now, these are the performance bottleneck
  20     HashMapBag<Integer,Sequence>       performed       = new HashMapBag<Integer,Sequence>();
  21
  22     /** FIXME */
  23     Forest.Many finalResult;
  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, Object>, IntegerMappable, GraphViz.ToGraphViz, Iterable<Node> {
  27
  28         public ArrayList<Reduction> reductionQueue = new ArrayList<Reduction>();
  29
  30         public void invoke(State st, Result result, Object o) {
  31             //shifts++;
  32             good |= next.newNode(result, st, false);
  33         }
  34
  35         /** the token immediately after this phase */
  36         final Tok token;
  37         final int pos;
  38
  39         public IntPairMap<Node> hash;  /* ALLOC */
  40         private boolean good;
  41         private Phase next = null;
  42         private Phase prev;
  43         private Input.Location location;
  44         private Input.Location nextLocation;
  45         private Input.Location prevLocation;
  46
  47         private Forest forest;
  48
  49         public Phase(Phase prev, Phase previous, Tok token, Input.Location location,
  50                      Input.Location nextLocation, Forest forest) throws ParseFailed {
  51             this.prevLocation = prev==null ? location : prev.getLocation();
  52             this.prev = prev;
  53             this.forest = forest;
  54             this.pos = previous==null ? 0 : previous.pos+1;
  55             this.token = token;
  56             this.location = location;
  57             this.nextLocation = nextLocation;
  58             performed.clear();
  59             hash = new IntPairMap<Node>();
  60             good = false;
  61             finalResult = null;
  62             if (prev != null) prev.shift(this, forest);
  63         }
  64
  65         public boolean isFrontier() { return next==null; }
  66         public boolean isDone() throws ParseFailed {
  67             if (token != null) return false;
  68             if (token==null && finalResult==null)
  69                 ParseFailed.error("unexpected end of file", this);
  70             return true;
  71         }
  72
  73         public Input.Location getPrevLocation() { return prevLocation; }
  74         public Input.Location getLocation() { return location; }
  75         public Input.Region   getRegion() { return getPrevLocation().createRegion(getLocation()); }
  76         public Input.Location getNextLocation() { return nextLocation; }
  77
  78         /** perform all shift operations, adding promoted nodes to <tt>next</tt> */
  79         public void shift(Phase next, Forest result) throws ParseFailed {
  80             // this massively improves GC performance
  81             if (prev!=null) prev.hash = null;
  82             this.next = next;
  83             for(Node n : hash.values()) {
  84                 if (token == null && n.state().isAccepting()) {
  85                     if (finalResult==null) finalResult = new Forest.Many();
  86                     for(Result r : n)
  87                         finalResult.merge(r.getForest());
  88                 }
  89                 if (token == null) continue;
  90                 n.state().invokeShifts(token, this, new Result(result, n, null), null);
  91             }
  92             if (!good && token!=null) ParseFailed.error("unexpected character", this);
  93             if (token==null && finalResult==null) ParseFailed.error("unexpected end of file", this);
  94         }
  95
  96         /** perform all reduction operations */
  97         public void reduce() throws ParseFailed {
  98             Reduction last = null;
  99             while(!reductionQueue.isEmpty()) {
 100                 Reduction r = null;
 101
 102                 // ugly
 103                 OUTER: for(int i=0; i<reductionQueue.size(); i++) {
 104                     for(int j=0; j<reductionQueue.size(); j++) {
 105                         if (i==j) continue;
 106                         if (reductionQueue.get(i).compareTo(reductionQueue.get(j)) > 0)
 107                             continue OUTER;
 108                     }
 109                     r = reductionQueue.get(i);
 110                     reductionQueue.remove(r);
 111                     break;
 112                 }
 113
 114                 /*
 115                 if (last == null) last = r;
 116                 else if (r.compareTo(last) > 0) last = r;
 117                 else if (r.compareTo(last) < 0) {
 118                     if (r.targetPhase() != null)
 119                         System.out.println("err " + last.compareTo(r) + " " + last.targetPhase().pos() +
 120                                            " "    + r.targetPhase().pos() + " " + pos);
 121                 }
 122                 */
 123
 124                 r.perform();
 125             }
 126         }
 127
 128         public void newNodeFromReduction(Result result, State state, boolean fromEmptyReduction, Position reduction) {
 129             int pos = result.phase().pos;
 130             Sequence owner = reduction.owner();
 131             for(Sequence s : owner.hates)
 132                 if (performed.contains(pos, s))
 133                     return;
 134             for(Sequence s : owner.needs)
 135                 if (!performed.contains(pos, s))
 136                     return;
 137             if (owner.needed_or_hated && !performed.contains(pos, owner))
 138                 performed.add(pos, owner);
 139             if (state!=null)
 140                 newNode(result, state, fromEmptyReduction);
 141         }
 142
 143         /** add a new node (merging with existing nodes if possible)
 144          *  @param parent             the parent of the new node
 145          *  @param result             the SPPF result corresponding to the new node
 146          *  @param state              the state that the new node is in
 147          *  @param fromEmptyReduction true iff this node is being created as a result of a reduction of length zero (see GRMLR paper)
 148          *  @param start              the earliest part of the input contributing to this node (used to make merging decisions)
 149          */
 150         public boolean newNode(Result result, State state, boolean fromEmptyReduction) {
 151             Node p = hash.get(state, result.phase());
 152             if (p != null) { p.merge(result); return true; }
 153             do {
 154                 if (token != null && state.canShift(token)) break;
 155                 if (state.isAccepting()) break;
 156                 if (token==null) break;
 157                 if (!state.canReduce(token)) return false;
 158             } while(false);
 159             new Node(Phase.this, result, state, fromEmptyReduction);  // ALLOC
 160             return true;
 161         }
 162
 163         public int toInt() { return pos+1; }
 164         public int size() { return hash==null ? 0 : hash.size(); }
 165         public int pos() { return pos; }
 166         public Tok getToken() { return token; }
 167         public Iterator<Node> iterator() { return hash.iterator(); }
 168         public GSS getGSS() { return GSS.this; }
 169
 170         // GraphViz //////////////////////////////////////////////////////////////////////////////
 171
 172         public GraphViz.Node toGraphViz(GraphViz gv) {
 173             if (gv.hasNode(this)) return gv.createNode(this);
 174             GraphViz.Group g = gv.createGroup(this);
 175             g.label = "Phase " + pos;
 176             g.color = "gray";
 177             g.cluster = true;
 178             return g;
 179         }
 180         public boolean isTransparent() { return false; }
 181         public boolean isHidden() { return false; }
 182
 183     }
 184
 185 }