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