contrib/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h

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