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) Canonical.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 containsTuple(TokenTuple tt) {
64 Iterator itr = iterator();
65 while( itr.hasNext() ) {
66 TokenTupleSet tts = (TokenTupleSet) itr.next();
67 if( tts.containsTuple(tt) ) {
74 public boolean containsTupleSetWithBoth(TokenTuple tt1, TokenTuple tt2) {
75 Iterator itr = iterator();
76 while( itr.hasNext() ) {
77 TokenTupleSet tts = (TokenTupleSet) itr.next();
78 if( tts.containsTuple(tt1) && tts.containsTuple(tt2) ) {
85 public ReachabilitySet union(ReachabilitySet rsIn) {
88 ReachabilitySet rsOut = new ReachabilitySet(this);
89 rsOut.possibleReachabilities.addAll(rsIn.possibleReachabilities);
90 return rsOut.makeCanonical();
93 public ReachabilitySet union(TokenTupleSet ttsIn) {
96 ReachabilitySet rsOut = new ReachabilitySet(this);
97 rsOut.possibleReachabilities.add(ttsIn);
98 return rsOut.makeCanonical();
101 public ReachabilitySet intersection(ReachabilitySet rsIn) {
104 ReachabilitySet rsOut = new ReachabilitySet();
106 Iterator i = this.iterator();
107 while( i.hasNext() ) {
108 TokenTupleSet tts = (TokenTupleSet) i.next();
109 if( rsIn.possibleReachabilities.contains(tts) ) {
110 rsOut.possibleReachabilities.add(tts);
114 return rsOut.makeCanonical();
118 public ReachabilitySet add(TokenTupleSet tts) {
120 ReachabilitySet rsOut = new ReachabilitySet(tts);
121 return rsOut.union(this);
125 public ChangeTupleSet unionUpArityToChangeSet(ReachabilitySet rsIn) {
128 ChangeTupleSet ctsOut = new ChangeTupleSet();
130 Iterator itrO = this.iterator();
131 while( itrO.hasNext() ) {
132 TokenTupleSet o = (TokenTupleSet) itrO.next();
134 Iterator itrR = rsIn.iterator();
135 while( itrR.hasNext() ) {
136 TokenTupleSet r = (TokenTupleSet) itrR.next();
138 TokenTupleSet theUnion = new TokenTupleSet().makeCanonical();
140 Iterator itrRelement = r.iterator();
141 while( itrRelement.hasNext() ) {
142 TokenTuple ttR = (TokenTuple) itrRelement.next();
143 TokenTuple ttO = o.containsToken(ttR.getToken() );
146 theUnion = theUnion.union(new TokenTupleSet(ttR.unionArity(ttO) ) ).makeCanonical();
148 theUnion = theUnion.union(new TokenTupleSet(ttR) ).makeCanonical();
152 Iterator itrOelement = o.iterator();
153 while( itrOelement.hasNext() ) {
154 TokenTuple ttO = (TokenTuple) itrOelement.next();
155 TokenTuple ttR = theUnion.containsToken(ttO.getToken() );
158 theUnion = theUnion.union(new TokenTupleSet(ttO) ).makeCanonical();
162 if( !theUnion.isEmpty() ) {
163 ctsOut = ctsOut.union(new ChangeTupleSet(new ChangeTuple(o, theUnion) ) );
168 return ctsOut.makeCanonical();
172 public ReachabilitySet ageTokens(AllocationSite as) {
175 ReachabilitySet rsOut = new ReachabilitySet();
177 Iterator itrS = this.iterator();
178 while( itrS.hasNext() ) {
179 TokenTupleSet tts = (TokenTupleSet) itrS.next();
180 rsOut.possibleReachabilities.add(tts.ageTokens(as) );
183 return rsOut.makeCanonical();
187 public ReachabilitySet unshadowTokens(AllocationSite as) {
190 ReachabilitySet rsOut = new ReachabilitySet();
192 Iterator itrS = this.iterator();
193 while( itrS.hasNext() ) {
194 TokenTupleSet tts = (TokenTupleSet) itrS.next();
195 rsOut.possibleReachabilities.add(tts.unshadowTokens(as) );
198 return rsOut.makeCanonical();
202 public ReachabilitySet toShadowTokens(AllocationSite as) {
205 ReachabilitySet rsOut = new ReachabilitySet();
207 Iterator itrS = this.iterator();
208 while( itrS.hasNext() ) {
209 TokenTupleSet tts = (TokenTupleSet) itrS.next();
210 rsOut.possibleReachabilities.add(tts.toShadowTokens(as) );
213 return rsOut.makeCanonical();
217 public ReachabilitySet pruneBy(ReachabilitySet rsIn) {
220 ReachabilitySet rsOut = new ReachabilitySet();
222 Iterator itrB = this.iterator();
223 while( itrB.hasNext() ) {
224 TokenTupleSet ttsB = (TokenTupleSet) itrB.next();
226 boolean subsetExists = false;
228 Iterator itrA = rsIn.iterator();
229 while( itrA.hasNext() && !subsetExists ) {
230 TokenTupleSet ttsA = (TokenTupleSet) itrA.next();
232 if( ttsA.isSubset(ttsB) ) {
238 rsOut.possibleReachabilities.add(ttsB);
242 return rsOut.makeCanonical();
246 public ReachabilitySet exhaustiveArityCombinations() {
247 ReachabilitySet rsOut = new ReachabilitySet();
249 int numDimensions = this.possibleReachabilities.size();
251 if( numDimensions > 1 ) {
252 // for problems that are too big, punt and use less
253 // precise arity for reachability information
254 TokenTupleSet ttsImprecise = new TokenTupleSet().makeCanonical();
256 Iterator<TokenTupleSet> itrThis = this.iterator();
257 while( itrThis.hasNext() ) {
258 TokenTupleSet ttsUnit = itrThis.next();
259 ttsImprecise = ttsImprecise.unionUpArity(ttsUnit.makeArityZeroOrMore() );
262 //rsOut = this.union( ttsImprecise );
263 rsOut = rsOut.union(ttsImprecise);
267 // add an extra digit to detect termination
268 int[] digits = new int[numDimensions+1];
273 // start with the minimum possible coordinate
274 for( int i = 0; i < numDimensions+1; ++i ) {
275 digits[i] = minArity;
278 // and stop when the highest-ordered axis rolls above the minimum
279 while( digits[numDimensions] == minArity ) {
281 // spit out a "coordinate" made from these digits
282 TokenTupleSet ttsCoordinate = new TokenTupleSet().makeCanonical();
283 Iterator<TokenTupleSet> ttsItr = this.iterator();
284 for( int i = 0; i < numDimensions; ++i ) {
285 assert ttsItr.hasNext();
286 TokenTupleSet ttsUnit = ttsItr.next();
287 for( int j = 0; j < digits[i]; ++j ) {
288 ttsCoordinate = ttsCoordinate.unionUpArity(ttsUnit);
291 rsOut = rsOut.add(ttsCoordinate.makeCanonical() );
294 for( int i = 0; i < numDimensions+1; ++i ) {
297 if( digits[i] > maxArity ) {
298 // this axis reached its max, so roll it back to min and increment next higher digit
299 digits[i] = minArity;
302 // this axis did not reach its max so we just enumerated a new unique coordinate, stop
308 return rsOut.makeCanonical();
312 public boolean equals(Object o) {
317 if( !(o instanceof ReachabilitySet) ) {
321 ReachabilitySet rs = (ReachabilitySet) o;
322 return possibleReachabilities.equals(rs.possibleReachabilities);
326 private boolean oldHashSet = false;
327 private int oldHash = 0;
328 public int hashCode() {
329 int currentHash = possibleReachabilities.hashCode();
331 if( oldHashSet == false ) {
332 oldHash = currentHash;
335 if( oldHash != currentHash ) {
336 System.out.println("IF YOU SEE THIS A CANONICAL ReachabilitySet CHANGED");
346 public String toStringEscapeNewline() {
349 Iterator i = this.iterator();
350 while( i.hasNext() ) {
361 public String toString() {
364 Iterator i = this.iterator();
365 while( i.hasNext() ) {