Robust/src/Analysis/SSJava/FlowGraph.java

   1 package Analysis.SSJava;
   2
   3 import java.io.BufferedWriter;
   4 import java.io.File;
   5 import java.io.FileWriter;
   6 import java.io.IOException;
   7 import java.util.HashMap;
   8 import java.util.HashSet;
   9 import java.util.Iterator;
  10 import java.util.Map;
  11 import java.util.Set;
  12 import java.util.Map.Entry;
  13
  14 import Analysis.OoOJava.ConflictEdge;
  15 import Analysis.OoOJava.ConflictNode;
  16 import IR.Descriptor;
  17 import IR.FieldDescriptor;
  18 import IR.MethodDescriptor;
  19 import IR.VarDescriptor;
  20
  21 public class FlowGraph {
  22
  23   MethodDescriptor md;
  24
  25   Set<FlowNode> nodeSet;
  26   Set<FlowNode> returnNodeSet;
  27   FlowNode thisVarNode;
  28
  29   // maps the composite representation of field/var descriptors to infer nodes
  30   Map<NTuple<Descriptor>, FlowNode> mapDescTupleToInferNode;
  31
  32   // maps an infer node to the set of neighbors which is pointed by the node
  33   Map<NTuple<Descriptor>, Set<FlowNode>> mapNodeToNeighborSet;
  34
  35   // maps a paramter descriptor to its index
  36   Map<Descriptor, Integer> mapParamDescToIdx;
  37   boolean debug = true;
  38
  39   public FlowGraph(MethodDescriptor md, Map<Descriptor, Integer> mapParamDescToIdx) {
  40     this.md = md;
  41     this.nodeSet = new HashSet<FlowNode>();
  42     this.mapDescTupleToInferNode = new HashMap<NTuple<Descriptor>, FlowNode>();
  43     this.mapNodeToNeighborSet = new HashMap<NTuple<Descriptor>, Set<FlowNode>>();
  44     this.mapParamDescToIdx = new HashMap<Descriptor, Integer>();
  45     this.mapParamDescToIdx.putAll(mapParamDescToIdx);
  46     this.returnNodeSet = new HashSet<FlowNode>();
  47
  48     // create a node for 'this' varialbe
  49     NTuple<Descriptor> thisDescTuple = new NTuple<Descriptor>();
  50     thisDescTuple.add(md.getThis());
  51     FlowNode thisNode = new FlowNode(thisDescTuple, true);
  52     NTuple<Descriptor> thisVarTuple = new NTuple<Descriptor>();
  53     thisVarTuple.add(md.getThis());
  54     createNewFlowNode(thisVarTuple);
  55     thisVarNode = thisNode;
  56
  57   }
  58
  59   public Set<FlowNode> getNodeSet() {
  60     return nodeSet;
  61   }
  62
  63   public Set<FlowNode> getParameterNodeSet() {
  64     Set<FlowNode> paramNodeSet = new HashSet<FlowNode>();
  65     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
  66       FlowNode fn = (FlowNode) iterator.next();
  67       if (fn.isParameter()) {
  68         paramNodeSet.add(fn);
  69       }
  70     }
  71     return paramNodeSet;
  72   }
  73
  74   public void addNeighbor(FlowNode node, FlowNode neighbor) {
  75     Set<FlowNode> set = mapNodeToNeighborSet.get(node);
  76     if (set == null) {
  77       set = new HashSet<FlowNode>();
  78     }
  79     set.add(neighbor);
  80
  81     System.out.println("add a new neighbor " + neighbor + " to " + node);
  82   }
  83
  84   public boolean hasEdge(NTuple<Descriptor> fromDescTuple, NTuple<Descriptor> toDescTuple) {
  85
  86     FlowNode fromNode = mapDescTupleToInferNode.get(fromDescTuple);
  87     FlowNode toNode = mapDescTupleToInferNode.get(toDescTuple);
  88
  89     Set<FlowEdge> fromNodeOutEdgeSet = fromNode.getOutEdgeSet();
  90     for (Iterator iterator = fromNodeOutEdgeSet.iterator(); iterator.hasNext();) {
  91       FlowEdge flowEdge = (FlowEdge) iterator.next();
  92       if (flowEdge.getDst().equals(toNode)) {
  93         return true;
  94       } else {
  95         if (hasEdge(flowEdge.getDst().getDescTuple(), toDescTuple)) {
  96           return true;
  97         }
  98       }
  99     }
 100
 101     return false;
 102   }
 103
 104   public void addValueFlowEdge(NTuple<Descriptor> fromDescTuple, NTuple<Descriptor> toDescTuple) {
 105
 106     FlowNode fromNode = mapDescTupleToInferNode.get(fromDescTuple);
 107     FlowNode toNode = mapDescTupleToInferNode.get(toDescTuple);
 108
 109     System.out.println("create an edge from " + fromNode + " to " + toNode);
 110
 111     int fromTupleSize = fromDescTuple.size();
 112     NTuple<Descriptor> curTuple = new NTuple<Descriptor>();
 113     for (int i = 0; i < fromTupleSize; i++) {
 114       Descriptor desc = fromDescTuple.get(i);
 115       curTuple.add(desc);
 116       addFlowEdge(getFlowNode(curTuple), toNode, fromDescTuple, toDescTuple);
 117     }
 118
 119     int toTupleSize = toDescTuple.size();
 120     curTuple = new NTuple<Descriptor>();
 121     for (int i = 0; i < toTupleSize; i++) {
 122       Descriptor desc = toDescTuple.get(i);
 123       curTuple.add(desc);
 124       addFlowEdge(fromNode, getFlowNode(curTuple), fromDescTuple, toDescTuple);
 125     }
 126
 127   }
 128
 129   private void addFlowEdge(FlowNode fromNode, FlowNode toNode, NTuple<Descriptor> initTuple,
 130       NTuple<Descriptor> endTuple) {
 131
 132     FlowEdge edge = new FlowEdge(fromNode, toNode, initTuple, endTuple);
 133     fromNode.addOutEdge(edge);
 134
 135     System.out.println("add a new edge=" + edge);
 136
 137   }
 138
 139   public FlowNode getFlowNode(NTuple<Descriptor> descTuple) {
 140     if (mapDescTupleToInferNode.containsKey(descTuple)) {
 141       return mapDescTupleToInferNode.get(descTuple);
 142     } else {
 143       FlowNode node = createNewFlowNode(descTuple);
 144       return node;
 145     }
 146   }
 147
 148   public FlowNode getThisVarNode() {
 149     return thisVarNode;
 150   }
 151
 152   public FlowNode createNewFlowNode(NTuple<Descriptor> tuple) {
 153
 154     if (!mapDescTupleToInferNode.containsKey(tuple)) {
 155
 156       FlowNode node = new FlowNode(tuple, isParamter(tuple));
 157       mapDescTupleToInferNode.put(tuple, node);
 158       nodeSet.add(node);
 159
 160       if (tuple.size() > 1) {
 161         NTuple<Descriptor> baseTuple = tuple.subList(0, tuple.size() - 1);
 162         getFlowNode(baseTuple).addFieldNode(node);
 163       }
 164
 165       System.out.println("Creating new node=" + node);
 166       return node;
 167     } else {
 168       return mapDescTupleToInferNode.get(tuple);
 169     }
 170
 171   }
 172
 173   public void setReturnFlowNode(NTuple<Descriptor> tuple) {
 174
 175     if (!mapDescTupleToInferNode.containsKey(tuple)) {
 176       createNewFlowNode(tuple);
 177     }
 178
 179     FlowNode node = mapDescTupleToInferNode.get(tuple);
 180     node.setReturn(true);
 181
 182     returnNodeSet.add(node);
 183   }
 184
 185   public Set<FlowNode> getReturnNodeSet() {
 186     return returnNodeSet;
 187   }
 188
 189   public boolean isParamter(NTuple<Descriptor> tuple) {
 190     // return true if a descriptor tuple is started with a parameter descriptor
 191     Descriptor firstIdxDesc = tuple.get(0);
 192     return mapParamDescToIdx.containsKey(firstIdxDesc);
 193   }
 194
 195   public int getParamIdx(NTuple<Descriptor> tuple) {
 196     Descriptor firstDesc = tuple.get(0);
 197     return mapParamDescToIdx.get(firstDesc).intValue();
 198   }
 199
 200   private void drawEdges(FlowNode node, BufferedWriter bw, Set<FlowNode> addedNodeSet,
 201       Set<FlowEdge> addedEdgeSet) throws IOException {
 202
 203     Set<FlowEdge> edgeSet = node.getOutEdgeSet();
 204
 205     for (Iterator<FlowEdge> iterator = edgeSet.iterator(); iterator.hasNext();) {
 206       FlowEdge flowEdge = iterator.next();
 207
 208       FlowNode u = flowEdge.getSrc();
 209       FlowNode v = flowEdge.getDst();
 210
 211       if (u.getDescTuple().equals(flowEdge.getInitTuple())
 212           && v.getDescTuple().equals(flowEdge.getEndTuple())) {
 213         // only draw an edge of the actual value flow
 214
 215         if (!addedEdgeSet.contains(flowEdge)) {
 216
 217           if (!addedNodeSet.contains(u)) {
 218             drawNode(u, bw);
 219             addedNodeSet.add(u);
 220           }
 221           if (!addedNodeSet.contains(v)) {
 222             drawNode(v, bw);
 223             addedNodeSet.add(v);
 224           }
 225
 226           bw.write("" + u.getID() + " -> " + v.getID() + ";\n");
 227           addedEdgeSet.add(flowEdge);
 228         }
 229       }
 230
 231     }
 232
 233   }
 234
 235   private void drawNode(FlowNode node, BufferedWriter bw) throws IOException {
 236     bw.write(node.getID() + " [label=\"" + node.getPrettyID() + "\"]" + ";\n");
 237   }
 238
 239   public void writeGraph() throws java.io.IOException {
 240
 241     String graphName = "flowgraph_" + md.toString();
 242     graphName = graphName.replaceAll("[\\W]", "");
 243
 244     BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
 245     bw.write("digraph " + graphName + " {\n");
 246     bw.write("compound=true;\n");
 247
 248     // then visit every flow node
 249
 250     Iterator<FlowNode> iter = nodeSet.iterator();
 251
 252     Set<FlowEdge> addedEdgeSet = new HashSet<FlowEdge>();
 253     Set<FlowNode> addedNodeSet = new HashSet<FlowNode>();
 254
 255     while (iter.hasNext()) {
 256       FlowNode node = iter.next();
 257
 258       if (node.getDescTuple().size() == 1) {
 259         // here, we just care about the local variable
 260         if (node.getFieldNodeSet().size() > 0) {
 261           drawSubgraph(node, bw, addedEdgeSet);
 262         }
 263       }
 264       drawEdges(node, bw, addedNodeSet, addedEdgeSet);
 265
 266     }
 267
 268     bw.write("}\n");
 269     bw.close();
 270
 271   }
 272
 273   public boolean constainsNode(FlowNode node) {
 274     return nodeSet.contains(node);
 275   }
 276
 277   private void drawSubgraph(FlowNode node, BufferedWriter bw, Set<FlowEdge> addedSet)
 278       throws IOException {
 279
 280     bw.write("subgraph cluster_" + node.getID() + "{\n");
 281     bw.write("label=\"" + node.getPrettyID() + "\";\n");
 282
 283     Set<FlowNode> fieldNodeSet = node.getFieldNodeSet();
 284     for (Iterator iterator = fieldNodeSet.iterator(); iterator.hasNext();) {
 285       FlowNode fieldNode = (FlowNode) iterator.next();
 286       if (fieldNode.getFieldNodeSet().size() > 0) {
 287         drawSubgraph(fieldNode, bw, addedSet);
 288       } else {
 289         Descriptor desc = fieldNode.getDescTuple().getLastElement();
 290         if (desc instanceof VarDescriptor) {
 291           VarDescriptor varDesc = (VarDescriptor) desc;
 292           if (varDesc.getType().isPrimitive()) {
 293             bw.write(fieldNode.getID() + " [label=\"" + fieldNode.getPrettyID() + "\"];\n");
 294           }
 295         } else if (desc instanceof FieldDescriptor) {
 296           FieldDescriptor fieldDesc = (FieldDescriptor) desc;
 297           if (fieldDesc.getType().isPrimitive()) {
 298             bw.write(fieldNode.getID() + " [label=\"" + fieldNode.getPrettyID() + "\"];\n");
 299           }
 300         }
 301       }
 302     }
 303
 304     bw.write("}\n");
 305   }
 306 }