public SSJavaLattice<String> insertIntermediateNodesToStraightLine(Descriptor desc,
SSJavaLattice<String> skeletonLattice) {
+
+ SSJavaLattice<String> lattice = skeletonLattice.clone();
+ LocationSummary locSummary = infer.getLocationSummary(desc);
+
+ Descriptor parentDesc = getParent(desc);
+ if (parentDesc != null) {
+ SSJavaLattice<String> parentLattice = infer.getLattice(parentDesc);
+
+ Map<String, Set<String>> parentMap = parentLattice.getTable();
+ Set<String> parentKeySet = parentMap.keySet();
+ for (Iterator iterator = parentKeySet.iterator(); iterator.hasNext();) {
+ String parentKey = (String) iterator.next();
+ Set<String> parentValueSet = parentMap.get(parentKey);
+ for (Iterator iterator2 = parentValueSet.iterator(); iterator2.hasNext();) {
+ String value = (String) iterator2.next();
+ lattice.put(parentKey, value);
+ }
+ }
+
+ Set<String> parentSharedLocSet = parentLattice.getSharedLocSet();
+ for (Iterator iterator = parentSharedLocSet.iterator(); iterator.hasNext();) {
+ String parentSharedLoc = (String) iterator.next();
+ lattice.addSharedLoc(parentSharedLoc);
+ }
+ }
+
+ HierarchyGraph hierarchyGraph = infer.getSimpleHierarchyGraph(desc);
+ HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
+
+ Set<HNode> hierarchyGraphNodeSet = hierarchyGraph.getNodeSet();
+ for (Iterator iterator = hierarchyGraphNodeSet.iterator(); iterator.hasNext();) {
+ HNode hNode = (HNode) iterator.next();
+ if (!hNode.isSkeleton()) {
+ // here we need to insert an intermediate node for the hNode
+ System.out.println("local node=" + hNode);
+
+ // 1) find the lowest node m in the lattice that is above hnode in the lattice
+ // 2) count the number of non-shared nodes d between the hnode and the node m
+ int numNonSharedNodes;
+
+ HNode SCNode;
+ if (hNode.isDirectCombinationNode()) {
+ // this node itself is the lowest node m. it is the first node of the chain
+ Set<HNode> combineSet = hierarchyGraph.getCombineSetByCombinationNode(hNode);
+ SCNode = scGraph.getCombinationNode(combineSet);
+ numNonSharedNodes = -1;
+ } else {
+
+ Set<HNode> aboveSet = new HashSet<HNode>();
+ if (hNode.isCombinationNode()) {
+ Set<HNode> combineSkeletonNodeSet =
+ hierarchyGraph.getCombineSetByCombinationNode(hNode);
+ aboveSet.addAll(hierarchyGraph
+ .getFirstNodeOfCombinationNodeChainSet(combineSkeletonNodeSet));
+ SCNode = scGraph.getCombinationNode(combineSkeletonNodeSet);
+ } else {
+ System.out.println(" #######hierarchyGraph.getSkeleteNodeSetReachTo(" + hNode + ")="
+ + hierarchyGraph.getSkeleteNodeSetReachTo(hNode));
+
+ aboveSet.addAll(hierarchyGraph.getSkeleteNodeSetReachTo(hNode));
+ // assert aboveSet.size() == 1;
+ SCNode = aboveSet.iterator().next();
+ }
+
+ numNonSharedNodes = hierarchyGraph.countNonSharedNode(hNode, aboveSet);
+
+ System.out.println(" node=" + hNode + " above=" + aboveSet + " distance="
+ + numNonSharedNodes + " SCNode=" + SCNode);
+ }
+
+ // 3) convert the node m into a chain of nodes with the last node in the chain having m’s
+ // outgoing edges.
+ Set<String> outgoingElements = skeletonLattice.get(SCNode.getName());
+ System.out.println(" SCNODE outgoing=" + outgoingElements);
+
+ // 4) If hnode is not a shared location, check if there already exists a local variable
+ // node that has distance d below m along this chain. If such a node
+ // does not exist, insert it.
+ String locName =
+ getNewLocation(lattice, SCNode.getName(), outgoingElements, numNonSharedNodes,
+ hNode.isSharedNode());
+ System.out.println(" locName=" + locName);
+ locSummary.addMapHNodeNameToLocationName(hNode.getName(), locName);
+
+ }
+ }
+
+ return lattice;
+ }
+
+ public String getNewLocation(SSJavaLattice<String> lattice, String start, Set<String> endSet,
+ int dist, boolean isShared) {
+ System.out.println(" getNewLocation:: start=" + start + " endSet=" + endSet + " dist="
+ + dist + " isShared=" + isShared);
+ if (dist == -1) {
+ return start;
+ }
+ return recur_getNewLocation(lattice, start, endSet, dist, isShared);
+ }
+
+ private String recur_getNewLocation(SSJavaLattice<String> lattice, String cur,
+ Set<String> endSet, int dist, boolean isShared) {
+ Set<String> connectedSet = lattice.get(cur);
+ if (connectedSet == null) {
+ connectedSet = new HashSet<String>();
+ }
+
+ System.out.println(" recur_getNewLocation cur=" + cur + " dist=" + dist
+ + " connectedSet=" + connectedSet + " endSet=" + endSet);
+
+ if (dist == 0 && isShared) {
+ // if the node is shared,
+ // check if there already exists a shared node that has distance d + 1 on the chain
+ connectedSet = lattice.get(cur);
+ if (connectedSet.equals(endSet)) {
+ // need to insert a new shared location
+ } else {
+ assert connectedSet.size() == 1;
+ String below = connectedSet.iterator().next();
+ if (lattice.isSharedLoc(below)) {
+ return below;
+ }
+ }
+
+ // need to insert a new shared location
+ String newLocName = "ILOC" + (LocationInference.locSeed++);
+ for (Iterator iterator = connectedSet.iterator(); iterator.hasNext();) {
+ String outNode = (String) iterator.next();
+ lattice.put(newLocName, outNode);
+ }
+ connectedSet.clear();
+ lattice.put(cur, newLocName);
+
+ System.out.println(" INSERT NEW SHARED NODE=" + newLocName + " above=" + cur
+ + " below=" + lattice.get(newLocName));
+
+ lattice.addSharedLoc(newLocName);
+
+ return newLocName;
+
+ }
+
+ String next;
+ if (connectedSet.equals(endSet)) {
+ // need to insert a new location
+ String newLocName = "ILOC" + (LocationInference.locSeed++);
+ connectedSet.clear();
+ lattice.put(cur, newLocName);
+ System.out.println("NEW RELATION=" + lattice.get(cur));
+ for (Iterator iterator = endSet.iterator(); iterator.hasNext();) {
+ String endNode = (String) iterator.next();
+ lattice.put(newLocName, endNode);
+ }
+ next = newLocName;
+ System.out.println(" INSERT NEW NODE=" + newLocName + " above=" + cur + " below="
+ + endSet);
+ } else {
+ assert connectedSet.size() == 1;
+ next = connectedSet.iterator().next();
+ }
+ System.out.println(" next=" + next);
+
+ // if (dist == 0) {
+
+ // if (isShared) {
+
+ // // if the node is shared,
+ // // check if there already exists a shared node that has distance d + 1 on the chain
+ //
+ // connectedSet = lattice.get(next);
+ //
+ // if (connectedSet.equals(endSet)) {
+ // // need to insert a new shared location
+ // } else {
+ // assert connectedSet.size() != 1;
+ // String below = connectedSet.iterator().next();
+ // if (lattice.isSharedLoc(below)) {
+ // return below;
+ // }
+ // }
+ //
+ // // need to insert a new shared location
+ // String newLocName = "ILOC" + (LocationInference.locSeed++);
+ // for (Iterator iterator = connectedSet.iterator(); iterator.hasNext();) {
+ // String outNode = (String) iterator.next();
+ // lattice.put(newLocName, outNode);
+ // }
+ // connectedSet.clear();
+ // lattice.put(next, newLocName);
+ //
+ // System.out.println(" INSERT NEW SHARED NODE=" + newLocName + " above=" + next
+ // + " below=" + lattice.get(newLocName));
+ //
+ // lattice.addSharedLoc(newLocName);
+ //
+ // next = newLocName;
+ //
+ // }
+ //
+ // return next;
+
+ // } else {
+
+ if (dist == 0) {
+ return next;
+ } else {
+ if (!lattice.isSharedLoc(next)) {
+ dist--;
+ }
+ return recur_getNewLocation(lattice, next, endSet, dist, isShared);
+ }
+
+ // }
+
+ // ///////////////////////////////////////////////
+
+ // if (dist == 0) {
+ // return cur;
+ // } else if (connectedSet.equals(endSet)) {
+ // // need to insert a new location
+ // String newLocName = "ILOC" + (LocationInference.locSeed++);
+ // connectedSet.clear();
+ // lattice.put(cur, newLocName);
+ // for (Iterator iterator = endSet.iterator(); iterator.hasNext();) {
+ // String endNode = (String) iterator.next();
+ // lattice.put(newLocName, endNode);
+ // }
+ // return recur_getNewLocation(lattice, newLocName, endSet, --dist, isShared);
+ // } else {
+ // assert connectedSet.size() != 1;
+ // String next = connectedSet.iterator().next();
+ // return recur_getNewLocation(lattice, next, endSet, --dist, isShared);
+ // }
+
+ }
+
+ public SSJavaLattice<String> insertIntermediateNodesToStraightLine2(Descriptor desc,
+ SSJavaLattice<String> skeletonLattice) {
// copy nodes/edges from the parent method/class if possible
SSJavaLattice<String> lattice = skeletonLattice.clone();
private boolean isSharedNode;
private boolean isMergeNode;
+ // set true if hnode is the first node of the combination chain
+ private boolean isDirectCombinationNode;
+
public HNode() {
this.isSkeleton = false;
this.isCombinationNode = false;
this.isSharedNode = false;
this.isMergeNode = false;
+ this.isDirectCombinationNode = false;
}
public boolean isMergeNode() {
return name;
}
+ public boolean isDirectCombinationNode() {
+ return isDirectCombinationNode;
+ }
+
+ public void setDirectCombinationNode(boolean isDirectCombinationNode) {
+ this.isDirectCombinationNode = isDirectCombinationNode;
+ }
+
public boolean equals(Object o) {
if (o instanceof HNode) {
HNode in = (HNode) o;
Map<HNode, Set<HNode>> mapNormalNodeToSCNodeReachToSet;
+ Map<Set<HNode>, Set<HNode>> mapCombineNodeSetToFirstNodeOfChainSet;
+
Set<HNode> nodeSet;
// for the lattice generation
mapHNodeNameToCurrentHNode = new HashMap<String, HNode>();
mapNormalNodeToSCNodeReachToSet = new HashMap<HNode, Set<HNode>>();
+
+ mapCombineNodeSetToFirstNodeOfChainSet = new HashMap<Set<HNode>, Set<HNode>>();
}
public Descriptor getDesc() {
}
// System.out.println("--- CYCLIC VALUE FLOW: " + srcHNode + " -> " + dstHNode);
- HNode newMergeNode = mergeNodes(possibleCycleSet, false);
+ HNode newMergeNode = mergeNodes(possibleCycleSet);
newMergeNode.setSharedNode(true);
} else {
public void simplifyHierarchyGraph(LocationInference infer) {
removeRedundantEdges();
- combineRedundantNodes(false, infer);
+ combineRedundantNodes(infer);
}
- public void combineRedundantNodes(boolean onlyCombinationNodes, LocationInference infer) {
+ public void combineRedundantNodes(LocationInference infer) {
// Combine field/parameter nodes who have the same set of incoming/outgoing edges.
boolean isUpdated = false;
do {
- isUpdated = combineTwoRedundatnNodes(onlyCombinationNodes, infer);
+ isUpdated = combineTwoRedundatnNodes(infer);
} while (isUpdated);
}
return mapHNodeToOutgoingSet.get(node);
}
- private boolean combineTwoRedundatnNodes(boolean onlyCombinationNodes, LocationInference infer) {
+ private boolean combineTwoRedundatnNodes(LocationInference infer) {
for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
HNode node1 = (HNode) iterator.next();
- if ((onlyCombinationNodes && (!node1.isCombinationNode()))
- || (!onlyCombinationNodes && (!node1.isSkeleton()))) {
+ // if ((onlyCombinationNodes && (!node1.isCombinationNode()))
+ // || (!onlyCombinationNodes && (!node1.isSkeleton()))) {
+ // continue;
+ // }
+
+ if (!node1.isSkeleton()) {
continue;
}
for (Iterator iterator2 = nodeSet.iterator(); iterator2.hasNext();) {
HNode node2 = (HNode) iterator2.next();
- if ((onlyCombinationNodes && (!node2.isCombinationNode()))
- || (!onlyCombinationNodes && (!node2.isSkeleton()))) {
+ // if ((onlyCombinationNodes && (!node2.isCombinationNode()))
+ // || (!onlyCombinationNodes && (!node2.isSkeleton()))) {
+ // continue;
+ // }
+
+ if (!node2.isSkeleton()) {
continue;
}
// ///////////////
- mergeNodes(mergeSet, onlyCombinationNodes);
+ mergeNodes(mergeSet);
return true;
}
// System.out.println("addEdgeWithNoCycleCheck src=" + srcHNode + " -> " + dstHNode);
}
- private HNode mergeNodes(Set<HNode> set, boolean onlyCombinationNodes) {
+ private HNode mergeNodes(Set<HNode> set) {
Set<HNode> incomingNodeSet = new HashSet<HNode>();
Set<HNode> outgoingNodeSet = new HashSet<HNode>();
String nodeName;
boolean isMergeNode = false;
- if (onlyCombinationNodes) {
- nodeName = "Comb" + (LocationInference.locSeed++);
- } else {
- nodeName = "Node" + (LocationInference.locSeed++);
- isMergeNode = true;
- }
+ nodeName = "MNode" + (LocationInference.locSeed++);
+ isMergeNode = true;
+
HNode newMergeNode = new HNode(nodeName);
newMergeNode.setMergeNode(isMergeNode);
Set<Set<HNode>> keySet = simpleHierarchyGraph.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 + " combineSet=" + 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();
}
- private void addCombinationNode(HNode curNode, Set<HNode> reachToSet, Set<HNode> reachableSet) {
- if (!mapSkeletonNodeSetToCombinationNode.containsKey(reachToSet)) {
- // need to create a new combination node
- String nodeName = "Comb" + (LocationInference.locSeed++);
- HNode newCombinationNode = new HNode(nodeName);
- newCombinationNode.setCombinationNode(true);
-
- nodeSet.add(newCombinationNode);
- mapSkeletonNodeSetToCombinationNode.put(reachToSet, newCombinationNode);
-
- for (Iterator iterator = reachToSet.iterator(); iterator.hasNext();) {
- HNode reachToNode = (HNode) iterator.next();
- addEdge(reachToNode, newCombinationNode);
- }
-
- }
-
- HNode combinationNode = mapSkeletonNodeSetToCombinationNode.get(reachToSet);
- for (Iterator iterator = reachableSet.iterator(); iterator.hasNext();) {
- HNode reachableNode = (HNode) iterator.next();
- addEdge(combinationNode, reachableNode);
- }
-
- }
-
- private Set<HNode> getSkeleteNodeSetReachTo(HNode node) {
+ public Set<HNode> getSkeleteNodeSetReachTo(HNode node) {
Set<HNode> reachToSet = new HashSet<HNode>();
Set<HNode> visited = new HashSet<HNode>();
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);
// + tempSet);
if (reachToSet.size() > 1) {
// if (countSkeletonNodes(reachToSet) > 1) {
- // System.out.println("-node=" + node + " reachToSet=" + reachToSet);
- // System.out.println("-set combinationnode=" + node);
+ System.out.println("-node=" + node + " reachToSet=" + reachToSet);
+ System.out.println("-set combinationnode=" + node);
node.setCombinationNode(true);
mapCombinationNodeToCombineNodeSet.put(node, reachToSet);
+
+ // check if this node is the first node of the chain
+ boolean isFirstNodeOfChain = false;
+ Set<HNode> inNodeSet = getIncomingNodeSet(node);
+ for (Iterator iterator2 = inNodeSet.iterator(); iterator2.hasNext();) {
+ HNode inNode = (HNode) iterator2.next();
+ if (inNode.isSkeleton()) {
+ isFirstNodeOfChain = true;
+ } else if (inNode.isCombinationNode()) {
+ Set<HNode> inNodeReachToSet = getSkeleteNodeSetReachTo(inNode);
+ if (!reachToSet.equals(inNodeReachToSet)) {
+ isFirstNodeOfChain = true;
+ }
+ }
+ }
+
+ if (isFirstNodeOfChain) {
+ node.setDirectCombinationNode(true);
+ addFirstNodeOfChain(reachToSet, node);
+ // System.out.println("IT IS DIRECTLY CONNECTED WITH SC NODES:" + node);
+ }
+
}
}
}
}
+ public void addFirstNodeOfChain(Set<HNode> combineSet, HNode firstNode) {
+
+ if (!mapCombineNodeSetToFirstNodeOfChainSet.containsKey(combineSet)) {
+ mapCombineNodeSetToFirstNodeOfChainSet.put(combineSet, new HashSet<HNode>());
+ }
+
+ mapCombineNodeSetToFirstNodeOfChainSet.get(combineSet).add(firstNode);
+
+ }
+
+ public Set<HNode> getFirstNodeOfCombinationNodeChainSet(Set<HNode> combineNodeSet) {
+ return mapCombineNodeSetToFirstNodeOfChainSet.get(combineNodeSet);
+ }
+
private Set<HNode> removeTransitivelyReachToSet(Set<HNode> reachToSet) {
Set<HNode> toberemoved = new HashSet<HNode>();
return max;
}
+ public int countNonSharedNode(HNode startNode, Set<HNode> endNodeSet) {
+ System.out.println("countNonSharedNode startNode=" + startNode + " endNode=" + endNodeSet);
+ return recur_countNonSharedNode(startNode, endNodeSet, 0);
+ }
+
+ private int recur_countNonSharedNode(HNode startNode, Set<HNode> endNodeSet, int count) {
+
+ Set<HNode> inNodeSet = getIncomingNodeSet(startNode);
+
+ if (inNodeSet.size() == 0) {
+ // it is directly connected to the TOP node
+ }
+
+ for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
+ HNode inNode = (HNode) iterator.next();
+ if (endNodeSet.contains(inNode)) {
+ return count;
+ } else {
+ if (!inNode.isSharedNode()) {
+ count++;
+ }
+ return recur_countNonSharedNode(inNode, endNodeSet, count);
+ }
+ }
+
+ // System.out.println("startNode=" + startNode + " inNodeSet=" + inNodeSet);
+ // HNode inNode = inNodeSet.iterator().next();
+ return -1;
+ }
}
// HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(key);
HierarchyGraph scHierarchyGraph = getSkeletonCombinationHierarchyGraph(key);
if (key instanceof ClassDescriptor) {
- // writeInferredLatticeDotFile((ClassDescriptor) key, scHierarchyGraph, simpleLattice,
- // "_SIMPLE");
+ writeInferredLatticeDotFile((ClassDescriptor) key, simpleLattice, "_SIMPLE");
} else if (key instanceof MethodDescriptor) {
MethodDescriptor md = (MethodDescriptor) key;
- // writeInferredLatticeDotFile(md.getClassDesc(), md, scHierarchyGraph, simpleLattice,
- // "_SIMPLE");
+ writeInferredLatticeDotFile(md.getClassDesc(), md, simpleLattice, "_SIMPLE");
}
LocationSummary ls = getLocationSummary(key);
// + simpleHierarchyGraph.getName());
SSJavaLattice<String> lattice =
buildLattice.insertIntermediateNodesToStraightLine(desc, simpleLattice);
+
+ if (lattice == null) {
+ return;
+ }
lattice.removeRedundantEdges();
LocationInference.numLocationsSInfer += lattice.getKeySet().size();
Set<T> connectedSet = get(higher);
if (connectedSet == null) {
connectedSet = new HashSet<T>();
- }else{
+ } else {
connectedSet.removeAll(lowerSet);
}
connectedSet.add(newLoc);
}
}
+
+
public SSJavaLattice<T> clone() {
SSJavaLattice<T> clone = new SSJavaLattice<T>(getTopItem(), getBottomItem());
}
public boolean put(T key, T value) {
+
+ if(isGreaterThan(key, value)){
+ // this relation already exists
+ return false;
+ }
+
Set<T> s;
Set<T> topNeighbor = table.get(top);
-
if (table.containsKey(key)) {
s = table.get(key);
} else {
}
// if value is already connected with top, it is no longer to be
- topNeighbor.remove(value);
+ if(!key.equals(top)){
+ topNeighbor.remove(value);
+ }
+
// if key is already connected with bottom,, it is no longer to be
if (!value.equals(getBottomItem())) {
projects / IRC.git / commitdiff