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.SwitchStatementNode;
  51 import IR.Tree.TertiaryNode;
  52 import IR.Tree.TreeNode;
  53 import Util.Pair;
  54
  55 public class LocationInference {
  56
  57   State state;
  58   SSJavaAnalysis ssjava;
  59
  60   List<ClassDescriptor> toanalyzeList;
  61   List<MethodDescriptor> toanalyzeMethodList;
  62   Map<MethodDescriptor, FlowGraph> mapMethodDescriptorToFlowGraph;
  63
  64   // map a method descriptor to its set of parameter descriptors
  65   Map<MethodDescriptor, Set<Descriptor>> mapMethodDescriptorToParamDescSet;
  66
  67   // keep current descriptors to visit in fixed-point interprocedural analysis,
  68   private Stack<MethodDescriptor> methodDescriptorsToVisitStack;
  69
  70   // map a class descriptor to a field lattice
  71   private Map<ClassDescriptor, SSJavaLattice<String>> cd2lattice;
  72
  73   // map a method descriptor to a method lattice
  74   private Map<MethodDescriptor, SSJavaLattice<String>> md2lattice;
  75
  76   // map a method descriptor to the set of method invocation nodes which are
  77   // invoked by the method descriptor
  78   private Map<MethodDescriptor, Set<MethodInvokeNode>> mapMethodDescriptorToMethodInvokeNodeSet;
  79
  80   private Map<MethodInvokeNode, Map<Integer, NodeTupleSet>> mapMethodInvokeNodeToArgIdxMap;
  81
  82   private Map<MethodDescriptor, MethodLocationInfo> mapMethodDescToMethodLocationInfo;
  83
  84   private Map<ClassDescriptor, LocationInfo> mapClassToLocationInfo;
  85
  86   private Map<MethodDescriptor, Set<MethodDescriptor>> mapMethodToCalleeSet;
  87
  88   private Map<MethodDescriptor, Set<FlowNode>> mapMethodDescToParamNodeFlowsToReturnValue;
  89
  90   private Map<String, Vector<String>> mapFileNameToLineVector;
  91
  92   private Map<Descriptor, Integer> mapDescToDefinitionLine;
  93
  94   public static final String GLOBALLOC = "GLOBALLOC";
  95
  96   public static final String TOPLOC = "TOPLOC";
  97
  98   public static final Descriptor GLOBALDESC = new NameDescriptor(GLOBALLOC);
  99
 100   public static final Descriptor TOPDESC = new NameDescriptor(TOPLOC);
 101
 102   public static String newline = System.getProperty("line.separator");
 103
 104   LocationInfo curMethodInfo;
 105
 106   boolean debug = true;
 107
 108   public LocationInference(SSJavaAnalysis ssjava, State state) {
 109     this.ssjava = ssjava;
 110     this.state = state;
 111     this.toanalyzeList = new ArrayList<ClassDescriptor>();
 112     this.toanalyzeMethodList = new ArrayList<MethodDescriptor>();
 113     this.mapMethodDescriptorToFlowGraph = new HashMap<MethodDescriptor, FlowGraph>();
 114     this.cd2lattice = new HashMap<ClassDescriptor, SSJavaLattice<String>>();
 115     this.md2lattice = new HashMap<MethodDescriptor, SSJavaLattice<String>>();
 116     this.methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
 117     this.mapMethodDescriptorToMethodInvokeNodeSet =
 118         new HashMap<MethodDescriptor, Set<MethodInvokeNode>>();
 119     this.mapMethodInvokeNodeToArgIdxMap =
 120         new HashMap<MethodInvokeNode, Map<Integer, NodeTupleSet>>();
 121     this.mapMethodDescToMethodLocationInfo = new HashMap<MethodDescriptor, MethodLocationInfo>();
 122     this.mapMethodToCalleeSet = new HashMap<MethodDescriptor, Set<MethodDescriptor>>();
 123     this.mapClassToLocationInfo = new HashMap<ClassDescriptor, LocationInfo>();
 124
 125     this.mapFileNameToLineVector = new HashMap<String, Vector<String>>();
 126     this.mapDescToDefinitionLine = new HashMap<Descriptor, Integer>();
 127     this.mapMethodDescToParamNodeFlowsToReturnValue =
 128         new HashMap<MethodDescriptor, Set<FlowNode>>();
 129   }
 130
 131   public void setupToAnalyze() {
 132     SymbolTable classtable = state.getClassSymbolTable();
 133     toanalyzeList.clear();
 134     toanalyzeList.addAll(classtable.getValueSet());
 135     // Collections.sort(toanalyzeList, new Comparator<ClassDescriptor>() {
 136     // public int compare(ClassDescriptor o1, ClassDescriptor o2) {
 137     // return o1.getClassName().compareToIgnoreCase(o2.getClassName());
 138     // }
 139     // });
 140   }
 141
 142   public void setupToAnalazeMethod(ClassDescriptor cd) {
 143
 144     SymbolTable methodtable = cd.getMethodTable();
 145     toanalyzeMethodList.clear();
 146     toanalyzeMethodList.addAll(methodtable.getValueSet());
 147     Collections.sort(toanalyzeMethodList, new Comparator<MethodDescriptor>() {
 148       public int compare(MethodDescriptor o1, MethodDescriptor o2) {
 149         return o1.getSymbol().compareToIgnoreCase(o2.getSymbol());
 150       }
 151     });
 152   }
 153
 154   public boolean toAnalyzeMethodIsEmpty() {
 155     return toanalyzeMethodList.isEmpty();
 156   }
 157
 158   public boolean toAnalyzeIsEmpty() {
 159     return toanalyzeList.isEmpty();
 160   }
 161
 162   public ClassDescriptor toAnalyzeNext() {
 163     return toanalyzeList.remove(0);
 164   }
 165
 166   public MethodDescriptor toAnalyzeMethodNext() {
 167     return toanalyzeMethodList.remove(0);
 168   }
 169
 170   public void inference() {
 171
 172     // 1) construct value flow graph
 173     constructFlowGraph();
 174
 175     // 2) construct lattices
 176     inferLattices();
 177
 178     simplifyLattices();
 179
 180     debug_writeLatticeDotFile();
 181
 182     // 3) check properties
 183     checkLattices();
 184
 185     // 4) generate annotated source codes
 186     generateAnnoatedCode();
 187
 188   }
 189
 190   private void addMapClassDefinitionToLineNum(ClassDescriptor cd, String strLine, int lineNum) {
 191
 192     String classSymbol = cd.getSymbol();
 193     int idx = classSymbol.lastIndexOf("$");
 194     if (idx != -1) {
 195       classSymbol = classSymbol.substring(idx + 1);
 196     }
 197
 198     String pattern = "class " + classSymbol + " ";
 199     if (strLine.indexOf(pattern) != -1) {
 200       mapDescToDefinitionLine.put(cd, lineNum);
 201     }
 202   }
 203
 204   private void addMapMethodDefinitionToLineNum(Set<MethodDescriptor> methodSet, String strLine,
 205       int lineNum) {
 206     for (Iterator iterator = methodSet.iterator(); iterator.hasNext();) {
 207       MethodDescriptor md = (MethodDescriptor) iterator.next();
 208       String pattern = md.getMethodDeclaration();
 209       if (strLine.indexOf(pattern) != -1) {
 210         mapDescToDefinitionLine.put(md, lineNum);
 211         methodSet.remove(md);
 212         return;
 213       }
 214     }
 215
 216   }
 217
 218   private void readOriginalSourceFiles() {
 219
 220     SymbolTable classtable = state.getClassSymbolTable();
 221
 222     Set<ClassDescriptor> classDescSet = new HashSet<ClassDescriptor>();
 223     classDescSet.addAll(classtable.getValueSet());
 224
 225     try {
 226       // inefficient implement. it may re-visit the same file if the file
 227       // contains more than one class definitions.
 228       for (Iterator iterator = classDescSet.iterator(); iterator.hasNext();) {
 229         ClassDescriptor cd = (ClassDescriptor) iterator.next();
 230
 231         Set<MethodDescriptor> methodSet = new HashSet<MethodDescriptor>();
 232         methodSet.addAll(cd.getMethodTable().getValueSet());
 233
 234         String sourceFileName = cd.getSourceFileName();
 235         Vector<String> lineVec = new Vector<String>();
 236
 237         mapFileNameToLineVector.put(sourceFileName, lineVec);
 238
 239         BufferedReader in = new BufferedReader(new FileReader(sourceFileName));
 240         String strLine;
 241         int lineNum = 1;
 242         lineVec.add(""); // the index is started from 1.
 243         while ((strLine = in.readLine()) != null) {
 244           lineVec.add(lineNum, strLine);
 245           addMapClassDefinitionToLineNum(cd, strLine, lineNum);
 246           addMapMethodDefinitionToLineNum(methodSet, strLine, lineNum);
 247           lineNum++;
 248         }
 249
 250       }
 251
 252     } catch (IOException e) {
 253       e.printStackTrace();
 254     }
 255
 256   }
 257
 258   private String generateLatticeDefinition(Descriptor desc) {
 259
 260     Set<String> sharedLocSet = new HashSet<String>();
 261
 262     SSJavaLattice<String> lattice = getLattice(desc);
 263     String rtr = "@LATTICE(\"";
 264
 265     Map<String, Set<String>> map = lattice.getTable();
 266     Set<String> keySet = map.keySet();
 267     boolean first = true;
 268     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 269       String key = (String) iterator.next();
 270       if (!key.equals(lattice.getTopItem())) {
 271         Set<String> connectedSet = map.get(key);
 272
 273         if (connectedSet.size() == 1) {
 274           if (connectedSet.iterator().next().equals(lattice.getBottomItem())) {
 275             if (!first) {
 276               rtr += ",";
 277             } else {
 278               rtr += "LOC,";
 279               first = false;
 280             }
 281             rtr += key;
 282             if (lattice.isSharedLoc(key)) {
 283               rtr += "," + key + "*";
 284             }
 285           }
 286         }
 287
 288         for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) {
 289           String loc = (String) iterator2.next();
 290           if (!loc.equals(lattice.getBottomItem())) {
 291             if (!first) {
 292               rtr += ",";
 293             } else {
 294               rtr += "LOC,";
 295               first = false;
 296             }
 297             rtr += loc + "<" + key;
 298             if (lattice.isSharedLoc(key) && (!sharedLocSet.contains(key))) {
 299               rtr += "," + key + "*";
 300               sharedLocSet.add(key);
 301             }
 302             if (lattice.isSharedLoc(loc) && (!sharedLocSet.contains(loc))) {
 303               rtr += "," + loc + "*";
 304               sharedLocSet.add(loc);
 305             }
 306
 307           }
 308         }
 309       }
 310     }
 311
 312     rtr += "\")";
 313
 314     if (desc instanceof MethodDescriptor) {
 315       TypeDescriptor returnType = ((MethodDescriptor) desc).getReturnType();
 316
 317       MethodLocationInfo methodLocInfo = getMethodLocationInfo((MethodDescriptor) desc);
 318
 319       if (returnType != null && (!returnType.isVoid())) {
 320         rtr +=
 321             "\n@RETURNLOC(\"" + generateLocationAnnoatation(methodLocInfo.getReturnLoc()) + "\")";
 322       }
 323       rtr += "\n@THISLOC(\"this\")\n@GLOBALLOC(\"GLOBALLOC\")";
 324
 325       if (lattice.containsKey("PCLOC")) {
 326         rtr += "\n@PCLOC(\"PCLOC\")";
 327       }
 328     }
 329
 330     return rtr;
 331   }
 332
 333   private void generateAnnoatedCode() {
 334
 335     readOriginalSourceFiles();
 336
 337     setupToAnalyze();
 338     while (!toAnalyzeIsEmpty()) {
 339       ClassDescriptor cd = toAnalyzeNext();
 340
 341       setupToAnalazeMethod(cd);
 342
 343       LocationInfo locInfo = mapClassToLocationInfo.get(cd);
 344       String sourceFileName = cd.getSourceFileName();
 345
 346       if (cd.isInterface()) {
 347         continue;
 348       }
 349
 350       int classDefLine = mapDescToDefinitionLine.get(cd);
 351       Vector<String> sourceVec = mapFileNameToLineVector.get(sourceFileName);
 352
 353       if (locInfo == null) {
 354         locInfo = getLocationInfo(cd);
 355       }
 356
 357       for (Iterator iter = cd.getFields(); iter.hasNext();) {
 358         Descriptor fieldDesc = (Descriptor) iter.next();
 359         String locIdentifier = locInfo.getFieldInferLocation(fieldDesc).getLocIdentifier();
 360         if (!getLattice(cd).containsKey(locIdentifier)) {
 361           getLattice(cd).put(locIdentifier);
 362         }
 363       }
 364
 365       String fieldLatticeDefStr = generateLatticeDefinition(cd);
 366       String annoatedSrc = fieldLatticeDefStr + newline + sourceVec.get(classDefLine);
 367       sourceVec.set(classDefLine, annoatedSrc);
 368
 369       // generate annotations for field declarations
 370       LocationInfo fieldLocInfo = getLocationInfo(cd);
 371       Map<Descriptor, CompositeLocation> inferLocMap = fieldLocInfo.getMapDescToInferLocation();
 372
 373       for (Iterator iter = cd.getFields(); iter.hasNext();) {
 374         FieldDescriptor fd = (FieldDescriptor) iter.next();
 375
 376         String locAnnotationStr;
 377         if (inferLocMap.containsKey(fd)) {
 378           CompositeLocation inferLoc = inferLocMap.get(fd);
 379           locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")";
 380         } else {
 381           // if the field is not accssed by SS part, just assigns dummy
 382           // location
 383           locAnnotationStr = "@LOC(\"LOC\")";
 384         }
 385         int fdLineNum = fd.getLineNum();
 386         String orgFieldDeclarationStr = sourceVec.get(fdLineNum);
 387         String fieldDeclaration = fd.toString();
 388         fieldDeclaration = fieldDeclaration.substring(0, fieldDeclaration.length() - 1);
 389
 390         String annoatedStr = locAnnotationStr + " " + orgFieldDeclarationStr;
 391         sourceVec.set(fdLineNum, annoatedStr);
 392
 393       }
 394
 395       while (!toAnalyzeMethodIsEmpty()) {
 396         MethodDescriptor md = toAnalyzeMethodNext();
 397         SSJavaLattice<String> methodLattice = md2lattice.get(md);
 398         if (methodLattice != null) {
 399
 400           int methodDefLine = md.getLineNum();
 401
 402           MethodLocationInfo methodLocInfo = getMethodLocationInfo(md);
 403
 404           Map<Descriptor, CompositeLocation> methodInferLocMap =
 405               methodLocInfo.getMapDescToInferLocation();
 406           Set<Descriptor> localVarDescSet = methodInferLocMap.keySet();
 407
 408           for (Iterator iterator = localVarDescSet.iterator(); iterator.hasNext();) {
 409             Descriptor localVarDesc = (Descriptor) iterator.next();
 410             CompositeLocation inferLoc = methodInferLocMap.get(localVarDesc);
 411
 412             String locAnnotationStr = "@LOC(\"" + generateLocationAnnoatation(inferLoc) + "\")";
 413
 414             if (!isParameter(md, localVarDesc)) {
 415               if (mapDescToDefinitionLine.containsKey(localVarDesc)) {
 416                 int varLineNum = mapDescToDefinitionLine.get(localVarDesc);
 417                 String orgSourceLine = sourceVec.get(varLineNum);
 418                 int idx =
 419                     orgSourceLine.indexOf(generateVarDeclaration((VarDescriptor) localVarDesc));
 420                 assert (idx != -1);
 421                 String annoatedStr =
 422                     orgSourceLine.substring(0, idx) + locAnnotationStr + " "
 423                         + orgSourceLine.substring(idx);
 424                 sourceVec.set(varLineNum, annoatedStr);
 425               }
 426             } else {
 427               String methodDefStr = sourceVec.get(methodDefLine);
 428
 429               int idx =
 430                   getParamLocation(methodDefStr,
 431                       generateVarDeclaration((VarDescriptor) localVarDesc));
 432
 433               System.out.println("#methodDefStr=" + methodDefStr + " localVar="
 434                   + generateVarDeclaration((VarDescriptor) localVarDesc) + "   idx=" + idx);
 435
 436               assert (idx != -1);
 437
 438               String annoatedStr =
 439                   methodDefStr.substring(0, idx) + locAnnotationStr + " "
 440                       + methodDefStr.substring(idx);
 441               sourceVec.set(methodDefLine, annoatedStr);
 442             }
 443
 444           }
 445
 446           String methodLatticeDefStr = generateLatticeDefinition(md);
 447           String annoatedStr = methodLatticeDefStr + newline + sourceVec.get(methodDefLine);
 448           sourceVec.set(methodDefLine, annoatedStr);
 449
 450         }
 451       }
 452
 453     }
 454
 455     codeGen();
 456   }
 457
 458   private int getParamLocation(String methodStr, String paramStr) {
 459
 460     String pattern = paramStr + ",";
 461
 462     int idx = methodStr.indexOf(pattern);
 463     if (idx != -1) {
 464       return idx;
 465     } else {
 466       pattern = paramStr + ")";
 467       return methodStr.indexOf(pattern);
 468     }
 469
 470   }
 471
 472   private String generateVarDeclaration(VarDescriptor varDesc) {
 473
 474     TypeDescriptor td = varDesc.getType();
 475     String rtr = td.toString();
 476     if (td.isArray()) {
 477       for (int i = 0; i < td.getArrayCount(); i++) {
 478         rtr += "[]";
 479       }
 480     }
 481     rtr += " " + varDesc.getName();
 482     return rtr;
 483
 484   }
 485
 486   private String generateLocationAnnoatation(CompositeLocation loc) {
 487
 488     String rtr = "";
 489     // method location
 490     Location methodLoc = loc.get(0);
 491     rtr += methodLoc.getLocIdentifier();
 492
 493     for (int i = 1; i < loc.getSize(); i++) {
 494       Location element = loc.get(i);
 495       rtr += "," + element.getDescriptor().getSymbol() + "." + element.getLocIdentifier();
 496     }
 497
 498     return rtr;
 499   }
 500
 501   private boolean isParameter(MethodDescriptor md, Descriptor localVarDesc) {
 502     return getFlowGraph(md).isParamDesc(localVarDesc);
 503   }
 504
 505   private String extractFileName(String fileName) {
 506     int idx = fileName.lastIndexOf("/");
 507     if (idx == -1) {
 508       return fileName;
 509     } else {
 510       return fileName.substring(idx + 1);
 511     }
 512
 513   }
 514
 515   private void codeGen() {
 516
 517     Set<String> originalFileNameSet = mapFileNameToLineVector.keySet();
 518     for (Iterator iterator = originalFileNameSet.iterator(); iterator.hasNext();) {
 519       String orgFileName = (String) iterator.next();
 520       String outputFileName = extractFileName(orgFileName);
 521
 522       Vector<String> sourceVec = mapFileNameToLineVector.get(orgFileName);
 523
 524       try {
 525
 526         FileWriter fileWriter = new FileWriter("./infer/" + outputFileName);
 527         BufferedWriter out = new BufferedWriter(fileWriter);
 528
 529         for (int i = 0; i < sourceVec.size(); i++) {
 530           out.write(sourceVec.get(i));
 531           out.newLine();
 532         }
 533         out.close();
 534       } catch (IOException e) {
 535         e.printStackTrace();
 536       }
 537
 538     }
 539
 540   }
 541
 542   private void simplifyLattices() {
 543
 544     // generate lattice dot file
 545     setupToAnalyze();
 546
 547     while (!toAnalyzeIsEmpty()) {
 548       ClassDescriptor cd = toAnalyzeNext();
 549
 550       setupToAnalazeMethod(cd);
 551
 552       SSJavaLattice<String> classLattice = cd2lattice.get(cd);
 553       if (classLattice != null) {
 554         classLattice.removeRedundantEdges();
 555       }
 556
 557       while (!toAnalyzeMethodIsEmpty()) {
 558         MethodDescriptor md = toAnalyzeMethodNext();
 559         SSJavaLattice<String> methodLattice = md2lattice.get(md);
 560         if (methodLattice != null) {
 561           methodLattice.removeRedundantEdges();
 562         }
 563       }
 564     }
 565
 566   }
 567
 568   private void checkLattices() {
 569
 570     LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
 571
 572     // current descriptors to visit in fixed-point interprocedural analysis,
 573     // prioritized by
 574     // dependency in the call graph
 575     methodDescriptorsToVisitStack.clear();
 576
 577     descriptorListToAnalyze.removeFirst();
 578
 579     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
 580     methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
 581
 582     while (!descriptorListToAnalyze.isEmpty()) {
 583       MethodDescriptor md = descriptorListToAnalyze.removeFirst();
 584       checkLatticesOfVirtualMethods(md);
 585     }
 586
 587   }
 588
 589   private void debug_writeLatticeDotFile() {
 590     // generate lattice dot file
 591
 592     setupToAnalyze();
 593
 594     while (!toAnalyzeIsEmpty()) {
 595       ClassDescriptor cd = toAnalyzeNext();
 596
 597       setupToAnalazeMethod(cd);
 598
 599       SSJavaLattice<String> classLattice = cd2lattice.get(cd);
 600       if (classLattice != null) {
 601         ssjava.writeLatticeDotFile(cd, null, classLattice);
 602         debug_printDescriptorToLocNameMapping(cd);
 603       }
 604
 605       while (!toAnalyzeMethodIsEmpty()) {
 606         MethodDescriptor md = toAnalyzeMethodNext();
 607         SSJavaLattice<String> methodLattice = md2lattice.get(md);
 608         if (methodLattice != null) {
 609           ssjava.writeLatticeDotFile(cd, md, methodLattice);
 610           debug_printDescriptorToLocNameMapping(md);
 611         }
 612       }
 613     }
 614
 615   }
 616
 617   private void debug_printDescriptorToLocNameMapping(Descriptor desc) {
 618
 619     LocationInfo info = getLocationInfo(desc);
 620     System.out.println("## " + desc + " ##");
 621     System.out.println(info.getMapDescToInferLocation());
 622     LocationInfo locInfo = getLocationInfo(desc);
 623     System.out.println("mapping=" + locInfo.getMapLocSymbolToDescSet());
 624     System.out.println("###################");
 625
 626   }
 627
 628   private void inferLattices() {
 629
 630     // do fixed-point analysis
 631
 632     LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
 633
 634     Collections.sort(descriptorListToAnalyze, new Comparator<MethodDescriptor>() {
 635       public int compare(MethodDescriptor o1, MethodDescriptor o2) {
 636         return o1.getSymbol().compareToIgnoreCase(o2.getSymbol());
 637       }
 638     });
 639
 640     // current descriptors to visit in fixed-point interprocedural analysis,
 641     // prioritized by
 642     // dependency in the call graph
 643     methodDescriptorsToVisitStack.clear();
 644
 645     // descriptorListToAnalyze.removeFirst();
 646
 647     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
 648     methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
 649
 650     while (!descriptorListToAnalyze.isEmpty()) {
 651       MethodDescriptor md = descriptorListToAnalyze.removeFirst();
 652       methodDescriptorsToVisitStack.add(md);
 653     }
 654
 655     // analyze scheduled methods until there are no more to visit
 656     while (!methodDescriptorsToVisitStack.isEmpty()) {
 657       // start to analyze leaf node
 658       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
 659
 660       SSJavaLattice<String> methodLattice =
 661           new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM);
 662
 663       MethodLocationInfo methodInfo = new MethodLocationInfo(md);
 664       curMethodInfo = methodInfo;
 665
 666       System.out.println();
 667       System.out.println("SSJAVA: Inferencing the lattice from " + md);
 668
 669       try {
 670         analyzeMethodLattice(md, methodLattice, methodInfo);
 671       } catch (CyclicFlowException e) {
 672         throw new Error("Fail to generate the method lattice for " + md);
 673       }
 674
 675       SSJavaLattice<String> prevMethodLattice = getMethodLattice(md);
 676       MethodLocationInfo prevMethodInfo = getMethodLocationInfo(md);
 677
 678       if ((!methodLattice.equals(prevMethodLattice)) || (!methodInfo.equals(prevMethodInfo))) {
 679
 680         setMethodLattice(md, methodLattice);
 681         setMethodLocInfo(md, methodInfo);
 682
 683         // results for callee changed, so enqueue dependents caller for
 684         // further analysis
 685         Iterator<MethodDescriptor> depsItr = ssjava.getDependents(md).iterator();
 686         while (depsItr.hasNext()) {
 687           MethodDescriptor methodNext = depsItr.next();
 688           if (!methodDescriptorsToVisitStack.contains(methodNext)
 689               && methodDescriptorToVistSet.contains(methodNext)) {
 690             methodDescriptorsToVisitStack.add(methodNext);
 691           }
 692         }
 693
 694       }
 695
 696     }
 697   }
 698
 699   private void setMethodLocInfo(MethodDescriptor md, MethodLocationInfo methodInfo) {
 700     mapMethodDescToMethodLocationInfo.put(md, methodInfo);
 701   }
 702
 703   private void checkLatticesOfVirtualMethods(MethodDescriptor md) {
 704
 705     if (!md.isStatic()) {
 706       Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
 707       setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md));
 708
 709       for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
 710         MethodDescriptor mdCallee = (MethodDescriptor) iterator.next();
 711         if (!md.equals(mdCallee)) {
 712           checkConsistency(md, mdCallee);
 713         }
 714       }
 715
 716     }
 717
 718   }
 719
 720   private void checkConsistency(MethodDescriptor md1, MethodDescriptor md2) {
 721
 722     // check that two lattice have the same relations between parameters(+PC
 723     // LOC, GLOBAL_LOC RETURN LOC)
 724
 725     List<CompositeLocation> list1 = new ArrayList<CompositeLocation>();
 726     List<CompositeLocation> list2 = new ArrayList<CompositeLocation>();
 727
 728     MethodLocationInfo locInfo1 = getMethodLocationInfo(md1);
 729     MethodLocationInfo locInfo2 = getMethodLocationInfo(md2);
 730
 731     Map<Integer, CompositeLocation> paramMap1 = locInfo1.getMapParamIdxToInferLoc();
 732     Map<Integer, CompositeLocation> paramMap2 = locInfo2.getMapParamIdxToInferLoc();
 733
 734     int numParam = locInfo1.getMapParamIdxToInferLoc().keySet().size();
 735
 736     // add location types of paramters
 737     for (int idx = 0; idx < numParam; idx++) {
 738       list1.add(paramMap1.get(Integer.valueOf(idx)));
 739       list2.add(paramMap2.get(Integer.valueOf(idx)));
 740     }
 741
 742     // add program counter location
 743     list1.add(locInfo1.getPCLoc());
 744     list2.add(locInfo2.getPCLoc());
 745
 746     if (!md1.getReturnType().isVoid()) {
 747       // add return value location
 748       CompositeLocation rtrLoc1 =
 749           new CompositeLocation(new Location(md1, locInfo1.getReturnLocName()));
 750       CompositeLocation rtrLoc2 =
 751           new CompositeLocation(new Location(md2, locInfo2.getReturnLocName()));
 752       list1.add(rtrLoc1);
 753       list2.add(rtrLoc2);
 754     }
 755
 756     // add global location type
 757     if (md1.isStatic()) {
 758       CompositeLocation globalLoc1 =
 759           new CompositeLocation(new Location(md1, locInfo1.getGlobalLocName()));
 760       CompositeLocation globalLoc2 =
 761           new CompositeLocation(new Location(md2, locInfo2.getGlobalLocName()));
 762       list1.add(globalLoc1);
 763       list2.add(globalLoc2);
 764     }
 765
 766     for (int i = 0; i < list1.size(); i++) {
 767       CompositeLocation locA1 = list1.get(i);
 768       CompositeLocation locA2 = list2.get(i);
 769       for (int k = 0; k < list1.size(); k++) {
 770         if (i != k) {
 771           CompositeLocation locB1 = list1.get(k);
 772           CompositeLocation locB2 = list2.get(k);
 773           boolean r1 = isGreaterThan(getLattice(md1), locA1, locB1);
 774
 775           boolean r2 = isGreaterThan(getLattice(md1), locA2, locB2);
 776
 777           if (r1 != r2) {
 778             throw new Error("The method " + md1 + " is not consistent with the method " + md2
 779                 + ".:: They have a different ordering relation between locations (" + locA1 + ","
 780                 + locB1 + ") and (" + locA2 + "," + locB2 + ").");
 781           }
 782         }
 783       }
 784     }
 785
 786   }
 787
 788   private String getSymbol(int idx, FlowNode node) {
 789     Descriptor desc = node.getDescTuple().get(idx);
 790     return desc.getSymbol();
 791   }
 792
 793   private Descriptor getDescriptor(int idx, FlowNode node) {
 794     Descriptor desc = node.getDescTuple().get(idx);
 795     return desc;
 796   }
 797
 798   private void analyzeMethodLattice(MethodDescriptor md, SSJavaLattice<String> methodLattice,
 799       MethodLocationInfo methodInfo) throws CyclicFlowException {
 800
 801     // first take a look at method invocation nodes to newly added relations
 802     // from the callee
 803     analyzeLatticeMethodInvocationNode(md, methodLattice, methodInfo);
 804
 805     if (!md.isStatic()) {
 806       // set the this location
 807       String thisLocSymbol = md.getThis().getSymbol();
 808       methodInfo.setThisLocName(thisLocSymbol);
 809     }
 810
 811     // set the global location
 812     methodInfo.setGlobalLocName(LocationInference.GLOBALLOC);
 813     methodInfo.mapDescriptorToLocation(GLOBALDESC, new CompositeLocation(
 814         new Location(md, GLOBALLOC)));
 815
 816     // visit each node of method flow graph
 817     FlowGraph fg = getFlowGraph(md);
 818     Set<FlowNode> nodeSet = fg.getNodeSet();
 819
 820     // for the method lattice, we need to look at the first element of
 821     // NTuple<Descriptor>
 822     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 823       FlowNode srcNode = (FlowNode) iterator.next();
 824
 825       Set<FlowEdge> outEdgeSet = srcNode.getOutEdgeSet();
 826       for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) {
 827         FlowEdge outEdge = (FlowEdge) iterator2.next();
 828         FlowNode dstNode = outEdge.getDst();
 829
 830         NTuple<Descriptor> srcNodeTuple = srcNode.getDescTuple();
 831         NTuple<Descriptor> dstNodeTuple = dstNode.getDescTuple();
 832
 833         if (outEdge.getInitTuple().equals(srcNodeTuple)
 834             && outEdge.getEndTuple().equals(dstNodeTuple)) {
 835
 836           if ((srcNodeTuple.size() > 1 && dstNodeTuple.size() > 1)
 837               && srcNodeTuple.get(0).equals(dstNodeTuple.get(0))) {
 838
 839             // value flows between fields
 840             Descriptor desc = srcNodeTuple.get(0);
 841             ClassDescriptor classDesc;
 842
 843             if (desc.equals(GLOBALDESC)) {
 844               classDesc = md.getClassDesc();
 845             } else {
 846               VarDescriptor varDesc = (VarDescriptor) srcNodeTuple.get(0);
 847               classDesc = varDesc.getType().getClassDesc();
 848             }
 849             extractRelationFromFieldFlows(classDesc, srcNode, dstNode, 1);
 850
 851           } else {
 852             // value flow between local var - local var or local var - field
 853             addRelationToLattice(md, methodLattice, methodInfo, srcNode, dstNode);
 854           }
 855
 856           // else if (srcNodeTuple.size() == 1 || dstNodeTuple.size() == 1) {
 857           // // for the method lattice, we need to look at the first element of
 858           // // NTuple<Descriptor>
 859           // // in this case, take a look at connected nodes at the local level
 860           // addRelationToLattice(md, methodLattice, methodInfo, srcNode,
 861           // dstNode);
 862           // } else {
 863           // if
 864           // (!srcNode.getDescTuple().get(0).equals(dstNode.getDescTuple().get(0)))
 865           // {
 866           // // in this case, take a look at connected nodes at the local level
 867           // addRelationToLattice(md, methodLattice, methodInfo, srcNode,
 868           // dstNode);
 869           // } else {
 870           // Descriptor srcDesc = srcNode.getDescTuple().get(0);
 871           // Descriptor dstDesc = dstNode.getDescTuple().get(0);
 872           // recursivelyAddCompositeRelation(md, fg, methodInfo, srcNode,
 873           // dstNode, srcDesc,
 874           // dstDesc);
 875           // // recursiveAddRelationToLattice(1, md, srcNode, dstNode);
 876           // }
 877           // }
 878
 879         }
 880       }
 881     }
 882
 883     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 884       FlowNode flowNode = (FlowNode) iterator.next();
 885       if (flowNode.isDeclaratonNode()) {
 886         CompositeLocation inferLoc = methodInfo.getInferLocation(flowNode.getDescTuple().get(0));
 887         String locIdentifier = inferLoc.get(0).getLocIdentifier();
 888         if (!methodLattice.containsKey(locIdentifier)) {
 889           methodLattice.put(locIdentifier);
 890         }
 891
 892       }
 893     }
 894
 895     // create mapping from param idx to inferred composite location
 896
 897     int offset;
 898     if (!md.isStatic()) {
 899       // add 'this' reference location
 900       offset = 1;
 901       methodInfo.addMapParamIdxToInferLoc(0, methodInfo.getInferLocation(md.getThis()));
 902     } else {
 903       offset = 0;
 904     }
 905
 906     for (int idx = 0; idx < md.numParameters(); idx++) {
 907       Descriptor paramDesc = md.getParameter(idx);
 908       CompositeLocation inferParamLoc = methodInfo.getInferLocation(paramDesc);
 909       methodInfo.addMapParamIdxToInferLoc(idx + offset, inferParamLoc);
 910     }
 911
 912     Map<Integer, CompositeLocation> mapParamToLoc = methodInfo.getMapParamIdxToInferLoc();
 913     Set<Integer> keySet = mapParamToLoc.keySet();
 914
 915     if (!ssjava.getMethodContainingSSJavaLoop().equals(md)) {
 916       // calculate the initial program counter location
 917       // PC location is higher than location types of all parameters
 918       String pcLocSymbol = "PCLOC";
 919       for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 920         Integer paramIdx = (Integer) iterator.next();
 921         CompositeLocation inferLoc = mapParamToLoc.get(paramIdx);
 922         String paramLocLocalSymbol = inferLoc.get(0).getLocIdentifier();
 923         if (!methodLattice.isGreaterThan(pcLocSymbol, paramLocLocalSymbol)) {
 924           addRelationHigherToLower(methodLattice, methodInfo, pcLocSymbol, paramLocLocalSymbol);
 925
 926           Set<String> higherLocSet = getHigherLocSymbolThan(methodLattice, paramLocLocalSymbol);
 927           higherLocSet.remove(pcLocSymbol);
 928           for (Iterator iterator2 = higherLocSet.iterator(); iterator2.hasNext();) {
 929             String loc = (String) iterator2.next();
 930             addRelationHigherToLower(methodLattice, methodInfo, pcLocSymbol, loc);
 931           }
 932         }
 933       }
 934     }
 935
 936     // calculate a return location
 937     // the return location type is lower than all parameters and location types
 938     // of return values
 939     if (!md.getReturnType().isVoid()) {
 940
 941       // first, generate the set of return value location types that starts with
 942       // 'this' reference
 943
 944       Set<CompositeLocation> inferFieldReturnLocSet = new HashSet<CompositeLocation>();
 945
 946       Set<FlowNode> paramFlowNode = getParamNodeFlowingToReturnValue(md);
 947       Set<CompositeLocation> inferParamLocSet = new HashSet<CompositeLocation>();
 948       if (paramFlowNode != null) {
 949         for (Iterator iterator = paramFlowNode.iterator(); iterator.hasNext();) {
 950           FlowNode fn = (FlowNode) iterator.next();
 951           CompositeLocation inferLoc =
 952               generateInferredCompositeLocation(methodInfo, getFlowGraph(md).getLocationTuple(fn));
 953           inferParamLocSet.add(inferLoc);
 954         }
 955       }
 956
 957       Set<FlowNode> returnNodeSet = fg.getReturnNodeSet();
 958       skip: for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
 959         FlowNode returnNode = (FlowNode) iterator.next();
 960         CompositeLocation inferReturnLoc =
 961             generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode));
 962         System.out.println("@inferReturnLoc=" + inferReturnLoc);
 963         if (inferReturnLoc.get(0).getLocIdentifier().equals("this")) {
 964           // if the location type of the return value matches "this" reference
 965           // then, check whether this return value is equal to/lower than all of
 966           // parameters that possibly flow into the return values
 967           for (Iterator iterator2 = inferParamLocSet.iterator(); iterator2.hasNext();) {
 968             CompositeLocation paramInferLoc = (CompositeLocation) iterator2.next();
 969
 970             if ((!paramInferLoc.equals(inferReturnLoc))
 971                 && !isGreaterThan(methodLattice, paramInferLoc, inferReturnLoc)) {
 972               continue skip;
 973             }
 974           }
 975           inferFieldReturnLocSet.add(inferReturnLoc);
 976
 977         }
 978       }
 979
 980       if (inferFieldReturnLocSet.size() > 0) {
 981
 982         CompositeLocation returnLoc = getLowest(methodLattice, inferFieldReturnLocSet);
 983         methodInfo.setReturnLoc(returnLoc);
 984
 985       } else {
 986         String returnLocSymbol = "RETURNLOC";
 987         CompositeLocation returnLocInferLoc =
 988             new CompositeLocation(new Location(md, returnLocSymbol));
 989         methodInfo.setReturnLoc(returnLocInferLoc);
 990
 991         for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 992           Integer paramIdx = (Integer) iterator.next();
 993           CompositeLocation inferLoc = mapParamToLoc.get(paramIdx);
 994           String paramLocLocalSymbol = inferLoc.get(0).getLocIdentifier();
 995           if (!methodLattice.isGreaterThan(paramLocLocalSymbol, returnLocSymbol)) {
 996             addRelationHigherToLower(methodLattice, methodInfo, paramLocLocalSymbol,
 997                 returnLocSymbol);
 998           }
 999         }
