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