1 // Copyright 2006 all rights reserved; see LICENSE file for BSD-style license
3 package edu.berkeley.sbp;
4 import edu.berkeley.sbp.*;
5 import edu.berkeley.sbp.util.*;
6 import edu.berkeley.sbp.Parser.Table.*;
7 import edu.berkeley.sbp.Sequence.Position;
10 import java.lang.reflect.*;
12 final class Reduction implements Comparable<Reduction> {
14 public Position position;
15 public GSS.Phase phase;
20 public Reduction(Node node, Position position, Forest result, GSS.Phase target) {
21 this.position = position;
25 target.reductionQueue.add(this);
28 public void perform() {
31 node.finish(position, result, phase);
34 public String toString() { return position+""; }
36 public int compareTo(Reduction r) {
37 int ret = compareTo0(r);
39 Walk.Cache cache = node.state().cache();
40 if (canKill(cache, position, r.position) && canKill(cache, r.position, position)) throw new Error();
41 if (canKill(cache, position, r.position)) ret = 1;
42 else if (canKill(cache, r.position, position)) ret = -1;
43 if (canNeed(cache, position, r.position)) ret = 1;
44 else if (canNeed(cache, r.position, position)) ret = -1;
49 private static boolean isRightNullable(Walk.Cache c, Position p) {
50 if (p.isLast()) return true;
51 if (!c.possiblyEpsilon(p.element())) return false;
52 return isRightNullable(c, p.next());
55 public static boolean canKill(Walk.Cache cache, Position mep, Position himp) {
56 if (!isRightNullable(cache, mep)) return false;
57 if (!isRightNullable(cache, himp)) return false;
58 Sequence me = mep.owner();
59 Sequence him = himp.owner();
60 for(Sequence killer : him.hates()) {
61 HashSet<Sequence> eq2 = new Walk.EquivalentTo(killer, cache).walk();
62 if (eq2.contains(me)) return true;
67 public static final int LESS_THAN = -1;
68 public static final int EQUAL_TO = 0;
69 public static final int GREATER_THAN = 1;
71 public int compareTo0(Reduction n) {
72 if (targetPhase()==null && n.targetPhase()==null) return EQUAL_TO;
73 if (targetPhase()==null) return LESS_THAN;
74 if (n.targetPhase()==null) return GREATER_THAN;
75 if (targetPhase().pos < n.targetPhase().pos) return LESS_THAN;
76 if (targetPhase().pos > n.targetPhase().pos) return GREATER_THAN;
79 public int pos() { return targetPhase()==null ? 0 : targetPhase().pos; }
80 public GSS.Phase targetPhase() { return node.phase(); }
82 public static boolean canNeed(Walk.Cache cache, Position mep, Position himp) {
83 if (!isRightNullable(cache, mep)) return false;
84 if (!isRightNullable(cache, himp)) return false;
85 Sequence me = mep.owner();
86 Sequence him = himp.owner();
87 for(Sequence needer : him.needs()) {
88 HashSet<Sequence> eq2 = new Walk.EquivalentTo(needer, cache).walk();
89 if (eq2.contains(me)) return true;