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