contrib/llvm/tools/clang/lib/StaticAnalyzer/Core/MemRegion.cpp

   1 //== MemRegion.cpp - 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 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
  17 #include "clang/AST/Attr.h"
  18 #include "clang/AST/CharUnits.h"
  19 #include "clang/AST/DeclObjC.h"
  20 #include "clang/AST/RecordLayout.h"
  21 #include "clang/Analysis/AnalysisContext.h"
  22 #include "clang/Analysis/Support/BumpVector.h"
  23 #include "clang/Basic/SourceManager.h"
  24 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
  25 #include "llvm/Support/raw_ostream.h"
  26
  27 using namespace clang;
  28 using namespace ento;
  29
  30 //===----------------------------------------------------------------------===//
  31 // MemRegion Construction.
  32 //===----------------------------------------------------------------------===//
  33
  34 template<typename RegionTy> struct MemRegionManagerTrait;
  35
  36 template <typename RegionTy, typename A1>
  37 RegionTy* MemRegionManager::getRegion(const A1 a1) {
  38   const typename MemRegionManagerTrait<RegionTy>::SuperRegionTy *superRegion =
  39   MemRegionManagerTrait<RegionTy>::getSuperRegion(*this, a1);
  40
  41   llvm::FoldingSetNodeID ID;
  42   RegionTy::ProfileRegion(ID, a1, superRegion);
  43   void *InsertPos;
  44   RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
  45                                                                    InsertPos));
  46
  47   if (!R) {
  48     R = A.Allocate<RegionTy>();
  49     new (R) RegionTy(a1, superRegion);
  50     Regions.InsertNode(R, InsertPos);
  51   }
  52
  53   return R;
  54 }
  55
  56 template <typename RegionTy, typename A1>
  57 RegionTy* MemRegionManager::getSubRegion(const A1 a1,
  58                                          const MemRegion *superRegion) {
  59   llvm::FoldingSetNodeID ID;
  60   RegionTy::ProfileRegion(ID, a1, superRegion);
  61   void *InsertPos;
  62   RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
  63                                                                    InsertPos));
  64
  65   if (!R) {
  66     R = A.Allocate<RegionTy>();
  67     new (R) RegionTy(a1, superRegion);
  68     Regions.InsertNode(R, InsertPos);
  69   }
  70
  71   return R;
  72 }
  73
  74 template <typename RegionTy, typename A1, typename A2>
  75 RegionTy* MemRegionManager::getRegion(const A1 a1, const A2 a2) {
  76   const typename MemRegionManagerTrait<RegionTy>::SuperRegionTy *superRegion =
  77   MemRegionManagerTrait<RegionTy>::getSuperRegion(*this, a1, a2);
  78
  79   llvm::FoldingSetNodeID ID;
  80   RegionTy::ProfileRegion(ID, a1, a2, superRegion);
  81   void *InsertPos;
  82   RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
  83                                                                    InsertPos));
  84
  85   if (!R) {
  86     R = A.Allocate<RegionTy>();
  87     new (R) RegionTy(a1, a2, superRegion);
  88     Regions.InsertNode(R, InsertPos);
  89   }
  90
  91   return R;
  92 }
  93
  94 template <typename RegionTy, typename A1, typename A2>
  95 RegionTy* MemRegionManager::getSubRegion(const A1 a1, const A2 a2,
  96                                          const MemRegion *superRegion) {
  97   llvm::FoldingSetNodeID ID;
  98   RegionTy::ProfileRegion(ID, a1, a2, superRegion);
  99   void *InsertPos;
 100   RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
 101                                                                    InsertPos));
 102
 103   if (!R) {
 104     R = A.Allocate<RegionTy>();
 105     new (R) RegionTy(a1, a2, superRegion);
 106     Regions.InsertNode(R, InsertPos);
 107   }
 108
 109   return R;
 110 }
 111
 112 template <typename RegionTy, typename A1, typename A2, typename A3>
 113 RegionTy* MemRegionManager::getSubRegion(const A1 a1, const A2 a2, const A3 a3,
 114                                          const MemRegion *superRegion) {
 115   llvm::FoldingSetNodeID ID;
 116   RegionTy::ProfileRegion(ID, a1, a2, a3, superRegion);
 117   void *InsertPos;
 118   RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
 119                                                                    InsertPos));
 120
 121   if (!R) {
 122     R = A.Allocate<RegionTy>();
 123     new (R) RegionTy(a1, a2, a3, superRegion);
 124     Regions.InsertNode(R, InsertPos);
 125   }
 126
 127   return R;
 128 }
 129
 130 //===----------------------------------------------------------------------===//
 131 // Object destruction.
 132 //===----------------------------------------------------------------------===//
 133
 134 MemRegion::~MemRegion() {}
 135
 136 MemRegionManager::~MemRegionManager() {
 137   // All regions and their data are BumpPtrAllocated.  No need to call
 138   // their destructors.
 139 }
 140
 141 //===----------------------------------------------------------------------===//
 142 // Basic methods.
 143 //===----------------------------------------------------------------------===//
 144
 145 bool SubRegion::isSubRegionOf(const MemRegion* R) const {
 146   const MemRegion* r = getSuperRegion();
 147   while (r != nullptr) {
 148     if (r == R)
 149       return true;
 150     if (const SubRegion* sr = dyn_cast<SubRegion>(r))
 151       r = sr->getSuperRegion();
 152     else
 153       break;
 154   }
 155   return false;
 156 }
 157
 158 MemRegionManager* SubRegion::getMemRegionManager() const {
 159   const SubRegion* r = this;
 160   do {
 161     const MemRegion *superRegion = r->getSuperRegion();
 162     if (const SubRegion *sr = dyn_cast<SubRegion>(superRegion)) {
 163       r = sr;
 164       continue;
 165     }
 166     return superRegion->getMemRegionManager();
 167   } while (1);
 168 }
 169
 170 const StackFrameContext *VarRegion::getStackFrame() const {
 171   const StackSpaceRegion *SSR = dyn_cast<StackSpaceRegion>(getMemorySpace());
 172   return SSR ? SSR->getStackFrame() : nullptr;
 173 }
 174
 175 //===----------------------------------------------------------------------===//
 176 // Region extents.
 177 //===----------------------------------------------------------------------===//
 178
 179 DefinedOrUnknownSVal TypedValueRegion::getExtent(SValBuilder &svalBuilder) const {
 180   ASTContext &Ctx = svalBuilder.getContext();
 181   QualType T = getDesugaredValueType(Ctx);
 182
 183   if (isa<VariableArrayType>(T))
 184     return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this));
 185   if (T->isIncompleteType())
 186     return UnknownVal();
 187
 188   CharUnits size = Ctx.getTypeSizeInChars(T);
 189   QualType sizeTy = svalBuilder.getArrayIndexType();
 190   return svalBuilder.makeIntVal(size.getQuantity(), sizeTy);
 191 }
 192
 193 DefinedOrUnknownSVal FieldRegion::getExtent(SValBuilder &svalBuilder) const {
 194   // Force callers to deal with bitfields explicitly.
 195   if (getDecl()->isBitField())
 196     return UnknownVal();
 197
 198   DefinedOrUnknownSVal Extent = DeclRegion::getExtent(svalBuilder);
 199
 200   // A zero-length array at the end of a struct often stands for dynamically-
 201   // allocated extra memory.
 202   if (Extent.isZeroConstant()) {
 203     QualType T = getDesugaredValueType(svalBuilder.getContext());
 204
 205     if (isa<ConstantArrayType>(T))
 206       return UnknownVal();
 207   }
 208
 209   return Extent;
 210 }
 211
 212 DefinedOrUnknownSVal AllocaRegion::getExtent(SValBuilder &svalBuilder) const {
 213   return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this));
 214 }
 215
 216 DefinedOrUnknownSVal SymbolicRegion::getExtent(SValBuilder &svalBuilder) const {
 217   return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this));
 218 }
 219
 220 DefinedOrUnknownSVal StringRegion::getExtent(SValBuilder &svalBuilder) const {
 221   return svalBuilder.makeIntVal(getStringLiteral()->getByteLength()+1,
 222                                 svalBuilder.getArrayIndexType());
 223 }
 224
 225 ObjCIvarRegion::ObjCIvarRegion(const ObjCIvarDecl *ivd, const MemRegion* sReg)
 226   : DeclRegion(ivd, sReg, ObjCIvarRegionKind) {}
 227
 228 const ObjCIvarDecl *ObjCIvarRegion::getDecl() const {
 229   return cast<ObjCIvarDecl>(D);
 230 }
 231
 232 QualType ObjCIvarRegion::getValueType() const {
 233   return getDecl()->getType();
 234 }
 235
 236 QualType CXXBaseObjectRegion::getValueType() const {
 237   return QualType(getDecl()->getTypeForDecl(), 0);
 238 }
 239
 240 //===----------------------------------------------------------------------===//
 241 // FoldingSet profiling.
 242 //===----------------------------------------------------------------------===//
 243
 244 void MemSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const {
 245   ID.AddInteger(static_cast<unsigned>(getKind()));
 246 }
 247
 248 void StackSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const {
 249   ID.AddInteger(static_cast<unsigned>(getKind()));
 250   ID.AddPointer(getStackFrame());
 251 }
 252
 253 void StaticGlobalSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const {
 254   ID.AddInteger(static_cast<unsigned>(getKind()));
 255   ID.AddPointer(getCodeRegion());
 256 }
 257
 258 void StringRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
 259                                  const StringLiteral* Str,
 260                                  const MemRegion* superRegion) {
 261   ID.AddInteger(static_cast<unsigned>(StringRegionKind));
 262   ID.AddPointer(Str);
 263   ID.AddPointer(superRegion);
 264 }
 265
 266 void ObjCStringRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
 267                                      const ObjCStringLiteral* Str,
 268                                      const MemRegion* superRegion) {
 269   ID.AddInteger(static_cast<unsigned>(ObjCStringRegionKind));
 270   ID.AddPointer(Str);
 271   ID.AddPointer(superRegion);
 272 }
 273
 274 void AllocaRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
 275                                  const Expr *Ex, unsigned cnt,
 276                                  const MemRegion *superRegion) {
 277   ID.AddInteger(static_cast<unsigned>(AllocaRegionKind));
 278   ID.AddPointer(Ex);
 279   ID.AddInteger(cnt);
 280   ID.AddPointer(superRegion);
 281 }
 282
 283 void AllocaRegion::Profile(llvm::FoldingSetNodeID& ID) const {
 284   ProfileRegion(ID, Ex, Cnt, superRegion);
 285 }
 286
 287 void CompoundLiteralRegion::Profile(llvm::FoldingSetNodeID& ID) const {
 288   CompoundLiteralRegion::ProfileRegion(ID, CL, superRegion);
 289 }
 290
 291 void CompoundLiteralRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
 292                                           const CompoundLiteralExpr *CL,
 293                                           const MemRegion* superRegion) {
 294   ID.AddInteger(static_cast<unsigned>(CompoundLiteralRegionKind));
 295   ID.AddPointer(CL);
 296   ID.AddPointer(superRegion);
 297 }
 298
 299 void CXXThisRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
 300                                   const PointerType *PT,
 301                                   const MemRegion *sRegion) {
 302   ID.AddInteger(static_cast<unsigned>(CXXThisRegionKind));
 303   ID.AddPointer(PT);
 304   ID.AddPointer(sRegion);
 305 }
 306
 307 void CXXThisRegion::Profile(llvm::FoldingSetNodeID &ID) const {
 308   CXXThisRegion::ProfileRegion(ID, ThisPointerTy, superRegion);
 309 }
 310
 311 void ObjCIvarRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
 312                                    const ObjCIvarDecl *ivd,
 313                                    const MemRegion* superRegion) {
 314   DeclRegion::ProfileRegion(ID, ivd, superRegion, ObjCIvarRegionKind);
 315 }
 316
 317 void DeclRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, const Decl *D,
 318                                const MemRegion* superRegion, Kind k) {
 319   ID.AddInteger(static_cast<unsigned>(k));
 320   ID.AddPointer(D);
 321   ID.AddPointer(superRegion);
 322 }
 323
 324 void DeclRegion::Profile(llvm::FoldingSetNodeID& ID) const {
 325   DeclRegion::ProfileRegion(ID, D, superRegion, getKind());
 326 }
 327
 328 void VarRegion::Profile(llvm::FoldingSetNodeID &ID) const {
 329   VarRegion::ProfileRegion(ID, getDecl(), superRegion);
 330 }
 331
 332 void SymbolicRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, SymbolRef sym,
 333                                    const MemRegion *sreg) {
 334   ID.AddInteger(static_cast<unsigned>(MemRegion::SymbolicRegionKind));
 335   ID.Add(sym);
 336   ID.AddPointer(sreg);
 337 }
 338
 339 void SymbolicRegion::Profile(llvm::FoldingSetNodeID& ID) const {
 340   SymbolicRegion::ProfileRegion(ID, sym, getSuperRegion());
 341 }
 342
 343 void ElementRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
 344                                   QualType ElementType, SVal Idx,
 345                                   const MemRegion* superRegion) {
 346   ID.AddInteger(MemRegion::ElementRegionKind);
 347   ID.Add(ElementType);
 348   ID.AddPointer(superRegion);
 349   Idx.Profile(ID);
 350 }
 351
 352 void ElementRegion::Profile(llvm::FoldingSetNodeID& ID) const {
 353   ElementRegion::ProfileRegion(ID, ElementType, Index, superRegion);
 354 }
 355
 356 void FunctionCodeRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
 357                                        const NamedDecl *FD,
 358                                        const MemRegion*) {
 359   ID.AddInteger(MemRegion::FunctionCodeRegionKind);
 360   ID.AddPointer(FD);
 361 }
 362
 363 void FunctionCodeRegion::Profile(llvm::FoldingSetNodeID& ID) const {
 364   FunctionCodeRegion::ProfileRegion(ID, FD, superRegion);
 365 }
 366
 367 void BlockCodeRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
 368                                     const BlockDecl *BD, CanQualType,
 369                                     const AnalysisDeclContext *AC,
 370                                     const MemRegion*) {
 371   ID.AddInteger(MemRegion::BlockCodeRegionKind);
 372   ID.AddPointer(BD);
 373 }
 374
 375 void BlockCodeRegion::Profile(llvm::FoldingSetNodeID& ID) const {
 376   BlockCodeRegion::ProfileRegion(ID, BD, locTy, AC, superRegion);
 377 }
 378
 379 void BlockDataRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
 380                                     const BlockCodeRegion *BC,
 381                                     const LocationContext *LC,
 382                                     unsigned BlkCount,
 383                                     const MemRegion *sReg) {
 384   ID.AddInteger(MemRegion::BlockDataRegionKind);
 385   ID.AddPointer(BC);
 386   ID.AddPointer(LC);
 387   ID.AddInteger(BlkCount);
 388   ID.AddPointer(sReg);
 389 }
 390
 391 void BlockDataRegion::Profile(llvm::FoldingSetNodeID& ID) const {
 392   BlockDataRegion::ProfileRegion(ID, BC, LC, BlockCount, getSuperRegion());
 393 }
 394
 395 void CXXTempObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
 396                                         Expr const *Ex,
 397                                         const MemRegion *sReg) {
 398   ID.AddPointer(Ex);
 399   ID.AddPointer(sReg);
 400 }
 401
 402 void CXXTempObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const {
 403   ProfileRegion(ID, Ex, getSuperRegion());
 404 }
 405
 406 void CXXBaseObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
 407                                         const CXXRecordDecl *RD,
 408                                         bool IsVirtual,
 409                                         const MemRegion *SReg) {
 410   ID.AddPointer(RD);
 411   ID.AddBoolean(IsVirtual);
 412   ID.AddPointer(SReg);
 413 }
 414
 415 void CXXBaseObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const {
 416   ProfileRegion(ID, getDecl(), isVirtual(), superRegion);
 417 }
 418
 419 //===----------------------------------------------------------------------===//
 420 // Region anchors.
 421 //===----------------------------------------------------------------------===//
 422
 423 void GlobalsSpaceRegion::anchor() { }
 424 void HeapSpaceRegion::anchor() { }
 425 void UnknownSpaceRegion::anchor() { }
 426 void StackLocalsSpaceRegion::anchor() { }
 427 void StackArgumentsSpaceRegion::anchor() { }
 428 void TypedRegion::anchor() { }
 429 void TypedValueRegion::anchor() { }
 430 void CodeTextRegion::anchor() { }
 431 void SubRegion::anchor() { }
 432
 433 //===----------------------------------------------------------------------===//
 434 // Region pretty-printing.
 435 //===----------------------------------------------------------------------===//
 436
 437 LLVM_DUMP_METHOD void MemRegion::dump() const {
 438   dumpToStream(llvm::errs());
 439 }
 440
 441 std::string MemRegion::getString() const {
 442   std::string s;
 443   llvm::raw_string_ostream os(s);
 444   dumpToStream(os);
 445   return os.str();
 446 }
 447
 448 void MemRegion::dumpToStream(raw_ostream &os) const {
 449   os << "<Unknown Region>";
 450 }
 451
 452 void AllocaRegion::dumpToStream(raw_ostream &os) const {
 453   os << "alloca{" << static_cast<const void*>(Ex) << ',' << Cnt << '}';
 454 }
 455
 456 void FunctionCodeRegion::dumpToStream(raw_ostream &os) const {
 457   os << "code{" << getDecl()->getDeclName().getAsString() << '}';
 458 }
 459
 460 void BlockCodeRegion::dumpToStream(raw_ostream &os) const {
 461   os << "block_code{" << static_cast<const void*>(this) << '}';
 462 }
 463
 464 void BlockDataRegion::dumpToStream(raw_ostream &os) const {
 465   os << "block_data{" << BC;
 466   os << "; ";
 467   for (BlockDataRegion::referenced_vars_iterator
 468          I = referenced_vars_begin(),
 469          E = referenced_vars_end(); I != E; ++I)
 470     os << "(" << I.getCapturedRegion() << "," <<
 471                  I.getOriginalRegion() << ") ";
 472   os << '}';
 473 }
 474
 475 void CompoundLiteralRegion::dumpToStream(raw_ostream &os) const {
 476   // FIXME: More elaborate pretty-printing.
 477   os << "{ " << static_cast<const void*>(CL) <<  " }";
 478 }
 479
 480 void CXXTempObjectRegion::dumpToStream(raw_ostream &os) const {
 481   os << "temp_object{" << getValueType().getAsString() << ','
 482      << static_cast<const void*>(Ex) << '}';
 483 }
 484
 485 void CXXBaseObjectRegion::dumpToStream(raw_ostream &os) const {
 486   os << "base{" << superRegion << ',' << getDecl()->getName() << '}';
 487 }
 488
 489 void CXXThisRegion::dumpToStream(raw_ostream &os) const {
 490   os << "this";
 491 }
 492
 493 void ElementRegion::dumpToStream(raw_ostream &os) const {
 494   os << "element{" << superRegion << ','
 495      << Index << ',' << getElementType().getAsString() << '}';
 496 }
 497
 498 void FieldRegion::dumpToStream(raw_ostream &os) const {
 499   os << superRegion << "->" << *getDecl();
 500 }
 501
 502 void ObjCIvarRegion::dumpToStream(raw_ostream &os) const {
 503   os << "ivar{" << superRegion << ',' << *getDecl() << '}';
 504 }
 505
 506 void StringRegion::dumpToStream(raw_ostream &os) const {
 507   assert(Str != nullptr && "Expecting non-null StringLiteral");
 508   Str->printPretty(os, nullptr, PrintingPolicy(getContext().getLangOpts()));
 509 }
 510
 511 void ObjCStringRegion::dumpToStream(raw_ostream &os) const {
 512   assert(Str != nullptr && "Expecting non-null ObjCStringLiteral");
 513   Str->printPretty(os, nullptr, PrintingPolicy(getContext().getLangOpts()));
 514 }
 515
 516 void SymbolicRegion::dumpToStream(raw_ostream &os) const {
 517   os << "SymRegion{" << sym << '}';
 518 }
 519
 520 void VarRegion::dumpToStream(raw_ostream &os) const {
 521   os << *cast<VarDecl>(D);
 522 }
 523
 524 LLVM_DUMP_METHOD void RegionRawOffset::dump() const {
 525   dumpToStream(llvm::errs());
 526 }
 527
 528 void RegionRawOffset::dumpToStream(raw_ostream &os) const {
 529   os << "raw_offset{" << getRegion() << ',' << getOffset().getQuantity() << '}';
 530 }
 531
 532 void CodeSpaceRegion::dumpToStream(raw_ostream &os) const {
 533   os << "CodeSpaceRegion";
 534 }
 535
 536 void StaticGlobalSpaceRegion::dumpToStream(raw_ostream &os) const {
 537   os << "StaticGlobalsMemSpace{" << CR << '}';
 538 }
 539
 540 void GlobalInternalSpaceRegion::dumpToStream(raw_ostream &os) const {
 541   os << "GlobalInternalSpaceRegion";
 542 }
 543
 544 void GlobalSystemSpaceRegion::dumpToStream(raw_ostream &os) const {
 545   os << "GlobalSystemSpaceRegion";
 546 }
 547
 548 void GlobalImmutableSpaceRegion::dumpToStream(raw_ostream &os) const {
 549   os << "GlobalImmutableSpaceRegion";
 550 }
 551
 552 void HeapSpaceRegion::dumpToStream(raw_ostream &os) const {
 553   os << "HeapSpaceRegion";
 554 }
 555
 556 void UnknownSpaceRegion::dumpToStream(raw_ostream &os) const {
 557   os << "UnknownSpaceRegion";
 558 }
 559
 560 void StackArgumentsSpaceRegion::dumpToStream(raw_ostream &os) const {
 561   os << "StackArgumentsSpaceRegion";
 562 }
 563
 564 void StackLocalsSpaceRegion::dumpToStream(raw_ostream &os) const {
 565   os << "StackLocalsSpaceRegion";
 566 }
 567
 568 bool MemRegion::canPrintPretty() const {
 569   return canPrintPrettyAsExpr();
 570 }
 571
 572 bool MemRegion::canPrintPrettyAsExpr() const {
 573   return false;
 574 }
 575
 576 void MemRegion::printPretty(raw_ostream &os) const {
 577   assert(canPrintPretty() && "This region cannot be printed pretty.");
 578   os << "'";
 579   printPrettyAsExpr(os);
 580   os << "'";
 581 }
 582
 583 void MemRegion::printPrettyAsExpr(raw_ostream &os) const {
 584   llvm_unreachable("This region cannot be printed pretty.");
 585 }
 586
 587 bool VarRegion::canPrintPrettyAsExpr() const {
 588   return true;
 589 }
 590
 591 void VarRegion::printPrettyAsExpr(raw_ostream &os) const {
 592   os << getDecl()->getName();
 593 }
 594
 595 bool ObjCIvarRegion::canPrintPrettyAsExpr() const {
 596   return true;
 597 }
 598
 599 void ObjCIvarRegion::printPrettyAsExpr(raw_ostream &os) const {
 600   os << getDecl()->getName();
 601 }
 602
 603 bool FieldRegion::canPrintPretty() const {
 604   return true;
 605 }
 606
 607 bool FieldRegion::canPrintPrettyAsExpr() const {
 608   return superRegion->canPrintPrettyAsExpr();
 609 }
 610
 611 void FieldRegion::printPrettyAsExpr(raw_ostream &os) const {
 612   assert(canPrintPrettyAsExpr());
 613   superRegion->printPrettyAsExpr(os);
 614   os << "." << getDecl()->getName();
 615 }
 616
 617 void FieldRegion::printPretty(raw_ostream &os) const {
 618   if (canPrintPrettyAsExpr()) {
 619     os << "\'";
 620     printPrettyAsExpr(os);
 621     os << "'";
 622   } else {
 623     os << "field " << "\'" << getDecl()->getName() << "'";
 624   }
 625 }
 626
 627 bool CXXBaseObjectRegion::canPrintPrettyAsExpr() const {
 628   return superRegion->canPrintPrettyAsExpr();
 629 }
 630
 631 void CXXBaseObjectRegion::printPrettyAsExpr(raw_ostream &os) const {
 632   superRegion->printPrettyAsExpr(os);
 633 }
 634
 635 std::string MemRegion::getDescriptiveName(bool UseQuotes) const {
 636   std::string VariableName;
 637   std::string ArrayIndices;
 638   const MemRegion *R = this;
 639   SmallString<50> buf;
 640   llvm::raw_svector_ostream os(buf);
 641
 642   // Obtain array indices to add them to the variable name.
 643   const ElementRegion *ER = nullptr;
 644   while ((ER = R->getAs<ElementRegion>())) {
 645     // Index is a ConcreteInt.
 646     if (auto CI = ER->getIndex().getAs<nonloc::ConcreteInt>()) {
 647       llvm::SmallString<2> Idx;
 648       CI->getValue().toString(Idx);
 649       ArrayIndices = (llvm::Twine("[") + Idx.str() + "]" + ArrayIndices).str();
 650     }
 651     // If not a ConcreteInt, try to obtain the variable
 652     // name by calling 'getDescriptiveName' recursively.
 653     else {
 654       std::string Idx = ER->getDescriptiveName(false);
 655       if (!Idx.empty()) {
 656         ArrayIndices = (llvm::Twine("[") + Idx + "]" + ArrayIndices).str();
 657       }
 658     }
 659     R = ER->getSuperRegion();
 660   }
 661
 662   // Get variable name.
 663   if (R && R->canPrintPrettyAsExpr()) {
 664     R->printPrettyAsExpr(os);
 665     if (UseQuotes) {
 666       return (llvm::Twine("'") + os.str() + ArrayIndices + "'").str();
 667     } else {
 668       return (llvm::Twine(os.str()) + ArrayIndices).str();
 669     }
 670   }
 671
 672   return VariableName;
 673 }
 674
 675 SourceRange MemRegion::sourceRange() const {
 676   const VarRegion *const VR = dyn_cast<VarRegion>(this->getBaseRegion());
 677   const FieldRegion *const FR = dyn_cast<FieldRegion>(this);
 678
 679   // Check for more specific regions first.
 680   // FieldRegion
 681   if (FR) {
 682     return FR->getDecl()->getSourceRange();
 683   }
 684   // VarRegion
 685   else if (VR) {
 686     return VR->getDecl()->getSourceRange();
 687   }
 688   // Return invalid source range (can be checked by client).
 689   else {
 690     return SourceRange{};
 691   }
 692 }
 693
 694 //===----------------------------------------------------------------------===//
 695 // MemRegionManager methods.
 696 //===----------------------------------------------------------------------===//
 697
 698 template <typename REG>
 699 const REG *MemRegionManager::LazyAllocate(REG*& region) {
 700   if (!region) {
 701     region = A.Allocate<REG>();
 702     new (region) REG(this);
 703   }
 704
 705   return region;
 706 }
 707
 708 template <typename REG, typename ARG>
 709 const REG *MemRegionManager::LazyAllocate(REG*& region, ARG a) {
 710   if (!region) {
 711     region = A.Allocate<REG>();
 712     new (region) REG(this, a);
 713   }
 714
 715   return region;
 716 }
 717
 718 const StackLocalsSpaceRegion*
 719 MemRegionManager::getStackLocalsRegion(const StackFrameContext *STC) {
 720   assert(STC);
 721   StackLocalsSpaceRegion *&R = StackLocalsSpaceRegions[STC];
 722
 723   if (R)
 724     return R;
 725
 726   R = A.Allocate<StackLocalsSpaceRegion>();
 727   new (R) StackLocalsSpaceRegion(this, STC);
 728   return R;
 729 }
 730
 731 const StackArgumentsSpaceRegion *
 732 MemRegionManager::getStackArgumentsRegion(const StackFrameContext *STC) {
 733   assert(STC);
 734   StackArgumentsSpaceRegion *&R = StackArgumentsSpaceRegions[STC];
 735
 736   if (R)
 737     return R;
 738
 739   R = A.Allocate<StackArgumentsSpaceRegion>();
 740   new (R) StackArgumentsSpaceRegion(this, STC);
 741   return R;
 742 }
 743
 744 const GlobalsSpaceRegion
 745 *MemRegionManager::getGlobalsRegion(MemRegion::Kind K,
 746                                     const CodeTextRegion *CR) {
 747   if (!CR) {
 748     if (K == MemRegion::GlobalSystemSpaceRegionKind)
 749       return LazyAllocate(SystemGlobals);
 750     if (K == MemRegion::GlobalImmutableSpaceRegionKind)
 751       return LazyAllocate(ImmutableGlobals);
 752     assert(K == MemRegion::GlobalInternalSpaceRegionKind);
 753     return LazyAllocate(InternalGlobals);
 754   }
 755
 756   assert(K == MemRegion::StaticGlobalSpaceRegionKind);
 757   StaticGlobalSpaceRegion *&R = StaticsGlobalSpaceRegions[CR];
 758   if (R)
 759     return R;
 760
 761   R = A.Allocate<StaticGlobalSpaceRegion>();
 762   new (R) StaticGlobalSpaceRegion(this, CR);
 763   return R;
 764 }
 765
 766 const HeapSpaceRegion *MemRegionManager::getHeapRegion() {
 767   return LazyAllocate(heap);
 768 }
 769
 770 const UnknownSpaceRegion *MemRegionManager::getUnknownRegion() {
 771   return LazyAllocate(unknown);
 772 }
 773
 774 const CodeSpaceRegion *MemRegionManager::getCodeRegion() {
 775   return LazyAllocate(code);
 776 }
 777
 778 //===----------------------------------------------------------------------===//
 779 // Constructing regions.
 780 //===----------------------------------------------------------------------===//
 781 const StringRegion* MemRegionManager::getStringRegion(const StringLiteral* Str){
 782   return getSubRegion<StringRegion>(Str, getGlobalsRegion());
 783 }
 784
 785 const ObjCStringRegion *
 786 MemRegionManager::getObjCStringRegion(const ObjCStringLiteral* Str){
 787   return getSubRegion<ObjCStringRegion>(Str, getGlobalsRegion());
 788 }
 789
 790 /// Look through a chain of LocationContexts to either find the
 791 /// StackFrameContext that matches a DeclContext, or find a VarRegion
 792 /// for a variable captured by a block.
 793 static llvm::PointerUnion<const StackFrameContext *, const VarRegion *>
 794 getStackOrCaptureRegionForDeclContext(const LocationContext *LC,
 795                                       const DeclContext *DC,
 796                                       const VarDecl *VD) {
 797   while (LC) {
 798     if (const StackFrameContext *SFC = dyn_cast<StackFrameContext>(LC)) {
 799       if (cast<DeclContext>(SFC->getDecl()) == DC)
 800         return SFC;
 801     }
 802     if (const BlockInvocationContext *BC =
 803         dyn_cast<BlockInvocationContext>(LC)) {
 804       const BlockDataRegion *BR =
 805         static_cast<const BlockDataRegion*>(BC->getContextData());
 806       // FIXME: This can be made more efficient.
 807       for (BlockDataRegion::referenced_vars_iterator
 808            I = BR->referenced_vars_begin(),
 809            E = BR->referenced_vars_end(); I != E; ++I) {
 810         if (const VarRegion *VR = dyn_cast<VarRegion>(I.getOriginalRegion()))
 811           if (VR->getDecl() == VD)
 812             return cast<VarRegion>(I.getCapturedRegion());
 813       }
 814     }
 815
 816     LC = LC->getParent();
 817   }
 818   return (const StackFrameContext *)nullptr;
 819 }
 820
 821 const VarRegion* MemRegionManager::getVarRegion(const VarDecl *D,
 822                                                 const LocationContext *LC) {
 823   const MemRegion *sReg = nullptr;
 824
 825   if (D->hasGlobalStorage() && !D->isStaticLocal()) {
 826
 827     // First handle the globals defined in system headers.
 828     if (C.getSourceManager().isInSystemHeader(D->getLocation())) {
 829       // Whitelist the system globals which often DO GET modified, assume the
 830       // rest are immutable.
 831       if (D->getName().find("errno") != StringRef::npos)
 832         sReg = getGlobalsRegion(MemRegion::GlobalSystemSpaceRegionKind);
 833       else
 834         sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind);
 835
 836     // Treat other globals as GlobalInternal unless they are constants.
 837     } else {
 838       QualType GQT = D->getType();
 839       const Type *GT = GQT.getTypePtrOrNull();
 840       // TODO: We could walk the complex types here and see if everything is
 841       // constified.
 842       if (GT && GQT.isConstQualified() && GT->isArithmeticType())
 843         sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind);
 844       else
 845         sReg = getGlobalsRegion();
 846     }
 847
 848   // Finally handle static locals.
 849   } else {
 850     // FIXME: Once we implement scope handling, we will need to properly lookup
 851     // 'D' to the proper LocationContext.
 852     const DeclContext *DC = D->getDeclContext();
 853     llvm::PointerUnion<const StackFrameContext *, const VarRegion *> V =
 854       getStackOrCaptureRegionForDeclContext(LC, DC, D);
 855
 856     if (V.is<const VarRegion*>())
 857       return V.get<const VarRegion*>();
 858
 859     const StackFrameContext *STC = V.get<const StackFrameContext*>();
 860
 861     if (!STC)
 862       sReg = getUnknownRegion();
 863     else {
 864       if (D->hasLocalStorage()) {
 865         sReg = isa<ParmVarDecl>(D) || isa<ImplicitParamDecl>(D)
 866                ? static_cast<const MemRegion*>(getStackArgumentsRegion(STC))
 867                : static_cast<const MemRegion*>(getStackLocalsRegion(STC));
 868       }
 869       else {
 870         assert(D->isStaticLocal());
 871         const Decl *STCD = STC->getDecl();
 872         if (isa<FunctionDecl>(STCD) || isa<ObjCMethodDecl>(STCD))
 873           sReg = getGlobalsRegion(MemRegion::StaticGlobalSpaceRegionKind,
 874                                   getFunctionCodeRegion(cast<NamedDecl>(STCD)));
 875         else if (const BlockDecl *BD = dyn_cast<BlockDecl>(STCD)) {
 876           // FIXME: The fallback type here is totally bogus -- though it should
 877           // never be queried, it will prevent uniquing with the real
 878           // BlockCodeRegion. Ideally we'd fix the AST so that we always had a
 879           // signature.
 880           QualType T;
 881           if (const TypeSourceInfo *TSI = BD->getSignatureAsWritten())
 882             T = TSI->getType();
 883           if (T.isNull())
 884             T = getContext().VoidTy;
 885           if (!T->getAs<FunctionType>())
 886             T = getContext().getFunctionNoProtoType(T);
 887           T = getContext().getBlockPointerType(T);
 888
 889           const BlockCodeRegion *BTR =
 890             getBlockCodeRegion(BD, C.getCanonicalType(T),
 891                                STC->getAnalysisDeclContext());
 892           sReg = getGlobalsRegion(MemRegion::StaticGlobalSpaceRegionKind,
 893                                   BTR);
 894         }
 895         else {
 896           sReg = getGlobalsRegion();
 897         }
 898       }
 899     }
 900   }
 901
 902   return getSubRegion<VarRegion>(D, sReg);
 903 }
 904
 905 const VarRegion *MemRegionManager::getVarRegion(const VarDecl *D,
 906                                                 const MemRegion *superR) {
 907   return getSubRegion<VarRegion>(D, superR);
 908 }
 909
 910 const BlockDataRegion *
 911 MemRegionManager::getBlockDataRegion(const BlockCodeRegion *BC,
 912                                      const LocationContext *LC,
 913                                      unsigned blockCount) {
 914   const MemRegion *sReg = nullptr;
 915   const BlockDecl *BD = BC->getDecl();
 916   if (!BD->hasCaptures()) {
 917     // This handles 'static' blocks.
 918     sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind);
 919   }
 920   else {
 921     if (LC) {
 922       // FIXME: Once we implement scope handling, we want the parent region
 923       // to be the scope.
 924       const StackFrameContext *STC = LC->getCurrentStackFrame();
 925       assert(STC);
 926       sReg = getStackLocalsRegion(STC);
 927     }
 928     else {
 929       // We allow 'LC' to be NULL for cases where want BlockDataRegions
 930       // without context-sensitivity.
 931       sReg = getUnknownRegion();
 932     }
 933   }
 934
 935   return getSubRegion<BlockDataRegion>(BC, LC, blockCount, sReg);
 936 }
 937
 938 const CXXTempObjectRegion *
 939 MemRegionManager::getCXXStaticTempObjectRegion(const Expr *Ex) {
 940   return getSubRegion<CXXTempObjectRegion>(
 941       Ex, getGlobalsRegion(MemRegion::GlobalInternalSpaceRegionKind, nullptr));
 942 }
 943
 944 const CompoundLiteralRegion*
 945 MemRegionManager::getCompoundLiteralRegion(const CompoundLiteralExpr *CL,
 946                                            const LocationContext *LC) {
 947   const MemRegion *sReg = nullptr;
 948
 949   if (CL->isFileScope())
 950     sReg = getGlobalsRegion();
 951   else {
 952     const StackFrameContext *STC = LC->getCurrentStackFrame();
 953     assert(STC);
 954     sReg = getStackLocalsRegion(STC);
 955   }
 956
 957   return getSubRegion<CompoundLiteralRegion>(CL, sReg);
 958 }
 959
 960 const ElementRegion*
 961 MemRegionManager::getElementRegion(QualType elementType, NonLoc Idx,
 962                                    const MemRegion* superRegion,
 963                                    ASTContext &Ctx){
 964   QualType T = Ctx.getCanonicalType(elementType).getUnqualifiedType();
 965
 966   llvm::FoldingSetNodeID ID;
 967   ElementRegion::ProfileRegion(ID, T, Idx, superRegion);
 968
 969   void *InsertPos;
 970   MemRegion* data = Regions.FindNodeOrInsertPos(ID, InsertPos);
 971   ElementRegion* R = cast_or_null<ElementRegion>(data);
 972
 973   if (!R) {
 974     R = A.Allocate<ElementRegion>();
 975     new (R) ElementRegion(T, Idx, superRegion);
 976     Regions.InsertNode(R, InsertPos);
 977   }
 978
 979   return R;
 980 }
 981
 982 const FunctionCodeRegion *
 983 MemRegionManager::getFunctionCodeRegion(const NamedDecl *FD) {
 984   return getSubRegion<FunctionCodeRegion>(FD, getCodeRegion());
 985 }
 986
 987 const BlockCodeRegion *
 988 MemRegionManager::getBlockCodeRegion(const BlockDecl *BD, CanQualType locTy,
 989                                      AnalysisDeclContext *AC) {
 990   return getSubRegion<BlockCodeRegion>(BD, locTy, AC, getCodeRegion());
 991 }
 992
 993
 994 /// getSymbolicRegion - Retrieve or create a "symbolic" memory region.
 995 const SymbolicRegion *MemRegionManager::getSymbolicRegion(SymbolRef sym) {
 996   return getSubRegion<SymbolicRegion>(sym, getUnknownRegion());
 997 }
 998
 999 const SymbolicRegion *MemRegionManager::getSymbolicHeapRegion(SymbolRef Sym) {
1000   return getSubRegion<SymbolicRegion>(Sym, getHeapRegion());
1001 }
1002
1003 const FieldRegion*
1004 MemRegionManager::getFieldRegion(const FieldDecl *d,
1005                                  const MemRegion* superRegion){
1006   return getSubRegion<FieldRegion>(d, superRegion);
1007 }
1008
1009 const ObjCIvarRegion*
1010 MemRegionManager::getObjCIvarRegion(const ObjCIvarDecl *d,
1011                                     const MemRegion* superRegion) {
1012   return getSubRegion<ObjCIvarRegion>(d, superRegion);
1013 }
1014
1015 const CXXTempObjectRegion*
1016 MemRegionManager::getCXXTempObjectRegion(Expr const *E,
1017                                          LocationContext const *LC) {
1018   const StackFrameContext *SFC = LC->getCurrentStackFrame();
1019   assert(SFC);
1020   return getSubRegion<CXXTempObjectRegion>(E, getStackLocalsRegion(SFC));
1021 }
1022
1023 /// Checks whether \p BaseClass is a valid virtual or direct non-virtual base
1024 /// class of the type of \p Super.
1025 static bool isValidBaseClass(const CXXRecordDecl *BaseClass,
1026                              const TypedValueRegion *Super,
1027                              bool IsVirtual) {
1028   BaseClass = BaseClass->getCanonicalDecl();
1029
1030   const CXXRecordDecl *Class = Super->getValueType()->getAsCXXRecordDecl();
1031   if (!Class)
1032     return true;
1033
1034   if (IsVirtual)
1035     return Class->isVirtuallyDerivedFrom(BaseClass);
1036
1037   for (const auto &I : Class->bases()) {
1038     if (I.getType()->getAsCXXRecordDecl()->getCanonicalDecl() == BaseClass)
1039       return true;
1040   }
1041
1042   return false;
1043 }
1044
1045 const CXXBaseObjectRegion *
1046 MemRegionManager::getCXXBaseObjectRegion(const CXXRecordDecl *RD,
1047                                          const MemRegion *Super,
1048                                          bool IsVirtual) {
1049   if (isa<TypedValueRegion>(Super)) {
1050     assert(isValidBaseClass(RD, dyn_cast<TypedValueRegion>(Super), IsVirtual));
1051     (void)&isValidBaseClass;
1052
1053     if (IsVirtual) {
1054       // Virtual base regions should not be layered, since the layout rules
1055       // are different.
1056       while (const CXXBaseObjectRegion *Base =
1057                dyn_cast<CXXBaseObjectRegion>(Super)) {
1058         Super = Base->getSuperRegion();
1059       }
1060       assert(Super && !isa<MemSpaceRegion>(Super));
1061     }
1062   }
1063
1064   return getSubRegion<CXXBaseObjectRegion>(RD, IsVirtual, Super);
1065 }
1066
1067 const CXXThisRegion*
1068 MemRegionManager::getCXXThisRegion(QualType thisPointerTy,
1069                                    const LocationContext *LC) {
1070   const PointerType *PT = thisPointerTy->getAs<PointerType>();
1071   assert(PT);
1072   // Inside the body of the operator() of a lambda a this expr might refer to an
1073   // object in one of the parent location contexts.
1074   const auto *D = dyn_cast<CXXMethodDecl>(LC->getDecl());
1075   // FIXME: when operator() of lambda is analyzed as a top level function and
1076   // 'this' refers to a this to the enclosing scope, there is no right region to
1077   // return.
1078   while (!LC->inTopFrame() &&
1079          (!D || D->isStatic() ||
1080           PT != D->getThisType(getContext())->getAs<PointerType>())) {
1081     LC = LC->getParent();
1082     D = dyn_cast<CXXMethodDecl>(LC->getDecl());
1083   }
1084   const StackFrameContext *STC = LC->getCurrentStackFrame();
1085   assert(STC);
1086   return getSubRegion<CXXThisRegion>(PT, getStackArgumentsRegion(STC));
1087 }
1088
1089 const AllocaRegion*
1090 MemRegionManager::getAllocaRegion(const Expr *E, unsigned cnt,
1091                                   const LocationContext *LC) {
1092   const StackFrameContext *STC = LC->getCurrentStackFrame();
1093   assert(STC);
1094   return getSubRegion<AllocaRegion>(E, cnt, getStackLocalsRegion(STC));
1095 }
1096
1097 const MemSpaceRegion *MemRegion::getMemorySpace() const {
1098   const MemRegion *R = this;
1099   const SubRegion* SR = dyn_cast<SubRegion>(this);
1100
1101   while (SR) {
1102     R = SR->getSuperRegion();
1103     SR = dyn_cast<SubRegion>(R);
1104   }
1105
1106   return dyn_cast<MemSpaceRegion>(R);
1107 }
1108
1109 bool MemRegion::hasStackStorage() const {
1110   return isa<StackSpaceRegion>(getMemorySpace());
1111 }
1112
1113 bool MemRegion::hasStackNonParametersStorage() const {
1114   return isa<StackLocalsSpaceRegion>(getMemorySpace());
1115 }
1116
1117 bool MemRegion::hasStackParametersStorage() const {
1118   return isa<StackArgumentsSpaceRegion>(getMemorySpace());
1119 }
1120
1121 bool MemRegion::hasGlobalsOrParametersStorage() const {
1122   const MemSpaceRegion *MS = getMemorySpace();
1123   return isa<StackArgumentsSpaceRegion>(MS) ||
1124          isa<GlobalsSpaceRegion>(MS);
1125 }
1126
1127 // getBaseRegion strips away all elements and fields, and get the base region
1128 // of them.
1129 const MemRegion *MemRegion::getBaseRegion() const {
1130   const MemRegion *R = this;
1131   while (true) {
1132     switch (R->getKind()) {
1133       case MemRegion::ElementRegionKind:
1134       case MemRegion::FieldRegionKind:
1135       case MemRegion::ObjCIvarRegionKind:
1136       case MemRegion::CXXBaseObjectRegionKind:
1137         R = cast<SubRegion>(R)->getSuperRegion();
1138         continue;
1139       default:
1140         break;
1141     }
1142     break;
1143   }
1144   return R;
1145 }
1146
1147 bool MemRegion::isSubRegionOf(const MemRegion *R) const {
1148   return false;
1149 }
1150
1151 //===----------------------------------------------------------------------===//
1152 // View handling.
1153 //===----------------------------------------------------------------------===//
1154
1155 const MemRegion *MemRegion::StripCasts(bool StripBaseCasts) const {
1156   const MemRegion *R = this;
1157   while (true) {
1158     switch (R->getKind()) {
1159     case ElementRegionKind: {
1160       const ElementRegion *ER = cast<ElementRegion>(R);
1161       if (!ER->getIndex().isZeroConstant())
1162         return R;
1163       R = ER->getSuperRegion();
1164       break;
1165     }
1166     case CXXBaseObjectRegionKind:
1167       if (!StripBaseCasts)
1168         return R;
1169       R = cast<CXXBaseObjectRegion>(R)->getSuperRegion();
1170       break;
1171     default:
1172       return R;
1173     }
1174   }
1175 }
1176
1177 const SymbolicRegion *MemRegion::getSymbolicBase() const {
1178   const SubRegion *SubR = dyn_cast<SubRegion>(this);
1179
1180   while (SubR) {
1181     if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(SubR))
1182       return SymR;
1183     SubR = dyn_cast<SubRegion>(SubR->getSuperRegion());
1184   }
1185   return nullptr;
1186 }
1187
1188 RegionRawOffset ElementRegion::getAsArrayOffset() const {
1189   CharUnits offset = CharUnits::Zero();
1190   const ElementRegion *ER = this;
1191   const MemRegion *superR = nullptr;
1192   ASTContext &C = getContext();
1193
1194   // FIXME: Handle multi-dimensional arrays.
1195
1196   while (ER) {
1197     superR = ER->getSuperRegion();
1198
1199     // FIXME: generalize to symbolic offsets.
1200     SVal index = ER->getIndex();
1201     if (Optional<nonloc::ConcreteInt> CI = index.getAs<nonloc::ConcreteInt>()) {
1202       // Update the offset.
1203       int64_t i = CI->getValue().getSExtValue();
1204
1205       if (i != 0) {
1206         QualType elemType = ER->getElementType();
1207
1208         // If we are pointing to an incomplete type, go no further.
1209         if (elemType->isIncompleteType()) {
1210           superR = ER;
1211           break;
1212         }
1213
1214         CharUnits size = C.getTypeSizeInChars(elemType);
1215         offset += (i * size);
1216       }
1217
1218       // Go to the next ElementRegion (if any).
1219       ER = dyn_cast<ElementRegion>(superR);
1220       continue;
1221     }
1222
1223     return nullptr;
1224   }
1225
1226   assert(superR && "super region cannot be NULL");
1227   return RegionRawOffset(superR, offset);
1228 }
1229
1230
1231 /// Returns true if \p Base is an immediate base class of \p Child
1232 static bool isImmediateBase(const CXXRecordDecl *Child,
1233                             const CXXRecordDecl *Base) {
1234   assert(Child && "Child must not be null");
1235   // Note that we do NOT canonicalize the base class here, because
1236   // ASTRecordLayout doesn't either. If that leads us down the wrong path,
1237   // so be it; at least we won't crash.
1238   for (const auto &I : Child->bases()) {
1239     if (I.getType()->getAsCXXRecordDecl() == Base)
1240       return true;
1241   }
1242
1243   return false;
1244 }
1245
1246 RegionOffset MemRegion::getAsOffset() const {
1247   const MemRegion *R = this;
1248   const MemRegion *SymbolicOffsetBase = nullptr;
1249   int64_t Offset = 0;
1250
1251   while (1) {
1252     switch (R->getKind()) {
1253     case CodeSpaceRegionKind:
1254     case StackLocalsSpaceRegionKind:
1255     case StackArgumentsSpaceRegionKind:
1256     case HeapSpaceRegionKind:
1257     case UnknownSpaceRegionKind:
1258     case StaticGlobalSpaceRegionKind:
1259     case GlobalInternalSpaceRegionKind:
1260     case GlobalSystemSpaceRegionKind:
1261     case GlobalImmutableSpaceRegionKind:
1262       // Stores can bind directly to a region space to set a default value.
1263       assert(Offset == 0 && !SymbolicOffsetBase);
1264       goto Finish;
1265
1266     case FunctionCodeRegionKind:
1267     case BlockCodeRegionKind:
1268     case BlockDataRegionKind:
1269       // These will never have bindings, but may end up having values requested
1270       // if the user does some strange casting.
1271       if (Offset != 0)
1272         SymbolicOffsetBase = R;
1273       goto Finish;
1274
1275     case SymbolicRegionKind:
1276     case AllocaRegionKind:
1277     case CompoundLiteralRegionKind:
1278     case CXXThisRegionKind:
1279     case StringRegionKind:
1280     case ObjCStringRegionKind:
1281     case VarRegionKind:
1282     case CXXTempObjectRegionKind:
1283       // Usual base regions.
1284       goto Finish;
1285
1286     case ObjCIvarRegionKind:
1287       // This is a little strange, but it's a compromise between
1288       // ObjCIvarRegions having unknown compile-time offsets (when using the
1289       // non-fragile runtime) and yet still being distinct, non-overlapping
1290       // regions. Thus we treat them as "like" base regions for the purposes
1291       // of computing offsets.
1292       goto Finish;
1293
1294     case CXXBaseObjectRegionKind: {
1295       const CXXBaseObjectRegion *BOR = cast<CXXBaseObjectRegion>(R);
1296       R = BOR->getSuperRegion();
1297
1298       QualType Ty;
1299       bool RootIsSymbolic = false;
1300       if (const TypedValueRegion *TVR = dyn_cast<TypedValueRegion>(R)) {
1301         Ty = TVR->getDesugaredValueType(getContext());
1302       } else if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) {
1303         // If our base region is symbolic, we don't know what type it really is.
1304         // Pretend the type of the symbol is the true dynamic type.
1305         // (This will at least be self-consistent for the life of the symbol.)
1306         Ty = SR->getSymbol()->getType()->getPointeeType();
1307         RootIsSymbolic = true;
1308       }
1309
1310       const CXXRecordDecl *Child = Ty->getAsCXXRecordDecl();
1311       if (!Child) {
1312         // We cannot compute the offset of the base class.
1313         SymbolicOffsetBase = R;
1314       } else {
1315         if (RootIsSymbolic) {
1316           // Base layers on symbolic regions may not be type-correct.
1317           // Double-check the inheritance here, and revert to a symbolic offset
1318           // if it's invalid (e.g. due to a reinterpret_cast).
1319           if (BOR->isVirtual()) {
1320             if (!Child->isVirtuallyDerivedFrom(BOR->getDecl()))
1321               SymbolicOffsetBase = R;
1322           } else {
1323             if (!isImmediateBase(Child, BOR->getDecl()))
1324               SymbolicOffsetBase = R;
1325           }
1326         }
1327       }
1328
1329       // Don't bother calculating precise offsets if we already have a
1330       // symbolic offset somewhere in the chain.
1331       if (SymbolicOffsetBase)
1332         continue;
1333
1334       CharUnits BaseOffset;
1335       const ASTRecordLayout &Layout = getContext().getASTRecordLayout(Child);
1336       if (BOR->isVirtual())
1337         BaseOffset = Layout.getVBaseClassOffset(BOR->getDecl());
1338       else
1339         BaseOffset = Layout.getBaseClassOffset(BOR->getDecl());
1340
1341       // The base offset is in chars, not in bits.
1342       Offset += BaseOffset.getQuantity() * getContext().getCharWidth();
1343       break;
1344     }
1345     case ElementRegionKind: {
1346       const ElementRegion *ER = cast<ElementRegion>(R);
1347       R = ER->getSuperRegion();
1348
1349       QualType EleTy = ER->getValueType();
1350       if (EleTy->isIncompleteType()) {
1351         // We cannot compute the offset of the base class.
1352         SymbolicOffsetBase = R;
1353         continue;
1354       }
1355
1356       SVal Index = ER->getIndex();
1357       if (Optional<nonloc::ConcreteInt> CI =
1358               Index.getAs<nonloc::ConcreteInt>()) {
1359         // Don't bother calculating precise offsets if we already have a
1360         // symbolic offset somewhere in the chain.
1361         if (SymbolicOffsetBase)
1362           continue;
1363
1364         int64_t i = CI->getValue().getSExtValue();
1365         // This type size is in bits.
1366         Offset += i * getContext().getTypeSize(EleTy);
1367       } else {
1368         // We cannot compute offset for non-concrete index.
1369         SymbolicOffsetBase = R;
1370       }
1371       break;
1372     }
1373     case FieldRegionKind: {
1374       const FieldRegion *FR = cast<FieldRegion>(R);
1375       R = FR->getSuperRegion();
1376
1377       const RecordDecl *RD = FR->getDecl()->getParent();
1378       if (RD->isUnion() || !RD->isCompleteDefinition()) {
1379         // We cannot compute offset for incomplete type.
1380         // For unions, we could treat everything as offset 0, but we'd rather
1381         // treat each field as a symbolic offset so they aren't stored on top
1382         // of each other, since we depend on things in typed regions actually
1383         // matching their types.
1384         SymbolicOffsetBase = R;
1385       }
1386
1387       // Don't bother calculating precise offsets if we already have a
1388       // symbolic offset somewhere in the chain.
1389       if (SymbolicOffsetBase)
1390         continue;
1391
1392       // Get the field number.
1393       unsigned idx = 0;
1394       for (RecordDecl::field_iterator FI = RD->field_begin(),
1395              FE = RD->field_end(); FI != FE; ++FI, ++idx) {
1396         if (FR->getDecl() == *FI)
1397           break;
1398       }
1399       const ASTRecordLayout &Layout = getContext().getASTRecordLayout(RD);
1400       // This is offset in bits.
1401       Offset += Layout.getFieldOffset(idx);
1402       break;
1403     }
1404     }
1405   }
1406
1407  Finish:
1408   if (SymbolicOffsetBase)
1409     return RegionOffset(SymbolicOffsetBase, RegionOffset::Symbolic);
1410   return RegionOffset(R, Offset);
1411 }
1412
1413 //===----------------------------------------------------------------------===//
1414 // BlockDataRegion
1415 //===----------------------------------------------------------------------===//
1416
1417 std::pair<const VarRegion *, const VarRegion *>
1418 BlockDataRegion::getCaptureRegions(const VarDecl *VD) {
1419   MemRegionManager &MemMgr = *getMemRegionManager();
1420   const VarRegion *VR = nullptr;
1421   const VarRegion *OriginalVR = nullptr;
1422
1423   if (!VD->hasAttr<BlocksAttr>() && VD->hasLocalStorage()) {
1424     VR = MemMgr.getVarRegion(VD, this);
1425     OriginalVR = MemMgr.getVarRegion(VD, LC);
1426   }
1427   else {
1428     if (LC) {
1429       VR = MemMgr.getVarRegion(VD, LC);
1430       OriginalVR = VR;
1431     }
1432     else {
1433       VR = MemMgr.getVarRegion(VD, MemMgr.getUnknownRegion());
1434       OriginalVR = MemMgr.getVarRegion(VD, LC);
1435     }
1436   }
1437   return std::make_pair(VR, OriginalVR);
1438 }
1439
1440 void BlockDataRegion::LazyInitializeReferencedVars() {
1441   if (ReferencedVars)
1442     return;
1443
1444   AnalysisDeclContext *AC = getCodeRegion()->getAnalysisDeclContext();
1445   const auto &ReferencedBlockVars = AC->getReferencedBlockVars(BC->getDecl());
1446   auto NumBlockVars =
1447       std::distance(ReferencedBlockVars.begin(), ReferencedBlockVars.end());
1448
1449   if (NumBlockVars == 0) {
1450     ReferencedVars = (void*) 0x1;
1451     return;
1452   }
1453
1454   MemRegionManager &MemMgr = *getMemRegionManager();
1455   llvm::BumpPtrAllocator &A = MemMgr.getAllocator();
1456   BumpVectorContext BC(A);
1457
1458   typedef BumpVector<const MemRegion*> VarVec;
1459   VarVec *BV = A.Allocate<VarVec>();
1460   new (BV) VarVec(BC, NumBlockVars);
1461   VarVec *BVOriginal = A.Allocate<VarVec>();
1462   new (BVOriginal) VarVec(BC, NumBlockVars);
1463
1464   for (const VarDecl *VD : ReferencedBlockVars) {
1465     const VarRegion *VR = nullptr;
1466     const VarRegion *OriginalVR = nullptr;
1467     std::tie(VR, OriginalVR) = getCaptureRegions(VD);
1468     assert(VR);
1469     assert(OriginalVR);
1470     BV->push_back(VR, BC);
1471     BVOriginal->push_back(OriginalVR, BC);
1472   }
1473
1474   ReferencedVars = BV;
1475   OriginalVars = BVOriginal;
1476 }
1477
1478 BlockDataRegion::referenced_vars_iterator
1479 BlockDataRegion::referenced_vars_begin() const {
1480   const_cast<BlockDataRegion*>(this)->LazyInitializeReferencedVars();
1481
1482   BumpVector<const MemRegion*> *Vec =
1483     static_cast<BumpVector<const MemRegion*>*>(ReferencedVars);
1484
1485   if (Vec == (void*) 0x1)
1486     return BlockDataRegion::referenced_vars_iterator(nullptr, nullptr);
1487
1488   BumpVector<const MemRegion*> *VecOriginal =
1489     static_cast<BumpVector<const MemRegion*>*>(OriginalVars);
1490
1491   return BlockDataRegion::referenced_vars_iterator(Vec->begin(),
1492                                                    VecOriginal->begin());
1493 }
1494
1495 BlockDataRegion::referenced_vars_iterator
1496 BlockDataRegion::referenced_vars_end() const {
1497   const_cast<BlockDataRegion*>(this)->LazyInitializeReferencedVars();
1498
1499   BumpVector<const MemRegion*> *Vec =
1500     static_cast<BumpVector<const MemRegion*>*>(ReferencedVars);
1501
1502   if (Vec == (void*) 0x1)
1503     return BlockDataRegion::referenced_vars_iterator(nullptr, nullptr);
1504
1505   BumpVector<const MemRegion*> *VecOriginal =
1506     static_cast<BumpVector<const MemRegion*>*>(OriginalVars);
1507
1508   return BlockDataRegion::referenced_vars_iterator(Vec->end(),
1509                                                    VecOriginal->end());
1510 }
1511
1512 const VarRegion *BlockDataRegion::getOriginalRegion(const VarRegion *R) const {
1513   for (referenced_vars_iterator I = referenced_vars_begin(),
1514                                 E = referenced_vars_end();
1515        I != E; ++I) {
1516     if (I.getCapturedRegion() == R)
1517       return I.getOriginalRegion();
1518   }
1519   return nullptr;
1520 }
1521
1522 //===----------------------------------------------------------------------===//
1523 // RegionAndSymbolInvalidationTraits
1524 //===----------------------------------------------------------------------===//
1525
1526 void RegionAndSymbolInvalidationTraits::setTrait(SymbolRef Sym,
1527                                                  InvalidationKinds IK) {
1528   SymTraitsMap[Sym] |= IK;
1529 }
1530
1531 void RegionAndSymbolInvalidationTraits::setTrait(const MemRegion *MR,
1532                                                  InvalidationKinds IK) {
1533   assert(MR);
1534   if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR))
1535     setTrait(SR->getSymbol(), IK);
1536   else
1537     MRTraitsMap[MR] |= IK;
1538 }
1539
1540 bool RegionAndSymbolInvalidationTraits::hasTrait(SymbolRef Sym,
1541                                                  InvalidationKinds IK) const {
1542   const_symbol_iterator I = SymTraitsMap.find(Sym);
1543   if (I != SymTraitsMap.end())
1544     return I->second & IK;
1545
1546   return false;
1547 }
1548
1549 bool RegionAndSymbolInvalidationTraits::hasTrait(const MemRegion *MR,
1550                                                  InvalidationKinds IK) const {
1551   if (!MR)
1552     return false;
1553
1554   if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR))
1555     return hasTrait(SR->getSymbol(), IK);
1556
1557   const_region_iterator I = MRTraitsMap.find(MR);
1558   if (I != MRTraitsMap.end())
1559     return I->second & IK;
1560
1561   return false;
1562 }