changes: fix all problems of mapping between a flow node/hierarchy node to a lattice...

[IRC.git] / Robust / src / Analysis / SSJava / HierarchyGraph.java

diff --git a/Robust/src/Analysis/SSJava/HierarchyGraph.java b/Robust/src/Analysis/SSJava/HierarchyGraph.java
index 5b0b85f257493d8b68355c418ab72dce7b39c678..6a12849f157d7dc43e8f082a3a71c8cf4104f98a 100644 (file)
--- a/Robust/src/Analysis/SSJava/HierarchyGraph.java
+++ b/Robust/src/Analysis/SSJava/HierarchyGraph.java
@@ -11,6 +11,7 @@ import java.util.Set;
 
 import IR.Descriptor;
 import IR.FieldDescriptor;
+import IR.VarDescriptor;
 
 public class HierarchyGraph {
 
@@ -25,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
@@ -33,12 +36,8 @@ public class HierarchyGraph {
   Map<Set<HNode>, HNode> mapCombineNodeSetToCombinationNode;
   Map<Set<HNode>, Set<HNode>> mapCombineNodeSetToOutgoingNodeSet;
 
-  Map<HNode, String> mapHNodeToLocationName;
-
   Set<HNode> nodeSet;
 
-  public static int seed = 0;
-
   // for the lattice generation
   Map<HNode, Integer> mapHNodeToUniqueIndex;
   Map<HNode, Set<Integer>> mapHNodeToBasis;
@@ -58,11 +57,12 @@ public class HierarchyGraph {
     mapHNodeToUniqueIndex = new HashMap<HNode, Integer>();
     mapHNodeToBasis = new HashMap<HNode, Set<Integer>>();
 
-    mapHNodeToLocationName = new HashMap<HNode, String>();
     mapMergeNodetoMergingSet = new HashMap<HNode, Set<HNode>>();
 
     mapHNodeToCurrentHNode = new HashMap<HNode, HNode>();
 
+    mapHNodeNameToCurrentHNode = new HashMap<String, HNode>();
+
   }
 
   public Descriptor getDesc() {
@@ -73,14 +73,6 @@ public class HierarchyGraph {
     this.desc = desc;
   }
 
-  public void addMapHNodeToLocationName(HNode node, String locName) {
-    mapHNodeToLocationName.put(node, locName);
-  }
-
-  public String getLocationName(HNode node) {
-    return mapHNodeToLocationName.get(node);
-  }
-
   public String getName() {
     return name;
   }
@@ -107,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;
   }
@@ -149,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);
     }
 
   }
@@ -326,6 +326,10 @@ public class HierarchyGraph {
           continue;
         }
 
+        if (!isEligibleForMerging(node1, node2)) {
+          continue;
+        }
+
         if (!node1.equals(node2)) {
 
           Set<HNode> incomingNodeSet2 = getIncomingNodeSet(node2);
@@ -349,6 +353,31 @@ public class HierarchyGraph {
     return false;
   }
 
+  private boolean isEligibleForMerging(HNode node1, HNode node2) {
+
+    System.out.println("********isEligibleForMerging=" + node1 + " " + node2);
+
+    if (node1.isSharedNode() || node2.isSharedNode()) {
+
+      // if either of nodes is a shared node,
+      // all descriptors of node1 & node2 should have a primitive type
+
+      Set<Descriptor> descSet = new HashSet<Descriptor>();
+      descSet.addAll(getDescSetOfNode(node1));
+      descSet.addAll(getDescSetOfNode(node2));
+
+      for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
+        Descriptor desc = (Descriptor) iterator.next();
+        if (!LocationInference.isPrimitive(desc)) {
+          return false;
+        }
+      }
+      System.out.println("******** true");
+      return true;
+    }
+    return false;
+  }
+
   private void addEdgeWithNoCycleCheck(HNode srcHNode, HNode dstHNode) {
     getIncomingNodeSet(dstHNode).add(srcHNode);
     getOutgoingNodeSet(srcHNode).add(dstHNode);
@@ -369,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);
@@ -390,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();) {
@@ -427,25 +456,39 @@ 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("###mergedSkeletonNode=" + mergedSkeletonNode);
     System.out.println("###MERGING NODE=" + set + " new node=" + newMergeNode);
+
+    for (Iterator iterator = set.iterator(); iterator.hasNext();) {
+      HNode hNode = (HNode) iterator.next();
+      System.out.println("old=" + hNode + "----->newNode=" + getCurrentHNode(hNode));
+    }
+
     return newMergeNode;
   }
 
   private void addMapHNodeToCurrentHNode(HNode curNode, HNode newNode) {
     if (curNode.isMergeNode()) {
       Set<HNode> mergingSet = getMergingSet(curNode);
+      mergingSet.add(curNode);
+      System.out.println("addMapHNodeToCurrentHNode curNode=" + curNode + " meringSet="
+          + mergingSet);
       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);
     }
   }
 
