Robust/src/Analysis/SSJava/GlobalFlowGraph.java

   1 package Analysis.SSJava;
   2
   3 import java.io.BufferedWriter;
   4 import java.io.FileWriter;
   5 import java.io.IOException;
   6 import java.util.HashMap;
   7 import java.util.HashSet;
   8 import java.util.Iterator;
   9 import java.util.Map;
  10 import java.util.Set;
  11
  12 import IR.Descriptor;
  13 import IR.MethodDescriptor;
  14 import IR.Tree.MethodInvokeNode;
  15
  16 public class GlobalFlowGraph {
  17
  18   MethodDescriptor md;
  19
  20   Map<NTuple<Location>, GlobalFlowNode> mapLocTupleToNode;
  21   Map<GlobalFlowNode, Set<GlobalFlowNode>> mapFlowNodeToOutNodeSet;
  22   Map<GlobalFlowNode, Set<GlobalFlowNode>> mapFlowNodeToInNodeSet;
  23
  24   Map<Location, CompositeLocation> mapLocationToInferCompositeLocation;
  25
  26   public GlobalFlowGraph(MethodDescriptor md) {
  27     this.md = md;
  28     this.mapLocTupleToNode = new HashMap<NTuple<Location>, GlobalFlowNode>();
  29     this.mapFlowNodeToOutNodeSet = new HashMap<GlobalFlowNode, Set<GlobalFlowNode>>();
  30     this.mapFlowNodeToInNodeSet = new HashMap<GlobalFlowNode, Set<GlobalFlowNode>>();
  31
  32     this.mapLocationToInferCompositeLocation = new HashMap<Location, CompositeLocation>();
  33   }
  34
  35   public MethodDescriptor getMethodDescriptor() {
  36     return md;
  37   }
  38
  39   public Map<Location, CompositeLocation> getMapLocationToInferCompositeLocation() {
  40     return mapLocationToInferCompositeLocation;
  41   }
  42
  43   public GlobalFlowNode getFlowNode(NTuple<Location> locTuple) {
  44     if (!mapLocTupleToNode.containsKey(locTuple)) {
  45       GlobalFlowNode node = createNewGlobalFlowNode(locTuple);
  46       mapLocTupleToNode.put(locTuple, node);
  47     }
  48     return mapLocTupleToNode.get(locTuple);
  49   }
  50
  51   private GlobalFlowNode createNewGlobalFlowNode(NTuple<Location> locTuple) {
  52     GlobalFlowNode node = new GlobalFlowNode(locTuple);
  53     return node;
  54   }
  55
  56   public void addMapLocationToInferCompositeLocation(Location loc, CompositeLocation newCompLoc) {
  57     if (mapLocationToInferCompositeLocation.containsKey(loc)) {
  58       // need to do a sanity check
  59       // if the old composite location has the same prefix of the new composite location,
  60       // replace old one with new one
  61       // if both old and new do not share the prefix, throw error
  62       CompositeLocation oldCompLoc = mapLocationToInferCompositeLocation.get(loc);
  63
  64       if (newCompLoc.getSize() == oldCompLoc.getSize()) {
  65         for (int i = 0; i < oldCompLoc.getSize() - 1; i++) {
  66           Location oldLocElement = oldCompLoc.get(i);
  67           Location newLocElement = newCompLoc.get(i);
  68
  69           if (!oldLocElement.equals(newLocElement)) {
  70             throw new Error("Failed to generate a composite location. The old composite location="
  71                 + oldCompLoc + " and the new composite location=" + newCompLoc);
  72           }
  73         }
  74       } else if (newCompLoc.getSize() > oldCompLoc.getSize()) {
  75         mapLocationToInferCompositeLocation.put(loc, newCompLoc);
  76       }
  77
  78     } else {
  79       mapLocationToInferCompositeLocation.put(loc, newCompLoc);
  80     }
  81   }
  82
  83   public CompositeLocation getCompositeLocation(Location loc) {
  84     if (!mapLocationToInferCompositeLocation.containsKey(loc)) {
  85       CompositeLocation compLoc = new CompositeLocation();
  86       compLoc.addLocation(loc);
  87       mapLocationToInferCompositeLocation.put(loc, compLoc);
  88     }
  89     return mapLocationToInferCompositeLocation.get(loc);
  90   }
  91
  92   public boolean hasValueFlowEdge(NTuple<Location> fromLocTuple, NTuple<Location> toLocTuple) {
  93
  94     // return true if the graph already has a flow edge
  95
  96     if (!mapLocTupleToNode.containsKey(fromLocTuple) || !mapLocTupleToNode.containsKey(toLocTuple)) {
  97       return false;
  98     }
  99
 100     GlobalFlowNode fromNode = getFlowNode(fromLocTuple);
 101     GlobalFlowNode toNode = getFlowNode(toLocTuple);
 102
 103     if (!mapFlowNodeToOutNodeSet.containsKey(fromNode)
 104         || !mapFlowNodeToInNodeSet.containsKey(toNode)) {
 105       return false;
 106     }
 107
 108     if (mapFlowNodeToOutNodeSet.get(fromNode).contains(toNode)
 109         && mapFlowNodeToInNodeSet.get(toNode).contains(fromNode)) {
 110       return true;
 111     }
 112
 113     return false;
 114   }
 115
 116   public void addValueFlowEdge(NTuple<Location> fromLocTuple, NTuple<Location> toLocTuple) {
 117
 118     Location lastElementfromLocTuple = fromLocTuple.get(fromLocTuple.size() - 1);
 119     if (lastElementfromLocTuple.getLocDescriptor().equals(LocationInference.LITERALDESC)) {
 120       return;
 121     }
 122
 123     GlobalFlowNode fromNode = getFlowNode(fromLocTuple);
 124     GlobalFlowNode toNode = getFlowNode(toLocTuple);
 125
 126     if (!mapFlowNodeToOutNodeSet.containsKey(fromNode)) {
 127       mapFlowNodeToOutNodeSet.put(fromNode, new HashSet<GlobalFlowNode>());
 128     }
 129     mapFlowNodeToOutNodeSet.get(fromNode).add(toNode);
 130
 131     if (!mapFlowNodeToInNodeSet.containsKey(toNode)) {
 132       mapFlowNodeToInNodeSet.put(toNode, new HashSet<GlobalFlowNode>());
 133     }
 134     mapFlowNodeToInNodeSet.get(toNode).add(fromNode);
 135
 136     // System.out.println("create a global edge from " + fromNode + " to " + toNode);
 137
 138   }
 139
 140   public Set<GlobalFlowNode> getInNodeSet(GlobalFlowNode node) {
 141     if (!mapFlowNodeToInNodeSet.containsKey(node)) {
 142       mapFlowNodeToInNodeSet.put(node, new HashSet<GlobalFlowNode>());
 143     }
 144     return mapFlowNodeToInNodeSet.get(node);
 145   }
 146
 147   public Set<GlobalFlowNode> getNodeSet() {
 148     Set<GlobalFlowNode> nodeSet = new HashSet<GlobalFlowNode>();
 149     nodeSet.addAll(mapLocTupleToNode.values());
 150     return nodeSet;
 151   }
 152
 153   public Set<GlobalFlowNode> getOutNodeSet(GlobalFlowNode node) {
 154
 155     if (!mapFlowNodeToOutNodeSet.containsKey(node)) {
 156       mapFlowNodeToOutNodeSet.put(node, new HashSet<GlobalFlowNode>());
 157     }
 158
 159     return mapFlowNodeToOutNodeSet.get(node);
 160   }
 161
 162   public void writeGraph(String suffix) {
 163
 164     String graphName = "flowgraph_" + md.toString() + suffix;
 165     graphName = graphName.replaceAll("[\\W]", "");
 166
 167     try {
 168       BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
 169       bw.write("digraph " + graphName + " {\n");
 170       bw.write("compound=true;\n");
 171
 172       // then visit every flow node
 173
 174       // Iterator<FlowNode> iter = nodeSet.iterator();
 175       Iterator<GlobalFlowNode> iter = getNodeSet().iterator();
 176
 177       Set<GlobalFlowNode> addedNodeSet = new HashSet<GlobalFlowNode>();
 178
 179       while (iter.hasNext()) {
 180         GlobalFlowNode srcNode = iter.next();
 181
 182         Set<GlobalFlowNode> outNodeSet = getOutNodeSet(srcNode);
 183         for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
 184           GlobalFlowNode dstNode = (GlobalFlowNode) iterator.next();
 185
 186           if (!addedNodeSet.contains(srcNode)) {
 187             drawNode(srcNode, bw);
 188           }
 189
 190           if (!addedNodeSet.contains(dstNode)) {
 191             drawNode(dstNode, bw);
 192           }
 193
 194           bw.write("" + srcNode.getID() + " -> " + dstNode.getID() + ";\n");
 195
 196         }
 197
 198         // if (node.getDescTuple().size() == 1) {
 199         // // here, we just care about the local variable
 200         // if (node.getFieldNodeSet().size() > 0) {
 201         // drawSubgraph(node, bw, addedEdgeSet);
 202         // }
 203         // }
 204         // drawEdges(node, bw, addedNodeSet, addedEdgeSet);
 205
 206       }
 207
 208       bw.write("}\n");
 209       bw.close();
 210
 211     } catch (IOException e) {
 212       e.printStackTrace();
 213     }
 214   }
 215
 216   private void drawNode(GlobalFlowNode node, BufferedWriter bw) throws IOException {
 217     bw.write(node.getID() + " [label=\"" + node.getPrettyID() + "\"]" + ";\n");
 218   }
 219
 220   public Set<GlobalFlowNode> getIncomingNodeSet(GlobalFlowNode node) {
 221
 222     Set<GlobalFlowNode> incomingNodeSet = new HashSet<GlobalFlowNode>();
 223     recurIncomingNodeSet(node, incomingNodeSet);
 224
 225     return incomingNodeSet;
 226   }
 227
 228   private void recurIncomingNodeSet(GlobalFlowNode node, Set<GlobalFlowNode> visited) {
 229
 230     for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) {
 231       GlobalFlowNode curNode = (GlobalFlowNode) iterator.next();
 232
 233       Set<GlobalFlowNode> outNodeSet = getOutNodeSet(curNode);
 234
 235       for (Iterator iterator2 = outNodeSet.iterator(); iterator2.hasNext();) {
 236         GlobalFlowNode outNode = (GlobalFlowNode) iterator2.next();
 237
 238         if (outNode.equals(node)) {
 239           if (!visited.contains(curNode)) {
 240             visited.add(curNode);
 241             recurIncomingNodeSet(curNode, visited);
 242           }
 243         }
 244       }
 245     }
 246
 247   }
 248
 249   public Set<GlobalFlowNode> getIncomingNodeSetByPrefix(Location prefix) {
 250
 251     Set<GlobalFlowNode> incomingNodeSet = new HashSet<GlobalFlowNode>();
 252
 253     for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) {
 254       GlobalFlowNode curNode = (GlobalFlowNode) iterator.next();
 255       Set<GlobalFlowNode> outNodeSet = getOutNodeSet(curNode);
 256
 257       for (Iterator iterator2 = outNodeSet.iterator(); iterator2.hasNext();) {
 258         GlobalFlowNode outNode = (GlobalFlowNode) iterator2.next();
 259
 260         if (outNode.getLocTuple().startsWith(prefix)) {
 261           incomingNodeSet.add(curNode);
 262           recurIncomingNodeSetByPrefix(prefix, curNode, incomingNodeSet);
 263         }
 264
 265       }
 266     }
 267
 268     return incomingNodeSet;
 269
 270   }
 271
 272   private void recurIncomingNodeSetByPrefix(Location prefix, GlobalFlowNode node,
 273       Set<GlobalFlowNode> visited) {
 274
 275     Set<GlobalFlowNode> inNodeSet = getInNodeSet(node);
 276
 277     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
 278       GlobalFlowNode curNode = (GlobalFlowNode) iterator.next();
 279
 280       if (!curNode.getLocTuple().startsWith(prefix) && !visited.contains(curNode)) {
 281         visited.add(curNode);
 282         recurIncomingNodeSetByPrefix(prefix, curNode, visited);
 283       }
 284     }
 285
 286   }
 287
 288   public Set<GlobalFlowNode> getReachableNodeSetByPrefix(Location prefix) {
 289
 290     Set<GlobalFlowNode> reachableNodeSet = new HashSet<GlobalFlowNode>();
 291
 292     for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) {
 293       GlobalFlowNode curNode = (GlobalFlowNode) iterator.next();
 294
 295       if (curNode.getLocTuple().startsWith(prefix)) {
 296         Set<GlobalFlowNode> outNodeSet = getOutNodeSet(curNode);
 297         for (Iterator iterator2 = outNodeSet.iterator(); iterator2.hasNext();) {
 298           GlobalFlowNode outNode = (GlobalFlowNode) iterator2.next();
 299           if (!outNode.getLocTuple().startsWith(prefix) && !reachableNodeSet.contains(outNode)) {
 300             reachableNodeSet.add(outNode);
 301             recurReachableNodeSetByPrefix(prefix, outNode, reachableNodeSet);
 302           }
 303
 304         }
 305       }
 306     }
 307
 308     return reachableNodeSet;
 309   }
 310
 311   private void recurReachableNodeSetByPrefix(Location prefix, GlobalFlowNode node,
 312       Set<GlobalFlowNode> reachableNodeSet) {
 313     Set<GlobalFlowNode> outNodeSet = getOutNodeSet(node);
 314     for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
 315       GlobalFlowNode outNode = (GlobalFlowNode) iterator.next();
 316       if (!outNode.getLocTuple().startsWith(prefix) && !reachableNodeSet.contains(outNode)) {
 317         reachableNodeSet.add(outNode);
 318         recurReachableNodeSetByPrefix(prefix, outNode, reachableNodeSet);
 319       }
 320     }
 321   }
 322
 323   public Set<GlobalFlowNode> getReachableNodeSetFrom(GlobalFlowNode node) {
 324
 325     Set<GlobalFlowNode> reachableNodeSet = new HashSet<GlobalFlowNode>();
 326     recurReachableNodeSet(node, reachableNodeSet);
 327
 328     return reachableNodeSet;
 329   }
 330
 331   private void recurReachableNodeSet(GlobalFlowNode node, Set<GlobalFlowNode> reachableNodeSet) {
 332     Set<GlobalFlowNode> outNodeSet = getOutNodeSet(node);
 333     for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
 334       GlobalFlowNode outNode = (GlobalFlowNode) iterator.next();
 335       if (!reachableNodeSet.contains(outNode)) {
 336         reachableNodeSet.add(outNode);
 337         recurReachableNodeSet(outNode, reachableNodeSet);
 338       }
 339     }
 340   }
 341
 342 }