1//===--- Pointer.cpp - Types for the constexpr VM ---------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "Pointer.h"
10#include "Boolean.h"
11#include "Char.h"
12#include "Context.h"
13#include "Floating.h"
14#include "Function.h"
15#include "InitMap.h"
16#include "Integral.h"
17#include "InterpBlock.h"
18#include "MemberPointer.h"
19#include "PrimType.h"
20#include "Record.h"
21#include "clang/AST/Expr.h"
22#include "clang/AST/ExprCXX.h"
23#include "clang/AST/RecordLayout.h"
24
25using namespace clang;
26using namespace clang::interp;
27
28Pointer::Pointer(Block *Pointee)
29 : Pointer(Pointee, Pointee->getDescriptor()->getMetadataSize(),
30 Pointee->getDescriptor()->getMetadataSize()) {}
31
32Pointer::Pointer(Block *Pointee, uint64_t BaseAndOffset)
33 : Pointer(Pointee, BaseAndOffset, BaseAndOffset) {}
34
35Pointer::Pointer(Block *Pointee, unsigned Base, uint64_t Offset)
36 : Offset(Offset), StorageKind(Storage::Block) {
37 assert(Pointee);
38 assert(Base % alignof(void *) == 0 && "wrong base");
39 assert(Base >= Pointee->getDescriptor()->getMetadataSize());
40
41 BS = {.Pointee: Pointee, .Base: Base, .Prev: nullptr, .Next: nullptr};
42 Pointee->addPointer(P: this);
43}
44
45Pointer::Pointer(const Pointer &P)
46 : Offset(P.Offset), StorageKind(P.StorageKind) {
47 switch (StorageKind) {
48 case Storage::Int:
49 Int = P.Int;
50 break;
51 case Storage::Block:
52 BS = P.BS;
53 if (BS.Pointee)
54 BS.Pointee->addPointer(P: this);
55 break;
56 case Storage::Fn:
57 Fn = P.Fn;
58 break;
59 case Storage::Typeid:
60 Typeid = P.Typeid;
61 break;
62 }
63}
64
65Pointer::Pointer(Pointer &&P) : Offset(P.Offset), StorageKind(P.StorageKind) {
66 switch (StorageKind) {
67 case Storage::Int:
68 Int = P.Int;
69 break;
70 case Storage::Block:
71 BS = P.BS;
72 if (BS.Pointee)
73 BS.Pointee->replacePointer(Old: &P, New: this);
74 break;
75 case Storage::Fn:
76 Fn = P.Fn;
77 break;
78 case Storage::Typeid:
79 Typeid = P.Typeid;
80 break;
81 }
82}
83
84Pointer::~Pointer() {
85 if (!isBlockPointer())
86 return;
87
88 if (Block *Pointee = BS.Pointee) {
89 Pointee->removePointer(P: this);
90 BS.Pointee = nullptr;
91 Pointee->cleanup();
92 }
93}
94
95Pointer &Pointer::operator=(const Pointer &P) {
96 // If the current storage type is Block, we need to remove
97 // this pointer from the block.
98 if (isBlockPointer()) {
99 if (P.isBlockPointer() && this->block() == P.block()) {
100 Offset = P.Offset;
101 BS.Base = P.BS.Base;
102 return *this;
103 }
104
105 if (Block *Pointee = BS.Pointee) {
106 Pointee->removePointer(P: this);
107 BS.Pointee = nullptr;
108 Pointee->cleanup();
109 }
110 }
111
112 StorageKind = P.StorageKind;
113 Offset = P.Offset;
114
115 switch (StorageKind) {
116 case Storage::Int:
117 Int = P.Int;
118 break;
119 case Storage::Block:
120 BS = P.BS;
121
122 if (BS.Pointee)
123 BS.Pointee->addPointer(P: this);
124 break;
125 case Storage::Fn:
126 Fn = P.Fn;
127 break;
128 case Storage::Typeid:
129 Typeid = P.Typeid;
130 }
131 return *this;
132}
133
134Pointer &Pointer::operator=(Pointer &&P) {
135 // If the current storage type is Block, we need to remove
136 // this pointer from the block.
137 if (isBlockPointer()) {
138 if (P.isBlockPointer() && this->block() == P.block()) {
139 Offset = P.Offset;
140 BS.Base = P.BS.Base;
141 return *this;
142 }
143
144 if (Block *Pointee = BS.Pointee) {
145 Pointee->removePointer(P: this);
146 BS.Pointee = nullptr;
147 Pointee->cleanup();
148 }
149 }
150
151 StorageKind = P.StorageKind;
152 Offset = P.Offset;
153
154 switch (StorageKind) {
155 case Storage::Int:
156 Int = P.Int;
157 break;
158 case Storage::Block:
159 BS = P.BS;
160
161 if (BS.Pointee)
162 BS.Pointee->addPointer(P: this);
163 break;
164 case Storage::Fn:
165 Fn = P.Fn;
166 break;
167 case Storage::Typeid:
168 Typeid = P.Typeid;
169 }
170 return *this;
171}
172
173APValue Pointer::toAPValue(const ASTContext &ASTCtx) const {
174 llvm::SmallVector<APValue::LValuePathEntry, 5> Path;
175
176 if (isZero())
177 return APValue(APValue::LValueBase(), CharUnits::Zero(), Path,
178 /*IsOnePastEnd=*/false, /*IsNullPtr=*/true);
179 if (isIntegralPointer())
180 return APValue(static_cast<const Expr *>(nullptr),
181 CharUnits::fromQuantity(Quantity: asIntPointer().Value + this->Offset),
182 Path,
183 /*IsOnePastEnd=*/false, /*IsNullPtr=*/false);
184 if (isFunctionPointer()) {
185 const FunctionPointer &FP = asFunctionPointer();
186 if (const FunctionDecl *FD = FP.Func->getDecl())
187 return APValue(FD, CharUnits::fromQuantity(Quantity: Offset), {},
188 /*OnePastTheEnd=*/false, /*IsNull=*/false);
189 return APValue(FP.Func->getExpr(), CharUnits::fromQuantity(Quantity: Offset), {},
190 /*OnePastTheEnd=*/false, /*IsNull=*/false);
191 }
192
193 if (isTypeidPointer()) {
194 TypeInfoLValue TypeInfo(Typeid.TypePtr);
195 return APValue(APValue::LValueBase::getTypeInfo(
196 LV: TypeInfo, TypeInfo: QualType(Typeid.TypeInfoType, 0)),
197 CharUnits::Zero(), {},
198 /*OnePastTheEnd=*/false, /*IsNull=*/false);
199 }
200
201 // Build the lvalue base from the block.
202 const Descriptor *Desc = getDeclDesc();
203 APValue::LValueBase Base;
204 if (const auto *VD = Desc->asValueDecl())
205 Base = VD;
206 else if (const auto *E = Desc->asExpr()) {
207 if (block()->isDynamic()) {
208 QualType AllocatedType = getDeclPtr().getFieldDesc()->getDataType(Ctx: ASTCtx);
209 DynamicAllocLValue DA(*block()->DynAllocId);
210 Base = APValue::LValueBase::getDynamicAlloc(LV: DA, Type: AllocatedType);
211 } else {
212 Base = E;
213 }
214 } else
215 llvm_unreachable("Invalid allocation type");
216
217 CharUnits Offset = CharUnits::Zero();
218
219 auto getFieldOffset = [&](const FieldDecl *FD) -> CharUnits {
220 // This shouldn't happen, but if it does, don't crash inside
221 // getASTRecordLayout.
222 if (FD->getParent()->isInvalidDecl())
223 return CharUnits::Zero();
224 const ASTRecordLayout &Layout = ASTCtx.getASTRecordLayout(D: FD->getParent());
225 unsigned FieldIndex = FD->getFieldIndex();
226 return ASTCtx.toCharUnitsFromBits(BitSize: Layout.getFieldOffset(FieldNo: FieldIndex));
227 };
228
229 // Build the path into the object.
230 bool OnePastEnd = isOnePastEnd() && !isZeroSizeArray();
231
232 PtrView Ptr = view();
233 while (Ptr.isField() || Ptr.isArrayElement()) {
234
235 if (Ptr.isArrayRoot()) {
236 // An array root may still be an array element itself.
237 if (Ptr.isArrayElement()) {
238 Ptr = Ptr.expand();
239 const Descriptor *Desc = Ptr.getFieldDesc();
240 unsigned Index = Ptr.getIndex();
241 QualType ElemType = Desc->getElemQualType();
242 Offset += (Index * ASTCtx.getTypeSizeInChars(T: ElemType));
243 if (Ptr.getArray().getFieldDesc()->IsArray)
244 Path.push_back(Elt: APValue::LValuePathEntry::ArrayIndex(Index));
245 Ptr = Ptr.getArray();
246 } else {
247 const Descriptor *Desc = Ptr.getFieldDesc();
248 const auto *Dcl = Desc->asDecl();
249 Path.push_back(Elt: APValue::LValuePathEntry({Dcl, /*IsVirtual=*/false}));
250
251 if (const auto *FD = dyn_cast_if_present<FieldDecl>(Val: Dcl))
252 Offset += getFieldOffset(FD);
253
254 Ptr = Ptr.getBase();
255 }
256 } else if (Ptr.isArrayElement()) {
257 Ptr = Ptr.expand();
258 const Descriptor *Desc = Ptr.getFieldDesc();
259 unsigned Index;
260 if (Ptr.isOnePastEnd()) {
261 Index = Ptr.getArray().getNumElems();
262 OnePastEnd = false;
263 } else
264 Index = Ptr.getIndex();
265
266 QualType ElemType = Desc->getElemQualType();
267 if (const auto *RD = ElemType->getAsRecordDecl();
268 RD && !RD->getDefinition()) {
269 // Ignore this for the offset.
270 } else {
271 Offset += (Index * ASTCtx.getTypeSizeInChars(T: ElemType));
272 }
273 if (Ptr.getArray().getFieldDesc()->IsArray)
274 Path.push_back(Elt: APValue::LValuePathEntry::ArrayIndex(Index));
275 Ptr = Ptr.getArray();
276 } else {
277 const Descriptor *Desc = Ptr.getFieldDesc();
278
279 // Create a path entry for the field.
280 if (const auto *BaseOrMember = Desc->asDecl()) {
281 bool IsVirtual = false;
282 if (const auto *FD = dyn_cast<FieldDecl>(Val: BaseOrMember)) {
283 Ptr = Ptr.getBase();
284 Offset += getFieldOffset(FD);
285 } else if (const auto *RD = dyn_cast<CXXRecordDecl>(Val: BaseOrMember)) {
286 IsVirtual = Ptr.isVirtualBaseClass();
287 Ptr = Ptr.getBase();
288 const Record *BaseRecord = Ptr.getRecord();
289
290 const ASTRecordLayout &Layout = ASTCtx.getASTRecordLayout(
291 D: cast<CXXRecordDecl>(Val: BaseRecord->getDecl()));
292 if (IsVirtual)
293 Offset += Layout.getVBaseClassOffset(VBase: RD);
294 else
295 Offset += Layout.getBaseClassOffset(Base: RD);
296
297 } else {
298 Ptr = Ptr.getBase();
299 }
300 Path.push_back(Elt: APValue::LValuePathEntry({BaseOrMember, IsVirtual}));
301 continue;
302 }
303 llvm_unreachable("Invalid field type");
304 }
305 }
306
307 // We assemble the LValuePath starting from the innermost pointer to the
308 // outermost one. SO in a.b.c, the first element in Path will refer to
309 // the field 'c', while later code expects it to refer to 'a'.
310 // Just invert the order of the elements.
311 std::reverse(first: Path.begin(), last: Path.end());
312
313 auto Result = APValue(Base, Offset, Path, OnePastEnd);
314 Result.setConstexprUnknown(isConstexprUnknown());
315 return Result;
316}
317
318void Pointer::print(llvm::raw_ostream &OS) const {
319 switch (StorageKind) {
320 case Storage::Block: {
321 const Block *B = BS.Pointee;
322 OS << "(Block) " << B << " {";
323
324 if (isRoot())
325 OS << "rootptr(" << BS.Base << "), ";
326 else
327 OS << BS.Base << ", ";
328
329 if (isElementPastEnd())
330 OS << "pastend, ";
331 else
332 OS << Offset << ", ";
333
334 if (B)
335 OS << B->getSize();
336 else
337 OS << "nullptr";
338 OS << "}";
339 } break;
340 case Storage::Int:
341 OS << "(Int) {" << Int.Value << " + " << Offset << ", " << Int.Ty << "}";
342 break;
343 case Storage::Fn:
344 OS << "(Fn) { " << Fn.Func << " + " << Offset << " }";
345 break;
346 case Storage::Typeid:
347 OS << "(Typeid) { " << (const void *)asTypeidPointer().TypePtr << ", "
348 << (const void *)asTypeidPointer().TypeInfoType << " + " << Offset
349 << "}";
350 }
351}
352
353/// Compute an offset that can be used to compare the pointer to another one
354/// with the same base. To get accurate results, we basically _have to_ compute
355/// the lvalue offset using the ASTRecordLayout.
356///
357/// This function will fail if we're trying to get the type size of a forward
358/// declaration.
359///
360// FIXME: We're still mixing values from the record layout with our internal
361// offsets, which will inevitably lead to cryptic errors.
362std::optional<size_t>
363Pointer::computeOffsetForComparison(const ASTContext &ASTCtx) const {
364 switch (StorageKind) {
365 case Storage::Int:
366 return Int.Value + Offset;
367 case Storage::Block:
368 // See below.
369 break;
370 case Storage::Fn:
371 return getIntegerRepresentation();
372 case Storage::Typeid:
373 return reinterpret_cast<uintptr_t>(asTypeidPointer().TypePtr) + Offset;
374 }
375
376 auto getTypeSize = [&](QualType T) -> std::optional<size_t> {
377 if (const RecordType *RT = T->getAs<RecordType>()) {
378 // We cannot get the type size of a forward declaration.
379 if (!RT->getDecl()->getDefinition())
380 return std::nullopt;
381 }
382 return ASTCtx.getTypeSizeInChars(T).getQuantity();
383 };
384
385 size_t Result = 0;
386 PtrView P = view();
387 while (true) {
388 if (P.isVirtualBaseClass()) {
389 Result += getInlineDesc()->Offset;
390 P = P.getBase();
391 continue;
392 }
393
394 if (P.isBaseClass()) {
395 Result += P.getInlineDesc()->Offset - sizeof(InlineDescriptor);
396 P = P.getBase();
397 continue;
398 }
399 if (P.isArrayElement()) {
400 P = P.expand();
401 Result += (P.getIndex() * P.elemSize());
402 P = P.getArray();
403 continue;
404 }
405
406 if (P.isRoot()) {
407 if (P.isOnePastEnd()) {
408 if (auto Size = getTypeSize(P.getDeclDesc()->getType()))
409 Result += *Size;
410 else
411 return std::nullopt;
412 }
413 break;
414 }
415
416 assert(P.getField());
417 const Record *R = P.getBase().getRecord();
418 assert(R);
419
420 const ASTRecordLayout &Layout = ASTCtx.getASTRecordLayout(D: R->getDecl());
421 Result += ASTCtx
422 .toCharUnitsFromBits(
423 BitSize: Layout.getFieldOffset(FieldNo: P.getField()->getFieldIndex()))
424 .getQuantity();
425
426 if (P.isOnePastEnd()) {
427 if (auto Size = getTypeSize(P.getField()->getType()))
428 Result += *Size;
429 else
430 return std::nullopt;
431 }
432
433 P = P.getBase();
434 if (P.isRoot())
435 break;
436 }
437 return Result;
438}
439
440std::optional<size_t>
441Pointer::computeLayoutOffset(const ASTContext &ASTCtx) const {
442 switch (StorageKind) {
443 case Storage::Int:
444 return Int.Value + Offset;
445 case Storage::Block:
446 // See below.
447 break;
448 case Storage::Fn:
449 return getIntegerRepresentation();
450 case Storage::Typeid:
451 return reinterpret_cast<uintptr_t>(asTypeidPointer().TypePtr) + Offset;
452 }
453
454 auto getTypeSize = [&](QualType T) -> std::optional<size_t> {
455 if (const RecordType *RT = T->getAs<RecordType>()) {
456 // We cannot get the type size of a forward declaration.
457 if (!RT->getDecl()->getDefinition())
458 return std::nullopt;
459 }
460 return ASTCtx.getTypeSizeInChars(T).getQuantity();
461 };
462
463 auto getRecordDecl = [&](PtrView P) -> const CXXRecordDecl * {
464 if (const Record *R = P.getRecord())
465 return cast<CXXRecordDecl>(Val: R->getDecl());
466 return cast<CXXRecordDecl>(Val: P.getFieldDesc()->asDecl());
467 };
468
469 auto getRecordSize = [&](const RecordDecl *RD) -> unsigned {
470 CanQualType RecordTy = ASTCtx.getCanonicalTagType(TD: RD);
471 return ASTCtx.getTypeSizeInChars(T: RecordTy).getQuantity();
472 };
473
474 size_t Result = 0;
475 PtrView P = view();
476 while (true) {
477 if (P.isBaseClass()) {
478 const ASTRecordLayout &Layout =
479 ASTCtx.getASTRecordLayout(D: getRecordDecl(P.getBase()));
480 const CXXRecordDecl *RD = getRecordDecl(P);
481 if (P.isVirtualBaseClass())
482 Result += Layout.getVBaseClassOffset(VBase: RD).getQuantity();
483 else
484 Result += Layout.getBaseClassOffset(Base: RD).getQuantity();
485
486 if (P.isOnePastEnd())
487 Result += getRecordSize(RD);
488
489 P = P.getBase();
490 continue;
491 }
492
493 if (P.isArrayElement()) {
494 P = P.expand();
495 assert(P.getFieldDesc()->isArray());
496 if (std::optional<size_t> ElemSize =
497 getTypeSize(P.getFieldDesc()->getElemQualType()))
498 Result += *ElemSize * P.getIndex();
499 else
500 return std::nullopt;
501
502 P = P.getArray();
503 continue;
504 }
505
506 if (P.isRoot()) {
507 if (P.isPastEnd() || P.isOnePastEnd()) {
508 if (std::optional<size_t> Size =
509 getTypeSize(P.getDeclDesc()->getType()))
510 Result += *Size * P.getIndex();
511 else
512 return std::nullopt;
513 }
514 break;
515 }
516
517 assert(P.getField());
518 const FieldDecl *F = P.getField();
519 const ASTRecordLayout &Layout = ASTCtx.getASTRecordLayout(D: F->getParent());
520 Result +=
521 ASTCtx.toCharUnitsFromBits(BitSize: Layout.getFieldOffset(FieldNo: F->getFieldIndex()))
522 .getQuantity();
523
524 if (P.isPastEnd() || P.isOnePastEnd()) {
525 if (std::optional<size_t> Size = getTypeSize(F->getType()))
526 Result += *Size * P.getIndex();
527 else
528 return std::nullopt;
529 }
530
531 P = P.getBase();
532 if (P.isRoot())
533 break;
534 }
535 return Result;
536}
537
538std::string Pointer::toDiagnosticString(const ASTContext &Ctx) const {
539 if (isZero())
540 return "nullptr";
541
542 if (isIntegralPointer())
543 return (Twine("&(") + Twine(asIntPointer().Value + Offset) + ")").str();
544
545 QualType Ty = getType();
546 if (Ty->isLValueReferenceType())
547 Ty = Ty->getPointeeType();
548 return toAPValue(ASTCtx: Ctx).getAsString(Ctx, Ty);
549}
550
551bool Pointer::isInitialized() const {
552 if (!isBlockPointer())
553 return true;
554
555 if (isRoot() && BS.Base == sizeof(GlobalInlineDescriptor) &&
556 Offset == BS.Base) {
557 const auto &GD = block()->getBlockDesc<GlobalInlineDescriptor>();
558 return GD.InitState == GlobalInitState::Initialized;
559 }
560
561 assert(BS.Pointee && "Cannot check if null pointer was initialized");
562 const Descriptor *Desc = getFieldDesc();
563 assert(Desc);
564 if (Desc->isPrimitiveArray())
565 return isElementInitialized(Index: getIndex());
566
567 if (asBlockPointer().Base == 0)
568 return true;
569 // Field has its bit in an inline descriptor.
570 return getInlineDesc()->IsInitialized;
571}
572
573bool PtrView::isElementInitialized(unsigned Index) const {
574 const Descriptor *Desc = getFieldDesc();
575 assert(Desc);
576
577 if (Pointee->isStatic() && Base == 0)
578 return true;
579
580 if (isRoot() && Base == sizeof(GlobalInlineDescriptor) && Offset == Base) {
581 const auto &GD = Pointee->getBlockDesc<GlobalInlineDescriptor>();
582 return GD.InitState == GlobalInitState::Initialized;
583 }
584
585 if (Desc->isPrimitiveArray()) {
586 InitMapPtr IM = getInitMap();
587
588 if (IM.allInitialized())
589 return true;
590
591 if (!IM.hasInitMap())
592 return false;
593 return IM->isElementInitialized(I: Index);
594 }
595 return isInitialized();
596}
597
598bool Pointer::isElementAlive(unsigned Index) const {
599 assert(getFieldDesc()->isPrimitiveArray());
600
601 InitMapPtr &IM = getInitMap();
602 if (!IM.hasInitMap())
603 return true;
604
605 if (IM.allInitialized())
606 return true;
607
608 return IM->isElementAlive(I: Index);
609}
610
611Lifetime PtrView::getLifetime() const {
612 if (Base < sizeof(InlineDescriptor))
613 return Lifetime::Started;
614
615 if (inArray() && !isArrayRoot()) {
616 InitMapPtr &IM = getInitMap();
617
618 if (!IM.hasInitMap()) {
619 if (IM.allInitialized())
620 return Lifetime::Started;
621 return getArray().getLifetime();
622 }
623
624 return IM->isElementAlive(I: getIndex()) ? Lifetime::Started : Lifetime::Ended;
625 }
626
627 return getInlineDesc()->LifeState;
628}
629
630void PtrView::setLifeState(Lifetime L) const {
631 if (Base < sizeof(InlineDescriptor))
632 return;
633
634 if (inArray() && !isArrayRoot()) {
635 assert(L == Lifetime::Started || L == Lifetime::Ended);
636 const Descriptor *Desc = getFieldDesc();
637 InitMapPtr &IM = getInitMap();
638 if (!IM.hasInitMap())
639 IM.setInitMap(new InitMap(Desc->getNumElems(), IM.allInitialized()));
640
641 if (L == Lifetime::Ended)
642 IM->endElementLifetime(I: getIndex());
643 else if (L == Lifetime::Started)
644 IM->startElementLifetime(I: getIndex());
645 assert(isArrayRoot() || (this->getLifetime() == L));
646 return;
647 }
648
649 getInlineDesc()->LifeState = L;
650}
651
652void PtrView::initialize() const {
653 if (isRoot() && Base == sizeof(GlobalInlineDescriptor) && Offset == Base) {
654 auto &GD = Pointee->getBlockDesc<GlobalInlineDescriptor>();
655 GD.InitState = GlobalInitState::Initialized;
656 return;
657 }
658
659 const Descriptor *Desc = getFieldDesc();
660 assert(Desc);
661 if (Desc->isPrimitiveArray()) {
662 if (Desc->getNumElems() != 0)
663 initializeElement(Index: getIndex());
664 return;
665 }
666
667 // Field has its bit in an inline descriptor.
668 assert(Base != 0 && "Only composite fields can be initialised");
669 getInlineDesc()->IsInitialized = true;
670 getInlineDesc()->LifeState = Lifetime::Started;
671}
672
673void PtrView::initializeElement(unsigned Index) const {
674 // Primitive global arrays don't have an initmap.
675 if (Pointee->isStatic() && Base == 0)
676 return;
677
678 assert(Index < getFieldDesc()->getNumElems());
679
680 InitMapPtr &IM = getInitMap();
681 if (IM.allInitialized())
682 return;
683
684 if (!IM.hasInitMap()) {
685 const Descriptor *Desc = getFieldDesc();
686 IM.setInitMap(new InitMap(Desc->getNumElems()));
687 }
688 assert(IM.hasInitMap());
689
690 if (IM->initializeElement(I: Index))
691 IM.noteAllInitialized();
692}
693
694void Pointer::initializeAllElements() const {
695 assert(getFieldDesc()->isPrimitiveArray());
696 assert(isArrayRoot());
697
698 getInitMap().noteAllInitialized();
699}
700
701bool PtrView::allElementsInitialized() const {
702 assert(getFieldDesc()->isPrimitiveArray());
703 assert(isArrayRoot());
704
705 if (Pointee->isStatic() && Base == 0)
706 return true;
707
708 if (isRoot() && Base == sizeof(GlobalInlineDescriptor) && Offset == Base) {
709 const auto &GD = Pointee->getBlockDesc<GlobalInlineDescriptor>();
710 return GD.InitState == GlobalInitState::Initialized;
711 }
712
713 InitMapPtr IM = getInitMap();
714 return IM.allInitialized();
715}
716
717bool Pointer::allElementsAlive() const {
718 assert(getFieldDesc()->isPrimitiveArray());
719 assert(isArrayRoot());
720
721 if (isStatic() && BS.Base == 0)
722 return true;
723
724 if (isRoot() && BS.Base == sizeof(GlobalInlineDescriptor) &&
725 Offset == BS.Base) {
726 const auto &GD = block()->getBlockDesc<GlobalInlineDescriptor>();
727 return GD.InitState == GlobalInitState::Initialized;
728 }
729
730 InitMapPtr &IM = getInitMap();
731 return IM.allInitialized() || (IM.hasInitMap() && IM->allElementsAlive());
732}
733
734void PtrView::activate() const {
735 // Field has its bit in an inline descriptor.
736 assert(Base != 0 && "Only composite fields can be activated");
737
738 if (isRoot() && Base == sizeof(GlobalInlineDescriptor))
739 return;
740 if (!getInlineDesc()->InUnion)
741 return;
742
743 std::function<void(PtrView P)> activate;
744 activate = [&activate](PtrView P) -> void {
745 P.getInlineDesc()->IsActive = true;
746 P.startLifetime();
747 if (const Record *R = P.getRecord(); R && !R->isUnion()) {
748 for (const Record::Field &F : R->fields()) {
749 PtrView FieldPtr = P.atField(Offset: F.Offset);
750 if (!FieldPtr.getInlineDesc()->IsActive)
751 activate(FieldPtr);
752 }
753 // FIXME: Bases?
754 }
755 };
756
757 std::function<void(PtrView &)> deactivate;
758 deactivate = [&deactivate](PtrView &P) -> void {
759 P.getInlineDesc()->IsActive = false;
760
761 if (const Record *R = P.getRecord()) {
762 for (const Record::Field &F : R->fields()) {
763 PtrView FieldPtr = P.atField(Offset: F.Offset);
764 if (FieldPtr.getInlineDesc()->IsActive)
765 deactivate(FieldPtr);
766 }
767 // FIXME: Bases?
768 }
769 };
770
771 PtrView B = *this;
772 // Primitive array elements can't be activated individually, so
773 // look at the array root instead.
774 if (B.getFieldDesc()->isPrimitiveArray() && B.isArrayElement())
775 B = B.getArray();
776
777 while (!B.isRoot() && B.inUnion()) {
778 activate(B);
779
780 // When walking up the pointer chain, deactivate
781 // all union child pointers that aren't on our path.
782 PtrView Cur = B;
783 B = B.getBase();
784 if (const Record *BR = B.getRecord(); BR && BR->isUnion()) {
785 for (const Record::Field &F : BR->fields()) {
786 PtrView FieldPtr = B.atField(Offset: F.Offset);
787 if (FieldPtr != Cur)
788 deactivate(FieldPtr);
789 }
790 }
791 }
792}
793
794bool Pointer::hasSameBase(const Pointer &A, const Pointer &B) {
795 // Two null pointers always have the same base.
796 if (A.isZero() && B.isZero())
797 return true;
798
799 if (A.isIntegralPointer() && B.isIntegralPointer())
800 return true;
801 if (A.isFunctionPointer() && B.isFunctionPointer())
802 return true;
803 if (A.isTypeidPointer() && B.isTypeidPointer())
804 return A.asTypeidPointer().TypePtr == B.asTypeidPointer().TypePtr;
805
806 if (A.StorageKind != B.StorageKind)
807 return false;
808
809 return A.asBlockPointer().Pointee == B.asBlockPointer().Pointee;
810}
811
812bool Pointer::pointToSameBlock(const Pointer &A, const Pointer &B) {
813 if (!A.isBlockPointer() || !B.isBlockPointer())
814 return false;
815 return A.block() == B.block();
816}
817
818bool Pointer::elemsOfSameArray(const Pointer &A, const Pointer &B) {
819 assert(hasSameBase(A, B));
820 assert(A.isBlockPointer());
821 assert(B.isBlockPointer());
822
823 if (A.BS.Base == B.BS.Base)
824 return true;
825
826 if (A.isBaseClass() || B.isBaseClass())
827 return false;
828
829 if (A.getField() || B.getField())
830 return false;
831
832 auto closestArray = [](const Pointer &P) -> PtrView {
833 if (P.isArrayRoot())
834 return P.view();
835
836 PtrView V = P.view();
837 if (V.isArrayElement() || V.isOnePastEnd())
838 V = V.expand().getArray();
839
840 if (P.isRoot())
841 return P.view();
842
843 while (!V.isRoot() && !V.getFieldDesc()->IsArray) {
844 if (V.isArrayElement()) {
845 V = V.expand().getArray();
846 break;
847 }
848 V = V.getBase();
849 }
850 return V;
851 };
852
853 if (closestArray(A) != closestArray(B))
854 return false;
855
856 return true;
857}
858
859bool Pointer::pointsToLiteral() const {
860 if (isZero() || !isBlockPointer())
861 return false;
862
863 if (block()->isDynamic())
864 return false;
865
866 const Expr *E = block()->getDescriptor()->asExpr();
867 return E && !isa<MaterializeTemporaryExpr, StringLiteral>(Val: E);
868}
869
870bool Pointer::pointsToStringLiteral() const {
871 if (isZero() || !isBlockPointer())
872 return false;
873
874 if (block()->isDynamic())
875 return false;
876
877 const Expr *E = block()->getDescriptor()->asExpr();
878 return isa_and_nonnull<StringLiteral>(Val: E);
879}
880
881bool Pointer::pointsToLabel() const {
882 if (isZero() || !isBlockPointer())
883 return false;
884
885 if (const Expr *E = BS.Pointee->getDescriptor()->asExpr())
886 return isa<AddrLabelExpr>(Val: E);
887 return false;
888}
889
890std::optional<std::pair<PtrView, PtrView>>
891Pointer::computeSplitPoint(const Pointer &A, const Pointer &B) {
892 if (!A.isBlockPointer() || !B.isBlockPointer())
893 return std::nullopt;
894
895 if (A.asBlockPointer().Pointee != B.asBlockPointer().Pointee)
896 return std::nullopt;
897 if (A.isRoot() && B.isRoot())
898 return std::nullopt;
899
900 if (A == B)
901 return std::make_pair(x: A.view(), y: B.view());
902
903 auto getBase = [](PtrView P) -> PtrView {
904 if (P.isArrayElement())
905 return P.expand().getArray();
906 return P.getBase();
907 };
908
909 PtrView IterA = A.view();
910 PtrView IterB = B.view();
911 PtrView CurA = IterA;
912 PtrView CurB = IterB;
913 for (;;) {
914 if (IterA.Base > IterB.Base) {
915 CurA = IterA;
916 IterA = getBase(IterA);
917 } else {
918 CurB = IterB;
919 IterB = getBase(IterB);
920 }
921
922 if (IterA == IterB) {
923 // If the Iter is an array, CurA and CurB are both elements of the same
924 // array. That is fine, so return nullopt.
925 if (IterA.getFieldDesc()->isArray())
926 return std::nullopt;
927 return std::make_pair(x&: CurA, y&: CurB);
928 }
929
930 if (IterA.isRoot() && IterB.isRoot())
931 return std::nullopt;
932 }
933
934 llvm_unreachable("The loop above should've returned.");
935}
936
937std::optional<APValue> Pointer::toRValue(const Context &Ctx,
938 QualType ResultType) const {
939 const ASTContext &ASTCtx = Ctx.getASTContext();
940 assert(!ResultType.isNull());
941 // Method to recursively traverse composites.
942 std::function<bool(QualType, PtrView, APValue &)> Composite;
943 Composite = [&Composite, &Ctx, &ASTCtx](QualType Ty, PtrView Ptr,
944 APValue &R) {
945 if (const auto *AT = Ty->getAs<AtomicType>())
946 Ty = AT->getValueType();
947
948 // Invalid pointers.
949 if (Ptr.isDummy() || !Ptr.isLive() || Ptr.isPastEnd())
950 return false;
951
952 // Primitives should never end up here.
953 assert(!Ctx.canClassify(Ty));
954 const Descriptor *FieldDesc = Ptr.getFieldDesc();
955 assert(FieldDesc);
956
957 if (const auto *RT = Ty->getAsCanonical<RecordType>()) {
958 if (!FieldDesc->isRecord())
959 return false;
960 const auto *Record = Ptr.getRecord();
961 assert(Record && "Missing record descriptor");
962
963 bool Ok = true;
964 if (RT->getDecl()->isUnion()) {
965 const FieldDecl *ActiveField = nullptr;
966 APValue Value;
967 for (const auto &F : Record->fields()) {
968 PtrView FP = Ptr.atField(Offset: F.Offset);
969 if (FP.isActive()) {
970 const Descriptor *Desc = F.Desc;
971 if (Desc->isPrimitive()) {
972 TYPE_SWITCH(Desc->getPrimType(),
973 Value = FP.deref<T>().toAPValue(ASTCtx));
974 } else {
975 QualType FieldTy = F.Decl->getType();
976 Ok &= Composite(FieldTy, FP, Value);
977 }
978 ActiveField = FP.getFieldDesc()->asFieldDecl();
979 break;
980 }
981 }
982 R = APValue(ActiveField, Value);
983 } else {
984 unsigned NF = Record->getNumFields();
985 unsigned NB = Record->getNumBases();
986 unsigned NV = Ptr.isBaseClass() ? 0 : Record->getNumVirtualBases();
987
988 R = APValue(APValue::UninitStruct(), NB, NF, NV);
989
990 for (unsigned I = 0; I != NF; ++I) {
991 const Record::Field *FD = Record->getField(I);
992 const Descriptor *Desc = FD->Desc;
993 PtrView FP = Ptr.atField(Offset: FD->Offset);
994 APValue &Value = R.getStructField(i: I);
995 if (Desc->isPrimitive()) {
996 TYPE_SWITCH(Desc->getPrimType(),
997 Value = FP.deref<T>().toAPValue(ASTCtx));
998 } else {
999 QualType FieldTy = FD->Decl->getType();
1000 Ok &= Composite(FieldTy, FP, Value);
1001 }
1002 }
1003
1004 for (unsigned I = 0; I != NB; ++I) {
1005 const Record::Base *BD = Record->getBase(I);
1006 QualType BaseTy = Ctx.getASTContext().getCanonicalTagType(TD: BD->Decl);
1007 PtrView BP = Ptr.atField(Offset: BD->Offset);
1008 Ok &= Composite(BaseTy, BP, R.getStructBase(i: I));
1009 }
1010
1011 for (unsigned I = 0; I != NV; ++I) {
1012 const Record::Base *VD = Record->getVirtualBase(I);
1013 assert(VD);
1014 QualType VirtBaseTy =
1015 Ctx.getASTContext().getCanonicalTagType(TD: VD->Decl);
1016 PtrView VP = Ptr.atField(Offset: VD->Offset);
1017 Ok &= Composite(VirtBaseTy, VP, R.getStructVirtualBase(i: I));
1018 }
1019 }
1020 return Ok;
1021 }
1022
1023 if (Ty->isIncompleteArrayType()) {
1024 R = APValue(APValue::UninitArray(), 0, 0);
1025 return true;
1026 }
1027
1028 if (const auto *AT = Ty->getAsArrayTypeUnsafe()) {
1029 if (!FieldDesc->isArray())
1030 return false;
1031 const size_t NumElems = Ptr.getNumElems();
1032 QualType ElemTy = AT->getElementType();
1033 R = APValue(APValue::UninitArray{}, NumElems, NumElems);
1034
1035 bool Ok = true;
1036 OptPrimType ElemT = Ctx.classify(T: ElemTy);
1037 for (unsigned I = 0; I != NumElems; ++I) {
1038 APValue &Slot = R.getArrayInitializedElt(I);
1039 if (ElemT) {
1040 TYPE_SWITCH(*ElemT, Slot = Ptr.elem<T>(I).toAPValue(ASTCtx));
1041 } else {
1042 Ok &= Composite(ElemTy, Ptr.atIndex(Idx: I).narrow(), Slot);
1043 }
1044 }
1045 return Ok;
1046 }
1047
1048 // Complex types.
1049 if (Ty->isAnyComplexType()) {
1050 // Can happen via C casts.
1051 if (!FieldDesc->getType()->isAnyComplexType())
1052 return false;
1053
1054 PrimType ElemT = FieldDesc->getPrimType();
1055 if (isIntegerOrBoolType(T: ElemT)) {
1056 INT_TYPE_SWITCH(ElemT, {
1057 auto V1 = Ptr.elem<T>(0);
1058 auto V2 = Ptr.elem<T>(1);
1059 R = APValue(V1.toAPSInt(), V2.toAPSInt());
1060 return true;
1061 });
1062 } else if (ElemT == PT_Float) {
1063 R = APValue(Ptr.elem<Floating>(I: 0).getAPFloat(),
1064 Ptr.elem<Floating>(I: 1).getAPFloat());
1065 return true;
1066 }
1067 return false;
1068 }
1069
1070 // Vector types.
1071 if (const auto *VT = Ty->getAs<VectorType>()) {
1072 if (!FieldDesc->isPrimitiveArray())
1073 return false;
1074
1075 PrimType ElemT = FieldDesc->getPrimType();
1076 SmallVector<APValue> Values;
1077 Values.reserve(N: VT->getNumElements());
1078 for (unsigned I = 0; I != VT->getNumElements(); ++I) {
1079 TYPE_SWITCH(ElemT,
1080 { Values.push_back(Ptr.elem<T>(I).toAPValue(ASTCtx)); });
1081 }
1082
1083 assert(Values.size() == VT->getNumElements());
1084 R = APValue(Values.data(), Values.size());
1085 return true;
1086 }
1087
1088 // Constant Matrix types.
1089 if (const auto *MT = Ty->getAs<ConstantMatrixType>()) {
1090 if (!FieldDesc->isPrimitiveArray())
1091 return false;
1092 PrimType ElemT = FieldDesc->getPrimType();
1093 unsigned NumElems = MT->getNumElementsFlattened();
1094
1095 SmallVector<APValue> Values;
1096 Values.reserve(N: NumElems);
1097 for (unsigned I = 0; I != NumElems; ++I) {
1098 TYPE_SWITCH(ElemT,
1099 { Values.push_back(Ptr.elem<T>(I).toAPValue(ASTCtx)); });
1100 }
1101
1102 R = APValue(Values.data(), MT->getNumRows(), MT->getNumColumns());
1103 return true;
1104 }
1105
1106 llvm_unreachable("invalid value to return");
1107 };
1108
1109 // Can't return functions as rvalues.
1110 if (ResultType->isFunctionType())
1111 return std::nullopt;
1112
1113 // Invalid to read from.
1114 if (isDummy() || !isLive() || isPastEnd() ||
1115 (isOnePastEnd() && !isZeroSizeArray()))
1116 return std::nullopt;
1117
1118 // We can return these as rvalues, but we can't deref() them.
1119 if (isZero() || isIntegralPointer())
1120 return toAPValue(ASTCtx);
1121
1122 // Just load primitive types.
1123 if (OptPrimType T = Ctx.classify(T: ResultType)) {
1124 if (!canDeref(T: *T))
1125 return std::nullopt;
1126 TYPE_SWITCH(*T, return this->deref<T>().toAPValue(ASTCtx));
1127 }
1128
1129 // Return the composite type.
1130 APValue Result;
1131 if (!Composite(ResultType, view(), Result))
1132 return std::nullopt;
1133 return Result;
1134}
1135
1136const VarDecl *Pointer::getRootVarDecl() const {
1137 if (isBlockPointer())
1138 return getDeclDesc()->asVarDecl();
1139 return nullptr;
1140}
1141
1142std::optional<IntPointer> IntPointer::atOffset(const interp::Context &Ctx,
1143 unsigned Offset) const {
1144 QualType CurType = getPointeeType();
1145 if (CurType.isNull() || !CurType->isRecordType())
1146 return std::nullopt;
1147
1148 const Record *R = Ctx.getRecord(D: CurType->getAsRecordDecl());
1149 if (!R)
1150 return *this;
1151
1152 const Record::Field *F = nullptr;
1153 for (auto &It : R->fields()) {
1154 if (It.Offset == Offset) {
1155 F = &It;
1156 break;
1157 }
1158 }
1159 if (!F)
1160 return *this;
1161
1162 const FieldDecl *FD = F->Decl;
1163 if (FD->getParent()->isInvalidDecl())
1164 return std::nullopt;
1165
1166 const ASTContext &ASTCtx = Ctx.getASTContext();
1167 const ASTRecordLayout &Layout = ASTCtx.getASTRecordLayout(D: FD->getParent());
1168 unsigned FieldIndex = FD->getFieldIndex();
1169 uint64_t FieldOffset =
1170 ASTCtx.toCharUnitsFromBits(BitSize: Layout.getFieldOffset(FieldNo: FieldIndex))
1171 .getQuantity();
1172
1173 return IntPointer{.Ty: FD->getType().getTypePtr(), .Value: this->Value + FieldOffset};
1174}
1175
1176IntPointer IntPointer::baseCast(const interp::Context &Ctx,
1177 unsigned BaseOffset) const {
1178 if (!Ty)
1179 return *this;
1180
1181 QualType CurType = getPointeeType();
1182 if (CurType.isNull() || !CurType->isRecordType())
1183 return *this;
1184
1185 const Record *R = Ctx.getRecord(D: CurType->getAsRecordDecl());
1186 const Descriptor *BaseDesc = nullptr;
1187
1188 // This iterates over bases and checks for the proper offset. That's
1189 // potentially slow but this case really shouldn't happen a lot.
1190 for (const Record::Base &B : R->bases()) {
1191 if (B.Offset == BaseOffset) {
1192 BaseDesc = B.Desc;
1193 break;
1194 }
1195 }
1196 assert(BaseDesc);
1197
1198 // Adjust the offset value based on the information from the record layout.
1199 const ASTContext &ASTCtx = Ctx.getASTContext();
1200 const ASTRecordLayout &Layout = ASTCtx.getASTRecordLayout(D: R->getDecl());
1201 CharUnits BaseLayoutOffset =
1202 Layout.getBaseClassOffset(Base: cast<CXXRecordDecl>(Val: BaseDesc->asDecl()));
1203
1204 const RecordDecl *RD = BaseDesc->ElemRecord->getDecl();
1205 QualType T = RD->getASTContext().getTagType(Keyword: ElaboratedTypeKeyword::None,
1206 Qualifier: std::nullopt, TD: RD, OwnsTag: false);
1207 return {.Ty: T.getTypePtr(), .Value: Value + BaseLayoutOffset.getQuantity()};
1208}
1209