1//===--- Pointer.h - 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// Defines the classes responsible for pointer tracking.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_CLANG_AST_INTERP_POINTER_H
14#define LLVM_CLANG_AST_INTERP_POINTER_H
15
16#include "Descriptor.h"
17#include "InterpBlock.h"
18#include "clang/AST/ComparisonCategories.h"
19#include "clang/AST/Decl.h"
20#include "clang/AST/DeclCXX.h"
21#include "clang/AST/Expr.h"
22#include "llvm/Support/raw_ostream.h"
23
24namespace clang {
25namespace interp {
26class Block;
27class DeadBlock;
28class Pointer;
29class Context;
30template <unsigned A, bool B> class Integral;
31enum PrimType : unsigned;
32
33class Pointer;
34inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Pointer &P);
35
36struct BlockPointer {
37 /// The block the pointer is pointing to.
38 Block *Pointee;
39 /// Start of the current subfield.
40 unsigned Base;
41};
42
43struct IntPointer {
44 const Descriptor *Desc;
45 uint64_t Value;
46};
47
48enum class Storage { Block, Int };
49
50/// A pointer to a memory block, live or dead.
51///
52/// This object can be allocated into interpreter stack frames. If pointing to
53/// a live block, it is a link in the chain of pointers pointing to the block.
54///
55/// In the simplest form, a Pointer has a Block* (the pointee) and both Base
56/// and Offset are 0, which means it will point to raw data.
57///
58/// The Base field is used to access metadata about the data. For primitive
59/// arrays, the Base is followed by an InitMap. In a variety of cases, the
60/// Base is preceded by an InlineDescriptor, which is used to track the
61/// initialization state, among other things.
62///
63/// The Offset field is used to access the actual data. In other words, the
64/// data the pointer decribes can be found at
65/// Pointee->rawData() + Pointer.Offset.
66///
67///
68/// Pointee Offset
69/// │ │
70/// │ │
71/// ▼ ▼
72/// ┌───────┬────────────┬─────────┬────────────────────────────┐
73/// │ Block │ InlineDesc │ InitMap │ Actual Data │
74/// └───────┴────────────┴─────────┴────────────────────────────┘
75/// ▲
76/// │
77/// │
78/// Base
79class Pointer {
80private:
81 static constexpr unsigned PastEndMark = ~0u;
82 static constexpr unsigned RootPtrMark = ~0u;
83
84public:
85 Pointer() {
86 StorageKind = Storage::Int;
87 PointeeStorage.Int.Value = 0;
88 PointeeStorage.Int.Desc = nullptr;
89 }
90 Pointer(Block *B);
91 Pointer(Block *B, uint64_t BaseAndOffset);
92 Pointer(const Pointer &P);
93 Pointer(Pointer &&P);
94 Pointer(uint64_t Address, const Descriptor *Desc, uint64_t Offset = 0)
95 : Offset(Offset), StorageKind(Storage::Int) {
96 PointeeStorage.Int.Value = Address;
97 PointeeStorage.Int.Desc = Desc;
98 }
99 ~Pointer();
100
101 void operator=(const Pointer &P);
102 void operator=(Pointer &&P);
103
104 /// Equality operators are just for tests.
105 bool operator==(const Pointer &P) const {
106 if (P.StorageKind != StorageKind)
107 return false;
108 if (isIntegralPointer())
109 return P.asIntPointer().Value == asIntPointer().Value &&
110 Offset == P.Offset;
111
112 assert(isBlockPointer());
113 return P.asBlockPointer().Pointee == asBlockPointer().Pointee &&
114 P.asBlockPointer().Base == asBlockPointer().Base &&
115 Offset == P.Offset;
116 }
117
118 bool operator!=(const Pointer &P) const { return !(P == *this); }
119
120 /// Converts the pointer to an APValue.
121 APValue toAPValue(const ASTContext &ASTCtx) const;
122
123 /// Converts the pointer to a string usable in diagnostics.
124 std::string toDiagnosticString(const ASTContext &Ctx) const;
125
126 uint64_t getIntegerRepresentation() const {
127 if (isIntegralPointer())
128 return asIntPointer().Value + (Offset * elemSize());
129 return reinterpret_cast<uint64_t>(asBlockPointer().Pointee) + Offset;
130 }
131
132 /// Converts the pointer to an APValue that is an rvalue.
133 std::optional<APValue> toRValue(const Context &Ctx,
134 QualType ResultType) const;
135
136 /// Offsets a pointer inside an array.
137 [[nodiscard]] Pointer atIndex(uint64_t Idx) const {
138 if (isIntegralPointer())
139 return Pointer(asIntPointer().Value, asIntPointer().Desc, Idx);
140
141 if (asBlockPointer().Base == RootPtrMark)
142 return Pointer(asBlockPointer().Pointee, RootPtrMark,
143 getDeclDesc()->getSize());
144 uint64_t Off = Idx * elemSize();
145 if (getFieldDesc()->ElemDesc)
146 Off += sizeof(InlineDescriptor);
147 else
148 Off += sizeof(InitMapPtr);
149 return Pointer(asBlockPointer().Pointee, asBlockPointer().Base,
150 asBlockPointer().Base + Off);
151 }
152
153 /// Creates a pointer to a field.
154 [[nodiscard]] Pointer atField(unsigned Off) const {
155 unsigned Field = Offset + Off;
156 if (isIntegralPointer())
157 return Pointer(asIntPointer().Value + Field, asIntPointer().Desc);
158 return Pointer(asBlockPointer().Pointee, Field, Field);
159 }
160
161 /// Subtract the given offset from the current Base and Offset
162 /// of the pointer.
163 [[nodiscard]] Pointer atFieldSub(unsigned Off) const {
164 assert(Offset >= Off);
165 unsigned O = Offset - Off;
166 return Pointer(asBlockPointer().Pointee, O, O);
167 }
168
169 /// Restricts the scope of an array element pointer.
170 [[nodiscard]] Pointer narrow() const {
171 if (!isBlockPointer())
172 return *this;
173 assert(isBlockPointer());
174 // Null pointers cannot be narrowed.
175 if (isZero() || isUnknownSizeArray())
176 return *this;
177
178 // Pointer to an array of base types - enter block.
179 if (asBlockPointer().Base == RootPtrMark)
180 return Pointer(asBlockPointer().Pointee, sizeof(InlineDescriptor),
181 Offset == 0 ? Offset : PastEndMark);
182
183 // Pointer is one past end - magic offset marks that.
184 if (isOnePastEnd())
185 return Pointer(asBlockPointer().Pointee, asBlockPointer().Base,
186 PastEndMark);
187
188 // Primitive arrays are a bit special since they do not have inline
189 // descriptors. If Offset != Base, then the pointer already points to
190 // an element and there is nothing to do. Otherwise, the pointer is
191 // adjusted to the first element of the array.
192 if (inPrimitiveArray()) {
193 if (Offset != asBlockPointer().Base)
194 return *this;
195 return Pointer(asBlockPointer().Pointee, asBlockPointer().Base,
196 Offset + sizeof(InitMapPtr));
197 }
198
199 // Pointer is to a field or array element - enter it.
200 if (Offset != asBlockPointer().Base)
201 return Pointer(asBlockPointer().Pointee, Offset, Offset);
202
203 // Enter the first element of an array.
204 if (!getFieldDesc()->isArray())
205 return *this;
206
207 const unsigned NewBase = asBlockPointer().Base + sizeof(InlineDescriptor);
208 return Pointer(asBlockPointer().Pointee, NewBase, NewBase);
209 }
210
211 /// Expands a pointer to the containing array, undoing narrowing.
212 [[nodiscard]] Pointer expand() const {
213 assert(isBlockPointer());
214 Block *Pointee = asBlockPointer().Pointee;
215
216 if (isElementPastEnd()) {
217 // Revert to an outer one-past-end pointer.
218 unsigned Adjust;
219 if (inPrimitiveArray())
220 Adjust = sizeof(InitMapPtr);
221 else
222 Adjust = sizeof(InlineDescriptor);
223 return Pointer(Pointee, asBlockPointer().Base,
224 asBlockPointer().Base + getSize() + Adjust);
225 }
226
227 // Do not step out of array elements.
228 if (asBlockPointer().Base != Offset)
229 return *this;
230
231 // If at base, point to an array of base types.
232 if (isRoot())
233 return Pointer(Pointee, RootPtrMark, 0);
234
235 // Step into the containing array, if inside one.
236 unsigned Next = asBlockPointer().Base - getInlineDesc()->Offset;
237 const Descriptor *Desc =
238 (Next == Pointee->getDescriptor()->getMetadataSize())
239 ? getDeclDesc()
240 : getDescriptor(Offset: Next)->Desc;
241 if (!Desc->IsArray)
242 return *this;
243 return Pointer(Pointee, Next, Offset);
244 }
245
246 /// Checks if the pointer is null.
247 bool isZero() const {
248 if (isBlockPointer())
249 return asBlockPointer().Pointee == nullptr;
250 assert(isIntegralPointer());
251 return asIntPointer().Value == 0 && Offset == 0;
252 }
253 /// Checks if the pointer is live.
254 bool isLive() const {
255 if (isIntegralPointer())
256 return true;
257 return asBlockPointer().Pointee && !asBlockPointer().Pointee->IsDead;
258 }
259 /// Checks if the item is a field in an object.
260 bool isField() const {
261 if (isIntegralPointer())
262 return false;
263
264 return !isRoot() && getFieldDesc()->asDecl();
265 }
266
267 /// Accessor for information about the declaration site.
268 const Descriptor *getDeclDesc() const {
269 if (isIntegralPointer())
270 return asIntPointer().Desc;
271
272 assert(isBlockPointer());
273 assert(asBlockPointer().Pointee);
274 return asBlockPointer().Pointee->Desc;
275 }
276 SourceLocation getDeclLoc() const { return getDeclDesc()->getLocation(); }
277
278 /// Returns the expression or declaration the pointer has been created for.
279 DeclTy getSource() const {
280 if (isBlockPointer())
281 return getDeclDesc()->getSource();
282
283 assert(isIntegralPointer());
284 return asIntPointer().Desc ? asIntPointer().Desc->getSource() : DeclTy();
285 }
286
287 /// Returns a pointer to the object of which this pointer is a field.
288 [[nodiscard]] Pointer getBase() const {
289 if (asBlockPointer().Base == RootPtrMark) {
290 assert(Offset == PastEndMark && "cannot get base of a block");
291 return Pointer(asBlockPointer().Pointee, asBlockPointer().Base, 0);
292 }
293 unsigned NewBase = asBlockPointer().Base - getInlineDesc()->Offset;
294 return Pointer(asBlockPointer().Pointee, NewBase, NewBase);
295 }
296 /// Returns the parent array.
297 [[nodiscard]] Pointer getArray() const {
298 if (asBlockPointer().Base == RootPtrMark) {
299 assert(Offset != 0 && Offset != PastEndMark && "not an array element");
300 return Pointer(asBlockPointer().Pointee, asBlockPointer().Base, 0);
301 }
302 assert(Offset != asBlockPointer().Base && "not an array element");
303 return Pointer(asBlockPointer().Pointee, asBlockPointer().Base,
304 asBlockPointer().Base);
305 }
306
307 /// Accessors for information about the innermost field.
308 const Descriptor *getFieldDesc() const {
309 if (isIntegralPointer())
310 return asIntPointer().Desc;
311
312 if (isRoot())
313 return getDeclDesc();
314 return getInlineDesc()->Desc;
315 }
316
317 /// Returns the type of the innermost field.
318 QualType getType() const {
319 if (inPrimitiveArray() && Offset != asBlockPointer().Base) {
320 // Unfortunately, complex and vector types are not array types in clang,
321 // but they are for us.
322 if (const auto *AT = getFieldDesc()->getType()->getAsArrayTypeUnsafe())
323 return AT->getElementType();
324 if (const auto *CT = getFieldDesc()->getType()->getAs<ComplexType>())
325 return CT->getElementType();
326 if (const auto *CT = getFieldDesc()->getType()->getAs<VectorType>())
327 return CT->getElementType();
328 }
329 return getFieldDesc()->getType();
330 }
331
332 [[nodiscard]] Pointer getDeclPtr() const {
333 return Pointer(asBlockPointer().Pointee);
334 }
335
336 /// Returns the element size of the innermost field.
337 size_t elemSize() const {
338 if (isIntegralPointer()) {
339 if (!asIntPointer().Desc)
340 return 1;
341 return asIntPointer().Desc->getElemSize();
342 }
343
344 if (asBlockPointer().Base == RootPtrMark)
345 return getDeclDesc()->getSize();
346 return getFieldDesc()->getElemSize();
347 }
348 /// Returns the total size of the innermost field.
349 size_t getSize() const {
350 assert(isBlockPointer());
351 return getFieldDesc()->getSize();
352 }
353
354 /// Returns the offset into an array.
355 unsigned getOffset() const {
356 assert(Offset != PastEndMark && "invalid offset");
357 if (asBlockPointer().Base == RootPtrMark)
358 return Offset;
359
360 unsigned Adjust = 0;
361 if (Offset != asBlockPointer().Base) {
362 if (getFieldDesc()->ElemDesc)
363 Adjust = sizeof(InlineDescriptor);
364 else
365 Adjust = sizeof(InitMapPtr);
366 }
367 return Offset - asBlockPointer().Base - Adjust;
368 }
369
370 /// Whether this array refers to an array, but not
371 /// to the first element.
372 bool isArrayRoot() const {
373 return inArray() && Offset == asBlockPointer().Base;
374 }
375
376 /// Checks if the innermost field is an array.
377 bool inArray() const {
378 if (isBlockPointer())
379 return getFieldDesc()->IsArray;
380 return false;
381 }
382 /// Checks if the structure is a primitive array.
383 bool inPrimitiveArray() const {
384 if (isBlockPointer())
385 return getFieldDesc()->isPrimitiveArray();
386 return false;
387 }
388 /// Checks if the structure is an array of unknown size.
389 bool isUnknownSizeArray() const {
390 if (!isBlockPointer())
391 return false;
392 return getFieldDesc()->isUnknownSizeArray();
393 }
394 /// Checks if the pointer points to an array.
395 bool isArrayElement() const {
396 if (isBlockPointer())
397 return inArray() && asBlockPointer().Base != Offset;
398 return false;
399 }
400 /// Pointer points directly to a block.
401 bool isRoot() const {
402 if (isZero() || isIntegralPointer())
403 return true;
404 return (asBlockPointer().Base ==
405 asBlockPointer().Pointee->getDescriptor()->getMetadataSize() ||
406 asBlockPointer().Base == 0);
407 }
408 /// If this pointer has an InlineDescriptor we can use to initialize.
409 bool canBeInitialized() const {
410 if (!isBlockPointer())
411 return false;
412
413 return asBlockPointer().Pointee && asBlockPointer().Base > 0;
414 }
415
416 [[nodiscard]] const BlockPointer &asBlockPointer() const {
417 assert(isBlockPointer());
418 return PointeeStorage.BS;
419 }
420 [[nodiscard]] const IntPointer &asIntPointer() const {
421 assert(isIntegralPointer());
422 return PointeeStorage.Int;
423 }
424 bool isBlockPointer() const { return StorageKind == Storage::Block; }
425 bool isIntegralPointer() const { return StorageKind == Storage::Int; }
426
427 /// Returns the record descriptor of a class.
428 const Record *getRecord() const { return getFieldDesc()->ElemRecord; }
429 /// Returns the element record type, if this is a non-primive array.
430 const Record *getElemRecord() const {
431 const Descriptor *ElemDesc = getFieldDesc()->ElemDesc;
432 return ElemDesc ? ElemDesc->ElemRecord : nullptr;
433 }
434 /// Returns the field information.
435 const FieldDecl *getField() const { return getFieldDesc()->asFieldDecl(); }
436
437 /// Checks if the object is a union.
438 bool isUnion() const;
439
440 /// Checks if the storage is extern.
441 bool isExtern() const {
442 if (isBlockPointer())
443 return asBlockPointer().Pointee && asBlockPointer().Pointee->isExtern();
444 return false;
445 }
446 /// Checks if the storage is static.
447 bool isStatic() const {
448 if (isIntegralPointer())
449 return true;
450 assert(asBlockPointer().Pointee);
451 return asBlockPointer().Pointee->isStatic();
452 }
453 /// Checks if the storage is temporary.
454 bool isTemporary() const {
455 if (isBlockPointer()) {
456 assert(asBlockPointer().Pointee);
457 return asBlockPointer().Pointee->isTemporary();
458 }
459 return false;
460 }
461 /// Checks if the storage is a static temporary.
462 bool isStaticTemporary() const { return isStatic() && isTemporary(); }
463
464 /// Checks if the field is mutable.
465 bool isMutable() const {
466 if (!isBlockPointer())
467 return false;
468 return !isRoot() && getInlineDesc()->IsFieldMutable;
469 }
470
471 bool isWeak() const {
472 if (isIntegralPointer())
473 return false;
474
475 assert(isBlockPointer());
476 if (const ValueDecl *VD = getDeclDesc()->asValueDecl())
477 return VD->isWeak();
478 return false;
479 }
480 /// Checks if an object was initialized.
481 bool isInitialized() const;
482 /// Checks if the object is active.
483 bool isActive() const {
484 if (!isBlockPointer())
485 return true;
486 return isRoot() || getInlineDesc()->IsActive;
487 }
488 /// Checks if a structure is a base class.
489 bool isBaseClass() const { return isField() && getInlineDesc()->IsBase; }
490 bool isVirtualBaseClass() const {
491 return isField() && getInlineDesc()->IsVirtualBase;
492 }
493 /// Checks if the pointer points to a dummy value.
494 bool isDummy() const {
495 if (!isBlockPointer())
496 return false;
497
498 if (!asBlockPointer().Pointee)
499 return false;
500
501 return getDeclDesc()->isDummy();
502 }
503
504 /// Checks if an object or a subfield is mutable.
505 bool isConst() const {
506 if (isIntegralPointer())
507 return true;
508 return isRoot() ? getDeclDesc()->IsConst : getInlineDesc()->IsConst;
509 }
510
511 /// Returns the declaration ID.
512 std::optional<unsigned> getDeclID() const {
513 if (isBlockPointer()) {
514 assert(asBlockPointer().Pointee);
515 return asBlockPointer().Pointee->getDeclID();
516 }
517 return std::nullopt;
518 }
519
520 /// Returns the byte offset from the start.
521 unsigned getByteOffset() const {
522 if (isIntegralPointer())
523 return asIntPointer().Value + Offset;
524 if (isOnePastEnd())
525 return PastEndMark;
526 return Offset;
527 }
528
529 /// Returns the number of elements.
530 unsigned getNumElems() const {
531 if (isIntegralPointer())
532 return ~unsigned(0);
533 return getSize() / elemSize();
534 }
535
536 const Block *block() const { return asBlockPointer().Pointee; }
537
538 /// Returns the index into an array.
539 int64_t getIndex() const {
540 if (!isBlockPointer())
541 return 0;
542
543 if (isZero())
544 return 0;
545
546 // narrow()ed element in a composite array.
547 if (asBlockPointer().Base > sizeof(InlineDescriptor) &&
548 asBlockPointer().Base == Offset)
549 return 0;
550
551 if (auto ElemSize = elemSize())
552 return getOffset() / ElemSize;
553 return 0;
554 }
555
556 /// Checks if the index is one past end.
557 bool isOnePastEnd() const {
558 if (isIntegralPointer())
559 return false;
560
561 if (!asBlockPointer().Pointee)
562 return false;
563
564 if (isUnknownSizeArray())
565 return false;
566
567 return isElementPastEnd() || isPastEnd() ||
568 (getSize() == getOffset() && !isZeroSizeArray());
569 }
570
571 /// Checks if the pointer points past the end of the object.
572 bool isPastEnd() const {
573 if (isIntegralPointer())
574 return false;
575
576 return !isZero() && Offset > PointeeStorage.BS.Pointee->getSize();
577 }
578
579 /// Checks if the pointer is an out-of-bounds element pointer.
580 bool isElementPastEnd() const { return Offset == PastEndMark; }
581
582 /// Checks if the pointer is pointing to a zero-size array.
583 bool isZeroSizeArray() const { return getFieldDesc()->isZeroSizeArray(); }
584
585 /// Dereferences the pointer, if it's live.
586 template <typename T> T &deref() const {
587 assert(isLive() && "Invalid pointer");
588 assert(isBlockPointer());
589 assert(asBlockPointer().Pointee);
590 assert(isDereferencable());
591 assert(Offset + sizeof(T) <=
592 asBlockPointer().Pointee->getDescriptor()->getAllocSize());
593
594 if (isArrayRoot())
595 return *reinterpret_cast<T *>(asBlockPointer().Pointee->rawData() +
596 asBlockPointer().Base + sizeof(InitMapPtr));
597
598 return *reinterpret_cast<T *>(asBlockPointer().Pointee->rawData() + Offset);
599 }
600
601 /// Dereferences a primitive element.
602 template <typename T> T &elem(unsigned I) const {
603 assert(I < getNumElems());
604 assert(isBlockPointer());
605 assert(asBlockPointer().Pointee);
606 return reinterpret_cast<T *>(asBlockPointer().Pointee->data() +
607 sizeof(InitMapPtr))[I];
608 }
609
610 /// Whether this block can be read from at all. This is only true for
611 /// block pointers that point to a valid location inside that block.
612 bool isDereferencable() const {
613 if (!isBlockPointer())
614 return false;
615 if (isPastEnd())
616 return false;
617
618 return true;
619 }
620
621 /// Initializes a field.
622 void initialize() const;
623 /// Activats a field.
624 void activate() const;
625 /// Deactivates an entire strurcutre.
626 void deactivate() const;
627
628 /// Compare two pointers.
629 ComparisonCategoryResult compare(const Pointer &Other) const {
630 if (!hasSameBase(A: *this, B: Other))
631 return ComparisonCategoryResult::Unordered;
632
633 if (Offset < Other.Offset)
634 return ComparisonCategoryResult::Less;
635 else if (Offset > Other.Offset)
636 return ComparisonCategoryResult::Greater;
637
638 return ComparisonCategoryResult::Equal;
639 }
640
641 /// Checks if two pointers are comparable.
642 static bool hasSameBase(const Pointer &A, const Pointer &B);
643 /// Checks if two pointers can be subtracted.
644 static bool hasSameArray(const Pointer &A, const Pointer &B);
645
646 /// Prints the pointer.
647 void print(llvm::raw_ostream &OS) const;
648
649private:
650 friend class Block;
651 friend class DeadBlock;
652 friend class MemberPointer;
653 friend class InterpState;
654 friend struct InitMap;
655 friend class DynamicAllocator;
656
657 Pointer(Block *Pointee, unsigned Base, uint64_t Offset);
658
659 /// Returns the embedded descriptor preceding a field.
660 InlineDescriptor *getInlineDesc() const {
661 assert(asBlockPointer().Base != sizeof(GlobalInlineDescriptor));
662 assert(asBlockPointer().Base <= asBlockPointer().Pointee->getSize());
663 return getDescriptor(Offset: asBlockPointer().Base);
664 }
665
666 /// Returns a descriptor at a given offset.
667 InlineDescriptor *getDescriptor(unsigned Offset) const {
668 assert(Offset != 0 && "Not a nested pointer");
669 assert(isBlockPointer());
670 assert(!isZero());
671 return reinterpret_cast<InlineDescriptor *>(
672 asBlockPointer().Pointee->rawData() + Offset) -
673 1;
674 }
675
676 /// Returns a reference to the InitMapPtr which stores the initialization map.
677 InitMapPtr &getInitMap() const {
678 assert(isBlockPointer());
679 assert(!isZero());
680 return *reinterpret_cast<InitMapPtr *>(asBlockPointer().Pointee->rawData() +
681 asBlockPointer().Base);
682 }
683
684 /// Offset into the storage.
685 uint64_t Offset = 0;
686
687 /// Previous link in the pointer chain.
688 Pointer *Prev = nullptr;
689 /// Next link in the pointer chain.
690 Pointer *Next = nullptr;
691
692 union {
693 BlockPointer BS;
694 IntPointer Int;
695 } PointeeStorage;
696 Storage StorageKind = Storage::Int;
697};
698
699inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Pointer &P) {
700 P.print(OS);
701 return OS;
702}
703
704} // namespace interp
705} // namespace clang
706
707#endif
708