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> temp_toanalyzeList;
62 List<MethodDescriptor> temp_toanalyzeMethodList;
63 Map<MethodDescriptor, FlowGraph> mapMethodDescriptorToFlowGraph;
65 LinkedList<MethodDescriptor> toanalyze_methodDescList;
67 // map a method descriptor to its set of parameter descriptors
68 Map<MethodDescriptor, Set<Descriptor>> mapMethodDescriptorToParamDescSet;
70 // keep current descriptors to visit in fixed-point interprocedural analysis,
71 private Stack<MethodDescriptor> methodDescriptorsToVisitStack;
73 // map a class descriptor to a field lattice
74 private Map<ClassDescriptor, SSJavaLattice<String>> cd2lattice;
76 // map a method descriptor to a method lattice
77 private Map<MethodDescriptor, SSJavaLattice<String>> md2lattice;
79 // map a method/class descriptor to a hierarchy graph
80 private Map<Descriptor, HierarchyGraph> mapDescriptorToHierarchyGraph;
82 // map a method/class descriptor to a skeleton hierarchy graph
83 private Map<Descriptor, HierarchyGraph> mapDescriptorToSkeletonHierarchyGraph;
85 private Map<Descriptor, HierarchyGraph> mapDescriptorToSimpleHierarchyGraph;
87 // map a method/class descriptor to a skeleton hierarchy graph with combination nodes
88 private Map<Descriptor, HierarchyGraph> mapDescriptorToCombineSkeletonHierarchyGraph;
90 // map a descriptor to a simple lattice
91 private Map<Descriptor, SSJavaLattice<String>> mapDescriptorToSimpleLattice;
93 // map a method descriptor to the set of method invocation nodes which are
94 // invoked by the method descriptor
95 private Map<MethodDescriptor, Set<MethodInvokeNode>> mapMethodDescriptorToMethodInvokeNodeSet;
97 private Map<MethodInvokeNode, Map<Integer, NodeTupleSet>> mapMethodInvokeNodeToArgIdxMap;
99 private Map<MethodInvokeNode, NTuple<Descriptor>> mapMethodInvokeNodeToBaseTuple;
101 private Map<MethodDescriptor, MethodLocationInfo> mapMethodDescToMethodLocationInfo;
103 private Map<ClassDescriptor, LocationInfo> mapClassToLocationInfo;
105 private Map<MethodDescriptor, Set<MethodDescriptor>> mapMethodToCalleeSet;
107 private Map<MethodDescriptor, Set<FlowNode>> mapMethodDescToParamNodeFlowsToReturnValue;
109 private Map<String, Vector<String>> mapFileNameToLineVector;
111 private Map<Descriptor, Integer> mapDescToDefinitionLine;
113 private Map<Descriptor, LocationSummary> mapDescToLocationSummary;
115 // maps a method descriptor to a sub global flow graph that captures all value flows caused by the
116 // set of callees reachable from the method
117 private Map<MethodDescriptor, FlowGraph> mapMethodDescriptorToSubGlobalFlowGraph;
119 public static final String GLOBALLOC = "GLOBALLOC";
121 public static final String TOPLOC = "TOPLOC";
123 public static final String INTERLOC = "INTERLOC";
125 public static final Descriptor GLOBALDESC = new NameDescriptor(GLOBALLOC);
127 public static final Descriptor TOPDESC = new NameDescriptor(TOPLOC);
129 public static String newline = System.getProperty("line.separator");
131 LocationInfo curMethodInfo;
133 boolean debug = true;
135 private static int locSeed = 0;
137 public LocationInference(SSJavaAnalysis ssjava, State state) {
138 this.ssjava = ssjava;
140 this.temp_toanalyzeList = new ArrayList<ClassDescriptor>();
141 this.temp_toanalyzeMethodList = new ArrayList<MethodDescriptor>();
142 this.mapMethodDescriptorToFlowGraph = new HashMap<MethodDescriptor, FlowGraph>();
143 this.cd2lattice = new HashMap<ClassDescriptor, SSJavaLattice<String>>();
144 this.md2lattice = new HashMap<MethodDescriptor, SSJavaLattice<String>>();
145 this.methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
146 this.mapMethodDescriptorToMethodInvokeNodeSet =
147 new HashMap<MethodDescriptor, Set<MethodInvokeNode>>();
148 this.mapMethodInvokeNodeToArgIdxMap =
149 new HashMap<MethodInvokeNode, Map<Integer, NodeTupleSet>>();
150 this.mapMethodDescToMethodLocationInfo = new HashMap<MethodDescriptor, MethodLocationInfo>();
151 this.mapMethodToCalleeSet = new HashMap<MethodDescriptor, Set<MethodDescriptor>>();
152 this.mapClassToLocationInfo = new HashMap<ClassDescriptor, LocationInfo>();
154 this.mapFileNameToLineVector = new HashMap<String, Vector<String>>();
155 this.mapDescToDefinitionLine = new HashMap<Descriptor, Integer>();
156 this.mapMethodDescToParamNodeFlowsToReturnValue =
157 new HashMap<MethodDescriptor, Set<FlowNode>>();
159 this.mapDescriptorToHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
160 this.mapMethodInvokeNodeToBaseTuple = new HashMap<MethodInvokeNode, NTuple<Descriptor>>();
162 this.mapDescriptorToSkeletonHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
163 this.mapDescriptorToCombineSkeletonHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
164 this.mapDescriptorToSimpleHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
166 this.mapDescriptorToSimpleLattice = new HashMap<Descriptor, SSJavaLattice<String>>();
168 this.mapDescToLocationSummary = new HashMap<Descriptor, LocationSummary>();
170 mapMethodDescriptorToSubGlobalFlowGraph = new HashMap<MethodDescriptor, FlowGraph>();
174 public void setupToAnalyze() {
175 SymbolTable classtable = state.getClassSymbolTable();
176 temp_toanalyzeList.clear();
177 temp_toanalyzeList.addAll(classtable.getValueSet());
178 // Collections.sort(toanalyzeList, new Comparator<ClassDescriptor>() {
179 // public int compare(ClassDescriptor o1, ClassDescriptor o2) {
180 // return o1.getClassName().compareToIgnoreCase(o2.getClassName());
185 public void setupToAnalazeMethod(ClassDescriptor cd) {
187 SymbolTable methodtable = cd.getMethodTable();
188 temp_toanalyzeMethodList.clear();
189 temp_toanalyzeMethodList.addAll(methodtable.getValueSet());
190 Collections.sort(temp_toanalyzeMethodList, new Comparator<MethodDescriptor>() {
191 public int compare(MethodDescriptor o1, MethodDescriptor o2) {
192 return o1.getSymbol().compareToIgnoreCase(o2.getSymbol());
197 public boolean toAnalyzeMethodIsEmpty() {
198 return temp_toanalyzeMethodList.isEmpty();
201 public boolean toAnalyzeIsEmpty() {
202 return temp_toanalyzeList.isEmpty();
205 public ClassDescriptor toAnalyzeNext() {
206 return temp_toanalyzeList.remove(0);
209 public MethodDescriptor toAnalyzeMethodNext() {
210 return temp_toanalyzeMethodList.remove(0);
213 public void inference() {
215 // 1) construct value flow graph
216 constructFlowGraph();
218 constructGlobalFlowGraph();
222 constructHierarchyGraph();
224 debug_writeHierarchyDotFiles();
226 simplifyHierarchyGraph();
228 debug_writeSimpleHierarchyDotFiles();
230 constructSkeletonHierarchyGraph();
232 debug_writeSkeletonHierarchyDotFiles();
234 insertCombinationNodes();
236 debug_writeSkeletonCombinationHierarchyDotFiles();
240 debug_writeLattices();
242 generateMethodSummary();
246 // 2) construct lattices
251 // 3) check properties
254 // calculate RETURNLOC,PCLOC
255 calculateExtraLocations();
257 debug_writeLatticeDotFile();
259 // 4) generate annotated source codes
260 generateAnnoatedCode();
264 private void constructGlobalFlowGraph() {
266 System.out.println("");
267 LinkedList<MethodDescriptor> methodDescList =
268 (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
270 System.out.println("@@@methodDescList=" + methodDescList);
273 while (!methodDescList.isEmpty()) {
274 MethodDescriptor md = methodDescList.removeLast();
275 if (state.SSJAVADEBUG) {
276 System.out.println();
277 System.out.println("SSJAVA: Constructing a global flow graph: " + md);
279 FlowGraph flowGraph = getFlowGraph(md);
280 FlowGraph subGlobalFlowGraph = flowGraph.clone();
281 mapMethodDescriptorToSubGlobalFlowGraph.put(md, subGlobalFlowGraph);
283 addValueFlowsFromCalleeSubGlobalFlowGraph(md, subGlobalFlowGraph);
286 subGlobalFlowGraph.writeGraph("_SUBGLOBAL");
287 } catch (IOException e) {
290 // FlowGraph fg = new FlowGraph(md, mapParamDescToIdx);
291 // mapMethodDescriptorToFlowGraph.put(md, fg);
292 // analyzeMethodBody(md.getClassDesc(), md);
296 // _debug_printGraph();
300 private void addValueFlowsFromCalleeSubGlobalFlowGraph(MethodDescriptor mdCaller,
301 FlowGraph subGlobalFlowGraph) {
303 // the transformation for a call site propagates flows through parameters
304 // if the method is virtual, it also grab all relations from any possible
307 Set<MethodInvokeNode> setMethodInvokeNode = getMethodInvokeNodeSet(mdCaller);
309 for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) {
310 MethodInvokeNode min = (MethodInvokeNode) iterator.next();
311 MethodDescriptor mdCallee = min.getMethod();
312 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
313 if (mdCallee.isStatic()) {
314 setPossibleCallees.add(mdCallee);
316 Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getMethods(mdCallee);
317 // removes method descriptors that are not invoked by the caller
318 calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller));
319 setPossibleCallees.addAll(calleeSet);
322 for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
323 MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
324 propagateValueFlowsToCallerFromSubGlobalFlowGraph(min, mdCaller, possibleMdCallee);
325 // propagateFlowsToCallerWithNoCompositeLocation(min, mdCaller, possibleMdCallee);
332 private void propagateValueFlowsToCallerFromSubGlobalFlowGraph(MethodInvokeNode min,
333 MethodDescriptor mdCaller, MethodDescriptor possibleMdCallee) {
335 NTuple<Descriptor> baseTuple = mapMethodInvokeNodeToBaseTuple.get(min);
337 FlowGraph callerSubGlobalGraph = getSubGlobalFlowGraph(mdCaller);
338 FlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(possibleMdCallee);
340 int numParam = calleeSubGlobalGraph.getNumParameters();
341 for (int idx = 0; idx < numParam; idx++) {
342 FlowNode paramNode = calleeSubGlobalGraph.getParamFlowNode(idx);
343 NodeTupleSet argTupleSet = mapMethodInvokeNodeToArgIdxMap.get(min).get(idx);
344 System.out.println("argTupleSet=" + argTupleSet + " param=" + paramNode);
345 for (Iterator<NTuple<Descriptor>> iter = argTupleSet.iterator(); iter.hasNext();) {
346 NTuple<Descriptor> argTuple = iter.next();
347 addValueFlowsFromCalleeParam(calleeSubGlobalGraph, paramNode, callerSubGlobalGraph,
348 argTuple, baseTuple);
354 private void addValueFlowsFromCalleeParam(FlowGraph calleeSubGlobalGraph, FlowNode paramNode,
355 FlowGraph callerSubGlobalGraph, NTuple<Descriptor> argTuple, NTuple<Descriptor> baseTuple) {
357 Set<FlowNode> visited = new HashSet<FlowNode>();
359 visited.add(paramNode);
360 recurAddValueFlowsFromCalleeParam(calleeSubGlobalGraph, paramNode, callerSubGlobalGraph,
361 argTuple, visited, baseTuple);
364 private void recurAddValueFlowsFromCalleeParam(FlowGraph calleeSubGlobalGraph,
365 FlowNode calleeSrcNode, FlowGraph callerSubGlobalGraph, NTuple<Descriptor> callerSrcTuple,
366 Set<FlowNode> visited, NTuple<Descriptor> baseTuple) {
368 MethodDescriptor mdCallee = calleeSubGlobalGraph.getMethodDescriptor();
370 Set<FlowEdge> edgeSet = calleeSubGlobalGraph.getOutEdgeSet(calleeSrcNode);
371 for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) {
372 FlowEdge flowEdge = (FlowEdge) iterator.next();
373 FlowNode dstNode = flowEdge.getDst();
375 NTuple<Descriptor> dstDescTuple = dstNode.getCurrentDescTuple();
376 if (dstDescTuple.get(0).equals(mdCallee.getThis())) {
377 // destination node is started with 'this' variable
378 // need to translate it in terms of the caller's base node
379 dstDescTuple = translateToCaller(dstDescTuple, baseTuple);
382 callerSubGlobalGraph.addValueFlowEdge(callerSrcTuple, dstDescTuple);
384 if (!visited.contains(dstNode)) {
385 visited.add(dstNode);
386 recurAddValueFlowsFromCalleeParam(calleeSubGlobalGraph, dstNode, callerSubGlobalGraph,
387 dstDescTuple, visited, baseTuple);
394 private NTuple<Descriptor> translateToCaller(NTuple<Descriptor> dstDescTuple,
395 NTuple<Descriptor> baseTuple) {
396 NTuple<Descriptor> callerDescTuple = new NTuple<Descriptor>();
398 callerDescTuple.addAll(baseTuple);
399 for (int i = 1; i < dstDescTuple.size(); i++) {
400 callerDescTuple.add(dstDescTuple.get(i));
403 return callerDescTuple;
406 public LocationSummary getLocationSummary(Descriptor d) {
407 if (!mapDescToLocationSummary.containsKey(d)) {
408 if (d instanceof MethodDescriptor) {
409 mapDescToLocationSummary.put(d, new MethodSummary((MethodDescriptor) d));
410 } else if (d instanceof ClassDescriptor) {
411 mapDescToLocationSummary.put(d, new FieldSummary());
414 return mapDescToLocationSummary.get(d);
417 private void generateMethodSummary() {
419 Set<MethodDescriptor> keySet = md2lattice.keySet();
420 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
421 MethodDescriptor md = (MethodDescriptor) iterator.next();
423 System.out.println("\nSSJAVA: generate method summary: " + md);
425 FlowGraph flowGraph = getFlowGraph(md);
426 MethodSummary methodSummary = getMethodSummary(md);
428 // construct a parameter mapping that maps a parameter descriptor to an inferred composite
431 for (int paramIdx = 0; paramIdx < flowGraph.getNumParameters(); paramIdx++) {
432 FlowNode flowNode = flowGraph.getParamFlowNode(paramIdx);
433 NTuple<Descriptor> descTuple = flowNode.getDescTuple();
435 CompositeLocation assignedCompLoc = flowNode.getCompositeLocation();
436 CompositeLocation inferredCompLoc;
437 if (assignedCompLoc != null) {
438 inferredCompLoc = translateCompositeLocation(assignedCompLoc);
440 Descriptor locDesc = descTuple.get(0);
441 Location loc = new Location(md, locDesc.getSymbol());
442 loc.setLocDescriptor(locDesc);
443 inferredCompLoc = new CompositeLocation(loc);
445 System.out.println("-paramIdx=" + paramIdx + " infer=" + inferredCompLoc);
446 methodSummary.addMapParamIdxToInferLoc(paramIdx, inferredCompLoc);
453 private CompositeLocation translateCompositeLocation(CompositeLocation compLoc) {
454 CompositeLocation newCompLoc = new CompositeLocation();
456 // System.out.println("compLoc=" + compLoc);
457 for (int i = 0; i < compLoc.getSize(); i++) {
458 Location loc = compLoc.get(i);
459 Descriptor enclosingDescriptor = loc.getDescriptor();
460 Descriptor locDescriptor = loc.getLocDescriptor();
462 HNode hnode = getHierarchyGraph(enclosingDescriptor).getHNode(locDescriptor);
463 // System.out.println("-hnode=" + hnode + " from=" + locDescriptor +
464 // " enclosingDescriptor="
465 // + enclosingDescriptor);
466 // System.out.println("-getLocationSummary(enclosingDescriptor)="
467 // + getLocationSummary(enclosingDescriptor));
468 String locName = getLocationSummary(enclosingDescriptor).getLocationName(hnode.getName());
469 // System.out.println("-locName=" + locName);
470 Location newLoc = new Location(enclosingDescriptor, locName);
471 newLoc.setLocDescriptor(locDescriptor);
472 newCompLoc.addLocation(newLoc);
478 private void debug_writeLattices() {
480 Set<Descriptor> keySet = mapDescriptorToSimpleLattice.keySet();
481 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
482 Descriptor key = (Descriptor) iterator.next();
483 SSJavaLattice<String> simpleLattice = mapDescriptorToSimpleLattice.get(key);
484 // HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(key);
485 HierarchyGraph scHierarchyGraph = getSkeletonCombinationHierarchyGraph(key);
486 if (key instanceof ClassDescriptor) {
487 writeInferredLatticeDotFile((ClassDescriptor) key, scHierarchyGraph, simpleLattice,
489 } else if (key instanceof MethodDescriptor) {
490 MethodDescriptor md = (MethodDescriptor) key;
491 writeInferredLatticeDotFile(md.getClassDesc(), md, scHierarchyGraph, simpleLattice,
495 LocationSummary ls = getLocationSummary(key);
496 System.out.println("####LOC SUMMARY=" + key + "\n" + ls.getMapHNodeNameToLocationName());
499 Set<ClassDescriptor> cdKeySet = cd2lattice.keySet();
500 for (Iterator iterator = cdKeySet.iterator(); iterator.hasNext();) {
501 ClassDescriptor cd = (ClassDescriptor) iterator.next();
502 writeInferredLatticeDotFile((ClassDescriptor) cd, getSkeletonCombinationHierarchyGraph(cd),
503 cd2lattice.get(cd), "");
506 Set<MethodDescriptor> mdKeySet = md2lattice.keySet();
507 for (Iterator iterator = mdKeySet.iterator(); iterator.hasNext();) {
508 MethodDescriptor md = (MethodDescriptor) iterator.next();
509 writeInferredLatticeDotFile(md.getClassDesc(), md, getSkeletonCombinationHierarchyGraph(md),
510 md2lattice.get(md), "");
515 private void buildLattice() {
517 BuildLattice buildLattice = new BuildLattice(this);
519 Set<Descriptor> keySet = mapDescriptorToCombineSkeletonHierarchyGraph.keySet();
520 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
521 Descriptor desc = (Descriptor) iterator.next();
523 SSJavaLattice<String> simpleLattice = buildLattice.buildLattice(desc);
525 addMapDescToSimpleLattice(desc, simpleLattice);
527 HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc);
528 System.out.println("## insertIntermediateNodesToStraightLine:"
529 + simpleHierarchyGraph.getName());
530 SSJavaLattice<String> lattice =
531 buildLattice.insertIntermediateNodesToStraightLine(desc, simpleLattice);
532 lattice.removeRedundantEdges();
534 if (desc instanceof ClassDescriptor) {
536 cd2lattice.put((ClassDescriptor) desc, lattice);
537 // ssjava.writeLatticeDotFile((ClassDescriptor) desc, null, lattice);
538 } else if (desc instanceof MethodDescriptor) {
540 md2lattice.put((MethodDescriptor) desc, lattice);
541 MethodDescriptor md = (MethodDescriptor) desc;
542 ClassDescriptor cd = md.getClassDesc();
543 // ssjava.writeLatticeDotFile(cd, md, lattice);
546 // System.out.println("\nSSJAVA: Insering Combination Nodes:" + desc);
547 // HierarchyGraph skeletonGraph = getSkeletonHierarchyGraph(desc);
548 // HierarchyGraph skeletonGraphWithCombinationNode = skeletonGraph.clone();
549 // skeletonGraphWithCombinationNode.setName(desc + "_SC");
551 // HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc);
552 // System.out.println("Identifying Combination Nodes:");
553 // skeletonGraphWithCombinationNode.insertCombinationNodesToGraph(simpleHierarchyGraph);
554 // skeletonGraphWithCombinationNode.simplifySkeletonCombinationHierarchyGraph();
555 // mapDescriptorToCombineSkeletonHierarchyGraph.put(desc, skeletonGraphWithCombinationNode);
560 public void addMapDescToSimpleLattice(Descriptor desc, SSJavaLattice<String> lattice) {
561 mapDescriptorToSimpleLattice.put(desc, lattice);
564 public SSJavaLattice<String> getSimpleLattice(Descriptor desc) {
565 return mapDescriptorToSimpleLattice.get(desc);
568 private void simplifyHierarchyGraph() {
569 Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
570 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
571 Descriptor desc = (Descriptor) iterator.next();
572 HierarchyGraph simpleHierarchyGraph = getHierarchyGraph(desc).clone();
573 simpleHierarchyGraph.setName(desc + "_SIMPLE");
574 simpleHierarchyGraph.removeRedundantEdges();
575 // simpleHierarchyGraph.simplifyHierarchyGraph();
576 mapDescriptorToSimpleHierarchyGraph.put(desc, simpleHierarchyGraph);
580 private void insertCombinationNodes() {
581 Set<Descriptor> keySet = mapDescriptorToSkeletonHierarchyGraph.keySet();
582 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
583 Descriptor desc = (Descriptor) iterator.next();
584 System.out.println("\nSSJAVA: Insering Combination Nodes:" + desc);
585 HierarchyGraph skeletonGraph = getSkeletonHierarchyGraph(desc);
586 HierarchyGraph skeletonGraphWithCombinationNode = skeletonGraph.clone();
587 skeletonGraphWithCombinationNode.setName(desc + "_SC");
589 HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc);
590 System.out.println("Identifying Combination Nodes:");
591 skeletonGraphWithCombinationNode.insertCombinationNodesToGraph(simpleHierarchyGraph);
592 skeletonGraphWithCombinationNode.simplifySkeletonCombinationHierarchyGraph();
593 mapDescriptorToCombineSkeletonHierarchyGraph.put(desc, skeletonGraphWithCombinationNode);
597 private void constructSkeletonHierarchyGraph() {
598 Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
599 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
600 Descriptor desc = (Descriptor) iterator.next();
601 HierarchyGraph simpleGraph = getSimpleHierarchyGraph(desc);
602 HierarchyGraph skeletonGraph = simpleGraph.generateSkeletonGraph();
603 skeletonGraph.setMapDescToHNode(simpleGraph.getMapDescToHNode());
604 skeletonGraph.setMapHNodeToDescSet(simpleGraph.getMapHNodeToDescSet());
605 skeletonGraph.simplifyHierarchyGraph();
606 // skeletonGraph.combineRedundantNodes(false);
607 // skeletonGraph.removeRedundantEdges();
608 mapDescriptorToSkeletonHierarchyGraph.put(desc, skeletonGraph);
612 private void debug_writeHierarchyDotFiles() {
614 Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
615 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
616 Descriptor desc = (Descriptor) iterator.next();
617 getHierarchyGraph(desc).writeGraph();
622 private void debug_writeSimpleHierarchyDotFiles() {
624 Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
625 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
626 Descriptor desc = (Descriptor) iterator.next();
627 getHierarchyGraph(desc).writeGraph();
628 getSimpleHierarchyGraph(desc).writeGraph();
633 private void debug_writeSkeletonHierarchyDotFiles() {
635 Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
636 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
637 Descriptor desc = (Descriptor) iterator.next();
638 getSkeletonHierarchyGraph(desc).writeGraph();
643 private void debug_writeSkeletonCombinationHierarchyDotFiles() {
645 Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
646 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
647 Descriptor desc = (Descriptor) iterator.next();
648 getSkeletonCombinationHierarchyGraph(desc).writeGraph();
653 public HierarchyGraph getSimpleHierarchyGraph(Descriptor d) {
654 return mapDescriptorToSimpleHierarchyGraph.get(d);
657 private HierarchyGraph getSkeletonHierarchyGraph(Descriptor d) {
658 if (!mapDescriptorToSkeletonHierarchyGraph.containsKey(d)) {
659 mapDescriptorToSkeletonHierarchyGraph.put(d, new HierarchyGraph(d));
661 return mapDescriptorToSkeletonHierarchyGraph.get(d);
664 public HierarchyGraph getSkeletonCombinationHierarchyGraph(Descriptor d) {
665 if (!mapDescriptorToCombineSkeletonHierarchyGraph.containsKey(d)) {
666 mapDescriptorToCombineSkeletonHierarchyGraph.put(d, new HierarchyGraph(d));
668 return mapDescriptorToCombineSkeletonHierarchyGraph.get(d);
671 private void constructHierarchyGraph() {
673 // do fixed-point analysis
676 LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
678 // Collections.sort(descriptorListToAnalyze, new
679 // Comparator<MethodDescriptor>() {
680 // public int compare(MethodDescriptor o1, MethodDescriptor o2) {
681 // return o1.getSymbol().compareToIgnoreCase(o2.getSymbol());
685 // current descriptors to visit in fixed-point interprocedural analysis,
686 // prioritized by dependency in the call graph
687 methodDescriptorsToVisitStack.clear();
689 Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
690 methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
692 while (!descriptorListToAnalyze.isEmpty()) {
693 MethodDescriptor md = descriptorListToAnalyze.removeFirst();
694 methodDescriptorsToVisitStack.add(md);
697 // analyze scheduled methods until there are no more to visit
698 while (!methodDescriptorsToVisitStack.isEmpty()) {
699 // start to analyze leaf node
700 MethodDescriptor md = methodDescriptorsToVisitStack.pop();
702 HierarchyGraph hierarchyGraph = new HierarchyGraph(md);
703 // MethodSummary methodSummary = new MethodSummary(md);
705 // MethodLocationInfo methodInfo = new MethodLocationInfo(md);
706 // curMethodInfo = methodInfo;
708 System.out.println();
709 System.out.println("SSJAVA: Construcing the hierarchy graph from " + md);
711 constructHierarchyGraph(md, hierarchyGraph);
713 HierarchyGraph prevHierarchyGraph = getHierarchyGraph(md);
714 // MethodSummary prevMethodSummary = getMethodSummary(md);
716 if (!hierarchyGraph.equals(prevHierarchyGraph)) {
718 mapDescriptorToHierarchyGraph.put(md, hierarchyGraph);
719 // mapDescToLocationSummary.put(md, methodSummary);
721 // results for callee changed, so enqueue dependents caller for
723 Iterator<MethodDescriptor> depsItr = ssjava.getDependents(md).iterator();
724 while (depsItr.hasNext()) {
725 MethodDescriptor methodNext = depsItr.next();
726 if (!methodDescriptorsToVisitStack.contains(methodNext)
727 && methodDescriptorToVistSet.contains(methodNext)) {
728 methodDescriptorsToVisitStack.add(methodNext);
738 private HierarchyGraph getHierarchyGraph(Descriptor d) {
739 if (!mapDescriptorToHierarchyGraph.containsKey(d)) {
740 mapDescriptorToHierarchyGraph.put(d, new HierarchyGraph(d));
742 return mapDescriptorToHierarchyGraph.get(d);
745 private void constructHierarchyGraph(MethodDescriptor md, HierarchyGraph methodGraph) {
747 // visit each node of method flow graph
748 FlowGraph fg = getFlowGraph(md);
749 Set<FlowNode> nodeSet = fg.getNodeSet();
751 Set<Descriptor> paramDescSet = fg.getMapParamDescToIdx().keySet();
752 for (Iterator iterator = paramDescSet.iterator(); iterator.hasNext();) {
753 Descriptor desc = (Descriptor) iterator.next();
754 methodGraph.getHNode(desc).setSkeleton(true);
757 // for the method lattice, we need to look at the first element of
758 // NTuple<Descriptor>
759 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
760 FlowNode srcNode = (FlowNode) iterator.next();
762 Set<FlowEdge> outEdgeSet = fg.getOutEdgeSet(srcNode);
763 for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) {
764 FlowEdge outEdge = (FlowEdge) iterator2.next();
765 FlowNode dstNode = outEdge.getDst();
767 NTuple<Descriptor> srcNodeTuple = srcNode.getDescTuple();
768 NTuple<Descriptor> dstNodeTuple = dstNode.getDescTuple();
770 if (outEdge.getInitTuple().equals(srcNodeTuple)
771 && outEdge.getEndTuple().equals(dstNodeTuple)) {
773 NTuple<Descriptor> srcCurTuple = srcNode.getCurrentDescTuple();
774 NTuple<Descriptor> dstCurTuple = dstNode.getCurrentDescTuple();
776 if ((srcCurTuple.size() > 1 && dstCurTuple.size() > 1)
777 && srcCurTuple.get(0).equals(dstCurTuple.get(0))) {
779 // value flows between fields
780 Descriptor desc = srcCurTuple.get(0);
781 ClassDescriptor classDesc;
783 if (desc.equals(GLOBALDESC)) {
784 classDesc = md.getClassDesc();
786 VarDescriptor varDesc = (VarDescriptor) srcCurTuple.get(0);
787 classDesc = varDesc.getType().getClassDesc();
789 extractFlowsBetweenFields(classDesc, srcNode, dstNode, 1);
792 // value flow between local var - local var or local var - field
794 Descriptor srcDesc = srcCurTuple.get(0);
795 Descriptor dstDesc = dstCurTuple.get(0);
797 methodGraph.addEdge(srcDesc, dstDesc);
799 if (fg.isParamDesc(srcDesc)) {
800 methodGraph.setParamHNode(srcDesc);
802 if (fg.isParamDesc(dstDesc)) {
803 methodGraph.setParamHNode(dstDesc);
814 private MethodSummary getMethodSummary(MethodDescriptor md) {
815 if (!mapDescToLocationSummary.containsKey(md)) {
816 mapDescToLocationSummary.put(md, new MethodSummary(md));
818 return (MethodSummary) mapDescToLocationSummary.get(md);
821 private void addMapClassDefinitionToLineNum(ClassDescriptor cd, String strLine, int lineNum) {
823 String classSymbol = cd.getSymbol();
824 int idx = classSymbol.lastIndexOf("$");
826 classSymbol = classSymbol.substring(idx + 1);
829 String pattern = "class " + classSymbol + " ";
830 if (strLine.indexOf(pattern) != -1) {
831 mapDescToDefinitionLine.put(cd, lineNum);
835 private void addMapMethodDefinitionToLineNum(Set<MethodDescriptor> methodSet, String strLine,
837 for (Iterator iterator = methodSet.iterator(); iterator.hasNext();) {
838 MethodDescriptor md = (MethodDescriptor) iterator.next();
839 String pattern = md.getMethodDeclaration();
840 if (strLine.indexOf(pattern) != -1) {
841 mapDescToDefinitionLine.put(md, lineNum);
842 methodSet.remove(md);
849 private void readOriginalSourceFiles() {
851 SymbolTable classtable = state.getClassSymbolTable();
853 Set<ClassDescriptor> classDescSet = new HashSet<ClassDescriptor>();
854 classDescSet.addAll(classtable.getValueSet());
857 // inefficient implement. it may re-visit the same file if the file
858 // contains more than one class definitions.
859 for (Iterator iterator = classDescSet.iterator(); iterator.hasNext();) {
860 ClassDescriptor cd = (ClassDescriptor) iterator.next();
862 Set<MethodDescriptor> methodSet = new HashSet<MethodDescriptor>();
863 methodSet.addAll(cd.getMethodTable().getValueSet());
865 String sourceFileName = cd.getSourceFileName();
866 Vector<String> lineVec = new Vector<String>();
868 mapFileNameToLineVector.put(sourceFileName, lineVec);
870 BufferedReader in = new BufferedReader(new FileReader(sourceFileName));
873 lineVec.add(""); // the index is started from 1.
874 while ((strLine = in.readLine()) != null) {
875 lineVec.add(lineNum, strLine);
876 addMapClassDefinitionToLineNum(cd, strLine, lineNum);
877 addMapMethodDefinitionToLineNum(methodSet, strLine, lineNum);
883 } catch (IOException e) {
889 private String generateLatticeDefinition(Descriptor desc) {
891 Set<String> sharedLocSet = new HashSet<String>();
893 SSJavaLattice<String> lattice = getLattice(desc);
894 String rtr = "@LATTICE(\"";
896 Map<String, Set<String>> map = lattice.getTable();
897 Set<String> keySet = map.keySet();
898 boolean first = true;
899 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
900 String key = (String) iterator.next();
901 if (!key.equals(lattice.getTopItem())) {
902 Set<String> connectedSet = map.get(key);
904 if (connectedSet.size() == 1) {
905 if (connectedSet.iterator().next().equals(lattice.getBottomItem())) {
913 if (lattice.isSharedLoc(key)) {
914 rtr += "," + key + "*";
919 for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) {
920 String loc = (String) iterator2.next();
921 if (!loc.equals(lattice.getBottomItem())) {
928 rtr += loc + "<" + key;
929 if (lattice.isSharedLoc(key) && (!sharedLocSet.contains(key))) {
930 rtr += "," + key + "*";
931 sharedLocSet.add(key);
933 if (lattice.isSharedLoc(loc) && (!sharedLocSet.contains(loc))) {
934 rtr += "," + loc + "*";
935 sharedLocSet.add(loc);
945 if (desc instanceof MethodDescriptor) {
946 TypeDescriptor returnType = ((MethodDescriptor) desc).getReturnType();
948 MethodLocationInfo methodLocInfo = getMethodLocationInfo((MethodDescriptor) desc);
950 if (returnType != null && (!returnType.isVoid())) {
952 "\n@RETURNLOC(\"" + generateLocationAnnoatation(methodLocInfo.getReturnLoc()) + "\")";
955 rtr += "\n@THISLOC(\"this\")";
956 rtr += "\n@GLOBALLOC(\"GLOBALLOC\")";
958 CompositeLocation pcLoc = methodLocInfo.getPCLoc();
959 if ((pcLoc != null) && (!pcLoc.get(0).isTop())) {
960 rtr += "\n@PCLOC(\"" + generateLocationAnnoatation(pcLoc) + "\")";
968 private void generateAnnoatedCode() {
970 readOriginalSourceFiles();
973 while (!toAnalyzeIsEmpty()) {
974 ClassDescriptor cd = toAnalyzeNext();
976 setupToAnalazeMethod(cd);
978 LocationInfo locInfo = mapClassToLocationInfo.get(cd);
979 String sourceFileName = cd.getSourceFileName();
981 if (cd.isInterface()) {
985 int classDefLine = mapDescToDefinitionLine.get(cd);
986 Vector<String> sourceVec = mapFileNameToLineVector.get(sourceFileName);
988 if (locInfo == null) {
989 locInfo = getLocationInfo(cd);
992 for (Iterator iter = cd.getFields(); iter.hasNext();) {
993 FieldDescriptor fieldDesc = (FieldDescriptor) iter.next();
994 if (!(fieldDesc.isStatic() && fieldDesc.isFinal())) {
995 String locIdentifier = locInfo.getFieldInferLocation(fieldDesc).getLocIdentifier();
996 if (!getLattice(cd).getElementSet().contains(locIdentifier)) {
997 getLattice(cd).put(locIdentifier);
1002 String fieldLatticeDefStr = generateLatticeDefinition(cd);
1003 String annoatedSrc = fieldLatticeDefStr + newline + sourceVec.get(classDefLine);
1004 sourceVec.set(classDefLine, annoatedSrc);
1006 // generate annotations for field declarations
1007 LocationInfo fieldLocInfo = getLocationInfo(cd);
1008 Map<Descriptor, CompositeLocation> inferLocMap = fieldLocInfo.getMapDescToInferLocation();
1010 for (Iterator iter = cd.getFields(); iter.hasNext();) {
1011 FieldDescriptor fd = (FieldDescriptor) iter.next();
1013 String locAnnotationStr;
1014 CompositeLocation inferLoc = inferLocMap.get(fd);
1016 if (inferLoc != null) {
1017 // infer loc is null if the corresponding field is static and final
1018 locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")";
1019 int fdLineNum = fd.getLineNum();
1020 String orgFieldDeclarationStr = sourceVec.get(fdLineNum);
1021 String fieldDeclaration = fd.toString();
1022 fieldDeclaration = fieldDeclaration.substring(0, fieldDeclaration.length() - 1);
1023 String annoatedStr = locAnnotationStr + " " + orgFieldDeclarationStr;
1024 sourceVec.set(fdLineNum, annoatedStr);
1029 while (!toAnalyzeMethodIsEmpty()) {
1030 MethodDescriptor md = toAnalyzeMethodNext();
1032 if (!ssjava.needTobeAnnotated(md)) {
1036 SSJavaLattice<String> methodLattice = md2lattice.get(md);
1037 if (methodLattice != null) {
1039 int methodDefLine = md.getLineNum();
1041 MethodLocationInfo methodLocInfo = getMethodLocationInfo(md);
1043 Map<Descriptor, CompositeLocation> methodInferLocMap =
1044 methodLocInfo.getMapDescToInferLocation();
1045 Set<Descriptor> localVarDescSet = methodInferLocMap.keySet();
1047 Set<String> localLocElementSet = methodLattice.getElementSet();
1049 for (Iterator iterator = localVarDescSet.iterator(); iterator.hasNext();) {
1050 Descriptor localVarDesc = (Descriptor) iterator.next();
1051 CompositeLocation inferLoc = methodInferLocMap.get(localVarDesc);
1053 String localLocIdentifier = inferLoc.get(0).getLocIdentifier();
1054 if (!localLocElementSet.contains(localLocIdentifier)) {
1055 methodLattice.put(localLocIdentifier);
1058 String locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")";
1060 if (!isParameter(md, localVarDesc)) {
1061 if (mapDescToDefinitionLine.containsKey(localVarDesc)) {
1062 int varLineNum = mapDescToDefinitionLine.get(localVarDesc);
1063 String orgSourceLine = sourceVec.get(varLineNum);
1065 orgSourceLine.indexOf(generateVarDeclaration((VarDescriptor) localVarDesc));
1067 String annoatedStr =
1068 orgSourceLine.substring(0, idx) + locAnnotationStr + " "
1069 + orgSourceLine.substring(idx);
1070 sourceVec.set(varLineNum, annoatedStr);
1073 String methodDefStr = sourceVec.get(methodDefLine);
1076 getParamLocation(methodDefStr,
1077 generateVarDeclaration((VarDescriptor) localVarDesc));
1081 String annoatedStr =
1082 methodDefStr.substring(0, idx) + locAnnotationStr + " "
1083 + methodDefStr.substring(idx);
1084 sourceVec.set(methodDefLine, annoatedStr);
1089 // check if the lattice has to have the location type for the this
1092 // boolean needToAddthisRef = hasThisReference(md);
1093 if (localLocElementSet.contains("this")) {
1094 methodLattice.put("this");
1097 String methodLatticeDefStr = generateLatticeDefinition(md);
1098 String annoatedStr = methodLatticeDefStr + newline + sourceVec.get(methodDefLine);
1099 sourceVec.set(methodDefLine, annoatedStr);
1109 private boolean hasThisReference(MethodDescriptor md) {
1111 FlowGraph fg = getFlowGraph(md);
1112 Set<FlowNode> nodeSet = fg.getNodeSet();
1113 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1114 FlowNode flowNode = (FlowNode) iterator.next();
1115 if (flowNode.getDescTuple().get(0).equals(md.getThis())) {
1123 private int getParamLocation(String methodStr, String paramStr) {
1125 String pattern = paramStr + ",";
1127 int idx = methodStr.indexOf(pattern);
1131 pattern = paramStr + ")";
1132 return methodStr.indexOf(pattern);
1137 private String generateVarDeclaration(VarDescriptor varDesc) {
1139 TypeDescriptor td = varDesc.getType();
1140 String rtr = td.toString();
1142 for (int i = 0; i < td.getArrayCount(); i++) {
1146 rtr += " " + varDesc.getName();
1151 private String generateLocationAnnoatation(CompositeLocation loc) {
1154 Location methodLoc = loc.get(0);
1155 rtr += methodLoc.getLocIdentifier();
1157 for (int i = 1; i < loc.getSize(); i++) {
1158 Location element = loc.get(i);
1159 rtr += "," + element.getDescriptor().getSymbol() + "." + element.getLocIdentifier();
1165 private boolean isParameter(MethodDescriptor md, Descriptor localVarDesc) {
1166 return getFlowGraph(md).isParamDesc(localVarDesc);
1169 private String extractFileName(String fileName) {
1170 int idx = fileName.lastIndexOf("/");
1174 return fileName.substring(idx + 1);
1179 private void codeGen() {
1181 Set<String> originalFileNameSet = mapFileNameToLineVector.keySet();
1182 for (Iterator iterator = originalFileNameSet.iterator(); iterator.hasNext();) {
1183 String orgFileName = (String) iterator.next();
1184 String outputFileName = extractFileName(orgFileName);
1186 Vector<String> sourceVec = mapFileNameToLineVector.get(orgFileName);
1190 FileWriter fileWriter = new FileWriter("./infer/" + outputFileName);
1191 BufferedWriter out = new BufferedWriter(fileWriter);
1193 for (int i = 0; i < sourceVec.size(); i++) {
1194 out.write(sourceVec.get(i));
1198 } catch (IOException e) {
1199 e.printStackTrace();
1206 private void simplifyLattices() {
1210 while (!toAnalyzeIsEmpty()) {
1211 ClassDescriptor cd = toAnalyzeNext();
1212 setupToAnalazeMethod(cd);
1214 SSJavaLattice<String> classLattice = cd2lattice.get(cd);
1215 if (classLattice != null) {
1216 System.out.println("@@@check lattice=" + cd);
1217 checkLatticeProperty(cd, classLattice);
1220 while (!toAnalyzeMethodIsEmpty()) {
1221 MethodDescriptor md = toAnalyzeMethodNext();
1222 SSJavaLattice<String> methodLattice = md2lattice.get(md);
1223 if (methodLattice != null) {
1224 System.out.println("@@@check lattice=" + md);
1225 checkLatticeProperty(md, methodLattice);
1232 while (!toAnalyzeIsEmpty()) {
1233 ClassDescriptor cd = toAnalyzeNext();
1235 setupToAnalazeMethod(cd);
1237 SSJavaLattice<String> classLattice = cd2lattice.get(cd);
1238 if (classLattice != null) {
1239 classLattice.removeRedundantEdges();
1242 while (!toAnalyzeMethodIsEmpty()) {
1243 MethodDescriptor md = toAnalyzeMethodNext();
1244 SSJavaLattice<String> methodLattice = md2lattice.get(md);
1245 if (methodLattice != null) {
1246 methodLattice.removeRedundantEdges();
1253 private boolean checkLatticeProperty(Descriptor d, SSJavaLattice<String> lattice) {
1254 // if two elements has the same incoming node set,
1255 // we need to merge two elements ...
1258 boolean isModified = false;
1260 isUpdated = removeNodeSharingSameIncomingNodes(d, lattice);
1261 if (!isModified && isUpdated) {
1264 } while (isUpdated);
1269 private boolean removeNodeSharingSameIncomingNodes(Descriptor d, SSJavaLattice<String> lattice) {
1270 LocationInfo locInfo = getLocationInfo(d);
1271 Map<String, Set<String>> map = lattice.getIncomingElementMap();
1272 Set<String> keySet = map.keySet();
1273 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1274 String key = (String) iterator.next();
1275 Set<String> incomingSetKey = map.get(key);
1277 // System.out.println("key=" + key + " incomingSetKey=" +
1279 if (incomingSetKey.size() > 0) {
1280 for (Iterator iterator2 = keySet.iterator(); iterator2.hasNext();) {
1281 String cur = (String) iterator2.next();
1282 if (!cur.equals(key)) {
1283 Set<String> incomingSetCur = map.get(cur);
1284 if (incomingSetCur.equals(incomingSetKey)) {
1285 if (!(incomingSetCur.size() == 1 && incomingSetCur.contains(lattice.getTopItem()))) {
1286 // NEED TO MERGE HERE!!!!
1287 System.out.println("@@@Try merge=" + cur + " " + key);
1289 Set<String> mergeSet = new HashSet<String>();
1293 String newMergeLoc = "MLoc" + (SSJavaLattice.seed++);
1295 System.out.println("---ASSIGN NEW MERGE LOC=" + newMergeLoc + " to " + mergeSet);
1296 lattice.mergeIntoNewLocation(mergeSet, newMergeLoc);
1298 for (Iterator miterator = mergeSet.iterator(); miterator.hasNext();) {
1299 String oldLocSymbol = (String) miterator.next();
1301 Set<Pair<Descriptor, Descriptor>> inferLocSet =
1302 locInfo.getRelatedInferLocSet(oldLocSymbol);
1303 System.out.println("---update related locations=" + inferLocSet
1304 + " oldLocSymbol=" + oldLocSymbol);
1306 for (Iterator miterator2 = inferLocSet.iterator(); miterator2.hasNext();) {
1307 Pair<Descriptor, Descriptor> pair =
1308 (Pair<Descriptor, Descriptor>) miterator2.next();
1309 Descriptor enclosingDesc = pair.getFirst();
1310 Descriptor desc = pair.getSecond();
1312 System.out.println("---inferLoc pair=" + pair);
1314 CompositeLocation inferLoc =
1315 getLocationInfo(enclosingDesc).getInferLocation(desc);
1316 System.out.println("oldLoc=" + inferLoc);
1317 // if (curMethodInfo.md.equals(enclosingDesc)) {
1318 // inferLoc = curMethodInfo.getInferLocation(desc);
1321 // getLocationInfo(enclosingDesc).getInferLocation(desc);
1324 Location locElement = inferLoc.get(inferLoc.getSize() - 1);
1326 locElement.setLocIdentifier(newMergeLoc);
1327 locInfo.addMapLocSymbolToRelatedInferLoc(newMergeLoc, enclosingDesc, desc);
1329 // if (curMethodInfo.md.equals(enclosingDesc)) {
1330 // inferLoc = curMethodInfo.getInferLocation(desc);
1333 // getLocationInfo(enclosingDesc).getInferLocation(desc);
1336 inferLoc = getLocationInfo(enclosingDesc).getInferLocation(desc);
1337 System.out.println("---New Infer Loc=" + inferLoc);
1341 locInfo.removeRelatedInferLocSet(oldLocSymbol, newMergeLoc);
1345 for (Iterator iterator3 = mergeSet.iterator(); iterator3.hasNext();) {
1346 String oldLoc = (String) iterator3.next();
1347 lattice.remove(oldLoc);
1360 private void checkLattices() {
1362 LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
1364 // current descriptors to visit in fixed-point interprocedural analysis,
1366 // dependency in the call graph
1367 methodDescriptorsToVisitStack.clear();
1369 // descriptorListToAnalyze.removeFirst();
1371 Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
1372 methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
1374 while (!descriptorListToAnalyze.isEmpty()) {
1375 MethodDescriptor md = descriptorListToAnalyze.removeFirst();
1376 checkLatticesOfVirtualMethods(md);
1381 private void debug_writeLatticeDotFile() {
1382 // generate lattice dot file
1386 while (!toAnalyzeIsEmpty()) {
1387 ClassDescriptor cd = toAnalyzeNext();
1389 setupToAnalazeMethod(cd);
1391 SSJavaLattice<String> classLattice = cd2lattice.get(cd);
1392 if (classLattice != null) {
1393 ssjava.writeLatticeDotFile(cd, null, classLattice);
1394 debug_printDescriptorToLocNameMapping(cd);
1397 while (!toAnalyzeMethodIsEmpty()) {
1398 MethodDescriptor md = toAnalyzeMethodNext();
1399 SSJavaLattice<String> methodLattice = md2lattice.get(md);
1400 if (methodLattice != null) {
1401 ssjava.writeLatticeDotFile(cd, md, methodLattice);
1402 debug_printDescriptorToLocNameMapping(md);
1409 private void debug_printDescriptorToLocNameMapping(Descriptor desc) {
1411 LocationInfo info = getLocationInfo(desc);
1412 System.out.println("## " + desc + " ##");
1413 System.out.println(info.getMapDescToInferLocation());
1414 LocationInfo locInfo = getLocationInfo(desc);
1415 System.out.println("mapping=" + locInfo.getMapLocSymbolToDescSet());
1416 System.out.println("###################");
1420 private void inferLattices() {
1422 // do fixed-point analysis
1425 LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
1427 // Collections.sort(descriptorListToAnalyze, new
1428 // Comparator<MethodDescriptor>() {
1429 // public int compare(MethodDescriptor o1, MethodDescriptor o2) {
1430 // return o1.getSymbol().compareToIgnoreCase(o2.getSymbol());
1434 // current descriptors to visit in fixed-point interprocedural analysis,
1436 // dependency in the call graph
1437 methodDescriptorsToVisitStack.clear();
1439 // descriptorListToAnalyze.removeFirst();
1441 Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
1442 methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
1444 while (!descriptorListToAnalyze.isEmpty()) {
1445 MethodDescriptor md = descriptorListToAnalyze.removeFirst();
1446 methodDescriptorsToVisitStack.add(md);
1449 // analyze scheduled methods until there are no more to visit
1450 while (!methodDescriptorsToVisitStack.isEmpty()) {
1451 // start to analyze leaf node
1452 MethodDescriptor md = methodDescriptorsToVisitStack.pop();
1454 SSJavaLattice<String> methodLattice =
1455 new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM);
1457 MethodLocationInfo methodInfo = new MethodLocationInfo(md);
1458 curMethodInfo = methodInfo;
1460 System.out.println();
1461 System.out.println("SSJAVA: Inferencing the lattice from " + md);
1464 analyzeMethodLattice(md, methodLattice, methodInfo);
1465 } catch (CyclicFlowException e) {
1466 throw new Error("Fail to generate the method lattice for " + md);
1469 SSJavaLattice<String> prevMethodLattice = getMethodLattice(md);
1470 MethodLocationInfo prevMethodInfo = getMethodLocationInfo(md);
1472 if ((!methodLattice.equals(prevMethodLattice)) || (!methodInfo.equals(prevMethodInfo))) {
1474 setMethodLattice(md, methodLattice);
1475 setMethodLocInfo(md, methodInfo);
1477 // results for callee changed, so enqueue dependents caller for
1479 Iterator<MethodDescriptor> depsItr = ssjava.getDependents(md).iterator();
1480 while (depsItr.hasNext()) {
1481 MethodDescriptor methodNext = depsItr.next();
1482 if (!methodDescriptorsToVisitStack.contains(methodNext)
1483 && methodDescriptorToVistSet.contains(methodNext)) {
1484 methodDescriptorsToVisitStack.add(methodNext);
1494 private void calculateExtraLocations() {
1495 LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
1496 for (Iterator iterator = descriptorListToAnalyze.iterator(); iterator.hasNext();) {
1497 MethodDescriptor md = (MethodDescriptor) iterator.next();
1498 calculateExtraLocations(md);
1502 private void setMethodLocInfo(MethodDescriptor md, MethodLocationInfo methodInfo) {
1503 mapMethodDescToMethodLocationInfo.put(md, methodInfo);
1506 private void checkLatticesOfVirtualMethods(MethodDescriptor md) {
1508 if (!md.isStatic()) {
1509 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
1510 setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md));
1512 for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
1513 MethodDescriptor mdCallee = (MethodDescriptor) iterator.next();
1514 if (!md.equals(mdCallee)) {
1515 checkConsistency(md, mdCallee);
1523 private void checkConsistency(MethodDescriptor md1, MethodDescriptor md2) {
1525 // check that two lattice have the same relations between parameters(+PC
1526 // LOC, GLOBAL_LOC RETURN LOC)
1528 List<CompositeLocation> list1 = new ArrayList<CompositeLocation>();
1529 List<CompositeLocation> list2 = new ArrayList<CompositeLocation>();
1531 MethodLocationInfo locInfo1 = getMethodLocationInfo(md1);
1532 MethodLocationInfo locInfo2 = getMethodLocationInfo(md2);
1534 Map<Integer, CompositeLocation> paramMap1 = locInfo1.getMapParamIdxToInferLoc();
1535 Map<Integer, CompositeLocation> paramMap2 = locInfo2.getMapParamIdxToInferLoc();
1537 int numParam = locInfo1.getMapParamIdxToInferLoc().keySet().size();
1539 // add location types of paramters
1540 for (int idx = 0; idx < numParam; idx++) {
1541 list1.add(paramMap1.get(Integer.valueOf(idx)));
1542 list2.add(paramMap2.get(Integer.valueOf(idx)));
1545 // add program counter location
1546 list1.add(locInfo1.getPCLoc());
1547 list2.add(locInfo2.getPCLoc());
1549 if (!md1.getReturnType().isVoid()) {
1550 // add return value location
1551 CompositeLocation rtrLoc1 = getMethodLocationInfo(md1).getReturnLoc();
1552 CompositeLocation rtrLoc2 = getMethodLocationInfo(md2).getReturnLoc();
1557 // add global location type
1558 if (md1.isStatic()) {
1559 CompositeLocation globalLoc1 =
1560 new CompositeLocation(new Location(md1, locInfo1.getGlobalLocName()));
1561 CompositeLocation globalLoc2 =
1562 new CompositeLocation(new Location(md2, locInfo2.getGlobalLocName()));
1563 list1.add(globalLoc1);
1564 list2.add(globalLoc2);
1567 for (int i = 0; i < list1.size(); i++) {
1568 CompositeLocation locA1 = list1.get(i);
1569 CompositeLocation locA2 = list2.get(i);
1570 for (int k = 0; k < list1.size(); k++) {
1572 CompositeLocation locB1 = list1.get(k);
1573 CompositeLocation locB2 = list2.get(k);
1574 boolean r1 = isGreaterThan(getLattice(md1), locA1, locB1);
1576 boolean r2 = isGreaterThan(getLattice(md1), locA2, locB2);
1579 throw new Error("The method " + md1 + " is not consistent with the method " + md2
1580 + ".:: They have a different ordering relation between locations (" + locA1 + ","
1581 + locB1 + ") and (" + locA2 + "," + locB2 + ").");
1589 private String getSymbol(int idx, FlowNode node) {
1590 Descriptor desc = node.getDescTuple().get(idx);
1591 return desc.getSymbol();
1594 private Descriptor getDescriptor(int idx, FlowNode node) {
1595 Descriptor desc = node.getDescTuple().get(idx);
1599 private void analyzeMethodLattice(MethodDescriptor md, SSJavaLattice<String> methodLattice,
1600 MethodLocationInfo methodInfo) throws CyclicFlowException {
1602 // first take a look at method invocation nodes to newly added relations
1604 analyzeLatticeMethodInvocationNode(md, methodLattice, methodInfo);
1606 if (!md.isStatic()) {
1607 // set the this location
1608 String thisLocSymbol = md.getThis().getSymbol();
1609 methodInfo.setThisLocName(thisLocSymbol);
1612 // set the global location
1613 methodInfo.setGlobalLocName(LocationInference.GLOBALLOC);
1614 methodInfo.mapDescriptorToLocation(GLOBALDESC, new CompositeLocation(
1615 new Location(md, GLOBALLOC)));
1617 // visit each node of method flow graph
1618 FlowGraph fg = getFlowGraph(md);
1619 Set<FlowNode> nodeSet = fg.getNodeSet();
1621 // for the method lattice, we need to look at the first element of
1622 // NTuple<Descriptor>
1623 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1624 FlowNode srcNode = (FlowNode) iterator.next();
1626 Set<FlowEdge> outEdgeSet = fg.getOutEdgeSet(srcNode);
1627 for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) {
1628 FlowEdge outEdge = (FlowEdge) iterator2.next();
1629 FlowNode dstNode = outEdge.getDst();
1631 NTuple<Descriptor> srcNodeTuple = srcNode.getDescTuple();
1632 NTuple<Descriptor> dstNodeTuple = dstNode.getDescTuple();
1634 if (outEdge.getInitTuple().equals(srcNodeTuple)
1635 && outEdge.getEndTuple().equals(dstNodeTuple)) {
1637 if ((srcNodeTuple.size() > 1 && dstNodeTuple.size() > 1)
1638 && srcNodeTuple.get(0).equals(dstNodeTuple.get(0))) {
1640 // value flows between fields
1641 Descriptor desc = srcNodeTuple.get(0);
1642 ClassDescriptor classDesc;
1644 if (desc.equals(GLOBALDESC)) {
1645 classDesc = md.getClassDesc();
1647 VarDescriptor varDesc = (VarDescriptor) srcNodeTuple.get(0);
1648 classDesc = varDesc.getType().getClassDesc();
1650 extractRelationFromFieldFlows(classDesc, srcNode, dstNode, 1);
1653 // value flow between local var - local var or local var - field
1654 addRelationToLattice(md, methodLattice, methodInfo, srcNode, dstNode);
1660 // create mapping from param idx to inferred composite location
1663 if (!md.isStatic()) {
1664 // add 'this' reference location
1666 methodInfo.addMapParamIdxToInferLoc(0, methodInfo.getInferLocation(md.getThis()));
1671 for (int idx = 0; idx < md.numParameters(); idx++) {
1672 Descriptor paramDesc = md.getParameter(idx);
1673 CompositeLocation inferParamLoc = methodInfo.getInferLocation(paramDesc);
1674 methodInfo.addMapParamIdxToInferLoc(idx + offset, inferParamLoc);
1679 private void calculateExtraLocations(MethodDescriptor md) {
1680 // calcualte pcloc, returnloc,...
1682 SSJavaLattice<String> methodLattice = getMethodLattice(md);
1683 MethodLocationInfo methodInfo = getMethodLocationInfo(md);
1684 FlowGraph fg = getFlowGraph(md);
1685 Set<FlowNode> nodeSet = fg.getNodeSet();
1687 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1688 FlowNode flowNode = (FlowNode) iterator.next();
1689 if (flowNode.isDeclaratonNode()) {
1690 CompositeLocation inferLoc = methodInfo.getInferLocation(flowNode.getDescTuple().get(0));
1691 String locIdentifier = inferLoc.get(0).getLocIdentifier();
1692 if (!methodLattice.containsKey(locIdentifier)) {
1693 methodLattice.put(locIdentifier);
1699 Map<Integer, CompositeLocation> mapParamToLoc = methodInfo.getMapParamIdxToInferLoc();
1700 Set<Integer> paramIdxSet = mapParamToLoc.keySet();
1703 if (!ssjava.getMethodContainingSSJavaLoop().equals(md)) {
1704 // calculate the initial program counter location
1705 // PC location is higher than location types of all parameters
1706 String pcLocSymbol = "PCLOC";
1708 Set<CompositeLocation> paramInFlowSet = new HashSet<CompositeLocation>();
1710 for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) {
1711 Integer paramIdx = (Integer) iterator.next();
1713 FlowNode paramFlowNode = fg.getParamFlowNode(paramIdx);
1715 if (fg.getIncomingFlowNodeSet(paramFlowNode).size() > 0) {
1716 // parameter has in-value flows
1717 CompositeLocation inferLoc = mapParamToLoc.get(paramIdx);
1718 paramInFlowSet.add(inferLoc);
1722 if (paramInFlowSet.size() > 0) {
1723 CompositeLocation lowestLoc = getLowest(methodLattice, paramInFlowSet);
1724 assert (lowestLoc != null);
1725 methodInfo.setPCLoc(lowestLoc);
1730 // calculate a return location
1731 // the return location type is lower than all parameters and location
1734 if (!md.getReturnType().isVoid()) {
1735 // first, generate the set of return value location types that starts
1739 Set<CompositeLocation> inferFieldReturnLocSet = new HashSet<CompositeLocation>();
1741 Set<FlowNode> paramFlowNode = getParamNodeFlowingToReturnValue(md);
1742 Set<CompositeLocation> inferParamLocSet = new HashSet<CompositeLocation>();
1743 if (paramFlowNode != null) {
1744 for (Iterator iterator = paramFlowNode.iterator(); iterator.hasNext();) {
1745 FlowNode fn = (FlowNode) iterator.next();
1746 CompositeLocation inferLoc =
1747 generateInferredCompositeLocation(methodInfo, getFlowGraph(md).getLocationTuple(fn));
1748 inferParamLocSet.add(inferLoc);
1752 Set<FlowNode> returnNodeSet = fg.getReturnNodeSet();
1754 skip: for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
1755 FlowNode returnNode = (FlowNode) iterator.next();
1756 CompositeLocation inferReturnLoc =
1757 generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode));
1758 if (inferReturnLoc.get(0).getLocIdentifier().equals("this")) {
1759 // if the location type of the return value matches "this" reference
1760 // then, check whether this return value is equal to/lower than all
1762 // parameters that possibly flow into the return values
1763 for (Iterator iterator2 = inferParamLocSet.iterator(); iterator2.hasNext();) {
1764 CompositeLocation paramInferLoc = (CompositeLocation) iterator2.next();
1766 if ((!paramInferLoc.equals(inferReturnLoc))
1767 && !isGreaterThan(methodLattice, paramInferLoc, inferReturnLoc)) {
1771 inferFieldReturnLocSet.add(inferReturnLoc);
1776 if (inferFieldReturnLocSet.size() > 0) {
1778 CompositeLocation returnLoc = getLowest(methodLattice, inferFieldReturnLocSet);
1779 if (returnLoc == null) {
1780 // in this case, assign <'this',bottom> to the RETURNLOC
1781 returnLoc = new CompositeLocation(new Location(md, md.getThis().getSymbol()));
1782 returnLoc.addLocation(new Location(md.getClassDesc(), getLattice(md.getClassDesc())
1785 methodInfo.setReturnLoc(returnLoc);
1788 String returnLocSymbol = "RETURNLOC";
1789 CompositeLocation returnLocInferLoc =
1790 new CompositeLocation(new Location(md, returnLocSymbol));
1791 methodInfo.setReturnLoc(returnLocInferLoc);
1793 for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) {
1794 Integer paramIdx = (Integer) iterator.next();
1795 CompositeLocation inferLoc = mapParamToLoc.get(paramIdx);
1796 String paramLocLocalSymbol = inferLoc.get(0).getLocIdentifier();
1797 if (!methodLattice.isGreaterThan(paramLocLocalSymbol, returnLocSymbol)) {
1798 addRelationHigherToLower(methodLattice, methodInfo, paramLocLocalSymbol,
1803 for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
1804 FlowNode returnNode = (FlowNode) iterator.next();
1805 CompositeLocation inferLoc =
1806 generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode));
1807 if (!isGreaterThan(methodLattice, inferLoc, returnLocInferLoc)) {
1808 addRelation(methodLattice, methodInfo, inferLoc, returnLocInferLoc);
1815 } catch (CyclicFlowException e) {
1816 e.printStackTrace();
1821 private Set<String> getHigherLocSymbolThan(SSJavaLattice<String> lattice, String loc) {
1822 Set<String> higherLocSet = new HashSet<String>();
1824 Set<String> locSet = lattice.getTable().keySet();
1825 for (Iterator iterator = locSet.iterator(); iterator.hasNext();) {
1826 String element = (String) iterator.next();
1827 if (lattice.isGreaterThan(element, loc) && (!element.equals(lattice.getTopItem()))) {
1828 higherLocSet.add(element);
1831 return higherLocSet;
1834 private CompositeLocation getLowest(SSJavaLattice<String> methodLattice,
1835 Set<CompositeLocation> set) {
1837 CompositeLocation lowest = set.iterator().next();
1839 if (set.size() == 1) {
1843 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
1844 CompositeLocation loc = (CompositeLocation) iterator.next();
1846 if ((!loc.equals(lowest)) && (!isComparable(methodLattice, lowest, loc))) {
1847 // if there is a case where composite locations are incomparable, just
1852 if ((!loc.equals(lowest)) && isGreaterThan(methodLattice, lowest, loc)) {
1859 private boolean isComparable(SSJavaLattice<String> methodLattice, CompositeLocation comp1,
1860 CompositeLocation comp2) {
1862 int size = comp1.getSize() >= comp2.getSize() ? comp2.getSize() : comp1.getSize();
1864 for (int idx = 0; idx < size; idx++) {
1865 Location loc1 = comp1.get(idx);
1866 Location loc2 = comp2.get(idx);
1868 Descriptor desc1 = loc1.getDescriptor();
1869 Descriptor desc2 = loc2.getDescriptor();
1871 if (!desc1.equals(desc2)) {
1872 throw new Error("Fail to compare " + comp1 + " and " + comp2);
1875 String symbol1 = loc1.getLocIdentifier();
1876 String symbol2 = loc2.getLocIdentifier();
1878 SSJavaLattice<String> lattice;
1880 lattice = methodLattice;
1882 lattice = getLattice(desc1);
1885 if (symbol1.equals(symbol2)) {
1887 } else if (!lattice.isComparable(symbol1, symbol2)) {
1896 private boolean isGreaterThan(SSJavaLattice<String> methodLattice, CompositeLocation comp1,
1897 CompositeLocation comp2) {
1899 int size = comp1.getSize() >= comp2.getSize() ? comp2.getSize() : comp1.getSize();
1901 for (int idx = 0; idx < size; idx++) {
1902 Location loc1 = comp1.get(idx);
1903 Location loc2 = comp2.get(idx);
1905 Descriptor desc1 = loc1.getDescriptor();
1906 Descriptor desc2 = loc2.getDescriptor();
1908 if (!desc1.equals(desc2)) {
1909 throw new Error("Fail to compare " + comp1 + " and " + comp2);
1912 String symbol1 = loc1.getLocIdentifier();
1913 String symbol2 = loc2.getLocIdentifier();
1915 SSJavaLattice<String> lattice;
1917 lattice = methodLattice;
1919 lattice = getLattice(desc1);
1922 if (symbol1.equals(symbol2)) {
1924 } else if (lattice.isGreaterThan(symbol1, symbol2)) {
1935 private void recursiveAddRelationToLattice(int idx, MethodDescriptor md,
1936 CompositeLocation srcInferLoc, CompositeLocation dstInferLoc) throws CyclicFlowException {
1938 String srcLocSymbol = srcInferLoc.get(idx).getLocIdentifier();
1939 String dstLocSymbol = dstInferLoc.get(idx).getLocIdentifier();
1941 if (srcLocSymbol.equals(dstLocSymbol)) {
1942 recursiveAddRelationToLattice(idx + 1, md, srcInferLoc, dstInferLoc);
1945 Descriptor parentDesc = srcInferLoc.get(idx).getDescriptor();
1946 LocationInfo locInfo = getLocationInfo(parentDesc);
1948 addRelationHigherToLower(getLattice(parentDesc), getLocationInfo(parentDesc), srcLocSymbol,
1954 // private void propagateFlowsFromCallee(MethodInvokeNode min, MethodDescriptor mdCaller,
1955 // MethodDescriptor mdCallee) {
1957 // // the transformation for a call site propagates all relations between
1958 // // parameters from the callee
1959 // // if the method is virtual, it also grab all relations from any possible
1962 // Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
1963 // if (mdCallee.isStatic()) {
1964 // setPossibleCallees.add(mdCallee);
1966 // Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getMethods(mdCallee);
1967 // // removes method descriptors that are not invoked by the caller
1968 // calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller));
1969 // setPossibleCallees.addAll(calleeSet);
1972 // for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
1973 // MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
1974 // propagateFlowsToCaller(min, mdCaller, possibleMdCallee);
1979 private void contributeCalleeFlows(MethodInvokeNode min, MethodDescriptor mdCaller,
1980 MethodDescriptor mdCallee) {
1982 System.out.println("\n##contributeCalleeFlows callee=" + mdCallee + "TO caller=" + mdCaller);
1984 getSubGlobalFlowGraph(mdCallee);
1988 private FlowGraph getSubGlobalFlowGraph(MethodDescriptor md) {
1989 return mapMethodDescriptorToSubGlobalFlowGraph.get(md);
1992 private void propagateFlowsToCallerWithNoCompositeLocation(MethodInvokeNode min,
1993 MethodDescriptor mdCaller, MethodDescriptor mdCallee) {
1995 System.out.println("\n##PROPAGATE callee=" + mdCallee + "TO caller=" + mdCaller);
1997 // if the parameter A reaches to the parameter B
1998 // then, add an edge the argument A -> the argument B to the caller's flow
2001 FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
2002 FlowGraph callerFlowGraph = getFlowGraph(mdCaller);
2003 int numParam = calleeFlowGraph.getNumParameters();
2005 for (int i = 0; i < numParam; i++) {
2006 for (int k = 0; k < numParam; k++) {
2010 FlowNode paramNode1 = calleeFlowGraph.getParamFlowNode(i);
2011 FlowNode paramNode2 = calleeFlowGraph.getParamFlowNode(k);
2013 NodeTupleSet tupleSetArg1 = getNodeTupleSetByArgIdx(min, i);
2014 NodeTupleSet tupleSetArg2 = getNodeTupleSetByArgIdx(min, k);
2016 for (Iterator<NTuple<Descriptor>> iter1 = tupleSetArg1.iterator(); iter1.hasNext();) {
2017 NTuple<Descriptor> arg1Tuple = iter1.next();
2019 for (Iterator<NTuple<Descriptor>> iter2 = tupleSetArg2.iterator(); iter2.hasNext();) {
2020 NTuple<Descriptor> arg2Tuple = iter2.next();
2022 // check if the callee propagates an ordering constraints through
2025 Set<FlowNode> localReachSet =
2026 calleeFlowGraph.getLocalReachFlowNodeSetFrom(paramNode1);
2028 if (localReachSet.contains(paramNode2)) {
2029 // need to propagate an ordering relation s.t. arg1 is higher
2033 .println("-param1=" + paramNode1 + " is higher than param2=" + paramNode2);
2034 System.out.println("-arg1Tuple=" + arg1Tuple + " is higher than arg2Tuple="
2037 // otherwise, flows between method/field locations...
2038 callerFlowGraph.addValueFlowEdge(arg1Tuple, arg2Tuple);
2039 System.out.println("arg1=" + arg1Tuple + " arg2=" + arg2Tuple);
2046 System.out.println();
2050 System.out.println("##\n");
2054 private void propagateFlowsToCaller(MethodInvokeNode min, MethodDescriptor mdCaller,
2055 MethodDescriptor mdCallee) {
2057 System.out.println("\n##PROPAGATE callee=" + mdCallee + "TO caller=" + mdCaller);
2059 // if the parameter A reaches to the parameter B
2060 // then, add an edge the argument A -> the argument B to the caller's flow
2064 // also if a parameter is a composite location and is started with "this" reference,
2065 // need to make sure that the corresponding argument is higher than the translated location of
2068 FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
2069 FlowGraph callerFlowGraph = getFlowGraph(mdCaller);
2070 int numParam = calleeFlowGraph.getNumParameters();
2072 for (int i = 0; i < numParam; i++) {
2073 for (int k = 0; k < numParam; k++) {
2077 FlowNode paramNode1 = calleeFlowGraph.getParamFlowNode(i);
2078 FlowNode paramNode2 = calleeFlowGraph.getParamFlowNode(k);
2080 System.out.println("param1=" + paramNode1 + " curDescTuple="
2081 + paramNode1.getCurrentDescTuple());
2082 System.out.println("param2=" + paramNode2 + " curDescTuple="
2083 + paramNode2.getCurrentDescTuple());
2085 NodeTupleSet tupleSetArg1 = getNodeTupleSetByArgIdx(min, i);
2086 NodeTupleSet tupleSetArg2 = getNodeTupleSetByArgIdx(min, k);
2088 for (Iterator<NTuple<Descriptor>> iter1 = tupleSetArg1.iterator(); iter1.hasNext();) {
2089 NTuple<Descriptor> arg1Tuple = iter1.next();
2091 for (Iterator<NTuple<Descriptor>> iter2 = tupleSetArg2.iterator(); iter2.hasNext();) {
2092 NTuple<Descriptor> arg2Tuple = iter2.next();
2094 // check if the callee propagates an ordering constraints through
2097 Set<FlowNode> localReachSet =
2098 calleeFlowGraph.getLocalReachFlowNodeSetFrom(paramNode1);
2100 if (localReachSet.contains(paramNode2)) {
2101 // need to propagate an ordering relation s.t. arg1 is higher
2105 .println("-param1=" + paramNode1 + " is higher than param2=" + paramNode2);
2106 System.out.println("-arg1Tuple=" + arg1Tuple + " is higher than arg2Tuple="
2109 if (!min.getMethod().isStatic()) {
2110 // check if this is the case that values flow to/from the
2111 // current object reference 'this'
2113 NTuple<Descriptor> baseTuple = mapMethodInvokeNodeToBaseTuple.get(min);
2114 Descriptor baseRef = baseTuple.get(baseTuple.size() - 1);
2116 System.out.println("paramNode1.getCurrentDescTuple()="
2117 + paramNode1.getCurrentDescTuple());
2118 // calculate the prefix of the argument
2120 if (arg2Tuple.size() == 1 && arg2Tuple.get(0).equals(baseRef)) {
2121 // in this case, the callee flow causes a caller flow to the object whose method
2124 if (!paramNode1.getCurrentDescTuple().startsWith(mdCallee.getThis())) {
2125 // check whether ???
2127 NTuple<Descriptor> param1Prefix =
2128 calculatePrefixForParam(callerFlowGraph, calleeFlowGraph, min, arg1Tuple,
2131 if (param1Prefix != null && param1Prefix.startsWith(mdCallee.getThis())) {
2132 // in this case, we need to create a new edge 'this.FIELD'->'this'
2133 // but we couldn't... instead we assign a new composite location started
2134 // with 'this' reference to the corresponding parameter
2136 CompositeLocation compLocForParam1 =
2137 generateCompositeLocation(mdCallee, param1Prefix);
2140 .println("set comp loc=" + compLocForParam1 + " to " + paramNode1);
2141 paramNode1.setCompositeLocation(compLocForParam1);
2143 // then, we need to make sure that the corresponding argument in the caller
2144 // is required to be higher than or equal to the translated parameter
2147 NTuple<Descriptor> translatedParamTuple =
2148 translateCompositeLocationToCaller(min, compLocForParam1);
2150 // TODO : check if the arg >= the tranlated parameter
2152 System.out.println("add a flow edge= " + arg1Tuple + "->"
2153 + translatedParamTuple);
2154 callerFlowGraph.addValueFlowEdge(arg1Tuple, translatedParamTuple);
2161 // param1 has already been assigned a composite location
2163 System.out.println("--param1 has already been assigned a composite location");
2164 CompositeLocation compLocForParam1 = paramNode1.getCompositeLocation();
2165 NTuple<Descriptor> translatedParamTuple =
2166 translateCompositeLocationToCaller(min, compLocForParam1);
2168 // TODO : check if the arg >= the tranlated parameter
2170 System.out.println("add a flow edge= " + arg1Tuple + "->"
2171 + translatedParamTuple);
2172 callerFlowGraph.addValueFlowEdge(arg1Tuple, translatedParamTuple);
2178 } else if (arg1Tuple.size() == 1 && arg1Tuple.get(0).equals(baseRef)) {
2179 // in this case, the callee flow causes a caller flow originated from the object
2181 // method is invoked.
2183 System.out.println("###FROM CASE");
2185 if (!paramNode2.getCurrentDescTuple().startsWith(mdCallee.getThis())) {
2187 NTuple<Descriptor> param2Prefix =
2188 calculatePrefixForParam(callerFlowGraph, calleeFlowGraph, min, arg2Tuple,
2191 if (param2Prefix != null && param2Prefix.startsWith(mdCallee.getThis())) {
2192 // in this case, we need to create a new edge 'this' ->
2193 // 'this.FIELD' but we couldn't... instead we assign the corresponding
2194 // parameter a new composite location started with 'this' reference
2196 CompositeLocation compLocForParam2 =
2197 generateCompositeLocation(mdCallee, param2Prefix);
2199 // System.out.println("set comp loc=" + compLocForParam2
2201 // " to " + paramNode2);
2202 paramNode1.setCompositeLocation(compLocForParam2);
2210 // otherwise, flows between method/field locations...
2211 callerFlowGraph.addValueFlowEdge(arg1Tuple, arg2Tuple);
2212 System.out.println("arg1=" + arg1Tuple + " arg2=" + arg2Tuple);
2219 System.out.println();
2223 System.out.println("##\n");
2226 private NTuple<Descriptor> translateCompositeLocationToCaller(MethodInvokeNode min,
2227 CompositeLocation compLocForParam1) {
2228 NTuple<Descriptor> baseTuple = mapMethodInvokeNodeToBaseTuple.get(min);
2230 NTuple<Descriptor> tuple = new NTuple<Descriptor>();
2232 for (int i = 0; i < baseTuple.size(); i++) {
2233 tuple.add(baseTuple.get(i));
2236 for (int i = 1; i < compLocForParam1.getSize(); i++) {
2237 Location loc = compLocForParam1.get(i);
2238 tuple.add(loc.getLocDescriptor());
2244 private CompositeLocation generateCompositeLocation(MethodDescriptor md,
2245 NTuple<Descriptor> paramPrefix) {
2247 System.out.println("generateCompositeLocation=" + paramPrefix);
2249 CompositeLocation newCompLoc = convertToCompositeLocation(md, paramPrefix);
2251 Descriptor lastDescOfPrefix = paramPrefix.get(paramPrefix.size() - 1);
2252 // System.out.println("lastDescOfPrefix=" + lastDescOfPrefix + " kind="
2253 // + lastDescOfPrefix.getClass());
2254 ClassDescriptor enclosingDescriptor;
2255 if (lastDescOfPrefix instanceof FieldDescriptor) {
2256 enclosingDescriptor = ((FieldDescriptor) lastDescOfPrefix).getType().getClassDesc();
2257 // System.out.println("enclosingDescriptor0=" + enclosingDescriptor);
2259 // var descriptor case
2260 enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc();
2262 // System.out.println("enclosingDescriptor=" + enclosingDescriptor);
2264 LocationDescriptor newLocDescriptor = generateNewLocationDescriptor();
2265 newLocDescriptor.setEnclosingClassDesc(enclosingDescriptor);
2267 Location newLoc = new Location(enclosingDescriptor, newLocDescriptor.getSymbol());
2268 newLoc.setLocDescriptor(newLocDescriptor);
2269 newCompLoc.addLocation(newLoc);
2271 // System.out.println("--newCompLoc=" + newCompLoc);
2275 private NTuple<Descriptor> calculatePrefixForParam(FlowGraph callerFlowGraph,
2276 FlowGraph calleeFlowGraph, MethodInvokeNode min, NTuple<Descriptor> arg1Tuple,
2277 FlowNode paramNode1) {
2279 NTuple<Descriptor> baseTuple = mapMethodInvokeNodeToBaseTuple.get(min);
2280 Descriptor baseRef = baseTuple.get(baseTuple.size() - 1);
2281 System.out.println("baseRef=" + baseRef);
2283 FlowNode flowNodeArg1 = callerFlowGraph.getFlowNode(arg1Tuple);
2284 List<NTuple<Descriptor>> callerPrefixList = calculatePrefixList(callerFlowGraph, flowNodeArg1);
2285 System.out.println("callerPrefixList=" + callerPrefixList);
2287 List<NTuple<Descriptor>> prefixList = calculatePrefixList(calleeFlowGraph, paramNode1);
2288 System.out.println("###prefixList from node=" + paramNode1 + " =" + prefixList);
2290 List<NTuple<Descriptor>> calleePrefixList =
2291 translatePrefixListToCallee(baseRef, min.getMethod(), callerPrefixList);
2293 System.out.println("calleePrefixList=" + calleePrefixList);
2295 Set<FlowNode> reachNodeSetFromParam1 = calleeFlowGraph.getReachFlowNodeSetFrom(paramNode1);
2296 System.out.println("reachNodeSetFromParam1=" + reachNodeSetFromParam1);
2298 for (int i = 0; i < calleePrefixList.size(); i++) {
2299 NTuple<Descriptor> curPrefix = calleePrefixList.get(i);
2300 Set<NTuple<Descriptor>> reachableCommonPrefixSet = new HashSet<NTuple<Descriptor>>();
2302 for (Iterator iterator2 = reachNodeSetFromParam1.iterator(); iterator2.hasNext();) {
2303 FlowNode reachNode = (FlowNode) iterator2.next();
2304 if (reachNode.getCurrentDescTuple().startsWith(curPrefix)) {
2305 reachableCommonPrefixSet.add(reachNode.getCurrentDescTuple());
2309 if (!reachableCommonPrefixSet.isEmpty()) {
2310 System.out.println("###REACHABLECOMONPREFIX=" + reachableCommonPrefixSet
2311 + " with curPreFix=" + curPrefix);
2320 private List<NTuple<Descriptor>> translatePrefixListToCallee(Descriptor baseRef,
2321 MethodDescriptor mdCallee, List<NTuple<Descriptor>> callerPrefixList) {
2323 List<NTuple<Descriptor>> calleePrefixList = new ArrayList<NTuple<Descriptor>>();
2325 for (int i = 0; i < callerPrefixList.size(); i++) {
2326 NTuple<Descriptor> prefix = callerPrefixList.get(i);
2327 if (prefix.startsWith(baseRef)) {
2328 NTuple<Descriptor> calleePrefix = new NTuple<Descriptor>();
2329 calleePrefix.add(mdCallee.getThis());
2330 for (int k = 1; k < prefix.size(); k++) {
2331 calleePrefix.add(prefix.get(k));
2333 calleePrefixList.add(calleePrefix);
2337 return calleePrefixList;
2341 private List<NTuple<Descriptor>> calculatePrefixList(FlowGraph flowGraph, FlowNode flowNode) {
2343 System.out.println("\n##### calculatePrefixList=" + flowNode);
2345 Set<FlowNode> inNodeSet = flowGraph.getIncomingFlowNodeSet(flowNode);
2346 inNodeSet.add(flowNode);
2348 System.out.println("inNodeSet=" + inNodeSet);
2350 List<NTuple<Descriptor>> prefixList = new ArrayList<NTuple<Descriptor>>();
2352 for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
2353 FlowNode inNode = (FlowNode) iterator.next();
2355 NTuple<Descriptor> inNodeTuple = inNode.getCurrentDescTuple();
2357 // CompositeLocation inNodeInferredLoc =
2358 // generateInferredCompositeLocation(methodInfo, inNodeTuple);
2359 // NTuple<Location> inNodeInferredLocTuple = inNodeInferredLoc.getTuple();
2361 for (int i = 1; i < inNodeTuple.size(); i++) {
2362 NTuple<Descriptor> prefix = inNodeTuple.subList(0, i);
2363 if (!prefixList.contains(prefix)) {
2364 prefixList.add(prefix);
2369 Collections.sort(prefixList, new Comparator<NTuple<Descriptor>>() {
2370 public int compare(NTuple<Descriptor> arg0, NTuple<Descriptor> arg1) {
2371 int s0 = arg0.size();
2372 int s1 = arg1.size();
2375 } else if (s0 == s1) {
2387 public CompositeLocation convertToCompositeLocation(MethodDescriptor md, NTuple<Descriptor> tuple) {
2389 CompositeLocation compLoc = new CompositeLocation();
2391 Descriptor enclosingDescriptor = md;
2393 for (int i = 0; i < tuple.size(); i++) {
2394 Descriptor curDescriptor = tuple.get(i);
2395 Location locElement = new Location(enclosingDescriptor, curDescriptor.getSymbol());
2396 locElement.setLocDescriptor(curDescriptor);
2397 compLoc.addLocation(locElement);
2399 if (curDescriptor instanceof VarDescriptor) {
2400 enclosingDescriptor = md.getClassDesc();
2401 } else if (curDescriptor instanceof NameDescriptor) {
2402 // it is "GLOBAL LOC" case!
2403 enclosingDescriptor = GLOBALDESC;
2405 enclosingDescriptor = ((FieldDescriptor) curDescriptor).getClassDescriptor();
2410 System.out.println("-convertToCompositeLocation from=" + tuple + " to " + compLoc);
2415 private LocationDescriptor generateNewLocationDescriptor() {
2416 return new LocationDescriptor("Loc" + (locSeed++));
2419 private int getPrefixIndex(NTuple<Descriptor> tuple1, NTuple<Descriptor> tuple2) {
2421 // return the index where the prefix shared by tuple1 and tuple2 is ended
2422 // if there is no prefix shared by both of them, return -1
2424 int minSize = tuple1.size();
2425 if (minSize > tuple2.size()) {
2426 minSize = tuple2.size();
2430 for (int i = 0; i < minSize; i++) {
2431 if (!tuple1.get(i).equals(tuple2.get(i))) {
2441 private void analyzeLatticeMethodInvocationNode(MethodDescriptor mdCaller,
2442 SSJavaLattice<String> methodLattice, MethodLocationInfo methodInfo)
2443 throws CyclicFlowException {
2445 // the transformation for a call site propagates all relations between
2446 // parameters from the callee
2447 // if the method is virtual, it also grab all relations from any possible
2450 Set<MethodInvokeNode> setMethodInvokeNode =
2451 mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller);
2453 if (setMethodInvokeNode != null) {
2455 for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) {
2456 MethodInvokeNode min = (MethodInvokeNode) iterator.next();
2457 MethodDescriptor mdCallee = min.getMethod();
2458 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
2459 if (mdCallee.isStatic()) {
2460 setPossibleCallees.add(mdCallee);
2462 Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getMethods(mdCallee);
2463 // removes method descriptors that are not invoked by the caller
2464 calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller));
2465 setPossibleCallees.addAll(calleeSet);
2468 for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
2469 MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
2470 propagateRelationToCaller(min, mdCaller, possibleMdCallee, methodLattice, methodInfo);
2478 private void propagateRelationToCaller(MethodInvokeNode min, MethodDescriptor mdCaller,
2479 MethodDescriptor possibleMdCallee, SSJavaLattice<String> methodLattice,
2480 MethodLocationInfo methodInfo) throws CyclicFlowException {
2482 SSJavaLattice<String> calleeLattice = getMethodLattice(possibleMdCallee);
2483 MethodLocationInfo calleeLocInfo = getMethodLocationInfo(possibleMdCallee);
2484 FlowGraph calleeFlowGraph = getFlowGraph(possibleMdCallee);
2486 int numParam = calleeLocInfo.getNumParam();
2487 for (int i = 0; i < numParam; i++) {
2488 CompositeLocation param1 = calleeLocInfo.getParamCompositeLocation(i);
2489 for (int k = 0; k < numParam; k++) {
2491 CompositeLocation param2 = calleeLocInfo.getParamCompositeLocation(k);
2493 if (isGreaterThan(getLattice(possibleMdCallee), param1, param2)) {
2494 NodeTupleSet argDescTupleSet1 = getNodeTupleSetByArgIdx(min, i);
2495 NodeTupleSet argDescTupleSet2 = getNodeTupleSetByArgIdx(min, k);
2497 // the callee has the relation in which param1 is higher than param2
2498 // therefore, the caller has to have the relation in which arg1 is
2501 for (Iterator<NTuple<Descriptor>> iterator = argDescTupleSet1.iterator(); iterator
2503 NTuple<Descriptor> argDescTuple1 = iterator.next();
2505 for (Iterator<NTuple<Descriptor>> iterator2 = argDescTupleSet2.iterator(); iterator2
2507 NTuple<Descriptor> argDescTuple2 = iterator2.next();
2509 // retreive inferred location by the local var descriptor
2511 NTuple<Location> tuple1 = getFlowGraph(mdCaller).getLocationTuple(argDescTuple1);
2512 NTuple<Location> tuple2 = getFlowGraph(mdCaller).getLocationTuple(argDescTuple2);
2514 // CompositeLocation higherInferLoc =
2515 // methodInfo.getInferLocation(argTuple1.get(0));
2516 // CompositeLocation lowerInferLoc =
2517 // methodInfo.getInferLocation(argTuple2.get(0));
2519 CompositeLocation inferLoc1 = generateInferredCompositeLocation(methodInfo, tuple1);
2520 CompositeLocation inferLoc2 = generateInferredCompositeLocation(methodInfo, tuple2);
2522 // addRelation(methodLattice, methodInfo, inferLoc1, inferLoc2);
2524 addFlowGraphEdge(mdCaller, argDescTuple1, argDescTuple2);
2537 private CompositeLocation generateInferredCompositeLocation(MethodLocationInfo methodInfo,
2538 NTuple<Location> tuple) {
2540 // first, retrieve inferred location by the local var descriptor
2541 CompositeLocation inferLoc = new CompositeLocation();
2543 CompositeLocation localVarInferLoc =
2544 methodInfo.getInferLocation(tuple.get(0).getLocDescriptor());
2546 localVarInferLoc.get(0).setLocDescriptor(tuple.get(0).getLocDescriptor());
2548 for (int i = 0; i < localVarInferLoc.getSize(); i++) {
2549 inferLoc.addLocation(localVarInferLoc.get(i));
2552 for (int i = 1; i < tuple.size(); i++) {
2553 Location cur = tuple.get(i);
2554 Descriptor enclosingDesc = cur.getDescriptor();
2555 Descriptor curDesc = cur.getLocDescriptor();
2557 Location inferLocElement;
2558 if (curDesc == null) {
2559 // in this case, we have a newly generated location.
2560 inferLocElement = new Location(enclosingDesc, cur.getLocIdentifier());
2562 String fieldLocSymbol =
2563 getLocationInfo(enclosingDesc).getInferLocation(curDesc).get(0).getLocIdentifier();
2564 inferLocElement = new Location(enclosingDesc, fieldLocSymbol);
2565 inferLocElement.setLocDescriptor(curDesc);
2568 inferLoc.addLocation(inferLocElement);
2572 assert (inferLoc.get(0).getLocDescriptor().getSymbol() == inferLoc.get(0).getLocIdentifier());
2576 private void addRelation(SSJavaLattice<String> methodLattice, MethodLocationInfo methodInfo,
2577 CompositeLocation srcInferLoc, CompositeLocation dstInferLoc) throws CyclicFlowException {
2579 System.out.println("addRelation --- srcInferLoc=" + srcInferLoc + " dstInferLoc="
2581 String srcLocalLocSymbol = srcInferLoc.get(0).getLocIdentifier();
2582 String dstLocalLocSymbol = dstInferLoc.get(0).getLocIdentifier();
2584 if (srcInferLoc.getSize() == 1 && dstInferLoc.getSize() == 1) {
2585 // add a new relation to the local lattice
2586 addRelationHigherToLower(methodLattice, methodInfo, srcLocalLocSymbol, dstLocalLocSymbol);
2587 } else if (srcInferLoc.getSize() > 1 && dstInferLoc.getSize() > 1) {
2588 // both src and dst have assigned to a composite location
2590 if (!srcLocalLocSymbol.equals(dstLocalLocSymbol)) {
2591 addRelationHigherToLower(methodLattice, methodInfo, srcLocalLocSymbol, dstLocalLocSymbol);
2593 recursivelyAddRelation(1, srcInferLoc, dstInferLoc);
2596 // either src or dst has assigned to a composite location
2597 if (!srcLocalLocSymbol.equals(dstLocalLocSymbol)) {
2598 addRelationHigherToLower(methodLattice, methodInfo, srcLocalLocSymbol, dstLocalLocSymbol);
2602 System.out.println();
2606 public LocationInfo getLocationInfo(Descriptor d) {
2607 if (d instanceof MethodDescriptor) {
2608 return getMethodLocationInfo((MethodDescriptor) d);
2610 return getFieldLocationInfo((ClassDescriptor) d);
2614 private MethodLocationInfo getMethodLocationInfo(MethodDescriptor md) {
2616 if (!mapMethodDescToMethodLocationInfo.containsKey(md)) {
2617 mapMethodDescToMethodLocationInfo.put(md, new MethodLocationInfo(md));
2620 return mapMethodDescToMethodLocationInfo.get(md);
2624 private LocationInfo getFieldLocationInfo(ClassDescriptor cd) {
2626 if (!mapClassToLocationInfo.containsKey(cd)) {
2627 mapClassToLocationInfo.put(cd, new LocationInfo(cd));
2630 return mapClassToLocationInfo.get(cd);
2634 private void addRelationToLattice(MethodDescriptor md, SSJavaLattice<String> methodLattice,
2635 MethodLocationInfo methodInfo, FlowNode srcNode, FlowNode dstNode) throws CyclicFlowException {
2637 System.out.println();
2638 System.out.println("### addRelationToLattice src=" + srcNode + " dst=" + dstNode);
2640 // add a new binary relation of dstNode < srcNode
2641 FlowGraph flowGraph = getFlowGraph(md);
2643 System.out.println("***** src composite case::");
2644 calculateCompositeLocation(flowGraph, methodLattice, methodInfo, srcNode, null);
2646 CompositeLocation srcInferLoc =
2647 generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(srcNode));
2648 CompositeLocation dstInferLoc =
2649 generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(dstNode));
2650 addRelation(methodLattice, methodInfo, srcInferLoc, dstInferLoc);
2651 } catch (CyclicFlowException e) {
2652 // there is a cyclic value flow... try to calculate a composite location
2653 // for the destination node
2654 System.out.println("***** dst composite case::");
2655 calculateCompositeLocation(flowGraph, methodLattice, methodInfo, dstNode, srcNode);
2656 CompositeLocation srcInferLoc =
2657 generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(srcNode));
2658 CompositeLocation dstInferLoc =
2659 generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(dstNode));
2661 addRelation(methodLattice, methodInfo, srcInferLoc, dstInferLoc);
2662 } catch (CyclicFlowException e1) {
2663 throw new Error("Failed to merge cyclic value flows into a shared location.");
2669 private void recursivelyAddRelation(int idx, CompositeLocation srcInferLoc,
2670 CompositeLocation dstInferLoc) throws CyclicFlowException {
2672 String srcLocSymbol = srcInferLoc.get(idx).getLocIdentifier();
2673 String dstLocSymbol = dstInferLoc.get(idx).getLocIdentifier();
2675 Descriptor parentDesc = srcInferLoc.get(idx).getDescriptor();
2677 if (srcLocSymbol.equals(dstLocSymbol)) {
2678 // check if it is the case of shared location
2679 if (srcInferLoc.getSize() == (idx + 1) && dstInferLoc.getSize() == (idx + 1)) {
2680 Location inferLocElement = srcInferLoc.get(idx);
2681 System.out.println("SET SHARED LOCATION=" + inferLocElement);
2682 getLattice(inferLocElement.getDescriptor())
2683 .addSharedLoc(inferLocElement.getLocIdentifier());
2684 } else if (srcInferLoc.getSize() > (idx + 1) && dstInferLoc.getSize() > (idx + 1)) {
2685 recursivelyAddRelation(idx + 1, srcInferLoc, dstInferLoc);
2688 addRelationHigherToLower(getLattice(parentDesc), getLocationInfo(parentDesc), srcLocSymbol,
2693 private void recursivelyAddCompositeRelation(MethodDescriptor md, FlowGraph flowGraph,
2694 MethodLocationInfo methodInfo, FlowNode srcNode, FlowNode dstNode, Descriptor srcDesc,
2695 Descriptor dstDesc) throws CyclicFlowException {
2697 CompositeLocation inferSrcLoc;
2698 CompositeLocation inferDstLoc = methodInfo.getInferLocation(dstDesc);
2700 if (srcNode.getDescTuple().size() > 1) {
2702 inferSrcLoc = new CompositeLocation();
2704 NTuple<Location> locTuple = flowGraph.getLocationTuple(srcNode);
2705 for (int i = 0; i < locTuple.size(); i++) {
2706 inferSrcLoc.addLocation(locTuple.get(i));
2710 inferSrcLoc = methodInfo.getInferLocation(srcDesc);
2713 if (dstNode.getDescTuple().size() > 1) {
2715 inferDstLoc = new CompositeLocation();
2717 NTuple<Location> locTuple = flowGraph.getLocationTuple(dstNode);
2718 for (int i = 0; i < locTuple.size(); i++) {
2719 inferDstLoc.addLocation(locTuple.get(i));
2723 inferDstLoc = methodInfo.getInferLocation(dstDesc);
2726 recursiveAddRelationToLattice(1, md, inferSrcLoc, inferDstLoc);
2729 private void addPrefixMapping(Map<NTuple<Location>, Set<NTuple<Location>>> map,
2730 NTuple<Location> prefix, NTuple<Location> element) {
2732 if (!map.containsKey(prefix)) {
2733 map.put(prefix, new HashSet<NTuple<Location>>());
2735 map.get(prefix).add(element);
2738 private boolean calculateCompositeLocation(FlowGraph flowGraph,
2739 SSJavaLattice<String> methodLattice, MethodLocationInfo methodInfo, FlowNode flowNode,
2740 FlowNode srcNode) throws CyclicFlowException {
2742 Descriptor localVarDesc = flowNode.getDescTuple().get(0);
2743 NTuple<Location> flowNodelocTuple = flowGraph.getLocationTuple(flowNode);
2745 if (localVarDesc.equals(methodInfo.getMethodDesc())) {
2749 Set<FlowNode> inNodeSet = flowGraph.getIncomingFlowNodeSet(flowNode);
2750 Set<FlowNode> reachableNodeSet = flowGraph.getReachFlowNodeSetFrom(flowNode);
2752 Map<NTuple<Location>, Set<NTuple<Location>>> mapPrefixToIncomingLocTupleSet =
2753 new HashMap<NTuple<Location>, Set<NTuple<Location>>>();
2755 List<NTuple<Location>> prefixList = new ArrayList<NTuple<Location>>();
2757 for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
2758 FlowNode inNode = (FlowNode) iterator.next();
2759 NTuple<Location> inNodeTuple = flowGraph.getLocationTuple(inNode);
2761 CompositeLocation inNodeInferredLoc =
2762 generateInferredCompositeLocation(methodInfo, inNodeTuple);
2764 NTuple<Location> inNodeInferredLocTuple = inNodeInferredLoc.getTuple();
2766 for (int i = 1; i < inNodeInferredLocTuple.size(); i++) {
2767 NTuple<Location> prefix = inNodeInferredLocTuple.subList(0, i);
2768 if (!prefixList.contains(prefix)) {
2769 prefixList.add(prefix);
2771 addPrefixMapping(mapPrefixToIncomingLocTupleSet, prefix, inNodeInferredLocTuple);
2775 Collections.sort(prefixList, new Comparator<NTuple<Location>>() {
2776 public int compare(NTuple<Location> arg0, NTuple<Location> arg1) {
2777 int s0 = arg0.size();
2778 int s1 = arg1.size();
2781 } else if (s0 == s1) {
2789 // System.out.println("prefixList=" + prefixList);
2790 // System.out.println("reachableNodeSet=" + reachableNodeSet);
2792 // find out reachable nodes that have the longest common prefix
2793 for (int i = 0; i < prefixList.size(); i++) {
2794 NTuple<Location> curPrefix = prefixList.get(i);
2795 Set<NTuple<Location>> reachableCommonPrefixSet = new HashSet<NTuple<Location>>();
2797 for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
2798 FlowNode reachableNode = (FlowNode) iterator2.next();
2799 NTuple<Location> reachLocTuple = flowGraph.getLocationTuple(reachableNode);
2800 CompositeLocation reachLocInferLoc =
2801 generateInferredCompositeLocation(methodInfo, reachLocTuple);
2802 if (reachLocInferLoc.getTuple().startsWith(curPrefix)) {
2803 reachableCommonPrefixSet.add(reachLocTuple);
2807 if (!reachableCommonPrefixSet.isEmpty()) {
2808 // found reachable nodes that start with the prefix curPrefix
2809 // need to assign a composite location
2811 // first, check if there are more than one the set of locations that has
2812 // the same length of the longest reachable prefix, no way to assign
2813 // a composite location to the input local var
2814 prefixSanityCheck(prefixList, i, flowGraph, reachableNodeSet);
2816 Set<NTuple<Location>> incomingCommonPrefixSet =
2817 mapPrefixToIncomingLocTupleSet.get(curPrefix);
2819 int idx = curPrefix.size();
2820 NTuple<Location> element = incomingCommonPrefixSet.iterator().next();
2821 Descriptor desc = element.get(idx).getDescriptor();
2823 SSJavaLattice<String> lattice = getLattice(desc);
2824 LocationInfo locInfo = getLocationInfo(desc);
2826 CompositeLocation inferLocation =
2827 generateInferredCompositeLocation(methodInfo, flowNodelocTuple);
2829 // methodInfo.getInferLocation(localVarDesc);
2830 CompositeLocation newInferLocation = new CompositeLocation();
2832 if (inferLocation.getTuple().startsWith(curPrefix)) {
2833 // the same infer location is already existed. no need to do
2835 System.out.println("NO ATTEMPT TO MAKE A COMPOSITE LOCATION curPrefix=" + curPrefix);
2837 // TODO: refactoring!
2838 if (srcNode != null) {
2839 CompositeLocation newLoc = new CompositeLocation();
2840 String newLocSymbol = "Loc" + (SSJavaLattice.seed++);
2841 for (int locIdx = 0; locIdx < curPrefix.size(); locIdx++) {
2842 newLoc.addLocation(curPrefix.get(locIdx));
2844 Location newLocationElement = new Location(desc, newLocSymbol);
2845 newLoc.addLocation(newLocationElement);
2847 Descriptor srcLocalVar = srcNode.getDescTuple().get(0);
2848 methodInfo.mapDescriptorToLocation(srcLocalVar, newLoc.clone());
2849 addMapLocSymbolToInferredLocation(methodInfo.getMethodDesc(), srcLocalVar, newLoc);
2850 methodInfo.removeMaplocalVarToLocSet(srcLocalVar);
2852 // add the field/var descriptor to the set of the location symbol
2853 int lastIdx = srcNode.getDescTuple().size() - 1;
2854 Descriptor lastFlowNodeDesc = srcNode.getDescTuple().get(lastIdx);
2855 NTuple<Location> srcNodelocTuple = flowGraph.getLocationTuple(srcNode);
2856 Descriptor enclosinglastLastFlowNodeDesc = srcNodelocTuple.get(lastIdx).getDescriptor();
2858 CompositeLocation newlyInferredLocForFlowNode =
2859 generateInferredCompositeLocation(methodInfo, srcNodelocTuple);
2860 Location lastInferLocElement =
2861 newlyInferredLocForFlowNode.get(newlyInferredLocForFlowNode.getSize() - 1);
2862 Descriptor enclosingLastInferLocElement = lastInferLocElement.getDescriptor();
2864 // getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToDescSet(
2865 // lastInferLocElement.getLocIdentifier(), lastFlowNodeDesc);
2866 getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToRelatedInferLoc(
2867 lastInferLocElement.getLocIdentifier(), enclosinglastLastFlowNodeDesc,
2870 System.out.println("@@@@@@@ ASSIGN " + newLoc + " to SRC=" + srcNode);
2875 // assign a new composite location
2877 // String oldMethodLocationSymbol =
2878 // inferLocation.get(0).getLocIdentifier();
2879 String newLocSymbol = "Loc" + (SSJavaLattice.seed++);
2880 for (int locIdx = 0; locIdx < curPrefix.size(); locIdx++) {
2881 newInferLocation.addLocation(curPrefix.get(locIdx));
2883 Location newLocationElement = new Location(desc, newLocSymbol);
2884 newInferLocation.addLocation(newLocationElement);
2886 // maps local variable to location types of the common prefix
2887 methodInfo.mapDescriptorToLocation(localVarDesc, newInferLocation.clone());
2889 // methodInfo.mapDescriptorToLocation(localVarDesc, newInferLocation);
2890 addMapLocSymbolToInferredLocation(methodInfo.getMethodDesc(), localVarDesc,
2892 methodInfo.removeMaplocalVarToLocSet(localVarDesc);
2894 // add the field/var descriptor to the set of the location symbol
2895 int lastIdx = flowNode.getDescTuple().size() - 1;
2896 Descriptor lastFlowNodeDesc = flowNode.getDescTuple().get(lastIdx);
2897 Descriptor enclosinglastLastFlowNodeDesc = flowNodelocTuple.get(lastIdx).getDescriptor();
2899 CompositeLocation newlyInferredLocForFlowNode =
2900 generateInferredCompositeLocation(methodInfo, flowNodelocTuple);
2901 Location lastInferLocElement =
2902 newlyInferredLocForFlowNode.get(newlyInferredLocForFlowNode.getSize() - 1);
2903 Descriptor enclosingLastInferLocElement = lastInferLocElement.getDescriptor();
2905 // getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToDescSet(
2906 // lastInferLocElement.getLocIdentifier(), lastFlowNodeDesc);
2907 getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToRelatedInferLoc(
2908 lastInferLocElement.getLocIdentifier(), enclosinglastLastFlowNodeDesc,
2911 // clean up the previous location
2912 // Location prevInferLocElement =
2913 // inferLocation.get(inferLocation.getSize() - 1);
2914 // Descriptor prevEnclosingDesc = prevInferLocElement.getDescriptor();
2916 // SSJavaLattice<String> targetLattice;
2917 // LocationInfo targetInfo;
2918 // if (prevEnclosingDesc.equals(methodInfo.getMethodDesc())) {
2919 // targetLattice = methodLattice;
2920 // targetInfo = methodInfo;
2922 // targetLattice = getLattice(prevInferLocElement.getDescriptor());
2923 // targetInfo = getLocationInfo(prevInferLocElement.getDescriptor());
2926 // Set<Pair<Descriptor, Descriptor>> associstedDescSet =
2927 // targetInfo.getRelatedInferLocSet(prevInferLocElement.getLocIdentifier());
2929 // if (associstedDescSet.size() == 1) {
2930 // targetLattice.remove(prevInferLocElement.getLocIdentifier());
2932 // associstedDescSet.remove(lastFlowNodeDesc);
2937 System.out.println("curPrefix=" + curPrefix);
2938 System.out.println("ASSIGN NEW COMPOSITE LOCATION =" + newInferLocation + " to "
2941 String newlyInsertedLocName =
2942 newInferLocation.get(newInferLocation.getSize() - 1).getLocIdentifier();
2944 System.out.println("-- add in-flow");
2945 for (Iterator iterator = incomingCommonPrefixSet.iterator(); iterator.hasNext();) {
2946 NTuple<Location> tuple = (NTuple<Location>) iterator.next();
2947 Location loc = tuple.get(idx);
2948 String higher = loc.getLocIdentifier();
2949 addRelationHigherToLower(lattice, locInfo, higher, newlyInsertedLocName);
2952 System.out.println("-- add out flow");
2953 for (Iterator iterator = reachableCommonPrefixSet.iterator(); iterator.hasNext();) {
2954 NTuple<Location> tuple = (NTuple<Location>) iterator.next();
2955 if (tuple.size() > idx) {
2956 Location loc = tuple.get(idx);
2957 String lower = loc.getLocIdentifier();
2959 // locInfo.getFieldInferLocation(loc.getLocDescriptor()).getLocIdentifier();
2960 addRelationHigherToLower(lattice, locInfo, newlyInsertedLocName, lower);
2973 private void addMapLocSymbolToInferredLocation(MethodDescriptor md, Descriptor localVar,
2974 CompositeLocation inferLoc) {
2976 Location locElement = inferLoc.get((inferLoc.getSize() - 1));
2977 Descriptor enclosingDesc = locElement.getDescriptor();
2978 LocationInfo locInfo = getLocationInfo(enclosingDesc);
2979 locInfo.addMapLocSymbolToRelatedInferLoc(locElement.getLocIdentifier(), md, localVar);
2982 private boolean isCompositeLocation(CompositeLocation cl) {
2983 return cl.getSize() > 1;
2986 private boolean containsNonPrimitiveElement(Set<Descriptor> descSet) {
2987 for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
2988 Descriptor desc = (Descriptor) iterator.next();
2990 if (desc.equals(LocationInference.GLOBALDESC)) {
2992 } else if (desc instanceof VarDescriptor) {
2993 if (!((VarDescriptor) desc).getType().isPrimitive()) {
2996 } else if (desc instanceof FieldDescriptor) {
2997 if (!((FieldDescriptor) desc).getType().isPrimitive()) {
3006 private void addRelationHigherToLower(SSJavaLattice<String> lattice, LocationInfo locInfo,
3007 String higher, String lower) throws CyclicFlowException {
3009 System.out.println("---addRelationHigherToLower " + higher + " -> " + lower
3010 + " to the lattice of " + locInfo.getDescIdentifier());
3011 // if (higher.equals(lower) && lattice.isSharedLoc(higher)) {
3014 Set<String> cycleElementSet = lattice.getPossibleCycleElements(higher, lower);
3016 boolean hasNonPrimitiveElement = false;
3017 for (Iterator iterator = cycleElementSet.iterator(); iterator.hasNext();) {
3018 String cycleElementLocSymbol = (String) iterator.next();
3020 Set<Descriptor> descSet = locInfo.getDescSet(cycleElementLocSymbol);
3021 if (containsNonPrimitiveElement(descSet)) {
3022 hasNonPrimitiveElement = true;
3027 if (hasNonPrimitiveElement) {
3028 System.out.println("#Check cycle= " + lower + " < " + higher + " cycleElementSet="
3030 // if there is non-primitive element in the cycle, no way to merge cyclic
3031 // elements into the shared location
3032 throw new CyclicFlowException();
3035 if (cycleElementSet.size() > 0) {
3037 String newSharedLoc = "SharedLoc" + (SSJavaLattice.seed++);
3039 System.out.println("---ASSIGN NEW SHARED LOC=" + newSharedLoc + " to " + cycleElementSet);
3040 lattice.mergeIntoNewLocation(cycleElementSet, newSharedLoc);
3041 lattice.addSharedLoc(newSharedLoc);
3043 for (Iterator iterator = cycleElementSet.iterator(); iterator.hasNext();) {
3044 String oldLocSymbol = (String) iterator.next();
3046 Set<Pair<Descriptor, Descriptor>> inferLocSet = locInfo.getRelatedInferLocSet(oldLocSymbol);
3047 System.out.println("---update related locations=" + inferLocSet);
3048 for (Iterator iterator2 = inferLocSet.iterator(); iterator2.hasNext();) {
3049 Pair<Descriptor, Descriptor> pair = (Pair<Descriptor, Descriptor>) iterator2.next();
3050 Descriptor enclosingDesc = pair.getFirst();
3051 Descriptor desc = pair.getSecond();
3053 CompositeLocation inferLoc;
3054 if (curMethodInfo.md.equals(enclosingDesc)) {
3055 inferLoc = curMethodInfo.getInferLocation(desc);
3057 inferLoc = getLocationInfo(enclosingDesc).getInferLocation(desc);
3060 Location locElement = inferLoc.get(inferLoc.getSize() - 1);
3062 locElement.setLocIdentifier(newSharedLoc);
3063 locInfo.addMapLocSymbolToRelatedInferLoc(newSharedLoc, enclosingDesc, desc);
3065 if (curMethodInfo.md.equals(enclosingDesc)) {
3066 inferLoc = curMethodInfo.getInferLocation(desc);
3068 inferLoc = getLocationInfo(enclosingDesc).getInferLocation(desc);
3070 System.out.println("---New Infer Loc=" + inferLoc);
3073 locInfo.removeRelatedInferLocSet(oldLocSymbol, newSharedLoc);
3077 lattice.addSharedLoc(newSharedLoc);
3079 } else if (!lattice.isGreaterThan(higher, lower)) {
3080 lattice.addRelationHigherToLower(higher, lower);
3084 private void replaceOldLocWithNewLoc(SSJavaLattice<String> methodLattice, String oldLocSymbol,
3085 String newLocSymbol) {
3087 if (methodLattice.containsKey(oldLocSymbol)) {
3088 methodLattice.substituteLocation(oldLocSymbol, newLocSymbol);
3093 private void prefixSanityCheck(List<NTuple<Location>> prefixList, int curIdx,
3094 FlowGraph flowGraph, Set<FlowNode> reachableNodeSet) {
3096 NTuple<Location> curPrefix = prefixList.get(curIdx);
3098 for (int i = curIdx + 1; i < prefixList.size(); i++) {
3099 NTuple<Location> prefixTuple = prefixList.get(i);
3101 if (curPrefix.startsWith(prefixTuple)) {
3105 for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
3106 FlowNode reachableNode = (FlowNode) iterator2.next();
3107 NTuple<Location> reachLocTuple = flowGraph.getLocationTuple(reachableNode);
3108 if (reachLocTuple.startsWith(prefixTuple)) {
3110 throw new Error("Failed to generate a composite location");
3116 public boolean isPrimitiveLocalVariable(FlowNode node) {
3117 VarDescriptor varDesc = (VarDescriptor) node.getDescTuple().get(0);
3118 return varDesc.getType().isPrimitive();
3121 private SSJavaLattice<String> getLattice(Descriptor d) {
3122 if (d instanceof MethodDescriptor) {
3123 return getMethodLattice((MethodDescriptor) d);
3125 return getFieldLattice((ClassDescriptor) d);
3129 private SSJavaLattice<String> getMethodLattice(MethodDescriptor md) {
3130 if (!md2lattice.containsKey(md)) {
3131 md2lattice.put(md, new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM));
3133 return md2lattice.get(md);
3136 private void setMethodLattice(MethodDescriptor md, SSJavaLattice<String> lattice) {
3137 md2lattice.put(md, lattice);
3140 private void extractFlowsBetweenFields(ClassDescriptor cd, FlowNode srcNode, FlowNode dstNode,
3143 NTuple<Descriptor> srcCurTuple = srcNode.getCurrentDescTuple();
3144 NTuple<Descriptor> dstCurTuple = dstNode.getCurrentDescTuple();
3146 if (srcCurTuple.get(idx).equals(dstCurTuple.get(idx)) && srcCurTuple.size() > (idx + 1)
3147 && dstCurTuple.size() > (idx + 1)) {
3148 // value flow between fields: we don't need to add a binary relation
3151 Descriptor desc = srcCurTuple.get(idx);
3152 ClassDescriptor classDesc;
3155 classDesc = ((VarDescriptor) desc).getType().getClassDesc();
3157 classDesc = ((FieldDescriptor) desc).getType().getClassDesc();
3160 extractFlowsBetweenFields(classDesc, srcNode, dstNode, idx + 1);
3164 Descriptor srcFieldDesc = srcCurTuple.get(idx);
3165 Descriptor dstFieldDesc = dstCurTuple.get(idx);
3168 getHierarchyGraph(cd).addEdge(srcFieldDesc, dstFieldDesc);
3174 private void extractRelationFromFieldFlows(ClassDescriptor cd, FlowNode srcNode,
3175 FlowNode dstNode, int idx) throws CyclicFlowException {
3177 if (srcNode.getDescTuple().get(idx).equals(dstNode.getDescTuple().get(idx))
3178 && srcNode.getDescTuple().size() > (idx + 1) && dstNode.getDescTuple().size() > (idx + 1)) {
3179 // value flow between fields: we don't need to add a binary relation
3182 Descriptor desc = srcNode.getDescTuple().get(idx);
3183 ClassDescriptor classDesc;
3186 classDesc = ((VarDescriptor) desc).getType().getClassDesc();
3188 classDesc = ((FieldDescriptor) desc).getType().getClassDesc();
3191 extractRelationFromFieldFlows(classDesc, srcNode, dstNode, idx + 1);
3195 Descriptor srcFieldDesc = srcNode.getDescTuple().get(idx);
3196 Descriptor dstFieldDesc = dstNode.getDescTuple().get(idx);
3198 // add a new binary relation of dstNode < srcNode
3199 SSJavaLattice<String> fieldLattice = getFieldLattice(cd);
3200 LocationInfo fieldInfo = getFieldLocationInfo(cd);
3202 String srcSymbol = fieldInfo.getFieldInferLocation(srcFieldDesc).getLocIdentifier();
3203 String dstSymbol = fieldInfo.getFieldInferLocation(dstFieldDesc).getLocIdentifier();
3205 addRelationHigherToLower(fieldLattice, fieldInfo, srcSymbol, dstSymbol);
3211 public SSJavaLattice<String> getFieldLattice(ClassDescriptor cd) {
3212 if (!cd2lattice.containsKey(cd)) {
3213 cd2lattice.put(cd, new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM));
3215 return cd2lattice.get(cd);
3218 public LinkedList<MethodDescriptor> computeMethodList() {
3220 Set<MethodDescriptor> toSort = new HashSet<MethodDescriptor>();
3224 Set<MethodDescriptor> visited = new HashSet<MethodDescriptor>();
3225 Set<MethodDescriptor> reachableCallee = new HashSet<MethodDescriptor>();
3227 while (!toAnalyzeIsEmpty()) {
3228 ClassDescriptor cd = toAnalyzeNext();
3230 setupToAnalazeMethod(cd);
3231 temp_toanalyzeMethodList.removeAll(visited);
3233 while (!toAnalyzeMethodIsEmpty()) {
3234 MethodDescriptor md = toAnalyzeMethodNext();
3235 if ((!visited.contains(md))
3236 && (ssjava.needTobeAnnotated(md) || reachableCallee.contains(md))) {
3238 // creates a mapping from a method descriptor to virtual methods
3239 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
3240 if (md.isStatic()) {
3241 setPossibleCallees.add(md);
3243 setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md));
3246 Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getCalleeSet(md);
3247 Set<MethodDescriptor> needToAnalyzeCalleeSet = new HashSet<MethodDescriptor>();
3249 for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) {
3250 MethodDescriptor calleemd = (MethodDescriptor) iterator.next();
3251 if ((!ssjava.isTrustMethod(calleemd))
3252 && (!ssjava.isSSJavaUtil(calleemd.getClassDesc()))) {
3253 if (!visited.contains(calleemd)) {
3254 temp_toanalyzeMethodList.add(calleemd);
3256 reachableCallee.add(calleemd);
3257 needToAnalyzeCalleeSet.add(calleemd);
3261 mapMethodToCalleeSet.put(md, needToAnalyzeCalleeSet);
3270 return ssjava.topologicalSort(toSort);
3274 public void constructFlowGraph() {
3276 System.out.println("");
3277 toanalyze_methodDescList = computeMethodList();
3279 LinkedList<MethodDescriptor> methodDescList =
3280 (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
3282 System.out.println("@@@methodDescList=" + methodDescList);
3285 while (!methodDescList.isEmpty()) {
3286 MethodDescriptor md = methodDescList.removeLast();
3287 if (state.SSJAVADEBUG) {
3288 System.out.println();
3289 System.out.println("SSJAVA: Constructing a flow graph: " + md);
3291 // creates a mapping from a parameter descriptor to its index
3292 Map<Descriptor, Integer> mapParamDescToIdx = new HashMap<Descriptor, Integer>();
3294 if (!md.isStatic()) {
3296 mapParamDescToIdx.put(md.getThis(), 0);
3299 for (int i = 0; i < md.numParameters(); i++) {
3300 Descriptor paramDesc = (Descriptor) md.getParameter(i);
3301 mapParamDescToIdx.put(paramDesc, new Integer(i + offset));
3304 FlowGraph fg = new FlowGraph(md, mapParamDescToIdx);
3305 mapMethodDescriptorToFlowGraph.put(md, fg);
3307 analyzeMethodBody(md.getClassDesc(), md);
3308 propagateFlowsFromCalleesWithNoCompositeLocation(md);
3309 // assignCompositeLocation(md);
3313 _debug_printGraph();
3317 private Set<MethodInvokeNode> getMethodInvokeNodeSet(MethodDescriptor md) {
3318 if (!mapMethodDescriptorToMethodInvokeNodeSet.containsKey(md)) {
3319 mapMethodDescriptorToMethodInvokeNodeSet.put(md, new HashSet<MethodInvokeNode>());
3321 return mapMethodDescriptorToMethodInvokeNodeSet.get(md);
3324 private void constructSubGlobalFlowGraph(MethodDescriptor md) {
3326 FlowGraph flowGraph = getFlowGraph(md);
3328 Set<MethodInvokeNode> setMethodInvokeNode = getMethodInvokeNodeSet(md);
3330 for (Iterator<MethodInvokeNode> iter = setMethodInvokeNode.iterator(); iter.hasNext();) {
3331 MethodInvokeNode min = iter.next();
3332 propagateFlowsFromMethodInvokeNode(md, min);
3337 private void propagateFlowsFromMethodInvokeNode(MethodDescriptor mdCaller, MethodInvokeNode min) {
3338 // the transformation for a call site propagates flows through parameters
3339 // if the method is virtual, it also grab all relations from any possible
3342 MethodDescriptor mdCallee = min.getMethod();
3343 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
3344 if (mdCallee.isStatic()) {
3345 setPossibleCallees.add(mdCallee);
3347 Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getMethods(mdCallee);
3348 // removes method descriptors that are not invoked by the caller
3349 calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller));
3350 setPossibleCallees.addAll(calleeSet);
3353 for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
3354 MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
3355 contributeCalleeFlows(min, mdCaller, possibleMdCallee);
3360 private void assignCompositeLocation(MethodDescriptor md) {
3362 FlowGraph flowGraph = getFlowGraph(md);
3364 Set<FlowNode> nodeSet = flowGraph.getNodeSet();
3366 next: for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
3367 FlowNode flowNode = (FlowNode) iterator.next();
3369 // assign a composite location only to the local variable
3370 if (flowNode.getCurrentDescTuple().size() == 1) {
3372 List<NTuple<Descriptor>> prefixList = calculatePrefixList(flowGraph, flowNode);
3373 Set<FlowNode> reachSet = flowGraph.getReachFlowNodeSetFrom(flowNode);
3375 for (int i = 0; i < prefixList.size(); i++) {
3376 NTuple<Descriptor> curPrefix = prefixList.get(i);
3377 Set<NTuple<Descriptor>> reachableCommonPrefixSet = new HashSet<NTuple<Descriptor>>();
3379 for (Iterator iterator2 = reachSet.iterator(); iterator2.hasNext();) {
3380 FlowNode reachNode = (FlowNode) iterator2.next();
3381 if (reachNode.getCurrentDescTuple().startsWith(curPrefix)) {
3382 reachableCommonPrefixSet.add(reachNode.getCurrentDescTuple());
3386 if (!reachableCommonPrefixSet.isEmpty()) {
3387 System.out.println("NEED TO ASSIGN COMP LOC TO " + flowNode + " with prefix="
3389 CompositeLocation newCompLoc = generateCompositeLocation(md, curPrefix);
3390 flowNode.setCompositeLocation(newCompLoc);
3401 private void propagateFlowsFromCalleesWithNoCompositeLocation(MethodDescriptor mdCaller) {
3403 // the transformation for a call site propagates flows through parameters
3404 // if the method is virtual, it also grab all relations from any possible
3407 Set<MethodInvokeNode> setMethodInvokeNode =
3408 mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller);
3410 if (setMethodInvokeNode != null) {
3412 for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) {
3413 MethodInvokeNode min = (MethodInvokeNode) iterator.next();
3414 MethodDescriptor mdCallee = min.getMethod();
3415 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
3416 if (mdCallee.isStatic()) {
3417 setPossibleCallees.add(mdCallee);
3419 Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getMethods(mdCallee);
3420 // removes method descriptors that are not invoked by the caller
3421 calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller));
3422 setPossibleCallees.addAll(calleeSet);
3425 for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
3426 MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
3427 propagateFlowsToCallerWithNoCompositeLocation(min, mdCaller, possibleMdCallee);
3435 private void propagateFlowsFromCallees(MethodDescriptor mdCaller) {
3437 // the transformation for a call site propagates flows through parameters
3438 // if the method is virtual, it also grab all relations from any possible
3441 Set<MethodInvokeNode> setMethodInvokeNode =
3442 mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller);
3444 if (setMethodInvokeNode != null) {
3446 for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) {
3447 MethodInvokeNode min = (MethodInvokeNode) iterator.next();
3448 MethodDescriptor mdCallee = min.getMethod();
3449 Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
3450 if (mdCallee.isStatic()) {
3451 setPossibleCallees.add(mdCallee);
3453 Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getMethods(mdCallee);
3454 // removes method descriptors that are not invoked by the caller
3455 calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller));
3456 setPossibleCallees.addAll(calleeSet);
3459 for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
3460 MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
3461 propagateFlowsToCaller(min, mdCaller, possibleMdCallee);
3469 private void analyzeMethodBody(ClassDescriptor cd, MethodDescriptor md) {
3470 BlockNode bn = state.getMethodBody(md);
3471 NodeTupleSet implicitFlowTupleSet = new NodeTupleSet();
3472 analyzeFlowBlockNode(md, md.getParameterTable(), bn, implicitFlowTupleSet);
3475 private void analyzeFlowBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn,
3476 NodeTupleSet implicitFlowTupleSet) {
3478 bn.getVarTable().setParent(nametable);
3479 for (int i = 0; i < bn.size(); i++) {
3480 BlockStatementNode bsn = bn.get(i);
3481 analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet);
3486 private void analyzeBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
3487 BlockStatementNode bsn, NodeTupleSet implicitFlowTupleSet) {
3489 switch (bsn.kind()) {
3490 case Kind.BlockExpressionNode:
3491 analyzeBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn, implicitFlowTupleSet);
3494 case Kind.DeclarationNode:
3495 analyzeFlowDeclarationNode(md, nametable, (DeclarationNode) bsn, implicitFlowTupleSet);
3498 case Kind.IfStatementNode:
3499 analyzeFlowIfStatementNode(md, nametable, (IfStatementNode) bsn, implicitFlowTupleSet);
3503 analyzeFlowLoopNode(md, nametable, (LoopNode) bsn, implicitFlowTupleSet);
3506 case Kind.ReturnNode:
3507 analyzeFlowReturnNode(md, nametable, (ReturnNode) bsn, implicitFlowTupleSet);
3510 case Kind.SubBlockNode:
3511 analyzeFlowSubBlockNode(md, nametable, (SubBlockNode) bsn, implicitFlowTupleSet);
3514 case Kind.ContinueBreakNode:
3517 case Kind.SwitchStatementNode:
3518 analyzeSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn, implicitFlowTupleSet);
3525 private void analyzeSwitchBlockNode(MethodDescriptor md, SymbolTable nametable,
3526 SwitchBlockNode sbn, NodeTupleSet implicitFlowTupleSet) {
3528 analyzeFlowBlockNode(md, nametable, sbn.getSwitchBlockStatement(), implicitFlowTupleSet);
3532 private void analyzeSwitchStatementNode(MethodDescriptor md, SymbolTable nametable,
3533 SwitchStatementNode ssn, NodeTupleSet implicitFlowTupleSet) {
3535 NodeTupleSet condTupleNode = new NodeTupleSet();
3536 analyzeFlowExpressionNode(md, nametable, ssn.getCondition(), condTupleNode, null,
3537 implicitFlowTupleSet, false);
3539 NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
3541 newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
3542 newImplicitTupleSet.addTupleSet(condTupleNode);
3544 if (newImplicitTupleSet.size() > 1) {
3545 // need to create an intermediate node for the GLB of conditional locations & implicit flows
3546 NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
3547 for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) {
3548 NTuple<Descriptor> tuple = idxIter.next();
3549 addFlowGraphEdge(md, tuple, interTuple);
3551 newImplicitTupleSet.clear();
3552 newImplicitTupleSet.addTuple(interTuple);
3555 BlockNode sbn = ssn.getSwitchBody();
3556 for (int i = 0; i < sbn.size(); i++) {
3557 analyzeSwitchBlockNode(md, nametable, (SwitchBlockNode) sbn.get(i), newImplicitTupleSet);
3562 private void analyzeFlowSubBlockNode(MethodDescriptor md, SymbolTable nametable,
3563 SubBlockNode sbn, NodeTupleSet implicitFlowTupleSet) {
3564 analyzeFlowBlockNode(md, nametable, sbn.getBlockNode(), implicitFlowTupleSet);
3567 private void analyzeFlowReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode rn,
3568 NodeTupleSet implicitFlowTupleSet) {
3570 ExpressionNode returnExp = rn.getReturnExpression();
3572 if (returnExp != null) {
3573 NodeTupleSet nodeSet = new NodeTupleSet();
3574 // if a return expression returns a literal value, nodeSet is empty
3575 analyzeFlowExpressionNode(md, nametable, returnExp, nodeSet, false);
3576 FlowGraph fg = getFlowGraph(md);
3578 // if (implicitFlowTupleSet.size() == 1
3579 // && fg.getFlowNode(implicitFlowTupleSet.iterator().next()).isIntermediate()) {
3581 // // since there is already an intermediate node for the GLB of implicit flows
3582 // // we don't need to create another intermediate node.
3583 // // just re-use the intermediate node for implicit flows.
3585 // FlowNode meetNode = fg.getFlowNode(implicitFlowTupleSet.iterator().next());
3587 // for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
3588 // NTuple<Descriptor> returnNodeTuple = (NTuple<Descriptor>) iterator.next();
3589 // fg.addValueFlowEdge(returnNodeTuple, meetNode.getDescTuple());
3594 NodeTupleSet currentFlowTupleSet = new NodeTupleSet();
3596 // add tuples from return node
3597 currentFlowTupleSet.addTupleSet(nodeSet);
3599 // add tuples corresponding to the current implicit flows
3600 currentFlowTupleSet.addTupleSet(implicitFlowTupleSet);
3602 if (currentFlowTupleSet.size() > 1) {
3603 FlowNode meetNode = fg.createIntermediateNode();
3604 for (Iterator iterator = currentFlowTupleSet.iterator(); iterator.hasNext();) {
3605 NTuple<Descriptor> currentFlowTuple = (NTuple<Descriptor>) iterator.next();
3606 fg.addValueFlowEdge(currentFlowTuple, meetNode.getDescTuple());
3608 fg.addReturnFlowNode(meetNode.getDescTuple());
3609 } else if (currentFlowTupleSet.size() == 1) {
3610 NTuple<Descriptor> tuple = currentFlowTupleSet.iterator().next();
3611 fg.addReturnFlowNode(tuple);
3618 private void analyzeFlowLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln,
3619 NodeTupleSet implicitFlowTupleSet) {
3621 if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) {
3623 NodeTupleSet condTupleNode = new NodeTupleSet();
3624 analyzeFlowExpressionNode(md, nametable, ln.getCondition(), condTupleNode, null,
3625 implicitFlowTupleSet, false);
3627 NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
3629 newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
3630 newImplicitTupleSet.addTupleSet(condTupleNode);
3632 if (newImplicitTupleSet.size() > 1) {
3633 // need to create an intermediate node for the GLB of conditional locations & implicit flows
3634 NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
3635 for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter
3637 NTuple<Descriptor> tuple = idxIter.next();
3638 addFlowGraphEdge(md, tuple, interTuple);
3640 newImplicitTupleSet.clear();
3641 newImplicitTupleSet.addTuple(interTuple);
3646 // System.out.println("condTupleNode="+condTupleNode);
3647 // NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
3649 // for (Iterator<NTuple<Descriptor>> idxIter = condTupleNode.iterator(); idxIter.hasNext();) {
3650 // NTuple<Descriptor> tuple = idxIter.next();
3651 // addFlowGraphEdge(md, tuple, interTuple);
3654 // for (Iterator<NTuple<Descriptor>> idxIter = implicitFlowTupleSet.iterator(); idxIter
3656 // NTuple<Descriptor> tuple = idxIter.next();
3657 // addFlowGraphEdge(md, tuple, interTuple);
3660 // NodeTupleSet newImplicitSet = new NodeTupleSet();
3661 // newImplicitSet.addTuple(interTuple);
3662 analyzeFlowBlockNode(md, nametable, ln.getBody(), newImplicitTupleSet);
3665 // condTupleNode.addTupleSet(implicitFlowTupleSet);
3667 // add edges from condNodeTupleSet to all nodes of conditional nodes
3668 // analyzeFlowBlockNode(md, nametable, ln.getBody(), condTupleNode);
3671 // check 'for loop' case
3672 BlockNode bn = ln.getInitializer();
3673 bn.getVarTable().setParent(nametable);
3674 for (int i = 0; i < bn.size(); i++) {
3675 BlockStatementNode bsn = bn.get(i);
3676 analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet);
3679 NodeTupleSet condTupleNode = new NodeTupleSet();
3680 analyzeFlowExpressionNode(md, bn.getVarTable(), ln.getCondition(), condTupleNode, null,
3681 implicitFlowTupleSet, false);
3684 NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
3686 for (Iterator<NTuple<Descriptor>> idxIter = condTupleNode.iterator(); idxIter.hasNext();) {
3687 NTuple<Descriptor> tuple = idxIter.next();
3688 addFlowGraphEdge(md, tuple, interTuple);
3691 for (Iterator<NTuple<Descriptor>> idxIter = implicitFlowTupleSet.iterator(); idxIter
3693 NTuple<Descriptor> tuple = idxIter.next();
3694 addFlowGraphEdge(md, tuple, interTuple);
3697 NodeTupleSet newImplicitSet = new NodeTupleSet();
3698 newImplicitSet.addTuple(interTuple);
3699 analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(), newImplicitSet);
3700 analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(), newImplicitSet);
3703 // condTupleNode.addTupleSet(implicitFlowTupleSet);
3705 // analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(),
3707 // analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(),
3714 private void analyzeFlowIfStatementNode(MethodDescriptor md, SymbolTable nametable,
3715 IfStatementNode isn, NodeTupleSet implicitFlowTupleSet) {
3717 System.out.println("analyzeFlowIfStatementNode=" + isn.printNode(0));
3719 NodeTupleSet condTupleNode = new NodeTupleSet();
3720 analyzeFlowExpressionNode(md, nametable, isn.getCondition(), condTupleNode, null,
3721 implicitFlowTupleSet, false);
3723 NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
3725 newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
3726 newImplicitTupleSet.addTupleSet(condTupleNode);
3728 System.out.println("condTupleNode=" + condTupleNode);
3729 System.out.println("implicitFlowTupleSet=" + implicitFlowTupleSet);
3730 System.out.println("newImplicitTupleSet=" + newImplicitTupleSet);
3732 if (newImplicitTupleSet.size() > 1) {
3734 // need to create an intermediate node for the GLB of conditional locations & implicit flows
3735 NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
3736 for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) {
3737 NTuple<Descriptor> tuple = idxIter.next();
3738 addFlowGraphEdge(md, tuple, interTuple);
3740 newImplicitTupleSet.clear();
3741 newImplicitTupleSet.addTuple(interTuple);
3744 analyzeFlowBlockNode(md, nametable, isn.getTrueBlock(), newImplicitTupleSet);
3746 if (isn.getFalseBlock() != null) {
3747 analyzeFlowBlockNode(md, nametable, isn.getFalseBlock(), newImplicitTupleSet);
3752 private void analyzeFlowDeclarationNode(MethodDescriptor md, SymbolTable nametable,
3753 DeclarationNode dn, NodeTupleSet implicitFlowTupleSet) {
3755 VarDescriptor vd = dn.getVarDescriptor();
3756 mapDescToDefinitionLine.put(vd, dn.getNumLine());
3757 NTuple<Descriptor> tupleLHS = new NTuple<Descriptor>();
3759 FlowNode fn = getFlowGraph(md).createNewFlowNode(tupleLHS);
3760 fn.setDeclarationNode();
3762 if (dn.getExpression() != null) {
3764 NodeTupleSet nodeSetRHS = new NodeTupleSet();
3765 analyzeFlowExpressionNode(md, nametable, dn.getExpression(), nodeSetRHS, null,
3766 implicitFlowTupleSet, false);
3768 // creates edges from RHS to LHS
3769 NTuple<Descriptor> interTuple = null;
3770 if (nodeSetRHS.size() > 1) {
3771 interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
3774 for (Iterator<NTuple<Descriptor>> iter = nodeSetRHS.iterator(); iter.hasNext();) {
3775 NTuple<Descriptor> fromTuple = iter.next();
3776 addFlowGraphEdge(md, fromTuple, interTuple, tupleLHS);
3779 // creates edges from implicitFlowTupleSet to LHS
3780 for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
3781 NTuple<Descriptor> implicitTuple = iter.next();
3782 addFlowGraphEdge(md, implicitTuple, tupleLHS);
3789 private void analyzeBlockExpressionNode(MethodDescriptor md, SymbolTable nametable,
3790 BlockExpressionNode ben, NodeTupleSet implicitFlowTupleSet) {
3791 analyzeFlowExpressionNode(md, nametable, ben.getExpression(), null, null, implicitFlowTupleSet,
3795 private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
3796 ExpressionNode en, NodeTupleSet nodeSet, boolean isLHS) {
3797 return analyzeFlowExpressionNode(md, nametable, en, nodeSet, null, new NodeTupleSet(), isLHS);
3800 private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
3801 ExpressionNode en, NodeTupleSet nodeSet, NTuple<Descriptor> base,
3802 NodeTupleSet implicitFlowTupleSet, boolean isLHS) {
3804 // note that expression node can create more than one flow node
3805 // nodeSet contains of flow nodes
3806 // base is always assigned to null except the case of a name node!
3808 NTuple<Descriptor> flowTuple;
3810 switch (en.kind()) {
3812 case Kind.AssignmentNode:
3813 analyzeFlowAssignmentNode(md, nametable, (AssignmentNode) en, nodeSet, base,
3814 implicitFlowTupleSet);
3817 case Kind.FieldAccessNode:
3819 analyzeFlowFieldAccessNode(md, nametable, (FieldAccessNode) en, nodeSet, base,
3820 implicitFlowTupleSet, isLHS);
3821 if (flowTuple != null) {
3822 nodeSet.addTuple(flowTuple);
3827 NodeTupleSet nameNodeSet = new NodeTupleSet();
3829 analyzeFlowNameNode(md, nametable, (NameNode) en, nameNodeSet, base, implicitFlowTupleSet);
3830 if (flowTuple != null) {
3831 nodeSet.addTuple(flowTuple);
3836 analyzeFlowOpNode(md, nametable, (OpNode) en, nodeSet, implicitFlowTupleSet);
3839 case Kind.CreateObjectNode:
3840 analyzeCreateObjectNode(md, nametable, (CreateObjectNode) en);
3843 case Kind.ArrayAccessNode:
3844 analyzeFlowArrayAccessNode(md, nametable, (ArrayAccessNode) en, nodeSet, isLHS);
3847 case Kind.LiteralNode:
3848 analyzeLiteralNode(md, nametable, (LiteralNode) en);
3851 case Kind.MethodInvokeNode:
3852 analyzeFlowMethodInvokeNode(md, nametable, (MethodInvokeNode) en, nodeSet,
3853 implicitFlowTupleSet);
3856 case Kind.TertiaryNode:
3857 analyzeFlowTertiaryNode(md, nametable, (TertiaryNode) en, nodeSet, implicitFlowTupleSet);
3861 analyzeFlowCastNode(md, nametable, (CastNode) en, nodeSet, base, implicitFlowTupleSet);
3863 // case Kind.InstanceOfNode:
3864 // checkInstanceOfNode(md, nametable, (InstanceOfNode) en, td);
3867 // case Kind.ArrayInitializerNode:
3868 // checkArrayInitializerNode(md, nametable, (ArrayInitializerNode) en,
3872 // case Kind.ClassTypeNode:
3873 // checkClassTypeNode(md, nametable, (ClassTypeNode) en, td);
3876 // case Kind.OffsetNode:
3877 // checkOffsetNode(md, nametable, (OffsetNode)en, td);
3885 private void analyzeFlowCastNode(MethodDescriptor md, SymbolTable nametable, CastNode cn,
3886 NodeTupleSet nodeSet, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
3888 analyzeFlowExpressionNode(md, nametable, cn.getExpression(), nodeSet, base,
3889 implicitFlowTupleSet, false);
3893 private void analyzeFlowTertiaryNode(MethodDescriptor md, SymbolTable nametable, TertiaryNode tn,
3894 NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
3896 NodeTupleSet tertiaryTupleNode = new NodeTupleSet();
3897 analyzeFlowExpressionNode(md, nametable, tn.getCond(), tertiaryTupleNode, null,
3898 implicitFlowTupleSet, false);
3900 // add edges from tertiaryTupleNode to all nodes of conditional nodes
3901 tertiaryTupleNode.addTupleSet(implicitFlowTupleSet);
3902 analyzeFlowExpressionNode(md, nametable, tn.getTrueExpr(), tertiaryTupleNode, null,
3903 implicitFlowTupleSet, false);
3905 analyzeFlowExpressionNode(md, nametable, tn.getFalseExpr(), tertiaryTupleNode, null,
3906 implicitFlowTupleSet, false);
3908 nodeSet.addTupleSet(tertiaryTupleNode);
3912 private void addMapCallerMethodDescToMethodInvokeNodeSet(MethodDescriptor caller,
3913 MethodInvokeNode min) {
3914 Set<MethodInvokeNode> set = mapMethodDescriptorToMethodInvokeNodeSet.get(caller);
3916 set = new HashSet<MethodInvokeNode>();
3917 mapMethodDescriptorToMethodInvokeNodeSet.put(caller, set);
3922 private void addParamNodeFlowingToReturnValue(MethodDescriptor md, FlowNode fn) {
3924 if (!mapMethodDescToParamNodeFlowsToReturnValue.containsKey(md)) {
3925 mapMethodDescToParamNodeFlowsToReturnValue.put(md, new HashSet<FlowNode>());
3927 mapMethodDescToParamNodeFlowsToReturnValue.get(md).add(fn);
3930 private Set<FlowNode> getParamNodeFlowingToReturnValue(MethodDescriptor md) {
3931 return mapMethodDescToParamNodeFlowsToReturnValue.get(md);
3934 private void analyzeFlowMethodInvokeNode(MethodDescriptor md, SymbolTable nametable,
3935 MethodInvokeNode min, NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
3937 if (nodeSet == null) {
3938 nodeSet = new NodeTupleSet();
3941 MethodDescriptor calleeMethodDesc = min.getMethod();
3943 NameDescriptor baseName = min.getBaseName();
3944 boolean isSystemout = false;
3945 if (baseName != null) {
3946 isSystemout = baseName.getSymbol().equals("System.out");
3949 if (!ssjava.isSSJavaUtil(calleeMethodDesc.getClassDesc())
3950 && !ssjava.isTrustMethod(calleeMethodDesc) && !isSystemout) {
3952 addMapCallerMethodDescToMethodInvokeNodeSet(md, min);
3954 FlowGraph calleeFlowGraph = getFlowGraph(calleeMethodDesc);
3955 Set<FlowNode> calleeReturnSet = calleeFlowGraph.getReturnNodeSet();
3957 System.out.println("#calleeReturnSet=" + calleeReturnSet);
3959 if (min.getExpression() != null) {
3961 NodeTupleSet baseNodeSet = new NodeTupleSet();
3962 analyzeFlowExpressionNode(md, nametable, min.getExpression(), baseNodeSet, null,
3963 implicitFlowTupleSet, false);
3965 assert (baseNodeSet.size() == 1);
3966 mapMethodInvokeNodeToBaseTuple.put(min, baseNodeSet.iterator().next());
3968 if (!min.getMethod().isStatic()) {
3969 addArgIdxMap(min, 0, baseNodeSet);
3971 for (Iterator iterator = calleeReturnSet.iterator(); iterator.hasNext();) {
3972 FlowNode returnNode = (FlowNode) iterator.next();
3973 NTuple<Descriptor> returnDescTuple = returnNode.getDescTuple();
3974 if (returnDescTuple.startsWith(calleeMethodDesc.getThis())) {
3975 // the location type of the return value is started with 'this'
3977 for (Iterator<NTuple<Descriptor>> baseIter = baseNodeSet.iterator(); baseIter
3979 NTuple<Descriptor> baseTuple = baseIter.next();
3980 NTuple<Descriptor> inFlowTuple = new NTuple<Descriptor>(baseTuple.getList());
3981 inFlowTuple.addAll(returnDescTuple.subList(1, returnDescTuple.size()));
3982 nodeSet.addTuple(inFlowTuple);
3985 Set<FlowNode> inFlowSet = calleeFlowGraph.getIncomingFlowNodeSet(returnNode);
3986 for (Iterator iterator2 = inFlowSet.iterator(); iterator2.hasNext();) {
3987 FlowNode inFlowNode = (FlowNode) iterator2.next();
3988 if (inFlowNode.getDescTuple().startsWith(calleeMethodDesc.getThis())) {
3989 nodeSet.addTupleSet(baseNodeSet);
3998 // analyze parameter flows
4000 if (min.numArgs() > 0) {
4003 if (min.getMethod().isStatic()) {
4009 for (int i = 0; i < min.numArgs(); i++) {
4010 ExpressionNode en = min.getArg(i);
4011 int idx = i + offset;
4012 NodeTupleSet argTupleSet = new NodeTupleSet();
4013 analyzeFlowExpressionNode(md, nametable, en, argTupleSet, false);
4014 // if argument is liternal node, argTuple is set to NULL.
4015 addArgIdxMap(min, idx, argTupleSet);
4016 FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx);
4017 if (hasInFlowTo(calleeFlowGraph, paramNode, calleeReturnSet)
4018 || calleeMethodDesc.getModifiers().isNative()) {
4019 addParamNodeFlowingToReturnValue(calleeMethodDesc, paramNode);
4020 nodeSet.addTupleSet(argTupleSet);
4026 // propagateFlowsFromCallee(min, md, min.getMethod());
4032 private boolean hasInFlowTo(FlowGraph fg, FlowNode inNode, Set<FlowNode> nodeSet) {
4033 // return true if inNode has in-flows to nodeSet
4034 Set<FlowNode> reachableSet = fg.getReachFlowNodeSetFrom(inNode);
4035 for (Iterator iterator = reachableSet.iterator(); iterator.hasNext();) {
4036 FlowNode fn = (FlowNode) iterator.next();
4037 if (nodeSet.contains(fn)) {
4044 private NodeTupleSet getNodeTupleSetByArgIdx(MethodInvokeNode min, int idx) {
4045 return mapMethodInvokeNodeToArgIdxMap.get(min).get(new Integer(idx));
4048 private void addArgIdxMap(MethodInvokeNode min, int idx, NodeTupleSet tupleSet) {
4049 Map<Integer, NodeTupleSet> mapIdxToTupleSet = mapMethodInvokeNodeToArgIdxMap.get(min);
4050 if (mapIdxToTupleSet == null) {
4051 mapIdxToTupleSet = new HashMap<Integer, NodeTupleSet>();
4052 mapMethodInvokeNodeToArgIdxMap.put(min, mapIdxToTupleSet);
4054 mapIdxToTupleSet.put(new Integer(idx), tupleSet);
4057 private void analyzeFlowMethodParameters(MethodDescriptor callermd, SymbolTable nametable,
4058 MethodInvokeNode min, NodeTupleSet nodeSet) {
4060 if (min.numArgs() > 0) {
4063 if (min.getMethod().isStatic()) {
4067 // NTuple<Descriptor> thisArgTuple = new NTuple<Descriptor>();
4068 // thisArgTuple.add(callermd.getThis());
4069 // NodeTupleSet argTupleSet = new NodeTupleSet();
4070 // argTupleSet.addTuple(thisArgTuple);
4071 // addArgIdxMap(min, 0, argTupleSet);
4072 // nodeSet.addTuple(thisArgTuple);
4075 for (int i = 0; i < min.numArgs(); i++) {
4076 ExpressionNode en = min.getArg(i);
4077 NodeTupleSet argTupleSet = new NodeTupleSet();
4078 analyzeFlowExpressionNode(callermd, nametable, en, argTupleSet, false);
4079 // if argument is liternal node, argTuple is set to NULL.
4080 addArgIdxMap(min, i + offset, argTupleSet);
4081 nodeSet.addTupleSet(argTupleSet);
4088 private void analyzeLiteralNode(MethodDescriptor md, SymbolTable nametable, LiteralNode en) {
4092 private void analyzeFlowArrayAccessNode(MethodDescriptor md, SymbolTable nametable,
4093 ArrayAccessNode aan, NodeTupleSet nodeSet, boolean isLHS) {
4095 NodeTupleSet expNodeTupleSet = new NodeTupleSet();
4096 NTuple<Descriptor> base =
4097 analyzeFlowExpressionNode(md, nametable, aan.getExpression(), expNodeTupleSet, isLHS);
4099 NodeTupleSet idxNodeTupleSet = new NodeTupleSet();
4100 analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, isLHS);
4103 // need to create an edge from idx to array
4104 for (Iterator<NTuple<Descriptor>> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) {
4105 NTuple<Descriptor> idxTuple = idxIter.next();
4106 for (Iterator<NTuple<Descriptor>> arrIter = expNodeTupleSet.iterator(); arrIter.hasNext();) {
4107 NTuple<Descriptor> arrTuple = arrIter.next();
4108 getFlowGraph(md).addValueFlowEdge(idxTuple, arrTuple);
4112 nodeSet.addTupleSet(expNodeTupleSet);
4114 nodeSet.addTupleSet(expNodeTupleSet);
4115 nodeSet.addTupleSet(idxNodeTupleSet);
4119 private void analyzeCreateObjectNode(MethodDescriptor md, SymbolTable nametable,
4120 CreateObjectNode en) {
4121 // TODO Auto-generated method stub
4125 private void analyzeFlowOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on,
4126 NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
4128 NodeTupleSet leftOpSet = new NodeTupleSet();
4129 NodeTupleSet rightOpSet = new NodeTupleSet();
4132 analyzeFlowExpressionNode(md, nametable, on.getLeft(), leftOpSet, null, implicitFlowTupleSet,
4135 if (on.getRight() != null) {
4137 analyzeFlowExpressionNode(md, nametable, on.getRight(), rightOpSet, null,
4138 implicitFlowTupleSet, false);
4141 Operation op = on.getOp();
4143 switch (op.getOp()) {
4145 case Operation.UNARYPLUS:
4146 case Operation.UNARYMINUS:
4147 case Operation.LOGIC_NOT:
4149 nodeSet.addTupleSet(leftOpSet);
4152 case Operation.LOGIC_OR:
4153 case Operation.LOGIC_AND:
4154 case Operation.COMP:
4155 case Operation.BIT_OR:
4156 case Operation.BIT_XOR:
4157 case Operation.BIT_AND:
4158 case Operation.ISAVAILABLE:
4159 case Operation.EQUAL:
4160 case Operation.NOTEQUAL:
4167 case Operation.MULT:
4170 case Operation.LEFTSHIFT:
4171 case Operation.RIGHTSHIFT:
4172 case Operation.URIGHTSHIFT:
4174 // there are two operands
4175 nodeSet.addTupleSet(leftOpSet);
4176 nodeSet.addTupleSet(rightOpSet);
4180 throw new Error(op.toString());
4185 private NTuple<Descriptor> analyzeFlowNameNode(MethodDescriptor md, SymbolTable nametable,
4186 NameNode nn, NodeTupleSet nodeSet, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
4188 // System.out.println("analyzeFlowNameNode=" + nn.printNode(0));
4191 base = new NTuple<Descriptor>();
4194 NameDescriptor nd = nn.getName();
4196 if (nd.getBase() != null) {
4198 analyzeFlowExpressionNode(md, nametable, nn.getExpression(), nodeSet, base,
4199 implicitFlowTupleSet, false);
4201 // base node has the top location
4205 String varname = nd.toString();
4206 if (varname.equals("this")) {
4208 base.add(md.getThis());
4212 Descriptor d = (Descriptor) nametable.get(varname);
4214 if (d instanceof VarDescriptor) {
4215 VarDescriptor vd = (VarDescriptor) d;
4217 } else if (d instanceof FieldDescriptor) {
4218 // the type of field descriptor has a location!
4219 FieldDescriptor fd = (FieldDescriptor) d;
4220 if (fd.isStatic()) {
4222 // if it is 'static final', no need to have flow node for the TOP
4226 // if 'static', assign the default GLOBAL LOCATION to the first
4227 // element of the tuple
4228 base.add(GLOBALDESC);
4231 // the location of field access starts from this, followed by field
4233 base.add(md.getThis());
4237 } else if (d == null) {
4238 // access static field
4239 base.add(GLOBALDESC);
4240 base.add(nn.getField());
4243 // FieldDescriptor fd = nn.getField();addFlowGraphEdge
4245 // MethodLattice<String> localLattice = ssjava.getMethodLattice(md);
4246 // String globalLocId = localLattice.getGlobalLoc();
4247 // if (globalLocId == null) {
4249 // Error("Method lattice does not define global variable location at "
4250 // + generateErrorMessage(md.getClassDesc(), nn));
4252 // loc.addLocation(new Location(md, globalLocId));
4254 // Location fieldLoc = (Location) fd.getType().getExtension();
4255 // loc.addLocation(fieldLoc);
4261 getFlowGraph(md).createNewFlowNode(base);
4267 private NTuple<Descriptor> analyzeFlowFieldAccessNode(MethodDescriptor md, SymbolTable nametable,
4268 FieldAccessNode fan, NodeTupleSet nodeSet, NTuple<Descriptor> base,
4269 NodeTupleSet implicitFlowTupleSet, boolean isLHS) {
4271 ExpressionNode left = fan.getExpression();
4272 TypeDescriptor ltd = left.getType();
4273 FieldDescriptor fd = fan.getField();
4275 String varName = null;
4276 if (left.kind() == Kind.NameNode) {
4277 NameDescriptor nd = ((NameNode) left).getName();
4278 varName = nd.toString();
4281 if (ltd.isClassNameRef() || (varName != null && varName.equals("this"))) {
4282 // using a class name directly or access using this
4283 if (fd.isStatic() && fd.isFinal()) {
4288 NodeTupleSet idxNodeTupleSet = new NodeTupleSet();
4290 if (left instanceof ArrayAccessNode) {
4292 ArrayAccessNode aan = (ArrayAccessNode) left;
4293 left = aan.getExpression();
4294 analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, base,
4295 implicitFlowTupleSet, isLHS);
4297 nodeSet.addTupleSet(idxNodeTupleSet);
4300 analyzeFlowExpressionNode(md, nametable, left, nodeSet, base, implicitFlowTupleSet, isLHS);
4303 // in this case, field is TOP location
4307 NTuple<Descriptor> flowFieldTuple = new NTuple<Descriptor>(base.toList());
4309 if (!left.getType().isPrimitive()) {
4311 if (!fd.getSymbol().equals("length")) {
4312 // array.length access, just have the location of the array
4313 flowFieldTuple.add(fd);
4314 nodeSet.removeTuple(base);
4318 getFlowGraph(md).createNewFlowNode(flowFieldTuple);
4321 for (Iterator<NTuple<Descriptor>> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) {
4322 NTuple<Descriptor> idxTuple = idxIter.next();
4323 getFlowGraph(md).addValueFlowEdge(idxTuple, flowFieldTuple);
4326 return flowFieldTuple;
4332 private void debug_printTreeNode(TreeNode tn) {
4334 System.out.println("DEBUG: " + tn.printNode(0) + " line#=" + tn.getNumLine());
4338 private void analyzeFlowAssignmentNode(MethodDescriptor md, SymbolTable nametable,
4339 AssignmentNode an, NodeTupleSet nodeSet, NTuple<Descriptor> base,
4340 NodeTupleSet implicitFlowTupleSet) {
4342 NodeTupleSet nodeSetRHS = new NodeTupleSet();
4343 NodeTupleSet nodeSetLHS = new NodeTupleSet();
4345 boolean postinc = true;
4346 if (an.getOperation().getBaseOp() == null
4347 || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
4348 .getBaseOp().getOp() != Operation.POSTDEC)) {
4351 // if LHS is array access node, need to capture value flows between an array
4352 // and its index value
4353 analyzeFlowExpressionNode(md, nametable, an.getDest(), nodeSetLHS, null, implicitFlowTupleSet,
4357 // analyze value flows of rhs expression
4358 analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null, implicitFlowTupleSet,
4361 // System.out.println("-analyzeFlowAssignmentNode=" + an.printNode(0));
4362 // System.out.println("-nodeSetLHS=" + nodeSetLHS);
4363 // System.out.println("-nodeSetRHS=" + nodeSetRHS);
4364 // System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet);
4365 // System.out.println("-");
4367 if (an.getOperation().getOp() >= 2 && an.getOperation().getOp() <= 12) {
4368 // if assignment contains OP+EQ operator, creates edges from LHS to LHS
4370 for (Iterator<NTuple<Descriptor>> iter = nodeSetLHS.iterator(); iter.hasNext();) {
4371 NTuple<Descriptor> fromTuple = iter.next();
4372 for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
4373 NTuple<Descriptor> toTuple = iter2.next();
4374 addFlowGraphEdge(md, fromTuple, toTuple);
4379 // creates edges from RHS to LHS
4380 NTuple<Descriptor> interTuple = null;
4381 if (nodeSetRHS.size() > 1) {
4382 interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
4385 for (Iterator<NTuple<Descriptor>> iter = nodeSetRHS.iterator(); iter.hasNext();) {
4386 NTuple<Descriptor> fromTuple = iter.next();
4387 for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
4388 NTuple<Descriptor> toTuple = iter2.next();
4389 addFlowGraphEdge(md, fromTuple, interTuple, toTuple);
4393 // creates edges from implicitFlowTupleSet to LHS
4394 for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
4395 NTuple<Descriptor> fromTuple = iter.next();
4396 for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
4397 NTuple<Descriptor> toTuple = iter2.next();
4398 addFlowGraphEdge(md, fromTuple, toTuple);
4405 for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
4406 NTuple<Descriptor> tuple = iter2.next();
4407 addFlowGraphEdge(md, tuple, tuple);
4410 // creates edges from implicitFlowTupleSet to LHS
4411 for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
4412 NTuple<Descriptor> fromTuple = iter.next();
4413 for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
4414 NTuple<Descriptor> toTuple = iter2.next();
4415 addFlowGraphEdge(md, fromTuple, toTuple);
4421 if (nodeSet != null) {
4422 nodeSet.addTupleSet(nodeSetLHS);
4426 public FlowGraph getFlowGraph(MethodDescriptor md) {
4427 return mapMethodDescriptorToFlowGraph.get(md);
4430 private boolean addFlowGraphEdge(MethodDescriptor md, NTuple<Descriptor> from,
4431 NTuple<Descriptor> to) {
4432 FlowGraph graph = getFlowGraph(md);
4433 graph.addValueFlowEdge(from, to);
4437 private void addFlowGraphEdge(MethodDescriptor md, NTuple<Descriptor> from,
4438 NTuple<Descriptor> inter, NTuple<Descriptor> to) {
4440 FlowGraph graph = getFlowGraph(md);
4442 if (inter != null) {
4443 graph.addValueFlowEdge(from, inter);
4444 graph.addValueFlowEdge(inter, to);
4446 graph.addValueFlowEdge(from, to);
4451 public void writeInferredLatticeDotFile(ClassDescriptor cd, HierarchyGraph simpleHierarchyGraph,
4452 SSJavaLattice<String> locOrder, String nameSuffix) {
4453 writeInferredLatticeDotFile(cd, null, simpleHierarchyGraph, locOrder, nameSuffix);
4456 public void writeInferredLatticeDotFile(ClassDescriptor cd, MethodDescriptor md,
4457 HierarchyGraph simpleHierarchyGraph, SSJavaLattice<String> locOrder, String nameSuffix) {
4459 String fileName = "lattice_";
4462 cd.getSymbol().replaceAll("[\\W_]", "") + "_" + md.toString().replaceAll("[\\W_]", "");
4464 fileName += cd.getSymbol().replaceAll("[\\W_]", "");
4467 fileName += nameSuffix;
4469 Set<Pair<String, String>> pairSet = locOrder.getOrderingPairSet();
4471 Set<String> addedLocSet = new HashSet<String>();
4473 if (pairSet.size() > 0) {
4475 BufferedWriter bw = new BufferedWriter(new FileWriter(fileName + ".dot"));
4477 bw.write("digraph " + fileName + " {\n");
4479 for (Iterator iterator = pairSet.iterator(); iterator.hasNext();) {
4480 // pair is in the form of <higher, lower>
4481 Pair<String, String> pair = (Pair<String, String>) iterator.next();
4483 String highLocId = pair.getFirst();
4484 String lowLocId = pair.getSecond();
4486 if (!addedLocSet.contains(highLocId)) {
4487 addedLocSet.add(highLocId);
4488 drawNode(bw, locOrder, simpleHierarchyGraph, highLocId);
4491 if (!addedLocSet.contains(lowLocId)) {
4492 addedLocSet.add(lowLocId);
4493 drawNode(bw, locOrder, simpleHierarchyGraph, lowLocId);
4496 bw.write(highLocId + " -> " + lowLocId + ";\n");
4501 } catch (IOException e) {
4502 e.printStackTrace();
4509 private String convertMergeSetToString(HierarchyGraph graph, Set<HNode> mergeSet) {
4511 for (Iterator iterator = mergeSet.iterator(); iterator.hasNext();) {
4512 HNode merged = (HNode) iterator.next();
4513 if (merged.isMergeNode()) {
4514 str += convertMergeSetToString(graph, graph.getMapHNodetoMergeSet().get(merged));
4516 str += " " + merged.getName();
4522 private void drawNode(BufferedWriter bw, SSJavaLattice<String> lattice, HierarchyGraph graph,
4523 String locName) throws IOException {
4525 HNode node = graph.getHNode(locName);
4532 if (lattice.isSharedLoc(locName)) {
4533 prettyStr = locName + "*";
4535 prettyStr = locName;
4538 if (node.isMergeNode()) {
4539 Set<HNode> mergeSet = graph.getMapHNodetoMergeSet().get(node);
4540 prettyStr += ":" + convertMergeSetToString(graph, mergeSet);
4542 bw.write(locName + " [label=\"" + prettyStr + "\"]" + ";\n");
4545 public void _debug_printGraph() {
4546 Set<MethodDescriptor> keySet = mapMethodDescriptorToFlowGraph.keySet();
4548 for (Iterator<MethodDescriptor> iterator = keySet.iterator(); iterator.hasNext();) {
4549 MethodDescriptor md = (MethodDescriptor) iterator.next();
4550 FlowGraph fg = mapMethodDescriptorToFlowGraph.get(md);
4553 } catch (IOException e) {
4554 e.printStackTrace();
4562 class CyclicFlowException extends Exception {
4566 class InterDescriptor extends Descriptor {
4568 public InterDescriptor(String name) {