Robust/src/Analysis/Pointer/Edge.java

   1 package Analysis.Pointer;
   2 import IR.Flat.*;
   3 import IR.*;
   4 import Analysis.Pointer.AllocFactory.AllocNode;
   5 import Analysis.Disjoint.Canonical;
   6 import Analysis.Disjoint.Taint;
   7 import Analysis.Disjoint.TaintSet;
   8 import Analysis.Pointer.MySet;
   9 import java.util.*;
  10
  11 public class Edge {
  12   FieldDescriptor fd;
  13   AllocNode src;
  14   TempDescriptor srcvar;
  15   AllocNode dst;
  16   int statuspredicate;
  17   TaintSet taints;
  18
  19   public static final int SNGSNG=1;
  20   public static final int SNGSUM=2;
  21   public static final int SUMSNG=4;
  22   public static final int SUMSUM=8;
  23   public static final int NEW=16;
  24   public static final int MASK=15;
  25
  26   public String toString() {
  27     String taintlist="";
  28     if (taints!=null)
  29       taintlist=", "+taints.toString();
  30     if (srcvar!=null)
  31       return "<"+srcvar+", "+dst+taintlist+">";
  32     else if (fd!=null)
  33       return "<"+src+", "+statuspredicate+", "+fd+", "+dst+taintlist+ ">";
  34     else
  35       return "<"+src+", "+statuspredicate+", [], "+dst+taintlist+">";
  36   }
  37
  38   public static int mergeStatus(int stat1, int stat2) {
  39     int status=stat1|stat2;
  40     return ((status&NEW)==NEW)?NEW:status;
  41   }
  42
  43   public boolean isNew() {
  44     return (statuspredicate&NEW)==NEW;
  45   }
  46
  47   private Edge() {
  48   }
  49
  50   public Edge(AllocNode src, FieldDescriptor fd, AllocNode dst) {
  51     this.src=src;
  52     this.fd=fd;
  53     this.dst=dst;
  54   }
  55
  56   public Edge(AllocNode src, FieldDescriptor fd, AllocNode dst, int statuspredicate) {
  57     this.src=src;
  58     this.fd=fd;
  59     this.dst=dst;
  60     this.statuspredicate=statuspredicate;
  61   }
  62
  63   public Edge(TempDescriptor tmp, AllocNode dst) {
  64     this.srcvar=tmp;
  65     this.dst=dst;
  66   }
  67
  68   public AllocNode getDst() {
  69     return dst;
  70   }
  71
  72   public int hashCode() {
  73     int hashcode=dst.hashCode();
  74     if (fd!=null) {
  75       hashcode^=fd.hashCode();
  76     }
  77     if (src!=null) {
  78       hashcode^=(src.hashCode()<<3);
  79     } else {
  80       hashcode^=(srcvar.hashCode()<<3);
  81     }
  82     return hashcode;
  83   }
  84
  85   public Edge addTaint(Taint t) {
  86     Edge newe=copy();
  87     if (newe.taints==null)
  88       newe.taints=TaintSet.factory(t);
  89     else
  90       newe.taints=newe.taints.add(t);
  91     return newe;
  92   }
  93
  94   public Edge addTaintSet(TaintSet t) {
  95     Edge newe=copy();
  96     if (newe.taints==null)
  97       newe.taints=t;
  98     else
  99       newe.taints=newe.taints.merge(t);
 100     return newe;
 101   }
 102
 103   public void taintModify(Set<FlatSESEEnterNode> seseSet) {
 104     if (taints!=null) {
 105       taints=Canonical.removeSESETaints(taints, seseSet);
 106     }
 107   }
 108
 109   public TaintSet getTaints() {
 110     return taints;
 111   }
 112
 113   public String taintString() {
 114     if (taints==null)
 115       return "";
 116     else
 117       return taints.toString();
 118   }
 119
 120   public Edge changeTaintSet(TaintSet ts) {
 121     Edge newe=copy();
 122     newe.taints=ts;
 123     return newe;
 124   }
 125
 126   public boolean equals(Object o) {
 127     if (o instanceof Edge) {
 128       Edge e=(Edge) o;
 129       if (srcvar!=null) {
 130         return (srcvar==e.srcvar)&&(dst==e.dst);
 131       } else {
 132         return (src==e.src)&&(dst==e.dst)&&(fd==e.fd);
 133       }
 134     }
 135     return false;
 136   }
 137
 138   public Edge changeSrcVar(TempDescriptor tmp, TaintSet taintset) {
 139     Edge e=new Edge();
 140     e.fd=fd;
 141     e.srcvar=tmp;
 142     e.dst=dst;
 143     e.statuspredicate=NEW;
 144     if (taints==null)
 145       e.taints=taintset;
 146     else if (taintset==null)
 147       e.taints=taints;
 148     else
 149       e.taints=taints.merge(taintset);
 150     return e;
 151   }
 152
 153   public Edge changeSrc(FieldDescriptor newfd, AllocNode srcnode) {
 154     Edge e=new Edge();
 155     e.fd=newfd;
 156     e.src=srcnode;
 157     e.dst=dst;
 158     e.statuspredicate=NEW;
 159     if (taints!=null)
 160       e.taints=taints;
 161     return e;
 162   }
 163
 164   public Edge copy() {
 165     Edge e=new Edge();
 166     e.fd=fd;
 167     e.src=src;
 168     e.srcvar=srcvar;
 169     e.dst=dst;
 170     e.statuspredicate=statuspredicate;
 171     if (taints!=null)
 172       e.taints=taints;
 173     return e;
 174   }
 175
 176   public Edge merge(Edge e) {
 177     if (e==null)
 178       return this;
 179     Edge newe=copy();
 180     newe.statuspredicate=mergeStatus(statuspredicate, e.statuspredicate);
 181     if (e.taints!=null) {
 182       if (newe.taints==null)
 183         newe.taints=e.taints;
 184       else
 185         newe.taints=newe.taints.merge(e.taints);
 186     }
 187     return newe;
 188   }
 189
 190   public Edge rewrite(AllocNode single, AllocNode summary) {
 191     Edge e=copy();
 192     if (e.src==single)
 193       e.src=summary;
 194     if (e.dst==single)
 195       e.dst=summary;
 196     return e;
 197   }
 198
 199   public Edge rewrite(TempDescriptor orig, TempDescriptor newtmp) {
 200     Edge e=copy();
 201     if (e.srcvar!=orig)
 202       throw new Error("Mismatched temps");
 203     e.srcvar=newtmp;
 204     return e;
 205   }
 206
 207   public Edge[] makeStatus(AllocFactory factory) {
 208     int numedges=Integer.bitCount(statuspredicate&MASK);
 209
 210     Edge[] earray=new Edge[numedges];
 211     int mask=1;
 212     int edgeindex=0;
 213     for(int count=0; count<4; count++) {
 214       if ((mask&statuspredicate)==mask) {
 215         Edge e=new Edge();
 216         e.fd=fd;
 217         e.src=factory.getAllocNode(src, (mask&3)==0);
 218         e.dst=factory.getAllocNode(dst, (mask&5)==0);
 219         earray[edgeindex++]=e;
 220       }
 221       mask=mask<<1;
 222     }
 223     return earray;
 224   }
 225
 226   public boolean subsumes(Edge e) {
 227     return subsumes(this.statuspredicate, e.statuspredicate)&&subsumes(this.taints, e.taints);
 228   }
 229
 230   public static boolean subsumes(TaintSet ts1, TaintSet ts2) {
 231     if (ts2==null)
 232       return true;
 233     if (ts1==null) {
 234       if (ts2.isEmpty())
 235         return true;
 236       else
 237         return false;
 238     }
 239     //Neither is null
 240     //Do a set comparison
 241     //do merge + equals...faster than subset...
 242     TaintSet tsmerge=ts1.merge(ts2);
 243     return tsmerge.equals(ts1);
 244   }
 245
 246   public static boolean subsumes(int status1, int status2) {
 247     return ((status1&NEW)==NEW)||((status1|status2)==status1);
 248   }
 249
 250   public Edge makeOld() {
 251     Edge e=new Edge();
 252     e.fd=fd;
 253     e.src=src;
 254     e.srcvar=srcvar;
 255     e.dst=dst;
 256     e.taints=taints;
 257     int val=1;
 258     if (dst.isSummary())
 259       val=val<<1;
 260     if (src.isSummary())
 261       val=val<<2;
 262     e.statuspredicate=val;
 263     return e;
 264   }
 265
 266   public static MySet<Edge> makeOld(MySet<Edge> old) {
 267     MySet<Edge> newedge=new MySet<Edge>();
 268     for(Edge eold : old) {
 269       newedge.add(eold.makeOld());
 270     }
 271     return newedge;
 272   }
 273
 274   public static void mergeEdgesInto(MySet<Edge> orig, MySet<Edge> merge) {
 275     for(Edge e : merge) {
 276       if (orig.contains(e)) {
 277         Edge old=orig.get(e);
 278         e=e.merge(old);
 279       }
 280       orig.add(e);
 281     }
 282   }
 283
 284   public static MySet<Edge> taintAll(MySet<Edge> orig, Taint t) {
 285     MySet<Edge> taintedEdges=new MySet<Edge>();
 286     for(Edge e : orig) {
 287       taintedEdges.add(e.addTaint(t));
 288     }
 289     return taintedEdges;
 290   }
 291
 292   public static MySet<Edge> taintAll(MySet<Edge> orig, TaintSet t) {
 293     MySet<Edge> taintedEdges=new MySet<Edge>();
 294     for(Edge e : orig) {
 295       taintedEdges.add(e.addTaintSet(t));
 296     }
 297     return taintedEdges;
 298   }
 299
 300   public static void mergeEdgeInto(MySet<Edge> orig, Edge e) {
 301     if (orig.contains(e)) {
 302       Edge old=orig.get(e);
 303       e=e.merge(old);
 304     }
 305     orig.add(e);
 306   }
 307
 308   public AllocNode getSrcAlloc() {
 309     return src;
 310   }
 311
 312   public AllocNode getDstAlloc() {
 313     return dst;
 314   }
 315
 316   public FieldDescriptor getFieldDesc() {
 317     return fd;
 318   }
 319 }