1 package Analysis.Disjoint;
10 public class DefiniteReachState {
14 // Maps variables and an edge (x, y, e) to an unused value when the
15 // object of x is already reachable from the object of y, and the
16 // set of edges conservatively gives the path.
17 // NOTE: Use EdgeKey instead of edges because this analysis's
18 // scope is beyond the scope of a single reach graph.
22 // Tracks whether the analysis must know the definite reachability
23 // information of a given variable.
24 private enum DefReachKnown {
28 private Map<TempDescriptor, DefReachKnown> Rs;
33 // Maps a variable that points to object o0 to the
34 // set of variables that point to objects o1...oN
35 // that have a reference to o0.
36 private static MultiViewMapBuilder<Object> FuBuilder;
37 private static BitSet viewFu0;
38 private static BitSet viewFu1;
39 private MultiViewMap<Object> Fu;
47 // for MultiViewMaps that don't need to use the value,
48 // always map to this dummy
49 private static Object dummy = new Integer( -1234 );
52 // call before instantiating this class
53 static public void initBuilders() {
55 new MultiViewMapBuilder<Object>( new Class[] {
59 viewFu0 = FuBuilder.addPartialView( 0 );
60 viewFu1 = FuBuilder.addPartialView( 1 );
61 FuBuilder.setCheckTypes( true );
62 FuBuilder.setCheckConsistency( true );
69 public DefiniteReachState() {
70 Rs = new HashMap<TempDescriptor, DefReachKnown>();
71 Fu = FuBuilder.build();
76 public void methodEntry(Set<TempDescriptor> parameters) {
81 for( TempDescriptor p : parameters ) {
82 Rs.put( p, DefReachKnown.UNKNOWN );
85 Fu = FuBuilder.build();
88 public void copy(TempDescriptor x,
90 // R' := (R - <x,*> - <*,x>) U
91 // {<x,z>->e | <y,z>->e in R} U
92 // {<z,x>->e | <z,y>->e in R}
94 // R'.remove(view0, x);
95 // R'.remove(view1, x);
96 // setYs = R.get(view0, y);
97 // for each <y,z>->e: R'.put(<x,z>, e);
98 // setYs = R.get(view1, y);
99 // for each <z,y>->e: R'.put(<z,x>, e);
101 // Rs' := (Rs - <x,*>) U {<x,v> | <y,v> in Rs}
102 DefReachKnown valRs = Rs.get( y );
103 assert( valRs != null );
106 // Fu' := (Fu - <x, *> - <*, x>) U
107 // {<x,v> | <y,v> in Fu} U
108 // {<v,x> | <v,y> in Fu} U
109 // {<z, unknown> | <z,<x>> in Fu}
110 Fu.remove( viewFu0, MultiKey.factory( x ) );
111 Fu.remove( viewFu1, MultiKey.factory( x ) );
112 for( MultiKey key : Fu.get( viewFu0, MultiKey.factory( y ) ).keySet() ) {
113 DefReachFuVal val = (DefReachFuVal) key.get( 1 );
114 Fu.put( MultiKey.factory( x, val ), dummy );
116 for( MultiKey key : Fu.get( viewFu1, MultiKey.factory( y ) ).keySet() ) {
117 TempDescriptor v = (TempDescriptor) key.get( 0 );
118 Fu.put( MultiKey.factory( v, DefReachFuVal.factory( x ) ), dummy );
122 MultiKey.factory( DefReachFuVal.factory( DefReachFuVal.Val.UNKNOWN ) )
125 TempDescriptor z = (TempDescriptor) key.get( 0 );
126 Fu.put( MultiKey.factory( z, DefReachFuVal.factory( x ) ), dummy );
130 public void load(TempDescriptor x,
133 // R' := (R - <x,*> - <*,x>) U
134 // ({<x,y>} x Eo(y,f)) U
135 // U {<x,z>} x (Eo(y,f)U{e})
138 // R'.remove(view0, x);
139 // R'.remove(view1, x);
140 // R'.put(<x,y>, eee!);
141 // setYs = R.get(view0, y);
142 // for each <y,z>->e: R'.put(<x,z>, eee!Ue);
144 // Rs' := (Rs - <x,*>) U {<x, unknown>}
145 Rs.put( x, DefReachKnown.UNKNOWN );
148 public void store(TempDescriptor x,
151 // I think this should be if there is ANY <w,z>->e' IN Eremove, then kill all <w,z>
152 // R' := (R - {<w,z>->e | <w,z>->e in R, A<w,z>->e' in R, e' notin Eremove}) U
153 // {<y,x>->e | e in E(x) x {f} x E(y)}
155 // R'.remove(?); some e's...
156 // R'.put(<y,x>, E(x) x {f} x E(y));
161 public void newObject(TempDescriptor x) {
162 // R' := (R - <x,*> - <*,x>)
164 // R'.remove(view0, x);
165 // R'.remove(view1, x);
167 // Rs' := (Rs - <x,*>) U {<x, new>}
168 Rs.put( x, DefReachKnown.KNOWN );
172 // x is the return value, x = foo(...);
173 public void methodCall(TempDescriptor x) {
174 // R' := (R - <x,*> - <*,x>)
176 // R'.remove(view0, x);
177 // R'.remove(view1, x);
179 // Rs' := (Rs - <x,*>) U {<x, unknown>}
180 Rs.put( x, DefReachKnown.UNKNOWN );
183 public void merge( DefiniteReachState that ) {
184 // R' := <x,y>->e iff its in all incoming edges
186 // Rs' := <x, new> iff in all incoming edges, otherwie <x, unknown>
191 ///////////////////////////////////////////////////////////
195 // It definitely tests the current R as well as Rs
197 // but also be careful what null means, is it actually
198 // equivalent to UNKOWN? I'd rather put nothing, meaning
199 // we have to do an analysis pass over all the incoming edges
200 // before there is a sensical answer. I think...
201 private void mergeRs( DefiniteReachState that ) {
202 // merge "that" into "this" and leave "that" unchanged
203 Set<TempDescriptor> allVars = new HashSet<TempDescriptor>();
204 allVars.addAll( this.Rs.keySet() );
205 allVars.addAll( that.Rs.keySet() );
206 for( TempDescriptor x : allVars ) {
207 DefReachKnown vThis = this.Rs.get( x );
208 DefReachKnown vThat = that.Rs.get( x );
209 if( vThis != null && vThis.equals( DefReachKnown.KNOWN ) &&
210 vThat != null && vThat.equals( DefReachKnown.KNOWN ) ) {
211 this.Rs.put( x, DefReachKnown.KNOWN );
213 this.Rs.put( x, DefReachKnown.UNKNOWN );
220 public boolean equals( Object o ) {
227 if( !(o instanceof DefiniteReachState) ) {
230 DefiniteReachState that = (DefiniteReachState) o;
237 public int hashCode() {
244 public String toString() {
245 StringBuilder s = new StringBuilder( "R_s = {" );
246 for( TempDescriptor x : Rs.keySet() ) {
247 s.append( " "+x+"->"+Rs.get( x ) );