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