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 25namespace clang { 26 27class ASTContext; 28class 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. 83template<typename decl_type> 84class Redeclarable { 85protected: 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 193public: 194 friend class ASTDeclReader; 195 friend class ASTDeclWriter; 196 197 Redeclarable(const ASTContext &Ctx) 198 : RedeclLink(LatestDeclLink(Ctx)), 199 First(static_cast<decl_type *>(this)) {} 200 201 /// Return the previous declaration of this declaration or NULL if this 202 /// is the first declaration. 203 decl_type *getPreviousDecl() { 204 if (!RedeclLink.isFirst()) 205 return getNextRedeclaration(); 206 return nullptr; 207 } 208 const decl_type *getPreviousDecl() const { 209 return const_cast<decl_type *>( 210 static_cast<const decl_type*>(this))->getPreviousDecl(); 211 } 212 213 /// Return the first declaration of this declaration or itself if this 214 /// is the only declaration. 215 decl_type *getFirstDecl() { return First; } 216 217 /// Return the first declaration of this declaration or itself if this 218 /// is the only declaration. 219 const decl_type *getFirstDecl() const { return First; } 220 221 /// True if this is the first declaration in its redeclaration chain. 222 bool isFirstDecl() const { return RedeclLink.isFirst(); } 223 224 /// Returns the most recent (re)declaration of this declaration. 225 decl_type *getMostRecentDecl() { 226 return getFirstDecl()->getNextRedeclaration(); 227 } 228 229 /// Returns the most recent (re)declaration of this declaration. 230 const decl_type *getMostRecentDecl() const { 231 return getFirstDecl()->getNextRedeclaration(); 232 } 233 234 /// Set the previous declaration. If PrevDecl is NULL, set this as the 235 /// first and only declaration. 236 void setPreviousDecl(decl_type *PrevDecl); 237 238 /// Iterates through all the redeclarations of the same decl. 239 class redecl_iterator { 240 /// Current - The current declaration. 241 decl_type *Current = nullptr; 242 decl_type *Starter; 243 bool PassedFirst = false; 244 245 public: 246 using value_type = decl_type *; 247 using reference = decl_type *; 248 using pointer = decl_type *; 249 using iterator_category = std::forward_iterator_tag; 250 using difference_type = std::ptrdiff_t; 251 252 redecl_iterator() = default; 253 explicit redecl_iterator(decl_type *C) : Current(C), Starter(C) {} 254 255 reference operator*() const { return Current; } 256 pointer operator->() const { return Current; } 257 258 redecl_iterator& operator++() { 259 assert(Current && "Advancing while iterator has reached end"); 260 // Sanity check to avoid infinite loop on invalid redecl chain. 261 if (Current->isFirstDecl()) { 262 if (PassedFirst) { 263 assert(0 && "Passed first decl twice, invalid redecl chain!"); 264 Current = nullptr; 265 return *this; 266 } 267 PassedFirst = true; 268 } 269 270 // Get either previous decl or latest decl. 271 decl_type *Next = Current->getNextRedeclaration(); 272 Current = (Next != Starter) ? Next : nullptr; 273 return *this; 274 } 275 276 redecl_iterator operator++(int) { 277 redecl_iterator tmp(*this); 278 ++(*this); 279 return tmp; 280 } 281 282 friend bool operator==(redecl_iterator x, redecl_iterator y) { 283 return x.Current == y.Current; 284 } 285 friend bool operator!=(redecl_iterator x, redecl_iterator y) { 286 return x.Current != y.Current; 287 } 288 }; 289 290 using redecl_range = llvm::iterator_range<redecl_iterator>; 291 292 /// Returns an iterator range for all the redeclarations of the same 293 /// decl. It will iterate at least once (when this decl is the only one). 294 redecl_range redecls() const { 295 return redecl_range(redecl_iterator(const_cast<decl_type *>( 296 static_cast<const decl_type *>(this))), 297 redecl_iterator()); 298 } 299 300 redecl_iterator redecls_begin() const { return redecls().begin(); } 301 redecl_iterator redecls_end() const { return redecls().end(); } 302}; 303 304/// Get the primary declaration for a declaration from an AST file. That 305/// will be the first-loaded declaration. 306Decl *getPrimaryMergedDecl(Decl *D); 307 308/// Provides common interface for the Decls that cannot be redeclared, 309/// but can be merged if the same declaration is brought in from multiple 310/// modules. 311template<typename decl_type> 312class Mergeable { 313public: 314 Mergeable() = default; 315 316 /// Return the first declaration of this declaration or itself if this 317 /// is the only declaration. 318 decl_type *getFirstDecl() { 319 auto *D = static_cast<decl_type *>(this); 320 if (!D->isFromASTFile()) 321 return D; 322 return cast<decl_type>(getPrimaryMergedDecl(const_cast<decl_type*>(D))); 323 } 324 325 /// Return the first declaration of this declaration or itself if this 326 /// is the only declaration. 327 const decl_type *getFirstDecl() const { 328 const auto *D = static_cast<const decl_type *>(this); 329 if (!D->isFromASTFile()) 330 return D; 331 return cast<decl_type>(getPrimaryMergedDecl(const_cast<decl_type*>(D))); 332 } 333 334 /// Returns true if this is the first declaration. 335 bool isFirstDecl() const { return getFirstDecl() == this; } 336}; 337 338/// A wrapper class around a pointer that always points to its canonical 339/// declaration. 340/// 341/// CanonicalDeclPtr<decl_type> behaves just like decl_type*, except we call 342/// decl_type::getCanonicalDecl() on construction. 343/// 344/// This is useful for hashtables that you want to be keyed on a declaration's 345/// canonical decl -- if you use CanonicalDeclPtr as the key, you don't need to 346/// remember to call getCanonicalDecl() everywhere. 347template <typename decl_type> class CanonicalDeclPtr { 348public: 349 CanonicalDeclPtr() = default; 350 CanonicalDeclPtr(decl_type *Ptr) 351 : Ptr(Ptr ? Ptr->getCanonicalDecl() : nullptr) {} 352 CanonicalDeclPtr(const CanonicalDeclPtr &) = default; 353 CanonicalDeclPtr &operator=(const CanonicalDeclPtr &) = default; 354 355 operator decl_type *() { return Ptr; } 356 operator const decl_type *() const { return Ptr; } 357 358 decl_type *operator->() { return Ptr; } 359 const decl_type *operator->() const { return Ptr; } 360 361 decl_type &operator*() { return *Ptr; } 362 const decl_type &operator*() const { return *Ptr; } 363 364 friend bool operator==(CanonicalDeclPtr LHS, CanonicalDeclPtr RHS) { 365 return LHS.Ptr == RHS.Ptr; 366 } 367 friend bool operator!=(CanonicalDeclPtr LHS, CanonicalDeclPtr RHS) { 368 return LHS.Ptr != RHS.Ptr; 369 } 370 371private: 372 friend struct llvm::DenseMapInfo<CanonicalDeclPtr<decl_type>>; 373 374 decl_type *Ptr = nullptr; 375}; 376 377} // namespace clang 378 379namespace llvm { 380 381template <typename decl_type> 382struct 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} // namespace llvm 411 412#endif // LLVM_CLANG_AST_REDECLARABLE_H 413