changes.
authoryeom <yeom>
Thu, 19 Apr 2012 00:48:21 +0000 (00:48 +0000)
committeryeom <yeom>
Thu, 19 Apr 2012 00:48:21 +0000 (00:48 +0000)
Robust/src/Analysis/SSJava/FlowEdge.java [new file with mode: 0644]
Robust/src/Analysis/SSJava/FlowGraph.java
Robust/src/Analysis/SSJava/FlowNode.java
Robust/src/Analysis/SSJava/LocationInference.java
Robust/src/Analysis/SSJava/NodeTupleSet.java

diff --git a/Robust/src/Analysis/SSJava/FlowEdge.java b/Robust/src/Analysis/SSJava/FlowEdge.java
new file mode 100644 (file)
index 0000000..5309bac
--- /dev/null
@@ -0,0 +1,73 @@
+package Analysis.SSJava;
+
+import IR.Descriptor;
+
+public class FlowEdge {
+
+  private FlowNode src;
+  private FlowNode dst;
+
+  // indicates that which tuple in the graph initiates this edge
+  private NTuple<Descriptor> initTuple;
+
+  // indicates that which tuple in the graph is the end of this edge
+  private NTuple<Descriptor> endTuple;
+
+  public FlowEdge(FlowNode src, FlowNode dst, NTuple<Descriptor> initTuple,
+      NTuple<Descriptor> endTuple) {
+    this.src = src;
+    this.dst = dst;
+    this.initTuple = initTuple;
+    this.endTuple = endTuple;
+  }
+
+  public String toString() {
+    return "Edge(" + initTuple + "/" + endTuple + "):: " + src + " to " + dst;
+  }
+
+  public FlowNode getSrc() {
+    return src;
+  }
+
+  public void setSrc(FlowNode src) {
+    this.src = src;
+  }
+
+  public FlowNode getDst() {
+    return dst;
+  }
+
+  public void setDst(FlowNode dst) {
+    this.dst = dst;
+  }
+
+  public NTuple<Descriptor> getInitTuple() {
+    return initTuple;
+  }
+
+  public void setInitTuple(NTuple<Descriptor> initTuple) {
+    this.initTuple = initTuple;
+  }
+
+  public int hashCode() {
+    return src.hashCode() + dst.hashCode() + initTuple.hashCode() + endTuple.hashCode();
+  }
+
+  public NTuple<Descriptor> getEndTuple() {
+    return endTuple;
+  }
+
+  public boolean equals(Object obj) {
+
+    if (obj instanceof FlowEdge) {
+      FlowEdge in = (FlowEdge) obj;
+      if (src.equals(in.getSrc()) && dst.equals(in.getDst()) && initTuple.equals(in.getInitTuple())
+          && endTuple.equals(in.getEndTuple())) {
+        return true;
+      }
+    }
+
+    return false;
+  }
+
+}
index a35a93c..32af6cc 100644 (file)
@@ -1,10 +1,18 @@
 package Analysis.SSJava;
 
+import java.io.BufferedWriter;
+import java.io.File;
+import java.io.FileWriter;
+import java.io.IOException;
 import java.util.HashMap;
 import java.util.HashSet;
+import java.util.Iterator;
 import java.util.Map;
 import java.util.Set;
+import java.util.Map.Entry;
 
+import Analysis.OoOJava.ConflictEdge;
+import Analysis.OoOJava.ConflictNode;
 import IR.Descriptor;
 import IR.MethodDescriptor;
 
