changes: fix all problems of mapping between a flow node/hierarchy node to a lattice...
authoryeom <yeom>
Mon, 15 Oct 2012 02:42:50 +0000 (02:42 +0000)
committeryeom <yeom>
Mon, 15 Oct 2012 02:42:50 +0000 (02:42 +0000)
Robust/src/Analysis/SSJava/BuildLattice.java
Robust/src/Analysis/SSJava/HierarchyGraph.java
Robust/src/Analysis/SSJava/LocationInference.java

index b3cdd8a..780819f 100644 (file)
@@ -12,7 +12,6 @@ import Util.Pair;
 
 public class BuildLattice {
 
-  public static int seed = 0;
   private LocationInference infer;
 
   private final HNode topNode;
@@ -162,9 +161,11 @@ public class BuildLattice {
 
     Map<TripleItem, String> mapIntermediateLoc = new HashMap<TripleItem, String>();
 
+    System.out.println("*insert=" + desc);
+    System.out.println("***nodeSet=" + nodeSet);
     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
       HNode node = (HNode) iterator.next();
-      // System.out.println("node=" + node);
+      System.out.println("node=" + node);
       if (node.isSkeleton() && (!visited.contains(node))) {
         visited.add(node);
 
@@ -174,38 +175,8 @@ public class BuildLattice {
 
           if (!outNode.isSkeleton()) {
             if (outNode.isCombinationNode()) {
-              // expand the combination node 'outNode'
-              // here we need to expand the corresponding combination location in the lattice
-              HNode combinationNodeInSCGraph = getCombinationNodeInSCGraph(desc, outNode);
 
-              Set<HNode> combineSkeletonNodeSet =
-                  simpleGraph.getCombineSetByCombinationNode(outNode);
-
-              // System.out.println("combineSkeletonNodeSet=" + combineSkeletonNodeSet);
-
-              Set<HNode> combinationNodeSet =
-                  simpleGraph.getCombinationNodeSetByCombineNodeSet(combineSkeletonNodeSet);
-
-              // System.out.println("combinationNodeSet=" + combinationNodeSet);
-
-              Set<HNode> endNodeSetFromSimpleGraph =
-                  simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(outNode,
-                      combinationNodeSet);
-              // System.out.println("-endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph);
-              Set<HNode> endCombNodeSet = new HashSet<HNode>();
-              for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) {
-                HNode endNode = (HNode) iterator3.next();
-                endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode));
-              }
-              visited.add(outNode);
-
-              // follows the straight line up to another skeleton/combination node
-              if (endCombNodeSet.size() > 0) {
-                endCombNodeSet =
-                    removeTransitivelyReachToNode(desc, combinationNodeInSCGraph, endCombNodeSet);
-                recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited,
-                    mapIntermediateLoc, 1, locSummary, outNode);
-              }
+              expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode);
 
             } else {
               // we have a node that is neither combination or skeleton node
@@ -248,9 +219,15 @@ public class BuildLattice {
           }
 
         }
+      } else if (!node.isSkeleton() && node.isCombinationNode()) {
+
+        expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, node);
+
       } else if (!node.isSkeleton() && !node.isCombinationNode() && !node.isMergeNode()
           && !visited.contains(node)) {
 
+        System.out.println("n=" + node);
+
         // an intermediate node 'node' may be located between "TOP" location and a skeleton node
         int sizeIncomingNode = simpleGraph.getIncomingNodeSet(node).size();
 
@@ -285,6 +262,45 @@ public class BuildLattice {
 
   }
 
+  private void expandCombinationNode(Descriptor desc, SSJavaLattice<String> lattice,
+      Set<HNode> visited, Map<TripleItem, String> mapIntermediateLoc, LocationSummary locSummary,
+      HNode cnode) {
+
+    // expand the combination node 'outNode'
+    // here we need to expand the corresponding combination location in the lattice
+    HNode combinationNodeInSCGraph = getCombinationNodeInSCGraph(desc, cnode);
+
+    HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc);
+
+    Set<HNode> combineSkeletonNodeSet = simpleGraph.getCombineSetByCombinationNode(cnode);
+
+    // System.out.println("combineSkeletonNodeSet=" + combineSkeletonNodeSet);
+
+    Set<HNode> combinationNodeSet =
+        simpleGraph.getCombinationNodeSetByCombineNodeSet(combineSkeletonNodeSet);
+
+    // System.out.println("combinationNodeSet=" + combinationNodeSet);
+
+    Set<HNode> endNodeSetFromSimpleGraph =
+        simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(cnode, combinationNodeSet);
+    // System.out.println("-endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph);
+    Set<HNode> endCombNodeSet = new HashSet<HNode>();
+    for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) {
+      HNode endNode = (HNode) iterator3.next();
+      endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode));
+    }
+    visited.add(cnode);
+
+    // follows the straight line up to another skeleton/combination node
+    if (endCombNodeSet.size() > 0) {
+      endCombNodeSet =
+          removeTransitivelyReachToNode(desc, combinationNodeInSCGraph, endCombNodeSet);
+      recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited,
+          mapIntermediateLoc, 1, locSummary, cnode);
+    }
+
+  }
+
   private Set<HNode> removeTransitivelyReachToNode(Descriptor desc, HNode startNode,
       Set<HNode> endNodeSet) {
 
@@ -315,8 +331,15 @@ public class BuildLattice {
 
   private HNode getDirectlyReachableNodeFromStartNodeReachToEndNode(HierarchyGraph scGraph,
       HNode startNode, HNode endNode) {
+    System.out.println("getDirectlyReachableNodeFromStartNodeReachToEndNode start=" + startNode
+        + " end=" + endNode);
     Set<HNode> connected = new HashSet<HNode>();
     recurDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, endNode, connected);
+    if (connected.size() == 0) {
+      connected.add(endNode);
+    }
+    System.out.println("connected=" + connected);
+
     return connected.iterator().next();
   }
 
@@ -329,7 +352,6 @@ public class BuildLattice {
       if (inNode.equals(startNode)) {
         connected.add(curNode);
       } else {
-        // System.out.println("inNode=" + inNode);
         recurDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, inNode, connected);
       }
     }
