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