src/edu/berkeley/sbp/Reduction.java

   1 // Copyright 2006 all rights reserved; see LICENSE file for BSD-style license
   2
   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;
   8 import java.io.*;
   9 import java.util.*;
  10 import java.lang.reflect.*;
  11
  12 final class Reduction implements Comparable<Reduction> {
  13
  14     public Position position;
  15     public GSS.Phase phase;
  16     public Forest result;
  17     public Node node;
  18     boolean done = false;
  19
  20     public Reduction(Node node, Position position, Forest result, GSS.Phase target) {
  21         this.position = position;
  22         this.result = result;
  23         this.phase = target;
  24         this.node = node;
  25         target.reductionQueue.add(this);
  26     }
  27
  28     public void perform() {
  29         if (done) return;
  30         done = true;
  31         node.finish(position, result, phase);
  32     }
  33
  34     public String toString() { return position+""; }
  35
  36     public int compareTo(Reduction r) {
  37         int ret = compareTo0(r);
  38         if (ret == 0) {
  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;
  45         }
  46         return -1 * ret;
  47     }
  48
  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());
  53     }
  54
  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;
  63         }
  64         return false;
  65     }
  66
  67     public static final int LESS_THAN = -1;
  68     public static final int EQUAL_TO = 0;
  69     public static final int GREATER_THAN = 1;
  70
  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;
  77         return 0;
  78     }
  79     public int pos() { return targetPhase()==null ? 0 : targetPhase().pos; }
  80     public GSS.Phase targetPhase() { return node.phase(); }
  81
  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;
  90         }
  91         return false;
  92     }
  93 }