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