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