From: yeom Date: Fri, 12 Oct 2012 02:47:41 +0000 (+0000) Subject: changes. X-Git-Url: http://plrg.eecs.uci.edu/git/?p=IRC.git;a=commitdiff_plain;h=9cdbca1a3dcc949bee74ee42ddd8febff6048b9f changes. --- diff --git a/Robust/src/Analysis/SSJava/BuildLattice.java b/Robust/src/Analysis/SSJava/BuildLattice.java index bbef531a..eb38f270 100644 --- a/Robust/src/Analysis/SSJava/BuildLattice.java +++ b/Robust/src/Analysis/SSJava/BuildLattice.java @@ -14,8 +14,13 @@ public class BuildLattice { public static int seed = 0; private LocationInference infer; + private final HNode topNode; + private final HNode bottomNode; + public BuildLattice(LocationInference infer) { this.infer = infer; + topNode = new HNode(infer.ssjava.TOP); + bottomNode = new HNode(infer.ssjava.BOTTOM); } public SSJavaLattice buildLattice(Descriptor desc) { @@ -47,12 +52,17 @@ public class BuildLattice { Set higher = (Set) iterator.next(); String higherName = generateElementName(basisSet, inputGraph, mapFToLocName, higher); - locSummary.addMapHNodeNameToLocationName(higherName, higherName); HNode higherNode = inputGraph.getHNode(higherName); if (higherNode != null && higherNode.isSharedNode()) { lattice.addSharedLoc(higherName); } + Set descSet = inputGraph.getDescSetOfNode(higherNode); + for (Iterator iterator2 = descSet.iterator(); iterator2.hasNext();) { + Descriptor d = (Descriptor) iterator2.next(); + locSummary.addMapHNodeNameToLocationName(d.getSymbol(), higherName); + } + // locSummary.addMapHNodeNameToLocationName(higherName, higherName); Set> lowerSet = mapImSucc.get(higher); for (Iterator iterator2 = lowerSet.iterator(); iterator2.hasNext();) { @@ -121,8 +131,7 @@ public class BuildLattice { for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { HNode node = (HNode) iterator.next(); - System.out.println("-node=" + node); - + System.out.println("node=" + node); if (node.isSkeleton() && (!visited.contains(node))) { visited.add(node); @@ -155,7 +164,6 @@ public class BuildLattice { HNode endNode = (HNode) iterator3.next(); endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode)); } - // System.out.println("-endCombNodeSet=" + endCombNodeSet); visited.add(outNode); // follows the straight line up to another skeleton/combination node @@ -164,13 +172,11 @@ public class BuildLattice { removeTransitivelyReachToNode(desc, combinationNodeInSCGraph, endCombNodeSet); recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited, mapIntermediateLoc, 1, locSummary, outNode); - // recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited, - // mapIntermediateLoc, 1, locSummary, outNode); } } else { // we have a node that is neither combination or skeleton node - // System.out.println("skeleton node=" + node + " outNode=" + outNode); + System.out.println("%%%skeleton node=" + node + " outNode=" + outNode); HNode startNode = scGraph.getCurrentHNode(node); // if (node.getDescriptor() != null) { @@ -185,21 +191,25 @@ public class BuildLattice { Set endNodeSetFromSimpleGraph = simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(outNode, null); - // System.out.println("endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph - // + " from=" + outNode); + System.out.println("endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph + + " from=" + outNode); Set endCombNodeSet = new HashSet(); for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) { HNode endNode = (HNode) iterator3.next(); endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode)); } - + System.out.println("endCombNodeSet=" + endCombNodeSet); visited.add(outNode); if (endCombNodeSet.size() > 0) { // follows the straight line up to another skeleton/combination node endCombNodeSet = removeTransitivelyReachToNode(desc, startNode, endCombNodeSet); - recurDFSNormalNode(desc, lattice, startNode, endCombNodeSet, visited, - mapIntermediateLoc, 1, locSummary, outNode); + } else if (endCombNodeSet.size() == 0) { + // the outNode is (directly/transitively) connected to the bottom node + // therefore, we just add a dummy bottom HNode to the endCombNodeSet. + endCombNodeSet.add(bottomNode); } + recurDFSNormalNode(desc, lattice, startNode, endCombNodeSet, visited, + mapIntermediateLoc, 1, locSummary, outNode); } } @@ -209,56 +219,31 @@ public class BuildLattice { && !visited.contains(node)) { // an intermediate node 'node' may be located between "TOP" location and a skeleton node + int sizeIncomingNode = simpleGraph.getIncomingNodeSet(node).size(); - Set outNodeSet = - simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(node, null); - // Set outNodeSet = simpleGraph.getOutgoingNodeSet(node); - System.out.println("this case? node=" + node + " outNodeSet=" + outNodeSet); + if (sizeIncomingNode == 0) { + // this node will be directly connected to the TOP location + // start adding the following nodes from this node - Set belowSkeletonLocNameSet = new HashSet(); - Set belowSCNodeSet = new HashSet(); + Set endNodeSetFromSimpleGraph = + simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(node, null); - for (Iterator iterator2 = outNodeSet.iterator(); iterator2.hasNext();) { - HNode outNode = (HNode) iterator2.next(); - if (outNode.isSkeleton()) { - belowSCNodeSet.add(scGraph.getCurrentHNode(outNode)); - belowSkeletonLocNameSet.add(scGraph.getCurrentHNode(outNode).getName()); - } - } - System.out.println("-belowSkeletonLocNameSet=" + belowSkeletonLocNameSet); - if (belowSkeletonLocNameSet.size() > 0) { - - int count = simpleGraph.countHopFromTopLocation(node); - System.out.println("---count=" + count); - - TripleItem item = new TripleItem(null, belowSCNodeSet, count); - if (!mapIntermediateLoc.containsKey(item)) { - String newLocName = "ILOC" + (seed++); - mapIntermediateLoc.put(item, newLocName); - lattice.insertNewLocationBetween(lattice.getTopItem(), belowSkeletonLocNameSet, - newLocName); - locSummary.addMapHNodeNameToLocationName(node.getName(), newLocName); - } else { - String locName = mapIntermediateLoc.get(item); - locSummary.addMapHNodeNameToLocationName(node.getName(), locName); + Set endCombNodeSet = new HashSet(); + for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) { + HNode endNode = (HNode) iterator3.next(); + endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode)); } - // if (!mapBelowNameSetToILOCName.containsKey(belowSkeletonLocNameSet)) { - // String newLocName = "ILOC" + (seed++); - // mapBelowNameSetToILOCName.put(belowSkeletonLocNameSet, newLocName); - // lattice.insertNewLocationBetween(lattice.getTopItem(), belowSkeletonLocNameSet, - // newLocName); - // locSummary.addMapHNodeNameToLocationName(node.getName(), newLocName); - // } else { - // String ilocName = mapBelowNameSetToILOCName.get(belowSkeletonLocNameSet); - // locSummary.addMapHNodeNameToLocationName(node.getName(), ilocName); - // } + HNode startNode = topNode; + visited.add(startNode); + if (endCombNodeSet.size() > 0) { + // follows the straight line up to another skeleton/combination node + // endCombNodeSet = removeTransitivelyReachToNode(desc, node, endCombNodeSet); + recurDFSNormalNode(desc, lattice, startNode, endCombNodeSet, visited, + mapIntermediateLoc, 1, locSummary, node); + } } - // else { - // System.out.println("---LocName=" + newLocName); - // lattice.put(newLocName); - // } } } @@ -348,9 +333,15 @@ public class BuildLattice { } String locName = mapIntermediateLoc.get(item); - locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName); - HierarchyGraph graph = infer.getSimpleHierarchyGraph(desc); + + Set descSet = graph.getDescSetOfNode(curNode); + for (Iterator iterator = descSet.iterator(); iterator.hasNext();) { + Descriptor d = (Descriptor) iterator.next(); + locSummary.addMapHNodeNameToLocationName(d.getSymbol(), locName); + } + // locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName); + Set outSet = graph.getOutgoingNodeSet(curNode); for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) { HNode outNode = (HNode) iterator2.next(); @@ -393,13 +384,17 @@ public class BuildLattice { } + HierarchyGraph graph = infer.getSimpleHierarchyGraph(desc); String locName = mapIntermediateLoc.get(item); - locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName); + Set descSet = graph.getDescSetOfNode(curNode); + for (Iterator iterator = descSet.iterator(); iterator.hasNext();) { + Descriptor d = (Descriptor) iterator.next(); + locSummary.addMapHNodeNameToLocationName(d.getSymbol(), locName); + } // System.out.println("-TripleItem=" + item); // System.out.println("-curNode=" + curNode.getName() + " locName=" + locName); - HierarchyGraph graph = infer.getSimpleHierarchyGraph(desc); Set outSet = graph.getOutgoingNodeSet(curNode); for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) { HNode outNode = (HNode) iterator2.next(); diff --git a/Robust/src/Analysis/SSJava/CompositeLocation.java b/Robust/src/Analysis/SSJava/CompositeLocation.java index 5308cb67..f7e550c5 100644 --- a/Robust/src/Analysis/SSJava/CompositeLocation.java +++ b/Robust/src/Analysis/SSJava/CompositeLocation.java @@ -10,6 +10,10 @@ public class CompositeLocation implements TypeExtension { locTuple = new NTuple(); } + public CompositeLocation(NTuple locTuple) { + this.locTuple = locTuple.clone(); + } + public CompositeLocation(Location loc) { locTuple = new NTuple(); locTuple.add(loc); diff --git a/Robust/src/Analysis/SSJava/HierarchyGraph.java b/Robust/src/Analysis/SSJava/HierarchyGraph.java index 5b0b85f2..304121c7 100644 --- a/Robust/src/Analysis/SSJava/HierarchyGraph.java +++ b/Robust/src/Analysis/SSJava/HierarchyGraph.java @@ -470,7 +470,7 @@ public class HierarchyGraph { return mergingSet; } - private Set getDescSetOfNode(HNode node) { + public Set getDescSetOfNode(HNode node) { if (!mapHNodeToDescSet.containsKey(node)) { mapHNodeToDescSet.put(node, new HashSet()); } diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index 4cca1c49..e2c808c7 100644 --- a/Robust/src/Analysis/SSJava/LocationInference.java +++ b/Robust/src/Analysis/SSJava/LocationInference.java @@ -126,6 +126,8 @@ public class LocationInference { public static final String PCLOC = "PCLOC"; + public static final String RLOC = "RLOC"; + public static final Descriptor GLOBALDESC = new NameDescriptor(GLOBALLOC); public static final Descriptor TOPDESC = new NameDescriptor(TOPLOC); @@ -219,13 +221,11 @@ public class LocationInference { public void inference() { - // 1) construct value flow graph + // construct value flow graph constructFlowGraph(); assignCompositeLocation(); - // constructGlobalFlowGraph(); - constructHierarchyGraph(); debug_writeHierarchyDotFiles(); @@ -245,8 +245,6 @@ public class LocationInference { debug_writeSkeletonCombinationHierarchyDotFiles(); - // System.exit(0); - buildLattice(); debug_writeLattices(); @@ -255,6 +253,8 @@ public class LocationInference { generateMethodSummary(); + generateAnnoatedCode(); + System.exit(0); // 2) construct lattices @@ -263,9 +263,6 @@ public class LocationInference { // 3) check properties // checkLattices(); - // calculate RETURNLOC,PCLOC - calculateExtraLocations(); - debug_writeLatticeDotFile(); // 4) generate annotated source codes @@ -307,9 +304,10 @@ public class LocationInference { while (!methodDescList.isEmpty()) { MethodDescriptor md = methodDescList.removeLast(); - GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md); FlowGraph flowGraph = getFlowGraph(md); + MethodSummary methodSummary = getMethodSummary(md); + Set nodeSet = flowGraph.getNodeSet(); for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { FlowNode node = (FlowNode) iterator.next(); @@ -320,8 +318,14 @@ public class LocationInference { } else { NTuple descTuple = node.getDescTuple(); CompositeLocation compLoc = convertToCompositeLocation(md, descTuple); + compLoc = updateCompositeLocation(compLoc); node.setCompositeLocation(compLoc); } + + if (node.isDeclaratonNode()) { + Descriptor localVarDesc = node.getDescTuple().get(0); + methodSummary.addMapVarNameToInferCompLoc(localVarDesc, node.getCompositeLocation()); + } } } @@ -334,8 +338,14 @@ public class LocationInference { Location loc = compLoc.get(i); String nodeIdentifier = loc.getLocIdentifier(); Descriptor enclosingDesc = loc.getDescriptor(); - LocationSummary locSummary = getLocationSummary(enclosingDesc); - String locName = locSummary.getLocationName(nodeIdentifier); + System.out.println("enclosingDesc=" + enclosingDesc); + String locName; + if (!enclosingDesc.equals(GLOBALDESC)) { + LocationSummary locSummary = getLocationSummary(enclosingDesc); + locName = locSummary.getLocationName(nodeIdentifier); + } else { + locName = nodeIdentifier; + } Location updatedLoc = new Location(enclosingDesc, locName); updatedCompLoc.addLocation(updatedLoc); } @@ -446,15 +456,15 @@ public class LocationInference { NTuple baseLocTuple = translateToLocTuple(mdCaller, mapMethodInvokeNodeToBaseTuple.get(min)); - System.out.println("\n-translate caller infer composite loc to callee=" + mdCallee - + " baseLocTuple=" + baseLocTuple); + // System.out.println("\n-translate caller infer composite loc to callee=" + mdCallee + // + " baseLocTuple=" + baseLocTuple); Set keySet = callerMapLocToCompLoc.keySet(); for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { Location key = (Location) iterator.next(); CompositeLocation callerCompLoc = callerMapLocToCompLoc.get(key); if (!key.getDescriptor().equals(mdCaller)) { - System.out.println("--- caller key=" + key + " callerCompLoc=" + callerCompLoc); + // System.out.println("--- caller key=" + key + " callerCompLoc=" + callerCompLoc); // && callerCompLoc.getTuple().startsWith(baseLocTuple)) { // need to translate to the callee side @@ -566,55 +576,6 @@ public class LocationInference { } - private void constructGlobalFlowGraph() { - - System.out.println(""); - LinkedList methodDescList = - (LinkedList) toanalyze_methodDescList.clone(); - - System.out.println("@@@methodDescList=" + methodDescList); - // System.exit(0); - - while (!methodDescList.isEmpty()) { - MethodDescriptor md = methodDescList.removeLast(); - if (state.SSJAVADEBUG) { - System.out.println(); - System.out.println("SSJAVA: Constructing a global flow graph: " + md); - - FlowGraph flowGraph = getFlowGraph(md); - FlowGraph subGlobalFlowGraph = flowGraph.clone(); - - // mapMethodDescriptorToSubGlobalFlowGraph.put(md, subGlobalFlowGraph); - - // addValueFlowsFromCalleeSubGlobalFlowGraph(md, subGlobalFlowGraph); - - // try { - // subGlobalFlowGraph.writeGraph("_SUBGLOBAL"); - // } catch (IOException e) { - // e.printStackTrace(); - // } - // FlowGraph fg = new FlowGraph(md, mapParamDescToIdx); - // mapMethodDescriptorToFlowGraph.put(md, fg); - // analyzeMethodBody(md.getClassDesc(), md); - } - - } - - // DEBUG: write a global flow graph - MethodDescriptor mdContainingSSJavaLoop = ssjava.getMethodContainingSSJavaLoop(); - // FlowGraph globalFlowGraph = - // getSubGlobalFlowGraph(mdContainingSSJavaLoop); - // System.out.println("GLOBAL NODE SET=" + globalFlowGraph.getNodeSet()); - // assignCompositeLocation(globalFlowGraph); - // try { - // globalFlowGraph.writeGraph("_GLOBAL"); - // } catch (IOException e) { - // e.printStackTrace(); - // } - // _debug_printGraph(); - - } - private void calculateGlobalValueFlowCompositeLocation() { System.out.println("SSJAVA: Calculate composite locations in the global value flow graph"); @@ -1004,8 +965,8 @@ public class LocationInference { // assumes that we don't need to propagate callee flows to the argument // which is literal. - System.out.println("---translateToCallerLocTuple=" + min.printNode(0) - + " callee nodeLocTuple=" + nodeLocTuple); + // System.out.println("---translateToCallerLocTuple=" + min.printNode(0) + // + " callee nodeLocTuple=" + nodeLocTuple); FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); @@ -1266,6 +1227,9 @@ public class LocationInference { // } System.out.println("-paramIdx=" + paramIdx + " infer=" + inferredCompLoc); System.out.println("-flowNode inferLoc=" + flowNode.getCompositeLocation()); + + Descriptor localVarDesc = flowNode.getDescTuple().get(0); + methodSummary.addMapVarNameToInferCompLoc(localVarDesc, inferredCompLoc); methodSummary.addMapParamIdxToInferLoc(paramIdx, inferredCompLoc); } @@ -1852,17 +1816,17 @@ public class LocationInference { if (desc instanceof MethodDescriptor) { TypeDescriptor returnType = ((MethodDescriptor) desc).getReturnType(); - MethodLocationInfo methodLocInfo = getMethodLocationInfo((MethodDescriptor) desc); + MethodSummary methodSummary = getMethodSummary((MethodDescriptor) desc); if (returnType != null && (!returnType.isVoid())) { rtr += - "\n@RETURNLOC(\"" + generateLocationAnnoatation(methodLocInfo.getReturnLoc()) + "\")"; + "\n@RETURNLOC(\"" + generateLocationAnnoatation(methodSummary.getRETURNLoc()) + "\")"; } rtr += "\n@THISLOC(\"this\")"; rtr += "\n@GLOBALLOC(\"GLOBALLOC\")"; - CompositeLocation pcLoc = methodLocInfo.getPCLoc(); + CompositeLocation pcLoc = methodSummary.getPCLoc(); if ((pcLoc != null) && (!pcLoc.get(0).isTop())) { rtr += "\n@PCLOC(\"" + generateLocationAnnoatation(pcLoc) + "\")"; } @@ -1911,18 +1875,21 @@ public class LocationInference { sourceVec.set(classDefLine, annoatedSrc); // generate annotations for field declarations - LocationInfo fieldLocInfo = getLocationInfo(cd); - Map inferLocMap = fieldLocInfo.getMapDescToInferLocation(); + LocationSummary fieldLocSummary = getLocationSummary(cd); + // Map inferLocMap = fieldLocInfo.getMapDescToInferLocation(); + Map mapFieldNameToLocName = fieldLocSummary.getMapHNodeNameToLocationName(); for (Iterator iter = cd.getFields(); iter.hasNext();) { FieldDescriptor fd = (FieldDescriptor) iter.next(); String locAnnotationStr; - CompositeLocation inferLoc = inferLocMap.get(fd); + // CompositeLocation inferLoc = inferLocMap.get(fd); + String locName = mapFieldNameToLocName.get(fd.getSymbol()); - if (inferLoc != null) { + if (locName != null) { // infer loc is null if the corresponding field is static and final - locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")"; + // locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")"; + locAnnotationStr = "@LOC(\"" + locName + "\")"; int fdLineNum = fd.getLineNum(); String orgFieldDeclarationStr = sourceVec.get(fdLineNum); String fieldDeclaration = fd.toString(); @@ -1945,17 +1912,25 @@ public class LocationInference { int methodDefLine = md.getLineNum(); - MethodLocationInfo methodLocInfo = getMethodLocationInfo(md); + // MethodLocationInfo methodLocInfo = getMethodLocationInfo(md); + // Map methodInferLocMap = + // methodLocInfo.getMapDescToInferLocation(); + + MethodSummary methodSummary = getMethodSummary(md); + + Map mapVarDescToInferLoc = + methodSummary.getMapVarDescToInferCompositeLocation(); + System.out.println("-----md=" + md); + System.out.println("-----mapVarDescToInferLoc=" + mapVarDescToInferLoc); - Map methodInferLocMap = - methodLocInfo.getMapDescToInferLocation(); - Set localVarDescSet = methodInferLocMap.keySet(); + Set localVarDescSet = mapVarDescToInferLoc.keySet(); Set localLocElementSet = methodLattice.getElementSet(); for (Iterator iterator = localVarDescSet.iterator(); iterator.hasNext();) { Descriptor localVarDesc = (Descriptor) iterator.next(); - CompositeLocation inferLoc = methodInferLocMap.get(localVarDesc); + System.out.println("-------localVarDesc=" + localVarDesc); + CompositeLocation inferLoc = mapVarDescToInferLoc.get(localVarDesc); String localLocIdentifier = inferLoc.get(0).getLocIdentifier(); if (!localLocElementSet.contains(localLocIdentifier)) { @@ -2056,6 +2031,7 @@ public class LocationInference { } private String generateLocationAnnoatation(CompositeLocation loc) { + System.out.println("loc=" + loc); String rtr = ""; // method location Location methodLoc = loc.get(0); @@ -2177,22 +2153,12 @@ public class LocationInference { LinkedList descriptorListToAnalyze = ssjava.getSortedDescriptors(); for (Iterator iterator = descriptorListToAnalyze.iterator(); iterator.hasNext();) { MethodDescriptor md = (MethodDescriptor) iterator.next(); - calculateExtraLocations(md); - } - } - - private void calculateExtraLocations2() { - LinkedList descriptorListToAnalyze = ssjava.getSortedDescriptors(); - for (Iterator iterator = descriptorListToAnalyze.iterator(); iterator.hasNext();) { - MethodDescriptor md = (MethodDescriptor) iterator.next(); - calculateExtraLocations(md); + if (!ssjava.getMethodContainingSSJavaLoop().equals(md)) { + calculateExtraLocations(md); + } } } - private void setMethodLocInfo(MethodDescriptor md, MethodLocationInfo methodInfo) { - mapMethodDescToMethodLocationInfo.put(md, methodInfo); - } - private void checkLatticesOfVirtualMethods(MethodDescriptor md) { if (!md.isStatic()) { @@ -2286,179 +2252,252 @@ public class LocationInference { return desc; } - private void calculateExtraLocations(MethodDescriptor md) { - // calcualte pcloc, returnloc,... - - System.out.println("\nSSJAVA:Calculate extra locations: " + md); - - SSJavaLattice methodLattice = getMethodLattice(md); + private void calcualtePCLOC(MethodDescriptor md) { + System.out.println("#calcualtePCLOC"); MethodSummary methodSummary = getMethodSummary(md); - FlowGraph fg = getFlowGraph(md); - Set nodeSet = fg.getNodeSet(); + Map mapParamToLoc = methodSummary.getMapParamIdxToInferLoc(); - // for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { - // FlowNode flowNode = (FlowNode) iterator.next(); - // if (flowNode.isDeclaratonNode()) { - // CompositeLocation inferLoc = methodInfo.getInferLocation(flowNode.getDescTuple().get(0)); - // String locIdentifier = inferLoc.get(0).getLocIdentifier(); - // if (!methodLattice.containsKey(locIdentifier)) { - // methodLattice.put(locIdentifier); - // } - // } - // } - MethodLocationInfo methodInfo = getMethodLocationInfo(md); + // calculate the initial program counter location + // PC location is higher than location types of parameters which has incoming flows. - Map mapParamToLoc = methodSummary.getMapParamIdxToInferLoc(); - Set paramIdxSet = mapParamToLoc.keySet(); + Set> paramLocTupleHavingInFlowSet = new HashSet>(); - if (!ssjava.getMethodContainingSSJavaLoop().equals(md)) { - // calculate the initial program counter location - // PC location is higher than location types of parameters which has incoming flows. - String pcLocSymbol = "PCLOC"; + int numParams = fg.getNumParameters(); + for (int i = 0; i < numParams; i++) { + FlowNode paramFlowNode = fg.getParamFlowNode(i); + Descriptor prefix = paramFlowNode.getDescTuple().get(0); + + if (fg.getIncomingNodeSetByPrefix(prefix).size() > 0) { + // parameter has in-value flows + NTuple paramDescTuple = paramFlowNode.getCurrentDescTuple(); + NTuple paramLocTuple = translateToLocTuple(md, paramDescTuple); + paramLocTupleHavingInFlowSet.add(paramLocTuple); + } + } + + System.out.println("paramLocTupleHavingInFlowSet=" + paramLocTupleHavingInFlowSet); - Set> paramLocTupleHavingInFlowSet = new HashSet>(); + if (!coversAllParamters(md, fg, paramLocTupleHavingInFlowSet)) { + // if (numParamsWithIncomingValue > 0 && numParamsWithIncomingValue != fg.getNumParameters()) + // { - int numParams = fg.getNumParameters(); - for (int i = 0; i < numParams; i++) { - FlowNode paramFlowNode = fg.getParamFlowNode(i); + // Here, generates a location in the method lattice that is higher than the + // paramLocTupleHavingInFlowSet + NTuple pcLocTuple = + generateLocTupleRelativeTo(md, paramLocTupleHavingInFlowSet, PCLOC); - Descriptor prefix = paramFlowNode.getDescTuple().get(0); + int pcLocTupleIdx = pcLocTuple.size() - 1; + Location pcLoc = pcLocTuple.get(pcLocTupleIdx); + Descriptor pcDesc = pcLoc.getLocDescriptor(); + Descriptor enclosingDesc = pcLocTuple.get(pcLocTupleIdx).getDescriptor(); - // if (fg.getIncomingFlowNodeSet(paramFlowNode).size() > 0) { - if (fg.getIncomingNodeSetByPrefix(prefix).size() > 0) { - // parameter has in-value flows - NTuple paramDescTuple = paramFlowNode.getCurrentDescTuple(); - NTuple paramLocTuple = translateToLocTuple(md, paramDescTuple); + HierarchyGraph hierarchyGraph = getHierarchyGraph(enclosingDesc); + HNode pcNode = hierarchyGraph.getHNode(pcDesc); + pcNode.setSkeleton(true); - paramLocTupleHavingInFlowSet.add(paramLocTuple); - // CompositeLocation inferLoc = mapParamToLoc.get(paramIdx); - // paramInFlowSet.add(inferLoc); + for (Iterator iterator = paramLocTupleHavingInFlowSet.iterator(); iterator.hasNext();) { + NTuple paramLocTuple = (NTuple) iterator.next(); + if (paramLocTuple.size() > pcLocTupleIdx) { + Descriptor lowerDesc = paramLocTuple.get(pcLocTupleIdx).getLocDescriptor(); + hierarchyGraph.addEdge(pcDesc, lowerDesc); } } - System.out.println("paramLocTupleHavingInFlowSet=" + paramLocTupleHavingInFlowSet); + System.out.println("pcLoc=" + pcLoc); - int numParamsWithIncomingValue = paramLocTupleHavingInFlowSet.size(); + methodSummary.setPCLoc(new CompositeLocation(pcLocTuple)); + } + } + + private boolean coversAllParamters(MethodDescriptor md, FlowGraph fg, + Set> paramLocTupleHavingInFlowSet) { - if (paramLocTupleHavingInFlowSet.size() > 0 - && numParamsWithIncomingValue == fg.getNumParameters()) { - // If the PC loc is going to be higher than all paramters, we dont' need to do anything + int numParam = fg.getNumParameters(); + int size = paramLocTupleHavingInFlowSet.size(); - // Generates a location in the method lattice that is higher than the - // paramLocTupleHavingInFlowSet - NTuple pcLocTuple = generateLocTupleHigherThan(md, paramLocTupleHavingInFlowSet); + 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. - int pcLocTupleIdx = pcLocTuple.size() - 1; - Location pcLoc = pcLocTuple.get(pcLocTupleIdx); - Descriptor pcDesc = pcLoc.getLocDescriptor(); - Descriptor enclosingDesc = pcLocTuple.get(pcLocTupleIdx).getDescriptor(); + FlowNode thisParamNode = fg.getParamFlowNode(0); + NTuple thisParamLocTuple = + translateToLocTuple(md, thisParamNode.getCurrentDescTuple()); - HierarchyGraph hierarchyGraph = getHierarchyGraph(enclosingDesc); - HNode pcNode = hierarchyGraph.getHNode(pcDesc); - pcNode.setSkeleton(true); + if (!paramLocTupleHavingInFlowSet.contains(thisParamLocTuple)) { for (Iterator iterator = paramLocTupleHavingInFlowSet.iterator(); iterator.hasNext();) { - NTuple paramLocTuple = (NTuple) iterator.next(); - Descriptor lowerDesc = paramLocTuple.get(pcLocTupleIdx).getLocDescriptor(); - hierarchyGraph.addEdge(pcDesc, lowerDesc); + 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; + } else { + return false; } - // calculate a return location - // the return location type is lower than all parameters and location - // types of return values + } + + private void calculateRETURNLOC(MethodDescriptor md) { + + System.out.println("#calculateRETURNLOC"); + // calculate a return location: + // the return location type is lower than all parameters and the location of return values + + MethodSummary methodSummary = getMethodSummary(md); + + FlowGraph fg = getFlowGraph(md); + + Map mapParamToLoc = methodSummary.getMapParamIdxToInferLoc(); + Set paramIdxSet = mapParamToLoc.keySet(); + if (!md.getReturnType().isVoid()) { // first, generate the set of return value location types that starts // with 'this' reference - Set inferFieldReturnLocSet = new HashSet(); + Set> inferFieldReturnLocSet = new HashSet>(); Set paramFlowNodeFlowingToReturnValueSet = getParamNodeFlowingToReturnValue(md); - Set inferParamLocSet = new HashSet(); + System.out.println("paramFlowNodeFlowingToReturnValueSet=" + + paramFlowNodeFlowingToReturnValueSet); + + Set> locFlowingToReturnValueSet = new HashSet>(); for (Iterator iterator = paramFlowNodeFlowingToReturnValueSet.iterator(); iterator.hasNext();) { FlowNode fn = (FlowNode) iterator.next(); - CompositeLocation inferLoc = - generateInferredCompositeLocation(methodInfo, getFlowGraph(md).getLocationTuple(fn)); - inferParamLocSet.add(inferLoc); + + NTuple paramDescTuple = fn.getCurrentDescTuple(); + NTuple paramLocTuple = translateToLocTuple(md, paramDescTuple); + + locFlowingToReturnValueSet.add(paramLocTuple); } Set returnNodeSet = fg.getReturnNodeSet(); - - skip: for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { + for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { FlowNode returnNode = (FlowNode) iterator.next(); - CompositeLocation inferReturnLoc = - generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode)); - if (inferReturnLoc.get(0).getLocIdentifier().equals("this")) { - // if the location type of the return value matches "this" reference - // then, check whether this return value is equal to/lower than all - // of parameters that possibly flow into the return values - for (Iterator iterator2 = inferParamLocSet.iterator(); iterator2.hasNext();) { - CompositeLocation paramInferLoc = (CompositeLocation) iterator2.next(); + NTuple returnDescTuple = returnNode.getCurrentDescTuple(); + NTuple returnLocTuple = translateToLocTuple(md, returnDescTuple); + locFlowingToReturnValueSet.add(returnLocTuple); + } + System.out.println("locFlowingToReturnValueSet=" + locFlowingToReturnValueSet); - if ((!paramInferLoc.equals(inferReturnLoc)) - && !isGreaterThan(methodLattice, paramInferLoc, inferReturnLoc)) { - continue skip; - } - } - inferFieldReturnLocSet.add(inferReturnLoc); + // Here, generates a return location in the method lattice that is lower than the + // locFlowingToReturnValueSet + NTuple returnLocTuple = + generateLocTupleRelativeTo(md, locFlowingToReturnValueSet, RLOC); - } - } + System.out.println("returnLocTuple=" + returnLocTuple); - if (inferFieldReturnLocSet.size() > 0) { + int returnLocTupleIdx = returnLocTuple.size() - 1; + Location returnLoc = returnLocTuple.get(returnLocTupleIdx); + Descriptor returnDesc = returnLoc.getLocDescriptor(); + Descriptor enclosingDesc = returnLocTuple.get(returnLocTupleIdx).getDescriptor(); - CompositeLocation returnLoc = getLowest(methodLattice, inferFieldReturnLocSet); - if (returnLoc == null) { - // in this case, assign <'this',bottom> to the RETURNLOC - returnLoc = new CompositeLocation(new Location(md, md.getThis().getSymbol())); - returnLoc.addLocation(new Location(md.getClassDesc(), getLattice(md.getClassDesc()) - .getBottomItem())); - } - methodInfo.setReturnLoc(returnLoc); + HierarchyGraph hierarchyGraph = getHierarchyGraph(enclosingDesc); + HNode returnNode = hierarchyGraph.getHNode(returnDesc); + returnNode.setSkeleton(true); - } else { - String returnLocSymbol = "RETURNLOC"; - CompositeLocation returnLocInferLoc = - new CompositeLocation(new Location(md, returnLocSymbol)); - methodInfo.setReturnLoc(returnLocInferLoc); + for (Iterator iterator = locFlowingToReturnValueSet.iterator(); iterator.hasNext();) { + NTuple locTuple = (NTuple) iterator.next(); + Descriptor higherDesc = locTuple.get(returnLocTupleIdx).getLocDescriptor(); + hierarchyGraph.addEdge(higherDesc, returnDesc); + } - for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) { - Integer paramIdx = (Integer) iterator.next(); - CompositeLocation inferLoc = mapParamToLoc.get(paramIdx); - String paramLocLocalSymbol = inferLoc.get(0).getLocIdentifier(); - if (!methodLattice.isGreaterThan(paramLocLocalSymbol, returnLocSymbol)) { - // TODO - // addRelationHigherToLower(methodLattice, methodInfo, - // paramLocLocalSymbol, - // returnLocSymbol); - } - } + methodSummary.setRETURNLoc(new CompositeLocation(returnLocTuple)); - for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { - FlowNode returnNode = (FlowNode) iterator.next(); - CompositeLocation inferLoc = - generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode)); - if (!isGreaterThan(methodLattice, inferLoc, returnLocInferLoc)) { - // TODO - // addRelation(methodLattice, methodInfo, inferLoc, - // returnLocInferLoc); - } - } + // skip: for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { + // FlowNode returnNode = (FlowNode) iterator.next(); + // + // NTuple returnDescTuple = returnNode.getCurrentDescTuple(); + // NTuple returnLocTuple = translateToLocTuple(md, returnDescTuple); + // + // if (returnLocTuple.get(0).getLocDescriptor().equals(md.getThis())) { + // // if the location type of the return value matches "this" reference + // // then, check whether this return value is equal to/lower than all + // // of parameters that possibly flow into the return values + // for (Iterator iterator2 = inferParamLocSet.iterator(); iterator2.hasNext();) { + // CompositeLocation paramInferLoc = (CompositeLocation) iterator2.next(); + // + // if ((!paramInferLoc.equals(returnLocTuple)) + // && !isGreaterThan(methodLattice, paramInferLoc, inferReturnLoc)) { + // continue skip; + // } + // } + // inferFieldReturnLocSet.add(returnLocTuple); + // + // } + // } - } + // if (inferFieldReturnLocSet.size() > 0) { + // + // // CompositeLocation returnLoc = getLowest(methodLattice, inferFieldReturnLocSet); + // CompositeLocation returnLoc = null; + // if (returnLoc == null) { + // // in this case, assign <'this',bottom> to the RETURNLOC + // returnLoc = new CompositeLocation(new Location(md, md.getThis().getSymbol())); + // returnLoc.addLocation(new Location(md.getClassDesc(), getLattice(md.getClassDesc()) + // .getBottomItem())); + // } + // methodInfo.setReturnLoc(returnLoc); + // + // } else { + // String returnLocSymbol = "RETURNLOC"; + // CompositeLocation returnLocInferLoc = + // new CompositeLocation(new Location(md, returnLocSymbol)); + // methodInfo.setReturnLoc(returnLocInferLoc); + // + // for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) { + // Integer paramIdx = (Integer) iterator.next(); + // CompositeLocation inferLoc = mapParamToLoc.get(paramIdx); + // String paramLocLocalSymbol = inferLoc.get(0).getLocIdentifier(); + // if (!methodLattice.isGreaterThan(paramLocLocalSymbol, returnLocSymbol)) { + // // TODO + // // addRelationHigherToLower(methodLattice, methodInfo, + // // paramLocLocalSymbol, + // // returnLocSymbol); + // } + // } + // + // for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { + // FlowNode returnNode = (FlowNode) iterator.next(); + // CompositeLocation inferLoc = + // generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode)); + // if (!isGreaterThan(methodLattice, inferLoc, returnLocInferLoc)) { + // // TODO + // // addRelation(methodLattice, methodInfo, inferLoc, + // // returnLocInferLoc); + // } + // } + // + // } } } - private NTuple generateLocTupleHigherThan(MethodDescriptor md, - Set> paramLocTupleHavingInFlowSet) { + private void calculateExtraLocations(MethodDescriptor md) { + // calcualte pcloc, returnloc,... + + System.out.println("\nSSJAVA:Calculate PCLOC/RETURNLOC locations: " + md); + + calcualtePCLOC(md); + calculateRETURNLOC(md); + + } + + private NTuple generateLocTupleRelativeTo(MethodDescriptor md, + Set> paramLocTupleHavingInFlowSet, String locNamePrefix) { - System.out.println("-generateLocTupleHigherThan=" + paramLocTupleHavingInFlowSet); + System.out.println("-generateLocTupleRelativeTo=" + paramLocTupleHavingInFlowSet); NTuple higherLocTuple = new NTuple(); @@ -2466,7 +2505,7 @@ public class LocationInference { // check if all paramter loc tuple is started with 'this' reference boolean hasParamNotStartedWithThisRef = false; - int maxSize = 0; + int minSize = 0; Set> paramLocTupleStartedWithThis = new HashSet>(); @@ -2476,28 +2515,31 @@ public class LocationInference { hasParamNotStartedWithThisRef = true; } else if (paramLocTuple.size() > 1) { paramLocTupleStartedWithThis.add(paramLocTuple); - if (maxSize < paramLocTuple.size()) { - maxSize = paramLocTuple.size(); + if (minSize == 0 || minSize > paramLocTuple.size()) { + minSize = paramLocTuple.size(); } } } + System.out.println("---paramLocTupleStartedWithThis=" + paramLocTupleStartedWithThis); Descriptor enclosingDesc = md; if (hasParamNotStartedWithThisRef) { // in this case, PCLOC will be the local location } else { // all parameter is started with 'this', so PCLOC will be set relative to the composite // location started with 'this'. - for (int idx = 0; idx < maxSize - 1; idx++) { + for (int idx = 0; idx < minSize - 1; idx++) { Set locDescSet = new HashSet(); Location curLoc = null; - for (Iterator iterator = paramLocTupleHavingInFlowSet.iterator(); iterator.hasNext();) { - NTuple paramLocTuple = (NTuple) iterator.next(); + NTuple paramLocTuple = null; + for (Iterator iterator = paramLocTupleStartedWithThis.iterator(); iterator.hasNext();) { + paramLocTuple = (NTuple) iterator.next(); + System.out.println("-----paramLocTuple=" + paramLocTuple + " idx=" + idx); curLoc = paramLocTuple.get(idx); Descriptor locDesc = curLoc.getLocDescriptor(); locDescSet.add(locDesc); } - System.out.println("locDescSet=" + locDescSet + " idx=" + idx); + System.out.println("-----locDescSet=" + locDescSet + " idx=" + idx); if (locDescSet.size() != 1) { break; } @@ -2508,12 +2550,12 @@ public class LocationInference { } - String pcLocIdentifier = PCLOC + (locSeed++); + String pcLocIdentifier = locNamePrefix + (locSeed++); NameDescriptor pcLocDesc = new NameDescriptor(pcLocIdentifier); Location newLoc = new Location(enclosingDesc, pcLocDesc); higherLocTuple.add(newLoc); - System.out.println("---higherLocTuple=" + higherLocTuple); + System.out.println("---new loc tuple=" + higherLocTuple); return higherLocTuple; @@ -2523,9 +2565,17 @@ public class LocationInference { if (in instanceof VarDescriptor) { return ((VarDescriptor) in).getType().getClassDesc(); - } else {/* if (desc instanceof FieldDescriptor) { */ + } else if (in instanceof FieldDescriptor) { return ((FieldDescriptor) in).getType().getClassDesc(); } + // else if (in instanceof LocationDescriptor) { + // // here is the case that the descriptor 'in' is the last element of the assigned composite + // // location + // return ((VarDescriptor) locTuple.get(0).getLocDescriptor()).getType().getClassDesc(); + // } + else { + return null; + } } @@ -4286,6 +4336,8 @@ public class LocationInference { FlowGraph calleeFlowGraph = getFlowGraph(calleeMethodDesc); Set calleeReturnSet = calleeFlowGraph.getReturnNodeSet(); + System.out.println("-calleeReturnSet=" + calleeReturnSet); + if (min.getExpression() != null) { NodeTupleSet baseNodeSet = new NodeTupleSet(); @@ -4361,6 +4413,9 @@ public class LocationInference { addArgIdxMap(min, idx, argTuple); FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx); + System.out.println("-paramNode=" + paramNode + " hasInFlowTo=" + + hasInFlowTo(calleeFlowGraph, paramNode, calleeReturnSet)); + if (hasInFlowTo(calleeFlowGraph, paramNode, calleeReturnSet) || calleeMethodDesc.getModifiers().isNative()) { addParamNodeFlowingToReturnValue(calleeMethodDesc, paramNode); diff --git a/Robust/src/Analysis/SSJava/LocationSummary.java b/Robust/src/Analysis/SSJava/LocationSummary.java index c46100bc..4682b231 100644 --- a/Robust/src/Analysis/SSJava/LocationSummary.java +++ b/Robust/src/Analysis/SSJava/LocationSummary.java @@ -12,6 +12,7 @@ public abstract class LocationSummary { } public void addMapHNodeNameToLocationName(String nodeName, String locName) { + System.out.println("nodeName="+nodeName+" locName="+locName); mapHNodeNameToLocationName.put(nodeName, locName); } diff --git a/Robust/src/Analysis/SSJava/MethodSummary.java b/Robust/src/Analysis/SSJava/MethodSummary.java index 63f4b99e..d2f7916e 100644 --- a/Robust/src/Analysis/SSJava/MethodSummary.java +++ b/Robust/src/Analysis/SSJava/MethodSummary.java @@ -17,15 +17,35 @@ public class MethodSummary extends LocationSummary { CompositeLocation returnLoc; Map mapParamIdxToInferLoc; - Map mapDescToInferCompositeLocation; + Map mapVarDescToInferCompositeLocation; public MethodSummary(MethodDescriptor md) { this.md = md; this.pcLoc = new CompositeLocation(new Location(md, Location.TOP)); this.mapParamIdxToInferLoc = new HashMap(); + this.mapVarDescToInferCompositeLocation = new HashMap(); this.thisLocName = "this"; } + public Map getMapVarDescToInferCompositeLocation() { + return mapVarDescToInferCompositeLocation; + } + + public void addMapVarNameToInferCompLoc(Descriptor varDesc, CompositeLocation inferLoc) { + mapVarDescToInferCompositeLocation.put(varDesc, inferLoc); + } + + public CompositeLocation getInferLocation(Descriptor varDesc) { + return mapVarDescToInferCompositeLocation.get(varDesc); + // if (mapVarNameToInferCompositeLocation.containsKey(varName)) { + // // it already has a composite location assignment. + // return mapVarNameToInferCompositeLocation.get(varName); + // } else { + // String locName = getLocationName(varName); + // return new CompositeLocation(new Location(md, locName)); + // } + } + public void addMapParamIdxToInferLoc(int paramIdx, CompositeLocation inferLoc) { mapParamIdxToInferLoc.put(paramIdx, inferLoc); } @@ -38,4 +58,16 @@ public class MethodSummary extends LocationSummary { this.pcLoc = pcLoc; } + public CompositeLocation getPCLoc() { + return pcLoc; + } + + public void setRETURNLoc(CompositeLocation returnLoc) { + this.returnLoc = returnLoc; + } + + public CompositeLocation getRETURNLoc() { + return returnLoc; + } + } diff --git a/Robust/src/Analysis/SSJava/SSJavaLattice.java b/Robust/src/Analysis/SSJava/SSJavaLattice.java index 0ca550a0..c9ab0aa1 100644 --- a/Robust/src/Analysis/SSJava/SSJavaLattice.java +++ b/Robust/src/Analysis/SSJava/SSJavaLattice.java @@ -320,8 +320,8 @@ public class SSJavaLattice extends Lattice { } public void insertNewLocationBetween(T higher, Set lowerSet, T newLoc) { - System.out.println("---insert new location=" + newLoc + " between=" + higher + "<->" - + lowerSet); + // System.out.println("---insert new location=" + newLoc + " between=" + higher + "<->" + // + lowerSet); Set connectedSet = get(higher); if (connectedSet == null) { connectedSet = new HashSet();