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 boolean contains(NTuple<Location> locTuple) {
44 return mapLocTupleToNode.containsKey(locTuple);
47 public GlobalFlowNode getFlowNode(NTuple<Location> locTuple) {
48 if (!mapLocTupleToNode.containsKey(locTuple)) {
49 GlobalFlowNode node = createNewGlobalFlowNode(locTuple);
50 mapLocTupleToNode.put(locTuple, node);
52 return mapLocTupleToNode.get(locTuple);
55 private GlobalFlowNode createNewGlobalFlowNode(NTuple<Location> locTuple) {
56 if (locTuple.size() == 0) {
59 GlobalFlowNode node = new GlobalFlowNode(locTuple);
63 public void addMapLocationToInferCompositeLocation(Location loc, CompositeLocation newCompLoc) {
64 if (mapLocationToInferCompositeLocation.containsKey(loc)) {
65 // need to do a sanity check
66 // if the old composite location has the same prefix of the new composite location,
67 // replace old one with new one
68 // if both old and new do not share the prefix, throw error
69 CompositeLocation oldCompLoc = mapLocationToInferCompositeLocation.get(loc);
71 if (newCompLoc.getSize() == oldCompLoc.getSize()) {
72 for (int i = 0; i < oldCompLoc.getSize() - 1; i++) {
73 Location oldLocElement = oldCompLoc.get(i);
74 Location newLocElement = newCompLoc.get(i);
76 if (!oldLocElement.equals(newLocElement)) {
77 throw new Error("Failed to generate a composite location. The old composite location="
78 + oldCompLoc + " and the new composite location=" + newCompLoc);
81 } else if (newCompLoc.getSize() > oldCompLoc.getSize()) {
82 mapLocationToInferCompositeLocation.put(loc, newCompLoc);
86 mapLocationToInferCompositeLocation.put(loc, newCompLoc);
90 public CompositeLocation getCompositeLocation(Location loc) {
91 if (!mapLocationToInferCompositeLocation.containsKey(loc)) {
92 CompositeLocation compLoc = new CompositeLocation();
93 compLoc.addLocation(loc);
94 mapLocationToInferCompositeLocation.put(loc, compLoc);
96 return mapLocationToInferCompositeLocation.get(loc);
99 public boolean hasValueFlowEdge(NTuple<Location> fromLocTuple, NTuple<Location> toLocTuple) {
101 // return true if the graph already has a flow edge
103 if (!mapLocTupleToNode.containsKey(fromLocTuple) || !mapLocTupleToNode.containsKey(toLocTuple)) {
107 GlobalFlowNode fromNode = getFlowNode(fromLocTuple);
108 GlobalFlowNode toNode = getFlowNode(toLocTuple);
110 if (!mapFlowNodeToOutNodeSet.containsKey(fromNode)
111 || !mapFlowNodeToInNodeSet.containsKey(toNode)) {
115 if (mapFlowNodeToOutNodeSet.get(fromNode).contains(toNode)
116 && mapFlowNodeToInNodeSet.get(toNode).contains(fromNode)) {
123 public void addValueFlowEdge(NTuple<Location> fromLocTuple, NTuple<Location> toLocTuple) {
125 Location lastElementfromLocTuple = fromLocTuple.get(fromLocTuple.size() - 1);
126 if (lastElementfromLocTuple.getLocDescriptor().equals(LocationInference.LITERALDESC)) {
130 GlobalFlowNode fromNode = getFlowNode(fromLocTuple);
131 GlobalFlowNode toNode = getFlowNode(toLocTuple);
133 if (!mapFlowNodeToOutNodeSet.containsKey(fromNode)) {
134 mapFlowNodeToOutNodeSet.put(fromNode, new HashSet<GlobalFlowNode>());
136 mapFlowNodeToOutNodeSet.get(fromNode).add(toNode);
138 if (!mapFlowNodeToInNodeSet.containsKey(toNode)) {
139 mapFlowNodeToInNodeSet.put(toNode, new HashSet<GlobalFlowNode>());
141 mapFlowNodeToInNodeSet.get(toNode).add(fromNode);
143 // System.out.println("create a global edge from " + fromNode + " to " + toNode);
147 public Set<GlobalFlowNode> getInNodeSet(GlobalFlowNode node) {
148 if (!mapFlowNodeToInNodeSet.containsKey(node)) {
149 mapFlowNodeToInNodeSet.put(node, new HashSet<GlobalFlowNode>());
151 return mapFlowNodeToInNodeSet.get(node);
154 public Set<GlobalFlowNode> getNodeSet() {
155 Set<GlobalFlowNode> nodeSet = new HashSet<GlobalFlowNode>();
156 nodeSet.addAll(mapLocTupleToNode.values());
160 public Set<GlobalFlowNode> getOutNodeSet(GlobalFlowNode node) {
162 if (!mapFlowNodeToOutNodeSet.containsKey(node)) {
163 mapFlowNodeToOutNodeSet.put(node, new HashSet<GlobalFlowNode>());
166 return mapFlowNodeToOutNodeSet.get(node);
169 public void writeGraph(String suffix) {
171 String graphName = "flowgraph_" + md.toString() + suffix;
172 graphName = graphName.replaceAll("[\\W]", "");
175 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
176 bw.write("digraph " + graphName + " {\n");
177 bw.write("compound=true;\n");
179 // then visit every flow node
181 // Iterator<FlowNode> iter = nodeSet.iterator();
182 Iterator<GlobalFlowNode> iter = getNodeSet().iterator();
184 Set<GlobalFlowNode> addedNodeSet = new HashSet<GlobalFlowNode>();
186 while (iter.hasNext()) {
187 GlobalFlowNode srcNode = iter.next();
189 Set<GlobalFlowNode> outNodeSet = getOutNodeSet(srcNode);
190 for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
191 GlobalFlowNode dstNode = (GlobalFlowNode) iterator.next();
193 if (!addedNodeSet.contains(srcNode)) {
194 drawNode(srcNode, bw);
197 if (!addedNodeSet.contains(dstNode)) {
198 drawNode(dstNode, bw);
201 bw.write("" + srcNode.getID() + " -> " + dstNode.getID() + ";\n");
205 // if (node.getDescTuple().size() == 1) {
206 // // here, we just care about the local variable
207 // if (node.getFieldNodeSet().size() > 0) {
208 // drawSubgraph(node, bw, addedEdgeSet);
211 // drawEdges(node, bw, addedNodeSet, addedEdgeSet);
218 } catch (IOException e) {
223 private void drawNode(GlobalFlowNode node, BufferedWriter bw) throws IOException {
224 bw.write(node.getID() + " [label=\"" + node.getPrettyID() + "\"]" + ";\n");
227 public Set<GlobalFlowNode> getIncomingNodeSet(GlobalFlowNode node) {
229 Set<GlobalFlowNode> incomingNodeSet = new HashSet<GlobalFlowNode>();
230 recurIncomingNodeSet(node, incomingNodeSet);
232 return incomingNodeSet;
235 private void recurIncomingNodeSet(GlobalFlowNode node, Set<GlobalFlowNode> visited) {
237 for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) {
238 GlobalFlowNode curNode = (GlobalFlowNode) iterator.next();
240 Set<GlobalFlowNode> outNodeSet = getOutNodeSet(curNode);
242 for (Iterator iterator2 = outNodeSet.iterator(); iterator2.hasNext();) {
243 GlobalFlowNode outNode = (GlobalFlowNode) iterator2.next();
245 if (outNode.equals(node)) {
246 if (!visited.contains(curNode)) {
247 visited.add(curNode);
248 recurIncomingNodeSet(curNode, visited);
256 public Set<GlobalFlowNode> getIncomingNodeSetByPrefix(Location prefix) {
258 Set<GlobalFlowNode> incomingNodeSet = new HashSet<GlobalFlowNode>();
260 for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) {
261 GlobalFlowNode curNode = (GlobalFlowNode) iterator.next();
262 Set<GlobalFlowNode> outNodeSet = getOutNodeSet(curNode);
264 for (Iterator iterator2 = outNodeSet.iterator(); iterator2.hasNext();) {
265 GlobalFlowNode outNode = (GlobalFlowNode) iterator2.next();
266 if (outNode.getLocTuple().startsWith(prefix)) {
267 incomingNodeSet.add(curNode);
268 recurIncomingNodeSetByPrefix(prefix, curNode, incomingNodeSet);
274 return incomingNodeSet;
278 private void recurIncomingNodeSetByPrefix(Location prefix, GlobalFlowNode node,
279 Set<GlobalFlowNode> visited) {
281 Set<GlobalFlowNode> inNodeSet = getInNodeSet(node);
283 for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
284 GlobalFlowNode curNode = (GlobalFlowNode) iterator.next();
286 if (!curNode.getLocTuple().startsWith(prefix) && !visited.contains(curNode)) {
287 visited.add(curNode);
288 recurIncomingNodeSetByPrefix(prefix, curNode, visited);
294 public Set<GlobalFlowNode> getReachableNodeSetByPrefix(Location prefix) {
296 Set<GlobalFlowNode> reachableNodeSet = new HashSet<GlobalFlowNode>();
298 for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) {
299 GlobalFlowNode curNode = (GlobalFlowNode) iterator.next();
301 if (curNode.getLocTuple().startsWith(prefix)) {
302 Set<GlobalFlowNode> outNodeSet = getOutNodeSet(curNode);
303 for (Iterator iterator2 = outNodeSet.iterator(); iterator2.hasNext();) {
304 GlobalFlowNode outNode = (GlobalFlowNode) iterator2.next();
305 if (!outNode.getLocTuple().startsWith(prefix) && !reachableNodeSet.contains(outNode)) {
306 reachableNodeSet.add(outNode);
307 recurReachableNodeSetByPrefix(prefix, outNode, reachableNodeSet);
314 return reachableNodeSet;
317 private void recurReachableNodeSetByPrefix(Location prefix, GlobalFlowNode node,
318 Set<GlobalFlowNode> reachableNodeSet) {
319 Set<GlobalFlowNode> outNodeSet = getOutNodeSet(node);
320 for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
321 GlobalFlowNode outNode = (GlobalFlowNode) iterator.next();
322 if (!outNode.getLocTuple().startsWith(prefix) && !reachableNodeSet.contains(outNode)) {
323 reachableNodeSet.add(outNode);
324 recurReachableNodeSetByPrefix(prefix, outNode, reachableNodeSet);
329 public Set<GlobalFlowNode> getReachableNodeSetFrom(GlobalFlowNode node) {
331 Set<GlobalFlowNode> reachableNodeSet = new HashSet<GlobalFlowNode>();
332 recurReachableNodeSet(node, reachableNodeSet);
334 return reachableNodeSet;
337 private void recurReachableNodeSet(GlobalFlowNode node, Set<GlobalFlowNode> reachableNodeSet) {
338 Set<GlobalFlowNode> outNodeSet = getOutNodeSet(node);
339 for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
340 GlobalFlowNode outNode = (GlobalFlowNode) iterator.next();
341 if (!reachableNodeSet.contains(outNode)) {
342 reachableNodeSet.add(outNode);
343 recurReachableNodeSet(outNode, reachableNodeSet);