From 03f449200cf7e78de07f884509619d0e37edfacf Mon Sep 17 00:00:00 2001 From: yeom Date: Mon, 15 Oct 2012 02:42:50 +0000 Subject: [PATCH] changes: fix all problems of mapping between a flow node/hierarchy node to a lattice element --- Robust/src/Analysis/SSJava/BuildLattice.java | 103 +++++++++++------- .../src/Analysis/SSJava/HierarchyGraph.java | 45 ++++++-- .../Analysis/SSJava/LocationInference.java | 18 ++- 3 files changed, 110 insertions(+), 56 deletions(-) diff --git a/Robust/src/Analysis/SSJava/BuildLattice.java b/Robust/src/Analysis/SSJava/BuildLattice.java index b3cdd8ae..780819f4 100644 --- a/Robust/src/Analysis/SSJava/BuildLattice.java +++ b/Robust/src/Analysis/SSJava/BuildLattice.java @@ -12,7 +12,6 @@ import Util.Pair; public class BuildLattice { - public static int seed = 0; private LocationInference infer; private final HNode topNode; @@ -162,9 +161,11 @@ public class BuildLattice { Map mapIntermediateLoc = new HashMap(); + System.out.println("*insert=" + desc); + System.out.println("***nodeSet=" + nodeSet); for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { HNode node = (HNode) iterator.next(); - // System.out.println("node=" + node); + System.out.println("node=" + node); if (node.isSkeleton() && (!visited.contains(node))) { visited.add(node); @@ -174,38 +175,8 @@ public class BuildLattice { if (!outNode.isSkeleton()) { if (outNode.isCombinationNode()) { - // expand the combination node 'outNode' - // here we need to expand the corresponding combination location in the lattice - HNode combinationNodeInSCGraph = getCombinationNodeInSCGraph(desc, outNode); - Set combineSkeletonNodeSet = - simpleGraph.getCombineSetByCombinationNode(outNode); - - // System.out.println("combineSkeletonNodeSet=" + combineSkeletonNodeSet); - - Set combinationNodeSet = - simpleGraph.getCombinationNodeSetByCombineNodeSet(combineSkeletonNodeSet); - - // System.out.println("combinationNodeSet=" + combinationNodeSet); - - Set endNodeSetFromSimpleGraph = - simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(outNode, - combinationNodeSet); - // System.out.println("-endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph); - 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) { - endCombNodeSet = - removeTransitivelyReachToNode(desc, combinationNodeInSCGraph, endCombNodeSet); - recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited, - mapIntermediateLoc, 1, locSummary, outNode); - } + expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode); } else { // we have a node that is neither combination or skeleton node @@ -248,9 +219,15 @@ public class BuildLattice { } } + } else if (!node.isSkeleton() && node.isCombinationNode()) { + + expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, node); + } else if (!node.isSkeleton() && !node.isCombinationNode() && !node.isMergeNode() && !visited.contains(node)) { + System.out.println("n=" + node); + // an intermediate node 'node' may be located between "TOP" location and a skeleton node int sizeIncomingNode = simpleGraph.getIncomingNodeSet(node).size(); @@ -285,6 +262,45 @@ public class BuildLattice { } + private void expandCombinationNode(Descriptor desc, SSJavaLattice lattice, + Set visited, Map mapIntermediateLoc, LocationSummary locSummary, + HNode cnode) { + + // expand the combination node 'outNode' + // here we need to expand the corresponding combination location in the lattice + HNode combinationNodeInSCGraph = getCombinationNodeInSCGraph(desc, cnode); + + HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc); + + Set combineSkeletonNodeSet = simpleGraph.getCombineSetByCombinationNode(cnode); + + // System.out.println("combineSkeletonNodeSet=" + combineSkeletonNodeSet); + + Set combinationNodeSet = + simpleGraph.getCombinationNodeSetByCombineNodeSet(combineSkeletonNodeSet); + + // System.out.println("combinationNodeSet=" + combinationNodeSet); + + Set endNodeSetFromSimpleGraph = + simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(cnode, combinationNodeSet); + // System.out.println("-endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph); + Set endCombNodeSet = new HashSet(); + for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) { + HNode endNode = (HNode) iterator3.next(); + endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode)); + } + visited.add(cnode); + + // follows the straight line up to another skeleton/combination node + if (endCombNodeSet.size() > 0) { + endCombNodeSet = + removeTransitivelyReachToNode(desc, combinationNodeInSCGraph, endCombNodeSet); + recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited, + mapIntermediateLoc, 1, locSummary, cnode); + } + + } + private Set removeTransitivelyReachToNode(Descriptor desc, HNode startNode, Set endNodeSet) { @@ -315,8 +331,15 @@ public class BuildLattice { private HNode getDirectlyReachableNodeFromStartNodeReachToEndNode(HierarchyGraph scGraph, HNode startNode, HNode endNode) { + System.out.println("getDirectlyReachableNodeFromStartNodeReachToEndNode start=" + startNode + + " end=" + endNode); Set connected = new HashSet(); recurDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, endNode, connected); + if (connected.size() == 0) { + connected.add(endNode); + } + System.out.println("connected=" + connected); + return connected.iterator().next(); } @@ -329,7 +352,6 @@ public class BuildLattice { if (inNode.equals(startNode)) { connected.add(curNode); } else { - // System.out.println("inNode=" + inNode); recurDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, inNode, connected); } } @@ -344,7 +366,7 @@ public class BuildLattice { // System.out.println("item=" + item); if (!mapIntermediateLoc.containsKey(item)) { // need to create a new intermediate location in the lattice - String newLocName = "ILOC" + (seed++); + String newLocName = "ILOC" + (LocationInference.locSeed++); String above; if (idx == 1) { above = startNode.getName(); @@ -366,6 +388,7 @@ public class BuildLattice { } String locName = mapIntermediateLoc.get(item); + HierarchyGraph graph = infer.getSimpleHierarchyGraph(desc); Set descSet = graph.getDescSetOfNode(curNode); @@ -373,7 +396,8 @@ public class BuildLattice { Descriptor d = (Descriptor) iterator.next(); locSummary.addMapHNodeNameToLocationName(d.getSymbol(), locName); } - // locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName); + locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName); + Set outSet = graph.getOutgoingNodeSet(curNode); for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) { @@ -382,6 +406,8 @@ public class BuildLattice { visited.add(outNode); recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc, idx + 1, locSummary, outNode); + } else if (!outNode.isSkeleton() && outNode.isCombinationNode() && !visited.contains(outNode)) { + expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode); } } @@ -400,7 +426,7 @@ public class BuildLattice { String newLocName = combinationNodeInSCGraph.getName(); mapIntermediateLoc.put(item, newLocName); } else { - String newLocName = "ILOC" + (seed++); + String newLocName = "ILOC" + (LocationInference.locSeed++); int prevIdx = idx - 1; TripleItem prevItem = new TripleItem(combinationNodeInSCGraph, endNodeSet, prevIdx); above = mapIntermediateLoc.get(prevItem); @@ -424,6 +450,7 @@ public class BuildLattice { Descriptor d = (Descriptor) iterator.next(); locSummary.addMapHNodeNameToLocationName(d.getSymbol(), locName); } + locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName); // System.out.println("-TripleItem=" + item); // System.out.println("-curNode=" + curNode.getName() + " locName=" + locName); @@ -457,7 +484,7 @@ public class BuildLattice { if (inputGraph.BASISTOPELEMENT.equals(F)) { return SSJavaAnalysis.BOTTOM; } else { - String str = "LOC" + (seed++); + String str = "LOC" + (LocationInference.locSeed++); mapF2LocName.put(F, str); return str; } diff --git a/Robust/src/Analysis/SSJava/HierarchyGraph.java b/Robust/src/Analysis/SSJava/HierarchyGraph.java index d575f4f4..6a12849f 100644 --- a/Robust/src/Analysis/SSJava/HierarchyGraph.java +++ b/Robust/src/Analysis/SSJava/HierarchyGraph.java @@ -26,6 +26,8 @@ public class HierarchyGraph { Map mapDescToHNode; Map> mapHNodeToDescSet; Map mapHNodeToCurrentHNode; // tracking which node corresponds to the initial node + Map mapHNodeNameToCurrentHNode; // tracking which node corresponds to the initial + // node Map> mapMergeNodetoMergingSet; // data structures for a combination node @@ -36,8 +38,6 @@ public class HierarchyGraph { Set nodeSet; - public static int seed = 0; - // for the lattice generation Map mapHNodeToUniqueIndex; Map> mapHNodeToBasis; @@ -61,6 +61,8 @@ public class HierarchyGraph { mapHNodeToCurrentHNode = new HashMap(); + mapHNodeNameToCurrentHNode = new HashMap(); + } public Descriptor getDesc() { @@ -97,10 +99,18 @@ public class HierarchyGraph { return mapHNodeToCurrentHNode; } + public Map getMapHNodeNameToCurrentHNode() { + return mapHNodeNameToCurrentHNode; + } + public void setMapHNodeToCurrentHNode(Map mapHNodeToCurrentHNode) { this.mapHNodeToCurrentHNode = mapHNodeToCurrentHNode; } + public void setMapHNodeNameToCurrentHNode(Map mapHNodeNameToCurrentHNode) { + this.mapHNodeNameToCurrentHNode = mapHNodeNameToCurrentHNode; + } + public Map getMapDescToHNode() { return mapDescToHNode; } @@ -139,11 +149,11 @@ public class HierarchyGraph { HNode newMergeNode = mergeNodes(possibleCycleSet, false); newMergeNode.setSharedNode(true); System.out.println("### INTRODUCE A NEW MERGE NODE: " + newMergeNode); - System.out.println("### CYCLIC VALUE FLOW: " + srcHNode + " -> " + dstHNode); + System.out.println("### CYCLIC VALUE FLOW: " + srcHNode + " -> " + dstHNode + "\n"); } else { getIncomingNodeSet(dstHNode).add(srcHNode); getOutgoingNodeSet(srcHNode).add(dstHNode); - System.out.println("add an edge " + srcHNode + " -> " + dstHNode); + // System.out.println("add an edge " + srcHNode + " -> " + dstHNode); } } @@ -388,9 +398,9 @@ public class HierarchyGraph { String nodeName; boolean isMergeNode = false; if (onlyCombinationNodes) { - nodeName = "Comb" + (seed++); + nodeName = "Comb" + (LocationInference.locSeed++); } else { - nodeName = "Node" + (seed++); + nodeName = "Node" + (LocationInference.locSeed++); isMergeNode = true; } HNode newMergeNode = new HNode(nodeName); @@ -409,7 +419,7 @@ public class HierarchyGraph { } } System.out.println("--Set merging node=" + newMergeNode + " as a skeleton=" + set - + " hasSkeleton=" + hasSkeleton); + + " hasSkeleton=" + hasSkeleton + " CUR DESC=" + desc); newMergeNode.setSkeleton(hasSkeleton); for (Iterator iterator = set.iterator(); iterator.hasNext();) { @@ -446,12 +456,15 @@ public class HierarchyGraph { mergedSkeletonNode.add(merged); } } - mapMergeNodetoMergingSet.put(newMergeNode, mergedSkeletonNode); - for (Iterator iterator = mergedSkeletonNode.iterator(); iterator.hasNext();) { + + // mapMergeNodetoMergingSet.put(newMergeNode, mergedSkeletonNode); + // for (Iterator iterator = set.iterator(); iterator.hasNext();) { + mapMergeNodetoMergingSet.put(newMergeNode, set); + for (Iterator iterator = set.iterator(); iterator.hasNext();) { HNode mergedNode = (HNode) iterator.next(); addMapHNodeToCurrentHNode(mergedNode, newMergeNode); } - System.out.println("\n###mergedSkeletonNode=" + mergedSkeletonNode); + System.out.println("###mergedSkeletonNode=" + mergedSkeletonNode); System.out.println("###MERGING NODE=" + set + " new node=" + newMergeNode); for (Iterator iterator = set.iterator(); iterator.hasNext();) { @@ -471,9 +484,11 @@ public class HierarchyGraph { for (Iterator iterator = mergingSet.iterator(); iterator.hasNext();) { HNode mergingNode = (HNode) iterator.next(); mapHNodeToCurrentHNode.put(mergingNode, newNode); + mapHNodeNameToCurrentHNode.put(mergingNode.getName(), newNode); } } else { mapHNodeToCurrentHNode.put(curNode, newNode); + mapHNodeNameToCurrentHNode.put(curNode.getName(), newNode); } } @@ -484,6 +499,10 @@ public class HierarchyGraph { return mapHNodeToCurrentHNode.get(node); } + public HNode getCurrentHNode(String nodeName) { + return mapHNodeNameToCurrentHNode.get(nodeName); + } + private Set getMergingSet(HNode mergeNode) { Set mergingSet = new HashSet(); Set mergedNode = mapMergeNodetoMergingSet.get(mergeNode); @@ -643,7 +662,7 @@ public class HierarchyGraph { public HNode getCombinationNode(Set combineSet) { if (!mapCombineNodeSetToCombinationNode.containsKey(combineSet)) { - String name = "COMB" + (seed++); + String name = "COMB" + (LocationInference.locSeed++); HNode node = new HNode(name); node.setCombinationNode(true); nodeSet.add(node); @@ -715,7 +734,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" + (seed++); + String nodeName = "Comb" + (LocationInference.locSeed++); HNode newCombinationNode = new HNode(nodeName); newCombinationNode.setCombinationNode(true); @@ -832,6 +851,8 @@ public class HierarchyGraph { clone.setMapHNodeToDescSet(getMapHNodeToDescSet()); clone.setMapHNodetoMergeSet(getMapHNodetoMergeSet()); clone.setMapHNodeToCurrentHNode(getMapHNodeToCurrentHNode()); + clone.setMapHNodeNameToCurrentHNode(getMapHNodeNameToCurrentHNode()); + return clone; } diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index 34c1df96..dbcc415d 100644 --- a/Robust/src/Analysis/SSJava/LocationInference.java +++ b/Robust/src/Analysis/SSJava/LocationInference.java @@ -140,7 +140,7 @@ public class LocationInference { boolean debug = true; - private static int locSeed = 0; + public static int locSeed = 0; public LocationInference(SSJavaAnalysis ssjava, State state) { this.ssjava = ssjava; @@ -350,6 +350,14 @@ public class LocationInference { String locName; if (!enclosingDesc.equals(GLOBALDESC)) { LocationSummary locSummary = getLocationSummary(enclosingDesc); + HierarchyGraph hierarchyGraph = getSimpleHierarchyGraph(enclosingDesc); + if (hierarchyGraph != null) { + + HNode curNode = hierarchyGraph.getCurrentHNode(nodeIdentifier); + if (curNode != null) { + nodeIdentifier = curNode.getName(); + } + } locName = locSummary.getLocationName(nodeIdentifier); } else { locName = nodeIdentifier; @@ -363,7 +371,6 @@ public class LocationInference { private void translateCompositeLocationAssignmentToFlowGraph(MethodDescriptor mdCaller) { - // First, assign a composite location to a node in the flow graph GlobalFlowGraph callerGlobalFlowGraph = getSubGlobalFlowGraph(mdCaller); @@ -499,8 +506,8 @@ public class LocationInference { } } - System.out.println("-----*AFTER TRANSLATING COMP LOC MAPPING, CALLEE MAPPING=" - + calleeGlobalGraph.getMapLocationToInferCompositeLocation()); + // System.out.println("-----*AFTER TRANSLATING COMP LOC MAPPING, CALLEE MAPPING=" + // + calleeGlobalGraph.getMapLocationToInferCompositeLocation()); // If the location of an argument has a composite location // need to assign a proper composite location to the corresponding callee parameter @@ -1723,6 +1730,7 @@ public class LocationInference { NTuple srcCurTuple = srcNode.getCurrentDescTuple(); NTuple dstCurTuple = dstNode.getCurrentDescTuple(); + if ((srcCurTuple.size() > 1 && dstCurTuple.size() > 1) && srcCurTuple.get(0).equals(dstCurTuple.get(0))) { @@ -2961,7 +2969,6 @@ public class LocationInference { private void propagateFlowsToCallerWithNoCompositeLocation(MethodInvokeNode min, MethodDescriptor mdCaller, MethodDescriptor mdCallee) { - // if the parameter A reaches to the parameter B // then, add an edge the argument A -> the argument B to the caller's flow // graph @@ -4484,7 +4491,6 @@ public class LocationInference { argTuple = new NTuple(); } - addArgIdxMap(min, idx, argTuple); FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx); -- 2.34.1