From bd0e1175c28b5defcf6eff87eeaebd937bae96ea Mon Sep 17 00:00:00 2001 From: yeom Date: Wed, 1 Aug 2012 00:45:29 +0000 Subject: [PATCH] changes on the inference engine. --- Robust/src/Analysis/SSJava/FlowGraph.java | 47 ++++--- .../Analysis/SSJava/LocationInference.java | 126 ++++++++++-------- .../Analysis/SSJava/MethodLocationInfo.java | 6 + .../src/Analysis/SSJava/SSJavaAnalysis.java | 6 +- 4 files changed, 107 insertions(+), 78 deletions(-) diff --git a/Robust/src/Analysis/SSJava/FlowGraph.java b/Robust/src/Analysis/SSJava/FlowGraph.java index a2d1791b..4e0a7a66 100644 --- a/Robust/src/Analysis/SSJava/FlowGraph.java +++ b/Robust/src/Analysis/SSJava/FlowGraph.java @@ -86,7 +86,7 @@ public class FlowGraph { } set.add(neighbor); - System.out.println("add a new neighbor " + neighbor + " to " + node); +// System.out.println("add a new neighbor " + neighbor + " to " + node); } public boolean hasEdge(NTuple fromDescTuple, NTuple toDescTuple) { @@ -111,10 +111,10 @@ public class FlowGraph { public void addValueFlowEdge(NTuple fromDescTuple, NTuple toDescTuple) { - FlowNode fromNode = mapDescTupleToInferNode.get(fromDescTuple); - FlowNode toNode = mapDescTupleToInferNode.get(toDescTuple); + FlowNode fromNode = getFlowNode(fromDescTuple); + FlowNode toNode = getFlowNode(toDescTuple); - System.out.println("create an edge from " + fromNode + " to " + toNode); + // System.out.println("create an edge from " + fromNode + " to " + toNode); int fromTupleSize = fromDescTuple.size(); NTuple curTuple = new NTuple(); @@ -140,7 +140,7 @@ public class FlowGraph { FlowEdge edge = new FlowEdge(fromNode, toNode, initTuple, endTuple); fromNode.addOutEdge(edge); - System.out.println("add a new edge=" + edge); +// System.out.println("add a new edge=" + edge); } @@ -172,7 +172,7 @@ public class FlowGraph { getFlowNode(baseTuple).addFieldNode(node); } - System.out.println("Creating new node=" + node); +// System.out.println("Creating new node=" + node); return node; } else { return mapDescTupleToInferNode.get(tuple); @@ -245,20 +245,31 @@ public class FlowGraph { NTuple locTuple = new NTuple(); ClassDescriptor cd = null; - for (int i = 0; i < descTuple.size(); i++) { - Descriptor curDesc = descTuple.get(i); - Location loc; - if (i == 0) { - loc = new Location(md, curDesc.getSymbol()); - loc.setLocDescriptor(md); - cd = ((VarDescriptor) curDesc).getType().getClassDesc(); - } else { - loc = new Location(cd, curDesc.getSymbol()); - loc.setLocDescriptor(curDesc); - cd = ((FieldDescriptor) curDesc).getType().getClassDesc(); + Descriptor localDesc = fn.getDescTuple().get(0); + if (localDesc.getSymbol().equals(LocationInference.TOPLOC)) { + Location topLoc = new Location(md, Location.TOP); + locTuple.add(topLoc); + } else if (localDesc.getSymbol().equals(LocationInference.GLOBALLOC)) { + Location topLoc = new Location(md, LocationInference.GLOBALLOC); + locTuple.add(topLoc); + } else { + // normal case + for (int i = 0; i < descTuple.size(); i++) { + Descriptor curDesc = descTuple.get(i); + Location loc; + if (i == 0) { + loc = new Location(md, curDesc.getSymbol()); + loc.setLocDescriptor(md); + cd = ((VarDescriptor) curDesc).getType().getClassDesc(); + } else { + loc = new Location(cd, curDesc.getSymbol()); + loc.setLocDescriptor(curDesc); + cd = ((FieldDescriptor) curDesc).getType().getClassDesc(); + } + locTuple.add(loc); } - locTuple.add(loc); } + mapFlowNodeToLocTuple.put(fn, locTuple); } return mapFlowNodeToLocTuple.get(fn); diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index 89c206d6..66a82df8 100644 --- a/Robust/src/Analysis/SSJava/LocationInference.java +++ b/Robust/src/Analysis/SSJava/LocationInference.java @@ -44,6 +44,7 @@ import IR.Tree.ReturnNode; import IR.Tree.SubBlockNode; import IR.Tree.SwitchStatementNode; import IR.Tree.TertiaryNode; +import IR.Tree.TreeNode; public class LocationInference { @@ -78,6 +79,14 @@ public class LocationInference { private Map> mapMethodDescToPossibleMethodDescSet; + public static final String GLOBALLOC = "GLOBALLOC"; + + public static final String TOPLOC = "TOPLOC"; + + public static final Descriptor GLOBALDESC = new NameDescriptor(GLOBALLOC); + + public static final Descriptor TOPDESC = new NameDescriptor(TOPLOC); + boolean debug = true; public LocationInference(SSJavaAnalysis ssjava, State state) { @@ -344,7 +353,6 @@ public class LocationInference { for (Iterator iterator2 = paramLocNameSet1.iterator(); iterator2.hasNext();) { String locName2 = (String) iterator2.next(); - if (!locName1.equals(locName2)) { boolean r1 = lattice1.isGreaterThan(locName1, locName2); @@ -379,11 +387,12 @@ public class LocationInference { // from the callee analyzeLatticeMethodInvocationNode(md); - // grab the this location if the method use the 'this' reference + // set the this location String thisLocSymbol = md.getThis().getSymbol(); - // if (methodLattice.getKeySet().contains(thisLocSymbol)) { methodInfo.setThisLocName(thisLocSymbol); - // } + + // set the global location + methodInfo.setGlobalLocName(LocationInference.GLOBALLOC); // visit each node of method flow graph FlowGraph fg = getFlowGraph(md); @@ -443,7 +452,8 @@ public class LocationInference { for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { FlowNode rtrNode = (FlowNode) iterator.next(); - String localSymbol = rtrNode.getDescTuple().get(0).getSymbol(); + String localSymbol = + methodInfo.getInferLocation(rtrNode.getDescTuple().get(0)).get(0).getLocIdentifier(); returnVarSymbolSet.add(localSymbol); } @@ -621,7 +631,6 @@ public class LocationInference { 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); @@ -663,7 +672,6 @@ public class LocationInference { } - } private void recursivelyAddCompositeRelation(MethodDescriptor md, FlowGraph flowGraph, @@ -758,7 +766,6 @@ public class LocationInference { } }); - for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) { FlowNode reachableNode = (FlowNode) iterator2.next(); if (reachableNode.getDescTuple().size() == 1) { @@ -780,7 +787,6 @@ public class LocationInference { } - if (!reachableCommonPrefixSet.isEmpty()) { // found reachable nodes that start with the prefix curPrefix // need to assign a composite location @@ -819,7 +825,6 @@ public class LocationInference { Location fieldLoc = new Location(desc, newLocSymbol); inferLocation.addLocation(fieldLoc); - methodInfo.mapDescriptorToLocation(localVarDesc, inferLocation); methodInfo.removeMaplocalVarToLocSet(localVarDesc); @@ -832,7 +837,6 @@ public class LocationInference { String localLocName = methodInfo.getInferLocation(localVarDesc).get(0).getLocIdentifier(); return true; - } newlyInsertedLocName = inferLocation.get(inferLocation.getSize() - 1).getLocIdentifier(); @@ -842,11 +846,11 @@ public class LocationInference { Location loc = tuple.get(idx); String higher = locInfo.getFieldInferLocation(loc.getLocDescriptor()).getLocIdentifier(); - System.out.println("here3"); - + System.out.println("--"); + System.out.println("add in-flow relation:"); addRelationHigherToLower(lattice, locInfo, higher, newlyInsertedLocName); } - + System.out.println("end of add-inflow relation"); for (Iterator iterator = localInNodeSet.iterator(); iterator.hasNext();) { FlowNode localNode = (FlowNode) iterator.next(); @@ -861,7 +865,7 @@ public class LocationInference { && inNodeInferLoc.getSize() == (curPrefix.size() + 1)) { String higher = inNodeInferLoc.get(inNodeInferLoc.getSize() - 1).getLocIdentifier(); if (!higher.equals(newlyInsertedLocName)) { - + System.out.println("add localInNodeSet relation:"); addRelationHigherToLower(lattice, locInfo, higher, newlyInsertedLocName); } } else { @@ -876,9 +880,10 @@ public class LocationInference { Location loc = tuple.get(idx); String lower = locInfo.getFieldInferLocation(loc.getLocDescriptor()).getLocIdentifier(); // lattice.addRelationHigherToLower(newlyInsertedLocName, lower); - + System.out.println("add out-flow relation:"); addRelationHigherToLower(lattice, locInfo, newlyInsertedLocName, lower); } + System.out.println("end of add out-flow relation"); for (Iterator iterator = localOutNodeSet.iterator(); iterator.hasNext();) { FlowNode localOutNode = (FlowNode) iterator.next(); @@ -899,6 +904,7 @@ public class LocationInference { && outNodeInferLoc.getSize() == (curPrefix.size() + 1)) { String lower = outNodeInferLoc.get(outNodeInferLoc.getSize() - 1).getLocIdentifier(); + System.out.println("add outNodeInferLoc relation:"); addRelationHigherToLower(lattice, locInfo, newlyInsertedLocName, lower); @@ -925,7 +931,9 @@ public class LocationInference { for (Iterator iterator = descSet.iterator(); iterator.hasNext();) { Descriptor desc = (Descriptor) iterator.next(); - if (desc instanceof VarDescriptor) { + if (desc.equals(LocationInference.GLOBALDESC)) { + return true; + } else if (desc instanceof VarDescriptor) { if (!((VarDescriptor) desc).getType().isPrimitive()) { return true; } @@ -942,7 +950,13 @@ public class LocationInference { private void addRelationHigherToLower(SSJavaLattice lattice, LocationInfo locInfo, String higher, String lower) { + // if (higher.equals(lower) && lattice.isSharedLoc(higher)) { + // return; + // } + Set cycleElementSet = lattice.getPossibleCycleElements(higher, lower); + System.out.println("#Check cycle=" + lower + " < " + higher); + System.out.println("#cycleElementSet=" + cycleElementSet); boolean hasNonPrimitiveElement = false; for (Iterator iterator = cycleElementSet.iterator(); iterator.hasNext();) { @@ -971,6 +985,7 @@ public class LocationInference { locInfo.mergeMapping(oldLocSymbol, newSharedLoc); } + lattice.addSharedLoc(newSharedLoc); } else if (!lattice.isGreaterThan(higher, lower)) { lattice.addRelationHigherToLower(higher, lower); @@ -989,7 +1004,6 @@ public class LocationInference { private void prefixSanityCheck(List> prefixList, int curIdx, FlowGraph flowGraph, Set reachableNodeSet) { - NTuple curPrefix = prefixList.get(curIdx); for (int i = curIdx + 1; i < prefixList.size(); i++) { @@ -1037,7 +1051,6 @@ public class LocationInference { private void extractRelationFromFieldFlows(ClassDescriptor cd, FlowNode srcNode, FlowNode dstNode, int idx) { - if (srcNode.getDescTuple().get(idx).equals(dstNode.getDescTuple().get(idx)) && srcNode.getDescTuple().size() > (idx + 1) && dstNode.getDescTuple().size() > (idx + 1)) { // value flow between fields: we don't need to add a binary relation @@ -1063,7 +1076,6 @@ public class LocationInference { SSJavaLattice fieldLattice = getFieldLattice(cd); LocationInfo fieldInfo = getFieldLocationInfo(cd); - String srcSymbol = fieldInfo.getFieldInferLocation(srcFieldDesc).getLocIdentifier(); String dstSymbol = fieldInfo.getFieldInferLocation(dstFieldDesc).getLocIdentifier(); @@ -1195,18 +1207,20 @@ public class LocationInference { ExpressionNode returnExp = rn.getReturnExpression(); - NodeTupleSet nodeSet = new NodeTupleSet(); - analyzeFlowExpressionNode(md, nametable, returnExp, nodeSet, false); + if (returnExp != null) { + NodeTupleSet nodeSet = new NodeTupleSet(); + analyzeFlowExpressionNode(md, nametable, returnExp, nodeSet, false); - FlowGraph fg = getFlowGraph(md); + FlowGraph fg = getFlowGraph(md); - // annotate the elements of the node set as the return location - for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { - NTuple returnDescTuple = (NTuple) iterator.next(); - fg.setReturnFlowNode(returnDescTuple); - for (Iterator iterator2 = implicitFlowTupleSet.iterator(); iterator2.hasNext();) { - NTuple implicitFlowDescTuple = (NTuple) iterator2.next(); - fg.addValueFlowEdge(implicitFlowDescTuple, returnDescTuple); + // annotate the elements of the node set as the return location + for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + NTuple returnDescTuple = (NTuple) iterator.next(); + fg.setReturnFlowNode(returnDescTuple); + for (Iterator iterator2 = implicitFlowTupleSet.iterator(); iterator2.hasNext();) { + NTuple implicitFlowDescTuple = (NTuple) iterator2.next(); + fg.addValueFlowEdge(implicitFlowDescTuple, returnDescTuple); + } } } @@ -1435,7 +1449,7 @@ public class LocationInference { if (min.getExpression() != null) { NodeTupleSet baseNodeSet = new NodeTupleSet(); - analyzeFlowExpressionNode(calleeMD, nametable, min.getExpression(), baseNodeSet, null, + analyzeFlowExpressionNode(md, nametable, min.getExpression(), baseNodeSet, null, implicitFlowTupleSet, false); } else { @@ -1653,22 +1667,14 @@ public class LocationInference { FieldDescriptor fd = (FieldDescriptor) d; if (fd.isStatic()) { if (fd.isFinal()) { - // if it is 'static final', the location has TOP since no one can - // change its value - // loc.addLocation(Location.createTopLocation(md)); - // return loc; + // if it is 'static final', assign the default TOP LOCATION + // DESCRIPTOR + base.add(TOPDESC); + return base; } else { - // if 'static', the location has pre-assigned global loc - // MethodLattice localLattice = ssjava.getMethodLattice(md); - // String globalLocId = localLattice.getGlobalLoc(); - // if (globalLocId == null) { - // throw new - // Error("Global location element is not defined in the method " + - // md); - // } - // Location globalLoc = new Location(md, globalLocId); - // - // loc.addLocation(globalLoc); + // if 'static', assign the default GLOBAL LOCATION to the first + // element of the tuple + base.add(GLOBALDESC); } } else { // the location of field access starts from this, followed by field @@ -1679,6 +1685,10 @@ public class LocationInference { base.add(fd); } else if (d == null) { // access static field + base.add(GLOBALDESC); + // base.add(nn.getField()); + return base; + // FieldDescriptor fd = nn.getField();addFlowGraphEdge // // MethodLattice localLattice = ssjava.getMethodLattice(md); @@ -1726,10 +1736,10 @@ public class LocationInference { } } - // if (left instanceof ArrayAccessNode) { - // ArrayAccessNode aan = (ArrayAccessNode) left; - // left = aan.getExpression(); - // } + if (left instanceof ArrayAccessNode) { + ArrayAccessNode aan = (ArrayAccessNode) left; + left = aan.getExpression(); + } // fanNodeSet base = analyzeFlowExpressionNode(md, nametable, left, nodeSet, base, implicitFlowTupleSet, false); @@ -1737,12 +1747,11 @@ public class LocationInference { if (!left.getType().isPrimitive()) { if (fd.getSymbol().equals("length")) { - // TODO - // array.length access, return the location of the array - // return loc; + // array.length access, just have the location of the array + } else { + base.add(fd); } - base.add(fd); } getFlowGraph(md).createNewFlowNode(base); @@ -1750,12 +1759,15 @@ public class LocationInference { } + private void debug_printTreeNode(TreeNode tn) { + + System.out.println("DEBUG: " + tn.printNode(0) + " line#=" + tn.getNumLine()); + + } + private void analyzeFlowAssignmentNode(MethodDescriptor md, SymbolTable nametable, AssignmentNode an, NTuple base, NodeTupleSet implicitFlowTupleSet) { - // System.out.println("#an=" + an.printNode(0) + " an src=" + - // an.getSrc().printNode(0) + " dst=" - // + an.getDest().printNode(0)); NodeTupleSet nodeSetRHS = new NodeTupleSet(); NodeTupleSet nodeSetLHS = new NodeTupleSet(); diff --git a/Robust/src/Analysis/SSJava/MethodLocationInfo.java b/Robust/src/Analysis/SSJava/MethodLocationInfo.java index 986d4550..f4780e06 100644 --- a/Robust/src/Analysis/SSJava/MethodLocationInfo.java +++ b/Robust/src/Analysis/SSJava/MethodLocationInfo.java @@ -13,6 +13,7 @@ public class MethodLocationInfo extends LocationInfo { String returnLocName; String thisLocName; String PCLocName; + String globalLocName; Map mapParamIdxToLocName; Set paramLocNameSet; @@ -31,6 +32,11 @@ public class MethodLocationInfo extends LocationInfo { * public CompositeLocation getInferLocation(FlowNode node) { return * mapFlowNodeToLocation.get(node); } */ + + public void setGlobalLocName(String globalLocName) { + this.globalLocName = globalLocName; + } + public String getReturnLocName() { return returnLocName; } diff --git a/Robust/src/Analysis/SSJava/SSJavaAnalysis.java b/Robust/src/Analysis/SSJava/SSJavaAnalysis.java index c0fa9b3f..02123655 100644 --- a/Robust/src/Analysis/SSJava/SSJavaAnalysis.java +++ b/Robust/src/Analysis/SSJava/SSJavaAnalysis.java @@ -133,7 +133,7 @@ public class SSJavaAnalysis { init(); if (state.SSJAVADEBUG) { - // debugPrint(); + debug_printAnnotationRequiredSet(); } if (state.SSJAVAINFER) { inference(); @@ -243,11 +243,11 @@ public class SSJavaAnalysis { checker.linearTypeCheck(); } - public void debugPrint() { + public void debug_printAnnotationRequiredSet() { System.out.println("SSJAVA: SSJava is checking the following methods:"); for (Iterator iterator = annotationRequireSet.iterator(); iterator.hasNext();) { MethodDescriptor md = iterator.next(); - System.out.print(" " + md); + System.out.println(md); } System.out.println(); } -- 2.34.1