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