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     if (taint!=null) {
 252       edgeset.addAll(Edge.taintAll(srcEdges, taint));
 253     }
 254     for(Edge edge:srcEdges) {
 255       TaintSet ts=edge.getTaints();
 256       if (ts!=null) {
 257         ts=ts.reTaint(fn);
 258         if (taint!=null)
 259           ts=ts.merge(taint);
 260       } else {
 261         ts=taint;
 262       }
 263       MySet<Edge> removeedges=delta.heapedgeremove.get(edge.dst);
 264       for(Edge e:graph.getEdges(edge.dst)) {
 265         if (e.fd==fd&&(removeedges==null||!removeedges.contains(e))) {
 266           e=e.changeSrcVar(dst, ts);
 267           if (!edgeset.contains(e))
 268             edgeset.add(e);
 269           else {
 270             Edge preve=edgeset.get(e);
 271             e=e.merge(preve);
 272             edgeset.add(e);
 273           }
 274         }
 275       }
 276       if (delta.heapedgeadd.containsKey(edge.dst))
 277         for(Edge e:delta.heapedgeadd.get(edge.dst)) {
 278           if (e.fd==fd) {
 279             e=e.changeSrcVar(dst, ts);
 280             if (!edgeset.contains(e))
 281               edgeset.add(e);
 282             else {
 283               Edge preve=edgeset.get(e);
 284               e=e.merge(preve);
 285               edgeset.add(e);
 286             }
 287           }
 288         }
 289     }
 290     return edgeset;
 291   }
 292
 293   static MySet<Edge> diffDereference(Delta delta, TempDescriptor dst, MySet<Edge> srcEdges, FieldDescriptor fd, FlatNode fn, TaintSet taint) {
 294     MySet<Edge> edgeset=new MySet<Edge>();
 295     for(Edge edge:srcEdges) {
 296       TaintSet ts=edge.getTaints();
 297       if (ts!=null) {
 298         if (taint!=null)
 299           ts=ts.merge(taint);
 300         ts=ts.reTaint(fn);
 301       } else
 302         ts=taint;
 303       MySet<Edge> removeedges=delta.heapedgeremove.get(edge.dst);
 304       if (delta.baseheapedge.containsKey(edge.dst)) {
 305         for(Edge e:delta.baseheapedge.get(edge.dst)) {
 306           if (e.fd==fd&&(removeedges==null||!removeedges.contains(e))) {
 307             e=e.changeSrcVar(dst, ts);
 308             if (!edgeset.contains(e))
 309               edgeset.add(e);
 310             else {
 311               Edge preve=edgeset.get(e);
 312               e=e.merge(preve);
 313               edgeset.add(e);
 314             }
 315           }
 316         }
 317       }
 318       if (delta.heapedgeadd.containsKey(edge.dst))
 319         for(Edge e:delta.heapedgeadd.get(edge.dst)) {
 320           if (e.fd==fd) {
 321             e=e.changeSrcVar(dst, ts);
 322             if (!edgeset.contains(e))
 323               edgeset.add(e);
 324             else {
 325               Edge preve=edgeset.get(e);
 326               e=e.merge(preve);
 327               edgeset.add(e);
 328             }
 329           }
 330         }
 331     }
 332     return edgeset;
 333   }
 334
 335   static HashSet<AllocNode> getNodes(Graph graph, Delta delta, HashSet<AllocNode> srcNodes, FieldDescriptor fd) {
 336     HashSet<AllocNode> nodes=new HashSet<AllocNode>();
 337     for(AllocNode node:srcNodes) {
 338       MySet<Edge> removeedges=delta.heapedgeremove.get(node);
 339       for(Edge e:graph.getEdges(node)) {
 340         if (e.fd==fd&&(removeedges==null||!removeedges.contains(e)))
 341           nodes.add(e.dst);
 342       }
 343       if (delta.heapedgeadd.containsKey(node))
 344         for(Edge e:delta.heapedgeadd.get(node)) {
 345           if (e.fd==fd)
 346             nodes.add(e.dst);
 347         }
 348     }
 349     return nodes;
 350   }
 351 }