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