Robust/src/Analysis/Pointer/GraphManip.java

   1 package Analysis.Pointer;
   2 import IR.Flat.*;
   3 import IR.*;
   4 import Analysis.Pointer.AllocFactory.AllocNode;
   5 import java.util.*;
   6 import Analysis.Disjoint.TaintSet;
   7 import Analysis.Disjoint.Taint;
   8
   9 public class GraphManip {
  10   static MySet<Edge> genEdges(TempDescriptor tmp, HashSet<AllocNode> dstSet) {
  11     MySet<Edge> edgeset=new MySet<Edge>();
  12     for(AllocNode node:dstSet) {
  13       edgeset.add(new Edge(tmp, node));
  14     }
  15     return edgeset;
  16   }
  17
  18   static MySet<Edge> genEdges(TempDescriptor tmp, MySet<Edge> dstSet) {
  19     MySet<Edge> edgeset=new MySet<Edge>();
  20     for(Edge e:dstSet) {
  21       edgeset.add(e.changeSrcVar(tmp, null));
  22     }
  23     return edgeset;
  24   }
  25
  26   static MySet<Edge> genEdges(HashSet<AllocNode> srcSet, FieldDescriptor fd, HashSet<AllocNode> dstSet) {
  27     MySet<Edge> edgeset=new MySet<Edge>();
  28     for(AllocNode srcnode:srcSet) {
  29       for(AllocNode dstnode:dstSet) {
  30         edgeset.add(new Edge(srcnode, fd, dstnode, Edge.NEW));
  31       }
  32     }
  33     return edgeset;
  34   }
  35
  36   static MySet<Edge> genEdges(HashSet<AllocNode> srcSet, FieldDescriptor fd, MySet<Edge> dstSet) {
  37     MySet<Edge> edgeset=new MySet<Edge>();
  38     for(AllocNode srcnode:srcSet) {
  39       for(Edge dstedge:dstSet) {
  40         edgeset.add(dstedge.changeSrc(fd, srcnode));
  41       }
  42     }
  43     return edgeset;
  44   }
  45
  46   static MySet<Edge> getDiffEdges(Delta delta, TempDescriptor tmp) {
  47     MySet<Edge> edges=new MySet<Edge>();
  48     MySet<Edge> removeedges=delta.varedgeremove.get(tmp);
  49
  50     MySet<Edge> baseedges=delta.basevaredge.get(tmp);
  51     if (baseedges!=null) {
  52       for(Edge e:baseedges) {
  53         if (removeedges==null||!removeedges.contains(e))
  54           edges.add(e);
  55       }
  56     }
  57     if (delta.varedgeadd.containsKey(tmp))
  58       for(Edge e:delta.varedgeadd.get(tmp)) {
  59         edges.add(e);
  60       }
  61     return edges;
  62   }
  63
  64   static MySet<Edge> getEdges(Graph graph, Delta delta, TempDescriptor tmp) {
  65     MySet<Edge> edges=new MySet<Edge>();
  66     MySet<Edge> removeedges=delta.varedgeremove.get(tmp);
  67
  68     for(Edge e:graph.getEdges(tmp)) {
  69       if (removeedges==null||!removeedges.contains(e))
  70         edges.add(e);
  71     }
  72     if (delta.varedgeadd.containsKey(tmp))
  73       for(Edge e:delta.varedgeadd.get(tmp)) {
  74         edges.add(e);
  75       }
  76     return edges;
  77   }
  78
  79   static MySet<Edge> getEdges(Graph graph, Delta delta, HashSet<AllocNode> srcNodes, FieldDescriptor fd) {
  80     MySet<Edge> nodes=new MySet<Edge>();
  81     for(AllocNode node:srcNodes) {
  82       MySet<Edge> removeedges=delta.heapedgeremove.get(node);
  83       for(Edge e:graph.getEdges(node)) {
  84         if (e.fd==fd&&(removeedges==null||!removeedges.contains(e)))
  85           nodes.add(e);
  86       }
  87       if (delta.heapedgeadd.containsKey(node))
  88         for(Edge e:delta.heapedgeadd.get(node)) {
  89           if (e.fd==fd)
  90             nodes.add(e);
  91         }
  92     }
  93     return nodes;
  94   }
  95
  96   static MySet<Edge> getEdges(Graph graph, Delta delta, AllocNode node) {
  97     MySet<Edge> nodes=new MySet<Edge>();
  98     MySet<Edge> removeedges=delta.heapedgeremove.get(node);
  99     for(Edge e:graph.getEdges(node)) {
 100       if ((removeedges==null||!removeedges.contains(e)))
 101         nodes.add(e);
 102     }
 103     if (delta.heapedgeadd.containsKey(node))
 104       for(Edge e:delta.heapedgeadd.get(node)) {
 105         nodes.add(e);
 106       }
 107
 108     return nodes;
 109   }
 110
 111   static HashSet<AllocNode> getDiffNodes(Delta delta, TempDescriptor tmp) {
 112     HashSet<AllocNode> nodes=new HashSet<AllocNode>();
 113     MySet<Edge> removeedges=delta.varedgeremove.get(tmp);
 114
 115     MySet<Edge> baseEdges=delta.basevaredge.get(tmp);
 116
 117     if (baseEdges!=null)
 118       for(Edge e:baseEdges) {
 119         if (removeedges==null||!removeedges.contains(e))
 120           nodes.add(e.dst);
 121       }
 122     if (delta.varedgeadd.containsKey(tmp))
 123       for(Edge e:delta.varedgeadd.get(tmp)) {
 124         nodes.add(e.dst);
 125       }
 126     return nodes;
 127   }
 128
 129   static HashSet<AllocNode> getNodes(Graph graph, Delta delta, TempDescriptor tmp) {
 130     HashSet<AllocNode> nodes=new HashSet<AllocNode>();
 131     MySet<Edge> removeedges=delta.varedgeremove.get(tmp);
 132
 133     for(Edge e:graph.getEdges(tmp)) {
 134       if (removeedges==null||!removeedges.contains(e))
 135         nodes.add(e.dst);
 136     }
 137     if (delta.varedgeadd.containsKey(tmp))
 138       for(Edge e:delta.varedgeadd.get(tmp)) {
 139         nodes.add(e.dst);
 140       }
 141     return nodes;
 142   }
 143
 144   static HashSet<AllocNode> getDiffNodes(Delta delta, HashSet<AllocNode> srcNodes, FieldDescriptor fd) {
 145     HashSet<AllocNode> nodes=new HashSet<AllocNode>();
 146     for(AllocNode node:srcNodes) {
 147       MySet<Edge> removeedges=delta.heapedgeremove.get(node);
 148       MySet<Edge> baseEdges=delta.baseheapedge.get(node);
 149       if (baseEdges!=null)
 150         for(Edge e:baseEdges) {
 151           if (e.fd==fd&&(removeedges==null||!removeedges.contains(e)))
 152             nodes.add(e.dst);
 153         }
 154       if (delta.heapedgeadd.containsKey(node))
 155         for(Edge e:delta.heapedgeadd.get(node)) {
 156           if (e.fd==fd)
 157             nodes.add(e.dst);
 158         }
 159     }
 160     return nodes;
 161   }
 162
 163   static MySet<Edge> getDiffEdges(Delta delta, HashSet<AllocNode> srcNodes) {
 164     MySet<Edge> newedges=new MySet<Edge>();
 165     for(Map.Entry<AllocNode, MySet<Edge>> entry:delta.baseheapedge.entrySet()) {
 166       AllocNode node=entry.getKey();
 167       if (srcNodes.contains(node)) {
 168         MySet<Edge> edges=entry.getValue();
 169         MySet<Edge> removeedges=delta.heapedgeremove.get(node);
 170         for(Edge e:edges) {
 171           if (removeedges==null||!removeedges.contains(e)) {
 172             newedges.add(e);
 173           }
 174         }
 175       }
 176     }
 177     for(Map.Entry<AllocNode, MySet<Edge>> entry:delta.heapedgeadd.entrySet()) {
 178       AllocNode node=entry.getKey();
 179       if (srcNodes.contains(node)) {
 180         MySet<Edge> edges=entry.getValue();
 181         newedges.addAll(edges);
 182       }
 183     }
 184     return newedges;
 185   }
 186
 187
 188   static MySet<Edge> getDiffEdges(Delta delta, HashSet<AllocNode> srcNodes, FieldDescriptor fd) {
 189     MySet<Edge> newedges=new MySet<Edge>();
 190     for(Map.Entry<AllocNode, MySet<Edge>> entry:delta.baseheapedge.entrySet()) {
 191       AllocNode node=entry.getKey();
 192       if (srcNodes.contains(node)) {
 193         MySet<Edge> edges=entry.getValue();
 194         MySet<Edge> removeedges=delta.heapedgeremove.get(node);
 195         for(Edge e:edges) {
 196           if ((removeedges==null||!removeedges.contains(e))&&(e.fd==fd)) {
 197             newedges.add(e);
 198           }
 199         }
 200       }
 201     }
 202     for(Map.Entry<AllocNode, MySet<Edge>> entry:delta.heapedgeadd.entrySet()) {
 203       AllocNode node=entry.getKey();
 204       if (srcNodes.contains(node)) {
 205         MySet<Edge> edges=entry.getValue();
 206         for(Edge e:edges) {
 207           if (e.fd==fd)
 208             newedges.add(e);
 209         }
 210       }
 211     }
 212     return newedges;
 213   }
 214
 215   static MySet<Edge> makeOld(MySet<Edge> edgesin) {
 216     MySet<Edge> edgeset=new MySet<Edge>();
 217     for(Edge e:edgesin) {
 218       edgeset.add(e.makeOld());
 219     }
 220     return edgeset;
 221   }
 222
 223   static MySet<Edge> dereference(Graph graph, Delta delta, TempDescriptor dst, MySet<Edge> srcEdges, FieldDescriptor fd, FlatNode fn, TaintSet taint) {
 224     MySet<Edge> edgeset=new MySet<Edge>();
 225     for(Edge edge:srcEdges) {
 226       TaintSet ts=edge.getTaints();
 227       if (ts!=null) {
 228         ts=ts.reTaint(fn);
 229         if (taint!=null)
 230           ts=ts.merge(taint);
 231       } else {
 232         ts=taint;
 233       }
 234       MySet<Edge> removeedges=delta.heapedgeremove.get(edge.dst);
 235       for(Edge e:graph.getEdges(edge.dst)) {
 236         if (e.fd==fd&&(removeedges==null||!removeedges.contains(e))) {
 237           e=e.changeSrcVar(dst, ts);
 238           if (!edgeset.contains(e))
 239             edgeset.add(e);
 240           else {
 241             Edge preve=edgeset.get(e);
 242             e=e.merge(preve);
 243             edgeset.add(e);
 244           }
 245         }
 246       }
 247       if (delta.heapedgeadd.containsKey(edge.dst))
 248         for(Edge e:delta.heapedgeadd.get(edge.dst)) {
 249           if (e.fd==fd) {
 250             e=e.changeSrcVar(dst, ts);
 251             if (!edgeset.contains(e))
 252               edgeset.add(e);
 253             else {
 254               Edge preve=edgeset.get(e);
 255               e=e.merge(preve);
 256               edgeset.add(e);
 257             }
 258           }
 259         }
 260     }
 261     return edgeset;
 262   }
 263
 264   static MySet<Edge> diffDereference(Delta delta, TempDescriptor dst, MySet<Edge> srcEdges, FieldDescriptor fd, FlatNode fn, TaintSet taint) {
 265     MySet<Edge> edgeset=new MySet<Edge>();
 266     for(Edge edge:srcEdges) {
 267       TaintSet ts=edge.getTaints();
 268       if (ts!=null) {
 269         if (taint!=null)
 270           ts=ts.merge(taint);
 271         ts=ts.reTaint(fn);
 272       } else
 273         ts=taint;
 274       MySet<Edge> removeedges=delta.heapedgeremove.get(edge.dst);
 275       if (delta.baseheapedge.containsKey(edge.dst)) {
 276         for(Edge e:delta.baseheapedge.get(edge.dst)) {
 277           if (e.fd==fd&&(removeedges==null||!removeedges.contains(e))) {
 278             e=e.changeSrcVar(dst, ts);
 279             if (!edgeset.contains(e))
 280               edgeset.add(e);
 281             else {
 282               Edge preve=edgeset.get(e);
 283               e=e.merge(preve);
 284               edgeset.add(e);
 285             }
 286           }
 287         }
 288       }
 289       if (delta.heapedgeadd.containsKey(edge.dst))
 290         for(Edge e:delta.heapedgeadd.get(edge.dst)) {
 291           if (e.fd==fd) {
 292             e=e.changeSrcVar(dst, ts);
 293             if (!edgeset.contains(e))
 294               edgeset.add(e);
 295             else {
 296               Edge preve=edgeset.get(e);
 297               e=e.merge(preve);
 298               edgeset.add(e);
 299             }
 300           }
 301         }
 302     }
 303     return edgeset;
 304   }
 305
 306   static HashSet<AllocNode> getNodes(Graph graph, Delta delta, HashSet<AllocNode> srcNodes, FieldDescriptor fd) {
 307     HashSet<AllocNode> nodes=new HashSet<AllocNode>();
 308     for(AllocNode node:srcNodes) {
 309       MySet<Edge> removeedges=delta.heapedgeremove.get(node);
 310       for(Edge e:graph.getEdges(node)) {
 311         if (e.fd==fd&&(removeedges==null||!removeedges.contains(e)))
 312           nodes.add(e.dst);
 313       }
 314       if (delta.heapedgeadd.containsKey(node))
 315         for(Edge e:delta.heapedgeadd.get(node)) {
 316           if (e.fd==fd)
 317             nodes.add(e.dst);
 318         }
 319     }
 320     return nodes;
 321   }
 322 }