1000
1001         for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
1002           FlowNode returnNode = (FlowNode) iterator.next();
1003           CompositeLocation inferLoc =
1004               generateInferredCompositeLocation(methodInfo, fg.getLocationTuple(returnNode));
1005           if (!isGreaterThan(methodLattice, inferLoc, returnLocInferLoc)) {
1006             addRelation(methodLattice, methodInfo, inferLoc, returnLocInferLoc);
1007           }
1008         }
1009
1010       }
1011
1012     }
1013
1014   }
1015
1016   private Set<String> getHigherLocSymbolThan(SSJavaLattice<String> lattice, String loc) {
1017     Set<String> higherLocSet = new HashSet<String>();
1018
1019     Set<String> locSet = lattice.getTable().keySet();
1020     for (Iterator iterator = locSet.iterator(); iterator.hasNext();) {
1021       String element = (String) iterator.next();
1022       if (lattice.isGreaterThan(element, loc) && (!element.equals(lattice.getTopItem()))) {
1023         higherLocSet.add(element);
1024       }
1025     }
1026     return higherLocSet;
1027   }
1028
1029   private CompositeLocation getLowest(SSJavaLattice<String> methodLattice,
1030       Set<CompositeLocation> set) {
1031
1032     CompositeLocation lowest = set.iterator().next();
1033
1034     if (set.size() == 1) {
1035       return lowest;
1036     }
1037
1038     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
1039       CompositeLocation loc = (CompositeLocation) iterator.next();
1040       if (isGreaterThan(methodLattice, lowest, loc)) {
1041         lowest = loc;
1042       }
1043     }
1044     return lowest;
1045   }
1046
1047   private boolean isGreaterThan(SSJavaLattice<String> methodLattice, CompositeLocation comp1,
1048       CompositeLocation comp2) {
1049
1050     int size = comp1.getSize() >= comp2.getSize() ? comp2.getSize() : comp1.getSize();
1051
1052     for (int idx = 0; idx < size; idx++) {
1053       Location loc1 = comp1.get(idx);
1054       Location loc2 = comp2.get(idx);
1055
1056       Descriptor desc1 = loc1.getDescriptor();
1057       Descriptor desc2 = loc2.getDescriptor();
1058
1059       if (!desc1.equals(desc2)) {
1060         throw new Error("Fail to compare " + comp1 + " and " + comp2);
1061       }
1062
1063       String symbol1 = loc1.getLocIdentifier();
1064       String symbol2 = loc2.getLocIdentifier();
1065
1066       SSJavaLattice<String> lattice;
1067       if (idx == 0) {
1068         lattice = methodLattice;
1069       } else {
1070         lattice = getLattice(desc1);
1071       }
1072       if (symbol1.equals(symbol2)) {
1073         continue;
1074       } else if (lattice.isGreaterThan(symbol1, symbol2)) {
1075         return true;
1076       } else {
1077         return false;
1078       }
1079
1080     }
1081
1082     return false;
1083   }
1084
1085   private void recursiveAddRelationToLattice(int idx, MethodDescriptor md,
1086       CompositeLocation srcInferLoc, CompositeLocation dstInferLoc) throws CyclicFlowException {
1087
1088     String srcLocSymbol = srcInferLoc.get(idx).getLocIdentifier();
1089     String dstLocSymbol = dstInferLoc.get(idx).getLocIdentifier();
1090
1091     if (srcLocSymbol.equals(dstLocSymbol)) {
1092       recursiveAddRelationToLattice(idx + 1, md, srcInferLoc, dstInferLoc);
1093     } else {
1094
1095       Descriptor parentDesc = srcInferLoc.get(idx).getDescriptor();
1096       LocationInfo locInfo = getLocationInfo(parentDesc);
1097
1098       addRelationHigherToLower(getLattice(parentDesc), getLocationInfo(parentDesc), srcLocSymbol,
1099           dstLocSymbol);
1100     }
1101
1102   }
1103
1104   private void analyzeLatticeMethodInvocationNode(MethodDescriptor mdCaller,
1105       SSJavaLattice<String> methodLattice, MethodLocationInfo methodInfo)
1106       throws CyclicFlowException {
1107
1108     // the transformation for a call site propagates all relations between
1109     // parameters from the callee
1110     // if the method is virtual, it also grab all relations from any possible
1111     // callees
1112
1113     Set<MethodInvokeNode> setMethodInvokeNode =
1114         mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller);
1115
1116     if (setMethodInvokeNode != null) {
1117
1118       for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) {
1119         MethodInvokeNode min = (MethodInvokeNode) iterator.next();
1120         MethodDescriptor mdCallee = min.getMethod();
1121         Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
1122         if (mdCallee.isStatic()) {
1123           setPossibleCallees.add(mdCallee);
1124         } else {
1125           Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getMethods(mdCallee);
1126           // removes method descriptors that are not invoked by the caller
1127           calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller));
1128           setPossibleCallees.addAll(calleeSet);
1129         }
1130
1131         for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
1132           MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
1133           propagateRelationToCaller(min, mdCaller, possibleMdCallee, methodLattice, methodInfo);
1134         }
1135
1136       }
1137     }
1138
1139   }
1140
1141   private void propagateRelationToCaller(MethodInvokeNode min, MethodDescriptor mdCaller,
1142       MethodDescriptor possibleMdCallee, SSJavaLattice<String> methodLattice,
1143       MethodLocationInfo methodInfo) throws CyclicFlowException {
1144
1145     SSJavaLattice<String> calleeLattice = getMethodLattice(possibleMdCallee);
1146     MethodLocationInfo calleeLocInfo = getMethodLocationInfo(possibleMdCallee);
1147     FlowGraph calleeFlowGraph = getFlowGraph(possibleMdCallee);
1148
1149     int numParam = calleeLocInfo.getNumParam();
1150     for (int i = 0; i < numParam; i++) {
1151       CompositeLocation param1 = calleeLocInfo.getParamCompositeLocation(i);
1152       for (int k = 0; k < numParam; k++) {
1153         if (i != k) {
1154           CompositeLocation param2 = calleeLocInfo.getParamCompositeLocation(k);
1155           if (isGreaterThan(getLattice(possibleMdCallee), param1, param2)) {
1156             NodeTupleSet argDescTupleSet1 = getNodeTupleSetByArgIdx(min, i);
1157             NodeTupleSet argDescTupleSet2 = getNodeTupleSetByArgIdx(min, k);
1158
1159             // the callee has the relation in which param1 is higher than param2
1160             // therefore, the caller has to have the relation in which arg1 is
1161             // higher than arg2
1162
1163             for (Iterator<NTuple<Descriptor>> iterator = argDescTupleSet1.iterator(); iterator
1164                 .hasNext();) {
1165               NTuple<Descriptor> argDescTuple1 = iterator.next();
1166
1167               for (Iterator<NTuple<Descriptor>> iterator2 = argDescTupleSet2.iterator(); iterator2
1168                   .hasNext();) {
1169                 NTuple<Descriptor> argDescTuple2 = iterator2.next();
1170
1171                 // retreive inferred location by the local var descriptor
1172
1173                 NTuple<Location> tuple1 = getFlowGraph(mdCaller).getLocationTuple(argDescTuple1);
1174                 NTuple<Location> tuple2 = getFlowGraph(mdCaller).getLocationTuple(argDescTuple2);
1175
1176                 // CompositeLocation higherInferLoc =
1177                 // methodInfo.getInferLocation(argTuple1.get(0));
1178                 // CompositeLocation lowerInferLoc =
1179                 // methodInfo.getInferLocation(argTuple2.get(0));
1180
1181                 CompositeLocation inferLoc1 = generateInferredCompositeLocation(methodInfo, tuple1);
1182                 CompositeLocation inferLoc2 = generateInferredCompositeLocation(methodInfo, tuple2);
1183
1184                 // addRelation(methodLattice, methodInfo, inferLoc1, inferLoc2);
1185
1186                 addFlowGraphEdge(mdCaller, argDescTuple1, argDescTuple2);
1187
1188               }
1189
1190             }
1191
1192           }
1193         }
1194       }
1195     }
1196
1197   }
1198
1199   private CompositeLocation generateInferredCompositeLocation(MethodLocationInfo methodInfo,
1200       NTuple<Location> tuple) {
1201
1202     // first, retrieve inferred location by the local var descriptor
1203     CompositeLocation inferLoc = new CompositeLocation();
1204
1205     CompositeLocation localVarInferLoc =
1206         methodInfo.getInferLocation(tuple.get(0).getLocDescriptor());
1207
1208     localVarInferLoc.get(0).setLocDescriptor(tuple.get(0).getLocDescriptor());
1209
1210     for (int i = 0; i < localVarInferLoc.getSize(); i++) {
1211       inferLoc.addLocation(localVarInferLoc.get(i));
1212     }
1213
1214     for (int i = 1; i < tuple.size(); i++) {
1215       Location cur = tuple.get(i);
1216       Descriptor enclosingDesc = cur.getDescriptor();
1217       Descriptor curDesc = cur.getLocDescriptor();
1218
1219       Location inferLocElement;
1220       if (curDesc == null) {
1221         // in this case, we have a newly generated location.
1222         // System.out.println("!!! generated location=" +
1223         // cur.getLocIdentifier());
1224         inferLocElement = new Location(enclosingDesc, cur.getLocIdentifier());
1225       } else {
1226         String fieldLocSymbol =
1227             getLocationInfo(enclosingDesc).getInferLocation(curDesc).get(0).getLocIdentifier();
1228         inferLocElement = new Location(enclosingDesc, fieldLocSymbol);
1229         inferLocElement.setLocDescriptor(curDesc);
1230       }
1231
1232       inferLoc.addLocation(inferLocElement);
1233
1234     }
1235
1236     assert (inferLoc.get(0).getLocDescriptor().getSymbol() == inferLoc.get(0).getLocIdentifier());
1237     return inferLoc;
1238   }
1239
1240   private void addRelation(SSJavaLattice<String> methodLattice, MethodLocationInfo methodInfo,
1241       CompositeLocation srcInferLoc, CompositeLocation dstInferLoc) throws CyclicFlowException {
1242
1243     System.out.println("addRelation --- srcInferLoc=" + srcInferLoc + "  dstInferLoc="
1244         + dstInferLoc);
1245     String srcLocalLocSymbol = srcInferLoc.get(0).getLocIdentifier();
1246     String dstLocalLocSymbol = dstInferLoc.get(0).getLocIdentifier();
1247
1248     if (srcInferLoc.getSize() == 1 && dstInferLoc.getSize() == 1) {
1249       // add a new relation to the local lattice
1250       addRelationHigherToLower(methodLattice, methodInfo, srcLocalLocSymbol, dstLocalLocSymbol);
1251     } else if (srcInferLoc.getSize() > 1 && dstInferLoc.getSize() > 1) {
1252       // both src and dst have assigned to a composite location
1253
1254       if (!srcLocalLocSymbol.equals(dstLocalLocSymbol)) {
1255         addRelationHigherToLower(methodLattice, methodInfo, srcLocalLocSymbol, dstLocalLocSymbol);
1256       } else {
1257         recursivelyAddRelation(1, srcInferLoc, dstInferLoc);
1258       }
1259     } else {
1260       // either src or dst has assigned to a composite location
1261       if (!srcLocalLocSymbol.equals(dstLocalLocSymbol)) {
1262         addRelationHigherToLower(methodLattice, methodInfo, srcLocalLocSymbol, dstLocalLocSymbol);
1263       }
1264     }
1265
1266     System.out.println();
1267
1268   }
1269
1270   public LocationInfo getLocationInfo(Descriptor d) {
1271     if (d instanceof MethodDescriptor) {
1272       return getMethodLocationInfo((MethodDescriptor) d);
1273     } else {
1274       return getFieldLocationInfo((ClassDescriptor) d);
1275     }
1276   }
1277
1278   private MethodLocationInfo getMethodLocationInfo(MethodDescriptor md) {
1279
1280     if (!mapMethodDescToMethodLocationInfo.containsKey(md)) {
1281       mapMethodDescToMethodLocationInfo.put(md, new MethodLocationInfo(md));
1282     }
1283
1284     return mapMethodDescToMethodLocationInfo.get(md);
1285
1286   }
1287
1288   private LocationInfo getFieldLocationInfo(ClassDescriptor cd) {
1289
1290     if (!mapClassToLocationInfo.containsKey(cd)) {
1291       mapClassToLocationInfo.put(cd, new LocationInfo(cd));
1292     }
1293
1294     return mapClassToLocationInfo.get(cd);
1295
1296   }
1297
1298   private void addRelationToLattice(MethodDescriptor md, SSJavaLattice<String> methodLattice,
1299       MethodLocationInfo methodInfo, FlowNode srcNode, FlowNode dstNode) throws CyclicFlowException {
1300
1301     System.out.println();
1302     System.out.println("### addRelationToLattice src=" + srcNode + " dst=" + dstNode);
1303
1304     // add a new binary relation of dstNode < srcNode
1305     FlowGraph flowGraph = getFlowGraph(md);
1306     try {
1307       System.out.println("***** src composite case::");
1308       calculateCompositeLocation(flowGraph, methodLattice, methodInfo, srcNode);
1309
1310       CompositeLocation srcInferLoc =
1311           generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(srcNode));
1312       CompositeLocation dstInferLoc =
1313           generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(dstNode));
1314       addRelation(methodLattice, methodInfo, srcInferLoc, dstInferLoc);
1315     } catch (CyclicFlowException e) {
1316       // there is a cyclic value flow... try to calculate a composite location
1317       // for the destination node
1318       System.out.println("***** dst composite case::");
1319       calculateCompositeLocation(flowGraph, methodLattice, methodInfo, dstNode);
1320       CompositeLocation srcInferLoc =
1321           generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(srcNode));
1322       CompositeLocation dstInferLoc =
1323           generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(dstNode));
1324       try {
1325         addRelation(methodLattice, methodInfo, srcInferLoc, dstInferLoc);
1326       } catch (CyclicFlowException e1) {
1327         throw new Error("Failed to merge cyclic value flows into a shared location.");
1328       }
1329     }
1330
1331   }
1332
1333   private void recursivelyAddRelation(int idx, CompositeLocation srcInferLoc,
1334       CompositeLocation dstInferLoc) throws CyclicFlowException {
1335
1336     String srcLocSymbol = srcInferLoc.get(idx).getLocIdentifier();
1337     String dstLocSymbol = dstInferLoc.get(idx).getLocIdentifier();
1338
1339     Descriptor parentDesc = srcInferLoc.get(idx).getDescriptor();
1340
1341     if (srcLocSymbol.equals(dstLocSymbol)) {
1342       // check if it is the case of shared location
1343       if (srcInferLoc.getSize() == (idx + 1) && dstInferLoc.getSize() == (idx + 1)) {
1344         Location inferLocElement = srcInferLoc.get(idx);
1345         System.out.println("SET SHARED LOCATION=" + inferLocElement);
1346         getLattice(inferLocElement.getDescriptor())
1347             .addSharedLoc(inferLocElement.getLocIdentifier());
1348       } else if (srcInferLoc.getSize() > (idx + 1) && dstInferLoc.getSize() > (idx + 1)) {
1349         recursivelyAddRelation(idx + 1, srcInferLoc, dstInferLoc);
1350       }
1351     } else {
1352       addRelationHigherToLower(getLattice(parentDesc), getLocationInfo(parentDesc), srcLocSymbol,
1353           dstLocSymbol);
1354     }
1355   }
1356
1357   private void recursivelyAddCompositeRelation(MethodDescriptor md, FlowGraph flowGraph,
1358       MethodLocationInfo methodInfo, FlowNode srcNode, FlowNode dstNode, Descriptor srcDesc,
1359       Descriptor dstDesc) throws CyclicFlowException {
1360
1361     CompositeLocation inferSrcLoc;
1362     CompositeLocation inferDstLoc = methodInfo.getInferLocation(dstDesc);
1363
1364     if (srcNode.getDescTuple().size() > 1) {
1365       // field access
1366       inferSrcLoc = new CompositeLocation();
1367
1368       NTuple<Location> locTuple = flowGraph.getLocationTuple(srcNode);
1369       for (int i = 0; i < locTuple.size(); i++) {
1370         inferSrcLoc.addLocation(locTuple.get(i));
1371       }
1372
1373     } else {
1374       inferSrcLoc = methodInfo.getInferLocation(srcDesc);
1375     }
1376
1377     if (dstNode.getDescTuple().size() > 1) {
1378       // field access
1379       inferDstLoc = new CompositeLocation();
1380
1381       NTuple<Location> locTuple = flowGraph.getLocationTuple(dstNode);
1382       for (int i = 0; i < locTuple.size(); i++) {
1383         inferDstLoc.addLocation(locTuple.get(i));
1384       }
1385
1386     } else {
1387       inferDstLoc = methodInfo.getInferLocation(dstDesc);
1388     }
1389
1390     recursiveAddRelationToLattice(1, md, inferSrcLoc, inferDstLoc);
1391   }
1392
1393   private void addPrefixMapping(Map<NTuple<Location>, Set<NTuple<Location>>> map,
1394       NTuple<Location> prefix, NTuple<Location> element) {
1395
1396     if (!map.containsKey(prefix)) {
1397       map.put(prefix, new HashSet<NTuple<Location>>());
1398     }
1399     map.get(prefix).add(element);
1400   }
1401
1402   private boolean calculateCompositeLocation(FlowGraph flowGraph,
1403       SSJavaLattice<String> methodLattice, MethodLocationInfo methodInfo, FlowNode flowNode)
1404       throws CyclicFlowException {
1405
1406     Descriptor localVarDesc = flowNode.getDescTuple().get(0);
1407     NTuple<Location> flowNodelocTuple = flowGraph.getLocationTuple(flowNode);
1408
1409     if (localVarDesc.equals(methodInfo.getMethodDesc())) {
1410       return false;
1411     }
1412
1413     Set<FlowNode> inNodeSet = flowGraph.getIncomingFlowNodeSet(flowNode);
1414     Set<FlowNode> reachableNodeSet = flowGraph.getReachableFlowNodeSet(flowNode);
1415
1416     Map<NTuple<Location>, Set<NTuple<Location>>> mapPrefixToIncomingLocTupleSet =
1417         new HashMap<NTuple<Location>, Set<NTuple<Location>>>();
1418
1419     List<NTuple<Location>> prefixList = new ArrayList<NTuple<Location>>();
1420
1421     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
1422       FlowNode inNode = (FlowNode) iterator.next();
1423       NTuple<Location> inNodeTuple = flowGraph.getLocationTuple(inNode);
1424
1425       CompositeLocation inNodeInferredLoc =
1426           generateInferredCompositeLocation(methodInfo, inNodeTuple);
1427
1428       NTuple<Location> inNodeInferredLocTuple = inNodeInferredLoc.getTuple();
1429
1430       for (int i = 1; i < inNodeInferredLocTuple.size(); i++) {
1431         NTuple<Location> prefix = inNodeInferredLocTuple.subList(0, i);
1432         if (!prefixList.contains(prefix)) {
1433           prefixList.add(prefix);
1434         }
1435         addPrefixMapping(mapPrefixToIncomingLocTupleSet, prefix, inNodeInferredLocTuple);
1436       }
1437     }
1438
1439     Collections.sort(prefixList, new Comparator<NTuple<Location>>() {
1440       public int compare(NTuple<Location> arg0, NTuple<Location> arg1) {
1441         int s0 = arg0.size();
1442         int s1 = arg1.size();
1443         if (s0 > s1) {
1444           return -1;
1445         } else if (s0 == s1) {
1446           return 0;
1447         } else {
1448           return 1;
1449         }
1450       }
1451     });
1452
1453     System.out.println("prefixList=" + prefixList);
1454     System.out.println("reachableNodeSet=" + reachableNodeSet);
1455
1456     // find out reachable nodes that have the longest common prefix
1457     for (int i = 0; i < prefixList.size(); i++) {
1458       NTuple<Location> curPrefix = prefixList.get(i);
1459       Set<NTuple<Location>> reachableCommonPrefixSet = new HashSet<NTuple<Location>>();
1460
1461       for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
1462         FlowNode reachableNode = (FlowNode) iterator2.next();
1463         NTuple<Location> reachLocTuple = flowGraph.getLocationTuple(reachableNode);
1464         CompositeLocation reachLocInferLoc =
1465             generateInferredCompositeLocation(methodInfo, reachLocTuple);
1466         if (reachLocInferLoc.getTuple().startsWith(curPrefix)) {
1467           reachableCommonPrefixSet.add(reachLocTuple);
1468         }
1469       }
1470
1471       if (!reachableCommonPrefixSet.isEmpty()) {
1472         // found reachable nodes that start with the prefix curPrefix
1473         // need to assign a composite location
1474
1475         // first, check if there are more than one the set of locations that has
1476         // the same length of the longest reachable prefix, no way to assign
1477         // a composite location to the input local var
1478         prefixSanityCheck(prefixList, i, flowGraph, reachableNodeSet);
1479
1480         Set<NTuple<Location>> incomingCommonPrefixSet =
1481             mapPrefixToIncomingLocTupleSet.get(curPrefix);
1482
1483         int idx = curPrefix.size();
1484         NTuple<Location> element = incomingCommonPrefixSet.iterator().next();
1485         Descriptor desc = element.get(idx).getDescriptor();
1486
1487         SSJavaLattice<String> lattice = getLattice(desc);
1488         LocationInfo locInfo = getLocationInfo(desc);
1489
1490         CompositeLocation inferLocation =
1491             generateInferredCompositeLocation(methodInfo, flowNodelocTuple);
1492
1493         // methodInfo.getInferLocation(localVarDesc);
1494         CompositeLocation newInferLocation = new CompositeLocation();
1495
1496         if (inferLocation.getTuple().startsWith(curPrefix)) {
1497           // the same infer location is already existed. no need to do
1498           // anything
1499           System.out.println("NO ATTEMPT TO HAVE A COMPOSITE LOCATION curPrefix=" + curPrefix);
1500           return true;
1501         } else {
1502           // assign a new composite location
1503
1504           // String oldMethodLocationSymbol =
1505           // inferLocation.get(0).getLocIdentifier();
1506           String newLocSymbol = "Loc" + (SSJavaLattice.seed++);
1507           for (int locIdx = 0; locIdx < curPrefix.size(); locIdx++) {
1508             newInferLocation.addLocation(curPrefix.get(locIdx));
1509           }
1510           Location newLocationElement = new Location(desc, newLocSymbol);
1511           newInferLocation.addLocation(newLocationElement);
1512
1513           // maps local variable to location types of the common prefix
1514           methodInfo.mapDescriptorToLocation(localVarDesc, newInferLocation.clone());
1515
1516           // methodInfo.mapDescriptorToLocation(localVarDesc, newInferLocation);
1517           addMapLocSymbolToInferredLocation(methodInfo.getMethodDesc(), localVarDesc,
1518               newInferLocation);
1519           methodInfo.removeMaplocalVarToLocSet(localVarDesc);
1520
1521           // add the field/var descriptor to the set of the location symbol
1522           int lastIdx = flowNode.getDescTuple().size() - 1;
1523           Descriptor lastFlowNodeDesc = flowNode.getDescTuple().get(lastIdx);
1524           Descriptor enclosinglastLastFlowNodeDesc = flowNodelocTuple.get(lastIdx).getDescriptor();
1525
1526           CompositeLocation newlyInferredLocForFlowNode =
1527               generateInferredCompositeLocation(methodInfo, flowNodelocTuple);
1528           Location lastInferLocElement =
1529               newlyInferredLocForFlowNode.get(newlyInferredLocForFlowNode.getSize() - 1);
1530           Descriptor enclosingLastInferLocElement = lastInferLocElement.getDescriptor();
1531
1532           // getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToDescSet(
1533           // lastInferLocElement.getLocIdentifier(), lastFlowNodeDesc);
1534           getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToRelatedInferLoc(
1535               lastInferLocElement.getLocIdentifier(), enclosinglastLastFlowNodeDesc,
1536               lastFlowNodeDesc);
1537
1538           // clean up the previous location
1539           // Location prevInferLocElement =
1540           // inferLocation.get(inferLocation.getSize() - 1);
1541           // Descriptor prevEnclosingDesc = prevInferLocElement.getDescriptor();
1542           //
1543           // SSJavaLattice<String> targetLattice;
1544           // LocationInfo targetInfo;
1545           // if (prevEnclosingDesc.equals(methodInfo.getMethodDesc())) {
1546           // targetLattice = methodLattice;
1547           // targetInfo = methodInfo;
1548           // } else {
1549           // targetLattice = getLattice(prevInferLocElement.getDescriptor());
1550           // targetInfo = getLocationInfo(prevInferLocElement.getDescriptor());
1551           // }
1552           //
1553           // Set<Pair<Descriptor, Descriptor>> associstedDescSet =
1554           // targetInfo.getRelatedInferLocSet(prevInferLocElement.getLocIdentifier());
1555           //
1556           // if (associstedDescSet.size() == 1) {
1557           // targetLattice.remove(prevInferLocElement.getLocIdentifier());
1558           // } else {
1559           // associstedDescSet.remove(lastFlowNodeDesc);
1560           // }
1561
1562         }
1563
1564         System.out.println("curPrefix=" + curPrefix);
1565         System.out.println("ASSIGN NEW COMPOSITE LOCATION =" + newInferLocation + "    to "
1566             + flowNode);
1567
1568         String newlyInsertedLocName =
1569             newInferLocation.get(newInferLocation.getSize() - 1).getLocIdentifier();
1570
1571         System.out.println("-- add in-flow");
1572         for (Iterator iterator = incomingCommonPrefixSet.iterator(); iterator.hasNext();) {
1573           NTuple<Location> tuple = (NTuple<Location>) iterator.next();
1574           Location loc = tuple.get(idx);
1575           String higher = loc.getLocIdentifier();
1576           addRelationHigherToLower(lattice, locInfo, higher, newlyInsertedLocName);
1577         }
1578
1579         System.out.println("-- add out flow");
1580         for (Iterator iterator = reachableCommonPrefixSet.iterator(); iterator.hasNext();) {
1581           NTuple<Location> tuple = (NTuple<Location>) iterator.next();
1582           if (tuple.size() > idx) {
1583             Location loc = tuple.get(idx);
1584             String lower = loc.getLocIdentifier();
1585             // String lower =
1586             // locInfo.getFieldInferLocation(loc.getLocDescriptor()).getLocIdentifier();
1587             addRelationHigherToLower(lattice, locInfo, newlyInsertedLocName, lower);
1588           }
1589         }
1590
1591         return true;
1592       }
1593
1594     }
1595
1596     return false;
1597
1598   }
1599
1600   private void addMapLocSymbolToInferredLocation(MethodDescriptor md, Descriptor localVar,
1601       CompositeLocation inferLoc) {
1602
1603     Location locElement = inferLoc.get((inferLoc.getSize() - 1));
1604     Descriptor enclosingDesc = locElement.getDescriptor();
1605     LocationInfo locInfo = getLocationInfo(enclosingDesc);
1606     locInfo.addMapLocSymbolToRelatedInferLoc(locElement.getLocIdentifier(), md, localVar);
1607   }
1608
1609   private boolean isCompositeLocation(CompositeLocation cl) {
1610     return cl.getSize() > 1;
1611   }
1612
1613   private boolean containsNonPrimitiveElement(Set<Descriptor> descSet) {
1614     for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
1615       Descriptor desc = (Descriptor) iterator.next();
1616
1617       if (desc.equals(LocationInference.GLOBALDESC)) {
1618         return true;
1619       } else if (desc instanceof VarDescriptor) {
1620         if (!((VarDescriptor) desc).getType().isPrimitive()) {
1621           return true;
1622         }
1623       } else if (desc instanceof FieldDescriptor) {
1624         if (!((FieldDescriptor) desc).getType().isPrimitive()) {
1625           return true;
1626         }
1627       }
1628
1629     }
1630     return false;
1631   }
1632
1633   private void addRelationHigherToLower(SSJavaLattice<String> lattice, LocationInfo locInfo,
1634       String higher, String lower) throws CyclicFlowException {
1635
1636     System.out.println("---addRelationHigherToLower " + higher + " -> " + lower
1637         + " to the lattice of " + locInfo.getDescIdentifier());
1638     // if (higher.equals(lower) && lattice.isSharedLoc(higher)) {
1639     // return;
1640     // }
1641     Set<String> cycleElementSet = lattice.getPossibleCycleElements(higher, lower);
1642
1643     boolean hasNonPrimitiveElement = false;
1644     for (Iterator iterator = cycleElementSet.iterator(); iterator.hasNext();) {
1645       String cycleElementLocSymbol = (String) iterator.next();
1646
1647       Set<Descriptor> descSet = locInfo.getDescSet(cycleElementLocSymbol);
1648       if (containsNonPrimitiveElement(descSet)) {
1649         hasNonPrimitiveElement = true;
1650         break;
1651       }
1652     }
1653
1654     if (hasNonPrimitiveElement) {
1655       System.out.println("#Check cycle= " + lower + " < " + higher + "     cycleElementSet="
1656           + cycleElementSet);
1657       // if there is non-primitive element in the cycle, no way to merge cyclic
1658       // elements into the shared location
1659       throw new CyclicFlowException();
1660     }
1661
1662     if (cycleElementSet.size() > 0) {
1663
1664       String newSharedLoc = "SharedLoc" + (SSJavaLattice.seed++);
1665
1666       System.out.println("---ASSIGN NEW SHARED LOC=" + newSharedLoc + "   to  " + cycleElementSet);
1667       lattice.mergeIntoSharedLocation(cycleElementSet, newSharedLoc);
1668
1669       for (Iterator iterator = cycleElementSet.iterator(); iterator.hasNext();) {
1670         String oldLocSymbol = (String) iterator.next();
1671
1672         Set<Pair<Descriptor, Descriptor>> inferLocSet = locInfo.getRelatedInferLocSet(oldLocSymbol);
1673         System.out.println("---update related locations=" + inferLocSet);
1674         for (Iterator iterator2 = inferLocSet.iterator(); iterator2.hasNext();) {
1675           Pair<Descriptor, Descriptor> pair = (Pair<Descriptor, Descriptor>) iterator2.next();
1676           Descriptor enclosingDesc = pair.getFirst();
1677           Descriptor desc = pair.getSecond();
1678
1679           CompositeLocation inferLoc;
1680           if (curMethodInfo.md.equals(enclosingDesc)) {
1681             inferLoc = curMethodInfo.getInferLocation(desc);
1682           } else {
1683             inferLoc = getLocationInfo(enclosingDesc).getInferLocation(desc);
1684           }
1685
1686           Location locElement = inferLoc.get(inferLoc.getSize() - 1);
1687
1688           locElement.setLocIdentifier(newSharedLoc);
1689           locInfo.addMapLocSymbolToRelatedInferLoc(newSharedLoc, enclosingDesc, desc);
1690
1691           if (curMethodInfo.md.equals(enclosingDesc)) {
1692             inferLoc = curMethodInfo.getInferLocation(desc);
1693           } else {
1694             inferLoc = getLocationInfo(enclosingDesc).getInferLocation(desc);
1695           }
1696           System.out.println("---New Infer Loc=" + inferLoc);
1697
1698         }
1699         locInfo.removeRelatedInferLocSet(oldLocSymbol, newSharedLoc);
1700
1701       }
1702
1703       lattice.addSharedLoc(newSharedLoc);
1704
1705     } else if (!lattice.isGreaterThan(higher, lower)) {
1706       lattice.addRelationHigherToLower(higher, lower);
1707     }
1708   }
1709
1710   private void replaceOldLocWithNewLoc(SSJavaLattice<String> methodLattice, String oldLocSymbol,
1711       String newLocSymbol) {
1712
1713     if (methodLattice.containsKey(oldLocSymbol)) {
1714       methodLattice.substituteLocation(oldLocSymbol, newLocSymbol);
1715     }
1716
1717   }
1718
1719   private void prefixSanityCheck(List<NTuple<Location>> prefixList, int curIdx,
1720       FlowGraph flowGraph, Set<FlowNode> reachableNodeSet) {
1721
1722     NTuple<Location> curPrefix = prefixList.get(curIdx);
1723
1724     for (int i = curIdx + 1; i < prefixList.size(); i++) {
1725       NTuple<Location> prefixTuple = prefixList.get(i);
1726
1727       if (curPrefix.startsWith(prefixTuple)) {
1728         continue;
1729       }
1730
1731       for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
1732         FlowNode reachableNode = (FlowNode) iterator2.next();
1733         NTuple<Location> reachLocTuple = flowGraph.getLocationTuple(reachableNode);
1734         if (reachLocTuple.startsWith(prefixTuple)) {
1735           // TODO
1736           throw new Error("Failed to generate a composite location");
1737         }
1738       }
1739     }
1740   }
1741
1742   public boolean isPrimitiveLocalVariable(FlowNode node) {
1743     VarDescriptor varDesc = (VarDescriptor) node.getDescTuple().get(0);
1744     return varDesc.getType().isPrimitive();
1745   }
1746
1747   private SSJavaLattice<String> getLattice(Descriptor d) {
1748     if (d instanceof MethodDescriptor) {
1749       return getMethodLattice((MethodDescriptor) d);
1750     } else {
1751       return getFieldLattice((ClassDescriptor) d);
1752     }
1753   }
1754
1755   private SSJavaLattice<String> getMethodLattice(MethodDescriptor md) {
1756     if (!md2lattice.containsKey(md)) {
1757       md2lattice.put(md, new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM));
1758     }
1759     return md2lattice.get(md);
1760   }
1761
1762   private void setMethodLattice(MethodDescriptor md, SSJavaLattice<String> lattice) {
1763     md2lattice.put(md, lattice);
1764   }
1765
1766   private void extractRelationFromFieldFlows(ClassDescriptor cd, FlowNode srcNode,
1767       FlowNode dstNode, int idx) throws CyclicFlowException {
1768
1769     if (srcNode.getDescTuple().get(idx).equals(dstNode.getDescTuple().get(idx))
1770         && srcNode.getDescTuple().size() > (idx + 1) && dstNode.getDescTuple().size() > (idx + 1)) {
1771       // value flow between fields: we don't need to add a binary relation
1772       // for this case
1773
1774       Descriptor desc = srcNode.getDescTuple().get(idx);
1775       ClassDescriptor classDesc;
1776
1777       if (idx == 0) {
1778         classDesc = ((VarDescriptor) desc).getType().getClassDesc();
1779       } else {
1780         classDesc = ((FieldDescriptor) desc).getType().getClassDesc();
1781       }
1782
1783       extractRelationFromFieldFlows(classDesc, srcNode, dstNode, idx + 1);
1784
1785     } else {
1786
1787       Descriptor srcFieldDesc = srcNode.getDescTuple().get(idx);
1788       Descriptor dstFieldDesc = dstNode.getDescTuple().get(idx);
1789
1790       // add a new binary relation of dstNode < srcNode
1791       SSJavaLattice<String> fieldLattice = getFieldLattice(cd);
1792       LocationInfo fieldInfo = getFieldLocationInfo(cd);
1793
1794       String srcSymbol = fieldInfo.getFieldInferLocation(srcFieldDesc).getLocIdentifier();
1795       String dstSymbol = fieldInfo.getFieldInferLocation(dstFieldDesc).getLocIdentifier();
1796
1797       addRelationHigherToLower(fieldLattice, fieldInfo, srcSymbol, dstSymbol);
1798
1799     }
1800
1801   }
1802
1803   public SSJavaLattice<String> getFieldLattice(ClassDescriptor cd) {
1804     if (!cd2lattice.containsKey(cd)) {
1805       cd2lattice.put(cd, new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM));
1806     }
1807     return cd2lattice.get(cd);
1808   }
1809
1810   public LinkedList<MethodDescriptor> computeMethodList() {
1811
1812     Set<MethodDescriptor> toSort = new HashSet<MethodDescriptor>();
1813
1814     setupToAnalyze();
1815
1816     Set<MethodDescriptor> visited = new HashSet<MethodDescriptor>();
1817     Set<MethodDescriptor> reachableCallee = new HashSet<MethodDescriptor>();
1818
1819     while (!toAnalyzeIsEmpty()) {
1820       ClassDescriptor cd = toAnalyzeNext();
1821
1822       setupToAnalazeMethod(cd);
1823       toanalyzeMethodList.removeAll(visited);
1824
1825       while (!toAnalyzeMethodIsEmpty()) {
1826         MethodDescriptor md = toAnalyzeMethodNext();
1827         if ((!visited.contains(md))
1828             && (ssjava.needTobeAnnotated(md) || reachableCallee.contains(md))) {
1829
1830           // creates a mapping from a method descriptor to virtual methods
1831           Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
1832           if (md.isStatic()) {
1833             setPossibleCallees.add(md);
1834           } else {
1835             setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md));
1836           }
1837
1838           Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getCalleeSet(md);
1839           Set<MethodDescriptor> needToAnalyzeCalleeSet = new HashSet<MethodDescriptor>();
1840
1841           for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) {
1842             MethodDescriptor calleemd = (MethodDescriptor) iterator.next();
1843             if ((!ssjava.isTrustMethod(calleemd))
1844                 && (!ssjava.isSSJavaUtil(calleemd.getClassDesc()))) {
1845               if (!visited.contains(calleemd)) {
1846                 toanalyzeMethodList.add(calleemd);
1847               }
1848               reachableCallee.add(calleemd);
1849               needToAnalyzeCalleeSet.add(calleemd);
1850             }
1851           }
1852
1853           mapMethodToCalleeSet.put(md, needToAnalyzeCalleeSet);
1854
1855           visited.add(md);
1856
1857           toSort.add(md);
1858         }
1859       }
1860     }
1861
1862     return ssjava.topologicalSort(toSort);
1863
1864   }
1865
1866   public void constructFlowGraph() {
1867
1868     LinkedList<MethodDescriptor> methodDescList = computeMethodList();
1869
1870     while (!methodDescList.isEmpty()) {
1871       MethodDescriptor md = methodDescList.removeLast();
1872       if (state.SSJAVADEBUG) {
1873         System.out.println();
1874         System.out.println("SSJAVA: Constructing a flow graph: " + md);
1875
1876         // creates a mapping from a parameter descriptor to its index
1877         Map<Descriptor, Integer> mapParamDescToIdx = new HashMap<Descriptor, Integer>();
1878         int offset = 0;
1879         if (!md.isStatic()) {
1880           offset = 1;
1881           mapParamDescToIdx.put(md.getThis(), 0);
1882         }
1883
1884         for (int i = 0; i < md.numParameters(); i++) {
1885           Descriptor paramDesc = (Descriptor) md.getParameter(i);
1886           mapParamDescToIdx.put(paramDesc, new Integer(i + offset));
1887         }
1888
1889         FlowGraph fg = new FlowGraph(md, mapParamDescToIdx);
1890         mapMethodDescriptorToFlowGraph.put(md, fg);
1891
1892         analyzeMethodBody(md.getClassDesc(), md);
1893       }
1894     }
1895     _debug_printGraph();
1896
1897   }
1898
1899   private void analyzeMethodBody(ClassDescriptor cd, MethodDescriptor md) {
1900     BlockNode bn = state.getMethodBody(md);
1901     NodeTupleSet implicitFlowTupleSet = new NodeTupleSet();
1902     analyzeFlowBlockNode(md, md.getParameterTable(), bn, implicitFlowTupleSet);
1903   }
1904
1905   private void analyzeFlowBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn,
1906       NodeTupleSet implicitFlowTupleSet) {
1907
1908     bn.getVarTable().setParent(nametable);
1909     for (int i = 0; i < bn.size(); i++) {
1910       BlockStatementNode bsn = bn.get(i);
1911       analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet);
1912     }
1913
1914   }
1915
1916   private void analyzeBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
1917       BlockStatementNode bsn, NodeTupleSet implicitFlowTupleSet) {
1918
1919     switch (bsn.kind()) {
1920     case Kind.BlockExpressionNode:
1921       analyzeBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn, implicitFlowTupleSet);
1922       break;
1923
1924     case Kind.DeclarationNode:
1925       analyzeFlowDeclarationNode(md, nametable, (DeclarationNode) bsn, implicitFlowTupleSet);
1926       break;
1927
1928     case Kind.IfStatementNode:
1929       analyzeFlowIfStatementNode(md, nametable, (IfStatementNode) bsn, implicitFlowTupleSet);
1930       break;
1931
1932     case Kind.LoopNode:
1933       analyzeFlowLoopNode(md, nametable, (LoopNode) bsn, implicitFlowTupleSet);
1934       break;
1935
1936     case Kind.ReturnNode:
1937       analyzeFlowReturnNode(md, nametable, (ReturnNode) bsn, implicitFlowTupleSet);
1938       break;
1939
1940     case Kind.SubBlockNode:
1941       analyzeFlowSubBlockNode(md, nametable, (SubBlockNode) bsn, implicitFlowTupleSet);
1942       break;
1943
1944     case Kind.ContinueBreakNode:
1945       break;
1946
1947     case Kind.SwitchStatementNode:
1948       analyzeSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn);
1949       break;
1950
1951     }
1952
1953   }
1954
1955   private void analyzeSwitchStatementNode(MethodDescriptor md, SymbolTable nametable,
1956       SwitchStatementNode bsn) {
1957     // TODO Auto-generated method stub
1958   }
1959
1960   private void analyzeFlowSubBlockNode(MethodDescriptor md, SymbolTable nametable,
1961       SubBlockNode sbn, NodeTupleSet implicitFlowTupleSet) {
1962     analyzeFlowBlockNode(md, nametable, sbn.getBlockNode(), implicitFlowTupleSet);
1963   }
1964
1965   private void analyzeFlowReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode rn,
1966       NodeTupleSet implicitFlowTupleSet) {
1967
1968     ExpressionNode returnExp = rn.getReturnExpression();
1969
1970     if (returnExp != null) {
1971       NodeTupleSet nodeSet = new NodeTupleSet();
1972       analyzeFlowExpressionNode(md, nametable, returnExp, nodeSet, false);
1973
1974       FlowGraph fg = getFlowGraph(md);
1975
1976       // annotate the elements of the node set as the return location
1977       for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1978         NTuple<Descriptor> returnDescTuple = (NTuple<Descriptor>) iterator.next();
1979         fg.addReturnFlowNode(returnDescTuple);
1980         for (Iterator iterator2 = implicitFlowTupleSet.iterator(); iterator2.hasNext();) {
1981           NTuple<Descriptor> implicitFlowDescTuple = (NTuple<Descriptor>) iterator2.next();
1982           fg.addValueFlowEdge(implicitFlowDescTuple, returnDescTuple);
1983         }
1984       }
1985     }
1986
1987   }
1988
1989   private void analyzeFlowLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln,
1990       NodeTupleSet implicitFlowTupleSet) {
1991
1992     if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) {
1993
1994       NodeTupleSet condTupleNode = new NodeTupleSet();
1995       analyzeFlowExpressionNode(md, nametable, ln.getCondition(), condTupleNode, null,
1996           implicitFlowTupleSet, false);
1997       condTupleNode.addTupleSet(implicitFlowTupleSet);
1998
1999       // add edges from condNodeTupleSet to all nodes of conditional nodes
2000       analyzeFlowBlockNode(md, nametable, ln.getBody(), condTupleNode);
2001
2002     } else {
2003       // check 'for loop' case
2004       BlockNode bn = ln.getInitializer();
2005       bn.getVarTable().setParent(nametable);
2006       for (int i = 0; i < bn.size(); i++) {
2007         BlockStatementNode bsn = bn.get(i);
2008         analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet);
2009       }
2010
2011       NodeTupleSet condTupleNode = new NodeTupleSet();
2012       analyzeFlowExpressionNode(md, bn.getVarTable(), ln.getCondition(), condTupleNode, null,
2013           implicitFlowTupleSet, false);
2014       condTupleNode.addTupleSet(implicitFlowTupleSet);
2015
2016       analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(), condTupleNode);
2017       analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(), condTupleNode);
2018
2019     }
2020
2021   }
2022
2023   private void analyzeFlowIfStatementNode(MethodDescriptor md, SymbolTable nametable,
2024       IfStatementNode isn, NodeTupleSet implicitFlowTupleSet) {
2025
2026     NodeTupleSet condTupleNode = new NodeTupleSet();
2027     analyzeFlowExpressionNode(md, nametable, isn.getCondition(), condTupleNode, null,
2028         implicitFlowTupleSet, false);
2029
2030     // add edges from condNodeTupleSet to all nodes of conditional nodes
2031     condTupleNode.addTupleSet(implicitFlowTupleSet);
2032     analyzeFlowBlockNode(md, nametable, isn.getTrueBlock(), condTupleNode);
2033
2034     if (isn.getFalseBlock() != null) {
2035       analyzeFlowBlockNode(md, nametable, isn.getFalseBlock(), condTupleNode);
2036     }
2037
2038   }
2039
2040   private void analyzeFlowDeclarationNode(MethodDescriptor md, SymbolTable nametable,
2041       DeclarationNode dn, NodeTupleSet implicitFlowTupleSet) {
2042
2043     VarDescriptor vd = dn.getVarDescriptor();
2044     mapDescToDefinitionLine.put(vd, dn.getNumLine());
2045     NTuple<Descriptor> tupleLHS = new NTuple<Descriptor>();
2046     tupleLHS.add(vd);
2047     FlowNode fn = getFlowGraph(md).createNewFlowNode(tupleLHS);
2048     fn.setDeclarationNode();
2049
2050     if (dn.getExpression() != null) {
2051
2052       NodeTupleSet tupleSetRHS = new NodeTupleSet();
2053       analyzeFlowExpressionNode(md, nametable, dn.getExpression(), tupleSetRHS, null,
2054           implicitFlowTupleSet, false);
2055
2056       // add a new flow edge from rhs to lhs
2057       for (Iterator<NTuple<Descriptor>> iter = tupleSetRHS.iterator(); iter.hasNext();) {
2058         NTuple<Descriptor> from = iter.next();
2059         addFlowGraphEdge(md, from, tupleLHS);
2060       }
2061
2062     }
2063
2064   }
2065
2066   private void analyzeBlockExpressionNode(MethodDescriptor md, SymbolTable nametable,
2067       BlockExpressionNode ben, NodeTupleSet implicitFlowTupleSet) {
2068     analyzeFlowExpressionNode(md, nametable, ben.getExpression(), null, null, implicitFlowTupleSet,
2069         false);
2070   }
2071
2072   private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
2073       ExpressionNode en, NodeTupleSet nodeSet, boolean isLHS) {
2074     return analyzeFlowExpressionNode(md, nametable, en, nodeSet, null, new NodeTupleSet(), isLHS);
2075   }
2076
2077   private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
2078       ExpressionNode en, NodeTupleSet nodeSet, NTuple<Descriptor> base,
2079       NodeTupleSet implicitFlowTupleSet, boolean isLHS) {
2080
2081     // note that expression node can create more than one flow node
2082     // nodeSet contains of flow nodes
2083     // base is always assigned to null except the case of a name node!
2084
2085     NTuple<Descriptor> flowTuple;
2086
2087     switch (en.kind()) {
2088
2089     case Kind.AssignmentNode:
2090       analyzeFlowAssignmentNode(md, nametable, (AssignmentNode) en, nodeSet, base,
2091           implicitFlowTupleSet);
2092       break;
2093
2094     case Kind.FieldAccessNode:
2095       flowTuple =
2096           analyzeFlowFieldAccessNode(md, nametable, (FieldAccessNode) en, nodeSet, base,
2097               implicitFlowTupleSet, isLHS);
2098       if (flowTuple != null) {
2099         nodeSet.addTuple(flowTuple);
2100       }
2101       return flowTuple;
2102
2103     case Kind.NameNode:
2104       NodeTupleSet nameNodeSet = new NodeTupleSet();
2105       flowTuple =
2106           analyzeFlowNameNode(md, nametable, (NameNode) en, nameNodeSet, base, implicitFlowTupleSet);
2107       if (flowTuple != null) {
2108         nodeSet.addTuple(flowTuple);
2109       }
2110       return flowTuple;
2111
2112     case Kind.OpNode:
2113       analyzeFlowOpNode(md, nametable, (OpNode) en, nodeSet, implicitFlowTupleSet);
2114       break;
2115
2116     case Kind.CreateObjectNode:
2117       analyzeCreateObjectNode(md, nametable, (CreateObjectNode) en);
2118       break;
2119
2120     case Kind.ArrayAccessNode:
2121       analyzeFlowArrayAccessNode(md, nametable, (ArrayAccessNode) en, nodeSet, isLHS);
2122       break;
2123
2124     case Kind.LiteralNode:
2125       analyzeLiteralNode(md, nametable, (LiteralNode) en);
2126       break;
2127
2128     case Kind.MethodInvokeNode:
2129       analyzeFlowMethodInvokeNode(md, nametable, (MethodInvokeNode) en, nodeSet,
2130           implicitFlowTupleSet);
2131       break;
2132
2133     case Kind.TertiaryNode:
2134       analyzeFlowTertiaryNode(md, nametable, (TertiaryNode) en, nodeSet, implicitFlowTupleSet);
2135       break;
2136
2137     case Kind.CastNode:
2138       analyzeFlowCastNode(md, nametable, (CastNode) en, nodeSet, base, implicitFlowTupleSet);
2139       break;
2140     // case Kind.InstanceOfNode:
2141     // checkInstanceOfNode(md, nametable, (InstanceOfNode) en, td);
2142     // return null;
2143
2144     // case Kind.ArrayInitializerNode:
2145     // checkArrayInitializerNode(md, nametable, (ArrayInitializerNode) en,
2146     // td);
2147     // return null;
2148
2149     // case Kind.ClassTypeNode:
2150     // checkClassTypeNode(md, nametable, (ClassTypeNode) en, td);
2151     // return null;
2152
2153     // case Kind.OffsetNode:
2154     // checkOffsetNode(md, nametable, (OffsetNode)en, td);
2155     // return null;
2156
2157     }
2158     return null;
2159
2160   }
2161
2162   private void analyzeFlowCastNode(MethodDescriptor md, SymbolTable nametable, CastNode cn,
2163       NodeTupleSet nodeSet, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
2164
2165     analyzeFlowExpressionNode(md, nametable, cn.getExpression(), nodeSet, base,
2166         implicitFlowTupleSet, false);
2167
2168   }
2169
2170   private void analyzeFlowTertiaryNode(MethodDescriptor md, SymbolTable nametable, TertiaryNode tn,
2171       NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
2172
2173     NodeTupleSet tertiaryTupleNode = new NodeTupleSet();
2174     analyzeFlowExpressionNode(md, nametable, tn.getCond(), tertiaryTupleNode, null,
2175         implicitFlowTupleSet, false);
2176
2177     // add edges from tertiaryTupleNode to all nodes of conditional nodes
2178     tertiaryTupleNode.addTupleSet(implicitFlowTupleSet);
2179     analyzeFlowExpressionNode(md, nametable, tn.getTrueExpr(), tertiaryTupleNode, null,
2180         implicitFlowTupleSet, false);
2181
2182     analyzeFlowExpressionNode(md, nametable, tn.getFalseExpr(), tertiaryTupleNode, null,
2183         implicitFlowTupleSet, false);
2184
2185     nodeSet.addTupleSet(tertiaryTupleNode);
2186
2187   }
2188
2189   private void addMapCallerMethodDescToMethodInvokeNodeSet(MethodDescriptor caller,
2190       MethodInvokeNode min) {
2191     Set<MethodInvokeNode> set = mapMethodDescriptorToMethodInvokeNodeSet.get(caller);
2192     if (set == null) {
2193       set = new HashSet<MethodInvokeNode>();
2194       mapMethodDescriptorToMethodInvokeNodeSet.put(caller, set);
2195     }
2196     set.add(min);
2197   }
2198
2199   private void addParamNodeFlowingToReturnValue(MethodDescriptor md, FlowNode fn) {
2200
2201     if (!mapMethodDescToParamNodeFlowsToReturnValue.containsKey(md)) {
2202       mapMethodDescToParamNodeFlowsToReturnValue.put(md, new HashSet<FlowNode>());
2203     }
2204     mapMethodDescToParamNodeFlowsToReturnValue.get(md).add(fn);
2205   }
2206
2207   private Set<FlowNode> getParamNodeFlowingToReturnValue(MethodDescriptor md) {
2208     return mapMethodDescToParamNodeFlowsToReturnValue.get(md);
2209   }
2210
2211   private void analyzeFlowMethodInvokeNode(MethodDescriptor md, SymbolTable nametable,
2212       MethodInvokeNode min, NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
2213
2214     System.out.println("analyzeFlowMethodInvokeNode=" + min.printNode(0));
2215
2216     if (nodeSet == null) {
2217       nodeSet = new NodeTupleSet();
2218     }
2219
2220     addMapCallerMethodDescToMethodInvokeNodeSet(md, min);
2221
2222     MethodDescriptor calleeMethodDesc = min.getMethod();
2223
2224     NameDescriptor baseName = min.getBaseName();
2225     boolean isSystemout = false;
2226     if (baseName != null) {
2227       isSystemout = baseName.getSymbol().equals("System.out");
2228     }
2229
2230     if (!ssjava.isSSJavaUtil(calleeMethodDesc.getClassDesc())
2231         && !ssjava.isTrustMethod(calleeMethodDesc) && !calleeMethodDesc.getModifiers().isNative()
2232         && !isSystemout) {
2233
2234       FlowGraph calleeFlowGraph = getFlowGraph(calleeMethodDesc);
2235       Set<FlowNode> calleeReturnSet = calleeFlowGraph.getReturnNodeSet();
2236
2237       if (min.getExpression() != null) {
2238
2239         NodeTupleSet baseNodeSet = new NodeTupleSet();
2240         analyzeFlowExpressionNode(md, nametable, min.getExpression(), baseNodeSet, null,
2241             implicitFlowTupleSet, false);
2242
2243         if (!min.getMethod().isStatic()) {
2244           addArgIdxMap(min, 0, baseNodeSet);
2245           // System.out.println("arg idx=0  argTupleSet=" + baseNodeSet);
2246
2247           for (Iterator iterator = calleeReturnSet.iterator(); iterator.hasNext();) {
2248             FlowNode returnNode = (FlowNode) iterator.next();
2249             NTuple<Descriptor> returnDescTuple = returnNode.getDescTuple();
2250             if (returnDescTuple.startsWith(calleeMethodDesc.getThis())) {
2251               // the location type of the return value is started with 'this'
2252               // reference
2253               for (Iterator<NTuple<Descriptor>> baseIter = baseNodeSet.iterator(); baseIter
2254                   .hasNext();) {
2255                 NTuple<Descriptor> baseTuple = baseIter.next();
2256                 NTuple<Descriptor> inFlowTuple = new NTuple<Descriptor>(baseTuple.getList());
2257                 inFlowTuple.addAll(returnDescTuple.subList(1, returnDescTuple.size()));
2258                 nodeSet.addTuple(inFlowTuple);
2259               }
2260             } else {
2261               Set<FlowNode> inFlowSet = calleeFlowGraph.getIncomingFlowNodeSet(returnNode);
2262               for (Iterator iterator2 = inFlowSet.iterator(); iterator2.hasNext();) {
2263                 FlowNode inFlowNode = (FlowNode) iterator2.next();
2264                 if (inFlowNode.getDescTuple().startsWith(calleeMethodDesc.getThis())) {
2265                   nodeSet.addTupleSet(baseNodeSet);
2266                 }
2267               }
2268             }
2269           }
2270         }
2271       }
2272
2273       // analyze parameter flows
2274
2275       if (min.numArgs() > 0) {
2276
2277         int offset;
2278         if (min.getMethod().isStatic()) {
2279           offset = 0;
2280         } else {
2281           offset = 1;
2282         }
2283
2284         for (int i = 0; i < min.numArgs(); i++) {
2285           ExpressionNode en = min.getArg(i);
2286           int idx = i + offset;
2287           NodeTupleSet argTupleSet = new NodeTupleSet();
2288           analyzeFlowExpressionNode(calleeMethodDesc, nametable, en, argTupleSet, false);
2289           // if argument is liternal node, argTuple is set to NULL.
2290           addArgIdxMap(min, idx, argTupleSet);
2291           // System.out.println("arg idx=" + (idx) + "  argTupleSet=" +
2292           // argTupleSet);
2293           FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx);
2294           if (hasInFlowTo(calleeFlowGraph, paramNode, calleeReturnSet)) {
2295             addParamNodeFlowingToReturnValue(calleeMethodDesc, paramNode);
2296             nodeSet.addTupleSet(argTupleSet);
2297           }
2298         }
2299
2300       }
2301
2302     }
2303
2304   }
2305
2306   private boolean hasInFlowTo(FlowGraph fg, FlowNode inNode, Set<FlowNode> nodeSet) {
2307     // return true if inNode has in-flows to nodeSet
2308     Set<FlowNode> reachableSet = fg.getReachableFlowNodeSet(inNode);
2309     for (Iterator iterator = reachableSet.iterator(); iterator.hasNext();) {
2310       FlowNode fn = (FlowNode) iterator.next();
2311       if (nodeSet.contains(fn)) {
2312         return true;
2313       }
2314     }
2315     return false;
2316   }
2317
2318   private NodeTupleSet getNodeTupleSetByArgIdx(MethodInvokeNode min, int idx) {
2319     return mapMethodInvokeNodeToArgIdxMap.get(min).get(new Integer(idx));
2320   }
2321
2322   private void addArgIdxMap(MethodInvokeNode min, int idx, NodeTupleSet tupleSet) {
2323     Map<Integer, NodeTupleSet> mapIdxToTupleSet = mapMethodInvokeNodeToArgIdxMap.get(min);
2324     if (mapIdxToTupleSet == null) {
2325       mapIdxToTupleSet = new HashMap<Integer, NodeTupleSet>();
2326       mapMethodInvokeNodeToArgIdxMap.put(min, mapIdxToTupleSet);
2327     }
2328     mapIdxToTupleSet.put(new Integer(idx), tupleSet);
2329   }
2330
2331   private void analyzeFlowMethodParameters(MethodDescriptor callermd, SymbolTable nametable,
2332       MethodInvokeNode min, NodeTupleSet nodeSet) {
2333
2334     if (min.numArgs() > 0) {
2335
2336       int offset;
2337       if (min.getMethod().isStatic()) {
2338         offset = 0;
2339       } else {
2340         offset = 1;
2341         // NTuple<Descriptor> thisArgTuple = new NTuple<Descriptor>();
2342         // thisArgTuple.add(callermd.getThis());
2343         // NodeTupleSet argTupleSet = new NodeTupleSet();
2344         // argTupleSet.addTuple(thisArgTuple);
2345         // addArgIdxMap(min, 0, argTupleSet);
2346         // nodeSet.addTuple(thisArgTuple);
2347       }
2348
2349       for (int i = 0; i < min.numArgs(); i++) {
2350         ExpressionNode en = min.getArg(i);
2351         NodeTupleSet argTupleSet = new NodeTupleSet();
2352         analyzeFlowExpressionNode(callermd, nametable, en, argTupleSet, false);
2353         // if argument is liternal node, argTuple is set to NULL.
2354         addArgIdxMap(min, i + offset, argTupleSet);
2355         System.out.println("arg idx=" + (i + offset) + "  argTupleSet=" + argTupleSet);
2356         nodeSet.addTupleSet(argTupleSet);
2357       }
2358
2359     }
2360
2361   }
2362
2363   private void analyzeLiteralNode(MethodDescriptor md, SymbolTable nametable, LiteralNode en) {
2364
2365   }
2366
2367   private void analyzeFlowArrayAccessNode(MethodDescriptor md, SymbolTable nametable,
2368       ArrayAccessNode aan, NodeTupleSet nodeSet, boolean isLHS) {
2369
2370     NodeTupleSet expNodeTupleSet = new NodeTupleSet();
2371     analyzeFlowExpressionNode(md, nametable, aan.getExpression(), expNodeTupleSet, isLHS);
2372
2373     NodeTupleSet idxNodeTupleSet = new NodeTupleSet();
2374     analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, isLHS);
2375
2376     if (isLHS) {
2377       // need to create an edge from idx to array
2378       for (Iterator<NTuple<Descriptor>> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) {
2379         NTuple<Descriptor> idxTuple = idxIter.next();
2380         for (Iterator<NTuple<Descriptor>> arrIter = expNodeTupleSet.iterator(); arrIter.hasNext();) {
2381           NTuple<Descriptor> arrTuple = arrIter.next();
2382           getFlowGraph(md).addValueFlowEdge(idxTuple, arrTuple);
2383         }
2384       }
2385
2386       nodeSet.addTupleSet(expNodeTupleSet);
2387     } else {
2388       nodeSet.addTupleSet(expNodeTupleSet);
2389       nodeSet.addTupleSet(idxNodeTupleSet);
2390     }
2391   }
2392
2393   private void analyzeCreateObjectNode(MethodDescriptor md, SymbolTable nametable,
2394       CreateObjectNode en) {
2395     // TODO Auto-generated method stub
2396
2397   }
2398
2399   private void analyzeFlowOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on,
2400       NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
2401
2402     NodeTupleSet leftOpSet = new NodeTupleSet();
2403     NodeTupleSet rightOpSet = new NodeTupleSet();
2404
2405     // left operand
2406     analyzeFlowExpressionNode(md, nametable, on.getLeft(), leftOpSet, null, implicitFlowTupleSet,
2407         false);
2408
2409     if (on.getRight() != null) {
2410       // right operand
2411       analyzeFlowExpressionNode(md, nametable, on.getRight(), rightOpSet, null,
2412           implicitFlowTupleSet, false);
2413     }
2414
2415     Operation op = on.getOp();
2416
2417     switch (op.getOp()) {
2418
2419     case Operation.UNARYPLUS:
2420     case Operation.UNARYMINUS:
2421     case Operation.LOGIC_NOT:
2422       // single operand
2423       nodeSet.addTupleSet(leftOpSet);
2424       break;
2425
2426     case Operation.LOGIC_OR:
2427     case Operation.LOGIC_AND:
2428     case Operation.COMP:
2429     case Operation.BIT_OR:
2430     case Operation.BIT_XOR:
2431     case Operation.BIT_AND:
2432     case Operation.ISAVAILABLE:
2433     case Operation.EQUAL:
2434     case Operation.NOTEQUAL:
2435     case Operation.LT:
2436     case Operation.GT:
2437     case Operation.LTE:
2438     case Operation.GTE:
2439     case Operation.ADD:
2440     case Operation.SUB:
2441     case Operation.MULT:
2442     case Operation.DIV:
2443     case Operation.MOD:
2444     case Operation.LEFTSHIFT:
2445     case Operation.RIGHTSHIFT:
2446     case Operation.URIGHTSHIFT:
2447
2448       // there are two operands
2449       nodeSet.addTupleSet(leftOpSet);
2450       nodeSet.addTupleSet(rightOpSet);
2451       break;
2452
2453     default:
2454       throw new Error(op.toString());
2455     }
2456
2457   }
2458
2459   private NTuple<Descriptor> analyzeFlowNameNode(MethodDescriptor md, SymbolTable nametable,
2460       NameNode nn, NodeTupleSet nodeSet, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
2461
2462     if (base == null) {
2463       base = new NTuple<Descriptor>();
2464     }
2465
2466     NameDescriptor nd = nn.getName();
2467
2468     if (nd.getBase() != null) {
2469       base =
2470           analyzeFlowExpressionNode(md, nametable, nn.getExpression(), nodeSet, base,
2471               implicitFlowTupleSet, false);
2472       if (base == null) {
2473         // base node has the top location
2474         return base;
2475       }
2476     } else {
2477       String varname = nd.toString();
2478       if (varname.equals("this")) {
2479         // 'this' itself!
2480         base.add(md.getThis());
2481         return base;
2482       }
2483
2484       Descriptor d = (Descriptor) nametable.get(varname);
2485
2486       if (d instanceof VarDescriptor) {
2487         VarDescriptor vd = (VarDescriptor) d;
2488         base.add(vd);
2489       } else if (d instanceof FieldDescriptor) {
2490         // the type of field descriptor has a location!
2491         FieldDescriptor fd = (FieldDescriptor) d;
2492         if (fd.isStatic()) {
2493           if (fd.isFinal()) {
2494             // if it is 'static final', no need to have flow node for the TOP
2495             // location
2496             return null;
2497           } else {
2498             // if 'static', assign the default GLOBAL LOCATION to the first
2499             // element of the tuple
2500             base.add(GLOBALDESC);
2501           }
2502         } else {
2503           // the location of field access starts from this, followed by field
2504           // location
2505           base.add(md.getThis());
2506         }
2507
2508         base.add(fd);
2509       } else if (d == null) {
2510         // access static field
2511         base.add(GLOBALDESC);
2512         // base.add(nn.getField());
2513         return base;
2514
2515         // FieldDescriptor fd = nn.getField();addFlowGraphEdge
2516         //
2517         // MethodLattice<String> localLattice = ssjava.getMethodLattice(md);
2518         // String globalLocId = localLattice.getGlobalLoc();
2519         // if (globalLocId == null) {
2520         // throw new
2521         // Error("Method lattice does not define global variable location at "
2522         // + generateErrorMessage(md.getClassDesc(), nn));
2523         // }
2524         // loc.addLocation(new Location(md, globalLocId));
2525         //
2526         // Location fieldLoc = (Location) fd.getType().getExtension();
2527         // loc.addLocation(fieldLoc);
2528         //
2529         // return loc;
2530
2531       }
2532     }
2533
2534     getFlowGraph(md).createNewFlowNode(base);
2535
2536     return base;
2537
2538   }
2539
2540   private NTuple<Descriptor> analyzeFlowFieldAccessNode(MethodDescriptor md, SymbolTable nametable,
2541       FieldAccessNode fan, NodeTupleSet nodeSet, NTuple<Descriptor> base,
2542       NodeTupleSet implicitFlowTupleSet, boolean isLHS) {
2543
2544     ExpressionNode left = fan.getExpression();
2545     TypeDescriptor ltd = left.getType();
2546     FieldDescriptor fd = fan.getField();
2547
2548     String varName = null;
2549     if (left.kind() == Kind.NameNode) {
2550       NameDescriptor nd = ((NameNode) left).getName();
2551       varName = nd.toString();
2552     }
2553
2554     if (ltd.isClassNameRef() || (varName != null && varName.equals("this"))) {
2555       // using a class name directly or access using this
2556       if (fd.isStatic() && fd.isFinal()) {
2557         return null;
2558       }
2559     }
2560
2561     NodeTupleSet idxNodeTupleSet = new NodeTupleSet();
2562     if (left instanceof ArrayAccessNode) {
2563
2564       ArrayAccessNode aan = (ArrayAccessNode) left;
2565       left = aan.getExpression();
2566       analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, base,
2567           implicitFlowTupleSet, isLHS);
2568       nodeSet.addTupleSet(idxNodeTupleSet);
2569     }
2570     base =
2571         analyzeFlowExpressionNode(md, nametable, left, nodeSet, base, implicitFlowTupleSet, isLHS);
2572
2573     if (base == null) {
2574       // in this case, field is TOP location
2575       return null;
2576     } else {
2577
2578       NTuple<Descriptor> flowFieldTuple = new NTuple<Descriptor>(base.toList());
2579
2580       if (!left.getType().isPrimitive()) {
2581
2582         if (!fd.getSymbol().equals("length")) {
2583           // array.length access, just have the location of the array
2584           flowFieldTuple.add(fd);
2585           nodeSet.removeTuple(base);
2586         }
2587
2588       }
2589       getFlowGraph(md).createNewFlowNode(flowFieldTuple);
2590
2591       if (isLHS) {
2592         for (Iterator<NTuple<Descriptor>> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) {
2593           NTuple<Descriptor> idxTuple = idxIter.next();
2594           getFlowGraph(md).addValueFlowEdge(idxTuple, flowFieldTuple);
2595         }
2596       }
2597
2598       return flowFieldTuple;
2599
2600     }
2601
2602   }
2603
2604   private void debug_printTreeNode(TreeNode tn) {
2605
2606     System.out.println("DEBUG: " + tn.printNode(0) + "                line#=" + tn.getNumLine());
2607
2608   }
2609
2610   private void analyzeFlowAssignmentNode(MethodDescriptor md, SymbolTable nametable,
2611       AssignmentNode an, NodeTupleSet nodeSet, NTuple<Descriptor> base,
2612       NodeTupleSet implicitFlowTupleSet) {
2613
2614     NodeTupleSet nodeSetRHS = new NodeTupleSet();
2615     NodeTupleSet nodeSetLHS = new NodeTupleSet();
2616
2617     boolean postinc = true;
2618     if (an.getOperation().getBaseOp() == null
2619         || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
2620             .getBaseOp().getOp() != Operation.POSTDEC)) {
2621       postinc = false;
2622     }
2623     // if LHS is array access node, need to capture value flows between an array
2624     // and its index value
2625     analyzeFlowExpressionNode(md, nametable, an.getDest(), nodeSetLHS, null, implicitFlowTupleSet,
2626         true);
2627
2628     if (!postinc) {
2629       // analyze value flows of rhs expression
2630       analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null, implicitFlowTupleSet,
2631           false);
2632
2633       // System.out.println("-analyzeFlowAssignmentNode=" + an.printNode(0));
2634       // System.out.println("-nodeSetLHS=" + nodeSetLHS);
2635       // System.out.println("-nodeSetRHS=" + nodeSetRHS);
2636       // System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet);
2637       // System.out.println("-");
2638
2639       if (an.getOperation().getOp() >= 2 && an.getOperation().getOp() <= 12) {
2640         // if assignment contains OP+EQ operator, creates edges from LHS to LHS
2641         for (Iterator<NTuple<Descriptor>> iter = nodeSetLHS.iterator(); iter.hasNext();) {
2642           NTuple<Descriptor> fromTuple = iter.next();
2643           for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
2644             NTuple<Descriptor> toTuple = iter2.next();
2645             addFlowGraphEdge(md, fromTuple, toTuple);
2646           }
2647         }
2648       }
2649
2650       // creates edges from RHS to LHS
2651       for (Iterator<NTuple<Descriptor>> iter = nodeSetRHS.iterator(); iter.hasNext();) {
2652         NTuple<Descriptor> fromTuple = iter.next();
2653         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
2654           NTuple<Descriptor> toTuple = iter2.next();
2655           addFlowGraphEdge(md, fromTuple, toTuple);
2656         }
2657       }
2658
2659       // creates edges from implicitFlowTupleSet to LHS
2660       for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
2661         NTuple<Descriptor> fromTuple = iter.next();
2662         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
2663           NTuple<Descriptor> toTuple = iter2.next();
2664           addFlowGraphEdge(md, fromTuple, toTuple);
2665         }
2666       }
2667
2668     } else {
2669       // postinc case
2670       for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
2671         NTuple<Descriptor> tuple = iter2.next();
2672         addFlowGraphEdge(md, tuple, tuple);
2673       }
2674
2675       // creates edges from implicitFlowTupleSet to LHS
2676       for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
2677         NTuple<Descriptor> fromTuple = iter.next();
2678         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
2679           NTuple<Descriptor> toTuple = iter2.next();
2680           addFlowGraphEdge(md, fromTuple, toTuple);
2681         }
2682       }
2683
2684     }
2685
2686     if (nodeSet != null) {
2687       nodeSet.addTupleSet(nodeSetLHS);
2688     }
2689   }
2690
2691   public FlowGraph getFlowGraph(MethodDescriptor md) {
2692     return mapMethodDescriptorToFlowGraph.get(md);
2693   }
2694
2695   private boolean addFlowGraphEdge(MethodDescriptor md, NTuple<Descriptor> from,
2696       NTuple<Descriptor> to) {
2697     // TODO
2698     // return true if it adds a new edge
2699     FlowGraph graph = getFlowGraph(md);
2700     graph.addValueFlowEdge(from, to);
2701     return true;
2702   }
2703
2704   public void _debug_printGraph() {
2705     Set<MethodDescriptor> keySet = mapMethodDescriptorToFlowGraph.keySet();
2706
2707     for (Iterator<MethodDescriptor> iterator = keySet.iterator(); iterator.hasNext();) {
2708       MethodDescriptor md = (MethodDescriptor) iterator.next();
2709       FlowGraph fg = mapMethodDescriptorToFlowGraph.get(md);
2710       try {
2711         fg.writeGraph();
2712       } catch (IOException e) {
2713         e.printStackTrace();
2714       }
2715     }
2716
2717   }
2718
2719 }
2720
2721 class CyclicFlowException extends Exception {
2722
2723 }