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