AnalysisDeclContext.h

Go to the documentation of this file.

//===- AnalysisDeclContext.h - Context for path sensitivity -----*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
/// \file
/// This file defines AnalysisDeclContext, a class that manages the analysis
/// context data for context sensitive and path sensitive analysis.
/// It also defines the helper classes to model entering, leaving or inlining
/// function calls.
//
//===----------------------------------------------------------------------===//
 
#ifndef LLVM_CLANG_ANALYSIS_ANALYSISDECLCONTEXT_H
#define LLVM_CLANG_ANALYSIS_ANALYSISDECLCONTEXT_H
 
#include "clang/AST/DeclBase.h"
#include "clang/Analysis/BodyFarm.h"
#include "clang/Analysis/CFG.h"
#include "clang/Analysis/CFGStmtMap.h"
#include "clang/Analysis/CodeInjector.h"
#include "clang/Basic/LLVM.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/FoldingSet.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Support/Allocator.h"
#include <functional>
#include <iterator>
#include <memory>
 
namespace clang {
 
class AnalysisDeclContextManager;
class ASTContext;
class BlockDecl;
class CFGReverseBlockReachabilityAnalysis;
class ImplicitParamDecl;
class StackFrameManager;
class ParentMap;
class StackFrame;
class Stmt;
class VarDecl;
 
/// The base class of a hierarchy of objects representing analyses tied
/// to AnalysisDeclContext.
class ManagedAnalysis {
protected:
  ManagedAnalysis() = default;
 
public:
  virtual ~ManagedAnalysis();
 
  // Subclasses need to implement:
  //
  //  static const void *getTag();
  //
  // Which returns a fixed pointer address to distinguish classes of
  // analysis objects.  They also need to implement:
  //
  //  static [Derived*] create(AnalysisDeclContext &Ctx);
  //
  // which creates the analysis object given an AnalysisDeclContext.
};
 
/// AnalysisDeclContext contains the context data for the function, method
/// or block under analysis.
class AnalysisDeclContext {
  // Backpoint to the AnalysisManager object that created this
  // AnalysisDeclContext. This may be null.
  AnalysisDeclContextManager *ADCMgr;
 
  const Decl *const D;
 
  std::unique_ptr<CFG> cfg, completeCFG;
  std::optional<CFGStmtMap> cfgStmtMap;
 
  CFG::BuildOptions cfgBuildOptions;
  CFG::BuildOptions::ForcedBlkExprs *forcedBlkExprs = nullptr;
 
  bool builtCFG = false;
  bool builtCompleteCFG = false;
  std::unique_ptr<ParentMap> PM;
  std::unique_ptr<CFGReverseBlockReachabilityAnalysis> CFA;
 
  llvm::BumpPtrAllocator A;
 
  llvm::DenseMap<const BlockDecl *, void *> *ReferencedBlockVars = nullptr;
 
  void *ManagedAnalyses = nullptr;
 
public:
  AnalysisDeclContext(AnalysisDeclContextManager *Mgr, const Decl *D);
 
  AnalysisDeclContext(AnalysisDeclContextManager *Mgr, const Decl *D,
                      const CFG::BuildOptions &BuildOptions);
 
  ~AnalysisDeclContext();
 
  ASTContext &getASTContext() const { return D->getASTContext(); }
 
  const Decl *getDecl() const { return D; }
 
  AnalysisDeclContextManager *getManager() const { return ADCMgr; }
 
  CFG::BuildOptions &getCFGBuildOptions() { return cfgBuildOptions; }
 
  const CFG::BuildOptions &getCFGBuildOptions() const {
    return cfgBuildOptions;
  }
 
  /// \returns Whether we are adding exception handling edges from CallExprs.
  /// If this is false, then try/catch statements and blocks reachable from them
  /// can appear to be dead in the CFG, analysis passes must cope with that.
  bool getAddEHEdges() const { return cfgBuildOptions.AddEHEdges; }
  bool getUseUnoptimizedCFG() const {
    return !cfgBuildOptions.PruneTriviallyFalseEdges;
  }
  bool getAddImplicitDtors() const { return cfgBuildOptions.AddImplicitDtors; }
  bool getAddInitializers() const { return cfgBuildOptions.AddInitializers; }
 
