Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

Blame | Last modification | View Log | Download | RSS feed

  1. //==- MemRegion.h - Abstract memory regions for static analysis -*- 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 MemRegion and its subclasses.  MemRegion defines a
  10. //  partially-typed abstraction of memory useful for path-sensitive dataflow
  11. //  analyses.
  12. //
  13. //===----------------------------------------------------------------------===//
  14.  
  15. #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_MEMREGION_H
  16. #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_MEMREGION_H
  17.  
  18. #include "clang/AST/ASTContext.h"
  19. #include "clang/AST/CharUnits.h"
  20. #include "clang/AST/Decl.h"
  21. #include "clang/AST/DeclObjC.h"
  22. #include "clang/AST/DeclarationName.h"
  23. #include "clang/AST/Expr.h"
  24. #include "clang/AST/ExprObjC.h"
  25. #include "clang/AST/Type.h"
  26. #include "clang/Analysis/AnalysisDeclContext.h"
  27. #include "clang/Basic/LLVM.h"
  28. #include "clang/Basic/SourceLocation.h"
  29. #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
  30. #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
  31. #include "llvm/ADT/DenseMap.h"
  32. #include "llvm/ADT/FoldingSet.h"
  33. #include "llvm/ADT/PointerIntPair.h"
  34. #include "llvm/Support/Allocator.h"
  35. #include "llvm/Support/Casting.h"
  36. #include <cassert>
  37. #include <cstdint>
  38. #include <limits>
  39. #include <optional>
  40. #include <string>
  41. #include <utility>
  42.  
  43. namespace clang {
  44.  
  45. class AnalysisDeclContext;
  46. class CXXRecordDecl;
  47. class Decl;
  48. class LocationContext;
  49. class StackFrameContext;
  50.  
  51. namespace ento {
  52.  
  53. class CodeTextRegion;
  54. class MemRegion;
  55. class MemRegionManager;
  56. class MemSpaceRegion;
  57. class SValBuilder;
  58. class SymbolicRegion;
  59. class VarRegion;
  60.  
  61. /// Represent a region's offset within the top level base region.
  62. class RegionOffset {
  63.   /// The base region.
  64.   const MemRegion *R = nullptr;
  65.  
  66.   /// The bit offset within the base region. Can be negative.
  67.   int64_t Offset;
  68.  
  69. public:
  70.   // We're using a const instead of an enumeration due to the size required;
  71.   // Visual Studio will only create enumerations of size int, not long long.
  72.   static const int64_t Symbolic = std::numeric_limits<int64_t>::max();
  73.  
  74.   RegionOffset() = default;
  75.   RegionOffset(const MemRegion *r, int64_t off) : R(r), Offset(off) {}
  76.  
  77.   /// It might return null.
  78.   const MemRegion *getRegion() const { return R; }
  79.  
  80.   bool hasSymbolicOffset() const { return Offset == Symbolic; }
  81.  
  82.   int64_t getOffset() const {
  83.     assert(!hasSymbolicOffset());
  84.     return Offset;
  85.   }
  86.  
  87.   bool isValid() const { return R; }
  88. };
  89.  
  90. //===----------------------------------------------------------------------===//
  91. // Base region classes.
  92. //===----------------------------------------------------------------------===//
  93.  
  94. /// MemRegion - The root abstract class for all memory regions.
  95. class MemRegion : public llvm::FoldingSetNode {
  96. public:
  97.   enum Kind {
  98. #define REGION(Id, Parent) Id ## Kind,
  99. #define REGION_RANGE(Id, First, Last) BEGIN_##Id = First, END_##Id = Last,
  100. #include "clang/StaticAnalyzer/Core/PathSensitive/Regions.def"
  101.   };
  102.  
  103. private:
  104.   const Kind kind;
  105.   mutable std::optional<RegionOffset> cachedOffset;
  106.  
  107. protected:
  108.   MemRegion(Kind k) : kind(k) {}
  109.   virtual ~MemRegion();
  110.  
  111. public:
  112.   ASTContext &getContext() const;
  113.  
  114.   virtual void Profile(llvm::FoldingSetNodeID& ID) const = 0;
  115.  
  116.   virtual MemRegionManager &getMemRegionManager() const = 0;
  117.  
  118.   LLVM_ATTRIBUTE_RETURNS_NONNULL const MemSpaceRegion *getMemorySpace() const;
  119.  
  120.   LLVM_ATTRIBUTE_RETURNS_NONNULL const MemRegion *getBaseRegion() const;
  121.  
  122.   /// Recursively retrieve the region of the most derived class instance of
  123.   /// regions of C++ base class instances.
  124.   LLVM_ATTRIBUTE_RETURNS_NONNULL
  125.   const MemRegion *getMostDerivedObjectRegion() const;
  126.  
  127.   /// Check if the region is a subregion of the given region.
  128.   /// Each region is a subregion of itself.
  129.   virtual bool isSubRegionOf(const MemRegion *R) const;
  130.  
  131.   LLVM_ATTRIBUTE_RETURNS_NONNULL
  132.   const MemRegion *StripCasts(bool StripBaseAndDerivedCasts = true) const;
  133.  
  134.   /// If this is a symbolic region, returns the region. Otherwise,
  135.   /// goes up the base chain looking for the first symbolic base region.
  136.   /// It might return null.
  137.   const SymbolicRegion *getSymbolicBase() const;
  138.  
  139.   bool hasGlobalsOrParametersStorage() const;
  140.  
  141.   bool hasStackStorage() const;
  142.  
  143.   bool hasStackNonParametersStorage() const;
  144.  
  145.   bool hasStackParametersStorage() const;
  146.  
  147.   /// Compute the offset within the top level memory object.
  148.   RegionOffset getAsOffset() const;
  149.  
  150.   /// Get a string representation of a region for debug use.
  151.   std::string getString() const;
  152.  
  153.   virtual void dumpToStream(raw_ostream &os) const;
  154.  
  155.   void dump() const;
  156.  
  157.   /// Returns true if this region can be printed in a user-friendly way.
  158.   virtual bool canPrintPretty() const;
  159.  
  160.   /// Print the region for use in diagnostics.
  161.   virtual void printPretty(raw_ostream &os) const;
  162.  
  163.   /// Returns true if this region's textual representation can be used
  164.   /// as part of a larger expression.
  165.   virtual bool canPrintPrettyAsExpr() const;
  166.  
  167.   /// Print the region as expression.
  168.   ///
  169.   /// When this region represents a subexpression, the method is for printing
  170.   /// an expression containing it.
  171.   virtual void printPrettyAsExpr(raw_ostream &os) const;
  172.  
  173.   Kind getKind() const { return kind; }
  174.  
  175.   template<typename RegionTy> const RegionTy* getAs() const;
  176.   template <typename RegionTy>
  177.   LLVM_ATTRIBUTE_RETURNS_NONNULL const RegionTy *castAs() const;
  178.  
  179.   virtual bool isBoundable() const { return false; }
  180.  
  181.   /// Get descriptive name for memory region. The name is obtained from
  182.   /// the variable/field declaration retrieved from the memory region.
  183.   /// Regions that point to an element of an array are returned as: "arr[0]".
  184.   /// Regions that point to a struct are returned as: "st.var".
  185.   //
  186.   /// \param UseQuotes Set if the name should be quoted.
  187.   ///
  188.   /// \returns variable name for memory region
  189.   std::string getDescriptiveName(bool UseQuotes = true) const;
  190.  
  191.   /// Retrieve source range from memory region. The range retrieval
  192.   /// is based on the decl obtained from the memory region.
  193.   /// For a VarRegion the range of the base region is returned.
  194.   /// For a FieldRegion the range of the field is returned.
  195.   /// If no declaration is found, an empty source range is returned.
  196.   /// The client is responsible for checking if the returned range is valid.
  197.   ///
  198.   /// \returns source range for declaration retrieved from memory region
  199.   SourceRange sourceRange() const;
  200. };
  201.  
  202. /// MemSpaceRegion - A memory region that represents a "memory space";
  203. ///  for example, the set of global variables, the stack frame, etc.
  204. class MemSpaceRegion : public MemRegion {
  205. protected:
  206.   MemRegionManager &Mgr;
  207.  
  208.   MemSpaceRegion(MemRegionManager &mgr, Kind k) : MemRegion(k), Mgr(mgr) {
  209.     assert(classof(this));
  210.   }
  211.  
  212.   MemRegionManager &getMemRegionManager() const override { return Mgr; }
  213.  
  214. public:
  215.   bool isBoundable() const override { return false; }
  216.  
  217.   void Profile(llvm::FoldingSetNodeID &ID) const override;
  218.  
  219.   static bool classof(const MemRegion *R) {
  220.     Kind k = R->getKind();
  221.     return k >= BEGIN_MEMSPACES && k <= END_MEMSPACES;
  222.   }
  223. };
  224.  
  225. /// CodeSpaceRegion - The memory space that holds the executable code of
  226. /// functions and blocks.
  227. class CodeSpaceRegion : public MemSpaceRegion {
  228.   friend class MemRegionManager;
  229.  
  230.   CodeSpaceRegion(MemRegionManager &mgr)
  231.       : MemSpaceRegion(mgr, CodeSpaceRegionKind) {}
  232.  
  233. public:
  234.   void dumpToStream(raw_ostream &os) const override;
  235.  
  236.   static bool classof(const MemRegion *R) {
  237.     return R->getKind() == CodeSpaceRegionKind;
  238.   }
  239. };
  240.  
  241. class GlobalsSpaceRegion : public MemSpaceRegion {
  242.   virtual void anchor();
  243.  
  244. protected:
  245.   GlobalsSpaceRegion(MemRegionManager &mgr, Kind k) : MemSpaceRegion(mgr, k) {
  246.     assert(classof(this));
  247.   }
  248.  
  249. public:
  250.   static bool classof(const MemRegion *R) {
  251.     Kind k = R->getKind();
  252.     return k >= BEGIN_GLOBAL_MEMSPACES && k <= END_GLOBAL_MEMSPACES;
  253.   }
  254. };
  255.  
  256. /// The region of the static variables within the current CodeTextRegion
  257. /// scope.
  258. ///
  259. /// Currently, only the static locals are placed there, so we know that these
  260. /// variables do not get invalidated by calls to other functions.
  261. class StaticGlobalSpaceRegion : public GlobalsSpaceRegion {
  262.   friend class MemRegionManager;
  263.  
  264.   const CodeTextRegion *CR;
  265.  
  266.   StaticGlobalSpaceRegion(MemRegionManager &mgr, const CodeTextRegion *cr)
  267.       : GlobalsSpaceRegion(mgr, StaticGlobalSpaceRegionKind), CR(cr) {
  268.     assert(cr);
  269.   }
  270.  
  271. public:
  272.   void Profile(llvm::FoldingSetNodeID &ID) const override;
  273.  
  274.   void dumpToStream(raw_ostream &os) const override;
  275.  
  276.   LLVM_ATTRIBUTE_RETURNS_NONNULL
  277.   const CodeTextRegion *getCodeRegion() const { return CR; }
  278.  
  279.   static bool classof(const MemRegion *R) {
  280.     return R->getKind() == StaticGlobalSpaceRegionKind;
  281.   }
  282. };
  283.  
  284. /// The region for all the non-static global variables.
  285. ///
  286. /// This class is further split into subclasses for efficient implementation of
  287. /// invalidating a set of related global values as is done in
  288. /// RegionStoreManager::invalidateRegions (instead of finding all the dependent
  289. /// globals, we invalidate the whole parent region).
  290. class NonStaticGlobalSpaceRegion : public GlobalsSpaceRegion {
  291.   void anchor() override;
  292.  
  293. protected:
  294.   NonStaticGlobalSpaceRegion(MemRegionManager &mgr, Kind k)
  295.       : GlobalsSpaceRegion(mgr, k) {
  296.     assert(classof(this));
  297.   }
  298.  
  299. public:
  300.   static bool classof(const MemRegion *R) {
  301.     Kind k = R->getKind();
  302.     return k >= BEGIN_NON_STATIC_GLOBAL_MEMSPACES &&
  303.            k <= END_NON_STATIC_GLOBAL_MEMSPACES;
  304.   }
  305. };
  306.  
  307. /// The region containing globals which are defined in system/external
  308. /// headers and are considered modifiable by system calls (ex: errno).
  309. class GlobalSystemSpaceRegion : public NonStaticGlobalSpaceRegion {
  310.   friend class MemRegionManager;
  311.  
  312.   GlobalSystemSpaceRegion(MemRegionManager &mgr)
  313.       : NonStaticGlobalSpaceRegion(mgr, GlobalSystemSpaceRegionKind) {}
  314.  
  315. public:
  316.   void dumpToStream(raw_ostream &os) const override;
  317.  
  318.   static bool classof(const MemRegion *R) {
  319.     return R->getKind() == GlobalSystemSpaceRegionKind;
  320.   }
  321. };
  322.  
  323. /// The region containing globals which are considered not to be modified
  324. /// or point to data which could be modified as a result of a function call
  325. /// (system or internal). Ex: Const global scalars would be modeled as part of
  326. /// this region. This region also includes most system globals since they have
  327. /// low chance of being modified.
  328. class GlobalImmutableSpaceRegion : public NonStaticGlobalSpaceRegion {
  329.   friend class MemRegionManager;
  330.  
  331.   GlobalImmutableSpaceRegion(MemRegionManager &mgr)
  332.       : NonStaticGlobalSpaceRegion(mgr, GlobalImmutableSpaceRegionKind) {}
  333.  
  334. public:
  335.   void dumpToStream(raw_ostream &os) const override;
  336.  
  337.   static bool classof(const MemRegion *R) {
  338.     return R->getKind() == GlobalImmutableSpaceRegionKind;
  339.   }
  340. };
  341.  
  342. /// The region containing globals which can be modified by calls to
  343. /// "internally" defined functions - (for now just) functions other then system
  344. /// calls.
  345. class GlobalInternalSpaceRegion : public NonStaticGlobalSpaceRegion {
  346.   friend class MemRegionManager;
  347.  
  348.   GlobalInternalSpaceRegion(MemRegionManager &mgr)
  349.       : NonStaticGlobalSpaceRegion(mgr, GlobalInternalSpaceRegionKind) {}
  350.  
  351. public:
  352.   void dumpToStream(raw_ostream &os) const override;
  353.  
  354.   static bool classof(const MemRegion *R) {
  355.     return R->getKind() == GlobalInternalSpaceRegionKind;
  356.   }
  357. };
  358.  
  359. class HeapSpaceRegion : public MemSpaceRegion {
  360.   friend class MemRegionManager;
  361.  
  362.   HeapSpaceRegion(MemRegionManager &mgr)
  363.       : MemSpaceRegion(mgr, HeapSpaceRegionKind) {}
  364.  
  365. public:
  366.   void dumpToStream(raw_ostream &os) const override;
  367.  
  368.   static bool classof(const MemRegion *R) {
  369.     return R->getKind() == HeapSpaceRegionKind;
  370.   }
  371. };
  372.  
  373. class UnknownSpaceRegion : public MemSpaceRegion {
  374.   friend class MemRegionManager;
  375.  
  376.   UnknownSpaceRegion(MemRegionManager &mgr)
  377.       : MemSpaceRegion(mgr, UnknownSpaceRegionKind) {}
  378.  
  379. public:
  380.   void dumpToStream(raw_ostream &os) const override;
  381.  
  382.   static bool classof(const MemRegion *R) {
  383.     return R->getKind() == UnknownSpaceRegionKind;
  384.   }
  385. };
  386.  
  387. class StackSpaceRegion : public MemSpaceRegion {
  388.   virtual void anchor();
  389.  
  390.   const StackFrameContext *SFC;
  391.  
  392. protected:
  393.   StackSpaceRegion(MemRegionManager &mgr, Kind k, const StackFrameContext *sfc)
  394.       : MemSpaceRegion(mgr, k), SFC(sfc) {
  395.     assert(classof(this));
  396.     assert(sfc);
  397.   }
  398.  
  399. public:
  400.   LLVM_ATTRIBUTE_RETURNS_NONNULL
  401.   const StackFrameContext *getStackFrame() const { return SFC; }
  402.  
  403.   void Profile(llvm::FoldingSetNodeID &ID) const override;
  404.  
  405.   static bool classof(const MemRegion *R) {
  406.     Kind k = R->getKind();
  407.     return k >= BEGIN_STACK_MEMSPACES && k <= END_STACK_MEMSPACES;
  408.   }
  409. };
  410.  
  411. class StackLocalsSpaceRegion : public StackSpaceRegion {
  412.   friend class MemRegionManager;
  413.  
  414.   StackLocalsSpaceRegion(MemRegionManager &mgr, const StackFrameContext *sfc)
  415.       : StackSpaceRegion(mgr, StackLocalsSpaceRegionKind, sfc) {}
  416.  
  417. public:
  418.   void dumpToStream(raw_ostream &os) const override;
  419.  
  420.   static bool classof(const MemRegion *R) {
  421.     return R->getKind() == StackLocalsSpaceRegionKind;
  422.   }
  423. };
  424.  
  425. class StackArgumentsSpaceRegion : public StackSpaceRegion {
  426. private:
  427.   friend class MemRegionManager;
  428.  
  429.   StackArgumentsSpaceRegion(MemRegionManager &mgr, const StackFrameContext *sfc)
  430.       : StackSpaceRegion(mgr, StackArgumentsSpaceRegionKind, sfc) {}
  431.  
  432. public:
  433.   void dumpToStream(raw_ostream &os) const override;
  434.  
  435.   static bool classof(const MemRegion *R) {
  436.     return R->getKind() == StackArgumentsSpaceRegionKind;
  437.   }
  438. };
  439.  
  440. /// SubRegion - A region that subsets another larger region.  Most regions
  441. ///  are subclasses of SubRegion.
  442. class SubRegion : public MemRegion {
  443.   virtual void anchor();
  444.  
  445. protected:
  446.   const MemRegion* superRegion;
  447.  
  448.   SubRegion(const MemRegion *sReg, Kind k) : MemRegion(k), superRegion(sReg) {
  449.     assert(classof(this));
  450.     assert(sReg);
  451.   }
  452.  
  453. public:
  454.   LLVM_ATTRIBUTE_RETURNS_NONNULL
  455.   const MemRegion* getSuperRegion() const {
  456.     return superRegion;
  457.   }
  458.  
  459.   MemRegionManager &getMemRegionManager() const override;
  460.  
  461.   bool isSubRegionOf(const MemRegion* R) const override;
  462.  
  463.   static bool classof(const MemRegion* R) {
  464.     return R->getKind() > END_MEMSPACES;
  465.   }
  466. };
  467.  
  468. //===----------------------------------------------------------------------===//
  469. // MemRegion subclasses.
  470. //===----------------------------------------------------------------------===//
  471.  
  472. /// AllocaRegion - A region that represents an untyped blob of bytes created
  473. ///  by a call to 'alloca'.
  474. class AllocaRegion : public SubRegion {
  475.   friend class MemRegionManager;
  476.  
  477.   // Block counter. Used to distinguish different pieces of memory allocated by
  478.   // alloca at the same call site.
  479.   unsigned Cnt;
  480.  
  481.   const Expr *Ex;
  482.  
  483.   AllocaRegion(const Expr *ex, unsigned cnt, const MemSpaceRegion *superRegion)
  484.       : SubRegion(superRegion, AllocaRegionKind), Cnt(cnt), Ex(ex) {
  485.     assert(Ex);
  486.   }
  487.  
  488.   static void ProfileRegion(llvm::FoldingSetNodeID& ID, const Expr *Ex,
  489.                             unsigned Cnt, const MemRegion *superRegion);
  490.  
  491. public:
  492.   LLVM_ATTRIBUTE_RETURNS_NONNULL
  493.   const Expr *getExpr() const { return Ex; }
  494.  
  495.   bool isBoundable() const override { return true; }
  496.  
  497.   void Profile(llvm::FoldingSetNodeID& ID) const override;
  498.  
  499.   void dumpToStream(raw_ostream &os) const override;
  500.  
  501.   static bool classof(const MemRegion* R) {
  502.     return R->getKind() == AllocaRegionKind;
  503.   }
  504. };
  505.  
  506. /// TypedRegion - An abstract class representing regions that are typed.
  507. class TypedRegion : public SubRegion {
  508.   void anchor() override;
  509.  
  510. protected:
  511.   TypedRegion(const MemRegion *sReg, Kind k) : SubRegion(sReg, k) {
  512.     assert(classof(this));
  513.   }
  514.  
  515. public:
  516.   virtual QualType getLocationType() const = 0;
  517.  
  518.   QualType getDesugaredLocationType(ASTContext &Context) const {
  519.     return getLocationType().getDesugaredType(Context);
  520.   }
  521.  
  522.   bool isBoundable() const override { return true; }
  523.  
  524.   static bool classof(const MemRegion* R) {
  525.     unsigned k = R->getKind();
  526.     return k >= BEGIN_TYPED_REGIONS && k <= END_TYPED_REGIONS;
  527.   }
  528. };
  529.  
  530. /// TypedValueRegion - An abstract class representing regions having a typed value.
  531. class TypedValueRegion : public TypedRegion {
  532.   void anchor() override;
  533.  
  534. protected:
  535.   TypedValueRegion(const MemRegion* sReg, Kind k) : TypedRegion(sReg, k) {
  536.     assert(classof(this));
  537.   }
  538.  
  539. public:
  540.   virtual QualType getValueType() const = 0;
  541.  
  542.   QualType getLocationType() const override {
  543.     // FIXME: We can possibly optimize this later to cache this value.
  544.     QualType T = getValueType();
  545.     ASTContext &ctx = getContext();
  546.     if (T->getAs<ObjCObjectType>())
  547.       return ctx.getObjCObjectPointerType(T);
  548.     return ctx.getPointerType(getValueType());
  549.   }
  550.  
  551.   QualType getDesugaredValueType(ASTContext &Context) const {
  552.     QualType T = getValueType();
  553.     return T.getTypePtrOrNull() ? T.getDesugaredType(Context) : T;
  554.   }
  555.  
  556.   static bool classof(const MemRegion* R) {
  557.     unsigned k = R->getKind();
  558.     return k >= BEGIN_TYPED_VALUE_REGIONS && k <= END_TYPED_VALUE_REGIONS;
  559.   }
  560. };
  561.  
  562. class CodeTextRegion : public TypedRegion {
  563.   void anchor() override;
  564.  
  565. protected:
  566.   CodeTextRegion(const MemSpaceRegion *sreg, Kind k) : TypedRegion(sreg, k) {
  567.     assert(classof(this));
  568.   }
  569.  
  570. public:
  571.   bool isBoundable() const override { return false; }
  572.  
  573.   static bool classof(const MemRegion* R) {
  574.     Kind k = R->getKind();
  575.     return k >= BEGIN_CODE_TEXT_REGIONS && k <= END_CODE_TEXT_REGIONS;
  576.   }
  577. };
  578.  
  579. /// FunctionCodeRegion - A region that represents code texts of function.
  580. class FunctionCodeRegion : public CodeTextRegion {
  581.   friend class MemRegionManager;
  582.  
  583.   const NamedDecl *FD;
  584.  
  585.   FunctionCodeRegion(const NamedDecl *fd, const CodeSpaceRegion* sreg)
  586.       : CodeTextRegion(sreg, FunctionCodeRegionKind), FD(fd) {
  587.     assert(isa<ObjCMethodDecl>(fd) || isa<FunctionDecl>(fd));
  588.   }
  589.  
  590.   static void ProfileRegion(llvm::FoldingSetNodeID& ID, const NamedDecl *FD,
  591.                             const MemRegion*);
  592.  
  593. public:
  594.   QualType getLocationType() const override {
  595.     const ASTContext &Ctx = getContext();
  596.     if (const auto *D = dyn_cast<FunctionDecl>(FD)) {
  597.       return Ctx.getPointerType(D->getType());
  598.     }
  599.  
  600.     assert(isa<ObjCMethodDecl>(FD));
  601.     assert(false && "Getting the type of ObjCMethod is not supported yet");
  602.  
  603.     // TODO: We might want to return a different type here (ex: id (*ty)(...))
  604.     //       depending on how it is used.
  605.     return {};
  606.   }
  607.  
  608.   const NamedDecl *getDecl() const {
  609.     return FD;
  610.   }
  611.  
  612.   void dumpToStream(raw_ostream &os) const override;
  613.  
  614.   void Profile(llvm::FoldingSetNodeID& ID) const override;
  615.  
  616.   static bool classof(const MemRegion* R) {
  617.     return R->getKind() == FunctionCodeRegionKind;
  618.   }
  619. };
  620.  
  621. /// BlockCodeRegion - A region that represents code texts of blocks (closures).
  622. ///  Blocks are represented with two kinds of regions.  BlockCodeRegions
  623. ///  represent the "code", while BlockDataRegions represent instances of blocks,
  624. ///  which correspond to "code+data".  The distinction is important, because
  625. ///  like a closure a block captures the values of externally referenced
  626. ///  variables.
  627. class BlockCodeRegion : public CodeTextRegion {
  628.   friend class MemRegionManager;
  629.  
  630.   const BlockDecl *BD;
  631.   AnalysisDeclContext *AC;
  632.   CanQualType locTy;
  633.  
  634.   BlockCodeRegion(const BlockDecl *bd, CanQualType lTy,
  635.                   AnalysisDeclContext *ac, const CodeSpaceRegion* sreg)
  636.       : CodeTextRegion(sreg, BlockCodeRegionKind), BD(bd), AC(ac), locTy(lTy) {
  637.     assert(bd);
  638.     assert(ac);
  639.     assert(lTy->getTypePtr()->isBlockPointerType());
  640.   }
  641.  
  642.   static void ProfileRegion(llvm::FoldingSetNodeID& ID, const BlockDecl *BD,
  643.                             CanQualType, const AnalysisDeclContext*,
  644.                             const MemRegion*);
  645.  
  646. public:
  647.   QualType getLocationType() const override {
  648.     return locTy;
  649.   }
  650.  
  651.   LLVM_ATTRIBUTE_RETURNS_NONNULL
  652.   const BlockDecl *getDecl() const {
  653.     return BD;
  654.   }
  655.  
  656.   LLVM_ATTRIBUTE_RETURNS_NONNULL
  657.   AnalysisDeclContext *getAnalysisDeclContext() const { return AC; }
  658.  
  659.   void dumpToStream(raw_ostream &os) const override;
  660.  
  661.   void Profile(llvm::FoldingSetNodeID& ID) const override;
  662.  
  663.   static bool classof(const MemRegion* R) {
  664.     return R->getKind() == BlockCodeRegionKind;
  665.   }
  666. };
  667.  
  668. /// BlockDataRegion - A region that represents a block instance.
  669. ///  Blocks are represented with two kinds of regions.  BlockCodeRegions
  670. ///  represent the "code", while BlockDataRegions represent instances of blocks,
  671. ///  which correspond to "code+data".  The distinction is important, because
  672. ///  like a closure a block captures the values of externally referenced
  673. ///  variables.
  674. class BlockDataRegion : public TypedRegion {
  675.   friend class MemRegionManager;
  676.  
  677.   const BlockCodeRegion *BC;
  678.   const LocationContext *LC; // Can be null
  679.   unsigned BlockCount;
  680.   void *ReferencedVars = nullptr;
  681.   void *OriginalVars = nullptr;
  682.  
  683.   BlockDataRegion(const BlockCodeRegion *bc, const LocationContext *lc,
  684.                   unsigned count, const MemSpaceRegion *sreg)
  685.       : TypedRegion(sreg, BlockDataRegionKind), BC(bc), LC(lc),
  686.         BlockCount(count) {
  687.     assert(bc);
  688.     assert(bc->getDecl());
  689.     assert(lc);
  690.     assert(isa<GlobalImmutableSpaceRegion>(sreg) ||
  691.            isa<StackLocalsSpaceRegion>(sreg) ||
  692.            isa<UnknownSpaceRegion>(sreg));
  693.   }
  694.  
  695.   static void ProfileRegion(llvm::FoldingSetNodeID&, const BlockCodeRegion *,
  696.                             const LocationContext *, unsigned,
  697.                             const MemRegion *);
  698.  
  699. public:
  700.   LLVM_ATTRIBUTE_RETURNS_NONNULL
  701.   const BlockCodeRegion *getCodeRegion() const { return BC; }
  702.  
  703.   LLVM_ATTRIBUTE_RETURNS_NONNULL
  704.   const BlockDecl *getDecl() const { return BC->getDecl(); }
  705.  
  706.   QualType getLocationType() const override { return BC->getLocationType(); }
  707.  
  708.   class referenced_vars_iterator {
  709.     const MemRegion * const *R;
  710.     const MemRegion * const *OriginalR;
  711.  
  712.   public:
  713.     explicit referenced_vars_iterator(const MemRegion * const *r,
  714.                                       const MemRegion * const *originalR)
  715.         : R(r), OriginalR(originalR) {}
  716.  
  717.     LLVM_ATTRIBUTE_RETURNS_NONNULL
  718.     const VarRegion *getCapturedRegion() const {
  719.       return cast<VarRegion>(*R);
  720.     }
  721.  
  722.     LLVM_ATTRIBUTE_RETURNS_NONNULL
  723.     const VarRegion *getOriginalRegion() const {
  724.       return cast<VarRegion>(*OriginalR);
  725.     }
  726.  
  727.     bool operator==(const referenced_vars_iterator &I) const {
  728.       assert((R == nullptr) == (I.R == nullptr));
  729.       return I.R == R;
  730.     }
  731.  
  732.     bool operator!=(const referenced_vars_iterator &I) const {
  733.       assert((R == nullptr) == (I.R == nullptr));
  734.       return I.R != R;
  735.     }
  736.  
  737.     referenced_vars_iterator &operator++() {
  738.       ++R;
  739.       ++OriginalR;
  740.       return *this;
  741.     }
  742.   };
  743.  
  744.   /// Return the original region for a captured region, if
  745.   /// one exists. It might return null.
  746.   const VarRegion *getOriginalRegion(const VarRegion *VR) const;
  747.  
  748.   referenced_vars_iterator referenced_vars_begin() const;
  749.   referenced_vars_iterator referenced_vars_end() const;
  750.  
  751.   void dumpToStream(raw_ostream &os) const override;
  752.  
  753.   void Profile(llvm::FoldingSetNodeID& ID) const override;
  754.  
  755.   static bool classof(const MemRegion* R) {
  756.     return R->getKind() == BlockDataRegionKind;
  757.   }
  758.  
  759. private:
  760.   void LazyInitializeReferencedVars();
  761.   std::pair<const VarRegion *, const VarRegion *>
  762.   getCaptureRegions(const VarDecl *VD);
  763. };
  764.  
  765. /// SymbolicRegion - A special, "non-concrete" region. Unlike other region
  766. ///  classes, SymbolicRegion represents a region that serves as an alias for
  767. ///  either a real region, a NULL pointer, etc.  It essentially is used to
  768. ///  map the concept of symbolic values into the domain of regions.  Symbolic
  769. ///  regions do not need to be typed.
  770. class SymbolicRegion : public SubRegion {
  771.   friend class MemRegionManager;
  772.  
  773.   const SymbolRef sym;
  774.  
  775.   SymbolicRegion(const SymbolRef s, const MemSpaceRegion *sreg)
  776.       : SubRegion(sreg, SymbolicRegionKind), sym(s) {
  777.     // Because pointer arithmetic is represented by ElementRegion layers,
  778.     // the base symbol here should not contain any arithmetic.
  779.     assert(s && isa<SymbolData>(s));
  780.     assert(s->getType()->isAnyPointerType() ||
  781.            s->getType()->isReferenceType() ||
  782.            s->getType()->isBlockPointerType());
  783.     assert(isa<UnknownSpaceRegion>(sreg) || isa<HeapSpaceRegion>(sreg) ||
  784.            isa<GlobalSystemSpaceRegion>(sreg));
  785.   }
  786.  
  787. public:
  788.   /// It might return null.
  789.   SymbolRef getSymbol() const { return sym; }
  790.  
  791.   /// Gets the type of the wrapped symbol.
  792.   /// This type might not be accurate at all times - it's just our best guess.
  793.   /// Consider these cases:
  794.   ///   void foo(void *data, char *str, base *obj) {...}
  795.   /// The type of the pointee of `data` is of course not `void`, yet that's our
  796.   /// best guess. `str` might point to any object and `obj` might point to some
  797.   /// derived instance. `TypedRegions` other hand are representing the cases
  798.   /// when we actually know their types.
  799.   QualType getPointeeStaticType() const {
  800.     return sym->getType()->getPointeeType();
  801.   }
  802.  
  803.   bool isBoundable() const override { return true; }
  804.  
  805.   void Profile(llvm::FoldingSetNodeID& ID) const override;
  806.  
  807.   static void ProfileRegion(llvm::FoldingSetNodeID& ID,
  808.                             SymbolRef sym,
  809.                             const MemRegion* superRegion);
  810.  
  811.   void dumpToStream(raw_ostream &os) const override;
  812.  
  813.   static bool classof(const MemRegion* R) {
  814.     return R->getKind() == SymbolicRegionKind;
  815.   }
  816. };
  817.  
  818. /// StringRegion - Region associated with a StringLiteral.
  819. class StringRegion : public TypedValueRegion {
  820.   friend class MemRegionManager;
  821.  
  822.   const StringLiteral *Str;
  823.  
  824.   StringRegion(const StringLiteral *str, const GlobalInternalSpaceRegion *sreg)
  825.       : TypedValueRegion(sreg, StringRegionKind), Str(str) {
  826.     assert(str);
  827.   }
  828.  
  829.   static void ProfileRegion(llvm::FoldingSetNodeID &ID,
  830.                             const StringLiteral *Str,
  831.                             const MemRegion *superRegion);
  832.  
  833. public:
  834.   LLVM_ATTRIBUTE_RETURNS_NONNULL
  835.   const StringLiteral *getStringLiteral() const { return Str; }
  836.  
  837.   QualType getValueType() const override { return Str->getType(); }
  838.  
  839.   bool isBoundable() const override { return false; }
  840.  
  841.   void Profile(llvm::FoldingSetNodeID& ID) const override {
  842.     ProfileRegion(ID, Str, superRegion);
  843.   }
  844.  
  845.   void dumpToStream(raw_ostream &os) const override;
  846.  
  847.   static bool classof(const MemRegion* R) {
  848.     return R->getKind() == StringRegionKind;
  849.   }
  850. };
  851.  
  852. /// The region associated with an ObjCStringLiteral.
  853. class ObjCStringRegion : public TypedValueRegion {
  854.   friend class MemRegionManager;
  855.  
  856.   const ObjCStringLiteral *Str;
  857.  
  858.   ObjCStringRegion(const ObjCStringLiteral *str,
  859.                    const GlobalInternalSpaceRegion *sreg)
  860.       : TypedValueRegion(sreg, ObjCStringRegionKind), Str(str) {
  861.     assert(str);
  862.   }
  863.  
  864.   static void ProfileRegion(llvm::FoldingSetNodeID &ID,
  865.                             const ObjCStringLiteral *Str,
  866.                             const MemRegion *superRegion);
  867.  
  868. public:
  869.   LLVM_ATTRIBUTE_RETURNS_NONNULL
  870.   const ObjCStringLiteral *getObjCStringLiteral() const { return Str; }
  871.  
  872.   QualType getValueType() const override { return Str->getType(); }
  873.  
  874.   bool isBoundable() const override { return false; }
  875.  
  876.   void Profile(llvm::FoldingSetNodeID& ID) const override {
  877.     ProfileRegion(ID, Str, superRegion);
  878.   }
  879.  
  880.   void dumpToStream(raw_ostream &os) const override;
  881.  
  882.   static bool classof(const MemRegion* R) {
  883.     return R->getKind() == ObjCStringRegionKind;
  884.   }
  885. };
  886.  
  887. /// CompoundLiteralRegion - A memory region representing a compound literal.
  888. ///   Compound literals are essentially temporaries that are stack allocated
  889. ///   or in the global constant pool.
  890. class CompoundLiteralRegion : public TypedValueRegion {
  891.   friend class MemRegionManager;
  892.  
  893.   const CompoundLiteralExpr *CL;
  894.  
  895.   CompoundLiteralRegion(const CompoundLiteralExpr *cl,
  896.                         const MemSpaceRegion *sReg)
  897.       : TypedValueRegion(sReg, CompoundLiteralRegionKind), CL(cl) {
  898.     assert(cl);
  899.     assert(isa<GlobalInternalSpaceRegion>(sReg) ||
  900.            isa<StackLocalsSpaceRegion>(sReg));
  901.   }
  902.  
  903.   static void ProfileRegion(llvm::FoldingSetNodeID& ID,
  904.                             const CompoundLiteralExpr *CL,
  905.                             const MemRegion* superRegion);
  906.  
  907. public:
  908.   QualType getValueType() const override { return CL->getType(); }
  909.  
  910.   bool isBoundable() const override { return !CL->isFileScope(); }
  911.  
  912.   void Profile(llvm::FoldingSetNodeID& ID) const override;
  913.  
  914.   void dumpToStream(raw_ostream &os) const override;
  915.  
  916.   LLVM_ATTRIBUTE_RETURNS_NONNULL
  917.   const CompoundLiteralExpr *getLiteralExpr() const { return CL; }
  918.  
  919.   static bool classof(const MemRegion* R) {
  920.     return R->getKind() == CompoundLiteralRegionKind;
  921.   }
  922. };
  923.  
  924. class DeclRegion : public TypedValueRegion {
  925. protected:
  926.   DeclRegion(const MemRegion *sReg, Kind k) : TypedValueRegion(sReg, k) {
  927.     assert(classof(this));
  928.   }
  929.  
  930. public:
  931.   // TODO what does this return?
  932.   virtual const ValueDecl *getDecl() const = 0;
  933.  
  934.   static bool classof(const MemRegion* R) {
  935.     unsigned k = R->getKind();
  936.     return k >= BEGIN_DECL_REGIONS && k <= END_DECL_REGIONS;
  937.   }
  938. };
  939.  
  940. class VarRegion : public DeclRegion {
  941.   friend class MemRegionManager;
  942.  
  943. protected:
  944.   // Constructors and protected methods.
  945.   VarRegion(const MemRegion *sReg, Kind k) : DeclRegion(sReg, k) {
  946.     // VarRegion appears in unknown space when it's a block variable as seen
  947.     // from a block using it, when this block is analyzed at top-level.
  948.     // Other block variables appear within block data regions,
  949.     // which, unlike everything else on this list, are not memory spaces.
  950.     assert(isa<GlobalsSpaceRegion>(sReg) || isa<StackSpaceRegion>(sReg) ||
  951.            isa<BlockDataRegion>(sReg) || isa<UnknownSpaceRegion>(sReg));
  952.   }
  953.  
  954. public:
  955.   // TODO what does this return?
  956.   const VarDecl *getDecl() const override = 0;
  957.  
  958.   /// It might return null.
  959.   const StackFrameContext *getStackFrame() const;
  960.  
  961.   QualType getValueType() const override {
  962.     // FIXME: We can cache this if needed.
  963.     return getDecl()->getType();
  964.   }
  965.  
  966.   static bool classof(const MemRegion *R) {
  967.     unsigned k = R->getKind();
  968.     return k >= BEGIN_VAR_REGIONS && k <= END_VAR_REGIONS;
  969.   }
  970. };
  971.  
  972. class NonParamVarRegion : public VarRegion {
  973.   friend class MemRegionManager;
  974.  
  975.   const VarDecl *VD;
  976.  
  977.   // Constructors and private methods.
  978.   NonParamVarRegion(const VarDecl *vd, const MemRegion *sReg)
  979.       : VarRegion(sReg, NonParamVarRegionKind), VD(vd) {
  980.     // VarRegion appears in unknown space when it's a block variable as seen
  981.     // from a block using it, when this block is analyzed at top-level.
  982.     // Other block variables appear within block data regions,
  983.     // which, unlike everything else on this list, are not memory spaces.
  984.     assert(isa<GlobalsSpaceRegion>(sReg) || isa<StackSpaceRegion>(sReg) ||
  985.            isa<BlockDataRegion>(sReg) || isa<UnknownSpaceRegion>(sReg));
  986.     assert(vd);
  987.   }
  988.  
  989.   static void ProfileRegion(llvm::FoldingSetNodeID &ID, const VarDecl *VD,
  990.                             const MemRegion *superRegion);
  991.  
  992. public:
  993.   void Profile(llvm::FoldingSetNodeID &ID) const override;
  994.  
  995.   LLVM_ATTRIBUTE_RETURNS_NONNULL
  996.   const VarDecl *getDecl() const override { return VD; }
  997.  
  998.   QualType getValueType() const override {
  999.     // FIXME: We can cache this if needed.
  1000.     return getDecl()->getType();
  1001.   }
  1002.  
  1003.   void dumpToStream(raw_ostream &os) const override;
  1004.  
  1005.   bool canPrintPrettyAsExpr() const override;
  1006.  
  1007.   void printPrettyAsExpr(raw_ostream &os) const override;
  1008.  
  1009.   static bool classof(const MemRegion* R) {
  1010.     return R->getKind() == NonParamVarRegionKind;
  1011.   }
  1012. };
  1013.  
  1014. /// ParamVarRegion - Represents a region for paremters. Only parameters of the
  1015. /// function in the current stack frame are represented as `ParamVarRegion`s.
  1016. /// Parameters of top-level analyzed functions as well as captured paremeters
  1017. /// by lambdas and blocks are repesented as `VarRegion`s.
  1018.  
  1019. // FIXME: `ParamVarRegion` only supports parameters of functions, C++
  1020. // constructors, blocks and Objective-C methods with existing `Decl`. Upon
  1021. // implementing stack frame creations for functions without decl (functions
  1022. // passed by unknown function pointer) methods of `ParamVarRegion` must be
  1023. // updated.
  1024. class ParamVarRegion : public VarRegion {
  1025.   friend class MemRegionManager;
  1026.  
  1027.   const Expr *OriginExpr;
  1028.   unsigned Index;
  1029.  
  1030.   ParamVarRegion(const Expr *OE, unsigned Idx, const MemRegion *SReg)
  1031.       : VarRegion(SReg, ParamVarRegionKind), OriginExpr(OE), Index(Idx) {
  1032.     assert(!cast<StackSpaceRegion>(SReg)->getStackFrame()->inTopFrame());
  1033.     assert(OriginExpr);
  1034.   }
  1035.  
  1036.   static void ProfileRegion(llvm::FoldingSetNodeID &ID, const Expr *OE,
  1037.                             unsigned Idx, const MemRegion *SReg);
  1038.  
  1039. public:
  1040.   LLVM_ATTRIBUTE_RETURNS_NONNULL
  1041.   const Expr *getOriginExpr() const { return OriginExpr; }
  1042.   unsigned getIndex() const { return Index; }
  1043.  
  1044.   void Profile(llvm::FoldingSetNodeID& ID) const override;
  1045.  
  1046.   void dumpToStream(raw_ostream &os) const override;
  1047.  
  1048.   QualType getValueType() const override;
  1049.  
  1050.   /// TODO: What does this return?
  1051.   const ParmVarDecl *getDecl() const override;
  1052.  
  1053.   bool canPrintPrettyAsExpr() const override;
  1054.   void printPrettyAsExpr(raw_ostream &os) const override;
  1055.  
  1056.   static bool classof(const MemRegion *R) {
  1057.     return R->getKind() == ParamVarRegionKind;
  1058.   }
  1059. };
  1060.  
  1061. /// CXXThisRegion - Represents the region for the implicit 'this' parameter
  1062. ///  in a call to a C++ method.  This region doesn't represent the object
  1063. ///  referred to by 'this', but rather 'this' itself.
  1064. class CXXThisRegion : public TypedValueRegion {
  1065.   friend class MemRegionManager;
  1066.  
  1067.   CXXThisRegion(const PointerType *thisPointerTy,
  1068.                 const StackArgumentsSpaceRegion *sReg)
  1069.       : TypedValueRegion(sReg, CXXThisRegionKind),
  1070.         ThisPointerTy(thisPointerTy) {
  1071.     assert(ThisPointerTy->getPointeeType()->getAsCXXRecordDecl() &&
  1072.            "Invalid region type!");
  1073.   }
  1074.  
  1075.   static void ProfileRegion(llvm::FoldingSetNodeID &ID,
  1076.                             const PointerType *PT,
  1077.                             const MemRegion *sReg);
  1078.  
  1079. public:
  1080.   void Profile(llvm::FoldingSetNodeID &ID) const override;
  1081.  
  1082.   QualType getValueType() const override {
  1083.     return QualType(ThisPointerTy, 0);
  1084.   }
  1085.  
  1086.   void dumpToStream(raw_ostream &os) const override;
  1087.  
  1088.   static bool classof(const MemRegion* R) {
  1089.     return R->getKind() == CXXThisRegionKind;
  1090.   }
  1091.  
  1092. private:
  1093.   const PointerType *ThisPointerTy;
  1094. };
  1095.  
  1096. class FieldRegion : public DeclRegion {
  1097.   friend class MemRegionManager;
  1098.  
  1099.   const FieldDecl *FD;
  1100.  
  1101.   FieldRegion(const FieldDecl *fd, const SubRegion *sReg)
  1102.       : DeclRegion(sReg, FieldRegionKind), FD(fd) {
  1103.     assert(FD);
  1104.   }
  1105.  
  1106.   static void ProfileRegion(llvm::FoldingSetNodeID &ID, const FieldDecl *FD,
  1107.                             const MemRegion* superRegion) {
  1108.     ID.AddInteger(static_cast<unsigned>(FieldRegionKind));
  1109.     ID.AddPointer(FD);
  1110.     ID.AddPointer(superRegion);
  1111.   }
  1112.  
  1113. public:
  1114.   LLVM_ATTRIBUTE_RETURNS_NONNULL
  1115.   const FieldDecl *getDecl() const override { return FD; }
  1116.  
  1117.   void Profile(llvm::FoldingSetNodeID &ID) const override;
  1118.  
  1119.   QualType getValueType() const override {
  1120.     // FIXME: We can cache this if needed.
  1121.     return getDecl()->getType();
  1122.   }
  1123.  
  1124.   void dumpToStream(raw_ostream &os) const override;
  1125.  
  1126.   bool canPrintPretty() const override;
  1127.   void printPretty(raw_ostream &os) const override;
  1128.   bool canPrintPrettyAsExpr() const override;
  1129.   void printPrettyAsExpr(raw_ostream &os) const override;
  1130.  
  1131.   static bool classof(const MemRegion* R) {
  1132.     return R->getKind() == FieldRegionKind;
  1133.   }
  1134. };
  1135.  
  1136. class ObjCIvarRegion : public DeclRegion {
  1137.   friend class MemRegionManager;
  1138.  
  1139.   const ObjCIvarDecl *IVD;
  1140.  
  1141.   ObjCIvarRegion(const ObjCIvarDecl *ivd, const SubRegion *sReg);
  1142.  
  1143.   static void ProfileRegion(llvm::FoldingSetNodeID& ID, const ObjCIvarDecl *ivd,
  1144.                             const MemRegion* superRegion);
  1145.  
  1146. public:
  1147.   LLVM_ATTRIBUTE_RETURNS_NONNULL
  1148.   const ObjCIvarDecl *getDecl() const override;
  1149.  
  1150.   void Profile(llvm::FoldingSetNodeID& ID) const override;
  1151.  
  1152.   QualType getValueType() const override;
  1153.  
  1154.   bool canPrintPrettyAsExpr() const override;
  1155.   void printPrettyAsExpr(raw_ostream &os) const override;
  1156.  
  1157.   void dumpToStream(raw_ostream &os) const override;
  1158.  
  1159.   static bool classof(const MemRegion* R) {
  1160.     return R->getKind() == ObjCIvarRegionKind;
  1161.   }
  1162. };
  1163.  
  1164. //===----------------------------------------------------------------------===//
  1165. // Auxiliary data classes for use with MemRegions.
  1166. //===----------------------------------------------------------------------===//
  1167.  
  1168. class RegionRawOffset {
  1169.   friend class ElementRegion;
  1170.  
  1171.   const MemRegion *Region;
  1172.   CharUnits Offset;
  1173.  
  1174.   RegionRawOffset(const MemRegion* reg, CharUnits offset = CharUnits::Zero())
  1175.       : Region(reg), Offset(offset) {}
  1176.  
  1177. public:
  1178.   // FIXME: Eventually support symbolic offsets.
  1179.   CharUnits getOffset() const { return Offset; }
  1180.  
  1181.   // It might return null.
  1182.   const MemRegion *getRegion() const { return Region; }
  1183.  
  1184.   void dumpToStream(raw_ostream &os) const;
  1185.   void dump() const;
  1186. };
  1187.  
  1188. /// ElementRegion is used to represent both array elements and casts.
  1189. class ElementRegion : public TypedValueRegion {
  1190.   friend class MemRegionManager;
  1191.  
  1192.   QualType ElementType;
  1193.   NonLoc Index;
  1194.  
  1195.   ElementRegion(QualType elementType, NonLoc Idx, const SubRegion *sReg)
  1196.       : TypedValueRegion(sReg, ElementRegionKind), ElementType(elementType),
  1197.         Index(Idx) {
  1198.     assert((!isa<nonloc::ConcreteInt>(Idx) ||
  1199.             Idx.castAs<nonloc::ConcreteInt>().getValue().isSigned()) &&
  1200.            "The index must be signed");
  1201.     assert(!elementType.isNull() && !elementType->isVoidType() &&
  1202.            "Invalid region type!");
  1203.   }
  1204.  
  1205.   static void ProfileRegion(llvm::FoldingSetNodeID& ID, QualType elementType,
  1206.                             SVal Idx, const MemRegion* superRegion);
  1207.  
  1208. public:
  1209.   NonLoc getIndex() const { return Index; }
  1210.  
  1211.   QualType getValueType() const override { return ElementType; }
  1212.  
  1213.   QualType getElementType() const { return ElementType; }
  1214.  
  1215.   /// Compute the offset within the array. The array might also be a subobject.
  1216.   RegionRawOffset getAsArrayOffset() const;
  1217.  
  1218.   void dumpToStream(raw_ostream &os) const override;
  1219.  
  1220.   void Profile(llvm::FoldingSetNodeID& ID) const override;
  1221.  
  1222.   static bool classof(const MemRegion* R) {
  1223.     return R->getKind() == ElementRegionKind;
  1224.   }
  1225. };
  1226.  
  1227. // C++ temporary object associated with an expression.
  1228. class CXXTempObjectRegion : public TypedValueRegion {
  1229.   friend class MemRegionManager;
  1230.  
  1231.   Expr const *Ex;
  1232.  
  1233.   CXXTempObjectRegion(Expr const *E, MemSpaceRegion const *sReg)
  1234.       : TypedValueRegion(sReg, CXXTempObjectRegionKind), Ex(E) {
  1235.     assert(E);
  1236.     assert(isa<StackLocalsSpaceRegion>(sReg) ||
  1237.            isa<GlobalInternalSpaceRegion>(sReg));
  1238.   }
  1239.  
  1240.   static void ProfileRegion(llvm::FoldingSetNodeID &ID,
  1241.                             Expr const *E, const MemRegion *sReg);
  1242.  
  1243. public:
  1244.   LLVM_ATTRIBUTE_RETURNS_NONNULL
  1245.   const Expr *getExpr() const { return Ex; }
  1246.  
  1247.   QualType getValueType() const override { return Ex->getType(); }
  1248.  
  1249.   void dumpToStream(raw_ostream &os) const override;
  1250.  
  1251.   void Profile(llvm::FoldingSetNodeID &ID) const override;
  1252.  
  1253.   static bool classof(const MemRegion* R) {
  1254.     return R->getKind() == CXXTempObjectRegionKind;
  1255.   }
  1256. };
  1257.  
  1258. // CXXBaseObjectRegion represents a base object within a C++ object. It is
  1259. // identified by the base class declaration and the region of its parent object.
  1260. class CXXBaseObjectRegion : public TypedValueRegion {
  1261.   friend class MemRegionManager;
  1262.  
  1263.   llvm::PointerIntPair<const CXXRecordDecl *, 1, bool> Data;
  1264.  
  1265.   CXXBaseObjectRegion(const CXXRecordDecl *RD, bool IsVirtual,
  1266.                       const SubRegion *SReg)
  1267.       : TypedValueRegion(SReg, CXXBaseObjectRegionKind), Data(RD, IsVirtual) {
  1268.     assert(RD);
  1269.   }
  1270.  
  1271.   static void ProfileRegion(llvm::FoldingSetNodeID &ID, const CXXRecordDecl *RD,
  1272.                             bool IsVirtual, const MemRegion *SReg);
  1273.  
  1274. public:
  1275.   LLVM_ATTRIBUTE_RETURNS_NONNULL
  1276.   const CXXRecordDecl *getDecl() const { return Data.getPointer(); }
  1277.   bool isVirtual() const { return Data.getInt(); }
  1278.  
  1279.   QualType getValueType() const override;
  1280.  
  1281.   void dumpToStream(raw_ostream &os) const override;
  1282.  
  1283.   void Profile(llvm::FoldingSetNodeID &ID) const override;
  1284.  
  1285.   bool canPrintPrettyAsExpr() const override;
  1286.  
  1287.   void printPrettyAsExpr(raw_ostream &os) const override;
  1288.  
  1289.   static bool classof(const MemRegion *region) {
  1290.     return region->getKind() == CXXBaseObjectRegionKind;
  1291.   }
  1292. };
  1293.  
  1294. // CXXDerivedObjectRegion represents a derived-class object that surrounds
  1295. // a C++ object. It is identified by the derived class declaration and the
  1296. // region of its parent object. It is a bit counter-intuitive (but not otherwise
  1297. // unseen) that this region represents a larger segment of memory that its
  1298. // super-region.
  1299. class CXXDerivedObjectRegion : public TypedValueRegion {
  1300.   friend class MemRegionManager;
  1301.  
  1302.   const CXXRecordDecl *DerivedD;
  1303.  
  1304.   CXXDerivedObjectRegion(const CXXRecordDecl *DerivedD, const SubRegion *SReg)
  1305.       : TypedValueRegion(SReg, CXXDerivedObjectRegionKind), DerivedD(DerivedD) {
  1306.     assert(DerivedD);
  1307.     // In case of a concrete region, it should always be possible to model
  1308.     // the base-to-derived cast by undoing a previous derived-to-base cast,
  1309.     // otherwise the cast is most likely ill-formed.
  1310.     assert(SReg->getSymbolicBase() &&
  1311.            "Should have unwrapped a base region instead!");
  1312.   }
  1313.  
  1314.   static void ProfileRegion(llvm::FoldingSetNodeID &ID, const CXXRecordDecl *RD,
  1315.                             const MemRegion *SReg);
  1316.  
  1317. public:
  1318.   LLVM_ATTRIBUTE_RETURNS_NONNULL
  1319.   const CXXRecordDecl *getDecl() const { return DerivedD; }
  1320.  
  1321.   QualType getValueType() const override;
  1322.  
  1323.   void dumpToStream(raw_ostream &os) const override;
  1324.  
  1325.   void Profile(llvm::FoldingSetNodeID &ID) const override;
  1326.  
  1327.   bool canPrintPrettyAsExpr() const override;
  1328.  
  1329.   void printPrettyAsExpr(raw_ostream &os) const override;
  1330.  
  1331.   static bool classof(const MemRegion *region) {
  1332.     return region->getKind() == CXXDerivedObjectRegionKind;
  1333.   }
  1334. };
  1335.  
  1336. template<typename RegionTy>
  1337. const RegionTy* MemRegion::getAs() const {
  1338.   if (const auto *RT = dyn_cast<RegionTy>(this))
  1339.     return RT;
  1340.  
  1341.   return nullptr;
  1342. }
  1343.  
  1344. template <typename RegionTy>
  1345. LLVM_ATTRIBUTE_RETURNS_NONNULL const RegionTy *MemRegion::castAs() const {
  1346.   return cast<RegionTy>(this);
  1347. }
  1348.  
  1349. //===----------------------------------------------------------------------===//
  1350. // MemRegionManager - Factory object for creating regions.
  1351. //===----------------------------------------------------------------------===//
  1352.  
  1353. class MemRegionManager {
  1354.   ASTContext &Ctx;
  1355.   llvm::BumpPtrAllocator& A;
  1356.  
  1357.   llvm::FoldingSet<MemRegion> Regions;
  1358.  
  1359.   GlobalInternalSpaceRegion *InternalGlobals = nullptr;
  1360.   GlobalSystemSpaceRegion *SystemGlobals = nullptr;
  1361.   GlobalImmutableSpaceRegion *ImmutableGlobals = nullptr;
  1362.  
  1363.   llvm::DenseMap<const StackFrameContext *, StackLocalsSpaceRegion *>
  1364.     StackLocalsSpaceRegions;
  1365.   llvm::DenseMap<const StackFrameContext *, StackArgumentsSpaceRegion *>
  1366.     StackArgumentsSpaceRegions;
  1367.   llvm::DenseMap<const CodeTextRegion *, StaticGlobalSpaceRegion *>
  1368.     StaticsGlobalSpaceRegions;
  1369.  
  1370.   HeapSpaceRegion *heap = nullptr;
  1371.   UnknownSpaceRegion *unknown = nullptr;
  1372.   CodeSpaceRegion *code = nullptr;
  1373.  
  1374. public:
  1375.   MemRegionManager(ASTContext &c, llvm::BumpPtrAllocator &a) : Ctx(c), A(a) {}
  1376.   ~MemRegionManager();
  1377.  
  1378.   ASTContext &getContext() { return Ctx; }
  1379.   const ASTContext &getContext() const { return Ctx; }
  1380.  
  1381.   llvm::BumpPtrAllocator &getAllocator() { return A; }
  1382.  
  1383.   /// \returns The static size in bytes of the region \p MR.
  1384.   /// \note The region \p MR must be a 'SubRegion'.
  1385.   DefinedOrUnknownSVal getStaticSize(const MemRegion *MR,
  1386.                                      SValBuilder &SVB) const;
  1387.  
  1388.   /// getStackLocalsRegion - Retrieve the memory region associated with the
  1389.   ///  specified stack frame.
  1390.   const StackLocalsSpaceRegion *
  1391.   getStackLocalsRegion(const StackFrameContext *STC);
  1392.  
  1393.   /// getStackArgumentsRegion - Retrieve the memory region associated with
  1394.   ///  function/method arguments of the specified stack frame.
  1395.   const StackArgumentsSpaceRegion *
  1396.   getStackArgumentsRegion(const StackFrameContext *STC);
  1397.  
  1398.   /// getGlobalsRegion - Retrieve the memory region associated with
  1399.   ///  global variables.
  1400.   const GlobalsSpaceRegion *getGlobalsRegion(
  1401.       MemRegion::Kind K = MemRegion::GlobalInternalSpaceRegionKind,
  1402.       const CodeTextRegion *R = nullptr);
  1403.  
  1404.   /// getHeapRegion - Retrieve the memory region associated with the
  1405.   ///  generic "heap".
  1406.   const HeapSpaceRegion *getHeapRegion();
  1407.  
  1408.   /// getUnknownRegion - Retrieve the memory region associated with unknown
  1409.   /// memory space.
  1410.   const UnknownSpaceRegion *getUnknownRegion();
  1411.  
  1412.   const CodeSpaceRegion *getCodeRegion();
  1413.  
  1414.   /// getAllocaRegion - Retrieve a region associated with a call to alloca().
  1415.   const AllocaRegion *getAllocaRegion(const Expr *Ex, unsigned Cnt,
  1416.                                       const LocationContext *LC);
  1417.  
  1418.   /// getCompoundLiteralRegion - Retrieve the region associated with a
  1419.   ///  given CompoundLiteral.
  1420.   const CompoundLiteralRegion*
  1421.   getCompoundLiteralRegion(const CompoundLiteralExpr *CL,
  1422.                            const LocationContext *LC);
  1423.  
  1424.   /// getCXXThisRegion - Retrieve the [artificial] region associated with the
  1425.   ///  parameter 'this'.
  1426.   const CXXThisRegion *getCXXThisRegion(QualType thisPointerTy,
  1427.                                         const LocationContext *LC);
  1428.  
  1429.   /// Retrieve or create a "symbolic" memory region.
  1430.   /// If no memory space is specified, `UnknownSpaceRegion` will be used.
  1431.   const SymbolicRegion *
  1432.   getSymbolicRegion(SymbolRef Sym, const MemSpaceRegion *MemSpace = nullptr);
  1433.  
  1434.   /// Return a unique symbolic region belonging to heap memory space.
  1435.   const SymbolicRegion *getSymbolicHeapRegion(SymbolRef sym);
  1436.  
  1437.   const StringRegion *getStringRegion(const StringLiteral *Str);
  1438.  
  1439.   const ObjCStringRegion *getObjCStringRegion(const ObjCStringLiteral *Str);
  1440.  
  1441.   /// getVarRegion - Retrieve or create the memory region associated with
  1442.   ///  a specified VarDecl and LocationContext.
  1443.   const VarRegion *getVarRegion(const VarDecl *VD, const LocationContext *LC);
  1444.  
  1445.   /// getVarRegion - Retrieve or create the memory region associated with
  1446.   ///  a specified VarDecl and LocationContext.
  1447.   const NonParamVarRegion *getNonParamVarRegion(const VarDecl *VD,
  1448.                                                 const MemRegion *superR);
  1449.  
  1450.   /// getParamVarRegion - Retrieve or create the memory region
  1451.   /// associated with a specified CallExpr, Index and LocationContext.
  1452.   const ParamVarRegion *getParamVarRegion(const Expr *OriginExpr,
  1453.                                           unsigned Index,
  1454.                                           const LocationContext *LC);
  1455.  
  1456.   /// getElementRegion - Retrieve the memory region associated with the
  1457.   ///  associated element type, index, and super region.
  1458.   const ElementRegion *getElementRegion(QualType elementType, NonLoc Idx,
  1459.                                         const SubRegion *superRegion,
  1460.                                         ASTContext &Ctx);
  1461.  
  1462.   const ElementRegion *getElementRegionWithSuper(const ElementRegion *ER,
  1463.                                                  const SubRegion *superRegion) {
  1464.     return getElementRegion(ER->getElementType(), ER->getIndex(),
  1465.                             superRegion, ER->getContext());
  1466.   }
  1467.  
  1468.   /// getFieldRegion - Retrieve or create the memory region associated with
  1469.   ///  a specified FieldDecl.  'superRegion' corresponds to the containing
  1470.   ///  memory region (which typically represents the memory representing
  1471.   ///  a structure or class).
  1472.   const FieldRegion *getFieldRegion(const FieldDecl *fd,
  1473.                                     const SubRegion* superRegion);
  1474.  
  1475.   const FieldRegion *getFieldRegionWithSuper(const FieldRegion *FR,
  1476.                                              const SubRegion *superRegion) {
  1477.     return getFieldRegion(FR->getDecl(), superRegion);
  1478.   }
  1479.  
  1480.   /// getObjCIvarRegion - Retrieve or create the memory region associated with
  1481.   ///   a specified Objective-c instance variable.  'superRegion' corresponds
  1482.   ///   to the containing region (which typically represents the Objective-C
  1483.   ///   object).
  1484.   const ObjCIvarRegion *getObjCIvarRegion(const ObjCIvarDecl *ivd,
  1485.                                           const SubRegion* superRegion);
  1486.  
  1487.   const CXXTempObjectRegion *getCXXTempObjectRegion(Expr const *Ex,
  1488.                                                     LocationContext const *LC);
  1489.  
  1490.   /// Create a CXXBaseObjectRegion with the given base class for region
  1491.   /// \p Super.
  1492.   ///
  1493.   /// The type of \p Super is assumed be a class deriving from \p BaseClass.
  1494.   const CXXBaseObjectRegion *
  1495.   getCXXBaseObjectRegion(const CXXRecordDecl *BaseClass, const SubRegion *Super,
  1496.                          bool IsVirtual);
  1497.  
  1498.   /// Create a CXXBaseObjectRegion with the same CXXRecordDecl but a different
  1499.   /// super region.
  1500.   const CXXBaseObjectRegion *
  1501.   getCXXBaseObjectRegionWithSuper(const CXXBaseObjectRegion *baseReg,
  1502.                                   const SubRegion *superRegion) {
  1503.     return getCXXBaseObjectRegion(baseReg->getDecl(), superRegion,
  1504.                                   baseReg->isVirtual());
  1505.   }
  1506.  
  1507.   /// Create a CXXDerivedObjectRegion with the given derived class for region
  1508.   /// \p Super. This should not be used for casting an existing
  1509.   /// CXXBaseObjectRegion back to the derived type; instead, CXXBaseObjectRegion
  1510.   /// should be removed.
  1511.   const CXXDerivedObjectRegion *
  1512.   getCXXDerivedObjectRegion(const CXXRecordDecl *BaseClass,
  1513.                             const SubRegion *Super);
  1514.  
  1515.   const FunctionCodeRegion *getFunctionCodeRegion(const NamedDecl *FD);
  1516.   const BlockCodeRegion *getBlockCodeRegion(const BlockDecl *BD,
  1517.                                             CanQualType locTy,
  1518.                                             AnalysisDeclContext *AC);
  1519.  
  1520.   /// getBlockDataRegion - Get the memory region associated with an instance
  1521.   ///  of a block.  Unlike many other MemRegions, the LocationContext*
  1522.   ///  argument is allowed to be NULL for cases where we have no known
  1523.   ///  context.
  1524.   const BlockDataRegion *getBlockDataRegion(const BlockCodeRegion *bc,
  1525.                                             const LocationContext *lc,
  1526.                                             unsigned blockCount);
  1527.  
  1528.   /// Create a CXXTempObjectRegion for temporaries which are lifetime-extended
  1529.   /// by static references. This differs from getCXXTempObjectRegion in the
  1530.   /// super-region used.
  1531.   const CXXTempObjectRegion *getCXXStaticTempObjectRegion(const Expr *Ex);
  1532.  
  1533. private:
  1534.   template <typename RegionTy, typename SuperTy,
  1535.             typename Arg1Ty>
  1536.   RegionTy* getSubRegion(const Arg1Ty arg1,
  1537.                          const SuperTy* superRegion);
  1538.  
  1539.   template <typename RegionTy, typename SuperTy,
  1540.             typename Arg1Ty, typename Arg2Ty>
  1541.   RegionTy* getSubRegion(const Arg1Ty arg1, const Arg2Ty arg2,
  1542.                          const SuperTy* superRegion);
  1543.  
  1544.   template <typename RegionTy, typename SuperTy,
  1545.             typename Arg1Ty, typename Arg2Ty, typename Arg3Ty>
  1546.   RegionTy* getSubRegion(const Arg1Ty arg1, const Arg2Ty arg2,
  1547.                          const Arg3Ty arg3,
  1548.                          const SuperTy* superRegion);
  1549.  
  1550.   template <typename REG>
  1551.   const REG* LazyAllocate(REG*& region);
  1552.  
  1553.   template <typename REG, typename ARG>
  1554.   const REG* LazyAllocate(REG*& region, ARG a);
  1555. };
  1556.  
  1557. //===----------------------------------------------------------------------===//
  1558. // Out-of-line member definitions.
  1559. //===----------------------------------------------------------------------===//
  1560.  
  1561. inline ASTContext &MemRegion::getContext() const {
  1562.   return getMemRegionManager().getContext();
  1563. }
  1564.  
  1565. //===----------------------------------------------------------------------===//
  1566. // Means for storing region/symbol handling traits.
  1567. //===----------------------------------------------------------------------===//
  1568.  
  1569. /// Information about invalidation for a particular region/symbol.
  1570. class RegionAndSymbolInvalidationTraits {
  1571.   using StorageTypeForKinds = unsigned char;
  1572.  
  1573.   llvm::DenseMap<const MemRegion *, StorageTypeForKinds> MRTraitsMap;
  1574.   llvm::DenseMap<SymbolRef, StorageTypeForKinds> SymTraitsMap;
  1575.  
  1576.   using const_region_iterator =
  1577.       llvm::DenseMap<const MemRegion *, StorageTypeForKinds>::const_iterator;
  1578.   using const_symbol_iterator =
  1579.       llvm::DenseMap<SymbolRef, StorageTypeForKinds>::const_iterator;
  1580.  
  1581. public:
  1582.   /// Describes different invalidation traits.
  1583.   enum InvalidationKinds {
  1584.     /// Tells that a region's contents is not changed.
  1585.     TK_PreserveContents = 0x1,
  1586.  
  1587.     /// Suppress pointer-escaping of a region.
  1588.     TK_SuppressEscape = 0x2,
  1589.  
  1590.     // Do not invalidate super region.
  1591.     TK_DoNotInvalidateSuperRegion = 0x4,
  1592.  
  1593.     /// When applied to a MemSpaceRegion, indicates the entire memory space
  1594.     /// should be invalidated.
  1595.     TK_EntireMemSpace = 0x8
  1596.  
  1597.     // Do not forget to extend StorageTypeForKinds if number of traits exceed
  1598.     // the number of bits StorageTypeForKinds can store.
  1599.   };
  1600.  
  1601.   void setTrait(SymbolRef Sym, InvalidationKinds IK);
  1602.   void setTrait(const MemRegion *MR, InvalidationKinds IK);
  1603.   bool hasTrait(SymbolRef Sym, InvalidationKinds IK) const;
  1604.   bool hasTrait(const MemRegion *MR, InvalidationKinds IK) const;
  1605. };
  1606.  
  1607. //===----------------------------------------------------------------------===//
  1608. // Pretty-printing regions.
  1609. //===----------------------------------------------------------------------===//
  1610. inline raw_ostream &operator<<(raw_ostream &os, const MemRegion *R) {
  1611.   R->dumpToStream(os);
  1612.   return os;
  1613. }
  1614.  
  1615. } // namespace ento
  1616.  
  1617. } // namespace clang
  1618.  
  1619. #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_MEMREGION_H
  1620.