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. The old composite location="
  68                 + oldCompLoc + " and the new composite location=" + newCompLoc);
  69           }
  70         }
  71       } else if (newCompLoc.getSize() > oldCompLoc.getSize()) {
  72         mapLocationToInferCompositeLocation.put(loc, newCompLoc);
  73       }
  74
  75     } else {
  76       mapLocationToInferCompositeLocation.put(loc, newCompLoc);
  77     }
  78   }
  79
  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);
  85     }
  86     return mapLocationToInferCompositeLocation.get(loc);
  87   }
  88
  89   public void addValueFlowEdge(NTuple<Location> fromLocTuple, NTuple<Location> toLocTuple) {
  90
  91     GlobalFlowNode fromNode = getFlowNode(fromLocTuple);
  92     GlobalFlowNode toNode = getFlowNode(toLocTuple);
  93
  94     if (!mapFlowNodeToOutNodeSet.containsKey(fromNode)) {
  95       mapFlowNodeToOutNodeSet.put(fromNode, new HashSet<GlobalFlowNode>());
  96     }
  97     mapFlowNodeToOutNodeSet.get(fromNode).add(toNode);
  98
  99     System.out.println("create a global edge from " + fromNode + " to " + toNode);
 100
 101   }
 102
 103   public Set<GlobalFlowNode> getNodeSet() {
 104     Set<GlobalFlowNode> nodeSet = new HashSet<GlobalFlowNode>();
 105     nodeSet.addAll(mapLocTupleToNode.values());
 106     return nodeSet;
 107   }
 108
 109   public Set<GlobalFlowNode> getOutNodeSet(GlobalFlowNode node) {
 110
 111     if (!mapFlowNodeToOutNodeSet.containsKey(node)) {
 112       mapFlowNodeToOutNodeSet.put(node, new HashSet<GlobalFlowNode>());
 113     }
 114
 115     return mapFlowNodeToOutNodeSet.get(node);
 116   }
 117
 118   public void writeGraph(String suffix) {
 119
 120     String graphName = "flowgraph_" + md.toString() + suffix;
 121     graphName = graphName.replaceAll("[\\W]", "");
 122
 123     try {
 124       BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
 125       bw.write("digraph " + graphName + " {\n");
 126       bw.write("compound=true;\n");
 127
 128       // then visit every flow node
 129
 130       // Iterator<FlowNode> iter = nodeSet.iterator();
 131       Iterator<GlobalFlowNode> iter = getNodeSet().iterator();
 132
 133       Set<GlobalFlowNode> addedNodeSet = new HashSet<GlobalFlowNode>();
 134
 135       while (iter.hasNext()) {
 136         GlobalFlowNode srcNode = iter.next();
 137
 138         Set<GlobalFlowNode> outNodeSet = getOutNodeSet(srcNode);
 139         for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
 140           GlobalFlowNode dstNode = (GlobalFlowNode) iterator.next();
 141
 142           if (!addedNodeSet.contains(srcNode)) {
 143             drawNode(srcNode, bw);
 144           }
 145
 146           if (!addedNodeSet.contains(dstNode)) {
 147             drawNode(dstNode, bw);
 148           }
 149
 150           bw.write("" + srcNode.getID() + " -> " + dstNode.getID() + ";\n");
 151
 152         }
 153
 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);
 158         // }
 159         // }
 160         // drawEdges(node, bw, addedNodeSet, addedEdgeSet);
 161
 162       }
 163
 164       bw.write("}\n");
 165       bw.close();
 166
 167     } catch (IOException e) {
 168       e.printStackTrace();
 169     }
 170   }
 171
 172   private void drawNode(GlobalFlowNode node, BufferedWriter bw) throws IOException {
 173     bw.write(node.getID() + " [label=\"" + node.getPrettyID() + "\"]" + ";\n");
 174   }
 175
 176   public Set<GlobalFlowNode> getIncomingNodeSet(GlobalFlowNode node) {
 177
 178     Set<GlobalFlowNode> incomingNodeSet = new HashSet<GlobalFlowNode>();
 179     recurIncomingNodeSet(node, incomingNodeSet);
 180
 181     return incomingNodeSet;
 182   }
 183
 184   private void recurIncomingNodeSet(GlobalFlowNode node, Set<GlobalFlowNode> visited) {
 185
 186     for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) {
 187       GlobalFlowNode curNode = (GlobalFlowNode) iterator.next();
 188
 189       Set<GlobalFlowNode> outNodeSet = getOutNodeSet(curNode);
 190
 191       for (Iterator iterator2 = outNodeSet.iterator(); iterator2.hasNext();) {
 192         GlobalFlowNode outNode = (GlobalFlowNode) iterator2.next();
 193
 194         if (outNode.equals(node)) {
 195           if (!visited.contains(curNode)) {
 196             visited.add(curNode);
 197             recurIncomingNodeSet(curNode, visited);
 198           }
 199         }
 200       }
 201     }
 202
 203   }
 204
 205   public Set<GlobalFlowNode> getReachableNodeSetFrom(GlobalFlowNode node) {
 206
 207     Set<GlobalFlowNode> reachableNodeSet = new HashSet<GlobalFlowNode>();
 208     recurReachableNodeSet(node, reachableNodeSet);
 209
 210     return reachableNodeSet;
 211   }
 212
 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);
 220       }
 221     }
 222   }
 223
 224 }