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