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

source code of clang/lib/StaticAnalyzer/Core/MemRegion.cpp