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