1 package Analysis.Disjoint;
11 public class DefiniteReachState {
15 // Maps two variables to an edge (x, y, e) to an unused value when the
16 // object of x is already reachable from the object of y, and the
17 // set of edges conservatively gives the path.
18 // NOTE: Use EdgeKey instead of edges because this analysis's
19 // scope is beyond the scope of a single reach graph.
20 private static MultiViewMapBuilder<Object> RBuilder;
21 private static BitSet viewRfull;
22 private static BitSet viewR0;
23 private static BitSet viewR1;
24 private static BitSet viewR2;
25 private static BitSet viewR01;
26 private MultiViewMap<Object> R;
30 // Tracks whether the analysis must know the definite reachability
31 // information of a given variable.
32 //private enum DefReachKnown {
36 //private Map<TempDescriptor, DefReachKnown> Rs;
41 // Maps a variable that points to object o0 to the
42 // set of variables that point to objects o1...oN
43 // that have a reference to o0.
44 //private static MultiViewMapBuilder<Object> FuBuilder;
45 //private static BitSet viewFu0;
46 //private static BitSet viewFu1;
47 //private MultiViewMap<Object> Fu;
57 // call before instantiating this class
58 static public void initBuilders() {
60 new MultiViewMapBuilder<Object>( new Class[] {
65 viewRfull = RBuilder.getFullView();
66 viewR0 = RBuilder.addPartialView( 0 );
67 viewR1 = RBuilder.addPartialView( 1 );
68 viewR2 = RBuilder.addPartialView( 2 );
69 viewR01 = RBuilder.addPartialView( 0, 1 );
70 RBuilder.setCheckTypes( true );
71 RBuilder.setCheckConsistency( true );
74 // new MultiViewMapBuilder<Object>( new Class[] {
75 // TempDescriptor.class,
76 // DefReachFuVal.class},
78 //viewFu0 = FuBuilder.addPartialView( 0 );
79 //viewFu1 = FuBuilder.addPartialView( 1 );
80 //FuBuilder.setCheckTypes( true );
81 //FuBuilder.setCheckConsistency( true );
86 public DefiniteReachState( DefiniteReachState toCopy ) {
87 this.R = toCopy.R.clone( RBuilder );
91 public DefiniteReachState() {
93 //Rs = new HashMap<TempDescriptor, DefReachKnown>();
95 //Fu = FuBuilder.build();
99 public void methodEntry( Set<TempDescriptor> parameters ) {
100 methodEntryR( parameters );
103 //for( TempDescriptor p : parameters ) {
104 // Rs.put( p, DefReachKnown.UNKNOWN );
107 //Fu = FuBuilder.build();
110 public void copy( TempDescriptor x,
114 // Rs' := (Rs - <x,*>) U {<x,v> | <y,v> in Rs}
115 //DefReachKnown valRs = Rs.get( y );
116 //assert( valRs != null );
117 //Rs.put( x, valRs );
119 // Fu' := (Fu - <x, *> - <*, x>) U
120 // {<x,v> | <y,v> in Fu} U
121 // {<v,x> | <v,y> in Fu} U
122 // {<z, unknown> | <z,<x>> in Fu}
123 //Fu.remove( viewFu0, MultiKey.factory( x ) );
124 //Fu.remove( viewFu1, MultiKey.factory( x ) );
125 //for( MultiKey key : Fu.get( viewFu0, MultiKey.factory( y ) ).keySet() ) {
126 // DefReachFuVal val = (DefReachFuVal) key.get( 1 );
127 // Fu.put( MultiKey.factory( x, val ), dummy );
129 //for( MultiKey key : Fu.get( viewFu1, MultiKey.factory( y ) ).keySet() ) {
130 // TempDescriptor v = (TempDescriptor) key.get( 0 );
131 // Fu.put( MultiKey.factory( v, DefReachFuVal.factory( x ) ), dummy );
133 //for( MultiKey key :
135 // MultiKey.factory( DefReachFuVal.factory( DefReachFuVal.Val.UNKNOWN ) )
138 // TempDescriptor z = (TempDescriptor) key.get( 0 );
139 // Fu.put( MultiKey.factory( z, DefReachFuVal.factory( x ) ), dummy );
143 public void load( TempDescriptor x,
146 Set<EdgeKey> edgeKeysForLoad ) {
148 loadR( x, y, f, edgeKeysForLoad );
149 // Rs' := (Rs - <x,*>) U {<x, unknown>}
150 //Rs.put( x, DefReachKnown.UNKNOWN );
153 public void store( TempDescriptor x,
156 Set<EdgeKey> edgeKeysRemoved,
157 Set<EdgeKey> edgeKeysAdded ) {
159 storeR( x, f, y, edgeKeysRemoved, edgeKeysAdded );
163 public void newObject( TempDescriptor x ) {
166 // Rs' := (Rs - <x,*>) U {<x, new>}
167 //Rs.put( x, DefReachKnown.KNOWN );
171 public void methodCall( TempDescriptor retVal ) {
172 methodCallR( retVal );
174 // Rs' := (Rs - <x,*>) U {<x, unknown>}
175 //Rs.put( x, DefReachKnown.UNKNOWN );
178 public void merge( DefiniteReachState that ) {
181 // Rs' := <x, new> iff in all incoming edges, otherwie <x, unknown>
190 public void methodEntryR( Set<TempDescriptor> parameters ) {
194 public void copyR( TempDescriptor x,
196 // consider that x and y can be the same, so do the
197 // parts of the update in the right order:
199 // first get all info for update
200 MultiKey keyY = MultiKey.factory( y );
201 Map<MultiKey, Object> mapY0 = R.get( viewR0, keyY );
202 Map<MultiKey, Object> mapY1 = R.get( viewR1, keyY );
204 // then remove anything
205 MultiKey keyX = MultiKey.factory( x );
206 R.remove( viewR0, keyX );
207 R.remove( viewR1, keyX );
209 // then insert new stuff
210 for( MultiKey fullKeyY : mapY0.keySet() ) {
211 MultiKey fullKeyX = MultiKey.factory( x,
214 R.put( fullKeyX, MultiViewMap.dummyValue );
216 for( MultiKey fullKeyY : mapY1.keySet() ) {
217 MultiKey fullKeyX = MultiKey.factory( fullKeyY.get( 0 ),
220 R.put( fullKeyX, MultiViewMap.dummyValue );
224 public void loadR( TempDescriptor x,
227 Set<EdgeKey> edgeKeysForLoad ) {
228 // consider that x and y can be the same, so do the
229 // parts of the update in the right order:
231 // first get all info for update
232 MultiKey keyY = MultiKey.factory( y );
233 Map<MultiKey, Object> mapY0 = R.get( viewR0, keyY );
235 // then remove anything
236 MultiKey keyX = MultiKey.factory( x );
237 R.remove( viewR0, keyX );
238 R.remove( viewR1, keyX );
240 // then insert new stuff
241 for( EdgeKey e : edgeKeysForLoad ) {
242 R.put( MultiKey.factory( x, y, e ), MultiViewMap.dummyValue );
244 for( MultiKey fullKeyY : mapY0.keySet() ) {
245 R.put( MultiKey.factory( x,
248 MultiViewMap.dummyValue );
250 R.put( MultiKey.factory( x,
253 MultiViewMap.dummyValue );
258 public void storeR( TempDescriptor x,
261 Set<EdgeKey> edgeKeysRemoved,
262 Set<EdgeKey> edgeKeysAdded ) {
264 for( EdgeKey edgeKeyWZ : edgeKeysRemoved ) {
265 R.remove( viewR2, MultiKey.factory( edgeKeyWZ ) );
268 for( EdgeKey edgeKeyXY : edgeKeysAdded ) {
269 R.put( MultiKey.factory( y, x, edgeKeyXY ), MultiViewMap.dummyValue );
273 public void newObjectR( TempDescriptor x ) {
274 MultiKey keyX = MultiKey.factory( x );
275 R.remove( viewR0, keyX );
276 R.remove( viewR1, keyX );
279 public void methodCallR( TempDescriptor retVal ) {
280 MultiKey keyRetVal = MultiKey.factory( retVal );
281 R.remove( viewR0, keyRetVal );
282 R.remove( viewR1, keyRetVal );
285 public void mergeR( DefiniteReachState that ) {
286 for( MultiKey key : this.R.get().keySet() ) {
287 if( that.R.get( viewRfull, key ).isEmpty() ) {
288 this.R.remove( viewRfull, key );
296 ///////////////////////////////////////////////////////////
300 // It definitely tests the current R as well as Rs
302 // but also be careful what null means, is it actually
303 // equivalent to UNKOWN? I'd rather put nothing, meaning
304 // we have to do an analysis pass over all the incoming edges
305 // before there is a sensical answer. I think...
306 private void mergeRs( DefiniteReachState that ) {
307 // merge "that" into "this" and leave "that" unchanged
308 //Set<TempDescriptor> allVars = new HashSet<TempDescriptor>();
309 //allVars.addAll( this.Rs.keySet() );
310 //allVars.addAll( that.Rs.keySet() );
311 //for( TempDescriptor x : allVars ) {
312 // DefReachKnown vThis = this.Rs.get( x );
313 // DefReachKnown vThat = that.Rs.get( x );
314 // if( vThis != null && vThis.equals( DefReachKnown.KNOWN ) &&
315 // vThat != null && vThat.equals( DefReachKnown.KNOWN ) ) {
316 // this.Rs.put( x, DefReachKnown.KNOWN );
318 // this.Rs.put( x, DefReachKnown.UNKNOWN );
325 public boolean equals( Object o ) {
332 if( !(o instanceof DefiniteReachState) ) {
335 DefiniteReachState that = (DefiniteReachState) o;
342 public int hashCode() {
348 public void writeState( String outputName ) {
350 BufferedWriter bw = new BufferedWriter( new FileWriter( "defReach-"+outputName+".txt" ) );
351 bw.write( this.toString() );
353 } catch( IOException e ) {
354 System.out.println( "ERROR writing definite reachability state:\n "+e );
360 public String toString() {
361 StringBuilder s = new StringBuilder();
363 s.append( "R = {\n" );
364 s.append( R.toString( 2 ) );
367 //s.append( "R_s = {" );
368 //for( TempDescriptor x : Rs.keySet() ) {
369 // s.append( " "+x+"->"+Rs.get( x ) );