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