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.Collections;
   6 import java.util.Comparator;
   7 import java.util.HashMap;
   8 import java.util.HashSet;
   9 import java.util.Iterator;
  10 import java.util.LinkedList;
  11 import java.util.List;
  12 import java.util.Map;
  13 import java.util.Set;
  14 import java.util.Stack;
  15
  16 import IR.ClassDescriptor;
  17 import IR.Descriptor;
  18 import IR.FieldDescriptor;
  19 import IR.MethodDescriptor;
  20 import IR.NameDescriptor;
  21 import IR.Operation;
  22 import IR.State;
  23 import IR.SymbolTable;
  24 import IR.TypeDescriptor;
  25 import IR.VarDescriptor;
  26 import IR.Tree.ArrayAccessNode;
  27 import IR.Tree.AssignmentNode;
  28 import IR.Tree.BlockExpressionNode;
  29 import IR.Tree.BlockNode;
  30 import IR.Tree.BlockStatementNode;
  31 import IR.Tree.CastNode;
  32 import IR.Tree.CreateObjectNode;
  33 import IR.Tree.DeclarationNode;
  34 import IR.Tree.ExpressionNode;
  35 import IR.Tree.FieldAccessNode;
  36 import IR.Tree.IfStatementNode;
  37 import IR.Tree.Kind;
  38 import IR.Tree.LiteralNode;
  39 import IR.Tree.LoopNode;
  40 import IR.Tree.MethodInvokeNode;
  41 import IR.Tree.NameNode;
  42 import IR.Tree.OpNode;
  43 import IR.Tree.ReturnNode;
  44 import IR.Tree.SubBlockNode;
  45 import IR.Tree.SwitchStatementNode;
  46 import IR.Tree.TertiaryNode;
  47
  48 public class LocationInference {
  49
  50   State state;
  51   SSJavaAnalysis ssjava;
  52
  53   List<ClassDescriptor> toanalyzeList;
  54   List<MethodDescriptor> toanalyzeMethodList;
  55   Map<MethodDescriptor, FlowGraph> mapMethodDescriptorToFlowGraph;
  56
  57   // map a method descriptor to its set of parameter descriptors
  58   Map<MethodDescriptor, Set<Descriptor>> mapMethodDescriptorToParamDescSet;
  59
  60   // keep current descriptors to visit in fixed-point interprocedural analysis,
  61   private Stack<MethodDescriptor> methodDescriptorsToVisitStack;
  62
  63   // map a class descriptor to a field lattice
  64   private Map<ClassDescriptor, SSJavaLattice<String>> cd2lattice;
  65
  66   // map a method descriptor to a method lattice
  67   private Map<MethodDescriptor, SSJavaLattice<String>> md2lattice;
  68
  69   // map a method descriptor to the set of method invocation nodes which are
  70   // invoked by the method descriptor
  71   private Map<MethodDescriptor, Set<MethodInvokeNode>> mapMethodDescriptorToMethodInvokeNodeSet;
  72
  73   private Map<MethodInvokeNode, Map<Integer, NTuple<Descriptor>>> mapMethodInvokeNodeToArgIdxMap;
  74
  75   private Map<MethodDescriptor, MethodLocationInfo> mapMethodDescToMethodLocationInfo;
  76
  77   private Map<ClassDescriptor, LocationInfo> mapClassToLocationInfo;
  78
  79   private Map<MethodDescriptor, Set<MethodDescriptor>> mapMethodDescToPossibleMethodDescSet;
  80
  81   boolean debug = true;
  82
  83   public LocationInference(SSJavaAnalysis ssjava, State state) {
  84     this.ssjava = ssjava;
  85     this.state = state;
  86     this.toanalyzeList = new ArrayList<ClassDescriptor>();
  87     this.toanalyzeMethodList = new ArrayList<MethodDescriptor>();
  88     this.mapMethodDescriptorToFlowGraph = new HashMap<MethodDescriptor, FlowGraph>();
  89     this.cd2lattice = new HashMap<ClassDescriptor, SSJavaLattice<String>>();
  90     this.md2lattice = new HashMap<MethodDescriptor, SSJavaLattice<String>>();
  91     this.methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
  92     this.mapMethodDescriptorToMethodInvokeNodeSet =
  93         new HashMap<MethodDescriptor, Set<MethodInvokeNode>>();
  94     this.mapMethodInvokeNodeToArgIdxMap =
  95         new HashMap<MethodInvokeNode, Map<Integer, NTuple<Descriptor>>>();
  96     this.mapMethodDescToMethodLocationInfo = new HashMap<MethodDescriptor, MethodLocationInfo>();
  97     this.mapMethodDescToPossibleMethodDescSet =
  98         new HashMap<MethodDescriptor, Set<MethodDescriptor>>();
  99     this.mapClassToLocationInfo = new HashMap<ClassDescriptor, LocationInfo>();
 100   }
 101
 102   public void setupToAnalyze() {
 103     SymbolTable classtable = state.getClassSymbolTable();
 104     toanalyzeList.clear();
 105     toanalyzeList.addAll(classtable.getValueSet());
 106     Collections.sort(toanalyzeList, new Comparator<ClassDescriptor>() {
 107       public int compare(ClassDescriptor o1, ClassDescriptor o2) {
 108         return o1.getClassName().compareToIgnoreCase(o2.getClassName());
 109       }
 110     });
 111   }
 112
 113   public void setupToAnalazeMethod(ClassDescriptor cd) {
 114
 115     SymbolTable methodtable = cd.getMethodTable();
 116     toanalyzeMethodList.clear();
 117     toanalyzeMethodList.addAll(methodtable.getValueSet());
 118     Collections.sort(toanalyzeMethodList, new Comparator<MethodDescriptor>() {
 119       public int compare(MethodDescriptor o1, MethodDescriptor o2) {
 120         return o1.getSymbol().compareToIgnoreCase(o2.getSymbol());
 121       }
 122     });
 123   }
 124
 125   public boolean toAnalyzeMethodIsEmpty() {
 126     return toanalyzeMethodList.isEmpty();
 127   }
 128
 129   public boolean toAnalyzeIsEmpty() {
 130     return toanalyzeList.isEmpty();
 131   }
 132
 133   public ClassDescriptor toAnalyzeNext() {
 134     return toanalyzeList.remove(0);
 135   }
 136
 137   public MethodDescriptor toAnalyzeMethodNext() {
 138     return toanalyzeMethodList.remove(0);
 139   }
 140
 141   public void inference() {
 142
 143     // 1) construct value flow graph
 144     constructFlowGraph();
 145
 146     // 2) construct lattices
 147     inferLattices();
 148
 149     debug_writeLatticeDotFile();
 150
 151     // 3) check properties
 152     checkLattices();
 153
 154   }
 155
 156   private void checkLattices() {
 157
 158     LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
 159
 160     // current descriptors to visit in fixed-point interprocedural analysis,
 161     // prioritized by
 162     // dependency in the call graph
 163     methodDescriptorsToVisitStack.clear();
 164
 165     descriptorListToAnalyze.removeFirst();
 166
 167     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
 168     methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
 169
 170     while (!descriptorListToAnalyze.isEmpty()) {
 171       MethodDescriptor md = descriptorListToAnalyze.removeFirst();
 172       checkLatticesOfVirtualMethods(md);
 173     }
 174
 175   }
 176
 177   private void debug_writeLatticeDotFile() {
 178     // generate lattice dot file
 179
 180     setupToAnalyze();
 181
 182     while (!toAnalyzeIsEmpty()) {
 183       ClassDescriptor cd = toAnalyzeNext();
 184
 185       setupToAnalazeMethod(cd);
 186
 187       SSJavaLattice<String> classLattice = cd2lattice.get(cd);
 188       if (classLattice != null) {
 189         ssjava.writeLatticeDotFile(cd, null, classLattice);
 190       }
 191
 192       while (!toAnalyzeMethodIsEmpty()) {
 193         MethodDescriptor md = toAnalyzeMethodNext();
 194         if (ssjava.needTobeAnnotated(md)) {
 195           SSJavaLattice<String> methodLattice = md2lattice.get(md);
 196           if (methodLattice != null) {
 197             ssjava.writeLatticeDotFile(cd, md, methodLattice);
 198           }
 199         }
 200       }
 201     }
 202
 203   }
 204
 205   private void inferLattices() {
 206
 207     // do fixed-point analysis
 208
 209     LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
 210
 211     // current descriptors to visit in fixed-point interprocedural analysis,
 212     // prioritized by
 213     // dependency in the call graph
 214     methodDescriptorsToVisitStack.clear();
 215
 216     descriptorListToAnalyze.removeFirst();
 217
 218     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
 219     methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
 220
 221     while (!descriptorListToAnalyze.isEmpty()) {
 222       MethodDescriptor md = descriptorListToAnalyze.removeFirst();
 223       methodDescriptorsToVisitStack.add(md);
 224     }
 225
 226     // analyze scheduled methods until there are no more to visit
 227     while (!methodDescriptorsToVisitStack.isEmpty()) {
 228       // start to analyze leaf node
 229       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
 230
 231       SSJavaLattice<String> methodLattice =
 232           new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM);
 233
 234       System.out.println();
 235       System.out.println("SSJAVA: Inferencing the lattice from " + md);
 236
 237       analyzeMethodLattice(md, methodLattice);
 238
 239       SSJavaLattice<String> prevMethodLattice = getMethodLattice(md);
 240
 241       if (!methodLattice.equals(prevMethodLattice)) {
 242
 243         setMethodLattice(md, methodLattice);
 244
 245         // results for callee changed, so enqueue dependents caller for
 246         // further analysis
 247         Iterator<MethodDescriptor> depsItr = ssjava.getDependents(md).iterator();
 248         while (depsItr.hasNext()) {
 249           MethodDescriptor methodNext = depsItr.next();
 250           if (!methodDescriptorsToVisitStack.contains(methodNext)
 251               && methodDescriptorToVistSet.contains(methodNext)) {
 252             methodDescriptorsToVisitStack.add(methodNext);
 253           }
 254         }
 255
 256       }
 257
 258     }
 259
 260   }
 261
 262   private void checkLatticesOfVirtualMethods(MethodDescriptor md) {
 263
 264     if (!md.isStatic()) {
 265       Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
 266       setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md));
 267
 268       for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
 269         MethodDescriptor mdCallee = (MethodDescriptor) iterator.next();
 270         if (!md.equals(mdCallee)) {
 271           checkConsistency(md, mdCallee);
 272         }
 273       }
 274
 275     }
 276
 277   }
 278
 279   private void checkConsistency(MethodDescriptor md1, MethodDescriptor md2) {
 280
 281     // check that two lattice have the same relations between parameters(+PC
 282     // LOC, RETURN LOC)
 283
 284     MethodLocationInfo methodInfo1 = getMethodLocationInfo(md1);
 285
 286     SSJavaLattice<String> lattice1 = getMethodLattice(md1);
 287     SSJavaLattice<String> lattice2 = getMethodLattice(md2);
 288
 289     Set<String> paramLocNameSet1 = methodInfo1.getParameterLocNameSet();
 290
 291     for (Iterator iterator = paramLocNameSet1.iterator(); iterator.hasNext();) {
 292       String locName1 = (String) iterator.next();
 293       for (Iterator iterator2 = paramLocNameSet1.iterator(); iterator2.hasNext();) {
 294         String locName2 = (String) iterator2.next();
 295
 296         // System.out.println("COMPARE " + locName1 + " - " + locName2 + " "
 297         // + lattice1.isGreaterThan(locName1, locName2) + "-"
 298         // + lattice2.isGreaterThan(locName1, locName2));
 299
 300         if (!locName1.equals(locName2)) {
 301
 302           boolean r1 = lattice1.isGreaterThan(locName1, locName2);
 303           boolean r2 = lattice2.isGreaterThan(locName1, locName2);
 304
 305           if (r1 != r2) {
 306             throw new Error("The method " + md1 + " is not consistent with the method " + md2
 307                 + ".:: They have a different ordering relation between parameters " + locName1
 308                 + " and " + locName2 + ".");
 309           }
 310         }
 311
 312       }
 313     }
 314
 315   }
 316
 317   private String getSymbol(int idx, FlowNode node) {
 318     Descriptor desc = node.getDescTuple().get(idx);
 319     return desc.getSymbol();
 320   }
 321
 322   private Descriptor getDescriptor(int idx, FlowNode node) {
 323     Descriptor desc = node.getDescTuple().get(idx);
 324     return desc;
 325   }
 326
 327   private void analyzeMethodLattice(MethodDescriptor md, SSJavaLattice<String> methodLattice) {
 328
 329     MethodLocationInfo methodInfo = getMethodLocationInfo(md);
 330
 331     // first take a look at method invocation nodes to newly added relations
 332     // from the callee
 333     analyzeLatticeMethodInvocationNode(md);
 334
 335     // visit each node of method flow graph
 336     FlowGraph fg = getFlowGraph(md);
 337     Set<FlowNode> nodeSet = fg.getNodeSet();
 338
 339     // for the method lattice, we need to look at the first element of
 340     // NTuple<Descriptor>
 341     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 342       FlowNode srcNode = (FlowNode) iterator.next();
 343
 344       Set<FlowEdge> outEdgeSet = srcNode.getOutEdgeSet();
 345       for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) {
 346         FlowEdge outEdge = (FlowEdge) iterator2.next();
 347         FlowNode dstNode = outEdge.getDst();
 348
 349         NTuple<Descriptor> srcNodeTuple = srcNode.getDescTuple();
 350         NTuple<Descriptor> dstNodeTuple = dstNode.getDescTuple();
 351
 352         if (outEdge.getInitTuple().equals(srcNodeTuple)
 353             && outEdge.getEndTuple().equals(dstNodeTuple)) {
 354
 355           if ((srcNodeTuple.size() > 1 && dstNodeTuple.size() > 1)
 356               && srcNodeTuple.get(0).equals(dstNodeTuple.get(0))) {
 357
 358             // value flows between fields
 359             VarDescriptor varDesc = (VarDescriptor) srcNodeTuple.get(0);
 360             ClassDescriptor varClassDesc = varDesc.getType().getClassDesc();
 361             extractRelationFromFieldFlows(varClassDesc, srcNode, dstNode, 1);
 362
 363           } else {
 364             // for the method lattice, we need to look at the first element of
 365             // NTuple<Descriptor>
 366             if (srcNodeTuple.size() == 1 || dstNodeTuple.size() == 1) {
 367               // in this case, take a look at connected nodes at the local level
 368               addRelationToLattice(md, methodLattice, srcNode, dstNode);
 369             }
 370           }
 371
 372         }
 373       }
 374     }
 375
 376     // grab the this location if the method use the 'this' reference
 377     String thisLocSymbol = md.getThis().getSymbol();
 378     if (methodLattice.getKeySet().contains(thisLocSymbol)) {
 379       methodInfo.setThisLocName(thisLocSymbol);
 380     }
 381
 382     // calculate a return location
 383     if (!md.getReturnType().isVoid()) {
 384       Set<FlowNode> returnNodeSet = fg.getReturnNodeSet();
 385       Set<String> returnVarSymbolSet = new HashSet<String>();
 386
 387       for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
 388         FlowNode rtrNode = (FlowNode) iterator.next();
 389         String localSymbol = rtrNode.getDescTuple().get(0).getSymbol();
 390         returnVarSymbolSet.add(localSymbol);
 391       }
 392
 393       String returnGLB = methodLattice.getGLB(returnVarSymbolSet);
 394       if (returnGLB.equals(SSJavaAnalysis.BOTTOM)) {
 395         // need to insert a new location in-between the bottom and all locations
 396         // that is directly connected to the bottom
 397         String returnNewLocationSymbol = "Loc" + (SSJavaLattice.seed++);
 398         methodLattice.insertNewLocationAtOneLevelHigher(returnGLB, returnNewLocationSymbol);
 399         methodInfo.setReturnLocName(returnNewLocationSymbol);
 400       } else {
 401         methodInfo.setReturnLocName(returnGLB);
 402       }
 403     }
 404
 405   }
 406
 407   private void analyzeLatticeMethodInvocationNode(MethodDescriptor mdCaller) {
 408
 409     // the transformation for a call site propagates all relations between
 410     // parameters from the callee
 411     // if the method is virtual, it also grab all relations from any possible
 412     // callees
 413
 414     Set<MethodInvokeNode> setMethodInvokeNode =
 415         mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller);
 416     if (setMethodInvokeNode != null) {
 417
 418       for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) {
 419         MethodInvokeNode min = (MethodInvokeNode) iterator.next();
 420         MethodDescriptor mdCallee = min.getMethod();
 421         Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
 422         if (mdCallee.isStatic()) {
 423           setPossibleCallees.add(mdCallee);
 424         } else {
 425           setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(mdCallee));
 426         }
 427
 428         for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) {
 429           MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next();
 430           propagateRelationToCaller(min, mdCaller, possibleMdCallee);
 431         }
 432
 433       }
 434     }
 435
 436   }
 437
 438   private void propagateRelationToCaller(MethodInvokeNode min, MethodDescriptor mdCaller,
 439       MethodDescriptor possibleMdCallee) {
 440
 441     SSJavaLattice<String> calleeLattice = getMethodLattice(possibleMdCallee);
 442
 443     FlowGraph calleeFlowGraph = getFlowGraph(possibleMdCallee);
 444
 445     // find parameter node
 446     Set<FlowNode> paramNodeSet = calleeFlowGraph.getParameterNodeSet();
 447
 448     for (Iterator iterator = paramNodeSet.iterator(); iterator.hasNext();) {
 449       FlowNode paramFlowNode1 = (FlowNode) iterator.next();
 450
 451       for (Iterator iterator2 = paramNodeSet.iterator(); iterator2.hasNext();) {
 452         FlowNode paramFlowNode2 = (FlowNode) iterator2.next();
 453
 454         String paramSymbol1 = getSymbol(0, paramFlowNode1);
 455         String paramSymbol2 = getSymbol(0, paramFlowNode2);
 456         // if two parameters have a relation, we need to propagate this relation
 457         // to the caller
 458         if (!(paramSymbol1.equals(paramSymbol2))
 459             && calleeLattice.isComparable(paramSymbol1, paramSymbol2)) {
 460           int higherLocIdxCallee;
 461           int lowerLocIdxCallee;
 462           if (calleeLattice.isGreaterThan(paramSymbol1, paramSymbol2)) {
 463             higherLocIdxCallee = calleeFlowGraph.getParamIdx(paramFlowNode1.getDescTuple());
 464             lowerLocIdxCallee = calleeFlowGraph.getParamIdx(paramFlowNode2.getDescTuple());
 465           } else {
 466             higherLocIdxCallee = calleeFlowGraph.getParamIdx(paramFlowNode2.getDescTuple());
 467             lowerLocIdxCallee = calleeFlowGraph.getParamIdx(paramFlowNode1.getDescTuple());
 468           }
 469
 470           NTuple<Descriptor> higherArg = getArgTupleByArgIdx(min, higherLocIdxCallee);
 471           NTuple<Descriptor> lowerArg = getArgTupleByArgIdx(min, lowerLocIdxCallee);
 472
 473           addFlowGraphEdge(mdCaller, higherArg, lowerArg);
 474
 475         }
 476
 477       }
 478
 479     }
 480
 481   }
 482
 483   private LocationInfo getLocationInfo(Descriptor d) {
 484     if (d instanceof MethodDescriptor) {
 485       return getMethodLocationInfo((MethodDescriptor) d);
 486     } else {
 487       return getFieldLocationInfo((ClassDescriptor) d);
 488     }
 489   }
 490
 491   private MethodLocationInfo getMethodLocationInfo(MethodDescriptor md) {
 492
 493     if (!mapMethodDescToMethodLocationInfo.containsKey(md)) {
 494       mapMethodDescToMethodLocationInfo.put(md, new MethodLocationInfo(md));
 495     }
 496
 497     return mapMethodDescToMethodLocationInfo.get(md);
 498
 499   }
 500
 501   private LocationInfo getFieldLocationInfo(ClassDescriptor cd) {
 502
 503     if (!mapClassToLocationInfo.containsKey(cd)) {
 504       mapClassToLocationInfo.put(cd, new LocationInfo(cd));
 505     }
 506
 507     return mapClassToLocationInfo.get(cd);
 508
 509   }
 510
 511   private void addRelationToLattice(MethodDescriptor md, SSJavaLattice<String> methodLattice,
 512       FlowNode srcNode, FlowNode dstNode) {
 513
 514     System.out.println("### addRelationToLattice src=" + srcNode + " dst=" + dstNode);
 515
 516     // add a new binary relation of dstNode < srcNode
 517     FlowGraph flowGraph = getFlowGraph(md);
 518     MethodLocationInfo methodInfo = getMethodLocationInfo(md);
 519
 520     String srcOriginSymbol = getSymbol(0, srcNode);
 521     String dstOriginSymbol = getSymbol(0, dstNode);
 522
 523     Descriptor srcDesc = getDescriptor(0, srcNode);
 524     Descriptor dstDesc = getDescriptor(0, dstNode);
 525
 526     String srcSymbol = methodInfo.getLocName(srcOriginSymbol);
 527     String dstSymbol = methodInfo.getLocName(dstOriginSymbol);
 528
 529     if (srcNode.isParameter()) {
 530       int paramIdx = flowGraph.getParamIdx(srcNode.getDescTuple());
 531       methodInfo.addParameter(srcSymbol, srcDesc, paramIdx);
 532     } else {
 533       methodInfo.addMappingOfLocNameToDescriptor(srcSymbol, srcDesc);
 534     }
 535
 536     if (dstNode.isParameter()) {
 537       int paramIdx = flowGraph.getParamIdx(dstNode.getDescTuple());
 538       methodInfo.addParameter(dstSymbol, dstDesc, paramIdx);
 539     } else {
 540       methodInfo.addMappingOfLocNameToDescriptor(dstSymbol, dstDesc);
 541     }
 542
 543     // consider a composite location case
 544
 545     boolean isSrcLocalVar = false;
 546     boolean isDstLocalVar = false;
 547     if (srcNode.getDescTuple().size() == 1) {
 548       isSrcLocalVar = true;
 549     }
 550
 551     if (dstNode.getDescTuple().size() == 1) {
 552       isDstLocalVar = true;
 553     }
 554
 555     boolean isAssignedCompositeLocation = false;
 556     if (isSrcLocalVar && isDstLocalVar) {
 557       // both src and dst are local var
 558
 559       // CompositeLocation inferSrc=methodInfo.getInferLocation(srcNode);
 560       // CompositeLocation inferDst=methodInfo.getInferLocation(dstNode);
 561       // if( (inferSrc!=null && inferSrc.getSize()>1) || (inferDst!=null &&
 562       // inferDst.getSize()>1)){
 563       // isAssignedCompositeLocation = true;
 564       // }
 565
 566       // TODO: need to fix
 567       isAssignedCompositeLocation =
 568           calculateCompositeLocationForLocalVar(flowGraph, methodLattice, methodInfo, srcNode);
 569       calculateCompositeLocationForLocalVar(flowGraph, methodLattice, methodInfo, dstNode);
 570
 571     } else if (isSrcLocalVar) {
 572       // src is local var
 573       isAssignedCompositeLocation =
 574           calculateCompositeLocationForLocalVar(flowGraph, methodLattice, methodInfo, srcNode);
 575     } else if (isDstLocalVar) {
 576       // dst is local var
 577       isAssignedCompositeLocation =
 578           calculateCompositeLocationForLocalVar(flowGraph, methodLattice, methodInfo, dstNode);
 579     }
 580
 581     if (!isAssignedCompositeLocation) {
 582       if (!methodLattice.isGreaterThan(srcSymbol, dstSymbol)) {
 583         // if the lattice does not have this relation, add it
 584         methodLattice.addRelationHigherToLower(srcSymbol, dstSymbol);
 585       }
 586     }
 587
 588     // Set<String> cycleElementSet =
 589     // methodLattice.getPossibleCycleElements(srcSymbol, dstSymbol);
 590     //
 591     // System.out.println("### POSSIBLE CYCLE ELEMENT SET=" + cycleElementSet);
 592     // boolean hasNonPrimitiveElement = false;
 593     // for (Iterator iterator = cycleElementSet.iterator(); iterator.hasNext();)
 594     // {
 595     // String cycleElementSymbol = (String) iterator.next();
 596     // Set<Descriptor> flowNodeSet =
 597     // methodInfo.getFlowNodeSet(cycleElementSymbol);
 598     // for (Iterator iterator2 = flowNodeSet.iterator(); iterator2.hasNext();) {
 599     // Descriptor desc = (Descriptor) iterator2.next();
 600     // if (!isPrimitiveTypeDescriptor(desc)) {
 601     // hasNonPrimitiveElement = true;
 602     // }
 603     // System.out
 604     // .println("flowNode=" + desc + " is primitive?=" +
 605     // isPrimitiveTypeDescriptor(desc));
 606     // }
 607     // }
 608     //
 609     // if (hasNonPrimitiveElement) {
 610     // // if there is non-primitive element in the cycle, no way to merge cyclic
 611     // // elements into the shared location
 612     // System.out.println("Failed to merge cyclic value flows into a shared location.");
 613     //
 614     // // try to assign more fine-grind composite location to the source or the
 615     // // destination
 616     // System.out.println("SRC=" + srcSymbol + "    DST=" + dstSymbol);
 617     // System.out.println("### SRCNODE=" + srcNode + " DSTNODE=" + dstNode);
 618     //
 619     // FlowNode targetNode;
 620     // if (isPrimitiveLocalVariable(srcNode)) {
 621     // targetNode = srcNode;
 622     // } else {
 623     // targetNode = dstNode;
 624     // }
 625     //
 626     // calculateMoreFineGrainedLocation(md, methodLattice, targetNode);
 627     //
 628     // return;
 629     // }
 630     //
 631     // if (cycleElementSet.size() > 0) {
 632     // String newSharedLoc = "SharedLoc" + (SSJavaLattice.seed++);
 633     // methodLattice.mergeIntoSharedLocation(cycleElementSet, newSharedLoc);
 634     //
 635     // for (Iterator iterator = cycleElementSet.iterator(); iterator.hasNext();)
 636     // {
 637     // String locName = (String) iterator.next();
 638     // methodInfo.mapDescSymbolToLocName(locName, newSharedLoc);
 639     // }
 640     //
 641     // } else if (!methodLattice.isGreaterThan(srcSymbol, dstSymbol)) {
 642     // // if the lattice does not have this relation, add it
 643     // methodLattice.addRelationHigherToLower(srcSymbol, dstSymbol);
 644     // }
 645     //
 646     // System.out.println("methodLattice=" + methodLattice.getKeySet());
 647
 648   }
 649
 650   private void addPrefixMapping(Map<NTuple<Location>, Set<NTuple<Location>>> map,
 651       NTuple<Location> prefix, NTuple<Location> element) {
 652
 653     if (!map.containsKey(prefix)) {
 654       map.put(prefix, new HashSet<NTuple<Location>>());
 655     }
 656     map.get(prefix).add(element);
 657
 658   }
 659
 660   private NTuple<Location> getLocationTuple(MethodLocationInfo methodInfo, FlowGraph flowGraph,
 661       FlowNode flowNode) {
 662
 663     NTuple<Location> locTuple;
 664     CompositeLocation inferLoc = methodInfo.getInferLocation(flowNode);
 665     if (inferLoc != null) {
 666       // the flow node has already been assigned to the location
 667       locTuple = new NTuple<Location>();
 668       NTuple<Location> inferLocTuple = inferLoc.getTuple();
 669       for (int i = 0; i < inferLocTuple.size(); i++) {
 670         locTuple.add(inferLocTuple.get(i));
 671       }
 672     } else {
 673       locTuple = flowGraph.getLocationTuple(flowNode);
 674     }
 675
 676     return locTuple;
 677   }
 678
 679   private boolean calculateCompositeLocationForLocalVar(FlowGraph flowGraph,
 680       SSJavaLattice<String> methodLattice, MethodLocationInfo methodInfo, FlowNode flowNode) {
 681
 682     Set<FlowNode> inNodeSet = flowGraph.getIncomingFlowNodeSet(flowNode);
 683     Set<FlowNode> reachableNodeSet = flowGraph.getReachableFlowNodeSet(flowNode);
 684
 685     Map<NTuple<Location>, Set<NTuple<Location>>> mapPrefixToIncomingLocTupleSet =
 686         new HashMap<NTuple<Location>, Set<NTuple<Location>>>();
 687
 688     List<NTuple<Location>> prefixList = new ArrayList<NTuple<Location>>();
 689
 690     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
 691       FlowNode inNode = (FlowNode) iterator.next();
 692       NTuple<Location> inTuple = getLocationTuple(methodInfo, flowGraph, inNode);
 693
 694       if (inTuple.size() > 1) {
 695         for (int i = 1; i < inTuple.size(); i++) {
 696           NTuple<Location> prefix = inTuple.subList(0, i);
 697           if (!prefixList.contains(prefix)) {
 698             prefixList.add(prefix);
 699           }
 700           addPrefixMapping(mapPrefixToIncomingLocTupleSet, prefix, inTuple);
 701         }
 702       }
 703     }
 704
 705     Collections.sort(prefixList, new Comparator<NTuple<Location>>() {
 706       public int compare(NTuple<Location> arg0, NTuple<Location> arg1) {
 707         int s0 = arg0.size();
 708         int s1 = arg1.size();
 709         if (s0 > s1) {
 710           return -1;
 711         } else if (s0 == s1) {
 712           return 0;
 713         } else {
 714           return 1;
 715         }
 716       }
 717     });
 718
 719     // find out reachable nodes that have the longest common prefix
 720     for (int i = 0; i < prefixList.size(); i++) {
 721       NTuple<Location> curPrefix = prefixList.get(i);
 722       Set<NTuple<Location>> reachableCommonPrefixSet = new HashSet<NTuple<Location>>();
 723
 724       for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
 725         FlowNode reachableNode = (FlowNode) iterator2.next();
 726         NTuple<Location> reachLocTuple = flowGraph.getLocationTuple(reachableNode);
 727         if (reachLocTuple.startsWith(curPrefix)) {
 728           reachableCommonPrefixSet.add(reachLocTuple);
 729         }
 730       }
 731
 732       if (!reachableCommonPrefixSet.isEmpty()) {
 733         Set<NTuple<Location>> incomingCommonPrefixSet =
 734             mapPrefixToIncomingLocTupleSet.get(curPrefix);
 735
 736         int idx = curPrefix.size();
 737         NTuple<Location> element = incomingCommonPrefixSet.iterator().next();
 738         Descriptor desc = element.get(idx).getDescriptor();
 739
 740         SSJavaLattice<String> lattice = getLattice(desc);
 741         LocationInfo locInfo = getLocationInfo(desc);
 742
 743         CompositeLocation inferNode = methodInfo.getInferLocation(flowNode);
 744         String nodeSymbol;
 745         if (inferNode != null) {
 746
 747         } else {
 748           String newLocSymbol = "Loc" + (SSJavaLattice.seed++);
 749           inferNode = new CompositeLocation();
 750           for (int locIdx = 0; locIdx < curPrefix.size(); locIdx++) {
 751             inferNode.addLocation(curPrefix.get(locIdx));
 752           }
 753           inferNode.addLocation(new Location(desc, newLocSymbol));
 754           methodInfo.mapFlowNodeToInferLocation(flowNode, inferNode);
 755           if (flowNode.getDescTuple().size() == 1) {
 756             // local variable case
 757             modifyLocalLatticeAccrodingToNewlyAddedCompositeLocation(methodLattice, methodInfo,
 758                 inferNode, flowNode);
 759           }
 760         }
 761
 762         nodeSymbol = inferNode.get(inferNode.getSize() - 1).getLocIdentifier();
 763
 764         for (Iterator iterator = incomingCommonPrefixSet.iterator(); iterator.hasNext();) {
 765           NTuple<Location> tuple = (NTuple<Location>) iterator.next();
 766           Location loc = tuple.get(idx);
 767           String higher = locInfo.getLocName(loc.getLocIdentifier());
 768           lattice.addRelationHigherToLower(higher, nodeSymbol);
 769         }
 770
 771         for (Iterator iterator = reachableCommonPrefixSet.iterator(); iterator.hasNext();) {
 772           NTuple<Location> tuple = (NTuple<Location>) iterator.next();
 773           Location loc = tuple.get(idx);
 774           String lower = locInfo.getLocName(loc.getLocIdentifier());
 775           lattice.addRelationHigherToLower(nodeSymbol, lower);
 776         }
 777
 778         return true;
 779       }
 780
 781     }
 782
 783     return false;
 784
 785   }
 786
 787   private void modifyLocalLatticeAccrodingToNewlyAddedCompositeLocation(
 788       SSJavaLattice<String> methodLattice, MethodLocationInfo methodInfo,
 789       CompositeLocation inferNode, FlowNode flowNode) {
 790
 791     Location localLocation = inferNode.get(0);
 792     String newLocName = methodInfo.getLocName(localLocation.getLocIdentifier());
 793     String oldLocName = methodInfo.getLocName(flowNode.getDescTuple().get(0).getSymbol());
 794
 795     methodInfo.mapDescSymbolToLocName(oldLocName, newLocName);
 796     methodLattice.substituteLocation(oldLocName, newLocName);
 797
 798   }
 799
 800   public boolean isPrimitiveLocalVariable(FlowNode node) {
 801     VarDescriptor varDesc = (VarDescriptor) node.getDescTuple().get(0);
 802     return varDesc.getType().isPrimitive();
 803   }
 804
 805   private SSJavaLattice<String> getLattice(Descriptor d) {
 806     if (d instanceof MethodDescriptor) {
 807       return getMethodLattice((MethodDescriptor) d);
 808     } else {
 809       return getFieldLattice((ClassDescriptor) d);
 810     }
 811   }
 812
 813   private SSJavaLattice<String> getMethodLattice(MethodDescriptor md) {
 814     if (!md2lattice.containsKey(md)) {
 815       md2lattice.put(md, new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM));
 816     }
 817     return md2lattice.get(md);
 818   }
 819
 820   private void setMethodLattice(MethodDescriptor md, SSJavaLattice<String> lattice) {
 821     md2lattice.put(md, lattice);
 822   }
 823
 824   private void extractRelationFromFieldFlows(ClassDescriptor cd, FlowNode srcNode,
 825       FlowNode dstNode, int idx) {
 826
 827     if (srcNode.getDescTuple().get(idx).equals(dstNode.getDescTuple().get(idx))
 828         && srcNode.getDescTuple().size() > (idx + 1) && dstNode.getDescTuple().size() > (idx + 1)) {
 829       // value flow between fields: we don't need to add a binary relation
 830       // for this case
 831
 832       Descriptor desc = srcNode.getDescTuple().get(idx);
 833       ClassDescriptor classDesc;
 834
 835       if (idx == 0) {
 836         classDesc = ((VarDescriptor) desc).getType().getClassDesc();
 837       } else {
 838         classDesc = ((FieldDescriptor) desc).getType().getClassDesc();
 839       }
 840
 841       extractRelationFromFieldFlows(classDesc, srcNode, dstNode, idx + 1);
 842
 843     } else {
 844
 845       Descriptor srcFieldDesc = srcNode.getDescTuple().get(idx);
 846       Descriptor dstFieldDesc = dstNode.getDescTuple().get(idx);
 847
 848       // add a new binary relation of dstNode < srcNode
 849       SSJavaLattice<String> fieldLattice = getFieldLattice(cd);
 850
 851       String srcOriginalSymbol = srcFieldDesc.getSymbol();
 852       String dstOriginalSymbol = dstFieldDesc.getSymbol();
 853
 854       LocationInfo fieldInfo = getFieldLocationInfo(cd);
 855
 856       String srcSymbol = fieldInfo.getLocName(srcOriginalSymbol);
 857       String dstSymbol = fieldInfo.getLocName(dstOriginalSymbol);
 858
 859       Set<String> cycleElementSet = fieldLattice.getPossibleCycleElements(srcSymbol, dstSymbol);
 860
 861       if (cycleElementSet.size() > 0) {
 862         String newSharedLoc = "SharedLoc" + (SSJavaLattice.seed++);
 863         fieldLattice.mergeIntoSharedLocation(cycleElementSet, newSharedLoc);
 864
 865         for (Iterator iterator = cycleElementSet.iterator(); iterator.hasNext();) {
 866           String locName = (String) iterator.next();
 867           fieldInfo.mapDescSymbolToLocName(locName, newSharedLoc);
 868         }
 869
 870       } else if (!fieldLattice.isGreaterThan(srcSymbol, dstSymbol)) {
 871         // if the lattice does not have this relation, add it
 872         fieldLattice.addRelationHigherToLower(srcSymbol, dstSymbol);
 873       }
 874
 875     }
 876
 877   }
 878
 879   public SSJavaLattice<String> getFieldLattice(ClassDescriptor cd) {
 880     if (!cd2lattice.containsKey(cd)) {
 881       cd2lattice.put(cd, new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM));
 882     }
 883     return cd2lattice.get(cd);
 884   }
 885
 886   public void constructFlowGraph() {
 887
 888     setupToAnalyze();
 889
 890     while (!toAnalyzeIsEmpty()) {
 891       ClassDescriptor cd = toAnalyzeNext();
 892
 893       setupToAnalazeMethod(cd);
 894       while (!toAnalyzeMethodIsEmpty()) {
 895         MethodDescriptor md = toAnalyzeMethodNext();
 896         if (ssjava.needTobeAnnotated(md)) {
 897           if (state.SSJAVADEBUG) {
 898             System.out.println();
 899             System.out.println("SSJAVA: Constructing a flow graph: " + md);
 900           }
 901
 902           // creates a mapping from a method descriptor to virtual methods
 903           Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
 904           if (md.isStatic()) {
 905             setPossibleCallees.add(md);
 906           } else {
 907             setPossibleCallees.addAll(ssjava.getCallGraph().getMethods(md));
 908           }
 909           mapMethodDescToPossibleMethodDescSet.put(md, setPossibleCallees);
 910
 911           // creates a mapping from a parameter descriptor to its index
 912           Map<Descriptor, Integer> mapParamDescToIdx = new HashMap<Descriptor, Integer>();
 913           int offset = md.isStatic() ? 0 : 1;
 914           for (int i = 0; i < md.numParameters(); i++) {
 915             Descriptor paramDesc = (Descriptor) md.getParameter(i);
 916             mapParamDescToIdx.put(paramDesc, new Integer(i + offset));
 917           }
 918
 919           FlowGraph fg = new FlowGraph(md, mapParamDescToIdx);
 920           mapMethodDescriptorToFlowGraph.put(md, fg);
 921
 922           analyzeMethodBody(cd, md);
 923         }
 924       }
 925     }
 926
 927     _debug_printGraph();
 928   }
 929
 930   private void analyzeMethodBody(ClassDescriptor cd, MethodDescriptor md) {
 931     BlockNode bn = state.getMethodBody(md);
 932     NodeTupleSet implicitFlowTupleSet = new NodeTupleSet();
 933     analyzeFlowBlockNode(md, md.getParameterTable(), bn, implicitFlowTupleSet);
 934   }
 935
 936   private void analyzeFlowBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn,
 937       NodeTupleSet implicitFlowTupleSet) {
 938
 939     bn.getVarTable().setParent(nametable);
 940     for (int i = 0; i < bn.size(); i++) {
 941       BlockStatementNode bsn = bn.get(i);
 942       analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet);
 943     }
 944
 945   }
 946
 947   private void analyzeBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
 948       BlockStatementNode bsn, NodeTupleSet implicitFlowTupleSet) {
 949
 950     switch (bsn.kind()) {
 951     case Kind.BlockExpressionNode:
 952       analyzeBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn, implicitFlowTupleSet);
 953       break;
 954
 955     case Kind.DeclarationNode:
 956       analyzeFlowDeclarationNode(md, nametable, (DeclarationNode) bsn, implicitFlowTupleSet);
 957       break;
 958
 959     case Kind.IfStatementNode:
 960       analyzeFlowIfStatementNode(md, nametable, (IfStatementNode) bsn, implicitFlowTupleSet);
 961       break;
 962
 963     case Kind.LoopNode:
 964       analyzeFlowLoopNode(md, nametable, (LoopNode) bsn, implicitFlowTupleSet);
 965       break;
 966
 967     case Kind.ReturnNode:
 968       analyzeFlowReturnNode(md, nametable, (ReturnNode) bsn, implicitFlowTupleSet);
 969       break;
 970
 971     case Kind.SubBlockNode:
 972       analyzeFlowSubBlockNode(md, nametable, (SubBlockNode) bsn, implicitFlowTupleSet);
 973       break;
 974
 975     case Kind.ContinueBreakNode:
 976       break;
 977
 978     case Kind.SwitchStatementNode:
 979       analyzeSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn);
 980       break;
 981
 982     }
 983
 984   }
 985
 986   private void analyzeSwitchStatementNode(MethodDescriptor md, SymbolTable nametable,
 987       SwitchStatementNode bsn) {
 988     // TODO Auto-generated method stub
 989   }
 990
 991   private void analyzeFlowSubBlockNode(MethodDescriptor md, SymbolTable nametable,
 992       SubBlockNode sbn, NodeTupleSet implicitFlowTupleSet) {
 993     analyzeFlowBlockNode(md, nametable, sbn.getBlockNode(), implicitFlowTupleSet);
 994   }
 995
 996   private void analyzeFlowReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode rn,
 997       NodeTupleSet implicitFlowTupleSet) {
 998
 999     ExpressionNode returnExp = rn.getReturnExpression();
1000
1001     NodeTupleSet nodeSet = new NodeTupleSet();
1002     analyzeFlowExpressionNode(md, nametable, returnExp, nodeSet, false);
1003
1004     FlowGraph fg = getFlowGraph(md);
1005
1006     // annotate the elements of the node set as the return location
1007     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1008       NTuple<Descriptor> returnDescTuple = (NTuple<Descriptor>) iterator.next();
1009       fg.setReturnFlowNode(returnDescTuple);
1010       for (Iterator iterator2 = implicitFlowTupleSet.iterator(); iterator2.hasNext();) {
1011         NTuple<Descriptor> implicitFlowDescTuple = (NTuple<Descriptor>) iterator2.next();
1012         fg.addValueFlowEdge(implicitFlowDescTuple, returnDescTuple);
1013       }
1014     }
1015
1016   }
1017
1018   private void analyzeFlowLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln,
1019       NodeTupleSet implicitFlowTupleSet) {
1020
1021     if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) {
1022
1023       NodeTupleSet condTupleNode = new NodeTupleSet();
1024       analyzeFlowExpressionNode(md, nametable, ln.getCondition(), condTupleNode, null,
1025           implicitFlowTupleSet, false);
1026       condTupleNode.addTupleSet(implicitFlowTupleSet);
1027
1028       // add edges from condNodeTupleSet to all nodes of conditional nodes
1029       analyzeFlowBlockNode(md, nametable, ln.getBody(), condTupleNode);
1030
1031     } else {
1032       // check 'for loop' case
1033       BlockNode bn = ln.getInitializer();
1034       analyzeFlowBlockNode(md, bn.getVarTable(), bn, implicitFlowTupleSet);
1035       bn.getVarTable().setParent(nametable);
1036
1037       NodeTupleSet condTupleNode = new NodeTupleSet();
1038       analyzeFlowExpressionNode(md, bn.getVarTable(), ln.getCondition(), condTupleNode, null,
1039           implicitFlowTupleSet, false);
1040       condTupleNode.addTupleSet(implicitFlowTupleSet);
1041
1042       analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(), condTupleNode);
1043       analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(), condTupleNode);
1044
1045     }
1046
1047   }
1048
1049   private void analyzeFlowIfStatementNode(MethodDescriptor md, SymbolTable nametable,
1050       IfStatementNode isn, NodeTupleSet implicitFlowTupleSet) {
1051
1052     NodeTupleSet condTupleNode = new NodeTupleSet();
1053     analyzeFlowExpressionNode(md, nametable, isn.getCondition(), condTupleNode, null,
1054         implicitFlowTupleSet, false);
1055
1056     // add edges from condNodeTupleSet to all nodes of conditional nodes
1057     condTupleNode.addTupleSet(implicitFlowTupleSet);
1058     analyzeFlowBlockNode(md, nametable, isn.getTrueBlock(), condTupleNode);
1059
1060     if (isn.getFalseBlock() != null) {
1061       analyzeFlowBlockNode(md, nametable, isn.getFalseBlock(), condTupleNode);
1062     }
1063
1064   }
1065
1066   private void analyzeFlowDeclarationNode(MethodDescriptor md, SymbolTable nametable,
1067       DeclarationNode dn, NodeTupleSet implicitFlowTupleSet) {
1068
1069     VarDescriptor vd = dn.getVarDescriptor();
1070     NTuple<Descriptor> tupleLHS = new NTuple<Descriptor>();
1071     tupleLHS.add(vd);
1072     getFlowGraph(md).createNewFlowNode(tupleLHS);
1073
1074     if (dn.getExpression() != null) {
1075
1076       NodeTupleSet tupleSetRHS = new NodeTupleSet();
1077       analyzeFlowExpressionNode(md, nametable, dn.getExpression(), tupleSetRHS, null,
1078           implicitFlowTupleSet, false);
1079
1080       // add a new flow edge from rhs to lhs
1081       for (Iterator<NTuple<Descriptor>> iter = tupleSetRHS.iterator(); iter.hasNext();) {
1082         NTuple<Descriptor> from = iter.next();
1083         addFlowGraphEdge(md, from, tupleLHS);
1084       }
1085
1086     }
1087
1088   }
1089
1090   private void analyzeBlockExpressionNode(MethodDescriptor md, SymbolTable nametable,
1091       BlockExpressionNode ben, NodeTupleSet implicitFlowTupleSet) {
1092     analyzeFlowExpressionNode(md, nametable, ben.getExpression(), null, null, implicitFlowTupleSet,
1093         false);
1094   }
1095
1096   private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
1097       ExpressionNode en, NodeTupleSet nodeSet, boolean isLHS) {
1098     return analyzeFlowExpressionNode(md, nametable, en, nodeSet, null, new NodeTupleSet(), isLHS);
1099   }
1100
1101   private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
1102       ExpressionNode en, NodeTupleSet nodeSet, NTuple<Descriptor> base,
1103       NodeTupleSet implicitFlowTupleSet, boolean isLHS) {
1104
1105     // note that expression node can create more than one flow node
1106     // nodeSet contains of flow nodes
1107     // base is always assigned to null except the case of a name node!
1108
1109     NTuple<Descriptor> flowTuple;
1110
1111     switch (en.kind()) {
1112
1113     case Kind.AssignmentNode:
1114       analyzeFlowAssignmentNode(md, nametable, (AssignmentNode) en, base, implicitFlowTupleSet);
1115       break;
1116
1117     case Kind.FieldAccessNode:
1118       flowTuple =
1119           analyzeFlowFieldAccessNode(md, nametable, (FieldAccessNode) en, nodeSet, base,
1120               implicitFlowTupleSet);
1121       nodeSet.addTuple(flowTuple);
1122       return flowTuple;
1123
1124     case Kind.NameNode:
1125       NodeTupleSet nameNodeSet = new NodeTupleSet();
1126       flowTuple =
1127           analyzeFlowNameNode(md, nametable, (NameNode) en, nameNodeSet, base, implicitFlowTupleSet);
1128       nodeSet.addTuple(flowTuple);
1129       return flowTuple;
1130
1131     case Kind.OpNode:
1132       analyzeFlowOpNode(md, nametable, (OpNode) en, nodeSet, implicitFlowTupleSet);
1133       break;
1134
1135     case Kind.CreateObjectNode:
1136       analyzeCreateObjectNode(md, nametable, (CreateObjectNode) en);
1137       break;
1138
1139     case Kind.ArrayAccessNode:
1140       analyzeFlowArrayAccessNode(md, nametable, (ArrayAccessNode) en, nodeSet, isLHS);
1141       break;
1142
1143     case Kind.LiteralNode:
1144       analyzeLiteralNode(md, nametable, (LiteralNode) en);
1145       break;
1146
1147     case Kind.MethodInvokeNode:
1148       analyzeFlowMethodInvokeNode(md, nametable, (MethodInvokeNode) en, implicitFlowTupleSet);
1149       break;
1150
1151     case Kind.TertiaryNode:
1152       analyzeFlowTertiaryNode(md, nametable, (TertiaryNode) en, nodeSet, implicitFlowTupleSet);
1153       break;
1154
1155     case Kind.CastNode:
1156       analyzeFlowCastNode(md, nametable, (CastNode) en, implicitFlowTupleSet);
1157       break;
1158
1159     // case Kind.InstanceOfNode:
1160     // checkInstanceOfNode(md, nametable, (InstanceOfNode) en, td);
1161     // return null;
1162
1163     // case Kind.ArrayInitializerNode:
1164     // checkArrayInitializerNode(md, nametable, (ArrayInitializerNode) en,
1165     // td);
1166     // return null;
1167
1168     // case Kind.ClassTypeNode:
1169     // checkClassTypeNode(md, nametable, (ClassTypeNode) en, td);
1170     // return null;
1171
1172     // case Kind.OffsetNode:
1173     // checkOffsetNode(md, nametable, (OffsetNode)en, td);
1174     // return null;
1175
1176     }
1177     return null;
1178
1179   }
1180
1181   private void analyzeFlowCastNode(MethodDescriptor md, SymbolTable nametable, CastNode cn,
1182       NodeTupleSet implicitFlowTupleSet) {
1183
1184     NodeTupleSet nodeTupleSet = new NodeTupleSet();
1185     analyzeFlowExpressionNode(md, nametable, cn.getExpression(), nodeTupleSet, false);
1186
1187   }
1188
1189   private void analyzeFlowTertiaryNode(MethodDescriptor md, SymbolTable nametable, TertiaryNode tn,
1190       NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
1191
1192     NodeTupleSet tertiaryTupleNode = new NodeTupleSet();
1193     analyzeFlowExpressionNode(md, nametable, tn.getCond(), tertiaryTupleNode, null,
1194         implicitFlowTupleSet, false);
1195
1196     // add edges from tertiaryTupleNode to all nodes of conditional nodes
1197     tertiaryTupleNode.addTupleSet(implicitFlowTupleSet);
1198     analyzeFlowExpressionNode(md, nametable, tn.getTrueExpr(), tertiaryTupleNode, null,
1199         implicitFlowTupleSet, false);
1200
1201     analyzeFlowExpressionNode(md, nametable, tn.getFalseExpr(), tertiaryTupleNode, null,
1202         implicitFlowTupleSet, false);
1203
1204     nodeSet.addTupleSet(tertiaryTupleNode);
1205
1206   }
1207
1208   private void addMapCallerMethodDescToMethodInvokeNodeSet(MethodDescriptor caller,
1209       MethodInvokeNode min) {
1210     Set<MethodInvokeNode> set = mapMethodDescriptorToMethodInvokeNodeSet.get(caller);
1211     if (set == null) {
1212       set = new HashSet<MethodInvokeNode>();
1213       mapMethodDescriptorToMethodInvokeNodeSet.put(caller, set);
1214     }
1215     set.add(min);
1216   }
1217
1218   private void analyzeFlowMethodInvokeNode(MethodDescriptor md, SymbolTable nametable,
1219       MethodInvokeNode min, NodeTupleSet implicitFlowTupleSet) {
1220
1221     addMapCallerMethodDescToMethodInvokeNodeSet(md, min);
1222
1223     MethodDescriptor calleeMD = min.getMethod();
1224
1225     NameDescriptor baseName = min.getBaseName();
1226     boolean isSystemout = false;
1227     if (baseName != null) {
1228       isSystemout = baseName.getSymbol().equals("System.out");
1229     }
1230
1231     if (!ssjava.isSSJavaUtil(calleeMD.getClassDesc()) && !ssjava.isTrustMethod(calleeMD)
1232         && !calleeMD.getModifiers().isNative() && !isSystemout) {
1233
1234       // CompositeLocation baseLocation = null;
1235       if (min.getExpression() != null) {
1236
1237         NodeTupleSet baseNodeSet = new NodeTupleSet();
1238         analyzeFlowExpressionNode(calleeMD, nametable, min.getExpression(), baseNodeSet, null,
1239             implicitFlowTupleSet, false);
1240
1241       } else {
1242         if (min.getMethod().isStatic()) {
1243           // String globalLocId = ssjava.getMethodLattice(md).getGlobalLoc();
1244           // if (globalLocId == null) {
1245           // throw new
1246           // Error("Method lattice does not define global variable location at "
1247           // + generateErrorMessage(md.getClassDesc(), min));
1248           // }
1249           // baseLocation = new CompositeLocation(new Location(md,
1250           // globalLocId));
1251         } else {
1252           // 'this' var case
1253           // String thisLocId = ssjava.getMethodLattice(md).getThisLoc();
1254           // baseLocation = new CompositeLocation(new Location(md, thisLocId));
1255         }
1256       }
1257
1258       // constraint case:
1259       // if (constraint != null) {
1260       // int compareResult =
1261       // CompositeLattice.compare(constraint, baseLocation, true,
1262       // generateErrorMessage(cd, min));
1263       // if (compareResult != ComparisonResult.GREATER) {
1264       // // if the current constraint is higher than method's THIS location
1265       // // no need to check constraints!
1266       // CompositeLocation calleeConstraint =
1267       // translateCallerLocToCalleeLoc(calleeMD, baseLocation, constraint);
1268       // // System.out.println("check method body for constraint:" + calleeMD +
1269       // // " calleeConstraint="
1270       // // + calleeConstraint);
1271       // checkMethodBody(calleeMD.getClassDesc(), calleeMD, calleeConstraint);
1272       // }
1273       // }
1274
1275       analyzeFlowMethodParameters(md, nametable, min);
1276
1277       // checkCalleeConstraints(md, nametable, min, baseLocation, constraint);
1278
1279       // checkCallerArgumentLocationConstraints(md, nametable, min,
1280       // baseLocation, constraint);
1281
1282       if (!min.getMethod().getReturnType().isVoid()) {
1283         // If method has a return value, compute the highest possible return
1284         // location in the caller's perspective
1285         // CompositeLocation ceilingLoc =
1286         // computeCeilingLocationForCaller(md, nametable, min, baseLocation,
1287         // constraint);
1288         // return ceilingLoc;
1289       }
1290     }
1291
1292     // return new CompositeLocation(Location.createTopLocation(md));
1293
1294   }
1295
1296   private NTuple<Descriptor> getArgTupleByArgIdx(MethodInvokeNode min, int idx) {
1297     return mapMethodInvokeNodeToArgIdxMap.get(min).get(new Integer(idx));
1298   }
1299
1300   private void addArgIdxMap(MethodInvokeNode min, int idx, NTuple<Descriptor> argTuple) {
1301     Map<Integer, NTuple<Descriptor>> mapIdxToArgTuple = mapMethodInvokeNodeToArgIdxMap.get(min);
1302     if (mapIdxToArgTuple == null) {
1303       mapIdxToArgTuple = new HashMap<Integer, NTuple<Descriptor>>();
1304       mapMethodInvokeNodeToArgIdxMap.put(min, mapIdxToArgTuple);
1305     }
1306     mapIdxToArgTuple.put(new Integer(idx), argTuple);
1307   }
1308
1309   private void analyzeFlowMethodParameters(MethodDescriptor callermd, SymbolTable nametable,
1310       MethodInvokeNode min) {
1311
1312     if (min.numArgs() > 0) {
1313
1314       int offset = min.getMethod().isStatic() ? 0 : 1;
1315
1316       for (int i = 0; i < min.numArgs(); i++) {
1317         ExpressionNode en = min.getArg(i);
1318         NTuple<Descriptor> argTuple =
1319             analyzeFlowExpressionNode(callermd, nametable, en, new NodeTupleSet(), false);
1320
1321         addArgIdxMap(min, i + offset, argTuple);
1322       }
1323
1324     }
1325
1326   }
1327
1328   private void analyzeLiteralNode(MethodDescriptor md, SymbolTable nametable, LiteralNode en) {
1329     // TODO Auto-generated method stub
1330
1331   }
1332
1333   private void analyzeFlowArrayAccessNode(MethodDescriptor md, SymbolTable nametable,
1334       ArrayAccessNode aan, NodeTupleSet nodeSet, boolean isLHS) {
1335
1336     NodeTupleSet expNodeTupleSet = new NodeTupleSet();
1337     analyzeFlowExpressionNode(md, nametable, aan.getExpression(), expNodeTupleSet, isLHS);
1338
1339     NodeTupleSet idxNodeTupleSet = new NodeTupleSet();
1340     analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, isLHS);
1341
1342     if (isLHS) {
1343       // need to create an edge from idx to array
1344
1345       for (Iterator<NTuple<Descriptor>> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) {
1346         NTuple<Descriptor> idxTuple = idxIter.next();
1347         for (Iterator<NTuple<Descriptor>> arrIter = expNodeTupleSet.iterator(); arrIter.hasNext();) {
1348           NTuple<Descriptor> arrTuple = arrIter.next();
1349           getFlowGraph(md).addValueFlowEdge(idxTuple, arrTuple);
1350         }
1351       }
1352
1353       nodeSet.addTupleSet(expNodeTupleSet);
1354     } else {
1355       nodeSet.addTupleSet(expNodeTupleSet);
1356       nodeSet.addTupleSet(idxNodeTupleSet);
1357     }
1358
1359   }
1360
1361   private void analyzeCreateObjectNode(MethodDescriptor md, SymbolTable nametable,
1362       CreateObjectNode en) {
1363     // TODO Auto-generated method stub
1364
1365   }
1366
1367   private void analyzeFlowOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on,
1368       NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
1369
1370     NodeTupleSet leftOpSet = new NodeTupleSet();
1371     NodeTupleSet rightOpSet = new NodeTupleSet();
1372
1373     // left operand
1374     analyzeFlowExpressionNode(md, nametable, on.getLeft(), leftOpSet, null, implicitFlowTupleSet,
1375         false);
1376
1377     if (on.getRight() != null) {
1378       // right operand
1379       analyzeFlowExpressionNode(md, nametable, on.getRight(), rightOpSet, null,
1380           implicitFlowTupleSet, false);
1381     }
1382
1383     Operation op = on.getOp();
1384
1385     switch (op.getOp()) {
1386
1387     case Operation.UNARYPLUS:
1388     case Operation.UNARYMINUS:
1389     case Operation.LOGIC_NOT:
1390       // single operand
1391       nodeSet.addTupleSet(leftOpSet);
1392       break;
1393
1394     case Operation.LOGIC_OR:
1395     case Operation.LOGIC_AND:
1396     case Operation.COMP:
1397     case Operation.BIT_OR:
1398     case Operation.BIT_XOR:
1399     case Operation.BIT_AND:
1400     case Operation.ISAVAILABLE:
1401     case Operation.EQUAL:
1402     case Operation.NOTEQUAL:
1403     case Operation.LT:
1404     case Operation.GT:
1405     case Operation.LTE:
1406     case Operation.GTE:
1407     case Operation.ADD:
1408     case Operation.SUB:
1409     case Operation.MULT:
1410     case Operation.DIV:
1411     case Operation.MOD:
1412     case Operation.LEFTSHIFT:
1413     case Operation.RIGHTSHIFT:
1414     case Operation.URIGHTSHIFT:
1415
1416       // there are two operands
1417       nodeSet.addTupleSet(leftOpSet);
1418       nodeSet.addTupleSet(rightOpSet);
1419       break;
1420
1421     default:
1422       throw new Error(op.toString());
1423     }
1424   }
1425
1426   private NTuple<Descriptor> analyzeFlowNameNode(MethodDescriptor md, SymbolTable nametable,
1427       NameNode nn, NodeTupleSet nodeSet, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
1428
1429     if (base == null) {
1430       base = new NTuple<Descriptor>();
1431     }
1432
1433     NameDescriptor nd = nn.getName();
1434
1435     if (nd.getBase() != null) {
1436       analyzeFlowExpressionNode(md, nametable, nn.getExpression(), nodeSet, base,
1437           implicitFlowTupleSet, false);
1438     } else {
1439       String varname = nd.toString();
1440       if (varname.equals("this")) {
1441         // 'this' itself!
1442         base.add(md.getThis());
1443         return base;
1444       }
1445
1446       Descriptor d = (Descriptor) nametable.get(varname);
1447
1448       if (d instanceof VarDescriptor) {
1449         VarDescriptor vd = (VarDescriptor) d;
1450         base.add(vd);
1451       } else if (d instanceof FieldDescriptor) {
1452         // the type of field descriptor has a location!
1453         FieldDescriptor fd = (FieldDescriptor) d;
1454         if (fd.isStatic()) {
1455           if (fd.isFinal()) {
1456             // if it is 'static final', the location has TOP since no one can
1457             // change its value
1458             // loc.addLocation(Location.createTopLocation(md));
1459             // return loc;
1460           } else {
1461             // if 'static', the location has pre-assigned global loc
1462             // MethodLattice<String> localLattice = ssjava.getMethodLattice(md);
1463             // String globalLocId = localLattice.getGlobalLoc();
1464             // if (globalLocId == null) {
1465             // throw new
1466             // Error("Global location element is not defined in the method " +
1467             // md);
1468             // }
1469             // Location globalLoc = new Location(md, globalLocId);
1470             //
1471             // loc.addLocation(globalLoc);
1472           }
1473         } else {
1474           // the location of field access starts from this, followed by field
1475           // location
1476           base.add(md.getThis());
1477         }
1478
1479         base.add(fd);
1480       } else if (d == null) {
1481         // access static field
1482         // FieldDescriptor fd = nn.getField();addFlowGraphEdge
1483         //
1484         // MethodLattice<String> localLattice = ssjava.getMethodLattice(md);
1485         // String globalLocId = localLattice.getGlobalLoc();
1486         // if (globalLocId == null) {
1487         // throw new
1488         // Error("Method lattice does not define global variable location at "
1489         // + generateErrorMessage(md.getClassDesc(), nn));
1490         // }
1491         // loc.addLocation(new Location(md, globalLocId));
1492         //
1493         // Location fieldLoc = (Location) fd.getType().getExtension();
1494         // loc.addLocation(fieldLoc);
1495         //
1496         // return loc;
1497
1498       }
1499     }
1500
1501     getFlowGraph(md).createNewFlowNode(base);
1502
1503     return base;
1504
1505   }
1506
1507   private NTuple<Descriptor> analyzeFlowFieldAccessNode(MethodDescriptor md, SymbolTable nametable,
1508       FieldAccessNode fan, NodeTupleSet nodeSet, NTuple<Descriptor> base,
1509       NodeTupleSet implicitFlowTupleSet) {
1510
1511     ExpressionNode left = fan.getExpression();
1512     TypeDescriptor ltd = left.getType();
1513     FieldDescriptor fd = fan.getField();
1514
1515     String varName = null;
1516     if (left.kind() == Kind.NameNode) {
1517       NameDescriptor nd = ((NameNode) left).getName();
1518       varName = nd.toString();
1519     }
1520
1521     if (ltd.isClassNameRef() || (varName != null && varName.equals("this"))) {
1522       // using a class name directly or access using this
1523       if (fd.isStatic() && fd.isFinal()) {
1524         // loc.addLocation(Location.createTopLocation(md));
1525         // return loc;
1526       }
1527     }
1528
1529     // if (left instanceof ArrayAccessNode) {
1530     // ArrayAccessNode aan = (ArrayAccessNode) left;
1531     // left = aan.getExpression();
1532     // }
1533     // fanNodeSet
1534     base =
1535         analyzeFlowExpressionNode(md, nametable, left, nodeSet, base, implicitFlowTupleSet, false);
1536
1537     if (!left.getType().isPrimitive()) {
1538
1539       if (fd.getSymbol().equals("length")) {
1540         // TODO
1541         // array.length access, return the location of the array
1542         // return loc;
1543       }
1544
1545       base.add(fd);
1546     }
1547
1548     getFlowGraph(md).createNewFlowNode(base);
1549     return base;
1550
1551   }
1552
1553   private void analyzeFlowAssignmentNode(MethodDescriptor md, SymbolTable nametable,
1554       AssignmentNode an, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
1555
1556     NodeTupleSet nodeSetRHS = new NodeTupleSet();
1557     NodeTupleSet nodeSetLHS = new NodeTupleSet();
1558
1559     boolean postinc = true;
1560     if (an.getOperation().getBaseOp() == null
1561         || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
1562             .getBaseOp().getOp() != Operation.POSTDEC)) {
1563       postinc = false;
1564     }
1565
1566     // if LHS is array access node, need to capture value flows between an array
1567     // and its index value
1568     analyzeFlowExpressionNode(md, nametable, an.getDest(), nodeSetLHS, null, implicitFlowTupleSet,
1569         true);
1570
1571     if (!postinc) {
1572       // analyze value flows of rhs expression
1573       analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null, implicitFlowTupleSet,
1574           false);
1575
1576       // creates edges from RHS to LHS
1577       for (Iterator<NTuple<Descriptor>> iter = nodeSetRHS.iterator(); iter.hasNext();) {
1578         NTuple<Descriptor> fromTuple = iter.next();
1579         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
1580           NTuple<Descriptor> toTuple = iter2.next();
1581           addFlowGraphEdge(md, fromTuple, toTuple);
1582         }
1583       }
1584
1585       // creates edges from implicitFlowTupleSet to LHS
1586       for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
1587         NTuple<Descriptor> fromTuple = iter.next();
1588         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
1589           NTuple<Descriptor> toTuple = iter2.next();
1590           addFlowGraphEdge(md, fromTuple, toTuple);
1591         }
1592       }
1593
1594     } else {
1595       // postinc case
1596       for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
1597         NTuple<Descriptor> tuple = iter2.next();
1598         addFlowGraphEdge(md, tuple, tuple);
1599       }
1600
1601     }
1602
1603   }
1604
1605   public FlowGraph getFlowGraph(MethodDescriptor md) {
1606     return mapMethodDescriptorToFlowGraph.get(md);
1607   }
1608
1609   private boolean addFlowGraphEdge(MethodDescriptor md, NTuple<Descriptor> from,
1610       NTuple<Descriptor> to) {
1611     // TODO
1612     // return true if it adds a new edge
1613     FlowGraph graph = getFlowGraph(md);
1614     graph.addValueFlowEdge(from, to);
1615     return true;
1616   }
1617
1618   public void _debug_printGraph() {
1619     Set<MethodDescriptor> keySet = mapMethodDescriptorToFlowGraph.keySet();
1620
1621     for (Iterator<MethodDescriptor> iterator = keySet.iterator(); iterator.hasNext();) {
1622       MethodDescriptor md = (MethodDescriptor) iterator.next();
1623       FlowGraph fg = mapMethodDescriptorToFlowGraph.get(md);
1624       try {
1625         fg.writeGraph();
1626       } catch (IOException e) {
1627         e.printStackTrace();
1628       }
1629     }
1630
1631   }
1632
1633 }