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