changes.
[IRC.git] / Robust / src / Analysis / SSJava / LocationInference.java
1 package Analysis.SSJava;
2
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;
16 import java.util.Map;
17 import java.util.Set;
18 import java.util.Stack;
19 import java.util.Vector;
20
21 import IR.ClassDescriptor;
22 import IR.Descriptor;
23 import IR.FieldDescriptor;
24 import IR.MethodDescriptor;
25 import IR.NameDescriptor;
26 import IR.Operation;
27 import IR.State;
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;
42 import IR.Tree.Kind;
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;
54 import Util.Pair;
55
56 public class LocationInference {
57
58   State state;
59   SSJavaAnalysis ssjava;
60
61   List<ClassDescriptor> temp_toanalyzeList;
62   List<MethodDescriptor> temp_toanalyzeMethodList;
63   Map<MethodDescriptor, FlowGraph> mapMethodDescriptorToFlowGraph;
64
65   LinkedList<MethodDescriptor> toanalyze_methodDescList;
66
67   // map a method descriptor to its set of parameter descriptors
68   Map<MethodDescriptor, Set<Descriptor>> mapMethodDescriptorToParamDescSet;
69
70   // keep current descriptors to visit in fixed-point interprocedural analysis,
71   private Stack<MethodDescriptor> methodDescriptorsToVisitStack;
72
73   // map a class descriptor to a field lattice
74   private Map<ClassDescriptor, SSJavaLattice<String>> cd2lattice;
75
76   // map a method descriptor to a method lattice
77   private Map<MethodDescriptor, SSJavaLattice<String>> md2lattice;
78
79   // map a method/class descriptor to a hierarchy graph
80   private Map<Descriptor, HierarchyGraph> mapDescriptorToHierarchyGraph;
81
82   // map a method/class descriptor to a skeleton hierarchy graph
83   private Map<Descriptor, HierarchyGraph> mapDescriptorToSkeletonHierarchyGraph;
84
85   private Map<Descriptor, HierarchyGraph> mapDescriptorToSimpleHierarchyGraph;
86
87   // map a method/class descriptor to a skeleton hierarchy graph with combination nodes
88   private Map<Descriptor, HierarchyGraph> mapDescriptorToCombineSkeletonHierarchyGraph;
89
90   // map a descriptor to a simple lattice
91   private Map<Descriptor, SSJavaLattice<String>> mapDescriptorToSimpleLattice;
92
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;
96
97   private Map<MethodInvokeNode, Map<Integer, NTuple<Descriptor>>> mapMethodInvokeNodeToArgIdxMap;
98
99   private Map<MethodInvokeNode, NTuple<Descriptor>> mapMethodInvokeNodeToBaseTuple;
100
101   private Map<MethodDescriptor, MethodLocationInfo> mapMethodDescToMethodLocationInfo;
102
103   private Map<ClassDescriptor, LocationInfo> mapClassToLocationInfo;
104
105   private Map<MethodDescriptor, Set<MethodDescriptor>> mapMethodToCalleeSet;
106
107   private Map<MethodDescriptor, Set<FlowNode>> mapMethodDescToParamNodeFlowsToReturnValue;
108
109   private Map<String, Vector<String>> mapFileNameToLineVector;
110
111   private Map<Descriptor, Integer> mapDescToDefinitionLine;
112
113   private Map<Descriptor, LocationSummary> mapDescToLocationSummary;
114
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, GlobalFlowGraph> mapMethodDescriptorToSubGlobalFlowGraph;
118
119   private Map<MethodInvokeNode, Map<NTuple<Descriptor>, NTuple<Descriptor>>> mapMethodInvokeNodeToMapCallerArgToCalleeArg;
120
121   public static final String GLOBALLOC = "GLOBALLOC";
122
123   public static final String TOPLOC = "TOPLOC";
124
125   public static final String INTERLOC = "INTERLOC";
126
127   public static final Descriptor GLOBALDESC = new NameDescriptor(GLOBALLOC);
128
129   public static final Descriptor TOPDESC = new NameDescriptor(TOPLOC);
130
131   public static String newline = System.getProperty("line.separator");
132
133   LocationInfo curMethodInfo;
134
135   boolean debug = true;
136
137   private static int locSeed = 0;
138
139   public LocationInference(SSJavaAnalysis ssjava, State state) {
140     this.ssjava = ssjava;
141     this.state = state;
142     this.temp_toanalyzeList = new ArrayList<ClassDescriptor>();
143     this.temp_toanalyzeMethodList = new ArrayList<MethodDescriptor>();
144     this.mapMethodDescriptorToFlowGraph = new HashMap<MethodDescriptor, FlowGraph>();
145     this.cd2lattice = new HashMap<ClassDescriptor, SSJavaLattice<String>>();
146     this.md2lattice = new HashMap<MethodDescriptor, SSJavaLattice<String>>();
147     this.methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
148     this.mapMethodDescriptorToMethodInvokeNodeSet =
149         new HashMap<MethodDescriptor, Set<MethodInvokeNode>>();
150     this.mapMethodInvokeNodeToArgIdxMap =
151         new HashMap<MethodInvokeNode, Map<Integer, NTuple<Descriptor>>>();
152     this.mapMethodDescToMethodLocationInfo = new HashMap<MethodDescriptor, MethodLocationInfo>();
153     this.mapMethodToCalleeSet = new HashMap<MethodDescriptor, Set<MethodDescriptor>>();
154     this.mapClassToLocationInfo = new HashMap<ClassDescriptor, LocationInfo>();
155
156     this.mapFileNameToLineVector = new HashMap<String, Vector<String>>();
157     this.mapDescToDefinitionLine = new HashMap<Descriptor, Integer>();
158     this.mapMethodDescToParamNodeFlowsToReturnValue =
159         new HashMap<MethodDescriptor, Set<FlowNode>>();
160
161     this.mapDescriptorToHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
162     this.mapMethodInvokeNodeToBaseTuple = new HashMap<MethodInvokeNode, NTuple<Descriptor>>();
163
164     this.mapDescriptorToSkeletonHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
165     this.mapDescriptorToCombineSkeletonHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
166     this.mapDescriptorToSimpleHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
167
168     this.mapDescriptorToSimpleLattice = new HashMap<Descriptor, SSJavaLattice<String>>();
169
170     this.mapDescToLocationSummary = new HashMap<Descriptor, LocationSummary>();
171
172     this.mapMethodDescriptorToSubGlobalFlowGraph = new HashMap<MethodDescriptor, GlobalFlowGraph>();
173
174     this.mapMethodInvokeNodeToMapCallerArgToCalleeArg =
175         new HashMap<MethodInvokeNode, Map<NTuple<Descriptor>, NTuple<Descriptor>>>();
176
177   }
178
179   public void setupToAnalyze() {
180     SymbolTable classtable = state.getClassSymbolTable();
181     temp_toanalyzeList.clear();
182     temp_toanalyzeList.addAll(classtable.getValueSet());
183     // Collections.sort(toanalyzeList, new Comparator<ClassDescriptor>() {
184     // public int compare(ClassDescriptor o1, ClassDescriptor o2) {
185     // return o1.getClassName().compareToIgnoreCase(o2.getClassName());
186     // }
187     // });
188   }
189
190   public void setupToAnalazeMethod(ClassDescriptor cd) {
191
192     SymbolTable methodtable = cd.getMethodTable();
193     temp_toanalyzeMethodList.clear();
194     temp_toanalyzeMethodList.addAll(methodtable.getValueSet());
195     Collections.sort(temp_toanalyzeMethodList, new Comparator<MethodDescriptor>() {
196       public int compare(MethodDescriptor o1, MethodDescriptor o2) {
197         return o1.getSymbol().compareToIgnoreCase(o2.getSymbol());
198       }
199     });
200   }
201
202   public boolean toAnalyzeMethodIsEmpty() {
203     return temp_toanalyzeMethodList.isEmpty();
204   }
205
206   public boolean toAnalyzeIsEmpty() {
207     return temp_toanalyzeList.isEmpty();
208   }
209
210   public ClassDescriptor toAnalyzeNext() {
211     return temp_toanalyzeList.remove(0);
212   }
213
214   public MethodDescriptor toAnalyzeMethodNext() {
215     return temp_toanalyzeMethodList.remove(0);
216   }
217
218   public void inference() {
219
220     // 1) construct value flow graph
221     constructFlowGraph();
222
223     assignCompositeLocation();
224
225     // constructGlobalFlowGraph();
226
227     System.exit(0);
228
229     constructHierarchyGraph();
230
231     debug_writeHierarchyDotFiles();
232
233     simplifyHierarchyGraph();
234
235     debug_writeSimpleHierarchyDotFiles();
236
237     constructSkeletonHierarchyGraph();
238
239     debug_writeSkeletonHierarchyDotFiles();
240
241     insertCombinationNodes();
242
243     debug_writeSkeletonCombinationHierarchyDotFiles();
244
245     buildLattice();
246
247     debug_writeLattices();
248
249     generateMethodSummary();
250
251     System.exit(0);
252
253     // 2) construct lattices
254     inferLattices();
255
256     // simplifyLattices();
257
258     // 3) check properties
259     checkLattices();
260
261     // calculate RETURNLOC,PCLOC
262     calculateExtraLocations();
263
264     debug_writeLatticeDotFile();
265
266     // 4) generate annotated source codes
267     generateAnnoatedCode();
268
269   }
270
271   public Map<NTuple<Descriptor>, NTuple<Descriptor>> getMapCallerArgToCalleeParam(
272       MethodInvokeNode min) {
273
274     if (!mapMethodInvokeNodeToMapCallerArgToCalleeArg.containsKey(min)) {
275       mapMethodInvokeNodeToMapCallerArgToCalleeArg.put(min,
276           new HashMap<NTuple<Descriptor>, NTuple<Descriptor>>());
277     }
278
279     return mapMethodInvokeNodeToMapCallerArgToCalleeArg.get(min);
280   }
281
282   public void addMapCallerArgToCalleeParam(MethodInvokeNode min, NTuple<Descriptor> callerArg,
283       NTuple<Descriptor> calleeParam) {
284     getMapCallerArgToCalleeParam(min).put(callerArg, calleeParam);
285   }
286
287   private void assignCompositeLocation() {
288     calculateGlobalValueFlowCompositeLocation();
289     translateCompositeLocationAssignmentToFlowGraph();
290     _debug_printGraph();
291   }
292
293   private void translateCompositeLocationAssignmentToFlowGraph() {
294
295     MethodDescriptor methodEventLoopDesc = ssjava.getMethodContainingSSJavaLoop();
296     translateCompositeLocationAssignmentToFlowGraph(methodEventLoopDesc);
297
298   }
299
300   private void translateCompositeLocationAssignmentToFlowGraph(MethodDescriptor mdCaller) {
301
302     System.out.println("\n#translateCompositeLocationAssignmentToFlowGraph=" + mdCaller);
303
304     // First, assign a composite location to a node in the flow graph
305     GlobalFlowGraph callerGlobalFlowGraph = getSubGlobalFlowGraph(mdCaller);
306
307     FlowGraph callerFlowGraph = getFlowGraph(mdCaller);
308     Map<Location, CompositeLocation> callerMapLocToCompLoc =
309         callerGlobalFlowGraph.getMapLocationToInferCompositeLocation();
310     Set<Location> methodLocSet = callerMapLocToCompLoc.keySet();
311     for (Iterator iterator = methodLocSet.iterator(); iterator.hasNext();) {
312       Location methodLoc = (Location) iterator.next();
313       if (methodLoc.getDescriptor().equals(mdCaller)) {
314         CompositeLocation inferCompLoc = callerMapLocToCompLoc.get(methodLoc);
315         assignCompositeLocationToFlowGraph(callerFlowGraph, methodLoc, inferCompLoc);
316       }
317     }
318
319     Set<MethodInvokeNode> minSet = mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller);
320
321     Set<MethodDescriptor> calleeSet = new HashSet<MethodDescriptor>();
322     for (Iterator iterator = minSet.iterator(); iterator.hasNext();) {
323       MethodInvokeNode min = (MethodInvokeNode) iterator.next();
324       // need to translate a composite location that is started with the base
325       // tuple of 'min'.
326       if (mapMethodInvokeNodeToBaseTuple.get(min) != null) {
327         // if mapMethodInvokeNodeToBaseTuple doesn't have a mapping
328         // it means that the corresponding callee method does not cause any
329         // flows
330         translateMapLocationToInferCompositeLocationToCalleeGraph(callerGlobalFlowGraph, min);
331       }
332       calleeSet.add(min.getMethod());
333     }
334
335     for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) {
336       MethodDescriptor callee = (MethodDescriptor) iterator.next();
337       translateCompositeLocationAssignmentToFlowGraph(callee);
338     }
339
340   }
341
342   public void assignCompositeLocationToFlowGraph(FlowGraph flowGraph, Location loc,
343       CompositeLocation inferCompLoc) {
344     Descriptor localDesc = loc.getLocDescriptor();
345
346     Set<FlowNode> nodeSet = flowGraph.getNodeSet();
347     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
348       FlowNode node = (FlowNode) iterator.next();
349       if (node.getDescTuple().startsWith(localDesc)) {
350         // need to assign the inferred composite location to this node
351         CompositeLocation newCompLoc = generateCompositeLocation(node.getDescTuple(), inferCompLoc);
352         node.setCompositeLocation(newCompLoc);
353         System.out.println("SET Node=" + node + "  inferCompLoc=" + newCompLoc);
354       }
355     }
356   }
357
358   private CompositeLocation generateCompositeLocation(NTuple<Descriptor> nodeDescTuple,
359       CompositeLocation inferCompLoc) {
360
361     System.out.println("generateCompositeLocation=" + nodeDescTuple + " with inferCompLoc="
362         + inferCompLoc);
363
364     CompositeLocation newCompLoc = new CompositeLocation();
365     for (int i = 0; i < inferCompLoc.getSize(); i++) {
366       newCompLoc.addLocation(inferCompLoc.get(i));
367     }
368
369     Descriptor lastDescOfPrefix = nodeDescTuple.get(0);
370     Descriptor enclosingDescriptor;
371     if (lastDescOfPrefix instanceof InterDescriptor) {
372       enclosingDescriptor = null;
373     } else {
374       enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc();
375     }
376
377     for (int i = 1; i < nodeDescTuple.size(); i++) {
378       Descriptor desc = nodeDescTuple.get(i);
379       Location locElement = new Location(enclosingDescriptor, desc);
380       newCompLoc.addLocation(locElement);
381
382       enclosingDescriptor = ((FieldDescriptor) desc).getClassDescriptor();
383     }
384
385     return newCompLoc;
386   }
387
388   private void translateMapLocationToInferCompositeLocationToCalleeGraph(
389       GlobalFlowGraph callerGraph, MethodInvokeNode min) {
390
391     MethodDescriptor mdCallee = min.getMethod();
392     MethodDescriptor mdCaller = callerGraph.getMethodDescriptor();
393     Map<Location, CompositeLocation> callerMapLocToCompLoc =
394         callerGraph.getMapLocationToInferCompositeLocation();
395
396     FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
397     GlobalFlowGraph calleeGlobalGraph = getSubGlobalFlowGraph(mdCallee);
398
399     NTuple<Location> baseLocTuple =
400         translateToLocTuple(mdCaller, mapMethodInvokeNodeToBaseTuple.get(min));
401
402     System.out.println("-translate caller infer composite loc to callee=" + mdCallee);
403     Set<Location> keySet = callerMapLocToCompLoc.keySet();
404     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
405       Location key = (Location) iterator.next();
406       CompositeLocation callerCompLoc = callerMapLocToCompLoc.get(key);
407
408       if (!key.getDescriptor().equals(mdCaller)
409           && callerCompLoc.getTuple().startsWith(baseLocTuple)) {
410         // need to translate to the callee side
411         // System.out.println("need to translate callerCompLoc=" + callerCompLoc +
412         // " with baseTuple="
413         // + baseLocTuple);
414         // TODO
415         CompositeLocation newCalleeCompLoc =
416             translateCompositeLocationToCallee(callerCompLoc, baseLocTuple, mdCallee);
417         calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, newCalleeCompLoc);
418         System.out.println("---callee loc=" + key + "  newCalleeCompLoc=" + newCalleeCompLoc);
419       }
420     }
421
422     // If the location of an argument has a composite location
423     // need to assign a proper composite location to the corresponding callee parameter
424     System.out.println("-translate arg composite location to callee param:");
425     Map<Integer, NTuple<Descriptor>> mapIdxToArgTuple = mapMethodInvokeNodeToArgIdxMap.get(min);
426     Set<Integer> idxSet = mapIdxToArgTuple.keySet();
427     for (Iterator iterator = idxSet.iterator(); iterator.hasNext();) {
428       Integer idx = (Integer) iterator.next();
429
430       if (idx == 0 && !min.getMethod().isStatic()) {
431         continue;
432       }
433
434       NTuple<Descriptor> argTuple = mapIdxToArgTuple.get(idx);
435
436       // check if an arg tuple has been already assigned to a composite location
437       NTuple<Location> argLocTuple = translateToLocTuple(mdCaller, argTuple);
438       Location argLocalLoc = argLocTuple.get(0);
439
440       // if (!isPrimitiveType(argTuple)) {
441       if (callerMapLocToCompLoc.containsKey(argLocalLoc)) {
442
443         CompositeLocation callerCompLoc = callerMapLocToCompLoc.get(argLocalLoc);
444         for (int i = 1; i < argLocTuple.size(); i++) {
445           callerCompLoc.addLocation(argLocTuple.get(i));
446         }
447
448         if (callerCompLoc.getTuple().startsWith(baseLocTuple)) {
449
450           FlowNode calleeParamFlowNode = calleeFlowGraph.getParamFlowNode(idx);
451           NTuple<Descriptor> calleeParamDescTuple = calleeParamFlowNode.getDescTuple();
452           NTuple<Location> calleeParamLocTuple =
453               translateToLocTuple(mdCallee, calleeParamDescTuple);
454
455           CompositeLocation newCalleeCompLoc =
456               translateCompositeLocationToCallee(callerCompLoc, baseLocTuple, mdCallee);
457
458           calleeGlobalGraph.addMapLocationToInferCompositeLocation(calleeParamLocTuple.get(0),
459               newCalleeCompLoc);
460
461           System.out.println("###need to assign composite location to=" + calleeParamDescTuple
462               + " with baseTuple=" + baseLocTuple);
463           System.out.println("---newCalleeCompLoc=" + newCalleeCompLoc);
464         }
465
466       }
467
468     }
469
470   }
471
472   private boolean isPrimitiveType(NTuple<Descriptor> argTuple) {
473
474     Descriptor lastDesc = argTuple.get(argTuple.size() - 1);
475
476     if (lastDesc instanceof FieldDescriptor) {
477       return ((FieldDescriptor) lastDesc).getType().isPrimitive();
478     } else if (lastDesc instanceof VarDescriptor) {
479       return ((VarDescriptor) lastDesc).getType().isPrimitive();
480     }
481
482     return true;
483   }
484
485   private CompositeLocation translateCompositeLocationToCallee(CompositeLocation callerCompLoc,
486       NTuple<Location> baseLocTuple, MethodDescriptor mdCallee) {
487
488     CompositeLocation newCalleeCompLoc = new CompositeLocation();
489
490     // replace the last element of the caller compLoc with the 'this' location of the callee
491     for (int i = 0; i < baseLocTuple.size() - 1; i++) {
492       newCalleeCompLoc.addLocation(baseLocTuple.get(i));
493     }
494
495     Location calleeThisLoc = new Location(mdCallee, mdCallee.getThis());
496     newCalleeCompLoc.addLocation(calleeThisLoc);
497
498     for (int i = baseLocTuple.size(); i < callerCompLoc.getSize(); i++) {
499       newCalleeCompLoc.addLocation(callerCompLoc.get(i));
500     }
501
502     return newCalleeCompLoc;
503
504   }
505
506   private void constructGlobalFlowGraph() {
507
508     System.out.println("");
509     LinkedList<MethodDescriptor> methodDescList =
510         (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
511
512     System.out.println("@@@methodDescList=" + methodDescList);
513     // System.exit(0);
514
515     while (!methodDescList.isEmpty()) {
516       MethodDescriptor md = methodDescList.removeLast();
517       if (state.SSJAVADEBUG) {
518         System.out.println();
519         System.out.println("SSJAVA: Constructing a global flow graph: " + md);
520
521         FlowGraph flowGraph = getFlowGraph(md);
522         FlowGraph subGlobalFlowGraph = flowGraph.clone();
523
524         // mapMethodDescriptorToSubGlobalFlowGraph.put(md, subGlobalFlowGraph);
525
526         // addValueFlowsFromCalleeSubGlobalFlowGraph(md, subGlobalFlowGraph);
527
528         // try {
529         // subGlobalFlowGraph.writeGraph("_SUBGLOBAL");
530         // } catch (IOException e) {
531         // e.printStackTrace();
532         // }
533         // FlowGraph fg = new FlowGraph(md, mapParamDescToIdx);
534         // mapMethodDescriptorToFlowGraph.put(md, fg);
535         // analyzeMethodBody(md.getClassDesc(), md);
536       }
537
538     }
539
540     // DEBUG: write a global flow graph
541     MethodDescriptor mdContainingSSJavaLoop = ssjava.getMethodContainingSSJavaLoop();
542     // FlowGraph globalFlowGraph =
543     // getSubGlobalFlowGraph(mdContainingSSJavaLoop);
544     // System.out.println("GLOBAL NODE SET=" + globalFlowGraph.getNodeSet());
545     // assignCompositeLocation(globalFlowGraph);
546     // try {
547     // globalFlowGraph.writeGraph("_GLOBAL");
548     // } catch (IOException e) {
549     // e.printStackTrace();
550     // }
551     // _debug_printGraph();
552
553   }
554
555   private void calculateGlobalValueFlowCompositeLocation() {
556
557     System.out.println("SSJAVA: Calculate composite locations in the global value flow graph");
558     MethodDescriptor methodDescEventLoop = ssjava.getMethodContainingSSJavaLoop();
559     GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(methodDescEventLoop);
560
561     Set<NTuple<Location>> prefixSet = new HashSet<NTuple<Location>>();
562
563     Set<GlobalFlowNode> nodeSet = globalFlowGraph.getNodeSet();
564
565     next: for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
566       GlobalFlowNode node = (GlobalFlowNode) iterator.next();
567       Set<GlobalFlowNode> incomingNodeSet = globalFlowGraph.getIncomingNodeSet(node);
568       List<NTuple<Location>> prefixList = calculatePrefixList(globalFlowGraph, node);
569       Set<GlobalFlowNode> reachNodeSet = globalFlowGraph.getReachableNodeSetFrom(node);
570
571       // System.out.println("node=" + node + "    inNodeSet=" + incomingNodeSet
572       // + "   reachableNodeSet=" + reachNodeSet);
573
574       for (int i = 0; i < prefixList.size(); i++) {
575         NTuple<Location> curPrefix = prefixList.get(i);
576         Set<NTuple<Location>> reachableCommonPrefixSet = new HashSet<NTuple<Location>>();
577
578         for (Iterator iterator2 = reachNodeSet.iterator(); iterator2.hasNext();) {
579           GlobalFlowNode reachNode = (GlobalFlowNode) iterator2.next();
580           if (reachNode.getLocTuple().startsWith(curPrefix)) {
581             reachableCommonPrefixSet.add(reachNode.getLocTuple());
582           }
583         }
584
585         if (!reachableCommonPrefixSet.isEmpty()) {
586
587           // TODO
588           if (!node.getLocTuple().startsWith(curPrefix.get(0))) {
589             CompositeLocation newCompLoc = generateCompositeLocation(curPrefix);
590             System.out.println("NEED TO ASSIGN COMP LOC TO " + node + " with prefix=" + curPrefix);
591             System.out.println("- newCompLoc=" + newCompLoc);
592
593             Location targetLocalLoc = node.getLocTuple().get(0);
594             globalFlowGraph.addMapLocationToInferCompositeLocation(targetLocalLoc, newCompLoc);
595
596             continue next;
597           }
598
599         }
600
601       }
602
603     }
604     // Set<GlobalFlowNode> inNodeSet =
605     // graph.getIncomingNodeSetWithPrefix(prefix);
606     // System.out.println("inNodeSet=" + inNodeSet + "  from=" + node);
607   }
608
609   private void assignCompositeLocation(CompositeLocation compLocPrefix, GlobalFlowNode node) {
610     CompositeLocation newCompLoc = compLocPrefix.clone();
611     NTuple<Location> locTuple = node.getLocTuple();
612     for (int i = 1; i < locTuple.size(); i++) {
613       newCompLoc.addLocation(locTuple.get(i));
614     }
615     node.setInferCompositeLocation(newCompLoc);
616   }
617
618   private List<NTuple<Location>> calculatePrefixList(GlobalFlowGraph graph, GlobalFlowNode node) {
619
620     System.out.println("\n##### calculatePrefixList=" + node);
621
622     Set<GlobalFlowNode> incomingNodeSet = graph.getIncomingNodeSet(node);
623
624     List<NTuple<Location>> prefixList = new ArrayList<NTuple<Location>>();
625
626     for (Iterator iterator = incomingNodeSet.iterator(); iterator.hasNext();) {
627       GlobalFlowNode inNode = (GlobalFlowNode) iterator.next();
628       NTuple<Location> inNodeTuple = inNode.getLocTuple();
629
630       for (int i = 1; i < inNodeTuple.size(); i++) {
631         NTuple<Location> prefix = inNodeTuple.subList(0, i);
632         if (!prefixList.contains(prefix)) {
633           prefixList.add(prefix);
634         }
635       }
636     }
637
638     Collections.sort(prefixList, new Comparator<NTuple<Location>>() {
639       public int compare(NTuple<Location> arg0, NTuple<Location> arg1) {
640         int s0 = arg0.size();
641         int s1 = arg1.size();
642         if (s0 > s1) {
643           return -1;
644         } else if (s0 == s1) {
645           return 0;
646         } else {
647           return 1;
648         }
649       }
650     });
651     return prefixList;
652   }
653
654   private GlobalFlowGraph constructSubGlobalFlowGraph(FlowGraph flowGraph) {
655
656     MethodDescriptor md = flowGraph.getMethodDescriptor();
657
658     GlobalFlowGraph globalGraph = new GlobalFlowGraph(md);
659
660     // Set<FlowNode> nodeSet = flowGraph.getNodeSet();
661     Set<FlowEdge> edgeSet = flowGraph.getEdgeSet();
662
663     for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) {
664
665       FlowEdge edge = (FlowEdge) iterator.next();
666       NTuple<Descriptor> srcDescTuple = edge.getInitTuple();
667       NTuple<Descriptor> dstDescTuple = edge.getEndTuple();
668
669       // here only keep the first element(method location) of the descriptor
670       // tuple
671       NTuple<Location> srcLocTuple = translateToLocTuple(md, srcDescTuple);
672       // Location srcMethodLoc = srcLocTuple.get(0);
673       // Descriptor srcVarDesc = srcMethodLoc.getLocDescriptor();
674       // // if (flowGraph.isParamDesc(srcVarDesc) &&
675       // (!srcVarDesc.equals(md.getThis()))) {
676       // if (!srcVarDesc.equals(md.getThis())) {
677       // srcLocTuple = new NTuple<Location>();
678       // Location loc = new Location(md, srcVarDesc);
679       // srcLocTuple.add(loc);
680       // }
681       //
682       NTuple<Location> dstLocTuple = translateToLocTuple(md, dstDescTuple);
683       // Location dstMethodLoc = dstLocTuple.get(0);
684       // Descriptor dstVarDesc = dstMethodLoc.getLocDescriptor();
685       // if (!dstVarDesc.equals(md.getThis())) {
686       // dstLocTuple = new NTuple<Location>();
687       // Location loc = new Location(md, dstVarDesc);
688       // dstLocTuple.add(loc);
689       // }
690
691       globalGraph.addValueFlowEdge(srcLocTuple, dstLocTuple);
692
693     }
694
695     return globalGraph;
696   }
697
698   private NTuple<Location> translateToLocTuple(MethodDescriptor md, NTuple<Descriptor> descTuple) {
699
700     NTuple<Location> locTuple = new NTuple<Location>();
701
702     Descriptor enclosingDesc = md;
703     System.out.println("md=" + md + "  descTuple=" + descTuple);
704     for (int i = 0; i < descTuple.size(); i++) {
705       Descriptor desc = descTuple.get(i);
706
707       Location loc = new Location(enclosingDesc, desc);
708       locTuple.add(loc);
709
710       if (desc instanceof VarDescriptor) {
711         enclosingDesc = ((VarDescriptor) desc).getType().getClassDesc();
712       } else if (desc instanceof FieldDescriptor) {
713         enclosingDesc = ((FieldDescriptor) desc).getType().getClassDesc();
714       } else {
715         // TODO: inter descriptor case
716         enclosingDesc = desc;
717       }
718
719     }
720
721     return locTuple;
722
723   }
724
725   private void addValueFlowsFromCalleeSubGlobalFlowGraph(MethodDescriptor mdCaller,
726       GlobalFlowGraph subGlobalFlowGraph) {
727
728     // the transformation for a call site propagates flows through parameters
729     // if the method is virtual, it also grab all relations from any possible
730     // callees
731
732     Set<MethodInvokeNode> setMethodInvokeNode = getMethodInvokeNodeSet(mdCaller);
733
734     for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) {
735       MethodInvokeNode min = (MethodInvokeNode) iterator.next();
736       MethodDescriptor mdCallee = min.getMethod();
737       Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
738       if (mdCallee.isStatic()) {
739         setPossibleCallees.add(mdCallee);
740       } else {
741         Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getMethods(mdCallee);
742         // removes method descriptors that are not invoked by the caller
743         calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller));
744         setPossibleCallees.addAll(calleeSet);
745       }
746
747       for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
748         MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
749         propagateValueFlowsToCallerFromSubGlobalFlowGraph(min, mdCaller, possibleMdCallee);
750       }
751
752     }
753
754   }
755
756   private void propagateValueFlowsToCallerFromSubGlobalFlowGraph(MethodInvokeNode min,
757       MethodDescriptor mdCaller, MethodDescriptor possibleMdCallee) {
758
759     System.out.println("propagateValueFlowsToCallerFromSubGlobalFlowGraph=" + min.printNode(0)
760         + " by caller=" + mdCaller);
761     FlowGraph calleeFlowGraph = getFlowGraph(possibleMdCallee);
762     Map<Integer, NTuple<Descriptor>> mapIdxToArg = mapMethodInvokeNodeToArgIdxMap.get(min);
763
764     System.out.println("mapMethodInvokeNodeToArgIdxMap.get(min)="
765         + mapMethodInvokeNodeToArgIdxMap.get(min));
766     Set<Integer> keySet = mapIdxToArg.keySet();
767     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
768       Integer idx = (Integer) iterator.next();
769       NTuple<Descriptor> argDescTuple = mapIdxToArg.get(idx);
770       if (argDescTuple.size() > 0) {
771         NTuple<Location> argLocTuple = translateToLocTuple(mdCaller, argDescTuple);
772         NTuple<Descriptor> paramDescTuple = calleeFlowGraph.getParamFlowNode(idx).getDescTuple();
773         NTuple<Location> paramLocTuple = translateToLocTuple(possibleMdCallee, paramDescTuple);
774         addMapCallerArgToCalleeParam(min, argDescTuple, paramDescTuple);
775       }
776
777     }
778
779     NTuple<Descriptor> baseTuple = mapMethodInvokeNodeToBaseTuple.get(min);
780     GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(possibleMdCallee);
781     Set<GlobalFlowNode> calleeNodeSet = calleeSubGlobalGraph.getNodeSet();
782     System.out.println("#calleeNodeSet=" + calleeNodeSet);
783     for (Iterator iterator = calleeNodeSet.iterator(); iterator.hasNext();) {
784       GlobalFlowNode calleeNode = (GlobalFlowNode) iterator.next();
785       addValueFlowFromCalleeNode(min, mdCaller, possibleMdCallee, calleeNode);
786     }
787
788     // int numParam = calleeFlowGraph.getNumParameters();
789     // for (int idx = 0; idx < numParam; idx++) {
790     //
791     // FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx);
792     //
793     // NTuple<Location> paramLocTuple =
794     // translateToLocTuple(possibleMdCallee, paramNode.getCurrentDescTuple());
795     //
796     // GlobalFlowNode globalParamNode =
797     // calleeSubGlobalGraph.getFlowNode(paramLocTuple);
798     //
799     // NTuple<Descriptor> argTuple =
800     // mapMethodInvokeNodeToArgIdxMap.get(min).get(idx);
801     //
802     // NTuple<Location> argLocTuple = translateToLocTuple(mdCaller, argTuple);
803     //
804     // System.out.println("argTupleSet=" + argLocTuple + "   param=" +
805     // paramLocTuple);
806     // // here, it adds all value flows reachable from the paramNode in the
807     // callee's flow graph
808     //
809     // addValueFlowsFromCalleeParam(mdCaller, argLocTuple, baseLocTuple,
810     // possibleMdCallee,
811     // globalParamNode);
812     // }
813     //
814     // // TODO
815     // // FlowGraph callerSubGlobalGraph = getSubGlobalFlowGraph(mdCaller);
816     // // FlowGraph calleeSubGlobalGraph =
817     // getSubGlobalFlowGraph(possibleMdCallee);
818     // //
819     // // int numParam = calleeSubGlobalGraph.getNumParameters();
820     // // for (int idx = 0; idx < numParam; idx++) {
821     // // FlowNode paramNode = calleeSubGlobalGraph.getParamFlowNode(idx);
822     // // NTuple<Descriptor> argTuple =
823     // mapMethodInvokeNodeToArgIdxMap.get(min).get(idx);
824     // // System.out.println("argTupleSet=" + argTuple + "   param=" +
825     // paramNode);
826     // // // here, it adds all value flows reachable from the paramNode in the
827     // callee's flow graph
828     // // addValueFlowsFromCalleeParam(min, calleeSubGlobalGraph, paramNode,
829     // callerSubGlobalGraph,
830     // // argTuple, baseTuple);
831     // // }
832
833   }
834
835   private void addValueFlowFromCalleeNode(MethodInvokeNode min, MethodDescriptor mdCaller,
836       MethodDescriptor mdCallee, GlobalFlowNode calleeSrcNode) {
837
838     GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(mdCallee);
839     GlobalFlowGraph callerSubGlobalGraph = getSubGlobalFlowGraph(mdCaller);
840
841     NTuple<Location> callerSrcNodeLocTuple =
842         translateToCallerLocTuple(min, mdCallee, mdCaller, calleeSrcNode.getLocTuple());
843
844
845     if (callerSrcNodeLocTuple != null) {
846       Set<GlobalFlowNode> outNodeSet = calleeSubGlobalGraph.getOutNodeSet(calleeSrcNode);
847
848       for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
849         GlobalFlowNode outNode = (GlobalFlowNode) iterator.next();
850         NTuple<Location> callerDstNodeLocTuple =
851             translateToCallerLocTuple(min, mdCallee, mdCaller, outNode.getLocTuple());
852         if (callerDstNodeLocTuple != null) {
853           callerSubGlobalGraph.addValueFlowEdge(callerSrcNodeLocTuple, callerDstNodeLocTuple);
854         }
855       }
856     }
857
858   }
859
860   private NTuple<Location> translateToCallerLocTuple(MethodInvokeNode min,
861       MethodDescriptor mdCallee, MethodDescriptor mdCaller, NTuple<Location> nodeLocTuple) {
862     // this method will return NULL if the corresponding argument is literal
863     // value.
864     // assumes that we don't need to propagate callee flows to the argument
865     // which is literal.
866
867     System.out.println("---translateToCallerLocTuple=" + min.printNode(0)
868         + "  callee nodeLocTuple=" + nodeLocTuple);
869
870     FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
871
872     NTuple<Descriptor> nodeDescTuple = translateToDescTuple(nodeLocTuple);
873     if (calleeFlowGraph.isParameter(nodeDescTuple)) {
874       int paramIdx = calleeFlowGraph.getParamIdx(nodeDescTuple);
875       NTuple<Descriptor> argDescTuple = mapMethodInvokeNodeToArgIdxMap.get(min).get(paramIdx);
876       // System.out.println(" mapMethodInvokeNodeToArgIdxMap.get(min)="
877       // + mapMethodInvokeNodeToArgIdxMap.get(min));
878
879       if (argDescTuple.size() == 0) {
880         // argument is literal
881         return null;
882       }
883       NTuple<Location> argLocTuple = translateToLocTuple(mdCaller, argDescTuple);
884
885       NTuple<Location> callerLocTuple = new NTuple<Location>();
886
887       callerLocTuple.addAll(argLocTuple);
888       for (int i = 1; i < nodeLocTuple.size(); i++) {
889         callerLocTuple.add(nodeLocTuple.get(i));
890       }
891       return callerLocTuple;
892     } else {
893       return nodeLocTuple.clone();
894     }
895
896   }
897
898   private NTuple<Descriptor> translateToDescTuple(NTuple<Location> locTuple) {
899
900     NTuple<Descriptor> descTuple = new NTuple<Descriptor>();
901     for (int i = 0; i < locTuple.size(); i++) {
902       descTuple.add(locTuple.get(i).getLocDescriptor());
903     }
904     return descTuple;
905
906   }
907
908   private void addValueFlowsFromCalleeParam(MethodDescriptor mdCaller,
909       NTuple<Location> argLocTuple, NTuple<Location> baseLocTuple, MethodDescriptor mdCallee,
910       GlobalFlowNode globalParamNode) {
911
912     Set<GlobalFlowNode> visited = new HashSet<GlobalFlowNode>();
913     visited.add(globalParamNode);
914     recurAddValueFlowsFromCalleeParam(mdCaller, argLocTuple, baseLocTuple, mdCallee,
915         globalParamNode);
916
917   }
918
919   private void recurAddValueFlowsFromCalleeParam(MethodDescriptor mdCaller,
920       NTuple<Location> argLocTuple, NTuple<Location> baseLocTuple, MethodDescriptor mdCallee,
921       GlobalFlowNode calleeCurNode) {
922
923     // FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
924     // GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(mdCallee);
925     //
926     // NTuple<Location> curNodeLocTuple = calleeCurNode.getLocTuple();
927     // NTuple<Descriptor> curNodeDescTuple = calleeCurNode.getDescTuple();
928     // if (calleeFlowGraph.isParameter(curNodeDescTuple)) {
929     // curNodeLocTuple = translateToCaller(argLocTuple, curNodeLocTuple);
930     // }
931     //
932     // Set<GlobalFlowNode> outNodeSet =
933     // calleeSubGlobalGraph.getOutNodeSet(calleeCurNode);
934     // for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
935     // GlobalFlowNode outNode = (GlobalFlowNode) iterator.next();
936     //
937     // NTuple<Location> curNodeLocTuple = calleeCurNode.getLocTuple();
938     // NTuple<Descriptor> curNodeDescTuple = calleeCurNode.getDescTuple();
939     // if (calleeFlowGraph.isParameter(curNodeDescTuple)) {
940     // curNodeLocTuple = translateToCaller(argLocTuple, curNodeLocTuple);
941     // }
942     //
943     // outNode.getDescTuple();
944     //
945     // if (calleeFlowGraph.is)
946     //
947     // if (calleeSubGlobalGraph.isParameter(srcDescTuple)) {
948     // // destination node is started with 'parameter'
949     // // need to translate it in terms of the caller's a node
950     // srcDescTuple =
951     // translateToCaller(min, calleeSubGlobalGraph.getParamIdx(srcDescTuple),
952     // srcDescTuple);
953     // }
954     //
955     // }
956     //
957     // Set<FlowEdge> edgeSet =
958     // calleeSubGlobalGraph.getOutEdgeSetStartingFrom(calleeSrcNode);
959     // for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) {
960     // FlowEdge flowEdge = (FlowEdge) iterator.next();
961     //
962     // NTuple<Descriptor> srcDescTuple = flowEdge.getInitTuple();
963     // NTuple<Descriptor> dstDescTuple = flowEdge.getEndTuple();
964     //
965     // FlowNode dstNode = calleeSubGlobalGraph.getFlowNode(dstDescTuple);
966     //
967     // if (calleeSubGlobalGraph.isParameter(srcDescTuple)) {
968     // // destination node is started with 'parameter'
969     // // need to translate it in terms of the caller's a node
970     // srcDescTuple =
971     // translateToCaller(min, calleeSubGlobalGraph.getParamIdx(srcDescTuple),
972     // srcDescTuple);
973     // }
974     //
975     // if (calleeSubGlobalGraph.isParameter(dstDescTuple)) {
976     // // destination node is started with 'parameter'
977     // // need to translate it in terms of the caller's a node
978     // dstDescTuple =
979     // translateToCaller(min, calleeSubGlobalGraph.getParamIdx(dstDescTuple),
980     // dstDescTuple);
981     // }
982     //
983     // callerSubGlobalGraph.addValueFlowEdge(srcDescTuple, dstDescTuple);
984     //
985     // if (!visited.contains(dstNode)) {
986     // visited.add(dstNode);
987     // recurAddValueFlowsFromCalleeParam(min, calleeSubGlobalGraph, dstNode,
988     // callerSubGlobalGraph,
989     // dstDescTuple, visited, baseTuple);
990     // }
991     //
992     // }
993
994   }
995
996   private NTuple<Location> translateToCaller(NTuple<Location> argLocTuple,
997       NTuple<Location> curNodeLocTuple) {
998
999     NTuple<Location> callerLocTuple = new NTuple<Location>();
1000
1001     callerLocTuple.addAll(argLocTuple);
1002     for (int i = 1; i < curNodeLocTuple.size(); i++) {
1003       callerLocTuple.add(curNodeLocTuple.get(i));
1004     }
1005
1006     return callerLocTuple;
1007   }
1008
1009   private void recurAddValueFlowsFromCalleeParam(MethodInvokeNode min,
1010       FlowGraph calleeSubGlobalGraph, FlowNode calleeSrcNode, FlowGraph callerSubGlobalGraph,
1011       NTuple<Descriptor> callerSrcTuple, Set<FlowNode> visited, NTuple<Descriptor> baseTuple) {
1012
1013     MethodDescriptor mdCallee = calleeSubGlobalGraph.getMethodDescriptor();
1014
1015     // Set<FlowEdge> edgeSet =
1016     // calleeSubGlobalGraph.getOutEdgeSet(calleeSrcNode);
1017     Set<FlowEdge> edgeSet = calleeSubGlobalGraph.getOutEdgeSetStartingFrom(calleeSrcNode);
1018     for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) {
1019       FlowEdge flowEdge = (FlowEdge) iterator.next();
1020
1021       NTuple<Descriptor> srcDescTuple = flowEdge.getInitTuple();
1022       NTuple<Descriptor> dstDescTuple = flowEdge.getEndTuple();
1023
1024       FlowNode dstNode = calleeSubGlobalGraph.getFlowNode(dstDescTuple);
1025
1026       if (calleeSubGlobalGraph.isParameter(srcDescTuple)) {
1027         // destination node is started with 'parameter'
1028         // need to translate it in terms of the caller's a node
1029         srcDescTuple =
1030             translateToCaller(min, calleeSubGlobalGraph.getParamIdx(srcDescTuple), srcDescTuple);
1031       }
1032
1033       if (calleeSubGlobalGraph.isParameter(dstDescTuple)) {
1034         // destination node is started with 'parameter'
1035         // need to translate it in terms of the caller's a node
1036         dstDescTuple =
1037             translateToCaller(min, calleeSubGlobalGraph.getParamIdx(dstDescTuple), dstDescTuple);
1038       }
1039
1040       callerSubGlobalGraph.addValueFlowEdge(srcDescTuple, dstDescTuple);
1041
1042       if (!visited.contains(dstNode)) {
1043         visited.add(dstNode);
1044         recurAddValueFlowsFromCalleeParam(min, calleeSubGlobalGraph, dstNode, callerSubGlobalGraph,
1045             dstDescTuple, visited, baseTuple);
1046       }
1047
1048     }
1049
1050   }
1051
1052   private NTuple<Descriptor> translateToCaller(MethodInvokeNode min, int paramIdx,
1053       NTuple<Descriptor> srcDescTuple) {
1054
1055     NTuple<Descriptor> callerTuple = new NTuple<Descriptor>();
1056
1057     NTuple<Descriptor> argTuple = mapMethodInvokeNodeToArgIdxMap.get(min).get(paramIdx);
1058
1059     for (int i = 0; i < argTuple.size(); i++) {
1060       callerTuple.add(argTuple.get(i));
1061     }
1062
1063     for (int i = 1; i < srcDescTuple.size(); i++) {
1064       callerTuple.add(srcDescTuple.get(i));
1065     }
1066
1067     return callerTuple;
1068   }
1069
1070   private NTuple<Descriptor> traslateToCalleeParamTupleToCallerArgTuple(
1071       NTuple<Descriptor> calleeInitTuple, NTuple<Descriptor> callerSrcTuple) {
1072
1073     NTuple<Descriptor> callerInitTuple = new NTuple<Descriptor>();
1074
1075     for (int i = 0; i < callerSrcTuple.size(); i++) {
1076       callerInitTuple.add(callerSrcTuple.get(i));
1077     }
1078
1079     for (int i = 1; i < calleeInitTuple.size(); i++) {
1080       callerInitTuple.add(calleeInitTuple.get(i));
1081     }
1082
1083     return callerInitTuple;
1084   }
1085
1086   public LocationSummary getLocationSummary(Descriptor d) {
1087     if (!mapDescToLocationSummary.containsKey(d)) {
1088       if (d instanceof MethodDescriptor) {
1089         mapDescToLocationSummary.put(d, new MethodSummary((MethodDescriptor) d));
1090       } else if (d instanceof ClassDescriptor) {
1091         mapDescToLocationSummary.put(d, new FieldSummary());
1092       }
1093     }
1094     return mapDescToLocationSummary.get(d);
1095   }
1096
1097   private void generateMethodSummary() {
1098
1099     Set<MethodDescriptor> keySet = md2lattice.keySet();
1100     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1101       MethodDescriptor md = (MethodDescriptor) iterator.next();
1102
1103       System.out.println("\nSSJAVA: generate method summary: " + md);
1104
1105       FlowGraph flowGraph = getFlowGraph(md);
1106       MethodSummary methodSummary = getMethodSummary(md);
1107
1108       // construct a parameter mapping that maps a parameter descriptor to an
1109       // inferred composite
1110       // location
1111
1112       for (int paramIdx = 0; paramIdx < flowGraph.getNumParameters(); paramIdx++) {
1113         FlowNode flowNode = flowGraph.getParamFlowNode(paramIdx);
1114         NTuple<Descriptor> descTuple = flowNode.getDescTuple();
1115
1116         CompositeLocation assignedCompLoc = flowNode.getCompositeLocation();
1117         CompositeLocation inferredCompLoc;
1118         if (assignedCompLoc != null) {
1119           inferredCompLoc = translateCompositeLocation(assignedCompLoc);
1120         } else {
1121           Descriptor locDesc = descTuple.get(0);
1122           Location loc = new Location(md, locDesc.getSymbol());
1123           loc.setLocDescriptor(locDesc);
1124           inferredCompLoc = new CompositeLocation(loc);
1125         }
1126         System.out.println("-paramIdx=" + paramIdx + "   infer=" + inferredCompLoc);
1127         methodSummary.addMapParamIdxToInferLoc(paramIdx, inferredCompLoc);
1128       }
1129
1130     }
1131
1132   }
1133
1134   private CompositeLocation translateCompositeLocation(CompositeLocation compLoc) {
1135     CompositeLocation newCompLoc = new CompositeLocation();
1136
1137     // System.out.println("compLoc=" + compLoc);
1138     for (int i = 0; i < compLoc.getSize(); i++) {
1139       Location loc = compLoc.get(i);
1140       Descriptor enclosingDescriptor = loc.getDescriptor();
1141       Descriptor locDescriptor = loc.getLocDescriptor();
1142
1143       HNode hnode = getHierarchyGraph(enclosingDescriptor).getHNode(locDescriptor);
1144       // System.out.println("-hnode=" + hnode + "    from=" + locDescriptor +
1145       // " enclosingDescriptor="
1146       // + enclosingDescriptor);
1147       // System.out.println("-getLocationSummary(enclosingDescriptor)="
1148       // + getLocationSummary(enclosingDescriptor));
1149       String locName = getLocationSummary(enclosingDescriptor).getLocationName(hnode.getName());
1150       // System.out.println("-locName=" + locName);
1151       Location newLoc = new Location(enclosingDescriptor, locName);
1152       newLoc.setLocDescriptor(locDescriptor);
1153       newCompLoc.addLocation(newLoc);
1154     }
1155
1156     return newCompLoc;
1157   }
1158
1159   private void debug_writeLattices() {
1160
1161     Set<Descriptor> keySet = mapDescriptorToSimpleLattice.keySet();
1162     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1163       Descriptor key = (Descriptor) iterator.next();
1164       SSJavaLattice<String> simpleLattice = mapDescriptorToSimpleLattice.get(key);
1165       // HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(key);
1166       HierarchyGraph scHierarchyGraph = getSkeletonCombinationHierarchyGraph(key);
1167       if (key instanceof ClassDescriptor) {
1168         writeInferredLatticeDotFile((ClassDescriptor) key, scHierarchyGraph, simpleLattice,
1169             "_SIMPLE");
1170       } else if (key instanceof MethodDescriptor) {
1171         MethodDescriptor md = (MethodDescriptor) key;
1172         writeInferredLatticeDotFile(md.getClassDesc(), md, scHierarchyGraph, simpleLattice,
1173             "_SIMPLE");
1174       }
1175
1176       LocationSummary ls = getLocationSummary(key);
1177       System.out.println("####LOC SUMMARY=" + key + "\n" + ls.getMapHNodeNameToLocationName());
1178     }
1179
1180     Set<ClassDescriptor> cdKeySet = cd2lattice.keySet();
1181     for (Iterator iterator = cdKeySet.iterator(); iterator.hasNext();) {
1182       ClassDescriptor cd = (ClassDescriptor) iterator.next();
1183       writeInferredLatticeDotFile((ClassDescriptor) cd, getSkeletonCombinationHierarchyGraph(cd),
1184           cd2lattice.get(cd), "");
1185     }
1186
1187     Set<MethodDescriptor> mdKeySet = md2lattice.keySet();
1188     for (Iterator iterator = mdKeySet.iterator(); iterator.hasNext();) {
1189       MethodDescriptor md = (MethodDescriptor) iterator.next();
1190       writeInferredLatticeDotFile(md.getClassDesc(), md, getSkeletonCombinationHierarchyGraph(md),
1191           md2lattice.get(md), "");
1192     }
1193
1194   }
1195
1196   private void buildLattice() {
1197
1198     BuildLattice buildLattice = new BuildLattice(this);
1199
1200     Set<Descriptor> keySet = mapDescriptorToCombineSkeletonHierarchyGraph.keySet();
1201     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1202       Descriptor desc = (Descriptor) iterator.next();
1203
1204       SSJavaLattice<String> simpleLattice = buildLattice.buildLattice(desc);
1205
1206       addMapDescToSimpleLattice(desc, simpleLattice);
1207
1208       HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc);
1209       System.out.println("## insertIntermediateNodesToStraightLine:"
1210           + simpleHierarchyGraph.getName());
1211       SSJavaLattice<String> lattice =
1212           buildLattice.insertIntermediateNodesToStraightLine(desc, simpleLattice);
1213       lattice.removeRedundantEdges();
1214
1215       if (desc instanceof ClassDescriptor) {
1216         // field lattice
1217         cd2lattice.put((ClassDescriptor) desc, lattice);
1218         // ssjava.writeLatticeDotFile((ClassDescriptor) desc, null, lattice);
1219       } else if (desc instanceof MethodDescriptor) {
1220         // method lattice
1221         md2lattice.put((MethodDescriptor) desc, lattice);
1222         MethodDescriptor md = (MethodDescriptor) desc;
1223         ClassDescriptor cd = md.getClassDesc();
1224         // ssjava.writeLatticeDotFile(cd, md, lattice);
1225       }
1226
1227       // System.out.println("\nSSJAVA: Insering Combination Nodes:" + desc);
1228       // HierarchyGraph skeletonGraph = getSkeletonHierarchyGraph(desc);
1229       // HierarchyGraph skeletonGraphWithCombinationNode =
1230       // skeletonGraph.clone();
1231       // skeletonGraphWithCombinationNode.setName(desc + "_SC");
1232       //
1233       // HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc);
1234       // System.out.println("Identifying Combination Nodes:");
1235       // skeletonGraphWithCombinationNode.insertCombinationNodesToGraph(simpleHierarchyGraph);
1236       // skeletonGraphWithCombinationNode.simplifySkeletonCombinationHierarchyGraph();
1237       // mapDescriptorToCombineSkeletonHierarchyGraph.put(desc,
1238       // skeletonGraphWithCombinationNode);
1239     }
1240
1241   }
1242
1243   public void addMapDescToSimpleLattice(Descriptor desc, SSJavaLattice<String> lattice) {
1244     mapDescriptorToSimpleLattice.put(desc, lattice);
1245   }
1246
1247   public SSJavaLattice<String> getSimpleLattice(Descriptor desc) {
1248     return mapDescriptorToSimpleLattice.get(desc);
1249   }
1250
1251   private void simplifyHierarchyGraph() {
1252     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
1253     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1254       Descriptor desc = (Descriptor) iterator.next();
1255       HierarchyGraph simpleHierarchyGraph = getHierarchyGraph(desc).clone();
1256       simpleHierarchyGraph.setName(desc + "_SIMPLE");
1257       simpleHierarchyGraph.removeRedundantEdges();
1258       // simpleHierarchyGraph.simplifyHierarchyGraph();
1259       mapDescriptorToSimpleHierarchyGraph.put(desc, simpleHierarchyGraph);
1260     }
1261   }
1262
1263   private void insertCombinationNodes() {
1264     Set<Descriptor> keySet = mapDescriptorToSkeletonHierarchyGraph.keySet();
1265     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1266       Descriptor desc = (Descriptor) iterator.next();
1267       System.out.println("\nSSJAVA: Insering Combination Nodes:" + desc);
1268       HierarchyGraph skeletonGraph = getSkeletonHierarchyGraph(desc);
1269       HierarchyGraph skeletonGraphWithCombinationNode = skeletonGraph.clone();
1270       skeletonGraphWithCombinationNode.setName(desc + "_SC");
1271
1272       HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc);
1273       System.out.println("Identifying Combination Nodes:");
1274       skeletonGraphWithCombinationNode.insertCombinationNodesToGraph(simpleHierarchyGraph);
1275       skeletonGraphWithCombinationNode.simplifySkeletonCombinationHierarchyGraph();
1276       mapDescriptorToCombineSkeletonHierarchyGraph.put(desc, skeletonGraphWithCombinationNode);
1277     }
1278   }
1279
1280   private void constructSkeletonHierarchyGraph() {
1281     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
1282     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1283       Descriptor desc = (Descriptor) iterator.next();
1284       HierarchyGraph simpleGraph = getSimpleHierarchyGraph(desc);
1285       HierarchyGraph skeletonGraph = simpleGraph.generateSkeletonGraph();
1286       skeletonGraph.setMapDescToHNode(simpleGraph.getMapDescToHNode());
1287       skeletonGraph.setMapHNodeToDescSet(simpleGraph.getMapHNodeToDescSet());
1288       skeletonGraph.simplifyHierarchyGraph();
1289       // skeletonGraph.combineRedundantNodes(false);
1290       // skeletonGraph.removeRedundantEdges();
1291       mapDescriptorToSkeletonHierarchyGraph.put(desc, skeletonGraph);
1292     }
1293   }
1294
1295   private void debug_writeHierarchyDotFiles() {
1296
1297     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
1298     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1299       Descriptor desc = (Descriptor) iterator.next();
1300       getHierarchyGraph(desc).writeGraph();
1301     }
1302
1303   }
1304
1305   private void debug_writeSimpleHierarchyDotFiles() {
1306
1307     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
1308     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1309       Descriptor desc = (Descriptor) iterator.next();
1310       getHierarchyGraph(desc).writeGraph();
1311       getSimpleHierarchyGraph(desc).writeGraph();
1312     }
1313
1314   }
1315
1316   private void debug_writeSkeletonHierarchyDotFiles() {
1317
1318     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
1319     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1320       Descriptor desc = (Descriptor) iterator.next();
1321       getSkeletonHierarchyGraph(desc).writeGraph();
1322     }
1323
1324   }
1325
1326   private void debug_writeSkeletonCombinationHierarchyDotFiles() {
1327
1328     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
1329     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1330       Descriptor desc = (Descriptor) iterator.next();
1331       getSkeletonCombinationHierarchyGraph(desc).writeGraph();
1332     }
1333
1334   }
1335
1336   public HierarchyGraph getSimpleHierarchyGraph(Descriptor d) {
1337     return mapDescriptorToSimpleHierarchyGraph.get(d);
1338   }
1339
1340   private HierarchyGraph getSkeletonHierarchyGraph(Descriptor d) {
1341     if (!mapDescriptorToSkeletonHierarchyGraph.containsKey(d)) {
1342       mapDescriptorToSkeletonHierarchyGraph.put(d, new HierarchyGraph(d));
1343     }
1344     return mapDescriptorToSkeletonHierarchyGraph.get(d);
1345   }
1346
1347   public HierarchyGraph getSkeletonCombinationHierarchyGraph(Descriptor d) {
1348     if (!mapDescriptorToCombineSkeletonHierarchyGraph.containsKey(d)) {
1349       mapDescriptorToCombineSkeletonHierarchyGraph.put(d, new HierarchyGraph(d));
1350     }
1351     return mapDescriptorToCombineSkeletonHierarchyGraph.get(d);
1352   }
1353
1354   private void constructHierarchyGraph() {
1355
1356     // do fixed-point analysis
1357
1358     ssjava.init();
1359     LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
1360
1361     // Collections.sort(descriptorListToAnalyze, new
1362     // Comparator<MethodDescriptor>() {
1363     // public int compare(MethodDescriptor o1, MethodDescriptor o2) {
1364     // return o1.getSymbol().compareToIgnoreCase(o2.getSymbol());
1365     // }
1366     // });
1367
1368     // current descriptors to visit in fixed-point interprocedural analysis,
1369     // prioritized by dependency in the call graph
1370     methodDescriptorsToVisitStack.clear();
1371
1372     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
1373     methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
1374
1375     while (!descriptorListToAnalyze.isEmpty()) {
1376       MethodDescriptor md = descriptorListToAnalyze.removeFirst();
1377       methodDescriptorsToVisitStack.add(md);
1378     }
1379
1380     // analyze scheduled methods until there are no more to visit
1381     while (!methodDescriptorsToVisitStack.isEmpty()) {
1382       // start to analyze leaf node
1383       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
1384
1385       HierarchyGraph hierarchyGraph = new HierarchyGraph(md);
1386       // MethodSummary methodSummary = new MethodSummary(md);
1387
1388       // MethodLocationInfo methodInfo = new MethodLocationInfo(md);
1389       // curMethodInfo = methodInfo;
1390
1391       System.out.println();
1392       System.out.println("SSJAVA: Construcing the hierarchy graph from " + md);
1393
1394       constructHierarchyGraph(md, hierarchyGraph);
1395
1396       HierarchyGraph prevHierarchyGraph = getHierarchyGraph(md);
1397       // MethodSummary prevMethodSummary = getMethodSummary(md);
1398
1399       if (!hierarchyGraph.equals(prevHierarchyGraph)) {
1400
1401         mapDescriptorToHierarchyGraph.put(md, hierarchyGraph);
1402         // mapDescToLocationSummary.put(md, methodSummary);
1403
1404         // results for callee changed, so enqueue dependents caller for
1405         // further analysis
1406         Iterator<MethodDescriptor> depsItr = ssjava.getDependents(md).iterator();
1407         while (depsItr.hasNext()) {
1408           MethodDescriptor methodNext = depsItr.next();
1409           if (!methodDescriptorsToVisitStack.contains(methodNext)
1410               && methodDescriptorToVistSet.contains(methodNext)) {
1411             methodDescriptorsToVisitStack.add(methodNext);
1412           }
1413         }
1414
1415       }
1416
1417     }
1418
1419   }
1420
1421   private HierarchyGraph getHierarchyGraph(Descriptor d) {
1422     if (!mapDescriptorToHierarchyGraph.containsKey(d)) {
1423       mapDescriptorToHierarchyGraph.put(d, new HierarchyGraph(d));
1424     }
1425     return mapDescriptorToHierarchyGraph.get(d);
1426   }
1427
1428   private void constructHierarchyGraph(MethodDescriptor md, HierarchyGraph methodGraph) {
1429
1430     // visit each node of method flow graph
1431     FlowGraph fg = getFlowGraph(md);
1432     Set<FlowNode> nodeSet = fg.getNodeSet();
1433
1434     Set<Descriptor> paramDescSet = fg.getMapParamDescToIdx().keySet();
1435     for (Iterator iterator = paramDescSet.iterator(); iterator.hasNext();) {
1436       Descriptor desc = (Descriptor) iterator.next();
1437       methodGraph.getHNode(desc).setSkeleton(true);
1438     }
1439
1440     // for the method lattice, we need to look at the first element of
1441     // NTuple<Descriptor>
1442     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1443       FlowNode srcNode = (FlowNode) iterator.next();
1444
1445       Set<FlowEdge> outEdgeSet = fg.getOutEdgeSet(srcNode);
1446       for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) {
1447         FlowEdge outEdge = (FlowEdge) iterator2.next();
1448         FlowNode dstNode = outEdge.getDst();
1449
1450         NTuple<Descriptor> srcNodeTuple = srcNode.getDescTuple();
1451         NTuple<Descriptor> dstNodeTuple = dstNode.getDescTuple();
1452
1453         if (outEdge.getInitTuple().equals(srcNodeTuple)
1454             && outEdge.getEndTuple().equals(dstNodeTuple)) {
1455
1456           NTuple<Descriptor> srcCurTuple = srcNode.getCurrentDescTuple();
1457           NTuple<Descriptor> dstCurTuple = dstNode.getCurrentDescTuple();
1458
1459           if ((srcCurTuple.size() > 1 && dstCurTuple.size() > 1)
1460               && srcCurTuple.get(0).equals(dstCurTuple.get(0))) {
1461
1462             // value flows between fields
1463             Descriptor desc = srcCurTuple.get(0);
1464             ClassDescriptor classDesc;
1465
1466             if (desc.equals(GLOBALDESC)) {
1467               classDesc = md.getClassDesc();
1468             } else {
1469               VarDescriptor varDesc = (VarDescriptor) srcCurTuple.get(0);
1470               classDesc = varDesc.getType().getClassDesc();
1471             }
1472             extractFlowsBetweenFields(classDesc, srcNode, dstNode, 1);
1473
1474           } else {
1475             // value flow between local var - local var or local var - field
1476
1477             Descriptor srcDesc = srcCurTuple.get(0);
1478             Descriptor dstDesc = dstCurTuple.get(0);
1479
1480             methodGraph.addEdge(srcDesc, dstDesc);
1481
1482             if (fg.isParamDesc(srcDesc)) {
1483               methodGraph.setParamHNode(srcDesc);
1484             }
1485             if (fg.isParamDesc(dstDesc)) {
1486               methodGraph.setParamHNode(dstDesc);
1487             }
1488
1489           }
1490
1491         }
1492       }
1493     }
1494
1495   }
1496
1497   private MethodSummary getMethodSummary(MethodDescriptor md) {
1498     if (!mapDescToLocationSummary.containsKey(md)) {
1499       mapDescToLocationSummary.put(md, new MethodSummary(md));
1500     }
1501     return (MethodSummary) mapDescToLocationSummary.get(md);
1502   }
1503
1504   private void addMapClassDefinitionToLineNum(ClassDescriptor cd, String strLine, int lineNum) {
1505
1506     String classSymbol = cd.getSymbol();
1507     int idx = classSymbol.lastIndexOf("$");
1508     if (idx != -1) {
1509       classSymbol = classSymbol.substring(idx + 1);
1510     }
1511
1512     String pattern = "class " + classSymbol + " ";
1513     if (strLine.indexOf(pattern) != -1) {
1514       mapDescToDefinitionLine.put(cd, lineNum);
1515     }
1516   }
1517
1518   private void addMapMethodDefinitionToLineNum(Set<MethodDescriptor> methodSet, String strLine,
1519       int lineNum) {
1520     for (Iterator iterator = methodSet.iterator(); iterator.hasNext();) {
1521       MethodDescriptor md = (MethodDescriptor) iterator.next();
1522       String pattern = md.getMethodDeclaration();
1523       if (strLine.indexOf(pattern) != -1) {
1524         mapDescToDefinitionLine.put(md, lineNum);
1525         methodSet.remove(md);
1526         return;
1527       }
1528     }
1529
1530   }
1531
1532   private void readOriginalSourceFiles() {
1533
1534     SymbolTable classtable = state.getClassSymbolTable();
1535
1536     Set<ClassDescriptor> classDescSet = new HashSet<ClassDescriptor>();
1537     classDescSet.addAll(classtable.getValueSet());
1538
1539     try {
1540       // inefficient implement. it may re-visit the same file if the file
1541       // contains more than one class definitions.
1542       for (Iterator iterator = classDescSet.iterator(); iterator.hasNext();) {
1543         ClassDescriptor cd = (ClassDescriptor) iterator.next();
1544
1545         Set<MethodDescriptor> methodSet = new HashSet<MethodDescriptor>();
1546         methodSet.addAll(cd.getMethodTable().getValueSet());
1547
1548         String sourceFileName = cd.getSourceFileName();
1549         Vector<String> lineVec = new Vector<String>();
1550
1551         mapFileNameToLineVector.put(sourceFileName, lineVec);
1552
1553         BufferedReader in = new BufferedReader(new FileReader(sourceFileName));
1554         String strLine;
1555         int lineNum = 1;
1556         lineVec.add(""); // the index is started from 1.
1557         while ((strLine = in.readLine()) != null) {
1558           lineVec.add(lineNum, strLine);
1559           addMapClassDefinitionToLineNum(cd, strLine, lineNum);
1560           addMapMethodDefinitionToLineNum(methodSet, strLine, lineNum);
1561           lineNum++;
1562         }
1563
1564       }
1565
1566     } catch (IOException e) {
1567       e.printStackTrace();
1568     }
1569
1570   }
1571
1572   private String generateLatticeDefinition(Descriptor desc) {
1573
1574     Set<String> sharedLocSet = new HashSet<String>();
1575
1576     SSJavaLattice<String> lattice = getLattice(desc);
1577     String rtr = "@LATTICE(\"";
1578
1579     Map<String, Set<String>> map = lattice.getTable();
1580     Set<String> keySet = map.keySet();
1581     boolean first = true;
1582     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1583       String key = (String) iterator.next();
1584       if (!key.equals(lattice.getTopItem())) {
1585         Set<String> connectedSet = map.get(key);
1586
1587         if (connectedSet.size() == 1) {
1588           if (connectedSet.iterator().next().equals(lattice.getBottomItem())) {
1589             if (!first) {
1590               rtr += ",";
1591             } else {
1592               rtr += "LOC,";
1593               first = false;
1594             }
1595             rtr += key;
1596             if (lattice.isSharedLoc(key)) {
1597               rtr += "," + key + "*";
1598             }
1599           }
1600         }
1601
1602         for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) {
1603           String loc = (String) iterator2.next();
1604           if (!loc.equals(lattice.getBottomItem())) {
1605             if (!first) {
1606               rtr += ",";
1607             } else {
1608               rtr += "LOC,";
1609               first = false;
1610             }
1611             rtr += loc + "<" + key;
1612             if (lattice.isSharedLoc(key) && (!sharedLocSet.contains(key))) {
1613               rtr += "," + key + "*";
1614               sharedLocSet.add(key);
1615             }
1616             if (lattice.isSharedLoc(loc) && (!sharedLocSet.contains(loc))) {
1617               rtr += "," + loc + "*";
1618               sharedLocSet.add(loc);
1619             }
1620
1621           }
1622         }
1623       }
1624     }
1625
1626     rtr += "\")";
1627
1628     if (desc instanceof MethodDescriptor) {
1629       TypeDescriptor returnType = ((MethodDescriptor) desc).getReturnType();
1630
1631       MethodLocationInfo methodLocInfo = getMethodLocationInfo((MethodDescriptor) desc);
1632
1633       if (returnType != null && (!returnType.isVoid())) {
1634         rtr +=
1635             "\n@RETURNLOC(\"" + generateLocationAnnoatation(methodLocInfo.getReturnLoc()) + "\")";
1636       }
1637
1638       rtr += "\n@THISLOC(\"this\")";
1639       rtr += "\n@GLOBALLOC(\"GLOBALLOC\")";
1640
1641       CompositeLocation pcLoc = methodLocInfo.getPCLoc();
1642       if ((pcLoc != null) && (!pcLoc.get(0).isTop())) {
1643         rtr += "\n@PCLOC(\"" + generateLocationAnnoatation(pcLoc) + "\")";
1644       }
1645
1646     }
1647
1648     return rtr;
1649   }
1650
1651   private void generateAnnoatedCode() {
1652
1653     readOriginalSourceFiles();
1654
1655     setupToAnalyze();
1656     while (!toAnalyzeIsEmpty()) {
1657       ClassDescriptor cd = toAnalyzeNext();
1658
1659       setupToAnalazeMethod(cd);
1660
1661       LocationInfo locInfo = mapClassToLocationInfo.get(cd);
1662       String sourceFileName = cd.getSourceFileName();
1663
1664       if (cd.isInterface()) {
1665         continue;
1666       }
1667
1668       int classDefLine = mapDescToDefinitionLine.get(cd);
1669       Vector<String> sourceVec = mapFileNameToLineVector.get(sourceFileName);
1670
1671       if (locInfo == null) {
1672         locInfo = getLocationInfo(cd);
1673       }
1674
1675       for (Iterator iter = cd.getFields(); iter.hasNext();) {
1676         FieldDescriptor fieldDesc = (FieldDescriptor) iter.next();
1677         if (!(fieldDesc.isStatic() && fieldDesc.isFinal())) {
1678           String locIdentifier = locInfo.getFieldInferLocation(fieldDesc).getLocIdentifier();
1679           if (!getLattice(cd).getElementSet().contains(locIdentifier)) {
1680             getLattice(cd).put(locIdentifier);
1681           }
1682         }
1683       }
1684
1685       String fieldLatticeDefStr = generateLatticeDefinition(cd);
1686       String annoatedSrc = fieldLatticeDefStr + newline + sourceVec.get(classDefLine);
1687       sourceVec.set(classDefLine, annoatedSrc);
1688
1689       // generate annotations for field declarations
1690       LocationInfo fieldLocInfo = getLocationInfo(cd);
1691       Map<Descriptor, CompositeLocation> inferLocMap = fieldLocInfo.getMapDescToInferLocation();
1692
1693       for (Iterator iter = cd.getFields(); iter.hasNext();) {
1694         FieldDescriptor fd = (FieldDescriptor) iter.next();
1695
1696         String locAnnotationStr;
1697         CompositeLocation inferLoc = inferLocMap.get(fd);
1698
1699         if (inferLoc != null) {
1700           // infer loc is null if the corresponding field is static and final
1701           locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")";
1702           int fdLineNum = fd.getLineNum();
1703           String orgFieldDeclarationStr = sourceVec.get(fdLineNum);
1704           String fieldDeclaration = fd.toString();
1705           fieldDeclaration = fieldDeclaration.substring(0, fieldDeclaration.length() - 1);
1706           String annoatedStr = locAnnotationStr + " " + orgFieldDeclarationStr;
1707           sourceVec.set(fdLineNum, annoatedStr);
1708         }
1709
1710       }
1711
1712       while (!toAnalyzeMethodIsEmpty()) {
1713         MethodDescriptor md = toAnalyzeMethodNext();
1714
1715         if (!ssjava.needTobeAnnotated(md)) {
1716           continue;
1717         }
1718
1719         SSJavaLattice<String> methodLattice = md2lattice.get(md);
1720         if (methodLattice != null) {
1721
1722           int methodDefLine = md.getLineNum();
1723
1724           MethodLocationInfo methodLocInfo = getMethodLocationInfo(md);
1725
1726           Map<Descriptor, CompositeLocation> methodInferLocMap =
1727               methodLocInfo.getMapDescToInferLocation();
1728           Set<Descriptor> localVarDescSet = methodInferLocMap.keySet();
1729
1730           Set<String> localLocElementSet = methodLattice.getElementSet();
1731
1732           for (Iterator iterator = localVarDescSet.iterator(); iterator.hasNext();) {
1733             Descriptor localVarDesc = (Descriptor) iterator.next();
1734             CompositeLocation inferLoc = methodInferLocMap.get(localVarDesc);
1735
1736             String localLocIdentifier = inferLoc.get(0).getLocIdentifier();
1737             if (!localLocElementSet.contains(localLocIdentifier)) {
1738               methodLattice.put(localLocIdentifier);
1739             }
1740
1741             String locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")";
1742
1743             if (!isParameter(md, localVarDesc)) {
1744               if (mapDescToDefinitionLine.containsKey(localVarDesc)) {
1745                 int varLineNum = mapDescToDefinitionLine.get(localVarDesc);
1746                 String orgSourceLine = sourceVec.get(varLineNum);
1747                 int idx =
1748                     orgSourceLine.indexOf(generateVarDeclaration((VarDescriptor) localVarDesc));
1749                 assert (idx != -1);
1750                 String annoatedStr =
1751                     orgSourceLine.substring(0, idx) + locAnnotationStr + " "
1752                         + orgSourceLine.substring(idx);
1753                 sourceVec.set(varLineNum, annoatedStr);
1754               }
1755             } else {
1756               String methodDefStr = sourceVec.get(methodDefLine);
1757
1758               int idx =
1759                   getParamLocation(methodDefStr,
1760                       generateVarDeclaration((VarDescriptor) localVarDesc));
1761
1762               assert (idx != -1);
1763
1764               String annoatedStr =
1765                   methodDefStr.substring(0, idx) + locAnnotationStr + " "
1766                       + methodDefStr.substring(idx);
1767               sourceVec.set(methodDefLine, annoatedStr);
1768             }
1769
1770           }
1771
1772           // check if the lattice has to have the location type for the this
1773           // reference...
1774
1775           // boolean needToAddthisRef = hasThisReference(md);
1776           if (localLocElementSet.contains("this")) {
1777             methodLattice.put("this");
1778           }
1779
1780           String methodLatticeDefStr = generateLatticeDefinition(md);
1781           String annoatedStr = methodLatticeDefStr + newline + sourceVec.get(methodDefLine);
1782           sourceVec.set(methodDefLine, annoatedStr);
1783
1784         }
1785       }
1786
1787     }
1788
1789     codeGen();
1790   }
1791
1792   private boolean hasThisReference(MethodDescriptor md) {
1793
1794     FlowGraph fg = getFlowGraph(md);
1795     Set<FlowNode> nodeSet = fg.getNodeSet();
1796     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1797       FlowNode flowNode = (FlowNode) iterator.next();
1798       if (flowNode.getDescTuple().get(0).equals(md.getThis())) {
1799         return true;
1800       }
1801     }
1802
1803     return false;
1804   }
1805
1806   private int getParamLocation(String methodStr, String paramStr) {
1807
1808     String pattern = paramStr + ",";
1809
1810     int idx = methodStr.indexOf(pattern);
1811     if (idx != -1) {
1812       return idx;
1813     } else {
1814       pattern = paramStr + ")";
1815       return methodStr.indexOf(pattern);
1816     }
1817
1818   }
1819
1820   private String generateVarDeclaration(VarDescriptor varDesc) {
1821
1822     TypeDescriptor td = varDesc.getType();
1823     String rtr = td.toString();
1824     if (td.isArray()) {
1825       for (int i = 0; i < td.getArrayCount(); i++) {
1826         rtr += "[]";
1827       }
1828     }
1829     rtr += " " + varDesc.getName();
1830     return rtr;
1831
1832   }
1833
1834   private String generateLocationAnnoatation(CompositeLocation loc) {
1835     String rtr = "";
1836     // method location
1837     Location methodLoc = loc.get(0);
1838     rtr += methodLoc.getLocIdentifier();
1839
1840     for (int i = 1; i < loc.getSize(); i++) {
1841       Location element = loc.get(i);
1842       rtr += "," + element.getDescriptor().getSymbol() + "." + element.getLocIdentifier();
1843     }
1844
1845     return rtr;
1846   }
1847
1848   private boolean isParameter(MethodDescriptor md, Descriptor localVarDesc) {
1849     return getFlowGraph(md).isParamDesc(localVarDesc);
1850   }
1851
1852   private String extractFileName(String fileName) {
1853     int idx = fileName.lastIndexOf("/");
1854     if (idx == -1) {
1855       return fileName;
1856     } else {
1857       return fileName.substring(idx + 1);
1858     }
1859
1860   }
1861
1862   private void codeGen() {
1863
1864     Set<String> originalFileNameSet = mapFileNameToLineVector.keySet();
1865     for (Iterator iterator = originalFileNameSet.iterator(); iterator.hasNext();) {
1866       String orgFileName = (String) iterator.next();
1867       String outputFileName = extractFileName(orgFileName);
1868
1869       Vector<String> sourceVec = mapFileNameToLineVector.get(orgFileName);
1870
1871       try {
1872
1873         FileWriter fileWriter = new FileWriter("./infer/" + outputFileName);
1874         BufferedWriter out = new BufferedWriter(fileWriter);
1875
1876         for (int i = 0; i < sourceVec.size(); i++) {
1877           out.write(sourceVec.get(i));
1878           out.newLine();
1879         }
1880         out.close();
1881       } catch (IOException e) {
1882         e.printStackTrace();
1883       }
1884
1885     }
1886
1887   }
1888
1889   private void checkLattices() {
1890
1891     LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
1892
1893     // current descriptors to visit in fixed-point interprocedural analysis,
1894     // prioritized by
1895     // dependency in the call graph
1896     methodDescriptorsToVisitStack.clear();
1897
1898     // descriptorListToAnalyze.removeFirst();
1899
1900     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
1901     methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
1902
1903     while (!descriptorListToAnalyze.isEmpty()) {
1904       MethodDescriptor md = descriptorListToAnalyze.removeFirst();
1905       checkLatticesOfVirtualMethods(md);
1906     }
1907
1908   }
1909
1910   private void debug_writeLatticeDotFile() {
1911     // generate lattice dot file
1912
1913     setupToAnalyze();
1914
1915     while (!toAnalyzeIsEmpty()) {
1916       ClassDescriptor cd = toAnalyzeNext();
1917
1918       setupToAnalazeMethod(cd);
1919
1920       SSJavaLattice<String> classLattice = cd2lattice.get(cd);
1921       if (classLattice != null) {
1922         ssjava.writeLatticeDotFile(cd, null, classLattice);
1923         debug_printDescriptorToLocNameMapping(cd);
1924       }
1925
1926       while (!toAnalyzeMethodIsEmpty()) {
1927         MethodDescriptor md = toAnalyzeMethodNext();
1928         SSJavaLattice<String> methodLattice = md2lattice.get(md);
1929         if (methodLattice != null) {
1930           ssjava.writeLatticeDotFile(cd, md, methodLattice);
1931           debug_printDescriptorToLocNameMapping(md);
1932         }
1933       }
1934     }
1935
1936   }
1937
1938   private void debug_printDescriptorToLocNameMapping(Descriptor desc) {
1939
1940     LocationInfo info = getLocationInfo(desc);
1941     System.out.println("## " + desc + " ##");
1942     System.out.println(info.getMapDescToInferLocation());
1943     LocationInfo locInfo = getLocationInfo(desc);
1944     System.out.println("mapping=" + locInfo.getMapLocSymbolToDescSet());
1945     System.out.println("###################");
1946
1947   }
1948
1949   private void inferLattices() {
1950   }
1951
1952   private void calculateExtraLocations() {
1953     LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
1954     for (Iterator iterator = descriptorListToAnalyze.iterator(); iterator.hasNext();) {
1955       MethodDescriptor md = (MethodDescriptor) iterator.next();
1956       calculateExtraLocations(md);
1957     }
1958   }
1959
1960   private void setMethodLocInfo(MethodDescriptor md, MethodLocationInfo methodInfo) {
1961     mapMethodDescToMethodLocationInfo.put(md, methodInfo);
1962   }
1963
1964   private void checkLatticesOfVirtualMethods(MethodDescriptor md) {
1965
1966     if (!md.isStatic()) {
1967       Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
1968       setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md));
1969
1970       for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
1971         MethodDescriptor mdCallee = (MethodDescriptor) iterator.next();
1972         if (!md.equals(mdCallee)) {
1973           checkConsistency(md, mdCallee);
1974         }
1975       }
1976
1977     }
1978
1979   }
1980
1981   private void checkConsistency(MethodDescriptor md1, MethodDescriptor md2) {
1982
1983     // check that two lattice have the same relations between parameters(+PC
1984     // LOC, GLOBAL_LOC RETURN LOC)
1985
1986     List<CompositeLocation> list1 = new ArrayList<CompositeLocation>();
1987     List<CompositeLocation> list2 = new ArrayList<CompositeLocation>();
1988
1989     MethodLocationInfo locInfo1 = getMethodLocationInfo(md1);
1990     MethodLocationInfo locInfo2 = getMethodLocationInfo(md2);
1991
1992     Map<Integer, CompositeLocation> paramMap1 = locInfo1.getMapParamIdxToInferLoc();
1993     Map<Integer, CompositeLocation> paramMap2 = locInfo2.getMapParamIdxToInferLoc();
1994
1995     int numParam = locInfo1.getMapParamIdxToInferLoc().keySet().size();
1996
1997     // add location types of paramters
1998     for (int idx = 0; idx < numParam; idx++) {
1999       list1.add(paramMap1.get(Integer.valueOf(idx)));
2000       list2.add(paramMap2.get(Integer.valueOf(idx)));
2001     }
2002
2003     // add program counter location
2004     list1.add(locInfo1.getPCLoc());
2005     list2.add(locInfo2.getPCLoc());
2006
2007     if (!md1.getReturnType().isVoid()) {
2008       // add return value location
2009       CompositeLocation rtrLoc1 = getMethodLocationInfo(md1).getReturnLoc();
2010       CompositeLocation rtrLoc2 = getMethodLocationInfo(md2).getReturnLoc();
2011       list1.add(rtrLoc1);
2012       list2.add(rtrLoc2);
2013     }
2014
2015     // add global location type
2016     if (md1.isStatic()) {
2017       CompositeLocation globalLoc1 =
2018           new CompositeLocation(new Location(md1, locInfo1.getGlobalLocName()));
2019       CompositeLocation globalLoc2 =
2020           new CompositeLocation(new Location(md2, locInfo2.getGlobalLocName()));
2021       list1.add(globalLoc1);
2022       list2.add(globalLoc2);
2023     }
2024
2025     for (int i = 0; i < list1.size(); i++) {
2026       CompositeLocation locA1 = list1.get(i);
2027       CompositeLocation locA2 = list2.get(i);
2028       for (int k = 0; k < list1.size(); k++) {
2029         if (i != k) {
2030           CompositeLocation locB1 = list1.get(k);
2031           CompositeLocation locB2 = list2.get(k);
2032           boolean r1 = isGreaterThan(getLattice(md1), locA1, locB1);
2033
2034           boolean r2 = isGreaterThan(getLattice(md1), locA2, locB2);
2035
2036           if (r1 != r2) {
2037             throw new Error("The method " + md1 + " is not consistent with the method " + md2
2038                 + ".:: They have a different ordering relation between locations (" + locA1 + ","
2039                 + locB1 + ") and (" + locA2 + "," + locB2 + ").");
2040           }
2041         }
2042       }
2043     }
2044
2045   }
2046
2047   private String getSymbol(int idx, FlowNode node) {
2048     Descriptor desc = node.getDescTuple().get(idx);
2049     return desc.getSymbol();
2050   }
2051
2052   private Descriptor getDescriptor(int idx, FlowNode node) {
2053     Descriptor desc = node.getDescTuple().get(idx);
2054     return desc;
2055   }
2056
2057   private void calculateExtraLocations(MethodDescriptor md) {
2058     // calcualte pcloc, returnloc,...
2059
2060     SSJavaLattice<String> methodLattice = getMethodLattice(md);
2061     MethodLocationInfo methodInfo = getMethodLocationInfo(md);
2062     FlowGraph fg = getFlowGraph(md);
2063     Set<FlowNode> nodeSet = fg.getNodeSet();
2064
2065     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
2066       FlowNode flowNode = (FlowNode) iterator.next();
2067       if (flowNode.isDeclaratonNode()) {
2068         CompositeLocation inferLoc = methodInfo.getInferLocation(flowNode.getDescTuple().get(0));
2069         String locIdentifier = inferLoc.get(0).getLocIdentifier();
2070         if (!methodLattice.containsKey(locIdentifier)) {
2071           methodLattice.put(locIdentifier);
2072         }
2073
2074       }
2075     }
2076
2077     Map<Integer, CompositeLocation> mapParamToLoc = methodInfo.getMapParamIdxToInferLoc();
2078     Set<Integer> paramIdxSet = mapParamToLoc.keySet();
2079
2080     if (!ssjava.getMethodContainingSSJavaLoop().equals(md)) {
2081       // calculate the initial program counter location
2082       // PC location is higher than location types of all parameters
2083       String pcLocSymbol = "PCLOC";
2084
2085       Set<CompositeLocation> paramInFlowSet = new HashSet<CompositeLocation>();
2086
2087       for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) {
2088         Integer paramIdx = (Integer) iterator.next();
2089
2090         FlowNode paramFlowNode = fg.getParamFlowNode(paramIdx);
2091
2092         if (fg.getIncomingFlowNodeSet(paramFlowNode).size() > 0) {
2093           // parameter has in-value flows
2094           CompositeLocation inferLoc = mapParamToLoc.get(paramIdx);
2095           paramInFlowSet.add(inferLoc);
2096         }
2097       }
2098
2099       if (paramInFlowSet.size() > 0) {
2100         CompositeLocation lowestLoc = getLowest(methodLattice, paramInFlowSet);
2101         assert (lowestLoc != null);
2102         methodInfo.setPCLoc(lowestLoc);
2103       }
2104
2105     }
2106
2107     // calculate a return location
2108     // the return location type is lower than all parameters and location
2109     // types
2110     // of return values
2111     if (!md.getReturnType().isVoid()) {
2112       // first, generate the set of return value location types that starts
2113       // with
2114       // 'this' reference
2115
2116       Set<CompositeLocation> inferFieldReturnLocSet = new HashSet<CompositeLocation>();
2117
2118       Set<FlowNode> paramFlowNode = getParamNodeFlowingToReturnValue(md);
2119       Set<CompositeLocation> inferParamLocSet = new HashSet<CompositeLocation>();
2120       if (paramFlowNode != null) {
2121         for (Iterator iterator = paramFlowNode.iterator(); iterator.hasNext();) {
2122           FlowNode fn = (FlowNode) iterator.next();
2123           CompositeLocation inferLoc =
2124               generateInferredCompositeLocation(methodInfo, getFlowGraph(md).getLocationTuple(fn));
2125           inferParamLocSet.add(inferLoc);
2126         }
2127       }
2128
2129       Set<FlowNode> returnNodeSet = fg.getReturnNodeSet();
2130
2131       skip: for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
2132         FlowNode returnNode = (FlowNode) iterator.next();
2133         CompositeLocation inferReturnLoc =
2134             generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode));
2135         if (inferReturnLoc.get(0).getLocIdentifier().equals("this")) {
2136           // if the location type of the return value matches "this" reference
2137           // then, check whether this return value is equal to/lower than all
2138           // of
2139           // parameters that possibly flow into the return values
2140           for (Iterator iterator2 = inferParamLocSet.iterator(); iterator2.hasNext();) {
2141             CompositeLocation paramInferLoc = (CompositeLocation) iterator2.next();
2142
2143             if ((!paramInferLoc.equals(inferReturnLoc))
2144                 && !isGreaterThan(methodLattice, paramInferLoc, inferReturnLoc)) {
2145               continue skip;
2146             }
2147           }
2148           inferFieldReturnLocSet.add(inferReturnLoc);
2149
2150         }
2151       }
2152
2153       if (inferFieldReturnLocSet.size() > 0) {
2154
2155         CompositeLocation returnLoc = getLowest(methodLattice, inferFieldReturnLocSet);
2156         if (returnLoc == null) {
2157           // in this case, assign <'this',bottom> to the RETURNLOC
2158           returnLoc = new CompositeLocation(new Location(md, md.getThis().getSymbol()));
2159           returnLoc.addLocation(new Location(md.getClassDesc(), getLattice(md.getClassDesc())
2160               .getBottomItem()));
2161         }
2162         methodInfo.setReturnLoc(returnLoc);
2163
2164       } else {
2165         String returnLocSymbol = "RETURNLOC";
2166         CompositeLocation returnLocInferLoc =
2167             new CompositeLocation(new Location(md, returnLocSymbol));
2168         methodInfo.setReturnLoc(returnLocInferLoc);
2169
2170         for (Iterator iterator = paramIdxSet.iterator(); iterator.hasNext();) {
2171           Integer paramIdx = (Integer) iterator.next();
2172           CompositeLocation inferLoc = mapParamToLoc.get(paramIdx);
2173           String paramLocLocalSymbol = inferLoc.get(0).getLocIdentifier();
2174           if (!methodLattice.isGreaterThan(paramLocLocalSymbol, returnLocSymbol)) {
2175             // TODO
2176             // addRelationHigherToLower(methodLattice, methodInfo,
2177             // paramLocLocalSymbol,
2178             // returnLocSymbol);
2179           }
2180         }
2181
2182         for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
2183           FlowNode returnNode = (FlowNode) iterator.next();
2184           CompositeLocation inferLoc =
2185               generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode));
2186           if (!isGreaterThan(methodLattice, inferLoc, returnLocInferLoc)) {
2187             // TODO
2188             // addRelation(methodLattice, methodInfo, inferLoc,
2189             // returnLocInferLoc);
2190           }
2191         }
2192
2193       }
2194
2195     }
2196   }
2197
2198   private Set<String> getHigherLocSymbolThan(SSJavaLattice<String> lattice, String loc) {
2199     Set<String> higherLocSet = new HashSet<String>();
2200
2201     Set<String> locSet = lattice.getTable().keySet();
2202     for (Iterator iterator = locSet.iterator(); iterator.hasNext();) {
2203       String element = (String) iterator.next();
2204       if (lattice.isGreaterThan(element, loc) && (!element.equals(lattice.getTopItem()))) {
2205         higherLocSet.add(element);
2206       }
2207     }
2208     return higherLocSet;
2209   }
2210
2211   private CompositeLocation getLowest(SSJavaLattice<String> methodLattice,
2212       Set<CompositeLocation> set) {
2213
2214     CompositeLocation lowest = set.iterator().next();
2215
2216     if (set.size() == 1) {
2217       return lowest;
2218     }
2219
2220     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
2221       CompositeLocation loc = (CompositeLocation) iterator.next();
2222
2223       if ((!loc.equals(lowest)) && (!isComparable(methodLattice, lowest, loc))) {
2224         // if there is a case where composite locations are incomparable, just
2225         // return null
2226         return null;
2227       }
2228
2229       if ((!loc.equals(lowest)) && isGreaterThan(methodLattice, lowest, loc)) {
2230         lowest = loc;
2231       }
2232     }
2233     return lowest;
2234   }
2235
2236   private boolean isComparable(SSJavaLattice<String> methodLattice, CompositeLocation comp1,
2237       CompositeLocation comp2) {
2238
2239     int size = comp1.getSize() >= comp2.getSize() ? comp2.getSize() : comp1.getSize();
2240
2241     for (int idx = 0; idx < size; idx++) {
2242       Location loc1 = comp1.get(idx);
2243       Location loc2 = comp2.get(idx);
2244
2245       Descriptor desc1 = loc1.getDescriptor();
2246       Descriptor desc2 = loc2.getDescriptor();
2247
2248       if (!desc1.equals(desc2)) {
2249         throw new Error("Fail to compare " + comp1 + " and " + comp2);
2250       }
2251
2252       String symbol1 = loc1.getLocIdentifier();
2253       String symbol2 = loc2.getLocIdentifier();
2254
2255       SSJavaLattice<String> lattice;
2256       if (idx == 0) {
2257         lattice = methodLattice;
2258       } else {
2259         lattice = getLattice(desc1);
2260       }
2261
2262       if (symbol1.equals(symbol2)) {
2263         continue;
2264       } else if (!lattice.isComparable(symbol1, symbol2)) {
2265         return false;
2266       }
2267
2268     }
2269
2270     return true;
2271   }
2272
2273   private boolean isGreaterThan(SSJavaLattice<String> methodLattice, CompositeLocation comp1,
2274       CompositeLocation comp2) {
2275
2276     int size = comp1.getSize() >= comp2.getSize() ? comp2.getSize() : comp1.getSize();
2277
2278     for (int idx = 0; idx < size; idx++) {
2279       Location loc1 = comp1.get(idx);
2280       Location loc2 = comp2.get(idx);
2281
2282       Descriptor desc1 = loc1.getDescriptor();
2283       Descriptor desc2 = loc2.getDescriptor();
2284
2285       if (!desc1.equals(desc2)) {
2286         throw new Error("Fail to compare " + comp1 + " and " + comp2);
2287       }
2288
2289       String symbol1 = loc1.getLocIdentifier();
2290       String symbol2 = loc2.getLocIdentifier();
2291
2292       SSJavaLattice<String> lattice;
2293       if (idx == 0) {
2294         lattice = methodLattice;
2295       } else {
2296         lattice = getLattice(desc1);
2297       }
2298
2299       if (symbol1.equals(symbol2)) {
2300         continue;
2301       } else if (lattice.isGreaterThan(symbol1, symbol2)) {
2302         return true;
2303       } else {
2304         return false;
2305       }
2306
2307     }
2308
2309     return false;
2310   }
2311
2312   private void contributeCalleeFlows(MethodInvokeNode min, MethodDescriptor mdCaller,
2313       MethodDescriptor mdCallee) {
2314
2315     System.out.println("\n##contributeCalleeFlows callee=" + mdCallee + "TO caller=" + mdCaller);
2316
2317     getSubGlobalFlowGraph(mdCallee);
2318
2319   }
2320
2321   private GlobalFlowGraph getSubGlobalFlowGraph(MethodDescriptor md) {
2322     return mapMethodDescriptorToSubGlobalFlowGraph.get(md);
2323   }
2324
2325   private void propagateFlowsToCallerWithNoCompositeLocation(MethodInvokeNode min,
2326       MethodDescriptor mdCaller, MethodDescriptor mdCallee) {
2327
2328     System.out.println("\n##PROPAGATE callee=" + mdCallee + "TO caller=" + mdCaller);
2329
2330     // if the parameter A reaches to the parameter B
2331     // then, add an edge the argument A -> the argument B to the caller's flow
2332     // graph
2333
2334     FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
2335     FlowGraph callerFlowGraph = getFlowGraph(mdCaller);
2336     int numParam = calleeFlowGraph.getNumParameters();
2337
2338     for (int i = 0; i < numParam; i++) {
2339       for (int k = 0; k < numParam; k++) {
2340
2341         if (i != k) {
2342
2343           FlowNode paramNode1 = calleeFlowGraph.getParamFlowNode(i);
2344           FlowNode paramNode2 = calleeFlowGraph.getParamFlowNode(k);
2345
2346           NTuple<Descriptor> arg1Tuple = getNodeTupleByArgIdx(min, i);
2347           NTuple<Descriptor> arg2Tuple = getNodeTupleByArgIdx(min, k);
2348
2349           // check if the callee propagates an ordering constraints through
2350           // parameters
2351
2352           Set<FlowNode> localReachSet = calleeFlowGraph.getLocalReachFlowNodeSetFrom(paramNode1);
2353
2354           if (arg1Tuple.size() > 0 && arg2Tuple.size() > 2 && localReachSet.contains(paramNode2)) {
2355             // need to propagate an ordering relation s.t. arg1 is higher
2356             // than arg2
2357
2358             System.out.println("-param1=" + paramNode1 + " is higher than param2=" + paramNode2);
2359             System.out
2360                 .println("-arg1Tuple=" + arg1Tuple + " is higher than arg2Tuple=" + arg2Tuple);
2361
2362             // otherwise, flows between method/field locations...
2363             callerFlowGraph.addValueFlowEdge(arg1Tuple, arg2Tuple);
2364             System.out.println("arg1=" + arg1Tuple + "   arg2=" + arg2Tuple);
2365
2366           }
2367
2368           System.out.println();
2369         }
2370       }
2371     }
2372     System.out.println("##\n");
2373
2374   }
2375
2376   private void propagateFlowsToCaller(MethodInvokeNode min, MethodDescriptor mdCaller,
2377       MethodDescriptor mdCallee) {
2378
2379     System.out.println("\n##PROPAGATE callee=" + mdCallee + "TO caller=" + mdCaller);
2380
2381     // if the parameter A reaches to the parameter B
2382     // then, add an edge the argument A -> the argument B to the caller's flow
2383     // graph
2384
2385     // TODO
2386     // also if a parameter is a composite location and is started with "this"
2387     // reference,
2388     // need to make sure that the corresponding argument is higher than the
2389     // translated location of
2390     // the parameter.
2391
2392     FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
2393     FlowGraph callerFlowGraph = getFlowGraph(mdCaller);
2394     int numParam = calleeFlowGraph.getNumParameters();
2395
2396     for (int i = 0; i < numParam; i++) {
2397       for (int k = 0; k < numParam; k++) {
2398
2399         if (i != k) {
2400
2401           FlowNode paramNode1 = calleeFlowGraph.getParamFlowNode(i);
2402           FlowNode paramNode2 = calleeFlowGraph.getParamFlowNode(k);
2403
2404           System.out.println("param1=" + paramNode1 + " curDescTuple="
2405               + paramNode1.getCurrentDescTuple());
2406           System.out.println("param2=" + paramNode2 + " curDescTuple="
2407               + paramNode2.getCurrentDescTuple());
2408
2409           // TODO: deprecated method
2410           // NodeTupleSet tupleSetArg1 = getNodeTupleSetByArgIdx(min, i);
2411           // NodeTupleSet tupleSetArg2 = getNodeTupleSetByArgIdx(min, k);
2412           NodeTupleSet tupleSetArg1 = null;
2413           NodeTupleSet tupleSetArg2 = null;
2414
2415           for (Iterator<NTuple<Descriptor>> iter1 = tupleSetArg1.iterator(); iter1.hasNext();) {
2416             NTuple<Descriptor> arg1Tuple = iter1.next();
2417
2418             for (Iterator<NTuple<Descriptor>> iter2 = tupleSetArg2.iterator(); iter2.hasNext();) {
2419               NTuple<Descriptor> arg2Tuple = iter2.next();
2420
2421               // check if the callee propagates an ordering constraints through
2422               // parameters
2423
2424               Set<FlowNode> localReachSet =
2425                   calleeFlowGraph.getLocalReachFlowNodeSetFrom(paramNode1);
2426
2427               if (localReachSet.contains(paramNode2)) {
2428                 // need to propagate an ordering relation s.t. arg1 is higher
2429                 // than arg2
2430
2431                 System.out
2432                     .println("-param1=" + paramNode1 + " is higher than param2=" + paramNode2);
2433                 System.out.println("-arg1Tuple=" + arg1Tuple + " is higher than arg2Tuple="
2434                     + arg2Tuple);
2435
2436                 if (!min.getMethod().isStatic()) {
2437                   // check if this is the case that values flow to/from the
2438                   // current object reference 'this'
2439
2440                   NTuple<Descriptor> baseTuple = mapMethodInvokeNodeToBaseTuple.get(min);
2441                   Descriptor baseRef = baseTuple.get(baseTuple.size() - 1);
2442
2443                   System.out.println("paramNode1.getCurrentDescTuple()="
2444                       + paramNode1.getCurrentDescTuple());
2445                   // calculate the prefix of the argument
2446
2447                   if (arg2Tuple.size() == 1 && arg2Tuple.get(0).equals(baseRef)) {
2448                     // in this case, the callee flow causes a caller flow to the
2449                     // object whose method
2450                     // is invoked.
2451
2452                     if (!paramNode1.getCurrentDescTuple().startsWith(mdCallee.getThis())) {
2453                       // check whether ???
2454
2455                       NTuple<Descriptor> param1Prefix =
2456                           calculatePrefixForParam(callerFlowGraph, calleeFlowGraph, min, arg1Tuple,
2457                               paramNode1);
2458
2459                       if (param1Prefix != null && param1Prefix.startsWith(mdCallee.getThis())) {
2460                         // in this case, we need to create a new edge
2461                         // 'this.FIELD'->'this'
2462                         // but we couldn't... instead we assign a new composite
2463                         // location started
2464                         // with 'this' reference to the corresponding parameter
2465
2466                         CompositeLocation compLocForParam1 =
2467                             generateCompositeLocation(mdCallee, param1Prefix);
2468
2469                         System.out
2470                             .println("set comp loc=" + compLocForParam1 + " to " + paramNode1);
2471                         paramNode1.setCompositeLocation(compLocForParam1);
2472
2473                         // then, we need to make sure that the corresponding
2474                         // argument in the caller
2475                         // is required to be higher than or equal to the
2476                         // translated parameter
2477                         // location
2478
2479                         NTuple<Descriptor> translatedParamTuple =
2480                             translateCompositeLocationToCaller(min, compLocForParam1);
2481
2482                         // TODO : check if the arg >= the tranlated parameter
2483
2484                         System.out.println("add a flow edge= " + arg1Tuple + "->"
2485                             + translatedParamTuple);
2486                         callerFlowGraph.addValueFlowEdge(arg1Tuple, translatedParamTuple);
2487
2488                         continue;
2489
2490                       }
2491
2492                     } else {
2493                       // param1 has already been assigned a composite location
2494
2495                       System.out.println("--param1 has already been assigned a composite location");
2496                       CompositeLocation compLocForParam1 = paramNode1.getCompositeLocation();
2497                       NTuple<Descriptor> translatedParamTuple =
2498                           translateCompositeLocationToCaller(min, compLocForParam1);
2499
2500                       // TODO : check if the arg >= the tranlated parameter
2501
2502                       System.out.println("add a flow edge= " + arg1Tuple + "->"
2503                           + translatedParamTuple);
2504                       callerFlowGraph.addValueFlowEdge(arg1Tuple, translatedParamTuple);
2505
2506                       continue;
2507
2508                     }
2509
2510                   } else if (arg1Tuple.size() == 1 && arg1Tuple.get(0).equals(baseRef)) {
2511                     // in this case, the callee flow causes a caller flow
2512                     // originated from the object
2513                     // whose
2514                     // method is invoked.
2515
2516                     System.out.println("###FROM CASE");
2517
2518                     if (!paramNode2.getCurrentDescTuple().startsWith(mdCallee.getThis())) {
2519
2520                       NTuple<Descriptor> param2Prefix =
2521                           calculatePrefixForParam(callerFlowGraph, calleeFlowGraph, min, arg2Tuple,
2522                               paramNode2);
2523
2524                       if (param2Prefix != null && param2Prefix.startsWith(mdCallee.getThis())) {
2525                         // in this case, we need to create a new edge 'this' ->
2526                         // 'this.FIELD' but we couldn't... instead we assign the
2527                         // corresponding
2528                         // parameter a new composite location started with
2529                         // 'this' reference
2530
2531                         CompositeLocation compLocForParam2 =
2532                             generateCompositeLocation(mdCallee, param2Prefix);
2533
2534                         // System.out.println("set comp loc=" + compLocForParam2
2535                         // +
2536                         // " to " + paramNode2);
2537                         paramNode1.setCompositeLocation(compLocForParam2);
2538                         continue;
2539                       }
2540                     }
2541
2542                   }
2543                 }
2544
2545                 // otherwise, flows between method/field locations...
2546                 callerFlowGraph.addValueFlowEdge(arg1Tuple, arg2Tuple);
2547                 System.out.println("arg1=" + arg1Tuple + "   arg2=" + arg2Tuple);
2548
2549               }
2550
2551             }
2552
2553           }
2554           System.out.println();
2555         }
2556       }
2557     }
2558     System.out.println("##\n");
2559   }
2560
2561   private NTuple<Descriptor> translateCompositeLocationToCaller(MethodInvokeNode min,
2562       CompositeLocation compLocForParam1) {
2563     NTuple<Descriptor> baseTuple = mapMethodInvokeNodeToBaseTuple.get(min);
2564
2565     NTuple<Descriptor> tuple = new NTuple<Descriptor>();
2566
2567     for (int i = 0; i < baseTuple.size(); i++) {
2568       tuple.add(baseTuple.get(i));
2569     }
2570
2571     for (int i = 1; i < compLocForParam1.getSize(); i++) {
2572       Location loc = compLocForParam1.get(i);
2573       tuple.add(loc.getLocDescriptor());
2574     }
2575
2576     return tuple;
2577   }
2578
2579   private CompositeLocation generateCompositeLocation(NTuple<Location> prefixLocTuple) {
2580
2581     System.out.println("generateCompositeLocation=" + prefixLocTuple);
2582
2583     CompositeLocation newCompLoc = new CompositeLocation();
2584     for (int i = 0; i < prefixLocTuple.size(); i++) {
2585       newCompLoc.addLocation(prefixLocTuple.get(i));
2586     }
2587
2588     Descriptor lastDescOfPrefix = prefixLocTuple.get(prefixLocTuple.size() - 1).getLocDescriptor();
2589
2590     ClassDescriptor enclosingDescriptor;
2591     if (lastDescOfPrefix instanceof FieldDescriptor) {
2592       enclosingDescriptor = ((FieldDescriptor) lastDescOfPrefix).getType().getClassDesc();
2593       // System.out.println("enclosingDescriptor0=" + enclosingDescriptor);
2594     } else {
2595       // var descriptor case
2596       enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc();
2597     }
2598     // System.out.println("enclosingDescriptor=" + enclosingDescriptor);
2599
2600     LocationDescriptor newLocDescriptor = generateNewLocationDescriptor();
2601     newLocDescriptor.setEnclosingClassDesc(enclosingDescriptor);
2602
2603     Location newLoc = new Location(enclosingDescriptor, newLocDescriptor.getSymbol());
2604     newLoc.setLocDescriptor(newLocDescriptor);
2605     newCompLoc.addLocation(newLoc);
2606
2607     // System.out.println("--newCompLoc=" + newCompLoc);
2608     return newCompLoc;
2609   }
2610
2611   private CompositeLocation generateCompositeLocation(MethodDescriptor md,
2612       NTuple<Descriptor> paramPrefix) {
2613
2614     System.out.println("generateCompositeLocation=" + paramPrefix);
2615
2616     CompositeLocation newCompLoc = convertToCompositeLocation(md, paramPrefix);
2617
2618     Descriptor lastDescOfPrefix = paramPrefix.get(paramPrefix.size() - 1);
2619     // System.out.println("lastDescOfPrefix=" + lastDescOfPrefix + "  kind="
2620     // + lastDescOfPrefix.getClass());
2621     ClassDescriptor enclosingDescriptor;
2622     if (lastDescOfPrefix instanceof FieldDescriptor) {
2623       enclosingDescriptor = ((FieldDescriptor) lastDescOfPrefix).getType().getClassDesc();
2624       // System.out.println("enclosingDescriptor0=" + enclosingDescriptor);
2625     } else {
2626       // var descriptor case
2627       enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc();
2628     }
2629     // System.out.println("enclosingDescriptor=" + enclosingDescriptor);
2630
2631     LocationDescriptor newLocDescriptor = generateNewLocationDescriptor();
2632     newLocDescriptor.setEnclosingClassDesc(enclosingDescriptor);
2633
2634     Location newLoc = new Location(enclosingDescriptor, newLocDescriptor.getSymbol());
2635     newLoc.setLocDescriptor(newLocDescriptor);
2636     newCompLoc.addLocation(newLoc);
2637
2638     // System.out.println("--newCompLoc=" + newCompLoc);
2639     return newCompLoc;
2640   }
2641
2642   private NTuple<Descriptor> calculatePrefixForParam(FlowGraph callerFlowGraph,
2643       FlowGraph calleeFlowGraph, MethodInvokeNode min, NTuple<Descriptor> arg1Tuple,
2644       FlowNode paramNode1) {
2645
2646     NTuple<Descriptor> baseTuple = mapMethodInvokeNodeToBaseTuple.get(min);
2647     Descriptor baseRef = baseTuple.get(baseTuple.size() - 1);
2648     System.out.println("baseRef=" + baseRef);
2649
2650     FlowNode flowNodeArg1 = callerFlowGraph.getFlowNode(arg1Tuple);
2651     List<NTuple<Descriptor>> callerPrefixList = calculatePrefixList(callerFlowGraph, flowNodeArg1);
2652     System.out.println("callerPrefixList=" + callerPrefixList);
2653
2654     List<NTuple<Descriptor>> prefixList = calculatePrefixList(calleeFlowGraph, paramNode1);
2655     System.out.println("###prefixList from node=" + paramNode1 + " =" + prefixList);
2656
2657     List<NTuple<Descriptor>> calleePrefixList =
2658         translatePrefixListToCallee(baseRef, min.getMethod(), callerPrefixList);
2659
2660     System.out.println("calleePrefixList=" + calleePrefixList);
2661
2662     Set<FlowNode> reachNodeSetFromParam1 = calleeFlowGraph.getReachFlowNodeSetFrom(paramNode1);
2663     System.out.println("reachNodeSetFromParam1=" + reachNodeSetFromParam1);
2664
2665     for (int i = 0; i < calleePrefixList.size(); i++) {
2666       NTuple<Descriptor> curPrefix = calleePrefixList.get(i);
2667       Set<NTuple<Descriptor>> reachableCommonPrefixSet = new HashSet<NTuple<Descriptor>>();
2668
2669       for (Iterator iterator2 = reachNodeSetFromParam1.iterator(); iterator2.hasNext();) {
2670         FlowNode reachNode = (FlowNode) iterator2.next();
2671         if (reachNode.getCurrentDescTuple().startsWith(curPrefix)) {
2672           reachableCommonPrefixSet.add(reachNode.getCurrentDescTuple());
2673         }
2674       }
2675
2676       if (!reachableCommonPrefixSet.isEmpty()) {
2677         System.out.println("###REACHABLECOMONPREFIX=" + reachableCommonPrefixSet
2678             + " with curPreFix=" + curPrefix);
2679         return curPrefix;
2680       }
2681
2682     }
2683
2684     return null;
2685   }
2686
2687   private List<NTuple<Descriptor>> translatePrefixListToCallee(Descriptor baseRef,
2688       MethodDescriptor mdCallee, List<NTuple<Descriptor>> callerPrefixList) {
2689
2690     List<NTuple<Descriptor>> calleePrefixList = new ArrayList<NTuple<Descriptor>>();
2691
2692     for (int i = 0; i < callerPrefixList.size(); i++) {
2693       NTuple<Descriptor> prefix = callerPrefixList.get(i);
2694       if (prefix.startsWith(baseRef)) {
2695         NTuple<Descriptor> calleePrefix = new NTuple<Descriptor>();
2696         calleePrefix.add(mdCallee.getThis());
2697         for (int k = 1; k < prefix.size(); k++) {
2698           calleePrefix.add(prefix.get(k));
2699         }
2700         calleePrefixList.add(calleePrefix);
2701       }
2702     }
2703
2704     return calleePrefixList;
2705
2706   }
2707
2708   private List<NTuple<Descriptor>> calculatePrefixList(FlowGraph flowGraph, FlowNode flowNode) {
2709
2710     System.out.println("\n##### calculatePrefixList=" + flowNode);
2711
2712     Set<FlowNode> inNodeSet = flowGraph.getIncomingFlowNodeSet(flowNode);
2713     inNodeSet.add(flowNode);
2714
2715     System.out.println("inNodeSet=" + inNodeSet);
2716
2717     List<NTuple<Descriptor>> prefixList = new ArrayList<NTuple<Descriptor>>();
2718
2719     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
2720       FlowNode inNode = (FlowNode) iterator.next();
2721
2722       NTuple<Descriptor> inNodeTuple = inNode.getCurrentDescTuple();
2723
2724       // CompositeLocation inNodeInferredLoc =
2725       // generateInferredCompositeLocation(methodInfo, inNodeTuple);
2726       // NTuple<Location> inNodeInferredLocTuple = inNodeInferredLoc.getTuple();
2727
2728       for (int i = 1; i < inNodeTuple.size(); i++) {
2729         NTuple<Descriptor> prefix = inNodeTuple.subList(0, i);
2730         if (!prefixList.contains(prefix)) {
2731           prefixList.add(prefix);
2732         }
2733       }
2734     }
2735
2736     Collections.sort(prefixList, new Comparator<NTuple<Descriptor>>() {
2737       public int compare(NTuple<Descriptor> arg0, NTuple<Descriptor> arg1) {
2738         int s0 = arg0.size();
2739         int s1 = arg1.size();
2740         if (s0 > s1) {
2741           return -1;
2742         } else if (s0 == s1) {
2743           return 0;
2744         } else {
2745           return 1;
2746         }
2747       }
2748     });
2749
2750     return prefixList;
2751
2752   }
2753
2754   public CompositeLocation convertToCompositeLocation(MethodDescriptor md, NTuple<Descriptor> tuple) {
2755
2756     CompositeLocation compLoc = new CompositeLocation();
2757
2758     Descriptor enclosingDescriptor = md;
2759
2760     for (int i = 0; i < tuple.size(); i++) {
2761       Descriptor curDescriptor = tuple.get(i);
2762       Location locElement = new Location(enclosingDescriptor, curDescriptor.getSymbol());
2763       locElement.setLocDescriptor(curDescriptor);
2764       compLoc.addLocation(locElement);
2765
2766       if (curDescriptor instanceof VarDescriptor) {
2767         enclosingDescriptor = md.getClassDesc();
2768       } else if (curDescriptor instanceof NameDescriptor) {
2769         // it is "GLOBAL LOC" case!
2770         enclosingDescriptor = GLOBALDESC;
2771       } else {
2772         enclosingDescriptor = ((FieldDescriptor) curDescriptor).getClassDescriptor();
2773       }
2774
2775     }
2776
2777     System.out.println("-convertToCompositeLocation from=" + tuple + " to " + compLoc);
2778
2779     return compLoc;
2780   }
2781
2782   private LocationDescriptor generateNewLocationDescriptor() {
2783     return new LocationDescriptor("Loc" + (locSeed++));
2784   }
2785
2786   private int getPrefixIndex(NTuple<Descriptor> tuple1, NTuple<Descriptor> tuple2) {
2787
2788     // return the index where the prefix shared by tuple1 and tuple2 is ended
2789     // if there is no prefix shared by both of them, return -1
2790
2791     int minSize = tuple1.size();
2792     if (minSize > tuple2.size()) {
2793       minSize = tuple2.size();
2794     }
2795
2796     int idx = -1;
2797     for (int i = 0; i < minSize; i++) {
2798       if (!tuple1.get(i).equals(tuple2.get(i))) {
2799         break;
2800       } else {
2801         idx++;
2802       }
2803     }
2804
2805     return idx;
2806   }
2807
2808   private CompositeLocation generateInferredCompositeLocation(MethodLocationInfo methodInfo,
2809       NTuple<Location> tuple) {
2810
2811     // first, retrieve inferred location by the local var descriptor
2812     CompositeLocation inferLoc = new CompositeLocation();
2813
2814     CompositeLocation localVarInferLoc =
2815         methodInfo.getInferLocation(tuple.get(0).getLocDescriptor());
2816
2817     localVarInferLoc.get(0).setLocDescriptor(tuple.get(0).getLocDescriptor());
2818
2819     for (int i = 0; i < localVarInferLoc.getSize(); i++) {
2820       inferLoc.addLocation(localVarInferLoc.get(i));
2821     }
2822
2823     for (int i = 1; i < tuple.size(); i++) {
2824       Location cur = tuple.get(i);
2825       Descriptor enclosingDesc = cur.getDescriptor();
2826       Descriptor curDesc = cur.getLocDescriptor();
2827
2828       Location inferLocElement;
2829       if (curDesc == null) {
2830         // in this case, we have a newly generated location.
2831         inferLocElement = new Location(enclosingDesc, cur.getLocIdentifier());
2832       } else {
2833         String fieldLocSymbol =
2834             getLocationInfo(enclosingDesc).getInferLocation(curDesc).get(0).getLocIdentifier();
2835         inferLocElement = new Location(enclosingDesc, fieldLocSymbol);
2836         inferLocElement.setLocDescriptor(curDesc);
2837       }
2838
2839       inferLoc.addLocation(inferLocElement);
2840
2841     }
2842
2843     assert (inferLoc.get(0).getLocDescriptor().getSymbol() == inferLoc.get(0).getLocIdentifier());
2844     return inferLoc;
2845   }
2846
2847   public LocationInfo getLocationInfo(Descriptor d) {
2848     if (d instanceof MethodDescriptor) {
2849       return getMethodLocationInfo((MethodDescriptor) d);
2850     } else {
2851       return getFieldLocationInfo((ClassDescriptor) d);
2852     }
2853   }
2854
2855   private MethodLocationInfo getMethodLocationInfo(MethodDescriptor md) {
2856
2857     if (!mapMethodDescToMethodLocationInfo.containsKey(md)) {
2858       mapMethodDescToMethodLocationInfo.put(md, new MethodLocationInfo(md));
2859     }
2860
2861     return mapMethodDescToMethodLocationInfo.get(md);
2862
2863   }
2864
2865   private LocationInfo getFieldLocationInfo(ClassDescriptor cd) {
2866
2867     if (!mapClassToLocationInfo.containsKey(cd)) {
2868       mapClassToLocationInfo.put(cd, new LocationInfo(cd));
2869     }
2870
2871     return mapClassToLocationInfo.get(cd);
2872
2873   }
2874
2875   private void addPrefixMapping(Map<NTuple<Location>, Set<NTuple<Location>>> map,
2876       NTuple<Location> prefix, NTuple<Location> element) {
2877
2878     if (!map.containsKey(prefix)) {
2879       map.put(prefix, new HashSet<NTuple<Location>>());
2880     }
2881     map.get(prefix).add(element);
2882   }
2883
2884   private boolean containsNonPrimitiveElement(Set<Descriptor> descSet) {
2885     for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
2886       Descriptor desc = (Descriptor) iterator.next();
2887
2888       if (desc.equals(LocationInference.GLOBALDESC)) {
2889         return true;
2890       } else if (desc instanceof VarDescriptor) {
2891         if (!((VarDescriptor) desc).getType().isPrimitive()) {
2892           return true;
2893         }
2894       } else if (desc instanceof FieldDescriptor) {
2895         if (!((FieldDescriptor) desc).getType().isPrimitive()) {
2896           return true;
2897         }
2898       }
2899
2900     }
2901     return false;
2902   }
2903
2904   private SSJavaLattice<String> getLattice(Descriptor d) {
2905     if (d instanceof MethodDescriptor) {
2906       return getMethodLattice((MethodDescriptor) d);
2907     } else {
2908       return getFieldLattice((ClassDescriptor) d);
2909     }
2910   }
2911
2912   private SSJavaLattice<String> getMethodLattice(MethodDescriptor md) {
2913     if (!md2lattice.containsKey(md)) {
2914       md2lattice.put(md, new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM));
2915     }
2916     return md2lattice.get(md);
2917   }
2918
2919   private void setMethodLattice(MethodDescriptor md, SSJavaLattice<String> lattice) {
2920     md2lattice.put(md, lattice);
2921   }
2922
2923   private void extractFlowsBetweenFields(ClassDescriptor cd, FlowNode srcNode, FlowNode dstNode,
2924       int idx) {
2925
2926     NTuple<Descriptor> srcCurTuple = srcNode.getCurrentDescTuple();
2927     NTuple<Descriptor> dstCurTuple = dstNode.getCurrentDescTuple();
2928
2929     if (srcCurTuple.get(idx).equals(dstCurTuple.get(idx)) && srcCurTuple.size() > (idx + 1)
2930         && dstCurTuple.size() > (idx + 1)) {
2931       // value flow between fields: we don't need to add a binary relation
2932       // for this case
2933
2934       Descriptor desc = srcCurTuple.get(idx);
2935       ClassDescriptor classDesc;
2936
2937       if (idx == 0) {
2938         classDesc = ((VarDescriptor) desc).getType().getClassDesc();
2939       } else {
2940         classDesc = ((FieldDescriptor) desc).getType().getClassDesc();
2941       }
2942
2943       extractFlowsBetweenFields(classDesc, srcNode, dstNode, idx + 1);
2944
2945     } else {
2946
2947       Descriptor srcFieldDesc = srcCurTuple.get(idx);
2948       Descriptor dstFieldDesc = dstCurTuple.get(idx);
2949
2950       // add a new edge
2951       getHierarchyGraph(cd).addEdge(srcFieldDesc, dstFieldDesc);
2952
2953     }
2954
2955   }
2956
2957   public SSJavaLattice<String> getFieldLattice(ClassDescriptor cd) {
2958     if (!cd2lattice.containsKey(cd)) {
2959       cd2lattice.put(cd, new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM));
2960     }
2961     return cd2lattice.get(cd);
2962   }
2963
2964   public LinkedList<MethodDescriptor> computeMethodList() {
2965
2966     Set<MethodDescriptor> toSort = new HashSet<MethodDescriptor>();
2967
2968     setupToAnalyze();
2969
2970     Set<MethodDescriptor> visited = new HashSet<MethodDescriptor>();
2971     Set<MethodDescriptor> reachableCallee = new HashSet<MethodDescriptor>();
2972
2973     while (!toAnalyzeIsEmpty()) {
2974       ClassDescriptor cd = toAnalyzeNext();
2975
2976       setupToAnalazeMethod(cd);
2977       temp_toanalyzeMethodList.removeAll(visited);
2978
2979       while (!toAnalyzeMethodIsEmpty()) {
2980         MethodDescriptor md = toAnalyzeMethodNext();
2981         if ((!visited.contains(md))
2982             && (ssjava.needTobeAnnotated(md) || reachableCallee.contains(md))) {
2983
2984           // creates a mapping from a method descriptor to virtual methods
2985           Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
2986           if (md.isStatic()) {
2987             setPossibleCallees.add(md);
2988           } else {
2989             setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md));
2990           }
2991
2992           Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getCalleeSet(md);
2993           Set<MethodDescriptor> needToAnalyzeCalleeSet = new HashSet<MethodDescriptor>();
2994
2995           for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) {
2996             MethodDescriptor calleemd = (MethodDescriptor) iterator.next();
2997             if ((!ssjava.isTrustMethod(calleemd))
2998                 && (!ssjava.isSSJavaUtil(calleemd.getClassDesc()))) {
2999               if (!visited.contains(calleemd)) {
3000                 temp_toanalyzeMethodList.add(calleemd);
3001               }
3002               reachableCallee.add(calleemd);
3003               needToAnalyzeCalleeSet.add(calleemd);
3004             }
3005           }
3006
3007           mapMethodToCalleeSet.put(md, needToAnalyzeCalleeSet);
3008
3009           visited.add(md);
3010
3011           toSort.add(md);
3012         }
3013       }
3014     }
3015
3016     return ssjava.topologicalSort(toSort);
3017
3018   }
3019
3020   public void constructFlowGraph() {
3021
3022     System.out.println("");
3023     toanalyze_methodDescList = computeMethodList();
3024
3025     LinkedList<MethodDescriptor> methodDescList =
3026         (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
3027
3028     System.out.println("@@@methodDescList=" + methodDescList);
3029     // System.exit(0);
3030
3031     while (!methodDescList.isEmpty()) {
3032       MethodDescriptor md = methodDescList.removeLast();
3033       if (state.SSJAVADEBUG) {
3034         System.out.println();
3035         System.out.println("SSJAVA: Constructing a flow graph: " + md);
3036
3037         // creates a mapping from a parameter descriptor to its index
3038         Map<Descriptor, Integer> mapParamDescToIdx = new HashMap<Descriptor, Integer>();
3039         int offset = 0;
3040         if (!md.isStatic()) {
3041           offset = 1;
3042           mapParamDescToIdx.put(md.getThis(), 0);
3043         }
3044
3045         for (int i = 0; i < md.numParameters(); i++) {
3046           Descriptor paramDesc = (Descriptor) md.getParameter(i);
3047           mapParamDescToIdx.put(paramDesc, new Integer(i + offset));
3048         }
3049
3050         FlowGraph fg = new FlowGraph(md, mapParamDescToIdx);
3051         mapMethodDescriptorToFlowGraph.put(md, fg);
3052
3053         analyzeMethodBody(md.getClassDesc(), md);
3054
3055         // System.out.println("##constructSubGlobalFlowGraph");
3056         // GlobalFlowGraph subGlobalFlowGraph = constructSubGlobalFlowGraph(fg);
3057         // mapMethodDescriptorToSubGlobalFlowGraph.put(md, subGlobalFlowGraph);
3058         //
3059         // // TODO
3060         // System.out.println("##addValueFlowsFromCalleeSubGlobalFlowGraph");
3061         // addValueFlowsFromCalleeSubGlobalFlowGraph(md, subGlobalFlowGraph);
3062         // subGlobalFlowGraph.writeGraph("_SUBGLOBAL");
3063         //
3064         // propagateFlowsFromCalleesWithNoCompositeLocation(md);
3065
3066       }
3067     }
3068     // _debug_printGraph();
3069
3070     methodDescList = (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
3071
3072     while (!methodDescList.isEmpty()) {
3073       MethodDescriptor md = methodDescList.removeLast();
3074       if (state.SSJAVADEBUG) {
3075         System.out.println();
3076         System.out.println("SSJAVA: Constructing a flow graph2: " + md);
3077
3078         System.out.println("##constructSubGlobalFlowGraph");
3079         GlobalFlowGraph subGlobalFlowGraph = constructSubGlobalFlowGraph(getFlowGraph(md));
3080         mapMethodDescriptorToSubGlobalFlowGraph.put(md, subGlobalFlowGraph);
3081
3082         // TODO
3083         System.out.println("##addValueFlowsFromCalleeSubGlobalFlowGraph");
3084         addValueFlowsFromCalleeSubGlobalFlowGraph(md, subGlobalFlowGraph);
3085         subGlobalFlowGraph.writeGraph("_SUBGLOBAL");
3086
3087         propagateFlowsFromCalleesWithNoCompositeLocation(md);
3088
3089       }
3090     }
3091
3092   }
3093
3094   private Set<MethodInvokeNode> getMethodInvokeNodeSet(MethodDescriptor md) {
3095     if (!mapMethodDescriptorToMethodInvokeNodeSet.containsKey(md)) {
3096       mapMethodDescriptorToMethodInvokeNodeSet.put(md, new HashSet<MethodInvokeNode>());
3097     }
3098     return mapMethodDescriptorToMethodInvokeNodeSet.get(md);
3099   }
3100
3101   private void constructSubGlobalFlowGraph(MethodDescriptor md) {
3102
3103     FlowGraph flowGraph = getFlowGraph(md);
3104
3105     Set<MethodInvokeNode> setMethodInvokeNode = getMethodInvokeNodeSet(md);
3106
3107     for (Iterator<MethodInvokeNode> iter = setMethodInvokeNode.iterator(); iter.hasNext();) {
3108       MethodInvokeNode min = iter.next();
3109       propagateFlowsFromMethodInvokeNode(md, min);
3110     }
3111
3112   }
3113
3114   private void propagateFlowsFromMethodInvokeNode(MethodDescriptor mdCaller, MethodInvokeNode min) {
3115     // the transformation for a call site propagates flows through parameters
3116     // if the method is virtual, it also grab all relations from any possible
3117     // callees
3118
3119     MethodDescriptor mdCallee = min.getMethod();
3120     Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
3121     if (mdCallee.isStatic()) {
3122       setPossibleCallees.add(mdCallee);
3123     } else {
3124       Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getMethods(mdCallee);
3125       // removes method descriptors that are not invoked by the caller
3126       calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller));
3127       setPossibleCallees.addAll(calleeSet);
3128     }
3129
3130     for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
3131       MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
3132       contributeCalleeFlows(min, mdCaller, possibleMdCallee);
3133     }
3134
3135   }
3136
3137   private void assignCompositeLocation(MethodDescriptor md) {
3138
3139     FlowGraph flowGraph = getFlowGraph(md);
3140
3141     Set<FlowNode> nodeSet = flowGraph.getNodeSet();
3142
3143     next: for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
3144       FlowNode flowNode = (FlowNode) iterator.next();
3145
3146       // assign a composite location only to the local variable
3147       if (flowNode.getCurrentDescTuple().size() == 1) {
3148
3149         List<NTuple<Descriptor>> prefixList = calculatePrefixList(flowGraph, flowNode);
3150         Set<FlowNode> reachSet = flowGraph.getReachFlowNodeSetFrom(flowNode);
3151
3152         for (int i = 0; i < prefixList.size(); i++) {
3153           NTuple<Descriptor> curPrefix = prefixList.get(i);
3154           Set<NTuple<Descriptor>> reachableCommonPrefixSet = new HashSet<NTuple<Descriptor>>();
3155
3156           for (Iterator iterator2 = reachSet.iterator(); iterator2.hasNext();) {
3157             FlowNode reachNode = (FlowNode) iterator2.next();
3158             if (reachNode.getCurrentDescTuple().startsWith(curPrefix)) {
3159               reachableCommonPrefixSet.add(reachNode.getCurrentDescTuple());
3160             }
3161           }
3162
3163           if (!reachableCommonPrefixSet.isEmpty()) {
3164             System.out.println("NEED TO ASSIGN COMP LOC TO " + flowNode + " with prefix="
3165                 + curPrefix);
3166             CompositeLocation newCompLoc = generateCompositeLocation(md, curPrefix);
3167             flowNode.setCompositeLocation(newCompLoc);
3168             continue next;
3169           }
3170
3171         }
3172       }
3173
3174     }
3175
3176   }
3177
3178   private void propagateFlowsFromCalleesWithNoCompositeLocation(MethodDescriptor mdCaller) {
3179
3180     // the transformation for a call site propagates flows through parameters
3181     // if the method is virtual, it also grab all relations from any possible
3182     // callees
3183
3184     Set<MethodInvokeNode> setMethodInvokeNode =
3185         mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller);
3186
3187     if (setMethodInvokeNode != null) {
3188
3189       for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) {
3190         MethodInvokeNode min = (MethodInvokeNode) iterator.next();
3191         MethodDescriptor mdCallee = min.getMethod();
3192         Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
3193         if (mdCallee.isStatic()) {
3194           setPossibleCallees.add(mdCallee);
3195         } else {
3196           Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getMethods(mdCallee);
3197           // removes method descriptors that are not invoked by the caller
3198           calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller));
3199           setPossibleCallees.addAll(calleeSet);
3200         }
3201
3202         for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
3203           MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
3204           propagateFlowsToCallerWithNoCompositeLocation(min, mdCaller, possibleMdCallee);
3205         }
3206
3207       }
3208     }
3209
3210   }
3211
3212   private void propagateFlowsFromCallees(MethodDescriptor mdCaller) {
3213
3214     // the transformation for a call site propagates flows through parameters
3215     // if the method is virtual, it also grab all relations from any possible
3216     // callees
3217
3218     Set<MethodInvokeNode> setMethodInvokeNode =
3219         mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller);
3220
3221     if (setMethodInvokeNode != null) {
3222
3223       for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) {
3224         MethodInvokeNode min = (MethodInvokeNode) iterator.next();
3225         MethodDescriptor mdCallee = min.getMethod();
3226         Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
3227         if (mdCallee.isStatic()) {
3228           setPossibleCallees.add(mdCallee);
3229         } else {
3230           Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getMethods(mdCallee);
3231           // removes method descriptors that are not invoked by the caller
3232           calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller));
3233           setPossibleCallees.addAll(calleeSet);
3234         }
3235
3236         for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
3237           MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
3238           propagateFlowsToCaller(min, mdCaller, possibleMdCallee);
3239         }
3240
3241       }
3242     }
3243
3244   }
3245
3246   private void analyzeMethodBody(ClassDescriptor cd, MethodDescriptor md) {
3247     BlockNode bn = state.getMethodBody(md);
3248     NodeTupleSet implicitFlowTupleSet = new NodeTupleSet();
3249     analyzeFlowBlockNode(md, md.getParameterTable(), bn, implicitFlowTupleSet);
3250   }
3251
3252   private void analyzeFlowBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn,
3253       NodeTupleSet implicitFlowTupleSet) {
3254
3255     bn.getVarTable().setParent(nametable);
3256     for (int i = 0; i < bn.size(); i++) {
3257       BlockStatementNode bsn = bn.get(i);
3258       analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet);
3259     }
3260
3261   }
3262
3263   private void analyzeBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
3264       BlockStatementNode bsn, NodeTupleSet implicitFlowTupleSet) {
3265
3266     switch (bsn.kind()) {
3267     case Kind.BlockExpressionNode:
3268       analyzeBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn, implicitFlowTupleSet);
3269       break;
3270
3271     case Kind.DeclarationNode:
3272       analyzeFlowDeclarationNode(md, nametable, (DeclarationNode) bsn, implicitFlowTupleSet);
3273       break;
3274
3275     case Kind.IfStatementNode:
3276       analyzeFlowIfStatementNode(md, nametable, (IfStatementNode) bsn, implicitFlowTupleSet);
3277       break;
3278
3279     case Kind.LoopNode:
3280       analyzeFlowLoopNode(md, nametable, (LoopNode) bsn, implicitFlowTupleSet);
3281       break;
3282
3283     case Kind.ReturnNode:
3284       analyzeFlowReturnNode(md, nametable, (ReturnNode) bsn, implicitFlowTupleSet);
3285       break;
3286
3287     case Kind.SubBlockNode:
3288       analyzeFlowSubBlockNode(md, nametable, (SubBlockNode) bsn, implicitFlowTupleSet);
3289       break;
3290
3291     case Kind.ContinueBreakNode:
3292       break;
3293
3294     case Kind.SwitchStatementNode:
3295       analyzeSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn, implicitFlowTupleSet);
3296       break;
3297
3298     }
3299
3300   }
3301
3302   private void analyzeSwitchBlockNode(MethodDescriptor md, SymbolTable nametable,
3303       SwitchBlockNode sbn, NodeTupleSet implicitFlowTupleSet) {
3304
3305     analyzeFlowBlockNode(md, nametable, sbn.getSwitchBlockStatement(), implicitFlowTupleSet);
3306
3307   }
3308
3309   private void analyzeSwitchStatementNode(MethodDescriptor md, SymbolTable nametable,
3310       SwitchStatementNode ssn, NodeTupleSet implicitFlowTupleSet) {
3311
3312     NodeTupleSet condTupleNode = new NodeTupleSet();
3313     analyzeFlowExpressionNode(md, nametable, ssn.getCondition(), condTupleNode, null,
3314         implicitFlowTupleSet, false);
3315
3316     NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
3317
3318     newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
3319     newImplicitTupleSet.addTupleSet(condTupleNode);
3320
3321     if (newImplicitTupleSet.size() > 1) {
3322       // need to create an intermediate node for the GLB of conditional
3323       // locations & implicit flows
3324       NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
3325       for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) {
3326         NTuple<Descriptor> tuple = idxIter.next();
3327         addFlowGraphEdge(md, tuple, interTuple);
3328       }
3329       newImplicitTupleSet.clear();
3330       newImplicitTupleSet.addTuple(interTuple);
3331     }
3332
3333     BlockNode sbn = ssn.getSwitchBody();
3334     for (int i = 0; i < sbn.size(); i++) {
3335       analyzeSwitchBlockNode(md, nametable, (SwitchBlockNode) sbn.get(i), newImplicitTupleSet);
3336     }
3337
3338   }
3339
3340   private void analyzeFlowSubBlockNode(MethodDescriptor md, SymbolTable nametable,
3341       SubBlockNode sbn, NodeTupleSet implicitFlowTupleSet) {
3342     analyzeFlowBlockNode(md, nametable, sbn.getBlockNode(), implicitFlowTupleSet);
3343   }
3344
3345   private void analyzeFlowReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode rn,
3346       NodeTupleSet implicitFlowTupleSet) {
3347
3348     ExpressionNode returnExp = rn.getReturnExpression();
3349
3350     if (returnExp != null) {
3351       NodeTupleSet nodeSet = new NodeTupleSet();
3352       // if a return expression returns a literal value, nodeSet is empty
3353       analyzeFlowExpressionNode(md, nametable, returnExp, nodeSet, false);
3354       FlowGraph fg = getFlowGraph(md);
3355
3356       // if (implicitFlowTupleSet.size() == 1
3357       // &&
3358       // fg.getFlowNode(implicitFlowTupleSet.iterator().next()).isIntermediate())
3359       // {
3360       //
3361       // // since there is already an intermediate node for the GLB of implicit
3362       // flows
3363       // // we don't need to create another intermediate node.
3364       // // just re-use the intermediate node for implicit flows.
3365       //
3366       // FlowNode meetNode =
3367       // fg.getFlowNode(implicitFlowTupleSet.iterator().next());
3368       //
3369       // for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
3370       // NTuple<Descriptor> returnNodeTuple = (NTuple<Descriptor>)
3371       // iterator.next();
3372       // fg.addValueFlowEdge(returnNodeTuple, meetNode.getDescTuple());
3373       // }
3374       //
3375       // }
3376
3377       NodeTupleSet currentFlowTupleSet = new NodeTupleSet();
3378
3379       // add tuples from return node
3380       currentFlowTupleSet.addTupleSet(nodeSet);
3381
3382       // add tuples corresponding to the current implicit flows
3383       currentFlowTupleSet.addTupleSet(implicitFlowTupleSet);
3384
3385       if (currentFlowTupleSet.size() > 1) {
3386         FlowNode meetNode = fg.createIntermediateNode();
3387         for (Iterator iterator = currentFlowTupleSet.iterator(); iterator.hasNext();) {
3388           NTuple<Descriptor> currentFlowTuple = (NTuple<Descriptor>) iterator.next();
3389           fg.addValueFlowEdge(currentFlowTuple, meetNode.getDescTuple());<