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