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