clang 19.0.0git
Redeclarable.h
Go to the documentation of this file.
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
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>
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 =
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:
110
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
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) {
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>
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
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.
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
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
279 redecl_iterator tmp(*this);
280 ++(*this);
281 return tmp;
282 }
283
285 return x.Current == y.Current;
286 }
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).
297 return redecl_range(redecl_iterator(const_cast<decl_type *>(
298 static_cast<const decl_type *>(this))),
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>
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) {}
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
367 return LHS.Ptr == RHS.Ptr;
368 }
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>> {
387 using BaseInfo = DenseMapInfo<decl_type *>;
388
390 // Construct our CanonicalDeclPtr this way because the regular constructor
391 // would dereference P.Ptr, which is not allowed.
393 P.Ptr = BaseInfo::getEmptyKey();
394 return P;
395 }
396
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>> {
416 return P.Ptr;
417 }
421 return C;
422 }
423 static constexpr int NumLowBitsAvailable =
425};
426
427} // namespace llvm
428
429#endif // LLVM_CLANG_AST_REDECLARABLE_H
StringRef P
static const Decl * getCanonicalDecl(const Decl *D)
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:182
A wrapper class around a pointer that always points to its canonical declaration.
Definition: Redeclarable.h:349
CanonicalDeclPtr(const CanonicalDeclPtr &)=default
const decl_type * operator->() const
Definition: Redeclarable.h:361
CanonicalDeclPtr & operator=(const CanonicalDeclPtr &)=default
const decl_type & operator*() const
Definition: Redeclarable.h:364
decl_type & operator*()
Definition: Redeclarable.h:363
CanonicalDeclPtr(decl_type *Ptr)
Definition: Redeclarable.h:352
decl_type * operator->()
Definition: Redeclarable.h:360
friend bool operator==(CanonicalDeclPtr LHS, CanonicalDeclPtr RHS)
Definition: Redeclarable.h:366
friend bool operator!=(CanonicalDeclPtr LHS, CanonicalDeclPtr RHS)
Definition: Redeclarable.h:369
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:85
virtual void CompleteRedeclChain(const Decl *D)
Gives the external AST source an opportunity to complete the redeclaration chain for a declaration.
Provides support for incremental compilation.
Provides common interface for the Decls that cannot be redeclared, but can be merged if the same decl...
Definition: Redeclarable.h:314
bool isFirstDecl() const
Returns true if this is the first declaration.
Definition: Redeclarable.h:337
const decl_type * getFirstDecl() const
Return the first declaration of this declaration or itself if this is the only declaration.
Definition: Redeclarable.h:329
Mergeable()=default
decl_type * getFirstDecl()
Return the first declaration of this declaration or itself if this is the only declaration.
Definition: Redeclarable.h:320
Iterates through all the redeclarations of the same decl.
Definition: Redeclarable.h:240
friend bool operator!=(redecl_iterator x, redecl_iterator y)
Definition: Redeclarable.h:287
friend bool operator==(redecl_iterator x, redecl_iterator y)
Definition: Redeclarable.h:284
std::forward_iterator_tag iterator_category
Definition: Redeclarable.h:250
Provides common interface for the Decls that can be redeclared.
Definition: Redeclarable.h:84
decl_type * getFirstDecl()
Return the first declaration of this declaration or itself if this is the only declaration.
Definition: Redeclarable.h:216
const decl_type * getMostRecentDecl() const
Returns the most recent (re)declaration of this declaration.
Definition: Redeclarable.h:231
const decl_type * getFirstDecl() const
Return the first declaration of this declaration or itself if this is the only declaration.
Definition: Redeclarable.h:220
decl_type * getNextRedeclaration() const
Definition: Redeclarable.h:189
Redeclarable(const ASTContext &Ctx)
Definition: Redeclarable.h:198
decl_type * getPreviousDecl()
Return the previous declaration of this declaration or NULL if this is the first declaration.
Definition: Redeclarable.h:204
redecl_iterator redecls_end() const
Definition: Redeclarable.h:303
const decl_type * getPreviousDecl() const
Definition: Redeclarable.h:209
DeclLink RedeclLink
Points to the next redeclaration in the chain.
Definition: Redeclarable.h:185
llvm::iterator_range< redecl_iterator > redecl_range
Definition: Redeclarable.h:292
decl_type * getMostRecentDecl()
Returns the most recent (re)declaration of this declaration.
Definition: Redeclarable.h:226
void setPreviousDecl(decl_type *PrevDecl)
Set the previous declaration.
Definition: Decl.h:4955
static DeclLink LatestDeclLink(const ASTContext &Ctx)
Definition: Redeclarable.h:170
bool isFirstDecl() const
True if this is the first declaration in its redeclaration chain.
Definition: Redeclarable.h:223
redecl_iterator redecls_begin() const
Definition: Redeclarable.h:302
redecl_range redecls() const
Returns an iterator range for all the redeclarations of the same decl.
Definition: Redeclarable.h:296
static DeclLink PreviousDeclLink(decl_type *D)
Definition: Redeclarable.h:166
@ Decl
The l-value was an access to a declared entity or something equivalently strong, like the address of ...
The JSON file list parser is used to communicate input to InstallAPI.
Decl * getPrimaryMergedDecl(Decl *D)
Get the primary declaration for a declaration from an AST file.
Definition: Decl.cpp:77
YAML serialization mapping.
Definition: Dominators.h:30
A lazy value (of type T) that is within an AST node of type Owner, where the value might change in la...
void set(T NewValue)
Set the value of this pointer, in the current generation.
static unsigned getHashValue(const CanonicalDeclPtr &P)
Definition: Redeclarable.h:403
static bool isEqual(const CanonicalDeclPtr &LHS, const CanonicalDeclPtr &RHS)
Definition: Redeclarable.h:407
static void * getAsVoidPointer(clang::CanonicalDeclPtr< decl_type > P)
Definition: Redeclarable.h:415
static clang::CanonicalDeclPtr< decl_type > getFromVoidPointer(void *P)
Definition: Redeclarable.h:418