changes.
authoryeom <yeom>
Sat, 22 Sep 2012 00:49:41 +0000 (00:49 +0000)
committeryeom <yeom>
Sat, 22 Sep 2012 00:49:41 +0000 (00:49 +0000)
Robust/src/Analysis/SSJava/BasisSet.java [new file with mode: 0644]
Robust/src/Analysis/SSJava/BuildLattice.java [new file with mode: 0644]
Robust/src/Analysis/SSJava/FElement.java [new file with mode: 0644]
Robust/src/Analysis/SSJava/Family.java [new file with mode: 0644]
Robust/src/Analysis/SSJava/HNode.java
Robust/src/Analysis/SSJava/HierarchyGraph.java
Robust/src/Analysis/SSJava/LocationInference.java
Robust/src/Analysis/SSJava/SSJavaAnalysis.java
Robust/src/Analysis/SSJava/SSJavaLattice.java
Robust/src/Util/Lattice.java

diff --git a/Robust/src/Analysis/SSJava/BasisSet.java b/Robust/src/Analysis/SSJava/BasisSet.java
new file mode 100644 (file)
index 0000000..a379e99
--- /dev/null
@@ -0,0 +1,53 @@
+package Analysis.SSJava;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.Set;
+
+public class BasisSet {
+
+  // an element of the basis set is represented by a pair (HNode,basis)
+  Map<Set<Integer>, HNode> map;
+
+  public BasisSet() {
+    map = new HashMap<Set<Integer>, HNode>();
+  }
+
+  public void addElement(Set<Integer> basis, HNode node) {
+    map.put(basis, node);
+  }
+
+  public Iterator<Set<Integer>> basisIterator() {
+    return map.keySet().iterator();
+  }
+
+  public HNode getHNode(Set<Integer> B) {
+    return map.get(B);
+  }
+
+  public Set<HNode> getHNodeSet() {
+    Set<HNode> set = new HashSet<HNode>();
+    set.addAll(map.values());
+    return set;
+  }
+
+  public Set<Set<Integer>> getBasisSetByHNodeSet(Set<HNode> nodeSet) {
+
+    Set<Set<Integer>> rtrSet = new HashSet<Set<Integer>>();
+
+    Set<Set<Integer>> keySet = map.keySet();
+    for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
+      Set<Integer> basisKey = (Set<Integer>) iterator.next();
+      HNode node = map.get(basisKey);
+      if (nodeSet.contains(node)) {
+        rtrSet.add(basisKey);
+      }
+    }
+
+    return rtrSet;
+
+  }
+
+}
diff --git a/Robust/src/Analysis/SSJava/BuildLattice.java b/Robust/src/Analysis/SSJava/BuildLattice.java
new file mode 100644 (file)
index 0000000..eca8dfa
--- /dev/null
@@ -0,0 +1,447 @@
+package Analysis.SSJava;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.Set;
+
+import IR.Descriptor;
+import Util.Pair;
+
+public class BuildLattice {
+
+  public static int seed = 0;
+  private LocationInference infer;
+
+  public BuildLattice(LocationInference infer) {
+    this.infer = infer;
+  }
+
+  public SSJavaLattice<String> buildLattice(HierarchyGraph inputGraph) {
+
+    BasisSet basisSet = inputGraph.computeBasisSet();
+    debug_print(inputGraph);
+
+    Family family = generateFamily(basisSet);
+    Map<Set<Integer>, Set<Set<Integer>>> mapImSucc = coveringGraph(basisSet, family);
+
+    SSJavaLattice<String> lattice = buildLattice(basisSet, inputGraph, mapImSucc);
+    return lattice;
+
+  }
+
+  private SSJavaLattice<String> buildLattice(BasisSet basisSet, HierarchyGraph inputGraph,
+      Map<Set<Integer>, Set<Set<Integer>>> mapImSucc) {
+
+    SSJavaLattice<String> lattice =
+        new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM);
+
+    Map<Set<Integer>, String> mapFToLocName = new HashMap<Set<Integer>, String>();
+
+    Set<Set<Integer>> keySet = mapImSucc.keySet();
+    for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
+      Set<Integer> higher = (Set<Integer>) iterator.next();
+
+      String higherName = generateElementName(basisSet, inputGraph, mapFToLocName, higher);
+
+      Set<Set<Integer>> lowerSet = mapImSucc.get(higher);
+      for (Iterator iterator2 = lowerSet.iterator(); iterator2.hasNext();) {
+        Set<Integer> lower = (Set<Integer>) iterator2.next();
+
+        String lowerName = generateElementName(basisSet, inputGraph, mapFToLocName, lower);
+
+        if (higher.size() == 0) {
+          // empty case
+          lattice.put(lowerName);
+        } else {
+          lattice.addRelationHigherToLower(higherName, lowerName);
+        }
+
+      }
+
+    }
+
+    return lattice;
+  }
+
+  public HNode getCombinationNodeInSCGraph(Descriptor desc, HNode simpleGraphNode) {
+
+    Set<HNode> combineSkeletonNodeSet =
+        infer.getSimpleHierarchyGraph(desc).getCombineSetByCombinationNode(simpleGraphNode);
+    HNode combinationNodeInSCGraph =
+        infer.getSkeletonCombinationHierarchyGraph(desc).getCombinationNode(combineSkeletonNodeSet);
+    return combinationNodeInSCGraph;
+  }
+
+  public SSJavaLattice<String> insertIntermediateNodesToStraightLine(Descriptor desc,
+      SSJavaLattice<String> skeletonLattice) {
+
+    // perform DFS that starts from each skeleton/combination node and ends by another
+    // skeleton/combination node
+
+    HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc);
+    HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
+
+    SSJavaLattice<String> lattice = skeletonLattice.clone();
+
+    Map<TripleItem, String> mapIntermediateLocation = new HashMap<TripleItem, String>();
+
+    Set<HNode> visited = new HashSet<HNode>();
+
+    Set<HNode> nodeSet = simpleGraph.getNodeSet();
+
+    // expand a combination node
+    Map<TripleItem, String> mapIntermediateLoc = new HashMap<TripleItem, String>();
+    for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
+      HNode node = (HNode) iterator.next();
+      if (node.isSkeleton() && (!visited.contains(node))) {
+        visited.add(node);
+
+        Set<HNode> outSet = simpleGraph.getOutgoingNodeSet(node);
+        for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
+          HNode outNode = (HNode) iterator2.next();
+
+          if (!outNode.isSkeleton()) {
+            if (outNode.isCombinationNode()) {
+              // here we need to expand the corresponding combination location in the lattice
+              HNode combinationNodeInSCGraph = getCombinationNodeInSCGraph(desc, outNode);
+
+              Set<HNode> combineSkeletonNodeSet =
+                  simpleGraph.getCombineSetByCombinationNode(outNode);
+              Set<HNode> combinationNodeSet =
+                  simpleGraph.getCombinationNodeSetByCombineNodeSet(combineSkeletonNodeSet);
+              Set<HNode> endNodeSetFromSimpleGraph =
+                  simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(outNode,
+                      combinationNodeSet);
+              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) {
+                recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited,
+                    mapIntermediateLoc, 1, outNode);
+              }
+
+            } else {
+              // we have a node that is neither combination or skeleton node
+              HNode startNode = node;
+              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));
+              }
+
+              visited.add(outNode);
+              if (endCombNodeSet.size() > 0) {
+                // follows the straight line up to another skeleton/combination node
+                recurDFSNormalNode(desc, lattice, startNode, endCombNodeSet, visited,
+                    mapIntermediateLoc, 1, outNode);
+
+              }
+
+            }
+
+          }
+
+        }
+      }
+    }
+
+    return lattice;
+
+  }
+
+  private void recurDFSNormalNode(Descriptor desc, SSJavaLattice<String> lattice, HNode startNode,
+      Set<HNode> endNodeSet, Set<HNode> visited, Map<TripleItem, String> mapIntermediateLoc,
+      int idx, HNode curNode) {
+
+    TripleItem item = new TripleItem(startNode, endNodeSet, idx);
+
+    if (!mapIntermediateLoc.containsKey(item)) {
+      // need to create a new intermediate location in the lattice
+      String newLocName = "ILOC" + (seed++);
+      String above;
+      if (idx == 1) {
+        above = startNode.getName();
+      } else {
+        int prevIdx = idx - 1;
+        TripleItem prevItem = new TripleItem(startNode, endNodeSet, prevIdx);
+        above = mapIntermediateLoc.get(prevItem);
+      }
+
+      Set<String> belowSet = new HashSet<String>();
+      for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
+        HNode endNode = (HNode) iterator.next();
+        belowSet.add(endNode.getName());
+      }
+
+      lattice.insertNewLocationBetween(above, belowSet, newLocName);
+
+      mapIntermediateLoc.put(item, newLocName);
+    }
+
+    String locName = mapIntermediateLoc.get(item);
+
+    HierarchyGraph graph = infer.getSimpleHierarchyGraph(desc);
+    Set<HNode> outSet = graph.getOutgoingNodeSet(curNode);
+    for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
+      HNode outNode = (HNode) iterator2.next();
+      if (!outNode.isSkeleton() && !outNode.isCombinationNode() && !visited.contains(outNode)) {
+        visited.add(outNode);
+        recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc,
+            idx + 1, outNode);
+      }
+    }
+
+  }
+
+  private void recurDFS(Descriptor desc, SSJavaLattice<String> lattice,
+      HNode combinationNodeInSCGraph, Set<HNode> endNodeSet, Set<HNode> visited,
+      Map<TripleItem, String> mapIntermediateLoc, int idx, HNode curNode) {
+
+    TripleItem item = new TripleItem(combinationNodeInSCGraph, endNodeSet, idx);
+
+    if (!mapIntermediateLoc.containsKey(item)) {
+      // need to create a new intermediate location in the lattice
+      String newLocName = "ILOC" + (seed++);
+      String above;
+      if (idx == 1) {
+        above = combinationNodeInSCGraph.getName();
+      } else {
+        int prevIdx = idx - 1;
+        TripleItem prevItem = new TripleItem(combinationNodeInSCGraph, endNodeSet, prevIdx);
+        above = mapIntermediateLoc.get(prevItem);
+      }
+
+      Set<String> belowSet = new HashSet<String>();
+      for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
+        HNode endNode = (HNode) iterator.next();
+        belowSet.add(endNode.getName());
+      }
+      lattice.insertNewLocationBetween(above, belowSet, newLocName);
+
+      mapIntermediateLoc.put(item, newLocName);
+
+      String locName = mapIntermediateLoc.get(item);
+
+    }
+
+    HierarchyGraph graph = infer.getSimpleHierarchyGraph(desc);
+    Set<HNode> outSet = graph.getOutgoingNodeSet(curNode);
+    for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
+      HNode outNode = (HNode) iterator2.next();
+      if (!outNode.isSkeleton() && !visited.contains(outNode)) {
+        if (combinationNodeInSCGraph.equals(getCombinationNodeInSCGraph(desc, outNode))) {
+          visited.add(outNode);
+          recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited,
+              mapIntermediateLoc, idx + 1, outNode);
+        }
+      }
+    }
+
+  }
+
+  private String generateElementName(BasisSet basisSet, HierarchyGraph inputGraph,
+      Map<Set<Integer>, String> mapF2LocName, Set<Integer> F) {
+
+    if (mapF2LocName.containsKey(F)) {
+      return mapF2LocName.get(F);
+    }
+
+    HNode node = basisSet.getHNode(F);
+    if (node != null) {
+      mapF2LocName.put(F, node.getName());
+      return node.getName();
+    } else {
+      if (inputGraph.BASISTOPELEMENT.equals(F)) {
+        return SSJavaAnalysis.BOTTOM;
+      } else {
+        String str = "LOC" + (seed++);
+        mapF2LocName.put(F, str);
+        return str;
+      }
+    }
+  }
+
+  private void resetCount(Map<Set<Integer>, Integer> mapFtoCount, Family family) {
+    for (Iterator<Set<Integer>> iter = family.FIterator(); iter.hasNext();) {
+      Set<Integer> F = iter.next();
+      mapFtoCount.put(F, 0);
+    }
+  }
+
+  private Map<Set<Integer>, Set<Set<Integer>>> coveringGraph(BasisSet basisSet, Family family) {
+
+    Map<Set<Integer>, Integer> mapFtoCount = new HashMap<Set<Integer>, Integer>();
+    Map<Set<Integer>, Set<Set<Integer>>> mapImSucc = new HashMap<Set<Integer>, Set<Set<Integer>>>();
+
+    // initialize COUNT(F) to 0 for all elements of the family
+    resetCount(mapFtoCount, family);
+
+    for (Iterator<Set<Integer>> iter = family.FIterator(); iter.hasNext();) {
+      Set<Integer> F = iter.next();
+      Set<HNode> gammaF = family.getGamma(F);
+
+      Set<HNode> curHNodeSet = basisSet.getHNodeSet();
+      curHNodeSet.removeAll(gammaF);
+      Set<Set<Integer>> Bset = basisSet.getBasisSetByHNodeSet(curHNodeSet);
+
+      for (Iterator iterator = Bset.iterator(); iterator.hasNext();) {
+        Set<Integer> B = (Set<Integer>) iterator.next();
+
+        Set<Integer> Fprime = new HashSet<Integer>();
+        Fprime.addAll(F);
+        Fprime.addAll(B);
+
+        // COUNT(F')++;
+        mapFtoCount.put(Fprime, mapFtoCount.get(Fprime) + 1);
+
+        // if |gamma(F')|==COUNT(F') + |gamma(F)|
+        int numGammaFprime = family.getGamma(Fprime).size();
+        int countFprime = mapFtoCount.get(Fprime);
+        int numGammaF = family.getGamma(F).size();
+        if (numGammaFprime == (countFprime + numGammaF)) {
+          // ImSucc(F)=IMSucc(F) union F'
+          addImSucc(mapImSucc, F, Fprime);
+        }
+
+      }
+      resetCount(mapFtoCount, family);
+    }
+
+    System.out.println("mapImSucc=" + mapImSucc);
+
+    return mapImSucc;
+  }
+
+  private Set<Set<Integer>> getImSucc(Map<Set<Integer>, Set<Set<Integer>>> mapImSucc, Set<Integer> F) {
+    if (!mapImSucc.containsKey(F)) {
+      mapImSucc.put(F, new HashSet<Set<Integer>>());
+    }
+    return mapImSucc.get(F);
+  }
+
+  private void addImSucc(Map<Set<Integer>, Set<Set<Integer>>> mapImSucc, Set<Integer> F,
+      Set<Integer> Fprime) {
+
+    if (!mapImSucc.containsKey(F)) {
+      mapImSucc.put(F, new HashSet<Set<Integer>>());
+    }
+
+    mapImSucc.get(F).add(Fprime);
+
+  }
+
+  private Family generateFamily(BasisSet basisSet) {
+
+    Family family = new Family();
+
+    for (Iterator<Set<Integer>> iterator = basisSet.basisIterator(); iterator.hasNext();) {
+      Set<Integer> B = iterator.next();
+
+      Set<Pair<Set<Integer>, Set<HNode>>> tobeadded = new HashSet<Pair<Set<Integer>, Set<HNode>>>();
+
+      for (Iterator<Set<Integer>> iterator2 = family.FIterator(); iterator2.hasNext();) {
+        Set<Integer> F = iterator2.next();
+
+        Set<Integer> Fprime = new HashSet<Integer>();
+        Fprime.addAll(F);
+        Fprime.addAll(B);
+
+        Set<HNode> gammaFPrimeSet = new HashSet<HNode>();
+        gammaFPrimeSet.addAll(family.getGamma(F));
+        gammaFPrimeSet.add(basisSet.getHNode(B));
+
+        if (!family.containsF(Fprime)) {
+          Pair<Set<Integer>, Set<HNode>> pair =
+              new Pair<Set<Integer>, Set<HNode>>(Fprime, gammaFPrimeSet);
+          tobeadded.add(pair);
+        } else {
+          family.updateGammaF(Fprime, gammaFPrimeSet);
+        }
+      }
+
+      for (Iterator<Pair<Set<Integer>, Set<HNode>>> iterator2 = tobeadded.iterator(); iterator2
+          .hasNext();) {
+        Pair<Set<Integer>, Set<HNode>> pair = iterator2.next();
+        family.addFElement(pair.getFirst());
+        family.updateGammaF(pair.getFirst(), pair.getSecond());
+      }
+
+    }
+    return family;
+  }
+
+  private void debug_print(HierarchyGraph inputGraph) {
+    System.out.println("\nBuild Lattice:" + inputGraph.getName());
+    System.out.println("Node2Index:\n" + inputGraph.getMapHNodeToUniqueIndex());
+    System.out.println("Node2Basis:\n" + inputGraph.getMapHNodeToBasis());
+  }
+
+}
+
+class Identifier {
+  public HNode node;
+  public int idx;
+
+  public Identifier(HNode n, int i) {
+    node = n;
+    idx = i;
+  }
+
+  public int hashCode() {
+    return node.hashCode() + idx;
+  }
+
+  public boolean equals(Object obj) {
+
+    if (obj instanceof Identifier) {
+      Identifier in = (Identifier) obj;
+      if (node.equals(in.node) && idx == in.idx) {
+        return true;
+      }
+    }
+
+    return false;
+  }
+
+}
+
+class TripleItem {
+  public HNode higherNode;
+  public Set<HNode> lowerNodeSet;
+  public int idx;
+
+  public TripleItem(HNode h, Set<HNode> l, int i) {
+    higherNode = h;
+    lowerNodeSet = l;
+    idx = i;
+  }
+
+  public int hashCode() {
+    return higherNode.hashCode() + lowerNodeSet.hashCode() + idx;
+  }
+
+  public boolean equals(Object obj) {
+
+    if (obj instanceof TripleItem) {
+      TripleItem in = (TripleItem) obj;
+      if (higherNode.equals(in.higherNode) && lowerNodeSet.equals(in.lowerNodeSet) && idx == in.idx) {
+        return true;
+      }
+    }
+
+    return false;
+  }
+
+  public String toString() {
+    return higherNode + "-" + idx + "->" + lowerNodeSet;
+  }
+}
diff --git a/Robust/src/Analysis/SSJava/FElement.java b/Robust/src/Analysis/SSJava/FElement.java
new file mode 100644 (file)
index 0000000..49480cc
--- /dev/null
@@ -0,0 +1,15 @@
+package Analysis.SSJava;
+
+import java.util.HashSet;
+import java.util.Set;
+
+public class FElement {
+
+  public static Set<Integer> EMPTY = new HashSet<Integer>();
+  Set<Integer> set;
+
+  public FElement() {
+    set = new HashSet<Integer>();
+  }
+
+}
diff --git a/Robust/src/Analysis/SSJava/Family.java b/Robust/src/Analysis/SSJava/Family.java
new file mode 100644 (file)
index 0000000..07ffe07
--- /dev/null
@@ -0,0 +1,57 @@
+package Analysis.SSJava;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.Set;
+
+public class Family {
+
+  // an element of the family is represented by a pair (basis,set of corresponding nodes)
+  Map<Set<Integer>, Set<HNode>> mapFtoGammaF;
+
+  Set<Set<Integer>> Fset;
+
+  public static Set<Integer> EMPTY = new HashSet<Integer>();
+
+  public Family() {
+    Fset = new HashSet<Set<Integer>>();
+    Fset.add(EMPTY);
+    mapFtoGammaF = new HashMap<Set<Integer>, Set<HNode>>();
+  }
+
+  public void addFElement(Set<Integer> F) {
+    Fset.add(F);
+  }
+
+  public Set<HNode> getGamma(Set<Integer> F) {
+    if (!mapFtoGammaF.containsKey(F)) {
+      mapFtoGammaF.put(F, new HashSet<HNode>());
+    }
+    return mapFtoGammaF.get(F);
+  }
+
+  public void updateGammaF(Set<Integer> F, Set<HNode> gamma) {
+    getGamma(F).addAll(gamma);
+  }
+
+  public boolean containsF(Set<Integer> F) {
+    return Fset.contains(F);
+  }
+
+  public int size() {
+    return Fset.size();
+  }
+
+  public Iterator<Set<Integer>> FIterator() {
+    return Fset.iterator();
+  }
+
+  public String toString() {
+
+    return mapFtoGammaF.toString();
+
+  }
+
+}
index 47d2c72..62bae95 100644 (file)
@@ -67,11 +67,26 @@ public class HNode {
   }
 
   public String toString() {
-    String isShared = "";
+
+    String properties = "";
+
     if (isSharedNode()) {
-      isShared = "*";
+      properties += "*";
     }
-    return "[Node::" + name + isShared + "]";
+
+    if (isCombinationNode()) {
+      properties += "C";
+    }
+
+    if (isSkeleton()) {
+      properties += "S";
+    }
+
+    if (properties.length() > 0) {
+      properties = "(" + properties + ")";
+    }
+
+    return "[" + name + properties + "]";
   }
 
   public Descriptor getDescriptor() {
index 02625d9..52eb874 100644 (file)
@@ -25,11 +25,17 @@ public class HierarchyGraph {
   Map<HNode, Set<HNode>> mapCombinationNodeToCombineNodeSet;
   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;
+  Set<Integer> BASISTOPELEMENT;
+
   public HierarchyGraph() {
     mapHNodeToIncomingSet = new HashMap<HNode, Set<HNode>>();
     mapHNodeToOutgoingSet = new HashMap<HNode, Set<HNode>>();
@@ -40,6 +46,12 @@ public class HierarchyGraph {
     mapCombineNodeSetToOutgoingNodeSet = new HashMap<Set<HNode>, Set<HNode>>();
     mapCombineNodeSetToCombinationNode = new HashMap<Set<HNode>, HNode>();
     nodeSet = new HashSet<HNode>();
+
+    mapHNodeToUniqueIndex = new HashMap<HNode, Integer>();
+    mapHNodeToBasis = new HashMap<HNode, Set<Integer>>();
+
+    mapHNodeToLocationName = new HashMap<HNode, String>();
+
   }
 
   public Descriptor getDesc() {
@@ -50,6 +62,14 @@ 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;
   }
@@ -96,14 +116,19 @@ public class HierarchyGraph {
 
     Set<HNode> possibleCycleSet = getPossibleCycleNodes(srcHNode, dstHNode);
 
-    System.out.println("src=" + srcHNode + " dstHNode=" + dstHNode + " possibleCycleSet="
-        + possibleCycleSet);
-
     if (possibleCycleSet.size() > 0) {
+
+      if (possibleCycleSet.size() == 1) {
+        if (dstHNode.isSharedNode()) {
+          // it has already been assigned shared node.
+          return;
+        }
+      }
+
       HNode newMergeNode = mergeNodes(possibleCycleSet, false);
       newMergeNode.setSharedNode(true);
-      System.out.println("### CYCLIC VALUE FLOW: " + srcHNode + " -> " + dstHNode);
       System.out.println("### INTRODUCE A NEW MERGE NODE: " + newMergeNode);
+      System.out.println("### CYCLIC VALUE FLOW: " + srcHNode + " -> " + dstHNode);
     } else {
       getIncomingNodeSet(dstHNode).add(srcHNode);
       getOutgoingNodeSet(srcHNode).add(dstHNode);
@@ -185,7 +210,7 @@ public class HierarchyGraph {
     return connected;
   }
 
-  private void removeRedundantEdges() {
+  public void removeRedundantEdges() {
 
     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
       HNode src = (HNode) iterator.next();
@@ -226,7 +251,7 @@ public class HierarchyGraph {
     combineRedundantNodes(true);
   }
 
-  private void combineRedundantNodes(boolean onlyCombinationNodes) {
+  public void combineRedundantNodes(boolean onlyCombinationNodes) {
     // Combine field/parameter nodes who have the same set of incoming/outgoing edges.
     boolean isUpdated = false;
     do {
@@ -241,7 +266,7 @@ public class HierarchyGraph {
     return mapHNodeToIncomingSet.get(node);
   }
 
-  private Set<HNode> getOutgoingNodeSet(HNode node) {
+  public Set<HNode> getOutgoingNodeSet(HNode node) {
     if (!mapHNodeToOutgoingSet.containsKey(node)) {
       mapHNodeToOutgoingSet.put(node, new HashSet<HNode>());
     }
@@ -328,6 +353,8 @@ public class HierarchyGraph {
         break;
       }
     }
+    System.out.println("--Set merging node=" + newMergeNode + " as a skeleton=" + set
+        + " hasSkeleton=" + hasSkeleton);
     newMergeNode.setSkeleton(hasSkeleton);
 
     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
@@ -357,7 +384,7 @@ public class HierarchyGraph {
       }
     }
 
-    System.out.println("#MERGING NODE=" + set + " new node=" + newMergeNode);
+    System.out.println("###MERGING NODE=" + set + " new node=" + newMergeNode);
     return newMergeNode;
   }
 
@@ -401,6 +428,69 @@ public class HierarchyGraph {
 
   }
 
+  public Set<HNode> getDirectlyReachableSkeletonCombinationNodeFrom(HNode node,
+      Set<HNode> combinationNodeSet) {
+    Set<HNode> reachable = new HashSet<HNode>();
+    Set<HNode> visited = new HashSet<HNode>();
+    visited.add(node);
+    recurDirectlyReachableSkeletonCombinationNodeFrom(node, visited, reachable, combinationNodeSet);
+    return reachable;
+  }
+
+  public void recurDirectlyReachableSkeletonCombinationNodeFrom(HNode node, Set<HNode> visited,
+      Set<HNode> reachable, Set<HNode> combinationNodeSet) {
+
+    Set<HNode> outSet = getOutgoingNodeSet(node);
+    for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
+      HNode out = (HNode) iterator.next();
+
+      if (!visited.contains(out)) {
+        visited.add(out);
+        if (out.isSkeleton()) {
+          reachable.add(out);
+        } else if (out.isCombinationNode()) {
+          if (combinationNodeSet == null) {
+            reachable.add(out);
+          } else if (!combinationNodeSet.contains(out)) {
+            reachable.add(out);
+          } else {
+            recurDirectlyReachableSkeletonCombinationNodeFrom(out, visited, reachable,
+                combinationNodeSet);
+          }
+        } else {
+          recurDirectlyReachableSkeletonCombinationNodeFrom(out, visited, reachable,
+              combinationNodeSet);
+        }
+
+      }
+
+    }
+
+  }
+
+  public HNode getDirectlyReachableSkeletonCombinationNodeFrom(HNode node) {
+    Set<HNode> visited = new HashSet<HNode>();
+    return recurDirectlyReachableSkeletonCombinationNodeFrom(node, visited);
+  }
+
+  public HNode recurDirectlyReachableSkeletonCombinationNodeFrom(HNode node, Set<HNode> visited) {
+
+    Set<HNode> outSet = getOutgoingNodeSet(node);
+    for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
+      HNode out = (HNode) iterator.next();
+      // if (!visited.contains(out)) {
+      if (out.isCombinationNode() || out.isSkeleton()) {
+        return out;
+      } else {
+        // visited.add(out);
+        return getDirectlyReachableSkeletonCombinationNodeFrom(out);
+      }
+    }
+    // }
+
+    return null;
+  }
+
   public Set<HNode> getPossibleCycleNodes(HNode src, HNode dst) {
     // if an edge from src to dst introduces a new cycle flow,
     // the method returns the set of elements consisting of the cycle
@@ -440,7 +530,7 @@ public class HierarchyGraph {
     return mapCombinationNodeToCombineNodeSet.get(node);
   }
 
-  private HNode getCombinationNode(Set<HNode> combineSet) {
+  public HNode getCombinationNode(Set<HNode> combineSet) {
     if (!mapCombineNodeSetToCombinationNode.containsKey(combineSet)) {
       String name = "COMB" + (seed++);
       HNode node = new HNode(name);
@@ -465,14 +555,22 @@ public class HierarchyGraph {
     Set<Set<HNode>> keySet = hierarchyGraph.getCombineNodeSet();
     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
       Set<HNode> combineSet = (Set<HNode>) iterator.next();
-      System.out.println("combineSet=" + combineSet);
+      System.out.println("--combineSet=" + combineSet);
       HNode combinationNode = getCombinationNode(combineSet);
-
+      System.out.println("--combinationNode=" + combinationNode);
       // add an edge from a skeleton node to a combination node
       for (Iterator iterator2 = combineSet.iterator(); iterator2.hasNext();) {
         HNode inSkeletonNode = (HNode) iterator2.next();
-        HNode srcNode = getHNode(inSkeletonNode.getDescriptor());
-        System.out.println("inSkeletonNode=" + inSkeletonNode + "   srcNode=" + srcNode);
+        // System.out.println("--inSkeletonNode=" + inSkeletonNode + "  desc="
+        // + inSkeletonNode.getDescriptor());
+        HNode srcNode;
+        if (inSkeletonNode.getDescriptor() == null) {
+          // the node is merging one...
+          srcNode = inSkeletonNode;
+        } else {
+          srcNode = getHNode(inSkeletonNode.getDescriptor());
+        }
+        // System.out.println("--srcNode=" + srcNode);
         addEdgeWithNoCycleCheck(srcNode, combinationNode);
       }
 
@@ -489,6 +587,8 @@ public class HierarchyGraph {
         }
       }
 
+      System.out.println("--");
+
     }
 
   }
@@ -522,12 +622,33 @@ public class HierarchyGraph {
 
     Set<HNode> reachToSet = new HashSet<HNode>();
     Set<HNode> visited = new HashSet<HNode>();
-
     recurSkeletonReachTo(node, reachToSet, visited);
 
+    // if a node reaches to one of elements in the reachToSet, we do not need to keep it
+    // because the node is not directly connected to the combination node
+
+    removeRedundantReachToNodes(reachToSet);
+
     return reachToSet;
   }
 
+  private void removeRedundantReachToNodes(Set<HNode> reachToSet) {
+
+    Set<HNode> toberemoved = new HashSet<HNode>();
+    for (Iterator iterator = reachToSet.iterator(); iterator.hasNext();) {
+      HNode cur = (HNode) iterator.next();
+
+      for (Iterator iterator2 = reachToSet.iterator(); iterator2.hasNext();) {
+        HNode dst = (HNode) iterator2.next();
+        if (!cur.equals(dst) && reachTo(cur, dst)) {
+          // it is redundant
+          toberemoved.add(cur);
+        }
+      }
+    }
+    reachToSet.removeAll(toberemoved);
+  }
+
   private void recurSkeletonReachTo(HNode node, Set<HNode> reachToSet, Set<HNode> visited) {
 
     Set<HNode> inSet = getIncomingNodeSet(node);
@@ -609,7 +730,10 @@ public class HierarchyGraph {
       HNode node = (HNode) iterator.next();
       if (!node.isSkeleton()) {
         Set<HNode> reachToSet = getSkeleteNodeSetReachTo(node);
-        if (reachToSet.size() > 1) {
+        // if (reachToSet.size() > 1) {
+        if (countSkeletonNodes(reachToSet) > 1) {
+          System.out.println("-node=" + node + "  reachToSet=" + reachToSet);
+          System.out.println("-set combinationnode=" + node);
           node.setCombinationNode(true);
           mapCombinationNodeToCombineNodeSet.put(node, reachToSet);
         }
@@ -628,6 +752,22 @@ public class HierarchyGraph {
 
   }
 
+  public Map<HNode, Set<HNode>> getMapCombinationNodeToCombineNodeSet() {
+    return mapCombinationNodeToCombineNodeSet;
+  }
+
+  public int countSkeletonNodes(Set<HNode> set) {
+    int count = 0;
+
+    for (Iterator iterator = set.iterator(); iterator.hasNext();) {
+      HNode node = (HNode) iterator.next();
+      Set<Descriptor> descSet = getDescSetOfNode(node);
+      count += descSet.size();
+    }
+
+    return count;
+  }
+
   private void addMapCombineSetToOutgoingSet(Set<HNode> combineSet, Set<HNode> outSet) {
     if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) {
       mapCombineNodeSetToOutgoingNodeSet.put(combineSet, new HashSet<HNode>());
@@ -671,6 +811,114 @@ public class HierarchyGraph {
 
   }
 
+  private Set<HNode> getReachableNodeSetFrom(HNode node) {
+
+    Set<HNode> reachableSet = new HashSet<HNode>();
+    Set<HNode> visited = new HashSet<HNode>();
+
+    recurReachableNodeSetFrom(node, reachableSet, visited);
+
+    return reachableSet;
+  }
+
+  private void recurReachableNodeSetFrom(HNode node, Set<HNode> reachableSet, Set<HNode> visited) {
+
+    Set<HNode> outgoingNodeSet = getOutgoingNodeSet(node);
+    for (Iterator iterator = outgoingNodeSet.iterator(); iterator.hasNext();) {
+      HNode outNode = (HNode) iterator.next();
+      reachableSet.add(outNode);
+      if (!visited.contains(outNode)) {
+        visited.add(outNode);
+        recurReachableNodeSetFrom(outNode, reachableSet, visited);
+      }
+    }
+
+  }
+
+  public void assignUniqueIndexToNode() {
+    int idx = 1;
+    for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
+      HNode node = (HNode) iterator.next();
+      mapHNodeToUniqueIndex.put(node, idx);
+      idx++;
+    }
+
+    BASISTOPELEMENT = new HashSet<Integer>();
+    for (int i = 1; i < idx + 1; i++) {
+      BASISTOPELEMENT.add(i);
+    }
+  }
+
+  public BasisSet computeBasisSet() {
+
+    // assign a unique index to a node
+    assignUniqueIndexToNode();
+
+    // compute basis for each node
+    for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
+      HNode node = (HNode) iterator.next();
+
+      Set<Integer> basis = new HashSet<Integer>();
+      basis.addAll(BASISTOPELEMENT);
+
+      Set<HNode> reachableNodeSet = getReachableNodeSetFrom(node);
+      System.out.println("node=" + node + "    reachableNodeSet=" + reachableNodeSet);
+
+      // if a node is reachable from the current node
+      // need to remove the index of the reachable node from the basis
+
+      basis.remove(getHNodeIndex(node));
+      for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
+        HNode reachableNode = (HNode) iterator2.next();
+        int idx = getHNodeIndex(reachableNode);
+        basis.remove(idx);
+      }
+
+      mapHNodeToBasis.put(node, basis);
+    }
+
+    // construct the basis set
+
+    BasisSet basisSet = new BasisSet();
+
+    Set<HNode> keySet = mapHNodeToBasis.keySet();
+    for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
+      HNode node = (HNode) iterator.next();
+      Set<Integer> basis = mapHNodeToBasis.get(node);
+      basisSet.addElement(basis, node);
+    }
+
+    return basisSet;
+
+  }
+
+  public int getHNodeIndex(HNode node) {
+    return mapHNodeToUniqueIndex.get(node).intValue();
+  }
+
+  public Map<HNode, Integer> getMapHNodeToUniqueIndex() {
+    return mapHNodeToUniqueIndex;
+  }
+
+  public Map<HNode, Set<Integer>> getMapHNodeToBasis() {
+    return mapHNodeToBasis;
+  }
+
+  public Set<HNode> getCombinationNodeSetByCombineNodeSet(Set<HNode> combineSkeletonNodeSet) {
+
+    Set<HNode> combinationNodeSet = new HashSet<HNode>();
+    Set<HNode> keySet = mapCombinationNodeToCombineNodeSet.keySet();
+    for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
+      HNode key = (HNode) iterator.next();
+
+      if (mapCombinationNodeToCombineNodeSet.get(key).equals(combineSkeletonNodeSet)) {
+        combinationNodeSet.add(key);
+      }
+    }
+
+    return combinationNodeSet;
+  }
+
   public void writeGraph() {
 
     String graphName = "hierarchy" + name;
@@ -721,11 +969,9 @@ public class HierarchyGraph {
   }
 
   private void drawNode(BufferedWriter bw, HNode node) throws IOException {
-    String shared = "";
-    if (node.isSharedNode()) {
-      shared = "*";
-    }
-    bw.write(node.getName() + " [label=\"" + node.getName() + shared + "\"]" + ";\n");
+    String nodeName = node.toString();
+    nodeName = nodeName.substring(1, nodeName.length() - 1);
+    bw.write(node.getName() + " [label=\"" + nodeName + "\"]" + ";\n");
   }
 
 }
index 31900f1..e1524c2 100644 (file)
@@ -88,6 +88,9 @@ public class LocationInference {
   // map a method descriptor to a method summary
   private Map<MethodDescriptor, MethodSummary> mapMethodDescToMethodSummary;
 
+  // map a descriptor to a simple lattice
+  private Map<Descriptor, SSJavaLattice<String>> mapDescriptorToSimpleLattice;
+
   // map a method descriptor to the set of method invocation nodes which are
   // invoked by the method descriptor
   private Map<MethodDescriptor, Set<MethodInvokeNode>> mapMethodDescriptorToMethodInvokeNodeSet;
@@ -156,6 +159,8 @@ public class LocationInference {
     this.mapDescriptorToCombineSkeletonHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
     this.mapDescriptorToSimpleHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
 
+    this.mapDescriptorToSimpleLattice = new HashMap<Descriptor, SSJavaLattice<String>>();
+
   }
 
   public void setupToAnalyze() {
@@ -204,13 +209,23 @@ public class LocationInference {
 
     constructHierarchyGraph();
 
+    debug_writeHierarchyDotFiles();
+
     simplifyHierarchyGraph();
 
+    debug_writeSimpleHierarchyDotFiles();
+
     constructSkeletonHierarchyGraph();
 
+    debug_writeSkeletonHierarchyDotFiles();
+
     insertCombinationNodes();
 
-    debug_writeHierarchyDotFile();
+    debug_writeSkeletonCombinationHierarchyDotFiles();
+
+    buildLattice();
+
+    debug_writeLattices();
 
     System.exit(0);
 
@@ -232,6 +247,88 @@ public class LocationInference {
 
   }
 
+  private void debug_writeLattices() {
+
+    Set<Descriptor> keySet = mapDescriptorToSimpleLattice.keySet();
+    for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
+      Descriptor key = (Descriptor) iterator.next();
+      SSJavaLattice<String> simpleLattice = mapDescriptorToSimpleLattice.get(key);
+      if (key instanceof ClassDescriptor) {
+        ssjava.writeLatticeDotFile((ClassDescriptor) key, null, simpleLattice, "_SIMPLE");
+      } else if (key instanceof MethodDescriptor) {
+        MethodDescriptor md = (MethodDescriptor) key;
+        ssjava.writeLatticeDotFile(md.getClassDesc(), md, simpleLattice, "_SIMPLE");
+      }
+    }
+
+    Set<ClassDescriptor> cdKeySet = cd2lattice.keySet();
+    for (Iterator iterator = cdKeySet.iterator(); iterator.hasNext();) {
+      ClassDescriptor cd = (ClassDescriptor) iterator.next();
+      ssjava.writeLatticeDotFile(cd, null, cd2lattice.get(cd));
+    }
+
+    Set<MethodDescriptor> mdKeySet = md2lattice.keySet();
+    for (Iterator iterator = mdKeySet.iterator(); iterator.hasNext();) {
+      MethodDescriptor md = (MethodDescriptor) iterator.next();
+      ssjava.writeLatticeDotFile(md.getClassDesc(), md, md2lattice.get(md));
+    }
+
+  }
+
+  private void buildLattice() {
+
+    BuildLattice buildLattice = new BuildLattice(this);
+
+    Set<Descriptor> keySet = mapDescriptorToCombineSkeletonHierarchyGraph.keySet();
+    for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
+      Descriptor desc = (Descriptor) iterator.next();
+
+      HierarchyGraph graph = getSkeletonCombinationHierarchyGraph(desc);
+      SSJavaLattice<String> simpleLattice = buildLattice.buildLattice(graph);
+
+      addMapDescToSimpleLattice(desc, simpleLattice);
+
+      HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc);
+      System.out.println("## insertIntermediateNodesToStraightLine:"
+          + simpleHierarchyGraph.getName());
+      SSJavaLattice<String> lattice =
+          buildLattice.insertIntermediateNodesToStraightLine(desc, simpleLattice);
+      lattice.removeRedundantEdges();
+
+      if (desc instanceof ClassDescriptor) {
+        // field lattice
+        cd2lattice.put((ClassDescriptor) desc, lattice);
+        // ssjava.writeLatticeDotFile((ClassDescriptor) desc, null, lattice);
+      } else if (desc instanceof MethodDescriptor) {
+        // method lattice
+        md2lattice.put((MethodDescriptor) desc, lattice);
+        MethodDescriptor md = (MethodDescriptor) desc;
+        ClassDescriptor cd = md.getClassDesc();
+        // ssjava.writeLatticeDotFile(cd, md, lattice);
+      }
+
+      // System.out.println("\nSSJAVA: Insering 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();
+      // mapDescriptorToCombineSkeletonHierarchyGraph.put(desc, skeletonGraphWithCombinationNode);
+    }
+
+  }
+
+  public void addMapDescToSimpleLattice(Descriptor desc, SSJavaLattice<String> lattice) {
+    mapDescriptorToSimpleLattice.put(desc, lattice);
+  }
+
+  public SSJavaLattice<String> getSimpleLattice(Descriptor desc) {
+    return mapDescriptorToSimpleLattice.get(desc);
+  }
+
   private void simplifyHierarchyGraph() {
     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
@@ -252,8 +349,9 @@ public class LocationInference {
       HierarchyGraph skeletonGraphWithCombinationNode = skeletonGraph.clone();
       skeletonGraphWithCombinationNode.setName(desc + "_SC");
 
-      HierarchyGraph hierarchyGraph = getHierarchyGraph(desc);
-      skeletonGraphWithCombinationNode.insertCombinationNodesToGraph(hierarchyGraph);
+      HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc);
+      System.out.println("Identifying Combination Nodes:");
+      skeletonGraphWithCombinationNode.insertCombinationNodesToGraph(simpleHierarchyGraph);
       skeletonGraphWithCombinationNode.simplifySkeletonCombinationHierarchyGraph();
       mapDescriptorToCombineSkeletonHierarchyGraph.put(desc, skeletonGraphWithCombinationNode);
     }
@@ -267,18 +365,47 @@ public class LocationInference {
       HierarchyGraph skeletonGraph = simpleGraph.generateSkeletonGraph();
       skeletonGraph.setMapDescToHNode(simpleGraph.getMapDescToHNode());
       skeletonGraph.setMapHNodeToDescSet(simpleGraph.getMapHNodeToDescSet());
+      skeletonGraph.removeRedundantEdges();
       mapDescriptorToSkeletonHierarchyGraph.put(desc, skeletonGraph);
     }
   }
 
-  private void debug_writeHierarchyDotFile() {
+  private void debug_writeHierarchyDotFiles() {
+
+    Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
+    for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
+      Descriptor desc = (Descriptor) iterator.next();
+      getHierarchyGraph(desc).writeGraph();
+    }
+
+  }
+
+  private void debug_writeSimpleHierarchyDotFiles() {
 
     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
       Descriptor desc = (Descriptor) iterator.next();
       getHierarchyGraph(desc).writeGraph();
       getSimpleHierarchyGraph(desc).writeGraph();
+    }
+
+  }
+
+  private void debug_writeSkeletonHierarchyDotFiles() {
+
+    Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
+    for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
+      Descriptor desc = (Descriptor) iterator.next();
       getSkeletonHierarchyGraph(desc).writeGraph();
+    }
+
+  }
+
+  private void debug_writeSkeletonCombinationHierarchyDotFiles() {
+
+    Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
+    for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
+      Descriptor desc = (Descriptor) iterator.next();
       getSkeletonCombinationHierarchyGraph(desc).writeGraph();
     }
 
@@ -295,7 +422,7 @@ public class LocationInference {
     return mapDescriptorToSkeletonHierarchyGraph.get(d);
   }
 
-  private HierarchyGraph getSkeletonCombinationHierarchyGraph(Descriptor d) {
+  public HierarchyGraph getSkeletonCombinationHierarchyGraph(Descriptor d) {
     if (!mapDescriptorToCombineSkeletonHierarchyGraph.containsKey(d)) {
       mapDescriptorToCombineSkeletonHierarchyGraph.put(d, new HierarchyGraph(d));
     }
index 46a2296..afc629c 100644 (file)
@@ -345,15 +345,23 @@ public class SSJavaAnalysis {
 
   public <T> void writeLatticeDotFile(ClassDescriptor cd, MethodDescriptor md,
       SSJavaLattice<T> locOrder) {
+    writeLatticeDotFile(cd, md, locOrder, "");
+
+  }
+
+  public <T> void writeLatticeDotFile(ClassDescriptor cd, MethodDescriptor md,
+      SSJavaLattice<T> locOrder, String nameSuffix) {
 
     String fileName = "lattice_";
     if (md != null) {
       fileName +=
-          cd.getSymbol().replaceAll("[\\W_]", "") + "_" + md.getSymbol().replaceAll("[\\W_]", "");
+          cd.getSymbol().replaceAll("[\\W_]", "") + "_" + md.toString().replaceAll("[\\W_]", "");
     } else {
       fileName += cd.getSymbol().replaceAll("[\\W_]", "");
     }
 
+    fileName += nameSuffix;
+
     Set<Pair<T, T>> pairSet = locOrder.getOrderingPairSet();
 
     if (pairSet.size() > 0) {
index 4343f2d..ef1722b 100644 (file)
@@ -18,6 +18,10 @@ public class SSJavaLattice<T> extends Lattice<T> {
     sharedLocSet = new HashSet<T>();
   }
 
+  public void setSharedLocSet(Set<T> in) {
+    sharedLocSet.addAll(in);
+  }
+
   public Set<T> getSharedLocSet() {
     return sharedLocSet;
   }
@@ -241,43 +245,30 @@ public class SSJavaLattice<T> extends Lattice<T> {
   }
 
   public void removeRedundantEdges() {
-    boolean isUpdated;
-    do {
-      isUpdated = recurRemoveRedundant();
-    } while (isUpdated);
-  }
 
-  public boolean recurRemoveRedundant() {
-
-    Set<T> keySet = getKeySet();
-    Set<T> visited = new HashSet<T>();
+    Set<T> keySet = getTable().keySet();
 
     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
-      T key = (T) iterator.next();
-      Set<T> connectedSet = getTable().get(key);
-      if (connectedSet != null) {
-        Set<T> toberemovedSet = new HashSet<T>();
-        for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) {
-          T dst = (T) iterator2.next();
-          Set<T> otherNeighborSet = new HashSet<T>();
-          otherNeighborSet.addAll(connectedSet);
-          otherNeighborSet.remove(dst);
-          for (Iterator iterator3 = otherNeighborSet.iterator(); iterator3.hasNext();) {
-            T neighbor = (T) iterator3.next();
-            if (isReachable(neighbor, visited, dst)) {
-              toberemovedSet.add(dst);
-            }
+      T src = (T) iterator.next();
+      Set<T> connectedSet = getTable().get(src);
+      Set<T> toberemovedSet = new HashSet<T>();
+      for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) {
+        T dst = (T) iterator2.next();
+        Set<T> otherNeighborSet = new HashSet<T>();
+        otherNeighborSet.addAll(connectedSet);
+        otherNeighborSet.remove(dst);
+        for (Iterator iterator3 = otherNeighborSet.iterator(); iterator3.hasNext();) {
+          T neighbor = (T) iterator3.next();
+          if (isReachable(neighbor, new HashSet<T>(), dst)) {
+            toberemovedSet.add(dst);
           }
         }
-        if (toberemovedSet.size() > 0) {
-          connectedSet.removeAll(toberemovedSet);
-          return true;
-        }
+      }
+      if (toberemovedSet.size() > 0) {
+        connectedSet.removeAll(toberemovedSet);
       }
     }
 
-    return false;
-
   }
 
   private boolean isReachable(T neighbor, Set<T> visited, T dst) {
@@ -319,4 +310,32 @@ public class SSJavaLattice<T> extends Lattice<T> {
 
     return map;
   }
+
+  public void insertNewLocationBetween(T higher, T lower, T newLoc) {
+    Set<T> connectedSet = get(higher);
+    connectedSet.remove(lower);
+    connectedSet.add(newLoc);
+
+    put(newLoc, lower);
+  }
+
+  public void insertNewLocationBetween(T higher, Set<T> lowerSet, T newLoc) {
+    Set<T> connectedSet = get(higher);
+    connectedSet.removeAll(lowerSet);
+    connectedSet.add(newLoc);
+
+    for (Iterator iterator = lowerSet.iterator(); iterator.hasNext();) {
+      T lower = (T) iterator.next();
+      put(newLoc, lower);
+    }
+  }
+
+  public SSJavaLattice<T> clone() {
+
+    SSJavaLattice<T> clone = new SSJavaLattice<T>(getTopItem(), getBottomItem());
+    clone.setTable(getTable());
+    clone.setSharedLocSet(getSharedLocSet());
+    return clone;
+  }
+
 }
index 16c8936..aea7477 100644 (file)
@@ -40,6 +40,17 @@ public class Lattice<T> {
     return table;
   }
 
+  public void setTable(Map<T, Set<T>> in) {
+    Set<T> keySet = in.keySet();
+    for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
+      T key = (T) iterator.next();
+      Set<T> setIn = in.get(key);
+      Set<T> newSet = new HashSet<T>();
+      newSet.addAll(setIn);
+      table.put(key, newSet);
+    }
+  }
+
   public boolean put(T key) {
     if (table.containsKey(key)) {
       return false;