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;
23 Map<Location, CompositeLocation> mapLocationToInferCompositeLocation;
25 public GlobalFlowGraph(MethodDescriptor md) {
27 this.mapLocTupleToNode = new HashMap<NTuple<Location>, GlobalFlowNode>();
28 this.mapFlowNodeToOutNodeSet = new HashMap<GlobalFlowNode, Set<GlobalFlowNode>>();
29 this.mapLocationToInferCompositeLocation = new HashMap<Location, CompositeLocation>();
32 public MethodDescriptor getMethodDescriptor() {
36 public Map<Location, CompositeLocation> getMapLocationToInferCompositeLocation() {
37 return mapLocationToInferCompositeLocation;
40 public GlobalFlowNode getFlowNode(NTuple<Location> locTuple) {
41 if (!mapLocTupleToNode.containsKey(locTuple)) {
42 GlobalFlowNode node = createNewGlobalFlowNode(locTuple);
43 mapLocTupleToNode.put(locTuple, node);
45 return mapLocTupleToNode.get(locTuple);
48 private GlobalFlowNode createNewGlobalFlowNode(NTuple<Location> locTuple) {
49 GlobalFlowNode node = new GlobalFlowNode(locTuple);
53 public void addMapLocationToInferCompositeLocation(Location loc, CompositeLocation newCompLoc) {
54 if (mapLocationToInferCompositeLocation.containsKey(loc)) {
55 // need to do a sanity check
56 // if the old composite location has the same prefix of the new composite location,
57 // replace old one with new one
58 // if both old and new do not share the prefix, throw error
59 CompositeLocation oldCompLoc = mapLocationToInferCompositeLocation.get(loc);
61 if (newCompLoc.getSize() == oldCompLoc.getSize()) {
62 for (int i = 0; i < oldCompLoc.getSize(); i++) {
63 Location oldLocElement = oldCompLoc.get(i);
64 Location newLocElement = newCompLoc.get(i);
66 if (!oldLocElement.equals(newLocElement)) {
67 throw new Error("Failed to generate a composite location. The old composite location="
68 + oldCompLoc + " and the new composite location=" + newCompLoc);
71 } else if (newCompLoc.getSize() > oldCompLoc.getSize()) {
72 mapLocationToInferCompositeLocation.put(loc, newCompLoc);
76 mapLocationToInferCompositeLocation.put(loc, newCompLoc);
80 public CompositeLocation getCompositeLocation(Location loc) {
81 if (!mapLocationToInferCompositeLocation.containsKey(loc)) {
82 CompositeLocation compLoc = new CompositeLocation();
83 compLoc.addLocation(loc);
84 mapLocationToInferCompositeLocation.put(loc, compLoc);
86 return mapLocationToInferCompositeLocation.get(loc);
89 public void addValueFlowEdge(NTuple<Location> fromLocTuple, NTuple<Location> toLocTuple) {
91 GlobalFlowNode fromNode = getFlowNode(fromLocTuple);
92 GlobalFlowNode toNode = getFlowNode(toLocTuple);
94 if (!mapFlowNodeToOutNodeSet.containsKey(fromNode)) {
95 mapFlowNodeToOutNodeSet.put(fromNode, new HashSet<GlobalFlowNode>());
97 mapFlowNodeToOutNodeSet.get(fromNode).add(toNode);
99 System.out.println("create a global edge from " + fromNode + " to " + toNode);
103 public Set<GlobalFlowNode> getNodeSet() {
104 Set<GlobalFlowNode> nodeSet = new HashSet<GlobalFlowNode>();
105 nodeSet.addAll(mapLocTupleToNode.values());
109 public Set<GlobalFlowNode> getOutNodeSet(GlobalFlowNode node) {
111 if (!mapFlowNodeToOutNodeSet.containsKey(node)) {
112 mapFlowNodeToOutNodeSet.put(node, new HashSet<GlobalFlowNode>());
115 return mapFlowNodeToOutNodeSet.get(node);
118 public void writeGraph(String suffix) {
120 String graphName = "flowgraph_" + md.toString() + suffix;
121 graphName = graphName.replaceAll("[\\W]", "");
124 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
125 bw.write("digraph " + graphName + " {\n");
126 bw.write("compound=true;\n");
128 // then visit every flow node
130 // Iterator<FlowNode> iter = nodeSet.iterator();
131 Iterator<GlobalFlowNode> iter = getNodeSet().iterator();
133 Set<GlobalFlowNode> addedNodeSet = new HashSet<GlobalFlowNode>();
135 while (iter.hasNext()) {
136 GlobalFlowNode srcNode = iter.next();
138 Set<GlobalFlowNode> outNodeSet = getOutNodeSet(srcNode);
139 for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
140 GlobalFlowNode dstNode = (GlobalFlowNode) iterator.next();
142 if (!addedNodeSet.contains(srcNode)) {
143 drawNode(srcNode, bw);
146 if (!addedNodeSet.contains(dstNode)) {
147 drawNode(dstNode, bw);
150 bw.write("" + srcNode.getID() + " -> " + dstNode.getID() + ";\n");
154 // if (node.getDescTuple().size() == 1) {
155 // // here, we just care about the local variable
156 // if (node.getFieldNodeSet().size() > 0) {
157 // drawSubgraph(node, bw, addedEdgeSet);
160 // drawEdges(node, bw, addedNodeSet, addedEdgeSet);
167 } catch (IOException e) {
172 private void drawNode(GlobalFlowNode node, BufferedWriter bw) throws IOException {
173 bw.write(node.getID() + " [label=\"" + node.getPrettyID() + "\"]" + ";\n");
176 public Set<GlobalFlowNode> getIncomingNodeSet(GlobalFlowNode node) {
178 Set<GlobalFlowNode> incomingNodeSet = new HashSet<GlobalFlowNode>();
179 recurIncomingNodeSet(node, incomingNodeSet);
181 return incomingNodeSet;
184 private void recurIncomingNodeSet(GlobalFlowNode node, Set<GlobalFlowNode> visited) {
186 for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) {
187 GlobalFlowNode curNode = (GlobalFlowNode) iterator.next();
189 Set<GlobalFlowNode> outNodeSet = getOutNodeSet(curNode);
191 for (Iterator iterator2 = outNodeSet.iterator(); iterator2.hasNext();) {
192 GlobalFlowNode outNode = (GlobalFlowNode) iterator2.next();
194 if (outNode.equals(node)) {
195 if (!visited.contains(curNode)) {
196 visited.add(curNode);
197 recurIncomingNodeSet(curNode, visited);
205 public Set<GlobalFlowNode> getReachableNodeSetFrom(GlobalFlowNode node) {
207 Set<GlobalFlowNode> reachableNodeSet = new HashSet<GlobalFlowNode>();
208 recurReachableNodeSet(node, reachableNodeSet);
210 return reachableNodeSet;
213 private void recurReachableNodeSet(GlobalFlowNode node, Set<GlobalFlowNode> reachableNodeSet) {
214 Set<GlobalFlowNode> outNodeSet = getOutNodeSet(node);
215 for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
216 GlobalFlowNode outNode = (GlobalFlowNode) iterator.next();
217 if (!reachableNodeSet.contains(outNode)) {
218 reachableNodeSet.add(outNode);
219 recurReachableNodeSet(outNode, reachableNodeSet);