  void registerForcedBlockExpression(const Stmt *stmt);
  const CFGBlock *getBlockForRegisteredExpression(const Stmt *stmt);
 
  /// \returns The body of the stored Decl \c D.
  Stmt *getBody() const;
 
  /// \copydoc AnalysisDeclContext::getBody()
  /// \param[out] IsAutosynthesized Specifies if the body is auto-generated
  ///             by the BodyFarm.
  Stmt *getBody(bool &IsAutosynthesized) const;
 
  /// \returns Whether the body of the Decl \c D is generated by the BodyFarm.
  ///
  /// \note The lookup is not free. We are going to call getBody behind
  /// the scenes.
  /// \sa getBody
  bool isBodyAutosynthesized() const;
 
  /// \returns Whether the body of the Decl \c D is generated by the BodyFarm
  /// from a model file.
  ///
  /// \note The lookup is not free. We are going to call getBody behind
  /// the scenes.
  /// \sa getBody
  bool isBodyAutosynthesizedFromModelFile() const;
 
  CFG *getCFG();
 
  const CFGStmtMap *getCFGStmtMap();
 
  CFGReverseBlockReachabilityAnalysis *getCFGReachablityAnalysis();
 
  /// \returns A version of the CFG without any edges pruned.
  CFG *getUnoptimizedCFG();
 
  void dumpCFG(bool ShowColors);
 
  /// \returns Whether we have built a CFG for this analysis context.
  ///
  /// \note This doesn't correspond to whether or not a valid CFG exists, it
  /// corresponds to whether we *attempted* to build one.
  bool isCFGBuilt() const { return builtCFG; }
 
  ParentMap &getParentMap();
 
  using referenced_decls_iterator = const VarDecl *const *;
 
  llvm::iterator_range<referenced_decls_iterator>
  getReferencedBlockVars(const BlockDecl *BD);
 
  /// \returns The ImplicitParamDecl associated with \c self if this
  /// AnalysisDeclContext wraps an ObjCMethodDecl or nullptr otherwise.
  const ImplicitParamDecl *getSelfDecl() const;
 
  /// \copydoc StackFrameManager::getStackFrame()
  const StackFrame *getStackFrame(const StackFrame *ParentSF, const void *Data,
                                  const Expr *E, const CFGBlock *Blk,
                                  unsigned BlockCount, unsigned Index);
 
  /// \returns The specified analysis object, lazily running the analysis if
  /// necessary or nullptr if the analysis could not run.
  template <typename T> T *getAnalysis() {
    const void *tag = T::getTag();
    std::unique_ptr<ManagedAnalysis> &data = getAnalysisImpl(tag);
    if (!data)
      data = T::create(*this);
    return static_cast<T *>(data.get());
  }
 
  /// \returns Whether the root namespace of \p D is the \c std C++ namespace.
  static bool isInStdNamespace(const Decl *D);
 
  static std::string getFunctionName(const Decl *D);
 
private:
  std::unique_ptr<ManagedAnalysis> &getAnalysisImpl(const void *tag);
 
  StackFrameManager &getStackFrameManager();
};
 
/// It represents a stack frame of the call stack
class StackFrame final : public llvm::FoldingSetNode {
  friend class StackFrameManager;
 
  // AnalysisDeclContext can't be const since some methods may modify its
  // member.
  AnalysisDeclContext *Ctx;
 
  const StackFrame *Parent;
 
  int64_t ID;
 
  // Extra data for BlockInvocations
  const void *Data;
 
  // The call site where this stack frame is established.
  const Expr *CallSite;
 
  // The parent block of the call site.
  const CFGBlock *Block;
 
  // The number of times the 'Block' has been visited.
  // It allows discriminating between stack frames of the same call that is
  // called multiple times in a loop.
  const unsigned BlockCount;
 
