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