1 package Analysis.SSJava;
3 import java.io.BufferedReader;
4 import java.io.BufferedWriter;
5 import java.io.FileReader;
6 import java.io.FileWriter;
7 import java.io.IOException;
8 import java.util.ArrayList;
9 import java.util.Collections;
10 import java.util.Comparator;
11 import java.util.HashMap;
12 import java.util.HashSet;
13 import java.util.Iterator;
14 import java.util.LinkedList;
15 import java.util.List;
18 import java.util.Stack;
19 import java.util.Vector;
21 import IR.ClassDescriptor;
23 import IR.FieldDescriptor;
24 import IR.MethodDescriptor;
25 import IR.NameDescriptor;
28 import IR.SymbolTable;
29 import IR.TypeDescriptor;
30 import IR.VarDescriptor;
31 import IR.Tree.ArrayAccessNode;
32 import IR.Tree.AssignmentNode;
33 import IR.Tree.BlockExpressionNode;
34 import IR.Tree.BlockNode;
35 import IR.Tree.BlockStatementNode;
36 import IR.Tree.CastNode;
37 import IR.Tree.CreateObjectNode;
38 import IR.Tree.DeclarationNode;
39 import IR.Tree.ExpressionNode;
40 import IR.Tree.FieldAccessNode;
41 import IR.Tree.IfStatementNode;
43 import IR.Tree.LiteralNode;
44 import IR.Tree.LoopNode;
45 import IR.Tree.MethodInvokeNode;
46 import IR.Tree.NameNode;
47 import IR.Tree.OpNode;
48 import IR.Tree.ReturnNode;
49 import IR.Tree.SubBlockNode;
50 import IR.Tree.SwitchStatementNode;
51 import IR.Tree.TertiaryNode;
52 import IR.Tree.TreeNode;
55 public class LocationInference {
58 SSJavaAnalysis ssjava;
60 List<ClassDescriptor> toanalyzeList;
61 List<MethodDescriptor> toanalyzeMethodList;
62 Map<MethodDescriptor, FlowGraph> mapMethodDescriptorToFlowGraph;
64 // map a method descriptor to its set of parameter descriptors
65 Map<MethodDescriptor, Set<Descriptor>> mapMethodDescriptorToParamDescSet;
67 // keep current descriptors to visit in fixed-point interprocedural analysis,
68 private Stack<MethodDescriptor> methodDescriptorsToVisitStack;
70 // map a class descriptor to a field lattice
71 private Map<ClassDescriptor, SSJavaLattice<String>> cd2lattice;
73 // map a method descriptor to a method lattice
74 private Map<MethodDescriptor, SSJavaLattice<String>> md2lattice;
76 // map a method descriptor to the set of method invocation nodes which are
77 // invoked by the method descriptor
78 private Map<MethodDescriptor, Set<MethodInvokeNode>> mapMethodDescriptorToMethodInvokeNodeSet;
80 private Map<MethodInvokeNode, Map<Integer, NodeTupleSet>> mapMethodInvokeNodeToArgIdxMap;
82 private Map<MethodDescriptor, MethodLocationInfo> mapMethodDescToMethodLocationInfo;
84 private Map<ClassDescriptor, LocationInfo> mapClassToLocationInfo;
86 private Map<MethodDescriptor, Set<MethodDescriptor>> mapMethodToCalleeSet;
88 private Map<MethodDescriptor, Set<FlowNode>> mapMethodDescToParamNodeFlowsToReturnValue;
90 private Map<String, Vector<String>> mapFileNameToLineVector;
92 private Map<Descriptor, Integer> mapDescToDefinitionLine;
94 public static final String GLOBALLOC = "GLOBALLOC";
96 public static final String TOPLOC = "TOPLOC";
98 public static final String INTERLOC = "INTERLOC";
100 public static final Descriptor GLOBALDESC = new NameDescriptor(GLOBALLOC);
102 public static final Descriptor TOPDESC = new NameDescriptor(TOPLOC);
104 public static String newline = System.getProperty("line.separator");
106 LocationInfo curMethodInfo;
108 boolean debug = true;
110 public LocationInference(SSJavaAnalysis ssjava, State state) {
111 this.ssjava = ssjava;
113 this.toanalyzeList = new ArrayList<ClassDescriptor>();
114 this.toanalyzeMethodList = new ArrayList<MethodDescriptor>();
115 this.mapMethodDescriptorToFlowGraph = new HashMap<MethodDescriptor, FlowGraph>();
116 this.cd2lattice = new HashMap<ClassDescriptor, SSJavaLattice<String>>();
117 this.md2lattice = new HashMap<MethodDescriptor, SSJavaLattice<String>>();
118 this.methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
119 this.mapMethodDescriptorToMethodInvokeNodeSet =
120 new HashMap<MethodDescriptor, Set<MethodInvokeNode>>();
121 this.mapMethodInvokeNodeToArgIdxMap =
122 new HashMap<MethodInvokeNode, Map<Integer, NodeTupleSet>>();
123 this.mapMethodDescToMethodLocationInfo = new HashMap<MethodDescriptor, MethodLocationInfo>();
124 this.mapMethodToCalleeSet = new HashMap<MethodDescriptor, Set<MethodDescriptor>>();
125 this.mapClassToLocationInfo = new HashMap<ClassDescriptor, LocationInfo>();
127 this.mapFileNameToLineVector = new HashMap<String, Vector<String>>();
128 this.mapDescToDefinitionLine = new HashMap<Descriptor, Integer>();
129 this.mapMethodDescToParamNodeFlowsToReturnValue =
130 new HashMap<MethodDescriptor, Set<FlowNode>>();
133 public void setupToAnalyze() {
134 SymbolTable classtable = state.getClassSymbolTable();
135 toanalyzeList.clear();
136 toanalyzeList.addAll(classtable.getValueSet());
137 // Collections.sort(toanalyzeList, new Comparator<ClassDescriptor>() {
138 // public int compare(ClassDescriptor o1, ClassDescriptor o2) {
139 // return o1.getClassName().compareToIgnoreCase(o2.getClassName());
144 public void setupToAnalazeMethod(ClassDescriptor cd) {
146 SymbolTable methodtable = cd.getMethodTable();
147 toanalyzeMethodList.clear();
148 toanalyzeMethodList.addAll(methodtable.getValueSet());
149 Collections.sort(toanalyzeMethodList, new Comparator<MethodDescriptor>() {
150 public int compare(MethodDescriptor o1, MethodDescriptor o2) {
151 return o1.getSymbol().compareToIgnoreCase(o2.getSymbol());
156 public boolean toAnalyzeMethodIsEmpty() {
157 return toanalyzeMethodList.isEmpty();
160 public boolean toAnalyzeIsEmpty() {
161 return toanalyzeList.isEmpty();
164 public ClassDescriptor toAnalyzeNext() {
165 return toanalyzeList.remove(0);
168 public MethodDescriptor toAnalyzeMethodNext() {
169 return toanalyzeMethodList.remove(0);
172 public void inference() {
174 // 1) construct value flow graph
175 constructFlowGraph();
177 // 2) construct lattices
182 debug_writeLatticeDotFile();
184 // 3) check properties
187 // 4) generate annotated source codes
188 generateAnnoatedCode();
192 private void addMapClassDefinitionToLineNum(ClassDescriptor cd, String strLine, int lineNum) {
194 String classSymbol = cd.getSymbol();
195 int idx = classSymbol.lastIndexOf("$");
197 classSymbol = classSymbol.substring(idx + 1);
200 String pattern = "class " + classSymbol + " ";
201 if (strLine.indexOf(pattern) != -1) {
202 mapDescToDefinitionLine.put(cd, lineNum);
206 private void addMapMethodDefinitionToLineNum(Set<MethodDescriptor> methodSet, String strLine,
208 for (Iterator iterator = methodSet.iterator(); iterator.hasNext();) {
209 MethodDescriptor md = (MethodDescriptor) iterator.next();
210 String pattern = md.getMethodDeclaration();
211 if (strLine.indexOf(pattern) != -1) {
212 mapDescToDefinitionLine.put(md, lineNum);
213 methodSet.remove(md);
220 private void readOriginalSourceFiles() {
222 SymbolTable classtable = state.getClassSymbolTable();
224 Set<ClassDescriptor> classDescSet = new HashSet<ClassDescriptor>();
225 classDescSet.addAll(classtable.getValueSet());
228 // inefficient implement. it may re-visit the same file if the file
229 // contains more than one class definitions.
230 for (Iterator iterator = classDescSet.iterator(); iterator.hasNext();) {
231 ClassDescriptor cd = (ClassDescriptor) iterator.next();
233 Set<MethodDescriptor> methodSet = new HashSet<MethodDescriptor>();
234 methodSet.addAll(cd.getMethodTable().getValueSet());
236 String sourceFileName = cd.getSourceFileName();
237 Vector<String> lineVec = new Vector<String>();
239 mapFileNameToLineVector.put(sourceFileName, lineVec);
241 BufferedReader in = new BufferedReader(new FileReader(sourceFileName));
244 lineVec.add(""); // the index is started from 1.
245 while ((strLine = in.readLine()) != null) {
246 lineVec.add(lineNum, strLine);
247 addMapClassDefinitionToLineNum(cd, strLine, lineNum);
248 addMapMethodDefinitionToLineNum(methodSet, strLine, lineNum);
254 } catch (IOException e) {
260 private String generateLatticeDefinition(Descriptor desc) {
262 Set<String> sharedLocSet = new HashSet<String>();
264 SSJavaLattice<String> lattice = getLattice(desc);
265 String rtr = "@LATTICE(\"";
267 Map<String, Set<String>> map = lattice.getTable();
268 Set<String> keySet = map.keySet();
269 boolean first = true;
270 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
271 String key = (String) iterator.next();
272 if (!key.equals(lattice.getTopItem())) {
273 Set<String> connectedSet = map.get(key);
275 if (connectedSet.size() == 1) {
276 if (connectedSet.iterator().next().equals(lattice.getBottomItem())) {
284 if (lattice.isSharedLoc(key)) {
285 rtr += "," + key + "*";
290 for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) {
291 String loc = (String) iterator2.next();
292 if (!loc.equals(lattice.getBottomItem())) {
299 rtr += loc + "<" + key;
300 if (lattice.isSharedLoc(key) && (!sharedLocSet.contains(key))) {
301 rtr += "," + key + "*";
302 sharedLocSet.add(key);
304 if (lattice.isSharedLoc(loc) && (!sharedLocSet.contains(loc))) {
305 rtr += "," + loc + "*";
306 sharedLocSet.add(loc);
316 if (desc instanceof MethodDescriptor) {
317 TypeDescriptor returnType = ((MethodDescriptor) desc).getReturnType();
319 MethodLocationInfo methodLocInfo = getMethodLocationInfo((MethodDescriptor) desc);
321 if (returnType != null && (!returnType.isVoid())) {
323 "\n@RETURNLOC(\"" + generateLocationAnnoatation(methodLocInfo.getReturnLoc()) + "\")";
326 rtr += "\n@THISLOC(\"this\")";
327 rtr += "\n@GLOBALLOC(\"GLOBALLOC\")";
329 CompositeLocation pcLoc = methodLocInfo.getPCLoc();
330 if ((pcLoc != null) && (!pcLoc.get(0).isTop())) {
331 rtr += "\n@PCLOC(\"" + generateLocationAnnoatation(pcLoc) + "\")";
339 private void generateAnnoatedCode() {
341 readOriginalSourceFiles();
344 while (!toAnalyzeIsEmpty()) {
345 ClassDescriptor cd = toAnalyzeNext();
347 setupToAnalazeMethod(cd);
349 LocationInfo locInfo = mapClassToLocationInfo.get(cd);
350 String sourceFileName = cd.getSourceFileName();
352 if (cd.isInterface()) {
356 int classDefLine = mapDescToDefinitionLine.get(cd);
357 Vector<String> sourceVec = mapFileNameToLineVector.get(sourceFileName);
359 if (locInfo == null) {
360 locInfo = getLocationInfo(cd);
363 for (Iterator iter = cd.getFields(); iter.hasNext();) {
364 FieldDescriptor fieldDesc = (FieldDescriptor) iter.next();
365 if (!(fieldDesc.isStatic() && fieldDesc.isFinal())) {
366 String locIdentifier = locInfo.getFieldInferLocation(fieldDesc).getLocIdentifier();
367 if (!getLattice(cd).getElementSet().contains(locIdentifier)) {
368 getLattice(cd).put(locIdentifier);
373 String fieldLatticeDefStr = generateLatticeDefinition(cd);
374 String annoatedSrc = fieldLatticeDefStr + newline + sourceVec.get(classDefLine);
375 sourceVec.set(classDefLine, annoatedSrc);
377 // generate annotations for field declarations
378 LocationInfo fieldLocInfo = getLocationInfo(cd);
379 Map<Descriptor, CompositeLocation> inferLocMap = fieldLocInfo.getMapDescToInferLocation();
381 for (Iterator iter = cd.getFields(); iter.hasNext();) {
382 FieldDescriptor fd = (FieldDescriptor) iter.next();
384 String locAnnotationStr;
385 CompositeLocation inferLoc = inferLocMap.get(fd);
387 if (inferLoc != null) {
388 // infer loc is null if the corresponding field is static and final
389 locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")";
390 int fdLineNum = fd.getLineNum();
391 String orgFieldDeclarationStr = sourceVec.get(fdLineNum);
392 String fieldDeclaration = fd.toString();
393 fieldDeclaration = fieldDeclaration.substring(0, fieldDeclaration.length() - 1);
394 String annoatedStr = locAnnotationStr + " " + orgFieldDeclarationStr;
395 sourceVec.set(fdLineNum, annoatedStr);
400 while (!toAnalyzeMethodIsEmpty()) {
401 MethodDescriptor md = toAnalyzeMethodNext();
403 if (!ssjava.needTobeAnnotated(md)) {
407 SSJavaLattice<String> methodLattice = md2lattice.get(md);
408 if (methodLattice != null) {
410 int methodDefLine = md.getLineNum();
412 MethodLocationInfo methodLocInfo = getMethodLocationInfo(md);
414 Map<Descriptor, CompositeLocation> methodInferLocMap =
415 methodLocInfo.getMapDescToInferLocation();
416 Set<Descriptor> localVarDescSet = methodInferLocMap.keySet();
418 Set<String> localLocElementSet = methodLattice.getElementSet();
420 for (Iterator iterator = localVarDescSet.iterator(); iterator.hasNext();) {
421 Descriptor localVarDesc = (Descriptor) iterator.next();
422 CompositeLocation inferLoc = methodInferLocMap.get(localVarDesc);
424 String localLocIdentifier = inferLoc.get(0).getLocIdentifier();
425 if (!localLocElementSet.contains(localLocIdentifier)) {
426 methodLattice.put(localLocIdentifier);
429 String locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")";
431 if (!isParameter(md, localVarDesc)) {
432 if (mapDescToDefinitionLine.containsKey(localVarDesc)) {
433 int varLineNum = mapDescToDefinitionLine.get(localVarDesc);
434 String orgSourceLine = sourceVec.get(varLineNum);
436 orgSourceLine.indexOf(generateVarDeclaration((VarDescriptor) localVarDesc));
439 orgSourceLine.substring(0, idx) + locAnnotationStr + " "
440 + orgSourceLine.substring(idx);
441 sourceVec.set(varLineNum, annoatedStr);
444 String methodDefStr = sourceVec.get(methodDefLine);
447 getParamLocation(methodDefStr,
448 generateVarDeclaration((VarDescriptor) localVarDesc));
453 methodDefStr.substring(0, idx) + locAnnotationStr + " "
454 + methodDefStr.substring(idx);
455 sourceVec.set(methodDefLine, annoatedStr);
460 // check if the lattice has to have the location type for the this
463 // boolean needToAddthisRef = hasThisReference(md);
464 if (localLocElementSet.contains("this")) {
465 methodLattice.put("this");
468 String methodLatticeDefStr = generateLatticeDefinition(md);
469 String annoatedStr = methodLatticeDefStr + newline + sourceVec.get(methodDefLine);
470 sourceVec.set(methodDefLine, annoatedStr);
480 private boolean hasThisReference(MethodDescriptor md) {
482 FlowGraph fg = getFlowGraph(md);
483 Set<FlowNode> nodeSet = fg.getNodeSet();
484 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
485 FlowNode flowNode = (FlowNode) iterator.next();
486 if (flowNode.getDescTuple().get(0).equals(md.getThis())) {
494 private int getParamLocation(String methodStr, String paramStr) {
496 String pattern = paramStr + ",";
498 int idx = methodStr.indexOf(pattern);
502 pattern = paramStr + ")";
503 return methodStr.indexOf(pattern);
508 private String generateVarDeclaration(VarDescriptor varDesc) {
510 TypeDescriptor td = varDesc.getType();
511 String rtr = td.toString();
513 for (int i = 0; i < td.getArrayCount(); i++) {
517 rtr += " " + varDesc.getName();
522 private String generateLocationAnnoatation(CompositeLocation loc) {
525 Location methodLoc = loc.get(0);
526 rtr += methodLoc.getLocIdentifier();
528 for (int i = 1; i < loc.getSize(); i++) {
529 Location element = loc.get(i);
530 rtr += "," + element.getDescriptor().getSymbol() + "." + element.getLocIdentifier();
536 private boolean isParameter(MethodDescriptor md, Descriptor localVarDesc) {
537 return getFlowGraph(md).isParamDesc(localVarDesc);
540 private String extractFileName(String fileName) {
541 int idx = fileName.lastIndexOf("/");
545 return fileName.substring(idx + 1);
550 private void codeGen() {
552 Set<String> originalFileNameSet = mapFileNameToLineVector.keySet();
553 for (Iterator iterator = originalFileNameSet.iterator(); iterator.hasNext();) {
554 String orgFileName = (String) iterator.next();
555 String outputFileName = extractFileName(orgFileName);
557 Vector<String> sourceVec = mapFileNameToLineVector.get(orgFileName);
561 FileWriter fileWriter = new FileWriter("./infer/" + outputFileName);
562 BufferedWriter out = new BufferedWriter(fileWriter);
564 for (int i = 0; i < sourceVec.size(); i++) {
565 out.write(sourceVec.get(i));
569 } catch (IOException e) {
577 private void simplifyLattices() {
579 // generate lattice dot file
582 while (!toAnalyzeIsEmpty()) {
583 ClassDescriptor cd = toAnalyzeNext();
585 setupToAnalazeMethod(cd);
587 SSJavaLattice<String> classLattice = cd2lattice.get(cd);
588 if (classLattice != null) {
589 classLattice.removeRedundantEdges();
592 while (!toAnalyzeMethodIsEmpty()) {
593 MethodDescriptor md = toAnalyzeMethodNext();
594 SSJavaLattice<String> methodLattice = md2lattice.get(md);
595 if (methodLattice != null) {
596 methodLattice.removeRedundantEdges();
603 private void checkLattices() {
605 LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
607 // current descriptors to visit in fixed-point interprocedural analysis,
609 // dependency in the call graph
610 methodDescriptorsToVisitStack.clear();
612 // descriptorListToAnalyze.removeFirst();
614 Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
615 methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
617 while (!descriptorListToAnalyze.isEmpty()) {
618 MethodDescriptor md = descriptorListToAnalyze.removeFirst();
619 checkLatticesOfVirtualMethods(md);
624 private void debug_writeLatticeDotFile() {
625 // generate lattice dot file
629 while (!toAnalyzeIsEmpty()) {
630 ClassDescriptor cd = toAnalyzeNext();
632 setupToAnalazeMethod(cd);
634 SSJavaLattice<String> classLattice = cd2lattice.get(cd);
635 if (classLattice != null) {
636 ssjava.writeLatticeDotFile(cd, null, classLattice);
637 debug_printDescriptorToLocNameMapping(cd);
640 while (!toAnalyzeMethodIsEmpty()) {
641 MethodDescriptor md = toAnalyzeMethodNext();
642 SSJavaLattice<String> methodLattice = md2lattice.get(md);
643 if (methodLattice != null) {
644 ssjava.writeLatticeDotFile(cd, md, methodLattice);
645 debug_printDescriptorToLocNameMapping(md);
652 private void debug_printDescriptorToLocNameMapping(Descriptor desc) {
654 LocationInfo info = getLocationInfo(desc);
655 System.out.println("## " + desc + " ##");
656 System.out.println(info.getMapDescToInferLocation());
657 LocationInfo locInfo = getLocationInfo(desc);
658 System.out.println("mapping=" + locInfo.getMapLocSymbolToDescSet());
659 System.out.println("###################");
663 private void inferLattices() {
665 // do fixed-point analysis
668 LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
670 // Collections.sort(descriptorListToAnalyze, new
671 // Comparator<MethodDescriptor>() {
672 // public int compare(MethodDescriptor o1, MethodDescriptor o2) {
673 // return o1.getSymbol().compareToIgnoreCase(o2.getSymbol());
677 // current descriptors to visit in fixed-point interprocedural analysis,
679 // dependency in the call graph
680 methodDescriptorsToVisitStack.clear();
682 // descriptorListToAnalyze.removeFirst();
684 Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
685 methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
687 while (!descriptorListToAnalyze.isEmpty()) {
688 MethodDescriptor md = descriptorListToAnalyze.removeFirst();
689 methodDescriptorsToVisitStack.add(md);
692 // analyze scheduled methods until there are no more to visit
693 while (!methodDescriptorsToVisitStack.isEmpty()) {
694 // start to analyze leaf node
695 MethodDescriptor md = methodDescriptorsToVisitStack.pop();
697 SSJavaLattice<String> methodLattice =
698 new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM);
700 MethodLocationInfo methodInfo = new MethodLocationInfo(md);
701 curMethodInfo = methodInfo;
703 System.out.println();
704 System.out.println("SSJAVA: Inferencing the lattice from " + md);
707 analyzeMethodLattice(md, methodLattice, methodInfo);
708 } catch (CyclicFlowException e) {
709 throw new Error("Fail to generate the method lattice for " + md);
712 SSJavaLattice<String> prevMethodLattice = getMethodLattice(md);
713 MethodLocationInfo prevMethodInfo = getMethodLocationInfo(md);
715 if ((!methodLattice.equals(prevMethodLattice)) || (!methodInfo.equals(prevMethodInfo))) {
717 setMethodLattice(md, methodLattice);
718 setMethodLocInfo(md, methodInfo);
720 // results for callee changed, so enqueue dependents caller for
722 Iterator<MethodDescriptor> depsItr = ssjava.getDependents(md).iterator();
723 while (depsItr.hasNext()) {
724 MethodDescriptor methodNext = depsItr.next();
725 if (!methodDescriptorsToVisitStack.contains(methodNext)
726 && methodDescriptorToVistSet.contains(methodNext)) {
727 methodDescriptorsToVisitStack.add(methodNext);
735 descriptorListToAnalyze = ssjava.getSortedDescriptors();
736 for (Iterator iterator = descriptorListToAnalyze.iterator(); iterator.hasNext();) {
737 MethodDescriptor md = (MethodDescriptor) iterator.next();
738 calculateExtraLocations(md);
743 private void setMethodLocInfo(MethodDescriptor md, MethodLocationInfo methodInfo) {
744 mapMethodDescToMethodLocationInfo.put(md, methodInfo);
747 private void checkLatticesOfVirtualMethods(MethodDescriptor md) {
749 if (!md.isStatic()) {
750 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
751 setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md));
753 for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
754 MethodDescriptor mdCallee = (MethodDescriptor) iterator.next();
755 if (!md.equals(mdCallee)) {
756 checkConsistency(md, mdCallee);
764 private void checkConsistency(MethodDescriptor md1, MethodDescriptor md2) {
766 // check that two lattice have the same relations between parameters(+PC
767 // LOC, GLOBAL_LOC RETURN LOC)
769 List<CompositeLocation> list1 = new ArrayList<CompositeLocation>();
770 List<CompositeLocation> list2 = new ArrayList<CompositeLocation>();
772 MethodLocationInfo locInfo1 = getMethodLocationInfo(md1);
773 MethodLocationInfo locInfo2 = getMethodLocationInfo(md2);
775 Map<Integer, CompositeLocation> paramMap1 = locInfo1.getMapParamIdxToInferLoc();
776 Map<Integer, CompositeLocation> paramMap2 = locInfo2.getMapParamIdxToInferLoc();
778 int numParam = locInfo1.getMapParamIdxToInferLoc().keySet().size();
780 // add location types of paramters
781 for (int idx = 0; idx < numParam; idx++) {
782 list1.add(paramMap1.get(Integer.valueOf(idx)));
783 list2.add(paramMap2.get(Integer.valueOf(idx)));
786 // add program counter location
787 list1.add(locInfo1.getPCLoc());
788 list2.add(locInfo2.getPCLoc());
790 if (!md1.getReturnType().isVoid()) {
791 // add return value location
792 CompositeLocation rtrLoc1 = getMethodLocationInfo(md1).getReturnLoc();
793 CompositeLocation rtrLoc2 = getMethodLocationInfo(md2).getReturnLoc();
798 // add global location type
799 if (md1.isStatic()) {
800 CompositeLocation globalLoc1 =
801 new CompositeLocation(new Location(md1, locInfo1.getGlobalLocName()));
802 CompositeLocation globalLoc2 =
803 new CompositeLocation(new Location(md2, locInfo2.getGlobalLocName()));
804 list1.add(globalLoc1);
805 list2.add(globalLoc2);
808 for (int i = 0; i < list1.size(); i++) {
809 CompositeLocation locA1 = list1.get(i);
810 CompositeLocation locA2 = list2.get(i);
811 for (int k = 0; k < list1.size(); k++) {
813 CompositeLocation locB1 = list1.get(k);
814 CompositeLocation locB2 = list2.get(k);
815 boolean r1 = isGreaterThan(getLattice(md1), locA1, locB1);
817 boolean r2 = isGreaterThan(getLattice(md1), locA2, locB2);
820 throw new Error("The method " + md1 + " is not consistent with the method " + md2
821 + ".:: They have a different ordering relation between locations (" + locA1 + ","
822 + locB1 + ") and (" + locA2 + "," + locB2 + ").");
830 private String getSymbol(int idx, FlowNode node) {
831 Descriptor desc = node.getDescTuple().get(idx);
832 return desc.getSymbol();
835 private Descriptor getDescriptor(int idx, FlowNode node) {
836 Descriptor desc = node.getDescTuple().get(idx);
840 private void analyzeMethodLattice(MethodDescriptor md, SSJavaLattice<String> methodLattice,
841 MethodLocationInfo methodInfo) throws CyclicFlowException {
843 // first take a look at method invocation nodes to newly added relations
845 analyzeLatticeMethodInvocationNode(md, methodLattice, methodInfo);
847 if (!md.isStatic()) {
848 // set the this location
849 String thisLocSymbol = md.getThis().getSymbol();
850 methodInfo.setThisLocName(thisLocSymbol);
853 // set the global location
854 methodInfo.setGlobalLocName(LocationInference.GLOBALLOC);
855 methodInfo.mapDescriptorToLocation(GLOBALDESC, new CompositeLocation(
856 new Location(md, GLOBALLOC)));
858 // visit each node of method flow graph
859 FlowGraph fg = getFlowGraph(md);
860 Set<FlowNode> nodeSet = fg.getNodeSet();
862 // for the method lattice, we need to look at the first element of
863 // NTuple<Descriptor>
864 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
865 FlowNode srcNode = (FlowNode) iterator.next();
867 Set<FlowEdge> outEdgeSet = srcNode.getOutEdgeSet();
868 for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) {
869 FlowEdge outEdge = (FlowEdge) iterator2.next();
870 FlowNode dstNode = outEdge.getDst();
872 NTuple<Descriptor> srcNodeTuple = srcNode.getDescTuple();
873 NTuple<Descriptor> dstNodeTuple = dstNode.getDescTuple();
875 if (outEdge.getInitTuple().equals(srcNodeTuple)
876 && outEdge.getEndTuple().equals(dstNodeTuple)) {
878 if ((srcNodeTuple.size() > 1 && dstNodeTuple.size() > 1)
879 && srcNodeTuple.get(0).equals(dstNodeTuple.get(0))) {
881 // value flows between fields
882 Descriptor desc = srcNodeTuple.get(0);
883 ClassDescriptor classDesc;
885 if (desc.equals(GLOBALDESC)) {
886 classDesc = md.getClassDesc();
888 VarDescriptor varDesc = (VarDescriptor) srcNodeTuple.get(0);
889 classDesc = varDesc.getType().getClassDesc();
891 extractRelationFromFieldFlows(classDesc, srcNode, dstNode, 1);
894 // value flow between local var - local var or local var - field
895 addRelationToLattice(md, methodLattice, methodInfo, srcNode, dstNode);
901 // create mapping from param idx to inferred composite location
904 if (!md.isStatic()) {
905 // add 'this' reference location
907 methodInfo.addMapParamIdxToInferLoc(0, methodInfo.getInferLocation(md.getThis()));
912 for (int idx = 0; idx < md.numParameters(); idx++) {
913 Descriptor paramDesc = md.getParameter(idx);
914 CompositeLocation inferParamLoc = methodInfo.getInferLocation(paramDesc);
915 methodInfo.addMapParamIdxToInferLoc(idx + offset, inferParamLoc);
920 private void calculateExtraLocations(MethodDescriptor md) {
921 // calcualte pcloc, returnloc,...
923 SSJavaLattice<String> methodLattice = getMethodLattice(md);
924 MethodLocationInfo methodInfo = getMethodLocationInfo(md);
925 FlowGraph fg = getFlowGraph(md);
926 Set<FlowNode> nodeSet = fg.getNodeSet();
928 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
929 FlowNode flowNode = (FlowNode) iterator.next();
930 if (flowNode.isDeclaratonNode()) {
931 CompositeLocation inferLoc = methodInfo.getInferLocation(flowNode.getDescTuple().get(0));
932 String locIdentifier = inferLoc.get(0).getLocIdentifier();
933 if (!methodLattice.containsKey(locIdentifier)) {
934 methodLattice.put(locIdentifier);
940 Map<Integer, CompositeLocation> mapParamToLoc = methodInfo.getMapParamIdxToInferLoc();
941 Set<Integer> paramIdxSet = mapParamToLoc.keySet();
944 if (!ssjava.getMethodContainingSSJavaLoop().equals(md)) {
945 // calculate the initial program counter location
946 // PC location is higher than location types of all parameters
947 String pcLocSymbol = "PCLOC";
949 Set<CompositeLocation> paramInFlowSet = new HashSet<CompositeLocation>();
951 for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) {
952 Integer paramIdx = (Integer) iterator.next();
954 FlowNode paramFlowNode = fg.getParamFlowNode(paramIdx);
956 if (fg.getIncomingFlowNodeSet(paramFlowNode).size() > 0) {
957 // parameter has in-value flows
958 CompositeLocation inferLoc = mapParamToLoc.get(paramIdx);
959 paramInFlowSet.add(inferLoc);
963 if (paramInFlowSet.size() > 0) {
964 CompositeLocation lowestLoc = getLowest(methodLattice, paramInFlowSet);
965 assert (lowestLoc != null);
966 methodInfo.setPCLoc(lowestLoc);
971 // calculate a return location
972 // the return location type is lower than all parameters and location
975 if (!md.getReturnType().isVoid()) {
976 // first, generate the set of return value location types that starts
980 Set<CompositeLocation> inferFieldReturnLocSet = new HashSet<CompositeLocation>();
982 Set<FlowNode> paramFlowNode = getParamNodeFlowingToReturnValue(md);
983 Set<CompositeLocation> inferParamLocSet = new HashSet<CompositeLocation>();
984 if (paramFlowNode != null) {
985 for (Iterator iterator = paramFlowNode.iterator(); iterator.hasNext();) {
986 FlowNode fn = (FlowNode) iterator.next();
987 CompositeLocation inferLoc =
988 generateInferredCompositeLocation(methodInfo, getFlowGraph(md).getLocationTuple(fn));
989 inferParamLocSet.add(inferLoc);
993 Set<FlowNode> returnNodeSet = fg.getReturnNodeSet();
995 skip: for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
996 FlowNode returnNode = (FlowNode) iterator.next();
997 CompositeLocation inferReturnLoc =
998 generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode));
999 if (inferReturnLoc.get(0).getLocIdentifier().equals("this")) {
1000 // if the location type of the return value matches "this" reference
1001 // then, check whether this return value is equal to/lower than all
1003 // parameters that possibly flow into the return values
1004 for (Iterator iterator2 = inferParamLocSet.iterator(); iterator2.hasNext();) {
1005 CompositeLocation paramInferLoc = (CompositeLocation) iterator2.next();
1007 if ((!paramInferLoc.equals(inferReturnLoc))
1008 && !isGreaterThan(methodLattice, paramInferLoc, inferReturnLoc)) {
1012 inferFieldReturnLocSet.add(inferReturnLoc);
1017 if (inferFieldReturnLocSet.size() > 0) {
1019 CompositeLocation returnLoc = getLowest(methodLattice, inferFieldReturnLocSet);
1020 if (returnLoc == null) {
1021 // in this case, assign <'this',bottom> to the RETURNLOC
1022 returnLoc = new CompositeLocation(new Location(md, md.getThis().getSymbol()));
1023 returnLoc.addLocation(new Location(md.getClassDesc(), getLattice(md.getClassDesc())
1026 methodInfo.setReturnLoc(returnLoc);
1029 String returnLocSymbol = "RETURNLOC";
1030 CompositeLocation returnLocInferLoc =
1031 new CompositeLocation(new Location(md, returnLocSymbol));
1032 methodInfo.setReturnLoc(returnLocInferLoc);
1034 for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) {
1035 Integer paramIdx = (Integer) iterator.next();
1036 CompositeLocation inferLoc = mapParamToLoc.get(paramIdx);
1037 String paramLocLocalSymbol = inferLoc.get(0).getLocIdentifier();
1038 if (!methodLattice.isGreaterThan(paramLocLocalSymbol, returnLocSymbol)) {
1039 addRelationHigherToLower(methodLattice, methodInfo, paramLocLocalSymbol,
1044 for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
1045 FlowNode returnNode = (FlowNode) iterator.next();
1046 CompositeLocation inferLoc =
1047 generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode));
1048 if (!isGreaterThan(methodLattice, inferLoc, returnLocInferLoc)) {
1049 addRelation(methodLattice, methodInfo, inferLoc, returnLocInferLoc);
1056 } catch (CyclicFlowException e) {
1057 e.printStackTrace();
1062 private Set<String> getHigherLocSymbolThan(SSJavaLattice<String> lattice, String loc) {
1063 Set<String> higherLocSet = new HashSet<String>();
1065 Set<String> locSet = lattice.getTable().keySet();
1066 for (Iterator iterator = locSet.iterator(); iterator.hasNext();) {
1067 String element = (String) iterator.next();
1068 if (lattice.isGreaterThan(element, loc) && (!element.equals(lattice.getTopItem()))) {
1069 higherLocSet.add(element);
1072 return higherLocSet;
1075 private CompositeLocation getLowest(SSJavaLattice<String> methodLattice,
1076 Set<CompositeLocation> set) {
1078 CompositeLocation lowest = set.iterator().next();
1080 if (set.size() == 1) {
1084 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
1085 CompositeLocation loc = (CompositeLocation) iterator.next();
1087 if ((!loc.equals(lowest)) && (!isComparable(methodLattice, lowest, loc))) {
1088 // if there is a case where composite locations are incomparable, just
1093 if ((!loc.equals(lowest)) && isGreaterThan(methodLattice, lowest, loc)) {
1100 private boolean isComparable(SSJavaLattice<String> methodLattice, CompositeLocation comp1,
1101 CompositeLocation comp2) {
1103 int size = comp1.getSize() >= comp2.getSize() ? comp2.getSize() : comp1.getSize();
1105 for (int idx = 0; idx < size; idx++) {
1106 Location loc1 = comp1.get(idx);
1107 Location loc2 = comp2.get(idx);
1109 Descriptor desc1 = loc1.getDescriptor();
1110 Descriptor desc2 = loc2.getDescriptor();
1112 if (!desc1.equals(desc2)) {
1113 throw new Error("Fail to compare " + comp1 + " and " + comp2);
1116 String symbol1 = loc1.getLocIdentifier();
1117 String symbol2 = loc2.getLocIdentifier();
1119 SSJavaLattice<String> lattice;
1121 lattice = methodLattice;
1123 lattice = getLattice(desc1);
1126 if (symbol1.equals(symbol2)) {
1128 } else if (!lattice.isComparable(symbol1, symbol2)) {
1137 private boolean isGreaterThan(SSJavaLattice<String> methodLattice, CompositeLocation comp1,
1138 CompositeLocation comp2) {
1140 int size = comp1.getSize() >= comp2.getSize() ? comp2.getSize() : comp1.getSize();
1142 for (int idx = 0; idx < size; idx++) {
1143 Location loc1 = comp1.get(idx);
1144 Location loc2 = comp2.get(idx);
1146 Descriptor desc1 = loc1.getDescriptor();
1147 Descriptor desc2 = loc2.getDescriptor();
1149 if (!desc1.equals(desc2)) {
1150 throw new Error("Fail to compare " + comp1 + " and " + comp2);
1153 String symbol1 = loc1.getLocIdentifier();
1154 String symbol2 = loc2.getLocIdentifier();
1156 SSJavaLattice<String> lattice;
1158 lattice = methodLattice;
1160 lattice = getLattice(desc1);
1163 if (symbol1.equals(symbol2)) {
1165 } else if (lattice.isGreaterThan(symbol1, symbol2)) {
1176 private void recursiveAddRelationToLattice(int idx, MethodDescriptor md,
1177 CompositeLocation srcInferLoc, CompositeLocation dstInferLoc) throws CyclicFlowException {
1179 String srcLocSymbol = srcInferLoc.get(idx).getLocIdentifier();
1180 String dstLocSymbol = dstInferLoc.get(idx).getLocIdentifier();
1182 if (srcLocSymbol.equals(dstLocSymbol)) {
1183 recursiveAddRelationToLattice(idx + 1, md, srcInferLoc, dstInferLoc);
1186 Descriptor parentDesc = srcInferLoc.get(idx).getDescriptor();
1187 LocationInfo locInfo = getLocationInfo(parentDesc);
1189 addRelationHigherToLower(getLattice(parentDesc), getLocationInfo(parentDesc), srcLocSymbol,
1195 private void analyzeLatticeMethodInvocationNode(MethodDescriptor mdCaller,
1196 SSJavaLattice<String> methodLattice, MethodLocationInfo methodInfo)
1197 throws CyclicFlowException {
1199 // the transformation for a call site propagates all relations between
1200 // parameters from the callee
1201 // if the method is virtual, it also grab all relations from any possible
1204 Set<MethodInvokeNode> setMethodInvokeNode =
1205 mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller);
1207 if (setMethodInvokeNode != null) {
1209 for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) {
1210 MethodInvokeNode min = (MethodInvokeNode) iterator.next();
1211 MethodDescriptor mdCallee = min.getMethod();
1212 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
1213 if (mdCallee.isStatic()) {
1214 setPossibleCallees.add(mdCallee);
1216 Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getMethods(mdCallee);
1217 // removes method descriptors that are not invoked by the caller
1218 calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller));
1219 setPossibleCallees.addAll(calleeSet);
1222 for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
1223 MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
1224 propagateRelationToCaller(min, mdCaller, possibleMdCallee, methodLattice, methodInfo);
1232 private void propagateRelationToCaller(MethodInvokeNode min, MethodDescriptor mdCaller,
1233 MethodDescriptor possibleMdCallee, SSJavaLattice<String> methodLattice,
1234 MethodLocationInfo methodInfo) throws CyclicFlowException {
1236 SSJavaLattice<String> calleeLattice = getMethodLattice(possibleMdCallee);
1237 MethodLocationInfo calleeLocInfo = getMethodLocationInfo(possibleMdCallee);
1238 FlowGraph calleeFlowGraph = getFlowGraph(possibleMdCallee);
1240 int numParam = calleeLocInfo.getNumParam();
1241 for (int i = 0; i < numParam; i++) {
1242 CompositeLocation param1 = calleeLocInfo.getParamCompositeLocation(i);
1243 for (int k = 0; k < numParam; k++) {
1245 CompositeLocation param2 = calleeLocInfo.getParamCompositeLocation(k);
1247 if (isGreaterThan(getLattice(possibleMdCallee), param1, param2)) {
1248 NodeTupleSet argDescTupleSet1 = getNodeTupleSetByArgIdx(min, i);
1249 NodeTupleSet argDescTupleSet2 = getNodeTupleSetByArgIdx(min, k);
1251 // the callee has the relation in which param1 is higher than param2
1252 // therefore, the caller has to have the relation in which arg1 is
1255 for (Iterator<NTuple<Descriptor>> iterator = argDescTupleSet1.iterator(); iterator
1257 NTuple<Descriptor> argDescTuple1 = iterator.next();
1259 for (Iterator<NTuple<Descriptor>> iterator2 = argDescTupleSet2.iterator(); iterator2
1261 NTuple<Descriptor> argDescTuple2 = iterator2.next();
1263 // retreive inferred location by the local var descriptor
1265 NTuple<Location> tuple1 = getFlowGraph(mdCaller).getLocationTuple(argDescTuple1);
1266 NTuple<Location> tuple2 = getFlowGraph(mdCaller).getLocationTuple(argDescTuple2);
1268 // CompositeLocation higherInferLoc =
1269 // methodInfo.getInferLocation(argTuple1.get(0));
1270 // CompositeLocation lowerInferLoc =
1271 // methodInfo.getInferLocation(argTuple2.get(0));
1273 CompositeLocation inferLoc1 = generateInferredCompositeLocation(methodInfo, tuple1);
1274 CompositeLocation inferLoc2 = generateInferredCompositeLocation(methodInfo, tuple2);
1276 // addRelation(methodLattice, methodInfo, inferLoc1, inferLoc2);
1278 addFlowGraphEdge(mdCaller, argDescTuple1, argDescTuple2);
1291 private CompositeLocation generateInferredCompositeLocation(MethodLocationInfo methodInfo,
1292 NTuple<Location> tuple) {
1294 // first, retrieve inferred location by the local var descriptor
1295 CompositeLocation inferLoc = new CompositeLocation();
1297 CompositeLocation localVarInferLoc =
1298 methodInfo.getInferLocation(tuple.get(0).getLocDescriptor());
1300 localVarInferLoc.get(0).setLocDescriptor(tuple.get(0).getLocDescriptor());
1302 for (int i = 0; i < localVarInferLoc.getSize(); i++) {
1303 inferLoc.addLocation(localVarInferLoc.get(i));
1306 for (int i = 1; i < tuple.size(); i++) {
1307 Location cur = tuple.get(i);
1308 Descriptor enclosingDesc = cur.getDescriptor();
1309 Descriptor curDesc = cur.getLocDescriptor();
1311 Location inferLocElement;
1312 if (curDesc == null) {
1313 // in this case, we have a newly generated location.
1314 inferLocElement = new Location(enclosingDesc, cur.getLocIdentifier());
1316 String fieldLocSymbol =
1317 getLocationInfo(enclosingDesc).getInferLocation(curDesc).get(0).getLocIdentifier();
1318 inferLocElement = new Location(enclosingDesc, fieldLocSymbol);
1319 inferLocElement.setLocDescriptor(curDesc);
1322 inferLoc.addLocation(inferLocElement);
1326 assert (inferLoc.get(0).getLocDescriptor().getSymbol() == inferLoc.get(0).getLocIdentifier());
1330 private void addRelation(SSJavaLattice<String> methodLattice, MethodLocationInfo methodInfo,
1331 CompositeLocation srcInferLoc, CompositeLocation dstInferLoc) throws CyclicFlowException {
1333 System.out.println("addRelation --- srcInferLoc=" + srcInferLoc + " dstInferLoc="
1335 String srcLocalLocSymbol = srcInferLoc.get(0).getLocIdentifier();
1336 String dstLocalLocSymbol = dstInferLoc.get(0).getLocIdentifier();
1338 if (srcInferLoc.getSize() == 1 && dstInferLoc.getSize() == 1) {
1339 // add a new relation to the local lattice
1340 addRelationHigherToLower(methodLattice, methodInfo, srcLocalLocSymbol, dstLocalLocSymbol);
1341 } else if (srcInferLoc.getSize() > 1 && dstInferLoc.getSize() > 1) {
1342 // both src and dst have assigned to a composite location
1344 if (!srcLocalLocSymbol.equals(dstLocalLocSymbol)) {
1345 addRelationHigherToLower(methodLattice, methodInfo, srcLocalLocSymbol, dstLocalLocSymbol);
1347 recursivelyAddRelation(1, srcInferLoc, dstInferLoc);
1350 // either src or dst has assigned to a composite location
1351 if (!srcLocalLocSymbol.equals(dstLocalLocSymbol)) {
1352 addRelationHigherToLower(methodLattice, methodInfo, srcLocalLocSymbol, dstLocalLocSymbol);
1356 System.out.println();
1360 public LocationInfo getLocationInfo(Descriptor d) {
1361 if (d instanceof MethodDescriptor) {
1362 return getMethodLocationInfo((MethodDescriptor) d);
1364 return getFieldLocationInfo((ClassDescriptor) d);
1368 private MethodLocationInfo getMethodLocationInfo(MethodDescriptor md) {
1370 if (!mapMethodDescToMethodLocationInfo.containsKey(md)) {
1371 mapMethodDescToMethodLocationInfo.put(md, new MethodLocationInfo(md));
1374 return mapMethodDescToMethodLocationInfo.get(md);
1378 private LocationInfo getFieldLocationInfo(ClassDescriptor cd) {
1380 if (!mapClassToLocationInfo.containsKey(cd)) {
1381 mapClassToLocationInfo.put(cd, new LocationInfo(cd));
1384 return mapClassToLocationInfo.get(cd);
1388 private void addRelationToLattice(MethodDescriptor md, SSJavaLattice<String> methodLattice,
1389 MethodLocationInfo methodInfo, FlowNode srcNode, FlowNode dstNode) throws CyclicFlowException {
1391 System.out.println();
1392 System.out.println("### addRelationToLattice src=" + srcNode + " dst=" + dstNode);
1394 // add a new binary relation of dstNode < srcNode
1395 FlowGraph flowGraph = getFlowGraph(md);
1397 System.out.println("***** src composite case::");
1398 calculateCompositeLocation(flowGraph, methodLattice, methodInfo, srcNode, null);
1400 CompositeLocation srcInferLoc =
1401 generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(srcNode));
1402 CompositeLocation dstInferLoc =
1403 generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(dstNode));
1404 addRelation(methodLattice, methodInfo, srcInferLoc, dstInferLoc);
1405 } catch (CyclicFlowException e) {
1406 // there is a cyclic value flow... try to calculate a composite location
1407 // for the destination node
1408 System.out.println("***** dst composite case::");
1409 calculateCompositeLocation(flowGraph, methodLattice, methodInfo, dstNode, srcNode);
1410 CompositeLocation srcInferLoc =
1411 generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(srcNode));
1412 CompositeLocation dstInferLoc =
1413 generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(dstNode));
1415 addRelation(methodLattice, methodInfo, srcInferLoc, dstInferLoc);
1416 } catch (CyclicFlowException e1) {
1417 throw new Error("Failed to merge cyclic value flows into a shared location.");
1423 private void recursivelyAddRelation(int idx, CompositeLocation srcInferLoc,
1424 CompositeLocation dstInferLoc) throws CyclicFlowException {
1426 String srcLocSymbol = srcInferLoc.get(idx).getLocIdentifier();
1427 String dstLocSymbol = dstInferLoc.get(idx).getLocIdentifier();
1429 Descriptor parentDesc = srcInferLoc.get(idx).getDescriptor();
1431 if (srcLocSymbol.equals(dstLocSymbol)) {
1432 // check if it is the case of shared location
1433 if (srcInferLoc.getSize() == (idx + 1) && dstInferLoc.getSize() == (idx + 1)) {
1434 Location inferLocElement = srcInferLoc.get(idx);
1435 System.out.println("SET SHARED LOCATION=" + inferLocElement);
1436 getLattice(inferLocElement.getDescriptor())
1437 .addSharedLoc(inferLocElement.getLocIdentifier());
1438 } else if (srcInferLoc.getSize() > (idx + 1) && dstInferLoc.getSize() > (idx + 1)) {
1439 recursivelyAddRelation(idx + 1, srcInferLoc, dstInferLoc);
1442 addRelationHigherToLower(getLattice(parentDesc), getLocationInfo(parentDesc), srcLocSymbol,
1447 private void recursivelyAddCompositeRelation(MethodDescriptor md, FlowGraph flowGraph,
1448 MethodLocationInfo methodInfo, FlowNode srcNode, FlowNode dstNode, Descriptor srcDesc,
1449 Descriptor dstDesc) throws CyclicFlowException {
1451 CompositeLocation inferSrcLoc;
1452 CompositeLocation inferDstLoc = methodInfo.getInferLocation(dstDesc);
1454 if (srcNode.getDescTuple().size() > 1) {
1456 inferSrcLoc = new CompositeLocation();
1458 NTuple<Location> locTuple = flowGraph.getLocationTuple(srcNode);
1459 for (int i = 0; i < locTuple.size(); i++) {
1460 inferSrcLoc.addLocation(locTuple.get(i));
1464 inferSrcLoc = methodInfo.getInferLocation(srcDesc);
1467 if (dstNode.getDescTuple().size() > 1) {
1469 inferDstLoc = new CompositeLocation();
1471 NTuple<Location> locTuple = flowGraph.getLocationTuple(dstNode);
1472 for (int i = 0; i < locTuple.size(); i++) {
1473 inferDstLoc.addLocation(locTuple.get(i));
1477 inferDstLoc = methodInfo.getInferLocation(dstDesc);
1480 recursiveAddRelationToLattice(1, md, inferSrcLoc, inferDstLoc);
1483 private void addPrefixMapping(Map<NTuple<Location>, Set<NTuple<Location>>> map,
1484 NTuple<Location> prefix, NTuple<Location> element) {
1486 if (!map.containsKey(prefix)) {
1487 map.put(prefix, new HashSet<NTuple<Location>>());
1489 map.get(prefix).add(element);
1492 private boolean calculateCompositeLocation(FlowGraph flowGraph,
1493 SSJavaLattice<String> methodLattice, MethodLocationInfo methodInfo, FlowNode flowNode,
1494 FlowNode srcNode) throws CyclicFlowException {
1496 Descriptor localVarDesc = flowNode.getDescTuple().get(0);
1497 NTuple<Location> flowNodelocTuple = flowGraph.getLocationTuple(flowNode);
1499 if (localVarDesc.equals(methodInfo.getMethodDesc())) {
1503 Set<FlowNode> inNodeSet = flowGraph.getIncomingFlowNodeSet(flowNode);
1504 Set<FlowNode> reachableNodeSet = flowGraph.getReachableFlowNodeSet(flowNode);
1506 Map<NTuple<Location>, Set<NTuple<Location>>> mapPrefixToIncomingLocTupleSet =
1507 new HashMap<NTuple<Location>, Set<NTuple<Location>>>();
1509 List<NTuple<Location>> prefixList = new ArrayList<NTuple<Location>>();
1511 for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
1512 FlowNode inNode = (FlowNode) iterator.next();
1513 NTuple<Location> inNodeTuple = flowGraph.getLocationTuple(inNode);
1515 CompositeLocation inNodeInferredLoc =
1516 generateInferredCompositeLocation(methodInfo, inNodeTuple);
1518 NTuple<Location> inNodeInferredLocTuple = inNodeInferredLoc.getTuple();
1520 for (int i = 1; i < inNodeInferredLocTuple.size(); i++) {
1521 NTuple<Location> prefix = inNodeInferredLocTuple.subList(0, i);
1522 if (!prefixList.contains(prefix)) {
1523 prefixList.add(prefix);
1525 addPrefixMapping(mapPrefixToIncomingLocTupleSet, prefix, inNodeInferredLocTuple);
1529 Collections.sort(prefixList, new Comparator<NTuple<Location>>() {
1530 public int compare(NTuple<Location> arg0, NTuple<Location> arg1) {
1531 int s0 = arg0.size();
1532 int s1 = arg1.size();
1535 } else if (s0 == s1) {
1543 // System.out.println("prefixList=" + prefixList);
1544 // System.out.println("reachableNodeSet=" + reachableNodeSet);
1546 // find out reachable nodes that have the longest common prefix
1547 for (int i = 0; i < prefixList.size(); i++) {
1548 NTuple<Location> curPrefix = prefixList.get(i);
1549 Set<NTuple<Location>> reachableCommonPrefixSet = new HashSet<NTuple<Location>>();
1551 for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
1552 FlowNode reachableNode = (FlowNode) iterator2.next();
1553 NTuple<Location> reachLocTuple = flowGraph.getLocationTuple(reachableNode);
1554 CompositeLocation reachLocInferLoc =
1555 generateInferredCompositeLocation(methodInfo, reachLocTuple);
1556 if (reachLocInferLoc.getTuple().startsWith(curPrefix)) {
1557 reachableCommonPrefixSet.add(reachLocTuple);
1561 if (!reachableCommonPrefixSet.isEmpty()) {
1562 // found reachable nodes that start with the prefix curPrefix
1563 // need to assign a composite location
1565 // first, check if there are more than one the set of locations that has
1566 // the same length of the longest reachable prefix, no way to assign
1567 // a composite location to the input local var
1568 prefixSanityCheck(prefixList, i, flowGraph, reachableNodeSet);
1570 Set<NTuple<Location>> incomingCommonPrefixSet =
1571 mapPrefixToIncomingLocTupleSet.get(curPrefix);
1573 int idx = curPrefix.size();
1574 NTuple<Location> element = incomingCommonPrefixSet.iterator().next();
1575 Descriptor desc = element.get(idx).getDescriptor();
1577 SSJavaLattice<String> lattice = getLattice(desc);
1578 LocationInfo locInfo = getLocationInfo(desc);
1580 CompositeLocation inferLocation =
1581 generateInferredCompositeLocation(methodInfo, flowNodelocTuple);
1583 // methodInfo.getInferLocation(localVarDesc);
1584 CompositeLocation newInferLocation = new CompositeLocation();
1586 if (inferLocation.getTuple().startsWith(curPrefix)) {
1587 // the same infer location is already existed. no need to do
1589 System.out.println("NO ATTEMPT TO MAKE A COMPOSITE LOCATION curPrefix=" + curPrefix);
1591 // TODO: refactoring!
1592 if (srcNode != null) {
1593 CompositeLocation newLoc = new CompositeLocation();
1594 String newLocSymbol = "Loc" + (SSJavaLattice.seed++);
1595 for (int locIdx = 0; locIdx < curPrefix.size(); locIdx++) {
1596 newLoc.addLocation(curPrefix.get(locIdx));
1598 Location newLocationElement = new Location(desc, newLocSymbol);
1599 newLoc.addLocation(newLocationElement);
1601 Descriptor srcLocalVar = srcNode.getDescTuple().get(0);
1602 methodInfo.mapDescriptorToLocation(srcLocalVar, newLoc.clone());
1603 addMapLocSymbolToInferredLocation(methodInfo.getMethodDesc(), srcLocalVar, newLoc);
1604 methodInfo.removeMaplocalVarToLocSet(srcLocalVar);
1606 // add the field/var descriptor to the set of the location symbol
1607 int lastIdx = srcNode.getDescTuple().size() - 1;
1608 Descriptor lastFlowNodeDesc = srcNode.getDescTuple().get(lastIdx);
1609 NTuple<Location> srcNodelocTuple = flowGraph.getLocationTuple(srcNode);
1610 Descriptor enclosinglastLastFlowNodeDesc = srcNodelocTuple.get(lastIdx).getDescriptor();
1612 CompositeLocation newlyInferredLocForFlowNode =
1613 generateInferredCompositeLocation(methodInfo, srcNodelocTuple);
1614 Location lastInferLocElement =
1615 newlyInferredLocForFlowNode.get(newlyInferredLocForFlowNode.getSize() - 1);
1616 Descriptor enclosingLastInferLocElement = lastInferLocElement.getDescriptor();
1618 // getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToDescSet(
1619 // lastInferLocElement.getLocIdentifier(), lastFlowNodeDesc);
1620 getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToRelatedInferLoc(
1621 lastInferLocElement.getLocIdentifier(), enclosinglastLastFlowNodeDesc,
1624 System.out.println("@@@@@@@ ASSIGN " + newLoc + " to SRC=" + srcNode);
1629 // assign a new composite location
1631 // String oldMethodLocationSymbol =
1632 // inferLocation.get(0).getLocIdentifier();
1633 String newLocSymbol = "Loc" + (SSJavaLattice.seed++);
1634 for (int locIdx = 0; locIdx < curPrefix.size(); locIdx++) {
1635 newInferLocation.addLocation(curPrefix.get(locIdx));
1637 Location newLocationElement = new Location(desc, newLocSymbol);
1638 newInferLocation.addLocation(newLocationElement);
1640 // maps local variable to location types of the common prefix
1641 methodInfo.mapDescriptorToLocation(localVarDesc, newInferLocation.clone());
1643 // methodInfo.mapDescriptorToLocation(localVarDesc, newInferLocation);
1644 addMapLocSymbolToInferredLocation(methodInfo.getMethodDesc(), localVarDesc,
1646 methodInfo.removeMaplocalVarToLocSet(localVarDesc);
1648 // add the field/var descriptor to the set of the location symbol
1649 int lastIdx = flowNode.getDescTuple().size() - 1;
1650 Descriptor lastFlowNodeDesc = flowNode.getDescTuple().get(lastIdx);
1651 Descriptor enclosinglastLastFlowNodeDesc = flowNodelocTuple.get(lastIdx).getDescriptor();
1653 CompositeLocation newlyInferredLocForFlowNode =
1654 generateInferredCompositeLocation(methodInfo, flowNodelocTuple);
1655 Location lastInferLocElement =
1656 newlyInferredLocForFlowNode.get(newlyInferredLocForFlowNode.getSize() - 1);
1657 Descriptor enclosingLastInferLocElement = lastInferLocElement.getDescriptor();
1659 // getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToDescSet(
1660 // lastInferLocElement.getLocIdentifier(), lastFlowNodeDesc);
1661 getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToRelatedInferLoc(
1662 lastInferLocElement.getLocIdentifier(), enclosinglastLastFlowNodeDesc,
1665 // clean up the previous location
1666 // Location prevInferLocElement =
1667 // inferLocation.get(inferLocation.getSize() - 1);
1668 // Descriptor prevEnclosingDesc = prevInferLocElement.getDescriptor();
1670 // SSJavaLattice<String> targetLattice;
1671 // LocationInfo targetInfo;
1672 // if (prevEnclosingDesc.equals(methodInfo.getMethodDesc())) {
1673 // targetLattice = methodLattice;
1674 // targetInfo = methodInfo;
1676 // targetLattice = getLattice(prevInferLocElement.getDescriptor());
1677 // targetInfo = getLocationInfo(prevInferLocElement.getDescriptor());
1680 // Set<Pair<Descriptor, Descriptor>> associstedDescSet =
1681 // targetInfo.getRelatedInferLocSet(prevInferLocElement.getLocIdentifier());
1683 // if (associstedDescSet.size() == 1) {
1684 // targetLattice.remove(prevInferLocElement.getLocIdentifier());
1686 // associstedDescSet.remove(lastFlowNodeDesc);
1691 System.out.println("curPrefix=" + curPrefix);
1692 System.out.println("ASSIGN NEW COMPOSITE LOCATION =" + newInferLocation + " to "
1695 String newlyInsertedLocName =
1696 newInferLocation.get(newInferLocation.getSize() - 1).getLocIdentifier();
1698 System.out.println("-- add in-flow");
1699 for (Iterator iterator = incomingCommonPrefixSet.iterator(); iterator.hasNext();) {
1700 NTuple<Location> tuple = (NTuple<Location>) iterator.next();
1701 Location loc = tuple.get(idx);
1702 String higher = loc.getLocIdentifier();
1703 addRelationHigherToLower(lattice, locInfo, higher, newlyInsertedLocName);
1706 System.out.println("-- add out flow");
1707 for (Iterator iterator = reachableCommonPrefixSet.iterator(); iterator.hasNext();) {
1708 NTuple<Location> tuple = (NTuple<Location>) iterator.next();
1709 if (tuple.size() > idx) {
1710 Location loc = tuple.get(idx);
1711 String lower = loc.getLocIdentifier();
1713 // locInfo.getFieldInferLocation(loc.getLocDescriptor()).getLocIdentifier();
1714 addRelationHigherToLower(lattice, locInfo, newlyInsertedLocName, lower);
1727 private void addMapLocSymbolToInferredLocation(MethodDescriptor md, Descriptor localVar,
1728 CompositeLocation inferLoc) {
1730 Location locElement = inferLoc.get((inferLoc.getSize() - 1));
1731 Descriptor enclosingDesc = locElement.getDescriptor();
1732 LocationInfo locInfo = getLocationInfo(enclosingDesc);
1733 locInfo.addMapLocSymbolToRelatedInferLoc(locElement.getLocIdentifier(), md, localVar);
1736 private boolean isCompositeLocation(CompositeLocation cl) {
1737 return cl.getSize() > 1;
1740 private boolean containsNonPrimitiveElement(Set<Descriptor> descSet) {
1741 for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
1742 Descriptor desc = (Descriptor) iterator.next();
1744 if (desc.equals(LocationInference.GLOBALDESC)) {
1746 } else if (desc instanceof VarDescriptor) {
1747 if (!((VarDescriptor) desc).getType().isPrimitive()) {
1750 } else if (desc instanceof FieldDescriptor) {
1751 if (!((FieldDescriptor) desc).getType().isPrimitive()) {
1760 private void addRelationHigherToLower(SSJavaLattice<String> lattice, LocationInfo locInfo,
1761 String higher, String lower) throws CyclicFlowException {
1763 System.out.println("---addRelationHigherToLower " + higher + " -> " + lower
1764 + " to the lattice of " + locInfo.getDescIdentifier());
1765 // if (higher.equals(lower) && lattice.isSharedLoc(higher)) {
1768 Set<String> cycleElementSet = lattice.getPossibleCycleElements(higher, lower);
1770 boolean hasNonPrimitiveElement = false;
1771 for (Iterator iterator = cycleElementSet.iterator(); iterator.hasNext();) {
1772 String cycleElementLocSymbol = (String) iterator.next();
1774 Set<Descriptor> descSet = locInfo.getDescSet(cycleElementLocSymbol);
1775 if (containsNonPrimitiveElement(descSet)) {
1776 hasNonPrimitiveElement = true;
1781 if (hasNonPrimitiveElement) {
1782 System.out.println("#Check cycle= " + lower + " < " + higher + " cycleElementSet="
1784 // if there is non-primitive element in the cycle, no way to merge cyclic
1785 // elements into the shared location
1786 throw new CyclicFlowException();
1789 if (cycleElementSet.size() > 0) {
1791 String newSharedLoc = "SharedLoc" + (SSJavaLattice.seed++);
1793 System.out.println("---ASSIGN NEW SHARED LOC=" + newSharedLoc + " to " + cycleElementSet);
1794 lattice.mergeIntoSharedLocation(cycleElementSet, newSharedLoc);
1796 for (Iterator iterator = cycleElementSet.iterator(); iterator.hasNext();) {
1797 String oldLocSymbol = (String) iterator.next();
1799 Set<Pair<Descriptor, Descriptor>> inferLocSet = locInfo.getRelatedInferLocSet(oldLocSymbol);
1800 System.out.println("---update related locations=" + inferLocSet);
1801 for (Iterator iterator2 = inferLocSet.iterator(); iterator2.hasNext();) {
1802 Pair<Descriptor, Descriptor> pair = (Pair<Descriptor, Descriptor>) iterator2.next();
1803 Descriptor enclosingDesc = pair.getFirst();
1804 Descriptor desc = pair.getSecond();
1806 CompositeLocation inferLoc;
1807 if (curMethodInfo.md.equals(enclosingDesc)) {
1808 inferLoc = curMethodInfo.getInferLocation(desc);
1810 inferLoc = getLocationInfo(enclosingDesc).getInferLocation(desc);
1813 Location locElement = inferLoc.get(inferLoc.getSize() - 1);
1815 locElement.setLocIdentifier(newSharedLoc);
1816 locInfo.addMapLocSymbolToRelatedInferLoc(newSharedLoc, enclosingDesc, desc);
1818 if (curMethodInfo.md.equals(enclosingDesc)) {
1819 inferLoc = curMethodInfo.getInferLocation(desc);
1821 inferLoc = getLocationInfo(enclosingDesc).getInferLocation(desc);
1823 System.out.println("---New Infer Loc=" + inferLoc);
1826 locInfo.removeRelatedInferLocSet(oldLocSymbol, newSharedLoc);
1830 lattice.addSharedLoc(newSharedLoc);
1832 } else if (!lattice.isGreaterThan(higher, lower)) {
1833 lattice.addRelationHigherToLower(higher, lower);
1837 private void replaceOldLocWithNewLoc(SSJavaLattice<String> methodLattice, String oldLocSymbol,
1838 String newLocSymbol) {
1840 if (methodLattice.containsKey(oldLocSymbol)) {
1841 methodLattice.substituteLocation(oldLocSymbol, newLocSymbol);
1846 private void prefixSanityCheck(List<NTuple<Location>> prefixList, int curIdx,
1847 FlowGraph flowGraph, Set<FlowNode> reachableNodeSet) {
1849 NTuple<Location> curPrefix = prefixList.get(curIdx);
1851 for (int i = curIdx + 1; i < prefixList.size(); i++) {
1852 NTuple<Location> prefixTuple = prefixList.get(i);
1854 if (curPrefix.startsWith(prefixTuple)) {
1858 for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
1859 FlowNode reachableNode = (FlowNode) iterator2.next();
1860 NTuple<Location> reachLocTuple = flowGraph.getLocationTuple(reachableNode);
1861 if (reachLocTuple.startsWith(prefixTuple)) {
1863 throw new Error("Failed to generate a composite location");
1869 public boolean isPrimitiveLocalVariable(FlowNode node) {
1870 VarDescriptor varDesc = (VarDescriptor) node.getDescTuple().get(0);
1871 return varDesc.getType().isPrimitive();
1874 private SSJavaLattice<String> getLattice(Descriptor d) {
1875 if (d instanceof MethodDescriptor) {
1876 return getMethodLattice((MethodDescriptor) d);
1878 return getFieldLattice((ClassDescriptor) d);
1882 private SSJavaLattice<String> getMethodLattice(MethodDescriptor md) {
1883 if (!md2lattice.containsKey(md)) {
1884 md2lattice.put(md, new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM));
1886 return md2lattice.get(md);
1889 private void setMethodLattice(MethodDescriptor md, SSJavaLattice<String> lattice) {
1890 md2lattice.put(md, lattice);
1893 private void extractRelationFromFieldFlows(ClassDescriptor cd, FlowNode srcNode,
1894 FlowNode dstNode, int idx) throws CyclicFlowException {
1896 if (srcNode.getDescTuple().get(idx).equals(dstNode.getDescTuple().get(idx))
1897 && srcNode.getDescTuple().size() > (idx + 1) && dstNode.getDescTuple().size() > (idx + 1)) {
1898 // value flow between fields: we don't need to add a binary relation
1901 Descriptor desc = srcNode.getDescTuple().get(idx);
1902 ClassDescriptor classDesc;
1905 classDesc = ((VarDescriptor) desc).getType().getClassDesc();
1907 classDesc = ((FieldDescriptor) desc).getType().getClassDesc();
1910 extractRelationFromFieldFlows(classDesc, srcNode, dstNode, idx + 1);
1914 Descriptor srcFieldDesc = srcNode.getDescTuple().get(idx);
1915 Descriptor dstFieldDesc = dstNode.getDescTuple().get(idx);
1917 // add a new binary relation of dstNode < srcNode
1918 SSJavaLattice<String> fieldLattice = getFieldLattice(cd);
1919 LocationInfo fieldInfo = getFieldLocationInfo(cd);
1921 String srcSymbol = fieldInfo.getFieldInferLocation(srcFieldDesc).getLocIdentifier();
1922 String dstSymbol = fieldInfo.getFieldInferLocation(dstFieldDesc).getLocIdentifier();
1924 addRelationHigherToLower(fieldLattice, fieldInfo, srcSymbol, dstSymbol);
1930 public SSJavaLattice<String> getFieldLattice(ClassDescriptor cd) {
1931 if (!cd2lattice.containsKey(cd)) {
1932 cd2lattice.put(cd, new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM));
1934 return cd2lattice.get(cd);
1937 public LinkedList<MethodDescriptor> computeMethodList() {
1939 Set<MethodDescriptor> toSort = new HashSet<MethodDescriptor>();
1943 Set<MethodDescriptor> visited = new HashSet<MethodDescriptor>();
1944 Set<MethodDescriptor> reachableCallee = new HashSet<MethodDescriptor>();
1946 while (!toAnalyzeIsEmpty()) {
1947 ClassDescriptor cd = toAnalyzeNext();
1949 setupToAnalazeMethod(cd);
1950 toanalyzeMethodList.removeAll(visited);
1952 while (!toAnalyzeMethodIsEmpty()) {
1953 MethodDescriptor md = toAnalyzeMethodNext();
1954 if ((!visited.contains(md))
1955 && (ssjava.needTobeAnnotated(md) || reachableCallee.contains(md))) {
1957 // creates a mapping from a method descriptor to virtual methods
1958 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
1959 if (md.isStatic()) {
1960 setPossibleCallees.add(md);
1962 setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md));
1965 Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getCalleeSet(md);
1966 Set<MethodDescriptor> needToAnalyzeCalleeSet = new HashSet<MethodDescriptor>();
1968 for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) {
1969 MethodDescriptor calleemd = (MethodDescriptor) iterator.next();
1970 if ((!ssjava.isTrustMethod(calleemd))
1971 && (!ssjava.isSSJavaUtil(calleemd.getClassDesc()))) {
1972 if (!visited.contains(calleemd)) {
1973 toanalyzeMethodList.add(calleemd);
1975 reachableCallee.add(calleemd);
1976 needToAnalyzeCalleeSet.add(calleemd);
1980 mapMethodToCalleeSet.put(md, needToAnalyzeCalleeSet);
1989 return ssjava.topologicalSort(toSort);
1993 public void constructFlowGraph() {
1995 LinkedList<MethodDescriptor> methodDescList = computeMethodList();
1997 while (!methodDescList.isEmpty()) {
1998 MethodDescriptor md = methodDescList.removeLast();
1999 if (state.SSJAVADEBUG) {
2000 System.out.println();
2001 System.out.println("SSJAVA: Constructing a flow graph: " + md);
2003 // creates a mapping from a parameter descriptor to its index
2004 Map<Descriptor, Integer> mapParamDescToIdx = new HashMap<Descriptor, Integer>();
2006 if (!md.isStatic()) {
2008 mapParamDescToIdx.put(md.getThis(), 0);
2011 for (int i = 0; i < md.numParameters(); i++) {
2012 Descriptor paramDesc = (Descriptor) md.getParameter(i);
2013 mapParamDescToIdx.put(paramDesc, new Integer(i + offset));
2016 FlowGraph fg = new FlowGraph(md, mapParamDescToIdx);
2017 mapMethodDescriptorToFlowGraph.put(md, fg);
2019 analyzeMethodBody(md.getClassDesc(), md);
2022 _debug_printGraph();
2026 private void analyzeMethodBody(ClassDescriptor cd, MethodDescriptor md) {
2027 BlockNode bn = state.getMethodBody(md);
2028 NodeTupleSet implicitFlowTupleSet = new NodeTupleSet();
2029 analyzeFlowBlockNode(md, md.getParameterTable(), bn, implicitFlowTupleSet);
2032 private void analyzeFlowBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn,
2033 NodeTupleSet implicitFlowTupleSet) {
2035 bn.getVarTable().setParent(nametable);
2036 for (int i = 0; i < bn.size(); i++) {
2037 BlockStatementNode bsn = bn.get(i);
2038 analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet);
2043 private void analyzeBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
2044 BlockStatementNode bsn, NodeTupleSet implicitFlowTupleSet) {
2046 switch (bsn.kind()) {
2047 case Kind.BlockExpressionNode:
2048 analyzeBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn, implicitFlowTupleSet);
2051 case Kind.DeclarationNode:
2052 analyzeFlowDeclarationNode(md, nametable, (DeclarationNode) bsn, implicitFlowTupleSet);
2055 case Kind.IfStatementNode:
2056 analyzeFlowIfStatementNode(md, nametable, (IfStatementNode) bsn, implicitFlowTupleSet);
2060 analyzeFlowLoopNode(md, nametable, (LoopNode) bsn, implicitFlowTupleSet);
2063 case Kind.ReturnNode:
2064 analyzeFlowReturnNode(md, nametable, (ReturnNode) bsn, implicitFlowTupleSet);
2067 case Kind.SubBlockNode:
2068 analyzeFlowSubBlockNode(md, nametable, (SubBlockNode) bsn, implicitFlowTupleSet);
2071 case Kind.ContinueBreakNode:
2074 case Kind.SwitchStatementNode:
2075 analyzeSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn);
2082 private void analyzeSwitchStatementNode(MethodDescriptor md, SymbolTable nametable,
2083 SwitchStatementNode bsn) {
2084 // TODO Auto-generated method stub
2087 private void analyzeFlowSubBlockNode(MethodDescriptor md, SymbolTable nametable,
2088 SubBlockNode sbn, NodeTupleSet implicitFlowTupleSet) {
2089 analyzeFlowBlockNode(md, nametable, sbn.getBlockNode(), implicitFlowTupleSet);
2092 private void analyzeFlowReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode rn,
2093 NodeTupleSet implicitFlowTupleSet) {
2095 ExpressionNode returnExp = rn.getReturnExpression();
2097 if (returnExp != null) {
2098 NodeTupleSet nodeSet = new NodeTupleSet();
2099 analyzeFlowExpressionNode(md, nametable, returnExp, nodeSet, false);
2101 FlowGraph fg = getFlowGraph(md);
2103 // annotate the elements of the node set as the return location
2104 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
2105 NTuple<Descriptor> returnDescTuple = (NTuple<Descriptor>) iterator.next();
2106 fg.addReturnFlowNode(returnDescTuple);
2107 for (Iterator iterator2 = implicitFlowTupleSet.iterator(); iterator2.hasNext();) {
2108 NTuple<Descriptor> implicitFlowDescTuple = (NTuple<Descriptor>) iterator2.next();
2109 fg.addValueFlowEdge(implicitFlowDescTuple, returnDescTuple);
2116 private void analyzeFlowLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln,
2117 NodeTupleSet implicitFlowTupleSet) {
2119 if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) {
2121 NodeTupleSet condTupleNode = new NodeTupleSet();
2122 analyzeFlowExpressionNode(md, nametable, ln.getCondition(), condTupleNode, null,
2123 implicitFlowTupleSet, false);
2124 condTupleNode.addTupleSet(implicitFlowTupleSet);
2126 // add edges from condNodeTupleSet to all nodes of conditional nodes
2127 analyzeFlowBlockNode(md, nametable, ln.getBody(), condTupleNode);
2130 // check 'for loop' case
2131 BlockNode bn = ln.getInitializer();
2132 bn.getVarTable().setParent(nametable);
2133 for (int i = 0; i < bn.size(); i++) {
2134 BlockStatementNode bsn = bn.get(i);
2135 analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet);
2138 NodeTupleSet condTupleNode = new NodeTupleSet();
2139 analyzeFlowExpressionNode(md, bn.getVarTable(), ln.getCondition(), condTupleNode, null,
2140 implicitFlowTupleSet, false);
2141 condTupleNode.addTupleSet(implicitFlowTupleSet);
2143 analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(), condTupleNode);
2144 analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(), condTupleNode);
2150 private void analyzeFlowIfStatementNode(MethodDescriptor md, SymbolTable nametable,
2151 IfStatementNode isn, NodeTupleSet implicitFlowTupleSet) {
2153 NodeTupleSet condTupleNode = new NodeTupleSet();
2154 analyzeFlowExpressionNode(md, nametable, isn.getCondition(), condTupleNode, null,
2155 implicitFlowTupleSet, false);
2157 // NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
2158 // for (Iterator<NTuple<Descriptor>> idxIter = condTupleNode.iterator(); idxIter.hasNext();) {
2159 // NTuple<Descriptor> tuple = idxIter.next();
2160 // addFlowGraphEdge(md, tuple, interTuple);
2163 // for (Iterator<NTuple<Descriptor>> idxIter = implicitFlowTupleSet.iterator(); idxIter.hasNext();) {
2164 // NTuple<Descriptor> tuple = idxIter.next();
2165 // addFlowGraphEdge(md, tuple, interTuple);
2168 // NodeTupleSet newImplicitSet = new NodeTupleSet();
2169 // newImplicitSet.addTuple(interTuple);
2170 // analyzeFlowBlockNode(md, nametable, isn.getTrueBlock(), newImplicitSet);
2172 // if (isn.getFalseBlock() != null) {
2173 // analyzeFlowBlockNode(md, nametable, isn.getFalseBlock(), newImplicitSet);
2176 // add edges from condNodeTupleSet to all nodes of conditional nodes
2177 condTupleNode.addTupleSet(implicitFlowTupleSet);
2178 analyzeFlowBlockNode(md, nametable, isn.getTrueBlock(), condTupleNode);
2180 if (isn.getFalseBlock() != null) {
2181 analyzeFlowBlockNode(md, nametable, isn.getFalseBlock(), condTupleNode);
2186 private void analyzeFlowDeclarationNode(MethodDescriptor md, SymbolTable nametable,
2187 DeclarationNode dn, NodeTupleSet implicitFlowTupleSet) {
2189 VarDescriptor vd = dn.getVarDescriptor();
2190 mapDescToDefinitionLine.put(vd, dn.getNumLine());
2191 NTuple<Descriptor> tupleLHS = new NTuple<Descriptor>();
2193 FlowNode fn = getFlowGraph(md).createNewFlowNode(tupleLHS);
2194 fn.setDeclarationNode();
2196 if (dn.getExpression() != null) {
2198 NodeTupleSet tupleSetRHS = new NodeTupleSet();
2199 analyzeFlowExpressionNode(md, nametable, dn.getExpression(), tupleSetRHS, null,
2200 implicitFlowTupleSet, false);
2202 // add a new flow edge from rhs to lhs
2203 for (Iterator<NTuple<Descriptor>> iter = tupleSetRHS.iterator(); iter.hasNext();) {
2204 NTuple<Descriptor> from = iter.next();
2205 addFlowGraphEdge(md, from, tupleLHS);
2212 private void analyzeBlockExpressionNode(MethodDescriptor md, SymbolTable nametable,
2213 BlockExpressionNode ben, NodeTupleSet implicitFlowTupleSet) {
2214 analyzeFlowExpressionNode(md, nametable, ben.getExpression(), null, null, implicitFlowTupleSet,
2218 private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
2219 ExpressionNode en, NodeTupleSet nodeSet, boolean isLHS) {
2220 return analyzeFlowExpressionNode(md, nametable, en, nodeSet, null, new NodeTupleSet(), isLHS);
2223 private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
2224 ExpressionNode en, NodeTupleSet nodeSet, NTuple<Descriptor> base,
2225 NodeTupleSet implicitFlowTupleSet, boolean isLHS) {
2227 // note that expression node can create more than one flow node
2228 // nodeSet contains of flow nodes
2229 // base is always assigned to null except the case of a name node!
2231 NTuple<Descriptor> flowTuple;
2233 switch (en.kind()) {
2235 case Kind.AssignmentNode:
2236 analyzeFlowAssignmentNode(md, nametable, (AssignmentNode) en, nodeSet, base,
2237 implicitFlowTupleSet);
2240 case Kind.FieldAccessNode:
2242 analyzeFlowFieldAccessNode(md, nametable, (FieldAccessNode) en, nodeSet, base,
2243 implicitFlowTupleSet, isLHS);
2244 if (flowTuple != null) {
2245 nodeSet.addTuple(flowTuple);
2250 NodeTupleSet nameNodeSet = new NodeTupleSet();
2252 analyzeFlowNameNode(md, nametable, (NameNode) en, nameNodeSet, base, implicitFlowTupleSet);
2253 if (flowTuple != null) {
2254 nodeSet.addTuple(flowTuple);
2259 analyzeFlowOpNode(md, nametable, (OpNode) en, nodeSet, implicitFlowTupleSet);
2262 case Kind.CreateObjectNode:
2263 analyzeCreateObjectNode(md, nametable, (CreateObjectNode) en);
2266 case Kind.ArrayAccessNode:
2267 analyzeFlowArrayAccessNode(md, nametable, (ArrayAccessNode) en, nodeSet, isLHS);
2270 case Kind.LiteralNode:
2271 analyzeLiteralNode(md, nametable, (LiteralNode) en);
2274 case Kind.MethodInvokeNode:
2275 analyzeFlowMethodInvokeNode(md, nametable, (MethodInvokeNode) en, nodeSet,
2276 implicitFlowTupleSet);
2279 case Kind.TertiaryNode:
2280 analyzeFlowTertiaryNode(md, nametable, (TertiaryNode) en, nodeSet, implicitFlowTupleSet);
2284 analyzeFlowCastNode(md, nametable, (CastNode) en, nodeSet, base, implicitFlowTupleSet);
2286 // case Kind.InstanceOfNode:
2287 // checkInstanceOfNode(md, nametable, (InstanceOfNode) en, td);
2290 // case Kind.ArrayInitializerNode:
2291 // checkArrayInitializerNode(md, nametable, (ArrayInitializerNode) en,
2295 // case Kind.ClassTypeNode:
2296 // checkClassTypeNode(md, nametable, (ClassTypeNode) en, td);
2299 // case Kind.OffsetNode:
2300 // checkOffsetNode(md, nametable, (OffsetNode)en, td);
2308 private void analyzeFlowCastNode(MethodDescriptor md, SymbolTable nametable, CastNode cn,
2309 NodeTupleSet nodeSet, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
2311 analyzeFlowExpressionNode(md, nametable, cn.getExpression(), nodeSet, base,
2312 implicitFlowTupleSet, false);
2316 private void analyzeFlowTertiaryNode(MethodDescriptor md, SymbolTable nametable, TertiaryNode tn,
2317 NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
2319 NodeTupleSet tertiaryTupleNode = new NodeTupleSet();
2320 analyzeFlowExpressionNode(md, nametable, tn.getCond(), tertiaryTupleNode, null,
2321 implicitFlowTupleSet, false);
2323 // add edges from tertiaryTupleNode to all nodes of conditional nodes
2324 tertiaryTupleNode.addTupleSet(implicitFlowTupleSet);
2325 analyzeFlowExpressionNode(md, nametable, tn.getTrueExpr(), tertiaryTupleNode, null,
2326 implicitFlowTupleSet, false);
2328 analyzeFlowExpressionNode(md, nametable, tn.getFalseExpr(), tertiaryTupleNode, null,
2329 implicitFlowTupleSet, false);
2331 nodeSet.addTupleSet(tertiaryTupleNode);
2335 private void addMapCallerMethodDescToMethodInvokeNodeSet(MethodDescriptor caller,
2336 MethodInvokeNode min) {
2337 Set<MethodInvokeNode> set = mapMethodDescriptorToMethodInvokeNodeSet.get(caller);
2339 set = new HashSet<MethodInvokeNode>();
2340 mapMethodDescriptorToMethodInvokeNodeSet.put(caller, set);
2345 private void addParamNodeFlowingToReturnValue(MethodDescriptor md, FlowNode fn) {
2347 if (!mapMethodDescToParamNodeFlowsToReturnValue.containsKey(md)) {
2348 mapMethodDescToParamNodeFlowsToReturnValue.put(md, new HashSet<FlowNode>());
2350 mapMethodDescToParamNodeFlowsToReturnValue.get(md).add(fn);
2353 private Set<FlowNode> getParamNodeFlowingToReturnValue(MethodDescriptor md) {
2354 return mapMethodDescToParamNodeFlowsToReturnValue.get(md);
2357 private void analyzeFlowMethodInvokeNode(MethodDescriptor md, SymbolTable nametable,
2358 MethodInvokeNode min, NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
2360 if (nodeSet == null) {
2361 nodeSet = new NodeTupleSet();
2364 addMapCallerMethodDescToMethodInvokeNodeSet(md, min);
2366 MethodDescriptor calleeMethodDesc = min.getMethod();
2368 NameDescriptor baseName = min.getBaseName();
2369 boolean isSystemout = false;
2370 if (baseName != null) {
2371 isSystemout = baseName.getSymbol().equals("System.out");
2374 if (!ssjava.isSSJavaUtil(calleeMethodDesc.getClassDesc())
2375 && !ssjava.isTrustMethod(calleeMethodDesc) && !isSystemout) {
2377 FlowGraph calleeFlowGraph = getFlowGraph(calleeMethodDesc);
2378 Set<FlowNode> calleeReturnSet = calleeFlowGraph.getReturnNodeSet();
2380 if (min.getExpression() != null) {
2382 NodeTupleSet baseNodeSet = new NodeTupleSet();
2383 analyzeFlowExpressionNode(md, nametable, min.getExpression(), baseNodeSet, null,
2384 implicitFlowTupleSet, false);
2386 if (!min.getMethod().isStatic()) {
2387 addArgIdxMap(min, 0, baseNodeSet);
2389 for (Iterator iterator = calleeReturnSet.iterator(); iterator.hasNext();) {
2390 FlowNode returnNode = (FlowNode) iterator.next();
2391 NTuple<Descriptor> returnDescTuple = returnNode.getDescTuple();
2392 if (returnDescTuple.startsWith(calleeMethodDesc.getThis())) {
2393 // the location type of the return value is started with 'this'
2395 for (Iterator<NTuple<Descriptor>> baseIter = baseNodeSet.iterator(); baseIter
2397 NTuple<Descriptor> baseTuple = baseIter.next();
2398 NTuple<Descriptor> inFlowTuple = new NTuple<Descriptor>(baseTuple.getList());
2399 inFlowTuple.addAll(returnDescTuple.subList(1, returnDescTuple.size()));
2400 nodeSet.addTuple(inFlowTuple);
2403 Set<FlowNode> inFlowSet = calleeFlowGraph.getIncomingFlowNodeSet(returnNode);
2404 for (Iterator iterator2 = inFlowSet.iterator(); iterator2.hasNext();) {
2405 FlowNode inFlowNode = (FlowNode) iterator2.next();
2406 if (inFlowNode.getDescTuple().startsWith(calleeMethodDesc.getThis())) {
2407 nodeSet.addTupleSet(baseNodeSet);
2415 // analyze parameter flows
2417 if (min.numArgs() > 0) {
2420 if (min.getMethod().isStatic()) {
2426 for (int i = 0; i < min.numArgs(); i++) {
2427 ExpressionNode en = min.getArg(i);
2428 int idx = i + offset;
2429 NodeTupleSet argTupleSet = new NodeTupleSet();
2430 analyzeFlowExpressionNode(md, nametable, en, argTupleSet, true);
2431 // if argument is liternal node, argTuple is set to NULL.
2432 addArgIdxMap(min, idx, argTupleSet);
2433 FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx);
2434 if (hasInFlowTo(calleeFlowGraph, paramNode, calleeReturnSet)
2435 || calleeMethodDesc.getModifiers().isNative()) {
2436 addParamNodeFlowingToReturnValue(calleeMethodDesc, paramNode);
2437 nodeSet.addTupleSet(argTupleSet);
2447 private boolean hasInFlowTo(FlowGraph fg, FlowNode inNode, Set<FlowNode> nodeSet) {
2448 // return true if inNode has in-flows to nodeSet
2449 Set<FlowNode> reachableSet = fg.getReachableFlowNodeSet(inNode);
2450 for (Iterator iterator = reachableSet.iterator(); iterator.hasNext();) {
2451 FlowNode fn = (FlowNode) iterator.next();
2452 if (nodeSet.contains(fn)) {
2459 private NodeTupleSet getNodeTupleSetByArgIdx(MethodInvokeNode min, int idx) {
2460 return mapMethodInvokeNodeToArgIdxMap.get(min).get(new Integer(idx));
2463 private void addArgIdxMap(MethodInvokeNode min, int idx, NodeTupleSet tupleSet) {
2464 Map<Integer, NodeTupleSet> mapIdxToTupleSet = mapMethodInvokeNodeToArgIdxMap.get(min);
2465 if (mapIdxToTupleSet == null) {
2466 mapIdxToTupleSet = new HashMap<Integer, NodeTupleSet>();
2467 mapMethodInvokeNodeToArgIdxMap.put(min, mapIdxToTupleSet);
2469 mapIdxToTupleSet.put(new Integer(idx), tupleSet);
2472 private void analyzeFlowMethodParameters(MethodDescriptor callermd, SymbolTable nametable,
2473 MethodInvokeNode min, NodeTupleSet nodeSet) {
2475 if (min.numArgs() > 0) {
2478 if (min.getMethod().isStatic()) {
2482 // NTuple<Descriptor> thisArgTuple = new NTuple<Descriptor>();
2483 // thisArgTuple.add(callermd.getThis());
2484 // NodeTupleSet argTupleSet = new NodeTupleSet();
2485 // argTupleSet.addTuple(thisArgTuple);
2486 // addArgIdxMap(min, 0, argTupleSet);
2487 // nodeSet.addTuple(thisArgTuple);
2490 for (int i = 0; i < min.numArgs(); i++) {
2491 ExpressionNode en = min.getArg(i);
2492 NodeTupleSet argTupleSet = new NodeTupleSet();
2493 analyzeFlowExpressionNode(callermd, nametable, en, argTupleSet, false);
2494 // if argument is liternal node, argTuple is set to NULL.
2495 addArgIdxMap(min, i + offset, argTupleSet);
2496 nodeSet.addTupleSet(argTupleSet);
2503 private void analyzeLiteralNode(MethodDescriptor md, SymbolTable nametable, LiteralNode en) {
2507 private void analyzeFlowArrayAccessNode(MethodDescriptor md, SymbolTable nametable,
2508 ArrayAccessNode aan, NodeTupleSet nodeSet, boolean isLHS) {
2510 NodeTupleSet expNodeTupleSet = new NodeTupleSet();
2511 NTuple<Descriptor> base =
2512 analyzeFlowExpressionNode(md, nametable, aan.getExpression(), expNodeTupleSet, isLHS);
2514 NodeTupleSet idxNodeTupleSet = new NodeTupleSet();
2515 analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, isLHS);
2518 // need to create an edge from idx to array
2519 for (Iterator<NTuple<Descriptor>> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) {
2520 NTuple<Descriptor> idxTuple = idxIter.next();
2521 for (Iterator<NTuple<Descriptor>> arrIter = expNodeTupleSet.iterator(); arrIter.hasNext();) {
2522 NTuple<Descriptor> arrTuple = arrIter.next();
2523 getFlowGraph(md).addValueFlowEdge(idxTuple, arrTuple);
2527 nodeSet.addTupleSet(expNodeTupleSet);
2529 nodeSet.addTupleSet(expNodeTupleSet);
2530 nodeSet.addTupleSet(idxNodeTupleSet);
2534 private void analyzeCreateObjectNode(MethodDescriptor md, SymbolTable nametable,
2535 CreateObjectNode en) {
2536 // TODO Auto-generated method stub
2540 private void analyzeFlowOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on,
2541 NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
2543 NodeTupleSet leftOpSet = new NodeTupleSet();
2544 NodeTupleSet rightOpSet = new NodeTupleSet();
2547 analyzeFlowExpressionNode(md, nametable, on.getLeft(), leftOpSet, null, implicitFlowTupleSet,
2550 if (on.getRight() != null) {
2552 analyzeFlowExpressionNode(md, nametable, on.getRight(), rightOpSet, null,
2553 implicitFlowTupleSet, false);
2556 Operation op = on.getOp();
2558 switch (op.getOp()) {
2560 case Operation.UNARYPLUS:
2561 case Operation.UNARYMINUS:
2562 case Operation.LOGIC_NOT:
2564 nodeSet.addTupleSet(leftOpSet);
2567 case Operation.LOGIC_OR:
2568 case Operation.LOGIC_AND:
2569 case Operation.COMP:
2570 case Operation.BIT_OR:
2571 case Operation.BIT_XOR:
2572 case Operation.BIT_AND:
2573 case Operation.ISAVAILABLE:
2574 case Operation.EQUAL:
2575 case Operation.NOTEQUAL:
2582 case Operation.MULT:
2585 case Operation.LEFTSHIFT:
2586 case Operation.RIGHTSHIFT:
2587 case Operation.URIGHTSHIFT:
2589 // there are two operands
2590 nodeSet.addTupleSet(leftOpSet);
2591 nodeSet.addTupleSet(rightOpSet);
2595 throw new Error(op.toString());
2600 private NTuple<Descriptor> analyzeFlowNameNode(MethodDescriptor md, SymbolTable nametable,
2601 NameNode nn, NodeTupleSet nodeSet, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
2604 base = new NTuple<Descriptor>();
2607 NameDescriptor nd = nn.getName();
2609 if (nd.getBase() != null) {
2611 analyzeFlowExpressionNode(md, nametable, nn.getExpression(), nodeSet, base,
2612 implicitFlowTupleSet, false);
2614 // base node has the top location
2618 String varname = nd.toString();
2619 if (varname.equals("this")) {
2621 base.add(md.getThis());
2625 Descriptor d = (Descriptor) nametable.get(varname);
2627 if (d instanceof VarDescriptor) {
2628 VarDescriptor vd = (VarDescriptor) d;
2630 } else if (d instanceof FieldDescriptor) {
2631 // the type of field descriptor has a location!
2632 FieldDescriptor fd = (FieldDescriptor) d;
2633 if (fd.isStatic()) {
2635 // if it is 'static final', no need to have flow node for the TOP
2639 // if 'static', assign the default GLOBAL LOCATION to the first
2640 // element of the tuple
2641 base.add(GLOBALDESC);
2644 // the location of field access starts from this, followed by field
2646 base.add(md.getThis());
2650 } else if (d == null) {
2651 // access static field
2652 base.add(GLOBALDESC);
2653 // base.add(nn.getField());
2656 // FieldDescriptor fd = nn.getField();addFlowGraphEdge
2658 // MethodLattice<String> localLattice = ssjava.getMethodLattice(md);
2659 // String globalLocId = localLattice.getGlobalLoc();
2660 // if (globalLocId == null) {
2662 // Error("Method lattice does not define global variable location at "
2663 // + generateErrorMessage(md.getClassDesc(), nn));
2665 // loc.addLocation(new Location(md, globalLocId));
2667 // Location fieldLoc = (Location) fd.getType().getExtension();
2668 // loc.addLocation(fieldLoc);
2674 getFlowGraph(md).createNewFlowNode(base);
2680 private NTuple<Descriptor> analyzeFlowFieldAccessNode(MethodDescriptor md, SymbolTable nametable,
2681 FieldAccessNode fan, NodeTupleSet nodeSet, NTuple<Descriptor> base,
2682 NodeTupleSet implicitFlowTupleSet, boolean isLHS) {
2684 ExpressionNode left = fan.getExpression();
2685 TypeDescriptor ltd = left.getType();
2686 FieldDescriptor fd = fan.getField();
2688 String varName = null;
2689 if (left.kind() == Kind.NameNode) {
2690 NameDescriptor nd = ((NameNode) left).getName();
2691 varName = nd.toString();
2694 if (ltd.isClassNameRef() || (varName != null && varName.equals("this"))) {
2695 // using a class name directly or access using this
2696 if (fd.isStatic() && fd.isFinal()) {
2701 NodeTupleSet idxNodeTupleSet = new NodeTupleSet();
2703 if (left instanceof ArrayAccessNode) {
2705 ArrayAccessNode aan = (ArrayAccessNode) left;
2706 left = aan.getExpression();
2707 analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, base,
2708 implicitFlowTupleSet, isLHS);
2710 nodeSet.addTupleSet(idxNodeTupleSet);
2713 analyzeFlowExpressionNode(md, nametable, left, nodeSet, base, implicitFlowTupleSet, isLHS);
2716 // in this case, field is TOP location
2720 NTuple<Descriptor> flowFieldTuple = new NTuple<Descriptor>(base.toList());
2722 if (!left.getType().isPrimitive()) {
2724 if (!fd.getSymbol().equals("length")) {
2725 // array.length access, just have the location of the array
2726 flowFieldTuple.add(fd);
2727 nodeSet.removeTuple(base);
2731 getFlowGraph(md).createNewFlowNode(flowFieldTuple);
2734 for (Iterator<NTuple<Descriptor>> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) {
2735 NTuple<Descriptor> idxTuple = idxIter.next();
2736 getFlowGraph(md).addValueFlowEdge(idxTuple, flowFieldTuple);
2740 return flowFieldTuple;
2746 private void debug_printTreeNode(TreeNode tn) {
2748 System.out.println("DEBUG: " + tn.printNode(0) + " line#=" + tn.getNumLine());
2752 private void analyzeFlowAssignmentNode(MethodDescriptor md, SymbolTable nametable,
2753 AssignmentNode an, NodeTupleSet nodeSet, NTuple<Descriptor> base,
2754 NodeTupleSet implicitFlowTupleSet) {
2756 NodeTupleSet nodeSetRHS = new NodeTupleSet();
2757 NodeTupleSet nodeSetLHS = new NodeTupleSet();
2759 boolean postinc = true;
2760 if (an.getOperation().getBaseOp() == null
2761 || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
2762 .getBaseOp().getOp() != Operation.POSTDEC)) {
2765 // if LHS is array access node, need to capture value flows between an array
2766 // and its index value
2767 analyzeFlowExpressionNode(md, nametable, an.getDest(), nodeSetLHS, null, implicitFlowTupleSet,
2771 // analyze value flows of rhs expression
2772 analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null, implicitFlowTupleSet,
2775 // System.out.println("-analyzeFlowAssignmentNode=" + an.printNode(0));
2776 // System.out.println("-nodeSetLHS=" + nodeSetLHS);
2777 // System.out.println("-nodeSetRHS=" + nodeSetRHS);
2778 // System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet);
2779 // System.out.println("-");
2781 if (an.getOperation().getOp() >= 2 && an.getOperation().getOp() <= 12) {
2782 // if assignment contains OP+EQ operator, creates edges from LHS to LHS
2784 for (Iterator<NTuple<Descriptor>> iter = nodeSetLHS.iterator(); iter.hasNext();) {
2785 NTuple<Descriptor> fromTuple = iter.next();
2786 for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
2787 NTuple<Descriptor> toTuple = iter2.next();
2788 addFlowGraphEdge(md, fromTuple, toTuple);
2793 // creates edges from RHS to LHS
2794 NTuple<Descriptor> interTuple = null;
2795 if (nodeSetRHS.size() > 1) {
2796 interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
2799 for (Iterator<NTuple<Descriptor>> iter = nodeSetRHS.iterator(); iter.hasNext();) {
2800 NTuple<Descriptor> fromTuple = iter.next();
2801 for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
2802 NTuple<Descriptor> toTuple = iter2.next();
2803 addFlowGraphEdge(md, fromTuple, interTuple, toTuple);
2807 // creates edges from implicitFlowTupleSet to LHS
2808 for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
2809 NTuple<Descriptor> fromTuple = iter.next();
2810 for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
2811 NTuple<Descriptor> toTuple = iter2.next();
2812 addFlowGraphEdge(md, fromTuple, toTuple);
2819 for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
2820 NTuple<Descriptor> tuple = iter2.next();
2821 addFlowGraphEdge(md, tuple, tuple);
2824 // creates edges from implicitFlowTupleSet to LHS
2825 for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
2826 NTuple<Descriptor> fromTuple = iter.next();
2827 for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
2828 NTuple<Descriptor> toTuple = iter2.next();
2829 addFlowGraphEdge(md, fromTuple, toTuple);
2835 if (nodeSet != null) {
2836 nodeSet.addTupleSet(nodeSetLHS);
2840 public FlowGraph getFlowGraph(MethodDescriptor md) {
2841 return mapMethodDescriptorToFlowGraph.get(md);
2844 private boolean addFlowGraphEdge(MethodDescriptor md, NTuple<Descriptor> from,
2845 NTuple<Descriptor> to) {
2846 FlowGraph graph = getFlowGraph(md);
2847 graph.addValueFlowEdge(from, to);
2851 private void addFlowGraphEdge(MethodDescriptor md, NTuple<Descriptor> from,
2852 NTuple<Descriptor> inter, NTuple<Descriptor> to) {
2854 FlowGraph graph = getFlowGraph(md);
2856 if (inter != null) {
2857 graph.addValueFlowEdge(from, inter);
2858 graph.addValueFlowEdge(inter, to);
2860 graph.addValueFlowEdge(from, to);
2865 public void _debug_printGraph() {
2866 Set<MethodDescriptor> keySet = mapMethodDescriptorToFlowGraph.keySet();
2868 for (Iterator<MethodDescriptor> iterator = keySet.iterator(); iterator.hasNext();) {
2869 MethodDescriptor md = (MethodDescriptor) iterator.next();
2870 FlowGraph fg = mapMethodDescriptorToFlowGraph.get(md);
2873 } catch (IOException e) {
2874 e.printStackTrace();
2882 class CyclicFlowException extends Exception {
2886 class InterDescriptor extends Descriptor {
2888 public InterDescriptor(String name) {