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