implemented a fixed point based interprocedural analysis that analyzes flow-graphs...

diff --git a/Robust/src/Analysis/SSJava/FlowGraph.java b/Robust/src/Analysis/SSJava/FlowGraph.java
index c1181a5b62a913c975d8be8181e128777940d266..fb051631db47bd80b07f5f845d38adf2d444bebd 100644 (file)
--- a/Robust/src/Analysis/SSJava/FlowGraph.java
+++ b/Robust/src/Analysis/SSJava/FlowGraph.java
@@ -58,6 +58,17 @@ public class FlowGraph {
     return nodeSet;
   }
 
+  public Set<FlowNode> getParameterNodeSet() {
+    Set<FlowNode> paramNodeSet = new HashSet<FlowNode>();
+    for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
+      FlowNode fn = (FlowNode) iterator.next();
+      if (fn.isParameter()) {
+        paramNodeSet.add(fn);
+      }
+    }
+    return paramNodeSet;
+  }
+
   public void addNeighbor(FlowNode node, FlowNode neighbor) {
     Set<FlowNode> set = mapNodeToNeighborSet.get(node);
     if (set == null) {
@@ -68,6 +79,26 @@ public class FlowGraph {
     System.out.println("add a new neighbor " + neighbor + " to " + node);
   }
 
+  public boolean hasEdge(NTuple<Descriptor> fromDescTuple, NTuple<Descriptor> toDescTuple) {
+
+    FlowNode fromNode = mapDescTupleToInferNode.get(fromDescTuple);
+    FlowNode toNode = mapDescTupleToInferNode.get(toDescTuple);
+
+    Set<FlowEdge> fromNodeOutEdgeSet = fromNode.getOutEdgeSet();
+    for (Iterator iterator = fromNodeOutEdgeSet.iterator(); iterator.hasNext();) {
+      FlowEdge flowEdge = (FlowEdge) iterator.next();
+      if (flowEdge.getDst().equals(toNode)) {
+        return true;
+      } else {
+        if (hasEdge(flowEdge.getDst().getDescTuple(), toDescTuple)) {
+          return true;
+        }
+      }
+    }
+
+    return false;
+  }
+
   public void addValueFlowEdge(NTuple<Descriptor> fromDescTuple, NTuple<Descriptor> toDescTuple) {
 
     FlowNode fromNode = mapDescTupleToInferNode.get(fromDescTuple);

diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java
index 66dadfa782d185137835599916be82c75e7694ec..daa435f0e7f80b3df722698c69bc55d4ce44a7cb 100644 (file)
--- a/Robust/src/Analysis/SSJava/LocationInference.java
+++ b/Robust/src/Analysis/SSJava/LocationInference.java
@@ -170,7 +170,7 @@ public class LocationInference {
 
       SSJavaLattice<String> classLattice = cd2lattice.get(cd);
       if (classLattice != null) {
-        ssjava.writeLatticeDotFile(cd, classLattice);
+        ssjava.writeLatticeDotFile(cd, null, classLattice);
       }
 
       while (!toAnalyzeMethodIsEmpty()) {
@@ -178,7 +178,7 @@ public class LocationInference {
         if (ssjava.needTobeAnnotated(md)) {
           SSJavaLattice<String> methodLattice = md2lattice.get(md);
           if (methodLattice != null) {
-            ssjava.writeLatticeDotFile(cd, methodLattice);
+            ssjava.writeLatticeDotFile(cd, md, methodLattice);
           }
         }
       }
@@ -212,16 +212,16 @@ public class LocationInference {
     while (!methodDescriptorsToVisitStack.isEmpty()) {
       // start to analyze leaf node
       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
-      FlatMethod fm = state.getMethodFlat(md);
 
       SSJavaLattice<String> methodLattice =
           new SSJavaLattice<String>(SSJavaLattice.TOP, SSJavaLattice.BOTTOM);
 
+      System.out.println();
       System.out.println("SSJAVA: Inferencing the lattice from " + md);
 
       analyzeMethodLattice(md, methodLattice);
 
-      SSJavaLattice<String> prevMethodLattice = md2lattice.get(md);
+      SSJavaLattice<String> prevMethodLattice = getMethodLattice(md);
 
       if (!methodLattice.equals(prevMethodLattice)) {
         md2lattice.put(md, methodLattice);
@@ -248,16 +248,12 @@ public class LocationInference {
     return desc.getSymbol();
   }
 
-  private void addMappingDescriptorToLocationIdentifer(MethodDescriptor methodDesc,
-      VarDescriptor varDesc, String identifier) {
-    if (!md2LatticeMapping.containsKey(methodDesc)) {
-      md2LatticeMapping.put(methodDesc, new HashMap<VarDescriptor, String>());
-    }
-
-  }
-
   private void analyzeMethodLattice(MethodDescriptor md, SSJavaLattice<String> methodLattice) {
 
+    // first take a look at method invocation nodes to newly added relations
+    // from the callee
+    analyzeLatticeMethodInvocationNode(md);
+
     // visit each node of method flow graph
 
     FlowGraph fg = getFlowGraph(md);
@@ -265,7 +261,6 @@ public class LocationInference {
 
     // for the method lattice, we need to look at the first element of
     // NTuple<Descriptor>
-
     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
       FlowNode srcNode = (FlowNode) iterator.next();
 
@@ -277,112 +272,116 @@ public class LocationInference {
 
         addRelationToLattice(md, methodLattice, srcNode, dstNode);
 
-        // second, take a look at all nodes that are reachable from the source
-        // node
-        recursiveVisitNodes(md, srcNode, dstNode);
-
       }
 
     }
 
   }
 
-  private void addRelationToLattice(MethodDescriptor md, SSJavaLattice<String> methodLattice,
-      FlowNode srcNode, FlowNode dstNode) {
-    if ((srcNode.getDescTuple().size() > 1 && dstNode.getDescTuple().size() > 1)
-        && srcNode.getDescTuple().get(0).equals(dstNode.getDescTuple().get(0))) {
-      // value flow between fields: we don't need to add a binary relation
-      // for this case
-
-      VarDescriptor varDesc = (VarDescriptor) srcNode.getDescTuple().get(0);
-      ClassDescriptor varClassDesc = varDesc.getType().getClassDesc();
+  private void analyzeLatticeMethodInvocationNode(MethodDescriptor mdCaller) {
 
-      extractRelationFromFieldFlows(varClassDesc, srcNode, dstNode, 1);
-      return;
-    }
+    // the transformation for a call site propagates all relations between
+    // parameters from the callee
+    // if the method is virtual, it also grab all relations from any possible
+    // callees
 
-    // add a new binary relation of dstNode < srcNode
+    Set<MethodInvokeNode> setMethodInvokeNode =
+        mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller);
+    if (setMethodInvokeNode != null) {
 
-    String srcSymbol = getSymbol(0, srcNode);
-    String dstSymbol = getSymbol(0, dstNode);
+      for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) {
+        MethodInvokeNode min = (MethodInvokeNode) iterator.next();
+        MethodDescriptor mdCallee = min.getMethod();
+        Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
+        if (mdCallee.isStatic()) {
+          setPossibleCallees.add(mdCallee);
+        } else {
+          setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(mdCallee));
+        }
 
-    methodLattice.addRelationHigherToLower(srcSymbol, dstSymbol);
+        for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
+          MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
+          propagateRelationToCaller(min, mdCaller, possibleMdCallee);
+        }
 
-    if (srcNode.isParameter() && dstNode.isParameter()) {
-      propagateRelationToCaller(md, srcNode, dstNode);
+      }
     }
-  }
 
-  private SSJavaLattice<String> getMethodLattice(MethodDescriptor md) {
-
-    if (!md2lattice.containsKey(md)) {
-      md2lattice.put(md, new SSJavaLattice<String>(SSJavaLattice.TOP, SSJavaLattice.BOTTOM));
-    }
-    return md2lattice.get(md);
   }
 
-  private void propagateRelationToCaller(MethodDescriptor calleeMethodDesc, FlowNode srcNode,
-      FlowNode newVisitNode) {
+  private void propagateRelationToCaller(MethodInvokeNode min, MethodDescriptor mdCaller,
+      MethodDescriptor possibleMdCallee) {
 
-    FlowGraph calleeFlowGraph = getFlowGraph(calleeMethodDesc);
+    SSJavaLattice<String> calleeLattice = getMethodLattice(possibleMdCallee);
 
-    int higherLocIdxCallee = calleeFlowGraph.getParamIdx(srcNode.getDescTuple());
-    int lowerLocIdxCallee = calleeFlowGraph.getParamIdx(newVisitNode.getDescTuple());
+    FlowGraph calleeFlowGraph = getFlowGraph(possibleMdCallee);
 
-    System.out.println(" ssjava.getDependents(md)=" + ssjava.getDependents(calleeMethodDesc));
-    Iterator<MethodDescriptor> depsItr = ssjava.getDependents(calleeMethodDesc).iterator();
-    while (depsItr.hasNext()) {
-      MethodDescriptor callerMethodDesc = depsItr.next();
+    // find parameter node
+    Set<FlowNode> paramNodeSet = calleeFlowGraph.getParameterNodeSet();
 
-      SSJavaLattice<String> callerMethodLattice = md2lattice.get(callerMethodDesc);
+    for (Iterator iterator = paramNodeSet.iterator(); iterator.hasNext();) {
+      FlowNode paramFlowNode1 = (FlowNode) iterator.next();
 
-      Set<MethodInvokeNode> minSet = mapMethodDescriptorToMethodInvokeNodeSet.get(callerMethodDesc);
-      for (Iterator iterator = minSet.iterator(); iterator.hasNext();) {
-        MethodInvokeNode methodInvokeNode = (MethodInvokeNode) iterator.next();
-        if (methodInvokeNode.getMethod().equals(calleeMethodDesc)) {
-          // need to propagate a relation from the callee to the caller
-          // TODO
+      for (Iterator iterator2 = paramNodeSet.iterator(); iterator2.hasNext();) {
+        FlowNode paramFlowNode2 = (FlowNode) iterator2.next();
 
-          System.out.println("higherLocIdxCallee=" + higherLocIdxCallee);
-          System.out.println("lowerLocIdxCallee=" + lowerLocIdxCallee);
-
-          NTuple<Descriptor> higherArg = getArgTupleByArgIdx(methodInvokeNode, higherLocIdxCallee);
-          NTuple<Descriptor> lowerArg = getArgTupleByArgIdx(methodInvokeNode, lowerLocIdxCallee);
+        String paramSymbol1 = getSymbol(0, paramFlowNode1);
+        String paramSymbol2 = getSymbol(0, paramFlowNode2);
+        // if two parameters have relation, we need to propagate this relation
+        // to the caller
+        if (calleeLattice.isComparable(paramSymbol1, paramSymbol2)) {
+          int higherLocIdxCallee;
+          int lowerLocIdxCallee;
+          if (calleeLattice.isGreaterThan(paramSymbol1, paramSymbol2)) {
+            higherLocIdxCallee = calleeFlowGraph.getParamIdx(paramFlowNode1.getDescTuple());
+            lowerLocIdxCallee = calleeFlowGraph.getParamIdx(paramFlowNode2.getDescTuple());
+          } else {
+            higherLocIdxCallee = calleeFlowGraph.getParamIdx(paramFlowNode2.getDescTuple());
+            lowerLocIdxCallee = calleeFlowGraph.getParamIdx(paramFlowNode1.getDescTuple());
+          }
 
-          FlowNode callerHigherFlowNode = getFlowGraph(callerMethodDesc).getFlowNode(higherArg);
-          FlowNode calleeHigherFlowNode = getFlowGraph(callerMethodDesc).getFlowNode(lowerArg);
+          NTuple<Descriptor> higherArg = getArgTupleByArgIdx(min, higherLocIdxCallee);
+          NTuple<Descriptor> lowerArg = getArgTupleByArgIdx(min, lowerLocIdxCallee);
 
-          addRelationToLattice(callerMethodDesc, getMethodLattice(callerMethodDesc),
-              callerHigherFlowNode, calleeHigherFlowNode);
+          addFlowGraphEdge(mdCaller, higherArg, lowerArg);
 
         }
+
       }
 
     }
+
   }
 
-  private void recursiveVisitNodes(MethodDescriptor md, FlowNode srcNode, FlowNode currentVisitNode) {
+  private void addRelationToLattice(MethodDescriptor md, SSJavaLattice<String> methodLattice,
+      FlowNode srcNode, FlowNode dstNode) {
+    if ((srcNode.getDescTuple().size() > 1 && dstNode.getDescTuple().size() > 1)
+        && srcNode.getDescTuple().get(0).equals(dstNode.getDescTuple().get(0))) {
+      // value flow between fields: we don't need to add a binary relation
+      // for this case
+
+      VarDescriptor varDesc = (VarDescriptor) srcNode.getDescTuple().get(0);
+      ClassDescriptor varClassDesc = varDesc.getType().getClassDesc();
+
+      extractRelationFromFieldFlows(varClassDesc, srcNode, dstNode, 1);
+      return;
+    }
 
-    NTuple<Descriptor> srcTuple = srcNode.getDescTuple();
+    // add a new binary relation of dstNode < srcNode
 
-    for (Iterator<FlowEdge> outEdgeIter = currentVisitNode.getOutEdgeSet().iterator(); outEdgeIter
-        .hasNext();) {
+    String srcSymbol = getSymbol(0, srcNode);
+    String dstSymbol = getSymbol(0, dstNode);
 
-      FlowEdge outEdge = outEdgeIter.next();
-      FlowNode newVisitNode = outEdge.getDst();
+    methodLattice.addRelationHigherToLower(srcSymbol, dstSymbol);
 
-      NTuple<Descriptor> newVisitTuple = newVisitNode.getDescTuple();
+  }
 
-      // if both the source node and the newly visit node are parameters,
-      // need to keep this relation, then later add a new relation between
-      // corresponding arguments in the caller's lattice.
-      if (srcNode.isParameter() && newVisitNode.isParameter()) {
-        System.out.println("src=" + srcNode + "            newVisitNode=" + newVisitNode);
-        propagateRelationToCaller(md, srcNode, newVisitNode);
-      }
+  private SSJavaLattice<String> getMethodLattice(MethodDescriptor md) {
 
+    if (!md2lattice.containsKey(md)) {
+      md2lattice.put(md, new SSJavaLattice<String>(SSJavaLattice.TOP, SSJavaLattice.BOTTOM));
     }
-
+    return md2lattice.get(md);
   }
 
   private void extractRelationFromFieldFlows(ClassDescriptor cd, FlowNode srcNode,
@@ -509,7 +508,6 @@ public class LocationInference {
   private void analyzeSwitchStatementNode(MethodDescriptor md, SymbolTable nametable,
       SwitchStatementNode bsn) {
     // TODO Auto-generated method stub
-
   }
 
   private void analyzeFlowSubBlockNode(MethodDescriptor md, SymbolTable nametable,
@@ -1124,9 +1122,13 @@ public class LocationInference {
     return mapMethodDescriptorToFlowGraph.get(md);
   }
 
-  public void addFlowGraphEdge(MethodDescriptor md, NTuple<Descriptor> from, NTuple<Descriptor> to) {
+  public boolean addFlowGraphEdge(MethodDescriptor md, NTuple<Descriptor> from,
+      NTuple<Descriptor> to) {
+    // TODO
+    // return true if it adds a new edge
     FlowGraph graph = getFlowGraph(md);
     graph.addValueFlowEdge(from, to);
+    return true;
   }
 
   public void _debug_printGraph() {

diff --git a/Robust/src/Analysis/SSJava/SSJavaAnalysis.java b/Robust/src/Analysis/SSJava/SSJavaAnalysis.java
index 344dd83b754f93e6412126af47828edb7d5de6c3..b72f077a82cb5f17030ab78073040c3a14d23097 100644 (file)
--- a/Robust/src/Analysis/SSJava/SSJavaAnalysis.java
+++ b/Robust/src/Analysis/SSJava/SSJavaAnalysis.java
@@ -283,7 +283,7 @@ public class SSJavaAnalysis {
 
           if (state.SSJAVADEBUG) {
             // generate lattice dot file
-            writeLatticeDotFile(cd, locOrder);
+            writeLatticeDotFile(cd, null, locOrder);
           }
 
         } else if (marker.equals(METHODDEFAULT)) {
@@ -327,16 +327,23 @@ public class SSJavaAnalysis {
     }
   }
 
-  public void writeLatticeDotFile(ClassDescriptor cd, SSJavaLattice<String> locOrder) {
+  public void writeLatticeDotFile(ClassDescriptor cd, MethodDescriptor md,
+      SSJavaLattice<String> locOrder) {
 
-    String className = cd.getSymbol().replaceAll("[\\W_]", "");
+    String fileName = "lattice_";
+    if (md != null) {
+      fileName +=
+          cd.getSymbol().replaceAll("[\\W_]", "") + "_" + md.getSymbol().replaceAll("[\\W_]", "");
+    } else {
+      fileName += cd.getSymbol().replaceAll("[\\W_]", "");
+    }
 
     Set<Pair<String, String>> pairSet = locOrder.getOrderingPairSet();
 
     try {
-      BufferedWriter bw = new BufferedWriter(new FileWriter(className + ".dot"));
+      BufferedWriter bw = new BufferedWriter(new FileWriter(fileName + ".dot"));
 
-      bw.write("digraph " + className + " {\n");
+      bw.write("digraph " + fileName + " {\n");
 
       for (Iterator iterator = pairSet.iterator(); iterator.hasNext();) {
         // pair is in the form of <higher, lower>