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