1 //===- Redeclarable.h - Base for Decls that can be redeclared --*- 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 // This file defines the Redeclarable interface. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #ifndef LLVM_CLANG_AST_REDECLARABLE_H 14 #define LLVM_CLANG_AST_REDECLARABLE_H 15 16 #include "clang/AST/ExternalASTSource.h" 17 #include "llvm/ADT/DenseMapInfo.h" 18 #include "llvm/ADT/PointerUnion.h" 19 #include "llvm/ADT/iterator_range.h" 20 #include "llvm/Support/Casting.h" 21 #include <cassert> 22 #include <cstddef> 23 #include <iterator> 24 25 namespace clang { 26 27 class ASTContext; 28 class Decl; 29 30 // Some notes on redeclarables: 31 // 32 // - Every redeclarable is on a circular linked list. 33 // 34 // - Every decl has a pointer to the first element of the chain _and_ a 35 // DeclLink that may point to one of 3 possible states: 36 // - the "previous" (temporal) element in the chain 37 // - the "latest" (temporal) element in the chain 38 // - the "uninitialized-latest" value (when newly-constructed) 39 // 40 // - The first element is also often called the canonical element. Every 41 // element has a pointer to it so that "getCanonical" can be fast. 42 // 43 // - Most links in the chain point to previous, except the link out of 44 // the first; it points to latest. 45 // 46 // - Elements are called "first", "previous", "latest" or 47 // "most-recent" when referring to temporal order: order of addition 48 // to the chain. 49 // 50 // - It's easiest to just ignore the implementation of DeclLink when making 51 // sense of the redeclaration chain. 52 // 53 // - There's also a "definition" link for several types of 54 // redeclarable, where only one definition should exist at any given 55 // time (and the defn pointer is stored in the decl's "data" which 56 // is copied to every element on the chain when it's changed). 57 // 58 // Here is some ASCII art: 59 // 60 // "first" "latest" 61 // "canonical" "most recent" 62 // +------------+ first +--------------+ 63 // | | <--------------------------- | | 64 // | | | | 65 // | | | | 66 // | | +--------------+ | | 67 // | | first | | | | 68 // | | <---- | | | | 69 // | | | | | | 70 // | @class A | link | @interface A | link | @class A | 71 // | seen first | <---- | seen second | <---- | seen third | 72 // | | | | | | 73 // +------------+ +--------------+ +--------------+ 74 // | data | defn | data | defn | data | 75 // | | ----> | | <---- | | 76 // +------------+ +--------------+ +--------------+ 77 // | | ^ ^ 78 // | |defn | | 79 // | link +-----+ | 80 // +-->-------------------------------------------+ 81 82 /// Provides common interface for the Decls that can be redeclared. 83 template<typename decl_type> 84 class Redeclarable { 85 protected: 86 class DeclLink { 87 /// A pointer to a known latest declaration, either statically known or 88 /// generationally updated as decls are added by an external source. 89 using KnownLatest = 90 LazyGenerationalUpdatePtr<const Decl *, Decl *, 91 &ExternalASTSource::CompleteRedeclChain>; 92 93 /// We store a pointer to the ASTContext in the UninitializedLatest 94 /// pointer, but to avoid circular type dependencies when we steal the low 95 /// bits of this pointer, we use a raw void* here. 96 using UninitializedLatest = const void *; 97 98 using Previous = Decl *; 99 100 /// A pointer to either an uninitialized latest declaration (where either 101 /// we've not yet set the previous decl or there isn't one), or to a known 102 /// previous declaration. 103 using NotKnownLatest = llvm::PointerUnion<Previous, UninitializedLatest>; 104 105 mutable llvm::PointerUnion<NotKnownLatest, KnownLatest> Link; 106 107 public: 108 enum PreviousTag { PreviousLink }; 109 enum LatestTag { LatestLink }; 110 DeclLink(LatestTag,const ASTContext & Ctx)111 DeclLink(LatestTag, const ASTContext &Ctx) 112 : Link(NotKnownLatest(reinterpret_cast<UninitializedLatest>(&Ctx))) {} DeclLink(PreviousTag,decl_type * D)113 DeclLink(PreviousTag, decl_type *D) : Link(NotKnownLatest(Previous(D))) {} 114 isFirst()115 bool isFirst() const { 116 return Link.is<KnownLatest>() || 117 // FIXME: 'template' is required on the next line due to an 118 // apparent clang bug. 119 Link.get<NotKnownLatest>().template is<UninitializedLatest>(); 120 } 121 getPrevious(const decl_type * D)122 decl_type *getPrevious(const decl_type *D) const { 123 if (Link.is<NotKnownLatest>()) { 124 NotKnownLatest NKL = Link.get<NotKnownLatest>(); 125 if (NKL.is<Previous>()) 126 return static_cast<decl_type*>(NKL.get<Previous>()); 127 128 // Allocate the generational 'most recent' cache now, if needed. 129 Link = KnownLatest(*reinterpret_cast<const ASTContext *>( 130 NKL.get<UninitializedLatest>()), 131 const_cast<decl_type *>(D)); 132 } 133 134 return static_cast<decl_type*>(Link.get<KnownLatest>().get(D)); 135 } 136 setPrevious(decl_type * D)137 void setPrevious(decl_type *D) { 138 assert(!isFirst() && "decl became non-canonical unexpectedly"); 139 Link = Previous(D); 140 } 141 setLatest(decl_type * D)142 void setLatest(decl_type *D) { 143 assert(isFirst() && "decl became canonical unexpectedly"); 144 if (Link.is<NotKnownLatest>()) { 145 NotKnownLatest NKL = Link.get<NotKnownLatest>(); 146 Link = KnownLatest(*reinterpret_cast<const ASTContext *>( 147 NKL.get<UninitializedLatest>()), 148 D); 149 } else { 150 auto Latest = Link.get<KnownLatest>(); 151 Latest.set(D); 152 Link = Latest; 153 } 154 } 155 markIncomplete()156 void markIncomplete() { Link.get<KnownLatest>().markIncomplete(); } 157 getLatestNotUpdated()158 Decl *getLatestNotUpdated() const { 159 assert(isFirst() && "expected a canonical decl"); 160 if (Link.is<NotKnownLatest>()) 161 return nullptr; 162 return Link.get<KnownLatest>().getNotUpdated(); 163 } 164 }; 165 PreviousDeclLink(decl_type * D)166 static DeclLink PreviousDeclLink(decl_type *D) { 167 return DeclLink(DeclLink::PreviousLink, D); 168 } 169 LatestDeclLink(const ASTContext & Ctx)170 static DeclLink LatestDeclLink(const ASTContext &Ctx) { 171 return DeclLink(DeclLink::LatestLink, Ctx); 172 } 173 174 /// Points to the next redeclaration in the chain. 175 /// 176 /// If isFirst() is false, this is a link to the previous declaration 177 /// of this same Decl. If isFirst() is true, this is the first 178 /// declaration and Link points to the latest declaration. For example: 179 /// 180 /// #1 int f(int x, int y = 1); // <pointer to #3, true> 181 /// #2 int f(int x = 0, int y); // <pointer to #1, false> 182 /// #3 int f(int x, int y) { return x + y; } // <pointer to #2, false> 183 /// 184 /// If there is only one declaration, it is <pointer to self, true> 185 DeclLink RedeclLink; 186 187 decl_type *First; 188 getNextRedeclaration()189 decl_type *getNextRedeclaration() const { 190 return RedeclLink.getPrevious(static_cast<const decl_type *>(this)); 191 } 192 193 public: 194 friend class ASTDeclReader; 195 friend class ASTDeclWriter; 196 friend class IncrementalParser; 197 Redeclarable(const ASTContext & Ctx)198 Redeclarable(const ASTContext &Ctx) 199 : RedeclLink(LatestDeclLink(Ctx)), 200 First(static_cast<decl_type *>(this)) {} 201 202 /// Return the previous declaration of this declaration or NULL if this 203 /// is the first declaration. getPreviousDecl()204 decl_type *getPreviousDecl() { 205 if (!RedeclLink.isFirst()) 206 return getNextRedeclaration(); 207 return nullptr; 208 } getPreviousDecl()209 const decl_type *getPreviousDecl() const { 210 return const_cast<decl_type *>( 211 static_cast<const decl_type*>(this))->getPreviousDecl(); 212 } 213 214 /// Return the first declaration of this declaration or itself if this 215 /// is the only declaration. getFirstDecl()216 decl_type *getFirstDecl() { return First; } 217 218 /// Return the first declaration of this declaration or itself if this 219 /// is the only declaration. getFirstDecl()220 const decl_type *getFirstDecl() const { return First; } 221 222 /// True if this is the first declaration in its redeclaration chain. isFirstDecl()223 bool isFirstDecl() const { return RedeclLink.isFirst(); } 224 225 /// Returns the most recent (re)declaration of this declaration. getMostRecentDecl()226 decl_type *getMostRecentDecl() { 227 return getFirstDecl()->getNextRedeclaration(); 228 } 229 230 /// Returns the most recent (re)declaration of this declaration. getMostRecentDecl()231 const decl_type *getMostRecentDecl() const { 232 return getFirstDecl()->getNextRedeclaration(); 233 } 234 235 /// Set the previous declaration. If PrevDecl is NULL, set this as the 236 /// first and only declaration. 237 void setPreviousDecl(decl_type *PrevDecl); 238 239 /// Iterates through all the redeclarations of the same decl. 240 class redecl_iterator { 241 /// Current - The current declaration. 242 decl_type *Current = nullptr; 243 decl_type *Starter = nullptr; 244 bool PassedFirst = false; 245 246 public: 247 using value_type = decl_type *; 248 using reference = decl_type *; 249 using pointer = decl_type *; 250 using iterator_category = std::forward_iterator_tag; 251 using difference_type = std::ptrdiff_t; 252 253 redecl_iterator() = default; redecl_iterator(decl_type * C)254 explicit redecl_iterator(decl_type *C) : Current(C), Starter(C) {} 255 256 reference operator*() const { return Current; } 257 pointer operator->() const { return Current; } 258 259 redecl_iterator& operator++() { 260 assert(Current && "Advancing while iterator has reached end"); 261 // Make sure we don't infinitely loop on an invalid redecl chain. This 262 // should never happen. 263 if (Current->isFirstDecl()) { 264 if (PassedFirst) { 265 assert(0 && "Passed first decl twice, invalid redecl chain!"); 266 Current = nullptr; 267 return *this; 268 } 269 PassedFirst = true; 270 } 271 272 // Get either previous decl or latest decl. 273 decl_type *Next = Current->getNextRedeclaration(); 274 Current = (Next != Starter) ? Next : nullptr; 275 return *this; 276 } 277 278 redecl_iterator operator++(int) { 279 redecl_iterator tmp(*this); 280 ++(*this); 281 return tmp; 282 } 283 284 friend bool operator==(const redecl_iterator &x, const redecl_iterator &y) { 285 return x.Current == y.Current; 286 } 287 friend bool operator!=(const redecl_iterator &x, const redecl_iterator &y) { 288 return x.Current != y.Current; 289 } 290 }; 291 292 using redecl_range = llvm::iterator_range<redecl_iterator>; 293 294 /// Returns an iterator range for all the redeclarations of the same 295 /// decl. It will iterate at least once (when this decl is the only one). redecls()296 redecl_range redecls() const { 297 return redecl_range(redecl_iterator(const_cast<decl_type *>( 298 static_cast<const decl_type *>(this))), 299 redecl_iterator()); 300 } 301 redecls_begin()302 redecl_iterator redecls_begin() const { return redecls().begin(); } redecls_end()303 redecl_iterator redecls_end() const { return redecls().end(); } 304 }; 305 306 /// Get the primary declaration for a declaration from an AST file. That 307 /// will be the first-loaded declaration. 308 Decl *getPrimaryMergedDecl(Decl *D); 309 310 /// Provides common interface for the Decls that cannot be redeclared, 311 /// but can be merged if the same declaration is brought in from multiple 312 /// modules. 313 template<typename decl_type> 314 class Mergeable { 315 public: 316 Mergeable() = default; 317 318 /// Return the first declaration of this declaration or itself if this 319 /// is the only declaration. getFirstDecl()320 decl_type *getFirstDecl() { 321 auto *D = static_cast<decl_type *>(this); 322 if (!D->isFromASTFile()) 323 return D; 324 return cast<decl_type>(getPrimaryMergedDecl(const_cast<decl_type*>(D))); 325 } 326 327 /// Return the first declaration of this declaration or itself if this 328 /// is the only declaration. getFirstDecl()329 const decl_type *getFirstDecl() const { 330 const auto *D = static_cast<const decl_type *>(this); 331 if (!D->isFromASTFile()) 332 return D; 333 return cast<decl_type>(getPrimaryMergedDecl(const_cast<decl_type*>(D))); 334 } 335 336 /// Returns true if this is the first declaration. isFirstDecl()337 bool isFirstDecl() const { return getFirstDecl() == this; } 338 }; 339 340 /// A wrapper class around a pointer that always points to its canonical 341 /// declaration. 342 /// 343 /// CanonicalDeclPtr<decl_type> behaves just like decl_type*, except we call 344 /// decl_type::getCanonicalDecl() on construction. 345 /// 346 /// This is useful for hashtables that you want to be keyed on a declaration's 347 /// canonical decl -- if you use CanonicalDeclPtr as the key, you don't need to 348 /// remember to call getCanonicalDecl() everywhere. 349 template <typename decl_type> class CanonicalDeclPtr { 350 public: 351 CanonicalDeclPtr() = default; CanonicalDeclPtr(decl_type * Ptr)352 CanonicalDeclPtr(decl_type *Ptr) 353 : Ptr(Ptr ? Ptr->getCanonicalDecl() : nullptr) {} 354 CanonicalDeclPtr(const CanonicalDeclPtr &) = default; 355 CanonicalDeclPtr &operator=(const CanonicalDeclPtr &) = default; 356 357 operator decl_type *() { return Ptr; } 358 operator const decl_type *() const { return Ptr; } 359 360 decl_type *operator->() { return Ptr; } 361 const decl_type *operator->() const { return Ptr; } 362 363 decl_type &operator*() { return *Ptr; } 364 const decl_type &operator*() const { return *Ptr; } 365 366 friend bool operator==(CanonicalDeclPtr LHS, CanonicalDeclPtr RHS) { 367 return LHS.Ptr == RHS.Ptr; 368 } 369 friend bool operator!=(CanonicalDeclPtr LHS, CanonicalDeclPtr RHS) { 370 return LHS.Ptr != RHS.Ptr; 371 } 372 373 private: 374 friend struct llvm::DenseMapInfo<CanonicalDeclPtr<decl_type>>; 375 friend struct llvm::PointerLikeTypeTraits<CanonicalDeclPtr<decl_type>>; 376 377 decl_type *Ptr = nullptr; 378 }; 379 380 } // namespace clang 381 382 namespace llvm { 383 384 template <typename decl_type> 385 struct DenseMapInfo<clang::CanonicalDeclPtr<decl_type>> { 386 using CanonicalDeclPtr = clang::CanonicalDeclPtr<decl_type>; 387 using BaseInfo = DenseMapInfo<decl_type *>; 388 389 static CanonicalDeclPtr getEmptyKey() { 390 // Construct our CanonicalDeclPtr this way because the regular constructor 391 // would dereference P.Ptr, which is not allowed. 392 CanonicalDeclPtr P; 393 P.Ptr = BaseInfo::getEmptyKey(); 394 return P; 395 } 396 397 static CanonicalDeclPtr getTombstoneKey() { 398 CanonicalDeclPtr P; 399 P.Ptr = BaseInfo::getTombstoneKey(); 400 return P; 401 } 402 403 static unsigned getHashValue(const CanonicalDeclPtr &P) { 404 return BaseInfo::getHashValue(P); 405 } 406 407 static bool isEqual(const CanonicalDeclPtr &LHS, 408 const CanonicalDeclPtr &RHS) { 409 return BaseInfo::isEqual(LHS, RHS); 410 } 411 }; 412 413 template <typename decl_type> 414 struct PointerLikeTypeTraits<clang::CanonicalDeclPtr<decl_type>> { 415 static inline void *getAsVoidPointer(clang::CanonicalDeclPtr<decl_type> P) { 416 return P.Ptr; 417 } 418 static inline clang::CanonicalDeclPtr<decl_type> getFromVoidPointer(void *P) { 419 clang::CanonicalDeclPtr<decl_type> C; 420 C.Ptr = PointerLikeTypeTraits<decl_type *>::getFromVoidPtr(P); 421 return C; 422 } 423 static constexpr int NumLowBitsAvailable = 424 PointerLikeTypeTraits<decl_type *>::NumLowBitsAvailable; 425 }; 426 427 } // namespace llvm 428 429 #endif // LLVM_CLANG_AST_REDECLARABLE_H 430