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