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: Inserting 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       skeletonGraphWithCombinationNode.insertCombinationNodesToGraph(simpleHierarchyGraph);
2160       // skeletonGraphWithCombinationNode.insertCombinationNodesToGraph(simpleHierarchyGraph,
2161       // skeletonGraph);
2162       // skeletonGraphWithCombinationNode.simplifySkeletonCombinationHierarchyGraph();
2163       skeletonGraphWithCombinationNode.removeRedundantEdges();
2164       mapDescriptorToCombineSkeletonHierarchyGraph.put(desc, skeletonGraphWithCombinationNode);
2165     }
2166   }
2167
2168   private void constructSkeletonHierarchyGraph() {
2169     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
2170     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2171       Descriptor desc = (Descriptor) iterator.next();
2172       System.out.println("SSJAVA: Constructing Skeleton Hierarchy Graph: " + desc);
2173       HierarchyGraph simpleGraph = getSimpleHierarchyGraph(desc);
2174       HierarchyGraph skeletonGraph = simpleGraph.generateSkeletonGraph();
2175       skeletonGraph.setMapDescToHNode(simpleGraph.getMapDescToHNode());
2176       skeletonGraph.setMapHNodeToDescSet(simpleGraph.getMapHNodeToDescSet());
2177       skeletonGraph.simplifyHierarchyGraph();
2178       // skeletonGraph.combineRedundantNodes(false);
2179       // skeletonGraph.removeRedundantEdges();
2180       mapDescriptorToSkeletonHierarchyGraph.put(desc, skeletonGraph);
2181     }
2182   }
2183
2184   private void debug_writeHierarchyDotFiles() {
2185
2186     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
2187     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2188       Descriptor desc = (Descriptor) iterator.next();
2189       getHierarchyGraph(desc).writeGraph();
2190     }
2191
2192   }
2193
2194   private void debug_writeSimpleHierarchyDotFiles() {
2195
2196     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
2197     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2198       Descriptor desc = (Descriptor) iterator.next();
2199       getHierarchyGraph(desc).writeGraph();
2200       getSimpleHierarchyGraph(desc).writeGraph();
2201       getSimpleHierarchyGraph(desc).writeGraph(true);
2202     }
2203
2204   }
2205
2206   private void debug_writeSkeletonHierarchyDotFiles() {
2207
2208     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
2209     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2210       Descriptor desc = (Descriptor) iterator.next();
2211       getSkeletonHierarchyGraph(desc).writeGraph();
2212     }
2213
2214   }
2215
2216   private void debug_writeSkeletonCombinationHierarchyDotFiles() {
2217
2218     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
2219     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2220       Descriptor desc = (Descriptor) iterator.next();
2221       getSkeletonCombinationHierarchyGraph(desc).writeGraph();
2222     }
2223
2224   }
2225
2226   public HierarchyGraph getSimpleHierarchyGraph(Descriptor d) {
2227     return mapDescriptorToSimpleHierarchyGraph.get(d);
2228   }
2229
2230   private HierarchyGraph getSkeletonHierarchyGraph(Descriptor d) {
2231     if (!mapDescriptorToSkeletonHierarchyGraph.containsKey(d)) {
2232       mapDescriptorToSkeletonHierarchyGraph.put(d, new HierarchyGraph(d));
2233     }
2234     return mapDescriptorToSkeletonHierarchyGraph.get(d);
2235   }
2236
2237   public HierarchyGraph getSkeletonCombinationHierarchyGraph(Descriptor d) {
2238     if (!mapDescriptorToCombineSkeletonHierarchyGraph.containsKey(d)) {
2239       mapDescriptorToCombineSkeletonHierarchyGraph.put(d, new HierarchyGraph(d));
2240     }
2241     return mapDescriptorToCombineSkeletonHierarchyGraph.get(d);
2242   }
2243
2244   private void constructHierarchyGraph() {
2245
2246     LinkedList<MethodDescriptor> methodDescList =
2247         (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
2248
2249     while (!methodDescList.isEmpty()) {
2250       MethodDescriptor md = methodDescList.removeLast();
2251       if (state.SSJAVADEBUG) {
2252         HierarchyGraph hierarchyGraph = new HierarchyGraph(md);
2253         System.out.println();
2254         System.out.println("SSJAVA: Construcing the hierarchy graph from " + md);
2255         constructHierarchyGraph(md, hierarchyGraph);
2256         mapDescriptorToHierarchyGraph.put(md, hierarchyGraph);
2257
2258       }
2259     }
2260
2261     setupToAnalyze();
2262     while (!toAnalyzeIsEmpty()) {
2263       ClassDescriptor cd = toAnalyzeNext();
2264       HierarchyGraph graph = getHierarchyGraph(cd);
2265       for (Iterator iter = cd.getFields(); iter.hasNext();) {
2266         FieldDescriptor fieldDesc = (FieldDescriptor) iter.next();
2267         if (!(fieldDesc.isStatic() && fieldDesc.isFinal())) {
2268           graph.getHNode(fieldDesc);
2269         }
2270       }
2271     }
2272
2273     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
2274     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2275       Descriptor key = (Descriptor) iterator.next();
2276       HierarchyGraph graph = getHierarchyGraph(key);
2277
2278       Set<HNode> nodeToBeConnected = new HashSet<HNode>();
2279       for (Iterator iterator2 = graph.getNodeSet().iterator(); iterator2.hasNext();) {
2280         HNode node = (HNode) iterator2.next();
2281         if (!node.isSkeleton() && !node.isCombinationNode()) {
2282           if (graph.getIncomingNodeSet(node).size() == 0) {
2283             nodeToBeConnected.add(node);
2284           }
2285         }
2286       }
2287
2288       for (Iterator iterator2 = nodeToBeConnected.iterator(); iterator2.hasNext();) {
2289         HNode node = (HNode) iterator2.next();
2290         System.out.println("NEED TO BE CONNECTED TO TOP=" + node);
2291         graph.addEdge(graph.getHNode(TOPDESC), node);
2292       }
2293
2294     }
2295
2296   }
2297
2298   private void constructHierarchyGraph2() {
2299
2300     // do fixed-point analysis
2301
2302     LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
2303
2304     // Collections.sort(descriptorListToAnalyze, new
2305     // Comparator<MethodDescriptor>() {
2306     // public int compare(MethodDescriptor o1, MethodDescriptor o2) {
2307     // return o1.getSymbol().compareToIgnoreCase(o2.getSymbol());
2308     // }
2309     // });
2310
2311     // current descriptors to visit in fixed-point interprocedural analysis,
2312     // prioritized by dependency in the call graph
2313     methodDescriptorsToVisitStack.clear();
2314
2315     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
2316     methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
2317
2318     while (!descriptorListToAnalyze.isEmpty()) {
2319       MethodDescriptor md = descriptorListToAnalyze.removeFirst();
2320       methodDescriptorsToVisitStack.add(md);
2321     }
2322
2323     // analyze scheduled methods until there are no more to visit
2324     while (!methodDescriptorsToVisitStack.isEmpty()) {
2325       // start to analyze leaf node
2326       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
2327
2328       HierarchyGraph hierarchyGraph = new HierarchyGraph(md);
2329       // MethodSummary methodSummary = new MethodSummary(md);
2330
2331       // MethodLocationInfo methodInfo = new MethodLocationInfo(md);
2332       // curMethodInfo = methodInfo;
2333
2334       System.out.println();
2335       System.out.println("SSJAVA: Construcing the hierarchy graph from " + md);
2336
2337       constructHierarchyGraph(md, hierarchyGraph);
2338
2339       HierarchyGraph prevHierarchyGraph = getHierarchyGraph(md);
2340       // MethodSummary prevMethodSummary = getMethodSummary(md);
2341
2342       if (!hierarchyGraph.equals(prevHierarchyGraph)) {
2343
2344         mapDescriptorToHierarchyGraph.put(md, hierarchyGraph);
2345         // mapDescToLocationSummary.put(md, methodSummary);
2346
2347         // results for callee changed, so enqueue dependents caller for
2348         // further analysis
2349         Iterator<MethodDescriptor> depsItr = ssjava.getDependents(md).iterator();
2350         while (depsItr.hasNext()) {
2351           MethodDescriptor methodNext = depsItr.next();
2352           if (!methodDescriptorsToVisitStack.contains(methodNext)
2353               && methodDescriptorToVistSet.contains(methodNext)) {
2354             methodDescriptorsToVisitStack.add(methodNext);
2355           }
2356         }
2357
2358       }
2359
2360     }
2361
2362     setupToAnalyze();
2363     while (!toAnalyzeIsEmpty()) {
2364       ClassDescriptor cd = toAnalyzeNext();
2365       HierarchyGraph graph = getHierarchyGraph(cd);
2366       for (Iterator iter = cd.getFields(); iter.hasNext();) {
2367         FieldDescriptor fieldDesc = (FieldDescriptor) iter.next();
2368         if (!(fieldDesc.isStatic() && fieldDesc.isFinal())) {
2369           graph.getHNode(fieldDesc);
2370         }
2371       }
2372     }
2373
2374     Set<Descriptor> keySet = mapDescriptorToHierarchyGraph.keySet();
2375     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2376       Descriptor key = (Descriptor) iterator.next();
2377       HierarchyGraph graph = getHierarchyGraph(key);
2378
2379       Set<HNode> nodeToBeConnected = new HashSet<HNode>();
2380       for (Iterator iterator2 = graph.getNodeSet().iterator(); iterator2.hasNext();) {
2381         HNode node = (HNode) iterator2.next();
2382         if (!node.isSkeleton() && !node.isCombinationNode()) {
2383           if (graph.getIncomingNodeSet(node).size() == 0) {
2384             nodeToBeConnected.add(node);
2385           }
2386         }
2387       }
2388
2389       for (Iterator iterator2 = nodeToBeConnected.iterator(); iterator2.hasNext();) {
2390         HNode node = (HNode) iterator2.next();
2391         System.out.println("NEED TO BE CONNECTED TO TOP=" + node);
2392         graph.addEdge(graph.getHNode(TOPDESC), node);
2393       }
2394
2395     }
2396
2397   }
2398
2399   private HierarchyGraph getHierarchyGraph(Descriptor d) {
2400     if (!mapDescriptorToHierarchyGraph.containsKey(d)) {
2401       mapDescriptorToHierarchyGraph.put(d, new HierarchyGraph(d));
2402     }
2403     return mapDescriptorToHierarchyGraph.get(d);
2404   }
2405
2406   private void constructHierarchyGraph(MethodDescriptor md, HierarchyGraph methodGraph) {
2407
2408     // visit each node of method flow graph
2409     FlowGraph fg = getFlowGraph(md);
2410     // Set<FlowNode> nodeSet = fg.getNodeSet();
2411
2412     Set<FlowEdge> edgeSet = fg.getEdgeSet();
2413
2414     Set<Descriptor> paramDescSet = fg.getMapParamDescToIdx().keySet();
2415     for (Iterator iterator = paramDescSet.iterator(); iterator.hasNext();) {
2416       Descriptor desc = (Descriptor) iterator.next();
2417       methodGraph.getHNode(desc).setSkeleton(true);
2418     }
2419
2420     // for the method lattice, we need to look at the first element of
2421     // NTuple<Descriptor>
2422     boolean hasGlobalAccess = false;
2423     // for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
2424     // FlowNode originalSrcNode = (FlowNode) iterator.next();
2425     for (Iterator iterator = edgeSet.iterator(); iterator.hasNext();) {
2426       FlowEdge edge = (FlowEdge) iterator.next();
2427
2428       FlowNode originalSrcNode = fg.getFlowNode(edge.getInitTuple());
2429       Set<FlowNode> sourceNodeSet = new HashSet<FlowNode>();
2430       if (originalSrcNode instanceof FlowReturnNode) {
2431         FlowReturnNode rnode = (FlowReturnNode) originalSrcNode;
2432         System.out.println("rnode=" + rnode);
2433         Set<NTuple<Descriptor>> tupleSet = rnode.getReturnTupleSet();
2434         for (Iterator iterator2 = tupleSet.iterator(); iterator2.hasNext();) {
2435           NTuple<Descriptor> nTuple = (NTuple<Descriptor>) iterator2.next();
2436           sourceNodeSet.add(fg.getFlowNode(nTuple));
2437           System.out.println("&&&SOURCE fg.getFlowNode(nTuple)=" + fg.getFlowNode(nTuple));
2438         }
2439       } else {
2440         sourceNodeSet.add(originalSrcNode);
2441       }
2442
2443       // System.out.println("---sourceNodeSet=" + sourceNodeSet + "  from originalSrcNode="
2444       // + originalSrcNode);
2445
2446       for (Iterator iterator3 = sourceNodeSet.iterator(); iterator3.hasNext();) {
2447         FlowNode srcNode = (FlowNode) iterator3.next();
2448
2449         NTuple<Descriptor> srcNodeTuple = srcNode.getDescTuple();
2450         Descriptor srcLocalDesc = srcNodeTuple.get(0);
2451
2452         if (srcLocalDesc instanceof InterDescriptor
2453             && ((InterDescriptor) srcLocalDesc).getMethodArgIdxPair() != null) {
2454
2455           if (srcNode.getCompositeLocation() == null) {
2456             continue;
2457           }
2458         }
2459
2460         // if the srcNode is started with the global descriptor
2461         // need to set as a skeleton node
2462         if (!hasGlobalAccess && srcNode.getDescTuple().startsWith(GLOBALDESC)) {
2463           hasGlobalAccess = true;
2464         }
2465
2466         // Set<FlowEdge> outEdgeSet = fg.getOutEdgeSet(originalSrcNode);
2467         // for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) {
2468         // FlowEdge outEdge = (FlowEdge) iterator2.next();
2469         // FlowNode originalDstNode = outEdge.getDst();
2470         FlowNode originalDstNode = fg.getFlowNode(edge.getEndTuple());
2471
2472         Set<FlowNode> dstNodeSet = new HashSet<FlowNode>();
2473         if (originalDstNode instanceof FlowReturnNode) {
2474           FlowReturnNode rnode = (FlowReturnNode) originalDstNode;
2475           // System.out.println("\n-returnNode=" + rnode);
2476           Set<NTuple<Descriptor>> tupleSet = rnode.getReturnTupleSet();
2477           for (Iterator iterator4 = tupleSet.iterator(); iterator4.hasNext();) {
2478             NTuple<Descriptor> nTuple = (NTuple<Descriptor>) iterator4.next();
2479             dstNodeSet.add(fg.getFlowNode(nTuple));
2480             System.out.println("&&&DST fg.getFlowNode(nTuple)=" + fg.getFlowNode(nTuple));
2481           }
2482         } else {
2483           dstNodeSet.add(originalDstNode);
2484         }
2485         // System.out.println("---dstNodeSet=" + dstNodeSet);
2486         for (Iterator iterator4 = dstNodeSet.iterator(); iterator4.hasNext();) {
2487           FlowNode dstNode = (FlowNode) iterator4.next();
2488
2489           NTuple<Descriptor> dstNodeTuple = dstNode.getDescTuple();
2490           Descriptor dstLocalDesc = dstNodeTuple.get(0);
2491
2492           if (dstLocalDesc instanceof InterDescriptor
2493               && ((InterDescriptor) dstLocalDesc).getMethodArgIdxPair() != null) {
2494             if (dstNode.getCompositeLocation() == null) {
2495               System.out.println("%%%%%%%%%%%%%SKIP=" + dstNode);
2496               continue;
2497             }
2498           }
2499
2500           // if (outEdge.getInitTuple().equals(srcNodeTuple)
2501           // && outEdge.getEndTuple().equals(dstNodeTuple)) {
2502
2503           NTuple<Descriptor> srcCurTuple = srcNode.getCurrentDescTuple();
2504           NTuple<Descriptor> dstCurTuple = dstNode.getCurrentDescTuple();
2505
2506           System.out.println("-srcCurTuple=" + srcCurTuple + "  dstCurTuple=" + dstCurTuple
2507               + "  srcNode=" + srcNode + "   dstNode=" + dstNode);
2508
2509           // srcCurTuple = translateBaseTuple(srcNode, srcCurTuple);
2510           // dstCurTuple = translateBaseTuple(dstNode, dstCurTuple);
2511
2512           if ((srcCurTuple.size() > 1 && dstCurTuple.size() > 1)
2513               && srcCurTuple.get(0).equals(dstCurTuple.get(0))) {
2514
2515             // value flows between fields
2516             Descriptor desc = srcCurTuple.get(0);
2517             ClassDescriptor classDesc;
2518
2519             if (desc.equals(GLOBALDESC)) {
2520               classDesc = md.getClassDesc();
2521             } else {
2522               VarDescriptor varDesc = (VarDescriptor) srcCurTuple.get(0);
2523               classDesc = varDesc.getType().getClassDesc();
2524             }
2525             extractFlowsBetweenFields(classDesc, srcNode, dstNode, 1);
2526
2527           } else if ((srcCurTuple.size() == 1 && dstCurTuple.size() == 1)
2528               || ((srcCurTuple.size() > 1 || dstCurTuple.size() > 1) && !srcCurTuple.get(0).equals(
2529                   dstCurTuple.get(0)))) {
2530
2531             // value flow between a primitive local var - a primitive local var or local var -
2532             // field
2533
2534             Descriptor srcDesc = srcCurTuple.get(0);
2535             Descriptor dstDesc = dstCurTuple.get(0);
2536
2537             methodGraph.addEdge(srcDesc, dstDesc);
2538
2539             if (fg.isParamDesc(srcDesc)) {
2540               methodGraph.setParamHNode(srcDesc);
2541             }
2542             if (fg.isParamDesc(dstDesc)) {
2543               methodGraph.setParamHNode(dstDesc);
2544             }
2545
2546           }
2547
2548           // }
2549           // }
2550
2551         }
2552
2553       }
2554
2555     }
2556
2557     // If the method accesses static fields
2558     // set hasGloabalAccess true in the method summary.
2559     if (hasGlobalAccess) {
2560       getMethodSummary(md).setHasGlobalAccess();
2561     }
2562     methodGraph.getHNode(GLOBALDESC).setSkeleton(true);
2563
2564     if (ssjava.getMethodContainingSSJavaLoop().equals(md)) {
2565       // if the current method contains the event loop
2566       // we need to set all nodes of the hierarchy graph as a skeleton node
2567       Set<HNode> hnodeSet = methodGraph.getNodeSet();
2568       for (Iterator iterator = hnodeSet.iterator(); iterator.hasNext();) {
2569         HNode hnode = (HNode) iterator.next();
2570         hnode.setSkeleton(true);
2571       }
2572     }
2573
2574   }
2575
2576   private NTuple<Descriptor> translateBaseTuple(FlowNode flowNode, NTuple<Descriptor> inTuple) {
2577
2578     if (flowNode.getBaseTuple() != null) {
2579
2580       NTuple<Descriptor> translatedTuple = new NTuple<Descriptor>();
2581
2582       NTuple<Descriptor> baseTuple = flowNode.getBaseTuple();
2583
2584       for (int i = 0; i < baseTuple.size(); i++) {
2585         translatedTuple.add(baseTuple.get(i));
2586       }
2587
2588       for (int i = 1; i < inTuple.size(); i++) {
2589         translatedTuple.add(inTuple.get(i));
2590       }
2591
2592       System.out.println("------TRANSLATED " + inTuple + " -> " + translatedTuple);
2593       return translatedTuple;
2594
2595     } else {
2596       return inTuple;
2597     }
2598
2599   }
2600
2601   private MethodSummary getMethodSummary(MethodDescriptor md) {
2602     if (!mapDescToLocationSummary.containsKey(md)) {
2603       mapDescToLocationSummary.put(md, new MethodSummary(md));
2604     }
2605     return (MethodSummary) mapDescToLocationSummary.get(md);
2606   }
2607
2608   private void addMapClassDefinitionToLineNum(ClassDescriptor cd, String strLine, int lineNum) {
2609
2610     String classSymbol = cd.getSymbol();
2611     int idx = classSymbol.lastIndexOf("$");
2612     if (idx != -1) {
2613       classSymbol = classSymbol.substring(idx + 1);
2614     }
2615
2616     String pattern = "class " + classSymbol + " ";
2617     if (strLine.indexOf(pattern) != -1) {
2618       mapDescToDefinitionLine.put(cd, lineNum);
2619     }
2620   }
2621
2622   private void addMapMethodDefinitionToLineNum(Set<MethodDescriptor> methodSet, String strLine,
2623       int lineNum) {
2624     for (Iterator iterator = methodSet.iterator(); iterator.hasNext();) {
2625       MethodDescriptor md = (MethodDescriptor) iterator.next();
2626       String pattern = md.getMethodDeclaration();
2627       if (strLine.indexOf(pattern) != -1) {
2628         mapDescToDefinitionLine.put(md, lineNum);
2629         methodSet.remove(md);
2630         return;
2631       }
2632     }
2633
2634   }
2635
2636   private void readOriginalSourceFiles() {
2637
2638     SymbolTable classtable = state.getClassSymbolTable();
2639
2640     Set<ClassDescriptor> classDescSet = new HashSet<ClassDescriptor>();
2641     classDescSet.addAll(classtable.getValueSet());
2642
2643     try {
2644       // inefficient implement. it may re-visit the same file if the file
2645       // contains more than one class definitions.
2646       for (Iterator iterator = classDescSet.iterator(); iterator.hasNext();) {
2647         ClassDescriptor cd = (ClassDescriptor) iterator.next();
2648
2649         Set<MethodDescriptor> methodSet = new HashSet<MethodDescriptor>();
2650         methodSet.addAll(cd.getMethodTable().getValueSet());
2651
2652         String sourceFileName = cd.getSourceFileName();
2653         Vector<String> lineVec = new Vector<String>();
2654
2655         mapFileNameToLineVector.put(sourceFileName, lineVec);
2656
2657         BufferedReader in = new BufferedReader(new FileReader(sourceFileName));
2658         String strLine;
2659         int lineNum = 1;
2660         lineVec.add(""); // the index is started from 1.
2661         while ((strLine = in.readLine()) != null) {
2662           lineVec.add(lineNum, strLine);
2663           addMapClassDefinitionToLineNum(cd, strLine, lineNum);
2664           addMapMethodDefinitionToLineNum(methodSet, strLine, lineNum);
2665           lineNum++;
2666         }
2667
2668       }
2669
2670     } catch (IOException e) {
2671       e.printStackTrace();
2672     }
2673
2674   }
2675
2676   private String generateLatticeDefinition(Descriptor desc) {
2677
2678     Set<String> sharedLocSet = new HashSet<String>();
2679
2680     SSJavaLattice<String> lattice = getLattice(desc);
2681     String rtr = "@LATTICE(\"";
2682
2683     Map<String, Set<String>> map = lattice.getTable();
2684     Set<String> keySet = map.keySet();
2685     boolean first = true;
2686     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2687       String key = (String) iterator.next();
2688       if (!key.equals(lattice.getTopItem())) {
2689         Set<String> connectedSet = map.get(key);
2690
2691         if (connectedSet.size() == 1) {
2692           if (connectedSet.iterator().next().equals(lattice.getBottomItem())) {
2693             if (!first) {
2694               rtr += ",";
2695             } else {
2696               rtr += "LOC,";
2697               first = false;
2698             }
2699             rtr += key;
2700             if (lattice.isSharedLoc(key)) {
2701               rtr += "," + key + "*";
2702             }
2703           }
2704         }
2705
2706         for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) {
2707           String loc = (String) iterator2.next();
2708           if (!loc.equals(lattice.getBottomItem())) {
2709             if (!first) {
2710               rtr += ",";
2711             } else {
2712               rtr += "LOC,";
2713               first = false;
2714             }
2715             rtr += loc + "<" + key;
2716             if (lattice.isSharedLoc(key) && (!sharedLocSet.contains(key))) {
2717               rtr += "," + key + "*";
2718               sharedLocSet.add(key);
2719             }
2720             if (lattice.isSharedLoc(loc) && (!sharedLocSet.contains(loc))) {
2721               rtr += "," + loc + "*";
2722               sharedLocSet.add(loc);
2723             }
2724
2725           }
2726         }
2727       }
2728     }
2729
2730     if (desc instanceof MethodDescriptor) {
2731       System.out.println("#EXTRA LOC DECLARATION GEN=" + desc);
2732
2733       MethodDescriptor md = (MethodDescriptor) desc;
2734       MethodSummary methodSummary = getMethodSummary(md);
2735
2736       TypeDescriptor returnType = ((MethodDescriptor) desc).getReturnType();
2737       if (!ssjava.getMethodContainingSSJavaLoop().equals(desc) && returnType != null
2738           && (!returnType.isVoid())) {
2739         CompositeLocation returnLoc = methodSummary.getRETURNLoc();
2740         if (returnLoc.getSize() == 1) {
2741           String returnLocStr = generateLocationAnnoatation(methodSummary.getRETURNLoc());
2742           if (rtr.indexOf(returnLocStr) == -1) {
2743             rtr += "," + returnLocStr;
2744           }
2745         }
2746       }
2747       rtr += "\")";
2748
2749       if (!ssjava.getMethodContainingSSJavaLoop().equals(desc)) {
2750         if (returnType != null && (!returnType.isVoid())) {
2751           rtr +=
2752               "\n@RETURNLOC(\"" + generateLocationAnnoatation(methodSummary.getRETURNLoc()) + "\")";
2753         }
2754
2755         CompositeLocation pcLoc = methodSummary.getPCLoc();
2756         if ((pcLoc != null) && (!pcLoc.get(0).isTop())) {
2757           rtr += "\n@PCLOC(\"" + generateLocationAnnoatation(pcLoc) + "\")";
2758         }
2759       }
2760
2761       if (!md.isStatic()) {
2762         rtr += "\n@THISLOC(\"" + methodSummary.getThisLocName() + "\")";
2763       }
2764       rtr += "\n@GLOBALLOC(\"" + methodSummary.getGlobalLocName() + "\")";
2765
2766     } else {
2767       rtr += "\")";
2768     }
2769
2770     return rtr;
2771   }
2772
2773   private void generateAnnoatedCode() {
2774
2775     readOriginalSourceFiles();
2776
2777     setupToAnalyze();
2778     while (!toAnalyzeIsEmpty()) {
2779       ClassDescriptor cd = toAnalyzeNext();
2780
2781       setupToAnalazeMethod(cd);
2782
2783       String sourceFileName = cd.getSourceFileName();
2784
2785       if (cd.isInterface()) {
2786         continue;
2787       }
2788
2789       int classDefLine = mapDescToDefinitionLine.get(cd);
2790       Vector<String> sourceVec = mapFileNameToLineVector.get(sourceFileName);
2791
2792       LocationSummary fieldLocSummary = getLocationSummary(cd);
2793
2794       String fieldLatticeDefStr = generateLatticeDefinition(cd);
2795       String annoatedSrc = fieldLatticeDefStr + newline + sourceVec.get(classDefLine);
2796       sourceVec.set(classDefLine, annoatedSrc);
2797
2798       // generate annotations for field declarations
2799       // Map<Descriptor, CompositeLocation> inferLocMap = fieldLocInfo.getMapDescToInferLocation();
2800       Map<String, String> mapFieldNameToLocName = fieldLocSummary.getMapHNodeNameToLocationName();
2801
2802       for (Iterator iter = cd.getFields(); iter.hasNext();) {
2803         FieldDescriptor fd = (FieldDescriptor) iter.next();
2804
2805         String locAnnotationStr;
2806         // CompositeLocation inferLoc = inferLocMap.get(fd);
2807         String locName = mapFieldNameToLocName.get(fd.getSymbol());
2808
2809         if (locName != null) {
2810           // infer loc is null if the corresponding field is static and final
2811           // locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")";
2812           locAnnotationStr = "@LOC(\"" + locName + "\")";
2813           int fdLineNum = fd.getLineNum();
2814           String orgFieldDeclarationStr = sourceVec.get(fdLineNum);
2815           String fieldDeclaration = fd.toString();
2816           fieldDeclaration = fieldDeclaration.substring(0, fieldDeclaration.length() - 1);
2817           String annoatedStr = locAnnotationStr + " " + orgFieldDeclarationStr;
2818           sourceVec.set(fdLineNum, annoatedStr);
2819         }
2820
2821       }
2822
2823       while (!toAnalyzeMethodIsEmpty()) {
2824         MethodDescriptor md = toAnalyzeMethodNext();
2825
2826         if (!ssjava.needTobeAnnotated(md)) {
2827           continue;
2828         }
2829
2830         SSJavaLattice<String> methodLattice = md2lattice.get(md);
2831         if (methodLattice != null) {
2832
2833           int methodDefLine = md.getLineNum();
2834
2835           // MethodLocationInfo methodLocInfo = getMethodLocationInfo(md);
2836           // Map<Descriptor, CompositeLocation> methodInferLocMap =
2837           // methodLocInfo.getMapDescToInferLocation();
2838
2839           MethodSummary methodSummary = getMethodSummary(md);
2840
2841           Map<Descriptor, CompositeLocation> mapVarDescToInferLoc =
2842               methodSummary.getMapVarDescToInferCompositeLocation();
2843           System.out.println("-----md=" + md);
2844           System.out.println("-----mapVarDescToInferLoc=" + mapVarDescToInferLoc);
2845
2846           Set<Descriptor> localVarDescSet = mapVarDescToInferLoc.keySet();
2847
2848           Set<String> localLocElementSet = methodLattice.getElementSet();
2849
2850           for (Iterator iterator = localVarDescSet.iterator(); iterator.hasNext();) {
2851             Descriptor localVarDesc = (Descriptor) iterator.next();
2852             System.out.println("-------localVarDesc=" + localVarDesc);
2853             CompositeLocation inferLoc = mapVarDescToInferLoc.get(localVarDesc);
2854
2855             String localLocIdentifier = inferLoc.get(0).getLocIdentifier();
2856             if (!localLocElementSet.contains(localLocIdentifier)) {
2857               methodLattice.put(localLocIdentifier);
2858             }
2859
2860             String locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")";
2861
2862             if (!isParameter(md, localVarDesc)) {
2863               if (mapDescToDefinitionLine.containsKey(localVarDesc)) {
2864                 int varLineNum = mapDescToDefinitionLine.get(localVarDesc);
2865                 String orgSourceLine = sourceVec.get(varLineNum);
2866                 System.out.println("varLineNum=" + varLineNum + "  org src=" + orgSourceLine);
2867                 int idx =
2868                     orgSourceLine.indexOf(generateVarDeclaration((VarDescriptor) localVarDesc));
2869                 System.out.println("idx=" + idx
2870                     + "  generateVarDeclaration((VarDescriptor) localVarDesc)="
2871                     + generateVarDeclaration((VarDescriptor) localVarDesc));
2872                 assert (idx != -1);
2873                 String annoatedStr =
2874                     orgSourceLine.substring(0, idx) + locAnnotationStr + " "
2875                         + orgSourceLine.substring(idx);
2876                 sourceVec.set(varLineNum, annoatedStr);
2877               }
2878             } else {
2879               String methodDefStr = sourceVec.get(methodDefLine);
2880
2881               int idx =
2882                   getParamLocation(methodDefStr,
2883                       generateVarDeclaration((VarDescriptor) localVarDesc));
2884               System.out.println("methodDefStr=" + methodDefStr + " localVarDesc=" + localVarDesc
2885                   + " idx=" + idx);
2886               assert (idx != -1);
2887
2888               String annoatedStr =
2889                   methodDefStr.substring(0, idx) + locAnnotationStr + " "
2890                       + methodDefStr.substring(idx);
2891               sourceVec.set(methodDefLine, annoatedStr);
2892             }
2893
2894           }
2895
2896           // check if the lattice has to have the location type for the this
2897           // reference...
2898
2899           // boolean needToAddthisRef = hasThisReference(md);
2900           // if (localLocElementSet.contains("this")) {
2901           // methodLattice.put("this");
2902           // }
2903
2904           String methodLatticeDefStr = generateLatticeDefinition(md);
2905           String annoatedStr = methodLatticeDefStr + newline + sourceVec.get(methodDefLine);
2906           sourceVec.set(methodDefLine, annoatedStr);
2907
2908         }
2909       }
2910
2911     }
2912
2913     codeGen();
2914   }
2915
2916   private boolean hasThisReference(MethodDescriptor md) {
2917
2918     FlowGraph fg = getFlowGraph(md);
2919     Set<FlowNode> nodeSet = fg.getNodeSet();
2920     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
2921       FlowNode flowNode = (FlowNode) iterator.next();
2922       if (flowNode.getDescTuple().get(0).equals(md.getThis())) {
2923         return true;
2924       }
2925     }
2926
2927     return false;
2928   }
2929
2930   private int getParamLocation(String methodStr, String paramStr) {
2931
2932     String pattern = paramStr + ",";
2933
2934     int idx = methodStr.indexOf(pattern);
2935     if (idx != -1) {
2936       return idx;
2937     } else {
2938       pattern = paramStr + ")";
2939       return methodStr.indexOf(pattern);
2940     }
2941
2942   }
2943
2944   private String generateVarDeclaration(VarDescriptor varDesc) {
2945
2946     TypeDescriptor td = varDesc.getType();
2947     String rtr = td.toString();
2948     if (td.isArray()) {
2949       for (int i = 0; i < td.getArrayCount(); i++) {
2950         rtr += "[]";
2951       }
2952     }
2953     rtr += " " + varDesc.getName();
2954     return rtr;
2955
2956   }
2957
2958   private String generateLocationAnnoatation(CompositeLocation loc) {
2959     String rtr = "";
2960     // method location
2961     Location methodLoc = loc.get(0);
2962     rtr += methodLoc.getLocIdentifier();
2963
2964     for (int i = 1; i < loc.getSize(); i++) {
2965       Location element = loc.get(i);
2966       rtr += "," + element.getDescriptor().getSymbol() + "." + element.getLocIdentifier();
2967     }
2968
2969     return rtr;
2970   }
2971
2972   private boolean isParameter(MethodDescriptor md, Descriptor localVarDesc) {
2973     return getFlowGraph(md).isParamDesc(localVarDesc);
2974   }
2975
2976   private String extractFileName(String fileName) {
2977     int idx = fileName.lastIndexOf("/");
2978     if (idx == -1) {
2979       return fileName;
2980     } else {
2981       return fileName.substring(idx + 1);
2982     }
2983
2984   }
2985
2986   private void codeGen() {
2987
2988     Set<String> originalFileNameSet = mapFileNameToLineVector.keySet();
2989     for (Iterator iterator = originalFileNameSet.iterator(); iterator.hasNext();) {
2990       String orgFileName = (String) iterator.next();
2991       String outputFileName = extractFileName(orgFileName);
2992
2993       Vector<String> sourceVec = mapFileNameToLineVector.get(orgFileName);
2994
2995       try {
2996
2997         FileWriter fileWriter = new FileWriter("./infer/" + outputFileName);
2998         BufferedWriter out = new BufferedWriter(fileWriter);
2999
3000         for (int i = 0; i < sourceVec.size(); i++) {
3001           out.write(sourceVec.get(i));
3002           out.newLine();
3003         }
3004         out.close();
3005       } catch (IOException e) {
3006         e.printStackTrace();
3007       }
3008
3009     }
3010
3011   }
3012
3013   private void checkLattices() {
3014
3015     LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
3016
3017     // current descriptors to visit in fixed-point interprocedural analysis,
3018     // prioritized by
3019     // dependency in the call graph
3020     methodDescriptorsToVisitStack.clear();
3021
3022     // descriptorListToAnalyze.removeFirst();
3023
3024     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
3025     methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
3026
3027     while (!descriptorListToAnalyze.isEmpty()) {
3028       MethodDescriptor md = descriptorListToAnalyze.removeFirst();
3029       checkLatticesOfVirtualMethods(md);
3030     }
3031
3032   }
3033
3034   private void debug_writeLatticeDotFile() {
3035     // generate lattice dot file
3036
3037     setupToAnalyze();
3038
3039     while (!toAnalyzeIsEmpty()) {
3040       ClassDescriptor cd = toAnalyzeNext();
3041
3042       setupToAnalazeMethod(cd);
3043
3044       SSJavaLattice<String> classLattice = cd2lattice.get(cd);
3045       if (classLattice != null) {
3046         ssjava.writeLatticeDotFile(cd, null, classLattice);
3047         debug_printDescriptorToLocNameMapping(cd);
3048       }
3049
3050       while (!toAnalyzeMethodIsEmpty()) {
3051         MethodDescriptor md = toAnalyzeMethodNext();
3052         SSJavaLattice<String> methodLattice = md2lattice.get(md);
3053         if (methodLattice != null) {
3054           ssjava.writeLatticeDotFile(cd, md, methodLattice);
3055           debug_printDescriptorToLocNameMapping(md);
3056         }
3057       }
3058     }
3059
3060   }
3061
3062   private void debug_printDescriptorToLocNameMapping(Descriptor desc) {
3063
3064     LocationInfo info = getLocationInfo(desc);
3065     System.out.println("## " + desc + " ##");
3066     System.out.println(info.getMapDescToInferLocation());
3067     LocationInfo locInfo = getLocationInfo(desc);
3068     System.out.println("mapping=" + locInfo.getMapLocSymbolToDescSet());
3069     System.out.println("###################");
3070
3071   }
3072
3073   private void calculateExtraLocations() {
3074
3075     LinkedList<MethodDescriptor> methodDescList = ssjava.getSortedDescriptors();
3076     for (Iterator iterator = methodDescList.iterator(); iterator.hasNext();) {
3077       MethodDescriptor md = (MethodDescriptor) iterator.next();
3078       if (!ssjava.getMethodContainingSSJavaLoop().equals(md)) {
3079         calculateExtraLocations(md);
3080       }
3081     }
3082
3083   }
3084
3085   private void checkLatticesOfVirtualMethods(MethodDescriptor md) {
3086
3087     if (!md.isStatic()) {
3088       Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
3089       setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md));
3090
3091       for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
3092         MethodDescriptor mdCallee = (MethodDescriptor) iterator.next();
3093         if (!md.equals(mdCallee)) {
3094           checkConsistency(md, mdCallee);
3095         }
3096       }
3097
3098     }
3099
3100   }
3101
3102   private void checkConsistency(MethodDescriptor md1, MethodDescriptor md2) {
3103
3104     // check that two lattice have the same relations between parameters(+PC
3105     // LOC, GLOBAL_LOC RETURN LOC)
3106
3107     List<CompositeLocation> list1 = new ArrayList<CompositeLocation>();
3108     List<CompositeLocation> list2 = new ArrayList<CompositeLocation>();
3109
3110     MethodLocationInfo locInfo1 = getMethodLocationInfo(md1);
3111     MethodLocationInfo locInfo2 = getMethodLocationInfo(md2);
3112
3113     Map<Integer, CompositeLocation> paramMap1 = locInfo1.getMapParamIdxToInferLoc();
3114     Map<Integer, CompositeLocation> paramMap2 = locInfo2.getMapParamIdxToInferLoc();
3115
3116     int numParam = locInfo1.getMapParamIdxToInferLoc().keySet().size();
3117
3118     // add location types of paramters
3119     for (int idx = 0; idx < numParam; idx++) {
3120       list1.add(paramMap1.get(Integer.valueOf(idx)));
3121       list2.add(paramMap2.get(Integer.valueOf(idx)));
3122     }
3123
3124     // add program counter location
3125     list1.add(locInfo1.getPCLoc());
3126     list2.add(locInfo2.getPCLoc());
3127
3128     if (!md1.getReturnType().isVoid()) {
3129       // add return value location
3130       CompositeLocation rtrLoc1 = getMethodLocationInfo(md1).getReturnLoc();
3131       CompositeLocation rtrLoc2 = getMethodLocationInfo(md2).getReturnLoc();
3132       list1.add(rtrLoc1);
3133       list2.add(rtrLoc2);
3134     }
3135
3136     // add global location type
3137     if (md1.isStatic()) {
3138       CompositeLocation globalLoc1 =
3139           new CompositeLocation(new Location(md1, locInfo1.getGlobalLocName()));
3140       CompositeLocation globalLoc2 =
3141           new CompositeLocation(new Location(md2, locInfo2.getGlobalLocName()));
3142       list1.add(globalLoc1);
3143       list2.add(globalLoc2);
3144     }
3145
3146     for (int i = 0; i < list1.size(); i++) {
3147       CompositeLocation locA1 = list1.get(i);
3148       CompositeLocation locA2 = list2.get(i);
3149       for (int k = 0; k < list1.size(); k++) {
3150         if (i != k) {
3151           CompositeLocation locB1 = list1.get(k);
3152           CompositeLocation locB2 = list2.get(k);
3153           boolean r1 = isGreaterThan(getLattice(md1), locA1, locB1);
3154
3155           boolean r2 = isGreaterThan(getLattice(md1), locA2, locB2);
3156
3157           if (r1 != r2) {
3158             throw new Error("The method " + md1 + " is not consistent with the method " + md2
3159                 + ".:: They have a different ordering relation between locations (" + locA1 + ","
3160                 + locB1 + ") and (" + locA2 + "," + locB2 + ").");
3161           }
3162         }
3163       }
3164     }
3165
3166   }
3167
3168   private String getSymbol(int idx, FlowNode node) {
3169     Descriptor desc = node.getDescTuple().get(idx);
3170     return desc.getSymbol();
3171   }
3172
3173   private Descriptor getDescriptor(int idx, FlowNode node) {
3174     Descriptor desc = node.getDescTuple().get(idx);
3175     return desc;
3176   }
3177
3178   private void calculatePCLOC(MethodDescriptor md) {
3179
3180     System.out.println("#CalculatePCLOC");
3181     MethodSummary methodSummary = getMethodSummary(md);
3182     FlowGraph fg = getFlowGraph(md);
3183     Map<Integer, CompositeLocation> mapParamToLoc = methodSummary.getMapParamIdxToInferLoc();
3184
3185     // calculate the initial program counter location
3186     // PC location is higher than location types of parameters which has incoming flows.
3187
3188     Set<NTuple<Location>> paramLocTupleHavingInFlowSet = new HashSet<NTuple<Location>>();
3189     Set<Descriptor> paramDescNOTHavingInFlowSet = new HashSet<Descriptor>();
3190     // Set<FlowNode> paramNodeNOThavingInFlowSet = new HashSet<FlowNode>();
3191
3192     int numParams = fg.getNumParameters();
3193     for (int i = 0; i < numParams; i++) {
3194       FlowNode paramFlowNode = fg.getParamFlowNode(i);
3195       Descriptor prefix = paramFlowNode.getDescTuple().get(0);
3196       NTuple<Descriptor> paramDescTuple = paramFlowNode.getCurrentDescTuple();
3197       NTuple<Location> paramLocTuple = translateToLocTuple(md, paramDescTuple);
3198
3199       Set<FlowNode> inNodeToParamSet = fg.getIncomingNodeSetByPrefix(prefix);
3200       if (inNodeToParamSet.size() > 0) {
3201         // parameter has in-value flows
3202
3203         for (Iterator iterator = inNodeToParamSet.iterator(); iterator.hasNext();) {
3204           FlowNode inNode = (FlowNode) iterator.next();
3205           Set<FlowEdge> outEdgeSet = fg.getOutEdgeSet(inNode);
3206           for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) {
3207             FlowEdge flowEdge = (FlowEdge) iterator2.next();
3208             if (flowEdge.getEndTuple().startsWith(prefix)) {
3209               NTuple<Location> paramLocTupleWithIncomingFlow =
3210                   translateToLocTuple(md, flowEdge.getEndTuple());
3211               paramLocTupleHavingInFlowSet.add(paramLocTupleWithIncomingFlow);
3212             }
3213           }
3214         }
3215
3216         // paramLocTupleHavingInFlowSet.add(paramLocTuple);
3217       } else {
3218         // paramNodeNOThavingInFlowSet.add(fg.getFlowNode(paramDescTuple));
3219         paramDescNOTHavingInFlowSet.add(prefix);
3220       }
3221     }
3222
3223     System.out.println("paramLocTupleHavingInFlowSet=" + paramLocTupleHavingInFlowSet);
3224
3225     if (paramLocTupleHavingInFlowSet.size() > 0
3226         && !coversAllParamters(md, fg, paramLocTupleHavingInFlowSet)) {
3227
3228       // Here, generates a location in the method lattice that is higher than the
3229       // paramLocTupleHavingInFlowSet
3230       NTuple<Location> pcLocTuple =
3231           generateLocTupleRelativeTo(md, paramLocTupleHavingInFlowSet, PCLOC);
3232
3233       NTuple<Descriptor> pcDescTuple = translateToDescTuple(pcLocTuple);
3234
3235       // System.out.println("pcLoc=" + pcLocTuple);
3236
3237       CompositeLocation curPCLoc = methodSummary.getPCLoc();
3238       if (curPCLoc.get(0).isTop() || pcLocTuple.size() > curPCLoc.getSize()) {
3239         methodSummary.setPCLoc(new CompositeLocation(pcLocTuple));
3240
3241         Set<FlowNode> flowNodeLowerthanPCLocSet = new HashSet<FlowNode>();
3242         GlobalFlowGraph subGlobalFlowGraph = getSubGlobalFlowGraph(md);
3243         // add ordering relations s.t. PCLOC is higher than all flow nodes except the set of
3244         // parameters that do not have incoming flows
3245         for (Iterator iterator = fg.getNodeSet().iterator(); iterator.hasNext();) {
3246           FlowNode node = (FlowNode) iterator.next();
3247
3248           if (!(node instanceof FlowReturnNode)) {
3249             if (!paramDescNOTHavingInFlowSet.contains(node.getCurrentDescTuple().get(0))) {
3250               flowNodeLowerthanPCLocSet.add(node);
3251               fg.addValueFlowEdge(pcDescTuple, node.getDescTuple());
3252
3253               subGlobalFlowGraph.addValueFlowEdge(pcLocTuple,
3254                   translateToLocTuple(md, node.getDescTuple()));
3255             }
3256           } else {
3257             System.out.println("***SKIP PCLOC -> RETURNLOC=" + node);
3258           }
3259
3260         }
3261         fg.getFlowNode(translateToDescTuple(pcLocTuple)).setSkeleton(true);
3262
3263         if (pcLocTuple.get(0).getLocDescriptor().equals(md.getThis())) {
3264           System.out.println("#########################################");
3265           for (Iterator iterator = flowNodeLowerthanPCLocSet.iterator(); iterator.hasNext();) {
3266             FlowNode lowerNode = (FlowNode) iterator.next();
3267             if (lowerNode.getDescTuple().size() == 1 && lowerNode.getCompositeLocation() == null) {
3268               NTuple<Location> lowerLocTuple = translateToLocTuple(md, lowerNode.getDescTuple());
3269               CompositeLocation newComp =
3270                   calculateCompositeLocationFromSubGlobalGraph(md, lowerNode);
3271               if (newComp != null) {
3272                 subGlobalFlowGraph.addMapLocationToInferCompositeLocation(lowerLocTuple.get(0),
3273                     newComp);
3274                 lowerNode.setCompositeLocation(newComp);
3275                 System.out.println("NEW COMP LOC=" + newComp + "    to lowerNode=" + lowerNode);
3276               }
3277
3278             }
3279
3280           }
3281         }
3282
3283       }
3284
3285     }
3286   }
3287
3288   private int countFirstDescriptorSetSize(Set<NTuple<Location>> set) {
3289
3290     Set<Descriptor> descSet = new HashSet<Descriptor>();
3291
3292     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
3293       NTuple<Location> locTuple = (NTuple<Location>) iterator.next();
3294       descSet.add(locTuple.get(0).getLocDescriptor());
3295     }
3296
3297     return descSet.size();
3298   }
3299
3300   private boolean coversAllParamters(MethodDescriptor md, FlowGraph fg,
3301       Set<NTuple<Location>> paramLocTupleHavingInFlowSet) {
3302
3303     int numParam = fg.getNumParameters();
3304     // int size = paramLocTupleHavingInFlowSet.size();
3305     int size = countFirstDescriptorSetSize(paramLocTupleHavingInFlowSet);
3306
3307     System.out.println("numParam=" + numParam + "     size=" + size);
3308
3309     // if (!md.isStatic()) {
3310     //
3311     // // if the method is not static && there is a parameter composite location &&
3312     // // it is started with 'this',
3313     // // paramLocTupleHavingInFlowSet need to have 'this' parameter.
3314     //
3315     // FlowNode thisParamNode = fg.getParamFlowNode(0);
3316     // NTuple<Location> thisParamLocTuple =
3317     // translateToLocTuple(md, thisParamNode.getCurrentDescTuple());
3318     //
3319     // if (!paramLocTupleHavingInFlowSet.contains(thisParamLocTuple)) {
3320     //
3321     // for (Iterator iterator = paramLocTupleHavingInFlowSet.iterator(); iterator.hasNext();) {
3322     // NTuple<Location> paramTuple = (NTuple<Location>) iterator.next();
3323     // if (paramTuple.size() > 1 && paramTuple.get(0).getLocDescriptor().equals(md.getThis())) {
3324     // // paramLocTupleHavingInFlowSet.add(thisParamLocTuple);
3325     // // break;
3326     // size++;
3327     // }
3328     // }
3329     //
3330     // }
3331     // }
3332
3333     if (size == numParam) {
3334       return true;
3335     } else {
3336       return false;
3337     }
3338
3339   }
3340
3341   private void calculateRETURNLOC(MethodDescriptor md) {
3342
3343     System.out.println("#calculateRETURNLOC= " + md);
3344
3345     // calculate a return location:
3346     // the return location type is lower than all parameters and the location of return values
3347     MethodSummary methodSummary = getMethodSummary(md);
3348     // if (methodSummary.getRETURNLoc() != null) {
3349     // System.out.println("$HERE?");
3350     // return;
3351     // }
3352
3353     FlowGraph fg = getFlowGraph(md);
3354     Map<Integer, CompositeLocation> mapParamToLoc = methodSummary.getMapParamIdxToInferLoc();
3355     Set<Integer> paramIdxSet = mapParamToLoc.keySet();
3356
3357     if (md.getReturnType() != null && !md.getReturnType().isVoid()) {
3358       // first, generate the set of return value location types that starts
3359       // with 'this' reference
3360
3361       Set<FlowNode> paramFlowNodeFlowingToReturnValueSet = getParamNodeFlowingToReturnValue(md);
3362       // System.out.println("paramFlowNodeFlowingToReturnValueSet="
3363       // + paramFlowNodeFlowingToReturnValueSet);
3364
3365       Set<NTuple<Location>> tupleToBeHigherThanReturnLocSet = new HashSet<NTuple<Location>>();
3366       for (Iterator iterator = paramFlowNodeFlowingToReturnValueSet.iterator(); iterator.hasNext();) {
3367         FlowNode fn = (FlowNode) iterator.next();
3368         NTuple<Descriptor> paramDescTuple = fn.getCurrentDescTuple();
3369         tupleToBeHigherThanReturnLocSet.add(translateToLocTuple(md, paramDescTuple));
3370       }
3371
3372       Set<FlowNode> returnNodeSet = fg.getReturnNodeSet();
3373       for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
3374         FlowNode returnNode = (FlowNode) iterator.next();
3375         NTuple<Descriptor> returnDescTuple = returnNode.getCurrentDescTuple();
3376         tupleToBeHigherThanReturnLocSet.add(translateToLocTuple(md, returnDescTuple));
3377       }
3378       System.out.println("-flow graph's returnNodeSet=" + returnNodeSet);
3379       System.out.println("tupleSetToBeHigherThanReturnLoc=" + tupleToBeHigherThanReturnLocSet);
3380
3381       // Here, generates a return location in the method lattice that is lower than the
3382       // locFlowingToReturnValueSet
3383       NTuple<Location> returnLocTuple =
3384           generateLocTupleRelativeTo(md, tupleToBeHigherThanReturnLocSet, RLOC);
3385
3386       // System.out.println("returnLocTuple=" + returnLocTuple);
3387       NTuple<Descriptor> returnDescTuple = translateToDescTuple(returnLocTuple);
3388       CompositeLocation curReturnLoc = methodSummary.getRETURNLoc();
3389       if (curReturnLoc == null || returnDescTuple.size() > curReturnLoc.getSize()) {
3390         methodSummary.setRETURNLoc(new CompositeLocation(returnLocTuple));
3391
3392         for (Iterator iterator = tupleToBeHigherThanReturnLocSet.iterator(); iterator.hasNext();) {
3393           NTuple<Location> higherTuple = (NTuple<Location>) iterator.next();
3394           fg.addValueFlowEdge(translateToDescTuple(higherTuple), returnDescTuple);
3395         }
3396         fg.getFlowNode(returnDescTuple).setSkeleton(true);
3397
3398       }
3399
3400       // makes sure that PCLOC is higher than RETURNLOC
3401       CompositeLocation pcLoc = methodSummary.getPCLoc();
3402       if (!pcLoc.get(0).isTop()) {
3403         NTuple<Descriptor> pcLocDescTuple = translateToDescTuple(pcLoc.getTuple());
3404         fg.addValueFlowEdge(pcLocDescTuple, returnDescTuple);
3405       }
3406
3407     }
3408
3409   }
3410
3411   private void calculateExtraLocations(MethodDescriptor md) {
3412     // calcualte pcloc, returnloc,...
3413
3414     System.out.println("\nSSJAVA:Calculate PCLOC/RETURNLOC locations: " + md);
3415
3416     calculatePCLOC(md);
3417     calculateRETURNLOC(md);
3418
3419   }
3420
3421   private NTuple<Location> generateLocTupleRelativeTo(MethodDescriptor md,
3422       Set<NTuple<Location>> paramLocTupleHavingInFlowSet, String locNamePrefix) {
3423
3424     // System.out.println("-generateLocTupleRelativeTo=" + paramLocTupleHavingInFlowSet);
3425
3426     NTuple<Location> higherLocTuple = new NTuple<Location>();
3427
3428     VarDescriptor thisVarDesc = md.getThis();
3429     // check if all paramter loc tuple is started with 'this' reference
3430     boolean hasParamNotStartedWithThisRef = false;
3431
3432     int minSize = 0;
3433
3434     Set<NTuple<Location>> paramLocTupleStartedWithThis = new HashSet<NTuple<Location>>();
3435
3436     next: for (Iterator iterator = paramLocTupleHavingInFlowSet.iterator(); iterator.hasNext();) {
3437       NTuple<Location> paramLocTuple = (NTuple<Location>) iterator.next();
3438       Descriptor paramLocalDesc = paramLocTuple.get(0).getLocDescriptor();
3439       if (!paramLocalDesc.equals(thisVarDesc)) {
3440
3441         Set<FlowNode> inNodeSet = getFlowGraph(md).getIncomingNodeSetByPrefix(paramLocalDesc);
3442         for (Iterator iterator2 = inNodeSet.iterator(); iterator2.hasNext();) {
3443           FlowNode flowNode = (FlowNode) iterator2.next();
3444           if (flowNode.getDescTuple().startsWith(thisVarDesc)) {
3445             // System.out.println("paramLocTuple=" + paramLocTuple + " is lower than THIS");
3446             continue next;
3447           }
3448         }
3449         hasParamNotStartedWithThisRef = true;
3450
3451       } else if (paramLocTuple.size() > 1) {
3452         paramLocTupleStartedWithThis.add(paramLocTuple);
3453         if (minSize == 0 || minSize > paramLocTuple.size()) {
3454           minSize = paramLocTuple.size();
3455         }
3456       }
3457     }
3458
3459     // System.out.println("---paramLocTupleStartedWithThis=" + paramLocTupleStartedWithThis);
3460     Descriptor enclosingDesc = md;
3461     if (hasParamNotStartedWithThisRef) {
3462       // in this case, PCLOC will be the local location
3463     } else {
3464       // all parameter is started with 'this', so PCLOC will be set relative to the composite
3465       // location started with 'this'.
3466       // for (int idx = 0; idx < minSize - 1; idx++) {
3467       for (int idx = 0; idx < 1; idx++) {
3468         Set<Descriptor> locDescSet = new HashSet<Descriptor>();
3469         Location curLoc = null;
3470         NTuple<Location> paramLocTuple = null;
3471         for (Iterator iterator = paramLocTupleStartedWithThis.iterator(); iterator.hasNext();) {
3472           paramLocTuple = (NTuple<Location>) iterator.next();
3473           // System.out.println("-----paramLocTuple=" + paramLocTuple + "  idx=" + idx);
3474           curLoc = paramLocTuple.get(idx);
3475           Descriptor locDesc = curLoc.getLocDescriptor();
3476           locDescSet.add(locDesc);
3477         }
3478         // System.out.println("-----locDescSet=" + locDescSet + " idx=" + idx);
3479         if (locDescSet.size() != 1) {
3480           break;
3481         }
3482         Location newLocElement = new Location(curLoc.getDescriptor(), curLoc.getLocDescriptor());
3483         System.out.println("newLocElement" + newLocElement);
3484         higherLocTuple.add(newLocElement);
3485         enclosingDesc = getClassTypeDescriptor(curLoc.getLocDescriptor());
3486       }
3487
3488     }
3489
3490     String locIdentifier = locNamePrefix + (locSeed++);
3491     NameDescriptor locDesc = new NameDescriptor(locIdentifier);
3492     Location newLoc = new Location(enclosingDesc, locDesc);
3493     higherLocTuple.add(newLoc);
3494     System.out.println("---new loc tuple=" + higherLocTuple);
3495
3496     return higherLocTuple;
3497
3498   }
3499
3500   public ClassDescriptor getClassTypeDescriptor(Descriptor in) {
3501
3502     if (in instanceof VarDescriptor) {
3503       return ((VarDescriptor) in).getType().getClassDesc();
3504     } else if (in instanceof FieldDescriptor) {
3505       return ((FieldDescriptor) in).getType().getClassDesc();
3506     }
3507     // else if (in instanceof LocationDescriptor) {
3508     // // here is the case that the descriptor 'in' is the last element of the assigned composite
3509     // // location
3510     // return ((VarDescriptor) locTuple.get(0).getLocDescriptor()).getType().getClassDesc();
3511     // }
3512     else {
3513       return null;
3514     }
3515
3516   }
3517
3518   private Set<NTuple<Location>> calculateHighestLocTupleSet(
3519       Set<NTuple<Location>> paramLocTupleHavingInFlowSet) {
3520
3521     Set<NTuple<Location>> highestSet = new HashSet<NTuple<Location>>();
3522
3523     Iterator<NTuple<Location>> iterator = paramLocTupleHavingInFlowSet.iterator();
3524     NTuple<Location> highest = iterator.next();
3525
3526     for (; iterator.hasNext();) {
3527       NTuple<Location> curLocTuple = (NTuple<Location>) iterator.next();
3528       if (isHigherThan(curLocTuple, highest)) {
3529         // System.out.println(curLocTuple + " is greater than " + highest);
3530         highest = curLocTuple;
3531       }
3532     }
3533
3534     highestSet.add(highest);
3535
3536     MethodDescriptor md = (MethodDescriptor) highest.get(0).getDescriptor();
3537     VarDescriptor thisVarDesc = md.getThis();
3538
3539     // System.out.println("highest=" + highest);
3540
3541     for (Iterator<NTuple<Location>> iter = paramLocTupleHavingInFlowSet.iterator(); iter.hasNext();) {
3542       NTuple<Location> curLocTuple = iter.next();
3543
3544       if (!curLocTuple.equals(highest) && !hasOrderingRelation(highest, curLocTuple)) {
3545
3546         // System.out.println("add it to the highest set=" + curLocTuple);
3547         highestSet.add(curLocTuple);
3548
3549       }
3550     }
3551
3552     return highestSet;
3553
3554   }
3555
3556   private Set<String> getHigherLocSymbolThan(SSJavaLattice<String> lattice, String loc) {
3557     Set<String> higherLocSet = new HashSet<String>();
3558
3559     Set<String> locSet = lattice.getTable().keySet();
3560     for (Iterator iterator = locSet.iterator(); iterator.hasNext();) {
3561       String element = (String) iterator.next();
3562       if (lattice.isGreaterThan(element, loc) && (!element.equals(lattice.getTopItem()))) {
3563         higherLocSet.add(element);
3564       }
3565     }
3566     return higherLocSet;
3567   }
3568
3569   private CompositeLocation getLowest(SSJavaLattice<String> methodLattice,
3570       Set<CompositeLocation> set) {
3571
3572     CompositeLocation lowest = set.iterator().next();
3573
3574     if (set.size() == 1) {
3575       return lowest;
3576     }
3577
3578     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
3579       CompositeLocation loc = (CompositeLocation) iterator.next();
3580
3581       if ((!loc.equals(lowest)) && (!isComparable(methodLattice, lowest, loc))) {
3582         // if there is a case where composite locations are incomparable, just
3583         // return null
3584         return null;
3585       }
3586
3587       if ((!loc.equals(lowest)) && isGreaterThan(methodLattice, lowest, loc)) {
3588         lowest = loc;
3589       }
3590     }
3591     return lowest;
3592   }
3593
3594   private boolean isComparable(SSJavaLattice<String> methodLattice, CompositeLocation comp1,
3595       CompositeLocation comp2) {
3596
3597     int size = comp1.getSize() >= comp2.getSize() ? comp2.getSize() : comp1.getSize();
3598
3599     for (int idx = 0; idx < size; idx++) {
3600       Location loc1 = comp1.get(idx);
3601       Location loc2 = comp2.get(idx);
3602
3603       Descriptor desc1 = loc1.getDescriptor();
3604       Descriptor desc2 = loc2.getDescriptor();
3605
3606       if (!desc1.equals(desc2)) {
3607         throw new Error("Fail to compare " + comp1 + " and " + comp2);
3608       }
3609
3610       String symbol1 = loc1.getLocIdentifier();
3611       String symbol2 = loc2.getLocIdentifier();
3612
3613       SSJavaLattice<String> lattice;
3614       if (idx == 0) {
3615         lattice = methodLattice;
3616       } else {
3617         lattice = getLattice(desc1);
3618       }
3619
3620       if (symbol1.equals(symbol2)) {
3621         continue;
3622       } else if (!lattice.isComparable(symbol1, symbol2)) {
3623         return false;
3624       }
3625
3626     }
3627
3628     return true;
3629   }
3630
3631   private boolean isGreaterThan(SSJavaLattice<String> methodLattice, CompositeLocation comp1,
3632       CompositeLocation comp2) {
3633
3634     int size = comp1.getSize() >= comp2.getSize() ? comp2.getSize() : comp1.getSize();
3635
3636     for (int idx = 0; idx < size; idx++) {
3637       Location loc1 = comp1.get(idx);
3638       Location loc2 = comp2.get(idx);
3639
3640       Descriptor desc1 = loc1.getDescriptor();
3641       Descriptor desc2 = loc2.getDescriptor();
3642
3643       if (!desc1.equals(desc2)) {
3644         throw new Error("Fail to compare " + comp1 + " and " + comp2);
3645       }
3646
3647       String symbol1 = loc1.getLocIdentifier();
3648       String symbol2 = loc2.getLocIdentifier();
3649
3650       SSJavaLattice<String> lattice;
3651       if (idx == 0) {
3652         lattice = methodLattice;
3653       } else {
3654         lattice = getLattice(desc1);
3655       }
3656
3657       if (symbol1.equals(symbol2)) {
3658         continue;
3659       } else if (lattice.isGreaterThan(symbol1, symbol2)) {
3660         return true;
3661       } else {
3662         return false;
3663       }
3664
3665     }
3666
3667     return false;
3668   }
3669
3670   private GlobalFlowGraph getSubGlobalFlowGraph(MethodDescriptor md) {
3671
3672     if (!mapMethodDescriptorToSubGlobalFlowGraph.containsKey(md)) {
3673       mapMethodDescriptorToSubGlobalFlowGraph.put(md, new GlobalFlowGraph(md));
3674     }
3675     return mapMethodDescriptorToSubGlobalFlowGraph.get(md);
3676   }
3677
3678   private void propagateFlowsToCallerWithNoCompositeLocation(MethodInvokeNode min,
3679       MethodDescriptor mdCaller, MethodDescriptor mdCallee) {
3680
3681     System.out.println("-propagateFlowsToCallerWithNoCompositeLocation=" + min.printNode(0));
3682     // if the parameter A reaches to the parameter B
3683     // then, add an edge the argument A -> the argument B to the caller's flow
3684     // graph
3685
3686     FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
3687     FlowGraph callerFlowGraph = getFlowGraph(mdCaller);
3688     int numParam = calleeFlowGraph.getNumParameters();
3689
3690     for (int i = 0; i < numParam; i++) {
3691       for (int k = 0; k < numParam; k++) {
3692
3693         if (i != k) {
3694
3695           FlowNode paramNode1 = calleeFlowGraph.getParamFlowNode(i);
3696           FlowNode paramNode2 = calleeFlowGraph.getParamFlowNode(k);
3697
3698           NTuple<Descriptor> arg1Tuple = getNodeTupleByArgIdx(min, i);
3699           NTuple<Descriptor> arg2Tuple = getNodeTupleByArgIdx(min, k);
3700
3701           // check if the callee propagates an ordering constraints through
3702           // parameters
3703
3704           // Set<FlowNode> localReachSet = calleeFlowGraph.getLocalReachFlowNodeSetFrom(paramNode1);
3705           Set<FlowNode> localReachSet =
3706               calleeFlowGraph.getReachableSetFrom(paramNode1.getDescTuple());
3707
3708           NTuple<Descriptor> paramDescTuple1 = paramNode1.getCurrentDescTuple();
3709           NTuple<Descriptor> paramDescTuple2 = paramNode2.getCurrentDescTuple();
3710
3711           // System.out.println("-param1CurTuple=" + paramDescTuple1 + " param2CurTuple="
3712           // + paramDescTuple2);
3713           // System.out.println("-- localReachSet from param1=" + localReachSet);
3714
3715           if (paramDescTuple1.get(0).equals(paramDescTuple2.get(0))) {
3716             // if two parameters share the same prefix
3717             // it already has been assigned to a composite location
3718             // so we don't need to add an additional ordering relation caused by these two
3719             // paramters.
3720             continue;
3721           }
3722
3723           if (arg1Tuple.size() > 0 && arg2Tuple.size() > 0
3724               && containsPrefix(paramNode2.getDescTuple().get(0), localReachSet)) {
3725             // need to propagate an ordering relation s.t. arg1 is higher
3726             // than arg2
3727             // System.out.println("-param1=" + paramNode1 + " is higher than param2=" + paramNode2);
3728
3729             // add a new flow between the corresponding arguments.
3730             callerFlowGraph.addValueFlowEdge(arg1Tuple, arg2Tuple);
3731             // System.out.println("arg1=" + arg1Tuple + "   arg2=" + arg2Tuple);
3732
3733             // System.out
3734             // .println("-arg1Tuple=" + arg1Tuple + " is higher than arg2Tuple=" + arg2Tuple);
3735
3736           }
3737
3738           // System.out.println();
3739         }
3740       }
3741     }
3742
3743     // if a parameter has a composite location and the first element of the parameter location
3744     // matches the callee's 'this'
3745     // we have a more specific constraint: the caller's corresponding argument is higher than the
3746     // parameter location which is translated into the caller
3747
3748     for (int idx = 0; idx < numParam; idx++) {
3749       FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx);
3750       CompositeLocation compLoc = paramNode.getCompositeLocation();
3751       System.out.println("paramNode=" + paramNode + "   compLoc=" + compLoc);
3752       if (compLoc != null && compLoc.get(0).getLocDescriptor().equals(min.getMethod().getThis())) {
3753         System.out.println("$$$COMPLOC CASE=" + compLoc + "  idx=" + idx);
3754
3755         NTuple<Descriptor> argTuple = getNodeTupleByArgIdx(min, idx);
3756         System.out.println("--- argTuple=" + argTuple + " current compLoc="
3757             + callerFlowGraph.getFlowNode(argTuple).getCompositeLocation());
3758
3759         NTuple<Descriptor> translatedParamTuple =
3760             translateCompositeLocationToCaller(idx, min, compLoc);
3761         System.out.println("add a flow edge= " + argTuple + "->" + translatedParamTuple);
3762         callerFlowGraph.addValueFlowEdge(argTuple, translatedParamTuple);
3763
3764         Set<NTuple<Location>> pcLocTupleSet = getPCLocTupleSet(min);
3765         for (Iterator iterator = pcLocTupleSet.iterator(); iterator.hasNext();) {
3766           NTuple<Location> pcLocTuple = (NTuple<Location>) iterator.next();
3767           callerFlowGraph.addValueFlowEdge(translateToDescTuple(pcLocTuple), translatedParamTuple);
3768         }
3769
3770       }
3771     }
3772
3773   }
3774
3775   private boolean containsPrefix(Descriptor prefixDesc, Set<FlowNode> set) {
3776
3777     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
3778       FlowNode flowNode = (FlowNode) iterator.next();
3779       if (flowNode.getDescTuple().startsWith(prefixDesc)) {
3780         System.out.println("FOUND=" + flowNode);
3781         return true;
3782       }
3783     }
3784     return false;
3785   }
3786
3787   private NTuple<Descriptor> translateCompositeLocationToCaller(int idx, MethodInvokeNode min,
3788       CompositeLocation compLocForParam1) {
3789
3790     NTuple<Descriptor> baseTuple = mapMethodInvokeNodeToBaseTuple.get(min);
3791
3792     NTuple<Descriptor> tuple = new NTuple<Descriptor>();
3793     for (int i = 0; i < baseTuple.size(); i++) {
3794       tuple.add(baseTuple.get(i));
3795     }
3796
3797     for (int i = 1; i < compLocForParam1.getSize(); i++) {
3798       Location loc = compLocForParam1.get(i);
3799       tuple.add(loc.getLocDescriptor());
3800     }
3801
3802     return tuple;
3803   }
3804
3805   private CompositeLocation generateCompositeLocation(NTuple<Location> prefixLocTuple) {
3806
3807     System.out.println("generateCompositeLocation=" + prefixLocTuple);
3808
3809     CompositeLocation newCompLoc = new CompositeLocation();
3810     for (int i = 0; i < prefixLocTuple.size(); i++) {
3811       newCompLoc.addLocation(prefixLocTuple.get(i));
3812     }
3813
3814     Descriptor lastDescOfPrefix = prefixLocTuple.get(prefixLocTuple.size() - 1).getLocDescriptor();
3815
3816     ClassDescriptor enclosingDescriptor;
3817     if (lastDescOfPrefix instanceof FieldDescriptor) {
3818       enclosingDescriptor = ((FieldDescriptor) lastDescOfPrefix).getType().getClassDesc();
3819       // System.out.println("enclosingDescriptor0=" + enclosingDescriptor);
3820     } else if (lastDescOfPrefix.equals(GLOBALDESC)) {
3821       MethodDescriptor currentMethodDesc = (MethodDescriptor) prefixLocTuple.get(0).getDescriptor();
3822       enclosingDescriptor = currentMethodDesc.getClassDesc();
3823     } else {
3824       // var descriptor case
3825       enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc();
3826     }
3827     // System.out.println("enclosingDescriptor=" + enclosingDescriptor);
3828
3829     LocationDescriptor newLocDescriptor = generateNewLocationDescriptor();
3830     newLocDescriptor.setEnclosingClassDesc(enclosingDescriptor);
3831
3832     Location newLoc = new Location(enclosingDescriptor, newLocDescriptor.getSymbol());
3833     newLoc.setLocDescriptor(newLocDescriptor);
3834     newCompLoc.addLocation(newLoc);
3835
3836     // System.out.println("--newCompLoc=" + newCompLoc);
3837     return newCompLoc;
3838   }
3839
3840   private CompositeLocation generateCompositeLocation(MethodDescriptor md,
3841       NTuple<Descriptor> paramPrefix) {
3842
3843     System.out.println("generateCompositeLocation=" + paramPrefix);
3844
3845     CompositeLocation newCompLoc = convertToCompositeLocation(md, paramPrefix);
3846
3847     Descriptor lastDescOfPrefix = paramPrefix.get(paramPrefix.size() - 1);
3848     // System.out.println("lastDescOfPrefix=" + lastDescOfPrefix + "  kind="
3849     // + lastDescOfPrefix.getClass());
3850     ClassDescriptor enclosingDescriptor;
3851     if (lastDescOfPrefix instanceof FieldDescriptor) {
3852       enclosingDescriptor = ((FieldDescriptor) lastDescOfPrefix).getType().getClassDesc();
3853       // System.out.println("enclosingDescriptor0=" + enclosingDescriptor);
3854     } else {
3855       // var descriptor case
3856       enclosingDescriptor = ((VarDescriptor) lastDescOfPrefix).getType().getClassDesc();
3857     }
3858     // System.out.println("enclosingDescriptor=" + enclosingDescriptor);
3859
3860     LocationDescriptor newLocDescriptor = generateNewLocationDescriptor();
3861     newLocDescriptor.setEnclosingClassDesc(enclosingDescriptor);
3862
3863     Location newLoc = new Location(enclosingDescriptor, newLocDescriptor.getSymbol());
3864     newLoc.setLocDescriptor(newLocDescriptor);
3865     newCompLoc.addLocation(newLoc);
3866
3867     // System.out.println("--newCompLoc=" + newCompLoc);
3868     return newCompLoc;
3869   }
3870
3871   private List<NTuple<Descriptor>> translatePrefixListToCallee(Descriptor baseRef,
3872       MethodDescriptor mdCallee, List<NTuple<Descriptor>> callerPrefixList) {
3873
3874     List<NTuple<Descriptor>> calleePrefixList = new ArrayList<NTuple<Descriptor>>();
3875
3876     for (int i = 0; i < callerPrefixList.size(); i++) {
3877       NTuple<Descriptor> prefix = callerPrefixList.get(i);
3878       if (prefix.startsWith(baseRef)) {
3879         NTuple<Descriptor> calleePrefix = new NTuple<Descriptor>();
3880         calleePrefix.add(mdCallee.getThis());
3881         for (int k = 1; k < prefix.size(); k++) {
3882           calleePrefix.add(prefix.get(k));
3883         }
3884         calleePrefixList.add(calleePrefix);
3885       }
3886     }
3887
3888     return calleePrefixList;
3889
3890   }
3891
3892   public CompositeLocation convertToCompositeLocation(MethodDescriptor md, NTuple<Descriptor> tuple) {
3893
3894     CompositeLocation compLoc = new CompositeLocation();
3895
3896     Descriptor enclosingDescriptor = md;
3897
3898     for (int i = 0; i < tuple.size(); i++) {
3899       Descriptor curDescriptor = tuple.get(i);
3900       Location locElement = new Location(enclosingDescriptor, curDescriptor.getSymbol());
3901       locElement.setLocDescriptor(curDescriptor);
3902       compLoc.addLocation(locElement);
3903
3904       if (curDescriptor instanceof VarDescriptor) {
3905         enclosingDescriptor = md.getClassDesc();
3906       } else if (curDescriptor instanceof FieldDescriptor) {
3907         enclosingDescriptor = ((FieldDescriptor) curDescriptor).getClassDescriptor();
3908       } else if (curDescriptor instanceof NameDescriptor) {
3909         // it is "GLOBAL LOC" case!
3910         enclosingDescriptor = GLOBALDESC;
3911       } else if (curDescriptor instanceof InterDescriptor) {
3912         enclosingDescriptor = getFlowGraph(md).getEnclosingDescriptor(curDescriptor);
3913       } else {
3914         enclosingDescriptor = null;
3915       }
3916
3917     }
3918
3919     return compLoc;
3920   }
3921
3922   private LocationDescriptor generateNewLocationDescriptor() {
3923     return new LocationDescriptor("Loc" + (locSeed++));
3924   }
3925
3926   private int getPrefixIndex(NTuple<Descriptor> tuple1, NTuple<Descriptor> tuple2) {
3927
3928     // return the index where the prefix shared by tuple1 and tuple2 is ended
3929     // if there is no prefix shared by both of them, return -1
3930
3931     int minSize = tuple1.size();
3932     if (minSize > tuple2.size()) {
3933       minSize = tuple2.size();
3934     }
3935
3936     int idx = -1;
3937     for (int i = 0; i < minSize; i++) {
3938       if (!tuple1.get(i).equals(tuple2.get(i))) {
3939         break;
3940       } else {
3941         idx++;
3942       }
3943     }
3944
3945     return idx;
3946   }
3947
3948   private CompositeLocation generateInferredCompositeLocation(MethodLocationInfo methodInfo,
3949       NTuple<Location> tuple) {
3950
3951     // first, retrieve inferred location by the local var descriptor
3952     CompositeLocation inferLoc = new CompositeLocation();
3953
3954     CompositeLocation localVarInferLoc =
3955         methodInfo.getInferLocation(tuple.get(0).getLocDescriptor());
3956
3957     localVarInferLoc.get(0).setLocDescriptor(tuple.get(0).getLocDescriptor());
3958
3959     for (int i = 0; i < localVarInferLoc.getSize(); i++) {
3960       inferLoc.addLocation(localVarInferLoc.get(i));
3961     }
3962
3963     for (int i = 1; i < tuple.size(); i++) {
3964       Location cur = tuple.get(i);
3965       Descriptor enclosingDesc = cur.getDescriptor();
3966       Descriptor curDesc = cur.getLocDescriptor();
3967
3968       Location inferLocElement;
3969       if (curDesc == null) {
3970         // in this case, we have a newly generated location.
3971         inferLocElement = new Location(enclosingDesc, cur.getLocIdentifier());
3972       } else {
3973         String fieldLocSymbol =
3974             getLocationInfo(enclosingDesc).getInferLocation(curDesc).get(0).getLocIdentifier();
3975         inferLocElement = new Location(enclosingDesc, fieldLocSymbol);
3976         inferLocElement.setLocDescriptor(curDesc);
3977       }
3978
3979       inferLoc.addLocation(inferLocElement);
3980
3981     }
3982
3983     assert (inferLoc.get(0).getLocDescriptor().getSymbol() == inferLoc.get(0).getLocIdentifier());
3984     return inferLoc;
3985   }
3986
3987   public LocationInfo getLocationInfo(Descriptor d) {
3988     if (d instanceof MethodDescriptor) {
3989       return getMethodLocationInfo((MethodDescriptor) d);
3990     } else {
3991       return getFieldLocationInfo((ClassDescriptor) d);
3992     }
3993   }
3994
3995   private MethodLocationInfo getMethodLocationInfo(MethodDescriptor md) {
3996
3997     if (!mapMethodDescToMethodLocationInfo.containsKey(md)) {
3998       mapMethodDescToMethodLocationInfo.put(md, new MethodLocationInfo(md));
3999     }
4000
4001     return mapMethodDescToMethodLocationInfo.get(md);
4002
4003   }
4004
4005   private LocationInfo getFieldLocationInfo(ClassDescriptor cd) {
4006
4007     if (!mapClassToLocationInfo.containsKey(cd)) {
4008       mapClassToLocationInfo.put(cd, new LocationInfo(cd));
4009     }
4010
4011     return mapClassToLocationInfo.get(cd);
4012
4013   }
4014
4015   private void addPrefixMapping(Map<NTuple<Location>, Set<NTuple<Location>>> map,
4016       NTuple<Location> prefix, NTuple<Location> element) {
4017
4018     if (!map.containsKey(prefix)) {
4019       map.put(prefix, new HashSet<NTuple<Location>>());
4020     }
4021     map.get(prefix).add(element);
4022   }
4023
4024   private boolean containsNonPrimitiveElement(Set<Descriptor> descSet) {
4025     for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
4026       Descriptor desc = (Descriptor) iterator.next();
4027
4028       if (desc.equals(LocationInference.GLOBALDESC)) {
4029         return true;
4030       } else if (desc instanceof VarDescriptor) {
4031         if (!((VarDescriptor) desc).getType().isPrimitive()) {
4032           return true;
4033         }
4034       } else if (desc instanceof FieldDescriptor) {
4035         if (!((FieldDescriptor) desc).getType().isPrimitive()) {
4036           return true;
4037         }
4038       }
4039
4040     }
4041     return false;
4042   }
4043
4044   private SSJavaLattice<String> getLattice(Descriptor d) {
4045     if (d instanceof MethodDescriptor) {
4046       return getMethodLattice((MethodDescriptor) d);
4047     } else {
4048       return getFieldLattice((ClassDescriptor) d);
4049     }
4050   }
4051
4052   private SSJavaLattice<String> getMethodLattice(MethodDescriptor md) {
4053     if (!md2lattice.containsKey(md)) {
4054       md2lattice.put(md, new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM));
4055     }
4056     return md2lattice.get(md);
4057   }
4058
4059   private void setMethodLattice(MethodDescriptor md, SSJavaLattice<String> lattice) {
4060     md2lattice.put(md, lattice);
4061   }
4062
4063   private void extractFlowsBetweenFields(ClassDescriptor cd, FlowNode srcNode, FlowNode dstNode,
4064       int idx) {
4065
4066     NTuple<Descriptor> srcCurTuple = srcNode.getCurrentDescTuple();
4067     NTuple<Descriptor> dstCurTuple = dstNode.getCurrentDescTuple();
4068
4069     if (srcCurTuple.get(idx).equals(dstCurTuple.get(idx)) && srcCurTuple.size() > (idx + 1)
4070         && dstCurTuple.size() > (idx + 1)) {
4071       // value flow between fields: we don't need to add a binary relation
4072       // for this case
4073
4074       Descriptor desc = srcCurTuple.get(idx);
4075       ClassDescriptor classDesc;
4076
4077       if (idx == 0) {
4078         classDesc = ((VarDescriptor) desc).getType().getClassDesc();
4079       } else {
4080         if (desc instanceof FieldDescriptor) {
4081           classDesc = ((FieldDescriptor) desc).getType().getClassDesc();
4082         } else {
4083           // this case is that the local variable has a composite location assignment
4084           // the following element after the composite location to the local variable
4085           // has the enclosing descriptor of the local variable
4086           Descriptor localDesc = srcNode.getDescTuple().get(0);
4087           classDesc = ((VarDescriptor) localDesc).getType().getClassDesc();
4088         }
4089       }
4090       extractFlowsBetweenFields(classDesc, srcNode, dstNode, idx + 1);
4091
4092     } else {
4093
4094       Descriptor srcFieldDesc = srcCurTuple.get(idx);
4095       Descriptor dstFieldDesc = dstCurTuple.get(idx);
4096
4097       System.out.println("srcFieldDesc=" + srcFieldDesc + "  dstFieldDesc=" + dstFieldDesc
4098           + "   idx=" + idx);
4099       if (!srcFieldDesc.equals(dstFieldDesc)) {
4100         // add a new edge
4101         System.out.println("-ADD EDGE");
4102         getHierarchyGraph(cd).addEdge(srcFieldDesc, dstFieldDesc);
4103       } else if (!isReference(srcFieldDesc) && !isReference(dstFieldDesc)) {
4104         System.out.println("-ADD EDGE");
4105         getHierarchyGraph(cd).addEdge(srcFieldDesc, dstFieldDesc);
4106       }
4107
4108     }
4109
4110   }
4111
4112   public SSJavaLattice<String> getFieldLattice(ClassDescriptor cd) {
4113     if (!cd2lattice.containsKey(cd)) {
4114       cd2lattice.put(cd, new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM));
4115     }
4116     return cd2lattice.get(cd);
4117   }
4118
4119   public LinkedList<MethodDescriptor> computeMethodList() {
4120
4121     Set<MethodDescriptor> toSort = new HashSet<MethodDescriptor>();
4122
4123     setupToAnalyze();
4124
4125     Set<MethodDescriptor> visited = new HashSet<MethodDescriptor>();
4126     Set<MethodDescriptor> reachableCallee = new HashSet<MethodDescriptor>();
4127
4128     while (!toAnalyzeIsEmpty()) {
4129       ClassDescriptor cd = toAnalyzeNext();
4130
4131       setupToAnalazeMethod(cd);
4132       temp_toanalyzeMethodList.removeAll(visited);
4133
4134       while (!toAnalyzeMethodIsEmpty()) {
4135         MethodDescriptor md = toAnalyzeMethodNext();
4136         if ((!visited.contains(md))
4137             && (ssjava.needTobeAnnotated(md) || reachableCallee.contains(md))) {
4138
4139           // creates a mapping from a method descriptor to virtual methods
4140           Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
4141           if (md.isStatic()) {
4142             setPossibleCallees.add(md);
4143           } else {
4144             setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md));
4145           }
4146
4147           Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getCalleeSet(md);
4148           Set<MethodDescriptor> needToAnalyzeCalleeSet = new HashSet<MethodDescriptor>();
4149
4150           for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) {
4151             MethodDescriptor calleemd = (MethodDescriptor) iterator.next();
4152             if ((!ssjava.isTrustMethod(calleemd))
4153                 && (!ssjava.isSSJavaUtil(calleemd.getClassDesc()))
4154                 && (!calleemd.getModifiers().isNative())) {
4155               if (!visited.contains(calleemd)) {
4156                 temp_toanalyzeMethodList.add(calleemd);
4157               }
4158               reachableCallee.add(calleemd);
4159               needToAnalyzeCalleeSet.add(calleemd);
4160             }
4161           }
4162
4163           mapMethodToCalleeSet.put(md, needToAnalyzeCalleeSet);
4164
4165           visited.add(md);
4166
4167           toSort.add(md);
4168         }
4169       }
4170     }
4171
4172     return ssjava.topologicalSort(toSort);
4173
4174   }
4175
4176   public boolean isTransitivelyCalledFrom(MethodDescriptor callee, MethodDescriptor caller) {
4177     // if the callee is transitively invoked from the caller
4178     // return true;
4179
4180     int callerIdx = toanalyze_methodDescList.indexOf(caller);
4181     int calleeIdx = toanalyze_methodDescList.indexOf(callee);
4182
4183     if (callerIdx < calleeIdx) {
4184       return true;
4185     }
4186
4187     return false;
4188
4189   }
4190
4191   public void constructFlowGraph() {
4192
4193     System.out.println("");
4194     toanalyze_methodDescList = computeMethodList();
4195
4196     // hack... it seems that there is a problem with topological sorting.
4197     // so String.toString(Object o) is appeared too higher in the call chain.
4198     MethodDescriptor mdToString = null;
4199     for (Iterator iterator = toanalyze_methodDescList.iterator(); iterator.hasNext();) {
4200       MethodDescriptor md = (MethodDescriptor) iterator.next();
4201       if (md.toString().equals("public static String String.valueOf(Object o)")) {
4202         mdToString = md;
4203         break;
4204       }
4205     }
4206     if (mdToString != null) {
4207       toanalyze_methodDescList.remove(mdToString);
4208       toanalyze_methodDescList.addLast(mdToString);
4209     }
4210
4211     LinkedList<MethodDescriptor> methodDescList =
4212         (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
4213
4214     System.out.println("@@@methodDescList=" + methodDescList);
4215     // System.exit(0);
4216
4217     while (!methodDescList.isEmpty()) {
4218       MethodDescriptor md = methodDescList.removeLast();
4219       if (state.SSJAVADEBUG) {
4220         System.out.println();
4221         System.out.println("SSJAVA: Constructing a flow graph: " + md);
4222
4223         // creates a mapping from a parameter descriptor to its index
4224         Map<Descriptor, Integer> mapParamDescToIdx = new HashMap<Descriptor, Integer>();
4225         int offset = 0;
4226         if (!md.isStatic()) {
4227           offset = 1;
4228           mapParamDescToIdx.put(md.getThis(), 0);
4229         }
4230
4231         for (int i = 0; i < md.numParameters(); i++) {
4232           Descriptor paramDesc = (Descriptor) md.getParameter(i);
4233           mapParamDescToIdx.put(paramDesc, new Integer(i + offset));
4234         }
4235
4236         FlowGraph fg = new FlowGraph(md, mapParamDescToIdx);
4237         mapMethodDescriptorToFlowGraph.put(md, fg);
4238
4239         analyzeMethodBody(md.getClassDesc(), md);
4240
4241         // System.out.println("##constructSubGlobalFlowGraph");
4242         // GlobalFlowGraph subGlobalFlowGraph = constructSubGlobalFlowGraph(fg);
4243         // mapMethodDescriptorToSubGlobalFlowGraph.put(md, subGlobalFlowGraph);
4244         //
4245         // // TODO
4246         // System.out.println("##addValueFlowsFromCalleeSubGlobalFlowGraph");
4247         // addValueFlowsFromCalleeSubGlobalFlowGraph(md, subGlobalFlowGraph);
4248         // subGlobalFlowGraph.writeGraph("_SUBGLOBAL");
4249         //
4250         // propagateFlowsFromCalleesWithNoCompositeLocation(md);
4251       }
4252     }
4253     // _debug_printGraph();
4254
4255   }
4256
4257   private void constructGlobalFlowGraph() {
4258     LinkedList<MethodDescriptor> methodDescList =
4259         (LinkedList<MethodDescriptor>) toanalyze_methodDescList.clone();
4260
4261     while (!methodDescList.isEmpty()) {
4262       MethodDescriptor md = methodDescList.removeLast();
4263       if (state.SSJAVADEBUG) {
4264         System.out.println();
4265         System.out.println("SSJAVA: Constructing a sub global flow graph: " + md);
4266
4267         constructSubGlobalFlowGraph(getFlowGraph(md));
4268
4269         // TODO
4270         System.out.println("-add Value Flows From CalleeSubGlobalFlowGraph");
4271         addValueFlowsFromCalleeSubGlobalFlowGraph(md);
4272         // subGlobalFlowGraph.writeGraph("_SUBGLOBAL");
4273
4274         // System.out.println("-propagate Flows From Callees With No CompositeLocation");
4275         // propagateFlowsFromCalleesWithNoCompositeLocation(md);
4276
4277         // mark if a parameter has incoming flows
4278         checkParamNodesInSubGlobalFlowGraph(md);
4279
4280       }
4281     }
4282   }
4283
4284   private void checkParamNodesInSubGlobalFlowGraph(MethodDescriptor md) {
4285     GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
4286     FlowGraph flowGraph = getFlowGraph(md);
4287
4288     Set<FlowNode> paramFlowNodeSet = flowGraph.getParamFlowNodeSet();
4289     for (Iterator iterator = paramFlowNodeSet.iterator(); iterator.hasNext();) {
4290       FlowNode paramFlowNode = (FlowNode) iterator.next();
4291       System.out.println("paramFlowNode=" + paramFlowNode);
4292       NTuple<Descriptor> paramDescTuple = paramFlowNode.getDescTuple();
4293       NTuple<Location> paramLocTuple = translateToLocTuple(md, paramDescTuple);
4294       GlobalFlowNode paramGlobalNode = globalFlowGraph.getFlowNode(paramLocTuple);
4295
4296       Set<GlobalFlowNode> incomingNodeSet =
4297           globalFlowGraph.getIncomingNodeSetByPrefix(paramLocTuple.get(0));
4298
4299       if (incomingNodeSet.size() > 0) {
4300         paramGlobalNode.setParamNodeWithIncomingFlows(true);
4301       }
4302
4303     }
4304   }
4305
4306   private Set<MethodInvokeNode> getMethodInvokeNodeSet(MethodDescriptor md) {
4307     if (!mapMethodDescriptorToMethodInvokeNodeSet.containsKey(md)) {
4308       mapMethodDescriptorToMethodInvokeNodeSet.put(md, new HashSet<MethodInvokeNode>());
4309     }
4310     return mapMethodDescriptorToMethodInvokeNodeSet.get(md);
4311   }
4312
4313   private void propagateFlowsFromCalleesWithNoCompositeLocation(MethodDescriptor mdCaller) {
4314
4315     // the transformation for a call site propagates flows through parameters
4316     // if the method is virtual, it also grab all relations from any possible
4317     // callees
4318
4319     Set<MethodInvokeNode> setMethodInvokeNode =
4320         mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller);
4321
4322     if (setMethodInvokeNode != null) {
4323
4324       for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) {
4325         MethodInvokeNode min = (MethodInvokeNode) iterator.next();
4326         MethodDescriptor mdCallee = min.getMethod();
4327         Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
4328         if (mdCallee.isStatic()) {
4329           setPossibleCallees.add(mdCallee);
4330         } else {
4331           Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getMethods(mdCallee);
4332           // removes method descriptors that are not invoked by the caller
4333           calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller));
4334           setPossibleCallees.addAll(calleeSet);
4335         }
4336
4337         for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
4338           MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
4339           propagateFlowsToCallerWithNoCompositeLocation(min, mdCaller, possibleMdCallee);
4340         }
4341
4342       }
4343     }
4344
4345   }
4346
4347   private void analyzeMethodBody(ClassDescriptor cd, MethodDescriptor md) {
4348     BlockNode bn = state.getMethodBody(md);
4349     NodeTupleSet implicitFlowTupleSet = new NodeTupleSet();
4350     analyzeFlowBlockNode(md, md.getParameterTable(), bn, implicitFlowTupleSet);
4351   }
4352
4353   private void analyzeFlowBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn,
4354       NodeTupleSet implicitFlowTupleSet) {
4355
4356     bn.getVarTable().setParent(nametable);
4357     for (int i = 0; i < bn.size(); i++) {
4358       BlockStatementNode bsn = bn.get(i);
4359       analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet);
4360     }
4361
4362   }
4363
4364   private void analyzeBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
4365       BlockStatementNode bsn, NodeTupleSet implicitFlowTupleSet) {
4366
4367     switch (bsn.kind()) {
4368     case Kind.BlockExpressionNode:
4369       analyzeBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn, implicitFlowTupleSet);
4370       break;
4371
4372     case Kind.DeclarationNode:
4373       analyzeFlowDeclarationNode(md, nametable, (DeclarationNode) bsn, implicitFlowTupleSet);
4374       break;
4375
4376     case Kind.IfStatementNode:
4377       analyzeFlowIfStatementNode(md, nametable, (IfStatementNode) bsn, implicitFlowTupleSet);
4378       break;
4379
4380     case Kind.LoopNode:
4381       analyzeFlowLoopNode(md, nametable, (LoopNode) bsn, implicitFlowTupleSet);
4382       break;
4383
4384     case Kind.ReturnNode:
4385       analyzeFlowReturnNode(md, nametable, (ReturnNode) bsn, implicitFlowTupleSet);
4386       break;
4387
4388     case Kind.SubBlockNode:
4389       analyzeFlowSubBlockNode(md, nametable, (SubBlockNode) bsn, implicitFlowTupleSet);
4390       break;
4391
4392     case Kind.ContinueBreakNode:
4393       break;
4394
4395     case Kind.SwitchStatementNode:
4396       analyzeSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn, implicitFlowTupleSet);
4397       break;
4398
4399     }
4400
4401   }
4402
4403   private void analyzeSwitchBlockNode(MethodDescriptor md, SymbolTable nametable,
4404       SwitchBlockNode sbn, NodeTupleSet implicitFlowTupleSet) {
4405
4406     analyzeFlowBlockNode(md, nametable, sbn.getSwitchBlockStatement(), implicitFlowTupleSet);
4407
4408   }
4409
4410   private void analyzeSwitchStatementNode(MethodDescriptor md, SymbolTable nametable,
4411       SwitchStatementNode ssn, NodeTupleSet implicitFlowTupleSet) {
4412
4413     NodeTupleSet condTupleNode = new NodeTupleSet();
4414     analyzeFlowExpressionNode(md, nametable, ssn.getCondition(), condTupleNode, null,
4415         implicitFlowTupleSet, false);
4416
4417     NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
4418
4419     newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
4420     newImplicitTupleSet.addTupleSet(condTupleNode);
4421
4422     if (needToGenerateInterLoc(newImplicitTupleSet)) {
4423       // need to create an intermediate node for the GLB of conditional
4424       // locations & implicit flows
4425       System.out.println("10");
4426
4427       NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
4428       for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) {
4429         NTuple<Descriptor> tuple = idxIter.next();
4430         addFlowGraphEdge(md, tuple, interTuple);
4431       }
4432       newImplicitTupleSet.clear();
4433       newImplicitTupleSet.addTuple(interTuple);
4434     }
4435
4436     BlockNode sbn = ssn.getSwitchBody();
4437     for (int i = 0; i < sbn.size(); i++) {
4438       analyzeSwitchBlockNode(md, nametable, (SwitchBlockNode) sbn.get(i), newImplicitTupleSet);
4439     }
4440
4441   }
4442
4443   private void analyzeFlowSubBlockNode(MethodDescriptor md, SymbolTable nametable,
4444       SubBlockNode sbn, NodeTupleSet implicitFlowTupleSet) {
4445     analyzeFlowBlockNode(md, nametable, sbn.getBlockNode(), implicitFlowTupleSet);
4446   }
4447
4448   private void analyzeFlowReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode rn,
4449       NodeTupleSet implicitFlowTupleSet) {
4450
4451     // System.out.println("-analyzeFlowReturnNode=" + rn.printNode(0));
4452     ExpressionNode returnExp = rn.getReturnExpression();
4453
4454     if (returnExp != null) {
4455       NodeTupleSet nodeSet = new NodeTupleSet();
4456       // if a return expression returns a literal value, nodeSet is empty
4457       analyzeFlowExpressionNode(md, nametable, returnExp, nodeSet, false);
4458       FlowGraph fg = getFlowGraph(md);
4459
4460       // if (implicitFlowTupleSet.size() == 1
4461       // &&
4462       // fg.getFlowNode(implicitFlowTupleSet.iterator().next()).isIntermediate())
4463       // {
4464       //
4465       // // since there is already an intermediate node for the GLB of implicit
4466       // flows
4467       // // we don't need to create another intermediate node.
4468       // // just re-use the intermediate node for implicit flows.
4469       //
4470       // FlowNode meetNode =
4471       // fg.getFlowNode(implicitFlowTupleSet.iterator().next());
4472       //
4473       // for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
4474       // NTuple<Descriptor> returnNodeTuple = (NTuple<Descriptor>)
4475       // iterator.next();
4476       // fg.addValueFlowEdge(returnNodeTuple, meetNode.getDescTuple());
4477       // }
4478       //
4479       // }
4480
4481       NodeTupleSet currentFlowTupleSet = new NodeTupleSet();
4482
4483       // add tuples from return node
4484       currentFlowTupleSet.addTupleSet(nodeSet);
4485
4486       // add tuples corresponding to the current implicit flows
4487       currentFlowTupleSet.addTupleSet(implicitFlowTupleSet);
4488
4489       // System.out.println("---currentFlowTupleSet=" + currentFlowTupleSet);
4490
4491       if (needToGenerateInterLoc(currentFlowTupleSet)) {
4492         System.out.println("9");
4493
4494         FlowNode meetNode = fg.createIntermediateNode();
4495         for (Iterator iterator = currentFlowTupleSet.iterator(); iterator.hasNext();) {
4496           NTuple<Descriptor> currentFlowTuple = (NTuple<Descriptor>) iterator.next();
4497           fg.addValueFlowEdge(currentFlowTuple, meetNode.getDescTuple());
4498         }
4499         fg.addReturnFlowNode(meetNode.getDescTuple());
4500       } else {
4501         // currentFlowTupleSet = removeLiteralTuple(currentFlowTupleSet);
4502         for (Iterator iterator = currentFlowTupleSet.iterator(); iterator.hasNext();) {
4503           NTuple<Descriptor> currentFlowTuple = (NTuple<Descriptor>) iterator.next();
4504           fg.addReturnFlowNode(currentFlowTuple);
4505         }
4506       }
4507
4508     }
4509
4510   }
4511
4512   private NodeTupleSet removeLiteralTuple(NodeTupleSet inSet) {
4513     NodeTupleSet tupleSet = new NodeTupleSet();
4514     for (Iterator<NTuple<Descriptor>> iter = inSet.iterator(); iter.hasNext();) {
4515       NTuple<Descriptor> tuple = iter.next();
4516       if (!tuple.get(0).equals(LITERALDESC)) {
4517         tupleSet.addTuple(tuple);
4518       }
4519     }
4520     return tupleSet;
4521   }
4522
4523   private boolean needToGenerateInterLoc(NodeTupleSet tupleSet) {
4524     int size = 0;
4525     for (Iterator<NTuple<Descriptor>> iter = tupleSet.iterator(); iter.hasNext();) {
4526       NTuple<Descriptor> descTuple = iter.next();
4527       if (!descTuple.get(0).equals(LITERALDESC)) {
4528         size++;
4529       }
4530     }
4531     if (size > 1) {
4532       System.out.println("needToGenerateInterLoc=" + tupleSet + "  size=" + size);
4533       return true;
4534     } else {
4535       return false;
4536     }
4537   }
4538
4539   private void analyzeFlowLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln,
4540       NodeTupleSet implicitFlowTupleSet) {
4541
4542     if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) {
4543
4544       NodeTupleSet condTupleNode = new NodeTupleSet();
4545       analyzeFlowExpressionNode(md, nametable, ln.getCondition(), condTupleNode, null,
4546           implicitFlowTupleSet, false);
4547
4548       NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
4549
4550       newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
4551       newImplicitTupleSet.addTupleSet(condTupleNode);
4552
4553       newImplicitTupleSet.addGlobalFlowTupleSet(implicitFlowTupleSet.getGlobalLocTupleSet());
4554       newImplicitTupleSet.addGlobalFlowTupleSet(condTupleNode.getGlobalLocTupleSet());
4555
4556       if (needToGenerateInterLoc(newImplicitTupleSet)) {
4557         // need to create an intermediate node for the GLB of conditional
4558         // locations & implicit flows
4559         System.out.println("6");
4560
4561         NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
4562         for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter
4563             .hasNext();) {
4564           NTuple<Descriptor> tuple = idxIter.next();
4565           addFlowGraphEdge(md, tuple, interTuple);
4566         }
4567         newImplicitTupleSet.clear();
4568         newImplicitTupleSet.addTuple(interTuple);
4569
4570       }
4571
4572       // ///////////
4573       // System.out.println("condTupleNode="+condTupleNode);
4574       // NTuple<Descriptor> interTuple =
4575       // getFlowGraph(md).createIntermediateNode().getDescTuple();
4576       //
4577       // for (Iterator<NTuple<Descriptor>> idxIter = condTupleNode.iterator();
4578       // idxIter.hasNext();) {
4579       // NTuple<Descriptor> tuple = idxIter.next();
4580       // addFlowGraphEdge(md, tuple, interTuple);
4581       // }
4582
4583       // for (Iterator<NTuple<Descriptor>> idxIter =
4584       // implicitFlowTupleSet.iterator(); idxIter
4585       // .hasNext();) {
4586       // NTuple<Descriptor> tuple = idxIter.next();
4587       // addFlowGraphEdge(md, tuple, interTuple);
4588       // }
4589
4590       // NodeTupleSet newImplicitSet = new NodeTupleSet();
4591       // newImplicitSet.addTuple(interTuple);
4592       analyzeFlowBlockNode(md, nametable, ln.getBody(), newImplicitTupleSet);
4593       // ///////////
4594
4595       // condTupleNode.addTupleSet(implicitFlowTupleSet);
4596
4597       // add edges from condNodeTupleSet to all nodes of conditional nodes
4598       // analyzeFlowBlockNode(md, nametable, ln.getBody(), condTupleNode);
4599
4600     } else {
4601       // check 'for loop' case
4602       BlockNode bn = ln.getInitializer();
4603       bn.getVarTable().setParent(nametable);
4604       for (int i = 0; i < bn.size(); i++) {
4605         BlockStatementNode bsn = bn.get(i);
4606         analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet);
4607       }
4608
4609       NodeTupleSet condTupleNode = new NodeTupleSet();
4610       analyzeFlowExpressionNode(md, bn.getVarTable(), ln.getCondition(), condTupleNode, null,
4611           implicitFlowTupleSet, false);
4612
4613       NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
4614       newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
4615       newImplicitTupleSet.addTupleSet(condTupleNode);
4616
4617       if (needToGenerateInterLoc(newImplicitTupleSet)) {
4618         // need to create an intermediate node for the GLB of conditional
4619         // locations & implicit flows
4620         System.out.println("7");
4621
4622         NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
4623         for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter
4624             .hasNext();) {
4625           NTuple<Descriptor> tuple = idxIter.next();
4626           addFlowGraphEdge(md, tuple, interTuple);
4627         }
4628         newImplicitTupleSet.clear();
4629         newImplicitTupleSet.addTuple(interTuple);
4630
4631       }
4632
4633       // ///////////
4634       // NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
4635       //
4636       // for (Iterator<NTuple<Descriptor>> idxIter = condTupleNode.iterator(); idxIter.hasNext();) {
4637       // NTuple<Descriptor> tuple = idxIter.next();
4638       // addFlowGraphEdge(md, tuple, interTuple);
4639       // }
4640       //
4641       // for (Iterator<NTuple<Descriptor>> idxIter = implicitFlowTupleSet.iterator(); idxIter
4642       // .hasNext();) {
4643       // NTuple<Descriptor> tuple = idxIter.next();
4644       // addFlowGraphEdge(md, tuple, interTuple);
4645       // }
4646       //
4647       // NodeTupleSet newImplicitSet = new NodeTupleSet();
4648       // newImplicitSet.addTuple(interTuple);
4649       analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(), newImplicitTupleSet);
4650       analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(), newImplicitTupleSet);
4651       // ///////////
4652
4653       // condTupleNode.addTupleSet(implicitFlowTupleSet);
4654       //
4655       // analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(),
4656       // condTupleNode);
4657       // analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(),
4658       // condTupleNode);
4659
4660     }
4661
4662   }
4663
4664   private void analyzeFlowIfStatementNode(MethodDescriptor md, SymbolTable nametable,
4665       IfStatementNode isn, NodeTupleSet implicitFlowTupleSet) {
4666
4667     // System.out.println("analyzeFlowIfStatementNode=" + isn.printNode(0));
4668
4669     NodeTupleSet condTupleNode = new NodeTupleSet();
4670     analyzeFlowExpressionNode(md, nametable, isn.getCondition(), condTupleNode, null,
4671         implicitFlowTupleSet, false);
4672
4673     NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
4674
4675     newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
4676     newImplicitTupleSet.addTupleSet(condTupleNode);
4677
4678     // System.out.println("$$$GGGcondTupleNode=" + condTupleNode.getGlobalLocTupleSet());
4679     // System.out.println("-condTupleNode=" + condTupleNode);
4680     // System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet);
4681     // System.out.println("-newImplicitTupleSet=" + newImplicitTupleSet);
4682
4683     if (needToGenerateInterLoc(newImplicitTupleSet)) {
4684       System.out.println("5");
4685
4686       // need to create an intermediate node for the GLB of conditional locations & implicit flows
4687       NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
4688       for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) {
4689         NTuple<Descriptor> tuple = idxIter.next();
4690         addFlowGraphEdge(md, tuple, interTuple);
4691       }
4692       newImplicitTupleSet.clear();
4693       newImplicitTupleSet.addTuple(interTuple);
4694     }
4695
4696     // GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
4697     // for (Iterator<NTuple<Location>> iterator = condTupleNode.globalIterator();
4698     // iterator.hasNext();) {
4699     // NTuple<Location> calleeReturnLocTuple = iterator.next();
4700     // for (Iterator<NTuple<Descriptor>> iter2 = newImplicitTupleSet.iterator(); iter2.hasNext();) {
4701     // NTuple<Descriptor> callerImplicitTuple = iter2.next();
4702     // globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple,
4703     // translateToLocTuple(md, callerImplicitTuple));
4704     // }
4705     // }
4706     newImplicitTupleSet.addGlobalFlowTupleSet(condTupleNode.getGlobalLocTupleSet());
4707
4708     analyzeFlowBlockNode(md, nametable, isn.getTrueBlock(), newImplicitTupleSet);
4709
4710     if (isn.getFalseBlock() != null) {
4711       analyzeFlowBlockNode(md, nametable, isn.getFalseBlock(), newImplicitTupleSet);
4712     }
4713
4714   }
4715
4716   private void analyzeFlowDeclarationNode(MethodDescriptor md, SymbolTable nametable,
4717       DeclarationNode dn, NodeTupleSet implicitFlowTupleSet) {
4718
4719     VarDescriptor vd = dn.getVarDescriptor();
4720     mapDescToDefinitionLine.put(vd, dn.getNumLine());
4721     NTuple<Descriptor> tupleLHS = new NTuple<Descriptor>();
4722     tupleLHS.add(vd);
4723     FlowNode fn = getFlowGraph(md).createNewFlowNode(tupleLHS);
4724     fn.setDeclarationNode();
4725
4726     if (dn.getExpression() != null) {
4727       System.out.println("-analyzeFlowDeclarationNode=" + dn.printNode(0));
4728
4729       NodeTupleSet nodeSetRHS = new NodeTupleSet();
4730       analyzeFlowExpressionNode(md, nametable, dn.getExpression(), nodeSetRHS, null,
4731           implicitFlowTupleSet, false);
4732
4733       // creates edges from RHS to LHS
4734       NTuple<Descriptor> interTuple = null;
4735       if (needToGenerateInterLoc(nodeSetRHS)) {
4736         System.out.println("3");
4737         interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
4738       }
4739
4740       for (Iterator<NTuple<Descriptor>> iter = nodeSetRHS.iterator(); iter.hasNext();) {
4741         NTuple<Descriptor> fromTuple = iter.next();
4742         System.out.println("fromTuple=" + fromTuple + "  interTuple=" + interTuple + " tupleLSH="
4743             + tupleLHS);
4744         addFlowGraphEdge(md, fromTuple, interTuple, tupleLHS);
4745       }
4746
4747       // creates edges from implicitFlowTupleSet to LHS
4748       for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
4749         NTuple<Descriptor> implicitTuple = iter.next();
4750         addFlowGraphEdge(md, implicitTuple, tupleLHS);
4751       }
4752
4753       GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
4754       for (Iterator<NTuple<Location>> iterator = nodeSetRHS.globalIterator(); iterator.hasNext();) {
4755         NTuple<Location> calleeReturnLocTuple = iterator.next();
4756
4757         globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, translateToLocTuple(md, tupleLHS));
4758       }
4759
4760       for (Iterator<NTuple<Location>> iterator = implicitFlowTupleSet.globalIterator(); iterator
4761           .hasNext();) {
4762         NTuple<Location> implicitGlobalTuple = iterator.next();
4763
4764         globalFlowGraph.addValueFlowEdge(implicitGlobalTuple, translateToLocTuple(md, tupleLHS));
4765       }
4766
4767       System.out.println("-nodeSetRHS=" + nodeSetRHS);
4768       System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet);
4769
4770     }
4771
4772   }
4773
4774   private void analyzeBlockExpressionNode(MethodDescriptor md, SymbolTable nametable,
4775       BlockExpressionNode ben, NodeTupleSet implicitFlowTupleSet) {
4776     analyzeFlowExpressionNode(md, nametable, ben.getExpression(), null, null, implicitFlowTupleSet,
4777         false);
4778   }
4779
4780   private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
4781       ExpressionNode en, NodeTupleSet nodeSet, boolean isLHS) {
4782     return analyzeFlowExpressionNode(md, nametable, en, nodeSet, null, new NodeTupleSet(), isLHS);
4783   }
4784
4785   private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
4786       ExpressionNode en, NodeTupleSet nodeSet, NTuple<Descriptor> base,
4787       NodeTupleSet implicitFlowTupleSet, boolean isLHS) {
4788
4789     // System.out.println("en=" + en.printNode(0) + "   class=" + en.getClass());
4790
4791     // note that expression node can create more than one flow node
4792     // nodeSet contains of flow nodes
4793     // base is always assigned to null except the case of a name node!
4794     NTuple<Descriptor> flowTuple;
4795     switch (en.kind()) {
4796     case Kind.AssignmentNode:
4797       analyzeFlowAssignmentNode(md, nametable, (AssignmentNode) en, nodeSet, base,
4798           implicitFlowTupleSet);
4799       break;
4800
4801     case Kind.FieldAccessNode:
4802       flowTuple =
4803           analyzeFlowFieldAccessNode(md, nametable, (FieldAccessNode) en, nodeSet, base,
4804               implicitFlowTupleSet, isLHS);
4805       if (flowTuple != null) {
4806         nodeSet.addTuple(flowTuple);
4807       }
4808       return flowTuple;
4809
4810     case Kind.NameNode:
4811       NodeTupleSet nameNodeSet = new NodeTupleSet();
4812       flowTuple =
4813           analyzeFlowNameNode(md, nametable, (NameNode) en, nameNodeSet, base, implicitFlowTupleSet);
4814       if (flowTuple != null) {
4815         nodeSet.addTuple(flowTuple);
4816       }
4817       return flowTuple;
4818
4819     case Kind.OpNode:
4820       analyzeFlowOpNode(md, nametable, (OpNode) en, nodeSet, implicitFlowTupleSet);
4821       break;
4822
4823     case Kind.CreateObjectNode:
4824       analyzeCreateObjectNode(md, nametable, (CreateObjectNode) en);
4825       break;
4826
4827     case Kind.ArrayAccessNode:
4828       analyzeFlowArrayAccessNode(md, nametable, (ArrayAccessNode) en, nodeSet, isLHS);
4829       break;
4830
4831     case Kind.LiteralNode:
4832       analyzeFlowLiteralNode(md, nametable, (LiteralNode) en, nodeSet);
4833       break;
4834
4835     case Kind.MethodInvokeNode:
4836       analyzeFlowMethodInvokeNode(md, nametable, (MethodInvokeNode) en, nodeSet,
4837           implicitFlowTupleSet);
4838       break;
4839
4840     case Kind.TertiaryNode:
4841       analyzeFlowTertiaryNode(md, nametable, (TertiaryNode) en, nodeSet, implicitFlowTupleSet);
4842       break;
4843
4844     case Kind.CastNode:
4845       analyzeFlowCastNode(md, nametable, (CastNode) en, nodeSet, base, implicitFlowTupleSet);
4846       break;
4847     // case Kind.InstanceOfNode:
4848     // checkInstanceOfNode(md, nametable, (InstanceOfNode) en, td);
4849     // return null;
4850
4851     // case Kind.ArrayInitializerNode:
4852     // checkArrayInitializerNode(md, nametable, (ArrayInitializerNode) en,
4853     // td);
4854     // return null;
4855
4856     // case Kind.ClassTypeNode:
4857     // checkClassTypeNode(md, nametable, (ClassTypeNode) en, td);
4858     // return null;
4859
4860     // case Kind.OffsetNode:
4861     // checkOffsetNode(md, nametable, (OffsetNode)en, td);
4862     // return null;
4863
4864     }
4865
4866     return null;
4867
4868   }
4869
4870   private void analyzeFlowCastNode(MethodDescriptor md, SymbolTable nametable, CastNode cn,
4871       NodeTupleSet nodeSet, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
4872
4873     analyzeFlowExpressionNode(md, nametable, cn.getExpression(), nodeSet, base,
4874         implicitFlowTupleSet, false);
4875
4876   }
4877
4878   private void analyzeFlowTertiaryNode(MethodDescriptor md, SymbolTable nametable, TertiaryNode tn,
4879       NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
4880
4881     // System.out.println("analyzeFlowTertiaryNode=" + tn.printNode(0));
4882
4883     NodeTupleSet tertiaryTupleNode = new NodeTupleSet();
4884     analyzeFlowExpressionNode(md, nametable, tn.getCond(), tertiaryTupleNode, null,
4885         implicitFlowTupleSet, false);
4886
4887     NodeTupleSet newImplicitTupleSet = new NodeTupleSet();
4888     newImplicitTupleSet.addTupleSet(implicitFlowTupleSet);
4889     newImplicitTupleSet.addTupleSet(tertiaryTupleNode);
4890
4891     // System.out.println("$$$GGGcondTupleNode=" + tertiaryTupleNode.getGlobalLocTupleSet());
4892     // System.out.println("-tertiaryTupleNode=" + tertiaryTupleNode);
4893     // System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet);
4894     // System.out.println("-newImplicitTupleSet=" + newImplicitTupleSet);
4895
4896     if (needToGenerateInterLoc(newImplicitTupleSet)) {
4897       System.out.println("15");
4898       // need to create an intermediate node for the GLB of conditional locations & implicit flows
4899       NTuple<Descriptor> interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
4900       for (Iterator<NTuple<Descriptor>> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) {
4901         NTuple<Descriptor> tuple = idxIter.next();
4902         addFlowGraphEdge(md, tuple, interTuple);
4903       }
4904       newImplicitTupleSet.clear();
4905       newImplicitTupleSet.addTuple(interTuple);
4906     }
4907
4908     newImplicitTupleSet.addGlobalFlowTupleSet(tertiaryTupleNode.getGlobalLocTupleSet());
4909
4910     System.out.println("---------newImplicitTupleSet=" + newImplicitTupleSet);
4911     // add edges from tertiaryTupleNode to all nodes of conditional nodes
4912     // tertiaryTupleNode.addTupleSet(implicitFlowTupleSet);
4913     analyzeFlowExpressionNode(md, nametable, tn.getTrueExpr(), tertiaryTupleNode, null,
4914         newImplicitTupleSet, false);
4915
4916     analyzeFlowExpressionNode(md, nametable, tn.getFalseExpr(), tertiaryTupleNode, null,
4917         newImplicitTupleSet, false);
4918
4919     nodeSet.addGlobalFlowTupleSet(tertiaryTupleNode.getGlobalLocTupleSet());
4920     nodeSet.addTupleSet(tertiaryTupleNode);
4921
4922     System.out.println("#tertiary node set=" + nodeSet);
4923   }
4924
4925   private void addMapCallerMethodDescToMethodInvokeNodeSet(MethodDescriptor caller,
4926       MethodInvokeNode min) {
4927     Set<MethodInvokeNode> set = mapMethodDescriptorToMethodInvokeNodeSet.get(caller);
4928     if (set == null) {
4929       set = new HashSet<MethodInvokeNode>();
4930       mapMethodDescriptorToMethodInvokeNodeSet.put(caller, set);
4931     }
4932     set.add(min);
4933   }
4934
4935   private void addParamNodeFlowingToReturnValue(MethodDescriptor md, FlowNode fn) {
4936
4937     if (!mapMethodDescToParamNodeFlowsToReturnValue.containsKey(md)) {
4938       mapMethodDescToParamNodeFlowsToReturnValue.put(md, new HashSet<FlowNode>());
4939     }
4940     mapMethodDescToParamNodeFlowsToReturnValue.get(md).add(fn);
4941   }
4942
4943   private Set<FlowNode> getParamNodeFlowingToReturnValue(MethodDescriptor md) {
4944
4945     if (!mapMethodDescToParamNodeFlowsToReturnValue.containsKey(md)) {
4946       mapMethodDescToParamNodeFlowsToReturnValue.put(md, new HashSet<FlowNode>());
4947     }
4948
4949     return mapMethodDescToParamNodeFlowsToReturnValue.get(md);
4950   }
4951
4952   private Set<NTuple<Location>> getPCLocTupleSet(MethodInvokeNode min) {
4953     if (!mapMethodInvokeNodeToPCLocTupleSet.containsKey(min)) {
4954       mapMethodInvokeNodeToPCLocTupleSet.put(min, new HashSet<NTuple<Location>>());
4955     }
4956     return mapMethodInvokeNodeToPCLocTupleSet.get(min);
4957   }
4958
4959   private void analyzeFlowMethodInvokeNode(MethodDescriptor mdCaller, SymbolTable nametable,
4960       MethodInvokeNode min, NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
4961
4962     System.out.println("analyzeFlowMethodInvokeNode=" + min.printNode(0));
4963
4964     if (!toanalyze_methodDescList.contains(min.getMethod())) {
4965       return;
4966     }
4967
4968     addMapMethodDescToMethodInvokeNodeSet(min);
4969
4970     Set<NTuple<Location>> pcLocTupleSet = getPCLocTupleSet(min);
4971     for (Iterator iterator = implicitFlowTupleSet.iterator(); iterator.hasNext();) {
4972       NTuple<Descriptor> pcDescTuple = (NTuple<Descriptor>) iterator.next();
4973       if (!pcDescTuple.get(0).equals(LITERALDESC)) {
4974         // here we don't need to add the literal value as a PC location
4975         pcLocTupleSet.add(translateToLocTuple(mdCaller, pcDescTuple));
4976       }
4977     }
4978
4979     mapMethodInvokeNodeToArgIdxMap.put(min, new HashMap<Integer, NTuple<Descriptor>>());
4980
4981     if (nodeSet == null) {
4982       nodeSet = new NodeTupleSet();
4983     }
4984
4985     MethodDescriptor mdCallee = min.getMethod();
4986
4987     NameDescriptor baseName = min.getBaseName();
4988     boolean isSystemout = false;
4989     if (baseName != null) {
4990       isSystemout = baseName.getSymbol().equals("System.out");
4991     }
4992
4993     if (!ssjava.isSSJavaUtil(mdCallee.getClassDesc()) && !ssjava.isTrustMethod(mdCallee)
4994         && !isSystemout) {
4995
4996       addMapCallerMethodDescToMethodInvokeNodeSet(mdCaller, min);
4997
4998       FlowGraph calleeFlowGraph = getFlowGraph(mdCallee);
4999       System.out.println("mdCallee=" + mdCallee + " calleeFlowGraph=" + calleeFlowGraph);
5000       Set<FlowNode> calleeReturnSet = calleeFlowGraph.getReturnNodeSet();
5001
5002       System.out.println("---calleeReturnSet=" + calleeReturnSet);
5003
5004       NodeTupleSet tupleSet = new NodeTupleSet();
5005
5006       if (min.getExpression() != null) {
5007
5008         NodeTupleSet baseNodeSet = new NodeTupleSet();
5009         analyzeFlowExpressionNode(mdCaller, nametable, min.getExpression(), baseNodeSet, null,
5010             implicitFlowTupleSet, false);
5011         System.out.println("baseNodeSet=" + baseNodeSet);
5012
5013         assert (baseNodeSet.size() == 1);
5014         NTuple<Descriptor> baseTuple = baseNodeSet.iterator().next();
5015         if (baseTuple.get(0) instanceof InterDescriptor) {
5016           if (baseTuple.size() > 1) {
5017             throw new Error();
5018           }
5019           FlowNode interNode = getFlowGraph(mdCaller).getFlowNode(baseTuple);
5020           baseTuple = translateBaseTuple(interNode, baseTuple);
5021         }
5022         mapMethodInvokeNodeToBaseTuple.put(min, baseTuple);
5023
5024         if (!min.getMethod().isStatic()) {
5025           addArgIdxMap(min, 0, baseTuple);
5026
5027           for (Iterator iterator = calleeReturnSet.iterator(); iterator.hasNext();) {
5028             FlowNode returnNode = (FlowNode) iterator.next();
5029             NTuple<Descriptor> returnDescTuple = returnNode.getDescTuple();
5030             if (returnDescTuple.startsWith(mdCallee.getThis())) {
5031               // the location type of the return value is started with 'this'
5032               // reference
5033               NTuple<Descriptor> inFlowTuple = new NTuple<Descriptor>(baseTuple.getList());
5034
5035               if (inFlowTuple.get(0) instanceof InterDescriptor) {
5036                 // min.getExpression()
5037               } else {
5038
5039               }
5040
5041               inFlowTuple.addAll(returnDescTuple.subList(1, returnDescTuple.size()));
5042               // nodeSet.addTuple(inFlowTuple);
5043               System.out.println("1CREATE A NEW TUPLE=" + inFlowTuple + "  from="
5044                   + mdCallee.getThis());
5045               // tupleSet.addTuple(inFlowTuple);
5046               tupleSet.addTuple(baseTuple);
5047             } else {
5048               // TODO
5049               System.out.println("returnNode=" + returnNode);
5050               Set<FlowNode> inFlowSet = calleeFlowGraph.getIncomingFlowNodeSet(returnNode);
5051               // System.out.println("inFlowSet=" + inFlowSet + "   from retrunNode=" + returnNode);
5052               for (Iterator iterator2 = inFlowSet.iterator(); iterator2.hasNext();) {
5053                 FlowNode inFlowNode = (FlowNode) iterator2.next();
5054                 if (inFlowNode.getDescTuple().startsWith(mdCallee.getThis())) {
5055                   // nodeSet.addTupleSet(baseNodeSet);
5056                   System.out.println("2CREATE A NEW TUPLE=" + baseNodeSet + "  from="
5057                       + mdCallee.getThis());
5058                   tupleSet.addTupleSet(baseNodeSet);
5059                 }
5060               }
5061             }
5062           }
5063         }
5064
5065       }
5066       // analyze parameter flows
5067
5068       if (min.numArgs() > 0) {
5069
5070         int offset;
5071         if (min.getMethod().isStatic()) {
5072           offset = 0;
5073         } else {
5074           offset = 1;
5075         }
5076
5077         for (int i = 0; i < min.numArgs(); i++) {
5078           ExpressionNode en = min.getArg(i);
5079           int idx = i + offset;
5080           NodeTupleSet argTupleSet = new NodeTupleSet();
5081           analyzeFlowExpressionNode(mdCaller, nametable, en, argTupleSet, false);
5082           // if argument is liternal node, argTuple is set to NULL
5083           System.out.println("---arg idx=" + idx + "   argTupleSet=" + argTupleSet);
5084           NTuple<Descriptor> argTuple = generateArgTuple(mdCaller, argTupleSet);
5085
5086           // if an argument is literal value,
5087           // we need to create an itermediate node so that we could assign a composite location to
5088           // that node if needed
5089           if (argTuple.size() > 0
5090               && (argTuple.get(0).equals(GLOBALDESC) || argTuple.get(0).equals(LITERALDESC))) {
5091             /*
5092              * System.out.println("***GLOBAL ARG TUPLE CASE=" + argTuple); System.out.println("8");
5093              *
5094              * NTuple<Descriptor> interTuple =
5095              * getFlowGraph(mdCaller).createIntermediateNode().getDescTuple(); ((InterDescriptor)
5096              * interTuple.get(0)).setMethodArgIdxPair(min, idx); addFlowGraphEdge(mdCaller,
5097              * argTuple, interTuple); argTuple = interTuple; addArgIdxMap(min, idx, argTuple);
5098              * System.out.println("new min mapping i=" + idx + "  ->" + argTuple);
5099              */
5100             argTuple = new NTuple<Descriptor>();
5101           }
5102
5103           addArgIdxMap(min, idx, argTuple);
5104
5105           FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx);
5106
5107           // check whether a param node in the callee graph has incoming flows
5108           // if it has incoming flows, the corresponding arg should be lower than the current PC
5109           // Descriptor prefix = paramNode.getDescTuple().get(0);
5110           // if (calleeFlowGraph.getIncomingNodeSetByPrefix(prefix).size() > 0) {
5111           // for (Iterator<NTuple<Descriptor>> iterator = implicitFlowTupleSet.iterator(); iterator
5112           // .hasNext();) {
5113           // NTuple<Descriptor> pcTuple = iterator.next();
5114           // System.out.println("add edge pcTuple =" + pcTuple + " -> " + argTuple);
5115           // addFlowGraphEdge(md, pcTuple, argTuple);
5116           // }
5117           // }
5118
5119           System.out.println("paramNode=" + paramNode + "  calleeReturnSet=" + calleeReturnSet);
5120           if (hasInFlowTo(calleeFlowGraph, paramNode, calleeReturnSet)
5121               || mdCallee.getModifiers().isNative()) {
5122             addParamNodeFlowingToReturnValue(mdCallee, paramNode);
5123             // nodeSet.addTupleSet(argTupleSet);
5124             System.out.println("3CREATE A NEW TUPLE=" + argTupleSet + "  from=" + paramNode);
5125             tupleSet.addTupleSet(argTupleSet);
5126           }
5127         }
5128
5129       }
5130
5131       if (mdCallee.getReturnType() != null && !mdCallee.getReturnType().isVoid()) {
5132         FlowReturnNode returnHolderNode = getFlowGraph(mdCaller).createReturnNode(min);
5133
5134         if (needToGenerateInterLoc(tupleSet)) {
5135           System.out.println("20");
5136           FlowGraph fg = getFlowGraph(mdCaller);
5137           FlowNode interNode = fg.createIntermediateNode();
5138           interNode.setFormHolder(true);
5139
5140           NTuple<Descriptor> interTuple = interNode.getDescTuple();
5141
5142           for (Iterator iterator = tupleSet.iterator(); iterator.hasNext();) {
5143             NTuple<Descriptor> tuple = (NTuple<Descriptor>) iterator.next();
5144
5145             Set<NTuple<Descriptor>> addSet = new HashSet<NTuple<Descriptor>>();
5146             FlowNode node = fg.getFlowNode(tuple);
5147             if (node instanceof FlowReturnNode) {
5148               addSet.addAll(fg.getReturnTupleSet(((FlowReturnNode) node).getReturnTupleSet()));
5149             } else {
5150               addSet.add(tuple);
5151             }
5152             for (Iterator iterator2 = addSet.iterator(); iterator2.hasNext();) {
5153               NTuple<Descriptor> higher = (NTuple<Descriptor>) iterator2.next();
5154               addFlowGraphEdge(mdCaller, higher, interTuple);
5155             }
5156           }
5157
5158           returnHolderNode.addTuple(interTuple);
5159
5160           nodeSet.addTuple(interTuple);
5161           System.out.println("ADD TUPLESET=" + interTuple + " to returnnode=" + returnHolderNode);
5162
5163         } else {
5164           returnHolderNode.addTupleSet(tupleSet);
5165           System.out.println("ADD TUPLESET=" + tupleSet + " to returnnode=" + returnHolderNode);
5166         }
5167         // setNode.addTupleSet(tupleSet);
5168         // NodeTupleSet setFromReturnNode=new NodeTupleSet();
5169         // setFromReturnNode.addTuple(tuple);
5170
5171         NodeTupleSet holderTupleSet =
5172             getNodeTupleSetFromReturnNode(getFlowGraph(mdCaller), returnHolderNode);
5173
5174         System.out.println("HOLDER TUPLe SET=" + holderTupleSet);
5175         nodeSet.addTupleSet(holderTupleSet);
5176
5177         nodeSet.addTuple(returnHolderNode.getDescTuple());
5178       }
5179
5180       // propagateFlowsFromCallee(min, md, min.getMethod());
5181
5182       // when generating the global flow graph,
5183       // we need to add ordering relations from the set of callee return loc tuple to LHS of the
5184       // caller assignment
5185       for (Iterator iterator = calleeReturnSet.iterator(); iterator.hasNext();) {
5186         FlowNode calleeReturnNode = (FlowNode) iterator.next();
5187         NTuple<Location> calleeReturnLocTuple =
5188             translateToLocTuple(mdCallee, calleeReturnNode.getDescTuple());
5189         System.out.println("calleeReturnLocTuple=" + calleeReturnLocTuple);
5190         NTuple<Location> transaltedToCaller =
5191             translateToCallerLocTuple(min, mdCallee, mdCaller, calleeReturnLocTuple);
5192         // System.out.println("translateToCallerLocTuple="
5193         // + translateToCallerLocTuple(min, mdCallee, mdCaller, calleeReturnLocTuple));
5194         if (transaltedToCaller.size() > 0) {
5195           nodeSet.addGlobalFlowTuple(translateToCallerLocTuple(min, mdCallee, mdCaller,
5196               calleeReturnLocTuple));
5197         }
5198       }
5199
5200       System.out.println("min nodeSet=" + nodeSet);
5201
5202     }
5203
5204   }
5205
5206   private NodeTupleSet getNodeTupleSetFromReturnNode(FlowGraph fg, FlowReturnNode node) {
5207     NodeTupleSet nts = new NodeTupleSet();
5208
5209     Set<NTuple<Descriptor>> returnSet = node.getReturnTupleSet();
5210
5211     for (Iterator iterator = returnSet.iterator(); iterator.hasNext();) {
5212       NTuple<Descriptor> tuple = (NTuple<Descriptor>) iterator.next();
5213       FlowNode flowNode = fg.getFlowNode(tuple);
5214       if (flowNode instanceof FlowReturnNode) {
5215         returnSet.addAll(recurGetNode(fg, (FlowReturnNode) flowNode));
5216       } else {
5217         returnSet.add(tuple);
5218       }
5219     }
5220
5221     for (Iterator iterator = returnSet.iterator(); iterator.hasNext();) {
5222       NTuple<Descriptor> nTuple = (NTuple<Descriptor>) iterator.next();
5223       nts.addTuple(nTuple);
5224     }
5225
5226     return nts;
5227
5228   }
5229
5230   private Set<NTuple<Descriptor>> recurGetNode(FlowGraph fg, FlowReturnNode rnode) {
5231
5232     Set<NTuple<Descriptor>> tupleSet = new HashSet<NTuple<Descriptor>>();
5233
5234     Set<NTuple<Descriptor>> returnSet = rnode.getReturnTupleSet();
5235     for (Iterator iterator = returnSet.iterator(); iterator.hasNext();) {
5236       NTuple<Descriptor> tuple = (NTuple<Descriptor>) iterator.next();
5237       FlowNode flowNode = fg.getFlowNode(tuple);
5238       if (flowNode instanceof FlowReturnNode) {
5239         tupleSet.addAll(recurGetNode(fg, (FlowReturnNode) flowNode));
5240       }
5241       tupleSet.add(tuple);
5242     }
5243
5244     return tupleSet;
5245   }
5246
5247   private NTuple<Descriptor> generateArgTuple(MethodDescriptor mdCaller, NodeTupleSet argTupleSet) {
5248
5249     int size = 0;
5250
5251     // if argTupleSet is empty, it comes from the top location
5252     if (argTupleSet.size() == 0) {
5253       NTuple<Descriptor> descTuple = new NTuple<Descriptor>();
5254       descTuple.add(LITERALDESC);
5255       return descTuple;
5256     }
5257
5258     Set<NTuple<Descriptor>> argTupleSetNonLiteral = new HashSet<NTuple<Descriptor>>();
5259
5260     for (Iterator<NTuple<Descriptor>> iter = argTupleSet.iterator(); iter.hasNext();) {
5261       NTuple<Descriptor> descTuple = iter.next();
5262       if (!descTuple.get(0).equals(LITERALDESC)) {
5263         argTupleSetNonLiteral.add(descTuple);
5264       }
5265     }
5266
5267     if (argTupleSetNonLiteral.size() > 1) {
5268       System.out.println("11");
5269
5270       NTuple<Descriptor> interTuple =
5271           getFlowGraph(mdCaller).createIntermediateNode().getDescTuple();
5272       for (Iterator<NTuple<Descriptor>> idxIter = argTupleSet.iterator(); idxIter.hasNext();) {
5273         NTuple<Descriptor> tuple = idxIter.next();
5274         addFlowGraphEdge(mdCaller, tuple, interTuple);
5275       }
5276       return interTuple;
5277     } else if (argTupleSetNonLiteral.size() == 1) {
5278       return argTupleSetNonLiteral.iterator().next();
5279     } else {
5280       return argTupleSet.iterator().next();
5281     }
5282
5283   }
5284
5285   private boolean hasInFlowTo(FlowGraph fg, FlowNode inNode, Set<FlowNode> nodeSet) {
5286     // return true if inNode has in-flows to nodeSet
5287
5288     if (nodeSet.contains(inNode)) {
5289       // in this case, the method directly returns a parameter variable.
5290       return true;
5291     }
5292     // Set<FlowNode> reachableSet = fg.getReachFlowNodeSetFrom(inNode);
5293     Set<FlowNode> reachableSet = fg.getReachableSetFrom(inNode.getDescTuple());
5294     // System.out.println("inNode=" + inNode + "  reachalbeSet=" + reachableSet);
5295
5296     for (Iterator iterator = reachableSet.iterator(); iterator.hasNext();) {
5297       FlowNode fn = (FlowNode) iterator.next();
5298       if (nodeSet.contains(fn)) {
5299         return true;
5300       }
5301     }
5302     return false;
5303   }
5304
5305   private NTuple<Descriptor> getNodeTupleByArgIdx(MethodInvokeNode min, int idx) {
5306     return mapMethodInvokeNodeToArgIdxMap.get(min).get(new Integer(idx));
5307   }
5308
5309   private void addArgIdxMap(MethodInvokeNode min, int idx, NTuple<Descriptor> argTuple /*
5310                                                                                         * NodeTupleSet
5311                                                                                         * tupleSet
5312                                                                                         */) {
5313     Map<Integer, NTuple<Descriptor>> mapIdxToTuple = mapMethodInvokeNodeToArgIdxMap.get(min);
5314     if (mapIdxToTuple == null) {
5315       mapIdxToTuple = new HashMap<Integer, NTuple<Descriptor>>();
5316       mapMethodInvokeNodeToArgIdxMap.put(min, mapIdxToTuple);
5317     }
5318     mapIdxToTuple.put(new Integer(idx), argTuple);
5319   }
5320
5321   private void analyzeFlowLiteralNode(MethodDescriptor md, SymbolTable nametable, LiteralNode en,
5322       NodeTupleSet nodeSet) {
5323     NTuple<Descriptor> tuple = new NTuple<Descriptor>();
5324     tuple.add(LITERALDESC);
5325     nodeSet.addTuple(tuple);
5326   }
5327
5328   private void analyzeFlowArrayAccessNode(MethodDescriptor md, SymbolTable nametable,
5329       ArrayAccessNode aan, NodeTupleSet nodeSet, boolean isLHS) {
5330
5331     System.out.println("analyzeFlowArrayAccessNode aan=" + aan.printNode(0));
5332     String currentArrayAccessNodeExpStr = aan.printNode(0);
5333     arrayAccessNodeStack.push(aan.printNode(0));
5334
5335     NodeTupleSet expNodeTupleSet = new NodeTupleSet();
5336     NTuple<Descriptor> base =
5337         analyzeFlowExpressionNode(md, nametable, aan.getExpression(), expNodeTupleSet, isLHS);
5338     System.out.println("-base=" + base);
5339
5340     nodeSet.setMethodInvokeBaseDescTuple(base);
5341     NodeTupleSet idxNodeTupleSet = new NodeTupleSet();
5342     analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, isLHS);
5343
5344     arrayAccessNodeStack.pop();
5345
5346     if (isLHS) {
5347       // need to create an edge from idx to array
5348       for (Iterator<NTuple<Descriptor>> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) {
5349         NTuple<Descriptor> idxTuple = idxIter.next();
5350         for (Iterator<NTuple<Descriptor>> arrIter = expNodeTupleSet.iterator(); arrIter.hasNext();) {
5351           NTuple<Descriptor> arrTuple = arrIter.next();
5352           getFlowGraph(md).addValueFlowEdge(idxTuple, arrTuple);
5353         }
5354       }
5355
5356       GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
5357       for (Iterator<NTuple<Location>> iterator = idxNodeTupleSet.globalIterator(); iterator
5358           .hasNext();) {
5359         NTuple<Location> calleeReturnLocTuple = iterator.next();
5360         for (Iterator<NTuple<Descriptor>> arrIter = expNodeTupleSet.iterator(); arrIter.hasNext();) {
5361           NTuple<Descriptor> arrTuple = arrIter.next();
5362
5363           globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, translateToLocTuple(md, arrTuple));
5364         }
5365       }
5366
5367       nodeSet.addTupleSet(expNodeTupleSet);
5368     } else {
5369
5370       NodeTupleSet nodeSetArrayAccessExp = new NodeTupleSet();
5371
5372       nodeSetArrayAccessExp.addTupleSet(expNodeTupleSet);
5373       nodeSetArrayAccessExp.addTupleSet(idxNodeTupleSet);
5374
5375       if (arrayAccessNodeStack.isEmpty()
5376           || !arrayAccessNodeStack.peek().startsWith(currentArrayAccessNodeExpStr)) {
5377
5378         if (needToGenerateInterLoc(nodeSetArrayAccessExp)) {
5379           System.out.println("1");
5380           FlowNode interNode = getFlowGraph(md).createIntermediateNode();
5381           NTuple<Descriptor> interTuple = interNode.getDescTuple();
5382
5383           for (Iterator<NTuple<Descriptor>> iter = nodeSetArrayAccessExp.iterator(); iter.hasNext();) {
5384             NTuple<Descriptor> higherTuple = iter.next();
5385             addFlowGraphEdge(md, higherTuple, interTuple);
5386           }
5387           nodeSetArrayAccessExp.clear();
5388           nodeSetArrayAccessExp.addTuple(interTuple);
5389           FlowGraph fg = getFlowGraph(md);
5390
5391           System.out.println("base=" + base);
5392           if (base != null) {
5393             fg.addMapInterLocNodeToEnclosingDescriptor(interTuple.get(0),
5394                 getClassTypeDescriptor(base.get(base.size() - 1)));
5395             interNode.setBaseTuple(base);
5396           }
5397         }
5398       }
5399
5400       nodeSet.addGlobalFlowTupleSet(idxNodeTupleSet.getGlobalLocTupleSet());
5401       nodeSet.addTupleSet(nodeSetArrayAccessExp);
5402
5403     }
5404
5405   }
5406
5407   private void analyzeCreateObjectNode(MethodDescriptor md, SymbolTable nametable,
5408       CreateObjectNode en) {
5409     // TODO Auto-generated method stub
5410
5411   }
5412
5413   private void analyzeFlowOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on,
5414       NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
5415
5416     NodeTupleSet leftOpSet = new NodeTupleSet();
5417     NodeTupleSet rightOpSet = new NodeTupleSet();
5418
5419     System.out.println("analyzeFlowOpNode=" + on.printNode(0));
5420
5421     // left operand
5422     analyzeFlowExpressionNode(md, nametable, on.getLeft(), leftOpSet, null, implicitFlowTupleSet,
5423         false);
5424     System.out.println("--leftOpSet=" + leftOpSet);
5425
5426     if (on.getRight() != null) {
5427       // right operand
5428       analyzeFlowExpressionNode(md, nametable, on.getRight(), rightOpSet, null,
5429           implicitFlowTupleSet, false);
5430     }
5431     System.out.println("--rightOpSet=" + rightOpSet);
5432
5433     Operation op = on.getOp();
5434
5435     switch (op.getOp()) {
5436
5437     case Operation.UNARYPLUS:
5438     case Operation.UNARYMINUS:
5439     case Operation.LOGIC_NOT:
5440       // single operand
5441       nodeSet.addTupleSet(leftOpSet);
5442       break;
5443
5444     case Operation.LOGIC_OR:
5445     case Operation.LOGIC_AND:
5446     case Operation.COMP:
5447     case Operation.BIT_OR:
5448     case Operation.BIT_XOR:
5449     case Operation.BIT_AND:
5450     case Operation.ISAVAILABLE:
5451     case Operation.EQUAL:
5452     case Operation.NOTEQUAL:
5453     case Operation.LT:
5454     case Operation.GT:
5455     case Operation.LTE:
5456     case Operation.GTE:
5457     case Operation.ADD:
5458     case Operation.SUB:
5459     case Operation.MULT:
5460     case Operation.DIV:
5461     case Operation.MOD:
5462     case Operation.LEFTSHIFT:
5463     case Operation.RIGHTSHIFT:
5464     case Operation.URIGHTSHIFT:
5465
5466       // there are two operands
5467       nodeSet.addTupleSet(leftOpSet);
5468       nodeSet.addTupleSet(rightOpSet);
5469
5470       nodeSet.addGlobalFlowTupleSet(leftOpSet.getGlobalLocTupleSet());
5471       nodeSet.addGlobalFlowTupleSet(rightOpSet.getGlobalLocTupleSet());
5472
5473       break;
5474
5475     default:
5476       throw new Error(op.toString());
5477     }
5478
5479   }
5480
5481   private NTuple<Descriptor> analyzeFlowNameNode(MethodDescriptor md, SymbolTable nametable,
5482       NameNode nn, NodeTupleSet nodeSet, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
5483
5484     if (base == null) {
5485       base = new NTuple<Descriptor>();
5486     }
5487
5488     NameDescriptor nd = nn.getName();
5489
5490     if (nd.getBase() != null) {
5491       base =
5492           analyzeFlowExpressionNode(md, nametable, nn.getExpression(), nodeSet, base,
5493               implicitFlowTupleSet, false);
5494       if (base == null) {
5495         // base node has the top location
5496         return base;
5497       }
5498     } else {
5499       String varname = nd.toString();
5500       if (varname.equals("this")) {
5501         // 'this' itself!
5502         base.add(md.getThis());
5503         return base;
5504       }
5505
5506       Descriptor d = (Descriptor) nametable.get(varname);
5507
5508       if (d instanceof VarDescriptor) {
5509         VarDescriptor vd = (VarDescriptor) d;
5510         base.add(vd);
5511       } else if (d instanceof FieldDescriptor) {
5512         // the type of field descriptor has a location!
5513         FieldDescriptor fd = (FieldDescriptor) d;
5514         if (fd.isStatic()) {
5515           if (fd.isFinal()) {
5516             // if it is 'static final', no need to have flow node for the TOP
5517             // location
5518             return null;
5519           } else {
5520             // if 'static', assign the default GLOBAL LOCATION to the first
5521             // element of the tuple
5522             base.add(GLOBALDESC);
5523           }
5524         } else {
5525           // the location of field access starts from this, followed by field
5526           // location
5527           base.add(md.getThis());
5528         }
5529
5530         base.add(fd);
5531       } else if (d == null) {
5532         // access static field
5533         base.add(GLOBALDESC);
5534         base.add(nn.getField());
5535         return base;
5536
5537         // FieldDescriptor fd = nn.getField();addFlowGraphEdge
5538         //
5539         // MethodLattice<String> localLattice = ssjava.getMethodLattice(md);
5540         // String globalLocId = localLattice.getGlobalLoc();
5541         // if (globalLocId == null) {
5542         // throw new
5543         // Error("Method lattice does not define global variable location at "
5544         // + generateErrorMessage(md.getClassDesc(), nn));
5545         // }
5546         // loc.addLocation(new Location(md, globalLocId));
5547         //
5548         // Location fieldLoc = (Location) fd.getType().getExtension();
5549         // loc.addLocation(fieldLoc);
5550         //
5551         // return loc;
5552
5553       }
5554     }
5555     getFlowGraph(md).createNewFlowNode(base);
5556
5557     return base;
5558
5559   }
5560
5561   private NTuple<Descriptor> analyzeFlowFieldAccessNode(MethodDescriptor md, SymbolTable nametable,
5562       FieldAccessNode fan, NodeTupleSet nodeSet, NTuple<Descriptor> base,
5563       NodeTupleSet implicitFlowTupleSet, boolean isLHS) {
5564     // System.out.println("analyzeFlowFieldAccessNode=" + fan.printNode(0));
5565
5566     String currentArrayAccessNodeExpStr = null;
5567     ExpressionNode left = fan.getExpression();
5568     TypeDescriptor ltd = left.getType();
5569     FieldDescriptor fd = fan.getField();
5570     ArrayAccessNode aan = null;
5571
5572     String varName = null;
5573     if (left.kind() == Kind.NameNode) {
5574       NameDescriptor nd = ((NameNode) left).getName();
5575       varName = nd.toString();
5576     }
5577
5578     if (ltd.isClassNameRef() || (varName != null && varName.equals("this"))) {
5579       // using a class name directly or access using this
5580       if (fd.isStatic() && fd.isFinal()) {
5581         return null;
5582       }
5583     }
5584
5585     NodeTupleSet idxNodeTupleSet = new NodeTupleSet();
5586
5587     boolean isArrayCase = false;
5588     if (left instanceof ArrayAccessNode) {
5589
5590       isArrayCase = true;
5591       aan = (ArrayAccessNode) left;
5592
5593       currentArrayAccessNodeExpStr = aan.printNode(0);
5594       arrayAccessNodeStack.push(currentArrayAccessNodeExpStr);
5595
5596       left = aan.getExpression();
5597       analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, base,
5598           implicitFlowTupleSet, isLHS);
5599
5600     }
5601     base =
5602         analyzeFlowExpressionNode(md, nametable, left, nodeSet, base, implicitFlowTupleSet, isLHS);
5603
5604     if (base == null) {
5605       // in this case, field is TOP location
5606       return null;
5607     } else {
5608
5609       NTuple<Descriptor> flowFieldTuple = new NTuple<Descriptor>(base.toList());
5610
5611       if (!left.getType().isPrimitive()) {
5612         if (!fd.getSymbol().equals("length")) {
5613           // array.length access, just have the location of the array
5614           flowFieldTuple.add(fd);
5615           nodeSet.removeTuple(base);
5616         }
5617       }
5618       getFlowGraph(md).createNewFlowNode(flowFieldTuple);
5619
5620       if (isLHS) {
5621         for (Iterator<NTuple<Descriptor>> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) {
5622           NTuple<Descriptor> idxTuple = idxIter.next();
5623           getFlowGraph(md).addValueFlowEdge(idxTuple, flowFieldTuple);
5624         }
5625
5626         GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
5627         for (Iterator<NTuple<Location>> iterator = idxNodeTupleSet.globalIterator(); iterator
5628             .hasNext();) {
5629           NTuple<Location> calleeReturnLocTuple = iterator.next();
5630
5631           globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple,
5632               translateToLocTuple(md, flowFieldTuple));
5633         }
5634
5635       } else {
5636         nodeSet.addTupleSet(idxNodeTupleSet);
5637
5638         // if it is the array case and not the LHS case
5639         if (isArrayCase) {
5640           arrayAccessNodeStack.pop();
5641
5642           if (arrayAccessNodeStack.isEmpty()
5643               || !arrayAccessNodeStack.peek().startsWith(currentArrayAccessNodeExpStr)) {
5644             NodeTupleSet nodeSetArrayAccessExp = new NodeTupleSet();
5645
5646             nodeSetArrayAccessExp.addTuple(flowFieldTuple);
5647             nodeSetArrayAccessExp.addTupleSet(idxNodeTupleSet);
5648             nodeSetArrayAccessExp.addTupleSet(nodeSet);
5649
5650             if (needToGenerateInterLoc(nodeSetArrayAccessExp)) {
5651               System.out.println("4");
5652               System.out.println("nodeSetArrayAccessExp=" + nodeSetArrayAccessExp);
5653               // System.out.println("idxNodeTupleSet.getGlobalLocTupleSet()="
5654               // + idxNodeTupleSet.getGlobalLocTupleSet());
5655
5656               NTuple<Descriptor> interTuple =
5657                   getFlowGraph(md).createIntermediateNode().getDescTuple();
5658
5659               for (Iterator<NTuple<Descriptor>> iter = nodeSetArrayAccessExp.iterator(); iter
5660                   .hasNext();) {
5661                 NTuple<Descriptor> higherTuple = iter.next();
5662                 addFlowGraphEdge(md, higherTuple, interTuple);
5663               }
5664
5665               FlowGraph fg = getFlowGraph(md);
5666               fg.addMapInterLocNodeToEnclosingDescriptor(interTuple.get(0),
5667                   getClassTypeDescriptor(base.get(base.size() - 1)));
5668
5669               nodeSet.clear();
5670               flowFieldTuple = interTuple;
5671             }
5672             nodeSet.addGlobalFlowTupleSet(idxNodeTupleSet.getGlobalLocTupleSet());
5673           }
5674
5675         }
5676
5677       }
5678       return flowFieldTuple;
5679     }
5680
5681   }
5682
5683   private void debug_printTreeNode(TreeNode tn) {
5684
5685     System.out.println("DEBUG: " + tn.printNode(0) + "                line#=" + tn.getNumLine());
5686
5687   }
5688
5689   private void analyzeFlowAssignmentNode(MethodDescriptor md, SymbolTable nametable,
5690       AssignmentNode an, NodeTupleSet nodeSet, NTuple<Descriptor> base,
5691       NodeTupleSet implicitFlowTupleSet) {
5692
5693     NodeTupleSet nodeSetRHS = new NodeTupleSet();
5694     NodeTupleSet nodeSetLHS = new NodeTupleSet();
5695
5696     boolean postinc = true;
5697     if (an.getOperation().getBaseOp() == null
5698         || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
5699             .getBaseOp().getOp() != Operation.POSTDEC)) {
5700       postinc = false;
5701     }
5702     // if LHS is array access node, need to capture value flows between an array
5703     // and its index value
5704     analyzeFlowExpressionNode(md, nametable, an.getDest(), nodeSetLHS, null, implicitFlowTupleSet,
5705         true);
5706
5707     if (!postinc) {
5708       // analyze value flows of rhs expression
5709       analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null, implicitFlowTupleSet,
5710           false);
5711
5712       System.out.println("-analyzeFlowAssignmentNode=" + an.printNode(0));
5713       System.out.println("-nodeSetLHS=" + nodeSetLHS);
5714       System.out.println("-nodeSetRHS=" + nodeSetRHS);
5715       System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet);
5716       // System.out.println("-");
5717
5718       if (an.getOperation().getOp() >= 2 && an.getOperation().getOp() <= 12) {
5719         // if assignment contains OP+EQ operator, creates edges from LHS to LHS
5720
5721         for (Iterator<NTuple<Descriptor>> iter = nodeSetLHS.iterator(); iter.hasNext();) {
5722           NTuple<Descriptor> fromTuple = iter.next();
5723           for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
5724             NTuple<Descriptor> toTuple = iter2.next();
5725             addFlowGraphEdge(md, fromTuple, toTuple);
5726           }
5727         }
5728       }
5729
5730       // creates edges from RHS to LHS
5731       NTuple<Descriptor> interTuple = null;
5732       if (needToGenerateInterLoc(nodeSetRHS)) {
5733         System.out.println("2");
5734         interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple();
5735       }
5736
5737       for (Iterator<NTuple<Descriptor>> iter = nodeSetRHS.iterator(); iter.hasNext();) {
5738         NTuple<Descriptor> fromTuple = iter.next();
5739         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
5740           NTuple<Descriptor> toTuple = iter2.next();
5741           addFlowGraphEdge(md, fromTuple, interTuple, toTuple);
5742         }
5743       }
5744
5745       // creates edges from implicitFlowTupleSet to LHS
5746       for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
5747         NTuple<Descriptor> fromTuple = iter.next();
5748         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
5749           NTuple<Descriptor> toTuple = iter2.next();
5750           addFlowGraphEdge(md, fromTuple, toTuple);
5751         }
5752       }
5753
5754       // create global flow edges if the callee gives return value flows to the caller
5755       GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
5756       for (Iterator<NTuple<Location>> iterator = nodeSetRHS.globalIterator(); iterator.hasNext();) {
5757         NTuple<Location> calleeReturnLocTuple = iterator.next();
5758         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
5759           NTuple<Descriptor> callerLHSTuple = iter2.next();
5760           System.out.println("$$$ GLOBAL FLOW ADD=" + calleeReturnLocTuple + " -> "
5761               + translateToLocTuple(md, callerLHSTuple));
5762
5763           globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple,
5764               translateToLocTuple(md, callerLHSTuple));
5765         }
5766       }
5767
5768       for (Iterator<NTuple<Location>> iterator = implicitFlowTupleSet.globalIterator(); iterator
5769           .hasNext();) {
5770         NTuple<Location> calleeReturnLocTuple = iterator.next();
5771         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
5772           NTuple<Descriptor> callerLHSTuple = iter2.next();
5773
5774           globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple,
5775               translateToLocTuple(md, callerLHSTuple));
5776           System.out.println("$$$ GLOBAL FLOW PCLOC ADD=" + calleeReturnLocTuple + " -> "
5777               + translateToLocTuple(md, callerLHSTuple));
5778         }
5779       }
5780
5781     } else {
5782       // postinc case
5783
5784       for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
5785         NTuple<Descriptor> tuple = iter2.next();
5786         addFlowGraphEdge(md, tuple, tuple);
5787       }
5788
5789       // creates edges from implicitFlowTupleSet to LHS
5790       for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
5791         NTuple<Descriptor> fromTuple = iter.next();
5792         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
5793           NTuple<Descriptor> toTuple = iter2.next();
5794           addFlowGraphEdge(md, fromTuple, toTuple);
5795         }
5796       }
5797
5798       GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md);
5799       for (Iterator<NTuple<Location>> iterator = implicitFlowTupleSet.globalIterator(); iterator
5800           .hasNext();) {
5801         NTuple<Location> calleeReturnLocTuple = iterator.next();
5802         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
5803           NTuple<Descriptor> callerLHSTuple = iter2.next();
5804           globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple,
5805               translateToLocTuple(md, callerLHSTuple));
5806           System.out.println("$$$ GLOBAL FLOW PC ADD=" + calleeReturnLocTuple + " -> "
5807               + translateToLocTuple(md, callerLHSTuple));
5808         }
5809       }
5810
5811     }
5812
5813     if (nodeSet != null) {
5814       nodeSet.addTupleSet(nodeSetLHS);
5815       nodeSet.addGlobalFlowTupleSet(nodeSetLHS.getGlobalLocTupleSet());
5816     }
5817   }
5818
5819   public FlowGraph getFlowGraph(MethodDescriptor md) {
5820     return mapMethodDescriptorToFlowGraph.get(md);
5821   }
5822
5823   private boolean addFlowGraphEdge(MethodDescriptor md, NTuple<Descriptor> from,
5824       NTuple<Descriptor> to) {
5825     FlowGraph graph = getFlowGraph(md);
5826     graph.addValueFlowEdge(from, to);
5827     return true;
5828   }
5829
5830   private void addFlowGraphEdge(MethodDescriptor md, NTuple<Descriptor> from,
5831       NTuple<Descriptor> inter, NTuple<Descriptor> to) {
5832
5833     FlowGraph graph = getFlowGraph(md);
5834
5835     if (inter != null) {
5836       graph.addValueFlowEdge(from, inter);
5837       graph.addValueFlowEdge(inter, to);
5838     } else {
5839       graph.addValueFlowEdge(from, to);
5840     }
5841
5842   }
5843
5844   public void writeInferredLatticeDotFile(ClassDescriptor cd, HierarchyGraph simpleHierarchyGraph,
5845       SSJavaLattice<String> locOrder, String nameSuffix) {
5846     System.out.println("@cd=" + cd);
5847     System.out.println("@sharedLoc=" + locOrder.getSharedLocSet());
5848     writeInferredLatticeDotFile(cd, null, simpleHierarchyGraph, locOrder, nameSuffix);
5849   }
5850
5851   public void writeInferredLatticeDotFile(ClassDescriptor cd, MethodDescriptor md,
5852       HierarchyGraph simpleHierarchyGraph, SSJavaLattice<String> locOrder, String nameSuffix) {
5853
5854     String fileName = "lattice_";
5855     if (md != null) {
5856       fileName +=
5857       /* cd.getSymbol().replaceAll("[\\W_]", "") + "_" + */md.toString().replaceAll("[\\W_]", "");
5858     } else {
5859       fileName += cd.getSymbol().replaceAll("[\\W_]", "");
5860     }
5861
5862     fileName += nameSuffix;
5863
5864     Set<Pair<String, String>> pairSet = locOrder.getOrderingPairSet();
5865
5866     Set<String> addedLocSet = new HashSet<String>();
5867
5868     if (pairSet.size() > 0) {
5869       try {
5870         BufferedWriter bw = new BufferedWriter(new FileWriter(fileName + ".dot"));
5871
5872         bw.write("digraph " + fileName + " {\n");
5873
5874         for (Iterator iterator = pairSet.iterator(); iterator.hasNext();) {
5875           // pair is in the form of <higher, lower>
5876           Pair<String, String> pair = (Pair<String, String>) iterator.next();
5877
5878           String highLocId = pair.getFirst();
5879           String lowLocId = pair.getSecond();
5880           if (!addedLocSet.contains(highLocId)) {
5881             addedLocSet.add(highLocId);
5882             drawNode(bw, locOrder, simpleHierarchyGraph, highLocId);
5883           }
5884
5885           if (!addedLocSet.contains(lowLocId)) {
5886             addedLocSet.add(lowLocId);
5887             drawNode(bw, locOrder, simpleHierarchyGraph, lowLocId);
5888           }
5889
5890           bw.write(highLocId + " -> " + lowLocId + ";\n");
5891         }
5892         bw.write("}\n");
5893         bw.close();
5894
5895       } catch (IOException e) {
5896         e.printStackTrace();
5897       }
5898
5899     }
5900
5901   }
5902
5903   private String convertMergeSetToString(HierarchyGraph graph, Set<HNode> mergeSet) {
5904     String str = "";
5905     for (Iterator iterator = mergeSet.iterator(); iterator.hasNext();) {
5906       HNode merged = (HNode) iterator.next();
5907       if (merged.isMergeNode()) {
5908         str += convertMergeSetToString(graph, graph.getMapHNodetoMergeSet().get(merged));
5909       } else {
5910         str += " " + merged.getName();
5911       }
5912     }
5913     return str;
5914   }
5915
5916   private void drawNode(BufferedWriter bw, SSJavaLattice<String> lattice, HierarchyGraph graph,
5917       String locName) throws IOException {
5918
5919     String prettyStr;
5920     if (lattice.isSharedLoc(locName)) {
5921       prettyStr = locName + "*";
5922     } else {
5923       prettyStr = locName;
5924     }
5925     // HNode node = graph.getHNode(locName);
5926     // if (node != null && node.isMergeNode()) {
5927     // Set<HNode> mergeSet = graph.getMapHNodetoMergeSet().get(node);
5928     // prettyStr += ":" + convertMergeSetToString(graph, mergeSet);
5929     // }
5930     bw.write(locName + " [label=\"" + prettyStr + "\"]" + ";\n");
5931   }
5932
5933   public void _debug_writeFlowGraph() {
5934     Set<MethodDescriptor> keySet = mapMethodDescriptorToFlowGraph.keySet();
5935
5936     for (Iterator<MethodDescriptor> iterator = keySet.iterator(); iterator.hasNext();) {
5937       MethodDescriptor md = (MethodDescriptor) iterator.next();
5938       FlowGraph fg = mapMethodDescriptorToFlowGraph.get(md);
5939       GlobalFlowGraph subGlobalFlowGraph = getSubGlobalFlowGraph(md);
5940       try {
5941         fg.writeGraph();
5942         subGlobalFlowGraph.writeGraph("_SUBGLOBAL");
5943       } catch (IOException e) {
5944         e.printStackTrace();
5945       }
5946     }
5947
5948   }
5949
5950 }
5951
5952 class CyclicFlowException extends Exception {
5953
5954 }
5955
5956 class InterDescriptor extends Descriptor {
5957
5958   Pair<MethodInvokeNode, Integer> minArgIdxPair;
5959
5960   public InterDescriptor(String name) {
5961     super(name);
5962   }
5963
5964   public void setMethodArgIdxPair(MethodInvokeNode min, int idx) {
5965     minArgIdxPair = new Pair<MethodInvokeNode, Integer>(min, new Integer(idx));
5966   }
5967
5968   public Pair<MethodInvokeNode, Integer> getMethodArgIdxPair() {
5969     return minArgIdxPair;
5970   }
5971
5972 }