1327952Sdim//===- Redeclarable.h - Base for Decls that can be redeclared --*- C++ -*-====// 2198092Srdivacky// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6198092Srdivacky// 7198092Srdivacky//===----------------------------------------------------------------------===// 8198092Srdivacky// 9198092Srdivacky// This file defines the Redeclarable interface. 10198092Srdivacky// 11198092Srdivacky//===----------------------------------------------------------------------===// 12198092Srdivacky 13198092Srdivacky#ifndef LLVM_CLANG_AST_REDECLARABLE_H 14198092Srdivacky#define LLVM_CLANG_AST_REDECLARABLE_H 15198092Srdivacky 16276479Sdim#include "clang/AST/ExternalASTSource.h" 17327952Sdim#include "llvm/ADT/DenseMapInfo.h" 18327952Sdim#include "llvm/ADT/PointerUnion.h" 19327952Sdim#include "llvm/ADT/iterator_range.h" 20199990Srdivacky#include "llvm/Support/Casting.h" 21327952Sdim#include <cassert> 22327952Sdim#include <cstddef> 23199482Srdivacky#include <iterator> 24198092Srdivacky 25198092Srdivackynamespace clang { 26327952Sdim 27296417Sdimclass ASTContext; 28327952Sdimclass Decl; 29198092Srdivacky 30321369Sdim// Some notes on redeclarables: 31321369Sdim// 32321369Sdim// - Every redeclarable is on a circular linked list. 33321369Sdim// 34321369Sdim// - Every decl has a pointer to the first element of the chain _and_ a 35321369Sdim// DeclLink that may point to one of 3 possible states: 36321369Sdim// - the "previous" (temporal) element in the chain 37321369Sdim// - the "latest" (temporal) element in the chain 38341825Sdim// - the "uninitialized-latest" value (when newly-constructed) 39321369Sdim// 40321369Sdim// - The first element is also often called the canonical element. Every 41321369Sdim// element has a pointer to it so that "getCanonical" can be fast. 42321369Sdim// 43321369Sdim// - Most links in the chain point to previous, except the link out of 44321369Sdim// the first; it points to latest. 45321369Sdim// 46321369Sdim// - Elements are called "first", "previous", "latest" or 47321369Sdim// "most-recent" when referring to temporal order: order of addition 48321369Sdim// to the chain. 49321369Sdim// 50341825Sdim// - It's easiest to just ignore the implementation of DeclLink when making 51341825Sdim// sense of the redeclaration chain. 52321369Sdim// 53321369Sdim// - There's also a "definition" link for several types of 54321369Sdim// redeclarable, where only one definition should exist at any given 55321369Sdim// time (and the defn pointer is stored in the decl's "data" which 56321369Sdim// is copied to every element on the chain when it's changed). 57321369Sdim// 58321369Sdim// Here is some ASCII art: 59321369Sdim// 60321369Sdim// "first" "latest" 61321369Sdim// "canonical" "most recent" 62321369Sdim// +------------+ first +--------------+ 63321369Sdim// | | <--------------------------- | | 64321369Sdim// | | | | 65321369Sdim// | | | | 66321369Sdim// | | +--------------+ | | 67321369Sdim// | | first | | | | 68321369Sdim// | | <---- | | | | 69321369Sdim// | | | | | | 70321369Sdim// | @class A | link | @interface A | link | @class A | 71321369Sdim// | seen first | <---- | seen second | <---- | seen third | 72321369Sdim// | | | | | | 73321369Sdim// +------------+ +--------------+ +--------------+ 74321369Sdim// | data | defn | data | defn | data | 75321369Sdim// | | ----> | | <---- | | 76321369Sdim// +------------+ +--------------+ +--------------+ 77321369Sdim// | | ^ ^ 78321369Sdim// | |defn | | 79321369Sdim// | link +-----+ | 80321369Sdim// +-->-------------------------------------------+ 81321369Sdim 82341825Sdim/// Provides common interface for the Decls that can be redeclared. 83198092Srdivackytemplate<typename decl_type> 84198092Srdivackyclass Redeclarable { 85198092Srdivackyprotected: 86239462Sdim class DeclLink { 87276479Sdim /// A pointer to a known latest declaration, either statically known or 88276479Sdim /// generationally updated as decls are added by an external source. 89327952Sdim using KnownLatest = 90327952Sdim LazyGenerationalUpdatePtr<const Decl *, Decl *, 91327952Sdim &ExternalASTSource::CompleteRedeclChain>; 92276479Sdim 93296417Sdim /// We store a pointer to the ASTContext in the UninitializedLatest 94296417Sdim /// pointer, but to avoid circular type dependencies when we steal the low 95296417Sdim /// bits of this pointer, we use a raw void* here. 96327952Sdim using UninitializedLatest = const void *; 97296417Sdim 98327952Sdim using Previous = Decl *; 99276479Sdim 100276479Sdim /// A pointer to either an uninitialized latest declaration (where either 101276479Sdim /// we've not yet set the previous decl or there isn't one), or to a known 102276479Sdim /// previous declaration. 103327952Sdim using NotKnownLatest = llvm::PointerUnion<Previous, UninitializedLatest>; 104276479Sdim 105341825Sdim mutable llvm::PointerUnion<NotKnownLatest, KnownLatest> Link; 106276479Sdim 107239462Sdim public: 108276479Sdim enum PreviousTag { PreviousLink }; 109276479Sdim enum LatestTag { LatestLink }; 110198092Srdivacky 111276479Sdim DeclLink(LatestTag, const ASTContext &Ctx) 112341825Sdim : Link(NotKnownLatest(reinterpret_cast<UninitializedLatest>(&Ctx))) {} 113341825Sdim DeclLink(PreviousTag, decl_type *D) : Link(NotKnownLatest(Previous(D))) {} 114276479Sdim 115341825Sdim bool isFirst() const { 116341825Sdim return Link.is<KnownLatest>() || 117276479Sdim // FIXME: 'template' is required on the next line due to an 118276479Sdim // apparent clang bug. 119341825Sdim Link.get<NotKnownLatest>().template is<UninitializedLatest>(); 120276479Sdim } 121276479Sdim 122341825Sdim decl_type *getPrevious(const decl_type *D) const { 123341825Sdim if (Link.is<NotKnownLatest>()) { 124341825Sdim NotKnownLatest NKL = Link.get<NotKnownLatest>(); 125276479Sdim if (NKL.is<Previous>()) 126276479Sdim return static_cast<decl_type*>(NKL.get<Previous>()); 127276479Sdim 128276479Sdim // Allocate the generational 'most recent' cache now, if needed. 129341825Sdim Link = KnownLatest(*reinterpret_cast<const ASTContext *>( 130296417Sdim NKL.get<UninitializedLatest>()), 131276479Sdim const_cast<decl_type *>(D)); 132276479Sdim } 133276479Sdim 134341825Sdim return static_cast<decl_type*>(Link.get<KnownLatest>().get(D)); 135276479Sdim } 136276479Sdim 137276479Sdim void setPrevious(decl_type *D) { 138341825Sdim assert(!isFirst() && "decl became non-canonical unexpectedly"); 139341825Sdim Link = Previous(D); 140276479Sdim } 141276479Sdim 142276479Sdim void setLatest(decl_type *D) { 143341825Sdim assert(isFirst() && "decl became canonical unexpectedly"); 144341825Sdim if (Link.is<NotKnownLatest>()) { 145341825Sdim NotKnownLatest NKL = Link.get<NotKnownLatest>(); 146341825Sdim Link = KnownLatest(*reinterpret_cast<const ASTContext *>( 147296417Sdim NKL.get<UninitializedLatest>()), 148296417Sdim D); 149276479Sdim } else { 150341825Sdim auto Latest = Link.get<KnownLatest>(); 151276479Sdim Latest.set(D); 152341825Sdim Link = Latest; 153276479Sdim } 154276479Sdim } 155276479Sdim 156341825Sdim void markIncomplete() { Link.get<KnownLatest>().markIncomplete(); } 157288943Sdim 158288943Sdim Decl *getLatestNotUpdated() const { 159341825Sdim assert(isFirst() && "expected a canonical decl"); 160341825Sdim if (Link.is<NotKnownLatest>()) 161288943Sdim return nullptr; 162341825Sdim return Link.get<KnownLatest>().getNotUpdated(); 163288943Sdim } 164198092Srdivacky }; 165198092Srdivacky 166239462Sdim static DeclLink PreviousDeclLink(decl_type *D) { 167276479Sdim return DeclLink(DeclLink::PreviousLink, D); 168239462Sdim } 169198092Srdivacky 170276479Sdim static DeclLink LatestDeclLink(const ASTContext &Ctx) { 171276479Sdim return DeclLink(DeclLink::LatestLink, Ctx); 172239462Sdim } 173198092Srdivacky 174341825Sdim /// Points to the next redeclaration in the chain. 175198092Srdivacky /// 176341825Sdim /// If isFirst() is false, this is a link to the previous declaration 177341825Sdim /// of this same Decl. If isFirst() is true, this is the first 178198092Srdivacky /// declaration and Link points to the latest declaration. For example: 179198092Srdivacky /// 180198092Srdivacky /// #1 int f(int x, int y = 1); // <pointer to #3, true> 181198092Srdivacky /// #2 int f(int x = 0, int y); // <pointer to #1, false> 182198092Srdivacky /// #3 int f(int x, int y) { return x + y; } // <pointer to #2, false> 183198092Srdivacky /// 184198092Srdivacky /// If there is only one declaration, it is <pointer to self, true> 185198092Srdivacky DeclLink RedeclLink; 186327952Sdim 187288943Sdim decl_type *First; 188198092Srdivacky 189276479Sdim decl_type *getNextRedeclaration() const { 190341825Sdim return RedeclLink.getPrevious(static_cast<const decl_type *>(this)); 191276479Sdim } 192276479Sdim 193198092Srdivackypublic: 194327952Sdim friend class ASTDeclReader; 195327952Sdim friend class ASTDeclWriter; 196198092Srdivacky 197327952Sdim Redeclarable(const ASTContext &Ctx) 198327952Sdim : RedeclLink(LatestDeclLink(Ctx)), 199327952Sdim First(static_cast<decl_type *>(this)) {} 200327952Sdim 201341825Sdim /// Return the previous declaration of this declaration or NULL if this 202198092Srdivacky /// is the first declaration. 203234353Sdim decl_type *getPreviousDecl() { 204341825Sdim if (!RedeclLink.isFirst()) 205276479Sdim return getNextRedeclaration(); 206276479Sdim return nullptr; 207198092Srdivacky } 208234353Sdim const decl_type *getPreviousDecl() const { 209198092Srdivacky return const_cast<decl_type *>( 210234353Sdim static_cast<const decl_type*>(this))->getPreviousDecl(); 211198092Srdivacky } 212198092Srdivacky 213341825Sdim /// Return the first declaration of this declaration or itself if this 214198092Srdivacky /// is the only declaration. 215288943Sdim decl_type *getFirstDecl() { return First; } 216198092Srdivacky 217341825Sdim /// Return the first declaration of this declaration or itself if this 218198092Srdivacky /// is the only declaration. 219288943Sdim const decl_type *getFirstDecl() const { return First; } 220198092Srdivacky 221341825Sdim /// True if this is the first declaration in its redeclaration chain. 222341825Sdim bool isFirstDecl() const { return RedeclLink.isFirst(); } 223210299Sed 224341825Sdim /// Returns the most recent (re)declaration of this declaration. 225234353Sdim decl_type *getMostRecentDecl() { 226276479Sdim return getFirstDecl()->getNextRedeclaration(); 227199990Srdivacky } 228199990Srdivacky 229341825Sdim /// Returns the most recent (re)declaration of this declaration. 230234353Sdim const decl_type *getMostRecentDecl() const { 231276479Sdim return getFirstDecl()->getNextRedeclaration(); 232198893Srdivacky } 233276479Sdim 234341825Sdim /// Set the previous declaration. If PrevDecl is NULL, set this as the 235198092Srdivacky /// first and only declaration. 236261991Sdim void setPreviousDecl(decl_type *PrevDecl); 237198092Srdivacky 238341825Sdim /// Iterates through all the redeclarations of the same decl. 239198092Srdivacky class redecl_iterator { 240198092Srdivacky /// Current - The current declaration. 241327952Sdim decl_type *Current = nullptr; 242198092Srdivacky decl_type *Starter; 243327952Sdim bool PassedFirst = false; 244198092Srdivacky 245198092Srdivacky public: 246327952Sdim using value_type = decl_type *; 247327952Sdim using reference = decl_type *; 248327952Sdim using pointer = decl_type *; 249327952Sdim using iterator_category = std::forward_iterator_tag; 250327952Sdim using difference_type = std::ptrdiff_t; 251198092Srdivacky 252327952Sdim redecl_iterator() = default; 253327952Sdim explicit redecl_iterator(decl_type *C) : Current(C), Starter(C) {} 254198092Srdivacky 255198092Srdivacky reference operator*() const { return Current; } 256198092Srdivacky pointer operator->() const { return Current; } 257198092Srdivacky 258198092Srdivacky redecl_iterator& operator++() { 259198092Srdivacky assert(Current && "Advancing while iterator has reached end"); 260234353Sdim // Sanity check to avoid infinite loop on invalid redecl chain. 261261991Sdim if (Current->isFirstDecl()) { 262234353Sdim if (PassedFirst) { 263234353Sdim assert(0 && "Passed first decl twice, invalid redecl chain!"); 264276479Sdim Current = nullptr; 265234353Sdim return *this; 266234353Sdim } 267234353Sdim PassedFirst = true; 268234353Sdim } 269234353Sdim 270198092Srdivacky // Get either previous decl or latest decl. 271276479Sdim decl_type *Next = Current->getNextRedeclaration(); 272276479Sdim Current = (Next != Starter) ? Next : nullptr; 273198092Srdivacky return *this; 274198092Srdivacky } 275198092Srdivacky 276198092Srdivacky redecl_iterator operator++(int) { 277198092Srdivacky redecl_iterator tmp(*this); 278198092Srdivacky ++(*this); 279198092Srdivacky return tmp; 280198092Srdivacky } 281198092Srdivacky 282198092Srdivacky friend bool operator==(redecl_iterator x, redecl_iterator y) { 283198092Srdivacky return x.Current == y.Current; 284198092Srdivacky } 285198092Srdivacky friend bool operator!=(redecl_iterator x, redecl_iterator y) { 286198092Srdivacky return x.Current != y.Current; 287198092Srdivacky } 288198092Srdivacky }; 289198092Srdivacky 290327952Sdim using redecl_range = llvm::iterator_range<redecl_iterator>; 291276479Sdim 292341825Sdim /// Returns an iterator range for all the redeclarations of the same 293276479Sdim /// decl. It will iterate at least once (when this decl is the only one). 294276479Sdim redecl_range redecls() const { 295276479Sdim return redecl_range(redecl_iterator(const_cast<decl_type *>( 296276479Sdim static_cast<const decl_type *>(this))), 297276479Sdim redecl_iterator()); 298198092Srdivacky } 299212904Sdim 300276479Sdim redecl_iterator redecls_begin() const { return redecls().begin(); } 301276479Sdim redecl_iterator redecls_end() const { return redecls().end(); } 302198092Srdivacky}; 303198092Srdivacky 304341825Sdim/// Get the primary declaration for a declaration from an AST file. That 305261991Sdim/// will be the first-loaded declaration. 306261991SdimDecl *getPrimaryMergedDecl(Decl *D); 307261991Sdim 308341825Sdim/// Provides common interface for the Decls that cannot be redeclared, 309261991Sdim/// but can be merged if the same declaration is brought in from multiple 310261991Sdim/// modules. 311261991Sdimtemplate<typename decl_type> 312261991Sdimclass Mergeable { 313261991Sdimpublic: 314327952Sdim Mergeable() = default; 315261991Sdim 316341825Sdim /// Return the first declaration of this declaration or itself if this 317261991Sdim /// is the only declaration. 318261991Sdim decl_type *getFirstDecl() { 319341825Sdim auto *D = static_cast<decl_type *>(this); 320261991Sdim if (!D->isFromASTFile()) 321261991Sdim return D; 322261991Sdim return cast<decl_type>(getPrimaryMergedDecl(const_cast<decl_type*>(D))); 323261991Sdim } 324261991Sdim 325341825Sdim /// Return the first declaration of this declaration or itself if this 326261991Sdim /// is the only declaration. 327261991Sdim const decl_type *getFirstDecl() const { 328341825Sdim const auto *D = static_cast<const decl_type *>(this); 329261991Sdim if (!D->isFromASTFile()) 330261991Sdim return D; 331261991Sdim return cast<decl_type>(getPrimaryMergedDecl(const_cast<decl_type*>(D))); 332261991Sdim } 333261991Sdim 334341825Sdim /// Returns true if this is the first declaration. 335261991Sdim bool isFirstDecl() const { return getFirstDecl() == this; } 336261991Sdim}; 337261991Sdim 338314564Sdim/// A wrapper class around a pointer that always points to its canonical 339314564Sdim/// declaration. 340314564Sdim/// 341314564Sdim/// CanonicalDeclPtr<decl_type> behaves just like decl_type*, except we call 342314564Sdim/// decl_type::getCanonicalDecl() on construction. 343314564Sdim/// 344314564Sdim/// This is useful for hashtables that you want to be keyed on a declaration's 345314564Sdim/// canonical decl -- if you use CanonicalDeclPtr as the key, you don't need to 346314564Sdim/// remember to call getCanonicalDecl() everywhere. 347314564Sdimtemplate <typename decl_type> class CanonicalDeclPtr { 348314564Sdimpublic: 349327952Sdim CanonicalDeclPtr() = default; 350314564Sdim CanonicalDeclPtr(decl_type *Ptr) 351314564Sdim : Ptr(Ptr ? Ptr->getCanonicalDecl() : nullptr) {} 352314564Sdim CanonicalDeclPtr(const CanonicalDeclPtr &) = default; 353314564Sdim CanonicalDeclPtr &operator=(const CanonicalDeclPtr &) = default; 354198092Srdivacky 355314564Sdim operator decl_type *() { return Ptr; } 356314564Sdim operator const decl_type *() const { return Ptr; } 357314564Sdim 358314564Sdim decl_type *operator->() { return Ptr; } 359314564Sdim const decl_type *operator->() const { return Ptr; } 360314564Sdim 361314564Sdim decl_type &operator*() { return *Ptr; } 362314564Sdim const decl_type &operator*() const { return *Ptr; } 363314564Sdim 364353358Sdim friend bool operator==(CanonicalDeclPtr LHS, CanonicalDeclPtr RHS) { 365353358Sdim return LHS.Ptr == RHS.Ptr; 366353358Sdim } 367353358Sdim friend bool operator!=(CanonicalDeclPtr LHS, CanonicalDeclPtr RHS) { 368353358Sdim return LHS.Ptr != RHS.Ptr; 369353358Sdim } 370353358Sdim 371314564Sdimprivate: 372314564Sdim friend struct llvm::DenseMapInfo<CanonicalDeclPtr<decl_type>>; 373314564Sdim 374327952Sdim decl_type *Ptr = nullptr; 375314564Sdim}; 376327952Sdim 377314564Sdim} // namespace clang 378314564Sdim 379314564Sdimnamespace llvm { 380327952Sdim 381314564Sdimtemplate <typename decl_type> 382314564Sdimstruct DenseMapInfo<clang::CanonicalDeclPtr<decl_type>> { 383314564Sdim using CanonicalDeclPtr = clang::CanonicalDeclPtr<decl_type>; 384314564Sdim using BaseInfo = DenseMapInfo<decl_type *>; 385314564Sdim 386314564Sdim static CanonicalDeclPtr getEmptyKey() { 387314564Sdim // Construct our CanonicalDeclPtr this way because the regular constructor 388314564Sdim // would dereference P.Ptr, which is not allowed. 389314564Sdim CanonicalDeclPtr P; 390314564Sdim P.Ptr = BaseInfo::getEmptyKey(); 391314564Sdim return P; 392314564Sdim } 393314564Sdim 394314564Sdim static CanonicalDeclPtr getTombstoneKey() { 395314564Sdim CanonicalDeclPtr P; 396314564Sdim P.Ptr = BaseInfo::getTombstoneKey(); 397314564Sdim return P; 398314564Sdim } 399314564Sdim 400314564Sdim static unsigned getHashValue(const CanonicalDeclPtr &P) { 401314564Sdim return BaseInfo::getHashValue(P); 402314564Sdim } 403314564Sdim 404314564Sdim static bool isEqual(const CanonicalDeclPtr &LHS, 405314564Sdim const CanonicalDeclPtr &RHS) { 406314564Sdim return BaseInfo::isEqual(LHS, RHS); 407314564Sdim } 408314564Sdim}; 409327952Sdim 410314564Sdim} // namespace llvm 411314564Sdim 412327952Sdim#endif // LLVM_CLANG_AST_REDECLARABLE_H 413