X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=Robust%2Fsrc%2FAnalysis%2FSSJava%2FLocationInference.java;h=dfa8e0e72735a6c1364a78a7fe004624d4950773;hb=561af6103d5d245d56589c369041dccddf43cf48;hp=31900f103f5e2216b7f8ccdf62bf4c33258606f6;hpb=d421edc382984588192603ed519923beadeb4d3a;p=IRC.git diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index 31900f10..dfa8e0e7 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,12 @@ public class LocationInference { private Map mapDescToDefinitionLine; + private Map mapDescToLocationSummary; + + // maps a method descriptor to a sub global flow graph that captures all value flows caused by the + // set of callees reachable from the method + private Map mapMethodDescriptorToSubGlobalFlowGraph; + public static final String GLOBALLOC = "GLOBALLOC"; public static final String TOPLOC = "TOPLOC"; @@ -129,8 +137,8 @@ public class LocationInference { public LocationInference(SSJavaAnalysis ssjava, State state) { this.ssjava = ssjava; this.state = state; - this.toanalyzeList = new ArrayList(); - this.toanalyzeMethodList = new ArrayList(); + this.temp_toanalyzeList = new ArrayList(); + this.temp_toanalyzeMethodList = new ArrayList(); this.mapMethodDescriptorToFlowGraph = new HashMap(); this.cd2lattice = new HashMap>(); this.md2lattice = new HashMap>(); @@ -138,7 +146,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 +157,24 @@ 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(); + + mapMethodDescriptorToSubGlobalFlowGraph = new HashMap(); + } public void setupToAnalyze() { SymbolTable classtable = state.getClassSymbolTable(); - toanalyzeList.clear(); - toanalyzeList.addAll(classtable.getValueSet()); + temp_toanalyzeList.clear(); + temp_toanalyzeList.addAll(classtable.getValueSet()); // Collections.sort(toanalyzeList, new Comparator() { // public int compare(ClassDescriptor o1, ClassDescriptor o2) { // return o1.getClassName().compareToIgnoreCase(o2.getClassName()); @@ -172,9 +185,9 @@ public class LocationInference { public void setupToAnalazeMethod(ClassDescriptor cd) { SymbolTable methodtable = cd.getMethodTable(); - toanalyzeMethodList.clear(); - toanalyzeMethodList.addAll(methodtable.getValueSet()); - Collections.sort(toanalyzeMethodList, new Comparator() { + temp_toanalyzeMethodList.clear(); + temp_toanalyzeMethodList.addAll(methodtable.getValueSet()); + Collections.sort(temp_toanalyzeMethodList, new Comparator() { public int compare(MethodDescriptor o1, MethodDescriptor o2) { return o1.getSymbol().compareToIgnoreCase(o2.getSymbol()); } @@ -182,19 +195,19 @@ public class LocationInference { } public boolean toAnalyzeMethodIsEmpty() { - return toanalyzeMethodList.isEmpty(); + return temp_toanalyzeMethodList.isEmpty(); } public boolean toAnalyzeIsEmpty() { - return toanalyzeList.isEmpty(); + return temp_toanalyzeList.isEmpty(); } public ClassDescriptor toAnalyzeNext() { - return toanalyzeList.remove(0); + return temp_toanalyzeList.remove(0); } public MethodDescriptor toAnalyzeMethodNext() { - return toanalyzeMethodList.remove(0); + return temp_toanalyzeMethodList.remove(0); } public void inference() { @@ -202,15 +215,31 @@ public class LocationInference { // 1) construct value flow graph constructFlowGraph(); + 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); @@ -232,13 +261,363 @@ public class LocationInference { } + private void constructGlobalFlowGraph() { + + System.out.println(""); + LinkedList methodDescList = + (LinkedList) toanalyze_methodDescList.clone(); + + System.out.println("@@@methodDescList=" + methodDescList); + // System.exit(0); + + while (!methodDescList.isEmpty()) { + MethodDescriptor md = methodDescList.removeLast(); + if (state.SSJAVADEBUG) { + System.out.println(); + System.out.println("SSJAVA: Constructing a global flow graph: " + md); + + FlowGraph flowGraph = getFlowGraph(md); + FlowGraph subGlobalFlowGraph = flowGraph.clone(); + mapMethodDescriptorToSubGlobalFlowGraph.put(md, subGlobalFlowGraph); + + addValueFlowsFromCalleeSubGlobalFlowGraph(md, subGlobalFlowGraph); + + try { + subGlobalFlowGraph.writeGraph("_SUBGLOBAL"); + } catch (IOException e) { + e.printStackTrace(); + } + // FlowGraph fg = new FlowGraph(md, mapParamDescToIdx); + // mapMethodDescriptorToFlowGraph.put(md, fg); + // analyzeMethodBody(md.getClassDesc(), md); + } + + } + // _debug_printGraph(); + + } + + private void addValueFlowsFromCalleeSubGlobalFlowGraph(MethodDescriptor mdCaller, + FlowGraph subGlobalFlowGraph) { + + // the transformation for a call site propagates flows through parameters + // if the method is virtual, it also grab all relations from any possible + // callees + + Set setMethodInvokeNode = getMethodInvokeNodeSet(mdCaller); + + for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) { + MethodInvokeNode min = (MethodInvokeNode) iterator.next(); + MethodDescriptor mdCallee = min.getMethod(); + Set setPossibleCallees = new HashSet(); + if (mdCallee.isStatic()) { + setPossibleCallees.add(mdCallee); + } else { + Set calleeSet = ssjava.getCallGraph().getMethods(mdCallee); + // removes method descriptors that are not invoked by the caller + calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller)); + setPossibleCallees.addAll(calleeSet); + } + + for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) { + MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next(); + propagateValueFlowsToCallerFromSubGlobalFlowGraph(min, mdCaller, possibleMdCallee); + // propagateFlowsToCallerWithNoCompositeLocation(min, mdCaller, possibleMdCallee); + } + + } + + } + + private void propagateValueFlowsToCallerFromSubGlobalFlowGraph(MethodInvokeNode min, + MethodDescriptor mdCaller, MethodDescriptor possibleMdCallee) { + + NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); + + FlowGraph callerSubGlobalGraph = getSubGlobalFlowGraph(mdCaller); + FlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(possibleMdCallee); + + int numParam = calleeSubGlobalGraph.getNumParameters(); + for (int idx = 0; idx < numParam; idx++) { + FlowNode paramNode = calleeSubGlobalGraph.getParamFlowNode(idx); + 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 addValueFlowsFromCalleeParam(MethodInvokeNode min, FlowGraph calleeSubGlobalGraph, + FlowNode paramNode, FlowGraph callerSubGlobalGraph, NTuple argTuple, + NTuple baseTuple) { + + Set visited = new HashSet(); + + visited.add(paramNode); + recurAddValueFlowsFromCalleeParam(min, calleeSubGlobalGraph, paramNode, callerSubGlobalGraph, + argTuple, visited, baseTuple); + } + + 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; + } + + private NTuple translateToCaller(NTuple dstDescTuple, + NTuple baseTuple) { + NTuple callerDescTuple = new NTuple(); + + callerDescTuple.addAll(baseTuple); + for (int i = 1; i < dstDescTuple.size(); i++) { + callerDescTuple.add(dstDescTuple.get(i)); + } + + return callerDescTuple; + } + + public LocationSummary getLocationSummary(Descriptor d) { + if (!mapDescToLocationSummary.containsKey(d)) { + if (d instanceof MethodDescriptor) { + mapDescToLocationSummary.put(d, new MethodSummary((MethodDescriptor) d)); + } else if (d instanceof ClassDescriptor) { + mapDescToLocationSummary.put(d, new FieldSummary()); + } + } + return mapDescToLocationSummary.get(d); + } + + private void generateMethodSummary() { + + Set keySet = md2lattice.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + MethodDescriptor md = (MethodDescriptor) iterator.next(); + + System.out.println("\nSSJAVA: generate method summary: " + md); + + FlowGraph flowGraph = getFlowGraph(md); + MethodSummary methodSummary = getMethodSummary(md); + + // construct a parameter mapping that maps a parameter descriptor to an inferred composite + // location + + for (int paramIdx = 0; paramIdx < flowGraph.getNumParameters(); paramIdx++) { + FlowNode flowNode = flowGraph.getParamFlowNode(paramIdx); + NTuple descTuple = flowNode.getDescTuple(); + + CompositeLocation assignedCompLoc = flowNode.getCompositeLocation(); + CompositeLocation inferredCompLoc; + if (assignedCompLoc != null) { + inferredCompLoc = translateCompositeLocation(assignedCompLoc); + } else { + Descriptor locDesc = descTuple.get(0); + Location loc = new Location(md, locDesc.getSymbol()); + loc.setLocDescriptor(locDesc); + inferredCompLoc = new CompositeLocation(loc); + } + System.out.println("-paramIdx=" + paramIdx + " infer=" + inferredCompLoc); + methodSummary.addMapParamIdxToInferLoc(paramIdx, inferredCompLoc); + } + + } + + } + + private CompositeLocation translateCompositeLocation(CompositeLocation compLoc) { + CompositeLocation newCompLoc = new CompositeLocation(); + + // System.out.println("compLoc=" + compLoc); + for (int i = 0; i < compLoc.getSize(); i++) { + Location loc = compLoc.get(i); + Descriptor enclosingDescriptor = loc.getDescriptor(); + Descriptor locDescriptor = loc.getLocDescriptor(); + + HNode hnode = getHierarchyGraph(enclosingDescriptor).getHNode(locDescriptor); + // System.out.println("-hnode=" + hnode + " from=" + locDescriptor + + // " enclosingDescriptor=" + // + enclosingDescriptor); + // System.out.println("-getLocationSummary(enclosingDescriptor)=" + // + getLocationSummary(enclosingDescriptor)); + String locName = getLocationSummary(enclosingDescriptor).getLocationName(hnode.getName()); + // System.out.println("-locName=" + locName); + Location newLoc = new Location(enclosingDescriptor, locName); + newLoc.setLocDescriptor(locDescriptor); + newCompLoc.addLocation(newLoc); + } + + return newCompLoc; + } + + private void debug_writeLattices() { + + Set keySet = mapDescriptorToSimpleLattice.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Descriptor key = (Descriptor) iterator.next(); + SSJavaLattice simpleLattice = mapDescriptorToSimpleLattice.get(key); + // HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(key); + HierarchyGraph scHierarchyGraph = getSkeletonCombinationHierarchyGraph(key); + if (key instanceof ClassDescriptor) { + 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 +631,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 +647,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 +706,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 +744,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 +787,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 +804,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 +857,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) { @@ -1258,7 +1668,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(); @@ -1586,38 +1996,109 @@ public class LocationInference { } - private void propagateFlowsFromCallee(MethodInvokeNode min, MethodDescriptor mdCaller, + // private void propagateFlowsFromCallee(MethodInvokeNode min, MethodDescriptor mdCaller, + // MethodDescriptor mdCallee) { + // + // // the transformation for a call site propagates all relations between + // // parameters from the callee + // // if the method is virtual, it also grab all relations from any possible + // // callees + // + // Set setPossibleCallees = new HashSet(); + // if (mdCallee.isStatic()) { + // setPossibleCallees.add(mdCallee); + // } else { + // Set calleeSet = ssjava.getCallGraph().getMethods(mdCallee); + // // removes method descriptors that are not invoked by the caller + // calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller)); + // setPossibleCallees.addAll(calleeSet); + // } + // + // for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) { + // MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next(); + // propagateFlowsToCaller(min, mdCaller, possibleMdCallee); + // } + // + // } + + private void contributeCalleeFlows(MethodInvokeNode min, MethodDescriptor mdCaller, MethodDescriptor mdCallee) { - // the transformation for a call site propagates all relations between - // parameters from the callee - // if the method is virtual, it also grab all relations from any possible - // callees + System.out.println("\n##contributeCalleeFlows callee=" + mdCallee + "TO caller=" + mdCaller); - Set setPossibleCallees = new HashSet(); - if (mdCallee.isStatic()) { - setPossibleCallees.add(mdCallee); - } else { - Set calleeSet = ssjava.getCallGraph().getMethods(mdCallee); - // removes method descriptors that are not invoked by the caller - calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller)); - setPossibleCallees.addAll(calleeSet); - } + getSubGlobalFlowGraph(mdCallee); - for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) { - MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next(); - propagateFlowsToCaller(min, mdCaller, possibleMdCallee); + } + + private FlowGraph getSubGlobalFlowGraph(MethodDescriptor md) { + return mapMethodDescriptorToSubGlobalFlowGraph.get(md); + } + + private void propagateFlowsToCallerWithNoCompositeLocation(MethodInvokeNode min, + MethodDescriptor mdCaller, MethodDescriptor mdCallee) { + + System.out.println("\n##PROPAGATE callee=" + mdCallee + "TO caller=" + mdCaller); + + // if the parameter A reaches to the parameter B + // then, add an edge the argument A -> the argument B to the caller's flow + // graph + + FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); + FlowGraph callerFlowGraph = getFlowGraph(mdCaller); + int numParam = calleeFlowGraph.getNumParameters(); + + for (int i = 0; i < numParam; i++) { + for (int k = 0; k < numParam; k++) { + + if (i != k) { + + FlowNode paramNode1 = calleeFlowGraph.getParamFlowNode(i); + FlowNode paramNode2 = calleeFlowGraph.getParamFlowNode(k); + + 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 (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 +2111,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 +2138,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,51 +2150,85 @@ public class LocationInference { NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); Descriptor baseRef = baseTuple.get(baseTuple.size() - 1); + System.out.println("paramNode1.getCurrentDescTuple()=" + + paramNode1.getCurrentDescTuple()); // calculate the prefix of the argument + if (arg2Tuple.size() == 1 && arg2Tuple.get(0).equals(baseRef)) { + // in this case, the callee flow causes a caller flow to the object whose method + // is invoked. if (!paramNode1.getCurrentDescTuple().startsWith(mdCallee.getThis())) { + // check whether ??? NTuple param1Prefix = calculatePrefixForParam(callerFlowGraph, calleeFlowGraph, min, arg1Tuple, paramNode1); if (param1Prefix != null && param1Prefix.startsWith(mdCallee.getThis())) { - // in this case, we need to create a new edge - // 'this.FIELD'->'this' - // but we couldn't... instead we assign the - // corresponding - // parameter a new composite location started with - // 'this' - // reference + // in this case, we need to create a new edge 'this.FIELD'->'this' + // but we couldn't... instead we assign a new composite location started + // with 'this' reference to the corresponding parameter CompositeLocation compLocForParam1 = generateCompositeLocation(mdCallee, param1Prefix); - // System.out.println("set comp loc=" + compLocForParam1 - // + - // " to " + paramNode1); + System.out + .println("set comp loc=" + compLocForParam1 + " to " + paramNode1); paramNode1.setCompositeLocation(compLocForParam1); + + // then, we need to make sure that the corresponding argument in the caller + // is required to be higher than or equal to the translated parameter + // location + + NTuple translatedParamTuple = + translateCompositeLocationToCaller(min, compLocForParam1); + + // TODO : check if the arg >= the tranlated parameter + + System.out.println("add a flow edge= " + arg1Tuple + "->" + + translatedParamTuple); + callerFlowGraph.addValueFlowEdge(arg1Tuple, translatedParamTuple); + continue; + } + + } else { + // param1 has already been assigned a composite location + + System.out.println("--param1 has already been assigned a composite location"); + CompositeLocation compLocForParam1 = paramNode1.getCompositeLocation(); + NTuple translatedParamTuple = + translateCompositeLocationToCaller(min, compLocForParam1); + + // TODO : check if the arg >= the tranlated parameter + + System.out.println("add a flow edge= " + arg1Tuple + "->" + + translatedParamTuple); + callerFlowGraph.addValueFlowEdge(arg1Tuple, translatedParamTuple); + + continue; + } } else if (arg1Tuple.size() == 1 && arg1Tuple.get(0).equals(baseRef)) { + // in this case, the callee flow causes a caller flow originated from the object + // whose + // method is invoked. + + System.out.println("###FROM CASE"); if (!paramNode2.getCurrentDescTuple().startsWith(mdCallee.getThis())) { NTuple param2Prefix = - calculatePrefixForParam(callerFlowGraph, calleeFlowGraph, min, arg1Tuple, - paramNode1); + calculatePrefixForParam(callerFlowGraph, calleeFlowGraph, min, arg2Tuple, + paramNode2); if (param2Prefix != null && param2Prefix.startsWith(mdCallee.getThis())) { // in this case, we need to create a new edge 'this' -> - // 'this.FIELD' - // but we couldn't... instead we assign the - // corresponding - // parameter a new composite location started with - // 'this' - // reference + // 'this.FIELD' but we couldn't... instead we assign the corresponding + // parameter a new composite location started with 'this' reference CompositeLocation compLocForParam2 = generateCompositeLocation(mdCallee, param2Prefix); @@ -1718,33 +2246,66 @@ public class LocationInference { // otherwise, flows between method/field locations... callerFlowGraph.addValueFlowEdge(arg1Tuple, arg2Tuple); - // System.out.println("arg1=" + arg1Tuple + " arg2=" + - // arg2Tuple); + System.out.println("arg1=" + arg1Tuple + " arg2=" + arg2Tuple); } } } + System.out.println(); } } } + System.out.println("##\n"); + } + private NTuple translateCompositeLocationToCaller(MethodInvokeNode min, + CompositeLocation compLocForParam1) { + NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); + + NTuple tuple = new NTuple(); + + for (int i = 0; i < baseTuple.size(); i++) { + tuple.add(baseTuple.get(i)); + } + + for (int i = 1; i < compLocForParam1.getSize(); i++) { + Location loc = compLocForParam1.get(i); + tuple.add(loc.getLocDescriptor()); + } + + return tuple; } private CompositeLocation generateCompositeLocation(MethodDescriptor md, - NTuple param1Prefix) { + NTuple paramPrefix) { + + System.out.println("generateCompositeLocation=" + paramPrefix); + + CompositeLocation newCompLoc = convertToCompositeLocation(md, 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 +2321,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 +2377,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 +2444,7 @@ public class LocationInference { } - System.out.println("convertToCompositeLocation from=" + tuple + " to " + compLoc); + System.out.println("-convertToCompositeLocation from=" + tuple + " to " + compLoc); return compLoc; } @@ -1960,8 +2528,10 @@ public class LocationInference { CompositeLocation param2 = calleeLocInfo.getParamCompositeLocation(k); if (isGreaterThan(getLattice(possibleMdCallee), param1, param2)) { - NodeTupleSet argDescTupleSet1 = getNodeTupleSetByArgIdx(min, i); - NodeTupleSet argDescTupleSet2 = getNodeTupleSetByArgIdx(min, k); + // NodeTupleSet argDescTupleSet1 = getNodeTupleSetByArgIdx(min, i); + // NodeTupleSet argDescTupleSet2 = getNodeTupleSetByArgIdx(min, k); + NodeTupleSet argDescTupleSet1 = null; + NodeTupleSet argDescTupleSet2 = null; // the callee has the relation in which param1 is higher than param2 // therefore, the caller has to have the relation in which arg1 is @@ -2697,7 +3267,7 @@ public class LocationInference { ClassDescriptor cd = toAnalyzeNext(); setupToAnalazeMethod(cd); - toanalyzeMethodList.removeAll(visited); + temp_toanalyzeMethodList.removeAll(visited); while (!toAnalyzeMethodIsEmpty()) { MethodDescriptor md = toAnalyzeMethodNext(); @@ -2720,7 +3290,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 +3313,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,8 +3344,8 @@ public class LocationInference { mapMethodDescriptorToFlowGraph.put(md, fg); analyzeMethodBody(md.getClassDesc(), md); - propagateFlowsFromCallees(md); - assignCompositeLocation(md); + propagateFlowsFromCalleesWithNoCompositeLocation(md); + // assignCompositeLocation(md); } } @@ -2780,6 +3353,49 @@ public class LocationInference { } + private Set getMethodInvokeNodeSet(MethodDescriptor md) { + if (!mapMethodDescriptorToMethodInvokeNodeSet.containsKey(md)) { + mapMethodDescriptorToMethodInvokeNodeSet.put(md, new HashSet()); + } + return mapMethodDescriptorToMethodInvokeNodeSet.get(md); + } + + private void constructSubGlobalFlowGraph(MethodDescriptor md) { + + FlowGraph flowGraph = getFlowGraph(md); + + Set setMethodInvokeNode = getMethodInvokeNodeSet(md); + + for (Iterator iter = setMethodInvokeNode.iterator(); iter.hasNext();) { + MethodInvokeNode min = iter.next(); + propagateFlowsFromMethodInvokeNode(md, min); + } + + } + + private void propagateFlowsFromMethodInvokeNode(MethodDescriptor mdCaller, MethodInvokeNode min) { + // the transformation for a call site propagates flows through parameters + // if the method is virtual, it also grab all relations from any possible + // callees + + MethodDescriptor mdCallee = min.getMethod(); + Set setPossibleCallees = new HashSet(); + if (mdCallee.isStatic()) { + setPossibleCallees.add(mdCallee); + } else { + Set calleeSet = ssjava.getCallGraph().getMethods(mdCallee); + // removes method descriptors that are not invoked by the caller + calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller)); + setPossibleCallees.addAll(calleeSet); + } + + for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) { + MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next(); + contributeCalleeFlows(min, mdCaller, possibleMdCallee); + } + + } + private void assignCompositeLocation(MethodDescriptor md) { FlowGraph flowGraph = getFlowGraph(md); @@ -2821,6 +3437,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 @@ -3352,10 +4002,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,14 +4014,11 @@ 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); for (Iterator iterator2 = inFlowSet.iterator(); iterator2.hasNext();) { FlowNode inFlowNode = (FlowNode) iterator2.next(); @@ -3401,7 +4049,21 @@ public class LocationInference { NodeTupleSet argTupleSet = new NodeTupleSet(); analyzeFlowExpressionNode(md, nametable, en, argTupleSet, false); // if argument is liternal node, argTuple is set to NULL. - addArgIdxMap(min, idx, argTupleSet); + + NTuple argTuple = new NTuple(); + 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 { + argTuple = argTupleSet.iterator().next(); + } + + addArgIdxMap(min, idx, argTuple); FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx); if (hasInFlowTo(calleeFlowGraph, paramNode, calleeReturnSet) || calleeMethodDesc.getModifiers().isNative()) { @@ -3430,48 +4092,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); + 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); } - 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); - } - - } - + mapIdxToTuple.put(new Integer(idx), argTuple); } private void analyzeLiteralNode(MethodDescriptor md, SymbolTable nametable, LiteralNode en) { @@ -3747,11 +4381,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 +4471,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();