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