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