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