changes. it generates correct lattices.
authoryeom <yeom>
Thu, 8 Nov 2012 06:49:58 +0000 (06:49 +0000)
committeryeom <yeom>
Thu, 8 Nov 2012 06:49:58 +0000 (06:49 +0000)
Robust/src/Analysis/SSJava/BuildLattice.java
Robust/src/Analysis/SSJava/HierarchyGraph.java
Robust/src/Analysis/SSJava/LocationInference.java

index cbddb35..fd2d0e8 100644 (file)
@@ -17,10 +17,14 @@ public class BuildLattice {
   private Map<HNode, TripleItem> mapSharedNodeToTripleItem;
   private Map<HNode, Integer> mapHNodeToHighestIndex;
 
+  private Map<Pair<HNode, HNode>, Integer> mapItemToHighestIndex;
+
   public BuildLattice(LocationInference infer) {
     this.infer = infer;
     this.mapSharedNodeToTripleItem = new HashMap<HNode, TripleItem>();
     this.mapHNodeToHighestIndex = new HashMap<HNode, Integer>();
+    this.mapItemToHighestIndex = new HashMap<Pair<HNode, HNode>, Integer>();
+
   }
 
   public SSJavaLattice<String> buildLattice(Descriptor desc) {
@@ -166,355 +170,6 @@ public class BuildLattice {
   public SSJavaLattice<String> insertIntermediateNodesToStraightLine(Descriptor desc,
       SSJavaLattice<String> skeletonLattice) {
 
-    mapSharedNodeToTripleItem.clear();
-
-    HierarchyGraph hierarchyGraph = infer.getSimpleHierarchyGraph(desc);
-    HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
-    LocationSummary locSummary = infer.getLocationSummary(desc);
-    SSJavaLattice<String> lattice = skeletonLattice.clone();
-    Set<HNode> visited = new HashSet<HNode>();
-    Set<HNode> scNodeSet = scGraph.getNodeSet();
-
-    Map<TripleItem, String> mapIntermediateLoc = new HashMap<TripleItem, String>();
-
-    for (Iterator iterator = scNodeSet.iterator(); iterator.hasNext();) {
-      HNode scNode = (HNode) iterator.next();
-      Set<HNode> outHierarchyNodeSet = hierarchyGraph.getOutgoingNodeSet(scNode);
-      for (Iterator iterator2 = outHierarchyNodeSet.iterator(); iterator2.hasNext();) {
-        HNode outHierarchyNode = (HNode) iterator2.next();
-
-        if (!visited.contains(outHierarchyNode)) {
-
-          if (!outHierarchyNode.isCombinationNode() && !outHierarchyNode.isSkeleton()) {
-            visited.add(outHierarchyNode);
-            Set<HNode> outSCNodeSet = scGraph.getOutgoingNodeSet(scNode);
-
-            if (outSCNodeSet.size() > 0) {
-              // follows the straight line up to another skeleton/combination node
-              outSCNodeSet = removeTransitivelyReachToNode(desc, scNode, outSCNodeSet);
-            } else if (outSCNodeSet.size() == 0) {
-              // the outNode is (directly/transitively) connected to the bottom node
-              // therefore, we just add a dummy bottom HNode to the endCombNodeSet.
-              outSCNodeSet.add(LocationInference.BOTTOMHNODE);
-            }
-
-            recurDFVisitNormalNode(scNode, outSCNodeSet, outHierarchyNode, 1, desc, lattice,
-                visited, locSummary, mapIntermediateLoc);
-          } else if (outHierarchyNode.isCombinationNode()) {
-            visited.add(outHierarchyNode);
-            expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary,
-                outHierarchyNode);
-          }
-
-        }
-
-      }
-
-    }
-
-    // add shared locations
-    Set<HNode> sharedNodeSet = mapSharedNodeToTripleItem.keySet();
-    for (Iterator iterator = sharedNodeSet.iterator(); iterator.hasNext();) {
-      HNode sharedNode = (HNode) iterator.next();
-      TripleItem item = mapSharedNodeToTripleItem.get(sharedNode);
-      String nonSharedLocName = mapIntermediateLoc.get(item);
-      // System.out.println("sharedNode=" + sharedNode + "    locName=" + nonSharedLocName);
-
-      String newLocName;
-      if (locSummary.getHNodeNameSetByLatticeLoationName(nonSharedLocName) != null
-          && !lattice.isSharedLoc(nonSharedLocName)) {
-        // need to generate a new shared location in the lattice, which is one level lower than the
-        // 'locName' location
-        newLocName = "ILOC" + (LocationInference.locSeed++);
-
-        // Set<String> aboveElementSet = getAboveElementSet(lattice, locName);
-        Set<String> belowElementSet = new HashSet<String>();
-        belowElementSet.addAll(lattice.get(nonSharedLocName));
-
-        // System.out.println("nonSharedLocName=" + nonSharedLocName + "   belowElementSet="
-        // + belowElementSet + "  newLocName=" + newLocName);
-
-        lattice.insertNewLocationBetween(nonSharedLocName, belowElementSet, newLocName);
-      } else {
-        newLocName = nonSharedLocName;
-      }
-
-      lattice.addSharedLoc(newLocName);
-      HierarchyGraph graph = infer.getSimpleHierarchyGraph(desc);
-      Set<Descriptor> descSet = graph.getDescSetOfNode(sharedNode);
-      for (Iterator iterator2 = descSet.iterator(); iterator2.hasNext();) {
-        Descriptor d = (Descriptor) iterator2.next();
-        locSummary.addMapHNodeNameToLocationName(d.getSymbol(), newLocName);
-      }
-      locSummary.addMapHNodeNameToLocationName(sharedNode.getName(), newLocName);
-
-    }
-
-    return lattice;
-  }
-
-  private void recurDFVisitNormalNode(HNode scStartNode, Set<HNode> scEndNodeSet,
-      HNode curHierarchyNode, int idx, Descriptor desc, SSJavaLattice<String> lattice,
-      Set<HNode> visited, LocationSummary locSummary, Map<TripleItem, String> mapIntermediateLoc) {
-
-    TripleItem item = new TripleItem(scStartNode, scEndNodeSet, idx);
-    // System.out.println("item=" + item);
-    if (!mapIntermediateLoc.containsKey(item)) {
-      // need to create a new intermediate location in the lattice
-      String newLocName = "ILOC" + (LocationInference.locSeed++);
-      String above;
-      if (idx == 1) {
-        above = scStartNode.getName();
-      } else {
-        int prevIdx = idx - 1;
-        TripleItem prevItem = new TripleItem(scStartNode, scEndNodeSet, prevIdx);
-        above = mapIntermediateLoc.get(prevItem);
-      }
-
-      Set<String> belowSet = new HashSet<String>();
-      for (Iterator iterator = scEndNodeSet.iterator(); iterator.hasNext();) {
-        HNode endNode = (HNode) iterator.next();
-        String locName;
-        if (locSummary.getMapHNodeNameToLocationName().containsKey(endNode.getName())) {
-          locName = locSummary.getLocationName(endNode.getName());
-        } else {
-          locName = endNode.getName();
-        }
-        belowSet.add(locName);
-      }
-      lattice.insertNewLocationBetween(above, belowSet, newLocName);
-
-      mapIntermediateLoc.put(item, newLocName);
-    }
-
-    String curLocName = mapIntermediateLoc.get(item);
-    HierarchyGraph hierarchyGraph = infer.getSimpleHierarchyGraph(desc);
-
-    if (curHierarchyNode.isSharedNode()) {
-      // if the current node is shared location, add a shared location to the lattice later
-      mapSharedNodeToTripleItem.put(curHierarchyNode, item);
-    } else {
-      Set<Descriptor> descSet = hierarchyGraph.getDescSetOfNode(curHierarchyNode);
-      for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
-        Descriptor d = (Descriptor) iterator.next();
-        locSummary.addMapHNodeNameToLocationName(d.getSymbol(), curLocName);
-      }
-      locSummary.addMapHNodeNameToLocationName(curHierarchyNode.getName(), curLocName);
-    }
-
-    System.out.println("-TripleItem normal=" + item);
-    System.out.println("-curNode=" + curHierarchyNode.getName() + " S="
-        + curHierarchyNode.isSharedNode() + " locName=" + curLocName + "  isC="
-        + curHierarchyNode.isCombinationNode());
-
-    Set<HNode> outSet = hierarchyGraph.getOutgoingNodeSet(curHierarchyNode);
-    for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
-      HNode outHierarchyNodeFromCurNode = (HNode) iterator2.next();
-
-      // Set<HNode> incomingHNodeSetToOutNode = simpleHierarchyGraph.getIncomingNodeSet(outNode);
-      System.out.println("outHierarchyNodeFromCurNode=" + outHierarchyNodeFromCurNode);
-      // System.out.println("---incomingHNodeSetToOutNode=" + incomingHNodeSetToOutNode);
-
-      if (outHierarchyNodeFromCurNode.isSkeleton()
-          || outHierarchyNodeFromCurNode.isCombinationNode()) {
-        String lowerLocName = locSummary.getLocationName(outHierarchyNodeFromCurNode.getName());
-        lattice.addRelationHigherToLower(curLocName, lowerLocName);
-      } else {
-        if (visited.containsAll(hierarchyGraph.getIncomingNodeSet(outHierarchyNodeFromCurNode))) {
-          visited.add(outHierarchyNodeFromCurNode);
-          int newidx = getCurrentHighestIndex(outHierarchyNodeFromCurNode, idx + 1);
-          recurDFVisitNormalNode(scStartNode, scEndNodeSet, outHierarchyNodeFromCurNode, newidx,
-              desc, lattice, visited, locSummary, mapIntermediateLoc);
-        } else {
-          System.out.println("NOT RECUR");
-          updateHighestIndex(outHierarchyNodeFromCurNode, idx + 1);
-        }
-      }
-
-      // if (!outNode.isSkeleton() && !outNode.isCombinationNode() && !visited.contains(outNode)) {
-      // if (visited.containsAll(simpleHierarchyGraph.getIncomingNodeSet(outNode))) {
-      // visited.add(outNode);
-      // int newidx = getCurrentHighestIndex(outNode, idx + 1);
-      // recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc,
-      // newidx, locSummary, outNode);
-      // // recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc,
-      // // idx + 1, locSummary, outNode);
-      // } else {
-      // updateHighestIndex(outNode, idx + 1);
-      // System.out.println("NOT RECUR");
-      // }
-      // } else if (!outNode.isSkeleton() && outNode.isCombinationNode() &&
-      // !visited.contains(outNode)) {
-      // if (needToExpandCombinationNode(desc, outNode)) {
-      // System.out.println("NEED TO");
-      // expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode);
-      // } else {
-      // System.out.println("NOT NEED TO");
-      // }
-      // }
-
-    }
-
-  }
-
-  private void recurDFVisitCombinationNode(HNode scCombNode, Set<HNode> scEndNodeSet,
-      HNode curHierarchyCombNode, int idx, Descriptor desc, SSJavaLattice<String> lattice,
-      Set<HNode> visited, LocationSummary locSummary, Map<TripleItem, String> mapIntermediateLoc) {
-
-    // Descriptor desc, SSJavaLattice<String> lattice,
-    // HNode combinationNodeInSCGraph, Set<HNode> endNodeSet, Set<HNode> visited,
-    // Map<TripleItem, String> mapIntermediateLoc, int idx, LocationSummary locSummary, HNode
-    // curNode) {
-
-    TripleItem item = new TripleItem(scCombNode, scEndNodeSet, idx);
-
-    if (!mapIntermediateLoc.containsKey(item)) {
-      // need to create a new intermediate location in the lattice
-      String above;
-      if (idx == 1) {
-        String newLocName = scCombNode.getName();
-        mapIntermediateLoc.put(item, newLocName);
-      } else {
-        String newLocName = "ILOC" + (LocationInference.locSeed++);
-        int prevIdx = idx - 1;
-        TripleItem prevItem = new TripleItem(scCombNode, scEndNodeSet, prevIdx);
-        above = mapIntermediateLoc.get(prevItem);
-
-        Set<String> belowSet = new HashSet<String>();
-        for (Iterator iterator = scEndNodeSet.iterator(); iterator.hasNext();) {
-          HNode endNode = (HNode) iterator.next();
-          belowSet.add(endNode.getName());
-        }
-        lattice.insertNewLocationBetween(above, belowSet, newLocName);
-        mapIntermediateLoc.put(item, newLocName);
-      }
-
-    }
-
-    HierarchyGraph hierarchyNode = infer.getSimpleHierarchyGraph(desc);
-    String locName = mapIntermediateLoc.get(item);
-    if (curHierarchyCombNode.isSharedNode()) {
-      // if the current node is shared location, add a shared location to the lattice later
-      mapSharedNodeToTripleItem.put(curHierarchyCombNode, item);
-    } else {
-      Set<Descriptor> descSet = hierarchyNode.getDescSetOfNode(curHierarchyCombNode);
-      for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
-        Descriptor d = (Descriptor) iterator.next();
-        locSummary.addMapHNodeNameToLocationName(d.getSymbol(), locName);
-      }
-      locSummary.addMapHNodeNameToLocationName(curHierarchyCombNode.getName(), locName);
-    }
-
-    System.out.println("-TripleItem=" + item);
-    System.out.println("-curNode=" + curHierarchyCombNode.getName() + " S="
-        + curHierarchyCombNode.isSharedNode() + " locName=" + locName);
-
-    Set<HNode> outSet = hierarchyNode.getOutgoingNodeSet(curHierarchyCombNode);
-    for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
-      HNode outHierarchyNode = (HNode) iterator2.next();
-
-      System.out.println("---recurDFS outNode=" + outHierarchyNode);
-      System.out.println("---outNode combinationNodeInSCGraph="
-          + getCombinationNodeInSCGraph(desc, outHierarchyNode));
-
-      if (outHierarchyNode.isCombinationNode()) {
-        HNode outCombinationNodeInSCGraph = getCombinationNodeInSCGraph(desc, outHierarchyNode);
-        if (outCombinationNodeInSCGraph.equals(scCombNode)) {
-
-          Set<HNode> combineSkeletonNodeSet =
-              hierarchyNode.getCombineSetByCombinationNode(outHierarchyNode);
-          Set<HNode> incomingHNodeSetToOutNode = hierarchyNode.getIncomingNodeSet(outHierarchyNode);
-          // extract nodes belong to the same combine node
-          Set<HNode> incomingCombinedHNodeSet = new HashSet<HNode>();
-          for (Iterator iterator = incomingHNodeSetToOutNode.iterator(); iterator.hasNext();) {
-            HNode inNode = (HNode) iterator.next();
-            if (combineSkeletonNodeSet.contains(inNode)) {
-              incomingCombinedHNodeSet.add(inNode);
-            }
-          }
-          System.out.println("incomingCombinedHNodeSet=" + incomingCombinedHNodeSet);
-          if (visited.containsAll(incomingCombinedHNodeSet)) {
-            visited.add(outHierarchyNode);
-            System.out.println("-------curIdx=" + (idx + 1));
-            int newIdx = getCurrentHighestIndex(outHierarchyNode, idx + 1);
-            System.out.println("-------newIdx=" + newIdx);
-            recurDFVisitCombinationNode(scCombNode, scEndNodeSet, outHierarchyNode, newIdx, desc,
-                lattice, visited, locSummary, mapIntermediateLoc);
-          } else {
-            updateHighestIndex(outHierarchyNode, idx + 1);
-            System.out.println("-----NOT RECUR!");
-          }
-
-        }
-      }
-
-    }
-
-  }
-
-  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);
-    Set<HNode> endNodeSet =
-        infer.getSkeletonCombinationHierarchyGraph(desc).getOutgoingNodeSet(
-            combinationNodeInSCGraph);
-
-    System.out.println("expandCombinationNode=" + cnode + "  cnode in scgraph="
-        + combinationNodeInSCGraph);
-    System.out.println("endnodeset=" + endNodeSet);
-
-    if (combinationNodeInSCGraph == null) {
-      return;
-    }
-
-    // HierarchyGraph hierarchyGraph = infer.getSimpleHierarchyGraph(desc);
-    //
-    // Set<HNode> combineSkeletonNodeSet = hierarchyGraph.getCombineSetByCombinationNode(cnode);
-    //
-    // // System.out.println("combineSkeletonNodeSet=" + combineSkeletonNodeSet);
-    //
-    // Set<HNode> combinationNodeSet =
-    // hierarchyGraph.getCombinationNodeSetByCombineNodeSet(combineSkeletonNodeSet);
-    //
-    // // System.out.println("combinationNodeSet=" + combinationNodeSet);
-    //
-    // Set<HNode> endNodeSetFromSimpleGraph =
-    // hierarchyGraph.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 (endNodeSet.size() > 0) {
-      // System.out.println("---endCombNodeSet=" + endCombNodeSet);
-      endNodeSet = removeTransitivelyReachToNode(desc, combinationNodeInSCGraph, endNodeSet);
-
-      recurDFVisitCombinationNode(combinationNodeInSCGraph, endNodeSet, cnode, 1, desc, lattice,
-          visited, locSummary, mapIntermediateLoc);
-
-    } else {
-      endNodeSet.add(LocationInference.BOTTOMHNODE);
-      // System.out.println("---endCombNodeSet is zero");
-      // System.out.println("---endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph);
-      // System.out.println("---incoming=" + simpleGraph.getIncomingNodeSet(cnode));
-      recurDFVisitCombinationNode(combinationNodeInSCGraph, endNodeSet, cnode, 1, desc, lattice,
-          visited, locSummary, mapIntermediateLoc);
-    }
-
-  }
-
-  public SSJavaLattice<String> insertIntermediateNodesToStraightLine2(Descriptor desc,
-      SSJavaLattice<String> skeletonLattice) {
-
     // perform DFS that starts from each skeleton/combination node and ends by another
     // skeleton/combination node
 
@@ -549,7 +204,7 @@ public class BuildLattice {
             if (outNode.isCombinationNode()) {
               if (visited.containsAll(simpleGraph.getIncomingNodeSet(outNode))) {
                 // if (needToExpandCombinationNode(desc, outNode)) {
-                expandCombinationNode3(desc, lattice, visited, mapIntermediateLoc, locSummary,
+                expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary,
                     outNode);
                 // }
               }
@@ -567,16 +222,18 @@ public class BuildLattice {
               // startNode = node;
               // }
 
-              Set<HNode> endNodeSetFromSimpleGraph =
-                  simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(outNode, null);
+              // TODO
+              // Set<HNode> endNodeSetFromSimpleGraph =
+              // simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(outNode, null);
+              // Set<HNode> endCombNodeSet = new HashSet<HNode>();
+              // for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator();
+              // iterator3.hasNext();) {
+              // HNode endNode = (HNode) iterator3.next();
+              // endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode));
+              // }
+
+              Set<HNode> endCombNodeSet = scGraph.getOutgoingNodeSet(startNode);
 
-              // System.out.println("endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph
-              // + "   from=" + outNode);
-              Set<HNode> endCombNodeSet = new HashSet<HNode>();
-              for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) {
-                HNode endNode = (HNode) iterator3.next();
-                endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode));
-              }
               // System.out.println("endCombNodeSet=" + endCombNodeSet);
               visited.add(outNode);
               if (endCombNodeSet.size() > 0) {
@@ -636,7 +293,8 @@ public class BuildLattice {
       HNode sharedNode = (HNode) iterator.next();
       TripleItem item = mapSharedNodeToTripleItem.get(sharedNode);
       String nonSharedLocName = mapIntermediateLoc.get(item);
-      // System.out.println("sharedNode=" + sharedNode + "    locName=" + nonSharedLocName);
+      
+      System.out.println("sharedNode=" + sharedNode + "    locName=" + nonSharedLocName);
 
       String newLocName;
       if (locSummary.getHNodeNameSetByLatticeLoationName(nonSharedLocName) != null
@@ -649,8 +307,8 @@ public class BuildLattice {
         Set<String> belowElementSet = new HashSet<String>();
         belowElementSet.addAll(lattice.get(nonSharedLocName));
 
-        // System.out.println("nonSharedLocName=" + nonSharedLocName + "   belowElementSet="
-        // + belowElementSet + "  newLocName=" + newLocName);
+        System.out.println("nonSharedLocName=" + nonSharedLocName + "   belowElementSet="
+            + belowElementSet + "  newLocName=" + newLocName);
 
         lattice.insertNewLocationBetween(nonSharedLocName, belowElementSet, newLocName);
       } else {
@@ -711,6 +369,66 @@ public class BuildLattice {
     return true;
   }
 
+  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);
+
+    System.out.println("expandCombinationNode=" + cnode + "  cnode in scgraph="
+        + combinationNodeInSCGraph);
+
+    if (combinationNodeInSCGraph == null) {
+      return;
+    }
+
+    HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc);
+    HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
+
+    Set<HNode> combineSkeletonNodeSet = simpleGraph.getCombineSetByCombinationNode(cnode);
+
+    // System.out.println("combineSkeletonNodeSet=" + combineSkeletonNodeSet);
+
+    Set<HNode> combinationNodeSet =
+        simpleGraph.getCombinationNodeSetByCombineNodeSet(combineSkeletonNodeSet);
+
+    // System.out.println("combinationNodeSet=" + combinationNodeSet);
+
+    // TODO
+    // 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));
+    // }
+
+    Set<HNode> endCombNodeSet = scGraph.getOutgoingNodeSet(combinationNodeInSCGraph);
+    visited.add(cnode);
+
+    // follows the straight line up to another skeleton/combination node
+    if (endCombNodeSet.size() > 0) {
+      // System.out.println("---endCombNodeSet=" + endCombNodeSet);
+      endCombNodeSet =
+          removeTransitivelyReachToNode(desc, combinationNodeInSCGraph, endCombNodeSet);
+
+      recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited,
+          mapIntermediateLoc, 1, locSummary, cnode);
+    } else {
+      endCombNodeSet.add(LocationInference.BOTTOMHNODE);
+      // System.out.println("---endCombNodeSet is zero");
+      // System.out.println("---endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph);
+      // System.out.println("---incoming=" + simpleGraph.getIncomingNodeSet(cnode));
+      recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited,
+          mapIntermediateLoc, 1, locSummary, cnode);
+
+    }
+
+  }
+
   private Set<HNode> removeTransitivelyReachToNode(Descriptor desc, HNode startNode,
       Set<HNode> endNodeSet) {
 
@@ -801,62 +519,6 @@ public class BuildLattice {
     return connected.iterator().next();
   }
 
-  private void expandCombinationNode3(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);
-
-    System.out.println("expandCombinationNode=" + cnode + "  cnode in scgraph="
-        + combinationNodeInSCGraph);
-
-    if (combinationNodeInSCGraph == null) {
-      return;
-    }
-
-    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) {
-      // System.out.println("---endCombNodeSet=" + endCombNodeSet);
-      endCombNodeSet =
-          removeTransitivelyReachToNode(desc, combinationNodeInSCGraph, endCombNodeSet);
-
-      recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited,
-          mapIntermediateLoc, 1, locSummary, cnode);
-    } else {
-      endCombNodeSet.add(LocationInference.BOTTOMHNODE);
-      // System.out.println("---endCombNodeSet is zero");
-      // System.out.println("---endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph);
-      // System.out.println("---incoming=" + simpleGraph.getIncomingNodeSet(cnode));
-      recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited,
-          mapIntermediateLoc, 1, locSummary, cnode);
-
-    }
-
-  }
-
   private void recurDirectlyReachableNodeFromStartNodeReachToEndNode(HierarchyGraph scGraph,
       HNode startNode, HNode curNode, Set<HNode> connected) {
 
@@ -877,7 +539,6 @@ public class BuildLattice {
       int idx, LocationSummary locSummary, HNode curNode) {
 
     TripleItem item = new TripleItem(startNode, endNodeSet, idx);
-    // System.out.println("item=" + item);
     if (!mapIntermediateLoc.containsKey(item)) {
       // need to create a new intermediate location in the lattice
       String newLocName = "ILOC" + (LocationInference.locSeed++);
@@ -934,21 +595,24 @@ public class BuildLattice {
       System.out.println("---incomingHNodeSetToOutNode=" + incomingHNodeSetToOutNode);
 
       if (!outNode.isSkeleton() && !outNode.isCombinationNode() && !visited.contains(outNode)) {
+        Pair<HNode, HNode> pair = new Pair(startNode, outNode);
         if (visited.containsAll(simpleHierarchyGraph.getIncomingNodeSet(outNode))) {
           visited.add(outNode);
-          int newidx = getCurrentHighestIndex(outNode, idx + 1);
+          int newidx = getCurrentHighestIndex(pair, idx + 1);
+          // int newidx = getCurrentHighestIndex(outNode, idx + 1);
           recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc,
               newidx, locSummary, outNode);
           // recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc,
           // idx + 1, locSummary, outNode);
         } else {
-          updateHighestIndex(outNode, idx + 1);
+          updateHighestIndex(pair, idx + 1);
+          // updateHighestIndex(outNode, idx + 1);
           System.out.println("NOT RECUR");
         }
       } else if (!outNode.isSkeleton() && outNode.isCombinationNode() && !visited.contains(outNode)) {
         if (needToExpandCombinationNode(desc, outNode)) {
           System.out.println("NEED TO");
-          expandCombinationNode3(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode);
+          expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode);
         } else {
           System.out.println("NOT NEED TO");
         }
@@ -1040,24 +704,27 @@ public class BuildLattice {
 
           // check whether the next combination node is different from the current node
           if (combinationNodeInSCGraph.equals(getCombinationNodeInSCGraph(desc, outNode))) {
+            Pair<HNode, HNode> pair = new Pair(combinationNodeInSCGraph, outNode);
             if (visited.containsAll(incomingCombinedHNodeSet)) {
               visited.add(outNode);
               System.out.println("-------curIdx=" + (idx + 1));
-              int newIdx = getCurrentHighestIndex(outNode, idx + 1);
+
+              int newIdx = getCurrentHighestIndex(pair, idx + 1);
+              // int newIdx = getCurrentHighestIndex(outNode, idx + 1);
               System.out.println("-------newIdx=" + newIdx);
               recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited,
                   mapIntermediateLoc, newIdx, locSummary, outNode);
               // recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited,
               // mapIntermediateLoc, idx + 1, locSummary, outNode);
             } else {
-              updateHighestIndex(outNode, idx + 1);
+              updateHighestIndex(pair, idx + 1);
+              // updateHighestIndex(outNode, idx + 1);
               System.out.println("-----NOT RECUR!");
             }
           } else {
             if (needToExpandCombinationNode(desc, outNode)) {
               System.out.println("NEED TO");
-              expandCombinationNode3(desc, lattice, visited, mapIntermediateLoc, locSummary,
-                  outNode);
+              expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode);
             } else {
               System.out.println("NOT NEED TO");
             }
@@ -1071,6 +738,15 @@ public class BuildLattice {
 
   }
 
+  private int getCurrentHighestIndex(Pair<HNode, HNode> pair, int curIdx) {
+    int recordedIdx = getCurrentHighestIndex(pair);
+    if (recordedIdx > curIdx) {
+      return recordedIdx;
+    } else {
+      return curIdx;
+    }
+  }
+
   private int getCurrentHighestIndex(HNode node, int curIdx) {
     int recordedIdx = getCurrentHighestIndex(node);
     if (recordedIdx > curIdx) {
@@ -1080,6 +756,19 @@ public class BuildLattice {
     }
   }
 
+  private int getCurrentHighestIndex(Pair<HNode, HNode> pair) {
+    if (!mapItemToHighestIndex.containsKey(pair)) {
+      mapItemToHighestIndex.put(pair, new Integer(-1));
+    }
+    return mapItemToHighestIndex.get(pair).intValue();
+  }
+
+  private void updateHighestIndex(Pair<HNode, HNode> pair, int idx) {
+    if (idx > getCurrentHighestIndex(pair)) {
+      mapItemToHighestIndex.put(pair, new Integer(idx));
+    }
+  }
+
   private int getCurrentHighestIndex(HNode node) {
     if (!mapHNodeToHighestIndex.containsKey(node)) {
       mapHNodeToHighestIndex.put(node, new Integer(-1));
index ce62cf5..f9bb5e9 100644 (file)
@@ -783,6 +783,9 @@ public class HierarchyGraph {
       // System.out.println("--combineSet=" + combineSet);
       HNode combinationNode = getCombinationNode(combineSet);
       System.out.println("--combinationNode=" + combinationNode + "   combineSet=" + combineSet);
+
+      System.out.println("--hierarchynodes="
+          + simpleHierarchyGraph.getCombinationNodeSetByCombineNodeSet(combineSet));
       // add an edge from a skeleton node to a combination node
       for (Iterator iterator2 = combineSet.iterator(); iterator2.hasNext();) {
         HNode inSkeletonNode = (HNode) iterator2.next();
@@ -972,7 +975,11 @@ public class HierarchyGraph {
       HNode node = (HNode) iterator.next();
       if (!node.isSkeleton()) {
         Set<HNode> reachToSet = getSkeleteNodeSetReachTo(node);
-        System.out.println("$node=" + node + "   reachToNodeSet=" + reachToSet);
+        // Set<HNode> tempSet = removeTransitivelyReachToSet(reachToSet);
+        // reachToSet = removeTransitivelyReachToSet(reachToSet);
+        Set<HNode> tempSet = reachToSet;
+        System.out.println("$node=" + node + "   reachToNodeSet=" + reachToSet + " tempSet="
+            + tempSet);
         if (reachToSet.size() > 1) {
           // if (countSkeletonNodes(reachToSet) > 1) {
           System.out.println("-node=" + node + "  reachToSet=" + reachToSet);
@@ -995,6 +1002,38 @@ public class HierarchyGraph {
 
   }
 
+  private Set<HNode> removeTransitivelyReachToSet(Set<HNode> reachToSet) {
+
+    Set<HNode> toberemoved = new HashSet<HNode>();
+    Set<HNode> visited = new HashSet<HNode>();
+    for (Iterator iterator = reachToSet.iterator(); iterator.hasNext();) {
+      HNode node = (HNode) iterator.next();
+      visited.add(node);
+      recurIsReachingTo(node, reachToSet, toberemoved, visited);
+    }
+
+    Set<HNode> rSet = new HashSet<HNode>();
+    rSet.addAll(reachToSet);
+    rSet.removeAll(toberemoved);
+    return rSet;
+  }
+
+  private void recurIsReachingTo(HNode curNode, Set<HNode> reachToSet, Set<HNode> toberemoved,
+      Set<HNode> visited) {
+    Set<HNode> inNodeSet = getIncomingNodeSet(curNode);
+
+    for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
+      HNode inNode = (HNode) iterator.next();
+      if (reachToSet.contains(inNode)) {
+        toberemoved.add(inNode);
+      } else if (!visited.contains(inNode)) {
+        visited.add(inNode);
+        recurIsReachingTo(inNode, reachToSet, toberemoved, visited);
+      }
+    }
+
+  }
+
   public Map<HNode, Set<HNode>> getMapCombinationNodeToCombineNodeSet() {
     return mapCombinationNodeToCombineNodeSet;
   }
index 05500e2..fe7d2b9 100644 (file)
@@ -452,7 +452,7 @@ public class LocationInference {
       String locName;
       if (!enclosingDesc.equals(GLOBALDESC)) {
         LocationSummary locSummary = getLocationSummary(enclosingDesc);
-//        HierarchyGraph scGraph = getSkeletonCombinationHierarchyGraph(enclosingDesc);
+        // HierarchyGraph scGraph = getSkeletonCombinationHierarchyGraph(enclosingDesc);
         HierarchyGraph scGraph = getSimpleHierarchyGraph(enclosingDesc);
         if (scGraph != null) {
           HNode curNode = scGraph.getCurrentHNode(nodeIdentifier);
@@ -2150,15 +2150,17 @@ public class LocationInference {
     Set<Descriptor> keySet = mapDescriptorToSkeletonHierarchyGraph.keySet();
     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
       Descriptor desc = (Descriptor) iterator.next();
-      System.out.println("\nSSJAVA: Insering Combination Nodes:" + desc);
+      System.out.println("\nSSJAVA: Inserting Combination Nodes:" + desc);
       HierarchyGraph skeletonGraph = getSkeletonHierarchyGraph(desc);
       HierarchyGraph skeletonGraphWithCombinationNode = skeletonGraph.clone();
       skeletonGraphWithCombinationNode.setName(desc + "_SC");
 
       HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc);
-      System.out.println("Identifying Combination Nodes:");
       skeletonGraphWithCombinationNode.insertCombinationNodesToGraph(simpleHierarchyGraph);
-      skeletonGraphWithCombinationNode.simplifySkeletonCombinationHierarchyGraph();
+      // skeletonGraphWithCombinationNode.insertCombinationNodesToGraph(simpleHierarchyGraph,
+      // skeletonGraph);
+      // skeletonGraphWithCombinationNode.simplifySkeletonCombinationHierarchyGraph();
+      skeletonGraphWithCombinationNode.removeRedundantEdges();
       mapDescriptorToCombineSkeletonHierarchyGraph.put(desc, skeletonGraphWithCombinationNode);
     }
   }
@@ -3302,6 +3304,8 @@ public class LocationInference {
     // int size = paramLocTupleHavingInFlowSet.size();
     int size = countFirstDescriptorSetSize(paramLocTupleHavingInFlowSet);
 
+    System.out.println("numParam=" + numParam + "     size=" + size);
+
     // if (!md.isStatic()) {
     //
     // // if the method is not static && there is a parameter composite location &&
@@ -4660,7 +4664,7 @@ public class LocationInference {
   private void analyzeFlowIfStatementNode(MethodDescriptor md, SymbolTable nametable,
       IfStatementNode isn, NodeTupleSet implicitFlowTupleSet) {
 
-    System.out.println("analyzeFlowIfStatementNode=" + isn.printNode(0));
+    // System.out.println("analyzeFlowIfStatementNode=" + isn.printNode(0));
 
     NodeTupleSet condTupleNode = new NodeTupleSet();
     analyzeFlowExpressionNode(md, nametable, isn.getCondition(), condTupleNode, null,