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/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
  20 #include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h"
  21 #include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h"
  22 #include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h"
  23 #include "llvm/ADT/OwningPtr.h"
  24
  25 namespace clang {
  26
  27 namespace ento {
  28
  29 //===----------------------------------------------------------------------===//
  30 /// CoreEngine - Implements the core logic of the graph-reachability
  31 ///   analysis. It traverses the CFG and generates the ExplodedGraph.
  32 ///   Program "states" are treated as opaque void pointers.
  33 ///   The template class CoreEngine (which subclasses CoreEngine)
  34 ///   provides the matching component to the engine that knows the actual types
  35 ///   for states.  Note that this engine only dispatches to transfer functions
  36 ///   at the statement and block-level.  The analyses themselves must implement
  37 ///   any transfer function logic and the sub-expression level (if any).
  38 class CoreEngine {
  39   friend class StmtNodeBuilder;
  40   friend class GenericNodeBuilderImpl;
  41   friend class BranchNodeBuilder;
  42   friend class IndirectGotoNodeBuilder;
  43   friend class SwitchNodeBuilder;
  44   friend class EndOfFunctionNodeBuilder;
  45   friend class CallEnterNodeBuilder;
  46   friend class CallExitNodeBuilder;
  47
  48 public:
  49   typedef std::vector<std::pair<BlockEdge, const ExplodedNode*> >
  50             BlocksExhausted;
  51
  52   typedef std::vector<std::pair<const CFGBlock*, const ExplodedNode*> >
  53             BlocksAborted;
  54
  55 private:
  56
  57   SubEngine& SubEng;
  58
  59   /// G - The simulation graph.  Each node is a (location,state) pair.
  60   llvm::OwningPtr<ExplodedGraph> G;
  61
  62   /// WList - A set of queued nodes that need to be processed by the
  63   ///  worklist algorithm.  It is up to the implementation of WList to decide
  64   ///  the order that nodes are processed.
  65   WorkList* WList;
  66
  67   /// BCounterFactory - A factory object for created BlockCounter objects.
  68   ///   These are used to record for key nodes in the ExplodedGraph the
  69   ///   number of times different CFGBlocks have been visited along a path.
  70   BlockCounter::Factory BCounterFactory;
  71
  72   /// The locations where we stopped doing work because we visited a location
  73   ///  too many times.
  74   BlocksExhausted blocksExhausted;
  75
  76   /// The locations where we stopped because the engine aborted analysis,
  77   /// usually because it could not reason about something.
  78   BlocksAborted blocksAborted;
  79
  80   void generateNode(const ProgramPoint& Loc, const GRState* State,
  81                     ExplodedNode* Pred);
  82
  83   void HandleBlockEdge(const BlockEdge& E, ExplodedNode* Pred);
  84   void HandleBlockEntrance(const BlockEntrance& E, ExplodedNode* Pred);
  85   void HandleBlockExit(const CFGBlock* B, ExplodedNode* Pred);
  86   void HandlePostStmt(const CFGBlock* B, unsigned StmtIdx, ExplodedNode *Pred);
  87
  88   void HandleBranch(const Stmt* Cond, const Stmt* Term, const CFGBlock* B,
  89                     ExplodedNode* Pred);
  90   void HandleCallEnter(const CallEnter &L, const CFGBlock *Block,
  91                        unsigned Index, ExplodedNode *Pred);
  92   void HandleCallExit(const CallExit &L, ExplodedNode *Pred);
  93
  94 private:
  95   CoreEngine(const CoreEngine&); // Do not implement.
  96   CoreEngine& operator=(const CoreEngine&);
  97
  98 public:
  99   /// Construct a CoreEngine object to analyze the provided CFG using
 100   ///  a DFS exploration of the exploded graph.
 101   CoreEngine(SubEngine& subengine)
 102     : SubEng(subengine), G(new ExplodedGraph()),
 103       WList(WorkList::makeBFS()),
 104       BCounterFactory(G->getAllocator()) {}
 105
 106   /// Construct a CoreEngine object to analyze the provided CFG and to
 107   ///  use the provided worklist object to execute the worklist algorithm.
 108   ///  The CoreEngine object assumes ownership of 'wlist'.
 109   CoreEngine(WorkList* wlist, SubEngine& subengine)
 110     : SubEng(subengine), G(new ExplodedGraph()), WList(wlist),
 111       BCounterFactory(G->getAllocator()) {}
 112
 113   ~CoreEngine() {
 114     delete WList;
 115   }
 116
 117   /// getGraph - Returns the exploded graph.
 118   ExplodedGraph& getGraph() { return *G.get(); }
 119
 120   /// takeGraph - Returns the exploded graph.  Ownership of the graph is
 121   ///  transferred to the caller.
 122   ExplodedGraph* takeGraph() { return G.take(); }
 123
 124   /// ExecuteWorkList - Run the worklist algorithm for a maximum number of
 125   ///  steps.  Returns true if there is still simulation state on the worklist.
 126   bool ExecuteWorkList(const LocationContext *L, unsigned Steps,
 127                        const GRState *InitState);
 128   void ExecuteWorkListWithInitialState(const LocationContext *L, unsigned Steps,
 129                                        const GRState *InitState,
 130                                        ExplodedNodeSet &Dst);
 131
 132   // Functions for external checking of whether we have unfinished work
 133   bool wasBlockAborted() const { return !blocksAborted.empty(); }
 134   bool wasBlocksExhausted() const { return !blocksExhausted.empty(); }
 135   bool hasWorkRemaining() const { return wasBlocksExhausted() ||
 136                                          WList->hasWork() ||
 137                                          wasBlockAborted(); }
 138
 139   /// Inform the CoreEngine that a basic block was aborted because
 140   /// it could not be completely analyzed.
 141   void addAbortedBlock(const ExplodedNode *node, const CFGBlock *block) {
 142     blocksAborted.push_back(std::make_pair(block, node));
 143   }
 144
 145   WorkList *getWorkList() const { return WList; }
 146
 147   BlocksExhausted::const_iterator blocks_exhausted_begin() const {
 148     return blocksExhausted.begin();
 149   }
 150   BlocksExhausted::const_iterator blocks_exhausted_end() const {
 151     return blocksExhausted.end();
 152   }
 153   BlocksAborted::const_iterator blocks_aborted_begin() const {
 154     return blocksAborted.begin();
 155   }
 156   BlocksAborted::const_iterator blocks_aborted_end() const {
 157     return blocksAborted.end();
 158   }
 159 };
 160
 161 class StmtNodeBuilder {
 162   CoreEngine& Eng;
 163   const CFGBlock& B;
 164   const unsigned Idx;
 165   ExplodedNode* Pred;
 166   GRStateManager& Mgr;
 167
 168 public:
 169   bool PurgingDeadSymbols;
 170   bool BuildSinks;
 171   bool hasGeneratedNode;
 172   ProgramPoint::Kind PointKind;
 173   const void *Tag;
 174
 175   const GRState* CleanedState;
 176
 177
 178   typedef llvm::SmallPtrSet<ExplodedNode*,5> DeferredTy;
 179   DeferredTy Deferred;
 180
 181   void GenerateAutoTransition(ExplodedNode* N);
 182
 183 public:
 184   StmtNodeBuilder(const CFGBlock* b, unsigned idx, ExplodedNode* N,
 185                     CoreEngine* e, GRStateManager &mgr);
 186
 187   ~StmtNodeBuilder();
 188
 189   ExplodedNode* getPredecessor() const { return Pred; }
 190
 191   // FIXME: This should not be exposed.
 192   WorkList *getWorkList() { return Eng.WList; }
 193
 194   void SetCleanedState(const GRState* St) {
 195     CleanedState = St;
 196   }
 197
 198   BlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter();}
 199
 200   unsigned getCurrentBlockCount() const {
 201     return getBlockCounter().getNumVisited(
 202                             Pred->getLocationContext()->getCurrentStackFrame(),
 203                                            B.getBlockID());
 204   }
 205
 206   ExplodedNode* generateNode(PostStmt PP,const GRState* St,ExplodedNode* Pred) {
 207     hasGeneratedNode = true;
 208     return generateNodeInternal(PP, St, Pred);
 209   }
 210
 211   ExplodedNode* generateNode(const Stmt *S, const GRState *St,
 212                              ExplodedNode *Pred, ProgramPoint::Kind K,
 213                              const void *tag = 0) {
 214     hasGeneratedNode = true;
 215
 216     if (PurgingDeadSymbols)
 217       K = ProgramPoint::PostPurgeDeadSymbolsKind;
 218
 219     return generateNodeInternal(S, St, Pred, K, tag ? tag : Tag);
 220   }
 221
 222   ExplodedNode* generateNode(const Stmt *S, const GRState *St,
 223                              ExplodedNode *Pred, const void *tag = 0) {
 224     return generateNode(S, St, Pred, PointKind, tag);
 225   }
 226
 227   ExplodedNode *generateNode(const ProgramPoint &PP, const GRState* State,
 228                              ExplodedNode* Pred) {
 229     hasGeneratedNode = true;
 230     return generateNodeInternal(PP, State, Pred);
 231   }
 232
 233   ExplodedNode*
 234   generateNodeInternal(const ProgramPoint &PP, const GRState* State,
 235                        ExplodedNode* Pred);
 236
 237   ExplodedNode*
 238   generateNodeInternal(const Stmt* S, const GRState* State, ExplodedNode* Pred,
 239                    ProgramPoint::Kind K = ProgramPoint::PostStmtKind,
 240                    const void *tag = 0);
 241
 242   /// getStmt - Return the current block-level expression associated with
 243   ///  this builder.
 244   const Stmt* getStmt() const {
 245     const CFGStmt *CS = B[Idx].getAs<CFGStmt>();
 246     return CS ? CS->getStmt() : 0;
 247   }
 248
 249   /// getBlock - Return the CFGBlock associated with the block-level expression
 250   ///  of this builder.
 251   const CFGBlock* getBlock() const { return &B; }
 252
 253   unsigned getIndex() const { return Idx; }
 254
 255   const GRState* GetState(ExplodedNode* Pred) const {
 256     if (Pred == getPredecessor())
 257       return CleanedState;
 258     else
 259       return Pred->getState();
 260   }
 261
 262   ExplodedNode* MakeNode(ExplodedNodeSet& Dst, const Stmt* S,
 263                          ExplodedNode* Pred, const GRState* St) {
 264     return MakeNode(Dst, S, Pred, St, PointKind);
 265   }
 266
 267   ExplodedNode* MakeNode(ExplodedNodeSet& Dst, const Stmt* S,ExplodedNode* Pred,
 268                          const GRState* St, ProgramPoint::Kind K);
 269
 270   ExplodedNode* MakeSinkNode(ExplodedNodeSet& Dst, const Stmt* S,
 271                        ExplodedNode* Pred, const GRState* St) {
 272     bool Tmp = BuildSinks;
 273     BuildSinks = true;
 274     ExplodedNode* N = MakeNode(Dst, S, Pred, St);
 275     BuildSinks = Tmp;
 276     return N;
 277   }
 278 };
 279
 280 class BranchNodeBuilder {
 281   CoreEngine& Eng;
 282   const CFGBlock* Src;
 283   const CFGBlock* DstT;
 284   const CFGBlock* DstF;
 285   ExplodedNode* Pred;
 286
 287   typedef llvm::SmallVector<ExplodedNode*,3> DeferredTy;
 288   DeferredTy Deferred;
 289
 290   bool GeneratedTrue;
 291   bool GeneratedFalse;
 292   bool InFeasibleTrue;
 293   bool InFeasibleFalse;
 294
 295 public:
 296   BranchNodeBuilder(const CFGBlock* src, const CFGBlock* dstT,
 297                       const CFGBlock* dstF, ExplodedNode* pred, CoreEngine* e)
 298   : Eng(*e), Src(src), DstT(dstT), DstF(dstF), Pred(pred),
 299     GeneratedTrue(false), GeneratedFalse(false),
 300     InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {}
 301
 302   ~BranchNodeBuilder();
 303
 304   ExplodedNode* getPredecessor() const { return Pred; }
 305
 306   const ExplodedGraph& getGraph() const { return *Eng.G; }
 307
 308   BlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter();}
 309
 310   ExplodedNode* generateNode(const Stmt *Condition, const GRState* State);
 311
 312   ExplodedNode* generateNode(const GRState* State, bool branch);
 313
 314   const CFGBlock* getTargetBlock(bool branch) const {
 315     return branch ? DstT : DstF;
 316   }
 317
 318   void markInfeasible(bool branch) {
 319     if (branch)
 320       InFeasibleTrue = GeneratedTrue = true;
 321     else
 322       InFeasibleFalse = GeneratedFalse = true;
 323   }
 324
 325   bool isFeasible(bool branch) {
 326     return branch ? !InFeasibleTrue : !InFeasibleFalse;
 327   }
 328
 329   const GRState* getState() const {
 330     return getPredecessor()->getState();
 331   }
 332 };
 333
 334 class IndirectGotoNodeBuilder {
 335   CoreEngine& Eng;
 336   const CFGBlock* Src;
 337   const CFGBlock& DispatchBlock;
 338   const Expr* E;
 339   ExplodedNode* Pred;
 340
 341 public:
 342   IndirectGotoNodeBuilder(ExplodedNode* pred, const CFGBlock* src,
 343                     const Expr* e, const CFGBlock* dispatch, CoreEngine* eng)
 344     : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {}
 345
 346   class iterator {
 347     CFGBlock::const_succ_iterator I;
 348
 349     friend class IndirectGotoNodeBuilder;
 350     iterator(CFGBlock::const_succ_iterator i) : I(i) {}
 351   public:
 352
 353     iterator& operator++() { ++I; return *this; }
 354     bool operator!=(const iterator& X) const { return I != X.I; }
 355
 356     const LabelDecl *getLabel() const {
 357       return llvm::cast<LabelStmt>((*I)->getLabel())->getDecl();
 358     }
 359
 360     const CFGBlock *getBlock() const {
 361       return *I;
 362     }
 363   };
 364
 365   iterator begin() { return iterator(DispatchBlock.succ_begin()); }
 366   iterator end() { return iterator(DispatchBlock.succ_end()); }
 367
 368   ExplodedNode* generateNode(const iterator& I, const GRState* State,
 369                              bool isSink = false);
 370
 371   const Expr* getTarget() const { return E; }
 372
 373   const GRState* getState() const { return Pred->State; }
 374 };
 375
 376 class SwitchNodeBuilder {
 377   CoreEngine& Eng;
 378   const CFGBlock* Src;
 379   const Expr* Condition;
 380   ExplodedNode* Pred;
 381
 382 public:
 383   SwitchNodeBuilder(ExplodedNode* pred, const CFGBlock* src,
 384                       const Expr* condition, CoreEngine* eng)
 385   : Eng(*eng), Src(src), Condition(condition), Pred(pred) {}
 386
 387   class iterator {
 388     CFGBlock::const_succ_reverse_iterator I;
 389
 390     friend class SwitchNodeBuilder;
 391     iterator(CFGBlock::const_succ_reverse_iterator i) : I(i) {}
 392
 393   public:
 394     iterator& operator++() { ++I; return *this; }
 395     bool operator!=(const iterator &X) const { return I != X.I; }
 396     bool operator==(const iterator &X) const { return I == X.I; }
 397
 398     const CaseStmt* getCase() const {
 399       return llvm::cast<CaseStmt>((*I)->getLabel());
 400     }
 401
 402     const CFGBlock* getBlock() const {
 403       return *I;
 404     }
 405   };
 406
 407   iterator begin() { return iterator(Src->succ_rbegin()+1); }
 408   iterator end() { return iterator(Src->succ_rend()); }
 409
 410   const SwitchStmt *getSwitch() const {
 411     return llvm::cast<SwitchStmt>(Src->getTerminator());
 412   }
 413
 414   ExplodedNode* generateCaseStmtNode(const iterator& I, const GRState* State);
 415
 416   ExplodedNode* generateDefaultCaseNode(const GRState* State,
 417                                         bool isSink = false);
 418
 419   const Expr* getCondition() const { return Condition; }
 420
 421   const GRState* getState() const { return Pred->State; }
 422 };
 423
 424 class GenericNodeBuilderImpl {
 425 protected:
 426   CoreEngine &engine;
 427   ExplodedNode *pred;
 428   ProgramPoint pp;
 429   llvm::SmallVector<ExplodedNode*, 2> sinksGenerated;
 430
 431   ExplodedNode *generateNodeImpl(const GRState *state, ExplodedNode *pred,
 432                                  ProgramPoint programPoint, bool asSink);
 433
 434   GenericNodeBuilderImpl(CoreEngine &eng, ExplodedNode *pr, ProgramPoint p)
 435     : engine(eng), pred(pr), pp(p), hasGeneratedNode(false) {}
 436
 437 public:
 438   bool hasGeneratedNode;
 439
 440   WorkList &getWorkList() { return *engine.WList; }
 441
 442   ExplodedNode* getPredecessor() const { return pred; }
 443
 444   BlockCounter getBlockCounter() const {
 445     return engine.WList->getBlockCounter();
 446   }
 447
 448   const llvm::SmallVectorImpl<ExplodedNode*> &sinks() const {
 449     return sinksGenerated;
 450   }
 451 };
 452
 453 template <typename PP_T>
 454 class GenericNodeBuilder : public GenericNodeBuilderImpl {
 455 public:
 456   GenericNodeBuilder(CoreEngine &eng, ExplodedNode *pr, const PP_T &p)
 457     : GenericNodeBuilderImpl(eng, pr, p) {}
 458
 459   ExplodedNode *generateNode(const GRState *state, ExplodedNode *pred,
 460                              const void *tag, bool asSink) {
 461     return generateNodeImpl(state, pred, cast<PP_T>(pp).withTag(tag),
 462                             asSink);
 463   }
 464
 465   const PP_T &getProgramPoint() const { return cast<PP_T>(pp); }
 466 };
 467
 468 class EndOfFunctionNodeBuilder {
 469   CoreEngine &Eng;
 470   const CFGBlock& B;
 471   ExplodedNode* Pred;
 472   void *Tag;
 473
 474 public:
 475   bool hasGeneratedNode;
 476
 477 public:
 478   EndOfFunctionNodeBuilder(const CFGBlock* b, ExplodedNode* N, CoreEngine* e,
 479                            void *checkerTag = 0)
 480     : Eng(*e), B(*b), Pred(N), Tag(checkerTag), hasGeneratedNode(false) {}
 481
 482   ~EndOfFunctionNodeBuilder();
 483
 484   EndOfFunctionNodeBuilder withCheckerTag(void *tag) {
 485     return EndOfFunctionNodeBuilder(&B, Pred, &Eng, tag);
 486   }
 487
 488   WorkList &getWorkList() { return *Eng.WList; }
 489
 490   ExplodedNode* getPredecessor() const { return Pred; }
 491
 492   BlockCounter getBlockCounter() const {
 493     return Eng.WList->getBlockCounter();
 494   }
 495
 496   unsigned getCurrentBlockCount() const {
 497     return getBlockCounter().getNumVisited(
 498                             Pred->getLocationContext()->getCurrentStackFrame(),
 499                                            B.getBlockID());
 500   }
 501
 502   ExplodedNode* generateNode(const GRState* State, ExplodedNode *P = 0,
 503                              const void *tag = 0);
 504
 505   void GenerateCallExitNode(const GRState *state);
 506
 507   const CFGBlock* getBlock() const { return &B; }
 508
 509   const GRState* getState() const {
 510     return getPredecessor()->getState();
 511   }
 512 };
 513
 514 class CallEnterNodeBuilder {
 515   CoreEngine &Eng;
 516
 517   const ExplodedNode *Pred;
 518
 519   // The call site. For implicit automatic object dtor, this is the trigger
 520   // statement.
 521   const Stmt *CE;
 522
 523   // The context of the callee.
 524   const StackFrameContext *CalleeCtx;
 525
 526   // The parent block of the CallExpr.
 527   const CFGBlock *Block;
 528
 529   // The CFGBlock index of the CallExpr.
 530   unsigned Index;
 531
 532 public:
 533   CallEnterNodeBuilder(CoreEngine &eng, const ExplodedNode *pred,
 534                          const Stmt *s, const StackFrameContext *callee,
 535                          const CFGBlock *blk, unsigned idx)
 536     : Eng(eng), Pred(pred), CE(s), CalleeCtx(callee), Block(blk), Index(idx) {}
 537
 538   const GRState *getState() const { return Pred->getState(); }
 539
 540   const LocationContext *getLocationContext() const {
 541     return Pred->getLocationContext();
 542   }
 543
 544   const Stmt *getCallExpr() const { return CE; }
 545
 546   const StackFrameContext *getCalleeContext() const { return CalleeCtx; }
 547
 548   const CFGBlock *getBlock() const { return Block; }
 549
 550   unsigned getIndex() const { return Index; }
 551
 552   void generateNode(const GRState *state);
 553 };
 554
 555 class CallExitNodeBuilder {
 556   CoreEngine &Eng;
 557   const ExplodedNode *Pred;
 558
 559 public:
 560   CallExitNodeBuilder(CoreEngine &eng, const ExplodedNode *pred)
 561     : Eng(eng), Pred(pred) {}
 562
 563   const ExplodedNode *getPredecessor() const { return Pred; }
 564
 565   const GRState *getState() const { return Pred->getState(); }
 566
 567   void generateNode(const GRState *state);
 568 };
 569
 570 } // end GR namespace
 571
 572 } // end clang namespace
 573
 574 #endif