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
  52   // the preds on this state are irrelevant, so always strip them off
  53   // when we store it in this ExistPred to make sure it equals other
  54   // ExistPred objects with the same ne_state, preds ignored.
  55   protected ReachState ne_state;
  56
  57   // An edge existence predicate is satisfied if the elements
  58   // defining an edge are part of the given graph.
  59   // The reach state may be null--if not the predicate is
  60   // satisfied when the edge exists AND it has the state.
  61   // the source of an edge is *either* a variable
  62   // node or a heap region node
  63   protected TempDescriptor e_tdSrc;
  64   protected Integer e_hrnSrcID;
  65
  66   // the source of an edge might be out of the callee
  67   // context but in the caller graph, a normal caller
  68   // heap region or variable, OR it might be out of the
  69   // caller context ALSO: an ooc node in the caller
  70   protected boolean e_srcOutCalleeContext;
  71   protected boolean e_srcOutCallerContext;
  72
  73   // dst is always a heap region
  74   protected Integer e_hrnDstID;
  75
  76   // a reference has a field name and type
  77   protected TypeDescriptor e_type;
  78   protected String e_field;
  79
  80   // if the taint is non-null then the predicate
  81   // is true only if the edge exists AND has the
  82   // taint--ONLY ONE of the ne_state or e_taint
  83   // may be non-null for an edge predicate
  84   protected Taint e_taint;
  85
  86
  87
  88   // a static debug flag for higher abstraction code
  89   // to enable debug info at this level
  90   public static boolean debug = false;
  91
  92
  93   // to make the true predicate
  94   public static ExistPred factory() {
  95     ExistPred out = new ExistPred();
  96     out = (ExistPred) Canonical.makeCanonical(out);
  97     return out;
  98   }
  99
 100   protected ExistPred() {
 101     this.predType = TYPE_TRUE;
 102     ne_state   = null;
 103     n_hrnID    = null;
 104     e_tdSrc    = null;
 105     e_hrnSrcID = null;
 106     e_hrnDstID = null;
 107     e_type     = null;
 108     e_field    = null;
 109     e_taint    = null;
 110     e_srcOutCalleeContext = false;
 111     e_srcOutCallerContext = false;
 112   }
 113
 114   // node predicates
 115   public static ExistPred factory(Integer hrnID,
 116                                   ReachState state) {
 117
 118     ExistPred out = new ExistPred(hrnID, state);
 119
 120     out = (ExistPred) Canonical.makeCanonical(out);
 121     return out;
 122   }
 123
 124   protected ExistPred(Integer hrnID,
 125                       ReachState state) {
 126     assert hrnID != null;
 127     this.n_hrnID  = hrnID;
 128     this.ne_state = removePreds( state );
 129     this.predType = TYPE_NODE;
 130     e_tdSrc    = null;
 131     e_hrnSrcID = null;
 132     e_hrnDstID = null;
 133     e_type     = null;
 134     e_field    = null;
 135     e_taint    = null;
 136     e_srcOutCalleeContext = false;
 137     e_srcOutCallerContext = false;
 138   }
 139
 140   // edge predicates
 141   public static ExistPred factory(TempDescriptor tdSrc,
 142                                   Integer hrnSrcID,
 143                                   Integer hrnDstID,
 144                                   TypeDescriptor type,
 145                                   String field,
 146                                   ReachState state,
 147                                   Taint taint,
 148                                   boolean srcOutCalleeContext,
 149                                   boolean srcOutCallerContext) {
 150
 151     ExistPred out = new ExistPred(tdSrc,
 152                                   hrnSrcID,
 153                                   hrnDstID,
 154                                   type,
 155                                   field,
 156                                   state,
 157                                   taint,
 158                                   srcOutCalleeContext,
 159                                   srcOutCallerContext);
 160
 161     out = (ExistPred) Canonical.makeCanonical(out);
 162     return out;
 163   }
 164
 165   protected ExistPred(TempDescriptor tdSrc,
 166                       Integer hrnSrcID,
 167                       Integer hrnDstID,
 168                       TypeDescriptor type,
 169                       String field,
 170                       ReachState state,
 171                       Taint taint,
 172                       boolean srcOutCalleeContext,
 173                       boolean srcOutCallerContext) {
 174
 175     assert(tdSrc == null) || (hrnSrcID == null);
 176     assert hrnDstID != null;
 177     assert type     != null;
 178     assert(state == null) || (taint == null);
 179
 180     // fields can be null when the edge is from
 181     // a variable node to a heap region!
 182
 183     this.e_srcOutCalleeContext = srcOutCalleeContext;
 184     this.e_srcOutCallerContext = srcOutCallerContext;
 185
 186     assert !(e_srcOutCalleeContext && e_srcOutCallerContext);
 187
 188     this.e_tdSrc    = tdSrc;
 189     this.e_hrnSrcID = hrnSrcID;
 190     this.e_hrnDstID = hrnDstID;
 191     this.e_type     = type;
 192     this.e_field    = field;
 193     this.ne_state   = removePreds( state );
 194     this.e_taint    = taint;
 195     this.predType   = TYPE_EDGE;
 196     n_hrnID = null;
 197   }
 198
 199   // for node or edge, check inputs
 200   public static ExistPred factory(Integer hrnID,
 201                                   TempDescriptor tdSrc,
 202                                   Integer hrnSrcID,
 203                                   Integer hrnDstID,
 204                                   TypeDescriptor type,
 205                                   String field,
 206                                   ReachState state,
 207                                   Taint taint,
 208                                   boolean srcOutCalleeContext,
 209                                   boolean srcOutCallerContext) {
 210     ExistPred out;
 211
 212     if( hrnID != null ) {
 213       out = new ExistPred(hrnID, state);
 214
 215     } else {
 216       out = new ExistPred(tdSrc,
 217                           hrnSrcID,
 218                           hrnDstID,
 219                           type,
 220                           field,
 221                           state,
 222                           taint,
 223                           srcOutCalleeContext,
 224                           srcOutCallerContext);
 225     }
 226
 227     out = (ExistPred) Canonical.makeCanonical(out);
 228     return out;
 229   }
 230
 231
 232
 233   private ReachState removePreds( ReachState state ) {
 234     return state == null ? null : Canonical.attach( state, ExistPredSet.factory() );
 235   }
 236
 237
 238
 239   // only consider the subest of the caller elements that
 240   // are reachable by callee when testing predicates--if THIS
 241   // predicate is satisfied, return the predicate set of the
 242   // element that satisfied it, or null for false
 243   public ExistPredSet isSatisfiedBy(ReachGraph rg,
 244                                     Set<Integer> calleeReachableNodes,
 245                                     Set<RefSrcNode> callerSrcMatches
 246                                     ) {
 247     if( predType == TYPE_TRUE ) {
 248       return ExistPredSet.factory(ExistPred.factory() );
 249     }
 250
 251     if( predType == TYPE_NODE ) {
 252       // first find node
 253       HeapRegionNode hrn = rg.id2hrn.get(n_hrnID);
 254       if( hrn == null ) {
 255         return null;
 256       }
 257
 258       if( !calleeReachableNodes.contains(n_hrnID) ) {
 259         return null;
 260       }
 261
 262       // when the state is null we're done!
 263       if( ne_state == null ) {
 264         return hrn.getPreds();
 265
 266       } else {
 267         // otherwise look for state too
 268
 269         // TODO: contains OR containsSuperSet OR containsWithZeroes??
 270         ReachState stateCaller = hrn.getAlpha().containsIgnorePreds(ne_state);
 271
 272         if( stateCaller == null ) {
 273           return null;
 274
 275         } else {
 276           // it was here, return the predicates on the state!!
 277           return stateCaller.getPreds();
 278         }
 279       }
 280
 281       // unreachable program point!
 282     }
 283
 284     if( predType == TYPE_EDGE ) {
 285
 286       // first establish whether the source of the
 287       // reference edge exists
 288       VariableNode vnSrc = null;
 289       if( e_tdSrc != null ) {
 290         vnSrc = rg.td2vn.get(e_tdSrc);
 291       }
 292       HeapRegionNode hrnSrc = null;
 293       if( e_hrnSrcID != null ) {
 294         hrnSrc = rg.id2hrn.get(e_hrnSrcID);
 295       }
 296       assert(vnSrc == null) || (hrnSrc == null);
 297
 298       // the source is not present in graph
 299       if( vnSrc == null && hrnSrc == null ) {
 300         return null;
 301       }
 302
 303       RefSrcNode rsn;
 304       if( vnSrc != null ) {
 305         rsn = vnSrc;
 306         assert e_srcOutCalleeContext;
 307         assert !e_srcOutCallerContext;
 308
 309       } else {
 310
 311         assert !(e_srcOutCalleeContext && e_srcOutCallerContext);
 312
 313         if( e_srcOutCalleeContext ) {
 314           if( calleeReachableNodes.contains(e_hrnSrcID) ) {
 315             return null;
 316           }
 317
 318         } else if( e_srcOutCallerContext ) {
 319           if( !hrnSrc.isOutOfContext() ) {
 320             return null;
 321           }
 322
 323         } else {
 324
 325           if( !calleeReachableNodes.contains(e_hrnSrcID) ) {
 326             return null;
 327           }
 328           if( hrnSrc.isOutOfContext() ) {
 329             return null;
 330           }
 331
 332         }
 333
 334         rsn = hrnSrc;
 335       }
 336
 337       // is the destination present?
 338       HeapRegionNode hrnDst = rg.id2hrn.get(e_hrnDstID);
 339       if( hrnDst == null ) {
 340         return null;
 341       }
 342
 343       if( !calleeReachableNodes.contains(e_hrnDstID) ) {
 344         return null;
 345       }
 346
 347       // is there an edge between them with the given
 348       // type and field?
 349       // TODO: type OR a subtype?
 350       RefEdge edge = rsn.getReferenceTo(hrnDst,
 351                                         e_type,
 352                                         e_field);
 353       if( edge == null ) {
 354         return null;
 355       }
 356
 357       // when the state and taint are null we're done!
 358       if( ne_state == null &&
 359           e_taint  == null ) {
 360
 361         if( callerSrcMatches != null ) {
 362           callerSrcMatches.add( rsn );
 363         }
 364
 365         return edge.getPreds();
 366
 367
 368       } else if( ne_state != null ) {
 369         // otherwise look for state too
 370
 371         // TODO: contains OR containsSuperSet OR containsWithZeroes??
 372         ReachState stateCaller = edge.getBeta().containsIgnorePreds(ne_state);
 373
 374         if( stateCaller == null ) {
 375           return null;
 376
 377         } else {
 378           // it was here, return the predicates on the state!!
 379           return stateCaller.getPreds();
 380         }
 381
 382       } else {
 383         // otherwise look for taint
 384
 385         Taint tCaller = edge.getTaints().containsIgnorePreds(e_taint);
 386
 387         if( tCaller == null ) {
 388           return null;
 389
 390         } else {
 391           // it was here, return the predicates on the taint!!
 392           if( callerSrcMatches != null ) {
 393             callerSrcMatches.add( rsn );
 394           }
 395
 396           return tCaller.getPreds();
 397         }
 398       }
 399
 400       // unreachable program point!
 401     }
 402
 403     throw new Error("Unknown predicate type");
 404   }
 405
 406
 407
 408   // if this pred is an edge type pred, then given
 409   // a reach graph, find the element of the graph that
 410   // may exist and represents the source of the edge
 411   public RefSrcNode getEdgeSource( ReachGraph rg ) {
 412     if( predType != TYPE_EDGE ) {
 413       return null;
 414     }
 415
 416     if( e_tdSrc != null ) {
 417       // variable node is the source, look for it in the graph
 418       return rg.getVariableNodeNoMutation( e_tdSrc );
 419     }
 420
 421     // otherwise a heap region node is the source, look for it
 422     assert e_hrnDstID != null;
 423     return rg.id2hrn.get( e_hrnDstID );
 424   }
 425
 426
 427
 428   public boolean equalsSpecific(Object o) {
 429     if( o == null ) {
 430       return false;
 431     }
 432
 433     if( !(o instanceof ExistPred) ) {
 434       return false;
 435     }
 436
 437     ExistPred pred = (ExistPred) o;
 438
 439     if( this.predType != pred.predType ) {
 440       return false;
 441     }
 442
 443     if( ne_state == null ) {
 444       if( pred.ne_state != null ) {
 445         return false;
 446       }
 447     } else if( !ne_state.equalsIgnorePreds(pred.ne_state) ) {
 448       return false;
 449     }
 450
 451     if( n_hrnID == null ) {
 452       if( pred.n_hrnID != null ) {
 453         return false;
 454       }
 455     } else if( !n_hrnID.equals(pred.n_hrnID) ) {
 456       return false;
 457     }
 458
 459     if( e_tdSrc == null ) {
 460       if( pred.e_tdSrc != null ) {
 461         return false;
 462       }
 463     } else if( !e_tdSrc.equals(pred.e_tdSrc) ) {
 464       return false;
 465     }
 466
 467     if( e_hrnSrcID == null ) {
 468       if( pred.e_hrnSrcID != null ) {
 469         return false;
 470       }
 471     } else {
 472       if( !e_hrnSrcID.equals(pred.e_hrnSrcID) ) {
 473         return false;
 474       }
 475       if( e_srcOutCalleeContext != pred.e_srcOutCalleeContext ) {
 476         return false;
 477       }
 478       if( e_srcOutCallerContext != pred.e_srcOutCallerContext ) {
 479         return false;
 480       }
 481     }
 482
 483     if( e_hrnDstID == null ) {
 484       if( pred.e_hrnDstID != null ) {
 485         return false;
 486       }
 487     } else if( !e_hrnDstID.equals(pred.e_hrnDstID) ) {
 488       return false;
 489     }
 490
 491     if( e_type == null ) {
 492       if( pred.e_type != null ) {
 493         return false;
 494       }
 495     } else if( !e_type.equals(pred.e_type) ) {
 496       return false;
 497     }
 498
 499     if( e_field == null ) {
 500       if( pred.e_field != null ) {
 501         return false;
 502       }
 503     } else if( !e_field.equals(pred.e_field) ) {
 504       return false;
 505     }
 506
 507     if( e_taint == null ) {
 508       if( pred.e_taint != null ) {
 509         return false;
 510       }
 511     } else if( !e_taint.equals(pred.e_taint) ) {
 512       return false;
 513     }
 514
 515     return true;
 516   }
 517
 518
 519   public int hashCodeSpecific() {
 520
 521     if( predType == TYPE_TRUE ) {
 522       return 1;
 523     }
 524
 525     if( predType == TYPE_NODE ) {
 526       int hash = n_hrnID.intValue()*17;
 527
 528       if( ne_state != null ) {
 529         hash ^= ne_state.hashCodeNoPreds();
 530       }
 531
 532       return hash;
 533     }
 534
 535     if( predType == TYPE_EDGE ) {
 536       int hash = 0;
 537
 538       hash += e_type.hashCode()*17;
 539
 540       if( e_field != null ) {
 541         hash += e_field.hashCode()*7;
 542       }
 543
 544       if( e_tdSrc != null ) {
 545         hash ^= e_tdSrc.hashCode()*11;
 546       } else {
 547         hash ^= e_hrnSrcID.hashCode()*11;
 548         if( e_srcOutCalleeContext ) {
 549           hash ^= 0x01;
 550         }
 551         if( e_srcOutCallerContext ) {
 552           hash ^= 0x80;
 553         }
 554       }
 555
 556       hash += e_hrnDstID.hashCode();
 557
 558       if( ne_state != null ) {
 559         hash ^= ne_state.hashCodeNoPreds();
 560       }
 561
 562       if( e_taint != null ) {
 563         hash ^= e_taint.hashCode();
 564       }
 565
 566       return hash;
 567     }
 568
 569     throw new Error("Unknown predicate type");
 570   }
 571
 572
 573   public String toString() {
 574     if( predType == TYPE_TRUE ) {
 575       return "t";
 576     }
 577
 578     if( predType == TYPE_NODE ) {
 579       String s = n_hrnID.toString();
 580       if( ne_state != null ) {
 581         s += "w"+ne_state;
 582       }
 583       return s;
 584     }
 585
 586     if( predType == TYPE_EDGE ) {
 587       String s = "(";
 588
 589       if( e_tdSrc != null ) {
 590         s += e_tdSrc.toString();
 591       } else {
 592         s += e_hrnSrcID.toString();
 593       }
 594
 595       if( e_srcOutCalleeContext ) {
 596         s += "(ooCLEEc)";
 597       }
 598
 599       if( e_srcOutCallerContext ) {
 600         s += "(ooCLERc)";
 601       }
 602
 603       s += "-->"+e_hrnDstID+")";
 604
 605       if( ne_state != null ) {
 606         s += "w"+ne_state;
 607       }
 608
 609       if( e_taint != null ) {
 610         s += "w"+e_taint;
 611       }
 612
 613       return s;
 614     }
 615
 616     throw new Error("Unknown predicate type");
 617   }
 618
 619 }