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