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