more changes.
authoryeom <yeom>
Fri, 20 Apr 2012 00:21:04 +0000 (00:21 +0000)
committeryeom <yeom>
Fri, 20 Apr 2012 00:21:04 +0000 (00:21 +0000)
Robust/src/Analysis/SSJava/FlowDownCheck.java
Robust/src/Analysis/SSJava/FlowGraph.java
Robust/src/Analysis/SSJava/FlowNode.java
Robust/src/Analysis/SSJava/LocationInference.java
Robust/src/Analysis/SSJava/NTuple.java
Robust/src/Analysis/SSJava/NodeTupleSet.java

index 01d60c2c0966858491e1405dc5ae966c8dc950b3..45ceee7537df0f509f70b62a3ababa32bd803424 100644 (file)
@@ -606,6 +606,8 @@ public class FlowDownCheck {
     } else {
       // check 'for loop' case
       BlockNode bn = ln.getInitializer();
+      // need to check initialization node
+      checkLocationFromBlockNode(md, nametable, bn, constraint);
       bn.getVarTable().setParent(nametable);
 
       // calculate glb location of condition and update statements
index 32af6ccf7b28267ff4b6edf794b505b8d75fd61e..049317d8ee210ca72c975d20e774be05c10d9ef5 100644 (file)
@@ -14,7 +14,9 @@ import java.util.Map.Entry;
 import Analysis.OoOJava.ConflictEdge;
 import Analysis.OoOJava.ConflictNode;
 import IR.Descriptor;
+import IR.FieldDescriptor;
 import IR.MethodDescriptor;
+import IR.VarDescriptor;
 
 public class FlowGraph {
 
@@ -87,7 +89,6 @@ public class FlowGraph {
       NTuple<Descriptor> endTuple) {
 
     FlowEdge edge = new FlowEdge(fromNode, toNode, initTuple, endTuple);
-
     fromNode.addOutEdge(edge);
 
     System.out.println("add a new edge=" + edge);
@@ -98,8 +99,7 @@ public class FlowGraph {
     if (mapDescTupleToInferNode.containsKey(descTuple)) {
       return mapDescTupleToInferNode.get(descTuple);
     } else {
-      FlowNode node = new FlowNode(descTuple);
-      mapDescTupleToInferNode.put(descTuple, node);
+      FlowNode node = createNewFlowNode(descTuple);
       return node;
     }
   }
@@ -108,7 +108,7 @@ public class FlowGraph {
     return thisVarNode;
   }
 
-  public void createNewFlowNode(NTuple<Descriptor> tuple) {
+  public FlowNode createNewFlowNode(NTuple<Descriptor> tuple) {
 
     if (!mapDescTupleToInferNode.containsKey(tuple)) {
       FlowNode node = new FlowNode(tuple);
@@ -121,10 +121,52 @@ public class FlowGraph {
       }
 
       System.out.println("Creating new node=" + node);
+      return node;
+    } else {
+      return mapDescTupleToInferNode.get(tuple);
     }
 
   }
 
+  private void drawEdges(FlowNode node, BufferedWriter bw, Set<FlowNode> addedNodeSet,
+      Set<FlowEdge> addedEdgeSet) throws IOException {
+
+    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 (u.getDescTuple().equals(flowEdge.getInitTuple())
+          && v.getDescTuple().equals(flowEdge.getEndTuple())) {
+        // only draw an edge of the actual value flow
+
+        if (!addedEdgeSet.contains(flowEdge)) {
+
+          if (!addedNodeSet.contains(u)) {
+            drawNode(u, bw);
+            addedNodeSet.add(u);
+          }
+          if (!addedNodeSet.contains(v)) {
+            drawNode(v, bw);
+            addedNodeSet.add(v);
+          }
+
+          bw.write("" + u.getID() + " -> " + v.getID() + ";\n");
+          addedEdgeSet.add(flowEdge);
+        }
+      }
+
+    }
+
+  }
+
+  private void drawNode(FlowNode node, BufferedWriter bw) throws IOException {
+    bw.write(node.getID() + " [label=\"" + node.getPrettyID() + "\"]" + ";\n");
+  }
+
   public void writeGraph() throws java.io.IOException {
 
     String graphName = md.toString();
@@ -138,57 +180,58 @@ public class FlowGraph {
 
     Iterator<FlowNode> iter = nodeSet.iterator();
 
-    Set<FlowEdge> addedSet = new HashSet<FlowEdge>();
+    Set<FlowEdge> addedEdgeSet = new HashSet<FlowEdge>();
+    Set<FlowNode> addedNodeSet = new HashSet<FlowNode>();
 
     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);
+      if (node.getDescTuple().size() == 1) {
+        // here, we just care about the local variable
+        if (node.getFieldNodeSet().size() > 0) {
+          drawSubgraph(node, bw, addedEdgeSet);
         }
-
       }
-    }
+      drawEdges(node, bw, addedNodeSet, addedEdgeSet);
 
-    bw.write("graphTitle[label=\"" + graphName + "\",shape=box];\n");
+    }
 
     bw.write("}\n");
     bw.close();
 
   }
 
-  private void drawSubgraph(FlowNode node, BufferedWriter bw) throws IOException {
+  public boolean constainsNode(FlowNode node) {
+    return nodeSet.contains(node);
+  }
 
-    bw.write("  subgraph sg" + node.getID() + "{\n");
-    // bw.write("  color=gray;\n");
-    bw.write("  label=\"" + node.getID() + "\";\n");
+  private void drawSubgraph(FlowNode node, BufferedWriter bw, Set<FlowEdge> addedSet)
+      throws IOException {
+
+    bw.write("subgraph cluster_" + node.getID() + "{\n");
+    bw.write("label=\"" + node.getPrettyID() + "\";\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);
+      if (fieldNode.getFieldNodeSet().size() > 0) {
+        drawSubgraph(fieldNode, bw, addedSet);
+      } else {
+        Descriptor desc = fieldNode.getDescTuple().getLastElement();
+        if (desc instanceof VarDescriptor) {
+          VarDescriptor varDesc = (VarDescriptor) desc;
+          if (varDesc.getType().isPrimitive()) {
+            bw.write(fieldNode.getID() + " [label=\"" + fieldNode.getPrettyID() + "\"];\n");
+          }
+        } else if (desc instanceof FieldDescriptor) {
+          FieldDescriptor fieldDesc = (FieldDescriptor) desc;
+          if (fieldDesc.getType().isPrimitive()) {
+            bw.write(fieldNode.getID() + " [label=\"" + fieldNode.getPrettyID() + "\"];\n");
+          }
+        }
+      }
     }
 
-    bw.write("  }\n");
+    bw.write("}\n");
   }
 }
\ No newline at end of file
index ee97a2c7560e6b489428098796a9aea08c3684ed..86edb08d6c463b158ab56114acda1af13e9703f8 100644 (file)
@@ -95,4 +95,15 @@ public class FlowNode {
     return id;
   }
 
+  public String getPrettyID() {
+    String id = "<";
+    for (int i = 0; i < descTuple.size(); i++) {
+      if (i != 0) {
+        id += ",";
+      }
+      id += descTuple.get(i).getSymbol();
+    }
+    id += ">";
+    return id;
+  }
 }
