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