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

source code of clang/lib/AST/Interp/Pointer.h