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
43namespace clang {
44
45class AnalysisDeclContext;
46class CXXRecordDecl;
47class Decl;
48class LocationContext;
49class StackFrameContext;
50
51namespace ento {
52
53class CodeTextRegion;
54class MemRegion;
55class MemRegionManager;
56class MemSpaceRegion;
57class SValBuilder;
58class SymbolicRegion;
59class VarRegion;
60
61/// Represent a region's offset within the top level base region.
62class 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
69public:
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;
75  RegionOffset(const MemRegion *r, int64_t off) : R(r), Offset(off) {}
76
77  const MemRegion *getRegion() const { return R; }
78
79  bool hasSymbolicOffset() const { return Offset == Symbolic; }
80
81  int64_t getOffset() const {
82    assert(!hasSymbolicOffset());
83    return Offset;
84  }
85
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.
94class MemRegion : public llvm::FoldingSetNode {
95public:
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
102private:
103  const Kind kind;
104  mutable Optional<RegionOffset> cachedOffset;
105
106protected:
107  MemRegion(Kind k) : kind(k) {}
108  virtual ~MemRegion();
109
110public:
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
169  Kind getKind() const { return kind; }
170
171  template<typename RegionTy> const RegionTy* getAs() const;
172  template<typename RegionTy> const RegionTy* castAs() const;
173
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.
199class MemSpaceRegion : public MemRegion {
200protected:
201  MemRegionManager &Mgr;
202
203  MemSpaceRegion(MemRegionManager &mgr, Kind k) : MemRegion(k), Mgr(mgr) {
204    assert(classof(this));
205  }
206
207  MemRegionManager &getMemRegionManager() const override { return Mgr; }
208
209public:
210  bool isBoundable() const override { return false; }
211
212  void Profile(llvm::FoldingSetNodeID &ID) const override;
213
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.
222class CodeSpaceRegion : public MemSpaceRegion {
223  friend class MemRegionManager;
224
225  CodeSpaceRegion(MemRegionManager &mgr)
226      : MemSpaceRegion(mgr, CodeSpaceRegionKind) {}
227
228public:
229  void dumpToStream(raw_ostream &os) const override;
230
231  static bool classof(const MemRegion *R) {
232    return R->getKind() == CodeSpaceRegionKind;
233  }
234};
235
236class GlobalsSpaceRegion : public MemSpaceRegion {
237  virtual void anchor();
238
239protected:
240  GlobalsSpaceRegion(MemRegionManager &mgr, Kind k) : MemSpaceRegion(mgr, k) {
241    assert(classof(this));
242  }
243
244public:
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.
256class StaticGlobalSpaceRegion : public GlobalsSpaceRegion {
257  friend class MemRegionManager;
258
259  const CodeTextRegion *CR;
260
261  StaticGlobalSpaceRegion(MemRegionManager &mgr, const CodeTextRegion *cr)
262      : GlobalsSpaceRegion(mgr, StaticGlobalSpaceRegionKind), CR(cr) {
263    assert(cr);
264  }
265
266public:
267  void Profile(llvm::FoldingSetNodeID &ID) const override;
268
269  void dumpToStream(raw_ostream &os) const override;
270
271  const CodeTextRegion *getCodeRegion() const { return CR; }
272
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).
284class NonStaticGlobalSpaceRegion : public GlobalsSpaceRegion {
285  void anchor() override;
286
287protected:
288  NonStaticGlobalSpaceRegion(MemRegionManager &mgr, Kind k)
289      : GlobalsSpaceRegion(mgr, k) {
290    assert(classof(this));
291  }
292
293public:
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).
303class GlobalSystemSpaceRegion : public NonStaticGlobalSpaceRegion {
304  friend class MemRegionManager;
305
306  GlobalSystemSpaceRegion(MemRegionManager &mgr)
307      : NonStaticGlobalSpaceRegion(mgr, GlobalSystemSpaceRegionKind) {}
308
309public:
310  void dumpToStream(raw_ostream &os) const override;
311
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.
322class GlobalImmutableSpaceRegion : public NonStaticGlobalSpaceRegion {
323  friend class MemRegionManager;
324
325  GlobalImmutableSpaceRegion(MemRegionManager &mgr)
326      : NonStaticGlobalSpaceRegion(mgr, GlobalImmutableSpaceRegionKind) {}
327
328public:
329  void dumpToStream(raw_ostream &os) const override;
330
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.
339class GlobalInternalSpaceRegion : public NonStaticGlobalSpaceRegion {
340  friend class MemRegionManager;
341
342  GlobalInternalSpaceRegion(MemRegionManager &mgr)
343      : NonStaticGlobalSpaceRegion(mgr, GlobalInternalSpaceRegionKind) {}
344
345public:
346  void dumpToStream(raw_ostream &os) const override;
347
348  static bool classof(const MemRegion *R) {
349    return R->getKind() == GlobalInternalSpaceRegionKind;
350  }
351};
352
353class HeapSpaceRegion : public MemSpaceRegion {
354  friend class MemRegionManager;
355
356  HeapSpaceRegion(MemRegionManager &mgr)
357      : MemSpaceRegion(mgr, HeapSpaceRegionKind) {}
358
359public:
360  void dumpToStream(raw_ostream &os) const override;
361
362  static bool classof(const MemRegion *R) {
363    return R->getKind() == HeapSpaceRegionKind;
364  }
365};
366
367class UnknownSpaceRegion : public MemSpaceRegion {
368  friend class MemRegionManager;
369
370  UnknownSpaceRegion(MemRegionManager &mgr)
371      : MemSpaceRegion(mgr, UnknownSpaceRegionKind) {}
372
373public:
374  void dumpToStream(raw_ostream &os) const override;
375
376  static bool classof(const MemRegion *R) {
377    return R->getKind() == UnknownSpaceRegionKind;
378  }
379};
380
381class StackSpaceRegion : public MemSpaceRegion {
382  virtual void anchor();
383
384  const StackFrameContext *SFC;
385
386protected:
387  StackSpaceRegion(MemRegionManager &mgr, Kind k, const StackFrameContext *sfc)
388      : MemSpaceRegion(mgr, k), SFC(sfc) {
389    assert(classof(this));
390    assert(sfc);
391  }
392
393public:
394  const StackFrameContext *getStackFrame() const { return SFC; }
395
396  void Profile(llvm::FoldingSetNodeID &ID) const override;
397
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
404class StackLocalsSpaceRegion : public StackSpaceRegion {
405  friend class MemRegionManager;
406
407  StackLocalsSpaceRegion(MemRegionManager &mgr, const StackFrameContext *sfc)
408      : StackSpaceRegion(mgr, StackLocalsSpaceRegionKind, sfc) {}
409
410public:
411  void dumpToStream(raw_ostream &os) const override;
412
413  static bool classof(const MemRegion *R) {
414    return R->getKind() == StackLocalsSpaceRegionKind;
415  }
416};
417
418class StackArgumentsSpaceRegion : public StackSpaceRegion {
419private:
420  friend class MemRegionManager;
421
422  StackArgumentsSpaceRegion(MemRegionManager &mgr, const StackFrameContext *sfc)
423      : StackSpaceRegion(mgr, StackArgumentsSpaceRegionKind, sfc) {}
424
425public:
426  void dumpToStream(raw_ostream &os) const override;
427
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.
435class SubRegion : public MemRegion {
436  virtual void anchor();
437
438protected:
439  const MemRegion* superRegion;
440
441  SubRegion(const MemRegion *sReg, Kind k) : MemRegion(k), superRegion(sReg) {
442    assert(classof(this));
443    assert(sReg);
444  }
445
446public:
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
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'.
466class 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
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
483public:
484  const Expr *getExpr() const { return Ex; }
485
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
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.
498class TypedRegion : public SubRegion {
499  void anchor() override;
500
501protected:
502  TypedRegion(const MemRegion *sReg, Kind k) : SubRegion(sReg, k) {
503    assert(classof(this));
504  }
505
506public:
507  virtual QualType getLocationType() const = 0;
508
509  QualType getDesugaredLocationType(ASTContext &Context) const {
510    return getLocationType().getDesugaredType(Context);
511  }
512
513  bool isBoundable() const override { return true; }
514
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.
522class TypedValueRegion : public TypedRegion {
523  void anchor() override;
524
525protected:
526  TypedValueRegion(const MemRegion* sReg, Kind k) : TypedRegion(sReg, k) {
527    assert(classof(this));
528  }
529
530public:
531  virtual QualType getValueType() const = 0;
532
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
542  QualType getDesugaredValueType(ASTContext &Context) const {
543    QualType T = getValueType();
544    return T.getTypePtrOrNull() ? T.getDesugaredType(Context) : T;
545  }
546
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
553class CodeTextRegion : public TypedRegion {
554  void anchor() override;
555
556protected:
557  CodeTextRegion(const MemSpaceRegion *sreg, Kind k) : TypedRegion(sreg, k) {
558    assert(classof(this));
559  }
560
561public:
562  bool isBoundable() const override { return false; }
563
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.
571class FunctionCodeRegion : public CodeTextRegion {
572  friend class MemRegionManager;
573
574  const NamedDecl *FD;
575
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
584public:
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
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
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.
618class BlockCodeRegion : public CodeTextRegion {
619  friend class MemRegionManager;
620
621  const BlockDecl *BD;
622  AnalysisDeclContext *AC;
623  CanQualType locTy;
624
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
637public:
638  QualType getLocationType() const override {
639    return locTy;
640  }
641
642  const BlockDecl *getDecl() const {
643    return BD;
644  }
645
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
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.
663class 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
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
687public:
688  const BlockCodeRegion *getCodeRegion() const { return BC; }
689
690  const BlockDecl *getDecl() const { return BC->getDecl(); }
691
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:
699    explicit referenced_vars_iterator(const MemRegion * const *r,
700                                      const MemRegion * const *originalR)
701        : R(r), OriginalR(originalR) {}
702
703    const VarRegion *getCapturedRegion() const {
704      return cast<VarRegion>(*R);
705    }
706
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
739  static bool classof(const MemRegion* R) {
740    return R->getKind() == BlockDataRegionKind;
741  }
742
743private:
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.
754class SymbolicRegion : public SubRegion {
755  friend class MemRegionManager;
756
757  const SymbolRef sym;
758
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
770public:
771  SymbolRef getSymbol() const { return sym; }
772
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
783  static bool classof(const MemRegion* R) {
784    return R->getKind() == SymbolicRegionKind;
785  }
786};
787
788/// StringRegion - Region associated with a StringLiteral.
789class StringRegion : public TypedValueRegion {
790  friend class MemRegionManager;
791
792  const StringLiteral *Str;
793
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
803public:
804  const StringLiteral *getStringLiteral() const { return Str; }
805
806  QualType getValueType() const override { return Str->getType(); }
807
808  bool isBoundable() const override { return false; }
809
810  void Profile(llvm::FoldingSetNodeID& ID) const override {
811    ProfileRegion(ID, Str, superRegion);
812  }
813
814  void dumpToStream(raw_ostream &os) const override;
815
816  static bool classof(const MemRegion* R) {
817    return R->getKind() == StringRegionKind;
818  }
819};
820
821/// The region associated with an ObjCStringLiteral.
822class ObjCStringRegion : public TypedValueRegion {
823  friend class MemRegionManager;
824
825  const ObjCStringLiteral *Str;
826
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
837public:
838  const ObjCStringLiteral *getObjCStringLiteral() const { return Str; }
839
840  QualType getValueType() const override { return Str->getType(); }
841
842  bool isBoundable() const override { return false; }
843
844  void Profile(llvm::FoldingSetNodeID& ID) const override {
845    ProfileRegion(ID, Str, superRegion);
846  }
847
848  void dumpToStream(raw_ostream &os) const override;
849
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.
858class CompoundLiteralRegion : public TypedValueRegion {
859  friend class MemRegionManager;
860
861  const CompoundLiteralExpr *CL;
862
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
875public:
876  QualType getValueType() const override { return CL->getType(); }
877
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
884  const CompoundLiteralExpr *getLiteralExpr() const { return CL; }
885
886  static bool classof(const MemRegion* R) {
887    return R->getKind() == CompoundLiteralRegionKind;
888  }
889};
890
891class DeclRegion : public TypedValueRegion {
892protected:
893  DeclRegion(const MemRegion *sReg, Kind k) : TypedValueRegion(sReg, k) {
894    assert(classof(this));
895  }
896
897public:
898  virtual const ValueDecl *getDecl() const = 0;
899
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
906class VarRegion : public DeclRegion {
907  friend class MemRegionManager;
908
909protected:
910  // Constructors and protected methods.
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
920public:
921  const VarDecl *getDecl() const override = 0;
922
923  const StackFrameContext *getStackFrame() const;
924
925  QualType getValueType() const override {
926    // FIXME: We can cache this if needed.
927    return getDecl()->getType();
928  }
929
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
936class NonParamVarRegion : public VarRegion {
937  friend class MemRegionManager;
938
939  const VarDecl *VD;
940
941  // Constructors and private methods.
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
955public:
956  void Profile(llvm::FoldingSetNodeID &ID) const override;
957
958  const VarDecl *getDecl() const override { return VD; }
959
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
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.
986class ParamVarRegion : public VarRegion {
987  friend class MemRegionManager;
988
989  const Expr *OriginExpr;
990  unsigned Index;
991
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
1000public:
1001  const Expr *getOriginExpr() const { return OriginExpr; }
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
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.
1022class CXXThisRegion : public TypedValueRegion {
1023  friend class MemRegionManager;
1024
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
1037public:
1038  void Profile(llvm::FoldingSetNodeID &ID) const override;
1039
1040  QualType getValueType() const override {
1041    return QualType(ThisPointerTy, 0);
1042  }
1043
1044  void dumpToStream(raw_ostream &os) const override;
1045
1046  static bool classof(const MemRegion* R) {
1047    return R->getKind() == CXXThisRegionKind;
1048  }
1049
1050private:
1051  const PointerType *ThisPointerTy;
1052};
1053
1054class FieldRegion : public DeclRegion {
1055  friend class MemRegionManager;
1056
1057  const FieldDecl *FD;
1058
1059  FieldRegion(const FieldDecl *fd, const SubRegion *sReg)
1060      : DeclRegion(sReg, FieldRegionKind), FD(fd) {}
1061
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
1069public:
1070  const FieldDecl *getDecl() const override { return FD; }
1071
1072  void Profile(llvm::FoldingSetNodeID &ID) const override;
1073
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
1086  static bool classof(const MemRegion* R) {
1087    return R->getKind() == FieldRegionKind;
1088  }
1089};
1090
1091class 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
1101public:
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
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
1122class RegionRawOffset {
1123  friend class ElementRegion;
1124
1125  const MemRegion *Region;
1126  CharUnits Offset;
1127
1128  RegionRawOffset(const MemRegion* reg, CharUnits offset = CharUnits::Zero())
1129      : Region(reg), Offset(offset) {}
1130
1131public:
1132  // FIXME: Eventually support symbolic offsets.
1133  CharUnits getOffset() const { return Offset; }
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.
1141class ElementRegion : public TypedValueRegion {
1142  friend class MemRegionManager;
1143
1144  QualType ElementType;
1145  NonLoc Index;
1146
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
1160public:
1161  NonLoc getIndex() const { return Index; }
1162
1163  QualType getValueType() const override { return ElementType; }
1164
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
1174  static bool classof(const MemRegion* R) {
1175    return R->getKind() == ElementRegionKind;
1176  }
1177};
1178
1179// C++ temporary object associated with an expression.
1180class CXXTempObjectRegion : public TypedValueRegion {
1181  friend class MemRegionManager;
1182
1183  Expr const *Ex;
1184
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
1195public:
1196  const Expr *getExpr() const { return Ex; }
1197
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
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.
1211class CXXBaseObjectRegion : public TypedValueRegion {
1212  friend class MemRegionManager;
1213
1214  llvm::PointerIntPair<const CXXRecordDecl *, 1, bool> Data;
1215
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
1225public:
1226  const CXXRecordDecl *getDecl() const { return Data.getPointer(); }
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
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.
1249class CXXDerivedObjectRegion : public TypedValueRegion {
1250  friend class MemRegionManager;
1251
1252  const CXXRecordDecl *DerivedD;
1253
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
1267public:
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
1280  static bool classof(const MemRegion *region) {
1281    return region->getKind() == CXXDerivedObjectRegionKind;
1282  }
1283};
1284
1285template<typename RegionTy>
1286const RegionTy* MemRegion::getAs() const {
1287  if (const auto *RT = dyn_cast<RegionTy>(this))
1288    return RT;
1289
1290  return nullptr;
1291}
1292
1293template<typename RegionTy>
1294const RegionTy* MemRegion::castAs() const {
1295  return cast<RegionTy>(this);
1296}
1297
1298//===----------------------------------------------------------------------===//
1299// MemRegionManager - Factory object for creating regions.
1300//===----------------------------------------------------------------------===//
1301
1302class 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
1323public:
1324  MemRegionManager(ASTContext &c, llvm::BumpPtrAllocator &a) : Ctx(c), A(a) {}
1325  ~MemRegionManager();
1326
1327  ASTContext &getContext() { return Ctx; }
1328
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
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
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 *
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
1479private:
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
1507inline 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.
1516class 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
1527public:
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//===----------------------------------------------------------------------===//
1556inline 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