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 
25 namespace clang {
26 namespace interp {
27 class Block;
28 class DeadBlock;
29 class Pointer;
30 enum PrimType : unsigned;
31 
32 /// A pointer to a memory block, live or dead.
33 ///
34 /// This object can be allocated into interpreter stack frames. If pointing to
35 /// a live block, it is a link in the chain of pointers pointing to the block.
36 ///
37 /// In the simplest form, a Pointer has a Block* (the pointee) and both Base
38 /// and Offset are 0, which means it will point to raw data.
39 ///
40 /// The Base field is used to access metadata about the data. For primitive
41 /// arrays, the Base is followed by an InitMap. In a variety of cases, the
42 /// Base is preceded by an InlineDescriptor, which is used to track the
43 /// initialization state, among other things.
44 ///
45 /// The Offset field is used to access the actual data. In other words, the
46 /// data the pointer decribes can be found at
47 /// Pointee->rawData() + Pointer.Offset.
48 ///
49 ///
50 /// Pointee                      Offset
51 /// │                              │
52 /// │                              │
53 /// ▼                              ▼
54 /// ┌───────┬────────────┬─────────┬────────────────────────────┐
55 /// │ Block │ InlineDesc │ InitMap │ Actual Data                │
56 /// └───────┴────────────┴─────────┴────────────────────────────┘
57 ///                      ▲
58 ///                      │
59 ///                      │
60 ///                     Base
61 class Pointer {
62 private:
63   static constexpr unsigned PastEndMark = ~0u;
64   static constexpr unsigned RootPtrMark = ~0u;
65 
66 public:
67   Pointer() {}
68   Pointer(Block *B);
69   Pointer(Block *B, unsigned BaseAndOffset);
70   Pointer(const Pointer &P);
71   Pointer(Pointer &&P);
72   ~Pointer();
73 
74   void operator=(const Pointer &P);
75   void operator=(Pointer &&P);
76 
77   /// Converts the pointer to an APValue.
78   APValue toAPValue() const;
79 
80   /// Offsets a pointer inside an array.
81   Pointer atIndex(unsigned Idx) const {
82     if (Base == RootPtrMark)
83       return Pointer(Pointee, RootPtrMark, getDeclDesc()->getSize());
84     unsigned Off = Idx * elemSize();
85     if (getFieldDesc()->ElemDesc)
86       Off += sizeof(InlineDescriptor);
87     else
88       Off += sizeof(InitMap *);
89     return Pointer(Pointee, Base, Base + Off);
90   }
91 
92   /// Creates a pointer to a field.
93   Pointer atField(unsigned Off) const {
94     unsigned Field = Offset + Off;
95     return Pointer(Pointee, Field, Field);
96   }
97 
98   /// Restricts the scope of an array element pointer.
99   Pointer narrow() const {
100     // Null pointers cannot be narrowed.
101     if (isZero() || isUnknownSizeArray())
102       return *this;
103 
104     // Pointer to an array of base types - enter block.
105     if (Base == RootPtrMark)
106       return Pointer(Pointee, 0, Offset == 0 ? Offset : PastEndMark);
107 
108     // Pointer is one past end - magic offset marks that.
109     if (isOnePastEnd())
110       return Pointer(Pointee, Base, PastEndMark);
111 
112     // Primitive arrays are a bit special since they do not have inline
113     // descriptors. If Offset != Base, then the pointer already points to
114     // an element and there is nothing to do. Otherwise, the pointer is
115     // adjusted to the first element of the array.
116     if (inPrimitiveArray()) {
117       if (Offset != Base)
118         return *this;
119       return Pointer(Pointee, Base, Offset + sizeof(InitMap *));
120     }
121 
122     // Pointer is to a field or array element - enter it.
123     if (Offset != Base)
124       return Pointer(Pointee, Offset, Offset);
125 
126     // Enter the first element of an array.
127     if (!getFieldDesc()->isArray())
128       return *this;
129 
130     const unsigned NewBase = Base + sizeof(InlineDescriptor);
131     return Pointer(Pointee, NewBase, NewBase);
132   }
133 
134   /// Expands a pointer to the containing array, undoing narrowing.
135   Pointer expand() const {
136     if (isElementPastEnd()) {
137       // Revert to an outer one-past-end pointer.
138       unsigned Adjust;
139       if (inPrimitiveArray())
140         Adjust = sizeof(InitMap *);
141       else
142         Adjust = sizeof(InlineDescriptor);
143       return Pointer(Pointee, Base, Base + getSize() + Adjust);
144     }
145 
146     // Do not step out of array elements.
147     if (Base != Offset)
148       return *this;
149 
150     // If at base, point to an array of base types.
151     if (Base == 0)
152       return Pointer(Pointee, RootPtrMark, 0);
153 
154     // Step into the containing array, if inside one.
155     unsigned Next = Base - getInlineDesc()->Offset;
156     Descriptor *Desc = Next == 0 ? getDeclDesc() : getDescriptor(Next)->Desc;
157     if (!Desc->IsArray)
158       return *this;
159     return Pointer(Pointee, Next, Offset);
160   }
161 
162   /// Checks if the pointer is null.
163   bool isZero() const { return Pointee == nullptr; }
164   /// Checks if the pointer is live.
165   bool isLive() const { return Pointee && !Pointee->IsDead; }
166   /// Checks if the item is a field in an object.
167   bool isField() const { return Base != 0 && Base != RootPtrMark; }
168 
169   /// Accessor for information about the declaration site.
170   Descriptor *getDeclDesc() const { return Pointee->Desc; }
171   SourceLocation getDeclLoc() const { return getDeclDesc()->getLocation(); }
172 
173   /// Returns a pointer to the object of which this pointer is a field.
174   Pointer getBase() const {
175     if (Base == RootPtrMark) {
176       assert(Offset == PastEndMark && "cannot get base of a block");
177       return Pointer(Pointee, Base, 0);
178     }
179     assert(Offset == Base && "not an inner field");
180     unsigned NewBase = Base - getInlineDesc()->Offset;
181     return Pointer(Pointee, NewBase, NewBase);
182   }
183   /// Returns the parent array.
184   Pointer getArray() const {
185     if (Base == RootPtrMark) {
186       assert(Offset != 0 && Offset != PastEndMark && "not an array element");
187       return Pointer(Pointee, Base, 0);
188     }
189     assert(Offset != Base && "not an array element");
190     return Pointer(Pointee, Base, Base);
191   }
192 
193   /// Accessors for information about the innermost field.
194   Descriptor *getFieldDesc() const {
195     if (Base == 0 || Base == RootPtrMark)
196       return getDeclDesc();
197     return getInlineDesc()->Desc;
198   }
199 
200   /// Returns the type of the innermost field.
201   QualType getType() const { return getFieldDesc()->getType(); }
202 
203   /// Returns the element size of the innermost field.
204   size_t elemSize() const {
205     if (Base == RootPtrMark)
206       return getDeclDesc()->getSize();
207     return getFieldDesc()->getElemSize();
208   }
209   /// Returns the total size of the innermost field.
210   size_t getSize() const { return getFieldDesc()->getSize(); }
211 
212   /// Returns the offset into an array.
213   unsigned getOffset() const {
214     assert(Offset != PastEndMark && "invalid offset");
215     if (Base == RootPtrMark)
216       return Offset;
217 
218     unsigned Adjust = 0;
219     if (Offset != Base) {
220       if (getFieldDesc()->ElemDesc)
221         Adjust = sizeof(InlineDescriptor);
222       else
223         Adjust = sizeof(InitMap *);
224     }
225     return Offset - Base - Adjust;
226   }
227 
228   /// Checks if the innermost field is an array.
229   bool inArray() const { return getFieldDesc()->IsArray; }
230   /// Checks if the structure is a primitive array.
231   bool inPrimitiveArray() const { return getFieldDesc()->isPrimitiveArray(); }
232   /// Checks if the structure is an array of unknown size.
233   bool isUnknownSizeArray() const {
234     return getFieldDesc()->isUnknownSizeArray();
235   }
236   /// Checks if the pointer points to an array.
237   bool isArrayElement() const { return Base != Offset; }
238   /// Pointer points directly to a block.
239   bool isRoot() const {
240     return (Base == 0 || Base == RootPtrMark) && Offset == 0;
241   }
242 
243   /// Returns the record descriptor of a class.
244   Record *getRecord() const { return getFieldDesc()->ElemRecord; }
245   // Returns the element record type, if this is a non-primive array.
246   Record *getElemRecord() const { return getFieldDesc()->ElemDesc->ElemRecord; }
247   /// Returns the field information.
248   const FieldDecl *getField() const { return getFieldDesc()->asFieldDecl(); }
249 
250   /// Checks if the object is a union.
251   bool isUnion() const;
252 
253   /// Checks if the storage is extern.
254   bool isExtern() const { return Pointee->isExtern(); }
255   /// Checks if the storage is static.
256   bool isStatic() const { return Pointee->isStatic(); }
257   /// Checks if the storage is temporary.
258   bool isTemporary() const { return Pointee->isTemporary(); }
259   /// Checks if the storage is a static temporary.
260   bool isStaticTemporary() const { return isStatic() && isTemporary(); }
261 
262   /// Checks if the field is mutable.
263   bool isMutable() const {
264     return Base != 0 && getInlineDesc()->IsFieldMutable;
265   }
266   /// Checks if an object was initialized.
267   bool isInitialized() const;
268   /// Checks if the object is active.
269   bool isActive() const { return Base == 0 || getInlineDesc()->IsActive; }
270   /// Checks if a structure is a base class.
271   bool isBaseClass() const { return isField() && getInlineDesc()->IsBase; }
272 
273   /// Checks if an object or a subfield is mutable.
274   bool isConst() const {
275     return Base == 0 ? getDeclDesc()->IsConst : getInlineDesc()->IsConst;
276   }
277 
278   /// Returns the declaration ID.
279   std::optional<unsigned> getDeclID() const { return Pointee->getDeclID(); }
280 
281   /// Returns the byte offset from the start.
282   unsigned getByteOffset() const {
283     return Offset;
284   }
285 
286   /// Returns the number of elements.
287   unsigned getNumElems() const { return getSize() / elemSize(); }
288 
289   /// Returns the index into an array.
290   int64_t getIndex() const {
291     if (isElementPastEnd())
292       return 1;
293     if (auto ElemSize = elemSize())
294       return getOffset() / ElemSize;
295     return 0;
296   }
297 
298   /// Checks if the index is one past end.
299   bool isOnePastEnd() const {
300     return isElementPastEnd() || getSize() == getOffset();
301   }
302 
303   /// Checks if the pointer is an out-of-bounds element pointer.
304   bool isElementPastEnd() const { return Offset == PastEndMark; }
305 
306   /// Dereferences the pointer, if it's live.
307   template <typename T> T &deref() const {
308     assert(isLive() && "Invalid pointer");
309     return *reinterpret_cast<T *>(Pointee->rawData() + Offset);
310   }
311 
312   /// Dereferences a primitive element.
313   template <typename T> T &elem(unsigned I) const {
314     return reinterpret_cast<T *>(Pointee->rawData())[I];
315   }
316 
317   /// Initializes a field.
318   void initialize() const;
319   /// Activats a field.
320   void activate() const;
321   /// Deactivates an entire strurcutre.
322   void deactivate() const;
323 
324   /// Checks if two pointers are comparable.
325   static bool hasSameBase(const Pointer &A, const Pointer &B);
326   /// Checks if two pointers can be subtracted.
327   static bool hasSameArray(const Pointer &A, const Pointer &B);
328 
329   /// Prints the pointer.
330   void print(llvm::raw_ostream &OS) const {
331     OS << Pointee << " {" << Base << ", " << Offset << ", ";
332     if (Pointee)
333       OS << Pointee->getSize();
334     else
335       OS << "nullptr";
336     OS << "}";
337   }
338 
339 private:
340   friend class Block;
341   friend class DeadBlock;
342 
343   Pointer(Block *Pointee, unsigned Base, unsigned Offset);
344 
345   /// Returns the embedded descriptor preceding a field.
346   InlineDescriptor *getInlineDesc() const { return getDescriptor(Base); }
347 
348   /// Returns a descriptor at a given offset.
349   InlineDescriptor *getDescriptor(unsigned Offset) const {
350     assert(Offset != 0 && "Not a nested pointer");
351     return reinterpret_cast<InlineDescriptor *>(Pointee->rawData() + Offset) -
352            1;
353   }
354 
355   /// Returns a reference to the pointer which stores the initialization map.
356   InitMap *&getInitMap() const {
357     return *reinterpret_cast<InitMap **>(Pointee->rawData() + Base);
358   }
359 
360   /// The block the pointer is pointing to.
361   Block *Pointee = nullptr;
362   /// Start of the current subfield.
363   unsigned Base = 0;
364   /// Offset into the block.
365   unsigned Offset = 0;
366 
367   /// Previous link in the pointer chain.
368   Pointer *Prev = nullptr;
369   /// Next link in the pointer chain.
370   Pointer *Next = nullptr;
371 };
372 
373 inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Pointer &P) {
374   P.print(OS);
375   return OS;
376 }
377 
378 } // namespace interp
379 } // namespace clang
380 
381 #endif
382