X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FGSS.java;h=2e573486c9e8d3ff80cd13cfabb5d24ad489fed1;hp=3843f57020efe11b1df60b4612e8c818e89ddb91;hb=c53fc2952c7885d727500ce404887d552c5dec5f;hpb=ebb5fe5647046306f415e31e4967b23169c9004e

diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java
index 3843f57..2e57348 100644
--- a/src/edu/berkeley/sbp/GSS.java
+++ b/src/edu/berkeley/sbp/GSS.java
@@ -1,7 +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.*;
+import edu.berkeley.sbp.Sequence.Pos;
+import edu.berkeley.sbp.Sequence.Pos;
 import java.io.*;
 import java.util.*;
 import java.lang.reflect.*;
@@ -9,122 +13,174 @@ import java.lang.reflect.*;
 /** implements Tomita's Graph Structured Stack */
 class GSS {
 
-    public GSS() { }
+    Input input;
+    private Parser parser;
+    public GSS(Input input, Parser parser) { this.input = input; this.parser = parser;}
+    public Input getInput() { return input; }
 
-    private Phase.Node[] reducing_list = null;
+    /*
+    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<Parser.Table.State, Forest, GSS.Phase.Node> {
-
-        /** the token immediately after this phase */
-        public  final Token token;
-
-        boolean reducing = false;
-
-        /** currently this is necessary only for the code() hack -- it doesn't actually correspond to the input */
-        private final int pos;
+    class Phase<Tok> implements Invokable<State, StateNode, Forest>, IntegerMappable, GraphViz.ToGraphViz, Iterable<StateNode> {
 
-        /** FIXME */
-        public  Forest.Ref finalResult = null;
+        // FIXME: right now, these are the performance bottleneck
+        private HashMapBag<Integer,Integer>       performed       = new HashMapBag<Integer,Integer>();
 
-        /** all nodes, keyed by the value returned by code() */
-        /*private*/ HashMap<Long,Phase.Node> hash    = new HashMap<Long,Phase.Node>();  /* ALLOC */
+        public Forest.Many finalResult;
+        private PriorityQueue<Reduction> reductionQueue = new PriorityQueue<Reduction>();
 
-        /** the number of nodes in this phase */
-        private int numNodes = 0;
-
-        boolean closed = false;
-
-        private Token.Location location;
-        public Phase(Phase previous, Token token, Token.Location location) {
-            this.pos = previous==null ? 0 : previous.pos+1;
-            this.token = token;
-            this.location = location;
+        Parser parser() { return parser; }
+        public void addReduction(Reduction r) {
+            //System.out.println("+ " + r);
+            parser.spin();
+            reductionQueue.add(r);
         }
 
-        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 void invoke(State st, StateNode pred, Forest f) {
+            parser.spin();
+            good |= next.newNode(f, null, pred, st, false);
         }
 
-        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());
+        /** 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 Input.Location location;
+        private Input.Location nextLocation;
+        
+        private Forest forest;
+
+        public Phase(State startState) throws ParseFailed, IOException {
+            this(null, null);
+            newNode(null, null, null, startState, true);
         }
-        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)));
+        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.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;
                     }
-                    ret.append("\n");
                 }
+                /*
+                finishedReductions.add(r);
+                */
+                numReductions++;
             }
-            return ret.toString();
+            if (token==null) shift(null, null);
         }
-        
-        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());
+                ParseFailed.error("unexpected end of file", this, null,
+                                  getLocation().createRegion(getLocation()));
             return true;
         }
 
-        private String error = "generic syntax error";
+        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());
+        }
 
-        public Token.Location getLocation() { return location; }
+        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
@@ -133,166 +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, Parser.Table.State state, boolean fromEmptyReduction) {
-            Node p = hash.get(code(state, parent==null?null:parent.phase()));
-            if (p != null)  return newNode2(p, parent, pending, state, fromEmptyReduction);
-            else            return newNode3(parent, pending, state, fromEmptyReduction);
-        }
-        private boolean newNode2(Node p, Node parent, Forest pending, Parser.Table.State state, boolean fromEmptyReduction) {
-            p.holder.merge(pending);
-            if (p.parents().contains(parent)) return true;
-            //if (p.fe && p.phase() != parent.phase()) throw new Error("yep yep");
-            //if (!p.fe && p.phase() == parent.phase()) throw new Error("yep yep2");
-            p.parents().add(parent, true);
-            if (p!=parent && !fromEmptyReduction) p.queueReductions(parent);
-            return true;
-        }
-        private boolean newNode3(Node parent, Forest pending, Parser.Table.State state, boolean fromEmptyReduction) {
+        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.addResult(f, reduction, pred);
+                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;
+                if (!state.canReduce(token)) return false;
             } while(false);
-
-            Node n = new Node(parent, pending, state, fromEmptyReduction);  // ALLOC
-            n.queueEmptyReductions();
-            if (!fromEmptyReduction) n.queueReductions(parent);
-            return true;
-        }
-
-        
-        /** perform all reduction operations */
-        public void reduce() {
-            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();
-            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();
-            }
-        }
-
-        private boolean good = false;
-        public void invoke(Parser.Table.State st, Forest result, Node n) {
-            good |= next.newNode(n, result, st, false);
+            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();
         }
-        private Phase next = null;
-
-        /** perform all shift operations, adding promoted nodes to <tt>next</tt> */
-        public void shift(Phase next, Forest result) throws Parser.Failed {
-            this.next = next;
-            closed = true;
-            Forest res = null;
-            boolean ok = false;
-            for(Phase.Node n : hash.values()) {
-                if (n.holder==null) continue;
-                n.holder.resolve();
-                if (token == null && n.state.isAccepting()) {
-                    if (finalResult==null) finalResult = new Forest.Ref();
-                    finalResult.merge(n.holder);
-                }
-                if (!n.holder.valid()) continue;
-                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 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;
         }
-
-       
-        // GSS Nodes //////////////////////////////////////////////////////////////////////////////
-
-        /** a node in the GSS */
-        public final class Node extends FastSet<Node> implements Invokable<Parser.Table.Reduction, Node, Node> {
-
-            public boolean touched = false;
-            private Forest.Ref holder = null;
-            private boolean allqueued = false;
-
-            /** what state this node is in */
-            public final Parser.Table.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(Parser.Table.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);
-            }
-
-            private boolean fe;
-            private Node(Node parent, Forest pending, Parser.Table.State state, boolean fe) {
-                this.fe = fe;
-                this.state = state;
-                Phase start = parent==null ? null : parent.phase();
-                if (pending != null) this.holder().merge(pending);
-                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 (parent==null) holder().valid = true; // hack to make sure that the "base" node is always considered valid
-            }
+        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();
         }
 
     }
 
-    /** 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(Parser.Table.State state, Phase start) {
-        return (((long)state.idx) << 32) | (start==null ? 0 : (start.pos+1));
-    }
 }