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");
70 } else if (newCompLoc.getSize() > oldCompLoc.getSize()) {
71 mapLocationToInferCompositeLocation.put(loc, newCompLoc);
75 mapLocationToInferCompositeLocation.put(loc, newCompLoc);
79 public CompositeLocation getCompositeLocation(Location loc) {
80 if (!mapLocationToInferCompositeLocation.containsKey(loc)) {
81 CompositeLocation compLoc = new CompositeLocation();
82 compLoc.addLocation(loc);
83 mapLocationToInferCompositeLocation.put(loc, compLoc);
85 return mapLocationToInferCompositeLocation.get(loc);
88 public void addValueFlowEdge(NTuple<Location> fromLocTuple, NTuple<Location> toLocTuple) {
90 GlobalFlowNode fromNode = getFlowNode(fromLocTuple);
91 GlobalFlowNode toNode = getFlowNode(toLocTuple);
93 if (!mapFlowNodeToOutNodeSet.containsKey(fromNode)) {
94 mapFlowNodeToOutNodeSet.put(fromNode, new HashSet<GlobalFlowNode>());
96 mapFlowNodeToOutNodeSet.get(fromNode).add(toNode);
98 System.out.println("create a global edge from " + fromNode + " to " + toNode);
102 public Set<GlobalFlowNode> getNodeSet() {
103 Set<GlobalFlowNode> nodeSet = new HashSet<GlobalFlowNode>();
104 nodeSet.addAll(mapLocTupleToNode.values());
108 public Set<GlobalFlowNode> getOutNodeSet(GlobalFlowNode node) {
110 if (!mapFlowNodeToOutNodeSet.containsKey(node)) {
111 mapFlowNodeToOutNodeSet.put(node, new HashSet<GlobalFlowNode>());
114 return mapFlowNodeToOutNodeSet.get(node);
117 public void writeGraph(String suffix) {
119 String graphName = "flowgraph_" + md.toString() + suffix;
120 graphName = graphName.replaceAll("[\\W]", "");
123 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
124 bw.write("digraph " + graphName + " {\n");
125 bw.write("compound=true;\n");
127 // then visit every flow node
129 // Iterator<FlowNode> iter = nodeSet.iterator();
130 Iterator<GlobalFlowNode> iter = getNodeSet().iterator();
132 Set<GlobalFlowNode> addedNodeSet = new HashSet<GlobalFlowNode>();
134 while (iter.hasNext()) {
135 GlobalFlowNode srcNode = iter.next();
137 Set<GlobalFlowNode> outNodeSet = getOutNodeSet(srcNode);
138 for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
139 GlobalFlowNode dstNode = (GlobalFlowNode) iterator.next();
141 if (!addedNodeSet.contains(srcNode)) {
142 drawNode(srcNode, bw);
145 if (!addedNodeSet.contains(dstNode)) {
146 drawNode(dstNode, bw);
149 bw.write("" + srcNode.getID() + " -> " + dstNode.getID() + ";\n");
153 // if (node.getDescTuple().size() == 1) {
154 // // here, we just care about the local variable
155 // if (node.getFieldNodeSet().size() > 0) {
156 // drawSubgraph(node, bw, addedEdgeSet);
159 // drawEdges(node, bw, addedNodeSet, addedEdgeSet);
166 } catch (IOException e) {
171 private void drawNode(GlobalFlowNode node, BufferedWriter bw) throws IOException {
172 bw.write(node.getID() + " [label=\"" + node.getPrettyID() + "\"]" + ";\n");
175 public Set<GlobalFlowNode> getIncomingNodeSet(GlobalFlowNode node) {
177 Set<GlobalFlowNode> incomingNodeSet = new HashSet<GlobalFlowNode>();
178 recurIncomingNodeSet(node, incomingNodeSet);
180 return incomingNodeSet;
183 private void recurIncomingNodeSet(GlobalFlowNode node, Set<GlobalFlowNode> visited) {
185 for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) {
186 GlobalFlowNode curNode = (GlobalFlowNode) iterator.next();
188 Set<GlobalFlowNode> outNodeSet = getOutNodeSet(curNode);
190 for (Iterator iterator2 = outNodeSet.iterator(); iterator2.hasNext();) {
191 GlobalFlowNode outNode = (GlobalFlowNode) iterator2.next();
193 if (outNode.equals(node)) {
194 if (!visited.contains(curNode)) {
195 visited.add(curNode);
196 recurIncomingNodeSet(curNode, visited);
204 public Set<GlobalFlowNode> getReachableNodeSetFrom(GlobalFlowNode node) {
206 Set<GlobalFlowNode> reachableNodeSet = new HashSet<GlobalFlowNode>();
207 recurReachableNodeSet(node, reachableNodeSet);
209 return reachableNodeSet;
212 private void recurReachableNodeSet(GlobalFlowNode node, Set<GlobalFlowNode> reachableNodeSet) {
213 Set<GlobalFlowNode> outNodeSet = getOutNodeSet(node);
214 for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
215 GlobalFlowNode outNode = (GlobalFlowNode) iterator.next();
216 if (!reachableNodeSet.contains(outNode)) {
217 reachableNodeSet.add(outNode);
218 recurReachableNodeSet(outNode, reachableNodeSet);