X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=Robust%2Fsrc%2FAnalysis%2FSSJava%2FLocationInference.java;h=36645aa1c8ae24ee4cbf0b49f919dc1d3c6a94cb;hb=13a63ea76172e2fd0ce7987bf81845c44c839d55;hp=1294cf85604dc57a6de25f6de0671198f722db13;hpb=78a14d01d4b27a3e6e5f42c3bdb382a708426e96;p=IRC.git diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index 1294cf85..36645aa1 100644 --- a/Robust/src/Analysis/SSJava/LocationInference.java +++ b/Robust/src/Analysis/SSJava/LocationInference.java @@ -1,8 +1,11 @@ package Analysis.SSJava; +import java.io.BufferedReader; +import java.io.BufferedWriter; +import java.io.FileReader; +import java.io.FileWriter; import java.io.IOException; import java.util.ArrayList; -import java.util.Collection; import java.util.Collections; import java.util.Comparator; import java.util.HashMap; @@ -13,6 +16,7 @@ import java.util.List; import java.util.Map; import java.util.Set; import java.util.Stack; +import java.util.Vector; import IR.ClassDescriptor; import IR.Descriptor; @@ -43,6 +47,7 @@ import IR.Tree.NameNode; import IR.Tree.OpNode; import IR.Tree.ReturnNode; import IR.Tree.SubBlockNode; +import IR.Tree.SwitchBlockNode; import IR.Tree.SwitchStatementNode; import IR.Tree.TertiaryNode; import IR.Tree.TreeNode; @@ -53,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; @@ -69,11 +76,27 @@ public class LocationInference { // map a method descriptor to a method lattice private Map> md2lattice; + // map a method/class descriptor to a hierarchy graph + private Map mapDescriptorToHierarchyGraph; + + // map a method/class descriptor to a skeleton hierarchy graph + private Map mapDescriptorToSkeletonHierarchyGraph; + + private Map mapDescriptorToSimpleHierarchyGraph; + + // map a method/class descriptor to a skeleton hierarchy graph with combination nodes + private Map mapDescriptorToCombineSkeletonHierarchyGraph; + + // 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; private Map mapMethodDescToMethodLocationInfo; @@ -81,23 +104,41 @@ public class LocationInference { private Map> mapMethodToCalleeSet; + private Map> mapMethodDescToParamNodeFlowsToReturnValue; + + private Map> mapFileNameToLineVector; + + 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"; + public static final String INTERLOC = "INTERLOC"; + public static final Descriptor GLOBALDESC = new NameDescriptor(GLOBALLOC); public static final Descriptor TOPDESC = new NameDescriptor(TOPLOC); + public static String newline = System.getProperty("line.separator"); + LocationInfo curMethodInfo; boolean debug = true; + private static int locSeed = 0; + 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>(); @@ -105,29 +146,48 @@ 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(); + + this.mapFileNameToLineVector = new HashMap>(); + this.mapDescToDefinitionLine = new HashMap(); + this.mapMethodDescToParamNodeFlowsToReturnValue = + new HashMap>(); + + this.mapDescriptorToHierarchyGraph = 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()); - Collections.sort(toanalyzeList, new Comparator() { - public int compare(ClassDescriptor o1, ClassDescriptor o2) { - return o1.getClassName().compareToIgnoreCase(o2.getClassName()); - } - }); + 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()); + // } + // }); } 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()); } @@ -135,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() { @@ -155,306 +215,725 @@ public class LocationInference { // 1) construct value flow graph constructFlowGraph(); + constructGlobalFlowGraph(); + + System.exit(0); + + constructHierarchyGraph(); + + debug_writeHierarchyDotFiles(); + + simplifyHierarchyGraph(); + + debug_writeSimpleHierarchyDotFiles(); + + constructSkeletonHierarchyGraph(); + + debug_writeSkeletonHierarchyDotFiles(); + + insertCombinationNodes(); + + debug_writeSkeletonCombinationHierarchyDotFiles(); + + buildLattice(); + + debug_writeLattices(); + + generateMethodSummary(); + + System.exit(0); + // 2) construct lattices inferLattices(); simplifyLattices(); - debug_writeLatticeDotFile(); - // 3) check properties checkLattices(); + // calculate RETURNLOC,PCLOC + calculateExtraLocations(); + + debug_writeLatticeDotFile(); + + // 4) generate annotated source codes + generateAnnoatedCode(); + } - private void simplifyLattices() { + private void constructGlobalFlowGraph() { - // generate lattice dot file - setupToAnalyze(); + System.out.println(""); + LinkedList methodDescList = + (LinkedList) toanalyze_methodDescList.clone(); - while (!toAnalyzeIsEmpty()) { - ClassDescriptor cd = toAnalyzeNext(); + System.out.println("@@@methodDescList=" + methodDescList); + // System.exit(0); - setupToAnalazeMethod(cd); + while (!methodDescList.isEmpty()) { + MethodDescriptor md = methodDescList.removeLast(); + if (state.SSJAVADEBUG) { + System.out.println(); + System.out.println("SSJAVA: Constructing a global flow graph: " + md); - SSJavaLattice classLattice = cd2lattice.get(cd); - if (classLattice != null) { - classLattice.removeRedundantEdges(); - } + FlowGraph flowGraph = getFlowGraph(md); + FlowGraph subGlobalFlowGraph = flowGraph.clone(); + mapMethodDescriptorToSubGlobalFlowGraph.put(md, subGlobalFlowGraph); - while (!toAnalyzeMethodIsEmpty()) { - MethodDescriptor md = toAnalyzeMethodNext(); - if (ssjava.needTobeAnnotated(md)) { - SSJavaLattice methodLattice = md2lattice.get(md); - if (methodLattice != null) { - methodLattice.removeRedundantEdges(); - } + 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 checkLattices() { + private void assignCompositeLocation(FlowGraph globalFlowGraph) { + Set nodeSet = globalFlowGraph.getNodeSet(); - LinkedList descriptorListToAnalyze = ssjava.getSortedDescriptors(); + for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + FlowNode flowNode = (FlowNode) iterator.next(); + Set inNodeSet = globalFlowGraph.getIncomingFlowNodeSet(flowNode); + Set reachableNodeSet = globalFlowGraph.getReachFlowNodeSetFrom(flowNode); - // current descriptors to visit in fixed-point interprocedural analysis, - // prioritized by - // dependency in the call graph - methodDescriptorsToVisitStack.clear(); + // System.out.println("flowNode=" + flowNode + " incoming=" + inNodeSet); + // System.out.println("reachableNodeSet=" + reachableNodeSet); - descriptorListToAnalyze.removeFirst(); + Map, Set>> mapPrefixToIncomingLocTupleSet = + new HashMap, Set>>(); - Set methodDescriptorToVistSet = new HashSet(); - methodDescriptorToVistSet.addAll(descriptorListToAnalyze); + List> prefixList = new ArrayList>(); - while (!descriptorListToAnalyze.isEmpty()) { - MethodDescriptor md = descriptorListToAnalyze.removeFirst(); - checkLatticesOfVirtualMethods(md); - } + for (Iterator iterator2 = inNodeSet.iterator(); iterator2.hasNext();) { + FlowNode inNode = (FlowNode) iterator2.next(); - } + NTuple inNodeTuple = inNode.getCurrentDescTuple(); - private void debug_writeLatticeDotFile() { - // generate lattice dot file + // CompositeLocation inNodeInferredLoc = + // generateInferredCompositeLocation(methodInfo, inNodeTuple); + // NTuple inNodeInferredLocTuple = inNodeInferredLoc.getTuple(); - setupToAnalyze(); + for (int i = 1; i < inNodeTuple.size(); i++) { + NTuple prefix = inNodeTuple.subList(0, i); + if (!prefixList.contains(prefix)) { + prefixList.add(prefix); + } + } + } - while (!toAnalyzeIsEmpty()) { - ClassDescriptor cd = toAnalyzeNext(); + 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; + } + } + }); + + // 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 = reachableNode.getCurrentDescTuple(); + if (reachLocTuple.startsWith(curPrefix)) { + reachableCommonPrefixSet.add(reachLocTuple); + } + } - setupToAnalazeMethod(cd); + if (!reachableCommonPrefixSet.isEmpty()) { + // found reachable nodes that start with the prefix curPrefix + // need to assign a composite location + // System.out.println("-prefixList=" + prefixList); + // System.out.println("-reachableCommonPrefixSet=" + reachableCommonPrefixSet); + // System.out.println("-curPrefix=" + curPrefix); - SSJavaLattice classLattice = cd2lattice.get(cd); - if (classLattice != null) { - ssjava.writeLatticeDotFile(cd, null, classLattice); - debug_printDescriptorToLocNameMapping(cd); - } + // first, check if there are more than one the set of locations that has + // the same length of the longest reachable prefix, no way to assign + // a composite location to the input local var + prefixSanityCheck(prefixList, i, globalFlowGraph, reachableNodeSet); - while (!toAnalyzeMethodIsEmpty()) { - MethodDescriptor md = toAnalyzeMethodNext(); - if (ssjava.needTobeAnnotated(md)) { - SSJavaLattice methodLattice = md2lattice.get(md); - if (methodLattice != null) { - ssjava.writeLatticeDotFile(cd, md, methodLattice); - debug_printDescriptorToLocNameMapping(md); - } + MethodDescriptor topMethodDesc = globalFlowGraph.getMethodDescriptor(); + CompositeLocation newCompLoc = generateCompositeLocation(curPrefix, topMethodDesc); + + System.out.println("SET COMPOSITE LOCATION=" + newCompLoc + " to " + flowNode); + flowNode.setCompositeLocation(newCompLoc); } } + } } - private void debug_printDescriptorToLocNameMapping(Descriptor desc) { + private CompositeLocation generateCompositeLocation(NTuple curPrefix, + MethodDescriptor md) { + CompositeLocation newCompLoc = new CompositeLocation(); + + Descriptor enclosingDesc = md; + for (int i = 0; i < curPrefix.size(); i++) { + Descriptor curDesc = curPrefix.get(i); + Location loc = new Location(enclosingDesc, curDesc.getSymbol()); + newCompLoc.addLocation(loc); + if (i == 0) { + VarDescriptor varDesc = (VarDescriptor) curDesc; + enclosingDesc = varDesc.getType().getClassDesc(); + } else { + FieldDescriptor fieldDesc = (FieldDescriptor) curDesc; + enclosingDesc = fieldDesc.getType().getClassDesc(); + } + } - LocationInfo info = getLocationInfo(desc); - System.out.println("## " + desc + " ##"); - System.out.println(info.getMapDescToInferLocation()); - LocationInfo locInfo = getLocationInfo(desc); - System.out.println("mapping=" + locInfo.getMapLocSymbolToDescSet()); - System.out.println("###################"); + LocationDescriptor newLocDescriptor = generateNewLocationDescriptor(); + newLocDescriptor.setEnclosingClassDesc((ClassDescriptor) enclosingDesc); + + Location newLoc = new Location(enclosingDesc, newLocDescriptor.getSymbol()); + newLoc.setLocDescriptor(newLocDescriptor); + newCompLoc.addLocation(newLoc); + return newCompLoc; } - private void inferLattices() { + private void prefixSanityCheck(List> prefixList, int curIdx, + FlowGraph globalFlowGraph, Set reachableNodeSet) { - // do fixed-point analysis + NTuple curPrefix = prefixList.get(curIdx); - LinkedList descriptorListToAnalyze = ssjava.getSortedDescriptors(); + for (int i = curIdx + 1; i < prefixList.size(); i++) { + NTuple prefixTuple = prefixList.get(i); - Collections.sort(descriptorListToAnalyze, new Comparator() { - public int compare(MethodDescriptor o1, MethodDescriptor o2) { - return o1.getSymbol().compareToIgnoreCase(o2.getSymbol()); + if (curPrefix.startsWith(prefixTuple)) { + continue; } - }); - - // 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); + for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) { + FlowNode reachableNode = (FlowNode) iterator2.next(); + NTuple reachLocTuple = reachableNode.getCurrentDescTuple(); + if (reachLocTuple.startsWith(prefixTuple)) { + throw new Error( + "Failed to generate a composite location because there is more than one prefix which is reach to the current node."); + } + } } - // 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); + private void addValueFlowsFromCalleeSubGlobalFlowGraph(MethodDescriptor mdCaller, + FlowGraph subGlobalFlowGraph) { - MethodLocationInfo methodInfo = new MethodLocationInfo(md); - curMethodInfo = methodInfo; + // the transformation for a call site propagates flows through parameters + // if the method is virtual, it also grab all relations from any possible + // callees - System.out.println(); - System.out.println("SSJAVA: Inferencing the lattice from " + md); + Set setMethodInvokeNode = getMethodInvokeNodeSet(mdCaller); - try { - analyzeMethodLattice(md, methodLattice, methodInfo); - } catch (CyclicFlowException e) { - throw new Error("Fail to generate the method lattice for " + md); + for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) { + MethodInvokeNode min = (MethodInvokeNode) iterator.next(); + MethodDescriptor mdCallee = min.getMethod(); + Set setPossibleCallees = new HashSet(); + if (mdCallee.isStatic()) { + setPossibleCallees.add(mdCallee); + } else { + Set calleeSet = ssjava.getCallGraph().getMethods(mdCallee); + // removes method descriptors that are not invoked by the caller + calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller)); + setPossibleCallees.addAll(calleeSet); } - SSJavaLattice prevMethodLattice = getMethodLattice(md); - MethodLocationInfo prevMethodInfo = getMethodLocationInfo(md); + for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) { + MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next(); + propagateValueFlowsToCallerFromSubGlobalFlowGraph(min, mdCaller, possibleMdCallee); + // propagateFlowsToCallerWithNoCompositeLocation(min, mdCaller, possibleMdCallee); + } - 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 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 setMethodLocInfo(MethodDescriptor md, MethodLocationInfo methodInfo) { - mapMethodDescToMethodLocationInfo.put(md, methodInfo); } - private void checkLatticesOfVirtualMethods(MethodDescriptor md) { + private void addValueFlowsFromCalleeParam(MethodInvokeNode min, FlowGraph calleeSubGlobalGraph, + FlowNode paramNode, FlowGraph callerSubGlobalGraph, NTuple argTuple, + NTuple baseTuple) { - if (!md.isStatic()) { - Set setPossibleCallees = new HashSet(); - setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md)); + Set visited = new HashSet(); - for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) { - MethodDescriptor mdCallee = (MethodDescriptor) iterator.next(); - if (!md.equals(mdCallee)) { - checkConsistency(md, mdCallee); - } - } + 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(); - private void checkConsistency(MethodDescriptor md1, MethodDescriptor md2) { + // Set edgeSet = calleeSubGlobalGraph.getOutEdgeSet(calleeSrcNode); + Set edgeSet = calleeSubGlobalGraph.getOutEdgeSetStartingFrom(calleeSrcNode); + for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) { + FlowEdge flowEdge = (FlowEdge) iterator.next(); - // check that two lattice have the same relations between parameters(+PC - // LOC, GLOBAL_LOC RETURN LOC) + NTuple srcDescTuple = flowEdge.getInitTuple(); + NTuple dstDescTuple = flowEdge.getEndTuple(); - List list1 = new ArrayList(); - List list2 = new ArrayList(); + FlowNode dstNode = calleeSubGlobalGraph.getFlowNode(dstDescTuple); - MethodLocationInfo locInfo1 = getMethodLocationInfo(md1); - MethodLocationInfo locInfo2 = getMethodLocationInfo(md2); + 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); + } - Map paramMap1 = locInfo1.getMapParamIdxToInferLoc(); - Map paramMap2 = locInfo2.getMapParamIdxToInferLoc(); + 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); + } - int numParam = locInfo1.getMapParamIdxToInferLoc().keySet().size(); + callerSubGlobalGraph.addValueFlowEdge(srcDescTuple, dstDescTuple); + + if (!visited.contains(dstNode)) { + visited.add(dstNode); + recurAddValueFlowsFromCalleeParam(min, calleeSubGlobalGraph, dstNode, callerSubGlobalGraph, + dstDescTuple, visited, baseTuple); + } - // add location types of paramters - for (int idx = 0; idx < numParam; idx++) { - list1.add(paramMap1.get(Integer.valueOf(idx))); - list2.add(paramMap2.get(Integer.valueOf(idx))); } - // add program counter location - list1.add(locInfo1.getPCLoc()); - list2.add(locInfo2.getPCLoc()); + } - if (!md1.getReturnType().isVoid()) { - // add return value location - CompositeLocation rtrLoc1 = - new CompositeLocation(new Location(md1, locInfo1.getReturnLocName())); - CompositeLocation rtrLoc2 = - new CompositeLocation(new Location(md2, locInfo2.getReturnLocName())); - list1.add(rtrLoc1); - list2.add(rtrLoc2); + 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)); } - // add global location type - if (md1.isStatic()) { - CompositeLocation globalLoc1 = - new CompositeLocation(new Location(md1, locInfo1.getGlobalLocName())); - CompositeLocation globalLoc2 = - new CompositeLocation(new Location(md2, locInfo2.getGlobalLocName())); - list1.add(globalLoc1); - list2.add(globalLoc2); + for (int i = 1; i < srcDescTuple.size(); i++) { + callerTuple.add(srcDescTuple.get(i)); } - for (int i = 0; i < list1.size(); i++) { - CompositeLocation locA1 = list1.get(i); - CompositeLocation locA2 = list2.get(i); - for (int k = 0; k < list1.size(); k++) { - if (i != k) { - CompositeLocation locB1 = list1.get(k); - CompositeLocation locB2 = list2.get(k); - boolean r1 = isGreaterThan(getLattice(md1), locA1, locB1); + return callerTuple; + } - boolean r2 = isGreaterThan(getLattice(md1), locA2, locB2); + private NTuple translateToCaller(NTuple dstDescTuple, + NTuple baseTuple) { + NTuple callerDescTuple = new NTuple(); - if (r1 != r2) { - throw new Error("The method " + md1 + " is not consistent with the method " + md2 - + ".:: They have a different ordering relation between locations (" + locA1 + "," - + locB1 + ") and (" + locA2 + "," + locB2 + ")."); - } - } - } + callerDescTuple.addAll(baseTuple); + for (int i = 1; i < dstDescTuple.size(); i++) { + callerDescTuple.add(dstDescTuple.get(i)); } + return callerDescTuple; } - private String getSymbol(int idx, FlowNode node) { - Descriptor desc = node.getDescTuple().get(idx); - return desc.getSymbol(); + 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 Descriptor getDescriptor(int idx, FlowNode node) { - Descriptor desc = node.getDescTuple().get(idx); - return desc; + 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 locTuple = flowNode.getLocTuple(); + + CompositeLocation assignedCompLoc = flowNode.getCompositeLocation(); + CompositeLocation inferredCompLoc; + if (assignedCompLoc != null) { + inferredCompLoc = translateCompositeLocation(assignedCompLoc); + } else { + Location loc = locTuple.get(0); + inferredCompLoc = new CompositeLocation(loc); + } + System.out.println("-paramIdx=" + paramIdx + " infer=" + inferredCompLoc); + methodSummary.addMapParamIdxToInferLoc(paramIdx, inferredCompLoc); + } + + } + } - private void analyzeMethodLattice(MethodDescriptor md, SSJavaLattice methodLattice, - MethodLocationInfo methodInfo) throws CyclicFlowException { + 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); + } - // first take a look at method invocation nodes to newly added relations - // from the callee - analyzeLatticeMethodInvocationNode(md, methodLattice, methodInfo); + return newCompLoc; + } - if (!md.isStatic()) { - // set the this location - String thisLocSymbol = md.getThis().getSymbol(); - methodInfo.setThisLocName(thisLocSymbol); + 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 the global location - methodInfo.setGlobalLocName(LocationInference.GLOBALLOC); - methodInfo.mapDescriptorToLocation(GLOBALDESC, new CompositeLocation( - new Location(md, GLOBALLOC))); + 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.removeRedundantEdges(); + // simpleHierarchyGraph.simplifyHierarchyGraph(); + mapDescriptorToSimpleHierarchyGraph.put(desc, simpleHierarchyGraph); + } + } + + private void insertCombinationNodes() { + Set keySet = mapDescriptorToSkeletonHierarchyGraph.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Descriptor desc = (Descriptor) iterator.next(); + 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); + } + } + + private void constructSkeletonHierarchyGraph() { + Set keySet = mapDescriptorToHierarchyGraph.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Descriptor desc = (Descriptor) iterator.next(); + HierarchyGraph simpleGraph = getSimpleHierarchyGraph(desc); + 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_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(); + } + + } + + public HierarchyGraph getSimpleHierarchyGraph(Descriptor d) { + return mapDescriptorToSimpleHierarchyGraph.get(d); + } + + private HierarchyGraph getSkeletonHierarchyGraph(Descriptor d) { + if (!mapDescriptorToSkeletonHierarchyGraph.containsKey(d)) { + mapDescriptorToSkeletonHierarchyGraph.put(d, new HierarchyGraph(d)); + } + return mapDescriptorToSkeletonHierarchyGraph.get(d); + } + + public HierarchyGraph getSkeletonCombinationHierarchyGraph(Descriptor d) { + if (!mapDescriptorToCombineSkeletonHierarchyGraph.containsKey(d)) { + mapDescriptorToCombineSkeletonHierarchyGraph.put(d, new HierarchyGraph(d)); + } + return mapDescriptorToCombineSkeletonHierarchyGraph.get(d); + } + + private void constructHierarchyGraph() { + + // 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(); + + 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(); + + HierarchyGraph hierarchyGraph = new HierarchyGraph(md); + // MethodSummary methodSummary = new MethodSummary(md); + + // MethodLocationInfo methodInfo = new MethodLocationInfo(md); + // curMethodInfo = methodInfo; + + System.out.println(); + System.out.println("SSJAVA: Construcing the hierarchy graph from " + md); + + constructHierarchyGraph(md, hierarchyGraph); + + HierarchyGraph prevHierarchyGraph = getHierarchyGraph(md); + // MethodSummary prevMethodSummary = getMethodSummary(md); + + if (!hierarchyGraph.equals(prevHierarchyGraph)) { + + mapDescriptorToHierarchyGraph.put(md, hierarchyGraph); + // mapDescToLocationSummary.put(md, methodSummary); + + // 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 HierarchyGraph getHierarchyGraph(Descriptor d) { + if (!mapDescriptorToHierarchyGraph.containsKey(d)) { + mapDescriptorToHierarchyGraph.put(d, new HierarchyGraph(d)); + } + return mapDescriptorToHierarchyGraph.get(d); + } + + private void constructHierarchyGraph(MethodDescriptor md, HierarchyGraph methodGraph) { // visit each node of method flow graph FlowGraph fg = getFlowGraph(md); Set nodeSet = fg.getNodeSet(); + Set paramDescSet = fg.getMapParamDescToIdx().keySet(); + for (Iterator iterator = paramDescSet.iterator(); iterator.hasNext();) { + Descriptor desc = (Descriptor) iterator.next(); + methodGraph.getHNode(desc).setSkeleton(true); + } + // 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(); + Set outEdgeSet = fg.getOutEdgeSet(srcNode); for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) { FlowEdge outEdge = (FlowEdge) iterator2.next(); FlowNode dstNode = outEdge.getDst(); @@ -465,157 +944,1664 @@ public class LocationInference { if (outEdge.getInitTuple().equals(srcNodeTuple) && outEdge.getEndTuple().equals(dstNodeTuple)) { - if ((srcNodeTuple.size() > 1 && dstNodeTuple.size() > 1) - && srcNodeTuple.get(0).equals(dstNodeTuple.get(0))) { + NTuple srcCurTuple = srcNode.getCurrentDescTuple(); + NTuple dstCurTuple = dstNode.getCurrentDescTuple(); + + if ((srcCurTuple.size() > 1 && dstCurTuple.size() > 1) + && srcCurTuple.get(0).equals(dstCurTuple.get(0))) { // value flows between fields - Descriptor desc = srcNodeTuple.get(0); + Descriptor desc = srcCurTuple.get(0); ClassDescriptor classDesc; if (desc.equals(GLOBALDESC)) { classDesc = md.getClassDesc(); } else { - VarDescriptor varDesc = (VarDescriptor) srcNodeTuple.get(0); + VarDescriptor varDesc = (VarDescriptor) srcCurTuple.get(0); classDesc = varDesc.getType().getClassDesc(); } - extractRelationFromFieldFlows(classDesc, srcNode, dstNode, 1); + extractFlowsBetweenFields(classDesc, srcNode, dstNode, 1); } else { // value flow between local var - local var or local var - field - addRelationToLattice(md, methodLattice, methodInfo, srcNode, dstNode); - } - // else if (srcNodeTuple.size() == 1 || dstNodeTuple.size() == 1) { - // // for the method lattice, we need to look at the first element of - // // NTuple - // // in this case, take a look at connected nodes at the local level - // addRelationToLattice(md, methodLattice, methodInfo, srcNode, - // dstNode); - // } else { - // if - // (!srcNode.getDescTuple().get(0).equals(dstNode.getDescTuple().get(0))) - // { - // // in this case, take a look at connected nodes at the local level - // addRelationToLattice(md, methodLattice, methodInfo, srcNode, - // dstNode); - // } else { - // Descriptor srcDesc = srcNode.getDescTuple().get(0); - // Descriptor dstDesc = dstNode.getDescTuple().get(0); - // recursivelyAddCompositeRelation(md, fg, methodInfo, srcNode, - // dstNode, srcDesc, - // dstDesc); - // // recursiveAddRelationToLattice(1, md, srcNode, dstNode); - // } - // } + Descriptor srcDesc = srcCurTuple.get(0); + Descriptor dstDesc = dstCurTuple.get(0); + + methodGraph.addEdge(srcDesc, dstDesc); + + if (fg.isParamDesc(srcDesc)) { + methodGraph.setParamHNode(srcDesc); + } + if (fg.isParamDesc(dstDesc)) { + methodGraph.setParamHNode(dstDesc); + } + + } } } } - // 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; + private MethodSummary getMethodSummary(MethodDescriptor md) { + if (!mapDescToLocationSummary.containsKey(md)) { + mapDescToLocationSummary.put(md, new MethodSummary(md)); } + return (MethodSummary) mapDescToLocationSummary.get(md); + } - 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 addMapClassDefinitionToLineNum(ClassDescriptor cd, String strLine, int lineNum) { + + String classSymbol = cd.getSymbol(); + int idx = classSymbol.lastIndexOf("$"); + if (idx != -1) { + classSymbol = classSymbol.substring(idx + 1); } - // calculate the initial program counter location - // PC location is higher than location types of all parameters - String pcLocSymbol = "PCLOC"; - Map mapParamToLoc = methodInfo.getMapParamIdxToInferLoc(); - Set keySet = mapParamToLoc.keySet(); + String pattern = "class " + classSymbol + " "; + if (strLine.indexOf(pattern) != -1) { + mapDescToDefinitionLine.put(cd, lineNum); + } + } + + private void addMapMethodDefinitionToLineNum(Set methodSet, String strLine, + int lineNum) { + for (Iterator iterator = methodSet.iterator(); iterator.hasNext();) { + MethodDescriptor md = (MethodDescriptor) iterator.next(); + String pattern = md.getMethodDeclaration(); + if (strLine.indexOf(pattern) != -1) { + mapDescToDefinitionLine.put(md, lineNum); + methodSet.remove(md); + return; + } + } + + } + + private void readOriginalSourceFiles() { + + SymbolTable classtable = state.getClassSymbolTable(); + + Set classDescSet = new HashSet(); + classDescSet.addAll(classtable.getValueSet()); + + try { + // inefficient implement. it may re-visit the same file if the file + // contains more than one class definitions. + for (Iterator iterator = classDescSet.iterator(); iterator.hasNext();) { + ClassDescriptor cd = (ClassDescriptor) iterator.next(); + + Set methodSet = new HashSet(); + methodSet.addAll(cd.getMethodTable().getValueSet()); + + String sourceFileName = cd.getSourceFileName(); + Vector lineVec = new Vector(); + + mapFileNameToLineVector.put(sourceFileName, lineVec); + + BufferedReader in = new BufferedReader(new FileReader(sourceFileName)); + String strLine; + int lineNum = 1; + lineVec.add(""); // the index is started from 1. + while ((strLine = in.readLine()) != null) { + lineVec.add(lineNum, strLine); + addMapClassDefinitionToLineNum(cd, strLine, lineNum); + addMapMethodDefinitionToLineNum(methodSet, strLine, lineNum); + lineNum++; + } + + } + + } catch (IOException e) { + e.printStackTrace(); + } + + } + + private String generateLatticeDefinition(Descriptor desc) { + + Set sharedLocSet = new HashSet(); + + SSJavaLattice lattice = getLattice(desc); + String rtr = "@LATTICE(\""; + + Map> map = lattice.getTable(); + Set keySet = map.keySet(); + boolean first = true; for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { - Integer paramIdx = (Integer) iterator.next(); - CompositeLocation inferLoc = mapParamToLoc.get(paramIdx); - String paramLocLocalSymbol = inferLoc.get(0).getLocIdentifier(); - if (!methodLattice.isGreaterThan(pcLocSymbol, paramLocLocalSymbol)) { - addRelationHigherToLower(methodLattice, methodInfo, pcLocSymbol, paramLocLocalSymbol); + String key = (String) iterator.next(); + if (!key.equals(lattice.getTopItem())) { + Set connectedSet = map.get(key); + + if (connectedSet.size() == 1) { + if (connectedSet.iterator().next().equals(lattice.getBottomItem())) { + if (!first) { + rtr += ","; + } else { + rtr += "LOC,"; + first = false; + } + rtr += key; + if (lattice.isSharedLoc(key)) { + rtr += "," + key + "*"; + } + } + } + + for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) { + String loc = (String) iterator2.next(); + if (!loc.equals(lattice.getBottomItem())) { + if (!first) { + rtr += ","; + } else { + rtr += "LOC,"; + first = false; + } + rtr += loc + "<" + key; + if (lattice.isSharedLoc(key) && (!sharedLocSet.contains(key))) { + rtr += "," + key + "*"; + sharedLocSet.add(key); + } + if (lattice.isSharedLoc(loc) && (!sharedLocSet.contains(loc))) { + rtr += "," + loc + "*"; + sharedLocSet.add(loc); + } + + } + } + } + } + + rtr += "\")"; + + if (desc instanceof MethodDescriptor) { + TypeDescriptor returnType = ((MethodDescriptor) desc).getReturnType(); + + MethodLocationInfo methodLocInfo = getMethodLocationInfo((MethodDescriptor) desc); + + if (returnType != null && (!returnType.isVoid())) { + rtr += + "\n@RETURNLOC(\"" + generateLocationAnnoatation(methodLocInfo.getReturnLoc()) + "\")"; + } + + rtr += "\n@THISLOC(\"this\")"; + rtr += "\n@GLOBALLOC(\"GLOBALLOC\")"; + + CompositeLocation pcLoc = methodLocInfo.getPCLoc(); + if ((pcLoc != null) && (!pcLoc.get(0).isTop())) { + rtr += "\n@PCLOC(\"" + generateLocationAnnoatation(pcLoc) + "\")"; + } + + } + + return rtr; + } + + private void generateAnnoatedCode() { + + readOriginalSourceFiles(); + + setupToAnalyze(); + while (!toAnalyzeIsEmpty()) { + ClassDescriptor cd = toAnalyzeNext(); + + setupToAnalazeMethod(cd); + + LocationInfo locInfo = mapClassToLocationInfo.get(cd); + String sourceFileName = cd.getSourceFileName(); + + if (cd.isInterface()) { + continue; + } + + int classDefLine = mapDescToDefinitionLine.get(cd); + Vector sourceVec = mapFileNameToLineVector.get(sourceFileName); + + if (locInfo == null) { + locInfo = getLocationInfo(cd); + } + + for (Iterator iter = cd.getFields(); iter.hasNext();) { + FieldDescriptor fieldDesc = (FieldDescriptor) iter.next(); + if (!(fieldDesc.isStatic() && fieldDesc.isFinal())) { + String locIdentifier = locInfo.getFieldInferLocation(fieldDesc).getLocIdentifier(); + if (!getLattice(cd).getElementSet().contains(locIdentifier)) { + getLattice(cd).put(locIdentifier); + } + } + } + + String fieldLatticeDefStr = generateLatticeDefinition(cd); + String annoatedSrc = fieldLatticeDefStr + newline + sourceVec.get(classDefLine); + sourceVec.set(classDefLine, annoatedSrc); + + // generate annotations for field declarations + LocationInfo fieldLocInfo = getLocationInfo(cd); + Map inferLocMap = fieldLocInfo.getMapDescToInferLocation(); + + for (Iterator iter = cd.getFields(); iter.hasNext();) { + FieldDescriptor fd = (FieldDescriptor) iter.next(); + + String locAnnotationStr; + CompositeLocation inferLoc = inferLocMap.get(fd); + + if (inferLoc != null) { + // infer loc is null if the corresponding field is static and final + locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")"; + int fdLineNum = fd.getLineNum(); + String orgFieldDeclarationStr = sourceVec.get(fdLineNum); + String fieldDeclaration = fd.toString(); + fieldDeclaration = fieldDeclaration.substring(0, fieldDeclaration.length() - 1); + String annoatedStr = locAnnotationStr + " " + orgFieldDeclarationStr; + sourceVec.set(fdLineNum, annoatedStr); + } + + } + + while (!toAnalyzeMethodIsEmpty()) { + MethodDescriptor md = toAnalyzeMethodNext(); + + if (!ssjava.needTobeAnnotated(md)) { + continue; + } + + SSJavaLattice methodLattice = md2lattice.get(md); + if (methodLattice != null) { + + int methodDefLine = md.getLineNum(); + + MethodLocationInfo methodLocInfo = getMethodLocationInfo(md); + + Map methodInferLocMap = + methodLocInfo.getMapDescToInferLocation(); + Set localVarDescSet = methodInferLocMap.keySet(); + + Set localLocElementSet = methodLattice.getElementSet(); + + for (Iterator iterator = localVarDescSet.iterator(); iterator.hasNext();) { + Descriptor localVarDesc = (Descriptor) iterator.next(); + CompositeLocation inferLoc = methodInferLocMap.get(localVarDesc); + + String localLocIdentifier = inferLoc.get(0).getLocIdentifier(); + if (!localLocElementSet.contains(localLocIdentifier)) { + methodLattice.put(localLocIdentifier); + } + + String locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")"; + + if (!isParameter(md, localVarDesc)) { + if (mapDescToDefinitionLine.containsKey(localVarDesc)) { + int varLineNum = mapDescToDefinitionLine.get(localVarDesc); + String orgSourceLine = sourceVec.get(varLineNum); + int idx = + orgSourceLine.indexOf(generateVarDeclaration((VarDescriptor) localVarDesc)); + assert (idx != -1); + String annoatedStr = + orgSourceLine.substring(0, idx) + locAnnotationStr + " " + + orgSourceLine.substring(idx); + sourceVec.set(varLineNum, annoatedStr); + } + } else { + String methodDefStr = sourceVec.get(methodDefLine); + + int idx = + getParamLocation(methodDefStr, + generateVarDeclaration((VarDescriptor) localVarDesc)); + + assert (idx != -1); + + String annoatedStr = + methodDefStr.substring(0, idx) + locAnnotationStr + " " + + methodDefStr.substring(idx); + sourceVec.set(methodDefLine, annoatedStr); + } + + } + + // check if the lattice has to have the location type for the this + // reference... + + // boolean needToAddthisRef = hasThisReference(md); + if (localLocElementSet.contains("this")) { + methodLattice.put("this"); + } + + String methodLatticeDefStr = generateLatticeDefinition(md); + String annoatedStr = methodLatticeDefStr + newline + sourceVec.get(methodDefLine); + sourceVec.set(methodDefLine, annoatedStr); + + } + } + + } + + codeGen(); + } + + private boolean hasThisReference(MethodDescriptor md) { + + FlowGraph fg = getFlowGraph(md); + Set nodeSet = fg.getNodeSet(); + for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + FlowNode flowNode = (FlowNode) iterator.next(); + if (flowNode.getLocTuple().get(0).equals(md.getThis())) { + return true; + } + } + + return false; + } + + private int getParamLocation(String methodStr, String paramStr) { + + String pattern = paramStr + ","; + + int idx = methodStr.indexOf(pattern); + if (idx != -1) { + return idx; + } else { + pattern = paramStr + ")"; + return methodStr.indexOf(pattern); + } + + } + + private String generateVarDeclaration(VarDescriptor varDesc) { + + TypeDescriptor td = varDesc.getType(); + String rtr = td.toString(); + if (td.isArray()) { + for (int i = 0; i < td.getArrayCount(); i++) { + 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(); + + setupToAnalazeMethod(cd); + + SSJavaLattice classLattice = cd2lattice.get(cd); + if (classLattice != null) { + classLattice.removeRedundantEdges(); + } + + while (!toAnalyzeMethodIsEmpty()) { + MethodDescriptor md = toAnalyzeMethodNext(); + SSJavaLattice methodLattice = md2lattice.get(md); + if (methodLattice != null) { + methodLattice.removeRedundantEdges(); + } + } + } + + } + + private boolean checkLatticeProperty(Descriptor d, SSJavaLattice lattice) { + // if two elements has the same incoming node set, + // we need to merge two elements ... + + boolean isUpdated; + boolean isModified = false; + do { + isUpdated = removeNodeSharingSameIncomingNodes(d, lattice); + if (!isModified && isUpdated) { + isModified = true; + } + } while (isUpdated); + + return isModified; + } + + private boolean removeNodeSharingSameIncomingNodes(Descriptor d, SSJavaLattice lattice) { + LocationInfo locInfo = getLocationInfo(d); + Map> map = lattice.getIncomingElementMap(); + Set keySet = map.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + String key = (String) iterator.next(); + Set incomingSetKey = map.get(key); + + // System.out.println("key=" + key + " incomingSetKey=" + + // incomingSetKey); + if (incomingSetKey.size() > 0) { + for (Iterator iterator2 = keySet.iterator(); iterator2.hasNext();) { + String cur = (String) iterator2.next(); + if (!cur.equals(key)) { + Set incomingSetCur = map.get(cur); + if (incomingSetCur.equals(incomingSetKey)) { + if (!(incomingSetCur.size() == 1 && incomingSetCur.contains(lattice.getTopItem()))) { + // NEED TO MERGE HERE!!!! + System.out.println("@@@Try merge=" + cur + " " + key); + + Set mergeSet = new HashSet(); + mergeSet.add(cur); + mergeSet.add(key); + + String newMergeLoc = "MLoc" + (SSJavaLattice.seed++); + + System.out.println("---ASSIGN NEW MERGE LOC=" + newMergeLoc + " to " + mergeSet); + lattice.mergeIntoNewLocation(mergeSet, newMergeLoc); + + for (Iterator miterator = mergeSet.iterator(); miterator.hasNext();) { + String oldLocSymbol = (String) miterator.next(); + + Set> inferLocSet = + locInfo.getRelatedInferLocSet(oldLocSymbol); + System.out.println("---update related locations=" + inferLocSet + + " oldLocSymbol=" + oldLocSymbol); + + for (Iterator miterator2 = inferLocSet.iterator(); miterator2.hasNext();) { + Pair pair = + (Pair) miterator2.next(); + Descriptor enclosingDesc = pair.getFirst(); + Descriptor desc = pair.getSecond(); + + System.out.println("---inferLoc pair=" + pair); + + CompositeLocation inferLoc = + getLocationInfo(enclosingDesc).getInferLocation(desc); + System.out.println("oldLoc=" + inferLoc); + // if (curMethodInfo.md.equals(enclosingDesc)) { + // inferLoc = curMethodInfo.getInferLocation(desc); + // } else { + // inferLoc = + // getLocationInfo(enclosingDesc).getInferLocation(desc); + // } + + Location locElement = inferLoc.get(inferLoc.getSize() - 1); + + locElement.setLocIdentifier(newMergeLoc); + locInfo.addMapLocSymbolToRelatedInferLoc(newMergeLoc, enclosingDesc, desc); + + // if (curMethodInfo.md.equals(enclosingDesc)) { + // inferLoc = curMethodInfo.getInferLocation(desc); + // } else { + // inferLoc = + // getLocationInfo(enclosingDesc).getInferLocation(desc); + // } + + inferLoc = getLocationInfo(enclosingDesc).getInferLocation(desc); + System.out.println("---New Infer Loc=" + inferLoc); + + } + + locInfo.removeRelatedInferLocSet(oldLocSymbol, newMergeLoc); + + } + + for (Iterator iterator3 = mergeSet.iterator(); iterator3.hasNext();) { + String oldLoc = (String) iterator3.next(); + lattice.remove(oldLoc); + } + return true; + } + } + } + } + } + + } + return false; + } + + private void checkLattices() { + + LinkedList descriptorListToAnalyze = ssjava.getSortedDescriptors(); + + // 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(); + checkLatticesOfVirtualMethods(md); + } + + } + + private void debug_writeLatticeDotFile() { + // generate lattice dot file + + setupToAnalyze(); + + while (!toAnalyzeIsEmpty()) { + ClassDescriptor cd = toAnalyzeNext(); + + setupToAnalazeMethod(cd); + + SSJavaLattice classLattice = cd2lattice.get(cd); + if (classLattice != null) { + ssjava.writeLatticeDotFile(cd, null, classLattice); + debug_printDescriptorToLocNameMapping(cd); + } + + while (!toAnalyzeMethodIsEmpty()) { + MethodDescriptor md = toAnalyzeMethodNext(); + SSJavaLattice methodLattice = md2lattice.get(md); + if (methodLattice != null) { + ssjava.writeLatticeDotFile(cd, md, methodLattice); + debug_printDescriptorToLocNameMapping(md); + } + } + } + + } + + private void debug_printDescriptorToLocNameMapping(Descriptor desc) { + + LocationInfo info = getLocationInfo(desc); + System.out.println("## " + desc + " ##"); + System.out.println(info.getMapDescToInferLocation()); + LocationInfo locInfo = getLocationInfo(desc); + System.out.println("mapping=" + locInfo.getMapLocSymbolToDescSet()); + System.out.println("###################"); + + } + + private void inferLattices() { + + // do fixed-point analysis + + ssjava.init(); + LinkedList descriptorListToAnalyze = ssjava.getSortedDescriptors(); + + // Collections.sort(descriptorListToAnalyze, new + // Comparator() { + // public int compare(MethodDescriptor o1, MethodDescriptor o2) { + // return o1.getSymbol().compareToIgnoreCase(o2.getSymbol()); + // } + // }); + + // current descriptors to visit in fixed-point interprocedural analysis, + // prioritized by + // dependency in the call graph + methodDescriptorsToVisitStack.clear(); + + // descriptorListToAnalyze.removeFirst(); + + Set methodDescriptorToVistSet = new HashSet(); + methodDescriptorToVistSet.addAll(descriptorListToAnalyze); + + while (!descriptorListToAnalyze.isEmpty()) { + MethodDescriptor md = descriptorListToAnalyze.removeFirst(); + methodDescriptorsToVisitStack.add(md); + } + + // analyze scheduled methods until there are no more to visit + while (!methodDescriptorsToVisitStack.isEmpty()) { + // start to analyze leaf node + MethodDescriptor md = methodDescriptorsToVisitStack.pop(); + + SSJavaLattice methodLattice = + new SSJavaLattice(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM); + + MethodLocationInfo methodInfo = new MethodLocationInfo(md); + curMethodInfo = methodInfo; + + System.out.println(); + System.out.println("SSJAVA: Inferencing the lattice from " + md); + + try { + analyzeMethodLattice(md, methodLattice, methodInfo); + } catch (CyclicFlowException e) { + throw new Error("Fail to generate the method lattice for " + md); + } + + SSJavaLattice prevMethodLattice = getMethodLattice(md); + MethodLocationInfo prevMethodInfo = getMethodLocationInfo(md); + + if ((!methodLattice.equals(prevMethodLattice)) || (!methodInfo.equals(prevMethodInfo))) { + + setMethodLattice(md, methodLattice); + setMethodLocInfo(md, methodInfo); + + // results for callee changed, so enqueue dependents caller for + // further analysis + Iterator depsItr = ssjava.getDependents(md).iterator(); + while (depsItr.hasNext()) { + MethodDescriptor methodNext = depsItr.next(); + if (!methodDescriptorsToVisitStack.contains(methodNext) + && methodDescriptorToVistSet.contains(methodNext)) { + methodDescriptorsToVisitStack.add(methodNext); + } + } + + } + + } + + } + + private void calculateExtraLocations() { + LinkedList descriptorListToAnalyze = ssjava.getSortedDescriptors(); + for (Iterator iterator = descriptorListToAnalyze.iterator(); iterator.hasNext();) { + MethodDescriptor md = (MethodDescriptor) iterator.next(); + calculateExtraLocations(md); + } + } + + private void setMethodLocInfo(MethodDescriptor md, MethodLocationInfo methodInfo) { + mapMethodDescToMethodLocationInfo.put(md, methodInfo); + } + + private void checkLatticesOfVirtualMethods(MethodDescriptor md) { + + if (!md.isStatic()) { + Set setPossibleCallees = new HashSet(); + setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md)); + + for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) { + MethodDescriptor mdCallee = (MethodDescriptor) iterator.next(); + if (!md.equals(mdCallee)) { + checkConsistency(md, mdCallee); + } + } + + } + + } + + private void checkConsistency(MethodDescriptor md1, MethodDescriptor md2) { + + // check that two lattice have the same relations between parameters(+PC + // LOC, GLOBAL_LOC RETURN LOC) + + List list1 = new ArrayList(); + List list2 = new ArrayList(); + + MethodLocationInfo locInfo1 = getMethodLocationInfo(md1); + MethodLocationInfo locInfo2 = getMethodLocationInfo(md2); + + Map paramMap1 = locInfo1.getMapParamIdxToInferLoc(); + Map paramMap2 = locInfo2.getMapParamIdxToInferLoc(); + + int numParam = locInfo1.getMapParamIdxToInferLoc().keySet().size(); + + // add location types of paramters + for (int idx = 0; idx < numParam; idx++) { + list1.add(paramMap1.get(Integer.valueOf(idx))); + list2.add(paramMap2.get(Integer.valueOf(idx))); + } + + // add program counter location + list1.add(locInfo1.getPCLoc()); + list2.add(locInfo2.getPCLoc()); + + if (!md1.getReturnType().isVoid()) { + // add return value location + CompositeLocation rtrLoc1 = getMethodLocationInfo(md1).getReturnLoc(); + CompositeLocation rtrLoc2 = getMethodLocationInfo(md2).getReturnLoc(); + list1.add(rtrLoc1); + list2.add(rtrLoc2); + } + + // add global location type + if (md1.isStatic()) { + CompositeLocation globalLoc1 = + new CompositeLocation(new Location(md1, locInfo1.getGlobalLocName())); + CompositeLocation globalLoc2 = + new CompositeLocation(new Location(md2, locInfo2.getGlobalLocName())); + list1.add(globalLoc1); + list2.add(globalLoc2); + } + + for (int i = 0; i < list1.size(); i++) { + CompositeLocation locA1 = list1.get(i); + CompositeLocation locA2 = list2.get(i); + for (int k = 0; k < list1.size(); k++) { + if (i != k) { + CompositeLocation locB1 = list1.get(k); + CompositeLocation locB2 = list2.get(k); + boolean r1 = isGreaterThan(getLattice(md1), locA1, locB1); + + boolean r2 = isGreaterThan(getLattice(md1), locA2, locB2); + + if (r1 != r2) { + throw new Error("The method " + md1 + " is not consistent with the method " + md2 + + ".:: They have a different ordering relation between locations (" + locA1 + "," + + locB1 + ") and (" + locA2 + "," + locB2 + ")."); + } + } + } + } + + } + + private String getSymbol(int idx, FlowNode node) { + Descriptor desc = node.getDescTuple().get(idx); + return desc.getSymbol(); + } + + private Descriptor getDescriptor(int idx, FlowNode node) { + Descriptor desc = node.getDescTuple().get(idx); + 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 = fg.getOutEdgeSet(srcNode); + 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,... + + SSJavaLattice methodLattice = getMethodLattice(md); + MethodLocationInfo methodInfo = getMethodLocationInfo(md); + FlowGraph fg = getFlowGraph(md); + Set nodeSet = fg.getNodeSet(); + + for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + FlowNode flowNode = (FlowNode) iterator.next(); + if (flowNode.isDeclaratonNode()) { + CompositeLocation inferLoc = methodInfo.getInferLocation(flowNode.getDescTuple().get(0)); + String locIdentifier = inferLoc.get(0).getLocIdentifier(); + if (!methodLattice.containsKey(locIdentifier)) { + methodLattice.put(locIdentifier); + } + + } + } + + Map mapParamToLoc = methodInfo.getMapParamIdxToInferLoc(); + Set paramIdxSet = mapParamToLoc.keySet(); + + 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(); + + for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) { + Integer paramIdx = (Integer) iterator.next(); + + FlowNode paramFlowNode = fg.getParamFlowNode(paramIdx); + + if (fg.getIncomingFlowNodeSet(paramFlowNode).size() > 0) { + // parameter has in-value flows + CompositeLocation inferLoc = mapParamToLoc.get(paramIdx); + paramInFlowSet.add(inferLoc); + } + } + + if (paramInFlowSet.size() > 0) { + CompositeLocation lowestLoc = getLowest(methodLattice, paramInFlowSet); + assert (lowestLoc != null); + methodInfo.setPCLoc(lowestLoc); + } + + } + + // calculate a return location + // the return location type is lower than all parameters and location + // types + // of return values + if (!md.getReturnType().isVoid()) { + // first, generate the set of return value location types that starts + // with + // 'this' reference + + Set inferFieldReturnLocSet = new HashSet(); + + Set paramFlowNode = getParamNodeFlowingToReturnValue(md); + Set inferParamLocSet = new HashSet(); + if (paramFlowNode != null) { + for (Iterator iterator = paramFlowNode.iterator(); iterator.hasNext();) { + FlowNode fn = (FlowNode) iterator.next(); + CompositeLocation inferLoc = + generateInferredCompositeLocation(methodInfo, getFlowGraph(md).getLocationTuple(fn)); + inferParamLocSet.add(inferLoc); + } + } + + Set returnNodeSet = fg.getReturnNodeSet(); + + skip: for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { + FlowNode returnNode = (FlowNode) iterator.next(); + CompositeLocation inferReturnLoc = + generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode)); + if (inferReturnLoc.get(0).getLocIdentifier().equals("this")) { + // if the location type of the return value matches "this" reference + // then, check whether this return value is equal to/lower than all + // of + // parameters that possibly flow into the return values + for (Iterator iterator2 = inferParamLocSet.iterator(); iterator2.hasNext();) { + CompositeLocation paramInferLoc = (CompositeLocation) iterator2.next(); + + if ((!paramInferLoc.equals(inferReturnLoc)) + && !isGreaterThan(methodLattice, paramInferLoc, inferReturnLoc)) { + continue skip; + } + } + inferFieldReturnLocSet.add(inferReturnLoc); + + } + } + + if (inferFieldReturnLocSet.size() > 0) { + + CompositeLocation returnLoc = getLowest(methodLattice, inferFieldReturnLocSet); + if (returnLoc == null) { + // in this case, assign <'this',bottom> to the RETURNLOC + returnLoc = new CompositeLocation(new Location(md, md.getThis().getSymbol())); + returnLoc.addLocation(new Location(md.getClassDesc(), getLattice(md.getClassDesc()) + .getBottomItem())); + } + methodInfo.setReturnLoc(returnLoc); + + } else { + String returnLocSymbol = "RETURNLOC"; + CompositeLocation returnLocInferLoc = + new CompositeLocation(new Location(md, returnLocSymbol)); + methodInfo.setReturnLoc(returnLocInferLoc); + + for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) { + Integer paramIdx = (Integer) iterator.next(); + CompositeLocation inferLoc = mapParamToLoc.get(paramIdx); + String paramLocLocalSymbol = inferLoc.get(0).getLocIdentifier(); + if (!methodLattice.isGreaterThan(paramLocLocalSymbol, returnLocSymbol)) { + 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)) { + addRelation(methodLattice, methodInfo, inferLoc, returnLocInferLoc); + } + } + + } + + } + } catch (CyclicFlowException e) { + e.printStackTrace(); + } + + } + + private Set getHigherLocSymbolThan(SSJavaLattice lattice, String loc) { + Set higherLocSet = new HashSet(); + + Set locSet = lattice.getTable().keySet(); + for (Iterator iterator = locSet.iterator(); iterator.hasNext();) { + String element = (String) iterator.next(); + if (lattice.isGreaterThan(element, loc) && (!element.equals(lattice.getTopItem()))) { + higherLocSet.add(element); + } + } + return higherLocSet; + } + + private CompositeLocation getLowest(SSJavaLattice methodLattice, + Set set) { + + CompositeLocation lowest = set.iterator().next(); + + if (set.size() == 1) { + return lowest; + } + + for (Iterator iterator = set.iterator(); iterator.hasNext();) { + CompositeLocation loc = (CompositeLocation) iterator.next(); + + if ((!loc.equals(lowest)) && (!isComparable(methodLattice, lowest, loc))) { + // if there is a case where composite locations are incomparable, just + // return null + return null; + } + + if ((!loc.equals(lowest)) && isGreaterThan(methodLattice, lowest, loc)) { + lowest = loc; + } + } + return lowest; + } + + private boolean isComparable(SSJavaLattice methodLattice, CompositeLocation comp1, + CompositeLocation comp2) { + + int size = comp1.getSize() >= comp2.getSize() ? comp2.getSize() : comp1.getSize(); + + for (int idx = 0; idx < size; idx++) { + Location loc1 = comp1.get(idx); + Location loc2 = comp2.get(idx); + + Descriptor desc1 = loc1.getDescriptor(); + Descriptor desc2 = loc2.getDescriptor(); + + if (!desc1.equals(desc2)) { + throw new Error("Fail to compare " + comp1 + " and " + comp2); + } + + String symbol1 = loc1.getLocIdentifier(); + String symbol2 = loc2.getLocIdentifier(); + + SSJavaLattice lattice; + if (idx == 0) { + lattice = methodLattice; + } else { + lattice = getLattice(desc1); + } + + if (symbol1.equals(symbol2)) { + continue; + } else if (!lattice.isComparable(symbol1, symbol2)) { + return false; + } + + } + + return true; + } + + private boolean isGreaterThan(SSJavaLattice methodLattice, CompositeLocation comp1, + CompositeLocation comp2) { + + int size = comp1.getSize() >= comp2.getSize() ? comp2.getSize() : comp1.getSize(); + + for (int idx = 0; idx < size; idx++) { + Location loc1 = comp1.get(idx); + Location loc2 = comp2.get(idx); + + Descriptor desc1 = loc1.getDescriptor(); + Descriptor desc2 = loc2.getDescriptor(); + + if (!desc1.equals(desc2)) { + throw new Error("Fail to compare " + comp1 + " and " + comp2); + } + + String symbol1 = loc1.getLocIdentifier(); + String symbol2 = loc2.getLocIdentifier(); + + SSJavaLattice lattice; + if (idx == 0) { + lattice = methodLattice; + } else { + lattice = getLattice(desc1); + } + + if (symbol1.equals(symbol2)) { + continue; + } else if (lattice.isGreaterThan(symbol1, symbol2)) { + return true; + } else { + return false; + } + + } + + 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(); + + if (srcLocSymbol.equals(dstLocSymbol)) { + recursiveAddRelationToLattice(idx + 1, md, srcInferLoc, dstInferLoc); + } else { + + Descriptor parentDesc = srcInferLoc.get(idx).getDescriptor(); + LocationInfo locInfo = getLocationInfo(parentDesc); + + addRelationHigherToLower(getLattice(parentDesc), getLocationInfo(parentDesc), srcLocSymbol, + dstLocSymbol); + } + + } + + // private void propagateFlowsFromCallee(MethodInvokeNode min, MethodDescriptor mdCaller, + // MethodDescriptor mdCallee) { + // + // // the transformation for a call site propagates all relations between + // // parameters from the callee + // // if the method is virtual, it also grab all relations from any possible + // // callees + // + // Set setPossibleCallees = new HashSet(); + // if (mdCallee.isStatic()) { + // setPossibleCallees.add(mdCallee); + // } else { + // Set calleeSet = ssjava.getCallGraph().getMethods(mdCallee); + // // removes method descriptors that are not invoked by the caller + // calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller)); + // setPossibleCallees.addAll(calleeSet); + // } + // + // for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) { + // MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next(); + // propagateFlowsToCaller(min, mdCaller, possibleMdCallee); + // } + // + // } + + private void contributeCalleeFlows(MethodInvokeNode min, MethodDescriptor mdCaller, + MethodDescriptor mdCallee) { + + System.out.println("\n##contributeCalleeFlows callee=" + mdCallee + "TO caller=" + mdCaller); + + getSubGlobalFlowGraph(mdCallee); + + } + + private FlowGraph getSubGlobalFlowGraph(MethodDescriptor md) { + return mapMethodDescriptorToSubGlobalFlowGraph.get(md); + } + + private void propagateFlowsToCallerWithNoCompositeLocation(MethodInvokeNode min, + MethodDescriptor mdCaller, MethodDescriptor mdCallee) { + + System.out.println("\n##PROPAGATE callee=" + mdCallee + "TO caller=" + mdCaller); + + // 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(); + + for (int i = 0; i < numParam; i++) { + for (int k = 0; k < numParam; k++) { + + if (i != k) { + + FlowNode paramNode1 = calleeFlowGraph.getParamFlowNode(i); + FlowNode paramNode2 = calleeFlowGraph.getParamFlowNode(k); + + System.out.println("param1=" + paramNode1 + " curDescTuple=" + + paramNode1.getCurrentDescTuple()); + System.out.println("param2=" + paramNode2 + " curDescTuple=" + + paramNode2.getCurrentDescTuple()); + + // TODO: deprecated method + // NodeTupleSet tupleSetArg1 = getNodeTupleSetByArgIdx(min, i); + // NodeTupleSet tupleSetArg2 = getNodeTupleSetByArgIdx(min, k); + NodeTupleSet tupleSetArg1 = null; + NodeTupleSet tupleSetArg2 = null; + + for (Iterator> iter1 = tupleSetArg1.iterator(); iter1.hasNext();) { + NTuple arg1Tuple = iter1.next(); + + for (Iterator> iter2 = tupleSetArg2.iterator(); iter2.hasNext();) { + NTuple arg2Tuple = iter2.next(); + + // check if the callee propagates an ordering constraints through + // parameters + + Set localReachSet = + calleeFlowGraph.getLocalReachFlowNodeSetFrom(paramNode1); + + if (localReachSet.contains(paramNode2)) { + // need to propagate an ordering relation s.t. arg1 is higher + // than arg2 + + System.out + .println("-param1=" + paramNode1 + " is higher than param2=" + paramNode2); + System.out.println("-arg1Tuple=" + arg1Tuple + " is higher than arg2Tuple=" + + arg2Tuple); + + if (!min.getMethod().isStatic()) { + // check if this is the case that values flow to/from the + // current object reference 'this' + + NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); + Descriptor baseRef = baseTuple.get(baseTuple.size() - 1); + + System.out.println("paramNode1.getCurrentDescTuple()=" + + paramNode1.getCurrentDescTuple()); + // calculate the prefix of the argument + + if (arg2Tuple.size() == 1 && arg2Tuple.get(0).equals(baseRef)) { + // in this case, the callee flow causes a caller flow to the object whose method + // is invoked. + + if (!paramNode1.getCurrentDescTuple().startsWith(mdCallee.getThis())) { + // check whether ??? + + NTuple param1Prefix = + calculatePrefixForParam(callerFlowGraph, calleeFlowGraph, min, arg1Tuple, + paramNode1); + + if (param1Prefix != null && param1Prefix.startsWith(mdCallee.getThis())) { + // in this case, we need to create a new edge 'this.FIELD'->'this' + // but we couldn't... instead we assign a new composite location started + // with 'this' reference to the corresponding parameter + + CompositeLocation compLocForParam1 = + generateCompositeLocation(mdCallee, param1Prefix); + + System.out + .println("set comp loc=" + compLocForParam1 + " to " + paramNode1); + paramNode1.setCompositeLocation(compLocForParam1); + + // then, we need to make sure that the corresponding argument in the caller + // is required to be higher than or equal to the translated parameter + // location + + NTuple translatedParamTuple = + translateCompositeLocationToCaller(min, compLocForParam1); + + // TODO : check if the arg >= the tranlated parameter + + System.out.println("add a flow edge= " + arg1Tuple + "->" + + translatedParamTuple); + callerFlowGraph.addValueFlowEdge(arg1Tuple, translatedParamTuple); + + continue; + + } + + } else { + // param1 has already been assigned a composite location + + System.out.println("--param1 has already been assigned a composite location"); + CompositeLocation compLocForParam1 = paramNode1.getCompositeLocation(); + NTuple translatedParamTuple = + translateCompositeLocationToCaller(min, compLocForParam1); + + // TODO : check if the arg >= the tranlated parameter + + System.out.println("add a flow edge= " + arg1Tuple + "->" + + translatedParamTuple); + callerFlowGraph.addValueFlowEdge(arg1Tuple, translatedParamTuple); + + continue; + + } + + } else if (arg1Tuple.size() == 1 && arg1Tuple.get(0).equals(baseRef)) { + // in this case, the callee flow causes a caller flow originated from the object + // whose + // method is invoked. + + System.out.println("###FROM CASE"); + + if (!paramNode2.getCurrentDescTuple().startsWith(mdCallee.getThis())) { + + NTuple param2Prefix = + calculatePrefixForParam(callerFlowGraph, calleeFlowGraph, min, arg2Tuple, + paramNode2); + + if (param2Prefix != null && param2Prefix.startsWith(mdCallee.getThis())) { + // in this case, we need to create a new edge 'this' -> + // 'this.FIELD' but we couldn't... instead we assign the corresponding + // parameter a new composite location started with 'this' reference + + CompositeLocation compLocForParam2 = + generateCompositeLocation(mdCallee, param2Prefix); + + // System.out.println("set comp loc=" + compLocForParam2 + // + + // " to " + paramNode2); + paramNode1.setCompositeLocation(compLocForParam2); + continue; + } + } + + } + } + + // 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 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 paramPrefix) { + + System.out.println("generateCompositeLocation=" + paramPrefix); + + CompositeLocation newCompLoc = convertToCompositeLocation(md, paramPrefix); + + Descriptor lastDescOfPrefix = paramPrefix.get(paramPrefix.size() - 1); + // System.out.println("lastDescOfPrefix=" + lastDescOfPrefix + " kind=" + // + lastDescOfPrefix.getClass()); + ClassDescriptor enclosingDescriptor; + if (lastDescOfPrefix instanceof FieldDescriptor) { + enclosingDescriptor = ((FieldDescriptor) lastDescOfPrefix).getType().getClassDesc(); + // System.out.println("enclosingDescriptor0=" + enclosingDescriptor); + } else { + // var descriptor case + enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc(); + } + // System.out.println("enclosingDescriptor=" + enclosingDescriptor); + + LocationDescriptor newLocDescriptor = generateNewLocationDescriptor(); + newLocDescriptor.setEnclosingClassDesc(enclosingDescriptor); + + Location newLoc = new Location(enclosingDescriptor, newLocDescriptor.getSymbol()); + newLoc.setLocDescriptor(newLocDescriptor); + newCompLoc.addLocation(newLoc); + + // System.out.println("--newCompLoc=" + newCompLoc); + return newCompLoc; + } + + private NTuple calculatePrefixForParam(FlowGraph callerFlowGraph, + FlowGraph calleeFlowGraph, MethodInvokeNode min, NTuple arg1Tuple, + FlowNode paramNode1) { + + NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); + Descriptor baseRef = baseTuple.get(baseTuple.size() - 1); + System.out.println("baseRef=" + baseRef); + + FlowNode flowNodeArg1 = callerFlowGraph.getFlowNode(arg1Tuple); + List> callerPrefixList = calculatePrefixList(callerFlowGraph, flowNodeArg1); + System.out.println("callerPrefixList=" + callerPrefixList); + + List> prefixList = calculatePrefixList(calleeFlowGraph, paramNode1); + System.out.println("###prefixList from node=" + paramNode1 + " =" + prefixList); + + List> calleePrefixList = + translatePrefixListToCallee(baseRef, min.getMethod(), callerPrefixList); + + System.out.println("calleePrefixList=" + calleePrefixList); + + Set reachNodeSetFromParam1 = calleeFlowGraph.getReachFlowNodeSetFrom(paramNode1); + System.out.println("reachNodeSetFromParam1=" + reachNodeSetFromParam1); + + for (int i = 0; i < calleePrefixList.size(); i++) { + NTuple curPrefix = calleePrefixList.get(i); + Set> reachableCommonPrefixSet = new HashSet>(); + + for (Iterator iterator2 = reachNodeSetFromParam1.iterator(); iterator2.hasNext();) { + FlowNode reachNode = (FlowNode) iterator2.next(); + if (reachNode.getCurrentDescTuple().startsWith(curPrefix)) { + reachableCommonPrefixSet.add(reachNode.getCurrentDescTuple()); + } + } + + if (!reachableCommonPrefixSet.isEmpty()) { + System.out.println("###REACHABLECOMONPREFIX=" + reachableCommonPrefixSet + + " with curPreFix=" + curPrefix); + return curPrefix; } + } - // calculate a return location - // the return location type is lower than all parameters - if (!md.getReturnType().isVoid()) { + return null; + } + + private List> translatePrefixListToCallee(Descriptor baseRef, + MethodDescriptor mdCallee, List> callerPrefixList) { - String returnLocSymbol = "RETURNLOC"; + List> calleePrefixList = new ArrayList>(); - for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { - Integer paramIdx = (Integer) iterator.next(); - CompositeLocation inferLoc = mapParamToLoc.get(paramIdx); - String paramLocLocalSymbol = inferLoc.get(0).getLocIdentifier(); - if (!methodLattice.isGreaterThan(paramLocLocalSymbol, returnLocSymbol)) { - addRelationHigherToLower(methodLattice, methodInfo, paramLocLocalSymbol, returnLocSymbol); + for (int i = 0; i < callerPrefixList.size(); i++) { + NTuple prefix = callerPrefixList.get(i); + if (prefix.startsWith(baseRef)) { + NTuple calleePrefix = new NTuple(); + calleePrefix.add(mdCallee.getThis()); + for (int k = 1; k < prefix.size(); k++) { + calleePrefix.add(prefix.get(k)); } + calleePrefixList.add(calleePrefix); } } + return calleePrefixList; + } - private boolean isGreaterThan(SSJavaLattice methodLattice, CompositeLocation comp1, - CompositeLocation comp2) { + private List> calculatePrefixList(FlowGraph flowGraph, FlowNode flowNode) { - int size = comp1.getSize() >= comp2.getSize() ? comp2.getSize() : comp1.getSize(); + System.out.println("\n##### calculatePrefixList=" + flowNode); - for (int idx = 0; idx < size; idx++) { - Location loc1 = comp1.get(idx); - Location loc2 = comp2.get(idx); + Set inNodeSet = flowGraph.getIncomingFlowNodeSet(flowNode); + inNodeSet.add(flowNode); - Descriptor desc1 = loc1.getDescriptor(); - Descriptor desc2 = loc2.getDescriptor(); + System.out.println("inNodeSet=" + inNodeSet); - if (!desc1.equals(desc2)) { - throw new Error("Fail to compare " + comp1 + " and " + comp2); - } + List> prefixList = new ArrayList>(); - String symbol1 = loc1.getLocIdentifier(); - String symbol2 = loc2.getLocIdentifier(); + for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) { + FlowNode inNode = (FlowNode) iterator.next(); - SSJavaLattice lattice; - if (idx == 0) { - lattice = methodLattice; - } else { - lattice = getLattice(desc1); + NTuple inNodeTuple = inNode.getCurrentDescTuple(); + + // CompositeLocation inNodeInferredLoc = + // generateInferredCompositeLocation(methodInfo, inNodeTuple); + // NTuple inNodeInferredLocTuple = inNodeInferredLoc.getTuple(); + + for (int i = 1; i < inNodeTuple.size(); i++) { + NTuple prefix = inNodeTuple.subList(0, i); + if (!prefixList.contains(prefix)) { + prefixList.add(prefix); + } } - if (symbol1.equals(symbol2)) { - continue; - } else if (lattice.isGreaterThan(symbol1, symbol2)) { - return true; + } + + Collections.sort(prefixList, new Comparator>() { + public int compare(NTuple arg0, NTuple arg1) { + int s0 = arg0.size(); + int s1 = arg1.size(); + if (s0 > s1) { + return -1; + } else if (s0 == s1) { + return 0; + } else { + return 1; + } + } + }); + + return prefixList; + + } + + public CompositeLocation convertToCompositeLocation(MethodDescriptor md, NTuple tuple) { + + CompositeLocation compLoc = new CompositeLocation(); + + Descriptor enclosingDescriptor = md; + + for (int i = 0; i < tuple.size(); i++) { + Descriptor curDescriptor = tuple.get(i); + Location locElement = new Location(enclosingDescriptor, curDescriptor.getSymbol()); + locElement.setLocDescriptor(curDescriptor); + compLoc.addLocation(locElement); + + if (curDescriptor instanceof VarDescriptor) { + enclosingDescriptor = md.getClassDesc(); + } else if (curDescriptor instanceof NameDescriptor) { + // it is "GLOBAL LOC" case! + enclosingDescriptor = GLOBALDESC; } else { - return false; + enclosingDescriptor = ((FieldDescriptor) curDescriptor).getClassDescriptor(); } } - return false; + System.out.println("-convertToCompositeLocation from=" + tuple + " to " + compLoc); + + return compLoc; } - private void recursiveAddRelationToLattice(int idx, MethodDescriptor md, - CompositeLocation srcInferLoc, CompositeLocation dstInferLoc) throws CyclicFlowException { + private LocationDescriptor generateNewLocationDescriptor() { + return new LocationDescriptor("Loc" + (locSeed++)); + } - String srcLocSymbol = srcInferLoc.get(idx).getLocIdentifier(); - String dstLocSymbol = dstInferLoc.get(idx).getLocIdentifier(); + private int getPrefixIndex(NTuple tuple1, NTuple tuple2) { - if (srcLocSymbol.equals(dstLocSymbol)) { - recursiveAddRelationToLattice(idx + 1, md, srcInferLoc, dstInferLoc); - } else { + // return the index where the prefix shared by tuple1 and tuple2 is ended + // if there is no prefix shared by both of them, return -1 - Descriptor parentDesc = srcInferLoc.get(idx).getDescriptor(); - LocationInfo locInfo = getLocationInfo(parentDesc); + int minSize = tuple1.size(); + if (minSize > tuple2.size()) { + minSize = tuple2.size(); + } - addRelationHigherToLower(getLattice(parentDesc), getLocationInfo(parentDesc), srcLocSymbol, - dstLocSymbol); + int idx = -1; + for (int i = 0; i < minSize; i++) { + if (!tuple1.get(i).equals(tuple2.get(i))) { + break; + } else { + idx++; + } } + return idx; } private void analyzeLatticeMethodInvocationNode(MethodDescriptor mdCaller, @@ -669,9 +2655,12 @@ public class LocationInference { for (int k = 0; k < numParam; k++) { if (i != k) { CompositeLocation param2 = calleeLocInfo.getParamCompositeLocation(k); + if (isGreaterThan(getLattice(possibleMdCallee), param1, param2)) { - NodeTupleSet argDescTupleSet1 = getNodeTupleSetByArgIdx(min, i); - NodeTupleSet argDescTupleSet2 = getNodeTupleSetByArgIdx(min, k); + // NodeTupleSet argDescTupleSet1 = 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 @@ -716,9 +2705,6 @@ public class LocationInference { private CompositeLocation generateInferredCompositeLocation(MethodLocationInfo methodInfo, NTuple tuple) { - // System.out.println("@@@@@generateInferredCompositeLocation=" + tuple); - // System.out.println("generateInferredCompositeLocation=" + tuple + " 0=" - // + tuple.get(0).getLocDescriptor()); // first, retrieve inferred location by the local var descriptor CompositeLocation inferLoc = new CompositeLocation(); @@ -730,7 +2716,6 @@ public class LocationInference { for (int i = 0; i < localVarInferLoc.getSize(); i++) { inferLoc.addLocation(localVarInferLoc.get(i)); } - // System.out.println("@@@@@localVarInferLoc=" + localVarInferLoc); for (int i = 1; i < tuple.size(); i++) { Location cur = tuple.get(i); @@ -740,8 +2725,6 @@ public class LocationInference { Location inferLocElement; if (curDesc == null) { // in this case, we have a newly generated location. - // System.out.println("!!! generated location=" + - // cur.getLocIdentifier()); inferLocElement = new Location(enclosingDesc, cur.getLocIdentifier()); } else { String fieldLocSymbol = @@ -753,7 +2736,8 @@ public class LocationInference { inferLoc.addLocation(inferLocElement); } - // System.out.println("@@@@@inferLoc=" + inferLoc); + + assert (inferLoc.get(0).getLocDescriptor().getSymbol() == inferLoc.get(0).getLocIdentifier()); return inferLoc; } @@ -825,7 +2809,7 @@ public class LocationInference { FlowGraph flowGraph = getFlowGraph(md); try { System.out.println("***** src composite case::"); - calculateCompositeLocation(flowGraph, methodLattice, methodInfo, srcNode); + calculateCompositeLocation(flowGraph, methodLattice, methodInfo, srcNode, null); CompositeLocation srcInferLoc = generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(srcNode)); @@ -836,7 +2820,7 @@ public class LocationInference { // 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); + calculateCompositeLocation(flowGraph, methodLattice, methodInfo, dstNode, srcNode); CompositeLocation srcInferLoc = generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(srcNode)); CompositeLocation dstInferLoc = @@ -881,7 +2865,7 @@ public class LocationInference { CompositeLocation inferSrcLoc; CompositeLocation inferDstLoc = methodInfo.getInferLocation(dstDesc); - if (srcNode.getDescTuple().size() > 1) { + if (srcNode.getLocTuple().size() > 1) { // field access inferSrcLoc = new CompositeLocation(); @@ -894,7 +2878,7 @@ public class LocationInference { inferSrcLoc = methodInfo.getInferLocation(srcDesc); } - if (dstNode.getDescTuple().size() > 1) { + if (dstNode.getLocTuple().size() > 1) { // field access inferDstLoc = new CompositeLocation(); @@ -920,8 +2904,8 @@ public class LocationInference { } private boolean calculateCompositeLocation(FlowGraph flowGraph, - SSJavaLattice methodLattice, MethodLocationInfo methodInfo, FlowNode flowNode) - throws CyclicFlowException { + SSJavaLattice methodLattice, MethodLocationInfo methodInfo, FlowNode flowNode, + FlowNode srcNode) throws CyclicFlowException { Descriptor localVarDesc = flowNode.getDescTuple().get(0); NTuple flowNodelocTuple = flowGraph.getLocationTuple(flowNode); @@ -931,17 +2915,11 @@ public class LocationInference { } Set inNodeSet = flowGraph.getIncomingFlowNodeSet(flowNode); - Set reachableNodeSet = flowGraph.getReachableFlowNodeSet(flowNode); + Set reachableNodeSet = flowGraph.getReachFlowNodeSetFrom(flowNode); Map, Set>> mapPrefixToIncomingLocTupleSet = new HashMap, Set>>(); - Set localInNodeSet = new HashSet(); - Set localOutNodeSet = new HashSet(); - - CompositeLocation flowNodeInferLoc = - generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(flowNode)); - List> prefixList = new ArrayList>(); for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) { @@ -953,16 +2931,12 @@ public class LocationInference { NTuple inNodeInferredLocTuple = inNodeInferredLoc.getTuple(); - if (inNodeTuple.size() > 1) { - 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); + for (int i = 1; i < inNodeInferredLocTuple.size(); i++) { + NTuple prefix = inNodeInferredLocTuple.subList(0, i); + if (!prefixList.contains(prefix)) { + prefixList.add(prefix); } - } else { - localInNodeSet.add(inNode); + addPrefixMapping(mapPrefixToIncomingLocTupleSet, prefix, inNodeInferredLocTuple); } } @@ -980,12 +2954,8 @@ public class LocationInference { } }); - for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) { - FlowNode reachableNode = (FlowNode) iterator2.next(); - if (reachableNode.getDescTuple().size() == 1) { - localOutNodeSet.add(reachableNode); - } - } + // 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++) { @@ -1002,13 +2972,6 @@ public class LocationInference { } } - // check if the lattice has the relation in which higher prefix is - // actually lower than the current node - CompositeLocation prefixInferLoc = generateInferredCompositeLocation(methodInfo, curPrefix); - if (isGreaterThan(methodLattice, flowNodeInferLoc, prefixInferLoc)) { - reachableCommonPrefixSet.add(curPrefix); - } - if (!reachableCommonPrefixSet.isEmpty()) { // found reachable nodes that start with the prefix curPrefix // need to assign a composite location @@ -1016,7 +2979,7 @@ public class LocationInference { // 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); + // prefixSanityCheck(prefixList, i, flowGraph, reachableNodeSet); Set> incomingCommonPrefixSet = mapPrefixToIncomingLocTupleSet.get(curPrefix); @@ -1034,11 +2997,47 @@ public class LocationInference { // methodInfo.getInferLocation(localVarDesc); CompositeLocation newInferLocation = new CompositeLocation(); - System.out.println("PREV INFER LOCATION=" + inferLocation + " curPrefix=" - + curPrefix); if (inferLocation.getTuple().startsWith(curPrefix)) { // the same infer location is already existed. no need to do // anything + System.out.println("NO ATTEMPT TO MAKE A COMPOSITE LOCATION curPrefix=" + curPrefix); + + // TODO: refactoring! + if (srcNode != null) { + CompositeLocation newLoc = new CompositeLocation(); + String newLocSymbol = "Loc" + (SSJavaLattice.seed++); + for (int locIdx = 0; locIdx < curPrefix.size(); locIdx++) { + newLoc.addLocation(curPrefix.get(locIdx)); + } + Location newLocationElement = new Location(desc, newLocSymbol); + newLoc.addLocation(newLocationElement); + + Descriptor srcLocalVar = srcNode.getDescTuple().get(0); + methodInfo.mapDescriptorToLocation(srcLocalVar, newLoc.clone()); + addMapLocSymbolToInferredLocation(methodInfo.getMethodDesc(), srcLocalVar, newLoc); + methodInfo.removeMaplocalVarToLocSet(srcLocalVar); + + // add the field/var descriptor to the set of the location symbol + int lastIdx = srcNode.getLocTuple().size() - 1; + Descriptor lastFlowNodeDesc = srcNode.getDescTuple().get(lastIdx); + NTuple srcNodelocTuple = flowGraph.getLocationTuple(srcNode); + Descriptor enclosinglastLastFlowNodeDesc = srcNodelocTuple.get(lastIdx).getDescriptor(); + + CompositeLocation newlyInferredLocForFlowNode = + generateInferredCompositeLocation(methodInfo, srcNodelocTuple); + Location lastInferLocElement = + newlyInferredLocForFlowNode.get(newlyInferredLocForFlowNode.getSize() - 1); + Descriptor enclosingLastInferLocElement = lastInferLocElement.getDescriptor(); + + // getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToDescSet( + // lastInferLocElement.getLocIdentifier(), lastFlowNodeDesc); + getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToRelatedInferLoc( + lastInferLocElement.getLocIdentifier(), enclosinglastLastFlowNodeDesc, + lastFlowNodeDesc); + + System.out.println("@@@@@@@ ASSIGN " + newLoc + " to SRC=" + srcNode); + } + return true; } else { // assign a new composite location @@ -1052,10 +3051,8 @@ public class LocationInference { Location newLocationElement = new Location(desc, newLocSymbol); newInferLocation.addLocation(newLocationElement); - // if (flowNode.getDescTuple().size() == 1) { // maps local variable to location types of the common prefix methodInfo.mapDescriptorToLocation(localVarDesc, newInferLocation.clone()); - // } // methodInfo.mapDescriptorToLocation(localVarDesc, newInferLocation); addMapLocSymbolToInferredLocation(methodInfo.getMethodDesc(), localVarDesc, @@ -1063,12 +3060,20 @@ public class LocationInference { methodInfo.removeMaplocalVarToLocSet(localVarDesc); // add the field/var descriptor to the set of the location symbol - int flowNodeTupleSize = flowNode.getDescTuple().size(); - Descriptor lastFlowNodeDesc = flowNode.getDescTuple().get(flowNodeTupleSize - 1); - int inferLocSize = newInferLocation.getSize(); - Location lastLoc = newInferLocation.get(inferLocSize - 1); - Descriptor enclosingDesc = lastLoc.getDescriptor(); - getLocationInfo(enclosingDesc).addMapLocSymbolToDescSet(lastLoc.getLocIdentifier(), + int lastIdx = flowNode.getLocTuple().size() - 1; + Descriptor lastFlowNodeDesc = flowNode.getDescTuple().get(lastIdx); + Descriptor enclosinglastLastFlowNodeDesc = flowNodelocTuple.get(lastIdx).getDescriptor(); + + CompositeLocation newlyInferredLocForFlowNode = + generateInferredCompositeLocation(methodInfo, flowNodelocTuple); + Location lastInferLocElement = + newlyInferredLocForFlowNode.get(newlyInferredLocForFlowNode.getSize() - 1); + Descriptor enclosingLastInferLocElement = lastInferLocElement.getDescriptor(); + + // getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToDescSet( + // lastInferLocElement.getLocIdentifier(), lastFlowNodeDesc); + getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToRelatedInferLoc( + lastInferLocElement.getLocIdentifier(), enclosinglastLastFlowNodeDesc, lastFlowNodeDesc); // clean up the previous location @@ -1097,6 +3102,7 @@ public class LocationInference { } + System.out.println("curPrefix=" + curPrefix); System.out.println("ASSIGN NEW COMPOSITE LOCATION =" + newInferLocation + " to " + flowNode); @@ -1106,65 +3112,23 @@ public class LocationInference { System.out.println("-- add in-flow"); for (Iterator iterator = incomingCommonPrefixSet.iterator(); iterator.hasNext();) { NTuple tuple = (NTuple) iterator.next(); - System.out.println("--in-flow tuple=" + tuple); Location loc = tuple.get(idx); - String higher = locInfo.getFieldInferLocation(loc.getLocDescriptor()).getLocIdentifier(); + String higher = loc.getLocIdentifier(); addRelationHigherToLower(lattice, locInfo, higher, newlyInsertedLocName); } - System.out.println("-- add local in-flow"); - for (Iterator iterator = localInNodeSet.iterator(); iterator.hasNext();) { - FlowNode localNode = (FlowNode) iterator.next(); - - if (localNode.equals(flowNode)) { - continue; - } - - CompositeLocation inNodeInferLoc = - generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(localNode)); - - if (isCompositeLocation(inNodeInferLoc)) { - // need to make sure that newLocSymbol is lower than the infernode - // location in the field lattice - System.out.println("----srcNode=" + localNode + " dstNode=" + flowNode); - addRelationToLattice(methodInfo.getMethodDesc(), methodLattice, methodInfo, localNode, - flowNode); - - } - - } - 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 = locInfo.getFieldInferLocation(loc.getLocDescriptor()).getLocIdentifier(); + String lower = loc.getLocIdentifier(); + // String lower = + // locInfo.getFieldInferLocation(loc.getLocDescriptor()).getLocIdentifier(); addRelationHigherToLower(lattice, locInfo, newlyInsertedLocName, lower); } } - System.out.println("-- add local out flow"); - for (Iterator iterator = localOutNodeSet.iterator(); iterator.hasNext();) { - FlowNode localOutNode = (FlowNode) iterator.next(); - - if (localOutNode.equals(flowNode)) { - continue; - } - - CompositeLocation outNodeInferLoc = - generateInferredCompositeLocation(methodInfo, - flowGraph.getLocationTuple(localOutNode)); - - if (isCompositeLocation(outNodeInferLoc)) { - System.out.println("--- srcNode=" + flowNode + " dstNode=" + localOutNode); - addRelationToLattice(methodInfo.getMethodDesc(), methodLattice, methodInfo, flowNode, - localOutNode); - - } - } - System.out.println("-- end of add local out flow"); - return true; } @@ -1241,7 +3205,8 @@ public class LocationInference { String newSharedLoc = "SharedLoc" + (SSJavaLattice.seed++); System.out.println("---ASSIGN NEW SHARED LOC=" + newSharedLoc + " to " + cycleElementSet); - lattice.mergeIntoSharedLocation(cycleElementSet, newSharedLoc); + lattice.mergeIntoNewLocation(cycleElementSet, newSharedLoc); + lattice.addSharedLoc(newSharedLoc); for (Iterator iterator = cycleElementSet.iterator(); iterator.hasNext();) { String oldLocSymbol = (String) iterator.next(); @@ -1293,29 +3258,6 @@ public class LocationInference { } - 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(); @@ -1340,11 +3282,45 @@ public class LocationInference { md2lattice.put(md, lattice); } + private void extractFlowsBetweenFields(ClassDescriptor cd, FlowNode srcNode, FlowNode dstNode, + int idx) { + + NTuple srcCurTuple = srcNode.getCurrentDescTuple(); + NTuple dstCurTuple = dstNode.getCurrentDescTuple(); + + if (srcCurTuple.get(idx).equals(dstCurTuple.get(idx)) && srcCurTuple.size() > (idx + 1) + && dstCurTuple.size() > (idx + 1)) { + // value flow between fields: we don't need to add a binary relation + // for this case + + Descriptor desc = srcCurTuple.get(idx); + ClassDescriptor classDesc; + + if (idx == 0) { + classDesc = ((VarDescriptor) desc).getType().getClassDesc(); + } else { + classDesc = ((FieldDescriptor) desc).getType().getClassDesc(); + } + + extractFlowsBetweenFields(classDesc, srcNode, dstNode, idx + 1); + + } else { + + Descriptor srcFieldDesc = srcCurTuple.get(idx); + Descriptor dstFieldDesc = dstCurTuple.get(idx); + + // add a new edge + getHierarchyGraph(cd).addEdge(srcFieldDesc, dstFieldDesc); + + } + + } + private void extractRelationFromFieldFlows(ClassDescriptor cd, FlowNode srcNode, FlowNode dstNode, int idx) throws CyclicFlowException { - if (srcNode.getDescTuple().get(idx).equals(dstNode.getDescTuple().get(idx)) - && srcNode.getDescTuple().size() > (idx + 1) && dstNode.getDescTuple().size() > (idx + 1)) { + if (srcNode.getLocTuple().get(idx).equals(dstNode.getLocTuple().get(idx)) + && srcNode.getLocTuple().size() > (idx + 1) && dstNode.getLocTuple().size() > (idx + 1)) { // value flow between fields: we don't need to add a binary relation // for this case @@ -1381,75 +3357,258 @@ public class LocationInference { if (!cd2lattice.containsKey(cd)) { cd2lattice.put(cd, new SSJavaLattice(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM)); } - return cd2lattice.get(cd); + return cd2lattice.get(cd); + } + + public LinkedList computeMethodList() { + + Set toSort = new HashSet(); + + setupToAnalyze(); + + Set visited = new HashSet(); + Set reachableCallee = new HashSet(); + + while (!toAnalyzeIsEmpty()) { + ClassDescriptor cd = toAnalyzeNext(); + + setupToAnalazeMethod(cd); + temp_toanalyzeMethodList.removeAll(visited); + + while (!toAnalyzeMethodIsEmpty()) { + MethodDescriptor md = toAnalyzeMethodNext(); + if ((!visited.contains(md)) + && (ssjava.needTobeAnnotated(md) || reachableCallee.contains(md))) { + + // creates a mapping from a method descriptor to virtual methods + Set setPossibleCallees = new HashSet(); + if (md.isStatic()) { + setPossibleCallees.add(md); + } else { + setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md)); + } + + Set calleeSet = ssjava.getCallGraph().getCalleeSet(md); + Set needToAnalyzeCalleeSet = new HashSet(); + + for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) { + MethodDescriptor calleemd = (MethodDescriptor) iterator.next(); + if ((!ssjava.isTrustMethod(calleemd)) + && (!ssjava.isSSJavaUtil(calleemd.getClassDesc()))) { + if (!visited.contains(calleemd)) { + temp_toanalyzeMethodList.add(calleemd); + } + reachableCallee.add(calleemd); + needToAnalyzeCalleeSet.add(calleemd); + } + } + + mapMethodToCalleeSet.put(md, needToAnalyzeCalleeSet); + + visited.add(md); + + toSort.add(md); + } + } + } + + return ssjava.topologicalSort(toSort); + + } + + public void constructFlowGraph() { + + System.out.println(""); + toanalyze_methodDescList = computeMethodList(); + + 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 flow graph: " + md); + + // creates a mapping from a parameter descriptor to its index + Map mapParamDescToIdx = new HashMap(); + int offset = 0; + if (!md.isStatic()) { + offset = 1; + mapParamDescToIdx.put(md.getThis(), 0); + } + + for (int i = 0; i < md.numParameters(); i++) { + Descriptor paramDesc = (Descriptor) md.getParameter(i); + mapParamDescToIdx.put(paramDesc, new Integer(i + offset)); + } + + FlowGraph fg = new FlowGraph(md, mapParamDescToIdx); + mapMethodDescriptorToFlowGraph.put(md, fg); + + analyzeMethodBody(md.getClassDesc(), md); + propagateFlowsFromCalleesWithNoCompositeLocation(md); + // assignCompositeLocation(md); + + } + } + _debug_printGraph(); + + } + + private Set getMethodInvokeNodeSet(MethodDescriptor md) { + if (!mapMethodDescriptorToMethodInvokeNodeSet.containsKey(md)) { + mapMethodDescriptorToMethodInvokeNodeSet.put(md, new HashSet()); + } + return mapMethodDescriptorToMethodInvokeNodeSet.get(md); + } + + private void constructSubGlobalFlowGraph(MethodDescriptor md) { + + FlowGraph flowGraph = getFlowGraph(md); + + Set setMethodInvokeNode = getMethodInvokeNodeSet(md); + + for (Iterator iter = setMethodInvokeNode.iterator(); iter.hasNext();) { + MethodInvokeNode min = iter.next(); + propagateFlowsFromMethodInvokeNode(md, min); + } + + } + + private void propagateFlowsFromMethodInvokeNode(MethodDescriptor mdCaller, MethodInvokeNode min) { + // the transformation for a call site propagates flows through parameters + // if the method is virtual, it also grab all relations from any possible + // callees + + MethodDescriptor mdCallee = min.getMethod(); + Set setPossibleCallees = new HashSet(); + if (mdCallee.isStatic()) { + setPossibleCallees.add(mdCallee); + } else { + Set calleeSet = ssjava.getCallGraph().getMethods(mdCallee); + // removes method descriptors that are not invoked by the caller + calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller)); + setPossibleCallees.addAll(calleeSet); + } + + for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) { + MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next(); + contributeCalleeFlows(min, mdCaller, possibleMdCallee); + } + + } + + private void assignCompositeLocation(MethodDescriptor md) { + + FlowGraph flowGraph = getFlowGraph(md); + + Set nodeSet = flowGraph.getNodeSet(); + + next: for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + FlowNode flowNode = (FlowNode) iterator.next(); + + // assign a composite location only to the local variable + if (flowNode.getCurrentDescTuple().size() == 1) { + + List> prefixList = calculatePrefixList(flowGraph, flowNode); + Set reachSet = flowGraph.getReachFlowNodeSetFrom(flowNode); + + for (int i = 0; i < prefixList.size(); i++) { + NTuple curPrefix = prefixList.get(i); + Set> reachableCommonPrefixSet = new HashSet>(); + + for (Iterator iterator2 = reachSet.iterator(); iterator2.hasNext();) { + FlowNode reachNode = (FlowNode) iterator2.next(); + if (reachNode.getCurrentDescTuple().startsWith(curPrefix)) { + reachableCommonPrefixSet.add(reachNode.getCurrentDescTuple()); + } + } + + if (!reachableCommonPrefixSet.isEmpty()) { + System.out.println("NEED TO ASSIGN COMP LOC TO " + flowNode + " with prefix=" + + curPrefix); + CompositeLocation newCompLoc = generateCompositeLocation(md, curPrefix); + flowNode.setCompositeLocation(newCompLoc); + continue next; + } + + } + } + + } + } - public void constructFlowGraph() { + private void propagateFlowsFromCalleesWithNoCompositeLocation(MethodDescriptor mdCaller) { - setupToAnalyze(); + // 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 visited = new HashSet(); - Set reachableCallee = new HashSet(); + Set setMethodInvokeNode = + mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller); - while (!toAnalyzeIsEmpty()) { - ClassDescriptor cd = toAnalyzeNext(); + if (setMethodInvokeNode != null) { - setupToAnalazeMethod(cd); - toanalyzeMethodList.removeAll(visited); + 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); + } - while (!toAnalyzeMethodIsEmpty()) { - MethodDescriptor md = toAnalyzeMethodNext(); - if ((!visited.contains(md)) - && (ssjava.needTobeAnnotated(md) || reachableCallee.contains(md))) { - if (state.SSJAVADEBUG) { - System.out.println(); - System.out.println("SSJAVA: Constructing a flow graph: " + md); - } + for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) { + MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next(); + propagateFlowsToCallerWithNoCompositeLocation(min, mdCaller, possibleMdCallee); + } - // creates a mapping from a method descriptor to virtual methods - Set setPossibleCallees = new HashSet(); - if (md.isStatic()) { - setPossibleCallees.add(md); - } else { - setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md)); - } + } + } - Set calleeSet = ssjava.getCallGraph().getCalleeSet(md); - Set needToAnalyzeCalleeSet = new HashSet(); + } - for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) { - MethodDescriptor calleemd = (MethodDescriptor) iterator.next(); - if ((!ssjava.isTrustMethod(calleemd)) - && (!ssjava.isSSJavaUtil(calleemd.getClassDesc()))) { - if (!visited.contains(calleemd)) { - toanalyzeMethodList.add(calleemd); - } - reachableCallee.add(calleemd); - needToAnalyzeCalleeSet.add(calleemd); - } - } + private void propagateFlowsFromCallees(MethodDescriptor mdCaller) { - mapMethodToCalleeSet.put(md, needToAnalyzeCalleeSet); + // the transformation for a call site propagates flows through parameters + // if the method is virtual, it also grab all relations from any possible + // callees - // creates a mapping from a parameter descriptor to its index - Map mapParamDescToIdx = new HashMap(); - int offset = md.isStatic() ? 0 : 1; - for (int i = 0; i < md.numParameters(); i++) { - Descriptor paramDesc = (Descriptor) md.getParameter(i); - mapParamDescToIdx.put(paramDesc, new Integer(i + offset)); - } + Set setMethodInvokeNode = + mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller); - FlowGraph fg = new FlowGraph(md, mapParamDescToIdx); - mapMethodDescriptorToFlowGraph.put(md, fg); + if (setMethodInvokeNode != null) { - visited.add(md); - analyzeMethodBody(cd, md); + for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) { + MethodInvokeNode min = (MethodInvokeNode) iterator.next(); + MethodDescriptor mdCallee = min.getMethod(); + Set setPossibleCallees = new HashSet(); + if (mdCallee.isStatic()) { + setPossibleCallees.add(mdCallee); + } else { + Set calleeSet = ssjava.getCallGraph().getMethods(mdCallee); + // removes method descriptors that are not invoked by the caller + calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller)); + setPossibleCallees.addAll(calleeSet); + } + for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) { + MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next(); + propagateFlowsToCaller(min, mdCaller, possibleMdCallee); } + } } - _debug_printGraph(); } private void analyzeMethodBody(ClassDescriptor cd, MethodDescriptor md) { @@ -1501,16 +3660,48 @@ public class LocationInference { break; case Kind.SwitchStatementNode: - analyzeSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn); + analyzeSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn, implicitFlowTupleSet); break; } } + private void analyzeSwitchBlockNode(MethodDescriptor md, SymbolTable nametable, + SwitchBlockNode sbn, NodeTupleSet implicitFlowTupleSet) { + + analyzeFlowBlockNode(md, nametable, sbn.getSwitchBlockStatement(), implicitFlowTupleSet); + + } + private void analyzeSwitchStatementNode(MethodDescriptor md, SymbolTable nametable, - SwitchStatementNode bsn) { - // TODO Auto-generated method stub + SwitchStatementNode ssn, NodeTupleSet implicitFlowTupleSet) { + + NodeTupleSet condTupleNode = new NodeTupleSet(); + analyzeFlowExpressionNode(md, nametable, ssn.getCondition(), condTupleNode, null, + implicitFlowTupleSet, false); + + NodeTupleSet newImplicitTupleSet = new NodeTupleSet(); + + newImplicitTupleSet.addTupleSet(implicitFlowTupleSet); + newImplicitTupleSet.addTupleSet(condTupleNode); + + if (newImplicitTupleSet.size() > 1) { + // need to create an intermediate node for the GLB of conditional locations & implicit flows + NTuple interTuple = getFlowGraph(md).createIntermediateNode(md).getDescTuple(); + for (Iterator> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) { + NTuple tuple = idxIter.next(); + addFlowGraphEdge(md, tuple, interTuple); + } + newImplicitTupleSet.clear(); + newImplicitTupleSet.addTuple(interTuple); + } + + BlockNode sbn = ssn.getSwitchBody(); + for (int i = 0; i < sbn.size(); i++) { + analyzeSwitchBlockNode(md, nametable, (SwitchBlockNode) sbn.get(i), newImplicitTupleSet); + } + } private void analyzeFlowSubBlockNode(MethodDescriptor md, SymbolTable nametable, @@ -1525,19 +3716,46 @@ public class LocationInference { if (returnExp != null) { NodeTupleSet nodeSet = new NodeTupleSet(); + // if a return expression returns a literal value, nodeSet is empty analyzeFlowExpressionNode(md, nametable, returnExp, nodeSet, false); - FlowGraph fg = getFlowGraph(md); - // annotate the elements of the node set as the return location - for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { - NTuple returnDescTuple = (NTuple) iterator.next(); - fg.setReturnFlowNode(returnDescTuple); - for (Iterator iterator2 = implicitFlowTupleSet.iterator(); iterator2.hasNext();) { - NTuple implicitFlowDescTuple = (NTuple) iterator2.next(); - fg.addValueFlowEdge(implicitFlowDescTuple, returnDescTuple); + // if (implicitFlowTupleSet.size() == 1 + // && fg.getFlowNode(implicitFlowTupleSet.iterator().next()).isIntermediate()) { + // + // // 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()); + // + // for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + // NTuple returnNodeTuple = (NTuple) iterator.next(); + // fg.addValueFlowEdge(returnNodeTuple, meetNode.getDescTuple()); + // } + // + // } + + NodeTupleSet currentFlowTupleSet = new NodeTupleSet(); + + // add tuples from return node + currentFlowTupleSet.addTupleSet(nodeSet); + + // add tuples corresponding to the current implicit flows + currentFlowTupleSet.addTupleSet(implicitFlowTupleSet); + + if (currentFlowTupleSet.size() > 1) { + FlowNode meetNode = fg.createIntermediateNode(md); + for (Iterator iterator = currentFlowTupleSet.iterator(); iterator.hasNext();) { + NTuple currentFlowTuple = (NTuple) iterator.next(); + fg.addValueFlowEdge(currentFlowTuple, meetNode.getDescTuple()); } + fg.addReturnFlowNode(meetNode.getDescTuple()); + } else if (currentFlowTupleSet.size() == 1) { + NTuple tuple = currentFlowTupleSet.iterator().next(); + fg.addReturnFlowNode(tuple); } + } } @@ -1550,10 +3768,49 @@ public class LocationInference { NodeTupleSet condTupleNode = new NodeTupleSet(); analyzeFlowExpressionNode(md, nametable, ln.getCondition(), condTupleNode, null, implicitFlowTupleSet, false); - condTupleNode.addTupleSet(implicitFlowTupleSet); + + NodeTupleSet newImplicitTupleSet = new NodeTupleSet(); + + newImplicitTupleSet.addTupleSet(implicitFlowTupleSet); + newImplicitTupleSet.addTupleSet(condTupleNode); + + if (newImplicitTupleSet.size() > 1) { + // need to create an intermediate node for the GLB of conditional locations & implicit flows + NTuple interTuple = getFlowGraph(md).createIntermediateNode(md).getDescTuple(); + for (Iterator> idxIter = newImplicitTupleSet.iterator(); idxIter + .hasNext();) { + NTuple tuple = idxIter.next(); + addFlowGraphEdge(md, tuple, interTuple); + } + newImplicitTupleSet.clear(); + newImplicitTupleSet.addTuple(interTuple); + + } + + // /////////// + // System.out.println("condTupleNode="+condTupleNode); + // NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); + // + // for (Iterator> idxIter = condTupleNode.iterator(); idxIter.hasNext();) { + // NTuple tuple = idxIter.next(); + // addFlowGraphEdge(md, tuple, interTuple); + // } + + // for (Iterator> idxIter = implicitFlowTupleSet.iterator(); idxIter + // .hasNext();) { + // NTuple tuple = idxIter.next(); + // addFlowGraphEdge(md, tuple, interTuple); + // } + + // NodeTupleSet newImplicitSet = new NodeTupleSet(); + // newImplicitSet.addTuple(interTuple); + analyzeFlowBlockNode(md, nametable, ln.getBody(), newImplicitTupleSet); + // /////////// + + // condTupleNode.addTupleSet(implicitFlowTupleSet); // add edges from condNodeTupleSet to all nodes of conditional nodes - analyzeFlowBlockNode(md, nametable, ln.getBody(), condTupleNode); + // analyzeFlowBlockNode(md, nametable, ln.getBody(), condTupleNode); } else { // check 'for loop' case @@ -1567,10 +3824,33 @@ public class LocationInference { NodeTupleSet condTupleNode = new NodeTupleSet(); analyzeFlowExpressionNode(md, bn.getVarTable(), ln.getCondition(), condTupleNode, null, implicitFlowTupleSet, false); - condTupleNode.addTupleSet(implicitFlowTupleSet); - analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(), condTupleNode); - analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(), condTupleNode); + // /////////// + NTuple interTuple = getFlowGraph(md).createIntermediateNode(md).getDescTuple(); + + for (Iterator> idxIter = condTupleNode.iterator(); idxIter.hasNext();) { + NTuple tuple = idxIter.next(); + addFlowGraphEdge(md, tuple, interTuple); + } + + for (Iterator> idxIter = implicitFlowTupleSet.iterator(); idxIter + .hasNext();) { + NTuple tuple = idxIter.next(); + addFlowGraphEdge(md, tuple, interTuple); + } + + NodeTupleSet newImplicitSet = new NodeTupleSet(); + newImplicitSet.addTuple(interTuple); + analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(), newImplicitSet); + analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(), newImplicitSet); + // /////////// + + // condTupleNode.addTupleSet(implicitFlowTupleSet); + // + // analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(), + // condTupleNode); + // analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(), + // condTupleNode); } @@ -1579,16 +3859,37 @@ public class LocationInference { private void analyzeFlowIfStatementNode(MethodDescriptor md, SymbolTable nametable, IfStatementNode isn, NodeTupleSet implicitFlowTupleSet) { + System.out.println("analyzeFlowIfStatementNode=" + isn.printNode(0)); + NodeTupleSet condTupleNode = new NodeTupleSet(); analyzeFlowExpressionNode(md, nametable, isn.getCondition(), condTupleNode, null, implicitFlowTupleSet, false); - // add edges from condNodeTupleSet to all nodes of conditional nodes - condTupleNode.addTupleSet(implicitFlowTupleSet); - analyzeFlowBlockNode(md, nametable, isn.getTrueBlock(), condTupleNode); + NodeTupleSet newImplicitTupleSet = new NodeTupleSet(); + + newImplicitTupleSet.addTupleSet(implicitFlowTupleSet); + newImplicitTupleSet.addTupleSet(condTupleNode); + + System.out.println("condTupleNode=" + condTupleNode); + System.out.println("implicitFlowTupleSet=" + implicitFlowTupleSet); + System.out.println("newImplicitTupleSet=" + newImplicitTupleSet); + + if (newImplicitTupleSet.size() > 1) { + + // need to create an intermediate node for the GLB of conditional locations & implicit flows + NTuple interTuple = getFlowGraph(md).createIntermediateNode(md).getDescTuple(); + for (Iterator> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) { + NTuple tuple = idxIter.next(); + addFlowGraphEdge(md, tuple, interTuple); + } + newImplicitTupleSet.clear(); + newImplicitTupleSet.addTuple(interTuple); + } + + analyzeFlowBlockNode(md, nametable, isn.getTrueBlock(), newImplicitTupleSet); if (isn.getFalseBlock() != null) { - analyzeFlowBlockNode(md, nametable, isn.getFalseBlock(), condTupleNode); + analyzeFlowBlockNode(md, nametable, isn.getFalseBlock(), newImplicitTupleSet); } } @@ -1597,20 +3898,33 @@ public class LocationInference { DeclarationNode dn, NodeTupleSet implicitFlowTupleSet) { VarDescriptor vd = dn.getVarDescriptor(); + mapDescToDefinitionLine.put(vd, dn.getNumLine()); NTuple tupleLHS = new NTuple(); tupleLHS.add(vd); - getFlowGraph(md).createNewFlowNode(tupleLHS); + FlowNode fn = getFlowGraph(md).createNewFlowNode(tupleLHS); + fn.setDeclarationNode(); if (dn.getExpression() != null) { - NodeTupleSet tupleSetRHS = new NodeTupleSet(); - analyzeFlowExpressionNode(md, nametable, dn.getExpression(), tupleSetRHS, null, + NodeTupleSet nodeSetRHS = new NodeTupleSet(); + analyzeFlowExpressionNode(md, nametable, dn.getExpression(), nodeSetRHS, null, implicitFlowTupleSet, false); - // add a new flow edge from rhs to lhs - for (Iterator> iter = tupleSetRHS.iterator(); iter.hasNext();) { - NTuple from = iter.next(); - addFlowGraphEdge(md, from, tupleLHS); + // creates edges from RHS to LHS + NTuple interTuple = null; + if (nodeSetRHS.size() > 1) { + interTuple = getFlowGraph(md).createIntermediateNode(md).getDescTuple(); + } + + for (Iterator> iter = nodeSetRHS.iterator(); iter.hasNext();) { + NTuple fromTuple = iter.next(); + addFlowGraphEdge(md, fromTuple, interTuple, tupleLHS); + } + + // creates edges from implicitFlowTupleSet to LHS + for (Iterator> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) { + NTuple implicitTuple = iter.next(); + addFlowGraphEdge(md, implicitTuple, tupleLHS); } } @@ -1680,7 +3994,8 @@ public class LocationInference { break; case Kind.MethodInvokeNode: - analyzeFlowMethodInvokeNode(md, nametable, (MethodInvokeNode) en, implicitFlowTupleSet); + analyzeFlowMethodInvokeNode(md, nametable, (MethodInvokeNode) en, nodeSet, + implicitFlowTupleSet); break; case Kind.TertiaryNode: @@ -1749,12 +4064,26 @@ public class LocationInference { set.add(min); } + private void addParamNodeFlowingToReturnValue(MethodDescriptor md, FlowNode fn) { + + if (!mapMethodDescToParamNodeFlowsToReturnValue.containsKey(md)) { + mapMethodDescToParamNodeFlowsToReturnValue.put(md, new HashSet()); + } + mapMethodDescToParamNodeFlowsToReturnValue.get(md).add(fn); + } + + private Set getParamNodeFlowingToReturnValue(MethodDescriptor md) { + return mapMethodDescToParamNodeFlowsToReturnValue.get(md); + } + private void analyzeFlowMethodInvokeNode(MethodDescriptor md, SymbolTable nametable, - MethodInvokeNode min, NodeTupleSet implicitFlowTupleSet) { + MethodInvokeNode min, NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) { - addMapCallerMethodDescToMethodInvokeNodeSet(md, min); + if (nodeSet == null) { + nodeSet = new NodeTupleSet(); + } - MethodDescriptor calleeMD = min.getMethod(); + MethodDescriptor calleeMethodDesc = min.getMethod(); NameDescriptor baseName = min.getBaseName(); boolean isSystemout = false; @@ -1762,111 +4091,127 @@ public class LocationInference { isSystemout = baseName.getSymbol().equals("System.out"); } - if (!ssjava.isSSJavaUtil(calleeMD.getClassDesc()) && !ssjava.isTrustMethod(calleeMD) - && !calleeMD.getModifiers().isNative() && !isSystemout) { + if (!ssjava.isSSJavaUtil(calleeMethodDesc.getClassDesc()) + && !ssjava.isTrustMethod(calleeMethodDesc) && !isSystemout) { + + addMapCallerMethodDescToMethodInvokeNodeSet(md, min); + + FlowGraph calleeFlowGraph = getFlowGraph(calleeMethodDesc); + Set calleeReturnSet = calleeFlowGraph.getReturnNodeSet(); + + System.out.println("#calleeReturnSet=" + calleeReturnSet); - // CompositeLocation baseLocation = null; if (min.getExpression() != null) { NodeTupleSet baseNodeSet = new NodeTupleSet(); analyzeFlowExpressionNode(md, nametable, min.getExpression(), baseNodeSet, null, implicitFlowTupleSet, false); - } else { + assert (baseNodeSet.size() == 1); + NTuple baseTuple = baseNodeSet.iterator().next(); + mapMethodInvokeNodeToBaseTuple.put(min, baseTuple); + + if (!min.getMethod().isStatic()) { + addArgIdxMap(min, 0, baseTuple); + + for (Iterator iterator = calleeReturnSet.iterator(); iterator.hasNext();) { + FlowNode returnNode = (FlowNode) iterator.next(); + NTuple returnDescTuple = returnNode.getDescTuple(); + if (returnDescTuple.startsWith(calleeMethodDesc.getThis())) { + // the location type of the return value is started with 'this' + // reference + NTuple inFlowTuple = new NTuple(baseTuple.getList()); + inFlowTuple.addAll(returnDescTuple.subList(1, returnDescTuple.size())); + nodeSet.addTuple(inFlowTuple); + } else { + // TODO + Set inFlowSet = calleeFlowGraph.getIncomingFlowNodeSet(returnNode); + for (Iterator iterator2 = inFlowSet.iterator(); iterator2.hasNext();) { + FlowNode inFlowNode = (FlowNode) iterator2.next(); + if (inFlowNode.getDescTuple().startsWith(calleeMethodDesc.getThis())) { + nodeSet.addTupleSet(baseNodeSet); + } + } + } + } + } + + } + + // analyze parameter flows + + if (min.numArgs() > 0) { + + int offset; if (min.getMethod().isStatic()) { - // String globalLocId = ssjava.getMethodLattice(md).getGlobalLoc(); - // if (globalLocId == null) { - // throw new - // Error("Method lattice does not define global variable location at " - // + generateErrorMessage(md.getClassDesc(), min)); - // } - // baseLocation = new CompositeLocation(new Location(md, - // globalLocId)); + offset = 0; } else { - // 'this' var case - // String thisLocId = ssjava.getMethodLattice(md).getThisLoc(); - // baseLocation = new CompositeLocation(new Location(md, thisLocId)); - } - } - - // constraint case: - // if (constraint != null) { - // int compareResult = - // CompositeLattice.compare(constraint, baseLocation, true, - // generateErrorMessage(cd, min)); - // if (compareResult != ComparisonResult.GREATER) { - // // if the current constraint is higher than method's THIS location - // // no need to check constraints! - // CompositeLocation calleeConstraint = - // translateCallerLocToCalleeLoc(calleeMD, baseLocation, constraint); - // // System.out.println("check method body for constraint:" + calleeMD + - // // " calleeConstraint=" - // // + calleeConstraint); - // checkMethodBody(calleeMD.getClassDesc(), calleeMD, calleeConstraint); - // } - // } - - analyzeFlowMethodParameters(md, nametable, min); + offset = 1; + } - // checkCalleeConstraints(md, nametable, min, baseLocation, constraint); + for (int i = 0; i < min.numArgs(); i++) { + ExpressionNode en = min.getArg(i); + int idx = i + offset; + NodeTupleSet argTupleSet = new NodeTupleSet(); + analyzeFlowExpressionNode(md, nametable, en, argTupleSet, false); + // if argument is liternal node, argTuple is set to NULL. + + NTuple argTuple = new NTuple(); + if (argTupleSet.size() > 1) { + NTuple interTuple = + getFlowGraph(md).createIntermediateNode(md).getDescTuple(); + for (Iterator> idxIter = argTupleSet.iterator(); idxIter.hasNext();) { + NTuple tuple = idxIter.next(); + addFlowGraphEdge(md, tuple, interTuple); + } + argTuple = interTuple; + } else { + argTuple = argTupleSet.iterator().next(); + } - // checkCallerArgumentLocationConstraints(md, nametable, min, - // baseLocation, constraint); + addArgIdxMap(min, idx, argTuple); + FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx); + if (hasInFlowTo(calleeFlowGraph, paramNode, calleeReturnSet) + || calleeMethodDesc.getModifiers().isNative()) { + addParamNodeFlowingToReturnValue(calleeMethodDesc, paramNode); + nodeSet.addTupleSet(argTupleSet); + } + } - if (min.getMethod().getReturnType() != null && !min.getMethod().getReturnType().isVoid()) { - // If method has a return value, compute the highest possible return - // location in the caller's perspective - // CompositeLocation ceilingLoc = - // computeCeilingLocationForCaller(md, nametable, min, baseLocation, - // constraint); - // return ceilingLoc; } - } - // return new CompositeLocation(Location.createTopLocation(md)); + // propagateFlowsFromCallee(min, md, min.getMethod()); - } + } - private NodeTupleSet getNodeTupleSetByArgIdx(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 boolean hasInFlowTo(FlowGraph fg, FlowNode inNode, Set nodeSet) { + // return true if inNode has in-flows to nodeSet + Set reachableSet = fg.getReachFlowNodeSetFrom(inNode); + for (Iterator iterator = reachableSet.iterator(); iterator.hasNext();) { + FlowNode fn = (FlowNode) iterator.next(); + if (nodeSet.contains(fn)) { + return true; + } } - mapIdxToTupleSet.put(new Integer(idx), tupleSet); + return false; } - private void analyzeFlowMethodParameters(MethodDescriptor callermd, SymbolTable nametable, - MethodInvokeNode min) { - - 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); - } - - 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); - } + private NTuple getNodeTupleByArgIdx(MethodInvokeNode min, int idx) { + return mapMethodInvokeNodeToArgIdxMap.get(min).get(new Integer(idx)); + } + 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) { @@ -1877,7 +4222,8 @@ public class LocationInference { ArrayAccessNode aan, NodeTupleSet nodeSet, boolean isLHS) { NodeTupleSet expNodeTupleSet = new NodeTupleSet(); - analyzeFlowExpressionNode(md, nametable, aan.getExpression(), expNodeTupleSet, isLHS); + NTuple base = + analyzeFlowExpressionNode(md, nametable, aan.getExpression(), expNodeTupleSet, isLHS); NodeTupleSet idxNodeTupleSet = new NodeTupleSet(); analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, isLHS); @@ -1968,6 +4314,8 @@ public class LocationInference { private NTuple analyzeFlowNameNode(MethodDescriptor md, SymbolTable nametable, NameNode nn, NodeTupleSet nodeSet, NTuple base, NodeTupleSet implicitFlowTupleSet) { + // System.out.println("analyzeFlowNameNode=" + nn.printNode(0)); + if (base == null) { base = new NTuple(); } @@ -2018,7 +4366,7 @@ public class LocationInference { } else if (d == null) { // access static field base.add(GLOBALDESC); - // base.add(nn.getField()); + base.add(nn.getField()); return base; // FieldDescriptor fd = nn.getField();addFlowGraphEdge @@ -2039,7 +4387,6 @@ public class LocationInference { } } - getFlowGraph(md).createNewFlowNode(base); return base; @@ -2068,12 +4415,14 @@ public class LocationInference { } NodeTupleSet idxNodeTupleSet = new NodeTupleSet(); + if (left instanceof ArrayAccessNode) { ArrayAccessNode aan = (ArrayAccessNode) left; left = aan.getExpression(); analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, base, implicitFlowTupleSet, isLHS); + nodeSet.addTupleSet(idxNodeTupleSet); } base = @@ -2103,7 +4452,6 @@ public class LocationInference { getFlowGraph(md).addValueFlowEdge(idxTuple, flowFieldTuple); } } - return flowFieldTuple; } @@ -2147,6 +4495,7 @@ public class LocationInference { if (an.getOperation().getOp() >= 2 && an.getOperation().getOp() <= 12) { // if assignment contains OP+EQ operator, creates edges from LHS to LHS + for (Iterator> iter = nodeSetLHS.iterator(); iter.hasNext();) { NTuple fromTuple = iter.next(); for (Iterator> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) { @@ -2157,11 +4506,16 @@ public class LocationInference { } // creates edges from RHS to LHS + NTuple interTuple = null; + if (nodeSetRHS.size() > 1) { + interTuple = getFlowGraph(md).createIntermediateNode(md).getDescTuple(); + } + for (Iterator> iter = nodeSetRHS.iterator(); iter.hasNext();) { NTuple fromTuple = iter.next(); for (Iterator> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) { NTuple toTuple = iter2.next(); - addFlowGraphEdge(md, fromTuple, toTuple); + addFlowGraphEdge(md, fromTuple, interTuple, toTuple); } } @@ -2176,6 +4530,7 @@ public class LocationInference { } else { // postinc case + for (Iterator> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) { NTuple tuple = iter2.next(); addFlowGraphEdge(md, tuple, tuple); @@ -2203,13 +4558,119 @@ public class LocationInference { private boolean addFlowGraphEdge(MethodDescriptor md, NTuple from, NTuple to) { - // TODO - // return true if it adds a new edge FlowGraph graph = getFlowGraph(md); graph.addValueFlowEdge(from, to); return true; } + private void addFlowGraphEdge(MethodDescriptor md, NTuple from, + NTuple inter, NTuple to) { + + FlowGraph graph = getFlowGraph(md); + + if (inter != null) { + graph.addValueFlowEdge(from, inter); + graph.addValueFlowEdge(inter, to); + } else { + graph.addValueFlowEdge(from, to); + } + + } + + 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(); @@ -2230,3 +4691,11 @@ public class LocationInference { class CyclicFlowException extends Exception { } + +class InterDescriptor extends Descriptor { + + public InterDescriptor(String name) { + super(name); + } + +}