@@ -456,12 +499,17 @@ 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);
     for (Iterator iterator = mergedNode.iterator(); iterator.hasNext();) {
       HNode node = (HNode) iterator.next();
       if (node.isMergeNode()) {
+        mergingSet.add(node);
         mergingSet.addAll(getMergingSet(node));
       } else {
         mergingSet.add(node);
@@ -470,7 +518,7 @@ public class HierarchyGraph {
     return mergingSet;
   }
 
-  private Set<Descriptor> getDescSetOfNode(HNode node) {
+  public Set<Descriptor> getDescSetOfNode(HNode node) {
     if (!mapHNodeToDescSet.containsKey(node)) {
       mapHNodeToDescSet.put(node, new HashSet<Descriptor>());
     }
@@ -614,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);
@@ -669,8 +717,10 @@ public class HierarchyGraph {
           HNode outNode = getCombinationNode(combineNode);
           addEdgeWithNoCycleCheck(combinationNode, outNode);
         } else if (curNode.isSkeleton()) {
-          // HNode dstNode = getHNode(curNode.getDescriptor());
+          // HNode dstNode2 = getHNode(curNode.getDescriptor());
           HNode dstNode = getCurrentHNode(curNode);
+          // System.out.println("-----curNode=" + curNode + "------->" + dstNode + "    dstNode2="
+          // + dstNode2);
           addEdgeWithNoCycleCheck(combinationNode, dstNode);
         }
       }
@@ -684,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);
 
@@ -801,6 +851,8 @@ public class HierarchyGraph {
     clone.setMapHNodeToDescSet(getMapHNodeToDescSet());
     clone.setMapHNodetoMergeSet(getMapHNodetoMergeSet());
     clone.setMapHNodeToCurrentHNode(getMapHNodeToCurrentHNode());
+    clone.setMapHNodeNameToCurrentHNode(getMapHNodeNameToCurrentHNode());
+
     return clone;
   }
 
@@ -934,6 +986,7 @@ public class HierarchyGraph {
 
   public void assignUniqueIndexToNode() {
     int idx = 1;
+    System.out.println("nodeSet=" + nodeSet);
     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
       HNode node = (HNode) iterator.next();
       mapHNodeToUniqueIndex.put(node, idx);
@@ -946,7 +999,7 @@ public class HierarchyGraph {
     }
   }
 
-  public BasisSet computeBasisSet() {
+  public BasisSet computeBasisSet(Set<HNode> notGenerateSet) {
 
     // assign a unique index to a node
     assignUniqueIndexToNode();
@@ -955,12 +1008,16 @@ public class HierarchyGraph {
     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
       HNode node = (HNode) iterator.next();
 
+      if (notGenerateSet.contains(node)) {
+        System.out.println("%%%SKIP =" + node);
+        continue;
+      }
       Set<Integer> basis = new HashSet<Integer>();
       basis.addAll(BASISTOPELEMENT);
 
       Set<HNode> reachableNodeSet = getReachableNodeSetFrom(node);
       System.out.println("node=" + node + "    reachableNodeSet=" + reachableNodeSet);
-
+      System.out.println("mapHNodeToUniqueIndex.get(node)=" + mapHNodeToUniqueIndex.get(node));
       // if a node is reachable from the current node
       // need to remove the index of the reachable node from the basis
 
@@ -968,6 +1025,8 @@ public class HierarchyGraph {
       for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
         HNode reachableNode = (HNode) iterator2.next();
         System.out.println("reachableNode=" + reachableNode);
+        System.out.println("getHNodeIndex(reachableNode))="
+            + mapHNodeToUniqueIndex.get(reachableNode));
         int idx = getHNodeIndex(reachableNode);
         basis.remove(idx);
       }