1 //==- MemRegion.h - Abstract memory regions for static analysis -*- C++ -*--==//
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 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_MEMREGION_H
16 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_MEMREGION_H
17 
18 #include "clang/AST/ASTContext.h"
19 #include "clang/AST/CharUnits.h"
20 #include "clang/AST/Decl.h"
21 #include "clang/AST/DeclObjC.h"
22 #include "clang/AST/DeclarationName.h"
23 #include "clang/AST/Expr.h"
24 #include "clang/AST/ExprObjC.h"
25 #include "clang/AST/Type.h"
26 #include "clang/Analysis/AnalysisDeclContext.h"
27 #include "clang/Basic/LLVM.h"
28 #include "clang/Basic/SourceLocation.h"
29 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
30 #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
31 #include "llvm/ADT/DenseMap.h"
32 #include "llvm/ADT/FoldingSet.h"
33 #include "llvm/ADT/Optional.h"
34 #include "llvm/ADT/PointerIntPair.h"
35 #include "llvm/Support/Allocator.h"
36 #include "llvm/Support/Casting.h"
37 #include <cassert>
38 #include <cstdint>
39 #include <limits>
40 #include <string>
41 #include <utility>
42 
43 namespace clang {
44 
45 class AnalysisDeclContext;
46 class CXXRecordDecl;
47 class Decl;
48 class LocationContext;
49 class StackFrameContext;
50 
51 namespace ento {
52 
53 class CodeTextRegion;
54 class MemRegion;
55 class MemRegionManager;
56 class MemSpaceRegion;
57 class SValBuilder;
58 class SymbolicRegion;
59 class VarRegion;
60 
61 /// Represent a region's offset within the top level base region.
62 class RegionOffset {
63   /// The base region.
64   const MemRegion *R = nullptr;
65 
66   /// The bit offset within the base region. Can be negative.
67   int64_t Offset;
68 
69 public:
70   // We're using a const instead of an enumeration due to the size required;
71   // Visual Studio will only create enumerations of size int, not long long.
72   static const int64_t Symbolic = std::numeric_limits<int64_t>::max();
73 
74   RegionOffset() = default;
RegionOffset(const MemRegion * r,int64_t off)75   RegionOffset(const MemRegion *r, int64_t off) : R(r), Offset(off) {}
76 
getRegion()77   const MemRegion *getRegion() const { return R; }
78 
hasSymbolicOffset()79   bool hasSymbolicOffset() const { return Offset == Symbolic; }
80 
getOffset()81   int64_t getOffset() const {
82     assert(!hasSymbolicOffset());
83     return Offset;
84   }
85 
isValid()86   bool isValid() const { return R; }
87 };
88 
89 //===----------------------------------------------------------------------===//
90 // Base region classes.
91 //===----------------------------------------------------------------------===//
92 
93 /// MemRegion - The root abstract class for all memory regions.
94 class MemRegion : public llvm::FoldingSetNode {
95 public:
96   enum Kind {
97 #define REGION(Id, Parent) Id ## Kind,
98 #define REGION_RANGE(Id, First, Last) BEGIN_##Id = First, END_##Id = Last,
99 #include "clang/StaticAnalyzer/Core/PathSensitive/Regions.def"
100   };
101 
102 private:
103   const Kind kind;
104   mutable Optional<RegionOffset> cachedOffset;
105 
106 protected:
MemRegion(Kind k)107   MemRegion(Kind k) : kind(k) {}
108   virtual ~MemRegion();
109 
110 public:
111   ASTContext &getContext() const;
112 
113   virtual void Profile(llvm::FoldingSetNodeID& ID) const = 0;
114 
115   virtual MemRegionManager &getMemRegionManager() const = 0;
116 
117   const MemSpaceRegion *getMemorySpace() const;
118 
119   const MemRegion *getBaseRegion() const;
120 
121   /// Recursively retrieve the region of the most derived class instance of
122   /// regions of C++ base class instances.
123   const MemRegion *getMostDerivedObjectRegion() const;
124 
125   /// Check if the region is a subregion of the given region.
126   /// Each region is a subregion of itself.
127   virtual bool isSubRegionOf(const MemRegion *R) const;
128 
129   const MemRegion *StripCasts(bool StripBaseAndDerivedCasts = true) const;
130 
131   /// If this is a symbolic region, returns the region. Otherwise,
132   /// goes up the base chain looking for the first symbolic base region.
133   const SymbolicRegion *getSymbolicBase() const;
134 
135   bool hasGlobalsOrParametersStorage() const;
136 
137   bool hasStackStorage() const;
138 
139   bool hasStackNonParametersStorage() const;
140 
141   bool hasStackParametersStorage() const;
142 
143   /// Compute the offset within the top level memory object.
144   RegionOffset getAsOffset() const;
145 
146   /// Get a string representation of a region for debug use.
147   std::string getString() const;
148 
149   virtual void dumpToStream(raw_ostream &os) const;
150 
151   void dump() const;
152 
153   /// Returns true if this region can be printed in a user-friendly way.
154   virtual bool canPrintPretty() const;
155 
156   /// Print the region for use in diagnostics.
157   virtual void printPretty(raw_ostream &os) const;
158 
159   /// Returns true if this region's textual representation can be used
160   /// as part of a larger expression.
161   virtual bool canPrintPrettyAsExpr() const;
162 
163   /// Print the region as expression.
164   ///
165   /// When this region represents a subexpression, the method is for printing
166   /// an expression containing it.
167   virtual void printPrettyAsExpr(raw_ostream &os) const;
168 
getKind()169   Kind getKind() const { return kind; }
170 
171   template<typename RegionTy> const RegionTy* getAs() const;
172   template<typename RegionTy> const RegionTy* castAs() const;
173 
isBoundable()174   virtual bool isBoundable() const { return false; }
175 
176   /// Get descriptive name for memory region. The name is obtained from
177   /// the variable/field declaration retrieved from the memory region.
178   /// Regions that point to an element of an array are returned as: "arr[0]".
179   /// Regions that point to a struct are returned as: "st.var".
180   //
181   /// \param UseQuotes Set if the name should be quoted.
182   ///
183   /// \returns variable name for memory region
184   std::string getDescriptiveName(bool UseQuotes = true) const;
185 
186   /// Retrieve source range from memory region. The range retrieval
187   /// is based on the decl obtained from the memory region.
188   /// For a VarRegion the range of the base region is returned.
189   /// For a FieldRegion the range of the field is returned.
190   /// If no declaration is found, an empty source range is returned.
191   /// The client is responsible for checking if the returned range is valid.
192   ///
193   /// \returns source range for declaration retrieved from memory region
194   SourceRange sourceRange() const;
195 };
196 
197 /// MemSpaceRegion - A memory region that represents a "memory space";
198 ///  for example, the set of global variables, the stack frame, etc.
199 class MemSpaceRegion : public MemRegion {
200 protected:
201   MemRegionManager &Mgr;
202 
MemSpaceRegion(MemRegionManager & mgr,Kind k)203   MemSpaceRegion(MemRegionManager &mgr, Kind k) : MemRegion(k), Mgr(mgr) {
204     assert(classof(this));
205   }
206 
getMemRegionManager()207   MemRegionManager &getMemRegionManager() const override { return Mgr; }
208 
209 public:
isBoundable()210   bool isBoundable() const override { return false; }
211 
212   void Profile(llvm::FoldingSetNodeID &ID) const override;
213 
classof(const MemRegion * R)214   static bool classof(const MemRegion *R) {
215     Kind k = R->getKind();
216     return k >= BEGIN_MEMSPACES && k <= END_MEMSPACES;
217   }
218 };
219 
220 /// CodeSpaceRegion - The memory space that holds the executable code of
221 /// functions and blocks.
222 class CodeSpaceRegion : public MemSpaceRegion {
223   friend class MemRegionManager;
224 
CodeSpaceRegion(MemRegionManager & mgr)225   CodeSpaceRegion(MemRegionManager &mgr)
226       : MemSpaceRegion(mgr, CodeSpaceRegionKind) {}
227 
228 public:
229   void dumpToStream(raw_ostream &os) const override;
230 
classof(const MemRegion * R)231   static bool classof(const MemRegion *R) {
232     return R->getKind() == CodeSpaceRegionKind;
233   }
234 };
235 
236 class GlobalsSpaceRegion : public MemSpaceRegion {
237   virtual void anchor();
238 
239 protected:
GlobalsSpaceRegion(MemRegionManager & mgr,Kind k)240   GlobalsSpaceRegion(MemRegionManager &mgr, Kind k) : MemSpaceRegion(mgr, k) {
241     assert(classof(this));
242   }
243 
244 public:
classof(const MemRegion * R)245   static bool classof(const MemRegion *R) {
246     Kind k = R->getKind();
247     return k >= BEGIN_GLOBAL_MEMSPACES && k <= END_GLOBAL_MEMSPACES;
248   }
249 };
250 
251 /// The region of the static variables within the current CodeTextRegion
252 /// scope.
253 ///
254 /// Currently, only the static locals are placed there, so we know that these
255 /// variables do not get invalidated by calls to other functions.
256 class StaticGlobalSpaceRegion : public GlobalsSpaceRegion {
257   friend class MemRegionManager;
258 
259   const CodeTextRegion *CR;
260 
StaticGlobalSpaceRegion(MemRegionManager & mgr,const CodeTextRegion * cr)261   StaticGlobalSpaceRegion(MemRegionManager &mgr, const CodeTextRegion *cr)
262       : GlobalsSpaceRegion(mgr, StaticGlobalSpaceRegionKind), CR(cr) {
263     assert(cr);
264   }
265 
266 public:
267   void Profile(llvm::FoldingSetNodeID &ID) const override;
268 
269   void dumpToStream(raw_ostream &os) const override;
270 
getCodeRegion()271   const CodeTextRegion *getCodeRegion() const { return CR; }
272 
classof(const MemRegion * R)273   static bool classof(const MemRegion *R) {
274     return R->getKind() == StaticGlobalSpaceRegionKind;
275   }
276 };
277 
278 /// The region for all the non-static global variables.
279 ///
280 /// This class is further split into subclasses for efficient implementation of
281 /// invalidating a set of related global values as is done in
282 /// RegionStoreManager::invalidateRegions (instead of finding all the dependent
283 /// globals, we invalidate the whole parent region).
284 class NonStaticGlobalSpaceRegion : public GlobalsSpaceRegion {
285   void anchor() override;
286 
287 protected:
NonStaticGlobalSpaceRegion(MemRegionManager & mgr,Kind k)288   NonStaticGlobalSpaceRegion(MemRegionManager &mgr, Kind k)
289       : GlobalsSpaceRegion(mgr, k) {
290     assert(classof(this));
291   }
292 
293 public:
classof(const MemRegion * R)294   static bool classof(const MemRegion *R) {
295     Kind k = R->getKind();
296     return k >= BEGIN_NON_STATIC_GLOBAL_MEMSPACES &&
297            k <= END_NON_STATIC_GLOBAL_MEMSPACES;
298   }
299 };
300 
301 /// The region containing globals which are defined in system/external
302 /// headers and are considered modifiable by system calls (ex: errno).
303 class GlobalSystemSpaceRegion : public NonStaticGlobalSpaceRegion {
304   friend class MemRegionManager;
305 
GlobalSystemSpaceRegion(MemRegionManager & mgr)306   GlobalSystemSpaceRegion(MemRegionManager &mgr)
307       : NonStaticGlobalSpaceRegion(mgr, GlobalSystemSpaceRegionKind) {}
308 
309 public:
310   void dumpToStream(raw_ostream &os) const override;
311 
classof(const MemRegion * R)312   static bool classof(const MemRegion *R) {
313     return R->getKind() == GlobalSystemSpaceRegionKind;
314   }
315 };
316 
317 /// The region containing globals which are considered not to be modified
318 /// or point to data which could be modified as a result of a function call
319 /// (system or internal). Ex: Const global scalars would be modeled as part of
320 /// this region. This region also includes most system globals since they have
321 /// low chance of being modified.
322 class GlobalImmutableSpaceRegion : public NonStaticGlobalSpaceRegion {
323   friend class MemRegionManager;
324 
GlobalImmutableSpaceRegion(MemRegionManager & mgr)325   GlobalImmutableSpaceRegion(MemRegionManager &mgr)
326       : NonStaticGlobalSpaceRegion(mgr, GlobalImmutableSpaceRegionKind) {}
327 
328 public:
329   void dumpToStream(raw_ostream &os) const override;
330 
classof(const MemRegion * R)331   static bool classof(const MemRegion *R) {
332     return R->getKind() == GlobalImmutableSpaceRegionKind;
333   }
334 };
335 
336 /// The region containing globals which can be modified by calls to
337 /// "internally" defined functions - (for now just) functions other then system
338 /// calls.
339 class GlobalInternalSpaceRegion : public NonStaticGlobalSpaceRegion {
340   friend class MemRegionManager;
341 
GlobalInternalSpaceRegion(MemRegionManager & mgr)342   GlobalInternalSpaceRegion(MemRegionManager &mgr)
343       : NonStaticGlobalSpaceRegion(mgr, GlobalInternalSpaceRegionKind) {}
344 
345 public:
346   void dumpToStream(raw_ostream &os) const override;
347 
classof(const MemRegion * R)348   static bool classof(const MemRegion *R) {
349     return R->getKind() == GlobalInternalSpaceRegionKind;
350   }
351 };
352 
353 class HeapSpaceRegion : public MemSpaceRegion {
354   friend class MemRegionManager;
355 
HeapSpaceRegion(MemRegionManager & mgr)356   HeapSpaceRegion(MemRegionManager &mgr)
357       : MemSpaceRegion(mgr, HeapSpaceRegionKind) {}
358 
359 public:
360   void dumpToStream(raw_ostream &os) const override;
361 
classof(const MemRegion * R)362   static bool classof(const MemRegion *R) {
363     return R->getKind() == HeapSpaceRegionKind;
364   }
365 };
366 
367 class UnknownSpaceRegion : public MemSpaceRegion {
368   friend class MemRegionManager;
369 
UnknownSpaceRegion(MemRegionManager & mgr)370   UnknownSpaceRegion(MemRegionManager &mgr)
371       : MemSpaceRegion(mgr, UnknownSpaceRegionKind) {}
372 
373 public:
374   void dumpToStream(raw_ostream &os) const override;
375 
classof(const MemRegion * R)376   static bool classof(const MemRegion *R) {
377     return R->getKind() == UnknownSpaceRegionKind;
378   }
379 };
380 
381 class StackSpaceRegion : public MemSpaceRegion {
382   virtual void anchor();
383 
384   const StackFrameContext *SFC;
385 
386 protected:
StackSpaceRegion(MemRegionManager & mgr,Kind k,const StackFrameContext * sfc)387   StackSpaceRegion(MemRegionManager &mgr, Kind k, const StackFrameContext *sfc)
388       : MemSpaceRegion(mgr, k), SFC(sfc) {
389     assert(classof(this));
390     assert(sfc);
391   }
392 
393 public:
getStackFrame()394   const StackFrameContext *getStackFrame() const { return SFC; }
395 
396   void Profile(llvm::FoldingSetNodeID &ID) const override;
397 
classof(const MemRegion * R)398   static bool classof(const MemRegion *R) {
399     Kind k = R->getKind();
400     return k >= BEGIN_STACK_MEMSPACES && k <= END_STACK_MEMSPACES;
401   }
402 };
403 
404 class StackLocalsSpaceRegion : public StackSpaceRegion {
405   friend class MemRegionManager;
406 
StackLocalsSpaceRegion(MemRegionManager & mgr,const StackFrameContext * sfc)407   StackLocalsSpaceRegion(MemRegionManager &mgr, const StackFrameContext *sfc)
408       : StackSpaceRegion(mgr, StackLocalsSpaceRegionKind, sfc) {}
409 
410 public:
411   void dumpToStream(raw_ostream &os) const override;
412 
classof(const MemRegion * R)413   static bool classof(const MemRegion *R) {
414     return R->getKind() == StackLocalsSpaceRegionKind;
415   }
416 };
417 
418 class StackArgumentsSpaceRegion : public StackSpaceRegion {
419 private:
420   friend class MemRegionManager;
421 
StackArgumentsSpaceRegion(MemRegionManager & mgr,const StackFrameContext * sfc)422   StackArgumentsSpaceRegion(MemRegionManager &mgr, const StackFrameContext *sfc)
423       : StackSpaceRegion(mgr, StackArgumentsSpaceRegionKind, sfc) {}
424 
425 public:
426   void dumpToStream(raw_ostream &os) const override;
427 
classof(const MemRegion * R)428   static bool classof(const MemRegion *R) {
429     return R->getKind() == StackArgumentsSpaceRegionKind;
430   }
431 };
432 
433 /// SubRegion - A region that subsets another larger region.  Most regions
434 ///  are subclasses of SubRegion.
435 class SubRegion : public MemRegion {
436   virtual void anchor();
437 
438 protected:
439   const MemRegion* superRegion;
440 
SubRegion(const MemRegion * sReg,Kind k)441   SubRegion(const MemRegion *sReg, Kind k) : MemRegion(k), superRegion(sReg) {
442     assert(classof(this));
443     assert(sReg);
444   }
445 
446 public:
getSuperRegion()447   const MemRegion* getSuperRegion() const {
448     return superRegion;
449   }
450 
451   MemRegionManager &getMemRegionManager() const override;
452 
453   bool isSubRegionOf(const MemRegion* R) const override;
454 
classof(const MemRegion * R)455   static bool classof(const MemRegion* R) {
456     return R->getKind() > END_MEMSPACES;
457   }
458 };
459 
460 //===----------------------------------------------------------------------===//
461 // MemRegion subclasses.
462 //===----------------------------------------------------------------------===//
463 
464 /// AllocaRegion - A region that represents an untyped blob of bytes created
465 ///  by a call to 'alloca'.
466 class AllocaRegion : public SubRegion {
467   friend class MemRegionManager;
468 
469   // Block counter. Used to distinguish different pieces of memory allocated by
470   // alloca at the same call site.
471   unsigned Cnt;
472 
473   const Expr *Ex;
474 
AllocaRegion(const Expr * ex,unsigned cnt,const MemSpaceRegion * superRegion)475   AllocaRegion(const Expr *ex, unsigned cnt, const MemSpaceRegion *superRegion)
476       : SubRegion(superRegion, AllocaRegionKind), Cnt(cnt), Ex(ex) {
477     assert(Ex);
478   }
479 
480   static void ProfileRegion(llvm::FoldingSetNodeID& ID, const Expr *Ex,
481                             unsigned Cnt, const MemRegion *superRegion);
482 
483 public:
getExpr()484   const Expr *getExpr() const { return Ex; }
485 
isBoundable()486   bool isBoundable() const override { return true; }
487 
488   void Profile(llvm::FoldingSetNodeID& ID) const override;
489 
490   void dumpToStream(raw_ostream &os) const override;
491 
classof(const MemRegion * R)492   static bool classof(const MemRegion* R) {
493     return R->getKind() == AllocaRegionKind;
494   }
495 };
496 
497 /// TypedRegion - An abstract class representing regions that are typed.
498 class TypedRegion : public SubRegion {
499   void anchor() override;
500 
501 protected:
TypedRegion(const MemRegion * sReg,Kind k)502   TypedRegion(const MemRegion *sReg, Kind k) : SubRegion(sReg, k) {
503     assert(classof(this));
504   }
505 
506 public:
507   virtual QualType getLocationType() const = 0;
508 
getDesugaredLocationType(ASTContext & Context)509   QualType getDesugaredLocationType(ASTContext &Context) const {
510     return getLocationType().getDesugaredType(Context);
511   }
512 
isBoundable()513   bool isBoundable() const override { return true; }
514 
classof(const MemRegion * R)515   static bool classof(const MemRegion* R) {
516     unsigned k = R->getKind();
517     return k >= BEGIN_TYPED_REGIONS && k <= END_TYPED_REGIONS;
518   }
519 };
520 
521 /// TypedValueRegion - An abstract class representing regions having a typed value.
522 class TypedValueRegion : public TypedRegion {
523   void anchor() override;
524 
525 protected:
TypedValueRegion(const MemRegion * sReg,Kind k)526   TypedValueRegion(const MemRegion* sReg, Kind k) : TypedRegion(sReg, k) {
527     assert(classof(this));
528   }
529 
530 public:
531   virtual QualType getValueType() const = 0;
532 
getLocationType()533   QualType getLocationType() const override {
534     // FIXME: We can possibly optimize this later to cache this value.
535     QualType T = getValueType();
536     ASTContext &ctx = getContext();
537     if (T->getAs<ObjCObjectType>())
538       return ctx.getObjCObjectPointerType(T);
539     return ctx.getPointerType(getValueType());
540   }
541 
getDesugaredValueType(ASTContext & Context)542   QualType getDesugaredValueType(ASTContext &Context) const {
543     QualType T = getValueType();
544     return T.getTypePtrOrNull() ? T.getDesugaredType(Context) : T;
545   }
546 
classof(const MemRegion * R)547   static bool classof(const MemRegion* R) {
548     unsigned k = R->getKind();
549     return k >= BEGIN_TYPED_VALUE_REGIONS && k <= END_TYPED_VALUE_REGIONS;
550   }
551 };
552 
553 class CodeTextRegion : public TypedRegion {
554   void anchor() override;
555 
556 protected:
CodeTextRegion(const MemSpaceRegion * sreg,Kind k)557   CodeTextRegion(const MemSpaceRegion *sreg, Kind k) : TypedRegion(sreg, k) {
558     assert(classof(this));
559   }
560 
561 public:
isBoundable()562   bool isBoundable() const override { return false; }
563 
classof(const MemRegion * R)564   static bool classof(const MemRegion* R) {
565     Kind k = R->getKind();
566     return k >= BEGIN_CODE_TEXT_REGIONS && k <= END_CODE_TEXT_REGIONS;
567   }
568 };
569 
570 /// FunctionCodeRegion - A region that represents code texts of function.
571 class FunctionCodeRegion : public CodeTextRegion {
572   friend class MemRegionManager;
573 
574   const NamedDecl *FD;
575 
FunctionCodeRegion(const NamedDecl * fd,const CodeSpaceRegion * sreg)576   FunctionCodeRegion(const NamedDecl *fd, const CodeSpaceRegion* sreg)
577       : CodeTextRegion(sreg, FunctionCodeRegionKind), FD(fd) {
578     assert(isa<ObjCMethodDecl>(fd) || isa<FunctionDecl>(fd));
579   }
580 
581   static void ProfileRegion(llvm::FoldingSetNodeID& ID, const NamedDecl *FD,
582                             const MemRegion*);
583 
584 public:
getLocationType()585   QualType getLocationType() const override {
586     const ASTContext &Ctx = getContext();
587     if (const auto *D = dyn_cast<FunctionDecl>(FD)) {
588       return Ctx.getPointerType(D->getType());
589     }
590 
591     assert(isa<ObjCMethodDecl>(FD));
592     assert(false && "Getting the type of ObjCMethod is not supported yet");
593 
594     // TODO: We might want to return a different type here (ex: id (*ty)(...))
595     //       depending on how it is used.
596     return {};
597   }
598 
getDecl()599   const NamedDecl *getDecl() const {
600     return FD;
601   }
602 
603   void dumpToStream(raw_ostream &os) const override;
604 
605   void Profile(llvm::FoldingSetNodeID& ID) const override;
606 
classof(const MemRegion * R)607   static bool classof(const MemRegion* R) {
608     return R->getKind() == FunctionCodeRegionKind;
609   }
610 };
611 
612 /// BlockCodeRegion - A region that represents code texts of blocks (closures).
613 ///  Blocks are represented with two kinds of regions.  BlockCodeRegions
614 ///  represent the "code", while BlockDataRegions represent instances of blocks,
615 ///  which correspond to "code+data".  The distinction is important, because
616 ///  like a closure a block captures the values of externally referenced
617 ///  variables.
618 class BlockCodeRegion : public CodeTextRegion {
619   friend class MemRegionManager;
620 
621   const BlockDecl *BD;
622   AnalysisDeclContext *AC;
623   CanQualType locTy;
624 
BlockCodeRegion(const BlockDecl * bd,CanQualType lTy,AnalysisDeclContext * ac,const CodeSpaceRegion * sreg)625   BlockCodeRegion(const BlockDecl *bd, CanQualType lTy,
626                   AnalysisDeclContext *ac, const CodeSpaceRegion* sreg)
627       : CodeTextRegion(sreg, BlockCodeRegionKind), BD(bd), AC(ac), locTy(lTy) {
628     assert(bd);
629     assert(ac);
630     assert(lTy->getTypePtr()->isBlockPointerType());
631   }
632 
633   static void ProfileRegion(llvm::FoldingSetNodeID& ID, const BlockDecl *BD,
634                             CanQualType, const AnalysisDeclContext*,
635                             const MemRegion*);
636 
637 public:
getLocationType()638   QualType getLocationType() const override {
639     return locTy;
640   }
641 
getDecl()642   const BlockDecl *getDecl() const {
643     return BD;
644   }
645 
getAnalysisDeclContext()646   AnalysisDeclContext *getAnalysisDeclContext() const { return AC; }
647 
648   void dumpToStream(raw_ostream &os) const override;
649 
650   void Profile(llvm::FoldingSetNodeID& ID) const override;
651 
classof(const MemRegion * R)652   static bool classof(const MemRegion* R) {
653     return R->getKind() == BlockCodeRegionKind;
654   }
655 };
656 
657 /// BlockDataRegion - A region that represents a block instance.
658 ///  Blocks are represented with two kinds of regions.  BlockCodeRegions
659 ///  represent the "code", while BlockDataRegions represent instances of blocks,
660 ///  which correspond to "code+data".  The distinction is important, because
661 ///  like a closure a block captures the values of externally referenced
662 ///  variables.
663 class BlockDataRegion : public TypedRegion {
664   friend class MemRegionManager;
665 
666   const BlockCodeRegion *BC;
667   const LocationContext *LC; // Can be null
668   unsigned BlockCount;
669   void *ReferencedVars = nullptr;
670   void *OriginalVars = nullptr;
671 
BlockDataRegion(const BlockCodeRegion * bc,const LocationContext * lc,unsigned count,const MemSpaceRegion * sreg)672   BlockDataRegion(const BlockCodeRegion *bc, const LocationContext *lc,
673                   unsigned count, const MemSpaceRegion *sreg)
674       : TypedRegion(sreg, BlockDataRegionKind), BC(bc), LC(lc),
675         BlockCount(count) {
676     assert(bc);
677     assert(lc);
678     assert(isa<GlobalImmutableSpaceRegion>(sreg) ||
679            isa<StackLocalsSpaceRegion>(sreg) ||
680            isa<UnknownSpaceRegion>(sreg));
681   }
682 
683   static void ProfileRegion(llvm::FoldingSetNodeID&, const BlockCodeRegion *,
684                             const LocationContext *, unsigned,
685                             const MemRegion *);
686 
687 public:
getCodeRegion()688   const BlockCodeRegion *getCodeRegion() const { return BC; }
689 
getDecl()690   const BlockDecl *getDecl() const { return BC->getDecl(); }
691 
getLocationType()692   QualType getLocationType() const override { return BC->getLocationType(); }
693 
694   class referenced_vars_iterator {
695     const MemRegion * const *R;
696     const MemRegion * const *OriginalR;
697 
698   public:
referenced_vars_iterator(const MemRegion * const * r,const MemRegion * const * originalR)699     explicit referenced_vars_iterator(const MemRegion * const *r,
700                                       const MemRegion * const *originalR)
701         : R(r), OriginalR(originalR) {}
702 
getCapturedRegion()703     const VarRegion *getCapturedRegion() const {
704       return cast<VarRegion>(*R);
705     }
706 
getOriginalRegion()707     const VarRegion *getOriginalRegion() const {
708       return cast<VarRegion>(*OriginalR);
709     }
710 
711     bool operator==(const referenced_vars_iterator &I) const {
712       assert((R == nullptr) == (I.R == nullptr));
713       return I.R == R;
714     }
715 
716     bool operator!=(const referenced_vars_iterator &I) const {
717       assert((R == nullptr) == (I.R == nullptr));
718       return I.R != R;
719     }
720 
721     referenced_vars_iterator &operator++() {
722       ++R;
723       ++OriginalR;
724       return *this;
725     }
726   };
727 
728   /// Return the original region for a captured region, if
729   /// one exists.
730   const VarRegion *getOriginalRegion(const VarRegion *VR) const;
731 
732   referenced_vars_iterator referenced_vars_begin() const;
733   referenced_vars_iterator referenced_vars_end() const;
734 
735   void dumpToStream(raw_ostream &os) const override;
736 
737   void Profile(llvm::FoldingSetNodeID& ID) const override;
738 
classof(const MemRegion * R)739   static bool classof(const MemRegion* R) {
740     return R->getKind() == BlockDataRegionKind;
741   }
742 
743 private:
744   void LazyInitializeReferencedVars();
745   std::pair<const VarRegion *, const VarRegion *>
746   getCaptureRegions(const VarDecl *VD);
747 };
748 
749 /// SymbolicRegion - A special, "non-concrete" region. Unlike other region
750 ///  classes, SymbolicRegion represents a region that serves as an alias for
751 ///  either a real region, a NULL pointer, etc.  It essentially is used to
752 ///  map the concept of symbolic values into the domain of regions.  Symbolic
753 ///  regions do not need to be typed.
754 class SymbolicRegion : public SubRegion {
755   friend class MemRegionManager;
756 
757   const SymbolRef sym;
758 
SymbolicRegion(const SymbolRef s,const MemSpaceRegion * sreg)759   SymbolicRegion(const SymbolRef s, const MemSpaceRegion *sreg)
760       : SubRegion(sreg, SymbolicRegionKind), sym(s) {
761     // Because pointer arithmetic is represented by ElementRegion layers,
762     // the base symbol here should not contain any arithmetic.
763     assert(s && isa<SymbolData>(s));
764     assert(s->getType()->isAnyPointerType() ||
765            s->getType()->isReferenceType() ||
766            s->getType()->isBlockPointerType());
767     assert(isa<UnknownSpaceRegion>(sreg) || isa<HeapSpaceRegion>(sreg));
768   }
769 
770 public:
getSymbol()771   SymbolRef getSymbol() const { return sym; }
772 
isBoundable()773   bool isBoundable() const override { return true; }
774 
775   void Profile(llvm::FoldingSetNodeID& ID) const override;
776 
777   static void ProfileRegion(llvm::FoldingSetNodeID& ID,
778                             SymbolRef sym,
779                             const MemRegion* superRegion);
780 
781   void dumpToStream(raw_ostream &os) const override;
782 
classof(const MemRegion * R)783   static bool classof(const MemRegion* R) {
784     return R->getKind() == SymbolicRegionKind;
785   }
786 };
787 
788 /// StringRegion - Region associated with a StringLiteral.
789 class StringRegion : public TypedValueRegion {
790   friend class MemRegionManager;
791 
792   const StringLiteral *Str;
793 
StringRegion(const StringLiteral * str,const GlobalInternalSpaceRegion * sreg)794   StringRegion(const StringLiteral *str, const GlobalInternalSpaceRegion *sreg)
795       : TypedValueRegion(sreg, StringRegionKind), Str(str) {
796     assert(str);
797   }
798 
799   static void ProfileRegion(llvm::FoldingSetNodeID &ID,
800                             const StringLiteral *Str,
801                             const MemRegion *superRegion);
802 
803 public:
getStringLiteral()804   const StringLiteral *getStringLiteral() const { return Str; }
805 
getValueType()806   QualType getValueType() const override { return Str->getType(); }
807 
isBoundable()808   bool isBoundable() const override { return false; }
809 
Profile(llvm::FoldingSetNodeID & ID)810   void Profile(llvm::FoldingSetNodeID& ID) const override {
811     ProfileRegion(ID, Str, superRegion);
812   }
813 
814   void dumpToStream(raw_ostream &os) const override;
815 
classof(const MemRegion * R)816   static bool classof(const MemRegion* R) {
817     return R->getKind() == StringRegionKind;
818   }
819 };
820 
821 /// The region associated with an ObjCStringLiteral.
822 class ObjCStringRegion : public TypedValueRegion {
823   friend class MemRegionManager;
824 
825   const ObjCStringLiteral *Str;
826 
ObjCStringRegion(const ObjCStringLiteral * str,const GlobalInternalSpaceRegion * sreg)827   ObjCStringRegion(const ObjCStringLiteral *str,
828                    const GlobalInternalSpaceRegion *sreg)
829       : TypedValueRegion(sreg, ObjCStringRegionKind), Str(str) {
830     assert(str);
831   }
832 
833   static void ProfileRegion(llvm::FoldingSetNodeID &ID,
834                             const ObjCStringLiteral *Str,
835                             const MemRegion *superRegion);
836 
837 public:
getObjCStringLiteral()838   const ObjCStringLiteral *getObjCStringLiteral() const { return Str; }
839 
getValueType()840   QualType getValueType() const override { return Str->getType(); }
841 
isBoundable()842   bool isBoundable() const override { return false; }
843 
Profile(llvm::FoldingSetNodeID & ID)844   void Profile(llvm::FoldingSetNodeID& ID) const override {
845     ProfileRegion(ID, Str, superRegion);
846   }
847 
848   void dumpToStream(raw_ostream &os) const override;
849 
classof(const MemRegion * R)850   static bool classof(const MemRegion* R) {
851     return R->getKind() == ObjCStringRegionKind;
852   }
853 };
854 
855 /// CompoundLiteralRegion - A memory region representing a compound literal.
856 ///   Compound literals are essentially temporaries that are stack allocated
857 ///   or in the global constant pool.
858 class CompoundLiteralRegion : public TypedValueRegion {
859   friend class MemRegionManager;
860 
861   const CompoundLiteralExpr *CL;
862 
CompoundLiteralRegion(const CompoundLiteralExpr * cl,const MemSpaceRegion * sReg)863   CompoundLiteralRegion(const CompoundLiteralExpr *cl,
864                         const MemSpaceRegion *sReg)
865       : TypedValueRegion(sReg, CompoundLiteralRegionKind), CL(cl) {
866     assert(cl);
867     assert(isa<GlobalInternalSpaceRegion>(sReg) ||
868            isa<StackLocalsSpaceRegion>(sReg));
869   }
870 
871   static void ProfileRegion(llvm::FoldingSetNodeID& ID,
872                             const CompoundLiteralExpr *CL,
873                             const MemRegion* superRegion);
874 
875 public:
getValueType()876   QualType getValueType() const override { return CL->getType(); }
877 
isBoundable()878   bool isBoundable() const override { return !CL->isFileScope(); }
879 
880   void Profile(llvm::FoldingSetNodeID& ID) const override;
881 
882   void dumpToStream(raw_ostream &os) const override;
883 
getLiteralExpr()884   const CompoundLiteralExpr *getLiteralExpr() const { return CL; }
885 
classof(const MemRegion * R)886   static bool classof(const MemRegion* R) {
887     return R->getKind() == CompoundLiteralRegionKind;
888   }
889 };
890 
891 class DeclRegion : public TypedValueRegion {
892 protected:
DeclRegion(const MemRegion * sReg,Kind k)893   DeclRegion(const MemRegion *sReg, Kind k) : TypedValueRegion(sReg, k) {
894     assert(classof(this));
895   }
896 
897 public:
898   virtual const ValueDecl *getDecl() const = 0;
899 
classof(const MemRegion * R)900   static bool classof(const MemRegion* R) {
901     unsigned k = R->getKind();
902     return k >= BEGIN_DECL_REGIONS && k <= END_DECL_REGIONS;
903   }
904 };
905 
906 class VarRegion : public DeclRegion {
907   friend class MemRegionManager;
908 
909 protected:
910   // Constructors and protected methods.
VarRegion(const MemRegion * sReg,Kind k)911   VarRegion(const MemRegion *sReg, Kind k) : DeclRegion(sReg, k) {
912     // VarRegion appears in unknown space when it's a block variable as seen
913     // from a block using it, when this block is analyzed at top-level.
914     // Other block variables appear within block data regions,
915     // which, unlike everything else on this list, are not memory spaces.
916     assert(isa<GlobalsSpaceRegion>(sReg) || isa<StackSpaceRegion>(sReg) ||
917            isa<BlockDataRegion>(sReg) || isa<UnknownSpaceRegion>(sReg));
918   }
919 
920 public:
921   const VarDecl *getDecl() const override = 0;
922 
923   const StackFrameContext *getStackFrame() const;
924 
getValueType()925   QualType getValueType() const override {
926     // FIXME: We can cache this if needed.
927     return getDecl()->getType();
928   }
929 
classof(const MemRegion * R)930   static bool classof(const MemRegion *R) {
931     unsigned k = R->getKind();
932     return k >= BEGIN_VAR_REGIONS && k <= END_VAR_REGIONS;
933   }
934 };
935 
936 class NonParamVarRegion : public VarRegion {
937   friend class MemRegionManager;
938 
939   const VarDecl *VD;
940 
941   // Constructors and private methods.
NonParamVarRegion(const VarDecl * vd,const MemRegion * sReg)942   NonParamVarRegion(const VarDecl *vd, const MemRegion *sReg)
943       : VarRegion(sReg, NonParamVarRegionKind), VD(vd) {
944     // VarRegion appears in unknown space when it's a block variable as seen
945     // from a block using it, when this block is analyzed at top-level.
946     // Other block variables appear within block data regions,
947     // which, unlike everything else on this list, are not memory spaces.
948     assert(isa<GlobalsSpaceRegion>(sReg) || isa<StackSpaceRegion>(sReg) ||
949            isa<BlockDataRegion>(sReg) || isa<UnknownSpaceRegion>(sReg));
950   }
951 
952   static void ProfileRegion(llvm::FoldingSetNodeID &ID, const VarDecl *VD,
953                             const MemRegion *superRegion);
954 
955 public:
956   void Profile(llvm::FoldingSetNodeID &ID) const override;
957 
getDecl()958   const VarDecl *getDecl() const override { return VD; }
959 
getValueType()960   QualType getValueType() const override {
961     // FIXME: We can cache this if needed.
962     return getDecl()->getType();
963   }
964 
965   void dumpToStream(raw_ostream &os) const override;
966 
967   bool canPrintPrettyAsExpr() const override;
968 
969   void printPrettyAsExpr(raw_ostream &os) const override;
970 
classof(const MemRegion * R)971   static bool classof(const MemRegion* R) {
972     return R->getKind() == NonParamVarRegionKind;
973   }
974 };
975 
976 /// ParamVarRegion - Represents a region for paremters. Only parameters of the
977 /// function in the current stack frame are represented as `ParamVarRegion`s.
978 /// Parameters of top-level analyzed functions as well as captured paremeters
979 /// by lambdas and blocks are repesented as `VarRegion`s.
980 
981 // FIXME: `ParamVarRegion` only supports parameters of functions, C++
982 // constructors, blocks and Objective-C methods with existing `Decl`. Upon
983 // implementing stack frame creations for functions without decl (functions
984 // passed by unknown function pointer) methods of `ParamVarRegion` must be
985 // updated.
986 class ParamVarRegion : public VarRegion {
987   friend class MemRegionManager;
988 
989   const Expr *OriginExpr;
990   unsigned Index;
991 
ParamVarRegion(const Expr * OE,unsigned Idx,const MemRegion * SReg)992   ParamVarRegion(const Expr *OE, unsigned Idx, const MemRegion *SReg)
993       : VarRegion(SReg, ParamVarRegionKind), OriginExpr(OE), Index(Idx) {
994     assert(!cast<StackSpaceRegion>(SReg)->getStackFrame()->inTopFrame());
995   }
996 
997   static void ProfileRegion(llvm::FoldingSetNodeID &ID, const Expr *OE,
998                             unsigned Idx, const MemRegion *SReg);
999 
1000 public:
getOriginExpr()1001   const Expr *getOriginExpr() const { return OriginExpr; }
getIndex()1002   unsigned getIndex() const { return Index; }
1003 
1004   void Profile(llvm::FoldingSetNodeID& ID) const override;
1005 
1006   void dumpToStream(raw_ostream &os) const override;
1007 
1008   QualType getValueType() const override;
1009   const ParmVarDecl *getDecl() const override;
1010 
1011   bool canPrintPrettyAsExpr() const override;
1012   void printPrettyAsExpr(raw_ostream &os) const override;
1013 
classof(const MemRegion * R)1014   static bool classof(const MemRegion *R) {
1015     return R->getKind() == ParamVarRegionKind;
1016   }
1017 };
1018 
1019 /// CXXThisRegion - Represents the region for the implicit 'this' parameter
1020 ///  in a call to a C++ method.  This region doesn't represent the object
1021 ///  referred to by 'this', but rather 'this' itself.
1022 class CXXThisRegion : public TypedValueRegion {
1023   friend class MemRegionManager;
1024 
CXXThisRegion(const PointerType * thisPointerTy,const StackArgumentsSpaceRegion * sReg)1025   CXXThisRegion(const PointerType *thisPointerTy,
1026                 const StackArgumentsSpaceRegion *sReg)
1027       : TypedValueRegion(sReg, CXXThisRegionKind),
1028         ThisPointerTy(thisPointerTy) {
1029     assert(ThisPointerTy->getPointeeType()->getAsCXXRecordDecl() &&
1030            "Invalid region type!");
1031   }
1032 
1033   static void ProfileRegion(llvm::FoldingSetNodeID &ID,
1034                             const PointerType *PT,
1035                             const MemRegion *sReg);
1036 
1037 public:
1038   void Profile(llvm::FoldingSetNodeID &ID) const override;
1039 
getValueType()1040   QualType getValueType() const override {
1041     return QualType(ThisPointerTy, 0);
1042   }
1043 
1044   void dumpToStream(raw_ostream &os) const override;
1045 
classof(const MemRegion * R)1046   static bool classof(const MemRegion* R) {
1047     return R->getKind() == CXXThisRegionKind;
1048   }
1049 
1050 private:
1051   const PointerType *ThisPointerTy;
1052 };
1053 
1054 class FieldRegion : public DeclRegion {
1055   friend class MemRegionManager;
1056 
1057   const FieldDecl *FD;
1058 
FieldRegion(const FieldDecl * fd,const SubRegion * sReg)1059   FieldRegion(const FieldDecl *fd, const SubRegion *sReg)
1060       : DeclRegion(sReg, FieldRegionKind), FD(fd) {}
1061 
ProfileRegion(llvm::FoldingSetNodeID & ID,const FieldDecl * FD,const MemRegion * superRegion)1062   static void ProfileRegion(llvm::FoldingSetNodeID &ID, const FieldDecl *FD,
1063                             const MemRegion* superRegion) {
1064     ID.AddInteger(static_cast<unsigned>(FieldRegionKind));
1065     ID.AddPointer(FD);
1066     ID.AddPointer(superRegion);
1067   }
1068 
1069 public:
getDecl()1070   const FieldDecl *getDecl() const override { return FD; }
1071 
1072   void Profile(llvm::FoldingSetNodeID &ID) const override;
1073 
getValueType()1074   QualType getValueType() const override {
1075     // FIXME: We can cache this if needed.
1076     return getDecl()->getType();
1077   }
1078 
1079   void dumpToStream(raw_ostream &os) const override;
1080 
1081   bool canPrintPretty() const override;
1082   void printPretty(raw_ostream &os) const override;
1083   bool canPrintPrettyAsExpr() const override;
1084   void printPrettyAsExpr(raw_ostream &os) const override;
1085 
classof(const MemRegion * R)1086   static bool classof(const MemRegion* R) {
1087     return R->getKind() == FieldRegionKind;
1088   }
1089 };
1090 
1091 class ObjCIvarRegion : public DeclRegion {
1092   friend class MemRegionManager;
1093 
1094   const ObjCIvarDecl *IVD;
1095 
1096   ObjCIvarRegion(const ObjCIvarDecl *ivd, const SubRegion *sReg);
1097 
1098   static void ProfileRegion(llvm::FoldingSetNodeID& ID, const ObjCIvarDecl *ivd,
1099                             const MemRegion* superRegion);
1100 
1101 public:
1102   const ObjCIvarDecl *getDecl() const override;
1103 
1104   void Profile(llvm::FoldingSetNodeID& ID) const override;
1105 
1106   QualType getValueType() const override;
1107 
1108   bool canPrintPrettyAsExpr() const override;
1109   void printPrettyAsExpr(raw_ostream &os) const override;
1110 
1111   void dumpToStream(raw_ostream &os) const override;
1112 
classof(const MemRegion * R)1113   static bool classof(const MemRegion* R) {
1114     return R->getKind() == ObjCIvarRegionKind;
1115   }
1116 };
1117 
1118 //===----------------------------------------------------------------------===//
1119 // Auxiliary data classes for use with MemRegions.
1120 //===----------------------------------------------------------------------===//
1121 
1122 class RegionRawOffset {
1123   friend class ElementRegion;
1124 
1125   const MemRegion *Region;
1126   CharUnits Offset;
1127 
1128   RegionRawOffset(const MemRegion* reg, CharUnits offset = CharUnits::Zero())
Region(reg)1129       : Region(reg), Offset(offset) {}
1130 
1131 public:
1132   // FIXME: Eventually support symbolic offsets.
getOffset()1133   CharUnits getOffset() const { return Offset; }
getRegion()1134   const MemRegion *getRegion() const { return Region; }
1135 
1136   void dumpToStream(raw_ostream &os) const;
1137   void dump() const;
1138 };
1139 
1140 /// ElementRegion is used to represent both array elements and casts.
1141 class ElementRegion : public TypedValueRegion {
1142   friend class MemRegionManager;
1143 
1144   QualType ElementType;
1145   NonLoc Index;
1146 
ElementRegion(QualType elementType,NonLoc Idx,const SubRegion * sReg)1147   ElementRegion(QualType elementType, NonLoc Idx, const SubRegion *sReg)
1148       : TypedValueRegion(sReg, ElementRegionKind), ElementType(elementType),
1149         Index(Idx) {
1150     assert((!Idx.getAs<nonloc::ConcreteInt>() ||
1151             Idx.castAs<nonloc::ConcreteInt>().getValue().isSigned()) &&
1152            "The index must be signed");
1153     assert(!elementType.isNull() && !elementType->isVoidType() &&
1154            "Invalid region type!");
1155   }
1156 
1157   static void ProfileRegion(llvm::FoldingSetNodeID& ID, QualType elementType,
1158                             SVal Idx, const MemRegion* superRegion);
1159 
1160 public:
getIndex()1161   NonLoc getIndex() const { return Index; }
1162 
getValueType()1163   QualType getValueType() const override { return ElementType; }
1164 
getElementType()1165   QualType getElementType() const { return ElementType; }
1166 
1167   /// Compute the offset within the array. The array might also be a subobject.
1168   RegionRawOffset getAsArrayOffset() const;
1169 
1170   void dumpToStream(raw_ostream &os) const override;
1171 
1172   void Profile(llvm::FoldingSetNodeID& ID) const override;
1173 
classof(const MemRegion * R)1174   static bool classof(const MemRegion* R) {
1175     return R->getKind() == ElementRegionKind;
1176   }
1177 };
1178 
1179 // C++ temporary object associated with an expression.
1180 class CXXTempObjectRegion : public TypedValueRegion {
1181   friend class MemRegionManager;
1182 
1183   Expr const *Ex;
1184 
CXXTempObjectRegion(Expr const * E,MemSpaceRegion const * sReg)1185   CXXTempObjectRegion(Expr const *E, MemSpaceRegion const *sReg)
1186       : TypedValueRegion(sReg, CXXTempObjectRegionKind), Ex(E) {
1187     assert(E);
1188     assert(isa<StackLocalsSpaceRegion>(sReg) ||
1189            isa<GlobalInternalSpaceRegion>(sReg));
1190   }
1191 
1192   static void ProfileRegion(llvm::FoldingSetNodeID &ID,
1193                             Expr const *E, const MemRegion *sReg);
1194 
1195 public:
getExpr()1196   const Expr *getExpr() const { return Ex; }
1197 
getValueType()1198   QualType getValueType() const override { return Ex->getType(); }
1199 
1200   void dumpToStream(raw_ostream &os) const override;
1201 
1202   void Profile(llvm::FoldingSetNodeID &ID) const override;
1203 
classof(const MemRegion * R)1204   static bool classof(const MemRegion* R) {
1205     return R->getKind() == CXXTempObjectRegionKind;
1206   }
1207 };
1208 
1209 // CXXBaseObjectRegion represents a base object within a C++ object. It is
1210 // identified by the base class declaration and the region of its parent object.
1211 class CXXBaseObjectRegion : public TypedValueRegion {
1212   friend class MemRegionManager;
1213 
1214   llvm::PointerIntPair<const CXXRecordDecl *, 1, bool> Data;
1215 
CXXBaseObjectRegion(const CXXRecordDecl * RD,bool IsVirtual,const SubRegion * SReg)1216   CXXBaseObjectRegion(const CXXRecordDecl *RD, bool IsVirtual,
1217                       const SubRegion *SReg)
1218       : TypedValueRegion(SReg, CXXBaseObjectRegionKind), Data(RD, IsVirtual) {
1219     assert(RD);
1220   }
1221 
1222   static void ProfileRegion(llvm::FoldingSetNodeID &ID, const CXXRecordDecl *RD,
1223                             bool IsVirtual, const MemRegion *SReg);
1224 
1225 public:
getDecl()1226   const CXXRecordDecl *getDecl() const { return Data.getPointer(); }
isVirtual()1227   bool isVirtual() const { return Data.getInt(); }
1228 
1229   QualType getValueType() const override;
1230 
1231   void dumpToStream(raw_ostream &os) const override;
1232 
1233   void Profile(llvm::FoldingSetNodeID &ID) const override;
1234 
1235   bool canPrintPrettyAsExpr() const override;
1236 
1237   void printPrettyAsExpr(raw_ostream &os) const override;
1238 
classof(const MemRegion * region)1239   static bool classof(const MemRegion *region) {
1240     return region->getKind() == CXXBaseObjectRegionKind;
1241   }
1242 };
1243 
1244 // CXXDerivedObjectRegion represents a derived-class object that surrounds
1245 // a C++ object. It is identified by the derived class declaration and the
1246 // region of its parent object. It is a bit counter-intuitive (but not otherwise
1247 // unseen) that this region represents a larger segment of memory that its
1248 // super-region.
1249 class CXXDerivedObjectRegion : public TypedValueRegion {
1250   friend class MemRegionManager;
1251 
1252   const CXXRecordDecl *DerivedD;
1253 
CXXDerivedObjectRegion(const CXXRecordDecl * DerivedD,const SubRegion * SReg)1254   CXXDerivedObjectRegion(const CXXRecordDecl *DerivedD, const SubRegion *SReg)
1255       : TypedValueRegion(SReg, CXXDerivedObjectRegionKind), DerivedD(DerivedD) {
1256     assert(DerivedD);
1257     // In case of a concrete region, it should always be possible to model
1258     // the base-to-derived cast by undoing a previous derived-to-base cast,
1259     // otherwise the cast is most likely ill-formed.
1260     assert(SReg->getSymbolicBase() &&
1261            "Should have unwrapped a base region instead!");
1262   }
1263 
1264   static void ProfileRegion(llvm::FoldingSetNodeID &ID, const CXXRecordDecl *RD,
1265                             const MemRegion *SReg);
1266 
1267 public:
getDecl()1268   const CXXRecordDecl *getDecl() const { return DerivedD; }
1269 
1270   QualType getValueType() const override;
1271 
1272   void dumpToStream(raw_ostream &os) const override;
1273 
1274   void Profile(llvm::FoldingSetNodeID &ID) const override;
1275 
1276   bool canPrintPrettyAsExpr() const override;
1277 
1278   void printPrettyAsExpr(raw_ostream &os) const override;
1279 
classof(const MemRegion * region)1280   static bool classof(const MemRegion *region) {
1281     return region->getKind() == CXXDerivedObjectRegionKind;
1282   }
1283 };
1284 
1285 template<typename RegionTy>
getAs()1286 const RegionTy* MemRegion::getAs() const {
1287   if (const auto *RT = dyn_cast<RegionTy>(this))
1288     return RT;
1289 
1290   return nullptr;
1291 }
1292 
1293 template<typename RegionTy>
castAs()1294 const RegionTy* MemRegion::castAs() const {
1295   return cast<RegionTy>(this);
1296 }
1297 
1298 //===----------------------------------------------------------------------===//
1299 // MemRegionManager - Factory object for creating regions.
1300 //===----------------------------------------------------------------------===//
1301 
1302 class MemRegionManager {
1303   ASTContext &Ctx;
1304   llvm::BumpPtrAllocator& A;
1305 
1306   llvm::FoldingSet<MemRegion> Regions;
1307 
1308   GlobalInternalSpaceRegion *InternalGlobals = nullptr;
1309   GlobalSystemSpaceRegion *SystemGlobals = nullptr;
1310   GlobalImmutableSpaceRegion *ImmutableGlobals = nullptr;
1311 
1312   llvm::DenseMap<const StackFrameContext *, StackLocalsSpaceRegion *>
1313     StackLocalsSpaceRegions;
1314   llvm::DenseMap<const StackFrameContext *, StackArgumentsSpaceRegion *>
1315     StackArgumentsSpaceRegions;
1316   llvm::DenseMap<const CodeTextRegion *, StaticGlobalSpaceRegion *>
1317     StaticsGlobalSpaceRegions;
1318 
1319   HeapSpaceRegion *heap = nullptr;
1320   UnknownSpaceRegion *unknown = nullptr;
1321   CodeSpaceRegion *code = nullptr;
1322 
1323 public:
MemRegionManager(ASTContext & c,llvm::BumpPtrAllocator & a)1324   MemRegionManager(ASTContext &c, llvm::BumpPtrAllocator &a) : Ctx(c), A(a) {}
1325   ~MemRegionManager();
1326 
getContext()1327   ASTContext &getContext() { return Ctx; }
1328 
getAllocator()1329   llvm::BumpPtrAllocator &getAllocator() { return A; }
1330 
1331   /// \returns The static size in bytes of the region \p MR.
1332   /// \note The region \p MR must be a 'SubRegion'.
1333   DefinedOrUnknownSVal getStaticSize(const MemRegion *MR,
1334                                      SValBuilder &SVB) const;
1335 
1336   /// getStackLocalsRegion - Retrieve the memory region associated with the
1337   ///  specified stack frame.
1338   const StackLocalsSpaceRegion *
1339   getStackLocalsRegion(const StackFrameContext *STC);
1340 
1341   /// getStackArgumentsRegion - Retrieve the memory region associated with
1342   ///  function/method arguments of the specified stack frame.
1343   const StackArgumentsSpaceRegion *
1344   getStackArgumentsRegion(const StackFrameContext *STC);
1345 
1346   /// getGlobalsRegion - Retrieve the memory region associated with
1347   ///  global variables.
1348   const GlobalsSpaceRegion *getGlobalsRegion(
1349       MemRegion::Kind K = MemRegion::GlobalInternalSpaceRegionKind,
1350       const CodeTextRegion *R = nullptr);
1351 
1352   /// getHeapRegion - Retrieve the memory region associated with the
1353   ///  generic "heap".
1354   const HeapSpaceRegion *getHeapRegion();
1355 
1356   /// getUnknownRegion - Retrieve the memory region associated with unknown
1357   /// memory space.
1358   const UnknownSpaceRegion *getUnknownRegion();
1359 
1360   const CodeSpaceRegion *getCodeRegion();
1361 
1362   /// getAllocaRegion - Retrieve a region associated with a call to alloca().
1363   const AllocaRegion *getAllocaRegion(const Expr *Ex, unsigned Cnt,
1364                                       const LocationContext *LC);
1365 
1366   /// getCompoundLiteralRegion - Retrieve the region associated with a
1367   ///  given CompoundLiteral.
1368   const CompoundLiteralRegion*
1369   getCompoundLiteralRegion(const CompoundLiteralExpr *CL,
1370                            const LocationContext *LC);
1371 
1372   /// getCXXThisRegion - Retrieve the [artificial] region associated with the
1373   ///  parameter 'this'.
1374   const CXXThisRegion *getCXXThisRegion(QualType thisPointerTy,
1375                                         const LocationContext *LC);
1376 
1377   /// Retrieve or create a "symbolic" memory region.
1378   const SymbolicRegion* getSymbolicRegion(SymbolRef Sym);
1379 
1380   /// Return a unique symbolic region belonging to heap memory space.
1381   const SymbolicRegion *getSymbolicHeapRegion(SymbolRef sym);
1382 
1383   const StringRegion *getStringRegion(const StringLiteral *Str);
1384 
1385   const ObjCStringRegion *getObjCStringRegion(const ObjCStringLiteral *Str);
1386 
1387   /// getVarRegion - Retrieve or create the memory region associated with
1388   ///  a specified VarDecl and LocationContext.
1389   const VarRegion *getVarRegion(const VarDecl *VD, const LocationContext *LC);
1390 
1391   /// getVarRegion - Retrieve or create the memory region associated with
1392   ///  a specified VarDecl and LocationContext.
1393   const NonParamVarRegion *getNonParamVarRegion(const VarDecl *VD,
1394                                                 const MemRegion *superR);
1395 
1396   /// getParamVarRegion - Retrieve or create the memory region
1397   /// associated with a specified CallExpr, Index and LocationContext.
1398   const ParamVarRegion *getParamVarRegion(const Expr *OriginExpr,
1399                                           unsigned Index,
1400                                           const LocationContext *LC);
1401 
1402   /// getElementRegion - Retrieve the memory region associated with the
1403   ///  associated element type, index, and super region.
1404   const ElementRegion *getElementRegion(QualType elementType, NonLoc Idx,
1405                                         const SubRegion *superRegion,
1406                                         ASTContext &Ctx);
1407 
getElementRegionWithSuper(const ElementRegion * ER,const SubRegion * superRegion)1408   const ElementRegion *getElementRegionWithSuper(const ElementRegion *ER,
1409                                                  const SubRegion *superRegion) {
1410     return getElementRegion(ER->getElementType(), ER->getIndex(),
1411                             superRegion, ER->getContext());
1412   }
1413 
1414   /// getFieldRegion - Retrieve or create the memory region associated with
1415   ///  a specified FieldDecl.  'superRegion' corresponds to the containing
1416   ///  memory region (which typically represents the memory representing
1417   ///  a structure or class).
1418   const FieldRegion *getFieldRegion(const FieldDecl *fd,
1419                                     const SubRegion* superRegion);
1420 
getFieldRegionWithSuper(const FieldRegion * FR,const SubRegion * superRegion)1421   const FieldRegion *getFieldRegionWithSuper(const FieldRegion *FR,
1422                                              const SubRegion *superRegion) {
1423     return getFieldRegion(FR->getDecl(), superRegion);
1424   }
1425 
1426   /// getObjCIvarRegion - Retrieve or create the memory region associated with
1427   ///   a specified Objective-c instance variable.  'superRegion' corresponds
1428   ///   to the containing region (which typically represents the Objective-C
1429   ///   object).
1430   const ObjCIvarRegion *getObjCIvarRegion(const ObjCIvarDecl *ivd,
1431                                           const SubRegion* superRegion);
1432 
1433   const CXXTempObjectRegion *getCXXTempObjectRegion(Expr const *Ex,
1434                                                     LocationContext const *LC);
1435 
1436   /// Create a CXXBaseObjectRegion with the given base class for region
1437   /// \p Super.
1438   ///
1439   /// The type of \p Super is assumed be a class deriving from \p BaseClass.
1440   const CXXBaseObjectRegion *
1441   getCXXBaseObjectRegion(const CXXRecordDecl *BaseClass, const SubRegion *Super,
1442                          bool IsVirtual);
1443 
1444   /// Create a CXXBaseObjectRegion with the same CXXRecordDecl but a different
1445   /// super region.
1446   const CXXBaseObjectRegion *
getCXXBaseObjectRegionWithSuper(const CXXBaseObjectRegion * baseReg,const SubRegion * superRegion)1447   getCXXBaseObjectRegionWithSuper(const CXXBaseObjectRegion *baseReg,
1448                                   const SubRegion *superRegion) {
1449     return getCXXBaseObjectRegion(baseReg->getDecl(), superRegion,
1450                                   baseReg->isVirtual());
1451   }
1452 
1453   /// Create a CXXDerivedObjectRegion with the given derived class for region
1454   /// \p Super. This should not be used for casting an existing
1455   /// CXXBaseObjectRegion back to the derived type; instead, CXXBaseObjectRegion
1456   /// should be removed.
1457   const CXXDerivedObjectRegion *
1458   getCXXDerivedObjectRegion(const CXXRecordDecl *BaseClass,
1459                             const SubRegion *Super);
1460 
1461   const FunctionCodeRegion *getFunctionCodeRegion(const NamedDecl *FD);
1462   const BlockCodeRegion *getBlockCodeRegion(const BlockDecl *BD,
1463                                             CanQualType locTy,
1464                                             AnalysisDeclContext *AC);
1465 
1466   /// getBlockDataRegion - Get the memory region associated with an instance
1467   ///  of a block.  Unlike many other MemRegions, the LocationContext*
1468   ///  argument is allowed to be NULL for cases where we have no known
1469   ///  context.
1470   const BlockDataRegion *getBlockDataRegion(const BlockCodeRegion *bc,
1471                                             const LocationContext *lc,
1472                                             unsigned blockCount);
1473 
1474   /// Create a CXXTempObjectRegion for temporaries which are lifetime-extended
1475   /// by static references. This differs from getCXXTempObjectRegion in the
1476   /// super-region used.
1477   const CXXTempObjectRegion *getCXXStaticTempObjectRegion(const Expr *Ex);
1478 
1479 private:
1480   template <typename RegionTy, typename SuperTy,
1481             typename Arg1Ty>
1482   RegionTy* getSubRegion(const Arg1Ty arg1,
1483                          const SuperTy* superRegion);
1484 
1485   template <typename RegionTy, typename SuperTy,
1486             typename Arg1Ty, typename Arg2Ty>
1487   RegionTy* getSubRegion(const Arg1Ty arg1, const Arg2Ty arg2,
1488                          const SuperTy* superRegion);
1489 
1490   template <typename RegionTy, typename SuperTy,
1491             typename Arg1Ty, typename Arg2Ty, typename Arg3Ty>
1492   RegionTy* getSubRegion(const Arg1Ty arg1, const Arg2Ty arg2,
1493                          const Arg3Ty arg3,
1494                          const SuperTy* superRegion);
1495 
1496   template <typename REG>
1497   const REG* LazyAllocate(REG*& region);
1498 
1499   template <typename REG, typename ARG>
1500   const REG* LazyAllocate(REG*& region, ARG a);
1501 };
1502 
1503 //===----------------------------------------------------------------------===//
1504 // Out-of-line member definitions.
1505 //===----------------------------------------------------------------------===//
1506 
getContext()1507 inline ASTContext &MemRegion::getContext() const {
1508   return getMemRegionManager().getContext();
1509 }
1510 
1511 //===----------------------------------------------------------------------===//
1512 // Means for storing region/symbol handling traits.
1513 //===----------------------------------------------------------------------===//
1514 
1515 /// Information about invalidation for a particular region/symbol.
1516 class RegionAndSymbolInvalidationTraits {
1517   using StorageTypeForKinds = unsigned char;
1518 
1519   llvm::DenseMap<const MemRegion *, StorageTypeForKinds> MRTraitsMap;
1520   llvm::DenseMap<SymbolRef, StorageTypeForKinds> SymTraitsMap;
1521 
1522   using const_region_iterator =
1523       llvm::DenseMap<const MemRegion *, StorageTypeForKinds>::const_iterator;
1524   using const_symbol_iterator =
1525       llvm::DenseMap<SymbolRef, StorageTypeForKinds>::const_iterator;
1526 
1527 public:
1528   /// Describes different invalidation traits.
1529   enum InvalidationKinds {
1530     /// Tells that a region's contents is not changed.
1531     TK_PreserveContents = 0x1,
1532 
1533     /// Suppress pointer-escaping of a region.
1534     TK_SuppressEscape = 0x2,
1535 
1536     // Do not invalidate super region.
1537     TK_DoNotInvalidateSuperRegion = 0x4,
1538 
1539     /// When applied to a MemSpaceRegion, indicates the entire memory space
1540     /// should be invalidated.
1541     TK_EntireMemSpace = 0x8
1542 
1543     // Do not forget to extend StorageTypeForKinds if number of traits exceed
1544     // the number of bits StorageTypeForKinds can store.
1545   };
1546 
1547   void setTrait(SymbolRef Sym, InvalidationKinds IK);
1548   void setTrait(const MemRegion *MR, InvalidationKinds IK);
1549   bool hasTrait(SymbolRef Sym, InvalidationKinds IK) const;
1550   bool hasTrait(const MemRegion *MR, InvalidationKinds IK) const;
1551 };
1552 
1553 //===----------------------------------------------------------------------===//
1554 // Pretty-printing regions.
1555 //===----------------------------------------------------------------------===//
1556 inline raw_ostream &operator<<(raw_ostream &os, const MemRegion *R) {
1557   R->dumpToStream(os);
1558   return os;
1559 }
1560 
1561 } // namespace ento
1562 
1563 } // namespace clang
1564 
1565 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_MEMREGION_H
1566