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