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