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   Pointer getDeclPtr() const { return Pointer(Pointee); }
204 
205   /// Returns the element size of the innermost field.
206   size_t elemSize() const {
207     if (Base == RootPtrMark)
208       return getDeclDesc()->getSize();
209     return getFieldDesc()->getElemSize();
210   }
211   /// Returns the total size of the innermost field.
212   size_t getSize() const { return getFieldDesc()->getSize(); }
213 
214   /// Returns the offset into an array.
215   unsigned getOffset() const {
216     assert(Offset != PastEndMark && "invalid offset");
217     if (Base == RootPtrMark)
218       return Offset;
219 
220     unsigned Adjust = 0;
221     if (Offset != Base) {
222       if (getFieldDesc()->ElemDesc)
223         Adjust = sizeof(InlineDescriptor);
224       else
225         Adjust = sizeof(InitMap *);
226     }
227     return Offset - Base - Adjust;
228   }
229 
230   /// Whether this array refers to an array, but not
231   /// to the first element.
232   bool isArrayRoot() const { return inArray() && Offset == Base; }
233 
234   /// Checks if the innermost field is an array.
235   bool inArray() const { return getFieldDesc()->IsArray; }
236   /// Checks if the structure is a primitive array.
237   bool inPrimitiveArray() const { return getFieldDesc()->isPrimitiveArray(); }
238   /// Checks if the structure is an array of unknown size.
239   bool isUnknownSizeArray() const {
240     return getFieldDesc()->isUnknownSizeArray();
241   }
242   /// Checks if the pointer points to an array.
243   bool isArrayElement() const { return Base != Offset; }
244   /// Pointer points directly to a block.
245   bool isRoot() const {
246     return (Base == 0 || Base == RootPtrMark) && Offset == 0;
247   }
248 
249   /// Returns the record descriptor of a class.
250   const Record *getRecord() const { return getFieldDesc()->ElemRecord; }
251   /// Returns the element record type, if this is a non-primive array.
252   const Record *getElemRecord() const {
253     return getFieldDesc()->ElemDesc->ElemRecord;
254   }
255   /// Returns the field information.
256   const FieldDecl *getField() const { return getFieldDesc()->asFieldDecl(); }
257 
258   /// Checks if the object is a union.
259   bool isUnion() const;
260 
261   /// Checks if the storage is extern.
262   bool isExtern() const { return Pointee->isExtern(); }
263   /// Checks if the storage is static.
264   bool isStatic() const { return Pointee->isStatic(); }
265   /// Checks if the storage is temporary.
266   bool isTemporary() const { return Pointee->isTemporary(); }
267   /// Checks if the storage is a static temporary.
268   bool isStaticTemporary() const { return isStatic() && isTemporary(); }
269 
270   /// Checks if the field is mutable.
271   bool isMutable() const {
272     return Base != 0 && getInlineDesc()->IsFieldMutable;
273   }
274   /// Checks if an object was initialized.
275   bool isInitialized() const;
276   /// Checks if the object is active.
277   bool isActive() const { return Base == 0 || getInlineDesc()->IsActive; }
278   /// Checks if a structure is a base class.
279   bool isBaseClass() const { return isField() && getInlineDesc()->IsBase; }
280 
281   /// Checks if an object or a subfield is mutable.
282   bool isConst() const {
283     return Base == 0 ? getDeclDesc()->IsConst : getInlineDesc()->IsConst;
284   }
285 
286   /// Returns the declaration ID.
287   std::optional<unsigned> getDeclID() const { return Pointee->getDeclID(); }
288 
289   /// Returns the byte offset from the start.
290   unsigned getByteOffset() const {
291     return Offset;
292   }
293 
294   /// Returns the number of elements.
295   unsigned getNumElems() const { return getSize() / elemSize(); }
296 
297   const Block *block() const { return Pointee; }
298 
299   /// Returns the index into an array.
300   int64_t getIndex() const {
301     if (isElementPastEnd())
302       return 1;
303     if (auto ElemSize = elemSize())
304       return getOffset() / ElemSize;
305     return 0;
306   }
307 
308   /// Checks if the index is one past end.
309   bool isOnePastEnd() const {
310     return isElementPastEnd() || getSize() == getOffset();
311   }
312 
313   /// Checks if the pointer is an out-of-bounds element pointer.
314   bool isElementPastEnd() const { return Offset == PastEndMark; }
315 
316   /// Dereferences the pointer, if it's live.
317   template <typename T> T &deref() const {
318     assert(isLive() && "Invalid pointer");
319     if (isArrayRoot())
320       return *reinterpret_cast<T *>(Pointee->rawData() + Base +
321                                     sizeof(InitMap *));
322 
323     return *reinterpret_cast<T *>(Pointee->rawData() + Offset);
324   }
325 
326   /// Dereferences a primitive element.
327   template <typename T> T &elem(unsigned I) const {
328     assert(I < getNumElems());
329     return reinterpret_cast<T *>(Pointee->data() + sizeof(InitMap *))[I];
330   }
331 
332   /// Initializes a field.
333   void initialize() const;
334   /// Activats a field.
335   void activate() const;
336   /// Deactivates an entire strurcutre.
337   void deactivate() const;
338 
339   /// Checks if two pointers are comparable.
340   static bool hasSameBase(const Pointer &A, const Pointer &B);
341   /// Checks if two pointers can be subtracted.
342   static bool hasSameArray(const Pointer &A, const Pointer &B);
343 
344   /// Prints the pointer.
345   void print(llvm::raw_ostream &OS) const {
346     OS << Pointee << " {" << Base << ", " << Offset << ", ";
347     if (Pointee)
348       OS << Pointee->getSize();
349     else
350       OS << "nullptr";
351     OS << "}";
352   }
353 
354 private:
355   friend class Block;
356   friend class DeadBlock;
357 
358   Pointer(Block *Pointee, unsigned Base, unsigned Offset);
359 
360   /// Returns the embedded descriptor preceding a field.
361   InlineDescriptor *getInlineDesc() const { return getDescriptor(Base); }
362 
363   /// Returns a descriptor at a given offset.
364   InlineDescriptor *getDescriptor(unsigned Offset) const {
365     assert(Offset != 0 && "Not a nested pointer");
366     return reinterpret_cast<InlineDescriptor *>(Pointee->rawData() + Offset) -
367            1;
368   }
369 
370   /// Returns a reference to the pointer which stores the initialization map.
371   InitMap *&getInitMap() const {
372     return *reinterpret_cast<InitMap **>(Pointee->rawData() + Base);
373   }
374 
375   /// The block the pointer is pointing to.
376   Block *Pointee = nullptr;
377   /// Start of the current subfield.
378   unsigned Base = 0;
379   /// Offset into the block.
380   unsigned Offset = 0;
381 
382   /// Previous link in the pointer chain.
383   Pointer *Prev = nullptr;
384   /// Next link in the pointer chain.
385   Pointer *Next = nullptr;
386 };
387 
388 inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Pointer &P) {
389   P.print(OS);
390   return OS;
391 }
392 
393 } // namespace interp
394 } // namespace clang
395 
396 #endif
397