Robust/src/Analysis/Disjoint/ExistPred.java

   1 package Analysis.Disjoint;
   2
   3 import IR.*;
   4 import IR.Flat.*;
   5 import java.util.*;
   6 import java.io.*;
   7
   8 ///////////////////////////////////////////
   9 //  IMPORTANT
  10 //  This class is an immutable Canonical, so
  11 //
  12 //  0) construct them with a factory pattern
  13 //  to ensure only canonical versions escape
  14 //
  15 //  1) any operation that modifies a Canonical
  16 //  is a static method in the Canonical class
  17 //
  18 //  2) operations that just read this object
  19 //  should be defined here
  20 //
  21 //  3) every Canonical subclass hashCode should
  22 //  throw an error if the hash ever changes
  23 //
  24 ///////////////////////////////////////////
  25
  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
  31
  32 public class ExistPred extends Canonical {
  33
  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
  37
  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;
  43
  44   // true predicates always evaluate to true
  45
  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;
  52
  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;
  61
  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;
  68
  69   // dst is always a heap region
  70   protected Integer e_hrnDstID;
  71
  72   // a reference has a field name and type
  73   protected TypeDescriptor e_type;
  74   protected String e_field;
  75
  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;
  81
  82
  83
  84   // a static debug flag for higher abstraction code
  85   // to enable debug info at this level
  86   public static boolean debug = false;
  87
  88
  89   // to make the true predicate
  90   public static ExistPred factory() {
  91     ExistPred out = new ExistPred();
  92     out = (ExistPred) Canonical.makeCanonical(out);
  93     return out;
  94   }
  95
  96   protected ExistPred() {
  97     this.predType = TYPE_TRUE;
  98     ne_state   = null;
  99     n_hrnID    = null;
 100     e_tdSrc    = null;
 101     e_hrnSrcID = null;
 102     e_hrnDstID = null;
 103     e_type     = null;
 104     e_field    = null;
 105     e_taint    = null;
 106     e_srcOutCalleeContext = false;
 107     e_srcOutCallerContext = false;
 108   }
 109
 110   // node predicates
 111   public static ExistPred factory(Integer hrnID,
 112                                   ReachState state) {
 113
 114     ExistPred out = new ExistPred(hrnID, state);
 115
 116     out = (ExistPred) Canonical.makeCanonical(out);
 117     return out;
 118   }
 119
 120   protected ExistPred(Integer hrnID,
 121                       ReachState state) {
 122     assert hrnID != null;
 123     this.n_hrnID  = hrnID;
 124     this.ne_state = state;
 125     this.predType = TYPE_NODE;
 126     e_tdSrc    = null;
 127     e_hrnSrcID = null;
 128     e_hrnDstID = null;
 129     e_type     = null;
 130     e_field    = null;
 131     e_taint    = null;
 132     e_srcOutCalleeContext = false;
 133     e_srcOutCallerContext = false;
 134   }
 135
 136   // edge predicates
 137   public static ExistPred factory(TempDescriptor tdSrc,
 138                                   Integer hrnSrcID,
 139                                   Integer hrnDstID,
 140                                   TypeDescriptor type,
 141                                   String field,
 142                                   ReachState state,
 143                                   Taint taint,
 144                                   boolean srcOutCalleeContext,
 145                                   boolean srcOutCallerContext) {
 146
 147     ExistPred out = new ExistPred(tdSrc,
 148                                   hrnSrcID,
 149                                   hrnDstID,
 150                                   type,
 151                                   field,
 152                                   state,
 153                                   taint,
 154                                   srcOutCalleeContext,
 155                                   srcOutCallerContext);
 156
 157     out = (ExistPred) Canonical.makeCanonical(out);
 158     return out;
 159   }
 160
 161   protected ExistPred(TempDescriptor tdSrc,
 162                       Integer hrnSrcID,
 163                       Integer hrnDstID,
 164                       TypeDescriptor type,
 165                       String field,
 166                       ReachState state,
 167                       Taint taint,
 168                       boolean srcOutCalleeContext,
 169                       boolean srcOutCallerContext) {
 170
 171     assert(tdSrc == null) || (hrnSrcID == null);
 172     assert hrnDstID != null;
 173     assert type     != null;
 174     assert(state == null) || (taint == null);
 175
 176     // fields can be null when the edge is from
 177     // a variable node to a heap region!
 178
 179     this.e_srcOutCalleeContext = srcOutCalleeContext;
 180     this.e_srcOutCallerContext = srcOutCallerContext;
 181
 182     assert !(e_srcOutCalleeContext && e_srcOutCallerContext);
 183
 184     this.e_tdSrc    = tdSrc;
 185     this.e_hrnSrcID = hrnSrcID;
 186     this.e_hrnDstID = hrnDstID;
 187     this.e_type     = type;
 188     this.e_field    = field;
 189     this.ne_state   = state;
 190     this.e_taint    = taint;
 191     this.predType   = TYPE_EDGE;
 192     n_hrnID = null;
 193   }
 194
 195   // for node or edge, check inputs
 196   public static ExistPred factory(Integer hrnID,
 197                                   TempDescriptor tdSrc,
 198                                   Integer hrnSrcID,
 199                                   Integer hrnDstID,
 200                                   TypeDescriptor type,
 201                                   String field,
 202                                   ReachState state,
 203                                   Taint taint,
 204                                   boolean srcOutCalleeContext,
 205                                   boolean srcOutCallerContext) {
 206     ExistPred out;
 207
 208     if( hrnID != null ) {
 209       out = new ExistPred(hrnID, state);
 210
 211     } else {
 212       out = new ExistPred(tdSrc,
 213                           hrnSrcID,
 214                           hrnDstID,
 215                           type,
 216                           field,
 217                           state,
 218                           taint,
 219                           srcOutCalleeContext,
 220                           srcOutCallerContext);
 221     }
 222
 223     out = (ExistPred) Canonical.makeCanonical(out);
 224     return out;
 225   }
 226
 227
 228
 229
 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
 236                                     ) {
 237     if( predType == TYPE_TRUE ) {
 238       return ExistPredSet.factory(ExistPred.factory() );
 239     }
 240
 241     if( predType == TYPE_NODE ) {
 242
 243       // first find node
 244       HeapRegionNode hrn = rg.id2hrn.get(n_hrnID);
 245       if( hrn == null ) {
 246         return null;
 247       }
 248
 249       if( !calleeReachableNodes.contains(n_hrnID) ) {
 250         return null;
 251       }
 252
 253       // when the state is null we're done!
 254       if( ne_state == null ) {
 255         return hrn.getPreds();
 256
 257       } else {
 258         // otherwise look for state too
 259
 260         // TODO: contains OR containsSuperSet OR containsWithZeroes??
 261         ReachState stateCaller = hrn.getAlpha().containsIgnorePreds(ne_state);
 262
 263         if( stateCaller == null ) {
 264           return null;
 265
 266         } else {
 267           // it was here, return the predicates on the state!!
 268           return stateCaller.getPreds();
 269         }
 270       }
 271
 272       // unreachable program point!
 273     }
 274
 275     if( predType == TYPE_EDGE ) {
 276
 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);
 282       }
 283       HeapRegionNode hrnSrc = null;
 284       if( e_hrnSrcID != null ) {
 285         hrnSrc = rg.id2hrn.get(e_hrnSrcID);
 286       }
 287       assert(vnSrc == null) || (hrnSrc == null);
 288
 289       // the source is not present in graph
 290       if( vnSrc == null && hrnSrc == null ) {
 291         return null;
 292       }
 293
 294       RefSrcNode rsn;
 295       if( vnSrc != null ) {
 296         rsn = vnSrc;
 297         assert e_srcOutCalleeContext;
 298         assert !e_srcOutCallerContext;
 299
 300       } else {
 301
 302         assert !(e_srcOutCalleeContext && e_srcOutCallerContext);
 303
 304         if( e_srcOutCalleeContext ) {
 305           if( calleeReachableNodes.contains(e_hrnSrcID) ) {
 306             return null;
 307           }
 308
 309         } else if( e_srcOutCallerContext ) {
 310           if( !hrnSrc.isOutOfContext() ) {
 311             return null;
 312           }
 313
 314         } else {
 315
 316           if( !calleeReachableNodes.contains(e_hrnSrcID) ) {
 317             return null;
 318           }
 319           if( hrnSrc.isOutOfContext() ) {
 320             return null;
 321           }
 322
 323         }
 324
 325         rsn = hrnSrc;
 326       }
 327
 328       // is the destination present?
 329       HeapRegionNode hrnDst = rg.id2hrn.get(e_hrnDstID);
 330       if( hrnDst == null ) {
 331         return null;
 332       }
 333
 334       if( !calleeReachableNodes.contains(e_hrnDstID) ) {
 335         return null;
 336       }
 337
 338       // is there an edge between them with the given
 339       // type and field?
 340       // TODO: type OR a subtype?
 341       RefEdge edge = rsn.getReferenceTo(hrnDst,
 342                                         e_type,
 343                                         e_field);
 344       if( edge == null ) {
 345         return null;
 346       }
 347
 348       // when the state and taint are null we're done!
 349       if( ne_state == null &&
 350           e_taint  == null ) {
 351         return edge.getPreds();
 352
 353       } else if( ne_state != null ) {
 354         // otherwise look for state too
 355
 356         // TODO: contains OR containsSuperSet OR containsWithZeroes??
 357         ReachState stateCaller = edge.getBeta().containsIgnorePreds(ne_state);
 358
 359         if( stateCaller == null ) {
 360           return null;
 361
 362         } else {
 363           // it was here, return the predicates on the state!!
 364           return stateCaller.getPreds();
 365         }
 366
 367       } else {
 368         // otherwise look for taint
 369
 370         Taint tCaller = edge.getTaints().containsIgnorePreds(e_taint);
 371
 372         if( tCaller == null ) {
 373           return null;
 374
 375         } else {
 376           // it was here, return the predicates on the taint!!
 377           return tCaller.getPreds();
 378         }
 379       }
 380
 381       // unreachable program point!
 382     }
 383
 384     throw new Error("Unknown predicate type");
 385   }
 386
 387
 388
 389   public boolean equalsSpecific(Object o) {
 390     if( o == null ) {
 391       return false;
 392     }
 393
 394     if( !(o instanceof ExistPred) ) {
 395       return false;
 396     }
 397
 398     ExistPred pred = (ExistPred) o;
 399
 400     if( this.predType != pred.predType ) {
 401       return false;
 402     }
 403
 404     if( ne_state == null ) {
 405       if( pred.ne_state != null ) {
 406         return false;
 407       }
 408     } else if( !ne_state.equals(pred.ne_state) ) {
 409       return false;
 410     }
 411
 412     if( n_hrnID == null ) {
 413       if( pred.n_hrnID != null ) {
 414         return false;
 415       }
 416     } else if( !n_hrnID.equals(pred.n_hrnID) ) {
 417       return false;
 418     }
 419
 420     if( e_tdSrc == null ) {
 421       if( pred.e_tdSrc != null ) {
 422         return false;
 423       }
 424     } else if( !e_tdSrc.equals(pred.e_tdSrc) ) {
 425       return false;
 426     }
 427
 428     if( e_hrnSrcID == null ) {
 429       if( pred.e_hrnSrcID != null ) {
 430         return false;
 431       }
 432     } else {
 433       if( !e_hrnSrcID.equals(pred.e_hrnSrcID) ) {
 434         return false;
 435       }
 436       if( e_srcOutCalleeContext != pred.e_srcOutCalleeContext ) {
 437         return false;
 438       }
 439       if( e_srcOutCallerContext != pred.e_srcOutCallerContext ) {
 440         return false;
 441       }
 442     }
 443
 444     if( e_hrnDstID == null ) {
 445       if( pred.e_hrnDstID != null ) {
 446         return false;
 447       }
 448     } else if( !e_hrnDstID.equals(pred.e_hrnDstID) ) {
 449       return false;
 450     }
 451
 452     if( e_type == null ) {
 453       if( pred.e_type != null ) {
 454         return false;
 455       }
 456     } else if( !e_type.equals(pred.e_type) ) {
 457       return false;
 458     }
 459
 460     if( e_field == null ) {
 461       if( pred.e_field != null ) {
 462         return false;
 463       }
 464     } else if( !e_field.equals(pred.e_field) ) {
 465       return false;
 466     }
 467
 468     if( e_taint == null ) {
 469       if( pred.e_taint != null ) {
 470         return false;
 471       }
 472     } else if( !e_taint.equals(pred.e_taint) ) {
 473       return false;
 474     }
 475
 476     return true;
 477   }
 478
 479
 480   public int hashCodeSpecific() {
 481     if( predType == TYPE_TRUE ) {
 482       return 1;
 483     }
 484
 485     if( predType == TYPE_NODE ) {
 486       int hash = n_hrnID.intValue()*17;
 487
 488       if( ne_state != null ) {
 489         hash ^= ne_state.hashCode();
 490       }
 491
 492       return hash;
 493     }
 494
 495     if( predType == TYPE_EDGE ) {
 496       int hash = 0;
 497
 498       hash += e_type.hashCode()*17;
 499
 500       if( e_field != null ) {
 501         hash += e_field.hashCode()*7;
 502       }
 503
 504       if( e_tdSrc != null ) {
 505         hash ^= e_tdSrc.hashCode()*11;
 506       } else {
 507         hash ^= e_hrnSrcID.hashCode()*11;
 508         if( e_srcOutCalleeContext ) {
 509           hash ^= 0xf1aeb;
 510         }
 511         if( e_srcOutCallerContext ) {
 512           hash ^= 0x875d;
 513         }
 514       }
 515
 516       hash += e_hrnDstID.hashCode();
 517
 518       if( ne_state != null ) {
 519         hash ^= ne_state.hashCode();
 520       }
 521
 522       if( e_taint != null ) {
 523         hash ^= e_taint.hashCode();
 524       }
 525
 526       return hash;
 527     }
 528
 529     throw new Error("Unknown predicate type");
 530   }
 531
 532
 533   public String toString() {
 534     if( predType == TYPE_TRUE ) {
 535       return "t";
 536     }
 537
 538     if( predType == TYPE_NODE ) {
 539       String s = n_hrnID.toString();
 540       if( ne_state != null ) {
 541         s += "w"+ne_state;
 542       }
 543       return s;
 544     }
 545
 546     if( predType == TYPE_EDGE ) {
 547       String s = "(";
 548
 549       if( e_tdSrc != null ) {
 550         s += e_tdSrc.toString();
 551       } else {
 552         s += e_hrnSrcID.toString();
 553       }
 554
 555       if( e_srcOutCalleeContext ) {
 556         s += "(ooCLEEc)";
 557       }
 558
 559       if( e_srcOutCallerContext ) {
 560         s += "(ooCLERc)";
 561       }
 562
 563       s += "-->"+e_hrnDstID+")";
 564
 565       if( ne_state != null ) {
 566         s += "w"+ne_state;
 567       }
 568
 569       if( e_taint != null ) {
 570         s += "w"+e_taint;
 571       }
 572
 573       return s;
 574     }
 575
 576     throw new Error("Unknown predicate type");
 577   }
 578
 579 }