1 package Analysis.OwnershipAnalysis;
9 public class TokenTupleSet extends Canonical {
11 private HashSet<TokenTuple> tokenTuples;
14 public TokenTupleSet() {
15 tokenTuples = new HashSet<TokenTuple>();
18 public TokenTupleSet(TokenTuple tt) {
24 public TokenTupleSet(TokenTupleSet tts) {
26 // okay to clone, TokenTuple and TokenTupleSet should be canonical
27 tokenTuples = (HashSet<TokenTuple>)tts.tokenTuples.clone();
31 public TokenTupleSet makeCanonical() {
32 return (TokenTupleSet) Canonical.makeCanonical(this);
35 public Iterator iterator() {
36 return tokenTuples.iterator();
39 public boolean isEmpty() {
40 return tokenTuples.isEmpty();
43 public boolean isSubset(TokenTupleSet ttsIn) {
45 return ttsIn.tokenTuples.containsAll(this.tokenTuples);
48 public boolean containsTuple(TokenTuple tt) {
50 return tokenTuples.contains(tt);
54 public TokenTupleSet union(TokenTupleSet ttsIn) {
56 TokenTupleSet ttsOut = new TokenTupleSet(this);
57 ttsOut.tokenTuples.addAll(ttsIn.tokenTuples);
58 return ttsOut.makeCanonical();
61 public TokenTupleSet unionUpArity( TokenTupleSet ttsIn ) {
63 TokenTupleSet ttsOut = new TokenTupleSet();
65 Iterator<TokenTuple> ttItr = this.iterator();
66 while( ttItr.hasNext() ) {
67 TokenTuple tt = ttItr.next();
69 if( ttsIn.containsToken( tt.getToken() ) ) {
70 ttsOut.tokenTuples.add(tt.increaseArity());
72 ttsOut.tokenTuples.add(tt);
76 ttItr = ttsIn.iterator();
77 while( ttItr.hasNext() ) {
78 TokenTuple tt = ttItr.next();
80 if( !ttsOut.containsToken(tt.getToken()) ) {
81 ttsOut.tokenTuples.add(tt);
85 return ttsOut.makeCanonical();
88 public TokenTupleSet add(TokenTuple tt) {
90 TokenTupleSet ttsOut = new TokenTupleSet(tt);
91 return ttsOut.union(this);
95 // this should only be done with a multiple-object heap region's token!
96 public TokenTupleSet increaseArity(Integer token) {
98 TokenTupleSet ttsOut = new TokenTupleSet(this);
100 = new TokenTuple(token, true, TokenTuple.ARITY_ONE).makeCanonical();
101 if( ttsOut.tokenTuples.contains(tt) ) {
102 ttsOut.tokenTuples.remove(tt);
103 ttsOut.tokenTuples.add(
104 new TokenTuple(token, true, TokenTuple.ARITY_MANY).makeCanonical()
108 return ttsOut.makeCanonical();
112 public boolean equals(Object o) {
117 if( !(o instanceof TokenTupleSet) ) {
121 TokenTupleSet tts = (TokenTupleSet) o;
122 return tokenTuples.equals(tts.tokenTuples);
125 public int hashCode() {
126 return tokenTuples.hashCode();
130 // this should be a hash table so we can do this by key
131 public boolean containsToken(Integer token) {
132 assert token != null;
134 Iterator itr = tokenTuples.iterator();
135 while( itr.hasNext() ) {
136 TokenTuple tt = (TokenTuple) itr.next();
137 if( token.equals(tt.getToken() ) ) {
145 public TokenTupleSet ageTokens(AllocationSite as) {
148 TokenTupleSet ttsOut = new TokenTupleSet();
150 TokenTuple ttSummary = null;
151 boolean foundOldest = false;
153 Iterator itrT = this.iterator();
154 while( itrT.hasNext() ) {
155 TokenTuple tt = (TokenTuple) itrT.next();
157 Integer token = tt.getToken();
158 int age = as.getAge(token);
160 // summary tokens and tokens not associated with
161 // the site should be left alone
162 if( age == AllocationSite.AGE_notInThisSite ) {
163 ttsOut.tokenTuples.add(tt);
166 if( age == AllocationSite.AGE_summary ) {
167 // remember the summary tuple, but don't add it
168 // we may combine it with the oldest tuple
171 } else if( age == AllocationSite.AGE_oldest ) {
172 // found an oldest token, again just remember
177 // otherwise, we change this token to the
179 Integer tokenToChangeTo = as.getIthOldest(age + 1);
180 TokenTuple ttAged = tt.changeTokenTo(tokenToChangeTo);
181 ttsOut.tokenTuples.add(ttAged);
187 // there are four cases to consider here
188 // 1. we found a summary tuple and no oldest tuple
189 // Here we just pass the summary unchanged
190 // 2. we found an oldest tuple, no summary
191 // Make a new, arity-one summary tuple
192 // 3. we found both a summary and an oldest
193 // Merge them by increasing arity of summary
194 // 4. (not handled) we found neither, do nothing
195 if ( ttSummary != null && !foundOldest ) {
196 ttsOut.tokenTuples.add(ttSummary);
198 } else if( ttSummary == null && foundOldest ) {
199 ttsOut.tokenTuples.add(new TokenTuple(as.getSummary(),
201 TokenTuple.ARITY_ONE).makeCanonical() );
203 } else if( ttSummary != null && foundOldest ) {
204 ttsOut.tokenTuples.add(ttSummary.increaseArity() );
207 return ttsOut.makeCanonical();
211 public ReachabilitySet rewriteToken( TokenTuple tokenToRewrite,
212 ReachabilitySet replacements ) {
214 ReachabilitySet rsOut = new ReachabilitySet().makeCanonical();
216 if( !tokenTuples.contains( tokenToRewrite ) ) {
217 rsOut = rsOut.add( this );
220 TokenTupleSet ttsMinusToken = new TokenTupleSet( this );
221 ttsMinusToken.tokenTuples.remove( tokenToRewrite );
223 Iterator<TokenTupleSet> replaceItr = replacements.iterator();
224 while( replaceItr.hasNext() ) {
225 TokenTupleSet replacement = replaceItr.next();
226 TokenTupleSet replaced = new TokenTupleSet();
227 replaced.tokenTuples.addAll( ttsMinusToken.tokenTuples );
228 replaced.tokenTuples.addAll( replacement.tokenTuples );
229 replaced = replaced.makeCanonical();
230 rsOut = rsOut.add( replaced );
238 public String toString() {
239 return tokenTuples.toString();