index fe0900c91b56f5e476d31d1327f60a5113bc8363..cb2bb28b804465a23f6866cafe0b5e9315485a68 100644 (file)
@@ -130,37 +130,38 @@ public class LocationInference {
 
   private void analyzeMethodBody(ClassDescriptor cd, MethodDescriptor md) {
     BlockNode bn = state.getMethodBody(md);
-    analyzeBlockNode(md, md.getParameterTable(), bn);
+    analyzeFlowBlockNode(md, md.getParameterTable(), bn, null);
   }
 
-  private void analyzeBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn) {
+  private void analyzeFlowBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn,
+      NodeTupleSet implicitFlowTupleSet) {
 
     bn.getVarTable().setParent(nametable);
     for (int i = 0; i < bn.size(); i++) {
       BlockStatementNode bsn = bn.get(i);
-      analyzeBlockStatementNode(md, bn.getVarTable(), bsn);
+      analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet);
     }
 
   }
 
   private void analyzeBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
-      BlockStatementNode bsn) {
+      BlockStatementNode bsn, NodeTupleSet implicitFlowTupleSet) {
 
     switch (bsn.kind()) {
     case Kind.BlockExpressionNode:
-      analyzeBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn);
+      analyzeBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn, implicitFlowTupleSet);
       break;
 
     case Kind.DeclarationNode:
