From cbc13efe1afc46ef542fde526361b4911d3da0e1 Mon Sep 17 00:00:00 2001 From: yeom Date: Sat, 16 Feb 2013 02:08:57 +0000 Subject: [PATCH] changes. --- Robust/src/Analysis/SSJava/BuildLattice.java | 238 ++++++++++++++++++ Robust/src/Analysis/SSJava/HNode.java | 12 + .../src/Analysis/SSJava/HierarchyGraph.java | 161 +++++++----- .../Analysis/SSJava/LocationInference.java | 10 +- Robust/src/Analysis/SSJava/SSJavaLattice.java | 4 +- Robust/src/Util/Lattice.java | 12 +- 6 files changed, 366 insertions(+), 71 deletions(-) diff --git a/Robust/src/Analysis/SSJava/BuildLattice.java b/Robust/src/Analysis/SSJava/BuildLattice.java index 754db088..7a38272d 100644 --- a/Robust/src/Analysis/SSJava/BuildLattice.java +++ b/Robust/src/Analysis/SSJava/BuildLattice.java @@ -224,6 +224,244 @@ public class BuildLattice { public SSJavaLattice insertIntermediateNodesToStraightLine(Descriptor desc, SSJavaLattice skeletonLattice) { + + SSJavaLattice lattice = skeletonLattice.clone(); + LocationSummary locSummary = infer.getLocationSummary(desc); + + Descriptor parentDesc = getParent(desc); + if (parentDesc != null) { + SSJavaLattice parentLattice = infer.getLattice(parentDesc); + + Map> parentMap = parentLattice.getTable(); + Set parentKeySet = parentMap.keySet(); + for (Iterator iterator = parentKeySet.iterator(); iterator.hasNext();) { + String parentKey = (String) iterator.next(); + Set parentValueSet = parentMap.get(parentKey); + for (Iterator iterator2 = parentValueSet.iterator(); iterator2.hasNext();) { + String value = (String) iterator2.next(); + lattice.put(parentKey, value); + } + } + + Set 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 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 combineSet = hierarchyGraph.getCombineSetByCombinationNode(hNode); + SCNode = scGraph.getCombinationNode(combineSet); + numNonSharedNodes = -1; + } else { + + Set aboveSet = new HashSet(); + if (hNode.isCombinationNode()) { + Set 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 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 lattice, String start, Set 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 lattice, String cur, + Set endSet, int dist, boolean isShared) { + Set connectedSet = lattice.get(cur); + if (connectedSet == null) { + connectedSet = new HashSet(); + } + + 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 insertIntermediateNodesToStraightLine2(Descriptor desc, + SSJavaLattice skeletonLattice) { // copy nodes/edges from the parent method/class if possible SSJavaLattice lattice = skeletonLattice.clone(); diff --git a/Robust/src/Analysis/SSJava/HNode.java b/Robust/src/Analysis/SSJava/HNode.java index 67133fb8..a565f2bd 100644 --- a/Robust/src/Analysis/SSJava/HNode.java +++ b/Robust/src/Analysis/SSJava/HNode.java @@ -12,11 +12,15 @@ public class HNode { 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() { @@ -66,6 +70,14 @@ public class HNode { 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; diff --git a/Robust/src/Analysis/SSJava/HierarchyGraph.java b/Robust/src/Analysis/SSJava/HierarchyGraph.java index f7919be7..ed82566e 100644 --- a/Robust/src/Analysis/SSJava/HierarchyGraph.java +++ b/Robust/src/Analysis/SSJava/HierarchyGraph.java @@ -38,6 +38,8 @@ public class HierarchyGraph { Map> mapNormalNodeToSCNodeReachToSet; + Map, Set> mapCombineNodeSetToFirstNodeOfChainSet; + Set nodeSet; // for the lattice generation @@ -66,6 +68,8 @@ public class HierarchyGraph { mapHNodeNameToCurrentHNode = new HashMap(); mapNormalNodeToSCNodeReachToSet = new HashMap>(); + + mapCombineNodeSetToFirstNodeOfChainSet = new HashMap, Set>(); } public Descriptor getDesc() { @@ -153,7 +157,7 @@ public class HierarchyGraph { } // System.out.println("--- CYCLIC VALUE FLOW: " + srcHNode + " -> " + dstHNode); - HNode newMergeNode = mergeNodes(possibleCycleSet, false); + HNode newMergeNode = mergeNodes(possibleCycleSet); newMergeNode.setSharedNode(true); } else { @@ -300,14 +304,14 @@ public class HierarchyGraph { 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); } @@ -325,12 +329,16 @@ public class HierarchyGraph { 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; } @@ -340,8 +348,12 @@ public class HierarchyGraph { 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; } @@ -368,7 +380,7 @@ public class HierarchyGraph { // /////////////// - mergeNodes(mergeSet, onlyCombinationNodes); + mergeNodes(mergeSet); return true; } @@ -407,7 +419,7 @@ public class HierarchyGraph { // System.out.println("addEdgeWithNoCycleCheck src=" + srcHNode + " -> " + dstHNode); } - private HNode mergeNodes(Set set, boolean onlyCombinationNodes) { + private HNode mergeNodes(Set set) { Set incomingNodeSet = new HashSet(); Set outgoingNodeSet = new HashSet(); @@ -420,12 +432,9 @@ public class HierarchyGraph { 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); @@ -782,12 +791,13 @@ public class HierarchyGraph { Set> keySet = simpleHierarchyGraph.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 + " 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(); @@ -827,32 +837,7 @@ public class HierarchyGraph { } - private void addCombinationNode(HNode curNode, Set reachToSet, Set 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 getSkeleteNodeSetReachTo(HNode node) { + public Set getSkeleteNodeSetReachTo(HNode node) { Set reachToSet = new HashSet(); Set visited = new HashSet(); @@ -867,23 +852,6 @@ public class HierarchyGraph { 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); @@ -984,10 +952,32 @@ public class HierarchyGraph { // + 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 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 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); + } + } } } @@ -1004,6 +994,20 @@ public class HierarchyGraph { } + public void addFirstNodeOfChain(Set combineSet, HNode firstNode) { + + if (!mapCombineNodeSetToFirstNodeOfChainSet.containsKey(combineSet)) { + mapCombineNodeSetToFirstNodeOfChainSet.put(combineSet, new HashSet()); + } + + mapCombineNodeSetToFirstNodeOfChainSet.get(combineSet).add(firstNode); + + } + + public Set getFirstNodeOfCombinationNodeChainSet(Set combineNodeSet) { + return mapCombineNodeSetToFirstNodeOfChainSet.get(combineNodeSet); + } + private Set removeTransitivelyReachToSet(Set reachToSet) { Set toberemoved = new HashSet(); @@ -1348,4 +1352,33 @@ public class HierarchyGraph { return max; } + public int countNonSharedNode(HNode startNode, Set endNodeSet) { + System.out.println("countNonSharedNode startNode=" + startNode + " endNode=" + endNodeSet); + return recur_countNonSharedNode(startNode, endNodeSet, 0); + } + + private int recur_countNonSharedNode(HNode startNode, Set endNodeSet, int count) { + + Set 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; + } } diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index b2bd43fc..caa4504a 100644 --- a/Robust/src/Analysis/SSJava/LocationInference.java +++ b/Robust/src/Analysis/SSJava/LocationInference.java @@ -2556,12 +2556,10 @@ public class LocationInference { // 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); @@ -2614,6 +2612,10 @@ public class LocationInference { // + simpleHierarchyGraph.getName()); SSJavaLattice lattice = buildLattice.insertIntermediateNodesToStraightLine(desc, simpleLattice); + + if (lattice == null) { + return; + } lattice.removeRedundantEdges(); LocationInference.numLocationsSInfer += lattice.getKeySet().size(); diff --git a/Robust/src/Analysis/SSJava/SSJavaLattice.java b/Robust/src/Analysis/SSJava/SSJavaLattice.java index c9ab0aa1..ae875777 100644 --- a/Robust/src/Analysis/SSJava/SSJavaLattice.java +++ b/Robust/src/Analysis/SSJava/SSJavaLattice.java @@ -325,7 +325,7 @@ public class SSJavaLattice extends Lattice { Set connectedSet = get(higher); if (connectedSet == null) { connectedSet = new HashSet(); - }else{ + } else { connectedSet.removeAll(lowerSet); } connectedSet.add(newLoc); @@ -336,6 +336,8 @@ public class SSJavaLattice extends Lattice { } } + + public SSJavaLattice clone() { SSJavaLattice clone = new SSJavaLattice(getTopItem(), getBottomItem()); diff --git a/Robust/src/Util/Lattice.java b/Robust/src/Util/Lattice.java index aea74773..b76b7bb0 100644 --- a/Robust/src/Util/Lattice.java +++ b/Robust/src/Util/Lattice.java @@ -66,10 +66,15 @@ public class Lattice { } public boolean put(T key, T value) { + + if(isGreaterThan(key, value)){ + // this relation already exists + return false; + } + Set s; Set topNeighbor = table.get(top); - if (table.containsKey(key)) { s = table.get(key); } else { @@ -90,7 +95,10 @@ public class Lattice { } // 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())) { -- 2.34.1