Robust/src/Analysis/OwnershipAnalysis/TokenTupleSet.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 TokenTupleSet extends Canonical {
  10
  11   private HashSet<TokenTuple> tokenTuples;
  12
  13
  14   public TokenTupleSet() {
  15     tokenTuples = new HashSet<TokenTuple>();
  16   }
  17
  18   public TokenTupleSet(TokenTuple tt) {
  19     this();
  20     assert tt != null;
  21     tokenTuples.add(tt);
  22   }
  23
  24   public TokenTupleSet(TokenTupleSet tts) {
  25     assert tts != null;
  26     // okay to clone, TokenTuple and TokenTupleSet should be canonical
  27     tokenTuples = (HashSet<TokenTuple>)tts.tokenTuples.clone();
  28   }
  29
  30
  31   public TokenTupleSet makeCanonical() {
  32     return (TokenTupleSet) Canonical.makeCanonical(this);
  33   }
  34
  35   public Iterator iterator() {
  36     return tokenTuples.iterator();
  37   }
  38
  39   public boolean isEmpty() {
  40     return tokenTuples.isEmpty();
  41   }
  42
  43   public boolean isSubset(TokenTupleSet ttsIn) {
  44     assert ttsIn != null;
  45     return ttsIn.tokenTuples.containsAll(this.tokenTuples);
  46   }
  47
  48   public boolean containsTuple(TokenTuple tt) {
  49     assert tt != null;
  50     return tokenTuples.contains(tt);
  51   }
  52
  53
  54   public TokenTupleSet union(TokenTupleSet ttsIn) {
  55     assert ttsIn != null;
  56     TokenTupleSet ttsOut = new TokenTupleSet(this);
  57     ttsOut.tokenTuples.addAll(ttsIn.tokenTuples);
  58     return ttsOut.makeCanonical();
  59   }
  60
  61   public TokenTupleSet add(TokenTuple tt) {
  62     assert tt != null;
  63     TokenTupleSet ttsOut = new TokenTupleSet(tt);
  64     return ttsOut.union(this);
  65   }
  66
  67
  68   // this should only be done with a multiple-object heap region's token!
  69   public TokenTupleSet increaseArity(Integer token) {
  70     assert token != null;
  71     TokenTupleSet ttsOut = new TokenTupleSet(this);
  72     TokenTuple tt
  73     = new TokenTuple(token, true, TokenTuple.ARITY_ONE).makeCanonical();
  74     if( ttsOut.tokenTuples.contains(tt) ) {
  75       ttsOut.tokenTuples.remove(tt);
  76       ttsOut.tokenTuples.add(
  77         new TokenTuple(token, true, TokenTuple.ARITY_MANY).makeCanonical()
  78         );
  79     }
  80
  81     return ttsOut.makeCanonical();
  82   }
  83
  84
  85   public boolean equals(Object o) {
  86     if( o == null ) {
  87       return false;
  88     }
  89
  90     if( !(o instanceof TokenTupleSet) ) {
  91       return false;
  92     }
  93
  94     TokenTupleSet tts = (TokenTupleSet) o;
  95     return tokenTuples.equals(tts.tokenTuples);
  96   }
  97
  98   public int hashCode() {
  99     return tokenTuples.hashCode();
 100   }
 101
 102
 103   // this should be a hash table so we can do this by key
 104   public boolean containsToken(Integer token) {
 105     assert token != null;
 106
 107     Iterator itr = tokenTuples.iterator();
 108     while( itr.hasNext() ) {
 109       TokenTuple tt = (TokenTuple) itr.next();
 110       if( token.equals(tt.getToken() ) ) {
 111         return true;
 112       }
 113     }
 114     return false;
 115   }
 116
 117
 118   public TokenTupleSet ageTokens(AllocationSite as) {
 119     assert as != null;
 120
 121     TokenTupleSet ttsOut = new TokenTupleSet();
 122
 123     TokenTuple ttSummary = null;
 124     boolean foundOldest  = false;
 125
 126     Iterator itrT = this.iterator();
 127     while( itrT.hasNext() ) {
 128       TokenTuple tt = (TokenTuple) itrT.next();
 129
 130       Integer token = tt.getToken();
 131       int age = as.getAge(token);
 132
 133       // summary tokens and tokens not associated with
 134       // the site should be left alone
 135       if( age == AllocationSite.AGE_notInThisSite ) {
 136         ttsOut.tokenTuples.add(tt);
 137
 138       } else {
 139         if( age == AllocationSite.AGE_summary ) {
 140           // remember the summary tuple, but don't add it
 141           // we may combine it with the oldest tuple
 142           ttSummary = tt;
 143
 144         } else if( age == AllocationSite.AGE_oldest ) {
 145           // found an oldest token, again just remember
 146           // for later
 147           foundOldest = true;
 148
 149         } else {
 150           // otherwise, we change this token to the
 151           // next older token
 152           Integer tokenToChangeTo = as.getIthOldest(age + 1);
 153           TokenTuple ttAged       = tt.changeTokenTo(tokenToChangeTo);
 154           ttsOut.tokenTuples.add(ttAged);
 155         }
 156
 157       }
 158     }
 159
 160     // there are four cases to consider here
 161     // 1. we found a summary tuple and no oldest tuple
 162     //    Here we just pass the summary unchanged
 163     // 2. we found an oldest tuple, no summary
 164     //    Make a new, arity-one summary tuple
 165     // 3. we found both a summary and an oldest
 166     //    Merge them by increasing arity of summary
 167     // 4. (not handled) we found neither, do nothing
 168     if       ( ttSummary != null && !foundOldest ) {
 169       ttsOut.tokenTuples.add(ttSummary);
 170
 171     } else if( ttSummary == null &&  foundOldest ) {
 172       ttsOut.tokenTuples.add(new TokenTuple(as.getSummary(),
 173                                             true,
 174                                             TokenTuple.ARITY_ONE).makeCanonical() );
 175
 176     } else if( ttSummary != null &&  foundOldest ) {
 177       ttsOut.tokenTuples.add(ttSummary.increaseArity() );
 178     }
 179
 180     return ttsOut.makeCanonical();
 181   }
 182
 183
 184   public String toString() {
 185     return tokenTuples.toString();
 186   }
 187 }