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 void addValueFlowEdge(NTuple<Location> fromLocTuple, NTuple<Location> toLocTuple) {
94 GlobalFlowNode fromNode = getFlowNode(fromLocTuple);
95 GlobalFlowNode toNode = getFlowNode(toLocTuple);
97 if (!mapFlowNodeToOutNodeSet.containsKey(fromNode)) {
98 mapFlowNodeToOutNodeSet.put(fromNode, new HashSet<GlobalFlowNode>());
100 mapFlowNodeToOutNodeSet.get(fromNode).add(toNode);
102 if (!mapFlowNodeToInNodeSet.containsKey(toNode)) {
103 mapFlowNodeToInNodeSet.put(toNode, new HashSet<GlobalFlowNode>());
105 mapFlowNodeToInNodeSet.get(toNode).add(fromNode);
107 // System.out.println("create a global edge from " + fromNode + " to " + toNode);
111 public Set<GlobalFlowNode> getInNodeSet(GlobalFlowNode node) {
112 if (!mapFlowNodeToInNodeSet.containsKey(node)) {
113 mapFlowNodeToInNodeSet.put(node, new HashSet<GlobalFlowNode>());
115 return mapFlowNodeToInNodeSet.get(node);
118 public Set<GlobalFlowNode> getNodeSet() {
119 Set<GlobalFlowNode> nodeSet = new HashSet<GlobalFlowNode>();
120 nodeSet.addAll(mapLocTupleToNode.values());
124 public Set<GlobalFlowNode> getOutNodeSet(GlobalFlowNode node) {
126 if (!mapFlowNodeToOutNodeSet.containsKey(node)) {
127 mapFlowNodeToOutNodeSet.put(node, new HashSet<GlobalFlowNode>());
130 return mapFlowNodeToOutNodeSet.get(node);
133 public void writeGraph(String suffix) {
135 String graphName = "flowgraph_" + md.toString() + suffix;
136 graphName = graphName.replaceAll("[\\W]", "");
139 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
140 bw.write("digraph " + graphName + " {\n");
141 bw.write("compound=true;\n");
143 // then visit every flow node
145 // Iterator<FlowNode> iter = nodeSet.iterator();
146 Iterator<GlobalFlowNode> iter = getNodeSet().iterator();
148 Set<GlobalFlowNode> addedNodeSet = new HashSet<GlobalFlowNode>();
150 while (iter.hasNext()) {
151 GlobalFlowNode srcNode = iter.next();
153 Set<GlobalFlowNode> outNodeSet = getOutNodeSet(srcNode);
154 for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
155 GlobalFlowNode dstNode = (GlobalFlowNode) iterator.next();
157 if (!addedNodeSet.contains(srcNode)) {
158 drawNode(srcNode, bw);
161 if (!addedNodeSet.contains(dstNode)) {
162 drawNode(dstNode, bw);
165 bw.write("" + srcNode.getID() + " -> " + dstNode.getID() + ";\n");
169 // if (node.getDescTuple().size() == 1) {
170 // // here, we just care about the local variable
171 // if (node.getFieldNodeSet().size() > 0) {
172 // drawSubgraph(node, bw, addedEdgeSet);
175 // drawEdges(node, bw, addedNodeSet, addedEdgeSet);
182 } catch (IOException e) {
187 private void drawNode(GlobalFlowNode node, BufferedWriter bw) throws IOException {
188 bw.write(node.getID() + " [label=\"" + node.getPrettyID() + "\"]" + ";\n");
191 public Set<GlobalFlowNode> getIncomingNodeSet(GlobalFlowNode node) {
193 Set<GlobalFlowNode> incomingNodeSet = new HashSet<GlobalFlowNode>();
194 recurIncomingNodeSet(node, incomingNodeSet);
196 return incomingNodeSet;
199 private void recurIncomingNodeSet(GlobalFlowNode node, Set<GlobalFlowNode> visited) {
201 for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) {
202 GlobalFlowNode curNode = (GlobalFlowNode) iterator.next();
204 Set<GlobalFlowNode> outNodeSet = getOutNodeSet(curNode);
206 for (Iterator iterator2 = outNodeSet.iterator(); iterator2.hasNext();) {
207 GlobalFlowNode outNode = (GlobalFlowNode) iterator2.next();
209 if (outNode.equals(node)) {
210 if (!visited.contains(curNode)) {
211 visited.add(curNode);
212 recurIncomingNodeSet(curNode, visited);
220 public Set<GlobalFlowNode> getIncomingNodeSetByPrefix(Location prefix) {
222 Set<GlobalFlowNode> incomingNodeSet = new HashSet<GlobalFlowNode>();
224 for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) {
225 GlobalFlowNode curNode = (GlobalFlowNode) iterator.next();
226 Set<GlobalFlowNode> outNodeSet = getOutNodeSet(curNode);
228 for (Iterator iterator2 = outNodeSet.iterator(); iterator2.hasNext();) {
229 GlobalFlowNode outNode = (GlobalFlowNode) iterator2.next();
231 if (outNode.getLocTuple().startsWith(prefix)) {
232 incomingNodeSet.add(curNode);
233 recurIncomingNodeSetByPrefix(prefix, curNode, incomingNodeSet);
239 return incomingNodeSet;
243 private void recurIncomingNodeSetByPrefix(Location prefix, GlobalFlowNode node,
244 Set<GlobalFlowNode> visited) {
246 Set<GlobalFlowNode> inNodeSet = getInNodeSet(node);
248 for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
249 GlobalFlowNode curNode = (GlobalFlowNode) iterator.next();
251 if (!curNode.getLocTuple().startsWith(prefix) && !visited.contains(curNode)) {
252 visited.add(curNode);
253 recurIncomingNodeSetByPrefix(prefix, curNode, visited);
259 public Set<GlobalFlowNode> getReachableNodeSetByPrefix(Location prefix) {
261 Set<GlobalFlowNode> reachableNodeSet = new HashSet<GlobalFlowNode>();
263 for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) {
264 GlobalFlowNode curNode = (GlobalFlowNode) iterator.next();
266 if (curNode.getLocTuple().startsWith(prefix)) {
267 Set<GlobalFlowNode> outNodeSet = getOutNodeSet(curNode);
268 for (Iterator iterator2 = outNodeSet.iterator(); iterator2.hasNext();) {
269 GlobalFlowNode outNode = (GlobalFlowNode) iterator2.next();
270 if (!outNode.getLocTuple().startsWith(prefix) && !reachableNodeSet.contains(outNode)) {
271 reachableNodeSet.add(outNode);
272 recurReachableNodeSetByPrefix(prefix, outNode, reachableNodeSet);
279 return reachableNodeSet;
282 private void recurReachableNodeSetByPrefix(Location prefix, GlobalFlowNode node,
283 Set<GlobalFlowNode> reachableNodeSet) {
284 Set<GlobalFlowNode> outNodeSet = getOutNodeSet(node);
285 for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
286 GlobalFlowNode outNode = (GlobalFlowNode) iterator.next();
287 if (!outNode.getLocTuple().startsWith(prefix) && !reachableNodeSet.contains(outNode)) {
288 reachableNodeSet.add(outNode);
289 recurReachableNodeSetByPrefix(prefix, outNode, reachableNodeSet);
294 public Set<GlobalFlowNode> getReachableNodeSetFrom(GlobalFlowNode node) {
296 Set<GlobalFlowNode> reachableNodeSet = new HashSet<GlobalFlowNode>();
297 recurReachableNodeSet(node, reachableNodeSet);
299 return reachableNodeSet;
302 private void recurReachableNodeSet(GlobalFlowNode node, Set<GlobalFlowNode> reachableNodeSet) {
303 Set<GlobalFlowNode> outNodeSet = getOutNodeSet(node);
304 for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
305 GlobalFlowNode outNode = (GlobalFlowNode) iterator.next();
306 if (!reachableNodeSet.contains(outNode)) {
307 reachableNodeSet.add(outNode);
308 recurReachableNodeSet(outNode, reachableNodeSet);