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