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 111 DeclLink(LatestTag, const ASTContext &Ctx) 112 : Link(NotKnownLatest(reinterpret_cast<UninitializedLatest>(&Ctx))) {} 113 DeclLink(PreviousTag, decl_type *D) : Link(NotKnownLatest(Previous(D))) {} 114 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 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 137 void setPrevious(decl_type *D) { 138 assert(!isFirst() && "decl became non-canonical unexpectedly"); 139 Link = Previous(D); 140 } 141 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 156 void markIncomplete() { Link.get<KnownLatest>().markIncomplete(); } 157 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 166 static DeclLink PreviousDeclLink(decl_type *D) { 167 return DeclLink(DeclLink::PreviousLink, D); 168 } 169 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 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 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. 204 decl_type *getPreviousDecl() { 205 if (!RedeclLink.isFirst()) 206 return getNextRedeclaration(); 207 return nullptr; 208 } 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. 216 decl_type *getFirstDecl() { return First; } 217 218 /// Return the first declaration of this declaration or itself if this 219 /// is the only declaration. 220 const decl_type *getFirstDecl() const { return First; } 221 222 /// True if this is the first declaration in its redeclaration chain. 223 bool isFirstDecl() const { return RedeclLink.isFirst(); } 224 225 /// Returns the most recent (re)declaration of this declaration. 226 decl_type *getMostRecentDecl() { 227 return getFirstDecl()->getNextRedeclaration(); 228 } 229 230 /// Returns the most recent (re)declaration of this declaration. 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; 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; 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 // Sanity check to avoid infinite loop on invalid redecl chain. 262 if (Current->isFirstDecl()) { 263 if (PassedFirst) { 264 assert(0 && "Passed first decl twice, invalid redecl chain!"); 265 Current = nullptr; 266 return *this; 267 } 268 PassedFirst = true; 269 } 270 271 // Get either previous decl or latest decl. 272 decl_type *Next = Current->getNextRedeclaration(); 273 Current = (Next != Starter) ? Next : nullptr; 274 return *this; 275 } 276 277 redecl_iterator operator++(int) { 278 redecl_iterator tmp(*this); 279 ++(*this); 280 return tmp; 281 } 282 283 friend bool operator==(redecl_iterator x, redecl_iterator y) { 284 return x.Current == y.Current; 285 } 286 friend bool operator!=(redecl_iterator x, redecl_iterator y) { 287 return x.Current != y.Current; 288 } 289 }; 290 291 using redecl_range = llvm::iterator_range<redecl_iterator>; 292 293 /// Returns an iterator range for all the redeclarations of the same 294 /// decl. It will iterate at least once (when this decl is the only one). 295 redecl_range redecls() const { 296 return redecl_range(redecl_iterator(const_cast<decl_type *>( 297 static_cast<const decl_type *>(this))), 298 redecl_iterator()); 299 } 300 301 redecl_iterator redecls_begin() const { return redecls().begin(); } 302 redecl_iterator redecls_end() const { return redecls().end(); } 303 }; 304 305 /// Get the primary declaration for a declaration from an AST file. That 306 /// will be the first-loaded declaration. 307 Decl *getPrimaryMergedDecl(Decl *D); 308 309 /// Provides common interface for the Decls that cannot be redeclared, 310 /// but can be merged if the same declaration is brought in from multiple 311 /// modules. 312 template<typename decl_type> 313 class Mergeable { 314 public: 315 Mergeable() = default; 316 317 /// Return the first declaration of this declaration or itself if this 318 /// is the only declaration. 319 decl_type *getFirstDecl() { 320 auto *D = static_cast<decl_type *>(this); 321 if (!D->isFromASTFile()) 322 return D; 323 return cast<decl_type>(getPrimaryMergedDecl(const_cast<decl_type*>(D))); 324 } 325 326 /// Return the first declaration of this declaration or itself if this 327 /// is the only declaration. 328 const decl_type *getFirstDecl() const { 329 const auto *D = static_cast<const decl_type *>(this); 330 if (!D->isFromASTFile()) 331 return D; 332 return cast<decl_type>(getPrimaryMergedDecl(const_cast<decl_type*>(D))); 333 } 334 335 /// Returns true if this is the first declaration. 336 bool isFirstDecl() const { return getFirstDecl() == this; } 337 }; 338 339 /// A wrapper class around a pointer that always points to its canonical 340 /// declaration. 341 /// 342 /// CanonicalDeclPtr<decl_type> behaves just like decl_type*, except we call 343 /// decl_type::getCanonicalDecl() on construction. 344 /// 345 /// This is useful for hashtables that you want to be keyed on a declaration's 346 /// canonical decl -- if you use CanonicalDeclPtr as the key, you don't need to 347 /// remember to call getCanonicalDecl() everywhere. 348 template <typename decl_type> class CanonicalDeclPtr { 349 public: 350 CanonicalDeclPtr() = default; 351 CanonicalDeclPtr(decl_type *Ptr) 352 : Ptr(Ptr ? Ptr->getCanonicalDecl() : nullptr) {} 353 CanonicalDeclPtr(const CanonicalDeclPtr &) = default; 354 CanonicalDeclPtr &operator=(const CanonicalDeclPtr &) = default; 355 356 operator decl_type *() { return Ptr; } 357 operator const decl_type *() const { return Ptr; } 358 359 decl_type *operator->() { return Ptr; } 360 const decl_type *operator->() const { return Ptr; } 361 362 decl_type &operator*() { return *Ptr; } 363 const decl_type &operator*() const { return *Ptr; } 364 365 friend bool operator==(CanonicalDeclPtr LHS, CanonicalDeclPtr RHS) { 366 return LHS.Ptr == RHS.Ptr; 367 } 368 friend bool operator!=(CanonicalDeclPtr LHS, CanonicalDeclPtr RHS) { 369 return LHS.Ptr != RHS.Ptr; 370 } 371 372 private: 373 friend struct llvm::DenseMapInfo<CanonicalDeclPtr<decl_type>>; 374 friend struct llvm::PointerLikeTypeTraits<CanonicalDeclPtr<decl_type>>; 375 376 decl_type *Ptr = nullptr; 377 }; 378 379 } // namespace clang 380 381 namespace llvm { 382 383 template <typename decl_type> 384 struct DenseMapInfo<clang::CanonicalDeclPtr<decl_type>> { 385 using CanonicalDeclPtr = clang::CanonicalDeclPtr<decl_type>; 386 using BaseInfo = DenseMapInfo<decl_type *>; 387 388 static CanonicalDeclPtr getEmptyKey() { 389 // Construct our CanonicalDeclPtr this way because the regular constructor 390 // would dereference P.Ptr, which is not allowed. 391 CanonicalDeclPtr P; 392 P.Ptr = BaseInfo::getEmptyKey(); 393 return P; 394 } 395 396 static CanonicalDeclPtr getTombstoneKey() { 397 CanonicalDeclPtr P; 398 P.Ptr = BaseInfo::getTombstoneKey(); 399 return P; 400 } 401 402 static unsigned getHashValue(const CanonicalDeclPtr &P) { 403 return BaseInfo::getHashValue(P); 404 } 405 406 static bool isEqual(const CanonicalDeclPtr &LHS, 407 const CanonicalDeclPtr &RHS) { 408 return BaseInfo::isEqual(LHS, RHS); 409 } 410 }; 411 412 template <typename decl_type> 413 struct PointerLikeTypeTraits<clang::CanonicalDeclPtr<decl_type>> { 414 static inline void *getAsVoidPointer(clang::CanonicalDeclPtr<decl_type> P) { 415 return P.Ptr; 416 } 417 static inline clang::CanonicalDeclPtr<decl_type> getFromVoidPointer(void *P) { 418 clang::CanonicalDeclPtr<decl_type> C; 419 C.Ptr = PointerLikeTypeTraits<decl_type *>::getFromVoidPtr(P); 420 return C; 421 } 422 static constexpr int NumLowBitsAvailable = 423 PointerLikeTypeTraits<decl_type *>::NumLowBitsAvailable; 424 }; 425 426 } // namespace llvm 427 428 #endif // LLVM_CLANG_AST_REDECLARABLE_H 429