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