From 031636263ce6e4b6f35f3d9162460eb0ef536c2a Mon Sep 17 00:00:00 2001 From: yeom Date: Sat, 7 Jul 2012 02:08:11 +0000 Subject: [PATCH] a bunch of fixes. --- Robust/src/Analysis/SSJava/FlowGraph.java | 26 +- Robust/src/Analysis/SSJava/FlowNode.java | 11 + Robust/src/Analysis/SSJava/Location.java | 4 +- .../Analysis/SSJava/LocationInference.java | 298 ++++-- .../Analysis/SSJava/MethodLocationInfo.java | 73 ++ Robust/src/Analysis/SSJava/NodeTupleSet.java | 36 +- .../src/Analysis/SSJava/SSJavaAnalysis.java | 59 +- .../SSJava/SSJavaInferenceEngine.java | 921 ------------------ Robust/src/Analysis/SSJava/SSJavaLattice.java | 33 +- Robust/src/Util/Lattice.java | 12 +- 10 files changed, 431 insertions(+), 1042 deletions(-) create mode 100644 Robust/src/Analysis/SSJava/MethodLocationInfo.java delete mode 100644 Robust/src/Analysis/SSJava/SSJavaInferenceEngine.java diff --git a/Robust/src/Analysis/SSJava/FlowGraph.java b/Robust/src/Analysis/SSJava/FlowGraph.java index fb051631..ce0021ca 100644 --- a/Robust/src/Analysis/SSJava/FlowGraph.java +++ b/Robust/src/Analysis/SSJava/FlowGraph.java @@ -23,6 +23,7 @@ public class FlowGraph { MethodDescriptor md; Set nodeSet; + Set returnNodeSet; FlowNode thisVarNode; // maps the composite representation of field/var descriptors to infer nodes @@ -37,11 +38,12 @@ public class FlowGraph { public FlowGraph(MethodDescriptor md, Map mapParamDescToIdx) { this.md = md; - nodeSet = new HashSet(); - mapDescTupleToInferNode = new HashMap, FlowNode>(); - mapNodeToNeighborSet = new HashMap, Set>(); + this.nodeSet = new HashSet(); + this.mapDescTupleToInferNode = new HashMap, FlowNode>(); + this.mapNodeToNeighborSet = new HashMap, Set>(); this.mapParamDescToIdx = new HashMap(); this.mapParamDescToIdx.putAll(mapParamDescToIdx); + this.returnNodeSet = new HashSet(); // create a node for 'this' varialbe NTuple thisDescTuple = new NTuple(); @@ -168,6 +170,22 @@ public class FlowGraph { } + public void setReturnFlowNode(NTuple tuple) { + + if (!mapDescTupleToInferNode.containsKey(tuple)) { + createNewFlowNode(tuple); + } + + FlowNode node = mapDescTupleToInferNode.get(tuple); + node.setReturn(true); + + returnNodeSet.add(node); + } + + public Set getReturnNodeSet() { + return returnNodeSet; + } + public boolean isParamter(NTuple tuple) { // return true if a descriptor tuple is started with a parameter descriptor Descriptor firstIdxDesc = tuple.get(0); @@ -220,7 +238,7 @@ public class FlowGraph { public void writeGraph() throws java.io.IOException { - String graphName = md.toString(); + String graphName = "flowgraph_" + md.toString(); graphName = graphName.replaceAll("[\\W]", ""); BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot")); diff --git a/Robust/src/Analysis/SSJava/FlowNode.java b/Robust/src/Analysis/SSJava/FlowNode.java index 21a2e089..eb9c2a7e 100644 --- a/Robust/src/Analysis/SSJava/FlowNode.java +++ b/Robust/src/Analysis/SSJava/FlowNode.java @@ -18,6 +18,9 @@ public class FlowNode { // set true if this node is driven from a paramter private boolean isParameter; + // set true if this node stores a return value + private boolean isReturn; + public Set getFieldNodeSet() { return fieldNodeSet; } @@ -63,6 +66,14 @@ public class FlowNode { return descTuple.get(descTuple.size() - 1); } + public boolean isReturn() { + return isReturn; + } + + public void setReturn(boolean isReturn) { + this.isReturn = isReturn; + } + public String toString() { String rtr = "[FlowNode]:"; if (isParameter()) { diff --git a/Robust/src/Analysis/SSJava/Location.java b/Robust/src/Analysis/SSJava/Location.java index 271b447f..fbab568e 100644 --- a/Robust/src/Analysis/SSJava/Location.java +++ b/Robust/src/Analysis/SSJava/Location.java @@ -23,9 +23,9 @@ public class Location implements TypeExtension { this.d = d; this.type = type; if (type == TOP) { - loc = SSJavaLattice.TOP; + loc = SSJavaAnalysis.TOP; } else if (type == BOTTOM) { - loc = SSJavaLattice.BOTTOM; + loc = SSJavaAnalysis.BOTTOM; } } diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index daa435f0..089e7f8b 100644 --- a/Robust/src/Analysis/SSJava/LocationInference.java +++ b/Robust/src/Analysis/SSJava/LocationInference.java @@ -25,7 +25,6 @@ import IR.State; import IR.SymbolTable; import IR.TypeDescriptor; import IR.VarDescriptor; -import IR.Flat.FlatMethod; import IR.Tree.ArrayAccessNode; import IR.Tree.AssignmentNode; import IR.Tree.BlockExpressionNode; @@ -69,22 +68,16 @@ public class LocationInference { // map a method descriptor to a method lattice private Map> md2lattice; - // map a method descriptor to a lattice mapping - private Map> md2LatticeMapping; - - // map a method descriptor to a lattice mapping - private Map> cd2LatticeMapping; - - // map a method descriptor to the set of hierarchy relations that are - // contributed from the callee - private Map> mapMethodDescriptorToCalleeParamRelationSet; - // map a method descriptor to the set of method invocation nodes which are // invoked by the method descriptor private Map> mapMethodDescriptorToMethodInvokeNodeSet; private Map>> mapMethodInvokeNodeToArgIdxMap; + private Map mapLatticeToMethodLocationInfo; + + private Map> mapMethodDescToPossibleMethodDescSet; + boolean debug = true; public LocationInference(SSJavaAnalysis ssjava, State state) { @@ -96,15 +89,13 @@ public class LocationInference { this.cd2lattice = new HashMap>(); this.md2lattice = new HashMap>(); this.methodDescriptorsToVisitStack = new Stack(); - this.md2LatticeMapping = new HashMap>(); - this.cd2LatticeMapping = new HashMap>(); - this.mapMethodDescriptorToCalleeParamRelationSet = - new HashMap>(); this.mapMethodDescriptorToMethodInvokeNodeSet = new HashMap>(); this.mapMethodInvokeNodeToArgIdxMap = new HashMap>>(); - + this.mapLatticeToMethodLocationInfo = new HashMap(); + this.mapMethodDescToPossibleMethodDescSet = + new HashMap>(); } public void setupToAnalyze() { @@ -156,6 +147,30 @@ public class LocationInference { debug_writeLatticeDotFile(); + // 3) check properties + checkLattices(); + + } + + private void checkLattices() { + + LinkedList descriptorListToAnalyze = ssjava.getSortedDescriptors(); + + // current descriptors to visit in fixed-point interprocedural analysis, + // prioritized by + // dependency in the call graph + methodDescriptorsToVisitStack.clear(); + + descriptorListToAnalyze.removeFirst(); + + Set methodDescriptorToVistSet = new HashSet(); + methodDescriptorToVistSet.addAll(descriptorListToAnalyze); + + while (!descriptorListToAnalyze.isEmpty()) { + MethodDescriptor md = descriptorListToAnalyze.removeFirst(); + checkLatticesOfVirtualMethods(md); + } + } private void debug_writeLatticeDotFile() { @@ -190,7 +205,6 @@ public class LocationInference { // do fixed-point analysis - // perform method READ/OVERWRITE analysis LinkedList descriptorListToAnalyze = ssjava.getSortedDescriptors(); // current descriptors to visit in fixed-point interprocedural analysis, @@ -214,7 +228,7 @@ public class LocationInference { MethodDescriptor md = methodDescriptorsToVisitStack.pop(); SSJavaLattice methodLattice = - new SSJavaLattice(SSJavaLattice.TOP, SSJavaLattice.BOTTOM); + new SSJavaLattice(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM); System.out.println(); System.out.println("SSJAVA: Inferencing the lattice from " + md); @@ -224,7 +238,8 @@ public class LocationInference { SSJavaLattice prevMethodLattice = getMethodLattice(md); if (!methodLattice.equals(prevMethodLattice)) { - md2lattice.put(md, methodLattice); + + setMethodLattice(md, methodLattice); // results for callee changed, so enqueue dependents caller for // further analysis @@ -243,6 +258,61 @@ public class LocationInference { } + private void checkLatticesOfVirtualMethods(MethodDescriptor md) { + + if (!md.isStatic()) { + Set setPossibleCallees = new HashSet(); + setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md)); + + for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) { + MethodDescriptor mdCallee = (MethodDescriptor) iterator.next(); + if (!md.equals(mdCallee)) { + checkConsistency(md, mdCallee); + } + } + + } + + } + + private void checkConsistency(MethodDescriptor md1, MethodDescriptor md2) { + + // check that two lattice have the same relations between parameters(+PC + // LOC, RETURN LOC) + + MethodLocationInfo methodInfo1 = getMethodLocationInfo(md1); + + SSJavaLattice lattice1 = getMethodLattice(md1); + SSJavaLattice lattice2 = getMethodLattice(md2); + + Set paramLocNameSet1 = methodInfo1.getParameterLocNameSet(); + + for (Iterator iterator = paramLocNameSet1.iterator(); iterator.hasNext();) { + String locName1 = (String) iterator.next(); + for (Iterator iterator2 = paramLocNameSet1.iterator(); iterator2.hasNext();) { + String locName2 = (String) iterator2.next(); + + // System.out.println("COMPARE " + locName1 + " - " + locName2 + " " + // + lattice1.isGreaterThan(locName1, locName2) + "-" + // + lattice2.isGreaterThan(locName1, locName2)); + + if (!locName1.equals(locName2)) { + + boolean r1 = lattice1.isGreaterThan(locName1, locName2); + boolean r2 = lattice2.isGreaterThan(locName1, locName2); + + 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 + "."); + } + } + + } + } + + } + private String getSymbol(int idx, FlowNode node) { Descriptor desc = node.getDescTuple().get(idx); return desc.getSymbol(); @@ -250,12 +320,13 @@ public class LocationInference { private void analyzeMethodLattice(MethodDescriptor md, SSJavaLattice methodLattice) { + MethodLocationInfo methodInfo = getMethodLocationInfo(md); + // first take a look at method invocation nodes to newly added relations // from the callee analyzeLatticeMethodInvocationNode(md); // visit each node of method flow graph - FlowGraph fg = getFlowGraph(md); Set nodeSet = fg.getNodeSet(); @@ -264,18 +335,65 @@ public class LocationInference { for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { FlowNode srcNode = (FlowNode) iterator.next(); - // first, take a look at directly connected nodes Set outEdgeSet = srcNode.getOutEdgeSet(); for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) { FlowEdge outEdge = (FlowEdge) iterator2.next(); FlowNode dstNode = outEdge.getDst(); - addRelationToLattice(md, methodLattice, srcNode, dstNode); + NTuple srcNodeTuple = srcNode.getDescTuple(); + NTuple dstNodeTuple = dstNode.getDescTuple(); + + if (outEdge.getInitTuple().equals(srcNodeTuple) + && outEdge.getEndTuple().equals(dstNodeTuple)) { + + if ((srcNodeTuple.size() > 1 && dstNodeTuple.size() > 1) + && srcNodeTuple.get(0).equals(dstNodeTuple.get(0))) { + + // value flows between fields + VarDescriptor varDesc = (VarDescriptor) srcNodeTuple.get(0); + ClassDescriptor varClassDesc = varDesc.getType().getClassDesc(); + extractRelationFromFieldFlows(varClassDesc, srcNode, dstNode, 1); + + } else { + // in this case, take a look at connected nodes at the local level + addRelationToLattice(md, methodLattice, srcNode, dstNode); + } + + } } } + // grab the this location if the method use the 'this' reference + String thisLocSymbol = md.getThis().getSymbol(); + if (methodLattice.getKeySet().contains(thisLocSymbol)) { + methodInfo.setThisLocName(thisLocSymbol); + } + + // calculate a return location + if (!md.getReturnType().isVoid()) { + Set returnNodeSet = fg.getReturnNodeSet(); + Set returnVarSymbolSet = new HashSet(); + + for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { + FlowNode rtrNode = (FlowNode) iterator.next(); + String localSymbol = rtrNode.getDescTuple().get(0).getSymbol(); + returnVarSymbolSet.add(localSymbol); + } + + String returnGLB = methodLattice.getGLB(returnVarSymbolSet); + if (returnGLB.equals(SSJavaAnalysis.BOTTOM)) { + // 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); + methodInfo.setReturnLocName(returnNewLocationSymbol); + } else { + methodInfo.setReturnLocName(returnGLB); + } + } + } private void analyzeLatticeMethodInvocationNode(MethodDescriptor mdCaller) { @@ -327,9 +445,10 @@ public class LocationInference { String paramSymbol1 = getSymbol(0, paramFlowNode1); String paramSymbol2 = getSymbol(0, paramFlowNode2); - // if two parameters have relation, we need to propagate this relation + // if two parameters have a relation, we need to propagate this relation // to the caller - if (calleeLattice.isComparable(paramSymbol1, paramSymbol2)) { + if (!(paramSymbol1.equals(paramSymbol2)) + && calleeLattice.isComparable(paramSymbol1, paramSymbol2)) { int higherLocIdxCallee; int lowerLocIdxCallee; if (calleeLattice.isGreaterThan(paramSymbol1, paramSymbol2)) { @@ -353,55 +472,86 @@ public class LocationInference { } - private void addRelationToLattice(MethodDescriptor md, SSJavaLattice methodLattice, - FlowNode srcNode, FlowNode dstNode) { - if ((srcNode.getDescTuple().size() > 1 && dstNode.getDescTuple().size() > 1) - && srcNode.getDescTuple().get(0).equals(dstNode.getDescTuple().get(0))) { - // value flow between fields: we don't need to add a binary relation - // for this case - - VarDescriptor varDesc = (VarDescriptor) srcNode.getDescTuple().get(0); - ClassDescriptor varClassDesc = varDesc.getType().getClassDesc(); + private MethodLocationInfo getMethodLocationInfo(MethodDescriptor md) { - extractRelationFromFieldFlows(varClassDesc, srcNode, dstNode, 1); - return; + if (!mapLatticeToMethodLocationInfo.containsKey(md)) { + mapLatticeToMethodLocationInfo.put(md, new MethodLocationInfo(md)); } - // add a new binary relation of dstNode < srcNode + return mapLatticeToMethodLocationInfo.get(md); + + } + private void addRelationToLattice(MethodDescriptor md, SSJavaLattice methodLattice, + FlowNode srcNode, FlowNode dstNode) { + + // add a new binary relation of dstNode < srcNode String srcSymbol = getSymbol(0, srcNode); String dstSymbol = getSymbol(0, dstNode); - methodLattice.addRelationHigherToLower(srcSymbol, dstSymbol); + FlowGraph flowGraph = getFlowGraph(md); + MethodLocationInfo methodInfo = getMethodLocationInfo(md); + + if (srcNode.isParameter()) { + int paramIdx = flowGraph.getParamIdx(srcNode.getDescTuple()); + methodInfo.addParameter(srcSymbol, srcNode, paramIdx); + } + if (dstNode.isParameter()) { + int paramIdx = flowGraph.getParamIdx(dstNode.getDescTuple()); + methodInfo.addParameter(dstSymbol, dstNode, paramIdx); + } + + if (!methodLattice.isGreaterThan(srcSymbol, dstSymbol)) { + // if the lattice does not have this relation, add it + methodLattice.addRelationHigherToLower(srcSymbol, dstSymbol); + } } private SSJavaLattice getMethodLattice(MethodDescriptor md) { - if (!md2lattice.containsKey(md)) { - md2lattice.put(md, new SSJavaLattice(SSJavaLattice.TOP, SSJavaLattice.BOTTOM)); + md2lattice.put(md, new SSJavaLattice(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM)); } return md2lattice.get(md); } + private void setMethodLattice(MethodDescriptor md, SSJavaLattice lattice) { + md2lattice.put(md, lattice); + } + private void extractRelationFromFieldFlows(ClassDescriptor cd, FlowNode srcNode, FlowNode dstNode, int idx) { - if (srcNode.getDescTuple().get(idx).equals(dstNode.getDescTuple().get(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 // for this case - VarDescriptor varDesc = (VarDescriptor) srcNode.getDescTuple().get(idx); - ClassDescriptor varClassDesc = varDesc.getType().getClassDesc(); - extractRelationFromFieldFlows(varClassDesc, srcNode, dstNode, idx + 1); + + Descriptor desc = srcNode.getDescTuple().get(idx); + ClassDescriptor classDesc; + + if (idx == 0) { + classDesc = ((VarDescriptor) desc).getType().getClassDesc(); + } else { + classDesc = ((FieldDescriptor) desc).getType().getClassDesc(); + } + + extractRelationFromFieldFlows(classDesc, srcNode, dstNode, idx + 1); + } else { Descriptor srcFieldDesc = srcNode.getDescTuple().get(idx); Descriptor dstFieldDesc = dstNode.getDescTuple().get(idx); // add a new binary relation of dstNode < srcNode - SSJavaLattice fieldLattice = getFieldLattice(cd); - fieldLattice.addRelationHigherToLower(srcFieldDesc.getSymbol(), dstFieldDesc.getSymbol()); + + String srcSymbol = srcFieldDesc.getSymbol(); + String dstSymbol = dstFieldDesc.getSymbol(); + + if (!fieldLattice.isGreaterThan(srcSymbol, dstSymbol)) { + fieldLattice.addRelationHigherToLower(srcSymbol, dstSymbol); + } } @@ -409,7 +559,7 @@ public class LocationInference { public SSJavaLattice getFieldLattice(ClassDescriptor cd) { if (!cd2lattice.containsKey(cd)) { - cd2lattice.put(cd, new SSJavaLattice(SSJavaLattice.TOP, SSJavaLattice.BOTTOM)); + cd2lattice.put(cd, new SSJavaLattice(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM)); } return cd2lattice.get(cd); } @@ -426,11 +576,20 @@ public class LocationInference { MethodDescriptor md = toAnalyzeMethodNext(); if (ssjava.needTobeAnnotated(md)) { if (state.SSJAVADEBUG) { + System.out.println(); System.out.println("SSJAVA: Constructing a flow graph: " + md); } - // creates a mapping from a parameter descriptor to its index + // creates a mapping from a method descriptor to virtual methods + Set setPossibleCallees = new HashSet(); + if (md.isStatic()) { + setPossibleCallees.add(md); + } else { + setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md)); + } + mapMethodDescToPossibleMethodDescSet.put(md, setPossibleCallees); + // creates a mapping from a parameter descriptor to its index Map mapParamDescToIdx = new HashMap(); int offset = md.isStatic() ? 0 : 1; for (int i = 0; i < md.numParameters(); i++) { @@ -487,7 +646,7 @@ public class LocationInference { break; case Kind.ReturnNode: - analyzeReturnNode(md, nametable, (ReturnNode) bsn); + analyzeFlowReturnNode(md, nametable, (ReturnNode) bsn, implicitFlowTupleSet); break; case Kind.SubBlockNode: @@ -515,8 +674,25 @@ public class LocationInference { analyzeFlowBlockNode(md, nametable, sbn.getBlockNode(), implicitFlowTupleSet); } - private void analyzeReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode bsn) { - // TODO Auto-generated method stub + private void analyzeFlowReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode rn, + NodeTupleSet implicitFlowTupleSet) { + + ExpressionNode returnExp = rn.getReturnExpression(); + + NodeTupleSet nodeSet = new NodeTupleSet(); + analyzeFlowExpressionNode(md, nametable, returnExp, nodeSet, false); + + 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); + } + } } @@ -609,7 +785,7 @@ public class LocationInference { // note that expression node can create more than one flow node // nodeSet contains of flow nodes - // base is always assigned to null except name node case! + // base is always assigned to null except the case of a name node! NTuple flowTuple; @@ -694,15 +870,12 @@ public class LocationInference { private void analyzeFlowTertiaryNode(MethodDescriptor md, SymbolTable nametable, TertiaryNode tn, NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) { - System.out.println("### analyzeFlowTertiaryNode=" + tn.printNode(0)); - NodeTupleSet tertiaryTupleNode = new NodeTupleSet(); analyzeFlowExpressionNode(md, nametable, tn.getCond(), tertiaryTupleNode, null, implicitFlowTupleSet, false); // add edges from tertiaryTupleNode to all nodes of conditional nodes tertiaryTupleNode.addTupleSet(implicitFlowTupleSet); - System.out.println("### TertiarayNode's condition=" + tertiaryTupleNode); analyzeFlowExpressionNode(md, nametable, tn.getTrueExpr(), tertiaryTupleNode, null, implicitFlowTupleSet, false); @@ -743,7 +916,6 @@ public class LocationInference { if (min.getExpression() != null) { NodeTupleSet baseNodeSet = new NodeTupleSet(); - System.out.println("Analyzing base of method=" + min.getExpression()); analyzeFlowExpressionNode(calleeMD, nametable, min.getExpression(), baseNodeSet, null, implicitFlowTupleSet, false); @@ -880,17 +1052,13 @@ public class LocationInference { NodeTupleSet rightOpSet = new NodeTupleSet(); // left operand - System.out.println("Analyzing left op=" + on.getLeft().printNode(0) + "::" - + on.getLeft().getClass()); analyzeFlowExpressionNode(md, nametable, on.getLeft(), leftOpSet, null, implicitFlowTupleSet, false); - System.out.println("leftOpSet=" + leftOpSet); if (on.getRight() != null) { // right operand analyzeFlowExpressionNode(md, nametable, on.getRight(), rightOpSet, null, implicitFlowTupleSet, false); - System.out.println("rightOpSet=" + rightOpSet); } Operation op = on.getOp(); @@ -1058,6 +1226,7 @@ public class LocationInference { base.add(fd); } + getFlowGraph(md).createNewFlowNode(base); return base; } @@ -1065,8 +1234,6 @@ public class LocationInference { private void analyzeFlowAssignmentNode(MethodDescriptor md, SymbolTable nametable, AssignmentNode an, NTuple base, NodeTupleSet implicitFlowTupleSet) { - System.out.println("analyzeFlowAssignmentNode=" + an); - NodeTupleSet nodeSetRHS = new NodeTupleSet(); NodeTupleSet nodeSetLHS = new NodeTupleSet(); @@ -1081,13 +1248,11 @@ public class LocationInference { // and its index value analyzeFlowExpressionNode(md, nametable, an.getDest(), nodeSetLHS, null, implicitFlowTupleSet, true); - System.out.println("ASSIGNMENT NODE nodeSetLHS=" + nodeSetLHS); if (!postinc) { // analyze value flows of rhs expression analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null, implicitFlowTupleSet, false); - System.out.println("ASSIGNMENT NODE nodeSetRHS=" + nodeSetRHS); // creates edges from RHS to LHS for (Iterator> iter = nodeSetRHS.iterator(); iter.hasNext();) { @@ -1122,7 +1287,7 @@ public class LocationInference { return mapMethodDescriptorToFlowGraph.get(md); } - public boolean addFlowGraphEdge(MethodDescriptor md, NTuple from, + private boolean addFlowGraphEdge(MethodDescriptor md, NTuple from, NTuple to) { // TODO // return true if it adds a new edge @@ -1147,8 +1312,3 @@ public class LocationInference { } } - -class ParamIndexRelation { - private Integer higherIdx; - private Integer lowerIdx; -} diff --git a/Robust/src/Analysis/SSJava/MethodLocationInfo.java b/Robust/src/Analysis/SSJava/MethodLocationInfo.java new file mode 100644 index 00000000..ad78508b --- /dev/null +++ b/Robust/src/Analysis/SSJava/MethodLocationInfo.java @@ -0,0 +1,73 @@ +package Analysis.SSJava; + +import java.util.HashMap; +import java.util.HashSet; +import java.util.Map; +import java.util.Set; + +import IR.MethodDescriptor; + +public class MethodLocationInfo { + + String returnLocName; + String thisLocName; + String PCLocName; + Map mapParamIdxToLocName; + Map mapLocNameToFlowNode; + MethodDescriptor md; + + public MethodLocationInfo(MethodDescriptor md) { + this.md = md; + this.mapParamIdxToLocName = new HashMap(); + this.mapLocNameToFlowNode = new HashMap(); + this.PCLocName = SSJavaAnalysis.TOP; + } + + public String getReturnLocName() { + return returnLocName; + } + + public void setReturnLocName(String returnLocName) { + this.returnLocName = returnLocName; + } + + public String getThisLocName() { + return thisLocName; + } + + public void setThisLocName(String thisLocName) { + this.thisLocName = thisLocName; + } + + public String getPCLocName() { + return PCLocName; + } + + public void setPCLocName(String pCLocName) { + PCLocName = pCLocName; + } + + public void addParameter(String name, FlowNode node, int idx) { + mapParamIdxToLocName.put(new Integer(idx), name); + mapLocNameToFlowNode.put(name, node); + } + + public Set getParameterLocNameSet() { + Set paramSet = new HashSet(); + + paramSet.add(PCLocName); + + if (thisLocName != null) { + paramSet.add(thisLocName); + } + + if (returnLocName != null) { + paramSet.add(returnLocName); + } + + paramSet.addAll(mapLocNameToFlowNode.keySet()); + + return paramSet; + } + +} diff --git a/Robust/src/Analysis/SSJava/NodeTupleSet.java b/Robust/src/Analysis/SSJava/NodeTupleSet.java index 68509604..3040a15a 100644 --- a/Robust/src/Analysis/SSJava/NodeTupleSet.java +++ b/Robust/src/Analysis/SSJava/NodeTupleSet.java @@ -1,51 +1,53 @@ package Analysis.SSJava; +import java.util.ArrayList; import java.util.HashSet; import java.util.Iterator; +import java.util.List; import java.util.Set; import IR.Descriptor; public class NodeTupleSet { - private Set> set; + private List> list; public NodeTupleSet() { - set = new HashSet>(); + list = new ArrayList>(); } public void addTuple(NTuple tuple) { - // need to add additional elements because we need to create edges even from - // the base - // for example, if we have input , we need to add additional element - // and to the set - - // NTuple cur = new NTuple(); - // for (int i = 0; i < tuple.size(); i++) { - // Descriptor d = tuple.get(i); - // cur.add(d); - // set.add(new NTuple(cur)); - // } + for (Iterator iterator = list.iterator(); iterator.hasNext();) { + NTuple t = (NTuple) iterator.next(); + if (t.equals(tuple)) { + return; + } + } - set.add(tuple); + list.add(tuple); } public Iterator> iterator() { - return set.iterator(); + return list.iterator(); } public String toString() { - return set.toString(); + return list.toString(); } public Set> getSet() { + Set> set = new HashSet>(); + set.addAll(list); return set; } public void addTupleSet(NodeTupleSet in) { if (in != null) { - set.addAll(in.getSet()); + for (Iterator iterator = in.iterator(); iterator.hasNext();) { + NTuple inTuple = (NTuple) iterator.next(); + addTuple(inTuple); + } } } } diff --git a/Robust/src/Analysis/SSJava/SSJavaAnalysis.java b/Robust/src/Analysis/SSJava/SSJavaAnalysis.java index b72f077a..c0fa9b3f 100644 --- a/Robust/src/Analysis/SSJava/SSJavaAnalysis.java +++ b/Robust/src/Analysis/SSJava/SSJavaAnalysis.java @@ -48,6 +48,9 @@ public class SSJavaAnalysis { public static final String DELEGATETHIS = "DELEGATETHIS"; public static final String TRUST = "TRUST"; + public static final String TOP = "_top_"; + public static final String BOTTOM = "_bottom_"; + State state; TypeUtil tu; FlowDownCheck flowDownChecker; @@ -277,7 +280,7 @@ public class SSJavaAnalysis { String marker = an.getMarker(); if (marker.equals(LATTICE)) { SSJavaLattice locOrder = - new SSJavaLattice(SSJavaLattice.TOP, SSJavaLattice.BOTTOM); + new SSJavaLattice(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM); cd2lattice.put(cd, locOrder); parseClassLatticeDefinition(cd, an.getValue(), locOrder); @@ -288,7 +291,7 @@ public class SSJavaAnalysis { } else if (marker.equals(METHODDEFAULT)) { MethodLattice locOrder = - new MethodLattice(SSJavaLattice.TOP, SSJavaLattice.BOTTOM); + new MethodLattice(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM); cd2methodDefault.put(cd, locOrder); parseMethodDefaultLatticeDefinition(cd, an.getValue(), locOrder); } @@ -306,7 +309,7 @@ public class SSJavaAnalysis { if (an.getMarker().equals(LATTICE)) { // developer explicitly defines method lattice MethodLattice locOrder = - new MethodLattice(SSJavaLattice.TOP, SSJavaLattice.BOTTOM); + new MethodLattice(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM); md2lattice.put(md, locOrder); parseMethodDefaultLatticeDefinition(cd, an.getValue(), locOrder); } else if (an.getMarker().equals(TERMINATE)) { @@ -327,8 +330,8 @@ public class SSJavaAnalysis { } } - public void writeLatticeDotFile(ClassDescriptor cd, MethodDescriptor md, - SSJavaLattice locOrder) { + public void writeLatticeDotFile(ClassDescriptor cd, MethodDescriptor md, + SSJavaLattice locOrder) { String fileName = "lattice_"; if (md != null) { @@ -338,32 +341,40 @@ public class SSJavaAnalysis { fileName += cd.getSymbol().replaceAll("[\\W_]", ""); } - Set> pairSet = locOrder.getOrderingPairSet(); + Set> pairSet = locOrder.getOrderingPairSet(); - try { - BufferedWriter bw = new BufferedWriter(new FileWriter(fileName + ".dot")); + if (pairSet.size() > 0) { + try { + BufferedWriter bw = new BufferedWriter(new FileWriter(fileName + ".dot")); - bw.write("digraph " + fileName + " {\n"); + bw.write("digraph " + fileName + " {\n"); - for (Iterator iterator = pairSet.iterator(); iterator.hasNext();) { - // pair is in the form of - Pair pair = (Pair) iterator.next(); + for (Iterator iterator = pairSet.iterator(); iterator.hasNext();) { + // pair is in the form of + Pair pair = (Pair) iterator.next(); - String highLocId = pair.getFirst(); - if (locOrder.isSharedLoc(highLocId)) { - highLocId = "\"" + highLocId + "*\""; - } - String lowLocId = pair.getSecond(); - if (locOrder.isSharedLoc(lowLocId)) { - lowLocId = "\"" + lowLocId + "*\""; + T highLocId = pair.getFirst(); + String highLocStr, lowLocStr; + if (locOrder.isSharedLoc(highLocId)) { + highLocStr = "\"" + highLocId + "*\""; + } else { + highLocStr = highLocId.toString(); + } + T lowLocId = pair.getSecond(); + if (locOrder.isSharedLoc(lowLocId)) { + lowLocStr = "\"" + lowLocId + "*\""; + } else { + lowLocStr = lowLocId.toString(); + } + bw.write(highLocId + " -> " + lowLocId + ";\n"); } - bw.write(highLocId + " -> " + lowLocId + ";\n"); + bw.write("}\n"); + bw.close(); + + } catch (IOException e) { + e.printStackTrace(); } - bw.write("}\n"); - bw.close(); - } catch (IOException e) { - e.printStackTrace(); } } diff --git a/Robust/src/Analysis/SSJava/SSJavaInferenceEngine.java b/Robust/src/Analysis/SSJava/SSJavaInferenceEngine.java deleted file mode 100644 index 369473cd..00000000 --- a/Robust/src/Analysis/SSJava/SSJavaInferenceEngine.java +++ /dev/null @@ -1,921 +0,0 @@ -package Analysis.SSJava; - -import java.io.FileWriter; -import java.io.IOException; -import java.io.PrintWriter; -import java.util.ArrayList; -import java.util.Collections; -import java.util.Comparator; -import java.util.HashSet; -import java.util.Hashtable; -import java.util.Iterator; -import java.util.List; -import java.util.Set; - -import IR.ClassDescriptor; -import IR.Descriptor; -import IR.FieldDescriptor; -import IR.MethodDescriptor; -import IR.NameDescriptor; -import IR.Operation; -import IR.State; -import IR.SymbolTable; -import IR.VarDescriptor; -import IR.Tree.ArrayAccessNode; -import IR.Tree.AssignmentNode; -import IR.Tree.BlockExpressionNode; -import IR.Tree.BlockNode; -import IR.Tree.BlockStatementNode; -import IR.Tree.CastNode; -import IR.Tree.DeclarationNode; -import IR.Tree.ExpressionNode; -import IR.Tree.IfStatementNode; -import IR.Tree.Kind; -import IR.Tree.LiteralNode; -import IR.Tree.LoopNode; -import IR.Tree.NameNode; -import IR.Tree.OpNode; -import IR.Tree.ReturnNode; -import IR.Tree.SubBlockNode; -import IR.Tree.SwitchStatementNode; -import IR.Tree.SwitchBlockNode; - -public class SSJavaInferenceEngine { - - State state; - static SSJavaAnalysis ssjava; - - Set toanalyze; - List toanalyzeList; - - Set toanalyzeMethod; - List toanalyzeMethodList; - - // mapping from 'descriptor' to 'composite location' - Hashtable d2loc; - - Hashtable md2ReturnLoc; - Hashtable md2ReturnLocGen; - - // mapping from 'locID' to 'class descriptor' - Hashtable fieldLocName2cd; - - private Set implicitFlowSet; /* - * should maybe be - * hashtable> - */ - private RelationSet rSet; - - boolean deterministic = true; - - public SSJavaInferenceEngine(SSJavaAnalysis ssjava, State state) { - this.ssjava = ssjava; - this.state = state; - if (deterministic) { - this.toanalyzeList = new ArrayList(); - } else { - this.toanalyze = new HashSet(); - } - if (deterministic) { - this.toanalyzeMethodList = new ArrayList(); - } else { - this.toanalyzeMethod = new HashSet(); - } - this.d2loc = new Hashtable(); - this.fieldLocName2cd = new Hashtable(); - this.md2ReturnLoc = new Hashtable(); - this.md2ReturnLocGen = new Hashtable(); - this.implicitFlowSet = new HashSet(); - this.rSet = new RelationSet(); - } - - public void init() { - - // construct mapping from the location name to the class descriptor - // assume that the location name is unique through the whole program - - Set cdSet = ssjava.getCd2lattice().keySet(); - for (Iterator iterator = cdSet.iterator(); iterator.hasNext();) { - ClassDescriptor cd = (ClassDescriptor) iterator.next(); - SSJavaLattice lattice = ssjava.getCd2lattice().get(cd); - Set fieldLocNameSet = lattice.getKeySet(); - - for (Iterator iterator2 = fieldLocNameSet.iterator(); iterator2.hasNext();) { - String fieldLocName = (String) iterator2.next(); - fieldLocName2cd.put(fieldLocName, cd); - } - - } - - } - - public boolean toAnalyzeIsEmpty() { - if (deterministic) { - return toanalyzeList.isEmpty(); - } else { - return toanalyze.isEmpty(); - } - } - - public ClassDescriptor toAnalyzeNext() { - if (deterministic) { - return toanalyzeList.remove(0); - } else { - ClassDescriptor cd = toanalyze.iterator().next(); - toanalyze.remove(cd); - return cd; - } - } - - public void setupToAnalyze() { - SymbolTable classtable = state.getClassSymbolTable(); - if (deterministic) { - toanalyzeList.clear(); - toanalyzeList.addAll(classtable.getValueSet()); - Collections.sort(toanalyzeList, new Comparator() { - public int compare(ClassDescriptor o1, ClassDescriptor o2) { - return o1.getClassName().compareTo(o2.getClassName()); - } - }); - } else { - toanalyze.clear(); - toanalyze.addAll(classtable.getValueSet()); - } - } - - public void setupToAnalazeMethod(ClassDescriptor cd) { - - SymbolTable methodtable = cd.getMethodTable(); - if (deterministic) { - toanalyzeMethodList.clear(); - toanalyzeMethodList.addAll(methodtable.getValueSet()); - Collections.sort(toanalyzeMethodList, new Comparator() { - public int compare(MethodDescriptor o1, MethodDescriptor o2) { - return o1.getSymbol().compareTo(o2.getSymbol()); - } - }); - } else { - toanalyzeMethod.clear(); - toanalyzeMethod.addAll(methodtable.getValueSet()); - } - } - - public boolean toAnalyzeMethodIsEmpty() { - if (deterministic) { - return toanalyzeMethodList.isEmpty(); - } else { - return toanalyzeMethod.isEmpty(); - } - } - - public MethodDescriptor toAnalyzeMethodNext() { - if (deterministic) { - return toanalyzeMethodList.remove(0); - } else { - MethodDescriptor md = toanalyzeMethod.iterator().next(); - toanalyzeMethod.remove(md); - return md; - } - } - - public void inference() { - FileWriter latticeFile; - PrintWriter latticeOut; - setupToAnalyze(); - - while (!toAnalyzeIsEmpty()) { - ClassDescriptor cd = toAnalyzeNext(); - try { - latticeFile = new FileWriter(cd.getClassName() + ".lat"); - } catch (IOException e) { - System.out.println("File Fail"); - return; - } - latticeOut = new PrintWriter(latticeFile); - if (ssjava.needToBeAnnoated(cd)) { - setupToAnalazeMethod(cd); - while (!toAnalyzeMethodIsEmpty()) { - MethodDescriptor md = toAnalyzeMethodNext(); - if (ssjava.needTobeAnnotated(md)) { - inferRelationsFromBlockNode(md, md.getParameterTable(), state.getMethodBody(md)); - latticeOut.println(md.getClassMethodName() + "\n"); - latticeOut.println(rSet.toString()); - rSet = new RelationSet(); - } - } - } - latticeOut.flush(); - latticeOut.close(); - } - } - - private void inferRelationsFromBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn) { - - bn.getVarTable().setParent(nametable); - for (int i = 0; i < bn.size(); i++) { - BlockStatementNode bsn = bn.get(i); - inferRelationsFromBlockStatementNode(md, bn.getVarTable(), bsn); - } - - } - - private void inferRelationsFromBlockStatementNode(MethodDescriptor md, SymbolTable nametable, - BlockStatementNode bsn) { - - switch (bsn.kind()) { - case Kind.BlockExpressionNode: - inferRelationsFromBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn); - break; - - case Kind.DeclarationNode: - inferRelationsFromDeclarationNode(md, nametable, (DeclarationNode) bsn); - break; - - case Kind.IfStatementNode: - inferRelationsFromIfStatementNode(md, nametable, (IfStatementNode) bsn); - break; - - case Kind.LoopNode: - inferRelationsFromLoopNode(md, nametable, (LoopNode) bsn); - break; - - case Kind.ReturnNode: - inferRelationsFromReturnNode(md, nametable, (ReturnNode) bsn); - break; - - case Kind.SubBlockNode: - inferRelationsFromSubBlockNode(md, nametable, (SubBlockNode) bsn); - break; - - case Kind.SwitchStatementNode: - inferRelationsFromSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn); - break; - - default: - System.out.println(bsn.kind() + " not handled..."); - break; - } - } - - private void inferRelationsFromSwitchStatementNode(MethodDescriptor md, - SymbolTable nametable, SwitchStatementNode ssn) { - - ClassDescriptor cd = md.getClassDesc(); - VarID condID = - inferRelationsFromExpressionNode(md, nametable, ssn.getCondition(), null, (BlockStatementNode) ssn, false); - BlockNode sbn = ssn.getSwitchBody(); - - for (int i = 0; i < sbn.size(); i++) { - inferRelationsFromSwitchBlockNode(md, nametable, (SwitchBlockNode) sbn.get(i)); - } - - for(ImplicitTuple tuple: implicitFlowSet){ - if(tuple.isFromBranch((BlockStatementNode) ssn)){ - implicitFlowSet.remove(tuple); - } - } - } - - private void inferRelationsFromSwitchBlockNode(MethodDescriptor md, - SymbolTable nametable, SwitchBlockNode sbn) { - inferRelationsFromBlockNode(md, nametable, sbn.getSwitchBlockStatement()); - } - - private void inferRelationsFromReturnNode(MethodDescriptor md, SymbolTable nametable, - ReturnNode rn) { - - ExpressionNode returnExp = rn.getReturnExpression(); - - // interim fixes - VarID returnID = new VarID(md); - returnID.setReturn(); - if (returnExp != null) { - inferRelationsFromExpressionNode(md, nametable, returnExp, returnID, null, false); - } - } - - private void inferRelationsFromLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln) { - - ClassDescriptor cd = md.getClassDesc(); - if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) { - - inferRelationsFromExpressionNode(md, nametable, ln.getCondition(), null, ln, false); - - inferRelationsFromBlockNode(md, nametable, ln.getBody()); - - for (ImplicitTuple tuple : implicitFlowSet) { - if (tuple.isFromBranch(ln)) { - implicitFlowSet.remove(tuple); - } - } - - } else { - // check 'for loop' case - BlockNode bn = ln.getInitializer(); - bn.getVarTable().setParent(nametable); - - inferRelationsFromBlockNode(md, nametable, bn); - inferRelationsFromExpressionNode(md, bn.getVarTable(), ln.getCondition(), null, ln, false); - - inferRelationsFromBlockNode(md, bn.getVarTable(), ln.getUpdate()); - inferRelationsFromBlockNode(md, bn.getVarTable(), ln.getBody()); - - for (ImplicitTuple tuple : implicitFlowSet) { - if (tuple.isFromBranch(ln)) { - implicitFlowSet.remove(tuple); - } - } - - } - - } - - private void inferRelationsFromSubBlockNode(MethodDescriptor md, - SymbolTable nametable, SubBlockNode sbn) { - inferRelationsFromBlockNode(md, nametable.getParent(), sbn.getBlockNode()); - } - - private void inferRelationsFromIfStatementNode(MethodDescriptor md, SymbolTable nametable, - IfStatementNode isn) { - - inferRelationsFromExpressionNode(md, nametable, isn.getCondition(), null, isn, false); - - inferRelationsFromBlockNode(md, nametable, isn.getTrueBlock()); - - if (isn.getFalseBlock() != null) { - inferRelationsFromBlockNode(md, nametable, isn.getFalseBlock()); - } - - for (ImplicitTuple tuple : implicitFlowSet) { - if (tuple.isFromBranch(isn)) { - implicitFlowSet.remove(tuple); - } - } - } - - private void inferRelationsFromDeclarationNode(MethodDescriptor md, SymbolTable nametable, - DeclarationNode dn) { - } - - private void inferRelationsFromBlockExpressionNode(MethodDescriptor md, - SymbolTable nametable, BlockExpressionNode ben) { - inferRelationsFromExpressionNode(md, nametable, ben.getExpression(), null, null, false); - } - - private VarID inferRelationsFromExpressionNode(MethodDescriptor md, SymbolTable nametable, - ExpressionNode en, VarID flowTo, BlockStatementNode implicitTag, boolean isLHS) { - - VarID var = null; - switch (en.kind()) { - - case Kind.AssignmentNode: - var = - inferRelationsFromAssignmentNode(md, nametable, (AssignmentNode) en, flowTo, implicitTag); - break; - - // case Kind.FieldAccessNode: - // var = - // inferRelationsFromFieldAccessNode(md, nametable, (FieldAccessNode) en, - // flowTo); - // break; - - case Kind.NameNode: - var = inferRelationsFromNameNode(md, nametable, (NameNode) en, flowTo, implicitTag); - break; - - case Kind.OpNode: - var = inferRelationsFromOpNode(md, nametable, (OpNode) en, flowTo, implicitTag); - break; - /* - * case Kind.CreateObjectNode: var = inferRelationsFromCreateObjectNode(md, - * nametable, (CreateObjectNode) en); break; - */ - case Kind.ArrayAccessNode: - var = inferRelationsFromArrayAccessNode(md, nametable, (ArrayAccessNode) en, flowTo, implicitTag, isLHS); - break; - - case Kind.LiteralNode: - var = inferRelationsFromLiteralNode(md, nametable, (LiteralNode) en); - break; - /* - * case Kind.MethodInvokeNode: var = inferRelationsFromMethodInvokeNode(md, - * nametable, (MethodInvokeNode) en, flowTo); break; - * - * case Kind.TertiaryNode: var = inferRelationsFromTertiaryNode(md, - * nametable, (TertiaryNode) en); break; - */ - case Kind.CastNode: - var = inferRelationsFromCastNode(md, nametable, (CastNode) en, flowTo, implicitTag); - break; - - default: - System.out.println("expressionnode not handled..."); - return null; - - } - // addTypeLocation(en.getType(), compLoc); - return var; - - } - - - private VarID inferRelationsFromCastNode(MethodDescriptor md, - SymbolTable nametable, CastNode cn, VarID flowTo, BlockStatementNode implicitTag) { - - ExpressionNode en = cn.getExpression(); - return inferRelationsFromExpressionNode(md, nametable, en, flowTo, implicitTag, false); - - } - /* - * private CompositeLocation inferRelationsFromTertiaryNode(MethodDescriptor - * md, SymbolTable nametable, TertiaryNode tn, CompositeLocation constraint) { - * ClassDescriptor cd = md.getClassDesc(); - * - * CompositeLocation condLoc = inferRelationsFromExpressionNode(md, nametable, - * tn.getCond(), new CompositeLocation(), constraint, false); // - * addLocationType(tn.getCond().getType(), condLoc); CompositeLocation trueLoc - * = inferRelationsFromExpressionNode(md, nametable, tn.getTrueExpr(), new - * CompositeLocation(), constraint, false); // - * addLocationType(tn.getTrueExpr().getType(), trueLoc); CompositeLocation - * falseLoc = inferRelationsFromExpressionNode(md, nametable, - * tn.getFalseExpr(), new CompositeLocation(), constraint, false); // - * addLocationType(tn.getFalseExpr().getType(), falseLoc); - * - * // locations from true/false branches can be TOP when there are only - * literal // values // in this case, we don't need to check flow down rule! - * - * // check if condLoc is higher than trueLoc & falseLoc if - * (!trueLoc.get(0).isTop() && !CompositeLattice.isGreaterThan(condLoc, - * trueLoc, generateErrorMessage(cd, tn))) { throw new Error( - * "The location of the condition expression is lower than the true expression at " - * + cd.getSourceFileName() + ":" + tn.getCond().getNumLine()); } - * - * if (!falseLoc.get(0).isTop() && !CompositeLattice.isGreaterThan(condLoc, - * falseLoc, generateErrorMessage(cd, tn.getCond()))) { throw new Error( - * "The location of the condition expression is lower than the true expression at " - * + cd.getSourceFileName() + ":" + tn.getCond().getNumLine()); } - * - * // then, return glb of trueLoc & falseLoc Set - * glbInputSet = new HashSet(); glbInputSet.add(trueLoc); - * glbInputSet.add(falseLoc); - * - * return CompositeLattice.calculateGLB(glbInputSet, generateErrorMessage(cd, - * tn)); } - * - * private CompositeLocation - * inferRelationsFromMethodInvokeNode(MethodDescriptor md, SymbolTable - * nametable, MethodInvokeNode min, CompositeLocation loc, CompositeLocation - * constraint) { - * - * CompositeLocation baseLocation = null; if (min.getExpression() != null) { - * baseLocation = inferRelationsFromExpressionNode(md, nametable, - * min.getExpression(), new CompositeLocation(), constraint, false); } else { - * - * if (min.getMethod().isStatic()) { String globalLocId = - * ssjava.getMethodLattice(md).getGlobalLoc(); if (globalLocId == null) { - * throw new - * Error("Method lattice does not define global variable location at " + - * generateErrorMessage(md.getClassDesc(), min)); } baseLocation = new - * CompositeLocation(new Location(md, globalLocId)); } else { String thisLocId - * = ssjava.getMethodLattice(md).getThisLoc(); baseLocation = new - * CompositeLocation(new Location(md, thisLocId)); } } - * - * checkCalleeConstraints(md, nametable, min, baseLocation, constraint); - * - * checkCallerArgumentLocationConstraints(md, nametable, min, baseLocation, - * constraint); - * - * if (!min.getMethod().getReturnType().isVoid()) { // If method has a return - * value, compute the highest possible return // location in the caller's - * perspective CompositeLocation ceilingLoc = - * computeCeilingLocationForCaller(md, nametable, min, baseLocation, - * constraint); return ceilingLoc; } - * - * return new CompositeLocation(); - * - * } - * - * private void checkCallerArgumentLocationConstraints(MethodDescriptor md, - * SymbolTable nametable, MethodInvokeNode min, CompositeLocation - * callerBaseLoc, CompositeLocation constraint) { // if parameter location - * consists of THIS and FIELD location, // caller should pass an argument that - * is comparable to the declared // parameter location // and is not lower - * than the declared parameter location in the field // lattice. - * - * MethodDescriptor calleemd = min.getMethod(); - * - * List callerArgList = new ArrayList(); - * List calleeParamList = new - * ArrayList(); - * - * MethodLattice calleeLattice = ssjava.getMethodLattice(calleemd); - * Location calleeThisLoc = new Location(calleemd, - * calleeLattice.getThisLoc()); - * - * for (int i = 0; i < min.numArgs(); i++) { ExpressionNode en = - * min.getArg(i); CompositeLocation callerArgLoc = - * inferRelationsFromExpressionNode(md, nametable, en, new - * CompositeLocation(), constraint, false); callerArgList.add(callerArgLoc); } - * - * // setup callee params set for (int i = 0; i < calleemd.numParameters(); - * i++) { VarDescriptor calleevd = (VarDescriptor) calleemd.getParameter(i); - * CompositeLocation calleeLoc = d2loc.get(calleevd); - * calleeParamList.add(calleeLoc); } - * - * String errorMsg = generateErrorMessage(md.getClassDesc(), min); - * - * System.out.println("checkCallerArgumentLocationConstraints=" + - * min.printNode(0)); System.out.println("base location=" + callerBaseLoc); - * - * for (int i = 0; i < calleeParamList.size(); i++) { CompositeLocation - * calleeParamLoc = calleeParamList.get(i); if - * (calleeParamLoc.get(0).equals(calleeThisLoc) && calleeParamLoc.getSize() > - * 1) { - * - * // callee parameter location has field information CompositeLocation - * callerArgLoc = callerArgList.get(i); - * - * CompositeLocation paramLocation = translateCalleeParamLocToCaller(md, - * calleeParamLoc, callerBaseLoc, errorMsg); - * - * Set inputGLBSet = new HashSet(); if - * (constraint != null) { inputGLBSet.add(callerArgLoc); - * inputGLBSet.add(constraint); callerArgLoc = - * CompositeLattice.calculateGLB(inputGLBSet, - * generateErrorMessage(md.getClassDesc(), min)); } - * - * if (!CompositeLattice.isGreaterThan(callerArgLoc, paramLocation, errorMsg)) - * { throw new Error("Caller argument '" + min.getArg(i).printNode(0) + " : " - * + callerArgLoc + - * "' should be higher than corresponding callee's parameter : " + - * paramLocation + " at " + errorMsg); } - * - * } } - * - * } - * - * private CompositeLocation translateCalleeParamLocToCaller(MethodDescriptor - * md, CompositeLocation calleeParamLoc, CompositeLocation callerBaseLocation, - * String errorMsg) { - * - * CompositeLocation translate = new CompositeLocation(); - * - * for (int i = 0; i < callerBaseLocation.getSize(); i++) { - * translate.addLocation(callerBaseLocation.get(i)); } - * - * for (int i = 1; i < calleeParamLoc.getSize(); i++) { - * translate.addLocation(calleeParamLoc.get(i)); } - * - * System.out.println("TRANSLATED=" + translate + " from calleeParamLoc=" + - * calleeParamLoc); - * - * return translate; } - * - * private CompositeLocation computeCeilingLocationForCaller(MethodDescriptor - * md, SymbolTable nametable, MethodInvokeNode min, CompositeLocation - * baseLocation, CompositeLocation constraint) { List - * argList = new ArrayList(); - * - * // by default, method has a THIS parameter argList.add(baseLocation); - * - * for (int i = 0; i < min.numArgs(); i++) { ExpressionNode en = - * min.getArg(i); CompositeLocation callerArg = - * inferRelationsFromExpressionNode(md, nametable, en, new - * CompositeLocation(), constraint, false); argList.add(callerArg); } - * - * System.out.println("\n## computeReturnLocation=" + min.getMethod() + - * " argList=" + argList); CompositeLocation compLoc = - * md2ReturnLocGen.get(min.getMethod()).computeReturnLocation(argList); - * DeltaLocation delta = new DeltaLocation(compLoc, 1); - * System.out.println("##computeReturnLocation=" + delta); - * - * return delta; - * - * } - * - * private void checkCalleeConstraints(MethodDescriptor md, SymbolTable - * nametable, MethodInvokeNode min, CompositeLocation callerBaseLoc, - * CompositeLocation constraint) { - * - * System.out.println("checkCalleeConstraints="+min.printNode(0)); - * - * MethodDescriptor calleemd = min.getMethod(); - * - * MethodLattice calleeLattice = ssjava.getMethodLattice(calleemd); - * CompositeLocation calleeThisLoc = new CompositeLocation(new - * Location(calleemd, calleeLattice.getThisLoc())); - * - * List callerArgList = new ArrayList(); - * List calleeParamList = new - * ArrayList(); - * - * if (min.numArgs() > 0) { // caller needs to guarantee that it passes - * arguments in regarding to // callee's hierarchy - * - * // setup caller args set // first, add caller's base(this) location - * callerArgList.add(callerBaseLoc); // second, add caller's arguments for - * (int i = 0; i < min.numArgs(); i++) { ExpressionNode en = min.getArg(i); - * CompositeLocation callerArgLoc = inferRelationsFromExpressionNode(md, - * nametable, en, new CompositeLocation(), constraint, false); - * callerArgList.add(callerArgLoc); } - * - * // setup callee params set // first, add callee's this location - * calleeParamList.add(calleeThisLoc); // second, add callee's parameters for - * (int i = 0; i < calleemd.numParameters(); i++) { VarDescriptor calleevd = - * (VarDescriptor) calleemd.getParameter(i); CompositeLocation calleeLoc = - * d2loc.get(calleevd); - * System.out.println("calleevd="+calleevd+" loc="+calleeLoc); - * calleeParamList.add(calleeLoc); } - * - * // here, check if ordering relations among caller's args respect // - * ordering relations in-between callee's args CHECK: for (int i = 0; i < - * calleeParamList.size(); i++) { CompositeLocation calleeLoc1 = - * calleeParamList.get(i); CompositeLocation callerLoc1 = - * callerArgList.get(i); - * - * for (int j = 0; j < calleeParamList.size(); j++) { if (i != j) { - * CompositeLocation calleeLoc2 = calleeParamList.get(j); CompositeLocation - * callerLoc2 = callerArgList.get(j); - * - * if (callerLoc1.get(callerLoc1.getSize() - 1).isTop() || - * callerLoc2.get(callerLoc2.getSize() - 1).isTop()) { continue CHECK; } - * - * System.out.println("calleeLoc1="+calleeLoc1); - * System.out.println("calleeLoc2=" - * +calleeLoc2+"calleeParamList="+calleeParamList); - * - * int callerResult = CompositeLattice.compare(callerLoc1, callerLoc2, true, - * generateErrorMessage(md.getClassDesc(), min)); int calleeResult = - * CompositeLattice.compare(calleeLoc1, calleeLoc2, true, - * generateErrorMessage(md.getClassDesc(), min)); - * - * if (calleeResult == ComparisonResult.GREATER && callerResult != - * ComparisonResult.GREATER) { // If calleeLoc1 is higher than calleeLoc2 // - * then, caller should have same ordering relation in-bet // callerLoc1 & - * callerLoc2 - * - * String paramName1, paramName2; - * - * if (i == 0) { paramName1 = "'THIS'"; } else { paramName1 = "'parameter " + - * calleemd.getParamName(i - 1) + "'"; } - * - * if (j == 0) { paramName2 = "'THIS'"; } else { paramName2 = "'parameter " + - * calleemd.getParamName(j - 1) + "'"; } - * - * throw new Error( - * "Caller doesn't respect an ordering relation among method arguments: callee expects that " - * + paramName1 + " should be higher than " + paramName2 + " in " + calleemd + - * " at " + md.getClassDesc().getSourceFileName() + ":" + min.getNumLine()); } - * } - * - * } } - * - * } - * - * } - */ - private VarID inferRelationsFromArrayAccessNode(MethodDescriptor md, SymbolTable - nametable, ArrayAccessNode aan, VarID flowTo, BlockStatementNode implicitTag, boolean isLHS) { - - - VarID arrayID = inferRelationsFromExpressionNode(md, nametable, aan.getExpression(), flowTo, implicitTag, isLHS); - - if (isLHS) { - VarID indexID = inferRelationsFromExpressionNode(md, nametable, aan.getIndex(), arrayID, implicitTag, isLHS); - } - else{ - VarID indexID = inferRelationsFromExpressionNode(md, nametable, aan.getIndex(), flowTo, implicitTag, isLHS); - } - return arrayID; - } - - /* - private CompositeLocation - inferRelationsFromCreateObjectNode(MethodDescriptor md, SymbolTable - nametable, CreateObjectNode con) { - - ClassDescriptor cd = md.getClassDesc(); - - CompositeLocation compLoc = new CompositeLocation(); - compLoc.addLocation(Location.createTopLocation(md)); return compLoc; - - } - */ - private VarID inferRelationsFromOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on, - VarID flowTo, BlockStatementNode implicitTag) { - - VarID var = - inferRelationsFromExpressionNode(md, nametable, on.getLeft(), flowTo, implicitTag, false); - - if (on.getRight() != null) { - inferRelationsFromExpressionNode(md, nametable, on.getRight(), flowTo, implicitTag, false); - } - - Operation op = on.getOp(); - - switch (op.getOp()) { - - case Operation.UNARYPLUS: - case Operation.UNARYMINUS: - case Operation.LOGIC_NOT: - // single operand - return var; - - case Operation.LOGIC_OR: - case Operation.LOGIC_AND: - case Operation.COMP: - case Operation.BIT_OR: - case Operation.BIT_XOR: - case Operation.BIT_AND: - case Operation.ISAVAILABLE: - case Operation.EQUAL: - case Operation.NOTEQUAL: - case Operation.LT: - case Operation.GT: - case Operation.LTE: - case Operation.GTE: - case Operation.ADD: - case Operation.SUB: - case Operation.MULT: - case Operation.DIV: - case Operation.MOD: - case Operation.LEFTSHIFT: - case Operation.RIGHTSHIFT: - case Operation.URIGHTSHIFT: - - return var; - - default: - throw new Error(op.toString()); - } - - } - - private VarID inferRelationsFromLiteralNode(MethodDescriptor md, SymbolTable nametable, - LiteralNode ln) { - // literal data flow does not matter - return null; - - } - - private VarID inferRelationsFromNameNode(MethodDescriptor md, SymbolTable nametable, NameNode nn, - VarID flowTo, BlockStatementNode implicitTag) { - VarID var = null; - NameDescriptor nd = nn.getName(); - if (nd.getBase() != null) { - var = - inferRelationsFromExpressionNode(md, nametable, nn.getExpression(), flowTo, implicitTag, - false); - } else { - String varname = nd.toString(); - if (varname.equals("this")) { - var = new VarID(nd); - if (flowTo != null) { - rSet.addRelation(new BinaryRelation(var, flowTo)); - } - if (implicitTag != null) { - implicitFlowSet.add(new ImplicitTuple(var, implicitTag)); - } - var.setThis(); - return var; - } - - Descriptor d = (Descriptor) nametable.get(varname); - - if (d instanceof VarDescriptor) { - var = new VarID(nd); - if (flowTo != null) { - rSet.addRelation(new BinaryRelation(var, flowTo)); - } - if (implicitTag != null) { - implicitFlowSet.add(new ImplicitTuple(var, implicitTag)); - } - } else if (d instanceof FieldDescriptor) { - FieldDescriptor fd = (FieldDescriptor) d; - if (fd.isStatic()) { - if (fd.isFinal()) { - var = new VarID(nd); - if (flowTo != null) { - rSet.addRelation(new BinaryRelation(var, flowTo)); - } - if (implicitTag != null) { - implicitFlowSet.add(new ImplicitTuple(var, implicitTag)); - } - var.setTop(); - return var; - } else { - var = new VarID(nd); - if (flowTo != null) { - rSet.addRelation(new BinaryRelation(var, flowTo)); - } - if (implicitTag != null) { - implicitFlowSet.add(new ImplicitTuple(var, implicitTag)); - } - var.setGlobal(); - } - } else { - var = new VarID(nd); - if (flowTo != null) { - rSet.addRelation(new BinaryRelation(var, flowTo)); - } - if (implicitTag != null) { - implicitFlowSet.add(new ImplicitTuple(var, implicitTag)); - } - var.setThis(); - } - } else if (d == null) { - var = new VarID(nd); - if (flowTo != null) { - rSet.addRelation(new BinaryRelation(var, flowTo)); - } - if (implicitTag != null) { - implicitFlowSet.add(new ImplicitTuple(var, implicitTag)); - } - var.setGlobal(); - return var; - } - } - return var; - } - - /* - * private CompositeLocation - * inferRelationsFromFieldAccessNode(MethodDescriptor md, SymbolTable - * nametable, FieldAccessNode fan, CompositeLocation loc, CompositeLocation - * constraint) { - * - * ExpressionNode left = fan.getExpression(); TypeDescriptor ltd = - * left.getType(); - * - * FieldDescriptor fd = fan.getField(); - * - * String varName = null; if (left.kind() == Kind.NameNode) { NameDescriptor - * nd = ((NameNode) left).getName(); varName = nd.toString(); } - * - * if (ltd.isClassNameRef() || (varName != null && varName.equals("this"))) { - * // using a class name directly or access using this if (fd.isStatic() && - * fd.isFinal()) { loc.addLocation(Location.createTopLocation(md)); return - * loc; } } - * - * loc = inferRelationsFromExpressionNode(md, nametable, left, loc, - * constraint, false); - * System.out.println("### inferRelationsFromFieldAccessNode=" + - * fan.printNode(0)); System.out.println("### left=" + left.printNode(0)); if - * (!left.getType().isPrimitive()) { Location fieldLoc = getFieldLocation(fd); - * loc.addLocation(fieldLoc); } - * - * return loc; } - * - * private Location getFieldLocation(FieldDescriptor fd) { - * - * System.out.println("### getFieldLocation=" + fd); - * System.out.println("### fd.getType().getExtension()=" + - * fd.getType().getExtension()); - * - * Location fieldLoc = (Location) fd.getType().getExtension(); - * - * // handle the case that method annotation checking skips checking field // - * declaration if (fieldLoc == null) { fieldLoc = - * checkFieldDeclaration(fd.getClassDescriptor(), fd); } - * - * return fieldLoc; - * - * } - */ - - private VarID inferRelationsFromAssignmentNode(MethodDescriptor md, SymbolTable nametable, - AssignmentNode an, VarID flowTo, BlockStatementNode implicitTag) { - ClassDescriptor cd = md.getClassDesc(); - boolean postinc = true; - - if (an.getOperation().getBaseOp() == null - || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation() - .getBaseOp().getOp() != Operation.POSTDEC)) - postinc = false; - // get ID for leftside - VarID destID = - inferRelationsFromExpressionNode(md, nametable, an.getDest(), flowTo, implicitTag, true); - - if (!postinc) { - // recursively add relations from RHS to LHS - inferRelationsFromExpressionNode(md, nametable, an.getSrc(), destID, null, false); - - } else { - // add relation to self - destID = inferRelationsFromExpressionNode(md, nametable, an.getDest(), destID, null, false); - } - - // checks if flow to anythin and adds relation - if (flowTo != null) { - rSet.addRelation(new BinaryRelation(destID, flowTo)); - } - - // add relations for implicit flow - for (ImplicitTuple it : implicitFlowSet) { - rSet.addRelation(new BinaryRelation(it.getVar(), destID)); - } - - return destID; - } -} \ No newline at end of file diff --git a/Robust/src/Analysis/SSJava/SSJavaLattice.java b/Robust/src/Analysis/SSJava/SSJavaLattice.java index cbbae46c..be1a342e 100644 --- a/Robust/src/Analysis/SSJava/SSJavaLattice.java +++ b/Robust/src/Analysis/SSJava/SSJavaLattice.java @@ -1,16 +1,15 @@ package Analysis.SSJava; import java.util.HashSet; +import java.util.Iterator; import java.util.Set; import Util.Lattice; public class SSJavaLattice extends Lattice { - public static final String TOP = "_top_"; - public static final String BOTTOM = "_bottom_"; - Set sharedLocSet; + public static int seed = 0; public SSJavaLattice(T top, T bottom) { super(top, bottom); @@ -36,4 +35,32 @@ public class SSJavaLattice extends Lattice { return put(higher, lower); } + public void insertNewLocationAtOneLevelHigher(T lowerLoc, T newLoc) { + // first identifying which location is connected to the input loc + Set keySet = getKeySet(); + Set oneLevelHigherLocSet = new HashSet(); + + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + T locKey = (T) iterator.next(); + Set conntectedSet = get(locKey); + for (Iterator iterator2 = conntectedSet.iterator(); iterator2.hasNext();) { + T connectedLoc = (T) iterator2.next(); + if (connectedLoc.equals(lowerLoc)) { + oneLevelHigherLocSet.add(locKey); + } + } + } + + put(newLoc); + addRelationHigherToLower(newLoc, lowerLoc); + + for (Iterator iterator = oneLevelHigherLocSet.iterator(); iterator.hasNext();) { + T higherLoc = (T) iterator.next(); + // remove an existing edge between the higher loc and the input loc + get(higherLoc).remove(lowerLoc); + // add a new edge from the higher loc to the new location + put(higherLoc, newLoc); + } + + } } diff --git a/Robust/src/Util/Lattice.java b/Robust/src/Util/Lattice.java index 22ed8d64..bc024cfa 100644 --- a/Robust/src/Util/Lattice.java +++ b/Robust/src/Util/Lattice.java @@ -76,7 +76,9 @@ public class Lattice { topNeighbor.remove(value); // if key is already connected with bottom,, it is no longer to be - table.get(key).remove(getBottomItem()); + if (!value.equals(getBottomItem())) { + table.get(key).remove(getBottomItem()); + } return true; } else @@ -129,7 +131,9 @@ public class Lattice { Set neighborSet = get(a); - if (neighborSet == null) { + if (a.equals(b)) { + return true; + } else if (neighborSet == null) { return false; } else if (neighborSet.contains(b)) { return true; @@ -146,6 +150,10 @@ public class Lattice { public boolean isGreaterThan(T a, T b) { + if (a.equals(b)) { + return false; + } + if (a.equals(top)) { if (b.equals(top)) { return false; -- 2.34.1