1 //===-- Redeclarable.h - Base for Decls that can be redeclared -*- C++ -*-====//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the Redeclarable interface.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_CLANG_AST_REDECLARABLE_H
15 #define LLVM_CLANG_AST_REDECLARABLE_H
17 #include "clang/AST/ExternalASTSource.h"
18 #include "llvm/Support/Casting.h"
24 // Some notes on redeclarables:
26 // - Every redeclarable is on a circular linked list.
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)
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.
37 // - Most links in the chain point to previous, except the link out of
38 // the first; it points to latest.
40 // - Elements are called "first", "previous", "latest" or
41 // "most-recent" when referring to temporal order: order of addition
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.
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).
54 // Here is some ASCII art:
57 // "canonical" "most recent"
58 // +------------+ first +--------------+
59 // | | <--------------------------- | |
62 // | | +--------------+ | |
66 // | @class A | link | @interface A | link | @class A |
67 // | seen first | <---- | seen second | <---- | seen third |
69 // +------------+ +--------------+ +--------------+
70 // | data | defn | data | defn | data |
71 // | | ----> | | <---- | |
72 // +------------+ +--------------+ +--------------+
76 // +-->-------------------------------------------+
78 /// \brief Provides common interface for the Decls that can be redeclared.
79 template<typename decl_type>
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>
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;
94 typedef Decl *Previous;
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;
101 mutable llvm::PointerUnion<NotKnownLatest, KnownLatest> Next;
104 enum PreviousTag { PreviousLink };
105 enum LatestTag { LatestLink };
107 DeclLink(LatestTag, const ASTContext &Ctx)
108 : Next(NotKnownLatest(reinterpret_cast<UninitializedLatest>(&Ctx))) {}
109 DeclLink(PreviousTag, decl_type *D)
110 : Next(NotKnownLatest(Previous(D))) {}
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>();
119 bool NextIsLatest() const { return !NextIsPrevious(); }
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>());
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));
133 return static_cast<decl_type*>(Next.get<KnownLatest>().get(D));
136 void setPrevious(decl_type *D) {
137 assert(NextIsPrevious() && "decl became non-canonical unexpectedly");
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>()),
149 auto Latest = Next.get<KnownLatest>();
155 void markIncomplete() { Next.get<KnownLatest>().markIncomplete(); }
157 Decl *getLatestNotUpdated() const {
158 assert(NextIsLatest() && "expected a canonical decl");
159 if (Next.is<NotKnownLatest>())
161 return Next.get<KnownLatest>().getNotUpdated();
165 static DeclLink PreviousDeclLink(decl_type *D) {
166 return DeclLink(DeclLink::PreviousLink, D);
169 static DeclLink LatestDeclLink(const ASTContext &Ctx) {
170 return DeclLink(DeclLink::LatestLink, Ctx);
173 /// \brief Points to the next redeclaration in the chain.
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:
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>
183 /// If there is only one declaration, it is <pointer to self, true>
187 decl_type *getNextRedeclaration() const {
188 return RedeclLink.getNext(static_cast<const decl_type *>(this));
192 Redeclarable(const ASTContext &Ctx)
193 : RedeclLink(LatestDeclLink(Ctx)), First(static_cast<decl_type *>(this)) {}
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();
202 const decl_type *getPreviousDecl() const {
203 return const_cast<decl_type *>(
204 static_cast<const decl_type*>(this))->getPreviousDecl();
207 /// \brief Return the first declaration of this declaration or itself if this
208 /// is the only declaration.
209 decl_type *getFirstDecl() { return First; }
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; }
215 /// \brief True if this is the first declaration in its redeclaration chain.
216 bool isFirstDecl() const { return RedeclLink.NextIsLatest(); }
218 /// \brief Returns the most recent (re)declaration of this declaration.
219 decl_type *getMostRecentDecl() {
220 return getFirstDecl()->getNextRedeclaration();
223 /// \brief Returns the most recent (re)declaration of this declaration.
224 const decl_type *getMostRecentDecl() const {
225 return getFirstDecl()->getNextRedeclaration();
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);
232 /// \brief Iterates through all the redeclarations of the same decl.
233 class redecl_iterator {
234 /// Current - The current declaration.
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;
246 redecl_iterator() : Current(nullptr) { }
247 explicit redecl_iterator(decl_type *C)
248 : Current(C), Starter(C), PassedFirst(false) { }
250 reference operator*() const { return Current; }
251 pointer operator->() const { return Current; }
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()) {
258 assert(0 && "Passed first decl twice, invalid redecl chain!");
265 // Get either previous decl or latest decl.
266 decl_type *Next = Current->getNextRedeclaration();
267 Current = (Next != Starter) ? Next : nullptr;
271 redecl_iterator operator++(int) {
272 redecl_iterator tmp(*this);
277 friend bool operator==(redecl_iterator x, redecl_iterator y) {
278 return x.Current == y.Current;
280 friend bool operator!=(redecl_iterator x, redecl_iterator y) {
281 return x.Current != y.Current;
285 typedef llvm::iterator_range<redecl_iterator> redecl_range;
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))),
295 redecl_iterator redecls_begin() const { return redecls().begin(); }
296 redecl_iterator redecls_end() const { return redecls().end(); }
298 friend class ASTDeclReader;
299 friend class ASTDeclWriter;
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);
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
309 template<typename decl_type>
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())
320 return cast<decl_type>(getPrimaryMergedDecl(const_cast<decl_type*>(D)));
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())
329 return cast<decl_type>(getPrimaryMergedDecl(const_cast<decl_type*>(D)));
332 /// \brief Returns true if this is the first declaration.
333 bool isFirstDecl() const { return getFirstDecl() == this; }
336 /// A wrapper class around a pointer that always points to its canonical
339 /// CanonicalDeclPtr<decl_type> behaves just like decl_type*, except we call
340 /// decl_type::getCanonicalDecl() on construction.
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 {
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;
353 operator decl_type *() { return Ptr; }
354 operator const decl_type *() const { return Ptr; }
356 decl_type *operator->() { return Ptr; }
357 const decl_type *operator->() const { return Ptr; }
359 decl_type &operator*() { return *Ptr; }
360 const decl_type &operator*() const { return *Ptr; }
363 friend struct llvm::DenseMapInfo<CanonicalDeclPtr<decl_type>>;
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 *>;
375 static CanonicalDeclPtr getEmptyKey() {
376 // Construct our CanonicalDeclPtr this way because the regular constructor
377 // would dereference P.Ptr, which is not allowed.
379 P.Ptr = BaseInfo::getEmptyKey();
383 static CanonicalDeclPtr getTombstoneKey() {
385 P.Ptr = BaseInfo::getTombstoneKey();
389 static unsigned getHashValue(const CanonicalDeclPtr &P) {
390 return BaseInfo::getHashValue(P);
393 static bool isEqual(const CanonicalDeclPtr &LHS,
394 const CanonicalDeclPtr &RHS) {
395 return BaseInfo::isEqual(LHS, RHS);