From: adam Date: Wed, 11 Jan 2006 07:45:53 +0000 (-0500) Subject: checkpoint harmony X-Git-Tag: tag_for_25-Mar~396 X-Git-Url: http://git.megacz.com/?p=sbp.git;a=commitdiff_plain;h=aeae43c3255b14e4ba65e0171b87c48bbf953c31 checkpoint harmony darcs-hash:20060111074553-5007d-29d4ba803784845b6ee8969d7c1bbb45d920492e.gz --- diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java index 1432402..becea95 100644 --- a/src/edu/berkeley/sbp/GSS.java +++ b/src/edu/berkeley/sbp/GSS.java @@ -3,7 +3,6 @@ import edu.berkeley.sbp.*; import edu.berkeley.sbp.util.*; 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.*; @@ -87,9 +86,9 @@ class GSS { 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) { + 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.position.owner(); + Sequence owner = reduction==null ? null : reduction.owner(); if (reduction!=null) { if (inhibited.contains(pos, owner)) return; if (owner.needs != null) @@ -154,14 +153,14 @@ class GSS { inhibited.remove(p, s2); } - public void inhibit(Reduction r, int p) { - if (r.position.owner().hated == null) return; + public void inhibit(Position r, int p) { + if (r.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) { + for(Sequence seq : r.owner().hated) { if (performed.contains(p,seq)) { uninhibit(p, seq); - //System.out.println("\nresetting due to " + r.position.owner() + " killing " + seq); + //System.out.println("\nresetting due to " + r.owner() + " killing " + seq); //inhibited.clear(); inhibited.add(p, seq); //inhibited = new HashMapBag(); @@ -234,8 +233,8 @@ class GSS { Forest pending; State state; boolean fromEmptyReduction; - Reduction reduction; - public Waiting(Node parent, Forest pending, State state, boolean fromEmptyReduction, Reduction reduction) { + Position reduction; + public Waiting(Node parent, Forest pending, State state, boolean fromEmptyReduction, Position reduction) { waits++; this.parent = parent; this.pending = pending; @@ -252,7 +251,7 @@ class GSS { // Node ///////////////////////////////////////////////////////////////////////////////// /** a node in the GSS */ - public final class Node extends FastSet implements Invokable { + public final class Node extends FastSet implements Invokable { private Forest.Ref holder = null; private boolean allqueued = false; @@ -277,25 +276,25 @@ class GSS { else state.invokeReductions(token, this, this, n2); } - public final void invoke(Reduction r, Node n, Node n2) { - if (n==null || n2==null || r.position.pos==0) { - if (r.position.pos==0) { + public final void invoke(Position r, Node n, Node n2) { + 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.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); + 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); } 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[] holder = new Forest[r.pos]; + if (r.pos<=0) throw new Error("called wrong form of reduce()"); + int pos = r.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()); + System.arraycopy(holder, 0, r.holder, 0, holder.length); + Forest rex = r.rewrite(n.phase().getLocation()); n2.finish(r, rex, n.phase(), holder); } else { n2.reduce(r, pos-1, n.phase(), holder); @@ -304,13 +303,13 @@ class GSS { } } - public void reduce(Reduction r, int pos, GSS.Phase target, Forest[] holder) { + public void reduce(Position 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 { if (isRightNullable(p)) { Walk.Follow wf = new Walk.Follow(top.empty(), p.owner(), all_elements, cache); - Reduction red = new Reduction(p); - Topology follow = wf.walk(p.owner()); for(Position p2 = p; p2 != null && p2.element() != null; p2 = p2.next()) follow = follow.intersect(new Walk.Follow(top.empty(), p2.element(), all_elements, cache).walk(p2.element())); - state.reductions.put(follow, red); - if (wf.includesEof()) state.eofReductions.add(red); + state.reductions.put(follow, p); + if (wf.includesEof()) state.eofReductions.add(p); } // if the element following this position is an atom, copy the corresponding @@ -129,13 +127,13 @@ public abstract class Parser { public transient HashMap gotoSetNonTerminals = new HashMap(); private transient TopologicalBag gotoSetTerminals = new TopologicalBag(); - private TopologicalBag reductions = new TopologicalBag(); - private HashSet eofReductions = new HashSet(); + private TopologicalBag reductions = new TopologicalBag(); + private HashSet eofReductions = new HashSet(); private TopologicalBag shifts = new TopologicalBag(); private boolean accept = false; private VisitableMap oshifts = null; - private VisitableMap oreductions = null; + private VisitableMap oreductions = null; // Interface Methods ////////////////////////////////////////////////////////////////////////////// @@ -148,8 +146,8 @@ public abstract class Parser { } boolean canReduce(Token t) { return t==null ? eofReductions.size()>0 : oreductions.contains(t); } - void invokeReductions(Token t, Invokable irbc, B b, C c) { - if (t==null) for(Reduction r : eofReductions) irbc.invoke(r, b, c); + void invokeReductions(Token t, Invokable irbc, B b, C c) { + if (t==null) for(Position r : eofReductions) irbc.invoke(r, b, c); else oreductions.invoke(t, irbc, b, c); } @@ -244,35 +242,6 @@ public abstract class Parser { public int compareTo(Table.State s) { return idx==s.idx ? 0 : idx < s.idx ? -1 : 1; } public int toInt() { return idx; } } - - /** - * the information needed to perform a reduction; copied here to - * avoid keeping references to Element objects in a Table - */ - public class Reduction { - // FIXME: cleanup; almost everything in here could go in either Sequence.Position.getRewrite() or else in GSS.Reduct - /*private*/ final Position position; - public int hashCode() { return position.hashCode(); } - public boolean equals(Object o) { - if (o==null) return false; - if (o==this) return true; - if (!(o instanceof Reduction)) return false; - Reduction r = (Reduction)o; - return r.position == position; - } - public Reduction(Position p) { - this.position = p; - } - public String toString() { return "[reduce " + position + "]"; } - - private Forest zero = null; - public Forest zero() { - if (zero != null) return zero; - if (position.pos > 0) throw new Error(); - return zero = position.rewrite(null); - } - - } } private static final Forest[] emptyForestArray = new Forest[0]; diff --git a/src/edu/berkeley/sbp/Sequence.java b/src/edu/berkeley/sbp/Sequence.java index d274013..d8f39fd 100644 --- a/src/edu/berkeley/sbp/Sequence.java +++ b/src/edu/berkeley/sbp/Sequence.java @@ -89,6 +89,14 @@ public abstract class Sequence extends Element implements Iterable { /** the imaginary position before or after an element of a sequence; corresponds to an "LR item" */ public class Position { + private Forest zero = null; + public Forest zero() { + if (zero != null) return zero; + if (pos > 0) throw new Error(); + return zero = rewrite(null); + } + + final int pos; private final Position next; final Forest[] holder; @@ -113,7 +121,7 @@ public abstract class Sequence extends Element implements Iterable { /** true iff this Position is the last one in the sequence */ public boolean isLast() { return next()==null; } - // Reduction ///////////////////////////////////////////////////////////////////////////////// + // Position ///////////////////////////////////////////////////////////////////////////////// final Forest rewrite(Token.Location loc) { if (this==firstp()) return epsilonForm();