X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=Robust%2Fsrc%2FAnalysis%2FSSJava%2FLocationInference.java;h=18f1d3ed5b8580cb78a9122664b716f3a5a71352;hb=ddac34bb8ed87db61d32630e714e7f006a077c8e;hp=916016054b8cfe069e7f276b4db5ec069457c8f2;hpb=e993e72e1d2bfe7921c32573245ad85781dffba3;p=IRC.git diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index 91601605..18f1d3ed 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; @@ -114,12 +121,28 @@ 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; + private Map mapMethodDescriptorToCompositeReturnCase; + + private Map mapMethodDescToHighestOverriddenMethodDesc; + + private Map> mapHighestOverriddenMethodDescToMethodDescSet; + + private Map>> mapHighestOverriddenMethodDescToSetHigherThanRLoc; + + private Map> mapHighestOverriddenMethodDescToReturnLocTuple; + + private Map> mapHighestOverriddenMethodDescToPCLocTuple; + + private Map>> mapHighestOverriddenMethodDescToSetLowerThanPCLoc; + public static final String GLOBALLOC = "GLOBALLOC"; public static final String INTERLOC = "INTERLOC"; @@ -154,9 +177,15 @@ public class LocationInference { private Stack arrayAccessNodeStack; - public LocationInference(SSJavaAnalysis ssjava, State state) { + private ClassDescriptor rootClassDescriptor; + + private BuildLattice buildLattice; + + 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(); @@ -197,6 +226,30 @@ public class LocationInference { this.arrayAccessNodeStack = new Stack(); + this.mapMethodDescToMethodInvokeNodeSet = + new HashMap>(); + + this.mapMethodDescriptorToCompositeReturnCase = new HashMap(); + + mapMethodDescToHighestOverriddenMethodDesc = new HashMap(); + + mapHighestOverriddenMethodDescToSetHigherThanRLoc = + new HashMap>>(); + + mapHighestOverriddenMethodDescToSetLowerThanPCLoc = + new HashMap>>(); + + mapHighestOverriddenMethodDescToMethodDescSet = + new HashMap>(); + + mapHighestOverriddenMethodDescToReturnLocTuple = + new HashMap>(); + + mapHighestOverriddenMethodDescToPCLocTuple = + new HashMap>(); + + this.buildLattice = new BuildLattice(this); + } public void setupToAnalyze() { @@ -247,6 +300,8 @@ public class LocationInference { constructGlobalFlowGraph(); + checkReturnNodes(); + assignCompositeLocation(); updateFlowGraph(); calculateExtraLocations(); @@ -254,10 +309,13 @@ public class LocationInference { _debug_writeFlowGraph(); - // System.exit(0); + buildInheritanceTree(); + calculateReturnPCLocInheritance(); constructHierarchyGraph(); + addInheritanceConstraintsToHierarchyGraph(); + debug_writeHierarchyDotFiles(); simplifyHierarchyGraph(); @@ -272,7 +330,8 @@ public class LocationInference { debug_writeSkeletonCombinationHierarchyDotFiles(); - buildLattice(); + buildLatticeInheritanceTree(); + // buildLattice(); debug_writeLattices(); @@ -282,10 +341,498 @@ 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()); + } + 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 highestPCLoc = + mapHighestOverriddenMethodDescToPCLocTuple.get(highestMethodDesc); + + NTuple highestRETURNLoc = + mapHighestOverriddenMethodDescToReturnLocTuple.get(highestMethodDesc); + + System.out.println("---highestMethodDesc=" + highestMethodDesc); + + for (Iterator iterator2 = methodDescSet.iterator(); iterator2.hasNext();) { + MethodDescriptor md = (MethodDescriptor) iterator2.next(); + FlowGraph flowGraph = getFlowGraph(md); + + MethodSummary summary = getMethodSummary(md); + CompositeLocation curPCLoc = summary.getPCLoc(); + + // update PCLOC + if (highestPCLoc != null) { + // handle the case that PCLOC is started with 'this'... + NTuple newPCLoc = new NTuple(); + if (highestPCLoc.size() == 1) { + newPCLoc.add(highestPCLoc.get(0)); + } else { + newPCLoc.add(md.getThis()); + newPCLoc.add(highestPCLoc.get(1)); + } + + FlowNode pcFlowNode = flowGraph.getFlowNode(translateToDescTuple(curPCLoc.getTuple())); + pcFlowNode.setBaseTuple(newPCLoc); + + CompositeLocation newPCLocCompLoc = + new CompositeLocation(translateToLocTuple(md, newPCLoc)); + summary.setPCLoc(newPCLocCompLoc); + } else { + // need to remove PCLOC if the overridden method defines it + if (curPCLoc != null && !curPCLoc.get(0).isTop()) { + System.out.println("md=" + md + " curPCLoc=" + curPCLoc); + FlowNode pcFlowNode = flowGraph.getFlowNode(translateToDescTuple(curPCLoc.getTuple())); + System.out.println("#######REMOVE PCLOCNODE=" + pcFlowNode); + flowGraph.removeNode(pcFlowNode); + } + } + + // need to update RETURNLOC + if (highestRETURNLoc != null) { + + CompositeLocation curRETURNLoc = summary.getRETURNLoc(); + System.out.println("curRETURNLoc=" + curRETURNLoc); + + // handle the case that RETURNLOC is started with 'this'... + NTuple newRETURNLoc = new NTuple(); + if (highestRETURNLoc.size() == 1) { + newRETURNLoc.add(highestRETURNLoc.get(0)); + } else { + newRETURNLoc.add(md.getThis()); + newRETURNLoc.add(highestRETURNLoc.get(1)); + } + + FlowNode returnFlowNode = + flowGraph.getFlowNode(translateToDescTuple(curRETURNLoc.getTuple())); + returnFlowNode.setBaseTuple(newRETURNLoc); + + CompositeLocation newRETURNLocCompLoc = + new CompositeLocation(translateToLocTuple(md, newRETURNLoc)); + summary.setPCLoc(newRETURNLocCompLoc); + System.out.println("md=" + md + "###newRETURNLocCompLoc=" + newRETURNLocCompLoc); + + } + + } + } + } + + private void calculateHighestPCLocInheritance() { + + Set keySet = mapHighestOverriddenMethodDescToMethodDescSet.keySet(); + 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); + + 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(); + + if (!pcLOC.get(0).isTop()) { + if (pcLOC.getSize() == 1) { + // return location is not started with 'this' + // check whether the return location is lower than all parameters. + + 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++; + System.out.println("-------" + pcFlowNode + " -> " + paramNode); + } + } + + int offset = 0; + if (!md.isStatic()) { + offset = 1; + } + + NTuple rTuple = new NTuple(); + rTuple.add(pcLOC.get(0).getLocDescriptor()); + if (count == (md.numParameters() + offset)) { + // means return loc is lower than a composite location starting with 'this' + mapHighestOverriddenMethodDescToPCLocTuple.put(highestMethodDesc, rTuple); + } else { + if (tempTuple == null) { + tempTuple = rTuple; + } + } + } else { + // if the current overridden method has a composite pc loc(size>1) + // and it has not yet finalized the pc location, + // the highest overridden method would have the composite pc location starting with + // 'this' + NTuple rTuple = new NTuple(); + for (int i = 0; i < pcLOC.getSize(); i++) { + rTuple.add(pcLOC.get(i).getLocDescriptor()); + } + tempTuple = rTuple; + } + } else { + mapHighestOverriddenMethodDescToPCLocTuple.remove(highestMethodDesc); + System.out.println("highest=" + highestMethodDesc + " HIGHEST PCLOC=" + + mapHighestOverriddenMethodDescToPCLocTuple.get(highestMethodDesc)); + continue next; + } + } + + } + + if (!mapHighestOverriddenMethodDescToPCLocTuple.containsKey(highestMethodDesc) + && tempTuple != null) { + mapHighestOverriddenMethodDescToPCLocTuple.put(highestMethodDesc, tempTuple); + } + System.out.println("highest=" + highestMethodDesc + " HIGHEST PCLOC=" + + mapHighestOverriddenMethodDescToPCLocTuple.get(highestMethodDesc)); + } + + } + + private void calculateLowestReturnLocInheritance() { + + Set keySet = mapHighestOverriddenMethodDescToMethodDescSet.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + MethodDescriptor highestMethodDesc = (MethodDescriptor) iterator.next(); + + NTuple tempTuple = null; + + if (getMethodSummary(highestMethodDesc).getRETURNLoc() != null) { + Set methodDescSet = + mapHighestOverriddenMethodDescToMethodDescSet.get(highestMethodDesc); + for (Iterator iterator2 = methodDescSet.iterator(); iterator2.hasNext();) { + MethodDescriptor md = (MethodDescriptor) iterator2.next(); + + FlowGraph flowGraph = getFlowGraph(md); + Set paramNodeSet = flowGraph.getParamFlowNodeSet(); + System.out.println("###md=" + md + " paramNodeSet=" + paramNodeSet); + + CompositeLocation returnLoc = getMethodSummary(md).getRETURNLoc(); + if (returnLoc.getSize() == 1) { + // return location is not started with 'this' + // check whether the return location is lower than all parameters. + + 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++; + System.out.println("-------" + paramNode + " -> " + returnFlowNode); + } + } + + int offset = 0; + if (!md.isStatic()) { + offset = 1; + } + + NTuple rTuple = new NTuple(); + rTuple.add(returnLoc.get(0).getLocDescriptor()); + if (count == (md.numParameters() + offset)) { + // means return loc is lower than a composite location starting with 'this' + mapHighestOverriddenMethodDescToReturnLocTuple.put(highestMethodDesc, rTuple); + } else { + if (tempTuple == null) { + tempTuple = rTuple; + } + } + } else { + // if the current overridden method has a composite return loc(size>1) + // and it has not yet finalized the return location + // the highest overridden method has the composite return location starting with + // 'this' + NTuple rTuple = new NTuple(); + for (int i = 0; i < returnLoc.getSize(); i++) { + rTuple.add(returnLoc.get(i).getLocDescriptor()); + } + tempTuple = rTuple; + } + + } + + } + + if (!mapHighestOverriddenMethodDescToReturnLocTuple.containsKey(highestMethodDesc) + && tempTuple != null) { + mapHighestOverriddenMethodDescToReturnLocTuple.put(highestMethodDesc, tempTuple); + } + System.out.println("highest=" + highestMethodDesc + " rTuple=" + + mapHighestOverriddenMethodDescToReturnLocTuple.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 void addTupleLowerThanPCLoc(NTuple tuple) { + + } + + 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); + + // 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... + Set parentNodeSet = parentGraph.getNodeSet(); + 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); + + // 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 updateFlowGraph() { LinkedList methodDescList = @@ -298,6 +845,23 @@ public class LocationInference { 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) { + toanalyze_classDescSet.add((ClassDescriptor) loc.getDescriptor()); + } else if (loc.getDescriptor() instanceof MethodDescriptor) { + toanalyze_classDescSet.add(((MethodDescriptor) loc.getDescriptor()).getClassDesc()); + } + } + + } + } } @@ -328,10 +892,36 @@ public class LocationInference { translateCompositeLocationAssignmentToFlowGraph(methodEventLoopDesc); } + 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() { @@ -342,7 +932,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); @@ -394,9 +984,12 @@ public class LocationInference { String locName; if (!enclosingDesc.equals(GLOBALDESC)) { LocationSummary locSummary = getLocationSummary(enclosingDesc); - HierarchyGraph scGraph = getSkeletonCombinationHierarchyGraph(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(); } @@ -414,8 +1007,8 @@ public class LocationInference { private void translateCompositeLocationAssignmentToFlowGraph(MethodDescriptor mdCaller) { - System.out.println("\n\n###translateCompositeLocationAssignmentToFlowGraph mdCaller=" - + 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); @@ -444,106 +1037,13 @@ public class LocationInference { MethodDescriptor mdCallee = min.getMethod(); calleeSet.add(mdCallee); - FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); - - NTuple methodInvokeBaseDescTuple = mapMethodInvokeNodeToBaseTuple.get(min); - NTuple methodInvokeBaseLocTuple = null; - if (methodInvokeBaseDescTuple != null) { - methodInvokeBaseLocTuple = translateToLocTuple(mdCaller, methodInvokeBaseDescTuple); - } - - // //////////////// - // //////////////// - - // If the location of an argument has a composite location - // need to assign a proper composite location to the corresponding callee parameter - // System.out.println("---translate arg composite location to callee param. min=" - // + min.printNode(0)); - Map> mapIdxToArgTuple = mapMethodInvokeNodeToArgIdxMap.get(min); - Set idxSet = mapIdxToArgTuple.keySet(); - for (Iterator iterator2 = idxSet.iterator(); iterator2.hasNext();) { - Integer idx = (Integer) iterator2.next(); - - if (idx == 0 && !min.getMethod().isStatic()) { - continue; - } - - 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 (!isPrimitiveType(argTuple)) { - if (callerMapLocToCompLoc.containsKey(argLocalLoc)) { - - CompositeLocation argLocalCompositeLocation = callerMapLocToCompLoc.get(argLocalLoc); - CompositeLocation argCompLoc = argLocalCompositeLocation.clone(); - for (int i = 1; i < argLocTuple.size(); i++) { - argCompLoc.addLocation(argLocTuple.get(i)); - } - - FlowNode calleeParamFlowNode = calleeFlowGraph.getParamFlowNode(idx); - - System.out - .println("----- argLocTuple=" + argLocTuple + " argLocalLoc=+" + argLocalLoc); - System.out.println("-------need to translate argCompLoc=" + argCompLoc - + " with baseTuple=" + methodInvokeBaseLocTuple + " calleeParamLocTuple=" - + calleeParamFlowNode); - - CompositeLocation paramCompLoc = translateArgCompLocToParamCompLoc(min, argCompLoc); - calleeParamFlowNode.setCompositeLocation(paramCompLoc); - - // if (baseLocTuple != null && callerCompLoc.getTuple().startsWith(baseLocTuple)) { - // - // FlowNode calleeParamFlowNode = calleeFlowGraph.getParamFlowNode(idx); - // NTuple calleeParamDescTuple = calleeParamFlowNode.getDescTuple(); - // NTuple calleeParamLocTuple - // =###translateCompositeLocationAssignmentToFlowGraph mdCaller=public static void - // huffcodetab.huffman_decoder(int htIdx, int x, BitReserve br) - - // translateToLocTuple(mdCallee, calleeParamDescTuple); - // - // 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("---callee loc=" + calleeParamLocTuple.get(0) - // + " newCalleeCompLoc=" + newCalleeCompLoc); - // - // // System.out.println("###need to assign composite location to=" + - // // calleeParamDescTuple - // // + " with baseTuple=" + baseLocTuple); - // } - - } - } - } } - // //////////////// - // //////////////// for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) { MethodDescriptor callee = (MethodDescriptor) iterator.next(); translateCompositeLocationAssignmentToFlowGraph(callee); } - for (Iterator iterator = minSet.iterator(); iterator.hasNext();) { - MethodInvokeNode min = (MethodInvokeNode) iterator.next(); - // 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); - } - } private CompositeLocation translateArgCompLocToParamCompLoc(MethodInvokeNode min, @@ -570,7 +1070,7 @@ public class LocationInference { // it matches with the current argument composite location // so what is the corresponding parameter local descriptor? FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx); - System.out.println("----------found paramNode=" + paramNode); + // System.out.println("----------found paramNode=" + paramNode); NTuple paramDescTuple = paramNode.getCurrentDescTuple(); NTuple newParamTupleFromArgTuple = translateToLocTuple(mdCallee, paramDescTuple); @@ -578,7 +1078,7 @@ public class LocationInference { newParamTupleFromArgTuple.add(argLocTuple.get(i)); } - System.out.println("-----------newParamTuple=" + newParamTupleFromArgTuple); + // System.out.println("-----------newParamTuple=" + newParamTupleFromArgTuple); return new CompositeLocation(newParamTupleFromArgTuple); } @@ -615,19 +1115,53 @@ public class LocationInference { // // 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); + } + + } + } } @@ -639,6 +1173,38 @@ public class LocationInference { } + 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); + } + private void addOrderingConstraintFromCompLocParamToArg(MethodDescriptor mdCaller, MethodInvokeNode min) { System.out.println("-addOrderingConstraintFromCompLocParamToArg=" + min.printNode(0)); @@ -682,6 +1248,7 @@ public class LocationInference { + "-> globalParamLocTu!globalArgLocTuple.get(0).getLocDescriptor().equals(LITERALDESC)ple=" + globalParamLocTuple); hasChanges = true; + globalGraph.addValueFlowEdge(pcLocTuple, globalParamLocTuple); } } @@ -718,6 +1285,8 @@ public class LocationInference { 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++) { newCompLoc.addLocation(inferCompLoc.get(i)); @@ -726,7 +1295,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(); } @@ -760,10 +1329,8 @@ public class LocationInference { baseLocTuple = translateToLocTuple(mdCaller, mapMethodInvokeNodeToBaseTuple.get(min)); } - System.out.println("\n-#translate caller=" + mdCaller + " infer composite loc to callee=" - + mdCallee + " baseLocTuple=" + baseLocTuple); - // System.out.println("-mapIdxToArgTuple=" + mapIdxToArgTuple); - // System.out.println("-callerMapLocToCompLoc=" + callerMapLocToCompLoc); + // 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();) { @@ -780,10 +1347,14 @@ public class LocationInference { translateCompositeLocationToCallee(callerCompLoc, baseLocTuple, mdCallee); calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, newCalleeCompLoc); - // System.out.println("---key=" + key + " callerCompLoc=" + callerCompLoc + // System.out.println("1---key=" + key + " callerCompLoc=" + callerCompLoc // + " newCalleeCompLoc=" + newCalleeCompLoc); - // System.out.println("-----baseLoctuple=" + baseLocTuple); // 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); @@ -798,19 +1369,41 @@ public class LocationInference { newCalleeCompLoc.addLocation(callerCompLoc.get(i)); } calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, newCalleeCompLoc); - // System.out.println("---key=" + key + " callerCompLoc=" + callerCompLoc + // 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); - // System.out.println("-----paramIdx=" + paramIdx + " paramFlowNode=" + paramFlowNode); NTuple paramLocTuple = translateToLocTuple(mdCallee, paramFlowNode.getDescTuple()); newCalleeCompLoc = new CompositeLocation(); @@ -821,9 +1414,8 @@ public class LocationInference { newCalleeCompLoc.addLocation(callerCompLoc.get(i)); } calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, newCalleeCompLoc); - // System.out.println("---key=" + key + " callerCompLoc=" + callerCompLoc + // System.out.println("4---key=" + key + " callerCompLoc=" + callerCompLoc // + " newCalleeCompLoc=" + newCalleeCompLoc); - // System.out.println("------argTuple=" + argTuple); // System.out.println("-----caller=" + mdCaller + " callee=" + mdCallee); } @@ -833,9 +1425,8 @@ public class LocationInference { } } - // System.out.println("-----*AFTER TRANSLATING COMP LOC MAPPING, CALLEE MAPPING=" - // + calleeGlobalGraph.getMapLocationToInferCompositeLocation()); - + 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(); @@ -847,6 +1438,7 @@ public class LocationInference { } 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); @@ -860,16 +1452,23 @@ public class LocationInference { callerCompLoc.addLocation(argLocTuple.get(i)); } - if (baseLocTuple != null && callerCompLoc.getTuple().startsWith(baseLocTuple)) { + System.out.println("---callerCompLoc=" + callerCompLoc); - FlowNode calleeParamFlowNode = calleeFlowGraph.getParamFlowNode(idx); - NTuple calleeParamDescTuple = calleeParamFlowNode.getDescTuple(); - NTuple calleeParamLocTuple = - translateToLocTuple(mdCallee, calleeParamDescTuple); + // if (baseLocTuple != null && callerCompLoc.getTuple().startsWith(baseLocTuple)) { - // System.out.println("---need to translate callerCompLoc=" + callerCompLoc - // + " with baseTuple=" + baseLocTuple + " calleeParamLocTuple=" - // + calleeParamLocTuple); + 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); @@ -877,11 +1476,53 @@ public class LocationInference { calleeGlobalGraph.addMapLocationToInferCompositeLocation(calleeParamLocTuple.get(0), newCalleeCompLoc); - // System.out.println("---callee loc=" + calleeParamLocTuple.get(0) - // + " newCalleeCompLoc=" + 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()); + + // } + } } @@ -889,6 +1530,99 @@ public class LocationInference { } + private CompositeLocation calculateCompositeLocationFromSubGlobalGraph(MethodDescriptor md, + FlowNode paramNode) { + + System.out.println("#############################################################"); + System.out.println("calculateCompositeLocationFromSubGlobalGraph=" + paramNode); + + GlobalFlowGraph subGlobalFlowGraph = getSubGlobalFlowGraph(md); + NTuple paramLocTuple = translateToLocTuple(md, paramNode.getDescTuple()); + GlobalFlowNode paramGlobalNode = subGlobalFlowGraph.getFlowNode(paramLocTuple); + + List> prefixList = calculatePrefixList(subGlobalFlowGraph, paramGlobalNode); + + Location prefixLoc = paramLocTuple.get(0); + + Set reachableNodeSet = + subGlobalFlowGraph.getReachableNodeSetByPrefix(paramGlobalNode.getLocTuple().get(0)); + // Set reachNodeSet = globalFlowGraph.getReachableNodeSetFrom(node); + + // System.out.println("node=" + node + " prefixList=" + prefixList); + + for (int i = 0; i < prefixList.size(); i++) { + NTuple curPrefix = prefixList.get(i); + Set> reachableCommonPrefixSet = new HashSet>(); + + for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) { + GlobalFlowNode reachNode = (GlobalFlowNode) iterator2.next(); + if (reachNode.getLocTuple().startsWith(curPrefix)) { + reachableCommonPrefixSet.add(reachNode.getLocTuple()); + } + } + // System.out.println("reachableCommonPrefixSet=" + reachableCommonPrefixSet); + + if (!reachableCommonPrefixSet.isEmpty()) { + + MethodDescriptor curPrefixFirstElementMethodDesc = + (MethodDescriptor) curPrefix.get(0).getDescriptor(); + + MethodDescriptor nodePrefixLocFirstElementMethodDesc = + (MethodDescriptor) prefixLoc.getDescriptor(); + + // System.out.println("curPrefixFirstElementMethodDesc=" + + // curPrefixFirstElementMethodDesc); + // System.out.println("nodePrefixLocFirstElementMethodDesc=" + // + nodePrefixLocFirstElementMethodDesc); + + if (curPrefixFirstElementMethodDesc.equals(nodePrefixLocFirstElementMethodDesc) + || isTransitivelyCalledFrom(nodePrefixLocFirstElementMethodDesc, + curPrefixFirstElementMethodDesc)) { + + // TODO + // if (!node.getLocTuple().startsWith(curPrefix.get(0))) { + + Location curPrefixLocalLoc = curPrefix.get(0); + if (subGlobalFlowGraph.mapLocationToInferCompositeLocation.containsKey(curPrefixLocalLoc)) { + // in this case, the local variable of the current prefix has already got a composite + // location + // so we just ignore the current composite location. + + // System.out.println("HERE WE DO NOT ASSIGN A COMPOSITE LOCATION TO =" + node + // + " DUE TO " + curPrefix); + return null; + } + + if (!needToGenerateCompositeLocation(paramGlobalNode, curPrefix)) { + System.out.println("NO NEED TO GENERATE COMP LOC to " + paramGlobalNode + + " with prefix=" + curPrefix); + return null; + } + + Location targetLocalLoc = paramGlobalNode.getLocTuple().get(0); + CompositeLocation newCompLoc = generateCompositeLocation(curPrefix); + System.out.println("NEED TO ASSIGN COMP LOC TO " + paramGlobalNode + " with prefix=" + + curPrefix); + System.out.println("-targetLocalLoc=" + targetLocalLoc + " - newCompLoc=" + newCompLoc); + + // makes sure that a newly generated location appears in the hierarchy graph + for (int compIdx = 0; compIdx < newCompLoc.getSize(); compIdx++) { + Location curLoc = newCompLoc.get(compIdx); + getHierarchyGraph(curLoc.getDescriptor()).getHNode(curLoc.getLocDescriptor()); + } + + subGlobalFlowGraph.addMapLocationToInferCompositeLocation(targetLocalLoc, newCompLoc); + + return newCompLoc; + + } + + } + + } + return null; + } + private int getParamIdx(CompositeLocation compLoc, Map> mapIdxToArgTuple) { @@ -972,9 +1706,11 @@ public class LocationInference { // Set reachNodeSet = globalFlowGraph.getReachableNodeSetFrom(node); // 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();) { @@ -1017,10 +1753,15 @@ 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("-targetLocalLoc=" + targetLocalLoc + " - newCompLoc=" @@ -1032,15 +1773,212 @@ public class LocationInference { // } } - + + } + + } + + } + } + + 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; + } } - } - } - // Set inNodeSet = - // graph.getIncomingNodeSetWithPrefix(prefix); - // System.out.println("inNodeSet=" + inNodeSet + " from=" + node); + return false; } private void assignCompositeLocation(CompositeLocation compLocPrefix, GlobalFlowNode node) { @@ -1058,11 +1996,11 @@ public class LocationInference { Set incomingNodeSetPrefix = graph.getIncomingNodeSetByPrefix(node.getLocTuple().get(0)); - // System.out.println("incomingNodeSetPrefix=" + incomingNodeSetPrefix); + // System.out.println("---incomingNodeSetPrefix=" + incomingNodeSetPrefix); Set reachableNodeSetPrefix = graph.getReachableNodeSetByPrefix(node.getLocTuple().get(0)); - // System.out.println("reachableNodeSetPrefix=" + reachableNodeSetPrefix); + // System.out.println("---reachableNodeSetPrefix=" + reachableNodeSetPrefix); List> prefixList = new ArrayList>(); @@ -1097,54 +2035,117 @@ public class LocationInference { } }); - // remove a prefix which is not suitable for generating composite location - Location localVarLoc = node.getLocTuple().get(0); - MethodDescriptor md = (MethodDescriptor) localVarLoc.getDescriptor(); - ClassDescriptor cd = md.getClassDesc(); - - int idx = 0; - Set> toberemoved = new HashSet>(); - // for (int i = 0; i < prefixList.size(); i++) { - // NTuple prefixLocTuple = prefixList.get(i); - // if (!containsClassDesc(cd, prefixLocTuple)) { - // toberemoved.add(prefixLocTuple); - // } - // } + return prefixList; + + } - // System.out.println("method class=" + cd + " toberemoved=" + toberemoved); + private CompositeLocation calculateCompositeLocationFromFlowGraph(MethodDescriptor md, + FlowNode node) { - prefixList.removeAll(toberemoved); + System.out.println("#############################################################"); + System.out.println("calculateCompositeLocationFromFlowGraph=" + node); - return prefixList; + FlowGraph flowGraph = getFlowGraph(md); + // NTuple paramLocTuple = translateToLocTuple(md, paramNode.getDescTuple()); + // GlobalFlowNode paramGlobalNode = subGlobalFlowGraph.getFlowNode(paramLocTuple); - // 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); - // } - // } - // } + 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 boolean containsClassDesc(ClassDescriptor cd, NTuple prefixLocTuple) { @@ -1184,24 +2185,7 @@ public class LocationInference { // 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); @@ -1215,7 +2199,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); @@ -1227,7 +2210,6 @@ public class LocationInference { } else if (desc instanceof FieldDescriptor) { enclosingDesc = ((FieldDescriptor) desc).getType().getClassDesc(); } else { - // TODO: inter descriptor case enclosingDesc = desc; } @@ -1308,12 +2290,14 @@ public class LocationInference { 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); } } @@ -1323,110 +2307,6 @@ public class LocationInference { } - private void addValueFlowBetweenParametersToCaller(MethodInvokeNode min, - MethodDescriptor mdCaller, MethodDescriptor mdCallee) { - - System.out.println("***addValueFlowBetweenParametersToCaller from mdCallee=" + mdCallee); - - Set> PCLocTupleSet = mapMethodInvokeNodeToPCLocTupleSet.get(min); - System.out.println("-PCLocTupleSet=" + PCLocTupleSet); - - GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(mdCallee); - GlobalFlowGraph callerSubGlobalGraph = getSubGlobalFlowGraph(mdCaller); - - // if the parameter A reaches to the parameter B - // then, add an edge the argument A -> the argument B to the global flow graph - FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); - FlowGraph callerFlowGraph = getFlowGraph(mdCaller); - int numParam = calleeFlowGraph.getNumParameters(); - - for (int i = 0; i < numParam; i++) { - for (int k = 0; k < numParam; k++) { - - if (i != k) { - - System.out.println("i=" + i + " k=" + k); - - FlowNode paramNode1 = calleeFlowGraph.getParamFlowNode(i); - FlowNode paramNode2 = calleeFlowGraph.getParamFlowNode(k); - - NTuple arg1Tuple = getNodeTupleByArgIdx(min, i); - NTuple arg2Tuple = getNodeTupleByArgIdx(min, k); - - NTuple paramDescTuple1 = paramNode1.getCurrentDescTuple(); - NTuple paramDescTuple2 = paramNode2.getCurrentDescTuple(); - - 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; - } - - NTuple paramLocTuple1 = translateToLocTuple(mdCallee, paramDescTuple1); - NTuple paramLocTuple2 = translateToLocTuple(mdCallee, paramDescTuple2); - - // check if the callee propagates an ordering constraints through - // parameters - - // Set localReachSet = calleeFlowGraph.getLocalReachFlowNodeSetFrom(paramNode1); - - Set reachToParam1Set = - calleeSubGlobalGraph.getIncomingNodeSetByPrefix(paramLocTuple1.get(0)); - - // System.out.println("-- localReachSet from param1=" + localReachSet); - - GlobalFlowNode globalFlowNodeParam1 = calleeSubGlobalGraph.getFlowNode(paramLocTuple1); - GlobalFlowNode globalFlowNodeParam2 = calleeSubGlobalGraph.getFlowNode(paramLocTuple2); - - System.out.println("-param1CurTuple=" + paramDescTuple1 + " param2CurTuple=" - + paramDescTuple2); - - System.out.println("arg1Tuple=" + arg1Tuple + " arg2Tuple=" + arg2Tuple); - // System.out.println("-reachToParam1Set=" + reachToParam1Set); - - if (arg1Tuple.size() > 0 && arg2Tuple.size() > 0 - && reachToParam1Set.contains(globalFlowNodeParam2)) { - // need to propagate an ordering relation s.t. arg1 is higher - // than arg2 - System.out.println("---param1=" + paramNode1 + " is higher than param2=" + paramNode2); - - NTuple callerSrcNodeLocTuple = - translateToCallerLocTuple(min, mdCallee, mdCaller, paramLocTuple1); - - NTuple callerDstNodeLocTuple = - translateToCallerLocTuple(min, mdCallee, mdCaller, paramLocTuple2); - - System.out.println("---callerSrcNodeLocTuple=" + callerSrcNodeLocTuple); - System.out.println("---callerDstNodeLocTuple=" + callerDstNodeLocTuple); - - System.out.println("-----add global value flow :" + callerSrcNodeLocTuple + "->" - + callerDstNodeLocTuple); - callerSubGlobalGraph.addValueFlowEdge(callerSrcNodeLocTuple, callerDstNodeLocTuple); - for (Iterator iterator = PCLocTupleSet.iterator(); iterator.hasNext();) { - NTuple pcLocTuple = (NTuple) iterator.next(); - System.out.println("-----add global value flow PC :" + pcLocTuple + "->" - + callerSrcNodeLocTuple); - callerSubGlobalGraph.addValueFlowEdge(pcLocTuple, callerSrcNodeLocTuple); - } - - // add a new flow between the corresponding arguments. - callerFlowGraph.addValueFlowEdge(arg1Tuple, arg2Tuple); - System.out.println("arg1=" + arg1Tuple + " arg2=" + arg2Tuple); - - // System.out - // .println("-arg1Tuple=" + arg1Tuple + " is higher than arg2Tuple=" + arg2Tuple); - - } - - System.out.println(); - } - } - } - - } - private void addValueFlowFromCalleeNode(MethodInvokeNode min, MethodDescriptor mdCaller, MethodDescriptor mdCallee, GlobalFlowNode calleeSrcNode) { @@ -1449,7 +2329,8 @@ public class LocationInference { translateToCallerLocTuple(min, mdCallee, mdCaller, outNode.getLocTuple()); // System.out.println("outNode=" + outNode + " callerDstNodeLocTuple=" // + callerDstNodeLocTuple); - if (callerDstNodeLocTuple != null) { + if (callerSrcNodeLocTuple != null && callerDstNodeLocTuple != null + && callerSrcNodeLocTuple.size() > 0 && callerDstNodeLocTuple.size() > 0) { callerSubGlobalGraph.addValueFlowEdge(callerSrcNodeLocTuple, callerDstNodeLocTuple); } } @@ -1462,8 +2343,9 @@ 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); @@ -1473,6 +2355,8 @@ public class LocationInference { // // 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(); @@ -1501,6 +2385,29 @@ public class LocationInference { return false; } + public static boolean isReference(Descriptor desc) { + + if (desc instanceof FieldDescriptor) { + + TypeDescriptor type = ((FieldDescriptor) desc).getType(); + if (type.isArray()) { + return !type.isPrimitive(); + } else { + return type.isPtr(); + } + + } else if (desc instanceof VarDescriptor) { + TypeDescriptor type = ((VarDescriptor) desc).getType(); + if (type.isArray()) { + return !type.isPrimitive(); + } else { + return type.isPtr(); + } + } + + return false; + } + private NTuple translateToDescTuple(NTuple locTuple) { NTuple descTuple = new NTuple(); @@ -1552,18 +2459,6 @@ public class LocationInference { FlowNode flowNode = flowGraph.getParamFlowNode(paramIdx); CompositeLocation inferredCompLoc = updateCompositeLocation(flowNode.getCompositeLocation()); - // NTuple descTuple = flowNode.getDescTuple(); - // - // CompositeLocation assignedCompLoc = flowNode.getCompositeLocation(); - // CompositeLocation inferredCompLoc; - // if (assignedCompLoc != null) { - // inferredCompLoc = translateCompositeLocation(assignedCompLoc); - // } else { - // Descriptor locDesc = descTuple.get(0); - // Location loc = new Location(md, locDesc.getSymbol()); - // loc.setLocDescriptor(locDesc); - // inferredCompLoc = new CompositeLocation(loc); - // } System.out.println("-paramIdx=" + paramIdx + " infer=" + inferredCompLoc + " original=" + flowNode.getCompositeLocation()); @@ -1692,12 +2587,12 @@ public class LocationInference { // HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(key); HierarchyGraph scHierarchyGraph = getSkeletonCombinationHierarchyGraph(key); if (key instanceof ClassDescriptor) { - writeInferredLatticeDotFile((ClassDescriptor) key, scHierarchyGraph, simpleLattice, - "_SIMPLE"); + // writeInferredLatticeDotFile((ClassDescriptor) key, scHierarchyGraph, simpleLattice, + // "_SIMPLE"); } else if (key instanceof MethodDescriptor) { MethodDescriptor md = (MethodDescriptor) key; - writeInferredLatticeDotFile(md.getClassDesc(), md, scHierarchyGraph, simpleLattice, - "_SIMPLE"); + // writeInferredLatticeDotFile(md.getClassDesc(), md, scHierarchyGraph, simpleLattice, + // "_SIMPLE"); } LocationSummary ls = getLocationSummary(key); @@ -1707,8 +2602,10 @@ public class LocationInference { Set cdKeySet = cd2lattice.keySet(); for (Iterator iterator = cdKeySet.iterator(); iterator.hasNext();) { ClassDescriptor cd = (ClassDescriptor) iterator.next(); + System.out.println("########cd=" + cd); writeInferredLatticeDotFile((ClassDescriptor) cd, getSkeletonCombinationHierarchyGraph(cd), cd2lattice.get(cd), ""); + COUNT += cd2lattice.get(cd).getKeySet().size(); } Set mdKeySet = md2lattice.keySet(); @@ -1716,14 +2613,40 @@ public class LocationInference { MethodDescriptor md = (MethodDescriptor) iterator.next(); writeInferredLatticeDotFile(md.getClassDesc(), md, getSkeletonCombinationHierarchyGraph(md), md2lattice.get(md), ""); + COUNT += md2lattice.get(md).getKeySet().size(); + } + System.out.println("###COUNT=" + COUNT); + } + + 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); + lattice.removeRedundantEdges(); + + if (desc instanceof ClassDescriptor) { + // field lattice + cd2lattice.put((ClassDescriptor) desc, lattice); + // ssjava.writeLatticeDotFile((ClassDescriptor) desc, null, lattice); + } else if (desc instanceof MethodDescriptor) { + // method lattice + md2lattice.put((MethodDescriptor) desc, lattice); + MethodDescriptor md = (MethodDescriptor) desc; + ClassDescriptor cd = md.getClassDesc(); + // ssjava.writeLatticeDotFile(cd, md, lattice); } } private void buildLattice() { - BuildLattice buildLattice = new BuildLattice(this); - Set keySet = mapDescriptorToCombineSkeletonHierarchyGraph.keySet(); for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { Descriptor desc = (Descriptor) iterator.next(); @@ -1751,18 +2674,67 @@ 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) { + + System.out.println("$$$toanalyze_classDescSet=" + toanalyze_classDescSet); + 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); + buildLattice.setIntermediateLocMap(md, parentMap); + } + buildLattice(md); + } + } + + // traverse children + Set children = getDirectSubClasses(cd); + for (Iterator iterator = children.iterator(); iterator.hasNext();) { + ClassDescriptor classDescriptor = (ClassDescriptor) iterator.next(); + if (toanalyze_classDescSet.contains(classDescriptor)) { + DFSBuildLatticeInheritanceTree(classDescriptor); + } + } } @@ -1791,15 +2763,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); } } @@ -1837,6 +2811,7 @@ public class LocationInference { Descriptor desc = (Descriptor) iterator.next(); getHierarchyGraph(desc).writeGraph(); getSimpleHierarchyGraph(desc).writeGraph(); + getSimpleHierarchyGraph(desc).writeGraph(true); } } @@ -1876,10 +2851,64 @@ public class LocationInference { if (!mapDescriptorToCombineSkeletonHierarchyGraph.containsKey(d)) { mapDescriptorToCombineSkeletonHierarchyGraph.put(d, new HierarchyGraph(d)); } - return mapDescriptorToCombineSkeletonHierarchyGraph.get(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 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 void constructHierarchyGraph() { + private void constructHierarchyGraph2() { // do fixed-point analysis @@ -1991,7 +3020,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();) { @@ -2002,13 +3033,17 @@ 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 originalSrcNode = (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(); + FlowNode originalSrcNode = fg.getFlowNode(edge.getInitTuple()); Set sourceNodeSet = new HashSet(); if (originalSrcNode instanceof FlowReturnNode) { FlowReturnNode rnode = (FlowReturnNode) originalSrcNode; - Set> tupleSet = rnode.getTupleSet(); + 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)); @@ -2018,82 +3053,127 @@ public class LocationInference { sourceNodeSet.add(originalSrcNode); } - System.out.println("---sourceNodeSet=" + sourceNodeSet); + // System.out.println("---sourceNodeSet=" + sourceNodeSet + " from originalSrcNode=" + // + originalSrcNode); + for (Iterator iterator3 = sourceNodeSet.iterator(); iterator3.hasNext();) { FlowNode srcNode = (FlowNode) iterator3.next(); + NTuple srcNodeTuple = srcNode.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(); - - Set dstNodeSet = new HashSet(); - if (originalDstNode instanceof FlowReturnNode) { - FlowReturnNode rnode = (FlowReturnNode) originalDstNode; - Set> tupleSet = rnode.getTupleSet(); - for (Iterator iterator4 = tupleSet.iterator(); iterator4.hasNext();) { - NTuple nTuple = (NTuple) iterator4.next(); - dstNodeSet.add(fg.getFlowNode(nTuple)); + // 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; } - } else { - dstNodeSet.add(originalDstNode); } - System.out.println("---dstNodeSet=" + dstNodeSet); - for (Iterator iterator4 = dstNodeSet.iterator(); iterator4.hasNext();) { - FlowNode dstNode = (FlowNode) iterator4.next(); - NTuple srcNodeTuple = srcNode.getDescTuple(); - NTuple dstNodeTuple = dstNode.getDescTuple(); + // if (outEdge.getInitTuple().equals(srcNodeTuple) + // && outEdge.getEndTuple().equals(dstNodeTuple)) { + + NTuple srcCurTuple = srcNode.getCurrentDescTuple(); + NTuple dstCurTuple = dstNode.getCurrentDescTuple(); - // if (outEdge.getInitTuple().equals(srcNodeTuple) - // && outEdge.getEndTuple().equals(dstNodeTuple)) { + // ////////////////////////// + // inheritance check + if (mapMethodDescToHighestOverriddenMethodDesc.containsKey(md)) { - NTuple srcCurTuple = srcNode.getCurrentDescTuple(); - NTuple dstCurTuple = dstNode.getCurrentDescTuple(); + MethodDescriptor highestOverriddenMethodDesc = + mapMethodDescToHighestOverriddenMethodDesc.get(md); - // System.out.println("-srcCurTuple=" + srcCurTuple + " dstCurTuple=" + dstCurTuple); + if (srcCurTuple.get(srcCurTuple.size() - 1).getSymbol().startsWith(PCLOC)) { + } - if ((srcCurTuple.size() > 1 && dstCurTuple.size() > 1) - && srcCurTuple.get(0).equals(dstCurTuple.get(0))) { + } + // ////////////////////////// - // value flows between fields - Descriptor desc = srcCurTuple.get(0); - ClassDescriptor classDesc; + System.out.println("-srcCurTuple=" + srcCurTuple + " dstCurTuple=" + dstCurTuple + + " srcNode=" + srcNode + " dstNode=" + dstNode); - if (desc.equals(GLOBALDESC)) { - classDesc = md.getClassDesc(); - } else { - VarDescriptor varDesc = (VarDescriptor) srcCurTuple.get(0); - classDesc = varDesc.getType().getClassDesc(); - } - extractFlowsBetweenFields(classDesc, srcNode, dstNode, 1); + // srcCurTuple = translateBaseTuple(srcNode, srcCurTuple); + // dstCurTuple = translateBaseTuple(dstNode, dstCurTuple); - } else if (!srcCurTuple.get(0).equals(dstCurTuple.get(0))) { - // value flow between local var - local var or local var - field + if ((srcCurTuple.size() > 1 && dstCurTuple.size() > 1) + && srcCurTuple.get(0).equals(dstCurTuple.get(0))) { - Descriptor srcDesc = srcCurTuple.get(0); - Descriptor dstDesc = dstCurTuple.get(0); + // value flows between fields + Descriptor desc = srcCurTuple.get(0); + ClassDescriptor classDesc; - methodGraph.addEdge(srcDesc, dstDesc); + if (desc.equals(GLOBALDESC)) { + classDesc = md.getClassDesc(); + } else { + VarDescriptor varDesc = (VarDescriptor) srcCurTuple.get(0); + classDesc = varDesc.getType().getClassDesc(); + } + extractFlowsBetweenFields(classDesc, srcNode, dstNode, 1); - if (fg.isParamDesc(srcDesc)) { - methodGraph.setParamHNode(srcDesc); - } - if (fg.isParamDesc(dstDesc)) { - methodGraph.setParamHNode(dstDesc); - } + } 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); + + methodGraph.addEdge(srcDesc, dstDesc); + + if (fg.isParamDesc(srcDesc)) { + methodGraph.setParamHNode(srcDesc); + } + if (fg.isParamDesc(dstDesc)) { + methodGraph.setParamHNode(dstDesc); } - // } } + // } + // } + } } @@ -2119,6 +3199,31 @@ public class LocationInference { } + 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) { if (!mapDescToLocationSummary.containsKey(md)) { mapDescToLocationSummary.put(md, new MethodSummary(md)); @@ -2248,20 +3353,31 @@ public class LocationInference { } } - rtr += "\")"; - if (desc instanceof MethodDescriptor) { System.out.println("#EXTRA LOC DECLARATION GEN=" + 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) + "\")"; @@ -2273,6 +3389,8 @@ public class LocationInference { } rtr += "\n@GLOBALLOC(\"" + methodSummary.getGlobalLocName() + "\")"; + } else { + rtr += "\")"; } return rtr; @@ -2371,6 +3489,7 @@ 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 @@ -2745,50 +3864,97 @@ public class LocationInference { 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 (!paramDescNOTHavingInFlowSet.contains(node.getCurrentDescTuple().get(0))) { - fg.addValueFlowEdge(pcDescTuple, node.getDescTuple()); + if (!(node instanceof FlowReturnNode)) { + if (!paramDescNOTHavingInFlowSet.contains(node.getCurrentDescTuple().get(0))) { + flowNodeLowerthanPCLocSet.add(node); + fg.addValueFlowEdge(pcDescTuple, node.getDescTuple()); + + subGlobalFlowGraph.addValueFlowEdge(pcLocTuple, + translateToLocTuple(md, node.getDescTuple())); + } + } else { + System.out.println("***SKIP PCLOC -> RETURNLOC=" + node); } + } fg.getFlowNode(translateToDescTuple(pcLocTuple)).setSkeleton(true); + + if (pcLocTuple.get(0).getLocDescriptor().equals(md.getThis())) { + System.out.println("#########################################"); + for (Iterator iterator = flowNodeLowerthanPCLocSet.iterator(); iterator.hasNext();) { + FlowNode lowerNode = (FlowNode) iterator.next(); + if (lowerNode.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); + } + + } + + } + } + } } } - 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; @@ -2801,14 +3967,20 @@ public class LocationInference { private void calculateRETURNLOC(MethodDescriptor md) { System.out.println("#calculateRETURNLOC= " + md); + // calculate a return location: // the return location type is lower than all parameters and the location of return values MethodSummary methodSummary = getMethodSummary(md); + // if (methodSummary.getRETURNLoc() != null) { + // System.out.println("$HERE?"); + // return; + // } + 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 @@ -2851,6 +4023,13 @@ public class LocationInference { } + // 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); + } + } } @@ -2910,7 +4089,8 @@ public class LocationInference { } 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; @@ -2933,9 +4113,9 @@ public class LocationInference { } - 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); @@ -3124,6 +4304,7 @@ public class LocationInference { private void propagateFlowsToCallerWithNoCompositeLocation(MethodInvokeNode min, MethodDescriptor mdCaller, MethodDescriptor mdCallee) { + 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 @@ -3146,15 +4327,17 @@ 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("-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 @@ -3163,20 +4346,22 @@ public class LocationInference { 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); // 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(); } } } @@ -3189,9 +4374,14 @@ public class LocationInference { 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); + 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); @@ -3208,6 +4398,18 @@ public class LocationInference { } + private boolean containsPrefix(Descriptor prefixDesc, Set set) { + + for (Iterator iterator = set.iterator(); iterator.hasNext();) { + FlowNode flowNode = (FlowNode) iterator.next(); + if (flowNode.getDescTuple().startsWith(prefixDesc)) { + System.out.println("FOUND=" + flowNode); + return true; + } + } + return false; + } + private NTuple translateCompositeLocationToCaller(int idx, MethodInvokeNode min, CompositeLocation compLocForParam1) { @@ -3218,7 +4420,7 @@ public class LocationInference { tuple.add(baseTuple.get(i)); } - for (int i = baseTuple.size(); i < compLocForParam1.getSize(); i++) { + for (int i = 1; i < compLocForParam1.getSize(); i++) { Location loc = compLocForParam1.get(i); tuple.add(loc.getLocDescriptor()); } @@ -3332,6 +4534,8 @@ public class LocationInference { } else if (curDescriptor instanceof NameDescriptor) { // it is "GLOBAL LOC" case! enclosingDescriptor = GLOBALDESC; + } else if (curDescriptor instanceof InterDescriptor) { + enclosingDescriptor = getFlowGraph(md).getEnclosingDescriptor(curDescriptor); } else { enclosingDescriptor = null; } @@ -3463,7 +4667,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 { @@ -3516,8 +4720,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); + } } @@ -3542,6 +4754,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); @@ -3564,7 +4781,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); } @@ -3606,6 +4824,21 @@ 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 mdToString = 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)")) { + mdToString = md; + break; + } + } + if (mdToString != null) { + toanalyze_methodDescList.remove(mdToString); + toanalyze_methodDescList.addLast(mdToString); + } + LinkedList methodDescList = (LinkedList) toanalyze_methodDescList.clone(); @@ -3646,7 +4879,6 @@ public class LocationInference { // subGlobalFlowGraph.writeGraph("_SUBGLOBAL"); // // propagateFlowsFromCalleesWithNoCompositeLocation(md); - } } // _debug_printGraph(); @@ -3821,6 +5053,7 @@ public class LocationInference { if (needToGenerateInterLoc(newImplicitTupleSet)) { // need to create an intermediate node for the GLB of conditional // locations & implicit flows + System.out.println("10"); NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); for (Iterator> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) { @@ -3887,6 +5120,8 @@ public class LocationInference { // System.out.println("---currentFlowTupleSet=" + currentFlowTupleSet); if (needToGenerateInterLoc(currentFlowTupleSet)) { + System.out.println("9"); + FlowNode meetNode = fg.createIntermediateNode(); for (Iterator iterator = currentFlowTupleSet.iterator(); iterator.hasNext();) { NTuple currentFlowTuple = (NTuple) iterator.next(); @@ -3925,6 +5160,7 @@ public class LocationInference { } } if (size > 1) { + System.out.println("needToGenerateInterLoc=" + tupleSet + " size=" + size); return true; } else { return false; @@ -3951,6 +5187,7 @@ public class LocationInference { if (needToGenerateInterLoc(newImplicitTupleSet)) { // need to create an intermediate node for the GLB of conditional // locations & implicit flows + System.out.println("6"); NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); for (Iterator> idxIter = newImplicitTupleSet.iterator(); idxIter @@ -4011,6 +5248,7 @@ public class LocationInference { if (needToGenerateInterLoc(newImplicitTupleSet)) { // need to create an intermediate node for the GLB of conditional // locations & implicit flows + System.out.println("7"); NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); for (Iterator> idxIter = newImplicitTupleSet.iterator(); idxIter @@ -4074,6 +5312,8 @@ public class LocationInference { // System.out.println("-newImplicitTupleSet=" + newImplicitTupleSet); if (needToGenerateInterLoc(newImplicitTupleSet)) { + System.out.println("5"); + // need to create an intermediate node for the GLB of conditional locations & implicit flows NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); for (Iterator> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) { @@ -4115,6 +5355,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, @@ -4123,12 +5364,14 @@ public class LocationInference { // creates edges from RHS to LHS NTuple interTuple = null; if (needToGenerateInterLoc(nodeSetRHS)) { - + System.out.println("3"); interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); } for (Iterator> iter = nodeSetRHS.iterator(); iter.hasNext();) { NTuple fromTuple = iter.next(); + System.out.println("fromTuple=" + fromTuple + " interTuple=" + interTuple + " tupleLSH=" + + tupleLHS); addFlowGraphEdge(md, fromTuple, interTuple, tupleLHS); } @@ -4141,9 +5384,20 @@ public class LocationInference { 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); + } } @@ -4163,12 +5417,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); @@ -4254,20 +5509,48 @@ public class LocationInference { private void analyzeFlowTertiaryNode(MethodDescriptor md, SymbolTable nametable, TertiaryNode tn, NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) { + // System.out.println("analyzeFlowTertiaryNode=" + tn.printNode(0)); + NodeTupleSet tertiaryTupleNode = new NodeTupleSet(); analyzeFlowExpressionNode(md, nametable, tn.getCond(), tertiaryTupleNode, null, implicitFlowTupleSet, false); + NodeTupleSet newImplicitTupleSet = new NodeTupleSet(); + newImplicitTupleSet.addTupleSet(implicitFlowTupleSet); + newImplicitTupleSet.addTupleSet(tertiaryTupleNode); + + // System.out.println("$$$GGGcondTupleNode=" + tertiaryTupleNode.getGlobalLocTupleSet()); + // System.out.println("-tertiaryTupleNode=" + tertiaryTupleNode); + // System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet); + // System.out.println("-newImplicitTupleSet=" + newImplicitTupleSet); + + if (needToGenerateInterLoc(newImplicitTupleSet)) { + System.out.println("15"); + // need to create an intermediate node for the GLB of conditional locations & implicit flows + NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); + for (Iterator> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) { + NTuple tuple = idxIter.next(); + addFlowGraphEdge(md, tuple, interTuple); + } + newImplicitTupleSet.clear(); + newImplicitTupleSet.addTuple(interTuple); + } + + newImplicitTupleSet.addGlobalFlowTupleSet(tertiaryTupleNode.getGlobalLocTupleSet()); + + System.out.println("---------newImplicitTupleSet=" + newImplicitTupleSet); // add edges from tertiaryTupleNode to all nodes of conditional nodes - tertiaryTupleNode.addTupleSet(implicitFlowTupleSet); + // tertiaryTupleNode.addTupleSet(implicitFlowTupleSet); analyzeFlowExpressionNode(md, nametable, tn.getTrueExpr(), tertiaryTupleNode, null, - implicitFlowTupleSet, false); + newImplicitTupleSet, false); analyzeFlowExpressionNode(md, nametable, tn.getFalseExpr(), tertiaryTupleNode, null, - implicitFlowTupleSet, false); + newImplicitTupleSet, false); + nodeSet.addGlobalFlowTupleSet(tertiaryTupleNode.getGlobalLocTupleSet()); nodeSet.addTupleSet(tertiaryTupleNode); + System.out.println("#tertiary node set=" + nodeSet); } private void addMapCallerMethodDescToMethodInvokeNodeSet(MethodDescriptor caller, @@ -4313,6 +5596,8 @@ public class LocationInference { return; } + addMapMethodDescToMethodInvokeNodeSet(min); + Set> pcLocTupleSet = getPCLocTupleSet(min); for (Iterator iterator = implicitFlowTupleSet.iterator(); iterator.hasNext();) { NTuple pcDescTuple = (NTuple) iterator.next(); @@ -4342,21 +5627,11 @@ public class LocationInference { addMapCallerMethodDescToMethodInvokeNodeSet(mdCaller, min); FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); - System.out.println("mdCallee=" + mdCallee); + System.out.println("mdCallee=" + mdCallee + " calleeFlowGraph=" + calleeFlowGraph); Set calleeReturnSet = calleeFlowGraph.getReturnNodeSet(); System.out.println("---calleeReturnSet=" + calleeReturnSet); - // 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()); - nodeSet.addGlobalFlowTuple(calleeReturnLocTuple); - } - NodeTupleSet tupleSet = new NodeTupleSet(); if (min.getExpression() != null) { @@ -4364,9 +5639,17 @@ public class LocationInference { NodeTupleSet baseNodeSet = new NodeTupleSet(); 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()) { @@ -4379,19 +5662,31 @@ public class LocationInference { // 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); - tupleSet.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); for (Iterator iterator2 = inFlowSet.iterator(); iterator2.hasNext();) { FlowNode inFlowNode = (FlowNode) iterator2.next(); if (inFlowNode.getDescTuple().startsWith(mdCallee.getThis())) { // nodeSet.addTupleSet(baseNodeSet); + System.out.println("2CREATE A NEW TUPLE=" + baseNodeSet + " from=" + + mdCallee.getThis()); tupleSet.addTupleSet(baseNodeSet); - } } } @@ -4416,7 +5711,7 @@ public class LocationInference { NodeTupleSet argTupleSet = new NodeTupleSet(); analyzeFlowExpressionNode(mdCaller, nametable, en, argTupleSet, false); // if argument is liternal node, argTuple is set to NULL - System.out.println("argTupleSet=" + argTupleSet); + System.out.println("---arg idx=" + idx + " argTupleSet=" + argTupleSet); NTuple argTuple = generateArgTuple(mdCaller, argTupleSet); // if an argument is literal value, @@ -4424,13 +5719,16 @@ public class LocationInference { // 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); - NTuple interTuple = - getFlowGraph(mdCaller).createIntermediateNode().getDescTuple(); - addFlowGraphEdge(mdCaller, argTuple, interTuple); - argTuple = interTuple; - addArgIdxMap(min, idx, argTuple); - System.out.println("new min mapping i=" + idx + " ->" + argTuple); + /* + * 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); @@ -4449,10 +5747,12 @@ public class LocationInference { // } // } + System.out.println("paramNode=" + paramNode + " calleeReturnSet=" + calleeReturnSet); if (hasInFlowTo(calleeFlowGraph, paramNode, calleeReturnSet) || mdCallee.getModifiers().isNative()) { addParamNodeFlowingToReturnValue(mdCallee, paramNode); // nodeSet.addTupleSet(argTupleSet); + System.out.println("3CREATE A NEW TUPLE=" + argTupleSet + " from=" + paramNode); tupleSet.addTupleSet(argTupleSet); } } @@ -4460,15 +5760,119 @@ public class LocationInference { } if (mdCallee.getReturnType() != null && !mdCallee.getReturnType().isVoid()) { - FlowReturnNode setNode = getFlowGraph(mdCaller).createReturnNode(min); - nodeSet.addTuple(setNode.getDescTuple()); + FlowReturnNode returnHolderNode = getFlowGraph(mdCaller).createReturnNode(min); + + if (needToGenerateInterLoc(tupleSet)) { + System.out.println("20"); + 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()); + // 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) { @@ -4492,6 +5896,8 @@ public class LocationInference { } if (argTupleSetNonLiteral.size() > 1) { + System.out.println("11"); + NTuple interTuple = getFlowGraph(mdCaller).createIntermediateNode().getDescTuple(); for (Iterator> idxIter = argTupleSet.iterator(); idxIter.hasNext();) { @@ -4510,6 +5916,10 @@ 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); @@ -4549,14 +5959,16 @@ public class LocationInference { private void analyzeFlowArrayAccessNode(MethodDescriptor md, SymbolTable nametable, ArrayAccessNode aan, NodeTupleSet nodeSet, boolean isLHS) { - // System.out.println("analyzeFlowArrayAccessNode aan=" + aan.printNode(0)); + 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); @@ -4578,6 +5990,7 @@ public class LocationInference { NTuple calleeReturnLocTuple = iterator.next(); for (Iterator> arrIter = expNodeTupleSet.iterator(); arrIter.hasNext();) { NTuple arrTuple = arrIter.next(); + globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, translateToLocTuple(md, arrTuple)); } } @@ -4594,7 +6007,9 @@ public class LocationInference { || !arrayAccessNodeStack.peek().startsWith(currentArrayAccessNodeExpStr)) { if (needToGenerateInterLoc(nodeSetArrayAccessExp)) { - NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); + System.out.println("1"); + FlowNode interNode = getFlowGraph(md).createIntermediateNode(); + NTuple interTuple = interNode.getDescTuple(); for (Iterator> iter = nodeSetArrayAccessExp.iterator(); iter.hasNext();) { NTuple higherTuple = iter.next(); @@ -4602,6 +6017,14 @@ public class LocationInference { } 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); + } } } @@ -4624,15 +6047,19 @@ 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); + System.out.println("--leftOpSet=" + leftOpSet); if (on.getRight() != null) { // right operand analyzeFlowExpressionNode(md, nametable, on.getRight(), rightOpSet, null, implicitFlowTupleSet, false); } + System.out.println("--rightOpSet=" + rightOpSet); Operation op = on.getOp(); @@ -4801,7 +6228,6 @@ public class LocationInference { analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, base, implicitFlowTupleSet, isLHS); - nodeSet.addTupleSet(idxNodeTupleSet); } base = analyzeFlowExpressionNode(md, nametable, left, nodeSet, base, implicitFlowTupleSet, isLHS); @@ -4832,11 +6258,13 @@ public class LocationInference { 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) { @@ -4848,8 +6276,14 @@ public class LocationInference { nodeSetArrayAccessExp.addTuple(flowFieldTuple); nodeSetArrayAccessExp.addTupleSet(idxNodeTupleSet); + nodeSetArrayAccessExp.addTupleSet(nodeSet); if (needToGenerateInterLoc(nodeSetArrayAccessExp)) { + System.out.println("4"); + System.out.println("nodeSetArrayAccessExp=" + nodeSetArrayAccessExp); + // System.out.println("idxNodeTupleSet.getGlobalLocTupleSet()=" + // + idxNodeTupleSet.getGlobalLocTupleSet()); + NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); @@ -4858,9 +6292,14 @@ public class LocationInference { 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()); } @@ -4901,10 +6340,10 @@ public class LocationInference { analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null, implicitFlowTupleSet, false); - // System.out.println("-analyzeFlowAssignmentNode=" + an.printNode(0)); - // System.out.println("-nodeSetLHS=" + nodeSetLHS); - // System.out.println("-nodeSetRHS=" + nodeSetRHS); - // System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet); + System.out.println("-analyzeFlowAssignmentNode=" + an.printNode(0)); + System.out.println("-nodeSetLHS=" + nodeSetLHS); + System.out.println("-nodeSetRHS=" + nodeSetRHS); + System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet); // System.out.println("-"); if (an.getOperation().getOp() >= 2 && an.getOperation().getOp() <= 12) { @@ -4922,6 +6361,7 @@ public class LocationInference { // creates edges from RHS to LHS NTuple interTuple = null; if (needToGenerateInterLoc(nodeSetRHS)) { + System.out.println("2"); interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); } @@ -4948,10 +6388,11 @@ public class LocationInference { NTuple calleeReturnLocTuple = iterator.next(); for (Iterator> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) { NTuple callerLHSTuple = iter2.next(); - globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, - translateToLocTuple(md, callerLHSTuple)); System.out.println("$$$ GLOBAL FLOW ADD=" + calleeReturnLocTuple + " -> " + translateToLocTuple(md, callerLHSTuple)); + + globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, + translateToLocTuple(md, callerLHSTuple)); } } @@ -4960,6 +6401,7 @@ public class LocationInference { 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 + " -> " @@ -5032,6 +6474,8 @@ public class LocationInference { public void writeInferredLatticeDotFile(ClassDescriptor cd, HierarchyGraph simpleHierarchyGraph, SSJavaLattice locOrder, String nameSuffix) { + System.out.println("@cd=" + cd); + System.out.println("@sharedLoc=" + locOrder.getSharedLocSet()); writeInferredLatticeDotFile(cd, null, simpleHierarchyGraph, locOrder, nameSuffix); } @@ -5041,13 +6485,15 @@ public class LocationInference { String fileName = "lattice_"; if (md != null) { fileName += - /* cd.getSymbol().replaceAll("[\\W_]", "") + "_" + */md.toString().replaceAll("[\\W_]", ""); + cd.getSymbol().replaceAll("[\\W_]", "") + "_" + md.toString().replaceAll("[\\W_]", ""); } else { fileName += cd.getSymbol().replaceAll("[\\W_]", ""); } fileName += nameSuffix; + System.out.println("***lattice=" + fileName + " setsize=" + locOrder.getKeySet().size()); + Set> pairSet = locOrder.getOrderingPairSet(); Set addedLocSet = new HashSet(); @@ -5064,7 +6510,6 @@ public class LocationInference { String highLocId = pair.getFirst(); String lowLocId = pair.getSecond(); - if (!addedLocSet.contains(highLocId)) { addedLocSet.add(highLocId); drawNode(bw, locOrder, simpleHierarchyGraph, highLocId); @@ -5104,23 +6549,17 @@ public class LocationInference { private void drawNode(BufferedWriter bw, SSJavaLattice lattice, HierarchyGraph graph, String locName) throws IOException { - HNode node = graph.getHNode(locName); - - if (node == null) { - return; - } - String prettyStr; if (lattice.isSharedLoc(locName)) { prettyStr = locName + "*"; } else { prettyStr = locName; } - - if (node.isMergeNode()) { - Set mergeSet = graph.getMapHNodetoMergeSet().get(node); - prettyStr += ":" + convertMergeSetToString(graph, mergeSet); - } + // HNode node = graph.getHNode(locName); + // if (node != null && node.isMergeNode()) { + // Set mergeSet = graph.getMapHNodetoMergeSet().get(node); + // prettyStr += ":" + convertMergeSetToString(graph, mergeSet); + // } bw.write(locName + " [label=\"" + prettyStr + "\"]" + ";\n"); } @@ -5149,8 +6588,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; + } + }