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