clang/lib/AST/Interp/Pointer.h

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