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_STATICANALYZER_CORE_PATHSENSITIVE_COREENGINE_H
  16 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_COREENGINE_H
  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 <memory>
  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   mutable 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   std::unique_ptr<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   void HandleCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE,
  99                                     const CFGBlock *B, ExplodedNode *Pred);
 100
 101   /// Handle conditional logic for running static initializers.
 102   void HandleStaticInit(const DeclStmt *DS, const CFGBlock *B,
 103                         ExplodedNode *Pred);
 104
 105 private:
 106   CoreEngine(const CoreEngine &) LLVM_DELETED_FUNCTION;
 107   void operator=(const CoreEngine &) LLVM_DELETED_FUNCTION;
 108
 109   ExplodedNode *generateCallExitBeginNode(ExplodedNode *N);
 110
 111 public:
 112   /// Construct a CoreEngine object to analyze the provided CFG.
 113   CoreEngine(SubEngine &subengine, FunctionSummariesTy *FS)
 114       : SubEng(subengine), WList(WorkList::makeDFS()),
 115         BCounterFactory(G.getAllocator()), FunctionSummaries(FS) {}
 116
 117   /// getGraph - Returns the exploded graph.
 118   ExplodedGraph &getGraph() { return G; }
 119
 120   /// ExecuteWorkList - Run the worklist algorithm for a maximum number of
 121   ///  steps.  Returns true if there is still simulation state on the worklist.
 122   bool ExecuteWorkList(const LocationContext *L, unsigned Steps,
 123                        ProgramStateRef InitState);
 124   /// Returns true if there is still simulation state on the worklist.
 125   bool ExecuteWorkListWithInitialState(const LocationContext *L,
 126                                        unsigned Steps,
 127                                        ProgramStateRef InitState,
 128                                        ExplodedNodeSet &Dst);
 129
 130   /// Dispatch the work list item based on the given location information.
 131   /// Use Pred parameter as the predecessor state.
 132   void dispatchWorkItem(ExplodedNode* Pred, ProgramPoint Loc,
 133                         const WorkListUnit& WU);
 134
 135   // Functions for external checking of whether we have unfinished work
 136   bool wasBlockAborted() const { return !blocksAborted.empty(); }
 137   bool wasBlocksExhausted() const { return !blocksExhausted.empty(); }
 138   bool hasWorkRemaining() const { return wasBlocksExhausted() ||
 139                                          WList->hasWork() ||
 140                                          wasBlockAborted(); }
 141
 142   /// Inform the CoreEngine that a basic block was aborted because
 143   /// it could not be completely analyzed.
 144   void addAbortedBlock(const ExplodedNode *node, const CFGBlock *block) {
 145     blocksAborted.push_back(std::make_pair(block, node));
 146   }
 147
 148   WorkList *getWorkList() const { return WList.get(); }
 149
 150   BlocksExhausted::const_iterator blocks_exhausted_begin() const {
 151     return blocksExhausted.begin();
 152   }
 153   BlocksExhausted::const_iterator blocks_exhausted_end() const {
 154     return blocksExhausted.end();
 155   }
 156   BlocksAborted::const_iterator blocks_aborted_begin() const {
 157     return blocksAborted.begin();
 158   }
 159   BlocksAborted::const_iterator blocks_aborted_end() const {
 160     return blocksAborted.end();
 161   }
 162
 163   /// \brief Enqueue the given set of nodes onto the work list.
 164   void enqueue(ExplodedNodeSet &Set);
 165
 166   /// \brief Enqueue nodes that were created as a result of processing
 167   /// a statement onto the work list.
 168   void enqueue(ExplodedNodeSet &Set, const CFGBlock *Block, unsigned Idx);
 169
 170   /// \brief enqueue the nodes corresponding to the end of function onto the
 171   /// end of path / work list.
 172   void enqueueEndOfFunction(ExplodedNodeSet &Set);
 173
 174   /// \brief Enqueue a single node created as a result of statement processing.
 175   void enqueueStmtNode(ExplodedNode *N, const CFGBlock *Block, unsigned Idx);
 176 };
 177
 178 // TODO: Turn into a calss.
 179 struct NodeBuilderContext {
 180   const CoreEngine &Eng;
 181   const CFGBlock *Block;
 182   const LocationContext *LC;
 183   NodeBuilderContext(const CoreEngine &E, const CFGBlock *B, ExplodedNode *N)
 184     : Eng(E), Block(B), LC(N->getLocationContext()) { assert(B); }
 185
 186   /// \brief Return the CFGBlock associated with this builder.
 187   const CFGBlock *getBlock() const { return Block; }
 188
 189   /// \brief Returns the number of times the current basic block has been
 190   /// visited on the exploded graph path.
 191   unsigned blockCount() const {
 192     return Eng.WList->getBlockCounter().getNumVisited(
 193                     LC->getCurrentStackFrame(),
 194                     Block->getBlockID());
 195   }
 196 };
 197
 198 /// \class NodeBuilder
 199 /// \brief This is the simplest builder which generates nodes in the
 200 /// ExplodedGraph.
 201 ///
 202 /// The main benefit of the builder is that it automatically tracks the
 203 /// frontier nodes (or destination set). This is the set of nodes which should
 204 /// be propagated to the next step / builder. They are the nodes which have been
 205 /// added to the builder (either as the input node set or as the newly
 206 /// constructed nodes) but did not have any outgoing transitions added.
 207 class NodeBuilder {
 208   virtual void anchor();
 209 protected:
 210   const NodeBuilderContext &C;
 211
 212   /// Specifies if the builder results have been finalized. For example, if it
 213   /// is set to false, autotransitions are yet to be generated.
 214   bool Finalized;
 215   bool HasGeneratedNodes;
 216   /// \brief The frontier set - a set of nodes which need to be propagated after
 217   /// the builder dies.
 218   ExplodedNodeSet &Frontier;
 219
 220   /// Checkes if the results are ready.
 221   virtual bool checkResults() {
 222     if (!Finalized)
 223       return false;
 224     return true;
 225   }
 226
 227   bool hasNoSinksInFrontier() {
 228     for (iterator I = Frontier.begin(), E = Frontier.end(); I != E; ++I) {
 229       if ((*I)->isSink())
 230         return false;
 231     }
 232     return true;
 233   }
 234
 235   /// Allow subclasses to finalize results before result_begin() is executed.
 236   virtual void finalizeResults() {}
 237
 238   ExplodedNode *generateNodeImpl(const ProgramPoint &PP,
 239                                  ProgramStateRef State,
 240                                  ExplodedNode *Pred,
 241                                  bool MarkAsSink = false);
 242
 243 public:
 244   NodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet,
 245               const NodeBuilderContext &Ctx, bool F = true)
 246     : C(Ctx), Finalized(F), HasGeneratedNodes(false), Frontier(DstSet) {
 247     Frontier.Add(SrcNode);
 248   }
 249
 250   NodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet,
 251               const NodeBuilderContext &Ctx, bool F = true)
 252     : C(Ctx), Finalized(F), HasGeneratedNodes(false), Frontier(DstSet) {
 253     Frontier.insert(SrcSet);
 254     assert(hasNoSinksInFrontier());
 255   }
 256
 257   virtual ~NodeBuilder() {}
 258
 259   /// \brief Generates a node in the ExplodedGraph.
 260   ExplodedNode *generateNode(const ProgramPoint &PP,
 261                              ProgramStateRef State,
 262                              ExplodedNode *Pred) {
 263     return generateNodeImpl(PP, State, Pred, false);
 264   }
 265
 266   /// \brief Generates a sink in the ExplodedGraph.
 267   ///
 268   /// When a node is marked as sink, the exploration from the node is stopped -
 269   /// the node becomes the last node on the path and certain kinds of bugs are
 270   /// suppressed.
 271   ExplodedNode *generateSink(const ProgramPoint &PP,
 272                              ProgramStateRef State,
 273                              ExplodedNode *Pred) {
 274     return generateNodeImpl(PP, State, Pred, true);
 275   }
 276
 277   const ExplodedNodeSet &getResults() {
 278     finalizeResults();
 279     assert(checkResults());
 280     return Frontier;
 281   }
 282
 283   typedef ExplodedNodeSet::iterator iterator;
 284   /// \brief Iterators through the results frontier.
 285   inline iterator begin() {
 286     finalizeResults();
 287     assert(checkResults());
 288     return Frontier.begin();
 289   }
 290   inline iterator end() {
 291     finalizeResults();
 292     return Frontier.end();
 293   }
 294
 295   const NodeBuilderContext &getContext() { return C; }
 296   bool hasGeneratedNodes() { return HasGeneratedNodes; }
 297
 298   void takeNodes(const ExplodedNodeSet &S) {
 299     for (ExplodedNodeSet::iterator I = S.begin(), E = S.end(); I != E; ++I )
 300       Frontier.erase(*I);
 301   }
 302   void takeNodes(ExplodedNode *N) { Frontier.erase(N); }
 303   void addNodes(const ExplodedNodeSet &S) { Frontier.insert(S); }
 304   void addNodes(ExplodedNode *N) { Frontier.Add(N); }
 305 };
 306
 307 /// \class NodeBuilderWithSinks
 308 /// \brief This node builder keeps track of the generated sink nodes.
 309 class NodeBuilderWithSinks: public NodeBuilder {
 310   void anchor() override;
 311 protected:
 312   SmallVector<ExplodedNode*, 2> sinksGenerated;
 313   ProgramPoint &Location;
 314
 315 public:
 316   NodeBuilderWithSinks(ExplodedNode *Pred, ExplodedNodeSet &DstSet,
 317                        const NodeBuilderContext &Ctx, ProgramPoint &L)
 318     : NodeBuilder(Pred, DstSet, Ctx), Location(L) {}
 319
 320   ExplodedNode *generateNode(ProgramStateRef State,
 321                              ExplodedNode *Pred,
 322                              const ProgramPointTag *Tag = nullptr) {
 323     const ProgramPoint &LocalLoc = (Tag ? Location.withTag(Tag) : Location);
 324     return NodeBuilder::generateNode(LocalLoc, State, Pred);
 325   }
 326
 327   ExplodedNode *generateSink(ProgramStateRef State, ExplodedNode *Pred,
 328                              const ProgramPointTag *Tag = nullptr) {
 329     const ProgramPoint &LocalLoc = (Tag ? Location.withTag(Tag) : Location);
 330     ExplodedNode *N = NodeBuilder::generateSink(LocalLoc, State, Pred);
 331     if (N && N->isSink())
 332       sinksGenerated.push_back(N);
 333     return N;
 334   }
 335
 336   const SmallVectorImpl<ExplodedNode*> &getSinks() const {
 337     return sinksGenerated;
 338   }
 339 };
 340
 341 /// \class StmtNodeBuilder
 342 /// \brief This builder class is useful for generating nodes that resulted from
 343 /// visiting a statement. The main difference from its parent NodeBuilder is
 344 /// that it creates a statement specific ProgramPoint.
 345 class StmtNodeBuilder: public NodeBuilder {
 346   NodeBuilder *EnclosingBldr;
 347 public:
 348
 349   /// \brief Constructs a StmtNodeBuilder. If the builder is going to process
 350   /// nodes currently owned by another builder(with larger scope), use
 351   /// Enclosing builder to transfer ownership.
 352   StmtNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet,
 353                   const NodeBuilderContext &Ctx,
 354                   NodeBuilder *Enclosing = nullptr)
 355     : NodeBuilder(SrcNode, DstSet, Ctx), EnclosingBldr(Enclosing) {
 356     if (EnclosingBldr)
 357       EnclosingBldr->takeNodes(SrcNode);
 358   }
 359
 360   StmtNodeBuilder(ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet,
 361                   const NodeBuilderContext &Ctx,
 362                   NodeBuilder *Enclosing = nullptr)
 363     : NodeBuilder(SrcSet, DstSet, Ctx), EnclosingBldr(Enclosing) {
 364     if (EnclosingBldr)
 365       for (ExplodedNodeSet::iterator I = SrcSet.begin(),
 366                                      E = SrcSet.end(); I != E; ++I )
 367         EnclosingBldr->takeNodes(*I);
 368   }
 369
 370   virtual ~StmtNodeBuilder();
 371
 372   using NodeBuilder::generateNode;
 373   using NodeBuilder::generateSink;
 374
 375   ExplodedNode *generateNode(const Stmt *S,
 376                              ExplodedNode *Pred,
 377                              ProgramStateRef St,
 378                              const ProgramPointTag *tag = nullptr,
 379                              ProgramPoint::Kind K = ProgramPoint::PostStmtKind){
 380     const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K,
 381                                   Pred->getLocationContext(), tag);
 382     return NodeBuilder::generateNode(L, St, Pred);
 383   }
 384
 385   ExplodedNode *generateSink(const Stmt *S,
 386                              ExplodedNode *Pred,
 387                              ProgramStateRef St,
 388                              const ProgramPointTag *tag = nullptr,
 389                              ProgramPoint::Kind K = ProgramPoint::PostStmtKind){
 390     const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K,
 391                                   Pred->getLocationContext(), tag);
 392     return NodeBuilder::generateSink(L, St, Pred);
 393   }
 394 };
 395
 396 /// \brief BranchNodeBuilder is responsible for constructing the nodes
 397 /// corresponding to the two branches of the if statement - true and false.
 398 class BranchNodeBuilder: public NodeBuilder {
 399   void anchor() override;
 400   const CFGBlock *DstT;
 401   const CFGBlock *DstF;
 402
 403   bool InFeasibleTrue;
 404   bool InFeasibleFalse;
 405
 406 public:
 407   BranchNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet,
 408                     const NodeBuilderContext &C,
 409                     const CFGBlock *dstT, const CFGBlock *dstF)
 410   : NodeBuilder(SrcNode, DstSet, C), DstT(dstT), DstF(dstF),
 411     InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {
 412     // The branch node builder does not generate autotransitions.
 413     // If there are no successors it means that both branches are infeasible.
 414     takeNodes(SrcNode);
 415   }
 416
 417   BranchNodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet,
 418                     const NodeBuilderContext &C,
 419                     const CFGBlock *dstT, const CFGBlock *dstF)
 420   : NodeBuilder(SrcSet, DstSet, C), DstT(dstT), DstF(dstF),
 421     InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {
 422     takeNodes(SrcSet);
 423   }
 424
 425   ExplodedNode *generateNode(ProgramStateRef State, bool branch,
 426                              ExplodedNode *Pred);
 427
 428   const CFGBlock *getTargetBlock(bool branch) const {
 429     return branch ? DstT : DstF;
 430   }
 431
 432   void markInfeasible(bool branch) {
 433     if (branch)
 434       InFeasibleTrue = true;
 435     else
 436       InFeasibleFalse = true;
 437   }
 438
 439   bool isFeasible(bool branch) {
 440     return branch ? !InFeasibleTrue : !InFeasibleFalse;
 441   }
 442 };
 443
 444 class IndirectGotoNodeBuilder {
 445   CoreEngine& Eng;
 446   const CFGBlock *Src;
 447   const CFGBlock &DispatchBlock;
 448   const Expr *E;
 449   ExplodedNode *Pred;
 450
 451 public:
 452   IndirectGotoNodeBuilder(ExplodedNode *pred, const CFGBlock *src,
 453                     const Expr *e, const CFGBlock *dispatch, CoreEngine* eng)
 454     : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {}
 455
 456   class iterator {
 457     CFGBlock::const_succ_iterator I;
 458
 459     friend class IndirectGotoNodeBuilder;
 460     iterator(CFGBlock::const_succ_iterator i) : I(i) {}
 461   public:
 462
 463     iterator &operator++() { ++I; return *this; }
 464     bool operator!=(const iterator &X) const { return I != X.I; }
 465
 466     const LabelDecl *getLabel() const {
 467       return cast<LabelStmt>((*I)->getLabel())->getDecl();
 468     }
 469
 470     const CFGBlock *getBlock() const {
 471       return *I;
 472     }
 473   };
 474
 475   iterator begin() { return iterator(DispatchBlock.succ_begin()); }
 476   iterator end() { return iterator(DispatchBlock.succ_end()); }
 477
 478   ExplodedNode *generateNode(const iterator &I,
 479                              ProgramStateRef State,
 480                              bool isSink = false);
 481
 482   const Expr *getTarget() const { return E; }
 483
 484   ProgramStateRef getState() const { return Pred->State; }
 485
 486   const LocationContext *getLocationContext() const {
 487     return Pred->getLocationContext();
 488   }
 489 };
 490
 491 class SwitchNodeBuilder {
 492   CoreEngine& Eng;
 493   const CFGBlock *Src;
 494   const Expr *Condition;
 495   ExplodedNode *Pred;
 496
 497 public:
 498   SwitchNodeBuilder(ExplodedNode *pred, const CFGBlock *src,
 499                     const Expr *condition, CoreEngine* eng)
 500   : Eng(*eng), Src(src), Condition(condition), Pred(pred) {}
 501
 502   class iterator {
 503     CFGBlock::const_succ_reverse_iterator I;
 504
 505     friend class SwitchNodeBuilder;
 506     iterator(CFGBlock::const_succ_reverse_iterator i) : I(i) {}
 507
 508   public:
 509     iterator &operator++() { ++I; return *this; }
 510     bool operator!=(const iterator &X) const { return I != X.I; }
 511     bool operator==(const iterator &X) const { return I == X.I; }
 512
 513     const CaseStmt *getCase() const {
 514       return cast<CaseStmt>((*I)->getLabel());
 515     }
 516
 517     const CFGBlock *getBlock() const {
 518       return *I;
 519     }
 520   };
 521
 522   iterator begin() { return iterator(Src->succ_rbegin()+1); }
 523   iterator end() { return iterator(Src->succ_rend()); }
 524
 525   const SwitchStmt *getSwitch() const {
 526     return cast<SwitchStmt>(Src->getTerminator());
 527   }
 528
 529   ExplodedNode *generateCaseStmtNode(const iterator &I,
 530                                      ProgramStateRef State);
 531
 532   ExplodedNode *generateDefaultCaseNode(ProgramStateRef State,
 533                                         bool isSink = false);
 534
 535   const Expr *getCondition() const { return Condition; }
 536
 537   ProgramStateRef getState() const { return Pred->State; }
 538
 539   const LocationContext *getLocationContext() const {
 540     return Pred->getLocationContext();
 541   }
 542 };
 543
 544 } // end ento namespace
 545 } // end clang namespace
 546
 547 #endif