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

diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java
index cff543d..f222fe5 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,158 +12,107 @@ 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;
-
-    HashMapBag<Integer,Sequence> inhibited = new HashMapBag<Integer,Sequence>();
-    HashMapBag<Integer,Sequence> assumed = 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>();
-    
-    /** 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 {
-        public int toInt() { return pos+1; }
-
-        /** the token immediately after this phase */
-        public  final Token token;
+    Input input;
+    public GSS(Input input) { this.input = input; }
+    public Input getInput() { return input; }
 
-        boolean reducing;
+    // FIXME: right now, these are the performance bottleneck
+    HashMapBag<Integer,Sequence>       performed       = new HashMapBag<Integer,Sequence>();
 
-        /** currently this is necessary only for the code() hack -- it doesn't actually correspond to the input */
-        private final int pos;
+    /** FIXME */
+    Forest.Many finalResult;
 
-        /** FIXME */
-        public  Forest.Ref 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, Result, Object>, IntegerMappable, GraphViz.ToGraphViz, Iterable<Node> {
 
-        /** all nodes, keyed by the value returned by code() */
-        /*private*/ IntPairMap<Phase.Node> hash;  /* ALLOC */
+        public PriorityQueue<Reduction> reductionQueue = new PriorityQueue<Reduction>();
 
-        /** the number of nodes in this phase */
-        private int numNodes;
+        public void invoke(State st, Result result, Object o) {
+            //shifts++;
+            good |= next.newNode(result, st, false);
+        }
 
-        boolean closed;
+        /** the token immediately after this phase */
+        final Tok token;
+        final int pos;
 
+        public IntPairMap<Node> hash;  /* ALLOC */
         private boolean good;
         private Phase next = null;
-
-        private Token.Location location;
-        public final Parser parser;
-
+        private Phase prev;
+        private Input.Location location;
+        private Input.Location nextLocation;
+        private Input.Location prevLocation;
+        
         private Forest forest;
-        Phase prev;
-        public Phase(Phase prev, Parser parser, Phase previous, Token token, Token.Location location, Forest forest) {
+
+        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;
-            inhibited.clear();
-            assumed.clear();
-            reset();
-        }
-
-        public void reset() {
-            tail.clear();
-            waiting.clear();
+            this.nextLocation = nextLocation;
             performed.clear();
-            hash = new IntPairMap<Phase.Node>();
+            hash = new IntPairMap<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 boolean isFrontier() { return next==null; }
+        public boolean isDone() throws ParseFailed {
+            if (token != null) return false;
+            if (token==null && finalResult==null)
+                ParseFailed.error("unexpected end of file", this);
+            return true;
         }
 
-        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>>();
+        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()) {
-                //System.out.println(n.state);
-                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");
+                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);
             }
-            return ret.toString();
+            if (!good && token!=null) ParseFailed.error("unexpected character", this);
+            if (token==null && finalResult==null) ParseFailed.error("unexpected end of file", this);
         }
-        
-        public boolean isDone() throws Parser.Failed {
-            if (token != null) return false;
-            if (token==null && finalResult==null)
-                throw new Parser.Failed(error(red("unexpected end of file\n")),
-                                        getLocation());
-            return true;
+
+        /** perform all reduction operations */
+        public void reduce() throws ParseFailed {
+            while(!reductionQueue.isEmpty())
+                reductionQueue.poll().perform();
         }
 
-        public Token.Location getLocation() { return location; }
+        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
@@ -171,253 +121,39 @@ 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 (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)) {
-                            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) {
+        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;
+                if (!state.canReduce(token)) return false;
             } while(false);
-
-            Node n = new Node(parent, pending, state, fromEmptyReduction);  // ALLOC
-            n.queueEmptyReductions();
-            if (!fromEmptyReduction) n.queueReductions(parent);
+            new Node(Phase.this, result, state, fromEmptyReduction);  // ALLOC
             return true;
         }
 
-        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);
-                    //assumed = inhibited;
-                    //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();
-                }
-                //for(Waiting w : tail)
-                //w.perform();
-            } catch (Reset r) {
-                reset();
-                reduce();
-            }
-        }
-
-        class Reset extends RuntimeException { }
-
-        public void invoke(State st, Forest result, Node n) {
-            boolean ok = next.newNode(n, result, st, false);
-            if (ok && !good) {
-                good = !st.lame();
-                //if (good) System.out.println(st);
-            }
-        }
-
-        /** perform all shift operations, adding promoted nodes to <tt>next</tt> */
-        public void shift(Phase next, Forest result) throws Parser.Failed {
-            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 Parser.Failed(error(red("unexpected character")+" "+purple(token)+" encountered at "+green(getLocation())+"\n"),
-                                        getLocation());
-            if (token==null && finalResult==null)
-                throw new Parser.Failed(error(red("unexpected end of file\n")),
-                                        getLocation());
-
-            // this massively improves GC performance
-            //hash = null;
-        }
-
-
-        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);
-            }
-        }
-       
-        // 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 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; }
 
-            public final void invoke(Reduction r, Node n, Node n2) {
-                if (n==null) {
-                    if (r.numPop==0) r.reduce(this);
-                    return;
-                }
-                if (r.numPop==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);
-            }
+        // GraphViz //////////////////////////////////////////////////////////////////////////////
 
-            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);
-                Phase.this.numNodes++;
-            }
+        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;
         }
+        public boolean isTransparent() { return false; }
+        public boolean isHidden() { return false; }
 
     }
 
-    /** 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);
-    }
 }