X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FGSS.java;h=f222fe568d8e4914540399674279d6e1bd1ac144;hp=80fbd5c4655f28e7e0e2aad060b02975fe09ddca;hb=fc8cad4de7decd07e23f26ccfadb5e6d1ce291d5;hpb=e5cfb136bf7fd1352eff1bd87a458aa4ff748537

diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java
index 80fbd5c..f222fe5 100644
--- a/src/edu/berkeley/sbp/GSS.java
+++ b/src/edu/berkeley/sbp/GSS.java
@@ -1,3 +1,5 @@
+// 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.*;
@@ -10,83 +12,107 @@ import java.lang.reflect.*;
 /** implements Tomita's Graph Structured Stack */
 class GSS {
 
-    public static int count = 0;
-    
-    public GSS() { }
-
-    private Phase.Node[] reducing_list = null;
-    public int resets = 0;
-    public int waits = 0;
+    Input input;
+    public GSS(Input input) { this.input = input; }
+    public Input getInput() { return input; }
 
-    HashMapBag<Sequence,Phase.Waiting> waiting         = new HashMapBag<Sequence,Phase.Waiting>();
+    // FIXME: right now, these are the performance bottleneck
     HashMapBag<Integer,Sequence>       performed       = new HashMapBag<Integer,Sequence>();
-    HashMapBag<Integer,Sequence>       lastperformed   = new HashMapBag<Integer,Sequence>();
-    HashMapBag<Integer,Sequence>       expected        = new HashMapBag<Integer,Sequence>();
-    
+
     /** FIXME */
-    public  Forest.Ref finalResult;
+    Forest.Many finalResult;
 
     /** corresponds to a positions <i>between tokens</i> the input stream; same as Tomita's U_i's */
-    class Phase<Tok> implements Invokable<State, Forest, Phase<Tok>.Node>, IntegerMappable, GraphViz.ToGraphViz, Iterable<Phase.Node> {
+    class Phase<Tok> implements Invokable<State, Result, Object>, IntegerMappable, GraphViz.ToGraphViz, Iterable<Node> {
 
-        public Iterator<Phase.Node> iterator() { return hash.iterator(); }
-        public void invoke(State st, Forest result, Node n) {
-            good |= next.newNode(n, result, st, false);
+        public PriorityQueue<Reduction> reductionQueue = new PriorityQueue<Reduction>();
+
+        public void invoke(State st, Result result, Object o) {
+            //shifts++;
+            good |= next.newNode(result, st, false);
         }
 
         /** the token immediately after this phase */
         final Tok token;
+        final int pos;
 
-        private final int pos;
-
-        boolean reducing;
-        private IntPairMap<Phase.Node> hash;  /* ALLOC */
-        private IntPairMap<Forest> singularReductions;  /* ALLOC */
-        private boolean closed;
+        public IntPairMap<Node> hash;  /* ALLOC */
         private boolean good;
         private Phase next = null;
         private Phase prev;
         private Input.Location location;
-        public final Parser parser;
-
+        private Input.Location nextLocation;
+        private Input.Location prevLocation;
+        
         private Forest forest;
 
-        public Phase(Phase prev, Parser parser, Phase previous, Tok token, Input.Location location, Forest forest) throws ParseFailed {
+        public Phase(Phase prev, Phase previous, Tok token, Input.Location location,
+                     Input.Location nextLocation, Forest forest) throws ParseFailed {
+            this.prevLocation = prev==null ? location : prev.getLocation();
             this.prev = prev;
             this.forest = forest;
-            this.parser = parser;
             this.pos = previous==null ? 0 : previous.pos+1;
             this.token = token;
             this.location = location;
+            this.nextLocation = nextLocation;
             performed.clear();
-            reset();
-        }
-
-        public void reset() throws ParseFailed {
-            waiting.clear();
-            expected.clear();
-            lastperformed.clear();
-            lastperformed.addAll(performed);
-            performed.clear();
-            hash = new IntPairMap<Phase.Node>();
-            singularReductions = new IntPairMap<Forest>();
-            reset = false;
+            hash = new IntPairMap<Node>();
             good = false;
-            closed = false;
-            reducing = false;
             finalResult = null;
             if (prev != null) prev.shift(this, forest);
         }
 
-      
+        public boolean isFrontier() { return next==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);
             return true;
         }
 
+        public Input.Location getPrevLocation() { return prevLocation; }
         public Input.Location getLocation() { return location; }
+        public Input.Region   getRegion() { return getPrevLocation().createRegion(getLocation()); }
+        public Input.Location getNextLocation() { return nextLocation; }
+
+        /** 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;
+            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), null);
+            }
+            if (!good && token!=null) ParseFailed.error("unexpected character", this);
+            if (token==null && finalResult==null) ParseFailed.error("unexpected end of file", this);
+        }
+
+        /** perform all reduction operations */
+        public void reduce() throws ParseFailed {
+            while(!reductionQueue.isEmpty())
+                reductionQueue.poll().perform();
+        }
+
+        public void newNodeFromReduction(Result result, State state, boolean fromEmptyReduction, 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, fromEmptyReduction);
+        }
 
         /** add a new node (merging with existing nodes if possible)
          *  @param parent             the parent of the new node
@@ -95,345 +121,25 @@ 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, Position reduction) {
-            int pos = parent==null?0:parent.phase()==null?0:parent.phase().pos;
-            Sequence owner = reduction==null ? null : reduction.owner();
-            if (reduction!=null) {
-                if (owner.hates!=null) {
-                    for (Sequence s : performed.getAll(pos))
-                        if (owner.hates.contains(s))
-                            return;
-                    for (Sequence s : lastperformed.getAll(pos))
-                        if (owner.hates.contains(s)) {
-                            //System.out.println("now expecting ["+pos+"] => " + s);
-                            expected.add(pos, s);
-                            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 (!performed.contains(pos, owner)) {
-                    performed.add(pos, owner);
-                    if (owner.hated != null)
-                        for(Sequence seq : owner.hated)
-                            if (performed.contains(pos, seq)) {
-                                performed.remove(pos, seq);
-                                reset = true;
-                            }
-                }
-            }
-            if (!owner.lame)
-                newNode(parent, pending, state, fromEmptyReduction);
-            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) {
-            //if (p.parents().contains(parent)) return true;
-            p.merge(parent, pending);
-            p.parents().add(parent, true);
-            if (p!=parent && !fromEmptyReduction && reducing) p.performReductions(parent);
-            return true;
-        }
-        private boolean newNode3(Node parent, Forest pending, State state, boolean fromEmptyReduction) {
+        public boolean newNode(Result result, State state, boolean fromEmptyReduction) {
+            Node p = hash.get(state, result.phase());
+            if (p != null) { p.merge(result); return true; }
             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.performEmptyReductions();
-                if (!fromEmptyReduction) n.performReductions(parent);
-            }
+            new Node(Phase.this, result, state, fromEmptyReduction);  // ALLOC
             return true;
         }
 
-        /** perform all reduction operations */
-        public void reduce() throws ParseFailed {
-            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.performEmptyReductions();
-                    // 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.performReductions();
-                }
-                if (reset) {
-                    reset = false;
-                    resets++;
-                    throw new Reset();
-                }                
-                for(int i : expected)
-                    for(Sequence s : expected.getAll(i))
-                        if (!performed.contains(i, s)) {
-                            //System.out.println("resetting due to pos="+i+": " + s + " " + System.identityHashCode(s));
-                            resets++;
-                            throw new Reset();
-                        }
-            } catch (Reset r) {
-                reset();
-                reduce();
-            }
-            count = 0;
-        }
-
-        private boolean reset = false;
-        class Reset extends RuntimeException { }
-
-        /** 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 && parser.helpgc) {
-                prev.hash = null;
-                prev.singularReductions = 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();
-                    for(Object f : n.results())
-                        finalResult.merge((Forest)f);
-                }
-                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(StringUtil.escapify(token+"", "\\\'\r\n"))+
-                                                        "\' 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());
-        }
-
-
-        class Waiting {
-            Node parent;
-            Forest pending;
-            State state;
-            boolean fromEmptyReduction;
-            Position reduction;
-            public Waiting(Node parent, Forest pending, State state, boolean fromEmptyReduction, Position 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);
-            }
-        }
-       
-        // Node /////////////////////////////////////////////////////////////////////////////////
-
-        /** a node in the GSS */
-        final class Node implements Invokable<Position, Node, Node>, IntegerMappable, GraphViz.ToGraphViz {
-            public FastSet<Node> set = new FastSet<Node>();
-
-        public GraphViz.Node toGraphViz(GraphViz gv) {
-            if (gv.hasNode(this)) return gv.createNode(this);
-            GraphViz.Node n = gv.createNode(this);
-            n.label = ""+state.toStringx();
-            n.shape = "rectangle";
-            n.fill = "green";
-            //GraphViz.Node f = pending().toGraphViz(gv);
-            //n.add(f);
-            for(Forest result : results()) n.edge(result, "");
-            for(Node parent : parents()) n.edge(parent, "");
-            ((GraphViz.Group)phase().toGraphViz(gv)).add(n);
-            return n;
-        }
-        public boolean isTransparent() { return false; }
-        public boolean isHidden() { return false; }
-
-
-            //private Forest.Ref holder = new Forest.Ref();
-            private boolean allqueued = false;
-
-            /** what state this node is in */
-            public final Parser.Table<Tok>.State<Tok> 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; }
-            //private Forest pending() { return !Phase.this.closed ? holder : holder.resolve(); }
-            private HashMap<Node,Forest> resultMap = new HashMap<Node,Forest>();
-            public void merge(Node parent, Forest result) {
-                //holder.merge(result);
-                Forest.Ref f = (Forest.Ref)resultMap.get(parent);
-                if (f==null) { f = new Forest.Ref(); resultMap.put(parent, f); }
-                f.merge(result);
-                set.add(parent, true);
-            }
-            //public Iterable<Node> childrenFor(Forest result) { return resultMap.getAll(result); }
-            public Iterable<Forest> results() { return resultMap.values(); }
-            private Forest pending(Node n) {
-                //return !Phase.this.closed ? holder : holder.resolve();
-                /*
-                for(Forest f : resultMap)
-                    if (resultMap.contains(f, n))
-                        return f;
-                return null;
-                */
-                return resultMap.get(n);
-            }
-            public  FastSet<Node> parents() { return set; }
-
-            public void performReductions() {
-                if (allqueued) return;
-                allqueued = true;
-                state.invokeReductions(token, this, this, null);
-            }
-
-            public void performReductions(Node n2) {
-                if (!allqueued) performReductions();
-                else            state.invokeReductions(token, this, this, n2);
-            }
-
-            public void performEmptyReductions() { state.invokeReductions(token, this, null, null); }
-            public final void invoke(Position r, Node n, Node n2) {
-                //if (r.owner().lame) return;
-                if (n==null || n2==null || r.pos==0) {
-                    if (r.pos==0) {
-                        if (n==null) n = this;
-                        else return;
-                    }
-                    if (n==null) return;
-                    Forest[] holder = new Forest[r.pos];
-                    if (r.pos==0) n.finish(r, r.zero(), n.phase(), holder);
-                    else          n.reduce(r, r.pos-1,  n.phase(), holder, null, n.pending(n));
-                } else {
-                    Forest[] holder = new Forest[r.pos];
-                    if (r.pos<=0) throw new Error("called wrong form of reduce()");
-                    int pos = r.pos-1;
-                    n.reduce(r, pos, n.phase(), holder, n2, n.pending(n));
-                }
-            }
-
-            /*
-            public void reduce(Position r, int pos, Phase target, Forest[] holder) {
-                reduce(r, pos, target, holder, null); }
-            public void reduce(Position r, int pos, Phase target, Forest[] holder, Node only) {
-                reduce(r, pos, target, holder, only, this.pending());
-            }
-            */
-            public void reduce(Position r, int pos, Phase target, Forest[] holder, Node only, Forest pending) {
-                Forest old = holder[pos];
-                holder[pos] = pending;
-                if (pos==0) {
-
-                    // FIXME: I'm unsure about this -- basically we want to deal with the case where
-                    //        there are two nodes, each of whose Ref points to the same Forest instance.
-                    //        Some node in the next phase has both of these as parents.  This might happen
-                    //        since the same reduction can appear in more than one state.
-
-                    if (only != null)  {
-                        holder[pos] = pending(only);
-                        System.arraycopy(holder, 0, r.holder, 0, holder.length);
-                        for(int i=0; i<r.pos; i++) if (r.holder[i]==null) throw new Error("realbad");
-                        Forest rex = null;
-                        if (r.pos==1)  rex = singularReductions.get(pending, r);
-                        if (rex==null) {
-                            rex = r.rewrite(phase().getLocation());
-                            if (r.pos==1) singularReductions.put(pending, r, rex);
-                        }
-                        only.finish(r, rex, target, holder);
-                    } else {
-                        for(Forest result : results()) {
-                            pending = holder[pos] = result;
-                            System.arraycopy(holder, 0, r.holder, 0, holder.length);
-                            for(int i=0; i<r.pos; i++) if (r.holder[i]==null) throw new Error("realbad");
-                            Forest rex = null;
-                            if (rex==null && r.pos==1)  rex = singularReductions.get(pending, r);
-                            if (rex==null) {
-                                rex = r.rewrite(phase().getLocation());
-                                if (r.pos==1) singularReductions.put(pending, r, rex);
-                            }
-                            for(Node child : parents()) {
-                                if (pending(child)==result)
-                                    child.finish(r, rex, target, holder);
-                            }
-                        }
-                    }
-                } else {
-                    if (only != null)  {
-                        holder[pos] = pending(only);
-                        only.reduce(r, pos-1, target, holder, null, only.pending(only));
-                    } else {
-                        for(Node child : this.parents()) {
-                            holder[pos] = pending(child);
-                            child.reduce(r, pos-1, target, holder, null, child.pending(child));
-                        }
-                    }
-                }
-                holder[pos] = old;
-            }
-
-            public void finish(Position r, Forest result, Phase<Tok> target, Forest[] holder) {
-                Parser.Table<Tok>.State<Tok> state0 = state.gotoSetNonTerminals.get(r.owner());
-                if (result==null) throw new Error();
-                if (state0!=null)
-                    target.newNode(this, result, state0, r.pos<=0, r);
-            }
-
-            private Node(Node parent, Forest pending, State state) {
-                this.state = state;
-                this.merge(parent, 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 idx; }
-            private final int idx = node_idx++;
-        }
-        private int node_idx = 0;
-
         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 //////////////////////////////////////////////////////////////////////////////
 
@@ -449,4 +155,5 @@ class GSS {
         public boolean isHidden() { return false; }
 
     }
+
 }