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 | |
25 | namespace clang { |
26 | |
27 | class ASTContext; |
28 | class 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. |
83 | template<typename decl_type> |
84 | class Redeclarable { |
85 | protected: |
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 | |
193 | public: |
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. |
308 | Decl *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. |
313 | template<typename decl_type> |
314 | class Mergeable { |
315 | public: |
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. |
349 | template <typename decl_type> class CanonicalDeclPtr { |
350 | public: |
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 | |
373 | private: |
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 | |
382 | namespace llvm { |
383 | |
384 | template <typename decl_type> |
385 | struct 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 | |
413 | template <typename decl_type> |
414 | struct 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 | |