From 2dcc891b7dfc2a791c10b820da51755813adefd7 Mon Sep 17 00:00:00 2001 From: yeom Date: Sun, 21 Oct 2012 23:50:23 +0000 Subject: [PATCH] addressing two problems in the composite location generation: 1) when a parameter has a composite location which starts with the 'this' reference, we need to add a ordering constraints s.t. the corresponding argument is higher than the parameter composite location in the global value flow, which might cause structure changes of the global flow graph 2) when a callee assigns a new composite location to the return value, we need to changes ordering relations of the global flow graph. --- Robust/src/Analysis/SSJava/FlowDownCheck.java | 4 + Robust/src/Analysis/SSJava/FlowGraph.java | 92 +- Robust/src/Analysis/SSJava/FlowNode.java | 2 +- .../src/Analysis/SSJava/FlowReturnNode.java | 63 ++ .../src/Analysis/SSJava/GlobalFlowGraph.java | 24 + .../Analysis/SSJava/LocationInference.java | 969 +++++------------- Robust/src/Analysis/SSJava/MethodSummary.java | 8 +- 7 files changed, 409 insertions(+), 753 deletions(-) create mode 100644 Robust/src/Analysis/SSJava/FlowReturnNode.java diff --git a/Robust/src/Analysis/SSJava/FlowDownCheck.java b/Robust/src/Analysis/SSJava/FlowDownCheck.java index f3d34a55..5dbf31e1 100644 --- a/Robust/src/Analysis/SSJava/FlowDownCheck.java +++ b/Robust/src/Analysis/SSJava/FlowDownCheck.java @@ -1122,6 +1122,10 @@ public class FlowDownCheck { MethodDescriptor calleemd = min.getMethod(); + if (calleemd.isStatic()) { + return; + } + List callerArgList = new ArrayList(); List calleeParamList = new ArrayList(); diff --git a/Robust/src/Analysis/SSJava/FlowGraph.java b/Robust/src/Analysis/SSJava/FlowGraph.java index 2ab6dad9..feed5777 100644 --- a/Robust/src/Analysis/SSJava/FlowGraph.java +++ b/Robust/src/Analysis/SSJava/FlowGraph.java @@ -13,7 +13,9 @@ import IR.ClassDescriptor; import IR.Descriptor; import IR.FieldDescriptor; import IR.MethodDescriptor; +import IR.NameDescriptor; import IR.VarDescriptor; +import IR.Tree.MethodInvokeNode; public class FlowGraph { @@ -37,6 +39,8 @@ public class FlowGraph { // DS for the lattice generation Map mapIdxToFlowNode; + Map mapMethodInvokeNodeToFlowReturnNode; + public static int interseed = 0; boolean debug = true; @@ -52,6 +56,7 @@ public class FlowGraph { this.mapIdxToFlowNode = new HashMap(); this.mapFlowNodeToOutEdgeSet = new HashMap>(); this.mapFlowNodeToInEdgeSet = new HashMap>(); + this.mapMethodInvokeNodeToFlowReturnNode = new HashMap(); if (!md.isStatic()) { // create a node for 'this' varialbe @@ -109,7 +114,26 @@ public class FlowGraph { mapDescTupleToInferNode.put(tuple, newNode); // nodeSet.add(newNode); - System.out.println("create new intermediate node= " + newNode); + System.out.println("create new intermediate node= " + newNode); + + return newNode; + } + + public FlowReturnNode getFlowReturnNode(MethodInvokeNode min) { + return mapMethodInvokeNodeToFlowReturnNode.get(min); + } + + public FlowReturnNode createReturnNode(MethodInvokeNode min) { + NTuple tuple = new NTuple(); + NameDescriptor n = new NameDescriptor("RETURNLOC" + (LocationInference.locSeed++)); + tuple.add(n); + + FlowReturnNode newNode = new FlowReturnNode(tuple, min); + mapDescTupleToInferNode.put(tuple, newNode); + mapMethodInvokeNodeToFlowReturnNode.put(min, newNode); + // nodeSet.add(newNode); + + System.out.println("create new set node= " + newNode); return newNode; } @@ -235,7 +259,7 @@ public class FlowGraph { return; } - System.out.println("create an edge from " + fromNode + " to " + toNode); + // System.out.println("create an edge from " + fromNode + " to " + toNode); int fromTupleSize = fromDescTuple.size(); NTuple curFromTuple = new NTuple(); @@ -534,50 +558,28 @@ public class FlowGraph { if (node.equals(getFlowNode(flowEdge.getEndTuple()))) { FlowNode incomingNode = getFlowNode(flowEdge.getInitTuple()); - if (!visited.contains(incomingNode)) { - visited.add(incomingNode); - getIncomingFlowNodeSet(incomingNode, visited); - } - } - } - } - - } - - public Set> getIncomingFlowTupleSet(FlowNode fn) { - - NTuple dstTuple = fn.getDescTuple(); - - Set> set = new HashSet>(); - - ClassDescriptor cd = null; - - for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) { - FlowNode node = (FlowNode) iterator.next(); - - Set edgeSet = getOutEdgeSet(node); - for (Iterator iterator2 = edgeSet.iterator(); iterator2.hasNext();) { - FlowEdge flowEdge = (FlowEdge) iterator2.next(); - if (dstTuple.equals(flowEdge.getEndTuple())) { - NTuple initTuple = flowEdge.getInitTuple(); - NTuple locTuple = new NTuple(); - for (int i = 0; i < initTuple.size(); i++) { - Descriptor d = initTuple.get(i); - Location loc; - if (i == 0) { - loc = new Location(md, d.getSymbol()); - cd = ((VarDescriptor) d).getType().getClassDesc(); - } else { - loc = new Location(cd, d.getSymbol()); - cd = ((FieldDescriptor) d).getType().getClassDesc(); + if (incomingNode instanceof FlowReturnNode) { + FlowReturnNode rnode = (FlowReturnNode) incomingNode; + Set> nodeTupleSet = rnode.getTupleSet(); + for (Iterator iterator3 = nodeTupleSet.iterator(); iterator3.hasNext();) { + NTuple nodeTuple = (NTuple) iterator3.next(); + FlowNode fn = getFlowNode(nodeTuple); + if (!visited.contains(fn)) { + visited.add(fn); + getIncomingFlowNodeSet(fn, visited); + } + } + } else { + if (!visited.contains(incomingNode)) { + visited.add(incomingNode); + getIncomingFlowNodeSet(incomingNode, visited); } - locTuple.add(loc); } - set.add(locTuple); + } } } - return set; + } public boolean isParameter(NTuple tuple) { @@ -704,7 +706,13 @@ public class FlowGraph { } private void drawNode(FlowNode node, BufferedWriter bw) throws IOException { - bw.write(node.getID() + " [label=\"" + node.getPrettyID() + "\"]" + ";\n"); + if (node instanceof FlowReturnNode) { + FlowReturnNode rnode = (FlowReturnNode) node; + bw.write(node.getID() + " [label=\"" + node.getPrettyID() + "\"]" + ";\n"); + } else { + bw.write(node.getID() + " [label=\"" + node.getPrettyID() + "\"]" + ";\n"); + } + } public void writeGraph() throws java.io.IOException { diff --git a/Robust/src/Analysis/SSJava/FlowNode.java b/Robust/src/Analysis/SSJava/FlowNode.java index 92822a3a..c6a6b79e 100644 --- a/Robust/src/Analysis/SSJava/FlowNode.java +++ b/Robust/src/Analysis/SSJava/FlowNode.java @@ -11,7 +11,7 @@ import IR.VarDescriptor; public class FlowNode { // descriptor tuple is a unique identifier of the flow node - private NTuple descTuple; + protected NTuple descTuple; // if the infer node represents the base type of field access, // this set contains fields of the base type diff --git a/Robust/src/Analysis/SSJava/FlowReturnNode.java b/Robust/src/Analysis/SSJava/FlowReturnNode.java new file mode 100644 index 00000000..a2807802 --- /dev/null +++ b/Robust/src/Analysis/SSJava/FlowReturnNode.java @@ -0,0 +1,63 @@ +package Analysis.SSJava; + +import java.util.HashSet; +import java.util.Set; + +import IR.Descriptor; +import IR.NameDescriptor; +import IR.Tree.MethodInvokeNode; + +public class FlowReturnNode extends FlowNode { + + Set> returnTupleSet; + MethodInvokeNode min; + + public FlowReturnNode(NTuple t, MethodInvokeNode min) { + super(t); + this.returnTupleSet = new HashSet>(); + this.min = min; + } + + public void setNewTuple(NTuple in) { + returnTupleSet.clear(); + returnTupleSet.add(in); + } + + public void addTupleSet(NodeTupleSet in) { + returnTupleSet.addAll(in.getSet()); + } + + public void addTupleSet(Set> in) { + returnTupleSet.addAll(in); + } + + public void addTuple(NTuple in) { + returnTupleSet.add(in); + } + + public Set> getTupleSet() { + return returnTupleSet; + } + + public String toString() { + String rtr = "[RNODE]:" + descTuple + ":" + min.getMethodName(); + rtr += ":" + returnTupleSet; + return rtr; + } + + public String getPrettyID() { + String id = min.getMethodName() + "<"; + String property = ""; + for (int i = 0; i < descTuple.size(); i++) { + if (i != 0) { + id += ","; + } + id += descTuple.get(i).getSymbol(); + } + id += ">"; + + id += " " + returnTupleSet; + + return id; + } +} diff --git a/Robust/src/Analysis/SSJava/GlobalFlowGraph.java b/Robust/src/Analysis/SSJava/GlobalFlowGraph.java index a9ef90af..792a7fc4 100644 --- a/Robust/src/Analysis/SSJava/GlobalFlowGraph.java +++ b/Robust/src/Analysis/SSJava/GlobalFlowGraph.java @@ -89,6 +89,30 @@ public class GlobalFlowGraph { return mapLocationToInferCompositeLocation.get(loc); } + public boolean hasValueFlowEdge(NTuple fromLocTuple, NTuple toLocTuple) { + + // return true if the graph already has a flow edge + + if (!mapLocTupleToNode.containsKey(fromLocTuple) || !mapLocTupleToNode.containsKey(toLocTuple)) { + return false; + } + + GlobalFlowNode fromNode = getFlowNode(fromLocTuple); + GlobalFlowNode toNode = getFlowNode(toLocTuple); + + if (!mapFlowNodeToOutNodeSet.containsKey(fromNode) + || !mapFlowNodeToInNodeSet.containsKey(toNode)) { + return false; + } + + if (mapFlowNodeToOutNodeSet.get(fromNode).contains(toNode) + && mapFlowNodeToInNodeSet.get(toNode).contains(fromNode)) { + return true; + } + + return false; + } + public void addValueFlowEdge(NTuple fromLocTuple, NTuple toLocTuple) { Location lastElementfromLocTuple = fromLocTuple.get(fromLocTuple.size() - 1); diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index b17ea3c7..103faa85 100644 --- a/Robust/src/Analysis/SSJava/LocationInference.java +++ b/Robust/src/Analysis/SSJava/LocationInference.java @@ -146,6 +146,8 @@ public class LocationInference { LocationInfo curMethodInfo; + private boolean hasChanges = false; + boolean debug = true; public static int locSeed = 0; @@ -239,14 +241,16 @@ public class LocationInference { // construct value flow graph constructFlowGraph(); - assignCompositeLocation(); - updateFlowGraph(); - - assignCompositeLocation(); - updateFlowGraph(); + constructGlobalFlowGraph(); - // calculate RETURNLOC,PCLOC - calculateExtraLocations(); + do { + assignCompositeLocation(); + updateFlowGraph(); + calculateExtraLocations(); + hasChanges = false; + addAdditionalOrderingConstraints(); + System.out.println("&&&&&&&&&&&&&&&&&&&&&&has changes=" + hasChanges); + } while (hasChanges); _debug_writeFlowGraph(); @@ -324,6 +328,12 @@ public class LocationInference { translateCompositeLocationAssignmentToFlowGraph(methodEventLoopDesc); } + private void addAdditionalOrderingConstraints() { + System.out.println("\nSSJAVA: Add addtional ordering constriants:"); + MethodDescriptor methodEventLoopDesc = ssjava.getMethodContainingSSJavaLoop(); + addAddtionalOrderingConstraints(methodEventLoopDesc); + } + private void updateCompositeLocationAssignments() { LinkedList methodDescList = @@ -428,7 +438,6 @@ public class LocationInference { // tuple of 'min'. translateMapLocationToInferCompositeLocationToCalleeGraph(callerGlobalFlowGraph, min); calleeSet.add(min.getMethod()); - } for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) { @@ -443,7 +452,60 @@ public class LocationInference { // the corresponding argument in the caller is required to be higher than the translated // parameter location in the caller lattice // TODO + // addOrderingConstraintFromCompLocParamToArg(mdCaller, min); + } + + } + + private void addAddtionalOrderingConstraints(MethodDescriptor mdCaller) { + + // First, assign a composite location to a node in the flow graph + GlobalFlowGraph callerGlobalFlowGraph = getSubGlobalFlowGraph(mdCaller); + + FlowGraph callerFlowGraph = getFlowGraph(mdCaller); + Map callerMapLocToCompLoc = + callerGlobalFlowGraph.getMapLocationToInferCompositeLocation(); + Set methodLocSet = callerMapLocToCompLoc.keySet(); + + Set minSet = mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller); + + Set calleeSet = new HashSet(); + for (Iterator iterator = minSet.iterator(); iterator.hasNext();) { + MethodInvokeNode min = (MethodInvokeNode) iterator.next(); + MethodDescriptor mdCallee = min.getMethod(); + calleeSet.add(mdCallee); + + // + // add an additional ordering constraint + // if the first element of a parameter composite location matches 'this' reference, + // the corresponding argument in the caller is required to be higher than the translated + // parameter location in the caller lattice + // TODO addOrderingConstraintFromCompLocParamToArg(mdCaller, min); + + // + // update return flow nodes in the caller + CompositeLocation returnLoc = getMethodSummary(mdCallee).getRETURNLoc(); + + System.out.println("### min=" + min.printNode(0) + " returnLoc=" + returnLoc); + if (returnLoc != null && returnLoc.get(0).getLocDescriptor().equals(mdCallee.getThis()) + && returnLoc.getSize() > 1) { + System.out.println("###RETURN COMP LOC=" + returnLoc); + NTuple returnLocTuple = returnLoc.getTuple(); + NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); + NTuple newReturnTuple = baseTuple.clone(); + for (int i = 1; i < returnLocTuple.size(); i++) { + newReturnTuple.add(returnLocTuple.get(i).getLocDescriptor()); + } + System.out.println("###NEW RETURN TUPLE FOR CALLER=" + newReturnTuple); + callerFlowGraph.getFlowReturnNode(min).setNewTuple(newReturnTuple); + } + + } + + for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) { + MethodDescriptor callee = (MethodDescriptor) iterator.next(); + addAddtionalOrderingConstraints(callee); } } @@ -469,20 +531,41 @@ public class LocationInference { if (compLoc != null) { NTuple argTuple = getNodeTupleByArgIdx(min, idx); NTuple globalArgLocTuple = translateToLocTuple(mdCaller, argTuple); - System.out.println("----- add global flow globalArgLocTuple=" + globalArgLocTuple - + "-> globalParamLocTuple=" + globalParamLocTuple); - globalGraph.addValueFlowEdge(globalArgLocTuple, globalParamLocTuple); + + if (!isLiteralValueLocTuple(globalArgLocTuple) + && !isLiteralValueLocTuple(globalParamLocTuple)) { + if (!globalGraph.hasValueFlowEdge(globalArgLocTuple, globalParamLocTuple)) { + System.out.println("----- add global flow globalArgLocTuple=" + globalArgLocTuple + + "-> globalParamLocTuple=" + globalParamLocTuple); + hasChanges = true; + globalGraph.addValueFlowEdge(globalArgLocTuple, globalParamLocTuple); + } + } for (Iterator iterator = pcLocTupleSet.iterator(); iterator.hasNext();) { NTuple pcLocTuple = (NTuple) iterator.next(); - System.out.println("----- add global flow PCLOC=" + pcLocTuple - + "-> globalParamLocTuple=" + globalParamLocTuple); - globalGraph.addValueFlowEdge(pcLocTuple, globalParamLocTuple); + + if (!isLiteralValueLocTuple(pcLocTuple) && !isLiteralValueLocTuple(globalParamLocTuple)) { + if (!globalGraph.hasValueFlowEdge(pcLocTuple, globalParamLocTuple)) { + System.out + .println("----- add global flow PCLOC=" + + pcLocTuple + + "-> globalParamLocTu!globalArgLocTuple.get(0).getLocDescriptor().equals(LITERALDESC)ple=" + + globalParamLocTuple); + hasChanges = true; + globalGraph.addValueFlowEdge(pcLocTuple, globalParamLocTuple); + } + } + } } } } + private boolean isLiteralValueLocTuple(NTuple locTuple) { + return locTuple.get(0).getLocDescriptor().equals(LITERALDESC); + } + public void assignCompositeLocationToFlowGraph(FlowGraph flowGraph, Location loc, CompositeLocation inferCompLoc) { Descriptor localDesc = loc.getLocDescriptor(); @@ -548,8 +631,8 @@ public class LocationInference { baseLocTuple = translateToLocTuple(mdCaller, mapMethodInvokeNodeToBaseTuple.get(min)); } - System.out.println("\n-#translate caller=" + mdCaller + " infer composite loc to callee=" - + mdCallee + " baseLocTuple=" + baseLocTuple); + // System.out.println("\n-#translate caller=" + mdCaller + " infer composite loc to callee=" + // + mdCallee + " baseLocTuple=" + baseLocTuple); // System.out.println("-mapIdxToArgTuple=" + mapIdxToArgTuple); // System.out.println("-callerMapLocToCompLoc=" + callerMapLocToCompLoc); @@ -568,12 +651,11 @@ public class LocationInference { translateCompositeLocationToCallee(callerCompLoc, baseLocTuple, mdCallee); calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, newCalleeCompLoc); - System.out.println("---key=" + key + " callerCompLoc=" + callerCompLoc - + " newCalleeCompLoc=" + newCalleeCompLoc); - System.out.println("-----baseLoctuple=" + baseLocTuple); - System.out.println("-----caller=" + mdCaller + " callee=" + mdCallee); + // System.out.println("---key=" + key + " callerCompLoc=" + callerCompLoc + // + " newCalleeCompLoc=" + newCalleeCompLoc); + // System.out.println("-----baseLoctuple=" + baseLocTuple); + // System.out.println("-----caller=" + mdCaller + " callee=" + mdCallee); } else { - System.out.println("2"); // check if it is the global access Location compLocFirstElement = callerCompLoc.getTuple().get(0); if (compLocFirstElement.getDescriptor().equals(mdCallee) @@ -587,9 +669,9 @@ public class LocationInference { newCalleeCompLoc.addLocation(callerCompLoc.get(i)); } calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, newCalleeCompLoc); - System.out.println("---key=" + key + " callerCompLoc=" + callerCompLoc - + " newCalleeCompLoc=" + newCalleeCompLoc); - System.out.println("-----caller=" + mdCaller + " callee=" + mdCallee); + // System.out.println("---key=" + key + " callerCompLoc=" + callerCompLoc + // + " newCalleeCompLoc=" + newCalleeCompLoc); + // System.out.println("-----caller=" + mdCaller + " callee=" + mdCallee); } else { int paramIdx = getParamIdx(callerCompLoc, mapIdxToArgTuple); @@ -599,7 +681,7 @@ public class LocationInference { NTuple argTuple = mapIdxToArgTuple.get(paramIdx); FlowNode paramFlowNode = calleeFlowGraph.getParamFlowNode(paramIdx); - System.out.println("-----paramIdx=" + paramIdx + " paramFlowNode=" + paramFlowNode); + // System.out.println("-----paramIdx=" + paramIdx + " paramFlowNode=" + paramFlowNode); NTuple paramLocTuple = translateToLocTuple(mdCallee, paramFlowNode.getDescTuple()); newCalleeCompLoc = new CompositeLocation(); @@ -610,10 +692,10 @@ public class LocationInference { newCalleeCompLoc.addLocation(callerCompLoc.get(i)); } calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, newCalleeCompLoc); - System.out.println("---key=" + key + " callerCompLoc=" + callerCompLoc - + " newCalleeCompLoc=" + newCalleeCompLoc); - System.out.println("------argTuple=" + argTuple); - System.out.println("-----caller=" + mdCaller + " callee=" + mdCallee); + // System.out.println("---key=" + key + " callerCompLoc=" + callerCompLoc + // + " newCalleeCompLoc=" + newCalleeCompLoc); + // System.out.println("------argTuple=" + argTuple); + // System.out.println("-----caller=" + mdCaller + " callee=" + mdCallee); } @@ -627,8 +709,6 @@ public class LocationInference { // If the location of an argument has a composite location // need to assign a proper composite location to the corresponding callee parameter - // System.out.println("---translate arg composite location to callee param. min=" - // + min.printNode(0)); Set idxSet = mapIdxToArgTuple.keySet(); for (Iterator iterator = idxSet.iterator(); iterator.hasNext();) { Integer idx = (Integer) iterator.next(); @@ -658,9 +738,9 @@ public class LocationInference { NTuple calleeParamLocTuple = translateToLocTuple(mdCallee, calleeParamDescTuple); - System.out.println("---need to translate callerCompLoc=" + callerCompLoc - + " with baseTuple=" + baseLocTuple + " calleeParamLocTuple=" - + calleeParamLocTuple); + // System.out.println("---need to translate callerCompLoc=" + callerCompLoc + // + " with baseTuple=" + baseLocTuple + " calleeParamLocTuple=" + // + calleeParamLocTuple); CompositeLocation newCalleeCompLoc = translateCompositeLocationToCallee(callerCompLoc, baseLocTuple, mdCallee); @@ -668,11 +748,9 @@ public class LocationInference { calleeGlobalGraph.addMapLocationToInferCompositeLocation(calleeParamLocTuple.get(0), newCalleeCompLoc); - System.out.println("---callee loc=" + calleeParamLocTuple.get(0) - + " newCalleeCompLoc=" + newCalleeCompLoc); + // System.out.println("---callee loc=" + calleeParamLocTuple.get(0) + // + " newCalleeCompLoc=" + newCalleeCompLoc); - // System.out.println("###need to assign composite location to=" + calleeParamDescTuple - // + " with baseTuple=" + baseLocTuple); } } @@ -763,23 +841,19 @@ public class LocationInference { globalFlowGraph.getReachableNodeSetByPrefix(node.getLocTuple().get(0)); // Set reachNodeSet = globalFlowGraph.getReachableNodeSetFrom(node); - System.out.println("node=" + node + " prefixList=" + prefixList); - // System.out.println("node=" + node + " prefixList=" + prefixList + " reachableNodeSet=" - // + reachableNodeSet); + // System.out.println("node=" + node + " prefixList=" + prefixList); for (int i = 0; i < prefixList.size(); i++) { NTuple curPrefix = prefixList.get(i); Set> reachableCommonPrefixSet = new HashSet>(); - System.out.println("curPrefix=" + curPrefix); for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) { GlobalFlowNode reachNode = (GlobalFlowNode) iterator2.next(); - System.out.println("reachNode=" + reachNode); if (reachNode.getLocTuple().startsWith(curPrefix)) { reachableCommonPrefixSet.add(reachNode.getLocTuple()); } } - System.out.println("reachableCommonPrefixSet=" + reachableCommonPrefixSet); + // System.out.println("reachableCommonPrefixSet=" + reachableCommonPrefixSet); if (!reachableCommonPrefixSet.isEmpty()) { @@ -789,9 +863,10 @@ public class LocationInference { MethodDescriptor nodePrefixLocFirstElementMethodDesc = (MethodDescriptor) prefixLoc.getDescriptor(); - System.out.println("curPrefixFirstElementMethodDesc=" + curPrefixFirstElementMethodDesc); - System.out.println("nodePrefixLocFirstElementMethodDesc=" - + nodePrefixLocFirstElementMethodDesc); + // System.out.println("curPrefixFirstElementMethodDesc=" + + // curPrefixFirstElementMethodDesc); + // System.out.println("nodePrefixLocFirstElementMethodDesc=" + // + nodePrefixLocFirstElementMethodDesc); if (curPrefixFirstElementMethodDesc.equals(nodePrefixLocFirstElementMethodDesc) || isTransitivelyCalledFrom(nodePrefixLocFirstElementMethodDesc, @@ -853,7 +928,7 @@ public class LocationInference { Set incomingNodeSetPrefix = graph.getIncomingNodeSetByPrefix(node.getLocTuple().get(0)); System.out.println("incomingNodeSetPrefix=" + incomingNodeSetPrefix); - // + Set reachableNodeSetPrefix = graph.getReachableNodeSetByPrefix(node.getLocTuple().get(0)); System.out.println("reachableNodeSetPrefix=" + reachableNodeSetPrefix); @@ -863,20 +938,12 @@ public class LocationInference { for (Iterator iterator = incomingNodeSetPrefix.iterator(); iterator.hasNext();) { GlobalFlowNode inNode = (GlobalFlowNode) iterator.next(); NTuple inNodeTuple = inNode.getLocTuple(); - System.out.println("inNodetuple=" + inNodeTuple); - // if (inNodeTuple.size() == 1) { - // if (!prefixList.contains(inNodeTuple)) { - // prefixList.add(inNodeTuple); - // } - // } else { for (int i = 1; i < inNodeTuple.size(); i++) { NTuple prefix = inNodeTuple.subList(0, i); - System.out.println("-p=" + prefix); if (!prefixList.contains(prefix)) { prefixList.add(prefix); } } - // } } Collections.sort(prefixList, new Comparator>() { @@ -899,7 +966,6 @@ public class LocationInference { ClassDescriptor cd = md.getClassDesc(); int idx = 0; - System.out.println("$$$$$$$$$$$prefixList=" + prefixList); Set> toberemoved = new HashSet>(); // for (int i = 0; i < prefixList.size(); i++) { // NTuple prefixLocTuple = prefixList.get(i); @@ -908,7 +974,7 @@ public class LocationInference { // } // } - System.out.println("method class=" + cd + " toberemoved=" + toberemoved); + // System.out.println("method class=" + cd + " toberemoved=" + toberemoved); prefixList.removeAll(toberemoved); @@ -1063,12 +1129,12 @@ public class LocationInference { private void propagateValueFlowsToCallerFromSubGlobalFlowGraph(MethodInvokeNode min, MethodDescriptor mdCaller, MethodDescriptor possibleMdCallee) { - System.out.println("---propagate from " + min.printNode(0) + " to caller=" + mdCaller); + // System.out.println("---propagate from " + min.printNode(0) + " to caller=" + mdCaller); FlowGraph calleeFlowGraph = getFlowGraph(possibleMdCallee); Map> mapIdxToArg = mapMethodInvokeNodeToArgIdxMap.get(min); - System.out.println("-----mapMethodInvokeNodeToArgIdxMap.get(min)=" - + mapMethodInvokeNodeToArgIdxMap.get(min)); + // System.out.println("-----mapMethodInvokeNodeToArgIdxMap.get(min)=" + // + mapMethodInvokeNodeToArgIdxMap.get(min)); Set keySet = mapIdxToArg.keySet(); for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { Integer idx = (Integer) iterator.next(); @@ -1089,51 +1155,6 @@ public class LocationInference { addValueFlowFromCalleeNode(min, mdCaller, possibleMdCallee, calleeNode); } - // int numParam = calleeFlowGraph.getNumParameters(); - // for (int idx = 0; idx < numParam; idx++) { - // - // FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx); - // - // NTuple paramLocTuple = - // translateToLocTuple(possibleMdCallee, paramNode.getCurrentDescTuple()); - // - // GlobalFlowNode globalParamNode = - // calleeSubGlobalGraph.getFlowNode(paramLocTuple); - // - // NTuple argTuple = - // mapMethodInvokeNodeToArgIdxMap.get(min).get(idx); - // - // NTuple argLocTuple = translateToLocTuple(mdCaller, argTuple); - // - // System.out.println("argTupleSet=" + argLocTuple + " param=" + - // paramLocTuple); - // // here, it adds all value flows reachable from the paramNode in the - // callee's flow graph - // - // addValueFlowsFromCalleeParam(mdCaller, argLocTuple, baseLocTuple, - // possibleMdCallee, - // globalParamNode); - // } - // - // // TODO - // // FlowGraph callerSubGlobalGraph = getSubGlobalFlowGraph(mdCaller); - // // FlowGraph calleeSubGlobalGraph = - // getSubGlobalFlowGraph(possibleMdCallee); - // // - // // int numParam = calleeSubGlobalGraph.getNumParameters(); - // // for (int idx = 0; idx < numParam; idx++) { - // // FlowNode paramNode = calleeSubGlobalGraph.getParamFlowNode(idx); - // // NTuple argTuple = - // mapMethodInvokeNodeToArgIdxMap.get(min).get(idx); - // // System.out.println("argTupleSet=" + argTuple + " param=" + - // paramNode); - // // // here, it adds all value flows reachable from the paramNode in the - // callee's flow graph - // // addValueFlowsFromCalleeParam(min, calleeSubGlobalGraph, paramNode, - // callerSubGlobalGraph, - // // argTuple, baseTuple); - // // } - } private void addValueFlowFromCalleeNode(MethodInvokeNode min, MethodDescriptor mdCaller, @@ -1214,184 +1235,6 @@ public class LocationInference { } - private void addValueFlowsFromCalleeParam(MethodDescriptor mdCaller, - NTuple argLocTuple, NTuple baseLocTuple, MethodDescriptor mdCallee, - GlobalFlowNode globalParamNode) { - - Set visited = new HashSet(); - visited.add(globalParamNode); - recurAddValueFlowsFromCalleeParam(mdCaller, argLocTuple, baseLocTuple, mdCallee, - globalParamNode); - - } - - private void recurAddValueFlowsFromCalleeParam(MethodDescriptor mdCaller, - NTuple argLocTuple, NTuple baseLocTuple, MethodDescriptor mdCallee, - GlobalFlowNode calleeCurNode) { - - // FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); - // GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(mdCallee); - // - // NTuple curNodeLocTuple = calleeCurNode.getLocTuple(); - // NTuple curNodeDescTuple = calleeCurNode.getDescTuple(); - // if (calleeFlowGraph.isParameter(curNodeDescTuple)) { - // curNodeLocTuple = translateToCaller(argLocTuple, curNodeLocTuple); - // } - // - // Set outNodeSet = - // calleeSubGlobalGraph.getOutNodeSet(calleeCurNode); - // for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) { - // GlobalFlowNode outNode = (GlobalFlowNode) iterator.next(); - // - // NTuple curNodeLocTuple = calleeCurNode.getLocTuple(); - // NTuple curNodeDescTuple = calleeCurNode.getDescTuple(); - // if (calleeFlowGraph.isParameter(curNodeDescTuple)) { - // curNodeLocTuple = translateToCaller(argLocTuple, curNodeLocTuple); - // } - // - // outNode.getDescTuple(); - // - // if (calleeFlowGraph.is) - // - // if (calleeSubGlobalGraph.isParameter(srcDescTuple)) { - // // destination node is started with 'parameter' - // // need to translate it in terms of the caller's a node - // srcDescTuple = - // translateToCaller(min, calleeSubGlobalGraph.getParamIdx(srcDescTuple), - // srcDescTuple); - // } - // - // } - // - // Set edgeSet = - // calleeSubGlobalGraph.getOutEdgeSetStartingFrom(calleeSrcNode); - // for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) { - // FlowEdge flowEdge = (FlowEdge) iterator.next(); - // - // NTuple srcDescTuple = flowEdge.getInitTuple(); - // NTuple dstDescTuple = flowEdge.getEndTuple(); - // - // FlowNode dstNode = calleeSubGlobalGraph.getFlowNode(dstDescTuple); - // - // if (calleeSubGlobalGraph.isParameter(srcDescTuple)) { - // // destination node is started with 'parameter' - // // need to translate it in terms of the caller's a node - // srcDescTuple = - // translateToCaller(min, calleeSubGlobalGraph.getParamIdx(srcDescTuple), - // srcDescTuple); - // } - // - // if (calleeSubGlobalGraph.isParameter(dstDescTuple)) { - // // destination node is started with 'parameter' - // // need to translate it in terms of the caller's a node - // dstDescTuple = - // translateToCaller(min, calleeSubGlobalGraph.getParamIdx(dstDescTuple), - // dstDescTuple); - // } - // - // callerSubGlobalGraph.addValueFlowEdge(srcDescTuple, dstDescTuple); - // - // if (!visited.contains(dstNode)) { - // visited.add(dstNode); - // recurAddValueFlowsFromCalleeParam(min, calleeSubGlobalGraph, dstNode, - // callerSubGlobalGraph, - // dstDescTuple, visited, baseTuple); - // } - // - // } - - } - - private NTuple translateToCaller(NTuple argLocTuple, - NTuple curNodeLocTuple) { - - NTuple callerLocTuple = new NTuple(); - - callerLocTuple.addAll(argLocTuple); - for (int i = 1; i < curNodeLocTuple.size(); i++) { - callerLocTuple.add(curNodeLocTuple.get(i)); - } - - return callerLocTuple; - } - - private void recurAddValueFlowsFromCalleeParam(MethodInvokeNode min, - FlowGraph calleeSubGlobalGraph, FlowNode calleeSrcNode, FlowGraph callerSubGlobalGraph, - NTuple callerSrcTuple, Set visited, NTuple baseTuple) { - - MethodDescriptor mdCallee = calleeSubGlobalGraph.getMethodDescriptor(); - - // Set edgeSet = - // calleeSubGlobalGraph.getOutEdgeSet(calleeSrcNode); - Set edgeSet = calleeSubGlobalGraph.getOutEdgeSetStartingFrom(calleeSrcNode); - for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) { - FlowEdge flowEdge = (FlowEdge) iterator.next(); - - NTuple srcDescTuple = flowEdge.getInitTuple(); - NTuple dstDescTuple = flowEdge.getEndTuple(); - - FlowNode dstNode = calleeSubGlobalGraph.getFlowNode(dstDescTuple); - - if (calleeSubGlobalGraph.isParameter(srcDescTuple)) { - // destination node is started with 'parameter' - // need to translate it in terms of the caller's a node - srcDescTuple = - translateToCaller(min, calleeSubGlobalGraph.getParamIdx(srcDescTuple), srcDescTuple); - } - - if (calleeSubGlobalGraph.isParameter(dstDescTuple)) { - // destination node is started with 'parameter' - // need to translate it in terms of the caller's a node - dstDescTuple = - translateToCaller(min, calleeSubGlobalGraph.getParamIdx(dstDescTuple), dstDescTuple); - } - - callerSubGlobalGraph.addValueFlowEdge(srcDescTuple, dstDescTuple); - - if (!visited.contains(dstNode)) { - visited.add(dstNode); - recurAddValueFlowsFromCalleeParam(min, calleeSubGlobalGraph, dstNode, callerSubGlobalGraph, - dstDescTuple, visited, baseTuple); - } - - } - - } - - private NTuple translateToCaller(MethodInvokeNode min, int paramIdx, - NTuple srcDescTuple) { - - NTuple callerTuple = new NTuple(); - - NTuple argTuple = mapMethodInvokeNodeToArgIdxMap.get(min).get(paramIdx); - - for (int i = 0; i < argTuple.size(); i++) { - callerTuple.add(argTuple.get(i)); - } - - for (int i = 1; i < srcDescTuple.size(); i++) { - callerTuple.add(srcDescTuple.get(i)); - } - - return callerTuple; - } - - private NTuple traslateToCalleeParamTupleToCallerArgTuple( - NTuple calleeInitTuple, NTuple callerSrcTuple) { - - NTuple callerInitTuple = new NTuple(); - - for (int i = 0; i < callerSrcTuple.size(); i++) { - callerInitTuple.add(callerSrcTuple.get(i)); - } - - for (int i = 1; i < calleeInitTuple.size(); i++) { - callerInitTuple.add(calleeInitTuple.get(i)); - } - - return callerInitTuple; - } - public LocationSummary getLocationSummary(Descriptor d) { if (!mapDescToLocationSummary.containsKey(d)) { if (d instanceof MethodDescriptor) { @@ -1884,64 +1727,101 @@ public class LocationInference { // NTuple boolean hasGlobalAccess = false; for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { - FlowNode srcNode = (FlowNode) iterator.next(); - - // if the srcNode is started with the global descriptor - // need to set as a skeleton node - if (!hasGlobalAccess && srcNode.getDescTuple().startsWith(GLOBALDESC)) { - hasGlobalAccess = true; + FlowNode originalSrcNode = (FlowNode) iterator.next(); + + Set sourceNodeSet = new HashSet(); + if (originalSrcNode instanceof FlowReturnNode) { + FlowReturnNode rnode = (FlowReturnNode) originalSrcNode; + Set> tupleSet = rnode.getTupleSet(); + for (Iterator iterator2 = tupleSet.iterator(); iterator2.hasNext();) { + NTuple nTuple = (NTuple) iterator2.next(); + sourceNodeSet.add(fg.getFlowNode(nTuple)); + System.out.println("&&&SOURCE fg.getFlowNode(nTuple)=" + fg.getFlowNode(nTuple)); + } + } else { + sourceNodeSet.add(originalSrcNode); } - Set outEdgeSet = fg.getOutEdgeSet(srcNode); - for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) { - FlowEdge outEdge = (FlowEdge) iterator2.next(); - FlowNode dstNode = outEdge.getDst(); + System.out.println("---sourceNodeSet=" + sourceNodeSet); + for (Iterator iterator3 = sourceNodeSet.iterator(); iterator3.hasNext();) { + FlowNode srcNode = (FlowNode) iterator3.next(); - NTuple srcNodeTuple = srcNode.getDescTuple(); - NTuple dstNodeTuple = dstNode.getDescTuple(); + // if the srcNode is started with the global descriptor + // need to set as a skeleton node + if (!hasGlobalAccess && srcNode.getDescTuple().startsWith(GLOBALDESC)) { + hasGlobalAccess = true; + } - if (outEdge.getInitTuple().equals(srcNodeTuple) - && outEdge.getEndTuple().equals(dstNodeTuple)) { + Set outEdgeSet = fg.getOutEdgeSet(originalSrcNode); + for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) { + FlowEdge outEdge = (FlowEdge) iterator2.next(); + FlowNode originalDstNode = outEdge.getDst(); + + Set dstNodeSet = new HashSet(); + if (originalDstNode instanceof FlowReturnNode) { + FlowReturnNode rnode = (FlowReturnNode) originalDstNode; + Set> tupleSet = rnode.getTupleSet(); + for (Iterator iterator4 = tupleSet.iterator(); iterator4.hasNext();) { + NTuple nTuple = (NTuple) iterator4.next(); + dstNodeSet.add(fg.getFlowNode(nTuple)); + } + } else { + dstNodeSet.add(originalDstNode); + } + System.out.println("---dstNodeSet=" + dstNodeSet); + for (Iterator iterator4 = dstNodeSet.iterator(); iterator4.hasNext();) { + FlowNode dstNode = (FlowNode) iterator4.next(); - NTuple srcCurTuple = srcNode.getCurrentDescTuple(); - NTuple dstCurTuple = dstNode.getCurrentDescTuple(); + NTuple srcNodeTuple = srcNode.getDescTuple(); + NTuple dstNodeTuple = dstNode.getDescTuple(); - // System.out.println("-srcCurTuple=" + srcCurTuple + " dstCurTuple=" + dstCurTuple); + // if (outEdge.getInitTuple().equals(srcNodeTuple) + // && outEdge.getEndTuple().equals(dstNodeTuple)) { - if ((srcCurTuple.size() > 1 && dstCurTuple.size() > 1) - && srcCurTuple.get(0).equals(dstCurTuple.get(0))) { + NTuple srcCurTuple = srcNode.getCurrentDescTuple(); + NTuple dstCurTuple = dstNode.getCurrentDescTuple(); - // value flows between fields - Descriptor desc = srcCurTuple.get(0); - ClassDescriptor classDesc; + // System.out.println("-srcCurTuple=" + srcCurTuple + " dstCurTuple=" + dstCurTuple); - if (desc.equals(GLOBALDESC)) { - classDesc = md.getClassDesc(); - } else { - VarDescriptor varDesc = (VarDescriptor) srcCurTuple.get(0); - classDesc = varDesc.getType().getClassDesc(); - } - extractFlowsBetweenFields(classDesc, srcNode, dstNode, 1); + if ((srcCurTuple.size() > 1 && dstCurTuple.size() > 1) + && srcCurTuple.get(0).equals(dstCurTuple.get(0))) { - } else if (!srcCurTuple.get(0).equals(dstCurTuple.get(0))) { - // value flow between local var - local var or local var - field + // value flows between fields + Descriptor desc = srcCurTuple.get(0); + ClassDescriptor classDesc; - Descriptor srcDesc = srcCurTuple.get(0); - Descriptor dstDesc = dstCurTuple.get(0); + if (desc.equals(GLOBALDESC)) { + classDesc = md.getClassDesc(); + } else { + VarDescriptor varDesc = (VarDescriptor) srcCurTuple.get(0); + classDesc = varDesc.getType().getClassDesc(); + } + extractFlowsBetweenFields(classDesc, srcNode, dstNode, 1); - methodGraph.addEdge(srcDesc, dstDesc); + } else if (!srcCurTuple.get(0).equals(dstCurTuple.get(0))) { + // value flow between local var - local var or local var - field + + Descriptor srcDesc = srcCurTuple.get(0); + Descriptor dstDesc = dstCurTuple.get(0); + + methodGraph.addEdge(srcDesc, dstDesc); + + if (fg.isParamDesc(srcDesc)) { + methodGraph.setParamHNode(srcDesc); + } + if (fg.isParamDesc(dstDesc)) { + methodGraph.setParamHNode(dstDesc); + } - if (fg.isParamDesc(srcDesc)) { - methodGraph.setParamHNode(srcDesc); - } - if (fg.isParamDesc(dstDesc)) { - methodGraph.setParamHNode(dstDesc); } + // } } } + } + } // If the method accesses static fields @@ -2304,7 +2184,6 @@ public class LocationInference { } private String generateLocationAnnoatation(CompositeLocation loc) { - System.out.println("loc=" + loc); String rtr = ""; // method location Location methodLoc = loc.get(0); @@ -2569,7 +2448,7 @@ public class LocationInference { } } - System.out.println("paramLocTupleHavingInFlowSet=" + paramLocTupleHavingInFlowSet); + // System.out.println("paramLocTupleHavingInFlowSet=" + paramLocTupleHavingInFlowSet); if (paramLocTupleHavingInFlowSet.size() > 0 /* && !coversAllParamters(md, fg, paramLocTupleHavingInFlowSet) */) { @@ -2581,20 +2460,24 @@ public class LocationInference { NTuple pcDescTuple = translateToDescTuple(pcLocTuple); - // add ordering relations s.t. PCLOC is higher than all flow nodes except the set of - // parameters that do not have incoming flows + // System.out.println("pcLoc=" + pcLocTuple); - for (Iterator iterator = fg.getNodeSet().iterator(); iterator.hasNext();) { - FlowNode node = (FlowNode) iterator.next(); + CompositeLocation curPCLoc = methodSummary.getPCLoc(); + if (curPCLoc.get(0).isTop() || pcLocTuple.size() > curPCLoc.getSize()) { + methodSummary.setPCLoc(new CompositeLocation(pcLocTuple)); - if (!paramDescNOTHavingInFlowSet.contains(node.getCurrentDescTuple().get(0))) { - fg.addValueFlowEdge(pcDescTuple, node.getDescTuple()); + // add ordering relations s.t. PCLOC is higher than all flow nodes except the set of + // parameters that do not have incoming flows + for (Iterator iterator = fg.getNodeSet().iterator(); iterator.hasNext();) { + FlowNode node = (FlowNode) iterator.next(); + + if (!paramDescNOTHavingInFlowSet.contains(node.getCurrentDescTuple().get(0))) { + fg.addValueFlowEdge(pcDescTuple, node.getDescTuple()); + } } + fg.getFlowNode(translateToDescTuple(pcLocTuple)).setSkeleton(true); } - System.out.println("pcLoc=" + pcLocTuple); - - methodSummary.setPCLoc(new CompositeLocation(pcLocTuple)); } } @@ -2651,8 +2534,8 @@ public class LocationInference { // with 'this' reference Set paramFlowNodeFlowingToReturnValueSet = getParamNodeFlowingToReturnValue(md); - System.out.println("paramFlowNodeFlowingToReturnValueSet=" - + paramFlowNodeFlowingToReturnValueSet); + // System.out.println("paramFlowNodeFlowingToReturnValueSet=" + // + paramFlowNodeFlowingToReturnValueSet); Set> tupleToBeHigherThanReturnLocSet = new HashSet>(); for (Iterator iterator = paramFlowNodeFlowingToReturnValueSet.iterator(); iterator.hasNext();) { @@ -2667,8 +2550,8 @@ public class LocationInference { NTuple returnDescTuple = returnNode.getCurrentDescTuple(); tupleToBeHigherThanReturnLocSet.add(translateToLocTuple(md, returnDescTuple)); } - System.out.println("-flow graph's returnNodeSet=" + returnNodeSet); - System.out.println("tupleSetToBeHigherThanReturnLoc=" + tupleToBeHigherThanReturnLocSet); + // System.out.println("-flow graph's returnNodeSet=" + returnNodeSet); + // System.out.println("tupleSetToBeHigherThanReturnLoc=" + tupleToBeHigherThanReturnLocSet); // Here, generates a return location in the method lattice that is lower than the // locFlowingToReturnValueSet @@ -2676,85 +2559,21 @@ public class LocationInference { generateLocTupleRelativeTo(md, tupleToBeHigherThanReturnLocSet, RLOC); // System.out.println("returnLocTuple=" + returnLocTuple); - NTuple returnDescTuple = translateToDescTuple(returnLocTuple); - for (Iterator iterator = tupleToBeHigherThanReturnLocSet.iterator(); iterator.hasNext();) { - NTuple higherTuple = (NTuple) iterator.next(); - fg.addValueFlowEdge(translateToDescTuple(higherTuple), returnDescTuple); - } - - fg.getFlowNode(returnDescTuple).setSkeleton(true); - // System.out.println("fg node set=" + fg.getNodeSet()); - - methodSummary.setRETURNLoc(new CompositeLocation(returnLocTuple)); + CompositeLocation curReturnLoc = methodSummary.getRETURNLoc(); + if (curReturnLoc == null || returnDescTuple.size() > curReturnLoc.getSize()) { + methodSummary.setRETURNLoc(new CompositeLocation(returnLocTuple)); - // skip: for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { - // FlowNode returnNode = (FlowNode) iterator.next(); - // - // NTuple returnDescTuple = returnNode.getCurrentDescTuple(); - // NTuple returnLocTuple = translateToLocTuple(md, returnDescTuple); - // - // if (returnLocTuple.get(0).getLocDescriptor().equals(md.getThis())) { - // // if the location type of the return value matches "this" reference - // // then, check whether this return value is equal to/lower than all - // // of parameters that possibly flow into the return values - // for (Iterator iterator2 = inferParamLocSet.iterator(); iterator2.hasNext();) { - // CompositeLocation paramInferLoc = (CompositeLocation) iterator2.next(); - // - // if ((!paramInferLoc.equals(returnLocTuple)) - // && !isGreaterThan(methodLattice, paramInferLoc, inferReturnLoc)) { - // continue skip; - // } - // } - // inferFieldReturnLocSet.add(returnLocTuple); - // - // } - // } + for (Iterator iterator = tupleToBeHigherThanReturnLocSet.iterator(); iterator.hasNext();) { + NTuple higherTuple = (NTuple) iterator.next(); + fg.addValueFlowEdge(translateToDescTuple(higherTuple), returnDescTuple); + } + fg.getFlowNode(returnDescTuple).setSkeleton(true); - // if (inferFieldReturnLocSet.size() > 0) { - // - // // CompositeLocation returnLoc = getLowest(methodLattice, inferFieldReturnLocSet); - // CompositeLocation returnLoc = null; - // if (returnLoc == null) { - // // in this case, assign <'this',bottom> to the RETURNLOC - // returnLoc = new CompositeLocation(new Location(md, md.getThis().getSymbol())); - // returnLoc.addLocation(new Location(md.getClassDesc(), getLattice(md.getClassDesc()) - // .getBottomItem())); - // } - // methodInfo.setReturnLoc(returnLoc); - // - // } else { - // String returnLocSymbol = "RETURNLOC"; - // CompositeLocation returnLocInferLoc = - // new CompositeLocation(new Location(md, returnLocSymbol)); - // methodInfo.setReturnLoc(returnLocInferLoc); - // - // for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) { - // Integer paramIdx = (Integer) iterator.next(); - // CompositeLocation inferLoc = mapParamToLoc.get(paramIdx); - // String paramLocLocalSymbol = inferLoc.get(0).getLocIdentifier(); - // if (!methodLattice.isGreaterThan(paramLocLocalSymbol, returnLocSymbol)) { - // // TODO - // // addRelationHigherToLower(methodLattice, methodInfo, - // // paramLocLocalSymbol, - // // returnLocSymbol); - // } - // } - // - // for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { - // FlowNode returnNode = (FlowNode) iterator.next(); - // CompositeLocation inferLoc = - // generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode)); - // if (!isGreaterThan(methodLattice, inferLoc, returnLocInferLoc)) { - // // TODO - // // addRelation(methodLattice, methodInfo, inferLoc, - // // returnLocInferLoc); - // } - // } - // - // } + } } + } private void calculateExtraLocations(MethodDescriptor md) { @@ -2770,7 +2589,7 @@ public class LocationInference { private NTuple generateLocTupleRelativeTo(MethodDescriptor md, Set> paramLocTupleHavingInFlowSet, String locNamePrefix) { - System.out.println("-generateLocTupleRelativeTo=" + paramLocTupleHavingInFlowSet); + // System.out.println("-generateLocTupleRelativeTo=" + paramLocTupleHavingInFlowSet); NTuple higherLocTuple = new NTuple(); @@ -2791,7 +2610,7 @@ public class LocationInference { for (Iterator iterator2 = inNodeSet.iterator(); iterator2.hasNext();) { FlowNode flowNode = (FlowNode) iterator2.next(); if (flowNode.getDescTuple().startsWith(thisVarDesc)) { - System.out.println("paramLocTuple=" + paramLocTuple + " is lower than THIS"); + // System.out.println("paramLocTuple=" + paramLocTuple + " is lower than THIS"); continue next; } } @@ -2805,7 +2624,7 @@ public class LocationInference { } } - System.out.println("---paramLocTupleStartedWithThis=" + paramLocTupleStartedWithThis); + // System.out.println("---paramLocTupleStartedWithThis=" + paramLocTupleStartedWithThis); Descriptor enclosingDesc = md; if (hasParamNotStartedWithThisRef) { // in this case, PCLOC will be the local location @@ -2818,12 +2637,12 @@ public class LocationInference { NTuple paramLocTuple = null; for (Iterator iterator = paramLocTupleStartedWithThis.iterator(); iterator.hasNext();) { paramLocTuple = (NTuple) iterator.next(); - System.out.println("-----paramLocTuple=" + paramLocTuple + " idx=" + idx); + // System.out.println("-----paramLocTuple=" + paramLocTuple + " idx=" + idx); curLoc = paramLocTuple.get(idx); Descriptor locDesc = curLoc.getLocDescriptor(); locDescSet.add(locDesc); } - System.out.println("-----locDescSet=" + locDescSet + " idx=" + idx); + // System.out.println("-----locDescSet=" + locDescSet + " idx=" + idx); if (locDescSet.size() != 1) { break; } @@ -2874,7 +2693,7 @@ public class LocationInference { for (; iterator.hasNext();) { NTuple curLocTuple = (NTuple) iterator.next(); if (isHigherThan(curLocTuple, highest)) { - System.out.println(curLocTuple + " is greater than " + highest); + // System.out.println(curLocTuple + " is greater than " + highest); highest = curLocTuple; } } @@ -2884,14 +2703,14 @@ public class LocationInference { MethodDescriptor md = (MethodDescriptor) highest.get(0).getDescriptor(); VarDescriptor thisVarDesc = md.getThis(); - System.out.println("highest=" + highest); + // System.out.println("highest=" + highest); for (Iterator> iter = paramLocTupleHavingInFlowSet.iterator(); iter.hasNext();) { NTuple curLocTuple = iter.next(); if (!curLocTuple.equals(highest) && !hasOrderingRelation(highest, curLocTuple)) { - System.out.println("add it to the highest set=" + curLocTuple); + // System.out.println("add it to the highest set=" + curLocTuple); highestSet.add(curLocTuple); } @@ -2901,147 +2720,6 @@ public class LocationInference { } - private void calculateExtraLocations2(MethodDescriptor md) { - // calcualte pcloc, returnloc,... - - SSJavaLattice methodLattice = getMethodLattice(md); - MethodLocationInfo methodInfo = getMethodLocationInfo(md); - FlowGraph fg = getFlowGraph(md); - Set nodeSet = fg.getNodeSet(); - - for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { - FlowNode flowNode = (FlowNode) iterator.next(); - if (flowNode.isDeclaratonNode()) { - CompositeLocation inferLoc = methodInfo.getInferLocation(flowNode.getDescTuple().get(0)); - String locIdentifier = inferLoc.get(0).getLocIdentifier(); - if (!methodLattice.containsKey(locIdentifier)) { - methodLattice.put(locIdentifier); - } - - } - } - - Map mapParamToLoc = methodInfo.getMapParamIdxToInferLoc(); - Set paramIdxSet = mapParamToLoc.keySet(); - - if (!ssjava.getMethodContainingSSJavaLoop().equals(md)) { - // calculate the initial program counter location - // PC location is higher than location types of all parameters - String pcLocSymbol = "PCLOC"; - - Set paramInFlowSet = new HashSet(); - - for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) { - Integer paramIdx = (Integer) iterator.next(); - - FlowNode paramFlowNode = fg.getParamFlowNode(paramIdx); - - if (fg.getIncomingFlowNodeSet(paramFlowNode).size() > 0) { - // parameter has in-value flows - CompositeLocation inferLoc = mapParamToLoc.get(paramIdx); - paramInFlowSet.add(inferLoc); - } - } - - if (paramInFlowSet.size() > 0) { - CompositeLocation lowestLoc = getLowest(methodLattice, paramInFlowSet); - assert (lowestLoc != null); - methodInfo.setPCLoc(lowestLoc); - } - - } - - // calculate a return location - // the return location type is lower than all parameters and location - // types - // of return values - if (!md.getReturnType().isVoid()) { - // first, generate the set of return value location types that starts - // with - // 'this' reference - - Set inferFieldReturnLocSet = new HashSet(); - - Set paramFlowNode = getParamNodeFlowingToReturnValue(md); - Set inferParamLocSet = new HashSet(); - if (paramFlowNode != null) { - for (Iterator iterator = paramFlowNode.iterator(); iterator.hasNext();) { - FlowNode fn = (FlowNode) iterator.next(); - CompositeLocation inferLoc = - generateInferredCompositeLocation(methodInfo, getFlowGraph(md).getLocationTuple(fn)); - inferParamLocSet.add(inferLoc); - } - } - - Set returnNodeSet = fg.getReturnNodeSet(); - - skip: for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { - FlowNode returnNode = (FlowNode) iterator.next(); - CompositeLocation inferReturnLoc = - generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode)); - if (inferReturnLoc.get(0).getLocIdentifier().equals("this")) { - // if the location type of the return value matches "this" reference - // then, check whether this return value is equal to/lower than all - // of - // parameters that possibly flow into the return values - for (Iterator iterator2 = inferParamLocSet.iterator(); iterator2.hasNext();) { - CompositeLocation paramInferLoc = (CompositeLocation) iterator2.next(); - - if ((!paramInferLoc.equals(inferReturnLoc)) - && !isGreaterThan(methodLattice, paramInferLoc, inferReturnLoc)) { - continue skip; - } - } - inferFieldReturnLocSet.add(inferReturnLoc); - - } - } - - if (inferFieldReturnLocSet.size() > 0) { - - CompositeLocation returnLoc = getLowest(methodLattice, inferFieldReturnLocSet); - if (returnLoc == null) { - // in this case, assign <'this',bottom> to the RETURNLOC - returnLoc = new CompositeLocation(new Location(md, md.getThis().getSymbol())); - returnLoc.addLocation(new Location(md.getClassDesc(), getLattice(md.getClassDesc()) - .getBottomItem())); - } - methodInfo.setReturnLoc(returnLoc); - - } else { - String returnLocSymbol = "RETURNLOC"; - CompositeLocation returnLocInferLoc = - new CompositeLocation(new Location(md, returnLocSymbol)); - methodInfo.setReturnLoc(returnLocInferLoc); - - for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) { - Integer paramIdx = (Integer) iterator.next(); - CompositeLocation inferLoc = mapParamToLoc.get(paramIdx); - String paramLocLocalSymbol = inferLoc.get(0).getLocIdentifier(); - if (!methodLattice.isGreaterThan(paramLocLocalSymbol, returnLocSymbol)) { - // TODO - // addRelationHigherToLower(methodLattice, methodInfo, - // paramLocLocalSymbol, - // returnLocSymbol); - } - } - - for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { - FlowNode returnNode = (FlowNode) iterator.next(); - CompositeLocation inferLoc = - generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode)); - if (!isGreaterThan(methodLattice, inferLoc, returnLocInferLoc)) { - // TODO - // addRelation(methodLattice, methodInfo, inferLoc, - // returnLocInferLoc); - } - } - - } - - } - } - private Set getHigherLocSymbolThan(SSJavaLattice lattice, String loc) { Set higherLocSet = new HashSet(); @@ -3156,15 +2834,6 @@ public class LocationInference { return false; } - private void contributeCalleeFlows(MethodInvokeNode min, MethodDescriptor mdCaller, - MethodDescriptor mdCallee) { - - System.out.println("\n##contributeCalleeFlows callee=" + mdCallee + "TO caller=" + mdCaller); - - getSubGlobalFlowGraph(mdCallee); - - } - private GlobalFlowGraph getSubGlobalFlowGraph(MethodDescriptor md) { if (!mapMethodDescriptorToSubGlobalFlowGraph.containsKey(md)) { @@ -3344,51 +3013,6 @@ public class LocationInference { return newCompLoc; } - private NTuple calculatePrefixForParam(FlowGraph callerFlowGraph, - FlowGraph calleeFlowGraph, MethodInvokeNode min, NTuple arg1Tuple, - FlowNode paramNode1) { - - NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); - Descriptor baseRef = baseTuple.get(baseTuple.size() - 1); - System.out.println("baseRef=" + baseRef); - - FlowNode flowNodeArg1 = callerFlowGraph.getFlowNode(arg1Tuple); - 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); - - System.out.println("calleePrefixList=" + calleePrefixList); - - Set reachNodeSetFromParam1 = calleeFlowGraph.getReachFlowNodeSetFrom(paramNode1); - System.out.println("reachNodeSetFromParam1=" + reachNodeSetFromParam1); - - for (int i = 0; i < calleePrefixList.size(); i++) { - NTuple curPrefix = calleePrefixList.get(i); - Set> reachableCommonPrefixSet = new HashSet>(); - - for (Iterator iterator2 = reachNodeSetFromParam1.iterator(); iterator2.hasNext();) { - FlowNode reachNode = (FlowNode) iterator2.next(); - if (reachNode.getCurrentDescTuple().startsWith(curPrefix)) { - reachableCommonPrefixSet.add(reachNode.getCurrentDescTuple()); - } - } - - if (!reachableCommonPrefixSet.isEmpty()) { - System.out.println("###REACHABLECOMONPREFIX=" + reachableCommonPrefixSet - + " with curPreFix=" + curPrefix); - return curPrefix; - } - - } - - return null; - } - private List> translatePrefixListToCallee(Descriptor baseRef, MethodDescriptor mdCallee, List> callerPrefixList) { @@ -3794,7 +3418,11 @@ public class LocationInference { } // _debug_printGraph(); - methodDescList = (LinkedList) toanalyze_methodDescList.clone(); + } + + private void constructGlobalFlowGraph() { + LinkedList methodDescList = + (LinkedList) toanalyze_methodDescList.clone(); while (!methodDescList.isEmpty()) { MethodDescriptor md = methodDescList.removeLast(); @@ -3814,7 +3442,6 @@ public class LocationInference { } } - } private Set getMethodInvokeNodeSet(MethodDescriptor md) { @@ -3824,83 +3451,6 @@ public class LocationInference { 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); - - Set nodeSet = flowGraph.getNodeSet(); - - next: for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { - FlowNode flowNode = (FlowNode) iterator.next(); - - // assign a composite location only to the local variable - if (flowNode.getCurrentDescTuple().size() == 1) { - - List> prefixList = calculatePrefixList(flowGraph, flowNode); - Set reachSet = flowGraph.getReachFlowNodeSetFrom(flowNode); - - for (int i = 0; i < prefixList.size(); i++) { - NTuple curPrefix = prefixList.get(i); - Set> reachableCommonPrefixSet = new HashSet>(); - - for (Iterator iterator2 = reachSet.iterator(); iterator2.hasNext();) { - FlowNode reachNode = (FlowNode) iterator2.next(); - if (reachNode.getCurrentDescTuple().startsWith(curPrefix)) { - reachableCommonPrefixSet.add(reachNode.getCurrentDescTuple()); - } - } - - if (!reachableCommonPrefixSet.isEmpty()) { - System.out.println("NEED TO ASSIGN COMP LOC TO " + flowNode + " with prefix=" - + curPrefix); - CompositeLocation newCompLoc = generateCompositeLocation(md, curPrefix); - flowNode.setCompositeLocation(newCompLoc); - continue next; - } - - } - } - - } - - } - private void propagateFlowsFromCalleesWithNoCompositeLocation(MethodDescriptor mdCaller) { // the transformation for a call site propagates flows through parameters @@ -4038,7 +3588,7 @@ public class LocationInference { private void analyzeFlowReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode rn, NodeTupleSet implicitFlowTupleSet) { - System.out.println("-analyzeFlowReturnNode=" + rn.printNode(0)); + // System.out.println("-analyzeFlowReturnNode=" + rn.printNode(0)); ExpressionNode returnExp = rn.getReturnExpression(); if (returnExp != null) { @@ -4076,10 +3626,9 @@ public class LocationInference { // add tuples corresponding to the current implicit flows currentFlowTupleSet.addTupleSet(implicitFlowTupleSet); - System.out.println("---currentFlowTupleSet=" + currentFlowTupleSet); + // System.out.println("---currentFlowTupleSet=" + currentFlowTupleSet); if (needToGenerateInterLoc(currentFlowTupleSet)) { - System.out.println("8"); FlowNode meetNode = fg.createIntermediateNode(); for (Iterator iterator = currentFlowTupleSet.iterator(); iterator.hasNext();) { NTuple currentFlowTuple = (NTuple) iterator.next(); @@ -4480,7 +4029,7 @@ public class LocationInference { private void analyzeFlowMethodInvokeNode(MethodDescriptor mdCaller, SymbolTable nametable, MethodInvokeNode min, NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) { - System.out.println("analyzeFlowMethodInvokeNode=" + min.printNode(0)); + // System.out.println("analyzeFlowMethodInvokeNode=" + min.printNode(0)); Set> pcLocTupleSet = getPCLocTupleSet(min); for (Iterator iterator = implicitFlowTupleSet.iterator(); iterator.hasNext();) { @@ -4508,10 +4057,14 @@ public class LocationInference { addMapCallerMethodDescToMethodInvokeNodeSet(mdCaller, min); FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); + Set calleeReturnSet = calleeFlowGraph.getReturnNodeSet(); System.out.println("---calleeReturnSet=" + calleeReturnSet); + // when generating the global flow graph, + // we need to add ordering relations from the set of callee return loc tuple to LHS of the + // caller assignment for (Iterator iterator = calleeReturnSet.iterator(); iterator.hasNext();) { FlowNode calleeReturnNode = (FlowNode) iterator.next(); NTuple calleeReturnLocTuple = @@ -4519,6 +4072,8 @@ public class LocationInference { nodeSet.addGlobalFlowTuple(calleeReturnLocTuple); } + FlowReturnNode setNode = getFlowGraph(mdCaller).createReturnNode(min); + if (min.getExpression() != null) { NodeTupleSet baseNodeSet = new NodeTupleSet(); @@ -4540,7 +4095,8 @@ public class LocationInference { // reference NTuple inFlowTuple = new NTuple(baseTuple.getList()); inFlowTuple.addAll(returnDescTuple.subList(1, returnDescTuple.size())); - nodeSet.addTuple(inFlowTuple); + // nodeSet.addTuple(inFlowTuple); + setNode.addTuple(inFlowTuple); } else { // TODO Set inFlowSet = calleeFlowGraph.getIncomingFlowNodeSet(returnNode); @@ -4548,7 +4104,9 @@ public class LocationInference { for (Iterator iterator2 = inFlowSet.iterator(); iterator2.hasNext();) { FlowNode inFlowNode = (FlowNode) iterator2.next(); if (inFlowNode.getDescTuple().startsWith(mdCallee.getThis())) { - nodeSet.addTupleSet(baseNodeSet); + // nodeSet.addTupleSet(baseNodeSet); + setNode.addTupleSet(baseNodeSet); + } } } @@ -4576,7 +4134,6 @@ public class LocationInference { NTuple argTuple = new NTuple(); if (needToGenerateInterLoc(argTupleSet)) { - System.out.println("3"); NTuple interTuple = getFlowGraph(mdCaller).createIntermediateNode().getDescTuple(); for (Iterator> idxIter = argTupleSet.iterator(); idxIter.hasNext();) { @@ -4609,12 +4166,14 @@ public class LocationInference { if (hasInFlowTo(calleeFlowGraph, paramNode, calleeReturnSet) || mdCallee.getModifiers().isNative()) { addParamNodeFlowingToReturnValue(mdCallee, paramNode); - nodeSet.addTupleSet(argTupleSet); + // nodeSet.addTupleSet(argTupleSet); + setNode.addTupleSet(argTupleSet); } } } + nodeSet.addTuple(setNode.getDescTuple()); // propagateFlowsFromCallee(min, md, min.getMethod()); System.out.println("min nodeSet=" + nodeSet); @@ -4807,7 +4366,6 @@ public class LocationInference { if (fd.isFinal()) { // if it is 'static final', no need to have flow node for the TOP // location - System.out.println("STATIC FINAL"); return null; } else { // if 'static', assign the default GLOBAL LOCATION to the first @@ -4966,7 +4524,6 @@ public class LocationInference { // creates edges from RHS to LHS NTuple interTuple = null; if (needToGenerateInterLoc(nodeSetRHS)) { - System.out.println("1"); interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); } @@ -4996,8 +4553,8 @@ public class LocationInference { NTuple callerLHSTuple = iter2.next(); globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, translateToLocTuple(md, callerLHSTuple)); - System.out.println("$$$ GLOBAL FLOW ADD=" + calleeReturnLocTuple + " -> " - + translateToLocTuple(md, callerLHSTuple)); + // System.out.println("$$$ GLOBAL FLOW ADD=" + calleeReturnLocTuple + " -> " + // + translateToLocTuple(md, callerLHSTuple)); } } } diff --git a/Robust/src/Analysis/SSJava/MethodSummary.java b/Robust/src/Analysis/SSJava/MethodSummary.java index 333b2240..ebf73397 100644 --- a/Robust/src/Analysis/SSJava/MethodSummary.java +++ b/Robust/src/Analysis/SSJava/MethodSummary.java @@ -58,16 +58,16 @@ public class MethodSummary extends LocationSummary { return mapParamIdxToInferLoc; } - public void setPCLoc(CompositeLocation pcLoc) { - this.pcLoc = pcLoc; + public void setPCLoc(CompositeLocation in) { + this.pcLoc = in; } public CompositeLocation getPCLoc() { return pcLoc; } - public void setRETURNLoc(CompositeLocation returnLoc) { - this.returnLoc = returnLoc; + public void setRETURNLoc(CompositeLocation in) { + this.returnLoc = in; } public CompositeLocation getRETURNLoc() { -- 2.34.1