@@ -344,7 +366,7 @@ public class BuildLattice {
     // System.out.println("item=" + item);
     if (!mapIntermediateLoc.containsKey(item)) {
       // need to create a new intermediate location in the lattice
-      String newLocName = "ILOC" + (seed++);
+      String newLocName = "ILOC" + (LocationInference.locSeed++);
       String above;
       if (idx == 1) {
         above = startNode.getName();
@@ -366,6 +388,7 @@ public class BuildLattice {
     }
 
     String locName = mapIntermediateLoc.get(item);
+
     HierarchyGraph graph = infer.getSimpleHierarchyGraph(desc);
 
     Set<Descriptor> descSet = graph.getDescSetOfNode(curNode);
@@ -373,7 +396,8 @@ public class BuildLattice {
       Descriptor d = (Descriptor) iterator.next();
       locSummary.addMapHNodeNameToLocationName(d.getSymbol(), locName);
     }
-    // locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName);
+    locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName);
+
 
     Set<HNode> outSet = graph.getOutgoingNodeSet(curNode);
     for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
@@ -382,6 +406,8 @@ public class BuildLattice {
         visited.add(outNode);
         recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc,
             idx + 1, locSummary, outNode);
+      } else if (!outNode.isSkeleton() && outNode.isCombinationNode() && !visited.contains(outNode)) {
+        expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode);
       }
     }
 
@@ -400,7 +426,7 @@ public class BuildLattice {
         String newLocName = combinationNodeInSCGraph.getName();
         mapIntermediateLoc.put(item, newLocName);
       } else {
-        String newLocName = "ILOC" + (seed++);
+        String newLocName = "ILOC" + (LocationInference.locSeed++);
         int prevIdx = idx - 1;
         TripleItem prevItem = new TripleItem(combinationNodeInSCGraph, endNodeSet, prevIdx);
         above = mapIntermediateLoc.get(prevItem);
@@ -424,6 +450,7 @@ public class BuildLattice {
       Descriptor d = (Descriptor) iterator.next();
       locSummary.addMapHNodeNameToLocationName(d.getSymbol(), locName);
     }
+    locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName);
 
     // System.out.println("-TripleItem=" + item);
     // System.out.println("-curNode=" + curNode.getName() + " locName=" + locName);
