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

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