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);
3888         highestSet.add(curLocTuple);
3889
3890       }
3891     }
3892
3893     return highestSet;
3894
3895   }
3896
3897   private Set<String> getHigherLocSymbolThan(SSJavaLattice<String> lattice, String loc) {
3898     Set<String> higherLocSet = new HashSet<String>();
3899
3900     Set<String> locSet = lattice.getTable().keySet();
3901     for (Iterator iterator = locSet.iterator(); iterator.hasNext();) {
3902       String element = (String) iterator.next();
3903       if (lattice.isGreaterThan(element, loc) && (!element.equals(lattice.getTopItem()))) {
3904         higherLocSet.add(element);
3905       }
3906     }
3907     return higherLocSet;
3908   }
3909
3910   private CompositeLocation getLowest(SSJavaLattice<String> methodLattice,
3911       Set<CompositeLocation> set) {
3912
3913     CompositeLocation lowest = set.iterator().next();
3914
3915     if (set.size() == 1) {
3916       return lowest;
3917     }
3918
3919     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
3920       CompositeLocation loc = (CompositeLocation) iterator.next();
3921
3922       if ((!loc.equals(lowest)) && (!isComparable(methodLattice, lowest, loc))) {
3923         // if there is a case where composite locations are incomparable, just
3924         // return null
3925         return null;
3926       }
3927
3928       if ((!loc.equals(lowest)) && isGreaterThan(methodLattice, lowest, loc)) {
3929         lowest = loc;
3930       }
3931     }
3932     return lowest;
3933   }
3934
3935   private boolean isComparable(SSJavaLattice<String> methodLattice, CompositeLocation comp1,
3936       CompositeLocation comp2) {
3937
3938     int size = comp1.getSize() >= comp2.getSize() ? comp2.getSize() : comp1.getSize();
3939
3940     for (int idx = 0; idx < size; idx++) {
3941       Location loc1 = comp1.get(idx);
3942       Location loc2 = comp2.get(idx);
3943
3944       Descriptor desc1 = loc1.getDescriptor();
3945       Descriptor desc2 = loc2.getDescriptor();
3946
3947       if (!desc1.equals(desc2)) {
3948         throw new Error("Fail to compare " + comp1 + " and " + comp2);
3949       }
3950
3951       String symbol1 = loc1.getLocIdentifier();
3952       String symbol2 = loc2.getLocIdentifier();
3953
3954       SSJavaLattice<String> lattice;
3955       if (idx == 0) {
3956         lattice = methodLattice;
3957       } else {
3958         lattice = getLattice(desc1);
3959       }
3960
3961       if (symbol1.equals(symbol2)) {
3962         continue;
3963       } else if (!lattice.isComparable(symbol1, symbol2)) {
3964         return false;
3965       }
3966
3967     }
3968
3969     return true;
3970   }
3971
3972   private boolean isGreaterThan(SSJavaLattice<String> methodLattice, CompositeLocation comp1,
3973       CompositeLocation comp2) {
3974
3975     int size = comp1.getSize() >= comp2.getSize() ? comp2.getSize() : comp1.getSize();
3976
3977     for (int idx = 0; idx < size; idx++) {
3978       Location loc1 = comp1.get(idx);
3979       Location loc2 = comp2.get(idx);
3980
3981       Descriptor desc1 = loc1.getDescriptor();
3982       Descriptor desc2 = loc2.getDescriptor();
3983
3984       if (!desc1.equals(desc2)) {
3985         throw new Error("Fail to compare " + comp1 + " and " + comp2);
3986       }
3987
3988       String symbol1 = loc1.getLocIdentifier();
3989       String symbol2 = loc2.getLocIdentifier();
3990
3991       SSJavaLattice<String> lattice;
3992       if (idx == 0) {
3993         lattice = methodLattice;
3994       } else {
3995         lattice = getLattice(desc1);
3996       }
3997
3998       if (symbol1.equals(symbol2)) {
3999         continue;
4000       } else if (lattice.isGreaterThan(symbol1, symbol2)) {
4001         return true;
4002       } else {
4003         return false;
4004       }
4005
4006     }
4007
4008     return false;
4009   }
4010
4011   private GlobalFlowGraph getSubGlobalFlowGraph(MethodDescriptor md) {
4012
4013     if (!mapMethodDescriptorToSubGlobalFlowGraph.containsKey(md)) {
4014       mapMethodDescriptorToSubGlobalFlowGraph.put(md, new GlobalFlowGraph(md));
4015     }
4016     return mapMethodDescriptorToSubGlobalFlowGraph.get(md);
4017   }
4018
4019   private void propagateFlowsToCallerWithNoCompositeLocation(MethodInvokeNode min,
4020       MethodDescriptor mdCaller, MethodDescriptor mdCallee) {
4021
4022     System.out.println("-propagateFlowsToCallerWithNoCompositeLocation=" + min.printNode(0));
4023     // if the parameter A reaches to the parameter B
4024     // then, add an edge the argument A -> the argument B to the caller's flow
4025     // graph
4026
4027     FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
4028     FlowGraph callerFlowGraph = getFlowGraph(mdCaller);
4029     int numParam = calleeFlowGraph.getNumParameters();
4030
4031     for (int i = 0; i < numParam; i++) {
4032       for (int k = 0; k < numParam; k++) {
4033
4034         if (i != k) {
4035
4036           FlowNode paramNode1 = calleeFlowGraph.getParamFlowNode(i);
4037           FlowNode paramNode2 = calleeFlowGraph.getParamFlowNode(k);
4038
4039           NTuple<Descriptor> arg1Tuple = getNodeTupleByArgIdx(min, i);
4040           NTuple<Descriptor> arg2Tuple = getNodeTupleByArgIdx(min, k);
4041
4042           // check if the callee propagates an ordering constraints through
4043           // parameters
4044
4045           // Set<FlowNode> localReachSet = calleeFlowGraph.getLocalReachFlowNodeSetFrom(paramNode1);
4046           Set<FlowNode> localReachSet =
4047               calleeFlowGraph.getReachableSetFrom(paramNode1.getDescTuple());
4048
4049           NTuple<Descriptor> paramDescTuple1 = paramNode1.getCurrentDescTuple();
4050           NTuple<Descriptor> paramDescTuple2 = paramNode2.getCurrentDescTuple();
4051
4052           // System.out.println("-param1CurTuple=" + paramDescTuple1 + " param2CurTuple="
4053           // + paramDescTuple2);
4054           // System.out.println("-- localReachSet from param1=" + localReachSet);
4055
4056           if (paramDescTuple1.get(0).equals(paramDescTuple2.get(0))) {
4057             // if two parameters share the same prefix
4058             // it already has been assigned to a composite location
4059             // so we don't need to add an additional ordering relation caused by these two
4060             // paramters.
4061             continue;
4062           }
4063
4064           if (arg1Tuple.size() > 0 && arg2Tuple.size() > 0
4065               && containsPrefix(paramNode2.getDescTuple().get(0), localReachSet)) {
4066             // need to propagate an ordering relation s.t. arg1 is higher
4067             // than arg2
4068             // System.out.println("-param1=" + paramNode1 + " is higher than param2=" + paramNode2);
4069
4070             // add a new flow between the corresponding arguments.
4071             callerFlowGraph.addValueFlowEdge(arg1Tuple, arg2Tuple);
4072             // System.out.println("arg1=" + arg1Tuple + "   arg2=" + arg2Tuple);
4073
4074             // System.out
4075             // .println("-arg1Tuple=" + arg1Tuple + " is higher than arg2Tuple=" + arg2Tuple);
4076
4077           }
4078
4079           // System.out.println();
4080         }
4081       }
4082     }
4083
4084     // if a parameter has a composite location and the first element of the parameter location
4085     // matches the callee's 'this'
4086     // we have a more specific constraint: the caller's corresponding argument is higher than the
4087     // parameter location which is translated into the caller
4088
4089     for (int idx = 0; idx < numParam; idx++) {
4090       FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx);
4091       CompositeLocation compLoc = paramNode.getCompositeLocation();
4092       System.out.println("paramNode=" + paramNode + "   compLoc=" + compLoc);
4093       if (compLoc != null && compLoc.get(0).getLocDescriptor().equals(min.getMethod().getThis())) {
4094         System.out.println("$$$COMPLOC CASE=" + compLoc + "  idx=" + idx);
4095
4096         NTuple<Descriptor> argTuple = getNodeTupleByArgIdx(min, idx);
4097         System.out.println("--- argTuple=" + argTuple + " current compLoc="
4098             + callerFlowGraph.getFlowNode(argTuple).getCompositeLocation());
4099
4100         NTuple<Descriptor> translatedParamTuple =
4101             translateCompositeLocationToCaller(idx, min, compLoc);
4102         System.out.println("add a flow edge= " + argTuple + "->" + translatedParamTuple);
4103         callerFlowGraph.addValueFlowEdge(argTuple, translatedParamTuple);
4104
4105         Set<NTuple<Location>> pcLocTupleSet = getPCLocTupleSet(min);
4106         for (Iterator iterator = pcLocTupleSet.iterator(); iterator.hasNext();) {
4107           NTuple<Location> pcLocTuple = (NTuple<Location>) iterator.next();
4108           callerFlowGraph.addValueFlowEdge(translateToDescTuple(pcLocTuple), translatedParamTuple);
4109         }
4110
4111       }
4112     }
4113
4114   }
4115
4116   private boolean containsPrefix(Descriptor prefixDesc, Set<FlowNode> set) {
4117
4118     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
4119       FlowNode flowNode = (FlowNode) iterator.next();
4120       if (flowNode.getDescTuple().startsWith(prefixDesc)) {
4121         System.out.println("FOUND=" + flowNode);
4122         return true;
4123       }
4124     }
4125     return false;
4126   }
4127
4128   private NTuple<Descriptor> translateCompositeLocationToCaller(int idx, MethodInvokeNode min,
4129       CompositeLocation compLocForParam1) {
4130
4131     NTuple<Descriptor> baseTuple = mapMethodInvokeNodeToBaseTuple.get(min);
4132
4133     NTuple<Descriptor> tuple = new NTuple<Descriptor>();
4134     for (int i = 0; i < baseTuple.size(); i++) {
4135       tuple.add(baseTuple.get(i));
4136     }
4137
4138     for (int i = 1; i < compLocForParam1.getSize(); i++) {
4139       Location loc = compLocForParam1.get(i);
4140       tuple.add(loc.getLocDescriptor());
4141     }
4142
4143     return tuple;
4144   }
4145
4146   private CompositeLocation generateCompositeLocation(NTuple<Location> prefixLocTuple) {
4147
4148     System.out.println("generateCompositeLocation=" + prefixLocTuple);
4149
4150     CompositeLocation newCompLoc = new CompositeLocation();
4151     for (int i = 0; i < prefixLocTuple.size(); i++) {
4152       newCompLoc.addLocation(prefixLocTuple.get(i));
4153     }
4154
4155     Descriptor lastDescOfPrefix = prefixLocTuple.get(prefixLocTuple.size() - 1).getLocDescriptor();
4156
4157     ClassDescriptor enclosingDescriptor;
4158     if (lastDescOfPrefix instanceof FieldDescriptor) {
4159       enclosingDescriptor = ((FieldDescriptor) lastDescOfPrefix).getType().getClassDesc();
4160       // System.out.println("enclosingDescriptor0=" + enclosingDescriptor);
4161     } else if (lastDescOfPrefix.equals(GLOBALDESC)) {
4162       MethodDescriptor currentMethodDesc = (MethodDescriptor) prefixLocTuple.get(0).getDescriptor();
4163       enclosingDescriptor = currentMethodDesc.getClassDesc();
4164     } else {
4165       // var descriptor case
4166       enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc();
4167     }
4168     // System.out.println("enclosingDescriptor=" + enclosingDescriptor);
4169
4170     LocationDescriptor newLocDescriptor = generateNewLocationDescriptor();
4171     newLocDescriptor.setEnclosingClassDesc(enclosingDescriptor);
4172
4173     Location newLoc = new Location(enclosingDescriptor, newLocDescriptor.getSymbol());
4174     newLoc.setLocDescriptor(newLocDescriptor);
4175     newCompLoc.addLocation(newLoc);
4176
4177     // System.out.println("--newCompLoc=" + newCompLoc);
4178     return newCompLoc;
4179   }
4180
4181   private CompositeLocation generateCompositeLocation(MethodDescriptor md,
4182       NTuple<Descriptor> paramPrefix) {
4183
4184     System.out.println("generateCompositeLocation=" + paramPrefix);
4185
4186     CompositeLocation newCompLoc = convertToCompositeLocation(md, paramPrefix);
4187
4188     Descriptor lastDescOfPrefix = paramPrefix.get(paramPrefix.size() - 1);
4189     // System.out.println("lastDescOfPrefix=" + lastDescOfPrefix + "  kind="
4190     // + lastDescOfPrefix.getClass());
4191     ClassDescriptor enclosingDescriptor;
4192     if (lastDescOfPrefix instanceof FieldDescriptor) {
4193       enclosingDescriptor = ((FieldDescriptor) lastDescOfPrefix).getType().getClassDesc();
4194       // System.out.println("enclosingDescriptor0=" + enclosingDescriptor);
4195     } else {
4196       // var descriptor case
4197       enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc();
4198     }
4199     // System.out.println("enclosingDescriptor=" + enclosingDescriptor);
4200
4201     LocationDescriptor newLocDescriptor = generateNewLocationDescriptor();
4202     newLocDescriptor.setEnclosingClassDesc(enclosingDescriptor);
4203
4204     Location newLoc = new Location(enclosingDescriptor, newLocDescriptor.getSymbol());
4205     newLoc.setLocDescriptor(newLocDescriptor);
4206     newCompLoc.addLocation(newLoc);
4207
4208     // System.out.println("--newCompLoc=" + newCompLoc);
4209     return newCompLoc;
4210   }
4211
4212   private List<NTuple<Descriptor>> translatePrefixListToCallee(Descriptor baseRef,
4213       MethodDescriptor mdCallee, List<NTuple<Descriptor>> callerPrefixList) {
4214
4215     List<NTuple<Descriptor>> calleePrefixList = new ArrayList<NTuple<Descriptor>>();
4216
4217     for (int i = 0; i < callerPrefixList.size(); i++) {
4218       NTuple<Descriptor> prefix = callerPrefixList.get(i);
4219       if (prefix.startsWith(baseRef)) {
4220         NTuple<Descriptor> calleePrefix = new NTuple<Descriptor>();
4221         calleePrefix.add(mdCallee.getThis());
4222         for (int k = 1; k < prefix.size(); k++) {
4223           calleePrefix.add(prefix.get(k));
4224         }
4225         calleePrefixList.add(calleePrefix);
4226       }
4227     }
4228
4229     return calleePrefixList;
4230
4231   }
4232
4233   public CompositeLocation convertToCompositeLocation(MethodDescriptor md, NTuple<Descriptor> tuple) {
4234
4235     CompositeLocation compLoc = new CompositeLocation();
4236
4237     Descriptor enclosingDescriptor = md;
4238
4239     for (int i = 0; i < tuple.size(); i++) {
4240       Descriptor curDescriptor = tuple.get(i);
4241       Location locElement = new Location(enclosingDescriptor, curDescriptor.getSymbol());
4242       locElement.setLocDescriptor(curDescriptor);
4243       compLoc.addLocation(locElement);
4244
4245       if (curDescriptor instanceof VarDescriptor) {
4246         enclosingDescriptor = md.getClassDesc();
4247       } else if (curDescriptor instanceof FieldDescriptor) {
4248         enclosingDescriptor = ((FieldDescriptor) curDescriptor).getClassDescriptor();
4249       } else if (curDescriptor instanceof NameDescriptor) {
4250         // it is "GLOBAL LOC" case!
4251         enclosingDescriptor = GLOBALDESC;
4252       } else if (curDescriptor instanceof InterDescriptor) {
4253         enclosingDescriptor = getFlowGraph(md).getEnclosingDescriptor(curDescriptor);
4254       } else {
4255         enclosingDescriptor = null;
4256       }
4257
4258     }
4259
4260     return compLoc;
4261   }
4262
4263   private LocationDescriptor generateNewLocationDescriptor() {
4264     return new LocationDescriptor("Loc" + (locSeed++));
4265   }
4266
4267   private int getPrefixIndex(NTuple<Descriptor> tuple1, NTuple<Descriptor> tuple2) {
4268
4269     // return the index where the prefix shared by tuple1 and tuple2 is ended
4270     // if there is no prefix shared by both of them, return -1
4271
4272     int minSize = tuple1.size();
4273     if (minSize > tuple2.size()) {
4274       minSize = tuple2.size();
4275     }
4276
4277     int idx = -1;
4278     for (int i = 0; i < minSize; i++) {
4279       if (!tuple1.get(i).equals(tuple2.get(i))) {
4280         break;
4281       } else {
4282         idx++;
4283       }
4284     }
4285
4286     return idx;
4287   }
4288
4289   private CompositeLocation generateInferredCompositeLocation(MethodLocationInfo methodInfo,
4290       NTuple<Location> tuple) {
4291
4292     // first, retrieve inferred location by the local var descriptor
4293     CompositeLocation inferLoc = new CompositeLocation();
4294
4295     CompositeLocation localVarInferLoc =
4296         methodInfo.getInferLocation(tuple.get(0).getLocDescriptor());
4297
4298     localVarInferLoc.get(0).setLocDescriptor(tuple.get(0).getLocDescriptor());
4299
4300     for (int i = 0; i < localVarInferLoc.getSize(); i++) {
4301       inferLoc.addLocation(localVarInferLoc.get(i));
4302     }
4303
4304     for (int i = 1; i < tuple.size(); i++) {
4305       Location cur = tuple.get(i);
4306       Descriptor enclosingDesc = cur.getDescriptor();
4307       Descriptor curDesc = cur.getLocDescriptor();
4308
4309       Location inferLocElement;
4310       if (curDesc == null) {
4311         // in this case, we have a newly generated location.
4312         inferLocElement = new Location(enclosingDesc, cur.getLocIdentifier());
4313       } else {
4314         String fieldLocSymbol =
4315             getLocationInfo(enclosingDesc).getInferLocation(curDesc).get(0).getLocIdentifier();
4316         inferLocElement = new Location(enclosingDesc, fieldLocSymbol);
4317         inferLocElement.setLocDescriptor(curDesc);
4318       }
4319
4320       inferLoc.addLocation(inferLocElement);
4321
4322     }
4323
4324     assert (inferLoc.get(0).getLocDescriptor().getSymbol() == inferLoc.get(0).getLocIdentifier());
4325     return inferLoc;
4326   }
4327
4328   public LocationInfo getLocationInfo(Descriptor d) {
4329     if (d instanceof MethodDescriptor) {
4330       return getMethodLocationInfo((MethodDescriptor) d);
4331     } else {
4332       return getFieldLocationInfo((ClassDescriptor) d);
4333     }
4334   }
4335
4336   private MethodLocationInfo getMethodLocationInfo(MethodDescriptor md) {
4337
4338     if (!mapMethodDescToMethodLocationInfo.containsKey(md)) {
4339       mapMethodDescToMethodLocationInfo.put(md, new MethodLocationInfo(md));
4340     }
4341
4342     return mapMethodDescToMethodLocationInfo.get(md);
4343
4344   }
4345
4346   private LocationInfo getFieldLocationInfo(ClassDescriptor cd) {
4347
4348     if (!mapClassToLocationInfo.containsKey(cd)) {
4349       mapClassToLocationInfo.put(cd, new LocationInfo(cd));
4350     }
4351
4352     return mapClassToLocationInfo.get(cd);
4353
4354   }
4355
4356   private void addPrefixMapping(Map<NTuple<Location>, Set<NTuple<Location>>> map,
4357       NTuple<Location> prefix, NTuple<Location> element) {
4358
4359     if (!map.containsKey(prefix)) {
4360       map.put(prefix, new HashSet<NTuple<Location>>());
4361     }
4362     map.get(prefix).add(element);
4363   }
4364
4365   private boolean containsNonPrimitiveElement(Set<Descriptor> descSet) {
4366     for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
4367       Descriptor desc = (Descriptor) iterator.next();
4368
4369       if (desc.equals(LocationInference.GLOBALDESC)) {
4370         return true;
4371       } else if (desc instanceof VarDescriptor) {
4372         if (!((VarDescriptor) desc).getType().isPrimitive()) {
4373           return true;
4374         }
4375       } else if (desc instanceof FieldDescriptor) {
4376         if (!((FieldDescriptor) desc).getType().isPrimitive()) {
4377           return true;
4378         }
4379       }
4380
4381     }
4382     return false;
4383   }
4384
4385   private SSJavaLattice<String> getLattice(Descriptor d) {
4386     if (d instanceof MethodDescriptor) {
4387       return getMethodLattice((MethodDescriptor) d);
4388     } else {
4389       return getFieldLattice((ClassDescriptor) d);
4390     }
4391   }
4392
4393   private SSJavaLattice<String> getMethodLattice(MethodDescriptor md) {
4394     if (!md2lattice.containsKey(md)) {
4395       md2lattice.put(md, new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM));
4396     }
4397     return md2lattice.get(md);
4398   }
4399
4400   private void setMethodLattice(MethodDescriptor md, SSJavaLattice<String> lattice) {
4401     md2lattice.put(md, lattice);
4402   }
4403
4404   private void extractFlowsBetweenFields(ClassDescriptor cd, FlowNode srcNode, FlowNode dstNode,
4405       int idx) {
4406
4407     NTuple<Descriptor> srcCurTuple = srcNode.getCurrentDescTuple();
4408     NTuple<Descriptor> dstCurTuple = dstNode.getCurrentDescTuple();
4409
4410     if (srcCurTuple.get(idx).equals(dstCurTuple.get(idx)) && srcCurTuple.size() > (idx + 1)
4411         && dstCurTuple.size() > (idx + 1)) {
4412       // value flow between fields: we don't need to add a binary relation
4413       // for this case
4414
4415       Descriptor desc = srcCurTuple.get(idx);
4416       ClassDescriptor classDesc;
4417
4418       if (idx == 0) {
4419         classDesc = ((VarDescriptor) desc).getType().getClassDesc();
4420       } else {
4421         if (desc instanceof FieldDescriptor) {
4422           classDesc = ((FieldDescriptor) desc).getType().getClassDesc();
4423         } else {
4424           // this case is that the local variable has a composite location assignment
4425           // the following element after the composite location to the local variable
4426           // has the enclosing descriptor of the local variable
4427           Descriptor localDesc = srcNode.getDescTuple().get(0);
4428           classDesc = ((VarDescriptor) localDesc).getType().getClassDesc();
4429         }
4430       }
4431       extractFlowsBetweenFields(classDesc, srcNode, dstNode, idx + 1);
4432
4433     } else {
4434
4435       Descriptor srcFieldDesc = srcCurTuple.get(idx);
4436       Descriptor dstFieldDesc = dstCurTuple.get(idx);
4437
4438       System.out.println("srcFieldDesc=" + srcFieldDesc + "  dstFieldDesc=" + dstFieldDesc
4439           + "   idx=" + idx);
4440       if (!srcFieldDesc.equals(dstFieldDesc)) {
4441         // add a new edge
4442         System.out.println("-ADD EDGE");
4443         getHierarchyGraph(cd).addEdge(srcFieldDesc, dstFieldDesc);
4444       } else if (!isReference(srcFieldDesc) && !isReference(dstFieldDesc)) {
4445         System.out.println("-ADD EDGE");
4446         getHierarchyGraph(cd).addEdge(srcFieldDesc, dstFieldDesc);
4447       }
4448
4449     }
4450
4451   }
4452
4453   public SSJavaLattice<String> getFieldLattice(ClassDescriptor cd) {
4454     if (!cd2lattice.containsKey(cd)) {
4455       cd2lattice.put(cd, new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM));
4456     }
4457     return cd2lattice.get(cd);
4458   }
4459
4460   public LinkedList<MethodDescriptor> computeMethodList() {
4461
4462     Set<MethodDescriptor> toSort = new HashSet<MethodDescriptor>();
4463
4464     setupToAnalyze();
4465
4466     Set<MethodDescriptor> visited = new HashSet<MethodDescriptor>();
4467     Set<MethodDescriptor> reachableCallee = new HashSet<MethodDescriptor>();
4468
4469     while (!toAnalyzeIsEmpty()) {
4470       ClassDescriptor cd = toAnalyzeNext();
4471
4472       if (cd.getClassName().equals("Object")) {
4473         inheritanceTree = new InheritanceTree<ClassDescriptor>(cd);
4474       }
4475
4476       setupToAnalazeMethod(cd);
4477       temp_toanalyzeMethodList.removeAll(visited);
4478
4479       while (!toAnalyzeMethodIsEmpty()) {
4480         MethodDescriptor md = toAnalyzeMethodNext();
4481         if ((!visited.contains(md))
4482             && (ssjava.needTobeAnnotated(md) || reachableCallee.contains(md))) {
4483
4484           // creates a mapping from a method descriptor to virtual methods
4485           Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
4486           if (md.isStatic()) {
4487             setPossibleCallees.add(md);
4488           } else {
4489             setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md));
4490           }
4491
4492           Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getCalleeSet(md);
4493           Set<MethodDescriptor> needToAnalyzeCalleeSet = new HashSet<MethodDescriptor>();
4494
4495           for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) {
4496             MethodDescriptor calleemd = (MethodDescriptor) iterator.next();
4497             if ((!ssjava.isTrustMethod(calleemd))
4498                 && (!ssjava.isSSJavaUtil(calleemd.getClassDesc()))
4499                 && (!calleemd.getModifiers().isNative())) {
4500               if (!visited.contains(calleemd)) {
4501                 temp_toanalyzeMethodList.add(calleemd);
4502               }
4503               reachableCallee.add(calleemd);
4504               needToAnalyzeCalleeSet.add(calleemd);
4505             }
4506           }
4507
4508           mapMethodToCalleeSet.put(md, needToAnalyzeCalleeSet);
4509
4510           visited.add(md);
4511
4512           toSort.add(md);
4513         }
4514       }
4515     }
4516
4517     return ssjava.topologicalSort(toSort);
4518
4519   }
4520
4521   public boolean isTransitivelyCalledFrom(MethodDescriptor callee, MethodDescriptor caller) {
4522     // if the callee is transitively invoked from the caller
4523     // return true;
4524
4525     int callerIdx = toanalyze_methodDescList.indexOf(caller);
4526     int calleeIdx = toanalyze_methodDescList.indexOf(callee);
4527
4528     if (callerIdx < calleeIdx) {
4529       return true;
4530     }
4531
4532     return false;
4533
4534   }
4535
4536   public void constructFlowGraph() {
4537
4538     System.out.println("");
4539     toanalyze_methodDescList = computeMethodList();
4540
4541     // hack... it seems that there is a problem with topological sorting.
4542     // so String.toString(Object o) is appeared too higher in the call chain.
4543     MethodDescriptor mdToString = null;
4544     for (Iterator iterator = toanalyze_methodDescList.iterator(); iterator.hasNext();) {
4545       MethodDescriptor md = (MethodDescriptor) iterator.next();
4546       if (md.toString().equals("public static String String.valueOf(Object o)")) {
4547         mdToString = md;
4548         break;
4549       }
4550     }
4551     if (mdToString != null) {
4552       toanalyze_methodDescList.remove(mdToString);
4553       toanalyze_methodDescList.addLast(mdToString);
4554     }
4555
4556     LinkedList<MethodDescriptor> methodDescList =
4557         (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
4558
4559     System.out.println("@@@methodDescList=" + methodDescList);
4560     // System.exit(0);
4561
4562     while (!methodDescList.isEmpty()) {
4563       MethodDescriptor md = methodDescList.removeLast();
4564       if (state.SSJAVADEBUG) {
4565         System.out.println();
4566         System.out.println("SSJAVA: Constructing a flow graph: " + md);
4567
4568         // creates a mapping from a parameter descriptor to its index
4569         Map<Descriptor, Integer> mapParamDescToIdx = new HashMap<Descriptor, Integer>();
4570         int offset = 0;
4571         if (!md.isStatic()) {
4572           offset = 1;
4573           mapParamDescToIdx.put(md.getThis(), 0);
4574         }
4575
4576         for (int i = 0; i < md.numParameters(); i++) {
4577           Descriptor paramDesc = (Descriptor) md.getParameter(i);
4578           mapParamDescToIdx.put(paramDesc, new Integer(i + offset));
4579         }
4580
4581         FlowGraph fg = new FlowGraph(md, mapParamDescToIdx);
4582         mapMethodDescriptorToFlowGraph.put(md, fg);
4583
4584         analyzeMethodBody(md.getClassDesc(), md);
4585
4586         // System.out.println("##constructSubGlobalFlowGraph");
4587         // GlobalFlowGraph subGlobalFlowGraph = constructSubGlobalFlowGraph(fg);
4588         // mapMethodDescriptorToSubGlobalFlowGraph.put(md, subGlobalFlowGraph);
4589         //
4590         // // TODO
4591         // System.out.println("##addValueFlowsFromCalleeSubGlobalFlowGraph");
4592         // addValueFlowsFromCalleeSubGlobalFlowGraph(md, subGlobalFlowGraph);
4593         // subGlobalFlowGraph.writeGraph("_SUBGLOBAL");
4594         //
4595         // propagateFlowsFromCalleesWithNoCompositeLocation(md);
4596       }
4597     }
4598     // _debug_printGraph();
4599
4600   }
4601
4602   private void constructGlobalFlowGraph() {
4603     LinkedList<MethodDescriptor> methodDescList =
4604         (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
4605
4606     while (!methodDescList.isEmpty()) {
4607       MethodDescriptor md = methodDescList.removeLast();
4608       if (state.SSJAVADEBUG) {
4609         System.out.println();
4610         System.out.println("SSJAVA: Constructing a sub global flow graph: " + md);
4611
4612         constructSubGlobalFlowGraph(getFlowGraph(md));
4613
4614         // TODO
4615         System.out.println("-add Value Flows From CalleeSubGlobalFlowGraph");
4616         addValueFlowsFromCalleeSubGlobalFlowGraph(md);
4617         // subGlobalFlowGraph.writeGraph("_SUBGLOBAL");
4618
4619         // System.out.println("-propagate Flows From Callees With No CompositeLocation");
4620         // propagateFlowsFromCalleesWithNoCompositeLocation(md);
4621
4622         // mark if a parameter has incoming flows
4623         checkParamNodesInSubGlobalFlowGraph(md);
4624
4625       }
4626     }
4627   }
4628
4629   private void checkParamNodesInSubGlobalFlowGraph(MethodDescriptor md) {
4630     GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
4631     FlowGraph flowGraph = getFlowGraph(md);
4632
4633     Set<FlowNode> paramFlowNodeSet = flowGraph.getParamFlowNodeSet();
4634     for (Iterator iterator = paramFlowNodeSet.iterator(); iterator.hasNext();) {
4635       FlowNode paramFlowNode = (FlowNode) iterator.next();
4636       System.out.println("paramFlowNode=" + paramFlowNode);
4637       NTuple<Descriptor> paramDescTuple = paramFlowNode.getDescTuple();
4638       NTuple<Location> paramLocTuple = translateToLocTuple(md, paramDescTuple);
4639       GlobalFlowNode paramGlobalNode = globalFlowGraph.getFlowNode(paramLocTuple);
4640
4641       Set<GlobalFlowNode> incomingNodeSet =
4642           globalFlowGraph.getIncomingNodeSetByPrefix(paramLocTuple.get(0));
4643
4644       if (incomingNodeSet.size() > 0) {
4645         paramGlobalNode.setParamNodeWithIncomingFlows(true);
4646       }
4647
4648     }
4649   }
4650
4651   private Set<MethodInvokeNode> getMethodInvokeNodeSet(MethodDescriptor md) {
4652     if (!mapMethodDescriptorToMethodInvokeNodeSet.containsKey(md)) {
4653       mapMethodDescriptorToMethodInvokeNodeSet.put(md, new HashSet<MethodInvokeNode>());
4654     }
4655     return mapMethodDescriptorToMethodInvokeNodeSet.get(md);
4656   }
4657
4658   private void propagateFlowsFromCalleesWithNoCompositeLocation(MethodDescriptor mdCaller) {
4659
4660     // the transformation for a call site propagates flows through parameters
4661     // if the method is virtual, it also grab all relations from any possible
4662     // callees
4663
4664     Set<MethodInvokeNode> setMethodInvokeNode =
4665         mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller);
4666
4667     if (setMethodInvokeNode != null) {
4668
4669       for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) {
4670         MethodInvokeNode min = (MethodInvokeNode) iterator.next();
4671         MethodDescriptor mdCallee = min.getMethod();
4672         Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
4673         if (mdCallee.isStatic()) {
4674           setPossibleCallees.add(mdCallee);
4675         } else {
4676           Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getMethods(mdCallee);
4677           // removes method descriptors that are not invoked by the caller
4678           calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller));
4679           setPossibleCallees.addAll(calleeSet);
4680         }
4681
4682         for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
4683           MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
4684           propagateFlowsToCallerWithNoCompositeLocation(min, mdCaller, possibleMdCallee);
4685         }
4686
4687       }
4688     }
4689
4690   }
4691
4692   private void analyzeMethodBody(ClassDescriptor cd, MethodDescriptor md) {
4693     BlockNode bn = state.getMethodBody(md);
4694     NodeTupleSet implicitFlowTupleSet = new NodeTupleSet();
4695     analyzeFlowBlockNode(md, md.getParameterTable(), bn, implicitFlowTupleSet);
4696   }
4697
4698   private void analyzeFlowBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn,
4699       NodeTupleSet implicitFlowTupleSet) {
4700
4701     bn.getVarTable().setParent(nametable);
4702     for (int i = 0; i < bn.size(); i++) {
4703       BlockStatementNode bsn = bn.get(i);
4704       analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet);
4705     }
4706
4707   }
4708
4709   private void analyzeBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
4710       BlockStatementNode bsn, NodeTupleSet implicitFlowTupleSet) {
4711
4712     switch (bsn.kind()) {
4713     case Kind.BlockExpressionNode:
4714       analyzeBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn, implicitFlowTupleSet);
4715       break;
4716
4717     case Kind.DeclarationNode:
4718       analyzeFlowDeclarationNode(md, nametable, (DeclarationNode) bsn, implicitFlowTupleSet);
4719       break;
4720
4721     case Kind.IfStatementNode:
4722       analyzeFlowIfStatementNode(md, nametable, (IfStatementNode) bsn, implicitFlowTupleSet);
4723       break;
4724
4725     case Kind.LoopNode:
4726       analyzeFlowLoopNode(md, nametable, (LoopNode) bsn, implicitFlowTupleSet);
4727       break;
4728
4729     case Kind.ReturnNode:
4730       analyzeFlowReturnNode(md, nametable, (ReturnNode) bsn, implicitFlowTupleSet);
4731       break;
4732
4733     case Kind.SubBlockNode:
4734       analyzeFlowSubBlockNode(md, nametable, (SubBlockNode) bsn, implicitFlowTupleSet);
4735       break;
4736
4737     case Kind.ContinueBreakNode:
4738       break;
4739
4740     case Kind.SwitchStatementNode:
4741       analyzeSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn, implicitFlowTupleSet);
4742       break;
4743
4744     }
4745
4746   }
4747
4748   private void analyzeSwitchBlockNode(MethodDescriptor md, SymbolTable nametable,
4749       SwitchBlockNode sbn, NodeTupleSet implicitFlowTupleSet) {
4750
4751     analyzeFlowBlockNode(md, nametable, sbn.getSwitchBlockStatement(), implicitFlowTupleSet);
4752
4753   }
4754
4755   private void analyzeSwitchStatementNode(MethodDescriptor md, SymbolTable nametable,
4756       SwitchStatementNode ssn, NodeTupleSet implicitFlowTupleSet) {
4757
4758     NodeTupleSet condTupleNode = new NodeTupleSet();
4759     analyzeFlowExpressionNode(md, nametable, ssn.getCondition(), condTupleNode, null,
4760         implicitFlowTupleSet, false);
4761
4762     NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
4763
4764     newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
4765     newImplicitTupleSet.addTupleSet(condTupleNode);
4766
4767     if (needToGenerateInterLoc(newImplicitTupleSet)) {
4768       // need to create an intermediate node for the GLB of conditional
4769       // locations & implicit flows
4770       System.out.println("10");
4771
4772       NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
4773       for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) {
4774         NTuple<Descriptor> tuple = idxIter.next();
4775         addFlowGraphEdge(md, tuple, interTuple);
4776       }
4777       newImplicitTupleSet.clear();
4778       newImplicitTupleSet.addTuple(interTuple);
4779     }
4780
4781     BlockNode sbn = ssn.getSwitchBody();
4782     for (int i = 0; i < sbn.size(); i++) {
4783       analyzeSwitchBlockNode(md, nametable, (SwitchBlockNode) sbn.get(i), newImplicitTupleSet);
4784     }
4785
4786   }
4787
4788   private void analyzeFlowSubBlockNode(MethodDescriptor md, SymbolTable nametable,
4789       SubBlockNode sbn, NodeTupleSet implicitFlowTupleSet) {
4790     analyzeFlowBlockNode(md, nametable, sbn.getBlockNode(), implicitFlowTupleSet);
4791   }
4792
4793   private void analyzeFlowReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode rn,
4794       NodeTupleSet implicitFlowTupleSet) {
4795
4796     // System.out.println("-analyzeFlowReturnNode=" + rn.printNode(0));
4797     ExpressionNode returnExp = rn.getReturnExpression();
4798
4799     if (returnExp != null) {
4800       NodeTupleSet nodeSet = new NodeTupleSet();
4801       // if a return expression returns a literal value, nodeSet is empty
4802       analyzeFlowExpressionNode(md, nametable, returnExp, nodeSet, false);
4803       FlowGraph fg = getFlowGraph(md);
4804
4805       // if (implicitFlowTupleSet.size() == 1
4806       // &&
4807       // fg.getFlowNode(implicitFlowTupleSet.iterator().next()).isIntermediate())
4808       // {
4809       //
4810       // // since there is already an intermediate node for the GLB of implicit
4811       // flows
4812       // // we don't need to create another intermediate node.
4813       // // just re-use the intermediate node for implicit flows.
4814       //
4815       // FlowNode meetNode =
4816       // fg.getFlowNode(implicitFlowTupleSet.iterator().next());
4817       //
4818       // for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
4819       // NTuple<Descriptor> returnNodeTuple = (NTuple<Descriptor>)
4820       // iterator.next();
4821       // fg.addValueFlowEdge(returnNodeTuple, meetNode.getDescTuple());
4822       // }
4823       //
4824       // }
4825
4826       NodeTupleSet currentFlowTupleSet = new NodeTupleSet();
4827
4828       // add tuples from return node
4829       currentFlowTupleSet.addTupleSet(nodeSet);
4830
4831       // add tuples corresponding to the current implicit flows
4832       currentFlowTupleSet.addTupleSet(implicitFlowTupleSet);
4833
4834       // System.out.println("---currentFlowTupleSet=" + currentFlowTupleSet);
4835
4836       if (needToGenerateInterLoc(currentFlowTupleSet)) {
4837         System.out.println("9");
4838
4839         FlowNode meetNode = fg.createIntermediateNode();
4840         for (Iterator iterator = currentFlowTupleSet.iterator(); iterator.hasNext();) {
4841           NTuple<Descriptor> currentFlowTuple = (NTuple<Descriptor>) iterator.next();
4842           fg.addValueFlowEdge(currentFlowTuple, meetNode.getDescTuple());
4843         }
4844         fg.addReturnFlowNode(meetNode.getDescTuple());
4845       } else {
4846         // currentFlowTupleSet = removeLiteralTuple(currentFlowTupleSet);
4847         for (Iterator iterator = currentFlowTupleSet.iterator(); iterator.hasNext();) {
4848           NTuple<Descriptor> currentFlowTuple = (NTuple<Descriptor>) iterator.next();
4849           fg.addReturnFlowNode(currentFlowTuple);
4850         }
4851       }
4852
4853     }
4854
4855   }
4856
4857   private NodeTupleSet removeLiteralTuple(NodeTupleSet inSet) {
4858     NodeTupleSet tupleSet = new NodeTupleSet();
4859     for (Iterator<NTuple<Descriptor>> iter = inSet.iterator(); iter.hasNext();) {
4860       NTuple<Descriptor> tuple = iter.next();
4861       if (!tuple.get(0).equals(LITERALDESC)) {
4862         tupleSet.addTuple(tuple);
4863       }
4864     }
4865     return tupleSet;
4866   }
4867
4868   private boolean needToGenerateInterLoc(NodeTupleSet tupleSet) {
4869     int size = 0;
4870     for (Iterator<NTuple<Descriptor>> iter = tupleSet.iterator(); iter.hasNext();) {
4871       NTuple<Descriptor> descTuple = iter.next();
4872       if (!descTuple.get(0).equals(LITERALDESC)) {
4873         size++;
4874       }
4875     }
4876     if (size > 1) {
4877       System.out.println("needToGenerateInterLoc=" + tupleSet + "  size=" + size);
4878       return true;
4879     } else {
4880       return false;
4881     }
4882   }
4883
4884   private void analyzeFlowLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln,
4885       NodeTupleSet implicitFlowTupleSet) {
4886
4887     if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) {
4888
4889       NodeTupleSet condTupleNode = new NodeTupleSet();
4890       analyzeFlowExpressionNode(md, nametable, ln.getCondition(), condTupleNode, null,
4891           implicitFlowTupleSet, false);
4892
4893       NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
4894
4895       newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
4896       newImplicitTupleSet.addTupleSet(condTupleNode);
4897
4898       newImplicitTupleSet.addGlobalFlowTupleSet(implicitFlowTupleSet.getGlobalLocTupleSet());
4899       newImplicitTupleSet.addGlobalFlowTupleSet(condTupleNode.getGlobalLocTupleSet());
4900
4901       if (needToGenerateInterLoc(newImplicitTupleSet)) {
4902         // need to create an intermediate node for the GLB of conditional
4903         // locations & implicit flows
4904         System.out.println("6");
4905
4906         NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
4907         for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter
4908             .hasNext();) {
4909           NTuple<Descriptor> tuple = idxIter.next();
4910           addFlowGraphEdge(md, tuple, interTuple);
4911         }
4912         newImplicitTupleSet.clear();
4913         newImplicitTupleSet.addTuple(interTuple);
4914
4915       }
4916
4917       // ///////////
4918       // System.out.println("condTupleNode="+condTupleNode);
4919       // NTuple<Descriptor> interTuple =
4920       // getFlowGraph(md).createIntermediateNode().getDescTuple();
4921       //
4922       // for (Iterator<NTuple<Descriptor>> idxIter = condTupleNode.iterator();
4923       // idxIter.hasNext();) {
4924       // NTuple<Descriptor> tuple = idxIter.next();
4925       // addFlowGraphEdge(md, tuple, interTuple);
4926       // }
4927
4928       // for (Iterator<NTuple<Descriptor>> idxIter =
4929       // implicitFlowTupleSet.iterator(); idxIter
4930       // .hasNext();) {
4931       // NTuple<Descriptor> tuple = idxIter.next();
4932       // addFlowGraphEdge(md, tuple, interTuple);
4933       // }
4934
4935       // NodeTupleSet newImplicitSet = new NodeTupleSet();
4936       // newImplicitSet.addTuple(interTuple);
4937       analyzeFlowBlockNode(md, nametable, ln.getBody(), newImplicitTupleSet);
4938       // ///////////
4939
4940       // condTupleNode.addTupleSet(implicitFlowTupleSet);
4941
4942       // add edges from condNodeTupleSet to all nodes of conditional nodes
4943       // analyzeFlowBlockNode(md, nametable, ln.getBody(), condTupleNode);
4944
4945     } else {
4946       // check 'for loop' case
4947       BlockNode bn = ln.getInitializer();
4948       bn.getVarTable().setParent(nametable);
4949       for (int i = 0; i < bn.size(); i++) {
4950         BlockStatementNode bsn = bn.get(i);
4951         analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet);
4952       }
4953
4954       NodeTupleSet condTupleNode = new NodeTupleSet();
4955       analyzeFlowExpressionNode(md, bn.getVarTable(), ln.getCondition(), condTupleNode, null,
4956           implicitFlowTupleSet, false);
4957
4958       NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
4959       newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
4960       newImplicitTupleSet.addTupleSet(condTupleNode);
4961
4962       if (needToGenerateInterLoc(newImplicitTupleSet)) {
4963         // need to create an intermediate node for the GLB of conditional
4964         // locations & implicit flows
4965         System.out.println("7");
4966
4967         NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
4968         for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter
4969             .hasNext();) {
4970           NTuple<Descriptor> tuple = idxIter.next();
4971           addFlowGraphEdge(md, tuple, interTuple);
4972         }
4973         newImplicitTupleSet.clear();
4974         newImplicitTupleSet.addTuple(interTuple);
4975
4976       }
4977
4978       // ///////////
4979       // NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
4980       //
4981       // for (Iterator<NTuple<Descriptor>> idxIter = condTupleNode.iterator(); idxIter.hasNext();) {
4982       // NTuple<Descriptor> tuple = idxIter.next();
4983       // addFlowGraphEdge(md, tuple, interTuple);
4984       // }
4985       //
4986       // for (Iterator<NTuple<Descriptor>> idxIter = implicitFlowTupleSet.iterator(); idxIter
4987       // .hasNext();) {
4988       // NTuple<Descriptor> tuple = idxIter.next();
4989       // addFlowGraphEdge(md, tuple, interTuple);
4990       // }
4991       //
4992       // NodeTupleSet newImplicitSet = new NodeTupleSet();
4993       // newImplicitSet.addTuple(interTuple);
4994       analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(), newImplicitTupleSet);
4995       analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(), newImplicitTupleSet);
4996       // ///////////
4997
4998       // condTupleNode.addTupleSet(implicitFlowTupleSet);
4999       //
5000       // analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(),
5001       // condTupleNode);
5002       // analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(),
5003       // condTupleNode);
5004
5005     }
5006
5007   }
5008
5009   private void analyzeFlowIfStatementNode(MethodDescriptor md, SymbolTable nametable,
5010       IfStatementNode isn, NodeTupleSet implicitFlowTupleSet) {
5011
5012     // System.out.println("analyzeFlowIfStatementNode=" + isn.printNode(0));
5013
5014     NodeTupleSet condTupleNode = new NodeTupleSet();
5015     analyzeFlowExpressionNode(md, nametable, isn.getCondition(), condTupleNode, null,
5016         implicitFlowTupleSet, false);
5017
5018     NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
5019
5020     newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
5021     newImplicitTupleSet.addTupleSet(condTupleNode);
5022
5023     // System.out.println("$$$GGGcondTupleNode=" + condTupleNode.getGlobalLocTupleSet());
5024     // System.out.println("-condTupleNode=" + condTupleNode);
5025     // System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet);
5026     // System.out.println("-newImplicitTupleSet=" + newImplicitTupleSet);
5027
5028     if (needToGenerateInterLoc(newImplicitTupleSet)) {
5029       System.out.println("5");
5030
5031       // need to create an intermediate node for the GLB of conditional locations & implicit flows
5032       NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
5033       for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) {
5034         NTuple<Descriptor> tuple = idxIter.next();
5035         addFlowGraphEdge(md, tuple, interTuple);
5036       }
5037       newImplicitTupleSet.clear();
5038       newImplicitTupleSet.addTuple(interTuple);
5039     }
5040
5041     // GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
5042     // for (Iterator<NTuple<Location>> iterator = condTupleNode.globalIterator();
5043     // iterator.hasNext();) {
5044     // NTuple<Location> calleeReturnLocTuple = iterator.next();
5045     // for (Iterator<NTuple<Descriptor>> iter2 = newImplicitTupleSet.iterator(); iter2.hasNext();) {
5046     // NTuple<Descriptor> callerImplicitTuple = iter2.next();
5047     // globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple,
5048     // translateToLocTuple(md, callerImplicitTuple));
5049     // }
5050     // }
5051     newImplicitTupleSet.addGlobalFlowTupleSet(condTupleNode.getGlobalLocTupleSet());
5052
5053     analyzeFlowBlockNode(md, nametable, isn.getTrueBlock(), newImplicitTupleSet);
5054
5055     if (isn.getFalseBlock() != null) {
5056       analyzeFlowBlockNode(md, nametable, isn.getFalseBlock(), newImplicitTupleSet);
5057     }
5058
5059   }
5060
5061   private void analyzeFlowDeclarationNode(MethodDescriptor md, SymbolTable nametable,
5062       DeclarationNode dn, NodeTupleSet implicitFlowTupleSet) {
5063
5064     VarDescriptor vd = dn.getVarDescriptor();
5065     mapDescToDefinitionLine.put(vd, dn.getNumLine());
5066     NTuple<Descriptor> tupleLHS = new NTuple<Descriptor>();
5067     tupleLHS.add(vd);
5068     FlowNode fn = getFlowGraph(md).createNewFlowNode(tupleLHS);
5069     fn.setDeclarationNode();
5070
5071     if (dn.getExpression() != null) {
5072       System.out.println("-analyzeFlowDeclarationNode=" + dn.printNode(0));
5073
5074       NodeTupleSet nodeSetRHS = new NodeTupleSet();
5075       analyzeFlowExpressionNode(md, nametable, dn.getExpression(), nodeSetRHS, null,
5076           implicitFlowTupleSet, false);
5077
5078       // creates edges from RHS to LHS
5079       NTuple<Descriptor> interTuple = null;
5080       if (needToGenerateInterLoc(nodeSetRHS)) {
5081         System.out.println("3");
5082         interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
5083       }
5084
5085       for (Iterator<NTuple<Descriptor>> iter = nodeSetRHS.iterator(); iter.hasNext();) {
5086         NTuple<Descriptor> fromTuple = iter.next();
5087         System.out.println("fromTuple=" + fromTuple + "  interTuple=" + interTuple + " tupleLSH="
5088             + tupleLHS);
5089         addFlowGraphEdge(md, fromTuple, interTuple, tupleLHS);
5090       }
5091
5092       // creates edges from implicitFlowTupleSet to LHS
5093       for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
5094         NTuple<Descriptor> implicitTuple = iter.next();
5095         addFlowGraphEdge(md, implicitTuple, tupleLHS);
5096       }
5097
5098       GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
5099       for (Iterator<NTuple<Location>> iterator = nodeSetRHS.globalIterator(); iterator.hasNext();) {
5100         NTuple<Location> calleeReturnLocTuple = iterator.next();
5101
5102         globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, translateToLocTuple(md, tupleLHS));
5103       }
5104
5105       for (Iterator<NTuple<Location>> iterator = implicitFlowTupleSet.globalIterator(); iterator
5106           .hasNext();) {
5107         NTuple<Location> implicitGlobalTuple = iterator.next();
5108
5109         globalFlowGraph.addValueFlowEdge(implicitGlobalTuple, translateToLocTuple(md, tupleLHS));
5110       }
5111
5112       System.out.println("-nodeSetRHS=" + nodeSetRHS);
5113       System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet);
5114
5115     }
5116
5117   }
5118
5119   private void analyzeBlockExpressionNode(MethodDescriptor md, SymbolTable nametable,
5120       BlockExpressionNode ben, NodeTupleSet implicitFlowTupleSet) {
5121     analyzeFlowExpressionNode(md, nametable, ben.getExpression(), null, null, implicitFlowTupleSet,
5122         false);
5123   }
5124
5125   private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
5126       ExpressionNode en, NodeTupleSet nodeSet, boolean isLHS) {
5127     return analyzeFlowExpressionNode(md, nametable, en, nodeSet, null, new NodeTupleSet(), isLHS);
5128   }
5129
5130   private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
5131       ExpressionNode en, NodeTupleSet nodeSet, NTuple<Descriptor> base,
5132       NodeTupleSet implicitFlowTupleSet, boolean isLHS) {
5133
5134     // System.out.println("en=" + en.printNode(0) + "   class=" + en.getClass());
5135
5136     // note that expression node can create more than one flow node
5137     // nodeSet contains of flow nodes
5138     // base is always assigned to null except the case of a name node!
5139     NTuple<Descriptor> flowTuple;
5140     switch (en.kind()) {
5141     case Kind.AssignmentNode:
5142       analyzeFlowAssignmentNode(md, nametable, (AssignmentNode) en, nodeSet, base,
5143           implicitFlowTupleSet);
5144       break;
5145
5146     case Kind.FieldAccessNode:
5147       flowTuple =
5148           analyzeFlowFieldAccessNode(md, nametable, (FieldAccessNode) en, nodeSet, base,
5149               implicitFlowTupleSet, isLHS);
5150       if (flowTuple != null) {
5151         nodeSet.addTuple(flowTuple);
5152       }
5153       return flowTuple;
5154
5155     case Kind.NameNode:
5156       NodeTupleSet nameNodeSet = new NodeTupleSet();
5157       flowTuple =
5158           analyzeFlowNameNode(md, nametable, (NameNode) en, nameNodeSet, base, implicitFlowTupleSet);
5159       if (flowTuple != null) {
5160         nodeSet.addTuple(flowTuple);
5161       }
5162       return flowTuple;
5163
5164     case Kind.OpNode:
5165       analyzeFlowOpNode(md, nametable, (OpNode) en, nodeSet, implicitFlowTupleSet);
5166       break;
5167
5168     case Kind.CreateObjectNode:
5169       analyzeCreateObjectNode(md, nametable, (CreateObjectNode) en);
5170       break;
5171
5172     case Kind.ArrayAccessNode:
5173       analyzeFlowArrayAccessNode(md, nametable, (ArrayAccessNode) en, nodeSet, isLHS);
5174       break;
5175
5176     case Kind.LiteralNode:
5177       analyzeFlowLiteralNode(md, nametable, (LiteralNode) en, nodeSet);
5178       break;
5179
5180     case Kind.MethodInvokeNode:
5181       analyzeFlowMethodInvokeNode(md, nametable, (MethodInvokeNode) en, nodeSet,
5182           implicitFlowTupleSet);
5183       break;
5184
5185     case Kind.TertiaryNode:
5186       analyzeFlowTertiaryNode(md, nametable, (TertiaryNode) en, nodeSet, implicitFlowTupleSet);
5187       break;
5188
5189     case Kind.CastNode:
5190       analyzeFlowCastNode(md, nametable, (CastNode) en, nodeSet, base, implicitFlowTupleSet);
5191       break;
5192     // case Kind.InstanceOfNode:
5193     // checkInstanceOfNode(md, nametable, (InstanceOfNode) en, td);
5194     // return null;
5195
5196     // case Kind.ArrayInitializerNode:
5197     // checkArrayInitializerNode(md, nametable, (ArrayInitializerNode) en,
5198     // td);
5199     // return null;
5200
5201     // case Kind.ClassTypeNode:
5202     // checkClassTypeNode(md, nametable, (ClassTypeNode) en, td);
5203     // return null;
5204
5205     // case Kind.OffsetNode:
5206     // checkOffsetNode(md, nametable, (OffsetNode)en, td);
5207     // return null;
5208
5209     }
5210
5211     return null;
5212
5213   }
5214
5215   private void analyzeFlowCastNode(MethodDescriptor md, SymbolTable nametable, CastNode cn,
5216       NodeTupleSet nodeSet, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
5217
5218     analyzeFlowExpressionNode(md, nametable, cn.getExpression(), nodeSet, base,
5219         implicitFlowTupleSet, false);
5220
5221   }
5222
5223   private void analyzeFlowTertiaryNode(MethodDescriptor md, SymbolTable nametable, TertiaryNode tn,
5224       NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
5225
5226     // System.out.println("analyzeFlowTertiaryNode=" + tn.printNode(0));
5227
5228     NodeTupleSet tertiaryTupleNode = new NodeTupleSet();
5229     analyzeFlowExpressionNode(md, nametable, tn.getCond(), tertiaryTupleNode, null,
5230         implicitFlowTupleSet, false);
5231
5232     NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
5233     newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
5234     newImplicitTupleSet.addTupleSet(tertiaryTupleNode);
5235
5236     // System.out.println("$$$GGGcondTupleNode=" + tertiaryTupleNode.getGlobalLocTupleSet());
5237     // System.out.println("-tertiaryTupleNode=" + tertiaryTupleNode);
5238     // System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet);
5239     // System.out.println("-newImplicitTupleSet=" + newImplicitTupleSet);
5240
5241     if (needToGenerateInterLoc(newImplicitTupleSet)) {
5242       System.out.println("15");
5243       // need to create an intermediate node for the GLB of conditional locations & implicit flows
5244       NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
5245       for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) {
5246         NTuple<Descriptor> tuple = idxIter.next();
5247         addFlowGraphEdge(md, tuple, interTuple);
5248       }
5249       newImplicitTupleSet.clear();
5250       newImplicitTupleSet.addTuple(interTuple);
5251     }
5252
5253     newImplicitTupleSet.addGlobalFlowTupleSet(tertiaryTupleNode.getGlobalLocTupleSet());
5254
5255     System.out.println("---------newImplicitTupleSet=" + newImplicitTupleSet);
5256     // add edges from tertiaryTupleNode to all nodes of conditional nodes
5257     // tertiaryTupleNode.addTupleSet(implicitFlowTupleSet);
5258     analyzeFlowExpressionNode(md, nametable, tn.getTrueExpr(), tertiaryTupleNode, null,
5259         newImplicitTupleSet, false);
5260
5261     analyzeFlowExpressionNode(md, nametable, tn.getFalseExpr(), tertiaryTupleNode, null,
5262         newImplicitTupleSet, false);
5263
5264     nodeSet.addGlobalFlowTupleSet(tertiaryTupleNode.getGlobalLocTupleSet());
5265     nodeSet.addTupleSet(tertiaryTupleNode);
5266
5267     System.out.println("#tertiary node set=" + nodeSet);
5268   }
5269
5270   private void addMapCallerMethodDescToMethodInvokeNodeSet(MethodDescriptor caller,
5271       MethodInvokeNode min) {
5272     Set<MethodInvokeNode> set = mapMethodDescriptorToMethodInvokeNodeSet.get(caller);
5273     if (set == null) {
5274       set = new HashSet<MethodInvokeNode>();
5275       mapMethodDescriptorToMethodInvokeNodeSet.put(caller, set);
5276     }
5277     set.add(min);
5278   }
5279
5280   private void addParamNodeFlowingToReturnValue(MethodDescriptor md, FlowNode fn) {
5281
5282     if (!mapMethodDescToParamNodeFlowsToReturnValue.containsKey(md)) {
5283       mapMethodDescToParamNodeFlowsToReturnValue.put(md, new HashSet<FlowNode>());
5284     }
5285     mapMethodDescToParamNodeFlowsToReturnValue.get(md).add(fn);
5286   }
5287
5288   private Set<FlowNode> getParamNodeFlowingToReturnValue(MethodDescriptor md) {
5289
5290     if (!mapMethodDescToParamNodeFlowsToReturnValue.containsKey(md)) {
5291       mapMethodDescToParamNodeFlowsToReturnValue.put(md, new HashSet<FlowNode>());
5292     }
5293
5294     return mapMethodDescToParamNodeFlowsToReturnValue.get(md);
5295   }
5296
5297   private Set<NTuple<Location>> getPCLocTupleSet(MethodInvokeNode min) {
5298     if (!mapMethodInvokeNodeToPCLocTupleSet.containsKey(min)) {
5299       mapMethodInvokeNodeToPCLocTupleSet.put(min, new HashSet<NTuple<Location>>());
5300     }
5301     return mapMethodInvokeNodeToPCLocTupleSet.get(min);
5302   }
5303
5304   private void analyzeFlowMethodInvokeNode(MethodDescriptor mdCaller, SymbolTable nametable,
5305       MethodInvokeNode min, NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
5306
5307     System.out.println("analyzeFlowMethodInvokeNode=" + min.printNode(0));
5308
5309     if (!toanalyze_methodDescList.contains(min.getMethod())) {
5310       return;
5311     }
5312
5313     addMapMethodDescToMethodInvokeNodeSet(min);
5314
5315     Set<NTuple<Location>> pcLocTupleSet = getPCLocTupleSet(min);
5316     for (Iterator iterator = implicitFlowTupleSet.iterator(); iterator.hasNext();) {
5317       NTuple<Descriptor> pcDescTuple = (NTuple<Descriptor>) iterator.next();
5318       if (!pcDescTuple.get(0).equals(LITERALDESC)) {
5319         // here we don't need to add the literal value as a PC location
5320         pcLocTupleSet.add(translateToLocTuple(mdCaller, pcDescTuple));
5321       }
5322     }
5323
5324     mapMethodInvokeNodeToArgIdxMap.put(min, new HashMap<Integer, NTuple<Descriptor>>());
5325
5326     if (nodeSet == null) {
5327       nodeSet = new NodeTupleSet();
5328     }
5329
5330     MethodDescriptor mdCallee = min.getMethod();
5331
5332     NameDescriptor baseName = min.getBaseName();
5333     boolean isSystemout = false;
5334     if (baseName != null) {
5335       isSystemout = baseName.getSymbol().equals("System.out");
5336     }
5337
5338     if (!ssjava.isSSJavaUtil(mdCallee.getClassDesc()) && !ssjava.isTrustMethod(mdCallee)
5339         && !isSystemout) {
5340
5341       addMapCallerMethodDescToMethodInvokeNodeSet(mdCaller, min);
5342
5343       FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
5344       System.out.println("mdCallee=" + mdCallee + " calleeFlowGraph=" + calleeFlowGraph);
5345       Set<FlowNode> calleeReturnSet = calleeFlowGraph.getReturnNodeSet();
5346
5347       System.out.println("---calleeReturnSet=" + calleeReturnSet);
5348
5349       NodeTupleSet tupleSet = new NodeTupleSet();
5350
5351       if (min.getExpression() != null) {
5352
5353         NodeTupleSet baseNodeSet = new NodeTupleSet();
5354         analyzeFlowExpressionNode(mdCaller, nametable, min.getExpression(), baseNodeSet, null,
5355             implicitFlowTupleSet, false);
5356         System.out.println("baseNodeSet=" + baseNodeSet);
5357
5358         assert (baseNodeSet.size() == 1);
5359         NTuple<Descriptor> baseTuple = baseNodeSet.iterator().next();
5360         if (baseTuple.get(0) instanceof InterDescriptor) {
5361           if (baseTuple.size() > 1) {
5362             throw new Error();
5363           }
5364           FlowNode interNode = getFlowGraph(mdCaller).getFlowNode(baseTuple);
5365           baseTuple = translateBaseTuple(interNode, baseTuple);
5366         }
5367         mapMethodInvokeNodeToBaseTuple.put(min, baseTuple);
5368
5369         if (!min.getMethod().isStatic()) {
5370           addArgIdxMap(min, 0, baseTuple);
5371
5372           for (Iterator iterator = calleeReturnSet.iterator(); iterator.hasNext();) {
5373             FlowNode returnNode = (FlowNode) iterator.next();
5374             NTuple<Descriptor> returnDescTuple = returnNode.getDescTuple();
5375             if (returnDescTuple.startsWith(mdCallee.getThis())) {
5376               // the location type of the return value is started with 'this'
5377               // reference
5378               NTuple<Descriptor> inFlowTuple = new NTuple<Descriptor>(baseTuple.getList());
5379
5380               if (inFlowTuple.get(0) instanceof InterDescriptor) {
5381                 // min.getExpression()
5382               } else {
5383
5384               }
5385
5386               inFlowTuple.addAll(returnDescTuple.subList(1, returnDescTuple.size()));
5387               // nodeSet.addTuple(inFlowTuple);
5388               System.out.println("1CREATE A NEW TUPLE=" + inFlowTuple + "  from="
5389                   + mdCallee.getThis());
5390               // tupleSet.addTuple(inFlowTuple);
5391               tupleSet.addTuple(baseTuple);
5392             } else {
5393               // TODO
5394               System.out.println("returnNode=" + returnNode);
5395               Set<FlowNode> inFlowSet = calleeFlowGraph.getIncomingFlowNodeSet(returnNode);
5396               // System.out.println("inFlowSet=" + inFlowSet + "   from retrunNode=" + returnNode);
5397               for (Iterator iterator2 = inFlowSet.iterator(); iterator2.hasNext();) {
5398                 FlowNode inFlowNode = (FlowNode) iterator2.next();
5399                 if (inFlowNode.getDescTuple().startsWith(mdCallee.getThis())) {
5400                   // nodeSet.addTupleSet(baseNodeSet);
5401                   System.out.println("2CREATE A NEW TUPLE=" + baseNodeSet + "  from="
5402                       + mdCallee.getThis());
5403                   tupleSet.addTupleSet(baseNodeSet);
5404                 }
5405               }
5406             }
5407           }
5408         }
5409
5410       }
5411       // analyze parameter flows
5412
5413       if (min.numArgs() > 0) {
5414
5415         int offset;
5416         if (min.getMethod().isStatic()) {
5417           offset = 0;
5418         } else {
5419           offset = 1;
5420         }
5421
5422         for (int i = 0; i < min.numArgs(); i++) {
5423           ExpressionNode en = min.getArg(i);
5424           int idx = i + offset;
5425           NodeTupleSet argTupleSet = new NodeTupleSet();
5426           analyzeFlowExpressionNode(mdCaller, nametable, en, argTupleSet, false);
5427           // if argument is liternal node, argTuple is set to NULL
5428           System.out.println("---arg idx=" + idx + "   argTupleSet=" + argTupleSet);
5429           NTuple<Descriptor> argTuple = generateArgTuple(mdCaller, argTupleSet);
5430
5431           // if an argument is literal value,
5432           // we need to create an itermediate node so that we could assign a composite location to
5433           // that node if needed
5434           if (argTuple.size() > 0
5435               && (argTuple.get(0).equals(GLOBALDESC) || argTuple.get(0).equals(LITERALDESC))) {
5436             /*
5437              * System.out.println("***GLOBAL ARG TUPLE CASE=" + argTuple); System.out.println("8");
5438              *
5439              * NTuple<Descriptor> interTuple =
5440              * getFlowGraph(mdCaller).createIntermediateNode().getDescTuple(); ((InterDescriptor)
5441              * interTuple.get(0)).setMethodArgIdxPair(min, idx); addFlowGraphEdge(mdCaller,
5442              * argTuple, interTuple); argTuple = interTuple; addArgIdxMap(min, idx, argTuple);
5443              * System.out.println("new min mapping i=" + idx + "  ->" + argTuple);
5444              */
5445             argTuple = new NTuple<Descriptor>();
5446           }
5447
5448           addArgIdxMap(min, idx, argTuple);
5449
5450           FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx);
5451
5452           // check whether a param node in the callee graph has incoming flows
5453           // if it has incoming flows, the corresponding arg should be lower than the current PC
5454           // Descriptor prefix = paramNode.getDescTuple().get(0);
5455           // if (calleeFlowGraph.getIncomingNodeSetByPrefix(prefix).size() > 0) {
5456           // for (Iterator<NTuple<Descriptor>> iterator = implicitFlowTupleSet.iterator(); iterator
5457           // .hasNext();) {
5458           // NTuple<Descriptor> pcTuple = iterator.next();
5459           // System.out.println("add edge pcTuple =" + pcTuple + " -> " + argTuple);
5460           // addFlowGraphEdge(md, pcTuple, argTuple);
5461           // }
5462           // }
5463
5464           System.out.println("paramNode=" + paramNode + "  calleeReturnSet=" + calleeReturnSet);
5465           if (hasInFlowTo(calleeFlowGraph, paramNode, calleeReturnSet)
5466               || mdCallee.getModifiers().isNative()) {
5467             addParamNodeFlowingToReturnValue(mdCallee, paramNode);
5468             // nodeSet.addTupleSet(argTupleSet);
5469             System.out.println("3CREATE A NEW TUPLE=" + argTupleSet + "  from=" + paramNode);
5470             tupleSet.addTupleSet(argTupleSet);
5471           }
5472         }
5473
5474       }
5475
5476       if (mdCallee.getReturnType() != null && !mdCallee.getReturnType().isVoid()) {
5477         FlowReturnNode returnHolderNode = getFlowGraph(mdCaller).createReturnNode(min);
5478
5479         if (needToGenerateInterLoc(tupleSet)) {
5480           System.out.println("20");
5481           FlowGraph fg = getFlowGraph(mdCaller);
5482           FlowNode interNode = fg.createIntermediateNode();
5483           interNode.setFormHolder(true);
5484
5485           NTuple<Descriptor> interTuple = interNode.getDescTuple();
5486
5487           for (Iterator iterator = tupleSet.iterator(); iterator.hasNext();) {
5488             NTuple<Descriptor> tuple = (NTuple<Descriptor>) iterator.next();
5489
5490             Set<NTuple<Descriptor>> addSet = new HashSet<NTuple<Descriptor>>();
5491             FlowNode node = fg.getFlowNode(tuple);
5492             if (node instanceof FlowReturnNode) {
5493               addSet.addAll(fg.getReturnTupleSet(((FlowReturnNode) node).getReturnTupleSet()));
5494             } else {
5495               addSet.add(tuple);
5496             }
5497             for (Iterator iterator2 = addSet.iterator(); iterator2.hasNext();) {
5498               NTuple<Descriptor> higher = (NTuple<Descriptor>) iterator2.next();
5499               addFlowGraphEdge(mdCaller, higher, interTuple);
5500             }
5501           }
5502
5503           returnHolderNode.addTuple(interTuple);
5504
5505           nodeSet.addTuple(interTuple);
5506           System.out.println("ADD TUPLESET=" + interTuple + " to returnnode=" + returnHolderNode);
5507
5508         } else {
5509           returnHolderNode.addTupleSet(tupleSet);
5510           System.out.println("ADD TUPLESET=" + tupleSet + " to returnnode=" + returnHolderNode);
5511         }
5512         // setNode.addTupleSet(tupleSet);
5513         // NodeTupleSet setFromReturnNode=new NodeTupleSet();
5514         // setFromReturnNode.addTuple(tuple);
5515
5516         NodeTupleSet holderTupleSet =
5517             getNodeTupleSetFromReturnNode(getFlowGraph(mdCaller), returnHolderNode);
5518
5519         System.out.println("HOLDER TUPLe SET=" + holderTupleSet);
5520         nodeSet.addTupleSet(holderTupleSet);
5521
5522         nodeSet.addTuple(returnHolderNode.getDescTuple());
5523       }
5524
5525       // propagateFlowsFromCallee(min, md, min.getMethod());
5526
5527       // when generating the global flow graph,
5528       // we need to add ordering relations from the set of callee return loc tuple to LHS of the
5529       // caller assignment
5530       for (Iterator iterator = calleeReturnSet.iterator(); iterator.hasNext();) {
5531         FlowNode calleeReturnNode = (FlowNode) iterator.next();
5532         NTuple<Location> calleeReturnLocTuple =
5533             translateToLocTuple(mdCallee, calleeReturnNode.getDescTuple());
5534         System.out.println("calleeReturnLocTuple=" + calleeReturnLocTuple);
5535         NTuple<Location> transaltedToCaller =
5536             translateToCallerLocTuple(min, mdCallee, mdCaller, calleeReturnLocTuple);
5537         // System.out.println("translateToCallerLocTuple="
5538         // + translateToCallerLocTuple(min, mdCallee, mdCaller, calleeReturnLocTuple));
5539         if (transaltedToCaller.size() > 0) {
5540           nodeSet.addGlobalFlowTuple(translateToCallerLocTuple(min, mdCallee, mdCaller,
5541               calleeReturnLocTuple));
5542         }
5543       }
5544
5545       System.out.println("min nodeSet=" + nodeSet);
5546
5547     }
5548
5549   }
5550
5551   private NodeTupleSet getNodeTupleSetFromReturnNode(FlowGraph fg, FlowReturnNode node) {
5552     NodeTupleSet nts = new NodeTupleSet();
5553
5554     Set<NTuple<Descriptor>> returnSet = node.getReturnTupleSet();
5555
5556     for (Iterator iterator = returnSet.iterator(); iterator.hasNext();) {
5557       NTuple<Descriptor> tuple = (NTuple<Descriptor>) iterator.next();
5558       FlowNode flowNode = fg.getFlowNode(tuple);
5559       if (flowNode instanceof FlowReturnNode) {
5560         returnSet.addAll(recurGetNode(fg, (FlowReturnNode) flowNode));
5561       } else {
5562         returnSet.add(tuple);
5563       }
5564     }
5565
5566     for (Iterator iterator = returnSet.iterator(); iterator.hasNext();) {
5567       NTuple<Descriptor> nTuple = (NTuple<Descriptor>) iterator.next();
5568       nts.addTuple(nTuple);
5569     }
5570
5571     return nts;
5572
5573   }
5574
5575   private Set<NTuple<Descriptor>> recurGetNode(FlowGraph fg, FlowReturnNode rnode) {
5576
5577     Set<NTuple<Descriptor>> tupleSet = new HashSet<NTuple<Descriptor>>();
5578
5579     Set<NTuple<Descriptor>> returnSet = rnode.getReturnTupleSet();
5580     for (Iterator iterator = returnSet.iterator(); iterator.hasNext();) {
5581       NTuple<Descriptor> tuple = (NTuple<Descriptor>) iterator.next();
5582       FlowNode flowNode = fg.getFlowNode(tuple);
5583       if (flowNode instanceof FlowReturnNode) {
5584         tupleSet.addAll(recurGetNode(fg, (FlowReturnNode) flowNode));
5585       }
5586       tupleSet.add(tuple);
5587     }
5588
5589     return tupleSet;
5590   }
5591
5592   private NTuple<Descriptor> generateArgTuple(MethodDescriptor mdCaller, NodeTupleSet argTupleSet) {
5593
5594     int size = 0;
5595
5596     // if argTupleSet is empty, it comes from the top location
5597     if (argTupleSet.size() == 0) {
5598       NTuple<Descriptor> descTuple = new NTuple<Descriptor>();
5599       descTuple.add(LITERALDESC);
5600       return descTuple;
5601     }
5602
5603     Set<NTuple<Descriptor>> argTupleSetNonLiteral = new HashSet<NTuple<Descriptor>>();
5604
5605     for (Iterator<NTuple<Descriptor>> iter = argTupleSet.iterator(); iter.hasNext();) {
5606       NTuple<Descriptor> descTuple = iter.next();
5607       if (!descTuple.get(0).equals(LITERALDESC)) {
5608         argTupleSetNonLiteral.add(descTuple);
5609       }
5610     }
5611
5612     if (argTupleSetNonLiteral.size() > 1) {
5613       System.out.println("11");
5614
5615       NTuple<Descriptor> interTuple =
5616           getFlowGraph(mdCaller).createIntermediateNode().getDescTuple();
5617       for (Iterator<NTuple<Descriptor>> idxIter = argTupleSet.iterator(); idxIter.hasNext();) {
5618         NTuple<Descriptor> tuple = idxIter.next();
5619         addFlowGraphEdge(mdCaller, tuple, interTuple);
5620       }
5621       return interTuple;
5622     } else if (argTupleSetNonLiteral.size() == 1) {
5623       return argTupleSetNonLiteral.iterator().next();
5624     } else {
5625       return argTupleSet.iterator().next();
5626     }
5627
5628   }
5629
5630   private boolean hasInFlowTo(FlowGraph fg, FlowNode inNode, Set<FlowNode> nodeSet) {
5631     // return true if inNode has in-flows to nodeSet
5632
5633     if (nodeSet.contains(inNode)) {
5634       // in this case, the method directly returns a parameter variable.
5635       return true;
5636     }
5637     // Set<FlowNode> reachableSet = fg.getReachFlowNodeSetFrom(inNode);
5638     Set<FlowNode> reachableSet = fg.getReachableSetFrom(inNode.getDescTuple());
5639     // System.out.println("inNode=" + inNode + "  reachalbeSet=" + reachableSet);
5640
5641     for (Iterator iterator = reachableSet.iterator(); iterator.hasNext();) {
5642       FlowNode fn = (FlowNode) iterator.next();
5643       if (nodeSet.contains(fn)) {
5644         return true;
5645       }
5646     }
5647     return false;
5648   }
5649
5650   private NTuple<Descriptor> getNodeTupleByArgIdx(MethodInvokeNode min, int idx) {
5651     return mapMethodInvokeNodeToArgIdxMap.get(min).get(new Integer(idx));
5652   }
5653
5654   private void addArgIdxMap(MethodInvokeNode min, int idx, NTuple<Descriptor> argTuple /*
5655                                                                                         * NodeTupleSet
5656                                                                                         * tupleSet
5657                                                                                         */) {
5658     Map<Integer, NTuple<Descriptor>> mapIdxToTuple = mapMethodInvokeNodeToArgIdxMap.get(min);
5659     if (mapIdxToTuple == null) {
5660       mapIdxToTuple = new HashMap<Integer, NTuple<Descriptor>>();
5661       mapMethodInvokeNodeToArgIdxMap.put(min, mapIdxToTuple);
5662     }
5663     mapIdxToTuple.put(new Integer(idx), argTuple);
5664   }
5665
5666   private void analyzeFlowLiteralNode(MethodDescriptor md, SymbolTable nametable, LiteralNode en,
5667       NodeTupleSet nodeSet) {
5668     NTuple<Descriptor> tuple = new NTuple<Descriptor>();
5669     tuple.add(LITERALDESC);
5670     nodeSet.addTuple(tuple);
5671   }
5672
5673   private void analyzeFlowArrayAccessNode(MethodDescriptor md, SymbolTable nametable,
5674       ArrayAccessNode aan, NodeTupleSet nodeSet, boolean isLHS) {
5675
5676     System.out.println("analyzeFlowArrayAccessNode aan=" + aan.printNode(0));
5677     String currentArrayAccessNodeExpStr = aan.printNode(0);
5678     arrayAccessNodeStack.push(aan.printNode(0));
5679
5680     NodeTupleSet expNodeTupleSet = new NodeTupleSet();
5681     NTuple<Descriptor> base =
5682         analyzeFlowExpressionNode(md, nametable, aan.getExpression(), expNodeTupleSet, isLHS);
5683     System.out.println("-base=" + base);
5684
5685     nodeSet.setMethodInvokeBaseDescTuple(base);
5686     NodeTupleSet idxNodeTupleSet = new NodeTupleSet();
5687     analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, isLHS);
5688
5689     arrayAccessNodeStack.pop();
5690
5691     if (isLHS) {
5692       // need to create an edge from idx to array
5693       for (Iterator<NTuple<Descriptor>> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) {
5694         NTuple<Descriptor> idxTuple = idxIter.next();
5695         for (Iterator<NTuple<Descriptor>> arrIter = expNodeTupleSet.iterator(); arrIter.hasNext();) {
5696           NTuple<Descriptor> arrTuple = arrIter.next();
5697           getFlowGraph(md).addValueFlowEdge(idxTuple, arrTuple);
5698         }
5699       }
5700
5701       GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
5702       for (Iterator<NTuple<Location>> iterator = idxNodeTupleSet.globalIterator(); iterator
5703           .hasNext();) {
5704         NTuple<Location> calleeReturnLocTuple = iterator.next();
5705         for (Iterator<NTuple<Descriptor>> arrIter = expNodeTupleSet.iterator(); arrIter.hasNext();) {
5706           NTuple<Descriptor> arrTuple = arrIter.next();
5707
5708           globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, translateToLocTuple(md, arrTuple));
5709         }
5710       }
5711
5712       nodeSet.addTupleSet(expNodeTupleSet);
5713     } else {
5714
5715       NodeTupleSet nodeSetArrayAccessExp = new NodeTupleSet();
5716
5717       nodeSetArrayAccessExp.addTupleSet(expNodeTupleSet);
5718       nodeSetArrayAccessExp.addTupleSet(idxNodeTupleSet);
5719
5720       if (arrayAccessNodeStack.isEmpty()
5721           || !arrayAccessNodeStack.peek().startsWith(currentArrayAccessNodeExpStr)) {
5722
5723         if (needToGenerateInterLoc(nodeSetArrayAccessExp)) {
5724           System.out.println("1");
5725           FlowNode interNode = getFlowGraph(md).createIntermediateNode();
5726           NTuple<Descriptor> interTuple = interNode.getDescTuple();
5727
5728           for (Iterator<NTuple<Descriptor>> iter = nodeSetArrayAccessExp.iterator(); iter.hasNext();) {
5729             NTuple<Descriptor> higherTuple = iter.next();
5730             addFlowGraphEdge(md, higherTuple, interTuple);
5731           }
5732           nodeSetArrayAccessExp.clear();
5733           nodeSetArrayAccessExp.addTuple(interTuple);
5734           FlowGraph fg = getFlowGraph(md);
5735
5736           System.out.println("base=" + base);
5737           if (base != null) {
5738             fg.addMapInterLocNodeToEnclosingDescriptor(interTuple.get(0),
5739                 getClassTypeDescriptor(base.get(base.size() - 1)));
5740             interNode.setBaseTuple(base);
5741           }
5742         }
5743       }
5744
5745       nodeSet.addGlobalFlowTupleSet(idxNodeTupleSet.getGlobalLocTupleSet());
5746       nodeSet.addTupleSet(nodeSetArrayAccessExp);
5747
5748     }
5749
5750   }
5751
5752   private void analyzeCreateObjectNode(MethodDescriptor md, SymbolTable nametable,
5753       CreateObjectNode en) {
5754     // TODO Auto-generated method stub
5755
5756   }
5757
5758   private void analyzeFlowOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on,
5759       NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
5760
5761     NodeTupleSet leftOpSet = new NodeTupleSet();
5762     NodeTupleSet rightOpSet = new NodeTupleSet();
5763
5764     System.out.println("analyzeFlowOpNode=" + on.printNode(0));
5765
5766     // left operand
5767     analyzeFlowExpressionNode(md, nametable, on.getLeft(), leftOpSet, null, implicitFlowTupleSet,
5768         false);
5769     System.out.println("--leftOpSet=" + leftOpSet);
5770
5771     if (on.getRight() != null) {
5772       // right operand
5773       analyzeFlowExpressionNode(md, nametable, on.getRight(), rightOpSet, null,
5774           implicitFlowTupleSet, false);
5775     }
5776     System.out.println("--rightOpSet=" + rightOpSet);
5777
5778     Operation op = on.getOp();
5779
5780     switch (op.getOp()) {
5781
5782     case Operation.UNARYPLUS:
5783     case Operation.UNARYMINUS:
5784     case Operation.LOGIC_NOT:
5785       // single operand
5786       nodeSet.addTupleSet(leftOpSet);
5787       break;
5788
5789     case Operation.LOGIC_OR:
5790     case Operation.LOGIC_AND:
5791     case Operation.COMP:
5792     case Operation.BIT_OR:
5793     case Operation.BIT_XOR:
5794     case Operation.BIT_AND:
5795     case Operation.ISAVAILABLE:
5796     case Operation.EQUAL:
5797     case Operation.NOTEQUAL:
5798     case Operation.LT:
5799     case Operation.GT:
5800     case Operation.LTE:
5801     case Operation.GTE:
5802     case Operation.ADD:
5803     case Operation.SUB:
5804     case Operation.MULT:
5805     case Operation.DIV:
5806     case Operation.MOD:
5807     case Operation.LEFTSHIFT:
5808     case Operation.RIGHTSHIFT:
5809     case Operation.URIGHTSHIFT:
5810
5811       // there are two operands
5812       nodeSet.addTupleSet(leftOpSet);
5813       nodeSet.addTupleSet(rightOpSet);
5814
5815       nodeSet.addGlobalFlowTupleSet(leftOpSet.getGlobalLocTupleSet());
5816       nodeSet.addGlobalFlowTupleSet(rightOpSet.getGlobalLocTupleSet());
5817
5818       break;
5819
5820     default:
5821       throw new Error(op.toString());
5822     }
5823
5824   }
5825
5826   private NTuple<Descriptor> analyzeFlowNameNode(MethodDescriptor md, SymbolTable nametable,
5827       NameNode nn, NodeTupleSet nodeSet, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
5828
5829     if (base == null) {
5830       base = new NTuple<Descriptor>();
5831     }
5832
5833     NameDescriptor nd = nn.getName();
5834
5835     if (nd.getBase() != null) {
5836       base =
5837           analyzeFlowExpressionNode(md, nametable, nn.getExpression(), nodeSet, base,
5838               implicitFlowTupleSet, false);
5839       if (base == null) {
5840         // base node has the top location
5841         return base;
5842       }
5843     } else {
5844       String varname = nd.toString();
5845       if (varname.equals("this")) {
5846         // 'this' itself!
5847         base.add(md.getThis());
5848         return base;
5849       }
5850
5851       Descriptor d = (Descriptor) nametable.get(varname);
5852
5853       if (d instanceof VarDescriptor) {
5854         VarDescriptor vd = (VarDescriptor) d;
5855         base.add(vd);
5856       } else if (d instanceof FieldDescriptor) {
5857         // the type of field descriptor has a location!
5858         FieldDescriptor fd = (FieldDescriptor) d;
5859         if (fd.isStatic()) {
5860           if (fd.isFinal()) {
5861             // if it is 'static final', no need to have flow node for the TOP
5862             // location
5863             return null;
5864           } else {
5865             // if 'static', assign the default GLOBAL LOCATION to the first
5866             // element of the tuple
5867             base.add(GLOBALDESC);
5868           }
5869         } else {
5870           // the location of field access starts from this, followed by field
5871           // location
5872           base.add(md.getThis());
5873         }
5874
5875         base.add(fd);
5876       } else if (d == null) {
5877         // access static field
5878         base.add(GLOBALDESC);
5879         base.add(nn.getField());
5880         return base;
5881
5882         // FieldDescriptor fd = nn.getField();addFlowGraphEdge
5883         //
5884         // MethodLattice<String> localLattice = ssjava.getMethodLattice(md);
5885         // String globalLocId = localLattice.getGlobalLoc();
5886         // if (globalLocId == null) {
5887         // throw new
5888         // Error("Method lattice does not define global variable location at "
5889         // + generateErrorMessage(md.getClassDesc(), nn));
5890         // }
5891         // loc.addLocation(new Location(md, globalLocId));
5892         //
5893         // Location fieldLoc = (Location) fd.getType().getExtension();
5894         // loc.addLocation(fieldLoc);
5895         //
5896         // return loc;
5897
5898       }
5899     }
5900     getFlowGraph(md).createNewFlowNode(base);
5901
5902     return base;
5903
5904   }
5905
5906   private NTuple<Descriptor> analyzeFlowFieldAccessNode(MethodDescriptor md, SymbolTable nametable,
5907       FieldAccessNode fan, NodeTupleSet nodeSet, NTuple<Descriptor> base,
5908       NodeTupleSet implicitFlowTupleSet, boolean isLHS) {
5909     // System.out.println("analyzeFlowFieldAccessNode=" + fan.printNode(0));
5910
5911     String currentArrayAccessNodeExpStr = null;
5912     ExpressionNode left = fan.getExpression();
5913     TypeDescriptor ltd = left.getType();
5914     FieldDescriptor fd = fan.getField();
5915     ArrayAccessNode aan = null;
5916
5917     String varName = null;
5918     if (left.kind() == Kind.NameNode) {
5919       NameDescriptor nd = ((NameNode) left).getName();
5920       varName = nd.toString();
5921     }
5922
5923     if (ltd.isClassNameRef() || (varName != null && varName.equals("this"))) {
5924       // using a class name directly or access using this
5925       if (fd.isStatic() && fd.isFinal()) {
5926         return null;
5927       }
5928     }
5929
5930     NodeTupleSet idxNodeTupleSet = new NodeTupleSet();
5931
5932     boolean isArrayCase = false;
5933     if (left instanceof ArrayAccessNode) {
5934
5935       isArrayCase = true;
5936       aan = (ArrayAccessNode) left;
5937
5938       currentArrayAccessNodeExpStr = aan.printNode(0);
5939       arrayAccessNodeStack.push(currentArrayAccessNodeExpStr);
5940
5941       left = aan.getExpression();
5942       analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, base,
5943           implicitFlowTupleSet, isLHS);
5944
5945     }
5946     base =
5947         analyzeFlowExpressionNode(md, nametable, left, nodeSet, base, implicitFlowTupleSet, isLHS);
5948
5949     if (base == null) {
5950       // in this case, field is TOP location
5951       return null;
5952     } else {
5953
5954       NTuple<Descriptor> flowFieldTuple = new NTuple<Descriptor>(base.toList());
5955
5956       if (!left.getType().isPrimitive()) {
5957         if (!fd.getSymbol().equals("length")) {
5958           // array.length access, just have the location of the array
5959           flowFieldTuple.add(fd);
5960           nodeSet.removeTuple(base);
5961         }
5962       }
5963       getFlowGraph(md).createNewFlowNode(flowFieldTuple);
5964
5965       if (isLHS) {
5966         for (Iterator<NTuple<Descriptor>> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) {
5967           NTuple<Descriptor> idxTuple = idxIter.next();
5968           getFlowGraph(md).addValueFlowEdge(idxTuple, flowFieldTuple);
5969         }
5970
5971         GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
5972         for (Iterator<NTuple<Location>> iterator = idxNodeTupleSet.globalIterator(); iterator
5973             .hasNext();) {
5974           NTuple<Location> calleeReturnLocTuple = iterator.next();
5975
5976           globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple,
5977               translateToLocTuple(md, flowFieldTuple));
5978         }
5979
5980       } else {
5981         nodeSet.addTupleSet(idxNodeTupleSet);
5982
5983         // if it is the array case and not the LHS case
5984         if (isArrayCase) {
5985           arrayAccessNodeStack.pop();
5986
5987           if (arrayAccessNodeStack.isEmpty()
5988               || !arrayAccessNodeStack.peek().startsWith(currentArrayAccessNodeExpStr)) {
5989             NodeTupleSet nodeSetArrayAccessExp = new NodeTupleSet();
5990
5991             nodeSetArrayAccessExp.addTuple(flowFieldTuple);
5992             nodeSetArrayAccessExp.addTupleSet(idxNodeTupleSet);
5993             nodeSetArrayAccessExp.addTupleSet(nodeSet);
5994
5995             if (needToGenerateInterLoc(nodeSetArrayAccessExp)) {
5996               System.out.println("4");
5997               System.out.println("nodeSetArrayAccessExp=" + nodeSetArrayAccessExp);
5998               // System.out.println("idxNodeTupleSet.getGlobalLocTupleSet()="
5999               // + idxNodeTupleSet.getGlobalLocTupleSet());
6000
6001               NTuple<Descriptor> interTuple =
6002                   getFlowGraph(md).createIntermediateNode().getDescTuple();
6003
6004               for (Iterator<NTuple<Descriptor>> iter = nodeSetArrayAccessExp.iterator(); iter
6005                   .hasNext();) {
6006                 NTuple<Descriptor> higherTuple = iter.next();
6007                 addFlowGraphEdge(md, higherTuple, interTuple);
6008               }
6009
6010               FlowGraph fg = getFlowGraph(md);
6011               fg.addMapInterLocNodeToEnclosingDescriptor(interTuple.get(0),
6012                   getClassTypeDescriptor(base.get(base.size() - 1)));
6013
6014               nodeSet.clear();
6015               flowFieldTuple = interTuple;
6016             }
6017             nodeSet.addGlobalFlowTupleSet(idxNodeTupleSet.getGlobalLocTupleSet());
6018           }
6019
6020         }
6021
6022       }
6023       return flowFieldTuple;
6024     }
6025
6026   }
6027
6028   private void debug_printTreeNode(TreeNode tn) {
6029
6030     System.out.println("DEBUG: " + tn.printNode(0) + "                line#=" + tn.getNumLine());
6031
6032   }
6033
6034   private void analyzeFlowAssignmentNode(MethodDescriptor md, SymbolTable nametable,
6035       AssignmentNode an, NodeTupleSet nodeSet, NTuple<Descriptor> base,
6036       NodeTupleSet implicitFlowTupleSet) {
6037
6038     NodeTupleSet nodeSetRHS = new NodeTupleSet();
6039     NodeTupleSet nodeSetLHS = new NodeTupleSet();
6040
6041     boolean postinc = true;
6042     if (an.getOperation().getBaseOp() == null
6043         || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
6044             .getBaseOp().getOp() != Operation.POSTDEC)) {
6045       postinc = false;
6046     }
6047     // if LHS is array access node, need to capture value flows between an array
6048     // and its index value
6049     analyzeFlowExpressionNode(md, nametable, an.getDest(), nodeSetLHS, null, implicitFlowTupleSet,
6050         true);
6051
6052     if (!postinc) {
6053       // analyze value flows of rhs expression
6054       analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null, implicitFlowTupleSet,
6055           false);
6056
6057       System.out.println("-analyzeFlowAssignmentNode=" + an.printNode(0));
6058       System.out.println("-nodeSetLHS=" + nodeSetLHS);
6059       System.out.println("-nodeSetRHS=" + nodeSetRHS);
6060       System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet);
6061       // System.out.println("-");
6062
6063       if (an.getOperation().getOp() >= 2 && an.getOperation().getOp() <= 12) {
6064         // if assignment contains OP+EQ operator, creates edges from LHS to LHS
6065
6066         for (Iterator<NTuple<Descriptor>> iter = nodeSetLHS.iterator(); iter.hasNext();) {
6067           NTuple<Descriptor> fromTuple = iter.next();
6068           for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
6069             NTuple<Descriptor> toTuple = iter2.next();
6070             addFlowGraphEdge(md, fromTuple, toTuple);
6071           }
6072         }
6073       }
6074
6075       // creates edges from RHS to LHS
6076       NTuple<Descriptor> interTuple = null;
6077       if (needToGenerateInterLoc(nodeSetRHS)) {
6078         System.out.println("2");
6079         interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
6080       }
6081
6082       for (Iterator<NTuple<Descriptor>> iter = nodeSetRHS.iterator(); iter.hasNext();) {
6083         NTuple<Descriptor> fromTuple = iter.next();
6084         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
6085           NTuple<Descriptor> toTuple = iter2.next();
6086           addFlowGraphEdge(md, fromTuple, interTuple, toTuple);
6087         }
6088       }
6089
6090       // creates edges from implicitFlowTupleSet to LHS
6091       for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
6092         NTuple<Descriptor> fromTuple = iter.next();
6093         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
6094           NTuple<Descriptor> toTuple = iter2.next();
6095           addFlowGraphEdge(md, fromTuple, toTuple);
6096         }
6097       }
6098
6099       // create global flow edges if the callee gives return value flows to the caller
6100       GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
6101       for (Iterator<NTuple<Location>> iterator = nodeSetRHS.globalIterator(); iterator.hasNext();) {
6102         NTuple<Location> calleeReturnLocTuple = iterator.next();
6103         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
6104           NTuple<Descriptor> callerLHSTuple = iter2.next();
6105           System.out.println("$$$ GLOBAL FLOW ADD=" + calleeReturnLocTuple + " -> "
6106               + translateToLocTuple(md, callerLHSTuple));
6107
6108           globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple,
6109               translateToLocTuple(md, callerLHSTuple));
6110         }
6111       }
6112
6113       for (Iterator<NTuple<Location>> iterator = implicitFlowTupleSet.globalIterator(); iterator
6114           .hasNext();) {
6115         NTuple<Location> calleeReturnLocTuple = iterator.next();
6116         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
6117           NTuple<Descriptor> callerLHSTuple = iter2.next();
6118
6119           globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple,
6120               translateToLocTuple(md, callerLHSTuple));
6121           System.out.println("$$$ GLOBAL FLOW PCLOC ADD=" + calleeReturnLocTuple + " -> "
6122               + translateToLocTuple(md, callerLHSTuple));
6123         }
6124       }
6125
6126     } else {
6127       // postinc case
6128
6129       for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
6130         NTuple<Descriptor> tuple = iter2.next();
6131         addFlowGraphEdge(md, tuple, tuple);
6132       }
6133
6134       // creates edges from implicitFlowTupleSet to LHS
6135       for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
6136         NTuple<Descriptor> fromTuple = iter.next();
6137         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
6138           NTuple<Descriptor> toTuple = iter2.next();
6139           addFlowGraphEdge(md, fromTuple, toTuple);
6140         }
6141       }
6142
6143       GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
6144       for (Iterator<NTuple<Location>> iterator = implicitFlowTupleSet.globalIterator(); iterator
6145           .hasNext();) {
6146         NTuple<Location> calleeReturnLocTuple = iterator.next();
6147         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
6148           NTuple<Descriptor> callerLHSTuple = iter2.next();
6149           globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple,
6150               translateToLocTuple(md, callerLHSTuple));
6151           System.out.println("$$$ GLOBAL FLOW PC ADD=" + calleeReturnLocTuple + " -> "
6152               + translateToLocTuple(md, callerLHSTuple));
6153         }
6154       }
6155
6156     }
6157
6158     if (nodeSet != null) {
6159       nodeSet.addTupleSet(nodeSetLHS);
6160       nodeSet.addGlobalFlowTupleSet(nodeSetLHS.getGlobalLocTupleSet());
6161     }
6162   }
6163
6164   public FlowGraph getFlowGraph(MethodDescriptor md) {
6165     return mapMethodDescriptorToFlowGraph.get(md);
6166   }
6167
6168   private boolean addFlowGraphEdge(MethodDescriptor md, NTuple<Descriptor> from,
6169       NTuple<Descriptor> to) {
6170     FlowGraph graph = getFlowGraph(md);
6171     graph.addValueFlowEdge(from, to);
6172     return true;
6173   }
6174
6175   private void addFlowGraphEdge(MethodDescriptor md, NTuple<Descriptor> from,
6176       NTuple<Descriptor> inter, NTuple<Descriptor> to) {
6177
6178     FlowGraph graph = getFlowGraph(md);
6179
6180     if (inter != null) {
6181       graph.addValueFlowEdge(from, inter);
6182       graph.addValueFlowEdge(inter, to);
6183     } else {
6184       graph.addValueFlowEdge(from, to);
6185     }
6186
6187   }
6188
6189   public void writeInferredLatticeDotFile(ClassDescriptor cd, HierarchyGraph simpleHierarchyGraph,
6190       SSJavaLattice<String> locOrder, String nameSuffix) {
6191     System.out.println("@cd=" + cd);
6192     System.out.println("@sharedLoc=" + locOrder.getSharedLocSet());
6193     writeInferredLatticeDotFile(cd, null, simpleHierarchyGraph, locOrder, nameSuffix);
6194   }
6195
6196   public void writeInferredLatticeDotFile(ClassDescriptor cd, MethodDescriptor md,
6197       HierarchyGraph simpleHierarchyGraph, SSJavaLattice<String> locOrder, String nameSuffix) {
6198
6199     String fileName = "lattice_";
6200     if (md != null) {
6201       fileName +=
6202           cd.getSymbol().replaceAll("[\\W_]", "") + "_" + md.toString().replaceAll("[\\W_]", "");
6203     } else {
6204       fileName += cd.getSymbol().replaceAll("[\\W_]", "");
6205     }
6206
6207     fileName += nameSuffix;
6208
6209     System.out.println("***lattice=" + fileName + "    setsize=" + locOrder.getKeySet().size());
6210
6211     Set<Pair<String, String>> pairSet = locOrder.getOrderingPairSet();
6212
6213     Set<String> addedLocSet = new HashSet<String>();
6214
6215     if (pairSet.size() > 0) {
6216       try {
6217         BufferedWriter bw = new BufferedWriter(new FileWriter(fileName + ".dot"));
6218
6219         bw.write("digraph " + fileName + " {\n");
6220
6221         for (Iterator iterator = pairSet.iterator(); iterator.hasNext();) {
6222           // pair is in the form of <higher, lower>
6223           Pair<String, String> pair = (Pair<String, String>) iterator.next();
6224
6225           String highLocId = pair.getFirst();
6226           String lowLocId = pair.getSecond();
6227           if (!addedLocSet.contains(highLocId)) {
6228             addedLocSet.add(highLocId);
6229             drawNode(bw, locOrder, simpleHierarchyGraph, highLocId);
6230           }
6231
6232           if (!addedLocSet.contains(lowLocId)) {
6233             addedLocSet.add(lowLocId);
6234             drawNode(bw, locOrder, simpleHierarchyGraph, lowLocId);
6235           }
6236
6237           bw.write(highLocId + " -> " + lowLocId + ";\n");
6238         }
6239         bw.write("}\n");
6240         bw.close();
6241
6242       } catch (IOException e) {
6243         e.printStackTrace();
6244       }
6245
6246     }
6247
6248   }
6249
6250   private String convertMergeSetToString(HierarchyGraph graph, Set<HNode> mergeSet) {
6251     String str = "";
6252     for (Iterator iterator = mergeSet.iterator(); iterator.hasNext();) {
6253       HNode merged = (HNode) iterator.next();
6254       if (merged.isMergeNode()) {
6255         str += convertMergeSetToString(graph, graph.getMapHNodetoMergeSet().get(merged));
6256       } else {
6257         str += " " + merged.getName();
6258       }
6259     }
6260     return str;
6261   }
6262
6263   private void drawNode(BufferedWriter bw, SSJavaLattice<String> lattice, HierarchyGraph graph,
6264       String locName) throws IOException {
6265
6266     String prettyStr;
6267     if (lattice.isSharedLoc(locName)) {
6268       prettyStr = locName + "*";
6269     } else {
6270       prettyStr = locName;
6271     }
6272     // HNode node = graph.getHNode(locName);
6273     // if (node != null && node.isMergeNode()) {
6274     // Set<HNode> mergeSet = graph.getMapHNodetoMergeSet().get(node);
6275     // prettyStr += ":" + convertMergeSetToString(graph, mergeSet);
6276     // }
6277     bw.write(locName + " [label=\"" + prettyStr + "\"]" + ";\n");
6278   }
6279
6280   public void _debug_writeFlowGraph() {
6281     Set<MethodDescriptor> keySet = mapMethodDescriptorToFlowGraph.keySet();
6282
6283     for (Iterator<MethodDescriptor> iterator = keySet.iterator(); iterator.hasNext();) {
6284       MethodDescriptor md = (MethodDescriptor) iterator.next();
6285       FlowGraph fg = mapMethodDescriptorToFlowGraph.get(md);
6286       GlobalFlowGraph subGlobalFlowGraph = getSubGlobalFlowGraph(md);
6287       try {
6288         fg.writeGraph();
6289         subGlobalFlowGraph.writeGraph("_SUBGLOBAL");
6290       } catch (IOException e) {
6291         e.printStackTrace();
6292       }
6293     }
6294
6295   }
6296
6297 }
6298
6299 class CyclicFlowException extends Exception {
6300
6301 }
6302
6303 class InterDescriptor extends Descriptor {
6304
6305   Pair<MethodInvokeNode, Integer> minArgIdxPair;
6306
6307   public InterDescriptor(String name) {
6308     super(name);
6309   }
6310
6311   public void setMethodArgIdxPair(MethodInvokeNode min, int idx) {
6312     minArgIdxPair = new Pair<MethodInvokeNode, Integer>(min, new Integer(idx));
6313   }
6314
6315   public Pair<MethodInvokeNode, Integer> getMethodArgIdxPair() {
6316     return minArgIdxPair;
6317   }
6318
6319 }