Robust/src/Analysis/OwnershipAnalysis/ReachabilitySet.java

   1 package Analysis.OwnershipAnalysis;
   2
   3 import IR.*;
   4 import IR.Flat.*;
   5 import java.util.*;
   6 import java.io.*;
   7
   8
   9 public class ReachabilitySet extends Canonical {
  10
  11   private HashSet<TokenTupleSet> possibleReachabilities;
  12
  13   public ReachabilitySet() {
  14     possibleReachabilities = new HashSet<TokenTupleSet>();
  15   }
  16
  17   public ReachabilitySet(TokenTupleSet tts) {
  18     this();
  19     assert tts != null;
  20     possibleReachabilities.add(tts);
  21   }
  22
  23   public ReachabilitySet(TokenTuple tt) {
  24     // can't assert before calling this(), it will
  25     // do the checking though
  26     this( new TokenTupleSet(tt).makeCanonical() );
  27   }
  28
  29   public ReachabilitySet(HashSet<TokenTupleSet> possibleReachabilities) {
  30     assert possibleReachabilities != null;
  31     this.possibleReachabilities = possibleReachabilities;
  32   }
  33
  34   public ReachabilitySet(ReachabilitySet rs) {
  35     assert rs != null;
  36     // okay to clone, ReachabilitySet should be canonical
  37     possibleReachabilities = (HashSet<TokenTupleSet>)rs.possibleReachabilities.clone();
  38   }
  39
  40
  41   public ReachabilitySet makeCanonical() {
  42     return (ReachabilitySet) Canonical.makeCanonical(this);
  43   }
  44
  45   public Iterator iterator() {
  46     return possibleReachabilities.iterator();
  47   }
  48
  49
  50   public boolean contains(TokenTupleSet tts) {
  51     assert tts != null;
  52     return possibleReachabilities.contains(tts);
  53   }
  54
  55   public boolean containsTuple(TokenTuple tt) {
  56     Iterator itr = iterator();
  57     while( itr.hasNext() ) {
  58       TokenTupleSet tts = (TokenTupleSet) itr.next();
  59       if( tts.containsTuple(tt) ) {
  60         return true;
  61       }
  62     }
  63     return false;
  64   }
  65
  66
  67   public ReachabilitySet increaseArity(Integer token) {
  68     assert token != null;
  69
  70     HashSet<TokenTupleSet> possibleReachabilitiesNew = new HashSet<TokenTupleSet>();
  71
  72     Iterator itr = iterator();
  73     while( itr.hasNext() ) {
  74       TokenTupleSet tts = (TokenTupleSet) itr.next();
  75       possibleReachabilitiesNew.add(tts.increaseArity(token) );
  76     }
  77
  78     return new ReachabilitySet(possibleReachabilitiesNew).makeCanonical();
  79   }
  80
  81
  82   public ReachabilitySet union(ReachabilitySet rsIn) {
  83     assert rsIn != null;
  84
  85     ReachabilitySet rsOut = new ReachabilitySet(this);
  86     rsOut.possibleReachabilities.addAll(rsIn.possibleReachabilities);
  87     return rsOut.makeCanonical();
  88   }
  89
  90   public ReachabilitySet union(TokenTupleSet ttsIn) {
  91     assert ttsIn != null;
  92
  93     ReachabilitySet rsOut = new ReachabilitySet(this);
  94     rsOut.possibleReachabilities.add(ttsIn);
  95     return rsOut.makeCanonical();
  96   }
  97
  98   public ReachabilitySet intersection(ReachabilitySet rsIn) {
  99     assert rsIn != null;
 100
 101     ReachabilitySet rsOut = new ReachabilitySet();
 102
 103     Iterator i = this.iterator();
 104     while( i.hasNext() ) {
 105       TokenTupleSet tts = (TokenTupleSet) i.next();
 106       if( rsIn.possibleReachabilities.contains(tts) ) {
 107         rsOut.possibleReachabilities.add(tts);
 108       }
 109     }
 110
 111     return rsOut.makeCanonical();
 112   }
 113
 114
 115   public ReachabilitySet add(TokenTupleSet tts) {
 116     assert tts != null;
 117     ReachabilitySet rsOut = new ReachabilitySet(tts);
 118     return rsOut.union(this);
 119   }
 120
 121
 122   public ChangeTupleSet unionUpArityToChangeSet(ReachabilitySet rsIn) {
 123     assert rsIn != null;
 124
 125     ChangeTupleSet ctsOut = new ChangeTupleSet();
 126
 127     Iterator itrO = this.iterator();
 128     while( itrO.hasNext() ) {
 129       TokenTupleSet o = (TokenTupleSet) itrO.next();
 130
 131       Iterator itrR = rsIn.iterator();
 132       while( itrR.hasNext() ) {
 133         TokenTupleSet r = (TokenTupleSet) itrR.next();
 134
 135         TokenTupleSet theUnion = new TokenTupleSet();
 136
 137         Iterator itrRelement = r.iterator();
 138         while( itrRelement.hasNext() ) {
 139           TokenTuple e = (TokenTuple) itrRelement.next();
 140
 141           if( o.containsToken(e.getToken() ) ) {
 142             theUnion = theUnion.union(new TokenTupleSet(e.increaseArity() ) ).makeCanonical();
 143           } else {
 144             theUnion = theUnion.union(new TokenTupleSet(e) ).makeCanonical();
 145           }
 146         }
 147
 148         Iterator itrOelement = o.iterator();
 149         while( itrOelement.hasNext() ) {
 150           TokenTuple e = (TokenTuple) itrOelement.next();
 151
 152           if( !theUnion.containsToken(e.getToken() ) ) {
 153             theUnion = theUnion.union(new TokenTupleSet(e) ).makeCanonical();
 154           }
 155         }
 156
 157         if( !theUnion.isEmpty() ) {
 158           ctsOut = ctsOut.union(
 159             new ChangeTupleSet(new ChangeTuple(o, theUnion) )
 160             );
 161         }
 162       }
 163     }
 164
 165     return ctsOut.makeCanonical();
 166   }
 167
 168
 169   public ReachabilitySet ageTokens(AllocationSite as) {
 170     assert as != null;
 171
 172     ReachabilitySet rsOut = new ReachabilitySet();
 173
 174     Iterator itrS = this.iterator();
 175     while( itrS.hasNext() ) {
 176       TokenTupleSet tts = (TokenTupleSet) itrS.next();
 177       rsOut.possibleReachabilities.add(tts.ageTokens(as) );
 178     }
 179
 180     return rsOut.makeCanonical();
 181   }
 182
 183
 184   public ReachabilitySet pruneBy(ReachabilitySet rsIn) {
 185     assert rsIn != null;
 186
 187     ReachabilitySet rsOut = new ReachabilitySet();
 188
 189     Iterator itrB = this.iterator();
 190     while( itrB.hasNext() ) {
 191       TokenTupleSet ttsB = (TokenTupleSet) itrB.next();
 192
 193       boolean subsetExists = false;
 194
 195       Iterator itrA = rsIn.iterator();
 196       while( itrA.hasNext() && !subsetExists ) {
 197         TokenTupleSet ttsA = (TokenTupleSet) itrA.next();
 198
 199         if( ttsA.isSubset(ttsB) ) {
 200           subsetExists = true;
 201         }
 202       }
 203
 204       if( subsetExists ) {
 205         rsOut.possibleReachabilities.add(ttsB);
 206       }
 207     }
 208
 209     return rsOut.makeCanonical();
 210   }
 211
 212
 213   public boolean equals(Object o) {
 214     if( o == null ) {
 215       return false;
 216     }
 217
 218     if( !(o instanceof ReachabilitySet) ) {
 219       return false;
 220     }
 221
 222     ReachabilitySet rs = (ReachabilitySet) o;
 223     return possibleReachabilities.equals(rs.possibleReachabilities);
 224   }
 225
 226   public int hashCode() {
 227     return possibleReachabilities.hashCode();
 228   }
 229
 230
 231   public String toStringEscapeNewline() {
 232     String s = "[";
 233
 234     Iterator i = this.iterator();
 235     while( i.hasNext() ) {
 236       s += i.next();
 237       if( i.hasNext() ) {
 238         s += "\\n";
 239       }
 240     }
 241
 242     s += "]";
 243     return s;
 244   }
 245
 246   public String toString() {
 247     String s = "[";
 248
 249     Iterator i = this.iterator();
 250     while( i.hasNext() ) {
 251       s += i.next();
 252       if( i.hasNext() ) {
 253         s += "\n";
 254       }
 255     }
 256
 257     s += "]";
 258     return s;
 259   }
 260 }