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