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