X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FGSS.java;h=1432402f0ac79b656a71f908bff6bab963d6dcaa;hb=cd979dfc5968a185c12d6eedc2aa688ef4b0f8b8;hp=1adb8e445ee2dfb192f5a242b0a619bac940383e;hpb=526da96dd06e152d194ec92c9ef9df6085a1251b;p=sbp.git

diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java
index 1adb8e4..1432402 100644
--- a/src/edu/berkeley/sbp/GSS.java
+++ b/src/edu/berkeley/sbp/GSS.java
@@ -17,42 +17,32 @@ class GSS {
     public int resets = 0;
     public int waits = 0;
 
-    HashMapBag<Integer,Sequence> inhibited = new HashMapBag<Integer,Sequence>();
-    HashMapBag<Integer,Sequence> assumed = new HashMapBag<Integer,Sequence>();
+    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>();
-    HashSet<Phase.Waiting> tail = new     HashSet<Phase.Waiting>();
+    HashMapBag<Integer,Sequence>       performed = new HashMapBag<Integer,Sequence>();
     
+    /** FIXME */
+    public  Forest.Ref finalResult;
+
     /** 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> {
+    public class Phase implements Invokable<State, Forest, GSS.Phase.Node>, IntegerMappable {
 
         /** the token immediately after this phase */
-        public  final Token token;
-
-        boolean reducing;
+        final Token token;
 
-        /** currently this is necessary only for the code() hack -- it doesn't actually correspond to the input */
         private final int pos;
 
-        /** FIXME */
-        public  Forest.Ref finalResult;
-
-        /** all nodes, keyed by the value returned by code() */
-        /*private*/ HashMap<Long,Phase.Node> hash;  /* ALLOC */
-
-        /** the number of nodes in this phase */
-        private int numNodes;
-
-        boolean closed;
-
+        boolean reducing;
+        private IntPairMap<Phase.Node> hash;  /* ALLOC */
+        private boolean closed;
         private boolean good;
         private Phase next = null;
-
+        private Phase prev;
         private Token.Location location;
         public final Parser parser;
 
         private Forest forest;
-        Phase prev;
+
         public Phase(Phase prev, Parser parser, Phase previous, Token token, Token.Location location, Forest forest) {
             this.prev = prev;
             this.forest = forest;
@@ -61,100 +51,25 @@ class GSS {
             this.token = token;
             this.location = location;
             inhibited.clear();
-            assumed.clear();
             reset();
         }
 
         public void reset() {
-            tail.clear();
             waiting.clear();
             performed.clear();
-            hash = new HashMap<Long,Phase.Node>();
+            hash = new IntPairMap<Phase.Node>();
             good = false;
             closed = false;
-            numNodes = 0;
             reducing = false;
             finalResult = null;
             if (prev != null) prev.shift(this, forest);
         }
 
-        public void complain(Node n, HashMap<String,HashSet<String>> errors, boolean force) {
-            if (n.touched) return;
-            n.touched = true;
-            for(Position p : n.state) {
-                //if (!p.isLast()) { 
-                if (((p.isFirst() || p.isLast()) && !force) || p.owner().name==null) {
-                    for(Node n2 : n.parents())
-                        complain(n2, errors, force | p.isFirst());
-                } else {
-                    String seqname = p.owner().name;
-                    HashSet<String> hs = errors.get(seqname);
-                    if (hs==null) errors.put(seqname, hs = new HashSet<String>());
-                    hs.add(p.element()+"");
-                    //String s = "  while parsing " + seqname + ": expected a " + p.element();
-                        //"\n";
-                    /*
-                    s +=       "      parsed: ";
-                    for(Position p2 = p.owner().firstp(); p2 != null && p2 != p && !p2.isLast(); p2 = p2.next()) s += (p2.element() + " ");
-                    s += "\n";
-                    s +=       "    expected: ";
-                    for(Position p2 = p; p2 != null && !p2.isLast(); p2 = p2.next()) s += (p2.element() + " ");
-                    */
-                    //s += "\n";
-                    //errors.add(s);
-                }
-            }
-        }
-
-        public String black(Object o) { return "\033[30m"+o+"\033[0m"; }
-        public String red(Object o) { return "\033[31m"+o+"\033[0m"; }
-        public String green(Object o) { return "\033[32m"+o+"\033[0m"; }
-        public String yellow(Object o) { return "\033[33m"+o+"\033[0m"; }
-        public String blue(Object o) { return "\033[34m"+o+"\033[0m"; }
-        public String purple(Object o) { return "\033[35m"+o+"\033[0m"; }
-        public String cyan(Object o) { return "\033[36m"+o+"\033[0m"; }
-        public String el(Object e) {
-            String s = e.toString();
-            if (s.length()==0 || s.charAt(0)!='\"' || s.charAt(s.length()-1)!='\"') return yellow(s);
-            s = s.substring(1);
-            s = s.substring(0, s.length()-1);
-            StringBuffer ret = new StringBuffer();
-            for(int i=0; i<s.length(); i++) {
-                if (s.charAt(i)=='\\' && i<s.length()-1) ret.append(s.charAt(++i));
-                else ret.append(s);
-            }
-            return purple(ret.toString());
-        }
-        public String error(String message) {
-            String lookAhead = token==null ? "<EOF>" : token.toString();
-            StringBuffer ret = new StringBuffer();
-            ret.append("\n  ");
-            ret.append(message);
-            HashMap<String,HashSet<String>> errors = new HashMap<String,HashSet<String>>();
-            for(Node n : hash.values()) complain(n, errors, false);
-            for(String s : errors.keySet()) {
-                ret.append("    while parsing " + yellow(s));
-                HashSet<String> hs = errors.get(s);
-                if (hs.size()==1) ret.append(" expected " + yellow(el(hs.iterator().next())) + "\n");
-                else {
-                    ret.append(" expected ");
-                    boolean first = true;
-                    for(String s2 : hs) {
-                        if (!first) ret.append(" or ");
-                        first = false;
-                        ret.append(yellow(el(s2)));
-                    }
-                    ret.append("\n");
-                }
-            }
-            return ret.toString();
-        }
-        
-        public boolean isDone() throws Parser.Failed {
+      
+        public boolean isDone() throws ParseFailed {
             if (token != null) return false;
             if (token==null && finalResult==null)
-                throw new Parser.Failed(error(red("unexpected end of file\n")),
-                                        getLocation());
+                throw new ParseFailed(ParseFailed.error(ANSI.red("unexpected end of file\n"), token, hash.values()), getLocation());
             return true;
         }
 
@@ -168,7 +83,7 @@ class GSS {
          *  @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(code(state, parent==null?null:parent.phase()));
+            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);
         }
@@ -177,12 +92,6 @@ class GSS {
             Sequence owner = reduction==null ? null : reduction.position.owner();
             if (reduction!=null) {
                 if (inhibited.contains(pos, owner)) return;
-                /*
-                if (assumed.contains(pos, owner)) {
-                    tail.add(new Waiting(parent, pending, state, fromEmptyReduction, reduction));
-                    return;
-                }
-                */
                 if (owner.needs != null)
                     for(Sequence s : owner.needs)
                         if (!performed.contains(pos, s)) {
@@ -216,7 +125,7 @@ class GSS {
             p.holder.merge(pending);
             if (p.parents().contains(parent)) return true;
             p.parents().add(parent, true);
-            if (p!=parent && !fromEmptyReduction) p.queueReductions(parent);
+            if (p!=parent && !fromEmptyReduction && reducing) p.performReductions(parent);
             return true;
         }
         private boolean newNode3(Node parent, Forest pending, State state, boolean fromEmptyReduction) {
@@ -224,16 +133,18 @@ class GSS {
                 if (token != null && state.canShift(token)) break;
                 if (state.isAccepting()) break;
                 if (token==null) break;
-                //if (!state.canReduce(token)) return false;
+                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);
+            Node n = new Node(parent, pending, state);  // ALLOC
+            if (reducing) {
+                n.performEmptyReductions();
+                if (!fromEmptyReduction) n.performReductions(parent);
+            }
             return true;
         }
 
@@ -253,7 +164,6 @@ class GSS {
                     //System.out.println("\nresetting due to " + r.position.owner() + " killing " + seq);
                     //inhibited.clear();
                     inhibited.add(p, seq);
-                    //assumed = inhibited;
                     //inhibited = new HashMapBag<Integer,Sequence>();
                     reset = true;
                     resets++;
@@ -269,21 +179,18 @@ class GSS {
                 reducing = true;
                 if (reducing_list==null || reducing_list.length < hash.size())
                     reducing_list = new Phase.Node[hash.size() * 4];
-                Collection<Node> hv = hash.values();
-                hv.toArray(reducing_list);
-                int num = hv.size();
+                hash.toArray(reducing_list);
+                int num = hash.size();
                 for(int i=0; i<num; i++) {
                     Node n = reducing_list[i];
-                    n.queueEmptyReductions();
+                    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.queueReductions();
+                    n.performReductions();
                 }
-                //for(Waiting w : tail)
-                //w.perform();
             } catch (Reset r) {
                 reset();
                 reduce();
@@ -297,14 +204,14 @@ class GSS {
         }
 
         /** perform all shift operations, adding promoted nodes to <tt>next</tt> */
-        public void shift(Phase next, Forest result) throws Parser.Failed {
+        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 (n.holder().empty() && pos>0) continue;
                 if (token == null && n.state.isAccepting()) {
                     if (finalResult==null) finalResult = new Forest.Ref();
                     finalResult.merge(n.holder);
@@ -314,14 +221,11 @@ class GSS {
             }
 
             if (!good && token!=null)
-                throw new Parser.Failed(error(red("unexpected character")+" "+purple(token)+" encountered at "+green(getLocation())+"\n"),
+                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 Parser.Failed(error(red("unexpected end of file\n")),
+                throw new ParseFailed(ParseFailed.error(ANSI.red("unexpected end of file\n"), token, hash.values()),
                                         getLocation());
-
-            // this massively improves GC performance
-            //hash = null;
         }
 
 
@@ -345,12 +249,11 @@ class GSS {
             }
         }
        
-        // GSS Nodes //////////////////////////////////////////////////////////////////////////////
+        // Node /////////////////////////////////////////////////////////////////////////////////
 
         /** 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;
 
@@ -358,66 +261,84 @@ class GSS {
             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  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;
+            public void performReductions() {
                 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 void performReductions(Node n2) {
+                if (!allqueued) performReductions();
+                else            state.invokeReductions(token, this, this, n2);
             }
 
             public final void invoke(Reduction r, Node n, Node n2) {
-                if (n==null) {
-                    if (r.numPop==0) r.reduce(this);
-                    return;
+                if (n==null || n2==null || r.position.pos==0) {
+                    if (r.position.pos==0) {
+                        if (n==null) n = this;
+                        else return;
+                    }
+                    if (n==null) return;
+                    Forest[] holder = new Forest[r.position.pos];
+                    if (r.position.pos==0) n.finish(r, r.zero(), n.phase(), holder);
+                    else                   n.reduce(r, r.position.pos-1, n.phase(), holder);
+                } else {
+                    Forest[] holder = new Forest[r.position.pos];
+                    if (r.position.pos<=0) throw new Error("called wrong form of reduce()");
+                    int pos = r.position.pos-1;
+                    Forest old = holder[pos];
+                    holder[pos] = n.pending();
+                    if (pos==0) {
+                        System.arraycopy(holder, 0, r.position.holder, 0, holder.length);
+                        Forest rex = r.position.rewrite(n.phase().getLocation());
+                        n2.finish(r, rex, n.phase(), holder);
+                    } else {
+                        n2.reduce(r, pos-1, n.phase(), holder);
+                    }
+                    holder[pos] = old;
+                }
+            }
+
+            public void reduce(Reduction r, int pos, GSS.Phase target, Forest[] holder) {
+                Forest old = holder[pos];
+                holder[pos] = this.pending();
+                if (pos==0) {
+                    System.arraycopy(holder, 0, r.position.holder, 0, holder.length);
+                    for(int i=0; i<r.position.pos; i++) if (r.position.holder[i]==null) throw new Error("realbad");
+                    Forest rex = r.position.rewrite(target.getLocation());
+                    for(GSS.Phase.Node child : this.parents()) child.finish(r, rex, target, holder);
+                } else {
+                    for(GSS.Phase.Node child : this.parents()) child.reduce(r, pos-1, target, holder);
                 }
-                if (r.numPop==0) return;
-                if (n2==null) r.reduce(n);
-                else          r.reduce(n, n2);
+                holder[pos] = old;
             }
-            public void queueEmptyReductions() {
-                if (!reducing) return;
-                state.invokeReductions(token, this, null, null);
+
+            public void finish(Reduction r, Forest result, GSS.Phase target, Forest[] holder) {
+                State state0 = state.gotoSetNonTerminals.get(r.position.owner());
+                if (result==null) throw new Error();
+                if (state0!=null)
+                    target.newNode(this, result, state0, r.position.pos<=0, r);
             }
 
-            private boolean fe;
-            public boolean dead = false;
-            public boolean redo = false;
-            private Node(Node parent, Forest pending, State state, boolean fe) {
-                this.fe = fe;
+            public void performEmptyReductions() { state.invokeReductions(token, this, null, null); }
+
+            private Node(Node parent, Forest pending, State state) {
                 this.state = state;
                 this.holder().merge(pending);
-                //if (holder().empty()) throw new Error(holder()+"");
                 Phase start = parent==null ? null : parent.phase();
                 if (parent != null) parents().add(parent, true);
-                if (Phase.this.hash.get(code(state, start)) != null) throw new Error("severe problem!");
-                Phase.this.hash.put(code(state, start), this);
-                Phase.this.numNodes++;
+                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(); }
     }
 
-    /** helper method */
-    private static boolean equal(Object a, Object b) {
-        if (a==null && b==null) return true;
-        if (a==null || b==null) return false;
-        return a.equals(b);
-    }
-
-    /** this is something of a hack right now */
-    private static long code(State state, Phase start) {
-        return (((long)state.idx) << 32) | (start==null ? 0 : (start.pos+1));
-    }
 }