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