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.MethodDescriptor;
  18
  19 public class FlowGraph {
  20
  21   MethodDescriptor md;
  22
  23   Set<FlowNode> nodeSet;
  24   FlowNode thisVarNode;
  25
  26   // maps the composite representation of field/var descriptors to infer nodes
  27   Map<NTuple<Descriptor>, FlowNode> mapDescTupleToInferNode;
  28
  29   // maps an infer node to the set of neighbors which is pointed by the node
  30   Map<NTuple<Descriptor>, Set<FlowNode>> mapNodeToNeighborSet;
  31
  32   boolean debug = true;
  33
  34   public FlowGraph(MethodDescriptor md) {
  35     this.md = md;
  36     nodeSet = new HashSet<FlowNode>();
  37     mapDescTupleToInferNode = new HashMap<NTuple<Descriptor>, FlowNode>();
  38     mapNodeToNeighborSet = new HashMap<NTuple<Descriptor>, Set<FlowNode>>();
  39
  40     // create a node for 'this' varialbe
  41     NTuple<Descriptor> thisDescTuple = new NTuple<Descriptor>();
  42     thisDescTuple.add(md.getThis());
  43     FlowNode thisNode = new FlowNode(thisDescTuple);
  44     NTuple<Descriptor> thisVarTuple = new NTuple<Descriptor>();
  45     thisVarTuple.add(md.getThis());
  46     mapDescTupleToInferNode.put(thisVarTuple, thisNode);
  47     thisVarNode = thisNode;
  48
  49   }
  50
  51   public void addNeighbor(FlowNode node, FlowNode neighbor) {
  52     Set<FlowNode> set = mapNodeToNeighborSet.get(node);
  53     if (set == null) {
  54       set = new HashSet<FlowNode>();
  55     }
  56     set.add(neighbor);
  57
  58     System.out.println("add a new neighbor " + neighbor + " to " + node);
  59   }
  60
  61   public void addValueFlowEdge(NTuple<Descriptor> fromDescTuple, NTuple<Descriptor> toDescTuple) {
  62
  63     FlowNode fromNode = mapDescTupleToInferNode.get(fromDescTuple);
  64     FlowNode toNode = mapDescTupleToInferNode.get(toDescTuple);
  65
  66     System.out.println("create an edge from " + fromNode + " to " + toNode);
  67
  68     int fromTupleSize = fromDescTuple.size();
  69     NTuple<Descriptor> curTuple = new NTuple<Descriptor>();
  70     for (int i = 0; i < fromTupleSize; i++) {
  71       Descriptor desc = fromDescTuple.get(i);
  72       curTuple.add(desc);
  73       addFlowEdge(getFlowNode(curTuple), toNode, fromDescTuple, toDescTuple);
  74     }
  75
  76     int toTupleSize = toDescTuple.size();
  77     curTuple = new NTuple<Descriptor>();
  78     for (int i = 0; i < toTupleSize; i++) {
  79       Descriptor desc = toDescTuple.get(i);
  80       curTuple.add(desc);
  81       addFlowEdge(fromNode, getFlowNode(curTuple), fromDescTuple, toDescTuple);
  82     }
  83
  84   }
  85
  86   private void addFlowEdge(FlowNode fromNode, FlowNode toNode, NTuple<Descriptor> initTuple,
  87       NTuple<Descriptor> endTuple) {
  88
  89     FlowEdge edge = new FlowEdge(fromNode, toNode, initTuple, endTuple);
  90
  91     fromNode.addOutEdge(edge);
  92
  93     System.out.println("add a new edge=" + edge);
  94
  95   }
  96
  97   public FlowNode getFlowNode(NTuple<Descriptor> descTuple) {
  98     if (mapDescTupleToInferNode.containsKey(descTuple)) {
  99       return mapDescTupleToInferNode.get(descTuple);
 100     } else {
 101       FlowNode node = new FlowNode(descTuple);
 102       mapDescTupleToInferNode.put(descTuple, node);
 103       return node;
 104     }
 105   }
 106
 107   public FlowNode getThisVarNode() {
 108     return thisVarNode;
 109   }
 110
 111   public void createNewFlowNode(NTuple<Descriptor> tuple) {
 112
 113     if (!mapDescTupleToInferNode.containsKey(tuple)) {
 114       FlowNode node = new FlowNode(tuple);
 115       mapDescTupleToInferNode.put(tuple, node);
 116       nodeSet.add(node);
 117
 118       if (tuple.size() > 1) {
 119         NTuple<Descriptor> baseTuple = tuple.subList(0, tuple.size() - 1);
 120         getFlowNode(baseTuple).addFieldNode(node);
 121       }
 122
 123       System.out.println("Creating new node=" + node);
 124     }
 125
 126   }
 127
 128   public void writeGraph() throws java.io.IOException {
 129
 130     String graphName = md.toString();
 131     graphName = graphName.replaceAll("[\\W]", "");
 132
 133     BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
 134     bw.write("digraph " + graphName + " {\n");
 135     bw.write("compound=true;\n");
 136
 137     // then visit every flow node
 138
 139     Iterator<FlowNode> iter = nodeSet.iterator();
 140
 141     Set<FlowEdge> addedSet = new HashSet<FlowEdge>();
 142
 143     while (iter.hasNext()) {
 144       FlowNode node = iter.next();
 145
 146       if (node.getFieldNodeSet().size() > 0) {
 147         drawSubgraph(node, bw);
 148       }
 149
 150       String attributes = " [";
 151
 152       attributes += "label=\"" + node.getID() + "\"]";
 153
 154       bw.write(node.getID() + attributes + ";\n");
 155
 156       Set<FlowEdge> edgeSet = node.getOutEdgeSet();
 157
 158       for (Iterator<FlowEdge> iterator = edgeSet.iterator(); iterator.hasNext();) {
 159         FlowEdge flowEdge = iterator.next();
 160
 161         FlowNode u = flowEdge.getSrc();
 162         FlowNode v = flowEdge.getDst();
 163
 164         if (!addedSet.contains(flowEdge)) {
 165           bw.write("" + u.getID() + " -> " + v.getID() + ";\n");
 166           addedSet.add(flowEdge);
 167         }
 168
 169       }
 170     }
 171
 172     bw.write("graphTitle[label=\"" + graphName + "\",shape=box];\n");
 173
 174     bw.write("}\n");
 175     bw.close();
 176
 177   }
 178
 179   private void drawSubgraph(FlowNode node, BufferedWriter bw) throws IOException {
 180
 181     bw.write("  subgraph sg" + node.getID() + "{\n");
 182     // bw.write("  color=gray;\n");
 183     bw.write("  label=\"" + node.getID() + "\";\n");
 184
 185     Set<FlowNode> fieldNodeSet = node.getFieldNodeSet();
 186     for (Iterator iterator = fieldNodeSet.iterator(); iterator.hasNext();) {
 187       FlowNode fieldNode = (FlowNode) iterator.next();
 188       String attribute = fieldNode.getID() + ";\n";
 189       bw.write("  " + attribute);
 190     }
 191
 192     bw.write("  }\n");
 193   }
 194 }