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