contrib/llvm/tools/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h

   1 //==- CoreEngine.h - Path-Sensitive Dataflow Engine ----------------*- C++ -*-//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //  This file defines a generic engine for intraprocedural, path-sensitive,
  11 //  dataflow analysis via graph reachability.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_CLANG_GR_COREENGINE
  16 #define LLVM_CLANG_GR_COREENGINE
  17
  18 #include "clang/AST/Expr.h"
  19 #include "clang/Analysis/AnalysisContext.h"
  20 #include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h"
  21 #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
  22 #include "clang/StaticAnalyzer/Core/PathSensitive/FunctionSummary.h"
  23 #include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h"
  24 #include "llvm/ADT/OwningPtr.h"
  25
  26 namespace clang {
  27
  28 class ProgramPointTag;
  29
  30 namespace ento {
  31
  32 class NodeBuilder;
  33
  34 //===----------------------------------------------------------------------===//
  35 /// CoreEngine - Implements the core logic of the graph-reachability
  36 ///   analysis. It traverses the CFG and generates the ExplodedGraph.
  37 ///   Program "states" are treated as opaque void pointers.
  38 ///   The template class CoreEngine (which subclasses CoreEngine)
  39 ///   provides the matching component to the engine that knows the actual types
  40 ///   for states.  Note that this engine only dispatches to transfer functions
  41 ///   at the statement and block-level.  The analyses themselves must implement
  42 ///   any transfer function logic and the sub-expression level (if any).
  43 class CoreEngine {
  44   friend struct NodeBuilderContext;
  45   friend class NodeBuilder;
  46   friend class ExprEngine;
  47   friend class CommonNodeBuilder;
  48   friend class IndirectGotoNodeBuilder;
  49   friend class SwitchNodeBuilder;
  50   friend class EndOfFunctionNodeBuilder;
  51 public:
  52   typedef std::vector<std::pair<BlockEdge, const ExplodedNode*> >
  53             BlocksExhausted;
  54
  55   typedef std::vector<std::pair<const CFGBlock*, const ExplodedNode*> >
  56             BlocksAborted;
  57
  58 private:
  59
  60   SubEngine& SubEng;
  61
  62   /// G - The simulation graph.  Each node is a (location,state) pair.
  63   OwningPtr<ExplodedGraph> G;
  64
  65   /// WList - A set of queued nodes that need to be processed by the
  66   ///  worklist algorithm.  It is up to the implementation of WList to decide
  67   ///  the order that nodes are processed.
  68   OwningPtr<WorkList> WList;
  69
  70   /// BCounterFactory - A factory object for created BlockCounter objects.
  71   ///   These are used to record for key nodes in the ExplodedGraph the
  72   ///   number of times different CFGBlocks have been visited along a path.
  73   BlockCounter::Factory BCounterFactory;
  74
  75   /// The locations where we stopped doing work because we visited a location
  76   ///  too many times.
  77   BlocksExhausted blocksExhausted;
  78
  79   /// The locations where we stopped because the engine aborted analysis,
  80   /// usually because it could not reason about something.
  81   BlocksAborted blocksAborted;
  82
  83   /// The information about functions shared by the whole translation unit.
  84   /// (This data is owned by AnalysisConsumer.)
  85   FunctionSummariesTy *FunctionSummaries;
  86
  87   void generateNode(const ProgramPoint &Loc,
  88                     ProgramStateRef State,
  89                     ExplodedNode *Pred);
  90
  91   void HandleBlockEdge(const BlockEdge &E, ExplodedNode *Pred);
  92   void HandleBlockEntrance(const BlockEntrance &E, ExplodedNode *Pred);
  93   void HandleBlockExit(const CFGBlock *B, ExplodedNode *Pred);
  94   void HandlePostStmt(const CFGBlock *B, unsigned StmtIdx, ExplodedNode *Pred);
  95
  96   void HandleBranch(const Stmt *Cond, const Stmt *Term, const CFGBlock *B,
  97                     ExplodedNode *Pred);
  98
  99   /// Handle conditional logic for running static initializers.
 100   void HandleStaticInit(const DeclStmt *DS, const CFGBlock *B,
 101                         ExplodedNode *Pred);
 102
 103 private:
 104   CoreEngine(const CoreEngine &) LLVM_DELETED_FUNCTION;
 105   void operator=(const CoreEngine &) LLVM_DELETED_FUNCTION;
 106
 107   ExplodedNode *generateCallExitBeginNode(ExplodedNode *N);
 108
 109 public:
 110   /// Construct a CoreEngine object to analyze the provided CFG.
 111   CoreEngine(SubEngine& subengine,
 112              FunctionSummariesTy *FS)
 113     : SubEng(subengine), G(new ExplodedGraph()),
 114       WList(WorkList::makeDFS()),
 115       BCounterFactory(G->getAllocator()),
 116       FunctionSummaries(FS){}
 117
 118   /// getGraph - Returns the exploded graph.
 119   ExplodedGraph& getGraph() { return *G.get(); }
 120
 121   /// takeGraph - Returns the exploded graph.  Ownership of the graph is
 122   ///  transferred to the caller.
 123   ExplodedGraph* takeGraph() { return G.take(); }
 124
 125   /// ExecuteWorkList - Run the worklist algorithm for a maximum number of
 126   ///  steps.  Returns true if there is still simulation state on the worklist.
 127   bool ExecuteWorkList(const LocationContext *L, unsigned Steps,
 128                        ProgramStateRef InitState);
 129   /// Returns true if there is still simulation state on the worklist.
 130   bool ExecuteWorkListWithInitialState(const LocationContext *L,
 131                                        unsigned Steps,
 132                                        ProgramStateRef InitState,
 133                                        ExplodedNodeSet &Dst);
 134
 135   /// Dispatch the work list item based on the given location information.
 136   /// Use Pred parameter as the predecessor state.
 137   void dispatchWorkItem(ExplodedNode* Pred, ProgramPoint Loc,
 138                         const WorkListUnit& WU);
 139
 140   // Functions for external checking of whether we have unfinished work
 141   bool wasBlockAborted() const { return !blocksAborted.empty(); }
 142   bool wasBlocksExhausted() const { return !blocksExhausted.empty(); }
 143   bool hasWorkRemaining() const { return wasBlocksExhausted() ||
 144                                          WList->hasWork() ||
 145                                          wasBlockAborted(); }
 146
 147   /// Inform the CoreEngine that a basic block was aborted because
 148   /// it could not be completely analyzed.
 149   void addAbortedBlock(const ExplodedNode *node, const CFGBlock *block) {
 150     blocksAborted.push_back(std::make_pair(block, node));
 151   }
 152
 153   WorkList *getWorkList() const { return WList.get(); }
 154
 155   BlocksExhausted::const_iterator blocks_exhausted_begin() const {
 156     return blocksExhausted.begin();
 157   }
 158   BlocksExhausted::const_iterator blocks_exhausted_end() const {
 159     return blocksExhausted.end();
 160   }
 161   BlocksAborted::const_iterator blocks_aborted_begin() const {
 162     return blocksAborted.begin();
 163   }
 164   BlocksAborted::const_iterator blocks_aborted_end() const {
 165     return blocksAborted.end();
 166   }
 167
 168   /// \brief Enqueue the given set of nodes onto the work list.
 169   void enqueue(ExplodedNodeSet &Set);
 170
 171   /// \brief Enqueue nodes that were created as a result of processing
 172   /// a statement onto the work list.
 173   void enqueue(ExplodedNodeSet &Set, const CFGBlock *Block, unsigned Idx);
 174
 175   /// \brief enqueue the nodes corresponding to the end of function onto the
 176   /// end of path / work list.
 177   void enqueueEndOfFunction(ExplodedNodeSet &Set);
 178
 179   /// \brief Enqueue a single node created as a result of statement processing.
 180   void enqueueStmtNode(ExplodedNode *N, const CFGBlock *Block, unsigned Idx);
 181 };
 182
 183 // TODO: Turn into a calss.
 184 struct NodeBuilderContext {
 185   const CoreEngine &Eng;
 186   const CFGBlock *Block;
 187   const LocationContext *LC;
 188   NodeBuilderContext(const CoreEngine &E, const CFGBlock *B, ExplodedNode *N)
 189     : Eng(E), Block(B), LC(N->getLocationContext()) { assert(B); }
 190
 191   /// \brief Return the CFGBlock associated with this builder.
 192   const CFGBlock *getBlock() const { return Block; }
 193
 194   /// \brief Returns the number of times the current basic block has been
 195   /// visited on the exploded graph path.
 196   unsigned blockCount() const {
 197     return Eng.WList->getBlockCounter().getNumVisited(
 198                     LC->getCurrentStackFrame(),
 199                     Block->getBlockID());
 200   }
 201 };
 202
 203 /// \class NodeBuilder
 204 /// \brief This is the simplest builder which generates nodes in the
 205 /// ExplodedGraph.
 206 ///
 207 /// The main benefit of the builder is that it automatically tracks the
 208 /// frontier nodes (or destination set). This is the set of nodes which should
 209 /// be propagated to the next step / builder. They are the nodes which have been
 210 /// added to the builder (either as the input node set or as the newly
 211 /// constructed nodes) but did not have any outgoing transitions added.
 212 class NodeBuilder {
 213   virtual void anchor();
 214 protected:
 215   const NodeBuilderContext &C;
 216
 217   /// Specifies if the builder results have been finalized. For example, if it
 218   /// is set to false, autotransitions are yet to be generated.
 219   bool Finalized;
 220   bool HasGeneratedNodes;
 221   /// \brief The frontier set - a set of nodes which need to be propagated after
 222   /// the builder dies.
 223   ExplodedNodeSet &Frontier;
 224
 225   /// Checkes if the results are ready.
 226   virtual bool checkResults() {
 227     if (!Finalized)
 228       return false;
 229     return true;
 230   }
 231
 232   bool hasNoSinksInFrontier() {
 233     for (iterator I = Frontier.begin(), E = Frontier.end(); I != E; ++I) {
 234       if ((*I)->isSink())
 235         return false;
 236     }
 237     return true;
 238   }
 239
 240   /// Allow subclasses to finalize results before result_begin() is executed.
 241   virtual void finalizeResults() {}
 242
 243   ExplodedNode *generateNodeImpl(const ProgramPoint &PP,
 244                                  ProgramStateRef State,
 245                                  ExplodedNode *Pred,
 246                                  bool MarkAsSink = false);
 247
 248 public:
 249   NodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet,
 250               const NodeBuilderContext &Ctx, bool F = true)
 251     : C(Ctx), Finalized(F), HasGeneratedNodes(false), Frontier(DstSet) {
 252     Frontier.Add(SrcNode);
 253   }
 254
 255   NodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet,
 256               const NodeBuilderContext &Ctx, bool F = true)
 257     : C(Ctx), Finalized(F), HasGeneratedNodes(false), Frontier(DstSet) {
 258     Frontier.insert(SrcSet);
 259     assert(hasNoSinksInFrontier());
 260   }
 261
 262   virtual ~NodeBuilder() {}
 263
 264   /// \brief Generates a node in the ExplodedGraph.
 265   ExplodedNode *generateNode(const ProgramPoint &PP,
 266                              ProgramStateRef State,
 267                              ExplodedNode *Pred) {
 268     return generateNodeImpl(PP, State, Pred, false);
 269   }
 270
 271   /// \brief Generates a sink in the ExplodedGraph.
 272   ///
 273   /// When a node is marked as sink, the exploration from the node is stopped -
 274   /// the node becomes the last node on the path and certain kinds of bugs are
 275   /// suppressed.
 276   ExplodedNode *generateSink(const ProgramPoint &PP,
 277                              ProgramStateRef State,
 278                              ExplodedNode *Pred) {
 279     return generateNodeImpl(PP, State, Pred, true);
 280   }
 281
 282   const ExplodedNodeSet &getResults() {
 283     finalizeResults();
 284     assert(checkResults());
 285     return Frontier;
 286   }
 287
 288   typedef ExplodedNodeSet::iterator iterator;
 289   /// \brief Iterators through the results frontier.
 290   inline iterator begin() {
 291     finalizeResults();
 292     assert(checkResults());
 293     return Frontier.begin();
 294   }
 295   inline iterator end() {
 296     finalizeResults();
 297     return Frontier.end();
 298   }
 299
 300   const NodeBuilderContext &getContext() { return C; }
 301   bool hasGeneratedNodes() { return HasGeneratedNodes; }
 302
 303   void takeNodes(const ExplodedNodeSet &S) {
 304     for (ExplodedNodeSet::iterator I = S.begin(), E = S.end(); I != E; ++I )
 305       Frontier.erase(*I);
 306   }
 307   void takeNodes(ExplodedNode *N) { Frontier.erase(N); }
 308   void addNodes(const ExplodedNodeSet &S) { Frontier.insert(S); }
 309   void addNodes(ExplodedNode *N) { Frontier.Add(N); }
 310 };
 311
 312 /// \class NodeBuilderWithSinks
 313 /// \brief This node builder keeps track of the generated sink nodes.
 314 class NodeBuilderWithSinks: public NodeBuilder {
 315   virtual void anchor();
 316 protected:
 317   SmallVector<ExplodedNode*, 2> sinksGenerated;
 318   ProgramPoint &Location;
 319
 320 public:
 321   NodeBuilderWithSinks(ExplodedNode *Pred, ExplodedNodeSet &DstSet,
 322                        const NodeBuilderContext &Ctx, ProgramPoint &L)
 323     : NodeBuilder(Pred, DstSet, Ctx), Location(L) {}
 324
 325   ExplodedNode *generateNode(ProgramStateRef State,
 326                              ExplodedNode *Pred,
 327                              const ProgramPointTag *Tag = 0) {
 328     const ProgramPoint &LocalLoc = (Tag ? Location.withTag(Tag) : Location);
 329     return NodeBuilder::generateNode(LocalLoc, State, Pred);
 330   }
 331
 332   ExplodedNode *generateSink(ProgramStateRef State, ExplodedNode *Pred,
 333                              const ProgramPointTag *Tag = 0) {
 334     const ProgramPoint &LocalLoc = (Tag ? Location.withTag(Tag) : Location);
 335     ExplodedNode *N = NodeBuilder::generateSink(LocalLoc, State, Pred);
 336     if (N && N->isSink())
 337       sinksGenerated.push_back(N);
 338     return N;
 339   }
 340
 341   const SmallVectorImpl<ExplodedNode*> &getSinks() const {
 342     return sinksGenerated;
 343   }
 344 };
 345
 346 /// \class StmtNodeBuilder
 347 /// \brief This builder class is useful for generating nodes that resulted from
 348 /// visiting a statement. The main difference from its parent NodeBuilder is
 349 /// that it creates a statement specific ProgramPoint.
 350 class StmtNodeBuilder: public NodeBuilder {
 351   NodeBuilder *EnclosingBldr;
 352 public:
 353
 354   /// \brief Constructs a StmtNodeBuilder. If the builder is going to process
 355   /// nodes currently owned by another builder(with larger scope), use
 356   /// Enclosing builder to transfer ownership.
 357   StmtNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet,
 358                       const NodeBuilderContext &Ctx, NodeBuilder *Enclosing = 0)
 359     : NodeBuilder(SrcNode, DstSet, Ctx), EnclosingBldr(Enclosing) {
 360     if (EnclosingBldr)
 361       EnclosingBldr->takeNodes(SrcNode);
 362   }
 363
 364   StmtNodeBuilder(ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet,
 365                       const NodeBuilderContext &Ctx, NodeBuilder *Enclosing = 0)
 366     : NodeBuilder(SrcSet, DstSet, Ctx), EnclosingBldr(Enclosing) {
 367     if (EnclosingBldr)
 368       for (ExplodedNodeSet::iterator I = SrcSet.begin(),
 369                                      E = SrcSet.end(); I != E; ++I )
 370         EnclosingBldr->takeNodes(*I);
 371   }
 372
 373   virtual ~StmtNodeBuilder();
 374
 375   using NodeBuilder::generateNode;
 376   using NodeBuilder::generateSink;
 377
 378   ExplodedNode *generateNode(const Stmt *S,
 379                              ExplodedNode *Pred,
 380                              ProgramStateRef St,
 381                              const ProgramPointTag *tag = 0,
 382                              ProgramPoint::Kind K = ProgramPoint::PostStmtKind){
 383     const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K,
 384                                   Pred->getLocationContext(), tag);
 385     return NodeBuilder::generateNode(L, St, Pred);
 386   }
 387
 388   ExplodedNode *generateSink(const Stmt *S,
 389                              ExplodedNode *Pred,
 390                              ProgramStateRef St,
 391                              const ProgramPointTag *tag = 0,
 392                              ProgramPoint::Kind K = ProgramPoint::PostStmtKind){
 393     const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K,
 394                                   Pred->getLocationContext(), tag);
 395     return NodeBuilder::generateSink(L, St, Pred);
 396   }
 397 };
 398
 399 /// \brief BranchNodeBuilder is responsible for constructing the nodes
 400 /// corresponding to the two branches of the if statement - true and false.
 401 class BranchNodeBuilder: public NodeBuilder {
 402   virtual void anchor();
 403   const CFGBlock *DstT;
 404   const CFGBlock *DstF;
 405
 406   bool InFeasibleTrue;
 407   bool InFeasibleFalse;
 408
 409 public:
 410   BranchNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet,
 411                     const NodeBuilderContext &C,
 412                     const CFGBlock *dstT, const CFGBlock *dstF)
 413   : NodeBuilder(SrcNode, DstSet, C), DstT(dstT), DstF(dstF),
 414     InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {
 415     // The branch node builder does not generate autotransitions.
 416     // If there are no successors it means that both branches are infeasible.
 417     takeNodes(SrcNode);
 418   }
 419
 420   BranchNodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet,
 421                     const NodeBuilderContext &C,
 422                     const CFGBlock *dstT, const CFGBlock *dstF)
 423   : NodeBuilder(SrcSet, DstSet, C), DstT(dstT), DstF(dstF),
 424     InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {
 425     takeNodes(SrcSet);
 426   }
 427
 428   ExplodedNode *generateNode(ProgramStateRef State, bool branch,
 429                              ExplodedNode *Pred);
 430
 431   const CFGBlock *getTargetBlock(bool branch) const {
 432     return branch ? DstT : DstF;
 433   }
 434
 435   void markInfeasible(bool branch) {
 436     if (branch)
 437       InFeasibleTrue = true;
 438     else
 439       InFeasibleFalse = true;
 440   }
 441
 442   bool isFeasible(bool branch) {
 443     return branch ? !InFeasibleTrue : !InFeasibleFalse;
 444   }
 445 };
 446
 447 class IndirectGotoNodeBuilder {
 448   CoreEngine& Eng;
 449   const CFGBlock *Src;
 450   const CFGBlock &DispatchBlock;
 451   const Expr *E;
 452   ExplodedNode *Pred;
 453
 454 public:
 455   IndirectGotoNodeBuilder(ExplodedNode *pred, const CFGBlock *src,
 456                     const Expr *e, const CFGBlock *dispatch, CoreEngine* eng)
 457     : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {}
 458
 459   class iterator {
 460     CFGBlock::const_succ_iterator I;
 461
 462     friend class IndirectGotoNodeBuilder;
 463     iterator(CFGBlock::const_succ_iterator i) : I(i) {}
 464   public:
 465
 466     iterator &operator++() { ++I; return *this; }
 467     bool operator!=(const iterator &X) const { return I != X.I; }
 468
 469     const LabelDecl *getLabel() const {
 470       return cast<LabelStmt>((*I)->getLabel())->getDecl();
 471     }
 472
 473     const CFGBlock *getBlock() const {
 474       return *I;
 475     }
 476   };
 477
 478   iterator begin() { return iterator(DispatchBlock.succ_begin()); }
 479   iterator end() { return iterator(DispatchBlock.succ_end()); }
 480
 481   ExplodedNode *generateNode(const iterator &I,
 482                              ProgramStateRef State,
 483                              bool isSink = false);
 484
 485   const Expr *getTarget() const { return E; }
 486
 487   ProgramStateRef getState() const { return Pred->State; }
 488
 489   const LocationContext *getLocationContext() const {
 490     return Pred->getLocationContext();
 491   }
 492 };
 493
 494 class SwitchNodeBuilder {
 495   CoreEngine& Eng;
 496   const CFGBlock *Src;
 497   const Expr *Condition;
 498   ExplodedNode *Pred;
 499
 500 public:
 501   SwitchNodeBuilder(ExplodedNode *pred, const CFGBlock *src,
 502                     const Expr *condition, CoreEngine* eng)
 503   : Eng(*eng), Src(src), Condition(condition), Pred(pred) {}
 504
 505   class iterator {
 506     CFGBlock::const_succ_reverse_iterator I;
 507
 508     friend class SwitchNodeBuilder;
 509     iterator(CFGBlock::const_succ_reverse_iterator i) : I(i) {}
 510
 511   public:
 512     iterator &operator++() { ++I; return *this; }
 513     bool operator!=(const iterator &X) const { return I != X.I; }
 514     bool operator==(const iterator &X) const { return I == X.I; }
 515
 516     const CaseStmt *getCase() const {
 517       return cast<CaseStmt>((*I)->getLabel());
 518     }
 519
 520     const CFGBlock *getBlock() const {
 521       return *I;
 522     }
 523   };
 524
 525   iterator begin() { return iterator(Src->succ_rbegin()+1); }
 526   iterator end() { return iterator(Src->succ_rend()); }
 527
 528   const SwitchStmt *getSwitch() const {
 529     return cast<SwitchStmt>(Src->getTerminator());
 530   }
 531
 532   ExplodedNode *generateCaseStmtNode(const iterator &I,
 533                                      ProgramStateRef State);
 534
 535   ExplodedNode *generateDefaultCaseNode(ProgramStateRef State,
 536                                         bool isSink = false);
 537
 538   const Expr *getCondition() const { return Condition; }
 539
 540   ProgramStateRef getState() const { return Pred->State; }
 541
 542   const LocationContext *getLocationContext() const {
 543     return Pred->getLocationContext();
 544   }
 545 };
 546
 547 } // end ento namespace
 548 } // end clang namespace
 549
 550 #endif