Robust/src/Analysis/SSJava/GlobalFlowGraph.java

   1 package Analysis.SSJava;
   2
   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;
   9 import java.util.Map;
  10 import java.util.Set;
  11
  12 import IR.Descriptor;
  13 import IR.MethodDescriptor;
  14 import IR.Tree.MethodInvokeNode;
  15
  16 public class GlobalFlowGraph {
  17
  18   MethodDescriptor md;
  19
  20   Map<NTuple<Location>, GlobalFlowNode> mapLocTupleToNode;
  21   Map<GlobalFlowNode, Set<GlobalFlowNode>> mapFlowNodeToOutNodeSet;
  22
  23   Map<Location, CompositeLocation> mapLocationToInferCompositeLocation;
  24
  25   public GlobalFlowGraph(MethodDescriptor md) {
  26     this.md = md;
  27     this.mapLocTupleToNode = new HashMap<NTuple<Location>, GlobalFlowNode>();
  28     this.mapFlowNodeToOutNodeSet = new HashMap<GlobalFlowNode, Set<GlobalFlowNode>>();
  29     this.mapLocationToInferCompositeLocation = new HashMap<Location, CompositeLocation>();
  30   }
  31
  32   public MethodDescriptor getMethodDescriptor() {
  33     return md;
  34   }
  35
  36   public Map<Location, CompositeLocation> getMapLocationToInferCompositeLocation() {
  37     return mapLocationToInferCompositeLocation;
  38   }
  39
  40   public GlobalFlowNode getFlowNode(NTuple<Location> locTuple) {
  41     if (!mapLocTupleToNode.containsKey(locTuple)) {
  42       GlobalFlowNode node = createNewGlobalFlowNode(locTuple);
  43       mapLocTupleToNode.put(locTuple, node);
  44     }
  45     return mapLocTupleToNode.get(locTuple);
  46   }
  47
  48   private GlobalFlowNode createNewGlobalFlowNode(NTuple<Location> locTuple) {
  49     GlobalFlowNode node = new GlobalFlowNode(locTuple);
  50     return node;
  51   }
  52
  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);
  60
  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);
  65
  66           if (!oldLocElement.equals(newLocElement)) {
  67             throw new Error("Failed to generate a composite location");
  68           }
  69         }
  70       } else if (newCompLoc.getSize() > oldCompLoc.getSize()) {
  71         mapLocationToInferCompositeLocation.put(loc, newCompLoc);
  72       }
  73
  74     } else {
  75       mapLocationToInferCompositeLocation.put(loc, newCompLoc);
  76     }
  77   }
  78
  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);
  84     }
  85     return mapLocationToInferCompositeLocation.get(loc);
  86   }
  87
  88   public void addValueFlowEdge(NTuple<Location> fromLocTuple, NTuple<Location> toLocTuple) {
  89
  90     GlobalFlowNode fromNode = getFlowNode(fromLocTuple);
  91     GlobalFlowNode toNode = getFlowNode(toLocTuple);
  92
  93     if (!mapFlowNodeToOutNodeSet.containsKey(fromNode)) {
  94       mapFlowNodeToOutNodeSet.put(fromNode, new HashSet<GlobalFlowNode>());
  95     }
  96     mapFlowNodeToOutNodeSet.get(fromNode).add(toNode);
  97
  98     System.out.println("create a global edge from " + fromNode + " to " + toNode);
  99
 100   }
 101
 102   public Set<GlobalFlowNode> getNodeSet() {
 103     Set<GlobalFlowNode> nodeSet = new HashSet<GlobalFlowNode>();
 104     nodeSet.addAll(mapLocTupleToNode.values());
 105     return nodeSet;
 106   }
 107
 108   public Set<GlobalFlowNode> getOutNodeSet(GlobalFlowNode node) {
 109
 110     if (!mapFlowNodeToOutNodeSet.containsKey(node)) {
 111       mapFlowNodeToOutNodeSet.put(node, new HashSet<GlobalFlowNode>());
 112     }
 113
 114     return mapFlowNodeToOutNodeSet.get(node);
 115   }
 116
 117   public void writeGraph(String suffix) {
 118
 119     String graphName = "flowgraph_" + md.toString() + suffix;
 120     graphName = graphName.replaceAll("[\\W]", "");
 121
 122     try {
 123       BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
 124       bw.write("digraph " + graphName + " {\n");
 125       bw.write("compound=true;\n");
 126
 127       // then visit every flow node
 128
 129       // Iterator<FlowNode> iter = nodeSet.iterator();
 130       Iterator<GlobalFlowNode> iter = getNodeSet().iterator();
 131
 132       Set<GlobalFlowNode> addedNodeSet = new HashSet<GlobalFlowNode>();
 133
 134       while (iter.hasNext()) {
 135         GlobalFlowNode srcNode = iter.next();
 136
 137         Set<GlobalFlowNode> outNodeSet = getOutNodeSet(srcNode);
 138         for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
 139           GlobalFlowNode dstNode = (GlobalFlowNode) iterator.next();
 140
 141           if (!addedNodeSet.contains(srcNode)) {
 142             drawNode(srcNode, bw);
 143           }
 144
 145           if (!addedNodeSet.contains(dstNode)) {
 146             drawNode(dstNode, bw);
 147           }
 148
 149           bw.write("" + srcNode.getID() + " -> " + dstNode.getID() + ";\n");
 150
 151         }
 152
 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);
 157         // }
 158         // }
 159         // drawEdges(node, bw, addedNodeSet, addedEdgeSet);
 160
 161       }
 162
 163       bw.write("}\n");
 164       bw.close();
 165
 166     } catch (IOException e) {
 167       e.printStackTrace();
 168     }
 169   }
 170
 171   private void drawNode(GlobalFlowNode node, BufferedWriter bw) throws IOException {
 172     bw.write(node.getID() + " [label=\"" + node.getPrettyID() + "\"]" + ";\n");
 173   }
 174
 175   public Set<GlobalFlowNode> getIncomingNodeSet(GlobalFlowNode node) {
 176
 177     Set<GlobalFlowNode> incomingNodeSet = new HashSet<GlobalFlowNode>();
 178     recurIncomingNodeSet(node, incomingNodeSet);
 179
 180     return incomingNodeSet;
 181   }
 182
 183   private void recurIncomingNodeSet(GlobalFlowNode node, Set<GlobalFlowNode> visited) {
 184
 185     for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) {
 186       GlobalFlowNode curNode = (GlobalFlowNode) iterator.next();
 187
 188       Set<GlobalFlowNode> outNodeSet = getOutNodeSet(curNode);
 189
 190       for (Iterator iterator2 = outNodeSet.iterator(); iterator2.hasNext();) {
 191         GlobalFlowNode outNode = (GlobalFlowNode) iterator2.next();
 192
 193         if (outNode.equals(node)) {
 194           if (!visited.contains(curNode)) {
 195             visited.add(curNode);
 196             recurIncomingNodeSet(curNode, visited);
 197           }
 198         }
 199       }
 200     }
 201
 202   }
 203
 204   public Set<GlobalFlowNode> getReachableNodeSetFrom(GlobalFlowNode node) {
 205
 206     Set<GlobalFlowNode> reachableNodeSet = new HashSet<GlobalFlowNode>();
 207     recurReachableNodeSet(node, reachableNodeSet);
 208
 209     return reachableNodeSet;
 210   }
 211
 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);
 219       }
 220     }
 221   }
 222
 223 }