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