1 package Analysis.OwnershipAnalysis;
9 public class ReachabilitySet extends Canonical {
11 private HashSet<TokenTupleSet> possibleReachabilities;
13 public ReachabilitySet() {
14 possibleReachabilities = new HashSet<TokenTupleSet>();
17 public ReachabilitySet(TokenTupleSet tts) {
20 possibleReachabilities.add(tts);
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() );
29 public ReachabilitySet(HashSet<TokenTupleSet> possibleReachabilities) {
30 assert possibleReachabilities != null;
31 this.possibleReachabilities = possibleReachabilities;
34 public ReachabilitySet(ReachabilitySet rs) {
36 // okay to clone, ReachabilitySet should be canonical
37 possibleReachabilities = (HashSet<TokenTupleSet>)rs.possibleReachabilities.clone();
41 public ReachabilitySet makeCanonical() {
42 return (ReachabilitySet) ReachabilitySet.makeCanonical(this);
45 public Iterator<TokenTupleSet> iterator() {
46 return possibleReachabilities.iterator();
51 return possibleReachabilities.size();
54 public boolean isEmpty() {
55 return possibleReachabilities.isEmpty();
58 public boolean contains(TokenTupleSet tts) {
60 return possibleReachabilities.contains(tts);
63 public boolean containsWithZeroes(TokenTupleSet tts) {
66 if( possibleReachabilities.contains(tts) ) {
70 Iterator itr = iterator();
71 while( itr.hasNext() ) {
72 TokenTupleSet ttsThis = (TokenTupleSet) itr.next();
73 if( ttsThis.containsWithZeroes(tts) ) {
82 public boolean containsSuperSet(TokenTupleSet tts) {
83 return containsSuperSet(tts, false);
86 public boolean containsStrictSuperSet(TokenTupleSet tts) {
87 return containsSuperSet(tts, true);
90 public boolean containsSuperSet(TokenTupleSet tts, boolean strict) {
93 if( !strict && possibleReachabilities.contains(tts) ) {
97 Iterator itr = iterator();
98 while( itr.hasNext() ) {
99 TokenTupleSet ttsThis = (TokenTupleSet) itr.next();
101 if( !tts.equals(ttsThis) && tts.isSubset(ttsThis) ) {
105 if( tts.isSubset(ttsThis) ) {
115 public boolean containsTuple(TokenTuple tt) {
116 Iterator itr = iterator();
117 while( itr.hasNext() ) {
118 TokenTupleSet tts = (TokenTupleSet) itr.next();
119 if( tts.containsTuple(tt) ) {
126 public boolean containsTupleSetWithBoth(TokenTuple tt1, TokenTuple tt2) {
127 Iterator itr = iterator();
128 while( itr.hasNext() ) {
129 TokenTupleSet tts = (TokenTupleSet) itr.next();
130 if( tts.containsTuple(tt1) && tts.containsTuple(tt2) ) {
137 public static ReachabilitySet factory(TokenTupleSet tts) {
138 CanonicalWrapper cw=new CanonicalWrapper(tts);
139 if (lookuphash.containsKey(cw))
140 return (ReachabilitySet)lookuphash.get(cw).b;
141 ReachabilitySet rs=new ReachabilitySet(tts);
142 rs=rs.makeCanonical();
144 lookuphash.put(cw,cw);
148 public ReachabilitySet union(TokenTupleSet ttsIn) {
149 ReachOperation ro=new ReachOperation(this, ttsIn);
150 if (unionhash.containsKey(ro)) {
151 return (ReachabilitySet) unionhash.get(ro).c;
153 ReachabilitySet rsOut = new ReachabilitySet(this);
154 rsOut.possibleReachabilities.add(ttsIn);
155 ro.c=rsOut=rsOut.makeCanonical();
156 unionhash.put(ro,ro);
162 public ReachabilitySet union(ReachabilitySet rsIn) {
163 // assert rsIn != null;
165 // assert can.containsKey(this);
166 // assert can.containsKey(rsIn);
168 ReachOperation ro=new ReachOperation(this, rsIn);
169 if (unionhash.containsKey(ro))
170 return (ReachabilitySet) unionhash.get(ro).c;
172 ReachabilitySet rsOut = new ReachabilitySet(this);
173 rsOut.possibleReachabilities.addAll(rsIn.possibleReachabilities);
174 ro.c=rsOut=rsOut.makeCanonical();
175 unionhash.put(ro, ro);
180 public ReachabilitySet intersection(ReachabilitySet rsIn) {
181 // assert rsIn != null;
183 // assert can.containsKey(this);
184 // assert can.containsKey(rsIn);
186 ReachOperation ro=new ReachOperation(this, rsIn);
187 if (interhash.containsKey(ro))
188 return (ReachabilitySet) interhash.get(ro).c;
190 ReachabilitySet rsOut = new ReachabilitySet();
191 Iterator i = this.iterator();
192 while( i.hasNext() ) {
193 TokenTupleSet tts = (TokenTupleSet) i.next();
194 if( rsIn.possibleReachabilities.contains(tts) ) {
195 rsOut.possibleReachabilities.add(tts);
198 ro.c=rsOut=rsOut.makeCanonical();
199 interhash.put(ro,ro);
205 public ReachabilitySet add(TokenTupleSet tts) {
210 public ReachabilitySet remove(TokenTupleSet tts) {
212 ReachabilitySet rsOut = new ReachabilitySet(this);
213 assert rsOut.possibleReachabilities.remove(tts);
214 return rsOut.makeCanonical();
217 public ReachabilitySet removeTokenAIfTokenB(TokenTuple ttA,
222 ReachabilitySet rsOut = new ReachabilitySet();
224 Iterator i = this.iterator();
225 while( i.hasNext() ) {
226 TokenTupleSet tts = (TokenTupleSet) i.next();
227 if( tts.containsTuple(ttB) ) {
228 rsOut.possibleReachabilities.add(tts.remove(ttA) );
230 rsOut.possibleReachabilities.add(tts);
234 return rsOut.makeCanonical();
238 public ReachabilitySet applyChangeSet(ChangeTupleSet C, boolean keepSourceState) {
241 ReachabilitySet rsOut = new ReachabilitySet();
243 Iterator i = this.iterator();
244 while( i.hasNext() ) {
245 TokenTupleSet tts = (TokenTupleSet) i.next();
247 boolean changeFound = false;
249 Iterator<ChangeTuple> itrC = C.iterator();
250 while( itrC.hasNext() ) {
251 ChangeTuple c = itrC.next();
253 if( tts.equals(c.getSetToMatch() ) ) {
254 rsOut.possibleReachabilities.add(c.getSetToAdd() );
259 if( keepSourceState || !changeFound ) {
260 rsOut.possibleReachabilities.add(tts);
264 return rsOut.makeCanonical();
268 public ChangeTupleSet unionUpArityToChangeSet(ReachabilitySet rsIn) {
271 ChangeTupleSet ctsOut = new ChangeTupleSet();
273 Iterator itrO = this.iterator();
274 while( itrO.hasNext() ) {
275 TokenTupleSet o = (TokenTupleSet) itrO.next();
277 Iterator itrR = rsIn.iterator();
278 while( itrR.hasNext() ) {
279 TokenTupleSet r = (TokenTupleSet) itrR.next();
281 TokenTupleSet theUnion = new TokenTupleSet().makeCanonical();
283 Iterator itrRelement = r.iterator();
284 while( itrRelement.hasNext() ) {
285 TokenTuple ttR = (TokenTuple) itrRelement.next();
286 TokenTuple ttO = o.containsToken(ttR.getToken() );
289 theUnion = theUnion.union((new TokenTupleSet(ttR.unionArity(ttO)).makeCanonical() ) );
291 theUnion = theUnion.union((new TokenTupleSet(ttR)).makeCanonical() );
295 Iterator itrOelement = o.iterator();
296 while( itrOelement.hasNext() ) {
297 TokenTuple ttO = (TokenTuple) itrOelement.next();
298 TokenTuple ttR = theUnion.containsToken(ttO.getToken() );
301 theUnion = theUnion.union(new TokenTupleSet(ttO).makeCanonical() );
305 if( !theUnion.isEmpty() ) {
306 ctsOut = ctsOut.union((new ChangeTupleSet(new ChangeTuple(o, theUnion) )).makeCanonical() );
311 return ctsOut.makeCanonical();
315 public ReachabilitySet ageTokens(AllocationSite as) {
318 ReachabilitySet rsOut = new ReachabilitySet();
320 Iterator itrS = this.iterator();
321 while( itrS.hasNext() ) {
322 TokenTupleSet tts = (TokenTupleSet) itrS.next();
323 rsOut.possibleReachabilities.add(tts.ageTokens(as) );
326 return rsOut.makeCanonical();
330 public ReachabilitySet unshadowTokens(AllocationSite as) {
333 ReachabilitySet rsOut = new ReachabilitySet();
335 Iterator itrS = this.iterator();
336 while( itrS.hasNext() ) {
337 TokenTupleSet tts = (TokenTupleSet) itrS.next();
338 rsOut.possibleReachabilities.add(tts.unshadowTokens(as) );
341 return rsOut.makeCanonical();
345 public ReachabilitySet toShadowTokens(AllocationSite as) {
348 ReachabilitySet rsOut = new ReachabilitySet();
350 Iterator itrS = this.iterator();
351 while( itrS.hasNext() ) {
352 TokenTupleSet tts = (TokenTupleSet) itrS.next();
353 rsOut.possibleReachabilities.add(tts.toShadowTokens(as) );
356 return rsOut.makeCanonical();
360 public ReachabilitySet pruneBy(ReachabilitySet rsIn) {
363 ReachabilitySet rsOut = new ReachabilitySet();
365 Iterator itrB = this.iterator();
366 while( itrB.hasNext() ) {
367 TokenTupleSet ttsB = (TokenTupleSet) itrB.next();
369 boolean subsetExists = false;
371 Iterator itrA = rsIn.iterator();
372 while( itrA.hasNext() && !subsetExists ) {
373 TokenTupleSet ttsA = (TokenTupleSet) itrA.next();
375 if( ttsA.isSubset(ttsB) ) {
381 rsOut.possibleReachabilities.add(ttsB);
385 return rsOut.makeCanonical();
389 public ReachabilitySet exhaustiveArityCombinations() {
390 ReachabilitySet rsOut = (new ReachabilitySet()).makeCanonical();
392 int numDimensions = this.possibleReachabilities.size();
394 if( numDimensions > 3 ) {
395 // for problems that are too big, punt and use less
396 // precise arity for reachability information
397 TokenTupleSet ttsImprecise = new TokenTupleSet().makeCanonical();
399 Iterator<TokenTupleSet> itrThis = this.iterator();
400 while( itrThis.hasNext() ) {
401 TokenTupleSet ttsUnit = itrThis.next();
402 ttsImprecise = ttsImprecise.unionUpArity(ttsUnit.makeArityZeroOrMore() );
405 //rsOut = this.union( ttsImprecise );
406 rsOut = rsOut.union(ttsImprecise);
410 // add an extra digit to detect termination
411 int[] digits = new int[numDimensions+1];
416 // start with the minimum possible coordinate
417 for( int i = 0; i < numDimensions+1; ++i ) {
418 digits[i] = minArity;
421 // and stop when the highest-ordered axis rolls above the minimum
422 while( digits[numDimensions] == minArity ) {
424 // spit out a "coordinate" made from these digits
425 TokenTupleSet ttsCoordinate = new TokenTupleSet().makeCanonical();
426 Iterator<TokenTupleSet> ttsItr = this.iterator();
427 for( int i = 0; i < numDimensions; ++i ) {
428 assert ttsItr.hasNext();
429 TokenTupleSet ttsUnit = ttsItr.next();
430 for( int j = 0; j < digits[i]; ++j ) {
431 ttsCoordinate = ttsCoordinate.unionUpArity(ttsUnit);
434 rsOut = rsOut.add(ttsCoordinate.makeCanonical() );
437 for( int i = 0; i < numDimensions+1; ++i ) {
440 if( digits[i] > maxArity ) {
441 // this axis reached its max, so roll it back to min and increment next higher digit
442 digits[i] = minArity;
445 // this axis did not reach its max so we just enumerated a new unique coordinate, stop
451 return rsOut.makeCanonical();
455 public boolean equals(Object o) {
460 if( !(o instanceof ReachabilitySet) ) {
464 ReachabilitySet rs = (ReachabilitySet) o;
465 return possibleReachabilities.equals(rs.possibleReachabilities);
469 private boolean oldHashSet = false;
470 private int oldHash = 0;
471 public int hashCode() {
472 int currentHash = possibleReachabilities.hashCode();
474 if( oldHashSet == false ) {
475 oldHash = currentHash;
478 if( oldHash != currentHash ) {
479 System.out.println("IF YOU SEE THIS A CANONICAL ReachabilitySet CHANGED");
489 public String toStringEscapeNewline(boolean hideSubsetReachability) {
492 Iterator<TokenTupleSet> i = this.iterator();
493 while( i.hasNext() ) {
494 TokenTupleSet tts = i.next();
496 // skip this if there is a superset already
497 if( hideSubsetReachability &&
498 containsStrictSuperSet(tts) ) {
513 public String toString() {
514 return toString(false);
517 public String toString(boolean hideSubsetReachability) {
520 Iterator<TokenTupleSet> i = this.iterator();
521 while( i.hasNext() ) {
522 TokenTupleSet tts = i.next();
524 // skip this if there is a superset already
525 if( hideSubsetReachability &&
526 containsStrictSuperSet(tts) ) {