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