Robust/src/Analysis/SSJava/LocationInference.java

   1 package Analysis.SSJava;
   2
   3 import java.io.BufferedReader;
   4 import java.io.BufferedWriter;
   5 import java.io.FileReader;
   6 import java.io.FileWriter;
   7 import java.io.IOException;
   8 import java.util.ArrayList;
   9 import java.util.Collections;
  10 import java.util.Comparator;
  11 import java.util.HashMap;
  12 import java.util.HashSet;
  13 import java.util.Iterator;
  14 import java.util.LinkedList;
  15 import java.util.List;
  16 import java.util.Map;
  17 import java.util.Set;
  18 import java.util.Stack;
  19 import java.util.Vector;
  20
  21 import IR.ClassDescriptor;
  22 import IR.Descriptor;
  23 import IR.FieldDescriptor;
  24 import IR.MethodDescriptor;
  25 import IR.NameDescriptor;
  26 import IR.Operation;
  27 import IR.State;
  28 import IR.SymbolTable;
  29 import IR.TypeDescriptor;
  30 import IR.TypeUtil;
  31 import IR.VarDescriptor;
  32 import IR.Tree.ArrayAccessNode;
  33 import IR.Tree.AssignmentNode;
  34 import IR.Tree.BlockExpressionNode;
  35 import IR.Tree.BlockNode;
  36 import IR.Tree.BlockStatementNode;
  37 import IR.Tree.CastNode;
  38 import IR.Tree.CreateObjectNode;
  39 import IR.Tree.DeclarationNode;
  40 import IR.Tree.ExpressionNode;
  41 import IR.Tree.FieldAccessNode;
  42 import IR.Tree.IfStatementNode;
  43 import IR.Tree.Kind;
  44 import IR.Tree.LiteralNode;
  45 import IR.Tree.LoopNode;
  46 import IR.Tree.MethodInvokeNode;
  47 import IR.Tree.NameNode;
  48 import IR.Tree.OpNode;
  49 import IR.Tree.ReturnNode;
  50 import IR.Tree.SubBlockNode;
  51 import IR.Tree.SwitchBlockNode;
  52 import IR.Tree.SwitchStatementNode;
  53 import IR.Tree.TertiaryNode;
  54 import IR.Tree.TreeNode;
  55 import Util.Pair;
  56
  57 public class LocationInference {
  58
  59   static int COUNT = 0;
  60
  61   State state;
  62   SSJavaAnalysis ssjava;
  63   TypeUtil tu;
  64
  65   List<ClassDescriptor> temp_toanalyzeList;
  66   List<MethodDescriptor> temp_toanalyzeMethodList;
  67   Map<MethodDescriptor, FlowGraph> mapMethodDescriptorToFlowGraph;
  68
  69   LinkedList<MethodDescriptor> toanalyze_methodDescList;
  70   Set<ClassDescriptor> toanalyze_classDescSet;
  71
  72   // InheritanceTree<ClassDescriptor> inheritanceTree;
  73
  74   // map a method descriptor to its set of parameter descriptors
  75   Map<MethodDescriptor, Set<Descriptor>> mapMethodDescriptorToParamDescSet;
  76
  77   // keep current descriptors to visit in fixed-point interprocedural analysis,
  78   private Stack<MethodDescriptor> methodDescriptorsToVisitStack;
  79
  80   // map a descriptor to a naive lattice
  81   private Map<Descriptor, SSJavaLattice<String>> desc2naiveLattice;
  82
  83   // map a class descriptor to a field lattice
  84   private Map<ClassDescriptor, SSJavaLattice<String>> cd2lattice;
  85
  86   // map a method descriptor to a method lattice
  87   private Map<MethodDescriptor, SSJavaLattice<String>> md2lattice;
  88
  89   // map a method/class descriptor to a hierarchy graph
  90   private Map<Descriptor, HierarchyGraph> mapDescriptorToHierarchyGraph;
  91
  92   // map a method/class descriptor to a skeleton hierarchy graph
  93   private Map<Descriptor, HierarchyGraph> mapDescriptorToSkeletonHierarchyGraph;
  94
  95   private Map<Descriptor, HierarchyGraph> mapDescriptorToSimpleHierarchyGraph;
  96
  97   // map a method/class descriptor to a skeleton hierarchy graph with combination nodes
  98   private Map<Descriptor, HierarchyGraph> mapDescriptorToCombineSkeletonHierarchyGraph;
  99
 100   // map a descriptor to a skeleton lattice
 101   private Map<Descriptor, SSJavaLattice<String>> mapDescriptorToSkeletonLattice;
 102
 103   // map a method descriptor to the set of method invocation nodes which are
 104   // invoked by the method descriptor
 105   private Map<MethodDescriptor, Set<MethodInvokeNode>> mapMethodDescriptorToMethodInvokeNodeSet;
 106
 107   private Map<MethodInvokeNode, Map<Integer, NTuple<Descriptor>>> mapMethodInvokeNodeToArgIdxMap;
 108
 109   private Map<MethodInvokeNode, NTuple<Descriptor>> mapMethodInvokeNodeToBaseTuple;
 110
 111   private Map<MethodInvokeNode, Set<NTuple<Location>>> mapMethodInvokeNodeToPCLocTupleSet;
 112
 113   private Map<MethodDescriptor, MethodLocationInfo> mapMethodDescToMethodLocationInfo;
 114
 115   private Map<ClassDescriptor, LocationInfo> mapClassToLocationInfo;
 116
 117   private Map<MethodDescriptor, Set<MethodDescriptor>> mapMethodToCalleeSet;
 118
 119   private Map<MethodDescriptor, Set<FlowNode>> mapMethodDescToParamNodeFlowsToReturnValue;
 120
 121   private Map<String, Vector<String>> mapFileNameToLineVector;
 122
 123   private Map<Descriptor, Integer> mapDescToDefinitionLine;
 124
 125   private Map<Descriptor, LocationSummary> mapDescToLocationSummary;
 126
 127   private Map<MethodDescriptor, Set<MethodInvokeNode>> mapMethodDescToMethodInvokeNodeSet;
 128
 129   // maps a method descriptor to a sub global flow graph that captures all value flows caused by the
 130   // set of callees reachable from the method
 131   private Map<MethodDescriptor, GlobalFlowGraph> mapMethodDescriptorToSubGlobalFlowGraph;
 132
 133   private Map<MethodInvokeNode, Map<NTuple<Descriptor>, NTuple<Descriptor>>> mapMethodInvokeNodeToMapCallerArgToCalleeArg;
 134
 135   private Map<MethodDescriptor, Boolean> mapMethodDescriptorToCompositeReturnCase;
 136
 137   private Map<MethodDescriptor, MethodDescriptor> mapMethodDescToHighestOverriddenMethodDesc;
 138
 139   private Map<MethodDescriptor, Set<MethodDescriptor>> mapHighestOverriddenMethodDescToMethodDescSet;
 140
 141   private Map<MethodDescriptor, NTuple<Descriptor>> mapHighestOverriddenMethodDescToReturnLocTuple;
 142
 143   private Map<MethodDescriptor, NTuple<Descriptor>> mapHighestOverriddenMethodDescToPCLocTuple;
 144
 145   private Map<MethodDescriptor, Set<NTuple<Descriptor>>> mapHighestOverriddenMethodDescToSetLowerThanPCLoc;
 146
 147   private Map<MethodDescriptor, Set<NTuple<Descriptor>>> mapHighestOverriddenMethodDescToSetHigherThanRETURNLoc;
 148
 149   public static final String GLOBALLOC = "GLOBALLOC";
 150
 151   public static final String INTERLOC = "INTERLOC";
 152
 153   public static final String PCLOC = "_PCLOC_";
 154
 155   public static final String RLOC = "_RLOC_";
 156
 157   public static final Descriptor GLOBALDESC = new NameDescriptor(GLOBALLOC);
 158
 159   public static final Descriptor TOPDESC = new NameDescriptor(SSJavaAnalysis.TOP);
 160
 161   public static final Descriptor BOTTOMDESC = new NameDescriptor(SSJavaAnalysis.BOTTOM);
 162
 163   public static final Descriptor RETURNLOC = new NameDescriptor(RLOC);
 164
 165   public static final Descriptor LITERALDESC = new NameDescriptor("LITERAL");
 166
 167   public static final HNode TOPHNODE = new HNode(TOPDESC);
 168
 169   public static final HNode BOTTOMHNODE = new HNode(BOTTOMDESC);
 170
 171   public static String newline = System.getProperty("line.separator");
 172
 173   LocationInfo curMethodInfo;
 174
 175   private boolean hasChanges = false;
 176
 177   boolean debug = true;
 178
 179   public static int locSeed = 0;
 180
 181   private Stack<String> arrayAccessNodeStack;
 182
 183   private ClassDescriptor rootClassDescriptor;
 184
 185   private BuildLattice buildLattice;
 186
 187   public static int numLocationsSInfer = 0;
 188   public static int numLocationsNaive = 0;
 189
 190   public static int numPathsSInfer = 0;
 191   public static int numPathsNaive = 0;
 192
 193   public Map<Descriptor, Integer> mapNumPathsMapSInfer;
 194   public Map<Descriptor, Integer> mapNumLocsMapSInfer;
 195
 196   public Map<Descriptor, Integer> mapNumPathsMapNaive;
 197   public Map<Descriptor, Integer> mapNumLocsMapNaive;
 198
 199   public LocationInference(SSJavaAnalysis ssjava, State state, TypeUtil tu) {
 200     this.ssjava = ssjava;
 201     this.state = state;
 202     this.tu = tu;
 203     this.toanalyze_classDescSet = new HashSet<ClassDescriptor>();
 204     this.temp_toanalyzeList = new ArrayList<ClassDescriptor>();
 205     this.temp_toanalyzeMethodList = new ArrayList<MethodDescriptor>();
 206     this.mapMethodDescriptorToFlowGraph = new HashMap<MethodDescriptor, FlowGraph>();
 207     this.cd2lattice = new HashMap<ClassDescriptor, SSJavaLattice<String>>();
 208     this.md2lattice = new HashMap<MethodDescriptor, SSJavaLattice<String>>();
 209     this.desc2naiveLattice = new HashMap<Descriptor, SSJavaLattice<String>>();
 210
 211     this.methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
 212     this.mapMethodDescriptorToMethodInvokeNodeSet =
 213         new HashMap<MethodDescriptor, Set<MethodInvokeNode>>();
 214     this.mapMethodInvokeNodeToArgIdxMap =
 215         new HashMap<MethodInvokeNode, Map<Integer, NTuple<Descriptor>>>();
 216     this.mapMethodDescToMethodLocationInfo = new HashMap<MethodDescriptor, MethodLocationInfo>();
 217     this.mapMethodToCalleeSet = new HashMap<MethodDescriptor, Set<MethodDescriptor>>();
 218     this.mapClassToLocationInfo = new HashMap<ClassDescriptor, LocationInfo>();
 219
 220     this.mapFileNameToLineVector = new HashMap<String, Vector<String>>();
 221     this.mapDescToDefinitionLine = new HashMap<Descriptor, Integer>();
 222     this.mapMethodDescToParamNodeFlowsToReturnValue =
 223         new HashMap<MethodDescriptor, Set<FlowNode>>();
 224
 225     this.mapDescriptorToHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
 226     this.mapMethodInvokeNodeToBaseTuple = new HashMap<MethodInvokeNode, NTuple<Descriptor>>();
 227
 228     this.mapDescriptorToSkeletonHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
 229     this.mapDescriptorToCombineSkeletonHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
 230     this.mapDescriptorToSimpleHierarchyGraph = new HashMap<Descriptor, HierarchyGraph>();
 231
 232     this.mapDescriptorToSkeletonLattice = new HashMap<Descriptor, SSJavaLattice<String>>();
 233
 234     this.mapDescToLocationSummary = new HashMap<Descriptor, LocationSummary>();
 235
 236     this.mapMethodDescriptorToSubGlobalFlowGraph = new HashMap<MethodDescriptor, GlobalFlowGraph>();
 237
 238     this.mapMethodInvokeNodeToMapCallerArgToCalleeArg =
 239         new HashMap<MethodInvokeNode, Map<NTuple<Descriptor>, NTuple<Descriptor>>>();
 240
 241     this.mapMethodInvokeNodeToPCLocTupleSet =
 242         new HashMap<MethodInvokeNode, Set<NTuple<Location>>>();
 243
 244     this.arrayAccessNodeStack = new Stack<String>();
 245
 246     this.mapMethodDescToMethodInvokeNodeSet =
 247         new HashMap<MethodDescriptor, Set<MethodInvokeNode>>();
 248
 249     this.mapMethodDescriptorToCompositeReturnCase = new HashMap<MethodDescriptor, Boolean>();
 250
 251     mapMethodDescToHighestOverriddenMethodDesc = new HashMap<MethodDescriptor, MethodDescriptor>();
 252
 253     mapHighestOverriddenMethodDescToSetLowerThanPCLoc =
 254         new HashMap<MethodDescriptor, Set<NTuple<Descriptor>>>();
 255
 256     mapHighestOverriddenMethodDescToMethodDescSet =
 257         new HashMap<MethodDescriptor, Set<MethodDescriptor>>();
 258
 259     mapHighestOverriddenMethodDescToReturnLocTuple =
 260         new HashMap<MethodDescriptor, NTuple<Descriptor>>();
 261
 262     mapHighestOverriddenMethodDescToPCLocTuple =
 263         new HashMap<MethodDescriptor, NTuple<Descriptor>>();
 264
 265     mapHighestOverriddenMethodDescToSetHigherThanRETURNLoc =
 266         new HashMap<MethodDescriptor, Set<NTuple<Descriptor>>>();
 267
 268     mapNumPathsMapSInfer = new HashMap<Descriptor, Integer>();
 269     mapNumLocsMapSInfer = new HashMap<Descriptor, Integer>();
 270
 271     mapNumPathsMapNaive = new HashMap<Descriptor, Integer>();
 272     mapNumLocsMapNaive = new HashMap<Descriptor, Integer>();
 273
 274     this.buildLattice = new BuildLattice(this);
 275
 276   }
 277
 278   public void setupToAnalyze() {
 279     SymbolTable classtable = state.getClassSymbolTable();
 280     temp_toanalyzeList.clear();
 281     temp_toanalyzeList.addAll(classtable.getValueSet());
 282     // Collections.sort(toanalyzeList, new Comparator<ClassDescriptor>() {
 283     // public int compare(ClassDescriptor o1, ClassDescriptor o2) {
 284     // return o1.getClassName().compareToIgnoreCase(o2.getClassName());
 285     // }
 286     // });
 287   }
 288
 289   public void setupToAnalazeMethod(ClassDescriptor cd) {
 290
 291     SymbolTable methodtable = cd.getMethodTable();
 292     temp_toanalyzeMethodList.clear();
 293     temp_toanalyzeMethodList.addAll(methodtable.getValueSet());
 294     Collections.sort(temp_toanalyzeMethodList, new Comparator<MethodDescriptor>() {
 295       public int compare(MethodDescriptor o1, MethodDescriptor o2) {
 296         return o1.getSymbol().compareToIgnoreCase(o2.getSymbol());
 297       }
 298     });
 299   }
 300
 301   public boolean toAnalyzeMethodIsEmpty() {
 302     return temp_toanalyzeMethodList.isEmpty();
 303   }
 304
 305   public boolean toAnalyzeIsEmpty() {
 306     return temp_toanalyzeList.isEmpty();
 307   }
 308
 309   public ClassDescriptor toAnalyzeNext() {
 310     return temp_toanalyzeList.remove(0);
 311   }
 312
 313   public MethodDescriptor toAnalyzeMethodNext() {
 314     return temp_toanalyzeMethodList.remove(0);
 315   }
 316
 317   public void inference() {
 318
 319     ssjava.init();
 320
 321     // construct value flow graph
 322     constructFlowGraph();
 323
 324     constructGlobalFlowGraph();
 325
 326     checkReturnNodes();
 327
 328     assignCompositeLocation();
 329     updateFlowGraph();
 330     calculateExtraLocations();
 331     addAdditionalOrderingConstraints();
 332
 333     _debug_writeFlowGraph();
 334
 335     buildInheritanceTree();
 336     calculateReturnPCLocInheritance();
 337
 338     constructHierarchyGraph();
 339
 340     addInheritanceConstraintsToHierarchyGraph();
 341
 342     debug_writeHierarchyDotFiles();
 343
 344     simplifyHierarchyGraph();
 345
 346     debug_writeSimpleHierarchyDotFiles();
 347
 348     constructSkeletonHierarchyGraph();
 349
 350     debug_writeSkeletonHierarchyDotFiles();
 351
 352     insertCombinationNodes();
 353
 354     debug_writeSkeletonCombinationHierarchyDotFiles();
 355
 356     buildLatticeInheritanceTree();
 357     // buildLattice();
 358
 359     debug_writeLattices();
 360
 361     updateCompositeLocationAssignments();
 362
 363     generateMethodSummary();
 364
 365     generateAnnoatedCode();
 366
 367     for (Iterator iterator = cd2lattice.keySet().iterator(); iterator.hasNext();) {
 368       ClassDescriptor cd = (ClassDescriptor) iterator.next();
 369       SSJavaLattice<String> lattice = getLattice(cd);
 370       HierarchyGraph hg = mapDescriptorToHierarchyGraph.get(cd);
 371       // System.out.println("~~~\t" + cd + "\t" + lattice.getKeySet().size() + "\t"
 372       // + hg.getNodeSet().size());
 373     }
 374
 375     for (Iterator iterator = md2lattice.keySet().iterator(); iterator.hasNext();) {
 376       MethodDescriptor md = (MethodDescriptor) iterator.next();
 377       SSJavaLattice<String> locOrder = getLattice(md);
 378       // writeLatticeDotFile(md.getClassDesc(), md, getMethodLattice(md));
 379       HierarchyGraph hg = mapDescriptorToHierarchyGraph.get(md);
 380       // System.out.println("~~~\t" + md.getClassDesc() + "_" + md + "\t"
 381       // + locOrder.getKeySet().size() + "\t" + hg.getNodeSet().size());
 382     }
 383
 384     if (state.SSJAVA_INFER_NAIVE_WRITEDOTS) {
 385       System.out.println("The number of elements: Naive=" + numLocationsNaive);
 386     }
 387     System.out.println("The number of elements: SInfer=" + numLocationsSInfer);
 388
 389     writeNumLocsPathsCSVFile();
 390
 391     System.exit(0);
 392
 393   }
 394
 395   private void calculateReturnPCLocInheritance() {
 396     calculateHighestPCLocInheritance();
 397     calculateLowestReturnLocInheritance();
 398     updateFlowGraphPCReturnLocInheritance();
 399   }
 400
 401   private void updateFlowGraphPCReturnLocInheritance() {
 402
 403     Set<MethodDescriptor> keySet = mapHighestOverriddenMethodDescToMethodDescSet.keySet();
 404     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 405       MethodDescriptor highestMethodDesc = (MethodDescriptor) iterator.next();
 406
 407       if (mapHighestOverriddenMethodDescToMethodDescSet.get(highestMethodDesc).size() == 1) {
 408         continue;
 409       }
 410
 411       Set<MethodDescriptor> methodDescSet =
 412           mapHighestOverriddenMethodDescToMethodDescSet.get(highestMethodDesc);
 413
 414       NTuple<Descriptor> highestPCLocDescTuple =
 415           mapHighestOverriddenMethodDescToPCLocTuple.get(highestMethodDesc);
 416
 417       NTuple<Descriptor> highestRETURNLocDescTuple =
 418           mapHighestOverriddenMethodDescToReturnLocTuple.get(highestMethodDesc);
 419
 420       // System.out.println("\n$$$$$$$$$$$$$$$$updateFlowGraphPCReturnLocInheritance="
 421       // + highestMethodDesc);
 422       // System.out.println("-----highestPCLoc=" + highestPCLocDescTuple);
 423       // System.out.println("-----highestRETURNLoc=" + highestRETURNLocDescTuple);
 424
 425       for (Iterator iterator2 = methodDescSet.iterator(); iterator2.hasNext();) {
 426         MethodDescriptor md = (MethodDescriptor) iterator2.next();
 427         // System.out.println("\n --------MD=" + md);
 428         FlowGraph flowGraph = getFlowGraph(md);
 429
 430         MethodSummary summary = getMethodSummary(md);
 431         CompositeLocation curPCLoc = summary.getPCLoc();
 432         NTuple<Descriptor> curPCDescTuple = translateToDescTuple(curPCLoc.getTuple());
 433         // System.out.println("md=" + md + "  curPCLoc=" + curPCLoc);
 434         // System.out.println("highestPCLoc=" + highestPCLocDescTuple);
 435
 436         if (highestPCLocDescTuple == null) {
 437           // this case: PCLOC is top
 438           // System.out.println("###SET PCLOC AS TOP");
 439           if (curPCDescTuple != null && !curPCLoc.get(0).isTop()) {
 440             FlowNode pcFlowNode = flowGraph.getFlowNode(curPCDescTuple);
 441             flowGraph.removeNode(pcFlowNode);
 442           }
 443           summary.setPCLoc(new CompositeLocation(new Location(md, Location.TOP)));
 444         } else {
 445           NTuple<Descriptor> newPCDescTuple = new NTuple<Descriptor>();
 446           if (highestPCLocDescTuple.size() == 1) {
 447             newPCDescTuple.add(highestPCLocDescTuple.get(0));
 448           } else {
 449             newPCDescTuple.add(md.getThis());
 450             newPCDescTuple.add(highestPCLocDescTuple.get(1));
 451           }
 452           if (!curPCDescTuple.equals(newPCDescTuple)) {
 453             FlowNode pcFlowNode = flowGraph.getFlowNode(curPCDescTuple);
 454             flowGraph.updateTuple(pcFlowNode, newPCDescTuple);
 455             // flowGraph.removeNode(pcFlowNode);
 456             Set<NTuple<Descriptor>> descSetLowerThanPCLoc =
 457                 mapHighestOverriddenMethodDescToSetLowerThanPCLoc.get(highestMethodDesc);
 458             for (Iterator iterator3 = descSetLowerThanPCLoc.iterator(); iterator3.hasNext();) {
 459               NTuple<Descriptor> lowerNTuple = (NTuple<Descriptor>) iterator3.next();
 460               flowGraph.addValueFlowEdge(newPCDescTuple, lowerNTuple);
 461             }
 462             CompositeLocation newPCCompLoc =
 463                 new CompositeLocation(translateToLocTuple(md, newPCDescTuple));
 464             summary.setPCLoc(newPCCompLoc);
 465           }
 466
 467         }
 468
 469         // update return loc
 470         if (highestRETURNLocDescTuple != null) {
 471           CompositeLocation curRETURNLoc = summary.getRETURNLoc();
 472           NTuple<Descriptor> curReturnDescTuple = translateToDescTuple(curRETURNLoc.getTuple());
 473
 474           if (!curReturnDescTuple.equals(highestRETURNLocDescTuple)) {
 475             // handle the case that RETURNLOC is started with 'this'...
 476             NTuple<Descriptor> newRETURNLocDescTuple = new NTuple<Descriptor>();
 477             if (highestRETURNLocDescTuple.size() == 1) {
 478               newRETURNLocDescTuple.add(highestRETURNLocDescTuple.get(0));
 479             } else {
 480               newRETURNLocDescTuple.add(md.getThis());
 481               newRETURNLocDescTuple.add(highestRETURNLocDescTuple.get(1));
 482             }
 483
 484             FlowNode returnFlowNode = flowGraph.getFlowNode(curReturnDescTuple);
 485             flowGraph.updateTuple(returnFlowNode, newRETURNLocDescTuple);
 486
 487             Set<NTuple<Descriptor>> descSetHigherThanRETURNLoc =
 488                 mapHighestOverriddenMethodDescToSetHigherThanRETURNLoc.get(highestMethodDesc);
 489             for (Iterator iterator3 = descSetHigherThanRETURNLoc.iterator(); iterator3.hasNext();) {
 490               NTuple<Descriptor> higherNTuple = (NTuple<Descriptor>) iterator3.next();
 491               flowGraph.addValueFlowEdge(higherNTuple, newRETURNLocDescTuple);
 492             }
 493
 494             CompositeLocation newRETURNLocCompLoc =
 495                 new CompositeLocation(translateToLocTuple(md, newRETURNLocDescTuple));
 496             summary.setRETURNLoc(newRETURNLocCompLoc);
 497           }
 498         }
 499       }
 500     }
 501   }
 502
 503   private void calculateHighestPCLocInheritance() {
 504
 505     Set<MethodDescriptor> keySet = mapHighestOverriddenMethodDescToMethodDescSet.keySet();
 506
 507     Map<MethodDescriptor, Integer> mapMethodDescToParamCount =
 508         new HashMap<MethodDescriptor, Integer>();
 509
 510     next: for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 511       MethodDescriptor highestMethodDesc = (MethodDescriptor) iterator.next();
 512
 513       NTuple<Descriptor> tempTuple = null;
 514
 515       if (getMethodSummary(highestMethodDesc).getPCLoc() != null) {
 516
 517         Set<MethodDescriptor> methodDescSet =
 518             mapHighestOverriddenMethodDescToMethodDescSet.get(highestMethodDesc);
 519
 520         if (methodDescSet.size() > 1) {
 521           // System.out.println("---method desc set=" + methodDescSet + "  from=" +
 522           // highestMethodDesc);
 523         } else {
 524           continue next;
 525         }
 526
 527         for (Iterator iterator2 = methodDescSet.iterator(); iterator2.hasNext();) {
 528           MethodDescriptor md = (MethodDescriptor) iterator2.next();
 529
 530           FlowGraph flowGraph = getFlowGraph(md);
 531           if (flowGraph == null) {
 532             continue;
 533           }
 534           Set<FlowNode> paramNodeSet = flowGraph.getParamFlowNodeSet();
 535           // System.out.println("###md=" + md + "   paramNodeSet=" + paramNodeSet);
 536
 537           CompositeLocation pcLOC = getMethodSummary(md).getPCLoc();
 538           // System.out.println("---pcLOC=" + pcLOC);
 539
 540           if (md.equals(highestMethodDesc)) {
 541             mapHighestOverriddenMethodDescToPCLocTuple.put(highestMethodDesc,
 542                 translateToDescTuple(pcLOC.getTuple()));
 543           }
 544
 545           if (!pcLOC.get(0).isTop()) {
 546
 547             FlowNode pcFlowNode = flowGraph.getFlowNode(translateToDescTuple(pcLOC.getTuple()));
 548
 549             int count = 0;
 550             for (Iterator iterator3 = paramNodeSet.iterator(); iterator3.hasNext();) {
 551               FlowNode paramNode = (FlowNode) iterator3.next();
 552               if (flowGraph.getReachableSetFrom(pcFlowNode.getCurrentDescTuple().subList(0, 1))
 553                   .contains(paramNode)) {
 554                 count++;
 555               }
 556             }
 557             mapMethodDescToParamCount.put(md, count);
 558
 559           } else {
 560
 561             // the PC location is top
 562             // if one of pcloc among the method inheritance chain has the TOP,
 563             // all methods in the same chain should have the TOP.
 564             mapHighestOverriddenMethodDescToPCLocTuple.remove(highestMethodDesc);
 565             // System.out.println("highest=" + highestMethodDesc + "  HIGHEST PCLOC="
 566             // + mapHighestOverriddenMethodDescToPCLocTuple.get(highestMethodDesc));
 567
 568             Set<NTuple<Descriptor>> descTupleSetLowerThanPC = new HashSet<NTuple<Descriptor>>();
 569             for (Iterator iterator3 = paramNodeSet.iterator(); iterator3.hasNext();) {
 570               FlowNode flowNode = (FlowNode) iterator3.next();
 571               descTupleSetLowerThanPC.add(flowNode.getCurrentDescTuple());
 572             }
 573             mapHighestOverriddenMethodDescToSetLowerThanPCLoc.put(highestMethodDesc,
 574                 descTupleSetLowerThanPC);
 575
 576             continue next;
 577           }
 578         }
 579
 580         // identify which method in the inheritance chain has the highest PCLOC
 581         // basically, finds a method that has the highest count or TOP location
 582         int highestCount = -1;
 583         MethodDescriptor methodDescHighestCount = null;
 584         for (Iterator iterator2 = methodDescSet.iterator(); iterator2.hasNext();) {
 585           MethodDescriptor methodDesc = (MethodDescriptor) iterator2.next();
 586           if (mapMethodDescToParamCount.containsKey(methodDesc)) {
 587             int curCount = mapMethodDescToParamCount.get(methodDesc).intValue();
 588             if (highestCount < curCount) {
 589               highestCount = curCount;
 590               methodDescHighestCount = methodDesc;
 591             }
 592           }
 593         }
 594
 595         if (methodDescHighestCount != null) {
 596           FlowGraph flowGraph = getFlowGraph(methodDescHighestCount);
 597           CompositeLocation pcLOC = getMethodSummary(methodDescHighestCount).getPCLoc();
 598           FlowNode pcFlowNode = flowGraph.getFlowNode(translateToDescTuple(pcLOC.getTuple()));
 599           Set<FlowNode> reachableSet =
 600               flowGraph.getReachableSetFrom(pcFlowNode.getCurrentDescTuple().subList(0, 1));
 601
 602           Set<FlowNode> reachableParamNodeSet = new HashSet<FlowNode>();
 603           for (Iterator iterator3 = reachableSet.iterator(); iterator3.hasNext();) {
 604             FlowNode flowNode = (FlowNode) iterator3.next();
 605             if (flowGraph.isParameter(flowNode.getCurrentDescTuple())) {
 606               reachableParamNodeSet.add(flowNode);
 607             }
 608
 609           }
 610
 611           Set<NTuple<Descriptor>> descTupleSetLowerThanPC = new HashSet<NTuple<Descriptor>>();
 612           for (Iterator iterator2 = reachableParamNodeSet.iterator(); iterator2.hasNext();) {
 613             FlowNode flowNode = (FlowNode) iterator2.next();
 614             descTupleSetLowerThanPC.add(flowNode.getCurrentDescTuple());
 615           }
 616
 617           // mapHighestOverriddenMethodDescToPCLocTuple.remove(highestMethodDesc);
 618           mapHighestOverriddenMethodDescToSetLowerThanPCLoc.put(highestMethodDesc,
 619               descTupleSetLowerThanPC);
 620         }
 621
 622       }
 623
 624       // System.out.println("####################################");
 625       // System.out.println("  highest=" + highestMethodDesc + "  HIGHEST PCLOC="
 626       // + mapHighestOverriddenMethodDescToPCLocTuple.get(highestMethodDesc));
 627       // System.out.println("  setLowerThanPCLoc="
 628       // + mapHighestOverriddenMethodDescToSetLowerThanPCLoc.get(highestMethodDesc));
 629     }
 630
 631   }
 632
 633   private void calculateLowestReturnLocInheritance() {
 634
 635     Set<MethodDescriptor> keySet = mapHighestOverriddenMethodDescToMethodDescSet.keySet();
 636
 637     Map<MethodDescriptor, Integer> mapMethodDescToParamCount =
 638         new HashMap<MethodDescriptor, Integer>();
 639
 640     next: for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 641       MethodDescriptor highestMethodDesc = (MethodDescriptor) iterator.next();
 642
 643       Set<MethodDescriptor> methodDescSet =
 644           mapHighestOverriddenMethodDescToMethodDescSet.get(highestMethodDesc);
 645
 646       if (methodDescSet.size() > 1 && getMethodSummary(highestMethodDesc).getRETURNLoc() != null) {
 647       } else {
 648         continue next;
 649       }
 650
 651       for (Iterator iterator2 = methodDescSet.iterator(); iterator2.hasNext();) {
 652         MethodDescriptor md = (MethodDescriptor) iterator2.next();
 653
 654         FlowGraph flowGraph = getFlowGraph(md);
 655         Set<FlowNode> paramNodeSet = flowGraph.getParamFlowNodeSet();
 656
 657         CompositeLocation returnLoc = getMethodSummary(md).getRETURNLoc();
 658
 659         FlowNode returnFlowNode = flowGraph.getFlowNode(translateToDescTuple(returnLoc.getTuple()));
 660
 661         int count = 0;
 662         for (Iterator iterator3 = paramNodeSet.iterator(); iterator3.hasNext();) {
 663           FlowNode paramNode = (FlowNode) iterator3.next();
 664           if (flowGraph.getReachableSetFrom(paramNode.getCurrentDescTuple().subList(0, 1))
 665               .contains(returnFlowNode)) {
 666             count++;
 667           }
 668         }
 669         mapMethodDescToParamCount.put(md, count);
 670         // System.out.println("###returnLoc=" + returnLoc + "    count higher=" + count);
 671       }
 672
 673       // identify which method in the inheritance chain has the highest PCLOC
 674       // basically, finds a method that has the highest count or TOP location
 675       int highestCount = -1;
 676       MethodDescriptor methodDescHighestCount = null;
 677       for (Iterator iterator2 = methodDescSet.iterator(); iterator2.hasNext();) {
 678         MethodDescriptor methodDesc = (MethodDescriptor) iterator2.next();
 679         int curCount = mapMethodDescToParamCount.get(methodDesc).intValue();
 680         if (highestCount < curCount) {
 681           highestCount = curCount;
 682           methodDescHighestCount = methodDesc;
 683         }
 684       }
 685
 686       if (methodDescHighestCount != null) {
 687         FlowGraph flowGraph = getFlowGraph(methodDescHighestCount);
 688         CompositeLocation returnLOC = getMethodSummary(methodDescHighestCount).getRETURNLoc();
 689         NTuple<Descriptor> returnLocTuple = translateToDescTuple(returnLOC.getTuple());
 690         FlowNode returnFlowNode = flowGraph.getFlowNode(returnLocTuple);
 691
 692         Set<FlowNode> curMethodParamNodeSet = flowGraph.getParamFlowNodeSet();
 693         Set<NTuple<Descriptor>> descTupleSetHigherThanPC = new HashSet<NTuple<Descriptor>>();
 694         for (Iterator iterator3 = curMethodParamNodeSet.iterator(); iterator3.hasNext();) {
 695           FlowNode paramNode = (FlowNode) iterator3.next();
 696           if (flowGraph.getReachableSetFrom(paramNode.getCurrentDescTuple().subList(0, 1))
 697               .contains(returnFlowNode)) {
 698             descTupleSetHigherThanPC.add(paramNode.getCurrentDescTuple());
 699           }
 700         }
 701
 702         mapHighestOverriddenMethodDescToReturnLocTuple.put(highestMethodDesc, returnLocTuple);
 703         mapHighestOverriddenMethodDescToSetHigherThanRETURNLoc.put(highestMethodDesc,
 704             descTupleSetHigherThanPC);
 705
 706       }
 707
 708       // System.out.println("####################################");
 709       // System.out.println("  highest=" + highestMethodDesc + "  LOWEST RETURNLOC="
 710       // + mapHighestOverriddenMethodDescToReturnLocTuple.get(highestMethodDesc));
 711       // System.out.println("  setHigherThanReturnLoc="
 712       // + mapHighestOverriddenMethodDescToSetHigherThanRETURNLoc.get(highestMethodDesc));
 713
 714     }
 715
 716   }
 717
 718   private void addMapHighestMethodDescToMethodDesc(MethodDescriptor highest, MethodDescriptor md) {
 719     if (!mapHighestOverriddenMethodDescToMethodDescSet.containsKey(highest)) {
 720       mapHighestOverriddenMethodDescToMethodDescSet.put(highest, new HashSet<MethodDescriptor>());
 721     }
 722     mapHighestOverriddenMethodDescToMethodDescSet.get(highest).add(md);
 723   }
 724
 725   private void DFSInheritanceTreeCalculatingHighestOverriddenMethod(ClassDescriptor cd) {
 726
 727     // ClassDescriptor cd = node.getData();
 728
 729     for (Iterator iterator = cd.getMethods(); iterator.hasNext();) {
 730       MethodDescriptor md = (MethodDescriptor) iterator.next();
 731       MethodDescriptor highestMethodDesc = getHighestOverriddenMethod(md.getClassDesc(), md);
 732       mapMethodDescToHighestOverriddenMethodDesc.put(md, highestMethodDesc);
 733       addMapHighestMethodDescToMethodDesc(highestMethodDesc, md);
 734
 735     }
 736
 737     // traverse children
 738     Set<ClassDescriptor> children = getDirectSubClasses(cd);
 739     for (Iterator iterator = children.iterator(); iterator.hasNext();) {
 740       ClassDescriptor child = (ClassDescriptor) iterator.next();
 741       DFSInheritanceTreeCalculatingHighestOverriddenMethod(child);
 742     }
 743
 744   }
 745
 746   private MethodDescriptor getHighestOverriddenMethod(ClassDescriptor curClassDesc,
 747       MethodDescriptor curMethodDesc) {
 748
 749     // Node<ClassDescriptor> curNode = inheritanceTree.getTreeNode(curClassDesc);
 750     // Node<ClassDescriptor> parentNode = curNode.getParent();
 751     ClassDescriptor parentClassDesc = curClassDesc.getSuperDesc();
 752
 753     if (parentClassDesc != null) {
 754       if (parentClassDesc.getMethodTable().contains(curMethodDesc.getSymbol())) {
 755         Set<MethodDescriptor> methodDescSet =
 756             parentClassDesc.getMethodTable().getSet(curMethodDesc.getSymbol());
 757         for (Iterator iterator = methodDescSet.iterator(); iterator.hasNext();) {
 758           MethodDescriptor md = (MethodDescriptor) iterator.next();
 759           if (md.matches(curMethodDesc)) {
 760             return getHighestOverriddenMethod(parentClassDesc, md);
 761           }
 762         }
 763       }
 764       // traverse to the parent!
 765       return getHighestOverriddenMethod(parentClassDesc, curMethodDesc);
 766     }
 767     return curMethodDesc;
 768   }
 769
 770   private void buildInheritanceTree() {
 771
 772     DFSInheritanceTreeCalculatingHighestOverriddenMethod(rootClassDescriptor);
 773
 774   }
 775
 776   private void addInheritanceConstraintsToHierarchyGraph() {
 777
 778     // DFS the inheritance tree and propagates nodes/edges of parent to child
 779
 780     // Node<ClassDescriptor> rootNode = inheritanceTree.getRootNode();
 781     DFSInheritanceTree(rootClassDescriptor);
 782
 783   }
 784
 785   private void DFSInheritanceTree(ClassDescriptor parentClassDescriptor) {
 786
 787     // ClassDescriptor parentClassDescriptor = parentNode.getData();
 788
 789     Set<ClassDescriptor> children = getDirectSubClasses(parentClassDescriptor);
 790     for (Iterator iterator = children.iterator(); iterator.hasNext();) {
 791       ClassDescriptor childClassDescriptor = (ClassDescriptor) iterator.next();
 792
 793       HierarchyGraph parentGraph = getHierarchyGraph(parentClassDescriptor);
 794       HierarchyGraph childGraph = getHierarchyGraph(childClassDescriptor);
 795
 796       Set<HNode> parentNodeSet = parentGraph.getNodeSet();
 797       for (Iterator iterator2 = parentNodeSet.iterator(); iterator2.hasNext();) {
 798         HNode hNode = (HNode) iterator2.next();
 799         childGraph.addNode(hNode);
 800       }
 801
 802       // copies extra information from the parent hierarchy graph
 803       Map<HNode, Set<HNode>> parentMergeNodeMap = parentGraph.getMapHNodetoMergeSet();
 804       Map<HNode, Set<HNode>> childMergeNodeMap = childGraph.getMapHNodetoMergeSet();
 805
 806       Set<HNode> keySet = parentMergeNodeMap.keySet();
 807       for (Iterator iterator2 = keySet.iterator(); iterator2.hasNext();) {
 808         HNode parentKey = (HNode) iterator2.next();
 809         if (!childMergeNodeMap.containsKey(parentKey)) {
 810           childMergeNodeMap.put(parentKey, new HashSet<HNode>());
 811         }
 812         childMergeNodeMap.get(parentKey).addAll(parentMergeNodeMap.get(parentKey));
 813       }
 814
 815       // copies nodes/edges from the parent class...
 816       for (Iterator iterator2 = parentNodeSet.iterator(); iterator2.hasNext();) {
 817         HNode parentHNode = (HNode) iterator2.next();
 818
 819         Set<HNode> parentIncomingHNode = parentGraph.getIncomingNodeSet(parentHNode);
 820         Set<HNode> parentOutgoingHNode = parentGraph.getOutgoingNodeSet(parentHNode);
 821
 822         for (Iterator iterator3 = parentIncomingHNode.iterator(); iterator3.hasNext();) {
 823           HNode inHNode = (HNode) iterator3.next();
 824           childGraph.addEdge(inHNode.getDescriptor(), parentHNode.getDescriptor());
 825         }
 826
 827         for (Iterator iterator3 = parentOutgoingHNode.iterator(); iterator3.hasNext();) {
 828           HNode outHNode = (HNode) iterator3.next();
 829           childGraph.addEdge(parentHNode.getDescriptor(), outHNode.getDescriptor());
 830         }
 831
 832       }
 833
 834       // copies nodes/edges from parent methods to overridden methods
 835
 836       for (Iterator iterator3 = childClassDescriptor.getMethods(); iterator3.hasNext();) {
 837         MethodDescriptor childMethodDescriptor = (MethodDescriptor) iterator3.next();
 838
 839         MethodDescriptor parentMethodDesc =
 840             getParentMethodDesc(childMethodDescriptor.getClassDesc(), childMethodDescriptor);
 841
 842         if (parentMethodDesc != null) {
 843
 844           HierarchyGraph parentMethodGraph = getHierarchyGraph(parentMethodDesc);
 845           HierarchyGraph childMethodGraph = getHierarchyGraph(childMethodDescriptor);
 846
 847           Set<HNode> parentMethodNodeSet = parentMethodGraph.getNodeSet();
 848           for (Iterator iterator2 = parentMethodNodeSet.iterator(); iterator2.hasNext();) {
 849             HNode hNode = (HNode) iterator2.next();
 850             childMethodGraph.addNode(hNode);
 851           }
 852
 853           // copies extra information from the parent hierarchy graph
 854           Map<HNode, Set<HNode>> parentMethodMergeNodeMap =
 855               parentMethodGraph.getMapHNodetoMergeSet();
 856           Map<HNode, Set<HNode>> childMethodMergeNodeMap = childMethodGraph.getMapHNodetoMergeSet();
 857
 858           Set<HNode> methodKeySet = parentMethodMergeNodeMap.keySet();
 859           for (Iterator iterator2 = methodKeySet.iterator(); iterator2.hasNext();) {
 860             HNode parentKey = (HNode) iterator2.next();
 861             if (!childMethodMergeNodeMap.containsKey(parentKey)) {
 862               childMethodMergeNodeMap.put(parentKey, new HashSet<HNode>());
 863             }
 864             childMethodMergeNodeMap.get(parentKey).addAll(parentMethodMergeNodeMap.get(parentKey));
 865           }
 866
 867           // copies nodes/edges from the parent method...
 868           for (Iterator iterator2 = parentMethodGraph.getNodeSet().iterator(); iterator2.hasNext();) {
 869             HNode parentHNode = (HNode) iterator2.next();
 870
 871             Set<HNode> parentIncomingHNode = parentMethodGraph.getIncomingNodeSet(parentHNode);
 872             Set<HNode> parentOutgoingHNode = parentMethodGraph.getOutgoingNodeSet(parentHNode);
 873
 874             for (Iterator iterator4 = parentIncomingHNode.iterator(); iterator4.hasNext();) {
 875               HNode inHNode = (HNode) iterator4.next();
 876               childMethodGraph.addEdge(inHNode, parentHNode);
 877             }
 878
 879             for (Iterator iterator4 = parentOutgoingHNode.iterator(); iterator4.hasNext();) {
 880               HNode outHNode = (HNode) iterator4.next();
 881               childMethodGraph.addEdge(parentHNode, outHNode);
 882             }
 883
 884           }
 885
 886         }
 887
 888       }
 889
 890       DFSInheritanceTree(childClassDescriptor);
 891     }
 892
 893   }
 894
 895   public MethodDescriptor getParentMethodDesc(ClassDescriptor classDesc, MethodDescriptor methodDesc) {
 896
 897     // Node<ClassDescriptor> childNode = inheritanceTree.getTreeNode(classDesc);
 898     ClassDescriptor parentClassDesc = classDesc.getSuperDesc();
 899     // Node<ClassDescriptor> parentNode = childNode.getParent();
 900
 901     if (parentClassDesc != null) {
 902       // ClassDescriptor parentClassDesc = parentNode.getData();
 903       if (parentClassDesc.getMethodTable().contains(methodDesc.getSymbol())) {
 904         Set<MethodDescriptor> methodDescSet =
 905             parentClassDesc.getMethodTable().getSet(methodDesc.getSymbol());
 906         for (Iterator iterator = methodDescSet.iterator(); iterator.hasNext();) {
 907           MethodDescriptor md = (MethodDescriptor) iterator.next();
 908           if (md.matches(methodDesc)) {
 909             return md;
 910           }
 911         }
 912       }
 913
 914       // traverse to the parent!
 915       getParentMethodDesc(parentClassDesc, methodDesc);
 916
 917     }
 918
 919     return null;
 920   }
 921
 922   private void checkReturnNodes() {
 923     LinkedList<MethodDescriptor> methodDescList =
 924         (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
 925
 926     while (!methodDescList.isEmpty()) {
 927       MethodDescriptor md = methodDescList.removeLast();
 928
 929       if (md.getReturnType() != null && !md.getReturnType().isVoid()) {
 930         checkFlowNodeReturnThisField(md);
 931       }
 932       // // in this case, this method will return the composite location that starts with 'this'
 933       // FlowGraph flowGraph = getFlowGraph(md);
 934       // Set<FlowNode> returnNodeSet = flowGraph.getReturnNodeSet();
 935       // }
 936
 937     }
 938
 939   }
 940
 941   private void addSuperClasses(ClassDescriptor cd) {
 942     ClassDescriptor parentClassDesc = cd.getSuperDesc();
 943     if (parentClassDesc != null) {
 944       toanalyze_classDescSet.add(parentClassDesc);
 945       addSuperClasses(parentClassDesc);
 946     }
 947   }
 948
 949   private void updateFlowGraph() {
 950
 951     LinkedList<MethodDescriptor> methodDescList =
 952         (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
 953
 954     while (!methodDescList.isEmpty()) {
 955       MethodDescriptor md = methodDescList.removeLast();
 956       if (state.SSJAVADEBUG) {
 957         System.out.println();
 958         System.out.println("SSJAVA: Updating a flow graph: " + md);
 959         propagateFlowsFromCalleesWithNoCompositeLocation(md);
 960       }
 961
 962       Set<FlowNode> nodeSet = getFlowGraph(md).getNodeSet();
 963       for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 964         FlowNode flowNode = (FlowNode) iterator.next();
 965         NTuple<Descriptor> descTuple = flowNode.getCurrentDescTuple();
 966         NTuple<Location> locTuple = translateToLocTuple(md, descTuple);
 967         for (int i = 0; i < locTuple.size(); i++) {
 968           Location loc = locTuple.get(i);
 969           if (loc.getDescriptor() instanceof ClassDescriptor) {
 970             ClassDescriptor classDesc = (ClassDescriptor) loc.getDescriptor();
 971             toanalyze_classDescSet.add(classDesc);
 972             addSuperClasses(classDesc);
 973           } else if (loc.getDescriptor() instanceof MethodDescriptor) {
 974             toanalyze_classDescSet.add(((MethodDescriptor) loc.getDescriptor()).getClassDesc());
 975           }
 976         }
 977
 978       }
 979
 980     }
 981   }
 982
 983   public Map<NTuple<Descriptor>, NTuple<Descriptor>> getMapCallerArgToCalleeParam(
 984       MethodInvokeNode min) {
 985
 986     if (!mapMethodInvokeNodeToMapCallerArgToCalleeArg.containsKey(min)) {
 987       mapMethodInvokeNodeToMapCallerArgToCalleeArg.put(min,
 988           new HashMap<NTuple<Descriptor>, NTuple<Descriptor>>());
 989     }
 990
 991     return mapMethodInvokeNodeToMapCallerArgToCalleeArg.get(min);
 992   }
 993
 994   public void addMapCallerArgToCalleeParam(MethodInvokeNode min, NTuple<Descriptor> callerArg,
 995       NTuple<Descriptor> calleeParam) {
 996     getMapCallerArgToCalleeParam(min).put(callerArg, calleeParam);
 997   }
 998
 999   private void assignCompositeLocation() {
1000     calculateGlobalValueFlowCompositeLocation();
1001     translateCompositeLocationAssignmentToFlowGraph();
1002   }
1003
1004   private void translateCompositeLocationAssignmentToFlowGraph() {
1005     System.out.println("\nSSJAVA: Translate composite location assignments to flow graphs:");
1006     MethodDescriptor methodEventLoopDesc = ssjava.getMethodContainingSSJavaLoop();
1007     translateCompositeLocationAssignmentToFlowGraph(methodEventLoopDesc);
1008   }
1009
1010   private void translateCompositeLocationAssignmentToFlowGraph2() {
1011     System.out.println("\nSSJAVA: Translate composite location assignments to flow graphs:");
1012     MethodDescriptor methodEventLoopDesc = ssjava.getMethodContainingSSJavaLoop();
1013     translateCompositeLocationAssignmentToFlowGraph(methodEventLoopDesc);
1014   }
1015
1016   private void addAdditionalOrderingConstraints() {
1017     System.out.println("\nSSJAVA: Add addtional ordering constriants:");
1018     MethodDescriptor methodEventLoopDesc = ssjava.getMethodContainingSSJavaLoop();
1019     addAddtionalOrderingConstraints(methodEventLoopDesc);
1020     // calculateReturnHolderLocation();
1021   }
1022
1023   private void calculateReturnHolderLocation() {
1024     LinkedList<MethodDescriptor> methodDescList =
1025         (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
1026
1027     while (!methodDescList.isEmpty()) {
1028       MethodDescriptor md = methodDescList.removeLast();
1029
1030       FlowGraph fg = getFlowGraph(md);
1031       Set<FlowNode> nodeSet = fg.getNodeSet();
1032       for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1033         FlowNode flowNode = (FlowNode) iterator.next();
1034         if (flowNode.isFromHolder()) {
1035           calculateCompositeLocationFromFlowGraph(md, flowNode);
1036         }
1037       }
1038
1039     }
1040   }
1041
1042   private void updateCompositeLocationAssignments() {
1043
1044     LinkedList<MethodDescriptor> methodDescList =
1045         (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
1046
1047     while (!methodDescList.isEmpty()) {
1048       MethodDescriptor md = methodDescList.removeLast();
1049
1050       System.out.println("\n#updateCompositeLocationAssignments=" + md);
1051
1052       FlowGraph flowGraph = getFlowGraph(md);
1053
1054       MethodSummary methodSummary = getMethodSummary(md);
1055
1056       Set<FlowNode> nodeSet = flowGraph.getNodeSet();
1057       for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1058         FlowNode node = (FlowNode) iterator.next();
1059         System.out.println("-node=" + node + "   node.getDescTuple=" + node.getDescTuple());
1060         if (node.getCompositeLocation() != null) {
1061           CompositeLocation compLoc = node.getCompositeLocation();
1062           CompositeLocation updatedCompLoc = updateCompositeLocation(compLoc);
1063           node.setCompositeLocation(updatedCompLoc);
1064           System.out.println("---updatedCompLoc1=" + updatedCompLoc);
1065         } else {
1066           NTuple<Descriptor> descTuple = node.getDescTuple();
1067           // System.out.println("update desc=" + descTuple);
1068           CompositeLocation compLoc = convertToCompositeLocation(md, descTuple);
1069           compLoc = updateCompositeLocation(compLoc);
1070           node.setCompositeLocation(compLoc);
1071           // System.out.println("---updatedCompLoc2=" + compLoc);
1072         }
1073
1074         if (node.isDeclaratonNode()) {
1075           Descriptor localVarDesc = node.getDescTuple().get(0);
1076           CompositeLocation compLoc = updateCompositeLocation(node.getCompositeLocation());
1077           methodSummary.addMapVarNameToInferCompLoc(localVarDesc, compLoc);
1078         }
1079       }
1080
1081       // update PCLOC and RETURNLOC if they have a composite location assignment
1082       if (methodSummary.getRETURNLoc() != null) {
1083         methodSummary.setRETURNLoc(updateCompositeLocation(methodSummary.getRETURNLoc()));
1084       }
1085       if (methodSummary.getPCLoc() != null) {
1086         methodSummary.setPCLoc(updateCompositeLocation(methodSummary.getPCLoc()));
1087       }
1088
1089     }
1090
1091   }
1092
1093   private CompositeLocation updateCompositeLocation(CompositeLocation compLoc) {
1094     CompositeLocation updatedCompLoc = new CompositeLocation();
1095     for (int i = 0; i < compLoc.getSize(); i++) {
1096       Location loc = compLoc.get(i);
1097       String nodeIdentifier = loc.getLocIdentifier();
1098       Descriptor enclosingDesc = loc.getDescriptor();
1099       String locName;
1100       if (!enclosingDesc.equals(GLOBALDESC)) {
1101         LocationSummary locSummary = getLocationSummary(enclosingDesc);
1102         // HierarchyGraph scGraph = getSkeletonCombinationHierarchyGraph(enclosingDesc);
1103         HierarchyGraph scGraph = getSimpleHierarchyGraph(enclosingDesc);
1104         if (scGraph != null) {
1105           HNode curNode = scGraph.getCurrentHNode(nodeIdentifier);
1106           System.out.println("     nodeID=" + nodeIdentifier + " curNode=" + curNode
1107               + "  enclosingDesc=" + enclosingDesc);
1108           if (curNode != null) {
1109             nodeIdentifier = curNode.getName();
1110           }
1111         }
1112         locName = locSummary.getLocationName(nodeIdentifier);
1113       } else {
1114         locName = nodeIdentifier;
1115       }
1116       Location updatedLoc = new Location(enclosingDesc, locName);
1117       updatedCompLoc.addLocation(updatedLoc);
1118     }
1119
1120     return updatedCompLoc;
1121   }
1122
1123   private void translateCompositeLocationAssignmentToFlowGraph(MethodDescriptor mdCaller) {
1124
1125     // System.out.println("\n\n###translateCompositeLocationAssignmentToFlowGraph mdCaller="
1126     // + mdCaller);
1127
1128     // First, assign a composite location to a node in the flow graph
1129     GlobalFlowGraph callerGlobalFlowGraph = getSubGlobalFlowGraph(mdCaller);
1130
1131     FlowGraph callerFlowGraph = getFlowGraph(mdCaller);
1132     Map<Location, CompositeLocation> callerMapLocToCompLoc =
1133         callerGlobalFlowGraph.getMapLocationToInferCompositeLocation();
1134
1135     Set<Location> methodLocSet = callerMapLocToCompLoc.keySet();
1136     for (Iterator iterator = methodLocSet.iterator(); iterator.hasNext();) {
1137       Location methodLoc = (Location) iterator.next();
1138       if (methodLoc.getDescriptor().equals(mdCaller)) {
1139         CompositeLocation inferCompLoc = callerMapLocToCompLoc.get(methodLoc);
1140         assignCompositeLocationToFlowGraph(callerFlowGraph, methodLoc, inferCompLoc);
1141       }
1142     }
1143
1144     Set<MethodInvokeNode> minSet = mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller);
1145
1146     Set<MethodDescriptor> calleeSet = new HashSet<MethodDescriptor>();
1147     for (Iterator iterator = minSet.iterator(); iterator.hasNext();) {
1148       MethodInvokeNode min = (MethodInvokeNode) iterator.next();
1149       // need to translate a composite location that is started with the base
1150       // tuple of 'min'.
1151       translateMapLocationToInferCompositeLocationToCalleeGraph(callerGlobalFlowGraph, min);
1152       MethodDescriptor mdCallee = min.getMethod();
1153       calleeSet.add(mdCallee);
1154
1155     }
1156
1157     for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) {
1158       MethodDescriptor callee = (MethodDescriptor) iterator.next();
1159       translateCompositeLocationAssignmentToFlowGraph(callee);
1160     }
1161
1162   }
1163
1164   private void addAddtionalOrderingConstraints(MethodDescriptor mdCaller) {
1165
1166     // First, assign a composite location to a node in the flow graph
1167     GlobalFlowGraph callerGlobalFlowGraph = getSubGlobalFlowGraph(mdCaller);
1168
1169     FlowGraph callerFlowGraph = getFlowGraph(mdCaller);
1170     Map<Location, CompositeLocation> callerMapLocToCompLoc =
1171         callerGlobalFlowGraph.getMapLocationToInferCompositeLocation();
1172     Set<Location> methodLocSet = callerMapLocToCompLoc.keySet();
1173
1174     Set<MethodInvokeNode> minSet = mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller);
1175
1176     Set<MethodDescriptor> calleeSet = new HashSet<MethodDescriptor>();
1177     for (Iterator iterator = minSet.iterator(); iterator.hasNext();) {
1178       MethodInvokeNode min = (MethodInvokeNode) iterator.next();
1179       MethodDescriptor mdCallee = min.getMethod();
1180       calleeSet.add(mdCallee);
1181
1182       //
1183       // add an additional ordering constraint
1184       // if the first element of a parameter composite location matches 'this' reference,
1185       // the corresponding argument in the caller is required to be higher than the translated
1186       // parameter location in the caller lattice
1187       // TODO
1188       // addOrderingConstraintFromCompLocParamToArg(mdCaller, min);
1189
1190       //
1191       // update return flow nodes in the caller
1192       CompositeLocation returnLoc = getMethodSummary(mdCallee).getRETURNLoc();
1193       // System.out.println("### min=" + min.printNode(0) + "  returnLoc=" + returnLoc);
1194       if (returnLoc != null && returnLoc.get(0).getLocDescriptor().equals(mdCallee.getThis())
1195           && returnLoc.getSize() > 1) {
1196         // System.out.println("###RETURN COMP LOC=" + returnLoc);
1197         NTuple<Location> returnLocTuple = returnLoc.getTuple();
1198         NTuple<Descriptor> baseTuple = mapMethodInvokeNodeToBaseTuple.get(min);
1199         // System.out.println("###basetuple=" + baseTuple);
1200         NTuple<Descriptor> newReturnTuple = baseTuple.clone();
1201         for (int i = 1; i < returnLocTuple.size(); i++) {
1202           newReturnTuple.add(returnLocTuple.get(i).getLocDescriptor());
1203         }
1204         // System.out.println("###NEW RETURN TUPLE FOR CALLER=" + newReturnTuple);
1205
1206         FlowReturnNode holderNode = callerFlowGraph.getFlowReturnNode(min);
1207         NodeTupleSet holderTupleSet =
1208             getNodeTupleSetFromReturnNode(getFlowGraph(mdCaller), holderNode);
1209
1210         callerFlowGraph.getFlowReturnNode(min).setNewTuple(newReturnTuple);
1211
1212         // then need to remove old constraints
1213         // TODO SAT
1214         // System.out.println("###REMOVE OLD CONSTRAINTS=" + holderNode);
1215         for (Iterator<NTuple<Descriptor>> iter = holderTupleSet.iterator(); iter.hasNext();) {
1216           NTuple<Descriptor> tupleFromHolder = iter.next();
1217           Set<FlowEdge> holderOutEdge = callerFlowGraph.getOutEdgeSet(holderNode);
1218           for (Iterator iterator2 = holderOutEdge.iterator(); iterator2.hasNext();) {
1219             FlowEdge outEdge = (FlowEdge) iterator2.next();
1220             NTuple<Descriptor> toberemovedTuple = outEdge.getEndTuple();
1221             // System.out.println("---remove " + tupleFromHolder + " -> " + toberemovedTuple);
1222             callerFlowGraph.removeEdge(tupleFromHolder, toberemovedTuple);
1223           }
1224         }
1225
1226       } else {
1227         // if the return loc set was empty and later pcloc was connected to the return loc
1228         // need to make sure that return loc reflects to this changes.
1229         FlowReturnNode flowReturnNode = callerFlowGraph.getFlowReturnNode(min);
1230         if (flowReturnNode != null && flowReturnNode.getReturnTupleSet().isEmpty()) {
1231
1232           if (needToUpdateReturnLocHolder(min.getMethod(), flowReturnNode)) {
1233             NTuple<Descriptor> baseTuple = mapMethodInvokeNodeToBaseTuple.get(min);
1234             NTuple<Descriptor> newReturnTuple = baseTuple.clone();
1235             flowReturnNode.addTuple(newReturnTuple);
1236           }
1237
1238         }
1239
1240       }
1241
1242     }
1243
1244     for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) {
1245       MethodDescriptor callee = (MethodDescriptor) iterator.next();
1246       addAddtionalOrderingConstraints(callee);
1247     }
1248
1249   }
1250
1251   private boolean needToUpdateReturnLocHolder(MethodDescriptor mdCallee,
1252       FlowReturnNode flowReturnNode) {
1253     FlowGraph fg = getFlowGraph(mdCallee);
1254     MethodSummary summary = getMethodSummary(mdCallee);
1255     CompositeLocation returnCompLoc = summary.getRETURNLoc();
1256     NTuple<Descriptor> returnDescTuple = translateToDescTuple(returnCompLoc.getTuple());
1257     Set<FlowNode> incomingNodeToReturnNode =
1258         fg.getIncomingFlowNodeSet(fg.getFlowNode(returnDescTuple));
1259     for (Iterator iterator = incomingNodeToReturnNode.iterator(); iterator.hasNext();) {
1260       FlowNode inNode = (FlowNode) iterator.next();
1261       if (inNode.getDescTuple().get(0).equals(mdCallee.getThis())) {
1262         return true;
1263       }
1264     }
1265     return false;
1266   }
1267
1268   private void addMapMethodDescToMethodInvokeNodeSet(MethodInvokeNode min) {
1269     MethodDescriptor md = min.getMethod();
1270     if (!mapMethodDescToMethodInvokeNodeSet.containsKey(md)) {
1271       mapMethodDescToMethodInvokeNodeSet.put(md, new HashSet<MethodInvokeNode>());
1272     }
1273     mapMethodDescToMethodInvokeNodeSet.get(md).add(min);
1274   }
1275
1276   private Set<MethodInvokeNode> getMethodInvokeNodeSetByMethodDesc(MethodDescriptor md) {
1277     if (!mapMethodDescToMethodInvokeNodeSet.containsKey(md)) {
1278       mapMethodDescToMethodInvokeNodeSet.put(md, new HashSet<MethodInvokeNode>());
1279     }
1280     return mapMethodDescToMethodInvokeNodeSet.get(md);
1281   }
1282
1283   public void assignCompositeLocationToFlowGraph(FlowGraph flowGraph, Location loc,
1284       CompositeLocation inferCompLoc) {
1285     Descriptor localDesc = loc.getLocDescriptor();
1286
1287     Set<FlowNode> nodeSet = flowGraph.getNodeSet();
1288     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1289       FlowNode node = (FlowNode) iterator.next();
1290       if (node.getDescTuple().startsWith(localDesc)
1291           && !node.getDescTuple().get(0).equals(LITERALDESC)) {
1292         // need to assign the inferred composite location to this node
1293         CompositeLocation newCompLoc = generateCompositeLocation(node.getDescTuple(), inferCompLoc);
1294         node.setCompositeLocation(newCompLoc);
1295         // System.out.println("SET Node=" + node + "  inferCompLoc=" + newCompLoc);
1296       }
1297     }
1298   }
1299
1300   private CompositeLocation generateCompositeLocation(NTuple<Descriptor> nodeDescTuple,
1301       CompositeLocation inferCompLoc) {
1302
1303     // System.out.println("generateCompositeLocation=" + nodeDescTuple + " with inferCompLoc="
1304     // + inferCompLoc);
1305
1306     MethodDescriptor md = (MethodDescriptor) inferCompLoc.get(0).getDescriptor();
1307
1308     CompositeLocation newCompLoc = new CompositeLocation();
1309     for (int i = 0; i < inferCompLoc.getSize(); i++) {
1310       newCompLoc.addLocation(inferCompLoc.get(i));
1311     }
1312
1313     Descriptor lastDescOfPrefix = nodeDescTuple.get(0);
1314     Descriptor enclosingDescriptor;
1315     if (lastDescOfPrefix instanceof InterDescriptor) {
1316       enclosingDescriptor = getFlowGraph(md).getEnclosingDescriptor(lastDescOfPrefix);
1317     } else {
1318       enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc();
1319     }
1320
1321     for (int i = 1; i < nodeDescTuple.size(); i++) {
1322       Descriptor desc = nodeDescTuple.get(i);
1323       Location locElement = new Location(enclosingDescriptor, desc);
1324       newCompLoc.addLocation(locElement);
1325
1326       enclosingDescriptor = ((FieldDescriptor) desc).getClassDescriptor();
1327     }
1328
1329     return newCompLoc;
1330   }
1331
1332   private void translateMapLocationToInferCompositeLocationToCalleeGraph(
1333       GlobalFlowGraph callerGraph, MethodInvokeNode min) {
1334
1335     MethodDescriptor mdCallee = min.getMethod();
1336     MethodDescriptor mdCaller = callerGraph.getMethodDescriptor();
1337     Map<Location, CompositeLocation> callerMapLocToCompLoc =
1338         callerGraph.getMapLocationToInferCompositeLocation();
1339
1340     Map<Integer, NTuple<Descriptor>> mapIdxToArgTuple = mapMethodInvokeNodeToArgIdxMap.get(min);
1341
1342     FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
1343     GlobalFlowGraph calleeGlobalGraph = getSubGlobalFlowGraph(mdCallee);
1344
1345     NTuple<Location> baseLocTuple = null;
1346     if (mapMethodInvokeNodeToBaseTuple.containsKey(min)) {
1347       baseLocTuple = translateToLocTuple(mdCaller, mapMethodInvokeNodeToBaseTuple.get(min));
1348     }
1349
1350     // System.out.println("\n-#translate caller=" + mdCaller + " infer composite loc to callee="
1351     // + mdCallee + " baseLocTuple=" + baseLocTuple);
1352
1353     Set<Location> keySet = callerMapLocToCompLoc.keySet();
1354     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1355       Location key = (Location) iterator.next();
1356       CompositeLocation callerCompLoc = callerMapLocToCompLoc.get(key);
1357
1358       if (!key.getDescriptor().equals(mdCaller)) {
1359
1360         CompositeLocation newCalleeCompLoc;
1361         if (baseLocTuple != null && callerCompLoc.getTuple().startsWith(baseLocTuple)) {
1362           // System.out.println("-----need to translate callerCompLoc=" + callerCompLoc
1363           // + " with baseTuple=" + baseLocTuple);
1364           newCalleeCompLoc =
1365               translateCompositeLocationToCallee(callerCompLoc, baseLocTuple, mdCallee);
1366
1367           calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, newCalleeCompLoc);
1368           // System.out.println("1---key=" + key + "  callerCompLoc=" + callerCompLoc
1369           // + "  newCalleeCompLoc=" + newCalleeCompLoc);
1370           // System.out.println("-----caller=" + mdCaller + "    callee=" + mdCallee);
1371           if (!newCalleeCompLoc.get(0).getDescriptor().equals(mdCallee)) {
1372             System.exit(0);
1373           }
1374
1375           // System.out.println("-----baseLoctuple=" + baseLocTuple);
1376         } else {
1377           // check if it is the global access
1378           Location compLocFirstElement = callerCompLoc.getTuple().get(0);
1379           if (compLocFirstElement.getDescriptor().equals(mdCallee)
1380               && compLocFirstElement.getLocDescriptor().equals(GLOBALDESC)) {
1381
1382             newCalleeCompLoc = new CompositeLocation();
1383             Location newMethodLoc = new Location(mdCallee, GLOBALDESC);
1384
1385             newCalleeCompLoc.addLocation(newMethodLoc);
1386             for (int i = 1; i < callerCompLoc.getSize(); i++) {
1387               newCalleeCompLoc.addLocation(callerCompLoc.get(i));
1388             }
1389             calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, newCalleeCompLoc);
1390             // System.out.println("2---key=" + key + "  callerCompLoc=" + callerCompLoc
1391             // + "  newCalleeCompLoc=" + newCalleeCompLoc);
1392             // System.out.println("-----caller=" + mdCaller + "    callee=" + mdCallee);
1393
1394           } else {
1395             int paramIdx = getParamIdx(callerCompLoc, mapIdxToArgTuple);
1396             if (paramIdx == -1) {
1397               // here, the first element of the current composite location comes from the current
1398               // callee
1399               // so transfer the same composite location to the callee
1400               if (!calleeGlobalGraph.contrainsInferCompositeLocationMapKey(key)) {
1401                 if (callerCompLoc.get(0).getDescriptor().equals(mdCallee)) {
1402                   // System.out.println("3---key=" + key + "  callerCompLoc=" + callerCompLoc
1403                   // + "  newCalleeCompLoc=" + callerCompLoc);
1404                   // System.out.println("-----caller=" + mdCaller + "    callee=" + mdCallee);
1405                   calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, callerCompLoc);
1406                 } else {
1407                   // System.out.println("3---SKIP key=" + key + " callerCompLoc=" + callerCompLoc);
1408                 }
1409               }
1410               continue;
1411             }
1412
1413             // It is the case where two parameters have relative orderings between them by having
1414             // composite locations
1415             // if we found the param idx, it means that the first part of the caller composite
1416             // location corresponds to the one of arguments.
1417             // for example, if the caller argument is <<caller.this>,<Decoder.br>>
1418             // and the current caller composite location mapping
1419             // <<caller.this>,<Decoder.br>,<Br.value>>
1420             // and the parameter which matches with the caller argument is 'Br brParam'
1421             // then, the translated callee composite location will be <<callee.brParam>,<Br.value>>
1422             NTuple<Descriptor> argTuple = mapIdxToArgTuple.get(paramIdx);
1423
1424             FlowNode paramFlowNode = calleeFlowGraph.getParamFlowNode(paramIdx);
1425             NTuple<Location> paramLocTuple =
1426                 translateToLocTuple(mdCallee, paramFlowNode.getDescTuple());
1427             newCalleeCompLoc = new CompositeLocation();
1428             for (int i = 0; i < paramLocTuple.size(); i++) {
1429               newCalleeCompLoc.addLocation(paramLocTuple.get(i));
1430             }
1431             for (int i = argTuple.size(); i < callerCompLoc.getSize(); i++) {
1432               newCalleeCompLoc.addLocation(callerCompLoc.get(i));
1433             }
1434             calleeGlobalGraph.addMapLocationToInferCompositeLocation(key, newCalleeCompLoc);
1435             // System.out.println("4---key=" + key + "  callerCompLoc=" + callerCompLoc
1436             // + "  newCalleeCompLoc=" + newCalleeCompLoc);
1437             // System.out.println("-----caller=" + mdCaller + "    callee=" + mdCallee);
1438
1439           }
1440
1441         }
1442
1443       }
1444     }
1445
1446     // System.out.println("#ASSIGN COMP LOC TO CALLEE PARAMS: callee=" + mdCallee + "  caller="
1447     // + mdCaller);
1448     // If the location of an argument has a composite location
1449     // need to assign a proper composite location to the corresponding callee parameter
1450     Set<Integer> idxSet = mapIdxToArgTuple.keySet();
1451     for (Iterator iterator = idxSet.iterator(); iterator.hasNext();) {
1452       Integer idx = (Integer) iterator.next();
1453
1454       if (idx == 0 && !min.getMethod().isStatic()) {
1455         continue;
1456       }
1457
1458       NTuple<Descriptor> argTuple = mapIdxToArgTuple.get(idx);
1459       // System.out.println("-argTuple=" + argTuple + "   idx=" + idx);
1460       if (argTuple.size() > 0) {
1461         // check if an arg tuple has been already assigned to a composite location
1462         NTuple<Location> argLocTuple = translateToLocTuple(mdCaller, argTuple);
1463         Location argLocalLoc = argLocTuple.get(0);
1464
1465         // if (!isPrimitiveType(argTuple)) {
1466         if (callerMapLocToCompLoc.containsKey(argLocalLoc)) {
1467
1468           CompositeLocation callerCompLoc = callerMapLocToCompLoc.get(argLocalLoc);
1469           for (int i = 1; i < argLocTuple.size(); i++) {
1470             callerCompLoc.addLocation(argLocTuple.get(i));
1471           }
1472
1473           // System.out.println("---callerCompLoc=" + callerCompLoc);
1474
1475           // if (baseLocTuple != null && callerCompLoc.getTuple().startsWith(baseLocTuple)) {
1476
1477           FlowNode calleeParamFlowNode = calleeFlowGraph.getParamFlowNode(idx);
1478
1479           NTuple<Descriptor> calleeParamDescTuple = calleeParamFlowNode.getDescTuple();
1480           NTuple<Location> calleeParamLocTuple =
1481               translateToLocTuple(mdCallee, calleeParamDescTuple);
1482
1483           int refParamIdx = getParamIdx(callerCompLoc, mapIdxToArgTuple);
1484           // System.out.println("-----paramIdx=" + refParamIdx);
1485           if (refParamIdx == 0 && !mdCallee.isStatic()) {
1486
1487             // System.out.println("-------need to translate callerCompLoc=" + callerCompLoc
1488             // + " with baseTuple=" + baseLocTuple + "   calleeParamLocTuple="
1489             // + calleeParamLocTuple);
1490
1491             CompositeLocation newCalleeCompLoc =
1492                 translateCompositeLocationToCallee(callerCompLoc, baseLocTuple, mdCallee);
1493
1494             calleeGlobalGraph.addMapLocationToInferCompositeLocation(calleeParamLocTuple.get(0),
1495                 newCalleeCompLoc);
1496
1497             // System.out.println("---------key=" + calleeParamLocTuple.get(0) + "  callerCompLoc="
1498             // + callerCompLoc + "  newCalleeCompLoc=" + newCalleeCompLoc);
1499
1500           } else if (refParamIdx != -1) {
1501             // the first element of an argument composite location matches with one of paramtere
1502             // composite locations
1503
1504             // System.out.println("-------param match case=");
1505
1506             NTuple<Descriptor> argTupleRef = mapIdxToArgTuple.get(refParamIdx);
1507             FlowNode refParamFlowNode = calleeFlowGraph.getParamFlowNode(refParamIdx);
1508             NTuple<Location> refParamLocTuple =
1509                 translateToLocTuple(mdCallee, refParamFlowNode.getDescTuple());
1510
1511             // System.out.println("---------refParamLocTuple=" + refParamLocTuple
1512             // + "  from argTupleRef=" + argTupleRef);
1513
1514             CompositeLocation newCalleeCompLoc = new CompositeLocation();
1515             for (int i = 0; i < refParamLocTuple.size(); i++) {
1516               newCalleeCompLoc.addLocation(refParamLocTuple.get(i));
1517             }
1518             for (int i = argTupleRef.size(); i < callerCompLoc.getSize(); i++) {
1519               newCalleeCompLoc.addLocation(callerCompLoc.get(i));
1520             }
1521
1522             calleeGlobalGraph.addMapLocationToInferCompositeLocation(calleeParamLocTuple.get(0),
1523                 newCalleeCompLoc);
1524
1525             calleeParamFlowNode.setCompositeLocation(newCalleeCompLoc);
1526             // System.out.println("-----------key=" + calleeParamLocTuple.get(0) +
1527             // "  callerCompLoc="
1528             // + callerCompLoc + "  newCalleeCompLoc=" + newCalleeCompLoc);
1529
1530           } else {
1531             CompositeLocation newCalleeCompLoc =
1532                 calculateCompositeLocationFromSubGlobalGraph(mdCallee, calleeParamFlowNode);
1533             if (newCalleeCompLoc != null) {
1534               calleeGlobalGraph.addMapLocationToInferCompositeLocation(calleeParamLocTuple.get(0),
1535                   newCalleeCompLoc);
1536               calleeParamFlowNode.setCompositeLocation(newCalleeCompLoc);
1537             }
1538           }
1539
1540           // System.out.println("-----------------calleeParamFlowNode="
1541           // + calleeParamFlowNode.getCompositeLocation());
1542
1543           // }
1544
1545         }
1546       }
1547
1548     }
1549
1550   }
1551
1552   private CompositeLocation calculateCompositeLocationFromSubGlobalGraph(MethodDescriptor md,
1553       FlowNode paramNode) {
1554
1555     // System.out.println("#############################################################");
1556     // System.out.println("calculateCompositeLocationFromSubGlobalGraph=" + paramNode);
1557
1558     GlobalFlowGraph subGlobalFlowGraph = getSubGlobalFlowGraph(md);
1559     NTuple<Location> paramLocTuple = translateToLocTuple(md, paramNode.getDescTuple());
1560     GlobalFlowNode paramGlobalNode = subGlobalFlowGraph.getFlowNode(paramLocTuple);
1561
1562     List<NTuple<Location>> prefixList = calculatePrefixList(subGlobalFlowGraph, paramGlobalNode);
1563
1564     Location prefixLoc = paramLocTuple.get(0);
1565
1566     Set<GlobalFlowNode> reachableNodeSet =
1567         subGlobalFlowGraph.getReachableNodeSetByPrefix(paramGlobalNode.getLocTuple().get(0));
1568     // Set<GlobalFlowNode> reachNodeSet = globalFlowGraph.getReachableNodeSetFrom(node);
1569
1570     // System.out.println("node=" + node + "    prefixList=" + prefixList);
1571
1572     for (int i = 0; i < prefixList.size(); i++) {
1573       NTuple<Location> curPrefix = prefixList.get(i);
1574       Set<NTuple<Location>> reachableCommonPrefixSet = new HashSet<NTuple<Location>>();
1575
1576       for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
1577         GlobalFlowNode reachNode = (GlobalFlowNode) iterator2.next();
1578         if (reachNode.getLocTuple().startsWith(curPrefix)) {
1579           reachableCommonPrefixSet.add(reachNode.getLocTuple());
1580         }
1581       }
1582       // System.out.println("reachableCommonPrefixSet=" + reachableCommonPrefixSet);
1583
1584       if (!reachableCommonPrefixSet.isEmpty()) {
1585
1586         MethodDescriptor curPrefixFirstElementMethodDesc =
1587             (MethodDescriptor) curPrefix.get(0).getDescriptor();
1588
1589         MethodDescriptor nodePrefixLocFirstElementMethodDesc =
1590             (MethodDescriptor) prefixLoc.getDescriptor();
1591
1592         // System.out.println("curPrefixFirstElementMethodDesc=" +
1593         // curPrefixFirstElementMethodDesc);
1594         // System.out.println("nodePrefixLocFirstElementMethodDesc="
1595         // + nodePrefixLocFirstElementMethodDesc);
1596
1597         if (curPrefixFirstElementMethodDesc.equals(nodePrefixLocFirstElementMethodDesc)
1598             || isTransitivelyCalledFrom(nodePrefixLocFirstElementMethodDesc,
1599                 curPrefixFirstElementMethodDesc)) {
1600
1601           // TODO
1602           // if (!node.getLocTuple().startsWith(curPrefix.get(0))) {
1603
1604           Location curPrefixLocalLoc = curPrefix.get(0);
1605           if (subGlobalFlowGraph.mapLocationToInferCompositeLocation.containsKey(curPrefixLocalLoc)) {
1606             // in this case, the local variable of the current prefix has already got a composite
1607             // location
1608             // so we just ignore the current composite location.
1609
1610             // System.out.println("HERE WE DO NOT ASSIGN A COMPOSITE LOCATION TO =" + node
1611             // + " DUE TO " + curPrefix);
1612             return null;
1613           }
1614
1615           if (!needToGenerateCompositeLocation(paramGlobalNode, curPrefix)) {
1616             // System.out.println("NO NEED TO GENERATE COMP LOC to " + paramGlobalNode
1617             // + " with prefix=" + curPrefix);
1618             return null;
1619           }
1620
1621           Location targetLocalLoc = paramGlobalNode.getLocTuple().get(0);
1622           CompositeLocation newCompLoc = generateCompositeLocation(curPrefix);
1623           // System.out.println("NEED TO ASSIGN COMP LOC TO " + paramGlobalNode + " with prefix="
1624           // + curPrefix);
1625           // System.out.println("-targetLocalLoc=" + targetLocalLoc + "   - newCompLoc=" +
1626           // newCompLoc);
1627
1628           // makes sure that a newly generated location appears in the hierarchy graph
1629           for (int compIdx = 0; compIdx < newCompLoc.getSize(); compIdx++) {
1630             Location curLoc = newCompLoc.get(compIdx);
1631             getHierarchyGraph(curLoc.getDescriptor()).getHNode(curLoc.getLocDescriptor());
1632           }
1633
1634           subGlobalFlowGraph.addMapLocationToInferCompositeLocation(targetLocalLoc, newCompLoc);
1635
1636           return newCompLoc;
1637
1638         }
1639
1640       }
1641
1642     }
1643     return null;
1644   }
1645
1646   private int getParamIdx(CompositeLocation compLoc,
1647       Map<Integer, NTuple<Descriptor>> mapIdxToArgTuple) {
1648
1649     // if the composite location is started with the argument descriptor
1650     // return the argument's index. o.t. return -1
1651
1652     Set<Integer> keySet = mapIdxToArgTuple.keySet();
1653     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1654       Integer key = (Integer) iterator.next();
1655       NTuple<Descriptor> argTuple = mapIdxToArgTuple.get(key);
1656       if (argTuple.size() > 0 && translateToDescTuple(compLoc.getTuple()).startsWith(argTuple)) {
1657         // System.out.println("compLoc.getTuple=" + compLoc + " is started with " + argTuple);
1658         return key.intValue();
1659       }
1660     }
1661
1662     return -1;
1663   }
1664
1665   private boolean isPrimitiveType(NTuple<Descriptor> argTuple) {
1666
1667     Descriptor lastDesc = argTuple.get(argTuple.size() - 1);
1668
1669     if (lastDesc instanceof FieldDescriptor) {
1670       return ((FieldDescriptor) lastDesc).getType().isPrimitive();
1671     } else if (lastDesc instanceof VarDescriptor) {
1672       return ((VarDescriptor) lastDesc).getType().isPrimitive();
1673     } else if (lastDesc instanceof InterDescriptor) {
1674       return true;
1675     }
1676
1677     return false;
1678   }
1679
1680   private CompositeLocation translateCompositeLocationToCallee(CompositeLocation callerCompLoc,
1681       NTuple<Location> baseLocTuple, MethodDescriptor mdCallee) {
1682
1683     CompositeLocation newCalleeCompLoc = new CompositeLocation();
1684
1685     Location calleeThisLoc = new Location(mdCallee, mdCallee.getThis());
1686     newCalleeCompLoc.addLocation(calleeThisLoc);
1687
1688     // remove the base tuple from the caller
1689     // ex; In the method invoation foo.bar.methodA(), the callee will have the composite location
1690     // ,which is relative to the 'this' variable, <THIS,...>
1691     for (int i = baseLocTuple.size(); i < callerCompLoc.getSize(); i++) {
1692       newCalleeCompLoc.addLocation(callerCompLoc.get(i));
1693     }
1694
1695     return newCalleeCompLoc;
1696
1697   }
1698
1699   private void calculateGlobalValueFlowCompositeLocation() {
1700
1701     System.out.println("SSJAVA: Calculate composite locations in the global value flow graph");
1702     MethodDescriptor methodDescEventLoop = ssjava.getMethodContainingSSJavaLoop();
1703     GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(methodDescEventLoop);
1704
1705     Set<Location> calculatedPrefixSet = new HashSet<Location>();
1706
1707     Set<GlobalFlowNode> nodeSet = globalFlowGraph.getNodeSet();
1708
1709     next: for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1710       GlobalFlowNode node = (GlobalFlowNode) iterator.next();
1711
1712       Location prefixLoc = node.getLocTuple().get(0);
1713
1714       if (calculatedPrefixSet.contains(prefixLoc)) {
1715         // the prefix loc has been already assigned to a composite location
1716         continue;
1717       }
1718
1719       calculatedPrefixSet.add(prefixLoc);
1720
1721       // Set<GlobalFlowNode> incomingNodeSet = globalFlowGraph.getIncomingNodeSet(node);
1722       List<NTuple<Location>> prefixList = calculatePrefixList(globalFlowGraph, node);
1723
1724       Set<GlobalFlowNode> reachableNodeSet =
1725           globalFlowGraph.getReachableNodeSetByPrefix(node.getLocTuple().get(0));
1726       // Set<GlobalFlowNode> reachNodeSet = globalFlowGraph.getReachableNodeSetFrom(node);
1727
1728       // System.out.println("node=" + node + "    prefixList=" + prefixList);
1729       // System.out.println("---prefixList=" + prefixList);
1730
1731       nextprefix: for (int i = 0; i < prefixList.size(); i++) {
1732         NTuple<Location> curPrefix = prefixList.get(i);
1733         // System.out.println("---curPrefix=" + curPrefix);
1734         Set<NTuple<Location>> reachableCommonPrefixSet = new HashSet<NTuple<Location>>();
1735
1736         for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
1737           GlobalFlowNode reachNode = (GlobalFlowNode) iterator2.next();
1738           if (reachNode.getLocTuple().startsWith(curPrefix)) {
1739             reachableCommonPrefixSet.add(reachNode.getLocTuple());
1740           }
1741         }
1742         // System.out.println("reachableCommonPrefixSet=" + reachableCommonPrefixSet);
1743
1744         if (!reachableCommonPrefixSet.isEmpty()) {
1745
1746           System.out.println("WARNING:: The algorithm is going to nondeterministicly inline " +
1747                         " a cylce in between following prefixes="+reachableCommonPrefixSet +
1748                         " for the current node="+node);
1749
1750           MethodDescriptor curPrefixFirstElementMethodDesc =
1751               (MethodDescriptor) curPrefix.get(0).getDescriptor();
1752
1753           MethodDescriptor nodePrefixLocFirstElementMethodDesc =
1754               (MethodDescriptor) prefixLoc.getDescriptor();
1755
1756           // System.out.println("curPrefixFirstElementMethodDesc=" +
1757           // curPrefixFirstElementMethodDesc);
1758           // System.out.println("nodePrefixLocFirstElementMethodDesc="
1759           // + nodePrefixLocFirstElementMethodDesc);
1760
1761           if (curPrefixFirstElementMethodDesc.equals(nodePrefixLocFirstElementMethodDesc)
1762               || isTransitivelyCalledFrom(nodePrefixLocFirstElementMethodDesc,
1763                   curPrefixFirstElementMethodDesc)) {
1764
1765             // TODO
1766             // if (!node.getLocTuple().startsWith(curPrefix.get(0))) {
1767
1768             Location curPrefixLocalLoc = curPrefix.get(0);
1769             if (globalFlowGraph.mapLocationToInferCompositeLocation.containsKey(curPrefixLocalLoc)) {
1770               // in this case, the local variable of the current prefix has already got a composite
1771               // location
1772               // so we just ignore the current composite location.
1773
1774               // System.out.println("HERE WE DO NOT ASSIGN A COMPOSITE LOCATION TO =" + node
1775               // + " DUE TO " + curPrefix);
1776
1777               continue next;
1778             }
1779
1780             if (!needToGenerateCompositeLocation(node, curPrefix)) {
1781               // System.out.println("NO NEED TO GENERATE COMP LOC to " + node + " with prefix="
1782               // + curPrefix);
1783               // System.out.println("prefixList=" + prefixList);
1784               // System.out.println("reachableNodeSet=" + reachableNodeSet);
1785               continue nextprefix;
1786             }
1787
1788             Location targetLocalLoc = node.getLocTuple().get(0);
1789             CompositeLocation newCompLoc = generateCompositeLocation(curPrefix);
1790             // System.out.println("NEED TO ASSIGN COMP LOC TO " + node + " with prefix=" +
1791             // curPrefix);
1792             // System.out.println("-targetLocalLoc=" + targetLocalLoc + "   - newCompLoc="
1793             // + newCompLoc);
1794             globalFlowGraph.addMapLocationToInferCompositeLocation(targetLocalLoc, newCompLoc);
1795             // }
1796
1797             // if (node.getLocTuple().get(0).getDescriptor().getSymbol().equals("get_scale_factors")
1798             // || node.getLocTuple().get(0).getDescriptor().getSymbol()
1799             // .equals("get_LSF_scale_data")){
1800             // Set<GlobalFlowNode> debugInNodeSet =
1801             // globalFlowGraph.debug_getIncomingNodeSetFromPrefix(node, curPrefix);
1802             // }
1803             continue next;
1804             // }
1805
1806           }
1807
1808         }
1809
1810       }
1811
1812     }
1813   }
1814
1815   private boolean checkFlowNodeReturnThisField(MethodDescriptor md) {
1816
1817     MethodDescriptor methodDescEventLoop = ssjava.getMethodContainingSSJavaLoop();
1818     GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(methodDescEventLoop);
1819
1820     FlowGraph flowGraph = getFlowGraph(md);
1821
1822     ClassDescriptor enclosingDesc = getClassTypeDescriptor(md.getThis());
1823     if (enclosingDesc == null) {
1824       return false;
1825     }
1826
1827     int count = 0;
1828     Set<FlowNode> returnNodeSet = flowGraph.getReturnNodeSet();
1829     Set<GlobalFlowNode> globalReturnNodeSet = new HashSet<GlobalFlowNode>();
1830     for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
1831       FlowNode flowNode = (FlowNode) iterator.next();
1832       NTuple<Location> locTuple = translateToLocTuple(md, flowNode.getDescTuple());
1833       GlobalFlowNode globalReturnNode = globalFlowGraph.getFlowNode(locTuple);
1834       globalReturnNodeSet.add(globalReturnNode);
1835
1836       List<NTuple<Location>> prefixList = calculatePrefixList(globalFlowGraph, globalReturnNode);
1837       for (int i = 0; i < prefixList.size(); i++) {
1838         NTuple<Location> curPrefix = prefixList.get(i);
1839         ClassDescriptor cd =
1840             getClassTypeDescriptor(curPrefix.get(curPrefix.size() - 1).getLocDescriptor());
1841         if (cd != null && cd.equals(enclosingDesc)) {
1842           count++;
1843           break;
1844         }
1845       }
1846
1847     }
1848
1849     if (count == returnNodeSet.size()) {
1850       // in this case, all return nodes in the method returns values coming from a location that
1851       // starts with "this"
1852
1853       // System.out.println("$$$SET RETURN LOC TRUE=" + md);
1854       mapMethodDescriptorToCompositeReturnCase.put(md, Boolean.TRUE);
1855
1856       // NameDescriptor returnLocDesc = new NameDescriptor("RLOC" + (locSeed++));
1857       // NTuple<Descriptor> rDescTuple = new NTuple<Descriptor>();
1858       // rDescTuple.add(md.getThis());
1859       // rDescTuple.add(returnLocDesc);
1860       //
1861       // for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
1862       // FlowNode rnode = (FlowNode) iterator.next();
1863       // flowGraph.addValueFlowEdge(rnode.getDescTuple(), rDescTuple);
1864       // }
1865       //
1866       // getMethodSummary(md).setRETURNLoc(new CompositeLocation(translateToLocTuple(md,
1867       // rDescTuple)));
1868
1869     } else {
1870       mapMethodDescriptorToCompositeReturnCase.put(md, Boolean.FALSE);
1871     }
1872
1873     return mapMethodDescriptorToCompositeReturnCase.get(md).booleanValue();
1874
1875   }
1876
1877   private boolean needToGenerateCompositeLocation(GlobalFlowNode node, NTuple<Location> curPrefix) {
1878     // return true if there is a path between a node to which we want to give a composite location
1879     // and nodes which start with curPrefix
1880
1881     // System.out.println("---needToGenerateCompositeLocation curPrefix=" + curPrefix);
1882
1883     Location targetLocalLoc = node.getLocTuple().get(0);
1884
1885     MethodDescriptor md = (MethodDescriptor) targetLocalLoc.getDescriptor();
1886     FlowGraph flowGraph = getFlowGraph(md);
1887
1888     FlowNode flowNode = flowGraph.getFlowNode(node.getDescTuple());
1889     Set<FlowNode> reachableSet = flowGraph.getReachFlowNodeSetFrom(flowNode);
1890
1891     Set<FlowNode> paramNodeSet = flowGraph.getParamFlowNodeSet();
1892     for (Iterator iterator = paramNodeSet.iterator(); iterator.hasNext();) {
1893       FlowNode paramFlowNode = (FlowNode) iterator.next();
1894       if (curPrefix.startsWith(translateToLocTuple(md, paramFlowNode.getDescTuple()))) {
1895         return true;
1896       }
1897     }
1898
1899     if (targetLocalLoc.getLocDescriptor() instanceof InterDescriptor) {
1900       Pair<MethodInvokeNode, Integer> pair =
1901           ((InterDescriptor) targetLocalLoc.getLocDescriptor()).getMethodArgIdxPair();
1902
1903       if (pair != null) {
1904         // System.out.println("$$$TARGETLOCALLOC HOLDER=" + targetLocalLoc);
1905
1906         MethodInvokeNode min = pair.getFirst();
1907         Integer paramIdx = pair.getSecond();
1908         MethodDescriptor mdCallee = min.getMethod();
1909
1910         FlowNode paramNode = getFlowGraph(mdCallee).getParamFlowNode(paramIdx);
1911         if (checkNodeReachToReturnNode(mdCallee, paramNode)) {
1912           return true;
1913         }
1914
1915       }
1916
1917     }
1918
1919     GlobalFlowGraph subGlobalFlowGraph = getSubGlobalFlowGraph(md);
1920     Set<GlobalFlowNode> subGlobalReachableSet = subGlobalFlowGraph.getReachableNodeSetFrom(node);
1921
1922     if (!md.isStatic()) {
1923       ClassDescriptor currentMethodThisType = getClassTypeDescriptor(md.getThis());
1924       for (int i = 0; i < curPrefix.size(); i++) {
1925         ClassDescriptor prefixType = getClassTypeDescriptor(curPrefix.get(i).getLocDescriptor());
1926         if (prefixType != null && prefixType.equals(currentMethodThisType)) {
1927           // System.out.println("PREFIX TYPE MATCHES WITH=" + currentMethodThisType);
1928
1929           if (mapMethodDescriptorToCompositeReturnCase.containsKey(md)) {
1930             boolean hasCompReturnLocWithThis =
1931                 mapMethodDescriptorToCompositeReturnCase.get(md).booleanValue();
1932             if (hasCompReturnLocWithThis) {
1933               if (checkNodeReachToReturnNode(md, flowNode)) {
1934                 return true;
1935               }
1936             }
1937           }
1938
1939           for (Iterator iterator3 = subGlobalReachableSet.iterator(); iterator3.hasNext();) {
1940             GlobalFlowNode subGlobalReachalbeNode = (GlobalFlowNode) iterator3.next();
1941             if (subGlobalReachalbeNode.getLocTuple().get(0).getLocDescriptor().equals(md.getThis())) {
1942               // System.out.println("PREFIX FOUND=" + subGlobalReachalbeNode);
1943               return true;
1944             }
1945           }
1946         }
1947       }
1948     }
1949
1950     Location lastLocationOfPrefix = curPrefix.get(curPrefix.size() - 1);
1951     // check whether prefix appears in the list of parameters
1952     Set<MethodInvokeNode> minSet = mapMethodDescToMethodInvokeNodeSet.get(md);
1953     // System.out.println("$$$md=" + md + "   minSet=" + minSet);
1954     if (minSet == null) {
1955       return false;
1956     }
1957     found: for (Iterator iterator = minSet.iterator(); iterator.hasNext();) {
1958       MethodInvokeNode min = (MethodInvokeNode) iterator.next();
1959       Map<Integer, NTuple<Descriptor>> map = mapMethodInvokeNodeToArgIdxMap.get(min);
1960       Set<Integer> keySet = map.keySet();
1961       // System.out.println("min=" + min.printNode(0));
1962
1963       for (Iterator iterator2 = keySet.iterator(); iterator2.hasNext();) {
1964         Integer argIdx = (Integer) iterator2.next();
1965         NTuple<Descriptor> argTuple = map.get(argIdx);
1966
1967         if (!(!md.isStatic() && argIdx == 0)) {
1968           // if the argTuple is empty, we don't need to do with anything(LITERAL CASE).
1969           if (argTuple.size() > 0
1970               && argTuple.get(argTuple.size() - 1).equals(lastLocationOfPrefix.getLocDescriptor())) {
1971             NTuple<Location> locTuple =
1972                 translateToLocTuple(md, flowGraph.getParamFlowNode(argIdx).getDescTuple());
1973             lastLocationOfPrefix = locTuple.get(0);
1974             // System.out.println("ARG CASE=" + locTuple);
1975             for (Iterator iterator3 = subGlobalReachableSet.iterator(); iterator3.hasNext();) {
1976               GlobalFlowNode subGlobalReachalbeNode = (GlobalFlowNode) iterator3.next();
1977               // NTuple<Location> locTuple = translateToLocTuple(md, reachalbeNode.getDescTuple());
1978               NTuple<Location> globalReachlocTuple = subGlobalReachalbeNode.getLocTuple();
1979               for (int i = 0; i < globalReachlocTuple.size(); i++) {
1980                 if (globalReachlocTuple.get(i).equals(lastLocationOfPrefix)) {
1981                   // System.out.println("ARG  " + argTuple + "  IS MATCHED WITH="
1982                   // + lastLocationOfPrefix);
1983                   return true;
1984                 }
1985               }
1986             }
1987           }
1988         }
1989       }
1990     }
1991
1992     return false;
1993   }
1994
1995   private boolean checkNodeReachToReturnNode(MethodDescriptor md, FlowNode node) {
1996
1997     FlowGraph flowGraph = getFlowGraph(md);
1998     Set<FlowNode> reachableSet = flowGraph.getReachFlowNodeSetFrom(node);
1999     if (mapMethodDescriptorToCompositeReturnCase.containsKey(md)) {
2000       boolean hasCompReturnLocWithThis =
2001           mapMethodDescriptorToCompositeReturnCase.get(md).booleanValue();
2002
2003       if (hasCompReturnLocWithThis) {
2004         for (Iterator iterator = flowGraph.getReturnNodeSet().iterator(); iterator.hasNext();) {
2005           FlowNode returnFlowNode = (FlowNode) iterator.next();
2006           if (reachableSet.contains(returnFlowNode)) {
2007             return true;
2008           }
2009         }
2010       }
2011     }
2012     return false;
2013   }
2014
2015   private void assignCompositeLocation(CompositeLocation compLocPrefix, GlobalFlowNode node) {
2016     CompositeLocation newCompLoc = compLocPrefix.clone();
2017     NTuple<Location> locTuple = node.getLocTuple();
2018     for (int i = 1; i < locTuple.size(); i++) {
2019       newCompLoc.addLocation(locTuple.get(i));
2020     }
2021     node.setInferCompositeLocation(newCompLoc);
2022   }
2023
2024   private List<NTuple<Location>> calculatePrefixList(GlobalFlowGraph graph, GlobalFlowNode node) {
2025
2026     // System.out.println("\n##### calculatePrefixList node=" + node);
2027
2028     Set<GlobalFlowNode> incomingNodeSetPrefix =
2029         graph.getIncomingNodeSetByPrefix(node.getLocTuple().get(0));
2030     // System.out.println("---incomingNodeSetPrefix=" + incomingNodeSetPrefix);
2031
2032     Set<GlobalFlowNode> reachableNodeSetPrefix =
2033         graph.getReachableNodeSetByPrefix(node.getLocTuple().get(0));
2034     // System.out.println("---reachableNodeSetPrefix=" + reachableNodeSetPrefix);
2035
2036     List<NTuple<Location>> prefixList = new ArrayList<NTuple<Location>>();
2037
2038     for (Iterator iterator = incomingNodeSetPrefix.iterator(); iterator.hasNext();) {
2039       GlobalFlowNode inNode = (GlobalFlowNode) iterator.next();
2040       NTuple<Location> inNodeTuple = inNode.getLocTuple();
2041
2042       if (inNodeTuple.get(0).getLocDescriptor() instanceof InterDescriptor
2043           || inNodeTuple.get(0).getLocDescriptor().equals(GLOBALDESC)) {
2044         continue;
2045       }
2046
2047       for (int i = 1; i < inNodeTuple.size(); i++) {
2048         NTuple<Location> prefix = inNodeTuple.subList(0, i);
2049         if (!prefixList.contains(prefix)) {
2050           prefixList.add(prefix);
2051         }
2052       }
2053     }
2054
2055     Collections.sort(prefixList, new Comparator<NTuple<Location>>() {
2056       public int compare(NTuple<Location> arg0, NTuple<Location> arg1) {
2057         int s0 = arg0.size();
2058         int s1 = arg1.size();
2059         if (s0 > s1) {
2060           return -1;
2061         } else if (s0 == s1) {
2062           return 0;
2063         } else {
2064           return 1;
2065         }
2066       }
2067     });
2068
2069     return prefixList;
2070
2071   }
2072
2073   private CompositeLocation calculateCompositeLocationFromFlowGraph(MethodDescriptor md,
2074       FlowNode node) {
2075
2076     // System.out.println("#############################################################");
2077     // System.out.println("calculateCompositeLocationFromFlowGraph=" + node);
2078
2079     FlowGraph flowGraph = getFlowGraph(md);
2080     // NTuple<Location> paramLocTuple = translateToLocTuple(md, paramNode.getDescTuple());
2081     // GlobalFlowNode paramGlobalNode = subGlobalFlowGraph.getFlowNode(paramLocTuple);
2082
2083     List<NTuple<Location>> prefixList = calculatePrefixListFlowGraph(flowGraph, node);
2084
2085     // Set<GlobalFlowNode> reachableNodeSet =
2086     // subGlobalFlowGraph.getReachableNodeSetByPrefix(paramGlobalNode.getLocTuple().get(0));
2087     //
2088     Set<FlowNode> reachableNodeSet =
2089         flowGraph.getReachableSetFrom(node.getDescTuple().subList(0, 1));
2090
2091     // Set<GlobalFlowNode> reachNodeSet = globalFlowGraph.getReachableNodeSetFrom(node);
2092
2093     // System.out.println("node=" + node + "    prefixList=" + prefixList);
2094
2095     for (int i = 0; i < prefixList.size(); i++) {
2096       NTuple<Location> curPrefix = prefixList.get(i);
2097       Set<NTuple<Location>> reachableCommonPrefixSet = new HashSet<NTuple<Location>>();
2098
2099       for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
2100         FlowNode reachNode = (FlowNode) iterator2.next();
2101         NTuple<Location> reachLocTuple = translateToLocTuple(md, reachNode.getCurrentDescTuple());
2102         if (reachLocTuple.startsWith(curPrefix)) {
2103           reachableCommonPrefixSet.add(reachLocTuple);
2104         }
2105       }
2106       // System.out.println("reachableCommonPrefixSet=" + reachableCommonPrefixSet);
2107
2108       if (!reachableCommonPrefixSet.isEmpty()) {
2109
2110         MethodDescriptor curPrefixFirstElementMethodDesc =
2111             (MethodDescriptor) curPrefix.get(0).getDescriptor();
2112
2113         Location curPrefixLocalLoc = curPrefix.get(0);
2114
2115         Location targetLocalLoc = new Location(md, node.getDescTuple().get(0));
2116         // Location targetLocalLoc = paramGlobalNode.getLocTuple().get(0);
2117
2118         CompositeLocation newCompLoc = generateCompositeLocation(curPrefix);
2119         // System.out.println("NEED2ASSIGN COMP LOC TO " + node + " with prefix=" + curPrefix);
2120         // System.out.println("-targetLocalLoc=" + targetLocalLoc + "   - newCompLoc=" +
2121         // newCompLoc);
2122
2123         node.setCompositeLocation(newCompLoc);
2124
2125         return newCompLoc;
2126
2127       }
2128
2129     }
2130     return null;
2131   }
2132
2133   private List<NTuple<Location>> calculatePrefixListFlowGraph(FlowGraph graph, FlowNode node) {
2134
2135     // System.out.println("\n##### calculatePrefixList node=" + node);
2136
2137     MethodDescriptor md = graph.getMethodDescriptor();
2138     Set<FlowNode> incomingNodeSetPrefix =
2139         graph.getIncomingNodeSetByPrefix(node.getDescTuple().get(0));
2140     // System.out.println("---incomingNodeSetPrefix=" + incomingNodeSetPrefix);
2141
2142     Set<FlowNode> reachableNodeSetPrefix =
2143         graph.getReachableSetFrom(node.getDescTuple().subList(0, 1));
2144     // System.out.println("---reachableNodeSetPrefix=" + reachableNodeSetPrefix);
2145
2146     List<NTuple<Location>> prefixList = new ArrayList<NTuple<Location>>();
2147
2148     for (Iterator iterator = incomingNodeSetPrefix.iterator(); iterator.hasNext();) {
2149       FlowNode inNode = (FlowNode) iterator.next();
2150       NTuple<Location> inNodeTuple = translateToLocTuple(md, inNode.getCurrentDescTuple());
2151
2152       // if (inNodeTuple.get(0).getLocDescriptor() instanceof InterDescriptor
2153       // || inNodeTuple.get(0).getLocDescriptor().equals(GLOBALDESC)) {
2154       // continue;
2155       // }
2156
2157       for (int i = 1; i < inNodeTuple.size(); i++) {
2158         NTuple<Location> prefix = inNodeTuple.subList(0, i);
2159         if (!prefixList.contains(prefix)) {
2160           prefixList.add(prefix);
2161         }
2162       }
2163     }
2164
2165     Collections.sort(prefixList, new Comparator<NTuple<Location>>() {
2166       public int compare(NTuple<Location> arg0, NTuple<Location> arg1) {
2167         int s0 = arg0.size();
2168         int s1 = arg1.size();
2169         if (s0 > s1) {
2170           return -1;
2171         } else if (s0 == s1) {
2172           return 0;
2173         } else {
2174           return 1;
2175         }
2176       }
2177     });
2178
2179     return prefixList;
2180
2181   }
2182
2183   private GlobalFlowGraph constructSubGlobalFlowGraph(FlowGraph flowGraph) {
2184
2185     MethodDescriptor md = flowGraph.getMethodDescriptor();
2186
2187     GlobalFlowGraph globalGraph = getSubGlobalFlowGraph(md);
2188
2189     // Set<FlowNode> nodeSet = flowGraph.getNodeSet();
2190     Set<FlowEdge> edgeSet = flowGraph.getEdgeSet();
2191
2192     for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) {
2193
2194       FlowEdge edge = (FlowEdge) iterator.next();
2195       NTuple<Descriptor> srcDescTuple = edge.getInitTuple();
2196       NTuple<Descriptor> dstDescTuple = edge.getEndTuple();
2197
2198       if (flowGraph.getFlowNode(srcDescTuple) instanceof FlowReturnNode
2199           || flowGraph.getFlowNode(dstDescTuple) instanceof FlowReturnNode) {
2200         continue;
2201       }
2202
2203       // here only keep the first element(method location) of the descriptor
2204       // tuple
2205       NTuple<Location> srcLocTuple = translateToLocTuple(md, srcDescTuple);
2206       NTuple<Location> dstLocTuple = translateToLocTuple(md, dstDescTuple);
2207
2208       globalGraph.addValueFlowEdge(srcLocTuple, dstLocTuple);
2209
2210     }
2211
2212     return globalGraph;
2213   }
2214
2215   private NTuple<Location> translateToLocTuple(MethodDescriptor md, NTuple<Descriptor> descTuple) {
2216
2217     NTuple<Location> locTuple = new NTuple<Location>();
2218
2219     Descriptor enclosingDesc = md;
2220     for (int i = 0; i < descTuple.size(); i++) {
2221       Descriptor desc = descTuple.get(i);
2222
2223       Location loc = new Location(enclosingDesc, desc);
2224       locTuple.add(loc);
2225
2226       if (desc instanceof VarDescriptor) {
2227         enclosingDesc = ((VarDescriptor) desc).getType().getClassDesc();
2228       } else if (desc instanceof FieldDescriptor) {
2229         enclosingDesc = ((FieldDescriptor) desc).getType().getClassDesc();
2230       } else {
2231         enclosingDesc = desc;
2232       }
2233
2234     }
2235
2236     return locTuple;
2237
2238   }
2239
2240   private void addValueFlowsFromCalleeSubGlobalFlowGraph(MethodDescriptor mdCaller) {
2241
2242     // the transformation for a call site propagates flows through parameters
2243     // if the method is virtual, it also grab all relations from any possible
2244     // callees
2245
2246     Set<MethodInvokeNode> setMethodInvokeNode = getMethodInvokeNodeSet(mdCaller);
2247
2248     for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) {
2249       MethodInvokeNode min = (MethodInvokeNode) iterator.next();
2250       MethodDescriptor mdCallee = min.getMethod();
2251       Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
2252       if (mdCallee.isStatic()) {
2253         setPossibleCallees.add(mdCallee);
2254       } else {
2255         Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getMethods(mdCallee);
2256         // removes method descriptors that are not invoked by the caller
2257         calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller));
2258         setPossibleCallees.addAll(calleeSet);
2259       }
2260
2261       for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
2262         MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
2263         propagateValueFlowsToCallerFromSubGlobalFlowGraph(min, mdCaller, possibleMdCallee);
2264       }
2265
2266     }
2267
2268   }
2269
2270   private void propagateValueFlowsToCallerFromSubGlobalFlowGraph(MethodInvokeNode min,
2271       MethodDescriptor mdCaller, MethodDescriptor possibleMdCallee) {
2272
2273     // System.out.println("---propagate from " + min.printNode(0) + " to caller=" + mdCaller);
2274     FlowGraph calleeFlowGraph = getFlowGraph(possibleMdCallee);
2275     Map<Integer, NTuple<Descriptor>> mapIdxToArg = mapMethodInvokeNodeToArgIdxMap.get(min);
2276
2277     // System.out.println("-----mapMethodInvokeNodeToArgIdxMap.get(min)="
2278     // + mapMethodInvokeNodeToArgIdxMap.get(min));
2279
2280     Set<Integer> keySet = mapIdxToArg.keySet();
2281     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2282       Integer idx = (Integer) iterator.next();
2283       NTuple<Descriptor> argDescTuple = mapIdxToArg.get(idx);
2284       if (argDescTuple.size() > 0) {
2285         NTuple<Location> argLocTuple = translateToLocTuple(mdCaller, argDescTuple);
2286         NTuple<Descriptor> paramDescTuple = calleeFlowGraph.getParamFlowNode(idx).getDescTuple();
2287         NTuple<Location> paramLocTuple = translateToLocTuple(possibleMdCallee, paramDescTuple);
2288         // System.out.println("-------paramDescTuple=" + paramDescTuple + "->argDescTuple="
2289         // + argDescTuple);
2290         addMapCallerArgToCalleeParam(min, argDescTuple, paramDescTuple);
2291       }
2292     }
2293
2294     // addValueFlowBetweenParametersToCaller(min, mdCaller, possibleMdCallee);
2295
2296     NTuple<Descriptor> baseTuple = mapMethodInvokeNodeToBaseTuple.get(min);
2297     GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(possibleMdCallee);
2298     Set<GlobalFlowNode> calleeNodeSet = calleeSubGlobalGraph.getNodeSet();
2299     for (Iterator iterator = calleeNodeSet.iterator(); iterator.hasNext();) {
2300       GlobalFlowNode calleeNode = (GlobalFlowNode) iterator.next();
2301       addValueFlowFromCalleeNode(min, mdCaller, possibleMdCallee, calleeNode);
2302     }
2303
2304     // System.out.println("$$$GLOBAL PC LOC ADD=" + mdCaller);
2305     Set<NTuple<Location>> pcLocTupleSet = mapMethodInvokeNodeToPCLocTupleSet.get(min);
2306     // System.out.println("---pcLocTupleSet=" + pcLocTupleSet);
2307     GlobalFlowGraph callerSubGlobalGraph = getSubGlobalFlowGraph(mdCaller);
2308     for (Iterator iterator = calleeNodeSet.iterator(); iterator.hasNext();) {
2309       GlobalFlowNode calleeNode = (GlobalFlowNode) iterator.next();
2310       if (calleeNode.isParamNodeWithIncomingFlows()) {
2311         // System.out.println("calleeNode.getLocTuple()" + calleeNode.getLocTuple());
2312         NTuple<Location> callerSrcNodeLocTuple =
2313             translateToCallerLocTuple(min, possibleMdCallee, mdCaller, calleeNode.getLocTuple());
2314         // System.out.println("---callerSrcNodeLocTuple=" + callerSrcNodeLocTuple);
2315         if (callerSrcNodeLocTuple != null && callerSrcNodeLocTuple.size() > 0) {
2316           for (Iterator iterator2 = pcLocTupleSet.iterator(); iterator2.hasNext();) {
2317             NTuple<Location> pcLocTuple = (NTuple<Location>) iterator2.next();
2318
2319             callerSubGlobalGraph.addValueFlowEdge(pcLocTuple, callerSrcNodeLocTuple);
2320           }
2321         }
2322       }
2323
2324     }
2325
2326   }
2327
2328   private void addValueFlowFromCalleeNode(MethodInvokeNode min, MethodDescriptor mdCaller,
2329       MethodDescriptor mdCallee, GlobalFlowNode calleeSrcNode) {
2330
2331     GlobalFlowGraph calleeSubGlobalGraph = getSubGlobalFlowGraph(mdCallee);
2332     GlobalFlowGraph callerSubGlobalGraph = getSubGlobalFlowGraph(mdCaller);
2333
2334     // System.out.println("$addValueFlowFromCalleeNode calleeSrcNode=" + calleeSrcNode);
2335
2336     NTuple<Location> callerSrcNodeLocTuple =
2337         translateToCallerLocTuple(min, mdCallee, mdCaller, calleeSrcNode.getLocTuple());
2338     // System.out.println("---callerSrcNodeLocTuple=" + callerSrcNodeLocTuple);
2339
2340     if (callerSrcNodeLocTuple != null && callerSrcNodeLocTuple.size() > 0) {
2341
2342       Set<GlobalFlowNode> outNodeSet = calleeSubGlobalGraph.getOutNodeSet(calleeSrcNode);
2343
2344       for (Iterator iterator = outNodeSet.iterator(); iterator.hasNext();) {
2345         GlobalFlowNode outNode = (GlobalFlowNode) iterator.next();
2346         NTuple<Location> callerDstNodeLocTuple =
2347             translateToCallerLocTuple(min, mdCallee, mdCaller, outNode.getLocTuple());
2348         // System.out.println("outNode=" + outNode + "   callerDstNodeLocTuple="
2349         // + callerDstNodeLocTuple);
2350         if (callerSrcNodeLocTuple != null && callerDstNodeLocTuple != null
2351             && callerSrcNodeLocTuple.size() > 0 && callerDstNodeLocTuple.size() > 0) {
2352           callerSubGlobalGraph.addValueFlowEdge(callerSrcNodeLocTuple, callerDstNodeLocTuple);
2353         }
2354       }
2355     }
2356
2357   }
2358
2359   private NTuple<Location> translateToCallerLocTuple(MethodInvokeNode min,
2360       MethodDescriptor mdCallee, MethodDescriptor mdCaller, NTuple<Location> nodeLocTuple) {
2361     // this method will return the same nodeLocTuple if the corresponding argument is literal
2362     // value.
2363
2364     // System.out.println("translateToCallerLocTuple=" + nodeLocTuple);
2365
2366     FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
2367     NTuple<Descriptor> nodeDescTuple = translateToDescTuple(nodeLocTuple);
2368     if (calleeFlowGraph.isParameter(nodeDescTuple)) {
2369       int paramIdx = calleeFlowGraph.getParamIdx(nodeDescTuple);
2370       NTuple<Descriptor> argDescTuple = mapMethodInvokeNodeToArgIdxMap.get(min).get(paramIdx);
2371
2372       // if (isPrimitive(nodeLocTuple.get(0).getLocDescriptor())) {
2373       // // the type of argument is primitive.
2374       // return nodeLocTuple.clone();
2375       // }
2376       // System.out.println("paramIdx=" + paramIdx + "  argDescTuple=" + argDescTuple + " from min="
2377       // + min.printNode(0));
2378       NTuple<Location> argLocTuple = translateToLocTuple(mdCaller, argDescTuple);
2379
2380       NTuple<Location> callerLocTuple = new NTuple<Location>();
2381
2382       callerLocTuple.addAll(argLocTuple);
2383       for (int i = 1; i < nodeLocTuple.size(); i++) {
2384         callerLocTuple.add(nodeLocTuple.get(i));
2385       }
2386       return callerLocTuple;
2387     } else {
2388       return nodeLocTuple.clone();
2389     }
2390
2391   }
2392
2393   public static boolean isPrimitive(Descriptor desc) {
2394
2395     if (desc instanceof FieldDescriptor) {
2396       return ((FieldDescriptor) desc).getType().isPrimitive();
2397     } else if (desc instanceof VarDescriptor) {
2398       return ((VarDescriptor) desc).getType().isPrimitive();
2399     } else if (desc instanceof InterDescriptor) {
2400       return true;
2401     }
2402
2403     return false;
2404   }
2405
2406   public static boolean isReference(Descriptor desc) {
2407
2408     if (desc instanceof FieldDescriptor) {
2409
2410       TypeDescriptor type = ((FieldDescriptor) desc).getType();
2411       if (type.isArray()) {
2412         return !type.isPrimitive();
2413       } else {
2414         return type.isPtr();
2415       }
2416
2417     } else if (desc instanceof VarDescriptor) {
2418       TypeDescriptor type = ((VarDescriptor) desc).getType();
2419       if (type.isArray()) {
2420         return !type.isPrimitive();
2421       } else {
2422         return type.isPtr();
2423       }
2424     }
2425
2426     return false;
2427   }
2428
2429   private NTuple<Descriptor> translateToDescTuple(NTuple<Location> locTuple) {
2430
2431     NTuple<Descriptor> descTuple = new NTuple<Descriptor>();
2432     for (int i = 0; i < locTuple.size(); i++) {
2433       descTuple.add(locTuple.get(i).getLocDescriptor());
2434     }
2435     return descTuple;
2436
2437   }
2438
2439   public LocationSummary getLocationSummary(Descriptor d) {
2440     if (!mapDescToLocationSummary.containsKey(d)) {
2441       if (d instanceof MethodDescriptor) {
2442         mapDescToLocationSummary.put(d, new MethodSummary((MethodDescriptor) d));
2443       } else if (d instanceof ClassDescriptor) {
2444         mapDescToLocationSummary.put(d, new FieldSummary());
2445       }
2446     }
2447     return mapDescToLocationSummary.get(d);
2448   }
2449
2450   private void generateMethodSummary() {
2451
2452     Set<MethodDescriptor> keySet = md2lattice.keySet();
2453     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2454       MethodDescriptor md = (MethodDescriptor) iterator.next();
2455
2456       System.out.println("\nSSJAVA: generate method summary: " + md);
2457
2458       FlowGraph flowGraph = getFlowGraph(md);
2459       if (flowGraph == null) {
2460         continue;
2461       }
2462       MethodSummary methodSummary = getMethodSummary(md);
2463
2464       HierarchyGraph scGraph = getSkeletonCombinationHierarchyGraph(md);
2465
2466       // set the 'this' reference location
2467       if (!md.isStatic()) {
2468         // System.out.println("setThisLocName=" + scGraph.getHNode(md.getThis()).getName());
2469         methodSummary.setThisLocName(scGraph.getHNode(md.getThis()).getName());
2470       }
2471
2472       // set the 'global' reference location if needed
2473       if (methodSummary.hasGlobalAccess()) {
2474         methodSummary.setGlobalLocName(scGraph.getHNode(GLOBALDESC).getName());
2475       }
2476
2477       // construct a parameter mapping that maps a parameter descriptor to an
2478       // inferred composite location
2479       for (int paramIdx = 0; paramIdx < flowGraph.getNumParameters(); paramIdx++) {
2480         FlowNode flowNode = flowGraph.getParamFlowNode(paramIdx);
2481         CompositeLocation inferredCompLoc =
2482             updateCompositeLocation(flowNode.getCompositeLocation());
2483         // System.out.println("-paramIdx=" + paramIdx + "   infer=" + inferredCompLoc + " original="
2484         // + flowNode.getCompositeLocation());
2485
2486         Descriptor localVarDesc = flowNode.getDescTuple().get(0);
2487         methodSummary.addMapVarNameToInferCompLoc(localVarDesc, inferredCompLoc);
2488         methodSummary.addMapParamIdxToInferLoc(paramIdx, inferredCompLoc);
2489       }
2490
2491     }
2492
2493   }
2494
2495   private boolean hasOrderingRelation(NTuple<Location> locTuple1, NTuple<Location> locTuple2) {
2496
2497     int size = locTuple1.size() >= locTuple2.size() ? locTuple2.size() : locTuple1.size();
2498
2499     for (int idx = 0; idx < size; idx++) {
2500       Location loc1 = locTuple1.get(idx);
2501       Location loc2 = locTuple2.get(idx);
2502
2503       Descriptor desc1 = loc1.getDescriptor();
2504       Descriptor desc2 = loc2.getDescriptor();
2505
2506       if (!desc1.equals(desc2)) {
2507         throw new Error("Fail to compare " + locTuple1 + " and " + locTuple2);
2508       }
2509
2510       Descriptor locDesc1 = loc1.getLocDescriptor();
2511       Descriptor locDesc2 = loc2.getLocDescriptor();
2512
2513       HierarchyGraph hierarchyGraph = getHierarchyGraph(desc1);
2514
2515       HNode node1 = hierarchyGraph.getHNode(locDesc1);
2516       HNode node2 = hierarchyGraph.getHNode(locDesc2);
2517
2518       // System.out.println("---node1=" + node1 + "  node2=" + node2);
2519       // System.out.println("---hierarchyGraph.getIncomingNodeSet(node2)="
2520       // + hierarchyGraph.getIncomingNodeSet(node2));
2521
2522       if (locDesc1.equals(locDesc2)) {
2523         continue;
2524       } else if (!hierarchyGraph.getIncomingNodeSet(node2).contains(node1)
2525           && !hierarchyGraph.getIncomingNodeSet(node1).contains(node2)) {
2526         return false;
2527       } else {
2528         return true;
2529       }
2530
2531     }
2532
2533     return false;
2534
2535   }
2536
2537   private boolean isHigherThan(NTuple<Location> locTuple1, NTuple<Location> locTuple2) {
2538
2539     int size = locTuple1.size() >= locTuple2.size() ? locTuple2.size() : locTuple1.size();
2540
2541     for (int idx = 0; idx < size; idx++) {
2542       Location loc1 = locTuple1.get(idx);
2543       Location loc2 = locTuple2.get(idx);
2544
2545       Descriptor desc1 = loc1.getDescriptor();
2546       Descriptor desc2 = loc2.getDescriptor();
2547
2548       if (!desc1.equals(desc2)) {
2549         throw new Error("Fail to compare " + locTuple1 + " and " + locTuple2);
2550       }
2551
2552       Descriptor locDesc1 = loc1.getLocDescriptor();
2553       Descriptor locDesc2 = loc2.getLocDescriptor();
2554
2555       HierarchyGraph hierarchyGraph = getHierarchyGraph(desc1);
2556
2557       HNode node1 = hierarchyGraph.getHNode(locDesc1);
2558       HNode node2 = hierarchyGraph.getHNode(locDesc2);
2559
2560       // System.out.println("---node1=" + node1 + "  node2=" + node2);
2561       // System.out.println("---hierarchyGraph.getIncomingNodeSet(node2)="
2562       // + hierarchyGraph.getIncomingNodeSet(node2));
2563
2564       if (locDesc1.equals(locDesc2)) {
2565         continue;
2566       } else if (hierarchyGraph.getIncomingNodeSet(node2).contains(node1)) {
2567         return true;
2568       } else {
2569         return false;
2570       }
2571
2572     }
2573
2574     return false;
2575   }
2576
2577   private void debug_writeLattices() {
2578
2579     Set<Descriptor> keySet = mapDescriptorToSkeletonLattice.keySet();
2580     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2581       Descriptor key = (Descriptor) iterator.next();
2582       SSJavaLattice<String> skeletonLattice = mapDescriptorToSkeletonLattice.get(key);
2583       // HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(key);
2584       HierarchyGraph scHierarchyGraph = getSkeletonCombinationHierarchyGraph(key);
2585       if (key instanceof ClassDescriptor) {
2586         writeInferredLatticeDotFile((ClassDescriptor) key, skeletonLattice, "_SKELETON");
2587       } else if (key instanceof MethodDescriptor) {
2588         MethodDescriptor md = (MethodDescriptor) key;
2589         writeInferredLatticeDotFile(md.getClassDesc(), md, skeletonLattice, "_SKELETON");
2590       }
2591
2592       LocationSummary ls = getLocationSummary(key);
2593       // System.out.println("####LOC SUMMARY=" + key + "\n" + ls.getMapHNodeNameToLocationName());
2594     }
2595
2596     Set<ClassDescriptor> cdKeySet = cd2lattice.keySet();
2597     for (Iterator iterator = cdKeySet.iterator(); iterator.hasNext();) {
2598       ClassDescriptor cd = (ClassDescriptor) iterator.next();
2599       // System.out.println("########cd=" + cd);
2600       writeInferredLatticeDotFile((ClassDescriptor) cd, cd2lattice.get(cd), "");
2601       COUNT += cd2lattice.get(cd).getKeySet().size();
2602     }
2603
2604     Set<MethodDescriptor> mdKeySet = md2lattice.keySet();
2605     for (Iterator iterator = mdKeySet.iterator(); iterator.hasNext();) {
2606       MethodDescriptor md = (MethodDescriptor) iterator.next();
2607       writeInferredLatticeDotFile(md.getClassDesc(), md, md2lattice.get(md), "");
2608       COUNT += md2lattice.get(md).getKeySet().size();
2609     }
2610     System.out.println("###COUNT=" + COUNT);
2611
2612     Set<Descriptor> descKeySet = desc2naiveLattice.keySet();
2613     for (Iterator iterator = descKeySet.iterator(); iterator.hasNext();) {
2614       Descriptor desc = (Descriptor) iterator.next();
2615       // System.out.println("########cd=" + cd);
2616
2617       ClassDescriptor cd_naive;
2618       MethodDescriptor md_naive;
2619       if (desc instanceof ClassDescriptor) {
2620         cd_naive = (ClassDescriptor) desc;
2621         md_naive = null;
2622       } else {
2623         md_naive = (MethodDescriptor) desc;
2624         cd_naive = md_naive.getClassDesc();
2625       }
2626
2627       writeInferredLatticeDotFile(cd_naive, md_naive, desc2naiveLattice.get(desc), "_naive");
2628     }
2629   }
2630
2631   private void buildLattice(Descriptor desc) {
2632     // System.out.println("buildLattice=" + desc);
2633     SSJavaLattice<String> skeletonLattice = buildLattice.buildLattice(desc);
2634
2635     addMapDescToSkeletonLattice(desc, skeletonLattice);
2636
2637     // write a dot file before everything is done
2638     if (desc instanceof ClassDescriptor) {
2639       writeInferredLatticeDotFile((ClassDescriptor) desc, null, skeletonLattice, "_SC");
2640     } else {
2641       MethodDescriptor md = (MethodDescriptor) desc;
2642       writeInferredLatticeDotFile(md.getClassDesc(), md, skeletonLattice, "_SC");
2643     }
2644
2645     HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc);
2646
2647     // System.out.println("\n## insertIntermediateNodesToStraightLine:"
2648     // + simpleHierarchyGraph.getName());
2649     SSJavaLattice<String> lattice =
2650         buildLattice.insertIntermediateNodesToStraightLine(desc, skeletonLattice);
2651
2652     if (lattice == null) {
2653       return;
2654     }
2655     lattice.removeRedundantEdges();
2656
2657     int numLocs = lattice.getKeySet().size();
2658     LocationInference.numLocationsSInfer += numLocs;
2659     mapNumLocsMapSInfer.put(desc, new Integer(numLocs));
2660
2661     int numPaths = lattice.countPaths();
2662     LocationInference.numLocationsSInfer += numPaths;
2663     mapNumPathsMapSInfer.put(desc, new Integer(numPaths));
2664
2665     System.out.println(desc + " numPaths=" + numPaths + " numLocs=" + numLocs);
2666
2667     if (desc instanceof ClassDescriptor) {
2668       // field lattice
2669       cd2lattice.put((ClassDescriptor) desc, lattice);
2670       ssjava.writeLatticeDotFile((ClassDescriptor) desc, null, lattice);
2671     } else if (desc instanceof MethodDescriptor) {
2672       // method lattice
2673       md2lattice.put((MethodDescriptor) desc, lattice);
2674       MethodDescriptor md = (MethodDescriptor) desc;
2675       ClassDescriptor cd = md.getClassDesc();
2676       ssjava.writeLatticeDotFile(cd, md, lattice);
2677     }
2678
2679   }
2680
2681   // deprecated: it builds method/class lattices without considering class inheritance
2682   private void buildLattice() {
2683
2684     Set<Descriptor> keySet = mapDescriptorToCombineSkeletonHierarchyGraph.keySet();
2685     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2686       Descriptor desc = (Descriptor) iterator.next();
2687
2688       SSJavaLattice<String> simpleLattice = buildLattice.buildLattice(desc);
2689
2690       addMapDescToSkeletonLattice(desc, simpleLattice);
2691
2692       HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc);
2693       System.out.println("\n## insertIntermediateNodesToStraightLine:"
2694           + simpleHierarchyGraph.getName());
2695       SSJavaLattice<String> lattice =
2696           buildLattice.insertIntermediateNodesToStraightLine(desc, simpleLattice);
2697       lattice.removeRedundantEdges();
2698
2699       LocationInference.numLocationsSInfer += lattice.getKeySet().size();
2700
2701       if (desc instanceof ClassDescriptor) {
2702         // field lattice
2703         cd2lattice.put((ClassDescriptor) desc, lattice);
2704         // ssjava.writeLatticeDotFile((ClassDescriptor) desc, null, lattice);
2705       } else if (desc instanceof MethodDescriptor) {
2706         // method lattice
2707         md2lattice.put((MethodDescriptor) desc, lattice);
2708         MethodDescriptor md = (MethodDescriptor) desc;
2709         ClassDescriptor cd = md.getClassDesc();
2710         // ssjava.writeLatticeDotFile(cd, md, lattice);
2711       }
2712
2713     }
2714
2715   }
2716
2717   private void buildLatticeInheritanceTree() {
2718     // DFS the inheritance tree and propagates lattice nodes/edges from the parent to children
2719     // Node<ClassDescriptor> rootNode = inheritanceTree.getRootNode();
2720     DFSBuildLatticeInheritanceTree(rootClassDescriptor);
2721   }
2722
2723   public Set<ClassDescriptor> getDirectSubClasses(ClassDescriptor parent) {
2724
2725     Set<ClassDescriptor> result = new HashSet<ClassDescriptor>();
2726
2727     Set<ClassDescriptor> children = tu.getDirectSubClasses(parent);
2728     if (children == null) {
2729       children = new HashSet<ClassDescriptor>();
2730     }
2731
2732     for (Iterator iterator = children.iterator(); iterator.hasNext();) {
2733       ClassDescriptor child = (ClassDescriptor) iterator.next();
2734       if (toanalyze_classDescSet.contains(child)) {
2735         result.add(child);
2736       }
2737     }
2738
2739     return result;
2740   }
2741
2742   private void DFSBuildLatticeInheritanceTree(ClassDescriptor cd) {
2743     // ClassDescriptor cd = node.getData();
2744
2745     ClassDescriptor parentClassDesc = cd.getSuperDesc();
2746     if (parentClassDesc != null) {
2747       Map<TripleItem, String> parentMap = buildLattice.getIntermediateLocMap(parentClassDesc);
2748       buildLattice.setIntermediateLocMap(cd, parentMap);
2749     }
2750
2751     buildLattice(cd);
2752
2753     for (Iterator iterator = cd.getMethods(); iterator.hasNext();) {
2754       MethodDescriptor md = (MethodDescriptor) iterator.next();
2755       if (toanalyze_methodDescList.contains(md)) {
2756         MethodDescriptor parentMethodDesc = getParentMethodDesc(md.getClassDesc(), md);
2757         if (parentMethodDesc != null) {
2758           Map<TripleItem, String> parentMap = buildLattice.getIntermediateLocMap(parentMethodDesc);
2759           Map<TripleItem, String> childMap = new HashMap<TripleItem, String>();
2760           Set<TripleItem> keySet = parentMap.keySet();
2761           for (Iterator iterator2 = keySet.iterator(); iterator2.hasNext();) {
2762             TripleItem key = (TripleItem) iterator2.next();
2763             childMap.put(key, parentMap.get(key));
2764           }
2765           buildLattice.setIntermediateLocMap(md, childMap);
2766         }
2767         buildLattice(md);
2768       }
2769     }
2770
2771     // traverse children
2772     Set<ClassDescriptor> children = tu.getDirectSubClasses(cd);
2773     if (children != null) {
2774       for (Iterator iterator = children.iterator(); iterator.hasNext();) {
2775         ClassDescriptor classDescriptor = (ClassDescriptor) iterator.next();
2776         if (toanalyze_classDescSet.contains(classDescriptor)) {
2777           DFSBuildLatticeInheritanceTree(classDescriptor);
2778         } else {
2779           if (classDescriptor.isAbstract()) {
2780             DFSBuildLatticeInheritanceTree(classDescriptor);
2781           }
2782         }
2783       }
2784     }
2785
2786   }
2787
2788   public void addMapDescToSkeletonLattice(Descriptor desc, SSJavaLattice<String> lattice) {
2789     mapDescriptorToSkeletonLattice.put(desc, lattice);
2790   }
2791
2792   public SSJavaLattice<String> getSkeletonLattice(Descriptor desc) {
2793     return mapDescriptorToSkeletonLattice.get(desc);
2794   }
2795
2796   private void simplifyHierarchyGraph() {
2797     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
2798     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2799       Descriptor desc = (Descriptor) iterator.next();
2800       // System.out.println("SSJAVA: remove redundant edges: " + desc);
2801       HierarchyGraph simpleHierarchyGraph = getHierarchyGraph(desc).clone();
2802       simpleHierarchyGraph.setName(desc + "_SIMPLE");
2803       simpleHierarchyGraph.removeRedundantEdges();
2804       // simpleHierarchyGraph.removeIsolatedNodes();
2805       mapDescriptorToSimpleHierarchyGraph.put(desc, simpleHierarchyGraph);
2806     }
2807   }
2808
2809   private void insertCombinationNodes() {
2810     Set<Descriptor> keySet = mapDescriptorToSkeletonHierarchyGraph.keySet();
2811     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2812       Descriptor desc = (Descriptor) iterator.next();
2813       System.out.println("\nSSJAVA: Inserting Combination Nodes:" + desc);
2814       HierarchyGraph skeletonGraph = getSkeletonHierarchyGraph(desc);
2815       HierarchyGraph skeletonGraphWithCombinationNode = skeletonGraph.clone();
2816       skeletonGraphWithCombinationNode.setSCGraph(true);
2817       skeletonGraphWithCombinationNode.setName(desc + "_SC");
2818
2819       HierarchyGraph simpleHierarchyGraph = getSimpleHierarchyGraph(desc);
2820       skeletonGraphWithCombinationNode.insertCombinationNodesToGraph(simpleHierarchyGraph);
2821       // skeletonGraphWithCombinationNode.insertCombinationNodesToGraph(simpleHierarchyGraph,
2822       // skeletonGraph);
2823       // skeletonGraphWithCombinationNode.simplifySkeletonCombinationHierarchyGraph();
2824       skeletonGraphWithCombinationNode.removeRedundantEdges();
2825       mapDescriptorToCombineSkeletonHierarchyGraph.put(desc, skeletonGraphWithCombinationNode);
2826     }
2827   }
2828
2829   private void constructSkeletonHierarchyGraph() {
2830     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
2831     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2832       Descriptor desc = (Descriptor) iterator.next();
2833       System.out.println("SSJAVA: Constructing Skeleton Hierarchy Graph: " + desc);
2834       HierarchyGraph simpleGraph = getSimpleHierarchyGraph(desc);
2835       HierarchyGraph skeletonGraph = simpleGraph.generateSkeletonGraph();
2836       skeletonGraph.setMapDescToHNode(simpleGraph.getMapDescToHNode());
2837       skeletonGraph.setMapHNodeToDescSet(simpleGraph.getMapHNodeToDescSet());
2838       skeletonGraph.simplifyHierarchyGraph(this);
2839       mapDescriptorToSkeletonHierarchyGraph.put(desc, skeletonGraph);
2840     }
2841   }
2842
2843   private void recurUpAccumulateInheritanceDesc(Descriptor curDesc, Set<Descriptor> set) {
2844
2845     if (curDesc instanceof ClassDescriptor) {
2846       ClassDescriptor cd = (ClassDescriptor) curDesc;
2847       ClassDescriptor parentClassDesc = cd.getSuperDesc();
2848       if (parentClassDesc != null && !parentClassDesc.equals(rootClassDescriptor)) {
2849         set.add(parentClassDesc);
2850         recurUpAccumulateInheritanceDesc(parentClassDesc, set);
2851       }
2852     } else {
2853       MethodDescriptor md = (MethodDescriptor) curDesc;
2854       ClassDescriptor cd = md.getClassDesc();
2855
2856       // traverse up
2857       ClassDescriptor parentClassDesc = cd.getSuperDesc();
2858       if (parentClassDesc != null && !parentClassDesc.equals(rootClassDescriptor)) {
2859
2860         Set<MethodDescriptor> methodDescSet =
2861             parentClassDesc.getMethodTable().getSet(md.getSymbol());
2862         for (Iterator iterator = methodDescSet.iterator(); iterator.hasNext();) {
2863           MethodDescriptor parentMethodDesc = (MethodDescriptor) iterator.next();
2864           if (parentMethodDesc.matches(md)) {
2865             set.add(parentMethodDesc);
2866             recurUpAccumulateInheritanceDesc(parentMethodDesc, set);
2867           }
2868         }
2869       }
2870
2871     }
2872
2873   }
2874
2875   private void recurDownAccumulateInheritanceDesc(Descriptor curDesc, Set<Descriptor> set) {
2876
2877     if (curDesc instanceof ClassDescriptor) {
2878       ClassDescriptor cd = (ClassDescriptor) curDesc;
2879       ClassDescriptor parentClassDesc = cd.getSuperDesc();
2880       Set<ClassDescriptor> directSubClasses = tu.getDirectSubClasses(cd);
2881       for (Iterator iterator = directSubClasses.iterator(); iterator.hasNext();) {
2882         ClassDescriptor child = (ClassDescriptor) iterator.next();
2883         recurDownAccumulateInheritanceDesc(child, set);
2884       }
2885     } else {
2886       MethodDescriptor md = (MethodDescriptor) curDesc;
2887       ClassDescriptor cd = md.getClassDesc();
2888
2889       // traverse down
2890       Set<ClassDescriptor> directSubClasses = tu.getDirectSubClasses(cd);
2891       for (Iterator iterator = directSubClasses.iterator(); iterator.hasNext();) {
2892         ClassDescriptor child = (ClassDescriptor) iterator.next();
2893
2894         Set<MethodDescriptor> methodDescSet = child.getMethodTable().getSet(md.getSymbol());
2895         for (Iterator iterator2 = methodDescSet.iterator(); iterator2.hasNext();) {
2896           MethodDescriptor childMethodDesc = (MethodDescriptor) iterator2.next();
2897           if (childMethodDesc.matches(md)) {
2898             set.add(childMethodDesc);
2899             recurDownAccumulateInheritanceDesc(childMethodDesc, set);
2900           }
2901         }
2902       }
2903
2904     }
2905
2906   }
2907
2908   private void accumulateInheritanceDesc(Descriptor curDesc, Set<Descriptor> set) {
2909
2910     recurUpAccumulateInheritanceDesc(curDesc, set);
2911     recurDownAccumulateInheritanceDesc(curDesc, set);
2912
2913   }
2914
2915   public boolean isValidMergeInheritanceCheck(Descriptor desc, Set<HNode> mergeSet) {
2916
2917     // set up inheritance chain set...
2918     Set<Descriptor> inheritanceDescSet = new HashSet<Descriptor>();
2919     recurUpAccumulateInheritanceDesc(desc, inheritanceDescSet);
2920
2921     nextgraph: for (Iterator iterator = inheritanceDescSet.iterator(); iterator.hasNext();) {
2922       Descriptor inheritDesc = (Descriptor) iterator.next();
2923
2924       if (!desc.equals(inheritDesc)) {
2925         HierarchyGraph graph = getSkeletonCombinationHierarchyGraph(inheritDesc);
2926
2927         // first check whether this graph includes all elements of the merge set
2928         for (Iterator iterator2 = mergeSet.iterator(); iterator2.hasNext();) {
2929           HNode node = (HNode) iterator2.next();
2930           if (!graph.contains(node)) {
2931             continue nextgraph;
2932           }
2933         }
2934
2935         HNode firstNode = mergeSet.iterator().next();
2936
2937         Set<HNode> incomingNode = graph.getIncomingNodeSet(firstNode);
2938         Set<HNode> outgoingNode = graph.getOutgoingNodeSet(firstNode);
2939
2940         for (Iterator iterator2 = mergeSet.iterator(); iterator2.hasNext();) {
2941           HNode node = (HNode) iterator2.next();
2942
2943           if (!graph.getIncomingNodeSet(node).equals(incomingNode)
2944               || !graph.getOutgoingNodeSet(node).equals(outgoingNode)) {
2945             return false;
2946           }
2947
2948         }
2949       }
2950
2951     }
2952
2953     return true;
2954   }
2955
2956   private void debug_writeHierarchyDotFiles() {
2957
2958     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
2959     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2960       Descriptor desc = (Descriptor) iterator.next();
2961       getHierarchyGraph(desc).writeGraph();
2962     }
2963
2964   }
2965
2966   private void debug_writeSimpleHierarchyDotFiles() {
2967
2968     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
2969     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2970       Descriptor desc = (Descriptor) iterator.next();
2971       getHierarchyGraph(desc).writeGraph();
2972       getSimpleHierarchyGraph(desc).writeGraph();
2973       getSimpleHierarchyGraph(desc).writeGraph(true);
2974     }
2975
2976   }
2977
2978   private void debug_writeSkeletonHierarchyDotFiles() {
2979
2980     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
2981     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2982       Descriptor desc = (Descriptor) iterator.next();
2983       getSkeletonHierarchyGraph(desc).writeGraph();
2984     }
2985
2986   }
2987
2988   private void debug_writeSkeletonCombinationHierarchyDotFiles() {
2989
2990     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
2991     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2992       Descriptor desc = (Descriptor) iterator.next();
2993       getSkeletonCombinationHierarchyGraph(desc).writeGraph();
2994     }
2995
2996   }
2997
2998   public HierarchyGraph getSimpleHierarchyGraph(Descriptor d) {
2999     return mapDescriptorToSimpleHierarchyGraph.get(d);
3000   }
3001
3002   private HierarchyGraph getSkeletonHierarchyGraph(Descriptor d) {
3003     if (!mapDescriptorToSkeletonHierarchyGraph.containsKey(d)) {
3004       mapDescriptorToSkeletonHierarchyGraph.put(d, new HierarchyGraph(d));
3005     }
3006     return mapDescriptorToSkeletonHierarchyGraph.get(d);
3007   }
3008
3009   public HierarchyGraph getSkeletonCombinationHierarchyGraph(Descriptor d) {
3010     if (!mapDescriptorToCombineSkeletonHierarchyGraph.containsKey(d)) {
3011       mapDescriptorToCombineSkeletonHierarchyGraph.put(d, new HierarchyGraph(d));
3012     }
3013     return mapDescriptorToCombineSkeletonHierarchyGraph.get(d);
3014   }
3015
3016   private void constructHierarchyGraph() {
3017
3018     LinkedList<MethodDescriptor> methodDescList =
3019         (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
3020
3021     while (!methodDescList.isEmpty()) {
3022       MethodDescriptor md = methodDescList.removeLast();
3023       if (state.SSJAVADEBUG) {
3024         HierarchyGraph hierarchyGraph = new HierarchyGraph(md);
3025         System.out.println();
3026         System.out.println("SSJAVA: Construcing the hierarchy graph from " + md);
3027         constructHierarchyGraph(md, hierarchyGraph);
3028         mapDescriptorToHierarchyGraph.put(md, hierarchyGraph);
3029
3030       }
3031     }
3032
3033     setupToAnalyze();
3034     while (!toAnalyzeIsEmpty()) {
3035       ClassDescriptor cd = toAnalyzeNext();
3036       HierarchyGraph graph = getHierarchyGraph(cd);
3037       for (Iterator iter = cd.getFields(); iter.hasNext();) {
3038         FieldDescriptor fieldDesc = (FieldDescriptor) iter.next();
3039         if (!(fieldDesc.isStatic() && fieldDesc.isFinal())) {
3040           graph.getHNode(fieldDesc);
3041         }
3042       }
3043     }
3044
3045     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
3046     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
3047       Descriptor key = (Descriptor) iterator.next();
3048       HierarchyGraph graph = getHierarchyGraph(key);
3049
3050       Set<HNode> nodeToBeConnected = new HashSet<HNode>();
3051       for (Iterator iterator2 = graph.getNodeSet().iterator(); iterator2.hasNext();) {
3052         HNode node = (HNode) iterator2.next();
3053         if (!node.isSkeleton() && !node.isCombinationNode()) {
3054           if (graph.getIncomingNodeSet(node).size() == 0) {
3055             nodeToBeConnected.add(node);
3056           }
3057         }
3058       }
3059
3060       for (Iterator iterator2 = nodeToBeConnected.iterator(); iterator2.hasNext();) {
3061         HNode node = (HNode) iterator2.next();
3062         // System.out.println("NEED TO BE CONNECTED TO TOP=" + node);
3063         graph.addEdge(graph.getHNode(TOPDESC), node);
3064       }
3065
3066     }
3067
3068   }
3069
3070   private void constructHierarchyGraph2() {
3071
3072     // do fixed-point analysis
3073
3074     LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
3075
3076     // Collections.sort(descriptorListToAnalyze, new
3077     // Comparator<MethodDescriptor>() {
3078     // public int compare(MethodDescriptor o1, MethodDescriptor o2) {
3079     // return o1.getSymbol().compareToIgnoreCase(o2.getSymbol());
3080     // }
3081     // });
3082
3083     // current descriptors to visit in fixed-point interprocedural analysis,
3084     // prioritized by dependency in the call graph
3085     methodDescriptorsToVisitStack.clear();
3086
3087     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
3088     methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
3089
3090     while (!descriptorListToAnalyze.isEmpty()) {
3091       MethodDescriptor md = descriptorListToAnalyze.removeFirst();
3092       methodDescriptorsToVisitStack.add(md);
3093     }
3094
3095     // analyze scheduled methods until there are no more to visit
3096     while (!methodDescriptorsToVisitStack.isEmpty()) {
3097       // start to analyze leaf node
3098       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
3099
3100       HierarchyGraph hierarchyGraph = new HierarchyGraph(md);
3101       // MethodSummary methodSummary = new MethodSummary(md);
3102
3103       // MethodLocationInfo methodInfo = new MethodLocationInfo(md);
3104       // curMethodInfo = methodInfo;
3105
3106       System.out.println();
3107       System.out.println("SSJAVA: Construcing the hierarchy graph from " + md);
3108
3109       constructHierarchyGraph(md, hierarchyGraph);
3110
3111       HierarchyGraph prevHierarchyGraph = getHierarchyGraph(md);
3112       // MethodSummary prevMethodSummary = getMethodSummary(md);
3113
3114       if (!hierarchyGraph.equals(prevHierarchyGraph)) {
3115
3116         mapDescriptorToHierarchyGraph.put(md, hierarchyGraph);
3117         // mapDescToLocationSummary.put(md, methodSummary);
3118
3119         // results for callee changed, so enqueue dependents caller for
3120         // further analysis
3121         Iterator<MethodDescriptor> depsItr = ssjava.getDependents(md).iterator();
3122         while (depsItr.hasNext()) {
3123           MethodDescriptor methodNext = depsItr.next();
3124           if (!methodDescriptorsToVisitStack.contains(methodNext)
3125               && methodDescriptorToVistSet.contains(methodNext)) {
3126             methodDescriptorsToVisitStack.add(methodNext);
3127           }
3128         }
3129
3130       }
3131
3132     }
3133
3134     setupToAnalyze();
3135     while (!toAnalyzeIsEmpty()) {
3136       ClassDescriptor cd = toAnalyzeNext();
3137       HierarchyGraph graph = getHierarchyGraph(cd);
3138       for (Iterator iter = cd.getFields(); iter.hasNext();) {
3139         FieldDescriptor fieldDesc = (FieldDescriptor) iter.next();
3140         if (!(fieldDesc.isStatic() && fieldDesc.isFinal())) {
3141           graph.getHNode(fieldDesc);
3142         }
3143       }
3144     }
3145
3146     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
3147     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
3148       Descriptor key = (Descriptor) iterator.next();
3149       HierarchyGraph graph = getHierarchyGraph(key);
3150
3151       Set<HNode> nodeToBeConnected = new HashSet<HNode>();
3152       for (Iterator iterator2 = graph.getNodeSet().iterator(); iterator2.hasNext();) {
3153         HNode node = (HNode) iterator2.next();
3154         if (!node.isSkeleton() && !node.isCombinationNode()) {
3155           if (graph.getIncomingNodeSet(node).size() == 0) {
3156             nodeToBeConnected.add(node);
3157           }
3158         }
3159       }
3160
3161       for (Iterator iterator2 = nodeToBeConnected.iterator(); iterator2.hasNext();) {
3162         HNode node = (HNode) iterator2.next();
3163         // System.out.println("NEED TO BE CONNECTED TO TOP=" + node);
3164         graph.addEdge(graph.getHNode(TOPDESC), node);
3165       }
3166
3167     }
3168
3169   }
3170
3171   private HierarchyGraph getHierarchyGraph(Descriptor d) {
3172     if (!mapDescriptorToHierarchyGraph.containsKey(d)) {
3173       mapDescriptorToHierarchyGraph.put(d, new HierarchyGraph(d));
3174     }
3175     return mapDescriptorToHierarchyGraph.get(d);
3176   }
3177
3178   private void constructHierarchyGraph(MethodDescriptor md, HierarchyGraph methodGraph) {
3179
3180     // visit each node of method flow graph
3181     FlowGraph fg = getFlowGraph(md);
3182     // Set<FlowNode> nodeSet = fg.getNodeSet();
3183
3184     Set<FlowEdge> edgeSet = fg.getEdgeSet();
3185
3186     Set<Descriptor> paramDescSet = fg.getMapParamDescToIdx().keySet();
3187     for (Iterator iterator = paramDescSet.iterator(); iterator.hasNext();) {
3188       Descriptor desc = (Descriptor) iterator.next();
3189       methodGraph.getHNode(desc).setSkeleton(true);
3190     }
3191
3192     // for the method lattice, we need to look at the first element of
3193     // NTuple<Descriptor>
3194     boolean hasGlobalAccess = false;
3195     // for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
3196     // FlowNode originalSrcNode = (FlowNode) iterator.next();
3197     for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) {
3198       FlowEdge edge = (FlowEdge) iterator.next();
3199
3200       FlowNode originalSrcNode = fg.getFlowNode(edge.getInitTuple());
3201       Set<FlowNode> sourceNodeSet = new HashSet<FlowNode>();
3202       if (originalSrcNode instanceof FlowReturnNode) {
3203         FlowReturnNode rnode = (FlowReturnNode) originalSrcNode;
3204         // System.out.println("rnode=" + rnode);
3205         Set<NTuple<Descriptor>> tupleSet = rnode.getReturnTupleSet();
3206         for (Iterator iterator2 = tupleSet.iterator(); iterator2.hasNext();) {
3207           NTuple<Descriptor> nTuple = (NTuple<Descriptor>) iterator2.next();
3208           sourceNodeSet.add(fg.getFlowNode(nTuple));
3209           // System.out.println("&&&SOURCE fg.getFlowNode(nTuple)=" + fg.getFlowNode(nTuple));
3210         }
3211       } else {
3212         sourceNodeSet.add(originalSrcNode);
3213       }
3214
3215       // System.out.println("---sourceNodeSet=" + sourceNodeSet + "  from originalSrcNode="
3216       // + originalSrcNode);
3217
3218       for (Iterator iterator3 = sourceNodeSet.iterator(); iterator3.hasNext();) {
3219         FlowNode srcNode = (FlowNode) iterator3.next();
3220
3221         NTuple<Descriptor> srcNodeTuple = srcNode.getDescTuple();
3222         Descriptor srcLocalDesc = srcNodeTuple.get(0);
3223
3224         if (srcLocalDesc instanceof InterDescriptor
3225             && ((InterDescriptor) srcLocalDesc).getMethodArgIdxPair() != null) {
3226
3227           if (srcNode.getCompositeLocation() == null) {
3228             continue;
3229           }
3230         }
3231
3232         // if the srcNode is started with the global descriptor
3233         // need to set as a skeleton node
3234         if (!hasGlobalAccess && srcNode.getDescTuple().startsWith(GLOBALDESC)) {
3235           System.out.println("SRCNODE=" + srcNode);
3236           hasGlobalAccess = true;
3237         }
3238
3239         // Set<FlowEdge> outEdgeSet = fg.getOutEdgeSet(originalSrcNode);
3240         // for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) {
3241         // FlowEdge outEdge = (FlowEdge) iterator2.next();
3242         // FlowNode originalDstNode = outEdge.getDst();
3243         FlowNode originalDstNode = fg.getFlowNode(edge.getEndTuple());
3244
3245         Set<FlowNode> dstNodeSet = new HashSet<FlowNode>();
3246         if (originalDstNode instanceof FlowReturnNode) {
3247           FlowReturnNode rnode = (FlowReturnNode) originalDstNode;
3248           // System.out.println("\n-returnNode=" + rnode);
3249           Set<NTuple<Descriptor>> tupleSet = rnode.getReturnTupleSet();
3250           for (Iterator iterator4 = tupleSet.iterator(); iterator4.hasNext();) {
3251             NTuple<Descriptor> nTuple = (NTuple<Descriptor>) iterator4.next();
3252             dstNodeSet.add(fg.getFlowNode(nTuple));
3253             // System.out.println("&&&DST fg.getFlowNode(nTuple)=" + fg.getFlowNode(nTuple));
3254           }
3255         } else {
3256           dstNodeSet.add(originalDstNode);
3257         }
3258         // System.out.println("---dstNodeSet=" + dstNodeSet);
3259         for (Iterator iterator4 = dstNodeSet.iterator(); iterator4.hasNext();) {
3260           FlowNode dstNode = (FlowNode) iterator4.next();
3261
3262           NTuple<Descriptor> dstNodeTuple = dstNode.getDescTuple();
3263           Descriptor dstLocalDesc = dstNodeTuple.get(0);
3264
3265           if (dstLocalDesc instanceof InterDescriptor
3266               && ((InterDescriptor) dstLocalDesc).getMethodArgIdxPair() != null) {
3267             if (dstNode.getCompositeLocation() == null) {
3268               // System.out.println("%%%%%%%%%%%%%SKIP=" + dstNode);
3269               continue;
3270             }
3271           }
3272
3273           // if (outEdge.getInitTuple().equals(srcNodeTuple)
3274           // && outEdge.getEndTuple().equals(dstNodeTuple)) {
3275
3276           NTuple<Descriptor> srcCurTuple = srcNode.getCurrentDescTuple();
3277           NTuple<Descriptor> dstCurTuple = dstNode.getCurrentDescTuple();
3278
3279           // //////////////////////////
3280           // inheritance check
3281           if (mapMethodDescToHighestOverriddenMethodDesc.containsKey(md)) {
3282
3283             MethodDescriptor highestOverriddenMethodDesc =
3284                 mapMethodDescToHighestOverriddenMethodDesc.get(md);
3285
3286             if (srcCurTuple.get(srcCurTuple.size() - 1).getSymbol().startsWith(PCLOC)) {
3287             }
3288
3289           }
3290           // //////////////////////////
3291
3292           // System.out.println("-srcCurTuple=" + srcCurTuple + "  dstCurTuple=" + dstCurTuple
3293           // + "  srcNode=" + srcNode + "   dstNode=" + dstNode);
3294
3295           // srcCurTuple = translateBaseTuple(srcNode, srcCurTuple);
3296           // dstCurTuple = translateBaseTuple(dstNode, dstCurTuple);
3297
3298           if ((srcCurTuple.size() > 1 && dstCurTuple.size() > 1)
3299               && srcCurTuple.get(0).equals(dstCurTuple.get(0))) {
3300
3301             // value flows between fields
3302             Descriptor desc = srcCurTuple.get(0);
3303             ClassDescriptor classDesc;
3304
3305             if (desc.equals(GLOBALDESC)) {
3306               classDesc = md.getClassDesc();
3307             } else {
3308               VarDescriptor varDesc = (VarDescriptor) srcCurTuple.get(0);
3309               classDesc = varDesc.getType().getClassDesc();
3310             }
3311             extractFlowsBetweenFields(classDesc, srcNode, dstNode, 1);
3312
3313           } else if ((srcCurTuple.size() == 1 && dstCurTuple.size() == 1)
3314               || ((srcCurTuple.size() > 1 || dstCurTuple.size() > 1) && !srcCurTuple.get(0).equals(
3315                   dstCurTuple.get(0)))) {
3316
3317             // value flow between a primitive local var - a primitive local var or local var -
3318             // field
3319
3320             Descriptor srcDesc = srcCurTuple.get(0);
3321             Descriptor dstDesc = dstCurTuple.get(0);
3322
3323             methodGraph.addEdge(srcDesc, dstDesc);
3324
3325             if (fg.isParamDesc(srcDesc)) {
3326               methodGraph.setParamHNode(srcDesc);
3327             }
3328             if (fg.isParamDesc(dstDesc)) {
3329               methodGraph.setParamHNode(dstDesc);
3330             }
3331
3332           }
3333
3334           // }
3335           // }
3336
3337         }
3338
3339       }
3340
3341     }
3342
3343     // If the method accesses static fields
3344     // set hasGloabalAccess true in the method summary.
3345     if (hasGlobalAccess) {
3346       getMethodSummary(md).setHasGlobalAccess();
3347       methodGraph.getHNode(GLOBALDESC).setSkeleton(true);
3348     }
3349
3350     if (ssjava.getMethodContainingSSJavaLoop().equals(md)) {
3351       // if the current method contains the event loop
3352       // we need to set all nodes of the hierarchy graph as a skeleton node
3353       Set<HNode> hnodeSet = methodGraph.getNodeSet();
3354       for (Iterator iterator = hnodeSet.iterator(); iterator.hasNext();) {
3355         HNode hnode = (HNode) iterator.next();
3356         hnode.setSkeleton(true);
3357       }
3358     }
3359
3360   }
3361
3362   private NTuple<Descriptor> translateBaseTuple(FlowNode flowNode, NTuple<Descriptor> inTuple) {
3363
3364     if (flowNode.getBaseTuple() != null) {
3365
3366       NTuple<Descriptor> translatedTuple = new NTuple<Descriptor>();
3367
3368       NTuple<Descriptor> baseTuple = flowNode.getBaseTuple();
3369
3370       for (int i = 0; i < baseTuple.size(); i++) {
3371         translatedTuple.add(baseTuple.get(i));
3372       }
3373
3374       for (int i = 1; i < inTuple.size(); i++) {
3375         translatedTuple.add(inTuple.get(i));
3376       }
3377
3378       // System.out.println("------TRANSLATED " + inTuple + " -> " + translatedTuple);
3379       return translatedTuple;
3380
3381     } else {
3382       return inTuple;
3383     }
3384
3385   }
3386
3387   private MethodSummary getMethodSummary(MethodDescriptor md) {
3388     if (!mapDescToLocationSummary.containsKey(md)) {
3389       mapDescToLocationSummary.put(md, new MethodSummary(md));
3390     }
3391     return (MethodSummary) mapDescToLocationSummary.get(md);
3392   }
3393
3394   private void addMapClassDefinitionToLineNum(ClassDescriptor cd, String strLine, int lineNum) {
3395
3396     String classSymbol = cd.getSymbol();
3397     int idx = classSymbol.lastIndexOf("$");
3398     if (idx != -1) {
3399       classSymbol = classSymbol.substring(idx + 1);
3400     }
3401
3402     String pattern = "class " + classSymbol + " ";
3403     if (strLine.indexOf(pattern) != -1) {
3404       mapDescToDefinitionLine.put(cd, lineNum);
3405     }
3406   }
3407
3408   private void addMapMethodDefinitionToLineNum(Set<MethodDescriptor> methodSet, String strLine,
3409       int lineNum) {
3410     for (Iterator iterator = methodSet.iterator(); iterator.hasNext();) {
3411       MethodDescriptor md = (MethodDescriptor) iterator.next();
3412       String pattern = md.getMethodDeclaration();
3413       if (strLine.indexOf(pattern) != -1) {
3414         mapDescToDefinitionLine.put(md, lineNum);
3415         methodSet.remove(md);
3416         return;
3417       }
3418     }
3419
3420   }
3421
3422   private void readOriginalSourceFiles() {
3423
3424     SymbolTable classtable = state.getClassSymbolTable();
3425
3426     Set<ClassDescriptor> classDescSet = new HashSet<ClassDescriptor>();
3427     classDescSet.addAll(classtable.getValueSet());
3428
3429     try {
3430       // inefficient implement. it may re-visit the same file if the file
3431       // contains more than one class definitions.
3432       for (Iterator iterator = classDescSet.iterator(); iterator.hasNext();) {
3433         ClassDescriptor cd = (ClassDescriptor) iterator.next();
3434
3435         Set<MethodDescriptor> methodSet = new HashSet<MethodDescriptor>();
3436         methodSet.addAll(cd.getMethodTable().getValueSet());
3437
3438         String sourceFileName = cd.getSourceFileName();
3439         Vector<String> lineVec = new Vector<String>();
3440
3441         mapFileNameToLineVector.put(sourceFileName, lineVec);
3442
3443         BufferedReader in = new BufferedReader(new FileReader(sourceFileName));
3444         String strLine;
3445         int lineNum = 1;
3446         lineVec.add(""); // the index is started from 1.
3447         while ((strLine = in.readLine()) != null) {
3448           lineVec.add(lineNum, strLine);
3449           addMapClassDefinitionToLineNum(cd, strLine, lineNum);
3450           addMapMethodDefinitionToLineNum(methodSet, strLine, lineNum);
3451           lineNum++;
3452         }
3453
3454       }
3455
3456     } catch (IOException e) {
3457       e.printStackTrace();
3458     }
3459
3460   }
3461
3462   private String generateLatticeDefinition(Descriptor desc) {
3463
3464     Set<String> sharedLocSet = new HashSet<String>();
3465
3466     SSJavaLattice<String> lattice = getLattice(desc);
3467     String rtr = "@LATTICE(\"";
3468
3469     Map<String, Set<String>> map = lattice.getTable();
3470     Set<String> keySet = map.keySet();
3471
3472     // System.out.println("@generateLatticeDefinition=" + desc + "      map=" + map);
3473
3474     boolean first = true;
3475     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
3476       String key = (String) iterator.next();
3477       if (!key.equals(lattice.getTopItem())) {
3478         Set<String> connectedSet = map.get(key);
3479
3480         if (connectedSet.size() == 1) {
3481           if (connectedSet.iterator().next().equals(lattice.getBottomItem())) {
3482             if (!first) {
3483               rtr += ",";
3484             } else {
3485               rtr += "LOC,";
3486               first = false;
3487             }
3488             rtr += key;
3489             if (lattice.isSharedLoc(key)) {
3490               rtr += "," + key + "*";
3491             }
3492           }
3493         }
3494
3495         for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) {
3496           String loc = (String) iterator2.next();
3497           if (!loc.equals(lattice.getBottomItem())) {
3498             if (!first) {
3499               rtr += ",";
3500             } else {
3501               rtr += "LOC,";
3502               first = false;
3503             }
3504             rtr += loc + "<" + key;
3505             if (lattice.isSharedLoc(key) && (!sharedLocSet.contains(key))) {
3506               rtr += "," + key + "*";
3507               sharedLocSet.add(key);
3508             }
3509             if (lattice.isSharedLoc(loc) && (!sharedLocSet.contains(loc))) {
3510               rtr += "," + loc + "*";
3511               sharedLocSet.add(loc);
3512             }
3513
3514           }
3515         }
3516       }
3517     }
3518
3519     if (desc instanceof MethodDescriptor) {
3520       // System.out.println("#EXTRA LOC DECLARATION GEN=" + desc);
3521
3522       MethodDescriptor md = (MethodDescriptor) desc;
3523       MethodSummary methodSummary = getMethodSummary(md);
3524
3525       TypeDescriptor returnType = ((MethodDescriptor) desc).getReturnType();
3526       if (!ssjava.getMethodContainingSSJavaLoop().equals(desc) && returnType != null
3527           && (!returnType.isVoid())) {
3528         CompositeLocation returnLoc = methodSummary.getRETURNLoc();
3529         if (returnLoc.getSize() == 1) {
3530           String returnLocStr = generateLocationAnnoatation(methodSummary.getRETURNLoc());
3531           if (rtr.indexOf(returnLocStr) == -1) {
3532             rtr += "," + returnLocStr;
3533           }
3534         }
3535       }
3536       rtr += "\")";
3537
3538       if (!ssjava.getMethodContainingSSJavaLoop().equals(desc)) {
3539         if (returnType != null && (!returnType.isVoid())) {
3540           rtr +=
3541               "\n@RETURNLOC(\"" + generateLocationAnnoatation(methodSummary.getRETURNLoc()) + "\")";
3542         }
3543
3544         CompositeLocation pcLoc = methodSummary.getPCLoc();
3545         if ((pcLoc != null) && (!pcLoc.get(0).isTop())) {
3546           rtr += "\n@PCLOC(\"" + generateLocationAnnoatation(pcLoc) + "\")";
3547         }
3548       }
3549
3550       if (!md.isStatic()) {
3551         rtr += "\n@THISLOC(\"" + methodSummary.getThisLocName() + "\")";
3552       }
3553       rtr += "\n@GLOBALLOC(\"" + methodSummary.getGlobalLocName() + "\")";
3554
3555     } else {
3556       rtr += "\")";
3557     }
3558
3559     return rtr;
3560   }
3561
3562   private void generateAnnoatedCode() {
3563
3564     readOriginalSourceFiles();
3565
3566     setupToAnalyze();
3567     while (!toAnalyzeIsEmpty()) {
3568       ClassDescriptor cd = toAnalyzeNext();
3569
3570       setupToAnalazeMethod(cd);
3571
3572       String sourceFileName = cd.getSourceFileName();
3573
3574       if (cd.isInterface()) {
3575         continue;
3576       }
3577
3578       int classDefLine = mapDescToDefinitionLine.get(cd);
3579       Vector<String> sourceVec = mapFileNameToLineVector.get(sourceFileName);
3580
3581       LocationSummary fieldLocSummary = getLocationSummary(cd);
3582
3583       String fieldLatticeDefStr = generateLatticeDefinition(cd);
3584       String annoatedSrc = fieldLatticeDefStr + newline + sourceVec.get(classDefLine);
3585       sourceVec.set(classDefLine, annoatedSrc);
3586
3587       // generate annotations for field declarations
3588       // Map<Descriptor, CompositeLocation> inferLocMap = fieldLocInfo.getMapDescToInferLocation();
3589       Map<String, String> mapFieldNameToLocName = fieldLocSummary.getMapHNodeNameToLocationName();
3590
3591       for (Iterator iter = cd.getFields(); iter.hasNext();) {
3592         FieldDescriptor fd = (FieldDescriptor) iter.next();
3593
3594         String locAnnotationStr;
3595         // CompositeLocation inferLoc = inferLocMap.get(fd);
3596         String locName = mapFieldNameToLocName.get(fd.getSymbol());
3597
3598         if (locName != null) {
3599           // infer loc is null if the corresponding field is static and final
3600           // locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")";
3601           locAnnotationStr = "@LOC(\"" + locName + "\")";
3602           int fdLineNum = fd.getLineNum();
3603           String orgFieldDeclarationStr = sourceVec.get(fdLineNum);
3604           String fieldDeclaration = fd.toString();
3605           fieldDeclaration = fieldDeclaration.substring(0, fieldDeclaration.length() - 1);
3606           String annoatedStr = locAnnotationStr + " " + orgFieldDeclarationStr;
3607           sourceVec.set(fdLineNum, annoatedStr);
3608         }
3609
3610       }
3611
3612       while (!toAnalyzeMethodIsEmpty()) {
3613         MethodDescriptor md = toAnalyzeMethodNext();
3614
3615         if (!ssjava.needTobeAnnotated(md)) {
3616           continue;
3617         }
3618
3619         SSJavaLattice<String> methodLattice = md2lattice.get(md);
3620         // System.out.println("md=" + md + " methodLattice=" + methodLattice);
3621         if (methodLattice != null) {
3622
3623           int methodDefLine = md.getLineNum();
3624
3625           // MethodLocationInfo methodLocInfo = getMethodLocationInfo(md);
3626           // Map<Descriptor, CompositeLocation> methodInferLocMap =
3627           // methodLocInfo.getMapDescToInferLocation();
3628
3629           MethodSummary methodSummary = getMethodSummary(md);
3630
3631           Map<Descriptor, CompositeLocation> mapVarDescToInferLoc =
3632               methodSummary.getMapVarDescToInferCompositeLocation();
3633           // System.out.println("-----md=" + md + " methodDefLine=" + methodDefLine);
3634           // System.out.println("-----mapVarDescToInferLoc=" + mapVarDescToInferLoc);
3635
3636           Set<Descriptor> localVarDescSet = mapVarDescToInferLoc.keySet();
3637
3638           Set<String> localLocElementSet = methodLattice.getElementSet();
3639
3640           for (Iterator iterator = localVarDescSet.iterator(); iterator.hasNext();) {
3641             Descriptor localVarDesc = (Descriptor) iterator.next();
3642             // System.out.println("-------localVarDesc=" + localVarDesc);
3643             CompositeLocation inferLoc = mapVarDescToInferLoc.get(localVarDesc);
3644
3645             String localLocIdentifier = inferLoc.get(0).getLocIdentifier();
3646             if (!localLocElementSet.contains(localLocIdentifier)) {
3647               methodLattice.put(localLocIdentifier);
3648             }
3649
3650             String locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")";
3651
3652             if (!isParameter(md, localVarDesc)) {
3653               if (mapDescToDefinitionLine.containsKey(localVarDesc)) {
3654                 int varLineNum = mapDescToDefinitionLine.get(localVarDesc);
3655                 String orgSourceLine = sourceVec.get(varLineNum);
3656                 // System.out.println("varLineNum=" + varLineNum + "  org src=" + orgSourceLine);
3657                 int idx =
3658                     orgSourceLine.indexOf(generateVarDeclaration((VarDescriptor) localVarDesc));
3659                 // System.out.println("idx=" + idx
3660                 // + "  generateVarDeclaration((VarDescriptor) localVarDesc)="
3661                 // + generateVarDeclaration((VarDescriptor) localVarDesc));
3662                 assert (idx != -1);
3663                 String annoatedStr =
3664                     orgSourceLine.substring(0, idx) + locAnnotationStr + " "
3665                         + orgSourceLine.substring(idx);
3666                 sourceVec.set(varLineNum, annoatedStr);
3667               }
3668             } else {
3669               String methodDefStr = sourceVec.get(methodDefLine);
3670
3671               int idx =
3672                   getParamLocation(methodDefStr,
3673                       generateVarDeclaration((VarDescriptor) localVarDesc));
3674               // System.out.println("methodDefStr=" + methodDefStr + " localVarDesc=" + localVarDesc
3675               // + " idx=" + idx);
3676               assert (idx != -1);
3677
3678               String annoatedStr =
3679                   methodDefStr.substring(0, idx) + locAnnotationStr + " "
3680                       + methodDefStr.substring(idx);
3681               sourceVec.set(methodDefLine, annoatedStr);
3682             }
3683
3684           }
3685
3686           // check if the lattice has to have the location type for the this
3687           // reference...
3688
3689           // boolean needToAddthisRef = hasThisReference(md);
3690           // if (localLocElementSet.contains("this")) {
3691           // methodLattice.put("this");
3692           // }
3693
3694           String methodLatticeDefStr = generateLatticeDefinition(md);
3695           String annoatedStr = methodLatticeDefStr + newline + sourceVec.get(methodDefLine);
3696           sourceVec.set(methodDefLine, annoatedStr);
3697
3698         }
3699       }
3700
3701     }
3702
3703     codeGen();
3704   }
3705
3706   private boolean hasThisReference(MethodDescriptor md) {
3707
3708     FlowGraph fg = getFlowGraph(md);
3709     Set<FlowNode> nodeSet = fg.getNodeSet();
3710     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
3711       FlowNode flowNode = (FlowNode) iterator.next();
3712       if (flowNode.getDescTuple().get(0).equals(md.getThis())) {
3713         return true;
3714       }
3715     }
3716
3717     return false;
3718   }
3719
3720   private int getParamLocation(String methodStr, String paramStr) {
3721
3722     String pattern = paramStr + ",";
3723
3724     int idx = methodStr.indexOf(pattern);
3725     if (idx != -1) {
3726       return idx;
3727     } else {
3728       pattern = paramStr + ")";
3729       return methodStr.indexOf(pattern);
3730     }
3731
3732   }
3733
3734   private String generateVarDeclaration(VarDescriptor varDesc) {
3735
3736     TypeDescriptor td = varDesc.getType();
3737     String rtr = td.toString();
3738     if (td.isArray()) {
3739       for (int i = 0; i < td.getArrayCount(); i++) {
3740         rtr += "[]";
3741       }
3742     }
3743     rtr += " " + varDesc.getName();
3744     return rtr;
3745
3746   }
3747
3748   private String generateLocationAnnoatation(CompositeLocation loc) {
3749     String rtr = "";
3750     // method location
3751     Location methodLoc = loc.get(0);
3752     rtr += methodLoc.getLocIdentifier();
3753
3754     for (int i = 1; i < loc.getSize(); i++) {
3755       Location element = loc.get(i);
3756       rtr += "," + element.getDescriptor().getSymbol() + "." + element.getLocIdentifier();
3757     }
3758
3759     return rtr;
3760   }
3761
3762   private boolean isParameter(MethodDescriptor md, Descriptor localVarDesc) {
3763     return getFlowGraph(md).isParamDesc(localVarDesc);
3764   }
3765
3766   private String extractFileName(String fileName) {
3767     int idx = fileName.lastIndexOf("/");
3768     if (idx == -1) {
3769       return fileName;
3770     } else {
3771       return fileName.substring(idx + 1);
3772     }
3773
3774   }
3775
3776   private void codeGen() {
3777
3778     Set<String> originalFileNameSet = mapFileNameToLineVector.keySet();
3779     for (Iterator iterator = originalFileNameSet.iterator(); iterator.hasNext();) {
3780       String orgFileName = (String) iterator.next();
3781       String outputFileName = extractFileName(orgFileName);
3782
3783       Vector<String> sourceVec = mapFileNameToLineVector.get(orgFileName);
3784
3785       try {
3786
3787         FileWriter fileWriter = new FileWriter("./infer/" + outputFileName);
3788         BufferedWriter out = new BufferedWriter(fileWriter);
3789
3790         for (int i = 0; i < sourceVec.size(); i++) {
3791           out.write(sourceVec.get(i));
3792           out.newLine();
3793         }
3794         out.close();
3795       } catch (IOException e) {
3796         e.printStackTrace();
3797       }
3798
3799     }
3800
3801   }
3802
3803   private void checkLattices() {
3804
3805     LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
3806
3807     // current descriptors to visit in fixed-point interprocedural analysis,
3808     // prioritized by
3809     // dependency in the call graph
3810     methodDescriptorsToVisitStack.clear();
3811
3812     // descriptorListToAnalyze.removeFirst();
3813
3814     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
3815     methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
3816
3817     while (!descriptorListToAnalyze.isEmpty()) {
3818       MethodDescriptor md = descriptorListToAnalyze.removeFirst();
3819       checkLatticesOfVirtualMethods(md);
3820     }
3821
3822   }
3823
3824   private void debug_writeLatticeDotFile() {
3825     // generate lattice dot file
3826
3827     setupToAnalyze();
3828
3829     while (!toAnalyzeIsEmpty()) {
3830       ClassDescriptor cd = toAnalyzeNext();
3831
3832       setupToAnalazeMethod(cd);
3833
3834       SSJavaLattice<String> classLattice = cd2lattice.get(cd);
3835       if (classLattice != null) {
3836         ssjava.writeLatticeDotFile(cd, null, classLattice);
3837         // debug_printDescriptorToLocNameMapping(cd);
3838       }
3839
3840       while (!toAnalyzeMethodIsEmpty()) {
3841         MethodDescriptor md = toAnalyzeMethodNext();
3842         SSJavaLattice<String> methodLattice = md2lattice.get(md);
3843         if (methodLattice != null) {
3844           ssjava.writeLatticeDotFile(cd, md, methodLattice);
3845           // debug_printDescriptorToLocNameMapping(md);
3846         }
3847       }
3848     }
3849
3850   }
3851
3852   private void debug_printDescriptorToLocNameMapping(Descriptor desc) {
3853
3854     LocationInfo info = getLocationInfo(desc);
3855     System.out.println("## " + desc + " ##");
3856     System.out.println(info.getMapDescToInferLocation());
3857     LocationInfo locInfo = getLocationInfo(desc);
3858     System.out.println("mapping=" + locInfo.getMapLocSymbolToDescSet());
3859     System.out.println("###################");
3860
3861   }
3862
3863   private void calculateExtraLocations() {
3864
3865     // LinkedList<MethodDescriptor> methodDescList = ssjava.getSortedDescriptors();
3866     LinkedList<MethodDescriptor> methodDescList =
3867         (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
3868     for (Iterator iterator = methodDescList.iterator(); iterator.hasNext();) {
3869       MethodDescriptor md = (MethodDescriptor) iterator.next();
3870       if (!ssjava.getMethodContainingSSJavaLoop().equals(md)) {
3871         calculateExtraLocations(md);
3872       }
3873     }
3874
3875   }
3876
3877   private void checkLatticesOfVirtualMethods(MethodDescriptor md) {
3878
3879     if (!md.isStatic()) {
3880       Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
3881       setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md));
3882
3883       for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
3884         MethodDescriptor mdCallee = (MethodDescriptor) iterator.next();
3885         if (!md.equals(mdCallee)) {
3886           checkConsistency(md, mdCallee);
3887         }
3888       }
3889
3890     }
3891
3892   }
3893
3894   private void checkConsistency(MethodDescriptor md1, MethodDescriptor md2) {
3895
3896     // check that two lattice have the same relations between parameters(+PC
3897     // LOC, GLOBAL_LOC RETURN LOC)
3898
3899     List<CompositeLocation> list1 = new ArrayList<CompositeLocation>();
3900     List<CompositeLocation> list2 = new ArrayList<CompositeLocation>();
3901
3902     MethodLocationInfo locInfo1 = getMethodLocationInfo(md1);
3903     MethodLocationInfo locInfo2 = getMethodLocationInfo(md2);
3904
3905     Map<Integer, CompositeLocation> paramMap1 = locInfo1.getMapParamIdxToInferLoc();
3906     Map<Integer, CompositeLocation> paramMap2 = locInfo2.getMapParamIdxToInferLoc();
3907
3908     int numParam = locInfo1.getMapParamIdxToInferLoc().keySet().size();
3909
3910     // add location types of paramters
3911     for (int idx = 0; idx < numParam; idx++) {
3912       list1.add(paramMap1.get(Integer.valueOf(idx)));
3913       list2.add(paramMap2.get(Integer.valueOf(idx)));
3914     }
3915
3916     // add program counter location
3917     list1.add(locInfo1.getPCLoc());
3918     list2.add(locInfo2.getPCLoc());
3919
3920     if (!md1.getReturnType().isVoid()) {
3921       // add return value location
3922       CompositeLocation rtrLoc1 = getMethodLocationInfo(md1).getReturnLoc();
3923       CompositeLocation rtrLoc2 = getMethodLocationInfo(md2).getReturnLoc();
3924       list1.add(rtrLoc1);
3925       list2.add(rtrLoc2);
3926     }
3927
3928     // add global location type
3929     if (md1.isStatic()) {
3930       CompositeLocation globalLoc1 =
3931           new CompositeLocation(new Location(md1, locInfo1.getGlobalLocName()));
3932       CompositeLocation globalLoc2 =
3933           new CompositeLocation(new Location(md2, locInfo2.getGlobalLocName()));
3934       list1.add(globalLoc1);
3935       list2.add(globalLoc2);
3936     }
3937
3938     for (int i = 0; i < list1.size(); i++) {
3939       CompositeLocation locA1 = list1.get(i);
3940       CompositeLocation locA2 = list2.get(i);
3941       for (int k = 0; k < list1.size(); k++) {
3942         if (i != k) {
3943           CompositeLocation locB1 = list1.get(k);
3944           CompositeLocation locB2 = list2.get(k);
3945           boolean r1 = isGreaterThan(getLattice(md1), locA1, locB1);
3946
3947           boolean r2 = isGreaterThan(getLattice(md1), locA2, locB2);
3948
3949           if (r1 != r2) {
3950             throw new Error("The method " + md1 + " is not consistent with the method " + md2
3951                 + ".:: They have a different ordering relation between locations (" + locA1 + ","
3952                 + locB1 + ") and (" + locA2 + "," + locB2 + ").");
3953           }
3954         }
3955       }
3956     }
3957
3958   }
3959
3960   private String getSymbol(int idx, FlowNode node) {
3961     Descriptor desc = node.getDescTuple().get(idx);
3962     return desc.getSymbol();
3963   }
3964
3965   private Descriptor getDescriptor(int idx, FlowNode node) {
3966     Descriptor desc = node.getDescTuple().get(idx);
3967     return desc;
3968   }
3969
3970   private void calculatePCLOC(MethodDescriptor md) {
3971
3972     // System.out.println("#CalculatePCLOC");
3973     MethodSummary methodSummary = getMethodSummary(md);
3974     FlowGraph fg = getFlowGraph(md);
3975     Map<Integer, CompositeLocation> mapParamToLoc = methodSummary.getMapParamIdxToInferLoc();
3976
3977     // calculate the initial program counter location
3978     // PC location is higher than location types of parameters which has incoming flows.
3979
3980     Set<NTuple<Location>> paramLocTupleHavingInFlowSet = new HashSet<NTuple<Location>>();
3981     Set<Descriptor> paramDescNOTHavingInFlowSet = new HashSet<Descriptor>();
3982     // Set<FlowNode> paramNodeNOThavingInFlowSet = new HashSet<FlowNode>();
3983
3984     int numParams = fg.getNumParameters();
3985     for (int i = 0; i < numParams; i++) {
3986       FlowNode paramFlowNode = fg.getParamFlowNode(i);
3987       Descriptor prefix = paramFlowNode.getDescTuple().get(0);
3988       NTuple<Descriptor> paramDescTuple = paramFlowNode.getCurrentDescTuple();
3989       NTuple<Location> paramLocTuple = translateToLocTuple(md, paramDescTuple);
3990
3991       Set<FlowNode> inNodeToParamSet = fg.getIncomingNodeSetByPrefix(prefix);
3992       if (inNodeToParamSet.size() > 0) {
3993         // parameter has in-value flows
3994
3995         for (Iterator iterator = inNodeToParamSet.iterator(); iterator.hasNext();) {
3996           FlowNode inNode = (FlowNode) iterator.next();
3997           Set<FlowEdge> outEdgeSet = fg.getOutEdgeSet(inNode);
3998           for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) {
3999             FlowEdge flowEdge = (FlowEdge) iterator2.next();
4000             if (flowEdge.getEndTuple().startsWith(prefix)) {
4001               NTuple<Location> paramLocTupleWithIncomingFlow =
4002                   translateToLocTuple(md, flowEdge.getEndTuple());
4003               paramLocTupleHavingInFlowSet.add(paramLocTupleWithIncomingFlow);
4004             }
4005           }
4006         }
4007
4008         // paramLocTupleHavingInFlowSet.add(paramLocTuple);
4009       } else {
4010         // paramNodeNOThavingInFlowSet.add(fg.getFlowNode(paramDescTuple));
4011         paramDescNOTHavingInFlowSet.add(prefix);
4012       }
4013     }
4014
4015     // System.out.println("paramLocTupleHavingInFlowSet=" + paramLocTupleHavingInFlowSet);
4016
4017     if (paramLocTupleHavingInFlowSet.size() > 0
4018         && !coversAllParamters(md, fg, paramLocTupleHavingInFlowSet)) {
4019
4020       // Here, generates a location in the method lattice that is higher than the
4021       // paramLocTupleHavingInFlowSet
4022       NTuple<Location> pcLocTuple =
4023           generateLocTupleRelativeTo(md, paramLocTupleHavingInFlowSet, PCLOC);
4024
4025       NTuple<Descriptor> pcDescTuple = translateToDescTuple(pcLocTuple);
4026
4027       // System.out.println("pcLoc=" + pcLocTuple);
4028
4029       CompositeLocation curPCLoc = methodSummary.getPCLoc();
4030       if (curPCLoc.get(0).isTop() || pcLocTuple.size() > curPCLoc.getSize()) {
4031         methodSummary.setPCLoc(new CompositeLocation(pcLocTuple));
4032
4033         Set<FlowNode> flowNodeLowerthanPCLocSet = new HashSet<FlowNode>();
4034         GlobalFlowGraph subGlobalFlowGraph = getSubGlobalFlowGraph(md);
4035         // add ordering relations s.t. PCLOC is higher than all flow nodes except the set of
4036         // parameters that do not have incoming flows
4037         for (Iterator iterator = fg.getNodeSet().iterator(); iterator.hasNext();) {
4038           FlowNode node = (FlowNode) iterator.next();
4039
4040           if (!(node instanceof FlowReturnNode)) {
4041             if (!paramDescNOTHavingInFlowSet.contains(node.getCurrentDescTuple().get(0))) {
4042               flowNodeLowerthanPCLocSet.add(node);
4043               fg.addValueFlowEdge(pcDescTuple, node.getDescTuple());
4044
4045               subGlobalFlowGraph.addValueFlowEdge(pcLocTuple,
4046                   translateToLocTuple(md, node.getDescTuple()));
4047             }
4048           } else {
4049             // System.out.println("***SKIP PCLOC -> RETURNLOC=" + node);
4050           }
4051
4052         }
4053         fg.getFlowNode(translateToDescTuple(pcLocTuple)).setSkeleton(true);
4054
4055         if (pcLocTuple.get(0).getLocDescriptor().equals(md.getThis())) {
4056           for (Iterator iterator = flowNodeLowerthanPCLocSet.iterator(); iterator.hasNext();) {
4057             FlowNode lowerNode = (FlowNode) iterator.next();
4058             if (lowerNode.getDescTuple().size() == 1 && lowerNode.getCompositeLocation() == null) {
4059               NTuple<Location> lowerLocTuple = translateToLocTuple(md, lowerNode.getDescTuple());
4060               CompositeLocation newComp =
4061                   calculateCompositeLocationFromSubGlobalGraph(md, lowerNode);
4062               if (newComp != null) {
4063                 subGlobalFlowGraph.addMapLocationToInferCompositeLocation(lowerLocTuple.get(0),
4064                     newComp);
4065                 lowerNode.setCompositeLocation(newComp);
4066                 // System.out.println("NEW COMP LOC=" + newComp + "    to lowerNode=" + lowerNode);
4067               }
4068
4069             }
4070
4071           }
4072         }
4073
4074       }
4075
4076     }
4077   }
4078
4079   private int countFirstDescriptorSetSize(Set<NTuple<Location>> set) {
4080
4081     Set<Descriptor> descSet = new HashSet<Descriptor>();
4082
4083     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
4084       NTuple<Location> locTuple = (NTuple<Location>) iterator.next();
4085       descSet.add(locTuple.get(0).getLocDescriptor());
4086     }
4087
4088     return descSet.size();
4089   }
4090
4091   private boolean coversAllParamters(MethodDescriptor md, FlowGraph fg,
4092       Set<NTuple<Location>> paramLocTupleHavingInFlowSet) {
4093
4094     int numParam = fg.getNumParameters();
4095     // int size = paramLocTupleHavingInFlowSet.size();
4096     int size = countFirstDescriptorSetSize(paramLocTupleHavingInFlowSet);
4097
4098     // System.out.println("numParam=" + numParam + "     size=" + size);
4099
4100     // if (!md.isStatic()) {
4101     //
4102     // // if the method is not static && there is a parameter composite location &&
4103     // // it is started with 'this',
4104     // // paramLocTupleHavingInFlowSet need to have 'this' parameter.
4105     //
4106     // FlowNode thisParamNode = fg.getParamFlowNode(0);
4107     // NTuple<Location> thisParamLocTuple =
4108     // translateToLocTuple(md, thisParamNode.getCurrentDescTuple());
4109     //
4110     // if (!paramLocTupleHavingInFlowSet.contains(thisParamLocTuple)) {
4111     //
4112     // for (Iterator iterator = paramLocTupleHavingInFlowSet.iterator(); iterator.hasNext();) {
4113     // NTuple<Location> paramTuple = (NTuple<Location>) iterator.next();
4114     // if (paramTuple.size() > 1 && paramTuple.get(0).getLocDescriptor().equals(md.getThis())) {
4115     // // paramLocTupleHavingInFlowSet.add(thisParamLocTuple);
4116     // // break;
4117     // size++;
4118     // }
4119     // }
4120     //
4121     // }
4122     // }
4123
4124     if (size == numParam) {
4125       return true;
4126     } else {
4127       return false;
4128     }
4129
4130   }
4131
4132   private void calculateRETURNLOC(MethodDescriptor md) {
4133
4134     // System.out.println("#calculateRETURNLOC= " + md);
4135
4136     // calculate a return location:
4137     // the return location type is lower than all parameters and the location of return values
4138     MethodSummary methodSummary = getMethodSummary(md);
4139     // if (methodSummary.getRETURNLoc() != null) {
4140     // System.out.println("$HERE?");
4141     // return;
4142     // }
4143
4144     FlowGraph fg = getFlowGraph(md);
4145     Map<Integer, CompositeLocation> mapParamToLoc = methodSummary.getMapParamIdxToInferLoc();
4146     Set<Integer> paramIdxSet = mapParamToLoc.keySet();
4147
4148     if (md.getReturnType() != null && !md.getReturnType().isVoid()) {
4149       // first, generate the set of return value location types that starts
4150       // with 'this' reference
4151
4152       Set<FlowNode> paramFlowNodeFlowingToReturnValueSet = getParamNodeFlowingToReturnValue(md);
4153       // System.out.println("paramFlowNodeFlowingToReturnValueSet="
4154       // + paramFlowNodeFlowingToReturnValueSet);
4155
4156       Set<NTuple<Location>> tupleToBeHigherThanReturnLocSet = new HashSet<NTuple<Location>>();
4157       for (Iterator iterator = paramFlowNodeFlowingToReturnValueSet.iterator(); iterator.hasNext();) {
4158         FlowNode fn = (FlowNode) iterator.next();
4159         NTuple<Descriptor> paramDescTuple = fn.getCurrentDescTuple();
4160         tupleToBeHigherThanReturnLocSet.add(translateToLocTuple(md, paramDescTuple));
4161       }
4162
4163       Set<FlowNode> returnNodeSet = fg.getReturnNodeSet();
4164       for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
4165         FlowNode returnNode = (FlowNode) iterator.next();
4166         NTuple<Descriptor> returnDescTuple = returnNode.getCurrentDescTuple();
4167         tupleToBeHigherThanReturnLocSet.add(translateToLocTuple(md, returnDescTuple));
4168       }
4169       // System.out.println("-flow graph's returnNodeSet=" + returnNodeSet);
4170       // System.out.println("tupleSetToBeHigherThanReturnLoc=" + tupleToBeHigherThanReturnLocSet);
4171
4172       // Here, generates a return location in the method lattice that is lower than the
4173       // locFlowingToReturnValueSet
4174       NTuple<Location> returnLocTuple =
4175           generateLocTupleRelativeTo(md, tupleToBeHigherThanReturnLocSet, RLOC);
4176
4177       // System.out.println("returnLocTuple=" + returnLocTuple);
4178       NTuple<Descriptor> returnDescTuple = translateToDescTuple(returnLocTuple);
4179       CompositeLocation curReturnLoc = methodSummary.getRETURNLoc();
4180       if (curReturnLoc == null || returnDescTuple.size() > curReturnLoc.getSize()) {
4181         methodSummary.setRETURNLoc(new CompositeLocation(returnLocTuple));
4182
4183         for (Iterator iterator = tupleToBeHigherThanReturnLocSet.iterator(); iterator.hasNext();) {
4184           NTuple<Location> higherTuple = (NTuple<Location>) iterator.next();
4185           fg.addValueFlowEdge(translateToDescTuple(higherTuple), returnDescTuple);
4186         }
4187         fg.getFlowNode(returnDescTuple).setSkeleton(true);
4188
4189       }
4190
4191       // makes sure that PCLOC is higher than RETURNLOC
4192       CompositeLocation pcLoc = methodSummary.getPCLoc();
4193       if (!pcLoc.get(0).isTop()) {
4194         NTuple<Descriptor> pcLocDescTuple = translateToDescTuple(pcLoc.getTuple());
4195         fg.addValueFlowEdge(pcLocDescTuple, returnDescTuple);
4196       }
4197
4198     }
4199
4200   }
4201
4202   private void calculateExtraLocations(MethodDescriptor md) {
4203     // calcualte pcloc, returnloc,...
4204
4205     System.out.println("\nSSJAVA:Calculate PCLOC/RETURNLOC locations: " + md);
4206
4207     calculatePCLOC(md);
4208     calculateRETURNLOC(md);
4209
4210   }
4211
4212   private NTuple<Location> generateLocTupleRelativeTo(MethodDescriptor md,
4213       Set<NTuple<Location>> paramLocTupleHavingInFlowSet, String locNamePrefix) {
4214
4215     // System.out.println("-generateLocTupleRelativeTo=" + paramLocTupleHavingInFlowSet);
4216
4217     NTuple<Location> higherLocTuple = new NTuple<Location>();
4218
4219     VarDescriptor thisVarDesc = md.getThis();
4220     // check if all paramter loc tuple is started with 'this' reference
4221     boolean hasParamNotStartedWithThisRef = false;
4222
4223     int minSize = 0;
4224
4225     Set<NTuple<Location>> paramLocTupleStartedWithThis = new HashSet<NTuple<Location>>();
4226
4227     next: for (Iterator iterator = paramLocTupleHavingInFlowSet.iterator(); iterator.hasNext();) {
4228       NTuple<Location> paramLocTuple = (NTuple<Location>) iterator.next();
4229       Descriptor paramLocalDesc = paramLocTuple.get(0).getLocDescriptor();
4230       if (!paramLocalDesc.equals(thisVarDesc)) {
4231
4232         Set<FlowNode> inNodeSet = getFlowGraph(md).getIncomingNodeSetByPrefix(paramLocalDesc);
4233         for (Iterator iterator2 = inNodeSet.iterator(); iterator2.hasNext();) {
4234           FlowNode flowNode = (FlowNode) iterator2.next();
4235           if (flowNode.getDescTuple().startsWith(thisVarDesc)) {
4236             // System.out.println("paramLocTuple=" + paramLocTuple + " is lower than THIS");
4237             continue next;
4238           }
4239         }
4240         hasParamNotStartedWithThisRef = true;
4241
4242       } else if (paramLocTuple.size() > 1) {
4243         paramLocTupleStartedWithThis.add(paramLocTuple);
4244         if (minSize == 0 || minSize > paramLocTuple.size()) {
4245           minSize = paramLocTuple.size();
4246         }
4247       }
4248     }
4249
4250     // System.out.println("---paramLocTupleStartedWithThis=" + paramLocTupleStartedWithThis);
4251     Descriptor enclosingDesc = md;
4252     if (hasParamNotStartedWithThisRef) {
4253       // in this case, PCLOC will be the local location
4254     } else {
4255       // all parameter is started with 'this', so PCLOC will be set relative to the composite
4256       // location started with 'this'.
4257       // for (int idx = 0; idx < minSize - 1; idx++) {
4258       for (int idx = 0; idx < 1; idx++) {
4259         Set<Descriptor> locDescSet = new HashSet<Descriptor>();
4260         Location curLoc = null;
4261         NTuple<Location> paramLocTuple = null;
4262         for (Iterator iterator = paramLocTupleStartedWithThis.iterator(); iterator.hasNext();) {
4263           paramLocTuple = (NTuple<Location>) iterator.next();
4264           // System.out.println("-----paramLocTuple=" + paramLocTuple + "  idx=" + idx);
4265           curLoc = paramLocTuple.get(idx);
4266           Descriptor locDesc = curLoc.getLocDescriptor();
4267           locDescSet.add(locDesc);
4268         }
4269         // System.out.println("-----locDescSet=" + locDescSet + " idx=" + idx);
4270         if (locDescSet.size() != 1) {
4271           break;
4272         }
4273         Location newLocElement = new Location(curLoc.getDescriptor(), curLoc.getLocDescriptor());
4274         // System.out.println("newLocElement" + newLocElement);
4275         higherLocTuple.add(newLocElement);
4276         enclosingDesc = getClassTypeDescriptor(curLoc.getLocDescriptor());
4277       }
4278
4279     }
4280
4281     String locIdentifier = locNamePrefix + (locSeed++);
4282     NameDescriptor locDesc = new NameDescriptor(locIdentifier);
4283     Location newLoc = new Location(enclosingDesc, locDesc);
4284     higherLocTuple.add(newLoc);
4285     // System.out.println("---new loc tuple=" + higherLocTuple);
4286
4287     return higherLocTuple;
4288
4289   }
4290
4291   public ClassDescriptor getClassTypeDescriptor(Descriptor in) {
4292
4293     if (in instanceof VarDescriptor) {
4294       return ((VarDescriptor) in).getType().getClassDesc();
4295     } else if (in instanceof FieldDescriptor) {
4296       return ((FieldDescriptor) in).getType().getClassDesc();
4297     }
4298     // else if (in instanceof LocationDescriptor) {
4299     // // here is the case that the descriptor 'in' is the last element of the assigned composite
4300     // // location
4301     // return ((VarDescriptor) locTuple.get(0).getLocDescriptor()).getType().getClassDesc();
4302     // }
4303     else {
4304       return null;
4305     }
4306
4307   }
4308
4309   private Set<NTuple<Location>> calculateHighestLocTupleSet(
4310       Set<NTuple<Location>> paramLocTupleHavingInFlowSet) {
4311
4312     Set<NTuple<Location>> highestSet = new HashSet<NTuple<Location>>();
4313
4314     Iterator<NTuple<Location>> iterator = paramLocTupleHavingInFlowSet.iterator();
4315     NTuple<Location> highest = iterator.next();
4316
4317     for (; iterator.hasNext();) {
4318       NTuple<Location> curLocTuple = (NTuple<Location>) iterator.next();
4319       if (isHigherThan(curLocTuple, highest)) {
4320         // System.out.println(curLocTuple + " is greater than " + highest);
4321         highest = curLocTuple;
4322       }
4323     }
4324
4325     highestSet.add(highest);
4326
4327     MethodDescriptor md = (MethodDescriptor) highest.get(0).getDescriptor();
4328     VarDescriptor thisVarDesc = md.getThis();
4329
4330     // System.out.println("highest=" + highest);
4331
4332     for (Iterator<NTuple<Location>> iter = paramLocTupleHavingInFlowSet.iterator(); iter.hasNext();) {
4333       NTuple<Location> curLocTuple = iter.next();
4334
4335       if (!curLocTuple.equals(highest) && !hasOrderingRelation(highest, curLocTuple)) {
4336
4337         // System.out.println("add it to the highest set=" + curLocTuple);
4338         highestSet.add(curLocTuple);
4339
4340       }
4341     }
4342
4343     return highestSet;
4344
4345   }
4346
4347   private Set<String> getHigherLocSymbolThan(SSJavaLattice<String> lattice, String loc) {
4348     Set<String> higherLocSet = new HashSet<String>();
4349
4350     Set<String> locSet = lattice.getTable().keySet();
4351     for (Iterator iterator = locSet.iterator(); iterator.hasNext();) {
4352       String element = (String) iterator.next();
4353       if (lattice.isGreaterThan(element, loc) && (!element.equals(lattice.getTopItem()))) {
4354         higherLocSet.add(element);
4355       }
4356     }
4357     return higherLocSet;
4358   }
4359
4360   private CompositeLocation getLowest(SSJavaLattice<String> methodLattice,
4361       Set<CompositeLocation> set) {
4362
4363     CompositeLocation lowest = set.iterator().next();
4364
4365     if (set.size() == 1) {
4366       return lowest;
4367     }
4368
4369     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
4370       CompositeLocation loc = (CompositeLocation) iterator.next();
4371
4372       if ((!loc.equals(lowest)) && (!isComparable(methodLattice, lowest, loc))) {
4373         // if there is a case where composite locations are incomparable, just
4374         // return null
4375         return null;
4376       }
4377
4378       if ((!loc.equals(lowest)) && isGreaterThan(methodLattice, lowest, loc)) {
4379         lowest = loc;
4380       }
4381     }
4382     return lowest;
4383   }
4384
4385   private boolean isComparable(SSJavaLattice<String> methodLattice, CompositeLocation comp1,
4386       CompositeLocation comp2) {
4387
4388     int size = comp1.getSize() >= comp2.getSize() ? comp2.getSize() : comp1.getSize();
4389
4390     for (int idx = 0; idx < size; idx++) {
4391       Location loc1 = comp1.get(idx);
4392       Location loc2 = comp2.get(idx);
4393
4394       Descriptor desc1 = loc1.getDescriptor();
4395       Descriptor desc2 = loc2.getDescriptor();
4396
4397       if (!desc1.equals(desc2)) {
4398         throw new Error("Fail to compare " + comp1 + " and " + comp2);
4399       }
4400
4401       String symbol1 = loc1.getLocIdentifier();
4402       String symbol2 = loc2.getLocIdentifier();
4403
4404       SSJavaLattice<String> lattice;
4405       if (idx == 0) {
4406         lattice = methodLattice;
4407       } else {
4408         lattice = getLattice(desc1);
4409       }
4410
4411       if (symbol1.equals(symbol2)) {
4412         continue;
4413       } else if (!lattice.isComparable(symbol1, symbol2)) {
4414         return false;
4415       }
4416
4417     }
4418
4419     return true;
4420   }
4421
4422   private boolean isGreaterThan(SSJavaLattice<String> methodLattice, CompositeLocation comp1,
4423       CompositeLocation comp2) {
4424
4425     int size = comp1.getSize() >= comp2.getSize() ? comp2.getSize() : comp1.getSize();
4426
4427     for (int idx = 0; idx < size; idx++) {
4428       Location loc1 = comp1.get(idx);
4429       Location loc2 = comp2.get(idx);
4430
4431       Descriptor desc1 = loc1.getDescriptor();
4432       Descriptor desc2 = loc2.getDescriptor();
4433
4434       if (!desc1.equals(desc2)) {
4435         throw new Error("Fail to compare " + comp1 + " and " + comp2);
4436       }
4437
4438       String symbol1 = loc1.getLocIdentifier();
4439       String symbol2 = loc2.getLocIdentifier();
4440
4441       SSJavaLattice<String> lattice;
4442       if (idx == 0) {
4443         lattice = methodLattice;
4444       } else {
4445         lattice = getLattice(desc1);
4446       }
4447
4448       if (symbol1.equals(symbol2)) {
4449         continue;
4450       } else if (lattice.isGreaterThan(symbol1, symbol2)) {
4451         return true;
4452       } else {
4453         return false;
4454       }
4455
4456     }
4457
4458     return false;
4459   }
4460
4461   private GlobalFlowGraph getSubGlobalFlowGraph(MethodDescriptor md) {
4462
4463     if (!mapMethodDescriptorToSubGlobalFlowGraph.containsKey(md)) {
4464       mapMethodDescriptorToSubGlobalFlowGraph.put(md, new GlobalFlowGraph(md));
4465     }
4466     return mapMethodDescriptorToSubGlobalFlowGraph.get(md);
4467   }
4468
4469   private void propagateFlowsToCallerWithNoCompositeLocation(MethodInvokeNode min,
4470       MethodDescriptor mdCaller, MethodDescriptor mdCallee) {
4471
4472     // System.out.println("-propagateFlowsToCallerWithNoCompositeLocation=" + min.printNode(0));
4473     // if the parameter A reaches to the parameter B
4474     // then, add an edge the argument A -> the argument B to the caller's flow
4475     // graph
4476
4477     FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
4478     FlowGraph callerFlowGraph = getFlowGraph(mdCaller);
4479     int numParam = calleeFlowGraph.getNumParameters();
4480
4481     for (int i = 0; i < numParam; i++) {
4482       for (int k = 0; k < numParam; k++) {
4483
4484         if (i != k) {
4485
4486           FlowNode paramNode1 = calleeFlowGraph.getParamFlowNode(i);
4487           FlowNode paramNode2 = calleeFlowGraph.getParamFlowNode(k);
4488
4489           NTuple<Descriptor> arg1Tuple = getNodeTupleByArgIdx(min, i);
4490           NTuple<Descriptor> arg2Tuple = getNodeTupleByArgIdx(min, k);
4491
4492           // check if the callee propagates an ordering constraints through
4493           // parameters
4494
4495           // Set<FlowNode> localReachSet = calleeFlowGraph.getLocalReachFlowNodeSetFrom(paramNode1);
4496           Set<FlowNode> localReachSet =
4497               calleeFlowGraph.getReachableSetFrom(paramNode1.getDescTuple());
4498
4499           NTuple<Descriptor> paramDescTuple1 = paramNode1.getCurrentDescTuple();
4500           NTuple<Descriptor> paramDescTuple2 = paramNode2.getCurrentDescTuple();
4501
4502           // System.out.println("-param1CurTuple=" + paramDescTuple1 + " param2CurTuple="
4503           // + paramDescTuple2);
4504           // System.out.println("-- localReachSet from param1=" + localReachSet);
4505
4506           if (paramDescTuple1.get(0).equals(paramDescTuple2.get(0))) {
4507             // if two parameters share the same prefix
4508             // it already has been assigned to a composite location
4509             // so we don't need to add an additional ordering relation caused by these two
4510             // paramters.
4511             continue;
4512           }
4513
4514           if (arg1Tuple.size() > 0 && arg2Tuple.size() > 0
4515               && containsPrefix(paramNode2.getDescTuple().get(0), localReachSet)) {
4516             // need to propagate an ordering relation s.t. arg1 is higher
4517             // than arg2
4518             // System.out.println("-param1=" + paramNode1 + " is higher than param2=" + paramNode2);
4519
4520             // add a new flow between the corresponding arguments.
4521             callerFlowGraph.addValueFlowEdge(arg1Tuple, arg2Tuple);
4522             // System.out.println("arg1=" + arg1Tuple + "   arg2=" + arg2Tuple);
4523
4524             // System.out
4525             // .println("-arg1Tuple=" + arg1Tuple + " is higher than arg2Tuple=" + arg2Tuple);
4526
4527           }
4528
4529           // System.out.println();
4530         }
4531       }
4532     }
4533
4534     // if a parameter has a composite location and the first element of the parameter location
4535     // matches the callee's 'this'
4536     // we have a more specific constraint: the caller's corresponding argument is higher than the
4537     // parameter location which is translated into the caller
4538
4539     for (int idx = 0; idx < numParam; idx++) {
4540       FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx);
4541       CompositeLocation compLoc = paramNode.getCompositeLocation();
4542       // System.out.println("paramNode=" + paramNode + "   compLoc=" + compLoc);
4543       if (compLoc != null && compLoc.get(0).getLocDescriptor().equals(min.getMethod().getThis())) {
4544         // System.out.println("$$$COMPLOC CASE=" + compLoc + "  idx=" + idx);
4545
4546         NTuple<Descriptor> argTuple = getNodeTupleByArgIdx(min, idx);
4547         // System.out.println("--- argTuple=" + argTuple + " current compLoc="
4548         // + callerFlowGraph.getFlowNode(argTuple).getCompositeLocation());
4549
4550         NTuple<Descriptor> translatedParamTuple =
4551             translateCompositeLocationToCaller(idx, min, compLoc);
4552         // System.out.println("add a flow edge= " + argTuple + "->" + translatedParamTuple);
4553         callerFlowGraph.addValueFlowEdge(argTuple, translatedParamTuple);
4554
4555         Set<NTuple<Location>> pcLocTupleSet = getPCLocTupleSet(min);
4556         for (Iterator iterator = pcLocTupleSet.iterator(); iterator.hasNext();) {
4557           NTuple<Location> pcLocTuple = (NTuple<Location>) iterator.next();
4558           callerFlowGraph.addValueFlowEdge(translateToDescTuple(pcLocTuple), translatedParamTuple);
4559         }
4560
4561       }
4562     }
4563
4564   }
4565
4566   private boolean containsPrefix(Descriptor prefixDesc, Set<FlowNode> set) {
4567
4568     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
4569       FlowNode flowNode = (FlowNode) iterator.next();
4570       if (flowNode.getDescTuple().startsWith(prefixDesc)) {
4571         // System.out.println("FOUND=" + flowNode);
4572         return true;
4573       }
4574     }
4575     return false;
4576   }
4577
4578   private NTuple<Descriptor> translateCompositeLocationToCaller(int idx, MethodInvokeNode min,
4579       CompositeLocation compLocForParam1) {
4580
4581     NTuple<Descriptor> baseTuple = mapMethodInvokeNodeToBaseTuple.get(min);
4582
4583     NTuple<Descriptor> tuple = new NTuple<Descriptor>();
4584     for (int i = 0; i < baseTuple.size(); i++) {
4585       tuple.add(baseTuple.get(i));
4586     }
4587
4588     for (int i = 1; i < compLocForParam1.getSize(); i++) {
4589       Location loc = compLocForParam1.get(i);
4590       tuple.add(loc.getLocDescriptor());
4591     }
4592
4593     return tuple;
4594   }
4595
4596   private CompositeLocation generateCompositeLocation(NTuple<Location> prefixLocTuple) {
4597
4598     // System.out.println("generateCompositeLocation=" + prefixLocTuple);
4599
4600     CompositeLocation newCompLoc = new CompositeLocation();
4601     for (int i = 0; i < prefixLocTuple.size(); i++) {
4602       newCompLoc.addLocation(prefixLocTuple.get(i));
4603     }
4604
4605     Descriptor lastDescOfPrefix = prefixLocTuple.get(prefixLocTuple.size() - 1).getLocDescriptor();
4606
4607     ClassDescriptor enclosingDescriptor;
4608     if (lastDescOfPrefix instanceof FieldDescriptor) {
4609       enclosingDescriptor = ((FieldDescriptor) lastDescOfPrefix).getType().getClassDesc();
4610       // System.out.println("enclosingDescriptor0=" + enclosingDescriptor);
4611     } else if (lastDescOfPrefix.equals(GLOBALDESC)) {
4612       MethodDescriptor currentMethodDesc = (MethodDescriptor) prefixLocTuple.get(0).getDescriptor();
4613       enclosingDescriptor = currentMethodDesc.getClassDesc();
4614     } else {
4615       // var descriptor case
4616       enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc();
4617     }
4618     // System.out.println("enclosingDescriptor=" + enclosingDescriptor);
4619
4620     LocationDescriptor newLocDescriptor = generateNewLocationDescriptor();
4621     newLocDescriptor.setEnclosingClassDesc(enclosingDescriptor);
4622
4623     Location newLoc = new Location(enclosingDescriptor, newLocDescriptor.getSymbol());
4624     newLoc.setLocDescriptor(newLocDescriptor);
4625     newCompLoc.addLocation(newLoc);
4626
4627     // System.out.println("--newCompLoc=" + newCompLoc);
4628     return newCompLoc;
4629   }
4630
4631   private CompositeLocation generateCompositeLocation(MethodDescriptor md,
4632       NTuple<Descriptor> paramPrefix) {
4633
4634     // System.out.println("generateCompositeLocation=" + paramPrefix);
4635
4636     CompositeLocation newCompLoc = convertToCompositeLocation(md, paramPrefix);
4637
4638     Descriptor lastDescOfPrefix = paramPrefix.get(paramPrefix.size() - 1);
4639     // System.out.println("lastDescOfPrefix=" + lastDescOfPrefix + "  kind="
4640     // + lastDescOfPrefix.getClass());
4641     ClassDescriptor enclosingDescriptor;
4642     if (lastDescOfPrefix instanceof FieldDescriptor) {
4643       enclosingDescriptor = ((FieldDescriptor) lastDescOfPrefix).getType().getClassDesc();
4644       // System.out.println("enclosingDescriptor0=" + enclosingDescriptor);
4645     } else {
4646       // var descriptor case
4647       enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc();
4648     }
4649     // System.out.println("enclosingDescriptor=" + enclosingDescriptor);
4650
4651     LocationDescriptor newLocDescriptor = generateNewLocationDescriptor();
4652     newLocDescriptor.setEnclosingClassDesc(enclosingDescriptor);
4653
4654     Location newLoc = new Location(enclosingDescriptor, newLocDescriptor.getSymbol());
4655     newLoc.setLocDescriptor(newLocDescriptor);
4656     newCompLoc.addLocation(newLoc);
4657
4658     // System.out.println("--newCompLoc=" + newCompLoc);
4659     return newCompLoc;
4660   }
4661
4662   private List<NTuple<Descriptor>> translatePrefixListToCallee(Descriptor baseRef,
4663       MethodDescriptor mdCallee, List<NTuple<Descriptor>> callerPrefixList) {
4664
4665     List<NTuple<Descriptor>> calleePrefixList = new ArrayList<NTuple<Descriptor>>();
4666
4667     for (int i = 0; i < callerPrefixList.size(); i++) {
4668       NTuple<Descriptor> prefix = callerPrefixList.get(i);
4669       if (prefix.startsWith(baseRef)) {
4670         NTuple<Descriptor> calleePrefix = new NTuple<Descriptor>();
4671         calleePrefix.add(mdCallee.getThis());
4672         for (int k = 1; k < prefix.size(); k++) {
4673           calleePrefix.add(prefix.get(k));
4674         }
4675         calleePrefixList.add(calleePrefix);
4676       }
4677     }
4678
4679     return calleePrefixList;
4680
4681   }
4682
4683   public CompositeLocation convertToCompositeLocation(MethodDescriptor md, NTuple<Descriptor> tuple) {
4684
4685     CompositeLocation compLoc = new CompositeLocation();
4686
4687     Descriptor enclosingDescriptor = md;
4688
4689     for (int i = 0; i < tuple.size(); i++) {
4690       Descriptor curDescriptor = tuple.get(i);
4691       Location locElement = new Location(enclosingDescriptor, curDescriptor.getSymbol());
4692       locElement.setLocDescriptor(curDescriptor);
4693       compLoc.addLocation(locElement);
4694
4695       if (curDescriptor instanceof VarDescriptor) {
4696         enclosingDescriptor = md.getClassDesc();
4697       } else if (curDescriptor instanceof FieldDescriptor) {
4698         enclosingDescriptor = ((FieldDescriptor) curDescriptor).getClassDescriptor();
4699       } else if (curDescriptor instanceof NameDescriptor) {
4700         // it is "GLOBAL LOC" case!
4701         enclosingDescriptor = GLOBALDESC;
4702       } else if (curDescriptor instanceof InterDescriptor) {
4703         enclosingDescriptor = getFlowGraph(md).getEnclosingDescriptor(curDescriptor);
4704       } else {
4705         enclosingDescriptor = null;
4706       }
4707
4708     }
4709
4710     return compLoc;
4711   }
4712
4713   private LocationDescriptor generateNewLocationDescriptor() {
4714     return new LocationDescriptor("Loc" + (locSeed++));
4715   }
4716
4717   private int getPrefixIndex(NTuple<Descriptor> tuple1, NTuple<Descriptor> tuple2) {
4718
4719     // return the index where the prefix shared by tuple1 and tuple2 is ended
4720     // if there is no prefix shared by both of them, return -1
4721
4722     int minSize = tuple1.size();
4723     if (minSize > tuple2.size()) {
4724       minSize = tuple2.size();
4725     }
4726
4727     int idx = -1;
4728     for (int i = 0; i < minSize; i++) {
4729       if (!tuple1.get(i).equals(tuple2.get(i))) {
4730         break;
4731       } else {
4732         idx++;
4733       }
4734     }
4735
4736     return idx;
4737   }
4738
4739   private CompositeLocation generateInferredCompositeLocation(MethodLocationInfo methodInfo,
4740       NTuple<Location> tuple) {
4741
4742     // first, retrieve inferred location by the local var descriptor
4743     CompositeLocation inferLoc = new CompositeLocation();
4744
4745     CompositeLocation localVarInferLoc =
4746         methodInfo.getInferLocation(tuple.get(0).getLocDescriptor());
4747
4748     localVarInferLoc.get(0).setLocDescriptor(tuple.get(0).getLocDescriptor());
4749
4750     for (int i = 0; i < localVarInferLoc.getSize(); i++) {
4751       inferLoc.addLocation(localVarInferLoc.get(i));
4752     }
4753
4754     for (int i = 1; i < tuple.size(); i++) {
4755       Location cur = tuple.get(i);
4756       Descriptor enclosingDesc = cur.getDescriptor();
4757       Descriptor curDesc = cur.getLocDescriptor();
4758
4759       Location inferLocElement;
4760       if (curDesc == null) {
4761         // in this case, we have a newly generated location.
4762         inferLocElement = new Location(enclosingDesc, cur.getLocIdentifier());
4763       } else {
4764         String fieldLocSymbol =
4765             getLocationInfo(enclosingDesc).getInferLocation(curDesc).get(0).getLocIdentifier();
4766         inferLocElement = new Location(enclosingDesc, fieldLocSymbol);
4767         inferLocElement.setLocDescriptor(curDesc);
4768       }
4769
4770       inferLoc.addLocation(inferLocElement);
4771
4772     }
4773
4774     assert (inferLoc.get(0).getLocDescriptor().getSymbol() == inferLoc.get(0).getLocIdentifier());
4775     return inferLoc;
4776   }
4777
4778   public LocationInfo getLocationInfo(Descriptor d) {
4779     if (d instanceof MethodDescriptor) {
4780       return getMethodLocationInfo((MethodDescriptor) d);
4781     } else {
4782       return getFieldLocationInfo((ClassDescriptor) d);
4783     }
4784   }
4785
4786   private MethodLocationInfo getMethodLocationInfo(MethodDescriptor md) {
4787
4788     if (!mapMethodDescToMethodLocationInfo.containsKey(md)) {
4789       mapMethodDescToMethodLocationInfo.put(md, new MethodLocationInfo(md));
4790     }
4791
4792     return mapMethodDescToMethodLocationInfo.get(md);
4793
4794   }
4795
4796   private LocationInfo getFieldLocationInfo(ClassDescriptor cd) {
4797
4798     if (!mapClassToLocationInfo.containsKey(cd)) {
4799       mapClassToLocationInfo.put(cd, new LocationInfo(cd));
4800     }
4801
4802     return mapClassToLocationInfo.get(cd);
4803
4804   }
4805
4806   private void addPrefixMapping(Map<NTuple<Location>, Set<NTuple<Location>>> map,
4807       NTuple<Location> prefix, NTuple<Location> element) {
4808
4809     if (!map.containsKey(prefix)) {
4810       map.put(prefix, new HashSet<NTuple<Location>>());
4811     }
4812     map.get(prefix).add(element);
4813   }
4814
4815   private boolean containsNonPrimitiveElement(Set<Descriptor> descSet) {
4816     for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
4817       Descriptor desc = (Descriptor) iterator.next();
4818
4819       if (desc.equals(LocationInference.GLOBALDESC)) {
4820         return true;
4821       } else if (desc instanceof VarDescriptor) {
4822         if (!((VarDescriptor) desc).getType().isPrimitive()) {
4823           return true;
4824         }
4825       } else if (desc instanceof FieldDescriptor) {
4826         if (!((FieldDescriptor) desc).getType().isPrimitive()) {
4827           return true;
4828         }
4829       }
4830
4831     }
4832     return false;
4833   }
4834
4835   public SSJavaLattice<String> getLattice(Descriptor d) {
4836     if (d instanceof MethodDescriptor) {
4837       return getMethodLattice((MethodDescriptor) d);
4838     } else {
4839       return getFieldLattice((ClassDescriptor) d);
4840     }
4841   }
4842
4843   private SSJavaLattice<String> getMethodLattice(MethodDescriptor md) {
4844     if (!md2lattice.containsKey(md)) {
4845       md2lattice.put(md, new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM));
4846     }
4847     return md2lattice.get(md);
4848   }
4849
4850   private void setMethodLattice(MethodDescriptor md, SSJavaLattice<String> lattice) {
4851     md2lattice.put(md, lattice);
4852   }
4853
4854   private void extractFlowsBetweenFields(ClassDescriptor cd, FlowNode srcNode, FlowNode dstNode,
4855       int idx) {
4856
4857     NTuple<Descriptor> srcCurTuple = srcNode.getCurrentDescTuple();
4858     NTuple<Descriptor> dstCurTuple = dstNode.getCurrentDescTuple();
4859
4860     if (srcCurTuple.get(idx).equals(dstCurTuple.get(idx)) && srcCurTuple.size() > (idx + 1)
4861         && dstCurTuple.size() > (idx + 1)) {
4862       // value flow between fields: we don't need to add a binary relation
4863       // for this case
4864
4865       Descriptor desc = srcCurTuple.get(idx);
4866       ClassDescriptor classDesc;
4867
4868       if (idx == 0) {
4869         classDesc = ((VarDescriptor) desc).getType().getClassDesc();
4870       } else {
4871         if (desc instanceof FieldDescriptor) {
4872           classDesc = ((FieldDescriptor) desc).getType().getClassDesc();
4873         } else {
4874           // this case is that the local variable has a composite location assignment
4875           // the following element after the composite location to the local variable
4876           // has the enclosing descriptor of the local variable
4877           Descriptor localDesc = srcNode.getDescTuple().get(0);
4878           classDesc = ((VarDescriptor) localDesc).getType().getClassDesc();
4879         }
4880       }
4881       extractFlowsBetweenFields(classDesc, srcNode, dstNode, idx + 1);
4882
4883     } else {
4884
4885       Descriptor srcFieldDesc = srcCurTuple.get(idx);
4886       Descriptor dstFieldDesc = dstCurTuple.get(idx);
4887
4888       // System.out.println("srcFieldDesc=" + srcFieldDesc + "  dstFieldDesc=" + dstFieldDesc
4889       // + "   idx=" + idx);
4890       if (!srcFieldDesc.equals(dstFieldDesc)) {
4891         // add a new edge
4892         // System.out.println("-ADD EDGE");
4893         getHierarchyGraph(cd).addEdge(srcFieldDesc, dstFieldDesc);
4894       } else if (!isReference(srcFieldDesc) && !isReference(dstFieldDesc)) {
4895         // System.out.println("-ADD EDGE");
4896         getHierarchyGraph(cd).addEdge(srcFieldDesc, dstFieldDesc);
4897       }
4898
4899     }
4900
4901   }
4902
4903   public SSJavaLattice<String> getFieldLattice(ClassDescriptor cd) {
4904     if (!cd2lattice.containsKey(cd)) {
4905       cd2lattice.put(cd, new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM));
4906     }
4907     return cd2lattice.get(cd);
4908   }
4909
4910   public LinkedList<MethodDescriptor> computeMethodList() {
4911
4912     Set<MethodDescriptor> toSort = new HashSet<MethodDescriptor>();
4913
4914     setupToAnalyze();
4915
4916     Set<MethodDescriptor> visited = new HashSet<MethodDescriptor>();
4917     Set<MethodDescriptor> reachableCallee = new HashSet<MethodDescriptor>();
4918
4919     while (!toAnalyzeIsEmpty()) {
4920       ClassDescriptor cd = toAnalyzeNext();
4921
4922       if (cd.getClassName().equals("Object")) {
4923         rootClassDescriptor = cd;
4924         // inheritanceTree = new InheritanceTree<ClassDescriptor>(cd);
4925       }
4926
4927       setupToAnalazeMethod(cd);
4928       temp_toanalyzeMethodList.removeAll(visited);
4929
4930       while (!toAnalyzeMethodIsEmpty()) {
4931         MethodDescriptor md = toAnalyzeMethodNext();
4932         if ((!visited.contains(md))
4933             && (ssjava.needTobeAnnotated(md) || reachableCallee.contains(md))) {
4934
4935           // creates a mapping from a method descriptor to virtual methods
4936           Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
4937           if (md.isStatic()) {
4938             setPossibleCallees.add(md);
4939           } else {
4940             setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md));
4941           }
4942
4943           Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getCalleeSet(md);
4944           Set<MethodDescriptor> needToAnalyzeCalleeSet = new HashSet<MethodDescriptor>();
4945
4946           for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) {
4947             MethodDescriptor calleemd = (MethodDescriptor) iterator.next();
4948             if ((!ssjava.isTrustMethod(calleemd))
4949                 && (!ssjava.isSSJavaUtil(calleemd.getClassDesc()))
4950                 && (!calleemd.getModifiers().isNative())) {
4951               if (!visited.contains(calleemd)) {
4952                 temp_toanalyzeMethodList.add(calleemd);
4953               }
4954               reachableCallee.add(calleemd);
4955               needToAnalyzeCalleeSet.add(calleemd);
4956             }
4957           }
4958
4959           mapMethodToCalleeSet.put(md, needToAnalyzeCalleeSet);
4960
4961           visited.add(md);
4962
4963           toSort.add(md);
4964         }
4965       }
4966     }
4967
4968     return ssjava.topologicalSort(toSort);
4969
4970   }
4971
4972   public boolean isTransitivelyCalledFrom(MethodDescriptor callee, MethodDescriptor caller) {
4973     // if the callee is transitively invoked from the caller
4974     // return true;
4975
4976     int callerIdx = toanalyze_methodDescList.indexOf(caller);
4977     int calleeIdx = toanalyze_methodDescList.indexOf(callee);
4978
4979     if (callerIdx < calleeIdx) {
4980       return true;
4981     }
4982
4983     return false;
4984
4985   }
4986
4987   public void constructFlowGraph() {
4988
4989     System.out.println("");
4990     toanalyze_methodDescList = computeMethodList();
4991
4992     // hack... it seems that there is a problem with topological sorting.
4993     // so String.toString(Object o) is appeared too higher in the call chain.
4994     MethodDescriptor mdToString1 = null;
4995     MethodDescriptor mdToString2 = null;
4996     for (Iterator iterator = toanalyze_methodDescList.iterator(); iterator.hasNext();) {
4997       MethodDescriptor md = (MethodDescriptor) iterator.next();
4998       if (md.toString().equals("public static String String.valueOf(Object o)")) {
4999         mdToString1 = md;
5000       }
5001       if (md.toString().equals("public String Object.toString()")) {
5002         mdToString2 = md;
5003       }
5004     }
5005
5006     if (mdToString1 != null) {
5007       toanalyze_methodDescList.remove(mdToString1);
5008       toanalyze_methodDescList.addLast(mdToString1);
5009     }
5010     if (mdToString2 != null) {
5011       toanalyze_methodDescList.remove(mdToString2);
5012       toanalyze_methodDescList.addLast(mdToString2);
5013     }
5014
5015     LinkedList<MethodDescriptor> methodDescList =
5016         (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
5017
5018     // System.out.println("@@@methodDescList=" + methodDescList);
5019     // System.exit(0);
5020
5021     while (!methodDescList.isEmpty()) {
5022       MethodDescriptor md = methodDescList.removeLast();
5023       if (state.SSJAVADEBUG) {
5024         System.out.println();
5025         System.out.println("SSJAVA: Constructing a flow graph: " + md);
5026
5027         // creates a mapping from a parameter descriptor to its index
5028         Map<Descriptor, Integer> mapParamDescToIdx = new HashMap<Descriptor, Integer>();
5029         int offset = 0;
5030         if (!md.isStatic()) {
5031           offset = 1;
5032           mapParamDescToIdx.put(md.getThis(), 0);
5033         }
5034
5035         for (int i = 0; i < md.numParameters(); i++) {
5036           Descriptor paramDesc = (Descriptor) md.getParameter(i);
5037           mapParamDescToIdx.put(paramDesc, new Integer(i + offset));
5038         }
5039
5040         FlowGraph fg = new FlowGraph(md, mapParamDescToIdx);
5041         mapMethodDescriptorToFlowGraph.put(md, fg);
5042
5043         analyzeMethodBody(md.getClassDesc(), md);
5044
5045         // System.out.println("##constructSubGlobalFlowGraph");
5046         // GlobalFlowGraph subGlobalFlowGraph = constructSubGlobalFlowGraph(fg);
5047         // mapMethodDescriptorToSubGlobalFlowGraph.put(md, subGlobalFlowGraph);
5048         //
5049         // // TODO
5050         // System.out.println("##addValueFlowsFromCalleeSubGlobalFlowGraph");
5051         // addValueFlowsFromCalleeSubGlobalFlowGraph(md, subGlobalFlowGraph);
5052         // subGlobalFlowGraph.writeGraph("_SUBGLOBAL");
5053         //
5054         // propagateFlowsFromCalleesWithNoCompositeLocation(md);
5055       }
5056     }
5057     // _debug_printGraph();
5058
5059   }
5060
5061   private void constructGlobalFlowGraph() {
5062     LinkedList<MethodDescriptor> methodDescList =
5063         (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
5064
5065     while (!methodDescList.isEmpty()) {
5066       MethodDescriptor md = methodDescList.removeLast();
5067       if (state.SSJAVADEBUG) {
5068         System.out.println();
5069         System.out.println("SSJAVA: Constructing a sub global flow graph: " + md);
5070
5071         constructSubGlobalFlowGraph(getFlowGraph(md));
5072
5073         // TODO
5074         // System.out.println("-add Value Flows From CalleeSubGlobalFlowGraph");
5075         addValueFlowsFromCalleeSubGlobalFlowGraph(md);
5076         // subGlobalFlowGraph.writeGraph("_SUBGLOBAL");
5077
5078         // System.out.println("-propagate Flows From Callees With No CompositeLocation");
5079         // propagateFlowsFromCalleesWithNoCompositeLocation(md);
5080
5081         // mark if a parameter has incoming flows
5082         checkParamNodesInSubGlobalFlowGraph(md);
5083
5084       }
5085     }
5086   }
5087
5088   private void checkParamNodesInSubGlobalFlowGraph(MethodDescriptor md) {
5089     GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
5090     FlowGraph flowGraph = getFlowGraph(md);
5091
5092     Set<FlowNode> paramFlowNodeSet = flowGraph.getParamFlowNodeSet();
5093     for (Iterator iterator = paramFlowNodeSet.iterator(); iterator.hasNext();) {
5094       FlowNode paramFlowNode = (FlowNode) iterator.next();
5095       // System.out.println("paramFlowNode=" + paramFlowNode);
5096       NTuple<Descriptor> paramDescTuple = paramFlowNode.getDescTuple();
5097       NTuple<Location> paramLocTuple = translateToLocTuple(md, paramDescTuple);
5098       GlobalFlowNode paramGlobalNode = globalFlowGraph.getFlowNode(paramLocTuple);
5099
5100       Set<GlobalFlowNode> incomingNodeSet =
5101           globalFlowGraph.getIncomingNodeSetByPrefix(paramLocTuple.get(0));
5102
5103       if (incomingNodeSet.size() > 0) {
5104         paramGlobalNode.setParamNodeWithIncomingFlows(true);
5105       }
5106
5107     }
5108   }
5109
5110   private Set<MethodInvokeNode> getMethodInvokeNodeSet(MethodDescriptor md) {
5111     if (!mapMethodDescriptorToMethodInvokeNodeSet.containsKey(md)) {
5112       mapMethodDescriptorToMethodInvokeNodeSet.put(md, new HashSet<MethodInvokeNode>());
5113     }
5114     return mapMethodDescriptorToMethodInvokeNodeSet.get(md);
5115   }
5116
5117   private void propagateFlowsFromCalleesWithNoCompositeLocation(MethodDescriptor mdCaller) {
5118
5119     // the transformation for a call site propagates flows through parameters
5120     // if the method is virtual, it also grab all relations from any possible
5121     // callees
5122
5123     Set<MethodInvokeNode> setMethodInvokeNode =
5124         mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller);
5125
5126     if (setMethodInvokeNode != null) {
5127
5128       for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) {
5129         MethodInvokeNode min = (MethodInvokeNode) iterator.next();
5130         MethodDescriptor mdCallee = min.getMethod();
5131         Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
5132         if (mdCallee.isStatic()) {
5133           setPossibleCallees.add(mdCallee);
5134         } else {
5135           Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getMethods(mdCallee);
5136           // removes method descriptors that are not invoked by the caller
5137           calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller));
5138           setPossibleCallees.addAll(calleeSet);
5139         }
5140
5141         for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
5142           MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
5143           propagateFlowsToCallerWithNoCompositeLocation(min, mdCaller, possibleMdCallee);
5144         }
5145
5146       }
5147     }
5148
5149   }
5150
5151   private void analyzeMethodBody(ClassDescriptor cd, MethodDescriptor md) {
5152     BlockNode bn = state.getMethodBody(md);
5153     NodeTupleSet implicitFlowTupleSet = new NodeTupleSet();
5154     analyzeFlowBlockNode(md, md.getParameterTable(), bn, implicitFlowTupleSet);
5155   }
5156
5157   private void analyzeFlowBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn,
5158       NodeTupleSet implicitFlowTupleSet) {
5159
5160     bn.getVarTable().setParent(nametable);
5161     for (int i = 0; i < bn.size(); i++) {
5162       BlockStatementNode bsn = bn.get(i);
5163       analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet);
5164     }
5165
5166   }
5167
5168   private void analyzeBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
5169       BlockStatementNode bsn, NodeTupleSet implicitFlowTupleSet) {
5170
5171     switch (bsn.kind()) {
5172     case Kind.BlockExpressionNode:
5173       analyzeBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn, implicitFlowTupleSet);
5174       break;
5175
5176     case Kind.DeclarationNode:
5177       analyzeFlowDeclarationNode(md, nametable, (DeclarationNode) bsn, implicitFlowTupleSet);
5178       break;
5179
5180     case Kind.IfStatementNode:
5181       analyzeFlowIfStatementNode(md, nametable, (IfStatementNode) bsn, implicitFlowTupleSet);
5182       break;
5183
5184     case Kind.LoopNode:
5185       analyzeFlowLoopNode(md, nametable, (LoopNode) bsn, implicitFlowTupleSet);
5186       break;
5187
5188     case Kind.ReturnNode:
5189       analyzeFlowReturnNode(md, nametable, (ReturnNode) bsn, implicitFlowTupleSet);
5190       break;
5191
5192     case Kind.SubBlockNode:
5193       analyzeFlowSubBlockNode(md, nametable, (SubBlockNode) bsn, implicitFlowTupleSet);
5194       break;
5195
5196     case Kind.ContinueBreakNode:
5197       break;
5198
5199     case Kind.SwitchStatementNode:
5200       analyzeSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn, implicitFlowTupleSet);
5201       break;
5202
5203     }
5204
5205   }
5206
5207   private void analyzeSwitchBlockNode(MethodDescriptor md, SymbolTable nametable,
5208       SwitchBlockNode sbn, NodeTupleSet implicitFlowTupleSet) {
5209
5210     analyzeFlowBlockNode(md, nametable, sbn.getSwitchBlockStatement(), implicitFlowTupleSet);
5211
5212   }
5213
5214   private void analyzeSwitchStatementNode(MethodDescriptor md, SymbolTable nametable,
5215       SwitchStatementNode ssn, NodeTupleSet implicitFlowTupleSet) {
5216
5217     NodeTupleSet condTupleNode = new NodeTupleSet();
5218     analyzeFlowExpressionNode(md, nametable, ssn.getCondition(), condTupleNode, null,
5219         implicitFlowTupleSet, false);
5220
5221     NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
5222
5223     newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
5224     newImplicitTupleSet.addTupleSet(condTupleNode);
5225
5226     if (needToGenerateInterLoc(newImplicitTupleSet)) {
5227       // need to create an intermediate node for the GLB of conditional
5228       // locations & implicit flows
5229
5230       NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
5231       for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) {
5232         NTuple<Descriptor> tuple = idxIter.next();
5233         addFlowGraphEdge(md, tuple, interTuple);
5234       }
5235       newImplicitTupleSet.clear();
5236       newImplicitTupleSet.addTuple(interTuple);
5237     }
5238
5239     BlockNode sbn = ssn.getSwitchBody();
5240     for (int i = 0; i < sbn.size(); i++) {
5241       analyzeSwitchBlockNode(md, nametable, (SwitchBlockNode) sbn.get(i), newImplicitTupleSet);
5242     }
5243
5244   }
5245
5246   private void analyzeFlowSubBlockNode(MethodDescriptor md, SymbolTable nametable,
5247       SubBlockNode sbn, NodeTupleSet implicitFlowTupleSet) {
5248     analyzeFlowBlockNode(md, nametable, sbn.getBlockNode(), implicitFlowTupleSet);
5249   }
5250
5251   private void analyzeFlowReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode rn,
5252       NodeTupleSet implicitFlowTupleSet) {
5253
5254     // System.out.println("-analyzeFlowReturnNode=" + rn.printNode(0));
5255     ExpressionNode returnExp = rn.getReturnExpression();
5256
5257     if (returnExp != null) {
5258       NodeTupleSet nodeSet = new NodeTupleSet();
5259       // if a return expression returns a literal value, nodeSet is empty
5260       analyzeFlowExpressionNode(md, nametable, returnExp, nodeSet, false);
5261       FlowGraph fg = getFlowGraph(md);
5262
5263       // if (implicitFlowTupleSet.size() == 1
5264       // &&
5265       // fg.getFlowNode(implicitFlowTupleSet.iterator().next()).isIntermediate())
5266       // {
5267       //
5268       // // since there is already an intermediate node for the GLB of implicit
5269       // flows
5270       // // we don't need to create another intermediate node.
5271       // // just re-use the intermediate node for implicit flows.
5272       //
5273       // FlowNode meetNode =
5274       // fg.getFlowNode(implicitFlowTupleSet.iterator().next());
5275       //
5276       // for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
5277       // NTuple<Descriptor> returnNodeTuple = (NTuple<Descriptor>)
5278       // iterator.next();
5279       // fg.addValueFlowEdge(returnNodeTuple, meetNode.getDescTuple());
5280       // }
5281       //
5282       // }
5283
5284       NodeTupleSet currentFlowTupleSet = new NodeTupleSet();
5285
5286       // add tuples from return node
5287       currentFlowTupleSet.addTupleSet(nodeSet);
5288
5289       // add tuples corresponding to the current implicit flows
5290       currentFlowTupleSet.addTupleSet(implicitFlowTupleSet);
5291
5292       // System.out.println("---currentFlowTupleSet=" + currentFlowTupleSet);
5293
5294       if (needToGenerateInterLoc(currentFlowTupleSet)) {
5295
5296         FlowNode meetNode = fg.createIntermediateNode();
5297         for (Iterator iterator = currentFlowTupleSet.iterator(); iterator.hasNext();) {
5298           NTuple<Descriptor> currentFlowTuple = (NTuple<Descriptor>) iterator.next();
5299           fg.addValueFlowEdge(currentFlowTuple, meetNode.getDescTuple());
5300         }
5301         fg.addReturnFlowNode(meetNode.getDescTuple());
5302       } else {
5303         // currentFlowTupleSet = removeLiteralTuple(currentFlowTupleSet);
5304         for (Iterator iterator = currentFlowTupleSet.iterator(); iterator.hasNext();) {
5305           NTuple<Descriptor> currentFlowTuple = (NTuple<Descriptor>) iterator.next();
5306           fg.addReturnFlowNode(currentFlowTuple);
5307         }
5308       }
5309
5310     }
5311
5312   }
5313
5314   private NodeTupleSet removeLiteralTuple(NodeTupleSet inSet) {
5315     NodeTupleSet tupleSet = new NodeTupleSet();
5316     for (Iterator<NTuple<Descriptor>> iter = inSet.iterator(); iter.hasNext();) {
5317       NTuple<Descriptor> tuple = iter.next();
5318       if (!tuple.get(0).equals(LITERALDESC)) {
5319         tupleSet.addTuple(tuple);
5320       }
5321     }
5322     return tupleSet;
5323   }
5324
5325   private boolean needToGenerateInterLoc(NodeTupleSet tupleSet) {
5326     int size = 0;
5327     for (Iterator<NTuple<Descriptor>> iter = tupleSet.iterator(); iter.hasNext();) {
5328       NTuple<Descriptor> descTuple = iter.next();
5329       if (!descTuple.get(0).equals(LITERALDESC)) {
5330         size++;
5331       }
5332     }
5333     if (size > 1) {
5334       // System.out.println("needToGenerateInterLoc=" + tupleSet + "  size=" + size);
5335       return true;
5336     } else {
5337       return false;
5338     }
5339   }
5340
5341   private void analyzeFlowLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln,
5342       NodeTupleSet implicitFlowTupleSet) {
5343
5344     if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) {
5345
5346       NodeTupleSet condTupleNode = new NodeTupleSet();
5347       analyzeFlowExpressionNode(md, nametable, ln.getCondition(), condTupleNode, null,
5348           implicitFlowTupleSet, false);
5349
5350       NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
5351
5352       newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
5353       newImplicitTupleSet.addTupleSet(condTupleNode);
5354
5355       newImplicitTupleSet.addGlobalFlowTupleSet(implicitFlowTupleSet.getGlobalLocTupleSet());
5356       newImplicitTupleSet.addGlobalFlowTupleSet(condTupleNode.getGlobalLocTupleSet());
5357
5358       if (needToGenerateInterLoc(newImplicitTupleSet)) {
5359         // need to create an intermediate node for the GLB of conditional
5360         // locations & implicit flows
5361
5362         NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
5363         for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter
5364             .hasNext();) {
5365           NTuple<Descriptor> tuple = idxIter.next();
5366           addFlowGraphEdge(md, tuple, interTuple);
5367         }
5368         newImplicitTupleSet.clear();
5369         newImplicitTupleSet.addTuple(interTuple);
5370
5371       }
5372
5373       // ///////////
5374       // System.out.println("condTupleNode="+condTupleNode);
5375       // NTuple<Descriptor> interTuple =
5376       // getFlowGraph(md).createIntermediateNode().getDescTuple();
5377       //
5378       // for (Iterator<NTuple<Descriptor>> idxIter = condTupleNode.iterator();
5379       // idxIter.hasNext();) {
5380       // NTuple<Descriptor> tuple = idxIter.next();
5381       // addFlowGraphEdge(md, tuple, interTuple);
5382       // }
5383
5384       // for (Iterator<NTuple<Descriptor>> idxIter =
5385       // implicitFlowTupleSet.iterator(); idxIter
5386       // .hasNext();) {
5387       // NTuple<Descriptor> tuple = idxIter.next();
5388       // addFlowGraphEdge(md, tuple, interTuple);
5389       // }
5390
5391       // NodeTupleSet newImplicitSet = new NodeTupleSet();
5392       // newImplicitSet.addTuple(interTuple);
5393       analyzeFlowBlockNode(md, nametable, ln.getBody(), newImplicitTupleSet);
5394       // ///////////
5395
5396       // condTupleNode.addTupleSet(implicitFlowTupleSet);
5397
5398       // add edges from condNodeTupleSet to all nodes of conditional nodes
5399       // analyzeFlowBlockNode(md, nametable, ln.getBody(), condTupleNode);
5400
5401     } else {
5402       // check 'for loop' case
5403       BlockNode bn = ln.getInitializer();
5404       bn.getVarTable().setParent(nametable);
5405       for (int i = 0; i < bn.size(); i++) {
5406         BlockStatementNode bsn = bn.get(i);
5407         analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet);
5408       }
5409
5410       NodeTupleSet condTupleNode = new NodeTupleSet();
5411       analyzeFlowExpressionNode(md, bn.getVarTable(), ln.getCondition(), condTupleNode, null,
5412           implicitFlowTupleSet, false);
5413
5414       NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
5415       newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
5416       newImplicitTupleSet.addTupleSet(condTupleNode);
5417
5418       if (needToGenerateInterLoc(newImplicitTupleSet)) {
5419         // need to create an intermediate node for the GLB of conditional
5420         // locations & implicit flows
5421
5422         NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
5423         for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter
5424             .hasNext();) {
5425           NTuple<Descriptor> tuple = idxIter.next();
5426           addFlowGraphEdge(md, tuple, interTuple);
5427         }
5428         newImplicitTupleSet.clear();
5429         newImplicitTupleSet.addTuple(interTuple);
5430
5431       }
5432
5433       // ///////////
5434       // NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
5435       //
5436       // for (Iterator<NTuple<Descriptor>> idxIter = condTupleNode.iterator(); idxIter.hasNext();) {
5437       // NTuple<Descriptor> tuple = idxIter.next();
5438       // addFlowGraphEdge(md, tuple, interTuple);
5439       // }
5440       //
5441       // for (Iterator<NTuple<Descriptor>> idxIter = implicitFlowTupleSet.iterator(); idxIter
5442       // .hasNext();) {
5443       // NTuple<Descriptor> tuple = idxIter.next();
5444       // addFlowGraphEdge(md, tuple, interTuple);
5445       // }
5446       //
5447       // NodeTupleSet newImplicitSet = new NodeTupleSet();
5448       // newImplicitSet.addTuple(interTuple);
5449       analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(), newImplicitTupleSet);
5450       analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(), newImplicitTupleSet);
5451       // ///////////
5452
5453       // condTupleNode.addTupleSet(implicitFlowTupleSet);
5454       //
5455       // analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(),
5456       // condTupleNode);
5457       // analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(),
5458       // condTupleNode);
5459
5460     }
5461
5462   }
5463
5464   private void analyzeFlowIfStatementNode(MethodDescriptor md, SymbolTable nametable,
5465       IfStatementNode isn, NodeTupleSet implicitFlowTupleSet) {
5466
5467     // System.out.println("analyzeFlowIfStatementNode=" + isn.printNode(0));
5468
5469     NodeTupleSet condTupleNode = new NodeTupleSet();
5470     analyzeFlowExpressionNode(md, nametable, isn.getCondition(), condTupleNode, null,
5471         implicitFlowTupleSet, false);
5472
5473     NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
5474
5475     newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
5476     newImplicitTupleSet.addTupleSet(condTupleNode);
5477
5478     // System.out.println("$$$GGGcondTupleNode=" + condTupleNode.getGlobalLocTupleSet());
5479     // System.out.println("-condTupleNode=" + condTupleNode);
5480     // System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet);
5481     // System.out.println("-newImplicitTupleSet=" + newImplicitTupleSet);
5482
5483     if (needToGenerateInterLoc(newImplicitTupleSet)) {
5484
5485       // need to create an intermediate node for the GLB of conditional locations & implicit flows
5486       NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
5487       for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) {
5488         NTuple<Descriptor> tuple = idxIter.next();
5489         addFlowGraphEdge(md, tuple, interTuple);
5490       }
5491       newImplicitTupleSet.clear();
5492       newImplicitTupleSet.addTuple(interTuple);
5493     }
5494
5495     // GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
5496     // for (Iterator<NTuple<Location>> iterator = condTupleNode.globalIterator();
5497     // iterator.hasNext();) {
5498     // NTuple<Location> calleeReturnLocTuple = iterator.next();
5499     // for (Iterator<NTuple<Descriptor>> iter2 = newImplicitTupleSet.iterator(); iter2.hasNext();) {
5500     // NTuple<Descriptor> callerImplicitTuple = iter2.next();
5501     // globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple,
5502     // translateToLocTuple(md, callerImplicitTuple));
5503     // }
5504     // }
5505     newImplicitTupleSet.addGlobalFlowTupleSet(condTupleNode.getGlobalLocTupleSet());
5506
5507     analyzeFlowBlockNode(md, nametable, isn.getTrueBlock(), newImplicitTupleSet);
5508
5509     if (isn.getFalseBlock() != null) {
5510       analyzeFlowBlockNode(md, nametable, isn.getFalseBlock(), newImplicitTupleSet);
5511     }
5512
5513   }
5514
5515   private void analyzeFlowDeclarationNode(MethodDescriptor md, SymbolTable nametable,
5516       DeclarationNode dn, NodeTupleSet implicitFlowTupleSet) {
5517
5518     VarDescriptor vd = dn.getVarDescriptor();
5519     mapDescToDefinitionLine.put(vd, dn.getNumLine());
5520     NTuple<Descriptor> tupleLHS = new NTuple<Descriptor>();
5521     tupleLHS.add(vd);
5522     FlowNode fn = getFlowGraph(md).createNewFlowNode(tupleLHS);
5523     fn.setDeclarationNode();
5524
5525     if (dn.getExpression() != null) {
5526       // System.out.println("-analyzeFlowDeclarationNode=" + dn.printNode(0));
5527
5528       NodeTupleSet nodeSetRHS = new NodeTupleSet();
5529       analyzeFlowExpressionNode(md, nametable, dn.getExpression(), nodeSetRHS, null,
5530           implicitFlowTupleSet, false);
5531
5532       // creates edges from RHS to LHS
5533       NTuple<Descriptor> interTuple = null;
5534       if (needToGenerateInterLoc(nodeSetRHS)) {
5535         interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
5536       }
5537
5538       for (Iterator<NTuple<Descriptor>> iter = nodeSetRHS.iterator(); iter.hasNext();) {
5539         NTuple<Descriptor> fromTuple = iter.next();
5540         // System.out.println("fromTuple=" + fromTuple + "  interTuple=" + interTuple + " tupleLSH="
5541         // + tupleLHS);
5542         addFlowGraphEdge(md, fromTuple, interTuple, tupleLHS);
5543       }
5544
5545       // creates edges from implicitFlowTupleSet to LHS
5546       for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
5547         NTuple<Descriptor> implicitTuple = iter.next();
5548         addFlowGraphEdge(md, implicitTuple, tupleLHS);
5549       }
5550
5551       GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
5552       for (Iterator<NTuple<Location>> iterator = nodeSetRHS.globalIterator(); iterator.hasNext();) {
5553         NTuple<Location> calleeReturnLocTuple = iterator.next();
5554
5555         globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, translateToLocTuple(md, tupleLHS));
5556       }
5557
5558       for (Iterator<NTuple<Location>> iterator = implicitFlowTupleSet.globalIterator(); iterator
5559           .hasNext();) {
5560         NTuple<Location> implicitGlobalTuple = iterator.next();
5561
5562         globalFlowGraph.addValueFlowEdge(implicitGlobalTuple, translateToLocTuple(md, tupleLHS));
5563       }
5564
5565       // System.out.println("-nodeSetRHS=" + nodeSetRHS);
5566       // System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet);
5567
5568     }
5569
5570   }
5571
5572   private void analyzeBlockExpressionNode(MethodDescriptor md, SymbolTable nametable,
5573       BlockExpressionNode ben, NodeTupleSet implicitFlowTupleSet) {
5574     analyzeFlowExpressionNode(md, nametable, ben.getExpression(), null, null, implicitFlowTupleSet,
5575         false);
5576   }
5577
5578   private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
5579       ExpressionNode en, NodeTupleSet nodeSet, boolean isLHS) {
5580     return analyzeFlowExpressionNode(md, nametable, en, nodeSet, null, new NodeTupleSet(), isLHS);
5581   }
5582
5583   private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
5584       ExpressionNode en, NodeTupleSet nodeSet, NTuple<Descriptor> base,
5585       NodeTupleSet implicitFlowTupleSet, boolean isLHS) {
5586
5587     // System.out.println("en=" + en.printNode(0) + "   class=" + en.getClass());
5588
5589     // note that expression node can create more than one flow node
5590     // nodeSet contains of flow nodes
5591     // base is always assigned to null except the case of a name node!
5592     NTuple<Descriptor> flowTuple;
5593     switch (en.kind()) {
5594     case Kind.AssignmentNode:
5595       analyzeFlowAssignmentNode(md, nametable, (AssignmentNode) en, nodeSet, base,
5596           implicitFlowTupleSet);
5597       break;
5598
5599     case Kind.FieldAccessNode:
5600       flowTuple =
5601           analyzeFlowFieldAccessNode(md, nametable, (FieldAccessNode) en, nodeSet, base,
5602               implicitFlowTupleSet, isLHS);
5603       if (flowTuple != null) {
5604         nodeSet.addTuple(flowTuple);
5605       }
5606       return flowTuple;
5607
5608     case Kind.NameNode:
5609       NodeTupleSet nameNodeSet = new NodeTupleSet();
5610       flowTuple =
5611           analyzeFlowNameNode(md, nametable, (NameNode) en, nameNodeSet, base, implicitFlowTupleSet);
5612       if (flowTuple != null) {
5613         nodeSet.addTuple(flowTuple);
5614       }
5615       return flowTuple;
5616
5617     case Kind.OpNode:
5618       analyzeFlowOpNode(md, nametable, (OpNode) en, nodeSet, implicitFlowTupleSet);
5619       break;
5620
5621     case Kind.CreateObjectNode:
5622       analyzeCreateObjectNode(md, nametable, (CreateObjectNode) en, nodeSet, implicitFlowTupleSet);
5623       break;
5624
5625     case Kind.ArrayAccessNode:
5626       analyzeFlowArrayAccessNode(md, nametable, (ArrayAccessNode) en, nodeSet, isLHS);
5627       break;
5628
5629     case Kind.LiteralNode:
5630       analyzeFlowLiteralNode(md, nametable, (LiteralNode) en, nodeSet);
5631       break;
5632
5633     case Kind.MethodInvokeNode:
5634       analyzeFlowMethodInvokeNode(md, nametable, (MethodInvokeNode) en, nodeSet,
5635           implicitFlowTupleSet);
5636       break;
5637
5638     case Kind.TertiaryNode:
5639       analyzeFlowTertiaryNode(md, nametable, (TertiaryNode) en, nodeSet, implicitFlowTupleSet);
5640       break;
5641
5642     case Kind.CastNode:
5643       analyzeFlowCastNode(md, nametable, (CastNode) en, nodeSet, base, implicitFlowTupleSet);
5644       break;
5645     // case Kind.InstanceOfNode:
5646     // checkInstanceOfNode(md, nametable, (InstanceOfNode) en, td);
5647     // return null;
5648
5649     // case Kind.ArrayInitializerNode:
5650     // checkArrayInitializerNode(md, nametable, (ArrayInitializerNode) en,
5651     // td);
5652     // return null;
5653
5654     // case Kind.ClassTypeNode:
5655     // checkClassTypeNode(md, nametable, (ClassTypeNode) en, td);
5656     // return null;
5657
5658     // case Kind.OffsetNode:
5659     // checkOffsetNode(md, nametable, (OffsetNode)en, td);
5660     // return null;
5661
5662     }
5663
5664     return null;
5665
5666   }
5667
5668   private void analyzeFlowCastNode(MethodDescriptor md, SymbolTable nametable, CastNode cn,
5669       NodeTupleSet nodeSet, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
5670
5671     analyzeFlowExpressionNode(md, nametable, cn.getExpression(), nodeSet, base,
5672         implicitFlowTupleSet, false);
5673
5674   }
5675
5676   private void analyzeFlowTertiaryNode(MethodDescriptor md, SymbolTable nametable, TertiaryNode tn,
5677       NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
5678
5679     // System.out.println("analyzeFlowTertiaryNode=" + tn.printNode(0));
5680
5681     NodeTupleSet tertiaryTupleNode = new NodeTupleSet();
5682     analyzeFlowExpressionNode(md, nametable, tn.getCond(), tertiaryTupleNode, null,
5683         implicitFlowTupleSet, false);
5684
5685     NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
5686     newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
5687     newImplicitTupleSet.addTupleSet(tertiaryTupleNode);
5688
5689     // System.out.println("$$$GGGcondTupleNode=" + tertiaryTupleNode.getGlobalLocTupleSet());
5690     // System.out.println("-tertiaryTupleNode=" + tertiaryTupleNode);
5691     // System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet);
5692     // System.out.println("-newImplicitTupleSet=" + newImplicitTupleSet);
5693
5694     if (needToGenerateInterLoc(newImplicitTupleSet)) {
5695       // need to create an intermediate node for the GLB of conditional locations & implicit flows
5696       NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
5697       for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) {
5698         NTuple<Descriptor> tuple = idxIter.next();
5699         addFlowGraphEdge(md, tuple, interTuple);
5700       }
5701       newImplicitTupleSet.clear();
5702       newImplicitTupleSet.addTuple(interTuple);
5703     }
5704
5705     newImplicitTupleSet.addGlobalFlowTupleSet(tertiaryTupleNode.getGlobalLocTupleSet());
5706
5707     // System.out.println("---------newImplicitTupleSet=" + newImplicitTupleSet);
5708
5709     // add edges from tertiaryTupleNode to all nodes of conditional nodes
5710     // tertiaryTupleNode.addTupleSet(implicitFlowTupleSet);
5711     analyzeFlowExpressionNode(md, nametable, tn.getTrueExpr(), tertiaryTupleNode, null,
5712         newImplicitTupleSet, false);
5713
5714     analyzeFlowExpressionNode(md, nametable, tn.getFalseExpr(), tertiaryTupleNode, null,
5715         newImplicitTupleSet, false);
5716
5717     nodeSet.addGlobalFlowTupleSet(tertiaryTupleNode.getGlobalLocTupleSet());
5718     nodeSet.addTupleSet(tertiaryTupleNode);
5719
5720     // System.out.println("#tertiary node set=" + nodeSet);
5721   }
5722
5723   private void addMapCallerMethodDescToMethodInvokeNodeSet(MethodDescriptor caller,
5724       MethodInvokeNode min) {
5725     Set<MethodInvokeNode> set = mapMethodDescriptorToMethodInvokeNodeSet.get(caller);
5726     if (set == null) {
5727       set = new HashSet<MethodInvokeNode>();
5728       mapMethodDescriptorToMethodInvokeNodeSet.put(caller, set);
5729     }
5730     set.add(min);
5731   }
5732
5733   private void addParamNodeFlowingToReturnValue(MethodDescriptor md, FlowNode fn) {
5734
5735     if (!mapMethodDescToParamNodeFlowsToReturnValue.containsKey(md)) {
5736       mapMethodDescToParamNodeFlowsToReturnValue.put(md, new HashSet<FlowNode>());
5737     }
5738     mapMethodDescToParamNodeFlowsToReturnValue.get(md).add(fn);
5739   }
5740
5741   private Set<FlowNode> getParamNodeFlowingToReturnValue(MethodDescriptor md) {
5742
5743     if (!mapMethodDescToParamNodeFlowsToReturnValue.containsKey(md)) {
5744       mapMethodDescToParamNodeFlowsToReturnValue.put(md, new HashSet<FlowNode>());
5745     }
5746
5747     return mapMethodDescToParamNodeFlowsToReturnValue.get(md);
5748   }
5749
5750   private Set<NTuple<Location>> getPCLocTupleSet(MethodInvokeNode min) {
5751     if (!mapMethodInvokeNodeToPCLocTupleSet.containsKey(min)) {
5752       mapMethodInvokeNodeToPCLocTupleSet.put(min, new HashSet<NTuple<Location>>());
5753     }
5754     return mapMethodInvokeNodeToPCLocTupleSet.get(min);
5755   }
5756
5757   private void analyzeFlowMethodInvokeNode(MethodDescriptor mdCaller, SymbolTable nametable,
5758       MethodInvokeNode min, NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
5759
5760     // System.out.println("analyzeFlowMethodInvokeNode=" + min.printNode(0));
5761
5762     if (!toanalyze_methodDescList.contains(min.getMethod())) {
5763       return;
5764     }
5765
5766     addMapMethodDescToMethodInvokeNodeSet(min);
5767
5768     Set<NTuple<Location>> pcLocTupleSet = getPCLocTupleSet(min);
5769     for (Iterator iterator = implicitFlowTupleSet.iterator(); iterator.hasNext();) {
5770       NTuple<Descriptor> pcDescTuple = (NTuple<Descriptor>) iterator.next();
5771       if (!pcDescTuple.get(0).equals(LITERALDESC)) {
5772         // here we don't need to add the literal value as a PC location
5773         pcLocTupleSet.add(translateToLocTuple(mdCaller, pcDescTuple));
5774       }
5775     }
5776
5777     mapMethodInvokeNodeToArgIdxMap.put(min, new HashMap<Integer, NTuple<Descriptor>>());
5778
5779     if (nodeSet == null) {
5780       nodeSet = new NodeTupleSet();
5781     }
5782
5783     MethodDescriptor mdCallee = min.getMethod();
5784
5785     NameDescriptor baseName = min.getBaseName();
5786     boolean isSystemout = false;
5787     if (baseName != null) {
5788       isSystemout = baseName.getSymbol().equals("System.out");
5789     }
5790
5791     if (!ssjava.isSSJavaUtil(mdCallee.getClassDesc()) && !ssjava.isTrustMethod(mdCallee)
5792         && !isSystemout) {
5793
5794       addMapCallerMethodDescToMethodInvokeNodeSet(mdCaller, min);
5795
5796       FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
5797       // System.out.println("mdCallee=" + mdCallee + " calleeFlowGraph=" + calleeFlowGraph);
5798       Set<FlowNode> calleeReturnSet = calleeFlowGraph.getReturnNodeSet();
5799
5800       // System.out.println("---calleeReturnSet=" + calleeReturnSet);
5801
5802       NodeTupleSet tupleSet = new NodeTupleSet();
5803
5804       if (min.getExpression() != null) {
5805
5806         NodeTupleSet baseNodeSet = new NodeTupleSet();
5807         analyzeFlowExpressionNode(mdCaller, nametable, min.getExpression(), baseNodeSet, null,
5808             implicitFlowTupleSet, false);
5809         // System.out.println("baseNodeSet=" + baseNodeSet);
5810
5811         assert (baseNodeSet.size() == 1);
5812         NTuple<Descriptor> baseTuple = baseNodeSet.iterator().next();
5813         if (baseTuple.get(0) instanceof InterDescriptor) {
5814           if (baseTuple.size() > 1) {
5815             throw new Error();
5816           }
5817           FlowNode interNode = getFlowGraph(mdCaller).getFlowNode(baseTuple);
5818           baseTuple = translateBaseTuple(interNode, baseTuple);
5819         }
5820         mapMethodInvokeNodeToBaseTuple.put(min, baseTuple);
5821
5822         if (!min.getMethod().isStatic()) {
5823           addArgIdxMap(min, 0, baseTuple);
5824
5825           for (Iterator iterator = calleeReturnSet.iterator(); iterator.hasNext();) {
5826             FlowNode returnNode = (FlowNode) iterator.next();
5827             NTuple<Descriptor> returnDescTuple = returnNode.getDescTuple();
5828             if (returnDescTuple.startsWith(mdCallee.getThis())) {
5829               // the location type of the return value is started with 'this'
5830               // reference
5831               NTuple<Descriptor> inFlowTuple = new NTuple<Descriptor>(baseTuple.getList());
5832
5833               if (inFlowTuple.get(0) instanceof InterDescriptor) {
5834                 // min.getExpression()
5835               } else {
5836
5837               }
5838
5839               inFlowTuple.addAll(returnDescTuple.subList(1, returnDescTuple.size()));
5840               // nodeSet.addTuple(inFlowTuple);
5841               // System.out.println("1CREATE A NEW TUPLE=" + inFlowTuple + "  from="
5842               // + mdCallee.getThis());
5843               // tupleSet.addTuple(inFlowTuple);
5844               tupleSet.addTuple(baseTuple);
5845             } else {
5846               // TODO
5847               // System.out.println("returnNode=" + returnNode);
5848               Set<FlowNode> inFlowSet = calleeFlowGraph.getIncomingFlowNodeSet(returnNode);
5849               // System.out.println("inFlowSet=" + inFlowSet + "   from retrunNode=" + returnNode);
5850               for (Iterator iterator2 = inFlowSet.iterator(); iterator2.hasNext();) {
5851                 FlowNode inFlowNode = (FlowNode) iterator2.next();
5852                 if (inFlowNode.getDescTuple().startsWith(mdCallee.getThis())) {
5853                   // nodeSet.addTupleSet(baseNodeSet);
5854                   // System.out.println("2CREATE A NEW TUPLE=" + baseNodeSet + "  from="
5855                   // + mdCallee.getThis());
5856                   tupleSet.addTupleSet(baseNodeSet);
5857                 }
5858               }
5859             }
5860           }
5861         }
5862
5863       }
5864       // analyze parameter flows
5865
5866       if (min.numArgs() > 0) {
5867
5868         int offset;
5869         if (min.getMethod().isStatic()) {
5870           offset = 0;
5871         } else {
5872           offset = 1;
5873         }
5874
5875         for (int i = 0; i < min.numArgs(); i++) {
5876           ExpressionNode en = min.getArg(i);
5877           int idx = i + offset;
5878           NodeTupleSet argTupleSet = new NodeTupleSet();
5879           analyzeFlowExpressionNode(mdCaller, nametable, en, argTupleSet, false);
5880           // if argument is liternal node, argTuple is set to NULL
5881           // System.out.println("---arg idx=" + idx + "   argTupleSet=" + argTupleSet);
5882           NTuple<Descriptor> argTuple = generateArgTuple(mdCaller, argTupleSet);
5883
5884           // if an argument is literal value,
5885           // we need to create an itermediate node so that we could assign a composite location to
5886           // that node if needed
5887           if (argTuple.size() > 0
5888               && (argTuple.get(0).equals(GLOBALDESC) || argTuple.get(0).equals(LITERALDESC))) {
5889             /*
5890              * System.out.println("***GLOBAL ARG TUPLE CASE=" + argTuple); System.out.println("8");
5891              *
5892              * NTuple<Descriptor> interTuple =
5893              * getFlowGraph(mdCaller).createIntermediateNode().getDescTuple(); ((InterDescriptor)
5894              * interTuple.get(0)).setMethodArgIdxPair(min, idx); addFlowGraphEdge(mdCaller,
5895              * argTuple, interTuple); argTuple = interTuple; addArgIdxMap(min, idx, argTuple);
5896              * System.out.println("new min mapping i=" + idx + "  ->" + argTuple);
5897              */
5898             argTuple = new NTuple<Descriptor>();
5899           }
5900
5901           addArgIdxMap(min, idx, argTuple);
5902
5903           FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx);
5904
5905           // check whether a param node in the callee graph has incoming flows
5906           // if it has incoming flows, the corresponding arg should be lower than the current PC
5907           // Descriptor prefix = paramNode.getDescTuple().get(0);
5908           // if (calleeFlowGraph.getIncomingNodeSetByPrefix(prefix).size() > 0) {
5909           // for (Iterator<NTuple<Descriptor>> iterator = implicitFlowTupleSet.iterator(); iterator
5910           // .hasNext();) {
5911           // NTuple<Descriptor> pcTuple = iterator.next();
5912           // System.out.println("add edge pcTuple =" + pcTuple + " -> " + argTuple);
5913           // addFlowGraphEdge(md, pcTuple, argTuple);
5914           // }
5915           // }
5916
5917           // System.out.println("paramNode=" + paramNode + "  calleeReturnSet=" + calleeReturnSet);
5918           if (hasInFlowTo(calleeFlowGraph, paramNode, calleeReturnSet)
5919               || mdCallee.getModifiers().isNative()) {
5920             addParamNodeFlowingToReturnValue(mdCallee, paramNode);
5921             // nodeSet.addTupleSet(argTupleSet);
5922             // System.out.println("3CREATE A NEW TUPLE=" + argTupleSet + "  from=" + paramNode);
5923             tupleSet.addTupleSet(argTupleSet);
5924           }
5925         }
5926
5927       }
5928
5929       if (mdCallee.getReturnType() != null && !mdCallee.getReturnType().isVoid()) {
5930         FlowReturnNode returnHolderNode = getFlowGraph(mdCaller).createReturnNode(min);
5931
5932         if (needToGenerateInterLoc(tupleSet)) {
5933           FlowGraph fg = getFlowGraph(mdCaller);
5934           FlowNode interNode = fg.createIntermediateNode();
5935           interNode.setFormHolder(true);
5936
5937           NTuple<Descriptor> interTuple = interNode.getDescTuple();
5938
5939           for (Iterator iterator = tupleSet.iterator(); iterator.hasNext();) {
5940             NTuple<Descriptor> tuple = (NTuple<Descriptor>) iterator.next();
5941
5942             Set<NTuple<Descriptor>> addSet = new HashSet<NTuple<Descriptor>>();
5943             FlowNode node = fg.getFlowNode(tuple);
5944             if (node instanceof FlowReturnNode) {
5945               addSet.addAll(fg.getReturnTupleSet(((FlowReturnNode) node).getReturnTupleSet()));
5946             } else {
5947               addSet.add(tuple);
5948             }
5949             for (Iterator iterator2 = addSet.iterator(); iterator2.hasNext();) {
5950               NTuple<Descriptor> higher = (NTuple<Descriptor>) iterator2.next();
5951               addFlowGraphEdge(mdCaller, higher, interTuple);
5952             }
5953           }
5954
5955           returnHolderNode.addTuple(interTuple);
5956
5957           nodeSet.addTuple(interTuple);
5958           // System.out.println("ADD TUPLESET=" + interTuple + " to returnnode=" +
5959           // returnHolderNode);
5960
5961         } else {
5962           returnHolderNode.addTupleSet(tupleSet);
5963           // System.out.println("ADD TUPLESET=" + tupleSet + " to returnnode=" + returnHolderNode);
5964         }
5965         // setNode.addTupleSet(tupleSet);
5966         // NodeTupleSet setFromReturnNode=new NodeTupleSet();
5967         // setFromReturnNode.addTuple(tuple);
5968
5969         NodeTupleSet holderTupleSet =
5970             getNodeTupleSetFromReturnNode(getFlowGraph(mdCaller), returnHolderNode);
5971
5972         // System.out.println("HOLDER TUPLE SET=" + holderTupleSet);
5973         nodeSet.addTupleSet(holderTupleSet);
5974
5975         nodeSet.addTuple(returnHolderNode.getDescTuple());
5976       }
5977
5978       // propagateFlowsFromCallee(min, md, min.getMethod());
5979
5980       // when generating the global flow graph,
5981       // we need to add ordering relations from the set of callee return loc tuple to LHS of the
5982       // caller assignment
5983       for (Iterator iterator = calleeReturnSet.iterator(); iterator.hasNext();) {
5984         FlowNode calleeReturnNode = (FlowNode) iterator.next();
5985         NTuple<Location> calleeReturnLocTuple =
5986             translateToLocTuple(mdCallee, calleeReturnNode.getDescTuple());
5987         // System.out.println("calleeReturnLocTuple=" + calleeReturnLocTuple);
5988         NTuple<Location> transaltedToCaller =
5989             translateToCallerLocTuple(min, mdCallee, mdCaller, calleeReturnLocTuple);
5990         // System.out.println("translateToCallerLocTuple="
5991         // + translateToCallerLocTuple(min, mdCallee, mdCaller, calleeReturnLocTuple));
5992         if (transaltedToCaller.size() > 0) {
5993           nodeSet.addGlobalFlowTuple(translateToCallerLocTuple(min, mdCallee, mdCaller,
5994               calleeReturnLocTuple));
5995         }
5996       }
5997
5998       // System.out.println("min nodeSet=" + nodeSet);
5999
6000     }
6001
6002   }
6003
6004   private NodeTupleSet getNodeTupleSetFromReturnNode(FlowGraph fg, FlowReturnNode node) {
6005     NodeTupleSet nts = new NodeTupleSet();
6006
6007     Set<NTuple<Descriptor>> returnSet = node.getReturnTupleSet();
6008
6009     for (Iterator iterator = returnSet.iterator(); iterator.hasNext();) {
6010       NTuple<Descriptor> tuple = (NTuple<Descriptor>) iterator.next();
6011       FlowNode flowNode = fg.getFlowNode(tuple);
6012       if (flowNode instanceof FlowReturnNode) {
6013         returnSet.addAll(recurGetNode(fg, (FlowReturnNode) flowNode));
6014       } else {
6015         returnSet.add(tuple);
6016       }
6017     }
6018
6019     for (Iterator iterator = returnSet.iterator(); iterator.hasNext();) {
6020       NTuple<Descriptor> nTuple = (NTuple<Descriptor>) iterator.next();
6021       nts.addTuple(nTuple);
6022     }
6023
6024     return nts;
6025
6026   }
6027
6028   private Set<NTuple<Descriptor>> recurGetNode(FlowGraph fg, FlowReturnNode rnode) {
6029
6030     Set<NTuple<Descriptor>> tupleSet = new HashSet<NTuple<Descriptor>>();
6031
6032     Set<NTuple<Descriptor>> returnSet = rnode.getReturnTupleSet();
6033     for (Iterator iterator = returnSet.iterator(); iterator.hasNext();) {
6034       NTuple<Descriptor> tuple = (NTuple<Descriptor>) iterator.next();
6035       FlowNode flowNode = fg.getFlowNode(tuple);
6036       if (flowNode instanceof FlowReturnNode) {
6037         tupleSet.addAll(recurGetNode(fg, (FlowReturnNode) flowNode));
6038       }
6039       tupleSet.add(tuple);
6040     }
6041
6042     return tupleSet;
6043   }
6044
6045   private NTuple<Descriptor> generateArgTuple(MethodDescriptor mdCaller, NodeTupleSet argTupleSet) {
6046
6047     int size = 0;
6048
6049     // if argTupleSet is empty, it comes from the top location
6050     if (argTupleSet.size() == 0) {
6051       NTuple<Descriptor> descTuple = new NTuple<Descriptor>();
6052       descTuple.add(LITERALDESC);
6053       return descTuple;
6054     }
6055
6056     Set<NTuple<Descriptor>> argTupleSetNonLiteral = new HashSet<NTuple<Descriptor>>();
6057
6058     for (Iterator<NTuple<Descriptor>> iter = argTupleSet.iterator(); iter.hasNext();) {
6059       NTuple<Descriptor> descTuple = iter.next();
6060       if (!descTuple.get(0).equals(LITERALDESC)) {
6061         argTupleSetNonLiteral.add(descTuple);
6062       }
6063     }
6064
6065     if (argTupleSetNonLiteral.size() > 1) {
6066
6067       NTuple<Descriptor> interTuple =
6068           getFlowGraph(mdCaller).createIntermediateNode().getDescTuple();
6069       for (Iterator<NTuple<Descriptor>> idxIter = argTupleSet.iterator(); idxIter.hasNext();) {
6070         NTuple<Descriptor> tuple = idxIter.next();
6071         addFlowGraphEdge(mdCaller, tuple, interTuple);
6072       }
6073       return interTuple;
6074     } else if (argTupleSetNonLiteral.size() == 1) {
6075       return argTupleSetNonLiteral.iterator().next();
6076     } else {
6077       return argTupleSet.iterator().next();
6078     }
6079
6080   }
6081
6082   private boolean hasInFlowTo(FlowGraph fg, FlowNode inNode, Set<FlowNode> nodeSet) {
6083     // return true if inNode has in-flows to nodeSet
6084
6085     if (nodeSet.contains(inNode)) {
6086       // in this case, the method directly returns a parameter variable.
6087       return true;
6088     }
6089     // Set<FlowNode> reachableSet = fg.getReachFlowNodeSetFrom(inNode);
6090     Set<FlowNode> reachableSet = fg.getReachableSetFrom(inNode.getDescTuple());
6091     // System.out.println("inNode=" + inNode + "  reachalbeSet=" + reachableSet);
6092
6093     for (Iterator iterator = reachableSet.iterator(); iterator.hasNext();) {
6094       FlowNode fn = (FlowNode) iterator.next();
6095       if (nodeSet.contains(fn)) {
6096         return true;
6097       }
6098     }
6099     return false;
6100   }
6101
6102   private NTuple<Descriptor> getNodeTupleByArgIdx(MethodInvokeNode min, int idx) {
6103     return mapMethodInvokeNodeToArgIdxMap.get(min).get(new Integer(idx));
6104   }
6105
6106   private void addArgIdxMap(MethodInvokeNode min, int idx, NTuple<Descriptor> argTuple /*
6107                                                                                         * NodeTupleSet
6108                                                                                         * tupleSet
6109                                                                                         */) {
6110     Map<Integer, NTuple<Descriptor>> mapIdxToTuple = mapMethodInvokeNodeToArgIdxMap.get(min);
6111     if (mapIdxToTuple == null) {
6112       mapIdxToTuple = new HashMap<Integer, NTuple<Descriptor>>();
6113       mapMethodInvokeNodeToArgIdxMap.put(min, mapIdxToTuple);
6114     }
6115     mapIdxToTuple.put(new Integer(idx), argTuple);
6116   }
6117
6118   private void analyzeFlowLiteralNode(MethodDescriptor md, SymbolTable nametable, LiteralNode en,
6119       NodeTupleSet nodeSet) {
6120     NTuple<Descriptor> tuple = new NTuple<Descriptor>();
6121     tuple.add(LITERALDESC);
6122     nodeSet.addTuple(tuple);
6123   }
6124
6125   private void analyzeFlowArrayAccessNode(MethodDescriptor md, SymbolTable nametable,
6126       ArrayAccessNode aan, NodeTupleSet nodeSet, boolean isLHS) {
6127
6128     // System.out.println("analyzeFlowArrayAccessNode aan=" + aan.printNode(0));
6129     String currentArrayAccessNodeExpStr = aan.printNode(0);
6130     arrayAccessNodeStack.push(aan.printNode(0));
6131
6132     NodeTupleSet expNodeTupleSet = new NodeTupleSet();
6133     NTuple<Descriptor> base =
6134         analyzeFlowExpressionNode(md, nametable, aan.getExpression(), expNodeTupleSet, isLHS);
6135     // System.out.println("-base=" + base);
6136
6137     nodeSet.setMethodInvokeBaseDescTuple(base);
6138     NodeTupleSet idxNodeTupleSet = new NodeTupleSet();
6139     analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, isLHS);
6140
6141     arrayAccessNodeStack.pop();
6142
6143     if (isLHS) {
6144       // need to create an edge from idx to array
6145       for (Iterator<NTuple<Descriptor>> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) {
6146         NTuple<Descriptor> idxTuple = idxIter.next();
6147         for (Iterator<NTuple<Descriptor>> arrIter = expNodeTupleSet.iterator(); arrIter.hasNext();) {
6148           NTuple<Descriptor> arrTuple = arrIter.next();
6149           getFlowGraph(md).addValueFlowEdge(idxTuple, arrTuple);
6150         }
6151       }
6152
6153       GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
6154       for (Iterator<NTuple<Location>> iterator = idxNodeTupleSet.globalIterator(); iterator
6155           .hasNext();) {
6156         NTuple<Location> calleeReturnLocTuple = iterator.next();
6157         for (Iterator<NTuple<Descriptor>> arrIter = expNodeTupleSet.iterator(); arrIter.hasNext();) {
6158           NTuple<Descriptor> arrTuple = arrIter.next();
6159
6160           globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, translateToLocTuple(md, arrTuple));
6161         }
6162       }
6163
6164       nodeSet.addTupleSet(expNodeTupleSet);
6165     } else {
6166
6167       NodeTupleSet nodeSetArrayAccessExp = new NodeTupleSet();
6168
6169       nodeSetArrayAccessExp.addTupleSet(expNodeTupleSet);
6170       nodeSetArrayAccessExp.addTupleSet(idxNodeTupleSet);
6171
6172       if (arrayAccessNodeStack.isEmpty()
6173           || !arrayAccessNodeStack.peek().startsWith(currentArrayAccessNodeExpStr)) {
6174
6175         if (needToGenerateInterLoc(nodeSetArrayAccessExp)) {
6176           FlowNode interNode = getFlowGraph(md).createIntermediateNode();
6177           NTuple<Descriptor> interTuple = interNode.getDescTuple();
6178
6179           for (Iterator<NTuple<Descriptor>> iter = nodeSetArrayAccessExp.iterator(); iter.hasNext();) {
6180             NTuple<Descriptor> higherTuple = iter.next();
6181             addFlowGraphEdge(md, higherTuple, interTuple);
6182           }
6183           nodeSetArrayAccessExp.clear();
6184           nodeSetArrayAccessExp.addTuple(interTuple);
6185           FlowGraph fg = getFlowGraph(md);
6186
6187           // System.out.println("base=" + base);
6188           if (base != null) {
6189             fg.addMapInterLocNodeToEnclosingDescriptor(interTuple.get(0),
6190                 getClassTypeDescriptor(base.get(base.size() - 1)));
6191             interNode.setBaseTuple(base);
6192           }
6193         }
6194       }
6195
6196       nodeSet.addGlobalFlowTupleSet(idxNodeTupleSet.getGlobalLocTupleSet());
6197       nodeSet.addTupleSet(nodeSetArrayAccessExp);
6198
6199     }
6200
6201   }
6202
6203   private void analyzeCreateObjectNode(MethodDescriptor md, SymbolTable nametable,
6204       CreateObjectNode en, NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
6205     // System.out.println("#analyzeCreateObjectNode=" + en.printNode(0));
6206     int numArgs = en.numArgs();
6207     NodeTupleSet argSet = new NodeTupleSet();
6208
6209     for (int i = 0; i < numArgs; i++) {
6210       analyzeFlowExpressionNode(md, nametable, en.getArg(i), argSet, null, implicitFlowTupleSet,
6211           false);
6212     }
6213
6214     // System.out.println("###argSet=" + argSet);
6215     nodeSet.addTupleSet(argSet);
6216
6217   }
6218
6219   private void analyzeFlowOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on,
6220       NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
6221
6222     NodeTupleSet leftOpSet = new NodeTupleSet();
6223     NodeTupleSet rightOpSet = new NodeTupleSet();
6224
6225     // System.out.println("analyzeFlowOpNode=" + on.printNode(0));
6226
6227     // left operand
6228     analyzeFlowExpressionNode(md, nametable, on.getLeft(), leftOpSet, null, implicitFlowTupleSet,
6229         false);
6230
6231     if (on.getRight() != null) {
6232       // right operand
6233       analyzeFlowExpressionNode(md, nametable, on.getRight(), rightOpSet, null,
6234           implicitFlowTupleSet, false);
6235     }
6236
6237     Operation op = on.getOp();
6238
6239     switch (op.getOp()) {
6240
6241     case Operation.UNARYPLUS:
6242     case Operation.UNARYMINUS:
6243     case Operation.LOGIC_NOT:
6244       // single operand
6245       nodeSet.addTupleSet(leftOpSet);
6246       break;
6247
6248     case Operation.LOGIC_OR:
6249     case Operation.LOGIC_AND:
6250     case Operation.COMP:
6251     case Operation.BIT_OR:
6252     case Operation.BIT_XOR:
6253     case Operation.BIT_AND:
6254     case Operation.ISAVAILABLE:
6255     case Operation.EQUAL:
6256     case Operation.NOTEQUAL:
6257     case Operation.LT:
6258     case Operation.GT:
6259     case Operation.LTE:
6260     case Operation.GTE:
6261     case Operation.ADD:
6262     case Operation.SUB:
6263     case Operation.MULT:
6264     case Operation.DIV:
6265     case Operation.MOD:
6266     case Operation.LEFTSHIFT:
6267     case Operation.RIGHTSHIFT:
6268     case Operation.URIGHTSHIFT:
6269
6270       // there are two operands
6271       nodeSet.addTupleSet(leftOpSet);
6272       nodeSet.addTupleSet(rightOpSet);
6273
6274       nodeSet.addGlobalFlowTupleSet(leftOpSet.getGlobalLocTupleSet());
6275       nodeSet.addGlobalFlowTupleSet(rightOpSet.getGlobalLocTupleSet());
6276
6277       break;
6278
6279     default:
6280       throw new Error(op.toString());
6281     }
6282
6283   }
6284
6285   private NTuple<Descriptor> analyzeFlowNameNode(MethodDescriptor md, SymbolTable nametable,
6286       NameNode nn, NodeTupleSet nodeSet, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
6287
6288     if (base == null) {
6289       base = new NTuple<Descriptor>();
6290     }
6291
6292     NameDescriptor nd = nn.getName();
6293
6294     if (nd.getBase() != null) {
6295       base =
6296           analyzeFlowExpressionNode(md, nametable, nn.getExpression(), nodeSet, base,
6297               implicitFlowTupleSet, false);
6298       if (base == null) {
6299         // base node has the top location
6300         return base;
6301       }
6302     } else {
6303       String varname = nd.toString();
6304       if (varname.equals("this")) {
6305         // 'this' itself!
6306         base.add(md.getThis());
6307         return base;
6308       }
6309
6310       Descriptor d = (Descriptor) nametable.get(varname);
6311
6312       if (d instanceof VarDescriptor) {
6313         VarDescriptor vd = (VarDescriptor) d;
6314         base.add(vd);
6315       } else if (d instanceof FieldDescriptor) {
6316         // the type of field descriptor has a location!
6317         FieldDescriptor fd = (FieldDescriptor) d;
6318         if (fd.isStatic()) {
6319           if (fd.isFinal()) {
6320             // if it is 'static final', no need to have flow node for the TOP
6321             // location
6322             return null;
6323           } else {
6324             // if 'static', assign the default GLOBAL LOCATION to the first
6325             // element of the tuple
6326             base.add(GLOBALDESC);
6327           }
6328         } else {
6329           // the location of field access starts from this, followed by field
6330           // location
6331           base.add(md.getThis());
6332         }
6333
6334         base.add(fd);
6335       } else if (d == null) {
6336         // access static field
6337         base.add(GLOBALDESC);
6338         base.add(nn.getField());
6339         return base;
6340
6341         // FieldDescriptor fd = nn.getField();addFlowGraphEdge
6342         //
6343         // MethodLattice<String> localLattice = ssjava.getMethodLattice(md);
6344         // String globalLocId = localLattice.getGlobalLoc();
6345         // if (globalLocId == null) {
6346         // throw new
6347         // Error("Method lattice does not define global variable location at "
6348         // + generateErrorMessage(md.getClassDesc(), nn));
6349         // }
6350         // loc.addLocation(new Location(md, globalLocId));
6351         //
6352         // Location fieldLoc = (Location) fd.getType().getExtension();
6353         // loc.addLocation(fieldLoc);
6354         //
6355         // return loc;
6356
6357       }
6358     }
6359     getFlowGraph(md).createNewFlowNode(base);
6360
6361     return base;
6362
6363   }
6364
6365   private NTuple<Descriptor> analyzeFlowFieldAccessNode(MethodDescriptor md, SymbolTable nametable,
6366       FieldAccessNode fan, NodeTupleSet nodeSet, NTuple<Descriptor> base,
6367       NodeTupleSet implicitFlowTupleSet, boolean isLHS) {
6368     // System.out.println("analyzeFlowFieldAccessNode=" + fan.printNode(0));
6369
6370     String currentArrayAccessNodeExpStr = null;
6371     ExpressionNode left = fan.getExpression();
6372     TypeDescriptor ltd = left.getType();
6373     FieldDescriptor fd = fan.getField();
6374     ArrayAccessNode aan = null;
6375
6376     String varName = null;
6377     if (left.kind() == Kind.NameNode) {
6378       NameDescriptor nd = ((NameNode) left).getName();
6379       varName = nd.toString();
6380     }
6381
6382     if (ltd.isClassNameRef() || (varName != null && varName.equals("this"))) {
6383       // using a class name directly or access using this
6384       if (fd.isStatic() && fd.isFinal()) {
6385         return null;
6386       }
6387     }
6388
6389     NodeTupleSet idxNodeTupleSet = new NodeTupleSet();
6390
6391     boolean isArrayCase = false;
6392     if (left instanceof ArrayAccessNode) {
6393
6394       isArrayCase = true;
6395       aan = (ArrayAccessNode) left;
6396
6397       currentArrayAccessNodeExpStr = aan.printNode(0);
6398       arrayAccessNodeStack.push(currentArrayAccessNodeExpStr);
6399
6400       left = aan.getExpression();
6401       analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, base,
6402           implicitFlowTupleSet, isLHS);
6403
6404     }
6405     base =
6406         analyzeFlowExpressionNode(md, nametable, left, nodeSet, base, implicitFlowTupleSet, isLHS);
6407
6408     if (base == null) {
6409       // in this case, field is TOP location
6410       return null;
6411     } else {
6412
6413       NTuple<Descriptor> flowFieldTuple = new NTuple<Descriptor>(base.toList());
6414
6415       if (!left.getType().isPrimitive()) {
6416         if (!fd.getSymbol().equals("length")) {
6417           // array.length access, just have the location of the array
6418           flowFieldTuple.add(fd);
6419           nodeSet.removeTuple(base);
6420         }
6421       }
6422       getFlowGraph(md).createNewFlowNode(flowFieldTuple);
6423
6424       if (isLHS) {
6425         for (Iterator<NTuple<Descriptor>> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) {
6426           NTuple<Descriptor> idxTuple = idxIter.next();
6427           getFlowGraph(md).addValueFlowEdge(idxTuple, flowFieldTuple);
6428         }
6429
6430         GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
6431         for (Iterator<NTuple<Location>> iterator = idxNodeTupleSet.globalIterator(); iterator
6432             .hasNext();) {
6433           NTuple<Location> calleeReturnLocTuple = iterator.next();
6434
6435           globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple,
6436               translateToLocTuple(md, flowFieldTuple));
6437         }
6438
6439       } else {
6440         nodeSet.addTupleSet(idxNodeTupleSet);
6441
6442         // if it is the array case and not the LHS case
6443         if (isArrayCase) {
6444           arrayAccessNodeStack.pop();
6445
6446           if (arrayAccessNodeStack.isEmpty()
6447               || !arrayAccessNodeStack.peek().startsWith(currentArrayAccessNodeExpStr)) {
6448             NodeTupleSet nodeSetArrayAccessExp = new NodeTupleSet();
6449
6450             nodeSetArrayAccessExp.addTuple(flowFieldTuple);
6451             nodeSetArrayAccessExp.addTupleSet(idxNodeTupleSet);
6452             nodeSetArrayAccessExp.addTupleSet(nodeSet);
6453
6454             if (needToGenerateInterLoc(nodeSetArrayAccessExp)) {
6455               // System.out.println("nodeSetArrayAccessExp=" + nodeSetArrayAccessExp);
6456               // System.out.println("idxNodeTupleSet.getGlobalLocTupleSet()="
6457               // + idxNodeTupleSet.getGlobalLocTupleSet());
6458
6459               NTuple<Descriptor> interTuple =
6460                   getFlowGraph(md).createIntermediateNode().getDescTuple();
6461
6462               for (Iterator<NTuple<Descriptor>> iter = nodeSetArrayAccessExp.iterator(); iter
6463                   .hasNext();) {
6464                 NTuple<Descriptor> higherTuple = iter.next();
6465                 addFlowGraphEdge(md, higherTuple, interTuple);
6466               }
6467
6468               FlowGraph fg = getFlowGraph(md);
6469               fg.addMapInterLocNodeToEnclosingDescriptor(interTuple.get(0),
6470                   getClassTypeDescriptor(base.get(base.size() - 1)));
6471
6472               nodeSet.clear();
6473               flowFieldTuple = interTuple;
6474             }
6475             nodeSet.addGlobalFlowTupleSet(idxNodeTupleSet.getGlobalLocTupleSet());
6476           }
6477
6478         }
6479
6480       }
6481       return flowFieldTuple;
6482     }
6483
6484   }
6485
6486   private void debug_printTreeNode(TreeNode tn) {
6487
6488     System.out.println("DEBUG: " + tn.printNode(0) + "                line#=" + tn.getNumLine());
6489
6490   }
6491
6492   private void analyzeFlowAssignmentNode(MethodDescriptor md, SymbolTable nametable,
6493       AssignmentNode an, NodeTupleSet nodeSet, NTuple<Descriptor> base,
6494       NodeTupleSet implicitFlowTupleSet) {
6495
6496     NodeTupleSet nodeSetRHS = new NodeTupleSet();
6497     NodeTupleSet nodeSetLHS = new NodeTupleSet();
6498
6499     boolean postinc = true;
6500     if (an.getOperation().getBaseOp() == null
6501         || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
6502             .getBaseOp().getOp() != Operation.POSTDEC)) {
6503       postinc = false;
6504     }
6505     // if LHS is array access node, need to capture value flows between an array
6506     // and its index value
6507     analyzeFlowExpressionNode(md, nametable, an.getDest(), nodeSetLHS, null, implicitFlowTupleSet,
6508         true);
6509
6510     if (!postinc) {
6511       // analyze value flows of rhs expression
6512       analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null, implicitFlowTupleSet,
6513           false);
6514
6515       // System.out.println("-analyzeFlowAssignmentNode=" + an.printNode(0));
6516       // System.out.println("-nodeSetLHS=" + nodeSetLHS);
6517       // System.out.println("-nodeSetRHS=" + nodeSetRHS);
6518       // System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet);
6519       // System.out.println("-");
6520
6521       if (an.getOperation().getOp() >= 2 && an.getOperation().getOp() <= 12) {
6522         // if assignment contains OP+EQ operator, creates edges from LHS to LHS
6523
6524         for (Iterator<NTuple<Descriptor>> iter = nodeSetLHS.iterator(); iter.hasNext();) {
6525           NTuple<Descriptor> fromTuple = iter.next();
6526           for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
6527             NTuple<Descriptor> toTuple = iter2.next();
6528             addFlowGraphEdge(md, fromTuple, toTuple);
6529           }
6530         }
6531       }
6532
6533       // creates edges from RHS to LHS
6534       NTuple<Descriptor> interTuple = null;
6535       if (needToGenerateInterLoc(nodeSetRHS)) {
6536         interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
6537       }
6538
6539       for (Iterator<NTuple<Descriptor>> iter = nodeSetRHS.iterator(); iter.hasNext();) {
6540         NTuple<Descriptor> fromTuple = iter.next();
6541         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
6542           NTuple<Descriptor> toTuple = iter2.next();
6543           addFlowGraphEdge(md, fromTuple, interTuple, toTuple);
6544         }
6545       }
6546
6547       // creates edges from implicitFlowTupleSet to LHS
6548       for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
6549         NTuple<Descriptor> fromTuple = iter.next();
6550         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
6551           NTuple<Descriptor> toTuple = iter2.next();
6552           addFlowGraphEdge(md, fromTuple, toTuple);
6553         }
6554       }
6555
6556       // create global flow edges if the callee gives return value flows to the caller
6557       GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
6558       for (Iterator<NTuple<Location>> iterator = nodeSetRHS.globalIterator(); iterator.hasNext();) {
6559         NTuple<Location> calleeReturnLocTuple = iterator.next();
6560         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
6561           NTuple<Descriptor> callerLHSTuple = iter2.next();
6562           // System.out.println("$$$ GLOBAL FLOW ADD=" + calleeReturnLocTuple + " -> "
6563           // + translateToLocTuple(md, callerLHSTuple));
6564
6565           globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple,
6566               translateToLocTuple(md, callerLHSTuple));
6567         }
6568       }
6569
6570       for (Iterator<NTuple<Location>> iterator = implicitFlowTupleSet.globalIterator(); iterator
6571           .hasNext();) {
6572         NTuple<Location> calleeReturnLocTuple = iterator.next();
6573         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
6574           NTuple<Descriptor> callerLHSTuple = iter2.next();
6575
6576           globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple,
6577               translateToLocTuple(md, callerLHSTuple));
6578           // System.out.println("$$$ GLOBAL FLOW PCLOC ADD=" + calleeReturnLocTuple + " -> "
6579           // + translateToLocTuple(md, callerLHSTuple));
6580         }
6581       }
6582
6583     } else {
6584       // postinc case
6585
6586       for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
6587         NTuple<Descriptor> tuple = iter2.next();
6588         addFlowGraphEdge(md, tuple, tuple);
6589       }
6590
6591       // creates edges from implicitFlowTupleSet to LHS
6592       for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
6593         NTuple<Descriptor> fromTuple = iter.next();
6594         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
6595           NTuple<Descriptor> toTuple = iter2.next();
6596           addFlowGraphEdge(md, fromTuple, toTuple);
6597         }
6598       }
6599
6600       GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
6601       for (Iterator<NTuple<Location>> iterator = implicitFlowTupleSet.globalIterator(); iterator
6602           .hasNext();) {
6603         NTuple<Location> calleeReturnLocTuple = iterator.next();
6604         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
6605           NTuple<Descriptor> callerLHSTuple = iter2.next();
6606           globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple,
6607               translateToLocTuple(md, callerLHSTuple));
6608           // System.out.println("$$$ GLOBAL FLOW PC ADD=" + calleeReturnLocTuple + " -> "
6609           // + translateToLocTuple(md, callerLHSTuple));
6610         }
6611       }
6612
6613     }
6614
6615     if (nodeSet != null) {
6616       nodeSet.addTupleSet(nodeSetLHS);
6617       nodeSet.addGlobalFlowTupleSet(nodeSetLHS.getGlobalLocTupleSet());
6618     }
6619   }
6620
6621   public FlowGraph getFlowGraph(MethodDescriptor md) {
6622     return mapMethodDescriptorToFlowGraph.get(md);
6623   }
6624
6625   private boolean addFlowGraphEdge(MethodDescriptor md, NTuple<Descriptor> from,
6626       NTuple<Descriptor> to) {
6627     FlowGraph graph = getFlowGraph(md);
6628     graph.addValueFlowEdge(from, to);
6629     return true;
6630   }
6631
6632   private void addFlowGraphEdge(MethodDescriptor md, NTuple<Descriptor> from,
6633       NTuple<Descriptor> inter, NTuple<Descriptor> to) {
6634
6635     FlowGraph graph = getFlowGraph(md);
6636
6637     if (inter != null) {
6638       graph.addValueFlowEdge(from, inter);
6639       graph.addValueFlowEdge(inter, to);
6640     } else {
6641       graph.addValueFlowEdge(from, to);
6642     }
6643
6644   }
6645
6646   public void writeInferredLatticeDotFile(ClassDescriptor cd, SSJavaLattice<String> locOrder,
6647       String nameSuffix) {
6648     // System.out.println("@cd=" + cd);
6649     // System.out.println("@sharedLoc=" + locOrder.getSharedLocSet());
6650     writeInferredLatticeDotFile(cd, null, locOrder, nameSuffix);
6651   }
6652
6653   public void writeNumLocsPathsCSVFile() {
6654
6655     try {
6656       BufferedWriter bw = new BufferedWriter(new FileWriter("sinfernumbers.csv"));
6657
6658       Set<Descriptor> keySet = mapNumLocsMapSInfer.keySet();
6659       for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
6660         Descriptor desc = (Descriptor) iterator.next();
6661         int numLocs = mapNumLocsMapSInfer.get(desc);
6662         int numPaths = mapNumPathsMapSInfer.get(desc);
6663         bw.write(desc.getSymbol().replaceAll("[,]", "") + "," + numLocs + "," + numPaths + "\n");
6664       }
6665       bw.close();
6666
6667       if (state.SSJAVA_INFER_NAIVE_WRITEDOTS) {
6668         BufferedWriter bw2 = new BufferedWriter(new FileWriter("naivenumbers.csv"));
6669         Set<Descriptor> keySet2 = mapNumLocsMapNaive.keySet();
6670         for (Iterator iterator = keySet2.iterator(); iterator.hasNext();) {
6671           Descriptor desc = (Descriptor) iterator.next();
6672           int numLocs = mapNumLocsMapNaive.get(desc);
6673           int numPaths = mapNumPathsMapNaive.get(desc);
6674           bw2.write(desc.getSymbol().replaceAll("[,]", "") + "," + numLocs + "," + numPaths + "\n");
6675         }
6676         bw2.close();
6677       }
6678
6679     } catch (IOException e) {
6680       // TODO Auto-generated catch block
6681       e.printStackTrace();
6682     }
6683
6684   }
6685
6686   public void writeInferredLatticeDotFile(ClassDescriptor cd, MethodDescriptor md,
6687       SSJavaLattice<String> locOrder, String nameSuffix) {
6688
6689     String fileName = "lattice_";
6690     if (md != null) {
6691       fileName +=
6692           cd.getSymbol().replaceAll("[\\W_]", "") + "_" + md.toString().replaceAll("[\\W_]", "");
6693     } else {
6694       fileName += cd.getSymbol().replaceAll("[\\W_]", "");
6695     }
6696
6697     fileName += nameSuffix;
6698
6699     System.out.println("***lattice=" + fileName + "    setsize=" + locOrder.getKeySet().size());
6700
6701     Set<Pair<String, String>> pairSet = locOrder.getOrderingPairSet();
6702
6703     Set<String> addedLocSet = new HashSet<String>();
6704
6705     if (pairSet.size() > 0) {
6706       try {
6707         BufferedWriter bw = new BufferedWriter(new FileWriter(fileName + ".dot"));
6708
6709         bw.write("digraph " + fileName + " {\n");
6710
6711         for (Iterator iterator = pairSet.iterator(); iterator.hasNext();) {
6712           // pair is in the form of <higher, lower>
6713           Pair<String, String> pair = (Pair<String, String>) iterator.next();
6714
6715           String highLocId = pair.getFirst();
6716           String lowLocId = pair.getSecond();
6717           if (!addedLocSet.contains(highLocId)) {
6718             addedLocSet.add(highLocId);
6719             drawNode(bw, locOrder, highLocId);
6720           }
6721
6722           if (!addedLocSet.contains(lowLocId)) {
6723             addedLocSet.add(lowLocId);
6724             drawNode(bw, locOrder, lowLocId);
6725           }
6726
6727           bw.write(highLocId + " -> " + lowLocId + ";\n");
6728         }
6729         bw.write("}\n");
6730         bw.close();
6731
6732       } catch (IOException e) {
6733         e.printStackTrace();
6734       }
6735
6736     }
6737
6738   }
6739
6740   private String convertMergeSetToString(HierarchyGraph graph, Set<HNode> mergeSet) {
6741     String str = "";
6742     for (Iterator iterator = mergeSet.iterator(); iterator.hasNext();) {
6743       HNode merged = (HNode) iterator.next();
6744       if (merged.isMergeNode()) {
6745         str += convertMergeSetToString(graph, graph.getMapHNodetoMergeSet().get(merged));
6746       } else {
6747         str += " " + merged.getName();
6748       }
6749     }
6750     return str;
6751   }
6752
6753   public void addNaiveLattice(Descriptor desc, SSJavaLattice<String> lattice) {
6754     desc2naiveLattice.put(desc, lattice);
6755   }
6756
6757   private void drawNode(BufferedWriter bw, SSJavaLattice<String> lattice, String locName)
6758       throws IOException {
6759
6760     String prettyStr;
6761     if (lattice.isSharedLoc(locName)) {
6762       prettyStr = locName + "*";
6763     } else {
6764       prettyStr = locName;
6765     }
6766     // HNode node = graph.getHNode(locName);
6767     // if (node != null && node.isMergeNode()) {
6768     // Set<HNode> mergeSet = graph.getMapHNodetoMergeSet().get(node);
6769     // prettyStr += ":" + convertMergeSetToString(graph, mergeSet);
6770     // }
6771     bw.write(locName + " [label=\"" + prettyStr + "\"]" + ";\n");
6772   }
6773
6774   public void _debug_writeFlowGraph() {
6775     Set<MethodDescriptor> keySet = mapMethodDescriptorToFlowGraph.keySet();
6776
6777     for (Iterator<MethodDescriptor> iterator = keySet.iterator(); iterator.hasNext();) {
6778       MethodDescriptor md = (MethodDescriptor) iterator.next();
6779       FlowGraph fg = mapMethodDescriptorToFlowGraph.get(md);
6780       GlobalFlowGraph subGlobalFlowGraph = getSubGlobalFlowGraph(md);
6781       try {
6782         fg.writeGraph();
6783         subGlobalFlowGraph.writeGraph("_SUBGLOBAL");
6784       } catch (IOException e) {
6785         e.printStackTrace();
6786       }
6787     }
6788
6789   }
6790
6791 }
6792
6793 class CyclicFlowException extends Exception {
6794
6795 }
6796
6797 class InterDescriptor extends Descriptor {
6798
6799   Pair<MethodInvokeNode, Integer> minArgIdxPair;
6800
6801   public InterDescriptor(String name) {
6802     super(name);
6803   }
6804
6805   public void setMethodArgIdxPair(MethodInvokeNode min, int idx) {
6806     minArgIdxPair = new Pair<MethodInvokeNode, Integer>(min, new Integer(idx));
6807   }
6808
6809   public Pair<MethodInvokeNode, Integer> getMethodArgIdxPair() {
6810     return minArgIdxPair;
6811   }
6812
6813 }