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     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     if (Size.isZeroConstant()) {
776       if (isa<ConstantArrayType>(Ty))
777         return UnknownVal();
778     }
779 
780     return Size;
781   }
782     // FIXME: The following are being used in 'SimpleSValBuilder' and in
783     // 'ArrayBoundChecker::checkLocation' because there is no symbol to
784     // represent the regions more appropriately.
785   case MemRegion::BlockDataRegionKind:
786   case MemRegion::BlockCodeRegionKind:
787   case MemRegion::FunctionCodeRegionKind:
788     return nonloc::SymbolVal(SymMgr.getExtentSymbol(SR));
789   default:
790     llvm_unreachable("Unhandled region");
791   }
792 }
793 
794 template <typename REG>
795 const REG *MemRegionManager::LazyAllocate(REG*& region) {
796   if (!region) {
797     region = A.Allocate<REG>();
798     new (region) REG(*this);
799   }
800 
801   return region;
802 }
803 
804 template <typename REG, typename ARG>
805 const REG *MemRegionManager::LazyAllocate(REG*& region, ARG a) {
806   if (!region) {
807     region = A.Allocate<REG>();
808     new (region) REG(this, a);
809   }
810 
811   return region;
812 }
813 
814 const StackLocalsSpaceRegion*
815 MemRegionManager::getStackLocalsRegion(const StackFrameContext *STC) {
816   assert(STC);
817   StackLocalsSpaceRegion *&R = StackLocalsSpaceRegions[STC];
818 
819   if (R)
820     return R;
821 
822   R = A.Allocate<StackLocalsSpaceRegion>();
823   new (R) StackLocalsSpaceRegion(*this, STC);
824   return R;
825 }
826 
827 const StackArgumentsSpaceRegion *
828 MemRegionManager::getStackArgumentsRegion(const StackFrameContext *STC) {
829   assert(STC);
830   StackArgumentsSpaceRegion *&R = StackArgumentsSpaceRegions[STC];
831 
832   if (R)
833     return R;
834 
835   R = A.Allocate<StackArgumentsSpaceRegion>();
836   new (R) StackArgumentsSpaceRegion(*this, STC);
837   return R;
838 }
839 
840 const GlobalsSpaceRegion
841 *MemRegionManager::getGlobalsRegion(MemRegion::Kind K,
842                                     const CodeTextRegion *CR) {
843   if (!CR) {
844     if (K == MemRegion::GlobalSystemSpaceRegionKind)
845       return LazyAllocate(SystemGlobals);
846     if (K == MemRegion::GlobalImmutableSpaceRegionKind)
847       return LazyAllocate(ImmutableGlobals);
848     assert(K == MemRegion::GlobalInternalSpaceRegionKind);
849     return LazyAllocate(InternalGlobals);
850   }
851 
852   assert(K == MemRegion::StaticGlobalSpaceRegionKind);
853   StaticGlobalSpaceRegion *&R = StaticsGlobalSpaceRegions[CR];
854   if (R)
855     return R;
856 
857   R = A.Allocate<StaticGlobalSpaceRegion>();
858   new (R) StaticGlobalSpaceRegion(*this, CR);
859   return R;
860 }
861 
862 const HeapSpaceRegion *MemRegionManager::getHeapRegion() {
863   return LazyAllocate(heap);
864 }
865 
866 const UnknownSpaceRegion *MemRegionManager::getUnknownRegion() {
867   return LazyAllocate(unknown);
868 }
869 
870 const CodeSpaceRegion *MemRegionManager::getCodeRegion() {
871   return LazyAllocate(code);
872 }
873 
874 //===----------------------------------------------------------------------===//
875 // Constructing regions.
876 //===----------------------------------------------------------------------===//
877 
878 const StringRegion *MemRegionManager::getStringRegion(const StringLiteral *Str){
879   return getSubRegion<StringRegion>(
880       Str, cast<GlobalInternalSpaceRegion>(getGlobalsRegion()));
881 }
882 
883 const ObjCStringRegion *
884 MemRegionManager::getObjCStringRegion(const ObjCStringLiteral *Str){
885   return getSubRegion<ObjCStringRegion>(
886       Str, cast<GlobalInternalSpaceRegion>(getGlobalsRegion()));
887 }
888 
889 /// Look through a chain of LocationContexts to either find the
890 /// StackFrameContext that matches a DeclContext, or find a VarRegion
891 /// for a variable captured by a block.
892 static llvm::PointerUnion<const StackFrameContext *, const VarRegion *>
893 getStackOrCaptureRegionForDeclContext(const LocationContext *LC,
894                                       const DeclContext *DC,
895                                       const VarDecl *VD) {
896   while (LC) {
897     if (const auto *SFC = dyn_cast<StackFrameContext>(LC)) {
898       if (cast<DeclContext>(SFC->getDecl()) == DC)
899         return SFC;
900     }
901     if (const auto *BC = dyn_cast<BlockInvocationContext>(LC)) {
902       const auto *BR = static_cast<const BlockDataRegion *>(BC->getData());
903       // FIXME: This can be made more efficient.
904       for (BlockDataRegion::referenced_vars_iterator
905            I = BR->referenced_vars_begin(),
906            E = BR->referenced_vars_end(); I != E; ++I) {
907         const TypedValueRegion *OrigR = I.getOriginalRegion();
908         if (const auto *VR = dyn_cast<VarRegion>(OrigR)) {
909           if (VR->getDecl() == VD)
910             return cast<VarRegion>(I.getCapturedRegion());
911         }
912       }
913     }
914 
915     LC = LC->getParent();
916   }
917   return (const StackFrameContext *)nullptr;
918 }
919 
920 const VarRegion *MemRegionManager::getVarRegion(const VarDecl *D,
921                                                 const LocationContext *LC) {
922   const auto *PVD = dyn_cast<ParmVarDecl>(D);
923   if (PVD) {
924     unsigned Index = PVD->getFunctionScopeIndex();
925     const StackFrameContext *SFC = LC->getStackFrame();
926     const Stmt *CallSite = SFC->getCallSite();
927     if (CallSite) {
928       const Decl *D = SFC->getDecl();
929       if (const auto *FD = dyn_cast<FunctionDecl>(D)) {
930         if (Index < FD->param_size() && FD->parameters()[Index] == PVD)
931           return getSubRegion<ParamVarRegion>(cast<Expr>(CallSite), Index,
932                                               getStackArgumentsRegion(SFC));
933       } else if (const auto *BD = dyn_cast<BlockDecl>(D)) {
934         if (Index < BD->param_size() && BD->parameters()[Index] == PVD)
935           return getSubRegion<ParamVarRegion>(cast<Expr>(CallSite), Index,
936                                               getStackArgumentsRegion(SFC));
937       } else {
938         return getSubRegion<ParamVarRegion>(cast<Expr>(CallSite), Index,
939                                             getStackArgumentsRegion(SFC));
940       }
941     }
942   }
943 
944   D = D->getCanonicalDecl();
945   const MemRegion *sReg = nullptr;
946 
947   if (D->hasGlobalStorage() && !D->isStaticLocal()) {
948 
949     // First handle the globals defined in system headers.
950     if (Ctx.getSourceManager().isInSystemHeader(D->getLocation())) {
951       // Whitelist the system globals which often DO GET modified, assume the
952       // rest are immutable.
953       if (D->getName().find("errno") != StringRef::npos)
954         sReg = getGlobalsRegion(MemRegion::GlobalSystemSpaceRegionKind);
955       else
956         sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind);
957 
958     // Treat other globals as GlobalInternal unless they are constants.
959     } else {
960       QualType GQT = D->getType();
961       const Type *GT = GQT.getTypePtrOrNull();
962       // TODO: We could walk the complex types here and see if everything is
963       // constified.
964       if (GT && GQT.isConstQualified() && GT->isArithmeticType())
965         sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind);
966       else
967         sReg = getGlobalsRegion();
968     }
969 
970   // Finally handle static locals.
971   } else {
972     // FIXME: Once we implement scope handling, we will need to properly lookup
973     // 'D' to the proper LocationContext.
974     const DeclContext *DC = D->getDeclContext();
975     llvm::PointerUnion<const StackFrameContext *, const VarRegion *> V =
976       getStackOrCaptureRegionForDeclContext(LC, DC, D);
977 
978     if (V.is<const VarRegion*>())
979       return V.get<const VarRegion*>();
980 
981     const auto *STC = V.get<const StackFrameContext *>();
982 
983     if (!STC) {
984       // FIXME: Assign a more sensible memory space to static locals
985       // we see from within blocks that we analyze as top-level declarations.
986       sReg = getUnknownRegion();
987     } else {
988       if (D->hasLocalStorage()) {
989         sReg = isa<ParmVarDecl>(D) || isa<ImplicitParamDecl>(D)
990                ? static_cast<const MemRegion*>(getStackArgumentsRegion(STC))
991                : static_cast<const MemRegion*>(getStackLocalsRegion(STC));
992       }
993       else {
994         assert(D->isStaticLocal());
995         const Decl *STCD = STC->getDecl();
996         if (isa<FunctionDecl>(STCD) || isa<ObjCMethodDecl>(STCD))
997           sReg = getGlobalsRegion(MemRegion::StaticGlobalSpaceRegionKind,
998                                   getFunctionCodeRegion(cast<NamedDecl>(STCD)));
999         else if (const auto *BD = dyn_cast<BlockDecl>(STCD)) {
1000           // FIXME: The fallback type here is totally bogus -- though it should
1001           // never be queried, it will prevent uniquing with the real
1002           // BlockCodeRegion. Ideally we'd fix the AST so that we always had a
1003           // signature.
1004           QualType T;
1005           if (const TypeSourceInfo *TSI = BD->getSignatureAsWritten())
1006             T = TSI->getType();
1007           if (T.isNull())
1008             T = getContext().VoidTy;
1009           if (!T->getAs<FunctionType>())
1010             T = getContext().getFunctionNoProtoType(T);
1011           T = getContext().getBlockPointerType(T);
1012 
1013           const BlockCodeRegion *BTR =
1014             getBlockCodeRegion(BD, Ctx.getCanonicalType(T),
1015                                STC->getAnalysisDeclContext());
1016           sReg = getGlobalsRegion(MemRegion::StaticGlobalSpaceRegionKind,
1017                                   BTR);
1018         }
1019         else {
1020           sReg = getGlobalsRegion();
1021         }
1022       }
1023     }
1024   }
1025 
1026   return getSubRegion<NonParamVarRegion>(D, sReg);
1027 }
1028 
1029 const NonParamVarRegion *
1030 MemRegionManager::getNonParamVarRegion(const VarDecl *D,
1031                                        const MemRegion *superR) {
1032   D = D->getCanonicalDecl();
1033   return getSubRegion<NonParamVarRegion>(D, superR);
1034 }
1035 
1036 const ParamVarRegion *
1037 MemRegionManager::getParamVarRegion(const Expr *OriginExpr, unsigned Index,
1038                                     const LocationContext *LC) {
1039   const StackFrameContext *SFC = LC->getStackFrame();
1040   assert(SFC);
1041   return getSubRegion<ParamVarRegion>(OriginExpr, Index,
1042                                       getStackArgumentsRegion(SFC));
1043 }
1044 
1045 const BlockDataRegion *
1046 MemRegionManager::getBlockDataRegion(const BlockCodeRegion *BC,
1047                                      const LocationContext *LC,
1048                                      unsigned blockCount) {
1049   const MemSpaceRegion *sReg = nullptr;
1050   const BlockDecl *BD = BC->getDecl();
1051   if (!BD->hasCaptures()) {
1052     // This handles 'static' blocks.
1053     sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind);
1054   }
1055   else {
1056     if (LC) {
1057       // FIXME: Once we implement scope handling, we want the parent region
1058       // to be the scope.
1059       const StackFrameContext *STC = LC->getStackFrame();
1060       assert(STC);
1061       sReg = getStackLocalsRegion(STC);
1062     }
1063     else {
1064       // We allow 'LC' to be NULL for cases where want BlockDataRegions
1065       // without context-sensitivity.
1066       sReg = getUnknownRegion();
1067     }
1068   }
1069 
1070   return getSubRegion<BlockDataRegion>(BC, LC, blockCount, sReg);
1071 }
1072 
1073 const CXXTempObjectRegion *
1074 MemRegionManager::getCXXStaticTempObjectRegion(const Expr *Ex) {
1075   return getSubRegion<CXXTempObjectRegion>(
1076       Ex, getGlobalsRegion(MemRegion::GlobalInternalSpaceRegionKind, nullptr));
1077 }
1078 
1079 const CompoundLiteralRegion*
1080 MemRegionManager::getCompoundLiteralRegion(const CompoundLiteralExpr *CL,
1081                                            const LocationContext *LC) {
1082   const MemSpaceRegion *sReg = nullptr;
1083 
1084   if (CL->isFileScope())
1085     sReg = getGlobalsRegion();
1086   else {
1087     const StackFrameContext *STC = LC->getStackFrame();
1088     assert(STC);
1089     sReg = getStackLocalsRegion(STC);
1090   }
1091 
1092   return getSubRegion<CompoundLiteralRegion>(CL, sReg);
1093 }
1094 
1095 const ElementRegion*
1096 MemRegionManager::getElementRegion(QualType elementType, NonLoc Idx,
1097                                    const SubRegion* superRegion,
1098                                    ASTContext &Ctx){
1099   QualType T = Ctx.getCanonicalType(elementType).getUnqualifiedType();
1100 
1101   llvm::FoldingSetNodeID ID;
1102   ElementRegion::ProfileRegion(ID, T, Idx, superRegion);
1103 
1104   void *InsertPos;
1105   MemRegion* data = Regions.FindNodeOrInsertPos(ID, InsertPos);
1106   auto *R = cast_or_null<ElementRegion>(data);
1107 
1108   if (!R) {
1109     R = A.Allocate<ElementRegion>();
1110     new (R) ElementRegion(T, Idx, superRegion);
1111     Regions.InsertNode(R, InsertPos);
1112   }
1113 
1114   return R;
1115 }
1116 
1117 const FunctionCodeRegion *
1118 MemRegionManager::getFunctionCodeRegion(const NamedDecl *FD) {
1119   // To think: should we canonicalize the declaration here?
1120   return getSubRegion<FunctionCodeRegion>(FD, getCodeRegion());
1121 }
1122 
1123 const BlockCodeRegion *
1124 MemRegionManager::getBlockCodeRegion(const BlockDecl *BD, CanQualType locTy,
1125                                      AnalysisDeclContext *AC) {
1126   return getSubRegion<BlockCodeRegion>(BD, locTy, AC, getCodeRegion());
1127 }
1128 
1129 /// getSymbolicRegion - Retrieve or create a "symbolic" memory region.
1130 const SymbolicRegion *MemRegionManager::getSymbolicRegion(SymbolRef sym) {
1131   return getSubRegion<SymbolicRegion>(sym, getUnknownRegion());
1132 }
1133 
1134 const SymbolicRegion *MemRegionManager::getSymbolicHeapRegion(SymbolRef Sym) {
1135   return getSubRegion<SymbolicRegion>(Sym, getHeapRegion());
1136 }
1137 
1138 const FieldRegion*
1139 MemRegionManager::getFieldRegion(const FieldDecl *d,
1140                                  const SubRegion* superRegion){
1141   return getSubRegion<FieldRegion>(d, superRegion);
1142 }
1143 
1144 const ObjCIvarRegion*
1145 MemRegionManager::getObjCIvarRegion(const ObjCIvarDecl *d,
1146                                     const SubRegion* superRegion) {
1147   return getSubRegion<ObjCIvarRegion>(d, superRegion);
1148 }
1149 
1150 const CXXTempObjectRegion*
1151 MemRegionManager::getCXXTempObjectRegion(Expr const *E,
1152                                          LocationContext const *LC) {
1153   const StackFrameContext *SFC = LC->getStackFrame();
1154   assert(SFC);
1155   return getSubRegion<CXXTempObjectRegion>(E, getStackLocalsRegion(SFC));
1156 }
1157 
1158 /// Checks whether \p BaseClass is a valid virtual or direct non-virtual base
1159 /// class of the type of \p Super.
1160 static bool isValidBaseClass(const CXXRecordDecl *BaseClass,
1161                              const TypedValueRegion *Super,
1162                              bool IsVirtual) {
1163   BaseClass = BaseClass->getCanonicalDecl();
1164 
1165   const CXXRecordDecl *Class = Super->getValueType()->getAsCXXRecordDecl();
1166   if (!Class)
1167     return true;
1168 
1169   if (IsVirtual)
1170     return Class->isVirtuallyDerivedFrom(BaseClass);
1171 
1172   for (const auto &I : Class->bases()) {
1173     if (I.getType()->getAsCXXRecordDecl()->getCanonicalDecl() == BaseClass)
1174       return true;
1175   }
1176 
1177   return false;
1178 }
1179 
1180 const CXXBaseObjectRegion *
1181 MemRegionManager::getCXXBaseObjectRegion(const CXXRecordDecl *RD,
1182                                          const SubRegion *Super,
1183                                          bool IsVirtual) {
1184   if (isa<TypedValueRegion>(Super)) {
1185     assert(isValidBaseClass(RD, cast<TypedValueRegion>(Super), IsVirtual));
1186     (void)&isValidBaseClass;
1187 
1188     if (IsVirtual) {
1189       // Virtual base regions should not be layered, since the layout rules
1190       // are different.
1191       while (const auto *Base = dyn_cast<CXXBaseObjectRegion>(Super))
1192         Super = cast<SubRegion>(Base->getSuperRegion());
1193       assert(Super && !isa<MemSpaceRegion>(Super));
1194     }
1195   }
1196 
1197   return getSubRegion<CXXBaseObjectRegion>(RD, IsVirtual, Super);
1198 }
1199 
1200 const CXXDerivedObjectRegion *
1201 MemRegionManager::getCXXDerivedObjectRegion(const CXXRecordDecl *RD,
1202                                             const SubRegion *Super) {
1203   return getSubRegion<CXXDerivedObjectRegion>(RD, Super);
1204 }
1205 
1206 const CXXThisRegion*
1207 MemRegionManager::getCXXThisRegion(QualType thisPointerTy,
1208                                    const LocationContext *LC) {
1209   const auto *PT = thisPointerTy->getAs<PointerType>();
1210   assert(PT);
1211   // Inside the body of the operator() of a lambda a this expr might refer to an
1212   // object in one of the parent location contexts.
1213   const auto *D = dyn_cast<CXXMethodDecl>(LC->getDecl());
1214   // FIXME: when operator() of lambda is analyzed as a top level function and
1215   // 'this' refers to a this to the enclosing scope, there is no right region to
1216   // return.
1217   while (!LC->inTopFrame() && (!D || D->isStatic() ||
1218                                PT != D->getThisType()->getAs<PointerType>())) {
1219     LC = LC->getParent();
1220     D = dyn_cast<CXXMethodDecl>(LC->getDecl());
1221   }
1222   const StackFrameContext *STC = LC->getStackFrame();
1223   assert(STC);
1224   return getSubRegion<CXXThisRegion>(PT, getStackArgumentsRegion(STC));
1225 }
1226 
1227 const AllocaRegion*
1228 MemRegionManager::getAllocaRegion(const Expr *E, unsigned cnt,
1229                                   const LocationContext *LC) {
1230   const StackFrameContext *STC = LC->getStackFrame();
1231   assert(STC);
1232   return getSubRegion<AllocaRegion>(E, cnt, getStackLocalsRegion(STC));
1233 }
1234 
1235 const MemSpaceRegion *MemRegion::getMemorySpace() const {
1236   const MemRegion *R = this;
1237   const auto *SR = dyn_cast<SubRegion>(this);
1238 
1239   while (SR) {
1240     R = SR->getSuperRegion();
1241     SR = dyn_cast<SubRegion>(R);
1242   }
1243 
1244   return dyn_cast<MemSpaceRegion>(R);
1245 }
1246 
1247 bool MemRegion::hasStackStorage() const {
1248   return isa<StackSpaceRegion>(getMemorySpace());
1249 }
1250 
1251 bool MemRegion::hasStackNonParametersStorage() const {
1252   return isa<StackLocalsSpaceRegion>(getMemorySpace());
1253 }
1254 
1255 bool MemRegion::hasStackParametersStorage() const {
1256   return isa<StackArgumentsSpaceRegion>(getMemorySpace());
1257 }
1258 
1259 bool MemRegion::hasGlobalsOrParametersStorage() const {
1260   const MemSpaceRegion *MS = getMemorySpace();
1261   return isa<StackArgumentsSpaceRegion>(MS) ||
1262          isa<GlobalsSpaceRegion>(MS);
1263 }
1264 
1265 // getBaseRegion strips away all elements and fields, and get the base region
1266 // of them.
1267 const MemRegion *MemRegion::getBaseRegion() const {
1268   const MemRegion *R = this;
1269   while (true) {
1270     switch (R->getKind()) {
1271       case MemRegion::ElementRegionKind:
1272       case MemRegion::FieldRegionKind:
1273       case MemRegion::ObjCIvarRegionKind:
1274       case MemRegion::CXXBaseObjectRegionKind:
1275       case MemRegion::CXXDerivedObjectRegionKind:
1276         R = cast<SubRegion>(R)->getSuperRegion();
1277         continue;
1278       default:
1279         break;
1280     }
1281     break;
1282   }
1283   return R;
1284 }
1285 
1286 // getgetMostDerivedObjectRegion gets the region of the root class of a C++
1287 // class hierarchy.
1288 const MemRegion *MemRegion::getMostDerivedObjectRegion() const {
1289   const MemRegion *R = this;
1290   while (const auto *BR = dyn_cast<CXXBaseObjectRegion>(R))
1291     R = BR->getSuperRegion();
1292   return R;
1293 }
1294 
1295 bool MemRegion::isSubRegionOf(const MemRegion *) const {
1296   return false;
1297 }
1298 
1299 //===----------------------------------------------------------------------===//
1300 // View handling.
1301 //===----------------------------------------------------------------------===//
1302 
1303 const MemRegion *MemRegion::StripCasts(bool StripBaseAndDerivedCasts) const {
1304   const MemRegion *R = this;
1305   while (true) {
1306     switch (R->getKind()) {
1307     case ElementRegionKind: {
1308       const auto *ER = cast<ElementRegion>(R);
1309       if (!ER->getIndex().isZeroConstant())
1310         return R;
1311       R = ER->getSuperRegion();
1312       break;
1313     }
1314     case CXXBaseObjectRegionKind:
1315     case CXXDerivedObjectRegionKind:
1316       if (!StripBaseAndDerivedCasts)
1317         return R;
1318       R = cast<TypedValueRegion>(R)->getSuperRegion();
1319       break;
1320     default:
1321       return R;
1322     }
1323   }
1324 }
1325 
1326 const SymbolicRegion *MemRegion::getSymbolicBase() const {
1327   const auto *SubR = dyn_cast<SubRegion>(this);
1328 
1329   while (SubR) {
1330     if (const auto *SymR = dyn_cast<SymbolicRegion>(SubR))
1331       return SymR;
1332     SubR = dyn_cast<SubRegion>(SubR->getSuperRegion());
1333   }
1334   return nullptr;
1335 }
1336 
1337 RegionRawOffset ElementRegion::getAsArrayOffset() const {
1338   int64_t offset = 0;
1339   const ElementRegion *ER = this;
1340   const MemRegion *superR = nullptr;
1341   ASTContext &C = getContext();
1342 
1343   // FIXME: Handle multi-dimensional arrays.
1344 
1345   while (ER) {
1346     superR = ER->getSuperRegion();
1347 
1348     // FIXME: generalize to symbolic offsets.
1349     SVal index = ER->getIndex();
1350     if (auto CI = index.getAs<nonloc::ConcreteInt>()) {
1351       // Update the offset.
1352       int64_t i = CI->getValue().getSExtValue();
1353 
1354       if (i != 0) {
1355         QualType elemType = ER->getElementType();
1356 
1357         // If we are pointing to an incomplete type, go no further.
1358         if (elemType->isIncompleteType()) {
1359           superR = ER;
1360           break;
1361         }
1362 
1363         int64_t size = C.getTypeSizeInChars(elemType).getQuantity();
1364         if (auto NewOffset = llvm::checkedMulAdd(i, size, offset)) {
1365           offset = *NewOffset;
1366         } else {
1367           LLVM_DEBUG(llvm::dbgs() << "MemRegion::getAsArrayOffset: "
1368                                   << "offset overflowing, returning unknown\n");
1369 
1370           return nullptr;
1371         }
1372       }
1373 
1374       // Go to the next ElementRegion (if any).
1375       ER = dyn_cast<ElementRegion>(superR);
1376       continue;
1377     }
1378 
1379     return nullptr;
1380   }
1381 
1382   assert(superR && "super region cannot be NULL");
1383   return RegionRawOffset(superR, CharUnits::fromQuantity(offset));
1384 }
1385 
1386 /// Returns true if \p Base is an immediate base class of \p Child
1387 static bool isImmediateBase(const CXXRecordDecl *Child,
1388                             const CXXRecordDecl *Base) {
1389   assert(Child && "Child must not be null");
1390   // Note that we do NOT canonicalize the base class here, because
1391   // ASTRecordLayout doesn't either. If that leads us down the wrong path,
1392   // so be it; at least we won't crash.
1393   for (const auto &I : Child->bases()) {
1394     if (I.getType()->getAsCXXRecordDecl() == Base)
1395       return true;
1396   }
1397 
1398   return false;
1399 }
1400 
1401 static RegionOffset calculateOffset(const MemRegion *R) {
1402   const MemRegion *SymbolicOffsetBase = nullptr;
1403   int64_t Offset = 0;
1404 
1405   while (true) {
1406     switch (R->getKind()) {
1407     case MemRegion::CodeSpaceRegionKind:
1408     case MemRegion::StackLocalsSpaceRegionKind:
1409     case MemRegion::StackArgumentsSpaceRegionKind:
1410     case MemRegion::HeapSpaceRegionKind:
1411     case MemRegion::UnknownSpaceRegionKind:
1412     case MemRegion::StaticGlobalSpaceRegionKind:
1413     case MemRegion::GlobalInternalSpaceRegionKind:
1414     case MemRegion::GlobalSystemSpaceRegionKind:
1415     case MemRegion::GlobalImmutableSpaceRegionKind:
1416       // Stores can bind directly to a region space to set a default value.
1417       assert(Offset == 0 && !SymbolicOffsetBase);
1418       goto Finish;
1419 
1420     case MemRegion::FunctionCodeRegionKind:
1421     case MemRegion::BlockCodeRegionKind:
1422     case MemRegion::BlockDataRegionKind:
1423       // These will never have bindings, but may end up having values requested
1424       // if the user does some strange casting.
1425       if (Offset != 0)
1426         SymbolicOffsetBase = R;
1427       goto Finish;
1428 
1429     case MemRegion::SymbolicRegionKind:
1430     case MemRegion::AllocaRegionKind:
1431     case MemRegion::CompoundLiteralRegionKind:
1432     case MemRegion::CXXThisRegionKind:
1433     case MemRegion::StringRegionKind:
1434     case MemRegion::ObjCStringRegionKind:
1435     case MemRegion::NonParamVarRegionKind:
1436     case MemRegion::ParamVarRegionKind:
1437     case MemRegion::CXXTempObjectRegionKind:
1438       // Usual base regions.
1439       goto Finish;
1440 
1441     case MemRegion::ObjCIvarRegionKind:
1442       // This is a little strange, but it's a compromise between
1443       // ObjCIvarRegions having unknown compile-time offsets (when using the
1444       // non-fragile runtime) and yet still being distinct, non-overlapping
1445       // regions. Thus we treat them as "like" base regions for the purposes
1446       // of computing offsets.
1447       goto Finish;
1448 
1449     case MemRegion::CXXBaseObjectRegionKind: {
1450       const auto *BOR = cast<CXXBaseObjectRegion>(R);
1451       R = BOR->getSuperRegion();
1452 
1453       QualType Ty;
1454       bool RootIsSymbolic = false;
1455       if (const auto *TVR = dyn_cast<TypedValueRegion>(R)) {
1456         Ty = TVR->getDesugaredValueType(R->getContext());
1457       } else if (const auto *SR = dyn_cast<SymbolicRegion>(R)) {
1458         // If our base region is symbolic, we don't know what type it really is.
1459         // Pretend the type of the symbol is the true dynamic type.
1460         // (This will at least be self-consistent for the life of the symbol.)
1461         Ty = SR->getSymbol()->getType()->getPointeeType();
1462         RootIsSymbolic = true;
1463       }
1464 
1465       const CXXRecordDecl *Child = Ty->getAsCXXRecordDecl();
1466       if (!Child) {
1467         // We cannot compute the offset of the base class.
1468         SymbolicOffsetBase = R;
1469       } else {
1470         if (RootIsSymbolic) {
1471           // Base layers on symbolic regions may not be type-correct.
1472           // Double-check the inheritance here, and revert to a symbolic offset
1473           // if it's invalid (e.g. due to a reinterpret_cast).
1474           if (BOR->isVirtual()) {
1475             if (!Child->isVirtuallyDerivedFrom(BOR->getDecl()))
1476               SymbolicOffsetBase = R;
1477           } else {
1478             if (!isImmediateBase(Child, BOR->getDecl()))
1479               SymbolicOffsetBase = R;
1480           }
1481         }
1482       }
1483 
1484       // Don't bother calculating precise offsets if we already have a
1485       // symbolic offset somewhere in the chain.
1486       if (SymbolicOffsetBase)
1487         continue;
1488 
1489       CharUnits BaseOffset;
1490       const ASTRecordLayout &Layout = R->getContext().getASTRecordLayout(Child);
1491       if (BOR->isVirtual())
1492         BaseOffset = Layout.getVBaseClassOffset(BOR->getDecl());
1493       else
1494         BaseOffset = Layout.getBaseClassOffset(BOR->getDecl());
1495 
1496       // The base offset is in chars, not in bits.
1497       Offset += BaseOffset.getQuantity() * R->getContext().getCharWidth();
1498       break;
1499     }
1500 
1501     case MemRegion::CXXDerivedObjectRegionKind: {
1502       // TODO: Store the base type in the CXXDerivedObjectRegion and use it.
1503       goto Finish;
1504     }
1505 
1506     case MemRegion::ElementRegionKind: {
1507       const auto *ER = cast<ElementRegion>(R);
1508       R = ER->getSuperRegion();
1509 
1510       QualType EleTy = ER->getValueType();
1511       if (EleTy->isIncompleteType()) {
1512         // We cannot compute the offset of the base class.
1513         SymbolicOffsetBase = R;
1514         continue;
1515       }
1516 
1517       SVal Index = ER->getIndex();
1518       if (Optional<nonloc::ConcreteInt> CI =
1519               Index.getAs<nonloc::ConcreteInt>()) {
1520         // Don't bother calculating precise offsets if we already have a
1521         // symbolic offset somewhere in the chain.
1522         if (SymbolicOffsetBase)
1523           continue;
1524 
1525         int64_t i = CI->getValue().getSExtValue();
1526         // This type size is in bits.
1527         Offset += i * R->getContext().getTypeSize(EleTy);
1528       } else {
1529         // We cannot compute offset for non-concrete index.
1530         SymbolicOffsetBase = R;
1531       }
1532       break;
1533     }
1534     case MemRegion::FieldRegionKind: {
1535       const auto *FR = cast<FieldRegion>(R);
1536       R = FR->getSuperRegion();
1537       assert(R);
1538 
1539       const RecordDecl *RD = FR->getDecl()->getParent();
1540       if (RD->isUnion() || !RD->isCompleteDefinition()) {
1541         // We cannot compute offset for incomplete type.
1542         // For unions, we could treat everything as offset 0, but we'd rather
1543         // treat each field as a symbolic offset so they aren't stored on top
1544         // of each other, since we depend on things in typed regions actually
1545         // matching their types.
1546         SymbolicOffsetBase = R;
1547       }
1548 
1549       // Don't bother calculating precise offsets if we already have a
1550       // symbolic offset somewhere in the chain.
1551       if (SymbolicOffsetBase)
1552         continue;
1553 
1554       // Get the field number.
1555       unsigned idx = 0;
1556       for (RecordDecl::field_iterator FI = RD->field_begin(),
1557              FE = RD->field_end(); FI != FE; ++FI, ++idx) {
1558         if (FR->getDecl() == *FI)
1559           break;
1560       }
1561       const ASTRecordLayout &Layout = R->getContext().getASTRecordLayout(RD);
1562       // This is offset in bits.
1563       Offset += Layout.getFieldOffset(idx);
1564       break;
1565     }
1566     }
1567   }
1568 
1569  Finish:
1570   if (SymbolicOffsetBase)
1571     return RegionOffset(SymbolicOffsetBase, RegionOffset::Symbolic);
1572   return RegionOffset(R, Offset);
1573 }
1574 
1575 RegionOffset MemRegion::getAsOffset() const {
1576   if (!cachedOffset)
1577     cachedOffset = calculateOffset(this);
1578   return *cachedOffset;
1579 }
1580 
1581 //===----------------------------------------------------------------------===//
1582 // BlockDataRegion
1583 //===----------------------------------------------------------------------===//
1584 
1585 std::pair<const VarRegion *, const VarRegion *>
1586 BlockDataRegion::getCaptureRegions(const VarDecl *VD) {
1587   MemRegionManager &MemMgr = getMemRegionManager();
1588   const VarRegion *VR = nullptr;
1589   const VarRegion *OriginalVR = nullptr;
1590 
1591   if (!VD->hasAttr<BlocksAttr>() && VD->hasLocalStorage()) {
1592     VR = MemMgr.getNonParamVarRegion(VD, this);
1593     OriginalVR = MemMgr.getVarRegion(VD, LC);
1594   }
1595   else {
1596     if (LC) {
1597       VR = MemMgr.getVarRegion(VD, LC);
1598       OriginalVR = VR;
1599     }
1600     else {
1601       VR = MemMgr.getNonParamVarRegion(VD, MemMgr.getUnknownRegion());
1602       OriginalVR = MemMgr.getVarRegion(VD, LC);
1603     }
1604   }
1605   return std::make_pair(VR, OriginalVR);
1606 }
1607 
1608 void BlockDataRegion::LazyInitializeReferencedVars() {
1609   if (ReferencedVars)
1610     return;
1611 
1612   AnalysisDeclContext *AC = getCodeRegion()->getAnalysisDeclContext();
1613   const auto &ReferencedBlockVars = AC->getReferencedBlockVars(BC->getDecl());
1614   auto NumBlockVars =
1615       std::distance(ReferencedBlockVars.begin(), ReferencedBlockVars.end());
1616 
1617   if (NumBlockVars == 0) {
1618     ReferencedVars = (void*) 0x1;
1619     return;
1620   }
1621 
1622   MemRegionManager &MemMgr = getMemRegionManager();
1623   llvm::BumpPtrAllocator &A = MemMgr.getAllocator();
1624   BumpVectorContext BC(A);
1625 
1626   using VarVec = BumpVector<const MemRegion *>;
1627 
1628   auto *BV = A.Allocate<VarVec>();
1629   new (BV) VarVec(BC, NumBlockVars);
1630   auto *BVOriginal = A.Allocate<VarVec>();
1631   new (BVOriginal) VarVec(BC, NumBlockVars);
1632 
1633   for (const auto *VD : ReferencedBlockVars) {
1634     const VarRegion *VR = nullptr;
1635     const VarRegion *OriginalVR = nullptr;
1636     std::tie(VR, OriginalVR) = getCaptureRegions(VD);
1637     assert(VR);
1638     assert(OriginalVR);
1639     BV->push_back(VR, BC);
1640     BVOriginal->push_back(OriginalVR, BC);
1641   }
1642 
1643   ReferencedVars = BV;
1644   OriginalVars = BVOriginal;
1645 }
1646 
1647 BlockDataRegion::referenced_vars_iterator
1648 BlockDataRegion::referenced_vars_begin() const {
1649   const_cast<BlockDataRegion*>(this)->LazyInitializeReferencedVars();
1650 
1651   auto *Vec = static_cast<BumpVector<const MemRegion *> *>(ReferencedVars);
1652 
1653   if (Vec == (void*) 0x1)
1654     return BlockDataRegion::referenced_vars_iterator(nullptr, nullptr);
1655 
1656   auto *VecOriginal =
1657       static_cast<BumpVector<const MemRegion *> *>(OriginalVars);
1658 
1659   return BlockDataRegion::referenced_vars_iterator(Vec->begin(),
1660                                                    VecOriginal->begin());
1661 }
1662 
1663 BlockDataRegion::referenced_vars_iterator
1664 BlockDataRegion::referenced_vars_end() const {
1665   const_cast<BlockDataRegion*>(this)->LazyInitializeReferencedVars();
1666 
1667   auto *Vec = static_cast<BumpVector<const MemRegion *> *>(ReferencedVars);
1668 
1669   if (Vec == (void*) 0x1)
1670     return BlockDataRegion::referenced_vars_iterator(nullptr, nullptr);
1671 
1672   auto *VecOriginal =
1673       static_cast<BumpVector<const MemRegion *> *>(OriginalVars);
1674 
1675   return BlockDataRegion::referenced_vars_iterator(Vec->end(),
1676                                                    VecOriginal->end());
1677 }
1678 
1679 const VarRegion *BlockDataRegion::getOriginalRegion(const VarRegion *R) const {
1680   for (referenced_vars_iterator I = referenced_vars_begin(),
1681                                 E = referenced_vars_end();
1682        I != E; ++I) {
1683     if (I.getCapturedRegion() == R)
1684       return I.getOriginalRegion();
1685   }
1686   return nullptr;
1687 }
1688 
1689 //===----------------------------------------------------------------------===//
1690 // RegionAndSymbolInvalidationTraits
1691 //===----------------------------------------------------------------------===//
1692 
1693 void RegionAndSymbolInvalidationTraits::setTrait(SymbolRef Sym,
1694                                                  InvalidationKinds IK) {
1695   SymTraitsMap[Sym] |= IK;
1696 }
1697 
1698 void RegionAndSymbolInvalidationTraits::setTrait(const MemRegion *MR,
1699                                                  InvalidationKinds IK) {
1700   assert(MR);
1701   if (const auto *SR = dyn_cast<SymbolicRegion>(MR))
1702     setTrait(SR->getSymbol(), IK);
1703   else
1704     MRTraitsMap[MR] |= IK;
1705 }
1706 
1707 bool RegionAndSymbolInvalidationTraits::hasTrait(SymbolRef Sym,
1708                                                  InvalidationKinds IK) const {
1709   const_symbol_iterator I = SymTraitsMap.find(Sym);
1710   if (I != SymTraitsMap.end())
1711     return I->second & IK;
1712 
1713   return false;
1714 }
1715 
1716 bool RegionAndSymbolInvalidationTraits::hasTrait(const MemRegion *MR,
1717                                                  InvalidationKinds IK) const {
1718   if (!MR)
1719     return false;
1720 
1721   if (const auto *SR = dyn_cast<SymbolicRegion>(MR))
1722     return hasTrait(SR->getSymbol(), IK);
1723 
1724   const_region_iterator I = MRTraitsMap.find(MR);
1725   if (I != MRTraitsMap.end())
1726     return I->second & IK;
1727 
1728   return false;
1729 }
1730