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<TokenTupleSet> 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 unshadowTokens(AllocationSite as) {
 185     assert as != null;
 186
 187     ReachabilitySet rsOut = new ReachabilitySet();
 188
 189     Iterator itrS = this.iterator();
 190     while( itrS.hasNext() ) {
 191       TokenTupleSet tts = (TokenTupleSet) itrS.next();
 192       rsOut.possibleReachabilities.add( tts.unshadowTokens(as) );
 193     }
 194
 195     return rsOut.makeCanonical();
 196   }
 197
 198
 199   public ReachabilitySet toShadowTokens(AllocationSite as) {
 200     assert as != null;
 201
 202     ReachabilitySet rsOut = new ReachabilitySet();
 203
 204     Iterator itrS = this.iterator();
 205     while( itrS.hasNext() ) {
 206       TokenTupleSet tts = (TokenTupleSet) itrS.next();
 207       rsOut.possibleReachabilities.add( tts.toShadowTokens(as) );
 208     }
 209
 210     return rsOut.makeCanonical();
 211   }
 212
 213
 214   public ReachabilitySet pruneBy(ReachabilitySet rsIn) {
 215     assert rsIn != null;
 216
 217     ReachabilitySet rsOut = new ReachabilitySet();
 218
 219     Iterator itrB = this.iterator();
 220     while( itrB.hasNext() ) {
 221       TokenTupleSet ttsB = (TokenTupleSet) itrB.next();
 222
 223       boolean subsetExists = false;
 224
 225       Iterator itrA = rsIn.iterator();
 226       while( itrA.hasNext() && !subsetExists ) {
 227         TokenTupleSet ttsA = (TokenTupleSet) itrA.next();
 228
 229         if( ttsA.isSubset(ttsB) ) {
 230           subsetExists = true;
 231         }
 232       }
 233
 234       if( subsetExists ) {
 235         rsOut.possibleReachabilities.add(ttsB);
 236       }
 237     }
 238
 239     return rsOut.makeCanonical();
 240   }
 241
 242
 243   public ReachabilitySet exhaustiveArityCombinations() {
 244     ReachabilitySet rsOut = new ReachabilitySet();
 245
 246     int numDimensions = this.possibleReachabilities.size();
 247
 248     // add an extra digit to detect termination
 249     int[] digits = new int[numDimensions+1];
 250
 251     int minArity = 0;
 252     int maxArity = 2;
 253
 254     // start with the minimum possible coordinate
 255     for( int i = 0; i < numDimensions+1; ++i ) {
 256       digits[i] = minArity;
 257     }
 258
 259     // and stop when the highest-ordered axis rolls above the minimum
 260     while( digits[numDimensions] == minArity ) {
 261
 262       // spit out a "coordinate" made from these digits
 263       TokenTupleSet ttsCoordinate = new TokenTupleSet();
 264       Iterator<TokenTupleSet> ttsItr = this.iterator();
 265       for( int i = 0; i < numDimensions; ++i ) {
 266         assert ttsItr.hasNext();
 267         TokenTupleSet ttsUnit = ttsItr.next();
 268         for( int j = 0; j < digits[i]; ++j ) {
 269           ttsCoordinate = ttsCoordinate.unionUpArity( ttsUnit );
 270         }
 271       }
 272       rsOut = rsOut.add( ttsCoordinate.makeCanonical() );
 273
 274       // increment
 275       for( int i = 0; i < numDimensions+1; ++i ) {
 276         digits[i]++;
 277         if( digits[i] > maxArity ) {
 278           // this axis reached its max, so roll it back to min and increment next higher digit
 279           digits[i] = minArity;
 280
 281         } else {
 282           // this axis did not reach its max so we just enumerated a new unique coordinate, stop
 283           break;
 284         }
 285       }
 286     }
 287
 288     return rsOut.makeCanonical();
 289   }
 290
 291
 292   public boolean equals(Object o) {
 293     if( o == null ) {
 294       return false;
 295     }
 296
 297     if( !(o instanceof ReachabilitySet) ) {
 298       return false;
 299     }
 300
 301     ReachabilitySet rs = (ReachabilitySet) o;
 302     return possibleReachabilities.equals(rs.possibleReachabilities);
 303   }
 304
 305   public int hashCode() {
 306     return possibleReachabilities.hashCode();
 307   }
 308
 309
 310   public String toStringEscapeNewline() {
 311     String s = "[";
 312
 313     Iterator i = this.iterator();
 314     while( i.hasNext() ) {
 315       s += i.next();
 316       if( i.hasNext() ) {
 317         s += "\\n";
 318       }
 319     }
 320
 321     s += "]";
 322     return s;
 323   }
 324
 325   public String toString() {
 326     String s = "[";
 327
 328     Iterator i = this.iterator();
 329     while( i.hasNext() ) {
 330       s += i.next();
 331       if( i.hasNext() ) {
 332         s += "\n";
 333       }
 334     }
 335
 336     s += "]";
 337     return s;
 338   }
 339 }