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             extractRelationFromFieldFlows(classDesc, srcNode, dstNode, 1);
 482
 483           } else {
 484             // value flow between local var - local var or local var - field
 485             addRelationToLattice(md, methodLattice, methodInfo, srcNode, dstNode);
 486           }
 487
 488           // else if (srcNodeTuple.size() == 1 || dstNodeTuple.size() == 1) {
 489           // // for the method lattice, we need to look at the first element of
 490           // // NTuple<Descriptor>
 491           // // in this case, take a look at connected nodes at the local level
 492           // addRelationToLattice(md, methodLattice, methodInfo, srcNode,
 493           // dstNode);
 494           // } else {
 495           // if
 496           // (!srcNode.getDescTuple().get(0).equals(dstNode.getDescTuple().get(0)))
 497           // {
 498           // // in this case, take a look at connected nodes at the local level
 499           // addRelationToLattice(md, methodLattice, methodInfo, srcNode,
 500           // dstNode);
 501           // } else {
 502           // Descriptor srcDesc = srcNode.getDescTuple().get(0);
 503           // Descriptor dstDesc = dstNode.getDescTuple().get(0);
 504           // recursivelyAddCompositeRelation(md, fg, methodInfo, srcNode,
 505           // dstNode, srcDesc,
 506           // dstDesc);
 507           // // recursiveAddRelationToLattice(1, md, srcNode, dstNode);
 508           // }
 509           // }
 510
 511         }
 512       }
 513     }
 514
 515     // create mapping from param idx to inferred composite location
 516
 517     int offset;
 518     if (!md.isStatic()) {
 519       // add 'this' reference location
 520       offset = 1;
 521       methodInfo.addMapParamIdxToInferLoc(0, methodInfo.getInferLocation(md.getThis()));
 522     } else {
 523       offset = 0;
 524     }
 525
 526     for (int idx = 0; idx < md.numParameters(); idx++) {
 527       Descriptor paramDesc = md.getParameter(idx);
 528       CompositeLocation inferParamLoc = methodInfo.getInferLocation(paramDesc);
 529       methodInfo.addMapParamIdxToInferLoc(idx + offset, inferParamLoc);
 530     }
 531
 532     // calculate the initial program counter location
 533     // PC location is higher than location types of all parameters
 534     String pcLocSymbol = "PCLOC";
 535     Map<Integer, CompositeLocation> mapParamToLoc = methodInfo.getMapParamIdxToInferLoc();
 536     Set<Integer> keySet = mapParamToLoc.keySet();
 537     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 538       Integer paramIdx = (Integer) iterator.next();
 539       CompositeLocation inferLoc = mapParamToLoc.get(paramIdx);
 540       String paramLocLocalSymbol = inferLoc.get(0).getLocIdentifier();
 541       if (!methodLattice.isGreaterThan(pcLocSymbol, paramLocLocalSymbol)) {
 542         addRelationHigherToLower(methodLattice, methodInfo, pcLocSymbol, paramLocLocalSymbol);
 543       }
 544     }
 545
 546     // calculate a return location
 547     // the return location type is lower than all parameters
 548     if (!md.getReturnType().isVoid()) {
 549
 550       String returnLocSymbol = "RETURNLOC";
 551
 552       for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 553         Integer paramIdx = (Integer) iterator.next();
 554         CompositeLocation inferLoc = mapParamToLoc.get(paramIdx);
 555         String paramLocLocalSymbol = inferLoc.get(0).getLocIdentifier();
 556         if (!methodLattice.isGreaterThan(paramLocLocalSymbol, returnLocSymbol)) {
 557           addRelationHigherToLower(methodLattice, methodInfo, paramLocLocalSymbol, returnLocSymbol);
 558         }
 559       }
 560     }
 561
 562   }
 563
 564   private boolean isGreaterThan(SSJavaLattice<String> methodLattice, CompositeLocation comp1,
 565       CompositeLocation comp2) {
 566
 567     int size = comp1.getSize() >= comp2.getSize() ? comp2.getSize() : comp1.getSize();
 568
 569     for (int idx = 0; idx < size; idx++) {
 570       Location loc1 = comp1.get(idx);
 571       Location loc2 = comp2.get(idx);
 572
 573       Descriptor desc1 = loc1.getDescriptor();
 574       Descriptor desc2 = loc2.getDescriptor();
 575
 576       if (!desc1.equals(desc2)) {
 577         throw new Error("Fail to compare " + comp1 + " and " + comp2);
 578       }
 579
 580       String symbol1 = loc1.getLocIdentifier();
 581       String symbol2 = loc2.getLocIdentifier();
 582
 583       SSJavaLattice<String> lattice;
 584       if (idx == 0) {
 585         lattice = methodLattice;
 586       } else {
 587         lattice = getLattice(desc1);
 588       }
 589       if (symbol1.equals(symbol2)) {
 590         continue;
 591       } else if (lattice.isGreaterThan(symbol1, symbol2)) {
 592         return true;
 593       } else {
 594         return false;
 595       }
 596
 597     }
 598
 599     return false;
 600   }
 601
 602   private void recursiveAddRelationToLattice(int idx, MethodDescriptor md,
 603       CompositeLocation srcInferLoc, CompositeLocation dstInferLoc) throws CyclicFlowException {
 604
 605     String srcLocSymbol = srcInferLoc.get(idx).getLocIdentifier();
 606     String dstLocSymbol = dstInferLoc.get(idx).getLocIdentifier();
 607
 608     if (srcLocSymbol.equals(dstLocSymbol)) {
 609       recursiveAddRelationToLattice(idx + 1, md, srcInferLoc, dstInferLoc);
 610     } else {
 611
 612       Descriptor parentDesc = srcInferLoc.get(idx).getDescriptor();
 613       LocationInfo locInfo = getLocationInfo(parentDesc);
 614
 615       addRelationHigherToLower(getLattice(parentDesc), getLocationInfo(parentDesc), srcLocSymbol,
 616           dstLocSymbol);
 617     }
 618
 619   }
 620
 621   private void analyzeLatticeMethodInvocationNode(MethodDescriptor mdCaller,
 622       SSJavaLattice<String> methodLattice, MethodLocationInfo methodInfo)
 623       throws CyclicFlowException {
 624
 625     // the transformation for a call site propagates all relations between
 626     // parameters from the callee
 627     // if the method is virtual, it also grab all relations from any possible
 628     // callees
 629
 630     Set<MethodInvokeNode> setMethodInvokeNode =
 631         mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller);
 632
 633     if (setMethodInvokeNode != null) {
 634
 635       for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) {
 636         MethodInvokeNode min = (MethodInvokeNode) iterator.next();
 637         MethodDescriptor mdCallee = min.getMethod();
 638         Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
 639         if (mdCallee.isStatic()) {
 640           setPossibleCallees.add(mdCallee);
 641         } else {
 642           Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getMethods(mdCallee);
 643           // removes method descriptors that are not invoked by the caller
 644           calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller));
 645           setPossibleCallees.addAll(calleeSet);
 646         }
 647
 648         for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
 649           MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
 650           propagateRelationToCaller(min, mdCaller, possibleMdCallee, methodLattice, methodInfo);
 651         }
 652
 653       }
 654     }
 655
 656   }
 657
 658   private void propagateRelationToCaller(MethodInvokeNode min, MethodDescriptor mdCaller,
 659       MethodDescriptor possibleMdCallee, SSJavaLattice<String> methodLattice,
 660       MethodLocationInfo methodInfo) throws CyclicFlowException {
 661
 662     SSJavaLattice<String> calleeLattice = getMethodLattice(possibleMdCallee);
 663     MethodLocationInfo calleeLocInfo = getMethodLocationInfo(possibleMdCallee);
 664     FlowGraph calleeFlowGraph = getFlowGraph(possibleMdCallee);
 665
 666     int numParam = calleeLocInfo.getNumParam();
 667     for (int i = 0; i < numParam; i++) {
 668       CompositeLocation param1 = calleeLocInfo.getParamCompositeLocation(i);
 669       for (int k = 0; k < numParam; k++) {
 670         if (i != k) {
 671           CompositeLocation param2 = calleeLocInfo.getParamCompositeLocation(k);
 672           if (isGreaterThan(getLattice(possibleMdCallee), param1, param2)) {
 673             NodeTupleSet argDescTupleSet1 = getNodeTupleSetByArgIdx(min, i);
 674             NodeTupleSet argDescTupleSet2 = getNodeTupleSetByArgIdx(min, k);
 675
 676             // the callee has the relation in which param1 is higher than param2
 677             // therefore, the caller has to have the relation in which arg1 is
 678             // higher than arg2
 679
 680             for (Iterator<NTuple<Descriptor>> iterator = argDescTupleSet1.iterator(); iterator
 681                 .hasNext();) {
 682               NTuple<Descriptor> argDescTuple1 = iterator.next();
 683
 684               for (Iterator<NTuple<Descriptor>> iterator2 = argDescTupleSet2.iterator(); iterator2
 685                   .hasNext();) {
 686                 NTuple<Descriptor> argDescTuple2 = iterator2.next();
 687
 688                 // retreive inferred location by the local var descriptor
 689
 690                 NTuple<Location> tuple1 = getFlowGraph(mdCaller).getLocationTuple(argDescTuple1);
 691                 NTuple<Location> tuple2 = getFlowGraph(mdCaller).getLocationTuple(argDescTuple2);
 692
 693                 // CompositeLocation higherInferLoc =
 694                 // methodInfo.getInferLocation(argTuple1.get(0));
 695                 // CompositeLocation lowerInferLoc =
 696                 // methodInfo.getInferLocation(argTuple2.get(0));
 697
 698                 CompositeLocation inferLoc1 = generateInferredCompositeLocation(methodInfo, tuple1);
 699                 CompositeLocation inferLoc2 = generateInferredCompositeLocation(methodInfo, tuple2);
 700
 701                 // addRelation(methodLattice, methodInfo, inferLoc1, inferLoc2);
 702
 703                 addFlowGraphEdge(mdCaller, argDescTuple1, argDescTuple2);
 704
 705               }
 706
 707             }
 708
 709           }
 710         }
 711       }
 712     }
 713
 714   }
 715
 716   private CompositeLocation generateInferredCompositeLocation(MethodLocationInfo methodInfo,
 717       NTuple<Location> tuple) {
 718
 719     // first, retrieve inferred location by the local var descriptor
 720     CompositeLocation inferLoc = new CompositeLocation();
 721
 722     CompositeLocation localVarInferLoc =
 723         methodInfo.getInferLocation(tuple.get(0).getLocDescriptor());
 724
 725     localVarInferLoc.get(0).setLocDescriptor(tuple.get(0).getLocDescriptor());
 726
 727     for (int i = 0; i < localVarInferLoc.getSize(); i++) {
 728       inferLoc.addLocation(localVarInferLoc.get(i));
 729     }
 730     // System.out.println("@@@@@localVarInferLoc=" + localVarInferLoc);
 731
 732     for (int i = 1; i < tuple.size(); i++) {
 733       Location cur = tuple.get(i);
 734       Descriptor enclosingDesc = cur.getDescriptor();
 735       Descriptor curDesc = cur.getLocDescriptor();
 736
 737       Location inferLocElement;
 738       if (curDesc == null) {
 739         // in this case, we have a newly generated location.
 740         // System.out.println("!!! generated location=" +
 741         // cur.getLocIdentifier());
 742         inferLocElement = new Location(enclosingDesc, cur.getLocIdentifier());
 743       } else {
 744         String fieldLocSymbol =
 745             getLocationInfo(enclosingDesc).getInferLocation(curDesc).get(0).getLocIdentifier();
 746         inferLocElement = new Location(enclosingDesc, fieldLocSymbol);
 747         inferLocElement.setLocDescriptor(curDesc);
 748       }
 749
 750       inferLoc.addLocation(inferLocElement);
 751
 752     }
 753
 754     assert (inferLoc.get(0).getLocDescriptor().getSymbol() == inferLoc.get(0).getLocIdentifier());
 755     return inferLoc;
 756   }
 757
 758   private void addRelation(SSJavaLattice<String> methodLattice, MethodLocationInfo methodInfo,
 759       CompositeLocation srcInferLoc, CompositeLocation dstInferLoc) throws CyclicFlowException {
 760
 761     System.out.println("addRelation --- srcInferLoc=" + srcInferLoc + "  dstInferLoc="
 762         + dstInferLoc);
 763     String srcLocalLocSymbol = srcInferLoc.get(0).getLocIdentifier();
 764     String dstLocalLocSymbol = dstInferLoc.get(0).getLocIdentifier();
 765
 766     if (srcInferLoc.getSize() == 1 && dstInferLoc.getSize() == 1) {
 767       // add a new relation to the local lattice
 768       addRelationHigherToLower(methodLattice, methodInfo, srcLocalLocSymbol, dstLocalLocSymbol);
 769     } else if (srcInferLoc.getSize() > 1 && dstInferLoc.getSize() > 1) {
 770       // both src and dst have assigned to a composite location
 771
 772       if (!srcLocalLocSymbol.equals(dstLocalLocSymbol)) {
 773         addRelationHigherToLower(methodLattice, methodInfo, srcLocalLocSymbol, dstLocalLocSymbol);
 774       } else {
 775         recursivelyAddRelation(1, srcInferLoc, dstInferLoc);
 776       }
 777     } else {
 778       // either src or dst has assigned to a composite location
 779       if (!srcLocalLocSymbol.equals(dstLocalLocSymbol)) {
 780         addRelationHigherToLower(methodLattice, methodInfo, srcLocalLocSymbol, dstLocalLocSymbol);
 781       }
 782     }
 783
 784     System.out.println();
 785
 786   }
 787
 788   public LocationInfo getLocationInfo(Descriptor d) {
 789     if (d instanceof MethodDescriptor) {
 790       return getMethodLocationInfo((MethodDescriptor) d);
 791     } else {
 792       return getFieldLocationInfo((ClassDescriptor) d);
 793     }
 794   }
 795
 796   private MethodLocationInfo getMethodLocationInfo(MethodDescriptor md) {
 797
 798     if (!mapMethodDescToMethodLocationInfo.containsKey(md)) {
 799       mapMethodDescToMethodLocationInfo.put(md, new MethodLocationInfo(md));
 800     }
 801
 802     return mapMethodDescToMethodLocationInfo.get(md);
 803
 804   }
 805
 806   private LocationInfo getFieldLocationInfo(ClassDescriptor cd) {
 807
 808     if (!mapClassToLocationInfo.containsKey(cd)) {
 809       mapClassToLocationInfo.put(cd, new LocationInfo(cd));
 810     }
 811
 812     return mapClassToLocationInfo.get(cd);
 813
 814   }
 815
 816   private void addRelationToLattice(MethodDescriptor md, SSJavaLattice<String> methodLattice,
 817       MethodLocationInfo methodInfo, FlowNode srcNode, FlowNode dstNode) throws CyclicFlowException {
 818
 819     System.out.println();
 820     System.out.println("### addRelationToLattice src=" + srcNode + " dst=" + dstNode);
 821
 822     // add a new binary relation of dstNode < srcNode
 823     FlowGraph flowGraph = getFlowGraph(md);
 824     try {
 825       System.out.println("***** src composite case::");
 826       calculateCompositeLocation(flowGraph, methodLattice, methodInfo, srcNode);
 827
 828       CompositeLocation srcInferLoc =
 829           generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(srcNode));
 830       CompositeLocation dstInferLoc =
 831           generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(dstNode));
 832       addRelation(methodLattice, methodInfo, srcInferLoc, dstInferLoc);
 833     } catch (CyclicFlowException e) {
 834       // there is a cyclic value flow... try to calculate a composite location
 835       // for the destination node
 836       System.out.println("***** dst composite case::");
 837       calculateCompositeLocation(flowGraph, methodLattice, methodInfo, dstNode);
 838       CompositeLocation srcInferLoc =
 839           generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(srcNode));
 840       CompositeLocation dstInferLoc =
 841           generateInferredCompositeLocation(methodInfo, flowGraph.getLocationTuple(dstNode));
 842       try {
 843         addRelation(methodLattice, methodInfo, srcInferLoc, dstInferLoc);
 844       } catch (CyclicFlowException e1) {
 845         throw new Error("Failed to merge cyclic value flows into a shared location.");
 846       }
 847     }
 848
 849   }
 850
 851   private void recursivelyAddRelation(int idx, CompositeLocation srcInferLoc,
 852       CompositeLocation dstInferLoc) throws CyclicFlowException {
 853
 854     String srcLocSymbol = srcInferLoc.get(idx).getLocIdentifier();
 855     String dstLocSymbol = dstInferLoc.get(idx).getLocIdentifier();
 856
 857     Descriptor parentDesc = srcInferLoc.get(idx).getDescriptor();
 858
 859     if (srcLocSymbol.equals(dstLocSymbol)) {
 860       // check if it is the case of shared location
 861       if (srcInferLoc.getSize() == (idx + 1) && dstInferLoc.getSize() == (idx + 1)) {
 862         Location inferLocElement = srcInferLoc.get(idx);
 863         System.out.println("SET SHARED LOCATION=" + inferLocElement);
 864         getLattice(inferLocElement.getDescriptor())
 865             .addSharedLoc(inferLocElement.getLocIdentifier());
 866       } else if (srcInferLoc.getSize() > (idx + 1) && dstInferLoc.getSize() > (idx + 1)) {
 867         recursivelyAddRelation(idx + 1, srcInferLoc, dstInferLoc);
 868       }
 869     } else {
 870       addRelationHigherToLower(getLattice(parentDesc), getLocationInfo(parentDesc), srcLocSymbol,
 871           dstLocSymbol);
 872     }
 873   }
 874
 875   private void recursivelyAddCompositeRelation(MethodDescriptor md, FlowGraph flowGraph,
 876       MethodLocationInfo methodInfo, FlowNode srcNode, FlowNode dstNode, Descriptor srcDesc,
 877       Descriptor dstDesc) throws CyclicFlowException {
 878
 879     CompositeLocation inferSrcLoc;
 880     CompositeLocation inferDstLoc = methodInfo.getInferLocation(dstDesc);
 881
 882     if (srcNode.getDescTuple().size() > 1) {
 883       // field access
 884       inferSrcLoc = new CompositeLocation();
 885
 886       NTuple<Location> locTuple = flowGraph.getLocationTuple(srcNode);
 887       for (int i = 0; i < locTuple.size(); i++) {
 888         inferSrcLoc.addLocation(locTuple.get(i));
 889       }
 890
 891     } else {
 892       inferSrcLoc = methodInfo.getInferLocation(srcDesc);
 893     }
 894
 895     if (dstNode.getDescTuple().size() > 1) {
 896       // field access
 897       inferDstLoc = new CompositeLocation();
 898
 899       NTuple<Location> locTuple = flowGraph.getLocationTuple(dstNode);
 900       for (int i = 0; i < locTuple.size(); i++) {
 901         inferDstLoc.addLocation(locTuple.get(i));
 902       }
 903
 904     } else {
 905       inferDstLoc = methodInfo.getInferLocation(dstDesc);
 906     }
 907
 908     recursiveAddRelationToLattice(1, md, inferSrcLoc, inferDstLoc);
 909   }
 910
 911   private void addPrefixMapping(Map<NTuple<Location>, Set<NTuple<Location>>> map,
 912       NTuple<Location> prefix, NTuple<Location> element) {
 913
 914     if (!map.containsKey(prefix)) {
 915       map.put(prefix, new HashSet<NTuple<Location>>());
 916     }
 917     map.get(prefix).add(element);
 918   }
 919
 920   private boolean calculateCompositeLocation(FlowGraph flowGraph,
 921       SSJavaLattice<String> methodLattice, MethodLocationInfo methodInfo, FlowNode flowNode)
 922       throws CyclicFlowException {
 923
 924     Descriptor localVarDesc = flowNode.getDescTuple().get(0);
 925     NTuple<Location> flowNodelocTuple = flowGraph.getLocationTuple(flowNode);
 926
 927     if (localVarDesc.equals(methodInfo.getMethodDesc())) {
 928       return false;
 929     }
 930
 931     Set<FlowNode> inNodeSet = flowGraph.getIncomingFlowNodeSet(flowNode);
 932     Set<FlowNode> reachableNodeSet = flowGraph.getReachableFlowNodeSet(flowNode);
 933
 934     Map<NTuple<Location>, Set<NTuple<Location>>> mapPrefixToIncomingLocTupleSet =
 935         new HashMap<NTuple<Location>, Set<NTuple<Location>>>();
 936
 937     List<NTuple<Location>> prefixList = new ArrayList<NTuple<Location>>();
 938
 939     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
 940       FlowNode inNode = (FlowNode) iterator.next();
 941       NTuple<Location> inNodeTuple = flowGraph.getLocationTuple(inNode);
 942
 943       CompositeLocation inNodeInferredLoc =
 944           generateInferredCompositeLocation(methodInfo, inNodeTuple);
 945
 946       NTuple<Location> inNodeInferredLocTuple = inNodeInferredLoc.getTuple();
 947
 948       for (int i = 1; i < inNodeInferredLocTuple.size(); i++) {
 949         NTuple<Location> prefix = inNodeInferredLocTuple.subList(0, i);
 950         if (!prefixList.contains(prefix)) {
 951           prefixList.add(prefix);
 952         }
 953         addPrefixMapping(mapPrefixToIncomingLocTupleSet, prefix, inNodeInferredLocTuple);
 954       }
 955     }
 956
 957     Collections.sort(prefixList, new Comparator<NTuple<Location>>() {
 958       public int compare(NTuple<Location> arg0, NTuple<Location> arg1) {
 959         int s0 = arg0.size();
 960         int s1 = arg1.size();
 961         if (s0 > s1) {
 962           return -1;
 963         } else if (s0 == s1) {
 964           return 0;
 965         } else {
 966           return 1;
 967         }
 968       }
 969     });
 970
 971     // find out reachable nodes that have the longest common prefix
 972     for (int i = 0; i < prefixList.size(); i++) {
 973       NTuple<Location> curPrefix = prefixList.get(i);
 974       Set<NTuple<Location>> reachableCommonPrefixSet = new HashSet<NTuple<Location>>();
 975
 976       for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
 977         FlowNode reachableNode = (FlowNode) iterator2.next();
 978         NTuple<Location> reachLocTuple = flowGraph.getLocationTuple(reachableNode);
 979         CompositeLocation reachLocInferLoc =
 980             generateInferredCompositeLocation(methodInfo, reachLocTuple);
 981         if (reachLocInferLoc.getTuple().startsWith(curPrefix)) {
 982           reachableCommonPrefixSet.add(reachLocTuple);
 983         }
 984       }
 985
 986       if (!reachableCommonPrefixSet.isEmpty()) {
 987         // found reachable nodes that start with the prefix curPrefix
 988         // need to assign a composite location
 989
 990         // first, check if there are more than one the set of locations that has
 991         // the same length of the longest reachable prefix, no way to assign
 992         // a composite location to the input local var
 993         prefixSanityCheck(prefixList, i, flowGraph, reachableNodeSet);
 994
 995         Set<NTuple<Location>> incomingCommonPrefixSet =
 996             mapPrefixToIncomingLocTupleSet.get(curPrefix);
 997
 998         int idx = curPrefix.size();
 999         NTuple<Location> element = incomingCommonPrefixSet.iterator().next();
1000         Descriptor desc = element.get(idx).getDescriptor();
1001
1002         SSJavaLattice<String> lattice = getLattice(desc);
1003         LocationInfo locInfo = getLocationInfo(desc);
1004
1005         CompositeLocation inferLocation =
1006             generateInferredCompositeLocation(methodInfo, flowNodelocTuple);
1007
1008         // methodInfo.getInferLocation(localVarDesc);
1009         CompositeLocation newInferLocation = new CompositeLocation();
1010
1011         if (inferLocation.getTuple().startsWith(curPrefix)) {
1012           // the same infer location is already existed. no need to do
1013           // anything
1014           return true;
1015         } else {
1016           // assign a new composite location
1017
1018           // String oldMethodLocationSymbol =
1019           // inferLocation.get(0).getLocIdentifier();
1020           String newLocSymbol = "Loc" + (SSJavaLattice.seed++);
1021           for (int locIdx = 0; locIdx < curPrefix.size(); locIdx++) {
1022             newInferLocation.addLocation(curPrefix.get(locIdx));
1023           }
1024           Location newLocationElement = new Location(desc, newLocSymbol);
1025           newInferLocation.addLocation(newLocationElement);
1026
1027           // maps local variable to location types of the common prefix
1028           methodInfo.mapDescriptorToLocation(localVarDesc, newInferLocation.clone());
1029
1030           // methodInfo.mapDescriptorToLocation(localVarDesc, newInferLocation);
1031           addMapLocSymbolToInferredLocation(methodInfo.getMethodDesc(), localVarDesc,
1032               newInferLocation);
1033           methodInfo.removeMaplocalVarToLocSet(localVarDesc);
1034
1035           // add the field/var descriptor to the set of the location symbol
1036           int lastIdx = flowNode.getDescTuple().size() - 1;
1037           Descriptor lastFlowNodeDesc = flowNode.getDescTuple().get(lastIdx);
1038           Descriptor enclosinglastLastFlowNodeDesc = flowNodelocTuple.get(lastIdx).getDescriptor();
1039
1040           CompositeLocation newlyInferredLocForFlowNode =
1041               generateInferredCompositeLocation(methodInfo, flowNodelocTuple);
1042           Location lastInferLocElement =
1043               newlyInferredLocForFlowNode.get(newlyInferredLocForFlowNode.getSize() - 1);
1044           Descriptor enclosingLastInferLocElement = lastInferLocElement.getDescriptor();
1045
1046           // getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToDescSet(
1047           // lastInferLocElement.getLocIdentifier(), lastFlowNodeDesc);
1048           getLocationInfo(enclosingLastInferLocElement).addMapLocSymbolToRelatedInferLoc(
1049               lastInferLocElement.getLocIdentifier(), enclosinglastLastFlowNodeDesc,
1050               lastFlowNodeDesc);
1051
1052           // clean up the previous location
1053           // Location prevInferLocElement =
1054           // inferLocation.get(inferLocation.getSize() - 1);
1055           // Descriptor prevEnclosingDesc = prevInferLocElement.getDescriptor();
1056           //
1057           // SSJavaLattice<String> targetLattice;
1058           // LocationInfo targetInfo;
1059           // if (prevEnclosingDesc.equals(methodInfo.getMethodDesc())) {
1060           // targetLattice = methodLattice;
1061           // targetInfo = methodInfo;
1062           // } else {
1063           // targetLattice = getLattice(prevInferLocElement.getDescriptor());
1064           // targetInfo = getLocationInfo(prevInferLocElement.getDescriptor());
1065           // }
1066           //
1067           // Set<Pair<Descriptor, Descriptor>> associstedDescSet =
1068           // targetInfo.getRelatedInferLocSet(prevInferLocElement.getLocIdentifier());
1069           //
1070           // if (associstedDescSet.size() == 1) {
1071           // targetLattice.remove(prevInferLocElement.getLocIdentifier());
1072           // } else {
1073           // associstedDescSet.remove(lastFlowNodeDesc);
1074           // }
1075
1076         }
1077
1078         System.out.println("ASSIGN NEW COMPOSITE LOCATION =" + newInferLocation + "    to "
1079             + flowNode);
1080
1081         String newlyInsertedLocName =
1082             newInferLocation.get(newInferLocation.getSize() - 1).getLocIdentifier();
1083
1084         System.out.println("-- add in-flow");
1085         for (Iterator iterator = incomingCommonPrefixSet.iterator(); iterator.hasNext();) {
1086           NTuple<Location> tuple = (NTuple<Location>) iterator.next();
1087           Location loc = tuple.get(idx);
1088           String higher = loc.getLocIdentifier();
1089           addRelationHigherToLower(lattice, locInfo, higher, newlyInsertedLocName);
1090         }
1091
1092         System.out.println("-- add out flow");
1093         for (Iterator iterator = reachableCommonPrefixSet.iterator(); iterator.hasNext();) {
1094           NTuple<Location> tuple = (NTuple<Location>) iterator.next();
1095           if (tuple.size() > idx) {
1096             Location loc = tuple.get(idx);
1097             String lower = loc.getLocIdentifier();
1098             // String lower =
1099             // locInfo.getFieldInferLocation(loc.getLocDescriptor()).getLocIdentifier();
1100             addRelationHigherToLower(lattice, locInfo, newlyInsertedLocName, lower);
1101           }
1102         }
1103
1104         return true;
1105       }
1106
1107     }
1108
1109     return false;
1110
1111   }
1112
1113   private void addMapLocSymbolToInferredLocation(MethodDescriptor md, Descriptor localVar,
1114       CompositeLocation inferLoc) {
1115
1116     Location locElement = inferLoc.get((inferLoc.getSize() - 1));
1117     Descriptor enclosingDesc = locElement.getDescriptor();
1118     LocationInfo locInfo = getLocationInfo(enclosingDesc);
1119     locInfo.addMapLocSymbolToRelatedInferLoc(locElement.getLocIdentifier(), md, localVar);
1120   }
1121
1122   private boolean isCompositeLocation(CompositeLocation cl) {
1123     return cl.getSize() > 1;
1124   }
1125
1126   private boolean containsNonPrimitiveElement(Set<Descriptor> descSet) {
1127     for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
1128       Descriptor desc = (Descriptor) iterator.next();
1129
1130       if (desc.equals(LocationInference.GLOBALDESC)) {
1131         return true;
1132       } else if (desc instanceof VarDescriptor) {
1133         if (!((VarDescriptor) desc).getType().isPrimitive()) {
1134           return true;
1135         }
1136       } else if (desc instanceof FieldDescriptor) {
1137         if (!((FieldDescriptor) desc).getType().isPrimitive()) {
1138           return true;
1139         }
1140       }
1141
1142     }
1143     return false;
1144   }
1145
1146   private void addRelationHigherToLower(SSJavaLattice<String> lattice, LocationInfo locInfo,
1147       String higher, String lower) throws CyclicFlowException {
1148
1149     System.out.println("---addRelationHigherToLower " + higher + " -> " + lower
1150         + " to the lattice of " + locInfo.getDescIdentifier());
1151     // if (higher.equals(lower) && lattice.isSharedLoc(higher)) {
1152     // return;
1153     // }
1154     Set<String> cycleElementSet = lattice.getPossibleCycleElements(higher, lower);
1155
1156     boolean hasNonPrimitiveElement = false;
1157     for (Iterator iterator = cycleElementSet.iterator(); iterator.hasNext();) {
1158       String cycleElementLocSymbol = (String) iterator.next();
1159
1160       Set<Descriptor> descSet = locInfo.getDescSet(cycleElementLocSymbol);
1161       if (containsNonPrimitiveElement(descSet)) {
1162         hasNonPrimitiveElement = true;
1163         break;
1164       }
1165     }
1166
1167     if (hasNonPrimitiveElement) {
1168       System.out.println("#Check cycle= " + lower + " < " + higher + "     cycleElementSet="
1169           + cycleElementSet);
1170       // if there is non-primitive element in the cycle, no way to merge cyclic
1171       // elements into the shared location
1172       throw new CyclicFlowException();
1173     }
1174
1175     if (cycleElementSet.size() > 0) {
1176
1177       String newSharedLoc = "SharedLoc" + (SSJavaLattice.seed++);
1178
1179       System.out.println("---ASSIGN NEW SHARED LOC=" + newSharedLoc + "   to  " + cycleElementSet);
1180       lattice.mergeIntoSharedLocation(cycleElementSet, newSharedLoc);
1181
1182       for (Iterator iterator = cycleElementSet.iterator(); iterator.hasNext();) {
1183         String oldLocSymbol = (String) iterator.next();
1184
1185         Set<Pair<Descriptor, Descriptor>> inferLocSet = locInfo.getRelatedInferLocSet(oldLocSymbol);
1186         System.out.println("---update related locations=" + inferLocSet);
1187         for (Iterator iterator2 = inferLocSet.iterator(); iterator2.hasNext();) {
1188           Pair<Descriptor, Descriptor> pair = (Pair<Descriptor, Descriptor>) iterator2.next();
1189           Descriptor enclosingDesc = pair.getFirst();
1190           Descriptor desc = pair.getSecond();
1191
1192           CompositeLocation inferLoc;
1193           if (curMethodInfo.md.equals(enclosingDesc)) {
1194             inferLoc = curMethodInfo.getInferLocation(desc);
1195           } else {
1196             inferLoc = getLocationInfo(enclosingDesc).getInferLocation(desc);
1197           }
1198
1199           Location locElement = inferLoc.get(inferLoc.getSize() - 1);
1200
1201           locElement.setLocIdentifier(newSharedLoc);
1202           locInfo.addMapLocSymbolToRelatedInferLoc(newSharedLoc, enclosingDesc, desc);
1203
1204           if (curMethodInfo.md.equals(enclosingDesc)) {
1205             inferLoc = curMethodInfo.getInferLocation(desc);
1206           } else {
1207             inferLoc = getLocationInfo(enclosingDesc).getInferLocation(desc);
1208           }
1209           System.out.println("---New Infer Loc=" + inferLoc);
1210
1211         }
1212         locInfo.removeRelatedInferLocSet(oldLocSymbol, newSharedLoc);
1213
1214       }
1215
1216       lattice.addSharedLoc(newSharedLoc);
1217
1218     } else if (!lattice.isGreaterThan(higher, lower)) {
1219       lattice.addRelationHigherToLower(higher, lower);
1220     }
1221   }
1222
1223   private void replaceOldLocWithNewLoc(SSJavaLattice<String> methodLattice, String oldLocSymbol,
1224       String newLocSymbol) {
1225
1226     if (methodLattice.containsKey(oldLocSymbol)) {
1227       methodLattice.substituteLocation(oldLocSymbol, newLocSymbol);
1228     }
1229
1230   }
1231
1232   private void prefixSanityCheck(List<NTuple<Location>> prefixList, int curIdx,
1233       FlowGraph flowGraph, Set<FlowNode> reachableNodeSet) {
1234
1235     NTuple<Location> curPrefix = prefixList.get(curIdx);
1236
1237     for (int i = curIdx + 1; i < prefixList.size(); i++) {
1238       NTuple<Location> prefixTuple = prefixList.get(i);
1239
1240       if (curPrefix.startsWith(prefixTuple)) {
1241         continue;
1242       }
1243
1244       for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
1245         FlowNode reachableNode = (FlowNode) iterator2.next();
1246         NTuple<Location> reachLocTuple = flowGraph.getLocationTuple(reachableNode);
1247         if (reachLocTuple.startsWith(prefixTuple)) {
1248           // TODO
1249           throw new Error("Failed to generate a composite location");
1250         }
1251       }
1252     }
1253   }
1254
1255   public boolean isPrimitiveLocalVariable(FlowNode node) {
1256     VarDescriptor varDesc = (VarDescriptor) node.getDescTuple().get(0);
1257     return varDesc.getType().isPrimitive();
1258   }
1259
1260   private SSJavaLattice<String> getLattice(Descriptor d) {
1261     if (d instanceof MethodDescriptor) {
1262       return getMethodLattice((MethodDescriptor) d);
1263     } else {
1264       return getFieldLattice((ClassDescriptor) d);
1265     }
1266   }
1267
1268   private SSJavaLattice<String> getMethodLattice(MethodDescriptor md) {
1269     if (!md2lattice.containsKey(md)) {
1270       md2lattice.put(md, new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM));
1271     }
1272     return md2lattice.get(md);
1273   }
1274
1275   private void setMethodLattice(MethodDescriptor md, SSJavaLattice<String> lattice) {
1276     md2lattice.put(md, lattice);
1277   }
1278
1279   private void extractRelationFromFieldFlows(ClassDescriptor cd, FlowNode srcNode,
1280       FlowNode dstNode, int idx) throws CyclicFlowException {
1281
1282     if (srcNode.getDescTuple().get(idx).equals(dstNode.getDescTuple().get(idx))
1283         && srcNode.getDescTuple().size() > (idx + 1) && dstNode.getDescTuple().size() > (idx + 1)) {
1284       // value flow between fields: we don't need to add a binary relation
1285       // for this case
1286
1287       Descriptor desc = srcNode.getDescTuple().get(idx);
1288       ClassDescriptor classDesc;
1289
1290       if (idx == 0) {
1291         classDesc = ((VarDescriptor) desc).getType().getClassDesc();
1292       } else {
1293         classDesc = ((FieldDescriptor) desc).getType().getClassDesc();
1294       }
1295
1296       extractRelationFromFieldFlows(classDesc, srcNode, dstNode, idx + 1);
1297
1298     } else {
1299
1300       Descriptor srcFieldDesc = srcNode.getDescTuple().get(idx);
1301       Descriptor dstFieldDesc = dstNode.getDescTuple().get(idx);
1302
1303       // add a new binary relation of dstNode < srcNode
1304       SSJavaLattice<String> fieldLattice = getFieldLattice(cd);
1305       LocationInfo fieldInfo = getFieldLocationInfo(cd);
1306
1307       String srcSymbol = fieldInfo.getFieldInferLocation(srcFieldDesc).getLocIdentifier();
1308       String dstSymbol = fieldInfo.getFieldInferLocation(dstFieldDesc).getLocIdentifier();
1309
1310       addRelationHigherToLower(fieldLattice, fieldInfo, srcSymbol, dstSymbol);
1311
1312     }
1313
1314   }
1315
1316   public SSJavaLattice<String> getFieldLattice(ClassDescriptor cd) {
1317     if (!cd2lattice.containsKey(cd)) {
1318       cd2lattice.put(cd, new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM));
1319     }
1320     return cd2lattice.get(cd);
1321   }
1322
1323   public void constructFlowGraph() {
1324
1325     setupToAnalyze();
1326
1327     Set<MethodDescriptor> visited = new HashSet<MethodDescriptor>();
1328     Set<MethodDescriptor> reachableCallee = new HashSet<MethodDescriptor>();
1329
1330     while (!toAnalyzeIsEmpty()) {
1331       ClassDescriptor cd = toAnalyzeNext();
1332
1333       setupToAnalazeMethod(cd);
1334       toanalyzeMethodList.removeAll(visited);
1335
1336       while (!toAnalyzeMethodIsEmpty()) {
1337         MethodDescriptor md = toAnalyzeMethodNext();
1338         if ((!visited.contains(md))
1339             && (ssjava.needTobeAnnotated(md) || reachableCallee.contains(md))) {
1340           if (state.SSJAVADEBUG) {
1341             System.out.println();
1342             System.out.println("SSJAVA: Constructing a flow graph: " + md);
1343           }
1344
1345           // creates a mapping from a method descriptor to virtual methods
1346           Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
1347           if (md.isStatic()) {
1348             setPossibleCallees.add(md);
1349           } else {
1350             setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md));
1351           }
1352
1353           Set<MethodDescriptor> calleeSet = ssjava.getCallGraph().getCalleeSet(md);
1354           Set<MethodDescriptor> needToAnalyzeCalleeSet = new HashSet<MethodDescriptor>();
1355
1356           for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) {
1357             MethodDescriptor calleemd = (MethodDescriptor) iterator.next();
1358             if ((!ssjava.isTrustMethod(calleemd))
1359                 && (!ssjava.isSSJavaUtil(calleemd.getClassDesc()))) {
1360               if (!visited.contains(calleemd)) {
1361                 toanalyzeMethodList.add(calleemd);
1362               }
1363               reachableCallee.add(calleemd);
1364               needToAnalyzeCalleeSet.add(calleemd);
1365             }
1366           }
1367
1368           mapMethodToCalleeSet.put(md, needToAnalyzeCalleeSet);
1369
1370           // creates a mapping from a parameter descriptor to its index
1371           Map<Descriptor, Integer> mapParamDescToIdx = new HashMap<Descriptor, Integer>();
1372           int offset = md.isStatic() ? 0 : 1;
1373           for (int i = 0; i < md.numParameters(); i++) {
1374             Descriptor paramDesc = (Descriptor) md.getParameter(i);
1375             mapParamDescToIdx.put(paramDesc, new Integer(i + offset));
1376           }
1377
1378           FlowGraph fg = new FlowGraph(md, mapParamDescToIdx);
1379           mapMethodDescriptorToFlowGraph.put(md, fg);
1380
1381           visited.add(md);
1382           analyzeMethodBody(cd, md);
1383
1384         }
1385       }
1386     }
1387
1388     _debug_printGraph();
1389   }
1390
1391   private void analyzeMethodBody(ClassDescriptor cd, MethodDescriptor md) {
1392     BlockNode bn = state.getMethodBody(md);
1393     NodeTupleSet implicitFlowTupleSet = new NodeTupleSet();
1394     analyzeFlowBlockNode(md, md.getParameterTable(), bn, implicitFlowTupleSet);
1395   }
1396
1397   private void analyzeFlowBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn,
1398       NodeTupleSet implicitFlowTupleSet) {
1399
1400     bn.getVarTable().setParent(nametable);
1401     for (int i = 0; i < bn.size(); i++) {
1402       BlockStatementNode bsn = bn.get(i);
1403       analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet);
1404     }
1405
1406   }
1407
1408   private void analyzeBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
1409       BlockStatementNode bsn, NodeTupleSet implicitFlowTupleSet) {
1410
1411     switch (bsn.kind()) {
1412     case Kind.BlockExpressionNode:
1413       analyzeBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn, implicitFlowTupleSet);
1414       break;
1415
1416     case Kind.DeclarationNode:
1417       analyzeFlowDeclarationNode(md, nametable, (DeclarationNode) bsn, implicitFlowTupleSet);
1418       break;
1419
1420     case Kind.IfStatementNode:
1421       analyzeFlowIfStatementNode(md, nametable, (IfStatementNode) bsn, implicitFlowTupleSet);
1422       break;
1423
1424     case Kind.LoopNode:
1425       analyzeFlowLoopNode(md, nametable, (LoopNode) bsn, implicitFlowTupleSet);
1426       break;
1427
1428     case Kind.ReturnNode:
1429       analyzeFlowReturnNode(md, nametable, (ReturnNode) bsn, implicitFlowTupleSet);
1430       break;
1431
1432     case Kind.SubBlockNode:
1433       analyzeFlowSubBlockNode(md, nametable, (SubBlockNode) bsn, implicitFlowTupleSet);
1434       break;
1435
1436     case Kind.ContinueBreakNode:
1437       break;
1438
1439     case Kind.SwitchStatementNode:
1440       analyzeSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn);
1441       break;
1442
1443     }
1444
1445   }
1446
1447   private void analyzeSwitchStatementNode(MethodDescriptor md, SymbolTable nametable,
1448       SwitchStatementNode bsn) {
1449     // TODO Auto-generated method stub
1450   }
1451
1452   private void analyzeFlowSubBlockNode(MethodDescriptor md, SymbolTable nametable,
1453       SubBlockNode sbn, NodeTupleSet implicitFlowTupleSet) {
1454     analyzeFlowBlockNode(md, nametable, sbn.getBlockNode(), implicitFlowTupleSet);
1455   }
1456
1457   private void analyzeFlowReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode rn,
1458       NodeTupleSet implicitFlowTupleSet) {
1459
1460     ExpressionNode returnExp = rn.getReturnExpression();
1461
1462     if (returnExp != null) {
1463       NodeTupleSet nodeSet = new NodeTupleSet();
1464       analyzeFlowExpressionNode(md, nametable, returnExp, nodeSet, false);
1465
1466       FlowGraph fg = getFlowGraph(md);
1467
1468       // annotate the elements of the node set as the return location
1469       for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1470         NTuple<Descriptor> returnDescTuple = (NTuple<Descriptor>) iterator.next();
1471         fg.setReturnFlowNode(returnDescTuple);
1472         for (Iterator iterator2 = implicitFlowTupleSet.iterator(); iterator2.hasNext();) {
1473           NTuple<Descriptor> implicitFlowDescTuple = (NTuple<Descriptor>) iterator2.next();
1474           fg.addValueFlowEdge(implicitFlowDescTuple, returnDescTuple);
1475         }
1476       }
1477     }
1478
1479   }
1480
1481   private void analyzeFlowLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln,
1482       NodeTupleSet implicitFlowTupleSet) {
1483
1484     if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) {
1485
1486       NodeTupleSet condTupleNode = new NodeTupleSet();
1487       analyzeFlowExpressionNode(md, nametable, ln.getCondition(), condTupleNode, null,
1488           implicitFlowTupleSet, false);
1489       condTupleNode.addTupleSet(implicitFlowTupleSet);
1490
1491       // add edges from condNodeTupleSet to all nodes of conditional nodes
1492       analyzeFlowBlockNode(md, nametable, ln.getBody(), condTupleNode);
1493
1494     } else {
1495       // check 'for loop' case
1496       BlockNode bn = ln.getInitializer();
1497       bn.getVarTable().setParent(nametable);
1498       for (int i = 0; i < bn.size(); i++) {
1499         BlockStatementNode bsn = bn.get(i);
1500         analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet);
1501       }
1502
1503       NodeTupleSet condTupleNode = new NodeTupleSet();
1504       analyzeFlowExpressionNode(md, bn.getVarTable(), ln.getCondition(), condTupleNode, null,
1505           implicitFlowTupleSet, false);
1506       condTupleNode.addTupleSet(implicitFlowTupleSet);
1507
1508       analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(), condTupleNode);
1509       analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(), condTupleNode);
1510
1511     }
1512
1513   }
1514
1515   private void analyzeFlowIfStatementNode(MethodDescriptor md, SymbolTable nametable,
1516       IfStatementNode isn, NodeTupleSet implicitFlowTupleSet) {
1517
1518     NodeTupleSet condTupleNode = new NodeTupleSet();
1519     analyzeFlowExpressionNode(md, nametable, isn.getCondition(), condTupleNode, null,
1520         implicitFlowTupleSet, false);
1521
1522     // add edges from condNodeTupleSet to all nodes of conditional nodes
1523     condTupleNode.addTupleSet(implicitFlowTupleSet);
1524     analyzeFlowBlockNode(md, nametable, isn.getTrueBlock(), condTupleNode);
1525
1526     if (isn.getFalseBlock() != null) {
1527       analyzeFlowBlockNode(md, nametable, isn.getFalseBlock(), condTupleNode);
1528     }
1529
1530   }
1531
1532   private void analyzeFlowDeclarationNode(MethodDescriptor md, SymbolTable nametable,
1533       DeclarationNode dn, NodeTupleSet implicitFlowTupleSet) {
1534
1535     VarDescriptor vd = dn.getVarDescriptor();
1536     NTuple<Descriptor> tupleLHS = new NTuple<Descriptor>();
1537     tupleLHS.add(vd);
1538     getFlowGraph(md).createNewFlowNode(tupleLHS);
1539
1540     if (dn.getExpression() != null) {
1541
1542       NodeTupleSet tupleSetRHS = new NodeTupleSet();
1543       analyzeFlowExpressionNode(md, nametable, dn.getExpression(), tupleSetRHS, null,
1544           implicitFlowTupleSet, false);
1545
1546       // add a new flow edge from rhs to lhs
1547       for (Iterator<NTuple<Descriptor>> iter = tupleSetRHS.iterator(); iter.hasNext();) {
1548         NTuple<Descriptor> from = iter.next();
1549         addFlowGraphEdge(md, from, tupleLHS);
1550       }
1551
1552     }
1553
1554   }
1555
1556   private void analyzeBlockExpressionNode(MethodDescriptor md, SymbolTable nametable,
1557       BlockExpressionNode ben, NodeTupleSet implicitFlowTupleSet) {
1558     analyzeFlowExpressionNode(md, nametable, ben.getExpression(), null, null, implicitFlowTupleSet,
1559         false);
1560   }
1561
1562   private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
1563       ExpressionNode en, NodeTupleSet nodeSet, boolean isLHS) {
1564     return analyzeFlowExpressionNode(md, nametable, en, nodeSet, null, new NodeTupleSet(), isLHS);
1565   }
1566
1567   private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
1568       ExpressionNode en, NodeTupleSet nodeSet, NTuple<Descriptor> base,
1569       NodeTupleSet implicitFlowTupleSet, boolean isLHS) {
1570
1571     // note that expression node can create more than one flow node
1572     // nodeSet contains of flow nodes
1573     // base is always assigned to null except the case of a name node!
1574
1575     NTuple<Descriptor> flowTuple;
1576
1577     switch (en.kind()) {
1578
1579     case Kind.AssignmentNode:
1580       analyzeFlowAssignmentNode(md, nametable, (AssignmentNode) en, nodeSet, base,
1581           implicitFlowTupleSet);
1582       break;
1583
1584     case Kind.FieldAccessNode:
1585       flowTuple =
1586           analyzeFlowFieldAccessNode(md, nametable, (FieldAccessNode) en, nodeSet, base,
1587               implicitFlowTupleSet, isLHS);
1588       if (flowTuple != null) {
1589         nodeSet.addTuple(flowTuple);
1590       }
1591       return flowTuple;
1592
1593     case Kind.NameNode:
1594       NodeTupleSet nameNodeSet = new NodeTupleSet();
1595       flowTuple =
1596           analyzeFlowNameNode(md, nametable, (NameNode) en, nameNodeSet, base, implicitFlowTupleSet);
1597       if (flowTuple != null) {
1598         nodeSet.addTuple(flowTuple);
1599       }
1600       return flowTuple;
1601
1602     case Kind.OpNode:
1603       analyzeFlowOpNode(md, nametable, (OpNode) en, nodeSet, implicitFlowTupleSet);
1604       break;
1605
1606     case Kind.CreateObjectNode:
1607       analyzeCreateObjectNode(md, nametable, (CreateObjectNode) en);
1608       break;
1609
1610     case Kind.ArrayAccessNode:
1611       analyzeFlowArrayAccessNode(md, nametable, (ArrayAccessNode) en, nodeSet, isLHS);
1612       break;
1613
1614     case Kind.LiteralNode:
1615       analyzeLiteralNode(md, nametable, (LiteralNode) en);
1616       break;
1617
1618     case Kind.MethodInvokeNode:
1619       analyzeFlowMethodInvokeNode(md, nametable, (MethodInvokeNode) en, implicitFlowTupleSet);
1620       break;
1621
1622     case Kind.TertiaryNode:
1623       analyzeFlowTertiaryNode(md, nametable, (TertiaryNode) en, nodeSet, implicitFlowTupleSet);
1624       break;
1625
1626     case Kind.CastNode:
1627       analyzeFlowCastNode(md, nametable, (CastNode) en, nodeSet, base, implicitFlowTupleSet);
1628       break;
1629     // case Kind.InstanceOfNode:
1630     // checkInstanceOfNode(md, nametable, (InstanceOfNode) en, td);
1631     // return null;
1632
1633     // case Kind.ArrayInitializerNode:
1634     // checkArrayInitializerNode(md, nametable, (ArrayInitializerNode) en,
1635     // td);
1636     // return null;
1637
1638     // case Kind.ClassTypeNode:
1639     // checkClassTypeNode(md, nametable, (ClassTypeNode) en, td);
1640     // return null;
1641
1642     // case Kind.OffsetNode:
1643     // checkOffsetNode(md, nametable, (OffsetNode)en, td);
1644     // return null;
1645
1646     }
1647     return null;
1648
1649   }
1650
1651   private void analyzeFlowCastNode(MethodDescriptor md, SymbolTable nametable, CastNode cn,
1652       NodeTupleSet nodeSet, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
1653
1654     analyzeFlowExpressionNode(md, nametable, cn.getExpression(), nodeSet, base,
1655         implicitFlowTupleSet, false);
1656
1657   }
1658
1659   private void analyzeFlowTertiaryNode(MethodDescriptor md, SymbolTable nametable, TertiaryNode tn,
1660       NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
1661
1662     NodeTupleSet tertiaryTupleNode = new NodeTupleSet();
1663     analyzeFlowExpressionNode(md, nametable, tn.getCond(), tertiaryTupleNode, null,
1664         implicitFlowTupleSet, false);
1665
1666     // add edges from tertiaryTupleNode to all nodes of conditional nodes
1667     tertiaryTupleNode.addTupleSet(implicitFlowTupleSet);
1668     analyzeFlowExpressionNode(md, nametable, tn.getTrueExpr(), tertiaryTupleNode, null,
1669         implicitFlowTupleSet, false);
1670
1671     analyzeFlowExpressionNode(md, nametable, tn.getFalseExpr(), tertiaryTupleNode, null,
1672         implicitFlowTupleSet, false);
1673
1674     nodeSet.addTupleSet(tertiaryTupleNode);
1675
1676   }
1677
1678   private void addMapCallerMethodDescToMethodInvokeNodeSet(MethodDescriptor caller,
1679       MethodInvokeNode min) {
1680     Set<MethodInvokeNode> set = mapMethodDescriptorToMethodInvokeNodeSet.get(caller);
1681     if (set == null) {
1682       set = new HashSet<MethodInvokeNode>();
1683       mapMethodDescriptorToMethodInvokeNodeSet.put(caller, set);
1684     }
1685     set.add(min);
1686   }
1687
1688   private void analyzeFlowMethodInvokeNode(MethodDescriptor md, SymbolTable nametable,
1689       MethodInvokeNode min, NodeTupleSet implicitFlowTupleSet) {
1690
1691     addMapCallerMethodDescToMethodInvokeNodeSet(md, min);
1692
1693     MethodDescriptor calleeMD = min.getMethod();
1694
1695     NameDescriptor baseName = min.getBaseName();
1696     boolean isSystemout = false;
1697     if (baseName != null) {
1698       isSystemout = baseName.getSymbol().equals("System.out");
1699     }
1700
1701     if (!ssjava.isSSJavaUtil(calleeMD.getClassDesc()) && !ssjava.isTrustMethod(calleeMD)
1702         && !calleeMD.getModifiers().isNative() && !isSystemout) {
1703
1704       // CompositeLocation baseLocation = null;
1705       if (min.getExpression() != null) {
1706
1707         NodeTupleSet baseNodeSet = new NodeTupleSet();
1708         analyzeFlowExpressionNode(md, nametable, min.getExpression(), baseNodeSet, null,
1709             implicitFlowTupleSet, false);
1710
1711       } else {
1712         if (min.getMethod().isStatic()) {
1713           // String globalLocId = ssjava.getMethodLattice(md).getGlobalLoc();
1714           // if (globalLocId == null) {
1715           // throw new
1716           // Error("Method lattice does not define global variable location at "
1717           // + generateErrorMessage(md.getClassDesc(), min));
1718           // }
1719           // baseLocation = new CompositeLocation(new Location(md,
1720           // globalLocId));
1721         } else {
1722           // 'this' var case
1723           // String thisLocId = ssjava.getMethodLattice(md).getThisLoc();
1724           // baseLocation = new CompositeLocation(new Location(md, thisLocId));
1725         }
1726       }
1727
1728       // constraint case:
1729       // if (constraint != null) {
1730       // int compareResult =
1731       // CompositeLattice.compare(constraint, baseLocation, true,
1732       // generateErrorMessage(cd, min));
1733       // if (compareResult != ComparisonResult.GREATER) {
1734       // // if the current constraint is higher than method's THIS location
1735       // // no need to check constraints!
1736       // CompositeLocation calleeConstraint =
1737       // translateCallerLocToCalleeLoc(calleeMD, baseLocation, constraint);
1738       // // System.out.println("check method body for constraint:" + calleeMD +
1739       // // " calleeConstraint="
1740       // // + calleeConstraint);
1741       // checkMethodBody(calleeMD.getClassDesc(), calleeMD, calleeConstraint);
1742       // }
1743       // }
1744
1745       analyzeFlowMethodParameters(md, nametable, min);
1746
1747       // checkCalleeConstraints(md, nametable, min, baseLocation, constraint);
1748
1749       // checkCallerArgumentLocationConstraints(md, nametable, min,
1750       // baseLocation, constraint);
1751
1752       if (min.getMethod().getReturnType() != null && !min.getMethod().getReturnType().isVoid()) {
1753         // If method has a return value, compute the highest possible return
1754         // location in the caller's perspective
1755         // CompositeLocation ceilingLoc =
1756         // computeCeilingLocationForCaller(md, nametable, min, baseLocation,
1757         // constraint);
1758         // return ceilingLoc;
1759       }
1760     }
1761
1762     // return new CompositeLocation(Location.createTopLocation(md));
1763
1764   }
1765
1766   private NodeTupleSet getNodeTupleSetByArgIdx(MethodInvokeNode min, int idx) {
1767     return mapMethodInvokeNodeToArgIdxMap.get(min).get(new Integer(idx));
1768   }
1769
1770   private void addArgIdxMap(MethodInvokeNode min, int idx, NodeTupleSet tupleSet) {
1771     Map<Integer, NodeTupleSet> mapIdxToTupleSet = mapMethodInvokeNodeToArgIdxMap.get(min);
1772     if (mapIdxToTupleSet == null) {
1773       mapIdxToTupleSet = new HashMap<Integer, NodeTupleSet>();
1774       mapMethodInvokeNodeToArgIdxMap.put(min, mapIdxToTupleSet);
1775     }
1776     mapIdxToTupleSet.put(new Integer(idx), tupleSet);
1777   }
1778
1779   private void analyzeFlowMethodParameters(MethodDescriptor callermd, SymbolTable nametable,
1780       MethodInvokeNode min) {
1781
1782     if (min.numArgs() > 0) {
1783
1784       int offset;
1785       if (min.getMethod().isStatic()) {
1786         offset = 0;
1787       } else {
1788         offset = 1;
1789         NTuple<Descriptor> thisArgTuple = new NTuple<Descriptor>();
1790         thisArgTuple.add(callermd.getThis());
1791         NodeTupleSet argTupleSet = new NodeTupleSet();
1792         argTupleSet.addTuple(thisArgTuple);
1793         addArgIdxMap(min, 0, argTupleSet);
1794       }
1795
1796       for (int i = 0; i < min.numArgs(); i++) {
1797         ExpressionNode en = min.getArg(i);
1798         NodeTupleSet argTupleSet = new NodeTupleSet();
1799         analyzeFlowExpressionNode(callermd, nametable, en, argTupleSet, false);
1800         // if argument is liternal node, argTuple is set to NULL.
1801         addArgIdxMap(min, i + offset, argTupleSet);
1802       }
1803
1804     }
1805
1806   }
1807
1808   private void analyzeLiteralNode(MethodDescriptor md, SymbolTable nametable, LiteralNode en) {
1809
1810   }
1811
1812   private void analyzeFlowArrayAccessNode(MethodDescriptor md, SymbolTable nametable,
1813       ArrayAccessNode aan, NodeTupleSet nodeSet, boolean isLHS) {
1814
1815     NodeTupleSet expNodeTupleSet = new NodeTupleSet();
1816     analyzeFlowExpressionNode(md, nametable, aan.getExpression(), expNodeTupleSet, isLHS);
1817
1818     NodeTupleSet idxNodeTupleSet = new NodeTupleSet();
1819     analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, isLHS);
1820
1821     if (isLHS) {
1822       // need to create an edge from idx to array
1823       for (Iterator<NTuple<Descriptor>> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) {
1824         NTuple<Descriptor> idxTuple = idxIter.next();
1825         for (Iterator<NTuple<Descriptor>> arrIter = expNodeTupleSet.iterator(); arrIter.hasNext();) {
1826           NTuple<Descriptor> arrTuple = arrIter.next();
1827           getFlowGraph(md).addValueFlowEdge(idxTuple, arrTuple);
1828         }
1829       }
1830
1831       nodeSet.addTupleSet(expNodeTupleSet);
1832     } else {
1833       nodeSet.addTupleSet(expNodeTupleSet);
1834       nodeSet.addTupleSet(idxNodeTupleSet);
1835     }
1836   }
1837
1838   private void analyzeCreateObjectNode(MethodDescriptor md, SymbolTable nametable,
1839       CreateObjectNode en) {
1840     // TODO Auto-generated method stub
1841
1842   }
1843
1844   private void analyzeFlowOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on,
1845       NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
1846
1847     NodeTupleSet leftOpSet = new NodeTupleSet();
1848     NodeTupleSet rightOpSet = new NodeTupleSet();
1849
1850     // left operand
1851     analyzeFlowExpressionNode(md, nametable, on.getLeft(), leftOpSet, null, implicitFlowTupleSet,
1852         false);
1853
1854     if (on.getRight() != null) {
1855       // right operand
1856       analyzeFlowExpressionNode(md, nametable, on.getRight(), rightOpSet, null,
1857           implicitFlowTupleSet, false);
1858     }
1859
1860     Operation op = on.getOp();
1861
1862     switch (op.getOp()) {
1863
1864     case Operation.UNARYPLUS:
1865     case Operation.UNARYMINUS:
1866     case Operation.LOGIC_NOT:
1867       // single operand
1868       nodeSet.addTupleSet(leftOpSet);
1869       break;
1870
1871     case Operation.LOGIC_OR:
1872     case Operation.LOGIC_AND:
1873     case Operation.COMP:
1874     case Operation.BIT_OR:
1875     case Operation.BIT_XOR:
1876     case Operation.BIT_AND:
1877     case Operation.ISAVAILABLE:
1878     case Operation.EQUAL:
1879     case Operation.NOTEQUAL:
1880     case Operation.LT:
1881     case Operation.GT:
1882     case Operation.LTE:
1883     case Operation.GTE:
1884     case Operation.ADD:
1885     case Operation.SUB:
1886     case Operation.MULT:
1887     case Operation.DIV:
1888     case Operation.MOD:
1889     case Operation.LEFTSHIFT:
1890     case Operation.RIGHTSHIFT:
1891     case Operation.URIGHTSHIFT:
1892
1893       // there are two operands
1894       nodeSet.addTupleSet(leftOpSet);
1895       nodeSet.addTupleSet(rightOpSet);
1896       break;
1897
1898     default:
1899       throw new Error(op.toString());
1900     }
1901
1902   }
1903
1904   private NTuple<Descriptor> analyzeFlowNameNode(MethodDescriptor md, SymbolTable nametable,
1905       NameNode nn, NodeTupleSet nodeSet, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
1906
1907     if (base == null) {
1908       base = new NTuple<Descriptor>();
1909     }
1910
1911     NameDescriptor nd = nn.getName();
1912
1913     if (nd.getBase() != null) {
1914       base =
1915           analyzeFlowExpressionNode(md, nametable, nn.getExpression(), nodeSet, base,
1916               implicitFlowTupleSet, false);
1917       if (base == null) {
1918         // base node has the top location
1919         return base;
1920       }
1921     } else {
1922       String varname = nd.toString();
1923       if (varname.equals("this")) {
1924         // 'this' itself!
1925         base.add(md.getThis());
1926         return base;
1927       }
1928
1929       Descriptor d = (Descriptor) nametable.get(varname);
1930
1931       if (d instanceof VarDescriptor) {
1932         VarDescriptor vd = (VarDescriptor) d;
1933         base.add(vd);
1934       } else if (d instanceof FieldDescriptor) {
1935         // the type of field descriptor has a location!
1936         FieldDescriptor fd = (FieldDescriptor) d;
1937         if (fd.isStatic()) {
1938           if (fd.isFinal()) {
1939             // if it is 'static final', no need to have flow node for the TOP
1940             // location
1941             return null;
1942           } else {
1943             // if 'static', assign the default GLOBAL LOCATION to the first
1944             // element of the tuple
1945             base.add(GLOBALDESC);
1946           }
1947         } else {
1948           // the location of field access starts from this, followed by field
1949           // location
1950           base.add(md.getThis());
1951         }
1952
1953         base.add(fd);
1954       } else if (d == null) {
1955         // access static field
1956         base.add(GLOBALDESC);
1957         // base.add(nn.getField());
1958         return base;
1959
1960         // FieldDescriptor fd = nn.getField();addFlowGraphEdge
1961         //
1962         // MethodLattice<String> localLattice = ssjava.getMethodLattice(md);
1963         // String globalLocId = localLattice.getGlobalLoc();
1964         // if (globalLocId == null) {
1965         // throw new
1966         // Error("Method lattice does not define global variable location at "
1967         // + generateErrorMessage(md.getClassDesc(), nn));
1968         // }
1969         // loc.addLocation(new Location(md, globalLocId));
1970         //
1971         // Location fieldLoc = (Location) fd.getType().getExtension();
1972         // loc.addLocation(fieldLoc);
1973         //
1974         // return loc;
1975
1976       }
1977     }
1978
1979     getFlowGraph(md).createNewFlowNode(base);
1980
1981     return base;
1982
1983   }
1984
1985   private NTuple<Descriptor> analyzeFlowFieldAccessNode(MethodDescriptor md, SymbolTable nametable,
1986       FieldAccessNode fan, NodeTupleSet nodeSet, NTuple<Descriptor> base,
1987       NodeTupleSet implicitFlowTupleSet, boolean isLHS) {
1988
1989     ExpressionNode left = fan.getExpression();
1990     TypeDescriptor ltd = left.getType();
1991     FieldDescriptor fd = fan.getField();
1992
1993     String varName = null;
1994     if (left.kind() == Kind.NameNode) {
1995       NameDescriptor nd = ((NameNode) left).getName();
1996       varName = nd.toString();
1997     }
1998
1999     if (ltd.isClassNameRef() || (varName != null && varName.equals("this"))) {
2000       // using a class name directly or access using this
2001       if (fd.isStatic() && fd.isFinal()) {
2002         return null;
2003       }
2004     }
2005
2006     NodeTupleSet idxNodeTupleSet = new NodeTupleSet();
2007     if (left instanceof ArrayAccessNode) {
2008
2009       ArrayAccessNode aan = (ArrayAccessNode) left;
2010       left = aan.getExpression();
2011       analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, base,
2012           implicitFlowTupleSet, isLHS);
2013       nodeSet.addTupleSet(idxNodeTupleSet);
2014     }
2015     base =
2016         analyzeFlowExpressionNode(md, nametable, left, nodeSet, base, implicitFlowTupleSet, isLHS);
2017
2018     if (base == null) {
2019       // in this case, field is TOP location
2020       return null;
2021     } else {
2022
2023       NTuple<Descriptor> flowFieldTuple = new NTuple<Descriptor>(base.toList());
2024
2025       if (!left.getType().isPrimitive()) {
2026
2027         if (!fd.getSymbol().equals("length")) {
2028           // array.length access, just have the location of the array
2029           flowFieldTuple.add(fd);
2030           nodeSet.removeTuple(base);
2031         }
2032
2033       }
2034       getFlowGraph(md).createNewFlowNode(flowFieldTuple);
2035
2036       if (isLHS) {
2037         for (Iterator<NTuple<Descriptor>> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) {
2038           NTuple<Descriptor> idxTuple = idxIter.next();
2039           getFlowGraph(md).addValueFlowEdge(idxTuple, flowFieldTuple);
2040         }
2041       }
2042
2043       return flowFieldTuple;
2044
2045     }
2046
2047   }
2048
2049   private void debug_printTreeNode(TreeNode tn) {
2050
2051     System.out.println("DEBUG: " + tn.printNode(0) + "                line#=" + tn.getNumLine());
2052
2053   }
2054
2055   private void analyzeFlowAssignmentNode(MethodDescriptor md, SymbolTable nametable,
2056       AssignmentNode an, NodeTupleSet nodeSet, NTuple<Descriptor> base,
2057       NodeTupleSet implicitFlowTupleSet) {
2058
2059     NodeTupleSet nodeSetRHS = new NodeTupleSet();
2060     NodeTupleSet nodeSetLHS = new NodeTupleSet();
2061
2062     boolean postinc = true;
2063     if (an.getOperation().getBaseOp() == null
2064         || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
2065             .getBaseOp().getOp() != Operation.POSTDEC)) {
2066       postinc = false;
2067     }
2068     // if LHS is array access node, need to capture value flows between an array
2069     // and its index value
2070     analyzeFlowExpressionNode(md, nametable, an.getDest(), nodeSetLHS, null, implicitFlowTupleSet,
2071         true);
2072
2073     if (!postinc) {
2074       // analyze value flows of rhs expression
2075       analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null, implicitFlowTupleSet,
2076           false);
2077
2078       // System.out.println("-analyzeFlowAssignmentNode=" + an.printNode(0));
2079       // System.out.println("-nodeSetLHS=" + nodeSetLHS);
2080       // System.out.println("-nodeSetRHS=" + nodeSetRHS);
2081       // System.out.println("-implicitFlowTupleSet=" + implicitFlowTupleSet);
2082       // System.out.println("-");
2083
2084       if (an.getOperation().getOp() >= 2 && an.getOperation().getOp() <= 12) {
2085         // if assignment contains OP+EQ operator, creates edges from LHS to LHS
2086         for (Iterator<NTuple<Descriptor>> iter = nodeSetLHS.iterator(); iter.hasNext();) {
2087           NTuple<Descriptor> fromTuple = iter.next();
2088           for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
2089             NTuple<Descriptor> toTuple = iter2.next();
2090             addFlowGraphEdge(md, fromTuple, toTuple);
2091           }
2092         }
2093       }
2094
2095       // creates edges from RHS to LHS
2096       for (Iterator<NTuple<Descriptor>> iter = nodeSetRHS.iterator(); iter.hasNext();) {
2097         NTuple<Descriptor> fromTuple = iter.next();
2098         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
2099           NTuple<Descriptor> toTuple = iter2.next();
2100           addFlowGraphEdge(md, fromTuple, toTuple);
2101         }
2102       }
2103
2104       // creates edges from implicitFlowTupleSet to LHS
2105       for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
2106         NTuple<Descriptor> fromTuple = iter.next();
2107         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
2108           NTuple<Descriptor> toTuple = iter2.next();
2109           addFlowGraphEdge(md, fromTuple, toTuple);
2110         }
2111       }
2112
2113     } else {
2114       // postinc case
2115       for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
2116         NTuple<Descriptor> tuple = iter2.next();
2117         addFlowGraphEdge(md, tuple, tuple);
2118       }
2119
2120       // creates edges from implicitFlowTupleSet to LHS
2121       for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
2122         NTuple<Descriptor> fromTuple = iter.next();
2123         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
2124           NTuple<Descriptor> toTuple = iter2.next();
2125           addFlowGraphEdge(md, fromTuple, toTuple);
2126         }
2127       }
2128
2129     }
2130
2131     if (nodeSet != null) {
2132       nodeSet.addTupleSet(nodeSetLHS);
2133     }
2134   }
2135
2136   public FlowGraph getFlowGraph(MethodDescriptor md) {
2137     return mapMethodDescriptorToFlowGraph.get(md);
2138   }
2139
2140   private boolean addFlowGraphEdge(MethodDescriptor md, NTuple<Descriptor> from,
2141       NTuple<Descriptor> to) {
2142     // TODO
2143     // return true if it adds a new edge
2144     FlowGraph graph = getFlowGraph(md);
2145     graph.addValueFlowEdge(from, to);
2146     return true;
2147   }
2148
2149   public void _debug_printGraph() {
2150     Set<MethodDescriptor> keySet = mapMethodDescriptorToFlowGraph.keySet();
2151
2152     for (Iterator<MethodDescriptor> iterator = keySet.iterator(); iterator.hasNext();) {
2153       MethodDescriptor md = (MethodDescriptor) iterator.next();
2154       FlowGraph fg = mapMethodDescriptorToFlowGraph.get(md);
2155       try {
2156         fg.writeGraph();
2157       } catch (IOException e) {
2158         e.printStackTrace();
2159       }
2160     }
2161
2162   }
2163
2164 }
2165
2166 class CyclicFlowException extends Exception {
2167
2168 }