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 void addValueFlowEdge(NTuple<Location> fromLocTuple, NTuple<Location> toLocTuple) {
  93
  94     GlobalFlowNode fromNode = getFlowNode(fromLocTuple);
  95     GlobalFlowNode toNode = getFlowNode(toLocTuple);
  96
  97     if (!mapFlowNodeToOutNodeSet.containsKey(fromNode)) {
  98       mapFlowNodeToOutNodeSet.put(fromNode, new HashSet<GlobalFlowNode>());
  99     }
 100     mapFlowNodeToOutNodeSet.get(fromNode).add(toNode);
 101
 102     if (!mapFlowNodeToInNodeSet.containsKey(toNode)) {
 103       mapFlowNodeToInNodeSet.put(toNode, new HashSet<GlobalFlowNode>());
 104     }
 105     mapFlowNodeToInNodeSet.get(toNode).add(fromNode);
 106
 107     System.out.println("create a global edge from " + fromNode + " to " + toNode);
 108
 109   }
 110
 111   public Set<GlobalFlowNode> getInNodeSet(GlobalFlowNode node) {
 112     if (!mapFlowNodeToInNodeSet.containsKey(node)) {
 113       mapFlowNodeToInNodeSet.put(node, new HashSet<GlobalFlowNode>());
 114     }
 115     return mapFlowNodeToInNodeSet.get(node);
 116   }
 117
 118   public Set<GlobalFlowNode> getNodeSet() {
 119     Set<GlobalFlowNode> nodeSet = new HashSet<GlobalFlowNode>();
 120     nodeSet.addAll(mapLocTupleToNode.values());
 121     return nodeSet;
 122   }
 123
 124   public Set<GlobalFlowNode> getOutNodeSet(GlobalFlowNode node) {
 125
 126     if (!mapFlowNodeToOutNodeSet.containsKey(node)) {
 127       mapFlowNodeToOutNodeSet.put(node, new HashSet<GlobalFlowNode>());
 128     }
 129
 130     return mapFlowNodeToOutNodeSet.get(node);
 131   }
 132
 133   public void writeGraph(String suffix) {
 134
 135     String graphName = "flowgraph_" + md.toString() + suffix;
 136     graphName = graphName.replaceAll("[\\W]", "");
 137
 138     try {
 139       BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
 140       bw.write("digraph " + graphName + " {\n");
 141       bw.write("compound=true;\n");
 142
 143       // then visit every flow node
 144
 145       // Iterator<FlowNode> iter = nodeSet.iterator();
 146       Iterator<GlobalFlowNode> iter = getNodeSet().iterator();
 147
 148       Set<GlobalFlowNode> addedNodeSet = new HashSet<GlobalFlowNode>();
 149
 150       while (iter.hasNext()) {
 151         GlobalFlowNode srcNode = iter.next();
 152
 153         Set<GlobalFlowNode> outNodeSet = getOutNodeSet(srcNode);
 154         for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
 155           GlobalFlowNode dstNode = (GlobalFlowNode) iterator.next();
 156
 157           if (!addedNodeSet.contains(srcNode)) {
 158             drawNode(srcNode, bw);
 159           }
 160
 161           if (!addedNodeSet.contains(dstNode)) {
 162             drawNode(dstNode, bw);
 163           }
 164
 165           bw.write("" + srcNode.getID() + " -> " + dstNode.getID() + ";\n");
 166
 167         }
 168
 169         // if (node.getDescTuple().size() == 1) {
 170         // // here, we just care about the local variable
 171         // if (node.getFieldNodeSet().size() > 0) {
 172         // drawSubgraph(node, bw, addedEdgeSet);
 173         // }
 174         // }
 175         // drawEdges(node, bw, addedNodeSet, addedEdgeSet);
 176
 177       }
 178
 179       bw.write("}\n");
 180       bw.close();
 181
 182     } catch (IOException e) {
 183       e.printStackTrace();
 184     }
 185   }
 186
 187   private void drawNode(GlobalFlowNode node, BufferedWriter bw) throws IOException {
 188     bw.write(node.getID() + " [label=\"" + node.getPrettyID() + "\"]" + ";\n");
 189   }
 190
 191   public Set<GlobalFlowNode> getIncomingNodeSet(GlobalFlowNode node) {
 192
 193     Set<GlobalFlowNode> incomingNodeSet = new HashSet<GlobalFlowNode>();
 194     recurIncomingNodeSet(node, incomingNodeSet);
 195
 196     return incomingNodeSet;
 197   }
 198
 199   private void recurIncomingNodeSet(GlobalFlowNode node, Set<GlobalFlowNode> visited) {
 200
 201     for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) {
 202       GlobalFlowNode curNode = (GlobalFlowNode) iterator.next();
 203
 204       Set<GlobalFlowNode> outNodeSet = getOutNodeSet(curNode);
 205
 206       for (Iterator iterator2 = outNodeSet.iterator(); iterator2.hasNext();) {
 207         GlobalFlowNode outNode = (GlobalFlowNode) iterator2.next();
 208
 209         if (outNode.equals(node)) {
 210           if (!visited.contains(curNode)) {
 211             visited.add(curNode);
 212             recurIncomingNodeSet(curNode, visited);
 213           }
 214         }
 215       }
 216     }
 217
 218   }
 219
 220   public Set<GlobalFlowNode> getIncomingNodeSetByPrefix(Location prefix) {
 221
 222     Set<GlobalFlowNode> incomingNodeSet = new HashSet<GlobalFlowNode>();
 223
 224     for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) {
 225       GlobalFlowNode curNode = (GlobalFlowNode) iterator.next();
 226       Set<GlobalFlowNode> outNodeSet = getOutNodeSet(curNode);
 227
 228       for (Iterator iterator2 = outNodeSet.iterator(); iterator2.hasNext();) {
 229         GlobalFlowNode outNode = (GlobalFlowNode) iterator2.next();
 230
 231         if (outNode.getLocTuple().startsWith(prefix)) {
 232           incomingNodeSet.add(curNode);
 233           recurIncomingNodeSetByPrefix(prefix, curNode, incomingNodeSet);
 234         }
 235
 236       }
 237     }
 238
 239     return incomingNodeSet;
 240
 241   }
 242
 243   private void recurIncomingNodeSetByPrefix(Location prefix, GlobalFlowNode node,
 244       Set<GlobalFlowNode> visited) {
 245
 246     Set<GlobalFlowNode> inNodeSet = getInNodeSet(node);
 247
 248     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
 249       GlobalFlowNode curNode = (GlobalFlowNode) iterator.next();
 250
 251       if (!curNode.getLocTuple().startsWith(prefix) && !visited.contains(curNode)) {
 252         visited.add(curNode);
 253         recurIncomingNodeSetByPrefix(prefix, curNode, visited);
 254       }
 255     }
 256
 257   }
 258
 259   public Set<GlobalFlowNode> getReachableNodeSetByPrefix(Location prefix) {
 260
 261     Set<GlobalFlowNode> reachableNodeSet = new HashSet<GlobalFlowNode>();
 262
 263     for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) {
 264       GlobalFlowNode curNode = (GlobalFlowNode) iterator.next();
 265
 266       if (curNode.getLocTuple().startsWith(prefix)) {
 267         Set<GlobalFlowNode> outNodeSet = getOutNodeSet(curNode);
 268         for (Iterator iterator2 = outNodeSet.iterator(); iterator2.hasNext();) {
 269           GlobalFlowNode outNode = (GlobalFlowNode) iterator2.next();
 270           if (!outNode.getLocTuple().startsWith(prefix) && !reachableNodeSet.contains(outNode)) {
 271             reachableNodeSet.add(outNode);
 272             recurReachableNodeSetByPrefix(prefix, outNode, reachableNodeSet);
 273           }
 274
 275         }
 276       }
 277     }
 278
 279     return reachableNodeSet;
 280   }
 281
 282   private void recurReachableNodeSetByPrefix(Location prefix, GlobalFlowNode node,
 283       Set<GlobalFlowNode> reachableNodeSet) {
 284     Set<GlobalFlowNode> outNodeSet = getOutNodeSet(node);
 285     for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
 286       GlobalFlowNode outNode = (GlobalFlowNode) iterator.next();
 287       if (!outNode.getLocTuple().startsWith(prefix) && !reachableNodeSet.contains(outNode)) {
 288         reachableNodeSet.add(outNode);
 289         recurReachableNodeSetByPrefix(prefix, outNode, reachableNodeSet);
 290       }
 291     }
 292   }
 293
 294   public Set<GlobalFlowNode> getReachableNodeSetFrom(GlobalFlowNode node) {
 295
 296     Set<GlobalFlowNode> reachableNodeSet = new HashSet<GlobalFlowNode>();
 297     recurReachableNodeSet(node, reachableNodeSet);
 298
 299     return reachableNodeSet;
 300   }
 301
 302   private void recurReachableNodeSet(GlobalFlowNode node, Set<GlobalFlowNode> reachableNodeSet) {
 303     Set<GlobalFlowNode> outNodeSet = getOutNodeSet(node);
 304     for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
 305       GlobalFlowNode outNode = (GlobalFlowNode) iterator.next();
 306       if (!reachableNodeSet.contains(outNode)) {
 307         reachableNodeSet.add(outNode);
 308         recurReachableNodeSet(outNode, reachableNodeSet);
 309       }
 310     }
 311   }
 312
 313 }