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.SwitchBlockNode;
51 import IR.Tree.SwitchStatementNode;
52 import IR.Tree.TertiaryNode;
53 import IR.Tree.TreeNode;
56 public class LocationInference {
59 SSJavaAnalysis ssjava;
61 List<ClassDescriptor> toanalyzeList;
62 List<MethodDescriptor> toanalyzeMethodList;
63 Map<MethodDescriptor, FlowGraph> mapMethodDescriptorToFlowGraph;
65 // map a method descriptor to its set of parameter descriptors
66 Map<MethodDescriptor, Set<Descriptor>> mapMethodDescriptorToParamDescSet;
68 // keep current descriptors to visit in fixed-point interprocedural analysis,
69 private Stack<MethodDescriptor> methodDescriptorsToVisitStack;
71 // map a class descriptor to a field lattice
72 private Map<ClassDescriptor, SSJavaLattice<String>> cd2lattice;
74 // map a method descriptor to a method lattice
75 private Map<MethodDescriptor, SSJavaLattice<String>> md2lattice;
77 // map a method/class descriptor to a hierarchy graph
78 private Map<Descriptor, HierarchyGraph> mapDescriptorToHierarchyGraph;
80 // map a method/class descriptor to a skeleton hierarchy graph
81 private Map<Descriptor, HierarchyGraph> mapDescriptorToSkeletonHierarchyGraph;
83 private Map<Descriptor, HierarchyGraph> mapDescriptorToSimpleHierarchyGraph;
85 // map a method/class descriptor to a skeleton hierarchy graph with combination nodes
86 private Map<Descriptor, HierarchyGraph> mapDescriptorToCombineSkeletonHierarchyGraph;
88 // map a method descriptor to a method summary
89 private Map<MethodDescriptor, MethodSummary> mapMethodDescToMethodSummary;
91 // map a descriptor to a simple lattice
92 private Map<Descriptor, SSJavaLattice<String>> mapDescriptorToSimpleLattice;
94 // map a method descriptor to the set of method invocation nodes which are
95 // invoked by the method descriptor
96 private Map<MethodDescriptor, Set<MethodInvokeNode>> mapMethodDescriptorToMethodInvokeNodeSet;
98 private Map<MethodInvokeNode, Map<Integer, NodeTupleSet>> mapMethodInvokeNodeToArgIdxMap;
100 private Map<MethodInvokeNode, NTuple<Descriptor>> mapMethodInvokeNodeToBaseTuple;
102 private Map<MethodDescriptor, MethodLocationInfo> mapMethodDescToMethodLocationInfo;
104 private Map<ClassDescriptor, LocationInfo> mapClassToLocationInfo;
106 private Map<MethodDescriptor, Set<MethodDescriptor>> mapMethodToCalleeSet;
108 private Map<MethodDescriptor, Set<FlowNode>> mapMethodDescToParamNodeFlowsToReturnValue;
110 private Map<String, Vector<String>> mapFileNameToLineVector;
112 private Map<Descriptor, Integer> mapDescToDefinitionLine;
114 public static final String GLOBALLOC = "GLOBALLOC";
116 public static final String TOPLOC = "TOPLOC";
118 public static final String INTERLOC = "INTERLOC";
120 public static final Descriptor GLOBALDESC = new NameDescriptor(GLOBALLOC);
122 public static final Descriptor TOPDESC = new NameDescriptor(TOPLOC);
124 public static String newline = System.getProperty("line.separator");
126 LocationInfo curMethodInfo;
128 boolean debug = true;
130 private static int locSeed = 0;
132 public LocationInference(SSJavaAnalysis ssjava, State state) {
133 this.ssjava = ssjava;
135 this.toanalyzeList = new ArrayList<ClassDescriptor>();
136 this.toanalyzeMethodList = new ArrayList<MethodDescriptor>();
137 this.mapMethodDescriptorToFlowGraph = new HashMap<MethodDescriptor, FlowGraph>();
138 this.cd2lattice = new HashMap<ClassDescriptor, SSJavaLattice<String>>();
139 this.md2lattice = new HashMap<MethodDescriptor, SSJavaLattice<String>>();
140 this.methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
141 this.mapMethodDescriptorToMethodInvokeNodeSet =
142 new HashMap<MethodDescriptor, Set<MethodInvokeNode>>();
143 this.mapMethodInvokeNodeToArgIdxMap =
144 new HashMap<MethodInvokeNode, Map<Integer, NodeTupleSet>>();
145 this.mapMethodDescToMethodLocationInfo = new HashMap<MethodDescriptor, MethodLocationInfo>();
146 this.mapMethodToCalleeSet = new HashMap<MethodDescriptor, Set<MethodDescriptor>>();
147 this.mapClassToLocationInfo = new HashMap<ClassDescriptor, LocationInfo>();
149 this.mapFileNameToLineVector = new HashMap<String, Vector<String>>();
150 this.mapDescToDefinitionLine = new HashMap<Descriptor, Integer>();
151 this.mapMethodDescToParamNodeFlowsToReturnValue =
152 new HashMap<MethodDescriptor, Set<FlowNode>>();
154 this.mapDescriptorToHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
155 this.mapMethodDescToMethodSummary = new HashMap<MethodDescriptor, MethodSummary>();
156 this.mapMethodInvokeNodeToBaseTuple = new HashMap<MethodInvokeNode, NTuple<Descriptor>>();
158 this.mapDescriptorToSkeletonHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
159 this.mapDescriptorToCombineSkeletonHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
160 this.mapDescriptorToSimpleHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
162 this.mapDescriptorToSimpleLattice = new HashMap<Descriptor, SSJavaLattice<String>>();
166 public void setupToAnalyze() {
167 SymbolTable classtable = state.getClassSymbolTable();
168 toanalyzeList.clear();
169 toanalyzeList.addAll(classtable.getValueSet());
170 // Collections.sort(toanalyzeList, new Comparator<ClassDescriptor>() {
171 // public int compare(ClassDescriptor o1, ClassDescriptor o2) {
172 // return o1.getClassName().compareToIgnoreCase(o2.getClassName());
177 public void setupToAnalazeMethod(ClassDescriptor cd) {
179 SymbolTable methodtable = cd.getMethodTable();
180 toanalyzeMethodList.clear();
181 toanalyzeMethodList.addAll(methodtable.getValueSet());
182 Collections.sort(toanalyzeMethodList, new Comparator<MethodDescriptor>() {
183 public int compare(MethodDescriptor o1, MethodDescriptor o2) {
184 return o1.getSymbol().compareToIgnoreCase(o2.getSymbol());
189 public boolean toAnalyzeMethodIsEmpty() {
190 return toanalyzeMethodList.isEmpty();
193 public boolean toAnalyzeIsEmpty() {
194 return toanalyzeList.isEmpty();
197 public ClassDescriptor toAnalyzeNext() {
198 return toanalyzeList.remove(0);
201 public MethodDescriptor toAnalyzeMethodNext() {
202 return toanalyzeMethodList.remove(0);
205 public void inference() {
207 // 1) construct value flow graph
208 constructFlowGraph();
210 constructHierarchyGraph();
212 debug_writeHierarchyDotFiles();
214 simplifyHierarchyGraph();
216 debug_writeSimpleHierarchyDotFiles();
218 constructSkeletonHierarchyGraph();
220 debug_writeSkeletonHierarchyDotFiles();
222 insertCombinationNodes();
224 debug_writeSkeletonCombinationHierarchyDotFiles();
228 debug_writeLattices();
232 // 2) construct lattices
237 // 3) check properties
240 // calculate RETURNLOC,PCLOC
241 calculateExtraLocations();
243 debug_writeLatticeDotFile();
245 // 4) generate annotated source codes
246 generateAnnoatedCode();
250 private void debug_writeLattices() {
252 Set<Descriptor> keySet = mapDescriptorToSimpleLattice.keySet();
253 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
254 Descriptor key = (Descriptor) iterator.next();
255 SSJavaLattice<String> simpleLattice = mapDescriptorToSimpleLattice.get(key);
256 if (key instanceof ClassDescriptor) {
257 ssjava.writeLatticeDotFile((ClassDescriptor) key, null, simpleLattice, "_SIMPLE");
258 } else if (key instanceof MethodDescriptor) {
259 MethodDescriptor md = (MethodDescriptor) key;
260 ssjava.writeLatticeDotFile(md.getClassDesc(), md, simpleLattice, "_SIMPLE");
264 Set<ClassDescriptor> cdKeySet = cd2lattice.keySet();
265 for (Iterator iterator = cdKeySet.iterator(); iterator.hasNext();) {
266 ClassDescriptor cd = (ClassDescriptor) iterator.next();
267 ssjava.writeLatticeDotFile(cd, null, cd2lattice.get(cd));
270 Set<MethodDescriptor> mdKeySet = md2lattice.keySet();
271 for (Iterator iterator = mdKeySet.iterator(); iterator.hasNext();) {
272 MethodDescriptor md = (MethodDescriptor) iterator.next();
273 ssjava.writeLatticeDotFile(md.getClassDesc(), md, md2lattice.get(md));
278 private void buildLattice() {
280 BuildLattice buildLattice = new BuildLattice(this);
282 Set<Descriptor> keySet = mapDescriptorToCombineSkeletonHierarchyGraph.keySet();
283 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
284 Descriptor desc = (Descriptor) iterator.next();
286 HierarchyGraph graph = getSkeletonCombinationHierarchyGraph(desc);
287 SSJavaLattice<String> simpleLattice = buildLattice.buildLattice(graph);
289 addMapDescToSimpleLattice(desc, simpleLattice);
291 HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc);
292 System.out.println("## insertIntermediateNodesToStraightLine:"
293 + simpleHierarchyGraph.getName());
294 SSJavaLattice<String> lattice =
295 buildLattice.insertIntermediateNodesToStraightLine(desc, simpleLattice);
296 lattice.removeRedundantEdges();
298 if (desc instanceof ClassDescriptor) {
300 cd2lattice.put((ClassDescriptor) desc, lattice);
301 // ssjava.writeLatticeDotFile((ClassDescriptor) desc, null, lattice);
302 } else if (desc instanceof MethodDescriptor) {
304 md2lattice.put((MethodDescriptor) desc, lattice);
305 MethodDescriptor md = (MethodDescriptor) desc;
306 ClassDescriptor cd = md.getClassDesc();
307 // ssjava.writeLatticeDotFile(cd, md, lattice);
310 // System.out.println("\nSSJAVA: Insering Combination Nodes:" + desc);
311 // HierarchyGraph skeletonGraph = getSkeletonHierarchyGraph(desc);
312 // HierarchyGraph skeletonGraphWithCombinationNode = skeletonGraph.clone();
313 // skeletonGraphWithCombinationNode.setName(desc + "_SC");
315 // HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc);
316 // System.out.println("Identifying Combination Nodes:");
317 // skeletonGraphWithCombinationNode.insertCombinationNodesToGraph(simpleHierarchyGraph);
318 // skeletonGraphWithCombinationNode.simplifySkeletonCombinationHierarchyGraph();
319 // mapDescriptorToCombineSkeletonHierarchyGraph.put(desc, skeletonGraphWithCombinationNode);
324 public void addMapDescToSimpleLattice(Descriptor desc, SSJavaLattice<String> lattice) {
325 mapDescriptorToSimpleLattice.put(desc, lattice);
328 public SSJavaLattice<String> getSimpleLattice(Descriptor desc) {
329 return mapDescriptorToSimpleLattice.get(desc);
332 private void simplifyHierarchyGraph() {
333 Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
334 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
335 Descriptor desc = (Descriptor) iterator.next();
336 HierarchyGraph simpleHierarchyGraph = getHierarchyGraph(desc).clone();
337 simpleHierarchyGraph.setName(desc + "_SIMPLE");
338 simpleHierarchyGraph.simplifyHierarchyGraph();
339 mapDescriptorToSimpleHierarchyGraph.put(desc, simpleHierarchyGraph);
343 private void insertCombinationNodes() {
344 Set<Descriptor> keySet = mapDescriptorToSkeletonHierarchyGraph.keySet();
345 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
346 Descriptor desc = (Descriptor) iterator.next();
347 System.out.println("\nSSJAVA: Insering Combination Nodes:" + desc);
348 HierarchyGraph skeletonGraph = getSkeletonHierarchyGraph(desc);
349 HierarchyGraph skeletonGraphWithCombinationNode = skeletonGraph.clone();
350 skeletonGraphWithCombinationNode.setName(desc + "_SC");
352 HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc);
353 System.out.println("Identifying Combination Nodes:");
354 skeletonGraphWithCombinationNode.insertCombinationNodesToGraph(simpleHierarchyGraph);
355 skeletonGraphWithCombinationNode.simplifySkeletonCombinationHierarchyGraph();
356 mapDescriptorToCombineSkeletonHierarchyGraph.put(desc, skeletonGraphWithCombinationNode);
360 private void constructSkeletonHierarchyGraph() {
361 Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
362 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
363 Descriptor desc = (Descriptor) iterator.next();
364 HierarchyGraph simpleGraph = getSimpleHierarchyGraph(desc);
365 HierarchyGraph skeletonGraph = simpleGraph.generateSkeletonGraph();
366 skeletonGraph.setMapDescToHNode(simpleGraph.getMapDescToHNode());
367 skeletonGraph.setMapHNodeToDescSet(simpleGraph.getMapHNodeToDescSet());
368 skeletonGraph.removeRedundantEdges();
369 mapDescriptorToSkeletonHierarchyGraph.put(desc, skeletonGraph);
373 private void debug_writeHierarchyDotFiles() {
375 Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
376 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
377 Descriptor desc = (Descriptor) iterator.next();
378 getHierarchyGraph(desc).writeGraph();
383 private void debug_writeSimpleHierarchyDotFiles() {
385 Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
386 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
387 Descriptor desc = (Descriptor) iterator.next();
388 getHierarchyGraph(desc).writeGraph();
389 getSimpleHierarchyGraph(desc).writeGraph();
394 private void debug_writeSkeletonHierarchyDotFiles() {
396 Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
397 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
398 Descriptor desc = (Descriptor) iterator.next();
399 getSkeletonHierarchyGraph(desc).writeGraph();
404 private void debug_writeSkeletonCombinationHierarchyDotFiles() {
406 Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
407 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
408 Descriptor desc = (Descriptor) iterator.next();
409 getSkeletonCombinationHierarchyGraph(desc).writeGraph();
414 public HierarchyGraph getSimpleHierarchyGraph(Descriptor d) {
415 return mapDescriptorToSimpleHierarchyGraph.get(d);
418 private HierarchyGraph getSkeletonHierarchyGraph(Descriptor d) {
419 if (!mapDescriptorToSkeletonHierarchyGraph.containsKey(d)) {
420 mapDescriptorToSkeletonHierarchyGraph.put(d, new HierarchyGraph(d));
422 return mapDescriptorToSkeletonHierarchyGraph.get(d);
425 public HierarchyGraph getSkeletonCombinationHierarchyGraph(Descriptor d) {
426 if (!mapDescriptorToCombineSkeletonHierarchyGraph.containsKey(d)) {
427 mapDescriptorToCombineSkeletonHierarchyGraph.put(d, new HierarchyGraph(d));
429 return mapDescriptorToCombineSkeletonHierarchyGraph.get(d);
432 private void constructHierarchyGraph() {
434 // do fixed-point analysis
437 LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
439 // Collections.sort(descriptorListToAnalyze, new
440 // Comparator<MethodDescriptor>() {
441 // public int compare(MethodDescriptor o1, MethodDescriptor o2) {
442 // return o1.getSymbol().compareToIgnoreCase(o2.getSymbol());
446 // current descriptors to visit in fixed-point interprocedural analysis,
447 // prioritized by dependency in the call graph
448 methodDescriptorsToVisitStack.clear();
450 Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
451 methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
453 while (!descriptorListToAnalyze.isEmpty()) {
454 MethodDescriptor md = descriptorListToAnalyze.removeFirst();
455 methodDescriptorsToVisitStack.add(md);
458 // analyze scheduled methods until there are no more to visit
459 while (!methodDescriptorsToVisitStack.isEmpty()) {
460 // start to analyze leaf node
461 MethodDescriptor md = methodDescriptorsToVisitStack.pop();
463 HierarchyGraph methodGraph = new HierarchyGraph(md);
464 MethodSummary methodSummary = new MethodSummary();
466 MethodLocationInfo methodInfo = new MethodLocationInfo(md);
467 curMethodInfo = methodInfo;
469 System.out.println();
470 System.out.println("SSJAVA: Construcing the hierarchy graph from " + md);
472 constructHierarchyGraph(md, methodGraph, methodSummary);
474 HierarchyGraph prevMethodGraph = getHierarchyGraph(md);
475 MethodSummary prevMethodSummary = getMethodSummary(md);
477 if ((!methodGraph.equals(prevMethodGraph)) || (!methodSummary.equals(prevMethodSummary))) {
479 mapDescriptorToHierarchyGraph.put(md, methodGraph);
480 mapMethodDescToMethodSummary.put(md, methodSummary);
482 // results for callee changed, so enqueue dependents caller for
484 Iterator<MethodDescriptor> depsItr = ssjava.getDependents(md).iterator();
485 while (depsItr.hasNext()) {
486 MethodDescriptor methodNext = depsItr.next();
487 if (!methodDescriptorsToVisitStack.contains(methodNext)
488 && methodDescriptorToVistSet.contains(methodNext)) {
489 methodDescriptorsToVisitStack.add(methodNext);
499 private HierarchyGraph getHierarchyGraph(Descriptor d) {
500 if (!mapDescriptorToHierarchyGraph.containsKey(d)) {
501 mapDescriptorToHierarchyGraph.put(d, new HierarchyGraph(d));
503 return mapDescriptorToHierarchyGraph.get(d);
506 private void constructHierarchyGraph(MethodDescriptor md, HierarchyGraph methodGraph,
507 MethodSummary methodSummary) {
509 // visit each node of method flow graph
510 FlowGraph fg = getFlowGraph(md);
511 Set<FlowNode> nodeSet = fg.getNodeSet();
513 Set<Descriptor> paramDescSet = fg.getMapParamDescToIdx().keySet();
514 for (Iterator iterator = paramDescSet.iterator(); iterator.hasNext();) {
515 Descriptor desc = (Descriptor) iterator.next();
516 methodGraph.getHNode(desc).setSkeleton(true);
519 // for the method lattice, we need to look at the first element of
520 // NTuple<Descriptor>
521 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
522 FlowNode srcNode = (FlowNode) iterator.next();
524 Set<FlowEdge> outEdgeSet = srcNode.getOutEdgeSet();
525 for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) {
526 FlowEdge outEdge = (FlowEdge) iterator2.next();
527 FlowNode dstNode = outEdge.getDst();
529 NTuple<Descriptor> srcNodeTuple = srcNode.getDescTuple();
530 NTuple<Descriptor> dstNodeTuple = dstNode.getDescTuple();
532 if (outEdge.getInitTuple().equals(srcNodeTuple)
533 && outEdge.getEndTuple().equals(dstNodeTuple)) {
535 NTuple<Descriptor> srcCurTuple = srcNode.getCurrentDescTuple();
536 NTuple<Descriptor> dstCurTuple = dstNode.getCurrentDescTuple();
538 if ((srcCurTuple.size() > 1 && dstCurTuple.size() > 1)
539 && srcCurTuple.get(0).equals(dstCurTuple.get(0))) {
541 // value flows between fields
542 Descriptor desc = srcCurTuple.get(0);
543 ClassDescriptor classDesc;
545 if (desc.equals(GLOBALDESC)) {
546 classDesc = md.getClassDesc();
548 VarDescriptor varDesc = (VarDescriptor) srcCurTuple.get(0);
549 classDesc = varDesc.getType().getClassDesc();
551 extractFlowsBetweenFields(classDesc, srcNode, dstNode, 1);
554 // value flow between local var - local var or local var - field
556 Descriptor srcDesc = srcCurTuple.get(0);
557 Descriptor dstDesc = dstCurTuple.get(0);
559 methodGraph.addEdge(srcDesc, dstDesc);
561 if (fg.isParamDesc(srcDesc)) {
562 methodGraph.setParamHNode(srcDesc);
564 if (fg.isParamDesc(dstDesc)) {
565 methodGraph.setParamHNode(dstDesc);
576 private MethodSummary getMethodSummary(MethodDescriptor md) {
577 if (!mapMethodDescToMethodSummary.containsKey(md)) {
578 mapMethodDescToMethodSummary.put(md, new MethodSummary());
580 return mapMethodDescToMethodSummary.get(md);
583 private void addMapClassDefinitionToLineNum(ClassDescriptor cd, String strLine, int lineNum) {
585 String classSymbol = cd.getSymbol();
586 int idx = classSymbol.lastIndexOf("$");
588 classSymbol = classSymbol.substring(idx + 1);
591 String pattern = "class " + classSymbol + " ";
592 if (strLine.indexOf(pattern) != -1) {
593 mapDescToDefinitionLine.put(cd, lineNum);
597 private void addMapMethodDefinitionToLineNum(Set<MethodDescriptor> methodSet, String strLine,
599 for (Iterator iterator = methodSet.iterator(); iterator.hasNext();) {
600 MethodDescriptor md = (MethodDescriptor) iterator.next();
601 String pattern = md.getMethodDeclaration();
602 if (strLine.indexOf(pattern) != -1) {
603 mapDescToDefinitionLine.put(md, lineNum);
604 methodSet.remove(md);
611 private void readOriginalSourceFiles() {
613 SymbolTable classtable = state.getClassSymbolTable();
615 Set<ClassDescriptor> classDescSet = new HashSet<ClassDescriptor>();
616 classDescSet.addAll(classtable.getValueSet());
619 // inefficient implement. it may re-visit the same file if the file
620 // contains more than one class definitions.
621 for (Iterator iterator = classDescSet.iterator(); iterator.hasNext();) {
622 ClassDescriptor cd = (ClassDescriptor) iterator.next();
624 Set<MethodDescriptor> methodSet = new HashSet<MethodDescriptor>();
625 methodSet.addAll(cd.getMethodTable().getValueSet());
627 String sourceFileName = cd.getSourceFileName();
628 Vector<String> lineVec = new Vector<String>();
630 mapFileNameToLineVector.put(sourceFileName, lineVec);
632 BufferedReader in = new BufferedReader(new FileReader(sourceFileName));
635 lineVec.add(""); // the index is started from 1.
636 while ((strLine = in.readLine()) != null) {
637 lineVec.add(lineNum, strLine);
638 addMapClassDefinitionToLineNum(cd, strLine, lineNum);
639 addMapMethodDefinitionToLineNum(methodSet, strLine, lineNum);
645 } catch (IOException e) {
651 private String generateLatticeDefinition(Descriptor desc) {
653 Set<String> sharedLocSet = new HashSet<String>();
655 SSJavaLattice<String> lattice = getLattice(desc);
656 String rtr = "@LATTICE(\"";
658 Map<String, Set<String>> map = lattice.getTable();
659 Set<String> keySet = map.keySet();
660 boolean first = true;
661 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
662 String key = (String) iterator.next();
663 if (!key.equals(lattice.getTopItem())) {
664 Set<String> connectedSet = map.get(key);
666 if (connectedSet.size() == 1) {
667 if (connectedSet.iterator().next().equals(lattice.getBottomItem())) {
675 if (lattice.isSharedLoc(key)) {
676 rtr += "," + key + "*";
681 for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) {
682 String loc = (String) iterator2.next();
683 if (!loc.equals(lattice.getBottomItem())) {
690 rtr += loc + "<" + key;
691 if (lattice.isSharedLoc(key) && (!sharedLocSet.contains(key))) {
692 rtr += "," + key + "*";
693 sharedLocSet.add(key);
695 if (lattice.isSharedLoc(loc) && (!sharedLocSet.contains(loc))) {
696 rtr += "," + loc + "*";
697 sharedLocSet.add(loc);
707 if (desc instanceof MethodDescriptor) {
708 TypeDescriptor returnType = ((MethodDescriptor) desc).getReturnType();
710 MethodLocationInfo methodLocInfo = getMethodLocationInfo((MethodDescriptor) desc);
712 if (returnType != null && (!returnType.isVoid())) {
714 "\n@RETURNLOC(\"" + generateLocationAnnoatation(methodLocInfo.getReturnLoc()) + "\")";
717 rtr += "\n@THISLOC(\"this\")";
718 rtr += "\n@GLOBALLOC(\"GLOBALLOC\")";
720 CompositeLocation pcLoc = methodLocInfo.getPCLoc();
721 if ((pcLoc != null) && (!pcLoc.get(0).isTop())) {
722 rtr += "\n@PCLOC(\"" + generateLocationAnnoatation(pcLoc) + "\")";
730 private void generateAnnoatedCode() {
732 readOriginalSourceFiles();
735 while (!toAnalyzeIsEmpty()) {
736 ClassDescriptor cd = toAnalyzeNext();
738 setupToAnalazeMethod(cd);
740 LocationInfo locInfo = mapClassToLocationInfo.get(cd);
741 String sourceFileName = cd.getSourceFileName();
743 if (cd.isInterface()) {
747 int classDefLine = mapDescToDefinitionLine.get(cd);
748 Vector<String> sourceVec = mapFileNameToLineVector.get(sourceFileName);
750 if (locInfo == null) {
751 locInfo = getLocationInfo(cd);
754 for (Iterator iter = cd.getFields(); iter.hasNext();) {
755 FieldDescriptor fieldDesc = (FieldDescriptor) iter.next();
756 if (!(fieldDesc.isStatic() && fieldDesc.isFinal())) {
757 String locIdentifier = locInfo.getFieldInferLocation(fieldDesc).getLocIdentifier();
758 if (!getLattice(cd).getElementSet().contains(locIdentifier)) {
759 getLattice(cd).put(locIdentifier);
764 String fieldLatticeDefStr = generateLatticeDefinition(cd);
765 String annoatedSrc = fieldLatticeDefStr + newline + sourceVec.get(classDefLine);
766 sourceVec.set(classDefLine, annoatedSrc);
768 // generate annotations for field declarations
769 LocationInfo fieldLocInfo = getLocationInfo(cd);
770 Map<Descriptor, CompositeLocation> inferLocMap = fieldLocInfo.getMapDescToInferLocation();
772 for (Iterator iter = cd.getFields(); iter.hasNext();) {
773 FieldDescriptor fd = (FieldDescriptor) iter.next();
775 String locAnnotationStr;
776 CompositeLocation inferLoc = inferLocMap.get(fd);
778 if (inferLoc != null) {
779 // infer loc is null if the corresponding field is static and final
780 locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")";
781 int fdLineNum = fd.getLineNum();
782 String orgFieldDeclarationStr = sourceVec.get(fdLineNum);
783 String fieldDeclaration = fd.toString();
784 fieldDeclaration = fieldDeclaration.substring(0, fieldDeclaration.length() - 1);
785 String annoatedStr = locAnnotationStr + " " + orgFieldDeclarationStr;
786 sourceVec.set(fdLineNum, annoatedStr);
791 while (!toAnalyzeMethodIsEmpty()) {
792 MethodDescriptor md = toAnalyzeMethodNext();
794 if (!ssjava.needTobeAnnotated(md)) {
798 SSJavaLattice<String> methodLattice = md2lattice.get(md);
799 if (methodLattice != null) {
801 int methodDefLine = md.getLineNum();
803 MethodLocationInfo methodLocInfo = getMethodLocationInfo(md);
805 Map<Descriptor, CompositeLocation> methodInferLocMap =
806 methodLocInfo.getMapDescToInferLocation();
807 Set<Descriptor> localVarDescSet = methodInferLocMap.keySet();
809 Set<String> localLocElementSet = methodLattice.getElementSet();
811 for (Iterator iterator = localVarDescSet.iterator(); iterator.hasNext();) {
812 Descriptor localVarDesc = (Descriptor) iterator.next();
813 CompositeLocation inferLoc = methodInferLocMap.get(localVarDesc);
815 String localLocIdentifier = inferLoc.get(0).getLocIdentifier();
816 if (!localLocElementSet.contains(localLocIdentifier)) {
817 methodLattice.put(localLocIdentifier);
820 String locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")";
822 if (!isParameter(md, localVarDesc)) {
823 if (mapDescToDefinitionLine.containsKey(localVarDesc)) {
824 int varLineNum = mapDescToDefinitionLine.get(localVarDesc);
825 String orgSourceLine = sourceVec.get(varLineNum);
827 orgSourceLine.indexOf(generateVarDeclaration((VarDescriptor) localVarDesc));
830 orgSourceLine.substring(0, idx) + locAnnotationStr + " "
831 + orgSourceLine.substring(idx);
832 sourceVec.set(varLineNum, annoatedStr);
835 String methodDefStr = sourceVec.get(methodDefLine);
838 getParamLocation(methodDefStr,
839 generateVarDeclaration((VarDescriptor) localVarDesc));
844 methodDefStr.substring(0, idx) + locAnnotationStr + " "
845 + methodDefStr.substring(idx);
846 sourceVec.set(methodDefLine, annoatedStr);
851 // check if the lattice has to have the location type for the this
854 // boolean needToAddthisRef = hasThisReference(md);
855 if (localLocElementSet.contains("this")) {
856 methodLattice.put("this");
859 String methodLatticeDefStr = generateLatticeDefinition(md);
860 String annoatedStr = methodLatticeDefStr + newline + sourceVec.get(methodDefLine);
861 sourceVec.set(methodDefLine, annoatedStr);
871 private boolean hasThisReference(MethodDescriptor md) {
873 FlowGraph fg = getFlowGraph(md);
874 Set<FlowNode> nodeSet = fg.getNodeSet();
875 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
876 FlowNode flowNode = (FlowNode) iterator.next();
877 if (flowNode.getDescTuple().get(0).equals(md.getThis())) {
885 private int getParamLocation(String methodStr, String paramStr) {
887 String pattern = paramStr + ",";
889 int idx = methodStr.indexOf(pattern);
893 pattern = paramStr + ")";
894 return methodStr.indexOf(pattern);
899 private String generateVarDeclaration(VarDescriptor varDesc) {
901 TypeDescriptor td = varDesc.getType();
902 String rtr = td.toString();
904 for (int i = 0; i < td.getArrayCount(); i++) {
908 rtr += " " + varDesc.getName();
913 private String generateLocationAnnoatation(CompositeLocation loc) {
916 Location methodLoc = loc.get(0);
917 rtr += methodLoc.getLocIdentifier();
919 for (int i = 1; i < loc.getSize(); i++) {
920 Location element = loc.get(i);
921 rtr += "," + element.getDescriptor().getSymbol() + "." + element.getLocIdentifier();
927 private boolean isParameter(MethodDescriptor md, Descriptor localVarDesc) {
928 return getFlowGraph(md).isParamDesc(localVarDesc);
931 private String extractFileName(String fileName) {
932 int idx = fileName.lastIndexOf("/");
936 return fileName.substring(idx + 1);
941 private void codeGen() {
943 Set<String> originalFileNameSet = mapFileNameToLineVector.keySet();
944 for (Iterator iterator = originalFileNameSet.iterator(); iterator.hasNext();) {
945 String orgFileName = (String) iterator.next();
946 String outputFileName = extractFileName(orgFileName);
948 Vector<String> sourceVec = mapFileNameToLineVector.get(orgFileName);
952 FileWriter fileWriter = new FileWriter("./infer/" + outputFileName);
953 BufferedWriter out = new BufferedWriter(fileWriter);
955 for (int i = 0; i < sourceVec.size(); i++) {
956 out.write(sourceVec.get(i));
960 } catch (IOException e) {
968 private void simplifyLattices() {
972 while (!toAnalyzeIsEmpty()) {
973 ClassDescriptor cd = toAnalyzeNext();
974 setupToAnalazeMethod(cd);
976 SSJavaLattice<String> classLattice = cd2lattice.get(cd);
977 if (classLattice != null) {
978 System.out.println("@@@check lattice=" + cd);
979 checkLatticeProperty(cd, classLattice);
982 while (!toAnalyzeMethodIsEmpty()) {
983 MethodDescriptor md = toAnalyzeMethodNext();
984 SSJavaLattice<String> methodLattice = md2lattice.get(md);
985 if (methodLattice != null) {
986 System.out.println("@@@check lattice=" + md);
987 checkLatticeProperty(md, methodLattice);
994 while (!toAnalyzeIsEmpty()) {
995 ClassDescriptor cd = toAnalyzeNext();
997 setupToAnalazeMethod(cd);
999 SSJavaLattice<String> classLattice = cd2lattice.get(cd);
1000 if (classLattice != null) {
1001 classLattice.removeRedundantEdges();
1004 while (!toAnalyzeMethodIsEmpty()) {
1005 MethodDescriptor md = toAnalyzeMethodNext();
1006 SSJavaLattice<String> methodLattice = md2lattice.get(md);
1007 if (methodLattice != null) {
1008 methodLattice.removeRedundantEdges();
1015 private boolean checkLatticeProperty(Descriptor d, SSJavaLattice<String> lattice) {
1016 // if two elements has the same incoming node set,
1017 // we need to merge two elements ...
1020 boolean isModified = false;
1022 isUpdated = removeNodeSharingSameIncomingNodes(d, lattice);
1023 if (!isModified && isUpdated) {
1026 } while (isUpdated);
1031 private boolean removeNodeSharingSameIncomingNodes(Descriptor d, SSJavaLattice<String> lattice) {
1032 LocationInfo locInfo = getLocationInfo(d);
1033 Map<String, Set<String>> map = lattice.getIncomingElementMap();
1034 Set<String> keySet = map.keySet();
1035 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1036 String key = (String) iterator.next();
1037 Set<String> incomingSetKey = map.get(key);
1039 // System.out.println("key=" + key + " incomingSetKey=" +
1041 if (incomingSetKey.size() > 0) {
1042 for (Iterator iterator2 = keySet.iterator(); iterator2.hasNext();) {
1043 String cur = (String) iterator2.next();
1044 if (!cur.equals(key)) {
1045 Set<String> incomingSetCur = map.get(cur);
1046 if (incomingSetCur.equals(incomingSetKey)) {
1047 if (!(incomingSetCur.size() == 1 && incomingSetCur.contains(lattice.getTopItem()))) {
1048 // NEED TO MERGE HERE!!!!
1049 System.out.println("@@@Try merge=" + cur + " " + key);
1051 Set<String> mergeSet = new HashSet<String>();
1055 String newMergeLoc = "MLoc" + (SSJavaLattice.seed++);
1057 System.out.println("---ASSIGN NEW MERGE LOC=" + newMergeLoc + " to " + mergeSet);
1058 lattice.mergeIntoNewLocation(mergeSet, newMergeLoc);
1060 for (Iterator miterator = mergeSet.iterator(); miterator.hasNext();) {
1061 String oldLocSymbol = (String) miterator.next();
1063 Set<Pair<Descriptor, Descriptor>> inferLocSet =
1064 locInfo.getRelatedInferLocSet(oldLocSymbol);
1065 System.out.println("---update related locations=" + inferLocSet
1066 + " oldLocSymbol=" + oldLocSymbol);
1068 for (Iterator miterator2 = inferLocSet.iterator(); miterator2.hasNext();) {
1069 Pair<Descriptor, Descriptor> pair =
1070 (Pair<Descriptor, Descriptor>) miterator2.next();
1071 Descriptor enclosingDesc = pair.getFirst();
1072 Descriptor desc = pair.getSecond();
1074 System.out.println("---inferLoc pair=" + pair);
1076 CompositeLocation inferLoc =
1077 getLocationInfo(enclosingDesc).getInferLocation(desc);
1078 System.out.println("oldLoc=" + inferLoc);
1079 // if (curMethodInfo.md.equals(enclosingDesc)) {
1080 // inferLoc = curMethodInfo.getInferLocation(desc);
1083 // getLocationInfo(enclosingDesc).getInferLocation(desc);
1086 Location locElement = inferLoc.get(inferLoc.getSize() - 1);
1088 locElement.setLocIdentifier(newMergeLoc);
1089 locInfo.addMapLocSymbolToRelatedInferLoc(newMergeLoc, enclosingDesc, desc);
1091 // if (curMethodInfo.md.equals(enclosingDesc)) {
1092 // inferLoc = curMethodInfo.getInferLocation(desc);
1095 // getLocationInfo(enclosingDesc).getInferLocation(desc);
1098 inferLoc = getLocationInfo(enclosingDesc).getInferLocation(desc);
1099 System.out.println("---New Infer Loc=" + inferLoc);
1103 locInfo.removeRelatedInferLocSet(oldLocSymbol, newMergeLoc);
1107 for (Iterator iterator3 = mergeSet.iterator(); iterator3.hasNext();) {
1108 String oldLoc = (String) iterator3.next();
1109 lattice.remove(oldLoc);
1122 private void checkLattices() {
1124 LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
1126 // current descriptors to visit in fixed-point interprocedural analysis,
1128 // dependency in the call graph
1129 methodDescriptorsToVisitStack.clear();
1131 // descriptorListToAnalyze.removeFirst();
1133 Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
1134 methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
1136 while (!descriptorListToAnalyze.isEmpty()) {
1137 MethodDescriptor md = descriptorListToAnalyze.removeFirst();
1138 checkLatticesOfVirtualMethods(md);
1143 private void debug_writeLatticeDotFile() {
1144 // generate lattice dot file
1148 while (!toAnalyzeIsEmpty()) {
1149 ClassDescriptor cd = toAnalyzeNext();
1151 setupToAnalazeMethod(cd);
1153 SSJavaLattice<String> classLattice = cd2lattice.get(cd);
1154 if (classLattice != null) {
1155 ssjava.writeLatticeDotFile(cd, null, classLattice);
1156 debug_printDescriptorToLocNameMapping(cd);
1159 while (!toAnalyzeMethodIsEmpty()) {
1160 MethodDescriptor md = toAnalyzeMethodNext();
1161 SSJavaLattice<String> methodLattice = md2lattice.get(md);
1162 if (methodLattice != null) {
1163 ssjava.writeLatticeDotFile(cd, md, methodLattice);
1164 debug_printDescriptorToLocNameMapping(md);
1171 private void debug_printDescriptorToLocNameMapping(Descriptor desc) {
1173 LocationInfo info = getLocationInfo(desc);
1174 System.out.println("## " + desc + " ##");
1175 System.out.println(info.getMapDescToInferLocation());
1176 LocationInfo locInfo = getLocationInfo(desc);
1177 System.out.println("mapping=" + locInfo.getMapLocSymbolToDescSet());
1178 System.out.println("###################");
1182 private void inferLattices() {
1184 // do fixed-point analysis
1187 LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
1189 // Collections.sort(descriptorListToAnalyze, new
1190 // Comparator<MethodDescriptor>() {
1191 // public int compare(MethodDescriptor o1, MethodDescriptor o2) {
1192 // return o1.getSymbol().compareToIgnoreCase(o2.getSymbol());
1196 // current descriptors to visit in fixed-point interprocedural analysis,
1198 // dependency in the call graph
1199 methodDescriptorsToVisitStack.clear();
1201 // descriptorListToAnalyze.removeFirst();
1203 Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
1204 methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
1206 while (!descriptorListToAnalyze.isEmpty()) {
1207 MethodDescriptor md = descriptorListToAnalyze.removeFirst();
1208 methodDescriptorsToVisitStack.add(md);
1211 // analyze scheduled methods until there are no more to visit
1212 while (!methodDescriptorsToVisitStack.isEmpty()) {
1213 // start to analyze leaf node
1214 MethodDescriptor md = methodDescriptorsToVisitStack.pop();
1216 SSJavaLattice<String> methodLattice =
1217 new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM);
1219 MethodLocationInfo methodInfo = new MethodLocationInfo(md);
1220 curMethodInfo = methodInfo;
1222 System.out.println();
1223 System.out.println("SSJAVA: Inferencing the lattice from " + md);
1226 analyzeMethodLattice(md, methodLattice, methodInfo);
1227 } catch (CyclicFlowException e) {
1228 throw new Error("Fail to generate the method lattice for " + md);
1231 SSJavaLattice<String> prevMethodLattice = getMethodLattice(md);
1232 MethodLocationInfo prevMethodInfo = getMethodLocationInfo(md);
1234 if ((!methodLattice.equals(prevMethodLattice)) || (!methodInfo.equals(prevMethodInfo))) {
1236 setMethodLattice(md, methodLattice);
1237 setMethodLocInfo(md, methodInfo);
1239 // results for callee changed, so enqueue dependents caller for
1241 Iterator<MethodDescriptor> depsItr = ssjava.getDependents(md).iterator();
1242 while (depsItr.hasNext()) {
1243 MethodDescriptor methodNext = depsItr.next();
1244 if (!methodDescriptorsToVisitStack.contains(methodNext)
1245 && methodDescriptorToVistSet.contains(methodNext)) {
1246 methodDescriptorsToVisitStack.add(methodNext);
1256 private void calculateExtraLocations() {
1257 LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
1258 for (Iterator iterator = descriptorListToAnalyze.iterator(); iterator.hasNext();) {
1259 MethodDescriptor md = (MethodDescriptor) iterator.next();
1260 calculateExtraLocations(md);
1264 private void setMethodLocInfo(MethodDescriptor md, MethodLocationInfo methodInfo) {
1265 mapMethodDescToMethodLocationInfo.put(md, methodInfo);
1268 private void checkLatticesOfVirtualMethods(MethodDescriptor md) {
1270 if (!md.isStatic()) {
1271 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
1272 setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md));
1274 for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
1275 MethodDescriptor mdCallee = (MethodDescriptor) iterator.next();
1276 if (!md.equals(mdCallee)) {
1277 checkConsistency(md, mdCallee);
1285 private void checkConsistency(MethodDescriptor md1, MethodDescriptor md2) {
1287 // check that two lattice have the same relations between parameters(+PC
1288 // LOC, GLOBAL_LOC RETURN LOC)
1290 List<CompositeLocation> list1 = new ArrayList<CompositeLocation>();
1291 List<CompositeLocation> list2 = new ArrayList<CompositeLocation>();
1293 MethodLocationInfo locInfo1 = getMethodLocationInfo(md1);
1294 MethodLocationInfo locInfo2 = getMethodLocationInfo(md2);
1296 Map<Integer, CompositeLocation> paramMap1 = locInfo1.getMapParamIdxToInferLoc();
1297 Map<Integer, CompositeLocation> paramMap2 = locInfo2.getMapParamIdxToInferLoc();
1299 int numParam = locInfo1.getMapParamIdxToInferLoc().keySet().size();
1301 // add location types of paramters
1302 for (int idx = 0; idx < numParam; idx++) {
1303 list1.add(paramMap1.get(Integer.valueOf(idx)));
1304 list2.add(paramMap2.get(Integer.valueOf(idx)));
1307 // add program counter location
1308 list1.add(locInfo1.getPCLoc());
1309 list2.add(locInfo2.getPCLoc());
1311 if (!md1.getReturnType().isVoid()) {
1312 // add return value location
1313 CompositeLocation rtrLoc1 = getMethodLocationInfo(md1).getReturnLoc();
1314 CompositeLocation rtrLoc2 = getMethodLocationInfo(md2).getReturnLoc();
1319 // add global location type
1320 if (md1.isStatic()) {
1321 CompositeLocation globalLoc1 =
1322 new CompositeLocation(new Location(md1, locInfo1.getGlobalLocName()));
1323 CompositeLocation globalLoc2 =
1324 new CompositeLocation(new Location(md2, locInfo2.getGlobalLocName()));
1325 list1.add(globalLoc1);
1326 list2.add(globalLoc2);
1329 for (int i = 0; i < list1.size(); i++) {
1330 CompositeLocation locA1 = list1.get(i);
1331 CompositeLocation locA2 = list2.get(i);
1332 for (int k = 0; k < list1.size(); k++) {
1334 CompositeLocation locB1 = list1.get(k);
1335 CompositeLocation locB2 = list2.get(k);
1336 boolean r1 = isGreaterThan(getLattice(md1), locA1, locB1);
1338 boolean r2 = isGreaterThan(getLattice(md1), locA2, locB2);
1341 throw new Error("The method " + md1 + " is not consistent with the method " + md2
1342 + ".:: They have a different ordering relation between locations (" + locA1 + ","
1343 + locB1 + ") and (" + locA2 + "," + locB2 + ").");
1351 private String getSymbol(int idx, FlowNode node) {
1352 Descriptor desc = node.getDescTuple().get(idx);
1353 return desc.getSymbol();
1356 private Descriptor getDescriptor(int idx, FlowNode node) {
1357 Descriptor desc = node.getDescTuple().get(idx);
1361 private void analyzeMethodLattice(MethodDescriptor md, SSJavaLattice<String> methodLattice,
1362 MethodLocationInfo methodInfo) throws CyclicFlowException {
1364 // first take a look at method invocation nodes to newly added relations
1366 analyzeLatticeMethodInvocationNode(md, methodLattice, methodInfo);
1368 if (!md.isStatic()) {
1369 // set the this location
1370 String thisLocSymbol = md.getThis().getSymbol();
1371 methodInfo.setThisLocName(thisLocSymbol);
1374 // set the global location
1375 methodInfo.setGlobalLocName(LocationInference.GLOBALLOC);
1376 methodInfo.mapDescriptorToLocation(GLOBALDESC, new CompositeLocation(
1377 new Location(md, GLOBALLOC)));
1379 // visit each node of method flow graph
1380 FlowGraph fg = getFlowGraph(md);
1381 Set<FlowNode> nodeSet = fg.getNodeSet();
1383 // for the method lattice, we need to look at the first element of
1384 // NTuple<Descriptor>
1385 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1386 FlowNode srcNode = (FlowNode) iterator.next();
1388 Set<FlowEdge> outEdgeSet = srcNode.getOutEdgeSet();
1389 for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) {
1390 FlowEdge outEdge = (FlowEdge) iterator2.next();
1391 FlowNode dstNode = outEdge.getDst();
1393 NTuple<Descriptor> srcNodeTuple = srcNode.getDescTuple();
1394 NTuple<Descriptor> dstNodeTuple = dstNode.getDescTuple();
1396 if (outEdge.getInitTuple().equals(srcNodeTuple)
1397 && outEdge.getEndTuple().equals(dstNodeTuple)) {
1399 if ((srcNodeTuple.size() > 1 && dstNodeTuple.size() > 1)
1400 && srcNodeTuple.get(0).equals(dstNodeTuple.get(0))) {
1402 // value flows between fields
1403 Descriptor desc = srcNodeTuple.get(0);
1404 ClassDescriptor classDesc;
1406 if (desc.equals(GLOBALDESC)) {
1407 classDesc = md.getClassDesc();
1409 VarDescriptor varDesc = (VarDescriptor) srcNodeTuple.get(0);
1410 classDesc = varDesc.getType().getClassDesc();
1412 extractRelationFromFieldFlows(classDesc, srcNode, dstNode, 1);
1415 // value flow between local var - local var or local var - field
1416 addRelationToLattice(md, methodLattice, methodInfo, srcNode, dstNode);
1422 // create mapping from param idx to inferred composite location
1425 if (!md.isStatic()) {
1426 // add 'this' reference location
1428 methodInfo.addMapParamIdxToInferLoc(0, methodInfo.getInferLocation(md.getThis()));
1433 for (int idx = 0; idx < md.numParameters(); idx++) {
1434 Descriptor paramDesc = md.getParameter(idx);
1435 CompositeLocation inferParamLoc = methodInfo.getInferLocation(paramDesc);
1436 methodInfo.addMapParamIdxToInferLoc(idx + offset, inferParamLoc);
1441 private void calculateExtraLocations(MethodDescriptor md) {
1442 // calcualte pcloc, returnloc,...
1444 SSJavaLattice<String> methodLattice = getMethodLattice(md);
1445 MethodLocationInfo methodInfo = getMethodLocationInfo(md);
1446 FlowGraph fg = getFlowGraph(md);
1447 Set<FlowNode> nodeSet = fg.getNodeSet();
1449 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1450 FlowNode flowNode = (FlowNode) iterator.next();
1451 if (flowNode.isDeclaratonNode()) {
1452 CompositeLocation inferLoc = methodInfo.getInferLocation(flowNode.getDescTuple().get(0));
1453 String locIdentifier = inferLoc.get(0).getLocIdentifier();
1454 if (!methodLattice.containsKey(locIdentifier)) {
1455 methodLattice.put(locIdentifier);
1461 Map<Integer, CompositeLocation> mapParamToLoc = methodInfo.getMapParamIdxToInferLoc();
1462 Set<Integer> paramIdxSet = mapParamToLoc.keySet();
1465 if (!ssjava.getMethodContainingSSJavaLoop().equals(md)) {
1466 // calculate the initial program counter location
1467 // PC location is higher than location types of all parameters
1468 String pcLocSymbol = "PCLOC";
1470 Set<CompositeLocation> paramInFlowSet = new HashSet<CompositeLocation>();
1472 for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) {
1473 Integer paramIdx = (Integer) iterator.next();
1475 FlowNode paramFlowNode = fg.getParamFlowNode(paramIdx);
1477 if (fg.getIncomingFlowNodeSet(paramFlowNode).size() > 0) {
1478 // parameter has in-value flows
1479 CompositeLocation inferLoc = mapParamToLoc.get(paramIdx);
1480 paramInFlowSet.add(inferLoc);
1484 if (paramInFlowSet.size() > 0) {
1485 CompositeLocation lowestLoc = getLowest(methodLattice, paramInFlowSet);
1486 assert (lowestLoc != null);
1487 methodInfo.setPCLoc(lowestLoc);
1492 // calculate a return location
1493 // the return location type is lower than all parameters and location
1496 if (!md.getReturnType().isVoid()) {
1497 // first, generate the set of return value location types that starts
1501 Set<CompositeLocation> inferFieldReturnLocSet = new HashSet<CompositeLocation>();
1503 Set<FlowNode> paramFlowNode = getParamNodeFlowingToReturnValue(md);
1504 Set<CompositeLocation> inferParamLocSet = new HashSet<CompositeLocation>();
1505 if (paramFlowNode != null) {
1506 for (Iterator iterator = paramFlowNode.iterator(); iterator.hasNext();) {
1507 FlowNode fn = (FlowNode) iterator.next();
1508 CompositeLocation inferLoc =
1509 generateInferredCompositeLocation(methodInfo, getFlowGraph(md).getLocationTuple(fn));
1510 inferParamLocSet.add(inferLoc);
1514 Set<FlowNode> returnNodeSet = fg.getReturnNodeSet();
1516 skip: for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
1517 FlowNode returnNode = (FlowNode) iterator.next();
1518 CompositeLocation inferReturnLoc =
1519 generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode));
1520 if (inferReturnLoc.get(0).getLocIdentifier().equals("this")) {
1521 // if the location type of the return value matches "this" reference
1522 // then, check whether this return value is equal to/lower than all
1524 // parameters that possibly flow into the return values
1525 for (Iterator iterator2 = inferParamLocSet.iterator(); iterator2.hasNext();) {
1526 CompositeLocation paramInferLoc = (CompositeLocation) iterator2.next();
1528 if ((!paramInferLoc.equals(inferReturnLoc))
1529 && !isGreaterThan(methodLattice, paramInferLoc, inferReturnLoc)) {
1533 inferFieldReturnLocSet.add(inferReturnLoc);
1538 if (inferFieldReturnLocSet.size() > 0) {
1540 CompositeLocation returnLoc = getLowest(methodLattice, inferFieldReturnLocSet);
1541 if (returnLoc == null) {
1542 // in this case, assign <'this',bottom> to the RETURNLOC
1543 returnLoc = new CompositeLocation(new Location(md, md.getThis().getSymbol()));
1544 returnLoc.addLocation(new Location(md.getClassDesc(), getLattice(md.getClassDesc())
1547 methodInfo.setReturnLoc(returnLoc);
1550 String returnLocSymbol = "RETURNLOC";
1551 CompositeLocation returnLocInferLoc =
1552 new CompositeLocation(new Location(md, returnLocSymbol));
1553 methodInfo.setReturnLoc(returnLocInferLoc);
1555 for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) {
1556 Integer paramIdx = (Integer) iterator.next();
1557 CompositeLocation inferLoc = mapParamToLoc.get(paramIdx);
1558 String paramLocLocalSymbol = inferLoc.get(0).getLocIdentifier();
1559 if (!methodLattice.isGreaterThan(paramLocLocalSymbol, returnLocSymbol)) {
1560 addRelationHigherToLower(methodLattice, methodInfo, paramLocLocalSymbol,
1565 for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
1566 FlowNode returnNode = (FlowNode) iterator.next();
1567 CompositeLocation inferLoc =
1568 generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode));
1569 if (!isGreaterThan(methodLattice, inferLoc, returnLocInferLoc)) {
1570 addRelation(methodLattice, methodInfo, inferLoc, returnLocInferLoc);
1577 } catch (CyclicFlowException e) {
1578 e.printStackTrace();
1583 private Set<String> getHigherLocSymbolThan(SSJavaLattice<String> lattice, String loc) {
1584 Set<String> higherLocSet = new HashSet<String>();
1586 Set<String> locSet = lattice.getTable().keySet();
1587 for (Iterator iterator = locSet.iterator(); iterator.hasNext();) {
1588 String element = (String) iterator.next();
1589 if (lattice.isGreaterThan(element, loc) && (!element.equals(lattice.getTopItem()))) {
1590 higherLocSet.add(element);
1593 return higherLocSet;
1596 private CompositeLocation getLowest(SSJavaLattice<String> methodLattice,
1597 Set<CompositeLocation> set) {
1599 CompositeLocation lowest = set.iterator().next();
1601 if (set.size() == 1) {
1605 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
1606 CompositeLocation loc = (CompositeLocation) iterator.next();
1608 if ((!loc.equals(lowest)) && (!isComparable(methodLattice, lowest, loc))) {
1609 // if there is a case where composite locations are incomparable, just
1614 if ((!loc.equals(lowest)) && isGreaterThan(methodLattice, lowest, loc)) {
1621 private boolean isComparable(SSJavaLattice<String> methodLattice, CompositeLocation comp1,
1622 CompositeLocation comp2) {
1624 int size = comp1.getSize() >= comp2.getSize() ? comp2.getSize() : comp1.getSize();
1626 for (int idx = 0; idx < size; idx++) {
1627 Location loc1 = comp1.get(idx);
1628 Location loc2 = comp2.get(idx);
1630 Descriptor desc1 = loc1.getDescriptor();
1631 Descriptor desc2 = loc2.getDescriptor();
1633 if (!desc1.equals(desc2)) {
1634 throw new Error("Fail to compare " + comp1 + " and " + comp2);
1637 String symbol1 = loc1.getLocIdentifier();
1638 String symbol2 = loc2.getLocIdentifier();
1640 SSJavaLattice<String> lattice;
1642 lattice = methodLattice;
1644 lattice = getLattice(desc1);
1647 if (symbol1.equals(symbol2)) {
1649 } else if (!lattice.isComparable(symbol1, symbol2)) {
1658 private boolean isGreaterThan(SSJavaLattice<String> methodLattice, CompositeLocation comp1,
1659 CompositeLocation comp2) {
1661 int size = comp1.getSize() >= comp2.getSize() ? comp2.getSize() : comp1.getSize();
1663 for (int idx = 0; idx < size; idx++) {
1664 Location loc1 = comp1.get(idx);
1665 Location loc2 = comp2.get(idx);
1667 Descriptor desc1 = loc1.getDescriptor();
1668 Descriptor desc2 = loc2.getDescriptor();
1670 if (!desc1.equals(desc2)) {
1671 throw new Error("Fail to compare " + comp1 + " and " + comp2);
1674 String symbol1 = loc1.getLocIdentifier();
1675 String symbol2 = loc2.getLocIdentifier();
1677 SSJavaLattice<String> lattice;
1679 lattice = methodLattice;
1681 lattice = getLattice(desc1);
1684 if (symbol1.equals(symbol2)) {
1686 } else if (lattice.isGreaterThan(symbol1, symbol2)) {
1697 private void recursiveAddRelationToLattice(int idx, MethodDescriptor md,
1698 CompositeLocation srcInferLoc, CompositeLocation dstInferLoc) throws CyclicFlowException {
1700 String srcLocSymbol = srcInferLoc.get(idx).getLocIdentifier();
1701 String dstLocSymbol = dstInferLoc.get(idx).getLocIdentifier();
1703 if (srcLocSymbol.equals(dstLocSymbol)) {
1704 recursiveAddRelationToLattice(idx + 1, md, srcInferLoc, dstInferLoc);
1707 Descriptor parentDesc = srcInferLoc.get(idx).getDescriptor();
1708 LocationInfo locInfo = getLocationInfo(parentDesc);
1710 addRelationHigherToLower(getLattice(parentDesc), getLocationInfo(parentDesc), srcLocSymbol,
1716 private void propagateFlowsFromCallee(MethodInvokeNode min, MethodDescriptor mdCaller,
1717 MethodDescriptor mdCallee) {
1719 // the transformation for a call site propagates all relations between
1720 // parameters from the callee
1721 // if the method is virtual, it also grab all relations from any possible
1724 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
1725 if (mdCallee.isStatic()) {
1726 setPossibleCallees.add(mdCallee);
1728 Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getMethods(mdCallee);
1729 // removes method descriptors that are not invoked by the caller
1730 calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller));
1731 setPossibleCallees.addAll(calleeSet);
1734 for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
1735 MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
1736 propagateFlowsToCaller(min, mdCaller, possibleMdCallee);
1741 private void propagateFlowsToCaller(MethodInvokeNode min, MethodDescriptor mdCaller,
1742 MethodDescriptor mdCallee) {
1744 // if the parameter A reaches to the parameter B
1745 // then, add an edge the argument A -> the argument B to the caller's flow
1748 FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
1749 FlowGraph callerFlowGraph = getFlowGraph(mdCaller);
1750 int numParam = calleeFlowGraph.getNumParameters();
1752 for (int i = 0; i < numParam; i++) {
1753 for (int k = 0; k < numParam; k++) {
1757 FlowNode paramNode1 = calleeFlowGraph.getParamFlowNode(i);
1758 FlowNode paramNode2 = calleeFlowGraph.getParamFlowNode(k);
1760 NodeTupleSet tupleSetArg1 = getNodeTupleSetByArgIdx(min, i);
1761 NodeTupleSet tupleSetArg2 = getNodeTupleSetByArgIdx(min, k);
1763 for (Iterator<NTuple<Descriptor>> iter1 = tupleSetArg1.iterator(); iter1.hasNext();) {
1764 NTuple<Descriptor> arg1Tuple = iter1.next();
1766 for (Iterator<NTuple<Descriptor>> iter2 = tupleSetArg2.iterator(); iter2.hasNext();) {
1767 NTuple<Descriptor> arg2Tuple = iter2.next();
1769 // check if the callee propagates an ordering constraints through
1772 Set<FlowNode> localReachSet =
1773 calleeFlowGraph.getLocalReachFlowNodeSetFrom(paramNode1);
1775 if (localReachSet.contains(paramNode2)) {
1776 // need to propagate an ordering relation s.t. arg1 is higher
1779 if (!min.getMethod().isStatic()) {
1780 // check if this is the case that values flow to/from the
1781 // current object reference 'this'
1783 NTuple<Descriptor> baseTuple = mapMethodInvokeNodeToBaseTuple.get(min);
1784 Descriptor baseRef = baseTuple.get(baseTuple.size() - 1);
1786 // calculate the prefix of the argument
1787 if (arg2Tuple.size() == 1 && arg2Tuple.get(0).equals(baseRef)) {
1789 if (!paramNode1.getCurrentDescTuple().startsWith(mdCallee.getThis())) {
1791 NTuple<Descriptor> param1Prefix =
1792 calculatePrefixForParam(callerFlowGraph, calleeFlowGraph, min, arg1Tuple,
1795 if (param1Prefix != null && param1Prefix.startsWith(mdCallee.getThis())) {
1796 // in this case, we need to create a new edge
1797 // 'this.FIELD'->'this'
1798 // but we couldn't... instead we assign the
1800 // parameter a new composite location started with
1804 CompositeLocation compLocForParam1 =
1805 generateCompositeLocation(mdCallee, param1Prefix);
1807 // System.out.println("set comp loc=" + compLocForParam1
1809 // " to " + paramNode1);
1810 paramNode1.setCompositeLocation(compLocForParam1);
1815 } else if (arg1Tuple.size() == 1 && arg1Tuple.get(0).equals(baseRef)) {
1817 if (!paramNode2.getCurrentDescTuple().startsWith(mdCallee.getThis())) {
1819 NTuple<Descriptor> param2Prefix =
1820 calculatePrefixForParam(callerFlowGraph, calleeFlowGraph, min, arg1Tuple,
1823 if (param2Prefix != null && param2Prefix.startsWith(mdCallee.getThis())) {
1824 // in this case, we need to create a new edge 'this' ->
1826 // but we couldn't... instead we assign the
1828 // parameter a new composite location started with
1832 CompositeLocation compLocForParam2 =
1833 generateCompositeLocation(mdCallee, param2Prefix);
1835 // System.out.println("set comp loc=" + compLocForParam2
1837 // " to " + paramNode2);
1838 paramNode1.setCompositeLocation(compLocForParam2);
1846 // otherwise, flows between method/field locations...
1847 callerFlowGraph.addValueFlowEdge(arg1Tuple, arg2Tuple);
1848 // System.out.println("arg1=" + arg1Tuple + " arg2=" +
1862 private CompositeLocation generateCompositeLocation(MethodDescriptor md,
1863 NTuple<Descriptor> param1Prefix) {
1865 CompositeLocation newCompLoc = convertToCompositeLocation(md, param1Prefix);
1867 LocationDescriptor newLocDescriptor = generateNewLocationDescriptor();
1869 Descriptor enclosingDescriptor = param1Prefix.get(param1Prefix.size() - 1);
1870 Location newLoc = new Location(enclosingDescriptor, newLocDescriptor.getSymbol());
1871 newLoc.setLocDescriptor(newLocDescriptor);
1872 newCompLoc.addLocation(newLoc);
1874 System.out.println("newCompLoc=" + newCompLoc);
1878 private NTuple<Descriptor> calculatePrefixForParam(FlowGraph callerFlowGraph,
1879 FlowGraph calleeFlowGraph, MethodInvokeNode min, NTuple<Descriptor> arg1Tuple,
1880 FlowNode paramNode1) {
1882 NTuple<Descriptor> baseTuple = mapMethodInvokeNodeToBaseTuple.get(min);
1883 Descriptor baseRef = baseTuple.get(baseTuple.size() - 1);
1884 System.out.println("baseRef=" + baseRef);
1886 FlowNode flowNodeArg1 = callerFlowGraph.getFlowNode(arg1Tuple);
1887 List<NTuple<Descriptor>> callerPrefixList = calculatePrefixList(callerFlowGraph, flowNodeArg1);
1888 System.out.println("callerPrefixList=" + callerPrefixList);
1890 List<NTuple<Descriptor>> calleePrefixList =
1891 translatePrefixListToCallee(baseRef, min.getMethod(), callerPrefixList);
1893 System.out.println("calleePrefixList=" + calleePrefixList);
1895 Set<FlowNode> reachNodeSetFromParam1 = calleeFlowGraph.getReachFlowNodeSetFrom(paramNode1);
1896 System.out.println("reachNodeSetFromParam1=" + reachNodeSetFromParam1);
1898 for (int i = 0; i < calleePrefixList.size(); i++) {
1899 NTuple<Descriptor> curPrefix = calleePrefixList.get(i);
1900 Set<NTuple<Descriptor>> reachableCommonPrefixSet = new HashSet<NTuple<Descriptor>>();
1902 for (Iterator iterator2 = reachNodeSetFromParam1.iterator(); iterator2.hasNext();) {
1903 FlowNode reachNode = (FlowNode) iterator2.next();
1904 if (reachNode.getCurrentDescTuple().startsWith(curPrefix)) {
1905 reachableCommonPrefixSet.add(reachNode.getCurrentDescTuple());
1909 if (!reachableCommonPrefixSet.isEmpty()) {
1910 System.out.println("###REACHABLECOMONPREFIX=" + reachableCommonPrefixSet
1911 + " with curPreFix=" + curPrefix);
1920 private List<NTuple<Descriptor>> translatePrefixListToCallee(Descriptor baseRef,
1921 MethodDescriptor mdCallee, List<NTuple<Descriptor>> callerPrefixList) {
1923 List<NTuple<Descriptor>> calleePrefixList = new ArrayList<NTuple<Descriptor>>();
1925 for (int i = 0; i < callerPrefixList.size(); i++) {
1926 NTuple<Descriptor> prefix = callerPrefixList.get(i);
1927 if (prefix.startsWith(baseRef)) {
1928 NTuple<Descriptor> calleePrefix = new NTuple<Descriptor>();
1929 calleePrefix.add(mdCallee.getThis());
1930 for (int k = 1; k < prefix.size(); k++) {
1931 calleePrefix.add(prefix.get(k));
1933 calleePrefixList.add(calleePrefix);
1937 return calleePrefixList;
1941 private List<NTuple<Descriptor>> calculatePrefixList(FlowGraph flowGraph, FlowNode flowNode) {
1943 Set<FlowNode> inNodeSet = flowGraph.getIncomingFlowNodeSet(flowNode);
1944 inNodeSet.add(flowNode);
1946 List<NTuple<Descriptor>> prefixList = new ArrayList<NTuple<Descriptor>>();
1948 for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
1949 FlowNode inNode = (FlowNode) iterator.next();
1951 NTuple<Descriptor> inNodeTuple = inNode.getCurrentDescTuple();
1953 // CompositeLocation inNodeInferredLoc =
1954 // generateInferredCompositeLocation(methodInfo, inNodeTuple);
1955 // NTuple<Location> inNodeInferredLocTuple = inNodeInferredLoc.getTuple();
1957 for (int i = 1; i < inNodeTuple.size(); i++) {
1958 NTuple<Descriptor> prefix = inNodeTuple.subList(0, i);
1959 if (!prefixList.contains(prefix)) {
1960 prefixList.add(prefix);
1965 Collections.sort(prefixList, new Comparator<NTuple<Descriptor>>() {
1966 public int compare(NTuple<Descriptor> arg0, NTuple<Descriptor> arg1) {
1967 int s0 = arg0.size();
1968 int s1 = arg1.size();
1971 } else if (s0 == s1) {
1983 public CompositeLocation convertToCompositeLocation(MethodDescriptor md, NTuple<Descriptor> tuple) {
1985 CompositeLocation compLoc = new CompositeLocation();
1987 Descriptor enclosingDescriptor = md;
1989 for (int i = 0; i < tuple.size(); i++) {
1990 Descriptor curDescriptor = tuple.get(i);
1991 Location locElement = new Location(enclosingDescriptor, curDescriptor.getSymbol());
1992 locElement.setLocDescriptor(curDescriptor);
1993 compLoc.addLocation(locElement);
1995 if (curDescriptor instanceof VarDescriptor) {
1996 enclosingDescriptor = md.getClassDesc();
1997 } else if (curDescriptor instanceof NameDescriptor) {
1998 // it is "GLOBAL LOC" case!
1999 enclosingDescriptor = GLOBALDESC;
2001 enclosingDescriptor = ((FieldDescriptor) curDescriptor).getClassDescriptor();
2006 System.out.println("convertToCompositeLocation from=" + tuple + " to " + compLoc);
2011 private LocationDescriptor generateNewLocationDescriptor() {
2012 return new LocationDescriptor("Loc" + (locSeed++));
2015 private int getPrefixIndex(NTuple<Descriptor> tuple1, NTuple<Descriptor> tuple2) {
2017 // return the index where the prefix shared by tuple1 and tuple2 is ended
2018 // if there is no prefix shared by both of them, return -1
2020 int minSize = tuple1.size();
2021 if (minSize > tuple2.size()) {
2022 minSize = tuple2.size();
2026 for (int i = 0; i < minSize; i++) {
2027 if (!tuple1.get(i).equals(tuple2.get(i))) {
2037 private void analyzeLatticeMethodInvocationNode(MethodDescriptor mdCaller,
2038 SSJavaLattice<String> methodLattice, MethodLocationInfo methodInfo)
2039 throws CyclicFlowException {
2041 // the transformation for a call site propagates all relations between
2042 // parameters from the callee
2043 // if the method is virtual, it also grab all relations from any possible
2046 Set<MethodInvokeNode> setMethodInvokeNode =
2047 mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller);
2049 if (setMethodInvokeNode != null) {
2051 for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) {
2052 MethodInvokeNode min = (MethodInvokeNode) iterator.next();
2053 MethodDescriptor mdCallee = min.getMethod();
2054 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
2055 if (mdCallee.isStatic()) {
2056 setPossibleCallees.add(mdCallee);
2058 Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getMethods(mdCallee);
2059 // removes method descriptors that are not invoked by the caller
2060 calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller));
2061 setPossibleCallees.addAll(calleeSet);
2064 for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
2065 MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
2066 propagateRelationToCaller(min, mdCaller, possibleMdCallee, methodLattice, methodInfo);
2074 private void propagateRelationToCaller(MethodInvokeNode min, MethodDescriptor mdCaller,
2075 MethodDescriptor possibleMdCallee, SSJavaLattice<String> methodLattice,
2076 MethodLocationInfo methodInfo) throws CyclicFlowException {
2078 SSJavaLattice<String> calleeLattice = getMethodLattice(possibleMdCallee);
2079 MethodLocationInfo calleeLocInfo = getMethodLocationInfo(possibleMdCallee);
2080 FlowGraph calleeFlowGraph = getFlowGraph(possibleMdCallee);
2082 int numParam = calleeLocInfo.getNumParam();
2083 for (int i = 0; i < numParam; i++) {
2084 CompositeLocation param1 = calleeLocInfo.getParamCompositeLocation(i);
2085 for (int k = 0; k < numParam; k++) {
2087 CompositeLocation param2 = calleeLocInfo.getParamCompositeLocation(k);
2089 if (isGreaterThan(getLattice(possibleMdCallee), param1, param2)) {
2090 NodeTupleSet argDescTupleSet1 = getNodeTupleSetByArgIdx(min, i);
2091 NodeTupleSet argDescTupleSet2 = getNodeTupleSetByArgIdx(min, k);
2093 // the callee has the relation in which param1 is higher than param2
2094 // therefore, the caller has to have the relation in which arg1 is
2097 for (Iterator<NTuple<Descriptor>> iterator = argDescTupleSet1.iterator(); iterator
2099 NTuple<Descriptor> argDescTuple1 = iterator.next();
2101 for (Iterator<NTuple<Descriptor>> iterator2 = argDescTupleSet2.iterator(); iterator2
2103 NTuple<Descriptor> argDescTuple2 = iterator2.next();
2105 // retreive inferred location by the local var descriptor
2107 NTuple<Location> tuple1 = getFlowGraph(mdCaller).getLocationTuple(argDescTuple1);
2108 NTuple<Location> tuple2 = getFlowGraph(mdCaller).getLocationTuple(argDescTuple2);
2110 // CompositeLocation higherInferLoc =
2111 // methodInfo.getInferLocation(argTuple1.get(0));
2112 // CompositeLocation lowerInferLoc =
2113 // methodInfo.getInferLocation(argTuple2.get(0));
2115 CompositeLocation inferLoc1 = generateInferredCompositeLocation(methodInfo, tuple1);
2116 CompositeLocation inferLoc2 = generateInferredCompositeLocation(methodInfo, tuple2);
2118 // addRelation(methodLattice, methodInfo, inferLoc1, inferLoc2);
2120 addFlowGraphEdge(mdCaller, argDescTuple1, argDescTuple2);
2133 private CompositeLocation generateInferredCompositeLocation(MethodLocationInfo methodInfo,
2134 NTuple<Location> tuple) {
2136 // first, retrieve inferred location by the local var descriptor
2137 CompositeLocation inferLoc = new CompositeLocation();
2139 CompositeLocation localVarInferLoc =
2140 methodInfo.getInferLocation(tuple.get(0).getLocDescriptor());
2142 localVarInferLoc.get(0).setLocDescriptor(tuple.get(0).getLocDescriptor());
2144 for (int i = 0; i < localVarInferLoc.getSize(); i++) {
2145 inferLoc.addLocation(localVarInferLoc.get(i));
2148 for (int i = 1; i < tuple.size(); i++) {
2149 Location cur = tuple.get(i);
2150 Descriptor enclosingDesc = cur.getDescriptor();
2151 Descriptor curDesc = cur.getLocDescriptor();
2153 Location inferLocElement;
2154 if (curDesc == null) {
2155 // in this case, we have a newly generated location.
2156 inferLocElement = new Location(enclosingDesc, cur.getLocIdentifier());
2158 String fieldLocSymbol =
2159 getLocationInfo(enclosingDesc).getInferLocation(curDesc).get(0).getLocIdentifier();
2160 inferLocElement = new Location(enclosingDesc, fieldLocSymbol);
2161 inferLocElement.setLocDescriptor(curDesc);
2164 inferLoc.addLocation(inferLocElement);
2168 assert (inferLoc.get(0).getLocDescriptor().getSymbol() == inferLoc.get(0).getLocIdentifier());
2172 private void addRelation(SSJavaLattice<String> methodLattice, MethodLocationInfo methodInfo,
2173 CompositeLocation srcInferLoc, CompositeLocation dstInferLoc) throws CyclicFlowException {
2175 System.out.println("addRelation --- srcInferLoc=" + srcInferLoc + " dstInferLoc="
2177 String srcLocalLocSymbol = srcInferLoc.get(0).getLocIdentifier();
2178 String dstLocalLocSymbol = dstInferLoc.get(0).getLocIdentifier();
2180 if (srcInferLoc.getSize() == 1 && dstInferLoc.getSize() == 1) {
2181 // add a new relation to the local lattice
2182 addRelationHigherToLower(methodLattice, methodInfo, srcLocalLocSymbol, dstLocalLocSymbol);
2183 } else if (srcInferLoc.getSize() > 1 && dstInferLoc.getSize() > 1) {
2184 // both src and dst have assigned to a composite location
2186 if (!srcLocalLocSymbol.equals(dstLocalLocSymbol)) {
2187 addRelationHigherToLower(methodLattice, methodInfo, srcLocalLocSymbol, dstLocalLocSymbol);
2189 recursivelyAddRelation(1, srcInferLoc, dstInferLoc);
2192 // either src or dst has assigned to a composite location
2193 if (!srcLocalLocSymbol.equals(dstLocalLocSymbol)) {
2194 addRelationHigherToLower(methodLattice, methodInfo, srcLocalLocSymbol, dstLocalLocSymbol);
2198 System.out.println();
2202 public LocationInfo getLocationInfo(Descriptor d) {
2203 if (d instanceof MethodDescriptor) {
2204 return getMethodLocationInfo((MethodDescriptor) d);
2206 return getFieldLocationInfo((ClassDescriptor) d);
2210 private MethodLocationInfo getMethodLocationInfo(MethodDescriptor md) {
2212 if (!mapMethodDescToMethodLocationInfo.containsKey(md)) {
2213 mapMethodDescToMethodLocationInfo.put(md, new MethodLocationInfo(md));
2216 return mapMethodDescToMethodLocationInfo.get(md);
2220 private LocationInfo getFieldLocationInfo(ClassDescriptor cd) {
2222 if (!mapClassToLocationInfo.containsKey(cd)) {
2223 mapClassToLocationInfo.put(cd, new LocationInfo(cd));
2226 return mapClassToLocationInfo.get(cd);
2230 private void addRelationToLattice(MethodDescriptor md, SSJavaLattice<String> methodLattice,
2231 MethodLocationInfo methodInfo, FlowNode srcNode, FlowNode dstNode) throws CyclicFlowException {
2233 System.out.println();
2234 System.out.println("### addRelationToLattice src=" + srcNode + " dst=" + dstNode);
2236 // add a new binary relation of dstNode < srcNode
2237 FlowGraph flowGraph = getFlowGraph(md);
2239 System.out.println("***** src composite case::");
2240 calculateCompositeLocation(flowGraph, methodLattice, methodInfo, srcNode, null);
2242 CompositeLocation srcInferLoc =
2243 generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(srcNode));
2244 CompositeLocation dstInferLoc =
2245 generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(dstNode));
2246 addRelation(methodLattice, methodInfo, srcInferLoc, dstInferLoc);
2247 } catch (CyclicFlowException e) {
2248 // there is a cyclic value flow... try to calculate a composite location
2249 // for the destination node
2250 System.out.println("***** dst composite case::");
2251 calculateCompositeLocation(flowGraph, methodLattice, methodInfo, dstNode, srcNode);
2252 CompositeLocation srcInferLoc =
2253 generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(srcNode));
2254 CompositeLocation dstInferLoc =
2255 generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(dstNode));
2257 addRelation(methodLattice, methodInfo, srcInferLoc, dstInferLoc);
2258 } catch (CyclicFlowException e1) {
2259 throw new Error("Failed to merge cyclic value flows into a shared location.");
2265 private void recursivelyAddRelation(int idx, CompositeLocation srcInferLoc,
2266 CompositeLocation dstInferLoc) throws CyclicFlowException {
2268 String srcLocSymbol = srcInferLoc.get(idx).getLocIdentifier();
2269 String dstLocSymbol = dstInferLoc.get(idx).getLocIdentifier();
2271 Descriptor parentDesc = srcInferLoc.get(idx).getDescriptor();
2273 if (srcLocSymbol.equals(dstLocSymbol)) {
2274 // check if it is the case of shared location
2275 if (srcInferLoc.getSize() == (idx + 1) && dstInferLoc.getSize() == (idx + 1)) {
2276 Location inferLocElement = srcInferLoc.get(idx);
2277 System.out.println("SET SHARED LOCATION=" + inferLocElement);
2278 getLattice(inferLocElement.getDescriptor())
2279 .addSharedLoc(inferLocElement.getLocIdentifier());
2280 } else if (srcInferLoc.getSize() > (idx + 1) && dstInferLoc.getSize() > (idx + 1)) {
2281 recursivelyAddRelation(idx + 1, srcInferLoc, dstInferLoc);
2284 addRelationHigherToLower(getLattice(parentDesc), getLocationInfo(parentDesc), srcLocSymbol,
2289 private void recursivelyAddCompositeRelation(MethodDescriptor md, FlowGraph flowGraph,
2290 MethodLocationInfo methodInfo, FlowNode srcNode, FlowNode dstNode, Descriptor srcDesc,
2291 Descriptor dstDesc) throws CyclicFlowException {
2293 CompositeLocation inferSrcLoc;
2294 CompositeLocation inferDstLoc = methodInfo.getInferLocation(dstDesc);
2296 if (srcNode.getDescTuple().size() > 1) {
2298 inferSrcLoc = new CompositeLocation();
2300 NTuple<Location> locTuple = flowGraph.getLocationTuple(srcNode);
2301 for (int i = 0; i < locTuple.size(); i++) {
2302 inferSrcLoc.addLocation(locTuple.get(i));
2306 inferSrcLoc = methodInfo.getInferLocation(srcDesc);
2309 if (dstNode.getDescTuple().size() > 1) {
2311 inferDstLoc = new CompositeLocation();
2313 NTuple<Location> locTuple = flowGraph.getLocationTuple(dstNode);
2314 for (int i = 0; i < locTuple.size(); i++) {
2315 inferDstLoc.addLocation(locTuple.get(i));
2319 inferDstLoc = methodInfo.getInferLocation(dstDesc);
2322 recursiveAddRelationToLattice(1, md, inferSrcLoc, inferDstLoc);
2325 private void addPrefixMapping(Map<NTuple<Location>, Set<NTuple<Location>>> map,
2326 NTuple<Location> prefix, NTuple<Location> element) {
2328 if (!map.containsKey(prefix)) {
2329 map.put(prefix, new HashSet<NTuple<Location>>());
2331 map.get(prefix).add(element);
2334 private boolean calculateCompositeLocation(FlowGraph flowGraph,
2335 SSJavaLattice<String> methodLattice, MethodLocationInfo methodInfo, FlowNode flowNode,
2336 FlowNode srcNode) throws CyclicFlowException {
2338 Descriptor localVarDesc = flowNode.getDescTuple().get(0);
2339 NTuple<Location> flowNodelocTuple = flowGraph.getLocationTuple(flowNode);
2341 if (localVarDesc.equals(methodInfo.getMethodDesc())) {
2345 Set<FlowNode> inNodeSet = flowGraph.getIncomingFlowNodeSet(flowNode);
2346 Set<FlowNode> reachableNodeSet = flowGraph.getReachFlowNodeSetFrom(flowNode);
2348 Map<NTuple<Location>, Set<NTuple<Location>>> mapPrefixToIncomingLocTupleSet =
2349 new HashMap<NTuple<Location>, Set<NTuple<Location>>>();
2351 List<NTuple<Location>> prefixList = new ArrayList<NTuple<Location>>();
2353 for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
2354 FlowNode inNode = (FlowNode) iterator.next();
2355 NTuple<Location> inNodeTuple = flowGraph.getLocationTuple(inNode);
2357 CompositeLocation inNodeInferredLoc =
2358 generateInferredCompositeLocation(methodInfo, inNodeTuple);
2360 NTuple<Location> inNodeInferredLocTuple = inNodeInferredLoc.getTuple();
2362 for (int i = 1; i < inNodeInferredLocTuple.size(); i++) {
2363 NTuple<Location> prefix = inNodeInferredLocTuple.subList(0, i);
2364 if (!prefixList.contains(prefix)) {
2365 prefixList.add(prefix);
2367 addPrefixMapping(mapPrefixToIncomingLocTupleSet, prefix, inNodeInferredLocTuple);
2371 Collections.sort(prefixList, new Comparator<NTuple<Location>>() {
2372 public int compare(NTuple<Location> arg0, NTuple<Location> arg1) {
2373 int s0 = arg0.size();
2374 int s1 = arg1.size();
2377 } else if (s0 == s1) {
2385 // System.out.println("prefixList=" + prefixList);
2386 // System.out.println("reachableNodeSet=" + reachableNodeSet);
2388 // find out reachable nodes that have the longest common prefix
2389 for (int i = 0; i < prefixList.size(); i++) {
2390 NTuple<Location> curPrefix = prefixList.get(i);
2391 Set<NTuple<Location>> reachableCommonPrefixSet = new HashSet<NTuple<Location>>();
2393 for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
2394 FlowNode reachableNode = (FlowNode) iterator2.next();
2395 NTuple<Location> reachLocTuple = flowGraph.getLocationTuple(reachableNode);
2396 CompositeLocation reachLocInferLoc =
2397 generateInferredCompositeLocation(methodInfo, reachLocTuple);
2398 if (reachLocInferLoc.getTuple().startsWith(curPrefix)) {
2399 reachableCommonPrefixSet.add(reachLocTuple);
2403 if (!reachableCommonPrefixSet.isEmpty()) {
2404 // found reachable nodes that start with the prefix curPrefix
2405 // need to assign a composite location
2407 // first, check if there are more than one the set of locations that has
2408 // the same length of the longest reachable prefix, no way to assign
2409 // a composite location to the input local var
2410 prefixSanityCheck(prefixList, i, flowGraph, reachableNodeSet);
2412 Set<NTuple<Location>> incomingCommonPrefixSet =
2413 mapPrefixToIncomingLocTupleSet.get(curPrefix);
2415 int idx = curPrefix.size();
2416 NTuple<Location> element = incomingCommonPrefixSet.iterator().next();
2417 Descriptor desc = element.get(idx).getDescriptor();
2419 SSJavaLattice<String> lattice = getLattice(desc);
2420 LocationInfo locInfo = getLocationInfo(desc);
2422 CompositeLocation inferLocation =
2423 generateInferredCompositeLocation(methodInfo, flowNodelocTuple);
2425 // methodInfo.getInferLocation(localVarDesc);
2426 CompositeLocation newInferLocation = new CompositeLocation();
2428 if (inferLocation.getTuple().startsWith(curPrefix)) {
2429 // the same infer location is already existed. no need to do
2431 System.out.println("NO ATTEMPT TO MAKE A COMPOSITE LOCATION curPrefix=" + curPrefix);
2433 // TODO: refactoring!
2434 if (srcNode != null) {
2435 CompositeLocation newLoc = new CompositeLocation();
2436 String newLocSymbol = "Loc" + (SSJavaLattice.seed++);
2437 for (int locIdx = 0; locIdx < curPrefix.size(); locIdx++) {
2438 newLoc.addLocation(curPrefix.get(locIdx));
2440 Location newLocationElement = new Location(desc, newLocSymbol);
2441 newLoc.addLocation(newLocationElement);
2443 Descriptor srcLocalVar = srcNode.getDescTuple().get(0);
2444 methodInfo.mapDescriptorToLocation(srcLocalVar, newLoc.clone());
2445 addMapLocSymbolToInferredLocation(methodInfo.getMethodDesc(), srcLocalVar, newLoc);
2446 methodInfo.removeMaplocalVarToLocSet(srcLocalVar);
2448 // add the field/var descriptor to the set of the location symbol
2449 int lastIdx = srcNode.getDescTuple().size() - 1;
2450 Descriptor lastFlowNodeDesc = srcNode.getDescTuple().get(lastIdx);
2451 NTuple<Location> srcNodelocTuple = flowGraph.getLocationTuple(srcNode);
2452 Descriptor enclosinglastLastFlowNodeDesc = srcNodelocTuple.get(lastIdx).getDescriptor();
2454 CompositeLocation newlyInferredLocForFlowNode =
2455 generateInferredCompositeLocation(methodInfo, srcNodelocTuple);
2456 Location lastInferLocElement =
2457 newlyInferredLocForFlowNode.get(newlyInferredLocForFlowNode.getSize() - 1);
2458 Descriptor enclosingLastInferLocElement = lastInferLocElement.getDescriptor();
2460 // getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToDescSet(
2461 // lastInferLocElement.getLocIdentifier(), lastFlowNodeDesc);
2462 getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToRelatedInferLoc(
2463 lastInferLocElement.getLocIdentifier(), enclosinglastLastFlowNodeDesc,
2466 System.out.println("@@@@@@@ ASSIGN " + newLoc + " to SRC=" + srcNode);
2471 // assign a new composite location
2473 // String oldMethodLocationSymbol =
2474 // inferLocation.get(0).getLocIdentifier();
2475 String newLocSymbol = "Loc" + (SSJavaLattice.seed++);
2476 for (int locIdx = 0; locIdx < curPrefix.size(); locIdx++) {
2477 newInferLocation.addLocation(curPrefix.get(locIdx));
2479 Location newLocationElement = new Location(desc, newLocSymbol);
2480 newInferLocation.addLocation(newLocationElement);
2482 // maps local variable to location types of the common prefix
2483 methodInfo.mapDescriptorToLocation(localVarDesc, newInferLocation.clone());
2485 // methodInfo.mapDescriptorToLocation(localVarDesc, newInferLocation);
2486 addMapLocSymbolToInferredLocation(methodInfo.getMethodDesc(), localVarDesc,
2488 methodInfo.removeMaplocalVarToLocSet(localVarDesc);
2490 // add the field/var descriptor to the set of the location symbol
2491 int lastIdx = flowNode.getDescTuple().size() - 1;
2492 Descriptor lastFlowNodeDesc = flowNode.getDescTuple().get(lastIdx);
2493 Descriptor enclosinglastLastFlowNodeDesc = flowNodelocTuple.get(lastIdx).getDescriptor();
2495 CompositeLocation newlyInferredLocForFlowNode =
2496 generateInferredCompositeLocation(methodInfo, flowNodelocTuple);
2497 Location lastInferLocElement =
2498 newlyInferredLocForFlowNode.get(newlyInferredLocForFlowNode.getSize() - 1);
2499 Descriptor enclosingLastInferLocElement = lastInferLocElement.getDescriptor();
2501 // getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToDescSet(
2502 // lastInferLocElement.getLocIdentifier(), lastFlowNodeDesc);
2503 getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToRelatedInferLoc(
2504 lastInferLocElement.getLocIdentifier(), enclosinglastLastFlowNodeDesc,
2507 // clean up the previous location
2508 // Location prevInferLocElement =
2509 // inferLocation.get(inferLocation.getSize() - 1);
2510 // Descriptor prevEnclosingDesc = prevInferLocElement.getDescriptor();
2512 // SSJavaLattice<String> targetLattice;
2513 // LocationInfo targetInfo;
2514 // if (prevEnclosingDesc.equals(methodInfo.getMethodDesc())) {
2515 // targetLattice = methodLattice;
2516 // targetInfo = methodInfo;
2518 // targetLattice = getLattice(prevInferLocElement.getDescriptor());
2519 // targetInfo = getLocationInfo(prevInferLocElement.getDescriptor());
2522 // Set<Pair<Descriptor, Descriptor>> associstedDescSet =
2523 // targetInfo.getRelatedInferLocSet(prevInferLocElement.getLocIdentifier());
2525 // if (associstedDescSet.size() == 1) {
2526 // targetLattice.remove(prevInferLocElement.getLocIdentifier());
2528 // associstedDescSet.remove(lastFlowNodeDesc);
2533 System.out.println("curPrefix=" + curPrefix);
2534 System.out.println("ASSIGN NEW COMPOSITE LOCATION =" + newInferLocation + " to "
2537 String newlyInsertedLocName =
2538 newInferLocation.get(newInferLocation.getSize() - 1).getLocIdentifier();
2540 System.out.println("-- add in-flow");
2541 for (Iterator iterator = incomingCommonPrefixSet.iterator(); iterator.hasNext();) {
2542 NTuple<Location> tuple = (NTuple<Location>) iterator.next();
2543 Location loc = tuple.get(idx);
2544 String higher = loc.getLocIdentifier();
2545 addRelationHigherToLower(lattice, locInfo, higher, newlyInsertedLocName);
2548 System.out.println("-- add out flow");
2549 for (Iterator iterator = reachableCommonPrefixSet.iterator(); iterator.hasNext();) {
2550 NTuple<Location> tuple = (NTuple<Location>) iterator.next();
2551 if (tuple.size() > idx) {
2552 Location loc = tuple.get(idx);
2553 String lower = loc.getLocIdentifier();
2555 // locInfo.getFieldInferLocation(loc.getLocDescriptor()).getLocIdentifier();
2556 addRelationHigherToLower(lattice, locInfo, newlyInsertedLocName, lower);
2569 private void addMapLocSymbolToInferredLocation(MethodDescriptor md, Descriptor localVar,
2570 CompositeLocation inferLoc) {
2572 Location locElement = inferLoc.get((inferLoc.getSize() - 1));
2573 Descriptor enclosingDesc = locElement.getDescriptor();
2574 LocationInfo locInfo = getLocationInfo(enclosingDesc);
2575 locInfo.addMapLocSymbolToRelatedInferLoc(locElement.getLocIdentifier(), md, localVar);
2578 private boolean isCompositeLocation(CompositeLocation cl) {
2579 return cl.getSize() > 1;
2582 private boolean containsNonPrimitiveElement(Set<Descriptor> descSet) {
2583 for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
2584 Descriptor desc = (Descriptor) iterator.next();
2586 if (desc.equals(LocationInference.GLOBALDESC)) {
2588 } else if (desc instanceof VarDescriptor) {
2589 if (!((VarDescriptor) desc).getType().isPrimitive()) {
2592 } else if (desc instanceof FieldDescriptor) {
2593 if (!((FieldDescriptor) desc).getType().isPrimitive()) {
2602 private void addRelationHigherToLower(SSJavaLattice<String> lattice, LocationInfo locInfo,
2603 String higher, String lower) throws CyclicFlowException {
2605 System.out.println("---addRelationHigherToLower " + higher + " -> " + lower
2606 + " to the lattice of " + locInfo.getDescIdentifier());
2607 // if (higher.equals(lower) && lattice.isSharedLoc(higher)) {
2610 Set<String> cycleElementSet = lattice.getPossibleCycleElements(higher, lower);
2612 boolean hasNonPrimitiveElement = false;
2613 for (Iterator iterator = cycleElementSet.iterator(); iterator.hasNext();) {
2614 String cycleElementLocSymbol = (String) iterator.next();
2616 Set<Descriptor> descSet = locInfo.getDescSet(cycleElementLocSymbol);
2617 if (containsNonPrimitiveElement(descSet)) {
2618 hasNonPrimitiveElement = true;
2623 if (hasNonPrimitiveElement) {
2624 System.out.println("#Check cycle= " + lower + " < " + higher + " cycleElementSet="
2626 // if there is non-primitive element in the cycle, no way to merge cyclic
2627 // elements into the shared location
2628 throw new CyclicFlowException();
2631 if (cycleElementSet.size() > 0) {
2633 String newSharedLoc = "SharedLoc" + (SSJavaLattice.seed++);
2635 System.out.println("---ASSIGN NEW SHARED LOC=" + newSharedLoc + " to " + cycleElementSet);
2636 lattice.mergeIntoNewLocation(cycleElementSet, newSharedLoc);
2637 lattice.addSharedLoc(newSharedLoc);
2639 for (Iterator iterator = cycleElementSet.iterator(); iterator.hasNext();) {
2640 String oldLocSymbol = (String) iterator.next();
2642 Set<Pair<Descriptor, Descriptor>> inferLocSet = locInfo.getRelatedInferLocSet(oldLocSymbol);
2643 System.out.println("---update related locations=" + inferLocSet);
2644 for (Iterator iterator2 = inferLocSet.iterator(); iterator2.hasNext();) {
2645 Pair<Descriptor, Descriptor> pair = (Pair<Descriptor, Descriptor>) iterator2.next();
2646 Descriptor enclosingDesc = pair.getFirst();
2647 Descriptor desc = pair.getSecond();
2649 CompositeLocation inferLoc;
2650 if (curMethodInfo.md.equals(enclosingDesc)) {
2651 inferLoc = curMethodInfo.getInferLocation(desc);
2653 inferLoc = getLocationInfo(enclosingDesc).getInferLocation(desc);
2656 Location locElement = inferLoc.get(inferLoc.getSize() - 1);
2658 locElement.setLocIdentifier(newSharedLoc);
2659 locInfo.addMapLocSymbolToRelatedInferLoc(newSharedLoc, enclosingDesc, desc);
2661 if (curMethodInfo.md.equals(enclosingDesc)) {
2662 inferLoc = curMethodInfo.getInferLocation(desc);
2664 inferLoc = getLocationInfo(enclosingDesc).getInferLocation(desc);
2666 System.out.println("---New Infer Loc=" + inferLoc);
2669 locInfo.removeRelatedInferLocSet(oldLocSymbol, newSharedLoc);
2673 lattice.addSharedLoc(newSharedLoc);
2675 } else if (!lattice.isGreaterThan(higher, lower)) {
2676 lattice.addRelationHigherToLower(higher, lower);
2680 private void replaceOldLocWithNewLoc(SSJavaLattice<String> methodLattice, String oldLocSymbol,
2681 String newLocSymbol) {
2683 if (methodLattice.containsKey(oldLocSymbol)) {
2684 methodLattice.substituteLocation(oldLocSymbol, newLocSymbol);
2689 private void prefixSanityCheck(List<NTuple<Location>> prefixList, int curIdx,
2690 FlowGraph flowGraph, Set<FlowNode> reachableNodeSet) {
2692 NTuple<Location> curPrefix = prefixList.get(curIdx);
2694 for (int i = curIdx + 1; i < prefixList.size(); i++) {
2695 NTuple<Location> prefixTuple = prefixList.get(i);
2697 if (curPrefix.startsWith(prefixTuple)) {
2701 for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
2702 FlowNode reachableNode = (FlowNode) iterator2.next();
2703 NTuple<Location> reachLocTuple = flowGraph.getLocationTuple(reachableNode);
2704 if (reachLocTuple.startsWith(prefixTuple)) {
2706 throw new Error("Failed to generate a composite location");
2712 public boolean isPrimitiveLocalVariable(FlowNode node) {
2713 VarDescriptor varDesc = (VarDescriptor) node.getDescTuple().get(0);
2714 return varDesc.getType().isPrimitive();
2717 private SSJavaLattice<String> getLattice(Descriptor d) {
2718 if (d instanceof MethodDescriptor) {
2719 return getMethodLattice((MethodDescriptor) d);
2721 return getFieldLattice((ClassDescriptor) d);
2725 private SSJavaLattice<String> getMethodLattice(MethodDescriptor md) {
2726 if (!md2lattice.containsKey(md)) {
2727 md2lattice.put(md, new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM));
2729 return md2lattice.get(md);
2732 private void setMethodLattice(MethodDescriptor md, SSJavaLattice<String> lattice) {
2733 md2lattice.put(md, lattice);
2736 private void extractFlowsBetweenFields(ClassDescriptor cd, FlowNode srcNode, FlowNode dstNode,
2739 NTuple<Descriptor> srcCurTuple = srcNode.getCurrentDescTuple();
2740 NTuple<Descriptor> dstCurTuple = dstNode.getCurrentDescTuple();
2742 if (srcCurTuple.get(idx).equals(dstCurTuple.get(idx)) && srcCurTuple.size() > (idx + 1)
2743 && dstCurTuple.size() > (idx + 1)) {
2744 // value flow between fields: we don't need to add a binary relation
2747 Descriptor desc = srcCurTuple.get(idx);
2748 ClassDescriptor classDesc;
2751 classDesc = ((VarDescriptor) desc).getType().getClassDesc();
2753 classDesc = ((FieldDescriptor) desc).getType().getClassDesc();
2756 extractFlowsBetweenFields(classDesc, srcNode, dstNode, idx + 1);
2760 Descriptor srcFieldDesc = srcCurTuple.get(idx);
2761 Descriptor dstFieldDesc = dstCurTuple.get(idx);
2764 getHierarchyGraph(cd).addEdge(srcFieldDesc, dstFieldDesc);
2770 private void extractRelationFromFieldFlows(ClassDescriptor cd, FlowNode srcNode,
2771 FlowNode dstNode, int idx) throws CyclicFlowException {
2773 if (srcNode.getDescTuple().get(idx).equals(dstNode.getDescTuple().get(idx))
2774 && srcNode.getDescTuple().size() > (idx + 1) && dstNode.getDescTuple().size() > (idx + 1)) {
2775 // value flow between fields: we don't need to add a binary relation
2778 Descriptor desc = srcNode.getDescTuple().get(idx);
2779 ClassDescriptor classDesc;
2782 classDesc = ((VarDescriptor) desc).getType().getClassDesc();
2784 classDesc = ((FieldDescriptor) desc).getType().getClassDesc();
2787 extractRelationFromFieldFlows(classDesc, srcNode, dstNode, idx + 1);
2791 Descriptor srcFieldDesc = srcNode.getDescTuple().get(idx);
2792 Descriptor dstFieldDesc = dstNode.getDescTuple().get(idx);
2794 // add a new binary relation of dstNode < srcNode
2795 SSJavaLattice<String> fieldLattice = getFieldLattice(cd);
2796 LocationInfo fieldInfo = getFieldLocationInfo(cd);
2798 String srcSymbol = fieldInfo.getFieldInferLocation(srcFieldDesc).getLocIdentifier();
2799 String dstSymbol = fieldInfo.getFieldInferLocation(dstFieldDesc).getLocIdentifier();
2801 addRelationHigherToLower(fieldLattice, fieldInfo, srcSymbol, dstSymbol);
2807 public SSJavaLattice<String> getFieldLattice(ClassDescriptor cd) {
2808 if (!cd2lattice.containsKey(cd)) {
2809 cd2lattice.put(cd, new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM));
2811 return cd2lattice.get(cd);
2814 public LinkedList<MethodDescriptor> computeMethodList() {
2816 Set<MethodDescriptor> toSort = new HashSet<MethodDescriptor>();
2820 Set<MethodDescriptor> visited = new HashSet<MethodDescriptor>();
2821 Set<MethodDescriptor> reachableCallee = new HashSet<MethodDescriptor>();
2823 while (!toAnalyzeIsEmpty()) {
2824 ClassDescriptor cd = toAnalyzeNext();
2826 setupToAnalazeMethod(cd);
2827 toanalyzeMethodList.removeAll(visited);
2829 while (!toAnalyzeMethodIsEmpty()) {
2830 MethodDescriptor md = toAnalyzeMethodNext();
2831 if ((!visited.contains(md))
2832 && (ssjava.needTobeAnnotated(md) || reachableCallee.contains(md))) {
2834 // creates a mapping from a method descriptor to virtual methods
2835 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
2836 if (md.isStatic()) {
2837 setPossibleCallees.add(md);
2839 setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md));
2842 Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getCalleeSet(md);
2843 Set<MethodDescriptor> needToAnalyzeCalleeSet = new HashSet<MethodDescriptor>();
2845 for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) {
2846 MethodDescriptor calleemd = (MethodDescriptor) iterator.next();
2847 if ((!ssjava.isTrustMethod(calleemd))
2848 && (!ssjava.isSSJavaUtil(calleemd.getClassDesc()))) {
2849 if (!visited.contains(calleemd)) {
2850 toanalyzeMethodList.add(calleemd);
2852 reachableCallee.add(calleemd);
2853 needToAnalyzeCalleeSet.add(calleemd);
2857 mapMethodToCalleeSet.put(md, needToAnalyzeCalleeSet);
2866 return ssjava.topologicalSort(toSort);
2870 public void constructFlowGraph() {
2872 System.out.println("");
2873 LinkedList<MethodDescriptor> methodDescList = computeMethodList();
2875 System.out.println("@@@methodDescList=" + methodDescList);
2878 while (!methodDescList.isEmpty()) {
2879 MethodDescriptor md = methodDescList.removeLast();
2880 if (state.SSJAVADEBUG) {
2881 System.out.println();
2882 System.out.println("SSJAVA: Constructing a flow graph: " + md);
2884 // creates a mapping from a parameter descriptor to its index
2885 Map<Descriptor, Integer> mapParamDescToIdx = new HashMap<Descriptor, Integer>();
2887 if (!md.isStatic()) {
2889 mapParamDescToIdx.put(md.getThis(), 0);
2892 for (int i = 0; i < md.numParameters(); i++) {
2893 Descriptor paramDesc = (Descriptor) md.getParameter(i);
2894 mapParamDescToIdx.put(paramDesc, new Integer(i + offset));
2897 FlowGraph fg = new FlowGraph(md, mapParamDescToIdx);
2898 mapMethodDescriptorToFlowGraph.put(md, fg);
2900 analyzeMethodBody(md.getClassDesc(), md);
2901 propagateFlowsFromCallees(md);
2902 assignCompositeLocation(md);
2906 _debug_printGraph();
2910 private void assignCompositeLocation(MethodDescriptor md) {
2912 FlowGraph flowGraph = getFlowGraph(md);
2914 Set<FlowNode> nodeSet = flowGraph.getNodeSet();
2916 next: for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
2917 FlowNode flowNode = (FlowNode) iterator.next();
2919 // assign a composite location only to the local variable
2920 if (flowNode.getCurrentDescTuple().size() == 1) {
2922 List<NTuple<Descriptor>> prefixList = calculatePrefixList(flowGraph, flowNode);
2923 Set<FlowNode> reachSet = flowGraph.getReachFlowNodeSetFrom(flowNode);
2925 for (int i = 0; i < prefixList.size(); i++) {
2926 NTuple<Descriptor> curPrefix = prefixList.get(i);
2927 Set<NTuple<Descriptor>> reachableCommonPrefixSet = new HashSet<NTuple<Descriptor>>();
2929 for (Iterator iterator2 = reachSet.iterator(); iterator2.hasNext();) {
2930 FlowNode reachNode = (FlowNode) iterator2.next();
2931 if (reachNode.getCurrentDescTuple().startsWith(curPrefix)) {
2932 reachableCommonPrefixSet.add(reachNode.getCurrentDescTuple());
2936 if (!reachableCommonPrefixSet.isEmpty()) {
2937 System.out.println("NEED TO ASSIGN COMP LOC TO " + flowNode + " with prefix="
2939 CompositeLocation newCompLoc = generateCompositeLocation(md, curPrefix);
2940 flowNode.setCompositeLocation(newCompLoc);
2951 private void propagateFlowsFromCallees(MethodDescriptor mdCaller) {
2953 // the transformation for a call site propagates flows through parameters
2954 // if the method is virtual, it also grab all relations from any possible
2957 Set<MethodInvokeNode> setMethodInvokeNode =
2958 mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller);
2960 if (setMethodInvokeNode != null) {
2962 for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) {
2963 MethodInvokeNode min = (MethodInvokeNode) iterator.next();
2964 MethodDescriptor mdCallee = min.getMethod();
2965 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
2966 if (mdCallee.isStatic()) {
2967 setPossibleCallees.add(mdCallee);
2969 Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getMethods(mdCallee);
2970 // removes method descriptors that are not invoked by the caller
2971 calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller));
2972 setPossibleCallees.addAll(calleeSet);
2975 for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
2976 MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
2977 propagateFlowsToCaller(min, mdCaller, possibleMdCallee);
2985 private void analyzeMethodBody(ClassDescriptor cd, MethodDescriptor md) {
2986 BlockNode bn = state.getMethodBody(md);
2987 NodeTupleSet implicitFlowTupleSet = new NodeTupleSet();
2988 analyzeFlowBlockNode(md, md.getParameterTable(), bn, implicitFlowTupleSet);
2991 private void analyzeFlowBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn,
2992 NodeTupleSet implicitFlowTupleSet) {
2994 bn.getVarTable().setParent(nametable);
2995 for (int i = 0; i < bn.size(); i++) {
2996 BlockStatementNode bsn = bn.get(i);
2997 analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet);
3002 private void analyzeBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
3003 BlockStatementNode bsn, NodeTupleSet implicitFlowTupleSet) {
3005 switch (bsn.kind()) {
3006 case Kind.BlockExpressionNode:
3007 analyzeBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn, implicitFlowTupleSet);
3010 case Kind.DeclarationNode:
3011 analyzeFlowDeclarationNode(md, nametable, (DeclarationNode) bsn, implicitFlowTupleSet);
3014 case Kind.IfStatementNode:
3015 analyzeFlowIfStatementNode(md, nametable, (IfStatementNode) bsn, implicitFlowTupleSet);
3019 analyzeFlowLoopNode(md, nametable, (LoopNode) bsn, implicitFlowTupleSet);
3022 case Kind.ReturnNode:
3023 analyzeFlowReturnNode(md, nametable, (ReturnNode) bsn, implicitFlowTupleSet);
3026 case Kind.SubBlockNode:
3027 analyzeFlowSubBlockNode(md, nametable, (SubBlockNode) bsn, implicitFlowTupleSet);
3030 case Kind.ContinueBreakNode:
3033 case Kind.SwitchStatementNode:
3034 analyzeSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn, implicitFlowTupleSet);
3041 private void analyzeSwitchBlockNode(MethodDescriptor md, SymbolTable nametable,
3042 SwitchBlockNode sbn, NodeTupleSet implicitFlowTupleSet) {
3044 analyzeFlowBlockNode(md, nametable, sbn.getSwitchBlockStatement(), implicitFlowTupleSet);
3048 private void analyzeSwitchStatementNode(MethodDescriptor md, SymbolTable nametable,
3049 SwitchStatementNode ssn, NodeTupleSet implicitFlowTupleSet) {
3051 NodeTupleSet condTupleNode = new NodeTupleSet();
3052 analyzeFlowExpressionNode(md, nametable, ssn.getCondition(), condTupleNode, null,
3053 implicitFlowTupleSet, false);
3055 NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
3057 newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
3058 newImplicitTupleSet.addTupleSet(condTupleNode);
3060 if (newImplicitTupleSet.size() > 1) {
3061 // need to create an intermediate node for the GLB of conditional locations & implicit flows
3062 NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
3063 for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) {
3064 NTuple<Descriptor> tuple = idxIter.next();
3065 addFlowGraphEdge(md, tuple, interTuple);
3067 newImplicitTupleSet.clear();
3068 newImplicitTupleSet.addTuple(interTuple);
3071 BlockNode sbn = ssn.getSwitchBody();
3072 for (int i = 0; i < sbn.size(); i++) {
3073 analyzeSwitchBlockNode(md, nametable, (SwitchBlockNode) sbn.get(i), newImplicitTupleSet);
3078 private void analyzeFlowSubBlockNode(MethodDescriptor md, SymbolTable nametable,
3079 SubBlockNode sbn, NodeTupleSet implicitFlowTupleSet) {
3080 analyzeFlowBlockNode(md, nametable, sbn.getBlockNode(), implicitFlowTupleSet);
3083 private void analyzeFlowReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode rn,
3084 NodeTupleSet implicitFlowTupleSet) {
3086 ExpressionNode returnExp = rn.getReturnExpression();
3088 if (returnExp != null) {
3089 NodeTupleSet nodeSet = new NodeTupleSet();
3090 // if a return expression returns a literal value, nodeSet is empty
3091 analyzeFlowExpressionNode(md, nametable, returnExp, nodeSet, false);
3092 FlowGraph fg = getFlowGraph(md);
3094 // if (implicitFlowTupleSet.size() == 1
3095 // && fg.getFlowNode(implicitFlowTupleSet.iterator().next()).isIntermediate()) {
3097 // // since there is already an intermediate node for the GLB of implicit flows
3098 // // we don't need to create another intermediate node.
3099 // // just re-use the intermediate node for implicit flows.
3101 // FlowNode meetNode = fg.getFlowNode(implicitFlowTupleSet.iterator().next());
3103 // for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
3104 // NTuple<Descriptor> returnNodeTuple = (NTuple<Descriptor>) iterator.next();
3105 // fg.addValueFlowEdge(returnNodeTuple, meetNode.getDescTuple());
3110 NodeTupleSet currentFlowTupleSet = new NodeTupleSet();
3112 // add tuples from return node
3113 currentFlowTupleSet.addTupleSet(nodeSet);
3115 // add tuples corresponding to the current implicit flows
3116 currentFlowTupleSet.addTupleSet(implicitFlowTupleSet);
3118 if (currentFlowTupleSet.size() > 1) {
3119 FlowNode meetNode = fg.createIntermediateNode();
3120 for (Iterator iterator = currentFlowTupleSet.iterator(); iterator.hasNext();) {
3121 NTuple<Descriptor> currentFlowTuple = (NTuple<Descriptor>) iterator.next();
3122 fg.addValueFlowEdge(currentFlowTuple, meetNode.getDescTuple());
3124 fg.addReturnFlowNode(meetNode.getDescTuple());
3125 } else if (currentFlowTupleSet.size() == 1) {
3126 NTuple<Descriptor> tuple = currentFlowTupleSet.iterator().next();
3127 fg.addReturnFlowNode(tuple);
3134 private void analyzeFlowLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln,
3135 NodeTupleSet implicitFlowTupleSet) {
3137 if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) {
3139 NodeTupleSet condTupleNode = new NodeTupleSet();
3140 analyzeFlowExpressionNode(md, nametable, ln.getCondition(), condTupleNode, null,
3141 implicitFlowTupleSet, false);
3143 NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
3145 newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
3146 newImplicitTupleSet.addTupleSet(condTupleNode);
3148 if (newImplicitTupleSet.size() > 1) {
3149 // need to create an intermediate node for the GLB of conditional locations & implicit flows
3150 NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
3151 for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter
3153 NTuple<Descriptor> tuple = idxIter.next();
3154 addFlowGraphEdge(md, tuple, interTuple);
3156 newImplicitTupleSet.clear();
3157 newImplicitTupleSet.addTuple(interTuple);
3162 // System.out.println("condTupleNode="+condTupleNode);
3163 // NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
3165 // for (Iterator<NTuple<Descriptor>> idxIter = condTupleNode.iterator(); idxIter.hasNext();) {
3166 // NTuple<Descriptor> tuple = idxIter.next();
3167 // addFlowGraphEdge(md, tuple, interTuple);
3170 // for (Iterator<NTuple<Descriptor>> idxIter = implicitFlowTupleSet.iterator(); idxIter
3172 // NTuple<Descriptor> tuple = idxIter.next();
3173 // addFlowGraphEdge(md, tuple, interTuple);
3176 // NodeTupleSet newImplicitSet = new NodeTupleSet();
3177 // newImplicitSet.addTuple(interTuple);
3178 analyzeFlowBlockNode(md, nametable, ln.getBody(), newImplicitTupleSet);
3181 // condTupleNode.addTupleSet(implicitFlowTupleSet);
3183 // add edges from condNodeTupleSet to all nodes of conditional nodes
3184 // analyzeFlowBlockNode(md, nametable, ln.getBody(), condTupleNode);
3187 // check 'for loop' case
3188 BlockNode bn = ln.getInitializer();
3189 bn.getVarTable().setParent(nametable);
3190 for (int i = 0; i < bn.size(); i++) {
3191 BlockStatementNode bsn = bn.get(i);
3192 analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet);
3195 NodeTupleSet condTupleNode = new NodeTupleSet();
3196 analyzeFlowExpressionNode(md, bn.getVarTable(), ln.getCondition(), condTupleNode, null,
3197 implicitFlowTupleSet, false);
3200 NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
3202 for (Iterator<NTuple<Descriptor>> idxIter = condTupleNode.iterator(); idxIter.hasNext();) {
3203 NTuple<Descriptor> tuple = idxIter.next();
3204 addFlowGraphEdge(md, tuple, interTuple);
3207 for (Iterator<NTuple<Descriptor>> idxIter = implicitFlowTupleSet.iterator(); idxIter
3209 NTuple<Descriptor> tuple = idxIter.next();
3210 addFlowGraphEdge(md, tuple, interTuple);
3213 NodeTupleSet newImplicitSet = new NodeTupleSet();
3214 newImplicitSet.addTuple(interTuple);
3215 analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(), newImplicitSet);
3216 analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(), newImplicitSet);
3219 // condTupleNode.addTupleSet(implicitFlowTupleSet);
3221 // analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(),
3223 // analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(),
3230 private void analyzeFlowIfStatementNode(MethodDescriptor md, SymbolTable nametable,
3231 IfStatementNode isn, NodeTupleSet implicitFlowTupleSet) {
3233 System.out.println("analyzeFlowIfStatementNode=" + isn.printNode(0));
3235 NodeTupleSet condTupleNode = new NodeTupleSet();
3236 analyzeFlowExpressionNode(md, nametable, isn.getCondition(), condTupleNode, null,
3237 implicitFlowTupleSet, false);
3239 NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
3241 newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
3242 newImplicitTupleSet.addTupleSet(condTupleNode);
3244 System.out.println("condTupleNode=" + condTupleNode);
3245 System.out.println("implicitFlowTupleSet=" + implicitFlowTupleSet);
3246 System.out.println("newImplicitTupleSet=" + newImplicitTupleSet);
3248 if (newImplicitTupleSet.size() > 1) {
3250 // need to create an intermediate node for the GLB of conditional locations & implicit flows
3251 NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
3252 for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) {
3253 NTuple<Descriptor> tuple = idxIter.next();
3254 addFlowGraphEdge(md, tuple, interTuple);
3256 newImplicitTupleSet.clear();
3257 newImplicitTupleSet.addTuple(interTuple);
3260 analyzeFlowBlockNode(md, nametable, isn.getTrueBlock(), newImplicitTupleSet);
3262 if (isn.getFalseBlock() != null) {
3263 analyzeFlowBlockNode(md, nametable, isn.getFalseBlock(), newImplicitTupleSet);
3268 private void analyzeFlowDeclarationNode(MethodDescriptor md, SymbolTable nametable,
3269 DeclarationNode dn, NodeTupleSet implicitFlowTupleSet) {
3271 VarDescriptor vd = dn.getVarDescriptor();
3272 mapDescToDefinitionLine.put(vd, dn.getNumLine());
3273 NTuple<Descriptor> tupleLHS = new NTuple<Descriptor>();
3275 FlowNode fn = getFlowGraph(md).createNewFlowNode(tupleLHS);
3276 fn.setDeclarationNode();
3278 if (dn.getExpression() != null) {
3280 NodeTupleSet nodeSetRHS = new NodeTupleSet();
3281 analyzeFlowExpressionNode(md, nametable, dn.getExpression(), nodeSetRHS, null,
3282 implicitFlowTupleSet, false);
3284 // creates edges from RHS to LHS
3285 NTuple<Descriptor> interTuple = null;
3286 if (nodeSetRHS.size() > 1) {
3287 interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
3290 for (Iterator<NTuple<Descriptor>> iter = nodeSetRHS.iterator(); iter.hasNext();) {
3291 NTuple<Descriptor> fromTuple = iter.next();
3292 addFlowGraphEdge(md, fromTuple, interTuple, tupleLHS);
3295 // creates edges from implicitFlowTupleSet to LHS
3296 for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
3297 NTuple<Descriptor> implicitTuple = iter.next();
3298 addFlowGraphEdge(md, implicitTuple, tupleLHS);
3305 private void analyzeBlockExpressionNode(MethodDescriptor md, SymbolTable nametable,
3306 BlockExpressionNode ben, NodeTupleSet implicitFlowTupleSet) {
3307 analyzeFlowExpressionNode(md, nametable, ben.getExpression(), null, null, implicitFlowTupleSet,
3311 private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
3312 ExpressionNode en, NodeTupleSet nodeSet, boolean isLHS) {
3313 return analyzeFlowExpressionNode(md, nametable, en, nodeSet, null, new NodeTupleSet(), isLHS);
3316 private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
3317 ExpressionNode en, NodeTupleSet nodeSet, NTuple<Descriptor> base,
3318 NodeTupleSet implicitFlowTupleSet, boolean isLHS) {
3320 // note that expression node can create more than one flow node
3321 // nodeSet contains of flow nodes
3322 // base is always assigned to null except the case of a name node!
3324 NTuple<Descriptor> flowTuple;
3326 switch (en.kind()) {
3328 case Kind.AssignmentNode:
3329 analyzeFlowAssignmentNode(md, nametable, (AssignmentNode) en, nodeSet, base,
3330 implicitFlowTupleSet);
3333 case Kind.FieldAccessNode:
3335 analyzeFlowFieldAccessNode(md, nametable, (FieldAccessNode) en, nodeSet, base,
3336 implicitFlowTupleSet, isLHS);
3337 if (flowTuple != null) {
3338 nodeSet.addTuple(flowTuple);
3343 NodeTupleSet nameNodeSet = new NodeTupleSet();
3345 analyzeFlowNameNode(md, nametable, (NameNode) en, nameNodeSet, base, implicitFlowTupleSet);
3346 if (flowTuple != null) {
3347 nodeSet.addTuple(flowTuple);
3352 analyzeFlowOpNode(md, nametable, (OpNode) en, nodeSet, implicitFlowTupleSet);
3355 case Kind.CreateObjectNode:
3356 analyzeCreateObjectNode(md, nametable, (CreateObjectNode) en);
3359 case Kind.ArrayAccessNode:
3360 analyzeFlowArrayAccessNode(md, nametable, (ArrayAccessNode) en, nodeSet, isLHS);
3363 case Kind.LiteralNode:
3364 analyzeLiteralNode(md, nametable, (LiteralNode) en);
3367 case Kind.MethodInvokeNode:
3368 analyzeFlowMethodInvokeNode(md, nametable, (MethodInvokeNode) en, nodeSet,
3369 implicitFlowTupleSet);
3372 case Kind.TertiaryNode:
3373 analyzeFlowTertiaryNode(md, nametable, (TertiaryNode) en, nodeSet, implicitFlowTupleSet);
3377 analyzeFlowCastNode(md, nametable, (CastNode) en, nodeSet, base, implicitFlowTupleSet);
3379 // case Kind.InstanceOfNode:
3380 // checkInstanceOfNode(md, nametable, (InstanceOfNode) en, td);
3383 // case Kind.ArrayInitializerNode:
3384 // checkArrayInitializerNode(md, nametable, (ArrayInitializerNode) en,
3388 // case Kind.ClassTypeNode:
3389 // checkClassTypeNode(md, nametable, (ClassTypeNode) en, td);
3392 // case Kind.OffsetNode:
3393 // checkOffsetNode(md, nametable, (OffsetNode)en, td);
3401 private void analyzeFlowCastNode(MethodDescriptor md, SymbolTable nametable, CastNode cn,
3402 NodeTupleSet nodeSet, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
3404 analyzeFlowExpressionNode(md, nametable, cn.getExpression(), nodeSet, base,
3405 implicitFlowTupleSet, false);
3409 private void analyzeFlowTertiaryNode(MethodDescriptor md, SymbolTable nametable, TertiaryNode tn,
3410 NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
3412 NodeTupleSet tertiaryTupleNode = new NodeTupleSet();
3413 analyzeFlowExpressionNode(md, nametable, tn.getCond(), tertiaryTupleNode, null,
3414 implicitFlowTupleSet, false);
3416 // add edges from tertiaryTupleNode to all nodes of conditional nodes
3417 tertiaryTupleNode.addTupleSet(implicitFlowTupleSet);
3418 analyzeFlowExpressionNode(md, nametable, tn.getTrueExpr(), tertiaryTupleNode, null,
3419 implicitFlowTupleSet, false);
3421 analyzeFlowExpressionNode(md, nametable, tn.getFalseExpr(), tertiaryTupleNode, null,
3422 implicitFlowTupleSet, false);
3424 nodeSet.addTupleSet(tertiaryTupleNode);
3428 private void addMapCallerMethodDescToMethodInvokeNodeSet(MethodDescriptor caller,
3429 MethodInvokeNode min) {
3430 Set<MethodInvokeNode> set = mapMethodDescriptorToMethodInvokeNodeSet.get(caller);
3432 set = new HashSet<MethodInvokeNode>();
3433 mapMethodDescriptorToMethodInvokeNodeSet.put(caller, set);
3438 private void addParamNodeFlowingToReturnValue(MethodDescriptor md, FlowNode fn) {
3440 if (!mapMethodDescToParamNodeFlowsToReturnValue.containsKey(md)) {
3441 mapMethodDescToParamNodeFlowsToReturnValue.put(md, new HashSet<FlowNode>());
3443 mapMethodDescToParamNodeFlowsToReturnValue.get(md).add(fn);
3446 private Set<FlowNode> getParamNodeFlowingToReturnValue(MethodDescriptor md) {
3447 return mapMethodDescToParamNodeFlowsToReturnValue.get(md);
3450 private void analyzeFlowMethodInvokeNode(MethodDescriptor md, SymbolTable nametable,
3451 MethodInvokeNode min, NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
3453 if (nodeSet == null) {
3454 nodeSet = new NodeTupleSet();
3457 MethodDescriptor calleeMethodDesc = min.getMethod();
3459 NameDescriptor baseName = min.getBaseName();
3460 boolean isSystemout = false;
3461 if (baseName != null) {
3462 isSystemout = baseName.getSymbol().equals("System.out");
3465 if (!ssjava.isSSJavaUtil(calleeMethodDesc.getClassDesc())
3466 && !ssjava.isTrustMethod(calleeMethodDesc) && !isSystemout) {
3468 addMapCallerMethodDescToMethodInvokeNodeSet(md, min);
3470 FlowGraph calleeFlowGraph = getFlowGraph(calleeMethodDesc);
3471 Set<FlowNode> calleeReturnSet = calleeFlowGraph.getReturnNodeSet();
3473 System.out.println("#calleeReturnSet=" + calleeReturnSet);
3475 if (min.getExpression() != null) {
3477 NodeTupleSet baseNodeSet = new NodeTupleSet();
3478 analyzeFlowExpressionNode(md, nametable, min.getExpression(), baseNodeSet, null,
3479 implicitFlowTupleSet, false);
3481 assert (baseNodeSet.size() == 1);
3482 mapMethodInvokeNodeToBaseTuple.put(min, baseNodeSet.iterator().next());
3484 if (!min.getMethod().isStatic()) {
3485 addArgIdxMap(min, 0, baseNodeSet);
3487 for (Iterator iterator = calleeReturnSet.iterator(); iterator.hasNext();) {
3488 FlowNode returnNode = (FlowNode) iterator.next();
3489 NTuple<Descriptor> returnDescTuple = returnNode.getDescTuple();
3490 if (returnDescTuple.startsWith(calleeMethodDesc.getThis())) {
3491 // the location type of the return value is started with 'this'
3493 for (Iterator<NTuple<Descriptor>> baseIter = baseNodeSet.iterator(); baseIter
3495 NTuple<Descriptor> baseTuple = baseIter.next();
3496 NTuple<Descriptor> inFlowTuple = new NTuple<Descriptor>(baseTuple.getList());
3497 inFlowTuple.addAll(returnDescTuple.subList(1, returnDescTuple.size()));
3498 nodeSet.addTuple(inFlowTuple);
3501 Set<FlowNode> inFlowSet = calleeFlowGraph.getIncomingFlowNodeSet(returnNode);
3502 for (Iterator iterator2 = inFlowSet.iterator(); iterator2.hasNext();) {
3503 FlowNode inFlowNode = (FlowNode) iterator2.next();
3504 if (inFlowNode.getDescTuple().startsWith(calleeMethodDesc.getThis())) {
3505 nodeSet.addTupleSet(baseNodeSet);
3514 // analyze parameter flows
3516 if (min.numArgs() > 0) {
3519 if (min.getMethod().isStatic()) {
3525 for (int i = 0; i < min.numArgs(); i++) {
3526 ExpressionNode en = min.getArg(i);
3527 int idx = i + offset;
3528 NodeTupleSet argTupleSet = new NodeTupleSet();
3529 analyzeFlowExpressionNode(md, nametable, en, argTupleSet, false);
3530 // if argument is liternal node, argTuple is set to NULL.
3531 addArgIdxMap(min, idx, argTupleSet);
3532 FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx);
3533 if (hasInFlowTo(calleeFlowGraph, paramNode, calleeReturnSet)
3534 || calleeMethodDesc.getModifiers().isNative()) {
3535 addParamNodeFlowingToReturnValue(calleeMethodDesc, paramNode);
3536 nodeSet.addTupleSet(argTupleSet);
3542 // propagateFlowsFromCallee(min, md, min.getMethod());
3548 private boolean hasInFlowTo(FlowGraph fg, FlowNode inNode, Set<FlowNode> nodeSet) {
3549 // return true if inNode has in-flows to nodeSet
3550 Set<FlowNode> reachableSet = fg.getReachFlowNodeSetFrom(inNode);
3551 for (Iterator iterator = reachableSet.iterator(); iterator.hasNext();) {
3552 FlowNode fn = (FlowNode) iterator.next();
3553 if (nodeSet.contains(fn)) {
3560 private NodeTupleSet getNodeTupleSetByArgIdx(MethodInvokeNode min, int idx) {
3561 return mapMethodInvokeNodeToArgIdxMap.get(min).get(new Integer(idx));
3564 private void addArgIdxMap(MethodInvokeNode min, int idx, NodeTupleSet tupleSet) {
3565 Map<Integer, NodeTupleSet> mapIdxToTupleSet = mapMethodInvokeNodeToArgIdxMap.get(min);
3566 if (mapIdxToTupleSet == null) {
3567 mapIdxToTupleSet = new HashMap<Integer, NodeTupleSet>();
3568 mapMethodInvokeNodeToArgIdxMap.put(min, mapIdxToTupleSet);
3570 mapIdxToTupleSet.put(new Integer(idx), tupleSet);
3573 private void analyzeFlowMethodParameters(MethodDescriptor callermd, SymbolTable nametable,
3574 MethodInvokeNode min, NodeTupleSet nodeSet) {
3576 if (min.numArgs() > 0) {
3579 if (min.getMethod().isStatic()) {
3583 // NTuple<Descriptor> thisArgTuple = new NTuple<Descriptor>();
3584 // thisArgTuple.add(callermd.getThis());
3585 // NodeTupleSet argTupleSet = new NodeTupleSet();
3586 // argTupleSet.addTuple(thisArgTuple);
3587 // addArgIdxMap(min, 0, argTupleSet);
3588 // nodeSet.addTuple(thisArgTuple);
3591 for (int i = 0; i < min.numArgs(); i++) {
3592 ExpressionNode en = min.getArg(i);
3593 NodeTupleSet argTupleSet = new NodeTupleSet();
3594 analyzeFlowExpressionNode(callermd, nametable, en, argTupleSet, false);
3595 // if argument is liternal node, argTuple is set to NULL.
3596 addArgIdxMap(min, i + offset, argTupleSet);
3597 nodeSet.addTupleSet(argTupleSet);
3604 private void analyzeLiteralNode(MethodDescriptor md, SymbolTable nametable, LiteralNode en) {
3608 private void analyzeFlowArrayAccessNode(MethodDescriptor md, SymbolTable nametable,
3609 ArrayAccessNode aan, NodeTupleSet nodeSet, boolean isLHS) {
3611 NodeTupleSet expNodeTupleSet = new NodeTupleSet();
3612 NTuple<Descriptor> base =
3613 analyzeFlowExpressionNode(md, nametable, aan.getExpression(), expNodeTupleSet, isLHS);
3615 NodeTupleSet idxNodeTupleSet = new NodeTupleSet();
3616 analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, isLHS);
3619 // need to create an edge from idx to array
3620 for (Iterator<NTuple<Descriptor>> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) {
3621 NTuple<Descriptor> idxTuple = idxIter.next();
3622 for (Iterator<NTuple<Descriptor>> arrIter = expNodeTupleSet.iterator(); arrIter.hasNext();) {
3623 NTuple<Descriptor> arrTuple = arrIter.next();
3624 getFlowGraph(md).addValueFlowEdge(idxTuple, arrTuple);
3628 nodeSet.addTupleSet(expNodeTupleSet);
3630 nodeSet.addTupleSet(expNodeTupleSet);
3631 nodeSet.addTupleSet(idxNodeTupleSet);
3635 private void analyzeCreateObjectNode(MethodDescriptor md, SymbolTable nametable,
3636 CreateObjectNode en) {
3637 // TODO Auto-generated method stub
3641 private void analyzeFlowOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on,
3642 NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
3644 NodeTupleSet leftOpSet = new NodeTupleSet();
3645 NodeTupleSet rightOpSet = new NodeTupleSet();
3648 analyzeFlowExpressionNode(md, nametable, on.getLeft(), leftOpSet, null, implicitFlowTupleSet,
3651 if (on.getRight() != null) {
3653 analyzeFlowExpressionNode(md, nametable, on.getRight(), rightOpSet, null,
3654 implicitFlowTupleSet, false);
3657 Operation op = on.getOp();
3659 switch (op.getOp()) {
3661 case Operation.UNARYPLUS:
3662 case Operation.UNARYMINUS:
3663 case Operation.LOGIC_NOT:
3665 nodeSet.addTupleSet(leftOpSet);
3668 case Operation.LOGIC_OR:
3669 case Operation.LOGIC_AND:
3670 case Operation.COMP:
3671 case Operation.BIT_OR:
3672 case Operation.BIT_XOR:
3673 case Operation.BIT_AND:
3674 case Operation.ISAVAILABLE:
3675 case Operation.EQUAL:
3676 case Operation.NOTEQUAL:
3683 case Operation.MULT:
3686 case Operation.LEFTSHIFT:
3687 case Operation.RIGHTSHIFT:
3688 case Operation.URIGHTSHIFT:
3690 // there are two operands
3691 nodeSet.addTupleSet(leftOpSet);
3692 nodeSet.addTupleSet(rightOpSet);
3696 throw new Error(op.toString());
3701 private NTuple<Descriptor> analyzeFlowNameNode(MethodDescriptor md, SymbolTable nametable,
3702 NameNode nn, NodeTupleSet nodeSet, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
3704 // System.out.println("analyzeFlowNameNode=" + nn.printNode(0));
3707 base = new NTuple<Descriptor>();
3710 NameDescriptor nd = nn.getName();
3712 if (nd.getBase() != null) {
3714 analyzeFlowExpressionNode(md, nametable, nn.getExpression(), nodeSet, base,
3715 implicitFlowTupleSet, false);
3717 // base node has the top location
3721 String varname = nd.toString();
3722 if (varname.equals("this")) {
3724 base.add(md.getThis());
3728 Descriptor d = (Descriptor) nametable.get(varname);
3730 if (d instanceof VarDescriptor) {
3731 VarDescriptor vd = (VarDescriptor) d;
3733 } else if (d instanceof FieldDescriptor) {
3734 // the type of field descriptor has a location!
3735 FieldDescriptor fd = (FieldDescriptor) d;
3736 if (fd.isStatic()) {
3738 // if it is 'static final', no need to have flow node for the TOP
3742 // if 'static', assign the default GLOBAL LOCATION to the first
3743 // element of the tuple
3744 base.add(GLOBALDESC);
3747 // the location of field access starts from this, followed by field
3749 base.add(md.getThis());
3753 } else if (d == null) {
3754 // access static field
3755 base.add(GLOBALDESC);
3756 base.add(nn.getField());
3759 // FieldDescriptor fd = nn.getField();addFlowGraphEdge
3761 // MethodLattice<String> localLattice = ssjava.getMethodLattice(md);
3762 // String globalLocId = localLattice.getGlobalLoc();
3763 // if (globalLocId == null) {
3765 // Error("Method lattice does not define global variable location at "
3766 // + generateErrorMessage(md.getClassDesc(), nn));
3768 // loc.addLocation(new Location(md, globalLocId));
3770 // Location fieldLoc = (Location) fd.getType().getExtension();
3771 // loc.addLocation(fieldLoc);
3777 getFlowGraph(md).createNewFlowNode(base);
3783 private NTuple<Descriptor> analyzeFlowFieldAccessNode(MethodDescriptor md, SymbolTable nametable,
3784 FieldAccessNode fan, NodeTupleSet nodeSet, NTuple<Descriptor> base,
3785 NodeTupleSet implicitFlowTupleSet, boolean isLHS) {
3787 ExpressionNode left = fan.getExpression();
3788 TypeDescriptor ltd = left.getType();
3789 FieldDescriptor fd = fan.getField();
3791 String varName = null;
3792 if (left.kind() == Kind.NameNode) {
3793 NameDescriptor nd = ((NameNode) left).getName();
3794 varName = nd.toString();
3797 if (ltd.isClassNameRef() || (varName != null && varName.equals("this"))) {
3798 // using a class name directly or access using this
3799 if (fd.isStatic() && fd.isFinal()) {
3804 NodeTupleSet idxNodeTupleSet = new NodeTupleSet();
3806 if (left instanceof ArrayAccessNode) {
3808 ArrayAccessNode aan = (ArrayAccessNode) left;
3809 left = aan.getExpression();
3810 analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, base,
3811 implicitFlowTupleSet, isLHS);
3813 nodeSet.addTupleSet(idxNodeTupleSet);
3816 analyzeFlowExpressionNode(md, nametable, left, nodeSet, base, implicitFlowTupleSet, isLHS);
3819 // in this case, field is TOP location
3823 NTuple<Descriptor> flowFieldTuple = new NTuple<Descriptor>(base.toList());
3825 if (!left.getType().isPrimitive()) {
3827 if (!fd.getSymbol().equals("length")) {
3828 // array.length access, just have the location of the array
3829 flowFieldTuple.add(fd);
3830 nodeSet.removeTuple(base);
3834 getFlowGraph(md).createNewFlowNode(flowFieldTuple);
3837 for (Iterator<NTuple<Descriptor>> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) {
3838 NTuple<Descriptor> idxTuple = idxIter.next();
3839 getFlowGraph(md).addValueFlowEdge(idxTuple, flowFieldTuple);
3842 return flowFieldTuple;
3848 private void debug_printTreeNode(TreeNode tn) {
3850 System.out.println("DEBUG: " + tn.printNode(0) + " line#=" + tn.getNumLine());
3854 private void analyzeFlowAssignmentNode(MethodDescriptor md, SymbolTable nametable,
3855 AssignmentNode an, NodeTupleSet nodeSet, NTuple<Descriptor> base,
3856 NodeTupleSet implicitFlowTupleSet) {
3858 NodeTupleSet nodeSetRHS = new NodeTupleSet();
3859 NodeTupleSet nodeSetLHS = new NodeTupleSet();
3861 boolean postinc = true;
3862 if (an.getOperation().getBaseOp() == null
3863 || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
3864 .getBaseOp().getOp() != Operation.POSTDEC)) {
3867 // if LHS is array access node, need to capture value flows between an array
3868 // and its index value
3869 analyzeFlowExpressionNode(md, nametable, an.getDest(), nodeSetLHS, null, implicitFlowTupleSet,
3873 // analyze value flows of rhs expression
3874 analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null, implicitFlowTupleSet,
3877 System.out.println("-analyzeFlowAssignmentNode=" + an.printNode(0));
3878 System.out.println("-nodeSetLHS=" + nodeSetLHS);
3879 System.out.println("-nodeSetRHS=" + nodeSetRHS);
3880 System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet);
3881 System.out.println("-");
3883 if (an.getOperation().getOp() >= 2 && an.getOperation().getOp() <= 12) {
3884 // if assignment contains OP+EQ operator, creates edges from LHS to LHS
3886 for (Iterator<NTuple<Descriptor>> iter = nodeSetLHS.iterator(); iter.hasNext();) {
3887 NTuple<Descriptor> fromTuple = iter.next();
3888 for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
3889 NTuple<Descriptor> toTuple = iter2.next();
3890 addFlowGraphEdge(md, fromTuple, toTuple);
3895 // creates edges from RHS to LHS
3896 NTuple<Descriptor> interTuple = null;
3897 if (nodeSetRHS.size() > 1) {
3898 interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
3901 for (Iterator<NTuple<Descriptor>> iter = nodeSetRHS.iterator(); iter.hasNext();) {
3902 NTuple<Descriptor> fromTuple = iter.next();
3903 for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
3904 NTuple<Descriptor> toTuple = iter2.next();
3905 addFlowGraphEdge(md, fromTuple, interTuple, toTuple);
3909 // creates edges from implicitFlowTupleSet to LHS
3910 for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
3911 NTuple<Descriptor> fromTuple = iter.next();
3912 for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
3913 NTuple<Descriptor> toTuple = iter2.next();
3914 addFlowGraphEdge(md, fromTuple, toTuple);
3921 for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
3922 NTuple<Descriptor> tuple = iter2.next();
3923 addFlowGraphEdge(md, tuple, tuple);
3926 // creates edges from implicitFlowTupleSet to LHS
3927 for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
3928 NTuple<Descriptor> fromTuple = iter.next();
3929 for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
3930 NTuple<Descriptor> toTuple = iter2.next();
3931 addFlowGraphEdge(md, fromTuple, toTuple);
3937 if (nodeSet != null) {
3938 nodeSet.addTupleSet(nodeSetLHS);
3942 public FlowGraph getFlowGraph(MethodDescriptor md) {
3943 return mapMethodDescriptorToFlowGraph.get(md);
3946 private boolean addFlowGraphEdge(MethodDescriptor md, NTuple<Descriptor> from,
3947 NTuple<Descriptor> to) {
3948 FlowGraph graph = getFlowGraph(md);
3949 graph.addValueFlowEdge(from, to);
3953 private void addFlowGraphEdge(MethodDescriptor md, NTuple<Descriptor> from,
3954 NTuple<Descriptor> inter, NTuple<Descriptor> to) {
3956 FlowGraph graph = getFlowGraph(md);
3958 if (inter != null) {
3959 graph.addValueFlowEdge(from, inter);
3960 graph.addValueFlowEdge(inter, to);
3962 graph.addValueFlowEdge(from, to);
3967 public void _debug_printGraph() {
3968 Set<MethodDescriptor> keySet = mapMethodDescriptorToFlowGraph.keySet();
3970 for (Iterator<MethodDescriptor> iterator = keySet.iterator(); iterator.hasNext();) {
3971 MethodDescriptor md = (MethodDescriptor) iterator.next();
3972 FlowGraph fg = mapMethodDescriptorToFlowGraph.get(md);
3975 } catch (IOException e) {
3976 e.printStackTrace();
3984 class CyclicFlowException extends Exception {
3988 class InterDescriptor extends Descriptor {
3990 public InterDescriptor(String name) {