1 package Analysis.OwnershipAnalysis;
9 public class ReachabilitySet extends Canonical {
11 private HashSet<TokenTupleSet> possibleReachabilities;
13 public ReachabilitySet() {
14 possibleReachabilities = new HashSet<TokenTupleSet>();
15 //TokenTupleSet ttsEmpty = new TokenTupleSet().makeCanonical();
16 //possibleReachabilities.add( ttsEmpty );
19 public ReachabilitySet( TokenTupleSet tts ) {
22 possibleReachabilities.add( tts );
25 public ReachabilitySet( TokenTuple tt ) {
26 this( new TokenTupleSet( tt ).makeCanonical() );
29 public ReachabilitySet( HashSet<TokenTupleSet> possibleReachabilities ) {
30 this.possibleReachabilities = possibleReachabilities;
33 public ReachabilitySet( ReachabilitySet rs ) {
35 possibleReachabilities = (HashSet<TokenTupleSet>) rs.possibleReachabilities.clone(); // again, DEEP COPY?!
38 public ReachabilitySet makeCanonical() {
39 return (ReachabilitySet) Canonical.makeCanonical( this );
42 public boolean contains( TokenTupleSet tts ) {
44 return possibleReachabilities.contains( tts );
47 public ReachabilitySet add( TokenTupleSet tts ) {
48 ReachabilitySet rsOut = new ReachabilitySet( tts );
49 return this.union( rsOut );
52 public ReachabilitySet increaseArity( Integer token ) {
55 HashSet<TokenTupleSet> possibleReachabilitiesNew = new HashSet<TokenTupleSet>();
57 Iterator itr = iterator();
58 while( itr.hasNext() ) {
59 TokenTupleSet tts = (TokenTupleSet) itr.next();
60 possibleReachabilitiesNew.add( tts.increaseArity( token ) );
63 return new ReachabilitySet( possibleReachabilitiesNew ).makeCanonical();
66 public Iterator iterator() {
67 return possibleReachabilities.iterator();
70 public ReachabilitySet union( ReachabilitySet rsIn ) {
73 ReachabilitySet rsOut = new ReachabilitySet( this );
74 rsOut.possibleReachabilities.addAll( rsIn.possibleReachabilities );
75 return rsOut.makeCanonical();
78 public ReachabilitySet union( TokenTupleSet ttsIn ) {
81 ReachabilitySet rsOut = new ReachabilitySet( this );
82 rsOut.possibleReachabilities.add( ttsIn );
83 return rsOut.makeCanonical();
86 public ReachabilitySet intersection( ReachabilitySet rsIn ) {
89 ReachabilitySet rsOut = new ReachabilitySet();
91 Iterator i = this.iterator();
92 while( i.hasNext() ) {
93 TokenTupleSet tts = (TokenTupleSet) i.next();
94 if( rsIn.possibleReachabilities.contains( tts ) ) {
95 rsOut.possibleReachabilities.add( tts );
99 return rsOut.makeCanonical();
103 public ReachabilitySet unionUpArity( ReachabilitySet rsIn ) {
106 ReachabilitySet rsOut = new ReachabilitySet();
110 itrIn = rsIn.iterator();
111 while( itrIn.hasNext() ) {
112 TokenTupleSet ttsIn = (TokenTupleSet) itrIn.next();
114 boolean foundEqual = false;
116 itrThis = this.iterator();
117 while( itrThis.hasNext() ) {
118 TokenTupleSet ttsThis = (TokenTupleSet) itrThis.next();
120 if( ttsIn.equalWithoutArity( ttsThis ) ) {
121 rsOut.possibleReachabilities.add( ttsIn.unionUpArity( ttsThis ) );
128 rsOut.possibleReachabilities.add( ttsIn );
132 itrThis = this.iterator();
133 while( itrThis.hasNext() ) {
134 TokenTupleSet ttsThis = (TokenTupleSet) itrThis.next();
136 boolean foundEqual = false;
138 itrIn = rsIn.iterator();
139 while( itrIn.hasNext() ) {
140 TokenTupleSet ttsIn = (TokenTupleSet) itrIn.next();
142 if( ttsThis.equalWithoutArity( ttsIn ) ) {
149 rsOut.possibleReachabilities.add( ttsThis );
153 return rsOut.makeCanonical();
157 public ChangeTupleSet unionUpArityToChangeSet( ReachabilitySet rsIn ) {
160 ChangeTupleSet ctsOut = new ChangeTupleSet();
162 Iterator itrO = this.iterator();
163 while( itrO.hasNext() ) {
164 TokenTupleSet o = (TokenTupleSet) itrO.next();
166 Iterator itrR = rsIn.iterator();
167 while( itrR.hasNext() ) {
168 TokenTupleSet r = (TokenTupleSet) itrR.next();
170 TokenTupleSet theUnion = new TokenTupleSet();
172 Iterator itrRelement = r.iterator();
173 while( itrRelement.hasNext() ) {
174 TokenTuple e = (TokenTuple) itrRelement.next();
176 if( o.containsToken( e.getToken() ) ) {
177 theUnion = theUnion.union( new TokenTupleSet( e.increaseArity() ) ).makeCanonical();
179 theUnion = theUnion.union( new TokenTupleSet( e ) ).makeCanonical();
183 Iterator itrOelement = o.iterator();
184 while( itrOelement.hasNext() ) {
185 TokenTuple e = (TokenTuple) itrOelement.next();
187 if( !theUnion.containsToken( e.getToken() ) ) {
188 theUnion = theUnion.union( new TokenTupleSet( e ) ).makeCanonical();
192 if( !theUnion.isEmpty() ) {
193 ctsOut = ctsOut.union(
194 new ChangeTupleSet( new ChangeTuple( o, theUnion ) )
200 return ctsOut.makeCanonical();
204 public ReachabilitySet ageTokens( AllocationSite as ) {
207 ReachabilitySet rsOut = new ReachabilitySet();
209 Iterator itrS = this.iterator();
210 while( itrS.hasNext() ) {
211 TokenTupleSet tts = (TokenTupleSet) itrS.next();
212 rsOut.possibleReachabilities.add( tts.ageTokens( as ) );
215 return rsOut.makeCanonical();
219 public ReachabilitySet pruneBy( ReachabilitySet rsIn ) {
222 ReachabilitySet rsOut = new ReachabilitySet();
224 Iterator itrB = this.iterator();
225 while( itrB.hasNext() ) {
226 TokenTupleSet ttsB = (TokenTupleSet) itrB.next();
228 boolean subsetExists = false;
230 Iterator itrA = rsIn.iterator();
231 while( itrA.hasNext() && !subsetExists ) {
232 TokenTupleSet ttsA = (TokenTupleSet) itrA.next();
234 if( ttsA.isSubset( ttsB ) ) {
236 rsOut.possibleReachabilities.add( ttsB );
241 return rsOut.makeCanonical();
245 public boolean equals( Object o ) {
250 if( !(o instanceof ReachabilitySet) ) {
254 ReachabilitySet rs = (ReachabilitySet) o;
255 return possibleReachabilities.equals( rs.possibleReachabilities );
258 public int hashCode() {
259 return possibleReachabilities.hashCode();
263 public String toStringEscapeNewline() {
266 Iterator i = this.iterator();
267 while( i.hasNext() ) {
278 public String toString() {
281 Iterator i = this.iterator();
282 while( i.hasNext() ) {