From b1709554ba9722b714ff6e8f83d60943fc1fa1d8 Mon Sep 17 00:00:00 2001 From: yeom Date: Sat, 22 Sep 2012 00:49:41 +0000 Subject: [PATCH] changes. --- Robust/src/Analysis/SSJava/BasisSet.java | 53 +++ Robust/src/Analysis/SSJava/BuildLattice.java | 447 ++++++++++++++++++ Robust/src/Analysis/SSJava/FElement.java | 15 + Robust/src/Analysis/SSJava/Family.java | 57 +++ Robust/src/Analysis/SSJava/HNode.java | 21 +- .../src/Analysis/SSJava/HierarchyGraph.java | 286 ++++++++++- .../Analysis/SSJava/LocationInference.java | 137 +++++- .../src/Analysis/SSJava/SSJavaAnalysis.java | 10 +- Robust/src/Analysis/SSJava/SSJavaLattice.java | 77 +-- Robust/src/Util/Lattice.java | 11 + 10 files changed, 1056 insertions(+), 58 deletions(-) create mode 100644 Robust/src/Analysis/SSJava/BasisSet.java create mode 100644 Robust/src/Analysis/SSJava/BuildLattice.java create mode 100644 Robust/src/Analysis/SSJava/FElement.java create mode 100644 Robust/src/Analysis/SSJava/Family.java diff --git a/Robust/src/Analysis/SSJava/BasisSet.java b/Robust/src/Analysis/SSJava/BasisSet.java new file mode 100644 index 00000000..a379e996 --- /dev/null +++ b/Robust/src/Analysis/SSJava/BasisSet.java @@ -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, HNode> map; + + public BasisSet() { + map = new HashMap, HNode>(); + } + + public void addElement(Set basis, HNode node) { + map.put(basis, node); + } + + public Iterator> basisIterator() { + return map.keySet().iterator(); + } + + public HNode getHNode(Set B) { + return map.get(B); + } + + public Set getHNodeSet() { + Set set = new HashSet(); + set.addAll(map.values()); + return set; + } + + public Set> getBasisSetByHNodeSet(Set nodeSet) { + + Set> rtrSet = new HashSet>(); + + Set> keySet = map.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Set basisKey = (Set) 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 index 00000000..eca8dfaa --- /dev/null +++ b/Robust/src/Analysis/SSJava/BuildLattice.java @@ -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 buildLattice(HierarchyGraph inputGraph) { + + BasisSet basisSet = inputGraph.computeBasisSet(); + debug_print(inputGraph); + + Family family = generateFamily(basisSet); + Map, Set>> mapImSucc = coveringGraph(basisSet, family); + + SSJavaLattice lattice = buildLattice(basisSet, inputGraph, mapImSucc); + return lattice; + + } + + private SSJavaLattice buildLattice(BasisSet basisSet, HierarchyGraph inputGraph, + Map, Set>> mapImSucc) { + + SSJavaLattice lattice = + new SSJavaLattice(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM); + + Map, String> mapFToLocName = new HashMap, String>(); + + Set> keySet = mapImSucc.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Set higher = (Set) iterator.next(); + + String higherName = generateElementName(basisSet, inputGraph, mapFToLocName, higher); + + Set> lowerSet = mapImSucc.get(higher); + for (Iterator iterator2 = lowerSet.iterator(); iterator2.hasNext();) { + Set lower = (Set) 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 combineSkeletonNodeSet = + infer.getSimpleHierarchyGraph(desc).getCombineSetByCombinationNode(simpleGraphNode); + HNode combinationNodeInSCGraph = + infer.getSkeletonCombinationHierarchyGraph(desc).getCombinationNode(combineSkeletonNodeSet); + return combinationNodeInSCGraph; + } + + public SSJavaLattice insertIntermediateNodesToStraightLine(Descriptor desc, + SSJavaLattice 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 lattice = skeletonLattice.clone(); + + Map mapIntermediateLocation = new HashMap(); + + Set visited = new HashSet(); + + Set nodeSet = simpleGraph.getNodeSet(); + + // expand a combination node + Map mapIntermediateLoc = new HashMap(); + for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + HNode node = (HNode) iterator.next(); + if (node.isSkeleton() && (!visited.contains(node))) { + visited.add(node); + + Set 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 combineSkeletonNodeSet = + simpleGraph.getCombineSetByCombinationNode(outNode); + Set combinationNodeSet = + simpleGraph.getCombinationNodeSetByCombineNodeSet(combineSkeletonNodeSet); + Set endNodeSetFromSimpleGraph = + simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(outNode, + combinationNodeSet); + Set endCombNodeSet = new HashSet(); + 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 endNodeSetFromSimpleGraph = + simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(outNode, null); + + Set endCombNodeSet = new HashSet(); + 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 lattice, HNode startNode, + Set endNodeSet, Set visited, Map 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 belowSet = new HashSet(); + 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 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 lattice, + HNode combinationNodeInSCGraph, Set endNodeSet, Set visited, + Map 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 belowSet = new HashSet(); + 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 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, String> mapF2LocName, Set 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, Integer> mapFtoCount, Family family) { + for (Iterator> iter = family.FIterator(); iter.hasNext();) { + Set F = iter.next(); + mapFtoCount.put(F, 0); + } + } + + private Map, Set>> coveringGraph(BasisSet basisSet, Family family) { + + Map, Integer> mapFtoCount = new HashMap, Integer>(); + Map, Set>> mapImSucc = new HashMap, Set>>(); + + // initialize COUNT(F) to 0 for all elements of the family + resetCount(mapFtoCount, family); + + for (Iterator> iter = family.FIterator(); iter.hasNext();) { + Set F = iter.next(); + Set gammaF = family.getGamma(F); + + Set curHNodeSet = basisSet.getHNodeSet(); + curHNodeSet.removeAll(gammaF); + Set> Bset = basisSet.getBasisSetByHNodeSet(curHNodeSet); + + for (Iterator iterator = Bset.iterator(); iterator.hasNext();) { + Set B = (Set) iterator.next(); + + Set Fprime = new HashSet(); + 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> getImSucc(Map, Set>> mapImSucc, Set F) { + if (!mapImSucc.containsKey(F)) { + mapImSucc.put(F, new HashSet>()); + } + return mapImSucc.get(F); + } + + private void addImSucc(Map, Set>> mapImSucc, Set F, + Set Fprime) { + + if (!mapImSucc.containsKey(F)) { + mapImSucc.put(F, new HashSet>()); + } + + mapImSucc.get(F).add(Fprime); + + } + + private Family generateFamily(BasisSet basisSet) { + + Family family = new Family(); + + for (Iterator> iterator = basisSet.basisIterator(); iterator.hasNext();) { + Set B = iterator.next(); + + Set, Set>> tobeadded = new HashSet, Set>>(); + + for (Iterator> iterator2 = family.FIterator(); iterator2.hasNext();) { + Set F = iterator2.next(); + + Set Fprime = new HashSet(); + Fprime.addAll(F); + Fprime.addAll(B); + + Set gammaFPrimeSet = new HashSet(); + gammaFPrimeSet.addAll(family.getGamma(F)); + gammaFPrimeSet.add(basisSet.getHNode(B)); + + if (!family.containsF(Fprime)) { + Pair, Set> pair = + new Pair, Set>(Fprime, gammaFPrimeSet); + tobeadded.add(pair); + } else { + family.updateGammaF(Fprime, gammaFPrimeSet); + } + } + + for (Iterator, Set>> iterator2 = tobeadded.iterator(); iterator2 + .hasNext();) { + Pair, Set> 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 lowerNodeSet; + public int idx; + + public TripleItem(HNode h, Set 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 index 00000000..49480cc6 --- /dev/null +++ b/Robust/src/Analysis/SSJava/FElement.java @@ -0,0 +1,15 @@ +package Analysis.SSJava; + +import java.util.HashSet; +import java.util.Set; + +public class FElement { + + public static Set EMPTY = new HashSet(); + Set set; + + public FElement() { + set = new HashSet(); + } + +} diff --git a/Robust/src/Analysis/SSJava/Family.java b/Robust/src/Analysis/SSJava/Family.java new file mode 100644 index 00000000..07ffe073 --- /dev/null +++ b/Robust/src/Analysis/SSJava/Family.java @@ -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> mapFtoGammaF; + + Set> Fset; + + public static Set EMPTY = new HashSet(); + + public Family() { + Fset = new HashSet>(); + Fset.add(EMPTY); + mapFtoGammaF = new HashMap, Set>(); + } + + public void addFElement(Set F) { + Fset.add(F); + } + + public Set getGamma(Set F) { + if (!mapFtoGammaF.containsKey(F)) { + mapFtoGammaF.put(F, new HashSet()); + } + return mapFtoGammaF.get(F); + } + + public void updateGammaF(Set F, Set gamma) { + getGamma(F).addAll(gamma); + } + + public boolean containsF(Set F) { + return Fset.contains(F); + } + + public int size() { + return Fset.size(); + } + + public Iterator> FIterator() { + return Fset.iterator(); + } + + public String toString() { + + return mapFtoGammaF.toString(); + + } + +} diff --git a/Robust/src/Analysis/SSJava/HNode.java b/Robust/src/Analysis/SSJava/HNode.java index 47d2c720..62bae954 100644 --- a/Robust/src/Analysis/SSJava/HNode.java +++ b/Robust/src/Analysis/SSJava/HNode.java @@ -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() { diff --git a/Robust/src/Analysis/SSJava/HierarchyGraph.java b/Robust/src/Analysis/SSJava/HierarchyGraph.java index 02625d92..52eb8742 100644 --- a/Robust/src/Analysis/SSJava/HierarchyGraph.java +++ b/Robust/src/Analysis/SSJava/HierarchyGraph.java @@ -25,11 +25,17 @@ public class HierarchyGraph { Map> mapCombinationNodeToCombineNodeSet; Map, HNode> mapCombineNodeSetToCombinationNode; Map, Set> mapCombineNodeSetToOutgoingNodeSet; + Map mapHNodeToLocationName; Set nodeSet; public static int seed = 0; + // for the lattice generation + Map mapHNodeToUniqueIndex; + Map> mapHNodeToBasis; + Set BASISTOPELEMENT; + public HierarchyGraph() { mapHNodeToIncomingSet = new HashMap>(); mapHNodeToOutgoingSet = new HashMap>(); @@ -40,6 +46,12 @@ public class HierarchyGraph { mapCombineNodeSetToOutgoingNodeSet = new HashMap, Set>(); mapCombineNodeSetToCombinationNode = new HashMap, HNode>(); nodeSet = new HashSet(); + + mapHNodeToUniqueIndex = new HashMap(); + mapHNodeToBasis = new HashMap>(); + + mapHNodeToLocationName = new HashMap(); + } 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 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 getOutgoingNodeSet(HNode node) { + public Set getOutgoingNodeSet(HNode node) { if (!mapHNodeToOutgoingSet.containsKey(node)) { mapHNodeToOutgoingSet.put(node, new HashSet()); } @@ -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 getDirectlyReachableSkeletonCombinationNodeFrom(HNode node, + Set combinationNodeSet) { + Set reachable = new HashSet(); + Set visited = new HashSet(); + visited.add(node); + recurDirectlyReachableSkeletonCombinationNodeFrom(node, visited, reachable, combinationNodeSet); + return reachable; + } + + public void recurDirectlyReachableSkeletonCombinationNodeFrom(HNode node, Set visited, + Set reachable, Set combinationNodeSet) { + + Set 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 visited = new HashSet(); + return recurDirectlyReachableSkeletonCombinationNodeFrom(node, visited); + } + + public HNode recurDirectlyReachableSkeletonCombinationNodeFrom(HNode node, Set visited) { + + Set 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 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 combineSet) { + public HNode getCombinationNode(Set combineSet) { if (!mapCombineNodeSetToCombinationNode.containsKey(combineSet)) { String name = "COMB" + (seed++); HNode node = new HNode(name); @@ -465,14 +555,22 @@ public class HierarchyGraph { Set> keySet = hierarchyGraph.getCombineNodeSet(); for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { Set combineSet = (Set) 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 reachToSet = new HashSet(); Set visited = new HashSet(); - 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 reachToSet) { + + Set toberemoved = new HashSet(); + 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 reachToSet, Set visited) { Set inSet = getIncomingNodeSet(node); @@ -609,7 +730,10 @@ public class HierarchyGraph { HNode node = (HNode) iterator.next(); if (!node.isSkeleton()) { Set 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> getMapCombinationNodeToCombineNodeSet() { + return mapCombinationNodeToCombineNodeSet; + } + + public int countSkeletonNodes(Set set) { + int count = 0; + + for (Iterator iterator = set.iterator(); iterator.hasNext();) { + HNode node = (HNode) iterator.next(); + Set descSet = getDescSetOfNode(node); + count += descSet.size(); + } + + return count; + } + private void addMapCombineSetToOutgoingSet(Set combineSet, Set outSet) { if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) { mapCombineNodeSetToOutgoingNodeSet.put(combineSet, new HashSet()); @@ -671,6 +811,114 @@ public class HierarchyGraph { } + private Set getReachableNodeSetFrom(HNode node) { + + Set reachableSet = new HashSet(); + Set visited = new HashSet(); + + recurReachableNodeSetFrom(node, reachableSet, visited); + + return reachableSet; + } + + private void recurReachableNodeSetFrom(HNode node, Set reachableSet, Set visited) { + + Set 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(); + 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 basis = new HashSet(); + basis.addAll(BASISTOPELEMENT); + + Set 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 keySet = mapHNodeToBasis.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + HNode node = (HNode) iterator.next(); + Set basis = mapHNodeToBasis.get(node); + basisSet.addElement(basis, node); + } + + return basisSet; + + } + + public int getHNodeIndex(HNode node) { + return mapHNodeToUniqueIndex.get(node).intValue(); + } + + public Map getMapHNodeToUniqueIndex() { + return mapHNodeToUniqueIndex; + } + + public Map> getMapHNodeToBasis() { + return mapHNodeToBasis; + } + + public Set getCombinationNodeSetByCombineNodeSet(Set combineSkeletonNodeSet) { + + Set combinationNodeSet = new HashSet(); + Set 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"); } } diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index 31900f10..e1524c25 100644 --- a/Robust/src/Analysis/SSJava/LocationInference.java +++ b/Robust/src/Analysis/SSJava/LocationInference.java @@ -88,6 +88,9 @@ public class LocationInference { // map a method descriptor to a method summary private Map mapMethodDescToMethodSummary; + // map a descriptor to a simple lattice + private Map> mapDescriptorToSimpleLattice; + // map a method descriptor to the set of method invocation nodes which are // invoked by the method descriptor private Map> mapMethodDescriptorToMethodInvokeNodeSet; @@ -156,6 +159,8 @@ public class LocationInference { this.mapDescriptorToCombineSkeletonHierarchyGraph = new HashMap(); this.mapDescriptorToSimpleHierarchyGraph = new HashMap(); + this.mapDescriptorToSimpleLattice = new HashMap>(); + } 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 keySet = mapDescriptorToSimpleLattice.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Descriptor key = (Descriptor) iterator.next(); + SSJavaLattice 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 cdKeySet = cd2lattice.keySet(); + for (Iterator iterator = cdKeySet.iterator(); iterator.hasNext();) { + ClassDescriptor cd = (ClassDescriptor) iterator.next(); + ssjava.writeLatticeDotFile(cd, null, cd2lattice.get(cd)); + } + + Set 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 keySet = mapDescriptorToCombineSkeletonHierarchyGraph.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Descriptor desc = (Descriptor) iterator.next(); + + HierarchyGraph graph = getSkeletonCombinationHierarchyGraph(desc); + SSJavaLattice simpleLattice = buildLattice.buildLattice(graph); + + addMapDescToSimpleLattice(desc, simpleLattice); + + HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc); + System.out.println("## insertIntermediateNodesToStraightLine:" + + simpleHierarchyGraph.getName()); + SSJavaLattice 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 lattice) { + mapDescriptorToSimpleLattice.put(desc, lattice); + } + + public SSJavaLattice getSimpleLattice(Descriptor desc) { + return mapDescriptorToSimpleLattice.get(desc); + } + private void simplifyHierarchyGraph() { Set 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 keySet = mapDescriptorToHierarchyGraph.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Descriptor desc = (Descriptor) iterator.next(); + getHierarchyGraph(desc).writeGraph(); + } + + } + + private void debug_writeSimpleHierarchyDotFiles() { Set 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 keySet = mapDescriptorToHierarchyGraph.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Descriptor desc = (Descriptor) iterator.next(); getSkeletonHierarchyGraph(desc).writeGraph(); + } + + } + + private void debug_writeSkeletonCombinationHierarchyDotFiles() { + + Set 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)); } diff --git a/Robust/src/Analysis/SSJava/SSJavaAnalysis.java b/Robust/src/Analysis/SSJava/SSJavaAnalysis.java index 46a22966..afc629cf 100644 --- a/Robust/src/Analysis/SSJava/SSJavaAnalysis.java +++ b/Robust/src/Analysis/SSJava/SSJavaAnalysis.java @@ -345,15 +345,23 @@ public class SSJavaAnalysis { public void writeLatticeDotFile(ClassDescriptor cd, MethodDescriptor md, SSJavaLattice locOrder) { + writeLatticeDotFile(cd, md, locOrder, ""); + + } + + public void writeLatticeDotFile(ClassDescriptor cd, MethodDescriptor md, + SSJavaLattice 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> pairSet = locOrder.getOrderingPairSet(); if (pairSet.size() > 0) { diff --git a/Robust/src/Analysis/SSJava/SSJavaLattice.java b/Robust/src/Analysis/SSJava/SSJavaLattice.java index 4343f2de..ef1722b7 100644 --- a/Robust/src/Analysis/SSJava/SSJavaLattice.java +++ b/Robust/src/Analysis/SSJava/SSJavaLattice.java @@ -18,6 +18,10 @@ public class SSJavaLattice extends Lattice { sharedLocSet = new HashSet(); } + public void setSharedLocSet(Set in) { + sharedLocSet.addAll(in); + } + public Set getSharedLocSet() { return sharedLocSet; } @@ -241,43 +245,30 @@ public class SSJavaLattice extends Lattice { } public void removeRedundantEdges() { - boolean isUpdated; - do { - isUpdated = recurRemoveRedundant(); - } while (isUpdated); - } - public boolean recurRemoveRedundant() { - - Set keySet = getKeySet(); - Set visited = new HashSet(); + Set keySet = getTable().keySet(); for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { - T key = (T) iterator.next(); - Set connectedSet = getTable().get(key); - if (connectedSet != null) { - Set toberemovedSet = new HashSet(); - for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) { - T dst = (T) iterator2.next(); - Set otherNeighborSet = new HashSet(); - 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 connectedSet = getTable().get(src); + Set toberemovedSet = new HashSet(); + for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) { + T dst = (T) iterator2.next(); + Set otherNeighborSet = new HashSet(); + otherNeighborSet.addAll(connectedSet); + otherNeighborSet.remove(dst); + for (Iterator iterator3 = otherNeighborSet.iterator(); iterator3.hasNext();) { + T neighbor = (T) iterator3.next(); + if (isReachable(neighbor, new HashSet(), 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 visited, T dst) { @@ -319,4 +310,32 @@ public class SSJavaLattice extends Lattice { return map; } + + public void insertNewLocationBetween(T higher, T lower, T newLoc) { + Set connectedSet = get(higher); + connectedSet.remove(lower); + connectedSet.add(newLoc); + + put(newLoc, lower); + } + + public void insertNewLocationBetween(T higher, Set lowerSet, T newLoc) { + Set 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 clone() { + + SSJavaLattice clone = new SSJavaLattice(getTopItem(), getBottomItem()); + clone.setTable(getTable()); + clone.setSharedLocSet(getSharedLocSet()); + return clone; + } + } diff --git a/Robust/src/Util/Lattice.java b/Robust/src/Util/Lattice.java index 16c89369..aea74773 100644 --- a/Robust/src/Util/Lattice.java +++ b/Robust/src/Util/Lattice.java @@ -40,6 +40,17 @@ public class Lattice { return table; } + public void setTable(Map> in) { + Set keySet = in.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + T key = (T) iterator.next(); + Set setIn = in.get(key); + Set newSet = new HashSet(); + newSet.addAll(setIn); + table.put(key, newSet); + } + } + public boolean put(T key) { if (table.containsKey(key)) { return false; -- 2.34.1