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   public boolean containsTupleSetWithBoth(TokenTuple tt1, TokenTuple tt2) {
  67     Iterator itr = iterator();
  68     while( itr.hasNext() ) {
  69       TokenTupleSet tts = (TokenTupleSet) itr.next();
  70       if( tts.containsTuple(tt1) && tts.containsTuple(tt2) ) {
  71         return true;
  72       }
  73     }
  74     return false;
  75   }
  76
  77   public ReachabilitySet increaseArity(Integer token) {
  78     assert token != null;
  79
  80     HashSet<TokenTupleSet> possibleReachabilitiesNew = new HashSet<TokenTupleSet>();
  81
  82     Iterator itr = iterator();
  83     while( itr.hasNext() ) {
  84       TokenTupleSet tts = (TokenTupleSet) itr.next();
  85       possibleReachabilitiesNew.add(tts.increaseArity(token) );
  86     }
  87
  88     return new ReachabilitySet(possibleReachabilitiesNew).makeCanonical();
  89   }
  90
  91
  92   public ReachabilitySet union(ReachabilitySet rsIn) {
  93     assert rsIn != null;
  94
  95     ReachabilitySet rsOut = new ReachabilitySet(this);
  96     rsOut.possibleReachabilities.addAll(rsIn.possibleReachabilities);
  97     return rsOut.makeCanonical();
  98   }
  99
 100   public ReachabilitySet union(TokenTupleSet ttsIn) {
 101     assert ttsIn != null;
 102
 103     ReachabilitySet rsOut = new ReachabilitySet(this);
 104     rsOut.possibleReachabilities.add(ttsIn);
 105     return rsOut.makeCanonical();
 106   }
 107
 108   public ReachabilitySet intersection(ReachabilitySet rsIn) {
 109     assert rsIn != null;
 110
 111     ReachabilitySet rsOut = new ReachabilitySet();
 112
 113     Iterator i = this.iterator();
 114     while( i.hasNext() ) {
 115       TokenTupleSet tts = (TokenTupleSet) i.next();
 116       if( rsIn.possibleReachabilities.contains(tts) ) {
 117         rsOut.possibleReachabilities.add(tts);
 118       }
 119     }
 120
 121     return rsOut.makeCanonical();
 122   }
 123
 124
 125   public ReachabilitySet add(TokenTupleSet tts) {
 126     assert tts != null;
 127     ReachabilitySet rsOut = new ReachabilitySet(tts);
 128     return rsOut.union(this);
 129   }
 130
 131
 132   public ChangeTupleSet unionUpArityToChangeSet(ReachabilitySet rsIn) {
 133     assert rsIn != null;
 134
 135     ChangeTupleSet ctsOut = new ChangeTupleSet();
 136
 137     Iterator itrO = this.iterator();
 138     while( itrO.hasNext() ) {
 139       TokenTupleSet o = (TokenTupleSet) itrO.next();
 140
 141       Iterator itrR = rsIn.iterator();
 142       while( itrR.hasNext() ) {
 143         TokenTupleSet r = (TokenTupleSet) itrR.next();
 144
 145         TokenTupleSet theUnion = new TokenTupleSet();
 146
 147         Iterator itrRelement = r.iterator();
 148         while( itrRelement.hasNext() ) {
 149           TokenTuple e = (TokenTuple) itrRelement.next();
 150
 151           if( o.containsToken(e.getToken() ) ) {
 152             theUnion = theUnion.union(new TokenTupleSet(e.increaseArity() ) ).makeCanonical();
 153           } else {
 154             theUnion = theUnion.union(new TokenTupleSet(e) ).makeCanonical();
 155           }
 156         }
 157
 158         Iterator itrOelement = o.iterator();
 159         while( itrOelement.hasNext() ) {
 160           TokenTuple e = (TokenTuple) itrOelement.next();
 161
 162           if( !theUnion.containsToken(e.getToken() ) ) {
 163             theUnion = theUnion.union(new TokenTupleSet(e) ).makeCanonical();
 164           }
 165         }
 166
 167         if( !theUnion.isEmpty() ) {
 168           ctsOut = ctsOut.union(
 169             new ChangeTupleSet(new ChangeTuple(o, theUnion) )
 170             );
 171         }
 172       }
 173     }
 174
 175     return ctsOut.makeCanonical();
 176   }
 177
 178
 179   public ReachabilitySet ageTokens(AllocationSite as) {
 180     assert as != null;
 181
 182     ReachabilitySet rsOut = new ReachabilitySet();
 183
 184     Iterator itrS = this.iterator();
 185     while( itrS.hasNext() ) {
 186       TokenTupleSet tts = (TokenTupleSet) itrS.next();
 187       rsOut.possibleReachabilities.add(tts.ageTokens(as) );
 188     }
 189
 190     return rsOut.makeCanonical();
 191   }
 192
 193
 194   public ReachabilitySet unshadowTokens(AllocationSite as) {
 195     assert as != null;
 196
 197     ReachabilitySet rsOut = new ReachabilitySet();
 198
 199     Iterator itrS = this.iterator();
 200     while( itrS.hasNext() ) {
 201       TokenTupleSet tts = (TokenTupleSet) itrS.next();
 202       rsOut.possibleReachabilities.add(tts.unshadowTokens(as) );
 203     }
 204
 205     return rsOut.makeCanonical();
 206   }
 207
 208
 209   public ReachabilitySet toShadowTokens(AllocationSite as) {
 210     assert as != null;
 211
 212     ReachabilitySet rsOut = new ReachabilitySet();
 213
 214     Iterator itrS = this.iterator();
 215     while( itrS.hasNext() ) {
 216       TokenTupleSet tts = (TokenTupleSet) itrS.next();
 217       rsOut.possibleReachabilities.add(tts.toShadowTokens(as) );
 218     }
 219
 220     return rsOut.makeCanonical();
 221   }
 222
 223
 224   public ReachabilitySet pruneBy(ReachabilitySet rsIn) {
 225     assert rsIn != null;
 226
 227     ReachabilitySet rsOut = new ReachabilitySet();
 228
 229     Iterator itrB = this.iterator();
 230     while( itrB.hasNext() ) {
 231       TokenTupleSet ttsB = (TokenTupleSet) itrB.next();
 232
 233       boolean subsetExists = false;
 234
 235       Iterator itrA = rsIn.iterator();
 236       while( itrA.hasNext() && !subsetExists ) {
 237         TokenTupleSet ttsA = (TokenTupleSet) itrA.next();
 238
 239         if( ttsA.isSubset(ttsB) ) {
 240           subsetExists = true;
 241         }
 242       }
 243
 244       if( subsetExists ) {
 245         rsOut.possibleReachabilities.add(ttsB);
 246       }
 247     }
 248
 249     return rsOut.makeCanonical();
 250   }
 251
 252
 253   public ReachabilitySet exhaustiveArityCombinations() {
 254     ReachabilitySet rsOut = new ReachabilitySet();
 255
 256     int numDimensions = this.possibleReachabilities.size();
 257
 258     // add an extra digit to detect termination
 259     int[] digits = new int[numDimensions+1];
 260
 261     int minArity = 0;
 262     int maxArity = 2;
 263
 264     // start with the minimum possible coordinate
 265     for( int i = 0; i < numDimensions+1; ++i ) {
 266       digits[i] = minArity;
 267     }
 268
 269     // and stop when the highest-ordered axis rolls above the minimum
 270     while( digits[numDimensions] == minArity ) {
 271
 272       // spit out a "coordinate" made from these digits
 273       TokenTupleSet ttsCoordinate = new TokenTupleSet();
 274       Iterator<TokenTupleSet> ttsItr = this.iterator();
 275       for( int i = 0; i < numDimensions; ++i ) {
 276         assert ttsItr.hasNext();
 277         TokenTupleSet ttsUnit = ttsItr.next();
 278         for( int j = 0; j < digits[i]; ++j ) {
 279           ttsCoordinate = ttsCoordinate.unionUpArity(ttsUnit);
 280         }
 281       }
 282       rsOut = rsOut.add(ttsCoordinate.makeCanonical() );
 283
 284       // increment
 285       for( int i = 0; i < numDimensions+1; ++i ) {
 286         digits[i]++;
 287         if( digits[i] > maxArity ) {
 288           // this axis reached its max, so roll it back to min and increment next higher digit
 289           digits[i] = minArity;
 290
 291         } else {
 292           // this axis did not reach its max so we just enumerated a new unique coordinate, stop
 293           break;
 294         }
 295       }
 296     }
 297
 298     return rsOut.makeCanonical();
 299   }
 300
 301
 302   public boolean equals(Object o) {
 303     if( o == null ) {
 304       return false;
 305     }
 306
 307     if( !(o instanceof ReachabilitySet) ) {
 308       return false;
 309     }
 310
 311     ReachabilitySet rs = (ReachabilitySet) o;
 312     return possibleReachabilities.equals(rs.possibleReachabilities);
 313   }
 314
 315   public int hashCode() {
 316     return possibleReachabilities.hashCode();
 317   }
 318
 319
 320   public String toStringEscapeNewline() {
 321     String s = "[";
 322
 323     Iterator i = this.iterator();
 324     while( i.hasNext() ) {
 325       s += i.next();
 326       if( i.hasNext() ) {
 327         s += "\\n";
 328       }
 329     }
 330
 331     s += "]";
 332     return s;
 333   }
 334
 335   public String toString() {
 336     String s = "[";
 337
 338     Iterator i = this.iterator();
 339     while( i.hasNext() ) {
 340       s += i.next();
 341       if( i.hasNext() ) {
 342         s += "\n";
 343       }
 344     }
 345
 346     s += "]";
 347     return s;
 348   }
 349 }