Robust/src/Analysis/SSJava/LocationInference.java

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