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