+ // 1) construct value flow graph
+ constructFlowGraph();
+
+ // 2) construct lattices
+ inferLattices();
+
+ debug_writeLatticeDotFile();
+
+ }
+
+ private void debug_writeLatticeDotFile() {
+ // generate lattice dot file
+
+ setupToAnalyze();
+
+ while (!toAnalyzeIsEmpty()) {
+ ClassDescriptor cd = toAnalyzeNext();
+
+ setupToAnalazeMethod(cd);
+
+ SSJavaLattice<String> classLattice = cd2lattice.get(cd);
+ if (classLattice != null) {
+ ssjava.writeLatticeDotFile(cd, classLattice);
+ }
+
+ while (!toAnalyzeMethodIsEmpty()) {
+ MethodDescriptor md = toAnalyzeMethodNext();
+ if (ssjava.needTobeAnnotated(md)) {
+ SSJavaLattice<String> methodLattice = md2lattice.get(md);
+ if (methodLattice != null) {
+ ssjava.writeLatticeDotFile(cd, methodLattice);
+ }
+ }
+ }
+ }
+
+ }
+
+ private void inferLattices() {
+
+ // do fixed-point analysis
+
+ // perform method READ/OVERWRITE analysis
+ LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
+
+ // current descriptors to visit in fixed-point interprocedural analysis,
+ // prioritized by
+ // dependency in the call graph
+ methodDescriptorsToVisitStack.clear();
+
+ descriptorListToAnalyze.removeFirst();
+
+ Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
+ 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();
+ FlatMethod fm = state.getMethodFlat(md);
+
+ SSJavaLattice<String> methodLattice =
+ new SSJavaLattice<String>(SSJavaLattice.TOP, SSJavaLattice.BOTTOM);
+
+ analyzeMethodLattice(md, methodLattice);
+
+ SSJavaLattice<String> prevMethodLattice = md2lattice.get(md);
+
+ if (!methodLattice.equals(prevMethodLattice)) {
+ md2lattice.put(md, methodLattice);
+
+ // results for callee changed, so enqueue dependents caller for
+ // further analysis
+ Iterator<MethodDescriptor> depsItr = ssjava.getDependents(md).iterator();
+ while (depsItr.hasNext()) {
+ MethodDescriptor methodNext = depsItr.next();
+ if (!methodDescriptorsToVisitStack.contains(methodNext)
+ && methodDescriptorToVistSet.contains(methodNext)) {
+ methodDescriptorsToVisitStack.add(methodNext);
+ }
+ }
+
+ }
+
+ }
+
+ }
+
+ private String getSymbol(int idx, FlowNode node) {
+ Descriptor desc = node.getDescTuple().get(idx);
+ return desc.getSymbol();
+ }
+
+ private void addMappingDescriptorToLocationIdentifer(MethodDescriptor methodDesc,
+ VarDescriptor varDesc, String identifier) {
+ if (!md2LatticeMapping.containsKey(methodDesc)) {
+ md2LatticeMapping.put(methodDesc, new HashMap<VarDescriptor, String>());
+ }
+
+ }
+
+ private void analyzeMethodLattice(MethodDescriptor md, SSJavaLattice<String> methodLattice) {
+
+ System.out.println("# Create the method lattice for " + md);
+
+ // visit each node of method flow graph
+
+ FlowGraph fg = getFlowGraph(md);
+ Set<FlowNode> nodeSet = fg.getNodeSet();
+
+ // for the method lattice, we need to look at the first element of
+ // NTuple<Descriptor>
+
+ for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
+ FlowNode srcNode = (FlowNode) iterator.next();
+
+ Set<FlowEdge> outEdgeSet = srcNode.getOutEdgeSet();
+ for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) {
+ FlowEdge outEdge = (FlowEdge) iterator2.next();
+
+ FlowNode dstNode = outEdge.getDst();
+
+ if ((srcNode.getDescTuple().size() > 1 && dstNode.getDescTuple().size() > 1)
+ && srcNode.getDescTuple().get(0).equals(dstNode.getDescTuple().get(0))) {
+ // value flow between fields: we don't need to add a binary relation
+ // for this case
+
+ VarDescriptor varDesc = (VarDescriptor) srcNode.getDescTuple().get(0);
+ ClassDescriptor varClassDesc = varDesc.getType().getClassDesc();
+
+ extractRelationFromFieldFlows(varClassDesc, srcNode, dstNode, 1);
+ continue;
+ }
+
+ // add a new binary relation of dstNode < srcNode
+
+ String srcSymbol = getSymbol(0, srcNode);
+ String dstSymbol = getSymbol(0, dstNode);
+
+ methodLattice.addRelationHigherToLower(srcSymbol, dstSymbol);
+
+ }
+
+ }
+
+ }
+
+ private void extractRelationFromFieldFlows(ClassDescriptor cd, FlowNode srcNode,
+ FlowNode dstNode, int idx) {
+
+ if (srcNode.getDescTuple().get(idx).equals(dstNode.getDescTuple().get(idx))) {
+ // value flow between fields: we don't need to add a binary relation
+ // for this case
+ VarDescriptor varDesc = (VarDescriptor) srcNode.getDescTuple().get(idx);
+ ClassDescriptor varClassDesc = varDesc.getType().getClassDesc();
+ extractRelationFromFieldFlows(varClassDesc, srcNode, dstNode, idx + 1);
+ } else {
+
+ Descriptor srcFieldDesc = srcNode.getDescTuple().get(idx);
+ Descriptor dstFieldDesc = dstNode.getDescTuple().get(idx);
+
+ // add a new binary relation of dstNode < srcNode
+
+ SSJavaLattice<String> fieldLattice = getFieldLattice(cd);
+ fieldLattice.addRelationHigherToLower(srcFieldDesc.getSymbol(), dstFieldDesc.getSymbol());
+
+ }
+
+ }
+
+ public SSJavaLattice<String> getFieldLattice(ClassDescriptor cd) {
+ if (!cd2lattice.containsKey(cd)) {
+ cd2lattice.put(cd, new SSJavaLattice<String>(SSJavaLattice.TOP, SSJavaLattice.BOTTOM));
+ }
+ return cd2lattice.get(cd);
+ }
+
+ public void constructFlowGraph() {