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