1 package Analysis.SSJava;
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;
13 import IR.MethodDescriptor;
14 import IR.Tree.MethodInvokeNode;
16 public class GlobalFlowGraph {
20 Map<NTuple<Location>, GlobalFlowNode> mapLocTupleToNode;
21 Map<GlobalFlowNode, Set<GlobalFlowNode>> mapFlowNodeToOutNodeSet;
22 Map<GlobalFlowNode, Set<GlobalFlowNode>> mapFlowNodeToInNodeSet;
24 Map<Location, CompositeLocation> mapLocationToInferCompositeLocation;
26 public GlobalFlowGraph(MethodDescriptor 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>>();
32 this.mapLocationToInferCompositeLocation = new HashMap<Location, CompositeLocation>();
35 public MethodDescriptor getMethodDescriptor() {
39 public Map<Location, CompositeLocation> getMapLocationToInferCompositeLocation() {
40 return mapLocationToInferCompositeLocation;
43 public GlobalFlowNode getFlowNode(NTuple<Location> locTuple) {
44 if (!mapLocTupleToNode.containsKey(locTuple)) {
45 GlobalFlowNode node = createNewGlobalFlowNode(locTuple);
46 mapLocTupleToNode.put(locTuple, node);
48 return mapLocTupleToNode.get(locTuple);
51 private GlobalFlowNode createNewGlobalFlowNode(NTuple<Location> locTuple) {
52 GlobalFlowNode node = new GlobalFlowNode(locTuple);
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);
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);
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);
74 } else if (newCompLoc.getSize() > oldCompLoc.getSize()) {
75 mapLocationToInferCompositeLocation.put(loc, newCompLoc);
79 mapLocationToInferCompositeLocation.put(loc, newCompLoc);
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);
89 return mapLocationToInferCompositeLocation.get(loc);
92 public boolean hasValueFlowEdge(NTuple<Location> fromLocTuple, NTuple<Location> toLocTuple) {
94 // return true if the graph already has a flow edge
96 if (!mapLocTupleToNode.containsKey(fromLocTuple) || !mapLocTupleToNode.containsKey(toLocTuple)) {
100 GlobalFlowNode fromNode = getFlowNode(fromLocTuple);
101 GlobalFlowNode toNode = getFlowNode(toLocTuple);
103 if (!mapFlowNodeToOutNodeSet.containsKey(fromNode)
104 || !mapFlowNodeToInNodeSet.containsKey(toNode)) {
108 if (mapFlowNodeToOutNodeSet.get(fromNode).contains(toNode)
109 && mapFlowNodeToInNodeSet.get(toNode).contains(fromNode)) {
116 public void addValueFlowEdge(NTuple<Location> fromLocTuple, NTuple<Location> toLocTuple) {
118 Location lastElementfromLocTuple = fromLocTuple.get(fromLocTuple.size() - 1);
119 if (lastElementfromLocTuple.getLocDescriptor().equals(LocationInference.LITERALDESC)) {
123 GlobalFlowNode fromNode = getFlowNode(fromLocTuple);
124 GlobalFlowNode toNode = getFlowNode(toLocTuple);
126 if (!mapFlowNodeToOutNodeSet.containsKey(fromNode)) {
127 mapFlowNodeToOutNodeSet.put(fromNode, new HashSet<GlobalFlowNode>());
129 mapFlowNodeToOutNodeSet.get(fromNode).add(toNode);
131 if (!mapFlowNodeToInNodeSet.containsKey(toNode)) {
132 mapFlowNodeToInNodeSet.put(toNode, new HashSet<GlobalFlowNode>());
134 mapFlowNodeToInNodeSet.get(toNode).add(fromNode);
136 // System.out.println("create a global edge from " + fromNode + " to " + toNode);
140 public Set<GlobalFlowNode> getInNodeSet(GlobalFlowNode node) {
141 if (!mapFlowNodeToInNodeSet.containsKey(node)) {
142 mapFlowNodeToInNodeSet.put(node, new HashSet<GlobalFlowNode>());
144 return mapFlowNodeToInNodeSet.get(node);
147 public Set<GlobalFlowNode> getNodeSet() {
148 Set<GlobalFlowNode> nodeSet = new HashSet<GlobalFlowNode>();
149 nodeSet.addAll(mapLocTupleToNode.values());
153 public Set<GlobalFlowNode> getOutNodeSet(GlobalFlowNode node) {
155 if (!mapFlowNodeToOutNodeSet.containsKey(node)) {
156 mapFlowNodeToOutNodeSet.put(node, new HashSet<GlobalFlowNode>());
159 return mapFlowNodeToOutNodeSet.get(node);
162 public void writeGraph(String suffix) {
164 String graphName = "flowgraph_" + md.toString() + suffix;
165 graphName = graphName.replaceAll("[\\W]", "");
168 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
169 bw.write("digraph " + graphName + " {\n");
170 bw.write("compound=true;\n");
172 // then visit every flow node
174 // Iterator<FlowNode> iter = nodeSet.iterator();
175 Iterator<GlobalFlowNode> iter = getNodeSet().iterator();
177 Set<GlobalFlowNode> addedNodeSet = new HashSet<GlobalFlowNode>();
179 while (iter.hasNext()) {
180 GlobalFlowNode srcNode = iter.next();
182 Set<GlobalFlowNode> outNodeSet = getOutNodeSet(srcNode);
183 for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
184 GlobalFlowNode dstNode = (GlobalFlowNode) iterator.next();
186 if (!addedNodeSet.contains(srcNode)) {
187 drawNode(srcNode, bw);
190 if (!addedNodeSet.contains(dstNode)) {
191 drawNode(dstNode, bw);
194 bw.write("" + srcNode.getID() + " -> " + dstNode.getID() + ";\n");
198 // if (node.getDescTuple().size() == 1) {
199 // // here, we just care about the local variable
200 // if (node.getFieldNodeSet().size() > 0) {
201 // drawSubgraph(node, bw, addedEdgeSet);
204 // drawEdges(node, bw, addedNodeSet, addedEdgeSet);
211 } catch (IOException e) {
216 private void drawNode(GlobalFlowNode node, BufferedWriter bw) throws IOException {
217 bw.write(node.getID() + " [label=\"" + node.getPrettyID() + "\"]" + ";\n");
220 public Set<GlobalFlowNode> getIncomingNodeSet(GlobalFlowNode node) {
222 Set<GlobalFlowNode> incomingNodeSet = new HashSet<GlobalFlowNode>();
223 recurIncomingNodeSet(node, incomingNodeSet);
225 return incomingNodeSet;
228 private void recurIncomingNodeSet(GlobalFlowNode node, Set<GlobalFlowNode> visited) {
230 for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) {
231 GlobalFlowNode curNode = (GlobalFlowNode) iterator.next();
233 Set<GlobalFlowNode> outNodeSet = getOutNodeSet(curNode);
235 for (Iterator iterator2 = outNodeSet.iterator(); iterator2.hasNext();) {
236 GlobalFlowNode outNode = (GlobalFlowNode) iterator2.next();
238 if (outNode.equals(node)) {
239 if (!visited.contains(curNode)) {
240 visited.add(curNode);
241 recurIncomingNodeSet(curNode, visited);
249 public Set<GlobalFlowNode> getIncomingNodeSetByPrefix(Location prefix) {
251 Set<GlobalFlowNode> incomingNodeSet = new HashSet<GlobalFlowNode>();
253 for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) {
254 GlobalFlowNode curNode = (GlobalFlowNode) iterator.next();
255 Set<GlobalFlowNode> outNodeSet = getOutNodeSet(curNode);
257 for (Iterator iterator2 = outNodeSet.iterator(); iterator2.hasNext();) {
258 GlobalFlowNode outNode = (GlobalFlowNode) iterator2.next();
260 if (outNode.getLocTuple().startsWith(prefix)) {
261 incomingNodeSet.add(curNode);
262 recurIncomingNodeSetByPrefix(prefix, curNode, incomingNodeSet);
268 return incomingNodeSet;
272 private void recurIncomingNodeSetByPrefix(Location prefix, GlobalFlowNode node,
273 Set<GlobalFlowNode> visited) {
275 Set<GlobalFlowNode> inNodeSet = getInNodeSet(node);
277 for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
278 GlobalFlowNode curNode = (GlobalFlowNode) iterator.next();
280 if (!curNode.getLocTuple().startsWith(prefix) && !visited.contains(curNode)) {
281 visited.add(curNode);
282 recurIncomingNodeSetByPrefix(prefix, curNode, visited);
288 public Set<GlobalFlowNode> getReachableNodeSetByPrefix(Location prefix) {
290 Set<GlobalFlowNode> reachableNodeSet = new HashSet<GlobalFlowNode>();
292 for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) {
293 GlobalFlowNode curNode = (GlobalFlowNode) iterator.next();
295 if (curNode.getLocTuple().startsWith(prefix)) {
296 Set<GlobalFlowNode> outNodeSet = getOutNodeSet(curNode);
297 for (Iterator iterator2 = outNodeSet.iterator(); iterator2.hasNext();) {
298 GlobalFlowNode outNode = (GlobalFlowNode) iterator2.next();
299 if (!outNode.getLocTuple().startsWith(prefix) && !reachableNodeSet.contains(outNode)) {
300 reachableNodeSet.add(outNode);
301 recurReachableNodeSetByPrefix(prefix, outNode, reachableNodeSet);
308 return reachableNodeSet;
311 private void recurReachableNodeSetByPrefix(Location prefix, GlobalFlowNode node,
312 Set<GlobalFlowNode> reachableNodeSet) {
313 Set<GlobalFlowNode> outNodeSet = getOutNodeSet(node);
314 for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
315 GlobalFlowNode outNode = (GlobalFlowNode) iterator.next();
316 if (!outNode.getLocTuple().startsWith(prefix) && !reachableNodeSet.contains(outNode)) {
317 reachableNodeSet.add(outNode);
318 recurReachableNodeSetByPrefix(prefix, outNode, reachableNodeSet);
323 public Set<GlobalFlowNode> getReachableNodeSetFrom(GlobalFlowNode node) {
325 Set<GlobalFlowNode> reachableNodeSet = new HashSet<GlobalFlowNode>();
326 recurReachableNodeSet(node, reachableNodeSet);
328 return reachableNodeSet;
331 private void recurReachableNodeSet(GlobalFlowNode node, Set<GlobalFlowNode> reachableNodeSet) {
332 Set<GlobalFlowNode> outNodeSet = getOutNodeSet(node);
333 for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
334 GlobalFlowNode outNode = (GlobalFlowNode) iterator.next();
335 if (!reachableNodeSet.contains(outNode)) {
336 reachableNodeSet.add(outNode);
337 recurReachableNodeSet(outNode, reachableNodeSet);