-// Copyright 2006 all rights reserved; see LICENSE file for BSD-style license
+// 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.Parser.Table.*;
-import edu.berkeley.sbp.Sequence.Position;
-import java.io.*;
-import java.util.*;
-import java.lang.reflect.*;
+import edu.berkeley.sbp.Sequence.Pos;
+import edu.berkeley.sbp.Sequence.Pos;
final class Reduction implements Comparable<Reduction> {
- public Position position;
- public GSS.Phase phase;
- public Forest result;
- public Node node;
- boolean done = false;
+ private Pos reduction;
+ private GSS.Phase phase;
+ private Forest forest;
+ private Node pred;
- public Reduction(Node node, Position position, Forest result, GSS.Phase target) {
- this.position = position;
- this.result = result;
+ public Reduction(Node pred, Pos reduction, Forest forest, GSS.Phase target) {
+ this.reduction = reduction;
+ this.forest = forest;
this.phase = target;
- this.node = node;
- target.reductionQueue.add(this);
- }
-
- public void perform() {
- if (done) return;
- done = true;
- node.finish(position, result, phase);
+ this.pred = pred;
+ target.addReduction(this);
}
public int compareTo(Reduction r) {
- int ret = compareTo0(r);
- if (ret == 0) {
- Walk.Cache cache = node.state().cache();
- if (canKill(cache, position, r.position) && canKill(cache, r.position, position)) throw new Error();
- if (canKill(cache, position, r.position)) ret = 1;
- else if (canKill(cache, r.position, position)) ret = -1;
- if (canNeed(cache, position, r.position)) ret = 1;
- else if (canNeed(cache, r.position, position)) ret = -1;
+ if (pred.phase()!=null || r.pred.phase()!=null) {
+ if (pred.phase()==null) return 1;
+ if (r.pred.phase()==null) return -1;
+ if (pred.phase().pos < r.pred.phase().pos) return 1;
+ if (pred.phase().pos > r.pred.phase().pos) return -1;
}
- return -1 * ret;
+ /*
+ int master = Parser.mastercache.comparePositions(reduction(), r.reduction());
+ if (master != 0 && master != signum(reduction.ord() - r.reduction.ord()))
+ throw new Error("master="+master+" and a="+reduction.ord()+" and b="+r.reduction.ord()+"\n"+reduction+"\n"+r.reduction);
+ */
+ return reduction.compareTo(r.reduction);
}
- private static boolean isRightNullable(Walk.Cache c, Position p) {
- if (p.isLast()) return true;
- if (!c.possiblyEpsilon(p.element())) return false;
- return isRightNullable(c, p.next());
- }
-
- public static boolean canKill(Walk.Cache cache, Position mep, Position himp) {
- if (!isRightNullable(cache, mep)) return false;
- if (!isRightNullable(cache, himp)) return false;
- Sequence me = mep.owner();
- Sequence him = himp.owner();
- for(Sequence killer : him.hates()) {
- HashSet<Sequence> eq2 = new Walk.EquivalentTo(killer, cache).walk();
- if (eq2.contains(me)) return true;
- }
- return false;
+ private int signum(int x) {
+ if (x==0) return 0;
+ if (x<0) return -1;
+ return 1;
}
- public static final int LESS_THAN = -1;
- public static final int EQUAL_TO = 0;
- public static final int GREATER_THAN = 1;
-
- public int compareTo0(Reduction n) {
- if (targetPhase()==null && n.targetPhase()==null) return EQUAL_TO;
- if (targetPhase()==null) return LESS_THAN;
- if (n.targetPhase()==null) return GREATER_THAN;
- if (targetPhase().pos < n.targetPhase().pos) return LESS_THAN;
- if (targetPhase().pos > n.targetPhase().pos) return GREATER_THAN;
- return 0;
- }
- public int pos() { return targetPhase()==null ? 0 : targetPhase().pos; }
- public GSS.Phase targetPhase() { return node.phase(); }
-
- public static boolean canNeed(Walk.Cache cache, Position mep, Position himp) {
- if (!isRightNullable(cache, mep)) return false;
- if (!isRightNullable(cache, himp)) return false;
- Sequence me = mep.owner();
- Sequence him = himp.owner();
- for(Sequence needer : him.needs()) {
- HashSet<Sequence> eq2 = new Walk.EquivalentTo(needer, cache).walk();
- if (eq2.contains(me)) return true;
- }
- return false;
+ public void perform() {
+ if (reduction==null) return;
+ phase.newNodeFromReduction(forest, reduction, pred);
}
+ public GSS.Phase predPhase() { return pred.phase(); }
+ public Pos reduction() { return reduction; }
+ public GSS.Phase targetPhase() { return phase; }
+ public String toString() { return (pred.phase()==null ? 0 : pred.phase().pos) + ":"+reduction; }
}