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