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