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