X-Git-Url: http://plrg.eecs.uci.edu/git/?p=IRC.git;a=blobdiff_plain;f=Robust%2Fsrc%2FAnalysis%2FSSJava%2FLocationInference.java;h=0967c58b5986b90f2c47dadfa256bb0390bf1989;hp=31900f103f5e2216b7f8ccdf62bf4c33258606f6;hb=76263fb08dca40e3c50ec9403ff4ddd02c35bfe1;hpb=d421edc382984588192603ed519923beadeb4d3a diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index 31900f10..0967c58b 100644 --- a/Robust/src/Analysis/SSJava/LocationInference.java +++ b/Robust/src/Analysis/SSJava/LocationInference.java @@ -58,10 +58,12 @@ public class LocationInference { State state; SSJavaAnalysis ssjava; - List toanalyzeList; - List toanalyzeMethodList; + List temp_toanalyzeList; + List temp_toanalyzeMethodList; Map mapMethodDescriptorToFlowGraph; + LinkedList toanalyze_methodDescList; + // map a method descriptor to its set of parameter descriptors Map> mapMethodDescriptorToParamDescSet; @@ -85,14 +87,14 @@ public class LocationInference { // map a method/class descriptor to a skeleton hierarchy graph with combination nodes private Map mapDescriptorToCombineSkeletonHierarchyGraph; - // map a method descriptor to a method summary - private Map mapMethodDescToMethodSummary; + // map a descriptor to a simple lattice + private Map> mapDescriptorToSimpleLattice; // map a method descriptor to the set of method invocation nodes which are // invoked by the method descriptor private Map> mapMethodDescriptorToMethodInvokeNodeSet; - private Map> mapMethodInvokeNodeToArgIdxMap; + private Map>> mapMethodInvokeNodeToArgIdxMap; private Map> mapMethodInvokeNodeToBaseTuple; @@ -108,6 +110,14 @@ public class LocationInference { private Map mapDescToDefinitionLine; + private Map mapDescToLocationSummary; + + // maps a method descriptor to a sub global flow graph that captures all value flows caused by the + // set of callees reachable from the method + private Map mapMethodDescriptorToSubGlobalFlowGraph; + + private Map, NTuple>> mapMethodInvokeNodeToMapCallerArgToCalleeArg; + public static final String GLOBALLOC = "GLOBALLOC"; public static final String TOPLOC = "TOPLOC"; @@ -129,8 +139,8 @@ public class LocationInference { public LocationInference(SSJavaAnalysis ssjava, State state) { this.ssjava = ssjava; this.state = state; - this.toanalyzeList = new ArrayList(); - this.toanalyzeMethodList = new ArrayList(); + this.temp_toanalyzeList = new ArrayList(); + this.temp_toanalyzeMethodList = new ArrayList(); this.mapMethodDescriptorToFlowGraph = new HashMap(); this.cd2lattice = new HashMap>(); this.md2lattice = new HashMap>(); @@ -138,7 +148,7 @@ public class LocationInference { this.mapMethodDescriptorToMethodInvokeNodeSet = new HashMap>(); this.mapMethodInvokeNodeToArgIdxMap = - new HashMap>(); + new HashMap>>(); this.mapMethodDescToMethodLocationInfo = new HashMap(); this.mapMethodToCalleeSet = new HashMap>(); this.mapClassToLocationInfo = new HashMap(); @@ -149,19 +159,27 @@ public class LocationInference { new HashMap>(); this.mapDescriptorToHierarchyGraph = new HashMap(); - this.mapMethodDescToMethodSummary = new HashMap(); this.mapMethodInvokeNodeToBaseTuple = new HashMap>(); this.mapDescriptorToSkeletonHierarchyGraph = new HashMap(); this.mapDescriptorToCombineSkeletonHierarchyGraph = new HashMap(); this.mapDescriptorToSimpleHierarchyGraph = new HashMap(); + this.mapDescriptorToSimpleLattice = new HashMap>(); + + this.mapDescToLocationSummary = new HashMap(); + + this.mapMethodDescriptorToSubGlobalFlowGraph = new HashMap(); + + this.mapMethodInvokeNodeToMapCallerArgToCalleeArg = + new HashMap, NTuple>>(); + } public void setupToAnalyze() { SymbolTable classtable = state.getClassSymbolTable(); - toanalyzeList.clear(); - toanalyzeList.addAll(classtable.getValueSet()); + temp_toanalyzeList.clear(); + temp_toanalyzeList.addAll(classtable.getValueSet()); // Collections.sort(toanalyzeList, new Comparator() { // public int compare(ClassDescriptor o1, ClassDescriptor o2) { // return o1.getClassName().compareToIgnoreCase(o2.getClassName()); @@ -172,9 +190,9 @@ public class LocationInference { public void setupToAnalazeMethod(ClassDescriptor cd) { SymbolTable methodtable = cd.getMethodTable(); - toanalyzeMethodList.clear(); - toanalyzeMethodList.addAll(methodtable.getValueSet()); - Collections.sort(toanalyzeMethodList, new Comparator() { + temp_toanalyzeMethodList.clear(); + temp_toanalyzeMethodList.addAll(methodtable.getValueSet()); + Collections.sort(temp_toanalyzeMethodList, new Comparator() { public int compare(MethodDescriptor o1, MethodDescriptor o2) { return o1.getSymbol().compareToIgnoreCase(o2.getSymbol()); } @@ -182,19 +200,19 @@ public class LocationInference { } public boolean toAnalyzeMethodIsEmpty() { - return toanalyzeMethodList.isEmpty(); + return temp_toanalyzeMethodList.isEmpty(); } public boolean toAnalyzeIsEmpty() { - return toanalyzeList.isEmpty(); + return temp_toanalyzeList.isEmpty(); } public ClassDescriptor toAnalyzeNext() { - return toanalyzeList.remove(0); + return temp_toanalyzeList.remove(0); } public MethodDescriptor toAnalyzeMethodNext() { - return toanalyzeMethodList.remove(0); + return temp_toanalyzeMethodList.remove(0); } public void inference() { @@ -202,22 +220,40 @@ public class LocationInference { // 1) construct value flow graph constructFlowGraph(); + assignCompositeLocation(); + + // constructGlobalFlowGraph(); + + System.exit(0); + constructHierarchyGraph(); + debug_writeHierarchyDotFiles(); + simplifyHierarchyGraph(); + debug_writeSimpleHierarchyDotFiles(); + constructSkeletonHierarchyGraph(); + debug_writeSkeletonHierarchyDotFiles(); + insertCombinationNodes(); - debug_writeHierarchyDotFile(); + debug_writeSkeletonCombinationHierarchyDotFiles(); + + buildLattice(); + + debug_writeLattices(); + + generateMethodSummary(); System.exit(0); // 2) construct lattices inferLattices(); - simplifyLattices(); + // simplifyLattices(); // 3) check properties checkLattices(); @@ -232,13 +268,994 @@ public class LocationInference { } + public Map, NTuple> getMapCallerArgToCalleeParam( + MethodInvokeNode min) { + + if (!mapMethodInvokeNodeToMapCallerArgToCalleeArg.containsKey(min)) { + mapMethodInvokeNodeToMapCallerArgToCalleeArg.put(min, + new HashMap, NTuple>()); + } + + return mapMethodInvokeNodeToMapCallerArgToCalleeArg.get(min); + } + + public void addMapCallerArgToCalleeParam(MethodInvokeNode min, NTuple callerArg, + NTuple calleeParam) { + getMapCallerArgToCalleeParam(min).put(callerArg, calleeParam); + } + + private void assignCompositeLocation() { + calculateGlobalValueFlowCompositeLocation(); + translateCompositeLocationAssignmentToFlowGraph(); + _debug_printGraph(); + } + + private void translateCompositeLocationAssignmentToFlowGraph() { + + MethodDescriptor methodEventLoopDesc = ssjava.getMethodContainingSSJavaLoop(); + translateCompositeLocationAssignmentToFlowGraph(methodEventLoopDesc); + + } + + private void translateCompositeLocationAssignmentToFlowGraph(MethodDescriptor mdCaller) { + + System.out.println("\n#translateCompositeLocationAssignmentToFlowGraph=" + 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); + } + } + + Set minSet = mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller); + + 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'. + if (mapMethodInvokeNodeToBaseTuple.get(min) != null) { + // if mapMethodInvokeNodeToBaseTuple doesn't have a mapping + // it means that the corresponding callee method does not cause any + // flows + translateMapLocationToInferCompositeLocationToCalleeGraph(callerGlobalFlowGraph, min); + } + calleeSet.add(min.getMethod()); + } + + for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) { + MethodDescriptor callee = (MethodDescriptor) iterator.next(); + translateCompositeLocationAssignmentToFlowGraph(callee); + } + + } + + 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)) { + // 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 CompositeLocation generateCompositeLocation(NTuple nodeDescTuple, + CompositeLocation inferCompLoc) { + + System.out.println("generateCompositeLocation=" + nodeDescTuple + " with inferCompLoc=" + + inferCompLoc); + + CompositeLocation newCompLoc = new CompositeLocation(); + for (int i = 0; i < inferCompLoc.getSize(); i++) { + newCompLoc.addLocation(inferCompLoc.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 < nodeDescTuple.size(); i++) { + Descriptor desc = nodeDescTuple.get(i); + Location locElement = new Location(enclosingDescriptor, desc); + newCompLoc.addLocation(locElement); + + enclosingDescriptor = ((FieldDescriptor) desc).getClassDescriptor(); + } + + return newCompLoc; + } + + private void translateMapLocationToInferCompositeLocationToCalleeGraph( + GlobalFlowGraph callerGraph, MethodInvokeNode min) { + + MethodDescriptor mdCallee = min.getMethod(); + MethodDescriptor mdCaller = callerGraph.getMethodDescriptor(); + Map callerMapLocToCompLoc = + callerGraph.getMapLocationToInferCompositeLocation(); + + FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); + GlobalFlowGraph calleeGlobalGraph = getSubGlobalFlowGraph(mdCallee); + + NTuple baseLocTuple = + translateToLocTuple(mdCaller, mapMethodInvokeNodeToBaseTuple.get(min)); + + System.out.println("-translate caller infer composite loc to callee=" + mdCallee); + Set keySet = callerMapLocToCompLoc.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Location key = (Location) iterator.next(); + CompositeLocation callerCompLoc = callerMapLocToCompLoc.get(key); + + if (!key.getDescriptor().equals(mdCaller) + && callerCompLoc.getTuple().startsWith(baseLocTuple)) { + // need to translate to the callee side + // System.out.println("need to translate callerCompLoc=" + callerCompLoc + + // " with baseTuple=" + // + baseLocTuple); + // TODO + CompositeLocation newCalleeCompLoc = + translateCompositeLocationToCallee(callerCompLoc, baseLocTuple, mdCallee); + calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, newCalleeCompLoc); + System.out.println("---callee loc=" + key + " newCalleeCompLoc=" + newCalleeCompLoc); + } + } + + // If the location of an argument has a composite location + // need to assign a proper composite location to the corresponding callee parameter + System.out.println("-translate arg composite location to callee param:"); + Map> mapIdxToArgTuple = mapMethodInvokeNodeToArgIdxMap.get(min); + Set idxSet = mapIdxToArgTuple.keySet(); + for (Iterator iterator = idxSet.iterator(); iterator.hasNext();) { + Integer idx = (Integer) iterator.next(); + + if (idx == 0 && !min.getMethod().isStatic()) { + continue; + } + + NTuple argTuple = mapIdxToArgTuple.get(idx); + + // check if an arg tuple has been already assigned to a composite location + NTuple argLocTuple = translateToLocTuple(mdCaller, argTuple); + Location argLocalLoc = argLocTuple.get(0); + + // if (!isPrimitiveType(argTuple)) { + if (callerMapLocToCompLoc.containsKey(argLocalLoc)) { + + CompositeLocation callerCompLoc = callerMapLocToCompLoc.get(argLocalLoc); + for (int i = 1; i < argLocTuple.size(); i++) { + callerCompLoc.addLocation(argLocTuple.get(i)); + } + + if (callerCompLoc.getTuple().startsWith(baseLocTuple)) { + + FlowNode calleeParamFlowNode = calleeFlowGraph.getParamFlowNode(idx); + NTuple calleeParamDescTuple = calleeParamFlowNode.getDescTuple(); + NTuple calleeParamLocTuple = + translateToLocTuple(mdCallee, calleeParamDescTuple); + + CompositeLocation newCalleeCompLoc = + translateCompositeLocationToCallee(callerCompLoc, baseLocTuple, mdCallee); + + calleeGlobalGraph.addMapLocationToInferCompositeLocation(calleeParamLocTuple.get(0), + newCalleeCompLoc); + + System.out.println("###need to assign composite location to=" + calleeParamDescTuple + + " with baseTuple=" + baseLocTuple); + System.out.println("---newCalleeCompLoc=" + newCalleeCompLoc); + } + + } + + } + + } + + 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(); + } + + return true; + } + + private CompositeLocation translateCompositeLocationToCallee(CompositeLocation callerCompLoc, + NTuple baseLocTuple, MethodDescriptor mdCallee) { + + CompositeLocation newCalleeCompLoc = new CompositeLocation(); + + // replace the last element of the caller compLoc with the 'this' location of the callee + for (int i = 0; i < baseLocTuple.size() - 1; i++) { + newCalleeCompLoc.addLocation(baseLocTuple.get(i)); + } + + Location calleeThisLoc = new Location(mdCallee, mdCallee.getThis()); + newCalleeCompLoc.addLocation(calleeThisLoc); + + for (int i = baseLocTuple.size(); i < callerCompLoc.getSize(); i++) { + newCalleeCompLoc.addLocation(callerCompLoc.get(i)); + } + + return newCalleeCompLoc; + + } + + private void constructGlobalFlowGraph() { + + System.out.println(""); + LinkedList methodDescList = + (LinkedList) toanalyze_methodDescList.clone(); + + System.out.println("@@@methodDescList=" + methodDescList); + // System.exit(0); + + while (!methodDescList.isEmpty()) { + MethodDescriptor md = methodDescList.removeLast(); + if (state.SSJAVADEBUG) { + System.out.println(); + System.out.println("SSJAVA: Constructing a global flow graph: " + md); + + FlowGraph flowGraph = getFlowGraph(md); + FlowGraph subGlobalFlowGraph = flowGraph.clone(); + + // mapMethodDescriptorToSubGlobalFlowGraph.put(md, subGlobalFlowGraph); + + // addValueFlowsFromCalleeSubGlobalFlowGraph(md, subGlobalFlowGraph); + + // try { + // subGlobalFlowGraph.writeGraph("_SUBGLOBAL"); + // } catch (IOException e) { + // e.printStackTrace(); + // } + // FlowGraph fg = new FlowGraph(md, mapParamDescToIdx); + // mapMethodDescriptorToFlowGraph.put(md, fg); + // analyzeMethodBody(md.getClassDesc(), md); + } + + } + + // DEBUG: 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 calculateGlobalValueFlowCompositeLocation() { + + System.out.println("SSJAVA: Calculate composite locations in the global value flow graph"); + MethodDescriptor methodDescEventLoop = ssjava.getMethodContainingSSJavaLoop(); + GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(methodDescEventLoop); + + Set> prefixSet = new HashSet>(); + + Set nodeSet = globalFlowGraph.getNodeSet(); + + next: for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + GlobalFlowNode node = (GlobalFlowNode) iterator.next(); + Set incomingNodeSet = globalFlowGraph.getIncomingNodeSet(node); + List> prefixList = calculatePrefixList(globalFlowGraph, node); + Set reachNodeSet = globalFlowGraph.getReachableNodeSetFrom(node); + + // System.out.println("node=" + node + " inNodeSet=" + incomingNodeSet + // + " reachableNodeSet=" + reachNodeSet); + + for (int i = 0; i < prefixList.size(); i++) { + NTuple curPrefix = prefixList.get(i); + Set> reachableCommonPrefixSet = new HashSet>(); + + for (Iterator iterator2 = reachNodeSet.iterator(); iterator2.hasNext();) { + GlobalFlowNode reachNode = (GlobalFlowNode) iterator2.next(); + if (reachNode.getLocTuple().startsWith(curPrefix)) { + reachableCommonPrefixSet.add(reachNode.getLocTuple()); + } + } + + if (!reachableCommonPrefixSet.isEmpty()) { + + // TODO + if (!node.getLocTuple().startsWith(curPrefix.get(0))) { + CompositeLocation newCompLoc = generateCompositeLocation(curPrefix); + System.out.println("NEED TO ASSIGN COMP LOC TO " + node + " with prefix=" + curPrefix); + System.out.println("- newCompLoc=" + newCompLoc); + + Location targetLocalLoc = node.getLocTuple().get(0); + globalFlowGraph.addMapLocationToInferCompositeLocation(targetLocalLoc, newCompLoc); + + continue next; + } + + } + + } + + } + // Set inNodeSet = + // graph.getIncomingNodeSetWithPrefix(prefix); + // System.out.println("inNodeSet=" + inNodeSet + " from=" + node); + } + + 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); + + Set incomingNodeSet = graph.getIncomingNodeSet(node); + + List> prefixList = new ArrayList>(); + + for (Iterator iterator = incomingNodeSet.iterator(); iterator.hasNext();) { + GlobalFlowNode inNode = (GlobalFlowNode) iterator.next(); + NTuple inNodeTuple = inNode.getLocTuple(); + + 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; + } + + private GlobalFlowGraph constructSubGlobalFlowGraph(FlowGraph flowGraph) { + + MethodDescriptor md = flowGraph.getMethodDescriptor(); + + GlobalFlowGraph globalGraph = new GlobalFlowGraph(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(); + + // 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, + GlobalFlowGraph subGlobalFlowGraph) { + + // the transformation for a call site propagates flows through parameters + // if the method is virtual, it also grab all relations from any possible + // callees + + Set setMethodInvokeNode = getMethodInvokeNodeSet(mdCaller); + + for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) { + MethodInvokeNode min = (MethodInvokeNode) iterator.next(); + MethodDescriptor mdCallee = min.getMethod(); + Set setPossibleCallees = new HashSet(); + if (mdCallee.isStatic()) { + setPossibleCallees.add(mdCallee); + } else { + Set calleeSet = ssjava.getCallGraph().getMethods(mdCallee); + // removes method descriptors that are not invoked by the caller + calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller)); + setPossibleCallees.addAll(calleeSet); + } + + for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) { + MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next(); + propagateValueFlowsToCallerFromSubGlobalFlowGraph(min, mdCaller, possibleMdCallee); + } + + } + + } + + private void propagateValueFlowsToCallerFromSubGlobalFlowGraph(MethodInvokeNode min, + MethodDescriptor mdCaller, MethodDescriptor possibleMdCallee) { + + System.out.println("propagateValueFlowsToCallerFromSubGlobalFlowGraph=" + min.printNode(0) + + " by 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); + addMapCallerArgToCalleeParam(min, argDescTuple, paramDescTuple); + } + + } + + NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); + GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(possibleMdCallee); + Set calleeNodeSet = calleeSubGlobalGraph.getNodeSet(); + System.out.println("#calleeNodeSet=" + calleeNodeSet); + for (Iterator iterator = calleeNodeSet.iterator(); iterator.hasNext();) { + GlobalFlowNode calleeNode = (GlobalFlowNode) iterator.next(); + addValueFlowFromCalleeNode(min, mdCaller, possibleMdCallee, calleeNode); + } + + // int numParam = calleeFlowGraph.getNumParameters(); + // for (int idx = 0; idx < numParam; idx++) { + // + // FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx); + // + // NTuple paramLocTuple = + // translateToLocTuple(possibleMdCallee, paramNode.getCurrentDescTuple()); + // + // GlobalFlowNode globalParamNode = + // calleeSubGlobalGraph.getFlowNode(paramLocTuple); + // + // NTuple argTuple = + // mapMethodInvokeNodeToArgIdxMap.get(min).get(idx); + // + // NTuple argLocTuple = translateToLocTuple(mdCaller, argTuple); + // + // System.out.println("argTupleSet=" + argLocTuple + " param=" + + // paramLocTuple); + // // here, it adds all value flows reachable from the paramNode in the + // callee's flow graph + // + // addValueFlowsFromCalleeParam(mdCaller, argLocTuple, baseLocTuple, + // possibleMdCallee, + // globalParamNode); + // } + // + // // TODO + // // FlowGraph callerSubGlobalGraph = getSubGlobalFlowGraph(mdCaller); + // // FlowGraph calleeSubGlobalGraph = + // getSubGlobalFlowGraph(possibleMdCallee); + // // + // // int numParam = calleeSubGlobalGraph.getNumParameters(); + // // for (int idx = 0; idx < numParam; idx++) { + // // FlowNode paramNode = calleeSubGlobalGraph.getParamFlowNode(idx); + // // NTuple argTuple = + // mapMethodInvokeNodeToArgIdxMap.get(min).get(idx); + // // System.out.println("argTupleSet=" + argTuple + " param=" + + // paramNode); + // // // here, it adds all value flows reachable from the paramNode in the + // callee's flow graph + // // addValueFlowsFromCalleeParam(min, calleeSubGlobalGraph, paramNode, + // callerSubGlobalGraph, + // // argTuple, baseTuple); + // // } + + } + + private void addValueFlowFromCalleeNode(MethodInvokeNode min, MethodDescriptor mdCaller, + MethodDescriptor mdCallee, GlobalFlowNode calleeSrcNode) { + + GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(mdCallee); + GlobalFlowGraph callerSubGlobalGraph = getSubGlobalFlowGraph(mdCaller); + + NTuple callerSrcNodeLocTuple = + translateToCallerLocTuple(min, mdCallee, mdCaller, calleeSrcNode.getLocTuple()); + + + if (callerSrcNodeLocTuple != null) { + 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()); + if (callerDstNodeLocTuple != null) { + callerSubGlobalGraph.addValueFlowEdge(callerSrcNodeLocTuple, callerDstNodeLocTuple); + } + } + } + + } + + private NTuple translateToCallerLocTuple(MethodInvokeNode min, + MethodDescriptor mdCallee, MethodDescriptor mdCaller, NTuple nodeLocTuple) { + // this method will return NULL if the corresponding argument is literal + // value. + // assumes that we don't need to propagate callee flows to the argument + // which is literal. + + System.out.println("---translateToCallerLocTuple=" + min.printNode(0) + + " callee nodeLocTuple=" + nodeLocTuple); + + FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); + + NTuple nodeDescTuple = translateToDescTuple(nodeLocTuple); + if (calleeFlowGraph.isParameter(nodeDescTuple)) { + int paramIdx = calleeFlowGraph.getParamIdx(nodeDescTuple); + NTuple argDescTuple = mapMethodInvokeNodeToArgIdxMap.get(min).get(paramIdx); + // System.out.println(" mapMethodInvokeNodeToArgIdxMap.get(min)=" + // + mapMethodInvokeNodeToArgIdxMap.get(min)); + + if (argDescTuple.size() == 0) { + // argument is literal + return null; + } + 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(); + } + + } + + 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; + + } + + private void addValueFlowsFromCalleeParam(MethodDescriptor mdCaller, + NTuple argLocTuple, NTuple baseLocTuple, MethodDescriptor mdCallee, + GlobalFlowNode globalParamNode) { + + Set visited = new HashSet(); + visited.add(globalParamNode); + recurAddValueFlowsFromCalleeParam(mdCaller, argLocTuple, baseLocTuple, mdCallee, + globalParamNode); + + } + + private void recurAddValueFlowsFromCalleeParam(MethodDescriptor mdCaller, + NTuple argLocTuple, NTuple baseLocTuple, MethodDescriptor mdCallee, + GlobalFlowNode calleeCurNode) { + + // FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); + // GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(mdCallee); + // + // NTuple curNodeLocTuple = calleeCurNode.getLocTuple(); + // NTuple curNodeDescTuple = calleeCurNode.getDescTuple(); + // if (calleeFlowGraph.isParameter(curNodeDescTuple)) { + // curNodeLocTuple = translateToCaller(argLocTuple, curNodeLocTuple); + // } + // + // Set outNodeSet = + // calleeSubGlobalGraph.getOutNodeSet(calleeCurNode); + // for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) { + // GlobalFlowNode outNode = (GlobalFlowNode) iterator.next(); + // + // NTuple curNodeLocTuple = calleeCurNode.getLocTuple(); + // NTuple curNodeDescTuple = calleeCurNode.getDescTuple(); + // if (calleeFlowGraph.isParameter(curNodeDescTuple)) { + // curNodeLocTuple = translateToCaller(argLocTuple, curNodeLocTuple); + // } + // + // outNode.getDescTuple(); + // + // if (calleeFlowGraph.is) + // + // if (calleeSubGlobalGraph.isParameter(srcDescTuple)) { + // // destination node is started with 'parameter' + // // need to translate it in terms of the caller's a node + // srcDescTuple = + // translateToCaller(min, calleeSubGlobalGraph.getParamIdx(srcDescTuple), + // srcDescTuple); + // } + // + // } + // + // Set edgeSet = + // calleeSubGlobalGraph.getOutEdgeSetStartingFrom(calleeSrcNode); + // for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) { + // FlowEdge flowEdge = (FlowEdge) iterator.next(); + // + // NTuple srcDescTuple = flowEdge.getInitTuple(); + // NTuple dstDescTuple = flowEdge.getEndTuple(); + // + // FlowNode dstNode = calleeSubGlobalGraph.getFlowNode(dstDescTuple); + // + // if (calleeSubGlobalGraph.isParameter(srcDescTuple)) { + // // destination node is started with 'parameter' + // // need to translate it in terms of the caller's a node + // srcDescTuple = + // translateToCaller(min, calleeSubGlobalGraph.getParamIdx(srcDescTuple), + // srcDescTuple); + // } + // + // if (calleeSubGlobalGraph.isParameter(dstDescTuple)) { + // // destination node is started with 'parameter' + // // need to translate it in terms of the caller's a node + // dstDescTuple = + // translateToCaller(min, calleeSubGlobalGraph.getParamIdx(dstDescTuple), + // dstDescTuple); + // } + // + // callerSubGlobalGraph.addValueFlowEdge(srcDescTuple, dstDescTuple); + // + // if (!visited.contains(dstNode)) { + // visited.add(dstNode); + // recurAddValueFlowsFromCalleeParam(min, calleeSubGlobalGraph, dstNode, + // callerSubGlobalGraph, + // dstDescTuple, visited, baseTuple); + // } + // + // } + + } + + private NTuple translateToCaller(NTuple argLocTuple, + NTuple curNodeLocTuple) { + + NTuple callerLocTuple = new NTuple(); + + callerLocTuple.addAll(argLocTuple); + for (int i = 1; i < curNodeLocTuple.size(); i++) { + callerLocTuple.add(curNodeLocTuple.get(i)); + } + + return callerLocTuple; + } + + private void recurAddValueFlowsFromCalleeParam(MethodInvokeNode min, + FlowGraph calleeSubGlobalGraph, FlowNode calleeSrcNode, FlowGraph callerSubGlobalGraph, + NTuple callerSrcTuple, Set visited, NTuple baseTuple) { + + MethodDescriptor mdCallee = calleeSubGlobalGraph.getMethodDescriptor(); + + // Set edgeSet = + // calleeSubGlobalGraph.getOutEdgeSet(calleeSrcNode); + Set edgeSet = calleeSubGlobalGraph.getOutEdgeSetStartingFrom(calleeSrcNode); + for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) { + FlowEdge flowEdge = (FlowEdge) iterator.next(); + + NTuple srcDescTuple = flowEdge.getInitTuple(); + NTuple dstDescTuple = flowEdge.getEndTuple(); + + FlowNode dstNode = calleeSubGlobalGraph.getFlowNode(dstDescTuple); + + if (calleeSubGlobalGraph.isParameter(srcDescTuple)) { + // destination node is started with 'parameter' + // need to translate it in terms of the caller's a node + srcDescTuple = + translateToCaller(min, calleeSubGlobalGraph.getParamIdx(srcDescTuple), srcDescTuple); + } + + if (calleeSubGlobalGraph.isParameter(dstDescTuple)) { + // destination node is started with 'parameter' + // need to translate it in terms of the caller's a node + dstDescTuple = + translateToCaller(min, calleeSubGlobalGraph.getParamIdx(dstDescTuple), dstDescTuple); + } + + callerSubGlobalGraph.addValueFlowEdge(srcDescTuple, dstDescTuple); + + if (!visited.contains(dstNode)) { + visited.add(dstNode); + recurAddValueFlowsFromCalleeParam(min, calleeSubGlobalGraph, dstNode, callerSubGlobalGraph, + dstDescTuple, visited, baseTuple); + } + + } + + } + + private NTuple translateToCaller(MethodInvokeNode min, int paramIdx, + NTuple srcDescTuple) { + + NTuple callerTuple = new NTuple(); + + NTuple argTuple = mapMethodInvokeNodeToArgIdxMap.get(min).get(paramIdx); + + for (int i = 0; i < argTuple.size(); i++) { + callerTuple.add(argTuple.get(i)); + } + + for (int i = 1; i < srcDescTuple.size(); i++) { + callerTuple.add(srcDescTuple.get(i)); + } + + return callerTuple; + } + + private NTuple traslateToCalleeParamTupleToCallerArgTuple( + NTuple calleeInitTuple, NTuple callerSrcTuple) { + + NTuple callerInitTuple = new NTuple(); + + for (int i = 0; i < callerSrcTuple.size(); i++) { + callerInitTuple.add(callerSrcTuple.get(i)); + } + + for (int i = 1; i < calleeInitTuple.size(); i++) { + callerInitTuple.add(calleeInitTuple.get(i)); + } + + return callerInitTuple; + } + + public LocationSummary getLocationSummary(Descriptor d) { + if (!mapDescToLocationSummary.containsKey(d)) { + if (d instanceof MethodDescriptor) { + mapDescToLocationSummary.put(d, new MethodSummary((MethodDescriptor) d)); + } else if (d instanceof ClassDescriptor) { + mapDescToLocationSummary.put(d, new FieldSummary()); + } + } + return mapDescToLocationSummary.get(d); + } + + private void generateMethodSummary() { + + Set keySet = md2lattice.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + MethodDescriptor md = (MethodDescriptor) iterator.next(); + + System.out.println("\nSSJAVA: generate method summary: " + md); + + FlowGraph flowGraph = getFlowGraph(md); + MethodSummary methodSummary = getMethodSummary(md); + + // construct a parameter mapping that maps a parameter descriptor to an + // inferred composite + // location + + for (int paramIdx = 0; paramIdx < flowGraph.getNumParameters(); paramIdx++) { + FlowNode flowNode = flowGraph.getParamFlowNode(paramIdx); + NTuple descTuple = flowNode.getDescTuple(); + + CompositeLocation assignedCompLoc = flowNode.getCompositeLocation(); + CompositeLocation inferredCompLoc; + if (assignedCompLoc != null) { + inferredCompLoc = translateCompositeLocation(assignedCompLoc); + } else { + Descriptor locDesc = descTuple.get(0); + Location loc = new Location(md, locDesc.getSymbol()); + loc.setLocDescriptor(locDesc); + inferredCompLoc = new CompositeLocation(loc); + } + System.out.println("-paramIdx=" + paramIdx + " infer=" + inferredCompLoc); + methodSummary.addMapParamIdxToInferLoc(paramIdx, inferredCompLoc); + } + + } + + } + + private CompositeLocation translateCompositeLocation(CompositeLocation compLoc) { + CompositeLocation newCompLoc = new CompositeLocation(); + + // System.out.println("compLoc=" + compLoc); + for (int i = 0; i < compLoc.getSize(); i++) { + Location loc = compLoc.get(i); + Descriptor enclosingDescriptor = loc.getDescriptor(); + Descriptor locDescriptor = loc.getLocDescriptor(); + + HNode hnode = getHierarchyGraph(enclosingDescriptor).getHNode(locDescriptor); + // System.out.println("-hnode=" + hnode + " from=" + locDescriptor + + // " enclosingDescriptor=" + // + enclosingDescriptor); + // System.out.println("-getLocationSummary(enclosingDescriptor)=" + // + getLocationSummary(enclosingDescriptor)); + String locName = getLocationSummary(enclosingDescriptor).getLocationName(hnode.getName()); + // System.out.println("-locName=" + locName); + Location newLoc = new Location(enclosingDescriptor, locName); + newLoc.setLocDescriptor(locDescriptor); + newCompLoc.addLocation(newLoc); + } + + return newCompLoc; + } + + private void debug_writeLattices() { + + Set keySet = mapDescriptorToSimpleLattice.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Descriptor key = (Descriptor) iterator.next(); + SSJavaLattice simpleLattice = mapDescriptorToSimpleLattice.get(key); + // HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(key); + HierarchyGraph scHierarchyGraph = getSkeletonCombinationHierarchyGraph(key); + if (key instanceof ClassDescriptor) { + writeInferredLatticeDotFile((ClassDescriptor) key, scHierarchyGraph, simpleLattice, + "_SIMPLE"); + } else if (key instanceof MethodDescriptor) { + MethodDescriptor md = (MethodDescriptor) key; + writeInferredLatticeDotFile(md.getClassDesc(), md, scHierarchyGraph, simpleLattice, + "_SIMPLE"); + } + + LocationSummary ls = getLocationSummary(key); + System.out.println("####LOC SUMMARY=" + key + "\n" + ls.getMapHNodeNameToLocationName()); + } + + Set cdKeySet = cd2lattice.keySet(); + for (Iterator iterator = cdKeySet.iterator(); iterator.hasNext();) { + ClassDescriptor cd = (ClassDescriptor) iterator.next(); + writeInferredLatticeDotFile((ClassDescriptor) cd, getSkeletonCombinationHierarchyGraph(cd), + cd2lattice.get(cd), ""); + } + + Set mdKeySet = md2lattice.keySet(); + for (Iterator iterator = mdKeySet.iterator(); iterator.hasNext();) { + MethodDescriptor md = (MethodDescriptor) iterator.next(); + writeInferredLatticeDotFile(md.getClassDesc(), md, getSkeletonCombinationHierarchyGraph(md), + md2lattice.get(md), ""); + } + + } + + private void buildLattice() { + + BuildLattice buildLattice = new BuildLattice(this); + + Set keySet = mapDescriptorToCombineSkeletonHierarchyGraph.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Descriptor desc = (Descriptor) iterator.next(); + + SSJavaLattice simpleLattice = buildLattice.buildLattice(desc); + + addMapDescToSimpleLattice(desc, simpleLattice); + + HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc); + System.out.println("## insertIntermediateNodesToStraightLine:" + + simpleHierarchyGraph.getName()); + SSJavaLattice lattice = + buildLattice.insertIntermediateNodesToStraightLine(desc, simpleLattice); + lattice.removeRedundantEdges(); + + if (desc instanceof ClassDescriptor) { + // field lattice + cd2lattice.put((ClassDescriptor) desc, lattice); + // ssjava.writeLatticeDotFile((ClassDescriptor) desc, null, lattice); + } else if (desc instanceof MethodDescriptor) { + // method lattice + md2lattice.put((MethodDescriptor) desc, lattice); + MethodDescriptor md = (MethodDescriptor) desc; + ClassDescriptor cd = md.getClassDesc(); + // ssjava.writeLatticeDotFile(cd, md, lattice); + } + + // System.out.println("\nSSJAVA: Insering Combination Nodes:" + desc); + // HierarchyGraph skeletonGraph = getSkeletonHierarchyGraph(desc); + // 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); + } + + } + + public void addMapDescToSimpleLattice(Descriptor desc, SSJavaLattice lattice) { + mapDescriptorToSimpleLattice.put(desc, lattice); + } + + public SSJavaLattice getSimpleLattice(Descriptor desc) { + return mapDescriptorToSimpleLattice.get(desc); + } + private void simplifyHierarchyGraph() { Set keySet = mapDescriptorToHierarchyGraph.keySet(); for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { Descriptor desc = (Descriptor) iterator.next(); HierarchyGraph simpleHierarchyGraph = getHierarchyGraph(desc).clone(); simpleHierarchyGraph.setName(desc + "_SIMPLE"); - simpleHierarchyGraph.simplifyHierarchyGraph(); + simpleHierarchyGraph.removeRedundantEdges(); + // simpleHierarchyGraph.simplifyHierarchyGraph(); mapDescriptorToSimpleHierarchyGraph.put(desc, simpleHierarchyGraph); } } @@ -252,8 +1269,9 @@ public class LocationInference { HierarchyGraph skeletonGraphWithCombinationNode = skeletonGraph.clone(); skeletonGraphWithCombinationNode.setName(desc + "_SC"); - HierarchyGraph hierarchyGraph = getHierarchyGraph(desc); - skeletonGraphWithCombinationNode.insertCombinationNodesToGraph(hierarchyGraph); + HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc); + System.out.println("Identifying Combination Nodes:"); + skeletonGraphWithCombinationNode.insertCombinationNodesToGraph(simpleHierarchyGraph); skeletonGraphWithCombinationNode.simplifySkeletonCombinationHierarchyGraph(); mapDescriptorToCombineSkeletonHierarchyGraph.put(desc, skeletonGraphWithCombinationNode); } @@ -267,18 +1285,49 @@ public class LocationInference { HierarchyGraph skeletonGraph = simpleGraph.generateSkeletonGraph(); skeletonGraph.setMapDescToHNode(simpleGraph.getMapDescToHNode()); skeletonGraph.setMapHNodeToDescSet(simpleGraph.getMapHNodeToDescSet()); + skeletonGraph.simplifyHierarchyGraph(); + // skeletonGraph.combineRedundantNodes(false); + // skeletonGraph.removeRedundantEdges(); mapDescriptorToSkeletonHierarchyGraph.put(desc, skeletonGraph); } } - private void debug_writeHierarchyDotFile() { + private void debug_writeHierarchyDotFiles() { + + Set keySet = mapDescriptorToHierarchyGraph.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Descriptor desc = (Descriptor) iterator.next(); + getHierarchyGraph(desc).writeGraph(); + } + + } + + private void debug_writeSimpleHierarchyDotFiles() { Set keySet = mapDescriptorToHierarchyGraph.keySet(); for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { Descriptor desc = (Descriptor) iterator.next(); getHierarchyGraph(desc).writeGraph(); getSimpleHierarchyGraph(desc).writeGraph(); + } + + } + + private void debug_writeSkeletonHierarchyDotFiles() { + + Set keySet = mapDescriptorToHierarchyGraph.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Descriptor desc = (Descriptor) iterator.next(); getSkeletonHierarchyGraph(desc).writeGraph(); + } + + } + + private void debug_writeSkeletonCombinationHierarchyDotFiles() { + + Set keySet = mapDescriptorToHierarchyGraph.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Descriptor desc = (Descriptor) iterator.next(); getSkeletonCombinationHierarchyGraph(desc).writeGraph(); } @@ -295,7 +1344,7 @@ public class LocationInference { return mapDescriptorToSkeletonHierarchyGraph.get(d); } - private HierarchyGraph getSkeletonCombinationHierarchyGraph(Descriptor d) { + public HierarchyGraph getSkeletonCombinationHierarchyGraph(Descriptor d) { if (!mapDescriptorToCombineSkeletonHierarchyGraph.containsKey(d)) { mapDescriptorToCombineSkeletonHierarchyGraph.put(d, new HierarchyGraph(d)); } @@ -333,24 +1382,24 @@ public class LocationInference { // start to analyze leaf node MethodDescriptor md = methodDescriptorsToVisitStack.pop(); - HierarchyGraph methodGraph = new HierarchyGraph(md); - MethodSummary methodSummary = new MethodSummary(); + HierarchyGraph hierarchyGraph = new HierarchyGraph(md); + // MethodSummary methodSummary = new MethodSummary(md); - MethodLocationInfo methodInfo = new MethodLocationInfo(md); - curMethodInfo = methodInfo; + // MethodLocationInfo methodInfo = new MethodLocationInfo(md); + // curMethodInfo = methodInfo; System.out.println(); System.out.println("SSJAVA: Construcing the hierarchy graph from " + md); - constructHierarchyGraph(md, methodGraph, methodSummary); + constructHierarchyGraph(md, hierarchyGraph); - HierarchyGraph prevMethodGraph = getHierarchyGraph(md); - MethodSummary prevMethodSummary = getMethodSummary(md); + HierarchyGraph prevHierarchyGraph = getHierarchyGraph(md); + // MethodSummary prevMethodSummary = getMethodSummary(md); - if ((!methodGraph.equals(prevMethodGraph)) || (!methodSummary.equals(prevMethodSummary))) { + if (!hierarchyGraph.equals(prevHierarchyGraph)) { - mapDescriptorToHierarchyGraph.put(md, methodGraph); - mapMethodDescToMethodSummary.put(md, methodSummary); + mapDescriptorToHierarchyGraph.put(md, hierarchyGraph); + // mapDescToLocationSummary.put(md, methodSummary); // results for callee changed, so enqueue dependents caller for // further analysis @@ -376,8 +1425,7 @@ public class LocationInference { return mapDescriptorToHierarchyGraph.get(d); } - private void constructHierarchyGraph(MethodDescriptor md, HierarchyGraph methodGraph, - MethodSummary methodSummary) { + private void constructHierarchyGraph(MethodDescriptor md, HierarchyGraph methodGraph) { // visit each node of method flow graph FlowGraph fg = getFlowGraph(md); @@ -394,7 +1442,7 @@ public class LocationInference { for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { FlowNode srcNode = (FlowNode) iterator.next(); - Set outEdgeSet = srcNode.getOutEdgeSet(); + Set outEdgeSet = fg.getOutEdgeSet(srcNode); for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) { FlowEdge outEdge = (FlowEdge) iterator2.next(); FlowNode dstNode = outEdge.getDst(); @@ -447,10 +1495,10 @@ public class LocationInference { } private MethodSummary getMethodSummary(MethodDescriptor md) { - if (!mapMethodDescToMethodSummary.containsKey(md)) { - mapMethodDescToMethodSummary.put(md, new MethodSummary()); + if (!mapDescToLocationSummary.containsKey(md)) { + mapDescToLocationSummary.put(md, new MethodSummary(md)); } - return mapMethodDescToMethodSummary.get(md); + return (MethodSummary) mapDescToLocationSummary.get(md); } private void addMapClassDefinitionToLineNum(ClassDescriptor cd, String strLine, int lineNum) { @@ -778,218 +1826,64 @@ public class LocationInference { rtr += "[]"; } } - rtr += " " + varDesc.getName(); - return rtr; - - } - - private String generateLocationAnnoatation(CompositeLocation loc) { - String rtr = ""; - // method location - Location methodLoc = loc.get(0); - rtr += methodLoc.getLocIdentifier(); - - for (int i = 1; i < loc.getSize(); i++) { - Location element = loc.get(i); - rtr += "," + element.getDescriptor().getSymbol() + "." + element.getLocIdentifier(); - } - - return rtr; - } - - private boolean isParameter(MethodDescriptor md, Descriptor localVarDesc) { - return getFlowGraph(md).isParamDesc(localVarDesc); - } - - private String extractFileName(String fileName) { - int idx = fileName.lastIndexOf("/"); - if (idx == -1) { - return fileName; - } else { - return fileName.substring(idx + 1); - } - - } - - private void codeGen() { - - Set originalFileNameSet = mapFileNameToLineVector.keySet(); - for (Iterator iterator = originalFileNameSet.iterator(); iterator.hasNext();) { - String orgFileName = (String) iterator.next(); - String outputFileName = extractFileName(orgFileName); - - Vector sourceVec = mapFileNameToLineVector.get(orgFileName); - - try { - - FileWriter fileWriter = new FileWriter("./infer/" + outputFileName); - BufferedWriter out = new BufferedWriter(fileWriter); - - for (int i = 0; i < sourceVec.size(); i++) { - out.write(sourceVec.get(i)); - out.newLine(); - } - out.close(); - } catch (IOException e) { - e.printStackTrace(); - } - - } - - } - - 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(); + rtr += " " + varDesc.getName(); + return rtr; - setupToAnalazeMethod(cd); + } - SSJavaLattice classLattice = cd2lattice.get(cd); - if (classLattice != null) { - classLattice.removeRedundantEdges(); - } + private String generateLocationAnnoatation(CompositeLocation loc) { + String rtr = ""; + // method location + Location methodLoc = loc.get(0); + rtr += methodLoc.getLocIdentifier(); - while (!toAnalyzeMethodIsEmpty()) { - MethodDescriptor md = toAnalyzeMethodNext(); - SSJavaLattice methodLattice = md2lattice.get(md); - if (methodLattice != null) { - methodLattice.removeRedundantEdges(); - } - } + for (int i = 1; i < loc.getSize(); i++) { + Location element = loc.get(i); + rtr += "," + element.getDescriptor().getSymbol() + "." + element.getLocIdentifier(); } + return rtr; } - private boolean checkLatticeProperty(Descriptor d, SSJavaLattice lattice) { - // if two elements has the same incoming node set, - // we need to merge two elements ... + private boolean isParameter(MethodDescriptor md, Descriptor localVarDesc) { + return getFlowGraph(md).isParamDesc(localVarDesc); + } - boolean isUpdated; - boolean isModified = false; - do { - isUpdated = removeNodeSharingSameIncomingNodes(d, lattice); - if (!isModified && isUpdated) { - isModified = true; - } - } while (isUpdated); + private String extractFileName(String fileName) { + int idx = fileName.lastIndexOf("/"); + if (idx == -1) { + return fileName; + } else { + return fileName.substring(idx + 1); + } - 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); + private void codeGen() { - } + Set originalFileNameSet = mapFileNameToLineVector.keySet(); + for (Iterator iterator = originalFileNameSet.iterator(); iterator.hasNext();) { + String orgFileName = (String) iterator.next(); + String outputFileName = extractFileName(orgFileName); - locInfo.removeRelatedInferLocSet(oldLocSymbol, newMergeLoc); + Vector sourceVec = mapFileNameToLineVector.get(orgFileName); - } + try { - for (Iterator iterator3 = mergeSet.iterator(); iterator3.hasNext();) { - String oldLoc = (String) iterator3.next(); - lattice.remove(oldLoc); - } - return true; - } - } - } + FileWriter fileWriter = new FileWriter("./infer/" + outputFileName); + BufferedWriter out = new BufferedWriter(fileWriter); + + for (int i = 0; i < sourceVec.size(); i++) { + out.write(sourceVec.get(i)); + out.newLine(); } + out.close(); + } catch (IOException e) { + e.printStackTrace(); } } - return false; + } private void checkLattices() { @@ -1053,77 +1947,6 @@ 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() { @@ -1231,86 +2054,6 @@ public class LocationInference { return desc; } - private void analyzeMethodLattice(MethodDescriptor md, SSJavaLattice methodLattice, - MethodLocationInfo methodInfo) throws CyclicFlowException { - - // first take a look at method invocation nodes to newly added relations - // from the callee - analyzeLatticeMethodInvocationNode(md, methodLattice, methodInfo); - - if (!md.isStatic()) { - // set the this location - String thisLocSymbol = md.getThis().getSymbol(); - methodInfo.setThisLocName(thisLocSymbol); - } - - // set the global location - methodInfo.setGlobalLocName(LocationInference.GLOBALLOC); - methodInfo.mapDescriptorToLocation(GLOBALDESC, new CompositeLocation( - new Location(md, GLOBALLOC))); - - // visit each node of method flow graph - FlowGraph fg = getFlowGraph(md); - Set nodeSet = fg.getNodeSet(); - - // 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(); - - Set outEdgeSet = srcNode.getOutEdgeSet(); - for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) { - FlowEdge outEdge = (FlowEdge) iterator2.next(); - FlowNode dstNode = outEdge.getDst(); - - NTuple srcNodeTuple = srcNode.getDescTuple(); - NTuple dstNodeTuple = dstNode.getDescTuple(); - - if (outEdge.getInitTuple().equals(srcNodeTuple) - && outEdge.getEndTuple().equals(dstNodeTuple)) { - - if ((srcNodeTuple.size() > 1 && dstNodeTuple.size() > 1) - && srcNodeTuple.get(0).equals(dstNodeTuple.get(0))) { - - // value flows between fields - Descriptor desc = srcNodeTuple.get(0); - ClassDescriptor classDesc; - - 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); - } - } - } - } - - // create mapping from param idx to inferred composite location - - int offset; - if (!md.isStatic()) { - // add 'this' reference location - offset = 1; - methodInfo.addMapParamIdxToInferLoc(0, methodInfo.getInferLocation(md.getThis())); - } else { - offset = 0; - } - - for (int idx = 0; idx < md.numParameters(); idx++) { - Descriptor paramDesc = md.getParameter(idx); - CompositeLocation inferParamLoc = methodInfo.getInferLocation(paramDesc); - methodInfo.addMapParamIdxToInferLoc(idx + offset, inferParamLoc); - } - - } - private void calculateExtraLocations(MethodDescriptor md) { // calcualte pcloc, returnloc,... @@ -1334,123 +2077,122 @@ public class LocationInference { 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"; - - Set paramInFlowSet = new HashSet(); + if (!ssjava.getMethodContainingSSJavaLoop().equals(md)) { + // calculate the initial program counter location + // PC location is higher than location types of all parameters + String pcLocSymbol = "PCLOC"; - for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) { - Integer paramIdx = (Integer) iterator.next(); + Set paramInFlowSet = new HashSet(); - FlowNode paramFlowNode = fg.getParamFlowNode(paramIdx); + for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) { + Integer paramIdx = (Integer) iterator.next(); - if (fg.getIncomingFlowNodeSet(paramFlowNode).size() > 0) { - // parameter has in-value flows - CompositeLocation inferLoc = mapParamToLoc.get(paramIdx); - paramInFlowSet.add(inferLoc); - } - } + FlowNode paramFlowNode = fg.getParamFlowNode(paramIdx); - if (paramInFlowSet.size() > 0) { - CompositeLocation lowestLoc = getLowest(methodLattice, paramInFlowSet); - assert (lowestLoc != null); - methodInfo.setPCLoc(lowestLoc); + if (fg.getIncomingFlowNodeSet(paramFlowNode).size() > 0) { + // parameter has in-value flows + CompositeLocation inferLoc = mapParamToLoc.get(paramIdx); + paramInFlowSet.add(inferLoc); } - } - // 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 + if (paramInFlowSet.size() > 0) { + CompositeLocation lowestLoc = getLowest(methodLattice, paramInFlowSet); + assert (lowestLoc != null); + methodInfo.setPCLoc(lowestLoc); + } - Set inferFieldReturnLocSet = new HashSet(); + } - Set paramFlowNode = getParamNodeFlowingToReturnValue(md); - Set inferParamLocSet = new HashSet(); - if (paramFlowNode != null) { - for (Iterator iterator = paramFlowNode.iterator(); iterator.hasNext();) { - FlowNode fn = (FlowNode) iterator.next(); - CompositeLocation inferLoc = - generateInferredCompositeLocation(methodInfo, getFlowGraph(md).getLocationTuple(fn)); - inferParamLocSet.add(inferLoc); - } + // calculate a return location + // the return location type is lower than all parameters and location + // types + // of return values + if (!md.getReturnType().isVoid()) { + // first, generate the set of return value location types that starts + // with + // 'this' reference + + Set inferFieldReturnLocSet = new HashSet(); + + Set paramFlowNode = getParamNodeFlowingToReturnValue(md); + Set inferParamLocSet = new HashSet(); + if (paramFlowNode != null) { + for (Iterator iterator = paramFlowNode.iterator(); iterator.hasNext();) { + FlowNode fn = (FlowNode) iterator.next(); + CompositeLocation inferLoc = + generateInferredCompositeLocation(methodInfo, getFlowGraph(md).getLocationTuple(fn)); + inferParamLocSet.add(inferLoc); } + } - Set returnNodeSet = fg.getReturnNodeSet(); - - skip: for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { - FlowNode returnNode = (FlowNode) iterator.next(); - CompositeLocation inferReturnLoc = - generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode)); - if (inferReturnLoc.get(0).getLocIdentifier().equals("this")) { - // if the location type of the return value matches "this" reference - // then, check whether this return value is equal to/lower than all - // of - // parameters that possibly flow into the return values - for (Iterator iterator2 = inferParamLocSet.iterator(); iterator2.hasNext();) { - CompositeLocation paramInferLoc = (CompositeLocation) iterator2.next(); - - if ((!paramInferLoc.equals(inferReturnLoc)) - && !isGreaterThan(methodLattice, paramInferLoc, inferReturnLoc)) { - continue skip; - } + 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); - } + inferFieldReturnLocSet.add(inferReturnLoc); + } + } - if (inferFieldReturnLocSet.size() > 0) { + if (inferFieldReturnLocSet.size() > 0) { - CompositeLocation returnLoc = getLowest(methodLattice, inferFieldReturnLocSet); - if (returnLoc == null) { - // in this case, assign <'this',bottom> to the RETURNLOC - returnLoc = new CompositeLocation(new Location(md, md.getThis().getSymbol())); - returnLoc.addLocation(new Location(md.getClassDesc(), getLattice(md.getClassDesc()) - .getBottomItem())); - } - methodInfo.setReturnLoc(returnLoc); + CompositeLocation returnLoc = getLowest(methodLattice, inferFieldReturnLocSet); + if (returnLoc == null) { + // in this case, assign <'this',bottom> to the RETURNLOC + returnLoc = new CompositeLocation(new Location(md, md.getThis().getSymbol())); + returnLoc.addLocation(new Location(md.getClassDesc(), getLattice(md.getClassDesc()) + .getBottomItem())); + } + methodInfo.setReturnLoc(returnLoc); - } else { - String returnLocSymbol = "RETURNLOC"; - CompositeLocation returnLocInferLoc = - new CompositeLocation(new Location(md, returnLocSymbol)); - methodInfo.setReturnLoc(returnLocInferLoc); - - for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) { - Integer paramIdx = (Integer) iterator.next(); - CompositeLocation inferLoc = mapParamToLoc.get(paramIdx); - String paramLocLocalSymbol = inferLoc.get(0).getLocIdentifier(); - if (!methodLattice.isGreaterThan(paramLocLocalSymbol, returnLocSymbol)) { - addRelationHigherToLower(methodLattice, methodInfo, paramLocLocalSymbol, - returnLocSymbol); - } - } + } else { + String returnLocSymbol = "RETURNLOC"; + CompositeLocation returnLocInferLoc = + new CompositeLocation(new Location(md, returnLocSymbol)); + methodInfo.setReturnLoc(returnLocInferLoc); - 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); - } + for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) { + Integer paramIdx = (Integer) iterator.next(); + CompositeLocation inferLoc = mapParamToLoc.get(paramIdx); + String paramLocLocalSymbol = inferLoc.get(0).getLocIdentifier(); + if (!methodLattice.isGreaterThan(paramLocLocalSymbol, returnLocSymbol)) { + // TODO + // addRelationHigherToLower(methodLattice, methodInfo, + // paramLocLocalSymbol, + // returnLocSymbol); } + } + for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { + FlowNode returnNode = (FlowNode) iterator.next(); + CompositeLocation inferLoc = + generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode)); + if (!isGreaterThan(methodLattice, inferLoc, returnLocInferLoc)) { + // TODO + // addRelation(methodLattice, methodInfo, inferLoc, + // returnLocInferLoc); + } } } - } catch (CyclicFlowException e) { - e.printStackTrace(); - } + } } private Set getHigherLocSymbolThan(SSJavaLattice lattice, String loc) { @@ -1567,57 +2309,86 @@ public class LocationInference { return false; } - private void recursiveAddRelationToLattice(int idx, MethodDescriptor md, - CompositeLocation srcInferLoc, CompositeLocation dstInferLoc) throws CyclicFlowException { - - String srcLocSymbol = srcInferLoc.get(idx).getLocIdentifier(); - String dstLocSymbol = dstInferLoc.get(idx).getLocIdentifier(); + private void contributeCalleeFlows(MethodInvokeNode min, MethodDescriptor mdCaller, + MethodDescriptor mdCallee) { - if (srcLocSymbol.equals(dstLocSymbol)) { - recursiveAddRelationToLattice(idx + 1, md, srcInferLoc, dstInferLoc); - } else { + System.out.println("\n##contributeCalleeFlows callee=" + mdCallee + "TO caller=" + mdCaller); - Descriptor parentDesc = srcInferLoc.get(idx).getDescriptor(); - LocationInfo locInfo = getLocationInfo(parentDesc); + getSubGlobalFlowGraph(mdCallee); - addRelationHigherToLower(getLattice(parentDesc), getLocationInfo(parentDesc), srcLocSymbol, - dstLocSymbol); - } + } + private GlobalFlowGraph getSubGlobalFlowGraph(MethodDescriptor md) { + return mapMethodDescriptorToSubGlobalFlowGraph.get(md); } - private void propagateFlowsFromCallee(MethodInvokeNode min, MethodDescriptor mdCaller, - MethodDescriptor mdCallee) { + private void propagateFlowsToCallerWithNoCompositeLocation(MethodInvokeNode min, + MethodDescriptor mdCaller, MethodDescriptor mdCallee) { - // the transformation for a call site propagates all relations between - // parameters from the callee - // if the method is virtual, it also grab all relations from any possible - // callees + System.out.println("\n##PROPAGATE callee=" + mdCallee + "TO caller=" + mdCaller); - Set setPossibleCallees = new HashSet(); - if (mdCallee.isStatic()) { - setPossibleCallees.add(mdCallee); - } else { - Set calleeSet = ssjava.getCallGraph().getMethods(mdCallee); - // removes method descriptors that are not invoked by the caller - calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller)); - setPossibleCallees.addAll(calleeSet); - } + // 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 - for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) { - MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next(); - propagateFlowsToCaller(min, mdCaller, possibleMdCallee); + 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); + + NTuple arg1Tuple = getNodeTupleByArgIdx(min, i); + NTuple arg2Tuple = getNodeTupleByArgIdx(min, k); + + // check if the callee propagates an ordering constraints through + // parameters + + Set localReachSet = calleeFlowGraph.getLocalReachFlowNodeSetFrom(paramNode1); + + if (arg1Tuple.size() > 0 && arg2Tuple.size() > 2 && localReachSet.contains(paramNode2)) { + // need to propagate an ordering relation s.t. arg1 is higher + // than arg2 + + System.out.println("-param1=" + paramNode1 + " is higher than param2=" + paramNode2); + System.out + .println("-arg1Tuple=" + arg1Tuple + " is higher than arg2Tuple=" + arg2Tuple); + + // otherwise, flows between method/field locations... + callerFlowGraph.addValueFlowEdge(arg1Tuple, arg2Tuple); + System.out.println("arg1=" + arg1Tuple + " arg2=" + arg2Tuple); + + } + + System.out.println(); + } + } } + System.out.println("##\n"); } private void propagateFlowsToCaller(MethodInvokeNode min, MethodDescriptor mdCaller, MethodDescriptor mdCallee) { + System.out.println("\n##PROPAGATE callee=" + mdCallee + "TO caller=" + mdCaller); + // if the parameter A reaches to the parameter B // then, add an edge the argument A -> the argument B to the caller's flow // graph + // TODO + // also if a parameter is a composite location and is started with "this" + // reference, + // need to make sure that the corresponding argument is higher than the + // translated location of + // the parameter. + FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); FlowGraph callerFlowGraph = getFlowGraph(mdCaller); int numParam = calleeFlowGraph.getNumParameters(); @@ -1630,8 +2401,16 @@ public class LocationInference { FlowNode paramNode1 = calleeFlowGraph.getParamFlowNode(i); FlowNode paramNode2 = calleeFlowGraph.getParamFlowNode(k); - NodeTupleSet tupleSetArg1 = getNodeTupleSetByArgIdx(min, i); - NodeTupleSet tupleSetArg2 = getNodeTupleSetByArgIdx(min, 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(); @@ -1649,6 +2428,11 @@ public class LocationInference { // need to propagate an ordering relation s.t. arg1 is higher // than arg2 + System.out + .println("-param1=" + paramNode1 + " is higher than param2=" + paramNode2); + System.out.println("-arg1Tuple=" + arg1Tuple + " is higher than arg2Tuple=" + + arg2Tuple); + if (!min.getMethod().isStatic()) { // check if this is the case that values flow to/from the // current object reference 'this' @@ -1656,10 +2440,17 @@ public class LocationInference { NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); Descriptor baseRef = baseTuple.get(baseTuple.size() - 1); + System.out.println("paramNode1.getCurrentDescTuple()=" + + paramNode1.getCurrentDescTuple()); // calculate the prefix of the argument + if (arg2Tuple.size() == 1 && arg2Tuple.get(0).equals(baseRef)) { + // in this case, the callee flow causes a caller flow to the + // object whose method + // is invoked. if (!paramNode1.getCurrentDescTuple().startsWith(mdCallee.getThis())) { + // check whether ??? NTuple param1Prefix = calculatePrefixForParam(callerFlowGraph, calleeFlowGraph, min, arg1Tuple, @@ -1667,40 +2458,75 @@ public class LocationInference { if (param1Prefix != null && param1Prefix.startsWith(mdCallee.getThis())) { // in this case, we need to create a new edge - // 'this.FIELD'->'this' - // but we couldn't... instead we assign the - // corresponding - // parameter a new composite location started with - // 'this' - // reference + // 'this.FIELD'->'this' + // but we couldn't... instead we assign a new composite + // location started + // with 'this' reference to the corresponding parameter CompositeLocation compLocForParam1 = generateCompositeLocation(mdCallee, param1Prefix); - // System.out.println("set comp loc=" + compLocForParam1 - // + - // " to " + paramNode1); + System.out + .println("set comp loc=" + compLocForParam1 + " to " + paramNode1); paramNode1.setCompositeLocation(compLocForParam1); + + // then, we need to make sure that the corresponding + // argument in the caller + // is required to be higher than or equal to the + // translated parameter + // location + + NTuple translatedParamTuple = + translateCompositeLocationToCaller(min, compLocForParam1); + + // TODO : check if the arg >= the tranlated parameter + + System.out.println("add a flow edge= " + arg1Tuple + "->" + + translatedParamTuple); + callerFlowGraph.addValueFlowEdge(arg1Tuple, translatedParamTuple); + continue; + } + + } else { + // param1 has already been assigned a composite location + + System.out.println("--param1 has already been assigned a composite location"); + CompositeLocation compLocForParam1 = paramNode1.getCompositeLocation(); + NTuple translatedParamTuple = + translateCompositeLocationToCaller(min, compLocForParam1); + + // TODO : check if the arg >= the tranlated parameter + + System.out.println("add a flow edge= " + arg1Tuple + "->" + + translatedParamTuple); + callerFlowGraph.addValueFlowEdge(arg1Tuple, translatedParamTuple); + + continue; + } } else if (arg1Tuple.size() == 1 && arg1Tuple.get(0).equals(baseRef)) { + // in this case, the callee flow causes a caller flow + // originated from the object + // whose + // method is invoked. + + System.out.println("###FROM CASE"); if (!paramNode2.getCurrentDescTuple().startsWith(mdCallee.getThis())) { NTuple param2Prefix = - calculatePrefixForParam(callerFlowGraph, calleeFlowGraph, min, arg1Tuple, - paramNode1); + calculatePrefixForParam(callerFlowGraph, calleeFlowGraph, min, arg2Tuple, + paramNode2); if (param2Prefix != null && param2Prefix.startsWith(mdCallee.getThis())) { // in this case, we need to create a new edge 'this' -> - // 'this.FIELD' - // but we couldn't... instead we assign the + // 'this.FIELD' but we couldn't... instead we assign the // corresponding // parameter a new composite location started with - // 'this' - // reference + // 'this' reference CompositeLocation compLocForParam2 = generateCompositeLocation(mdCallee, param2Prefix); @@ -1718,33 +2544,98 @@ public class LocationInference { // otherwise, flows between method/field locations... callerFlowGraph.addValueFlowEdge(arg1Tuple, arg2Tuple); - // System.out.println("arg1=" + arg1Tuple + " arg2=" + - // arg2Tuple); + System.out.println("arg1=" + arg1Tuple + " arg2=" + arg2Tuple); } } } + System.out.println(); } } } + System.out.println("##\n"); + } + + private NTuple translateCompositeLocationToCaller(MethodInvokeNode min, + CompositeLocation compLocForParam1) { + NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); + + NTuple tuple = new NTuple(); + + for (int i = 0; i < baseTuple.size(); i++) { + tuple.add(baseTuple.get(i)); + } + + for (int i = 1; i < compLocForParam1.getSize(); i++) { + Location loc = compLocForParam1.get(i); + tuple.add(loc.getLocDescriptor()); + } + + return tuple; + } + + private CompositeLocation generateCompositeLocation(NTuple prefixLocTuple) { + + System.out.println("generateCompositeLocation=" + prefixLocTuple); + + 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(); + + ClassDescriptor enclosingDescriptor; + if (lastDescOfPrefix instanceof FieldDescriptor) { + enclosingDescriptor = ((FieldDescriptor) lastDescOfPrefix).getType().getClassDesc(); + // System.out.println("enclosingDescriptor0=" + enclosingDescriptor); + } else { + // var descriptor case + enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc(); + } + // System.out.println("enclosingDescriptor=" + enclosingDescriptor); + + LocationDescriptor newLocDescriptor = generateNewLocationDescriptor(); + newLocDescriptor.setEnclosingClassDesc(enclosingDescriptor); + + Location newLoc = new Location(enclosingDescriptor, newLocDescriptor.getSymbol()); + newLoc.setLocDescriptor(newLocDescriptor); + newCompLoc.addLocation(newLoc); + // System.out.println("--newCompLoc=" + newCompLoc); + return newCompLoc; } private CompositeLocation generateCompositeLocation(MethodDescriptor md, - NTuple param1Prefix) { + NTuple paramPrefix) { + + System.out.println("generateCompositeLocation=" + paramPrefix); + + CompositeLocation newCompLoc = convertToCompositeLocation(md, paramPrefix); - CompositeLocation newCompLoc = convertToCompositeLocation(md, param1Prefix); + Descriptor lastDescOfPrefix = paramPrefix.get(paramPrefix.size() - 1); + // System.out.println("lastDescOfPrefix=" + lastDescOfPrefix + " kind=" + // + lastDescOfPrefix.getClass()); + ClassDescriptor enclosingDescriptor; + if (lastDescOfPrefix instanceof FieldDescriptor) { + enclosingDescriptor = ((FieldDescriptor) lastDescOfPrefix).getType().getClassDesc(); + // System.out.println("enclosingDescriptor0=" + enclosingDescriptor); + } else { + // var descriptor case + enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc(); + } + // System.out.println("enclosingDescriptor=" + enclosingDescriptor); LocationDescriptor newLocDescriptor = generateNewLocationDescriptor(); + newLocDescriptor.setEnclosingClassDesc(enclosingDescriptor); - Descriptor enclosingDescriptor = param1Prefix.get(param1Prefix.size() - 1); Location newLoc = new Location(enclosingDescriptor, newLocDescriptor.getSymbol()); newLoc.setLocDescriptor(newLocDescriptor); newCompLoc.addLocation(newLoc); - System.out.println("newCompLoc=" + newCompLoc); + // System.out.println("--newCompLoc=" + newCompLoc); return newCompLoc; } @@ -1760,6 +2651,9 @@ public class LocationInference { List> callerPrefixList = calculatePrefixList(callerFlowGraph, flowNodeArg1); System.out.println("callerPrefixList=" + callerPrefixList); + List> prefixList = calculatePrefixList(calleeFlowGraph, paramNode1); + System.out.println("###prefixList from node=" + paramNode1 + " =" + prefixList); + List> calleePrefixList = translatePrefixListToCallee(baseRef, min.getMethod(), callerPrefixList); @@ -1813,9 +2707,13 @@ public class LocationInference { private List> calculatePrefixList(FlowGraph flowGraph, FlowNode flowNode) { + System.out.println("\n##### calculatePrefixList=" + flowNode); + Set inNodeSet = flowGraph.getIncomingFlowNodeSet(flowNode); inNodeSet.add(flowNode); + System.out.println("inNodeSet=" + inNodeSet); + List> prefixList = new ArrayList>(); for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) { @@ -1876,7 +2774,7 @@ public class LocationInference { } - System.out.println("convertToCompositeLocation from=" + tuple + " to " + compLoc); + System.out.println("-convertToCompositeLocation from=" + tuple + " to " + compLoc); return compLoc; } @@ -1907,102 +2805,6 @@ public class LocationInference { 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); - - // 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); - - } - - } - - } - } - } - } - - } - private CompositeLocation generateInferredCompositeLocation(MethodLocationInfo methodInfo, NTuple tuple) { @@ -2032,424 +2834,51 @@ public class LocationInference { getLocationInfo(enclosingDesc).getInferLocation(curDesc).get(0).getLocIdentifier(); inferLocElement = new Location(enclosingDesc, fieldLocSymbol); inferLocElement.setLocDescriptor(curDesc); - } - - inferLoc.addLocation(inferLocElement); - - } - - assert (inferLoc.get(0).getLocDescriptor().getSymbol() == inferLoc.get(0).getLocIdentifier()); - 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); - } else { - return getFieldLocationInfo((ClassDescriptor) d); - } - } - - private MethodLocationInfo getMethodLocationInfo(MethodDescriptor md) { - - if (!mapMethodDescToMethodLocationInfo.containsKey(md)) { - mapMethodDescToMethodLocationInfo.put(md, new MethodLocationInfo(md)); - } - - return mapMethodDescToMethodLocationInfo.get(md); - - } - - private LocationInfo getFieldLocationInfo(ClassDescriptor cd) { - - if (!mapClassToLocationInfo.containsKey(cd)) { - mapClassToLocationInfo.put(cd, new LocationInfo(cd)); - } - - return mapClassToLocationInfo.get(cd); - - } - - 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.getDescTuple().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.getDescTuple().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) { - - if (!map.containsKey(prefix)) { - map.put(prefix, new HashSet>()); - } - 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.getDescTuple().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.getDescTuple().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); + inferLoc.addLocation(inferLocElement); - 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); - } + assert (inferLoc.get(0).getLocDescriptor().getSymbol() == inferLoc.get(0).getLocIdentifier()); + return inferLoc; + } - 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); - } - } + public LocationInfo getLocationInfo(Descriptor d) { + if (d instanceof MethodDescriptor) { + return getMethodLocationInfo((MethodDescriptor) d); + } else { + return getFieldLocationInfo((ClassDescriptor) d); + } + } - return true; - } + private MethodLocationInfo getMethodLocationInfo(MethodDescriptor md) { + if (!mapMethodDescToMethodLocationInfo.containsKey(md)) { + mapMethodDescToMethodLocationInfo.put(md, new MethodLocationInfo(md)); } - return false; + return mapMethodDescToMethodLocationInfo.get(md); } - private void addMapLocSymbolToInferredLocation(MethodDescriptor md, Descriptor localVar, - CompositeLocation inferLoc) { + private LocationInfo getFieldLocationInfo(ClassDescriptor cd) { + + if (!mapClassToLocationInfo.containsKey(cd)) { + mapClassToLocationInfo.put(cd, new LocationInfo(cd)); + } + + return mapClassToLocationInfo.get(cd); - 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 void addPrefixMapping(Map, Set>> map, + NTuple prefix, NTuple element) { + + if (!map.containsKey(prefix)) { + map.put(prefix, new HashSet>()); + } + map.get(prefix).add(element); } private boolean containsNonPrimitiveElement(Set descSet) { @@ -2472,121 +2901,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); - } - - } - - private void prefixSanityCheck(List> prefixList, int curIdx, - FlowGraph flowGraph, Set reachableNodeSet) { - - NTuple curPrefix = prefixList.get(curIdx); - - for (int i = curIdx + 1; i < prefixList.size(); i++) { - NTuple prefixTuple = prefixList.get(i); - - if (curPrefix.startsWith(prefixTuple)) { - continue; - } - - for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) { - FlowNode reachableNode = (FlowNode) iterator2.next(); - NTuple reachLocTuple = flowGraph.getLocationTuple(reachableNode); - if (reachLocTuple.startsWith(prefixTuple)) { - // TODO - throw new Error("Failed to generate a composite location"); - } - } - } - } - - 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); @@ -2640,43 +2954,6 @@ public class LocationInference { } - private void extractRelationFromFieldFlows(ClassDescriptor cd, FlowNode srcNode, - FlowNode dstNode, int idx) throws CyclicFlowException { - - if (srcNode.getDescTuple().get(idx).equals(dstNode.getDescTuple().get(idx)) - && srcNode.getDescTuple().size() > (idx + 1) && dstNode.getDescTuple().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(); - } - - 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); - - } - - } - public SSJavaLattice getFieldLattice(ClassDescriptor cd) { if (!cd2lattice.containsKey(cd)) { cd2lattice.put(cd, new SSJavaLattice(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM)); @@ -2697,7 +2974,7 @@ public class LocationInference { ClassDescriptor cd = toAnalyzeNext(); setupToAnalazeMethod(cd); - toanalyzeMethodList.removeAll(visited); + temp_toanalyzeMethodList.removeAll(visited); while (!toAnalyzeMethodIsEmpty()) { MethodDescriptor md = toAnalyzeMethodNext(); @@ -2720,7 +2997,7 @@ public class LocationInference { if ((!ssjava.isTrustMethod(calleemd)) && (!ssjava.isSSJavaUtil(calleemd.getClassDesc()))) { if (!visited.contains(calleemd)) { - toanalyzeMethodList.add(calleemd); + temp_toanalyzeMethodList.add(calleemd); } reachableCallee.add(calleemd); needToAnalyzeCalleeSet.add(calleemd); @@ -2743,7 +3020,10 @@ public class LocationInference { public void constructFlowGraph() { System.out.println(""); - LinkedList methodDescList = computeMethodList(); + toanalyze_methodDescList = computeMethodList(); + + LinkedList methodDescList = + (LinkedList) toanalyze_methodDescList.clone(); System.out.println("@@@methodDescList=" + methodDescList); // System.exit(0); @@ -2771,12 +3051,86 @@ public class LocationInference { mapMethodDescriptorToFlowGraph.put(md, fg); analyzeMethodBody(md.getClassDesc(), md); - propagateFlowsFromCallees(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(); + // _debug_printGraph(); + + methodDescList = (LinkedList) toanalyze_methodDescList.clone(); + + while (!methodDescList.isEmpty()) { + MethodDescriptor md = methodDescList.removeLast(); + if (state.SSJAVADEBUG) { + System.out.println(); + System.out.println("SSJAVA: Constructing a flow graph2: " + md); + + System.out.println("##constructSubGlobalFlowGraph"); + GlobalFlowGraph subGlobalFlowGraph = constructSubGlobalFlowGraph(getFlowGraph(md)); + mapMethodDescriptorToSubGlobalFlowGraph.put(md, subGlobalFlowGraph); + + // TODO + System.out.println("##addValueFlowsFromCalleeSubGlobalFlowGraph"); + addValueFlowsFromCalleeSubGlobalFlowGraph(md, subGlobalFlowGraph); + subGlobalFlowGraph.writeGraph("_SUBGLOBAL"); + + propagateFlowsFromCalleesWithNoCompositeLocation(md); + + } + } + + } + + 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); + } } @@ -2821,6 +3175,40 @@ public class LocationInference { } + private void propagateFlowsFromCalleesWithNoCompositeLocation(MethodDescriptor mdCaller) { + + // the transformation for a call site propagates flows through parameters + // if the method is virtual, it also grab all relations from any possible + // callees + + Set setMethodInvokeNode = + mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller); + + if (setMethodInvokeNode != null) { + + for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) { + MethodInvokeNode min = (MethodInvokeNode) iterator.next(); + MethodDescriptor mdCallee = min.getMethod(); + Set setPossibleCallees = new HashSet(); + if (mdCallee.isStatic()) { + setPossibleCallees.add(mdCallee); + } else { + Set calleeSet = ssjava.getCallGraph().getMethods(mdCallee); + // removes method descriptors that are not invoked by the caller + calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller)); + setPossibleCallees.addAll(calleeSet); + } + + for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) { + MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next(); + propagateFlowsToCallerWithNoCompositeLocation(min, mdCaller, possibleMdCallee); + } + + } + } + + } + private void propagateFlowsFromCallees(MethodDescriptor mdCaller) { // the transformation for a call site propagates flows through parameters @@ -2931,7 +3319,8 @@ public class LocationInference { newImplicitTupleSet.addTupleSet(condTupleNode); if (newImplicitTupleSet.size() > 1) { - // need to create an intermediate node for the GLB of conditional locations & implicit flows + // 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(); @@ -2965,16 +3354,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()); // } // @@ -3019,7 +3413,8 @@ public class LocationInference { newImplicitTupleSet.addTupleSet(condTupleNode); if (newImplicitTupleSet.size() > 1) { - // need to create an intermediate node for the GLB of conditional locations & implicit flows + // 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();) { @@ -3033,14 +3428,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); @@ -3323,6 +3721,10 @@ public class LocationInference { private void analyzeFlowMethodInvokeNode(MethodDescriptor md, SymbolTable nametable, MethodInvokeNode min, NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) { + System.out.println("analyzeFlowMethodInvokeNode=" + min.printNode(0)); + + mapMethodInvokeNodeToArgIdxMap.put(min, new HashMap>()); + if (nodeSet == null) { nodeSet = new NodeTupleSet(); } @@ -3343,8 +3745,6 @@ public class LocationInference { FlowGraph calleeFlowGraph = getFlowGraph(calleeMethodDesc); Set calleeReturnSet = calleeFlowGraph.getReturnNodeSet(); - System.out.println("#calleeReturnSet=" + calleeReturnSet); - if (min.getExpression() != null) { NodeTupleSet baseNodeSet = new NodeTupleSet(); @@ -3352,10 +3752,11 @@ public class LocationInference { implicitFlowTupleSet, false); assert (baseNodeSet.size() == 1); - mapMethodInvokeNodeToBaseTuple.put(min, baseNodeSet.iterator().next()); + NTuple baseTuple = baseNodeSet.iterator().next(); + mapMethodInvokeNodeToBaseTuple.put(min, baseTuple); if (!min.getMethod().isStatic()) { - addArgIdxMap(min, 0, baseNodeSet); + addArgIdxMap(min, 0, baseTuple); for (Iterator iterator = calleeReturnSet.iterator(); iterator.hasNext();) { FlowNode returnNode = (FlowNode) iterator.next(); @@ -3363,15 +3764,13 @@ public class LocationInference { if (returnDescTuple.startsWith(calleeMethodDesc.getThis())) { // the location type of the return value is started with 'this' // reference - for (Iterator> baseIter = baseNodeSet.iterator(); baseIter - .hasNext();) { - NTuple baseTuple = baseIter.next(); - NTuple inFlowTuple = new NTuple(baseTuple.getList()); - inFlowTuple.addAll(returnDescTuple.subList(1, returnDescTuple.size())); - nodeSet.addTuple(inFlowTuple); - } + NTuple inFlowTuple = new NTuple(baseTuple.getList()); + inFlowTuple.addAll(returnDescTuple.subList(1, returnDescTuple.size())); + nodeSet.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())) { @@ -3400,8 +3799,26 @@ public class LocationInference { int idx = i + offset; NodeTupleSet argTupleSet = new NodeTupleSet(); analyzeFlowExpressionNode(md, nametable, en, argTupleSet, false); - // if argument is liternal node, argTuple is set to NULL. - addArgIdxMap(min, idx, argTupleSet); + // if argument is liternal node, argTuple is set to NULL + + NTuple argTuple = new NTuple(); + System.out.println("-argTupleSet=" + argTupleSet + " from en=" + en.printNode(0)); + if (argTupleSet.size() > 1) { + NTuple interTuple = + getFlowGraph(md).createIntermediateNode().getDescTuple(); + for (Iterator> idxIter = argTupleSet.iterator(); idxIter.hasNext();) { + NTuple tuple = idxIter.next(); + addFlowGraphEdge(md, tuple, interTuple); + } + argTuple = interTuple; + } else if (argTupleSet.size() == 1) { + argTuple = argTupleSet.iterator().next(); + } else { + argTuple = new NTuple(); + } + + addArgIdxMap(min, idx, argTuple); + FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx); if (hasInFlowTo(calleeFlowGraph, paramNode, calleeReturnSet) || calleeMethodDesc.getModifiers().isNative()) { @@ -3414,13 +3831,18 @@ public class LocationInference { // propagateFlowsFromCallee(min, md, min.getMethod()); + System.out.println("min nodeSet=" + nodeSet); } } private boolean hasInFlowTo(FlowGraph fg, FlowNode inNode, Set nodeSet) { // return true if inNode has in-flows to nodeSet - Set reachableSet = fg.getReachFlowNodeSetFrom(inNode); + + // 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)) { @@ -3430,48 +3852,20 @@ public class LocationInference { return false; } - private NodeTupleSet getNodeTupleSetByArgIdx(MethodInvokeNode min, int idx) { + private NTuple getNodeTupleByArgIdx(MethodInvokeNode min, int idx) { return mapMethodInvokeNodeToArgIdxMap.get(min).get(new Integer(idx)); } - private void addArgIdxMap(MethodInvokeNode min, int idx, NodeTupleSet tupleSet) { - Map mapIdxToTupleSet = mapMethodInvokeNodeToArgIdxMap.get(min); - if (mapIdxToTupleSet == null) { - mapIdxToTupleSet = new HashMap(); - mapMethodInvokeNodeToArgIdxMap.put(min, mapIdxToTupleSet); - } - mapIdxToTupleSet.put(new Integer(idx), tupleSet); - } - - private void analyzeFlowMethodParameters(MethodDescriptor callermd, SymbolTable nametable, - MethodInvokeNode min, NodeTupleSet nodeSet) { - - if (min.numArgs() > 0) { - - int offset; - if (min.getMethod().isStatic()) { - offset = 0; - } else { - offset = 1; - // NTuple thisArgTuple = new NTuple(); - // thisArgTuple.add(callermd.getThis()); - // NodeTupleSet argTupleSet = new NodeTupleSet(); - // argTupleSet.addTuple(thisArgTuple); - // addArgIdxMap(min, 0, argTupleSet); - // nodeSet.addTuple(thisArgTuple); - } - - for (int i = 0; i < min.numArgs(); i++) { - ExpressionNode en = min.getArg(i); - NodeTupleSet argTupleSet = new NodeTupleSet(); - analyzeFlowExpressionNode(callermd, nametable, en, argTupleSet, false); - // if argument is liternal node, argTuple is set to NULL. - addArgIdxMap(min, i + offset, argTupleSet); - nodeSet.addTupleSet(argTupleSet); - } - + private void addArgIdxMap(MethodInvokeNode min, int idx, NTuple argTuple /* + * NodeTupleSet + * tupleSet + */) { + Map> mapIdxToTuple = mapMethodInvokeNodeToArgIdxMap.get(min); + if (mapIdxToTuple == null) { + mapIdxToTuple = new HashMap>(); + mapMethodInvokeNodeToArgIdxMap.put(min, mapIdxToTuple); } - + mapIdxToTuple.put(new Integer(idx), argTuple); } private void analyzeLiteralNode(MethodDescriptor md, SymbolTable nametable, LiteralNode en) { @@ -3747,11 +4141,11 @@ public class LocationInference { analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null, implicitFlowTupleSet, false); - System.out.println("-analyzeFlowAssignmentNode=" + an.printNode(0)); - System.out.println("-nodeSetLHS=" + nodeSetLHS); - System.out.println("-nodeSetRHS=" + nodeSetRHS); - System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet); - System.out.println("-"); + // System.out.println("-analyzeFlowAssignmentNode=" + an.printNode(0)); + // System.out.println("-nodeSetLHS=" + nodeSetLHS); + // System.out.println("-nodeSetRHS=" + nodeSetRHS); + // System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet); + // System.out.println("-"); if (an.getOperation().getOp() >= 2 && an.getOperation().getOp() <= 12) { // if assignment contains OP+EQ operator, creates edges from LHS to LHS @@ -3837,6 +4231,100 @@ public class LocationInference { } + public void writeInferredLatticeDotFile(ClassDescriptor cd, HierarchyGraph simpleHierarchyGraph, + SSJavaLattice locOrder, String nameSuffix) { + writeInferredLatticeDotFile(cd, null, simpleHierarchyGraph, locOrder, nameSuffix); + } + + public void writeInferredLatticeDotFile(ClassDescriptor cd, MethodDescriptor md, + HierarchyGraph simpleHierarchyGraph, SSJavaLattice locOrder, String nameSuffix) { + + String fileName = "lattice_"; + if (md != null) { + fileName += + cd.getSymbol().replaceAll("[\\W_]", "") + "_" + md.toString().replaceAll("[\\W_]", ""); + } else { + fileName += cd.getSymbol().replaceAll("[\\W_]", ""); + } + + fileName += nameSuffix; + + Set> pairSet = locOrder.getOrderingPairSet(); + + Set addedLocSet = new HashSet(); + + if (pairSet.size() > 0) { + try { + BufferedWriter bw = new BufferedWriter(new FileWriter(fileName + ".dot")); + + bw.write("digraph " + fileName + " {\n"); + + for (Iterator iterator = pairSet.iterator(); iterator.hasNext();) { + // pair is in the form of + Pair pair = (Pair) iterator.next(); + + String highLocId = pair.getFirst(); + String lowLocId = pair.getSecond(); + + if (!addedLocSet.contains(highLocId)) { + addedLocSet.add(highLocId); + drawNode(bw, locOrder, simpleHierarchyGraph, highLocId); + } + + if (!addedLocSet.contains(lowLocId)) { + addedLocSet.add(lowLocId); + drawNode(bw, locOrder, simpleHierarchyGraph, lowLocId); + } + + bw.write(highLocId + " -> " + lowLocId + ";\n"); + } + bw.write("}\n"); + bw.close(); + + } catch (IOException e) { + e.printStackTrace(); + } + + } + + } + + private String convertMergeSetToString(HierarchyGraph graph, Set mergeSet) { + String str = ""; + for (Iterator iterator = mergeSet.iterator(); iterator.hasNext();) { + HNode merged = (HNode) iterator.next(); + if (merged.isMergeNode()) { + str += convertMergeSetToString(graph, graph.getMapHNodetoMergeSet().get(merged)); + } else { + str += " " + merged.getName(); + } + } + return str; + } + + private void drawNode(BufferedWriter bw, SSJavaLattice lattice, HierarchyGraph graph, + String locName) throws IOException { + + HNode node = graph.getHNode(locName); + + if (node == null) { + return; + } + + String prettyStr; + if (lattice.isSharedLoc(locName)) { + prettyStr = locName + "*"; + } else { + prettyStr = locName; + } + + if (node.isMergeNode()) { + Set mergeSet = graph.getMapHNodetoMergeSet().get(node); + prettyStr += ":" + convertMergeSetToString(graph, mergeSet); + } + bw.write(locName + " [label=\"" + prettyStr + "\"]" + ";\n"); + } + public void _debug_printGraph() { Set keySet = mapMethodDescriptorToFlowGraph.keySet();