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