  // The index of the call site in the CFGBlock.
  const unsigned Index;
 
public:
  StackFrame(AnalysisDeclContext *ADC, const StackFrame *Parent,
             const void *Data, const Expr *E, const CFGBlock *Block,
             unsigned BlockCount, unsigned Index, int64_t ID)
      : Ctx(ADC), Parent(Parent), ID(ID), Data(Data), CallSite(E), Block(Block),
        BlockCount(BlockCount), Index(Index) {
    assert(ADC);
  }
 
  ~StackFrame() = default;
 
  LLVM_ATTRIBUTE_RETURNS_NONNULL
  AnalysisDeclContext *getAnalysisDeclContext() const { return Ctx; }
 
  /// It might return null.
  const StackFrame *getParent() const { return Parent; }
 
  /// Forward iterator over a chain of \c StackFrame parents. Advancing follows
  /// \c getParent(); the past-the-end iterator holds a null frame.
  class parent_iterator {
    const StackFrame *Current = nullptr;
 
  public:
    using iterator_category = std::forward_iterator_tag;
    using value_type = const StackFrame;
    using difference_type = std::ptrdiff_t;
    using pointer = const StackFrame *;
    using reference = const StackFrame &;
 
    parent_iterator() = default;
    explicit parent_iterator(const StackFrame *SF) : Current(SF) {}
 
    reference operator*() const { return *Current; }
    pointer operator->() const { return Current; }
    parent_iterator &operator++() {
      assert(Current && "Cannot call ++ on the end iterator");
      Current = Current->getParent();
      return *this;
    }
    parent_iterator operator++(int) {
      parent_iterator Tmp = *this;
      ++*this;
      return Tmp;
    }
    bool operator==(const parent_iterator &Other) const {
      return Current == Other.Current;
    }
    bool operator!=(const parent_iterator &Other) const {
      return !(*this == Other);
    }
  };
 
  /// Iterates over the strict ancestors of this frame, i.e. \c getParent(),
  /// \c getParent()->getParent(), ... up to (but excluding) the null frame.
  /// Does not include \c *this.
  llvm::iterator_range<parent_iterator> parents() const {
    return {parent_iterator(getParent()), parent_iterator()};
  }
 
  /// Iterates over this frame followed by all of its ancestors.
  llvm::iterator_range<parent_iterator> parentsIncludingSelf() const {
    return {parent_iterator(this), parent_iterator()};
  }
 
  int64_t getID() const { return ID; }
 
  bool isParentOf(const StackFrame *SF) const;
 
  const Decl *getDecl() const { return Ctx->getDecl(); }
 
  CFG *getCFG() const { return Ctx->getCFG(); }
 
  template <typename T> T *getAnalysis() const { return Ctx->getAnalysis<T>(); }
 
  const ParentMap &getParentMap() const { return Ctx->getParentMap(); }
 
  /// \copydoc AnalysisDeclContext::getSelfDecl()
  const ImplicitParamDecl *getSelfDecl() const { return Ctx->getSelfDecl(); }
 
  const void *getData() const { return Data; }
 
  const Expr *getCallSite() const { return CallSite; }
 
  const CFGBlock *getCallSiteBlock() const { return Block; }
 
  /// \returns Whether the current StackFrame has no caller context.
  bool inTopFrame() const { return getParent() == nullptr; }
 
  unsigned getIndex() const { return Index; }
 
  CFGElement getCallSiteCFGElement() const { return (*Block)[Index]; }
 
  /// Prints out the call stack in \c json format.
  ///
  /// \param Out   The out stream.
  /// \param NL    The newline.
  /// \param Space The space count for indentation.
  /// \param IsDot Whether the output format is \c dot.
  /// \param printMoreInfoPerStackFrame
  /// A callback to print more information for each stack frame, for example:
  /// \code
  ///   [&](const StackFrame *SF) { SF->dump(); }
  /// \endcode
  void printJson(
      raw_ostream &Out, const char *NL = "\n", unsigned int Space = 0,
      bool IsDot = false,
      std::function<void(const StackFrame *)> printMoreInfoPerStackFrame =
          [](const StackFrame *) {}) const;
 
  /// Prints out the call stack.
  ///
  /// \param Out The out stream.
  LLVM_DUMP_METHOD void dumpStack(raw_ostream &Out) const;
 
