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