X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=Robust%2Fsrc%2FAnalysis%2FSSJava%2FLocationInference.java;h=36645aa1c8ae24ee4cbf0b49f919dc1d3c6a94cb;hb=13a63ea76172e2fd0ce7987bf81845c44c839d55;hp=2bb1330bdd5d46ea3a58227c8ec2384c737e12fe;hpb=7bc8bfe860ceea4a366d0e35998ce5386b8226c3;p=IRC.git diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index 2bb1330b..36645aa1 100644 --- a/Robust/src/Analysis/SSJava/LocationInference.java +++ b/Robust/src/Analysis/SSJava/LocationInference.java @@ -1,19 +1,32 @@ package Analysis.SSJava; +import java.io.BufferedReader; +import java.io.BufferedWriter; +import java.io.FileReader; +import java.io.FileWriter; +import java.io.IOException; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.HashMap; +import java.util.HashSet; import java.util.Iterator; +import java.util.LinkedList; import java.util.List; import java.util.Map; +import java.util.Set; +import java.util.Stack; +import java.util.Vector; import IR.ClassDescriptor; import IR.Descriptor; import IR.FieldDescriptor; import IR.MethodDescriptor; +import IR.NameDescriptor; +import IR.Operation; import IR.State; import IR.SymbolTable; +import IR.TypeDescriptor; import IR.VarDescriptor; import IR.Tree.ArrayAccessNode; import IR.Tree.AssignmentNode; @@ -37,44 +50,144 @@ import IR.Tree.SubBlockNode; import IR.Tree.SwitchBlockNode; import IR.Tree.SwitchStatementNode; import IR.Tree.TertiaryNode; +import IR.Tree.TreeNode; +import Util.Pair; 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; + + // keep current descriptors to visit in fixed-point interprocedural analysis, + private Stack methodDescriptorsToVisitStack; + + // map a class descriptor to a field lattice + private Map> cd2lattice; + + // 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> mapMethodInvokeNodeToBaseTuple; + + private Map mapMethodDescToMethodLocationInfo; + + private Map mapClassToLocationInfo; + + private Map> mapMethodToCalleeSet; + + private Map> mapMethodDescToParamNodeFlowsToReturnValue; + + private Map> mapFileNameToLineVector; + + 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; + + 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); + + public static String newline = System.getProperty("line.separator"); + + LocationInfo curMethodInfo; boolean debug = true; - InferGraph graph; + 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.graph = new InferGraph(); + this.temp_toanalyzeList = new ArrayList(); + this.temp_toanalyzeMethodList = new ArrayList(); + this.mapMethodDescriptorToFlowGraph = new HashMap(); + this.cd2lattice = new HashMap>(); + this.md2lattice = new HashMap>(); + this.methodDescriptorsToVisitStack = new Stack(); + this.mapMethodDescriptorToMethodInvokeNodeSet = + new HashMap>(); + this.mapMethodInvokeNodeToArgIdxMap = + new HashMap>>(); + this.mapMethodDescToMethodLocationInfo = new HashMap(); + this.mapMethodToCalleeSet = new HashMap>(); + this.mapClassToLocationInfo = new HashMap(); + + this.mapFileNameToLineVector = new HashMap>(); + 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(); + + mapMethodDescriptorToSubGlobalFlowGraph = new HashMap(); + } public void setupToAnalyze() { SymbolTable classtable = state.getClassSymbolTable(); - toanalyzeList.clear(); - toanalyzeList.addAll(classtable.getValueSet()); - Collections.sort(toanalyzeList, new Comparator() { - public int compare(ClassDescriptor o1, ClassDescriptor o2) { - return o1.getClassName().compareToIgnoreCase(o2.getClassName()); - } - }); + 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()); + // } + // }); } 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()); } @@ -82,192 +195,4507 @@ 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); } - private void checkDeclarationInClass(ClassDescriptor cd) { - // Check to see that fields are okay - for (Iterator field_it = cd.getFields(); field_it.hasNext();) { - FieldDescriptor fd = (FieldDescriptor) field_it.next(); + public void inference() { + + // 1) construct value flow graph + constructFlowGraph(); - if (!(fd.isFinal() && fd.isStatic())) { - analyzeFieldDeclaration(cd, fd); - } else { - // for static final, assign top location by default - graph.assignTopLocationToDescriptor(fd); + 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(); + + // 3) check properties + checkLattices(); + + // calculate RETURNLOC,PCLOC + calculateExtraLocations(); + + debug_writeLatticeDotFile(); + + // 4) generate annotated source codes + generateAnnoatedCode(); + + } + + private void constructGlobalFlowGraph() { + + System.out.println(""); + LinkedList methodDescList = + (LinkedList) toanalyze_methodDescList.clone(); + + System.out.println("@@@methodDescList=" + methodDescList); + // System.exit(0); + + while (!methodDescList.isEmpty()) { + MethodDescriptor md = methodDescList.removeLast(); + if (state.SSJAVADEBUG) { + System.out.println(); + System.out.println("SSJAVA: Constructing a global flow graph: " + md); + + FlowGraph flowGraph = getFlowGraph(md); + FlowGraph subGlobalFlowGraph = flowGraph.clone(); + mapMethodDescriptorToSubGlobalFlowGraph.put(md, subGlobalFlowGraph); + + 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); } + } - } - private void analyzeFieldDeclaration(ClassDescriptor cd, FieldDescriptor fd) { - graph.assignUniqueIDtoDescriptor(fd); + // 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(); + } - public void inference() { + private void assignCompositeLocation(FlowGraph globalFlowGraph) { + Set nodeSet = globalFlowGraph.getNodeSet(); - // 1) assign a unique id to every field & variable - setupToAnalyze(); + for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + FlowNode flowNode = (FlowNode) iterator.next(); + Set inNodeSet = globalFlowGraph.getIncomingFlowNodeSet(flowNode); + Set reachableNodeSet = globalFlowGraph.getReachFlowNodeSetFrom(flowNode); - while (!toAnalyzeIsEmpty()) { - ClassDescriptor cd = toAnalyzeNext(); + // System.out.println("flowNode=" + flowNode + " incoming=" + inNodeSet); + // System.out.println("reachableNodeSet=" + reachableNodeSet); - System.out.println("SSJAVA: Location Inference on the class: " + cd); - checkDeclarationInClass(cd); + Map, Set>> mapPrefixToIncomingLocTupleSet = + new HashMap, Set>>(); - setupToAnalazeMethod(cd); - while (!toAnalyzeMethodIsEmpty()) { - MethodDescriptor md = toAnalyzeMethodNext(); + List> prefixList = new ArrayList>(); - if (ssjava.needTobeAnnotated(md)) { - // assigns unique id to the method parameters - assignUniqueIDMethodParamteres(cd, md); + for (Iterator iterator2 = inNodeSet.iterator(); iterator2.hasNext();) { + FlowNode inNode = (FlowNode) iterator2.next(); - if (state.SSJAVADEBUG) { - System.out.println("SSJAVA: Location Inference on the method: " + md); + NTuple inNodeTuple = inNode.getCurrentDescTuple(); + + // CompositeLocation inNodeInferredLoc = + // generateInferredCompositeLocation(methodInfo, inNodeTuple); + // NTuple inNodeInferredLocTuple = inNodeInferredLoc.getTuple(); + + 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; + } + } + }); + + // 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 = reachableNode.getCurrentDescTuple(); + if (reachLocTuple.startsWith(curPrefix)) { + reachableCommonPrefixSet.add(reachLocTuple); } - assignUniqueIDMethodBody(cd, md); } + + if (!reachableCommonPrefixSet.isEmpty()) { + // found reachable nodes that start with the prefix curPrefix + // need to assign a composite location + // System.out.println("-prefixList=" + prefixList); + // System.out.println("-reachableCommonPrefixSet=" + reachableCommonPrefixSet); + // System.out.println("-curPrefix=" + curPrefix); + + // 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, globalFlowGraph, reachableNodeSet); + + MethodDescriptor topMethodDesc = globalFlowGraph.getMethodDescriptor(); + CompositeLocation newCompLoc = generateCompositeLocation(curPrefix, topMethodDesc); + + System.out.println("SET COMPOSITE LOCATION=" + newCompLoc + " to " + flowNode); + flowNode.setCompositeLocation(newCompLoc); + } + } + + } + + } + + private CompositeLocation generateCompositeLocation(NTuple curPrefix, + MethodDescriptor md) { + CompositeLocation newCompLoc = new CompositeLocation(); + + Descriptor enclosingDesc = md; + for (int i = 0; i < curPrefix.size(); i++) { + Descriptor curDesc = curPrefix.get(i); + Location loc = new Location(enclosingDesc, curDesc.getSymbol()); + newCompLoc.addLocation(loc); + if (i == 0) { + VarDescriptor varDesc = (VarDescriptor) curDesc; + enclosingDesc = varDesc.getType().getClassDesc(); + } else { + FieldDescriptor fieldDesc = (FieldDescriptor) curDesc; + enclosingDesc = fieldDesc.getType().getClassDesc(); } } - // 2) construct value flow graph + LocationDescriptor newLocDescriptor = generateNewLocationDescriptor(); + newLocDescriptor.setEnclosingClassDesc((ClassDescriptor) enclosingDesc); - setupToAnalyze(); + Location newLoc = new Location(enclosingDesc, newLocDescriptor.getSymbol()); + newLoc.setLocDescriptor(newLocDescriptor); + newCompLoc.addLocation(newLoc); - while (!toAnalyzeIsEmpty()) { - ClassDescriptor cd = toAnalyzeNext(); + return newCompLoc; + } - setupToAnalazeMethod(cd); - while (!toAnalyzeMethodIsEmpty()) { - MethodDescriptor md = toAnalyzeMethodNext(); - if (ssjava.needTobeAnnotated(md)) { - if (state.SSJAVADEBUG) { - System.out.println("SSJAVA: Constructing a flow graph: " + md); - } - analyzeMethodBody(cd, md); + private void prefixSanityCheck(List> prefixList, int curIdx, + FlowGraph globalFlowGraph, Set reachableNodeSet) { + + NTuple curPrefix = prefixList.get(curIdx); + + for (int i = curIdx + 1; i < prefixList.size(); i++) { + NTuple prefixTuple = prefixList.get(i); + + if (curPrefix.startsWith(prefixTuple)) { + continue; + } + + for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) { + FlowNode reachableNode = (FlowNode) iterator2.next(); + NTuple reachLocTuple = reachableNode.getCurrentDescTuple(); + if (reachLocTuple.startsWith(prefixTuple)) { + throw new Error( + "Failed to generate a composite location because there is more than one prefix which is reach to the current node."); } } } } - private void analyzeMethodBody(ClassDescriptor cd, MethodDescriptor md) { - BlockNode bn = state.getMethodBody(md); - // checkLocationFromBlockNode(md, md.getParameterTable(), bn, constraints); + private void addValueFlowsFromCalleeSubGlobalFlowGraph(MethodDescriptor mdCaller, + FlowGraph 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); + // propagateFlowsToCallerWithNoCompositeLocation(min, mdCaller, possibleMdCallee); + } + + } + } - private void assignUniqueIDMethodParamteres(ClassDescriptor cd, MethodDescriptor md) { + private void propagateValueFlowsToCallerFromSubGlobalFlowGraph(MethodInvokeNode min, + MethodDescriptor mdCaller, MethodDescriptor possibleMdCallee) { - List paramList = new ArrayList(); - for (int i = 0; i < md.numParameters(); i++) { - // process annotations on method parameters - VarDescriptor vd = (VarDescriptor) md.getParameter(i); - graph.assignUniqueIDtoDescriptor(vd); + NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); + + 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 assignUniqueIDMethodBody(ClassDescriptor cd, MethodDescriptor md) { - BlockNode bn = state.getMethodBody(md); - assignUniqueIDBlockNode(md, md.getParameterTable(), bn); + private void addValueFlowsFromCalleeParam(MethodInvokeNode min, FlowGraph calleeSubGlobalGraph, + FlowNode paramNode, FlowGraph callerSubGlobalGraph, NTuple argTuple, + NTuple baseTuple) { + + Set visited = new HashSet(); + + visited.add(paramNode); + recurAddValueFlowsFromCalleeParam(min, calleeSubGlobalGraph, paramNode, callerSubGlobalGraph, + argTuple, visited, baseTuple); } - private void assignUniqueIDBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn) { + 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); + } - bn.getVarTable().setParent(nametable); - for (int i = 0; i < bn.size(); i++) { - BlockStatementNode bsn = bn.get(i); - assignUniqueIDBlockStatementNode(md, bn.getVarTable(), bsn); } } - private void assignUniqueIDBlockStatementNode(MethodDescriptor md, SymbolTable nametable, - BlockStatementNode bsn) { + private NTuple translateToCaller(MethodInvokeNode min, int paramIdx, + NTuple srcDescTuple) { - switch (bsn.kind()) { + NTuple callerTuple = new NTuple(); - case Kind.DeclarationNode: - assignUniqueIDDeclarationNode(md, nametable, (DeclarationNode) bsn); - break; + NTuple argTuple = mapMethodInvokeNodeToArgIdxMap.get(min).get(paramIdx); - case Kind.IfStatementNode: - assignUniqueIDIfStatementNode(md, nametable, (IfStatementNode) bsn); - break; + for (int i = 0; i < argTuple.size(); i++) { + callerTuple.add(argTuple.get(i)); + } - case Kind.LoopNode: - assignUniqueIDLoopNode(md, nametable, (LoopNode) bsn); - break; + for (int i = 1; i < srcDescTuple.size(); i++) { + callerTuple.add(srcDescTuple.get(i)); + } - case Kind.SubBlockNode: - assignUniqueIDSubBlockNode(md, nametable, (SubBlockNode) bsn); - break; + return callerTuple; + } - case Kind.ContinueBreakNode: - break; + private NTuple translateToCaller(NTuple dstDescTuple, + NTuple baseTuple) { + NTuple callerDescTuple = new NTuple(); - case Kind.SwitchStatementNode: - assignUniqueIDSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn); + callerDescTuple.addAll(baseTuple); + for (int i = 1; i < dstDescTuple.size(); i++) { + callerDescTuple.add(dstDescTuple.get(i)); } + return callerDescTuple; } - private void assignUniqueIDSwitchStatementNode(MethodDescriptor md, SymbolTable nametable, - SwitchStatementNode ssn) { - BlockNode sbn = ssn.getSwitchBody(); - for (int i = 0; i < sbn.size(); i++) { - SwitchBlockNode node = (SwitchBlockNode) sbn.get(i); - assignUniqueIDBlockNode(md, nametable, node.getSwitchBlockStatement()); + 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 assignUniqueIDSubBlockNode(MethodDescriptor md, SymbolTable nametable, - SubBlockNode sbn) { - assignUniqueIDBlockNode(md, nametable, sbn.getBlockNode()); + 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 locTuple = flowNode.getLocTuple(); + + CompositeLocation assignedCompLoc = flowNode.getCompositeLocation(); + CompositeLocation inferredCompLoc; + if (assignedCompLoc != null) { + inferredCompLoc = translateCompositeLocation(assignedCompLoc); + } else { + Location loc = locTuple.get(0); + inferredCompLoc = new CompositeLocation(loc); + } + System.out.println("-paramIdx=" + paramIdx + " infer=" + inferredCompLoc); + methodSummary.addMapParamIdxToInferLoc(paramIdx, inferredCompLoc); + } + + } + } - private void assignUniqueIDLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln) { + private CompositeLocation translateCompositeLocation(CompositeLocation compLoc) { + CompositeLocation newCompLoc = new CompositeLocation(); - if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) { - assignUniqueIDBlockNode(md, nametable, ln.getBody()); - } else { - // check 'for loop' case - BlockNode bn = ln.getInitializer(); - bn.getVarTable().setParent(nametable); - assignUniqueIDBlockNode(md, bn.getVarTable(), ln.getUpdate()); - assignUniqueIDBlockNode(md, bn.getVarTable(), ln.getBody()); + // 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 assignUniqueIDIfStatementNode(MethodDescriptor md, SymbolTable nametable, - IfStatementNode isn) { + private void debug_writeLattices() { - assignUniqueIDBlockNode(md, nametable, isn.getTrueBlock()); + 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"); + } - if (isn.getFalseBlock() != null) { - assignUniqueIDBlockNode(md, nametable, isn.getFalseBlock()); + 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 assignUniqueIDDeclarationNode(MethodDescriptor md, SymbolTable nametable, - DeclarationNode dn) { + private void buildLattice() { - VarDescriptor vd = dn.getVarDescriptor(); - graph.assignUniqueIDtoDescriptor(vd); + 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.getLocTuple().get(0).equals(md.getThis())) { + return true; + } + } + + return false; + } + + private int getParamLocation(String methodStr, String paramStr) { + + String pattern = paramStr + ","; + + int idx = methodStr.indexOf(pattern); + if (idx != -1) { + return idx; + } else { + pattern = paramStr + ")"; + return methodStr.indexOf(pattern); + } + + } + + private String generateVarDeclaration(VarDescriptor varDesc) { + + TypeDescriptor td = varDesc.getType(); + String rtr = td.toString(); + if (td.isArray()) { + for (int i = 0; i < td.getArrayCount(); i++) { + rtr += "[]"; + } + } + rtr += " " + varDesc.getName(); + return rtr; + + } + + private String generateLocationAnnoatation(CompositeLocation loc) { + String rtr = ""; + // method location + Location methodLoc = loc.get(0); + rtr += methodLoc.getLocIdentifier(); + + for (int i = 1; i < loc.getSize(); i++) { + Location element = loc.get(i); + rtr += "," + element.getDescriptor().getSymbol() + "." + element.getLocIdentifier(); + } + + return rtr; + } + + private boolean isParameter(MethodDescriptor md, Descriptor localVarDesc) { + return getFlowGraph(md).isParamDesc(localVarDesc); + } + + private String extractFileName(String fileName) { + int idx = fileName.lastIndexOf("/"); + if (idx == -1) { + return fileName; + } else { + return fileName.substring(idx + 1); + } + + } + + private void codeGen() { + + Set originalFileNameSet = mapFileNameToLineVector.keySet(); + for (Iterator iterator = originalFileNameSet.iterator(); iterator.hasNext();) { + String orgFileName = (String) iterator.next(); + String outputFileName = extractFileName(orgFileName); + + Vector sourceVec = mapFileNameToLineVector.get(orgFileName); + + 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() { + + setupToAnalyze(); + + while (!toAnalyzeIsEmpty()) { + ClassDescriptor cd = toAnalyzeNext(); + setupToAnalazeMethod(cd); + + SSJavaLattice classLattice = cd2lattice.get(cd); + if (classLattice != null) { + System.out.println("@@@check lattice=" + cd); + checkLatticeProperty(cd, classLattice); + } + + while (!toAnalyzeMethodIsEmpty()) { + MethodDescriptor md = toAnalyzeMethodNext(); + SSJavaLattice methodLattice = md2lattice.get(md); + if (methodLattice != null) { + System.out.println("@@@check lattice=" + md); + checkLatticeProperty(md, methodLattice); + } + } + } + + 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(); + } + } + } + + } + + private boolean checkLatticeProperty(Descriptor d, SSJavaLattice lattice) { + // if two elements has the same incoming node set, + // we need to merge two elements ... + + boolean isUpdated; + boolean isModified = false; + do { + isUpdated = removeNodeSharingSameIncomingNodes(d, lattice); + if (!isModified && isUpdated) { + isModified = true; + } + } while (isUpdated); + + return isModified; + } + + private boolean removeNodeSharingSameIncomingNodes(Descriptor d, SSJavaLattice lattice) { + LocationInfo locInfo = getLocationInfo(d); + Map> map = lattice.getIncomingElementMap(); + Set keySet = map.keySet(); + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + String key = (String) iterator.next(); + Set incomingSetKey = map.get(key); + + // System.out.println("key=" + key + " incomingSetKey=" + + // incomingSetKey); + if (incomingSetKey.size() > 0) { + for (Iterator iterator2 = keySet.iterator(); iterator2.hasNext();) { + String cur = (String) iterator2.next(); + if (!cur.equals(key)) { + Set incomingSetCur = map.get(cur); + if (incomingSetCur.equals(incomingSetKey)) { + if (!(incomingSetCur.size() == 1 && incomingSetCur.contains(lattice.getTopItem()))) { + // NEED TO MERGE HERE!!!! + System.out.println("@@@Try merge=" + cur + " " + key); + + Set mergeSet = new HashSet(); + mergeSet.add(cur); + mergeSet.add(key); + + String newMergeLoc = "MLoc" + (SSJavaLattice.seed++); + + System.out.println("---ASSIGN NEW MERGE LOC=" + newMergeLoc + " to " + mergeSet); + lattice.mergeIntoNewLocation(mergeSet, newMergeLoc); + + for (Iterator miterator = mergeSet.iterator(); miterator.hasNext();) { + String oldLocSymbol = (String) miterator.next(); + + Set> inferLocSet = + locInfo.getRelatedInferLocSet(oldLocSymbol); + System.out.println("---update related locations=" + inferLocSet + + " oldLocSymbol=" + oldLocSymbol); + + for (Iterator miterator2 = inferLocSet.iterator(); miterator2.hasNext();) { + Pair pair = + (Pair) miterator2.next(); + Descriptor enclosingDesc = pair.getFirst(); + Descriptor desc = pair.getSecond(); + + System.out.println("---inferLoc pair=" + pair); + + CompositeLocation inferLoc = + getLocationInfo(enclosingDesc).getInferLocation(desc); + System.out.println("oldLoc=" + inferLoc); + // if (curMethodInfo.md.equals(enclosingDesc)) { + // inferLoc = curMethodInfo.getInferLocation(desc); + // } else { + // inferLoc = + // getLocationInfo(enclosingDesc).getInferLocation(desc); + // } + + Location locElement = inferLoc.get(inferLoc.getSize() - 1); + + locElement.setLocIdentifier(newMergeLoc); + locInfo.addMapLocSymbolToRelatedInferLoc(newMergeLoc, enclosingDesc, desc); + + // if (curMethodInfo.md.equals(enclosingDesc)) { + // inferLoc = curMethodInfo.getInferLocation(desc); + // } else { + // inferLoc = + // getLocationInfo(enclosingDesc).getInferLocation(desc); + // } + + inferLoc = getLocationInfo(enclosingDesc).getInferLocation(desc); + System.out.println("---New Infer Loc=" + inferLoc); + + } + + locInfo.removeRelatedInferLocSet(oldLocSymbol, newMergeLoc); + + } + + for (Iterator iterator3 = mergeSet.iterator(); iterator3.hasNext();) { + String oldLoc = (String) iterator3.next(); + lattice.remove(oldLoc); + } + return true; + } + } + } + } + } + + } + return false; + } + + private void checkLattices() { + + LinkedList descriptorListToAnalyze = ssjava.getSortedDescriptors(); + + // current descriptors to visit in fixed-point interprocedural analysis, + // prioritized by + // dependency in the call graph + methodDescriptorsToVisitStack.clear(); + + // descriptorListToAnalyze.removeFirst(); + + Set methodDescriptorToVistSet = new HashSet(); + methodDescriptorToVistSet.addAll(descriptorListToAnalyze); + + while (!descriptorListToAnalyze.isEmpty()) { + MethodDescriptor md = descriptorListToAnalyze.removeFirst(); + checkLatticesOfVirtualMethods(md); + } + + } + + private void debug_writeLatticeDotFile() { + // generate lattice dot file + + setupToAnalyze(); + + while (!toAnalyzeIsEmpty()) { + ClassDescriptor cd = toAnalyzeNext(); + + setupToAnalazeMethod(cd); + + SSJavaLattice classLattice = cd2lattice.get(cd); + if (classLattice != null) { + ssjava.writeLatticeDotFile(cd, null, classLattice); + debug_printDescriptorToLocNameMapping(cd); + } + + while (!toAnalyzeMethodIsEmpty()) { + MethodDescriptor md = toAnalyzeMethodNext(); + SSJavaLattice methodLattice = md2lattice.get(md); + if (methodLattice != null) { + ssjava.writeLatticeDotFile(cd, md, methodLattice); + debug_printDescriptorToLocNameMapping(md); + } + } + } + + } + + private void debug_printDescriptorToLocNameMapping(Descriptor desc) { + + LocationInfo info = getLocationInfo(desc); + System.out.println("## " + desc + " ##"); + System.out.println(info.getMapDescToInferLocation()); + LocationInfo locInfo = getLocationInfo(desc); + System.out.println("mapping=" + locInfo.getMapLocSymbolToDescSet()); + System.out.println("###################"); + + } + + private void inferLattices() { + + // do fixed-point analysis + + 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(); + + // 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); + } + } + + } + + } + + } + + private void calculateExtraLocations() { + LinkedList descriptorListToAnalyze = ssjava.getSortedDescriptors(); + for (Iterator iterator = descriptorListToAnalyze.iterator(); iterator.hasNext();) { + MethodDescriptor md = (MethodDescriptor) iterator.next(); + calculateExtraLocations(md); + } + } + + private void setMethodLocInfo(MethodDescriptor md, MethodLocationInfo methodInfo) { + mapMethodDescToMethodLocationInfo.put(md, methodInfo); + } + + private void checkLatticesOfVirtualMethods(MethodDescriptor md) { + + if (!md.isStatic()) { + Set setPossibleCallees = new HashSet(); + setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md)); + + for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) { + MethodDescriptor mdCallee = (MethodDescriptor) iterator.next(); + if (!md.equals(mdCallee)) { + checkConsistency(md, mdCallee); + } + } + + } + + } + + private void checkConsistency(MethodDescriptor md1, MethodDescriptor md2) { + + // check that two lattice have the same relations between parameters(+PC + // LOC, GLOBAL_LOC RETURN LOC) + + List list1 = new ArrayList(); + List list2 = new ArrayList(); + + MethodLocationInfo locInfo1 = getMethodLocationInfo(md1); + MethodLocationInfo locInfo2 = getMethodLocationInfo(md2); + + Map paramMap1 = locInfo1.getMapParamIdxToInferLoc(); + Map paramMap2 = locInfo2.getMapParamIdxToInferLoc(); + + int numParam = locInfo1.getMapParamIdxToInferLoc().keySet().size(); + + // add location types of paramters + for (int idx = 0; idx < numParam; idx++) { + list1.add(paramMap1.get(Integer.valueOf(idx))); + list2.add(paramMap2.get(Integer.valueOf(idx))); + } + + // add program counter location + list1.add(locInfo1.getPCLoc()); + list2.add(locInfo2.getPCLoc()); + + if (!md1.getReturnType().isVoid()) { + // add return value location + CompositeLocation rtrLoc1 = getMethodLocationInfo(md1).getReturnLoc(); + CompositeLocation rtrLoc2 = getMethodLocationInfo(md2).getReturnLoc(); + list1.add(rtrLoc1); + list2.add(rtrLoc2); + } + + // add global location type + if (md1.isStatic()) { + CompositeLocation globalLoc1 = + new CompositeLocation(new Location(md1, locInfo1.getGlobalLocName())); + CompositeLocation globalLoc2 = + new CompositeLocation(new Location(md2, locInfo2.getGlobalLocName())); + list1.add(globalLoc1); + list2.add(globalLoc2); + } + + for (int i = 0; i < list1.size(); i++) { + CompositeLocation locA1 = list1.get(i); + CompositeLocation locA2 = list2.get(i); + for (int k = 0; k < list1.size(); k++) { + if (i != k) { + CompositeLocation locB1 = list1.get(k); + CompositeLocation locB2 = list2.get(k); + boolean r1 = isGreaterThan(getLattice(md1), locA1, locB1); + + boolean r2 = isGreaterThan(getLattice(md1), locA2, locB2); + + if (r1 != r2) { + throw new Error("The method " + md1 + " is not consistent with the method " + md2 + + ".:: They have a different ordering relation between locations (" + locA1 + "," + + locB1 + ") and (" + locA2 + "," + locB2 + ")."); + } + } + } + } + + } + + private String getSymbol(int idx, FlowNode node) { + Descriptor desc = node.getDescTuple().get(idx); + return desc.getSymbol(); + } + + private Descriptor getDescriptor(int idx, FlowNode node) { + Descriptor desc = node.getDescTuple().get(idx); + 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 = 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)) { + + 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,... + + SSJavaLattice methodLattice = getMethodLattice(md); + MethodLocationInfo methodInfo = getMethodLocationInfo(md); + FlowGraph fg = getFlowGraph(md); + Set nodeSet = fg.getNodeSet(); + + for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) { + FlowNode flowNode = (FlowNode) iterator.next(); + if (flowNode.isDeclaratonNode()) { + CompositeLocation inferLoc = methodInfo.getInferLocation(flowNode.getDescTuple().get(0)); + String locIdentifier = inferLoc.get(0).getLocIdentifier(); + if (!methodLattice.containsKey(locIdentifier)) { + methodLattice.put(locIdentifier); + } + + } + } + + Map mapParamToLoc = methodInfo.getMapParamIdxToInferLoc(); + 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"; + + Set paramInFlowSet = new HashSet(); + + 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); + } + } + + if (paramInFlowSet.size() > 0) { + CompositeLocation lowestLoc = getLowest(methodLattice, paramInFlowSet); + assert (lowestLoc != null); + methodInfo.setPCLoc(lowestLoc); + } + + } + + // 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; + } + } + inferFieldReturnLocSet.add(inferReturnLoc); + + } + } + + if (inferFieldReturnLocSet.size() > 0) { + + 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 = 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)) { + 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)) { + addRelation(methodLattice, methodInfo, inferLoc, returnLocInferLoc); + } + } + + } + + } + } catch (CyclicFlowException e) { + e.printStackTrace(); + } + + } + + private Set getHigherLocSymbolThan(SSJavaLattice lattice, String loc) { + Set higherLocSet = new HashSet(); + + Set locSet = lattice.getTable().keySet(); + for (Iterator iterator = locSet.iterator(); iterator.hasNext();) { + String element = (String) iterator.next(); + if (lattice.isGreaterThan(element, loc) && (!element.equals(lattice.getTopItem()))) { + higherLocSet.add(element); + } + } + return higherLocSet; + } + + private CompositeLocation getLowest(SSJavaLattice methodLattice, + Set set) { + + CompositeLocation lowest = set.iterator().next(); + + if (set.size() == 1) { + return lowest; + } + + for (Iterator iterator = set.iterator(); iterator.hasNext();) { + CompositeLocation loc = (CompositeLocation) iterator.next(); + + 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) { + + int size = comp1.getSize() >= comp2.getSize() ? comp2.getSize() : comp1.getSize(); + + for (int idx = 0; idx < size; idx++) { + Location loc1 = comp1.get(idx); + Location loc2 = comp2.get(idx); + + Descriptor desc1 = loc1.getDescriptor(); + Descriptor desc2 = loc2.getDescriptor(); + + if (!desc1.equals(desc2)) { + throw new Error("Fail to compare " + comp1 + " and " + comp2); + } + + String symbol1 = loc1.getLocIdentifier(); + String symbol2 = loc2.getLocIdentifier(); + + SSJavaLattice lattice; + if (idx == 0) { + lattice = methodLattice; + } else { + lattice = getLattice(desc1); + } + + if (symbol1.equals(symbol2)) { + continue; + } else if (lattice.isGreaterThan(symbol1, symbol2)) { + return true; + } else { + return false; + } + + } + + return false; + } + + private void recursiveAddRelationToLattice(int idx, MethodDescriptor md, + CompositeLocation srcInferLoc, CompositeLocation dstInferLoc) throws CyclicFlowException { + + String srcLocSymbol = srcInferLoc.get(idx).getLocIdentifier(); + String dstLocSymbol = dstInferLoc.get(idx).getLocIdentifier(); + + if (srcLocSymbol.equals(dstLocSymbol)) { + recursiveAddRelationToLattice(idx + 1, md, srcInferLoc, dstInferLoc); + } else { + + Descriptor parentDesc = srcInferLoc.get(idx).getDescriptor(); + LocationInfo locInfo = getLocationInfo(parentDesc); + + addRelationHigherToLower(getLattice(parentDesc), getLocationInfo(parentDesc), srcLocSymbol, + dstLocSymbol); + } + + } + + // private void propagateFlowsFromCallee(MethodInvokeNode min, MethodDescriptor mdCaller, + // MethodDescriptor mdCallee) { + // + // // the transformation for a call site propagates all relations between + // // parameters from the callee + // // if the method is virtual, it also grab all relations from any possible + // // callees + // + // Set 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); + // } + // + // } + + private void contributeCalleeFlows(MethodInvokeNode min, MethodDescriptor mdCaller, + MethodDescriptor mdCallee) { + + System.out.println("\n##contributeCalleeFlows callee=" + mdCallee + "TO caller=" + mdCaller); + + getSubGlobalFlowGraph(mdCallee); + + } + + private FlowGraph 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 + + System.out + .println("-param1=" + paramNode1 + " is higher than param2=" + paramNode2); + System.out.println("-arg1Tuple=" + arg1Tuple + " is higher than arg2Tuple=" + + arg2Tuple); + + if (!min.getMethod().isStatic()) { + // check if this is the case that values flow to/from the + // current object reference 'this' + + NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); + Descriptor baseRef = baseTuple.get(baseTuple.size() - 1); + + System.out.println("paramNode1.getCurrentDescTuple()=" + + paramNode1.getCurrentDescTuple()); + // calculate the prefix of the argument + + 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. + + if (!paramNode1.getCurrentDescTuple().startsWith(mdCallee.getThis())) { + // check whether ??? + + NTuple param1Prefix = + calculatePrefixForParam(callerFlowGraph, calleeFlowGraph, min, arg1Tuple, + paramNode1); + + 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 + + CompositeLocation compLocForParam1 = + generateCompositeLocation(mdCallee, param1Prefix); + + System.out + .println("set comp loc=" + compLocForParam1 + " to " + paramNode1); + paramNode1.setCompositeLocation(compLocForParam1); + + // 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 + + NTuple translatedParamTuple = + translateCompositeLocationToCaller(min, compLocForParam1); + + // TODO : check if the arg >= the tranlated parameter + + System.out.println("add a flow edge= " + arg1Tuple + "->" + + translatedParamTuple); + callerFlowGraph.addValueFlowEdge(arg1Tuple, translatedParamTuple); + + continue; + + } + + } else { + // param1 has already been assigned a composite location + + System.out.println("--param1 has already been assigned a composite location"); + CompositeLocation compLocForParam1 = paramNode1.getCompositeLocation(); + NTuple translatedParamTuple = + translateCompositeLocationToCaller(min, compLocForParam1); + + // TODO : check if the arg >= the tranlated parameter + + System.out.println("add a flow edge= " + arg1Tuple + "->" + + translatedParamTuple); + callerFlowGraph.addValueFlowEdge(arg1Tuple, translatedParamTuple); + + continue; + + } + + } 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. + + System.out.println("###FROM CASE"); + + if (!paramNode2.getCurrentDescTuple().startsWith(mdCallee.getThis())) { + + NTuple param2Prefix = + calculatePrefixForParam(callerFlowGraph, calleeFlowGraph, min, arg2Tuple, + paramNode2); + + 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 compLocForParam2 = + generateCompositeLocation(mdCallee, param2Prefix); + + // System.out.println("set comp loc=" + compLocForParam2 + // + + // " to " + paramNode2); + paramNode1.setCompositeLocation(compLocForParam2); + continue; + } + } + + } + } + + // 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 NTuple translateCompositeLocationToCaller(MethodInvokeNode min, + CompositeLocation compLocForParam1) { + NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); + + NTuple tuple = new NTuple(); + + for (int i = 0; i < baseTuple.size(); i++) { + tuple.add(baseTuple.get(i)); + } + + for (int i = 1; i < compLocForParam1.getSize(); i++) { + Location loc = compLocForParam1.get(i); + tuple.add(loc.getLocDescriptor()); + } + + return tuple; + } + + private CompositeLocation generateCompositeLocation(MethodDescriptor md, + NTuple paramPrefix) { + + System.out.println("generateCompositeLocation=" + paramPrefix); + + CompositeLocation newCompLoc = convertToCompositeLocation(md, paramPrefix); + + 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); + + LocationDescriptor newLocDescriptor = generateNewLocationDescriptor(); + newLocDescriptor.setEnclosingClassDesc(enclosingDescriptor); + + Location newLoc = new Location(enclosingDescriptor, newLocDescriptor.getSymbol()); + newLoc.setLocDescriptor(newLocDescriptor); + newCompLoc.addLocation(newLoc); + + // System.out.println("--newCompLoc=" + newCompLoc); + return newCompLoc; + } + + private NTuple calculatePrefixForParam(FlowGraph callerFlowGraph, + FlowGraph calleeFlowGraph, MethodInvokeNode min, NTuple arg1Tuple, + FlowNode paramNode1) { + + NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); + Descriptor baseRef = baseTuple.get(baseTuple.size() - 1); + System.out.println("baseRef=" + baseRef); + + FlowNode flowNodeArg1 = callerFlowGraph.getFlowNode(arg1Tuple); + List> callerPrefixList = calculatePrefixList(callerFlowGraph, flowNodeArg1); + System.out.println("callerPrefixList=" + callerPrefixList); + + List> prefixList = calculatePrefixList(calleeFlowGraph, paramNode1); + System.out.println("###prefixList from node=" + paramNode1 + " =" + prefixList); + + List> calleePrefixList = + translatePrefixListToCallee(baseRef, min.getMethod(), callerPrefixList); + + System.out.println("calleePrefixList=" + calleePrefixList); + + Set reachNodeSetFromParam1 = calleeFlowGraph.getReachFlowNodeSetFrom(paramNode1); + System.out.println("reachNodeSetFromParam1=" + reachNodeSetFromParam1); + + for (int i = 0; i < calleePrefixList.size(); i++) { + NTuple curPrefix = calleePrefixList.get(i); + Set> reachableCommonPrefixSet = new HashSet>(); + + for (Iterator iterator2 = reachNodeSetFromParam1.iterator(); iterator2.hasNext();) { + FlowNode reachNode = (FlowNode) iterator2.next(); + if (reachNode.getCurrentDescTuple().startsWith(curPrefix)) { + reachableCommonPrefixSet.add(reachNode.getCurrentDescTuple()); + } + } + + if (!reachableCommonPrefixSet.isEmpty()) { + System.out.println("###REACHABLECOMONPREFIX=" + reachableCommonPrefixSet + + " with curPreFix=" + curPrefix); + return curPrefix; + } + + } + + return null; + } + + private List> translatePrefixListToCallee(Descriptor baseRef, + MethodDescriptor mdCallee, List> callerPrefixList) { + + 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); + } + } + + return calleePrefixList; + + } + + private List> calculatePrefixList(FlowGraph flowGraph, FlowNode flowNode) { + + System.out.println("\n##### calculatePrefixList=" + flowNode); + + Set inNodeSet = flowGraph.getIncomingFlowNodeSet(flowNode); + inNodeSet.add(flowNode); + + System.out.println("inNodeSet=" + inNodeSet); + + List> prefixList = new ArrayList>(); + + for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) { + FlowNode inNode = (FlowNode) iterator.next(); + + NTuple inNodeTuple = inNode.getCurrentDescTuple(); + + // CompositeLocation inNodeInferredLoc = + // generateInferredCompositeLocation(methodInfo, inNodeTuple); + // NTuple inNodeInferredLocTuple = inNodeInferredLoc.getTuple(); + + 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; + + } + + public CompositeLocation convertToCompositeLocation(MethodDescriptor md, NTuple tuple) { + + CompositeLocation compLoc = new CompositeLocation(); + + Descriptor enclosingDescriptor = md; + + 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); + + if (curDescriptor instanceof VarDescriptor) { + enclosingDescriptor = md.getClassDesc(); + } else if (curDescriptor instanceof NameDescriptor) { + // it is "GLOBAL LOC" case! + enclosingDescriptor = GLOBALDESC; + } else { + enclosingDescriptor = ((FieldDescriptor) curDescriptor).getClassDescriptor(); + } + + } + + System.out.println("-convertToCompositeLocation from=" + tuple + " to " + compLoc); + + return compLoc; + } + + private LocationDescriptor generateNewLocationDescriptor() { + return new LocationDescriptor("Loc" + (locSeed++)); + } + + private int getPrefixIndex(NTuple tuple1, NTuple tuple2) { + + // 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(); + } + + int idx = -1; + for (int i = 0; i < minSize; i++) { + if (!tuple1.get(i).equals(tuple2.get(i))) { + break; + } else { + idx++; + } + } + + return idx; + } + + private void analyzeLatticeMethodInvocationNode(MethodDescriptor mdCaller, + SSJavaLattice methodLattice, MethodLocationInfo methodInfo) + throws CyclicFlowException { + + // the transformation for a call site propagates all relations between + // parameters from the callee + // if the method is virtual, it also grab all relations from any possible + // callees + + Set setMethodInvokeNode = + mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller); + + if (setMethodInvokeNode != null) { + + for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) { + MethodInvokeNode min = (MethodInvokeNode) iterator.next(); + MethodDescriptor mdCallee = min.getMethod(); + Set setPossibleCallees = new HashSet(); + if (mdCallee.isStatic()) { + setPossibleCallees.add(mdCallee); + } else { + Set calleeSet = ssjava.getCallGraph().getMethods(mdCallee); + // removes method descriptors that are not invoked by the caller + calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller)); + setPossibleCallees.addAll(calleeSet); + } + + for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) { + MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next(); + propagateRelationToCaller(min, mdCaller, possibleMdCallee, methodLattice, methodInfo); + } + + } + } + + } + + private void propagateRelationToCaller(MethodInvokeNode min, MethodDescriptor mdCaller, + MethodDescriptor possibleMdCallee, SSJavaLattice methodLattice, + MethodLocationInfo methodInfo) throws CyclicFlowException { + + SSJavaLattice calleeLattice = getMethodLattice(possibleMdCallee); + MethodLocationInfo calleeLocInfo = getMethodLocationInfo(possibleMdCallee); + FlowGraph calleeFlowGraph = getFlowGraph(possibleMdCallee); + + int numParam = calleeLocInfo.getNumParam(); + for (int i = 0; i < numParam; i++) { + CompositeLocation param1 = calleeLocInfo.getParamCompositeLocation(i); + for (int k = 0; k < numParam; k++) { + if (i != k) { + CompositeLocation param2 = calleeLocInfo.getParamCompositeLocation(k); + + if (isGreaterThan(getLattice(possibleMdCallee), param1, param2)) { + // NodeTupleSet argDescTupleSet1 = getNodeTupleSetByArgIdx(min, i); + // NodeTupleSet argDescTupleSet2 = getNodeTupleSetByArgIdx(min, k); + NodeTupleSet argDescTupleSet1 = null; + NodeTupleSet argDescTupleSet2 = null; + + // 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(); + + for (Iterator> iterator2 = argDescTupleSet2.iterator(); iterator2 + .hasNext();) { + NTuple argDescTuple2 = iterator2.next(); + + // retreive inferred location by the local var descriptor + + NTuple tuple1 = getFlowGraph(mdCaller).getLocationTuple(argDescTuple1); + NTuple tuple2 = getFlowGraph(mdCaller).getLocationTuple(argDescTuple2); + + // CompositeLocation higherInferLoc = + // methodInfo.getInferLocation(argTuple1.get(0)); + // CompositeLocation lowerInferLoc = + // methodInfo.getInferLocation(argTuple2.get(0)); + + CompositeLocation inferLoc1 = generateInferredCompositeLocation(methodInfo, tuple1); + CompositeLocation inferLoc2 = generateInferredCompositeLocation(methodInfo, tuple2); + + // addRelation(methodLattice, methodInfo, inferLoc1, inferLoc2); + + addFlowGraphEdge(mdCaller, argDescTuple1, argDescTuple2); + + } + + } + + } + } + } + } + + } + + private CompositeLocation generateInferredCompositeLocation(MethodLocationInfo methodInfo, + NTuple tuple) { + + // first, retrieve inferred location by the local var descriptor + CompositeLocation inferLoc = new CompositeLocation(); + + CompositeLocation localVarInferLoc = + methodInfo.getInferLocation(tuple.get(0).getLocDescriptor()); + + localVarInferLoc.get(0).setLocDescriptor(tuple.get(0).getLocDescriptor()); + + for (int i = 0; i < localVarInferLoc.getSize(); i++) { + inferLoc.addLocation(localVarInferLoc.get(i)); + } + + 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); + + } + + assert (inferLoc.get(0).getLocDescriptor().getSymbol() == inferLoc.get(0).getLocIdentifier()); + return inferLoc; + } + + private void addRelation(SSJavaLattice methodLattice, MethodLocationInfo methodInfo, + CompositeLocation srcInferLoc, CompositeLocation dstInferLoc) throws CyclicFlowException { + + System.out.println("addRelation --- srcInferLoc=" + srcInferLoc + " dstInferLoc=" + + dstInferLoc); + String srcLocalLocSymbol = srcInferLoc.get(0).getLocIdentifier(); + String dstLocalLocSymbol = dstInferLoc.get(0).getLocIdentifier(); + + if (srcInferLoc.getSize() == 1 && dstInferLoc.getSize() == 1) { + // add a new relation to the local lattice + addRelationHigherToLower(methodLattice, methodInfo, srcLocalLocSymbol, dstLocalLocSymbol); + } else if (srcInferLoc.getSize() > 1 && dstInferLoc.getSize() > 1) { + // both src and dst have assigned to a composite location + + if (!srcLocalLocSymbol.equals(dstLocalLocSymbol)) { + addRelationHigherToLower(methodLattice, methodInfo, srcLocalLocSymbol, dstLocalLocSymbol); + } else { + recursivelyAddRelation(1, srcInferLoc, dstInferLoc); + } + } else { + // either src or dst has assigned to a composite location + if (!srcLocalLocSymbol.equals(dstLocalLocSymbol)) { + addRelationHigherToLower(methodLattice, methodInfo, srcLocalLocSymbol, dstLocalLocSymbol); + } + } + + System.out.println(); + + } + + public LocationInfo getLocationInfo(Descriptor d) { + if (d instanceof MethodDescriptor) { + return getMethodLocationInfo((MethodDescriptor) d); + } else { + return getFieldLocationInfo((ClassDescriptor) d); + } + } + + private MethodLocationInfo getMethodLocationInfo(MethodDescriptor md) { + + if (!mapMethodDescToMethodLocationInfo.containsKey(md)) { + mapMethodDescToMethodLocationInfo.put(md, new MethodLocationInfo(md)); + } + + return mapMethodDescToMethodLocationInfo.get(md); + + } + + private LocationInfo getFieldLocationInfo(ClassDescriptor cd) { + + if (!mapClassToLocationInfo.containsKey(cd)) { + mapClassToLocationInfo.put(cd, new LocationInfo(cd)); + } + + return mapClassToLocationInfo.get(cd); + + } + + private void addRelationToLattice(MethodDescriptor md, SSJavaLattice methodLattice, + MethodLocationInfo methodInfo, FlowNode srcNode, FlowNode dstNode) throws CyclicFlowException { + + System.out.println(); + System.out.println("### addRelationToLattice src=" + srcNode + " dst=" + dstNode); + + // add a new binary relation of dstNode < srcNode + FlowGraph flowGraph = getFlowGraph(md); + try { + System.out.println("***** src composite case::"); + calculateCompositeLocation(flowGraph, methodLattice, methodInfo, srcNode, null); + + 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, srcNode); + CompositeLocation srcInferLoc = + generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(srcNode)); + CompositeLocation dstInferLoc = + generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(dstNode)); + try { + addRelation(methodLattice, methodInfo, srcInferLoc, dstInferLoc); + } catch (CyclicFlowException e1) { + throw new Error("Failed to merge cyclic value flows into a shared location."); + } + } + + } + + private void recursivelyAddRelation(int idx, CompositeLocation srcInferLoc, + CompositeLocation dstInferLoc) throws CyclicFlowException { + + String srcLocSymbol = srcInferLoc.get(idx).getLocIdentifier(); + String dstLocSymbol = dstInferLoc.get(idx).getLocIdentifier(); + + 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); + } + } + + private void recursivelyAddCompositeRelation(MethodDescriptor md, FlowGraph flowGraph, + MethodLocationInfo methodInfo, FlowNode srcNode, FlowNode dstNode, Descriptor srcDesc, + Descriptor dstDesc) throws CyclicFlowException { + + CompositeLocation inferSrcLoc; + CompositeLocation inferDstLoc = methodInfo.getInferLocation(dstDesc); + + if (srcNode.getLocTuple().size() > 1) { + // field access + inferSrcLoc = new CompositeLocation(); + + NTuple locTuple = flowGraph.getLocationTuple(srcNode); + for (int i = 0; i < locTuple.size(); i++) { + inferSrcLoc.addLocation(locTuple.get(i)); + } + + } else { + inferSrcLoc = methodInfo.getInferLocation(srcDesc); + } + + if (dstNode.getLocTuple().size() > 1) { + // field access + inferDstLoc = new CompositeLocation(); + + NTuple locTuple = flowGraph.getLocationTuple(dstNode); + for (int i = 0; i < locTuple.size(); i++) { + inferDstLoc.addLocation(locTuple.get(i)); + } + + } else { + inferDstLoc = methodInfo.getInferLocation(dstDesc); + } + + recursiveAddRelationToLattice(1, md, inferSrcLoc, inferDstLoc); + } + + private void addPrefixMapping(Map, Set>> map, + NTuple prefix, NTuple element) { + + if (!map.containsKey(prefix)) { + map.put(prefix, new HashSet>()); + } + map.get(prefix).add(element); + } + + private boolean calculateCompositeLocation(FlowGraph flowGraph, + SSJavaLattice methodLattice, MethodLocationInfo methodInfo, FlowNode flowNode, + FlowNode srcNode) throws CyclicFlowException { + + Descriptor localVarDesc = flowNode.getDescTuple().get(0); + NTuple flowNodelocTuple = flowGraph.getLocationTuple(flowNode); + + if (localVarDesc.equals(methodInfo.getMethodDesc())) { + return false; + } + + Set inNodeSet = flowGraph.getIncomingFlowNodeSet(flowNode); + Set reachableNodeSet = flowGraph.getReachFlowNodeSetFrom(flowNode); + + Map, Set>> mapPrefixToIncomingLocTupleSet = + new HashMap, Set>>(); + + List> prefixList = new ArrayList>(); + + for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) { + FlowNode inNode = (FlowNode) iterator.next(); + NTuple inNodeTuple = flowGraph.getLocationTuple(inNode); + + CompositeLocation inNodeInferredLoc = + generateInferredCompositeLocation(methodInfo, inNodeTuple); + + NTuple inNodeInferredLocTuple = inNodeInferredLoc.getTuple(); + + for (int i = 1; i < inNodeInferredLocTuple.size(); i++) { + NTuple prefix = inNodeInferredLocTuple.subList(0, i); + if (!prefixList.contains(prefix)) { + prefixList.add(prefix); + } + addPrefixMapping(mapPrefixToIncomingLocTupleSet, prefix, inNodeInferredLocTuple); + } + } + + 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; + } + } + }); + + // 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); + + 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); + + // TODO: refactoring! + if (srcNode != null) { + CompositeLocation newLoc = new CompositeLocation(); + String newLocSymbol = "Loc" + (SSJavaLattice.seed++); + for (int locIdx = 0; locIdx < curPrefix.size(); locIdx++) { + newLoc.addLocation(curPrefix.get(locIdx)); + } + Location newLocationElement = new Location(desc, newLocSymbol); + newLoc.addLocation(newLocationElement); + + Descriptor srcLocalVar = srcNode.getDescTuple().get(0); + methodInfo.mapDescriptorToLocation(srcLocalVar, newLoc.clone()); + addMapLocSymbolToInferredLocation(methodInfo.getMethodDesc(), srcLocalVar, newLoc); + methodInfo.removeMaplocalVarToLocSet(srcLocalVar); + + // add the field/var descriptor to the set of the location symbol + int lastIdx = srcNode.getLocTuple().size() - 1; + Descriptor lastFlowNodeDesc = srcNode.getDescTuple().get(lastIdx); + NTuple srcNodelocTuple = flowGraph.getLocationTuple(srcNode); + Descriptor enclosinglastLastFlowNodeDesc = srcNodelocTuple.get(lastIdx).getDescriptor(); + + CompositeLocation newlyInferredLocForFlowNode = + generateInferredCompositeLocation(methodInfo, srcNodelocTuple); + Location lastInferLocElement = + newlyInferredLocForFlowNode.get(newlyInferredLocForFlowNode.getSize() - 1); + Descriptor enclosingLastInferLocElement = lastInferLocElement.getDescriptor(); + + // getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToDescSet( + // lastInferLocElement.getLocIdentifier(), lastFlowNodeDesc); + getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToRelatedInferLoc( + lastInferLocElement.getLocIdentifier(), enclosinglastLastFlowNodeDesc, + lastFlowNodeDesc); + + System.out.println("@@@@@@@ ASSIGN " + newLoc + " to SRC=" + srcNode); + } + + 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.getLocTuple().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); + + String newlyInsertedLocName = + newInferLocation.get(newInferLocation.getSize() - 1).getLocIdentifier(); + + System.out.println("-- add in-flow"); + for (Iterator iterator = incomingCommonPrefixSet.iterator(); iterator.hasNext();) { + NTuple tuple = (NTuple) iterator.next(); + Location loc = tuple.get(idx); + String higher = loc.getLocIdentifier(); + addRelationHigherToLower(lattice, locInfo, higher, newlyInsertedLocName); + } + + 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); + } + } + + return true; + } + + } + + return false; + + } + + private void addMapLocSymbolToInferredLocation(MethodDescriptor md, Descriptor localVar, + CompositeLocation inferLoc) { + + Location locElement = inferLoc.get((inferLoc.getSize() - 1)); + Descriptor enclosingDesc = locElement.getDescriptor(); + LocationInfo locInfo = getLocationInfo(enclosingDesc); + locInfo.addMapLocSymbolToRelatedInferLoc(locElement.getLocIdentifier(), md, localVar); + } + + private boolean isCompositeLocation(CompositeLocation cl) { + return cl.getSize() > 1; + } + + private boolean containsNonPrimitiveElement(Set descSet) { + for (Iterator iterator = descSet.iterator(); iterator.hasNext();) { + Descriptor desc = (Descriptor) iterator.next(); + + if (desc.equals(LocationInference.GLOBALDESC)) { + return true; + } else if (desc instanceof VarDescriptor) { + if (!((VarDescriptor) desc).getType().isPrimitive()) { + return true; + } + } else if (desc instanceof FieldDescriptor) { + if (!((FieldDescriptor) desc).getType().isPrimitive()) { + return true; + } + } + + } + return false; + } + + private void addRelationHigherToLower(SSJavaLattice lattice, LocationInfo locInfo, + String higher, String lower) throws CyclicFlowException { + + System.out.println("---addRelationHigherToLower " + higher + " -> " + lower + + " to the lattice of " + locInfo.getDescIdentifier()); + // if (higher.equals(lower) && lattice.isSharedLoc(higher)) { + // return; + // } + Set cycleElementSet = lattice.getPossibleCycleElements(higher, lower); + + boolean hasNonPrimitiveElement = false; + for (Iterator iterator = cycleElementSet.iterator(); iterator.hasNext();) { + String cycleElementLocSymbol = (String) iterator.next(); + + Set descSet = locInfo.getDescSet(cycleElementLocSymbol); + if (containsNonPrimitiveElement(descSet)) { + hasNonPrimitiveElement = true; + break; + } + } + + if (hasNonPrimitiveElement) { + System.out.println("#Check cycle= " + lower + " < " + higher + " cycleElementSet=" + + cycleElementSet); + // if there is non-primitive element in the cycle, no way to merge cyclic + // elements into the shared location + throw new CyclicFlowException(); + } + + if (cycleElementSet.size() > 0) { + + String newSharedLoc = "SharedLoc" + (SSJavaLattice.seed++); + + System.out.println("---ASSIGN NEW SHARED LOC=" + newSharedLoc + " to " + cycleElementSet); + lattice.mergeIntoNewLocation(cycleElementSet, newSharedLoc); + lattice.addSharedLoc(newSharedLoc); + + for (Iterator iterator = cycleElementSet.iterator(); iterator.hasNext();) { + String oldLocSymbol = (String) iterator.next(); + + Set> inferLocSet = locInfo.getRelatedInferLocSet(oldLocSymbol); + System.out.println("---update related locations=" + inferLocSet); + for (Iterator iterator2 = inferLocSet.iterator(); iterator2.hasNext();) { + Pair pair = (Pair) iterator2.next(); + Descriptor enclosingDesc = pair.getFirst(); + Descriptor desc = pair.getSecond(); + + CompositeLocation inferLoc; + if (curMethodInfo.md.equals(enclosingDesc)) { + inferLoc = curMethodInfo.getInferLocation(desc); + } else { + inferLoc = getLocationInfo(enclosingDesc).getInferLocation(desc); + } + + Location locElement = inferLoc.get(inferLoc.getSize() - 1); + + locElement.setLocIdentifier(newSharedLoc); + locInfo.addMapLocSymbolToRelatedInferLoc(newSharedLoc, enclosingDesc, desc); + + if (curMethodInfo.md.equals(enclosingDesc)) { + inferLoc = curMethodInfo.getInferLocation(desc); + } else { + inferLoc = getLocationInfo(enclosingDesc).getInferLocation(desc); + } + System.out.println("---New Infer Loc=" + inferLoc); + + } + locInfo.removeRelatedInferLocSet(oldLocSymbol, newSharedLoc); + + } + + lattice.addSharedLoc(newSharedLoc); + + } else if (!lattice.isGreaterThan(higher, lower)) { + lattice.addRelationHigherToLower(higher, lower); + } + } + + private void replaceOldLocWithNewLoc(SSJavaLattice methodLattice, String oldLocSymbol, + String newLocSymbol) { + + if (methodLattice.containsKey(oldLocSymbol)) { + methodLattice.substituteLocation(oldLocSymbol, newLocSymbol); + } + + } + + public boolean isPrimitiveLocalVariable(FlowNode node) { + VarDescriptor varDesc = (VarDescriptor) node.getDescTuple().get(0); + return varDesc.getType().isPrimitive(); + } + + private SSJavaLattice getLattice(Descriptor d) { + if (d instanceof MethodDescriptor) { + return getMethodLattice((MethodDescriptor) d); + } else { + return getFieldLattice((ClassDescriptor) d); + } + } + + private SSJavaLattice getMethodLattice(MethodDescriptor md) { + if (!md2lattice.containsKey(md)) { + md2lattice.put(md, new SSJavaLattice(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM)); + } + return md2lattice.get(md); + } + + private void setMethodLattice(MethodDescriptor md, SSJavaLattice lattice) { + md2lattice.put(md, lattice); + } + + private void extractFlowsBetweenFields(ClassDescriptor cd, FlowNode srcNode, FlowNode dstNode, + int idx) { + + 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 = srcCurTuple.get(idx); + ClassDescriptor classDesc; + + if (idx == 0) { + classDesc = ((VarDescriptor) desc).getType().getClassDesc(); + } else { + classDesc = ((FieldDescriptor) desc).getType().getClassDesc(); + } + + extractFlowsBetweenFields(classDesc, srcNode, dstNode, idx + 1); + + } else { + + Descriptor srcFieldDesc = srcCurTuple.get(idx); + Descriptor dstFieldDesc = dstCurTuple.get(idx); + + // add a new edge + getHierarchyGraph(cd).addEdge(srcFieldDesc, dstFieldDesc); + + } + + } + + private void extractRelationFromFieldFlows(ClassDescriptor cd, FlowNode srcNode, + FlowNode dstNode, int idx) throws CyclicFlowException { + + if (srcNode.getLocTuple().get(idx).equals(dstNode.getLocTuple().get(idx)) + && srcNode.getLocTuple().size() > (idx + 1) && dstNode.getLocTuple().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); + ClassDescriptor classDesc; + + if (idx == 0) { + classDesc = ((VarDescriptor) desc).getType().getClassDesc(); + } else { + classDesc = ((FieldDescriptor) desc).getType().getClassDesc(); + } + + extractRelationFromFieldFlows(classDesc, srcNode, dstNode, idx + 1); + + } else { + + Descriptor srcFieldDesc = srcNode.getDescTuple().get(idx); + Descriptor dstFieldDesc = dstNode.getDescTuple().get(idx); + + // add a new binary relation of dstNode < srcNode + SSJavaLattice fieldLattice = getFieldLattice(cd); + LocationInfo fieldInfo = getFieldLocationInfo(cd); + + String srcSymbol = fieldInfo.getFieldInferLocation(srcFieldDesc).getLocIdentifier(); + String dstSymbol = fieldInfo.getFieldInferLocation(dstFieldDesc).getLocIdentifier(); + + addRelationHigherToLower(fieldLattice, fieldInfo, srcSymbol, dstSymbol); + + } + + } + + public SSJavaLattice getFieldLattice(ClassDescriptor cd) { + if (!cd2lattice.containsKey(cd)) { + cd2lattice.put(cd, new SSJavaLattice(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM)); + } + return cd2lattice.get(cd); + } + + public LinkedList computeMethodList() { + + Set toSort = new HashSet(); + + setupToAnalyze(); + + Set visited = new HashSet(); + Set reachableCallee = new HashSet(); + + while (!toAnalyzeIsEmpty()) { + ClassDescriptor cd = toAnalyzeNext(); + + setupToAnalazeMethod(cd); + temp_toanalyzeMethodList.removeAll(visited); + + while (!toAnalyzeMethodIsEmpty()) { + MethodDescriptor md = toAnalyzeMethodNext(); + if ((!visited.contains(md)) + && (ssjava.needTobeAnnotated(md) || reachableCallee.contains(md))) { + + // creates a mapping from a method descriptor to virtual methods + Set setPossibleCallees = new HashSet(); + if (md.isStatic()) { + setPossibleCallees.add(md); + } else { + setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md)); + } + + Set calleeSet = ssjava.getCallGraph().getCalleeSet(md); + Set needToAnalyzeCalleeSet = new HashSet(); + + for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) { + MethodDescriptor calleemd = (MethodDescriptor) iterator.next(); + if ((!ssjava.isTrustMethod(calleemd)) + && (!ssjava.isSSJavaUtil(calleemd.getClassDesc()))) { + if (!visited.contains(calleemd)) { + temp_toanalyzeMethodList.add(calleemd); + } + reachableCallee.add(calleemd); + needToAnalyzeCalleeSet.add(calleemd); + } + } + + mapMethodToCalleeSet.put(md, needToAnalyzeCalleeSet); + + visited.add(md); + + toSort.add(md); + } + } + } + + return ssjava.topologicalSort(toSort); + + } + + public void constructFlowGraph() { + + 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(); + if (state.SSJAVADEBUG) { + System.out.println(); + System.out.println("SSJAVA: Constructing a flow graph: " + md); + + // creates a mapping from a parameter descriptor to its index + Map mapParamDescToIdx = new HashMap(); + int offset = 0; + if (!md.isStatic()) { + offset = 1; + mapParamDescToIdx.put(md.getThis(), 0); + } + + for (int i = 0; i < md.numParameters(); i++) { + Descriptor paramDesc = (Descriptor) md.getParameter(i); + mapParamDescToIdx.put(paramDesc, new Integer(i + offset)); + } + + FlowGraph fg = new FlowGraph(md, mapParamDescToIdx); + mapMethodDescriptorToFlowGraph.put(md, fg); + + analyzeMethodBody(md.getClassDesc(), md); + 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); + } + + } + } + + } + + private void analyzeMethodBody(ClassDescriptor cd, MethodDescriptor md) { + BlockNode bn = state.getMethodBody(md); + NodeTupleSet implicitFlowTupleSet = new NodeTupleSet(); + analyzeFlowBlockNode(md, md.getParameterTable(), bn, implicitFlowTupleSet); + } + + private void analyzeFlowBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn, + NodeTupleSet implicitFlowTupleSet) { + + bn.getVarTable().setParent(nametable); + for (int i = 0; i < bn.size(); i++) { + BlockStatementNode bsn = bn.get(i); + analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet); + } + + } + + private void analyzeBlockStatementNode(MethodDescriptor md, SymbolTable nametable, + BlockStatementNode bsn, NodeTupleSet implicitFlowTupleSet) { + + switch (bsn.kind()) { + case Kind.BlockExpressionNode: + analyzeBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn, implicitFlowTupleSet); + break; + + case Kind.DeclarationNode: + analyzeFlowDeclarationNode(md, nametable, (DeclarationNode) bsn, implicitFlowTupleSet); + break; + + case Kind.IfStatementNode: + analyzeFlowIfStatementNode(md, nametable, (IfStatementNode) bsn, implicitFlowTupleSet); + break; + + case Kind.LoopNode: + analyzeFlowLoopNode(md, nametable, (LoopNode) bsn, implicitFlowTupleSet); + break; + + case Kind.ReturnNode: + analyzeFlowReturnNode(md, nametable, (ReturnNode) bsn, implicitFlowTupleSet); + break; + + case Kind.SubBlockNode: + analyzeFlowSubBlockNode(md, nametable, (SubBlockNode) bsn, implicitFlowTupleSet); + break; + + case Kind.ContinueBreakNode: + break; + + case Kind.SwitchStatementNode: + 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 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(md).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, + SubBlockNode sbn, NodeTupleSet implicitFlowTupleSet) { + analyzeFlowBlockNode(md, nametable, sbn.getBlockNode(), implicitFlowTupleSet); + } + + private void analyzeFlowReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode rn, + NodeTupleSet implicitFlowTupleSet) { + + ExpressionNode returnExp = rn.getReturnExpression(); + + 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); + + // 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(md); + 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); + } + + } + + } + + private void analyzeFlowLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln, + NodeTupleSet implicitFlowTupleSet) { + + if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) { + + NodeTupleSet condTupleNode = new NodeTupleSet(); + analyzeFlowExpressionNode(md, nametable, ln.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(md).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); + + } else { + // check 'for loop' case + BlockNode bn = ln.getInitializer(); + bn.getVarTable().setParent(nametable); + for (int i = 0; i < bn.size(); i++) { + BlockStatementNode bsn = bn.get(i); + analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet); + } + + NodeTupleSet condTupleNode = new NodeTupleSet(); + analyzeFlowExpressionNode(md, bn.getVarTable(), ln.getCondition(), condTupleNode, null, + implicitFlowTupleSet, false); + + // /////////// + NTuple interTuple = getFlowGraph(md).createIntermediateNode(md).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); + + } + + } + + 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); + + 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(md).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(), newImplicitTupleSet); + } + + } + + private void analyzeFlowDeclarationNode(MethodDescriptor md, SymbolTable nametable, + DeclarationNode dn, NodeTupleSet implicitFlowTupleSet) { + + VarDescriptor vd = dn.getVarDescriptor(); + mapDescToDefinitionLine.put(vd, dn.getNumLine()); + NTuple tupleLHS = new NTuple(); + tupleLHS.add(vd); + FlowNode fn = getFlowGraph(md).createNewFlowNode(tupleLHS); + fn.setDeclarationNode(); + + if (dn.getExpression() != null) { + + NodeTupleSet nodeSetRHS = new NodeTupleSet(); + analyzeFlowExpressionNode(md, nametable, dn.getExpression(), nodeSetRHS, null, + implicitFlowTupleSet, false); + + // creates edges from RHS to LHS + NTuple interTuple = null; + if (nodeSetRHS.size() > 1) { + interTuple = getFlowGraph(md).createIntermediateNode(md).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); + } + + } + + } + + private void analyzeBlockExpressionNode(MethodDescriptor md, SymbolTable nametable, + BlockExpressionNode ben, NodeTupleSet implicitFlowTupleSet) { + analyzeFlowExpressionNode(md, nametable, ben.getExpression(), null, null, implicitFlowTupleSet, + false); + } + + private NTuple analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable, + ExpressionNode en, NodeTupleSet nodeSet, boolean isLHS) { + return analyzeFlowExpressionNode(md, nametable, en, nodeSet, null, new NodeTupleSet(), isLHS); + } + + private NTuple analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable, + ExpressionNode en, NodeTupleSet nodeSet, NTuple base, + NodeTupleSet implicitFlowTupleSet, boolean isLHS) { + + // note that expression node can create more than one flow node + // nodeSet contains of flow nodes + // base is always assigned to null except the case of a name node! + + NTuple flowTuple; + + switch (en.kind()) { + + case Kind.AssignmentNode: + analyzeFlowAssignmentNode(md, nametable, (AssignmentNode) en, nodeSet, base, + implicitFlowTupleSet); + break; + + case Kind.FieldAccessNode: + flowTuple = + analyzeFlowFieldAccessNode(md, nametable, (FieldAccessNode) en, nodeSet, base, + implicitFlowTupleSet, isLHS); + if (flowTuple != null) { + nodeSet.addTuple(flowTuple); + } + return flowTuple; + + case Kind.NameNode: + NodeTupleSet nameNodeSet = new NodeTupleSet(); + flowTuple = + analyzeFlowNameNode(md, nametable, (NameNode) en, nameNodeSet, base, implicitFlowTupleSet); + if (flowTuple != null) { + nodeSet.addTuple(flowTuple); + } + return flowTuple; + + case Kind.OpNode: + analyzeFlowOpNode(md, nametable, (OpNode) en, nodeSet, implicitFlowTupleSet); + break; + + case Kind.CreateObjectNode: + analyzeCreateObjectNode(md, nametable, (CreateObjectNode) en); + break; + + case Kind.ArrayAccessNode: + analyzeFlowArrayAccessNode(md, nametable, (ArrayAccessNode) en, nodeSet, isLHS); + break; + + case Kind.LiteralNode: + analyzeLiteralNode(md, nametable, (LiteralNode) en); + break; + + case Kind.MethodInvokeNode: + analyzeFlowMethodInvokeNode(md, nametable, (MethodInvokeNode) en, nodeSet, + implicitFlowTupleSet); + break; + + case Kind.TertiaryNode: + analyzeFlowTertiaryNode(md, nametable, (TertiaryNode) en, nodeSet, implicitFlowTupleSet); + break; + + case Kind.CastNode: + analyzeFlowCastNode(md, nametable, (CastNode) en, nodeSet, base, implicitFlowTupleSet); + break; + // case Kind.InstanceOfNode: + // checkInstanceOfNode(md, nametable, (InstanceOfNode) en, td); + // return null; + + // case Kind.ArrayInitializerNode: + // checkArrayInitializerNode(md, nametable, (ArrayInitializerNode) en, + // td); + // return null; + + // case Kind.ClassTypeNode: + // checkClassTypeNode(md, nametable, (ClassTypeNode) en, td); + // return null; + + // case Kind.OffsetNode: + // checkOffsetNode(md, nametable, (OffsetNode)en, td); + // return null; + + } + return null; + + } + + private void analyzeFlowCastNode(MethodDescriptor md, SymbolTable nametable, CastNode cn, + NodeTupleSet nodeSet, NTuple base, NodeTupleSet implicitFlowTupleSet) { + + analyzeFlowExpressionNode(md, nametable, cn.getExpression(), nodeSet, base, + implicitFlowTupleSet, false); + + } + + private void analyzeFlowTertiaryNode(MethodDescriptor md, SymbolTable nametable, TertiaryNode tn, + NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) { + + NodeTupleSet tertiaryTupleNode = new NodeTupleSet(); + analyzeFlowExpressionNode(md, nametable, tn.getCond(), tertiaryTupleNode, null, + implicitFlowTupleSet, false); + + // add edges from tertiaryTupleNode to all nodes of conditional nodes + tertiaryTupleNode.addTupleSet(implicitFlowTupleSet); + analyzeFlowExpressionNode(md, nametable, tn.getTrueExpr(), tertiaryTupleNode, null, + implicitFlowTupleSet, false); + + analyzeFlowExpressionNode(md, nametable, tn.getFalseExpr(), tertiaryTupleNode, null, + implicitFlowTupleSet, false); + + nodeSet.addTupleSet(tertiaryTupleNode); + + } + + private void addMapCallerMethodDescToMethodInvokeNodeSet(MethodDescriptor caller, + MethodInvokeNode min) { + Set set = mapMethodDescriptorToMethodInvokeNodeSet.get(caller); + if (set == null) { + set = new HashSet(); + mapMethodDescriptorToMethodInvokeNodeSet.put(caller, set); + } + set.add(min); + } + + private void addParamNodeFlowingToReturnValue(MethodDescriptor md, FlowNode fn) { + + if (!mapMethodDescToParamNodeFlowsToReturnValue.containsKey(md)) { + mapMethodDescToParamNodeFlowsToReturnValue.put(md, new HashSet()); + } + mapMethodDescToParamNodeFlowsToReturnValue.get(md).add(fn); + } + + private Set getParamNodeFlowingToReturnValue(MethodDescriptor md) { + return mapMethodDescToParamNodeFlowsToReturnValue.get(md); + } + + private void analyzeFlowMethodInvokeNode(MethodDescriptor md, SymbolTable nametable, + MethodInvokeNode min, NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) { + + if (nodeSet == null) { + nodeSet = new NodeTupleSet(); + } + + MethodDescriptor calleeMethodDesc = min.getMethod(); + + NameDescriptor baseName = min.getBaseName(); + boolean isSystemout = false; + if (baseName != null) { + isSystemout = baseName.getSymbol().equals("System.out"); + } + + 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, baseTuple); + + for (Iterator iterator = calleeReturnSet.iterator(); iterator.hasNext();) { + FlowNode returnNode = (FlowNode) iterator.next(); + NTuple returnDescTuple = returnNode.getDescTuple(); + if (returnDescTuple.startsWith(calleeMethodDesc.getThis())) { + // the location type of the return value is started with 'this' + // reference + NTuple inFlowTuple = new NTuple(baseTuple.getList()); + inFlowTuple.addAll(returnDescTuple.subList(1, returnDescTuple.size())); + nodeSet.addTuple(inFlowTuple); + } else { + // TODO + Set inFlowSet = calleeFlowGraph.getIncomingFlowNodeSet(returnNode); + for (Iterator iterator2 = inFlowSet.iterator(); iterator2.hasNext();) { + FlowNode inFlowNode = (FlowNode) iterator2.next(); + if (inFlowNode.getDescTuple().startsWith(calleeMethodDesc.getThis())) { + nodeSet.addTupleSet(baseNodeSet); + } + } + } + } + } + + } + + // analyze parameter flows + + if (min.numArgs() > 0) { + + int offset; + if (min.getMethod().isStatic()) { + offset = 0; + } else { + offset = 1; + } + + for (int i = 0; i < min.numArgs(); i++) { + ExpressionNode en = min.getArg(i); + int idx = i + offset; + NodeTupleSet argTupleSet = new NodeTupleSet(); + analyzeFlowExpressionNode(md, nametable, en, argTupleSet, false); + // if argument is liternal node, argTuple is set to NULL. + + NTuple argTuple = new NTuple(); + if (argTupleSet.size() > 1) { + NTuple interTuple = + getFlowGraph(md).createIntermediateNode(md).getDescTuple(); + for (Iterator> idxIter = argTupleSet.iterator(); idxIter.hasNext();) { + NTuple tuple = idxIter.next(); + addFlowGraphEdge(md, tuple, interTuple); + } + argTuple = interTuple; + } else { + argTuple = argTupleSet.iterator().next(); + } + + addArgIdxMap(min, idx, argTuple); + FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx); + if (hasInFlowTo(calleeFlowGraph, paramNode, calleeReturnSet) + || calleeMethodDesc.getModifiers().isNative()) { + addParamNodeFlowingToReturnValue(calleeMethodDesc, paramNode); + nodeSet.addTupleSet(argTupleSet); + } + } + + } + + // propagateFlowsFromCallee(min, md, min.getMethod()); + + } + + } + + private boolean hasInFlowTo(FlowGraph fg, FlowNode inNode, Set nodeSet) { + // return true if inNode has in-flows to nodeSet + Set reachableSet = fg.getReachFlowNodeSetFrom(inNode); + for (Iterator iterator = reachableSet.iterator(); iterator.hasNext();) { + FlowNode fn = (FlowNode) iterator.next(); + if (nodeSet.contains(fn)) { + return true; + } + } + return false; + } + + private NTuple getNodeTupleByArgIdx(MethodInvokeNode min, int idx) { + return mapMethodInvokeNodeToArgIdxMap.get(min).get(new Integer(idx)); + } + + 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) { + + } + + private void analyzeFlowArrayAccessNode(MethodDescriptor md, SymbolTable nametable, + ArrayAccessNode aan, NodeTupleSet nodeSet, boolean isLHS) { + + NodeTupleSet expNodeTupleSet = new NodeTupleSet(); + NTuple base = + analyzeFlowExpressionNode(md, nametable, aan.getExpression(), expNodeTupleSet, isLHS); + + NodeTupleSet idxNodeTupleSet = new NodeTupleSet(); + analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, isLHS); + + if (isLHS) { + // need to create an edge from idx to array + for (Iterator> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) { + NTuple idxTuple = idxIter.next(); + for (Iterator> arrIter = expNodeTupleSet.iterator(); arrIter.hasNext();) { + NTuple arrTuple = arrIter.next(); + getFlowGraph(md).addValueFlowEdge(idxTuple, arrTuple); + } + } + + nodeSet.addTupleSet(expNodeTupleSet); + } else { + nodeSet.addTupleSet(expNodeTupleSet); + nodeSet.addTupleSet(idxNodeTupleSet); + } + } + + private void analyzeCreateObjectNode(MethodDescriptor md, SymbolTable nametable, + CreateObjectNode en) { + // TODO Auto-generated method stub + + } + + private void analyzeFlowOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on, + NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) { + + NodeTupleSet leftOpSet = new NodeTupleSet(); + NodeTupleSet rightOpSet = new NodeTupleSet(); + + // left operand + analyzeFlowExpressionNode(md, nametable, on.getLeft(), leftOpSet, null, implicitFlowTupleSet, + false); + + if (on.getRight() != null) { + // right operand + analyzeFlowExpressionNode(md, nametable, on.getRight(), rightOpSet, null, + implicitFlowTupleSet, false); + } + + Operation op = on.getOp(); + + switch (op.getOp()) { + + case Operation.UNARYPLUS: + case Operation.UNARYMINUS: + case Operation.LOGIC_NOT: + // single operand + nodeSet.addTupleSet(leftOpSet); + break; + + case Operation.LOGIC_OR: + case Operation.LOGIC_AND: + case Operation.COMP: + case Operation.BIT_OR: + case Operation.BIT_XOR: + case Operation.BIT_AND: + case Operation.ISAVAILABLE: + case Operation.EQUAL: + case Operation.NOTEQUAL: + case Operation.LT: + case Operation.GT: + case Operation.LTE: + case Operation.GTE: + case Operation.ADD: + case Operation.SUB: + case Operation.MULT: + case Operation.DIV: + case Operation.MOD: + case Operation.LEFTSHIFT: + case Operation.RIGHTSHIFT: + case Operation.URIGHTSHIFT: + + // there are two operands + nodeSet.addTupleSet(leftOpSet); + nodeSet.addTupleSet(rightOpSet); + break; + + default: + throw new Error(op.toString()); + } + + } + + 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(); + } + + NameDescriptor nd = nn.getName(); + + if (nd.getBase() != null) { + base = + analyzeFlowExpressionNode(md, nametable, nn.getExpression(), nodeSet, base, + implicitFlowTupleSet, false); + if (base == null) { + // base node has the top location + return base; + } + } else { + String varname = nd.toString(); + if (varname.equals("this")) { + // 'this' itself! + base.add(md.getThis()); + return base; + } + + Descriptor d = (Descriptor) nametable.get(varname); + + if (d instanceof VarDescriptor) { + VarDescriptor vd = (VarDescriptor) d; + base.add(vd); + } else if (d instanceof FieldDescriptor) { + // the type of field descriptor has a location! + FieldDescriptor fd = (FieldDescriptor) d; + if (fd.isStatic()) { + if (fd.isFinal()) { + // if it is 'static final', no need to have flow node for the TOP + // location + return null; + } else { + // if 'static', assign the default GLOBAL LOCATION to the first + // element of the tuple + base.add(GLOBALDESC); + } + } else { + // the location of field access starts from this, followed by field + // location + base.add(md.getThis()); + } + + base.add(fd); + } else if (d == null) { + // access static field + base.add(GLOBALDESC); + base.add(nn.getField()); + return base; + + // FieldDescriptor fd = nn.getField();addFlowGraphEdge + // + // MethodLattice localLattice = ssjava.getMethodLattice(md); + // String globalLocId = localLattice.getGlobalLoc(); + // if (globalLocId == null) { + // throw new + // Error("Method lattice does not define global variable location at " + // + generateErrorMessage(md.getClassDesc(), nn)); + // } + // loc.addLocation(new Location(md, globalLocId)); + // + // Location fieldLoc = (Location) fd.getType().getExtension(); + // loc.addLocation(fieldLoc); + // + // return loc; + + } + } + getFlowGraph(md).createNewFlowNode(base); + + return base; + + } + + private NTuple analyzeFlowFieldAccessNode(MethodDescriptor md, SymbolTable nametable, + FieldAccessNode fan, NodeTupleSet nodeSet, NTuple base, + NodeTupleSet implicitFlowTupleSet, boolean isLHS) { + + ExpressionNode left = fan.getExpression(); + TypeDescriptor ltd = left.getType(); + FieldDescriptor fd = fan.getField(); + + String varName = null; + if (left.kind() == Kind.NameNode) { + NameDescriptor nd = ((NameNode) left).getName(); + varName = nd.toString(); + } + + if (ltd.isClassNameRef() || (varName != null && varName.equals("this"))) { + // using a class name directly or access using this + if (fd.isStatic() && fd.isFinal()) { + return null; + } + } + + NodeTupleSet idxNodeTupleSet = new NodeTupleSet(); + + if (left instanceof ArrayAccessNode) { + + ArrayAccessNode aan = (ArrayAccessNode) left; + left = aan.getExpression(); + analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, base, + implicitFlowTupleSet, isLHS); + + nodeSet.addTupleSet(idxNodeTupleSet); + } + base = + analyzeFlowExpressionNode(md, nametable, left, nodeSet, base, implicitFlowTupleSet, isLHS); + + if (base == null) { + // in this case, field is TOP location + return null; + } else { + + NTuple flowFieldTuple = new NTuple(base.toList()); + + if (!left.getType().isPrimitive()) { + + if (!fd.getSymbol().equals("length")) { + // array.length access, just have the location of the array + flowFieldTuple.add(fd); + nodeSet.removeTuple(base); + } + + } + getFlowGraph(md).createNewFlowNode(flowFieldTuple); + + if (isLHS) { + for (Iterator> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) { + NTuple idxTuple = idxIter.next(); + getFlowGraph(md).addValueFlowEdge(idxTuple, flowFieldTuple); + } + } + return flowFieldTuple; + + } + + } + + private void debug_printTreeNode(TreeNode tn) { + + System.out.println("DEBUG: " + tn.printNode(0) + " line#=" + tn.getNumLine()); + + } + + private void analyzeFlowAssignmentNode(MethodDescriptor md, SymbolTable nametable, + AssignmentNode an, NodeTupleSet nodeSet, NTuple base, + NodeTupleSet implicitFlowTupleSet) { + + NodeTupleSet nodeSetRHS = new NodeTupleSet(); + NodeTupleSet nodeSetLHS = new NodeTupleSet(); + + boolean postinc = true; + if (an.getOperation().getBaseOp() == null + || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation() + .getBaseOp().getOp() != Operation.POSTDEC)) { + postinc = false; + } + // if LHS is array access node, need to capture value flows between an array + // and its index value + analyzeFlowExpressionNode(md, nametable, an.getDest(), nodeSetLHS, null, implicitFlowTupleSet, + true); + + if (!postinc) { + // analyze value flows of rhs expression + analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null, implicitFlowTupleSet, + false); + + // System.out.println("-analyzeFlowAssignmentNode=" + an.printNode(0)); + // System.out.println("-nodeSetLHS=" + nodeSetLHS); + // System.out.println("-nodeSetRHS=" + nodeSetRHS); + // System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet); + // System.out.println("-"); + + if (an.getOperation().getOp() >= 2 && an.getOperation().getOp() <= 12) { + // if assignment contains OP+EQ operator, creates edges from LHS to LHS + + for (Iterator> iter = nodeSetLHS.iterator(); iter.hasNext();) { + NTuple fromTuple = iter.next(); + for (Iterator> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) { + NTuple toTuple = iter2.next(); + addFlowGraphEdge(md, fromTuple, toTuple); + } + } + } + + // creates edges from RHS to LHS + NTuple interTuple = null; + if (nodeSetRHS.size() > 1) { + interTuple = getFlowGraph(md).createIntermediateNode(md).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, interTuple, toTuple); + } + } + + // creates edges from implicitFlowTupleSet to LHS + for (Iterator> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) { + NTuple fromTuple = iter.next(); + for (Iterator> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) { + NTuple toTuple = iter2.next(); + addFlowGraphEdge(md, fromTuple, toTuple); + } + } + + } else { + // postinc case + + for (Iterator> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) { + NTuple tuple = iter2.next(); + addFlowGraphEdge(md, tuple, tuple); + } + + // creates edges from implicitFlowTupleSet to LHS + for (Iterator> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) { + NTuple fromTuple = iter.next(); + for (Iterator> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) { + NTuple toTuple = iter2.next(); + addFlowGraphEdge(md, fromTuple, toTuple); + } + } + + } + + if (nodeSet != null) { + nodeSet.addTupleSet(nodeSetLHS); + } + } + + public FlowGraph getFlowGraph(MethodDescriptor md) { + return mapMethodDescriptorToFlowGraph.get(md); + } + + private boolean addFlowGraphEdge(MethodDescriptor md, NTuple from, + NTuple to) { + 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(); + + for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { + MethodDescriptor md = (MethodDescriptor) iterator.next(); + FlowGraph fg = mapMethodDescriptorToFlowGraph.get(md); + try { + fg.writeGraph(); + } catch (IOException e) { + e.printStackTrace(); + } + } + + } + +} + +class CyclicFlowException extends Exception { + +} + +class InterDescriptor extends Descriptor { + + public InterDescriptor(String name) { + super(name); } }