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