contrib/llvm/tools/clang/include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h

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