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.Hashtable;
  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 Analysis.SSJava.FlowDownCheck.ComparisonResult;
  18 import Analysis.SSJava.FlowDownCheck.CompositeLattice;
  19 import IR.ClassDescriptor;
  20 import IR.Descriptor;
  21 import IR.FieldDescriptor;
  22 import IR.MethodDescriptor;
  23 import IR.NameDescriptor;
  24 import IR.Operation;
  25 import IR.State;
  26 import IR.SymbolTable;
  27 import IR.TypeDescriptor;
  28 import IR.VarDescriptor;
  29 import IR.Flat.FlatMethod;
  30 import IR.Tree.ArrayAccessNode;
  31 import IR.Tree.AssignmentNode;
  32 import IR.Tree.BlockExpressionNode;
  33 import IR.Tree.BlockNode;
  34 import IR.Tree.BlockStatementNode;
  35 import IR.Tree.CastNode;
  36 import IR.Tree.CreateObjectNode;
  37 import IR.Tree.DeclarationNode;
  38 import IR.Tree.ExpressionNode;
  39 import IR.Tree.FieldAccessNode;
  40 import IR.Tree.IfStatementNode;
  41 import IR.Tree.Kind;
  42 import IR.Tree.LiteralNode;
  43 import IR.Tree.LoopNode;
  44 import IR.Tree.MethodInvokeNode;
  45 import IR.Tree.NameNode;
  46 import IR.Tree.OpNode;
  47 import IR.Tree.ReturnNode;
  48 import IR.Tree.SubBlockNode;
  49 import IR.Tree.SwitchStatementNode;
  50 import IR.Tree.TertiaryNode;
  51
  52 public class LocationInference {
  53
  54   State state;
  55   SSJavaAnalysis ssjava;
  56
  57   List<ClassDescriptor> toanalyzeList;
  58   List<MethodDescriptor> toanalyzeMethodList;
  59   Map<MethodDescriptor, FlowGraph> mapMethodDescriptorToFlowGraph;
  60
  61   // keep current descriptors to visit in fixed-point interprocedural analysis,
  62   private Stack<MethodDescriptor> methodDescriptorsToVisitStack;
  63
  64   // map a class descriptor to a field lattice
  65   private Map<ClassDescriptor, SSJavaLattice<String>> cd2lattice;
  66
  67   // map a method descriptor to a method lattice
  68   private Map<MethodDescriptor, SSJavaLattice<String>> md2lattice;
  69
  70   // map a method descriptor to a lattice mapping
  71   private Map<MethodDescriptor, Map<VarDescriptor, String>> md2LatticeMapping;
  72
  73   // map a method descriptor to a lattice mapping
  74   private Map<MethodDescriptor, Map<FieldDescriptor, String>> cd2LatticeMapping;
  75
  76   boolean debug = true;
  77
  78   public LocationInference(SSJavaAnalysis ssjava, State state) {
  79     this.ssjava = ssjava;
  80     this.state = state;
  81     this.toanalyzeList = new ArrayList<ClassDescriptor>();
  82     this.toanalyzeMethodList = new ArrayList<MethodDescriptor>();
  83     this.mapMethodDescriptorToFlowGraph = new HashMap<MethodDescriptor, FlowGraph>();
  84     this.cd2lattice = new HashMap<ClassDescriptor, SSJavaLattice<String>>();
  85     this.md2lattice = new HashMap<MethodDescriptor, SSJavaLattice<String>>();
  86     this.methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
  87     this.md2LatticeMapping = new HashMap<MethodDescriptor, Map<VarDescriptor, String>>();
  88     this.cd2LatticeMapping = new HashMap<MethodDescriptor, Map<FieldDescriptor, String>>();
  89   }
  90
  91   public void setupToAnalyze() {
  92     SymbolTable classtable = state.getClassSymbolTable();
  93     toanalyzeList.clear();
  94     toanalyzeList.addAll(classtable.getValueSet());
  95     Collections.sort(toanalyzeList, new Comparator<ClassDescriptor>() {
  96       public int compare(ClassDescriptor o1, ClassDescriptor o2) {
  97         return o1.getClassName().compareToIgnoreCase(o2.getClassName());
  98       }
  99     });
 100   }
 101
 102   public void setupToAnalazeMethod(ClassDescriptor cd) {
 103
 104     SymbolTable methodtable = cd.getMethodTable();
 105     toanalyzeMethodList.clear();
 106     toanalyzeMethodList.addAll(methodtable.getValueSet());
 107     Collections.sort(toanalyzeMethodList, new Comparator<MethodDescriptor>() {
 108       public int compare(MethodDescriptor o1, MethodDescriptor o2) {
 109         return o1.getSymbol().compareToIgnoreCase(o2.getSymbol());
 110       }
 111     });
 112   }
 113
 114   public boolean toAnalyzeMethodIsEmpty() {
 115     return toanalyzeMethodList.isEmpty();
 116   }
 117
 118   public boolean toAnalyzeIsEmpty() {
 119     return toanalyzeList.isEmpty();
 120   }
 121
 122   public ClassDescriptor toAnalyzeNext() {
 123     return toanalyzeList.remove(0);
 124   }
 125
 126   public MethodDescriptor toAnalyzeMethodNext() {
 127     return toanalyzeMethodList.remove(0);
 128   }
 129
 130   public void inference() {
 131
 132     // 1) construct value flow graph
 133     constructFlowGraph();
 134
 135     // 2) construct lattices
 136     inferLattices();
 137
 138     debug_writeLatticeDotFile();
 139
 140   }
 141
 142   private void debug_writeLatticeDotFile() {
 143     // generate lattice dot file
 144
 145     setupToAnalyze();
 146
 147     while (!toAnalyzeIsEmpty()) {
 148       ClassDescriptor cd = toAnalyzeNext();
 149
 150       setupToAnalazeMethod(cd);
 151
 152       SSJavaLattice<String> classLattice = cd2lattice.get(cd);
 153       if (classLattice != null) {
 154         ssjava.writeLatticeDotFile(cd, classLattice);
 155       }
 156
 157       while (!toAnalyzeMethodIsEmpty()) {
 158         MethodDescriptor md = toAnalyzeMethodNext();
 159         if (ssjava.needTobeAnnotated(md)) {
 160           SSJavaLattice<String> methodLattice = md2lattice.get(md);
 161           if (methodLattice != null) {
 162             ssjava.writeLatticeDotFile(cd, methodLattice);
 163           }
 164         }
 165       }
 166     }
 167
 168   }
 169
 170   private void inferLattices() {
 171
 172     // do fixed-point analysis
 173
 174     // perform method READ/OVERWRITE analysis
 175     LinkedList<MethodDescriptor> descriptorListToAnalyze = ssjava.getSortedDescriptors();
 176
 177     // current descriptors to visit in fixed-point interprocedural analysis,
 178     // prioritized by
 179     // dependency in the call graph
 180     methodDescriptorsToVisitStack.clear();
 181
 182     descriptorListToAnalyze.removeFirst();
 183
 184     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
 185     methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
 186
 187     while (!descriptorListToAnalyze.isEmpty()) {
 188       MethodDescriptor md = descriptorListToAnalyze.removeFirst();
 189       methodDescriptorsToVisitStack.add(md);
 190     }
 191
 192     // analyze scheduled methods until there are no more to visit
 193     while (!methodDescriptorsToVisitStack.isEmpty()) {
 194       // start to analyze leaf node
 195       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
 196       FlatMethod fm = state.getMethodFlat(md);
 197
 198       SSJavaLattice<String> methodLattice =
 199           new SSJavaLattice<String>(SSJavaLattice.TOP, SSJavaLattice.BOTTOM);
 200
 201       analyzeMethodLattice(md, methodLattice);
 202
 203       SSJavaLattice<String> prevMethodLattice = md2lattice.get(md);
 204
 205       if (!methodLattice.equals(prevMethodLattice)) {
 206         md2lattice.put(md, methodLattice);
 207
 208         // results for callee changed, so enqueue dependents caller for
 209         // further analysis
 210         Iterator<MethodDescriptor> depsItr = ssjava.getDependents(md).iterator();
 211         while (depsItr.hasNext()) {
 212           MethodDescriptor methodNext = depsItr.next();
 213           if (!methodDescriptorsToVisitStack.contains(methodNext)
 214               && methodDescriptorToVistSet.contains(methodNext)) {
 215             methodDescriptorsToVisitStack.add(methodNext);
 216           }
 217         }
 218
 219       }
 220
 221     }
 222
 223   }
 224
 225   private String getSymbol(int idx, FlowNode node) {
 226     Descriptor desc = node.getDescTuple().get(idx);
 227     return desc.getSymbol();
 228   }
 229
 230   private void addMappingDescriptorToLocationIdentifer(MethodDescriptor methodDesc,
 231       VarDescriptor varDesc, String identifier) {
 232     if (!md2LatticeMapping.containsKey(methodDesc)) {
 233       md2LatticeMapping.put(methodDesc, new HashMap<VarDescriptor, String>());
 234     }
 235
 236   }
 237
 238   private void analyzeMethodLattice(MethodDescriptor md, SSJavaLattice<String> methodLattice) {
 239
 240     System.out.println("# Create the method lattice for " + md);
 241
 242     // visit each node of method flow graph
 243
 244     FlowGraph fg = getFlowGraph(md);
 245     Set<FlowNode> nodeSet = fg.getNodeSet();
 246
 247     // for the method lattice, we need to look at the first element of
 248     // NTuple<Descriptor>
 249
 250     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 251       FlowNode srcNode = (FlowNode) iterator.next();
 252
 253       Set<FlowEdge> outEdgeSet = srcNode.getOutEdgeSet();
 254       for (Iterator iterator2 = outEdgeSet.iterator(); iterator2.hasNext();) {
 255         FlowEdge outEdge = (FlowEdge) iterator2.next();
 256
 257         FlowNode dstNode = outEdge.getDst();
 258
 259         if ((srcNode.getDescTuple().size() > 1 && dstNode.getDescTuple().size() > 1)
 260             && srcNode.getDescTuple().get(0).equals(dstNode.getDescTuple().get(0))) {
 261           // value flow between fields: we don't need to add a binary relation
 262           // for this case
 263
 264           VarDescriptor varDesc = (VarDescriptor) srcNode.getDescTuple().get(0);
 265           ClassDescriptor varClassDesc = varDesc.getType().getClassDesc();
 266
 267           extractRelationFromFieldFlows(varClassDesc, srcNode, dstNode, 1);
 268           continue;
 269         }
 270
 271         // add a new binary relation of dstNode < srcNode
 272
 273         String srcSymbol = getSymbol(0, srcNode);
 274         String dstSymbol = getSymbol(0, dstNode);
 275
 276         methodLattice.addRelationHigherToLower(srcSymbol, dstSymbol);
 277
 278       }
 279
 280     }
 281
 282   }
 283
 284   private void extractRelationFromFieldFlows(ClassDescriptor cd, FlowNode srcNode,
 285       FlowNode dstNode, int idx) {
 286
 287     if (srcNode.getDescTuple().get(idx).equals(dstNode.getDescTuple().get(idx))) {
 288       // value flow between fields: we don't need to add a binary relation
 289       // for this case
 290       VarDescriptor varDesc = (VarDescriptor) srcNode.getDescTuple().get(idx);
 291       ClassDescriptor varClassDesc = varDesc.getType().getClassDesc();
 292       extractRelationFromFieldFlows(varClassDesc, srcNode, dstNode, idx + 1);
 293     } else {
 294
 295       Descriptor srcFieldDesc = srcNode.getDescTuple().get(idx);
 296       Descriptor dstFieldDesc = dstNode.getDescTuple().get(idx);
 297
 298       // add a new binary relation of dstNode < srcNode
 299
 300       SSJavaLattice<String> fieldLattice = getFieldLattice(cd);
 301       fieldLattice.addRelationHigherToLower(srcFieldDesc.getSymbol(), dstFieldDesc.getSymbol());
 302
 303     }
 304
 305   }
 306
 307   public SSJavaLattice<String> getFieldLattice(ClassDescriptor cd) {
 308     if (!cd2lattice.containsKey(cd)) {
 309       cd2lattice.put(cd, new SSJavaLattice<String>(SSJavaLattice.TOP, SSJavaLattice.BOTTOM));
 310     }
 311     return cd2lattice.get(cd);
 312   }
 313
 314   public void constructFlowGraph() {
 315
 316     setupToAnalyze();
 317
 318     while (!toAnalyzeIsEmpty()) {
 319       ClassDescriptor cd = toAnalyzeNext();
 320
 321       setupToAnalazeMethod(cd);
 322       while (!toAnalyzeMethodIsEmpty()) {
 323         MethodDescriptor md = toAnalyzeMethodNext();
 324         if (ssjava.needTobeAnnotated(md)) {
 325           if (state.SSJAVADEBUG) {
 326             System.out.println("SSJAVA: Constructing a flow graph: " + md);
 327           }
 328           FlowGraph fg = new FlowGraph(md);
 329           mapMethodDescriptorToFlowGraph.put(md, fg);
 330           analyzeMethodBody(cd, md);
 331         }
 332       }
 333     }
 334
 335     _debug_printGraph();
 336   }
 337
 338   private void analyzeMethodBody(ClassDescriptor cd, MethodDescriptor md) {
 339     BlockNode bn = state.getMethodBody(md);
 340     NodeTupleSet implicitFlowTupleSet = new NodeTupleSet();
 341     analyzeFlowBlockNode(md, md.getParameterTable(), bn, implicitFlowTupleSet);
 342   }
 343
 344   private void analyzeFlowBlockNode(MethodDescriptor md, SymbolTable nametable, BlockNode bn,
 345       NodeTupleSet implicitFlowTupleSet) {
 346
 347     bn.getVarTable().setParent(nametable);
 348     for (int i = 0; i < bn.size(); i++) {
 349       BlockStatementNode bsn = bn.get(i);
 350       analyzeBlockStatementNode(md, bn.getVarTable(), bsn, implicitFlowTupleSet);
 351     }
 352
 353   }
 354
 355   private void analyzeBlockStatementNode(MethodDescriptor md, SymbolTable nametable,
 356       BlockStatementNode bsn, NodeTupleSet implicitFlowTupleSet) {
 357
 358     switch (bsn.kind()) {
 359     case Kind.BlockExpressionNode:
 360       analyzeBlockExpressionNode(md, nametable, (BlockExpressionNode) bsn, implicitFlowTupleSet);
 361       break;
 362
 363     case Kind.DeclarationNode:
 364       analyzeFlowDeclarationNode(md, nametable, (DeclarationNode) bsn, implicitFlowTupleSet);
 365       break;
 366
 367     case Kind.IfStatementNode:
 368       analyzeFlowIfStatementNode(md, nametable, (IfStatementNode) bsn, implicitFlowTupleSet);
 369       break;
 370
 371     case Kind.LoopNode:
 372       analyzeFlowLoopNode(md, nametable, (LoopNode) bsn, implicitFlowTupleSet);
 373       break;
 374
 375     case Kind.ReturnNode:
 376       analyzeReturnNode(md, nametable, (ReturnNode) bsn);
 377       break;
 378
 379     case Kind.SubBlockNode:
 380       analyzeFlowSubBlockNode(md, nametable, (SubBlockNode) bsn, implicitFlowTupleSet);
 381       break;
 382
 383     case Kind.ContinueBreakNode:
 384       break;
 385
 386     case Kind.SwitchStatementNode:
 387       analyzeSwitchStatementNode(md, nametable, (SwitchStatementNode) bsn);
 388       break;
 389
 390     }
 391
 392   }
 393
 394   private void analyzeSwitchStatementNode(MethodDescriptor md, SymbolTable nametable,
 395       SwitchStatementNode bsn) {
 396     // TODO Auto-generated method stub
 397
 398   }
 399
 400   private void analyzeFlowSubBlockNode(MethodDescriptor md, SymbolTable nametable,
 401       SubBlockNode sbn, NodeTupleSet implicitFlowTupleSet) {
 402     analyzeFlowBlockNode(md, nametable, sbn.getBlockNode(), implicitFlowTupleSet);
 403   }
 404
 405   private void analyzeReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode bsn) {
 406     // TODO Auto-generated method stub
 407
 408   }
 409
 410   private void analyzeFlowLoopNode(MethodDescriptor md, SymbolTable nametable, LoopNode ln,
 411       NodeTupleSet implicitFlowTupleSet) {
 412
 413     if (ln.getType() == LoopNode.WHILELOOP || ln.getType() == LoopNode.DOWHILELOOP) {
 414
 415       NodeTupleSet condTupleNode = new NodeTupleSet();
 416       analyzeFlowExpressionNode(md, nametable, ln.getCondition(), condTupleNode, null,
 417           implicitFlowTupleSet, false);
 418       condTupleNode.addTupleSet(implicitFlowTupleSet);
 419
 420       // add edges from condNodeTupleSet to all nodes of conditional nodes
 421       analyzeFlowBlockNode(md, nametable, ln.getBody(), condTupleNode);
 422
 423     } else {
 424       // check 'for loop' case
 425       BlockNode bn = ln.getInitializer();
 426       analyzeFlowBlockNode(md, bn.getVarTable(), bn, implicitFlowTupleSet);
 427       bn.getVarTable().setParent(nametable);
 428
 429       NodeTupleSet condTupleNode = new NodeTupleSet();
 430       analyzeFlowExpressionNode(md, bn.getVarTable(), ln.getCondition(), condTupleNode, null,
 431           implicitFlowTupleSet, false);
 432       condTupleNode.addTupleSet(implicitFlowTupleSet);
 433
 434       analyzeFlowBlockNode(md, bn.getVarTable(), ln.getUpdate(), condTupleNode);
 435       analyzeFlowBlockNode(md, bn.getVarTable(), ln.getBody(), condTupleNode);
 436
 437     }
 438
 439   }
 440
 441   private void analyzeFlowIfStatementNode(MethodDescriptor md, SymbolTable nametable,
 442       IfStatementNode isn, NodeTupleSet implicitFlowTupleSet) {
 443
 444     NodeTupleSet condTupleNode = new NodeTupleSet();
 445     analyzeFlowExpressionNode(md, nametable, isn.getCondition(), condTupleNode, null,
 446         implicitFlowTupleSet, false);
 447
 448     // add edges from condNodeTupleSet to all nodes of conditional nodes
 449     condTupleNode.addTupleSet(implicitFlowTupleSet);
 450     analyzeFlowBlockNode(md, nametable, isn.getTrueBlock(), condTupleNode);
 451
 452     if (isn.getFalseBlock() != null) {
 453       analyzeFlowBlockNode(md, nametable, isn.getFalseBlock(), condTupleNode);
 454     }
 455
 456   }
 457
 458   private void analyzeFlowDeclarationNode(MethodDescriptor md, SymbolTable nametable,
 459       DeclarationNode dn, NodeTupleSet implicitFlowTupleSet) {
 460
 461     VarDescriptor vd = dn.getVarDescriptor();
 462     NTuple<Descriptor> tupleLHS = new NTuple<Descriptor>();
 463     tupleLHS.add(vd);
 464     getFlowGraph(md).createNewFlowNode(tupleLHS);
 465
 466     if (dn.getExpression() != null) {
 467
 468       NodeTupleSet tupleSetRHS = new NodeTupleSet();
 469       analyzeFlowExpressionNode(md, nametable, dn.getExpression(), tupleSetRHS, null,
 470           implicitFlowTupleSet, false);
 471
 472       // add a new flow edge from rhs to lhs
 473       for (Iterator<NTuple<Descriptor>> iter = tupleSetRHS.iterator(); iter.hasNext();) {
 474         NTuple<Descriptor> from = iter.next();
 475         addFlowGraphEdge(md, from, tupleLHS);
 476       }
 477
 478     }
 479
 480   }
 481
 482   private void analyzeBlockExpressionNode(MethodDescriptor md, SymbolTable nametable,
 483       BlockExpressionNode ben, NodeTupleSet implicitFlowTupleSet) {
 484     analyzeFlowExpressionNode(md, nametable, ben.getExpression(), null, null, implicitFlowTupleSet,
 485         false);
 486   }
 487
 488   private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
 489       ExpressionNode en, NodeTupleSet nodeSet, boolean isLHS) {
 490     return analyzeFlowExpressionNode(md, nametable, en, nodeSet, null, new NodeTupleSet(), isLHS);
 491   }
 492
 493   private NTuple<Descriptor> analyzeFlowExpressionNode(MethodDescriptor md, SymbolTable nametable,
 494       ExpressionNode en, NodeTupleSet nodeSet, NTuple<Descriptor> base,
 495       NodeTupleSet implicitFlowTupleSet, boolean isLHS) {
 496
 497     // note that expression node can create more than one flow node
 498     // nodeSet contains of flow nodes
 499     // base is always assigned to null except name node case!
 500
 501     NTuple<Descriptor> flowTuple;
 502
 503     switch (en.kind()) {
 504
 505     case Kind.AssignmentNode:
 506       analyzeFlowAssignmentNode(md, nametable, (AssignmentNode) en, base, implicitFlowTupleSet);
 507       break;
 508
 509     case Kind.FieldAccessNode:
 510       flowTuple =
 511           analyzeFlowFieldAccessNode(md, nametable, (FieldAccessNode) en, nodeSet, base,
 512               implicitFlowTupleSet);
 513       nodeSet.addTuple(flowTuple);
 514       return flowTuple;
 515
 516     case Kind.NameNode:
 517       NodeTupleSet nameNodeSet = new NodeTupleSet();
 518       flowTuple =
 519           analyzeFlowNameNode(md, nametable, (NameNode) en, nameNodeSet, base, implicitFlowTupleSet);
 520       nodeSet.addTuple(flowTuple);
 521       return flowTuple;
 522
 523     case Kind.OpNode:
 524       analyzeFlowOpNode(md, nametable, (OpNode) en, nodeSet, implicitFlowTupleSet);
 525       break;
 526
 527     case Kind.CreateObjectNode:
 528       analyzeCreateObjectNode(md, nametable, (CreateObjectNode) en);
 529       break;
 530
 531     case Kind.ArrayAccessNode:
 532       analyzeFlowArrayAccessNode(md, nametable, (ArrayAccessNode) en, nodeSet, isLHS);
 533       break;
 534
 535     case Kind.LiteralNode:
 536       analyzeLiteralNode(md, nametable, (LiteralNode) en);
 537       break;
 538
 539     case Kind.MethodInvokeNode:
 540       analyzeFlowMethodInvokeNode(md, nametable, (MethodInvokeNode) en, implicitFlowTupleSet);
 541       break;
 542
 543     case Kind.TertiaryNode:
 544       analyzeFlowTertiaryNode(md, nametable, (TertiaryNode) en, nodeSet, implicitFlowTupleSet);
 545       break;
 546
 547     case Kind.CastNode:
 548       analyzeFlowCastNode(md, nametable, (CastNode) en, implicitFlowTupleSet);
 549       break;
 550
 551     // case Kind.InstanceOfNode:
 552     // checkInstanceOfNode(md, nametable, (InstanceOfNode) en, td);
 553     // return null;
 554
 555     // case Kind.ArrayInitializerNode:
 556     // checkArrayInitializerNode(md, nametable, (ArrayInitializerNode) en,
 557     // td);
 558     // return null;
 559
 560     // case Kind.ClassTypeNode:
 561     // checkClassTypeNode(md, nametable, (ClassTypeNode) en, td);
 562     // return null;
 563
 564     // case Kind.OffsetNode:
 565     // checkOffsetNode(md, nametable, (OffsetNode)en, td);
 566     // return null;
 567
 568     }
 569     return null;
 570
 571   }
 572
 573   private void analyzeFlowCastNode(MethodDescriptor md, SymbolTable nametable, CastNode cn,
 574       NodeTupleSet implicitFlowTupleSet) {
 575
 576     NodeTupleSet nodeTupleSet = new NodeTupleSet();
 577     analyzeFlowExpressionNode(md, nametable, cn.getExpression(), nodeTupleSet, false);
 578
 579   }
 580
 581   private void analyzeFlowTertiaryNode(MethodDescriptor md, SymbolTable nametable, TertiaryNode tn,
 582       NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
 583
 584     System.out.println("### analyzeFlowTertiaryNode=" + tn.printNode(0));
 585
 586     NodeTupleSet tertiaryTupleNode = new NodeTupleSet();
 587     analyzeFlowExpressionNode(md, nametable, tn.getCond(), tertiaryTupleNode, null,
 588         implicitFlowTupleSet, false);
 589
 590     // add edges from tertiaryTupleNode to all nodes of conditional nodes
 591     tertiaryTupleNode.addTupleSet(implicitFlowTupleSet);
 592     System.out.println("### TertiarayNode's condition=" + tertiaryTupleNode);
 593     analyzeFlowExpressionNode(md, nametable, tn.getTrueExpr(), tertiaryTupleNode, null,
 594         implicitFlowTupleSet, false);
 595
 596     analyzeFlowExpressionNode(md, nametable, tn.getFalseExpr(), tertiaryTupleNode, null,
 597         implicitFlowTupleSet, false);
 598
 599     nodeSet.addTupleSet(tertiaryTupleNode);
 600
 601   }
 602
 603   private void analyzeFlowMethodInvokeNode(MethodDescriptor md, SymbolTable nametable,
 604       MethodInvokeNode min, NodeTupleSet implicitFlowTupleSet) {
 605
 606     MethodDescriptor calleeMD = min.getMethod();
 607
 608     NameDescriptor baseName = min.getBaseName();
 609     boolean isSystemout = false;
 610     if (baseName != null) {
 611       isSystemout = baseName.getSymbol().equals("System.out");
 612     }
 613
 614     if (!ssjava.isSSJavaUtil(calleeMD.getClassDesc()) && !ssjava.isTrustMethod(calleeMD)
 615         && !calleeMD.getModifiers().isNative() && !isSystemout) {
 616
 617       // CompositeLocation baseLocation = null;
 618       if (min.getExpression() != null) {
 619
 620         NodeTupleSet baseNodeSet = new NodeTupleSet();
 621         System.out.println("Analyzing base of method=" + min.getExpression());
 622         analyzeFlowExpressionNode(calleeMD, nametable, min.getExpression(), baseNodeSet, null,
 623             implicitFlowTupleSet, false);
 624
 625       } else {
 626         if (min.getMethod().isStatic()) {
 627           // String globalLocId = ssjava.getMethodLattice(md).getGlobalLoc();
 628           // if (globalLocId == null) {
 629           // throw new
 630           // Error("Method lattice does not define global variable location at "
 631           // + generateErrorMessage(md.getClassDesc(), min));
 632           // }
 633           // baseLocation = new CompositeLocation(new Location(md,
 634           // globalLocId));
 635         } else {
 636           // 'this' var case
 637           // String thisLocId = ssjava.getMethodLattice(md).getThisLoc();
 638           // baseLocation = new CompositeLocation(new Location(md, thisLocId));
 639         }
 640       }
 641
 642       // constraint case:
 643       // if (constraint != null) {
 644       // int compareResult =
 645       // CompositeLattice.compare(constraint, baseLocation, true,
 646       // generateErrorMessage(cd, min));
 647       // if (compareResult != ComparisonResult.GREATER) {
 648       // // if the current constraint is higher than method's THIS location
 649       // // no need to check constraints!
 650       // CompositeLocation calleeConstraint =
 651       // translateCallerLocToCalleeLoc(calleeMD, baseLocation, constraint);
 652       // // System.out.println("check method body for constraint:" + calleeMD +
 653       // // " calleeConstraint="
 654       // // + calleeConstraint);
 655       // checkMethodBody(calleeMD.getClassDesc(), calleeMD, calleeConstraint);
 656       // }
 657       // }
 658
 659       // checkCalleeConstraints(md, nametable, min, baseLocation, constraint);
 660
 661       // checkCallerArgumentLocationConstraints(md, nametable, min,
 662       // baseLocation, constraint);
 663
 664       if (!min.getMethod().getReturnType().isVoid()) {
 665         // If method has a return value, compute the highest possible return
 666         // location in the caller's perspective
 667         // CompositeLocation ceilingLoc =
 668         // computeCeilingLocationForCaller(md, nametable, min, baseLocation,
 669         // constraint);
 670         // return ceilingLoc;
 671       }
 672     }
 673
 674     // return new CompositeLocation(Location.createTopLocation(md));
 675
 676   }
 677
 678   private void analyzeLiteralNode(MethodDescriptor md, SymbolTable nametable, LiteralNode en) {
 679     // TODO Auto-generated method stub
 680
 681   }
 682
 683   private void analyzeFlowArrayAccessNode(MethodDescriptor md, SymbolTable nametable,
 684       ArrayAccessNode aan, NodeTupleSet nodeSet, boolean isLHS) {
 685
 686     NodeTupleSet expNodeTupleSet = new NodeTupleSet();
 687     analyzeFlowExpressionNode(md, nametable, aan.getExpression(), expNodeTupleSet, isLHS);
 688
 689     NodeTupleSet idxNodeTupleSet = new NodeTupleSet();
 690     analyzeFlowExpressionNode(md, nametable, aan.getIndex(), idxNodeTupleSet, isLHS);
 691
 692     if (isLHS) {
 693       // need to create an edge from idx to array
 694
 695       for (Iterator<NTuple<Descriptor>> idxIter = idxNodeTupleSet.iterator(); idxIter.hasNext();) {
 696         NTuple<Descriptor> idxTuple = idxIter.next();
 697         for (Iterator<NTuple<Descriptor>> arrIter = expNodeTupleSet.iterator(); arrIter.hasNext();) {
 698           NTuple<Descriptor> arrTuple = arrIter.next();
 699           getFlowGraph(md).addValueFlowEdge(idxTuple, arrTuple);
 700         }
 701       }
 702
 703       nodeSet.addTupleSet(expNodeTupleSet);
 704     } else {
 705       nodeSet.addTupleSet(expNodeTupleSet);
 706       nodeSet.addTupleSet(idxNodeTupleSet);
 707     }
 708
 709   }
 710
 711   private void analyzeCreateObjectNode(MethodDescriptor md, SymbolTable nametable,
 712       CreateObjectNode en) {
 713     // TODO Auto-generated method stub
 714
 715   }
 716
 717   private void analyzeFlowOpNode(MethodDescriptor md, SymbolTable nametable, OpNode on,
 718       NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) {
 719
 720     NodeTupleSet leftOpSet = new NodeTupleSet();
 721     NodeTupleSet rightOpSet = new NodeTupleSet();
 722
 723     // left operand
 724     System.out.println("Analyzing left op=" + on.getLeft().printNode(0) + "::"
 725         + on.getLeft().getClass());
 726     analyzeFlowExpressionNode(md, nametable, on.getLeft(), leftOpSet, null, implicitFlowTupleSet,
 727         false);
 728     System.out.println("leftOpSet=" + leftOpSet);
 729
 730     if (on.getRight() != null) {
 731       // right operand
 732       analyzeFlowExpressionNode(md, nametable, on.getRight(), rightOpSet, null,
 733           implicitFlowTupleSet, false);
 734       System.out.println("rightOpSet=" + rightOpSet);
 735     }
 736
 737     Operation op = on.getOp();
 738
 739     switch (op.getOp()) {
 740
 741     case Operation.UNARYPLUS:
 742     case Operation.UNARYMINUS:
 743     case Operation.LOGIC_NOT:
 744       // single operand
 745       nodeSet.addTupleSet(leftOpSet);
 746       break;
 747
 748     case Operation.LOGIC_OR:
 749     case Operation.LOGIC_AND:
 750     case Operation.COMP:
 751     case Operation.BIT_OR:
 752     case Operation.BIT_XOR:
 753     case Operation.BIT_AND:
 754     case Operation.ISAVAILABLE:
 755     case Operation.EQUAL:
 756     case Operation.NOTEQUAL:
 757     case Operation.LT:
 758     case Operation.GT:
 759     case Operation.LTE:
 760     case Operation.GTE:
 761     case Operation.ADD:
 762     case Operation.SUB:
 763     case Operation.MULT:
 764     case Operation.DIV:
 765     case Operation.MOD:
 766     case Operation.LEFTSHIFT:
 767     case Operation.RIGHTSHIFT:
 768     case Operation.URIGHTSHIFT:
 769
 770       // there are two operands
 771       nodeSet.addTupleSet(leftOpSet);
 772       nodeSet.addTupleSet(rightOpSet);
 773       break;
 774
 775     default:
 776       throw new Error(op.toString());
 777     }
 778   }
 779
 780   private NTuple<Descriptor> analyzeFlowNameNode(MethodDescriptor md, SymbolTable nametable,
 781       NameNode nn, NodeTupleSet nodeSet, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
 782
 783     if (base == null) {
 784       base = new NTuple<Descriptor>();
 785     }
 786
 787     NameDescriptor nd = nn.getName();
 788
 789     if (nd.getBase() != null) {
 790       analyzeFlowExpressionNode(md, nametable, nn.getExpression(), nodeSet, base,
 791           implicitFlowTupleSet, false);
 792     } else {
 793       String varname = nd.toString();
 794       if (varname.equals("this")) {
 795         // 'this' itself!
 796         base.add(md.getThis());
 797         return base;
 798       }
 799
 800       Descriptor d = (Descriptor) nametable.get(varname);
 801
 802       if (d instanceof VarDescriptor) {
 803         VarDescriptor vd = (VarDescriptor) d;
 804         base.add(vd);
 805       } else if (d instanceof FieldDescriptor) {
 806         // the type of field descriptor has a location!
 807         FieldDescriptor fd = (FieldDescriptor) d;
 808         if (fd.isStatic()) {
 809           if (fd.isFinal()) {
 810             // if it is 'static final', the location has TOP since no one can
 811             // change its value
 812             // loc.addLocation(Location.createTopLocation(md));
 813             // return loc;
 814           } else {
 815             // if 'static', the location has pre-assigned global loc
 816             // MethodLattice<String> localLattice = ssjava.getMethodLattice(md);
 817             // String globalLocId = localLattice.getGlobalLoc();
 818             // if (globalLocId == null) {
 819             // throw new
 820             // Error("Global location element is not defined in the method " +
 821             // md);
 822             // }
 823             // Location globalLoc = new Location(md, globalLocId);
 824             //
 825             // loc.addLocation(globalLoc);
 826           }
 827         } else {
 828           // the location of field access starts from this, followed by field
 829           // location
 830           base.add(md.getThis());
 831         }
 832
 833         base.add(fd);
 834       } else if (d == null) {
 835         // access static field
 836         // FieldDescriptor fd = nn.getField();addFlowGraphEdge
 837         //
 838         // MethodLattice<String> localLattice = ssjava.getMethodLattice(md);
 839         // String globalLocId = localLattice.getGlobalLoc();
 840         // if (globalLocId == null) {
 841         // throw new
 842         // Error("Method lattice does not define global variable location at "
 843         // + generateErrorMessage(md.getClassDesc(), nn));
 844         // }
 845         // loc.addLocation(new Location(md, globalLocId));
 846         //
 847         // Location fieldLoc = (Location) fd.getType().getExtension();
 848         // loc.addLocation(fieldLoc);
 849         //
 850         // return loc;
 851
 852       }
 853     }
 854
 855     getFlowGraph(md).createNewFlowNode(base);
 856
 857     return base;
 858
 859   }
 860
 861   private NTuple<Descriptor> analyzeFlowFieldAccessNode(MethodDescriptor md, SymbolTable nametable,
 862       FieldAccessNode fan, NodeTupleSet nodeSet, NTuple<Descriptor> base,
 863       NodeTupleSet implicitFlowTupleSet) {
 864
 865     ExpressionNode left = fan.getExpression();
 866     TypeDescriptor ltd = left.getType();
 867     FieldDescriptor fd = fan.getField();
 868
 869     String varName = null;
 870     if (left.kind() == Kind.NameNode) {
 871       NameDescriptor nd = ((NameNode) left).getName();
 872       varName = nd.toString();
 873     }
 874
 875     if (ltd.isClassNameRef() || (varName != null && varName.equals("this"))) {
 876       // using a class name directly or access using this
 877       if (fd.isStatic() && fd.isFinal()) {
 878         // loc.addLocation(Location.createTopLocation(md));
 879         // return loc;
 880       }
 881     }
 882
 883     // if (left instanceof ArrayAccessNode) {
 884     // ArrayAccessNode aan = (ArrayAccessNode) left;
 885     // left = aan.getExpression();
 886     // }
 887     // fanNodeSet
 888     base =
 889         analyzeFlowExpressionNode(md, nametable, left, nodeSet, base, implicitFlowTupleSet, false);
 890
 891     if (!left.getType().isPrimitive()) {
 892
 893       if (fd.getSymbol().equals("length")) {
 894         // TODO
 895         // array.length access, return the location of the array
 896         // return loc;
 897       }
 898
 899       base.add(fd);
 900     }
 901
 902     return base;
 903
 904   }
 905
 906   private void analyzeFlowAssignmentNode(MethodDescriptor md, SymbolTable nametable,
 907       AssignmentNode an, NTuple<Descriptor> base, NodeTupleSet implicitFlowTupleSet) {
 908
 909     System.out.println("analyzeFlowAssignmentNode=" + an);
 910
 911     NodeTupleSet nodeSetRHS = new NodeTupleSet();
 912     NodeTupleSet nodeSetLHS = new NodeTupleSet();
 913
 914     boolean postinc = true;
 915     if (an.getOperation().getBaseOp() == null
 916         || (an.getOperation().getBaseOp().getOp() != Operation.POSTINC && an.getOperation()
 917             .getBaseOp().getOp() != Operation.POSTDEC)) {
 918       postinc = false;
 919     }
 920
 921     // if LHS is array access node, need to capture value flows between an array
 922     // and its index value
 923     analyzeFlowExpressionNode(md, nametable, an.getDest(), nodeSetLHS, null, implicitFlowTupleSet,
 924         true);
 925     System.out.println("ASSIGNMENT NODE nodeSetLHS=" + nodeSetLHS);
 926
 927     if (!postinc) {
 928       // analyze value flows of rhs expression
 929       analyzeFlowExpressionNode(md, nametable, an.getSrc(), nodeSetRHS, null, implicitFlowTupleSet,
 930           false);
 931       System.out.println("ASSIGNMENT NODE nodeSetRHS=" + nodeSetRHS);
 932
 933       // creates edges from RHS to LHS
 934       for (Iterator<NTuple<Descriptor>> iter = nodeSetRHS.iterator(); iter.hasNext();) {
 935         NTuple<Descriptor> fromTuple = iter.next();
 936         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
 937           NTuple<Descriptor> toTuple = iter2.next();
 938           addFlowGraphEdge(md, fromTuple, toTuple);
 939         }
 940       }
 941
 942       // creates edges from implicitFlowTupleSet to LHS
 943       for (Iterator<NTuple<Descriptor>> iter = implicitFlowTupleSet.iterator(); iter.hasNext();) {
 944         NTuple<Descriptor> fromTuple = iter.next();
 945         for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
 946           NTuple<Descriptor> toTuple = iter2.next();
 947           addFlowGraphEdge(md, fromTuple, toTuple);
 948         }
 949       }
 950
 951     } else {
 952       // postinc case
 953       for (Iterator<NTuple<Descriptor>> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) {
 954         NTuple<Descriptor> tuple = iter2.next();
 955         addFlowGraphEdge(md, tuple, tuple);
 956       }
 957
 958     }
 959
 960   }
 961
 962   public FlowGraph getFlowGraph(MethodDescriptor md) {
 963     return mapMethodDescriptorToFlowGraph.get(md);
 964   }
 965
 966   public void addFlowGraphEdge(MethodDescriptor md, NTuple<Descriptor> from, NTuple<Descriptor> to) {
 967     FlowGraph graph = getFlowGraph(md);
 968     graph.addValueFlowEdge(from, to);
 969   }
 970
 971   public void _debug_printGraph() {
 972     Set<MethodDescriptor> keySet = mapMethodDescriptorToFlowGraph.keySet();
 973
 974     for (Iterator<MethodDescriptor> iterator = keySet.iterator(); iterator.hasNext();) {
 975       MethodDescriptor md = (MethodDescriptor) iterator.next();
 976       FlowGraph fg = mapMethodDescriptorToFlowGraph.get(md);
 977       try {
 978         fg.writeGraph();
 979       } catch (IOException e) {
 980         e.printStackTrace();
 981       }
 982     }
 983
 984   }
 985
 986 }