1 //===- Redeclarable.h - Base for Decls that can be redeclared --*- C++ -*-====// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file defines the Redeclarable interface. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_CLANG_AST_REDECLARABLE_H 15 #define LLVM_CLANG_AST_REDECLARABLE_H 16 17 #include "clang/AST/ExternalASTSource.h" 18 #include "llvm/ADT/DenseMapInfo.h" 19 #include "llvm/ADT/PointerUnion.h" 20 #include "llvm/ADT/iterator_range.h" 21 #include "llvm/Support/Casting.h" 22 #include <cassert> 23 #include <cstddef> 24 #include <iterator> 25 26 namespace clang { 27 28 class ASTContext; 29 class Decl; 30 31 // Some notes on redeclarables: 32 // 33 // - Every redeclarable is on a circular linked list. 34 // 35 // - Every decl has a pointer to the first element of the chain _and_ a 36 // DeclLink that may point to one of 3 possible states: 37 // - the "previous" (temporal) element in the chain 38 // - the "latest" (temporal) element in the chain 39 // - the "uninitialized-latest" value (when newly-constructed) 40 // 41 // - The first element is also often called the canonical element. Every 42 // element has a pointer to it so that "getCanonical" can be fast. 43 // 44 // - Most links in the chain point to previous, except the link out of 45 // the first; it points to latest. 46 // 47 // - Elements are called "first", "previous", "latest" or 48 // "most-recent" when referring to temporal order: order of addition 49 // to the chain. 50 // 51 // - It's easiest to just ignore the implementation of DeclLink when making 52 // sense of the redeclaration chain. 53 // 54 // - There's also a "definition" link for several types of 55 // redeclarable, where only one definition should exist at any given 56 // time (and the defn pointer is stored in the decl's "data" which 57 // is copied to every element on the chain when it's changed). 58 // 59 // Here is some ASCII art: 60 // 61 // "first" "latest" 62 // "canonical" "most recent" 63 // +------------+ first +--------------+ 64 // | | <--------------------------- | | 65 // | | | | 66 // | | | | 67 // | | +--------------+ | | 68 // | | first | | | | 69 // | | <---- | | | | 70 // | | | | | | 71 // | @class A | link | @interface A | link | @class A | 72 // | seen first | <---- | seen second | <---- | seen third | 73 // | | | | | | 74 // +------------+ +--------------+ +--------------+ 75 // | data | defn | data | defn | data | 76 // | | ----> | | <---- | | 77 // +------------+ +--------------+ +--------------+ 78 // | | ^ ^ 79 // | |defn | | 80 // | link +-----+ | 81 // +-->-------------------------------------------+ 82 83 /// Provides common interface for the Decls that can be redeclared. 84 template<typename decl_type> 85 class Redeclarable { 86 protected: 87 class DeclLink { 88 /// A pointer to a known latest declaration, either statically known or 89 /// generationally updated as decls are added by an external source. 90 using KnownLatest = 91 LazyGenerationalUpdatePtr<const Decl *, Decl *, 92 &ExternalASTSource::CompleteRedeclChain>; 93 94 /// We store a pointer to the ASTContext in the UninitializedLatest 95 /// pointer, but to avoid circular type dependencies when we steal the low 96 /// bits of this pointer, we use a raw void* here. 97 using UninitializedLatest = const void *; 98 99 using Previous = Decl *; 100 101 /// A pointer to either an uninitialized latest declaration (where either 102 /// we've not yet set the previous decl or there isn't one), or to a known 103 /// previous declaration. 104 using NotKnownLatest = llvm::PointerUnion<Previous, UninitializedLatest>; 105 106 mutable llvm::PointerUnion<NotKnownLatest, KnownLatest> Link; 107 108 public: 109 enum PreviousTag { PreviousLink }; 110 enum LatestTag { LatestLink }; 111 DeclLink(LatestTag,const ASTContext & Ctx)112 DeclLink(LatestTag, const ASTContext &Ctx) 113 : Link(NotKnownLatest(reinterpret_cast<UninitializedLatest>(&Ctx))) {} DeclLink(PreviousTag,decl_type * D)114 DeclLink(PreviousTag, decl_type *D) : Link(NotKnownLatest(Previous(D))) {} 115 isFirst()116 bool isFirst() const { 117 return Link.is<KnownLatest>() || 118 // FIXME: 'template' is required on the next line due to an 119 // apparent clang bug. 120 Link.get<NotKnownLatest>().template is<UninitializedLatest>(); 121 } 122 getPrevious(const decl_type * D)123 decl_type *getPrevious(const decl_type *D) const { 124 if (Link.is<NotKnownLatest>()) { 125 NotKnownLatest NKL = Link.get<NotKnownLatest>(); 126 if (NKL.is<Previous>()) 127 return static_cast<decl_type*>(NKL.get<Previous>()); 128 129 // Allocate the generational 'most recent' cache now, if needed. 130 Link = KnownLatest(*reinterpret_cast<const ASTContext *>( 131 NKL.get<UninitializedLatest>()), 132 const_cast<decl_type *>(D)); 133 } 134 135 return static_cast<decl_type*>(Link.get<KnownLatest>().get(D)); 136 } 137 setPrevious(decl_type * D)138 void setPrevious(decl_type *D) { 139 assert(!isFirst() && "decl became non-canonical unexpectedly"); 140 Link = Previous(D); 141 } 142 setLatest(decl_type * D)143 void setLatest(decl_type *D) { 144 assert(isFirst() && "decl became canonical unexpectedly"); 145 if (Link.is<NotKnownLatest>()) { 146 NotKnownLatest NKL = Link.get<NotKnownLatest>(); 147 Link = KnownLatest(*reinterpret_cast<const ASTContext *>( 148 NKL.get<UninitializedLatest>()), 149 D); 150 } else { 151 auto Latest = Link.get<KnownLatest>(); 152 Latest.set(D); 153 Link = Latest; 154 } 155 } 156 markIncomplete()157 void markIncomplete() { Link.get<KnownLatest>().markIncomplete(); } 158 getLatestNotUpdated()159 Decl *getLatestNotUpdated() const { 160 assert(isFirst() && "expected a canonical decl"); 161 if (Link.is<NotKnownLatest>()) 162 return nullptr; 163 return Link.get<KnownLatest>().getNotUpdated(); 164 } 165 }; 166 PreviousDeclLink(decl_type * D)167 static DeclLink PreviousDeclLink(decl_type *D) { 168 return DeclLink(DeclLink::PreviousLink, D); 169 } 170 LatestDeclLink(const ASTContext & Ctx)171 static DeclLink LatestDeclLink(const ASTContext &Ctx) { 172 return DeclLink(DeclLink::LatestLink, Ctx); 173 } 174 175 /// Points to the next redeclaration in the chain. 176 /// 177 /// If isFirst() is false, this is a link to the previous declaration 178 /// of this same Decl. If isFirst() is true, this is the first 179 /// declaration and Link points to the latest declaration. For example: 180 /// 181 /// #1 int f(int x, int y = 1); // <pointer to #3, true> 182 /// #2 int f(int x = 0, int y); // <pointer to #1, false> 183 /// #3 int f(int x, int y) { return x + y; } // <pointer to #2, false> 184 /// 185 /// If there is only one declaration, it is <pointer to self, true> 186 DeclLink RedeclLink; 187 188 decl_type *First; 189 getNextRedeclaration()190 decl_type *getNextRedeclaration() const { 191 return RedeclLink.getPrevious(static_cast<const decl_type *>(this)); 192 } 193 194 public: 195 friend class ASTDeclReader; 196 friend class ASTDeclWriter; 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; 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 // 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). redecls()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 redecls_begin()301 redecl_iterator redecls_begin() const { return redecls().begin(); } redecls_end()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. getFirstDecl()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. getFirstDecl()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. isFirstDecl()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; CanonicalDeclPtr(decl_type * Ptr)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 private: 366 friend struct llvm::DenseMapInfo<CanonicalDeclPtr<decl_type>>; 367 368 decl_type *Ptr = nullptr; 369 }; 370 371 } // namespace clang 372 373 namespace llvm { 374 375 template <typename decl_type> 376 struct DenseMapInfo<clang::CanonicalDeclPtr<decl_type>> { 377 using CanonicalDeclPtr = clang::CanonicalDeclPtr<decl_type>; 378 using BaseInfo = DenseMapInfo<decl_type *>; 379 380 static CanonicalDeclPtr getEmptyKey() { 381 // Construct our CanonicalDeclPtr this way because the regular constructor 382 // would dereference P.Ptr, which is not allowed. 383 CanonicalDeclPtr P; 384 P.Ptr = BaseInfo::getEmptyKey(); 385 return P; 386 } 387 388 static CanonicalDeclPtr getTombstoneKey() { 389 CanonicalDeclPtr P; 390 P.Ptr = BaseInfo::getTombstoneKey(); 391 return P; 392 } 393 394 static unsigned getHashValue(const CanonicalDeclPtr &P) { 395 return BaseInfo::getHashValue(P); 396 } 397 398 static bool isEqual(const CanonicalDeclPtr &LHS, 399 const CanonicalDeclPtr &RHS) { 400 return BaseInfo::isEqual(LHS, RHS); 401 } 402 }; 403 404 } // namespace llvm 405 406 #endif // LLVM_CLANG_AST_REDECLARABLE_H 407