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