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 isa<KnownLatest>(Link) || 117 isa<UninitializedLatest>(cast<NotKnownLatest>(Link)); 118 } 119 getPrevious(const decl_type * D)120 decl_type *getPrevious(const decl_type *D) const { 121 if (NotKnownLatest NKL = dyn_cast<NotKnownLatest>(Link)) { 122 if (auto *Prev = dyn_cast<Previous>(NKL)) 123 return static_cast<decl_type *>(Prev); 124 125 // Allocate the generational 'most recent' cache now, if needed. 126 Link = KnownLatest(*reinterpret_cast<const ASTContext *>( 127 cast<UninitializedLatest>(NKL)), 128 const_cast<decl_type *>(D)); 129 } 130 131 return static_cast<decl_type *>(cast<KnownLatest>(Link).get(D)); 132 } 133 setPrevious(decl_type * D)134 void setPrevious(decl_type *D) { 135 assert(!isFirst() && "decl became non-canonical unexpectedly"); 136 Link = Previous(D); 137 } 138 setLatest(decl_type * D)139 void setLatest(decl_type *D) { 140 assert(isFirst() && "decl became canonical unexpectedly"); 141 if (NotKnownLatest NKL = dyn_cast<NotKnownLatest>(Link)) { 142 Link = KnownLatest(*reinterpret_cast<const ASTContext *>( 143 cast<UninitializedLatest>(NKL)), 144 D); 145 } else { 146 auto Latest = cast<KnownLatest>(Link); 147 Latest.set(D); 148 Link = Latest; 149 } 150 } 151 markIncomplete()152 void markIncomplete() { cast<KnownLatest>(Link).markIncomplete(); } 153 getLatestNotUpdated()154 Decl *getLatestNotUpdated() const { 155 assert(isFirst() && "expected a canonical decl"); 156 if (isa<NotKnownLatest>(Link)) 157 return nullptr; 158 return cast<KnownLatest>(Link).getNotUpdated(); 159 } 160 }; 161 PreviousDeclLink(decl_type * D)162 static DeclLink PreviousDeclLink(decl_type *D) { 163 return DeclLink(DeclLink::PreviousLink, D); 164 } 165 LatestDeclLink(const ASTContext & Ctx)166 static DeclLink LatestDeclLink(const ASTContext &Ctx) { 167 return DeclLink(DeclLink::LatestLink, Ctx); 168 } 169 170 /// Points to the next redeclaration in the chain. 171 /// 172 /// If isFirst() is false, this is a link to the previous declaration 173 /// of this same Decl. If isFirst() is true, this is the first 174 /// declaration and Link points to the latest declaration. For example: 175 /// 176 /// #1 int f(int x, int y = 1); // <pointer to #3, true> 177 /// #2 int f(int x = 0, int y); // <pointer to #1, false> 178 /// #3 int f(int x, int y) { return x + y; } // <pointer to #2, false> 179 /// 180 /// If there is only one declaration, it is <pointer to self, true> 181 DeclLink RedeclLink; 182 183 decl_type *First; 184 getNextRedeclaration()185 decl_type *getNextRedeclaration() const { 186 return RedeclLink.getPrevious(static_cast<const decl_type *>(this)); 187 } 188 189 public: 190 friend class ASTDeclMerger; 191 friend class ASTDeclReader; 192 friend class ASTDeclWriter; 193 friend class IncrementalParser; 194 Redeclarable(const ASTContext & Ctx)195 Redeclarable(const ASTContext &Ctx) 196 : RedeclLink(LatestDeclLink(Ctx)), 197 First(static_cast<decl_type *>(this)) {} 198 199 /// Return the previous declaration of this declaration or NULL if this 200 /// is the first declaration. getPreviousDecl()201 decl_type *getPreviousDecl() { 202 if (!RedeclLink.isFirst()) 203 return getNextRedeclaration(); 204 return nullptr; 205 } getPreviousDecl()206 const decl_type *getPreviousDecl() const { 207 return const_cast<decl_type *>( 208 static_cast<const decl_type*>(this))->getPreviousDecl(); 209 } 210 211 /// Return the first declaration of this declaration or itself if this 212 /// is the only declaration. getFirstDecl()213 decl_type *getFirstDecl() { return First; } 214 215 /// Return the first declaration of this declaration or itself if this 216 /// is the only declaration. getFirstDecl()217 const decl_type *getFirstDecl() const { return First; } 218 219 /// True if this is the first declaration in its redeclaration chain. isFirstDecl()220 bool isFirstDecl() const { return RedeclLink.isFirst(); } 221 222 /// Returns the most recent (re)declaration of this declaration. getMostRecentDecl()223 decl_type *getMostRecentDecl() { 224 return getFirstDecl()->getNextRedeclaration(); 225 } 226 227 /// Returns the most recent (re)declaration of this declaration. getMostRecentDecl()228 const decl_type *getMostRecentDecl() const { 229 return getFirstDecl()->getNextRedeclaration(); 230 } 231 232 /// Set the previous declaration. If PrevDecl is NULL, set this as the 233 /// first and only declaration. 234 void setPreviousDecl(decl_type *PrevDecl); 235 236 /// Iterates through all the redeclarations of the same decl. 237 class redecl_iterator { 238 /// Current - The current declaration. 239 decl_type *Current = nullptr; 240 decl_type *Starter = nullptr; 241 bool PassedFirst = false; 242 243 public: 244 using value_type = decl_type *; 245 using reference = decl_type *; 246 using pointer = decl_type *; 247 using iterator_category = std::forward_iterator_tag; 248 using difference_type = std::ptrdiff_t; 249 250 redecl_iterator() = default; redecl_iterator(decl_type * C)251 explicit redecl_iterator(decl_type *C) : Current(C), Starter(C) {} 252 253 reference operator*() const { return Current; } 254 pointer operator->() const { return Current; } 255 256 redecl_iterator& operator++() { 257 assert(Current && "Advancing while iterator has reached end"); 258 // Make sure we don't infinitely loop on an invalid redecl chain. This 259 // should never happen. 260 if (Current->isFirstDecl()) { 261 if (PassedFirst) { 262 assert(0 && "Passed first decl twice, invalid redecl chain!"); 263 Current = nullptr; 264 return *this; 265 } 266 PassedFirst = true; 267 } 268 269 // Get either previous decl or latest decl. 270 decl_type *Next = Current->getNextRedeclaration(); 271 Current = (Next != Starter) ? Next : nullptr; 272 return *this; 273 } 274 275 redecl_iterator operator++(int) { 276 redecl_iterator tmp(*this); 277 ++(*this); 278 return tmp; 279 } 280 281 friend bool operator==(const redecl_iterator &x, const redecl_iterator &y) { 282 return x.Current == y.Current; 283 } 284 friend bool operator!=(const redecl_iterator &x, const redecl_iterator &y) { 285 return x.Current != y.Current; 286 } 287 }; 288 289 using redecl_range = llvm::iterator_range<redecl_iterator>; 290 291 /// Returns an iterator range for all the redeclarations of the same 292 /// decl. It will iterate at least once (when this decl is the only one). redecls()293 redecl_range redecls() const { 294 return redecl_range(redecl_iterator(const_cast<decl_type *>( 295 static_cast<const decl_type *>(this))), 296 redecl_iterator()); 297 } 298 redecls_begin()299 redecl_iterator redecls_begin() const { return redecls().begin(); } redecls_end()300 redecl_iterator redecls_end() const { return redecls().end(); } 301 }; 302 303 /// Get the primary declaration for a declaration from an AST file. That 304 /// will be the first-loaded declaration. 305 Decl *getPrimaryMergedDecl(Decl *D); 306 307 /// Provides common interface for the Decls that cannot be redeclared, 308 /// but can be merged if the same declaration is brought in from multiple 309 /// modules. 310 template<typename decl_type> 311 class Mergeable { 312 public: 313 Mergeable() = default; 314 315 /// Return the first declaration of this declaration or itself if this 316 /// is the only declaration. getFirstDecl()317 decl_type *getFirstDecl() { 318 auto *D = static_cast<decl_type *>(this); 319 if (!D->isFromASTFile()) 320 return D; 321 return cast<decl_type>(getPrimaryMergedDecl(const_cast<decl_type*>(D))); 322 } 323 324 /// Return the first declaration of this declaration or itself if this 325 /// is the only declaration. getFirstDecl()326 const decl_type *getFirstDecl() const { 327 const auto *D = static_cast<const decl_type *>(this); 328 if (!D->isFromASTFile()) 329 return D; 330 return cast<decl_type>(getPrimaryMergedDecl(const_cast<decl_type*>(D))); 331 } 332 333 /// Returns true if this is the first declaration. isFirstDecl()334 bool isFirstDecl() const { return getFirstDecl() == this; } 335 }; 336 337 /// A wrapper class around a pointer that always points to its canonical 338 /// declaration. 339 /// 340 /// CanonicalDeclPtr<decl_type> behaves just like decl_type*, except we call 341 /// decl_type::getCanonicalDecl() on construction. 342 /// 343 /// This is useful for hashtables that you want to be keyed on a declaration's 344 /// canonical decl -- if you use CanonicalDeclPtr as the key, you don't need to 345 /// remember to call getCanonicalDecl() everywhere. 346 template <typename decl_type> class CanonicalDeclPtr { 347 public: 348 CanonicalDeclPtr() = default; CanonicalDeclPtr(decl_type * Ptr)349 CanonicalDeclPtr(decl_type *Ptr) 350 : Ptr(Ptr ? Ptr->getCanonicalDecl() : nullptr) {} 351 CanonicalDeclPtr(const CanonicalDeclPtr &) = default; 352 CanonicalDeclPtr &operator=(const CanonicalDeclPtr &) = default; 353 354 operator decl_type *() { return Ptr; } 355 operator const decl_type *() const { return Ptr; } 356 357 decl_type *operator->() { return Ptr; } 358 const decl_type *operator->() const { return Ptr; } 359 360 decl_type &operator*() { return *Ptr; } 361 const decl_type &operator*() const { return *Ptr; } 362 363 friend bool operator==(CanonicalDeclPtr LHS, CanonicalDeclPtr RHS) { 364 return LHS.Ptr == RHS.Ptr; 365 } 366 friend bool operator!=(CanonicalDeclPtr LHS, CanonicalDeclPtr RHS) { 367 return LHS.Ptr != RHS.Ptr; 368 } 369 370 private: 371 friend struct llvm::DenseMapInfo<CanonicalDeclPtr<decl_type>>; 372 friend struct llvm::PointerLikeTypeTraits<CanonicalDeclPtr<decl_type>>; 373 374 decl_type *Ptr = nullptr; 375 }; 376 377 } // namespace clang 378 379 namespace llvm { 380 381 template <typename decl_type> 382 struct DenseMapInfo<clang::CanonicalDeclPtr<decl_type>> { 383 using CanonicalDeclPtr = clang::CanonicalDeclPtr<decl_type>; 384 using BaseInfo = DenseMapInfo<decl_type *>; 385 386 static CanonicalDeclPtr getEmptyKey() { 387 // Construct our CanonicalDeclPtr this way because the regular constructor 388 // would dereference P.Ptr, which is not allowed. 389 CanonicalDeclPtr P; 390 P.Ptr = BaseInfo::getEmptyKey(); 391 return P; 392 } 393 394 static CanonicalDeclPtr getTombstoneKey() { 395 CanonicalDeclPtr P; 396 P.Ptr = BaseInfo::getTombstoneKey(); 397 return P; 398 } 399 400 static unsigned getHashValue(const CanonicalDeclPtr &P) { 401 return BaseInfo::getHashValue(P); 402 } 403 404 static bool isEqual(const CanonicalDeclPtr &LHS, 405 const CanonicalDeclPtr &RHS) { 406 return BaseInfo::isEqual(LHS, RHS); 407 } 408 }; 409 410 template <typename decl_type> 411 struct PointerLikeTypeTraits<clang::CanonicalDeclPtr<decl_type>> { 412 static inline void *getAsVoidPointer(clang::CanonicalDeclPtr<decl_type> P) { 413 return P.Ptr; 414 } 415 static inline clang::CanonicalDeclPtr<decl_type> getFromVoidPointer(void *P) { 416 clang::CanonicalDeclPtr<decl_type> C; 417 C.Ptr = PointerLikeTypeTraits<decl_type *>::getFromVoidPtr(P); 418 return C; 419 } 420 static constexpr int NumLowBitsAvailable = 421 PointerLikeTypeTraits<decl_type *>::NumLowBitsAvailable; 422 }; 423 424 } // namespace llvm 425 426 #endif // LLVM_CLANG_AST_REDECLARABLE_H 427