-      analyzeFlowDeclarationNode(md, nametable, (DeclarationNode) bsn);
+      analyzeFlowDeclarationNode(md, nametable, (DeclarationNode) bsn, implicitFlowTupleSet);
       break;
 
     case Kind.IfStatementNode:
-      analyzeIfStatementNode(md, nametable, (IfStatementNode) bsn);
+      analyzeFlowIfStatementNode(md, nametable, (IfStatementNode) bsn, implicitFlowTupleSet);
       break;
 
     case Kind.LoopNode:
-      analyzeLoopNode(md, nametable, (LoopNode) bsn);
+      analyzeFlowLoopNode(md, nametable, (LoopNode) bsn, implicitFlowTupleSet);
       break;
 
     case Kind.ReturnNode:
@@ -168,7 +169,7 @@ public class LocationInference {
       break;
 
     case Kind.SubBlockNode:
-      analyzeSubBlockNode(md, nametable, (SubBlockNode) bsn);
+      analyzeFlowSubBlockNode(md, nametable, (SubBlockNode) bsn, implicitFlowTupleSet);
       break;
 
     case Kind.ContinueBreakNode:
@@ -188,9 +189,9 @@ public class LocationInference {
 
   }
 
-  private void analyzeSubBlockNode(MethodDescriptor md, SymbolTable nametable, SubBlockNode bsn) {
-    // TODO Auto-generated method stub
-
+  private void analyzeFlowSubBlockNode(MethodDescriptor md, SymbolTable nametable,
+      SubBlockNode sbn, NodeTupleSet implicitFlowTupleSet) {
+    analyzeFlowBlockNode(md, nametable, sbn.getBlockNode(), implicitFlowTupleSet);
   }
 
   private void analyzeReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode bsn) {
@@ -198,19 +199,58 @@ public class LocationInference {
 
   }
 
-  private void analyzeLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode bsn) {
-    // TODO Auto-generated method stub
+  private void analyzeFlowLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln,
+      NodeTupleSet implicitFlowTupleSet) {
+
+    if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) {
+
+      NodeTupleSet condTupleNode = new NodeTupleSet();
+      analyzeFlowExpressionNode(md, nametable, ln.getCondition(), condTupleNode, null,
+          implicitFlowTupleSet);
+      condTupleNode.addTupleSet(implicitFlowTupleSet);
+      System.out.println("condTupleNode=" + condTupleNode);
+
+      // add edges from condNodeTupleSet to all nodes of conditional nodes
+      analyzeFlowBlockNode(md, nametable, ln.getBody(), condTupleNode);
+
+    } else {
+      // check 'for loop' case
+      BlockNode bn = ln.getInitializer();
+      analyzeFlowBlockNode(md, nametable, bn, implicitFlowTupleSet);
+      bn.getVarTable().setParent(nametable);
+
+      NodeTupleSet condTupleNode = new NodeTupleSet();
+      analyzeFlowExpressionNode(md, nametable, ln.getCondition(), condTupleNode, null,
+          implicitFlowTupleSet);
+      condTupleNode.addTupleSet(implicitFlowTupleSet);
+      System.out.println("condTupleNode=" + condTupleNode);
+
+      analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(), condTupleNode);
+      analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(), condTupleNode);
+
+    }
 
   }
 