@@ -30,7 +38,9 @@ public class FlowGraph {
     mapNodeToNeighborSet = new HashMap<NTuple<Descriptor>, Set<FlowNode>>();
 
     // create a node for 'this' varialbe
-    FlowNode thisNode = new FlowNode(null, md.getThis());
+    NTuple<Descriptor> thisDescTuple = new NTuple<Descriptor>();
+    thisDescTuple.add(md.getThis());
+    FlowNode thisNode = new FlowNode(thisDescTuple);
     NTuple<Descriptor> thisVarTuple = new NTuple<Descriptor>();
     thisVarTuple.add(md.getThis());
     mapDescTupleToInferNode.put(thisVarTuple, thisNode);
@@ -60,7 +70,7 @@ public class FlowGraph {
     for (int i = 0; i < fromTupleSize; i++) {
       Descriptor desc = fromDescTuple.get(i);
       curTuple.add(desc);
-      addNeighbor(getInferNode(curTuple), toNode);
+      addFlowEdge(getFlowNode(curTuple), toNode, fromDescTuple, toDescTuple);
     }
 
     int toTupleSize = toDescTuple.size();
@@ -68,30 +78,117 @@ public class FlowGraph {
     for (int i = 0; i < toTupleSize; i++) {
       Descriptor desc = toDescTuple.get(i);
       curTuple.add(desc);
-      addNeighbor(fromNode, getInferNode(curTuple));
+      addFlowEdge(fromNode, getFlowNode(curTuple), fromDescTuple, toDescTuple);
     }
 
   }
 
-  public FlowNode getInferNode(NTuple<Descriptor> descTuple) {
+  private void addFlowEdge(FlowNode fromNode, FlowNode toNode, NTuple<Descriptor> initTuple,
+      NTuple<Descriptor> endTuple) {
+
+    FlowEdge edge = new FlowEdge(fromNode, toNode, initTuple, endTuple);
+
+    fromNode.addOutEdge(edge);
+
+    System.out.println("add a new edge=" + edge);
+
+  }
+
+  public FlowNode getFlowNode(NTuple<Descriptor> descTuple) {
     if (mapDescTupleToInferNode.containsKey(descTuple)) {
       return mapDescTupleToInferNode.get(descTuple);
+    } else {
+      FlowNode node = new FlowNode(descTuple);
+      mapDescTupleToInferNode.put(descTuple, node);
+      return node;
     }
-    return null;
   }
 
   public FlowNode getThisVarNode() {
     return thisVarNode;
   }
 
-  public void createNewFlowNode(NTuple<Descriptor> base) {
+  public void createNewFlowNode(NTuple<Descriptor> tuple) {
+
+    if (!mapDescTupleToInferNode.containsKey(tuple)) {
+      FlowNode node = new FlowNode(tuple);
+      mapDescTupleToInferNode.put(tuple, node);
+      nodeSet.add(node);
+
+      if (tuple.size() > 1) {
+        NTuple<Descriptor> baseTuple = tuple.subList(0, tuple.size() - 1);
+        getFlowNode(baseTuple).addFieldNode(node);
+      }
+
+      System.out.println("Creating new node=" + node);
+    }
+
+  }
+
+  public void writeGraph() throws java.io.IOException {
+
+    String graphName = md.toString();
+    graphName = graphName.replaceAll("[\\W]", "");
+
+    BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
+    bw.write("digraph " + graphName + " {\n");
+    bw.write("compound=true;\n");
+
+    // then visit every flow node
+
+    Iterator<FlowNode> iter = nodeSet.iterator();
 
-    FlowNode node = new FlowNode(base);
-    mapDescTupleToInferNode.put(base, node);
+    Set<FlowEdge> addedSet = new HashSet<FlowEdge>();
 
-    System.out.println("Creating new node=" + node);
+    while (iter.hasNext()) {
+      FlowNode node = iter.next();
+
+      if (node.getFieldNodeSet().size() > 0) {
+        drawSubgraph(node, bw);
+      }
+
+      String attributes = " [";
+
+      attributes += "label=\"" + node.getID() + "\"]";
+
+      bw.write(node.getID() + attributes + ";\n");
+
+      Set<FlowEdge> edgeSet = node.getOutEdgeSet();
+
+      for (Iterator<FlowEdge> iterator = edgeSet.iterator(); iterator.hasNext();) {
+        FlowEdge flowEdge = iterator.next();
+
+        FlowNode u = flowEdge.getSrc();
+        FlowNode v = flowEdge.getDst();
+
+        if (!addedSet.contains(flowEdge)) {
+          bw.write("" + u.getID() + " -> " + v.getID() + ";\n");
+          addedSet.add(flowEdge);
+        }
+
+      }
+    }
+
+    bw.write("graphTitle[label=\"" + graphName + "\",shape=box];\n");
+
+    bw.write("}\n");
+    bw.close();
 
   }
-  
 
+  private void drawSubgraph(FlowNode node, BufferedWriter bw) throws IOException {
+
+    bw.write("  subgraph sg" + node.getID() + "{\n");
+    // bw.write("  color=gray;\n");
+    bw.write("  label=\"" + node.getID() + "\";\n");
+
+    Set<FlowNode> fieldNodeSet = node.getFieldNodeSet();
+    for (Iterator iterator = fieldNodeSet.iterator(); iterator.hasNext();) {
+      FlowNode fieldNode = (FlowNode) iterator.next();
+      String attribute = fieldNode.getID() + ";\n";
+      bw.write("  " + attribute);
+    }
+
+    bw.write("  }\n");
+  }
 }
\ No newline at end of file
index cc7d4ee..ee97a2c 100644 (file)
@@ -1,5 +1,7 @@
 package Analysis.SSJava;
 
+import java.util.HashSet;
+import java.util.Iterator;
 import java.util.Set;
 
 import IR.Descriptor;
@@ -13,15 +15,23 @@ public class FlowNode {
   // this set contains fields of the base type
   private Set<FlowNode> fieldNodeSet;
 
-  public FlowNode(Descriptor desc) {
-    this(null, desc);
+  public Set<FlowNode> getFieldNodeSet() {
+    return fieldNodeSet;
   }
 
-  public FlowNode(NTuple<Descriptor> base) {
-    this(base, null);
-  }
+  private Set<FlowEdge> outEdgeSet;
+
+  public FlowNode(NTuple<Descriptor> tuple) {
 
-  public FlowNode(NTuple<Descriptor> base, Descriptor desc) {
+    NTuple<Descriptor> base = null;
+    Descriptor desc = null;
+    if (tuple.size() > 1) {
+      base = tuple.subList(0, tuple.size() - 1);
+      desc = tuple.get(tuple.size() - 1);
+    } else {
+      base = tuple;
+    }
+    fieldNodeSet = new HashSet<FlowNode>();
     descTuple = new NTuple<Descriptor>();
     if (base != null) {
       descTuple.addAll(base);
@@ -29,6 +39,11 @@ public class FlowNode {
     if (desc != null) {
       descTuple.add(desc);
     }
+    outEdgeSet = new HashSet<FlowEdge>();
+  }
+
+  public void addFieldNode(FlowNode node) {
+    fieldNodeSet.add(node);
   }
 
   public NTuple<Descriptor> getDescTuple() {
@@ -43,4 +58,41 @@ public class FlowNode {
     return "[FlowNode]::" + descTuple;
   }
 
+  public Iterator<FlowEdge> iteratorOfOutEdges() {
+    return outEdgeSet.iterator();
+  }
+
+  public void addOutEdge(FlowEdge out) {
+    outEdgeSet.add(out);
+  }
+
+  public Set<FlowEdge> getOutEdgeSet() {
+    return outEdgeSet;
+  }
+
+  public int hashCode() {
+    return 7 + descTuple.hashCode();
+  }
+
+  public boolean equals(Object obj) {
+
+    if (obj instanceof FlowNode) {
+      FlowNode in = (FlowNode) obj;
+      if (descTuple.equals(in.getDescTuple())) {
+        return true;
+      }
+    }
+
+    return false;
+
+  }
+
+  public String getID() {
+    String id = "";
+    for (int i = 0; i < descTuple.size(); i++) {
+      id += descTuple.get(i).getSymbol();
+    }
+    return id;
+  }
+
 }
index c99c6bb..fe0900c 100644 (file)
@@ -1,5 +1,6 @@
 package Analysis.SSJava;
 
+import java.io.IOException;
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.Comparator;
@@ -123,6 +124,8 @@ public class LocationInference {
       }
     }
 
+    _debug_printGraph();
+
   }
 
   private void analyzeMethodBody(ClassDescriptor cd, MethodDescriptor md) {
@@ -217,8 +220,7 @@ public class LocationInference {
     if (dn.getExpression() != null) {
 
       NodeTupleSet tupleSetRHS = new NodeTupleSet();
-      analyzeFlowExpressionNode(md, nametable, dn.getExpression(), tupleSetRHS,
-          new NTuple<Descriptor>());
+      analyzeFlowExpressionNode(md, nametable, dn.getExpression(), tupleSetRHS, null);
 
       // add a new flow edge from rhs to lhs
       for (Iterator<NTuple<Descriptor>> iter = tupleSetRHS.iterator(); iter.hasNext();) {
@@ -240,6 +242,7 @@ public class LocationInference {
 
     // note that expression node can create more than one flow node
     // nodeSet contains of flow nodes
+    // base is always assigned to null except name node case!
 
     NTuple<Descriptor> flowTuple;
 
@@ -261,8 +264,7 @@ public class LocationInference {
       return flowTuple;
 
     case Kind.OpNode:
-      // return analyzeOpNode(md, nametable, (OpNode) en, new
-      // HashSet<FlowNode>());
+      analyzeFlowOpNode(md, nametable, (OpNode) en, nodeSet);
       break;
 
     case Kind.CreateObjectNode:
@@ -343,21 +345,22 @@ public class LocationInference {
 
   }
 
-  private Set<FlowNode> analyzeOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on,
-      Set<FlowNode> nodeSet) {
+  private void analyzeFlowOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on,
+      NodeTupleSet nodeSet) {
 
-    ClassDescriptor cd = md.getClassDesc();
+    System.out.println("### OPNode=" + on.printNode(0));
+
+    NodeTupleSet leftOpSet = new NodeTupleSet();
+    NodeTupleSet rightOpSet = new NodeTupleSet();
 
     // left operand
-    // NTuple<Descriptor> leftOpTuple =
-    // analyzeFlowExpressionNode(md, nametable, on.getLeft(), new
-    // NTuple<Descriptor>());
+    analyzeFlowExpressionNode(md, nametable, on.getLeft(), leftOpSet, null);
+    System.out.println("leftOpSet=" + leftOpSet);
 
     if (on.getRight() != null) {
       // right operand
-      // NTuple<Descriptor> rightOpTuple =
-      // analyzeFlowExpressionNode(md, nametable, on.getRight(), new
-      // NTuple<Descriptor>());
+      analyzeFlowExpressionNode(md, nametable, on.getRight(), rightOpSet, null);
+      System.out.println("rightOpSet=" + rightOpSet);
     }
 
     Operation op = on.getOp();
@@ -368,7 +371,8 @@ public class LocationInference {
     case Operation.UNARYMINUS:
     case Operation.LOGIC_NOT:
       // single operand
-      // return leftLoc;
+      nodeSet.addTupleSet(leftOpSet);
+      break;
 
     case Operation.LOGIC_OR:
     case Operation.LOGIC_AND:
@@ -392,12 +396,10 @@ public class LocationInference {
     case Operation.RIGHTSHIFT:
     case Operation.URIGHTSHIFT:
 
-      Set<CompositeLocation> inputSet = new HashSet<CompositeLocation>();
-      // inputSet.add(leftLoc);
-      // inputSet.add(rightLoc);
-      // CompositeLocation glbCompLoc =
-      // CompositeLattice.calculateGLB(inputSet, generateErrorMessage(cd, on));
-      // return glbCompLoc;
+      // there are two operands
+      nodeSet.addTupleSet(leftOpSet);
+      nodeSet.addTupleSet(rightOpSet);
+      break;
 
     default:
       throw new Error(op.toString());
@@ -550,7 +552,7 @@ public class LocationInference {
 
     // if LHS is array access node, need to capture value flows between an array
     // and its index value
-    analyzeFlowExpressionNode(md, nametable, an.getDest(), nodeSetLHS, base);
+    analyzeFlowExpressionNode(md, nametable, an.getDest(), nodeSetLHS, null);
     System.out.println("ASSIGNMENT NODE nodeSetLHS=" + nodeSetLHS);
     // NTuple<Descriptor> lhsDescTuple = analyzeFlowExpressionNode(md,
     // nametable, an.getDest(), base);
@@ -560,20 +562,22 @@ public class LocationInference {
       analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null);
       System.out.println("ASSIGNMENT NODE nodeSetRHS=" + nodeSetRHS);
 
-    } else {
+      // creates edges from RHS to LHS
+      for (Iterator<NTuple<Descriptor>> iter = nodeSetRHS.iterator(); iter.hasNext();) {
+        NTuple<Descriptor> fromTuple = iter.next();
+        for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
+          NTuple<Descriptor> toTuple = iter2.next();
+          addFlowGraphEdge(md, fromTuple, toTuple);
+        }
+      }
 
+    } else {
       // postinc case
-      // src & dest are same
-
-    }
-
-    // creates edges from RHS to LHS
-    for (Iterator<NTuple<Descriptor>> iter = nodeSetRHS.iterator(); iter.hasNext();) {
-      NTuple<Descriptor> fromTuple = iter.next();
       for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
-        NTuple<Descriptor> toTuple = iter2.next();
-        addFlowGraphEdge(md, fromTuple, toTuple);
+        NTuple<Descriptor> tuple = iter2.next();
+        addFlowGraphEdge(md, tuple, tuple);
       }
+
     }
 
   }
@@ -587,4 +591,19 @@ public class LocationInference {
     graph.addValueFlowEdge(from, to);
   }
 
+  public void _debug_printGraph() {
+    Set<MethodDescriptor> keySet = mapMethodDescriptorToFlowGraph.keySet();
+
+    for (Iterator<MethodDescriptor> iterator = keySet.iterator(); iterator.hasNext();) {
+      MethodDescriptor md = (MethodDescriptor) iterator.next();
+      FlowGraph fg = mapMethodDescriptorToFlowGraph.get(md);
+      try {
+        fg.writeGraph();
+      } catch (IOException e) {
+        e.printStackTrace();
+      }
+    }
+
+  }
+
 }
index d793424..30fb1fb 100644 (file)
@@ -8,7 +8,7 @@ import IR.Descriptor;
 
 public class NodeTupleSet {
 
-  Set<NTuple<Descriptor>> set;
+  private Set<NTuple<Descriptor>> set;
 
   public NodeTupleSet() {
     set = new HashSet<NTuple<Descriptor>>();
@@ -21,12 +21,12 @@ public class NodeTupleSet {
     // for example, if we have input <a,b,c>, we need to add additional element
     // <a,b> and <a> to the set
 
-    NTuple<Descriptor> cur = new NTuple<Descriptor>();
-    for (int i = 0; i < tuple.size(); i++) {
-      Descriptor d = tuple.get(i);
-      cur.add(d);
-      set.add(new NTuple<Descriptor>(cur));
-    }
+    // NTuple<Descriptor> cur = new NTuple<Descriptor>();
+    // for (int i = 0; i < tuple.size(); i++) {
+    // Descriptor d = tuple.get(i);
+    // cur.add(d);
+    // set.add(new NTuple<Descriptor>(cur));
+    // }
 
     set.add(tuple);
   }
@@ -39,4 +39,11 @@ public class NodeTupleSet {
     return set.toString();
   }
 
+  public Set<NTuple<Descriptor>> getSet() {
+    return set;
+  }
+
+  public void addTupleSet(NodeTupleSet in) {
+    set.addAll(in.getSet());
+  }
 }