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