-  private void analyzeIfStatementNode(MethodDescriptor md, SymbolTable nametable,
-      IfStatementNode bsn) {
-    // TODO Auto-generated method stub
+  private void analyzeFlowIfStatementNode(MethodDescriptor md, SymbolTable nametable,
+      IfStatementNode isn, NodeTupleSet implicitFlowTupleSet) {
+
+    NodeTupleSet condTupleNode = new NodeTupleSet();
+    analyzeFlowExpressionNode(md, nametable, isn.getCondition(), condTupleNode, null,
+        implicitFlowTupleSet);
+
+    // add edges from condNodeTupleSet to all nodes of conditional nodes
+    condTupleNode.addTupleSet(implicitFlowTupleSet);
+    analyzeFlowBlockNode(md, nametable, isn.getTrueBlock(), condTupleNode);
+
+    if (isn.getFalseBlock() != null) {
+      analyzeFlowBlockNode(md, nametable, isn.getFalseBlock(), condTupleNode);
+    }
 
   }
 
   private void analyzeFlowDeclarationNode(MethodDescriptor md, SymbolTable nametable,
-      DeclarationNode dn) {
+      DeclarationNode dn, NodeTupleSet implicitFlowTupleSet) {
 
     VarDescriptor vd = dn.getVarDescriptor();
     NTuple<Descriptor> tupleLHS = new NTuple<Descriptor>();
@@ -220,7 +260,8 @@ public class LocationInference {
     if (dn.getExpression() != null) {
 
       NodeTupleSet tupleSetRHS = new NodeTupleSet();
-      analyzeFlowExpressionNode(md, nametable, dn.getExpression(), tupleSetRHS, null);
+      analyzeFlowExpressionNode(md, nametable, dn.getExpression(), tupleSetRHS, null,
+          implicitFlowTupleSet);
 
       // add a new flow edge from rhs to lhs
       for (Iterator<NTuple<Descriptor>> iter = tupleSetRHS.iterator(); iter.hasNext();) {
@@ -233,12 +274,13 @@ public class LocationInference {
   }
 
   private void analyzeBlockExpressionNode(MethodDescriptor md, SymbolTable nametable,
-      BlockExpressionNode ben) {
-    analyzeFlowExpressionNode(md, nametable, ben.getExpression(), null, null);
+      BlockExpressionNode ben, NodeTupleSet implicitFlowTupleSet) {
+    analyzeFlowExpressionNode(md, nametable, ben.getExpression(), null, null, implicitFlowTupleSet);
   }
 
   private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
-      ExpressionNode en, NodeTupleSet nodeSet, NTuple<Descriptor> base) {
+      ExpressionNode en, NodeTupleSet nodeSet, NTuple<Descriptor> base,
+      NodeTupleSet implicitFlowTupleSet) {
 
     // note that expression node can create more than one flow node
     // nodeSet contains of flow nodes
@@ -249,22 +291,25 @@ public class LocationInference {
     switch (en.kind()) {
 
     case Kind.AssignmentNode:
-      analyzeFlowAssignmentNode(md, nametable, (AssignmentNode) en, base);
+      analyzeFlowAssignmentNode(md, nametable, (AssignmentNode) en, base, implicitFlowTupleSet);
       break;
 
     case Kind.FieldAccessNode:
-      flowTuple = analyzeFlowFieldAccessNode(md, nametable, (FieldAccessNode) en, nodeSet, base);
+      flowTuple =
+          analyzeFlowFieldAccessNode(md, nametable, (FieldAccessNode) en, nodeSet, base,
+              implicitFlowTupleSet);
       nodeSet.addTuple(flowTuple);
       return flowTuple;
 
     case Kind.NameNode:
       NodeTupleSet nameNodeSet = new NodeTupleSet();
-      flowTuple = analyzeFlowNameNode(md, nametable, (NameNode) en, nameNodeSet, base);
+      flowTuple =
+          analyzeFlowNameNode(md, nametable, (NameNode) en, nameNodeSet, base, implicitFlowTupleSet);
       nodeSet.addTuple(flowTuple);
       return flowTuple;
 
     case Kind.OpNode:
-      analyzeFlowOpNode(md, nametable, (OpNode) en, nodeSet);
+      analyzeFlowOpNode(md, nametable, (OpNode) en, nodeSet, implicitFlowTupleSet);
       break;
 
     case Kind.CreateObjectNode:
@@ -346,20 +391,19 @@ public class LocationInference {
   }
 
   private void analyzeFlowOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on,
-      NodeTupleSet nodeSet) {
-
-    System.out.println("### OPNode=" + on.printNode(0));
+      NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
 
     NodeTupleSet leftOpSet = new NodeTupleSet();
     NodeTupleSet rightOpSet = new NodeTupleSet();
 
     // left operand
-    analyzeFlowExpressionNode(md, nametable, on.getLeft(), leftOpSet, null);
+    analyzeFlowExpressionNode(md, nametable, on.getLeft(), leftOpSet, null, implicitFlowTupleSet);
     System.out.println("leftOpSet=" + leftOpSet);
 
     if (on.getRight() != null) {
       // right operand
-      analyzeFlowExpressionNode(md, nametable, on.getRight(), rightOpSet, null);
+      analyzeFlowExpressionNode(md, nametable, on.getRight(), rightOpSet, null,
+          implicitFlowTupleSet);
       System.out.println("rightOpSet=" + rightOpSet);
     }
 
@@ -407,7 +451,7 @@ public class LocationInference {
   }
 
   private NTuple<Descriptor> analyzeFlowNameNode(MethodDescriptor md, SymbolTable nametable,
-      NameNode nn, NodeTupleSet nodeSet, NTuple<Descriptor> base) {
+      NameNode nn, NodeTupleSet nodeSet, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
 
     if (base == null) {
       base = new NTuple<Descriptor>();
@@ -415,7 +459,8 @@ public class LocationInference {
 
     NameDescriptor nd = nn.getName();
     if (nd.getBase() != null) {
-      analyzeFlowExpressionNode(md, nametable, nn.getExpression(), nodeSet, base);
+      analyzeFlowExpressionNode(md, nametable, nn.getExpression(), nodeSet, base,
+          implicitFlowTupleSet);
     } else {
       String varname = nd.toString();
       if (varname.equals("this")) {
@@ -491,7 +536,8 @@ public class LocationInference {
   }
 
   private NTuple<Descriptor> analyzeFlowFieldAccessNode(MethodDescriptor md, SymbolTable nametable,
-      FieldAccessNode fan, NodeTupleSet nodeSet, NTuple<Descriptor> base) {
+      FieldAccessNode fan, NodeTupleSet nodeSet, NTuple<Descriptor> base,
+      NodeTupleSet implicitFlowTupleSet) {
 
     ExpressionNode left = fan.getExpression();
     TypeDescriptor ltd = left.getType();
@@ -516,7 +562,7 @@ public class LocationInference {
     // left = aan.getExpression();
     // }
     // fanNodeSet
-    base = analyzeFlowExpressionNode(md, nametable, left, nodeSet, base);
+    base = analyzeFlowExpressionNode(md, nametable, left, nodeSet, base, implicitFlowTupleSet);
 
     if (!left.getType().isPrimitive()) {
 
@@ -534,12 +580,10 @@ public class LocationInference {
   }
 
   private void analyzeFlowAssignmentNode(MethodDescriptor md, SymbolTable nametable,
-      AssignmentNode an, NTuple<Descriptor> base) {
+      AssignmentNode an, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
 
     System.out.println("analyzeFlowAssignmentNode=" + an);
 
-    ClassDescriptor cd = md.getClassDesc();
-
     NodeTupleSet nodeSetRHS = new NodeTupleSet();
     NodeTupleSet nodeSetLHS = new NodeTupleSet();
 
@@ -552,14 +596,14 @@ 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, null);
+    analyzeFlowExpressionNode(md, nametable, an.getDest(), nodeSetLHS, null, implicitFlowTupleSet);
     System.out.println("ASSIGNMENT NODE nodeSetLHS=" + nodeSetLHS);
     // NTuple<Descriptor> lhsDescTuple = analyzeFlowExpressionNode(md,
     // nametable, an.getDest(), base);
 
     if (!postinc) {
       // analyze value flows of rhs expression
-      analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null);
+      analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null, implicitFlowTupleSet);
       System.out.println("ASSIGNMENT NODE nodeSetRHS=" + nodeSetRHS);
 
       // creates edges from RHS to LHS
@@ -571,6 +615,15 @@ public class LocationInference {
         }
       }
 
+      // creates edges from implicitFlowTupleSet to LHS
+      for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.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
       for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
index 289b46b947f77b5afa9249f1524e3cd5d5a5a1e1..513d7a507590de95f3270fe804cd1da3e3ce97b5 100644 (file)
@@ -105,4 +105,8 @@ public class NTuple<T> {
 
   }
 
+  public T getLastElement() {
+    return elements.get(elements.size() - 1);
+  }
+
 }
index 30fb1fb852adbb4e2ec55d50976fafdb4c4be14f..6850960485f676def5fdab549dd21111e98d8c01 100644 (file)
@@ -44,6 +44,8 @@ public class NodeTupleSet {
   }
 
   public void addTupleSet(NodeTupleSet in) {
-    set.addAll(in.getSet());
+    if (in != null) {
+      set.addAll(in.getSet());
+    }
   }
 }