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     if( numDimensions > 10 ) {
 259       System.out.println( "exhaustiveArityCombinations numDimensions = "+numDimensions );
 260     }
 261
 262     // add an extra digit to detect termination
 263     int[] digits = new int[numDimensions+1];
 264
 265     int minArity = 0;
 266     int maxArity = 2;
 267
 268     // start with the minimum possible coordinate
 269     for( int i = 0; i < numDimensions+1; ++i ) {
 270       digits[i] = minArity;
 271     }
 272
 273     // and stop when the highest-ordered axis rolls above the minimum
 274     while( digits[numDimensions] == minArity ) {
 275
 276       // spit out a "coordinate" made from these digits
 277       TokenTupleSet ttsCoordinate = new TokenTupleSet();
 278       Iterator<TokenTupleSet> ttsItr = this.iterator();
 279       for( int i = 0; i < numDimensions; ++i ) {
 280         assert ttsItr.hasNext();
 281         TokenTupleSet ttsUnit = ttsItr.next();
 282         for( int j = 0; j < digits[i]; ++j ) {
 283           ttsCoordinate = ttsCoordinate.unionUpArity(ttsUnit);
 284         }
 285       }
 286       rsOut = rsOut.add(ttsCoordinate.makeCanonical() );
 287
 288       // increment
 289       for( int i = 0; i < numDimensions+1; ++i ) {
 290         digits[i]++;
 291
 292
 293         if( i == 11 ) {
 294           System.out.print( "x " );
 295         }
 296
 297         if( i == 15 ) {
 298           System.out.print( "@ " );
 299         }
 300
 301         if( i == 17 ) {
 302           System.out.print( "# " );
 303         }
 304
 305         if( digits[i] > maxArity ) {
 306           // this axis reached its max, so roll it back to min and increment next higher digit
 307           digits[i] = minArity;
 308
 309         } else {
 310           // this axis did not reach its max so we just enumerated a new unique coordinate, stop
 311           break;
 312         }
 313       }
 314     }
 315
 316     return rsOut.makeCanonical();
 317   }
 318
 319
 320   public boolean equals(Object o) {
 321     if( o == null ) {
 322       return false;
 323     }
 324
 325     if( !(o instanceof ReachabilitySet) ) {
 326       return false;
 327     }
 328
 329     ReachabilitySet rs = (ReachabilitySet) o;
 330     return possibleReachabilities.equals(rs.possibleReachabilities);
 331   }
 332
 333   public int hashCode() {
 334     return possibleReachabilities.hashCode();
 335   }
 336
 337
 338   public String toStringEscapeNewline() {
 339     String s = "[";
 340
 341     Iterator i = this.iterator();
 342     while( i.hasNext() ) {
 343       s += i.next();
 344       if( i.hasNext() ) {
 345         s += "\\n";
 346       }
 347     }
 348
 349     s += "]";
 350     return s;
 351   }
 352
 353   public String toString() {
 354     String s = "[";
 355
 356     Iterator i = this.iterator();
 357     while( i.hasNext() ) {
 358       s += i.next();
 359       if( i.hasNext() ) {
 360         s += "\n";
 361       }
 362     }
 363
 364     s += "]";
 365     return s;
 366   }
 367 }