From: yeom Date: Thu, 11 Oct 2012 02:11:19 +0000 (+0000) Subject: changes. X-Git-Url: http://plrg.eecs.uci.edu/git/?p=IRC.git;a=commitdiff_plain;h=75ee5e21119b65f10cf603d29ee261674cd05a9a changes. --- diff --git a/Robust/src/Analysis/SSJava/BuildLattice.java b/Robust/src/Analysis/SSJava/BuildLattice.java index 52a2bf9c..bbef531a 100644 --- a/Robust/src/Analysis/SSJava/BuildLattice.java +++ b/Robust/src/Analysis/SSJava/BuildLattice.java @@ -119,9 +119,10 @@ public class BuildLattice { Map mapIntermediateLoc = new HashMap(); - for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { HNode node = (HNode) iterator.next(); + System.out.println("-node=" + node); + if (node.isSkeleton() && (!visited.contains(node))) { visited.add(node); @@ -132,30 +133,29 @@ public class BuildLattice { if (!outNode.isSkeleton()) { if (outNode.isCombinationNode()) { // expand the combination node 'outNode' - System.out.println("-COMBINATION NODE=" + outNode); // here we need to expand the corresponding combination location in the lattice HNode combinationNodeInSCGraph = getCombinationNodeInSCGraph(desc, outNode); Set combineSkeletonNodeSet = simpleGraph.getCombineSetByCombinationNode(outNode); - System.out.println("combineSkeletonNodeSet=" + combineSkeletonNodeSet); + // System.out.println("combineSkeletonNodeSet=" + combineSkeletonNodeSet); Set combinationNodeSet = simpleGraph.getCombinationNodeSetByCombineNodeSet(combineSkeletonNodeSet); - System.out.println("combinationNodeSet=" + combinationNodeSet); + // System.out.println("combinationNodeSet=" + combinationNodeSet); Set endNodeSetFromSimpleGraph = simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(outNode, combinationNodeSet); - System.out.println("-endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph); + // System.out.println("-endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph); 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); + // System.out.println("-endCombNodeSet=" + endCombNodeSet); visited.add(outNode); // follows the straight line up to another skeleton/combination node @@ -170,7 +170,7 @@ public class BuildLattice { } 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,8 +185,8 @@ 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(); @@ -207,21 +207,58 @@ public class BuildLattice { } } else if (!node.isSkeleton() && !node.isCombinationNode() && !node.isMergeNode() && !visited.contains(node)) { + // an intermediate node 'node' may be located between "TOP" location and a skeleton node - // but there is no such a case. + Set outNodeSet = + simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(node, null); // Set outNodeSet = simpleGraph.getOutgoingNodeSet(node); - // Set belowSkeletonLocNameSet = new HashSet(); - // for (Iterator iterator2 = outNodeSet.iterator(); iterator2.hasNext();) { - // HNode outNode = (HNode) iterator2.next(); - // if (outNode.isSkeleton()) { - // belowSkeletonLocNameSet.add(scGraph.getCurrentHNode(outNode).getName()); - // } + System.out.println("this case? node=" + node + " outNodeSet=" + outNodeSet); + + Set belowSkeletonLocNameSet = new HashSet(); + Set belowSCNodeSet = new HashSet(); + + 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); + } + + // 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); + // } + + } + // else { + // System.out.println("---LocName=" + newLocName); + // lattice.put(newLocName); // } - // String newLocName = "ILOC" + (seed++); - // lattice.insertNewLocationBetween(lattice.getTopItem(), belowSkeletonLocNameSet, - // newLocName); - // locSummary.addMapHNodeNameToLocationName(node.getName(), newLocName); } } @@ -246,12 +283,13 @@ public class BuildLattice { } else { HNode newEndNode = getDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, endNode); - System.out.println("#### old END NODE=" + endNode + " --->" + newEndNode); + // System.out.println("#### old END NODE=" + endNode + " --->" + newEndNode); newEndNodeSet.add(newEndNode); } } - System.out.println("removeTransitivelyReachToNode=" + endNodeSet + " newSet=" + newEndNodeSet); + // System.out.println("removeTransitivelyReachToNode=" + endNodeSet + " newSet=" + + // newEndNodeSet); return newEndNodeSet; @@ -273,7 +311,7 @@ public class BuildLattice { if (inNode.equals(startNode)) { connected.add(curNode); } else { - System.out.println("inNode=" + inNode); + // System.out.println("inNode=" + inNode); recurDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, inNode, connected); } } @@ -285,7 +323,7 @@ public class BuildLattice { int idx, LocationSummary locSummary, HNode curNode) { TripleItem item = new TripleItem(startNode, endNodeSet, idx); - System.out.println("item=" + item); + // System.out.println("item=" + item); if (!mapIntermediateLoc.containsKey(item)) { // need to create a new intermediate location in the lattice String newLocName = "ILOC" + (seed++); @@ -358,8 +396,8 @@ public class BuildLattice { String locName = mapIntermediateLoc.get(item); locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName); - System.out.println("-TripleItem=" + item); - System.out.println("-curNode=" + curNode.getName() + " locName=" + locName); + // System.out.println("-TripleItem=" + item); + // System.out.println("-curNode=" + curNode.getName() + " locName=" + locName); HierarchyGraph graph = infer.getSimpleHierarchyGraph(desc); Set outSet = graph.getOutgoingNodeSet(curNode); @@ -444,7 +482,7 @@ public class BuildLattice { resetCount(mapFtoCount, family); } - System.out.println("mapImSucc=" + mapImSucc); + // System.out.println("mapImSucc=" + mapImSucc); return mapImSucc; } @@ -509,8 +547,8 @@ public class BuildLattice { private void debug_print(HierarchyGraph inputGraph) { System.out.println("\nBuild Lattice:" + inputGraph.getName()); - System.out.println("Node2Index:\n" + inputGraph.getMapHNodeToUniqueIndex()); - System.out.println("Node2Basis:\n" + inputGraph.getMapHNodeToBasis()); + // System.out.println("Node2Index:\n" + inputGraph.getMapHNodeToUniqueIndex()); + // System.out.println("Node2Basis:\n" + inputGraph.getMapHNodeToBasis()); } } @@ -554,14 +592,21 @@ class TripleItem { } public int hashCode() { - return higherNode.hashCode() + lowerNodeSet.hashCode() + idx; + + int h = 0; + if (higherNode != null) { + h = higherNode.hashCode(); + } + + return h + lowerNodeSet.hashCode() + idx; } public boolean equals(Object obj) { if (obj instanceof TripleItem) { TripleItem in = (TripleItem) obj; - if (higherNode.equals(in.higherNode) && lowerNodeSet.equals(in.lowerNodeSet) && idx == in.idx) { + if ((higherNode == null || (higherNode != null && higherNode.equals(in.higherNode))) + && lowerNodeSet.equals(in.lowerNodeSet) && idx == in.idx) { return true; } } diff --git a/Robust/src/Analysis/SSJava/FlowGraph.java b/Robust/src/Analysis/SSJava/FlowGraph.java index ded08373..d0a854b8 100644 --- a/Robust/src/Analysis/SSJava/FlowGraph.java +++ b/Robust/src/Analysis/SSJava/FlowGraph.java @@ -22,6 +22,7 @@ public class FlowGraph { Set returnNodeSet; FlowNode thisVarNode; + Map> mapFlowNodeToInEdgeSet; Map> mapFlowNodeToOutEdgeSet; Map, FlowNode> mapLocTupleToFlowNode; @@ -50,6 +51,7 @@ public class FlowGraph { this.returnNodeSet = new HashSet(); this.mapIdxToFlowNode = new HashMap(); this.mapFlowNodeToOutEdgeSet = new HashMap>(); + this.mapFlowNodeToInEdgeSet = new HashMap>(); if (!md.isStatic()) { // create a node for 'this' varialbe @@ -217,6 +219,13 @@ public class FlowGraph { return mapFlowNodeToOutEdgeSet.get(node); } + public Set getInEdgeSet(FlowNode node) { + if (!mapFlowNodeToInEdgeSet.containsKey(node)) { + mapFlowNodeToInEdgeSet.put(node, new HashSet()); + } + return mapFlowNodeToInEdgeSet.get(node); + } + public void addValueFlowEdge(NTuple fromDescTuple, NTuple toDescTuple) { FlowNode fromNode = getFlowNode(fromDescTuple); @@ -261,10 +270,15 @@ public class FlowGraph { FlowEdge edge = new FlowEdge(fromNode, toNode, initTuple, endTuple); addOutEdge(fromNode, edge); + addInEdge(toNode, edge); // System.out.println("add a new edge=" + edge); } + private void addInEdge(FlowNode toNode, FlowEdge edge) { + getInEdgeSet(toNode).add(edge); + } + private void addOutEdge(FlowNode fromNode, FlowEdge edge) { if (!mapFlowNodeToOutEdgeSet.containsKey(fromNode)) { mapFlowNodeToOutEdgeSet.put(fromNode, new HashSet()); @@ -590,6 +604,46 @@ public class FlowGraph { return mapFlowNodeToOutEdgeSet; } + public Set getIncomingNodeSetByPrefix(Descriptor prefix) { + + Set incomingNodeSet = new HashSet(); + + for (Iterator iterator = getNodeSet().iterator(); iterator.hasNext();) { + FlowNode curNode = (FlowNode) iterator.next(); + Set outEdgeSet = getOutEdgeSet(curNode); + + for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) { + FlowEdge outEdge = (FlowEdge) iterator2.next(); + + if (outEdge.getEndTuple().startsWith(prefix)) { + incomingNodeSet.add(curNode); + recurIncomingNodeSetByPrefix(prefix, curNode, incomingNodeSet); + + } + + } + } + + return incomingNodeSet; + + } + + private void recurIncomingNodeSetByPrefix(Descriptor prefix, FlowNode node, Set visited) { + + Set inEdgeSet = getInEdgeSet(node); + + for (Iterator iterator = inEdgeSet.iterator(); iterator.hasNext();) { + FlowEdge inEdge = (FlowEdge) iterator.next(); + + FlowNode inNode = getFlowNode(inEdge.getInitTuple()); + if (!inEdge.getInitTuple().startsWith(prefix) && !visited.contains(inNode)) { + visited.add(inNode); + recurIncomingNodeSetByPrefix(prefix, inNode, visited); + } + } + + } + public void setMapFlowNodeToOutEdgeSet(Map> inMap) { Set keySet = inMap.keySet(); for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { @@ -712,5 +766,4 @@ public class FlowGraph { bw.write("}\n"); } - } \ No newline at end of file diff --git a/Robust/src/Analysis/SSJava/HierarchyGraph.java b/Robust/src/Analysis/SSJava/HierarchyGraph.java index 852206af..5b0b85f2 100644 --- a/Robust/src/Analysis/SSJava/HierarchyGraph.java +++ b/Robust/src/Analysis/SSJava/HierarchyGraph.java @@ -1098,4 +1098,32 @@ public class HierarchyGraph { } bw.write(node.getName() + " [label=\"" + nodeName + "\"]" + ";\n"); } + + public int countHopFromTopLocation(HNode node) { + + Set inNodeSet = getIncomingNodeSet(node); + int count = 0; + if (inNodeSet.size() > 0) { + count = recurCountHopFromTopLocation(inNodeSet, 1); + } + + return count; + } + + private int recurCountHopFromTopLocation(Set nodeSet, int curCount) { + + int max = curCount; + for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + HNode node = (HNode) iterator.next(); + Set inNodeSet = getIncomingNodeSet(node); + if (inNodeSet.size() > 0) { + int recurCount = recurCountHopFromTopLocation(inNodeSet, curCount + 1); + if (max < recurCount) { + max = recurCount; + } + } + } + return max; + } + } diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index 26bd8c29..4cca1c49 100644 --- a/Robust/src/Analysis/SSJava/LocationInference.java +++ b/Robust/src/Analysis/SSJava/LocationInference.java @@ -124,6 +124,8 @@ public class LocationInference { public static final String INTERLOC = "INTERLOC"; + public static final String PCLOC = "PCLOC"; + public static final Descriptor GLOBALDESC = new NameDescriptor(GLOBALLOC); public static final Descriptor TOPDESC = new NameDescriptor(TOPLOC); @@ -228,6 +230,9 @@ public class LocationInference { debug_writeHierarchyDotFiles(); + // calculate RETURNLOC,PCLOC + calculateExtraLocations(); + simplifyHierarchyGraph(); debug_writeSimpleHierarchyDotFiles(); @@ -240,21 +245,23 @@ public class LocationInference { debug_writeSkeletonCombinationHierarchyDotFiles(); + // System.exit(0); + buildLattice(); debug_writeLattices(); + updateCompositeLocationAssignments(); + generateMethodSummary(); System.exit(0); // 2) construct lattices - inferLattices(); - + // inferLattices(); // simplifyLattices(); - // 3) check properties - checkLattices(); + // checkLattices(); // calculate RETURNLOC,PCLOC calculateExtraLocations(); @@ -285,14 +292,55 @@ public class LocationInference { private void assignCompositeLocation() { calculateGlobalValueFlowCompositeLocation(); translateCompositeLocationAssignmentToFlowGraph(); - _debug_printGraph(); } private void translateCompositeLocationAssignmentToFlowGraph() { - MethodDescriptor methodEventLoopDesc = ssjava.getMethodContainingSSJavaLoop(); translateCompositeLocationAssignmentToFlowGraph(methodEventLoopDesc); + _debug_printGraph(); + } + + private void updateCompositeLocationAssignments() { + + LinkedList methodDescList = + (LinkedList) toanalyze_methodDescList.clone(); + while (!methodDescList.isEmpty()) { + MethodDescriptor md = methodDescList.removeLast(); + GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md); + FlowGraph flowGraph = getFlowGraph(md); + + Set nodeSet = flowGraph.getNodeSet(); + for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + FlowNode node = (FlowNode) iterator.next(); + if (node.getCompositeLocation() != null) { + CompositeLocation compLoc = node.getCompositeLocation(); + CompositeLocation updatedCompLoc = updateCompositeLocation(compLoc); + node.setCompositeLocation(updatedCompLoc); + } else { + NTuple descTuple = node.getDescTuple(); + CompositeLocation compLoc = convertToCompositeLocation(md, descTuple); + node.setCompositeLocation(compLoc); + } + } + + } + + } + + private CompositeLocation updateCompositeLocation(CompositeLocation compLoc) { + CompositeLocation updatedCompLoc = new CompositeLocation(); + for (int i = 0; i < compLoc.getSize(); i++) { + Location loc = compLoc.get(i); + String nodeIdentifier = loc.getLocIdentifier(); + Descriptor enclosingDesc = loc.getDescriptor(); + LocationSummary locSummary = getLocationSummary(enclosingDesc); + String locName = locSummary.getLocationName(nodeIdentifier); + Location updatedLoc = new Location(enclosingDesc, locName); + updatedCompLoc.addLocation(updatedLoc); + } + + return updatedCompLoc; } private void translateCompositeLocationAssignmentToFlowGraph(MethodDescriptor mdCaller) { @@ -1203,19 +1251,21 @@ public class LocationInference { for (int paramIdx = 0; paramIdx < flowGraph.getNumParameters(); paramIdx++) { FlowNode flowNode = flowGraph.getParamFlowNode(paramIdx); - NTuple descTuple = flowNode.getDescTuple(); - - CompositeLocation assignedCompLoc = flowNode.getCompositeLocation(); - CompositeLocation inferredCompLoc; - if (assignedCompLoc != null) { - inferredCompLoc = translateCompositeLocation(assignedCompLoc); - } else { - Descriptor locDesc = descTuple.get(0); - Location loc = new Location(md, locDesc.getSymbol()); - loc.setLocDescriptor(locDesc); - inferredCompLoc = new CompositeLocation(loc); - } + CompositeLocation inferredCompLoc = flowNode.getCompositeLocation(); + // NTuple descTuple = flowNode.getDescTuple(); + // + // CompositeLocation assignedCompLoc = flowNode.getCompositeLocation(); + // CompositeLocation inferredCompLoc; + // if (assignedCompLoc != null) { + // inferredCompLoc = translateCompositeLocation(assignedCompLoc); + // } else { + // Descriptor locDesc = descTuple.get(0); + // Location loc = new Location(md, locDesc.getSymbol()); + // loc.setLocDescriptor(locDesc); + // inferredCompLoc = new CompositeLocation(loc); + // } System.out.println("-paramIdx=" + paramIdx + " infer=" + inferredCompLoc); + System.out.println("-flowNode inferLoc=" + flowNode.getCompositeLocation()); methodSummary.addMapParamIdxToInferLoc(paramIdx, inferredCompLoc); } @@ -1223,6 +1273,88 @@ public class LocationInference { } + private boolean hasOrderingRelation(NTuple locTuple1, NTuple locTuple2) { + + int size = locTuple1.size() >= locTuple2.size() ? locTuple2.size() : locTuple1.size(); + + for (int idx = 0; idx < size; idx++) { + Location loc1 = locTuple1.get(idx); + Location loc2 = locTuple2.get(idx); + + Descriptor desc1 = loc1.getDescriptor(); + Descriptor desc2 = loc2.getDescriptor(); + + if (!desc1.equals(desc2)) { + throw new Error("Fail to compare " + locTuple1 + " and " + locTuple2); + } + + Descriptor locDesc1 = loc1.getLocDescriptor(); + Descriptor locDesc2 = loc2.getLocDescriptor(); + + HierarchyGraph hierarchyGraph = getHierarchyGraph(desc1); + + HNode node1 = hierarchyGraph.getHNode(locDesc1); + HNode node2 = hierarchyGraph.getHNode(locDesc2); + + System.out.println("---node1=" + node1 + " node2=" + node2); + System.out.println("---hierarchyGraph.getIncomingNodeSet(node2)=" + + hierarchyGraph.getIncomingNodeSet(node2)); + + if (locDesc1.equals(locDesc2)) { + continue; + } else if (!hierarchyGraph.getIncomingNodeSet(node2).contains(node1) + && !hierarchyGraph.getIncomingNodeSet(node1).contains(node2)) { + return false; + } else { + return true; + } + + } + + return false; + + } + + private boolean isHigherThan(NTuple locTuple1, NTuple locTuple2) { + + int size = locTuple1.size() >= locTuple2.size() ? locTuple2.size() : locTuple1.size(); + + for (int idx = 0; idx < size; idx++) { + Location loc1 = locTuple1.get(idx); + Location loc2 = locTuple2.get(idx); + + Descriptor desc1 = loc1.getDescriptor(); + Descriptor desc2 = loc2.getDescriptor(); + + if (!desc1.equals(desc2)) { + throw new Error("Fail to compare " + locTuple1 + " and " + locTuple2); + } + + Descriptor locDesc1 = loc1.getLocDescriptor(); + Descriptor locDesc2 = loc2.getLocDescriptor(); + + HierarchyGraph hierarchyGraph = getHierarchyGraph(desc1); + + HNode node1 = hierarchyGraph.getHNode(locDesc1); + HNode node2 = hierarchyGraph.getHNode(locDesc2); + + System.out.println("---node1=" + node1 + " node2=" + node2); + System.out.println("---hierarchyGraph.getIncomingNodeSet(node2)=" + + hierarchyGraph.getIncomingNodeSet(node2)); + + if (locDesc1.equals(locDesc2)) { + continue; + } else if (hierarchyGraph.getIncomingNodeSet(node2).contains(node1)) { + return true; + } else { + return false; + } + + } + + return false; + } + private CompositeLocation translateCompositeLocation(CompositeLocation compLoc) { CompositeLocation newCompLoc = new CompositeLocation(); @@ -1298,7 +1430,7 @@ public class LocationInference { addMapDescToSimpleLattice(desc, simpleLattice); HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc); - System.out.println("## insertIntermediateNodesToStraightLine:" + System.out.println("\n## insertIntermediateNodesToStraightLine:" + simpleHierarchyGraph.getName()); SSJavaLattice lattice = buildLattice.insertIntermediateNodesToStraightLine(desc, simpleLattice); @@ -2049,6 +2181,14 @@ public class LocationInference { } } + private void calculateExtraLocations2() { + LinkedList descriptorListToAnalyze = ssjava.getSortedDescriptors(); + for (Iterator iterator = descriptorListToAnalyze.iterator(); iterator.hasNext();) { + MethodDescriptor md = (MethodDescriptor) iterator.next(); + calculateExtraLocations(md); + } + } + private void setMethodLocInfo(MethodDescriptor md, MethodLocationInfo methodInfo) { mapMethodDescToMethodLocationInfo.put(md, methodInfo); } @@ -2149,6 +2289,287 @@ public class LocationInference { private void calculateExtraLocations(MethodDescriptor md) { // calcualte pcloc, returnloc,... + System.out.println("\nSSJAVA:Calculate extra locations: " + md); + + SSJavaLattice methodLattice = getMethodLattice(md); + + MethodSummary methodSummary = getMethodSummary(md); + + FlowGraph fg = getFlowGraph(md); + Set nodeSet = fg.getNodeSet(); + + // for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + // FlowNode flowNode = (FlowNode) iterator.next(); + // if (flowNode.isDeclaratonNode()) { + // CompositeLocation inferLoc = methodInfo.getInferLocation(flowNode.getDescTuple().get(0)); + // String locIdentifier = inferLoc.get(0).getLocIdentifier(); + // if (!methodLattice.containsKey(locIdentifier)) { + // methodLattice.put(locIdentifier); + // } + // } + // } + MethodLocationInfo methodInfo = getMethodLocationInfo(md); + + Map mapParamToLoc = methodSummary.getMapParamIdxToInferLoc(); + Set paramIdxSet = mapParamToLoc.keySet(); + + 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"; + + Set> paramLocTupleHavingInFlowSet = new HashSet>(); + + int numParams = fg.getNumParameters(); + for (int i = 0; i < numParams; i++) { + FlowNode paramFlowNode = fg.getParamFlowNode(i); + + Descriptor prefix = paramFlowNode.getDescTuple().get(0); + + // 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); + + paramLocTupleHavingInFlowSet.add(paramLocTuple); + // CompositeLocation inferLoc = mapParamToLoc.get(paramIdx); + // paramInFlowSet.add(inferLoc); + } + } + + System.out.println("paramLocTupleHavingInFlowSet=" + paramLocTupleHavingInFlowSet); + + int numParamsWithIncomingValue = paramLocTupleHavingInFlowSet.size(); + + 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 + + // Generates a location in the method lattice that is higher than the + // paramLocTupleHavingInFlowSet + NTuple pcLocTuple = generateLocTupleHigherThan(md, paramLocTupleHavingInFlowSet); + + int pcLocTupleIdx = pcLocTuple.size() - 1; + Location pcLoc = pcLocTuple.get(pcLocTupleIdx); + Descriptor pcDesc = pcLoc.getLocDescriptor(); + Descriptor enclosingDesc = pcLocTuple.get(pcLocTupleIdx).getDescriptor(); + + HierarchyGraph hierarchyGraph = getHierarchyGraph(enclosingDesc); + HNode pcNode = hierarchyGraph.getHNode(pcDesc); + pcNode.setSkeleton(true); + + for (Iterator iterator = paramLocTupleHavingInFlowSet.iterator(); iterator.hasNext();) { + NTuple paramLocTuple = (NTuple) iterator.next(); + Descriptor lowerDesc = paramLocTuple.get(pcLocTupleIdx).getLocDescriptor(); + hierarchyGraph.addEdge(pcDesc, lowerDesc); + } + + } + + } + + // calculate a return location + // the return location type is lower than all parameters and location + // types of return values + if (!md.getReturnType().isVoid()) { + // first, generate the set of return value location types that starts + // with 'this' reference + + Set inferFieldReturnLocSet = new HashSet(); + + Set paramFlowNodeFlowingToReturnValueSet = getParamNodeFlowingToReturnValue(md); + Set inferParamLocSet = 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); + } + + Set returnNodeSet = fg.getReturnNodeSet(); + + skip: for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { + FlowNode returnNode = (FlowNode) iterator.next(); + CompositeLocation inferReturnLoc = + generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode)); + if (inferReturnLoc.get(0).getLocIdentifier().equals("this")) { + // if the location type of the return value matches "this" reference + // then, check whether this return value is equal to/lower than all + // of parameters that possibly flow into the return values + for (Iterator iterator2 = inferParamLocSet.iterator(); iterator2.hasNext();) { + CompositeLocation paramInferLoc = (CompositeLocation) iterator2.next(); + + if ((!paramInferLoc.equals(inferReturnLoc)) + && !isGreaterThan(methodLattice, paramInferLoc, inferReturnLoc)) { + continue skip; + } + } + inferFieldReturnLocSet.add(inferReturnLoc); + + } + } + + if (inferFieldReturnLocSet.size() > 0) { + + CompositeLocation returnLoc = getLowest(methodLattice, inferFieldReturnLocSet); + if (returnLoc == null) { + // in this case, assign <'this',bottom> to the RETURNLOC + returnLoc = new CompositeLocation(new Location(md, md.getThis().getSymbol())); + returnLoc.addLocation(new Location(md.getClassDesc(), getLattice(md.getClassDesc()) + .getBottomItem())); + } + methodInfo.setReturnLoc(returnLoc); + + } else { + String returnLocSymbol = "RETURNLOC"; + CompositeLocation returnLocInferLoc = + new CompositeLocation(new Location(md, returnLocSymbol)); + methodInfo.setReturnLoc(returnLocInferLoc); + + for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) { + Integer paramIdx = (Integer) iterator.next(); + CompositeLocation inferLoc = mapParamToLoc.get(paramIdx); + String paramLocLocalSymbol = inferLoc.get(0).getLocIdentifier(); + if (!methodLattice.isGreaterThan(paramLocLocalSymbol, returnLocSymbol)) { + // TODO + // addRelationHigherToLower(methodLattice, methodInfo, + // paramLocLocalSymbol, + // returnLocSymbol); + } + } + + for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { + FlowNode returnNode = (FlowNode) iterator.next(); + CompositeLocation inferLoc = + generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode)); + if (!isGreaterThan(methodLattice, inferLoc, returnLocInferLoc)) { + // TODO + // addRelation(methodLattice, methodInfo, inferLoc, + // returnLocInferLoc); + } + } + + } + + } + } + + private NTuple generateLocTupleHigherThan(MethodDescriptor md, + Set> paramLocTupleHavingInFlowSet) { + + System.out.println("-generateLocTupleHigherThan=" + paramLocTupleHavingInFlowSet); + + NTuple higherLocTuple = new NTuple(); + + VarDescriptor thisVarDesc = md.getThis(); + // check if all paramter loc tuple is started with 'this' reference + boolean hasParamNotStartedWithThisRef = false; + + int maxSize = 0; + + Set> paramLocTupleStartedWithThis = new HashSet>(); + + for (Iterator iterator = paramLocTupleHavingInFlowSet.iterator(); iterator.hasNext();) { + NTuple paramLocTuple = (NTuple) iterator.next(); + if (!paramLocTuple.get(0).getLocDescriptor().equals(thisVarDesc)) { + hasParamNotStartedWithThisRef = true; + } else if (paramLocTuple.size() > 1) { + paramLocTupleStartedWithThis.add(paramLocTuple); + if (maxSize < paramLocTuple.size()) { + maxSize = paramLocTuple.size(); + } + } + } + + 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++) { + Set locDescSet = new HashSet(); + Location curLoc = null; + for (Iterator iterator = paramLocTupleHavingInFlowSet.iterator(); iterator.hasNext();) { + NTuple paramLocTuple = (NTuple) iterator.next(); + curLoc = paramLocTuple.get(idx); + Descriptor locDesc = curLoc.getLocDescriptor(); + locDescSet.add(locDesc); + } + System.out.println("locDescSet=" + locDescSet + " idx=" + idx); + if (locDescSet.size() != 1) { + break; + } + Location newLocElement = new Location(curLoc.getDescriptor(), curLoc.getLocDescriptor()); + higherLocTuple.add(newLocElement); + enclosingDesc = getClassTypeDescriptor(curLoc.getLocDescriptor()); + } + + } + + String pcLocIdentifier = PCLOC + (locSeed++); + NameDescriptor pcLocDesc = new NameDescriptor(pcLocIdentifier); + Location newLoc = new Location(enclosingDesc, pcLocDesc); + higherLocTuple.add(newLoc); + + System.out.println("---higherLocTuple=" + higherLocTuple); + + return higherLocTuple; + + } + + public ClassDescriptor getClassTypeDescriptor(Descriptor in) { + + if (in instanceof VarDescriptor) { + return ((VarDescriptor) in).getType().getClassDesc(); + } else {/* if (desc instanceof FieldDescriptor) { */ + return ((FieldDescriptor) in).getType().getClassDesc(); + } + + } + + private Set> calculateHighestLocTupleSet( + Set> paramLocTupleHavingInFlowSet) { + + Set> highestSet = new HashSet>(); + + Iterator> iterator = paramLocTupleHavingInFlowSet.iterator(); + NTuple highest = iterator.next(); + + for (; iterator.hasNext();) { + NTuple curLocTuple = (NTuple) iterator.next(); + if (isHigherThan(curLocTuple, highest)) { + System.out.println(curLocTuple + " is greater than " + highest); + highest = curLocTuple; + } + } + + highestSet.add(highest); + + MethodDescriptor md = (MethodDescriptor) highest.get(0).getDescriptor(); + VarDescriptor thisVarDesc = md.getThis(); + + System.out.println("highest=" + highest); + + for (Iterator> iter = paramLocTupleHavingInFlowSet.iterator(); iter.hasNext();) { + NTuple curLocTuple = iter.next(); + + if (!curLocTuple.equals(highest) && !hasOrderingRelation(highest, curLocTuple)) { + + System.out.println("add it to the highest set=" + curLocTuple); + highestSet.add(curLocTuple); + + } + } + + return highestSet; + + } + + private void calculateExtraLocations2(MethodDescriptor md) { + // calcualte pcloc, returnloc,... + SSJavaLattice methodLattice = getMethodLattice(md); MethodLocationInfo methodInfo = getMethodLocationInfo(md); FlowGraph fg = getFlowGraph(md); @@ -2861,14 +3282,14 @@ public class LocationInference { } else if (curDescriptor instanceof NameDescriptor) { // it is "GLOBAL LOC" case! enclosingDescriptor = GLOBALDESC; + } else if (curDescriptor instanceof InterDescriptor) { + enclosingDescriptor = null; } else { enclosingDescriptor = ((FieldDescriptor) curDescriptor).getClassDescriptor(); } } - System.out.println("-convertToCompositeLocation from=" + tuple + " to " + compLoc); - return compLoc; } @@ -3019,7 +3440,6 @@ public class LocationInference { NTuple srcCurTuple = srcNode.getCurrentDescTuple(); NTuple dstCurTuple = dstNode.getCurrentDescTuple(); - System.out.println("srcCurTuple=" + srcCurTuple + " dstCurTuple=" + dstCurTuple); if (srcCurTuple.get(idx).equals(dstCurTuple.get(idx)) && srcCurTuple.size() > (idx + 1) && dstCurTuple.size() > (idx + 1)) { // value flow between fields: we don't need to add a binary relation @@ -3031,12 +3451,14 @@ public class LocationInference { if (idx == 0) { classDesc = ((VarDescriptor) desc).getType().getClassDesc(); } else { - if (desc instanceof FieldDescriptor) { classDesc = ((FieldDescriptor) desc).getType().getClassDesc(); } else { - // TODO: need to handle a location descriptor case - classDesc = null; + // this case is that the local variable has a composite location assignment + // the following element after the composite location to the local variable + // has the enclosing descriptor of the local variable + Descriptor localDesc = srcNode.getDescTuple().get(0); + classDesc = ((VarDescriptor) localDesc).getType().getClassDesc(); } } extractFlowsBetweenFields(classDesc, srcNode, dstNode, idx + 1); @@ -3829,6 +4251,11 @@ public class LocationInference { } private Set getParamNodeFlowingToReturnValue(MethodDescriptor md) { + + if (!mapMethodDescToParamNodeFlowsToReturnValue.containsKey(md)) { + mapMethodDescToParamNodeFlowsToReturnValue.put(md, new HashSet()); + } + return mapMethodDescToParamNodeFlowsToReturnValue.get(md); } diff --git a/Robust/src/Analysis/SSJava/MethodSummary.java b/Robust/src/Analysis/SSJava/MethodSummary.java index 8414b834..63f4b99e 100644 --- a/Robust/src/Analysis/SSJava/MethodSummary.java +++ b/Robust/src/Analysis/SSJava/MethodSummary.java @@ -30,4 +30,12 @@ public class MethodSummary extends LocationSummary { mapParamIdxToInferLoc.put(paramIdx, inferLoc); } + public Map getMapParamIdxToInferLoc() { + return mapParamIdxToInferLoc; + } + + public void setPCLoc(CompositeLocation pcLoc) { + this.pcLoc = pcLoc; + } + } diff --git a/Robust/src/Analysis/SSJava/SSJavaLattice.java b/Robust/src/Analysis/SSJava/SSJavaLattice.java index 847cfecb..0ca550a0 100644 --- a/Robust/src/Analysis/SSJava/SSJavaLattice.java +++ b/Robust/src/Analysis/SSJava/SSJavaLattice.java @@ -323,7 +323,11 @@ public class SSJavaLattice extends Lattice { System.out.println("---insert new location=" + newLoc + " between=" + higher + "<->" + lowerSet); Set connectedSet = get(higher); - connectedSet.removeAll(lowerSet); + if (connectedSet == null) { + connectedSet = new HashSet(); + }else{ + connectedSet.removeAll(lowerSet); + } connectedSet.add(newLoc); for (Iterator iterator = lowerSet.iterator(); iterator.hasNext();) {