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