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 boolean contrainsInferCompositeLocationMapKey(Location loc) {
64 return mapLocationToInferCompositeLocation.containsKey(loc);
67 public void addMapLocationToInferCompositeLocation(Location loc, CompositeLocation newCompLoc) {
68 if (mapLocationToInferCompositeLocation.containsKey(loc)) {
69 // need to do a sanity check
70 // if the old composite location has the same prefix of the new composite location,
71 // replace old one with new one
72 // if both old and new do not share the prefix, throw error
73 CompositeLocation oldCompLoc = mapLocationToInferCompositeLocation.get(loc);
75 if (newCompLoc.getSize() == oldCompLoc.getSize()) {
76 for (int i = 0; i < oldCompLoc.getSize() - 1; i++) {
77 Location oldLocElement = oldCompLoc.get(i);
78 Location newLocElement = newCompLoc.get(i);
80 if (!oldLocElement.equals(newLocElement)) {
81 throw new Error("Failed to generate a composite location. The old composite location="
82 + oldCompLoc + " and the new composite location=" + newCompLoc);
85 } else if (newCompLoc.getSize() > oldCompLoc.getSize()) {
86 mapLocationToInferCompositeLocation.put(loc, newCompLoc);
90 mapLocationToInferCompositeLocation.put(loc, newCompLoc);
94 public CompositeLocation getCompositeLocation(Location loc) {
95 if (!mapLocationToInferCompositeLocation.containsKey(loc)) {
96 CompositeLocation compLoc = new CompositeLocation();
97 compLoc.addLocation(loc);
98 mapLocationToInferCompositeLocation.put(loc, compLoc);
100 return mapLocationToInferCompositeLocation.get(loc);
103 public boolean hasValueFlowEdge(NTuple<Location> fromLocTuple, NTuple<Location> toLocTuple) {
105 // return true if the graph already has a flow edge
107 if (!mapLocTupleToNode.containsKey(fromLocTuple) || !mapLocTupleToNode.containsKey(toLocTuple)) {
111 GlobalFlowNode fromNode = getFlowNode(fromLocTuple);
112 GlobalFlowNode toNode = getFlowNode(toLocTuple);
114 if (!mapFlowNodeToOutNodeSet.containsKey(fromNode)
115 || !mapFlowNodeToInNodeSet.containsKey(toNode)) {
119 if (mapFlowNodeToOutNodeSet.get(fromNode).contains(toNode)
120 && mapFlowNodeToInNodeSet.get(toNode).contains(fromNode)) {
127 public void addValueFlowEdge(NTuple<Location> fromLocTuple, NTuple<Location> toLocTuple) {
129 Location lastElementfromLocTuple = fromLocTuple.get(fromLocTuple.size() - 1);
130 if (lastElementfromLocTuple.getLocDescriptor().equals(LocationInference.LITERALDESC)) {
134 GlobalFlowNode fromNode = getFlowNode(fromLocTuple);
135 GlobalFlowNode toNode = getFlowNode(toLocTuple);
137 if (!mapFlowNodeToOutNodeSet.containsKey(fromNode)) {
138 mapFlowNodeToOutNodeSet.put(fromNode, new HashSet<GlobalFlowNode>());
140 mapFlowNodeToOutNodeSet.get(fromNode).add(toNode);
142 if (!mapFlowNodeToInNodeSet.containsKey(toNode)) {
143 mapFlowNodeToInNodeSet.put(toNode, new HashSet<GlobalFlowNode>());
145 mapFlowNodeToInNodeSet.get(toNode).add(fromNode);
147 // System.out.println("create a global edge from " + fromNode + " to " + toNode);
151 public Set<GlobalFlowNode> getInNodeSet(GlobalFlowNode node) {
152 if (!mapFlowNodeToInNodeSet.containsKey(node)) {
153 mapFlowNodeToInNodeSet.put(node, new HashSet<GlobalFlowNode>());
155 return mapFlowNodeToInNodeSet.get(node);
158 public Set<GlobalFlowNode> getNodeSet() {
159 Set<GlobalFlowNode> nodeSet = new HashSet<GlobalFlowNode>();
160 nodeSet.addAll(mapLocTupleToNode.values());
164 public Set<GlobalFlowNode> getOutNodeSet(GlobalFlowNode node) {
166 if (!mapFlowNodeToOutNodeSet.containsKey(node)) {
167 mapFlowNodeToOutNodeSet.put(node, new HashSet<GlobalFlowNode>());
170 return mapFlowNodeToOutNodeSet.get(node);
173 public void writeGraph(String suffix) {
175 String graphName = "flowgraph_" + md.toString() + suffix;
176 graphName = graphName.replaceAll("[\\W]", "");
179 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
180 bw.write("digraph " + graphName + " {\n");
181 bw.write("compound=true;\n");
183 // then visit every flow node
185 // Iterator<FlowNode> iter = nodeSet.iterator();
186 Iterator<GlobalFlowNode> iter = getNodeSet().iterator();
188 Set<GlobalFlowNode> addedNodeSet = new HashSet<GlobalFlowNode>();
190 while (iter.hasNext()) {
191 GlobalFlowNode srcNode = iter.next();
193 Set<GlobalFlowNode> outNodeSet = getOutNodeSet(srcNode);
194 for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
195 GlobalFlowNode dstNode = (GlobalFlowNode) iterator.next();
197 if (!addedNodeSet.contains(srcNode)) {
198 drawNode(srcNode, bw);
201 if (!addedNodeSet.contains(dstNode)) {
202 drawNode(dstNode, bw);
205 bw.write("" + srcNode.getID() + " -> " + dstNode.getID() + ";\n");
209 // if (node.getDescTuple().size() == 1) {
210 // // here, we just care about the local variable
211 // if (node.getFieldNodeSet().size() > 0) {
212 // drawSubgraph(node, bw, addedEdgeSet);
215 // drawEdges(node, bw, addedNodeSet, addedEdgeSet);
222 } catch (IOException e) {
227 private void drawNode(GlobalFlowNode node, BufferedWriter bw) throws IOException {
228 bw.write(node.getID() + " [label=\"" + node.getPrettyID() + "\"]" + ";\n");
231 public Set<GlobalFlowNode> getIncomingNodeSet(GlobalFlowNode node) {
233 Set<GlobalFlowNode> incomingNodeSet = new HashSet<GlobalFlowNode>();
234 recurIncomingNodeSet(node, incomingNodeSet);
236 return incomingNodeSet;
239 private void recurIncomingNodeSet(GlobalFlowNode node, Set<GlobalFlowNode> visited) {
241 for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) {
242 GlobalFlowNode curNode = (GlobalFlowNode) iterator.next();
244 Set<GlobalFlowNode> outNodeSet = getOutNodeSet(curNode);
246 for (Iterator iterator2 = outNodeSet.iterator(); iterator2.hasNext();) {
247 GlobalFlowNode outNode = (GlobalFlowNode) iterator2.next();
249 if (outNode.equals(node)) {
250 if (!visited.contains(curNode)) {
251 visited.add(curNode);
252 recurIncomingNodeSet(curNode, visited);
260 public Set<GlobalFlowNode> getIncomingNodeSetByPrefix(Location prefix) {
262 Set<GlobalFlowNode> incomingNodeSet = new HashSet<GlobalFlowNode>();
264 for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) {
265 GlobalFlowNode curNode = (GlobalFlowNode) iterator.next();
266 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)) {
271 incomingNodeSet.add(curNode);
272 recurIncomingNodeSetByPrefix(prefix, curNode, incomingNodeSet);
278 return incomingNodeSet;
282 private void recurIncomingNodeSetByPrefix(Location prefix, GlobalFlowNode node,
283 Set<GlobalFlowNode> visited) {
285 Set<GlobalFlowNode> inNodeSet = getInNodeSet(node);
287 for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
288 GlobalFlowNode curNode = (GlobalFlowNode) iterator.next();
290 if (!curNode.getLocTuple().startsWith(prefix) && !visited.contains(curNode)) {
291 visited.add(curNode);
292 recurIncomingNodeSetByPrefix(prefix, curNode, visited);
298 public Set<GlobalFlowNode> getReachableNodeSetByPrefix(Location prefix) {
300 Set<GlobalFlowNode> reachableNodeSet = new HashSet<GlobalFlowNode>();
302 for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) {
303 GlobalFlowNode curNode = (GlobalFlowNode) iterator.next();
305 if (curNode.getLocTuple().startsWith(prefix)) {
306 Set<GlobalFlowNode> outNodeSet = getOutNodeSet(curNode);
307 for (Iterator iterator2 = outNodeSet.iterator(); iterator2.hasNext();) {
308 GlobalFlowNode outNode = (GlobalFlowNode) iterator2.next();
309 if (!outNode.getLocTuple().startsWith(prefix) && !reachableNodeSet.contains(outNode)) {
310 reachableNodeSet.add(outNode);
311 recurReachableNodeSetByPrefix(prefix, outNode, reachableNodeSet);
318 return reachableNodeSet;
321 private void recurReachableNodeSetByPrefix(Location prefix, GlobalFlowNode node,
322 Set<GlobalFlowNode> reachableNodeSet) {
323 Set<GlobalFlowNode> outNodeSet = getOutNodeSet(node);
324 for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
325 GlobalFlowNode outNode = (GlobalFlowNode) iterator.next();
326 if (!outNode.getLocTuple().startsWith(prefix) && !reachableNodeSet.contains(outNode)) {
327 reachableNodeSet.add(outNode);
328 recurReachableNodeSetByPrefix(prefix, outNode, reachableNodeSet);
333 public Set<GlobalFlowNode> getReachableNodeSetFrom(GlobalFlowNode node) {
335 Set<GlobalFlowNode> reachableNodeSet = new HashSet<GlobalFlowNode>();
336 recurReachableNodeSet(node, reachableNodeSet);
338 return reachableNodeSet;
341 private void recurReachableNodeSet(GlobalFlowNode node, Set<GlobalFlowNode> reachableNodeSet) {
342 Set<GlobalFlowNode> outNodeSet = getOutNodeSet(node);
343 for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
344 GlobalFlowNode outNode = (GlobalFlowNode) iterator.next();
345 if (!reachableNodeSet.contains(outNode)) {
346 reachableNodeSet.add(outNode);
347 recurReachableNodeSet(outNode, reachableNodeSet);