Robust/src/Analysis/SSJava/LocationInference.java

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