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 }