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   // edge uses same ReachState ne_state as node type above
  77
  78
  79
  80   // a static debug flag for higher abstraction code
  81   // to enable debug info at this level
  82   public static boolean debug = false;
  83
  84
  85   // to make the true predicate
  86   public static ExistPred factory() {
  87     ExistPred out = new ExistPred();
  88     out = (ExistPred) Canonical.makeCanonical( out );
  89     return out;
  90   }
  91
  92   protected ExistPred() {
  93     this.predType = TYPE_TRUE;
  94     ne_state   = null;
  95     n_hrnID    = null;
  96     e_tdSrc    = null;
  97     e_hrnSrcID = null;
  98     e_hrnDstID = null;
  99     e_type     = null;
 100     e_field    = null;
 101     e_srcOutCalleeContext = false;
 102     e_srcOutCallerContext = false;
 103   }
 104
 105   // node predicates
 106   public static ExistPred factory( Integer    hrnID,
 107                                    ReachState state ) {
 108
 109     ExistPred out = new ExistPred( hrnID, state );
 110
 111     out = (ExistPred) Canonical.makeCanonical( out );
 112     return out;
 113   }
 114
 115   protected ExistPred( Integer    hrnID,
 116                        ReachState state ) {
 117     assert hrnID != null;
 118     this.n_hrnID  = hrnID;
 119     this.ne_state = state;
 120     this.predType = TYPE_NODE;
 121     e_tdSrc    = null;
 122     e_hrnSrcID = null;
 123     e_hrnDstID = null;
 124     e_type     = null;
 125     e_field    = null;
 126     e_srcOutCalleeContext = false;
 127     e_srcOutCallerContext = false;
 128   }
 129
 130   // edge predicates
 131   public static ExistPred factory( TempDescriptor tdSrc,
 132                                    Integer        hrnSrcID,
 133                                    Integer        hrnDstID,
 134                                    TypeDescriptor type,
 135                                    String         field,
 136                                    ReachState     state,
 137                                    boolean        srcOutCalleeContext,
 138                                    boolean        srcOutCallerContext ) {
 139
 140     ExistPred out = new ExistPred( tdSrc,
 141                                    hrnSrcID,
 142                                    hrnDstID,
 143                                    type,
 144                                    field,
 145                                    state,
 146                                    srcOutCalleeContext,
 147                                    srcOutCallerContext );
 148
 149     out = (ExistPred) Canonical.makeCanonical( out );
 150     return out;
 151   }
 152
 153   protected ExistPred( TempDescriptor tdSrc,
 154                        Integer        hrnSrcID,
 155                        Integer        hrnDstID,
 156                        TypeDescriptor type,
 157                        String         field,
 158                        ReachState     state,
 159                        boolean        srcOutCalleeContext,
 160                        boolean        srcOutCallerContext ) {
 161
 162     assert (tdSrc == null) || (hrnSrcID == null);
 163     assert hrnDstID != null;
 164     assert type     != null;
 165
 166     // fields can be null when the edge is from
 167     // a variable node to a heap region!
 168     // assert field    != null;
 169
 170     this.e_srcOutCalleeContext = srcOutCalleeContext;
 171     this.e_srcOutCallerContext = srcOutCallerContext;
 172
 173     assert !(e_srcOutCalleeContext && e_srcOutCallerContext);
 174
 175     this.e_tdSrc    = tdSrc;
 176     this.e_hrnSrcID = hrnSrcID;
 177     this.e_hrnDstID = hrnDstID;
 178     this.e_type     = type;
 179     this.e_field    = field;
 180     this.ne_state   = state;
 181     this.predType   = TYPE_EDGE;
 182     n_hrnID = null;
 183   }
 184
 185
 186   // only consider the subest of the caller elements that
 187   // are reachable by callee when testing predicates--if THIS
 188   // predicate is satisfied, return the predicate set of the
 189   // element that satisfied it, or null for false
 190   public ExistPredSet isSatisfiedBy( ReachGraph   rg,
 191                                      Set<Integer> calleeReachableNodes
 192                                      ) {
 193     if( predType == TYPE_TRUE ) {
 194       return ExistPredSet.factory( ExistPred.factory() );
 195     }
 196
 197     if( predType == TYPE_NODE ) {
 198
 199       // first find node
 200       HeapRegionNode hrn = rg.id2hrn.get( n_hrnID );
 201       if( hrn == null ) {
 202         return null;
 203       }
 204
 205       if( !calleeReachableNodes.contains( n_hrnID ) ) {
 206         return null;
 207       }
 208
 209       // when the state is null it is not part of the
 210       // predicate, so we've already satisfied
 211       if( ne_state == null ) {
 212         return hrn.getPreds();
 213       }
 214
 215       // otherwise look for state too
 216       // TODO: contains OR containsSuperSet OR containsWithZeroes??
 217       if( hrn.getAlpha().containsIgnorePreds( ne_state )
 218           == null ) {
 219         return hrn.getPreds();
 220       }
 221
 222       return null;
 223     }
 224
 225     if( predType == TYPE_EDGE ) {
 226
 227       // first establish whether the source of the
 228       // reference edge exists
 229       VariableNode vnSrc = null;
 230       if( e_tdSrc != null ) {
 231         vnSrc = rg.td2vn.get( e_tdSrc );
 232       }
 233       HeapRegionNode hrnSrc = null;
 234       if( e_hrnSrcID != null ) {
 235         hrnSrc = rg.id2hrn.get( e_hrnSrcID );
 236       }
 237       assert (vnSrc == null) || (hrnSrc == null);
 238
 239       // the source is not present in graph
 240       if( vnSrc == null && hrnSrc == null ) {
 241         return null;
 242       }
 243
 244       RefSrcNode rsn;
 245       if( vnSrc != null ) {
 246         rsn = vnSrc;
 247         assert e_srcOutCalleeContext;
 248         assert !e_srcOutCallerContext;
 249
 250       } else {
 251
 252         assert !(e_srcOutCalleeContext && e_srcOutCallerContext);
 253
 254         if( e_srcOutCalleeContext ) {
 255           if( calleeReachableNodes.contains( e_hrnSrcID ) ) {
 256             return null;
 257           }
 258
 259         } else if( e_srcOutCallerContext ) {
 260           if( !hrnSrc.isOutOfContext() ) {
 261             return null;
 262           }
 263
 264         } else {
 265
 266           if( !calleeReachableNodes.contains( e_hrnSrcID ) ) {
 267             return null;
 268           }
 269           if( hrnSrc.isOutOfContext() ) {
 270             return null;
 271           }
 272
 273         }
 274
 275         rsn = hrnSrc;
 276       }
 277
 278       // is the destination present?
 279       HeapRegionNode hrnDst = rg.id2hrn.get( e_hrnDstID );
 280       if( hrnDst == null ) {
 281         return null;
 282       }
 283
 284       if( !calleeReachableNodes.contains( e_hrnDstID ) ) {
 285         return null;
 286       }
 287
 288       // is there an edge between them with the given
 289       // type and field?
 290       // TODO: type OR a subtype?
 291       RefEdge edge = rsn.getReferenceTo( hrnDst,
 292                                          e_type,
 293                                          e_field );
 294       if( edge == null ) {
 295         return null;
 296       }
 297
 298       // only check state as part of the predicate if it
 299       // is non-null
 300       if( ne_state != null &&
 301           // TODO: contains OR containsSuperSet OR containsWithZeroes??
 302           hrnDst.getAlpha().containsIgnorePreds( ne_state ) != null
 303           ) {
 304         return null;
 305       }
 306
 307       // predicate satisfied
 308       return edge.getPreds();
 309     }
 310
 311     throw new Error( "Unknown predicate type" );
 312   }
 313
 314
 315
 316   public boolean equalsSpecific( Object o ) {
 317     if( o == null ) {
 318       return false;
 319     }
 320
 321     if( !(o instanceof ExistPred) ) {
 322       return false;
 323     }
 324
 325     ExistPred pred = (ExistPred) o;
 326
 327     if( this.predType != pred.predType ) {
 328       return false;
 329     }
 330
 331     if( ne_state == null ) {
 332       if( pred.ne_state != null ) {
 333         return false;
 334       }
 335     } else if( !ne_state.equals( pred.ne_state ) ) {
 336       return false;
 337     }
 338
 339     if( n_hrnID == null ) {
 340       if( pred.n_hrnID != null ) {
 341         return false;
 342       }
 343     } else if( !n_hrnID.equals( pred.n_hrnID ) ) {
 344       return false;
 345     }
 346
 347     if( e_tdSrc == null ) {
 348       if( pred.e_tdSrc != null ) {
 349         return false;
 350       }
 351     } else if( !e_tdSrc.equals( pred.e_tdSrc ) ) {
 352       return false;
 353     }
 354
 355     if( e_hrnSrcID == null ) {
 356       if( pred.e_hrnSrcID != null ) {
 357         return false;
 358       }
 359     } else {
 360       if( !e_hrnSrcID.equals( pred.e_hrnSrcID ) ) {
 361         return false;
 362       }
 363       if( e_srcOutCalleeContext != pred.e_srcOutCalleeContext ) {
 364         return false;
 365       }
 366       if( e_srcOutCallerContext != pred.e_srcOutCallerContext ) {
 367         return false;
 368       }
 369     }
 370
 371     if( e_hrnDstID == null ) {
 372       if( pred.e_hrnDstID != null ) {
 373         return false;
 374       }
 375     } else if( !e_hrnDstID.equals( pred.e_hrnDstID ) ) {
 376       return false;
 377     }
 378
 379     if( e_type == null ) {
 380       if( pred.e_type != null ) {
 381         return false;
 382       }
 383     } else if( !e_type.equals( pred.e_type ) ) {
 384       return false;
 385     }
 386
 387     if( e_field == null ) {
 388       if( pred.e_field != null ) {
 389         return false;
 390       }
 391     } else if( !e_field.equals( pred.e_field ) ) {
 392       return false;
 393     }
 394
 395     return true;
 396   }
 397
 398
 399   public int hashCodeSpecific() {
 400     if( predType == TYPE_TRUE ) {
 401       return 1;
 402     }
 403
 404     if( predType == TYPE_NODE ) {
 405       int hash = n_hrnID.intValue()*17;
 406
 407       if( ne_state != null ) {
 408         hash ^= ne_state.hashCode();
 409       }
 410
 411       return hash;
 412     }
 413
 414     if( predType == TYPE_EDGE ) {
 415       int hash = 0;
 416
 417       hash += e_type.hashCode()*17;
 418
 419       if( e_field != null ) {
 420         hash += e_field.hashCode()*7;
 421       }
 422
 423       if( e_tdSrc != null ) {
 424         hash ^= e_tdSrc.hashCode()*11;
 425       } else {
 426         hash ^= e_hrnSrcID.hashCode()*11;
 427         if( e_srcOutCalleeContext ) {
 428           hash ^= 0xf1aeb;
 429         }
 430         if( e_srcOutCallerContext ) {
 431           hash ^= 0x875d;
 432         }
 433       }
 434
 435       hash += e_hrnDstID.hashCode();
 436
 437       if( ne_state != null ) {
 438         hash ^= ne_state.hashCode();
 439       }
 440
 441       return hash;
 442     }
 443
 444     throw new Error( "Unknown predicate type" );
 445   }
 446
 447
 448   public String toString() {
 449     if( predType == TYPE_TRUE ) {
 450       return "t";
 451     }
 452
 453     if( predType == TYPE_NODE ) {
 454       String s = n_hrnID.toString();
 455       if( ne_state != null ) {
 456         s += "w"+ne_state;
 457       }
 458       return s;
 459     }
 460
 461     if( predType == TYPE_EDGE ) {
 462       String s = "(";
 463
 464       if( e_tdSrc != null ) {
 465         s += e_tdSrc.toString();
 466       } else {
 467         s += e_hrnSrcID.toString();
 468       }
 469
 470       if( e_srcOutCalleeContext ) {
 471         s += "(ooCLEEc)";
 472       }
 473
 474       if( e_srcOutCallerContext ) {
 475         s += "(ooCLERc)";
 476       }
 477
 478       s += "-->"+e_hrnDstID+")";
 479
 480       if( ne_state != null ) {
 481         s += "w"+ne_state;
 482       }
 483
 484       return s;
 485     }
 486
 487     throw new Error( "Unknown predicate type" );
 488   }
 489
 490 }