From ec795f9b357096a8a74b539b3a3057b325bfa7f3 Mon Sep 17 00:00:00 2001 From: yeom Date: Sat, 29 Sep 2012 00:56:43 +0000 Subject: [PATCH] changes. --- Robust/src/Analysis/SSJava/BuildLattice.java | 183 ++++- Robust/src/Analysis/SSJava/FieldSummary.java | 5 + Robust/src/Analysis/SSJava/FlowGraph.java | 136 +++- Robust/src/Analysis/SSJava/FlowNode.java | 40 +- Robust/src/Analysis/SSJava/HNode.java | 14 + .../src/Analysis/SSJava/HierarchyGraph.java | 156 +++- .../Analysis/SSJava/LocationDescriptor.java | 12 +- .../Analysis/SSJava/LocationInference.java | 766 +++++++++++++++--- .../src/Analysis/SSJava/LocationSummary.java | 29 + Robust/src/Analysis/SSJava/MethodSummary.java | 32 +- 10 files changed, 1190 insertions(+), 183 deletions(-) create mode 100644 Robust/src/Analysis/SSJava/FieldSummary.java create mode 100644 Robust/src/Analysis/SSJava/LocationSummary.java diff --git a/Robust/src/Analysis/SSJava/BuildLattice.java b/Robust/src/Analysis/SSJava/BuildLattice.java index eca8dfaa..264699c3 100644 --- a/Robust/src/Analysis/SSJava/BuildLattice.java +++ b/Robust/src/Analysis/SSJava/BuildLattice.java @@ -18,7 +18,10 @@ public class BuildLattice { this.infer = infer; } - public SSJavaLattice buildLattice(HierarchyGraph inputGraph) { + public SSJavaLattice buildLattice(Descriptor desc) { + + HierarchyGraph inputGraph = infer.getSkeletonCombinationHierarchyGraph(desc); + LocationSummary locSummary = infer.getLocationSummary(desc); BasisSet basisSet = inputGraph.computeBasisSet(); debug_print(inputGraph); @@ -26,13 +29,13 @@ public class BuildLattice { Family family = generateFamily(basisSet); Map, Set>> mapImSucc = coveringGraph(basisSet, family); - SSJavaLattice lattice = buildLattice(basisSet, inputGraph, mapImSucc); + SSJavaLattice lattice = buildLattice(basisSet, inputGraph, locSummary, mapImSucc); return lattice; } private SSJavaLattice buildLattice(BasisSet basisSet, HierarchyGraph inputGraph, - Map, Set>> mapImSucc) { + LocationSummary locSummary, Map, Set>> mapImSucc) { SSJavaLattice lattice = new SSJavaLattice(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM); @@ -44,12 +47,24 @@ public class BuildLattice { Set higher = (Set) iterator.next(); String higherName = generateElementName(basisSet, inputGraph, mapFToLocName, higher); + locSummary.addMapHNodeNameToLocationName(higherName, higherName); + + HNode higherNode = inputGraph.getHNode(higherName); + if (higherNode != null && higherNode.isSharedNode()) { + lattice.addSharedLoc(higherName); + } Set> lowerSet = mapImSucc.get(higher); for (Iterator iterator2 = lowerSet.iterator(); iterator2.hasNext();) { Set lower = (Set) iterator2.next(); String lowerName = generateElementName(basisSet, inputGraph, mapFToLocName, lower); + locSummary.addMapHNodeNameToLocationName(lowerName, lowerName); + + HNode lowerNode = inputGraph.getHNode(higherName); + if (lowerNode != null && lowerNode.isSharedNode()) { + lattice.addSharedLoc(lowerName); + } if (higher.size() == 0) { // empty case @@ -65,12 +80,24 @@ public class BuildLattice { return lattice; } - public HNode getCombinationNodeInSCGraph(Descriptor desc, HNode simpleGraphNode) { + public HNode getCombinationNodeInSCGraph(Descriptor desc, HNode nodeFromSimpleGraph) { + + HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc); + + if (nodeFromSimpleGraph.isSkeleton()) { + return scGraph.getCurrentHNode(nodeFromSimpleGraph); + } Set combineSkeletonNodeSet = - infer.getSimpleHierarchyGraph(desc).getCombineSetByCombinationNode(simpleGraphNode); + infer.getSimpleHierarchyGraph(desc).getCombineSetByCombinationNode(nodeFromSimpleGraph); HNode combinationNodeInSCGraph = - infer.getSkeletonCombinationHierarchyGraph(desc).getCombinationNode(combineSkeletonNodeSet); + infer.getSkeletonCombinationHierarchyGraph(desc).getMapCombineNodeSetToCombinationNode() + .get(combineSkeletonNodeSet); + + // Set combineSkeletonNodeSet = + // infer.getSimpleHierarchyGraph(desc).getCombineSetByCombinationNode(simpleGraphNode); + // HNode combinationNodeInSCGraph = + // infer.getSkeletonCombinationHierarchyGraph(desc).getCombinationNode(combineSkeletonNodeSet); return combinationNodeInSCGraph; } @@ -82,16 +109,14 @@ public class BuildLattice { HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc); HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc); + LocationSummary locSummary = infer.getLocationSummary(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(); @@ -104,34 +129,62 @@ public class BuildLattice { if (!outNode.isSkeleton()) { if (outNode.isCombinationNode()) { + // expand the combination node 'outNode' + System.out.println("-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)); } + System.out.println("-endCombNodeSet=" + endCombNodeSet); 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, outNode); + mapIntermediateLoc, 1, locSummary, outNode); + // recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited, + // mapIntermediateLoc, 1, locSummary, outNode); } } else { // we have a node that is neither combination or skeleton node - HNode startNode = node; + System.out.println("skeleton node=" + node + " outNode=" + outNode); + HNode startNode = scGraph.getCurrentHNode(node); + + // if (node.getDescriptor() != null) { + // // node is a skeleton node and it might be merged into another node in the SC + // graph. + // startNode = scGraph.getHNode(node.getDescriptor()); + // } else { + // // this node has already been merged before the SC graph. + // startNode = node; + // } + Set endNodeSetFromSimpleGraph = simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(outNode, null); + System.out.println("endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph + + " from=" + outNode); Set endCombNodeSet = new HashSet(); for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) { HNode endNode = (HNode) iterator3.next(); @@ -141,16 +194,30 @@ public class BuildLattice { visited.add(outNode); if (endCombNodeSet.size() > 0) { // follows the straight line up to another skeleton/combination node + endCombNodeSet = removeTransitivelyReachToNode(desc, startNode, endCombNodeSet); recurDFSNormalNode(desc, lattice, startNode, endCombNodeSet, visited, - mapIntermediateLoc, 1, outNode); - + mapIntermediateLoc, 1, locSummary, outNode); } - } } } + } else if (!node.isSkeleton() && !node.isCombinationNode() && !node.isMergeNode() + && !visited.contains(node)) { + // an intermediate node 'node' is located between "TOP" location and a skeleton node + + Set outNodeSet = simpleGraph.getOutgoingNodeSet(node); + Set belowSkeletonLocNameSet = new HashSet(); + for (Iterator iterator2 = outNodeSet.iterator(); iterator2.hasNext();) { + HNode outNode = (HNode) iterator2.next(); + if (outNode.isSkeleton()) { + belowSkeletonLocNameSet.add(scGraph.getCurrentHNode(outNode).getName()); + } + } + String newLocName = "ILOC" + (seed++); + lattice.insertNewLocationBetween(lattice.getTopItem(), belowSkeletonLocNameSet, newLocName); + locSummary.addMapHNodeNameToLocationName(node.getName(), newLocName); } } @@ -158,12 +225,62 @@ public class BuildLattice { } + private Set removeTransitivelyReachToNode(Descriptor desc, HNode startNode, + Set endNodeSet) { + + // if an end node is not directly connected to the start node in the SC graph + // replace it with a directly connected one which transitively reaches to it. + + HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc); + Set newEndNodeSet = new HashSet(); + + for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) { + HNode endNode = (HNode) iterator.next(); + if (scGraph.isDirectlyConnectedTo(startNode, endNode)) { + newEndNodeSet.add(endNode); + } else { + HNode newEndNode = + getDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, endNode); + System.out.println("#### old END NODE=" + endNode + " --->" + newEndNode); + newEndNodeSet.add(newEndNode); + } + } + + System.out.println("removeTransitivelyReachToNode=" + endNodeSet + " newSet=" + newEndNodeSet); + + return newEndNodeSet; + + } + + private HNode getDirectlyReachableNodeFromStartNodeReachToEndNode(HierarchyGraph scGraph, + HNode startNode, HNode endNode) { + Set connected = new HashSet(); + recurDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, endNode, connected); + return connected.iterator().next(); + } + + private void recurDirectlyReachableNodeFromStartNodeReachToEndNode(HierarchyGraph scGraph, + HNode startNode, HNode curNode, Set connected) { + + Set inNodeSet = scGraph.getIncomingNodeSet(curNode); + for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) { + HNode inNode = (HNode) iterator.next(); + if (inNode.equals(startNode)) { + connected.add(curNode); + } else { + System.out.println("inNode=" + inNode); + recurDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, inNode, connected); + } + } + + } + private void recurDFSNormalNode(Descriptor desc, SSJavaLattice lattice, HNode startNode, Set endNodeSet, Set visited, Map mapIntermediateLoc, - int idx, HNode curNode) { + int idx, LocationSummary locSummary, HNode curNode) { TripleItem item = new TripleItem(startNode, endNodeSet, idx); - + System.out.println("item=" + item); if (!mapIntermediateLoc.containsKey(item)) { // need to create a new intermediate location in the lattice String newLocName = "ILOC" + (seed++); @@ -188,6 +305,7 @@ public class BuildLattice { } String locName = mapIntermediateLoc.get(item); + locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName); HierarchyGraph graph = infer.getSimpleHierarchyGraph(desc); Set outSet = graph.getOutgoingNodeSet(curNode); @@ -196,7 +314,7 @@ public class BuildLattice { if (!outNode.isSkeleton() && !outNode.isCombinationNode() && !visited.contains(outNode)) { visited.add(outNode); recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc, - idx + 1, outNode); + idx + 1, locSummary, outNode); } } @@ -204,34 +322,39 @@ public class BuildLattice { private void recurDFS(Descriptor desc, SSJavaLattice lattice, HNode combinationNodeInSCGraph, Set endNodeSet, Set visited, - Map mapIntermediateLoc, int idx, HNode curNode) { + Map mapIntermediateLoc, int idx, LocationSummary locSummary, 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(); + String newLocName = combinationNodeInSCGraph.getName(); + mapIntermediateLoc.put(item, newLocName); } else { + String newLocName = "ILOC" + (seed++); 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()); + 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); + } - lattice.insertNewLocationBetween(above, belowSet, newLocName); - mapIntermediateLoc.put(item, newLocName); + } - String locName = mapIntermediateLoc.get(item); + String locName = mapIntermediateLoc.get(item); + locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName); - } + System.out.println("-TripleItem=" + item); + System.out.println("-curNode=" + curNode.getName() + " locName=" + locName); HierarchyGraph graph = infer.getSimpleHierarchyGraph(desc); Set outSet = graph.getOutgoingNodeSet(curNode); @@ -241,7 +364,7 @@ public class BuildLattice { if (combinationNodeInSCGraph.equals(getCombinationNodeInSCGraph(desc, outNode))) { visited.add(outNode); recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited, - mapIntermediateLoc, idx + 1, outNode); + mapIntermediateLoc, idx + 1, locSummary, outNode); } } } diff --git a/Robust/src/Analysis/SSJava/FieldSummary.java b/Robust/src/Analysis/SSJava/FieldSummary.java new file mode 100644 index 00000000..ab5a7b1b --- /dev/null +++ b/Robust/src/Analysis/SSJava/FieldSummary.java @@ -0,0 +1,5 @@ +package Analysis.SSJava; + +public class FieldSummary extends LocationSummary { + +} diff --git a/Robust/src/Analysis/SSJava/FlowGraph.java b/Robust/src/Analysis/SSJava/FlowGraph.java index 44a859ba..0655c5fa 100644 --- a/Robust/src/Analysis/SSJava/FlowGraph.java +++ b/Robust/src/Analysis/SSJava/FlowGraph.java @@ -21,21 +21,22 @@ public class FlowGraph { MethodDescriptor md; Set nodeSet; + Set returnNodeSet; FlowNode thisVarNode; + Map> mapFlowNodeToOutEdgeSet; + Map, FlowNode> mapLocTupleToFlowNode; Map> mapFlowNodeToLocTuple; // maps the composite representation of field/var descriptors to infer nodes Map, FlowNode> mapDescTupleToInferNode; - // maps an infer node to the set of neighbors which is pointed by the node - Map, Set> mapNodeToNeighborSet; - // maps a paramter descriptor to its index Map mapParamDescToIdx; + // DS for the lattice generation Map mapIdxToFlowNode; public static int interseed = 0; @@ -48,11 +49,11 @@ public class FlowGraph { this.mapLocTupleToFlowNode = new HashMap, FlowNode>(); this.nodeSet = new HashSet(); this.mapDescTupleToInferNode = new HashMap, FlowNode>(); - this.mapNodeToNeighborSet = new HashMap, Set>(); this.mapParamDescToIdx = new HashMap(); this.mapParamDescToIdx.putAll(mapParamDescToIdx); this.returnNodeSet = new HashSet(); this.mapIdxToFlowNode = new HashMap(); + this.mapFlowNodeToOutEdgeSet = new HashMap>(); if (!md.isStatic()) { // create a node for 'this' varialbe @@ -70,6 +71,34 @@ public class FlowGraph { } + public Map, FlowNode> getMapDescTupleToInferNode() { + return mapDescTupleToInferNode; + } + + public void setMapDescTupleToInferNode(Map, FlowNode> in) { + this.mapDescTupleToInferNode.putAll(in); + } + + public Map, FlowNode> getMapLocTupleToFlowNode() { + return mapLocTupleToFlowNode; + } + + public void setMapLocTupleToFlowNode(Map, FlowNode> in) { + this.mapLocTupleToFlowNode.putAll(in); + } + + public void setNodeSet(Set in) { + this.nodeSet.addAll(in); + } + + public void setReturnNodeSet(Set in) { + this.returnNodeSet.addAll(in); + } + + public void setThisVarNode(FlowNode thisVarNode) { + this.thisVarNode = thisVarNode; + } + public Map getMapParamDescToIdx() { return mapParamDescToIdx; } @@ -122,16 +151,6 @@ public class FlowGraph { return md; } - public void addNeighbor(FlowNode node, FlowNode neighbor) { - Set set = mapNodeToNeighborSet.get(node); - if (set == null) { - set = new HashSet(); - } - set.add(neighbor); - - // System.out.println("add a new neighbor " + neighbor + " to " + node); - } - public boolean isParamDesc(Descriptor desc) { if (mapParamDescToIdx.containsKey(desc)) { @@ -150,7 +169,7 @@ public class FlowGraph { FlowNode fromNode = mapDescTupleToInferNode.get(fromDescTuple); FlowNode toNode = mapDescTupleToInferNode.get(toDescTuple); - Set fromNodeOutEdgeSet = fromNode.getOutEdgeSet(); + Set fromNodeOutEdgeSet = getOutEdgeSet(fromNode); for (Iterator iterator = fromNodeOutEdgeSet.iterator(); iterator.hasNext();) { FlowEdge flowEdge = (FlowEdge) iterator.next(); if (flowEdge.getDst().equals(toNode)) { @@ -165,6 +184,13 @@ public class FlowGraph { return false; } + public Set getOutEdgeSet(FlowNode node) { + if (!mapFlowNodeToOutEdgeSet.containsKey(node)) { + mapFlowNodeToOutEdgeSet.put(node, new HashSet()); + } + return mapFlowNodeToOutEdgeSet.get(node); + } + public void addValueFlowEdge(NTuple fromDescTuple, NTuple toDescTuple) { FlowNode fromNode = getFlowNode(fromDescTuple); @@ -208,9 +234,16 @@ public class FlowGraph { NTuple endTuple) { FlowEdge edge = new FlowEdge(fromNode, toNode, initTuple, endTuple); - fromNode.addOutEdge(edge); + addOutEdge(fromNode, edge); + + // System.out.println("add a new edge=" + edge); + } - System.out.println("add a new edge=" + edge); + private void addOutEdge(FlowNode fromNode, FlowEdge edge) { + if (!mapFlowNodeToOutEdgeSet.containsKey(fromNode)) { + mapFlowNodeToOutEdgeSet.put(fromNode, new HashSet()); + } + mapFlowNodeToOutEdgeSet.get(fromNode).add(edge); } public FlowNode getFlowNode(NTuple descTuple) { @@ -271,7 +304,8 @@ public class FlowGraph { private void recurLocalReachFlowNodeSet(FlowNode fn, Set visited) { - for (Iterator iterator = fn.getOutEdgeSet().iterator(); iterator.hasNext();) { + Set outEdgeSet = getOutEdgeSet(fn); + for (Iterator iterator = outEdgeSet.iterator(); iterator.hasNext();) { FlowEdge edge = (FlowEdge) iterator.next(); FlowNode dstNode = edge.getDst(); @@ -285,7 +319,8 @@ public class FlowGraph { private void getReachFlowNodeSetFrom(FlowNode fn, Set visited) { - for (Iterator iterator = fn.getOutEdgeSet().iterator(); iterator.hasNext();) { + Set outEdgeSet = getOutEdgeSet(fn); + for (Iterator iterator = outEdgeSet.iterator(); iterator.hasNext();) { FlowEdge edge = (FlowEdge) iterator.next(); if (fn.equals(getFlowNode(edge.getInitTuple()))) { @@ -325,7 +360,10 @@ public class FlowGraph { // } public Set> getReachableFlowTupleSet(Set> visited, FlowNode fn) { - for (Iterator iterator = fn.getOutEdgeSet().iterator(); iterator.hasNext();) { + + Set outEdgeSet = getOutEdgeSet(fn); + + for (Iterator iterator = outEdgeSet.iterator(); iterator.hasNext();) { FlowEdge edge = (FlowEdge) iterator.next(); if (fn.getDescTuple().equals(edge.getInitTuple())) { @@ -379,7 +417,13 @@ public class FlowGraph { } else { loc = new Location(cd, curDesc.getSymbol()); loc.setLocDescriptor(curDesc); - cd = ((FieldDescriptor) curDesc).getType().getClassDesc(); + + if (curDesc instanceof FieldDescriptor) { + cd = ((FieldDescriptor) curDesc).getType().getClassDesc(); + } else { + cd = ((LocationDescriptor) curDesc).getEnclosingClassDesc(); + } + } locTuple.add(loc); } @@ -400,7 +444,7 @@ public class FlowGraph { for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { FlowNode curNode = (FlowNode) iterator.next(); - Set edgeSet = curNode.getOutEdgeSet(); + Set edgeSet = getOutEdgeSet(curNode); for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) { FlowEdge flowEdge = (FlowEdge) iterator2.next(); @@ -428,7 +472,8 @@ public class FlowGraph { for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { FlowNode node = (FlowNode) iterator.next(); - Set edgeSet = node.getOutEdgeSet(); + + Set edgeSet = getOutEdgeSet(node); for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) { FlowEdge flowEdge = (FlowEdge) iterator2.next(); if (dstTuple.equals(flowEdge.getEndTuple())) { @@ -459,10 +504,47 @@ public class FlowGraph { return mapParamDescToIdx.containsKey(firstIdxDesc); } + public FlowGraph clone() { + FlowGraph clone = new FlowGraph(md, mapParamDescToIdx); + + clone.setNodeSet(getNodeSet()); + clone.setMapLocTupleToFlowNode(getMapLocTupleToFlowNode()); + clone.setMapFlowNodeToLocTuple(getMapFlowNodeToLocTuple()); + clone.setMapDescTupleToInferNode(getMapDescTupleToInferNode()); + + clone.setMapFlowNodeToOutEdgeSet(getMapFlowNodeToOutEdgeSet()); + clone.setReturnNodeSet(getReturnNodeSet()); + clone.setThisVarNode(getThisVarNode()); + + return clone; + } + + public Map> getMapFlowNodeToLocTuple() { + return mapFlowNodeToLocTuple; + } + + public void setMapFlowNodeToLocTuple(Map> in) { + this.mapFlowNodeToLocTuple.putAll(in); + } + + public Map> getMapFlowNodeToOutEdgeSet() { + return mapFlowNodeToOutEdgeSet; + } + + public void setMapFlowNodeToOutEdgeSet(Map> inMap) { + Set keySet = inMap.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + FlowNode key = (FlowNode) iterator.next(); + Set newEdgeSet = new HashSet(); + newEdgeSet.addAll(inMap.get(key)); + mapFlowNodeToOutEdgeSet.put(key, newEdgeSet); + } + } + private void drawEdges(FlowNode node, BufferedWriter bw, Set addedNodeSet, Set addedEdgeSet) throws IOException { - Set edgeSet = node.getOutEdgeSet(); + Set edgeSet = getOutEdgeSet(node); for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) { FlowEdge flowEdge = iterator.next(); @@ -499,8 +581,12 @@ public class FlowGraph { } public void writeGraph() throws java.io.IOException { + writeGraph(""); + } + + public void writeGraph(String suffix) throws java.io.IOException { - String graphName = "flowgraph_" + md.toString(); + String graphName = "flowgraph_" + md.toString() + suffix; graphName = graphName.replaceAll("[\\W]", ""); BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot")); diff --git a/Robust/src/Analysis/SSJava/FlowNode.java b/Robust/src/Analysis/SSJava/FlowNode.java index b71789ae..51f1b08d 100644 --- a/Robust/src/Analysis/SSJava/FlowNode.java +++ b/Robust/src/Analysis/SSJava/FlowNode.java @@ -40,8 +40,6 @@ public class FlowNode { return fieldNodeSet; } - private Set outEdgeSet; - public FlowNode(NTuple tuple) { this.isSkeleton = false; @@ -63,7 +61,6 @@ public class FlowNode { if (desc != null) { descTuple.add(desc); } - outEdgeSet = new HashSet(); } @@ -114,17 +111,17 @@ public class FlowNode { return rtr; } - public Iterator iteratorOfOutEdges() { - return outEdgeSet.iterator(); - } - - public void addOutEdge(FlowEdge out) { - outEdgeSet.add(out); - } - - public Set getOutEdgeSet() { - return outEdgeSet; - } +// public Iterator iteratorOfOutEdges() { +// return outEdgeSet.iterator(); +// } +// +// public void addOutEdge(FlowEdge out) { +// outEdgeSet.add(out); +// } +// +// public Set getOutEdgeSet() { +// return outEdgeSet; +// } public int hashCode() { return 7 + descTuple.hashCode(); @@ -153,6 +150,7 @@ public class FlowNode { public String getPrettyID() { String id = "<"; + String property = ""; for (int i = 0; i < descTuple.size(); i++) { if (i != 0) { id += ","; @@ -165,7 +163,19 @@ public class FlowNode { id += " " + compLoc; } - return id; + if (isReturn()) { + property += "R"; + } + + if (isSkeleton()) { + property += "S"; + } + + if (property.length() > 0) { + property = " [" + property + "]"; + } + + return id + property; } public void setDeclarationNode() { diff --git a/Robust/src/Analysis/SSJava/HNode.java b/Robust/src/Analysis/SSJava/HNode.java index 62bae954..67133fb8 100644 --- a/Robust/src/Analysis/SSJava/HNode.java +++ b/Robust/src/Analysis/SSJava/HNode.java @@ -10,11 +10,21 @@ public class HNode { private boolean isSkeleton; private boolean isCombinationNode; private boolean isSharedNode; + private boolean isMergeNode; public HNode() { this.isSkeleton = false; this.isCombinationNode = false; this.isSharedNode = false; + this.isMergeNode = false; + } + + public boolean isMergeNode() { + return isMergeNode; + } + + public void setMergeNode(boolean isMergeNode) { + this.isMergeNode = isMergeNode; } public HNode(String name) { @@ -66,6 +76,10 @@ public class HNode { return false; } + public String getNamePropertyString() { + return toString().substring(1, toString().length() - 1); + } + public String toString() { String properties = ""; diff --git a/Robust/src/Analysis/SSJava/HierarchyGraph.java b/Robust/src/Analysis/SSJava/HierarchyGraph.java index 52eb8742..852206af 100644 --- a/Robust/src/Analysis/SSJava/HierarchyGraph.java +++ b/Robust/src/Analysis/SSJava/HierarchyGraph.java @@ -17,14 +17,22 @@ public class HierarchyGraph { Descriptor desc; String name; - Map mapDescToHNode; - Map> mapHNodeToDescSet; + + // graph structure Map> mapHNodeToIncomingSet; Map> mapHNodeToOutgoingSet; + + Map mapDescToHNode; + Map> mapHNodeToDescSet; + Map mapHNodeToCurrentHNode; // tracking which node corresponds to the initial node + Map> mapMergeNodetoMergingSet; + + // data structures for a combination node Map, HNode> mapSkeletonNodeSetToCombinationNode; Map> mapCombinationNodeToCombineNodeSet; Map, HNode> mapCombineNodeSetToCombinationNode; Map, Set> mapCombineNodeSetToOutgoingNodeSet; + Map mapHNodeToLocationName; Set nodeSet; @@ -51,6 +59,9 @@ public class HierarchyGraph { mapHNodeToBasis = new HashMap>(); mapHNodeToLocationName = new HashMap(); + mapMergeNodetoMergingSet = new HashMap>(); + + mapHNodeToCurrentHNode = new HashMap(); } @@ -92,6 +103,14 @@ public class HierarchyGraph { mapHNodeToDescSet.putAll(map); } + public Map getMapHNodeToCurrentHNode() { + return mapHNodeToCurrentHNode; + } + + public void setMapHNodeToCurrentHNode(Map mapHNodeToCurrentHNode) { + this.mapHNodeToCurrentHNode = mapHNodeToCurrentHNode; + } + public Map getMapDescToHNode() { return mapDescToHNode; } @@ -121,8 +140,10 @@ public class HierarchyGraph { if (possibleCycleSet.size() == 1) { if (dstHNode.isSharedNode()) { // it has already been assigned shared node. - return; + } else { + dstHNode.setSharedNode(true); } + return; } HNode newMergeNode = mergeNodes(possibleCycleSet, false); @@ -165,6 +186,16 @@ public class HierarchyGraph { return mapDescToHNode.get(d); } + public HNode getHNode(String name) { + for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + HNode node = (HNode) iterator.next(); + if (node.getName().equals(name)) { + return node; + } + } + return null; + } + private void mappingDescriptorToHNode(Descriptor desc, HNode node) { mapDescToHNode.put(desc, node); if (!mapHNodeToDescSet.containsKey(node)) { @@ -196,6 +227,8 @@ public class HierarchyGraph { skeletonGraph.setMapDescToHNode(getMapDescToHNode()); skeletonGraph.setMapHNodeToDescSet(getMapHNodeToDescSet()); + skeletonGraph.setMapHNodetoMergeSet(getMapHNodetoMergeSet()); + skeletonGraph.setMapHNodeToCurrentHNode(getMapHNodeToCurrentHNode()); return skeletonGraph; @@ -259,7 +292,7 @@ public class HierarchyGraph { } while (isUpdated); } - private Set getIncomingNodeSet(HNode node) { + public Set getIncomingNodeSet(HNode node) { if (!mapHNodeToIncomingSet.containsKey(node)) { mapHNodeToIncomingSet.put(node, new HashSet()); } @@ -334,12 +367,15 @@ public class HierarchyGraph { } String nodeName; + boolean isMergeNode = false; if (onlyCombinationNodes) { nodeName = "Comb" + (seed++); } else { nodeName = "Node" + (seed++); + isMergeNode = true; } HNode newMergeNode = new HNode(nodeName); + newMergeNode.setMergeNode(isMergeNode); nodeSet.add(newMergeNode); nodeSet.removeAll(set); @@ -384,10 +420,56 @@ public class HierarchyGraph { } } + Set mergedSkeletonNode = new HashSet(); + for (Iterator iter = set.iterator(); iter.hasNext();) { + HNode merged = iter.next(); + if (merged.isSkeleton()) { + mergedSkeletonNode.add(merged); + } + } + mapMergeNodetoMergingSet.put(newMergeNode, mergedSkeletonNode); + for (Iterator iterator = mergedSkeletonNode.iterator(); iterator.hasNext();) { + HNode mergedNode = (HNode) iterator.next(); + addMapHNodeToCurrentHNode(mergedNode, newMergeNode); + } + System.out.println("###MERGING NODE=" + set + " new node=" + newMergeNode); return newMergeNode; } + private void addMapHNodeToCurrentHNode(HNode curNode, HNode newNode) { + if (curNode.isMergeNode()) { + Set mergingSet = getMergingSet(curNode); + for (Iterator iterator = mergingSet.iterator(); iterator.hasNext();) { + HNode mergingNode = (HNode) iterator.next(); + mapHNodeToCurrentHNode.put(mergingNode, newNode); + } + } else { + mapHNodeToCurrentHNode.put(curNode, newNode); + } + } + + public HNode getCurrentHNode(HNode node) { + if (!mapHNodeToCurrentHNode.containsKey(node)) { + mapHNodeToCurrentHNode.put(node, node); + } + return mapHNodeToCurrentHNode.get(node); + } + + private Set getMergingSet(HNode mergeNode) { + Set mergingSet = new HashSet(); + Set mergedNode = mapMergeNodetoMergingSet.get(mergeNode); + for (Iterator iterator = mergedNode.iterator(); iterator.hasNext();) { + HNode node = (HNode) iterator.next(); + if (node.isMergeNode()) { + mergingSet.addAll(getMergingSet(node)); + } else { + mergingSet.add(node); + } + } + return mergingSet; + } + private Set getDescSetOfNode(HNode node) { if (!mapHNodeToDescSet.containsKey(node)) { mapHNodeToDescSet.put(node, new HashSet()); @@ -543,16 +625,20 @@ public class HierarchyGraph { return mapCombineNodeSetToCombinationNode.get(combineSet); } + public Map, HNode> getMapCombineNodeSetToCombinationNode() { + return mapCombineNodeSetToCombinationNode; + } + public Set> getCombineNodeSet() { return mapCombineNodeSetToOutgoingNodeSet.keySet(); } - public void insertCombinationNodesToGraph(HierarchyGraph hierarchyGraph) { + public void insertCombinationNodesToGraph(HierarchyGraph simpleHierarchyGraph) { // add a new combination node where parameter/field flows are actually combined. - hierarchyGraph.identifyCombinationNodes(); + simpleHierarchyGraph.identifyCombinationNodes(); - Set> keySet = hierarchyGraph.getCombineNodeSet(); + Set> keySet = simpleHierarchyGraph.getCombineNodeSet(); for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { Set combineSet = (Set) iterator.next(); System.out.println("--combineSet=" + combineSet); @@ -575,15 +661,17 @@ public class HierarchyGraph { } // add an edge from the combination node to outgoing nodes - Set outSet = hierarchyGraph.getOutgoingNodeSetByCombineSet(combineSet); + Set outSet = simpleHierarchyGraph.getOutgoingNodeSetByCombineSet(combineSet); for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) { HNode curNode = (HNode) iterator2.next(); if (curNode.isCombinationNode()) { - Set combineNode = hierarchyGraph.getCombineSetByCombinationNode(curNode); + Set combineNode = simpleHierarchyGraph.getCombineSetByCombinationNode(curNode); HNode outNode = getCombinationNode(combineNode); addEdgeWithNoCycleCheck(combinationNode, outNode); } else if (curNode.isSkeleton()) { - addEdgeWithNoCycleCheck(combinationNode, curNode); + // HNode dstNode = getHNode(curNode.getDescriptor()); + HNode dstNode = getCurrentHNode(curNode); + addEdgeWithNoCycleCheck(combinationNode, dstNode); } } @@ -711,10 +799,19 @@ public class HierarchyGraph { clone.setMapHNodeToOutgoingSet(getMapHNodeToOutgoingSet()); clone.setMapDescToHNode(getMapDescToHNode()); clone.setMapHNodeToDescSet(getMapHNodeToDescSet()); - + clone.setMapHNodetoMergeSet(getMapHNodetoMergeSet()); + clone.setMapHNodeToCurrentHNode(getMapHNodeToCurrentHNode()); return clone; } + public Map> getMapHNodetoMergeSet() { + return mapMergeNodetoMergingSet; + } + + public void setMapHNodetoMergeSet(Map> mapHNodetoMergeSet) { + this.mapMergeNodetoMergingSet = mapHNodetoMergeSet; + } + public Set getOutgoingNodeSetByCombineSet(Set combineSet) { if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) { @@ -730,8 +827,8 @@ public class HierarchyGraph { HNode node = (HNode) iterator.next(); if (!node.isSkeleton()) { Set reachToSet = getSkeleteNodeSetReachTo(node); - // if (reachToSet.size() > 1) { - if (countSkeletonNodes(reachToSet) > 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); @@ -870,6 +967,7 @@ public class HierarchyGraph { basis.remove(getHNodeIndex(node)); for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) { HNode reachableNode = (HNode) iterator2.next(); + System.out.println("reachableNode=" + reachableNode); int idx = getHNodeIndex(reachableNode); basis.remove(idx); } @@ -968,10 +1066,36 @@ public class HierarchyGraph { } } + public boolean contains(HNode node) { + return nodeSet.contains(node); + } + + public boolean isDirectlyConnectedTo(HNode src, HNode dst) { + return getOutgoingNodeSet(src).contains(dst); + } + + private String convertMergeSetToString(Set mergeSet) { + String str = ""; + for (Iterator iterator = mergeSet.iterator(); iterator.hasNext();) { + HNode merged = (HNode) iterator.next(); + if (merged.isMergeNode()) { + str += " " + convertMergeSetToString(mapMergeNodetoMergingSet.get(merged)); + } else { + str += " " + merged.getName(); + } + } + return str; + } + private void drawNode(BufferedWriter bw, HNode node) throws IOException { - String nodeName = node.toString(); - nodeName = nodeName.substring(1, nodeName.length() - 1); + String nodeName; + if (node.isMergeNode()) { + nodeName = node.getNamePropertyString(); + Set mergeSet = mapMergeNodetoMergingSet.get(node); + nodeName += ":" + convertMergeSetToString(mergeSet); + } else { + nodeName = node.getNamePropertyString(); + } bw.write(node.getName() + " [label=\"" + nodeName + "\"]" + ";\n"); } - } diff --git a/Robust/src/Analysis/SSJava/LocationDescriptor.java b/Robust/src/Analysis/SSJava/LocationDescriptor.java index ed2497d1..03eb3542 100644 --- a/Robust/src/Analysis/SSJava/LocationDescriptor.java +++ b/Robust/src/Analysis/SSJava/LocationDescriptor.java @@ -1,12 +1,22 @@ package Analysis.SSJava; +import IR.ClassDescriptor; import IR.Descriptor; public class LocationDescriptor extends Descriptor { + ClassDescriptor enclosingDesc; + public LocationDescriptor(String name) { super(name); } - + + public void setEnclosingClassDesc(ClassDescriptor en) { + enclosingDesc = en; + } + + public ClassDescriptor getEnclosingClassDesc() { + return enclosingDesc; + } } diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index e1524c25..148733af 100644 --- a/Robust/src/Analysis/SSJava/LocationInference.java +++ b/Robust/src/Analysis/SSJava/LocationInference.java @@ -58,10 +58,12 @@ public class LocationInference { State state; SSJavaAnalysis ssjava; - List toanalyzeList; - List toanalyzeMethodList; + List temp_toanalyzeList; + List temp_toanalyzeMethodList; Map mapMethodDescriptorToFlowGraph; + LinkedList toanalyze_methodDescList; + // map a method descriptor to its set of parameter descriptors Map> mapMethodDescriptorToParamDescSet; @@ -85,9 +87,6 @@ public class LocationInference { // map a method/class descriptor to a skeleton hierarchy graph with combination nodes private Map mapDescriptorToCombineSkeletonHierarchyGraph; - // map a method descriptor to a method summary - private Map mapMethodDescToMethodSummary; - // map a descriptor to a simple lattice private Map> mapDescriptorToSimpleLattice; @@ -111,6 +110,12 @@ public class LocationInference { private Map mapDescToDefinitionLine; + private Map mapDescToLocationSummary; + + // maps a method descriptor to a sub global flow graph that captures all value flows caused by the + // set of callees reachable from the method + private Map mapMethodDescriptorToSubGlobalFlowGraph; + public static final String GLOBALLOC = "GLOBALLOC"; public static final String TOPLOC = "TOPLOC"; @@ -132,8 +137,8 @@ public class LocationInference { public LocationInference(SSJavaAnalysis ssjava, State state) { this.ssjava = ssjava; this.state = state; - this.toanalyzeList = new ArrayList(); - this.toanalyzeMethodList = new ArrayList(); + this.temp_toanalyzeList = new ArrayList(); + this.temp_toanalyzeMethodList = new ArrayList(); this.mapMethodDescriptorToFlowGraph = new HashMap(); this.cd2lattice = new HashMap>(); this.md2lattice = new HashMap>(); @@ -152,7 +157,6 @@ public class LocationInference { new HashMap>(); this.mapDescriptorToHierarchyGraph = new HashMap(); - this.mapMethodDescToMethodSummary = new HashMap(); this.mapMethodInvokeNodeToBaseTuple = new HashMap>(); this.mapDescriptorToSkeletonHierarchyGraph = new HashMap(); @@ -161,12 +165,16 @@ public class LocationInference { this.mapDescriptorToSimpleLattice = new HashMap>(); + this.mapDescToLocationSummary = new HashMap(); + + mapMethodDescriptorToSubGlobalFlowGraph = new HashMap(); + } public void setupToAnalyze() { SymbolTable classtable = state.getClassSymbolTable(); - toanalyzeList.clear(); - toanalyzeList.addAll(classtable.getValueSet()); + temp_toanalyzeList.clear(); + temp_toanalyzeList.addAll(classtable.getValueSet()); // Collections.sort(toanalyzeList, new Comparator() { // public int compare(ClassDescriptor o1, ClassDescriptor o2) { // return o1.getClassName().compareToIgnoreCase(o2.getClassName()); @@ -177,9 +185,9 @@ public class LocationInference { public void setupToAnalazeMethod(ClassDescriptor cd) { SymbolTable methodtable = cd.getMethodTable(); - toanalyzeMethodList.clear(); - toanalyzeMethodList.addAll(methodtable.getValueSet()); - Collections.sort(toanalyzeMethodList, new Comparator() { + temp_toanalyzeMethodList.clear(); + temp_toanalyzeMethodList.addAll(methodtable.getValueSet()); + Collections.sort(temp_toanalyzeMethodList, new Comparator() { public int compare(MethodDescriptor o1, MethodDescriptor o2) { return o1.getSymbol().compareToIgnoreCase(o2.getSymbol()); } @@ -187,19 +195,19 @@ public class LocationInference { } public boolean toAnalyzeMethodIsEmpty() { - return toanalyzeMethodList.isEmpty(); + return temp_toanalyzeMethodList.isEmpty(); } public boolean toAnalyzeIsEmpty() { - return toanalyzeList.isEmpty(); + return temp_toanalyzeList.isEmpty(); } public ClassDescriptor toAnalyzeNext() { - return toanalyzeList.remove(0); + return temp_toanalyzeList.remove(0); } public MethodDescriptor toAnalyzeMethodNext() { - return toanalyzeMethodList.remove(0); + return temp_toanalyzeMethodList.remove(0); } public void inference() { @@ -207,6 +215,10 @@ public class LocationInference { // 1) construct value flow graph constructFlowGraph(); + constructGlobalFlowGraph(); + + System.exit(0); + constructHierarchyGraph(); debug_writeHierarchyDotFiles(); @@ -227,6 +239,8 @@ public class LocationInference { debug_writeLattices(); + generateMethodSummary(); + System.exit(0); // 2) construct lattices @@ -247,30 +261,253 @@ public class LocationInference { } + private void constructGlobalFlowGraph() { + + System.out.println(""); + LinkedList methodDescList = + (LinkedList) toanalyze_methodDescList.clone(); + + System.out.println("@@@methodDescList=" + methodDescList); + // System.exit(0); + + while (!methodDescList.isEmpty()) { + MethodDescriptor md = methodDescList.removeLast(); + if (state.SSJAVADEBUG) { + System.out.println(); + System.out.println("SSJAVA: Constructing a global flow graph: " + md); + + FlowGraph flowGraph = getFlowGraph(md); + FlowGraph subGlobalFlowGraph = flowGraph.clone(); + mapMethodDescriptorToSubGlobalFlowGraph.put(md, subGlobalFlowGraph); + + addValueFlowsFromCalleeSubGlobalFlowGraph(md, subGlobalFlowGraph); + + try { + subGlobalFlowGraph.writeGraph("_SUBGLOBAL"); + } catch (IOException e) { + e.printStackTrace(); + } + // FlowGraph fg = new FlowGraph(md, mapParamDescToIdx); + // mapMethodDescriptorToFlowGraph.put(md, fg); + // analyzeMethodBody(md.getClassDesc(), md); + + } + } + // _debug_printGraph(); + + } + + private void addValueFlowsFromCalleeSubGlobalFlowGraph(MethodDescriptor mdCaller, + FlowGraph subGlobalFlowGraph) { + + // the transformation for a call site propagates flows through parameters + // if the method is virtual, it also grab all relations from any possible + // callees + + Set setMethodInvokeNode = getMethodInvokeNodeSet(mdCaller); + + for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) { + MethodInvokeNode min = (MethodInvokeNode) iterator.next(); + MethodDescriptor mdCallee = min.getMethod(); + Set setPossibleCallees = new HashSet(); + if (mdCallee.isStatic()) { + setPossibleCallees.add(mdCallee); + } else { + Set calleeSet = ssjava.getCallGraph().getMethods(mdCallee); + // removes method descriptors that are not invoked by the caller + calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller)); + setPossibleCallees.addAll(calleeSet); + } + + for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) { + MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next(); + propagateValueFlowsToCallerFromSubGlobalFlowGraph(min, mdCaller, possibleMdCallee); + // propagateFlowsToCallerWithNoCompositeLocation(min, mdCaller, possibleMdCallee); + } + + } + + } + + private void propagateValueFlowsToCallerFromSubGlobalFlowGraph(MethodInvokeNode min, + MethodDescriptor mdCaller, MethodDescriptor possibleMdCallee) { + + NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); + + FlowGraph callerSubGlobalGraph = getSubGlobalFlowGraph(mdCaller); + FlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(possibleMdCallee); + + int numParam = calleeSubGlobalGraph.getNumParameters(); + for (int idx = 0; idx < numParam; idx++) { + FlowNode paramNode = calleeSubGlobalGraph.getParamFlowNode(idx); + NodeTupleSet argTupleSet = mapMethodInvokeNodeToArgIdxMap.get(min).get(idx); + System.out.println("argTupleSet=" + argTupleSet + " param=" + paramNode); + for (Iterator> iter = argTupleSet.iterator(); iter.hasNext();) { + NTuple argTuple = iter.next(); + addValueFlowsFromCalleeParam(calleeSubGlobalGraph, paramNode, callerSubGlobalGraph, + argTuple, baseTuple); + } + } + + } + + private void addValueFlowsFromCalleeParam(FlowGraph calleeSubGlobalGraph, FlowNode paramNode, + FlowGraph callerSubGlobalGraph, NTuple argTuple, NTuple baseTuple) { + + Set visited = new HashSet(); + + visited.add(paramNode); + recurAddValueFlowsFromCalleeParam(calleeSubGlobalGraph, paramNode, callerSubGlobalGraph, + argTuple, visited, baseTuple); + } + + private void recurAddValueFlowsFromCalleeParam(FlowGraph calleeSubGlobalGraph, + FlowNode calleeSrcNode, FlowGraph callerSubGlobalGraph, NTuple callerSrcTuple, + Set visited, NTuple baseTuple) { + + MethodDescriptor mdCallee = calleeSubGlobalGraph.getMethodDescriptor(); + + Set edgeSet = calleeSubGlobalGraph.getOutEdgeSet(calleeSrcNode); + for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) { + FlowEdge flowEdge = (FlowEdge) iterator.next(); + FlowNode dstNode = flowEdge.getDst(); + + NTuple dstDescTuple = dstNode.getCurrentDescTuple(); + if (dstDescTuple.get(0).equals(mdCallee.getThis())) { + // destination node is started with 'this' variable + // need to translate it in terms of the caller's base node + dstDescTuple = translateToCaller(dstDescTuple, baseTuple); + } + + callerSubGlobalGraph.addValueFlowEdge(callerSrcTuple, dstDescTuple); + + if (!visited.contains(dstNode)) { + visited.add(dstNode); + recurAddValueFlowsFromCalleeParam(calleeSubGlobalGraph, dstNode, callerSubGlobalGraph, + dstDescTuple, visited, baseTuple); + } + + } + + } + + private NTuple translateToCaller(NTuple dstDescTuple, + NTuple baseTuple) { + NTuple callerDescTuple = new NTuple(); + + callerDescTuple.addAll(baseTuple); + for (int i = 1; i < dstDescTuple.size(); i++) { + callerDescTuple.add(dstDescTuple.get(i)); + } + + return callerDescTuple; + } + + public LocationSummary getLocationSummary(Descriptor d) { + if (!mapDescToLocationSummary.containsKey(d)) { + if (d instanceof MethodDescriptor) { + mapDescToLocationSummary.put(d, new MethodSummary((MethodDescriptor) d)); + } else if (d instanceof ClassDescriptor) { + mapDescToLocationSummary.put(d, new FieldSummary()); + } + } + return mapDescToLocationSummary.get(d); + } + + private void generateMethodSummary() { + + Set keySet = md2lattice.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + MethodDescriptor md = (MethodDescriptor) iterator.next(); + + System.out.println("\nSSJAVA: generate method summary: " + md); + + FlowGraph flowGraph = getFlowGraph(md); + MethodSummary methodSummary = getMethodSummary(md); + + // construct a parameter mapping that maps a parameter descriptor to an inferred composite + // location + + for (int paramIdx = 0; paramIdx < flowGraph.getNumParameters(); paramIdx++) { + FlowNode flowNode = flowGraph.getParamFlowNode(paramIdx); + NTuple descTuple = flowNode.getDescTuple(); + + CompositeLocation assignedCompLoc = flowNode.getCompositeLocation(); + CompositeLocation inferredCompLoc; + if (assignedCompLoc != null) { + inferredCompLoc = translateCompositeLocation(assignedCompLoc); + } else { + Descriptor locDesc = descTuple.get(0); + Location loc = new Location(md, locDesc.getSymbol()); + loc.setLocDescriptor(locDesc); + inferredCompLoc = new CompositeLocation(loc); + } + System.out.println("-paramIdx=" + paramIdx + " infer=" + inferredCompLoc); + methodSummary.addMapParamIdxToInferLoc(paramIdx, inferredCompLoc); + } + + } + + } + + private CompositeLocation translateCompositeLocation(CompositeLocation compLoc) { + CompositeLocation newCompLoc = new CompositeLocation(); + + // System.out.println("compLoc=" + compLoc); + for (int i = 0; i < compLoc.getSize(); i++) { + Location loc = compLoc.get(i); + Descriptor enclosingDescriptor = loc.getDescriptor(); + Descriptor locDescriptor = loc.getLocDescriptor(); + + HNode hnode = getHierarchyGraph(enclosingDescriptor).getHNode(locDescriptor); + // System.out.println("-hnode=" + hnode + " from=" + locDescriptor + + // " enclosingDescriptor=" + // + enclosingDescriptor); + // System.out.println("-getLocationSummary(enclosingDescriptor)=" + // + getLocationSummary(enclosingDescriptor)); + String locName = getLocationSummary(enclosingDescriptor).getLocationName(hnode.getName()); + // System.out.println("-locName=" + locName); + Location newLoc = new Location(enclosingDescriptor, locName); + newLoc.setLocDescriptor(locDescriptor); + newCompLoc.addLocation(newLoc); + } + + return newCompLoc; + } + 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); + // HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(key); + HierarchyGraph scHierarchyGraph = getSkeletonCombinationHierarchyGraph(key); if (key instanceof ClassDescriptor) { - ssjava.writeLatticeDotFile((ClassDescriptor) key, null, simpleLattice, "_SIMPLE"); + writeInferredLatticeDotFile((ClassDescriptor) key, scHierarchyGraph, simpleLattice, + "_SIMPLE"); } else if (key instanceof MethodDescriptor) { MethodDescriptor md = (MethodDescriptor) key; - ssjava.writeLatticeDotFile(md.getClassDesc(), md, simpleLattice, "_SIMPLE"); + writeInferredLatticeDotFile(md.getClassDesc(), md, scHierarchyGraph, simpleLattice, + "_SIMPLE"); } + + LocationSummary ls = getLocationSummary(key); + System.out.println("####LOC SUMMARY=" + key + "\n" + ls.getMapHNodeNameToLocationName()); } Set cdKeySet = cd2lattice.keySet(); for (Iterator iterator = cdKeySet.iterator(); iterator.hasNext();) { ClassDescriptor cd = (ClassDescriptor) iterator.next(); - ssjava.writeLatticeDotFile(cd, null, cd2lattice.get(cd)); + writeInferredLatticeDotFile((ClassDescriptor) cd, getSkeletonCombinationHierarchyGraph(cd), + 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)); + writeInferredLatticeDotFile(md.getClassDesc(), md, getSkeletonCombinationHierarchyGraph(md), + md2lattice.get(md), ""); } } @@ -283,8 +520,7 @@ public class LocationInference { for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { Descriptor desc = (Descriptor) iterator.next(); - HierarchyGraph graph = getSkeletonCombinationHierarchyGraph(desc); - SSJavaLattice simpleLattice = buildLattice.buildLattice(graph); + SSJavaLattice simpleLattice = buildLattice.buildLattice(desc); addMapDescToSimpleLattice(desc, simpleLattice); @@ -335,7 +571,8 @@ public class LocationInference { Descriptor desc = (Descriptor) iterator.next(); HierarchyGraph simpleHierarchyGraph = getHierarchyGraph(desc).clone(); simpleHierarchyGraph.setName(desc + "_SIMPLE"); - simpleHierarchyGraph.simplifyHierarchyGraph(); + simpleHierarchyGraph.removeRedundantEdges(); + // simpleHierarchyGraph.simplifyHierarchyGraph(); mapDescriptorToSimpleHierarchyGraph.put(desc, simpleHierarchyGraph); } } @@ -365,7 +602,9 @@ public class LocationInference { HierarchyGraph skeletonGraph = simpleGraph.generateSkeletonGraph(); skeletonGraph.setMapDescToHNode(simpleGraph.getMapDescToHNode()); skeletonGraph.setMapHNodeToDescSet(simpleGraph.getMapHNodeToDescSet()); - skeletonGraph.removeRedundantEdges(); + skeletonGraph.simplifyHierarchyGraph(); + // skeletonGraph.combineRedundantNodes(false); + // skeletonGraph.removeRedundantEdges(); mapDescriptorToSkeletonHierarchyGraph.put(desc, skeletonGraph); } } @@ -460,24 +699,24 @@ public class LocationInference { // start to analyze leaf node MethodDescriptor md = methodDescriptorsToVisitStack.pop(); - HierarchyGraph methodGraph = new HierarchyGraph(md); - MethodSummary methodSummary = new MethodSummary(); + HierarchyGraph hierarchyGraph = new HierarchyGraph(md); + // MethodSummary methodSummary = new MethodSummary(md); - MethodLocationInfo methodInfo = new MethodLocationInfo(md); - curMethodInfo = methodInfo; + // MethodLocationInfo methodInfo = new MethodLocationInfo(md); + // curMethodInfo = methodInfo; System.out.println(); System.out.println("SSJAVA: Construcing the hierarchy graph from " + md); - constructHierarchyGraph(md, methodGraph, methodSummary); + constructHierarchyGraph(md, hierarchyGraph); - HierarchyGraph prevMethodGraph = getHierarchyGraph(md); - MethodSummary prevMethodSummary = getMethodSummary(md); + HierarchyGraph prevHierarchyGraph = getHierarchyGraph(md); + // MethodSummary prevMethodSummary = getMethodSummary(md); - if ((!methodGraph.equals(prevMethodGraph)) || (!methodSummary.equals(prevMethodSummary))) { + if (!hierarchyGraph.equals(prevHierarchyGraph)) { - mapDescriptorToHierarchyGraph.put(md, methodGraph); - mapMethodDescToMethodSummary.put(md, methodSummary); + mapDescriptorToHierarchyGraph.put(md, hierarchyGraph); + // mapDescToLocationSummary.put(md, methodSummary); // results for callee changed, so enqueue dependents caller for // further analysis @@ -503,8 +742,7 @@ public class LocationInference { return mapDescriptorToHierarchyGraph.get(d); } - private void constructHierarchyGraph(MethodDescriptor md, HierarchyGraph methodGraph, - MethodSummary methodSummary) { + private void constructHierarchyGraph(MethodDescriptor md, HierarchyGraph methodGraph) { // visit each node of method flow graph FlowGraph fg = getFlowGraph(md); @@ -521,7 +759,7 @@ public class LocationInference { for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { FlowNode srcNode = (FlowNode) iterator.next(); - Set outEdgeSet = srcNode.getOutEdgeSet(); + Set outEdgeSet = fg.getOutEdgeSet(srcNode); for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) { FlowEdge outEdge = (FlowEdge) iterator2.next(); FlowNode dstNode = outEdge.getDst(); @@ -574,10 +812,10 @@ public class LocationInference { } private MethodSummary getMethodSummary(MethodDescriptor md) { - if (!mapMethodDescToMethodSummary.containsKey(md)) { - mapMethodDescToMethodSummary.put(md, new MethodSummary()); + if (!mapDescToLocationSummary.containsKey(md)) { + mapDescToLocationSummary.put(md, new MethodSummary(md)); } - return mapMethodDescToMethodSummary.get(md); + return (MethodSummary) mapDescToLocationSummary.get(md); } private void addMapClassDefinitionToLineNum(ClassDescriptor cd, String strLine, int lineNum) { @@ -1385,7 +1623,7 @@ public class LocationInference { for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { FlowNode srcNode = (FlowNode) iterator.next(); - Set outEdgeSet = srcNode.getOutEdgeSet(); + Set outEdgeSet = fg.getOutEdgeSet(srcNode); for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) { FlowEdge outEdge = (FlowEdge) iterator2.next(); FlowNode dstNode = outEdge.getDst(); @@ -1713,38 +1951,120 @@ public class LocationInference { } - private void propagateFlowsFromCallee(MethodInvokeNode min, MethodDescriptor mdCaller, + // private void propagateFlowsFromCallee(MethodInvokeNode min, MethodDescriptor mdCaller, + // MethodDescriptor mdCallee) { + // + // // the transformation for a call site propagates all relations between + // // parameters from the callee + // // if the method is virtual, it also grab all relations from any possible + // // callees + // + // Set setPossibleCallees = new HashSet(); + // if (mdCallee.isStatic()) { + // setPossibleCallees.add(mdCallee); + // } else { + // Set calleeSet = ssjava.getCallGraph().getMethods(mdCallee); + // // removes method descriptors that are not invoked by the caller + // calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller)); + // setPossibleCallees.addAll(calleeSet); + // } + // + // for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) { + // MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next(); + // propagateFlowsToCaller(min, mdCaller, possibleMdCallee); + // } + // + // } + + private void contributeCalleeFlows(MethodInvokeNode min, MethodDescriptor mdCaller, MethodDescriptor mdCallee) { - // the transformation for a call site propagates all relations between - // parameters from the callee - // if the method is virtual, it also grab all relations from any possible - // callees + System.out.println("\n##contributeCalleeFlows callee=" + mdCallee + "TO caller=" + mdCaller); - Set setPossibleCallees = new HashSet(); - if (mdCallee.isStatic()) { - setPossibleCallees.add(mdCallee); - } else { - Set calleeSet = ssjava.getCallGraph().getMethods(mdCallee); - // removes method descriptors that are not invoked by the caller - calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller)); - setPossibleCallees.addAll(calleeSet); - } + getSubGlobalFlowGraph(mdCallee); - for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) { - MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next(); - propagateFlowsToCaller(min, mdCaller, possibleMdCallee); + } + + private FlowGraph getSubGlobalFlowGraph(MethodDescriptor md) { + return mapMethodDescriptorToSubGlobalFlowGraph.get(md); + } + + private void propagateFlowsToCallerWithNoCompositeLocation(MethodInvokeNode min, + MethodDescriptor mdCaller, MethodDescriptor mdCallee) { + + System.out.println("\n##PROPAGATE callee=" + mdCallee + "TO caller=" + mdCaller); + + // 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 + + FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); + FlowGraph callerFlowGraph = getFlowGraph(mdCaller); + int numParam = calleeFlowGraph.getNumParameters(); + + for (int i = 0; i < numParam; i++) { + for (int k = 0; k < numParam; k++) { + + if (i != k) { + + FlowNode paramNode1 = calleeFlowGraph.getParamFlowNode(i); + FlowNode paramNode2 = calleeFlowGraph.getParamFlowNode(k); + + NodeTupleSet tupleSetArg1 = getNodeTupleSetByArgIdx(min, i); + NodeTupleSet tupleSetArg2 = getNodeTupleSetByArgIdx(min, k); + + for (Iterator> iter1 = tupleSetArg1.iterator(); iter1.hasNext();) { + NTuple arg1Tuple = iter1.next(); + + for (Iterator> iter2 = tupleSetArg2.iterator(); iter2.hasNext();) { + NTuple arg2Tuple = iter2.next(); + + // check if the callee propagates an ordering constraints through + // parameters + + Set localReachSet = + calleeFlowGraph.getLocalReachFlowNodeSetFrom(paramNode1); + + if (localReachSet.contains(paramNode2)) { + // need to propagate an ordering relation s.t. arg1 is higher + // than arg2 + + System.out + .println("-param1=" + paramNode1 + " is higher than param2=" + paramNode2); + System.out.println("-arg1Tuple=" + arg1Tuple + " is higher than arg2Tuple=" + + arg2Tuple); + + // otherwise, flows between method/field locations... + callerFlowGraph.addValueFlowEdge(arg1Tuple, arg2Tuple); + System.out.println("arg1=" + arg1Tuple + " arg2=" + arg2Tuple); + + } + + } + + } + System.out.println(); + } + } } + System.out.println("##\n"); } private void propagateFlowsToCaller(MethodInvokeNode min, MethodDescriptor mdCaller, MethodDescriptor mdCallee) { + System.out.println("\n##PROPAGATE callee=" + mdCallee + "TO caller=" + mdCaller); + // 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 + // TODO + // also if a parameter is a composite location and is started with "this" reference, + // need to make sure that the corresponding argument is higher than the translated location of + // the parameter. + FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); FlowGraph callerFlowGraph = getFlowGraph(mdCaller); int numParam = calleeFlowGraph.getNumParameters(); @@ -1757,6 +2077,11 @@ public class LocationInference { FlowNode paramNode1 = calleeFlowGraph.getParamFlowNode(i); FlowNode paramNode2 = calleeFlowGraph.getParamFlowNode(k); + System.out.println("param1=" + paramNode1 + " curDescTuple=" + + paramNode1.getCurrentDescTuple()); + System.out.println("param2=" + paramNode2 + " curDescTuple=" + + paramNode2.getCurrentDescTuple()); + NodeTupleSet tupleSetArg1 = getNodeTupleSetByArgIdx(min, i); NodeTupleSet tupleSetArg2 = getNodeTupleSetByArgIdx(min, k); @@ -1776,6 +2101,11 @@ public class LocationInference { // need to propagate an ordering relation s.t. arg1 is higher // than arg2 + System.out + .println("-param1=" + paramNode1 + " is higher than param2=" + paramNode2); + System.out.println("-arg1Tuple=" + arg1Tuple + " is higher than arg2Tuple=" + + arg2Tuple); + if (!min.getMethod().isStatic()) { // check if this is the case that values flow to/from the // current object reference 'this' @@ -1783,51 +2113,85 @@ public class LocationInference { NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); Descriptor baseRef = baseTuple.get(baseTuple.size() - 1); + System.out.println("paramNode1.getCurrentDescTuple()=" + + paramNode1.getCurrentDescTuple()); // calculate the prefix of the argument + if (arg2Tuple.size() == 1 && arg2Tuple.get(0).equals(baseRef)) { + // in this case, the callee flow causes a caller flow to the object whose method + // is invoked. if (!paramNode1.getCurrentDescTuple().startsWith(mdCallee.getThis())) { + // check whether ??? NTuple param1Prefix = calculatePrefixForParam(callerFlowGraph, calleeFlowGraph, min, arg1Tuple, paramNode1); if (param1Prefix != null && param1Prefix.startsWith(mdCallee.getThis())) { - // in this case, we need to create a new edge - // 'this.FIELD'->'this' - // but we couldn't... instead we assign the - // corresponding - // parameter a new composite location started with - // 'this' - // reference + // in this case, we need to create a new edge 'this.FIELD'->'this' + // but we couldn't... instead we assign a new composite location started + // with 'this' reference to the corresponding parameter CompositeLocation compLocForParam1 = generateCompositeLocation(mdCallee, param1Prefix); - // System.out.println("set comp loc=" + compLocForParam1 - // + - // " to " + paramNode1); + System.out + .println("set comp loc=" + compLocForParam1 + " to " + paramNode1); paramNode1.setCompositeLocation(compLocForParam1); + + // then, we need to make sure that the corresponding argument in the caller + // is required to be higher than or equal to the translated parameter + // location + + NTuple translatedParamTuple = + translateCompositeLocationToCaller(min, compLocForParam1); + + // TODO : check if the arg >= the tranlated parameter + + System.out.println("add a flow edge= " + arg1Tuple + "->" + + translatedParamTuple); + callerFlowGraph.addValueFlowEdge(arg1Tuple, translatedParamTuple); + continue; + } + + } else { + // param1 has already been assigned a composite location + + System.out.println("--param1 has already been assigned a composite location"); + CompositeLocation compLocForParam1 = paramNode1.getCompositeLocation(); + NTuple translatedParamTuple = + translateCompositeLocationToCaller(min, compLocForParam1); + + // TODO : check if the arg >= the tranlated parameter + + System.out.println("add a flow edge= " + arg1Tuple + "->" + + translatedParamTuple); + callerFlowGraph.addValueFlowEdge(arg1Tuple, translatedParamTuple); + + continue; + } } else if (arg1Tuple.size() == 1 && arg1Tuple.get(0).equals(baseRef)) { + // in this case, the callee flow causes a caller flow originated from the object + // whose + // method is invoked. + + System.out.println("###FROM CASE"); if (!paramNode2.getCurrentDescTuple().startsWith(mdCallee.getThis())) { NTuple param2Prefix = - calculatePrefixForParam(callerFlowGraph, calleeFlowGraph, min, arg1Tuple, - paramNode1); + calculatePrefixForParam(callerFlowGraph, calleeFlowGraph, min, arg2Tuple, + paramNode2); if (param2Prefix != null && param2Prefix.startsWith(mdCallee.getThis())) { // in this case, we need to create a new edge 'this' -> - // 'this.FIELD' - // but we couldn't... instead we assign the - // corresponding - // parameter a new composite location started with - // 'this' - // reference + // 'this.FIELD' but we couldn't... instead we assign the corresponding + // parameter a new composite location started with 'this' reference CompositeLocation compLocForParam2 = generateCompositeLocation(mdCallee, param2Prefix); @@ -1845,33 +2209,66 @@ public class LocationInference { // otherwise, flows between method/field locations... callerFlowGraph.addValueFlowEdge(arg1Tuple, arg2Tuple); - // System.out.println("arg1=" + arg1Tuple + " arg2=" + - // arg2Tuple); + System.out.println("arg1=" + arg1Tuple + " arg2=" + arg2Tuple); } } } + System.out.println(); } } } + System.out.println("##\n"); + } + + private NTuple translateCompositeLocationToCaller(MethodInvokeNode min, + CompositeLocation compLocForParam1) { + NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); + + NTuple tuple = new NTuple(); + for (int i = 0; i < baseTuple.size(); i++) { + tuple.add(baseTuple.get(i)); + } + + for (int i = 1; i < compLocForParam1.getSize(); i++) { + Location loc = compLocForParam1.get(i); + tuple.add(loc.getLocDescriptor()); + } + + return tuple; } private CompositeLocation generateCompositeLocation(MethodDescriptor md, - NTuple param1Prefix) { + NTuple paramPrefix) { + + System.out.println("generateCompositeLocation=" + paramPrefix); - CompositeLocation newCompLoc = convertToCompositeLocation(md, param1Prefix); + CompositeLocation newCompLoc = convertToCompositeLocation(md, paramPrefix); + + Descriptor lastDescOfPrefix = paramPrefix.get(paramPrefix.size() - 1); + // System.out.println("lastDescOfPrefix=" + lastDescOfPrefix + " kind=" + // + lastDescOfPrefix.getClass()); + ClassDescriptor enclosingDescriptor; + if (lastDescOfPrefix instanceof FieldDescriptor) { + enclosingDescriptor = ((FieldDescriptor) lastDescOfPrefix).getType().getClassDesc(); + // System.out.println("enclosingDescriptor0=" + enclosingDescriptor); + } else { + // var descriptor case + enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc(); + } + // System.out.println("enclosingDescriptor=" + enclosingDescriptor); LocationDescriptor newLocDescriptor = generateNewLocationDescriptor(); + newLocDescriptor.setEnclosingClassDesc(enclosingDescriptor); - Descriptor enclosingDescriptor = param1Prefix.get(param1Prefix.size() - 1); Location newLoc = new Location(enclosingDescriptor, newLocDescriptor.getSymbol()); newLoc.setLocDescriptor(newLocDescriptor); newCompLoc.addLocation(newLoc); - System.out.println("newCompLoc=" + newCompLoc); + // System.out.println("--newCompLoc=" + newCompLoc); return newCompLoc; } @@ -1887,6 +2284,9 @@ public class LocationInference { List> callerPrefixList = calculatePrefixList(callerFlowGraph, flowNodeArg1); System.out.println("callerPrefixList=" + callerPrefixList); + List> prefixList = calculatePrefixList(calleeFlowGraph, paramNode1); + System.out.println("###prefixList from node=" + paramNode1 + " =" + prefixList); + List> calleePrefixList = translatePrefixListToCallee(baseRef, min.getMethod(), callerPrefixList); @@ -1940,9 +2340,13 @@ public class LocationInference { private List> calculatePrefixList(FlowGraph flowGraph, FlowNode flowNode) { + System.out.println("\n##### calculatePrefixList=" + flowNode); + Set inNodeSet = flowGraph.getIncomingFlowNodeSet(flowNode); inNodeSet.add(flowNode); + System.out.println("inNodeSet=" + inNodeSet); + List> prefixList = new ArrayList>(); for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) { @@ -2003,7 +2407,7 @@ public class LocationInference { } - System.out.println("convertToCompositeLocation from=" + tuple + " to " + compLoc); + System.out.println("-convertToCompositeLocation from=" + tuple + " to " + compLoc); return compLoc; } @@ -2824,7 +3228,7 @@ public class LocationInference { ClassDescriptor cd = toAnalyzeNext(); setupToAnalazeMethod(cd); - toanalyzeMethodList.removeAll(visited); + temp_toanalyzeMethodList.removeAll(visited); while (!toAnalyzeMethodIsEmpty()) { MethodDescriptor md = toAnalyzeMethodNext(); @@ -2847,7 +3251,7 @@ public class LocationInference { if ((!ssjava.isTrustMethod(calleemd)) && (!ssjava.isSSJavaUtil(calleemd.getClassDesc()))) { if (!visited.contains(calleemd)) { - toanalyzeMethodList.add(calleemd); + temp_toanalyzeMethodList.add(calleemd); } reachableCallee.add(calleemd); needToAnalyzeCalleeSet.add(calleemd); @@ -2870,7 +3274,10 @@ public class LocationInference { public void constructFlowGraph() { System.out.println(""); - LinkedList methodDescList = computeMethodList(); + toanalyze_methodDescList = computeMethodList(); + + LinkedList methodDescList = + (LinkedList) toanalyze_methodDescList.clone(); System.out.println("@@@methodDescList=" + methodDescList); // System.exit(0); @@ -2898,8 +3305,8 @@ public class LocationInference { mapMethodDescriptorToFlowGraph.put(md, fg); analyzeMethodBody(md.getClassDesc(), md); - propagateFlowsFromCallees(md); - assignCompositeLocation(md); + propagateFlowsFromCalleesWithNoCompositeLocation(md); + // assignCompositeLocation(md); } } @@ -2907,6 +3314,49 @@ public class LocationInference { } + private Set getMethodInvokeNodeSet(MethodDescriptor md) { + if (!mapMethodDescriptorToMethodInvokeNodeSet.containsKey(md)) { + mapMethodDescriptorToMethodInvokeNodeSet.put(md, new HashSet()); + } + return mapMethodDescriptorToMethodInvokeNodeSet.get(md); + } + + private void constructSubGlobalFlowGraph(MethodDescriptor md) { + + FlowGraph flowGraph = getFlowGraph(md); + + Set setMethodInvokeNode = getMethodInvokeNodeSet(md); + + for (Iterator iter = setMethodInvokeNode.iterator(); iter.hasNext();) { + MethodInvokeNode min = iter.next(); + propagateFlowsFromMethodInvokeNode(md, min); + } + + } + + private void propagateFlowsFromMethodInvokeNode(MethodDescriptor mdCaller, MethodInvokeNode min) { + // the transformation for a call site propagates flows through parameters + // if the method is virtual, it also grab all relations from any possible + // callees + + MethodDescriptor mdCallee = min.getMethod(); + Set setPossibleCallees = new HashSet(); + if (mdCallee.isStatic()) { + setPossibleCallees.add(mdCallee); + } else { + Set calleeSet = ssjava.getCallGraph().getMethods(mdCallee); + // removes method descriptors that are not invoked by the caller + calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller)); + setPossibleCallees.addAll(calleeSet); + } + + for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) { + MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next(); + contributeCalleeFlows(min, mdCaller, possibleMdCallee); + } + + } + private void assignCompositeLocation(MethodDescriptor md) { FlowGraph flowGraph = getFlowGraph(md); @@ -2948,6 +3398,40 @@ public class LocationInference { } + private void propagateFlowsFromCalleesWithNoCompositeLocation(MethodDescriptor mdCaller) { + + // the transformation for a call site propagates flows through parameters + // if the method is virtual, it also grab all relations from any possible + // callees + + Set setMethodInvokeNode = + mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller); + + if (setMethodInvokeNode != null) { + + for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) { + MethodInvokeNode min = (MethodInvokeNode) iterator.next(); + MethodDescriptor mdCallee = min.getMethod(); + Set setPossibleCallees = new HashSet(); + if (mdCallee.isStatic()) { + setPossibleCallees.add(mdCallee); + } else { + Set calleeSet = ssjava.getCallGraph().getMethods(mdCallee); + // removes method descriptors that are not invoked by the caller + calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller)); + setPossibleCallees.addAll(calleeSet); + } + + for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) { + MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next(); + propagateFlowsToCallerWithNoCompositeLocation(min, mdCaller, possibleMdCallee); + } + + } + } + + } + private void propagateFlowsFromCallees(MethodDescriptor mdCaller) { // the transformation for a call site propagates flows through parameters @@ -3874,11 +4358,11 @@ public class LocationInference { analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null, implicitFlowTupleSet, false); - System.out.println("-analyzeFlowAssignmentNode=" + an.printNode(0)); - System.out.println("-nodeSetLHS=" + nodeSetLHS); - System.out.println("-nodeSetRHS=" + nodeSetRHS); - System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet); - System.out.println("-"); + // System.out.println("-analyzeFlowAssignmentNode=" + an.printNode(0)); + // System.out.println("-nodeSetLHS=" + nodeSetLHS); + // System.out.println("-nodeSetRHS=" + nodeSetRHS); + // System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet); + // System.out.println("-"); if (an.getOperation().getOp() >= 2 && an.getOperation().getOp() <= 12) { // if assignment contains OP+EQ operator, creates edges from LHS to LHS @@ -3964,6 +4448,100 @@ public class LocationInference { } + public void writeInferredLatticeDotFile(ClassDescriptor cd, HierarchyGraph simpleHierarchyGraph, + SSJavaLattice locOrder, String nameSuffix) { + writeInferredLatticeDotFile(cd, null, simpleHierarchyGraph, locOrder, nameSuffix); + } + + public void writeInferredLatticeDotFile(ClassDescriptor cd, MethodDescriptor md, + HierarchyGraph simpleHierarchyGraph, SSJavaLattice locOrder, String nameSuffix) { + + String fileName = "lattice_"; + if (md != null) { + fileName += + cd.getSymbol().replaceAll("[\\W_]", "") + "_" + md.toString().replaceAll("[\\W_]", ""); + } else { + fileName += cd.getSymbol().replaceAll("[\\W_]", ""); + } + + fileName += nameSuffix; + + Set> pairSet = locOrder.getOrderingPairSet(); + + Set addedLocSet = new HashSet(); + + if (pairSet.size() > 0) { + try { + BufferedWriter bw = new BufferedWriter(new FileWriter(fileName + ".dot")); + + bw.write("digraph " + fileName + " {\n"); + + for (Iterator iterator = pairSet.iterator(); iterator.hasNext();) { + // pair is in the form of + Pair pair = (Pair) iterator.next(); + + String highLocId = pair.getFirst(); + String lowLocId = pair.getSecond(); + + if (!addedLocSet.contains(highLocId)) { + addedLocSet.add(highLocId); + drawNode(bw, locOrder, simpleHierarchyGraph, highLocId); + } + + if (!addedLocSet.contains(lowLocId)) { + addedLocSet.add(lowLocId); + drawNode(bw, locOrder, simpleHierarchyGraph, lowLocId); + } + + bw.write(highLocId + " -> " + lowLocId + ";\n"); + } + bw.write("}\n"); + bw.close(); + + } catch (IOException e) { + e.printStackTrace(); + } + + } + + } + + private String convertMergeSetToString(HierarchyGraph graph, Set mergeSet) { + String str = ""; + for (Iterator iterator = mergeSet.iterator(); iterator.hasNext();) { + HNode merged = (HNode) iterator.next(); + if (merged.isMergeNode()) { + str += convertMergeSetToString(graph, graph.getMapHNodetoMergeSet().get(merged)); + } else { + str += " " + merged.getName(); + } + } + return str; + } + + private void drawNode(BufferedWriter bw, SSJavaLattice lattice, HierarchyGraph graph, + String locName) throws IOException { + + HNode node = graph.getHNode(locName); + + if (node == null) { + return; + } + + String prettyStr; + if (lattice.isSharedLoc(locName)) { + prettyStr = locName + "*"; + } else { + prettyStr = locName; + } + + if (node.isMergeNode()) { + Set mergeSet = graph.getMapHNodetoMergeSet().get(node); + prettyStr += ":" + convertMergeSetToString(graph, mergeSet); + } + bw.write(locName + " [label=\"" + prettyStr + "\"]" + ";\n"); + } + public void _debug_printGraph() { Set keySet = mapMethodDescriptorToFlowGraph.keySet(); diff --git a/Robust/src/Analysis/SSJava/LocationSummary.java b/Robust/src/Analysis/SSJava/LocationSummary.java new file mode 100644 index 00000000..c46100bc --- /dev/null +++ b/Robust/src/Analysis/SSJava/LocationSummary.java @@ -0,0 +1,29 @@ +package Analysis.SSJava; + +import java.util.HashMap; +import java.util.Map; + +public abstract class LocationSummary { + + Map mapHNodeNameToLocationName; + + public LocationSummary() { + mapHNodeNameToLocationName = new HashMap(); + } + + public void addMapHNodeNameToLocationName(String nodeName, String locName) { + mapHNodeNameToLocationName.put(nodeName, locName); + } + + public String getLocationName(String nodeName) { + if (!mapHNodeNameToLocationName.containsKey(nodeName)) { + mapHNodeNameToLocationName.put(nodeName, nodeName); + } + return mapHNodeNameToLocationName.get(nodeName); + } + + public Map getMapHNodeNameToLocationName() { + return mapHNodeNameToLocationName; + } + +} diff --git a/Robust/src/Analysis/SSJava/MethodSummary.java b/Robust/src/Analysis/SSJava/MethodSummary.java index ebe588b0..8414b834 100644 --- a/Robust/src/Analysis/SSJava/MethodSummary.java +++ b/Robust/src/Analysis/SSJava/MethodSummary.java @@ -1,5 +1,33 @@ package Analysis.SSJava; -public class MethodSummary { - +import java.util.HashMap; +import java.util.Map; + +import IR.Descriptor; +import IR.MethodDescriptor; + +public class MethodSummary extends LocationSummary { + + MethodDescriptor md; + + String thisLocName; + String globalLocName; + + CompositeLocation pcLoc; + CompositeLocation returnLoc; + + Map mapParamIdxToInferLoc; + Map mapDescToInferCompositeLocation; + + public MethodSummary(MethodDescriptor md) { + this.md = md; + this.pcLoc = new CompositeLocation(new Location(md, Location.TOP)); + this.mapParamIdxToInferLoc = new HashMap(); + this.thisLocName = "this"; + } + + public void addMapParamIdxToInferLoc(int paramIdx, CompositeLocation inferLoc) { + mapParamIdxToInferLoc.put(paramIdx, inferLoc); + } + } -- 2.34.1