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