X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=Robust%2Fsrc%2FAnalysis%2FSSJava%2FLocationInference.java;h=6575d4bad7708eca4a0669d04875f7e06c32dd4e;hb=52bd77482e98618483034a513931c50a870b9a47;hp=36645aa1c8ae24ee4cbf0b49f919dc1d3c6a94cb;hpb=13a63ea76172e2fd0ce7987bf81845c44c839d55;p=IRC.git diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index 36645aa1..6575d4ba 100644 --- a/Robust/src/Analysis/SSJava/LocationInference.java +++ b/Robust/src/Analysis/SSJava/LocationInference.java @@ -98,6 +98,8 @@ public class LocationInference { private Map> mapMethodInvokeNodeToBaseTuple; + private Map>> mapMethodInvokeNodeToPCLocTupleSet; + private Map mapMethodDescToMethodLocationInfo; private Map mapClassToLocationInfo; @@ -112,27 +114,49 @@ public class LocationInference { private Map mapDescToLocationSummary; + private Map> mapMethodDescToMethodInvokeNodeSet; + // 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; + private Map mapMethodDescriptorToSubGlobalFlowGraph; - public static final String GLOBALLOC = "GLOBALLOC"; + private Map, NTuple>> mapMethodInvokeNodeToMapCallerArgToCalleeArg; + + private Map mapMethodDescriptorToCompositeReturnCase; - public static final String TOPLOC = "TOPLOC"; + public static final String GLOBALLOC = "GLOBALLOC"; public static final String INTERLOC = "INTERLOC"; + public static final String PCLOC = "_PCLOC_"; + + public static final String RLOC = "_RLOC_"; + public static final Descriptor GLOBALDESC = new NameDescriptor(GLOBALLOC); - public static final Descriptor TOPDESC = new NameDescriptor(TOPLOC); + public static final Descriptor TOPDESC = new NameDescriptor(SSJavaAnalysis.TOP); + + public static final Descriptor BOTTOMDESC = new NameDescriptor(SSJavaAnalysis.BOTTOM); + + public static final Descriptor RETURNLOC = new NameDescriptor(RLOC); + + public static final Descriptor LITERALDESC = new NameDescriptor("LITERAL"); + + public static final HNode TOPHNODE = new HNode(TOPDESC); + + public static final HNode BOTTOMHNODE = new HNode(BOTTOMDESC); public static String newline = System.getProperty("line.separator"); LocationInfo curMethodInfo; + private boolean hasChanges = false; + boolean debug = true; - private static int locSeed = 0; + public static int locSeed = 0; + + private Stack arrayAccessNodeStack; public LocationInference(SSJavaAnalysis ssjava, State state) { this.ssjava = ssjava; @@ -167,7 +191,20 @@ public class LocationInference { this.mapDescToLocationSummary = new HashMap(); - mapMethodDescriptorToSubGlobalFlowGraph = new HashMap(); + this.mapMethodDescriptorToSubGlobalFlowGraph = new HashMap(); + + this.mapMethodInvokeNodeToMapCallerArgToCalleeArg = + new HashMap, NTuple>>(); + + this.mapMethodInvokeNodeToPCLocTupleSet = + new HashMap>>(); + + this.arrayAccessNodeStack = new Stack(); + + this.mapMethodDescToMethodInvokeNodeSet = + new HashMap>(); + + this.mapMethodDescriptorToCompositeReturnCase = new HashMap(); } @@ -212,17 +249,30 @@ public class LocationInference { public void inference() { - // 1) construct value flow graph + ssjava.init(); + + // construct value flow graph constructFlowGraph(); constructGlobalFlowGraph(); - System.exit(0); + checkReturnNodes(); + + assignCompositeLocation(); + updateFlowGraph(); + calculateExtraLocations(); + addAdditionalOrderingConstraints(); + + _debug_writeFlowGraph(); + + // System.exit(0); constructHierarchyGraph(); debug_writeHierarchyDotFiles(); + // System.exit(0); + simplifyHierarchyGraph(); debug_writeSimpleHierarchyDotFiles(); @@ -239,420 +289,1712 @@ public class LocationInference { debug_writeLattices(); + updateCompositeLocationAssignments(); + generateMethodSummary(); - System.exit(0); + generateAnnoatedCode(); - // 2) construct lattices - inferLattices(); + System.exit(0); - simplifyLattices(); + } - // 3) check properties - checkLattices(); + private void checkReturnNodes() { + LinkedList methodDescList = + (LinkedList) toanalyze_methodDescList.clone(); - // calculate RETURNLOC,PCLOC - calculateExtraLocations(); + while (!methodDescList.isEmpty()) { + MethodDescriptor md = methodDescList.removeLast(); - debug_writeLatticeDotFile(); + if (md.getReturnType() != null && !md.getReturnType().isVoid()) { + checkFlowNodeReturnThisField(md); + } + // // in this case, this method will return the composite location that starts with 'this' + // FlowGraph flowGraph = getFlowGraph(md); + // Set returnNodeSet = flowGraph.getReturnNodeSet(); + // } - // 4) generate annotated source codes - generateAnnoatedCode(); + } } - private void constructGlobalFlowGraph() { + private void updateFlowGraph() { - 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); + System.out.println("SSJAVA: Updating a flow graph: " + md); + propagateFlowsFromCalleesWithNoCompositeLocation(md); + } + } + } - FlowGraph flowGraph = getFlowGraph(md); - FlowGraph subGlobalFlowGraph = flowGraph.clone(); - mapMethodDescriptorToSubGlobalFlowGraph.put(md, subGlobalFlowGraph); + public Map, NTuple> getMapCallerArgToCalleeParam( + MethodInvokeNode min) { - addValueFlowsFromCalleeSubGlobalFlowGraph(md, subGlobalFlowGraph); + if (!mapMethodInvokeNodeToMapCallerArgToCalleeArg.containsKey(min)) { + mapMethodInvokeNodeToMapCallerArgToCalleeArg.put(min, + new HashMap, NTuple>()); + } - try { - subGlobalFlowGraph.writeGraph("_SUBGLOBAL"); - } catch (IOException e) { - e.printStackTrace(); - } - // FlowGraph fg = new FlowGraph(md, mapParamDescToIdx); - // mapMethodDescriptorToFlowGraph.put(md, fg); - // analyzeMethodBody(md.getClassDesc(), md); - } + return mapMethodInvokeNodeToMapCallerArgToCalleeArg.get(min); + } - } + public void addMapCallerArgToCalleeParam(MethodInvokeNode min, NTuple callerArg, + NTuple calleeParam) { + getMapCallerArgToCalleeParam(min).put(callerArg, calleeParam); + } - // DEBUG: write a global flow graph - MethodDescriptor mdContainingSSJavaLoop = ssjava.getMethodContainingSSJavaLoop(); - FlowGraph globalFlowGraph = getSubGlobalFlowGraph(mdContainingSSJavaLoop); - // System.out.println("GLOBAL NODE SET=" + globalFlowGraph.getNodeSet()); - assignCompositeLocation(globalFlowGraph); - try { - globalFlowGraph.writeGraph("_GLOBAL"); - } catch (IOException e) { - e.printStackTrace(); - } - // _debug_printGraph(); + private void assignCompositeLocation() { + calculateGlobalValueFlowCompositeLocation(); + translateCompositeLocationAssignmentToFlowGraph(); + } + private void translateCompositeLocationAssignmentToFlowGraph() { + System.out.println("\nSSJAVA: Translate composite location assignments to flow graphs:"); + MethodDescriptor methodEventLoopDesc = ssjava.getMethodContainingSSJavaLoop(); + translateCompositeLocationAssignmentToFlowGraph(methodEventLoopDesc); } - private void assignCompositeLocation(FlowGraph globalFlowGraph) { - Set nodeSet = globalFlowGraph.getNodeSet(); + private void translateCompositeLocationAssignmentToFlowGraph2() { + System.out.println("\nSSJAVA: Translate composite location assignments to flow graphs:"); + MethodDescriptor methodEventLoopDesc = ssjava.getMethodContainingSSJavaLoop(); + translateCompositeLocationAssignmentToFlowGraph(methodEventLoopDesc); + } - for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { - FlowNode flowNode = (FlowNode) iterator.next(); - Set inNodeSet = globalFlowGraph.getIncomingFlowNodeSet(flowNode); - Set reachableNodeSet = globalFlowGraph.getReachFlowNodeSetFrom(flowNode); + private void addAdditionalOrderingConstraints() { + System.out.println("\nSSJAVA: Add addtional ordering constriants:"); + MethodDescriptor methodEventLoopDesc = ssjava.getMethodContainingSSJavaLoop(); + addAddtionalOrderingConstraints(methodEventLoopDesc); + } - // System.out.println("flowNode=" + flowNode + " incoming=" + inNodeSet); - // System.out.println("reachableNodeSet=" + reachableNodeSet); + private void updateCompositeLocationAssignments() { - Map, Set>> mapPrefixToIncomingLocTupleSet = - new HashMap, Set>>(); + LinkedList methodDescList = + (LinkedList) toanalyze_methodDescList.clone(); - List> prefixList = new ArrayList>(); + while (!methodDescList.isEmpty()) { + MethodDescriptor md = methodDescList.removeLast(); - for (Iterator iterator2 = inNodeSet.iterator(); iterator2.hasNext();) { - FlowNode inNode = (FlowNode) iterator2.next(); + System.out.println("\n#updateCompositeLocationAssignments=" + md); - NTuple inNodeTuple = inNode.getCurrentDescTuple(); + FlowGraph flowGraph = getFlowGraph(md); - // CompositeLocation inNodeInferredLoc = - // generateInferredCompositeLocation(methodInfo, inNodeTuple); - // NTuple inNodeInferredLocTuple = inNodeInferredLoc.getTuple(); + MethodSummary methodSummary = getMethodSummary(md); - for (int i = 1; i < inNodeTuple.size(); i++) { - NTuple prefix = inNodeTuple.subList(0, i); - if (!prefixList.contains(prefix)) { - prefixList.add(prefix); - } + Set nodeSet = flowGraph.getNodeSet(); + for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + FlowNode node = (FlowNode) iterator.next(); + System.out.println("-node=" + node + " node.getDescTuple=" + node.getDescTuple()); + if (node.getCompositeLocation() != null) { + CompositeLocation compLoc = node.getCompositeLocation(); + CompositeLocation updatedCompLoc = updateCompositeLocation(compLoc); + node.setCompositeLocation(updatedCompLoc); + System.out.println("---updatedCompLoc1=" + updatedCompLoc); + } else { + NTuple descTuple = node.getDescTuple(); + System.out.println("update desc=" + descTuple); + CompositeLocation compLoc = convertToCompositeLocation(md, descTuple); + compLoc = updateCompositeLocation(compLoc); + node.setCompositeLocation(compLoc); + System.out.println("---updatedCompLoc2=" + compLoc); } - } - Collections.sort(prefixList, new Comparator>() { - public int compare(NTuple arg0, NTuple arg1) { - int s0 = arg0.size(); - int s1 = arg1.size(); - if (s0 > s1) { - return -1; - } else if (s0 == s1) { - return 0; - } else { - return 1; - } + if (node.isDeclaratonNode()) { + Descriptor localVarDesc = node.getDescTuple().get(0); + CompositeLocation compLoc = updateCompositeLocation(node.getCompositeLocation()); + methodSummary.addMapVarNameToInferCompLoc(localVarDesc, compLoc); } - }); + } - // find out reachable nodes that have the longest common prefix - for (int i = 0; i < prefixList.size(); i++) { - NTuple curPrefix = prefixList.get(i); - Set> reachableCommonPrefixSet = new HashSet>(); + // update PCLOC and RETURNLOC if they have a composite location assignment + if (methodSummary.getRETURNLoc() != null) { + methodSummary.setRETURNLoc(updateCompositeLocation(methodSummary.getRETURNLoc())); + } + if (methodSummary.getPCLoc() != null) { + methodSummary.setPCLoc(updateCompositeLocation(methodSummary.getPCLoc())); + } - for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) { - FlowNode reachableNode = (FlowNode) iterator2.next(); - NTuple reachLocTuple = reachableNode.getCurrentDescTuple(); - if (reachLocTuple.startsWith(curPrefix)) { - reachableCommonPrefixSet.add(reachLocTuple); - } - } + } - if (!reachableCommonPrefixSet.isEmpty()) { - // found reachable nodes that start with the prefix curPrefix - // need to assign a composite location - // System.out.println("-prefixList=" + prefixList); - // System.out.println("-reachableCommonPrefixSet=" + reachableCommonPrefixSet); - // System.out.println("-curPrefix=" + curPrefix); - - // first, check if there are more than one the set of locations that has - // the same length of the longest reachable prefix, no way to assign - // a composite location to the input local var - prefixSanityCheck(prefixList, i, globalFlowGraph, reachableNodeSet); - - MethodDescriptor topMethodDesc = globalFlowGraph.getMethodDescriptor(); - CompositeLocation newCompLoc = generateCompositeLocation(curPrefix, topMethodDesc); - - System.out.println("SET COMPOSITE LOCATION=" + newCompLoc + " to " + flowNode); - flowNode.setCompositeLocation(newCompLoc); + } + + private CompositeLocation updateCompositeLocation(CompositeLocation compLoc) { + CompositeLocation updatedCompLoc = new CompositeLocation(); + for (int i = 0; i < compLoc.getSize(); i++) { + Location loc = compLoc.get(i); + String nodeIdentifier = loc.getLocIdentifier(); + Descriptor enclosingDesc = loc.getDescriptor(); + String locName; + if (!enclosingDesc.equals(GLOBALDESC)) { + LocationSummary locSummary = getLocationSummary(enclosingDesc); + HierarchyGraph scGraph = getSkeletonCombinationHierarchyGraph(enclosingDesc); + if (scGraph != null) { + HNode curNode = scGraph.getCurrentHNode(nodeIdentifier); + if (curNode != null) { + nodeIdentifier = curNode.getName(); + } } + locName = locSummary.getLocationName(nodeIdentifier); + } else { + locName = nodeIdentifier; } - + Location updatedLoc = new Location(enclosingDesc, locName); + updatedCompLoc.addLocation(updatedLoc); } + return updatedCompLoc; } - private CompositeLocation generateCompositeLocation(NTuple curPrefix, - MethodDescriptor md) { - CompositeLocation newCompLoc = new CompositeLocation(); + private void translateCompositeLocationAssignmentToFlowGraph(MethodDescriptor mdCaller) { - Descriptor enclosingDesc = md; - for (int i = 0; i < curPrefix.size(); i++) { - Descriptor curDesc = curPrefix.get(i); - Location loc = new Location(enclosingDesc, curDesc.getSymbol()); - newCompLoc.addLocation(loc); - if (i == 0) { - VarDescriptor varDesc = (VarDescriptor) curDesc; - enclosingDesc = varDesc.getType().getClassDesc(); - } else { - FieldDescriptor fieldDesc = (FieldDescriptor) curDesc; - enclosingDesc = fieldDesc.getType().getClassDesc(); + System.out.println("\n\n###translateCompositeLocationAssignmentToFlowGraph mdCaller=" + + 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(); + for (Iterator iterator = methodLocSet.iterator(); iterator.hasNext();) { + Location methodLoc = (Location) iterator.next(); + if (methodLoc.getDescriptor().equals(mdCaller)) { + CompositeLocation inferCompLoc = callerMapLocToCompLoc.get(methodLoc); + assignCompositeLocationToFlowGraph(callerFlowGraph, methodLoc, inferCompLoc); } } - LocationDescriptor newLocDescriptor = generateNewLocationDescriptor(); - newLocDescriptor.setEnclosingClassDesc((ClassDescriptor) enclosingDesc); + Set minSet = mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller); - Location newLoc = new Location(enclosingDesc, newLocDescriptor.getSymbol()); - newLoc.setLocDescriptor(newLocDescriptor); - newCompLoc.addLocation(newLoc); + Set calleeSet = new HashSet(); + for (Iterator iterator = minSet.iterator(); iterator.hasNext();) { + MethodInvokeNode min = (MethodInvokeNode) iterator.next(); + // need to translate a composite location that is started with the base + // tuple of 'min'. + translateMapLocationToInferCompositeLocationToCalleeGraph(callerGlobalFlowGraph, min); + MethodDescriptor mdCallee = min.getMethod(); + calleeSet.add(mdCallee); + + } + + for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) { + MethodDescriptor callee = (MethodDescriptor) iterator.next(); + translateCompositeLocationAssignmentToFlowGraph(callee); + } - return newCompLoc; } - private void prefixSanityCheck(List> prefixList, int curIdx, - FlowGraph globalFlowGraph, Set reachableNodeSet) { + private CompositeLocation translateArgCompLocToParamCompLoc(MethodInvokeNode min, + CompositeLocation argCompLoc) { + + System.out.println("--------translateArgCompLocToParamCompLoc argCompLoc=" + argCompLoc); + MethodDescriptor mdCallee = min.getMethod(); + FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); - NTuple curPrefix = prefixList.get(curIdx); + NTuple argLocTuple = argCompLoc.getTuple(); + Location argLocalLoc = argLocTuple.get(0); - for (int i = curIdx + 1; i < prefixList.size(); i++) { - NTuple prefixTuple = prefixList.get(i); + Map> mapIdxToArgTuple = mapMethodInvokeNodeToArgIdxMap.get(min); + Set idxSet = mapIdxToArgTuple.keySet(); + for (Iterator iterator2 = idxSet.iterator(); iterator2.hasNext();) { + Integer idx = (Integer) iterator2.next(); - if (curPrefix.startsWith(prefixTuple)) { + if (idx == 0 && !min.getMethod().isStatic()) { continue; } - for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) { - FlowNode reachableNode = (FlowNode) iterator2.next(); - NTuple reachLocTuple = reachableNode.getCurrentDescTuple(); - if (reachLocTuple.startsWith(prefixTuple)) { - throw new Error( - "Failed to generate a composite location because there is more than one prefix which is reach to the current node."); + NTuple argTuple = mapIdxToArgTuple.get(idx); + if (argTuple.size() > 0 && argTuple.get(0).equals(argLocalLoc.getLocDescriptor())) { + // it matches with the current argument composite location + // so what is the corresponding parameter local descriptor? + FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx); + System.out.println("----------found paramNode=" + paramNode); + NTuple paramDescTuple = paramNode.getCurrentDescTuple(); + + NTuple newParamTupleFromArgTuple = translateToLocTuple(mdCallee, paramDescTuple); + for (int i = 1; i < argLocTuple.size(); i++) { + newParamTupleFromArgTuple.add(argLocTuple.get(i)); } + + System.out.println("-----------newParamTuple=" + newParamTupleFromArgTuple); + return new CompositeLocation(newParamTupleFromArgTuple); + } } - + return null; } - private void addValueFlowsFromCalleeSubGlobalFlowGraph(MethodDescriptor mdCaller, - FlowGraph subGlobalFlowGraph) { + private void addAddtionalOrderingConstraints(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 + // First, assign a composite location to a node in the flow graph + GlobalFlowGraph callerGlobalFlowGraph = getSubGlobalFlowGraph(mdCaller); - Set setMethodInvokeNode = getMethodInvokeNodeSet(mdCaller); + FlowGraph callerFlowGraph = getFlowGraph(mdCaller); + Map callerMapLocToCompLoc = + callerGlobalFlowGraph.getMapLocationToInferCompositeLocation(); + Set methodLocSet = callerMapLocToCompLoc.keySet(); - for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) { + 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(); - 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); - } + 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); + } else { + // if the return loc set was empty and later pcloc was connected to the return loc + // need to make sure that return loc reflects to this changes. + FlowReturnNode flowReturnNode = callerFlowGraph.getFlowReturnNode(min); + if (flowReturnNode != null && flowReturnNode.getReturnTupleSet().isEmpty()) { + + if (needToUpdateReturnLocHolder(min.getMethod(), flowReturnNode)) { + NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); + NTuple newReturnTuple = baseTuple.clone(); + flowReturnNode.addTuple(newReturnTuple); + } - 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); - 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); + for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) { + MethodDescriptor callee = (MethodDescriptor) iterator.next(); + addAddtionalOrderingConstraints(callee); } } - private void addValueFlowsFromCalleeParam(MethodInvokeNode min, FlowGraph calleeSubGlobalGraph, - FlowNode paramNode, FlowGraph callerSubGlobalGraph, NTuple argTuple, - NTuple baseTuple) { + private boolean needToUpdateReturnLocHolder(MethodDescriptor mdCallee, + FlowReturnNode flowReturnNode) { + FlowGraph fg = getFlowGraph(mdCallee); + MethodSummary summary = getMethodSummary(mdCallee); + CompositeLocation returnCompLoc = summary.getRETURNLoc(); + NTuple returnDescTuple = translateToDescTuple(returnCompLoc.getTuple()); + Set incomingNodeToReturnNode = + fg.getIncomingFlowNodeSet(fg.getFlowNode(returnDescTuple)); + for (Iterator iterator = incomingNodeToReturnNode.iterator(); iterator.hasNext();) { + FlowNode inNode = (FlowNode) iterator.next(); + if (inNode.getDescTuple().get(0).equals(mdCallee.getThis())) { + return true; + } + } + return false; + } - Set visited = new HashSet(); + private void addMapMethodDescToMethodInvokeNodeSet(MethodInvokeNode min) { + MethodDescriptor md = min.getMethod(); + if (!mapMethodDescToMethodInvokeNodeSet.containsKey(md)) { + mapMethodDescToMethodInvokeNodeSet.put(md, new HashSet()); + } + mapMethodDescToMethodInvokeNodeSet.get(md).add(min); + } - visited.add(paramNode); - recurAddValueFlowsFromCalleeParam(min, calleeSubGlobalGraph, paramNode, callerSubGlobalGraph, - argTuple, visited, baseTuple); + private Set getMethodInvokeNodeSetByMethodDesc(MethodDescriptor md) { + if (!mapMethodDescToMethodInvokeNodeSet.containsKey(md)) { + mapMethodDescToMethodInvokeNodeSet.put(md, new HashSet()); + } + return mapMethodDescToMethodInvokeNodeSet.get(md); } - private void recurAddValueFlowsFromCalleeParam(MethodInvokeNode min, - FlowGraph calleeSubGlobalGraph, FlowNode calleeSrcNode, FlowGraph callerSubGlobalGraph, - NTuple callerSrcTuple, Set visited, NTuple baseTuple) { + private void addOrderingConstraintFromCompLocParamToArg(MethodDescriptor mdCaller, + MethodInvokeNode min) { + System.out.println("-addOrderingConstraintFromCompLocParamToArg=" + min.printNode(0)); - MethodDescriptor mdCallee = calleeSubGlobalGraph.getMethodDescriptor(); + GlobalFlowGraph globalGraph = getSubGlobalFlowGraph(ssjava.getMethodContainingSSJavaLoop()); - // Set edgeSet = calleeSubGlobalGraph.getOutEdgeSet(calleeSrcNode); - Set edgeSet = calleeSubGlobalGraph.getOutEdgeSetStartingFrom(calleeSrcNode); - for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) { - FlowEdge flowEdge = (FlowEdge) iterator.next(); + Set> pcLocTupleSet = getPCLocTupleSet(min); - NTuple srcDescTuple = flowEdge.getInitTuple(); - NTuple dstDescTuple = flowEdge.getEndTuple(); + MethodDescriptor mdCallee = min.getMethod(); - FlowNode dstNode = calleeSubGlobalGraph.getFlowNode(dstDescTuple); + FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); + for (int idx = 0; idx < calleeFlowGraph.getNumParameters(); idx++) { + FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx); + NTuple globalParamLocTuple = + translateToLocTuple(mdCallee, paramNode.getDescTuple()); + translateToLocTuple(mdCallee, paramNode.getDescTuple()); + CompositeLocation compLoc = paramNode.getCompositeLocation(); + System.out.println("---paramNode=" + paramNode + " compLoc=" + compLoc); + if (compLoc != null) { + NTuple argTuple = getNodeTupleByArgIdx(min, idx); + NTuple globalArgLocTuple = translateToLocTuple(mdCaller, argTuple); + + 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); + } + } - 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); - } + for (Iterator iterator = pcLocTupleSet.iterator(); iterator.hasNext();) { + NTuple pcLocTuple = (NTuple) iterator.next(); + + 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); + } + } - 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); + private boolean isLiteralValueLocTuple(NTuple locTuple) { + return locTuple.get(0).getLocDescriptor().equals(LITERALDESC); + } - if (!visited.contains(dstNode)) { - visited.add(dstNode); - recurAddValueFlowsFromCalleeParam(min, calleeSubGlobalGraph, dstNode, callerSubGlobalGraph, - dstDescTuple, visited, baseTuple); - } + public void assignCompositeLocationToFlowGraph(FlowGraph flowGraph, Location loc, + CompositeLocation inferCompLoc) { + Descriptor localDesc = loc.getLocDescriptor(); + Set nodeSet = flowGraph.getNodeSet(); + for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + FlowNode node = (FlowNode) iterator.next(); + if (node.getDescTuple().startsWith(localDesc) + && !node.getDescTuple().get(0).equals(LITERALDESC)) { + // need to assign the inferred composite location to this node + CompositeLocation newCompLoc = generateCompositeLocation(node.getDescTuple(), inferCompLoc); + node.setCompositeLocation(newCompLoc); + System.out.println("SET Node=" + node + " inferCompLoc=" + newCompLoc); + } } - } - private NTuple translateToCaller(MethodInvokeNode min, int paramIdx, - NTuple srcDescTuple) { + private CompositeLocation generateCompositeLocation(NTuple nodeDescTuple, + CompositeLocation inferCompLoc) { - NTuple callerTuple = new NTuple(); + System.out.println("generateCompositeLocation=" + nodeDescTuple + " with inferCompLoc=" + + inferCompLoc); - NTuple argTuple = mapMethodInvokeNodeToArgIdxMap.get(min).get(paramIdx); + CompositeLocation newCompLoc = new CompositeLocation(); + for (int i = 0; i < inferCompLoc.getSize(); i++) { + newCompLoc.addLocation(inferCompLoc.get(i)); + } - for (int i = 0; i < argTuple.size(); i++) { - callerTuple.add(argTuple.get(i)); + Descriptor lastDescOfPrefix = nodeDescTuple.get(0); + Descriptor enclosingDescriptor; + if (lastDescOfPrefix instanceof InterDescriptor) { + enclosingDescriptor = null; + } else { + enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc(); } - for (int i = 1; i < srcDescTuple.size(); i++) { - callerTuple.add(srcDescTuple.get(i)); + for (int i = 1; i < nodeDescTuple.size(); i++) { + Descriptor desc = nodeDescTuple.get(i); + Location locElement = new Location(enclosingDescriptor, desc); + newCompLoc.addLocation(locElement); + + enclosingDescriptor = ((FieldDescriptor) desc).getClassDescriptor(); } - return callerTuple; + return newCompLoc; } - private NTuple translateToCaller(NTuple dstDescTuple, - NTuple baseTuple) { - NTuple callerDescTuple = new NTuple(); + private void translateMapLocationToInferCompositeLocationToCalleeGraph( + GlobalFlowGraph callerGraph, MethodInvokeNode min) { - callerDescTuple.addAll(baseTuple); - for (int i = 1; i < dstDescTuple.size(); i++) { - callerDescTuple.add(dstDescTuple.get(i)); - } + MethodDescriptor mdCallee = min.getMethod(); + MethodDescriptor mdCaller = callerGraph.getMethodDescriptor(); + Map callerMapLocToCompLoc = + callerGraph.getMapLocationToInferCompositeLocation(); - return callerDescTuple; - } + Map> mapIdxToArgTuple = mapMethodInvokeNodeToArgIdxMap.get(min); - 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()); - } + FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); + GlobalFlowGraph calleeGlobalGraph = getSubGlobalFlowGraph(mdCallee); + + NTuple baseLocTuple = null; + if (mapMethodInvokeNodeToBaseTuple.containsKey(min)) { + baseLocTuple = translateToLocTuple(mdCaller, mapMethodInvokeNodeToBaseTuple.get(min)); } - return mapDescToLocationSummary.get(d); - } - private void generateMethodSummary() { + 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); - Set keySet = md2lattice.keySet(); + Set keySet = callerMapLocToCompLoc.keySet(); for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { - MethodDescriptor md = (MethodDescriptor) iterator.next(); + Location key = (Location) iterator.next(); + CompositeLocation callerCompLoc = callerMapLocToCompLoc.get(key); + + if (!key.getDescriptor().equals(mdCaller)) { + + CompositeLocation newCalleeCompLoc; + if (baseLocTuple != null && callerCompLoc.getTuple().startsWith(baseLocTuple)) { + // System.out.println("-----need to translate callerCompLoc=" + callerCompLoc + // + " with baseTuple=" + baseLocTuple); + newCalleeCompLoc = + translateCompositeLocationToCallee(callerCompLoc, baseLocTuple, mdCallee); + + calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, newCalleeCompLoc); + System.out.println("1---key=" + key + " callerCompLoc=" + callerCompLoc + + " newCalleeCompLoc=" + newCalleeCompLoc); + System.out.println("-----caller=" + mdCaller + " callee=" + mdCallee); + if (!newCalleeCompLoc.get(0).getDescriptor().equals(mdCallee)) { + System.exit(0); + } - System.out.println("\nSSJAVA: generate method summary: " + md); + // System.out.println("-----baseLoctuple=" + baseLocTuple); + } else { + // check if it is the global access + Location compLocFirstElement = callerCompLoc.getTuple().get(0); + if (compLocFirstElement.getDescriptor().equals(mdCallee) + && compLocFirstElement.getLocDescriptor().equals(GLOBALDESC)) { - FlowGraph flowGraph = getFlowGraph(md); - MethodSummary methodSummary = getMethodSummary(md); + newCalleeCompLoc = new CompositeLocation(); + Location newMethodLoc = new Location(mdCallee, GLOBALDESC); - // construct a parameter mapping that maps a parameter descriptor to an inferred composite - // location + newCalleeCompLoc.addLocation(newMethodLoc); + for (int i = 1; i < callerCompLoc.getSize(); i++) { + newCalleeCompLoc.addLocation(callerCompLoc.get(i)); + } + calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, newCalleeCompLoc); + System.out.println("2---key=" + key + " callerCompLoc=" + callerCompLoc + + " newCalleeCompLoc=" + newCalleeCompLoc); + System.out.println("-----caller=" + mdCaller + " callee=" + mdCallee); - for (int paramIdx = 0; paramIdx < flowGraph.getNumParameters(); paramIdx++) { - FlowNode flowNode = flowGraph.getParamFlowNode(paramIdx); - NTuple locTuple = flowNode.getLocTuple(); + } else { + int paramIdx = getParamIdx(callerCompLoc, mapIdxToArgTuple); + if (paramIdx == -1) { + // here, the first element of the current composite location comes from the current + // callee + // so transfer the same composite location to the callee + if (!calleeGlobalGraph.contrainsInferCompositeLocationMapKey(key)) { + if (callerCompLoc.get(0).getDescriptor().equals(mdCallee)) { + System.out.println("3---key=" + key + " callerCompLoc=" + callerCompLoc + + " newCalleeCompLoc=" + callerCompLoc); + System.out.println("-----caller=" + mdCaller + " callee=" + mdCallee); + calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, callerCompLoc); + } else { + System.out.println("3---SKIP key=" + key + " callerCompLoc=" + callerCompLoc); + } + } + continue; + } + + // It is the case where two parameters have relative orderings between them by having + // composite locations + // if we found the param idx, it means that the first part of the caller composite + // location corresponds to the one of arguments. + // for example, if the caller argument is <,> + // and the current caller composite location mapping + // <,,> + // and the parameter which matches with the caller argument is 'Br brParam' + // then, the translated callee composite location will be <,> + NTuple argTuple = mapIdxToArgTuple.get(paramIdx); + + FlowNode paramFlowNode = calleeFlowGraph.getParamFlowNode(paramIdx); + NTuple paramLocTuple = + translateToLocTuple(mdCallee, paramFlowNode.getDescTuple()); + newCalleeCompLoc = new CompositeLocation(); + for (int i = 0; i < paramLocTuple.size(); i++) { + newCalleeCompLoc.addLocation(paramLocTuple.get(i)); + } + for (int i = argTuple.size(); i < callerCompLoc.getSize(); i++) { + newCalleeCompLoc.addLocation(callerCompLoc.get(i)); + } + calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, newCalleeCompLoc); + System.out.println("4---key=" + key + " callerCompLoc=" + callerCompLoc + + " newCalleeCompLoc=" + newCalleeCompLoc); + System.out.println("-----caller=" + mdCaller + " callee=" + mdCallee); + + // System.out.println("-----argTuple=" + argTuple + " caller=" + mdCaller + + // " callee=" + // + mdCallee); + // System.out.println("-----paramIdx=" + paramIdx + " paramFlowNode=" + paramFlowNode); + + } - CompositeLocation assignedCompLoc = flowNode.getCompositeLocation(); - CompositeLocation inferredCompLoc; - if (assignedCompLoc != null) { - inferredCompLoc = translateCompositeLocation(assignedCompLoc); - } else { - Location loc = locTuple.get(0); - inferredCompLoc = new CompositeLocation(loc); } - System.out.println("-paramIdx=" + paramIdx + " infer=" + inferredCompLoc); - methodSummary.addMapParamIdxToInferLoc(paramIdx, inferredCompLoc); - } + } } - } + // System.out.println("-----*AFTER TRANSLATING COMP LOC MAPPING, CALLEE MAPPING=" + // + calleeGlobalGraph.getMapLocationToInferCompositeLocation()); - private CompositeLocation translateCompositeLocation(CompositeLocation compLoc) { - CompositeLocation newCompLoc = new CompositeLocation(); + System.out.println("#ASSIGN COMP LOC TO CALLEE PARAMS: callee=" + mdCallee + " caller=" + + mdCaller); + // If the location of an argument has a composite location + // need to assign a proper composite location to the corresponding callee parameter + Set idxSet = mapIdxToArgTuple.keySet(); + for (Iterator iterator = idxSet.iterator(); iterator.hasNext();) { + Integer idx = (Integer) iterator.next(); - // 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(); + if (idx == 0 && !min.getMethod().isStatic()) { + continue; + } - 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); - } + NTuple argTuple = mapIdxToArgTuple.get(idx); + System.out.println("-argTuple=" + argTuple + " idx=" + idx); + if (argTuple.size() > 0) { + // check if an arg tuple has been already assigned to a composite location + NTuple argLocTuple = translateToLocTuple(mdCaller, argTuple); + Location argLocalLoc = argLocTuple.get(0); - return newCompLoc; - } + // if (!isPrimitiveType(argTuple)) { + if (callerMapLocToCompLoc.containsKey(argLocalLoc)) { - private void debug_writeLattices() { + CompositeLocation callerCompLoc = callerMapLocToCompLoc.get(argLocalLoc); + for (int i = 1; i < argLocTuple.size(); i++) { + callerCompLoc.addLocation(argLocTuple.get(i)); + } - Set keySet = mapDescriptorToSimpleLattice.keySet(); - for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + System.out.println("---callerCompLoc=" + callerCompLoc); + + // if (baseLocTuple != null && callerCompLoc.getTuple().startsWith(baseLocTuple)) { + + FlowNode calleeParamFlowNode = calleeFlowGraph.getParamFlowNode(idx); + + NTuple calleeParamDescTuple = calleeParamFlowNode.getDescTuple(); + NTuple calleeParamLocTuple = + translateToLocTuple(mdCallee, calleeParamDescTuple); + + int refParamIdx = getParamIdx(callerCompLoc, mapIdxToArgTuple); + System.out.println("-----paramIdx=" + refParamIdx); + if (refParamIdx == 0 && !mdCallee.isStatic()) { + + System.out.println("-------need to translate callerCompLoc=" + callerCompLoc + + " with baseTuple=" + baseLocTuple + " calleeParamLocTuple=" + + calleeParamLocTuple); + + CompositeLocation newCalleeCompLoc = + translateCompositeLocationToCallee(callerCompLoc, baseLocTuple, mdCallee); + + calleeGlobalGraph.addMapLocationToInferCompositeLocation(calleeParamLocTuple.get(0), + newCalleeCompLoc); + + System.out.println("---------key=" + calleeParamLocTuple.get(0) + " callerCompLoc=" + + callerCompLoc + " newCalleeCompLoc=" + newCalleeCompLoc); + + } else if (refParamIdx != -1) { + // the first element of an argument composite location matches with one of paramtere + // composite locations + + System.out.println("-------param match case="); + + NTuple argTupleRef = mapIdxToArgTuple.get(refParamIdx); + FlowNode refParamFlowNode = calleeFlowGraph.getParamFlowNode(refParamIdx); + NTuple refParamLocTuple = + translateToLocTuple(mdCallee, refParamFlowNode.getDescTuple()); + + System.out.println("---------refParamLocTuple=" + refParamLocTuple + + " from argTupleRef=" + argTupleRef); + + CompositeLocation newCalleeCompLoc = new CompositeLocation(); + for (int i = 0; i < refParamLocTuple.size(); i++) { + newCalleeCompLoc.addLocation(refParamLocTuple.get(i)); + } + for (int i = argTupleRef.size(); i < callerCompLoc.getSize(); i++) { + newCalleeCompLoc.addLocation(callerCompLoc.get(i)); + } + + calleeGlobalGraph.addMapLocationToInferCompositeLocation(calleeParamLocTuple.get(0), + newCalleeCompLoc); + + calleeParamFlowNode.setCompositeLocation(newCalleeCompLoc); + System.out.println("-----------key=" + calleeParamLocTuple.get(0) + " callerCompLoc=" + + callerCompLoc + " newCalleeCompLoc=" + newCalleeCompLoc); + + } else { + CompositeLocation newCalleeCompLoc = + calculateCompositeLocationFromSubGlobalGraph(mdCallee, calleeParamFlowNode); + if (newCalleeCompLoc != null) { + calleeGlobalGraph.addMapLocationToInferCompositeLocation(calleeParamLocTuple.get(0), + newCalleeCompLoc); + calleeParamFlowNode.setCompositeLocation(newCalleeCompLoc); + } + } + + System.out.println("-----------------calleeParamFlowNode=" + + calleeParamFlowNode.getCompositeLocation()); + + // } + + } + } + + } + + } + + private CompositeLocation calculateCompositeLocationFromSubGlobalGraph(MethodDescriptor md, + FlowNode paramNode) { + + System.out.println("#############################################################"); + System.out.println("calculateCompositeLocationFromSubGlobalGraph=" + paramNode); + + GlobalFlowGraph subGlobalFlowGraph = getSubGlobalFlowGraph(md); + NTuple paramLocTuple = translateToLocTuple(md, paramNode.getDescTuple()); + GlobalFlowNode paramGlobalNode = subGlobalFlowGraph.getFlowNode(paramLocTuple); + + List> prefixList = calculatePrefixList(subGlobalFlowGraph, paramGlobalNode); + + Location prefixLoc = paramLocTuple.get(0); + + Set reachableNodeSet = + subGlobalFlowGraph.getReachableNodeSetByPrefix(paramGlobalNode.getLocTuple().get(0)); + // Set reachNodeSet = globalFlowGraph.getReachableNodeSetFrom(node); + + // System.out.println("node=" + node + " prefixList=" + prefixList); + + for (int i = 0; i < prefixList.size(); i++) { + NTuple curPrefix = prefixList.get(i); + Set> reachableCommonPrefixSet = new HashSet>(); + + for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) { + GlobalFlowNode reachNode = (GlobalFlowNode) iterator2.next(); + if (reachNode.getLocTuple().startsWith(curPrefix)) { + reachableCommonPrefixSet.add(reachNode.getLocTuple()); + } + } + // System.out.println("reachableCommonPrefixSet=" + reachableCommonPrefixSet); + + if (!reachableCommonPrefixSet.isEmpty()) { + + MethodDescriptor curPrefixFirstElementMethodDesc = + (MethodDescriptor) curPrefix.get(0).getDescriptor(); + + MethodDescriptor nodePrefixLocFirstElementMethodDesc = + (MethodDescriptor) prefixLoc.getDescriptor(); + + // System.out.println("curPrefixFirstElementMethodDesc=" + + // curPrefixFirstElementMethodDesc); + // System.out.println("nodePrefixLocFirstElementMethodDesc=" + // + nodePrefixLocFirstElementMethodDesc); + + if (curPrefixFirstElementMethodDesc.equals(nodePrefixLocFirstElementMethodDesc) + || isTransitivelyCalledFrom(nodePrefixLocFirstElementMethodDesc, + curPrefixFirstElementMethodDesc)) { + + // TODO + // if (!node.getLocTuple().startsWith(curPrefix.get(0))) { + + Location curPrefixLocalLoc = curPrefix.get(0); + if (subGlobalFlowGraph.mapLocationToInferCompositeLocation.containsKey(curPrefixLocalLoc)) { + // in this case, the local variable of the current prefix has already got a composite + // location + // so we just ignore the current composite location. + + // System.out.println("HERE WE DO NOT ASSIGN A COMPOSITE LOCATION TO =" + node + // + " DUE TO " + curPrefix); + return null; + } + + if (!needToGenerateCompositeLocation(paramGlobalNode, curPrefix)) { + System.out.println("NO NEED TO GENERATE COMP LOC to " + paramGlobalNode + + " with prefix=" + curPrefix); + // System.out.println("prefixList=" + prefixList); + // System.out.println("reachableNodeSet=" + reachableNodeSet); + return null; + } + + Location targetLocalLoc = paramGlobalNode.getLocTuple().get(0); + CompositeLocation newCompLoc = generateCompositeLocation(curPrefix); + System.out.println("NEED TO ASSIGN COMP LOC TO " + paramGlobalNode + " with prefix=" + + curPrefix); + System.out.println("-targetLocalLoc=" + targetLocalLoc + " - newCompLoc=" + newCompLoc); + + // makes sure that a newly generated location appears in the hierarchy graph + for (int compIdx = 0; compIdx < newCompLoc.getSize(); compIdx++) { + Location curLoc = newCompLoc.get(compIdx); + getHierarchyGraph(curLoc.getDescriptor()).getHNode(curLoc.getLocDescriptor()); + } + + subGlobalFlowGraph.addMapLocationToInferCompositeLocation(targetLocalLoc, newCompLoc); + + return newCompLoc; + + } + + } + + } + return null; + } + + private int getParamIdx(CompositeLocation compLoc, + Map> mapIdxToArgTuple) { + + // if the composite location is started with the argument descriptor + // return the argument's index. o.t. return -1 + + Set keySet = mapIdxToArgTuple.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Integer key = (Integer) iterator.next(); + NTuple argTuple = mapIdxToArgTuple.get(key); + if (argTuple.size() > 0 && translateToDescTuple(compLoc.getTuple()).startsWith(argTuple)) { + System.out.println("compLoc.getTuple=" + compLoc + " is started with " + argTuple); + return key.intValue(); + } + } + + return -1; + } + + private boolean isPrimitiveType(NTuple argTuple) { + + Descriptor lastDesc = argTuple.get(argTuple.size() - 1); + + if (lastDesc instanceof FieldDescriptor) { + return ((FieldDescriptor) lastDesc).getType().isPrimitive(); + } else if (lastDesc instanceof VarDescriptor) { + return ((VarDescriptor) lastDesc).getType().isPrimitive(); + } else if (lastDesc instanceof InterDescriptor) { + return true; + } + + return false; + } + + private CompositeLocation translateCompositeLocationToCallee(CompositeLocation callerCompLoc, + NTuple baseLocTuple, MethodDescriptor mdCallee) { + + CompositeLocation newCalleeCompLoc = new CompositeLocation(); + + Location calleeThisLoc = new Location(mdCallee, mdCallee.getThis()); + newCalleeCompLoc.addLocation(calleeThisLoc); + + // remove the base tuple from the caller + // ex; In the method invoation foo.bar.methodA(), the callee will have the composite location + // ,which is relative to the 'this' variable, + for (int i = baseLocTuple.size(); i < callerCompLoc.getSize(); i++) { + newCalleeCompLoc.addLocation(callerCompLoc.get(i)); + } + + return newCalleeCompLoc; + + } + + private void calculateGlobalValueFlowCompositeLocation() { + + System.out.println("SSJAVA: Calculate composite locations in the global value flow graph"); + MethodDescriptor methodDescEventLoop = ssjava.getMethodContainingSSJavaLoop(); + GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(methodDescEventLoop); + + Set calculatedPrefixSet = new HashSet(); + + Set nodeSet = globalFlowGraph.getNodeSet(); + + next: for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + GlobalFlowNode node = (GlobalFlowNode) iterator.next(); + + Location prefixLoc = node.getLocTuple().get(0); + + if (calculatedPrefixSet.contains(prefixLoc)) { + // the prefix loc has been already assigned to a composite location + continue; + } + + calculatedPrefixSet.add(prefixLoc); + + // Set incomingNodeSet = globalFlowGraph.getIncomingNodeSet(node); + List> prefixList = calculatePrefixList(globalFlowGraph, node); + + Set reachableNodeSet = + globalFlowGraph.getReachableNodeSetByPrefix(node.getLocTuple().get(0)); + // Set reachNodeSet = globalFlowGraph.getReachableNodeSetFrom(node); + + // System.out.println("node=" + node + " prefixList=" + prefixList); + System.out.println("---prefixList=" + prefixList); + + nextprefix: for (int i = 0; i < prefixList.size(); i++) { + NTuple curPrefix = prefixList.get(i); + System.out.println("---curPrefix=" + curPrefix); + Set> reachableCommonPrefixSet = new HashSet>(); + + for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) { + GlobalFlowNode reachNode = (GlobalFlowNode) iterator2.next(); + if (reachNode.getLocTuple().startsWith(curPrefix)) { + reachableCommonPrefixSet.add(reachNode.getLocTuple()); + } + } + // System.out.println("reachableCommonPrefixSet=" + reachableCommonPrefixSet); + + if (!reachableCommonPrefixSet.isEmpty()) { + + MethodDescriptor curPrefixFirstElementMethodDesc = + (MethodDescriptor) curPrefix.get(0).getDescriptor(); + + MethodDescriptor nodePrefixLocFirstElementMethodDesc = + (MethodDescriptor) prefixLoc.getDescriptor(); + + // System.out.println("curPrefixFirstElementMethodDesc=" + + // curPrefixFirstElementMethodDesc); + // System.out.println("nodePrefixLocFirstElementMethodDesc=" + // + nodePrefixLocFirstElementMethodDesc); + + if (curPrefixFirstElementMethodDesc.equals(nodePrefixLocFirstElementMethodDesc) + || isTransitivelyCalledFrom(nodePrefixLocFirstElementMethodDesc, + curPrefixFirstElementMethodDesc)) { + + // TODO + // if (!node.getLocTuple().startsWith(curPrefix.get(0))) { + + Location curPrefixLocalLoc = curPrefix.get(0); + if (globalFlowGraph.mapLocationToInferCompositeLocation.containsKey(curPrefixLocalLoc)) { + // in this case, the local variable of the current prefix has already got a composite + // location + // so we just ignore the current composite location. + + // System.out.println("HERE WE DO NOT ASSIGN A COMPOSITE LOCATION TO =" + node + // + " DUE TO " + curPrefix); + + continue next; + } + + if (!needToGenerateCompositeLocation(node, curPrefix)) { + System.out.println("NO NEED TO GENERATE COMP LOC to " + node + " with prefix=" + + curPrefix); + // System.out.println("prefixList=" + prefixList); + // System.out.println("reachableNodeSet=" + reachableNodeSet); + continue nextprefix; + } + + Location targetLocalLoc = node.getLocTuple().get(0); + CompositeLocation newCompLoc = generateCompositeLocation(curPrefix); + System.out.println("NEED TO ASSIGN COMP LOC TO " + node + " with prefix=" + curPrefix); + System.out.println("-targetLocalLoc=" + targetLocalLoc + " - newCompLoc=" + + newCompLoc); + globalFlowGraph.addMapLocationToInferCompositeLocation(targetLocalLoc, newCompLoc); + // } + + continue next; + // } + + } + + } + + } + + } + } + + private boolean checkFlowNodeReturnThisField(MethodDescriptor md) { + + MethodDescriptor methodDescEventLoop = ssjava.getMethodContainingSSJavaLoop(); + GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(methodDescEventLoop); + + FlowGraph flowGraph = getFlowGraph(md); + + ClassDescriptor enclosingDesc = getClassTypeDescriptor(md.getThis()); + if (enclosingDesc == null) { + return false; + } + + int count = 0; + Set returnNodeSet = flowGraph.getReturnNodeSet(); + Set globalReturnNodeSet = new HashSet(); + for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { + FlowNode flowNode = (FlowNode) iterator.next(); + NTuple locTuple = translateToLocTuple(md, flowNode.getDescTuple()); + GlobalFlowNode globalReturnNode = globalFlowGraph.getFlowNode(locTuple); + globalReturnNodeSet.add(globalReturnNode); + + List> prefixList = calculatePrefixList(globalFlowGraph, globalReturnNode); + for (int i = 0; i < prefixList.size(); i++) { + NTuple curPrefix = prefixList.get(i); + ClassDescriptor cd = + getClassTypeDescriptor(curPrefix.get(curPrefix.size() - 1).getLocDescriptor()); + if (cd != null && cd.equals(enclosingDesc)) { + count++; + break; + } + } + + } + + if (count == returnNodeSet.size()) { + // in this case, all return nodes in the method returns values coming from a location that + // starts with "this" + + System.out.println("$$$SET RETURN LOC TRUE=" + md); + mapMethodDescriptorToCompositeReturnCase.put(md, Boolean.TRUE); + + // NameDescriptor returnLocDesc = new NameDescriptor("RLOC" + (locSeed++)); + // NTuple rDescTuple = new NTuple(); + // rDescTuple.add(md.getThis()); + // rDescTuple.add(returnLocDesc); + // + // for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { + // FlowNode rnode = (FlowNode) iterator.next(); + // flowGraph.addValueFlowEdge(rnode.getDescTuple(), rDescTuple); + // } + // + // getMethodSummary(md).setRETURNLoc(new CompositeLocation(translateToLocTuple(md, + // rDescTuple))); + + } else { + mapMethodDescriptorToCompositeReturnCase.put(md, Boolean.FALSE); + } + + return mapMethodDescriptorToCompositeReturnCase.get(md).booleanValue(); + + } + + private boolean needToGenerateCompositeLocation(GlobalFlowNode node, NTuple curPrefix) { + // return true if there is a path between a node to which we want to give a composite location + // and nodes which start with curPrefix + + System.out.println("---needToGenerateCompositeLocation curPrefix=" + curPrefix); + + Location targetLocalLoc = node.getLocTuple().get(0); + + MethodDescriptor md = (MethodDescriptor) targetLocalLoc.getDescriptor(); + FlowGraph flowGraph = getFlowGraph(md); + FlowNode flowNode = flowGraph.getFlowNode(node.getDescTuple()); + Set reachableSet = flowGraph.getReachFlowNodeSetFrom(flowNode); + + Set paramNodeSet = flowGraph.getParamFlowNodeSet(); + for (Iterator iterator = paramNodeSet.iterator(); iterator.hasNext();) { + FlowNode paramFlowNode = (FlowNode) iterator.next(); + if (curPrefix.startsWith(translateToLocTuple(md, paramFlowNode.getDescTuple()))) { + System.out.println("here1?!"); + return true; + } + } + + if (targetLocalLoc.getLocDescriptor() instanceof InterDescriptor) { + Pair pair = + ((InterDescriptor) targetLocalLoc.getLocDescriptor()).getMethodArgIdxPair(); + + if (pair != null) { + System.out.println("$$$TARGETLOCALLOC HOLDER=" + targetLocalLoc); + + MethodInvokeNode min = pair.getFirst(); + Integer paramIdx = pair.getSecond(); + MethodDescriptor mdCallee = min.getMethod(); + + FlowNode paramNode = getFlowGraph(mdCallee).getParamFlowNode(paramIdx); + if (checkNodeReachToReturnNode(mdCallee, paramNode)) { + System.out.println("here2?!"); + return true; + } + + } + + } + + GlobalFlowGraph subGlobalFlowGraph = getSubGlobalFlowGraph(md); + Set subGlobalReachableSet = subGlobalFlowGraph.getReachableNodeSetFrom(node); + + if (!md.isStatic()) { + ClassDescriptor currentMethodThisType = getClassTypeDescriptor(md.getThis()); + for (int i = 0; i < curPrefix.size(); i++) { + ClassDescriptor prefixType = getClassTypeDescriptor(curPrefix.get(i).getLocDescriptor()); + if (prefixType != null && prefixType.equals(currentMethodThisType)) { + System.out.println("PREFIX TYPE MATCHES WITH=" + currentMethodThisType); + + if (mapMethodDescriptorToCompositeReturnCase.containsKey(md)) { + boolean hasCompReturnLocWithThis = + mapMethodDescriptorToCompositeReturnCase.get(md).booleanValue(); + if (hasCompReturnLocWithThis) { + if (checkNodeReachToReturnNode(md, flowNode)) { + System.out.println("here3?!"); + return true; + } + } + } + + for (Iterator iterator3 = subGlobalReachableSet.iterator(); iterator3.hasNext();) { + GlobalFlowNode subGlobalReachalbeNode = (GlobalFlowNode) iterator3.next(); + if (subGlobalReachalbeNode.getLocTuple().get(0).getLocDescriptor().equals(md.getThis())) { + System.out.println("PREFIX FOUND=" + subGlobalReachalbeNode); + System.out.println("here4?!"); + return true; + } + } + } + } + } + + // System.out.println("flowGraph.getReturnNodeSet()=" + flowGraph.getReturnNodeSet()); + // System.out.println("flowGraph.contains(node.getDescTuple())=" + // + flowGraph.contains(node.getDescTuple()) + " flowGraph.getFlowNode(node.getDescTuple())=" + // + flowGraph.getFlowNode(node.getDescTuple()));reachableSet + + // if (flowGraph.contains(node.getDescTuple()) + // && flowGraph.getReturnNodeSet().contains(flowGraph.getFlowNode(node.getDescTuple()))) { + // // return checkFlowNodeReturnThisField(flowGraph); + // } + + Location lastLocationOfPrefix = curPrefix.get(curPrefix.size() - 1); + // check whether prefix appears in the list of parameters + Set minSet = mapMethodDescToMethodInvokeNodeSet.get(md); + found: for (Iterator iterator = minSet.iterator(); iterator.hasNext();) { + MethodInvokeNode min = (MethodInvokeNode) iterator.next(); + Map> map = mapMethodInvokeNodeToArgIdxMap.get(min); + Set keySet = map.keySet(); + // System.out.println("min=" + min.printNode(0)); + + for (Iterator iterator2 = keySet.iterator(); iterator2.hasNext();) { + Integer argIdx = (Integer) iterator2.next(); + NTuple argTuple = map.get(argIdx); + + if (!(!md.isStatic() && argIdx == 0)) { + // if the argTuple is empty, we don't need to do with anything(LITERAL CASE). + if (argTuple.size() > 0 + && argTuple.get(argTuple.size() - 1).equals(lastLocationOfPrefix.getLocDescriptor())) { + NTuple locTuple = + translateToLocTuple(md, flowGraph.getParamFlowNode(argIdx).getDescTuple()); + lastLocationOfPrefix = locTuple.get(0); + System.out.println("ARG CASE=" + locTuple); + for (Iterator iterator3 = subGlobalReachableSet.iterator(); iterator3.hasNext();) { + GlobalFlowNode subGlobalReachalbeNode = (GlobalFlowNode) iterator3.next(); + // NTuple locTuple = translateToLocTuple(md, reachalbeNode.getDescTuple()); + NTuple globalReachlocTuple = subGlobalReachalbeNode.getLocTuple(); + for (int i = 0; i < globalReachlocTuple.size(); i++) { + if (globalReachlocTuple.get(i).equals(lastLocationOfPrefix)) { + System.out.println("ARG " + argTuple + " IS MATCHED WITH=" + + lastLocationOfPrefix); + System.out.println("here5?!"); + + return true; + } + } + } + } + } + } + } + + // ClassDescriptor cd; + // if (lastLocationOfPrefix.getLocDescriptor() instanceof VarDescriptor) { + // cd = ((VarDescriptor) lastLocationOfPrefix.getLocDescriptor()).getType().getClassDesc(); + // } else { + // // it is a field descriptor + // cd = ((FieldDescriptor) lastLocationOfPrefix.getLocDescriptor()).getType().getClassDesc(); + // } + // + // GlobalFlowGraph subGlobalFlowGraph = getSubGlobalFlowGraph(md); + // Set subGlobalReachableSet = subGlobalFlowGraph.getReachableNodeSetFrom(node); + // + // System.out.println("TRY TO FIND lastLocationOfPrefix=" + lastLocationOfPrefix); + // for (Iterator iterator2 = subGlobalReachableSet.iterator(); iterator2.hasNext();) { + // GlobalFlowNode subGlobalReachalbeNode = (GlobalFlowNode) iterator2.next(); + // // NTuple locTuple = translateToLocTuple(md, reachalbeNode.getDescTuple()); + // NTuple locTuple = subGlobalReachalbeNode.getLocTuple(); + // + // for (int i = 0; i < locTuple.size(); i++) { + // if (locTuple.get(i).equals(lastLocationOfPrefix)) { + // return true; + // } + // } + // + // Location lastLoc = locTuple.get(locTuple.size() - 1); + // Descriptor enclosingDescriptor = lastLoc.getDescriptor(); + // + // if (enclosingDescriptor != null && enclosingDescriptor.equals(cd)) { + // System.out.println("# WHY HERE?"); + // System.out.println("subGlobalReachalbeNode=" + subGlobalReachalbeNode); + // return true; + // } + // } + + return false; + } + + private boolean checkNodeReachToReturnNode(MethodDescriptor md, FlowNode node) { + + FlowGraph flowGraph = getFlowGraph(md); + Set reachableSet = flowGraph.getReachFlowNodeSetFrom(node); + if (mapMethodDescriptorToCompositeReturnCase.containsKey(md)) { + boolean hasCompReturnLocWithThis = + mapMethodDescriptorToCompositeReturnCase.get(md).booleanValue(); + + if (hasCompReturnLocWithThis) { + for (Iterator iterator = flowGraph.getReturnNodeSet().iterator(); iterator.hasNext();) { + FlowNode returnFlowNode = (FlowNode) iterator.next(); + if (reachableSet.contains(returnFlowNode)) { + return true; + } + } + } + } + return false; + } + + private void assignCompositeLocation(CompositeLocation compLocPrefix, GlobalFlowNode node) { + CompositeLocation newCompLoc = compLocPrefix.clone(); + NTuple locTuple = node.getLocTuple(); + for (int i = 1; i < locTuple.size(); i++) { + newCompLoc.addLocation(locTuple.get(i)); + } + node.setInferCompositeLocation(newCompLoc); + } + + private List> calculatePrefixList(GlobalFlowGraph graph, GlobalFlowNode node) { + + System.out.println("\n##### calculatePrefixList node=" + node); + + 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); + + List> prefixList = new ArrayList>(); + + for (Iterator iterator = incomingNodeSetPrefix.iterator(); iterator.hasNext();) { + GlobalFlowNode inNode = (GlobalFlowNode) iterator.next(); + NTuple inNodeTuple = inNode.getLocTuple(); + + if (inNodeTuple.get(0).getLocDescriptor() instanceof InterDescriptor + || inNodeTuple.get(0).getLocDescriptor().equals(GLOBALDESC)) { + continue; + } + + for (int i = 1; i < inNodeTuple.size(); i++) { + NTuple prefix = inNodeTuple.subList(0, i); + if (!prefixList.contains(prefix)) { + prefixList.add(prefix); + } + } + } + + Collections.sort(prefixList, new Comparator>() { + public int compare(NTuple arg0, NTuple arg1) { + int s0 = arg0.size(); + int s1 = arg1.size(); + if (s0 > s1) { + return -1; + } else if (s0 == s1) { + return 0; + } else { + return 1; + } + } + }); + + // remove a prefix which is not suitable for generating composite location + Location localVarLoc = node.getLocTuple().get(0); + MethodDescriptor md = (MethodDescriptor) localVarLoc.getDescriptor(); + ClassDescriptor cd = md.getClassDesc(); + + int idx = 0; + Set> toberemoved = new HashSet>(); + // for (int i = 0; i < prefixList.size(); i++) { + // NTuple prefixLocTuple = prefixList.get(i); + // if (!containsClassDesc(cd, prefixLocTuple)) { + // toberemoved.add(prefixLocTuple); + // } + // } + + // System.out.println("method class=" + cd + " toberemoved=" + toberemoved); + + prefixList.removeAll(toberemoved); + + return prefixList; + + } + + private boolean containsClassDesc(ClassDescriptor cd, NTuple prefixLocTuple) { + for (int i = 0; i < prefixLocTuple.size(); i++) { + Location loc = prefixLocTuple.get(i); + Descriptor locDesc = loc.getLocDescriptor(); + if (locDesc != null) { + ClassDescriptor type = getClassTypeDescriptor(locDesc); + if (type != null && type.equals(cd)) { + return true; + } + } + } + return false; + } + + private GlobalFlowGraph constructSubGlobalFlowGraph(FlowGraph flowGraph) { + + MethodDescriptor md = flowGraph.getMethodDescriptor(); + + GlobalFlowGraph globalGraph = getSubGlobalFlowGraph(md); + + // Set nodeSet = flowGraph.getNodeSet(); + Set edgeSet = flowGraph.getEdgeSet(); + + for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) { + + FlowEdge edge = (FlowEdge) iterator.next(); + NTuple srcDescTuple = edge.getInitTuple(); + NTuple dstDescTuple = edge.getEndTuple(); + + if (flowGraph.getFlowNode(srcDescTuple) instanceof FlowReturnNode + || flowGraph.getFlowNode(dstDescTuple) instanceof FlowReturnNode) { + continue; + } + + // here only keep the first element(method location) of the descriptor + // tuple + NTuple srcLocTuple = translateToLocTuple(md, srcDescTuple); + // Location srcMethodLoc = srcLocTuple.get(0); + // Descriptor srcVarDesc = srcMethodLoc.getLocDescriptor(); + // // if (flowGraph.isParamDesc(srcVarDesc) && + // (!srcVarDesc.equals(md.getThis()))) { + // if (!srcVarDesc.equals(md.getThis())) { + // srcLocTuple = new NTuple(); + // Location loc = new Location(md, srcVarDesc); + // srcLocTuple.add(loc); + // } + // + NTuple dstLocTuple = translateToLocTuple(md, dstDescTuple); + // Location dstMethodLoc = dstLocTuple.get(0); + // Descriptor dstVarDesc = dstMethodLoc.getLocDescriptor(); + // if (!dstVarDesc.equals(md.getThis())) { + // dstLocTuple = new NTuple(); + // Location loc = new Location(md, dstVarDesc); + // dstLocTuple.add(loc); + // } + + globalGraph.addValueFlowEdge(srcLocTuple, dstLocTuple); + + } + + return globalGraph; + } + + private NTuple translateToLocTuple(MethodDescriptor md, NTuple descTuple) { + + NTuple locTuple = new NTuple(); + + Descriptor enclosingDesc = md; + // System.out.println("md=" + md + " descTuple=" + descTuple); + for (int i = 0; i < descTuple.size(); i++) { + Descriptor desc = descTuple.get(i); + + Location loc = new Location(enclosingDesc, desc); + locTuple.add(loc); + + if (desc instanceof VarDescriptor) { + enclosingDesc = ((VarDescriptor) desc).getType().getClassDesc(); + } else if (desc instanceof FieldDescriptor) { + enclosingDesc = ((FieldDescriptor) desc).getType().getClassDesc(); + } else { + // TODO: inter descriptor case + enclosingDesc = desc; + } + + } + + return locTuple; + + } + + private void addValueFlowsFromCalleeSubGlobalFlowGraph(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 = 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); + } + + } + + } + + private void propagateValueFlowsToCallerFromSubGlobalFlowGraph(MethodInvokeNode min, + MethodDescriptor mdCaller, MethodDescriptor possibleMdCallee) { + + 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)); + + Set keySet = mapIdxToArg.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Integer idx = (Integer) iterator.next(); + NTuple argDescTuple = mapIdxToArg.get(idx); + if (argDescTuple.size() > 0) { + NTuple argLocTuple = translateToLocTuple(mdCaller, argDescTuple); + NTuple paramDescTuple = calleeFlowGraph.getParamFlowNode(idx).getDescTuple(); + NTuple paramLocTuple = translateToLocTuple(possibleMdCallee, paramDescTuple); + System.out.println("-------paramDescTuple=" + paramDescTuple + "->argDescTuple=" + + argDescTuple); + addMapCallerArgToCalleeParam(min, argDescTuple, paramDescTuple); + } + } + + // addValueFlowBetweenParametersToCaller(min, mdCaller, possibleMdCallee); + + NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); + GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(possibleMdCallee); + Set calleeNodeSet = calleeSubGlobalGraph.getNodeSet(); + for (Iterator iterator = calleeNodeSet.iterator(); iterator.hasNext();) { + GlobalFlowNode calleeNode = (GlobalFlowNode) iterator.next(); + addValueFlowFromCalleeNode(min, mdCaller, possibleMdCallee, calleeNode); + } + + System.out.println("$$$GLOBAL PC LOC ADD=" + mdCaller); + Set> pcLocTupleSet = mapMethodInvokeNodeToPCLocTupleSet.get(min); + System.out.println("---pcLocTupleSet=" + pcLocTupleSet); + GlobalFlowGraph callerSubGlobalGraph = getSubGlobalFlowGraph(mdCaller); + for (Iterator iterator = calleeNodeSet.iterator(); iterator.hasNext();) { + GlobalFlowNode calleeNode = (GlobalFlowNode) iterator.next(); + if (calleeNode.isParamNodeWithIncomingFlows()) { + System.out.println("calleeNode.getLocTuple()" + calleeNode.getLocTuple()); + NTuple callerSrcNodeLocTuple = + translateToCallerLocTuple(min, possibleMdCallee, mdCaller, calleeNode.getLocTuple()); + System.out.println("---callerSrcNodeLocTuple=" + callerSrcNodeLocTuple); + if (callerSrcNodeLocTuple != null && callerSrcNodeLocTuple.size() > 0) { + for (Iterator iterator2 = pcLocTupleSet.iterator(); iterator2.hasNext();) { + NTuple pcLocTuple = (NTuple) iterator2.next(); + callerSubGlobalGraph.addValueFlowEdge(pcLocTuple, callerSrcNodeLocTuple); + } + } + } + + } + + } + + private void addValueFlowFromCalleeNode(MethodInvokeNode min, MethodDescriptor mdCaller, + MethodDescriptor mdCallee, GlobalFlowNode calleeSrcNode) { + + GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(mdCallee); + GlobalFlowGraph callerSubGlobalGraph = getSubGlobalFlowGraph(mdCaller); + + // System.out.println("$addValueFlowFromCalleeNode calleeSrcNode=" + calleeSrcNode); + + NTuple callerSrcNodeLocTuple = + translateToCallerLocTuple(min, mdCallee, mdCaller, calleeSrcNode.getLocTuple()); + // System.out.println("---callerSrcNodeLocTuple=" + callerSrcNodeLocTuple); + + if (callerSrcNodeLocTuple != null && callerSrcNodeLocTuple.size() > 0) { + + Set outNodeSet = calleeSubGlobalGraph.getOutNodeSet(calleeSrcNode); + + for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) { + GlobalFlowNode outNode = (GlobalFlowNode) iterator.next(); + NTuple callerDstNodeLocTuple = + translateToCallerLocTuple(min, mdCallee, mdCaller, outNode.getLocTuple()); + // System.out.println("outNode=" + outNode + " callerDstNodeLocTuple=" + // + callerDstNodeLocTuple); + if (callerDstNodeLocTuple != null) { + callerSubGlobalGraph.addValueFlowEdge(callerSrcNodeLocTuple, callerDstNodeLocTuple); + } + } + } + + } + + private NTuple translateToCallerLocTuple(MethodInvokeNode min, + MethodDescriptor mdCallee, MethodDescriptor mdCaller, NTuple nodeLocTuple) { + // this method will return the same nodeLocTuple if the corresponding argument is literal + // value. + + FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); + + NTuple nodeDescTuple = translateToDescTuple(nodeLocTuple); + if (calleeFlowGraph.isParameter(nodeDescTuple)) { + int paramIdx = calleeFlowGraph.getParamIdx(nodeDescTuple); + NTuple argDescTuple = mapMethodInvokeNodeToArgIdxMap.get(min).get(paramIdx); + + // if (isPrimitive(nodeLocTuple.get(0).getLocDescriptor())) { + // // the type of argument is primitive. + // return nodeLocTuple.clone(); + // } + // System.out.println("paramIdx=" + paramIdx + " argDescTuple=" + argDescTuple); + NTuple argLocTuple = translateToLocTuple(mdCaller, argDescTuple); + + NTuple callerLocTuple = new NTuple(); + + callerLocTuple.addAll(argLocTuple); + for (int i = 1; i < nodeLocTuple.size(); i++) { + callerLocTuple.add(nodeLocTuple.get(i)); + } + return callerLocTuple; + } else { + return nodeLocTuple.clone(); + } + + } + + public static boolean isPrimitive(Descriptor desc) { + + if (desc instanceof FieldDescriptor) { + return ((FieldDescriptor) desc).getType().isPrimitive(); + } else if (desc instanceof VarDescriptor) { + return ((VarDescriptor) desc).getType().isPrimitive(); + } else if (desc instanceof InterDescriptor) { + return true; + } + + return false; + } + + public static boolean isReference(Descriptor desc) { + + if (desc instanceof FieldDescriptor) { + + TypeDescriptor type = ((FieldDescriptor) desc).getType(); + if (type.isArray()) { + return false; + } else { + return type.isPtr(); + } + + } else if (desc instanceof VarDescriptor) { + TypeDescriptor type = ((VarDescriptor) desc).getType(); + if (type.isArray()) { + return false; + } else { + return type.isPtr(); + } + } + + return false; + } + + private NTuple translateToDescTuple(NTuple locTuple) { + + NTuple descTuple = new NTuple(); + for (int i = 0; i < locTuple.size(); i++) { + descTuple.add(locTuple.get(i).getLocDescriptor()); + } + return descTuple; + + } + + 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); + + HierarchyGraph scGraph = getSkeletonCombinationHierarchyGraph(md); + + // set the 'this' reference location + if (!md.isStatic()) { + System.out.println("setThisLocName=" + scGraph.getHNode(md.getThis()).getName()); + methodSummary.setThisLocName(scGraph.getHNode(md.getThis()).getName()); + } + + // set the 'global' reference location if needed + if (methodSummary.hasGlobalAccess()) { + methodSummary.setGlobalLocName(scGraph.getHNode(GLOBALDESC).getName()); + } + + // 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); + CompositeLocation inferredCompLoc = + updateCompositeLocation(flowNode.getCompositeLocation()); + // 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 + " original=" + + flowNode.getCompositeLocation()); + + Descriptor localVarDesc = flowNode.getDescTuple().get(0); + methodSummary.addMapVarNameToInferCompLoc(localVarDesc, inferredCompLoc); + methodSummary.addMapParamIdxToInferLoc(paramIdx, inferredCompLoc); + } + + } + + } + + private boolean hasOrderingRelation(NTuple locTuple1, NTuple locTuple2) { + + int size = locTuple1.size() >= locTuple2.size() ? locTuple2.size() : locTuple1.size(); + + for (int idx = 0; idx < size; idx++) { + Location loc1 = locTuple1.get(idx); + Location loc2 = locTuple2.get(idx); + + Descriptor desc1 = loc1.getDescriptor(); + Descriptor desc2 = loc2.getDescriptor(); + + if (!desc1.equals(desc2)) { + throw new Error("Fail to compare " + locTuple1 + " and " + locTuple2); + } + + Descriptor locDesc1 = loc1.getLocDescriptor(); + Descriptor locDesc2 = loc2.getLocDescriptor(); + + HierarchyGraph hierarchyGraph = getHierarchyGraph(desc1); + + HNode node1 = hierarchyGraph.getHNode(locDesc1); + HNode node2 = hierarchyGraph.getHNode(locDesc2); + + System.out.println("---node1=" + node1 + " node2=" + node2); + System.out.println("---hierarchyGraph.getIncomingNodeSet(node2)=" + + hierarchyGraph.getIncomingNodeSet(node2)); + + if (locDesc1.equals(locDesc2)) { + continue; + } else if (!hierarchyGraph.getIncomingNodeSet(node2).contains(node1) + && !hierarchyGraph.getIncomingNodeSet(node1).contains(node2)) { + return false; + } else { + return true; + } + + } + + return false; + + } + + private boolean isHigherThan(NTuple locTuple1, NTuple locTuple2) { + + int size = locTuple1.size() >= locTuple2.size() ? locTuple2.size() : locTuple1.size(); + + for (int idx = 0; idx < size; idx++) { + Location loc1 = locTuple1.get(idx); + Location loc2 = locTuple2.get(idx); + + Descriptor desc1 = loc1.getDescriptor(); + Descriptor desc2 = loc2.getDescriptor(); + + if (!desc1.equals(desc2)) { + throw new Error("Fail to compare " + locTuple1 + " and " + locTuple2); + } + + Descriptor locDesc1 = loc1.getLocDescriptor(); + Descriptor locDesc2 = loc2.getLocDescriptor(); + + HierarchyGraph hierarchyGraph = getHierarchyGraph(desc1); + + HNode node1 = hierarchyGraph.getHNode(locDesc1); + HNode node2 = hierarchyGraph.getHNode(locDesc2); + + System.out.println("---node1=" + node1 + " node2=" + node2); + System.out.println("---hierarchyGraph.getIncomingNodeSet(node2)=" + + hierarchyGraph.getIncomingNodeSet(node2)); + + if (locDesc1.equals(locDesc2)) { + continue; + } else if (hierarchyGraph.getIncomingNodeSet(node2).contains(node1)) { + return true; + } else { + return false; + } + + } + + return false; + } + + 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); @@ -699,7 +2041,7 @@ public class LocationInference { addMapDescToSimpleLattice(desc, simpleLattice); HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc); - System.out.println("## insertIntermediateNodesToStraightLine:" + System.out.println("\n## insertIntermediateNodesToStraightLine:" + simpleHierarchyGraph.getName()); SSJavaLattice lattice = buildLattice.insertIntermediateNodesToStraightLine(desc, simpleLattice); @@ -719,14 +2061,16 @@ public class LocationInference { // System.out.println("\nSSJAVA: Insering Combination Nodes:" + desc); // HierarchyGraph skeletonGraph = getSkeletonHierarchyGraph(desc); - // HierarchyGraph skeletonGraphWithCombinationNode = skeletonGraph.clone(); + // HierarchyGraph skeletonGraphWithCombinationNode = + // skeletonGraph.clone(); // skeletonGraphWithCombinationNode.setName(desc + "_SC"); // // HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc); // System.out.println("Identifying Combination Nodes:"); // skeletonGraphWithCombinationNode.insertCombinationNodesToGraph(simpleHierarchyGraph); // skeletonGraphWithCombinationNode.simplifySkeletonCombinationHierarchyGraph(); - // mapDescriptorToCombineSkeletonHierarchyGraph.put(desc, skeletonGraphWithCombinationNode); + // mapDescriptorToCombineSkeletonHierarchyGraph.put(desc, + // skeletonGraphWithCombinationNode); } } @@ -743,10 +2087,10 @@ public class LocationInference { Set keySet = mapDescriptorToHierarchyGraph.keySet(); for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { Descriptor desc = (Descriptor) iterator.next(); + // System.out.println("SSJAVA: remove redundant edges: " + desc); HierarchyGraph simpleHierarchyGraph = getHierarchyGraph(desc).clone(); simpleHierarchyGraph.setName(desc + "_SIMPLE"); simpleHierarchyGraph.removeRedundantEdges(); - // simpleHierarchyGraph.simplifyHierarchyGraph(); mapDescriptorToSimpleHierarchyGraph.put(desc, simpleHierarchyGraph); } } @@ -772,6 +2116,7 @@ public class LocationInference { Set keySet = mapDescriptorToHierarchyGraph.keySet(); for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { Descriptor desc = (Descriptor) iterator.next(); + System.out.println("SSJAVA: Constructing Skeleton Hierarchy Graph: " + desc); HierarchyGraph simpleGraph = getSimpleHierarchyGraph(desc); HierarchyGraph skeletonGraph = simpleGraph.generateSkeletonGraph(); skeletonGraph.setMapDescToHNode(simpleGraph.getMapDescToHNode()); @@ -846,7 +2191,6 @@ public class LocationInference { // do fixed-point analysis - ssjava.init(); LinkedList descriptorListToAnalyze = ssjava.getSortedDescriptors(); // Collections.sort(descriptorListToAnalyze, new @@ -907,6 +2251,41 @@ public class LocationInference { } + setupToAnalyze(); + while (!toAnalyzeIsEmpty()) { + ClassDescriptor cd = toAnalyzeNext(); + HierarchyGraph graph = getHierarchyGraph(cd); + for (Iterator iter = cd.getFields(); iter.hasNext();) { + FieldDescriptor fieldDesc = (FieldDescriptor) iter.next(); + if (!(fieldDesc.isStatic() && fieldDesc.isFinal())) { + graph.getHNode(fieldDesc); + } + } + } + + Set keySet = mapDescriptorToHierarchyGraph.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Descriptor key = (Descriptor) iterator.next(); + HierarchyGraph graph = getHierarchyGraph(key); + + Set nodeToBeConnected = new HashSet(); + for (Iterator iterator2 = graph.getNodeSet().iterator(); iterator2.hasNext();) { + HNode node = (HNode) iterator2.next(); + if (!node.isSkeleton() && !node.isCombinationNode()) { + if (graph.getIncomingNodeSet(node).size() == 0) { + nodeToBeConnected.add(node); + } + } + } + + for (Iterator iterator2 = nodeToBeConnected.iterator(); iterator2.hasNext();) { + HNode node = (HNode) iterator2.next(); + System.out.println("NEED TO BE CONNECTED TO TOP=" + node); + graph.addEdge(graph.getHNode(TOPDESC), node); + } + + } + } private HierarchyGraph getHierarchyGraph(Descriptor d) { @@ -920,7 +2299,9 @@ public class LocationInference { // visit each node of method flow graph FlowGraph fg = getFlowGraph(md); - Set nodeSet = fg.getNodeSet(); + // Set nodeSet = fg.getNodeSet(); + + Set edgeSet = fg.getEdgeSet(); Set paramDescSet = fg.getMapParamDescToIdx().keySet(); for (Iterator iterator = paramDescSet.iterator(); iterator.hasNext();) { @@ -930,23 +2311,93 @@ public class LocationInference { // for the method lattice, we need to look at the first element of // NTuple - for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { - FlowNode srcNode = (FlowNode) iterator.next(); + boolean hasGlobalAccess = false; + // for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + // FlowNode originalSrcNode = (FlowNode) iterator.next(); + for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) { + FlowEdge edge = (FlowEdge) iterator.next(); + + FlowNode originalSrcNode = fg.getFlowNode(edge.getInitTuple()); + Set sourceNodeSet = new HashSet(); + if (originalSrcNode instanceof FlowReturnNode) { + FlowReturnNode rnode = (FlowReturnNode) originalSrcNode; + System.out.println("rnode=" + rnode); + Set> tupleSet = rnode.getReturnTupleSet(); + 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 + " from originalSrcNode=" + // + originalSrcNode); + + for (Iterator iterator3 = sourceNodeSet.iterator(); iterator3.hasNext();) { + FlowNode srcNode = (FlowNode) iterator3.next(); NTuple srcNodeTuple = srcNode.getDescTuple(); - NTuple dstNodeTuple = dstNode.getDescTuple(); + Descriptor srcLocalDesc = srcNodeTuple.get(0); + + if (srcLocalDesc instanceof InterDescriptor + && ((InterDescriptor) srcLocalDesc).getMethodArgIdxPair() != null) { + + if (srcNode.getCompositeLocation() == null) { + continue; + } + } + + // if the srcNode is started with the global descriptor + // need to set as a skeleton node + if (!hasGlobalAccess && srcNode.getDescTuple().startsWith(GLOBALDESC)) { + hasGlobalAccess = true; + } + + // Set outEdgeSet = fg.getOutEdgeSet(originalSrcNode); + // for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) { + // FlowEdge outEdge = (FlowEdge) iterator2.next(); + // FlowNode originalDstNode = outEdge.getDst(); + FlowNode originalDstNode = fg.getFlowNode(edge.getEndTuple()); + + Set dstNodeSet = new HashSet(); + if (originalDstNode instanceof FlowReturnNode) { + FlowReturnNode rnode = (FlowReturnNode) originalDstNode; + // System.out.println("\n-returnNode=" + rnode); + Set> tupleSet = rnode.getReturnTupleSet(); + for (Iterator iterator4 = tupleSet.iterator(); iterator4.hasNext();) { + NTuple nTuple = (NTuple) iterator4.next(); + dstNodeSet.add(fg.getFlowNode(nTuple)); + System.out.println("&&&DST fg.getFlowNode(nTuple)=" + 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 dstNodeTuple = dstNode.getDescTuple(); + Descriptor dstLocalDesc = dstNodeTuple.get(0); + + if (dstLocalDesc instanceof InterDescriptor + && ((InterDescriptor) dstLocalDesc).getMethodArgIdxPair() != null) { + if (dstNode.getCompositeLocation() == null) { + System.out.println("%%%%%%%%%%%%%SKIP=" + dstNode); + continue; + } + } - if (outEdge.getInitTuple().equals(srcNodeTuple) - && outEdge.getEndTuple().equals(dstNodeTuple)) { + // if (outEdge.getInitTuple().equals(srcNodeTuple) + // && outEdge.getEndTuple().equals(dstNodeTuple)) { NTuple srcCurTuple = srcNode.getCurrentDescTuple(); NTuple dstCurTuple = dstNode.getCurrentDescTuple(); + System.out.println("-srcCurTuple=" + srcCurTuple + " dstCurTuple=" + dstCurTuple + + " srcNode=" + srcNode + " dstNode=" + dstNode); + if ((srcCurTuple.size() > 1 && dstCurTuple.size() > 1) && srcCurTuple.get(0).equals(dstCurTuple.get(0))) { @@ -962,8 +2413,12 @@ public class LocationInference { } extractFlowsBetweenFields(classDesc, srcNode, dstNode, 1); - } else { - // value flow between local var - local var or local var - field + } else if ((srcCurTuple.size() == 1 && dstCurTuple.size() == 1) + || ((srcCurTuple.size() > 1 || dstCurTuple.size() > 1) && !srcCurTuple.get(0).equals( + dstCurTuple.get(0)))) { + + // value flow between a primitive local var - a primitive local var or local var - + // field Descriptor srcDesc = srcCurTuple.get(0); Descriptor dstDesc = dstCurTuple.get(0); @@ -979,7 +2434,29 @@ public class LocationInference { } + // } + // } + } + + } + + } + + // If the method accesses static fields + // set hasGloabalAccess true in the method summary. + if (hasGlobalAccess) { + getMethodSummary(md).setHasGlobalAccess(); + } + methodGraph.getHNode(GLOBALDESC).setSkeleton(true); + + if (ssjava.getMethodContainingSSJavaLoop().equals(md)) { + // if the current method contains the event loop + // we need to set all nodes of the hierarchy graph as a skeleton node + Set hnodeSet = methodGraph.getNodeSet(); + for (Iterator iterator = hnodeSet.iterator(); iterator.hasNext();) { + HNode hnode = (HNode) iterator.next(); + hnode.setSkeleton(true); } } @@ -1117,22 +2594,27 @@ public class LocationInference { rtr += "\")"; if (desc instanceof MethodDescriptor) { - TypeDescriptor returnType = ((MethodDescriptor) desc).getReturnType(); + System.out.println("#EXTRA LOC DECLARATION GEN=" + desc); - MethodLocationInfo methodLocInfo = getMethodLocationInfo((MethodDescriptor) desc); + MethodDescriptor md = (MethodDescriptor) desc; + MethodSummary methodSummary = getMethodSummary(md); - if (returnType != null && (!returnType.isVoid())) { - rtr += - "\n@RETURNLOC(\"" + generateLocationAnnoatation(methodLocInfo.getReturnLoc()) + "\")"; + if (!ssjava.getMethodContainingSSJavaLoop().equals(desc)) { + TypeDescriptor returnType = ((MethodDescriptor) desc).getReturnType(); + if (returnType != null && (!returnType.isVoid())) { + rtr += + "\n@RETURNLOC(\"" + generateLocationAnnoatation(methodSummary.getRETURNLoc()) + "\")"; + } + CompositeLocation pcLoc = methodSummary.getPCLoc(); + if ((pcLoc != null) && (!pcLoc.get(0).isTop())) { + rtr += "\n@PCLOC(\"" + generateLocationAnnoatation(pcLoc) + "\")"; + } } - rtr += "\n@THISLOC(\"this\")"; - rtr += "\n@GLOBALLOC(\"GLOBALLOC\")"; - - CompositeLocation pcLoc = methodLocInfo.getPCLoc(); - if ((pcLoc != null) && (!pcLoc.get(0).isTop())) { - rtr += "\n@PCLOC(\"" + generateLocationAnnoatation(pcLoc) + "\")"; + if (!md.isStatic()) { + rtr += "\n@THISLOC(\"" + methodSummary.getThisLocName() + "\")"; } + rtr += "\n@GLOBALLOC(\"" + methodSummary.getGlobalLocName() + "\")"; } @@ -1149,7 +2631,6 @@ public class LocationInference { setupToAnalazeMethod(cd); - LocationInfo locInfo = mapClassToLocationInfo.get(cd); String sourceFileName = cd.getSourceFileName(); if (cd.isInterface()) { @@ -1159,37 +2640,27 @@ public class LocationInference { int classDefLine = mapDescToDefinitionLine.get(cd); Vector sourceVec = mapFileNameToLineVector.get(sourceFileName); - if (locInfo == null) { - locInfo = getLocationInfo(cd); - } - - for (Iterator iter = cd.getFields(); iter.hasNext();) { - FieldDescriptor fieldDesc = (FieldDescriptor) iter.next(); - if (!(fieldDesc.isStatic() && fieldDesc.isFinal())) { - String locIdentifier = locInfo.getFieldInferLocation(fieldDesc).getLocIdentifier(); - if (!getLattice(cd).getElementSet().contains(locIdentifier)) { - getLattice(cd).put(locIdentifier); - } - } - } + LocationSummary fieldLocSummary = getLocationSummary(cd); String fieldLatticeDefStr = generateLatticeDefinition(cd); String annoatedSrc = fieldLatticeDefStr + newline + sourceVec.get(classDefLine); sourceVec.set(classDefLine, annoatedSrc); // generate annotations for field declarations - LocationInfo fieldLocInfo = getLocationInfo(cd); - Map inferLocMap = fieldLocInfo.getMapDescToInferLocation(); + // Map inferLocMap = fieldLocInfo.getMapDescToInferLocation(); + Map mapFieldNameToLocName = fieldLocSummary.getMapHNodeNameToLocationName(); for (Iterator iter = cd.getFields(); iter.hasNext();) { FieldDescriptor fd = (FieldDescriptor) iter.next(); String locAnnotationStr; - CompositeLocation inferLoc = inferLocMap.get(fd); + // CompositeLocation inferLoc = inferLocMap.get(fd); + String locName = mapFieldNameToLocName.get(fd.getSymbol()); - if (inferLoc != null) { + if (locName != null) { // infer loc is null if the corresponding field is static and final - locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")"; + // locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")"; + locAnnotationStr = "@LOC(\"" + locName + "\")"; int fdLineNum = fd.getLineNum(); String orgFieldDeclarationStr = sourceVec.get(fdLineNum); String fieldDeclaration = fd.toString(); @@ -1212,17 +2683,25 @@ public class LocationInference { int methodDefLine = md.getLineNum(); - MethodLocationInfo methodLocInfo = getMethodLocationInfo(md); + // MethodLocationInfo methodLocInfo = getMethodLocationInfo(md); + // Map methodInferLocMap = + // methodLocInfo.getMapDescToInferLocation(); + + MethodSummary methodSummary = getMethodSummary(md); + + Map mapVarDescToInferLoc = + methodSummary.getMapVarDescToInferCompositeLocation(); + System.out.println("-----md=" + md); + System.out.println("-----mapVarDescToInferLoc=" + mapVarDescToInferLoc); - Map methodInferLocMap = - methodLocInfo.getMapDescToInferLocation(); - Set localVarDescSet = methodInferLocMap.keySet(); + Set localVarDescSet = mapVarDescToInferLoc.keySet(); Set localLocElementSet = methodLattice.getElementSet(); for (Iterator iterator = localVarDescSet.iterator(); iterator.hasNext();) { Descriptor localVarDesc = (Descriptor) iterator.next(); - CompositeLocation inferLoc = methodInferLocMap.get(localVarDesc); + System.out.println("-------localVarDesc=" + localVarDesc); + CompositeLocation inferLoc = mapVarDescToInferLoc.get(localVarDesc); String localLocIdentifier = inferLoc.get(0).getLocIdentifier(); if (!localLocElementSet.contains(localLocIdentifier)) { @@ -1237,6 +2716,9 @@ public class LocationInference { String orgSourceLine = sourceVec.get(varLineNum); int idx = orgSourceLine.indexOf(generateVarDeclaration((VarDescriptor) localVarDesc)); + System.out.println("idx=" + idx + + " generateVarDeclaration((VarDescriptor) localVarDesc)=" + + generateVarDeclaration((VarDescriptor) localVarDesc)); assert (idx != -1); String annoatedStr = orgSourceLine.substring(0, idx) + locAnnotationStr + " " @@ -1249,7 +2731,8 @@ public class LocationInference { int idx = getParamLocation(methodDefStr, generateVarDeclaration((VarDescriptor) localVarDesc)); - + System.out.println("methodDefStr=" + methodDefStr + " localVarDesc=" + localVarDesc + + " idx=" + idx); assert (idx != -1); String annoatedStr = @@ -1264,9 +2747,9 @@ public class LocationInference { // reference... // boolean needToAddthisRef = hasThisReference(md); - if (localLocElementSet.contains("this")) { - methodLattice.put("this"); - } + // if (localLocElementSet.contains("this")) { + // methodLattice.put("this"); + // } String methodLatticeDefStr = generateLatticeDefinition(md); String annoatedStr = methodLatticeDefStr + newline + sourceVec.get(methodDefLine); @@ -1286,7 +2769,7 @@ public class LocationInference { Set nodeSet = fg.getNodeSet(); for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { FlowNode flowNode = (FlowNode) iterator.next(); - if (flowNode.getLocTuple().get(0).equals(md.getThis())) { + if (flowNode.getDescTuple().get(0).equals(md.getThis())) { return true; } } @@ -1377,160 +2860,6 @@ public class LocationInference { } - private void simplifyLattices() { - - setupToAnalyze(); - - while (!toAnalyzeIsEmpty()) { - ClassDescriptor cd = toAnalyzeNext(); - setupToAnalazeMethod(cd); - - SSJavaLattice classLattice = cd2lattice.get(cd); - if (classLattice != null) { - System.out.println("@@@check lattice=" + cd); - checkLatticeProperty(cd, classLattice); - } - - while (!toAnalyzeMethodIsEmpty()) { - MethodDescriptor md = toAnalyzeMethodNext(); - SSJavaLattice methodLattice = md2lattice.get(md); - if (methodLattice != null) { - System.out.println("@@@check lattice=" + md); - checkLatticeProperty(md, methodLattice); - } - } - } - - setupToAnalyze(); - - while (!toAnalyzeIsEmpty()) { - ClassDescriptor cd = toAnalyzeNext(); - - setupToAnalazeMethod(cd); - - SSJavaLattice classLattice = cd2lattice.get(cd); - if (classLattice != null) { - classLattice.removeRedundantEdges(); - } - - while (!toAnalyzeMethodIsEmpty()) { - MethodDescriptor md = toAnalyzeMethodNext(); - SSJavaLattice methodLattice = md2lattice.get(md); - if (methodLattice != null) { - methodLattice.removeRedundantEdges(); - } - } - } - - } - - private boolean checkLatticeProperty(Descriptor d, SSJavaLattice lattice) { - // if two elements has the same incoming node set, - // we need to merge two elements ... - - boolean isUpdated; - boolean isModified = false; - do { - isUpdated = removeNodeSharingSameIncomingNodes(d, lattice); - if (!isModified && isUpdated) { - isModified = true; - } - } while (isUpdated); - - return isModified; - } - - private boolean removeNodeSharingSameIncomingNodes(Descriptor d, SSJavaLattice lattice) { - LocationInfo locInfo = getLocationInfo(d); - Map> map = lattice.getIncomingElementMap(); - Set keySet = map.keySet(); - for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { - String key = (String) iterator.next(); - Set incomingSetKey = map.get(key); - - // System.out.println("key=" + key + " incomingSetKey=" + - // incomingSetKey); - if (incomingSetKey.size() > 0) { - for (Iterator iterator2 = keySet.iterator(); iterator2.hasNext();) { - String cur = (String) iterator2.next(); - if (!cur.equals(key)) { - Set incomingSetCur = map.get(cur); - if (incomingSetCur.equals(incomingSetKey)) { - if (!(incomingSetCur.size() == 1 && incomingSetCur.contains(lattice.getTopItem()))) { - // NEED TO MERGE HERE!!!! - System.out.println("@@@Try merge=" + cur + " " + key); - - Set mergeSet = new HashSet(); - mergeSet.add(cur); - mergeSet.add(key); - - String newMergeLoc = "MLoc" + (SSJavaLattice.seed++); - - System.out.println("---ASSIGN NEW MERGE LOC=" + newMergeLoc + " to " + mergeSet); - lattice.mergeIntoNewLocation(mergeSet, newMergeLoc); - - for (Iterator miterator = mergeSet.iterator(); miterator.hasNext();) { - String oldLocSymbol = (String) miterator.next(); - - Set> inferLocSet = - locInfo.getRelatedInferLocSet(oldLocSymbol); - System.out.println("---update related locations=" + inferLocSet - + " oldLocSymbol=" + oldLocSymbol); - - for (Iterator miterator2 = inferLocSet.iterator(); miterator2.hasNext();) { - Pair pair = - (Pair) miterator2.next(); - Descriptor enclosingDesc = pair.getFirst(); - Descriptor desc = pair.getSecond(); - - System.out.println("---inferLoc pair=" + pair); - - CompositeLocation inferLoc = - getLocationInfo(enclosingDesc).getInferLocation(desc); - System.out.println("oldLoc=" + inferLoc); - // if (curMethodInfo.md.equals(enclosingDesc)) { - // inferLoc = curMethodInfo.getInferLocation(desc); - // } else { - // inferLoc = - // getLocationInfo(enclosingDesc).getInferLocation(desc); - // } - - Location locElement = inferLoc.get(inferLoc.getSize() - 1); - - locElement.setLocIdentifier(newMergeLoc); - locInfo.addMapLocSymbolToRelatedInferLoc(newMergeLoc, enclosingDesc, desc); - - // if (curMethodInfo.md.equals(enclosingDesc)) { - // inferLoc = curMethodInfo.getInferLocation(desc); - // } else { - // inferLoc = - // getLocationInfo(enclosingDesc).getInferLocation(desc); - // } - - inferLoc = getLocationInfo(enclosingDesc).getInferLocation(desc); - System.out.println("---New Infer Loc=" + inferLoc); - - } - - locInfo.removeRelatedInferLocSet(oldLocSymbol, newMergeLoc); - - } - - for (Iterator iterator3 = mergeSet.iterator(); iterator3.hasNext();) { - String oldLoc = (String) iterator3.next(); - lattice.remove(oldLoc); - } - return true; - } - } - } - } - } - - } - return false; - } - private void checkLattices() { LinkedList descriptorListToAnalyze = ssjava.getSortedDescriptors(); @@ -1591,90 +2920,16 @@ public class LocationInference { } - private void inferLattices() { - - // do fixed-point analysis - - ssjava.init(); - LinkedList descriptorListToAnalyze = ssjava.getSortedDescriptors(); - - // Collections.sort(descriptorListToAnalyze, new - // Comparator() { - // public int compare(MethodDescriptor o1, MethodDescriptor o2) { - // return o1.getSymbol().compareToIgnoreCase(o2.getSymbol()); - // } - // }); - - // current descriptors to visit in fixed-point interprocedural analysis, - // prioritized by - // dependency in the call graph - methodDescriptorsToVisitStack.clear(); - - // descriptorListToAnalyze.removeFirst(); - - Set methodDescriptorToVistSet = new HashSet(); - methodDescriptorToVistSet.addAll(descriptorListToAnalyze); - - while (!descriptorListToAnalyze.isEmpty()) { - MethodDescriptor md = descriptorListToAnalyze.removeFirst(); - methodDescriptorsToVisitStack.add(md); - } - - // analyze scheduled methods until there are no more to visit - while (!methodDescriptorsToVisitStack.isEmpty()) { - // start to analyze leaf node - MethodDescriptor md = methodDescriptorsToVisitStack.pop(); - - SSJavaLattice methodLattice = - new SSJavaLattice(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM); - - MethodLocationInfo methodInfo = new MethodLocationInfo(md); - curMethodInfo = methodInfo; - - System.out.println(); - System.out.println("SSJAVA: Inferencing the lattice from " + md); - - try { - analyzeMethodLattice(md, methodLattice, methodInfo); - } catch (CyclicFlowException e) { - throw new Error("Fail to generate the method lattice for " + md); - } - - SSJavaLattice prevMethodLattice = getMethodLattice(md); - MethodLocationInfo prevMethodInfo = getMethodLocationInfo(md); - - if ((!methodLattice.equals(prevMethodLattice)) || (!methodInfo.equals(prevMethodInfo))) { - - setMethodLattice(md, methodLattice); - setMethodLocInfo(md, methodInfo); - - // results for callee changed, so enqueue dependents caller for - // further analysis - Iterator depsItr = ssjava.getDependents(md).iterator(); - while (depsItr.hasNext()) { - MethodDescriptor methodNext = depsItr.next(); - if (!methodDescriptorsToVisitStack.contains(methodNext) - && methodDescriptorToVistSet.contains(methodNext)) { - methodDescriptorsToVisitStack.add(methodNext); - } - } - - } - - } - - } - private void calculateExtraLocations() { - LinkedList descriptorListToAnalyze = ssjava.getSortedDescriptors(); - for (Iterator iterator = descriptorListToAnalyze.iterator(); iterator.hasNext();) { + + LinkedList methodDescList = ssjava.getSortedDescriptors(); + for (Iterator iterator = methodDescList.iterator(); iterator.hasNext();) { MethodDescriptor md = (MethodDescriptor) iterator.next(); - calculateExtraLocations(md); + if (!ssjava.getMethodContainingSSJavaLoop().equals(md)) { + calculateExtraLocations(md); + } } - } - private void setMethodLocInfo(MethodDescriptor md, MethodLocationInfo methodInfo) { - mapMethodDescToMethodLocationInfo.put(md, methodInfo); } private void checkLatticesOfVirtualMethods(MethodDescriptor md) { @@ -1770,226 +3025,366 @@ public class LocationInference { return desc; } - private void analyzeMethodLattice(MethodDescriptor md, SSJavaLattice methodLattice, - MethodLocationInfo methodInfo) throws CyclicFlowException { + private void calculatePCLOC(MethodDescriptor md) { - // first take a look at method invocation nodes to newly added relations - // from the callee - analyzeLatticeMethodInvocationNode(md, methodLattice, methodInfo); + System.out.println("#CalculatePCLOC"); + MethodSummary methodSummary = getMethodSummary(md); + FlowGraph fg = getFlowGraph(md); + Map mapParamToLoc = methodSummary.getMapParamIdxToInferLoc(); + + // calculate the initial program counter location + // PC location is higher than location types of parameters which has incoming flows. + + Set> paramLocTupleHavingInFlowSet = new HashSet>(); + Set paramDescNOTHavingInFlowSet = new HashSet(); + // Set paramNodeNOThavingInFlowSet = new HashSet(); + + int numParams = fg.getNumParameters(); + for (int i = 0; i < numParams; i++) { + FlowNode paramFlowNode = fg.getParamFlowNode(i); + Descriptor prefix = paramFlowNode.getDescTuple().get(0); + NTuple paramDescTuple = paramFlowNode.getCurrentDescTuple(); + NTuple paramLocTuple = translateToLocTuple(md, paramDescTuple); + + Set inNodeToParamSet = fg.getIncomingNodeSetByPrefix(prefix); + if (inNodeToParamSet.size() > 0) { + // parameter has in-value flows + + for (Iterator iterator = inNodeToParamSet.iterator(); iterator.hasNext();) { + FlowNode inNode = (FlowNode) iterator.next(); + Set outEdgeSet = fg.getOutEdgeSet(inNode); + for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) { + FlowEdge flowEdge = (FlowEdge) iterator2.next(); + if (flowEdge.getEndTuple().startsWith(prefix)) { + NTuple paramLocTupleWithIncomingFlow = + translateToLocTuple(md, flowEdge.getEndTuple()); + paramLocTupleHavingInFlowSet.add(paramLocTupleWithIncomingFlow); + } + } + } - if (!md.isStatic()) { - // set the this location - String thisLocSymbol = md.getThis().getSymbol(); - methodInfo.setThisLocName(thisLocSymbol); + // paramLocTupleHavingInFlowSet.add(paramLocTuple); + } else { + // paramNodeNOThavingInFlowSet.add(fg.getFlowNode(paramDescTuple)); + paramDescNOTHavingInFlowSet.add(prefix); + } } - // set the global location - methodInfo.setGlobalLocName(LocationInference.GLOBALLOC); - methodInfo.mapDescriptorToLocation(GLOBALDESC, new CompositeLocation( - new Location(md, GLOBALLOC))); + System.out.println("paramLocTupleHavingInFlowSet=" + paramLocTupleHavingInFlowSet); - // visit each node of method flow graph - FlowGraph fg = getFlowGraph(md); - Set nodeSet = fg.getNodeSet(); + if (paramLocTupleHavingInFlowSet.size() > 0 + && !coversAllParamters(md, fg, paramLocTupleHavingInFlowSet)) { - // for the method lattice, we need to look at the first element of - // NTuple - for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { - FlowNode srcNode = (FlowNode) iterator.next(); + // Here, generates a location in the method lattice that is higher than the + // paramLocTupleHavingInFlowSet + NTuple pcLocTuple = + generateLocTupleRelativeTo(md, paramLocTupleHavingInFlowSet, PCLOC); - Set outEdgeSet = fg.getOutEdgeSet(srcNode); - for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) { - FlowEdge outEdge = (FlowEdge) iterator2.next(); - FlowNode dstNode = outEdge.getDst(); + NTuple pcDescTuple = translateToDescTuple(pcLocTuple); - NTuple srcNodeTuple = srcNode.getDescTuple(); - NTuple dstNodeTuple = dstNode.getDescTuple(); + // System.out.println("pcLoc=" + pcLocTuple); - if (outEdge.getInitTuple().equals(srcNodeTuple) - && outEdge.getEndTuple().equals(dstNodeTuple)) { + CompositeLocation curPCLoc = methodSummary.getPCLoc(); + if (curPCLoc.get(0).isTop() || pcLocTuple.size() > curPCLoc.getSize()) { + methodSummary.setPCLoc(new CompositeLocation(pcLocTuple)); - if ((srcNodeTuple.size() > 1 && dstNodeTuple.size() > 1) - && srcNodeTuple.get(0).equals(dstNodeTuple.get(0))) { + Set flowNodeLowerthanPCLocSet = new HashSet(); + GlobalFlowGraph subGlobalFlowGraph = getSubGlobalFlowGraph(md); + // 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(); - // value flows between fields - Descriptor desc = srcNodeTuple.get(0); - ClassDescriptor classDesc; + if (!(node instanceof FlowReturnNode)) { + if (!paramDescNOTHavingInFlowSet.contains(node.getCurrentDescTuple().get(0))) { + flowNodeLowerthanPCLocSet.add(node); + fg.addValueFlowEdge(pcDescTuple, node.getDescTuple()); + subGlobalFlowGraph.addValueFlowEdge(pcLocTuple, + translateToLocTuple(md, node.getDescTuple())); + } + } else { + System.out.println("***SKIP PCLOC -> RETURNLOC=" + node); + } + + } + fg.getFlowNode(translateToDescTuple(pcLocTuple)).setSkeleton(true); + + if (pcLocTuple.get(0).getLocDescriptor().equals(md.getThis())) { + System.out.println("#########################################"); + for (Iterator iterator = flowNodeLowerthanPCLocSet.iterator(); iterator.hasNext();) { + FlowNode lowerNode = (FlowNode) iterator.next(); + if (lowerNode.getCompositeLocation() == null) { + NTuple lowerLocTuple = translateToLocTuple(md, lowerNode.getDescTuple()); + CompositeLocation newComp = + calculateCompositeLocationFromSubGlobalGraph(md, lowerNode); + if (newComp != null) { + subGlobalFlowGraph.addMapLocationToInferCompositeLocation(lowerLocTuple.get(0), + newComp); + lowerNode.setCompositeLocation(newComp); + System.out.println("NEW COMP LOC=" + newComp + " to lowerNode=" + lowerNode); + } - if (desc.equals(GLOBALDESC)) { - classDesc = md.getClassDesc(); - } else { - VarDescriptor varDesc = (VarDescriptor) srcNodeTuple.get(0); - classDesc = varDesc.getType().getClassDesc(); } - extractRelationFromFieldFlows(classDesc, srcNode, dstNode, 1); - } else { - // value flow between local var - local var or local var - field - addRelationToLattice(md, methodLattice, methodInfo, srcNode, dstNode); } } + } + } + } + + private boolean coversAllParamters(MethodDescriptor md, FlowGraph fg, + Set> paramLocTupleHavingInFlowSet) { - // create mapping from param idx to inferred composite location + int numParam = fg.getNumParameters(); + int size = paramLocTupleHavingInFlowSet.size(); - int offset; if (!md.isStatic()) { - // add 'this' reference location - offset = 1; - methodInfo.addMapParamIdxToInferLoc(0, methodInfo.getInferLocation(md.getThis())); - } else { - offset = 0; + + // if the method is not static && there is a parameter composite location && + // it is started with 'this', + // paramLocTupleHavingInFlowSet need to have 'this' parameter. + + FlowNode thisParamNode = fg.getParamFlowNode(0); + NTuple thisParamLocTuple = + translateToLocTuple(md, thisParamNode.getCurrentDescTuple()); + + if (!paramLocTupleHavingInFlowSet.contains(thisParamLocTuple)) { + + for (Iterator iterator = paramLocTupleHavingInFlowSet.iterator(); iterator.hasNext();) { + NTuple paramTuple = (NTuple) iterator.next(); + if (paramTuple.size() > 1 && paramTuple.get(0).getLocDescriptor().equals(md.getThis())) { + // paramLocTupleHavingInFlowSet.add(thisParamLocTuple); + // break; + size++; + } + } + + } } - for (int idx = 0; idx < md.numParameters(); idx++) { - Descriptor paramDesc = md.getParameter(idx); - CompositeLocation inferParamLoc = methodInfo.getInferLocation(paramDesc); - methodInfo.addMapParamIdxToInferLoc(idx + offset, inferParamLoc); + if (size == numParam) { + return true; + } else { + return false; } } - private void calculateExtraLocations(MethodDescriptor md) { - // calcualte pcloc, returnloc,... + private void calculateRETURNLOC(MethodDescriptor md) { + + System.out.println("#calculateRETURNLOC= " + md); + + // calculate a return location: + // the return location type is lower than all parameters and the location of return values + MethodSummary methodSummary = getMethodSummary(md); + // if (methodSummary.getRETURNLoc() != null) { + // System.out.println("$HERE?"); + // return; + // } - SSJavaLattice methodLattice = getMethodLattice(md); - MethodLocationInfo methodInfo = getMethodLocationInfo(md); FlowGraph fg = getFlowGraph(md); - Set nodeSet = fg.getNodeSet(); + Map mapParamToLoc = methodSummary.getMapParamIdxToInferLoc(); + Set paramIdxSet = mapParamToLoc.keySet(); - 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); + if (md.getReturnType() != null && !md.getReturnType().isVoid()) { + // first, generate the set of return value location types that starts + // with 'this' reference + + Set paramFlowNodeFlowingToReturnValueSet = getParamNodeFlowingToReturnValue(md); + // System.out.println("paramFlowNodeFlowingToReturnValueSet=" + // + paramFlowNodeFlowingToReturnValueSet); + + Set> tupleToBeHigherThanReturnLocSet = new HashSet>(); + for (Iterator iterator = paramFlowNodeFlowingToReturnValueSet.iterator(); iterator.hasNext();) { + FlowNode fn = (FlowNode) iterator.next(); + NTuple paramDescTuple = fn.getCurrentDescTuple(); + tupleToBeHigherThanReturnLocSet.add(translateToLocTuple(md, paramDescTuple)); + } + + Set returnNodeSet = fg.getReturnNodeSet(); + for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { + FlowNode returnNode = (FlowNode) iterator.next(); + NTuple returnDescTuple = returnNode.getCurrentDescTuple(); + tupleToBeHigherThanReturnLocSet.add(translateToLocTuple(md, returnDescTuple)); + } + 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 + NTuple returnLocTuple = + generateLocTupleRelativeTo(md, tupleToBeHigherThanReturnLocSet, RLOC); + + // System.out.println("returnLocTuple=" + returnLocTuple); + NTuple returnDescTuple = translateToDescTuple(returnLocTuple); + CompositeLocation curReturnLoc = methodSummary.getRETURNLoc(); + if (curReturnLoc == null || returnDescTuple.size() > curReturnLoc.getSize()) { + methodSummary.setRETURNLoc(new CompositeLocation(returnLocTuple)); + + for (Iterator iterator = tupleToBeHigherThanReturnLocSet.iterator(); iterator.hasNext();) { + NTuple higherTuple = (NTuple) iterator.next(); + fg.addValueFlowEdge(translateToDescTuple(higherTuple), returnDescTuple); } + fg.getFlowNode(returnDescTuple).setSkeleton(true); } + + // makes sure that PCLOC is higher than RETURNLOC + CompositeLocation pcLoc = methodSummary.getPCLoc(); + if (!pcLoc.get(0).isTop()) { + NTuple pcLocDescTuple = translateToDescTuple(pcLoc.getTuple()); + fg.addValueFlowEdge(pcLocDescTuple, returnDescTuple); + } + } - Map mapParamToLoc = methodInfo.getMapParamIdxToInferLoc(); - Set paramIdxSet = mapParamToLoc.keySet(); + } - try { - if (!ssjava.getMethodContainingSSJavaLoop().equals(md)) { - // calculate the initial program counter location - // PC location is higher than location types of all parameters - String pcLocSymbol = "PCLOC"; + private void calculateExtraLocations(MethodDescriptor md) { + // calcualte pcloc, returnloc,... + + System.out.println("\nSSJAVA:Calculate PCLOC/RETURNLOC locations: " + md); + + calculatePCLOC(md); + calculateRETURNLOC(md); + + } + + private NTuple generateLocTupleRelativeTo(MethodDescriptor md, + Set> paramLocTupleHavingInFlowSet, String locNamePrefix) { + + // System.out.println("-generateLocTupleRelativeTo=" + paramLocTupleHavingInFlowSet); + + NTuple higherLocTuple = new NTuple(); - Set paramInFlowSet = new HashSet(); + VarDescriptor thisVarDesc = md.getThis(); + // check if all paramter loc tuple is started with 'this' reference + boolean hasParamNotStartedWithThisRef = false; - for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) { - Integer paramIdx = (Integer) iterator.next(); + int minSize = 0; - FlowNode paramFlowNode = fg.getParamFlowNode(paramIdx); + Set> paramLocTupleStartedWithThis = new HashSet>(); - if (fg.getIncomingFlowNodeSet(paramFlowNode).size() > 0) { - // parameter has in-value flows - CompositeLocation inferLoc = mapParamToLoc.get(paramIdx); - paramInFlowSet.add(inferLoc); + next: for (Iterator iterator = paramLocTupleHavingInFlowSet.iterator(); iterator.hasNext();) { + NTuple paramLocTuple = (NTuple) iterator.next(); + Descriptor paramLocalDesc = paramLocTuple.get(0).getLocDescriptor(); + if (!paramLocalDesc.equals(thisVarDesc)) { + + Set inNodeSet = getFlowGraph(md).getIncomingNodeSetByPrefix(paramLocalDesc); + 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"); + continue next; } } + hasParamNotStartedWithThisRef = true; - if (paramInFlowSet.size() > 0) { - CompositeLocation lowestLoc = getLowest(methodLattice, paramInFlowSet); - assert (lowestLoc != null); - methodInfo.setPCLoc(lowestLoc); + } else if (paramLocTuple.size() > 1) { + paramLocTupleStartedWithThis.add(paramLocTuple); + if (minSize == 0 || minSize > paramLocTuple.size()) { + minSize = paramLocTuple.size(); } + } + } + // System.out.println("---paramLocTupleStartedWithThis=" + paramLocTupleStartedWithThis); + Descriptor enclosingDesc = md; + if (hasParamNotStartedWithThisRef) { + // in this case, PCLOC will be the local location + } else { + // all parameter is started with 'this', so PCLOC will be set relative to the composite + // location started with 'this'. + // for (int idx = 0; idx < minSize - 1; idx++) { + for (int idx = 0; idx < 1; idx++) { + Set locDescSet = new HashSet(); + Location curLoc = null; + NTuple paramLocTuple = null; + for (Iterator iterator = paramLocTupleStartedWithThis.iterator(); iterator.hasNext();) { + paramLocTuple = (NTuple) iterator.next(); + // 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); + if (locDescSet.size() != 1) { + break; + } + Location newLocElement = new Location(curLoc.getDescriptor(), curLoc.getLocDescriptor()); + System.out.println("newLocElement" + newLocElement); + higherLocTuple.add(newLocElement); + enclosingDesc = getClassTypeDescriptor(curLoc.getLocDescriptor()); } - // 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(); + String locIdentifier = locNamePrefix + (locSeed++); + NameDescriptor locDesc = new NameDescriptor(locIdentifier); + Location newLoc = new Location(enclosingDesc, locDesc); + higherLocTuple.add(newLoc); + System.out.println("---new loc tuple=" + higherLocTuple); - 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); - } - } + return higherLocTuple; + + } + + public ClassDescriptor getClassTypeDescriptor(Descriptor in) { + + if (in instanceof VarDescriptor) { + return ((VarDescriptor) in).getType().getClassDesc(); + } else if (in instanceof FieldDescriptor) { + return ((FieldDescriptor) in).getType().getClassDesc(); + } + // else if (in instanceof LocationDescriptor) { + // // here is the case that the descriptor 'in' is the last element of the assigned composite + // // location + // return ((VarDescriptor) locTuple.get(0).getLocDescriptor()).getType().getClassDesc(); + // } + else { + return null; + } + + } + + private Set> calculateHighestLocTupleSet( + Set> paramLocTupleHavingInFlowSet) { + + Set> highestSet = new HashSet>(); + + Iterator> iterator = paramLocTupleHavingInFlowSet.iterator(); + NTuple highest = iterator.next(); - 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); + for (; iterator.hasNext();) { + NTuple curLocTuple = (NTuple) iterator.next(); + if (isHigherThan(curLocTuple, highest)) { + // System.out.println(curLocTuple + " is greater than " + highest); + highest = curLocTuple; + } + } - } - } + highestSet.add(highest); - if (inferFieldReturnLocSet.size() > 0) { + MethodDescriptor md = (MethodDescriptor) highest.get(0).getDescriptor(); + VarDescriptor thisVarDesc = md.getThis(); - 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); + // System.out.println("highest=" + highest); - } 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)) { - addRelationHigherToLower(methodLattice, methodInfo, paramLocLocalSymbol, - returnLocSymbol); - } - } + for (Iterator> iter = paramLocTupleHavingInFlowSet.iterator(); iter.hasNext();) { + NTuple curLocTuple = iter.next(); - for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { - FlowNode returnNode = (FlowNode) iterator.next(); - CompositeLocation inferLoc = - generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode)); - if (!isGreaterThan(methodLattice, inferLoc, returnLocInferLoc)) { - addRelation(methodLattice, methodInfo, inferLoc, returnLocInferLoc); - } - } + if (!curLocTuple.equals(highest) && !hasOrderingRelation(highest, curLocTuple)) { - } + // System.out.println("add it to the highest set=" + curLocTuple); + highestSet.add(curLocTuple); } - } catch (CyclicFlowException e) { - e.printStackTrace(); } + return highestSet; + } private Set getHigherLocSymbolThan(SSJavaLattice lattice, String loc) { @@ -2106,68 +3501,18 @@ public class LocationInference { return false; } - private void recursiveAddRelationToLattice(int idx, MethodDescriptor md, - CompositeLocation srcInferLoc, CompositeLocation dstInferLoc) throws CyclicFlowException { + private GlobalFlowGraph getSubGlobalFlowGraph(MethodDescriptor md) { - String srcLocSymbol = srcInferLoc.get(idx).getLocIdentifier(); - String dstLocSymbol = dstInferLoc.get(idx).getLocIdentifier(); - - if (srcLocSymbol.equals(dstLocSymbol)) { - recursiveAddRelationToLattice(idx + 1, md, srcInferLoc, dstInferLoc); - } else { - - Descriptor parentDesc = srcInferLoc.get(idx).getDescriptor(); - LocationInfo locInfo = getLocationInfo(parentDesc); - - addRelationHigherToLower(getLattice(parentDesc), getLocationInfo(parentDesc), srcLocSymbol, - dstLocSymbol); + if (!mapMethodDescriptorToSubGlobalFlowGraph.containsKey(md)) { + mapMethodDescriptorToSubGlobalFlowGraph.put(md, new GlobalFlowGraph(md)); } - - } - - // 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) { - - System.out.println("\n##contributeCalleeFlows callee=" + mdCallee + "TO caller=" + mdCaller); - - getSubGlobalFlowGraph(mdCallee); - - } - - 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); - + System.out.println("-propagateFlowsToCallerWithNoCompositeLocation=" + min.printNode(0)); // 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 @@ -2190,211 +3535,95 @@ public class LocationInference { // check if the callee propagates an ordering constraints through // parameters - Set localReachSet = calleeFlowGraph.getLocalReachFlowNodeSetFrom(paramNode1); + // Set localReachSet = calleeFlowGraph.getLocalReachFlowNodeSetFrom(paramNode1); + Set localReachSet = + calleeFlowGraph.getReachableSetFrom(paramNode1.getDescTuple()); + + NTuple paramDescTuple1 = paramNode1.getCurrentDescTuple(); + NTuple paramDescTuple2 = paramNode2.getCurrentDescTuple(); + + // System.out.println("-param1CurTuple=" + paramDescTuple1 + " param2CurTuple=" + // + paramDescTuple2); + // System.out.println("-- localReachSet from param1=" + localReachSet); - if (localReachSet.contains(paramNode2)) { + if (paramDescTuple1.get(0).equals(paramDescTuple2.get(0))) { + // if two parameters share the same prefix + // it already has been assigned to a composite location + // so we don't need to add an additional ordering relation caused by these two + // paramters. + continue; + } + + if (arg1Tuple.size() > 0 && arg2Tuple.size() > 0 + && containsPrefix(paramNode2.getDescTuple().get(0), localReachSet)) { // 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("-param1=" + paramNode1 + " is higher than param2=" + paramNode2); - System.out - .println("-arg1Tuple=" + arg1Tuple + " is higher than arg2Tuple=" + arg2Tuple); - - // otherwise, flows between method/field locations... + // add a new flow between the corresponding arguments. callerFlowGraph.addValueFlowEdge(arg1Tuple, arg2Tuple); - System.out.println("arg1=" + arg1Tuple + " arg2=" + arg2Tuple); + // System.out.println("arg1=" + arg1Tuple + " arg2=" + arg2Tuple); + + // System.out + // .println("-arg1Tuple=" + arg1Tuple + " is higher than arg2Tuple=" + arg2Tuple); } - System.out.println(); + // 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(); - - 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); - - System.out.println("param1=" + paramNode1 + " curDescTuple=" - + paramNode1.getCurrentDescTuple()); - System.out.println("param2=" + paramNode2 + " curDescTuple=" - + paramNode2.getCurrentDescTuple()); - - // TODO: deprecated method - // NodeTupleSet tupleSetArg1 = getNodeTupleSetByArgIdx(min, i); - // NodeTupleSet tupleSetArg2 = getNodeTupleSetByArgIdx(min, k); - NodeTupleSet tupleSetArg1 = null; - NodeTupleSet tupleSetArg2 = null; - - 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); + // if a parameter has a composite location and the first element of the parameter location + // matches the callee's 'this' + // we have a more specific constraint: the caller's corresponding argument is higher than the + // parameter location which is translated into the caller - if (!min.getMethod().isStatic()) { - // check if this is the case that values flow to/from the - // current object reference 'this' - - 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 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); - 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, 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 - - CompositeLocation compLocForParam2 = - generateCompositeLocation(mdCallee, param2Prefix); - - // System.out.println("set comp loc=" + compLocForParam2 - // + - // " to " + paramNode2); - paramNode1.setCompositeLocation(compLocForParam2); - continue; - } - } - - } - } + for (int idx = 0; idx < numParam; idx++) { + FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx); + CompositeLocation compLoc = paramNode.getCompositeLocation(); + System.out.println("paramNode=" + paramNode + " compLoc=" + compLoc); + if (compLoc != null && compLoc.get(0).getLocDescriptor().equals(min.getMethod().getThis())) { + System.out.println("$$$COMPLOC CASE=" + compLoc + " idx=" + idx); + + NTuple argTuple = getNodeTupleByArgIdx(min, idx); + System.out.println("--- argTuple=" + argTuple + " current compLoc=" + + callerFlowGraph.getFlowNode(argTuple).getCompositeLocation()); + + NTuple translatedParamTuple = + translateCompositeLocationToCaller(idx, min, compLoc); + System.out.println("add a flow edge= " + argTuple + "->" + translatedParamTuple); + callerFlowGraph.addValueFlowEdge(argTuple, translatedParamTuple); + + Set> pcLocTupleSet = getPCLocTupleSet(min); + for (Iterator iterator = pcLocTupleSet.iterator(); iterator.hasNext();) { + NTuple pcLocTuple = (NTuple) iterator.next(); + callerFlowGraph.addValueFlowEdge(translateToDescTuple(pcLocTuple), translatedParamTuple); + } - // otherwise, flows between method/field locations... - callerFlowGraph.addValueFlowEdge(arg1Tuple, arg2Tuple); - System.out.println("arg1=" + arg1Tuple + " arg2=" + arg2Tuple); + } + } - } + } - } + private boolean containsPrefix(Descriptor prefixDesc, Set set) { - } - System.out.println(); - } + for (Iterator iterator = set.iterator(); iterator.hasNext();) { + FlowNode flowNode = (FlowNode) iterator.next(); + if (flowNode.getDescTuple().startsWith(prefixDesc)) { + System.out.println("FOUND=" + flowNode); + return true; } } - System.out.println("##\n"); + return false; } - private NTuple translateCompositeLocationToCaller(MethodInvokeNode min, + private NTuple translateCompositeLocationToCaller(int idx, 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)); } @@ -2407,20 +3636,24 @@ public class LocationInference { return tuple; } - private CompositeLocation generateCompositeLocation(MethodDescriptor md, - NTuple paramPrefix) { + private CompositeLocation generateCompositeLocation(NTuple prefixLocTuple) { - System.out.println("generateCompositeLocation=" + paramPrefix); + System.out.println("generateCompositeLocation=" + prefixLocTuple); - CompositeLocation newCompLoc = convertToCompositeLocation(md, paramPrefix); + CompositeLocation newCompLoc = new CompositeLocation(); + for (int i = 0; i < prefixLocTuple.size(); i++) { + newCompLoc.addLocation(prefixLocTuple.get(i)); + } + + Descriptor lastDescOfPrefix = prefixLocTuple.get(prefixLocTuple.size() - 1).getLocDescriptor(); - 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 if (lastDescOfPrefix.equals(GLOBALDESC)) { + MethodDescriptor currentMethodDesc = (MethodDescriptor) prefixLocTuple.get(0).getDescriptor(); + enclosingDescriptor = currentMethodDesc.getClassDesc(); } else { // var descriptor case enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc(); @@ -2438,49 +3671,35 @@ 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); + private CompositeLocation generateCompositeLocation(MethodDescriptor md, + NTuple paramPrefix) { - Set reachNodeSetFromParam1 = calleeFlowGraph.getReachFlowNodeSetFrom(paramNode1); - System.out.println("reachNodeSetFromParam1=" + reachNodeSetFromParam1); + System.out.println("generateCompositeLocation=" + paramPrefix); - for (int i = 0; i < calleePrefixList.size(); i++) { - NTuple curPrefix = calleePrefixList.get(i); - Set> reachableCommonPrefixSet = new HashSet>(); + CompositeLocation newCompLoc = convertToCompositeLocation(md, paramPrefix); - for (Iterator iterator2 = reachNodeSetFromParam1.iterator(); iterator2.hasNext();) { - FlowNode reachNode = (FlowNode) iterator2.next(); - if (reachNode.getCurrentDescTuple().startsWith(curPrefix)) { - reachableCommonPrefixSet.add(reachNode.getCurrentDescTuple()); - } - } + 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); - if (!reachableCommonPrefixSet.isEmpty()) { - System.out.println("###REACHABLECOMONPREFIX=" + reachableCommonPrefixSet - + " with curPreFix=" + curPrefix); - return curPrefix; - } + LocationDescriptor newLocDescriptor = generateNewLocationDescriptor(); + newLocDescriptor.setEnclosingClassDesc(enclosingDescriptor); - } + Location newLoc = new Location(enclosingDescriptor, newLocDescriptor.getSymbol()); + newLoc.setLocDescriptor(newLocDescriptor); + newCompLoc.addLocation(newLoc); - return null; + // System.out.println("--newCompLoc=" + newCompLoc); + return newCompLoc; } private List> translatePrefixListToCallee(Descriptor baseRef, @@ -2504,52 +3723,6 @@ 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();) { - FlowNode inNode = (FlowNode) iterator.next(); - - NTuple inNodeTuple = inNode.getCurrentDescTuple(); - - // CompositeLocation inNodeInferredLoc = - // generateInferredCompositeLocation(methodInfo, inNodeTuple); - // NTuple inNodeInferredLocTuple = inNodeInferredLoc.getTuple(); - - for (int i = 1; i < inNodeTuple.size(); i++) { - NTuple prefix = inNodeTuple.subList(0, i); - if (!prefixList.contains(prefix)) { - prefixList.add(prefix); - } - } - } - - Collections.sort(prefixList, new Comparator>() { - public int compare(NTuple arg0, NTuple arg1) { - int s0 = arg0.size(); - int s1 = arg1.size(); - if (s0 > s1) { - return -1; - } else if (s0 == s1) { - return 0; - } else { - return 1; - } - } - }); - - return prefixList; - - } - public CompositeLocation convertToCompositeLocation(MethodDescriptor md, NTuple tuple) { CompositeLocation compLoc = new CompositeLocation(); @@ -2564,17 +3737,17 @@ public class LocationInference { if (curDescriptor instanceof VarDescriptor) { enclosingDescriptor = md.getClassDesc(); + } else if (curDescriptor instanceof FieldDescriptor) { + enclosingDescriptor = ((FieldDescriptor) curDescriptor).getClassDescriptor(); } else if (curDescriptor instanceof NameDescriptor) { // it is "GLOBAL LOC" case! enclosingDescriptor = GLOBALDESC; } else { - enclosingDescriptor = ((FieldDescriptor) curDescriptor).getClassDescriptor(); + enclosingDescriptor = null; } } - System.out.println("-convertToCompositeLocation from=" + tuple + " to " + compLoc); - return compLoc; } @@ -2588,118 +3761,20 @@ public class LocationInference { // if there is no prefix shared by both of them, return -1 int minSize = tuple1.size(); - if (minSize > tuple2.size()) { - minSize = tuple2.size(); - } - - int idx = -1; - for (int i = 0; i < minSize; i++) { - if (!tuple1.get(i).equals(tuple2.get(i))) { - break; - } else { - idx++; - } - } - - return idx; - } - - private void analyzeLatticeMethodInvocationNode(MethodDescriptor mdCaller, - SSJavaLattice methodLattice, MethodLocationInfo methodInfo) - throws CyclicFlowException { - - // 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 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(); - propagateRelationToCaller(min, mdCaller, possibleMdCallee, methodLattice, methodInfo); - } - - } - } - - } - - private void propagateRelationToCaller(MethodInvokeNode min, MethodDescriptor mdCaller, - MethodDescriptor possibleMdCallee, SSJavaLattice methodLattice, - MethodLocationInfo methodInfo) throws CyclicFlowException { - - SSJavaLattice calleeLattice = getMethodLattice(possibleMdCallee); - MethodLocationInfo calleeLocInfo = getMethodLocationInfo(possibleMdCallee); - FlowGraph calleeFlowGraph = getFlowGraph(possibleMdCallee); - - int numParam = calleeLocInfo.getNumParam(); - for (int i = 0; i < numParam; i++) { - CompositeLocation param1 = calleeLocInfo.getParamCompositeLocation(i); - for (int k = 0; k < numParam; k++) { - if (i != k) { - CompositeLocation param2 = calleeLocInfo.getParamCompositeLocation(k); - - if (isGreaterThan(getLattice(possibleMdCallee), param1, param2)) { - // NodeTupleSet argDescTupleSet1 = getNodeTupleSetByArgIdx(min, i); - // NodeTupleSet argDescTupleSet2 = getNodeTupleSetByArgIdx(min, k); - NodeTupleSet argDescTupleSet1 = null; - NodeTupleSet argDescTupleSet2 = null; - - // the callee has the relation in which param1 is higher than param2 - // therefore, the caller has to have the relation in which arg1 is - // higher than arg2 - - for (Iterator> iterator = argDescTupleSet1.iterator(); iterator - .hasNext();) { - NTuple argDescTuple1 = iterator.next(); - - for (Iterator> iterator2 = argDescTupleSet2.iterator(); iterator2 - .hasNext();) { - NTuple argDescTuple2 = iterator2.next(); - - // retreive inferred location by the local var descriptor - - NTuple tuple1 = getFlowGraph(mdCaller).getLocationTuple(argDescTuple1); - NTuple tuple2 = getFlowGraph(mdCaller).getLocationTuple(argDescTuple2); - - // CompositeLocation higherInferLoc = - // methodInfo.getInferLocation(argTuple1.get(0)); - // CompositeLocation lowerInferLoc = - // methodInfo.getInferLocation(argTuple2.get(0)); - - CompositeLocation inferLoc1 = generateInferredCompositeLocation(methodInfo, tuple1); - CompositeLocation inferLoc2 = generateInferredCompositeLocation(methodInfo, tuple2); - - // addRelation(methodLattice, methodInfo, inferLoc1, inferLoc2); - - addFlowGraphEdge(mdCaller, argDescTuple1, argDescTuple2); - - } - - } + if (minSize > tuple2.size()) { + minSize = tuple2.size(); + } - } - } + int idx = -1; + for (int i = 0; i < minSize; i++) { + if (!tuple1.get(i).equals(tuple2.get(i))) { + break; + } else { + idx++; } } + return idx; } private CompositeLocation generateInferredCompositeLocation(MethodLocationInfo methodInfo, @@ -2741,36 +3816,6 @@ public class LocationInference { return inferLoc; } - private void addRelation(SSJavaLattice methodLattice, MethodLocationInfo methodInfo, - CompositeLocation srcInferLoc, CompositeLocation dstInferLoc) throws CyclicFlowException { - - System.out.println("addRelation --- srcInferLoc=" + srcInferLoc + " dstInferLoc=" - + dstInferLoc); - String srcLocalLocSymbol = srcInferLoc.get(0).getLocIdentifier(); - String dstLocalLocSymbol = dstInferLoc.get(0).getLocIdentifier(); - - if (srcInferLoc.getSize() == 1 && dstInferLoc.getSize() == 1) { - // add a new relation to the local lattice - addRelationHigherToLower(methodLattice, methodInfo, srcLocalLocSymbol, dstLocalLocSymbol); - } else if (srcInferLoc.getSize() > 1 && dstInferLoc.getSize() > 1) { - // both src and dst have assigned to a composite location - - if (!srcLocalLocSymbol.equals(dstLocalLocSymbol)) { - addRelationHigherToLower(methodLattice, methodInfo, srcLocalLocSymbol, dstLocalLocSymbol); - } else { - recursivelyAddRelation(1, srcInferLoc, dstInferLoc); - } - } else { - // either src or dst has assigned to a composite location - if (!srcLocalLocSymbol.equals(dstLocalLocSymbol)) { - addRelationHigherToLower(methodLattice, methodInfo, srcLocalLocSymbol, dstLocalLocSymbol); - } - } - - System.out.println(); - - } - public LocationInfo getLocationInfo(Descriptor d) { if (d instanceof MethodDescriptor) { return getMethodLocationInfo((MethodDescriptor) d); @@ -2799,101 +3844,6 @@ public class LocationInference { } - private void addRelationToLattice(MethodDescriptor md, SSJavaLattice methodLattice, - MethodLocationInfo methodInfo, FlowNode srcNode, FlowNode dstNode) throws CyclicFlowException { - - System.out.println(); - System.out.println("### addRelationToLattice src=" + srcNode + " dst=" + dstNode); - - // add a new binary relation of dstNode < srcNode - FlowGraph flowGraph = getFlowGraph(md); - try { - System.out.println("***** src composite case::"); - calculateCompositeLocation(flowGraph, methodLattice, methodInfo, srcNode, null); - - CompositeLocation srcInferLoc = - generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(srcNode)); - CompositeLocation dstInferLoc = - generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(dstNode)); - addRelation(methodLattice, methodInfo, srcInferLoc, dstInferLoc); - } catch (CyclicFlowException e) { - // there is a cyclic value flow... try to calculate a composite location - // for the destination node - System.out.println("***** dst composite case::"); - calculateCompositeLocation(flowGraph, methodLattice, methodInfo, dstNode, srcNode); - CompositeLocation srcInferLoc = - generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(srcNode)); - CompositeLocation dstInferLoc = - generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(dstNode)); - try { - addRelation(methodLattice, methodInfo, srcInferLoc, dstInferLoc); - } catch (CyclicFlowException e1) { - throw new Error("Failed to merge cyclic value flows into a shared location."); - } - } - - } - - private void recursivelyAddRelation(int idx, CompositeLocation srcInferLoc, - CompositeLocation dstInferLoc) throws CyclicFlowException { - - String srcLocSymbol = srcInferLoc.get(idx).getLocIdentifier(); - String dstLocSymbol = dstInferLoc.get(idx).getLocIdentifier(); - - Descriptor parentDesc = srcInferLoc.get(idx).getDescriptor(); - - if (srcLocSymbol.equals(dstLocSymbol)) { - // check if it is the case of shared location - if (srcInferLoc.getSize() == (idx + 1) && dstInferLoc.getSize() == (idx + 1)) { - Location inferLocElement = srcInferLoc.get(idx); - System.out.println("SET SHARED LOCATION=" + inferLocElement); - getLattice(inferLocElement.getDescriptor()) - .addSharedLoc(inferLocElement.getLocIdentifier()); - } else if (srcInferLoc.getSize() > (idx + 1) && dstInferLoc.getSize() > (idx + 1)) { - recursivelyAddRelation(idx + 1, srcInferLoc, dstInferLoc); - } - } else { - addRelationHigherToLower(getLattice(parentDesc), getLocationInfo(parentDesc), srcLocSymbol, - dstLocSymbol); - } - } - - private void recursivelyAddCompositeRelation(MethodDescriptor md, FlowGraph flowGraph, - MethodLocationInfo methodInfo, FlowNode srcNode, FlowNode dstNode, Descriptor srcDesc, - Descriptor dstDesc) throws CyclicFlowException { - - CompositeLocation inferSrcLoc; - CompositeLocation inferDstLoc = methodInfo.getInferLocation(dstDesc); - - if (srcNode.getLocTuple().size() > 1) { - // field access - inferSrcLoc = new CompositeLocation(); - - NTuple locTuple = flowGraph.getLocationTuple(srcNode); - for (int i = 0; i < locTuple.size(); i++) { - inferSrcLoc.addLocation(locTuple.get(i)); - } - - } else { - inferSrcLoc = methodInfo.getInferLocation(srcDesc); - } - - if (dstNode.getLocTuple().size() > 1) { - // field access - inferDstLoc = new CompositeLocation(); - - NTuple locTuple = flowGraph.getLocationTuple(dstNode); - for (int i = 0; i < locTuple.size(); i++) { - inferDstLoc.addLocation(locTuple.get(i)); - } - - } else { - inferDstLoc = methodInfo.getInferLocation(dstDesc); - } - - recursiveAddRelationToLattice(1, md, inferSrcLoc, inferDstLoc); - } - private void addPrefixMapping(Map, Set>> map, NTuple prefix, NTuple element) { @@ -2903,254 +3853,6 @@ public class LocationInference { map.get(prefix).add(element); } - private boolean calculateCompositeLocation(FlowGraph flowGraph, - SSJavaLattice methodLattice, MethodLocationInfo methodInfo, FlowNode flowNode, - FlowNode srcNode) throws CyclicFlowException { - - Descriptor localVarDesc = flowNode.getDescTuple().get(0); - NTuple flowNodelocTuple = flowGraph.getLocationTuple(flowNode); - - if (localVarDesc.equals(methodInfo.getMethodDesc())) { - return false; - } - - Set inNodeSet = flowGraph.getIncomingFlowNodeSet(flowNode); - Set reachableNodeSet = flowGraph.getReachFlowNodeSetFrom(flowNode); - - Map, Set>> mapPrefixToIncomingLocTupleSet = - new HashMap, Set>>(); - - List> prefixList = new ArrayList>(); - - for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) { - FlowNode inNode = (FlowNode) iterator.next(); - NTuple inNodeTuple = flowGraph.getLocationTuple(inNode); - - CompositeLocation inNodeInferredLoc = - generateInferredCompositeLocation(methodInfo, inNodeTuple); - - NTuple inNodeInferredLocTuple = inNodeInferredLoc.getTuple(); - - for (int i = 1; i < inNodeInferredLocTuple.size(); i++) { - NTuple prefix = inNodeInferredLocTuple.subList(0, i); - if (!prefixList.contains(prefix)) { - prefixList.add(prefix); - } - addPrefixMapping(mapPrefixToIncomingLocTupleSet, prefix, inNodeInferredLocTuple); - } - } - - Collections.sort(prefixList, new Comparator>() { - public int compare(NTuple arg0, NTuple arg1) { - int s0 = arg0.size(); - int s1 = arg1.size(); - if (s0 > s1) { - return -1; - } else if (s0 == s1) { - return 0; - } else { - return 1; - } - } - }); - - // System.out.println("prefixList=" + prefixList); - // System.out.println("reachableNodeSet=" + reachableNodeSet); - - // find out reachable nodes that have the longest common prefix - for (int i = 0; i < prefixList.size(); i++) { - NTuple curPrefix = prefixList.get(i); - Set> reachableCommonPrefixSet = new HashSet>(); - - for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) { - FlowNode reachableNode = (FlowNode) iterator2.next(); - NTuple reachLocTuple = flowGraph.getLocationTuple(reachableNode); - CompositeLocation reachLocInferLoc = - generateInferredCompositeLocation(methodInfo, reachLocTuple); - if (reachLocInferLoc.getTuple().startsWith(curPrefix)) { - reachableCommonPrefixSet.add(reachLocTuple); - } - } - - if (!reachableCommonPrefixSet.isEmpty()) { - // found reachable nodes that start with the prefix curPrefix - // need to assign a composite location - - // first, check if there are more than one the set of locations that has - // the same length of the longest reachable prefix, no way to assign - // a composite location to the input local var - // prefixSanityCheck(prefixList, i, flowGraph, reachableNodeSet); - - Set> incomingCommonPrefixSet = - mapPrefixToIncomingLocTupleSet.get(curPrefix); - - int idx = curPrefix.size(); - NTuple element = incomingCommonPrefixSet.iterator().next(); - Descriptor desc = element.get(idx).getDescriptor(); - - SSJavaLattice lattice = getLattice(desc); - LocationInfo locInfo = getLocationInfo(desc); - - CompositeLocation inferLocation = - generateInferredCompositeLocation(methodInfo, flowNodelocTuple); - - // methodInfo.getInferLocation(localVarDesc); - CompositeLocation newInferLocation = new CompositeLocation(); - - if (inferLocation.getTuple().startsWith(curPrefix)) { - // the same infer location is already existed. no need to do - // anything - System.out.println("NO ATTEMPT TO MAKE A COMPOSITE LOCATION curPrefix=" + curPrefix); - - // TODO: refactoring! - if (srcNode != null) { - CompositeLocation newLoc = new CompositeLocation(); - String newLocSymbol = "Loc" + (SSJavaLattice.seed++); - for (int locIdx = 0; locIdx < curPrefix.size(); locIdx++) { - newLoc.addLocation(curPrefix.get(locIdx)); - } - Location newLocationElement = new Location(desc, newLocSymbol); - newLoc.addLocation(newLocationElement); - - Descriptor srcLocalVar = srcNode.getDescTuple().get(0); - methodInfo.mapDescriptorToLocation(srcLocalVar, newLoc.clone()); - addMapLocSymbolToInferredLocation(methodInfo.getMethodDesc(), srcLocalVar, newLoc); - methodInfo.removeMaplocalVarToLocSet(srcLocalVar); - - // add the field/var descriptor to the set of the location symbol - int lastIdx = srcNode.getLocTuple().size() - 1; - Descriptor lastFlowNodeDesc = srcNode.getDescTuple().get(lastIdx); - NTuple srcNodelocTuple = flowGraph.getLocationTuple(srcNode); - Descriptor enclosinglastLastFlowNodeDesc = srcNodelocTuple.get(lastIdx).getDescriptor(); - - CompositeLocation newlyInferredLocForFlowNode = - generateInferredCompositeLocation(methodInfo, srcNodelocTuple); - Location lastInferLocElement = - newlyInferredLocForFlowNode.get(newlyInferredLocForFlowNode.getSize() - 1); - Descriptor enclosingLastInferLocElement = lastInferLocElement.getDescriptor(); - - // getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToDescSet( - // lastInferLocElement.getLocIdentifier(), lastFlowNodeDesc); - getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToRelatedInferLoc( - lastInferLocElement.getLocIdentifier(), enclosinglastLastFlowNodeDesc, - lastFlowNodeDesc); - - System.out.println("@@@@@@@ ASSIGN " + newLoc + " to SRC=" + srcNode); - } - - return true; - } else { - // assign a new composite location - - // String oldMethodLocationSymbol = - // inferLocation.get(0).getLocIdentifier(); - String newLocSymbol = "Loc" + (SSJavaLattice.seed++); - for (int locIdx = 0; locIdx < curPrefix.size(); locIdx++) { - newInferLocation.addLocation(curPrefix.get(locIdx)); - } - Location newLocationElement = new Location(desc, newLocSymbol); - newInferLocation.addLocation(newLocationElement); - - // maps local variable to location types of the common prefix - methodInfo.mapDescriptorToLocation(localVarDesc, newInferLocation.clone()); - - // methodInfo.mapDescriptorToLocation(localVarDesc, newInferLocation); - addMapLocSymbolToInferredLocation(methodInfo.getMethodDesc(), localVarDesc, - newInferLocation); - methodInfo.removeMaplocalVarToLocSet(localVarDesc); - - // add the field/var descriptor to the set of the location symbol - int lastIdx = flowNode.getLocTuple().size() - 1; - Descriptor lastFlowNodeDesc = flowNode.getDescTuple().get(lastIdx); - Descriptor enclosinglastLastFlowNodeDesc = flowNodelocTuple.get(lastIdx).getDescriptor(); - - CompositeLocation newlyInferredLocForFlowNode = - generateInferredCompositeLocation(methodInfo, flowNodelocTuple); - Location lastInferLocElement = - newlyInferredLocForFlowNode.get(newlyInferredLocForFlowNode.getSize() - 1); - Descriptor enclosingLastInferLocElement = lastInferLocElement.getDescriptor(); - - // getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToDescSet( - // lastInferLocElement.getLocIdentifier(), lastFlowNodeDesc); - getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToRelatedInferLoc( - lastInferLocElement.getLocIdentifier(), enclosinglastLastFlowNodeDesc, - lastFlowNodeDesc); - - // clean up the previous location - // Location prevInferLocElement = - // inferLocation.get(inferLocation.getSize() - 1); - // Descriptor prevEnclosingDesc = prevInferLocElement.getDescriptor(); - // - // SSJavaLattice targetLattice; - // LocationInfo targetInfo; - // if (prevEnclosingDesc.equals(methodInfo.getMethodDesc())) { - // targetLattice = methodLattice; - // targetInfo = methodInfo; - // } else { - // targetLattice = getLattice(prevInferLocElement.getDescriptor()); - // targetInfo = getLocationInfo(prevInferLocElement.getDescriptor()); - // } - // - // Set> associstedDescSet = - // targetInfo.getRelatedInferLocSet(prevInferLocElement.getLocIdentifier()); - // - // if (associstedDescSet.size() == 1) { - // targetLattice.remove(prevInferLocElement.getLocIdentifier()); - // } else { - // associstedDescSet.remove(lastFlowNodeDesc); - // } - - } - - System.out.println("curPrefix=" + curPrefix); - System.out.println("ASSIGN NEW COMPOSITE LOCATION =" + newInferLocation + " to " - + flowNode); - - String newlyInsertedLocName = - newInferLocation.get(newInferLocation.getSize() - 1).getLocIdentifier(); - - System.out.println("-- add in-flow"); - for (Iterator iterator = incomingCommonPrefixSet.iterator(); iterator.hasNext();) { - NTuple tuple = (NTuple) iterator.next(); - Location loc = tuple.get(idx); - String higher = loc.getLocIdentifier(); - addRelationHigherToLower(lattice, locInfo, higher, newlyInsertedLocName); - } - - System.out.println("-- add out flow"); - for (Iterator iterator = reachableCommonPrefixSet.iterator(); iterator.hasNext();) { - NTuple tuple = (NTuple) iterator.next(); - if (tuple.size() > idx) { - Location loc = tuple.get(idx); - String lower = loc.getLocIdentifier(); - // String lower = - // locInfo.getFieldInferLocation(loc.getLocDescriptor()).getLocIdentifier(); - addRelationHigherToLower(lattice, locInfo, newlyInsertedLocName, lower); - } - } - - return true; - } - - } - - return false; - - } - - private void addMapLocSymbolToInferredLocation(MethodDescriptor md, Descriptor localVar, - CompositeLocation inferLoc) { - - Location locElement = inferLoc.get((inferLoc.getSize() - 1)); - Descriptor enclosingDesc = locElement.getDescriptor(); - LocationInfo locInfo = getLocationInfo(enclosingDesc); - locInfo.addMapLocSymbolToRelatedInferLoc(locElement.getLocIdentifier(), md, localVar); - } - - private boolean isCompositeLocation(CompositeLocation cl) { - return cl.getSize() > 1; - } - private boolean containsNonPrimitiveElement(Set descSet) { for (Iterator iterator = descSet.iterator(); iterator.hasNext();) { Descriptor desc = (Descriptor) iterator.next(); @@ -3171,98 +3873,6 @@ public class LocationInference { return false; } - private void addRelationHigherToLower(SSJavaLattice lattice, LocationInfo locInfo, - String higher, String lower) throws CyclicFlowException { - - System.out.println("---addRelationHigherToLower " + higher + " -> " + lower - + " to the lattice of " + locInfo.getDescIdentifier()); - // if (higher.equals(lower) && lattice.isSharedLoc(higher)) { - // return; - // } - Set cycleElementSet = lattice.getPossibleCycleElements(higher, lower); - - boolean hasNonPrimitiveElement = false; - for (Iterator iterator = cycleElementSet.iterator(); iterator.hasNext();) { - String cycleElementLocSymbol = (String) iterator.next(); - - Set descSet = locInfo.getDescSet(cycleElementLocSymbol); - if (containsNonPrimitiveElement(descSet)) { - hasNonPrimitiveElement = true; - break; - } - } - - if (hasNonPrimitiveElement) { - System.out.println("#Check cycle= " + lower + " < " + higher + " cycleElementSet=" - + cycleElementSet); - // if there is non-primitive element in the cycle, no way to merge cyclic - // elements into the shared location - throw new CyclicFlowException(); - } - - if (cycleElementSet.size() > 0) { - - String newSharedLoc = "SharedLoc" + (SSJavaLattice.seed++); - - System.out.println("---ASSIGN NEW SHARED LOC=" + newSharedLoc + " to " + cycleElementSet); - lattice.mergeIntoNewLocation(cycleElementSet, newSharedLoc); - lattice.addSharedLoc(newSharedLoc); - - for (Iterator iterator = cycleElementSet.iterator(); iterator.hasNext();) { - String oldLocSymbol = (String) iterator.next(); - - Set> inferLocSet = locInfo.getRelatedInferLocSet(oldLocSymbol); - System.out.println("---update related locations=" + inferLocSet); - for (Iterator iterator2 = inferLocSet.iterator(); iterator2.hasNext();) { - Pair pair = (Pair) iterator2.next(); - Descriptor enclosingDesc = pair.getFirst(); - Descriptor desc = pair.getSecond(); - - CompositeLocation inferLoc; - if (curMethodInfo.md.equals(enclosingDesc)) { - inferLoc = curMethodInfo.getInferLocation(desc); - } else { - inferLoc = getLocationInfo(enclosingDesc).getInferLocation(desc); - } - - Location locElement = inferLoc.get(inferLoc.getSize() - 1); - - locElement.setLocIdentifier(newSharedLoc); - locInfo.addMapLocSymbolToRelatedInferLoc(newSharedLoc, enclosingDesc, desc); - - if (curMethodInfo.md.equals(enclosingDesc)) { - inferLoc = curMethodInfo.getInferLocation(desc); - } else { - inferLoc = getLocationInfo(enclosingDesc).getInferLocation(desc); - } - System.out.println("---New Infer Loc=" + inferLoc); - - } - locInfo.removeRelatedInferLocSet(oldLocSymbol, newSharedLoc); - - } - - lattice.addSharedLoc(newSharedLoc); - - } else if (!lattice.isGreaterThan(higher, lower)) { - lattice.addRelationHigherToLower(higher, lower); - } - } - - private void replaceOldLocWithNewLoc(SSJavaLattice methodLattice, String oldLocSymbol, - String newLocSymbol) { - - if (methodLattice.containsKey(oldLocSymbol)) { - methodLattice.substituteLocation(oldLocSymbol, newLocSymbol); - } - - } - - public boolean isPrimitiveLocalVariable(FlowNode node) { - VarDescriptor varDesc = (VarDescriptor) node.getDescTuple().get(0); - return varDesc.getType().isPrimitive(); - } - private SSJavaLattice getLattice(Descriptor d) { if (d instanceof MethodDescriptor) { return getMethodLattice((MethodDescriptor) d); @@ -3299,9 +3909,16 @@ public class LocationInference { if (idx == 0) { classDesc = ((VarDescriptor) desc).getType().getClassDesc(); } else { - classDesc = ((FieldDescriptor) desc).getType().getClassDesc(); + if (desc instanceof FieldDescriptor) { + classDesc = ((FieldDescriptor) desc).getType().getClassDesc(); + } else { + // this case is that the local variable has a composite location assignment + // the following element after the composite location to the local variable + // has the enclosing descriptor of the local variable + Descriptor localDesc = srcNode.getDescTuple().get(0); + classDesc = ((VarDescriptor) localDesc).getType().getClassDesc(); + } } - extractFlowsBetweenFields(classDesc, srcNode, dstNode, idx + 1); } else { @@ -3309,46 +3926,17 @@ public class LocationInference { Descriptor srcFieldDesc = srcCurTuple.get(idx); Descriptor dstFieldDesc = dstCurTuple.get(idx); - // add a new edge - getHierarchyGraph(cd).addEdge(srcFieldDesc, dstFieldDesc); - - } - - } - - private void extractRelationFromFieldFlows(ClassDescriptor cd, FlowNode srcNode, - FlowNode dstNode, int idx) throws CyclicFlowException { - - if (srcNode.getLocTuple().get(idx).equals(dstNode.getLocTuple().get(idx)) - && srcNode.getLocTuple().size() > (idx + 1) && dstNode.getLocTuple().size() > (idx + 1)) { - // value flow between fields: we don't need to add a binary relation - // for this case - - Descriptor desc = srcNode.getDescTuple().get(idx); - ClassDescriptor classDesc; - - if (idx == 0) { - classDesc = ((VarDescriptor) desc).getType().getClassDesc(); - } else { - classDesc = ((FieldDescriptor) desc).getType().getClassDesc(); + System.out.println("srcFieldDesc=" + srcFieldDesc + " dstFieldDesc=" + dstFieldDesc + + " idx=" + idx); + if (!srcFieldDesc.equals(dstFieldDesc)) { + // add a new edge + System.out.println("-ADD EDGE"); + getHierarchyGraph(cd).addEdge(srcFieldDesc, dstFieldDesc); + } else if (!isReference(srcFieldDesc) && !isReference(dstFieldDesc)) { + System.out.println("-ADD EDGE"); + getHierarchyGraph(cd).addEdge(srcFieldDesc, dstFieldDesc); } - extractRelationFromFieldFlows(classDesc, srcNode, dstNode, idx + 1); - - } else { - - Descriptor srcFieldDesc = srcNode.getDescTuple().get(idx); - Descriptor dstFieldDesc = dstNode.getDescTuple().get(idx); - - // add a new binary relation of dstNode < srcNode - SSJavaLattice fieldLattice = getFieldLattice(cd); - LocationInfo fieldInfo = getFieldLocationInfo(cd); - - String srcSymbol = fieldInfo.getFieldInferLocation(srcFieldDesc).getLocIdentifier(); - String dstSymbol = fieldInfo.getFieldInferLocation(dstFieldDesc).getLocIdentifier(); - - addRelationHigherToLower(fieldLattice, fieldInfo, srcSymbol, dstSymbol); - } } @@ -3394,7 +3982,8 @@ public class LocationInference { for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) { MethodDescriptor calleemd = (MethodDescriptor) iterator.next(); if ((!ssjava.isTrustMethod(calleemd)) - && (!ssjava.isSSJavaUtil(calleemd.getClassDesc()))) { + && (!ssjava.isSSJavaUtil(calleemd.getClassDesc())) + && (!calleemd.getModifiers().isNative())) { if (!visited.contains(calleemd)) { temp_toanalyzeMethodList.add(calleemd); } @@ -3416,6 +4005,21 @@ public class LocationInference { } + public boolean isTransitivelyCalledFrom(MethodDescriptor callee, MethodDescriptor caller) { + // if the callee is transitively invoked from the caller + // return true; + + int callerIdx = toanalyze_methodDescList.indexOf(caller); + int calleeIdx = toanalyze_methodDescList.indexOf(callee); + + if (callerIdx < calleeIdx) { + return true; + } + + return false; + + } + public void constructFlowGraph() { System.out.println(""); @@ -3450,134 +4054,80 @@ public class LocationInference { mapMethodDescriptorToFlowGraph.put(md, fg); analyzeMethodBody(md.getClassDesc(), md); - propagateFlowsFromCalleesWithNoCompositeLocation(md); - // assignCompositeLocation(md); + // System.out.println("##constructSubGlobalFlowGraph"); + // GlobalFlowGraph subGlobalFlowGraph = constructSubGlobalFlowGraph(fg); + // mapMethodDescriptorToSubGlobalFlowGraph.put(md, subGlobalFlowGraph); + // + // // TODO + // System.out.println("##addValueFlowsFromCalleeSubGlobalFlowGraph"); + // addValueFlowsFromCalleeSubGlobalFlowGraph(md, subGlobalFlowGraph); + // subGlobalFlowGraph.writeGraph("_SUBGLOBAL"); + // + // propagateFlowsFromCalleesWithNoCompositeLocation(md); } } - _debug_printGraph(); - - } - - 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); - } + // _debug_printGraph(); } - 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(); + private void constructGlobalFlowGraph() { + LinkedList methodDescList = + (LinkedList) toanalyze_methodDescList.clone(); - // assign a composite location only to the local variable - if (flowNode.getCurrentDescTuple().size() == 1) { + while (!methodDescList.isEmpty()) { + MethodDescriptor md = methodDescList.removeLast(); + if (state.SSJAVADEBUG) { + System.out.println(); + System.out.println("SSJAVA: Constructing a sub global flow graph: " + md); - List> prefixList = calculatePrefixList(flowGraph, flowNode); - Set reachSet = flowGraph.getReachFlowNodeSetFrom(flowNode); + constructSubGlobalFlowGraph(getFlowGraph(md)); - for (int i = 0; i < prefixList.size(); i++) { - NTuple curPrefix = prefixList.get(i); - Set> reachableCommonPrefixSet = new HashSet>(); + // TODO + System.out.println("-add Value Flows From CalleeSubGlobalFlowGraph"); + addValueFlowsFromCalleeSubGlobalFlowGraph(md); + // subGlobalFlowGraph.writeGraph("_SUBGLOBAL"); - for (Iterator iterator2 = reachSet.iterator(); iterator2.hasNext();) { - FlowNode reachNode = (FlowNode) iterator2.next(); - if (reachNode.getCurrentDescTuple().startsWith(curPrefix)) { - reachableCommonPrefixSet.add(reachNode.getCurrentDescTuple()); - } - } + // System.out.println("-propagate Flows From Callees With No CompositeLocation"); + // propagateFlowsFromCalleesWithNoCompositeLocation(md); - 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; - } + // mark if a parameter has incoming flows + checkParamNodesInSubGlobalFlowGraph(md); - } } - } - } - 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) { + private void checkParamNodesInSubGlobalFlowGraph(MethodDescriptor md) { + GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md); + FlowGraph flowGraph = getFlowGraph(md); - 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); - } + Set paramFlowNodeSet = flowGraph.getParamFlowNodeSet(); + for (Iterator iterator = paramFlowNodeSet.iterator(); iterator.hasNext();) { + FlowNode paramFlowNode = (FlowNode) iterator.next(); + System.out.println("paramFlowNode=" + paramFlowNode); + NTuple paramDescTuple = paramFlowNode.getDescTuple(); + NTuple paramLocTuple = translateToLocTuple(md, paramDescTuple); + GlobalFlowNode paramGlobalNode = globalFlowGraph.getFlowNode(paramLocTuple); - for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) { - MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next(); - propagateFlowsToCallerWithNoCompositeLocation(min, mdCaller, possibleMdCallee); - } + Set incomingNodeSet = + globalFlowGraph.getIncomingNodeSetByPrefix(paramLocTuple.get(0)); + if (incomingNodeSet.size() > 0) { + paramGlobalNode.setParamNodeWithIncomingFlows(true); } + } + } + private Set getMethodInvokeNodeSet(MethodDescriptor md) { + if (!mapMethodDescriptorToMethodInvokeNodeSet.containsKey(md)) { + mapMethodDescriptorToMethodInvokeNodeSet.put(md, new HashSet()); + } + return mapMethodDescriptorToMethodInvokeNodeSet.get(md); } - private void propagateFlowsFromCallees(MethodDescriptor mdCaller) { + 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 @@ -3603,7 +4153,7 @@ public class LocationInference { for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) { MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next(); - propagateFlowsToCaller(min, mdCaller, possibleMdCallee); + propagateFlowsToCallerWithNoCompositeLocation(min, mdCaller, possibleMdCallee); } } @@ -3686,9 +4236,12 @@ public class LocationInference { newImplicitTupleSet.addTupleSet(implicitFlowTupleSet); newImplicitTupleSet.addTupleSet(condTupleNode); - if (newImplicitTupleSet.size() > 1) { - // need to create an intermediate node for the GLB of conditional locations & implicit flows - NTuple interTuple = getFlowGraph(md).createIntermediateNode(md).getDescTuple(); + if (needToGenerateInterLoc(newImplicitTupleSet)) { + // need to create an intermediate node for the GLB of conditional + // locations & implicit flows + System.out.println("10"); + + NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); for (Iterator> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) { NTuple tuple = idxIter.next(); addFlowGraphEdge(md, tuple, interTuple); @@ -3712,6 +4265,7 @@ public class LocationInference { private void analyzeFlowReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode rn, NodeTupleSet implicitFlowTupleSet) { + // System.out.println("-analyzeFlowReturnNode=" + rn.printNode(0)); ExpressionNode returnExp = rn.getReturnExpression(); if (returnExp != null) { @@ -3721,16 +4275,21 @@ public class LocationInference { FlowGraph fg = getFlowGraph(md); // if (implicitFlowTupleSet.size() == 1 - // && fg.getFlowNode(implicitFlowTupleSet.iterator().next()).isIntermediate()) { + // && + // fg.getFlowNode(implicitFlowTupleSet.iterator().next()).isIntermediate()) + // { // - // // since there is already an intermediate node for the GLB of implicit flows + // // since there is already an intermediate node for the GLB of implicit + // flows // // we don't need to create another intermediate node. // // just re-use the intermediate node for implicit flows. // - // FlowNode meetNode = fg.getFlowNode(implicitFlowTupleSet.iterator().next()); + // FlowNode meetNode = + // fg.getFlowNode(implicitFlowTupleSet.iterator().next()); // // for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { - // NTuple returnNodeTuple = (NTuple) iterator.next(); + // NTuple returnNodeTuple = (NTuple) + // iterator.next(); // fg.addValueFlowEdge(returnNodeTuple, meetNode.getDescTuple()); // } // @@ -3744,22 +4303,56 @@ public class LocationInference { // add tuples corresponding to the current implicit flows currentFlowTupleSet.addTupleSet(implicitFlowTupleSet); - if (currentFlowTupleSet.size() > 1) { - FlowNode meetNode = fg.createIntermediateNode(md); + // System.out.println("---currentFlowTupleSet=" + currentFlowTupleSet); + + if (needToGenerateInterLoc(currentFlowTupleSet)) { + System.out.println("9"); + + FlowNode meetNode = fg.createIntermediateNode(); for (Iterator iterator = currentFlowTupleSet.iterator(); iterator.hasNext();) { NTuple currentFlowTuple = (NTuple) iterator.next(); fg.addValueFlowEdge(currentFlowTuple, meetNode.getDescTuple()); } fg.addReturnFlowNode(meetNode.getDescTuple()); - } else if (currentFlowTupleSet.size() == 1) { - NTuple tuple = currentFlowTupleSet.iterator().next(); - fg.addReturnFlowNode(tuple); + } else { + // currentFlowTupleSet = removeLiteralTuple(currentFlowTupleSet); + for (Iterator iterator = currentFlowTupleSet.iterator(); iterator.hasNext();) { + NTuple currentFlowTuple = (NTuple) iterator.next(); + fg.addReturnFlowNode(currentFlowTuple); + } } } } + private NodeTupleSet removeLiteralTuple(NodeTupleSet inSet) { + NodeTupleSet tupleSet = new NodeTupleSet(); + for (Iterator> iter = inSet.iterator(); iter.hasNext();) { + NTuple tuple = iter.next(); + if (!tuple.get(0).equals(LITERALDESC)) { + tupleSet.addTuple(tuple); + } + } + return tupleSet; + } + + private boolean needToGenerateInterLoc(NodeTupleSet tupleSet) { + int size = 0; + for (Iterator> iter = tupleSet.iterator(); iter.hasNext();) { + NTuple descTuple = iter.next(); + if (!descTuple.get(0).equals(LITERALDESC)) { + size++; + } + } + if (size > 1) { + System.out.println("needToGenerateInterLoc=" + tupleSet + " size=" + size); + return true; + } else { + return false; + } + } + private void analyzeFlowLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln, NodeTupleSet implicitFlowTupleSet) { @@ -3774,9 +4367,15 @@ public class LocationInference { newImplicitTupleSet.addTupleSet(implicitFlowTupleSet); newImplicitTupleSet.addTupleSet(condTupleNode); - if (newImplicitTupleSet.size() > 1) { - // need to create an intermediate node for the GLB of conditional locations & implicit flows - NTuple interTuple = getFlowGraph(md).createIntermediateNode(md).getDescTuple(); + newImplicitTupleSet.addGlobalFlowTupleSet(implicitFlowTupleSet.getGlobalLocTupleSet()); + newImplicitTupleSet.addGlobalFlowTupleSet(condTupleNode.getGlobalLocTupleSet()); + + if (needToGenerateInterLoc(newImplicitTupleSet)) { + // need to create an intermediate node for the GLB of conditional + // locations & implicit flows + System.out.println("6"); + + NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); for (Iterator> idxIter = newImplicitTupleSet.iterator(); idxIter .hasNext();) { NTuple tuple = idxIter.next(); @@ -3789,14 +4388,17 @@ public class LocationInference { // /////////// // System.out.println("condTupleNode="+condTupleNode); - // NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); + // NTuple interTuple = + // getFlowGraph(md).createIntermediateNode().getDescTuple(); // - // for (Iterator> idxIter = condTupleNode.iterator(); idxIter.hasNext();) { + // for (Iterator> idxIter = condTupleNode.iterator(); + // idxIter.hasNext();) { // NTuple tuple = idxIter.next(); // addFlowGraphEdge(md, tuple, interTuple); // } - // for (Iterator> idxIter = implicitFlowTupleSet.iterator(); idxIter + // for (Iterator> idxIter = + // implicitFlowTupleSet.iterator(); idxIter // .hasNext();) { // NTuple tuple = idxIter.next(); // addFlowGraphEdge(md, tuple, interTuple); @@ -3825,24 +4427,44 @@ public class LocationInference { analyzeFlowExpressionNode(md, bn.getVarTable(), ln.getCondition(), condTupleNode, null, implicitFlowTupleSet, false); - // /////////// - NTuple interTuple = getFlowGraph(md).createIntermediateNode(md).getDescTuple(); + NodeTupleSet newImplicitTupleSet = new NodeTupleSet(); + newImplicitTupleSet.addTupleSet(implicitFlowTupleSet); + newImplicitTupleSet.addTupleSet(condTupleNode); - for (Iterator> idxIter = condTupleNode.iterator(); idxIter.hasNext();) { - NTuple tuple = idxIter.next(); - addFlowGraphEdge(md, tuple, interTuple); - } + if (needToGenerateInterLoc(newImplicitTupleSet)) { + // need to create an intermediate node for the GLB of conditional + // locations & implicit flows + System.out.println("7"); + + NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); + for (Iterator> idxIter = newImplicitTupleSet.iterator(); idxIter + .hasNext();) { + NTuple tuple = idxIter.next(); + addFlowGraphEdge(md, tuple, interTuple); + } + newImplicitTupleSet.clear(); + newImplicitTupleSet.addTuple(interTuple); - for (Iterator> idxIter = implicitFlowTupleSet.iterator(); idxIter - .hasNext();) { - NTuple tuple = idxIter.next(); - addFlowGraphEdge(md, tuple, interTuple); } - NodeTupleSet newImplicitSet = new NodeTupleSet(); - newImplicitSet.addTuple(interTuple); - analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(), newImplicitSet); - analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(), newImplicitSet); + // /////////// + // NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); + // + // for (Iterator> idxIter = condTupleNode.iterator(); idxIter.hasNext();) { + // NTuple tuple = idxIter.next(); + // addFlowGraphEdge(md, tuple, interTuple); + // } + // + // for (Iterator> idxIter = implicitFlowTupleSet.iterator(); idxIter + // .hasNext();) { + // NTuple tuple = idxIter.next(); + // addFlowGraphEdge(md, tuple, interTuple); + // } + // + // NodeTupleSet newImplicitSet = new NodeTupleSet(); + // newImplicitSet.addTuple(interTuple); + analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(), newImplicitTupleSet); + analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(), newImplicitTupleSet); // /////////// // condTupleNode.addTupleSet(implicitFlowTupleSet); @@ -3859,7 +4481,7 @@ public class LocationInference { private void analyzeFlowIfStatementNode(MethodDescriptor md, SymbolTable nametable, IfStatementNode isn, NodeTupleSet implicitFlowTupleSet) { - System.out.println("analyzeFlowIfStatementNode=" + isn.printNode(0)); + // System.out.println("analyzeFlowIfStatementNode=" + isn.printNode(0)); NodeTupleSet condTupleNode = new NodeTupleSet(); analyzeFlowExpressionNode(md, nametable, isn.getCondition(), condTupleNode, null, @@ -3870,14 +4492,16 @@ public class LocationInference { newImplicitTupleSet.addTupleSet(implicitFlowTupleSet); newImplicitTupleSet.addTupleSet(condTupleNode); - System.out.println("condTupleNode=" + condTupleNode); - System.out.println("implicitFlowTupleSet=" + implicitFlowTupleSet); - System.out.println("newImplicitTupleSet=" + newImplicitTupleSet); + // System.out.println("$$$GGGcondTupleNode=" + condTupleNode.getGlobalLocTupleSet()); + // System.out.println("-condTupleNode=" + condTupleNode); + // System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet); + // System.out.println("-newImplicitTupleSet=" + newImplicitTupleSet); - if (newImplicitTupleSet.size() > 1) { + if (needToGenerateInterLoc(newImplicitTupleSet)) { + System.out.println("5"); // need to create an intermediate node for the GLB of conditional locations & implicit flows - NTuple interTuple = getFlowGraph(md).createIntermediateNode(md).getDescTuple(); + NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); for (Iterator> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) { NTuple tuple = idxIter.next(); addFlowGraphEdge(md, tuple, interTuple); @@ -3886,6 +4510,18 @@ public class LocationInference { newImplicitTupleSet.addTuple(interTuple); } + // GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md); + // for (Iterator> iterator = condTupleNode.globalIterator(); + // iterator.hasNext();) { + // NTuple calleeReturnLocTuple = iterator.next(); + // for (Iterator> iter2 = newImplicitTupleSet.iterator(); iter2.hasNext();) { + // NTuple callerImplicitTuple = iter2.next(); + // globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, + // translateToLocTuple(md, callerImplicitTuple)); + // } + // } + newImplicitTupleSet.addGlobalFlowTupleSet(condTupleNode.getGlobalLocTupleSet()); + analyzeFlowBlockNode(md, nametable, isn.getTrueBlock(), newImplicitTupleSet); if (isn.getFalseBlock() != null) { @@ -3912,12 +4548,15 @@ public class LocationInference { // creates edges from RHS to LHS NTuple interTuple = null; - if (nodeSetRHS.size() > 1) { - interTuple = getFlowGraph(md).createIntermediateNode(md).getDescTuple(); + if (needToGenerateInterLoc(nodeSetRHS)) { + System.out.println("3"); + interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); } for (Iterator> iter = nodeSetRHS.iterator(); iter.hasNext();) { NTuple fromTuple = iter.next(); + System.out.println("fromTuple=" + fromTuple + " interTuple=" + interTuple + " tupleLSH=" + + tupleLHS); addFlowGraphEdge(md, fromTuple, interTuple, tupleLHS); } @@ -3927,6 +4566,12 @@ public class LocationInference { addFlowGraphEdge(md, implicitTuple, tupleLHS); } + GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md); + for (Iterator> iterator = nodeSetRHS.globalIterator(); iterator.hasNext();) { + NTuple calleeReturnLocTuple = iterator.next(); + globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, translateToLocTuple(md, tupleLHS)); + } + } } @@ -3949,9 +4594,7 @@ public class LocationInference { // note that expression node can create more than one flow node // nodeSet contains of flow nodes // base is always assigned to null except the case of a name node! - NTuple flowTuple; - switch (en.kind()) { case Kind.AssignmentNode: @@ -3990,7 +4633,7 @@ public class LocationInference { break; case Kind.LiteralNode: - analyzeLiteralNode(md, nametable, (LiteralNode) en); + analyzeFlowLiteralNode(md, nametable, (LiteralNode) en, nodeSet); break; case Kind.MethodInvokeNode: @@ -4023,6 +4666,7 @@ public class LocationInference { // return null; } + return null; } @@ -4038,20 +4682,48 @@ public class LocationInference { private void analyzeFlowTertiaryNode(MethodDescriptor md, SymbolTable nametable, TertiaryNode tn, NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) { + System.out.println("analyzeFlowTertiaryNode=" + tn.printNode(0)); + NodeTupleSet tertiaryTupleNode = new NodeTupleSet(); analyzeFlowExpressionNode(md, nametable, tn.getCond(), tertiaryTupleNode, null, implicitFlowTupleSet, false); + NodeTupleSet newImplicitTupleSet = new NodeTupleSet(); + newImplicitTupleSet.addTupleSet(implicitFlowTupleSet); + newImplicitTupleSet.addTupleSet(tertiaryTupleNode); + + // System.out.println("$$$GGGcondTupleNode=" + tertiaryTupleNode.getGlobalLocTupleSet()); + // System.out.println("-tertiaryTupleNode=" + tertiaryTupleNode); + // System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet); + // System.out.println("-newImplicitTupleSet=" + newImplicitTupleSet); + + if (needToGenerateInterLoc(newImplicitTupleSet)) { + System.out.println("15"); + // need to create an intermediate node for the GLB of conditional locations & implicit flows + NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); + for (Iterator> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) { + NTuple tuple = idxIter.next(); + addFlowGraphEdge(md, tuple, interTuple); + } + newImplicitTupleSet.clear(); + newImplicitTupleSet.addTuple(interTuple); + } + + newImplicitTupleSet.addGlobalFlowTupleSet(tertiaryTupleNode.getGlobalLocTupleSet()); + + System.out.println("---------newImplicitTupleSet=" + newImplicitTupleSet); // add edges from tertiaryTupleNode to all nodes of conditional nodes - tertiaryTupleNode.addTupleSet(implicitFlowTupleSet); + // tertiaryTupleNode.addTupleSet(implicitFlowTupleSet); analyzeFlowExpressionNode(md, nametable, tn.getTrueExpr(), tertiaryTupleNode, null, - implicitFlowTupleSet, false); + newImplicitTupleSet, false); analyzeFlowExpressionNode(md, nametable, tn.getFalseExpr(), tertiaryTupleNode, null, - implicitFlowTupleSet, false); + newImplicitTupleSet, false); + nodeSet.addGlobalFlowTupleSet(tertiaryTupleNode.getGlobalLocTupleSet()); nodeSet.addTupleSet(tertiaryTupleNode); + System.out.println("#tertiary node set=" + nodeSet); } private void addMapCallerMethodDescToMethodInvokeNodeSet(MethodDescriptor caller, @@ -4073,17 +4745,48 @@ public class LocationInference { } private Set getParamNodeFlowingToReturnValue(MethodDescriptor md) { + + if (!mapMethodDescToParamNodeFlowsToReturnValue.containsKey(md)) { + mapMethodDescToParamNodeFlowsToReturnValue.put(md, new HashSet()); + } + return mapMethodDescToParamNodeFlowsToReturnValue.get(md); } - private void analyzeFlowMethodInvokeNode(MethodDescriptor md, SymbolTable nametable, + private Set> getPCLocTupleSet(MethodInvokeNode min) { + if (!mapMethodInvokeNodeToPCLocTupleSet.containsKey(min)) { + mapMethodInvokeNodeToPCLocTupleSet.put(min, new HashSet>()); + } + return mapMethodInvokeNodeToPCLocTupleSet.get(min); + } + + private void analyzeFlowMethodInvokeNode(MethodDescriptor mdCaller, SymbolTable nametable, MethodInvokeNode min, NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) { + System.out.println("analyzeFlowMethodInvokeNode=" + min.printNode(0)); + + if (!toanalyze_methodDescList.contains(min.getMethod())) { + return; + } + + addMapMethodDescToMethodInvokeNodeSet(min); + + Set> pcLocTupleSet = getPCLocTupleSet(min); + for (Iterator iterator = implicitFlowTupleSet.iterator(); iterator.hasNext();) { + NTuple pcDescTuple = (NTuple) iterator.next(); + if (!pcDescTuple.get(0).equals(LITERALDESC)) { + // here we don't need to add the literal value as a PC location + pcLocTupleSet.add(translateToLocTuple(mdCaller, pcDescTuple)); + } + } + + mapMethodInvokeNodeToArgIdxMap.put(min, new HashMap>()); + if (nodeSet == null) { nodeSet = new NodeTupleSet(); } - MethodDescriptor calleeMethodDesc = min.getMethod(); + MethodDescriptor mdCallee = min.getMethod(); NameDescriptor baseName = min.getBaseName(); boolean isSystemout = false; @@ -4091,20 +4794,23 @@ public class LocationInference { isSystemout = baseName.getSymbol().equals("System.out"); } - if (!ssjava.isSSJavaUtil(calleeMethodDesc.getClassDesc()) - && !ssjava.isTrustMethod(calleeMethodDesc) && !isSystemout) { + if (!ssjava.isSSJavaUtil(mdCallee.getClassDesc()) && !ssjava.isTrustMethod(mdCallee) + && !isSystemout) { - addMapCallerMethodDescToMethodInvokeNodeSet(md, min); + addMapCallerMethodDescToMethodInvokeNodeSet(mdCaller, min); - FlowGraph calleeFlowGraph = getFlowGraph(calleeMethodDesc); + FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); + System.out.println("mdCallee=" + mdCallee); Set calleeReturnSet = calleeFlowGraph.getReturnNodeSet(); - System.out.println("#calleeReturnSet=" + calleeReturnSet); + System.out.println("---calleeReturnSet=" + calleeReturnSet); + + NodeTupleSet tupleSet = new NodeTupleSet(); if (min.getExpression() != null) { NodeTupleSet baseNodeSet = new NodeTupleSet(); - analyzeFlowExpressionNode(md, nametable, min.getExpression(), baseNodeSet, null, + analyzeFlowExpressionNode(mdCaller, nametable, min.getExpression(), baseNodeSet, null, implicitFlowTupleSet, false); assert (baseNodeSet.size() == 1); @@ -4117,19 +4823,23 @@ public class LocationInference { for (Iterator iterator = calleeReturnSet.iterator(); iterator.hasNext();) { FlowNode returnNode = (FlowNode) iterator.next(); NTuple returnDescTuple = returnNode.getDescTuple(); - if (returnDescTuple.startsWith(calleeMethodDesc.getThis())) { + if (returnDescTuple.startsWith(mdCallee.getThis())) { // the location type of the return value is started with 'this' // reference NTuple inFlowTuple = new NTuple(baseTuple.getList()); inFlowTuple.addAll(returnDescTuple.subList(1, returnDescTuple.size())); - nodeSet.addTuple(inFlowTuple); + // nodeSet.addTuple(inFlowTuple); + tupleSet.addTuple(inFlowTuple); } else { // TODO Set inFlowSet = calleeFlowGraph.getIncomingFlowNodeSet(returnNode); + // System.out.println("inFlowSet=" + inFlowSet + " from retrunNode=" + returnNode); for (Iterator iterator2 = inFlowSet.iterator(); iterator2.hasNext();) { FlowNode inFlowNode = (FlowNode) iterator2.next(); - if (inFlowNode.getDescTuple().startsWith(calleeMethodDesc.getThis())) { - nodeSet.addTupleSet(baseNodeSet); + if (inFlowNode.getDescTuple().startsWith(mdCallee.getThis())) { + // nodeSet.addTupleSet(baseNodeSet); + tupleSet.addTupleSet(baseNodeSet); + } } } @@ -4137,7 +4847,6 @@ public class LocationInference { } } - // analyze parameter flows if (min.numArgs() > 0) { @@ -4153,42 +4862,131 @@ public class LocationInference { ExpressionNode en = min.getArg(i); int idx = i + offset; NodeTupleSet argTupleSet = new NodeTupleSet(); - analyzeFlowExpressionNode(md, nametable, en, argTupleSet, false); - // if argument is liternal node, argTuple is set to NULL. - - NTuple argTuple = new NTuple(); - if (argTupleSet.size() > 1) { - NTuple interTuple = - getFlowGraph(md).createIntermediateNode(md).getDescTuple(); - for (Iterator> idxIter = argTupleSet.iterator(); idxIter.hasNext();) { - NTuple tuple = idxIter.next(); - addFlowGraphEdge(md, tuple, interTuple); - } - argTuple = interTuple; - } else { - argTuple = argTupleSet.iterator().next(); + analyzeFlowExpressionNode(mdCaller, nametable, en, argTupleSet, false); + // if argument is liternal node, argTuple is set to NULL + System.out.println("argTupleSet=" + argTupleSet); + NTuple argTuple = generateArgTuple(mdCaller, argTupleSet); + + // if an argument is literal value, + // we need to create an itermediate node so that we could assign a composite location to + // that node if needed + if (argTuple.size() > 0 + && (argTuple.get(0).equals(GLOBALDESC) || argTuple.get(0).equals(LITERALDESC))) { + /* + * System.out.println("***GLOBAL ARG TUPLE CASE=" + argTuple); System.out.println("8"); + * + * NTuple interTuple = + * getFlowGraph(mdCaller).createIntermediateNode().getDescTuple(); ((InterDescriptor) + * interTuple.get(0)).setMethodArgIdxPair(min, idx); addFlowGraphEdge(mdCaller, + * argTuple, interTuple); argTuple = interTuple; addArgIdxMap(min, idx, argTuple); + * System.out.println("new min mapping i=" + idx + " ->" + argTuple); + */ + argTuple = new NTuple(); } addArgIdxMap(min, idx, argTuple); + FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx); + + // check whether a param node in the callee graph has incoming flows + // if it has incoming flows, the corresponding arg should be lower than the current PC + // Descriptor prefix = paramNode.getDescTuple().get(0); + // if (calleeFlowGraph.getIncomingNodeSetByPrefix(prefix).size() > 0) { + // for (Iterator> iterator = implicitFlowTupleSet.iterator(); iterator + // .hasNext();) { + // NTuple pcTuple = iterator.next(); + // System.out.println("add edge pcTuple =" + pcTuple + " -> " + argTuple); + // addFlowGraphEdge(md, pcTuple, argTuple); + // } + // } + + System.out.println("paramNode=" + paramNode + " calleeReturnSet=" + calleeReturnSet); if (hasInFlowTo(calleeFlowGraph, paramNode, calleeReturnSet) - || calleeMethodDesc.getModifiers().isNative()) { - addParamNodeFlowingToReturnValue(calleeMethodDesc, paramNode); - nodeSet.addTupleSet(argTupleSet); + || mdCallee.getModifiers().isNative()) { + addParamNodeFlowingToReturnValue(mdCallee, paramNode); + // nodeSet.addTupleSet(argTupleSet); + tupleSet.addTupleSet(argTupleSet); } } } + if (mdCallee.getReturnType() != null && !mdCallee.getReturnType().isVoid()) { + FlowReturnNode setNode = getFlowGraph(mdCaller).createReturnNode(min); + System.out.println("ADD TUPLESET=" + tupleSet + " to returnnode=" + setNode); + setNode.addTupleSet(tupleSet); + nodeSet.addTuple(setNode.getDescTuple()); + } + // propagateFlowsFromCallee(min, md, min.getMethod()); + // 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 = + translateToLocTuple(mdCallee, calleeReturnNode.getDescTuple()); + System.out.println("calleeReturnLocTuple=" + calleeReturnLocTuple); + nodeSet.addGlobalFlowTuple(translateToCallerLocTuple(min, mdCallee, mdCaller, + calleeReturnLocTuple)); + } + + System.out.println("min nodeSet=" + nodeSet); + + } + + } + + private NTuple generateArgTuple(MethodDescriptor mdCaller, NodeTupleSet argTupleSet) { + + int size = 0; + + // if argTupleSet is empty, it comes from the top location + if (argTupleSet.size() == 0) { + NTuple descTuple = new NTuple(); + descTuple.add(LITERALDESC); + return descTuple; + } + + Set> argTupleSetNonLiteral = new HashSet>(); + + for (Iterator> iter = argTupleSet.iterator(); iter.hasNext();) { + NTuple descTuple = iter.next(); + if (!descTuple.get(0).equals(LITERALDESC)) { + argTupleSetNonLiteral.add(descTuple); + } + } + + if (argTupleSetNonLiteral.size() > 1) { + System.out.println("11"); + + NTuple interTuple = + getFlowGraph(mdCaller).createIntermediateNode().getDescTuple(); + for (Iterator> idxIter = argTupleSet.iterator(); idxIter.hasNext();) { + NTuple tuple = idxIter.next(); + addFlowGraphEdge(mdCaller, tuple, interTuple); + } + return interTuple; + } else if (argTupleSetNonLiteral.size() == 1) { + return argTupleSetNonLiteral.iterator().next(); + } else { + return argTupleSet.iterator().next(); } } private boolean hasInFlowTo(FlowGraph fg, FlowNode inNode, Set nodeSet) { // return true if inNode has in-flows to nodeSet - Set reachableSet = fg.getReachFlowNodeSetFrom(inNode); + + if (nodeSet.contains(inNode)) { + // in this case, the method directly returns a parameter variable. + return true; + } + // Set reachableSet = fg.getReachFlowNodeSetFrom(inNode); + Set reachableSet = fg.getReachableSetFrom(inNode.getDescTuple()); + System.out.println("inNode=" + inNode + " reachalbeSet=" + reachableSet); + for (Iterator iterator = reachableSet.iterator(); iterator.hasNext();) { FlowNode fn = (FlowNode) iterator.next(); if (nodeSet.contains(fn)) { @@ -4214,13 +5012,20 @@ public class LocationInference { mapIdxToTuple.put(new Integer(idx), argTuple); } - private void analyzeLiteralNode(MethodDescriptor md, SymbolTable nametable, LiteralNode en) { - + private void analyzeFlowLiteralNode(MethodDescriptor md, SymbolTable nametable, LiteralNode en, + NodeTupleSet nodeSet) { + NTuple tuple = new NTuple(); + tuple.add(LITERALDESC); + nodeSet.addTuple(tuple); } private void analyzeFlowArrayAccessNode(MethodDescriptor md, SymbolTable nametable, ArrayAccessNode aan, NodeTupleSet nodeSet, boolean isLHS) { + // System.out.println("analyzeFlowArrayAccessNode aan=" + aan.printNode(0)); + String currentArrayAccessNodeExpStr = aan.printNode(0); + arrayAccessNodeStack.push(aan.printNode(0)); + NodeTupleSet expNodeTupleSet = new NodeTupleSet(); NTuple base = analyzeFlowExpressionNode(md, nametable, aan.getExpression(), expNodeTupleSet, isLHS); @@ -4228,6 +5033,8 @@ public class LocationInference { NodeTupleSet idxNodeTupleSet = new NodeTupleSet(); analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, isLHS); + arrayAccessNodeStack.pop(); + if (isLHS) { // need to create an edge from idx to array for (Iterator> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) { @@ -4238,11 +5045,45 @@ public class LocationInference { } } + GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md); + for (Iterator> iterator = idxNodeTupleSet.globalIterator(); iterator + .hasNext();) { + NTuple calleeReturnLocTuple = iterator.next(); + for (Iterator> arrIter = expNodeTupleSet.iterator(); arrIter.hasNext();) { + NTuple arrTuple = arrIter.next(); + globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, translateToLocTuple(md, arrTuple)); + } + } + nodeSet.addTupleSet(expNodeTupleSet); } else { - nodeSet.addTupleSet(expNodeTupleSet); - nodeSet.addTupleSet(idxNodeTupleSet); + + NodeTupleSet nodeSetArrayAccessExp = new NodeTupleSet(); + + nodeSetArrayAccessExp.addTupleSet(expNodeTupleSet); + nodeSetArrayAccessExp.addTupleSet(idxNodeTupleSet); + + if (arrayAccessNodeStack.isEmpty() + || !arrayAccessNodeStack.peek().startsWith(currentArrayAccessNodeExpStr)) { + + if (needToGenerateInterLoc(nodeSetArrayAccessExp)) { + System.out.println("1"); + NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); + + for (Iterator> iter = nodeSetArrayAccessExp.iterator(); iter.hasNext();) { + NTuple higherTuple = iter.next(); + addFlowGraphEdge(md, higherTuple, interTuple); + } + nodeSetArrayAccessExp.clear(); + nodeSetArrayAccessExp.addTuple(interTuple); + } + } + + nodeSet.addGlobalFlowTupleSet(idxNodeTupleSet.getGlobalLocTupleSet()); + nodeSet.addTupleSet(nodeSetArrayAccessExp); + } + } private void analyzeCreateObjectNode(MethodDescriptor md, SymbolTable nametable, @@ -4303,6 +5144,10 @@ public class LocationInference { // there are two operands nodeSet.addTupleSet(leftOpSet); nodeSet.addTupleSet(rightOpSet); + + nodeSet.addGlobalFlowTupleSet(leftOpSet.getGlobalLocTupleSet()); + nodeSet.addGlobalFlowTupleSet(rightOpSet.getGlobalLocTupleSet()); + break; default: @@ -4314,8 +5159,6 @@ public class LocationInference { private NTuple analyzeFlowNameNode(MethodDescriptor md, SymbolTable nametable, NameNode nn, NodeTupleSet nodeSet, NTuple base, NodeTupleSet implicitFlowTupleSet) { - // System.out.println("analyzeFlowNameNode=" + nn.printNode(0)); - if (base == null) { base = new NTuple(); } @@ -4396,10 +5239,13 @@ public class LocationInference { private NTuple analyzeFlowFieldAccessNode(MethodDescriptor md, SymbolTable nametable, FieldAccessNode fan, NodeTupleSet nodeSet, NTuple base, NodeTupleSet implicitFlowTupleSet, boolean isLHS) { + // System.out.println("analyzeFlowFieldAccessNode=" + fan.printNode(0)); + String currentArrayAccessNodeExpStr = null; ExpressionNode left = fan.getExpression(); TypeDescriptor ltd = left.getType(); FieldDescriptor fd = fan.getField(); + ArrayAccessNode aan = null; String varName = null; if (left.kind() == Kind.NameNode) { @@ -4416,14 +5262,19 @@ public class LocationInference { NodeTupleSet idxNodeTupleSet = new NodeTupleSet(); + boolean isArrayCase = false; if (left instanceof ArrayAccessNode) { - ArrayAccessNode aan = (ArrayAccessNode) left; + isArrayCase = true; + aan = (ArrayAccessNode) left; + + currentArrayAccessNodeExpStr = aan.printNode(0); + arrayAccessNodeStack.push(currentArrayAccessNodeExpStr); + left = aan.getExpression(); analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, base, implicitFlowTupleSet, isLHS); - nodeSet.addTupleSet(idxNodeTupleSet); } base = analyzeFlowExpressionNode(md, nametable, left, nodeSet, base, implicitFlowTupleSet, isLHS); @@ -4436,13 +5287,11 @@ public class LocationInference { NTuple flowFieldTuple = new NTuple(base.toList()); if (!left.getType().isPrimitive()) { - if (!fd.getSymbol().equals("length")) { // array.length access, just have the location of the array flowFieldTuple.add(fd); nodeSet.removeTuple(base); } - } getFlowGraph(md).createNewFlowNode(flowFieldTuple); @@ -4451,9 +5300,55 @@ public class LocationInference { NTuple idxTuple = idxIter.next(); getFlowGraph(md).addValueFlowEdge(idxTuple, flowFieldTuple); } + + GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md); + for (Iterator> iterator = idxNodeTupleSet.globalIterator(); iterator + .hasNext();) { + NTuple calleeReturnLocTuple = iterator.next(); + globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, + translateToLocTuple(md, flowFieldTuple)); + } + + } else { + nodeSet.addTupleSet(idxNodeTupleSet); + + // if it is the array case and not the LHS case + if (isArrayCase) { + arrayAccessNodeStack.pop(); + + if (arrayAccessNodeStack.isEmpty() + || !arrayAccessNodeStack.peek().startsWith(currentArrayAccessNodeExpStr)) { + NodeTupleSet nodeSetArrayAccessExp = new NodeTupleSet(); + + nodeSetArrayAccessExp.addTuple(flowFieldTuple); + nodeSetArrayAccessExp.addTupleSet(idxNodeTupleSet); + nodeSetArrayAccessExp.addTupleSet(nodeSet); + + if (needToGenerateInterLoc(nodeSetArrayAccessExp)) { + System.out.println("4"); + System.out.println("nodeSetArrayAccessExp=" + nodeSetArrayAccessExp); + // System.out.println("idxNodeTupleSet.getGlobalLocTupleSet()=" + // + idxNodeTupleSet.getGlobalLocTupleSet()); + + NTuple interTuple = + getFlowGraph(md).createIntermediateNode().getDescTuple(); + + for (Iterator> iter = nodeSetArrayAccessExp.iterator(); iter + .hasNext();) { + NTuple higherTuple = iter.next(); + addFlowGraphEdge(md, higherTuple, interTuple); + } + nodeSet.clear(); + flowFieldTuple = interTuple; + } + + nodeSet.addGlobalFlowTupleSet(idxNodeTupleSet.getGlobalLocTupleSet()); + } + + } + } return flowFieldTuple; - } } @@ -4487,10 +5382,10 @@ 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("-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) { @@ -4507,8 +5402,9 @@ public class LocationInference { // creates edges from RHS to LHS NTuple interTuple = null; - if (nodeSetRHS.size() > 1) { - interTuple = getFlowGraph(md).createIntermediateNode(md).getDescTuple(); + if (needToGenerateInterLoc(nodeSetRHS)) { + System.out.println("2"); + interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); } for (Iterator> iter = nodeSetRHS.iterator(); iter.hasNext();) { @@ -4528,6 +5424,31 @@ public class LocationInference { } } + // create global flow edges if the callee gives return value flows to the caller + GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md); + for (Iterator> iterator = nodeSetRHS.globalIterator(); iterator.hasNext();) { + NTuple calleeReturnLocTuple = iterator.next(); + for (Iterator> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) { + NTuple callerLHSTuple = iter2.next(); + globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, + translateToLocTuple(md, callerLHSTuple)); + System.out.println("$$$ GLOBAL FLOW ADD=" + calleeReturnLocTuple + " -> " + + translateToLocTuple(md, callerLHSTuple)); + } + } + + for (Iterator> iterator = implicitFlowTupleSet.globalIterator(); iterator + .hasNext();) { + NTuple calleeReturnLocTuple = iterator.next(); + for (Iterator> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) { + NTuple callerLHSTuple = iter2.next(); + globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, + translateToLocTuple(md, callerLHSTuple)); + System.out.println("$$$ GLOBAL FLOW PCLOC ADD=" + calleeReturnLocTuple + " -> " + + translateToLocTuple(md, callerLHSTuple)); + } + } + } else { // postinc case @@ -4545,10 +5466,24 @@ public class LocationInference { } } + GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md); + for (Iterator> iterator = implicitFlowTupleSet.globalIterator(); iterator + .hasNext();) { + NTuple calleeReturnLocTuple = iterator.next(); + for (Iterator> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) { + NTuple callerLHSTuple = iter2.next(); + globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, + translateToLocTuple(md, callerLHSTuple)); + System.out.println("$$$ GLOBAL FLOW PC ADD=" + calleeReturnLocTuple + " -> " + + translateToLocTuple(md, callerLHSTuple)); + } + } + } if (nodeSet != null) { nodeSet.addTupleSet(nodeSetLHS); + nodeSet.addGlobalFlowTupleSet(nodeSetLHS.getGlobalLocTupleSet()); } } @@ -4579,6 +5514,8 @@ public class LocationInference { public void writeInferredLatticeDotFile(ClassDescriptor cd, HierarchyGraph simpleHierarchyGraph, SSJavaLattice locOrder, String nameSuffix) { + System.out.println("@cd=" + cd); + System.out.println("@sharedLoc=" + locOrder.getSharedLocSet()); writeInferredLatticeDotFile(cd, null, simpleHierarchyGraph, locOrder, nameSuffix); } @@ -4588,7 +5525,7 @@ public class LocationInference { String fileName = "lattice_"; if (md != null) { fileName += - cd.getSymbol().replaceAll("[\\W_]", "") + "_" + md.toString().replaceAll("[\\W_]", ""); + /* cd.getSymbol().replaceAll("[\\W_]", "") + "_" + */md.toString().replaceAll("[\\W_]", ""); } else { fileName += cd.getSymbol().replaceAll("[\\W_]", ""); } @@ -4611,7 +5548,6 @@ public class LocationInference { String highLocId = pair.getFirst(); String lowLocId = pair.getSecond(); - if (!addedLocSet.contains(highLocId)) { addedLocSet.add(highLocId); drawNode(bw, locOrder, simpleHierarchyGraph, highLocId); @@ -4651,34 +5587,30 @@ public class LocationInference { 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); - } + // HNode node = graph.getHNode(locName); + // if (node != null && node.isMergeNode()) { + // Set mergeSet = graph.getMapHNodetoMergeSet().get(node); + // prettyStr += ":" + convertMergeSetToString(graph, mergeSet); + // } bw.write(locName + " [label=\"" + prettyStr + "\"]" + ";\n"); } - public void _debug_printGraph() { + public void _debug_writeFlowGraph() { Set keySet = mapMethodDescriptorToFlowGraph.keySet(); for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { MethodDescriptor md = (MethodDescriptor) iterator.next(); FlowGraph fg = mapMethodDescriptorToFlowGraph.get(md); + GlobalFlowGraph subGlobalFlowGraph = getSubGlobalFlowGraph(md); try { fg.writeGraph(); + subGlobalFlowGraph.writeGraph("_SUBGLOBAL"); } catch (IOException e) { e.printStackTrace(); } @@ -4694,8 +5626,18 @@ class CyclicFlowException extends Exception { class InterDescriptor extends Descriptor { + Pair minArgIdxPair; + public InterDescriptor(String name) { super(name); } + public void setMethodArgIdxPair(MethodInvokeNode min, int idx) { + minArgIdxPair = new Pair(min, new Integer(idx)); + } + + public Pair getMethodArgIdxPair() { + return minArgIdxPair; + } + }