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(O: 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 friend class IncrementalParser;
197
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.
204 decl_type *getPreviousDecl() {
205 if (!RedeclLink.isFirst())
206 return getNextRedeclaration();
207 return nullptr;
208 }
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.
216 decl_type *getFirstDecl() { return First; }
217
218 /// Return the first declaration of this declaration or itself if this
219 /// is the only declaration.
220 const decl_type *getFirstDecl() const { return First; }
221
222 /// True if this is the first declaration in its redeclaration chain.
223 bool isFirstDecl() const { return RedeclLink.isFirst(); }
224
225 /// Returns the most recent (re)declaration of this declaration.
226 decl_type *getMostRecentDecl() {
227 return getFirstDecl()->getNextRedeclaration();
228 }
229
230 /// Returns the most recent (re)declaration of this declaration.
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 = nullptr;
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;
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 // Make sure we don't infinitely loop on an invalid redecl chain. This
262 // should never happen.
263 if (Current->isFirstDecl()) {
264 if (PassedFirst) {
265 assert(0 && "Passed first decl twice, invalid redecl chain!");
266 Current = nullptr;
267 return *this;
268 }
269 PassedFirst = true;
270 }
271
272 // Get either previous decl or latest decl.
273 decl_type *Next = Current->getNextRedeclaration();
274 Current = (Next != Starter) ? Next : nullptr;
275 return *this;
276 }
277
278 redecl_iterator operator++(int) {
279 redecl_iterator tmp(*this);
280 ++(*this);
281 return tmp;
282 }
283
284 friend bool operator==(redecl_iterator x, redecl_iterator y) {
285 return x.Current == y.Current;
286 }
287 friend bool operator!=(redecl_iterator x, redecl_iterator y) {
288 return x.Current != y.Current;
289 }
290 };
291
292 using redecl_range = llvm::iterator_range<redecl_iterator>;
293
294 /// Returns an iterator range for all the redeclarations of the same
295 /// decl. It will iterate at least once (when this decl is the only one).
296 redecl_range redecls() const {
297 return redecl_range(redecl_iterator(const_cast<decl_type *>(
298 static_cast<const decl_type *>(this))),
299 redecl_iterator());
300 }
301
302 redecl_iterator redecls_begin() const { return redecls().begin(); }
303 redecl_iterator redecls_end() const { return redecls().end(); }
304};
305
306/// Get the primary declaration for a declaration from an AST file. That
307/// will be the first-loaded declaration.
308Decl *getPrimaryMergedDecl(Decl *D);
309
310/// Provides common interface for the Decls that cannot be redeclared,
311/// but can be merged if the same declaration is brought in from multiple
312/// modules.
313template<typename decl_type>
314class Mergeable {
315public:
316 Mergeable() = default;
317
318 /// Return the first declaration of this declaration or itself if this
319 /// is the only declaration.
320 decl_type *getFirstDecl() {
321 auto *D = static_cast<decl_type *>(this);
322 if (!D->isFromASTFile())
323 return D;
324 return cast<decl_type>(getPrimaryMergedDecl(const_cast<decl_type*>(D)));
325 }
326
327 /// Return the first declaration of this declaration or itself if this
328 /// is the only declaration.
329 const decl_type *getFirstDecl() const {
330 const auto *D = static_cast<const decl_type *>(this);
331 if (!D->isFromASTFile())
332 return D;
333 return cast<decl_type>(getPrimaryMergedDecl(const_cast<decl_type*>(D)));
334 }
335
336 /// Returns true if this is the first declaration.
337 bool isFirstDecl() const { return getFirstDecl() == this; }
338};
339
340/// A wrapper class around a pointer that always points to its canonical
341/// declaration.
342///
343/// CanonicalDeclPtr<decl_type> behaves just like decl_type*, except we call
344/// decl_type::getCanonicalDecl() on construction.
345///
346/// This is useful for hashtables that you want to be keyed on a declaration's
347/// canonical decl -- if you use CanonicalDeclPtr as the key, you don't need to
348/// remember to call getCanonicalDecl() everywhere.
349template <typename decl_type> class CanonicalDeclPtr {
350public:
351 CanonicalDeclPtr() = default;
352 CanonicalDeclPtr(decl_type *Ptr)
353 : Ptr(Ptr ? Ptr->getCanonicalDecl() : nullptr) {}
354 CanonicalDeclPtr(const CanonicalDeclPtr &) = default;
355 CanonicalDeclPtr &operator=(const CanonicalDeclPtr &) = default;
356
357 operator decl_type *() { return Ptr; }
358 operator const decl_type *() const { return Ptr; }
359
360 decl_type *operator->() { return Ptr; }
361 const decl_type *operator->() const { return Ptr; }
362
363 decl_type &operator*() { return *Ptr; }
364 const decl_type &operator*() const { return *Ptr; }
365
366 friend bool operator==(CanonicalDeclPtr LHS, CanonicalDeclPtr RHS) {
367 return LHS.Ptr == RHS.Ptr;
368 }
369 friend bool operator!=(CanonicalDeclPtr LHS, CanonicalDeclPtr RHS) {
370 return LHS.Ptr != RHS.Ptr;
371 }
372
373private:
374 friend struct llvm::DenseMapInfo<CanonicalDeclPtr<decl_type>>;
375 friend struct llvm::PointerLikeTypeTraits<CanonicalDeclPtr<decl_type>>;
376
377 decl_type *Ptr = nullptr;
378};
379
380} // namespace clang
381
382namespace llvm {
383
384template <typename decl_type>
385struct DenseMapInfo<clang::CanonicalDeclPtr<decl_type>> {
386 using CanonicalDeclPtr = clang::CanonicalDeclPtr<decl_type>;
387 using BaseInfo = DenseMapInfo<decl_type *>;
388
389 static CanonicalDeclPtr getEmptyKey() {
390 // Construct our CanonicalDeclPtr this way because the regular constructor
391 // would dereference P.Ptr, which is not allowed.
392 CanonicalDeclPtr P;
393 P.Ptr = BaseInfo::getEmptyKey();
394 return P;
395 }
396
397 static CanonicalDeclPtr getTombstoneKey() {
398 CanonicalDeclPtr P;
399 P.Ptr = BaseInfo::getTombstoneKey();
400 return P;
401 }
402
403 static unsigned getHashValue(const CanonicalDeclPtr &P) {
404 return BaseInfo::getHashValue(P);
405 }
406
407 static bool isEqual(const CanonicalDeclPtr &LHS,
408 const CanonicalDeclPtr &RHS) {
409 return BaseInfo::isEqual(LHS, RHS);
410 }
411};
412
413template <typename decl_type>
414struct PointerLikeTypeTraits<clang::CanonicalDeclPtr<decl_type>> {
415 static inline void *getAsVoidPointer(clang::CanonicalDeclPtr<decl_type> P) {
416 return P.Ptr;
417 }
418 static inline clang::CanonicalDeclPtr<decl_type> getFromVoidPointer(void *P) {
419 clang::CanonicalDeclPtr<decl_type> C;
420 C.Ptr = PointerLikeTypeTraits<decl_type *>::getFromVoidPtr(P);
421 return C;
422 }
423 static constexpr int NumLowBitsAvailable =
424 PointerLikeTypeTraits<decl_type *>::NumLowBitsAvailable;
425};
426
427} // namespace llvm
428
429#endif // LLVM_CLANG_AST_REDECLARABLE_H
430

source code of clang/include/clang/AST/Redeclarable.h