  LLVM_DUMP_METHOD void dump() const;
 
  void Profile(llvm::FoldingSetNodeID &ID);
 
  static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ADC,
                      const StackFrame *SF, const void *Data, const Expr *E,
                      const CFGBlock *Block, unsigned BlockCount,
                      unsigned Index) {
    ID.AddPointer(ADC);
    ID.AddPointer(SF);
    ID.AddPointer(E);
    ID.AddPointer(Data);
    ID.AddPointer(Block);
    ID.AddInteger(BlockCount);
    ID.AddInteger(Index);
  }
};
 
class StackFrameManager {
  llvm::FoldingSet<StackFrame> Frames;
 
  // ID used for generating a new stack frame.
  int64_t NewID = 0;
 
public:
  ~StackFrameManager();
 
  /// Obtain a context of the call stack using its parent context.
  ///
  /// \param ADC        The AnalysisDeclContext.
  /// \param ParentSF   The parent context of this newly created
  ///                   context.
  /// \param Data       Extra data in case this StackFrame is
  ///                   created for a BlockInvocation.
  /// \param E          The call expression.
  /// \param Block      The basic block.
  /// \param BlockCount The current count of entering into \p Block.
  /// \param StmtIdx    The index of the call expression \p E among the
  ///                   statements of the CFGBlock \p Block.
  /// \returns The stack frame context corresponding to the call.
  const StackFrame *getStackFrame(AnalysisDeclContext *ADC,
                                  const StackFrame *ParentSF, const void *Data,
                                  const Expr *E, const CFGBlock *Block,
                                  unsigned BlockCount, unsigned StmtIdx);
 
  /// Discard all previously created StackFrame objects.
  void clear();
};
 
class AnalysisDeclContextManager {
  using ContextMap =
      llvm::DenseMap<const Decl *, std::unique_ptr<AnalysisDeclContext>>;
 
  ContextMap Contexts;
  StackFrameManager SFMgr;
  CFG::BuildOptions cfgBuildOptions;
 
  // Pointer to an interface that can provide function bodies for
  // declarations from external source.
  std::unique_ptr<CodeInjector> Injector;
 
  // A factory for creating and caching implementations for common
  // methods during the analysis.
  BodyFarm FunctionBodyFarm;
 
  // Flag to indicate whether or not bodies should be synthesized
  // for well-known functions.
  bool SynthesizeBodies;
 
public:
  AnalysisDeclContextManager(
      ASTContext &ASTCtx, bool useUnoptimizedCFG = false,
      bool addImplicitDtors = false, bool addInitializers = false,
      bool addTemporaryDtors = false, bool addLifetime = false,
      bool addLoopExit = false, bool addScopes = false,
      bool synthesizeBodies = false, bool addStaticInitBranches = false,
      bool addCXXNewAllocator = true, bool addRichCXXConstructors = true,
      bool markElidedCXXConstructors = true, bool addVirtualBaseBranches = true,
      std::unique_ptr<CodeInjector> injector = nullptr);
 
  AnalysisDeclContext *getContext(const Decl *D);
 
  bool getUseUnoptimizedCFG() const {
    return !cfgBuildOptions.PruneTriviallyFalseEdges;
  }
 
  CFG::BuildOptions &getCFGBuildOptions() { return cfgBuildOptions; }
 
  /// \returns Whether faux bodies should be synthesized for known functions.
  bool synthesizeBodies() const { return SynthesizeBodies; }
 
  /// Obtain the beginning context of the analysis.
  ///
  /// \returns The top level stack frame for \p D.
  const StackFrame *getTopStackFrame(const Decl *D) {
    return SFMgr.getStackFrame(getContext(D), nullptr, nullptr, nullptr,
                               nullptr, 0, 0);
  }
 
  BodyFarm &getBodyFarm();
 
  /// Discard all previously created AnalysisDeclContexts.
  void clear();
 
private:
  friend class AnalysisDeclContext;
 
  StackFrameManager &getStackFrameManager() { return SFMgr; }
};
 
} // namespace clang
 
#endif // LLVM_CLANG_ANALYSIS_ANALYSISDECLCONTEXT_H