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
  15 public class GlobalFlowGraph {
  16
  17   MethodDescriptor md;
  18
  19   Map<NTuple<Location>, GlobalFlowNode> mapLocTupleToNode;
  20   Map<GlobalFlowNode, Set<GlobalFlowNode>> mapFlowNodeToOutNodeSet;
  21
  22   Map<Location, CompositeLocation> mapLocationToInferCompositeLocation;
  23
  24   Map<MethodDescriptor, Map<NTuple<Location>, NTuple<Location>>> mapCalleeToMapCallerArgToCalleeArg;
  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.mapLocationToInferCompositeLocation = new HashMap<Location, CompositeLocation>();
  31     this.mapCalleeToMapCallerArgToCalleeArg =
  32         new HashMap<MethodDescriptor, Map<NTuple<Location>, NTuple<Location>>>();
  33   }
  34
  35   public GlobalFlowNode getFlowNode(NTuple<Location> locTuple) {
  36     if (!mapLocTupleToNode.containsKey(locTuple)) {
  37       GlobalFlowNode node = createNewGlobalFlowNode(locTuple);
  38       mapLocTupleToNode.put(locTuple, node);
  39     }
  40     return mapLocTupleToNode.get(locTuple);
  41   }
  42
  43   private GlobalFlowNode createNewGlobalFlowNode(NTuple<Location> locTuple) {
  44     GlobalFlowNode node = new GlobalFlowNode(locTuple);
  45     return node;
  46   }
  47
  48   public void addMapLocationToInferCompositeLocation(Location loc, CompositeLocation newCompLoc) {
  49     if (mapLocationToInferCompositeLocation.containsKey(loc)) {
  50       // need to do a sanity check
  51       // if the old composite location has the same prefix of the new composite location,
  52       // replace old one with new one
  53       // if both old and new do not share the prefix, throw error
  54       CompositeLocation oldCompLoc = mapLocationToInferCompositeLocation.get(loc);
  55
  56       if (newCompLoc.getSize() > oldCompLoc.getSize()) {
  57         for (int i = 0; i < oldCompLoc.getSize(); i++) {
  58           Location oldLocElement = oldCompLoc.get(i);
  59           Location newLocElement = newCompLoc.get(i);
  60
  61           if (!oldLocElement.equals(newLocElement)) {
  62             throw new Error("Failed to generate a composite location");
  63           }
  64         }
  65         mapLocationToInferCompositeLocation.put(loc, newCompLoc);
  66       }
  67
  68     } else {
  69       mapLocationToInferCompositeLocation.put(loc, newCompLoc);
  70     }
  71   }
  72
  73   public CompositeLocation getCompositeLocation(Location loc) {
  74     if (!mapLocationToInferCompositeLocation.containsKey(loc)) {
  75       CompositeLocation compLoc = new CompositeLocation();
  76       compLoc.addLocation(loc);
  77       mapLocationToInferCompositeLocation.put(loc, compLoc);
  78     }
  79     return mapLocationToInferCompositeLocation.get(loc);
  80   }
  81
  82   public void addValueFlowEdge(NTuple<Location> fromLocTuple, NTuple<Location> toLocTuple) {
  83
  84     GlobalFlowNode fromNode = getFlowNode(fromLocTuple);
  85     GlobalFlowNode toNode = getFlowNode(toLocTuple);
  86
  87     if (!mapFlowNodeToOutNodeSet.containsKey(fromNode)) {
  88       mapFlowNodeToOutNodeSet.put(fromNode, new HashSet<GlobalFlowNode>());
  89     }
  90     mapFlowNodeToOutNodeSet.get(fromNode).add(toNode);
  91
  92     System.out.println("create a global edge from " + fromNode + " to " + toNode);
  93
  94   }
  95
  96   public Set<GlobalFlowNode> getNodeSet() {
  97     Set<GlobalFlowNode> nodeSet = new HashSet<GlobalFlowNode>();
  98     nodeSet.addAll(mapLocTupleToNode.values());
  99     return nodeSet;
 100   }
 101
 102   public Set<GlobalFlowNode> getOutNodeSet(GlobalFlowNode node) {
 103
 104     if (!mapFlowNodeToOutNodeSet.containsKey(node)) {
 105       mapFlowNodeToOutNodeSet.put(node, new HashSet<GlobalFlowNode>());
 106     }
 107
 108     return mapFlowNodeToOutNodeSet.get(node);
 109   }
 110
 111   public void writeGraph(String suffix) {
 112
 113     String graphName = "flowgraph_" + md.toString() + suffix;
 114     graphName = graphName.replaceAll("[\\W]", "");
 115
 116     try {
 117       BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
 118       bw.write("digraph " + graphName + " {\n");
 119       bw.write("compound=true;\n");
 120
 121       // then visit every flow node
 122
 123       // Iterator<FlowNode> iter = nodeSet.iterator();
 124       Iterator<GlobalFlowNode> iter = getNodeSet().iterator();
 125
 126       Set<GlobalFlowNode> addedNodeSet = new HashSet<GlobalFlowNode>();
 127
 128       while (iter.hasNext()) {
 129         GlobalFlowNode srcNode = iter.next();
 130
 131         Set<GlobalFlowNode> outNodeSet = getOutNodeSet(srcNode);
 132         for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
 133           GlobalFlowNode dstNode = (GlobalFlowNode) iterator.next();
 134
 135           if (!addedNodeSet.contains(srcNode)) {
 136             drawNode(srcNode, bw);
 137           }
 138
 139           if (!addedNodeSet.contains(dstNode)) {
 140             drawNode(dstNode, bw);
 141           }
 142
 143           bw.write("" + srcNode.getID() + " -> " + dstNode.getID() + ";\n");
 144
 145         }
 146
 147         // if (node.getDescTuple().size() == 1) {
 148         // // here, we just care about the local variable
 149         // if (node.getFieldNodeSet().size() > 0) {
 150         // drawSubgraph(node, bw, addedEdgeSet);
 151         // }
 152         // }
 153         // drawEdges(node, bw, addedNodeSet, addedEdgeSet);
 154
 155       }
 156
 157       bw.write("}\n");
 158       bw.close();
 159
 160     } catch (IOException e) {
 161       e.printStackTrace();
 162     }
 163   }
 164
 165   private void drawNode(GlobalFlowNode node, BufferedWriter bw) throws IOException {
 166     bw.write(node.getID() + " [label=\"" + node.getPrettyID() + "\"]" + ";\n");
 167   }
 168
 169   public Set<GlobalFlowNode> getIncomingNodeSet(GlobalFlowNode node) {
 170
 171     Set<GlobalFlowNode> incomingNodeSet = new HashSet<GlobalFlowNode>();
 172     recurIncomingNodeSet(node, incomingNodeSet);
 173
 174     return incomingNodeSet;
 175   }
 176
 177   private void recurIncomingNodeSet(GlobalFlowNode node, Set<GlobalFlowNode> visited) {
 178
 179     for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) {
 180       GlobalFlowNode curNode = (GlobalFlowNode) iterator.next();
 181
 182       Set<GlobalFlowNode> outNodeSet = getOutNodeSet(curNode);
 183
 184       for (Iterator iterator2 = outNodeSet.iterator(); iterator2.hasNext();) {
 185         GlobalFlowNode outNode = (GlobalFlowNode) iterator2.next();
 186
 187         if (outNode.equals(node)) {
 188           if (!visited.contains(curNode)) {
 189             visited.add(curNode);
 190             recurIncomingNodeSet(curNode, visited);
 191           }
 192         }
 193       }
 194     }
 195
 196   }
 197
 198   public Set<GlobalFlowNode> getReachableNodeSetFrom(GlobalFlowNode node) {
 199
 200     Set<GlobalFlowNode> reachableNodeSet = new HashSet<GlobalFlowNode>();
 201     recurReachableNodeSet(node, reachableNodeSet);
 202
 203     return reachableNodeSet;
 204   }
 205
 206   private void recurReachableNodeSet(GlobalFlowNode node, Set<GlobalFlowNode> reachableNodeSet) {
 207     Set<GlobalFlowNode> outNodeSet = getOutNodeSet(node);
 208     for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
 209       GlobalFlowNode outNode = (GlobalFlowNode) iterator.next();
 210       if (!reachableNodeSet.contains(outNode)) {
 211         reachableNodeSet.add(outNode);
 212         recurReachableNodeSet(outNode, reachableNodeSet);
 213       }
 214     }
 215   }
 216
 217 }