1 package Analysis.Disjoint;
8 ///////////////////////////////////////////
10 // This class is an immutable Canonical, so
12 // 0) construct them with a factory pattern
13 // to ensure only canonical versions escape
15 // 1) any operation that modifies a Canonical
16 // is a static method in the Canonical class
18 // 2) operations that just read this object
19 // should be defined here
21 // 3) every Canonical subclass hashCode should
22 // throw an error if the hash ever changes
24 ///////////////////////////////////////////
26 // Existence predicates in the callee final-result
27 // graph are relevant on the caller's callee-reachable
28 // graph parts. Any callee result elements with
29 // predicates not satisfied in the caller are not
30 // mapped in the call site transfer function
32 public class ExistPred extends Canonical {
34 // there are several types of predicates, note that
35 // there are not subclasses of the ExistPred class
36 // because they must be Canonical, no multiple inheritence
38 // types: true, node, edge
39 public static final int TYPE_TRUE = 0xa501;
40 public static final int TYPE_NODE = 0x02fd;
41 public static final int TYPE_EDGE = 0x414b;
42 protected int predType;
44 // true predicates always evaluate to true
46 // A node existence predicate is satisfied if the heap
47 // region ID defining a node is part of the given graph
48 // The reach state may be null--if not the predicate is
49 // satisfied when the edge exists AND it has the state.
50 protected Integer n_hrnID;
51 protected ReachState ne_state;
53 // An edge existence predicate is satisfied if the elements
54 // defining an edge are part of the given graph.
55 // The reach state may be null--if not the predicate is
56 // satisfied when the edge exists AND it has the state.
57 // the source of an edge is *either* a variable
58 // node or a heap region node
59 protected TempDescriptor e_tdSrc;
60 protected Integer e_hrnSrcID;
62 // the source of an edge might be out of the callee
63 // context but in the caller graph, a normal caller
64 // heap region or variable, OR it might be out of the
65 // caller context ALSO: an ooc node in the caller
66 protected boolean e_srcOutCalleeContext;
67 protected boolean e_srcOutCallerContext;
69 // dst is always a heap region
70 protected Integer e_hrnDstID;
72 // a reference has a field name and type
73 protected TypeDescriptor e_type;
74 protected String e_field;
76 // if the taint is non-null then the predicate
77 // is true only if the edge exists AND has the
78 // taint--ONLY ONE of the ne_state or e_taint
79 // may be non-null for an edge predicate
80 protected Taint e_taint;
84 // a static debug flag for higher abstraction code
85 // to enable debug info at this level
86 public static boolean debug = false;
89 // to make the true predicate
90 public static ExistPred factory() {
91 ExistPred out = new ExistPred();
92 out = (ExistPred) Canonical.makeCanonical(out);
96 protected ExistPred() {
97 this.predType = TYPE_TRUE;
106 e_srcOutCalleeContext = false;
107 e_srcOutCallerContext = false;
111 public static ExistPred factory(Integer hrnID,
114 ExistPred out = new ExistPred(hrnID, state);
116 out = (ExistPred) Canonical.makeCanonical(out);
120 protected ExistPred(Integer hrnID,
122 assert hrnID != null;
123 this.n_hrnID = hrnID;
124 this.ne_state = state;
125 this.predType = TYPE_NODE;
132 e_srcOutCalleeContext = false;
133 e_srcOutCallerContext = false;
137 public static ExistPred factory(TempDescriptor tdSrc,
144 boolean srcOutCalleeContext,
145 boolean srcOutCallerContext) {
147 ExistPred out = new ExistPred(tdSrc,
155 srcOutCallerContext);
157 out = (ExistPred) Canonical.makeCanonical(out);
161 protected ExistPred(TempDescriptor tdSrc,
168 boolean srcOutCalleeContext,
169 boolean srcOutCallerContext) {
171 assert(tdSrc == null) || (hrnSrcID == null);
172 assert hrnDstID != null;
174 assert(state == null) || (taint == null);
176 // fields can be null when the edge is from
177 // a variable node to a heap region!
179 this.e_srcOutCalleeContext = srcOutCalleeContext;
180 this.e_srcOutCallerContext = srcOutCallerContext;
182 assert !(e_srcOutCalleeContext && e_srcOutCallerContext);
184 this.e_tdSrc = tdSrc;
185 this.e_hrnSrcID = hrnSrcID;
186 this.e_hrnDstID = hrnDstID;
188 this.e_field = field;
189 this.ne_state = state;
190 this.e_taint = taint;
191 this.predType = TYPE_EDGE;
195 // for node or edge, check inputs
196 public static ExistPred factory(Integer hrnID,
197 TempDescriptor tdSrc,
204 boolean srcOutCalleeContext,
205 boolean srcOutCallerContext) {
208 if( hrnID != null ) {
209 out = new ExistPred(hrnID, state);
212 out = new ExistPred(tdSrc,
220 srcOutCallerContext);
223 out = (ExistPred) Canonical.makeCanonical(out);
230 // only consider the subest of the caller elements that
231 // are reachable by callee when testing predicates--if THIS
232 // predicate is satisfied, return the predicate set of the
233 // element that satisfied it, or null for false
234 public ExistPredSet isSatisfiedBy(ReachGraph rg,
235 Set<Integer> calleeReachableNodes
237 if( predType == TYPE_TRUE ) {
238 return ExistPredSet.factory(ExistPred.factory() );
241 if( predType == TYPE_NODE ) {
244 HeapRegionNode hrn = rg.id2hrn.get(n_hrnID);
249 if( !calleeReachableNodes.contains(n_hrnID) ) {
253 // when the state is null we're done!
254 if( ne_state == null ) {
255 return hrn.getPreds();
258 // otherwise look for state too
260 // TODO: contains OR containsSuperSet OR containsWithZeroes??
261 ReachState stateCaller = hrn.getAlpha().containsIgnorePreds(ne_state);
263 if( stateCaller == null ) {
267 // it was here, return the predicates on the state!!
268 return stateCaller.getPreds();
272 // unreachable program point!
275 if( predType == TYPE_EDGE ) {
277 // first establish whether the source of the
278 // reference edge exists
279 VariableNode vnSrc = null;
280 if( e_tdSrc != null ) {
281 vnSrc = rg.td2vn.get(e_tdSrc);
283 HeapRegionNode hrnSrc = null;
284 if( e_hrnSrcID != null ) {
285 hrnSrc = rg.id2hrn.get(e_hrnSrcID);
287 assert(vnSrc == null) || (hrnSrc == null);
289 // the source is not present in graph
290 if( vnSrc == null && hrnSrc == null ) {
295 if( vnSrc != null ) {
297 assert e_srcOutCalleeContext;
298 assert !e_srcOutCallerContext;
302 assert !(e_srcOutCalleeContext && e_srcOutCallerContext);
304 if( e_srcOutCalleeContext ) {
305 if( calleeReachableNodes.contains(e_hrnSrcID) ) {
309 } else if( e_srcOutCallerContext ) {
310 if( !hrnSrc.isOutOfContext() ) {
316 if( !calleeReachableNodes.contains(e_hrnSrcID) ) {
319 if( hrnSrc.isOutOfContext() ) {
328 // is the destination present?
329 HeapRegionNode hrnDst = rg.id2hrn.get(e_hrnDstID);
330 if( hrnDst == null ) {
334 if( !calleeReachableNodes.contains(e_hrnDstID) ) {
338 // is there an edge between them with the given
340 // TODO: type OR a subtype?
341 RefEdge edge = rsn.getReferenceTo(hrnDst,
348 // when the state and taint are null we're done!
349 if( ne_state == null &&
351 return edge.getPreds();
353 } else if( ne_state != null ) {
354 // otherwise look for state too
356 // TODO: contains OR containsSuperSet OR containsWithZeroes??
357 ReachState stateCaller = edge.getBeta().containsIgnorePreds(ne_state);
359 if( stateCaller == null ) {
363 // it was here, return the predicates on the state!!
364 return stateCaller.getPreds();
368 // otherwise look for taint
370 Taint tCaller = edge.getTaints().containsIgnorePreds(e_taint);
372 if( tCaller == null ) {
376 // it was here, return the predicates on the taint!!
377 return tCaller.getPreds();
381 // unreachable program point!
384 throw new Error("Unknown predicate type");
389 public boolean equalsSpecific(Object o) {
394 if( !(o instanceof ExistPred) ) {
398 ExistPred pred = (ExistPred) o;
400 if( this.predType != pred.predType ) {
404 if( ne_state == null ) {
405 if( pred.ne_state != null ) {
408 } else if( !ne_state.equals(pred.ne_state) ) {
412 if( n_hrnID == null ) {
413 if( pred.n_hrnID != null ) {
416 } else if( !n_hrnID.equals(pred.n_hrnID) ) {
420 if( e_tdSrc == null ) {
421 if( pred.e_tdSrc != null ) {
424 } else if( !e_tdSrc.equals(pred.e_tdSrc) ) {
428 if( e_hrnSrcID == null ) {
429 if( pred.e_hrnSrcID != null ) {
433 if( !e_hrnSrcID.equals(pred.e_hrnSrcID) ) {
436 if( e_srcOutCalleeContext != pred.e_srcOutCalleeContext ) {
439 if( e_srcOutCallerContext != pred.e_srcOutCallerContext ) {
444 if( e_hrnDstID == null ) {
445 if( pred.e_hrnDstID != null ) {
448 } else if( !e_hrnDstID.equals(pred.e_hrnDstID) ) {
452 if( e_type == null ) {
453 if( pred.e_type != null ) {
456 } else if( !e_type.equals(pred.e_type) ) {
460 if( e_field == null ) {
461 if( pred.e_field != null ) {
464 } else if( !e_field.equals(pred.e_field) ) {
468 if( e_taint == null ) {
469 if( pred.e_taint != null ) {
472 } else if( !e_taint.equals(pred.e_taint) ) {
480 public int hashCodeSpecific() {
481 if( predType == TYPE_TRUE ) {
485 if( predType == TYPE_NODE ) {
486 int hash = n_hrnID.intValue()*17;
488 if( ne_state != null ) {
489 hash ^= ne_state.hashCode();
495 if( predType == TYPE_EDGE ) {
498 hash += e_type.hashCode()*17;
500 if( e_field != null ) {
501 hash += e_field.hashCode()*7;
504 if( e_tdSrc != null ) {
505 hash ^= e_tdSrc.hashCode()*11;
507 hash ^= e_hrnSrcID.hashCode()*11;
508 if( e_srcOutCalleeContext ) {
511 if( e_srcOutCallerContext ) {
516 hash += e_hrnDstID.hashCode();
518 if( ne_state != null ) {
519 hash ^= ne_state.hashCode();
522 if( e_taint != null ) {
523 hash ^= e_taint.hashCode();
529 throw new Error("Unknown predicate type");
533 public String toString() {
534 if( predType == TYPE_TRUE ) {
538 if( predType == TYPE_NODE ) {
539 String s = n_hrnID.toString();
540 if( ne_state != null ) {
546 if( predType == TYPE_EDGE ) {
549 if( e_tdSrc != null ) {
550 s += e_tdSrc.toString();
552 s += e_hrnSrcID.toString();
555 if( e_srcOutCalleeContext ) {
559 if( e_srcOutCallerContext ) {
563 s += "-->"+e_hrnDstID+")";
565 if( ne_state != null ) {
569 if( e_taint != null ) {
576 throw new Error("Unknown predicate type");