Robust/src/Analysis/SSJava/LocationInference.java

   1 package Analysis.SSJava;
   2
   3 import java.io.IOException;
   4 import java.util.ArrayList;
   5 import java.util.Collections;
   6 import java.util.Comparator;
   7 import java.util.HashMap;
   8 import java.util.HashSet;
   9 import java.util.Iterator;
  10 import java.util.LinkedList;
  11 import java.util.List;
  12 import java.util.Map;
  13 import java.util.Set;
  14 import java.util.Stack;
  15
  16 import Analysis.SSJava.FlowDownCheck.ComparisonResult;
  17 import Analysis.SSJava.FlowDownCheck.CompositeLattice;
  18 import IR.ClassDescriptor;
  19 import IR.Descriptor;
  20 import IR.FieldDescriptor;
  21 import IR.MethodDescriptor;
  22 import IR.NameDescriptor;
  23 import IR.Operation;
  24 import IR.State;
  25 import IR.SymbolTable;
  26 import IR.TypeDescriptor;
  27 import IR.VarDescriptor;
  28 import IR.Tree.ArrayAccessNode;
  29 import IR.Tree.AssignmentNode;
  30 import IR.Tree.BlockExpressionNode;
  31 import IR.Tree.BlockNode;
  32 import IR.Tree.BlockStatementNode;
  33 import IR.Tree.CastNode;
  34 import IR.Tree.CreateObjectNode;
  35 import IR.Tree.DeclarationNode;
  36 import IR.Tree.ExpressionNode;
  37 import IR.Tree.FieldAccessNode;
  38 import IR.Tree.IfStatementNode;
  39 import IR.Tree.Kind;
  40 import IR.Tree.LiteralNode;
  41 import IR.Tree.LoopNode;
  42 import IR.Tree.MethodInvokeNode;
  43 import IR.Tree.NameNode;
  44 import IR.Tree.OpNode;
  45 import IR.Tree.ReturnNode;
  46 import IR.Tree.SubBlockNode;
  47 import IR.Tree.SwitchStatementNode;
  48 import IR.Tree.TertiaryNode;
  49
  50 public class LocationInference {
  51
  52   State state;
  53   SSJavaAnalysis ssjava;
  54
  55   List<ClassDescriptor> toanalyzeList;
  56   List<MethodDescriptor> toanalyzeMethodList;
  57   Map<MethodDescriptor, FlowGraph> mapMethodDescriptorToFlowGraph;
  58
  59   // map a method descriptor to its set of parameter descriptors
  60   Map<MethodDescriptor, Set<Descriptor>> mapMethodDescriptorToParamDescSet;
  61
  62   // keep current descriptors to visit in fixed-point interprocedural analysis,
  63   private Stack<MethodDescriptor> methodDescriptorsToVisitStack;
  64
  65   // map a class descriptor to a field lattice
  66   private Map<ClassDescriptor, SSJavaLattice<String>> cd2lattice;
  67
  68   // map a method descriptor to a method lattice
  69   private Map<MethodDescriptor, SSJavaLattice<String>> md2lattice;
  70
  71   // map a method descriptor to the set of method invocation nodes which are
  72   // invoked by the method descriptor
  73   private Map<MethodDescriptor, Set<MethodInvokeNode>> mapMethodDescriptorToMethodInvokeNodeSet;
  74
  75   private Map<MethodInvokeNode, Map<Integer, NTuple<Descriptor>>> mapMethodInvokeNodeToArgIdxMap;
  76
  77   private Map<MethodDescriptor, MethodLocationInfo> mapLatticeToMethodLocationInfo;
  78
  79   private Map<MethodDescriptor, Set<MethodDescriptor>> mapMethodDescToPossibleMethodDescSet;
  80
  81   boolean debug = true;
  82
  83   public LocationInference(SSJavaAnalysis ssjava, State state) {
  84     this.ssjava = ssjava;
  85     this.state = state;
  86     this.toanalyzeList = new ArrayList<ClassDescriptor>();
  87     this.toanalyzeMethodList = new ArrayList<MethodDescriptor>();
  88     this.mapMethodDescriptorToFlowGraph = new HashMap<MethodDescriptor, FlowGraph>();
  89     this.cd2lattice = new HashMap<ClassDescriptor, SSJavaLattice<String>>();
  90     this.md2lattice = new HashMap<MethodDescriptor, SSJavaLattice<String>>();
  91     this.methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
  92     this.mapMethodDescriptorToMethodInvokeNodeSet =
  93         new HashMap<MethodDescriptor, Set<MethodInvokeNode>>();
  94     this.mapMethodInvokeNodeToArgIdxMap =
  95         new HashMap<MethodInvokeNode, Map<Integer, NTuple<Descriptor>>>();
  96     this.mapLatticeToMethodLocationInfo = new HashMap<MethodDescriptor, MethodLocationInfo>();
  97     this.mapMethodDescToPossibleMethodDescSet =
  98         new HashMap<MethodDescriptor, Set<MethodDescriptor>>();
  99   }
 100
 101   public void setupToAnalyze() {
 102     SymbolTable classtable = state.getClassSymbolTable();
 103     toanalyzeList.clear();
 104     toanalyzeList.addAll(classtable.getValueSet());
 105     Collections.sort(toanalyzeList, new Comparator<ClassDescriptor>() {
 106       public int compare(ClassDescriptor o1, ClassDescriptor o2) {
 107         return o1.getClassName().compareToIgnoreCase(o2.getClassName());
 108       }
 109     });
 110   }
 111
 112   public void setupToAnalazeMethod(ClassDescriptor cd) {
 113
 114     SymbolTable methodtable = cd.getMethodTable();
 115     toanalyzeMethodList.clear();
 116     toanalyzeMethodList.addAll(methodtable.getValueSet());
 117     Collections.sort(toanalyzeMethodList, new Comparator<MethodDescriptor>() {
 118       public int compare(MethodDescriptor o1, MethodDescriptor o2) {
 119         return o1.getSymbol().compareToIgnoreCase(o2.getSymbol());
 120       }
 121     });
 122   }
 123
 124   public boolean toAnalyzeMethodIsEmpty() {
 125     return toanalyzeMethodList.isEmpty();
 126   }
 127
 128   public boolean toAnalyzeIsEmpty() {
 129     return toanalyzeList.isEmpty();
 130   }
 131
 132   public ClassDescriptor toAnalyzeNext() {
 133     return toanalyzeList.remove(0);
 134   }
 135
 136   public MethodDescriptor toAnalyzeMethodNext() {
 137     return toanalyzeMethodList.remove(0);
 138   }
 139
 140   public void inference() {
 141
 142     // 1) construct value flow graph
 143     constructFlowGraph();
 144
 145     // 2) construct lattices
 146     inferLattices();
 147
 148     debug_writeLatticeDotFile();
 149
 150     // 3) check properties
 151     checkLattices();
 152
 153   }
 154
 155   private void checkLattices() {
 156
 157     LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
 158
 159     // current descriptors to visit in fixed-point interprocedural analysis,
 160     // prioritized by
 161     // dependency in the call graph
 162     methodDescriptorsToVisitStack.clear();
 163
 164     descriptorListToAnalyze.removeFirst();
 165
 166     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
 167     methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
 168
 169     while (!descriptorListToAnalyze.isEmpty()) {
 170       MethodDescriptor md = descriptorListToAnalyze.removeFirst();
 171       checkLatticesOfVirtualMethods(md);
 172     }
 173
 174   }
 175
 176   private void debug_writeLatticeDotFile() {
 177     // generate lattice dot file
 178
 179     setupToAnalyze();
 180
 181     while (!toAnalyzeIsEmpty()) {
 182       ClassDescriptor cd = toAnalyzeNext();
 183
 184       setupToAnalazeMethod(cd);
 185
 186       SSJavaLattice<String> classLattice = cd2lattice.get(cd);
 187       if (classLattice != null) {
 188         ssjava.writeLatticeDotFile(cd, null, classLattice);
 189       }
 190
 191       while (!toAnalyzeMethodIsEmpty()) {
 192         MethodDescriptor md = toAnalyzeMethodNext();
 193         if (ssjava.needTobeAnnotated(md)) {
 194           SSJavaLattice<String> methodLattice = md2lattice.get(md);
 195           if (methodLattice != null) {
 196             ssjava.writeLatticeDotFile(cd, md, methodLattice);
 197           }
 198         }
 199       }
 200     }
 201
 202   }
 203
 204   private void inferLattices() {
 205
 206     // do fixed-point analysis
 207
 208     LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
 209
 210     // current descriptors to visit in fixed-point interprocedural analysis,
 211     // prioritized by
 212     // dependency in the call graph
 213     methodDescriptorsToVisitStack.clear();
 214
 215     descriptorListToAnalyze.removeFirst();
 216
 217     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
 218     methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
 219
 220     while (!descriptorListToAnalyze.isEmpty()) {
 221       MethodDescriptor md = descriptorListToAnalyze.removeFirst();
 222       methodDescriptorsToVisitStack.add(md);
 223     }
 224
 225     // analyze scheduled methods until there are no more to visit
 226     while (!methodDescriptorsToVisitStack.isEmpty()) {
 227       // start to analyze leaf node
 228       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
 229
 230       SSJavaLattice<String> methodLattice =
 231           new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM);
 232
 233       System.out.println();
 234       System.out.println("SSJAVA: Inferencing the lattice from " + md);
 235
 236       analyzeMethodLattice(md, methodLattice);
 237
 238       SSJavaLattice<String> prevMethodLattice = getMethodLattice(md);
 239
 240       if (!methodLattice.equals(prevMethodLattice)) {
 241
 242         setMethodLattice(md, methodLattice);
 243
 244         // results for callee changed, so enqueue dependents caller for
 245         // further analysis
 246         Iterator<MethodDescriptor> depsItr = ssjava.getDependents(md).iterator();
 247         while (depsItr.hasNext()) {
 248           MethodDescriptor methodNext = depsItr.next();
 249           if (!methodDescriptorsToVisitStack.contains(methodNext)
 250               && methodDescriptorToVistSet.contains(methodNext)) {
 251             methodDescriptorsToVisitStack.add(methodNext);
 252           }
 253         }
 254
 255       }
 256
 257     }
 258
 259   }
 260
 261   private void checkLatticesOfVirtualMethods(MethodDescriptor md) {
 262
 263     if (!md.isStatic()) {
 264       Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
 265       setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md));
 266
 267       for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
 268         MethodDescriptor mdCallee = (MethodDescriptor) iterator.next();
 269         if (!md.equals(mdCallee)) {
 270           checkConsistency(md, mdCallee);
 271         }
 272       }
 273
 274     }
 275
 276   }
 277
 278   private void checkConsistency(MethodDescriptor md1, MethodDescriptor md2) {
 279
 280     // check that two lattice have the same relations between parameters(+PC
 281     // LOC, RETURN LOC)
 282
 283     MethodLocationInfo methodInfo1 = getMethodLocationInfo(md1);
 284
 285     SSJavaLattice<String> lattice1 = getMethodLattice(md1);
 286     SSJavaLattice<String> lattice2 = getMethodLattice(md2);
 287
 288     Set<String> paramLocNameSet1 = methodInfo1.getParameterLocNameSet();
 289
 290     for (Iterator iterator = paramLocNameSet1.iterator(); iterator.hasNext();) {
 291       String locName1 = (String) iterator.next();
 292       for (Iterator iterator2 = paramLocNameSet1.iterator(); iterator2.hasNext();) {
 293         String locName2 = (String) iterator2.next();
 294
 295         // System.out.println("COMPARE " + locName1 + " - " + locName2 + " "
 296         // + lattice1.isGreaterThan(locName1, locName2) + "-"
 297         // + lattice2.isGreaterThan(locName1, locName2));
 298
 299         if (!locName1.equals(locName2)) {
 300
 301           boolean r1 = lattice1.isGreaterThan(locName1, locName2);
 302           boolean r2 = lattice2.isGreaterThan(locName1, locName2);
 303
 304           if (r1 != r2) {
 305             throw new Error("The method " + md1 + " is not consistent with the method " + md2
 306                 + ".:: They have a different ordering relation between parameters " + locName1
 307                 + " and " + locName2 + ".");
 308           }
 309         }
 310
 311       }
 312     }
 313
 314   }
 315
 316   private String getSymbol(int idx, FlowNode node) {
 317     Descriptor desc = node.getDescTuple().get(idx);
 318     return desc.getSymbol();
 319   }
 320
 321   private void analyzeMethodLattice(MethodDescriptor md, SSJavaLattice<String> methodLattice) {
 322
 323     MethodLocationInfo methodInfo = getMethodLocationInfo(md);
 324
 325     // first take a look at method invocation nodes to newly added relations
 326     // from the callee
 327     analyzeLatticeMethodInvocationNode(md);
 328
 329     // visit each node of method flow graph
 330     FlowGraph fg = getFlowGraph(md);
 331     Set<FlowNode> nodeSet = fg.getNodeSet();
 332
 333     // for the method lattice, we need to look at the first element of
 334     // NTuple<Descriptor>
 335     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 336       FlowNode srcNode = (FlowNode) iterator.next();
 337
 338       Set<FlowEdge> outEdgeSet = srcNode.getOutEdgeSet();
 339       for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) {
 340         FlowEdge outEdge = (FlowEdge) iterator2.next();
 341         FlowNode dstNode = outEdge.getDst();
 342
 343         NTuple<Descriptor> srcNodeTuple = srcNode.getDescTuple();
 344         NTuple<Descriptor> dstNodeTuple = dstNode.getDescTuple();
 345
 346         if (outEdge.getInitTuple().equals(srcNodeTuple)
 347             && outEdge.getEndTuple().equals(dstNodeTuple)) {
 348
 349           if ((srcNodeTuple.size() > 1 && dstNodeTuple.size() > 1)
 350               && srcNodeTuple.get(0).equals(dstNodeTuple.get(0))) {
 351
 352             // value flows between fields
 353             VarDescriptor varDesc = (VarDescriptor) srcNodeTuple.get(0);
 354             ClassDescriptor varClassDesc = varDesc.getType().getClassDesc();
 355             extractRelationFromFieldFlows(varClassDesc, srcNode, dstNode, 1);
 356
 357           } else {
 358             // in this case, take a look at connected nodes at the local level
 359             addRelationToLattice(md, methodLattice, srcNode, dstNode);
 360           }
 361
 362         }
 363
 364       }
 365
 366     }
 367
 368     // grab the this location if the method use the 'this' reference
 369     String thisLocSymbol = md.getThis().getSymbol();
 370     if (methodLattice.getKeySet().contains(thisLocSymbol)) {
 371       methodInfo.setThisLocName(thisLocSymbol);
 372     }
 373
 374     // calculate a return location
 375     if (!md.getReturnType().isVoid()) {
 376       Set<FlowNode> returnNodeSet = fg.getReturnNodeSet();
 377       Set<String> returnVarSymbolSet = new HashSet<String>();
 378
 379       for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
 380         FlowNode rtrNode = (FlowNode) iterator.next();
 381         String localSymbol = rtrNode.getDescTuple().get(0).getSymbol();
 382         returnVarSymbolSet.add(localSymbol);
 383       }
 384
 385       String returnGLB = methodLattice.getGLB(returnVarSymbolSet);
 386       if (returnGLB.equals(SSJavaAnalysis.BOTTOM)) {
 387         // need to insert a new location in-between the bottom and all locations
 388         // that is directly connected to the bottom
 389         String returnNewLocationSymbol = "Loc" + (SSJavaLattice.seed++);
 390         methodLattice.insertNewLocationAtOneLevelHigher(returnGLB, returnNewLocationSymbol);
 391         methodInfo.setReturnLocName(returnNewLocationSymbol);
 392       } else {
 393         methodInfo.setReturnLocName(returnGLB);
 394       }
 395     }
 396
 397   }
 398
 399   private void analyzeLatticeMethodInvocationNode(MethodDescriptor mdCaller) {
 400
 401     // the transformation for a call site propagates all relations between
 402     // parameters from the callee
 403     // if the method is virtual, it also grab all relations from any possible
 404     // callees
 405
 406     Set<MethodInvokeNode> setMethodInvokeNode =
 407         mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller);
 408     if (setMethodInvokeNode != null) {
 409
 410       for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) {
 411         MethodInvokeNode min = (MethodInvokeNode) iterator.next();
 412         MethodDescriptor mdCallee = min.getMethod();
 413         Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
 414         if (mdCallee.isStatic()) {
 415           setPossibleCallees.add(mdCallee);
 416         } else {
 417           setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(mdCallee));
 418         }
 419
 420         for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
 421           MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
 422           propagateRelationToCaller(min, mdCaller, possibleMdCallee);
 423         }
 424
 425       }
 426     }
 427
 428   }
 429
 430   private void propagateRelationToCaller(MethodInvokeNode min, MethodDescriptor mdCaller,
 431       MethodDescriptor possibleMdCallee) {
 432
 433     SSJavaLattice<String> calleeLattice = getMethodLattice(possibleMdCallee);
 434
 435     FlowGraph calleeFlowGraph = getFlowGraph(possibleMdCallee);
 436
 437     // find parameter node
 438     Set<FlowNode> paramNodeSet = calleeFlowGraph.getParameterNodeSet();
 439
 440     for (Iterator iterator = paramNodeSet.iterator(); iterator.hasNext();) {
 441       FlowNode paramFlowNode1 = (FlowNode) iterator.next();
 442
 443       for (Iterator iterator2 = paramNodeSet.iterator(); iterator2.hasNext();) {
 444         FlowNode paramFlowNode2 = (FlowNode) iterator2.next();
 445
 446         String paramSymbol1 = getSymbol(0, paramFlowNode1);
 447         String paramSymbol2 = getSymbol(0, paramFlowNode2);
 448         // if two parameters have a relation, we need to propagate this relation
 449         // to the caller
 450         if (!(paramSymbol1.equals(paramSymbol2))
 451             && calleeLattice.isComparable(paramSymbol1, paramSymbol2)) {
 452           int higherLocIdxCallee;
 453           int lowerLocIdxCallee;
 454           if (calleeLattice.isGreaterThan(paramSymbol1, paramSymbol2)) {
 455             higherLocIdxCallee = calleeFlowGraph.getParamIdx(paramFlowNode1.getDescTuple());
 456             lowerLocIdxCallee = calleeFlowGraph.getParamIdx(paramFlowNode2.getDescTuple());
 457           } else {
 458             higherLocIdxCallee = calleeFlowGraph.getParamIdx(paramFlowNode2.getDescTuple());
 459             lowerLocIdxCallee = calleeFlowGraph.getParamIdx(paramFlowNode1.getDescTuple());
 460           }
 461
 462           NTuple<Descriptor> higherArg = getArgTupleByArgIdx(min, higherLocIdxCallee);
 463           NTuple<Descriptor> lowerArg = getArgTupleByArgIdx(min, lowerLocIdxCallee);
 464
 465           addFlowGraphEdge(mdCaller, higherArg, lowerArg);
 466
 467         }
 468
 469       }
 470
 471     }
 472
 473   }
 474
 475   private MethodLocationInfo getMethodLocationInfo(MethodDescriptor md) {
 476
 477     if (!mapLatticeToMethodLocationInfo.containsKey(md)) {
 478       mapLatticeToMethodLocationInfo.put(md, new MethodLocationInfo(md));
 479     }
 480
 481     return mapLatticeToMethodLocationInfo.get(md);
 482
 483   }
 484
 485   private void addRelationToLattice(MethodDescriptor md, SSJavaLattice<String> methodLattice,
 486       FlowNode srcNode, FlowNode dstNode) {
 487
 488     // add a new binary relation of dstNode < srcNode
 489     String srcSymbol = getSymbol(0, srcNode);
 490     String dstSymbol = getSymbol(0, dstNode);
 491
 492     FlowGraph flowGraph = getFlowGraph(md);
 493     MethodLocationInfo methodInfo = getMethodLocationInfo(md);
 494
 495     if (srcNode.isParameter()) {
 496       int paramIdx = flowGraph.getParamIdx(srcNode.getDescTuple());
 497       methodInfo.addParameter(srcSymbol, srcNode, paramIdx);
 498     }
 499     if (dstNode.isParameter()) {
 500       int paramIdx = flowGraph.getParamIdx(dstNode.getDescTuple());
 501       methodInfo.addParameter(dstSymbol, dstNode, paramIdx);
 502     }
 503
 504     if (!methodLattice.isGreaterThan(srcSymbol, dstSymbol)) {
 505       // if the lattice does not have this relation, add it
 506       methodLattice.addRelationHigherToLower(srcSymbol, dstSymbol);
 507     }
 508
 509   }
 510
 511   private SSJavaLattice<String> getMethodLattice(MethodDescriptor md) {
 512     if (!md2lattice.containsKey(md)) {
 513       md2lattice.put(md, new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM));
 514     }
 515     return md2lattice.get(md);
 516   }
 517
 518   private void setMethodLattice(MethodDescriptor md, SSJavaLattice<String> lattice) {
 519     md2lattice.put(md, lattice);
 520   }
 521
 522   private void extractRelationFromFieldFlows(ClassDescriptor cd, FlowNode srcNode,
 523       FlowNode dstNode, int idx) {
 524
 525     if (srcNode.getDescTuple().get(idx).equals(dstNode.getDescTuple().get(idx))
 526         && srcNode.getDescTuple().size() > (idx + 1) && dstNode.getDescTuple().size() > (idx + 1)) {
 527       // value flow between fields: we don't need to add a binary relation
 528       // for this case
 529
 530       Descriptor desc = srcNode.getDescTuple().get(idx);
 531       ClassDescriptor classDesc;
 532
 533       if (idx == 0) {
 534         classDesc = ((VarDescriptor) desc).getType().getClassDesc();
 535       } else {
 536         classDesc = ((FieldDescriptor) desc).getType().getClassDesc();
 537       }
 538
 539       extractRelationFromFieldFlows(classDesc, srcNode, dstNode, idx + 1);
 540
 541     } else {
 542
 543       Descriptor srcFieldDesc = srcNode.getDescTuple().get(idx);
 544       Descriptor dstFieldDesc = dstNode.getDescTuple().get(idx);
 545
 546       // add a new binary relation of dstNode < srcNode
 547       SSJavaLattice<String> fieldLattice = getFieldLattice(cd);
 548
 549       String srcSymbol = srcFieldDesc.getSymbol();
 550       String dstSymbol = dstFieldDesc.getSymbol();
 551
 552       if (!fieldLattice.isGreaterThan(srcSymbol, dstSymbol)) {
 553         fieldLattice.addRelationHigherToLower(srcSymbol, dstSymbol);
 554       }
 555
 556     }
 557
 558   }
 559
 560   public SSJavaLattice<String> getFieldLattice(ClassDescriptor cd) {
 561     if (!cd2lattice.containsKey(cd)) {
 562       cd2lattice.put(cd, new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM));
 563     }
 564     return cd2lattice.get(cd);
 565   }
 566
 567   public void constructFlowGraph() {
 568
 569     setupToAnalyze();
 570
 571     while (!toAnalyzeIsEmpty()) {
 572       ClassDescriptor cd = toAnalyzeNext();
 573
 574       setupToAnalazeMethod(cd);
 575       while (!toAnalyzeMethodIsEmpty()) {
 576         MethodDescriptor md = toAnalyzeMethodNext();
 577         if (ssjava.needTobeAnnotated(md)) {
 578           if (state.SSJAVADEBUG) {
 579             System.out.println();
 580             System.out.println("SSJAVA: Constructing a flow graph: " + md);
 581           }
 582
 583           // creates a mapping from a method descriptor to virtual methods
 584           Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
 585           if (md.isStatic()) {
 586             setPossibleCallees.add(md);
 587           } else {
 588             setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md));
 589           }
 590           mapMethodDescToPossibleMethodDescSet.put(md, setPossibleCallees);
 591
 592           // creates a mapping from a parameter descriptor to its index
 593           Map<Descriptor, Integer> mapParamDescToIdx = new HashMap<Descriptor, Integer>();
 594           int offset = md.isStatic() ? 0 : 1;
 595           for (int i = 0; i < md.numParameters(); i++) {
 596             Descriptor paramDesc = (Descriptor) md.getParameter(i);
 597             mapParamDescToIdx.put(paramDesc, new Integer(i + offset));
 598           }
 599
 600           FlowGraph fg = new FlowGraph(md, mapParamDescToIdx);
 601           mapMethodDescriptorToFlowGraph.put(md, fg);
 602
 603           analyzeMethodBody(cd, md);
 604         }
 605       }
 606     }
 607
 608     _debug_printGraph();
 609   }
 610
 611   private void analyzeMethodBody(ClassDescriptor cd, MethodDescriptor md) {
 612     BlockNode bn = state.getMethodBody(md);
 613     NodeTupleSet implicitFlowTupleSet = new NodeTupleSet();
 614     analyzeFlowBlockNode(md, md.getParameterTable(), bn, implicitFlowTupleSet);
 615   }
 616
 617   private void analyzeFlowBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn,
 618       NodeTupleSet implicitFlowTupleSet) {
 619
 620     bn.getVarTable().setParent(nametable);
 621     for (int i = 0; i < bn.size(); i++) {
 622       BlockStatementNode bsn = bn.get(i);
 623       analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet);
 624     }
 625
 626   }
 627
 628   private void analyzeBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
 629       BlockStatementNode bsn, NodeTupleSet implicitFlowTupleSet) {
 630
 631     switch (bsn.kind()) {
 632     case Kind.BlockExpressionNode:
 633       analyzeBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn, implicitFlowTupleSet);
 634       break;
 635
 636     case Kind.DeclarationNode:
 637       analyzeFlowDeclarationNode(md, nametable, (DeclarationNode) bsn, implicitFlowTupleSet);
 638       break;
 639
 640     case Kind.IfStatementNode:
 641       analyzeFlowIfStatementNode(md, nametable, (IfStatementNode) bsn, implicitFlowTupleSet);
 642       break;
 643
 644     case Kind.LoopNode:
 645       analyzeFlowLoopNode(md, nametable, (LoopNode) bsn, implicitFlowTupleSet);
 646       break;
 647
 648     case Kind.ReturnNode:
 649       analyzeFlowReturnNode(md, nametable, (ReturnNode) bsn, implicitFlowTupleSet);
 650       break;
 651
 652     case Kind.SubBlockNode:
 653       analyzeFlowSubBlockNode(md, nametable, (SubBlockNode) bsn, implicitFlowTupleSet);
 654       break;
 655
 656     case Kind.ContinueBreakNode:
 657       break;
 658
 659     case Kind.SwitchStatementNode:
 660       analyzeSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn);
 661       break;
 662
 663     }
 664
 665   }
 666
 667   private void analyzeSwitchStatementNode(MethodDescriptor md, SymbolTable nametable,
 668       SwitchStatementNode bsn) {
 669     // TODO Auto-generated method stub
 670   }
 671
 672   private void analyzeFlowSubBlockNode(MethodDescriptor md, SymbolTable nametable,
 673       SubBlockNode sbn, NodeTupleSet implicitFlowTupleSet) {
 674     analyzeFlowBlockNode(md, nametable, sbn.getBlockNode(), implicitFlowTupleSet);
 675   }
 676
 677   private void analyzeFlowReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode rn,
 678       NodeTupleSet implicitFlowTupleSet) {
 679
 680     ExpressionNode returnExp = rn.getReturnExpression();
 681
 682     NodeTupleSet nodeSet = new NodeTupleSet();
 683     analyzeFlowExpressionNode(md, nametable, returnExp, nodeSet, false);
 684
 685     FlowGraph fg = getFlowGraph(md);
 686
 687     // annotate the elements of the node set as the return location
 688     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 689       NTuple<Descriptor> returnDescTuple = (NTuple<Descriptor>) iterator.next();
 690       fg.setReturnFlowNode(returnDescTuple);
 691       for (Iterator iterator2 = implicitFlowTupleSet.iterator(); iterator2.hasNext();) {
 692         NTuple<Descriptor> implicitFlowDescTuple = (NTuple<Descriptor>) iterator2.next();
 693         fg.addValueFlowEdge(implicitFlowDescTuple, returnDescTuple);
 694       }
 695     }
 696
 697   }
 698
 699   private void analyzeFlowLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln,
 700       NodeTupleSet implicitFlowTupleSet) {
 701
 702     if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) {
 703
 704       NodeTupleSet condTupleNode = new NodeTupleSet();
 705       analyzeFlowExpressionNode(md, nametable, ln.getCondition(), condTupleNode, null,
 706           implicitFlowTupleSet, false);
 707       condTupleNode.addTupleSet(implicitFlowTupleSet);
 708
 709       // add edges from condNodeTupleSet to all nodes of conditional nodes
 710       analyzeFlowBlockNode(md, nametable, ln.getBody(), condTupleNode);
 711
 712     } else {
 713       // check 'for loop' case
 714       BlockNode bn = ln.getInitializer();
 715       analyzeFlowBlockNode(md, bn.getVarTable(), bn, implicitFlowTupleSet);
 716       bn.getVarTable().setParent(nametable);
 717
 718       NodeTupleSet condTupleNode = new NodeTupleSet();
 719       analyzeFlowExpressionNode(md, bn.getVarTable(), ln.getCondition(), condTupleNode, null,
 720           implicitFlowTupleSet, false);
 721       condTupleNode.addTupleSet(implicitFlowTupleSet);
 722
 723       analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(), condTupleNode);
 724       analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(), condTupleNode);
 725
 726     }
 727
 728   }
 729
 730   private void analyzeFlowIfStatementNode(MethodDescriptor md, SymbolTable nametable,
 731       IfStatementNode isn, NodeTupleSet implicitFlowTupleSet) {
 732
 733     NodeTupleSet condTupleNode = new NodeTupleSet();
 734     analyzeFlowExpressionNode(md, nametable, isn.getCondition(), condTupleNode, null,
 735         implicitFlowTupleSet, false);
 736
 737     // add edges from condNodeTupleSet to all nodes of conditional nodes
 738     condTupleNode.addTupleSet(implicitFlowTupleSet);
 739     analyzeFlowBlockNode(md, nametable, isn.getTrueBlock(), condTupleNode);
 740
 741     if (isn.getFalseBlock() != null) {
 742       analyzeFlowBlockNode(md, nametable, isn.getFalseBlock(), condTupleNode);
 743     }
 744
 745   }
 746
 747   private void analyzeFlowDeclarationNode(MethodDescriptor md, SymbolTable nametable,
 748       DeclarationNode dn, NodeTupleSet implicitFlowTupleSet) {
 749
 750     VarDescriptor vd = dn.getVarDescriptor();
 751     NTuple<Descriptor> tupleLHS = new NTuple<Descriptor>();
 752     tupleLHS.add(vd);
 753     getFlowGraph(md).createNewFlowNode(tupleLHS);
 754
 755     if (dn.getExpression() != null) {
 756
 757       NodeTupleSet tupleSetRHS = new NodeTupleSet();
 758       analyzeFlowExpressionNode(md, nametable, dn.getExpression(), tupleSetRHS, null,
 759           implicitFlowTupleSet, false);
 760
 761       // add a new flow edge from rhs to lhs
 762       for (Iterator<NTuple<Descriptor>> iter = tupleSetRHS.iterator(); iter.hasNext();) {
 763         NTuple<Descriptor> from = iter.next();
 764         addFlowGraphEdge(md, from, tupleLHS);
 765       }
 766
 767     }
 768
 769   }
 770
 771   private void analyzeBlockExpressionNode(MethodDescriptor md, SymbolTable nametable,
 772       BlockExpressionNode ben, NodeTupleSet implicitFlowTupleSet) {
 773     analyzeFlowExpressionNode(md, nametable, ben.getExpression(), null, null, implicitFlowTupleSet,
 774         false);
 775   }
 776
 777   private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
 778       ExpressionNode en, NodeTupleSet nodeSet, boolean isLHS) {
 779     return analyzeFlowExpressionNode(md, nametable, en, nodeSet, null, new NodeTupleSet(), isLHS);
 780   }
 781
 782   private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
 783       ExpressionNode en, NodeTupleSet nodeSet, NTuple<Descriptor> base,
 784       NodeTupleSet implicitFlowTupleSet, boolean isLHS) {
 785
 786     // note that expression node can create more than one flow node
 787     // nodeSet contains of flow nodes
 788     // base is always assigned to null except the case of a name node!
 789
 790     NTuple<Descriptor> flowTuple;
 791
 792     switch (en.kind()) {
 793
 794     case Kind.AssignmentNode:
 795       analyzeFlowAssignmentNode(md, nametable, (AssignmentNode) en, base, implicitFlowTupleSet);
 796       break;
 797
 798     case Kind.FieldAccessNode:
 799       flowTuple =
 800           analyzeFlowFieldAccessNode(md, nametable, (FieldAccessNode) en, nodeSet, base,
 801               implicitFlowTupleSet);
 802       nodeSet.addTuple(flowTuple);
 803       return flowTuple;
 804
 805     case Kind.NameNode:
 806       NodeTupleSet nameNodeSet = new NodeTupleSet();
 807       flowTuple =
 808           analyzeFlowNameNode(md, nametable, (NameNode) en, nameNodeSet, base, implicitFlowTupleSet);
 809       nodeSet.addTuple(flowTuple);
 810       return flowTuple;
 811
 812     case Kind.OpNode:
 813       analyzeFlowOpNode(md, nametable, (OpNode) en, nodeSet, implicitFlowTupleSet);
 814       break;
 815
 816     case Kind.CreateObjectNode:
 817       analyzeCreateObjectNode(md, nametable, (CreateObjectNode) en);
 818       break;
 819
 820     case Kind.ArrayAccessNode:
 821       analyzeFlowArrayAccessNode(md, nametable, (ArrayAccessNode) en, nodeSet, isLHS);
 822       break;
 823
 824     case Kind.LiteralNode:
 825       analyzeLiteralNode(md, nametable, (LiteralNode) en);
 826       break;
 827
 828     case Kind.MethodInvokeNode:
 829       analyzeFlowMethodInvokeNode(md, nametable, (MethodInvokeNode) en, implicitFlowTupleSet);
 830       break;
 831
 832     case Kind.TertiaryNode:
 833       analyzeFlowTertiaryNode(md, nametable, (TertiaryNode) en, nodeSet, implicitFlowTupleSet);
 834       break;
 835
 836     case Kind.CastNode:
 837       analyzeFlowCastNode(md, nametable, (CastNode) en, implicitFlowTupleSet);
 838       break;
 839
 840     // case Kind.InstanceOfNode:
 841     // checkInstanceOfNode(md, nametable, (InstanceOfNode) en, td);
 842     // return null;
 843
 844     // case Kind.ArrayInitializerNode:
 845     // checkArrayInitializerNode(md, nametable, (ArrayInitializerNode) en,
 846     // td);
 847     // return null;
 848
 849     // case Kind.ClassTypeNode:
 850     // checkClassTypeNode(md, nametable, (ClassTypeNode) en, td);
 851     // return null;
 852
 853     // case Kind.OffsetNode:
 854     // checkOffsetNode(md, nametable, (OffsetNode)en, td);
 855     // return null;
 856
 857     }
 858     return null;
 859
 860   }
 861
 862   private void analyzeFlowCastNode(MethodDescriptor md, SymbolTable nametable, CastNode cn,
 863       NodeTupleSet implicitFlowTupleSet) {
 864
 865     NodeTupleSet nodeTupleSet = new NodeTupleSet();
 866     analyzeFlowExpressionNode(md, nametable, cn.getExpression(), nodeTupleSet, false);
 867
 868   }
 869
 870   private void analyzeFlowTertiaryNode(MethodDescriptor md, SymbolTable nametable, TertiaryNode tn,
 871       NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
 872
 873     NodeTupleSet tertiaryTupleNode = new NodeTupleSet();
 874     analyzeFlowExpressionNode(md, nametable, tn.getCond(), tertiaryTupleNode, null,
 875         implicitFlowTupleSet, false);
 876
 877     // add edges from tertiaryTupleNode to all nodes of conditional nodes
 878     tertiaryTupleNode.addTupleSet(implicitFlowTupleSet);
 879     analyzeFlowExpressionNode(md, nametable, tn.getTrueExpr(), tertiaryTupleNode, null,
 880         implicitFlowTupleSet, false);
 881
 882     analyzeFlowExpressionNode(md, nametable, tn.getFalseExpr(), tertiaryTupleNode, null,
 883         implicitFlowTupleSet, false);
 884
 885     nodeSet.addTupleSet(tertiaryTupleNode);
 886
 887   }
 888
 889   private void addMapCallerMethodDescToMethodInvokeNodeSet(MethodDescriptor caller,
 890       MethodInvokeNode min) {
 891     Set<MethodInvokeNode> set = mapMethodDescriptorToMethodInvokeNodeSet.get(caller);
 892     if (set == null) {
 893       set = new HashSet<MethodInvokeNode>();
 894       mapMethodDescriptorToMethodInvokeNodeSet.put(caller, set);
 895     }
 896     set.add(min);
 897   }
 898
 899   private void analyzeFlowMethodInvokeNode(MethodDescriptor md, SymbolTable nametable,
 900       MethodInvokeNode min, NodeTupleSet implicitFlowTupleSet) {
 901
 902     addMapCallerMethodDescToMethodInvokeNodeSet(md, min);
 903
 904     MethodDescriptor calleeMD = min.getMethod();
 905
 906     NameDescriptor baseName = min.getBaseName();
 907     boolean isSystemout = false;
 908     if (baseName != null) {
 909       isSystemout = baseName.getSymbol().equals("System.out");
 910     }
 911
 912     if (!ssjava.isSSJavaUtil(calleeMD.getClassDesc()) && !ssjava.isTrustMethod(calleeMD)
 913         && !calleeMD.getModifiers().isNative() && !isSystemout) {
 914
 915       // CompositeLocation baseLocation = null;
 916       if (min.getExpression() != null) {
 917
 918         NodeTupleSet baseNodeSet = new NodeTupleSet();
 919         analyzeFlowExpressionNode(calleeMD, nametable, min.getExpression(), baseNodeSet, null,
 920             implicitFlowTupleSet, false);
 921
 922       } else {
 923         if (min.getMethod().isStatic()) {
 924           // String globalLocId = ssjava.getMethodLattice(md).getGlobalLoc();
 925           // if (globalLocId == null) {
 926           // throw new
 927           // Error("Method lattice does not define global variable location at "
 928           // + generateErrorMessage(md.getClassDesc(), min));
 929           // }
 930           // baseLocation = new CompositeLocation(new Location(md,
 931           // globalLocId));
 932         } else {
 933           // 'this' var case
 934           // String thisLocId = ssjava.getMethodLattice(md).getThisLoc();
 935           // baseLocation = new CompositeLocation(new Location(md, thisLocId));
 936         }
 937       }
 938
 939       // constraint case:
 940       // if (constraint != null) {
 941       // int compareResult =
 942       // CompositeLattice.compare(constraint, baseLocation, true,
 943       // generateErrorMessage(cd, min));
 944       // if (compareResult != ComparisonResult.GREATER) {
 945       // // if the current constraint is higher than method's THIS location
 946       // // no need to check constraints!
 947       // CompositeLocation calleeConstraint =
 948       // translateCallerLocToCalleeLoc(calleeMD, baseLocation, constraint);
 949       // // System.out.println("check method body for constraint:" + calleeMD +
 950       // // " calleeConstraint="
 951       // // + calleeConstraint);
 952       // checkMethodBody(calleeMD.getClassDesc(), calleeMD, calleeConstraint);
 953       // }
 954       // }
 955
 956       analyzeFlowMethodParameters(md, nametable, min);
 957
 958       // checkCalleeConstraints(md, nametable, min, baseLocation, constraint);
 959
 960       // checkCallerArgumentLocationConstraints(md, nametable, min,
 961       // baseLocation, constraint);
 962
 963       if (!min.getMethod().getReturnType().isVoid()) {
 964         // If method has a return value, compute the highest possible return
 965         // location in the caller's perspective
 966         // CompositeLocation ceilingLoc =
 967         // computeCeilingLocationForCaller(md, nametable, min, baseLocation,
 968         // constraint);
 969         // return ceilingLoc;
 970       }
 971     }
 972
 973     // return new CompositeLocation(Location.createTopLocation(md));
 974
 975   }
 976
 977   private NTuple<Descriptor> getArgTupleByArgIdx(MethodInvokeNode min, int idx) {
 978     return mapMethodInvokeNodeToArgIdxMap.get(min).get(new Integer(idx));
 979   }
 980
 981   private void addArgIdxMap(MethodInvokeNode min, int idx, NTuple<Descriptor> argTuple) {
 982     Map<Integer, NTuple<Descriptor>> mapIdxToArgTuple = mapMethodInvokeNodeToArgIdxMap.get(min);
 983     if (mapIdxToArgTuple == null) {
 984       mapIdxToArgTuple = new HashMap<Integer, NTuple<Descriptor>>();
 985       mapMethodInvokeNodeToArgIdxMap.put(min, mapIdxToArgTuple);
 986     }
 987     mapIdxToArgTuple.put(new Integer(idx), argTuple);
 988   }
 989
 990   private void analyzeFlowMethodParameters(MethodDescriptor callermd, SymbolTable nametable,
 991       MethodInvokeNode min) {
 992
 993     if (min.numArgs() > 0) {
 994
 995       int offset = min.getMethod().isStatic() ? 0 : 1;
 996
 997       for (int i = 0; i < min.numArgs(); i++) {
 998         ExpressionNode en = min.getArg(i);
 999         NTuple<Descriptor> argTuple =
1000             analyzeFlowExpressionNode(callermd, nametable, en, new NodeTupleSet(), false);
1001
1002         addArgIdxMap(min, i + offset, argTuple);
1003       }
1004
1005     }
1006
1007   }
1008
1009   private void analyzeLiteralNode(MethodDescriptor md, SymbolTable nametable, LiteralNode en) {
1010     // TODO Auto-generated method stub
1011
1012   }
1013
1014   private void analyzeFlowArrayAccessNode(MethodDescriptor md, SymbolTable nametable,
1015       ArrayAccessNode aan, NodeTupleSet nodeSet, boolean isLHS) {
1016
1017     NodeTupleSet expNodeTupleSet = new NodeTupleSet();
1018     analyzeFlowExpressionNode(md, nametable, aan.getExpression(), expNodeTupleSet, isLHS);
1019
1020     NodeTupleSet idxNodeTupleSet = new NodeTupleSet();
1021     analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, isLHS);
1022
1023     if (isLHS) {
1024       // need to create an edge from idx to array
1025
1026       for (Iterator<NTuple<Descriptor>> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) {
1027         NTuple<Descriptor> idxTuple = idxIter.next();
1028         for (Iterator<NTuple<Descriptor>> arrIter = expNodeTupleSet.iterator(); arrIter.hasNext();) {
1029           NTuple<Descriptor> arrTuple = arrIter.next();
1030           getFlowGraph(md).addValueFlowEdge(idxTuple, arrTuple);
1031         }
1032       }
1033
1034       nodeSet.addTupleSet(expNodeTupleSet);
1035     } else {
1036       nodeSet.addTupleSet(expNodeTupleSet);
1037       nodeSet.addTupleSet(idxNodeTupleSet);
1038     }
1039
1040   }
1041
1042   private void analyzeCreateObjectNode(MethodDescriptor md, SymbolTable nametable,
1043       CreateObjectNode en) {
1044     // TODO Auto-generated method stub
1045
1046   }
1047
1048   private void analyzeFlowOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on,
1049       NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
1050
1051     NodeTupleSet leftOpSet = new NodeTupleSet();
1052     NodeTupleSet rightOpSet = new NodeTupleSet();
1053
1054     // left operand
1055     analyzeFlowExpressionNode(md, nametable, on.getLeft(), leftOpSet, null, implicitFlowTupleSet,
1056         false);
1057
1058     if (on.getRight() != null) {
1059       // right operand
1060       analyzeFlowExpressionNode(md, nametable, on.getRight(), rightOpSet, null,
1061           implicitFlowTupleSet, false);
1062     }
1063
1064     Operation op = on.getOp();
1065
1066     switch (op.getOp()) {
1067
1068     case Operation.UNARYPLUS:
1069     case Operation.UNARYMINUS:
1070     case Operation.LOGIC_NOT:
1071       // single operand
1072       nodeSet.addTupleSet(leftOpSet);
1073       break;
1074
1075     case Operation.LOGIC_OR:
1076     case Operation.LOGIC_AND:
1077     case Operation.COMP:
1078     case Operation.BIT_OR:
1079     case Operation.BIT_XOR:
1080     case Operation.BIT_AND:
1081     case Operation.ISAVAILABLE:
1082     case Operation.EQUAL:
1083     case Operation.NOTEQUAL:
1084     case Operation.LT:
1085     case Operation.GT:
1086     case Operation.LTE:
1087     case Operation.GTE:
1088     case Operation.ADD:
1089     case Operation.SUB:
1090     case Operation.MULT:
1091     case Operation.DIV:
1092     case Operation.MOD:
1093     case Operation.LEFTSHIFT:
1094     case Operation.RIGHTSHIFT:
1095     case Operation.URIGHTSHIFT:
1096
1097       // there are two operands
1098       nodeSet.addTupleSet(leftOpSet);
1099       nodeSet.addTupleSet(rightOpSet);
1100       break;
1101
1102     default:
1103       throw new Error(op.toString());
1104     }
1105   }
1106
1107   private NTuple<Descriptor> analyzeFlowNameNode(MethodDescriptor md, SymbolTable nametable,
1108       NameNode nn, NodeTupleSet nodeSet, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
1109
1110     if (base == null) {
1111       base = new NTuple<Descriptor>();
1112     }
1113
1114     NameDescriptor nd = nn.getName();
1115
1116     if (nd.getBase() != null) {
1117       analyzeFlowExpressionNode(md, nametable, nn.getExpression(), nodeSet, base,
1118           implicitFlowTupleSet, false);
1119     } else {
1120       String varname = nd.toString();
1121       if (varname.equals("this")) {
1122         // 'this' itself!
1123         base.add(md.getThis());
1124         return base;
1125       }
1126
1127       Descriptor d = (Descriptor) nametable.get(varname);
1128
1129       if (d instanceof VarDescriptor) {
1130         VarDescriptor vd = (VarDescriptor) d;
1131         base.add(vd);
1132       } else if (d instanceof FieldDescriptor) {
1133         // the type of field descriptor has a location!
1134         FieldDescriptor fd = (FieldDescriptor) d;
1135         if (fd.isStatic()) {
1136           if (fd.isFinal()) {
1137             // if it is 'static final', the location has TOP since no one can
1138             // change its value
1139             // loc.addLocation(Location.createTopLocation(md));
1140             // return loc;
1141           } else {
1142             // if 'static', the location has pre-assigned global loc
1143             // MethodLattice<String> localLattice = ssjava.getMethodLattice(md);
1144             // String globalLocId = localLattice.getGlobalLoc();
1145             // if (globalLocId == null) {
1146             // throw new
1147             // Error("Global location element is not defined in the method " +
1148             // md);
1149             // }
1150             // Location globalLoc = new Location(md, globalLocId);
1151             //
1152             // loc.addLocation(globalLoc);
1153           }
1154         } else {
1155           // the location of field access starts from this, followed by field
1156           // location
1157           base.add(md.getThis());
1158         }
1159
1160         base.add(fd);
1161       } else if (d == null) {
1162         // access static field
1163         // FieldDescriptor fd = nn.getField();addFlowGraphEdge
1164         //
1165         // MethodLattice<String> localLattice = ssjava.getMethodLattice(md);
1166         // String globalLocId = localLattice.getGlobalLoc();
1167         // if (globalLocId == null) {
1168         // throw new
1169         // Error("Method lattice does not define global variable location at "
1170         // + generateErrorMessage(md.getClassDesc(), nn));
1171         // }
1172         // loc.addLocation(new Location(md, globalLocId));
1173         //
1174         // Location fieldLoc = (Location) fd.getType().getExtension();
1175         // loc.addLocation(fieldLoc);
1176         //
1177         // return loc;
1178
1179       }
1180     }
1181
1182     getFlowGraph(md).createNewFlowNode(base);
1183
1184     return base;
1185
1186   }
1187
1188   private NTuple<Descriptor> analyzeFlowFieldAccessNode(MethodDescriptor md, SymbolTable nametable,
1189       FieldAccessNode fan, NodeTupleSet nodeSet, NTuple<Descriptor> base,
1190       NodeTupleSet implicitFlowTupleSet) {
1191
1192     ExpressionNode left = fan.getExpression();
1193     TypeDescriptor ltd = left.getType();
1194     FieldDescriptor fd = fan.getField();
1195
1196     String varName = null;
1197     if (left.kind() == Kind.NameNode) {
1198       NameDescriptor nd = ((NameNode) left).getName();
1199       varName = nd.toString();
1200     }
1201
1202     if (ltd.isClassNameRef() || (varName != null && varName.equals("this"))) {
1203       // using a class name directly or access using this
1204       if (fd.isStatic() && fd.isFinal()) {
1205         // loc.addLocation(Location.createTopLocation(md));
1206         // return loc;
1207       }
1208     }
1209
1210     // if (left instanceof ArrayAccessNode) {
1211     // ArrayAccessNode aan = (ArrayAccessNode) left;
1212     // left = aan.getExpression();
1213     // }
1214     // fanNodeSet
1215     base =
1216         analyzeFlowExpressionNode(md, nametable, left, nodeSet, base, implicitFlowTupleSet, false);
1217
1218     if (!left.getType().isPrimitive()) {
1219
1220       if (fd.getSymbol().equals("length")) {
1221         // TODO
1222         // array.length access, return the location of the array
1223         // return loc;
1224       }
1225
1226       base.add(fd);
1227     }
1228
1229     getFlowGraph(md).createNewFlowNode(base);
1230     return base;
1231
1232   }
1233
1234   private void analyzeFlowAssignmentNode(MethodDescriptor md, SymbolTable nametable,
1235       AssignmentNode an, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
1236
1237     NodeTupleSet nodeSetRHS = new NodeTupleSet();
1238     NodeTupleSet nodeSetLHS = new NodeTupleSet();
1239
1240     boolean postinc = true;
1241     if (an.getOperation().getBaseOp() == null
1242         || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
1243             .getBaseOp().getOp() != Operation.POSTDEC)) {
1244       postinc = false;
1245     }
1246
1247     // if LHS is array access node, need to capture value flows between an array
1248     // and its index value
1249     analyzeFlowExpressionNode(md, nametable, an.getDest(), nodeSetLHS, null, implicitFlowTupleSet,
1250         true);
1251
1252     if (!postinc) {
1253       // analyze value flows of rhs expression
1254       analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null, implicitFlowTupleSet,
1255           false);
1256
1257       // creates edges from RHS to LHS
1258       for (Iterator<NTuple<Descriptor>> iter = nodeSetRHS.iterator(); iter.hasNext();) {
1259         NTuple<Descriptor> fromTuple = iter.next();
1260         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
1261           NTuple<Descriptor> toTuple = iter2.next();
1262           addFlowGraphEdge(md, fromTuple, toTuple);
1263         }
1264       }
1265
1266       // creates edges from implicitFlowTupleSet to LHS
1267       for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
1268         NTuple<Descriptor> fromTuple = iter.next();
1269         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
1270           NTuple<Descriptor> toTuple = iter2.next();
1271           addFlowGraphEdge(md, fromTuple, toTuple);
1272         }
1273       }
1274
1275     } else {
1276       // postinc case
1277       for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
1278         NTuple<Descriptor> tuple = iter2.next();
1279         addFlowGraphEdge(md, tuple, tuple);
1280       }
1281
1282     }
1283
1284   }
1285
1286   public FlowGraph getFlowGraph(MethodDescriptor md) {
1287     return mapMethodDescriptorToFlowGraph.get(md);
1288   }
1289
1290   private boolean addFlowGraphEdge(MethodDescriptor md, NTuple<Descriptor> from,
1291       NTuple<Descriptor> to) {
1292     // TODO
1293     // return true if it adds a new edge
1294     FlowGraph graph = getFlowGraph(md);
1295     graph.addValueFlowEdge(from, to);
1296     return true;
1297   }
1298
1299   public void _debug_printGraph() {
1300     Set<MethodDescriptor> keySet = mapMethodDescriptorToFlowGraph.keySet();
1301
1302     for (Iterator<MethodDescriptor> iterator = keySet.iterator(); iterator.hasNext();) {
1303       MethodDescriptor md = (MethodDescriptor) iterator.next();
1304       FlowGraph fg = mapMethodDescriptorToFlowGraph.get(md);
1305       try {
1306         fg.writeGraph();
1307       } catch (IOException e) {
1308         e.printStackTrace();
1309       }
1310     }
1311
1312   }
1313
1314 }