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