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