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