X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FGSS.java;h=2d2e550cce16e613bec3951d8d8a348a0ba949d9;hp=4f8b4a9802b9b5fcdbde5fbd4bc3869fddf3cdd8;hb=76ce41540f06ac1fbcb44332dd62f53e88c27cf1;hpb=728fe06ea2e91634cfeae617b03dc42d35dc2f23

diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java
index 4f8b4a9..2d2e550 100644
--- a/src/edu/berkeley/sbp/GSS.java
+++ b/src/edu/berkeley/sbp/GSS.java
@@ -1,9 +1,11 @@
+// Copyright 2006-2007 all rights reserved; see LICENSE file for BSD-style license
+
 package edu.berkeley.sbp;
 import edu.berkeley.sbp.*;
 import edu.berkeley.sbp.util.*;
-import edu.berkeley.sbp.Sequence.Position;
-import edu.berkeley.sbp.Parser.Table.State;
-import edu.berkeley.sbp.Parser.Table.Reduction;
+import edu.berkeley.sbp.Parser.Table.*;
+import edu.berkeley.sbp.Sequence.Pos;
+import edu.berkeley.sbp.Sequence.Pos;
 import java.io.*;
 import java.util.*;
 import java.lang.reflect.*;
@@ -11,69 +13,174 @@ import java.lang.reflect.*;
 /** implements Tomita's Graph Structured Stack */
 class GSS {
 
-    public GSS() { }
-
-    private Phase.Node[] reducing_list = null;
-    public int resets = 0;
-    public int waits = 0;
+    Input input;
+    private Parser parser;
+    public GSS(Input input, Parser parser) { this.input = input; this.parser = parser;}
+    public Input getInput() { return input; }
 
-    HashMapBag<Integer,Sequence>       inhibited = new HashMapBag<Integer,Sequence>();
-    HashMapBag<Sequence,Phase.Waiting> waiting   = new HashMapBag<Sequence,Phase.Waiting>();
-    HashMapBag<Integer,Sequence>       performed = new HashMapBag<Integer,Sequence>();
-    
-    /** FIXME */
-    public  Forest.Ref finalResult;
+    /*
+    HashSet<Reduction> finishedReductions = new HashSet<Reduction>();
+    */
+    int numNewNodes = 0;
+    int numOldNodes = 0;
+    int viewPos = 0;
+    int numReductions = 0;
 
     /** corresponds to a positions <i>between tokens</i> the input stream; same as Tomita's U_i's */
-    public class Phase implements Invokable<State, Forest, GSS.Phase.Node>, IntegerMappable {
+    class Phase<Tok> implements Invokable<State, StateNode, Forest>, IntegerMappable, GraphViz.ToGraphViz, Iterable<StateNode> {
 
-        /** the token immediately after this phase */
-        final Token token;
+        // FIXME: right now, these are the performance bottleneck
+        private HashMapBag<Integer,Integer>       performed       = new HashMapBag<Integer,Integer>();
 
-        private final int pos;
+        public Forest.Many finalResult;
+        private PriorityQueue<Reduction> reductionQueue = new PriorityQueue<Reduction>();
 
-        boolean reducing;
-        private IntPairMap<Phase.Node> hash;  /* ALLOC */
-        private boolean closed;
-        private boolean good;
+        Parser parser() { return parser; }
+        public void addReduction(Reduction r) {
+            //System.out.println("+ " + r);
+            parser.spin();
+            reductionQueue.add(r);
+        }
+
+        public void invoke(State st, StateNode pred, Forest f) {
+            parser.spin();
+            good |= next.newNode(f, null, pred, st, false);
+        }
+
+        /** the token immediately after this phase */
+        final Tok token;
+        final int pos;
+        public IntPairMap<StateNode> hash = new IntPairMap<StateNode>();  /* ALLOC */
+        private boolean good = false;
         private Phase next = null;
         private Phase prev;
-        private Token.Location location;
-        public final Parser parser;
-
+        private Input.Location location;
+        private Input.Location nextLocation;
+        
         private Forest forest;
 
-        public Phase(Phase prev, Parser parser, Phase previous, Token token, Token.Location location, Forest forest) {
+        public Phase(State startState) throws ParseFailed, IOException {
+            this(null, null);
+            newNode(null, null, null, startState, true);
+        }
+        public Phase(Phase prev, Forest forest) throws ParseFailed, IOException {
+            this.location = input.getLocation();
+            this.token = (Tok)input.next();
+            this.nextLocation = input.getLocation();
             this.prev = prev;
             this.forest = forest;
-            this.parser = parser;
-            this.pos = previous==null ? 0 : previous.pos+1;
-            this.token = token;
-            this.location = location;
-            inhibited.clear();
-            reset();
-        }
-
-        public void reset() {
-            waiting.clear();
-            performed.clear();
-            hash = new IntPairMap<Phase.Node>();
-            good = false;
-            closed = false;
-            reducing = false;
-            finalResult = null;
+            this.pos = prev==null ? 0 : prev.pos+1;
             if (prev != null) prev.shift(this, forest);
+            numReductions = 0;
+            /*
+            finishedReductions.clear();
+            */
+
+            int minPhasePos = Integer.MAX_VALUE;
+            Reduction best = null;
+            //System.out.println("==============================================================================");
+            while(!reductionQueue.isEmpty()) {
+                Reduction r = reductionQueue.poll();
+                //System.out.println("- " + r);
+                if (r.predPhase() != null)
+                    if (r.predPhase().pos > minPhasePos)
+                        throw new Error();
+                r.perform();
+                if (r.predPhase() != null) {
+                    if (r.predPhase().pos < minPhasePos) {
+                        minPhasePos = r.predPhase().pos;
+                        best = r;
+                    } else if (r.predPhase().pos == minPhasePos) {
+                        /*
+                        if (best != null && Parser.mastercache.comparePositions(r.reduction(), best.reduction()) < 0)
+                            throw new Error("\n"+r+"\n"+best+"\n"+
+                                            Parser.mastercache.comparePositions(r.reduction(), best.reduction())+"\n"+r.compareTo(best)+
+                                            "\n"+(r.reduction().ord-best.reduction().ord));
+                        */
+                        best = r;
+                    }
+                }
+                /*
+                finishedReductions.add(r);
+                */
+                numReductions++;
+            }
+            if (token==null) shift(null, null);
         }
 
-      
         public boolean isDone() throws ParseFailed {
             if (token != null) return false;
             if (token==null && finalResult==null)
-                throw new ParseFailed(ParseFailed.error(ANSI.red("unexpected end of file\n"), token, hash.values()), getLocation());
+                ParseFailed.error("unexpected end of file", this, null,
+                                  getLocation().createRegion(getLocation()));
             return true;
         }
 
-        public Token.Location getLocation() { return location; }
+        public Input.Location getLocation() { return location; }
+        public Input.Location getNextLocation() { return nextLocation; }
+        public boolean        isFrontier() { return hash!=null; }
+
+        /** perform all shift operations, adding promoted nodes to <tt>next</tt> */
+        private void shift(Phase next, Forest f) throws ParseFailed {
+            this.next = next;
+            // this massively improves GC performance
+            if (prev != null) {
+                IntPairMap<StateNode> h = prev.hash;
+                prev.hash = null;
+                prev.performed = null;
+                for(StateNode n : h) n.check();
+            }
+            numOldNodes = hash.size();
+            for(StateNode n : hash.values()) {
+                if (token == null && n.state().isAccepting()) {
+                    if (finalResult==null) finalResult = new Forest.Many();
+                    for(ResultNode r : n)
+                        finalResult.merge(r.getForest());
+                }
+                if (token == null) continue;
+                n.state().invokeShifts(token, this, n, f);
+            }
+            numNewNodes = next==null ? 0 : next.hash.size();
+            viewPos = this.pos;
+
+            if (!good && token!=null) {
+                String toks = token+"";
+                if (toks.length()==1 && toks.charAt(0) == edu.berkeley.sbp.chr.CharAtom.left) {
+                    ParseFailed.error("unexpected increase in indentation", this,
+                                      token, getRegionFromThisToNext());
+                } else if (toks.length()==1 && toks.charAt(0) == edu.berkeley.sbp.chr.CharAtom.right) {
+                    ParseFailed.error("unexpected decrease in indentation", this,
+                                      token, getRegionFromThisToNext());
+                } else {
+                    ParseFailed.error("unexpected character '"+ANSI.cyan(StringUtil.escapify(token+"",
+                                                                                             "\\\'\r\n"))+"'",
+                                      this, token, getRegionFromThisToNext());
+                }
+            }
+            if (token==null && finalResult==null)
+                ParseFailed.error("unexpected end of file", this, null,
+                                  getLocation().createRegion(getLocation()));
+            for(StateNode n : hash) n.check();
+        }
+
+        Input.Region getRegionFromThisToNext() {
+            return getLocation().createRegion(getNextLocation());
+        }
+
+        void newNodeFromReduction(Forest f, Pos reduction, StateNode pred) {
+            int pos = pred.phase().pos;
+            for(int s : reduction.hates())
+                if (performed.contains(pos, s))
+                    return;
+            for(int s : reduction.needs())
+                if (!performed.contains(pos, s))
+                    return;
+            if (reduction.owner_needed_or_hated() && !performed.contains(pos, reduction.provides()))
+                performed.add(pos, reduction.provides());
+            Parser.Table.State state = (Parser.Table.State)pred.state().gotoSetNonTerminals.get(reduction);
+            if (state!=null)
+                newNode(f, reduction, pred, state, reduction.numPops()<=0);
+        }
 
         /** add a new node (merging with existing nodes if possible)
          *  @param parent             the parent of the new node
@@ -82,224 +189,56 @@ class GSS {
          *  @param fromEmptyReduction true iff this node is being created as a result of a reduction of length zero (see GRMLR paper)
          *  @param start              the earliest part of the input contributing to this node (used to make merging decisions)
          */
-        public boolean newNode(Node parent, Forest pending, State state, boolean fromEmptyReduction) {
-            Node p = hash.get(state, parent==null?null:parent.phase());
-            if (p != null)  return newNode2(p, parent, pending, state, fromEmptyReduction);
-            else            return newNode3(parent, pending, state, fromEmptyReduction);
-        }
-        public void newNode(Node parent, Forest pending, State state, boolean fromEmptyReduction, Reduction reduction) {
-            int pos = parent==null?0:parent.phase()==null?0:parent.phase().pos;
-            Sequence owner = reduction==null ? null : reduction.position.owner();
-            if (reduction!=null) {
-                if (inhibited.contains(pos, owner)) return;
-                if (owner.needs != null)
-                    for(Sequence s : owner.needs)
-                        if (!performed.contains(pos, s)) {
-                            waiting.add(s, new Waiting(parent, pending, state, fromEmptyReduction, reduction));
-                            return;
-                        }
-                if ((owner.needed != null && owner.needed.size()>0) ||
-                    (owner.hated != null && owner.hated.size()>0) ||
-                    (owner.hates != null && owner.hates.size()>0))
-                    performed.add(pos, owner);
+        private boolean newNode(Forest f, Pos reduction, StateNode pred, State state, boolean fromEmptyReduction) {
+            StateNode p = pred==null ? null : hash.get(state, pred.phase());
+            if (p != null) {
+                p.addPred(f, reduction, pred);
+                return !state.doomed();
             }
-            if (!owner.lame)
-                newNode(parent, pending, state, fromEmptyReduction);
-            if (reduction!=null) inhibit(reduction, parent==null?0:parent.phase().pos);
-            if (reduction != null) {
-                boolean redo = true;
-                while(redo) {
-                    redo = false;
-                    for(Waiting w : waiting.getAll(owner)) {
-                        if (w.parent==parent || (parent!=null&&w.parent!=null&&w.parent.phase()==parent.phase())) {
-                            waiting.remove(owner, w);
-                            w.perform();
-                            redo = true;
-                            break;
-                        }
-                    }
-                }
-            }
-        }
-        private boolean newNode2(Node p, Node parent, Forest pending, State state, boolean fromEmptyReduction) {
-            p.holder.merge(pending);
-            if (p.parents().contains(parent)) return true;
-            p.parents().add(parent, true);
-            if (p!=parent && !fromEmptyReduction && reducing) p.queueReductions(parent);
-            return true;
-        }
-        private boolean newNode3(Node parent, Forest pending, State state, boolean fromEmptyReduction) {
             do {
                 if (token != null && state.canShift(token)) break;
                 if (state.isAccepting()) break;
                 if (token==null) break;
                 if (!state.canReduce(token)) return false;
-                //if (count > 1) break;
-                //if (r.numPop == 0) break;
-                //r.reduce(pending, parent, null, Phase.this, null);
-                //return;
             } while(false);
-
-            Node n = new Node(parent, pending, state);  // ALLOC
-            if (reducing) {
-                n.queueEmptyReductions();
-                if (!fromEmptyReduction) n.queueReductions(parent);
-            }
-            return true;
+            StateNode n = new StateNode(Phase.this, f, reduction, pred, state, fromEmptyReduction);  // ALLOC
+            /** FIXME: this null-result can be used to notice bogus/dead states */
+            for(Object s : state.conjunctStates)
+                newNode(null, null, n, (State)s, fromEmptyReduction);
+            return !n.state().doomed();
         }
 
-        public void uninhibit(int p, Sequence s) {
-            if (s.hated!=null)
-                for(Sequence s2 : s.hated)
-                    inhibited.remove(p, s2);
-        }
-
-        public void inhibit(Reduction r, int p) {
-            if (r.position.owner().hated == null) return;
-            // remember that dead states are still allowed to shift -- just not allowed to reduce
-            boolean reset = false;
-            for(Sequence seq : r.position.owner().hated) {
-                if (performed.contains(p,seq)) {
-                    uninhibit(p, seq);
-                    //System.out.println("\nresetting due to " + r.position.owner() + " killing " + seq);
-                    //inhibited.clear();
-                    inhibited.add(p, seq);
-                    //inhibited = new HashMapBag<Integer,Sequence>();
-                    reset = true;
-                    resets++;
-                    throw new Reset();
-                }
-                inhibited.add(p, seq);
-            }
-        }
-        
-        /** perform all reduction operations */
-        public void reduce() {
-            try {
-                reducing = true;
-                if (reducing_list==null || reducing_list.length < hash.size())
-                    reducing_list = new Phase.Node[hash.size() * 4];
-                hash.toArray(reducing_list);
-                int num = hash.size();
-                for(int i=0; i<num; i++) {
-                    Node n = reducing_list[i];
-                    n.queueEmptyReductions();
-                    // INVARIANT: we never "see" a node until its parent-set is complete, modulo merges
-                }
-                for(int i=0; i<num; i++) {
-                    Node n = reducing_list[i];
-                    reducing_list[i] = null;
-                    n.queueReductions();
-                }
-            } catch (Reset r) {
-                reset();
-                reduce();
-            }
-        }
-
-        class Reset extends RuntimeException { }
-
-        public void invoke(State st, Forest result, Node n) {
-            good |= next.newNode(n, result, st, false);
-        }
-
-        /** perform all shift operations, adding promoted nodes to <tt>next</tt> */
-        public void shift(Phase next, Forest result) throws ParseFailed {
-            // this massively improves GC performance
-            if (prev!=null) prev.hash = null;
-            this.next = next;
-            closed = true;
-            Forest res = null;
-            boolean ok = false;
-            for(Phase.Node n : hash.values()) {
-                if (token == null && n.state.isAccepting()) {
-                    if (finalResult==null) finalResult = new Forest.Ref();
-                    finalResult.merge(n.holder);
-                }
-                if (token == null) continue;
-                n.state.invokeShifts(token, this, result, n);
-            }
-
-            if (!good && token!=null)
-                throw new ParseFailed(ParseFailed.error(ANSI.red("unexpected character")+" "+ANSI.purple(token)+" encountered at "+ANSI.green(getLocation())+"\n", token, hash.values()),
-                                        getLocation());
-            if (token==null && finalResult==null)
-                throw new ParseFailed(ParseFailed.error(ANSI.red("unexpected end of file\n"), token, hash.values()),
-                                        getLocation());
+        public int toInt() { return pos+1; }
+        public int size() { return hash==null ? 0 : hash.size(); }
+        public int pos() { return pos; }
+        public Tok getToken() { return token; }
+        public Iterator<StateNode> iterator() { return hash.iterator(); }
+        public GSS getGSS() { return GSS.this; }
+
+        // GraphViz //////////////////////////////////////////////////////////////////////////////
+
+        public GraphViz.StateNode toGraphViz(GraphViz gv) {
+            if (gv.hasNode(this)) return gv.createNode(this);
+            GraphViz.Group g = gv.createGroup(this);
+            g.label = "Phase " + pos;
+            g.color = "gray";
+            g.cluster = true;
+            return g;
         }
-
-
-        public class Waiting {
-            Node parent;
-            Forest pending;
-            State state;
-            boolean fromEmptyReduction;
-            Reduction reduction;
-            public Waiting(Node parent, Forest pending, State state, boolean fromEmptyReduction, Reduction reduction) {
-                waits++;
-                this.parent = parent;
-                this.pending = pending;
-                this.state = state;
-                this.fromEmptyReduction = fromEmptyReduction;
-                this.reduction = reduction;
-            }
-            public void perform() {
-                //System.out.println("performing: " + reduction.position);
-                newNode(parent, pending, state, fromEmptyReduction, reduction);
-            }
+        public boolean isTransparent() { return false; }
+        public boolean isHidden() { return false; }
+
+        public void dumpGraphViz(String filename) throws IOException {
+            FileOutputStream fos = new FileOutputStream(filename);
+            PrintWriter p = new PrintWriter(new OutputStreamWriter(fos));
+            GraphViz gv = new GraphViz();
+            for(Object n : this)
+                ((StateNode)n).toGraphViz(gv);
+            gv.dump(p);
+            p.flush();
+            p.close();
         }
-       
-        // Node /////////////////////////////////////////////////////////////////////////////////
 
-        /** a node in the GSS */
-        public final class Node extends FastSet<Node> implements Invokable<Reduction, Node, Node> {
-
-            private Forest.Ref holder = null;
-            private boolean allqueued = false;
-
-            /** what state this node is in */
-            public final State state;
-
-            /** which Phase this Node belongs to (node that Node is also a non-static inner class of Phase) */
-            public  Phase phase() { return Phase.this; }
-            public  Forest.Ref holder() { return holder==null ? (holder = new Forest.Ref()) : holder; }
-            public  Forest pending() { return Phase.this.closed ? holder().resolve() : holder; }
-            public  FastSet<Node> parents() { return this; }
-
-            public void queueReductions() {
-                if (allqueued) return;
-                allqueued = true;
-                state.invokeReductions(token, this, this, null);
-            }
-
-            public void queueReductions(Node n2) {
-                if (!allqueued) { queueReductions(); return; }
-                state.invokeReductions(token, this, this, n2);
-            }
-
-            public final void invoke(Reduction r, Node n, Node n2) {
-                if (n==null) {
-                    if (r.position.pos==0) r.reduce(this);
-                } else if (r.position.pos==0) return;
-                else if (n2==null) r.reduce(n);
-                else          r.reduce(n, n2);
-            }
-            public void queueEmptyReductions() { state.invokeReductions(token, this, null, null); }
-
-            public boolean dead = false;
-            public boolean redo = false;
-            private Node(Node parent, Forest pending, State state) {
-                this.state = state;
-                this.holder().merge(pending);
-                Phase start = parent==null ? null : parent.phase();
-                if (parent != null) parents().add(parent, true);
-                if (Phase.this.hash.get(state, start) != null) throw new Error("severe problem!");
-                Phase.this.hash.put(state, start, this);
-            }
-        }
-
-        public int toInt() { return pos+1; }
-        public int size() { return hash==null ? 0 : hash.size(); }
     }
 
 }