From 60a163564b0c17c6e4ca0ed875578ab105ae5464 Mon Sep 17 00:00:00 2001 From: yeom Date: Sat, 4 Aug 2012 02:09:12 +0000 Subject: [PATCH] changes. --- .../Analysis/SSJava/LocationInference.java | 320 ++++++++++++++---- .../Analysis/SSJava/MethodLocationInfo.java | 57 ++-- 2 files changed, 266 insertions(+), 111 deletions(-) diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index 66a82df8..4d87afb7 100644 --- a/Robust/src/Analysis/SSJava/LocationInference.java +++ b/Robust/src/Analysis/SSJava/LocationInference.java @@ -2,6 +2,7 @@ package Analysis.SSJava; import java.io.IOException; import java.util.ArrayList; +import java.util.Collection; import java.util.Collections; import java.util.Comparator; import java.util.HashMap; @@ -260,6 +261,12 @@ public class LocationInference { LinkedList descriptorListToAnalyze = ssjava.getSortedDescriptors(); + Collections.sort(descriptorListToAnalyze, new Comparator() { + public int compare(MethodDescriptor o1, MethodDescriptor o2) { + return o1.getSymbol().compareToIgnoreCase(o2.getSymbol()); + } + }); + // current descriptors to visit in fixed-point interprocedural analysis, // prioritized by // dependency in the call graph @@ -312,7 +319,6 @@ public class LocationInference { } } - } private void setMethodLocInfo(MethodDescriptor md, MethodLocationInfo methodInfo) { @@ -339,32 +345,66 @@ public class LocationInference { private void checkConsistency(MethodDescriptor md1, MethodDescriptor md2) { // check that two lattice have the same relations between parameters(+PC - // LOC, RETURN LOC) + // LOC, GLOBAL_LOC RETURN LOC) - MethodLocationInfo methodInfo1 = getMethodLocationInfo(md1); + List list1 = new ArrayList(); + List list2 = new ArrayList(); - SSJavaLattice lattice1 = getMethodLattice(md1); - SSJavaLattice lattice2 = getMethodLattice(md2); + MethodLocationInfo locInfo1 = getMethodLocationInfo(md1); + MethodLocationInfo locInfo2 = getMethodLocationInfo(md2); - Set paramLocNameSet1 = methodInfo1.getParameterLocNameSet(); + Map paramMap1 = locInfo1.getMapParamIdxToInferLoc(); + Map paramMap2 = locInfo2.getMapParamIdxToInferLoc(); - for (Iterator iterator = paramLocNameSet1.iterator(); iterator.hasNext();) { - String locName1 = (String) iterator.next(); - for (Iterator iterator2 = paramLocNameSet1.iterator(); iterator2.hasNext();) { - String locName2 = (String) iterator2.next(); + int numParam = locInfo1.getMapParamIdxToInferLoc().keySet().size(); + + // add location types of paramters + for (int idx = 0; idx < numParam; idx++) { + list1.add(paramMap1.get(Integer.valueOf(idx))); + list2.add(paramMap2.get(Integer.valueOf(idx))); + } + + // add program counter location + list1.add(locInfo1.getPCLoc()); + list2.add(locInfo2.getPCLoc()); + + if (!md1.getReturnType().isVoid()) { + // add return value location + CompositeLocation rtrLoc1 = + new CompositeLocation(new Location(md1, locInfo1.getReturnLocName())); + CompositeLocation rtrLoc2 = + new CompositeLocation(new Location(md2, locInfo2.getReturnLocName())); + list1.add(rtrLoc1); + list2.add(rtrLoc2); + } + + // add global location type + if (md1.isStatic()) { + CompositeLocation globalLoc1 = + new CompositeLocation(new Location(md1, locInfo1.getGlobalLocName())); + CompositeLocation globalLoc2 = + new CompositeLocation(new Location(md2, locInfo2.getGlobalLocName())); + list1.add(globalLoc1); + list2.add(globalLoc2); + } - if (!locName1.equals(locName2)) { + for (int i = 0; i < list1.size(); i++) { + CompositeLocation locA1 = list1.get(i); + CompositeLocation locA2 = list2.get(i); + for (int k = 0; k < list1.size(); k++) { + if (i != k) { + CompositeLocation locB1 = list1.get(k); + CompositeLocation locB2 = list2.get(k); + boolean r1 = isGreaterThan(locA1, locB1); - boolean r1 = lattice1.isGreaterThan(locName1, locName2); - boolean r2 = lattice2.isGreaterThan(locName1, locName2); + boolean r2 = isGreaterThan(locA2, locB2); if (r1 != r2) { throw new Error("The method " + md1 + " is not consistent with the method " + md2 - + ".:: They have a different ordering relation between parameters " + locName1 - + " and " + locName2 + "."); + + ".:: They have a different ordering relation between locations (" + locA1 + "," + + locB1 + ") and (" + locA2 + "," + locB2 + ")."); } } - } } @@ -445,6 +485,37 @@ public class LocationInference { } } + // create mapping from param idx to inferred composite location + + int offset; + if (!md.isStatic()) { + // add 'this' reference location + offset = 1; + methodInfo.addMapParamIdxToInferLoc(0, methodInfo.getInferLocation(md.getThis())); + } else { + offset = 0; + } + + for (int idx = 0; idx < md.numParameters(); idx++) { + Descriptor paramDesc = md.getParameter(idx); + CompositeLocation inferParamLoc = methodInfo.getInferLocation(paramDesc); + methodInfo.addMapParamIdxToInferLoc(idx + offset, inferParamLoc); + } + + // calculate the initial program counter location + // PC location is higher than location types of all parameters + String pcLocSymbol = "PCLOC"; + Map mapParamToLoc = methodInfo.getMapParamIdxToInferLoc(); + Set keySet = mapParamToLoc.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Integer paramIdx = (Integer) iterator.next(); + CompositeLocation inferLoc = mapParamToLoc.get(paramIdx); + String paramLocLocalSymbol = inferLoc.get(0).getLocIdentifier(); + if (!methodLattice.isGreaterThan(pcLocSymbol, paramLocLocalSymbol)) { + addRelationHigherToLower(methodLattice, methodInfo, pcLocSymbol, paramLocLocalSymbol); + } + } + // calculate a return location if (!md.getReturnType().isVoid()) { Set returnNodeSet = fg.getReturnNodeSet(); @@ -459,7 +530,8 @@ public class LocationInference { String returnGLB = methodLattice.getGLB(returnVarSymbolSet); if (returnGLB.equals(SSJavaAnalysis.BOTTOM)) { - // need to insert a new location in-between the bottom and all locations + // need to insert a new location in-between the bottom and all + // locations // that is directly connected to the bottom String returnNewLocationSymbol = "Loc" + (SSJavaLattice.seed++); methodLattice.insertNewLocationAtOneLevelHigher(returnGLB, returnNewLocationSymbol); @@ -471,6 +543,52 @@ public class LocationInference { } + private CompositeLocation getHighestLocation(Collection locSet) { + + Iterator locIter = locSet.iterator(); + + CompositeLocation highest = locIter.next(); + + for (; locIter.hasNext();) { + CompositeLocation loc = (CompositeLocation) locIter.next(); + if (isGreaterThan(loc, highest)) { + highest = loc; + } + } + + return highest; + + } + + private boolean isGreaterThan(CompositeLocation comp1, CompositeLocation comp2) { + + for (int idx = 0; idx < comp1.getSize(); idx++) { + Location loc1 = comp1.get(idx); + Location loc2 = comp2.get(idx); + + Descriptor desc1 = loc1.getDescriptor(); + Descriptor desc2 = loc2.getDescriptor(); + + if (!desc1.equals(desc2)) { + throw new Error("Fail to compare " + comp1 + " and " + comp2); + } + + String symbol1 = loc1.getLocIdentifier(); + String symbol2 = loc2.getLocIdentifier(); + + if (symbol1.equals(symbol2)) { + continue; + } else if (getLattice(desc1).isGreaterThan(symbol1, symbol2)) { + return true; + } else { + return false; + } + + } + + return false; + } + private void recursiveAddRelationToLattice(int idx, MethodDescriptor md, CompositeLocation srcInferLoc, CompositeLocation dstInferLoc) { @@ -511,6 +629,7 @@ public class LocationInference { setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(mdCallee)); } + System.out.println("mdCaller=" + mdCaller + " setPossibleCallees=" + setPossibleCallees); for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) { MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next(); propagateRelationToCaller(min, mdCaller, possibleMdCallee); @@ -528,6 +647,7 @@ public class LocationInference { FlowGraph calleeFlowGraph = getFlowGraph(possibleMdCallee); + System.out.println("calleeFlowGraph=" + calleeFlowGraph + " of " + possibleMdCallee); // find parameter node Set paramNodeSet = calleeFlowGraph.getParameterNodeSet(); @@ -556,7 +676,11 @@ public class LocationInference { NTuple higherArg = getArgTupleByArgIdx(min, higherLocIdxCallee); NTuple lowerArg = getArgTupleByArgIdx(min, lowerLocIdxCallee); - addFlowGraphEdge(mdCaller, higherArg, lowerArg); + if (higherArg != null && lowerArg != null) { + // if the argument has the TOP location, getArgTupleByArgIdx returns + // null + addFlowGraphEdge(mdCaller, higherArg, lowerArg); + } } @@ -602,74 +726,99 @@ public class LocationInference { // add a new binary relation of dstNode < srcNode FlowGraph flowGraph = getFlowGraph(md); - // MethodLocationInfo methodInfo = getMethodLocationInfo(md); - - // String srcOriginSymbol = getSymbol(0, srcNode); - // String dstOriginSymbol = getSymbol(0, dstNode); Descriptor srcDesc = getDescriptor(0, srcNode); Descriptor dstDesc = getDescriptor(0, dstNode); - // consider a composite location case - boolean isSrcLocalVar = false; - boolean isDstLocalVar = false; - if (srcNode.getDescTuple().size() == 1) { - isSrcLocalVar = true; - } - - if (dstNode.getDescTuple().size() == 1) { - isDstLocalVar = true; - } - - boolean isAssignedCompositeLocation = false; - if (!methodInfo.getInferLocation(srcDesc).get(0).getLocIdentifier() - .equals(methodInfo.getThisLocName())) { - isAssignedCompositeLocation = - calculateCompositeLocation(flowGraph, methodLattice, methodInfo, srcNode); - } + // boolean isAssignedCompositeLocation = false; + // if (!methodInfo.getInferLocation(srcDesc).get(0).getLocIdentifier() + // .equals(methodInfo.getThisLocName())) { + // isAssignedCompositeLocation = + calculateCompositeLocation(flowGraph, methodLattice, methodInfo, srcNode); + // } String srcSymbol = methodInfo.getInferLocation(srcDesc).get(0).getLocIdentifier(); String dstSymbol = methodInfo.getInferLocation(dstDesc).get(0).getLocIdentifier(); - if (srcNode.isParameter()) { - int paramIdx = flowGraph.getParamIdx(srcNode.getDescTuple()); - methodInfo.addParameter(srcSymbol, srcDesc, paramIdx); - } else { - // methodInfo.addMappingOfLocNameToDescriptor(srcSymbol, srcDesc); - } + // if (srcNode.isParameter()) { + // int paramIdx = flowGraph.getParamIdx(srcNode.getDescTuple()); + // methodInfo.addParameter(srcSymbol, srcDesc, paramIdx); + // } + // + // if (dstNode.isParameter()) { + // int paramIdx = flowGraph.getParamIdx(dstNode.getDescTuple()); + // methodInfo.addParameter(dstSymbol, dstDesc, paramIdx); + // } + + CompositeLocation srcInferLoc = methodInfo.getInferLocation(srcDesc); + CompositeLocation dstInferLoc = methodInfo.getInferLocation(dstDesc); + + String srcLocalLocSymbol = srcInferLoc.get(0).getLocIdentifier(); + String dstLocalLocSymbol = dstInferLoc.get(0).getLocIdentifier(); - if (dstNode.isParameter()) { - int paramIdx = flowGraph.getParamIdx(dstNode.getDescTuple()); - methodInfo.addParameter(dstSymbol, dstDesc, paramIdx); + if (srcInferLoc.getSize() == 1 && dstInferLoc.getSize() == 1) { + // add a new relation to the local lattice + addRelationHigherToLower(methodLattice, methodInfo, srcLocalLocSymbol, dstLocalLocSymbol); + } else if (srcInferLoc.getSize() > 1 && dstInferLoc.getSize() > 1) { + // both src and dst have assigned to a composite location + recursivelyAddRelation(1, srcInferLoc, dstInferLoc); } else { - // methodInfo.addMappingOfLocNameToDescriptor(dstSymbol, dstDesc); + // either src or dst has assigned to a composite location + if (!srcLocalLocSymbol.equals(dstLocalLocSymbol)) { + addRelationHigherToLower(methodLattice, methodInfo, srcLocalLocSymbol, dstLocalLocSymbol); + } } + // if (!isAssignedCompositeLocation) { + // // source does not have a composite location + // + // NTuple srcTuple = flowGraph.getLocationTuple(srcNode); + // NTuple dstTuple = flowGraph.getLocationTuple(dstNode); + // + // recursivelyAddCompositeRelation(md, flowGraph, methodInfo, srcNode, + // dstNode, srcDesc, dstDesc); + // + // // if (!srcSymbol.equals(dstSymbol)) { + // // // add a local relation + // // if (!methodLattice.isGreaterThan(srcSymbol, dstSymbol)) { + // // // if the lattice does not have this relation, add it + // // addRelationHigherToLower(methodLattice, methodInfo, srcSymbol, + // // dstSymbol); + // // // methodLattice.addRelationHigherToLower(srcSymbol, dstSymbol); + // // } + // // } else { + // // // if src and dst have the same local location... + // // recursivelyAddCompositeRelation(md, flowGraph, methodInfo, srcNode, + // // dstNode, srcDesc, + // // dstDesc); + // // } + // + // } else { + // // source variable has a composite location + // if (methodInfo.getInferLocation(dstDesc).getSize() == 1) { + // if (!srcSymbol.equals(dstSymbol)) { + // addRelationHigherToLower(methodLattice, methodInfo, srcSymbol, + // dstSymbol); + // } + // } + // + // } - if (!isAssignedCompositeLocation) { - // source does not have a composite location - if (!srcSymbol.equals(dstSymbol)) { - // add a local relation - if (!methodLattice.isGreaterThan(srcSymbol, dstSymbol)) { - // if the lattice does not have this relation, add it - addRelationHigherToLower(methodLattice, methodInfo, srcSymbol, dstSymbol); - // methodLattice.addRelationHigherToLower(srcSymbol, dstSymbol); - } - } else { - // if src and dst have the same local location... + } - recursivelyAddCompositeRelation(md, flowGraph, methodInfo, srcNode, dstNode, srcDesc, - dstDesc); + private void recursivelyAddRelation(int idx, CompositeLocation srcInferLoc, + CompositeLocation dstInferLoc) { - } + String srcLocSymbol = srcInferLoc.get(idx).getLocIdentifier(); + String dstLocSymbol = dstInferLoc.get(idx).getLocIdentifier(); + if (srcLocSymbol.equals(dstLocSymbol)) { + recursivelyAddRelation(idx + 1, srcInferLoc, dstInferLoc); } else { - // source variable has a composite location - if (methodInfo.getInferLocation(dstDesc).getSize() == 1) { - if (!srcSymbol.equals(dstSymbol)) { - addRelationHigherToLower(methodLattice, methodInfo, srcSymbol, dstSymbol); - } - } + Descriptor parentDesc = srcInferLoc.get(idx).getDescriptor(); + + addRelationHigherToLower(getLattice(parentDesc), getLocationInfo(parentDesc), srcLocSymbol, + dstLocSymbol); } } @@ -1095,6 +1244,8 @@ public class LocationInference { public void constructFlowGraph() { setupToAnalyze(); + + Set visited=new HashSet(); while (!toAnalyzeIsEmpty()) { ClassDescriptor cd = toAnalyzeNext(); @@ -1102,7 +1253,7 @@ public class LocationInference { setupToAnalazeMethod(cd); while (!toAnalyzeMethodIsEmpty()) { MethodDescriptor md = toAnalyzeMethodNext(); - if (ssjava.needTobeAnnotated(md)) { +// if (ssjava.needTobeAnnotated(md)) { if (state.SSJAVADEBUG) { System.out.println(); System.out.println("SSJAVA: Constructing a flow graph: " + md); @@ -1115,6 +1266,16 @@ public class LocationInference { } else { setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md)); } + + Set calleeSet=ssjava.getCallGraph().getCalleeSet(md); + + for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) { + MethodDescriptor calleemd = (MethodDescriptor) iterator.next(); + if((!ssjava.isSSJavaUtil(calleemd.getClassDesc())) && (! visited.contains(calleemd))){ + toanalyzeMethodList.add(calleemd); + } + } + mapMethodDescToPossibleMethodDescSet.put(md, setPossibleCallees); // creates a mapping from a parameter descriptor to its index @@ -1128,10 +1289,12 @@ public class LocationInference { FlowGraph fg = new FlowGraph(md, mapParamDescToIdx); mapMethodDescriptorToFlowGraph.put(md, fg); + visited.add(md); analyzeMethodBody(cd, md); + } } - } +// } _debug_printGraph(); } @@ -1493,7 +1656,7 @@ public class LocationInference { // checkCallerArgumentLocationConstraints(md, nametable, min, // baseLocation, constraint); - if (!min.getMethod().getReturnType().isVoid()) { + if (min.getMethod().getReturnType()!=null && !min.getMethod().getReturnType().isVoid()) { // If method has a return value, compute the highest possible return // location in the caller's perspective // CompositeLocation ceilingLoc = @@ -1532,6 +1695,7 @@ public class LocationInference { NTuple argTuple = analyzeFlowExpressionNode(callermd, nametable, en, new NodeTupleSet(), false); + // if argument is liternal node, argTuple is set to NULL. addArgIdxMap(min, i + offset, argTuple); } @@ -1540,7 +1704,6 @@ public class LocationInference { } private void analyzeLiteralNode(MethodDescriptor md, SymbolTable nametable, LiteralNode en) { - // TODO Auto-generated method stub } @@ -1787,6 +1950,17 @@ public class LocationInference { analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null, implicitFlowTupleSet, false); + if (an.getOperation().getOp() >= 2 && an.getOperation().getOp() <= 12) { + // if assignment contains OP+EQ operator, creates edges from LHS to LHS + for (Iterator> iter = nodeSetLHS.iterator(); iter.hasNext();) { + NTuple fromTuple = iter.next(); + for (Iterator> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) { + NTuple toTuple = iter2.next(); + addFlowGraphEdge(md, fromTuple, toTuple); + } + } + } + // creates edges from RHS to LHS for (Iterator> iter = nodeSetRHS.iterator(); iter.hasNext();) { NTuple fromTuple = iter.next(); diff --git a/Robust/src/Analysis/SSJava/MethodLocationInfo.java b/Robust/src/Analysis/SSJava/MethodLocationInfo.java index f4780e06..a29fa363 100644 --- a/Robust/src/Analysis/SSJava/MethodLocationInfo.java +++ b/Robust/src/Analysis/SSJava/MethodLocationInfo.java @@ -12,26 +12,30 @@ public class MethodLocationInfo extends LocationInfo { String returnLocName; String thisLocName; - String PCLocName; + CompositeLocation pcLoc; String globalLocName; - Map mapParamIdxToLocName; + Map mapParamIdxToInferLoc; Set paramLocNameSet; public MethodLocationInfo(MethodDescriptor md) { this.md = md; - this.mapParamIdxToLocName = new HashMap(); this.paramLocNameSet = new HashSet(); - this.PCLocName = SSJavaAnalysis.TOP; + this.pcLoc = new CompositeLocation(new Location(md, Location.TOP)); + this.mapParamIdxToInferLoc = new HashMap(); } - /* - * public void mapFlowNodeToInferLocation(FlowNode node, CompositeLocation - * location) { mapFlowNodeToLocation.put(node, location); } - * - * public CompositeLocation getInferLocation(FlowNode node) { return - * mapFlowNodeToLocation.get(node); } - */ + public void addMapParamIdxToInferLoc(int paramIdx, CompositeLocation inferLoc) { + mapParamIdxToInferLoc.put(paramIdx, inferLoc); + } + + public Map getMapParamIdxToInferLoc() { + return mapParamIdxToInferLoc; + } + + public String getGlobalLocName() { + return globalLocName; + } public void setGlobalLocName(String globalLocName) { this.globalLocName = globalLocName; @@ -53,35 +57,12 @@ public class MethodLocationInfo extends LocationInfo { this.thisLocName = thisLocName; } - public String getPCLocName() { - return PCLocName; - } - - public void setPCLocName(String pCLocName) { - PCLocName = pCLocName; + public CompositeLocation getPCLoc() { + return pcLoc; } - public void addParameter(String name, Descriptor desc, int idx) { - mapParamIdxToLocName.put(new Integer(idx), name); - // addMappingOfLocNameToDescriptor(name, desc); - } - - public Set getParameterLocNameSet() { - Set paramSet = new HashSet(); - - paramSet.add(PCLocName); - - if (thisLocName != null) { - paramSet.add(thisLocName); - } - - if (returnLocName != null) { - paramSet.add(returnLocName); - } - - paramSet.addAll(mapParamIdxToLocName.values()); - - return paramSet; + public void setPCLoc(CompositeLocation pcLoc) { + this.pcLoc = pcLoc; } public void removeMaplocalVarToLocSet(Descriptor localVarDesc) { -- 2.34.1