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