X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=Robust%2Fsrc%2FAnalysis%2FSSJava%2FLocationInference.java;h=981d942b4f878ff4286a31cdfaae980eb2020509;hb=c4e15379352959519956d9b77b723f441aa237b3;hp=688627cf5d2f7efb9dd581490d59a59344d7df06;hpb=531f76a639946cbb8080845674ccdba3c5fe1c2f;p=IRC.git diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index 688627cf..981d942b 100644 --- a/Robust/src/Analysis/SSJava/LocationInference.java +++ b/Robust/src/Analysis/SSJava/LocationInference.java @@ -47,6 +47,7 @@ import IR.Tree.NameNode; import IR.Tree.OpNode; import IR.Tree.ReturnNode; import IR.Tree.SubBlockNode; +import IR.Tree.SwitchBlockNode; import IR.Tree.SwitchStatementNode; import IR.Tree.TertiaryNode; import IR.Tree.TreeNode; @@ -57,10 +58,12 @@ public class LocationInference { State state; SSJavaAnalysis ssjava; - List toanalyzeList; - List toanalyzeMethodList; + List temp_toanalyzeList; + List temp_toanalyzeMethodList; Map mapMethodDescriptorToFlowGraph; + LinkedList toanalyze_methodDescList; + // map a method descriptor to its set of parameter descriptors Map> mapMethodDescriptorToParamDescSet; @@ -73,11 +76,27 @@ public class LocationInference { // map a method descriptor to a method lattice private Map> md2lattice; + // map a method/class descriptor to a hierarchy graph + private Map mapDescriptorToHierarchyGraph; + + // map a method/class descriptor to a skeleton hierarchy graph + private Map mapDescriptorToSkeletonHierarchyGraph; + + private Map mapDescriptorToSimpleHierarchyGraph; + + // map a method/class descriptor to a skeleton hierarchy graph with combination nodes + private Map mapDescriptorToCombineSkeletonHierarchyGraph; + + // map a descriptor to a simple lattice + private Map> mapDescriptorToSimpleLattice; + // 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> mapMethodInvokeNodeToBaseTuple; private Map mapMethodDescToMethodLocationInfo; @@ -91,10 +110,20 @@ public class LocationInference { private Map mapDescToDefinitionLine; + private Map mapDescToLocationSummary; + + // maps a method descriptor to a sub global flow graph that captures all value flows caused by the + // set of callees reachable from the method + private Map mapMethodDescriptorToSubGlobalFlowGraph; + + private Map, NTuple>> mapMethodInvokeNodeToMapCallerArgToCalleeArg; + public static final String GLOBALLOC = "GLOBALLOC"; public static final String TOPLOC = "TOPLOC"; + public static final String INTERLOC = "INTERLOC"; + public static final Descriptor GLOBALDESC = new NameDescriptor(GLOBALLOC); public static final Descriptor TOPDESC = new NameDescriptor(TOPLOC); @@ -105,11 +134,13 @@ public class LocationInference { boolean debug = true; + private static int locSeed = 0; + public LocationInference(SSJavaAnalysis ssjava, State state) { this.ssjava = ssjava; this.state = state; - this.toanalyzeList = new ArrayList(); - this.toanalyzeMethodList = new ArrayList(); + this.temp_toanalyzeList = new ArrayList(); + this.temp_toanalyzeMethodList = new ArrayList(); this.mapMethodDescriptorToFlowGraph = new HashMap(); this.cd2lattice = new HashMap>(); this.md2lattice = new HashMap>(); @@ -117,7 +148,7 @@ public class LocationInference { this.mapMethodDescriptorToMethodInvokeNodeSet = new HashMap>(); this.mapMethodInvokeNodeToArgIdxMap = - new HashMap>(); + new HashMap>>(); this.mapMethodDescToMethodLocationInfo = new HashMap(); this.mapMethodToCalleeSet = new HashMap>(); this.mapClassToLocationInfo = new HashMap(); @@ -126,12 +157,29 @@ public class LocationInference { this.mapDescToDefinitionLine = new HashMap(); this.mapMethodDescToParamNodeFlowsToReturnValue = new HashMap>(); + + this.mapDescriptorToHierarchyGraph = new HashMap(); + this.mapMethodInvokeNodeToBaseTuple = new HashMap>(); + + this.mapDescriptorToSkeletonHierarchyGraph = new HashMap(); + this.mapDescriptorToCombineSkeletonHierarchyGraph = new HashMap(); + this.mapDescriptorToSimpleHierarchyGraph = new HashMap(); + + this.mapDescriptorToSimpleLattice = new HashMap>(); + + this.mapDescToLocationSummary = new HashMap(); + + this.mapMethodDescriptorToSubGlobalFlowGraph = new HashMap(); + + this.mapMethodInvokeNodeToMapCallerArgToCalleeArg = + new HashMap, NTuple>>(); + } public void setupToAnalyze() { SymbolTable classtable = state.getClassSymbolTable(); - toanalyzeList.clear(); - toanalyzeList.addAll(classtable.getValueSet()); + temp_toanalyzeList.clear(); + temp_toanalyzeList.addAll(classtable.getValueSet()); // Collections.sort(toanalyzeList, new Comparator() { // public int compare(ClassDescriptor o1, ClassDescriptor o2) { // return o1.getClassName().compareToIgnoreCase(o2.getClassName()); @@ -142,9 +190,9 @@ public class LocationInference { public void setupToAnalazeMethod(ClassDescriptor cd) { SymbolTable methodtable = cd.getMethodTable(); - toanalyzeMethodList.clear(); - toanalyzeMethodList.addAll(methodtable.getValueSet()); - Collections.sort(toanalyzeMethodList, new Comparator() { + temp_toanalyzeMethodList.clear(); + temp_toanalyzeMethodList.addAll(methodtable.getValueSet()); + Collections.sort(temp_toanalyzeMethodList, new Comparator() { public int compare(MethodDescriptor o1, MethodDescriptor o2) { return o1.getSymbol().compareToIgnoreCase(o2.getSymbol()); } @@ -152,19 +200,19 @@ public class LocationInference { } public boolean toAnalyzeMethodIsEmpty() { - return toanalyzeMethodList.isEmpty(); + return temp_toanalyzeMethodList.isEmpty(); } public boolean toAnalyzeIsEmpty() { - return toanalyzeList.isEmpty(); + return temp_toanalyzeList.isEmpty(); } public ClassDescriptor toAnalyzeNext() { - return toanalyzeList.remove(0); + return temp_toanalyzeList.remove(0); } public MethodDescriptor toAnalyzeMethodNext() { - return toanalyzeMethodList.remove(0); + return temp_toanalyzeMethodList.remove(0); } public void inference() { @@ -172,289 +220,1528 @@ public class LocationInference { // 1) construct value flow graph constructFlowGraph(); + assignCompositeLocation(); + + // constructGlobalFlowGraph(); + + System.exit(0); + + constructHierarchyGraph(); + + debug_writeHierarchyDotFiles(); + + simplifyHierarchyGraph(); + + debug_writeSimpleHierarchyDotFiles(); + + constructSkeletonHierarchyGraph(); + + debug_writeSkeletonHierarchyDotFiles(); + + insertCombinationNodes(); + + debug_writeSkeletonCombinationHierarchyDotFiles(); + + buildLattice(); + + debug_writeLattices(); + + generateMethodSummary(); + + System.exit(0); + // 2) construct lattices inferLattices(); - simplifyLattices(); - - debug_writeLatticeDotFile(); + // simplifyLattices(); // 3) check properties checkLattices(); + // calculate RETURNLOC,PCLOC + calculateExtraLocations(); + + debug_writeLatticeDotFile(); + // 4) generate annotated source codes generateAnnoatedCode(); } - private void addMapClassDefinitionToLineNum(ClassDescriptor cd, String strLine, int lineNum) { + public Map, NTuple> getMapCallerArgToCalleeParam( + MethodInvokeNode min) { - String classSymbol = cd.getSymbol(); - int idx = classSymbol.lastIndexOf("$"); - if (idx != -1) { - classSymbol = classSymbol.substring(idx + 1); + if (!mapMethodInvokeNodeToMapCallerArgToCalleeArg.containsKey(min)) { + mapMethodInvokeNodeToMapCallerArgToCalleeArg.put(min, + new HashMap, NTuple>()); } - String pattern = "class " + classSymbol + " "; - if (strLine.indexOf(pattern) != -1) { - mapDescToDefinitionLine.put(cd, lineNum); - } + return mapMethodInvokeNodeToMapCallerArgToCalleeArg.get(min); } - private void addMapMethodDefinitionToLineNum(Set methodSet, String strLine, - int lineNum) { - for (Iterator iterator = methodSet.iterator(); iterator.hasNext();) { - MethodDescriptor md = (MethodDescriptor) iterator.next(); - String pattern = md.getMethodDeclaration(); - if (strLine.indexOf(pattern) != -1) { - mapDescToDefinitionLine.put(md, lineNum); - methodSet.remove(md); - return; - } - } + public void addMapCallerArgToCalleeParam(MethodInvokeNode min, NTuple callerArg, + NTuple calleeParam) { + // System.out.println("min=" + min + " arg=" + callerArg + " param=" + calleeParam); + getMapCallerArgToCalleeParam(min).put(callerArg, calleeParam); + } + private void assignCompositeLocation() { + calculateGlobalValueFlowCompositeLocation(); + translateCompositeLocationAssignmentToFlowGraph(); + _debug_printGraph(); } - private void readOriginalSourceFiles() { + private void translateCompositeLocationAssignmentToFlowGraph() { - SymbolTable classtable = state.getClassSymbolTable(); + MethodDescriptor methodEventLoopDesc = ssjava.getMethodContainingSSJavaLoop(); + translateCompositeLocationAssignmentToFlowGraph(methodEventLoopDesc); - Set classDescSet = new HashSet(); - classDescSet.addAll(classtable.getValueSet()); + } - try { - // inefficient implement. it may re-visit the same file if the file - // contains more than one class definitions. - for (Iterator iterator = classDescSet.iterator(); iterator.hasNext();) { - ClassDescriptor cd = (ClassDescriptor) iterator.next(); + private void translateCompositeLocationAssignmentToFlowGraph(MethodDescriptor mdCaller) { - Set methodSet = new HashSet(); - methodSet.addAll(cd.getMethodTable().getValueSet()); + System.out.println("\n#translateCompositeLocationAssignmentToFlowGraph=" + mdCaller); - String sourceFileName = cd.getSourceFileName(); - Vector lineVec = new Vector(); + // First, assign a composite location to a node in the flow graph + GlobalFlowGraph callerGlobalFlowGraph = getSubGlobalFlowGraph(mdCaller); - mapFileNameToLineVector.put(sourceFileName, lineVec); + FlowGraph callerFlowGraph = getFlowGraph(mdCaller); + Map callerMapLocToCompLoc = + callerGlobalFlowGraph.getMapLocationToInferCompositeLocation(); + Set methodLocSet = callerMapLocToCompLoc.keySet(); + for (Iterator iterator = methodLocSet.iterator(); iterator.hasNext();) { + Location methodLoc = (Location) iterator.next(); + if (methodLoc.getDescriptor().equals(mdCaller)) { + CompositeLocation inferCompLoc = callerMapLocToCompLoc.get(methodLoc); + assignCompositeLocationToFlowGraph(callerFlowGraph, methodLoc, inferCompLoc); + } + } - BufferedReader in = new BufferedReader(new FileReader(sourceFileName)); - String strLine; - int lineNum = 1; - lineVec.add(""); // the index is started from 1. - while ((strLine = in.readLine()) != null) { - lineVec.add(lineNum, strLine); - addMapClassDefinitionToLineNum(cd, strLine, lineNum); - addMapMethodDefinitionToLineNum(methodSet, strLine, lineNum); - lineNum++; - } + Set minSet = mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller); - } + Set calleeSet = new HashSet(); + for (Iterator iterator = minSet.iterator(); iterator.hasNext();) { + MethodInvokeNode min = (MethodInvokeNode) iterator.next(); + // need to translate a composite location that is started with the base tuple of 'min'. + translateMapLocationToInferCompositeLocationToCalleeGraph(callerGlobalFlowGraph, min); + calleeSet.add(min.getMethod()); + } - } catch (IOException e) { - e.printStackTrace(); + for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) { + MethodDescriptor callee = (MethodDescriptor) iterator.next(); + translateCompositeLocationAssignmentToFlowGraph(callee); } } - private String generateLatticeDefinition(Descriptor desc) { + public void assignCompositeLocationToFlowGraph(FlowGraph flowGraph, Location loc, + CompositeLocation inferCompLoc) { + Descriptor localDesc = loc.getLocDescriptor(); - Set sharedLocSet = new HashSet(); + Set nodeSet = flowGraph.getNodeSet(); + for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + FlowNode node = (FlowNode) iterator.next(); + if (node.getDescTuple().startsWith(localDesc)) { + // need to assign the inferred composite location to this node + CompositeLocation newCompLoc = generateCompositeLocation(node.getDescTuple(), inferCompLoc); + node.setCompositeLocation(newCompLoc); + System.out.println("SET Node=" + node + " inferCompLoc=" + newCompLoc); + } + } + } - SSJavaLattice lattice = getLattice(desc); - String rtr = "@LATTICE(\""; + private CompositeLocation generateCompositeLocation(NTuple nodeDescTuple, + CompositeLocation inferCompLoc) { - Map> map = lattice.getTable(); - Set keySet = map.keySet(); - boolean first = true; - for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { - String key = (String) iterator.next(); - if (!key.equals(lattice.getTopItem())) { - Set connectedSet = map.get(key); + System.out.println("generateCompositeLocation=" + nodeDescTuple + " with inferCompLoc=" + + inferCompLoc); - if (connectedSet.size() == 1) { - if (connectedSet.iterator().next().equals(lattice.getBottomItem())) { - if (!first) { - rtr += ","; - } else { - rtr += "LOC,"; - first = false; - } - rtr += key; - if (lattice.isSharedLoc(key)) { - rtr += "," + key + "*"; - } - } - } + CompositeLocation newCompLoc = new CompositeLocation(); + for (int i = 0; i < inferCompLoc.getSize(); i++) { + newCompLoc.addLocation(inferCompLoc.get(i)); + } - for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) { - String loc = (String) iterator2.next(); - if (!loc.equals(lattice.getBottomItem())) { - if (!first) { - rtr += ","; - } else { - rtr += "LOC,"; - first = false; - } - rtr += loc + "<" + key; - if (lattice.isSharedLoc(key) && (!sharedLocSet.contains(key))) { - rtr += "," + key + "*"; - sharedLocSet.add(key); - } - if (lattice.isSharedLoc(loc) && (!sharedLocSet.contains(loc))) { - rtr += "," + loc + "*"; - sharedLocSet.add(loc); - } + Descriptor lastDescOfPrefix = nodeDescTuple.get(0); + Descriptor enclosingDescriptor; + if (lastDescOfPrefix instanceof InterDescriptor) { + enclosingDescriptor = null; + } else { + enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc(); + } - } - } - } + for (int i = 1; i < nodeDescTuple.size(); i++) { + Descriptor desc = nodeDescTuple.get(i); + Location locElement = new Location(enclosingDescriptor, desc); + newCompLoc.addLocation(locElement); + + enclosingDescriptor = ((FieldDescriptor) desc).getClassDescriptor(); } - rtr += "\")"; + return newCompLoc; + } - if (desc instanceof MethodDescriptor) { - TypeDescriptor returnType = ((MethodDescriptor) desc).getReturnType(); + private void translateMapLocationToInferCompositeLocationToCalleeGraph( + GlobalFlowGraph callerGraph, MethodInvokeNode min) { - MethodLocationInfo methodLocInfo = getMethodLocationInfo((MethodDescriptor) desc); + MethodDescriptor mdCallee = min.getMethod(); + MethodDescriptor mdCaller = callerGraph.getMethodDescriptor(); + Map callerMapLocToCompLoc = + callerGraph.getMapLocationToInferCompositeLocation(); - if (returnType != null && (!returnType.isVoid())) { - rtr += - "\n@RETURNLOC(\"" + generateLocationAnnoatation(methodLocInfo.getReturnLoc()) + "\")"; - } - rtr += "\n@THISLOC(\"this\")\n@GLOBALLOC(\"GLOBALLOC\")"; + FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); + GlobalFlowGraph calleeGlobalGraph = getSubGlobalFlowGraph(mdCallee); - if (lattice.containsKey("PCLOC")) { - rtr += "\n@PCLOC(\"PCLOC\")"; + NTuple baseLocTuple = + translateToLocTuple(mdCaller, mapMethodInvokeNodeToBaseTuple.get(min)); + + System.out.println("-translate caller infer composite loc to callee=" + mdCallee); + Set keySet = callerMapLocToCompLoc.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Location key = (Location) iterator.next(); + CompositeLocation callerCompLoc = callerMapLocToCompLoc.get(key); + + if (!key.getDescriptor().equals(mdCaller) + && callerCompLoc.getTuple().startsWith(baseLocTuple)) { + // need to translate to the callee side + // System.out.println("need to translate callerCompLoc=" + callerCompLoc + + // " with baseTuple=" + // + baseLocTuple); + // TODO + CompositeLocation newCalleeCompLoc = + translateCompositeLocationToCallee(callerCompLoc, baseLocTuple, mdCallee); + calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, newCalleeCompLoc); + System.out.println("---callee loc=" + key + " newCalleeCompLoc=" + newCalleeCompLoc); } } - return rtr; - } + // If the location of an argument has a composite location + // need to assign a proper composite location to the corresponding callee parameter + System.out.println("-translate arg composite location to callee param:"); + Map> mapIdxToArgTuple = mapMethodInvokeNodeToArgIdxMap.get(min); + Set idxSet = mapIdxToArgTuple.keySet(); + for (Iterator iterator = idxSet.iterator(); iterator.hasNext();) { + Integer idx = (Integer) iterator.next(); - private void generateAnnoatedCode() { + if (idx == 0 && !min.getMethod().isStatic()) { + continue; + } - readOriginalSourceFiles(); + NTuple argTuple = mapIdxToArgTuple.get(idx); - setupToAnalyze(); - while (!toAnalyzeIsEmpty()) { - ClassDescriptor cd = toAnalyzeNext(); + // check if an arg tuple has been already assigned to a composite location + NTuple argLocTuple = translateToLocTuple(mdCaller, argTuple); + Location argLocalLoc = argLocTuple.get(0); - setupToAnalazeMethod(cd); + // if (!isPrimitiveType(argTuple)) { + if (callerMapLocToCompLoc.containsKey(argLocalLoc)) { - LocationInfo locInfo = mapClassToLocationInfo.get(cd); - String sourceFileName = cd.getSourceFileName(); + CompositeLocation callerCompLoc = callerMapLocToCompLoc.get(argLocalLoc); + for (int i = 1; i < argLocTuple.size(); i++) { + callerCompLoc.addLocation(argLocTuple.get(i)); + } - if (cd.isInterface()) { - continue; - } + if (callerCompLoc.getTuple().startsWith(baseLocTuple)) { - int classDefLine = mapDescToDefinitionLine.get(cd); - Vector sourceVec = mapFileNameToLineVector.get(sourceFileName); + FlowNode calleeParamFlowNode = calleeFlowGraph.getParamFlowNode(idx); + NTuple calleeParamDescTuple = calleeParamFlowNode.getDescTuple(); + NTuple calleeParamLocTuple = + translateToLocTuple(mdCallee, calleeParamDescTuple); - if (locInfo == null) { - locInfo = getLocationInfo(cd); - } + CompositeLocation newCalleeCompLoc = + translateCompositeLocationToCallee(callerCompLoc, baseLocTuple, mdCallee); - for (Iterator iter = cd.getFields(); iter.hasNext();) { - Descriptor fieldDesc = (Descriptor) iter.next(); - String locIdentifier = locInfo.getFieldInferLocation(fieldDesc).getLocIdentifier(); - if (!getLattice(cd).containsKey(locIdentifier)) { - getLattice(cd).put(locIdentifier); + calleeGlobalGraph.addMapLocationToInferCompositeLocation(calleeParamLocTuple.get(0), + newCalleeCompLoc); + + System.out.println("###need to assign composite location to=" + calleeParamDescTuple + + " with baseTuple=" + baseLocTuple); + System.out.println("---newCalleeCompLoc=" + newCalleeCompLoc); } + } - String fieldLatticeDefStr = generateLatticeDefinition(cd); - String annoatedSrc = fieldLatticeDefStr + newline + sourceVec.get(classDefLine); - sourceVec.set(classDefLine, annoatedSrc); + } - // generate annotations for field declarations - LocationInfo fieldLocInfo = getLocationInfo(cd); - Map inferLocMap = fieldLocInfo.getMapDescToInferLocation(); + } - for (Iterator iter = cd.getFields(); iter.hasNext();) { - FieldDescriptor fd = (FieldDescriptor) iter.next(); + private boolean isPrimitiveType(NTuple argTuple) { - String locAnnotationStr; - if (inferLocMap.containsKey(fd)) { - CompositeLocation inferLoc = inferLocMap.get(fd); - locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")"; - } else { - // if the field is not accssed by SS part, just assigns dummy - // location - locAnnotationStr = "@LOC(\"LOC\")"; - } - int fdLineNum = fd.getLineNum(); - String orgFieldDeclarationStr = sourceVec.get(fdLineNum); - String fieldDeclaration = fd.toString(); - fieldDeclaration = fieldDeclaration.substring(0, fieldDeclaration.length() - 1); + Descriptor lastDesc = argTuple.get(argTuple.size() - 1); - String annoatedStr = locAnnotationStr + " " + orgFieldDeclarationStr; - sourceVec.set(fdLineNum, annoatedStr); + if (lastDesc instanceof FieldDescriptor) { + return ((FieldDescriptor) lastDesc).getType().isPrimitive(); + } else if (lastDesc instanceof VarDescriptor) { + return ((VarDescriptor) lastDesc).getType().isPrimitive(); + } - } + return true; + } - while (!toAnalyzeMethodIsEmpty()) { - MethodDescriptor md = toAnalyzeMethodNext(); + private CompositeLocation translateCompositeLocationToCallee(CompositeLocation callerCompLoc, + NTuple baseLocTuple, MethodDescriptor mdCallee) { - if (!ssjava.needTobeAnnotated(md)) { - continue; - } + CompositeLocation newCalleeCompLoc = new CompositeLocation(); - SSJavaLattice methodLattice = md2lattice.get(md); - if (methodLattice != null) { + // replace the last element of the caller compLoc with the 'this' location of the callee + for (int i = 0; i < baseLocTuple.size() - 1; i++) { + newCalleeCompLoc.addLocation(baseLocTuple.get(i)); + } - int methodDefLine = md.getLineNum(); + Location calleeThisLoc = new Location(mdCallee, mdCallee.getThis()); + newCalleeCompLoc.addLocation(calleeThisLoc); - MethodLocationInfo methodLocInfo = getMethodLocationInfo(md); + for (int i = baseLocTuple.size(); i < callerCompLoc.getSize(); i++) { + newCalleeCompLoc.addLocation(callerCompLoc.get(i)); + } - Map methodInferLocMap = - methodLocInfo.getMapDescToInferLocation(); - Set localVarDescSet = methodInferLocMap.keySet(); + return newCalleeCompLoc; - for (Iterator iterator = localVarDescSet.iterator(); iterator.hasNext();) { - Descriptor localVarDesc = (Descriptor) iterator.next(); - CompositeLocation inferLoc = methodInferLocMap.get(localVarDesc); + } - String locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")"; + private void constructGlobalFlowGraph() { - if (!isParameter(md, localVarDesc)) { - if (mapDescToDefinitionLine.containsKey(localVarDesc)) { - int varLineNum = mapDescToDefinitionLine.get(localVarDesc); - String orgSourceLine = sourceVec.get(varLineNum); - int idx = - orgSourceLine.indexOf(generateVarDeclaration((VarDescriptor) localVarDesc)); - assert (idx != -1); - String annoatedStr = - orgSourceLine.substring(0, idx) + locAnnotationStr + " " - + orgSourceLine.substring(idx); - sourceVec.set(varLineNum, annoatedStr); - } - } else { - String methodDefStr = sourceVec.get(methodDefLine); + System.out.println(""); + LinkedList methodDescList = + (LinkedList) toanalyze_methodDescList.clone(); - int idx = - getParamLocation(methodDefStr, - generateVarDeclaration((VarDescriptor) localVarDesc)); + System.out.println("@@@methodDescList=" + methodDescList); + // System.exit(0); - assert (idx != -1); + while (!methodDescList.isEmpty()) { + MethodDescriptor md = methodDescList.removeLast(); + if (state.SSJAVADEBUG) { + System.out.println(); + System.out.println("SSJAVA: Constructing a global flow graph: " + md); - String annoatedStr = - methodDefStr.substring(0, idx) + locAnnotationStr + " " - + methodDefStr.substring(idx); - sourceVec.set(methodDefLine, annoatedStr); - } + FlowGraph flowGraph = getFlowGraph(md); + FlowGraph subGlobalFlowGraph = flowGraph.clone(); - } + // mapMethodDescriptorToSubGlobalFlowGraph.put(md, subGlobalFlowGraph); - String methodLatticeDefStr = generateLatticeDefinition(md); - String annoatedStr = methodLatticeDefStr + newline + sourceVec.get(methodDefLine); - sourceVec.set(methodDefLine, annoatedStr); + // addValueFlowsFromCalleeSubGlobalFlowGraph(md, subGlobalFlowGraph); - } + // try { + // subGlobalFlowGraph.writeGraph("_SUBGLOBAL"); + // } catch (IOException e) { + // e.printStackTrace(); + // } + // FlowGraph fg = new FlowGraph(md, mapParamDescToIdx); + // mapMethodDescriptorToFlowGraph.put(md, fg); + // analyzeMethodBody(md.getClassDesc(), md); } } - codeGen(); + // DEBUG: write a global flow graph + MethodDescriptor mdContainingSSJavaLoop = ssjava.getMethodContainingSSJavaLoop(); + // FlowGraph globalFlowGraph = getSubGlobalFlowGraph(mdContainingSSJavaLoop); + // System.out.println("GLOBAL NODE SET=" + globalFlowGraph.getNodeSet()); + // assignCompositeLocation(globalFlowGraph); + // try { + // globalFlowGraph.writeGraph("_GLOBAL"); + // } catch (IOException e) { + // e.printStackTrace(); + // } + // _debug_printGraph(); + + } + + private void calculateGlobalValueFlowCompositeLocation() { + + System.out.println("SSJAVA: Calculate composite locations in the global value flow graph"); + MethodDescriptor methodDescEventLoop = ssjava.getMethodContainingSSJavaLoop(); + GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(methodDescEventLoop); + + Set> prefixSet = new HashSet>(); + + Set nodeSet = globalFlowGraph.getNodeSet(); + + next: for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + GlobalFlowNode node = (GlobalFlowNode) iterator.next(); + Set incomingNodeSet = globalFlowGraph.getIncomingNodeSet(node); + List> prefixList = calculatePrefixList(globalFlowGraph, node); + Set reachNodeSet = globalFlowGraph.getReachableNodeSetFrom(node); + + // System.out.println("node=" + node + " inNodeSet=" + incomingNodeSet + // + " reachableNodeSet=" + reachNodeSet); + + for (int i = 0; i < prefixList.size(); i++) { + NTuple curPrefix = prefixList.get(i); + Set> reachableCommonPrefixSet = new HashSet>(); + + for (Iterator iterator2 = reachNodeSet.iterator(); iterator2.hasNext();) { + GlobalFlowNode reachNode = (GlobalFlowNode) iterator2.next(); + if (reachNode.getLocTuple().startsWith(curPrefix)) { + reachableCommonPrefixSet.add(reachNode.getLocTuple()); + } + } + + if (!reachableCommonPrefixSet.isEmpty()) { + CompositeLocation newCompLoc = generateCompositeLocation(curPrefix); + System.out.println("NEED TO ASSIGN COMP LOC TO " + node + " with prefix=" + curPrefix); + System.out.println("- newCompLoc=" + newCompLoc); + + Location targetLocalLoc = node.getLocTuple().get(0); + globalFlowGraph.addMapLocationToInferCompositeLocation(targetLocalLoc, newCompLoc); + + continue next; + } + + } + + } + // Set inNodeSet = graph.getIncomingNodeSetWithPrefix(prefix); + // System.out.println("inNodeSet=" + inNodeSet + " from=" + node); + } + + private void assignCompositeLocation(CompositeLocation compLocPrefix, GlobalFlowNode node) { + CompositeLocation newCompLoc = compLocPrefix.clone(); + NTuple locTuple = node.getLocTuple(); + for (int i = 1; i < locTuple.size(); i++) { + newCompLoc.addLocation(locTuple.get(i)); + } + node.setInferCompositeLocation(newCompLoc); + } + + private List> calculatePrefixList(GlobalFlowGraph graph, GlobalFlowNode node) { + + System.out.println("\n##### calculatePrefixList=" + node); + + Set incomingNodeSet = graph.getIncomingNodeSet(node); + + List> prefixList = new ArrayList>(); + + for (Iterator iterator = incomingNodeSet.iterator(); iterator.hasNext();) { + GlobalFlowNode inNode = (GlobalFlowNode) iterator.next(); + NTuple inNodeTuple = inNode.getLocTuple(); + + for (int i = 1; i < inNodeTuple.size(); i++) { + NTuple prefix = inNodeTuple.subList(0, i); + if (!prefixList.contains(prefix)) { + prefixList.add(prefix); + } + } + } + + 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; + } + } + }); + return prefixList; + } + + private GlobalFlowGraph constructSubGlobalFlowGraph(FlowGraph flowGraph) { + + MethodDescriptor md = flowGraph.getMethodDescriptor(); + + GlobalFlowGraph globalGraph = new GlobalFlowGraph(md); + + // Set nodeSet = flowGraph.getNodeSet(); + Set edgeSet = flowGraph.getEdgeSet(); + + for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) { + + FlowEdge edge = (FlowEdge) iterator.next(); + NTuple srcDescTuple = edge.getInitTuple(); + NTuple dstDescTuple = edge.getEndTuple(); + + // here only keep the first element(method location) of the descriptor tuple + NTuple srcLocTuple = translateToLocTuple(md, srcDescTuple); + // Location srcMethodLoc = srcLocTuple.get(0); + // Descriptor srcVarDesc = srcMethodLoc.getLocDescriptor(); + // // if (flowGraph.isParamDesc(srcVarDesc) && (!srcVarDesc.equals(md.getThis()))) { + // if (!srcVarDesc.equals(md.getThis())) { + // srcLocTuple = new NTuple(); + // Location loc = new Location(md, srcVarDesc); + // srcLocTuple.add(loc); + // } + // + NTuple dstLocTuple = translateToLocTuple(md, dstDescTuple); + // Location dstMethodLoc = dstLocTuple.get(0); + // Descriptor dstVarDesc = dstMethodLoc.getLocDescriptor(); + // if (!dstVarDesc.equals(md.getThis())) { + // dstLocTuple = new NTuple(); + // Location loc = new Location(md, dstVarDesc); + // dstLocTuple.add(loc); + // } + + globalGraph.addValueFlowEdge(srcLocTuple, dstLocTuple); + + } + + return globalGraph; + } + + private NTuple translateToLocTuple(MethodDescriptor md, NTuple descTuple) { + + NTuple locTuple = new NTuple(); + + Descriptor enclosingDesc = md; + System.out.println("md=" + md + " descTuple=" + descTuple); + for (int i = 0; i < descTuple.size(); i++) { + Descriptor desc = descTuple.get(i); + + Location loc = new Location(enclosingDesc, desc); + locTuple.add(loc); + + if (desc instanceof VarDescriptor) { + enclosingDesc = ((VarDescriptor) desc).getType().getClassDesc(); + } else if (desc instanceof FieldDescriptor) { + enclosingDesc = ((FieldDescriptor) desc).getType().getClassDesc(); + } else { + // TODO: inter descriptor case + enclosingDesc = desc; + } + + } + + return locTuple; + + } + + private void addValueFlowsFromCalleeSubGlobalFlowGraph(MethodDescriptor mdCaller, + GlobalFlowGraph subGlobalFlowGraph) { + + // the transformation for a call site propagates flows through parameters + // if the method is virtual, it also grab all relations from any possible + // callees + + Set setMethodInvokeNode = getMethodInvokeNodeSet(mdCaller); + + 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(); + propagateValueFlowsToCallerFromSubGlobalFlowGraph(min, mdCaller, possibleMdCallee); + } + + } + + } + + private void propagateValueFlowsToCallerFromSubGlobalFlowGraph(MethodInvokeNode min, + MethodDescriptor mdCaller, MethodDescriptor possibleMdCallee) { + + FlowGraph calleeFlowGraph = getFlowGraph(possibleMdCallee); + Map> mapIdxToArg = mapMethodInvokeNodeToArgIdxMap.get(min); + + Set keySet = mapIdxToArg.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Integer idx = (Integer) iterator.next(); + NTuple argDescTuple = mapIdxToArg.get(idx); + NTuple argLocTuple = translateToLocTuple(mdCaller, argDescTuple); + + NTuple paramDescTuple = calleeFlowGraph.getParamFlowNode(idx).getDescTuple(); + NTuple paramLocTuple = translateToLocTuple(possibleMdCallee, paramDescTuple); + addMapCallerArgToCalleeParam(min, argDescTuple, paramDescTuple); + } + + NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); + GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(possibleMdCallee); + Set calleeNodeSet = calleeSubGlobalGraph.getNodeSet(); + for (Iterator iterator = calleeNodeSet.iterator(); iterator.hasNext();) { + GlobalFlowNode calleeNode = (GlobalFlowNode) iterator.next(); + addValueFlowFromCalleeNode(min, mdCaller, possibleMdCallee, calleeNode); + } + + // int numParam = calleeFlowGraph.getNumParameters(); + // for (int idx = 0; idx < numParam; idx++) { + // + // FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx); + // + // NTuple paramLocTuple = + // translateToLocTuple(possibleMdCallee, paramNode.getCurrentDescTuple()); + // + // GlobalFlowNode globalParamNode = calleeSubGlobalGraph.getFlowNode(paramLocTuple); + // + // NTuple argTuple = mapMethodInvokeNodeToArgIdxMap.get(min).get(idx); + // + // NTuple argLocTuple = translateToLocTuple(mdCaller, argTuple); + // + // System.out.println("argTupleSet=" + argLocTuple + " param=" + paramLocTuple); + // // here, it adds all value flows reachable from the paramNode in the callee's flow graph + // + // addValueFlowsFromCalleeParam(mdCaller, argLocTuple, baseLocTuple, possibleMdCallee, + // globalParamNode); + // } + // + // // TODO + // // FlowGraph callerSubGlobalGraph = getSubGlobalFlowGraph(mdCaller); + // // FlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(possibleMdCallee); + // // + // // int numParam = calleeSubGlobalGraph.getNumParameters(); + // // for (int idx = 0; idx < numParam; idx++) { + // // FlowNode paramNode = calleeSubGlobalGraph.getParamFlowNode(idx); + // // NTuple argTuple = mapMethodInvokeNodeToArgIdxMap.get(min).get(idx); + // // System.out.println("argTupleSet=" + argTuple + " param=" + paramNode); + // // // here, it adds all value flows reachable from the paramNode in the callee's flow graph + // // addValueFlowsFromCalleeParam(min, calleeSubGlobalGraph, paramNode, callerSubGlobalGraph, + // // argTuple, baseTuple); + // // } + + } + + private void addValueFlowFromCalleeNode(MethodInvokeNode min, MethodDescriptor mdCaller, + MethodDescriptor mdCallee, GlobalFlowNode calleeSrcNode) { + + GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(mdCallee); + GlobalFlowGraph callerSubGlobalGraph = getSubGlobalFlowGraph(mdCaller); + + NTuple srcNodeLocTuple = + translateToCallerLocTuple(min, mdCallee, mdCaller, calleeSrcNode.getLocTuple()); + + Set outNodeSet = calleeSubGlobalGraph.getOutNodeSet(calleeSrcNode); + + for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) { + GlobalFlowNode outNode = (GlobalFlowNode) iterator.next(); + NTuple dstNodeLocTuple = + translateToCallerLocTuple(min, mdCallee, mdCaller, outNode.getLocTuple()); + callerSubGlobalGraph.addValueFlowEdge(srcNodeLocTuple, dstNodeLocTuple); + } + + } + + private NTuple translateToCallerLocTuple(MethodInvokeNode min, + MethodDescriptor mdCallee, MethodDescriptor mdCaller, NTuple nodeLocTuple) { + + FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); + + NTuple nodeDescTuple = translateToDescTuple(nodeLocTuple); + + if (calleeFlowGraph.isParameter(nodeDescTuple)) { + int paramIdx = calleeFlowGraph.getParamIdx(nodeDescTuple); + NTuple argDescTuple = mapMethodInvokeNodeToArgIdxMap.get(min).get(paramIdx); + NTuple argLocTuple = translateToLocTuple(mdCaller, argDescTuple); + + NTuple callerLocTuple = new NTuple(); + + callerLocTuple.addAll(argLocTuple); + for (int i = 1; i < nodeLocTuple.size(); i++) { + callerLocTuple.add(nodeLocTuple.get(i)); + } + return callerLocTuple; + } else { + return nodeLocTuple; + } + + } + + private NTuple translateToDescTuple(NTuple locTuple) { + + NTuple descTuple = new NTuple(); + for (int i = 0; i < locTuple.size(); i++) { + descTuple.add(locTuple.get(i).getLocDescriptor()); + } + return descTuple; + + } + + private void addValueFlowsFromCalleeParam(MethodDescriptor mdCaller, + NTuple argLocTuple, NTuple baseLocTuple, MethodDescriptor mdCallee, + GlobalFlowNode globalParamNode) { + + Set visited = new HashSet(); + visited.add(globalParamNode); + recurAddValueFlowsFromCalleeParam(mdCaller, argLocTuple, baseLocTuple, mdCallee, + globalParamNode); + + } + + private void recurAddValueFlowsFromCalleeParam(MethodDescriptor mdCaller, + NTuple argLocTuple, NTuple baseLocTuple, MethodDescriptor mdCallee, + GlobalFlowNode calleeCurNode) { + + // FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); + // GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(mdCallee); + // + // NTuple curNodeLocTuple = calleeCurNode.getLocTuple(); + // NTuple curNodeDescTuple = calleeCurNode.getDescTuple(); + // if (calleeFlowGraph.isParameter(curNodeDescTuple)) { + // curNodeLocTuple = translateToCaller(argLocTuple, curNodeLocTuple); + // } + // + // Set outNodeSet = calleeSubGlobalGraph.getOutNodeSet(calleeCurNode); + // for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) { + // GlobalFlowNode outNode = (GlobalFlowNode) iterator.next(); + // + // NTuple curNodeLocTuple = calleeCurNode.getLocTuple(); + // NTuple curNodeDescTuple = calleeCurNode.getDescTuple(); + // if (calleeFlowGraph.isParameter(curNodeDescTuple)) { + // curNodeLocTuple = translateToCaller(argLocTuple, curNodeLocTuple); + // } + // + // outNode.getDescTuple(); + // + // if (calleeFlowGraph.is) + // + // if (calleeSubGlobalGraph.isParameter(srcDescTuple)) { + // // destination node is started with 'parameter' + // // need to translate it in terms of the caller's a node + // srcDescTuple = + // translateToCaller(min, calleeSubGlobalGraph.getParamIdx(srcDescTuple), srcDescTuple); + // } + // + // } + // + // Set edgeSet = calleeSubGlobalGraph.getOutEdgeSetStartingFrom(calleeSrcNode); + // for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) { + // FlowEdge flowEdge = (FlowEdge) iterator.next(); + // + // NTuple srcDescTuple = flowEdge.getInitTuple(); + // NTuple dstDescTuple = flowEdge.getEndTuple(); + // + // FlowNode dstNode = calleeSubGlobalGraph.getFlowNode(dstDescTuple); + // + // if (calleeSubGlobalGraph.isParameter(srcDescTuple)) { + // // destination node is started with 'parameter' + // // need to translate it in terms of the caller's a node + // srcDescTuple = + // translateToCaller(min, calleeSubGlobalGraph.getParamIdx(srcDescTuple), srcDescTuple); + // } + // + // if (calleeSubGlobalGraph.isParameter(dstDescTuple)) { + // // destination node is started with 'parameter' + // // need to translate it in terms of the caller's a node + // dstDescTuple = + // translateToCaller(min, calleeSubGlobalGraph.getParamIdx(dstDescTuple), dstDescTuple); + // } + // + // callerSubGlobalGraph.addValueFlowEdge(srcDescTuple, dstDescTuple); + // + // if (!visited.contains(dstNode)) { + // visited.add(dstNode); + // recurAddValueFlowsFromCalleeParam(min, calleeSubGlobalGraph, dstNode, callerSubGlobalGraph, + // dstDescTuple, visited, baseTuple); + // } + // + // } + + } + + private NTuple translateToCaller(NTuple argLocTuple, + NTuple curNodeLocTuple) { + + NTuple callerLocTuple = new NTuple(); + + callerLocTuple.addAll(argLocTuple); + for (int i = 1; i < curNodeLocTuple.size(); i++) { + callerLocTuple.add(curNodeLocTuple.get(i)); + } + + return callerLocTuple; + } + + private void recurAddValueFlowsFromCalleeParam(MethodInvokeNode min, + FlowGraph calleeSubGlobalGraph, FlowNode calleeSrcNode, FlowGraph callerSubGlobalGraph, + NTuple callerSrcTuple, Set visited, NTuple baseTuple) { + + MethodDescriptor mdCallee = calleeSubGlobalGraph.getMethodDescriptor(); + + // Set edgeSet = calleeSubGlobalGraph.getOutEdgeSet(calleeSrcNode); + Set edgeSet = calleeSubGlobalGraph.getOutEdgeSetStartingFrom(calleeSrcNode); + for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) { + FlowEdge flowEdge = (FlowEdge) iterator.next(); + + NTuple srcDescTuple = flowEdge.getInitTuple(); + NTuple dstDescTuple = flowEdge.getEndTuple(); + + FlowNode dstNode = calleeSubGlobalGraph.getFlowNode(dstDescTuple); + + if (calleeSubGlobalGraph.isParameter(srcDescTuple)) { + // destination node is started with 'parameter' + // need to translate it in terms of the caller's a node + srcDescTuple = + translateToCaller(min, calleeSubGlobalGraph.getParamIdx(srcDescTuple), srcDescTuple); + } + + if (calleeSubGlobalGraph.isParameter(dstDescTuple)) { + // destination node is started with 'parameter' + // need to translate it in terms of the caller's a node + dstDescTuple = + translateToCaller(min, calleeSubGlobalGraph.getParamIdx(dstDescTuple), dstDescTuple); + } + + callerSubGlobalGraph.addValueFlowEdge(srcDescTuple, dstDescTuple); + + if (!visited.contains(dstNode)) { + visited.add(dstNode); + recurAddValueFlowsFromCalleeParam(min, calleeSubGlobalGraph, dstNode, callerSubGlobalGraph, + dstDescTuple, visited, baseTuple); + } + + } + + } + + private NTuple translateToCaller(MethodInvokeNode min, int paramIdx, + NTuple srcDescTuple) { + + NTuple callerTuple = new NTuple(); + + NTuple argTuple = mapMethodInvokeNodeToArgIdxMap.get(min).get(paramIdx); + + for (int i = 0; i < argTuple.size(); i++) { + callerTuple.add(argTuple.get(i)); + } + + for (int i = 1; i < srcDescTuple.size(); i++) { + callerTuple.add(srcDescTuple.get(i)); + } + + return callerTuple; + } + + private NTuple traslateToCalleeParamTupleToCallerArgTuple( + NTuple calleeInitTuple, NTuple callerSrcTuple) { + + NTuple callerInitTuple = new NTuple(); + + for (int i = 0; i < callerSrcTuple.size(); i++) { + callerInitTuple.add(callerSrcTuple.get(i)); + } + + for (int i = 1; i < calleeInitTuple.size(); i++) { + callerInitTuple.add(calleeInitTuple.get(i)); + } + + return callerInitTuple; + } + + public LocationSummary getLocationSummary(Descriptor d) { + if (!mapDescToLocationSummary.containsKey(d)) { + if (d instanceof MethodDescriptor) { + mapDescToLocationSummary.put(d, new MethodSummary((MethodDescriptor) d)); + } else if (d instanceof ClassDescriptor) { + mapDescToLocationSummary.put(d, new FieldSummary()); + } + } + return mapDescToLocationSummary.get(d); + } + + private void generateMethodSummary() { + + Set keySet = md2lattice.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + MethodDescriptor md = (MethodDescriptor) iterator.next(); + + System.out.println("\nSSJAVA: generate method summary: " + md); + + FlowGraph flowGraph = getFlowGraph(md); + MethodSummary methodSummary = getMethodSummary(md); + + // construct a parameter mapping that maps a parameter descriptor to an inferred composite + // location + + for (int paramIdx = 0; paramIdx < flowGraph.getNumParameters(); paramIdx++) { + FlowNode flowNode = flowGraph.getParamFlowNode(paramIdx); + NTuple descTuple = flowNode.getDescTuple(); + + CompositeLocation assignedCompLoc = flowNode.getCompositeLocation(); + CompositeLocation inferredCompLoc; + if (assignedCompLoc != null) { + inferredCompLoc = translateCompositeLocation(assignedCompLoc); + } else { + Descriptor locDesc = descTuple.get(0); + Location loc = new Location(md, locDesc.getSymbol()); + loc.setLocDescriptor(locDesc); + inferredCompLoc = new CompositeLocation(loc); + } + System.out.println("-paramIdx=" + paramIdx + " infer=" + inferredCompLoc); + methodSummary.addMapParamIdxToInferLoc(paramIdx, inferredCompLoc); + } + + } + + } + + private CompositeLocation translateCompositeLocation(CompositeLocation compLoc) { + CompositeLocation newCompLoc = new CompositeLocation(); + + // System.out.println("compLoc=" + compLoc); + for (int i = 0; i < compLoc.getSize(); i++) { + Location loc = compLoc.get(i); + Descriptor enclosingDescriptor = loc.getDescriptor(); + Descriptor locDescriptor = loc.getLocDescriptor(); + + HNode hnode = getHierarchyGraph(enclosingDescriptor).getHNode(locDescriptor); + // System.out.println("-hnode=" + hnode + " from=" + locDescriptor + + // " enclosingDescriptor=" + // + enclosingDescriptor); + // System.out.println("-getLocationSummary(enclosingDescriptor)=" + // + getLocationSummary(enclosingDescriptor)); + String locName = getLocationSummary(enclosingDescriptor).getLocationName(hnode.getName()); + // System.out.println("-locName=" + locName); + Location newLoc = new Location(enclosingDescriptor, locName); + newLoc.setLocDescriptor(locDescriptor); + newCompLoc.addLocation(newLoc); + } + + return newCompLoc; + } + + private void debug_writeLattices() { + + Set keySet = mapDescriptorToSimpleLattice.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Descriptor key = (Descriptor) iterator.next(); + SSJavaLattice simpleLattice = mapDescriptorToSimpleLattice.get(key); + // HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(key); + HierarchyGraph scHierarchyGraph = getSkeletonCombinationHierarchyGraph(key); + if (key instanceof ClassDescriptor) { + writeInferredLatticeDotFile((ClassDescriptor) key, scHierarchyGraph, simpleLattice, + "_SIMPLE"); + } else if (key instanceof MethodDescriptor) { + MethodDescriptor md = (MethodDescriptor) key; + writeInferredLatticeDotFile(md.getClassDesc(), md, scHierarchyGraph, simpleLattice, + "_SIMPLE"); + } + + LocationSummary ls = getLocationSummary(key); + System.out.println("####LOC SUMMARY=" + key + "\n" + ls.getMapHNodeNameToLocationName()); + } + + Set cdKeySet = cd2lattice.keySet(); + for (Iterator iterator = cdKeySet.iterator(); iterator.hasNext();) { + ClassDescriptor cd = (ClassDescriptor) iterator.next(); + writeInferredLatticeDotFile((ClassDescriptor) cd, getSkeletonCombinationHierarchyGraph(cd), + cd2lattice.get(cd), ""); + } + + Set mdKeySet = md2lattice.keySet(); + for (Iterator iterator = mdKeySet.iterator(); iterator.hasNext();) { + MethodDescriptor md = (MethodDescriptor) iterator.next(); + writeInferredLatticeDotFile(md.getClassDesc(), md, getSkeletonCombinationHierarchyGraph(md), + md2lattice.get(md), ""); + } + + } + + private void buildLattice() { + + BuildLattice buildLattice = new BuildLattice(this); + + Set keySet = mapDescriptorToCombineSkeletonHierarchyGraph.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Descriptor desc = (Descriptor) iterator.next(); + + SSJavaLattice simpleLattice = buildLattice.buildLattice(desc); + + addMapDescToSimpleLattice(desc, simpleLattice); + + HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc); + System.out.println("## insertIntermediateNodesToStraightLine:" + + simpleHierarchyGraph.getName()); + SSJavaLattice lattice = + buildLattice.insertIntermediateNodesToStraightLine(desc, simpleLattice); + lattice.removeRedundantEdges(); + + if (desc instanceof ClassDescriptor) { + // field lattice + cd2lattice.put((ClassDescriptor) desc, lattice); + // ssjava.writeLatticeDotFile((ClassDescriptor) desc, null, lattice); + } else if (desc instanceof MethodDescriptor) { + // method lattice + md2lattice.put((MethodDescriptor) desc, lattice); + MethodDescriptor md = (MethodDescriptor) desc; + ClassDescriptor cd = md.getClassDesc(); + // ssjava.writeLatticeDotFile(cd, md, lattice); + } + + // System.out.println("\nSSJAVA: Insering Combination Nodes:" + desc); + // HierarchyGraph skeletonGraph = getSkeletonHierarchyGraph(desc); + // HierarchyGraph skeletonGraphWithCombinationNode = skeletonGraph.clone(); + // skeletonGraphWithCombinationNode.setName(desc + "_SC"); + // + // HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc); + // System.out.println("Identifying Combination Nodes:"); + // skeletonGraphWithCombinationNode.insertCombinationNodesToGraph(simpleHierarchyGraph); + // skeletonGraphWithCombinationNode.simplifySkeletonCombinationHierarchyGraph(); + // mapDescriptorToCombineSkeletonHierarchyGraph.put(desc, skeletonGraphWithCombinationNode); + } + + } + + public void addMapDescToSimpleLattice(Descriptor desc, SSJavaLattice lattice) { + mapDescriptorToSimpleLattice.put(desc, lattice); + } + + public SSJavaLattice getSimpleLattice(Descriptor desc) { + return mapDescriptorToSimpleLattice.get(desc); + } + + private void simplifyHierarchyGraph() { + Set keySet = mapDescriptorToHierarchyGraph.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Descriptor desc = (Descriptor) iterator.next(); + HierarchyGraph simpleHierarchyGraph = getHierarchyGraph(desc).clone(); + simpleHierarchyGraph.setName(desc + "_SIMPLE"); + simpleHierarchyGraph.removeRedundantEdges(); + // simpleHierarchyGraph.simplifyHierarchyGraph(); + mapDescriptorToSimpleHierarchyGraph.put(desc, simpleHierarchyGraph); + } + } + + private void insertCombinationNodes() { + Set keySet = mapDescriptorToSkeletonHierarchyGraph.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Descriptor desc = (Descriptor) iterator.next(); + System.out.println("\nSSJAVA: Insering Combination Nodes:" + desc); + HierarchyGraph skeletonGraph = getSkeletonHierarchyGraph(desc); + HierarchyGraph skeletonGraphWithCombinationNode = skeletonGraph.clone(); + skeletonGraphWithCombinationNode.setName(desc + "_SC"); + + HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc); + System.out.println("Identifying Combination Nodes:"); + skeletonGraphWithCombinationNode.insertCombinationNodesToGraph(simpleHierarchyGraph); + skeletonGraphWithCombinationNode.simplifySkeletonCombinationHierarchyGraph(); + mapDescriptorToCombineSkeletonHierarchyGraph.put(desc, skeletonGraphWithCombinationNode); + } + } + + private void constructSkeletonHierarchyGraph() { + Set keySet = mapDescriptorToHierarchyGraph.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Descriptor desc = (Descriptor) iterator.next(); + HierarchyGraph simpleGraph = getSimpleHierarchyGraph(desc); + HierarchyGraph skeletonGraph = simpleGraph.generateSkeletonGraph(); + skeletonGraph.setMapDescToHNode(simpleGraph.getMapDescToHNode()); + skeletonGraph.setMapHNodeToDescSet(simpleGraph.getMapHNodeToDescSet()); + skeletonGraph.simplifyHierarchyGraph(); + // skeletonGraph.combineRedundantNodes(false); + // skeletonGraph.removeRedundantEdges(); + mapDescriptorToSkeletonHierarchyGraph.put(desc, skeletonGraph); + } + } + + private void debug_writeHierarchyDotFiles() { + + Set keySet = mapDescriptorToHierarchyGraph.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Descriptor desc = (Descriptor) iterator.next(); + getHierarchyGraph(desc).writeGraph(); + } + + } + + private void debug_writeSimpleHierarchyDotFiles() { + + Set keySet = mapDescriptorToHierarchyGraph.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Descriptor desc = (Descriptor) iterator.next(); + getHierarchyGraph(desc).writeGraph(); + getSimpleHierarchyGraph(desc).writeGraph(); + } + + } + + private void debug_writeSkeletonHierarchyDotFiles() { + + Set keySet = mapDescriptorToHierarchyGraph.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Descriptor desc = (Descriptor) iterator.next(); + getSkeletonHierarchyGraph(desc).writeGraph(); + } + + } + + private void debug_writeSkeletonCombinationHierarchyDotFiles() { + + Set keySet = mapDescriptorToHierarchyGraph.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + Descriptor desc = (Descriptor) iterator.next(); + getSkeletonCombinationHierarchyGraph(desc).writeGraph(); + } + + } + + public HierarchyGraph getSimpleHierarchyGraph(Descriptor d) { + return mapDescriptorToSimpleHierarchyGraph.get(d); + } + + private HierarchyGraph getSkeletonHierarchyGraph(Descriptor d) { + if (!mapDescriptorToSkeletonHierarchyGraph.containsKey(d)) { + mapDescriptorToSkeletonHierarchyGraph.put(d, new HierarchyGraph(d)); + } + return mapDescriptorToSkeletonHierarchyGraph.get(d); + } + + public HierarchyGraph getSkeletonCombinationHierarchyGraph(Descriptor d) { + if (!mapDescriptorToCombineSkeletonHierarchyGraph.containsKey(d)) { + mapDescriptorToCombineSkeletonHierarchyGraph.put(d, new HierarchyGraph(d)); + } + return mapDescriptorToCombineSkeletonHierarchyGraph.get(d); + } + + private void constructHierarchyGraph() { + + // do fixed-point analysis + + ssjava.init(); + 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(); + + Set methodDescriptorToVistSet = new HashSet(); + methodDescriptorToVistSet.addAll(descriptorListToAnalyze); + + while (!descriptorListToAnalyze.isEmpty()) { + MethodDescriptor md = descriptorListToAnalyze.removeFirst(); + methodDescriptorsToVisitStack.add(md); + } + + // analyze scheduled methods until there are no more to visit + while (!methodDescriptorsToVisitStack.isEmpty()) { + // start to analyze leaf node + MethodDescriptor md = methodDescriptorsToVisitStack.pop(); + + HierarchyGraph hierarchyGraph = new HierarchyGraph(md); + // MethodSummary methodSummary = new MethodSummary(md); + + // MethodLocationInfo methodInfo = new MethodLocationInfo(md); + // curMethodInfo = methodInfo; + + System.out.println(); + System.out.println("SSJAVA: Construcing the hierarchy graph from " + md); + + constructHierarchyGraph(md, hierarchyGraph); + + HierarchyGraph prevHierarchyGraph = getHierarchyGraph(md); + // MethodSummary prevMethodSummary = getMethodSummary(md); + + if (!hierarchyGraph.equals(prevHierarchyGraph)) { + + mapDescriptorToHierarchyGraph.put(md, hierarchyGraph); + // mapDescToLocationSummary.put(md, methodSummary); + + // results for callee changed, so enqueue dependents caller for + // further analysis + Iterator depsItr = ssjava.getDependents(md).iterator(); + while (depsItr.hasNext()) { + MethodDescriptor methodNext = depsItr.next(); + if (!methodDescriptorsToVisitStack.contains(methodNext) + && methodDescriptorToVistSet.contains(methodNext)) { + methodDescriptorsToVisitStack.add(methodNext); + } + } + + } + + } + + } + + private HierarchyGraph getHierarchyGraph(Descriptor d) { + if (!mapDescriptorToHierarchyGraph.containsKey(d)) { + mapDescriptorToHierarchyGraph.put(d, new HierarchyGraph(d)); + } + return mapDescriptorToHierarchyGraph.get(d); + } + + private void constructHierarchyGraph(MethodDescriptor md, HierarchyGraph methodGraph) { + + // visit each node of method flow graph + FlowGraph fg = getFlowGraph(md); + Set nodeSet = fg.getNodeSet(); + + Set paramDescSet = fg.getMapParamDescToIdx().keySet(); + for (Iterator iterator = paramDescSet.iterator(); iterator.hasNext();) { + Descriptor desc = (Descriptor) iterator.next(); + methodGraph.getHNode(desc).setSkeleton(true); + } + + // 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(); + + Set outEdgeSet = fg.getOutEdgeSet(srcNode); + for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) { + FlowEdge outEdge = (FlowEdge) iterator2.next(); + FlowNode dstNode = outEdge.getDst(); + + NTuple srcNodeTuple = srcNode.getDescTuple(); + NTuple dstNodeTuple = dstNode.getDescTuple(); + + if (outEdge.getInitTuple().equals(srcNodeTuple) + && outEdge.getEndTuple().equals(dstNodeTuple)) { + + NTuple srcCurTuple = srcNode.getCurrentDescTuple(); + NTuple dstCurTuple = dstNode.getCurrentDescTuple(); + + if ((srcCurTuple.size() > 1 && dstCurTuple.size() > 1) + && srcCurTuple.get(0).equals(dstCurTuple.get(0))) { + + // value flows between fields + Descriptor desc = srcCurTuple.get(0); + ClassDescriptor classDesc; + + if (desc.equals(GLOBALDESC)) { + classDesc = md.getClassDesc(); + } else { + VarDescriptor varDesc = (VarDescriptor) srcCurTuple.get(0); + classDesc = varDesc.getType().getClassDesc(); + } + extractFlowsBetweenFields(classDesc, srcNode, dstNode, 1); + + } else { + // value flow between local var - local var or local var - field + + Descriptor srcDesc = srcCurTuple.get(0); + Descriptor dstDesc = dstCurTuple.get(0); + + methodGraph.addEdge(srcDesc, dstDesc); + + if (fg.isParamDesc(srcDesc)) { + methodGraph.setParamHNode(srcDesc); + } + if (fg.isParamDesc(dstDesc)) { + methodGraph.setParamHNode(dstDesc); + } + + } + + } + } + } + + } + + private MethodSummary getMethodSummary(MethodDescriptor md) { + if (!mapDescToLocationSummary.containsKey(md)) { + mapDescToLocationSummary.put(md, new MethodSummary(md)); + } + return (MethodSummary) mapDescToLocationSummary.get(md); + } + + private void addMapClassDefinitionToLineNum(ClassDescriptor cd, String strLine, int lineNum) { + + String classSymbol = cd.getSymbol(); + int idx = classSymbol.lastIndexOf("$"); + if (idx != -1) { + classSymbol = classSymbol.substring(idx + 1); + } + + String pattern = "class " + classSymbol + " "; + if (strLine.indexOf(pattern) != -1) { + mapDescToDefinitionLine.put(cd, lineNum); + } + } + + private void addMapMethodDefinitionToLineNum(Set methodSet, String strLine, + int lineNum) { + for (Iterator iterator = methodSet.iterator(); iterator.hasNext();) { + MethodDescriptor md = (MethodDescriptor) iterator.next(); + String pattern = md.getMethodDeclaration(); + if (strLine.indexOf(pattern) != -1) { + mapDescToDefinitionLine.put(md, lineNum); + methodSet.remove(md); + return; + } + } + + } + + private void readOriginalSourceFiles() { + + SymbolTable classtable = state.getClassSymbolTable(); + + Set classDescSet = new HashSet(); + classDescSet.addAll(classtable.getValueSet()); + + try { + // inefficient implement. it may re-visit the same file if the file + // contains more than one class definitions. + for (Iterator iterator = classDescSet.iterator(); iterator.hasNext();) { + ClassDescriptor cd = (ClassDescriptor) iterator.next(); + + Set methodSet = new HashSet(); + methodSet.addAll(cd.getMethodTable().getValueSet()); + + String sourceFileName = cd.getSourceFileName(); + Vector lineVec = new Vector(); + + mapFileNameToLineVector.put(sourceFileName, lineVec); + + BufferedReader in = new BufferedReader(new FileReader(sourceFileName)); + String strLine; + int lineNum = 1; + lineVec.add(""); // the index is started from 1. + while ((strLine = in.readLine()) != null) { + lineVec.add(lineNum, strLine); + addMapClassDefinitionToLineNum(cd, strLine, lineNum); + addMapMethodDefinitionToLineNum(methodSet, strLine, lineNum); + lineNum++; + } + + } + + } catch (IOException e) { + e.printStackTrace(); + } + + } + + private String generateLatticeDefinition(Descriptor desc) { + + Set sharedLocSet = new HashSet(); + + SSJavaLattice lattice = getLattice(desc); + String rtr = "@LATTICE(\""; + + Map> map = lattice.getTable(); + Set keySet = map.keySet(); + boolean first = true; + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + String key = (String) iterator.next(); + if (!key.equals(lattice.getTopItem())) { + Set connectedSet = map.get(key); + + if (connectedSet.size() == 1) { + if (connectedSet.iterator().next().equals(lattice.getBottomItem())) { + if (!first) { + rtr += ","; + } else { + rtr += "LOC,"; + first = false; + } + rtr += key; + if (lattice.isSharedLoc(key)) { + rtr += "," + key + "*"; + } + } + } + + for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) { + String loc = (String) iterator2.next(); + if (!loc.equals(lattice.getBottomItem())) { + if (!first) { + rtr += ","; + } else { + rtr += "LOC,"; + first = false; + } + rtr += loc + "<" + key; + if (lattice.isSharedLoc(key) && (!sharedLocSet.contains(key))) { + rtr += "," + key + "*"; + sharedLocSet.add(key); + } + if (lattice.isSharedLoc(loc) && (!sharedLocSet.contains(loc))) { + rtr += "," + loc + "*"; + sharedLocSet.add(loc); + } + + } + } + } + } + + rtr += "\")"; + + if (desc instanceof MethodDescriptor) { + TypeDescriptor returnType = ((MethodDescriptor) desc).getReturnType(); + + MethodLocationInfo methodLocInfo = getMethodLocationInfo((MethodDescriptor) desc); + + if (returnType != null && (!returnType.isVoid())) { + rtr += + "\n@RETURNLOC(\"" + generateLocationAnnoatation(methodLocInfo.getReturnLoc()) + "\")"; + } + + rtr += "\n@THISLOC(\"this\")"; + rtr += "\n@GLOBALLOC(\"GLOBALLOC\")"; + + CompositeLocation pcLoc = methodLocInfo.getPCLoc(); + if ((pcLoc != null) && (!pcLoc.get(0).isTop())) { + rtr += "\n@PCLOC(\"" + generateLocationAnnoatation(pcLoc) + "\")"; + } + + } + + return rtr; + } + + private void generateAnnoatedCode() { + + readOriginalSourceFiles(); + + setupToAnalyze(); + while (!toAnalyzeIsEmpty()) { + ClassDescriptor cd = toAnalyzeNext(); + + setupToAnalazeMethod(cd); + + LocationInfo locInfo = mapClassToLocationInfo.get(cd); + String sourceFileName = cd.getSourceFileName(); + + if (cd.isInterface()) { + continue; + } + + int classDefLine = mapDescToDefinitionLine.get(cd); + Vector sourceVec = mapFileNameToLineVector.get(sourceFileName); + + if (locInfo == null) { + locInfo = getLocationInfo(cd); + } + + for (Iterator iter = cd.getFields(); iter.hasNext();) { + FieldDescriptor fieldDesc = (FieldDescriptor) iter.next(); + if (!(fieldDesc.isStatic() && fieldDesc.isFinal())) { + String locIdentifier = locInfo.getFieldInferLocation(fieldDesc).getLocIdentifier(); + if (!getLattice(cd).getElementSet().contains(locIdentifier)) { + getLattice(cd).put(locIdentifier); + } + } + } + + String fieldLatticeDefStr = generateLatticeDefinition(cd); + String annoatedSrc = fieldLatticeDefStr + newline + sourceVec.get(classDefLine); + sourceVec.set(classDefLine, annoatedSrc); + + // generate annotations for field declarations + LocationInfo fieldLocInfo = getLocationInfo(cd); + Map inferLocMap = fieldLocInfo.getMapDescToInferLocation(); + + for (Iterator iter = cd.getFields(); iter.hasNext();) { + FieldDescriptor fd = (FieldDescriptor) iter.next(); + + String locAnnotationStr; + CompositeLocation inferLoc = inferLocMap.get(fd); + + if (inferLoc != null) { + // infer loc is null if the corresponding field is static and final + locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")"; + int fdLineNum = fd.getLineNum(); + String orgFieldDeclarationStr = sourceVec.get(fdLineNum); + String fieldDeclaration = fd.toString(); + fieldDeclaration = fieldDeclaration.substring(0, fieldDeclaration.length() - 1); + String annoatedStr = locAnnotationStr + " " + orgFieldDeclarationStr; + sourceVec.set(fdLineNum, annoatedStr); + } + + } + + while (!toAnalyzeMethodIsEmpty()) { + MethodDescriptor md = toAnalyzeMethodNext(); + + if (!ssjava.needTobeAnnotated(md)) { + continue; + } + + SSJavaLattice methodLattice = md2lattice.get(md); + if (methodLattice != null) { + + int methodDefLine = md.getLineNum(); + + MethodLocationInfo methodLocInfo = getMethodLocationInfo(md); + + Map methodInferLocMap = + methodLocInfo.getMapDescToInferLocation(); + Set localVarDescSet = methodInferLocMap.keySet(); + + Set localLocElementSet = methodLattice.getElementSet(); + + for (Iterator iterator = localVarDescSet.iterator(); iterator.hasNext();) { + Descriptor localVarDesc = (Descriptor) iterator.next(); + CompositeLocation inferLoc = methodInferLocMap.get(localVarDesc); + + String localLocIdentifier = inferLoc.get(0).getLocIdentifier(); + if (!localLocElementSet.contains(localLocIdentifier)) { + methodLattice.put(localLocIdentifier); + } + + String locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")"; + + if (!isParameter(md, localVarDesc)) { + if (mapDescToDefinitionLine.containsKey(localVarDesc)) { + int varLineNum = mapDescToDefinitionLine.get(localVarDesc); + String orgSourceLine = sourceVec.get(varLineNum); + int idx = + orgSourceLine.indexOf(generateVarDeclaration((VarDescriptor) localVarDesc)); + assert (idx != -1); + String annoatedStr = + orgSourceLine.substring(0, idx) + locAnnotationStr + " " + + orgSourceLine.substring(idx); + sourceVec.set(varLineNum, annoatedStr); + } + } else { + String methodDefStr = sourceVec.get(methodDefLine); + + int idx = + getParamLocation(methodDefStr, + generateVarDeclaration((VarDescriptor) localVarDesc)); + + assert (idx != -1); + + String annoatedStr = + methodDefStr.substring(0, idx) + locAnnotationStr + " " + + methodDefStr.substring(idx); + sourceVec.set(methodDefLine, annoatedStr); + } + + } + + // check if the lattice has to have the location type for the this + // reference... + + // boolean needToAddthisRef = hasThisReference(md); + if (localLocElementSet.contains("this")) { + methodLattice.put("this"); + } + + String methodLatticeDefStr = generateLatticeDefinition(md); + String annoatedStr = methodLatticeDefStr + newline + sourceVec.get(methodDefLine); + sourceVec.set(methodDefLine, annoatedStr); + + } + } + + } + + codeGen(); + } + + private boolean hasThisReference(MethodDescriptor md) { + + FlowGraph fg = getFlowGraph(md); + Set nodeSet = fg.getNodeSet(); + for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + FlowNode flowNode = (FlowNode) iterator.next(); + if (flowNode.getDescTuple().get(0).equals(md.getThis())) { + return true; + } + } + + return false; } private int getParamLocation(String methodStr, String paramStr) { @@ -524,44 +1811,18 @@ public class LocationInference { try { - FileWriter fileWriter = new FileWriter("./infer/" + outputFileName); - BufferedWriter out = new BufferedWriter(fileWriter); - - for (int i = 0; i < sourceVec.size(); i++) { - out.write(sourceVec.get(i)); - out.newLine(); - } - out.close(); - } catch (IOException e) { - e.printStackTrace(); - } - - } - - } - - 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(); - SSJavaLattice methodLattice = md2lattice.get(md); - if (methodLattice != null) { - methodLattice.removeRedundantEdges(); + FileWriter fileWriter = new FileWriter("./infer/" + outputFileName); + BufferedWriter out = new BufferedWriter(fileWriter); + + for (int i = 0; i < sourceVec.size(); i++) { + out.write(sourceVec.get(i)); + out.newLine(); } + out.close(); + } catch (IOException e) { + e.printStackTrace(); } + } } @@ -627,83 +1888,14 @@ public class LocationInference { } private void inferLattices() { + } - // do fixed-point analysis - - ssjava.init(); + private void calculateExtraLocations() { 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(); - - Set methodDescriptorToVistSet = new HashSet(); - methodDescriptorToVistSet.addAll(descriptorListToAnalyze); - - while (!descriptorListToAnalyze.isEmpty()) { - MethodDescriptor md = descriptorListToAnalyze.removeFirst(); - methodDescriptorsToVisitStack.add(md); - } - - // analyze scheduled methods until there are no more to visit - while (!methodDescriptorsToVisitStack.isEmpty()) { - // start to analyze leaf node - MethodDescriptor md = methodDescriptorsToVisitStack.pop(); - - SSJavaLattice methodLattice = - 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); - - 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); - - if ((!methodLattice.equals(prevMethodLattice)) || (!methodInfo.equals(prevMethodInfo))) { - - setMethodLattice(md, methodLattice); - setMethodLocInfo(md, methodInfo); - - // results for callee changed, so enqueue dependents caller for - // further analysis - Iterator depsItr = ssjava.getDependents(md).iterator(); - while (depsItr.hasNext()) { - MethodDescriptor methodNext = depsItr.next(); - if (!methodDescriptorsToVisitStack.contains(methodNext) - && methodDescriptorToVistSet.contains(methodNext)) { - methodDescriptorsToVisitStack.add(methodNext); - } - } - - } - - } - - descriptorListToAnalyze = ssjava.getSortedDescriptors(); for (Iterator iterator = descriptorListToAnalyze.iterator(); iterator.hasNext();) { MethodDescriptor md = (MethodDescriptor) iterator.next(); calculateExtraLocations(md); } - } private void setMethodLocInfo(MethodDescriptor md, MethodLocationInfo methodInfo) { @@ -803,86 +1995,6 @@ public class LocationInference { return desc; } - private void analyzeMethodLattice(MethodDescriptor md, SSJavaLattice methodLattice, - MethodLocationInfo methodInfo) throws CyclicFlowException { - - // 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(); - - Set outEdgeSet = srcNode.getOutEdgeSet(); - for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) { - FlowEdge outEdge = (FlowEdge) iterator2.next(); - FlowNode dstNode = outEdge.getDst(); - - 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); - } - } - } - } - - // create mapping from param idx to inferred composite location - - int offset; - if (!md.isStatic()) { - // add 'this' reference location - offset = 1; - methodInfo.addMapParamIdxToInferLoc(0, methodInfo.getInferLocation(md.getThis())); - } else { - offset = 0; - } - - for (int idx = 0; idx < md.numParameters(); idx++) { - Descriptor paramDesc = md.getParameter(idx); - CompositeLocation inferParamLoc = methodInfo.getInferLocation(paramDesc); - methodInfo.addMapParamIdxToInferLoc(idx + offset, inferParamLoc); - } - - } - private void calculateExtraLocations(MethodDescriptor md) { // calcualte pcloc, returnloc,... @@ -904,123 +2016,122 @@ public class LocationInference { } Map mapParamToLoc = methodInfo.getMapParamIdxToInferLoc(); - Set keySet = mapParamToLoc.keySet(); + Set paramIdxSet = mapParamToLoc.keySet(); - try { - if (!ssjava.getMethodContainingSSJavaLoop().equals(md)) { - // calculate the initial program counter location - // PC location is higher than location types of all parameters - String pcLocSymbol = "PCLOC"; + if (!ssjava.getMethodContainingSSJavaLoop().equals(md)) { + // calculate the initial program counter location + // PC location is higher than location types of all parameters + String pcLocSymbol = "PCLOC"; - 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); - - Set higherLocSet = getHigherLocSymbolThan(methodLattice, paramLocLocalSymbol); - higherLocSet.remove(pcLocSymbol); - for (Iterator iterator2 = higherLocSet.iterator(); iterator2.hasNext();) { - String loc = (String) iterator2.next(); - addRelationHigherToLower(methodLattice, methodInfo, pcLocSymbol, loc); - } - } - } + Set paramInFlowSet = new HashSet(); - Set locElementSet = methodLattice.getElementSet(); - locElementSet.remove(pcLocSymbol); - for (Iterator iterator = locElementSet.iterator(); iterator.hasNext();) { - String loc = (String) iterator.next(); - if (!methodLattice.isGreaterThan(pcLocSymbol, loc)) { - addRelationHigherToLower(methodLattice, methodInfo, pcLocSymbol, loc); - } - } + for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) { + Integer paramIdx = (Integer) iterator.next(); + FlowNode paramFlowNode = fg.getParamFlowNode(paramIdx); + + if (fg.getIncomingFlowNodeSet(paramFlowNode).size() > 0) { + // parameter has in-value flows + CompositeLocation inferLoc = mapParamToLoc.get(paramIdx); + paramInFlowSet.add(inferLoc); + } } - // calculate a return location - // the return location type is lower than all parameters and location - // types - // of return values - if (!md.getReturnType().isVoid()) { - // first, generate the set of return value location types that starts - // with - // 'this' reference + if (paramInFlowSet.size() > 0) { + CompositeLocation lowestLoc = getLowest(methodLattice, paramInFlowSet); + assert (lowestLoc != null); + methodInfo.setPCLoc(lowestLoc); + } - Set inferFieldReturnLocSet = new HashSet(); + } - Set paramFlowNode = getParamNodeFlowingToReturnValue(md); - Set inferParamLocSet = new HashSet(); - if (paramFlowNode != null) { - for (Iterator iterator = paramFlowNode.iterator(); iterator.hasNext();) { - FlowNode fn = (FlowNode) iterator.next(); - CompositeLocation inferLoc = - generateInferredCompositeLocation(methodInfo, getFlowGraph(md).getLocationTuple(fn)); - inferParamLocSet.add(inferLoc); - } + // calculate a return location + // the return location type is lower than all parameters and location + // types + // of return values + if (!md.getReturnType().isVoid()) { + // first, generate the set of return value location types that starts + // with + // 'this' reference + + Set inferFieldReturnLocSet = new HashSet(); + + Set paramFlowNode = getParamNodeFlowingToReturnValue(md); + Set inferParamLocSet = new HashSet(); + if (paramFlowNode != null) { + for (Iterator iterator = paramFlowNode.iterator(); iterator.hasNext();) { + FlowNode fn = (FlowNode) iterator.next(); + CompositeLocation inferLoc = + generateInferredCompositeLocation(methodInfo, getFlowGraph(md).getLocationTuple(fn)); + inferParamLocSet.add(inferLoc); } + } - Set returnNodeSet = fg.getReturnNodeSet(); - skip: for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { - FlowNode returnNode = (FlowNode) iterator.next(); - CompositeLocation inferReturnLoc = - generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode)); - if (inferReturnLoc.get(0).getLocIdentifier().equals("this")) { - // if the location type of the return value matches "this" reference - // then, check whether this return value is equal to/lower than all - // of - // parameters that possibly flow into the return values - for (Iterator iterator2 = inferParamLocSet.iterator(); iterator2.hasNext();) { - CompositeLocation paramInferLoc = (CompositeLocation) iterator2.next(); - - if ((!paramInferLoc.equals(inferReturnLoc)) - && !isGreaterThan(methodLattice, paramInferLoc, inferReturnLoc)) { - continue skip; - } + Set returnNodeSet = fg.getReturnNodeSet(); + + skip: for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { + FlowNode returnNode = (FlowNode) iterator.next(); + CompositeLocation inferReturnLoc = + generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode)); + if (inferReturnLoc.get(0).getLocIdentifier().equals("this")) { + // if the location type of the return value matches "this" reference + // then, check whether this return value is equal to/lower than all + // of + // parameters that possibly flow into the return values + for (Iterator iterator2 = inferParamLocSet.iterator(); iterator2.hasNext();) { + CompositeLocation paramInferLoc = (CompositeLocation) iterator2.next(); + + if ((!paramInferLoc.equals(inferReturnLoc)) + && !isGreaterThan(methodLattice, paramInferLoc, inferReturnLoc)) { + continue skip; } - inferFieldReturnLocSet.add(inferReturnLoc); - } + inferFieldReturnLocSet.add(inferReturnLoc); + } + } - if (inferFieldReturnLocSet.size() > 0) { + if (inferFieldReturnLocSet.size() > 0) { - CompositeLocation returnLoc = getLowest(methodLattice, inferFieldReturnLocSet); - methodInfo.setReturnLoc(returnLoc); + CompositeLocation returnLoc = getLowest(methodLattice, inferFieldReturnLocSet); + if (returnLoc == null) { + // in this case, assign <'this',bottom> to the RETURNLOC + returnLoc = new CompositeLocation(new Location(md, md.getThis().getSymbol())); + returnLoc.addLocation(new Location(md.getClassDesc(), getLattice(md.getClassDesc()) + .getBottomItem())); + } + methodInfo.setReturnLoc(returnLoc); - } else { - String returnLocSymbol = "RETURNLOC"; - CompositeLocation returnLocInferLoc = - new CompositeLocation(new Location(md, returnLocSymbol)); - methodInfo.setReturnLoc(returnLocInferLoc); - - for (Iterator iterator = 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); - } - } + } else { + String returnLocSymbol = "RETURNLOC"; + CompositeLocation returnLocInferLoc = + new CompositeLocation(new Location(md, returnLocSymbol)); + methodInfo.setReturnLoc(returnLocInferLoc); - for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { - FlowNode returnNode = (FlowNode) iterator.next(); - CompositeLocation inferLoc = - generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode)); - if (!isGreaterThan(methodLattice, inferLoc, returnLocInferLoc)) { - addRelation(methodLattice, methodInfo, inferLoc, returnLocInferLoc); - } + for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) { + Integer paramIdx = (Integer) iterator.next(); + CompositeLocation inferLoc = mapParamToLoc.get(paramIdx); + String paramLocLocalSymbol = inferLoc.get(0).getLocIdentifier(); + if (!methodLattice.isGreaterThan(paramLocLocalSymbol, returnLocSymbol)) { + // TODO + // addRelationHigherToLower(methodLattice, methodInfo, paramLocLocalSymbol, + // returnLocSymbol); } + } + for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) { + FlowNode returnNode = (FlowNode) iterator.next(); + CompositeLocation inferLoc = + generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode)); + if (!isGreaterThan(methodLattice, inferLoc, returnLocInferLoc)) { + // TODO + // addRelation(methodLattice, methodInfo, inferLoc, returnLocInferLoc); + } } } - } catch (CyclicFlowException e) { - e.printStackTrace(); - } + } } private Set getHigherLocSymbolThan(SSJavaLattice lattice, String loc) { @@ -1047,13 +2158,57 @@ public class LocationInference { for (Iterator iterator = set.iterator(); iterator.hasNext();) { CompositeLocation loc = (CompositeLocation) iterator.next(); - if (isGreaterThan(methodLattice, lowest, loc)) { + + if ((!loc.equals(lowest)) && (!isComparable(methodLattice, lowest, loc))) { + // if there is a case where composite locations are incomparable, just + // return null + return null; + } + + if ((!loc.equals(lowest)) && isGreaterThan(methodLattice, lowest, loc)) { lowest = loc; } } return lowest; } + private boolean isComparable(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.isComparable(symbol1, symbol2)) { + return false; + } + + } + + return true; + } + private boolean isGreaterThan(SSJavaLattice methodLattice, CompositeLocation comp1, CompositeLocation comp2) { @@ -1079,6 +2234,7 @@ public class LocationInference { } else { lattice = getLattice(desc1); } + if (symbol1.equals(symbol2)) { continue; } else if (lattice.isGreaterThan(symbol1, symbol2)) { @@ -1087,367 +2243,427 @@ public class LocationInference { return false; } - } + } + + return false; + } + + private void contributeCalleeFlows(MethodInvokeNode min, MethodDescriptor mdCaller, + MethodDescriptor mdCallee) { + + System.out.println("\n##contributeCalleeFlows callee=" + mdCallee + "TO caller=" + mdCaller); + + getSubGlobalFlowGraph(mdCallee); + + } + + private GlobalFlowGraph getSubGlobalFlowGraph(MethodDescriptor md) { + return mapMethodDescriptorToSubGlobalFlowGraph.get(md); + } + + private void propagateFlowsToCallerWithNoCompositeLocation(MethodInvokeNode min, + MethodDescriptor mdCaller, MethodDescriptor mdCallee) { + + System.out.println("\n##PROPAGATE callee=" + mdCallee + "TO caller=" + mdCaller); + + // if the parameter A reaches to the parameter B + // then, add an edge the argument A -> the argument B to the caller's flow + // graph + + FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); + FlowGraph callerFlowGraph = getFlowGraph(mdCaller); + int numParam = calleeFlowGraph.getNumParameters(); + + for (int i = 0; i < numParam; i++) { + for (int k = 0; k < numParam; k++) { + + if (i != k) { + + FlowNode paramNode1 = calleeFlowGraph.getParamFlowNode(i); + FlowNode paramNode2 = calleeFlowGraph.getParamFlowNode(k); + + NTuple arg1Tuple = getNodeTupleByArgIdx(min, i); + NTuple arg2Tuple = getNodeTupleByArgIdx(min, k); + + // check if the callee propagates an ordering constraints through + // parameters + + Set localReachSet = calleeFlowGraph.getLocalReachFlowNodeSetFrom(paramNode1); + + if (localReachSet.contains(paramNode2)) { + // need to propagate an ordering relation s.t. arg1 is higher + // than arg2 + + System.out.println("-param1=" + paramNode1 + " is higher than param2=" + paramNode2); + System.out + .println("-arg1Tuple=" + arg1Tuple + " is higher than arg2Tuple=" + arg2Tuple); + + // otherwise, flows between method/field locations... + callerFlowGraph.addValueFlowEdge(arg1Tuple, arg2Tuple); + System.out.println("arg1=" + arg1Tuple + " arg2=" + arg2Tuple); + + } + + System.out.println(); + } + } + } + System.out.println("##\n"); + + } + + private void propagateFlowsToCaller(MethodInvokeNode min, MethodDescriptor mdCaller, + MethodDescriptor mdCallee) { + + System.out.println("\n##PROPAGATE callee=" + mdCallee + "TO caller=" + mdCaller); + + // if the parameter A reaches to the parameter B + // then, add an edge the argument A -> the argument B to the caller's flow + // graph + + // TODO + // also if a parameter is a composite location and is started with "this" reference, + // need to make sure that the corresponding argument is higher than the translated location of + // the parameter. + + FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); + FlowGraph callerFlowGraph = getFlowGraph(mdCaller); + int numParam = calleeFlowGraph.getNumParameters(); + + for (int i = 0; i < numParam; i++) { + for (int k = 0; k < numParam; k++) { + + if (i != k) { + + FlowNode paramNode1 = calleeFlowGraph.getParamFlowNode(i); + FlowNode paramNode2 = calleeFlowGraph.getParamFlowNode(k); + + System.out.println("param1=" + paramNode1 + " curDescTuple=" + + paramNode1.getCurrentDescTuple()); + System.out.println("param2=" + paramNode2 + " curDescTuple=" + + paramNode2.getCurrentDescTuple()); + + // TODO: deprecated method + // NodeTupleSet tupleSetArg1 = getNodeTupleSetByArgIdx(min, i); + // NodeTupleSet tupleSetArg2 = getNodeTupleSetByArgIdx(min, k); + NodeTupleSet tupleSetArg1 = null; + NodeTupleSet tupleSetArg2 = null; + + for (Iterator> iter1 = tupleSetArg1.iterator(); iter1.hasNext();) { + NTuple arg1Tuple = iter1.next(); + + for (Iterator> iter2 = tupleSetArg2.iterator(); iter2.hasNext();) { + NTuple arg2Tuple = iter2.next(); + + // check if the callee propagates an ordering constraints through + // parameters + + Set localReachSet = + calleeFlowGraph.getLocalReachFlowNodeSetFrom(paramNode1); + + if (localReachSet.contains(paramNode2)) { + // need to propagate an ordering relation s.t. arg1 is higher + // than arg2 - return false; - } + System.out + .println("-param1=" + paramNode1 + " is higher than param2=" + paramNode2); + System.out.println("-arg1Tuple=" + arg1Tuple + " is higher than arg2Tuple=" + + arg2Tuple); - private void recursiveAddRelationToLattice(int idx, MethodDescriptor md, - CompositeLocation srcInferLoc, CompositeLocation dstInferLoc) throws CyclicFlowException { + if (!min.getMethod().isStatic()) { + // check if this is the case that values flow to/from the + // current object reference 'this' - String srcLocSymbol = srcInferLoc.get(idx).getLocIdentifier(); - String dstLocSymbol = dstInferLoc.get(idx).getLocIdentifier(); + NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); + Descriptor baseRef = baseTuple.get(baseTuple.size() - 1); - if (srcLocSymbol.equals(dstLocSymbol)) { - recursiveAddRelationToLattice(idx + 1, md, srcInferLoc, dstInferLoc); - } else { + System.out.println("paramNode1.getCurrentDescTuple()=" + + paramNode1.getCurrentDescTuple()); + // calculate the prefix of the argument - Descriptor parentDesc = srcInferLoc.get(idx).getDescriptor(); - LocationInfo locInfo = getLocationInfo(parentDesc); + if (arg2Tuple.size() == 1 && arg2Tuple.get(0).equals(baseRef)) { + // in this case, the callee flow causes a caller flow to the object whose method + // is invoked. - addRelationHigherToLower(getLattice(parentDesc), getLocationInfo(parentDesc), srcLocSymbol, - dstLocSymbol); - } + if (!paramNode1.getCurrentDescTuple().startsWith(mdCallee.getThis())) { + // check whether ??? - } + NTuple param1Prefix = + calculatePrefixForParam(callerFlowGraph, calleeFlowGraph, min, arg1Tuple, + paramNode1); - private void analyzeLatticeMethodInvocationNode(MethodDescriptor mdCaller, - SSJavaLattice methodLattice, MethodLocationInfo methodInfo) - throws CyclicFlowException { + if (param1Prefix != null && param1Prefix.startsWith(mdCallee.getThis())) { + // in this case, we need to create a new edge 'this.FIELD'->'this' + // but we couldn't... instead we assign a new composite location started + // with 'this' reference to the corresponding parameter - // 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 + CompositeLocation compLocForParam1 = + generateCompositeLocation(mdCallee, param1Prefix); - Set setMethodInvokeNode = - mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller); + System.out + .println("set comp loc=" + compLocForParam1 + " to " + paramNode1); + paramNode1.setCompositeLocation(compLocForParam1); - if (setMethodInvokeNode != null) { + // then, we need to make sure that the corresponding argument in the caller + // is required to be higher than or equal to the translated parameter + // location - 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); - } + NTuple translatedParamTuple = + translateCompositeLocationToCaller(min, compLocForParam1); - for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) { - MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next(); - propagateRelationToCaller(min, mdCaller, possibleMdCallee, methodLattice, methodInfo); - } + // TODO : check if the arg >= the tranlated parameter - } - } + System.out.println("add a flow edge= " + arg1Tuple + "->" + + translatedParamTuple); + callerFlowGraph.addValueFlowEdge(arg1Tuple, translatedParamTuple); - } + continue; - private void propagateRelationToCaller(MethodInvokeNode min, MethodDescriptor mdCaller, - MethodDescriptor possibleMdCallee, SSJavaLattice methodLattice, - MethodLocationInfo methodInfo) throws CyclicFlowException { + } + } else { + // param1 has already been assigned a composite location - SSJavaLattice calleeLattice = getMethodLattice(possibleMdCallee); - MethodLocationInfo calleeLocInfo = getMethodLocationInfo(possibleMdCallee); - FlowGraph calleeFlowGraph = getFlowGraph(possibleMdCallee); + System.out.println("--param1 has already been assigned a composite location"); + CompositeLocation compLocForParam1 = paramNode1.getCompositeLocation(); + NTuple translatedParamTuple = + translateCompositeLocationToCaller(min, compLocForParam1); - 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); + // TODO : check if the arg >= the tranlated parameter + + System.out.println("add a flow edge= " + arg1Tuple + "->" + + translatedParamTuple); + callerFlowGraph.addValueFlowEdge(arg1Tuple, translatedParamTuple); - if (isGreaterThan(getLattice(possibleMdCallee), param1, param2)) { - NodeTupleSet argDescTupleSet1 = getNodeTupleSetByArgIdx(min, i); - NodeTupleSet argDescTupleSet2 = getNodeTupleSetByArgIdx(min, k); + continue; - // 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(); + } else if (arg1Tuple.size() == 1 && arg1Tuple.get(0).equals(baseRef)) { + // in this case, the callee flow causes a caller flow originated from the object + // whose + // method is invoked. - for (Iterator> iterator2 = argDescTupleSet2.iterator(); iterator2 - .hasNext();) { - NTuple argDescTuple2 = iterator2.next(); + System.out.println("###FROM CASE"); - // retreive inferred location by the local var descriptor + if (!paramNode2.getCurrentDescTuple().startsWith(mdCallee.getThis())) { - NTuple tuple1 = getFlowGraph(mdCaller).getLocationTuple(argDescTuple1); - NTuple tuple2 = getFlowGraph(mdCaller).getLocationTuple(argDescTuple2); + NTuple param2Prefix = + calculatePrefixForParam(callerFlowGraph, calleeFlowGraph, min, arg2Tuple, + paramNode2); - // CompositeLocation higherInferLoc = - // methodInfo.getInferLocation(argTuple1.get(0)); - // CompositeLocation lowerInferLoc = - // methodInfo.getInferLocation(argTuple2.get(0)); + if (param2Prefix != null && param2Prefix.startsWith(mdCallee.getThis())) { + // in this case, we need to create a new edge 'this' -> + // 'this.FIELD' but we couldn't... instead we assign the corresponding + // parameter a new composite location started with 'this' reference - CompositeLocation inferLoc1 = generateInferredCompositeLocation(methodInfo, tuple1); - CompositeLocation inferLoc2 = generateInferredCompositeLocation(methodInfo, tuple2); + CompositeLocation compLocForParam2 = + generateCompositeLocation(mdCallee, param2Prefix); - // addRelation(methodLattice, methodInfo, inferLoc1, inferLoc2); + // System.out.println("set comp loc=" + compLocForParam2 + // + + // " to " + paramNode2); + paramNode1.setCompositeLocation(compLocForParam2); + continue; + } + } + + } + } - addFlowGraphEdge(mdCaller, argDescTuple1, argDescTuple2); + // otherwise, flows between method/field locations... + callerFlowGraph.addValueFlowEdge(arg1Tuple, arg2Tuple); + System.out.println("arg1=" + arg1Tuple + " arg2=" + arg2Tuple); } } } + System.out.println(); } } } - + System.out.println("##\n"); } - private CompositeLocation generateInferredCompositeLocation(MethodLocationInfo methodInfo, - NTuple tuple) { - - // first, retrieve inferred location by the local var descriptor - CompositeLocation inferLoc = new CompositeLocation(); - - CompositeLocation localVarInferLoc = - methodInfo.getInferLocation(tuple.get(0).getLocDescriptor()); + private NTuple translateCompositeLocationToCaller(MethodInvokeNode min, + CompositeLocation compLocForParam1) { + NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); - localVarInferLoc.get(0).setLocDescriptor(tuple.get(0).getLocDescriptor()); + NTuple tuple = new NTuple(); - for (int i = 0; i < localVarInferLoc.getSize(); i++) { - inferLoc.addLocation(localVarInferLoc.get(i)); + for (int i = 0; i < baseTuple.size(); i++) { + tuple.add(baseTuple.get(i)); } - 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. - 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); - + for (int i = 1; i < compLocForParam1.getSize(); i++) { + Location loc = compLocForParam1.get(i); + tuple.add(loc.getLocDescriptor()); } - assert (inferLoc.get(0).getLocDescriptor().getSymbol() == inferLoc.get(0).getLocIdentifier()); - return inferLoc; + return tuple; } - private void addRelation(SSJavaLattice methodLattice, MethodLocationInfo methodInfo, - CompositeLocation srcInferLoc, CompositeLocation dstInferLoc) throws CyclicFlowException { + private CompositeLocation generateCompositeLocation(NTuple prefixLocTuple) { - System.out.println("addRelation --- srcInferLoc=" + srcInferLoc + " dstInferLoc=" - + dstInferLoc); - String srcLocalLocSymbol = srcInferLoc.get(0).getLocIdentifier(); - String dstLocalLocSymbol = dstInferLoc.get(0).getLocIdentifier(); + System.out.println("generateCompositeLocation=" + prefixLocTuple); - 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); - } + CompositeLocation newCompLoc = new CompositeLocation(); + for (int i = 0; i < prefixLocTuple.size(); i++) { + newCompLoc.addLocation(prefixLocTuple.get(i)); } - System.out.println(); - - } + Descriptor lastDescOfPrefix = prefixLocTuple.get(prefixLocTuple.size() - 1).getLocDescriptor(); - public LocationInfo getLocationInfo(Descriptor d) { - if (d instanceof MethodDescriptor) { - return getMethodLocationInfo((MethodDescriptor) d); + ClassDescriptor enclosingDescriptor; + if (lastDescOfPrefix instanceof FieldDescriptor) { + enclosingDescriptor = ((FieldDescriptor) lastDescOfPrefix).getType().getClassDesc(); + // System.out.println("enclosingDescriptor0=" + enclosingDescriptor); } else { - return getFieldLocationInfo((ClassDescriptor) d); + // var descriptor case + enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc(); } - } + // System.out.println("enclosingDescriptor=" + enclosingDescriptor); - private MethodLocationInfo getMethodLocationInfo(MethodDescriptor md) { - - if (!mapMethodDescToMethodLocationInfo.containsKey(md)) { - mapMethodDescToMethodLocationInfo.put(md, new MethodLocationInfo(md)); - } + LocationDescriptor newLocDescriptor = generateNewLocationDescriptor(); + newLocDescriptor.setEnclosingClassDesc(enclosingDescriptor); - return mapMethodDescToMethodLocationInfo.get(md); + Location newLoc = new Location(enclosingDescriptor, newLocDescriptor.getSymbol()); + newLoc.setLocDescriptor(newLocDescriptor); + newCompLoc.addLocation(newLoc); + // System.out.println("--newCompLoc=" + newCompLoc); + return newCompLoc; } - private LocationInfo getFieldLocationInfo(ClassDescriptor cd) { - - if (!mapClassToLocationInfo.containsKey(cd)) { - mapClassToLocationInfo.put(cd, new LocationInfo(cd)); - } + private CompositeLocation generateCompositeLocation(MethodDescriptor md, + NTuple paramPrefix) { - return mapClassToLocationInfo.get(cd); + System.out.println("generateCompositeLocation=" + paramPrefix); - } + CompositeLocation newCompLoc = convertToCompositeLocation(md, paramPrefix); - private void addRelationToLattice(MethodDescriptor md, SSJavaLattice methodLattice, - MethodLocationInfo methodInfo, FlowNode srcNode, FlowNode dstNode) throws CyclicFlowException { + Descriptor lastDescOfPrefix = paramPrefix.get(paramPrefix.size() - 1); + // System.out.println("lastDescOfPrefix=" + lastDescOfPrefix + " kind=" + // + lastDescOfPrefix.getClass()); + ClassDescriptor enclosingDescriptor; + if (lastDescOfPrefix instanceof FieldDescriptor) { + enclosingDescriptor = ((FieldDescriptor) lastDescOfPrefix).getType().getClassDesc(); + // System.out.println("enclosingDescriptor0=" + enclosingDescriptor); + } else { + // var descriptor case + enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc(); + } + // System.out.println("enclosingDescriptor=" + enclosingDescriptor); - System.out.println(); - System.out.println("### addRelationToLattice src=" + srcNode + " dst=" + dstNode); + LocationDescriptor newLocDescriptor = generateNewLocationDescriptor(); + newLocDescriptor.setEnclosingClassDesc(enclosingDescriptor); - // 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."); - } - } + Location newLoc = new Location(enclosingDescriptor, newLocDescriptor.getSymbol()); + newLoc.setLocDescriptor(newLocDescriptor); + newCompLoc.addLocation(newLoc); + // System.out.println("--newCompLoc=" + newCompLoc); + return newCompLoc; } - private void recursivelyAddRelation(int idx, CompositeLocation srcInferLoc, - CompositeLocation dstInferLoc) throws CyclicFlowException { + private NTuple calculatePrefixForParam(FlowGraph callerFlowGraph, + FlowGraph calleeFlowGraph, MethodInvokeNode min, NTuple arg1Tuple, + FlowNode paramNode1) { - String srcLocSymbol = srcInferLoc.get(idx).getLocIdentifier(); - String dstLocSymbol = dstInferLoc.get(idx).getLocIdentifier(); + NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); + Descriptor baseRef = baseTuple.get(baseTuple.size() - 1); + System.out.println("baseRef=" + baseRef); - Descriptor parentDesc = srcInferLoc.get(idx).getDescriptor(); - - 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); - } - } + FlowNode flowNodeArg1 = callerFlowGraph.getFlowNode(arg1Tuple); + List> callerPrefixList = calculatePrefixList(callerFlowGraph, flowNodeArg1); + System.out.println("callerPrefixList=" + callerPrefixList); - private void recursivelyAddCompositeRelation(MethodDescriptor md, FlowGraph flowGraph, - MethodLocationInfo methodInfo, FlowNode srcNode, FlowNode dstNode, Descriptor srcDesc, - Descriptor dstDesc) throws CyclicFlowException { + List> prefixList = calculatePrefixList(calleeFlowGraph, paramNode1); + System.out.println("###prefixList from node=" + paramNode1 + " =" + prefixList); - CompositeLocation inferSrcLoc; - CompositeLocation inferDstLoc = methodInfo.getInferLocation(dstDesc); + List> calleePrefixList = + translatePrefixListToCallee(baseRef, min.getMethod(), callerPrefixList); - if (srcNode.getDescTuple().size() > 1) { - // field access - inferSrcLoc = new CompositeLocation(); + System.out.println("calleePrefixList=" + calleePrefixList); - NTuple locTuple = flowGraph.getLocationTuple(srcNode); - for (int i = 0; i < locTuple.size(); i++) { - inferSrcLoc.addLocation(locTuple.get(i)); - } + Set reachNodeSetFromParam1 = calleeFlowGraph.getReachFlowNodeSetFrom(paramNode1); + System.out.println("reachNodeSetFromParam1=" + reachNodeSetFromParam1); - } else { - inferSrcLoc = methodInfo.getInferLocation(srcDesc); - } + for (int i = 0; i < calleePrefixList.size(); i++) { + NTuple curPrefix = calleePrefixList.get(i); + Set> reachableCommonPrefixSet = new HashSet>(); - if (dstNode.getDescTuple().size() > 1) { - // field access - inferDstLoc = new CompositeLocation(); + for (Iterator iterator2 = reachNodeSetFromParam1.iterator(); iterator2.hasNext();) { + FlowNode reachNode = (FlowNode) iterator2.next(); + if (reachNode.getCurrentDescTuple().startsWith(curPrefix)) { + reachableCommonPrefixSet.add(reachNode.getCurrentDescTuple()); + } + } - NTuple locTuple = flowGraph.getLocationTuple(dstNode); - for (int i = 0; i < locTuple.size(); i++) { - inferDstLoc.addLocation(locTuple.get(i)); + if (!reachableCommonPrefixSet.isEmpty()) { + System.out.println("###REACHABLECOMONPREFIX=" + reachableCommonPrefixSet + + " with curPreFix=" + curPrefix); + return curPrefix; } - } else { - inferDstLoc = methodInfo.getInferLocation(dstDesc); } - recursiveAddRelationToLattice(1, md, inferSrcLoc, inferDstLoc); + return null; } - private void addPrefixMapping(Map, Set>> map, - NTuple prefix, NTuple element) { + private List> translatePrefixListToCallee(Descriptor baseRef, + MethodDescriptor mdCallee, List> callerPrefixList) { - if (!map.containsKey(prefix)) { - map.put(prefix, new HashSet>()); + List> calleePrefixList = new ArrayList>(); + + for (int i = 0; i < callerPrefixList.size(); i++) { + NTuple prefix = callerPrefixList.get(i); + if (prefix.startsWith(baseRef)) { + NTuple calleePrefix = new NTuple(); + calleePrefix.add(mdCallee.getThis()); + for (int k = 1; k < prefix.size(); k++) { + calleePrefix.add(prefix.get(k)); + } + calleePrefixList.add(calleePrefix); + } } - map.get(prefix).add(element); - } - private boolean calculateCompositeLocation(FlowGraph flowGraph, - SSJavaLattice methodLattice, MethodLocationInfo methodInfo, FlowNode flowNode) - throws CyclicFlowException { + return calleePrefixList; - Descriptor localVarDesc = flowNode.getDescTuple().get(0); - NTuple flowNodelocTuple = flowGraph.getLocationTuple(flowNode); + } - if (localVarDesc.equals(methodInfo.getMethodDesc())) { - return false; - } + private List> calculatePrefixList(FlowGraph flowGraph, FlowNode flowNode) { + + System.out.println("\n##### calculatePrefixList=" + flowNode); Set inNodeSet = flowGraph.getIncomingFlowNodeSet(flowNode); - Set reachableNodeSet = flowGraph.getReachableFlowNodeSet(flowNode); + inNodeSet.add(flowNode); - Map, Set>> mapPrefixToIncomingLocTupleSet = - new HashMap, Set>>(); + System.out.println("inNodeSet=" + inNodeSet); - List> prefixList = new ArrayList>(); + 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 inNodeTuple = inNode.getCurrentDescTuple(); - NTuple inNodeInferredLocTuple = inNodeInferredLoc.getTuple(); + // CompositeLocation inNodeInferredLoc = + // generateInferredCompositeLocation(methodInfo, inNodeTuple); + // NTuple inNodeInferredLocTuple = inNodeInferredLoc.getTuple(); - for (int i = 1; i < inNodeInferredLocTuple.size(); i++) { - NTuple prefix = inNodeInferredLocTuple.subList(0, i); + for (int i = 1; i < inNodeTuple.size(); i++) { + NTuple prefix = inNodeTuple.subList(0, i); if (!prefixList.contains(prefix)) { prefixList.add(prefix); } - addPrefixMapping(mapPrefixToIncomingLocTupleSet, prefix, inNodeInferredLocTuple); } } - Collections.sort(prefixList, new Comparator>() { - public int compare(NTuple arg0, NTuple arg1) { + Collections.sort(prefixList, new Comparator>() { + public int compare(NTuple arg0, NTuple arg1) { int s0 = arg0.size(); int s1 = arg1.size(); if (s0 > s1) { @@ -1460,298 +2676,158 @@ public class LocationInference { } }); - System.out.println("prefixList=" + prefixList); - System.out.println("reachableNodeSet=" + reachableNodeSet); - - // 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); - } - } - - 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); + return prefixList; - CompositeLocation inferLocation = - generateInferredCompositeLocation(methodInfo, flowNodelocTuple); - - // methodInfo.getInferLocation(localVarDesc); - CompositeLocation newInferLocation = new CompositeLocation(); - - if (inferLocation.getTuple().startsWith(curPrefix)) { - // the same infer location is already existed. no need to do - // anything - System.out.println("NO ATTEMPT TO MAKE A COMPOSITE LOCATION curPrefix=" + curPrefix); - 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); - - // 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 lastIdx = flowNode.getDescTuple().size() - 1; - Descriptor lastFlowNodeDesc = flowNode.getDescTuple().get(lastIdx); - Descriptor enclosinglastLastFlowNodeDesc = flowNodelocTuple.get(lastIdx).getDescriptor(); - - CompositeLocation newlyInferredLocForFlowNode = - generateInferredCompositeLocation(methodInfo, flowNodelocTuple); - Location lastInferLocElement = - newlyInferredLocForFlowNode.get(newlyInferredLocForFlowNode.getSize() - 1); - Descriptor enclosingLastInferLocElement = lastInferLocElement.getDescriptor(); - - // getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToDescSet( - // lastInferLocElement.getLocIdentifier(), lastFlowNodeDesc); - getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToRelatedInferLoc( - lastInferLocElement.getLocIdentifier(), enclosinglastLastFlowNodeDesc, - 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("curPrefix=" + curPrefix); - System.out.println("ASSIGN NEW COMPOSITE LOCATION =" + newInferLocation + " to " - + flowNode); + public CompositeLocation convertToCompositeLocation(MethodDescriptor md, NTuple tuple) { - String newlyInsertedLocName = - newInferLocation.get(newInferLocation.getSize() - 1).getLocIdentifier(); + CompositeLocation compLoc = new CompositeLocation(); - System.out.println("-- add in-flow"); - for (Iterator iterator = incomingCommonPrefixSet.iterator(); iterator.hasNext();) { - NTuple tuple = (NTuple) iterator.next(); - Location loc = tuple.get(idx); - String higher = loc.getLocIdentifier(); - addRelationHigherToLower(lattice, locInfo, higher, newlyInsertedLocName); - } + Descriptor enclosingDescriptor = md; - 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 = loc.getLocIdentifier(); - // String lower = - // locInfo.getFieldInferLocation(loc.getLocDescriptor()).getLocIdentifier(); - addRelationHigherToLower(lattice, locInfo, newlyInsertedLocName, lower); - } - } + for (int i = 0; i < tuple.size(); i++) { + Descriptor curDescriptor = tuple.get(i); + Location locElement = new Location(enclosingDescriptor, curDescriptor.getSymbol()); + locElement.setLocDescriptor(curDescriptor); + compLoc.addLocation(locElement); - return true; + if (curDescriptor instanceof VarDescriptor) { + enclosingDescriptor = md.getClassDesc(); + } else if (curDescriptor instanceof NameDescriptor) { + // it is "GLOBAL LOC" case! + enclosingDescriptor = GLOBALDESC; + } else { + enclosingDescriptor = ((FieldDescriptor) curDescriptor).getClassDescriptor(); } } - return false; - - } - - private void addMapLocSymbolToInferredLocation(MethodDescriptor md, Descriptor localVar, - CompositeLocation inferLoc) { + System.out.println("-convertToCompositeLocation from=" + tuple + " to " + compLoc); - Location locElement = inferLoc.get((inferLoc.getSize() - 1)); - Descriptor enclosingDesc = locElement.getDescriptor(); - LocationInfo locInfo = getLocationInfo(enclosingDesc); - locInfo.addMapLocSymbolToRelatedInferLoc(locElement.getLocIdentifier(), md, localVar); + return compLoc; } - private boolean isCompositeLocation(CompositeLocation cl) { - return cl.getSize() > 1; + private LocationDescriptor generateNewLocationDescriptor() { + return new LocationDescriptor("Loc" + (locSeed++)); } - private boolean containsNonPrimitiveElement(Set descSet) { - for (Iterator iterator = descSet.iterator(); iterator.hasNext();) { - Descriptor desc = (Descriptor) iterator.next(); + private int getPrefixIndex(NTuple tuple1, NTuple tuple2) { - 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 the index where the prefix shared by tuple1 and tuple2 is ended + // if there is no prefix shared by both of them, return -1 + int minSize = tuple1.size(); + if (minSize > tuple2.size()) { + minSize = tuple2.size(); } - 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; + int idx = -1; + for (int i = 0; i < minSize; i++) { + if (!tuple1.get(i).equals(tuple2.get(i))) { break; + } else { + idx++; } } - 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(); - } + return idx; + } - if (cycleElementSet.size() > 0) { + private CompositeLocation generateInferredCompositeLocation(MethodLocationInfo methodInfo, + NTuple tuple) { - String newSharedLoc = "SharedLoc" + (SSJavaLattice.seed++); + // first, retrieve inferred location by the local var descriptor + CompositeLocation inferLoc = new CompositeLocation(); - System.out.println("---ASSIGN NEW SHARED LOC=" + newSharedLoc + " to " + cycleElementSet); - lattice.mergeIntoSharedLocation(cycleElementSet, newSharedLoc); + CompositeLocation localVarInferLoc = + methodInfo.getInferLocation(tuple.get(0).getLocDescriptor()); - for (Iterator iterator = cycleElementSet.iterator(); iterator.hasNext();) { - String oldLocSymbol = (String) iterator.next(); + localVarInferLoc.get(0).setLocDescriptor(tuple.get(0).getLocDescriptor()); - 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(); + for (int i = 0; i < localVarInferLoc.getSize(); i++) { + inferLoc.addLocation(localVarInferLoc.get(i)); + } - CompositeLocation inferLoc; - if (curMethodInfo.md.equals(enclosingDesc)) { - inferLoc = curMethodInfo.getInferLocation(desc); - } else { - inferLoc = getLocationInfo(enclosingDesc).getInferLocation(desc); - } + for (int i = 1; i < tuple.size(); i++) { + Location cur = tuple.get(i); + Descriptor enclosingDesc = cur.getDescriptor(); + Descriptor curDesc = cur.getLocDescriptor(); - Location locElement = inferLoc.get(inferLoc.getSize() - 1); + Location inferLocElement; + if (curDesc == null) { + // in this case, we have a newly generated location. + inferLocElement = new Location(enclosingDesc, cur.getLocIdentifier()); + } else { + String fieldLocSymbol = + getLocationInfo(enclosingDesc).getInferLocation(curDesc).get(0).getLocIdentifier(); + inferLocElement = new Location(enclosingDesc, fieldLocSymbol); + inferLocElement.setLocDescriptor(curDesc); + } - locElement.setLocIdentifier(newSharedLoc); - locInfo.addMapLocSymbolToRelatedInferLoc(newSharedLoc, enclosingDesc, desc); + inferLoc.addLocation(inferLocElement); - 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); + assert (inferLoc.get(0).getLocDescriptor().getSymbol() == inferLoc.get(0).getLocIdentifier()); + return inferLoc; + } - } + public LocationInfo getLocationInfo(Descriptor d) { + if (d instanceof MethodDescriptor) { + return getMethodLocationInfo((MethodDescriptor) d); + } else { + return getFieldLocationInfo((ClassDescriptor) d); + } + } - lattice.addSharedLoc(newSharedLoc); + private MethodLocationInfo getMethodLocationInfo(MethodDescriptor md) { - } else if (!lattice.isGreaterThan(higher, lower)) { - lattice.addRelationHigherToLower(higher, lower); + if (!mapMethodDescToMethodLocationInfo.containsKey(md)) { + mapMethodDescToMethodLocationInfo.put(md, new MethodLocationInfo(md)); } + + return mapMethodDescToMethodLocationInfo.get(md); + } - private void replaceOldLocWithNewLoc(SSJavaLattice methodLattice, String oldLocSymbol, - String newLocSymbol) { + private LocationInfo getFieldLocationInfo(ClassDescriptor cd) { - if (methodLattice.containsKey(oldLocSymbol)) { - methodLattice.substituteLocation(oldLocSymbol, newLocSymbol); + if (!mapClassToLocationInfo.containsKey(cd)) { + mapClassToLocationInfo.put(cd, new LocationInfo(cd)); } - } + return mapClassToLocationInfo.get(cd); - private void prefixSanityCheck(List> prefixList, int curIdx, - FlowGraph flowGraph, Set reachableNodeSet) { + } - NTuple curPrefix = prefixList.get(curIdx); + private void addPrefixMapping(Map, Set>> map, + NTuple prefix, NTuple element) { - for (int i = curIdx + 1; i < prefixList.size(); i++) { - NTuple prefixTuple = prefixList.get(i); + if (!map.containsKey(prefix)) { + map.put(prefix, new HashSet>()); + } + map.get(prefix).add(element); + } - if (curPrefix.startsWith(prefixTuple)) { - continue; - } + private boolean containsNonPrimitiveElement(Set descSet) { + for (Iterator iterator = descSet.iterator(); iterator.hasNext();) { + Descriptor desc = (Descriptor) iterator.next(); - 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"); + 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; } } - } - } - public boolean isPrimitiveLocalVariable(FlowNode node) { - VarDescriptor varDesc = (VarDescriptor) node.getDescTuple().get(0); - return varDesc.getType().isPrimitive(); + } + return false; } private SSJavaLattice getLattice(Descriptor d) { @@ -1773,15 +2849,18 @@ public class LocationInference { md2lattice.put(md, lattice); } - private void extractRelationFromFieldFlows(ClassDescriptor cd, FlowNode srcNode, - FlowNode dstNode, int idx) throws CyclicFlowException { + private void extractFlowsBetweenFields(ClassDescriptor cd, FlowNode srcNode, FlowNode dstNode, + int idx) { - if (srcNode.getDescTuple().get(idx).equals(dstNode.getDescTuple().get(idx)) - && srcNode.getDescTuple().size() > (idx + 1) && dstNode.getDescTuple().size() > (idx + 1)) { + NTuple srcCurTuple = srcNode.getCurrentDescTuple(); + NTuple dstCurTuple = dstNode.getCurrentDescTuple(); + + if (srcCurTuple.get(idx).equals(dstCurTuple.get(idx)) && srcCurTuple.size() > (idx + 1) + && dstCurTuple.size() > (idx + 1)) { // value flow between fields: we don't need to add a binary relation // for this case - Descriptor desc = srcNode.getDescTuple().get(idx); + Descriptor desc = srcCurTuple.get(idx); ClassDescriptor classDesc; if (idx == 0) { @@ -1790,21 +2869,15 @@ public class LocationInference { classDesc = ((FieldDescriptor) desc).getType().getClassDesc(); } - extractRelationFromFieldFlows(classDesc, srcNode, dstNode, idx + 1); + extractFlowsBetweenFields(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); - LocationInfo fieldInfo = getFieldLocationInfo(cd); + Descriptor srcFieldDesc = srcCurTuple.get(idx); + Descriptor dstFieldDesc = dstCurTuple.get(idx); - String srcSymbol = fieldInfo.getFieldInferLocation(srcFieldDesc).getLocIdentifier(); - String dstSymbol = fieldInfo.getFieldInferLocation(dstFieldDesc).getLocIdentifier(); - - addRelationHigherToLower(fieldLattice, fieldInfo, srcSymbol, dstSymbol); + // add a new edge + getHierarchyGraph(cd).addEdge(srcFieldDesc, dstFieldDesc); } @@ -1830,7 +2903,7 @@ public class LocationInference { ClassDescriptor cd = toAnalyzeNext(); setupToAnalazeMethod(cd); - toanalyzeMethodList.removeAll(visited); + temp_toanalyzeMethodList.removeAll(visited); while (!toAnalyzeMethodIsEmpty()) { MethodDescriptor md = toAnalyzeMethodNext(); @@ -1853,7 +2926,7 @@ public class LocationInference { if ((!ssjava.isTrustMethod(calleemd)) && (!ssjava.isSSJavaUtil(calleemd.getClassDesc()))) { if (!visited.contains(calleemd)) { - toanalyzeMethodList.add(calleemd); + temp_toanalyzeMethodList.add(calleemd); } reachableCallee.add(calleemd); needToAnalyzeCalleeSet.add(calleemd); @@ -1875,7 +2948,14 @@ public class LocationInference { public void constructFlowGraph() { - LinkedList methodDescList = computeMethodList(); + System.out.println(""); + toanalyze_methodDescList = computeMethodList(); + + LinkedList methodDescList = + (LinkedList) toanalyze_methodDescList.clone(); + + System.out.println("@@@methodDescList=" + methodDescList); + // System.exit(0); while (!methodDescList.isEmpty()) { MethodDescriptor md = methodDescList.removeLast(); @@ -1900,9 +2980,174 @@ public class LocationInference { mapMethodDescriptorToFlowGraph.put(md, fg); analyzeMethodBody(md.getClassDesc(), md); + + System.out.println("##constructSubGlobalFlowGraph"); + GlobalFlowGraph subGlobalFlowGraph = constructSubGlobalFlowGraph(fg); + mapMethodDescriptorToSubGlobalFlowGraph.put(md, subGlobalFlowGraph); + + // TODO + System.out.println("##addValueFlowsFromCalleeSubGlobalFlowGraph"); + addValueFlowsFromCalleeSubGlobalFlowGraph(md, subGlobalFlowGraph); + subGlobalFlowGraph.writeGraph("_SUBGLOBAL"); + + propagateFlowsFromCalleesWithNoCompositeLocation(md); + // assignCompositeLocation(md); + + } + } + // _debug_printGraph(); + + } + + private Set getMethodInvokeNodeSet(MethodDescriptor md) { + if (!mapMethodDescriptorToMethodInvokeNodeSet.containsKey(md)) { + mapMethodDescriptorToMethodInvokeNodeSet.put(md, new HashSet()); + } + return mapMethodDescriptorToMethodInvokeNodeSet.get(md); + } + + private void constructSubGlobalFlowGraph(MethodDescriptor md) { + + FlowGraph flowGraph = getFlowGraph(md); + + Set setMethodInvokeNode = getMethodInvokeNodeSet(md); + + for (Iterator iter = setMethodInvokeNode.iterator(); iter.hasNext();) { + MethodInvokeNode min = iter.next(); + propagateFlowsFromMethodInvokeNode(md, min); + } + + } + + private void propagateFlowsFromMethodInvokeNode(MethodDescriptor mdCaller, MethodInvokeNode min) { + // the transformation for a call site propagates flows through parameters + // if the method is virtual, it also grab all relations from any possible + // callees + + 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(); + contributeCalleeFlows(min, mdCaller, possibleMdCallee); + } + + } + + private void assignCompositeLocation(MethodDescriptor md) { + + FlowGraph flowGraph = getFlowGraph(md); + + Set nodeSet = flowGraph.getNodeSet(); + + next: for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + FlowNode flowNode = (FlowNode) iterator.next(); + + // assign a composite location only to the local variable + if (flowNode.getCurrentDescTuple().size() == 1) { + + List> prefixList = calculatePrefixList(flowGraph, flowNode); + Set reachSet = flowGraph.getReachFlowNodeSetFrom(flowNode); + + for (int i = 0; i < prefixList.size(); i++) { + NTuple curPrefix = prefixList.get(i); + Set> reachableCommonPrefixSet = new HashSet>(); + + for (Iterator iterator2 = reachSet.iterator(); iterator2.hasNext();) { + FlowNode reachNode = (FlowNode) iterator2.next(); + if (reachNode.getCurrentDescTuple().startsWith(curPrefix)) { + reachableCommonPrefixSet.add(reachNode.getCurrentDescTuple()); + } + } + + if (!reachableCommonPrefixSet.isEmpty()) { + System.out.println("NEED TO ASSIGN COMP LOC TO " + flowNode + " with prefix=" + + curPrefix); + CompositeLocation newCompLoc = generateCompositeLocation(md, curPrefix); + flowNode.setCompositeLocation(newCompLoc); + continue next; + } + + } + } + + } + + } + + private void propagateFlowsFromCalleesWithNoCompositeLocation(MethodDescriptor mdCaller) { + + // the transformation for a call site propagates flows through parameters + // 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(); + propagateFlowsToCallerWithNoCompositeLocation(min, mdCaller, possibleMdCallee); + } + + } + } + + } + + private void propagateFlowsFromCallees(MethodDescriptor mdCaller) { + + // the transformation for a call site propagates flows through parameters + // 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(); + propagateFlowsToCaller(min, mdCaller, possibleMdCallee); + } + } } - _debug_printGraph(); } @@ -1955,16 +3200,48 @@ public class LocationInference { break; case Kind.SwitchStatementNode: - analyzeSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn); + analyzeSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn, implicitFlowTupleSet); break; } } + private void analyzeSwitchBlockNode(MethodDescriptor md, SymbolTable nametable, + SwitchBlockNode sbn, NodeTupleSet implicitFlowTupleSet) { + + analyzeFlowBlockNode(md, nametable, sbn.getSwitchBlockStatement(), implicitFlowTupleSet); + + } + private void analyzeSwitchStatementNode(MethodDescriptor md, SymbolTable nametable, - SwitchStatementNode bsn) { - // TODO Auto-generated method stub + SwitchStatementNode ssn, NodeTupleSet implicitFlowTupleSet) { + + NodeTupleSet condTupleNode = new NodeTupleSet(); + analyzeFlowExpressionNode(md, nametable, ssn.getCondition(), condTupleNode, null, + implicitFlowTupleSet, false); + + NodeTupleSet newImplicitTupleSet = new NodeTupleSet(); + + newImplicitTupleSet.addTupleSet(implicitFlowTupleSet); + newImplicitTupleSet.addTupleSet(condTupleNode); + + if (newImplicitTupleSet.size() > 1) { + // need to create an intermediate node for the GLB of conditional locations & implicit flows + NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); + for (Iterator> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) { + NTuple tuple = idxIter.next(); + addFlowGraphEdge(md, tuple, interTuple); + } + newImplicitTupleSet.clear(); + newImplicitTupleSet.addTuple(interTuple); + } + + BlockNode sbn = ssn.getSwitchBody(); + for (int i = 0; i < sbn.size(); i++) { + analyzeSwitchBlockNode(md, nametable, (SwitchBlockNode) sbn.get(i), newImplicitTupleSet); + } + } private void analyzeFlowSubBlockNode(MethodDescriptor md, SymbolTable nametable, @@ -1979,19 +3256,46 @@ public class LocationInference { if (returnExp != null) { NodeTupleSet nodeSet = new NodeTupleSet(); + // if a return expression returns a literal value, nodeSet is empty 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.addReturnFlowNode(returnDescTuple); - for (Iterator iterator2 = implicitFlowTupleSet.iterator(); iterator2.hasNext();) { - NTuple implicitFlowDescTuple = (NTuple) iterator2.next(); - fg.addValueFlowEdge(implicitFlowDescTuple, returnDescTuple); + // if (implicitFlowTupleSet.size() == 1 + // && fg.getFlowNode(implicitFlowTupleSet.iterator().next()).isIntermediate()) { + // + // // since there is already an intermediate node for the GLB of implicit flows + // // we don't need to create another intermediate node. + // // just re-use the intermediate node for implicit flows. + // + // FlowNode meetNode = fg.getFlowNode(implicitFlowTupleSet.iterator().next()); + // + // for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + // NTuple returnNodeTuple = (NTuple) iterator.next(); + // fg.addValueFlowEdge(returnNodeTuple, meetNode.getDescTuple()); + // } + // + // } + + NodeTupleSet currentFlowTupleSet = new NodeTupleSet(); + + // add tuples from return node + currentFlowTupleSet.addTupleSet(nodeSet); + + // add tuples corresponding to the current implicit flows + currentFlowTupleSet.addTupleSet(implicitFlowTupleSet); + + if (currentFlowTupleSet.size() > 1) { + FlowNode meetNode = fg.createIntermediateNode(); + for (Iterator iterator = currentFlowTupleSet.iterator(); iterator.hasNext();) { + NTuple currentFlowTuple = (NTuple) iterator.next(); + fg.addValueFlowEdge(currentFlowTuple, meetNode.getDescTuple()); } + fg.addReturnFlowNode(meetNode.getDescTuple()); + } else if (currentFlowTupleSet.size() == 1) { + NTuple tuple = currentFlowTupleSet.iterator().next(); + fg.addReturnFlowNode(tuple); } + } } @@ -2004,10 +3308,49 @@ public class LocationInference { NodeTupleSet condTupleNode = new NodeTupleSet(); analyzeFlowExpressionNode(md, nametable, ln.getCondition(), condTupleNode, null, implicitFlowTupleSet, false); - condTupleNode.addTupleSet(implicitFlowTupleSet); + + NodeTupleSet newImplicitTupleSet = new NodeTupleSet(); + + newImplicitTupleSet.addTupleSet(implicitFlowTupleSet); + newImplicitTupleSet.addTupleSet(condTupleNode); + + if (newImplicitTupleSet.size() > 1) { + // need to create an intermediate node for the GLB of conditional locations & implicit flows + NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); + for (Iterator> idxIter = newImplicitTupleSet.iterator(); idxIter + .hasNext();) { + NTuple tuple = idxIter.next(); + addFlowGraphEdge(md, tuple, interTuple); + } + newImplicitTupleSet.clear(); + newImplicitTupleSet.addTuple(interTuple); + + } + + // /////////// + // System.out.println("condTupleNode="+condTupleNode); + // NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); + // + // for (Iterator> idxIter = condTupleNode.iterator(); idxIter.hasNext();) { + // NTuple tuple = idxIter.next(); + // addFlowGraphEdge(md, tuple, interTuple); + // } + + // for (Iterator> idxIter = implicitFlowTupleSet.iterator(); idxIter + // .hasNext();) { + // NTuple tuple = idxIter.next(); + // addFlowGraphEdge(md, tuple, interTuple); + // } + + // NodeTupleSet newImplicitSet = new NodeTupleSet(); + // newImplicitSet.addTuple(interTuple); + analyzeFlowBlockNode(md, nametable, ln.getBody(), newImplicitTupleSet); + // /////////// + + // condTupleNode.addTupleSet(implicitFlowTupleSet); // add edges from condNodeTupleSet to all nodes of conditional nodes - analyzeFlowBlockNode(md, nametable, ln.getBody(), condTupleNode); + // analyzeFlowBlockNode(md, nametable, ln.getBody(), condTupleNode); } else { // check 'for loop' case @@ -2021,10 +3364,33 @@ public class LocationInference { NodeTupleSet condTupleNode = new NodeTupleSet(); analyzeFlowExpressionNode(md, bn.getVarTable(), ln.getCondition(), condTupleNode, null, implicitFlowTupleSet, false); - condTupleNode.addTupleSet(implicitFlowTupleSet); - analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(), condTupleNode); - analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(), condTupleNode); + // /////////// + NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); + + for (Iterator> idxIter = condTupleNode.iterator(); idxIter.hasNext();) { + NTuple tuple = idxIter.next(); + addFlowGraphEdge(md, tuple, interTuple); + } + + for (Iterator> idxIter = implicitFlowTupleSet.iterator(); idxIter + .hasNext();) { + NTuple tuple = idxIter.next(); + addFlowGraphEdge(md, tuple, interTuple); + } + + NodeTupleSet newImplicitSet = new NodeTupleSet(); + newImplicitSet.addTuple(interTuple); + analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(), newImplicitSet); + analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(), newImplicitSet); + // /////////// + + // condTupleNode.addTupleSet(implicitFlowTupleSet); + // + // analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(), + // condTupleNode); + // analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(), + // condTupleNode); } @@ -2033,16 +3399,37 @@ public class LocationInference { private void analyzeFlowIfStatementNode(MethodDescriptor md, SymbolTable nametable, IfStatementNode isn, NodeTupleSet implicitFlowTupleSet) { + System.out.println("analyzeFlowIfStatementNode=" + isn.printNode(0)); + NodeTupleSet condTupleNode = new NodeTupleSet(); analyzeFlowExpressionNode(md, nametable, isn.getCondition(), condTupleNode, null, implicitFlowTupleSet, false); - // add edges from condNodeTupleSet to all nodes of conditional nodes - condTupleNode.addTupleSet(implicitFlowTupleSet); - analyzeFlowBlockNode(md, nametable, isn.getTrueBlock(), condTupleNode); + NodeTupleSet newImplicitTupleSet = new NodeTupleSet(); + + newImplicitTupleSet.addTupleSet(implicitFlowTupleSet); + newImplicitTupleSet.addTupleSet(condTupleNode); + + System.out.println("condTupleNode=" + condTupleNode); + System.out.println("implicitFlowTupleSet=" + implicitFlowTupleSet); + System.out.println("newImplicitTupleSet=" + newImplicitTupleSet); + + if (newImplicitTupleSet.size() > 1) { + + // need to create an intermediate node for the GLB of conditional locations & implicit flows + NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); + for (Iterator> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) { + NTuple tuple = idxIter.next(); + addFlowGraphEdge(md, tuple, interTuple); + } + newImplicitTupleSet.clear(); + newImplicitTupleSet.addTuple(interTuple); + } + + analyzeFlowBlockNode(md, nametable, isn.getTrueBlock(), newImplicitTupleSet); if (isn.getFalseBlock() != null) { - analyzeFlowBlockNode(md, nametable, isn.getFalseBlock(), condTupleNode); + analyzeFlowBlockNode(md, nametable, isn.getFalseBlock(), newImplicitTupleSet); } } @@ -2059,14 +3446,25 @@ public class LocationInference { if (dn.getExpression() != null) { - NodeTupleSet tupleSetRHS = new NodeTupleSet(); - analyzeFlowExpressionNode(md, nametable, dn.getExpression(), tupleSetRHS, null, + NodeTupleSet nodeSetRHS = new NodeTupleSet(); + analyzeFlowExpressionNode(md, nametable, dn.getExpression(), nodeSetRHS, null, implicitFlowTupleSet, false); - // add a new flow edge from rhs to lhs - for (Iterator> iter = tupleSetRHS.iterator(); iter.hasNext();) { - NTuple from = iter.next(); - addFlowGraphEdge(md, from, tupleLHS); + // creates edges from RHS to LHS + NTuple interTuple = null; + if (nodeSetRHS.size() > 1) { + interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); + } + + for (Iterator> iter = nodeSetRHS.iterator(); iter.hasNext();) { + NTuple fromTuple = iter.next(); + addFlowGraphEdge(md, fromTuple, interTuple, tupleLHS); + } + + // creates edges from implicitFlowTupleSet to LHS + for (Iterator> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) { + NTuple implicitTuple = iter.next(); + addFlowGraphEdge(md, implicitTuple, tupleLHS); } } @@ -2221,13 +3619,12 @@ public class LocationInference { private void analyzeFlowMethodInvokeNode(MethodDescriptor md, SymbolTable nametable, MethodInvokeNode min, NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) { + System.out.println("analyzeFlowMethodInvokeNode=" + min.printNode(0)); if (nodeSet == null) { nodeSet = new NodeTupleSet(); } - addMapCallerMethodDescToMethodInvokeNodeSet(md, min); - MethodDescriptor calleeMethodDesc = min.getMethod(); NameDescriptor baseName = min.getBaseName(); @@ -2239,19 +3636,25 @@ public class LocationInference { if (!ssjava.isSSJavaUtil(calleeMethodDesc.getClassDesc()) && !ssjava.isTrustMethod(calleeMethodDesc) && !isSystemout) { + addMapCallerMethodDescToMethodInvokeNodeSet(md, min); + FlowGraph calleeFlowGraph = getFlowGraph(calleeMethodDesc); Set calleeReturnSet = calleeFlowGraph.getReturnNodeSet(); + System.out.println("#calleeReturnSet=" + calleeReturnSet); + if (min.getExpression() != null) { NodeTupleSet baseNodeSet = new NodeTupleSet(); analyzeFlowExpressionNode(md, nametable, min.getExpression(), baseNodeSet, null, implicitFlowTupleSet, false); + assert (baseNodeSet.size() == 1); + NTuple baseTuple = baseNodeSet.iterator().next(); + mapMethodInvokeNodeToBaseTuple.put(min, baseTuple); if (!min.getMethod().isStatic()) { - addArgIdxMap(min, 0, baseNodeSet); - + addArgIdxMap(min, 0, baseTuple); for (Iterator iterator = calleeReturnSet.iterator(); iterator.hasNext();) { FlowNode returnNode = (FlowNode) iterator.next(); @@ -2259,15 +3662,13 @@ public class LocationInference { if (returnDescTuple.startsWith(calleeMethodDesc.getThis())) { // the location type of the return value is started with 'this' // reference - for (Iterator> baseIter = baseNodeSet.iterator(); baseIter - .hasNext();) { - NTuple baseTuple = baseIter.next(); - NTuple inFlowTuple = new NTuple(baseTuple.getList()); - inFlowTuple.addAll(returnDescTuple.subList(1, returnDescTuple.size())); - nodeSet.addTuple(inFlowTuple); - } + NTuple inFlowTuple = new NTuple(baseTuple.getList()); + inFlowTuple.addAll(returnDescTuple.subList(1, returnDescTuple.size())); + nodeSet.addTuple(inFlowTuple); } else { + // TODO Set inFlowSet = calleeFlowGraph.getIncomingFlowNodeSet(returnNode); + System.out.println("inFlowSet=" + inFlowSet + " from retrunNode=" + returnNode); for (Iterator iterator2 = inFlowSet.iterator(); iterator2.hasNext();) { FlowNode inFlowNode = (FlowNode) iterator2.next(); if (inFlowNode.getDescTuple().startsWith(calleeMethodDesc.getThis())) { @@ -2277,6 +3678,7 @@ public class LocationInference { } } } + } // analyze parameter flows @@ -2294,9 +3696,28 @@ public class LocationInference { ExpressionNode en = min.getArg(i); int idx = i + offset; NodeTupleSet argTupleSet = new NodeTupleSet(); - analyzeFlowExpressionNode(md, nametable, en, argTupleSet, true); - // if argument is liternal node, argTuple is set to NULL. - addArgIdxMap(min, idx, argTupleSet); + analyzeFlowExpressionNode(md, nametable, en, argTupleSet, false); + // if argument is liternal node, argTuple is set to NULL + + NTuple argTuple = new NTuple(); + System.out.println("-argTupleSet=" + argTupleSet + " from en=" + en.printNode(0)); + if (argTupleSet.size() > 1) { + NTuple interTuple = + getFlowGraph(md).createIntermediateNode().getDescTuple(); + for (Iterator> idxIter = argTupleSet.iterator(); idxIter.hasNext();) { + NTuple tuple = idxIter.next(); + addFlowGraphEdge(md, tuple, interTuple); + } + argTuple = interTuple; + } else if (argTupleSet.size() == 1) { + argTuple = argTupleSet.iterator().next(); + } else { + argTuple = new NTuple(); + } + + if (argTuple.size() != 0) { + addArgIdxMap(min, idx, argTuple); + } FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx); if (hasInFlowTo(calleeFlowGraph, paramNode, calleeReturnSet) || calleeMethodDesc.getModifiers().isNative()) { @@ -2307,13 +3728,20 @@ public class LocationInference { } + // propagateFlowsFromCallee(min, md, min.getMethod()); + + System.out.println("min nodeSet=" + nodeSet); } } private boolean hasInFlowTo(FlowGraph fg, FlowNode inNode, Set nodeSet) { // return true if inNode has in-flows to nodeSet - Set reachableSet = fg.getReachableFlowNodeSet(inNode); + + // Set reachableSet = fg.getReachFlowNodeSetFrom(inNode); + Set reachableSet = fg.getReachableSetFrom(inNode.getDescTuple()); + System.out.println("inNode=" + inNode + " reachalbeSet=" + reachableSet); + for (Iterator iterator = reachableSet.iterator(); iterator.hasNext();) { FlowNode fn = (FlowNode) iterator.next(); if (nodeSet.contains(fn)) { @@ -2323,48 +3751,20 @@ public class LocationInference { return false; } - private NodeTupleSet getNodeTupleSetByArgIdx(MethodInvokeNode min, int idx) { + private NTuple getNodeTupleByArgIdx(MethodInvokeNode min, int idx) { return mapMethodInvokeNodeToArgIdxMap.get(min).get(new Integer(idx)); } - private void addArgIdxMap(MethodInvokeNode min, int idx, NodeTupleSet tupleSet) { - Map mapIdxToTupleSet = mapMethodInvokeNodeToArgIdxMap.get(min); - if (mapIdxToTupleSet == null) { - mapIdxToTupleSet = new HashMap(); - mapMethodInvokeNodeToArgIdxMap.put(min, mapIdxToTupleSet); - } - mapIdxToTupleSet.put(new Integer(idx), tupleSet); - } - - private void analyzeFlowMethodParameters(MethodDescriptor callermd, SymbolTable nametable, - MethodInvokeNode min, NodeTupleSet nodeSet) { - - if (min.numArgs() > 0) { - - 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); - // nodeSet.addTuple(thisArgTuple); - } - - for (int i = 0; i < min.numArgs(); i++) { - ExpressionNode en = min.getArg(i); - 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); - nodeSet.addTupleSet(argTupleSet); - } - + private void addArgIdxMap(MethodInvokeNode min, int idx, NTuple argTuple /* + * NodeTupleSet + * tupleSet + */) { + Map> mapIdxToTuple = mapMethodInvokeNodeToArgIdxMap.get(min); + if (mapIdxToTuple == null) { + mapIdxToTuple = new HashMap>(); + mapMethodInvokeNodeToArgIdxMap.put(min, mapIdxToTuple); } - + mapIdxToTuple.put(new Integer(idx), argTuple); } private void analyzeLiteralNode(MethodDescriptor md, SymbolTable nametable, LiteralNode en) { @@ -2375,7 +3775,8 @@ public class LocationInference { ArrayAccessNode aan, NodeTupleSet nodeSet, boolean isLHS) { NodeTupleSet expNodeTupleSet = new NodeTupleSet(); - analyzeFlowExpressionNode(md, nametable, aan.getExpression(), expNodeTupleSet, isLHS); + NTuple base = + analyzeFlowExpressionNode(md, nametable, aan.getExpression(), expNodeTupleSet, isLHS); NodeTupleSet idxNodeTupleSet = new NodeTupleSet(); analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, isLHS); @@ -2466,6 +3867,8 @@ public class LocationInference { private NTuple analyzeFlowNameNode(MethodDescriptor md, SymbolTable nametable, NameNode nn, NodeTupleSet nodeSet, NTuple base, NodeTupleSet implicitFlowTupleSet) { + // System.out.println("analyzeFlowNameNode=" + nn.printNode(0)); + if (base == null) { base = new NTuple(); } @@ -2516,7 +3919,7 @@ public class LocationInference { } else if (d == null) { // access static field base.add(GLOBALDESC); - // base.add(nn.getField()); + base.add(nn.getField()); return base; // FieldDescriptor fd = nn.getField();addFlowGraphEdge @@ -2565,12 +3968,14 @@ public class LocationInference { } 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 = @@ -2600,7 +4005,6 @@ public class LocationInference { getFlowGraph(md).addValueFlowEdge(idxTuple, flowFieldTuple); } } - return flowFieldTuple; } @@ -2644,6 +4048,7 @@ public class LocationInference { 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();) { @@ -2654,11 +4059,16 @@ public class LocationInference { } // creates edges from RHS to LHS + NTuple interTuple = null; + if (nodeSetRHS.size() > 1) { + interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); + } + for (Iterator> iter = nodeSetRHS.iterator(); iter.hasNext();) { NTuple fromTuple = iter.next(); for (Iterator> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) { NTuple toTuple = iter2.next(); - addFlowGraphEdge(md, fromTuple, toTuple); + addFlowGraphEdge(md, fromTuple, interTuple, toTuple); } } @@ -2673,6 +4083,7 @@ public class LocationInference { } else { // postinc case + for (Iterator> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) { NTuple tuple = iter2.next(); addFlowGraphEdge(md, tuple, tuple); @@ -2700,13 +4111,119 @@ public class LocationInference { 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; } + private void addFlowGraphEdge(MethodDescriptor md, NTuple from, + NTuple inter, NTuple to) { + + FlowGraph graph = getFlowGraph(md); + + if (inter != null) { + graph.addValueFlowEdge(from, inter); + graph.addValueFlowEdge(inter, to); + } else { + graph.addValueFlowEdge(from, to); + } + + } + + public void writeInferredLatticeDotFile(ClassDescriptor cd, HierarchyGraph simpleHierarchyGraph, + SSJavaLattice locOrder, String nameSuffix) { + writeInferredLatticeDotFile(cd, null, simpleHierarchyGraph, locOrder, nameSuffix); + } + + public void writeInferredLatticeDotFile(ClassDescriptor cd, MethodDescriptor md, + HierarchyGraph simpleHierarchyGraph, SSJavaLattice locOrder, String nameSuffix) { + + String fileName = "lattice_"; + if (md != null) { + fileName += + cd.getSymbol().replaceAll("[\\W_]", "") + "_" + md.toString().replaceAll("[\\W_]", ""); + } else { + fileName += cd.getSymbol().replaceAll("[\\W_]", ""); + } + + fileName += nameSuffix; + + Set> pairSet = locOrder.getOrderingPairSet(); + + Set addedLocSet = new HashSet(); + + if (pairSet.size() > 0) { + try { + BufferedWriter bw = new BufferedWriter(new FileWriter(fileName + ".dot")); + + bw.write("digraph " + fileName + " {\n"); + + for (Iterator iterator = pairSet.iterator(); iterator.hasNext();) { + // pair is in the form of + Pair pair = (Pair) iterator.next(); + + String highLocId = pair.getFirst(); + String lowLocId = pair.getSecond(); + + if (!addedLocSet.contains(highLocId)) { + addedLocSet.add(highLocId); + drawNode(bw, locOrder, simpleHierarchyGraph, highLocId); + } + + if (!addedLocSet.contains(lowLocId)) { + addedLocSet.add(lowLocId); + drawNode(bw, locOrder, simpleHierarchyGraph, lowLocId); + } + + bw.write(highLocId + " -> " + lowLocId + ";\n"); + } + bw.write("}\n"); + bw.close(); + + } catch (IOException e) { + e.printStackTrace(); + } + + } + + } + + private String convertMergeSetToString(HierarchyGraph graph, Set mergeSet) { + String str = ""; + for (Iterator iterator = mergeSet.iterator(); iterator.hasNext();) { + HNode merged = (HNode) iterator.next(); + if (merged.isMergeNode()) { + str += convertMergeSetToString(graph, graph.getMapHNodetoMergeSet().get(merged)); + } else { + str += " " + merged.getName(); + } + } + return str; + } + + private void drawNode(BufferedWriter bw, SSJavaLattice lattice, HierarchyGraph graph, + String locName) throws IOException { + + HNode node = graph.getHNode(locName); + + if (node == null) { + return; + } + + String prettyStr; + if (lattice.isSharedLoc(locName)) { + prettyStr = locName + "*"; + } else { + prettyStr = locName; + } + + if (node.isMergeNode()) { + Set mergeSet = graph.getMapHNodetoMergeSet().get(node); + prettyStr += ":" + convertMergeSetToString(graph, mergeSet); + } + bw.write(locName + " [label=\"" + prettyStr + "\"]" + ";\n"); + } + public void _debug_printGraph() { Set keySet = mapMethodDescriptorToFlowGraph.keySet(); @@ -2727,3 +4244,11 @@ public class LocationInference { class CyclicFlowException extends Exception { } + +class InterDescriptor extends Descriptor { + + public InterDescriptor(String name) { + super(name); + } + +}