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