Robust/src/Analysis/SSJava/LocationInference.java

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