@@ -457,7 +484,7 @@ public class BuildLattice {
       if (inputGraph.BASISTOPELEMENT.equals(F)) {
         return SSJavaAnalysis.BOTTOM;
       } else {
-        String str = "LOC" + (seed++);
+        String str = "LOC" + (LocationInference.locSeed++);
         mapF2LocName.put(F, str);
         return str;
       }
index d575f4f..6a12849 100644 (file)
@@ -26,6 +26,8 @@ public class HierarchyGraph {
   Map<Descriptor, HNode> mapDescToHNode;
   Map<HNode, Set<Descriptor>> mapHNodeToDescSet;
   Map<HNode, HNode> mapHNodeToCurrentHNode; // tracking which node corresponds to the initial node
+  Map<String, HNode> mapHNodeNameToCurrentHNode; // tracking which node corresponds to the initial
+                                                 // node
   Map<HNode, Set<HNode>> mapMergeNodetoMergingSet;
 
   // data structures for a combination node
@@ -36,8 +38,6 @@ public class HierarchyGraph {
 
   Set<HNode> nodeSet;
 
-  public static int seed = 0;
-
   // for the lattice generation
   Map<HNode, Integer> mapHNodeToUniqueIndex;
   Map<HNode, Set<Integer>> mapHNodeToBasis;
@@ -61,6 +61,8 @@ public class HierarchyGraph {
 
     mapHNodeToCurrentHNode = new HashMap<HNode, HNode>();
 
+    mapHNodeNameToCurrentHNode = new HashMap<String, HNode>();
+
   }
 
   public Descriptor getDesc() {
@@ -97,10 +99,18 @@ public class HierarchyGraph {
     return mapHNodeToCurrentHNode;
   }
 
+  public Map<String, HNode> getMapHNodeNameToCurrentHNode() {
+    return mapHNodeNameToCurrentHNode;
+  }
+
   public void setMapHNodeToCurrentHNode(Map<HNode, HNode> mapHNodeToCurrentHNode) {
     this.mapHNodeToCurrentHNode = mapHNodeToCurrentHNode;
   }
 
+  public void setMapHNodeNameToCurrentHNode(Map<String, HNode> mapHNodeNameToCurrentHNode) {
+    this.mapHNodeNameToCurrentHNode = mapHNodeNameToCurrentHNode;
+  }
+
   public Map<Descriptor, HNode> getMapDescToHNode() {
     return mapDescToHNode;
   }
@@ -139,11 +149,11 @@ public class HierarchyGraph {
       HNode newMergeNode = mergeNodes(possibleCycleSet, false);
       newMergeNode.setSharedNode(true);
       System.out.println("### INTRODUCE A NEW MERGE NODE: " + newMergeNode);
-      System.out.println("### CYCLIC VALUE FLOW: " + srcHNode + " -> " + dstHNode);
+      System.out.println("### CYCLIC VALUE FLOW: " + srcHNode + " -> " + dstHNode + "\n");
     } else {
       getIncomingNodeSet(dstHNode).add(srcHNode);
       getOutgoingNodeSet(srcHNode).add(dstHNode);
-      System.out.println("add an edge " + srcHNode + " -> " + dstHNode);
+      // System.out.println("add an edge " + srcHNode + " -> " + dstHNode);
     }
 
   }
@@ -388,9 +398,9 @@ public class HierarchyGraph {
     String nodeName;
     boolean isMergeNode = false;
     if (onlyCombinationNodes) {
-      nodeName = "Comb" + (seed++);
+      nodeName = "Comb" + (LocationInference.locSeed++);
     } else {
-      nodeName = "Node" + (seed++);
+      nodeName = "Node" + (LocationInference.locSeed++);
       isMergeNode = true;
     }
     HNode newMergeNode = new HNode(nodeName);
@@ -409,7 +419,7 @@ public class HierarchyGraph {
       }
     }
     System.out.println("--Set merging node=" + newMergeNode + " as a skeleton=" + set
-        + " hasSkeleton=" + hasSkeleton);
+        + " hasSkeleton=" + hasSkeleton + " CUR DESC=" + desc);
     newMergeNode.setSkeleton(hasSkeleton);
 
     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
@@ -446,12 +456,15 @@ public class HierarchyGraph {
         mergedSkeletonNode.add(merged);
       }
     }
-    mapMergeNodetoMergingSet.put(newMergeNode, mergedSkeletonNode);
-    for (Iterator iterator = mergedSkeletonNode.iterator(); iterator.hasNext();) {
+
+    // mapMergeNodetoMergingSet.put(newMergeNode, mergedSkeletonNode);
+    // for (Iterator iterator = set.iterator(); iterator.hasNext();) {
+    mapMergeNodetoMergingSet.put(newMergeNode, set);
+    for (Iterator iterator = set.iterator(); iterator.hasNext();) {
       HNode mergedNode = (HNode) iterator.next();
       addMapHNodeToCurrentHNode(mergedNode, newMergeNode);
     }
-    System.out.println("\n###mergedSkeletonNode=" + mergedSkeletonNode);
+    System.out.println("###mergedSkeletonNode=" + mergedSkeletonNode);
     System.out.println("###MERGING NODE=" + set + " new node=" + newMergeNode);
 
     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
@@ -471,9 +484,11 @@ public class HierarchyGraph {
       for (Iterator iterator = mergingSet.iterator(); iterator.hasNext();) {
         HNode mergingNode = (HNode) iterator.next();
         mapHNodeToCurrentHNode.put(mergingNode, newNode);
+        mapHNodeNameToCurrentHNode.put(mergingNode.getName(), newNode);
       }
     } else {
       mapHNodeToCurrentHNode.put(curNode, newNode);
+      mapHNodeNameToCurrentHNode.put(curNode.getName(), newNode);
     }
   }
 
@@ -484,6 +499,10 @@ public class HierarchyGraph {
     return mapHNodeToCurrentHNode.get(node);
   }
 
+  public HNode getCurrentHNode(String nodeName) {
+    return mapHNodeNameToCurrentHNode.get(nodeName);
+  }
+
   private Set<HNode> getMergingSet(HNode mergeNode) {
     Set<HNode> mergingSet = new HashSet<HNode>();
     Set<HNode> mergedNode = mapMergeNodetoMergingSet.get(mergeNode);
@@ -643,7 +662,7 @@ public class HierarchyGraph {
 
   public HNode getCombinationNode(Set<HNode> combineSet) {
     if (!mapCombineNodeSetToCombinationNode.containsKey(combineSet)) {
-      String name = "COMB" + (seed++);
+      String name = "COMB" + (LocationInference.locSeed++);
       HNode node = new HNode(name);
       node.setCombinationNode(true);
       nodeSet.add(node);
@@ -715,7 +734,7 @@ public class HierarchyGraph {
   private void addCombinationNode(HNode curNode, Set<HNode> reachToSet, Set<HNode> reachableSet) {
     if (!mapSkeletonNodeSetToCombinationNode.containsKey(reachToSet)) {
       // need to create a new combination node
-      String nodeName = "Comb" + (seed++);
+      String nodeName = "Comb" + (LocationInference.locSeed++);
       HNode newCombinationNode = new HNode(nodeName);
       newCombinationNode.setCombinationNode(true);
 
@@ -832,6 +851,8 @@ public class HierarchyGraph {
     clone.setMapHNodeToDescSet(getMapHNodeToDescSet());
     clone.setMapHNodetoMergeSet(getMapHNodetoMergeSet());
     clone.setMapHNodeToCurrentHNode(getMapHNodeToCurrentHNode());
+    clone.setMapHNodeNameToCurrentHNode(getMapHNodeNameToCurrentHNode());
+
     return clone;
   }
 
index 34c1df9..dbcc415 100644 (file)
@@ -140,7 +140,7 @@ public class LocationInference {
 
   boolean debug = true;
 
-  private static int locSeed = 0;
+  public static int locSeed = 0;
 
   public LocationInference(SSJavaAnalysis ssjava, State state) {
     this.ssjava = ssjava;
@@ -350,6 +350,14 @@ public class LocationInference {
       String locName;
       if (!enclosingDesc.equals(GLOBALDESC)) {
         LocationSummary locSummary = getLocationSummary(enclosingDesc);
+        HierarchyGraph hierarchyGraph = getSimpleHierarchyGraph(enclosingDesc);
+        if (hierarchyGraph != null) {
+
+          HNode curNode = hierarchyGraph.getCurrentHNode(nodeIdentifier);
+          if (curNode != null) {
+            nodeIdentifier = curNode.getName();
+          }
+        }
         locName = locSummary.getLocationName(nodeIdentifier);
       } else {
         locName = nodeIdentifier;
@@ -363,7 +371,6 @@ public class LocationInference {
 
   private void translateCompositeLocationAssignmentToFlowGraph(MethodDescriptor mdCaller) {
 
-
     // First, assign a composite location to a node in the flow graph
     GlobalFlowGraph callerGlobalFlowGraph = getSubGlobalFlowGraph(mdCaller);
 
@@ -499,8 +506,8 @@ public class LocationInference {
       }
     }
 
-    System.out.println("-----*AFTER TRANSLATING COMP LOC MAPPING, CALLEE MAPPING="
-        + calleeGlobalGraph.getMapLocationToInferCompositeLocation());
+    // System.out.println("-----*AFTER TRANSLATING COMP LOC MAPPING, CALLEE MAPPING="
+    // + calleeGlobalGraph.getMapLocationToInferCompositeLocation());
 
     // If the location of an argument has a composite location
     // need to assign a proper composite location to the corresponding callee parameter
@@ -1723,6 +1730,7 @@ public class LocationInference {
           NTuple<Descriptor> srcCurTuple = srcNode.getCurrentDescTuple();
           NTuple<Descriptor> dstCurTuple = dstNode.getCurrentDescTuple();
 
+
           if ((srcCurTuple.size() > 1 && dstCurTuple.size() > 1)
               && srcCurTuple.get(0).equals(dstCurTuple.get(0))) {
 
@@ -2961,7 +2969,6 @@ public class LocationInference {
   private void propagateFlowsToCallerWithNoCompositeLocation(MethodInvokeNode min,
       MethodDescriptor mdCaller, MethodDescriptor mdCallee) {
 
-
     // if the parameter A reaches to the parameter B
     // then, add an edge the argument A -> the argument B to the caller's flow
     // graph
@@ -4484,7 +4491,6 @@ public class LocationInference {
             argTuple = new NTuple<Descriptor>();
           }
 
-
           addArgIdxMap(min, idx, argTuple);
 
           FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx);