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