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