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();
50 public boolean contains(TokenTupleSet tts) {
52 return possibleReachabilities.contains(tts);
55 public boolean containsTuple(TokenTuple tt) {
56 Iterator itr = iterator();
57 while( itr.hasNext() ) {
58 TokenTupleSet tts = (TokenTupleSet) itr.next();
59 if( tts.containsTuple(tt) ) {
67 public ReachabilitySet increaseArity(Integer token) {
70 HashSet<TokenTupleSet> possibleReachabilitiesNew = new HashSet<TokenTupleSet>();
72 Iterator itr = iterator();
73 while( itr.hasNext() ) {
74 TokenTupleSet tts = (TokenTupleSet) itr.next();
75 possibleReachabilitiesNew.add(tts.increaseArity(token) );
78 return new ReachabilitySet(possibleReachabilitiesNew).makeCanonical();
82 public ReachabilitySet union(ReachabilitySet rsIn) {
85 ReachabilitySet rsOut = new ReachabilitySet(this);
86 rsOut.possibleReachabilities.addAll(rsIn.possibleReachabilities);
87 return rsOut.makeCanonical();
90 public ReachabilitySet union(TokenTupleSet ttsIn) {
93 ReachabilitySet rsOut = new ReachabilitySet(this);
94 rsOut.possibleReachabilities.add(ttsIn);
95 return rsOut.makeCanonical();
98 public ReachabilitySet intersection(ReachabilitySet rsIn) {
101 ReachabilitySet rsOut = new ReachabilitySet();
103 Iterator i = this.iterator();
104 while( i.hasNext() ) {
105 TokenTupleSet tts = (TokenTupleSet) i.next();
106 if( rsIn.possibleReachabilities.contains(tts) ) {
107 rsOut.possibleReachabilities.add(tts);
111 return rsOut.makeCanonical();
115 public ReachabilitySet add(TokenTupleSet tts) {
117 ReachabilitySet rsOut = new ReachabilitySet(tts);
118 return rsOut.union(this);
122 public ChangeTupleSet unionUpArityToChangeSet(ReachabilitySet rsIn) {
125 ChangeTupleSet ctsOut = new ChangeTupleSet();
127 Iterator itrO = this.iterator();
128 while( itrO.hasNext() ) {
129 TokenTupleSet o = (TokenTupleSet) itrO.next();
131 Iterator itrR = rsIn.iterator();
132 while( itrR.hasNext() ) {
133 TokenTupleSet r = (TokenTupleSet) itrR.next();
135 TokenTupleSet theUnion = new TokenTupleSet();
137 Iterator itrRelement = r.iterator();
138 while( itrRelement.hasNext() ) {
139 TokenTuple e = (TokenTuple) itrRelement.next();
141 if( o.containsToken(e.getToken() ) ) {
142 theUnion = theUnion.union(new TokenTupleSet(e.increaseArity() ) ).makeCanonical();
144 theUnion = theUnion.union(new TokenTupleSet(e) ).makeCanonical();
148 Iterator itrOelement = o.iterator();
149 while( itrOelement.hasNext() ) {
150 TokenTuple e = (TokenTuple) itrOelement.next();
152 if( !theUnion.containsToken(e.getToken() ) ) {
153 theUnion = theUnion.union(new TokenTupleSet(e) ).makeCanonical();
157 if( !theUnion.isEmpty() ) {
158 ctsOut = ctsOut.union(
159 new ChangeTupleSet(new ChangeTuple(o, theUnion) )
165 return ctsOut.makeCanonical();
169 public ReachabilitySet ageTokens(AllocationSite as) {
172 ReachabilitySet rsOut = new ReachabilitySet();
174 Iterator itrS = this.iterator();
175 while( itrS.hasNext() ) {
176 TokenTupleSet tts = (TokenTupleSet) itrS.next();
177 rsOut.possibleReachabilities.add( tts.ageTokens(as) );
180 return rsOut.makeCanonical();
184 public ReachabilitySet unshadowTokens(AllocationSite as) {
187 ReachabilitySet rsOut = new ReachabilitySet();
189 Iterator itrS = this.iterator();
190 while( itrS.hasNext() ) {
191 TokenTupleSet tts = (TokenTupleSet) itrS.next();
192 rsOut.possibleReachabilities.add( tts.unshadowTokens(as) );
195 return rsOut.makeCanonical();
199 public ReachabilitySet toShadowTokens(AllocationSite as) {
202 ReachabilitySet rsOut = new ReachabilitySet();
204 Iterator itrS = this.iterator();
205 while( itrS.hasNext() ) {
206 TokenTupleSet tts = (TokenTupleSet) itrS.next();
207 rsOut.possibleReachabilities.add( tts.toShadowTokens(as) );
210 return rsOut.makeCanonical();
214 public ReachabilitySet pruneBy(ReachabilitySet rsIn) {
217 ReachabilitySet rsOut = new ReachabilitySet();
219 Iterator itrB = this.iterator();
220 while( itrB.hasNext() ) {
221 TokenTupleSet ttsB = (TokenTupleSet) itrB.next();
223 boolean subsetExists = false;
225 Iterator itrA = rsIn.iterator();
226 while( itrA.hasNext() && !subsetExists ) {
227 TokenTupleSet ttsA = (TokenTupleSet) itrA.next();
229 if( ttsA.isSubset(ttsB) ) {
235 rsOut.possibleReachabilities.add(ttsB);
239 return rsOut.makeCanonical();
243 public ReachabilitySet exhaustiveArityCombinations() {
244 ReachabilitySet rsOut = new ReachabilitySet();
246 int numDimensions = this.possibleReachabilities.size();
248 // add an extra digit to detect termination
249 int[] digits = new int[numDimensions+1];
254 // start with the minimum possible coordinate
255 for( int i = 0; i < numDimensions+1; ++i ) {
256 digits[i] = minArity;
259 // and stop when the highest-ordered axis rolls above the minimum
260 while( digits[numDimensions] == minArity ) {
262 // spit out a "coordinate" made from these digits
263 TokenTupleSet ttsCoordinate = new TokenTupleSet();
264 Iterator<TokenTupleSet> ttsItr = this.iterator();
265 for( int i = 0; i < numDimensions; ++i ) {
266 assert ttsItr.hasNext();
267 TokenTupleSet ttsUnit = ttsItr.next();
268 for( int j = 0; j < digits[i]; ++j ) {
269 ttsCoordinate = ttsCoordinate.unionUpArity( ttsUnit );
272 rsOut = rsOut.add( ttsCoordinate.makeCanonical() );
275 for( int i = 0; i < numDimensions+1; ++i ) {
277 if( digits[i] > maxArity ) {
278 // this axis reached its max, so roll it back to min and increment next higher digit
279 digits[i] = minArity;
282 // this axis did not reach its max so we just enumerated a new unique coordinate, stop
288 return rsOut.makeCanonical();
292 public boolean equals(Object o) {
297 if( !(o instanceof ReachabilitySet) ) {
301 ReachabilitySet rs = (ReachabilitySet) o;
302 return possibleReachabilities.equals(rs.possibleReachabilities);
305 public int hashCode() {
306 return possibleReachabilities.hashCode();
310 public String toStringEscapeNewline() {
313 Iterator i = this.iterator();
314 while( i.hasNext() ) {
325 public String toString() {
328 Iterator i = this.iterator();
329 while( i.hasNext() ) {