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 
56 using namespace clang;
57 using namespace ento;
58 
59 #define DEBUG_TYPE "MemRegion"
60 
61 //===----------------------------------------------------------------------===//
62 // MemRegion Construction.
63 //===----------------------------------------------------------------------===//
64 
65 template <typename RegionTy, typename SuperTy, typename Arg1Ty>
66 RegionTy* 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 
82 template <typename RegionTy, typename SuperTy, typename Arg1Ty, typename Arg2Ty>
83 RegionTy* 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 
99 template <typename RegionTy, typename SuperTy,
100           typename Arg1Ty, typename Arg2Ty, typename Arg3Ty>
101 RegionTy* 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 
122 MemRegion::~MemRegion() = default;
123 
124 // All regions and their data are BumpPtrAllocated.  No need to call their
125 // destructors.
126 MemRegionManager::~MemRegionManager() = default;
127 
128 //===----------------------------------------------------------------------===//
129 // Basic methods.
130 //===----------------------------------------------------------------------===//
131 
132 bool 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 
145 MemRegionManager* 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 
157 const 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 
166 DefinedOrUnknownSVal 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 
180 DefinedOrUnknownSVal 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 
199 DefinedOrUnknownSVal AllocaRegion::getExtent(SValBuilder &svalBuilder) const {
200   return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this));
201 }
202 
203 DefinedOrUnknownSVal SymbolicRegion::getExtent(SValBuilder &svalBuilder) const {
204   return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this));
205 }
206 
207 DefinedOrUnknownSVal StringRegion::getExtent(SValBuilder &svalBuilder) const {
208   return svalBuilder.makeIntVal(getStringLiteral()->getByteLength()+1,
209                                 svalBuilder.getArrayIndexType());
210 }
211 
212 ObjCIvarRegion::ObjCIvarRegion(const ObjCIvarDecl *ivd, const SubRegion *sReg)
213     : DeclRegion(ivd, sReg, ObjCIvarRegionKind) {}
214 
215 const ObjCIvarDecl *ObjCIvarRegion::getDecl() const {
216   return cast<ObjCIvarDecl>(D);
217 }
218 
219 QualType ObjCIvarRegion::getValueType() const {
220   return getDecl()->getType();
221 }
222 
223 QualType CXXBaseObjectRegion::getValueType() const {
224   return QualType(getDecl()->getTypeForDecl(), 0);
225 }
226 
227 QualType CXXDerivedObjectRegion::getValueType() const {
228   return QualType(getDecl()->getTypeForDecl(), 0);
229 }
230 
231 //===----------------------------------------------------------------------===//
232 // FoldingSet profiling.
233 //===----------------------------------------------------------------------===//
234 
235 void MemSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const {
236   ID.AddInteger(static_cast<unsigned>(getKind()));
237 }
238 
239 void StackSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const {
240   ID.AddInteger(static_cast<unsigned>(getKind()));
241   ID.AddPointer(getStackFrame());
242 }
243 
244 void StaticGlobalSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const {
245   ID.AddInteger(static_cast<unsigned>(getKind()));
246   ID.AddPointer(getCodeRegion());
247 }
248 
249 void 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 
257 void 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 
265 void 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 
274 void AllocaRegion::Profile(llvm::FoldingSetNodeID& ID) const {
275   ProfileRegion(ID, Ex, Cnt, superRegion);
276 }
277 
278 void CompoundLiteralRegion::Profile(llvm::FoldingSetNodeID& ID) const {
279   CompoundLiteralRegion::ProfileRegion(ID, CL, superRegion);
280 }
281 
282 void 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 
290 void 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 
298 void CXXThisRegion::Profile(llvm::FoldingSetNodeID &ID) const {
299   CXXThisRegion::ProfileRegion(ID, ThisPointerTy, superRegion);
300 }
301 
302 void ObjCIvarRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
303                                    const ObjCIvarDecl *ivd,
304                                    const MemRegion* superRegion) {
305   DeclRegion::ProfileRegion(ID, ivd, superRegion, ObjCIvarRegionKind);
306 }
307 
308 void 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 
315 void DeclRegion::Profile(llvm::FoldingSetNodeID& ID) const {
316   DeclRegion::ProfileRegion(ID, D, superRegion, getKind());
317 }
318 
319 void VarRegion::Profile(llvm::FoldingSetNodeID &ID) const {
320   VarRegion::ProfileRegion(ID, getDecl(), superRegion);
321 }
322 
323 void 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 
330 void SymbolicRegion::Profile(llvm::FoldingSetNodeID& ID) const {
331   SymbolicRegion::ProfileRegion(ID, sym, getSuperRegion());
332 }
333 
334 void 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 
343 void ElementRegion::Profile(llvm::FoldingSetNodeID& ID) const {
344   ElementRegion::ProfileRegion(ID, ElementType, Index, superRegion);
345 }
346 
347 void FunctionCodeRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
348                                        const NamedDecl *FD,
349                                        const MemRegion*) {
350   ID.AddInteger(MemRegion::FunctionCodeRegionKind);
351   ID.AddPointer(FD);
352 }
353 
354 void FunctionCodeRegion::Profile(llvm::FoldingSetNodeID& ID) const {
355   FunctionCodeRegion::ProfileRegion(ID, FD, superRegion);
356 }
357 
358 void 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 
366 void BlockCodeRegion::Profile(llvm::FoldingSetNodeID& ID) const {
367   BlockCodeRegion::ProfileRegion(ID, BD, locTy, AC, superRegion);
368 }
369 
370 void 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 
382 void BlockDataRegion::Profile(llvm::FoldingSetNodeID& ID) const {
383   BlockDataRegion::ProfileRegion(ID, BC, LC, BlockCount, getSuperRegion());
384 }
385 
386 void CXXTempObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
387                                         Expr const *Ex,
388                                         const MemRegion *sReg) {
389   ID.AddPointer(Ex);
390   ID.AddPointer(sReg);
391 }
392 
393 void CXXTempObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const {
394   ProfileRegion(ID, Ex, getSuperRegion());
395 }
396 
397 void 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 
406 void CXXBaseObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const {
407   ProfileRegion(ID, getDecl(), isVirtual(), superRegion);
408 }
409 
410 void CXXDerivedObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
411                                            const CXXRecordDecl *RD,
412                                            const MemRegion *SReg) {
413   ID.AddPointer(RD);
414   ID.AddPointer(SReg);
415 }
416 
417 void CXXDerivedObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const {
418   ProfileRegion(ID, getDecl(), superRegion);
419 }
420 
421 //===----------------------------------------------------------------------===//
422 // Region anchors.
423 //===----------------------------------------------------------------------===//
424 
425 void GlobalsSpaceRegion::anchor() {}
426 
427 void NonStaticGlobalSpaceRegion::anchor() {}
428 
429 void StackSpaceRegion::anchor() {}
430 
431 void TypedRegion::anchor() {}
432 
433 void TypedValueRegion::anchor() {}
434 
435 void CodeTextRegion::anchor() {}
436 
437 void SubRegion::anchor() {}
438 
439 //===----------------------------------------------------------------------===//
440 // Region pretty-printing.
441 //===----------------------------------------------------------------------===//
442 
443 LLVM_DUMP_METHOD void MemRegion::dump() const {
444   dumpToStream(llvm::errs());
445 }
446 
447 std::string MemRegion::getString() const {
448   std::string s;
449   llvm::raw_string_ostream os(s);
450   dumpToStream(os);
451   return os.str();
452 }
453 
454 void MemRegion::dumpToStream(raw_ostream &os) const {
455   os << "<Unknown Region>";
456 }
457 
458 void AllocaRegion::dumpToStream(raw_ostream &os) const {
459   os << "alloca{S" << Ex->getID(getContext()) << ',' << Cnt << '}';
460 }
461 
462 void FunctionCodeRegion::dumpToStream(raw_ostream &os) const {
463   os << "code{" << getDecl()->getDeclName().getAsString() << '}';
464 }
465 
466 void BlockCodeRegion::dumpToStream(raw_ostream &os) const {
467   os << "block_code{" << static_cast<const void *>(this) << '}';
468 }
469 
470 void 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 
481 void CompoundLiteralRegion::dumpToStream(raw_ostream &os) const {
482   // FIXME: More elaborate pretty-printing.
483   os << "{ S" << CL->getID(getContext()) <<  " }";
484 }
485 
486 void CXXTempObjectRegion::dumpToStream(raw_ostream &os) const {
487   os << "temp_object{" << getValueType().getAsString() << ", "
488      << "S" << Ex->getID(getContext()) << '}';
489 }
490 
491 void CXXBaseObjectRegion::dumpToStream(raw_ostream &os) const {
492   os << "Base{" << superRegion << ',' << getDecl()->getName() << '}';
493 }
494 
495 void CXXDerivedObjectRegion::dumpToStream(raw_ostream &os) const {
496   os << "Derived{" << superRegion << ',' << getDecl()->getName() << '}';
497 }
498 
499 void CXXThisRegion::dumpToStream(raw_ostream &os) const {
500   os << "this";
501 }
502 
503 void ElementRegion::dumpToStream(raw_ostream &os) const {
504   os << "Element{" << superRegion << ','
505      << Index << ',' << getElementType().getAsString() << '}';
506 }
507 
508 void FieldRegion::dumpToStream(raw_ostream &os) const {
509   os << superRegion << "." << *getDecl();
510 }
511 
512 void ObjCIvarRegion::dumpToStream(raw_ostream &os) const {
513   os << "Ivar{" << superRegion << ',' << *getDecl() << '}';
514 }
515 
516 void StringRegion::dumpToStream(raw_ostream &os) const {
517   assert(Str != nullptr && "Expecting non-null StringLiteral");
518   Str->printPretty(os, nullptr, PrintingPolicy(getContext().getLangOpts()));
519 }
520 
521 void ObjCStringRegion::dumpToStream(raw_ostream &os) const {
522   assert(Str != nullptr && "Expecting non-null ObjCStringLiteral");
523   Str->printPretty(os, nullptr, PrintingPolicy(getContext().getLangOpts()));
524 }
525 
526 void SymbolicRegion::dumpToStream(raw_ostream &os) const {
527   if (isa<HeapSpaceRegion>(getSuperRegion()))
528     os << "Heap";
529   os << "SymRegion{" << sym << '}';
530 }
531 
532 void 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 
540 LLVM_DUMP_METHOD void RegionRawOffset::dump() const {
541   dumpToStream(llvm::errs());
542 }
543 
544 void RegionRawOffset::dumpToStream(raw_ostream &os) const {
545   os << "raw_offset{" << getRegion() << ',' << getOffset().getQuantity() << '}';
546 }
547 
548 void CodeSpaceRegion::dumpToStream(raw_ostream &os) const {
549   os << "CodeSpaceRegion";
550 }
551 
552 void StaticGlobalSpaceRegion::dumpToStream(raw_ostream &os) const {
553   os << "StaticGlobalsMemSpace{" << CR << '}';
554 }
555 
556 void GlobalInternalSpaceRegion::dumpToStream(raw_ostream &os) const {
557   os << "GlobalInternalSpaceRegion";
558 }
559 
560 void GlobalSystemSpaceRegion::dumpToStream(raw_ostream &os) const {
561   os << "GlobalSystemSpaceRegion";
562 }
563 
564 void GlobalImmutableSpaceRegion::dumpToStream(raw_ostream &os) const {
565   os << "GlobalImmutableSpaceRegion";
566 }
567 
568 void HeapSpaceRegion::dumpToStream(raw_ostream &os) const {
569   os << "HeapSpaceRegion";
570 }
571 
572 void UnknownSpaceRegion::dumpToStream(raw_ostream &os) const {
573   os << "UnknownSpaceRegion";
574 }
575 
576 void StackArgumentsSpaceRegion::dumpToStream(raw_ostream &os) const {
577   os << "StackArgumentsSpaceRegion";
578 }
579 
580 void StackLocalsSpaceRegion::dumpToStream(raw_ostream &os) const {
581   os << "StackLocalsSpaceRegion";
582 }
583 
584 bool MemRegion::canPrintPretty() const {
585   return canPrintPrettyAsExpr();
586 }
587 
588 bool MemRegion::canPrintPrettyAsExpr() const {
589   return false;
590 }
591 
592 void MemRegion::printPretty(raw_ostream &os) const {
593   assert(canPrintPretty() && "This region cannot be printed pretty.");
594   os << "'";
595   printPrettyAsExpr(os);
596   os << "'";
597 }
598 
599 void MemRegion::printPrettyAsExpr(raw_ostream &) const {
600   llvm_unreachable("This region cannot be printed pretty.");
601 }
602 
603 bool VarRegion::canPrintPrettyAsExpr() const {
604   return true;
605 }
606 
607 void VarRegion::printPrettyAsExpr(raw_ostream &os) const {
608   os << getDecl()->getName();
609 }
610 
611 bool ObjCIvarRegion::canPrintPrettyAsExpr() const {
612   return true;
613 }
614 
615 void ObjCIvarRegion::printPrettyAsExpr(raw_ostream &os) const {
616   os << getDecl()->getName();
617 }
618 
619 bool FieldRegion::canPrintPretty() const {
620   return true;
621 }
622 
623 bool FieldRegion::canPrintPrettyAsExpr() const {
624   return superRegion->canPrintPrettyAsExpr();
625 }
626 
627 void FieldRegion::printPrettyAsExpr(raw_ostream &os) const {
628   assert(canPrintPrettyAsExpr());
629   superRegion->printPrettyAsExpr(os);
630   os << "." << getDecl()->getName();
631 }
632 
633 void 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 
643 bool CXXBaseObjectRegion::canPrintPrettyAsExpr() const {
644   return superRegion->canPrintPrettyAsExpr();
645 }
646 
647 void CXXBaseObjectRegion::printPrettyAsExpr(raw_ostream &os) const {
648   superRegion->printPrettyAsExpr(os);
649 }
650 
651 bool CXXDerivedObjectRegion::canPrintPrettyAsExpr() const {
652   return superRegion->canPrintPrettyAsExpr();
653 }
654 
655 void CXXDerivedObjectRegion::printPrettyAsExpr(raw_ostream &os) const {
656   superRegion->printPrettyAsExpr(os);
657 }
658 
659 std::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 
698 SourceRange 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 
720 template <typename REG>
721 const 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 
730 template <typename REG, typename ARG>
731 const 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 
740 const StackLocalsSpaceRegion*
741 MemRegionManager::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 
753 const StackArgumentsSpaceRegion *
754 MemRegionManager::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 
766 const 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 
788 const HeapSpaceRegion *MemRegionManager::getHeapRegion() {
789   return LazyAllocate(heap);
790 }
791 
792 const UnknownSpaceRegion *MemRegionManager::getUnknownRegion() {
793   return LazyAllocate(unknown);
794 }
795 
796 const CodeSpaceRegion *MemRegionManager::getCodeRegion() {
797   return LazyAllocate(code);
798 }
799 
800 //===----------------------------------------------------------------------===//
801 // Constructing regions.
802 //===----------------------------------------------------------------------===//
803 
804 const StringRegion *MemRegionManager::getStringRegion(const StringLiteral *Str){
805   return getSubRegion<StringRegion>(
806       Str, cast<GlobalInternalSpaceRegion>(getGlobalsRegion()));
807 }
808 
809 const ObjCStringRegion *
810 MemRegionManager::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.
818 static llvm::PointerUnion<const StackFrameContext *, const VarRegion *>
819 getStackOrCaptureRegionForDeclContext(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 
845 const 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 
932 const VarRegion *MemRegionManager::getVarRegion(const VarDecl *D,
933                                                 const MemRegion *superR) {
934   D = D->getCanonicalDecl();
935   return getSubRegion<VarRegion>(D, superR);
936 }
937 
938 const BlockDataRegion *
939 MemRegionManager::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 
966 const CXXTempObjectRegion *
967 MemRegionManager::getCXXStaticTempObjectRegion(const Expr *Ex) {
968   return getSubRegion<CXXTempObjectRegion>(
969       Ex, getGlobalsRegion(MemRegion::GlobalInternalSpaceRegionKind, nullptr));
970 }
971 
972 const CompoundLiteralRegion*
973 MemRegionManager::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 
988 const ElementRegion*
989 MemRegionManager::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 
1010 const FunctionCodeRegion *
1011 MemRegionManager::getFunctionCodeRegion(const NamedDecl *FD) {
1012   // To think: should we canonicalize the declaration here?
1013   return getSubRegion<FunctionCodeRegion>(FD, getCodeRegion());
1014 }
1015 
1016 const BlockCodeRegion *
1017 MemRegionManager::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.
1023 const SymbolicRegion *MemRegionManager::getSymbolicRegion(SymbolRef sym) {
1024   return getSubRegion<SymbolicRegion>(sym, getUnknownRegion());
1025 }
1026 
1027 const SymbolicRegion *MemRegionManager::getSymbolicHeapRegion(SymbolRef Sym) {
1028   return getSubRegion<SymbolicRegion>(Sym, getHeapRegion());
1029 }
1030 
1031 const FieldRegion*
1032 MemRegionManager::getFieldRegion(const FieldDecl *d,
1033                                  const SubRegion* superRegion){
1034   return getSubRegion<FieldRegion>(d, superRegion);
1035 }
1036 
1037 const ObjCIvarRegion*
1038 MemRegionManager::getObjCIvarRegion(const ObjCIvarDecl *d,
1039                                     const SubRegion* superRegion) {
1040   return getSubRegion<ObjCIvarRegion>(d, superRegion);
1041 }
1042 
1043 const CXXTempObjectRegion*
1044 MemRegionManager::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.
1053 static 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 
1073 const CXXBaseObjectRegion *
1074 MemRegionManager::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 
1093 const CXXDerivedObjectRegion *
1094 MemRegionManager::getCXXDerivedObjectRegion(const CXXRecordDecl *RD,
1095                                             const SubRegion *Super) {
1096   return getSubRegion<CXXDerivedObjectRegion>(RD, Super);
1097 }
1098 
1099 const CXXThisRegion*
1100 MemRegionManager::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 
1120 const AllocaRegion*
1121 MemRegionManager::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 
1128 const 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 
1140 bool MemRegion::hasStackStorage() const {
1141   return isa<StackSpaceRegion>(getMemorySpace());
1142 }
1143 
1144 bool MemRegion::hasStackNonParametersStorage() const {
1145   return isa<StackLocalsSpaceRegion>(getMemorySpace());
1146 }
1147 
1148 bool MemRegion::hasStackParametersStorage() const {
1149   return isa<StackArgumentsSpaceRegion>(getMemorySpace());
1150 }
1151 
1152 bool 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.
1160 const 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.
1181 const 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 
1188 bool MemRegion::isSubRegionOf(const MemRegion *) const {
1189   return false;
1190 }
1191 
1192 //===----------------------------------------------------------------------===//
1193 // View handling.
1194 //===----------------------------------------------------------------------===//
1195 
1196 const 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 
1219 const 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 
1230 RegionRawOffset 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
1280 static 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 
1294 static 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 
1467 RegionOffset MemRegion::getAsOffset() const {
1468   if (!cachedOffset)
1469     cachedOffset = calculateOffset(this);
1470   return *cachedOffset;
1471 }
1472 
1473 //===----------------------------------------------------------------------===//
1474 // BlockDataRegion
1475 //===----------------------------------------------------------------------===//
1476 
1477 std::pair<const VarRegion *, const VarRegion *>
1478 BlockDataRegion::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 
1500 void 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 
1539 BlockDataRegion::referenced_vars_iterator
1540 BlockDataRegion::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 
1555 BlockDataRegion::referenced_vars_iterator
1556 BlockDataRegion::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 
1571 const 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 
1585 void RegionAndSymbolInvalidationTraits::setTrait(SymbolRef Sym,
1586                                                  InvalidationKinds IK) {
1587   SymTraitsMap[Sym] |= IK;
1588 }
1589 
1590 void 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 
1599 bool 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 
1608 bool 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