X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FGSS.java;h=3c6beacabbf2c2ccd75f2286c75e2ab4d9312124;hp=d2b040d42fa475eae6bba5d4a3d1e32ca5c9790f;hb=5c4157c1118401c4223ff485e9531fc3ba851be2;hpb=ddf7ffb485e6b3dd0fe6b1b39b47a21a1e4b8973

diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java
index d2b040d..3c6beac 100644
--- a/src/edu/berkeley/sbp/GSS.java
+++ b/src/edu/berkeley/sbp/GSS.java
@@ -1,9 +1,10 @@
+// Copyright 2006 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.Parser.Table.*;
 import edu.berkeley.sbp.Sequence.Position;
-import edu.berkeley.sbp.Parser.Table.State;
-import edu.berkeley.sbp.Parser.Table.Reduction;
 import java.io.*;
 import java.util.*;
 import java.lang.reflect.*;
@@ -11,69 +12,169 @@ 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;
+    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, Result>, IntegerMappable, GraphViz.ToGraphViz, Iterable<Node> {
 
-        /** the token immediately after this phase */
-        final Token token;
+        // FIXME: right now, these are the performance bottleneck
+        private HashMapBag<Integer,Sequence>       performed       = new HashMapBag<Integer,Sequence>();
+
+        public Forest.Many finalResult;
+        private PriorityQueue<Reduction> reductionQueue = new PriorityQueue<Reduction>();
+
+        Parser parser() { return parser; }
+        public void addReduction(Reduction r) {
+            //System.out.println("+ " + r);
+            parser.spin();
+            reductionQueue.add(r);
+        }
+        public void invoke(State st, Result result) {
+            parser.spin();
+            good |= next.newNode(result, st, false);
+        }
 
-        private final int pos;
+        /** the token immediately after this phase */
+        final Tok token;
+        final int pos;
 
-        boolean reducing;
-        private IntPairMap<Phase.Node> hash;  /* ALLOC */
-        private boolean closed;
-        private boolean good;
+        public IntPairMap<Node> hash = new IntPairMap<Node>();  /* 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 Input.Location prevLocation;
+        
         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);
+            Result primordealResult = new Result(null, null, null);
+            newNode(primordealResult, startState, true);
+        }
+        public Phase(Phase prev, Forest forest) throws ParseFailed, IOException {
+            this.prevLocation = input.getLocation();
+            this.token = (Tok)input.next();
+            this.location = 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;
+            this.nextLocation = input.getLocation();
             if (prev != null) prev.shift(this, forest);
+            numReductions = 0;
+
+            int minPhasePos = Integer.MAX_VALUE;
+            int maxOrd = -1;
+            Reduction best = null;
+            //System.out.println("==============================================================================");
+            while(!reductionQueue.isEmpty()) {
+                Reduction r = reductionQueue.poll();
+                //System.out.println("- " + r);
+                if (r.parentPhase() != null)
+                    if (r.parentPhase().pos > minPhasePos)
+                        throw new Error();
+                r.perform();
+                if (r.parentPhase() != null) {
+                    if (r.parentPhase().pos < minPhasePos) {
+                        minPhasePos = r.parentPhase().pos;
+                        maxOrd = r.reduction().ord;
+                        best = r;
+                    } else if (r.parentPhase().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));
+                        */
+                        maxOrd = r.reduction().ord;
+                        best = 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 getPrevLocation() { return prevLocation; }
+        public Input.Location getLocation() { return location; }
+        public Input.Region getRegion() { return prevLocation.createRegion(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 result) throws ParseFailed {
+            this.next = next;
+            // this massively improves GC performance
+            if (prev != null) {
+                IntPairMap<Node> h = prev.hash;
+                prev.hash = null;
+                prev.performed = null;
+                for(Node n : h)
+                    n.check();
+            }
+            numOldNodes = hash.size();
+            for(Node n : hash.values()) {
+                if (token == null && n.state().isAccepting()) {
+                    if (finalResult==null) finalResult = new Forest.Many();
+                    for(Result r : n)
+                        finalResult.merge(r.getForest());
+                }
+                if (token == null) continue;
+                n.state().invokeShifts(token, this, new Result(result, n, null));
+            }
+            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(Node n : hash) n.check();
+        }
+
+        void newNodeFromReduction(Result result, State state, Position reduction) {
+            int pos = result.phase().pos;
+            Sequence owner = reduction.owner();
+            for(Sequence s : owner.hates())
+                if (performed.contains(pos, s))
+                    return;
+            for(Sequence s : owner.needs())
+                if (!performed.contains(pos, s))
+                    return;
+            if (owner.needed_or_hated && !performed.contains(pos, owner))
+                performed.add(pos, owner);
+            if (state!=null)
+                newNode(result, state, reduction.pos<=0);
+        }
 
         /** add a new node (merging with existing nodes if possible)
          *  @param parent             the parent of the new node
@@ -82,233 +183,52 @@ 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);
-            }
-            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) p.queueReductions(parent);
-            return true;
-        }
-        private boolean newNode3(Node parent, Forest pending, State state, boolean fromEmptyReduction) {
+        private boolean newNode(Result result, State state, boolean fromEmptyReduction) {
+            Node p = hash.get(state, result.phase());
+            if (p != null) { p.addResult(result); return !state.doomed(); }
             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, fromEmptyReduction);  // ALLOC
-            n.queueEmptyReductions();
-            if (!fromEmptyReduction) n.queueReductions(parent);
-            return true;
+            Node n = new Node(Phase.this, result, state, fromEmptyReduction);  // ALLOC
+            for(Object s : state.conjunctStates)
+                newNode(new Result(null, n, null), (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 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 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<Node> iterator() { return hash.iterator(); }
+        public GSS getGSS() { return GSS.this; }
+
+        // GraphViz //////////////////////////////////////////////////////////////////////////////
+
+        public GraphViz.Node 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;
         }
-       
-        // GSS Nodes //////////////////////////////////////////////////////////////////////////////
-
-        /** a node in the GSS */
-        public final class Node extends FastSet<Node> implements Invokable<Reduction, Node, Node> {
-
-            public boolean touched = false;
-            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 (!reducing) return;
-                if (allqueued) return;
-                allqueued = true;
-                int where = parents().size();
-                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);
-                    return;
-                }
-                if (r.position.pos==0) return;
-                if (n2==null) r.reduce(n);
-                else          r.reduce(n, n2);
-            }
-            public void queueEmptyReductions() {
-                if (!reducing) return;
-                state.invokeReductions(token, this, null, null);
-            }
-
-            private boolean fe;
-            public boolean dead = false;
-            public boolean redo = false;
-            private Node(Node parent, Forest pending, State state, boolean fe) {
-                this.fe = fe;
-                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 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)
+                ((Node)n).toGraphViz(gv);
+            gv.dump(p);
+            p.flush();
+            p.close();
         }
 
-        public int toInt() { return pos+1; }
-        public int size() { return hash==null ? 0 : hash.size(); }
     }
 
 }