X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;ds=sidebyside;f=Robust%2Fsrc%2FAnalysis%2FSSJava%2FLocationInference.java;h=1294cf85604dc57a6de25f6de0671198f722db13;hb=78a14d01d4b27a3e6e5f42c3bdb382a708426e96;hp=66dadfa782d185137835599916be82c75e7694ec;hpb=0b423adbb0f959f90ca7845e53fe8e7e0e151b96;p=IRC.git diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index 66dadfa7..1294cf85 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; @@ -13,8 +14,6 @@ import java.util.Map; import java.util.Set; import java.util.Stack; -import Analysis.SSJava.FlowDownCheck.ComparisonResult; -import Analysis.SSJava.FlowDownCheck.CompositeLattice; import IR.ClassDescriptor; import IR.Descriptor; import IR.FieldDescriptor; @@ -25,7 +24,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; @@ -47,6 +45,8 @@ import IR.Tree.ReturnNode; import IR.Tree.SubBlockNode; import IR.Tree.SwitchStatementNode; import IR.Tree.TertiaryNode; +import IR.Tree.TreeNode; +import Util.Pair; public class LocationInference { @@ -69,21 +69,27 @@ 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> mapMethodInvokeNodeToArgIdxMap; + + private Map mapMethodDescToMethodLocationInfo; + + private Map mapClassToLocationInfo; + + private Map> mapMethodToCalleeSet; + + 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); + + LocationInfo curMethodInfo; boolean debug = true; @@ -96,15 +102,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>>(); - + new HashMap>(); + this.mapMethodDescToMethodLocationInfo = new HashMap(); + this.mapMethodToCalleeSet = new HashMap>(); + this.mapClassToLocationInfo = new HashMap(); } public void setupToAnalyze() { @@ -154,8 +158,62 @@ public class LocationInference { // 2) construct lattices inferLattices(); + simplifyLattices(); + debug_writeLatticeDotFile(); + // 3) check properties + checkLattices(); + + } + + private void simplifyLattices() { + + // generate lattice dot file + setupToAnalyze(); + + while (!toAnalyzeIsEmpty()) { + ClassDescriptor cd = toAnalyzeNext(); + + setupToAnalazeMethod(cd); + + SSJavaLattice classLattice = cd2lattice.get(cd); + if (classLattice != null) { + classLattice.removeRedundantEdges(); + } + + while (!toAnalyzeMethodIsEmpty()) { + MethodDescriptor md = toAnalyzeMethodNext(); + if (ssjava.needTobeAnnotated(md)) { + SSJavaLattice methodLattice = md2lattice.get(md); + if (methodLattice != null) { + methodLattice.removeRedundantEdges(); + } + } + } + } + + } + + 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() { @@ -170,7 +228,8 @@ public class LocationInference { SSJavaLattice classLattice = cd2lattice.get(cd); if (classLattice != null) { - ssjava.writeLatticeDotFile(cd, classLattice); + ssjava.writeLatticeDotFile(cd, null, classLattice); + debug_printDescriptorToLocNameMapping(cd); } while (!toAnalyzeMethodIsEmpty()) { @@ -178,7 +237,8 @@ public class LocationInference { if (ssjava.needTobeAnnotated(md)) { SSJavaLattice methodLattice = md2lattice.get(md); if (methodLattice != null) { - ssjava.writeLatticeDotFile(cd, methodLattice); + ssjava.writeLatticeDotFile(cd, md, methodLattice); + debug_printDescriptorToLocNameMapping(md); } } } @@ -186,19 +246,35 @@ public class LocationInference { } + private void debug_printDescriptorToLocNameMapping(Descriptor desc) { + + LocationInfo info = getLocationInfo(desc); + System.out.println("## " + desc + " ##"); + System.out.println(info.getMapDescToInferLocation()); + LocationInfo locInfo = getLocationInfo(desc); + System.out.println("mapping=" + locInfo.getMapLocSymbolToDescSet()); + System.out.println("###################"); + + } + private void inferLattices() { // do fixed-point analysis - // perform method READ/OVERWRITE analysis 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 methodDescriptorsToVisitStack.clear(); - descriptorListToAnalyze.removeFirst(); + // descriptorListToAnalyze.removeFirst(); Set methodDescriptorToVistSet = new HashSet(); methodDescriptorToVistSet.addAll(descriptorListToAnalyze); @@ -212,19 +288,29 @@ public class LocationInference { while (!methodDescriptorsToVisitStack.isEmpty()) { // start to analyze leaf node MethodDescriptor md = methodDescriptorsToVisitStack.pop(); - FlatMethod fm = state.getMethodFlat(md); SSJavaLattice methodLattice = - new SSJavaLattice(SSJavaLattice.TOP, SSJavaLattice.BOTTOM); + new SSJavaLattice(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM); + MethodLocationInfo methodInfo = new MethodLocationInfo(md); + curMethodInfo = methodInfo; + + System.out.println(); System.out.println("SSJAVA: Inferencing the lattice from " + md); - analyzeMethodLattice(md, methodLattice); + try { + analyzeMethodLattice(md, methodLattice, methodInfo); + } catch (CyclicFlowException e) { + throw new Error("Fail to generate the method lattice for " + md); + } + + SSJavaLattice prevMethodLattice = getMethodLattice(md); + MethodLocationInfo prevMethodInfo = getMethodLocationInfo(md); - SSJavaLattice prevMethodLattice = md2lattice.get(md); + if ((!methodLattice.equals(prevMethodLattice)) || (!methodInfo.equals(prevMethodInfo))) { - if (!methodLattice.equals(prevMethodLattice)) { - md2lattice.put(md, methodLattice); + setMethodLattice(md, methodLattice); + setMethodLocInfo(md, methodInfo); // results for callee changed, so enqueue dependents caller for // further analysis @@ -240,6 +326,94 @@ public class LocationInference { } } + } + + private void setMethodLocInfo(MethodDescriptor md, MethodLocationInfo methodInfo) { + mapMethodDescToMethodLocationInfo.put(md, methodInfo); + } + + 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, GLOBAL_LOC RETURN LOC) + + List list1 = new ArrayList(); + List list2 = new ArrayList(); + + MethodLocationInfo locInfo1 = getMethodLocationInfo(md1); + MethodLocationInfo locInfo2 = getMethodLocationInfo(md2); + + Map paramMap1 = locInfo1.getMapParamIdxToInferLoc(); + Map paramMap2 = locInfo2.getMapParamIdxToInferLoc(); + + 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); + } + + 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(getLattice(md1), locA1, locB1); + + boolean r2 = isGreaterThan(getLattice(md1), 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 locations (" + locA1 + "," + + locB1 + ") and (" + locA2 + "," + locB2 + ")."); + } + } + } + } } @@ -248,161 +422,956 @@ public class LocationInference { return desc.getSymbol(); } - private void addMappingDescriptorToLocationIdentifer(MethodDescriptor methodDesc, - VarDescriptor varDesc, String identifier) { - if (!md2LatticeMapping.containsKey(methodDesc)) { - md2LatticeMapping.put(methodDesc, new HashMap()); - } - + private Descriptor getDescriptor(int idx, FlowNode node) { + Descriptor desc = node.getDescTuple().get(idx); + return desc; } - private void analyzeMethodLattice(MethodDescriptor md, SSJavaLattice methodLattice) { + private void analyzeMethodLattice(MethodDescriptor md, SSJavaLattice methodLattice, + MethodLocationInfo methodInfo) throws CyclicFlowException { - // visit each node of method flow graph + // first take a look at method invocation nodes to newly added relations + // from the callee + analyzeLatticeMethodInvocationNode(md, methodLattice, methodInfo); + if (!md.isStatic()) { + // set the this location + String thisLocSymbol = md.getThis().getSymbol(); + methodInfo.setThisLocName(thisLocSymbol); + } + + // set the global location + methodInfo.setGlobalLocName(LocationInference.GLOBALLOC); + methodInfo.mapDescriptorToLocation(GLOBALDESC, new CompositeLocation( + new Location(md, GLOBALLOC))); + + // visit each node of method flow graph FlowGraph fg = getFlowGraph(md); Set nodeSet = fg.getNodeSet(); // for the method lattice, we need to look at the first element of // NTuple - 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 + Descriptor desc = srcNodeTuple.get(0); + ClassDescriptor classDesc; + + if (desc.equals(GLOBALDESC)) { + classDesc = md.getClassDesc(); + } else { + VarDescriptor varDesc = (VarDescriptor) srcNodeTuple.get(0); + classDesc = varDesc.getType().getClassDesc(); + } + extractRelationFromFieldFlows(classDesc, srcNode, dstNode, 1); + + } else { + // value flow between local var - local var or local var - field + addRelationToLattice(md, methodLattice, methodInfo, srcNode, dstNode); + } + + // else if (srcNodeTuple.size() == 1 || dstNodeTuple.size() == 1) { + // // for the method lattice, we need to look at the first element of + // // NTuple + // // in this case, take a look at connected nodes at the local level + // addRelationToLattice(md, methodLattice, methodInfo, srcNode, + // dstNode); + // } else { + // if + // (!srcNode.getDescTuple().get(0).equals(dstNode.getDescTuple().get(0))) + // { + // // in this case, take a look at connected nodes at the local level + // addRelationToLattice(md, methodLattice, methodInfo, srcNode, + // dstNode); + // } else { + // Descriptor srcDesc = srcNode.getDescTuple().get(0); + // Descriptor dstDesc = dstNode.getDescTuple().get(0); + // recursivelyAddCompositeRelation(md, fg, methodInfo, srcNode, + // dstNode, srcDesc, + // dstDesc); + // // recursiveAddRelationToLattice(1, md, srcNode, dstNode); + // } + // } + + } + } + } + + // create mapping from param idx to inferred composite location - // second, take a look at all nodes that are reachable from the source - // node - recursiveVisitNodes(md, srcNode, dstNode); + 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 + // the return location type is lower than all parameters + if (!md.getReturnType().isVoid()) { + + String returnLocSymbol = "RETURNLOC"; + 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(paramLocLocalSymbol, returnLocSymbol)) { + addRelationHigherToLower(methodLattice, methodInfo, paramLocLocalSymbol, returnLocSymbol); + } + } } } - 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 + private boolean isGreaterThan(SSJavaLattice methodLattice, CompositeLocation comp1, + CompositeLocation comp2) { + + int size = comp1.getSize() >= comp2.getSize() ? comp2.getSize() : comp1.getSize(); + + for (int idx = 0; idx < size; 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(); + + SSJavaLattice lattice; + if (idx == 0) { + lattice = methodLattice; + } else { + lattice = getLattice(desc1); + } + if (symbol1.equals(symbol2)) { + continue; + } else if (lattice.isGreaterThan(symbol1, symbol2)) { + return true; + } else { + return false; + } + + } + + return false; + } + + private void recursiveAddRelationToLattice(int idx, MethodDescriptor md, + CompositeLocation srcInferLoc, CompositeLocation dstInferLoc) throws CyclicFlowException { + + String srcLocSymbol = srcInferLoc.get(idx).getLocIdentifier(); + String dstLocSymbol = dstInferLoc.get(idx).getLocIdentifier(); + + if (srcLocSymbol.equals(dstLocSymbol)) { + recursiveAddRelationToLattice(idx + 1, md, srcInferLoc, dstInferLoc); + } else { + + Descriptor parentDesc = srcInferLoc.get(idx).getDescriptor(); + LocationInfo locInfo = getLocationInfo(parentDesc); + + addRelationHigherToLower(getLattice(parentDesc), getLocationInfo(parentDesc), srcLocSymbol, + dstLocSymbol); + } + + } + + private void analyzeLatticeMethodInvocationNode(MethodDescriptor mdCaller, + SSJavaLattice methodLattice, MethodLocationInfo methodInfo) + throws CyclicFlowException { + + // the transformation for a call site propagates all relations between + // parameters from the callee + // if the method is virtual, it also grab all relations from any possible + // callees + + Set setMethodInvokeNode = + mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller); + + if (setMethodInvokeNode != null) { + + for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) { + MethodInvokeNode min = (MethodInvokeNode) iterator.next(); + MethodDescriptor mdCallee = min.getMethod(); + Set setPossibleCallees = new HashSet(); + if (mdCallee.isStatic()) { + setPossibleCallees.add(mdCallee); + } else { + Set calleeSet = ssjava.getCallGraph().getMethods(mdCallee); + // removes method descriptors that are not invoked by the caller + calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller)); + setPossibleCallees.addAll(calleeSet); + } + + for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) { + MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next(); + propagateRelationToCaller(min, mdCaller, possibleMdCallee, methodLattice, methodInfo); + } + + } + } + + } + + private void propagateRelationToCaller(MethodInvokeNode min, MethodDescriptor mdCaller, + MethodDescriptor possibleMdCallee, SSJavaLattice methodLattice, + MethodLocationInfo methodInfo) throws CyclicFlowException { + + SSJavaLattice calleeLattice = getMethodLattice(possibleMdCallee); + MethodLocationInfo calleeLocInfo = getMethodLocationInfo(possibleMdCallee); + FlowGraph calleeFlowGraph = getFlowGraph(possibleMdCallee); + + int numParam = calleeLocInfo.getNumParam(); + for (int i = 0; i < numParam; i++) { + CompositeLocation param1 = calleeLocInfo.getParamCompositeLocation(i); + for (int k = 0; k < numParam; k++) { + if (i != k) { + CompositeLocation param2 = calleeLocInfo.getParamCompositeLocation(k); + if (isGreaterThan(getLattice(possibleMdCallee), param1, param2)) { + NodeTupleSet argDescTupleSet1 = getNodeTupleSetByArgIdx(min, i); + NodeTupleSet argDescTupleSet2 = getNodeTupleSetByArgIdx(min, k); + + // the callee has the relation in which param1 is higher than param2 + // therefore, the caller has to have the relation in which arg1 is + // higher than arg2 + + for (Iterator> iterator = argDescTupleSet1.iterator(); iterator + .hasNext();) { + NTuple argDescTuple1 = iterator.next(); - VarDescriptor varDesc = (VarDescriptor) srcNode.getDescTuple().get(0); - ClassDescriptor varClassDesc = varDesc.getType().getClassDesc(); + for (Iterator> iterator2 = argDescTupleSet2.iterator(); iterator2 + .hasNext();) { + NTuple argDescTuple2 = iterator2.next(); - extractRelationFromFieldFlows(varClassDesc, srcNode, dstNode, 1); - return; + // retreive inferred location by the local var descriptor + + NTuple tuple1 = getFlowGraph(mdCaller).getLocationTuple(argDescTuple1); + NTuple tuple2 = getFlowGraph(mdCaller).getLocationTuple(argDescTuple2); + + // CompositeLocation higherInferLoc = + // methodInfo.getInferLocation(argTuple1.get(0)); + // CompositeLocation lowerInferLoc = + // methodInfo.getInferLocation(argTuple2.get(0)); + + CompositeLocation inferLoc1 = generateInferredCompositeLocation(methodInfo, tuple1); + CompositeLocation inferLoc2 = generateInferredCompositeLocation(methodInfo, tuple2); + + // addRelation(methodLattice, methodInfo, inferLoc1, inferLoc2); + + addFlowGraphEdge(mdCaller, argDescTuple1, argDescTuple2); + + } + + } + + } + } + } + } + + } + + private CompositeLocation generateInferredCompositeLocation(MethodLocationInfo methodInfo, + NTuple tuple) { + + // System.out.println("@@@@@generateInferredCompositeLocation=" + tuple); + // System.out.println("generateInferredCompositeLocation=" + tuple + " 0=" + // + tuple.get(0).getLocDescriptor()); + // first, retrieve inferred location by the local var descriptor + CompositeLocation inferLoc = new CompositeLocation(); + + CompositeLocation localVarInferLoc = + methodInfo.getInferLocation(tuple.get(0).getLocDescriptor()); + + localVarInferLoc.get(0).setLocDescriptor(tuple.get(0).getLocDescriptor()); + + for (int i = 0; i < localVarInferLoc.getSize(); i++) { + inferLoc.addLocation(localVarInferLoc.get(i)); + } + // System.out.println("@@@@@localVarInferLoc=" + localVarInferLoc); + + for (int i = 1; i < tuple.size(); i++) { + Location cur = tuple.get(i); + Descriptor enclosingDesc = cur.getDescriptor(); + Descriptor curDesc = cur.getLocDescriptor(); + + Location inferLocElement; + if (curDesc == null) { + // in this case, we have a newly generated location. + // System.out.println("!!! generated location=" + + // cur.getLocIdentifier()); + inferLocElement = new Location(enclosingDesc, cur.getLocIdentifier()); + } else { + String fieldLocSymbol = + getLocationInfo(enclosingDesc).getInferLocation(curDesc).get(0).getLocIdentifier(); + inferLocElement = new Location(enclosingDesc, fieldLocSymbol); + inferLocElement.setLocDescriptor(curDesc); + } + + inferLoc.addLocation(inferLocElement); + + } + // System.out.println("@@@@@inferLoc=" + inferLoc); + return inferLoc; + } + + private void addRelation(SSJavaLattice methodLattice, MethodLocationInfo methodInfo, + CompositeLocation srcInferLoc, CompositeLocation dstInferLoc) throws CyclicFlowException { + + System.out.println("addRelation --- srcInferLoc=" + srcInferLoc + " dstInferLoc=" + + dstInferLoc); + String srcLocalLocSymbol = srcInferLoc.get(0).getLocIdentifier(); + String dstLocalLocSymbol = dstInferLoc.get(0).getLocIdentifier(); + + 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 + + if (!srcLocalLocSymbol.equals(dstLocalLocSymbol)) { + addRelationHigherToLower(methodLattice, methodInfo, srcLocalLocSymbol, dstLocalLocSymbol); + } else { + recursivelyAddRelation(1, srcInferLoc, dstInferLoc); + } + } else { + // either src or dst has assigned to a composite location + if (!srcLocalLocSymbol.equals(dstLocalLocSymbol)) { + addRelationHigherToLower(methodLattice, methodInfo, srcLocalLocSymbol, dstLocalLocSymbol); + } + } + + System.out.println(); + + } + + public LocationInfo getLocationInfo(Descriptor d) { + if (d instanceof MethodDescriptor) { + return getMethodLocationInfo((MethodDescriptor) d); + } else { + return getFieldLocationInfo((ClassDescriptor) d); + } + } + + private MethodLocationInfo getMethodLocationInfo(MethodDescriptor md) { + + if (!mapMethodDescToMethodLocationInfo.containsKey(md)) { + mapMethodDescToMethodLocationInfo.put(md, new MethodLocationInfo(md)); + } + + return mapMethodDescToMethodLocationInfo.get(md); + + } + + private LocationInfo getFieldLocationInfo(ClassDescriptor cd) { + + if (!mapClassToLocationInfo.containsKey(cd)) { + mapClassToLocationInfo.put(cd, new LocationInfo(cd)); } + return mapClassToLocationInfo.get(cd); + + } + + private void addRelationToLattice(MethodDescriptor md, SSJavaLattice methodLattice, + MethodLocationInfo methodInfo, FlowNode srcNode, FlowNode dstNode) throws CyclicFlowException { + + System.out.println(); + System.out.println("### addRelationToLattice src=" + srcNode + " dst=" + dstNode); + // add a new binary relation of dstNode < srcNode + FlowGraph flowGraph = getFlowGraph(md); + try { + System.out.println("***** src composite case::"); + calculateCompositeLocation(flowGraph, methodLattice, methodInfo, srcNode); + + CompositeLocation srcInferLoc = + generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(srcNode)); + CompositeLocation dstInferLoc = + generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(dstNode)); + addRelation(methodLattice, methodInfo, srcInferLoc, dstInferLoc); + } catch (CyclicFlowException e) { + // there is a cyclic value flow... try to calculate a composite location + // for the destination node + System.out.println("***** dst composite case::"); + calculateCompositeLocation(flowGraph, methodLattice, methodInfo, dstNode); + CompositeLocation srcInferLoc = + generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(srcNode)); + CompositeLocation dstInferLoc = + generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(dstNode)); + try { + addRelation(methodLattice, methodInfo, srcInferLoc, dstInferLoc); + } catch (CyclicFlowException e1) { + throw new Error("Failed to merge cyclic value flows into a shared location."); + } + } + + } + + private void recursivelyAddRelation(int idx, CompositeLocation srcInferLoc, + CompositeLocation dstInferLoc) throws CyclicFlowException { - String srcSymbol = getSymbol(0, srcNode); - String dstSymbol = getSymbol(0, dstNode); + String srcLocSymbol = srcInferLoc.get(idx).getLocIdentifier(); + String dstLocSymbol = dstInferLoc.get(idx).getLocIdentifier(); - methodLattice.addRelationHigherToLower(srcSymbol, dstSymbol); + Descriptor parentDesc = srcInferLoc.get(idx).getDescriptor(); - if (srcNode.isParameter() && dstNode.isParameter()) { - propagateRelationToCaller(md, srcNode, dstNode); + if (srcLocSymbol.equals(dstLocSymbol)) { + // check if it is the case of shared location + if (srcInferLoc.getSize() == (idx + 1) && dstInferLoc.getSize() == (idx + 1)) { + Location inferLocElement = srcInferLoc.get(idx); + System.out.println("SET SHARED LOCATION=" + inferLocElement); + getLattice(inferLocElement.getDescriptor()) + .addSharedLoc(inferLocElement.getLocIdentifier()); + } else if (srcInferLoc.getSize() > (idx + 1) && dstInferLoc.getSize() > (idx + 1)) { + recursivelyAddRelation(idx + 1, srcInferLoc, dstInferLoc); + } + } else { + addRelationHigherToLower(getLattice(parentDesc), getLocationInfo(parentDesc), srcLocSymbol, + dstLocSymbol); } } - private SSJavaLattice getMethodLattice(MethodDescriptor md) { + private void recursivelyAddCompositeRelation(MethodDescriptor md, FlowGraph flowGraph, + MethodLocationInfo methodInfo, FlowNode srcNode, FlowNode dstNode, Descriptor srcDesc, + Descriptor dstDesc) throws CyclicFlowException { - if (!md2lattice.containsKey(md)) { - md2lattice.put(md, new SSJavaLattice(SSJavaLattice.TOP, SSJavaLattice.BOTTOM)); + CompositeLocation inferSrcLoc; + CompositeLocation inferDstLoc = methodInfo.getInferLocation(dstDesc); + + if (srcNode.getDescTuple().size() > 1) { + // field access + inferSrcLoc = new CompositeLocation(); + + NTuple locTuple = flowGraph.getLocationTuple(srcNode); + for (int i = 0; i < locTuple.size(); i++) { + inferSrcLoc.addLocation(locTuple.get(i)); + } + + } else { + inferSrcLoc = methodInfo.getInferLocation(srcDesc); } - return md2lattice.get(md); + + if (dstNode.getDescTuple().size() > 1) { + // field access + inferDstLoc = new CompositeLocation(); + + NTuple locTuple = flowGraph.getLocationTuple(dstNode); + for (int i = 0; i < locTuple.size(); i++) { + inferDstLoc.addLocation(locTuple.get(i)); + } + + } else { + inferDstLoc = methodInfo.getInferLocation(dstDesc); + } + + recursiveAddRelationToLattice(1, md, inferSrcLoc, inferDstLoc); } - private void propagateRelationToCaller(MethodDescriptor calleeMethodDesc, FlowNode srcNode, - FlowNode newVisitNode) { + private void addPrefixMapping(Map, Set>> map, + NTuple prefix, NTuple element) { - FlowGraph calleeFlowGraph = getFlowGraph(calleeMethodDesc); + if (!map.containsKey(prefix)) { + map.put(prefix, new HashSet>()); + } + map.get(prefix).add(element); + } - int higherLocIdxCallee = calleeFlowGraph.getParamIdx(srcNode.getDescTuple()); - int lowerLocIdxCallee = calleeFlowGraph.getParamIdx(newVisitNode.getDescTuple()); + private boolean calculateCompositeLocation(FlowGraph flowGraph, + SSJavaLattice methodLattice, MethodLocationInfo methodInfo, FlowNode flowNode) + throws CyclicFlowException { - System.out.println(" ssjava.getDependents(md)=" + ssjava.getDependents(calleeMethodDesc)); - Iterator depsItr = ssjava.getDependents(calleeMethodDesc).iterator(); - while (depsItr.hasNext()) { - MethodDescriptor callerMethodDesc = depsItr.next(); + Descriptor localVarDesc = flowNode.getDescTuple().get(0); + NTuple flowNodelocTuple = flowGraph.getLocationTuple(flowNode); - SSJavaLattice callerMethodLattice = md2lattice.get(callerMethodDesc); + if (localVarDesc.equals(methodInfo.getMethodDesc())) { + return false; + } - Set minSet = mapMethodDescriptorToMethodInvokeNodeSet.get(callerMethodDesc); - for (Iterator iterator = minSet.iterator(); iterator.hasNext();) { - MethodInvokeNode methodInvokeNode = (MethodInvokeNode) iterator.next(); - if (methodInvokeNode.getMethod().equals(calleeMethodDesc)) { - // need to propagate a relation from the callee to the caller - // TODO + Set inNodeSet = flowGraph.getIncomingFlowNodeSet(flowNode); + Set reachableNodeSet = flowGraph.getReachableFlowNodeSet(flowNode); + + Map, Set>> mapPrefixToIncomingLocTupleSet = + new HashMap, Set>>(); + + Set localInNodeSet = new HashSet(); + Set localOutNodeSet = new HashSet(); + + CompositeLocation flowNodeInferLoc = + generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(flowNode)); + + List> prefixList = new ArrayList>(); + + for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) { + FlowNode inNode = (FlowNode) iterator.next(); + NTuple inNodeTuple = flowGraph.getLocationTuple(inNode); + + CompositeLocation inNodeInferredLoc = + generateInferredCompositeLocation(methodInfo, inNodeTuple); + + NTuple inNodeInferredLocTuple = inNodeInferredLoc.getTuple(); + + if (inNodeTuple.size() > 1) { + for (int i = 1; i < inNodeInferredLocTuple.size(); i++) { + NTuple prefix = inNodeInferredLocTuple.subList(0, i); + if (!prefixList.contains(prefix)) { + prefixList.add(prefix); + } + addPrefixMapping(mapPrefixToIncomingLocTupleSet, prefix, inNodeInferredLocTuple); + } + } else { + localInNodeSet.add(inNode); + } + } + + Collections.sort(prefixList, new Comparator>() { + public int compare(NTuple arg0, NTuple arg1) { + int s0 = arg0.size(); + int s1 = arg1.size(); + if (s0 > s1) { + return -1; + } else if (s0 == s1) { + return 0; + } else { + return 1; + } + } + }); + + for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) { + FlowNode reachableNode = (FlowNode) iterator2.next(); + if (reachableNode.getDescTuple().size() == 1) { + localOutNodeSet.add(reachableNode); + } + } + + // find out reachable nodes that have the longest common prefix + for (int i = 0; i < prefixList.size(); i++) { + NTuple curPrefix = prefixList.get(i); + Set> reachableCommonPrefixSet = new HashSet>(); + + for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) { + FlowNode reachableNode = (FlowNode) iterator2.next(); + NTuple reachLocTuple = flowGraph.getLocationTuple(reachableNode); + CompositeLocation reachLocInferLoc = + generateInferredCompositeLocation(methodInfo, reachLocTuple); + if (reachLocInferLoc.getTuple().startsWith(curPrefix)) { + reachableCommonPrefixSet.add(reachLocTuple); + } + } + + // check if the lattice has the relation in which higher prefix is + // actually lower than the current node + CompositeLocation prefixInferLoc = generateInferredCompositeLocation(methodInfo, curPrefix); + if (isGreaterThan(methodLattice, flowNodeInferLoc, prefixInferLoc)) { + reachableCommonPrefixSet.add(curPrefix); + } + + if (!reachableCommonPrefixSet.isEmpty()) { + // found reachable nodes that start with the prefix curPrefix + // need to assign a composite location + + // first, check if there are more than one the set of locations that has + // the same length of the longest reachable prefix, no way to assign + // a composite location to the input local var + prefixSanityCheck(prefixList, i, flowGraph, reachableNodeSet); + + Set> incomingCommonPrefixSet = + mapPrefixToIncomingLocTupleSet.get(curPrefix); + + int idx = curPrefix.size(); + NTuple element = incomingCommonPrefixSet.iterator().next(); + Descriptor desc = element.get(idx).getDescriptor(); + + SSJavaLattice lattice = getLattice(desc); + LocationInfo locInfo = getLocationInfo(desc); + + CompositeLocation inferLocation = + generateInferredCompositeLocation(methodInfo, flowNodelocTuple); + + // methodInfo.getInferLocation(localVarDesc); + CompositeLocation newInferLocation = new CompositeLocation(); + + System.out.println("PREV INFER LOCATION=" + inferLocation + " curPrefix=" + + curPrefix); + if (inferLocation.getTuple().startsWith(curPrefix)) { + // the same infer location is already existed. no need to do + // anything + return true; + } else { + // assign a new composite location + + // String oldMethodLocationSymbol = + // inferLocation.get(0).getLocIdentifier(); + String newLocSymbol = "Loc" + (SSJavaLattice.seed++); + for (int locIdx = 0; locIdx < curPrefix.size(); locIdx++) { + newInferLocation.addLocation(curPrefix.get(locIdx)); + } + Location newLocationElement = new Location(desc, newLocSymbol); + newInferLocation.addLocation(newLocationElement); + + // if (flowNode.getDescTuple().size() == 1) { + // maps local variable to location types of the common prefix + methodInfo.mapDescriptorToLocation(localVarDesc, newInferLocation.clone()); + // } + + // methodInfo.mapDescriptorToLocation(localVarDesc, newInferLocation); + addMapLocSymbolToInferredLocation(methodInfo.getMethodDesc(), localVarDesc, + newInferLocation); + methodInfo.removeMaplocalVarToLocSet(localVarDesc); + + // add the field/var descriptor to the set of the location symbol + int flowNodeTupleSize = flowNode.getDescTuple().size(); + Descriptor lastFlowNodeDesc = flowNode.getDescTuple().get(flowNodeTupleSize - 1); + int inferLocSize = newInferLocation.getSize(); + Location lastLoc = newInferLocation.get(inferLocSize - 1); + Descriptor enclosingDesc = lastLoc.getDescriptor(); + getLocationInfo(enclosingDesc).addMapLocSymbolToDescSet(lastLoc.getLocIdentifier(), + lastFlowNodeDesc); + + // clean up the previous location + // Location prevInferLocElement = + // inferLocation.get(inferLocation.getSize() - 1); + // Descriptor prevEnclosingDesc = prevInferLocElement.getDescriptor(); + // + // SSJavaLattice targetLattice; + // LocationInfo targetInfo; + // if (prevEnclosingDesc.equals(methodInfo.getMethodDesc())) { + // targetLattice = methodLattice; + // targetInfo = methodInfo; + // } else { + // targetLattice = getLattice(prevInferLocElement.getDescriptor()); + // targetInfo = getLocationInfo(prevInferLocElement.getDescriptor()); + // } + // + // Set> associstedDescSet = + // targetInfo.getRelatedInferLocSet(prevInferLocElement.getLocIdentifier()); + // + // if (associstedDescSet.size() == 1) { + // targetLattice.remove(prevInferLocElement.getLocIdentifier()); + // } else { + // associstedDescSet.remove(lastFlowNodeDesc); + // } + + } + + System.out.println("ASSIGN NEW COMPOSITE LOCATION =" + newInferLocation + " to " + + flowNode); + + String newlyInsertedLocName = + newInferLocation.get(newInferLocation.getSize() - 1).getLocIdentifier(); + + System.out.println("-- add in-flow"); + for (Iterator iterator = incomingCommonPrefixSet.iterator(); iterator.hasNext();) { + NTuple tuple = (NTuple) iterator.next(); + System.out.println("--in-flow tuple=" + tuple); + Location loc = tuple.get(idx); + String higher = locInfo.getFieldInferLocation(loc.getLocDescriptor()).getLocIdentifier(); + addRelationHigherToLower(lattice, locInfo, higher, newlyInsertedLocName); + } + + System.out.println("-- add local in-flow"); + for (Iterator iterator = localInNodeSet.iterator(); iterator.hasNext();) { + FlowNode localNode = (FlowNode) iterator.next(); + + if (localNode.equals(flowNode)) { + continue; + } + + CompositeLocation inNodeInferLoc = + generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(localNode)); + + if (isCompositeLocation(inNodeInferLoc)) { + // need to make sure that newLocSymbol is lower than the infernode + // location in the field lattice + System.out.println("----srcNode=" + localNode + " dstNode=" + flowNode); + addRelationToLattice(methodInfo.getMethodDesc(), methodLattice, methodInfo, localNode, + flowNode); + + } + + } + + System.out.println("-- add out flow"); + for (Iterator iterator = reachableCommonPrefixSet.iterator(); iterator.hasNext();) { + NTuple tuple = (NTuple) iterator.next(); + if (tuple.size() > idx) { + Location loc = tuple.get(idx); + String lower = locInfo.getFieldInferLocation(loc.getLocDescriptor()).getLocIdentifier(); + addRelationHigherToLower(lattice, locInfo, newlyInsertedLocName, lower); + } + } + + System.out.println("-- add local out flow"); + for (Iterator iterator = localOutNodeSet.iterator(); iterator.hasNext();) { + FlowNode localOutNode = (FlowNode) iterator.next(); + + if (localOutNode.equals(flowNode)) { + continue; + } + + CompositeLocation outNodeInferLoc = + generateInferredCompositeLocation(methodInfo, + flowGraph.getLocationTuple(localOutNode)); + + if (isCompositeLocation(outNodeInferLoc)) { + System.out.println("--- srcNode=" + flowNode + " dstNode=" + localOutNode); + addRelationToLattice(methodInfo.getMethodDesc(), methodLattice, methodInfo, flowNode, + localOutNode); + + } + } + System.out.println("-- end of add local out flow"); + + return true; + } + + } + + return false; + + } + + private void addMapLocSymbolToInferredLocation(MethodDescriptor md, Descriptor localVar, + CompositeLocation inferLoc) { + + Location locElement = inferLoc.get((inferLoc.getSize() - 1)); + Descriptor enclosingDesc = locElement.getDescriptor(); + LocationInfo locInfo = getLocationInfo(enclosingDesc); + locInfo.addMapLocSymbolToRelatedInferLoc(locElement.getLocIdentifier(), md, localVar); + } + + private boolean isCompositeLocation(CompositeLocation cl) { + return cl.getSize() > 1; + } + + private boolean containsNonPrimitiveElement(Set descSet) { + for (Iterator iterator = descSet.iterator(); iterator.hasNext();) { + Descriptor desc = (Descriptor) iterator.next(); + + if (desc.equals(LocationInference.GLOBALDESC)) { + return true; + } else if (desc instanceof VarDescriptor) { + if (!((VarDescriptor) desc).getType().isPrimitive()) { + return true; + } + } else if (desc instanceof FieldDescriptor) { + if (!((FieldDescriptor) desc).getType().isPrimitive()) { + return true; + } + } + + } + return false; + } + + private void addRelationHigherToLower(SSJavaLattice lattice, LocationInfo locInfo, + String higher, String lower) throws CyclicFlowException { + + System.out.println("---addRelationHigherToLower " + higher + " -> " + lower + + " to the lattice of " + locInfo.getDescIdentifier()); + // if (higher.equals(lower) && lattice.isSharedLoc(higher)) { + // return; + // } + Set cycleElementSet = lattice.getPossibleCycleElements(higher, lower); + + boolean hasNonPrimitiveElement = false; + for (Iterator iterator = cycleElementSet.iterator(); iterator.hasNext();) { + String cycleElementLocSymbol = (String) iterator.next(); + + Set descSet = locInfo.getDescSet(cycleElementLocSymbol); + if (containsNonPrimitiveElement(descSet)) { + hasNonPrimitiveElement = true; + break; + } + } + + if (hasNonPrimitiveElement) { + System.out.println("#Check cycle= " + lower + " < " + higher + " cycleElementSet=" + + cycleElementSet); + // if there is non-primitive element in the cycle, no way to merge cyclic + // elements into the shared location + throw new CyclicFlowException(); + } - System.out.println("higherLocIdxCallee=" + higherLocIdxCallee); - System.out.println("lowerLocIdxCallee=" + lowerLocIdxCallee); + if (cycleElementSet.size() > 0) { - NTuple higherArg = getArgTupleByArgIdx(methodInvokeNode, higherLocIdxCallee); - NTuple lowerArg = getArgTupleByArgIdx(methodInvokeNode, lowerLocIdxCallee); + String newSharedLoc = "SharedLoc" + (SSJavaLattice.seed++); - FlowNode callerHigherFlowNode = getFlowGraph(callerMethodDesc).getFlowNode(higherArg); - FlowNode calleeHigherFlowNode = getFlowGraph(callerMethodDesc).getFlowNode(lowerArg); + System.out.println("---ASSIGN NEW SHARED LOC=" + newSharedLoc + " to " + cycleElementSet); + lattice.mergeIntoSharedLocation(cycleElementSet, newSharedLoc); - addRelationToLattice(callerMethodDesc, getMethodLattice(callerMethodDesc), - callerHigherFlowNode, calleeHigherFlowNode); + for (Iterator iterator = cycleElementSet.iterator(); iterator.hasNext();) { + String oldLocSymbol = (String) iterator.next(); + + Set> inferLocSet = locInfo.getRelatedInferLocSet(oldLocSymbol); + System.out.println("---update related locations=" + inferLocSet); + for (Iterator iterator2 = inferLocSet.iterator(); iterator2.hasNext();) { + Pair pair = (Pair) iterator2.next(); + Descriptor enclosingDesc = pair.getFirst(); + Descriptor desc = pair.getSecond(); + + CompositeLocation inferLoc; + if (curMethodInfo.md.equals(enclosingDesc)) { + inferLoc = curMethodInfo.getInferLocation(desc); + } else { + inferLoc = getLocationInfo(enclosingDesc).getInferLocation(desc); + } + + Location locElement = inferLoc.get(inferLoc.getSize() - 1); + + locElement.setLocIdentifier(newSharedLoc); + locInfo.addMapLocSymbolToRelatedInferLoc(newSharedLoc, enclosingDesc, desc); + + if (curMethodInfo.md.equals(enclosingDesc)) { + inferLoc = curMethodInfo.getInferLocation(desc); + } else { + inferLoc = getLocationInfo(enclosingDesc).getInferLocation(desc); + } + System.out.println("---New Infer Loc=" + inferLoc); } + locInfo.removeRelatedInferLocSet(oldLocSymbol, newSharedLoc); + } + lattice.addSharedLoc(newSharedLoc); + + } else if (!lattice.isGreaterThan(higher, lower)) { + lattice.addRelationHigherToLower(higher, lower); } } - private void recursiveVisitNodes(MethodDescriptor md, FlowNode srcNode, FlowNode currentVisitNode) { + private void replaceOldLocWithNewLoc(SSJavaLattice methodLattice, String oldLocSymbol, + String newLocSymbol) { + + if (methodLattice.containsKey(oldLocSymbol)) { + methodLattice.substituteLocation(oldLocSymbol, newLocSymbol); + } + + } - NTuple srcTuple = srcNode.getDescTuple(); + private void prefixSanityCheck(List> prefixList, int curIdx, + FlowGraph flowGraph, Set reachableNodeSet) { - for (Iterator outEdgeIter = currentVisitNode.getOutEdgeSet().iterator(); outEdgeIter - .hasNext();) { + NTuple curPrefix = prefixList.get(curIdx); - FlowEdge outEdge = outEdgeIter.next(); - FlowNode newVisitNode = outEdge.getDst(); + for (int i = curIdx + 1; i < prefixList.size(); i++) { + NTuple prefixTuple = prefixList.get(i); - NTuple newVisitTuple = newVisitNode.getDescTuple(); + if (curPrefix.startsWith(prefixTuple)) { + continue; + } - // if both the source node and the newly visit node are parameters, - // need to keep this relation, then later add a new relation between - // corresponding arguments in the caller's lattice. - if (srcNode.isParameter() && newVisitNode.isParameter()) { - System.out.println("src=" + srcNode + " newVisitNode=" + newVisitNode); - propagateRelationToCaller(md, srcNode, newVisitNode); + for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) { + FlowNode reachableNode = (FlowNode) iterator2.next(); + NTuple reachLocTuple = flowGraph.getLocationTuple(reachableNode); + if (reachLocTuple.startsWith(prefixTuple)) { + // TODO + throw new Error("Failed to generate a composite location"); + } } + } + } + + public boolean isPrimitiveLocalVariable(FlowNode node) { + VarDescriptor varDesc = (VarDescriptor) node.getDescTuple().get(0); + return varDesc.getType().isPrimitive(); + } + private SSJavaLattice getLattice(Descriptor d) { + if (d instanceof MethodDescriptor) { + return getMethodLattice((MethodDescriptor) d); + } else { + return getFieldLattice((ClassDescriptor) d); } + } + + private SSJavaLattice getMethodLattice(MethodDescriptor md) { + if (!md2lattice.containsKey(md)) { + 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) { + FlowNode dstNode, int idx) throws CyclicFlowException { - 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()); + LocationInfo fieldInfo = getFieldLocationInfo(cd); + + String srcSymbol = fieldInfo.getFieldInferLocation(srcFieldDesc).getLocIdentifier(); + String dstSymbol = fieldInfo.getFieldInferLocation(dstFieldDesc).getLocIdentifier(); + + addRelationHigherToLower(fieldLattice, fieldInfo, srcSymbol, dstSymbol); } @@ -410,7 +1379,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); } @@ -419,19 +1388,50 @@ public class LocationInference { setupToAnalyze(); + Set visited = new HashSet(); + Set reachableCallee = new HashSet(); + while (!toAnalyzeIsEmpty()) { ClassDescriptor cd = toAnalyzeNext(); setupToAnalazeMethod(cd); + toanalyzeMethodList.removeAll(visited); + while (!toAnalyzeMethodIsEmpty()) { MethodDescriptor md = toAnalyzeMethodNext(); - if (ssjava.needTobeAnnotated(md)) { + if ((!visited.contains(md)) + && (ssjava.needTobeAnnotated(md) || reachableCallee.contains(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)); + } + Set calleeSet = ssjava.getCallGraph().getCalleeSet(md); + Set needToAnalyzeCalleeSet = new HashSet(); + + for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) { + MethodDescriptor calleemd = (MethodDescriptor) iterator.next(); + if ((!ssjava.isTrustMethod(calleemd)) + && (!ssjava.isSSJavaUtil(calleemd.getClassDesc()))) { + if (!visited.contains(calleemd)) { + toanalyzeMethodList.add(calleemd); + } + reachableCallee.add(calleemd); + needToAnalyzeCalleeSet.add(calleemd); + } + } + + mapMethodToCalleeSet.put(md, needToAnalyzeCalleeSet); + + // 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++) { @@ -442,7 +1442,9 @@ public class LocationInference { FlowGraph fg = new FlowGraph(md, mapParamDescToIdx); mapMethodDescriptorToFlowGraph.put(md, fg); + visited.add(md); analyzeMethodBody(cd, md); + } } } @@ -488,7 +1490,7 @@ public class LocationInference { break; case Kind.ReturnNode: - analyzeReturnNode(md, nametable, (ReturnNode) bsn); + analyzeFlowReturnNode(md, nametable, (ReturnNode) bsn, implicitFlowTupleSet); break; case Kind.SubBlockNode: @@ -509,7 +1511,6 @@ public class LocationInference { private void analyzeSwitchStatementNode(MethodDescriptor md, SymbolTable nametable, SwitchStatementNode bsn) { // TODO Auto-generated method stub - } private void analyzeFlowSubBlockNode(MethodDescriptor md, SymbolTable nametable, @@ -517,8 +1518,27 @@ 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(); + + if (returnExp != null) { + 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); + } + } + } } @@ -538,8 +1558,11 @@ public class LocationInference { } else { // check 'for loop' case BlockNode bn = ln.getInitializer(); - analyzeFlowBlockNode(md, bn.getVarTable(), bn, implicitFlowTupleSet); bn.getVarTable().setParent(nametable); + for (int i = 0; i < bn.size(); i++) { + BlockStatementNode bsn = bn.get(i); + analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet); + } NodeTupleSet condTupleNode = new NodeTupleSet(); analyzeFlowExpressionNode(md, bn.getVarTable(), ln.getCondition(), condTupleNode, null, @@ -611,28 +1634,33 @@ 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; switch (en.kind()) { case Kind.AssignmentNode: - analyzeFlowAssignmentNode(md, nametable, (AssignmentNode) en, base, implicitFlowTupleSet); + analyzeFlowAssignmentNode(md, nametable, (AssignmentNode) en, nodeSet, base, + implicitFlowTupleSet); break; case Kind.FieldAccessNode: flowTuple = analyzeFlowFieldAccessNode(md, nametable, (FieldAccessNode) en, nodeSet, base, - implicitFlowTupleSet); - nodeSet.addTuple(flowTuple); + implicitFlowTupleSet, isLHS); + if (flowTuple != null) { + nodeSet.addTuple(flowTuple); + } return flowTuple; case Kind.NameNode: NodeTupleSet nameNodeSet = new NodeTupleSet(); flowTuple = analyzeFlowNameNode(md, nametable, (NameNode) en, nameNodeSet, base, implicitFlowTupleSet); - nodeSet.addTuple(flowTuple); + if (flowTuple != null) { + nodeSet.addTuple(flowTuple); + } return flowTuple; case Kind.OpNode: @@ -660,9 +1688,8 @@ public class LocationInference { break; case Kind.CastNode: - analyzeFlowCastNode(md, nametable, (CastNode) en, implicitFlowTupleSet); + analyzeFlowCastNode(md, nametable, (CastNode) en, nodeSet, base, implicitFlowTupleSet); break; - // case Kind.InstanceOfNode: // checkInstanceOfNode(md, nametable, (InstanceOfNode) en, td); // return null; @@ -686,25 +1713,22 @@ public class LocationInference { } private void analyzeFlowCastNode(MethodDescriptor md, SymbolTable nametable, CastNode cn, - NodeTupleSet implicitFlowTupleSet) { + NodeTupleSet nodeSet, NTuple base, NodeTupleSet implicitFlowTupleSet) { - NodeTupleSet nodeTupleSet = new NodeTupleSet(); - analyzeFlowExpressionNode(md, nametable, cn.getExpression(), nodeTupleSet, false); + analyzeFlowExpressionNode(md, nametable, cn.getExpression(), nodeSet, base, + implicitFlowTupleSet, false); } 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); @@ -745,8 +1769,7 @@ 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, + analyzeFlowExpressionNode(md, nametable, min.getExpression(), baseNodeSet, null, implicitFlowTupleSet, false); } else { @@ -790,7 +1813,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 = @@ -804,17 +1827,17 @@ public class LocationInference { } - private NTuple getArgTupleByArgIdx(MethodInvokeNode min, int idx) { + private NodeTupleSet getNodeTupleSetByArgIdx(MethodInvokeNode min, int idx) { return mapMethodInvokeNodeToArgIdxMap.get(min).get(new Integer(idx)); } - private void addArgIdxMap(MethodInvokeNode min, int idx, NTuple argTuple) { - Map> mapIdxToArgTuple = mapMethodInvokeNodeToArgIdxMap.get(min); - if (mapIdxToArgTuple == null) { - mapIdxToArgTuple = new HashMap>(); - mapMethodInvokeNodeToArgIdxMap.put(min, mapIdxToArgTuple); + private void addArgIdxMap(MethodInvokeNode min, int idx, NodeTupleSet tupleSet) { + Map mapIdxToTupleSet = mapMethodInvokeNodeToArgIdxMap.get(min); + if (mapIdxToTupleSet == null) { + mapIdxToTupleSet = new HashMap(); + mapMethodInvokeNodeToArgIdxMap.put(min, mapIdxToTupleSet); } - mapIdxToArgTuple.put(new Integer(idx), argTuple); + mapIdxToTupleSet.put(new Integer(idx), tupleSet); } private void analyzeFlowMethodParameters(MethodDescriptor callermd, SymbolTable nametable, @@ -822,14 +1845,24 @@ public class LocationInference { if (min.numArgs() > 0) { - int offset = min.getMethod().isStatic() ? 0 : 1; + int offset; + if (min.getMethod().isStatic()) { + offset = 0; + } else { + offset = 1; + NTuple thisArgTuple = new NTuple(); + thisArgTuple.add(callermd.getThis()); + NodeTupleSet argTupleSet = new NodeTupleSet(); + argTupleSet.addTuple(thisArgTuple); + addArgIdxMap(min, 0, argTupleSet); + } for (int i = 0; i < min.numArgs(); i++) { ExpressionNode en = min.getArg(i); - NTuple argTuple = - analyzeFlowExpressionNode(callermd, nametable, en, new NodeTupleSet(), false); - - addArgIdxMap(min, i + offset, argTuple); + NodeTupleSet argTupleSet = new NodeTupleSet(); + analyzeFlowExpressionNode(callermd, nametable, en, argTupleSet, false); + // if argument is liternal node, argTuple is set to NULL. + addArgIdxMap(min, i + offset, argTupleSet); } } @@ -837,7 +1870,6 @@ public class LocationInference { } private void analyzeLiteralNode(MethodDescriptor md, SymbolTable nametable, LiteralNode en) { - // TODO Auto-generated method stub } @@ -852,7 +1884,6 @@ public class LocationInference { if (isLHS) { // need to create an edge from idx to array - for (Iterator> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) { NTuple idxTuple = idxIter.next(); for (Iterator> arrIter = expNodeTupleSet.iterator(); arrIter.hasNext();) { @@ -866,7 +1897,6 @@ public class LocationInference { nodeSet.addTupleSet(expNodeTupleSet); nodeSet.addTupleSet(idxNodeTupleSet); } - } private void analyzeCreateObjectNode(MethodDescriptor md, SymbolTable nametable, @@ -882,17 +1912,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(); @@ -936,6 +1962,7 @@ public class LocationInference { default: throw new Error(op.toString()); } + } private NTuple analyzeFlowNameNode(MethodDescriptor md, SymbolTable nametable, @@ -948,8 +1975,13 @@ public class LocationInference { NameDescriptor nd = nn.getName(); if (nd.getBase() != null) { - analyzeFlowExpressionNode(md, nametable, nn.getExpression(), nodeSet, base, - implicitFlowTupleSet, false); + base = + analyzeFlowExpressionNode(md, nametable, nn.getExpression(), nodeSet, base, + implicitFlowTupleSet, false); + if (base == null) { + // base node has the top location + return base; + } } else { String varname = nd.toString(); if (varname.equals("this")) { @@ -968,22 +2000,13 @@ 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', no need to have flow node for the TOP + // location + return null; } 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 @@ -994,6 +2017,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); @@ -1021,7 +2048,7 @@ public class LocationInference { private NTuple analyzeFlowFieldAccessNode(MethodDescriptor md, SymbolTable nametable, FieldAccessNode fan, NodeTupleSet nodeSet, NTuple base, - NodeTupleSet implicitFlowTupleSet) { + NodeTupleSet implicitFlowTupleSet, boolean isLHS) { ExpressionNode left = fan.getExpression(); TypeDescriptor ltd = left.getType(); @@ -1036,38 +2063,62 @@ public class LocationInference { 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; + return null; } } - // if (left instanceof ArrayAccessNode) { - // ArrayAccessNode aan = (ArrayAccessNode) left; - // left = aan.getExpression(); - // } - // fanNodeSet + NodeTupleSet idxNodeTupleSet = new NodeTupleSet(); + if (left instanceof ArrayAccessNode) { + + ArrayAccessNode aan = (ArrayAccessNode) left; + left = aan.getExpression(); + analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, base, + implicitFlowTupleSet, isLHS); + nodeSet.addTupleSet(idxNodeTupleSet); + } base = - analyzeFlowExpressionNode(md, nametable, left, nodeSet, base, implicitFlowTupleSet, false); + analyzeFlowExpressionNode(md, nametable, left, nodeSet, base, implicitFlowTupleSet, isLHS); - if (!left.getType().isPrimitive()) { + if (base == null) { + // in this case, field is TOP location + return null; + } else { + + NTuple flowFieldTuple = new NTuple(base.toList()); + + if (!left.getType().isPrimitive()) { + + if (!fd.getSymbol().equals("length")) { + // array.length access, just have the location of the array + flowFieldTuple.add(fd); + nodeSet.removeTuple(base); + } - if (fd.getSymbol().equals("length")) { - // TODO - // array.length access, return the location of the array - // return loc; } + getFlowGraph(md).createNewFlowNode(flowFieldTuple); + + if (isLHS) { + for (Iterator> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) { + NTuple idxTuple = idxIter.next(); + getFlowGraph(md).addValueFlowEdge(idxTuple, flowFieldTuple); + } + } + + return flowFieldTuple; - base.add(fd); } - return base; + } + + 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("analyzeFlowAssignmentNode=" + an); + AssignmentNode an, NodeTupleSet nodeSet, NTuple base, + NodeTupleSet implicitFlowTupleSet) { NodeTupleSet nodeSetRHS = new NodeTupleSet(); NodeTupleSet nodeSetLHS = new NodeTupleSet(); @@ -1078,18 +2129,32 @@ public class LocationInference { .getBaseOp().getOp() != Operation.POSTDEC)) { postinc = false; } - // if LHS is array access node, need to capture value flows between an array // 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); + + // System.out.println("-analyzeFlowAssignmentNode=" + an.printNode(0)); + // System.out.println("-nodeSetLHS=" + nodeSetLHS); + // System.out.println("-nodeSetRHS=" + nodeSetRHS); + // System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet); + // System.out.println("-"); + + 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();) { @@ -1116,17 +2181,33 @@ public class LocationInference { addFlowGraphEdge(md, tuple, tuple); } + // creates edges from implicitFlowTupleSet to LHS + for (Iterator> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) { + NTuple fromTuple = iter.next(); + for (Iterator> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) { + NTuple toTuple = iter2.next(); + addFlowGraphEdge(md, fromTuple, toTuple); + } + } + } + if (nodeSet != null) { + nodeSet.addTupleSet(nodeSetLHS); + } } public FlowGraph getFlowGraph(MethodDescriptor md) { return mapMethodDescriptorToFlowGraph.get(md); } - public void addFlowGraphEdge(MethodDescriptor md, NTuple from, NTuple to) { + private boolean addFlowGraphEdge(MethodDescriptor md, NTuple from, + NTuple to) { + // TODO + // return true if it adds a new edge FlowGraph graph = getFlowGraph(md); graph.addValueFlowEdge(from, to); + return true; } public void _debug_printGraph() { @@ -1146,7 +2227,6 @@ public class LocationInference { } -class ParamIndexRelation { - private Integer higherIdx; - private Integer lowerIdx; +class CyclicFlowException extends Exception { + }