X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=Robust%2Fsrc%2FAnalysis%2FSSJava%2FLocationInference.java;h=caa4504a13c5e29cf88e7ed2c523e1bb5f9f9876;hb=cbc13efe1afc46ef542fde526361b4911d3da0e1;hp=b1399149b3e1ca4f6eb1079b7a56be3056b2ad37;hpb=9e11ce79473fe199b045066b384fdfed8eb022ea;p=IRC.git diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index b1399149..caa4504a 100644 --- a/Robust/src/Analysis/SSJava/LocationInference.java +++ b/Robust/src/Analysis/SSJava/LocationInference.java @@ -27,6 +27,7 @@ import IR.Operation; import IR.State; import IR.SymbolTable; import IR.TypeDescriptor; +import IR.TypeUtil; import IR.VarDescriptor; import IR.Tree.ArrayAccessNode; import IR.Tree.AssignmentNode; @@ -55,14 +56,20 @@ import Util.Pair; public class LocationInference { + static int COUNT = 0; + State state; SSJavaAnalysis ssjava; + TypeUtil tu; List temp_toanalyzeList; List temp_toanalyzeMethodList; Map mapMethodDescriptorToFlowGraph; LinkedList toanalyze_methodDescList; + Set toanalyze_classDescSet; + + // InheritanceTree inheritanceTree; // map a method descriptor to its set of parameter descriptors Map> mapMethodDescriptorToParamDescSet; @@ -70,6 +77,9 @@ public class LocationInference { // keep current descriptors to visit in fixed-point interprocedural analysis, private Stack methodDescriptorsToVisitStack; + // map a descriptor to a naive lattice + private Map> desc2naiveLattice; + // map a class descriptor to a field lattice private Map> cd2lattice; @@ -98,6 +108,8 @@ public class LocationInference { private Map> mapMethodInvokeNodeToBaseTuple; + private Map>> mapMethodInvokeNodeToPCLocTupleSet; + private Map mapMethodDescToMethodLocationInfo; private Map mapClassToLocationInfo; @@ -112,44 +124,81 @@ public class LocationInference { private Map mapDescToLocationSummary; + private Map> mapMethodDescToMethodInvokeNodeSet; + // maps a method descriptor to a sub global flow graph that captures all value flows caused by the // set of callees reachable from the method private Map mapMethodDescriptorToSubGlobalFlowGraph; private Map, NTuple>> mapMethodInvokeNodeToMapCallerArgToCalleeArg; - public static final String GLOBALLOC = "GLOBALLOC"; + private Map mapMethodDescriptorToCompositeReturnCase; + + private Map mapMethodDescToHighestOverriddenMethodDesc; - public static final String TOPLOC = "TOPLOC"; + private Map> mapHighestOverriddenMethodDescToMethodDescSet; + + private Map> mapHighestOverriddenMethodDescToReturnLocTuple; + + private Map> mapHighestOverriddenMethodDescToPCLocTuple; + + private Map>> mapHighestOverriddenMethodDescToSetLowerThanPCLoc; + + private Map>> mapHighestOverriddenMethodDescToSetHigherThanRETURNLoc; + + public static final String GLOBALLOC = "GLOBALLOC"; public static final String INTERLOC = "INTERLOC"; - public static final String PCLOC = "PCLOC"; + public static final String PCLOC = "_PCLOC_"; - public static final String RLOC = "RLOC"; + public static final String RLOC = "_RLOC_"; public static final Descriptor GLOBALDESC = new NameDescriptor(GLOBALLOC); - public static final Descriptor TOPDESC = new NameDescriptor(TOPLOC); + public static final Descriptor TOPDESC = new NameDescriptor(SSJavaAnalysis.TOP); + + public static final Descriptor BOTTOMDESC = new NameDescriptor(SSJavaAnalysis.BOTTOM); public static final Descriptor RETURNLOC = new NameDescriptor(RLOC); + public static final Descriptor LITERALDESC = new NameDescriptor("LITERAL"); + + public static final HNode TOPHNODE = new HNode(TOPDESC); + + public static final HNode BOTTOMHNODE = new HNode(BOTTOMDESC); + public static String newline = System.getProperty("line.separator"); LocationInfo curMethodInfo; + private boolean hasChanges = false; + boolean debug = true; - private static int locSeed = 0; + public static int locSeed = 0; + + private Stack arrayAccessNodeStack; + + private ClassDescriptor rootClassDescriptor; + + private BuildLattice buildLattice; - public LocationInference(SSJavaAnalysis ssjava, State state) { + public static int numLocationsSInfer = 0; + public static int numLocationsNaive = 0; + + public LocationInference(SSJavaAnalysis ssjava, State state, TypeUtil tu) { this.ssjava = ssjava; this.state = state; + this.tu = tu; + this.toanalyze_classDescSet = new HashSet(); this.temp_toanalyzeList = new ArrayList(); this.temp_toanalyzeMethodList = new ArrayList(); this.mapMethodDescriptorToFlowGraph = new HashMap(); this.cd2lattice = new HashMap>(); this.md2lattice = new HashMap>(); + this.desc2naiveLattice = new HashMap>(); + this.methodDescriptorsToVisitStack = new Stack(); this.mapMethodDescriptorToMethodInvokeNodeSet = new HashMap>(); @@ -180,6 +229,35 @@ public class LocationInference { this.mapMethodInvokeNodeToMapCallerArgToCalleeArg = new HashMap, NTuple>>(); + this.mapMethodInvokeNodeToPCLocTupleSet = + new HashMap>>(); + + this.arrayAccessNodeStack = new Stack(); + + this.mapMethodDescToMethodInvokeNodeSet = + new HashMap>(); + + this.mapMethodDescriptorToCompositeReturnCase = new HashMap(); + + mapMethodDescToHighestOverriddenMethodDesc = new HashMap(); + + mapHighestOverriddenMethodDescToSetLowerThanPCLoc = + new HashMap>>(); + + mapHighestOverriddenMethodDescToMethodDescSet = + new HashMap>(); + + mapHighestOverriddenMethodDescToReturnLocTuple = + new HashMap>(); + + mapHighestOverriddenMethodDescToPCLocTuple = + new HashMap>(); + + mapHighestOverriddenMethodDescToSetHigherThanRETURNLoc = + new HashMap>>(); + + this.buildLattice = new BuildLattice(this); + } public void setupToAnalyze() { @@ -223,19 +301,30 @@ public class LocationInference { public void inference() { + ssjava.init(); + // construct value flow graph constructFlowGraph(); + constructGlobalFlowGraph(); + + checkReturnNodes(); + assignCompositeLocation(); + updateFlowGraph(); + calculateExtraLocations(); + addAdditionalOrderingConstraints(); - // System.exit(0); + _debug_writeFlowGraph(); + + buildInheritanceTree(); + calculateReturnPCLocInheritance(); constructHierarchyGraph(); - debug_writeHierarchyDotFiles(); + addInheritanceConstraintsToHierarchyGraph(); - // calculate RETURNLOC,PCLOC - calculateExtraLocations(); + debug_writeHierarchyDotFiles(); simplifyHierarchyGraph(); @@ -249,7 +338,8 @@ public class LocationInference { debug_writeSkeletonCombinationHierarchyDotFiles(); - buildLattice(); + buildLatticeInheritanceTree(); + // buildLattice(); debug_writeLattices(); @@ -259,10 +349,620 @@ public class LocationInference { generateAnnoatedCode(); + for (Iterator iterator = cd2lattice.keySet().iterator(); iterator.hasNext();) { + ClassDescriptor cd = (ClassDescriptor) iterator.next(); + SSJavaLattice lattice = getLattice(cd); + HierarchyGraph hg = mapDescriptorToHierarchyGraph.get(cd); + // System.out.println("~~~\t" + cd + "\t" + lattice.getKeySet().size() + "\t" + // + hg.getNodeSet().size()); + } + + for (Iterator iterator = md2lattice.keySet().iterator(); iterator.hasNext();) { + MethodDescriptor md = (MethodDescriptor) iterator.next(); + SSJavaLattice locOrder = getLattice(md); + // writeLatticeDotFile(md.getClassDesc(), md, getMethodLattice(md)); + HierarchyGraph hg = mapDescriptorToHierarchyGraph.get(md); + // System.out.println("~~~\t" + md.getClassDesc() + "_" + md + "\t" + // + locOrder.getKeySet().size() + "\t" + hg.getNodeSet().size()); + } + + if (state.SSJAVA_INFER_NAIVE_WRITEDOTS) { + System.out.println("The number of elements: Naive=" + numLocationsNaive); + } + System.out.println("The number of elements: SInfer=" + numLocationsSInfer); + System.exit(0); } + private void calculateReturnPCLocInheritance() { + calculateHighestPCLocInheritance(); + calculateLowestReturnLocInheritance(); + updateFlowGraphPCReturnLocInheritance(); + } + + private void updateFlowGraphPCReturnLocInheritance() { + + Set keySet = mapHighestOverriddenMethodDescToMethodDescSet.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + MethodDescriptor highestMethodDesc = (MethodDescriptor) iterator.next(); + + if (mapHighestOverriddenMethodDescToMethodDescSet.get(highestMethodDesc).size() == 1) { + continue; + } + + Set methodDescSet = + mapHighestOverriddenMethodDescToMethodDescSet.get(highestMethodDesc); + + NTuple highestPCLocDescTuple = + mapHighestOverriddenMethodDescToPCLocTuple.get(highestMethodDesc); + + NTuple highestRETURNLocDescTuple = + mapHighestOverriddenMethodDescToReturnLocTuple.get(highestMethodDesc); + + // System.out.println("\n$$$$$$$$$$$$$$$$updateFlowGraphPCReturnLocInheritance=" + // + highestMethodDesc); + // System.out.println("-----highestPCLoc=" + highestPCLocDescTuple); + // System.out.println("-----highestRETURNLoc=" + highestRETURNLocDescTuple); + + for (Iterator iterator2 = methodDescSet.iterator(); iterator2.hasNext();) { + MethodDescriptor md = (MethodDescriptor) iterator2.next(); + // System.out.println("\n --------MD=" + md); + FlowGraph flowGraph = getFlowGraph(md); + + MethodSummary summary = getMethodSummary(md); + CompositeLocation curPCLoc = summary.getPCLoc(); + NTuple curPCDescTuple = translateToDescTuple(curPCLoc.getTuple()); + // System.out.println("md=" + md + " curPCLoc=" + curPCLoc); + // System.out.println("highestPCLoc=" + highestPCLocDescTuple); + + if (highestPCLocDescTuple == null) { + // this case: PCLOC is top + // System.out.println("###SET PCLOC AS TOP"); + if (curPCDescTuple != null && !curPCLoc.get(0).isTop()) { + FlowNode pcFlowNode = flowGraph.getFlowNode(curPCDescTuple); + flowGraph.removeNode(pcFlowNode); + } + summary.setPCLoc(new CompositeLocation(new Location(md, Location.TOP))); + } else { + NTuple newPCDescTuple = new NTuple(); + if (highestPCLocDescTuple.size() == 1) { + newPCDescTuple.add(highestPCLocDescTuple.get(0)); + } else { + newPCDescTuple.add(md.getThis()); + newPCDescTuple.add(highestPCLocDescTuple.get(1)); + } + if (!curPCDescTuple.equals(newPCDescTuple)) { + FlowNode pcFlowNode = flowGraph.getFlowNode(curPCDescTuple); + flowGraph.updateTuple(pcFlowNode, newPCDescTuple); + // flowGraph.removeNode(pcFlowNode); + Set> descSetLowerThanPCLoc = + mapHighestOverriddenMethodDescToSetLowerThanPCLoc.get(highestMethodDesc); + for (Iterator iterator3 = descSetLowerThanPCLoc.iterator(); iterator3.hasNext();) { + NTuple lowerNTuple = (NTuple) iterator3.next(); + flowGraph.addValueFlowEdge(newPCDescTuple, lowerNTuple); + } + CompositeLocation newPCCompLoc = + new CompositeLocation(translateToLocTuple(md, newPCDescTuple)); + summary.setPCLoc(newPCCompLoc); + } + + } + + // update return loc + if (highestRETURNLocDescTuple != null) { + CompositeLocation curRETURNLoc = summary.getRETURNLoc(); + NTuple curReturnDescTuple = translateToDescTuple(curRETURNLoc.getTuple()); + + if (!curReturnDescTuple.equals(highestRETURNLocDescTuple)) { + // handle the case that RETURNLOC is started with 'this'... + NTuple newRETURNLocDescTuple = new NTuple(); + if (highestRETURNLocDescTuple.size() == 1) { + newRETURNLocDescTuple.add(highestRETURNLocDescTuple.get(0)); + } else { + newRETURNLocDescTuple.add(md.getThis()); + newRETURNLocDescTuple.add(highestRETURNLocDescTuple.get(1)); + } + + FlowNode returnFlowNode = flowGraph.getFlowNode(curReturnDescTuple); + flowGraph.updateTuple(returnFlowNode, newRETURNLocDescTuple); + + Set> descSetHigherThanRETURNLoc = + mapHighestOverriddenMethodDescToSetHigherThanRETURNLoc.get(highestMethodDesc); + for (Iterator iterator3 = descSetHigherThanRETURNLoc.iterator(); iterator3.hasNext();) { + NTuple higherNTuple = (NTuple) iterator3.next(); + flowGraph.addValueFlowEdge(higherNTuple, newRETURNLocDescTuple); + } + + CompositeLocation newRETURNLocCompLoc = + new CompositeLocation(translateToLocTuple(md, newRETURNLocDescTuple)); + summary.setRETURNLoc(newRETURNLocCompLoc); + } + } + } + } + } + + private void calculateHighestPCLocInheritance() { + + Set keySet = mapHighestOverriddenMethodDescToMethodDescSet.keySet(); + + Map mapMethodDescToParamCount = + new HashMap(); + + next: for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + MethodDescriptor highestMethodDesc = (MethodDescriptor) iterator.next(); + + NTuple tempTuple = null; + + if (getMethodSummary(highestMethodDesc).getPCLoc() != null) { + + Set methodDescSet = + mapHighestOverriddenMethodDescToMethodDescSet.get(highestMethodDesc); + + if (methodDescSet.size() > 1) { + // System.out.println("---method desc set=" + methodDescSet + " from=" + + // highestMethodDesc); + } else { + continue next; + } + + for (Iterator iterator2 = methodDescSet.iterator(); iterator2.hasNext();) { + MethodDescriptor md = (MethodDescriptor) iterator2.next(); + + FlowGraph flowGraph = getFlowGraph(md); + if (flowGraph == null) { + continue; + } + Set paramNodeSet = flowGraph.getParamFlowNodeSet(); + // System.out.println("###md=" + md + " paramNodeSet=" + paramNodeSet); + + CompositeLocation pcLOC = getMethodSummary(md).getPCLoc(); + // System.out.println("---pcLOC=" + pcLOC); + + if (md.equals(highestMethodDesc)) { + mapHighestOverriddenMethodDescToPCLocTuple.put(highestMethodDesc, + translateToDescTuple(pcLOC.getTuple())); + } + + if (!pcLOC.get(0).isTop()) { + + FlowNode pcFlowNode = flowGraph.getFlowNode(translateToDescTuple(pcLOC.getTuple())); + + int count = 0; + for (Iterator iterator3 = paramNodeSet.iterator(); iterator3.hasNext();) { + FlowNode paramNode = (FlowNode) iterator3.next(); + if (flowGraph.getReachableSetFrom(pcFlowNode.getCurrentDescTuple().subList(0, 1)) + .contains(paramNode)) { + count++; + } + } + mapMethodDescToParamCount.put(md, count); + + } else { + + // the PC location is top + // if one of pcloc among the method inheritance chain has the TOP, + // all methods in the same chain should have the TOP. + mapHighestOverriddenMethodDescToPCLocTuple.remove(highestMethodDesc); + // System.out.println("highest=" + highestMethodDesc + " HIGHEST PCLOC=" + // + mapHighestOverriddenMethodDescToPCLocTuple.get(highestMethodDesc)); + + Set> descTupleSetLowerThanPC = new HashSet>(); + for (Iterator iterator3 = paramNodeSet.iterator(); iterator3.hasNext();) { + FlowNode flowNode = (FlowNode) iterator3.next(); + descTupleSetLowerThanPC.add(flowNode.getCurrentDescTuple()); + } + mapHighestOverriddenMethodDescToSetLowerThanPCLoc.put(highestMethodDesc, + descTupleSetLowerThanPC); + + continue next; + } + } + + // identify which method in the inheritance chain has the highest PCLOC + // basically, finds a method that has the highest count or TOP location + int highestCount = -1; + MethodDescriptor methodDescHighestCount = null; + for (Iterator iterator2 = methodDescSet.iterator(); iterator2.hasNext();) { + MethodDescriptor methodDesc = (MethodDescriptor) iterator2.next(); + if (mapMethodDescToParamCount.containsKey(methodDesc)) { + int curCount = mapMethodDescToParamCount.get(methodDesc).intValue(); + if (highestCount < curCount) { + highestCount = curCount; + methodDescHighestCount = methodDesc; + } + } + } + + if (methodDescHighestCount != null) { + FlowGraph flowGraph = getFlowGraph(methodDescHighestCount); + CompositeLocation pcLOC = getMethodSummary(methodDescHighestCount).getPCLoc(); + FlowNode pcFlowNode = flowGraph.getFlowNode(translateToDescTuple(pcLOC.getTuple())); + Set reachableSet = + flowGraph.getReachableSetFrom(pcFlowNode.getCurrentDescTuple().subList(0, 1)); + + Set reachableParamNodeSet = new HashSet(); + for (Iterator iterator3 = reachableSet.iterator(); iterator3.hasNext();) { + FlowNode flowNode = (FlowNode) iterator3.next(); + if (flowGraph.isParameter(flowNode.getCurrentDescTuple())) { + reachableParamNodeSet.add(flowNode); + } + + } + + Set> descTupleSetLowerThanPC = new HashSet>(); + for (Iterator iterator2 = reachableParamNodeSet.iterator(); iterator2.hasNext();) { + FlowNode flowNode = (FlowNode) iterator2.next(); + descTupleSetLowerThanPC.add(flowNode.getCurrentDescTuple()); + } + + // mapHighestOverriddenMethodDescToPCLocTuple.remove(highestMethodDesc); + mapHighestOverriddenMethodDescToSetLowerThanPCLoc.put(highestMethodDesc, + descTupleSetLowerThanPC); + } + + } + + // System.out.println("####################################"); + // System.out.println(" highest=" + highestMethodDesc + " HIGHEST PCLOC=" + // + mapHighestOverriddenMethodDescToPCLocTuple.get(highestMethodDesc)); + // System.out.println(" setLowerThanPCLoc=" + // + mapHighestOverriddenMethodDescToSetLowerThanPCLoc.get(highestMethodDesc)); + } + + } + + private void calculateLowestReturnLocInheritance() { + + Set keySet = mapHighestOverriddenMethodDescToMethodDescSet.keySet(); + + Map mapMethodDescToParamCount = + new HashMap(); + + next: for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + MethodDescriptor highestMethodDesc = (MethodDescriptor) iterator.next(); + + Set methodDescSet = + mapHighestOverriddenMethodDescToMethodDescSet.get(highestMethodDesc); + + if (methodDescSet.size() > 1 && getMethodSummary(highestMethodDesc).getRETURNLoc() != null) { + } else { + continue next; + } + + for (Iterator iterator2 = methodDescSet.iterator(); iterator2.hasNext();) { + MethodDescriptor md = (MethodDescriptor) iterator2.next(); + + FlowGraph flowGraph = getFlowGraph(md); + Set paramNodeSet = flowGraph.getParamFlowNodeSet(); + + CompositeLocation returnLoc = getMethodSummary(md).getRETURNLoc(); + + FlowNode returnFlowNode = flowGraph.getFlowNode(translateToDescTuple(returnLoc.getTuple())); + + int count = 0; + for (Iterator iterator3 = paramNodeSet.iterator(); iterator3.hasNext();) { + FlowNode paramNode = (FlowNode) iterator3.next(); + if (flowGraph.getReachableSetFrom(paramNode.getCurrentDescTuple().subList(0, 1)) + .contains(returnFlowNode)) { + count++; + } + } + mapMethodDescToParamCount.put(md, count); + // System.out.println("###returnLoc=" + returnLoc + " count higher=" + count); + } + + // identify which method in the inheritance chain has the highest PCLOC + // basically, finds a method that has the highest count or TOP location + int highestCount = -1; + MethodDescriptor methodDescHighestCount = null; + for (Iterator iterator2 = methodDescSet.iterator(); iterator2.hasNext();) { + MethodDescriptor methodDesc = (MethodDescriptor) iterator2.next(); + int curCount = mapMethodDescToParamCount.get(methodDesc).intValue(); + if (highestCount < curCount) { + highestCount = curCount; + methodDescHighestCount = methodDesc; + } + } + + if (methodDescHighestCount != null) { + FlowGraph flowGraph = getFlowGraph(methodDescHighestCount); + CompositeLocation returnLOC = getMethodSummary(methodDescHighestCount).getRETURNLoc(); + NTuple returnLocTuple = translateToDescTuple(returnLOC.getTuple()); + FlowNode returnFlowNode = flowGraph.getFlowNode(returnLocTuple); + + Set curMethodParamNodeSet = flowGraph.getParamFlowNodeSet(); + Set> descTupleSetHigherThanPC = new HashSet>(); + for (Iterator iterator3 = curMethodParamNodeSet.iterator(); iterator3.hasNext();) { + FlowNode paramNode = (FlowNode) iterator3.next(); + if (flowGraph.getReachableSetFrom(paramNode.getCurrentDescTuple().subList(0, 1)) + .contains(returnFlowNode)) { + descTupleSetHigherThanPC.add(paramNode.getCurrentDescTuple()); + } + } + + mapHighestOverriddenMethodDescToReturnLocTuple.put(highestMethodDesc, returnLocTuple); + mapHighestOverriddenMethodDescToSetHigherThanRETURNLoc.put(highestMethodDesc, + descTupleSetHigherThanPC); + + } + + // System.out.println("####################################"); + // System.out.println(" highest=" + highestMethodDesc + " LOWEST RETURNLOC=" + // + mapHighestOverriddenMethodDescToReturnLocTuple.get(highestMethodDesc)); + // System.out.println(" setHigherThanReturnLoc=" + // + mapHighestOverriddenMethodDescToSetHigherThanRETURNLoc.get(highestMethodDesc)); + + } + + } + + private void addMapHighestMethodDescToMethodDesc(MethodDescriptor highest, MethodDescriptor md) { + if (!mapHighestOverriddenMethodDescToMethodDescSet.containsKey(highest)) { + mapHighestOverriddenMethodDescToMethodDescSet.put(highest, new HashSet()); + } + mapHighestOverriddenMethodDescToMethodDescSet.get(highest).add(md); + } + + private void DFSInheritanceTreeCalculatingHighestOverriddenMethod(ClassDescriptor cd) { + + // ClassDescriptor cd = node.getData(); + + for (Iterator iterator = cd.getMethods(); iterator.hasNext();) { + MethodDescriptor md = (MethodDescriptor) iterator.next(); + MethodDescriptor highestMethodDesc = getHighestOverriddenMethod(md.getClassDesc(), md); + mapMethodDescToHighestOverriddenMethodDesc.put(md, highestMethodDesc); + addMapHighestMethodDescToMethodDesc(highestMethodDesc, md); + + } + + // traverse children + Set children = getDirectSubClasses(cd); + for (Iterator iterator = children.iterator(); iterator.hasNext();) { + ClassDescriptor child = (ClassDescriptor) iterator.next(); + DFSInheritanceTreeCalculatingHighestOverriddenMethod(child); + } + + } + + private MethodDescriptor getHighestOverriddenMethod(ClassDescriptor curClassDesc, + MethodDescriptor curMethodDesc) { + + // Node curNode = inheritanceTree.getTreeNode(curClassDesc); + // Node parentNode = curNode.getParent(); + ClassDescriptor parentClassDesc = curClassDesc.getSuperDesc(); + + if (parentClassDesc != null) { + if (parentClassDesc.getMethodTable().contains(curMethodDesc.getSymbol())) { + Set methodDescSet = + parentClassDesc.getMethodTable().getSet(curMethodDesc.getSymbol()); + for (Iterator iterator = methodDescSet.iterator(); iterator.hasNext();) { + MethodDescriptor md = (MethodDescriptor) iterator.next(); + if (md.matches(curMethodDesc)) { + return getHighestOverriddenMethod(parentClassDesc, md); + } + } + } + // traverse to the parent! + return getHighestOverriddenMethod(parentClassDesc, curMethodDesc); + } + return curMethodDesc; + } + + private void buildInheritanceTree() { + + DFSInheritanceTreeCalculatingHighestOverriddenMethod(rootClassDescriptor); + + } + + private void addInheritanceConstraintsToHierarchyGraph() { + + // DFS the inheritance tree and propagates nodes/edges of parent to child + + // Node rootNode = inheritanceTree.getRootNode(); + DFSInheritanceTree(rootClassDescriptor); + + } + + private void DFSInheritanceTree(ClassDescriptor parentClassDescriptor) { + + // ClassDescriptor parentClassDescriptor = parentNode.getData(); + + Set children = getDirectSubClasses(parentClassDescriptor); + for (Iterator iterator = children.iterator(); iterator.hasNext();) { + ClassDescriptor childClassDescriptor = (ClassDescriptor) iterator.next(); + + HierarchyGraph parentGraph = getHierarchyGraph(parentClassDescriptor); + HierarchyGraph childGraph = getHierarchyGraph(childClassDescriptor); + + Set parentNodeSet = parentGraph.getNodeSet(); + for (Iterator iterator2 = parentNodeSet.iterator(); iterator2.hasNext();) { + HNode hNode = (HNode) iterator2.next(); + childGraph.addNode(hNode); + } + + // copies extra information from the parent hierarchy graph + Map> parentMergeNodeMap = parentGraph.getMapHNodetoMergeSet(); + Map> childMergeNodeMap = childGraph.getMapHNodetoMergeSet(); + + Set keySet = parentMergeNodeMap.keySet(); + for (Iterator iterator2 = keySet.iterator(); iterator2.hasNext();) { + HNode parentKey = (HNode) iterator2.next(); + if (!childMergeNodeMap.containsKey(parentKey)) { + childMergeNodeMap.put(parentKey, new HashSet()); + } + childMergeNodeMap.get(parentKey).addAll(parentMergeNodeMap.get(parentKey)); + } + + // copies nodes/edges from the parent class... + for (Iterator iterator2 = parentNodeSet.iterator(); iterator2.hasNext();) { + HNode parentHNode = (HNode) iterator2.next(); + + Set parentIncomingHNode = parentGraph.getIncomingNodeSet(parentHNode); + Set parentOutgoingHNode = parentGraph.getOutgoingNodeSet(parentHNode); + + for (Iterator iterator3 = parentIncomingHNode.iterator(); iterator3.hasNext();) { + HNode inHNode = (HNode) iterator3.next(); + childGraph.addEdge(inHNode.getDescriptor(), parentHNode.getDescriptor()); + } + + for (Iterator iterator3 = parentOutgoingHNode.iterator(); iterator3.hasNext();) { + HNode outHNode = (HNode) iterator3.next(); + childGraph.addEdge(parentHNode.getDescriptor(), outHNode.getDescriptor()); + } + + } + + // copies nodes/edges from parent methods to overridden methods + + for (Iterator iterator3 = childClassDescriptor.getMethods(); iterator3.hasNext();) { + MethodDescriptor childMethodDescriptor = (MethodDescriptor) iterator3.next(); + + MethodDescriptor parentMethodDesc = + getParentMethodDesc(childMethodDescriptor.getClassDesc(), childMethodDescriptor); + + if (parentMethodDesc != null) { + + HierarchyGraph parentMethodGraph = getHierarchyGraph(parentMethodDesc); + HierarchyGraph childMethodGraph = getHierarchyGraph(childMethodDescriptor); + + Set parentMethodNodeSet = parentMethodGraph.getNodeSet(); + for (Iterator iterator2 = parentMethodNodeSet.iterator(); iterator2.hasNext();) { + HNode hNode = (HNode) iterator2.next(); + childMethodGraph.addNode(hNode); + } + + // copies extra information from the parent hierarchy graph + Map> parentMethodMergeNodeMap = + parentMethodGraph.getMapHNodetoMergeSet(); + Map> childMethodMergeNodeMap = childMethodGraph.getMapHNodetoMergeSet(); + + Set methodKeySet = parentMethodMergeNodeMap.keySet(); + for (Iterator iterator2 = methodKeySet.iterator(); iterator2.hasNext();) { + HNode parentKey = (HNode) iterator2.next(); + if (!childMethodMergeNodeMap.containsKey(parentKey)) { + childMethodMergeNodeMap.put(parentKey, new HashSet()); + } + childMethodMergeNodeMap.get(parentKey).addAll(parentMethodMergeNodeMap.get(parentKey)); + } + + // copies nodes/edges from the parent method... + for (Iterator iterator2 = parentMethodGraph.getNodeSet().iterator(); iterator2.hasNext();) { + HNode parentHNode = (HNode) iterator2.next(); + + Set parentIncomingHNode = parentMethodGraph.getIncomingNodeSet(parentHNode); + Set parentOutgoingHNode = parentMethodGraph.getOutgoingNodeSet(parentHNode); + + for (Iterator iterator4 = parentIncomingHNode.iterator(); iterator4.hasNext();) { + HNode inHNode = (HNode) iterator4.next(); + childMethodGraph.addEdge(inHNode, parentHNode); + } + + for (Iterator iterator4 = parentOutgoingHNode.iterator(); iterator4.hasNext();) { + HNode outHNode = (HNode) iterator4.next(); + childMethodGraph.addEdge(parentHNode, outHNode); + } + + } + + } + + } + + DFSInheritanceTree(childClassDescriptor); + } + + } + + public MethodDescriptor getParentMethodDesc(ClassDescriptor classDesc, MethodDescriptor methodDesc) { + + // Node childNode = inheritanceTree.getTreeNode(classDesc); + ClassDescriptor parentClassDesc = classDesc.getSuperDesc(); + // Node parentNode = childNode.getParent(); + + if (parentClassDesc != null) { + // ClassDescriptor parentClassDesc = parentNode.getData(); + if (parentClassDesc.getMethodTable().contains(methodDesc.getSymbol())) { + Set methodDescSet = + parentClassDesc.getMethodTable().getSet(methodDesc.getSymbol()); + for (Iterator iterator = methodDescSet.iterator(); iterator.hasNext();) { + MethodDescriptor md = (MethodDescriptor) iterator.next(); + if (md.matches(methodDesc)) { + return md; + } + } + } + + // traverse to the parent! + getParentMethodDesc(parentClassDesc, methodDesc); + + } + + return null; + } + + private void checkReturnNodes() { + LinkedList methodDescList = + (LinkedList) toanalyze_methodDescList.clone(); + + while (!methodDescList.isEmpty()) { + MethodDescriptor md = methodDescList.removeLast(); + + if (md.getReturnType() != null && !md.getReturnType().isVoid()) { + checkFlowNodeReturnThisField(md); + } + // // in this case, this method will return the composite location that starts with 'this' + // FlowGraph flowGraph = getFlowGraph(md); + // Set returnNodeSet = flowGraph.getReturnNodeSet(); + // } + + } + + } + + private void addSuperClasses(ClassDescriptor cd) { + ClassDescriptor parentClassDesc = cd.getSuperDesc(); + if (parentClassDesc != null) { + toanalyze_classDescSet.add(parentClassDesc); + addSuperClasses(parentClassDesc); + } + } + + private void updateFlowGraph() { + + LinkedList methodDescList = + (LinkedList) toanalyze_methodDescList.clone(); + + while (!methodDescList.isEmpty()) { + MethodDescriptor md = methodDescList.removeLast(); + if (state.SSJAVADEBUG) { + System.out.println(); + System.out.println("SSJAVA: Updating a flow graph: " + md); + propagateFlowsFromCalleesWithNoCompositeLocation(md); + } + + Set nodeSet = getFlowGraph(md).getNodeSet(); + for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + FlowNode flowNode = (FlowNode) iterator.next(); + NTuple descTuple = flowNode.getCurrentDescTuple(); + NTuple locTuple = translateToLocTuple(md, descTuple); + for (int i = 0; i < locTuple.size(); i++) { + Location loc = locTuple.get(i); + if (loc.getDescriptor() instanceof ClassDescriptor) { + ClassDescriptor classDesc = (ClassDescriptor) loc.getDescriptor(); + toanalyze_classDescSet.add(classDesc); + addSuperClasses(classDesc); + } else if (loc.getDescriptor() instanceof MethodDescriptor) { + toanalyze_classDescSet.add(((MethodDescriptor) loc.getDescriptor()).getClassDesc()); + } + } + + } + + } + } + public Map, NTuple> getMapCallerArgToCalleeParam( MethodInvokeNode min) { @@ -285,9 +985,41 @@ public class LocationInference { } private void translateCompositeLocationAssignmentToFlowGraph() { + System.out.println("\nSSJAVA: Translate composite location assignments to flow graphs:"); MethodDescriptor methodEventLoopDesc = ssjava.getMethodContainingSSJavaLoop(); translateCompositeLocationAssignmentToFlowGraph(methodEventLoopDesc); - _debug_printGraph(); + } + + private void translateCompositeLocationAssignmentToFlowGraph2() { + System.out.println("\nSSJAVA: Translate composite location assignments to flow graphs:"); + MethodDescriptor methodEventLoopDesc = ssjava.getMethodContainingSSJavaLoop(); + translateCompositeLocationAssignmentToFlowGraph(methodEventLoopDesc); + } + + private void addAdditionalOrderingConstraints() { + System.out.println("\nSSJAVA: Add addtional ordering constriants:"); + MethodDescriptor methodEventLoopDesc = ssjava.getMethodContainingSSJavaLoop(); + addAddtionalOrderingConstraints(methodEventLoopDesc); + // calculateReturnHolderLocation(); + } + + private void calculateReturnHolderLocation() { + LinkedList methodDescList = + (LinkedList) toanalyze_methodDescList.clone(); + + while (!methodDescList.isEmpty()) { + MethodDescriptor md = methodDescList.removeLast(); + + FlowGraph fg = getFlowGraph(md); + Set nodeSet = fg.getNodeSet(); + for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + FlowNode flowNode = (FlowNode) iterator.next(); + if (flowNode.isFromHolder()) { + calculateCompositeLocationFromFlowGraph(md, flowNode); + } + } + + } } private void updateCompositeLocationAssignments() { @@ -298,7 +1030,7 @@ public class LocationInference { while (!methodDescList.isEmpty()) { MethodDescriptor md = methodDescList.removeLast(); - System.out.println("\n#updateCompositeLocationAssignments=" + md); + // System.out.println("\n#updateCompositeLocationAssignments=" + md); FlowGraph flowGraph = getFlowGraph(md); @@ -307,23 +1039,25 @@ public class LocationInference { Set nodeSet = flowGraph.getNodeSet(); for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { FlowNode node = (FlowNode) iterator.next(); - System.out.println("-node=" + node + " node.getDescTuple=" + node.getDescTuple()); + // System.out.println("-node=" + node + " node.getDescTuple=" + node.getDescTuple()); if (node.getCompositeLocation() != null) { CompositeLocation compLoc = node.getCompositeLocation(); CompositeLocation updatedCompLoc = updateCompositeLocation(compLoc); node.setCompositeLocation(updatedCompLoc); - System.out.println("---updatedCompLoc1=" + updatedCompLoc); + // System.out.println("---updatedCompLoc1=" + updatedCompLoc); } else { NTuple descTuple = node.getDescTuple(); + // System.out.println("update desc=" + descTuple); CompositeLocation compLoc = convertToCompositeLocation(md, descTuple); compLoc = updateCompositeLocation(compLoc); node.setCompositeLocation(compLoc); - System.out.println("---updatedCompLoc2=" + compLoc); + // System.out.println("---updatedCompLoc2=" + compLoc); } if (node.isDeclaratonNode()) { Descriptor localVarDesc = node.getDescTuple().get(0); - methodSummary.addMapVarNameToInferCompLoc(localVarDesc, node.getCompositeLocation()); + CompositeLocation compLoc = updateCompositeLocation(node.getCompositeLocation()); + methodSummary.addMapVarNameToInferCompLoc(localVarDesc, compLoc); } } @@ -348,6 +1082,16 @@ public class LocationInference { String locName; if (!enclosingDesc.equals(GLOBALDESC)) { LocationSummary locSummary = getLocationSummary(enclosingDesc); + // HierarchyGraph scGraph = getSkeletonCombinationHierarchyGraph(enclosingDesc); + HierarchyGraph scGraph = getSimpleHierarchyGraph(enclosingDesc); + if (scGraph != null) { + HNode curNode = scGraph.getCurrentHNode(nodeIdentifier); + // System.out.println("nodeID=" + nodeIdentifier + " curNode=" + curNode + // + " enclosingDesc=" + enclosingDesc); + if (curNode != null) { + nodeIdentifier = curNode.getName(); + } + } locName = locSummary.getLocationName(nodeIdentifier); } else { locName = nodeIdentifier; @@ -361,7 +1105,8 @@ public class LocationInference { private void translateCompositeLocationAssignmentToFlowGraph(MethodDescriptor mdCaller) { - System.out.println("\n#translateCompositeLocationAssignmentToFlowGraph=" + mdCaller); + // System.out.println("\n\n###translateCompositeLocationAssignmentToFlowGraph mdCaller=" + // + mdCaller); // First, assign a composite location to a node in the flow graph GlobalFlowGraph callerGlobalFlowGraph = getSubGlobalFlowGraph(mdCaller); @@ -369,7 +1114,7 @@ public class LocationInference { FlowGraph callerFlowGraph = getFlowGraph(mdCaller); Map callerMapLocToCompLoc = callerGlobalFlowGraph.getMapLocationToInferCompositeLocation(); - System.out.println("---callerMapLocToCompLoc=" + callerMapLocToCompLoc); + Set methodLocSet = callerMapLocToCompLoc.keySet(); for (Iterator iterator = methodLocSet.iterator(); iterator.hasNext();) { Location methodLoc = (Location) iterator.next(); @@ -387,7 +1132,9 @@ public class LocationInference { // need to translate a composite location that is started with the base // tuple of 'min'. translateMapLocationToInferCompositeLocationToCalleeGraph(callerGlobalFlowGraph, min); - calleeSet.add(min.getMethod()); + MethodDescriptor mdCallee = min.getMethod(); + calleeSet.add(mdCallee); + } for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) { @@ -397,6 +1144,125 @@ public class LocationInference { } + private void addAddtionalOrderingConstraints(MethodDescriptor mdCaller) { + + // First, assign a composite location to a node in the flow graph + GlobalFlowGraph callerGlobalFlowGraph = getSubGlobalFlowGraph(mdCaller); + + FlowGraph callerFlowGraph = getFlowGraph(mdCaller); + Map callerMapLocToCompLoc = + callerGlobalFlowGraph.getMapLocationToInferCompositeLocation(); + Set methodLocSet = callerMapLocToCompLoc.keySet(); + + Set minSet = mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller); + + Set calleeSet = new HashSet(); + for (Iterator iterator = minSet.iterator(); iterator.hasNext();) { + MethodInvokeNode min = (MethodInvokeNode) iterator.next(); + MethodDescriptor mdCallee = min.getMethod(); + calleeSet.add(mdCallee); + + // + // add an additional ordering constraint + // if the first element of a parameter composite location matches 'this' reference, + // the corresponding argument in the caller is required to be higher than the translated + // parameter location in the caller lattice + // TODO + // addOrderingConstraintFromCompLocParamToArg(mdCaller, min); + + // + // update return flow nodes in the caller + CompositeLocation returnLoc = getMethodSummary(mdCallee).getRETURNLoc(); + // System.out.println("### min=" + min.printNode(0) + " returnLoc=" + returnLoc); + if (returnLoc != null && returnLoc.get(0).getLocDescriptor().equals(mdCallee.getThis()) + && returnLoc.getSize() > 1) { + // System.out.println("###RETURN COMP LOC=" + returnLoc); + NTuple returnLocTuple = returnLoc.getTuple(); + NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); + // System.out.println("###basetuple=" + baseTuple); + NTuple newReturnTuple = baseTuple.clone(); + for (int i = 1; i < returnLocTuple.size(); i++) { + newReturnTuple.add(returnLocTuple.get(i).getLocDescriptor()); + } + // System.out.println("###NEW RETURN TUPLE FOR CALLER=" + newReturnTuple); + + FlowReturnNode holderNode = callerFlowGraph.getFlowReturnNode(min); + NodeTupleSet holderTupleSet = + getNodeTupleSetFromReturnNode(getFlowGraph(mdCaller), holderNode); + + callerFlowGraph.getFlowReturnNode(min).setNewTuple(newReturnTuple); + + // then need to remove old constraints + // TODO SAT + // System.out.println("###REMOVE OLD CONSTRAINTS=" + holderNode); + for (Iterator> iter = holderTupleSet.iterator(); iter.hasNext();) { + NTuple tupleFromHolder = iter.next(); + Set holderOutEdge = callerFlowGraph.getOutEdgeSet(holderNode); + for (Iterator iterator2 = holderOutEdge.iterator(); iterator2.hasNext();) { + FlowEdge outEdge = (FlowEdge) iterator2.next(); + NTuple toberemovedTuple = outEdge.getEndTuple(); + // System.out.println("---remove " + tupleFromHolder + " -> " + toberemovedTuple); + callerFlowGraph.removeEdge(tupleFromHolder, toberemovedTuple); + } + } + + } else { + // if the return loc set was empty and later pcloc was connected to the return loc + // need to make sure that return loc reflects to this changes. + FlowReturnNode flowReturnNode = callerFlowGraph.getFlowReturnNode(min); + if (flowReturnNode != null && flowReturnNode.getReturnTupleSet().isEmpty()) { + + if (needToUpdateReturnLocHolder(min.getMethod(), flowReturnNode)) { + NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); + NTuple newReturnTuple = baseTuple.clone(); + flowReturnNode.addTuple(newReturnTuple); + } + + } + + } + + } + + for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) { + MethodDescriptor callee = (MethodDescriptor) iterator.next(); + addAddtionalOrderingConstraints(callee); + } + + } + + private boolean needToUpdateReturnLocHolder(MethodDescriptor mdCallee, + FlowReturnNode flowReturnNode) { + FlowGraph fg = getFlowGraph(mdCallee); + MethodSummary summary = getMethodSummary(mdCallee); + CompositeLocation returnCompLoc = summary.getRETURNLoc(); + NTuple returnDescTuple = translateToDescTuple(returnCompLoc.getTuple()); + Set incomingNodeToReturnNode = + fg.getIncomingFlowNodeSet(fg.getFlowNode(returnDescTuple)); + for (Iterator iterator = incomingNodeToReturnNode.iterator(); iterator.hasNext();) { + FlowNode inNode = (FlowNode) iterator.next(); + if (inNode.getDescTuple().get(0).equals(mdCallee.getThis())) { + return true; + } + } + return false; + } + + private void addMapMethodDescToMethodInvokeNodeSet(MethodInvokeNode min) { + MethodDescriptor md = min.getMethod(); + if (!mapMethodDescToMethodInvokeNodeSet.containsKey(md)) { + mapMethodDescToMethodInvokeNodeSet.put(md, new HashSet()); + } + mapMethodDescToMethodInvokeNodeSet.get(md).add(min); + } + + private Set getMethodInvokeNodeSetByMethodDesc(MethodDescriptor md) { + if (!mapMethodDescToMethodInvokeNodeSet.containsKey(md)) { + mapMethodDescToMethodInvokeNodeSet.put(md, new HashSet()); + } + return mapMethodDescToMethodInvokeNodeSet.get(md); + } + public void assignCompositeLocationToFlowGraph(FlowGraph flowGraph, Location loc, CompositeLocation inferCompLoc) { Descriptor localDesc = loc.getLocDescriptor(); @@ -404,11 +1270,12 @@ public class LocationInference { Set nodeSet = flowGraph.getNodeSet(); for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { FlowNode node = (FlowNode) iterator.next(); - if (node.getDescTuple().startsWith(localDesc)) { + if (node.getDescTuple().startsWith(localDesc) + && !node.getDescTuple().get(0).equals(LITERALDESC)) { // need to assign the inferred composite location to this node CompositeLocation newCompLoc = generateCompositeLocation(node.getDescTuple(), inferCompLoc); node.setCompositeLocation(newCompLoc); - System.out.println("SET Node=" + node + " inferCompLoc=" + newCompLoc); + // System.out.println("SET Node=" + node + " inferCompLoc=" + newCompLoc); } } } @@ -416,8 +1283,10 @@ public class LocationInference { private CompositeLocation generateCompositeLocation(NTuple nodeDescTuple, CompositeLocation inferCompLoc) { - System.out.println("generateCompositeLocation=" + nodeDescTuple + " with inferCompLoc=" - + inferCompLoc); + // System.out.println("generateCompositeLocation=" + nodeDescTuple + " with inferCompLoc=" + // + inferCompLoc); + + MethodDescriptor md = (MethodDescriptor) inferCompLoc.get(0).getDescriptor(); CompositeLocation newCompLoc = new CompositeLocation(); for (int i = 0; i < inferCompLoc.getSize(); i++) { @@ -427,7 +1296,7 @@ public class LocationInference { Descriptor lastDescOfPrefix = nodeDescTuple.get(0); Descriptor enclosingDescriptor; if (lastDescOfPrefix instanceof InterDescriptor) { - enclosingDescriptor = null; + enclosingDescriptor = getFlowGraph(md).getEnclosingDescriptor(lastDescOfPrefix); } else { enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc(); } @@ -451,6 +1320,8 @@ public class LocationInference { Map callerMapLocToCompLoc = callerGraph.getMapLocationToInferCompositeLocation(); + Map> mapIdxToArgTuple = mapMethodInvokeNodeToArgIdxMap.get(min); + FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); GlobalFlowGraph calleeGlobalGraph = getSubGlobalFlowGraph(mdCallee); @@ -459,8 +1330,9 @@ public class LocationInference { baseLocTuple = translateToLocTuple(mdCaller, mapMethodInvokeNodeToBaseTuple.get(min)); } - // System.out.println("\n-translate caller infer composite loc to callee=" + mdCallee - // + " baseLocTuple=" + baseLocTuple); + // System.out.println("\n-#translate caller=" + mdCaller + " infer composite loc to callee=" + // + mdCallee + " baseLocTuple=" + baseLocTuple); + Set keySet = callerMapLocToCompLoc.keySet(); for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { Location key = (Location) iterator.next(); @@ -470,13 +1342,20 @@ public class LocationInference { CompositeLocation newCalleeCompLoc; if (baseLocTuple != null && callerCompLoc.getTuple().startsWith(baseLocTuple)) { - // System.out.println("---need to translate callerCompLoc=" + callerCompLoc + // System.out.println("-----need to translate callerCompLoc=" + callerCompLoc // + " with baseTuple=" + baseLocTuple); newCalleeCompLoc = translateCompositeLocationToCallee(callerCompLoc, baseLocTuple, mdCallee); calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, newCalleeCompLoc); - // System.out.println("---callee loc=" + key + " newCalleeCompLoc=" + newCalleeCompLoc); + // System.out.println("1---key=" + key + " callerCompLoc=" + callerCompLoc + // + " newCalleeCompLoc=" + newCalleeCompLoc); + // System.out.println("-----caller=" + mdCaller + " callee=" + mdCallee); + if (!newCalleeCompLoc.get(0).getDescriptor().equals(mdCallee)) { + System.exit(0); + } + + // System.out.println("-----baseLoctuple=" + baseLocTuple); } else { // check if it is the global access Location compLocFirstElement = callerCompLoc.getTuple().get(0); @@ -490,71 +1369,280 @@ public class LocationInference { for (int i = 1; i < callerCompLoc.getSize(); i++) { newCalleeCompLoc.addLocation(callerCompLoc.get(i)); } - calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, newCalleeCompLoc); + calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, newCalleeCompLoc); + // System.out.println("2---key=" + key + " callerCompLoc=" + callerCompLoc + // + " newCalleeCompLoc=" + newCalleeCompLoc); + // System.out.println("-----caller=" + mdCaller + " callee=" + mdCallee); + + } else { + int paramIdx = getParamIdx(callerCompLoc, mapIdxToArgTuple); + if (paramIdx == -1) { + // here, the first element of the current composite location comes from the current + // callee + // so transfer the same composite location to the callee + if (!calleeGlobalGraph.contrainsInferCompositeLocationMapKey(key)) { + if (callerCompLoc.get(0).getDescriptor().equals(mdCallee)) { + // System.out.println("3---key=" + key + " callerCompLoc=" + callerCompLoc + // + " newCalleeCompLoc=" + callerCompLoc); + // System.out.println("-----caller=" + mdCaller + " callee=" + mdCallee); + calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, callerCompLoc); + } else { + // System.out.println("3---SKIP key=" + key + " callerCompLoc=" + callerCompLoc); + } + } + continue; + } + + // It is the case where two parameters have relative orderings between them by having + // composite locations + // if we found the param idx, it means that the first part of the caller composite + // location corresponds to the one of arguments. + // for example, if the caller argument is <,> + // and the current caller composite location mapping + // <,,> + // and the parameter which matches with the caller argument is 'Br brParam' + // then, the translated callee composite location will be <,> + NTuple argTuple = mapIdxToArgTuple.get(paramIdx); + + FlowNode paramFlowNode = calleeFlowGraph.getParamFlowNode(paramIdx); + NTuple paramLocTuple = + translateToLocTuple(mdCallee, paramFlowNode.getDescTuple()); + newCalleeCompLoc = new CompositeLocation(); + for (int i = 0; i < paramLocTuple.size(); i++) { + newCalleeCompLoc.addLocation(paramLocTuple.get(i)); + } + for (int i = argTuple.size(); i < callerCompLoc.getSize(); i++) { + newCalleeCompLoc.addLocation(callerCompLoc.get(i)); + } + calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, newCalleeCompLoc); + // System.out.println("4---key=" + key + " callerCompLoc=" + callerCompLoc + // + " newCalleeCompLoc=" + newCalleeCompLoc); + // System.out.println("-----caller=" + mdCaller + " callee=" + mdCallee); + + } + + } + + } + } + + // System.out.println("#ASSIGN COMP LOC TO CALLEE PARAMS: callee=" + mdCallee + " caller=" + // + mdCaller); + // If the location of an argument has a composite location + // need to assign a proper composite location to the corresponding callee parameter + Set idxSet = mapIdxToArgTuple.keySet(); + for (Iterator iterator = idxSet.iterator(); iterator.hasNext();) { + Integer idx = (Integer) iterator.next(); + + if (idx == 0 && !min.getMethod().isStatic()) { + continue; + } + + NTuple argTuple = mapIdxToArgTuple.get(idx); + // System.out.println("-argTuple=" + argTuple + " idx=" + idx); + if (argTuple.size() > 0) { + // check if an arg tuple has been already assigned to a composite location + NTuple argLocTuple = translateToLocTuple(mdCaller, argTuple); + Location argLocalLoc = argLocTuple.get(0); + + // if (!isPrimitiveType(argTuple)) { + if (callerMapLocToCompLoc.containsKey(argLocalLoc)) { + + CompositeLocation callerCompLoc = callerMapLocToCompLoc.get(argLocalLoc); + for (int i = 1; i < argLocTuple.size(); i++) { + callerCompLoc.addLocation(argLocTuple.get(i)); + } + + // System.out.println("---callerCompLoc=" + callerCompLoc); + + // if (baseLocTuple != null && callerCompLoc.getTuple().startsWith(baseLocTuple)) { + + FlowNode calleeParamFlowNode = calleeFlowGraph.getParamFlowNode(idx); + + NTuple calleeParamDescTuple = calleeParamFlowNode.getDescTuple(); + NTuple calleeParamLocTuple = + translateToLocTuple(mdCallee, calleeParamDescTuple); + + int refParamIdx = getParamIdx(callerCompLoc, mapIdxToArgTuple); + // System.out.println("-----paramIdx=" + refParamIdx); + if (refParamIdx == 0 && !mdCallee.isStatic()) { + + // System.out.println("-------need to translate callerCompLoc=" + callerCompLoc + // + " with baseTuple=" + baseLocTuple + " calleeParamLocTuple=" + // + calleeParamLocTuple); + + CompositeLocation newCalleeCompLoc = + translateCompositeLocationToCallee(callerCompLoc, baseLocTuple, mdCallee); + + calleeGlobalGraph.addMapLocationToInferCompositeLocation(calleeParamLocTuple.get(0), + newCalleeCompLoc); + + // System.out.println("---------key=" + calleeParamLocTuple.get(0) + " callerCompLoc=" + // + callerCompLoc + " newCalleeCompLoc=" + newCalleeCompLoc); + + } else if (refParamIdx != -1) { + // the first element of an argument composite location matches with one of paramtere + // composite locations + + // System.out.println("-------param match case="); + + NTuple argTupleRef = mapIdxToArgTuple.get(refParamIdx); + FlowNode refParamFlowNode = calleeFlowGraph.getParamFlowNode(refParamIdx); + NTuple refParamLocTuple = + translateToLocTuple(mdCallee, refParamFlowNode.getDescTuple()); + + // System.out.println("---------refParamLocTuple=" + refParamLocTuple + // + " from argTupleRef=" + argTupleRef); + + CompositeLocation newCalleeCompLoc = new CompositeLocation(); + for (int i = 0; i < refParamLocTuple.size(); i++) { + newCalleeCompLoc.addLocation(refParamLocTuple.get(i)); + } + for (int i = argTupleRef.size(); i < callerCompLoc.getSize(); i++) { + newCalleeCompLoc.addLocation(callerCompLoc.get(i)); + } + + calleeGlobalGraph.addMapLocationToInferCompositeLocation(calleeParamLocTuple.get(0), + newCalleeCompLoc); + + calleeParamFlowNode.setCompositeLocation(newCalleeCompLoc); + // System.out.println("-----------key=" + calleeParamLocTuple.get(0) + + // " callerCompLoc=" + // + callerCompLoc + " newCalleeCompLoc=" + newCalleeCompLoc); + } else { + CompositeLocation newCalleeCompLoc = + calculateCompositeLocationFromSubGlobalGraph(mdCallee, calleeParamFlowNode); + if (newCalleeCompLoc != null) { + calleeGlobalGraph.addMapLocationToInferCompositeLocation(calleeParamLocTuple.get(0), + newCalleeCompLoc); + calleeParamFlowNode.setCompositeLocation(newCalleeCompLoc); + } } - } + // System.out.println("-----------------calleeParamFlowNode=" + // + calleeParamFlowNode.getCompositeLocation()); + + // } + } } + } - // If the location of an argument has a composite location - // need to assign a proper composite location to the corresponding callee parameter - System.out.println("\n-translate arg composite location to callee param. min=" - + min.printNode(0)); - Map> mapIdxToArgTuple = mapMethodInvokeNodeToArgIdxMap.get(min); - Set idxSet = mapIdxToArgTuple.keySet(); - for (Iterator iterator = idxSet.iterator(); iterator.hasNext();) { - Integer idx = (Integer) iterator.next(); + } - if (idx == 0 && !min.getMethod().isStatic()) { - continue; + private CompositeLocation calculateCompositeLocationFromSubGlobalGraph(MethodDescriptor md, + FlowNode paramNode) { + + // System.out.println("#############################################################"); + // System.out.println("calculateCompositeLocationFromSubGlobalGraph=" + paramNode); + + GlobalFlowGraph subGlobalFlowGraph = getSubGlobalFlowGraph(md); + NTuple paramLocTuple = translateToLocTuple(md, paramNode.getDescTuple()); + GlobalFlowNode paramGlobalNode = subGlobalFlowGraph.getFlowNode(paramLocTuple); + + List> prefixList = calculatePrefixList(subGlobalFlowGraph, paramGlobalNode); + + Location prefixLoc = paramLocTuple.get(0); + + Set reachableNodeSet = + subGlobalFlowGraph.getReachableNodeSetByPrefix(paramGlobalNode.getLocTuple().get(0)); + // Set reachNodeSet = globalFlowGraph.getReachableNodeSetFrom(node); + + // System.out.println("node=" + node + " prefixList=" + prefixList); + + for (int i = 0; i < prefixList.size(); i++) { + NTuple curPrefix = prefixList.get(i); + Set> reachableCommonPrefixSet = new HashSet>(); + + for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) { + GlobalFlowNode reachNode = (GlobalFlowNode) iterator2.next(); + if (reachNode.getLocTuple().startsWith(curPrefix)) { + reachableCommonPrefixSet.add(reachNode.getLocTuple()); + } } + // System.out.println("reachableCommonPrefixSet=" + reachableCommonPrefixSet); - NTuple argTuple = mapIdxToArgTuple.get(idx); - if (argTuple.size() > 0) { - // check if an arg tuple has been already assigned to a composite location - NTuple argLocTuple = translateToLocTuple(mdCaller, argTuple); - Location argLocalLoc = argLocTuple.get(0); + if (!reachableCommonPrefixSet.isEmpty()) { - // if (!isPrimitiveType(argTuple)) { - if (callerMapLocToCompLoc.containsKey(argLocalLoc)) { + MethodDescriptor curPrefixFirstElementMethodDesc = + (MethodDescriptor) curPrefix.get(0).getDescriptor(); - CompositeLocation callerCompLoc = callerMapLocToCompLoc.get(argLocalLoc); - for (int i = 1; i < argLocTuple.size(); i++) { - callerCompLoc.addLocation(argLocTuple.get(i)); - } + MethodDescriptor nodePrefixLocFirstElementMethodDesc = + (MethodDescriptor) prefixLoc.getDescriptor(); - if (baseLocTuple != null && callerCompLoc.getTuple().startsWith(baseLocTuple)) { + // System.out.println("curPrefixFirstElementMethodDesc=" + + // curPrefixFirstElementMethodDesc); + // System.out.println("nodePrefixLocFirstElementMethodDesc=" + // + nodePrefixLocFirstElementMethodDesc); - FlowNode calleeParamFlowNode = calleeFlowGraph.getParamFlowNode(idx); - NTuple calleeParamDescTuple = calleeParamFlowNode.getDescTuple(); - NTuple calleeParamLocTuple = - translateToLocTuple(mdCallee, calleeParamDescTuple); + if (curPrefixFirstElementMethodDesc.equals(nodePrefixLocFirstElementMethodDesc) + || isTransitivelyCalledFrom(nodePrefixLocFirstElementMethodDesc, + curPrefixFirstElementMethodDesc)) { - System.out.println("---need to translate callerCompLoc=" + callerCompLoc - + " with baseTuple=" + baseLocTuple + " calleeParamLocTuple=" - + calleeParamLocTuple); + // TODO + // if (!node.getLocTuple().startsWith(curPrefix.get(0))) { - CompositeLocation newCalleeCompLoc = - translateCompositeLocationToCallee(callerCompLoc, baseLocTuple, mdCallee); + Location curPrefixLocalLoc = curPrefix.get(0); + if (subGlobalFlowGraph.mapLocationToInferCompositeLocation.containsKey(curPrefixLocalLoc)) { + // in this case, the local variable of the current prefix has already got a composite + // location + // so we just ignore the current composite location. - calleeGlobalGraph.addMapLocationToInferCompositeLocation(calleeParamLocTuple.get(0), - newCalleeCompLoc); + // System.out.println("HERE WE DO NOT ASSIGN A COMPOSITE LOCATION TO =" + node + // + " DUE TO " + curPrefix); + return null; + } - System.out.println("---callee loc=" + calleeParamLocTuple.get(0) - + " newCalleeCompLoc=" + newCalleeCompLoc); + if (!needToGenerateCompositeLocation(paramGlobalNode, curPrefix)) { + // System.out.println("NO NEED TO GENERATE COMP LOC to " + paramGlobalNode + // + " with prefix=" + curPrefix); + return null; + } - // System.out.println("###need to assign composite location to=" + calleeParamDescTuple - // + " with baseTuple=" + baseLocTuple); + Location targetLocalLoc = paramGlobalNode.getLocTuple().get(0); + CompositeLocation newCompLoc = generateCompositeLocation(curPrefix); + // System.out.println("NEED TO ASSIGN COMP LOC TO " + paramGlobalNode + " with prefix=" + // + curPrefix); + // System.out.println("-targetLocalLoc=" + targetLocalLoc + " - newCompLoc=" + + // newCompLoc); + + // makes sure that a newly generated location appears in the hierarchy graph + for (int compIdx = 0; compIdx < newCompLoc.getSize(); compIdx++) { + Location curLoc = newCompLoc.get(compIdx); + getHierarchyGraph(curLoc.getDescriptor()).getHNode(curLoc.getLocDescriptor()); } + subGlobalFlowGraph.addMapLocationToInferCompositeLocation(targetLocalLoc, newCompLoc); + + return newCompLoc; + } + } } + return null; + } + + private int getParamIdx(CompositeLocation compLoc, + Map> mapIdxToArgTuple) { + + // if the composite location is started with the argument descriptor + // return the argument's index. o.t. return -1 + + Set keySet = mapIdxToArgTuple.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Integer key = (Integer) iterator.next(); + NTuple argTuple = mapIdxToArgTuple.get(key); + if (argTuple.size() > 0 && translateToDescTuple(compLoc.getTuple()).startsWith(argTuple)) { + // System.out.println("compLoc.getTuple=" + compLoc + " is started with " + argTuple); + return key.intValue(); + } + } + return -1; } private boolean isPrimitiveType(NTuple argTuple) { @@ -565,9 +1653,11 @@ public class LocationInference { return ((FieldDescriptor) lastDesc).getType().isPrimitive(); } else if (lastDesc instanceof VarDescriptor) { return ((VarDescriptor) lastDesc).getType().isPrimitive(); + } else if (lastDesc instanceof InterDescriptor) { + return true; } - return true; + return false; } private CompositeLocation translateCompositeLocationToCallee(CompositeLocation callerCompLoc, @@ -602,7 +1692,6 @@ public class LocationInference { next: for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { GlobalFlowNode node = (GlobalFlowNode) iterator.next(); - System.out.println("-GlobalFlowNode=" + node); Location prefixLoc = node.getLocTuple().get(0); if (calculatedPrefixSet.contains(prefixLoc)) { @@ -619,11 +1708,12 @@ public class LocationInference { globalFlowGraph.getReachableNodeSetByPrefix(node.getLocTuple().get(0)); // Set reachNodeSet = globalFlowGraph.getReachableNodeSetFrom(node); - // System.out.println("node=" + node + " prefixList=" + prefixList + " reachableNodeSet=" - // + reachableNodeSet); + // System.out.println("node=" + node + " prefixList=" + prefixList); + // System.out.println("---prefixList=" + prefixList); - for (int i = 0; i < prefixList.size(); i++) { + nextprefix: for (int i = 0; i < prefixList.size(); i++) { NTuple curPrefix = prefixList.get(i); + // System.out.println("---curPrefix=" + curPrefix); Set> reachableCommonPrefixSet = new HashSet>(); for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) { @@ -632,6 +1722,7 @@ public class LocationInference { reachableCommonPrefixSet.add(reachNode.getLocTuple()); } } + // System.out.println("reachableCommonPrefixSet=" + reachableCommonPrefixSet); if (!reachableCommonPrefixSet.isEmpty()) { @@ -641,6 +1732,11 @@ public class LocationInference { MethodDescriptor nodePrefixLocFirstElementMethodDesc = (MethodDescriptor) prefixLoc.getDescriptor(); + // System.out.println("curPrefixFirstElementMethodDesc=" + + // curPrefixFirstElementMethodDesc); + // System.out.println("nodePrefixLocFirstElementMethodDesc=" + // + nodePrefixLocFirstElementMethodDesc); + if (curPrefixFirstElementMethodDesc.equals(nodePrefixLocFirstElementMethodDesc) || isTransitivelyCalledFrom(nodePrefixLocFirstElementMethodDesc, curPrefixFirstElementMethodDesc)) { @@ -660,13 +1756,20 @@ public class LocationInference { continue next; } - Location targetLocalLoc = node.getLocTuple().get(0); - // CompositeLocation curCompLoc = globalFlowGraph.getCompositeLocation(targetLocalLoc); - // if ((curPrefix.size() + 1) > curCompLoc.getSize()) { + if (!needToGenerateCompositeLocation(node, curPrefix)) { + // System.out.println("NO NEED TO GENERATE COMP LOC to " + node + " with prefix=" + // + curPrefix); + // System.out.println("prefixList=" + prefixList); + // System.out.println("reachableNodeSet=" + reachableNodeSet); + continue nextprefix; + } + Location targetLocalLoc = node.getLocTuple().get(0); CompositeLocation newCompLoc = generateCompositeLocation(curPrefix); - System.out.println("NEED TO ASSIGN COMP LOC TO " + node + " with prefix=" + curPrefix); - System.out.println("- newCompLoc=" + newCompLoc); + // System.out.println("NEED TO ASSIGN COMP LOC TO " + node + " with prefix=" + + // curPrefix); + // System.out.println("-targetLocalLoc=" + targetLocalLoc + " - newCompLoc=" + // + newCompLoc); globalFlowGraph.addMapLocationToInferCompositeLocation(targetLocalLoc, newCompLoc); // } @@ -680,9 +1783,206 @@ public class LocationInference { } } - // Set inNodeSet = - // graph.getIncomingNodeSetWithPrefix(prefix); - // System.out.println("inNodeSet=" + inNodeSet + " from=" + node); + } + + private boolean checkFlowNodeReturnThisField(MethodDescriptor md) { + + MethodDescriptor methodDescEventLoop = ssjava.getMethodContainingSSJavaLoop(); + GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(methodDescEventLoop); + + FlowGraph flowGraph = getFlowGraph(md); + + ClassDescriptor enclosingDesc = getClassTypeDescriptor(md.getThis()); + if (enclosingDesc == null) { + return false; + } + + int count = 0; + Set returnNodeSet = flowGraph.getReturnNodeSet(); + Set globalReturnNodeSet = new HashSet(); + for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { + FlowNode flowNode = (FlowNode) iterator.next(); + NTuple locTuple = translateToLocTuple(md, flowNode.getDescTuple()); + GlobalFlowNode globalReturnNode = globalFlowGraph.getFlowNode(locTuple); + globalReturnNodeSet.add(globalReturnNode); + + List> prefixList = calculatePrefixList(globalFlowGraph, globalReturnNode); + for (int i = 0; i < prefixList.size(); i++) { + NTuple curPrefix = prefixList.get(i); + ClassDescriptor cd = + getClassTypeDescriptor(curPrefix.get(curPrefix.size() - 1).getLocDescriptor()); + if (cd != null && cd.equals(enclosingDesc)) { + count++; + break; + } + } + + } + + if (count == returnNodeSet.size()) { + // in this case, all return nodes in the method returns values coming from a location that + // starts with "this" + + // System.out.println("$$$SET RETURN LOC TRUE=" + md); + mapMethodDescriptorToCompositeReturnCase.put(md, Boolean.TRUE); + + // NameDescriptor returnLocDesc = new NameDescriptor("RLOC" + (locSeed++)); + // NTuple rDescTuple = new NTuple(); + // rDescTuple.add(md.getThis()); + // rDescTuple.add(returnLocDesc); + // + // for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { + // FlowNode rnode = (FlowNode) iterator.next(); + // flowGraph.addValueFlowEdge(rnode.getDescTuple(), rDescTuple); + // } + // + // getMethodSummary(md).setRETURNLoc(new CompositeLocation(translateToLocTuple(md, + // rDescTuple))); + + } else { + mapMethodDescriptorToCompositeReturnCase.put(md, Boolean.FALSE); + } + + return mapMethodDescriptorToCompositeReturnCase.get(md).booleanValue(); + + } + + private boolean needToGenerateCompositeLocation(GlobalFlowNode node, NTuple curPrefix) { + // return true if there is a path between a node to which we want to give a composite location + // and nodes which start with curPrefix + + // System.out.println("---needToGenerateCompositeLocation curPrefix=" + curPrefix); + + Location targetLocalLoc = node.getLocTuple().get(0); + + MethodDescriptor md = (MethodDescriptor) targetLocalLoc.getDescriptor(); + FlowGraph flowGraph = getFlowGraph(md); + + FlowNode flowNode = flowGraph.getFlowNode(node.getDescTuple()); + Set reachableSet = flowGraph.getReachFlowNodeSetFrom(flowNode); + + Set paramNodeSet = flowGraph.getParamFlowNodeSet(); + for (Iterator iterator = paramNodeSet.iterator(); iterator.hasNext();) { + FlowNode paramFlowNode = (FlowNode) iterator.next(); + if (curPrefix.startsWith(translateToLocTuple(md, paramFlowNode.getDescTuple()))) { + return true; + } + } + + if (targetLocalLoc.getLocDescriptor() instanceof InterDescriptor) { + Pair pair = + ((InterDescriptor) targetLocalLoc.getLocDescriptor()).getMethodArgIdxPair(); + + if (pair != null) { + // System.out.println("$$$TARGETLOCALLOC HOLDER=" + targetLocalLoc); + + MethodInvokeNode min = pair.getFirst(); + Integer paramIdx = pair.getSecond(); + MethodDescriptor mdCallee = min.getMethod(); + + FlowNode paramNode = getFlowGraph(mdCallee).getParamFlowNode(paramIdx); + if (checkNodeReachToReturnNode(mdCallee, paramNode)) { + return true; + } + + } + + } + + GlobalFlowGraph subGlobalFlowGraph = getSubGlobalFlowGraph(md); + Set subGlobalReachableSet = subGlobalFlowGraph.getReachableNodeSetFrom(node); + + if (!md.isStatic()) { + ClassDescriptor currentMethodThisType = getClassTypeDescriptor(md.getThis()); + for (int i = 0; i < curPrefix.size(); i++) { + ClassDescriptor prefixType = getClassTypeDescriptor(curPrefix.get(i).getLocDescriptor()); + if (prefixType != null && prefixType.equals(currentMethodThisType)) { + // System.out.println("PREFIX TYPE MATCHES WITH=" + currentMethodThisType); + + if (mapMethodDescriptorToCompositeReturnCase.containsKey(md)) { + boolean hasCompReturnLocWithThis = + mapMethodDescriptorToCompositeReturnCase.get(md).booleanValue(); + if (hasCompReturnLocWithThis) { + if (checkNodeReachToReturnNode(md, flowNode)) { + return true; + } + } + } + + for (Iterator iterator3 = subGlobalReachableSet.iterator(); iterator3.hasNext();) { + GlobalFlowNode subGlobalReachalbeNode = (GlobalFlowNode) iterator3.next(); + if (subGlobalReachalbeNode.getLocTuple().get(0).getLocDescriptor().equals(md.getThis())) { + // System.out.println("PREFIX FOUND=" + subGlobalReachalbeNode); + return true; + } + } + } + } + } + + Location lastLocationOfPrefix = curPrefix.get(curPrefix.size() - 1); + // check whether prefix appears in the list of parameters + Set minSet = mapMethodDescToMethodInvokeNodeSet.get(md); + // System.out.println("$$$md=" + md + " minSet=" + minSet); + if (minSet == null) { + return false; + } + found: for (Iterator iterator = minSet.iterator(); iterator.hasNext();) { + MethodInvokeNode min = (MethodInvokeNode) iterator.next(); + Map> map = mapMethodInvokeNodeToArgIdxMap.get(min); + Set keySet = map.keySet(); + // System.out.println("min=" + min.printNode(0)); + + for (Iterator iterator2 = keySet.iterator(); iterator2.hasNext();) { + Integer argIdx = (Integer) iterator2.next(); + NTuple argTuple = map.get(argIdx); + + if (!(!md.isStatic() && argIdx == 0)) { + // if the argTuple is empty, we don't need to do with anything(LITERAL CASE). + if (argTuple.size() > 0 + && argTuple.get(argTuple.size() - 1).equals(lastLocationOfPrefix.getLocDescriptor())) { + NTuple locTuple = + translateToLocTuple(md, flowGraph.getParamFlowNode(argIdx).getDescTuple()); + lastLocationOfPrefix = locTuple.get(0); + // System.out.println("ARG CASE=" + locTuple); + for (Iterator iterator3 = subGlobalReachableSet.iterator(); iterator3.hasNext();) { + GlobalFlowNode subGlobalReachalbeNode = (GlobalFlowNode) iterator3.next(); + // NTuple locTuple = translateToLocTuple(md, reachalbeNode.getDescTuple()); + NTuple globalReachlocTuple = subGlobalReachalbeNode.getLocTuple(); + for (int i = 0; i < globalReachlocTuple.size(); i++) { + if (globalReachlocTuple.get(i).equals(lastLocationOfPrefix)) { + // System.out.println("ARG " + argTuple + " IS MATCHED WITH=" + // + lastLocationOfPrefix); + return true; + } + } + } + } + } + } + } + + return false; + } + + private boolean checkNodeReachToReturnNode(MethodDescriptor md, FlowNode node) { + + FlowGraph flowGraph = getFlowGraph(md); + Set reachableSet = flowGraph.getReachFlowNodeSetFrom(node); + if (mapMethodDescriptorToCompositeReturnCase.containsKey(md)) { + boolean hasCompReturnLocWithThis = + mapMethodDescriptorToCompositeReturnCase.get(md).booleanValue(); + + if (hasCompReturnLocWithThis) { + for (Iterator iterator = flowGraph.getReturnNodeSet().iterator(); iterator.hasNext();) { + FlowNode returnFlowNode = (FlowNode) iterator.next(); + if (reachableSet.contains(returnFlowNode)) { + return true; + } + } + } + } + return false; } private void assignCompositeLocation(CompositeLocation compLocPrefix, GlobalFlowNode node) { @@ -696,17 +1996,15 @@ public class LocationInference { private List> calculatePrefixList(GlobalFlowGraph graph, GlobalFlowNode node) { - System.out.println("\n##### calculatePrefixList node=" + node); - - MethodDescriptor md = graph.getMethodDescriptor(); + // System.out.println("\n##### calculatePrefixList node=" + node); Set incomingNodeSetPrefix = graph.getIncomingNodeSetByPrefix(node.getLocTuple().get(0)); - // System.out.println("incomingNodeSetPrefix=" + incomingNodeSetPrefix); - // - // Set reachableNodeSetPrefix = - // graph.getReachableNodeSetByPrefix(node.getLocTuple().get(0)); - // System.out.println("reachableNodeSetPrefix=" + reachableNodeSetPrefix); + // System.out.println("---incomingNodeSetPrefix=" + incomingNodeSetPrefix); + + Set reachableNodeSetPrefix = + graph.getReachableNodeSetByPrefix(node.getLocTuple().get(0)); + // System.out.println("---reachableNodeSetPrefix=" + reachableNodeSetPrefix); List> prefixList = new ArrayList>(); @@ -714,6 +2012,11 @@ public class LocationInference { GlobalFlowNode inNode = (GlobalFlowNode) iterator.next(); NTuple inNodeTuple = inNode.getLocTuple(); + if (inNodeTuple.get(0).getLocDescriptor() instanceof InterDescriptor + || inNodeTuple.get(0).getLocDescriptor().equals(GLOBALDESC)) { + continue; + } + for (int i = 1; i < inNodeTuple.size(); i++) { NTuple prefix = inNodeTuple.subList(0, i); if (!prefixList.contains(prefix)) { @@ -735,43 +2038,126 @@ public class LocationInference { } } }); + return prefixList; - // List> prefixList = new ArrayList>(); - // - // for (Iterator iterator = incomingNodeSet.iterator(); iterator.hasNext();) { - // GlobalFlowNode inNode = (GlobalFlowNode) iterator.next(); - // NTuple inNodeTuple = inNode.getLocTuple(); - // - // for (int i = 1; i < inNodeTuple.size(); i++) { - // NTuple prefix = inNodeTuple.subList(0, i); - // if (!prefixList.contains(prefix)) { - // prefixList.add(prefix); - // } - // } - // } + } + + private CompositeLocation calculateCompositeLocationFromFlowGraph(MethodDescriptor md, + FlowNode node) { + + // System.out.println("#############################################################"); + // System.out.println("calculateCompositeLocationFromFlowGraph=" + node); + + FlowGraph flowGraph = getFlowGraph(md); + // NTuple paramLocTuple = translateToLocTuple(md, paramNode.getDescTuple()); + // GlobalFlowNode paramGlobalNode = subGlobalFlowGraph.getFlowNode(paramLocTuple); + + List> prefixList = calculatePrefixListFlowGraph(flowGraph, node); + + // Set reachableNodeSet = + // subGlobalFlowGraph.getReachableNodeSetByPrefix(paramGlobalNode.getLocTuple().get(0)); // - // 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; + Set reachableNodeSet = + flowGraph.getReachableSetFrom(node.getDescTuple().subList(0, 1)); + + // Set reachNodeSet = globalFlowGraph.getReachableNodeSetFrom(node); + + // System.out.println("node=" + node + " prefixList=" + prefixList); + + for (int i = 0; i < prefixList.size(); i++) { + NTuple curPrefix = prefixList.get(i); + Set> reachableCommonPrefixSet = new HashSet>(); + + for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) { + FlowNode reachNode = (FlowNode) iterator2.next(); + NTuple reachLocTuple = translateToLocTuple(md, reachNode.getCurrentDescTuple()); + if (reachLocTuple.startsWith(curPrefix)) { + reachableCommonPrefixSet.add(reachLocTuple); + } + } + // System.out.println("reachableCommonPrefixSet=" + reachableCommonPrefixSet); + + if (!reachableCommonPrefixSet.isEmpty()) { + + MethodDescriptor curPrefixFirstElementMethodDesc = + (MethodDescriptor) curPrefix.get(0).getDescriptor(); + + Location curPrefixLocalLoc = curPrefix.get(0); + + Location targetLocalLoc = new Location(md, node.getDescTuple().get(0)); + // Location targetLocalLoc = paramGlobalNode.getLocTuple().get(0); + + CompositeLocation newCompLoc = generateCompositeLocation(curPrefix); + // System.out.println("NEED2ASSIGN COMP LOC TO " + node + " with prefix=" + curPrefix); + // System.out.println("-targetLocalLoc=" + targetLocalLoc + " - newCompLoc=" + + // newCompLoc); + + node.setCompositeLocation(newCompLoc); + + return newCompLoc; + + } + + } + return null; + } + + private List> calculatePrefixListFlowGraph(FlowGraph graph, FlowNode node) { + + // System.out.println("\n##### calculatePrefixList node=" + node); + + MethodDescriptor md = graph.getMethodDescriptor(); + Set incomingNodeSetPrefix = + graph.getIncomingNodeSetByPrefix(node.getDescTuple().get(0)); + // System.out.println("---incomingNodeSetPrefix=" + incomingNodeSetPrefix); + + Set reachableNodeSetPrefix = + graph.getReachableSetFrom(node.getDescTuple().subList(0, 1)); + // System.out.println("---reachableNodeSetPrefix=" + reachableNodeSetPrefix); + + List> prefixList = new ArrayList>(); + + for (Iterator iterator = incomingNodeSetPrefix.iterator(); iterator.hasNext();) { + FlowNode inNode = (FlowNode) iterator.next(); + NTuple inNodeTuple = translateToLocTuple(md, inNode.getCurrentDescTuple()); + + // if (inNodeTuple.get(0).getLocDescriptor() instanceof InterDescriptor + // || inNodeTuple.get(0).getLocDescriptor().equals(GLOBALDESC)) { + // continue; + // } + + for (int i = 1; i < inNodeTuple.size(); i++) { + NTuple prefix = inNodeTuple.subList(0, i); + if (!prefixList.contains(prefix)) { + prefixList.add(prefix); + } + } + } + + Collections.sort(prefixList, new Comparator>() { + public int compare(NTuple arg0, NTuple arg1) { + int s0 = arg0.size(); + int s1 = arg1.size(); + if (s0 > s1) { + return -1; + } else if (s0 == s1) { + return 0; + } else { + return 1; + } + } + }); + + return prefixList; + } private GlobalFlowGraph constructSubGlobalFlowGraph(FlowGraph flowGraph) { MethodDescriptor md = flowGraph.getMethodDescriptor(); - GlobalFlowGraph globalGraph = new GlobalFlowGraph(md); + GlobalFlowGraph globalGraph = getSubGlobalFlowGraph(md); // Set nodeSet = flowGraph.getNodeSet(); Set edgeSet = flowGraph.getEdgeSet(); @@ -782,27 +2168,15 @@ public class LocationInference { NTuple srcDescTuple = edge.getInitTuple(); NTuple dstDescTuple = edge.getEndTuple(); + if (flowGraph.getFlowNode(srcDescTuple) instanceof FlowReturnNode + || flowGraph.getFlowNode(dstDescTuple) instanceof FlowReturnNode) { + continue; + } + // here only keep the first element(method location) of the descriptor // tuple NTuple srcLocTuple = translateToLocTuple(md, srcDescTuple); - // Location srcMethodLoc = srcLocTuple.get(0); - // Descriptor srcVarDesc = srcMethodLoc.getLocDescriptor(); - // // if (flowGraph.isParamDesc(srcVarDesc) && - // (!srcVarDesc.equals(md.getThis()))) { - // if (!srcVarDesc.equals(md.getThis())) { - // srcLocTuple = new NTuple(); - // Location loc = new Location(md, srcVarDesc); - // srcLocTuple.add(loc); - // } - // NTuple dstLocTuple = translateToLocTuple(md, dstDescTuple); - // Location dstMethodLoc = dstLocTuple.get(0); - // Descriptor dstVarDesc = dstMethodLoc.getLocDescriptor(); - // if (!dstVarDesc.equals(md.getThis())) { - // dstLocTuple = new NTuple(); - // Location loc = new Location(md, dstVarDesc); - // dstLocTuple.add(loc); - // } globalGraph.addValueFlowEdge(srcLocTuple, dstLocTuple); @@ -816,7 +2190,6 @@ public class LocationInference { NTuple locTuple = new NTuple(); Descriptor enclosingDesc = md; - // System.out.println("md=" + md + " descTuple=" + descTuple); for (int i = 0; i < descTuple.size(); i++) { Descriptor desc = descTuple.get(i); @@ -828,7 +2201,6 @@ public class LocationInference { } else if (desc instanceof FieldDescriptor) { enclosingDesc = ((FieldDescriptor) desc).getType().getClassDesc(); } else { - // TODO: inter descriptor case enclosingDesc = desc; } @@ -838,8 +2210,7 @@ public class LocationInference { } - private void addValueFlowsFromCalleeSubGlobalFlowGraph(MethodDescriptor mdCaller, - GlobalFlowGraph subGlobalFlowGraph) { + private void addValueFlowsFromCalleeSubGlobalFlowGraph(MethodDescriptor mdCaller) { // the transformation for a call site propagates flows through parameters // if the method is virtual, it also grab all relations from any possible @@ -872,13 +2243,13 @@ public class LocationInference { private void propagateValueFlowsToCallerFromSubGlobalFlowGraph(MethodInvokeNode min, MethodDescriptor mdCaller, MethodDescriptor possibleMdCallee) { - System.out.println("propagateValueFlowsToCallerFromSubGlobalFlowGraph=" + min.printNode(0) - + " by caller=" + mdCaller); + // System.out.println("---propagate from " + min.printNode(0) + " to caller=" + mdCaller); FlowGraph calleeFlowGraph = getFlowGraph(possibleMdCallee); Map> mapIdxToArg = mapMethodInvokeNodeToArgIdxMap.get(min); - System.out.println("mapMethodInvokeNodeToArgIdxMap.get(min)=" - + mapMethodInvokeNodeToArgIdxMap.get(min)); + // System.out.println("-----mapMethodInvokeNodeToArgIdxMap.get(min)=" + // + mapMethodInvokeNodeToArgIdxMap.get(min)); + Set keySet = mapIdxToArg.keySet(); for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { Integer idx = (Integer) iterator.next(); @@ -887,64 +2258,43 @@ public class LocationInference { NTuple argLocTuple = translateToLocTuple(mdCaller, argDescTuple); NTuple paramDescTuple = calleeFlowGraph.getParamFlowNode(idx).getDescTuple(); NTuple paramLocTuple = translateToLocTuple(possibleMdCallee, paramDescTuple); + // System.out.println("-------paramDescTuple=" + paramDescTuple + "->argDescTuple=" + // + argDescTuple); addMapCallerArgToCalleeParam(min, argDescTuple, paramDescTuple); } - } + // addValueFlowBetweenParametersToCaller(min, mdCaller, possibleMdCallee); + NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(possibleMdCallee); Set calleeNodeSet = calleeSubGlobalGraph.getNodeSet(); - System.out.println("#calleeNodeSet=" + calleeNodeSet); for (Iterator iterator = calleeNodeSet.iterator(); iterator.hasNext();) { GlobalFlowNode calleeNode = (GlobalFlowNode) iterator.next(); - addValueFlowFromCalleeNode(min, mdCaller, possibleMdCallee, calleeNode); - } + addValueFlowFromCalleeNode(min, mdCaller, possibleMdCallee, calleeNode); + } + + // System.out.println("$$$GLOBAL PC LOC ADD=" + mdCaller); + Set> pcLocTupleSet = mapMethodInvokeNodeToPCLocTupleSet.get(min); + // System.out.println("---pcLocTupleSet=" + pcLocTupleSet); + GlobalFlowGraph callerSubGlobalGraph = getSubGlobalFlowGraph(mdCaller); + for (Iterator iterator = calleeNodeSet.iterator(); iterator.hasNext();) { + GlobalFlowNode calleeNode = (GlobalFlowNode) iterator.next(); + if (calleeNode.isParamNodeWithIncomingFlows()) { + // System.out.println("calleeNode.getLocTuple()" + calleeNode.getLocTuple()); + NTuple callerSrcNodeLocTuple = + translateToCallerLocTuple(min, possibleMdCallee, mdCaller, calleeNode.getLocTuple()); + // System.out.println("---callerSrcNodeLocTuple=" + callerSrcNodeLocTuple); + if (callerSrcNodeLocTuple != null && callerSrcNodeLocTuple.size() > 0) { + for (Iterator iterator2 = pcLocTupleSet.iterator(); iterator2.hasNext();) { + NTuple pcLocTuple = (NTuple) iterator2.next(); + + callerSubGlobalGraph.addValueFlowEdge(pcLocTuple, callerSrcNodeLocTuple); + } + } + } - // int numParam = calleeFlowGraph.getNumParameters(); - // for (int idx = 0; idx < numParam; idx++) { - // - // FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx); - // - // NTuple paramLocTuple = - // translateToLocTuple(possibleMdCallee, paramNode.getCurrentDescTuple()); - // - // GlobalFlowNode globalParamNode = - // calleeSubGlobalGraph.getFlowNode(paramLocTuple); - // - // NTuple argTuple = - // mapMethodInvokeNodeToArgIdxMap.get(min).get(idx); - // - // NTuple argLocTuple = translateToLocTuple(mdCaller, argTuple); - // - // System.out.println("argTupleSet=" + argLocTuple + " param=" + - // paramLocTuple); - // // here, it adds all value flows reachable from the paramNode in the - // callee's flow graph - // - // addValueFlowsFromCalleeParam(mdCaller, argLocTuple, baseLocTuple, - // possibleMdCallee, - // globalParamNode); - // } - // - // // TODO - // // FlowGraph callerSubGlobalGraph = getSubGlobalFlowGraph(mdCaller); - // // FlowGraph calleeSubGlobalGraph = - // getSubGlobalFlowGraph(possibleMdCallee); - // // - // // int numParam = calleeSubGlobalGraph.getNumParameters(); - // // for (int idx = 0; idx < numParam; idx++) { - // // FlowNode paramNode = calleeSubGlobalGraph.getParamFlowNode(idx); - // // NTuple argTuple = - // mapMethodInvokeNodeToArgIdxMap.get(min).get(idx); - // // System.out.println("argTupleSet=" + argTuple + " param=" + - // paramNode); - // // // here, it adds all value flows reachable from the paramNode in the - // callee's flow graph - // // addValueFlowsFromCalleeParam(min, calleeSubGlobalGraph, paramNode, - // callerSubGlobalGraph, - // // argTuple, baseTuple); - // // } + } } @@ -954,17 +2304,24 @@ public class LocationInference { GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(mdCallee); GlobalFlowGraph callerSubGlobalGraph = getSubGlobalFlowGraph(mdCaller); + // System.out.println("$addValueFlowFromCalleeNode calleeSrcNode=" + calleeSrcNode); + NTuple callerSrcNodeLocTuple = translateToCallerLocTuple(min, mdCallee, mdCaller, calleeSrcNode.getLocTuple()); + // System.out.println("---callerSrcNodeLocTuple=" + callerSrcNodeLocTuple); + + if (callerSrcNodeLocTuple != null && callerSrcNodeLocTuple.size() > 0) { - if (callerSrcNodeLocTuple != null) { Set outNodeSet = calleeSubGlobalGraph.getOutNodeSet(calleeSrcNode); for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) { GlobalFlowNode outNode = (GlobalFlowNode) iterator.next(); NTuple callerDstNodeLocTuple = translateToCallerLocTuple(min, mdCallee, mdCaller, outNode.getLocTuple()); - if (callerDstNodeLocTuple != null) { + // System.out.println("outNode=" + outNode + " callerDstNodeLocTuple=" + // + callerDstNodeLocTuple); + if (callerSrcNodeLocTuple != null && callerDstNodeLocTuple != null + && callerSrcNodeLocTuple.size() > 0 && callerDstNodeLocTuple.size() > 0) { callerSubGlobalGraph.addValueFlowEdge(callerSrcNodeLocTuple, callerDstNodeLocTuple); } } @@ -977,17 +2334,20 @@ public class LocationInference { // this method will return the same nodeLocTuple if the corresponding argument is literal // value. - FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); + // System.out.println("translateToCallerLocTuple=" + nodeLocTuple); + FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); NTuple nodeDescTuple = translateToDescTuple(nodeLocTuple); if (calleeFlowGraph.isParameter(nodeDescTuple)) { int paramIdx = calleeFlowGraph.getParamIdx(nodeDescTuple); NTuple argDescTuple = mapMethodInvokeNodeToArgIdxMap.get(min).get(paramIdx); - if (argDescTuple.size() == 0) { - // argument is literal - return nodeLocTuple.clone(); - } + // if (isPrimitive(nodeLocTuple.get(0).getLocDescriptor())) { + // // the type of argument is primitive. + // return nodeLocTuple.clone(); + // } + // System.out.println("paramIdx=" + paramIdx + " argDescTuple=" + argDescTuple + " from min=" + // + min.printNode(0)); NTuple argLocTuple = translateToLocTuple(mdCaller, argDescTuple); NTuple callerLocTuple = new NTuple(); @@ -1003,192 +2363,50 @@ public class LocationInference { } - private NTuple translateToDescTuple(NTuple locTuple) { - - NTuple descTuple = new NTuple(); - for (int i = 0; i < locTuple.size(); i++) { - descTuple.add(locTuple.get(i).getLocDescriptor()); - } - return descTuple; - - } - - private void addValueFlowsFromCalleeParam(MethodDescriptor mdCaller, - NTuple argLocTuple, NTuple baseLocTuple, MethodDescriptor mdCallee, - GlobalFlowNode globalParamNode) { - - Set visited = new HashSet(); - visited.add(globalParamNode); - recurAddValueFlowsFromCalleeParam(mdCaller, argLocTuple, baseLocTuple, mdCallee, - globalParamNode); - - } - - private void recurAddValueFlowsFromCalleeParam(MethodDescriptor mdCaller, - NTuple argLocTuple, NTuple baseLocTuple, MethodDescriptor mdCallee, - GlobalFlowNode calleeCurNode) { - - // FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); - // GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(mdCallee); - // - // NTuple curNodeLocTuple = calleeCurNode.getLocTuple(); - // NTuple curNodeDescTuple = calleeCurNode.getDescTuple(); - // if (calleeFlowGraph.isParameter(curNodeDescTuple)) { - // curNodeLocTuple = translateToCaller(argLocTuple, curNodeLocTuple); - // } - // - // Set outNodeSet = - // calleeSubGlobalGraph.getOutNodeSet(calleeCurNode); - // for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) { - // GlobalFlowNode outNode = (GlobalFlowNode) iterator.next(); - // - // NTuple curNodeLocTuple = calleeCurNode.getLocTuple(); - // NTuple curNodeDescTuple = calleeCurNode.getDescTuple(); - // if (calleeFlowGraph.isParameter(curNodeDescTuple)) { - // curNodeLocTuple = translateToCaller(argLocTuple, curNodeLocTuple); - // } - // - // outNode.getDescTuple(); - // - // if (calleeFlowGraph.is) - // - // if (calleeSubGlobalGraph.isParameter(srcDescTuple)) { - // // destination node is started with 'parameter' - // // need to translate it in terms of the caller's a node - // srcDescTuple = - // translateToCaller(min, calleeSubGlobalGraph.getParamIdx(srcDescTuple), - // srcDescTuple); - // } - // - // } - // - // Set edgeSet = - // calleeSubGlobalGraph.getOutEdgeSetStartingFrom(calleeSrcNode); - // for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) { - // FlowEdge flowEdge = (FlowEdge) iterator.next(); - // - // NTuple srcDescTuple = flowEdge.getInitTuple(); - // NTuple dstDescTuple = flowEdge.getEndTuple(); - // - // FlowNode dstNode = calleeSubGlobalGraph.getFlowNode(dstDescTuple); - // - // if (calleeSubGlobalGraph.isParameter(srcDescTuple)) { - // // destination node is started with 'parameter' - // // need to translate it in terms of the caller's a node - // srcDescTuple = - // translateToCaller(min, calleeSubGlobalGraph.getParamIdx(srcDescTuple), - // srcDescTuple); - // } - // - // if (calleeSubGlobalGraph.isParameter(dstDescTuple)) { - // // destination node is started with 'parameter' - // // need to translate it in terms of the caller's a node - // dstDescTuple = - // translateToCaller(min, calleeSubGlobalGraph.getParamIdx(dstDescTuple), - // dstDescTuple); - // } - // - // callerSubGlobalGraph.addValueFlowEdge(srcDescTuple, dstDescTuple); - // - // if (!visited.contains(dstNode)) { - // visited.add(dstNode); - // recurAddValueFlowsFromCalleeParam(min, calleeSubGlobalGraph, dstNode, - // callerSubGlobalGraph, - // dstDescTuple, visited, baseTuple); - // } - // - // } - - } - - private NTuple translateToCaller(NTuple argLocTuple, - NTuple curNodeLocTuple) { - - NTuple callerLocTuple = new NTuple(); + public static boolean isPrimitive(Descriptor desc) { - callerLocTuple.addAll(argLocTuple); - for (int i = 1; i < curNodeLocTuple.size(); i++) { - callerLocTuple.add(curNodeLocTuple.get(i)); + if (desc instanceof FieldDescriptor) { + return ((FieldDescriptor) desc).getType().isPrimitive(); + } else if (desc instanceof VarDescriptor) { + return ((VarDescriptor) desc).getType().isPrimitive(); + } else if (desc instanceof InterDescriptor) { + return true; } - return callerLocTuple; + return false; } - private void recurAddValueFlowsFromCalleeParam(MethodInvokeNode min, - FlowGraph calleeSubGlobalGraph, FlowNode calleeSrcNode, FlowGraph callerSubGlobalGraph, - NTuple callerSrcTuple, Set visited, NTuple baseTuple) { - - MethodDescriptor mdCallee = calleeSubGlobalGraph.getMethodDescriptor(); - - // Set edgeSet = - // calleeSubGlobalGraph.getOutEdgeSet(calleeSrcNode); - Set edgeSet = calleeSubGlobalGraph.getOutEdgeSetStartingFrom(calleeSrcNode); - for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) { - FlowEdge flowEdge = (FlowEdge) iterator.next(); - - NTuple srcDescTuple = flowEdge.getInitTuple(); - NTuple dstDescTuple = flowEdge.getEndTuple(); + public static boolean isReference(Descriptor desc) { - FlowNode dstNode = calleeSubGlobalGraph.getFlowNode(dstDescTuple); - - if (calleeSubGlobalGraph.isParameter(srcDescTuple)) { - // destination node is started with 'parameter' - // need to translate it in terms of the caller's a node - srcDescTuple = - translateToCaller(min, calleeSubGlobalGraph.getParamIdx(srcDescTuple), srcDescTuple); - } + if (desc instanceof FieldDescriptor) { - 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); + TypeDescriptor type = ((FieldDescriptor) desc).getType(); + if (type.isArray()) { + return !type.isPrimitive(); + } else { + return type.isPtr(); } - callerSubGlobalGraph.addValueFlowEdge(srcDescTuple, dstDescTuple); - - if (!visited.contains(dstNode)) { - visited.add(dstNode); - recurAddValueFlowsFromCalleeParam(min, calleeSubGlobalGraph, dstNode, callerSubGlobalGraph, - dstDescTuple, visited, baseTuple); + } else if (desc instanceof VarDescriptor) { + TypeDescriptor type = ((VarDescriptor) desc).getType(); + if (type.isArray()) { + return !type.isPrimitive(); + } else { + return type.isPtr(); } - - } - - } - - private NTuple translateToCaller(MethodInvokeNode min, int paramIdx, - NTuple srcDescTuple) { - - NTuple callerTuple = new NTuple(); - - NTuple argTuple = mapMethodInvokeNodeToArgIdxMap.get(min).get(paramIdx); - - for (int i = 0; i < argTuple.size(); i++) { - callerTuple.add(argTuple.get(i)); - } - - for (int i = 1; i < srcDescTuple.size(); i++) { - callerTuple.add(srcDescTuple.get(i)); } - return callerTuple; + return false; } - private NTuple traslateToCalleeParamTupleToCallerArgTuple( - NTuple calleeInitTuple, NTuple callerSrcTuple) { - - NTuple callerInitTuple = new NTuple(); - - for (int i = 0; i < callerSrcTuple.size(); i++) { - callerInitTuple.add(callerSrcTuple.get(i)); - } + private NTuple translateToDescTuple(NTuple locTuple) { - for (int i = 1; i < calleeInitTuple.size(); i++) { - callerInitTuple.add(calleeInitTuple.get(i)); + NTuple descTuple = new NTuple(); + for (int i = 0; i < locTuple.size(); i++) { + descTuple.add(locTuple.get(i).getLocDescriptor()); } + return descTuple; - return callerInitTuple; } public LocationSummary getLocationSummary(Descriptor d) { @@ -1211,13 +2429,16 @@ public class LocationInference { System.out.println("\nSSJAVA: generate method summary: " + md); FlowGraph flowGraph = getFlowGraph(md); + if (flowGraph == null) { + continue; + } MethodSummary methodSummary = getMethodSummary(md); HierarchyGraph scGraph = getSkeletonCombinationHierarchyGraph(md); // set the 'this' reference location if (!md.isStatic()) { - System.out.println("setThisLocName=" + scGraph.getHNode(md.getThis()).getName()); + // System.out.println("setThisLocName=" + scGraph.getHNode(md.getThis()).getName()); methodSummary.setThisLocName(scGraph.getHNode(md.getThis()).getName()); } @@ -1230,21 +2451,10 @@ public class LocationInference { // inferred composite location for (int paramIdx = 0; paramIdx < flowGraph.getNumParameters(); paramIdx++) { FlowNode flowNode = flowGraph.getParamFlowNode(paramIdx); - CompositeLocation inferredCompLoc = flowNode.getCompositeLocation(); - // NTuple descTuple = flowNode.getDescTuple(); - // - // CompositeLocation assignedCompLoc = flowNode.getCompositeLocation(); - // CompositeLocation inferredCompLoc; - // if (assignedCompLoc != null) { - // inferredCompLoc = translateCompositeLocation(assignedCompLoc); - // } else { - // Descriptor locDesc = descTuple.get(0); - // Location loc = new Location(md, locDesc.getSymbol()); - // loc.setLocDescriptor(locDesc); - // inferredCompLoc = new CompositeLocation(loc); - // } - System.out.println("-paramIdx=" + paramIdx + " infer=" + inferredCompLoc); - System.out.println("-flowNode inferLoc=" + flowNode.getCompositeLocation()); + CompositeLocation inferredCompLoc = + updateCompositeLocation(flowNode.getCompositeLocation()); + // System.out.println("-paramIdx=" + paramIdx + " infer=" + inferredCompLoc + " original=" + // + flowNode.getCompositeLocation()); Descriptor localVarDesc = flowNode.getDescTuple().get(0); methodSummary.addMapVarNameToInferCompLoc(localVarDesc, inferredCompLoc); @@ -1278,9 +2488,9 @@ public class LocationInference { HNode node1 = hierarchyGraph.getHNode(locDesc1); HNode node2 = hierarchyGraph.getHNode(locDesc2); - System.out.println("---node1=" + node1 + " node2=" + node2); - System.out.println("---hierarchyGraph.getIncomingNodeSet(node2)=" - + hierarchyGraph.getIncomingNodeSet(node2)); + // System.out.println("---node1=" + node1 + " node2=" + node2); + // System.out.println("---hierarchyGraph.getIncomingNodeSet(node2)=" + // + hierarchyGraph.getIncomingNodeSet(node2)); if (locDesc1.equals(locDesc2)) { continue; @@ -1320,9 +2530,9 @@ public class LocationInference { HNode node1 = hierarchyGraph.getHNode(locDesc1); HNode node2 = hierarchyGraph.getHNode(locDesc2); - System.out.println("---node1=" + node1 + " node2=" + node2); - System.out.println("---hierarchyGraph.getIncomingNodeSet(node2)=" - + hierarchyGraph.getIncomingNodeSet(node2)); + // System.out.println("---node1=" + node1 + " node2=" + node2); + // System.out.println("---hierarchyGraph.getIncomingNodeSet(node2)=" + // + hierarchyGraph.getIncomingNodeSet(node2)); if (locDesc1.equals(locDesc2)) { continue; @@ -1337,31 +2547,6 @@ public class LocationInference { return false; } - private CompositeLocation translateCompositeLocation(CompositeLocation compLoc) { - CompositeLocation newCompLoc = new CompositeLocation(); - - // System.out.println("compLoc=" + compLoc); - for (int i = 0; i < compLoc.getSize(); i++) { - Location loc = compLoc.get(i); - Descriptor enclosingDescriptor = loc.getDescriptor(); - Descriptor locDescriptor = loc.getLocDescriptor(); - - HNode hnode = getHierarchyGraph(enclosingDescriptor).getHNode(locDescriptor); - // System.out.println("-hnode=" + hnode + " from=" + locDescriptor + - // " enclosingDescriptor=" - // + enclosingDescriptor); - // System.out.println("-getLocationSummary(enclosingDescriptor)=" - // + getLocationSummary(enclosingDescriptor)); - String locName = getLocationSummary(enclosingDescriptor).getLocationName(hnode.getName()); - // System.out.println("-locName=" + locName); - Location newLoc = new Location(enclosingDescriptor, locName); - newLoc.setLocDescriptor(locDescriptor); - newCompLoc.addLocation(newLoc); - } - - return newCompLoc; - } - private void debug_writeLattices() { Set keySet = mapDescriptorToSimpleLattice.keySet(); @@ -1371,38 +2556,87 @@ public class LocationInference { // HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(key); HierarchyGraph scHierarchyGraph = getSkeletonCombinationHierarchyGraph(key); if (key instanceof ClassDescriptor) { - writeInferredLatticeDotFile((ClassDescriptor) key, scHierarchyGraph, simpleLattice, - "_SIMPLE"); + writeInferredLatticeDotFile((ClassDescriptor) key, simpleLattice, "_SIMPLE"); } else if (key instanceof MethodDescriptor) { MethodDescriptor md = (MethodDescriptor) key; - writeInferredLatticeDotFile(md.getClassDesc(), md, scHierarchyGraph, simpleLattice, - "_SIMPLE"); + writeInferredLatticeDotFile(md.getClassDesc(), md, simpleLattice, "_SIMPLE"); } LocationSummary ls = getLocationSummary(key); - System.out.println("####LOC SUMMARY=" + key + "\n" + ls.getMapHNodeNameToLocationName()); + // System.out.println("####LOC SUMMARY=" + key + "\n" + ls.getMapHNodeNameToLocationName()); } Set cdKeySet = cd2lattice.keySet(); for (Iterator iterator = cdKeySet.iterator(); iterator.hasNext();) { ClassDescriptor cd = (ClassDescriptor) iterator.next(); - writeInferredLatticeDotFile((ClassDescriptor) cd, getSkeletonCombinationHierarchyGraph(cd), - cd2lattice.get(cd), ""); + // System.out.println("########cd=" + cd); + writeInferredLatticeDotFile((ClassDescriptor) cd, cd2lattice.get(cd), ""); + COUNT += cd2lattice.get(cd).getKeySet().size(); } 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), ""); + writeInferredLatticeDotFile(md.getClassDesc(), md, md2lattice.get(md), ""); + COUNT += md2lattice.get(md).getKeySet().size(); + } + System.out.println("###COUNT=" + COUNT); + + Set descKeySet = desc2naiveLattice.keySet(); + for (Iterator iterator = descKeySet.iterator(); iterator.hasNext();) { + Descriptor desc = (Descriptor) iterator.next(); + // System.out.println("########cd=" + cd); + + ClassDescriptor cd_naive; + MethodDescriptor md_naive; + if (desc instanceof ClassDescriptor) { + cd_naive = (ClassDescriptor) desc; + md_naive = null; + } else { + md_naive = (MethodDescriptor) desc; + cd_naive = md_naive.getClassDesc(); + } + + writeInferredLatticeDotFile(cd_naive, md_naive, desc2naiveLattice.get(desc), "_naive"); + } + } + + private void buildLattice(Descriptor desc) { + // System.out.println("buildLattice=" + desc); + SSJavaLattice simpleLattice = buildLattice.buildLattice(desc); + + addMapDescToSimpleLattice(desc, simpleLattice); + + HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc); + // System.out.println("\n## insertIntermediateNodesToStraightLine:" + // + simpleHierarchyGraph.getName()); + SSJavaLattice lattice = + buildLattice.insertIntermediateNodesToStraightLine(desc, simpleLattice); + + if (lattice == null) { + return; + } + lattice.removeRedundantEdges(); + + LocationInference.numLocationsSInfer += lattice.getKeySet().size(); + + 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); } } + // deprecated: it builds method/class lattices without considering class inheritance private void buildLattice() { - BuildLattice buildLattice = new BuildLattice(this); - Set keySet = mapDescriptorToCombineSkeletonHierarchyGraph.keySet(); for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { Descriptor desc = (Descriptor) iterator.next(); @@ -1418,6 +2652,8 @@ public class LocationInference { buildLattice.insertIntermediateNodesToStraightLine(desc, simpleLattice); lattice.removeRedundantEdges(); + LocationInference.numLocationsSInfer += lattice.getKeySet().size(); + if (desc instanceof ClassDescriptor) { // field lattice cd2lattice.put((ClassDescriptor) desc, lattice); @@ -1430,18 +2666,77 @@ public class LocationInference { // 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); + } + + } + + private void buildLatticeInheritanceTree() { + // DFS the inheritance tree and propagates lattice nodes/edges from the parent to children + // Node rootNode = inheritanceTree.getRootNode(); + DFSBuildLatticeInheritanceTree(rootClassDescriptor); + } + + public Set getDirectSubClasses(ClassDescriptor parent) { + + Set result = new HashSet(); + + Set children = tu.getDirectSubClasses(parent); + if (children == null) { + children = new HashSet(); + } + + for (Iterator iterator = children.iterator(); iterator.hasNext();) { + ClassDescriptor child = (ClassDescriptor) iterator.next(); + if (toanalyze_classDescSet.contains(child)) { + result.add(child); + } + } + + return result; + } + + private void DFSBuildLatticeInheritanceTree(ClassDescriptor cd) { + // ClassDescriptor cd = node.getData(); + + ClassDescriptor parentClassDesc = cd.getSuperDesc(); + if (parentClassDesc != null) { + Map parentMap = buildLattice.getIntermediateLocMap(parentClassDesc); + buildLattice.setIntermediateLocMap(cd, parentMap); + } + + buildLattice(cd); + + for (Iterator iterator = cd.getMethods(); iterator.hasNext();) { + MethodDescriptor md = (MethodDescriptor) iterator.next(); + if (toanalyze_methodDescList.contains(md)) { + MethodDescriptor parentMethodDesc = getParentMethodDesc(md.getClassDesc(), md); + if (parentMethodDesc != null) { + Map parentMap = buildLattice.getIntermediateLocMap(parentMethodDesc); + Map childMap = new HashMap(); + Set keySet = parentMap.keySet(); + for (Iterator iterator2 = keySet.iterator(); iterator2.hasNext();) { + TripleItem key = (TripleItem) iterator2.next(); + childMap.put(key, parentMap.get(key)); + } + buildLattice.setIntermediateLocMap(md, childMap); + } + buildLattice(md); + } + } + + // traverse children + Set children = tu.getDirectSubClasses(cd); + if (children != null) { + for (Iterator iterator = children.iterator(); iterator.hasNext();) { + ClassDescriptor classDescriptor = (ClassDescriptor) iterator.next(); + if (toanalyze_classDescSet.contains(classDescriptor)) { + DFSBuildLatticeInheritanceTree(classDescriptor); + } else { + if (classDescriptor.isAbstract()) { + DFSBuildLatticeInheritanceTree(classDescriptor); + } + } + } } } @@ -1458,10 +2753,10 @@ public class LocationInference { Set keySet = mapDescriptorToHierarchyGraph.keySet(); for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { Descriptor desc = (Descriptor) iterator.next(); + // System.out.println("SSJAVA: remove redundant edges: " + desc); HierarchyGraph simpleHierarchyGraph = getHierarchyGraph(desc).clone(); simpleHierarchyGraph.setName(desc + "_SIMPLE"); simpleHierarchyGraph.removeRedundantEdges(); - // simpleHierarchyGraph.simplifyHierarchyGraph(); mapDescriptorToSimpleHierarchyGraph.put(desc, simpleHierarchyGraph); } } @@ -1470,15 +2765,17 @@ public class LocationInference { Set keySet = mapDescriptorToSkeletonHierarchyGraph.keySet(); for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { Descriptor desc = (Descriptor) iterator.next(); - System.out.println("\nSSJAVA: Insering Combination Nodes:" + desc); + System.out.println("\nSSJAVA: Inserting 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(); + // skeletonGraphWithCombinationNode.insertCombinationNodesToGraph(simpleHierarchyGraph, + // skeletonGraph); + // skeletonGraphWithCombinationNode.simplifySkeletonCombinationHierarchyGraph(); + skeletonGraphWithCombinationNode.removeRedundantEdges(); mapDescriptorToCombineSkeletonHierarchyGraph.put(desc, skeletonGraphWithCombinationNode); } } @@ -1487,17 +2784,129 @@ public class LocationInference { Set keySet = mapDescriptorToHierarchyGraph.keySet(); for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { Descriptor desc = (Descriptor) iterator.next(); + System.out.println("SSJAVA: Constructing Skeleton Hierarchy Graph: " + desc); HierarchyGraph simpleGraph = getSimpleHierarchyGraph(desc); HierarchyGraph skeletonGraph = simpleGraph.generateSkeletonGraph(); skeletonGraph.setMapDescToHNode(simpleGraph.getMapDescToHNode()); skeletonGraph.setMapHNodeToDescSet(simpleGraph.getMapHNodeToDescSet()); - skeletonGraph.simplifyHierarchyGraph(); - // skeletonGraph.combineRedundantNodes(false); - // skeletonGraph.removeRedundantEdges(); + skeletonGraph.simplifyHierarchyGraph(this); mapDescriptorToSkeletonHierarchyGraph.put(desc, skeletonGraph); } } + private void recurUpAccumulateInheritanceDesc(Descriptor curDesc, Set set) { + + if (curDesc instanceof ClassDescriptor) { + ClassDescriptor cd = (ClassDescriptor) curDesc; + ClassDescriptor parentClassDesc = cd.getSuperDesc(); + if (parentClassDesc != null && !parentClassDesc.equals(rootClassDescriptor)) { + set.add(parentClassDesc); + recurUpAccumulateInheritanceDesc(parentClassDesc, set); + } + } else { + MethodDescriptor md = (MethodDescriptor) curDesc; + ClassDescriptor cd = md.getClassDesc(); + + // traverse up + ClassDescriptor parentClassDesc = cd.getSuperDesc(); + if (parentClassDesc != null && !parentClassDesc.equals(rootClassDescriptor)) { + + Set methodDescSet = + parentClassDesc.getMethodTable().getSet(md.getSymbol()); + for (Iterator iterator = methodDescSet.iterator(); iterator.hasNext();) { + MethodDescriptor parentMethodDesc = (MethodDescriptor) iterator.next(); + if (parentMethodDesc.matches(md)) { + set.add(parentMethodDesc); + recurUpAccumulateInheritanceDesc(parentMethodDesc, set); + } + } + } + + } + + } + + private void recurDownAccumulateInheritanceDesc(Descriptor curDesc, Set set) { + + if (curDesc instanceof ClassDescriptor) { + ClassDescriptor cd = (ClassDescriptor) curDesc; + ClassDescriptor parentClassDesc = cd.getSuperDesc(); + Set directSubClasses = tu.getDirectSubClasses(cd); + for (Iterator iterator = directSubClasses.iterator(); iterator.hasNext();) { + ClassDescriptor child = (ClassDescriptor) iterator.next(); + recurDownAccumulateInheritanceDesc(child, set); + } + } else { + MethodDescriptor md = (MethodDescriptor) curDesc; + ClassDescriptor cd = md.getClassDesc(); + + // traverse down + Set directSubClasses = tu.getDirectSubClasses(cd); + for (Iterator iterator = directSubClasses.iterator(); iterator.hasNext();) { + ClassDescriptor child = (ClassDescriptor) iterator.next(); + + Set methodDescSet = child.getMethodTable().getSet(md.getSymbol()); + for (Iterator iterator2 = methodDescSet.iterator(); iterator2.hasNext();) { + MethodDescriptor childMethodDesc = (MethodDescriptor) iterator2.next(); + if (childMethodDesc.matches(md)) { + set.add(childMethodDesc); + recurDownAccumulateInheritanceDesc(childMethodDesc, set); + } + } + } + + } + + } + + private void accumulateInheritanceDesc(Descriptor curDesc, Set set) { + + recurUpAccumulateInheritanceDesc(curDesc, set); + recurDownAccumulateInheritanceDesc(curDesc, set); + + } + + public boolean isValidMergeInheritanceCheck(Descriptor desc, Set mergeSet) { + + // set up inheritance chain set... + Set inheritanceDescSet = new HashSet(); + recurUpAccumulateInheritanceDesc(desc, inheritanceDescSet); + + nextgraph: for (Iterator iterator = inheritanceDescSet.iterator(); iterator.hasNext();) { + Descriptor inheritDesc = (Descriptor) iterator.next(); + + if (!desc.equals(inheritDesc)) { + HierarchyGraph graph = getSkeletonCombinationHierarchyGraph(inheritDesc); + + // first check whether this graph includes all elements of the merge set + for (Iterator iterator2 = mergeSet.iterator(); iterator2.hasNext();) { + HNode node = (HNode) iterator2.next(); + if (!graph.contains(node)) { + continue nextgraph; + } + } + + HNode firstNode = mergeSet.iterator().next(); + + Set incomingNode = graph.getIncomingNodeSet(firstNode); + Set outgoingNode = graph.getOutgoingNodeSet(firstNode); + + for (Iterator iterator2 = mergeSet.iterator(); iterator2.hasNext();) { + HNode node = (HNode) iterator2.next(); + + if (!graph.getIncomingNodeSet(node).equals(incomingNode) + || !graph.getOutgoingNodeSet(node).equals(outgoingNode)) { + return false; + } + + } + } + + } + + return true; + } + private void debug_writeHierarchyDotFiles() { Set keySet = mapDescriptorToHierarchyGraph.keySet(); @@ -1515,6 +2924,7 @@ public class LocationInference { Descriptor desc = (Descriptor) iterator.next(); getHierarchyGraph(desc).writeGraph(); getSimpleHierarchyGraph(desc).writeGraph(); + getSimpleHierarchyGraph(desc).writeGraph(true); } } @@ -1527,41 +2937,94 @@ public class LocationInference { getSkeletonHierarchyGraph(desc).writeGraph(); } - } - - private void debug_writeSkeletonCombinationHierarchyDotFiles() { - + } + + 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() { + + LinkedList methodDescList = + (LinkedList) toanalyze_methodDescList.clone(); + + while (!methodDescList.isEmpty()) { + MethodDescriptor md = methodDescList.removeLast(); + if (state.SSJAVADEBUG) { + HierarchyGraph hierarchyGraph = new HierarchyGraph(md); + System.out.println(); + System.out.println("SSJAVA: Construcing the hierarchy graph from " + md); + constructHierarchyGraph(md, hierarchyGraph); + mapDescriptorToHierarchyGraph.put(md, hierarchyGraph); + + } + } + + setupToAnalyze(); + while (!toAnalyzeIsEmpty()) { + ClassDescriptor cd = toAnalyzeNext(); + HierarchyGraph graph = getHierarchyGraph(cd); + for (Iterator iter = cd.getFields(); iter.hasNext();) { + FieldDescriptor fieldDesc = (FieldDescriptor) iter.next(); + if (!(fieldDesc.isStatic() && fieldDesc.isFinal())) { + graph.getHNode(fieldDesc); + } + } + } + Set keySet = mapDescriptorToHierarchyGraph.keySet(); for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { - Descriptor desc = (Descriptor) iterator.next(); - getSkeletonCombinationHierarchyGraph(desc).writeGraph(); - } - - } + Descriptor key = (Descriptor) iterator.next(); + HierarchyGraph graph = getHierarchyGraph(key); + + Set nodeToBeConnected = new HashSet(); + for (Iterator iterator2 = graph.getNodeSet().iterator(); iterator2.hasNext();) { + HNode node = (HNode) iterator2.next(); + if (!node.isSkeleton() && !node.isCombinationNode()) { + if (graph.getIncomingNodeSet(node).size() == 0) { + nodeToBeConnected.add(node); + } + } + } - public HierarchyGraph getSimpleHierarchyGraph(Descriptor d) { - return mapDescriptorToSimpleHierarchyGraph.get(d); - } + for (Iterator iterator2 = nodeToBeConnected.iterator(); iterator2.hasNext();) { + HNode node = (HNode) iterator2.next(); + // System.out.println("NEED TO BE CONNECTED TO TOP=" + node); + graph.addEdge(graph.getHNode(TOPDESC), node); + } - private HierarchyGraph 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() { + private void constructHierarchyGraph2() { // do fixed-point analysis - ssjava.init(); LinkedList descriptorListToAnalyze = ssjava.getSortedDescriptors(); // Collections.sort(descriptorListToAnalyze, new @@ -1634,6 +3097,29 @@ public class LocationInference { } } + Set keySet = mapDescriptorToHierarchyGraph.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Descriptor key = (Descriptor) iterator.next(); + HierarchyGraph graph = getHierarchyGraph(key); + + Set nodeToBeConnected = new HashSet(); + for (Iterator iterator2 = graph.getNodeSet().iterator(); iterator2.hasNext();) { + HNode node = (HNode) iterator2.next(); + if (!node.isSkeleton() && !node.isCombinationNode()) { + if (graph.getIncomingNodeSet(node).size() == 0) { + nodeToBeConnected.add(node); + } + } + } + + for (Iterator iterator2 = nodeToBeConnected.iterator(); iterator2.hasNext();) { + HNode node = (HNode) iterator2.next(); + // System.out.println("NEED TO BE CONNECTED TO TOP=" + node); + graph.addEdge(graph.getHNode(TOPDESC), node); + } + + } + } private HierarchyGraph getHierarchyGraph(Descriptor d) { @@ -1647,7 +3133,9 @@ public class LocationInference { // visit each node of method flow graph FlowGraph fg = getFlowGraph(md); - Set nodeSet = fg.getNodeSet(); + // Set nodeSet = fg.getNodeSet(); + + Set edgeSet = fg.getEdgeSet(); Set paramDescSet = fg.getMapParamDescToIdx().keySet(); for (Iterator iterator = paramDescSet.iterator(); iterator.hasNext();) { @@ -1658,29 +3146,108 @@ public class LocationInference { // for the method lattice, we need to look at the first element of // NTuple boolean hasGlobalAccess = false; - for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { - FlowNode srcNode = (FlowNode) iterator.next(); + // for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + // FlowNode originalSrcNode = (FlowNode) iterator.next(); + for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) { + FlowEdge edge = (FlowEdge) iterator.next(); - // if the srcNode is started with the global descriptor - // need to set as a skeleton node - if (!hasGlobalAccess && srcNode.getDescTuple().startsWith(GLOBALDESC)) { - hasGlobalAccess = true; + FlowNode originalSrcNode = fg.getFlowNode(edge.getInitTuple()); + Set sourceNodeSet = new HashSet(); + if (originalSrcNode instanceof FlowReturnNode) { + FlowReturnNode rnode = (FlowReturnNode) originalSrcNode; + // System.out.println("rnode=" + rnode); + Set> tupleSet = rnode.getReturnTupleSet(); + for (Iterator iterator2 = tupleSet.iterator(); iterator2.hasNext();) { + NTuple nTuple = (NTuple) iterator2.next(); + sourceNodeSet.add(fg.getFlowNode(nTuple)); + // System.out.println("&&&SOURCE fg.getFlowNode(nTuple)=" + fg.getFlowNode(nTuple)); + } + } else { + sourceNodeSet.add(originalSrcNode); } - Set outEdgeSet = fg.getOutEdgeSet(srcNode); - for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) { - FlowEdge outEdge = (FlowEdge) iterator2.next(); - FlowNode dstNode = outEdge.getDst(); + // System.out.println("---sourceNodeSet=" + sourceNodeSet + " from originalSrcNode=" + // + originalSrcNode); + + for (Iterator iterator3 = sourceNodeSet.iterator(); iterator3.hasNext();) { + FlowNode srcNode = (FlowNode) iterator3.next(); NTuple srcNodeTuple = srcNode.getDescTuple(); - NTuple dstNodeTuple = dstNode.getDescTuple(); + Descriptor srcLocalDesc = srcNodeTuple.get(0); + + if (srcLocalDesc instanceof InterDescriptor + && ((InterDescriptor) srcLocalDesc).getMethodArgIdxPair() != null) { + + if (srcNode.getCompositeLocation() == null) { + continue; + } + } + + // if the srcNode is started with the global descriptor + // need to set as a skeleton node + if (!hasGlobalAccess && srcNode.getDescTuple().startsWith(GLOBALDESC)) { + hasGlobalAccess = true; + } + + // Set outEdgeSet = fg.getOutEdgeSet(originalSrcNode); + // for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) { + // FlowEdge outEdge = (FlowEdge) iterator2.next(); + // FlowNode originalDstNode = outEdge.getDst(); + FlowNode originalDstNode = fg.getFlowNode(edge.getEndTuple()); + + Set dstNodeSet = new HashSet(); + if (originalDstNode instanceof FlowReturnNode) { + FlowReturnNode rnode = (FlowReturnNode) originalDstNode; + // System.out.println("\n-returnNode=" + rnode); + Set> tupleSet = rnode.getReturnTupleSet(); + for (Iterator iterator4 = tupleSet.iterator(); iterator4.hasNext();) { + NTuple nTuple = (NTuple) iterator4.next(); + dstNodeSet.add(fg.getFlowNode(nTuple)); + // System.out.println("&&&DST fg.getFlowNode(nTuple)=" + fg.getFlowNode(nTuple)); + } + } else { + dstNodeSet.add(originalDstNode); + } + // System.out.println("---dstNodeSet=" + dstNodeSet); + for (Iterator iterator4 = dstNodeSet.iterator(); iterator4.hasNext();) { + FlowNode dstNode = (FlowNode) iterator4.next(); + + NTuple dstNodeTuple = dstNode.getDescTuple(); + Descriptor dstLocalDesc = dstNodeTuple.get(0); + + if (dstLocalDesc instanceof InterDescriptor + && ((InterDescriptor) dstLocalDesc).getMethodArgIdxPair() != null) { + if (dstNode.getCompositeLocation() == null) { + // System.out.println("%%%%%%%%%%%%%SKIP=" + dstNode); + continue; + } + } - if (outEdge.getInitTuple().equals(srcNodeTuple) - && outEdge.getEndTuple().equals(dstNodeTuple)) { + // if (outEdge.getInitTuple().equals(srcNodeTuple) + // && outEdge.getEndTuple().equals(dstNodeTuple)) { NTuple srcCurTuple = srcNode.getCurrentDescTuple(); NTuple dstCurTuple = dstNode.getCurrentDescTuple(); + // ////////////////////////// + // inheritance check + if (mapMethodDescToHighestOverriddenMethodDesc.containsKey(md)) { + + MethodDescriptor highestOverriddenMethodDesc = + mapMethodDescToHighestOverriddenMethodDesc.get(md); + + if (srcCurTuple.get(srcCurTuple.size() - 1).getSymbol().startsWith(PCLOC)) { + } + + } + // ////////////////////////// + + // System.out.println("-srcCurTuple=" + srcCurTuple + " dstCurTuple=" + dstCurTuple + // + " srcNode=" + srcNode + " dstNode=" + dstNode); + + // srcCurTuple = translateBaseTuple(srcNode, srcCurTuple); + // dstCurTuple = translateBaseTuple(dstNode, dstCurTuple); + if ((srcCurTuple.size() > 1 && dstCurTuple.size() > 1) && srcCurTuple.get(0).equals(dstCurTuple.get(0))) { @@ -1696,8 +3263,12 @@ public class LocationInference { } extractFlowsBetweenFields(classDesc, srcNode, dstNode, 1); - } else { - // value flow between local var - local var or local var - field + } else if ((srcCurTuple.size() == 1 && dstCurTuple.size() == 1) + || ((srcCurTuple.size() > 1 || dstCurTuple.size() > 1) && !srcCurTuple.get(0).equals( + dstCurTuple.get(0)))) { + + // value flow between a primitive local var - a primitive local var or local var - + // field Descriptor srcDesc = srcCurTuple.get(0); Descriptor dstDesc = dstCurTuple.get(0); @@ -1713,8 +3284,13 @@ public class LocationInference { } + // } + // } + } + } + } // If the method accesses static fields @@ -1724,6 +3300,41 @@ public class LocationInference { } methodGraph.getHNode(GLOBALDESC).setSkeleton(true); + if (ssjava.getMethodContainingSSJavaLoop().equals(md)) { + // if the current method contains the event loop + // we need to set all nodes of the hierarchy graph as a skeleton node + Set hnodeSet = methodGraph.getNodeSet(); + for (Iterator iterator = hnodeSet.iterator(); iterator.hasNext();) { + HNode hnode = (HNode) iterator.next(); + hnode.setSkeleton(true); + } + } + + } + + private NTuple translateBaseTuple(FlowNode flowNode, NTuple inTuple) { + + if (flowNode.getBaseTuple() != null) { + + NTuple translatedTuple = new NTuple(); + + NTuple baseTuple = flowNode.getBaseTuple(); + + for (int i = 0; i < baseTuple.size(); i++) { + translatedTuple.add(baseTuple.get(i)); + } + + for (int i = 1; i < inTuple.size(); i++) { + translatedTuple.add(inTuple.get(i)); + } + + // System.out.println("------TRANSLATED " + inTuple + " -> " + translatedTuple); + return translatedTuple; + + } else { + return inTuple; + } + } private MethodSummary getMethodSummary(MethodDescriptor md) { @@ -1810,6 +3421,9 @@ public class LocationInference { Map> map = lattice.getTable(); Set keySet = map.keySet(); + + // System.out.println("@generateLatticeDefinition=" + desc + " map=" + map); + boolean first = true; for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { String key = (String) iterator.next(); @@ -1855,28 +3469,44 @@ public class LocationInference { } } - rtr += "\")"; - if (desc instanceof MethodDescriptor) { - System.out.println("#EXTRA LOC DECLARATION GEN=" + desc); + // System.out.println("#EXTRA LOC DECLARATION GEN=" + desc); - MethodSummary methodSummary = getMethodSummary((MethodDescriptor) desc); + MethodDescriptor md = (MethodDescriptor) desc; + MethodSummary methodSummary = getMethodSummary(md); + + TypeDescriptor returnType = ((MethodDescriptor) desc).getReturnType(); + if (!ssjava.getMethodContainingSSJavaLoop().equals(desc) && returnType != null + && (!returnType.isVoid())) { + CompositeLocation returnLoc = methodSummary.getRETURNLoc(); + if (returnLoc.getSize() == 1) { + String returnLocStr = generateLocationAnnoatation(methodSummary.getRETURNLoc()); + if (rtr.indexOf(returnLocStr) == -1) { + rtr += "," + returnLocStr; + } + } + } + rtr += "\")"; if (!ssjava.getMethodContainingSSJavaLoop().equals(desc)) { - TypeDescriptor returnType = ((MethodDescriptor) desc).getReturnType(); if (returnType != null && (!returnType.isVoid())) { rtr += "\n@RETURNLOC(\"" + generateLocationAnnoatation(methodSummary.getRETURNLoc()) + "\")"; } + CompositeLocation pcLoc = methodSummary.getPCLoc(); if ((pcLoc != null) && (!pcLoc.get(0).isTop())) { rtr += "\n@PCLOC(\"" + generateLocationAnnoatation(pcLoc) + "\")"; } } - rtr += "\n@THISLOC(\"" + methodSummary.getThisLocName() + "\")"; + if (!md.isStatic()) { + rtr += "\n@THISLOC(\"" + methodSummary.getThisLocName() + "\")"; + } rtr += "\n@GLOBALLOC(\"" + methodSummary.getGlobalLocName() + "\")"; + } else { + rtr += "\")"; } return rtr; @@ -1940,6 +3570,7 @@ public class LocationInference { } SSJavaLattice methodLattice = md2lattice.get(md); + // System.out.println("md=" + md + " methodLattice=" + methodLattice); if (methodLattice != null) { int methodDefLine = md.getLineNum(); @@ -1952,8 +3583,8 @@ public class LocationInference { Map mapVarDescToInferLoc = methodSummary.getMapVarDescToInferCompositeLocation(); - System.out.println("-----md=" + md); - System.out.println("-----mapVarDescToInferLoc=" + mapVarDescToInferLoc); + // System.out.println("-----md=" + md + " methodDefLine=" + methodDefLine); + // System.out.println("-----mapVarDescToInferLoc=" + mapVarDescToInferLoc); Set localVarDescSet = mapVarDescToInferLoc.keySet(); @@ -1961,7 +3592,7 @@ public class LocationInference { for (Iterator iterator = localVarDescSet.iterator(); iterator.hasNext();) { Descriptor localVarDesc = (Descriptor) iterator.next(); - System.out.println("-------localVarDesc=" + localVarDesc); + // System.out.println("-------localVarDesc=" + localVarDesc); CompositeLocation inferLoc = mapVarDescToInferLoc.get(localVarDesc); String localLocIdentifier = inferLoc.get(0).getLocIdentifier(); @@ -1975,8 +3606,12 @@ public class LocationInference { if (mapDescToDefinitionLine.containsKey(localVarDesc)) { int varLineNum = mapDescToDefinitionLine.get(localVarDesc); String orgSourceLine = sourceVec.get(varLineNum); + // System.out.println("varLineNum=" + varLineNum + " org src=" + orgSourceLine); int idx = orgSourceLine.indexOf(generateVarDeclaration((VarDescriptor) localVarDesc)); + // System.out.println("idx=" + idx + // + " generateVarDeclaration((VarDescriptor) localVarDesc)=" + // + generateVarDeclaration((VarDescriptor) localVarDesc)); assert (idx != -1); String annoatedStr = orgSourceLine.substring(0, idx) + locAnnotationStr + " " @@ -1989,7 +3624,8 @@ public class LocationInference { int idx = getParamLocation(methodDefStr, generateVarDeclaration((VarDescriptor) localVarDesc)); - + // System.out.println("methodDefStr=" + methodDefStr + " localVarDesc=" + localVarDesc + // + " idx=" + idx); assert (idx != -1); String annoatedStr = @@ -2063,7 +3699,6 @@ public class LocationInference { } private String generateLocationAnnoatation(CompositeLocation loc) { - System.out.println("loc=" + loc); String rtr = ""; // method location Location methodLoc = loc.get(0); @@ -2152,7 +3787,7 @@ public class LocationInference { SSJavaLattice classLattice = cd2lattice.get(cd); if (classLattice != null) { ssjava.writeLatticeDotFile(cd, null, classLattice); - debug_printDescriptorToLocNameMapping(cd); + // debug_printDescriptorToLocNameMapping(cd); } while (!toAnalyzeMethodIsEmpty()) { @@ -2160,7 +3795,7 @@ public class LocationInference { SSJavaLattice methodLattice = md2lattice.get(md); if (methodLattice != null) { ssjava.writeLatticeDotFile(cd, md, methodLattice); - debug_printDescriptorToLocNameMapping(md); + // debug_printDescriptorToLocNameMapping(md); } } } @@ -2178,17 +3813,18 @@ public class LocationInference { } - private void inferLattices() { - } - private void calculateExtraLocations() { - LinkedList descriptorListToAnalyze = ssjava.getSortedDescriptors(); - for (Iterator iterator = descriptorListToAnalyze.iterator(); iterator.hasNext();) { + + // LinkedList methodDescList = ssjava.getSortedDescriptors(); + LinkedList methodDescList = + (LinkedList) toanalyze_methodDescList.clone(); + for (Iterator iterator = methodDescList.iterator(); iterator.hasNext();) { MethodDescriptor md = (MethodDescriptor) iterator.next(); if (!ssjava.getMethodContainingSSJavaLoop().equals(md)) { calculateExtraLocations(md); } } + } private void checkLatticesOfVirtualMethods(MethodDescriptor md) { @@ -2286,7 +3922,7 @@ public class LocationInference { private void calculatePCLOC(MethodDescriptor md) { - System.out.println("#calcualtePCLOC"); + // System.out.println("#CalculatePCLOC"); MethodSummary methodSummary = getMethodSummary(md); FlowGraph fg = getFlowGraph(md); Map mapParamToLoc = methodSummary.getMapParamIdxToInferLoc(); @@ -2295,21 +3931,41 @@ public class LocationInference { // PC location is higher than location types of parameters which has incoming flows. Set> paramLocTupleHavingInFlowSet = new HashSet>(); + Set paramDescNOTHavingInFlowSet = new HashSet(); + // Set paramNodeNOThavingInFlowSet = new HashSet(); int numParams = fg.getNumParameters(); for (int i = 0; i < numParams; i++) { FlowNode paramFlowNode = fg.getParamFlowNode(i); Descriptor prefix = paramFlowNode.getDescTuple().get(0); + NTuple paramDescTuple = paramFlowNode.getCurrentDescTuple(); + NTuple paramLocTuple = translateToLocTuple(md, paramDescTuple); - if (fg.getIncomingNodeSetByPrefix(prefix).size() > 0) { + Set inNodeToParamSet = fg.getIncomingNodeSetByPrefix(prefix); + if (inNodeToParamSet.size() > 0) { // parameter has in-value flows - NTuple paramDescTuple = paramFlowNode.getCurrentDescTuple(); - NTuple paramLocTuple = translateToLocTuple(md, paramDescTuple); - paramLocTupleHavingInFlowSet.add(paramLocTuple); + + for (Iterator iterator = inNodeToParamSet.iterator(); iterator.hasNext();) { + FlowNode inNode = (FlowNode) iterator.next(); + Set outEdgeSet = fg.getOutEdgeSet(inNode); + for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) { + FlowEdge flowEdge = (FlowEdge) iterator2.next(); + if (flowEdge.getEndTuple().startsWith(prefix)) { + NTuple paramLocTupleWithIncomingFlow = + translateToLocTuple(md, flowEdge.getEndTuple()); + paramLocTupleHavingInFlowSet.add(paramLocTupleWithIncomingFlow); + } + } + } + + // paramLocTupleHavingInFlowSet.add(paramLocTuple); + } else { + // paramNodeNOThavingInFlowSet.add(fg.getFlowNode(paramDescTuple)); + paramDescNOTHavingInFlowSet.add(prefix); } } - System.out.println("paramLocTupleHavingInFlowSet=" + paramLocTupleHavingInFlowSet); + // System.out.println("paramLocTupleHavingInFlowSet=" + paramLocTupleHavingInFlowSet); if (paramLocTupleHavingInFlowSet.size() > 0 && !coversAllParamters(md, fg, paramLocTupleHavingInFlowSet)) { @@ -2319,58 +3975,104 @@ public class LocationInference { NTuple pcLocTuple = generateLocTupleRelativeTo(md, paramLocTupleHavingInFlowSet, PCLOC); - int pcLocTupleIdx = pcLocTuple.size() - 1; - Location pcLoc = pcLocTuple.get(pcLocTupleIdx); - Descriptor pcDesc = pcLoc.getLocDescriptor(); - Descriptor enclosingDesc = pcLocTuple.get(pcLocTupleIdx).getDescriptor(); + NTuple pcDescTuple = translateToDescTuple(pcLocTuple); + + // System.out.println("pcLoc=" + pcLocTuple); + + CompositeLocation curPCLoc = methodSummary.getPCLoc(); + if (curPCLoc.get(0).isTop() || pcLocTuple.size() > curPCLoc.getSize()) { + methodSummary.setPCLoc(new CompositeLocation(pcLocTuple)); + + Set flowNodeLowerthanPCLocSet = new HashSet(); + GlobalFlowGraph subGlobalFlowGraph = getSubGlobalFlowGraph(md); + // add ordering relations s.t. PCLOC is higher than all flow nodes except the set of + // parameters that do not have incoming flows + for (Iterator iterator = fg.getNodeSet().iterator(); iterator.hasNext();) { + FlowNode node = (FlowNode) iterator.next(); + + if (!(node instanceof FlowReturnNode)) { + if (!paramDescNOTHavingInFlowSet.contains(node.getCurrentDescTuple().get(0))) { + flowNodeLowerthanPCLocSet.add(node); + fg.addValueFlowEdge(pcDescTuple, node.getDescTuple()); + + subGlobalFlowGraph.addValueFlowEdge(pcLocTuple, + translateToLocTuple(md, node.getDescTuple())); + } + } else { + // System.out.println("***SKIP PCLOC -> RETURNLOC=" + node); + } + + } + fg.getFlowNode(translateToDescTuple(pcLocTuple)).setSkeleton(true); + + if (pcLocTuple.get(0).getLocDescriptor().equals(md.getThis())) { + for (Iterator iterator = flowNodeLowerthanPCLocSet.iterator(); iterator.hasNext();) { + FlowNode lowerNode = (FlowNode) iterator.next(); + if (lowerNode.getDescTuple().size() == 1 && lowerNode.getCompositeLocation() == null) { + NTuple lowerLocTuple = translateToLocTuple(md, lowerNode.getDescTuple()); + CompositeLocation newComp = + calculateCompositeLocationFromSubGlobalGraph(md, lowerNode); + if (newComp != null) { + subGlobalFlowGraph.addMapLocationToInferCompositeLocation(lowerLocTuple.get(0), + newComp); + lowerNode.setCompositeLocation(newComp); + // System.out.println("NEW COMP LOC=" + newComp + " to lowerNode=" + lowerNode); + } - HierarchyGraph hierarchyGraph = getHierarchyGraph(enclosingDesc); - HNode pcNode = hierarchyGraph.getHNode(pcDesc); - pcNode.setSkeleton(true); + } - for (Iterator iterator = paramLocTupleHavingInFlowSet.iterator(); iterator.hasNext();) { - NTuple paramLocTuple = (NTuple) iterator.next(); - if (paramLocTuple.size() > pcLocTupleIdx) { - Descriptor lowerDesc = paramLocTuple.get(pcLocTupleIdx).getLocDescriptor(); - hierarchyGraph.addEdge(pcDesc, lowerDesc); + } } - } - System.out.println("pcLoc=" + pcLoc); + } - methodSummary.setPCLoc(new CompositeLocation(pcLocTuple)); } } - private boolean coversAllParamters(MethodDescriptor md, FlowGraph fg, - Set> paramLocTupleHavingInFlowSet) { + private int countFirstDescriptorSetSize(Set> set) { - int numParam = fg.getNumParameters(); - int size = paramLocTupleHavingInFlowSet.size(); + Set descSet = new HashSet(); - if (!md.isStatic()) { + for (Iterator iterator = set.iterator(); iterator.hasNext();) { + NTuple locTuple = (NTuple) iterator.next(); + descSet.add(locTuple.get(0).getLocDescriptor()); + } - // if the method is not static && there is a parameter composite location && - // it is started with 'this', - // paramLocTupleHavingInFlowSet need to have 'this' parameter. + return descSet.size(); + } - FlowNode thisParamNode = fg.getParamFlowNode(0); - NTuple thisParamLocTuple = - translateToLocTuple(md, thisParamNode.getCurrentDescTuple()); + private boolean coversAllParamters(MethodDescriptor md, FlowGraph fg, + Set> paramLocTupleHavingInFlowSet) { - if (!paramLocTupleHavingInFlowSet.contains(thisParamLocTuple)) { + int numParam = fg.getNumParameters(); + // int size = paramLocTupleHavingInFlowSet.size(); + int size = countFirstDescriptorSetSize(paramLocTupleHavingInFlowSet); - for (Iterator iterator = paramLocTupleHavingInFlowSet.iterator(); iterator.hasNext();) { - NTuple paramTuple = (NTuple) iterator.next(); - if (paramTuple.size() > 1 && paramTuple.get(0).getLocDescriptor().equals(md.getThis())) { - // paramLocTupleHavingInFlowSet.add(thisParamLocTuple); - // break; - size++; - } - } + // System.out.println("numParam=" + numParam + " size=" + size); - } - } + // if (!md.isStatic()) { + // + // // if the method is not static && there is a parameter composite location && + // // it is started with 'this', + // // paramLocTupleHavingInFlowSet need to have 'this' parameter. + // + // FlowNode thisParamNode = fg.getParamFlowNode(0); + // NTuple thisParamLocTuple = + // translateToLocTuple(md, thisParamNode.getCurrentDescTuple()); + // + // if (!paramLocTupleHavingInFlowSet.contains(thisParamLocTuple)) { + // + // for (Iterator iterator = paramLocTupleHavingInFlowSet.iterator(); iterator.hasNext();) { + // NTuple paramTuple = (NTuple) iterator.next(); + // if (paramTuple.size() > 1 && paramTuple.get(0).getLocDescriptor().equals(md.getThis())) { + // // paramLocTupleHavingInFlowSet.add(thisParamLocTuple); + // // break; + // size++; + // } + // } + // + // } + // } if (size == numParam) { return true; @@ -2382,137 +4084,72 @@ public class LocationInference { private void calculateRETURNLOC(MethodDescriptor md) { - System.out.println("#calculateRETURNLOC= " + md); + // System.out.println("#calculateRETURNLOC= " + md); + // calculate a return location: // the return location type is lower than all parameters and the location of return values - MethodSummary methodSummary = getMethodSummary(md); + // if (methodSummary.getRETURNLoc() != null) { + // System.out.println("$HERE?"); + // return; + // } FlowGraph fg = getFlowGraph(md); - Map mapParamToLoc = methodSummary.getMapParamIdxToInferLoc(); Set paramIdxSet = mapParamToLoc.keySet(); - if (!md.getReturnType().isVoid()) { + if (md.getReturnType() != null && !md.getReturnType().isVoid()) { // first, generate the set of return value location types that starts // with 'this' reference - Set> inferFieldReturnLocSet = new HashSet>(); - Set paramFlowNodeFlowingToReturnValueSet = getParamNodeFlowingToReturnValue(md); - System.out.println("paramFlowNodeFlowingToReturnValueSet=" - + paramFlowNodeFlowingToReturnValueSet); + // System.out.println("paramFlowNodeFlowingToReturnValueSet=" + // + paramFlowNodeFlowingToReturnValueSet); - Set> locFlowingToReturnValueSet = new HashSet>(); + Set> tupleToBeHigherThanReturnLocSet = new HashSet>(); for (Iterator iterator = paramFlowNodeFlowingToReturnValueSet.iterator(); iterator.hasNext();) { FlowNode fn = (FlowNode) iterator.next(); - NTuple paramDescTuple = fn.getCurrentDescTuple(); - NTuple paramLocTuple = translateToLocTuple(md, paramDescTuple); - - locFlowingToReturnValueSet.add(paramLocTuple); + tupleToBeHigherThanReturnLocSet.add(translateToLocTuple(md, paramDescTuple)); } Set returnNodeSet = fg.getReturnNodeSet(); for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { FlowNode returnNode = (FlowNode) iterator.next(); NTuple returnDescTuple = returnNode.getCurrentDescTuple(); - NTuple returnLocTuple = translateToLocTuple(md, returnDescTuple); - locFlowingToReturnValueSet.add(returnLocTuple); + tupleToBeHigherThanReturnLocSet.add(translateToLocTuple(md, returnDescTuple)); } - System.out.println("locFlowingToReturnValueSet=" + locFlowingToReturnValueSet); + // System.out.println("-flow graph's returnNodeSet=" + returnNodeSet); + // System.out.println("tupleSetToBeHigherThanReturnLoc=" + tupleToBeHigherThanReturnLocSet); // Here, generates a return location in the method lattice that is lower than the // locFlowingToReturnValueSet NTuple returnLocTuple = - generateLocTupleRelativeTo(md, locFlowingToReturnValueSet, RLOC); + generateLocTupleRelativeTo(md, tupleToBeHigherThanReturnLocSet, RLOC); - System.out.println("returnLocTuple=" + returnLocTuple); + // System.out.println("returnLocTuple=" + returnLocTuple); + NTuple returnDescTuple = translateToDescTuple(returnLocTuple); + CompositeLocation curReturnLoc = methodSummary.getRETURNLoc(); + if (curReturnLoc == null || returnDescTuple.size() > curReturnLoc.getSize()) { + methodSummary.setRETURNLoc(new CompositeLocation(returnLocTuple)); - int returnLocTupleIdx = returnLocTuple.size() - 1; - Location returnLoc = returnLocTuple.get(returnLocTupleIdx); - Descriptor returnDesc = returnLoc.getLocDescriptor(); - Descriptor enclosingDesc = returnLocTuple.get(returnLocTupleIdx).getDescriptor(); - - HierarchyGraph hierarchyGraph = getHierarchyGraph(enclosingDesc); - HNode returnNode = hierarchyGraph.getHNode(returnDesc); - returnNode.setSkeleton(true); + for (Iterator iterator = tupleToBeHigherThanReturnLocSet.iterator(); iterator.hasNext();) { + NTuple higherTuple = (NTuple) iterator.next(); + fg.addValueFlowEdge(translateToDescTuple(higherTuple), returnDescTuple); + } + fg.getFlowNode(returnDescTuple).setSkeleton(true); - for (Iterator iterator = locFlowingToReturnValueSet.iterator(); iterator.hasNext();) { - NTuple locTuple = (NTuple) iterator.next(); - Descriptor higherDesc = locTuple.get(returnLocTupleIdx).getLocDescriptor(); - hierarchyGraph.addEdge(higherDesc, returnDesc); } - methodSummary.setRETURNLoc(new CompositeLocation(returnLocTuple)); - - // skip: for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { - // FlowNode returnNode = (FlowNode) iterator.next(); - // - // NTuple returnDescTuple = returnNode.getCurrentDescTuple(); - // NTuple returnLocTuple = translateToLocTuple(md, returnDescTuple); - // - // if (returnLocTuple.get(0).getLocDescriptor().equals(md.getThis())) { - // // if the location type of the return value matches "this" reference - // // then, check whether this return value is equal to/lower than all - // // of parameters that possibly flow into the return values - // for (Iterator iterator2 = inferParamLocSet.iterator(); iterator2.hasNext();) { - // CompositeLocation paramInferLoc = (CompositeLocation) iterator2.next(); - // - // if ((!paramInferLoc.equals(returnLocTuple)) - // && !isGreaterThan(methodLattice, paramInferLoc, inferReturnLoc)) { - // continue skip; - // } - // } - // inferFieldReturnLocSet.add(returnLocTuple); - // - // } - // } - - // if (inferFieldReturnLocSet.size() > 0) { - // - // // CompositeLocation returnLoc = getLowest(methodLattice, inferFieldReturnLocSet); - // CompositeLocation returnLoc = null; - // if (returnLoc == null) { - // // in this case, assign <'this',bottom> to the RETURNLOC - // returnLoc = new CompositeLocation(new Location(md, md.getThis().getSymbol())); - // returnLoc.addLocation(new Location(md.getClassDesc(), getLattice(md.getClassDesc()) - // .getBottomItem())); - // } - // methodInfo.setReturnLoc(returnLoc); - // - // } else { - // String returnLocSymbol = "RETURNLOC"; - // CompositeLocation returnLocInferLoc = - // new CompositeLocation(new Location(md, returnLocSymbol)); - // methodInfo.setReturnLoc(returnLocInferLoc); - // - // for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) { - // Integer paramIdx = (Integer) iterator.next(); - // CompositeLocation inferLoc = mapParamToLoc.get(paramIdx); - // String paramLocLocalSymbol = inferLoc.get(0).getLocIdentifier(); - // if (!methodLattice.isGreaterThan(paramLocLocalSymbol, returnLocSymbol)) { - // // TODO - // // addRelationHigherToLower(methodLattice, methodInfo, - // // paramLocLocalSymbol, - // // returnLocSymbol); - // } - // } - // - // for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { - // FlowNode returnNode = (FlowNode) iterator.next(); - // CompositeLocation inferLoc = - // generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode)); - // if (!isGreaterThan(methodLattice, inferLoc, returnLocInferLoc)) { - // // TODO - // // addRelation(methodLattice, methodInfo, inferLoc, - // // returnLocInferLoc); - // } - // } - // - // } + // makes sure that PCLOC is higher than RETURNLOC + CompositeLocation pcLoc = methodSummary.getPCLoc(); + if (!pcLoc.get(0).isTop()) { + NTuple pcLocDescTuple = translateToDescTuple(pcLoc.getTuple()); + fg.addValueFlowEdge(pcLocDescTuple, returnDescTuple); + } } + } private void calculateExtraLocations(MethodDescriptor md) { @@ -2528,7 +4165,7 @@ public class LocationInference { private NTuple generateLocTupleRelativeTo(MethodDescriptor md, Set> paramLocTupleHavingInFlowSet, String locNamePrefix) { - System.out.println("-generateLocTupleRelativeTo=" + paramLocTupleHavingInFlowSet); + // System.out.println("-generateLocTupleRelativeTo=" + paramLocTupleHavingInFlowSet); NTuple higherLocTuple = new NTuple(); @@ -2540,10 +4177,21 @@ public class LocationInference { Set> paramLocTupleStartedWithThis = new HashSet>(); - for (Iterator iterator = paramLocTupleHavingInFlowSet.iterator(); iterator.hasNext();) { + next: for (Iterator iterator = paramLocTupleHavingInFlowSet.iterator(); iterator.hasNext();) { NTuple paramLocTuple = (NTuple) iterator.next(); - if (!paramLocTuple.get(0).getLocDescriptor().equals(thisVarDesc)) { + Descriptor paramLocalDesc = paramLocTuple.get(0).getLocDescriptor(); + if (!paramLocalDesc.equals(thisVarDesc)) { + + Set inNodeSet = getFlowGraph(md).getIncomingNodeSetByPrefix(paramLocalDesc); + for (Iterator iterator2 = inNodeSet.iterator(); iterator2.hasNext();) { + FlowNode flowNode = (FlowNode) iterator2.next(); + if (flowNode.getDescTuple().startsWith(thisVarDesc)) { + // System.out.println("paramLocTuple=" + paramLocTuple + " is lower than THIS"); + continue next; + } + } hasParamNotStartedWithThisRef = true; + } else if (paramLocTuple.size() > 1) { paramLocTupleStartedWithThis.add(paramLocTuple); if (minSize == 0 || minSize > paramLocTuple.size()) { @@ -2552,41 +4200,42 @@ public class LocationInference { } } - System.out.println("---paramLocTupleStartedWithThis=" + paramLocTupleStartedWithThis); + // System.out.println("---paramLocTupleStartedWithThis=" + paramLocTupleStartedWithThis); Descriptor enclosingDesc = md; if (hasParamNotStartedWithThisRef) { // in this case, PCLOC will be the local location } else { // all parameter is started with 'this', so PCLOC will be set relative to the composite // location started with 'this'. - for (int idx = 0; idx < minSize - 1; idx++) { + // for (int idx = 0; idx < minSize - 1; idx++) { + for (int idx = 0; idx < 1; idx++) { Set locDescSet = new HashSet(); Location curLoc = null; NTuple paramLocTuple = null; for (Iterator iterator = paramLocTupleStartedWithThis.iterator(); iterator.hasNext();) { paramLocTuple = (NTuple) iterator.next(); - System.out.println("-----paramLocTuple=" + paramLocTuple + " idx=" + idx); + // System.out.println("-----paramLocTuple=" + paramLocTuple + " idx=" + idx); curLoc = paramLocTuple.get(idx); Descriptor locDesc = curLoc.getLocDescriptor(); locDescSet.add(locDesc); } - System.out.println("-----locDescSet=" + locDescSet + " idx=" + idx); + // System.out.println("-----locDescSet=" + locDescSet + " idx=" + idx); if (locDescSet.size() != 1) { break; } Location newLocElement = new Location(curLoc.getDescriptor(), curLoc.getLocDescriptor()); + // System.out.println("newLocElement" + newLocElement); higherLocTuple.add(newLocElement); enclosingDesc = getClassTypeDescriptor(curLoc.getLocDescriptor()); } } - String pcLocIdentifier = locNamePrefix + (locSeed++); - NameDescriptor pcLocDesc = new NameDescriptor(pcLocIdentifier); - Location newLoc = new Location(enclosingDesc, pcLocDesc); + String locIdentifier = locNamePrefix + (locSeed++); + NameDescriptor locDesc = new NameDescriptor(locIdentifier); + Location newLoc = new Location(enclosingDesc, locDesc); higherLocTuple.add(newLoc); - - System.out.println("---new loc tuple=" + higherLocTuple); + // System.out.println("---new loc tuple=" + higherLocTuple); return higherLocTuple; @@ -2621,7 +4270,7 @@ public class LocationInference { for (; iterator.hasNext();) { NTuple curLocTuple = (NTuple) iterator.next(); if (isHigherThan(curLocTuple, highest)) { - System.out.println(curLocTuple + " is greater than " + highest); + // System.out.println(curLocTuple + " is greater than " + highest); highest = curLocTuple; } } @@ -2631,162 +4280,21 @@ public class LocationInference { MethodDescriptor md = (MethodDescriptor) highest.get(0).getDescriptor(); VarDescriptor thisVarDesc = md.getThis(); - System.out.println("highest=" + highest); + // System.out.println("highest=" + highest); for (Iterator> iter = paramLocTupleHavingInFlowSet.iterator(); iter.hasNext();) { NTuple curLocTuple = iter.next(); if (!curLocTuple.equals(highest) && !hasOrderingRelation(highest, curLocTuple)) { - System.out.println("add it to the highest set=" + curLocTuple); + // System.out.println("add it to the highest set=" + curLocTuple); highestSet.add(curLocTuple); } } - - return highestSet; - - } - - private void calculateExtraLocations2(MethodDescriptor md) { - // calcualte pcloc, returnloc,... - - SSJavaLattice methodLattice = getMethodLattice(md); - MethodLocationInfo methodInfo = getMethodLocationInfo(md); - FlowGraph fg = getFlowGraph(md); - Set nodeSet = fg.getNodeSet(); - - for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { - FlowNode flowNode = (FlowNode) iterator.next(); - if (flowNode.isDeclaratonNode()) { - CompositeLocation inferLoc = methodInfo.getInferLocation(flowNode.getDescTuple().get(0)); - String locIdentifier = inferLoc.get(0).getLocIdentifier(); - if (!methodLattice.containsKey(locIdentifier)) { - methodLattice.put(locIdentifier); - } - - } - } - - Map mapParamToLoc = methodInfo.getMapParamIdxToInferLoc(); - Set paramIdxSet = mapParamToLoc.keySet(); - - if (!ssjava.getMethodContainingSSJavaLoop().equals(md)) { - // calculate the initial program counter location - // PC location is higher than location types of all parameters - String pcLocSymbol = "PCLOC"; - - Set paramInFlowSet = new HashSet(); - - for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) { - Integer paramIdx = (Integer) iterator.next(); - - FlowNode paramFlowNode = fg.getParamFlowNode(paramIdx); - - if (fg.getIncomingFlowNodeSet(paramFlowNode).size() > 0) { - // parameter has in-value flows - CompositeLocation inferLoc = mapParamToLoc.get(paramIdx); - paramInFlowSet.add(inferLoc); - } - } - - if (paramInFlowSet.size() > 0) { - CompositeLocation lowestLoc = getLowest(methodLattice, paramInFlowSet); - assert (lowestLoc != null); - methodInfo.setPCLoc(lowestLoc); - } - - } - - // calculate a return location - // the return location type is lower than all parameters and location - // types - // of return values - if (!md.getReturnType().isVoid()) { - // first, generate the set of return value location types that starts - // with - // 'this' reference - - Set inferFieldReturnLocSet = new HashSet(); - - Set paramFlowNode = getParamNodeFlowingToReturnValue(md); - Set inferParamLocSet = new HashSet(); - if (paramFlowNode != null) { - for (Iterator iterator = paramFlowNode.iterator(); iterator.hasNext();) { - FlowNode fn = (FlowNode) iterator.next(); - CompositeLocation inferLoc = - generateInferredCompositeLocation(methodInfo, getFlowGraph(md).getLocationTuple(fn)); - inferParamLocSet.add(inferLoc); - } - } - - Set returnNodeSet = fg.getReturnNodeSet(); - - skip: for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { - FlowNode returnNode = (FlowNode) iterator.next(); - CompositeLocation inferReturnLoc = - generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode)); - if (inferReturnLoc.get(0).getLocIdentifier().equals("this")) { - // if the location type of the return value matches "this" reference - // then, check whether this return value is equal to/lower than all - // of - // parameters that possibly flow into the return values - for (Iterator iterator2 = inferParamLocSet.iterator(); iterator2.hasNext();) { - CompositeLocation paramInferLoc = (CompositeLocation) iterator2.next(); - - if ((!paramInferLoc.equals(inferReturnLoc)) - && !isGreaterThan(methodLattice, paramInferLoc, inferReturnLoc)) { - continue skip; - } - } - inferFieldReturnLocSet.add(inferReturnLoc); - - } - } - - if (inferFieldReturnLocSet.size() > 0) { - - CompositeLocation returnLoc = getLowest(methodLattice, inferFieldReturnLocSet); - if (returnLoc == null) { - // in this case, assign <'this',bottom> to the RETURNLOC - returnLoc = new CompositeLocation(new Location(md, md.getThis().getSymbol())); - returnLoc.addLocation(new Location(md.getClassDesc(), getLattice(md.getClassDesc()) - .getBottomItem())); - } - methodInfo.setReturnLoc(returnLoc); - - } else { - String returnLocSymbol = "RETURNLOC"; - CompositeLocation returnLocInferLoc = - new CompositeLocation(new Location(md, returnLocSymbol)); - methodInfo.setReturnLoc(returnLocInferLoc); - - for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) { - Integer paramIdx = (Integer) iterator.next(); - CompositeLocation inferLoc = mapParamToLoc.get(paramIdx); - String paramLocLocalSymbol = inferLoc.get(0).getLocIdentifier(); - if (!methodLattice.isGreaterThan(paramLocLocalSymbol, returnLocSymbol)) { - // TODO - // addRelationHigherToLower(methodLattice, methodInfo, - // paramLocLocalSymbol, - // returnLocSymbol); - } - } - - for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { - FlowNode returnNode = (FlowNode) iterator.next(); - CompositeLocation inferLoc = - generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode)); - if (!isGreaterThan(methodLattice, inferLoc, returnLocInferLoc)) { - // TODO - // addRelation(methodLattice, methodInfo, inferLoc, - // returnLocInferLoc); - } - } - - } - - } + + return highestSet; + } private Set getHigherLocSymbolThan(SSJavaLattice lattice, String loc) { @@ -2903,24 +4411,18 @@ public class LocationInference { return false; } - private void contributeCalleeFlows(MethodInvokeNode min, MethodDescriptor mdCaller, - MethodDescriptor mdCallee) { - - System.out.println("\n##contributeCalleeFlows callee=" + mdCallee + "TO caller=" + mdCaller); - - getSubGlobalFlowGraph(mdCallee); - - } - private GlobalFlowGraph getSubGlobalFlowGraph(MethodDescriptor md) { + + if (!mapMethodDescriptorToSubGlobalFlowGraph.containsKey(md)) { + mapMethodDescriptorToSubGlobalFlowGraph.put(md, new GlobalFlowGraph(md)); + } return mapMethodDescriptorToSubGlobalFlowGraph.get(md); } private void propagateFlowsToCallerWithNoCompositeLocation(MethodInvokeNode min, MethodDescriptor mdCaller, MethodDescriptor mdCallee) { - System.out.println("\n##PROPAGATE callee=" + mdCallee + "TO caller=" + mdCaller); - + // System.out.println("-propagateFlowsToCallerWithNoCompositeLocation=" + min.printNode(0)); // if the parameter A reaches to the parameter B // then, add an edge the argument A -> the argument B to the caller's flow // graph @@ -2943,222 +4445,95 @@ public class LocationInference { // check if the callee propagates an ordering constraints through // parameters - Set localReachSet = calleeFlowGraph.getLocalReachFlowNodeSetFrom(paramNode1); - System.out.println("-param1=" + paramNode1 + " is higher than param2=" + paramNode2); - System.out.println("-- localReachSet from param1=" + localReachSet); + // Set localReachSet = calleeFlowGraph.getLocalReachFlowNodeSetFrom(paramNode1); + Set localReachSet = + calleeFlowGraph.getReachableSetFrom(paramNode1.getDescTuple()); + + NTuple paramDescTuple1 = paramNode1.getCurrentDescTuple(); + NTuple paramDescTuple2 = paramNode2.getCurrentDescTuple(); + + // System.out.println("-param1CurTuple=" + paramDescTuple1 + " param2CurTuple=" + // + paramDescTuple2); + // System.out.println("-- localReachSet from param1=" + localReachSet); + + if (paramDescTuple1.get(0).equals(paramDescTuple2.get(0))) { + // if two parameters share the same prefix + // it already has been assigned to a composite location + // so we don't need to add an additional ordering relation caused by these two + // paramters. + continue; + } - if (arg1Tuple.size() > 0 && arg2Tuple.size() > 0 && localReachSet.contains(paramNode2)) { + if (arg1Tuple.size() > 0 && arg2Tuple.size() > 0 + && containsPrefix(paramNode2.getDescTuple().get(0), localReachSet)) { // need to propagate an ordering relation s.t. arg1 is higher // than arg2 + // System.out.println("-param1=" + paramNode1 + " is higher than param2=" + paramNode2); - System.out - .println("-arg1Tuple=" + arg1Tuple + " is higher than arg2Tuple=" + arg2Tuple); - - // otherwise, flows between method/field locations... + // add a new flow between the corresponding arguments. callerFlowGraph.addValueFlowEdge(arg1Tuple, arg2Tuple); - System.out.println("arg1=" + arg1Tuple + " arg2=" + arg2Tuple); + // System.out.println("arg1=" + arg1Tuple + " arg2=" + arg2Tuple); + + // System.out + // .println("-arg1Tuple=" + arg1Tuple + " is higher than arg2Tuple=" + arg2Tuple); } - System.out.println(); + // System.out.println(); } } } - System.out.println("##\n"); - - } - - private void propagateFlowsToCaller(MethodInvokeNode min, MethodDescriptor mdCaller, - MethodDescriptor mdCallee) { - - System.out.println("\n##PROPAGATE callee=" + mdCallee + "TO caller=" + mdCaller); - - // if the parameter A reaches to the parameter B - // then, add an edge the argument A -> the argument B to the caller's flow - // graph - - // TODO - // also if a parameter is a composite location and is started with "this" - // reference, - // need to make sure that the corresponding argument is higher than the - // translated location of - // the parameter. - - FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); - FlowGraph callerFlowGraph = getFlowGraph(mdCaller); - int numParam = calleeFlowGraph.getNumParameters(); - - for (int i = 0; i < numParam; i++) { - for (int k = 0; k < numParam; k++) { - - if (i != k) { - - FlowNode paramNode1 = calleeFlowGraph.getParamFlowNode(i); - FlowNode paramNode2 = calleeFlowGraph.getParamFlowNode(k); - - System.out.println("param1=" + paramNode1 + " curDescTuple=" - + paramNode1.getCurrentDescTuple()); - System.out.println("param2=" + paramNode2 + " curDescTuple=" - + paramNode2.getCurrentDescTuple()); - - // TODO: deprecated method - // NodeTupleSet tupleSetArg1 = getNodeTupleSetByArgIdx(min, i); - // NodeTupleSet tupleSetArg2 = getNodeTupleSetByArgIdx(min, k); - NodeTupleSet tupleSetArg1 = null; - NodeTupleSet tupleSetArg2 = null; - - for (Iterator> iter1 = tupleSetArg1.iterator(); iter1.hasNext();) { - NTuple arg1Tuple = iter1.next(); - - for (Iterator> iter2 = tupleSetArg2.iterator(); iter2.hasNext();) { - NTuple arg2Tuple = iter2.next(); - - // check if the callee propagates an ordering constraints through - // parameters - - Set localReachSet = - calleeFlowGraph.getLocalReachFlowNodeSetFrom(paramNode1); - - if (localReachSet.contains(paramNode2)) { - // need to propagate an ordering relation s.t. arg1 is higher - // than arg2 - - System.out - .println("-param1=" + paramNode1 + " is higher than param2=" + paramNode2); - System.out.println("-arg1Tuple=" + arg1Tuple + " is higher than arg2Tuple=" - + arg2Tuple); - - if (!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 + // if a parameter has a composite location and the first element of the parameter location + // matches the callee's 'this' + // we have a more specific constraint: the caller's corresponding argument is higher than the + // parameter location which is translated into the caller - System.out.println("add a flow edge= " + arg1Tuple + "->" - + translatedParamTuple); - callerFlowGraph.addValueFlowEdge(arg1Tuple, translatedParamTuple); - - continue; - - } - - } else if (arg1Tuple.size() == 1 && arg1Tuple.get(0).equals(baseRef)) { - // in this case, the callee flow causes a caller flow - // originated from the object - // whose - // method is invoked. - - System.out.println("###FROM CASE"); - - if (!paramNode2.getCurrentDescTuple().startsWith(mdCallee.getThis())) { - - NTuple param2Prefix = - calculatePrefixForParam(callerFlowGraph, calleeFlowGraph, min, arg2Tuple, - paramNode2); - - if (param2Prefix != null && param2Prefix.startsWith(mdCallee.getThis())) { - // in this case, we need to create a new edge 'this' -> - // 'this.FIELD' but we couldn't... instead we assign the - // corresponding - // parameter a new composite location started with - // 'this' reference - - CompositeLocation compLocForParam2 = - generateCompositeLocation(mdCallee, param2Prefix); - - // System.out.println("set comp loc=" + compLocForParam2 - // + - // " to " + paramNode2); - paramNode1.setCompositeLocation(compLocForParam2); - continue; - } - } - - } - } + for (int idx = 0; idx < numParam; idx++) { + FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx); + CompositeLocation compLoc = paramNode.getCompositeLocation(); + // System.out.println("paramNode=" + paramNode + " compLoc=" + compLoc); + if (compLoc != null && compLoc.get(0).getLocDescriptor().equals(min.getMethod().getThis())) { + // System.out.println("$$$COMPLOC CASE=" + compLoc + " idx=" + idx); + + NTuple argTuple = getNodeTupleByArgIdx(min, idx); + // System.out.println("--- argTuple=" + argTuple + " current compLoc=" + // + callerFlowGraph.getFlowNode(argTuple).getCompositeLocation()); + + NTuple translatedParamTuple = + translateCompositeLocationToCaller(idx, min, compLoc); + // System.out.println("add a flow edge= " + argTuple + "->" + translatedParamTuple); + callerFlowGraph.addValueFlowEdge(argTuple, translatedParamTuple); + + Set> pcLocTupleSet = getPCLocTupleSet(min); + for (Iterator iterator = pcLocTupleSet.iterator(); iterator.hasNext();) { + NTuple pcLocTuple = (NTuple) iterator.next(); + callerFlowGraph.addValueFlowEdge(translateToDescTuple(pcLocTuple), translatedParamTuple); + } - // otherwise, flows between method/field locations... - callerFlowGraph.addValueFlowEdge(arg1Tuple, arg2Tuple); - System.out.println("arg1=" + arg1Tuple + " arg2=" + arg2Tuple); + } + } - } + } - } + private boolean containsPrefix(Descriptor prefixDesc, Set set) { - } - System.out.println(); - } + for (Iterator iterator = set.iterator(); iterator.hasNext();) { + FlowNode flowNode = (FlowNode) iterator.next(); + if (flowNode.getDescTuple().startsWith(prefixDesc)) { + // System.out.println("FOUND=" + flowNode); + return true; } } - System.out.println("##\n"); + return false; } - private NTuple translateCompositeLocationToCaller(MethodInvokeNode min, + private NTuple translateCompositeLocationToCaller(int idx, MethodInvokeNode min, CompositeLocation compLocForParam1) { + NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); NTuple tuple = new NTuple(); - for (int i = 0; i < baseTuple.size(); i++) { tuple.add(baseTuple.get(i)); } @@ -3173,7 +4548,7 @@ public class LocationInference { private CompositeLocation generateCompositeLocation(NTuple prefixLocTuple) { - System.out.println("generateCompositeLocation=" + prefixLocTuple); + // System.out.println("generateCompositeLocation=" + prefixLocTuple); CompositeLocation newCompLoc = new CompositeLocation(); for (int i = 0; i < prefixLocTuple.size(); i++) { @@ -3209,7 +4584,7 @@ public class LocationInference { private CompositeLocation generateCompositeLocation(MethodDescriptor md, NTuple paramPrefix) { - System.out.println("generateCompositeLocation=" + paramPrefix); + // System.out.println("generateCompositeLocation=" + paramPrefix); CompositeLocation newCompLoc = convertToCompositeLocation(md, paramPrefix); @@ -3237,51 +4612,6 @@ public class LocationInference { return newCompLoc; } - private NTuple calculatePrefixForParam(FlowGraph callerFlowGraph, - FlowGraph calleeFlowGraph, MethodInvokeNode min, NTuple arg1Tuple, - FlowNode paramNode1) { - - NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); - Descriptor baseRef = baseTuple.get(baseTuple.size() - 1); - System.out.println("baseRef=" + baseRef); - - FlowNode flowNodeArg1 = callerFlowGraph.getFlowNode(arg1Tuple); - List> callerPrefixList = calculatePrefixList(callerFlowGraph, flowNodeArg1); - System.out.println("callerPrefixList=" + callerPrefixList); - - List> prefixList = calculatePrefixList(calleeFlowGraph, paramNode1); - System.out.println("###prefixList from node=" + paramNode1 + " =" + prefixList); - - List> calleePrefixList = - translatePrefixListToCallee(baseRef, min.getMethod(), callerPrefixList); - - System.out.println("calleePrefixList=" + calleePrefixList); - - Set reachNodeSetFromParam1 = calleeFlowGraph.getReachFlowNodeSetFrom(paramNode1); - System.out.println("reachNodeSetFromParam1=" + reachNodeSetFromParam1); - - for (int i = 0; i < calleePrefixList.size(); i++) { - NTuple curPrefix = calleePrefixList.get(i); - Set> reachableCommonPrefixSet = new HashSet>(); - - for (Iterator iterator2 = reachNodeSetFromParam1.iterator(); iterator2.hasNext();) { - FlowNode reachNode = (FlowNode) iterator2.next(); - if (reachNode.getCurrentDescTuple().startsWith(curPrefix)) { - reachableCommonPrefixSet.add(reachNode.getCurrentDescTuple()); - } - } - - if (!reachableCommonPrefixSet.isEmpty()) { - System.out.println("###REACHABLECOMONPREFIX=" + reachableCommonPrefixSet - + " with curPreFix=" + curPrefix); - return curPrefix; - } - - } - - return null; - } - private List> translatePrefixListToCallee(Descriptor baseRef, MethodDescriptor mdCallee, List> callerPrefixList) { @@ -3303,52 +4633,6 @@ public class LocationInference { } - private List> calculatePrefixList(FlowGraph flowGraph, FlowNode flowNode) { - - System.out.println("\n##### calculatePrefixList=" + flowNode); - - Set inNodeSet = flowGraph.getIncomingFlowNodeSet(flowNode); - inNodeSet.add(flowNode); - - System.out.println("inNodeSet=" + inNodeSet); - - List> prefixList = new ArrayList>(); - - for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) { - FlowNode inNode = (FlowNode) iterator.next(); - - NTuple inNodeTuple = inNode.getCurrentDescTuple(); - - // CompositeLocation inNodeInferredLoc = - // generateInferredCompositeLocation(methodInfo, inNodeTuple); - // NTuple inNodeInferredLocTuple = inNodeInferredLoc.getTuple(); - - for (int i = 1; i < inNodeTuple.size(); i++) { - NTuple prefix = inNodeTuple.subList(0, i); - if (!prefixList.contains(prefix)) { - prefixList.add(prefix); - } - } - } - - Collections.sort(prefixList, new Comparator>() { - public int compare(NTuple arg0, NTuple arg1) { - int s0 = arg0.size(); - int s1 = arg1.size(); - if (s0 > s1) { - return -1; - } else if (s0 == s1) { - return 0; - } else { - return 1; - } - } - }); - - return prefixList; - - } - public CompositeLocation convertToCompositeLocation(MethodDescriptor md, NTuple tuple) { CompositeLocation compLoc = new CompositeLocation(); @@ -3363,13 +4647,15 @@ public class LocationInference { if (curDescriptor instanceof VarDescriptor) { enclosingDescriptor = md.getClassDesc(); + } else if (curDescriptor instanceof FieldDescriptor) { + enclosingDescriptor = ((FieldDescriptor) curDescriptor).getClassDescriptor(); } else if (curDescriptor instanceof NameDescriptor) { // it is "GLOBAL LOC" case! enclosingDescriptor = GLOBALDESC; } else if (curDescriptor instanceof InterDescriptor) { - enclosingDescriptor = null; + enclosingDescriptor = getFlowGraph(md).getEnclosingDescriptor(curDescriptor); } else { - enclosingDescriptor = ((FieldDescriptor) curDescriptor).getClassDescriptor(); + enclosingDescriptor = null; } } @@ -3499,7 +4785,7 @@ public class LocationInference { return false; } - private SSJavaLattice getLattice(Descriptor d) { + public SSJavaLattice getLattice(Descriptor d) { if (d instanceof MethodDescriptor) { return getMethodLattice((MethodDescriptor) d); } else { @@ -3552,8 +4838,16 @@ public class LocationInference { Descriptor srcFieldDesc = srcCurTuple.get(idx); Descriptor dstFieldDesc = dstCurTuple.get(idx); - // add a new edge - getHierarchyGraph(cd).addEdge(srcFieldDesc, dstFieldDesc); + // System.out.println("srcFieldDesc=" + srcFieldDesc + " dstFieldDesc=" + dstFieldDesc + // + " idx=" + idx); + if (!srcFieldDesc.equals(dstFieldDesc)) { + // add a new edge + // System.out.println("-ADD EDGE"); + getHierarchyGraph(cd).addEdge(srcFieldDesc, dstFieldDesc); + } else if (!isReference(srcFieldDesc) && !isReference(dstFieldDesc)) { + // System.out.println("-ADD EDGE"); + getHierarchyGraph(cd).addEdge(srcFieldDesc, dstFieldDesc); + } } @@ -3578,6 +4872,11 @@ public class LocationInference { while (!toAnalyzeIsEmpty()) { ClassDescriptor cd = toAnalyzeNext(); + if (cd.getClassName().equals("Object")) { + rootClassDescriptor = cd; + // inheritanceTree = new InheritanceTree(cd); + } + setupToAnalazeMethod(cd); temp_toanalyzeMethodList.removeAll(visited); @@ -3600,7 +4899,8 @@ public class LocationInference { for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) { MethodDescriptor calleemd = (MethodDescriptor) iterator.next(); if ((!ssjava.isTrustMethod(calleemd)) - && (!ssjava.isSSJavaUtil(calleemd.getClassDesc()))) { + && (!ssjava.isSSJavaUtil(calleemd.getClassDesc())) + && (!calleemd.getModifiers().isNative())) { if (!visited.contains(calleemd)) { temp_toanalyzeMethodList.add(calleemd); } @@ -3642,10 +4942,33 @@ public class LocationInference { System.out.println(""); toanalyze_methodDescList = computeMethodList(); + // hack... it seems that there is a problem with topological sorting. + // so String.toString(Object o) is appeared too higher in the call chain. + MethodDescriptor mdToString1 = null; + MethodDescriptor mdToString2 = null; + for (Iterator iterator = toanalyze_methodDescList.iterator(); iterator.hasNext();) { + MethodDescriptor md = (MethodDescriptor) iterator.next(); + if (md.toString().equals("public static String String.valueOf(Object o)")) { + mdToString1 = md; + } + if (md.toString().equals("public String Object.toString()")) { + mdToString2 = md; + } + } + + if (mdToString1 != null) { + toanalyze_methodDescList.remove(mdToString1); + toanalyze_methodDescList.addLast(mdToString1); + } + if (mdToString2 != null) { + toanalyze_methodDescList.remove(mdToString2); + toanalyze_methodDescList.addLast(mdToString2); + } + LinkedList methodDescList = (LinkedList) toanalyze_methodDescList.clone(); - System.out.println("@@@methodDescList=" + methodDescList); + // System.out.println("@@@methodDescList=" + methodDescList); // System.exit(0); while (!methodDescList.isEmpty()) { @@ -3682,117 +5005,66 @@ public class LocationInference { // subGlobalFlowGraph.writeGraph("_SUBGLOBAL"); // // propagateFlowsFromCalleesWithNoCompositeLocation(md); - } } // _debug_printGraph(); - methodDescList = (LinkedList) toanalyze_methodDescList.clone(); + } + + private void constructGlobalFlowGraph() { + LinkedList methodDescList = + (LinkedList) toanalyze_methodDescList.clone(); while (!methodDescList.isEmpty()) { MethodDescriptor md = methodDescList.removeLast(); if (state.SSJAVADEBUG) { System.out.println(); - System.out.println("SSJAVA: Constructing a flow graph2: " + md); + System.out.println("SSJAVA: Constructing a sub global flow graph: " + md); - System.out.println("##constructSubGlobalFlowGraph"); - GlobalFlowGraph subGlobalFlowGraph = constructSubGlobalFlowGraph(getFlowGraph(md)); - mapMethodDescriptorToSubGlobalFlowGraph.put(md, subGlobalFlowGraph); + constructSubGlobalFlowGraph(getFlowGraph(md)); // TODO - System.out.println("##addValueFlowsFromCalleeSubGlobalFlowGraph"); - addValueFlowsFromCalleeSubGlobalFlowGraph(md, subGlobalFlowGraph); - subGlobalFlowGraph.writeGraph("_SUBGLOBAL"); - - propagateFlowsFromCalleesWithNoCompositeLocation(md); + // System.out.println("-add Value Flows From CalleeSubGlobalFlowGraph"); + addValueFlowsFromCalleeSubGlobalFlowGraph(md); + // subGlobalFlowGraph.writeGraph("_SUBGLOBAL"); - } - } + // System.out.println("-propagate Flows From Callees With No CompositeLocation"); + // propagateFlowsFromCalleesWithNoCompositeLocation(md); - } + // mark if a parameter has incoming flows + checkParamNodesInSubGlobalFlowGraph(md); - private Set getMethodInvokeNodeSet(MethodDescriptor md) { - if (!mapMethodDescriptorToMethodInvokeNodeSet.containsKey(md)) { - mapMethodDescriptorToMethodInvokeNodeSet.put(md, new HashSet()); + } } - return mapMethodDescriptorToMethodInvokeNodeSet.get(md); } - private void constructSubGlobalFlowGraph(MethodDescriptor md) { - + private void checkParamNodesInSubGlobalFlowGraph(MethodDescriptor md) { + GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md); FlowGraph flowGraph = getFlowGraph(md); - Set setMethodInvokeNode = getMethodInvokeNodeSet(md); - - for (Iterator iter = setMethodInvokeNode.iterator(); iter.hasNext();) { - MethodInvokeNode min = iter.next(); - propagateFlowsFromMethodInvokeNode(md, min); - } - - } + Set paramFlowNodeSet = flowGraph.getParamFlowNodeSet(); + for (Iterator iterator = paramFlowNodeSet.iterator(); iterator.hasNext();) { + FlowNode paramFlowNode = (FlowNode) iterator.next(); + // System.out.println("paramFlowNode=" + paramFlowNode); + NTuple paramDescTuple = paramFlowNode.getDescTuple(); + NTuple paramLocTuple = translateToLocTuple(md, paramDescTuple); + GlobalFlowNode paramGlobalNode = globalFlowGraph.getFlowNode(paramLocTuple); - 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 + Set incomingNodeSet = + globalFlowGraph.getIncomingNodeSetByPrefix(paramLocTuple.get(0)); - 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); - } + if (incomingNodeSet.size() > 0) { + paramGlobalNode.setParamNodeWithIncomingFlows(true); + } - for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) { - MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next(); - contributeCalleeFlows(min, mdCaller, possibleMdCallee); } - } - private void assignCompositeLocation(MethodDescriptor md) { - - FlowGraph flowGraph = getFlowGraph(md); - - Set nodeSet = flowGraph.getNodeSet(); - - next: for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { - FlowNode flowNode = (FlowNode) iterator.next(); - - // assign a composite location only to the local variable - if (flowNode.getCurrentDescTuple().size() == 1) { - - List> prefixList = calculatePrefixList(flowGraph, flowNode); - Set reachSet = flowGraph.getReachFlowNodeSetFrom(flowNode); - - for (int i = 0; i < prefixList.size(); i++) { - NTuple curPrefix = prefixList.get(i); - Set> reachableCommonPrefixSet = new HashSet>(); - - for (Iterator iterator2 = reachSet.iterator(); iterator2.hasNext();) { - FlowNode reachNode = (FlowNode) iterator2.next(); - if (reachNode.getCurrentDescTuple().startsWith(curPrefix)) { - reachableCommonPrefixSet.add(reachNode.getCurrentDescTuple()); - } - } - - if (!reachableCommonPrefixSet.isEmpty()) { - System.out.println("NEED TO ASSIGN COMP LOC TO " + flowNode + " with prefix=" - + curPrefix); - CompositeLocation newCompLoc = generateCompositeLocation(md, curPrefix); - flowNode.setCompositeLocation(newCompLoc); - continue next; - } - - } - } - + private Set getMethodInvokeNodeSet(MethodDescriptor md) { + if (!mapMethodDescriptorToMethodInvokeNodeSet.containsKey(md)) { + mapMethodDescriptorToMethodInvokeNodeSet.put(md, new HashSet()); } - + return mapMethodDescriptorToMethodInvokeNodeSet.get(md); } private void propagateFlowsFromCalleesWithNoCompositeLocation(MethodDescriptor mdCaller) { @@ -3829,40 +5101,6 @@ public class LocationInference { } - private void propagateFlowsFromCallees(MethodDescriptor mdCaller) { - - // the transformation for a call site propagates flows through parameters - // if the method is virtual, it also grab all relations from any possible - // callees - - Set setMethodInvokeNode = - mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller); - - if (setMethodInvokeNode != null) { - - for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) { - MethodInvokeNode min = (MethodInvokeNode) iterator.next(); - MethodDescriptor mdCallee = min.getMethod(); - Set setPossibleCallees = new HashSet(); - if (mdCallee.isStatic()) { - setPossibleCallees.add(mdCallee); - } else { - Set calleeSet = ssjava.getCallGraph().getMethods(mdCallee); - // removes method descriptors that are not invoked by the caller - calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller)); - setPossibleCallees.addAll(calleeSet); - } - - for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) { - MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next(); - propagateFlowsToCaller(min, mdCaller, possibleMdCallee); - } - - } - } - - } - private void analyzeMethodBody(ClassDescriptor cd, MethodDescriptor md) { BlockNode bn = state.getMethodBody(md); NodeTupleSet implicitFlowTupleSet = new NodeTupleSet(); @@ -3938,9 +5176,10 @@ public class LocationInference { newImplicitTupleSet.addTupleSet(implicitFlowTupleSet); newImplicitTupleSet.addTupleSet(condTupleNode); - if (newImplicitTupleSet.size() > 1) { + if (needToGenerateInterLoc(newImplicitTupleSet)) { // need to create an intermediate node for the GLB of conditional // locations & implicit flows + NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); for (Iterator> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) { NTuple tuple = idxIter.next(); @@ -3965,6 +5204,7 @@ public class LocationInference { private void analyzeFlowReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode rn, NodeTupleSet implicitFlowTupleSet) { + // System.out.println("-analyzeFlowReturnNode=" + rn.printNode(0)); ExpressionNode returnExp = rn.getReturnExpression(); if (returnExp != null) { @@ -4002,22 +5242,55 @@ public class LocationInference { // add tuples corresponding to the current implicit flows currentFlowTupleSet.addTupleSet(implicitFlowTupleSet); - if (currentFlowTupleSet.size() > 1) { + // System.out.println("---currentFlowTupleSet=" + currentFlowTupleSet); + + if (needToGenerateInterLoc(currentFlowTupleSet)) { + FlowNode meetNode = fg.createIntermediateNode(); for (Iterator iterator = currentFlowTupleSet.iterator(); iterator.hasNext();) { NTuple currentFlowTuple = (NTuple) iterator.next(); fg.addValueFlowEdge(currentFlowTuple, meetNode.getDescTuple()); } fg.addReturnFlowNode(meetNode.getDescTuple()); - } else if (currentFlowTupleSet.size() == 1) { - NTuple tuple = currentFlowTupleSet.iterator().next(); - fg.addReturnFlowNode(tuple); + } else { + // currentFlowTupleSet = removeLiteralTuple(currentFlowTupleSet); + for (Iterator iterator = currentFlowTupleSet.iterator(); iterator.hasNext();) { + NTuple currentFlowTuple = (NTuple) iterator.next(); + fg.addReturnFlowNode(currentFlowTuple); + } } } } + private NodeTupleSet removeLiteralTuple(NodeTupleSet inSet) { + NodeTupleSet tupleSet = new NodeTupleSet(); + for (Iterator> iter = inSet.iterator(); iter.hasNext();) { + NTuple tuple = iter.next(); + if (!tuple.get(0).equals(LITERALDESC)) { + tupleSet.addTuple(tuple); + } + } + return tupleSet; + } + + private boolean needToGenerateInterLoc(NodeTupleSet tupleSet) { + int size = 0; + for (Iterator> iter = tupleSet.iterator(); iter.hasNext();) { + NTuple descTuple = iter.next(); + if (!descTuple.get(0).equals(LITERALDESC)) { + size++; + } + } + if (size > 1) { + // System.out.println("needToGenerateInterLoc=" + tupleSet + " size=" + size); + return true; + } else { + return false; + } + } + private void analyzeFlowLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln, NodeTupleSet implicitFlowTupleSet) { @@ -4032,9 +5305,13 @@ public class LocationInference { newImplicitTupleSet.addTupleSet(implicitFlowTupleSet); newImplicitTupleSet.addTupleSet(condTupleNode); - if (newImplicitTupleSet.size() > 1) { + newImplicitTupleSet.addGlobalFlowTupleSet(implicitFlowTupleSet.getGlobalLocTupleSet()); + newImplicitTupleSet.addGlobalFlowTupleSet(condTupleNode.getGlobalLocTupleSet()); + + if (needToGenerateInterLoc(newImplicitTupleSet)) { // need to create an intermediate node for the GLB of conditional // locations & implicit flows + NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); for (Iterator> idxIter = newImplicitTupleSet.iterator(); idxIter .hasNext();) { @@ -4087,24 +5364,43 @@ public class LocationInference { analyzeFlowExpressionNode(md, bn.getVarTable(), ln.getCondition(), condTupleNode, null, implicitFlowTupleSet, false); - // /////////// - NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); + NodeTupleSet newImplicitTupleSet = new NodeTupleSet(); + newImplicitTupleSet.addTupleSet(implicitFlowTupleSet); + newImplicitTupleSet.addTupleSet(condTupleNode); - for (Iterator> idxIter = condTupleNode.iterator(); idxIter.hasNext();) { - NTuple tuple = idxIter.next(); - addFlowGraphEdge(md, tuple, interTuple); - } + if (needToGenerateInterLoc(newImplicitTupleSet)) { + // need to create an intermediate node for the GLB of conditional + // locations & implicit flows + + NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); + for (Iterator> idxIter = newImplicitTupleSet.iterator(); idxIter + .hasNext();) { + NTuple tuple = idxIter.next(); + addFlowGraphEdge(md, tuple, interTuple); + } + newImplicitTupleSet.clear(); + newImplicitTupleSet.addTuple(interTuple); - for (Iterator> idxIter = implicitFlowTupleSet.iterator(); idxIter - .hasNext();) { - NTuple tuple = idxIter.next(); - addFlowGraphEdge(md, tuple, interTuple); } - NodeTupleSet newImplicitSet = new NodeTupleSet(); - newImplicitSet.addTuple(interTuple); - analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(), newImplicitSet); - analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(), newImplicitSet); + // /////////// + // NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); + // + // for (Iterator> idxIter = condTupleNode.iterator(); idxIter.hasNext();) { + // NTuple tuple = idxIter.next(); + // addFlowGraphEdge(md, tuple, interTuple); + // } + // + // for (Iterator> idxIter = implicitFlowTupleSet.iterator(); idxIter + // .hasNext();) { + // NTuple tuple = idxIter.next(); + // addFlowGraphEdge(md, tuple, interTuple); + // } + // + // NodeTupleSet newImplicitSet = new NodeTupleSet(); + // newImplicitSet.addTuple(interTuple); + analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(), newImplicitTupleSet); + analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(), newImplicitTupleSet); // /////////// // condTupleNode.addTupleSet(implicitFlowTupleSet); @@ -4121,7 +5417,7 @@ public class LocationInference { private void analyzeFlowIfStatementNode(MethodDescriptor md, SymbolTable nametable, IfStatementNode isn, NodeTupleSet implicitFlowTupleSet) { - System.out.println("analyzeFlowIfStatementNode=" + isn.printNode(0)); + // System.out.println("analyzeFlowIfStatementNode=" + isn.printNode(0)); NodeTupleSet condTupleNode = new NodeTupleSet(); analyzeFlowExpressionNode(md, nametable, isn.getCondition(), condTupleNode, null, @@ -4132,11 +5428,12 @@ public class LocationInference { newImplicitTupleSet.addTupleSet(implicitFlowTupleSet); newImplicitTupleSet.addTupleSet(condTupleNode); - System.out.println("condTupleNode=" + condTupleNode); - System.out.println("implicitFlowTupleSet=" + implicitFlowTupleSet); - System.out.println("newImplicitTupleSet=" + newImplicitTupleSet); + // System.out.println("$$$GGGcondTupleNode=" + condTupleNode.getGlobalLocTupleSet()); + // System.out.println("-condTupleNode=" + condTupleNode); + // System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet); + // System.out.println("-newImplicitTupleSet=" + newImplicitTupleSet); - if (newImplicitTupleSet.size() > 1) { + if (needToGenerateInterLoc(newImplicitTupleSet)) { // need to create an intermediate node for the GLB of conditional locations & implicit flows NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); @@ -4148,6 +5445,18 @@ public class LocationInference { newImplicitTupleSet.addTuple(interTuple); } + // GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md); + // for (Iterator> iterator = condTupleNode.globalIterator(); + // iterator.hasNext();) { + // NTuple calleeReturnLocTuple = iterator.next(); + // for (Iterator> iter2 = newImplicitTupleSet.iterator(); iter2.hasNext();) { + // NTuple callerImplicitTuple = iter2.next(); + // globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, + // translateToLocTuple(md, callerImplicitTuple)); + // } + // } + newImplicitTupleSet.addGlobalFlowTupleSet(condTupleNode.getGlobalLocTupleSet()); + analyzeFlowBlockNode(md, nametable, isn.getTrueBlock(), newImplicitTupleSet); if (isn.getFalseBlock() != null) { @@ -4167,6 +5476,7 @@ public class LocationInference { fn.setDeclarationNode(); if (dn.getExpression() != null) { + // System.out.println("-analyzeFlowDeclarationNode=" + dn.printNode(0)); NodeTupleSet nodeSetRHS = new NodeTupleSet(); analyzeFlowExpressionNode(md, nametable, dn.getExpression(), nodeSetRHS, null, @@ -4174,12 +5484,14 @@ public class LocationInference { // creates edges from RHS to LHS NTuple interTuple = null; - if (nodeSetRHS.size() > 1) { + if (needToGenerateInterLoc(nodeSetRHS)) { interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); } for (Iterator> iter = nodeSetRHS.iterator(); iter.hasNext();) { NTuple fromTuple = iter.next(); + // System.out.println("fromTuple=" + fromTuple + " interTuple=" + interTuple + " tupleLSH=" + // + tupleLHS); addFlowGraphEdge(md, fromTuple, interTuple, tupleLHS); } @@ -4189,6 +5501,23 @@ public class LocationInference { addFlowGraphEdge(md, implicitTuple, tupleLHS); } + GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md); + for (Iterator> iterator = nodeSetRHS.globalIterator(); iterator.hasNext();) { + NTuple calleeReturnLocTuple = iterator.next(); + + globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, translateToLocTuple(md, tupleLHS)); + } + + for (Iterator> iterator = implicitFlowTupleSet.globalIterator(); iterator + .hasNext();) { + NTuple implicitGlobalTuple = iterator.next(); + + globalFlowGraph.addValueFlowEdge(implicitGlobalTuple, translateToLocTuple(md, tupleLHS)); + } + + // System.out.println("-nodeSetRHS=" + nodeSetRHS); + // System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet); + } } @@ -4208,14 +5537,13 @@ public class LocationInference { ExpressionNode en, NodeTupleSet nodeSet, NTuple base, NodeTupleSet implicitFlowTupleSet, boolean isLHS) { + // System.out.println("en=" + en.printNode(0) + " class=" + en.getClass()); + // note that expression node can create more than one flow node // nodeSet contains of flow nodes // base is always assigned to null except the case of a name node! - NTuple flowTuple; - switch (en.kind()) { - case Kind.AssignmentNode: analyzeFlowAssignmentNode(md, nametable, (AssignmentNode) en, nodeSet, base, implicitFlowTupleSet); @@ -4244,7 +5572,7 @@ public class LocationInference { break; case Kind.CreateObjectNode: - analyzeCreateObjectNode(md, nametable, (CreateObjectNode) en); + analyzeCreateObjectNode(md, nametable, (CreateObjectNode) en, nodeSet, implicitFlowTupleSet); break; case Kind.ArrayAccessNode: @@ -4252,7 +5580,7 @@ public class LocationInference { break; case Kind.LiteralNode: - analyzeLiteralNode(md, nametable, (LiteralNode) en); + analyzeFlowLiteralNode(md, nametable, (LiteralNode) en, nodeSet); break; case Kind.MethodInvokeNode: @@ -4285,6 +5613,7 @@ public class LocationInference { // return null; } + return null; } @@ -4300,20 +5629,48 @@ public class LocationInference { private void analyzeFlowTertiaryNode(MethodDescriptor md, SymbolTable nametable, TertiaryNode tn, NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) { + // System.out.println("analyzeFlowTertiaryNode=" + tn.printNode(0)); + NodeTupleSet tertiaryTupleNode = new NodeTupleSet(); analyzeFlowExpressionNode(md, nametable, tn.getCond(), tertiaryTupleNode, null, implicitFlowTupleSet, false); + NodeTupleSet newImplicitTupleSet = new NodeTupleSet(); + newImplicitTupleSet.addTupleSet(implicitFlowTupleSet); + newImplicitTupleSet.addTupleSet(tertiaryTupleNode); + + // System.out.println("$$$GGGcondTupleNode=" + tertiaryTupleNode.getGlobalLocTupleSet()); + // System.out.println("-tertiaryTupleNode=" + tertiaryTupleNode); + // System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet); + // System.out.println("-newImplicitTupleSet=" + newImplicitTupleSet); + + if (needToGenerateInterLoc(newImplicitTupleSet)) { + // need to create an intermediate node for the GLB of conditional locations & implicit flows + NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); + for (Iterator> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) { + NTuple tuple = idxIter.next(); + addFlowGraphEdge(md, tuple, interTuple); + } + newImplicitTupleSet.clear(); + newImplicitTupleSet.addTuple(interTuple); + } + + newImplicitTupleSet.addGlobalFlowTupleSet(tertiaryTupleNode.getGlobalLocTupleSet()); + + // System.out.println("---------newImplicitTupleSet=" + newImplicitTupleSet); + // add edges from tertiaryTupleNode to all nodes of conditional nodes - tertiaryTupleNode.addTupleSet(implicitFlowTupleSet); + // tertiaryTupleNode.addTupleSet(implicitFlowTupleSet); analyzeFlowExpressionNode(md, nametable, tn.getTrueExpr(), tertiaryTupleNode, null, - implicitFlowTupleSet, false); + newImplicitTupleSet, false); analyzeFlowExpressionNode(md, nametable, tn.getFalseExpr(), tertiaryTupleNode, null, - implicitFlowTupleSet, false); + newImplicitTupleSet, false); + nodeSet.addGlobalFlowTupleSet(tertiaryTupleNode.getGlobalLocTupleSet()); nodeSet.addTupleSet(tertiaryTupleNode); + // System.out.println("#tertiary node set=" + nodeSet); } private void addMapCallerMethodDescToMethodInvokeNodeSet(MethodDescriptor caller, @@ -4343,10 +5700,32 @@ public class LocationInference { return mapMethodDescToParamNodeFlowsToReturnValue.get(md); } - private void analyzeFlowMethodInvokeNode(MethodDescriptor md, SymbolTable nametable, + private Set> getPCLocTupleSet(MethodInvokeNode min) { + if (!mapMethodInvokeNodeToPCLocTupleSet.containsKey(min)) { + mapMethodInvokeNodeToPCLocTupleSet.put(min, new HashSet>()); + } + return mapMethodInvokeNodeToPCLocTupleSet.get(min); + } + + private void analyzeFlowMethodInvokeNode(MethodDescriptor mdCaller, SymbolTable nametable, MethodInvokeNode min, NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) { - System.out.println("analyzeFlowMethodInvokeNode=" + min.printNode(0)); + // System.out.println("analyzeFlowMethodInvokeNode=" + min.printNode(0)); + + if (!toanalyze_methodDescList.contains(min.getMethod())) { + return; + } + + addMapMethodDescToMethodInvokeNodeSet(min); + + Set> pcLocTupleSet = getPCLocTupleSet(min); + for (Iterator iterator = implicitFlowTupleSet.iterator(); iterator.hasNext();) { + NTuple pcDescTuple = (NTuple) iterator.next(); + if (!pcDescTuple.get(0).equals(LITERALDESC)) { + // here we don't need to add the literal value as a PC location + pcLocTupleSet.add(translateToLocTuple(mdCaller, pcDescTuple)); + } + } mapMethodInvokeNodeToArgIdxMap.put(min, new HashMap>()); @@ -4354,7 +5733,7 @@ public class LocationInference { nodeSet = new NodeTupleSet(); } - MethodDescriptor calleeMethodDesc = min.getMethod(); + MethodDescriptor mdCallee = min.getMethod(); NameDescriptor baseName = min.getBaseName(); boolean isSystemout = false; @@ -4362,24 +5741,35 @@ public class LocationInference { isSystemout = baseName.getSymbol().equals("System.out"); } - if (!ssjava.isSSJavaUtil(calleeMethodDesc.getClassDesc()) - && !ssjava.isTrustMethod(calleeMethodDesc) && !isSystemout) { + if (!ssjava.isSSJavaUtil(mdCallee.getClassDesc()) && !ssjava.isTrustMethod(mdCallee) + && !isSystemout) { - addMapCallerMethodDescToMethodInvokeNodeSet(md, min); + addMapCallerMethodDescToMethodInvokeNodeSet(mdCaller, min); - FlowGraph calleeFlowGraph = getFlowGraph(calleeMethodDesc); + FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); + // System.out.println("mdCallee=" + mdCallee + " calleeFlowGraph=" + calleeFlowGraph); Set calleeReturnSet = calleeFlowGraph.getReturnNodeSet(); - System.out.println("-calleeReturnSet=" + calleeReturnSet); + // System.out.println("---calleeReturnSet=" + calleeReturnSet); + + NodeTupleSet tupleSet = new NodeTupleSet(); if (min.getExpression() != null) { NodeTupleSet baseNodeSet = new NodeTupleSet(); - analyzeFlowExpressionNode(md, nametable, min.getExpression(), baseNodeSet, null, + analyzeFlowExpressionNode(mdCaller, nametable, min.getExpression(), baseNodeSet, null, implicitFlowTupleSet, false); + // System.out.println("baseNodeSet=" + baseNodeSet); assert (baseNodeSet.size() == 1); NTuple baseTuple = baseNodeSet.iterator().next(); + if (baseTuple.get(0) instanceof InterDescriptor) { + if (baseTuple.size() > 1) { + throw new Error(); + } + FlowNode interNode = getFlowGraph(mdCaller).getFlowNode(baseTuple); + baseTuple = translateBaseTuple(interNode, baseTuple); + } mapMethodInvokeNodeToBaseTuple.put(min, baseTuple); if (!min.getMethod().isStatic()) { @@ -4388,20 +5778,35 @@ public class LocationInference { for (Iterator iterator = calleeReturnSet.iterator(); iterator.hasNext();) { FlowNode returnNode = (FlowNode) iterator.next(); NTuple returnDescTuple = returnNode.getDescTuple(); - if (returnDescTuple.startsWith(calleeMethodDesc.getThis())) { + if (returnDescTuple.startsWith(mdCallee.getThis())) { // the location type of the return value is started with 'this' // reference NTuple inFlowTuple = new NTuple(baseTuple.getList()); + + if (inFlowTuple.get(0) instanceof InterDescriptor) { + // min.getExpression() + } else { + + } + inFlowTuple.addAll(returnDescTuple.subList(1, returnDescTuple.size())); - nodeSet.addTuple(inFlowTuple); + // nodeSet.addTuple(inFlowTuple); + // System.out.println("1CREATE A NEW TUPLE=" + inFlowTuple + " from=" + // + mdCallee.getThis()); + // tupleSet.addTuple(inFlowTuple); + tupleSet.addTuple(baseTuple); } else { // TODO + // System.out.println("returnNode=" + returnNode); Set inFlowSet = calleeFlowGraph.getIncomingFlowNodeSet(returnNode); - System.out.println("inFlowSet=" + inFlowSet + " from retrunNode=" + returnNode); + // System.out.println("inFlowSet=" + inFlowSet + " from retrunNode=" + returnNode); for (Iterator iterator2 = inFlowSet.iterator(); iterator2.hasNext();) { FlowNode inFlowNode = (FlowNode) iterator2.next(); - if (inFlowNode.getDescTuple().startsWith(calleeMethodDesc.getThis())) { - nodeSet.addTupleSet(baseNodeSet); + if (inFlowNode.getDescTuple().startsWith(mdCallee.getThis())) { + // nodeSet.addTupleSet(baseNodeSet); + // System.out.println("2CREATE A NEW TUPLE=" + baseNodeSet + " from=" + // + mdCallee.getThis()); + tupleSet.addTupleSet(baseNodeSet); } } } @@ -4409,7 +5814,6 @@ public class LocationInference { } } - // analyze parameter flows if (min.numArgs() > 0) { @@ -4425,43 +5829,205 @@ public class LocationInference { ExpressionNode en = min.getArg(i); int idx = i + offset; NodeTupleSet argTupleSet = new NodeTupleSet(); - analyzeFlowExpressionNode(md, nametable, en, argTupleSet, false); + analyzeFlowExpressionNode(mdCaller, nametable, en, argTupleSet, false); // if argument is liternal node, argTuple is set to NULL - - NTuple argTuple = new NTuple(); - System.out.println("-argTupleSet=" + argTupleSet + " from en=" + en.printNode(0)); - if (argTupleSet.size() > 1) { - NTuple interTuple = - getFlowGraph(md).createIntermediateNode().getDescTuple(); - for (Iterator> idxIter = argTupleSet.iterator(); idxIter.hasNext();) { - NTuple tuple = idxIter.next(); - addFlowGraphEdge(md, tuple, interTuple); - } - argTuple = interTuple; - } else if (argTupleSet.size() == 1) { - argTuple = argTupleSet.iterator().next(); - } else { + // System.out.println("---arg idx=" + idx + " argTupleSet=" + argTupleSet); + NTuple argTuple = generateArgTuple(mdCaller, argTupleSet); + + // if an argument is literal value, + // we need to create an itermediate node so that we could assign a composite location to + // that node if needed + if (argTuple.size() > 0 + && (argTuple.get(0).equals(GLOBALDESC) || argTuple.get(0).equals(LITERALDESC))) { + /* + * System.out.println("***GLOBAL ARG TUPLE CASE=" + argTuple); System.out.println("8"); + * + * NTuple interTuple = + * getFlowGraph(mdCaller).createIntermediateNode().getDescTuple(); ((InterDescriptor) + * interTuple.get(0)).setMethodArgIdxPair(min, idx); addFlowGraphEdge(mdCaller, + * argTuple, interTuple); argTuple = interTuple; addArgIdxMap(min, idx, argTuple); + * System.out.println("new min mapping i=" + idx + " ->" + argTuple); + */ argTuple = new NTuple(); } addArgIdxMap(min, idx, argTuple); FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx); - System.out.println("-paramNode=" + paramNode + " hasInFlowTo=" - + hasInFlowTo(calleeFlowGraph, paramNode, calleeReturnSet)); + // check whether a param node in the callee graph has incoming flows + // if it has incoming flows, the corresponding arg should be lower than the current PC + // Descriptor prefix = paramNode.getDescTuple().get(0); + // if (calleeFlowGraph.getIncomingNodeSetByPrefix(prefix).size() > 0) { + // for (Iterator> iterator = implicitFlowTupleSet.iterator(); iterator + // .hasNext();) { + // NTuple pcTuple = iterator.next(); + // System.out.println("add edge pcTuple =" + pcTuple + " -> " + argTuple); + // addFlowGraphEdge(md, pcTuple, argTuple); + // } + // } + + // System.out.println("paramNode=" + paramNode + " calleeReturnSet=" + calleeReturnSet); if (hasInFlowTo(calleeFlowGraph, paramNode, calleeReturnSet) - || calleeMethodDesc.getModifiers().isNative()) { - addParamNodeFlowingToReturnValue(calleeMethodDesc, paramNode); - nodeSet.addTupleSet(argTupleSet); + || mdCallee.getModifiers().isNative()) { + addParamNodeFlowingToReturnValue(mdCallee, paramNode); + // nodeSet.addTupleSet(argTupleSet); + // System.out.println("3CREATE A NEW TUPLE=" + argTupleSet + " from=" + paramNode); + tupleSet.addTupleSet(argTupleSet); + } + } + + } + + if (mdCallee.getReturnType() != null && !mdCallee.getReturnType().isVoid()) { + FlowReturnNode returnHolderNode = getFlowGraph(mdCaller).createReturnNode(min); + + if (needToGenerateInterLoc(tupleSet)) { + FlowGraph fg = getFlowGraph(mdCaller); + FlowNode interNode = fg.createIntermediateNode(); + interNode.setFormHolder(true); + + NTuple interTuple = interNode.getDescTuple(); + + for (Iterator iterator = tupleSet.iterator(); iterator.hasNext();) { + NTuple tuple = (NTuple) iterator.next(); + + Set> addSet = new HashSet>(); + FlowNode node = fg.getFlowNode(tuple); + if (node instanceof FlowReturnNode) { + addSet.addAll(fg.getReturnTupleSet(((FlowReturnNode) node).getReturnTupleSet())); + } else { + addSet.add(tuple); + } + for (Iterator iterator2 = addSet.iterator(); iterator2.hasNext();) { + NTuple higher = (NTuple) iterator2.next(); + addFlowGraphEdge(mdCaller, higher, interTuple); + } } + + returnHolderNode.addTuple(interTuple); + + nodeSet.addTuple(interTuple); + // System.out.println("ADD TUPLESET=" + interTuple + " to returnnode=" + + // returnHolderNode); + + } else { + returnHolderNode.addTupleSet(tupleSet); + // System.out.println("ADD TUPLESET=" + tupleSet + " to returnnode=" + returnHolderNode); } + // setNode.addTupleSet(tupleSet); + // NodeTupleSet setFromReturnNode=new NodeTupleSet(); + // setFromReturnNode.addTuple(tuple); + NodeTupleSet holderTupleSet = + getNodeTupleSetFromReturnNode(getFlowGraph(mdCaller), returnHolderNode); + + // System.out.println("HOLDER TUPLE SET=" + holderTupleSet); + nodeSet.addTupleSet(holderTupleSet); + + nodeSet.addTuple(returnHolderNode.getDescTuple()); } // propagateFlowsFromCallee(min, md, min.getMethod()); - System.out.println("min nodeSet=" + nodeSet); + // when generating the global flow graph, + // we need to add ordering relations from the set of callee return loc tuple to LHS of the + // caller assignment + for (Iterator iterator = calleeReturnSet.iterator(); iterator.hasNext();) { + FlowNode calleeReturnNode = (FlowNode) iterator.next(); + NTuple calleeReturnLocTuple = + translateToLocTuple(mdCallee, calleeReturnNode.getDescTuple()); + // System.out.println("calleeReturnLocTuple=" + calleeReturnLocTuple); + NTuple transaltedToCaller = + translateToCallerLocTuple(min, mdCallee, mdCaller, calleeReturnLocTuple); + // System.out.println("translateToCallerLocTuple=" + // + translateToCallerLocTuple(min, mdCallee, mdCaller, calleeReturnLocTuple)); + if (transaltedToCaller.size() > 0) { + nodeSet.addGlobalFlowTuple(translateToCallerLocTuple(min, mdCallee, mdCaller, + calleeReturnLocTuple)); + } + } + + // System.out.println("min nodeSet=" + nodeSet); + + } + + } + + private NodeTupleSet getNodeTupleSetFromReturnNode(FlowGraph fg, FlowReturnNode node) { + NodeTupleSet nts = new NodeTupleSet(); + + Set> returnSet = node.getReturnTupleSet(); + + for (Iterator iterator = returnSet.iterator(); iterator.hasNext();) { + NTuple tuple = (NTuple) iterator.next(); + FlowNode flowNode = fg.getFlowNode(tuple); + if (flowNode instanceof FlowReturnNode) { + returnSet.addAll(recurGetNode(fg, (FlowReturnNode) flowNode)); + } else { + returnSet.add(tuple); + } + } + + for (Iterator iterator = returnSet.iterator(); iterator.hasNext();) { + NTuple nTuple = (NTuple) iterator.next(); + nts.addTuple(nTuple); + } + + return nts; + + } + + private Set> recurGetNode(FlowGraph fg, FlowReturnNode rnode) { + + Set> tupleSet = new HashSet>(); + + Set> returnSet = rnode.getReturnTupleSet(); + for (Iterator iterator = returnSet.iterator(); iterator.hasNext();) { + NTuple tuple = (NTuple) iterator.next(); + FlowNode flowNode = fg.getFlowNode(tuple); + if (flowNode instanceof FlowReturnNode) { + tupleSet.addAll(recurGetNode(fg, (FlowReturnNode) flowNode)); + } + tupleSet.add(tuple); + } + + return tupleSet; + } + + private NTuple generateArgTuple(MethodDescriptor mdCaller, NodeTupleSet argTupleSet) { + + int size = 0; + + // if argTupleSet is empty, it comes from the top location + if (argTupleSet.size() == 0) { + NTuple descTuple = new NTuple(); + descTuple.add(LITERALDESC); + return descTuple; + } + + Set> argTupleSetNonLiteral = new HashSet>(); + + for (Iterator> iter = argTupleSet.iterator(); iter.hasNext();) { + NTuple descTuple = iter.next(); + if (!descTuple.get(0).equals(LITERALDESC)) { + argTupleSetNonLiteral.add(descTuple); + } + } + + if (argTupleSetNonLiteral.size() > 1) { + + NTuple interTuple = + getFlowGraph(mdCaller).createIntermediateNode().getDescTuple(); + for (Iterator> idxIter = argTupleSet.iterator(); idxIter.hasNext();) { + NTuple tuple = idxIter.next(); + addFlowGraphEdge(mdCaller, tuple, interTuple); + } + return interTuple; + } else if (argTupleSetNonLiteral.size() == 1) { + return argTupleSetNonLiteral.iterator().next(); + } else { + return argTupleSet.iterator().next(); } } @@ -4469,9 +6035,13 @@ public class LocationInference { private boolean hasInFlowTo(FlowGraph fg, FlowNode inNode, Set nodeSet) { // return true if inNode has in-flows to nodeSet + if (nodeSet.contains(inNode)) { + // in this case, the method directly returns a parameter variable. + return true; + } // Set reachableSet = fg.getReachFlowNodeSetFrom(inNode); Set reachableSet = fg.getReachableSetFrom(inNode.getDescTuple()); - System.out.println("inNode=" + inNode + " reachalbeSet=" + reachableSet); + // System.out.println("inNode=" + inNode + " reachalbeSet=" + reachableSet); for (Iterator iterator = reachableSet.iterator(); iterator.hasNext();) { FlowNode fn = (FlowNode) iterator.next(); @@ -4498,20 +6068,31 @@ public class LocationInference { mapIdxToTuple.put(new Integer(idx), argTuple); } - private void analyzeLiteralNode(MethodDescriptor md, SymbolTable nametable, LiteralNode en) { - + private void analyzeFlowLiteralNode(MethodDescriptor md, SymbolTable nametable, LiteralNode en, + NodeTupleSet nodeSet) { + NTuple tuple = new NTuple(); + tuple.add(LITERALDESC); + nodeSet.addTuple(tuple); } private void analyzeFlowArrayAccessNode(MethodDescriptor md, SymbolTable nametable, ArrayAccessNode aan, NodeTupleSet nodeSet, boolean isLHS) { + // System.out.println("analyzeFlowArrayAccessNode aan=" + aan.printNode(0)); + String currentArrayAccessNodeExpStr = aan.printNode(0); + arrayAccessNodeStack.push(aan.printNode(0)); + NodeTupleSet expNodeTupleSet = new NodeTupleSet(); NTuple base = analyzeFlowExpressionNode(md, nametable, aan.getExpression(), expNodeTupleSet, isLHS); + // System.out.println("-base=" + base); + nodeSet.setMethodInvokeBaseDescTuple(base); NodeTupleSet idxNodeTupleSet = new NodeTupleSet(); analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, isLHS); + arrayAccessNodeStack.pop(); + if (isLHS) { // need to create an edge from idx to array for (Iterator> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) { @@ -4522,16 +6103,69 @@ public class LocationInference { } } + GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md); + for (Iterator> iterator = idxNodeTupleSet.globalIterator(); iterator + .hasNext();) { + NTuple calleeReturnLocTuple = iterator.next(); + for (Iterator> arrIter = expNodeTupleSet.iterator(); arrIter.hasNext();) { + NTuple arrTuple = arrIter.next(); + + globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, translateToLocTuple(md, arrTuple)); + } + } + nodeSet.addTupleSet(expNodeTupleSet); } else { - nodeSet.addTupleSet(expNodeTupleSet); - nodeSet.addTupleSet(idxNodeTupleSet); + + NodeTupleSet nodeSetArrayAccessExp = new NodeTupleSet(); + + nodeSetArrayAccessExp.addTupleSet(expNodeTupleSet); + nodeSetArrayAccessExp.addTupleSet(idxNodeTupleSet); + + if (arrayAccessNodeStack.isEmpty() + || !arrayAccessNodeStack.peek().startsWith(currentArrayAccessNodeExpStr)) { + + if (needToGenerateInterLoc(nodeSetArrayAccessExp)) { + FlowNode interNode = getFlowGraph(md).createIntermediateNode(); + NTuple interTuple = interNode.getDescTuple(); + + for (Iterator> iter = nodeSetArrayAccessExp.iterator(); iter.hasNext();) { + NTuple higherTuple = iter.next(); + addFlowGraphEdge(md, higherTuple, interTuple); + } + nodeSetArrayAccessExp.clear(); + nodeSetArrayAccessExp.addTuple(interTuple); + FlowGraph fg = getFlowGraph(md); + + // System.out.println("base=" + base); + if (base != null) { + fg.addMapInterLocNodeToEnclosingDescriptor(interTuple.get(0), + getClassTypeDescriptor(base.get(base.size() - 1))); + interNode.setBaseTuple(base); + } + } + } + + nodeSet.addGlobalFlowTupleSet(idxNodeTupleSet.getGlobalLocTupleSet()); + nodeSet.addTupleSet(nodeSetArrayAccessExp); + } + } private void analyzeCreateObjectNode(MethodDescriptor md, SymbolTable nametable, - CreateObjectNode en) { - // TODO Auto-generated method stub + CreateObjectNode en, NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) { + // System.out.println("#analyzeCreateObjectNode=" + en.printNode(0)); + int numArgs = en.numArgs(); + NodeTupleSet argSet = new NodeTupleSet(); + + for (int i = 0; i < numArgs; i++) { + analyzeFlowExpressionNode(md, nametable, en.getArg(i), argSet, null, implicitFlowTupleSet, + false); + } + + // System.out.println("###argSet=" + argSet); + nodeSet.addTupleSet(argSet); } @@ -4541,6 +6175,8 @@ public class LocationInference { NodeTupleSet leftOpSet = new NodeTupleSet(); NodeTupleSet rightOpSet = new NodeTupleSet(); + // System.out.println("analyzeFlowOpNode=" + on.printNode(0)); + // left operand analyzeFlowExpressionNode(md, nametable, on.getLeft(), leftOpSet, null, implicitFlowTupleSet, false); @@ -4587,6 +6223,10 @@ public class LocationInference { // there are two operands nodeSet.addTupleSet(leftOpSet); nodeSet.addTupleSet(rightOpSet); + + nodeSet.addGlobalFlowTupleSet(leftOpSet.getGlobalLocTupleSet()); + nodeSet.addGlobalFlowTupleSet(rightOpSet.getGlobalLocTupleSet()); + break; default: @@ -4598,8 +6238,6 @@ public class LocationInference { private NTuple analyzeFlowNameNode(MethodDescriptor md, SymbolTable nametable, NameNode nn, NodeTupleSet nodeSet, NTuple base, NodeTupleSet implicitFlowTupleSet) { - // System.out.println("analyzeFlowNameNode=" + nn.printNode(0)); - if (base == null) { base = new NTuple(); } @@ -4680,10 +6318,13 @@ public class LocationInference { private NTuple analyzeFlowFieldAccessNode(MethodDescriptor md, SymbolTable nametable, FieldAccessNode fan, NodeTupleSet nodeSet, NTuple base, NodeTupleSet implicitFlowTupleSet, boolean isLHS) { + // System.out.println("analyzeFlowFieldAccessNode=" + fan.printNode(0)); + String currentArrayAccessNodeExpStr = null; ExpressionNode left = fan.getExpression(); TypeDescriptor ltd = left.getType(); FieldDescriptor fd = fan.getField(); + ArrayAccessNode aan = null; String varName = null; if (left.kind() == Kind.NameNode) { @@ -4700,14 +6341,19 @@ public class LocationInference { NodeTupleSet idxNodeTupleSet = new NodeTupleSet(); + boolean isArrayCase = false; if (left instanceof ArrayAccessNode) { - ArrayAccessNode aan = (ArrayAccessNode) left; + isArrayCase = true; + aan = (ArrayAccessNode) left; + + currentArrayAccessNodeExpStr = aan.printNode(0); + arrayAccessNodeStack.push(currentArrayAccessNodeExpStr); + left = aan.getExpression(); analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, base, implicitFlowTupleSet, isLHS); - nodeSet.addTupleSet(idxNodeTupleSet); } base = analyzeFlowExpressionNode(md, nametable, left, nodeSet, base, implicitFlowTupleSet, isLHS); @@ -4720,13 +6366,11 @@ public class LocationInference { NTuple flowFieldTuple = new NTuple(base.toList()); if (!left.getType().isPrimitive()) { - if (!fd.getSymbol().equals("length")) { // array.length access, just have the location of the array flowFieldTuple.add(fd); nodeSet.removeTuple(base); } - } getFlowGraph(md).createNewFlowNode(flowFieldTuple); @@ -4735,9 +6379,59 @@ public class LocationInference { NTuple idxTuple = idxIter.next(); getFlowGraph(md).addValueFlowEdge(idxTuple, flowFieldTuple); } + + GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md); + for (Iterator> iterator = idxNodeTupleSet.globalIterator(); iterator + .hasNext();) { + NTuple calleeReturnLocTuple = iterator.next(); + + globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, + translateToLocTuple(md, flowFieldTuple)); + } + + } else { + nodeSet.addTupleSet(idxNodeTupleSet); + + // if it is the array case and not the LHS case + if (isArrayCase) { + arrayAccessNodeStack.pop(); + + if (arrayAccessNodeStack.isEmpty() + || !arrayAccessNodeStack.peek().startsWith(currentArrayAccessNodeExpStr)) { + NodeTupleSet nodeSetArrayAccessExp = new NodeTupleSet(); + + nodeSetArrayAccessExp.addTuple(flowFieldTuple); + nodeSetArrayAccessExp.addTupleSet(idxNodeTupleSet); + nodeSetArrayAccessExp.addTupleSet(nodeSet); + + if (needToGenerateInterLoc(nodeSetArrayAccessExp)) { + // System.out.println("nodeSetArrayAccessExp=" + nodeSetArrayAccessExp); + // System.out.println("idxNodeTupleSet.getGlobalLocTupleSet()=" + // + idxNodeTupleSet.getGlobalLocTupleSet()); + + NTuple interTuple = + getFlowGraph(md).createIntermediateNode().getDescTuple(); + + for (Iterator> iter = nodeSetArrayAccessExp.iterator(); iter + .hasNext();) { + NTuple higherTuple = iter.next(); + addFlowGraphEdge(md, higherTuple, interTuple); + } + + FlowGraph fg = getFlowGraph(md); + fg.addMapInterLocNodeToEnclosingDescriptor(interTuple.get(0), + getClassTypeDescriptor(base.get(base.size() - 1))); + + nodeSet.clear(); + flowFieldTuple = interTuple; + } + nodeSet.addGlobalFlowTupleSet(idxNodeTupleSet.getGlobalLocTupleSet()); + } + + } + } return flowFieldTuple; - } } @@ -4791,7 +6485,7 @@ public class LocationInference { // creates edges from RHS to LHS NTuple interTuple = null; - if (nodeSetRHS.size() > 1) { + if (needToGenerateInterLoc(nodeSetRHS)) { interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); } @@ -4812,6 +6506,33 @@ public class LocationInference { } } + // create global flow edges if the callee gives return value flows to the caller + GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md); + for (Iterator> iterator = nodeSetRHS.globalIterator(); iterator.hasNext();) { + NTuple calleeReturnLocTuple = iterator.next(); + for (Iterator> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) { + NTuple callerLHSTuple = iter2.next(); + // System.out.println("$$$ GLOBAL FLOW ADD=" + calleeReturnLocTuple + " -> " + // + translateToLocTuple(md, callerLHSTuple)); + + globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, + translateToLocTuple(md, callerLHSTuple)); + } + } + + for (Iterator> iterator = implicitFlowTupleSet.globalIterator(); iterator + .hasNext();) { + NTuple calleeReturnLocTuple = iterator.next(); + for (Iterator> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) { + NTuple callerLHSTuple = iter2.next(); + + globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, + translateToLocTuple(md, callerLHSTuple)); + // System.out.println("$$$ GLOBAL FLOW PCLOC ADD=" + calleeReturnLocTuple + " -> " + // + translateToLocTuple(md, callerLHSTuple)); + } + } + } else { // postinc case @@ -4829,10 +6550,24 @@ public class LocationInference { } } + GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md); + for (Iterator> iterator = implicitFlowTupleSet.globalIterator(); iterator + .hasNext();) { + NTuple calleeReturnLocTuple = iterator.next(); + for (Iterator> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) { + NTuple callerLHSTuple = iter2.next(); + globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, + translateToLocTuple(md, callerLHSTuple)); + // System.out.println("$$$ GLOBAL FLOW PC ADD=" + calleeReturnLocTuple + " -> " + // + translateToLocTuple(md, callerLHSTuple)); + } + } + } if (nodeSet != null) { nodeSet.addTupleSet(nodeSetLHS); + nodeSet.addGlobalFlowTupleSet(nodeSetLHS.getGlobalLocTupleSet()); } } @@ -4861,13 +6596,15 @@ public class LocationInference { } - public void writeInferredLatticeDotFile(ClassDescriptor cd, HierarchyGraph simpleHierarchyGraph, - SSJavaLattice locOrder, String nameSuffix) { - writeInferredLatticeDotFile(cd, null, simpleHierarchyGraph, locOrder, nameSuffix); + public void writeInferredLatticeDotFile(ClassDescriptor cd, SSJavaLattice locOrder, + String nameSuffix) { + // System.out.println("@cd=" + cd); + // System.out.println("@sharedLoc=" + locOrder.getSharedLocSet()); + writeInferredLatticeDotFile(cd, null, locOrder, nameSuffix); } public void writeInferredLatticeDotFile(ClassDescriptor cd, MethodDescriptor md, - HierarchyGraph simpleHierarchyGraph, SSJavaLattice locOrder, String nameSuffix) { + SSJavaLattice locOrder, String nameSuffix) { String fileName = "lattice_"; if (md != null) { @@ -4879,6 +6616,8 @@ public class LocationInference { fileName += nameSuffix; + System.out.println("***lattice=" + fileName + " setsize=" + locOrder.getKeySet().size()); + Set> pairSet = locOrder.getOrderingPairSet(); Set addedLocSet = new HashSet(); @@ -4895,15 +6634,14 @@ public class LocationInference { String highLocId = pair.getFirst(); String lowLocId = pair.getSecond(); - if (!addedLocSet.contains(highLocId)) { addedLocSet.add(highLocId); - drawNode(bw, locOrder, simpleHierarchyGraph, highLocId); + drawNode(bw, locOrder, highLocId); } if (!addedLocSet.contains(lowLocId)) { addedLocSet.add(lowLocId); - drawNode(bw, locOrder, simpleHierarchyGraph, lowLocId); + drawNode(bw, locOrder, lowLocId); } bw.write(highLocId + " -> " + lowLocId + ";\n"); @@ -4932,14 +6670,12 @@ public class LocationInference { return str; } - private void drawNode(BufferedWriter bw, SSJavaLattice lattice, HierarchyGraph graph, - String locName) throws IOException { - - HNode node = graph.getHNode(locName); + public void addNaiveLattice(Descriptor desc, SSJavaLattice lattice) { + desc2naiveLattice.put(desc, lattice); + } - if (node == null) { - return; - } + private void drawNode(BufferedWriter bw, SSJavaLattice lattice, String locName) + throws IOException { String prettyStr; if (lattice.isSharedLoc(locName)) { @@ -4947,22 +6683,24 @@ public class LocationInference { } else { prettyStr = locName; } - - if (node.isMergeNode()) { - Set mergeSet = graph.getMapHNodetoMergeSet().get(node); - prettyStr += ":" + convertMergeSetToString(graph, mergeSet); - } + // HNode node = graph.getHNode(locName); + // if (node != null && node.isMergeNode()) { + // Set mergeSet = graph.getMapHNodetoMergeSet().get(node); + // prettyStr += ":" + convertMergeSetToString(graph, mergeSet); + // } bw.write(locName + " [label=\"" + prettyStr + "\"]" + ";\n"); } - public void _debug_printGraph() { + public void _debug_writeFlowGraph() { Set keySet = mapMethodDescriptorToFlowGraph.keySet(); for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { MethodDescriptor md = (MethodDescriptor) iterator.next(); FlowGraph fg = mapMethodDescriptorToFlowGraph.get(md); + GlobalFlowGraph subGlobalFlowGraph = getSubGlobalFlowGraph(md); try { fg.writeGraph(); + subGlobalFlowGraph.writeGraph("_SUBGLOBAL"); } catch (IOException e) { e.printStackTrace(); } @@ -4978,8 +6716,18 @@ class CyclicFlowException extends Exception { class InterDescriptor extends Descriptor { + Pair minArgIdxPair; + public InterDescriptor(String name) { super(name); } + public void setMethodArgIdxPair(MethodInvokeNode min, int idx) { + minArgIdxPair = new Pair(min, new Integer(idx)); + } + + public Pair getMethodArgIdxPair() { + return minArgIdxPair; + } + }