clang  14.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 
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 =
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) {
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 
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.
241  /// Current - The current declaration.
242  decl_type *Current = nullptr;
243  decl_type *Starter;
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;
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  // Sanity check to avoid infinite loop on invalid redecl chain.
262  if (Current->isFirstDecl()) {
263  if (PassedFirst) {
264  assert(0 && "Passed first decl twice, invalid redecl chain!");
265  Current = nullptr;
266  return *this;
267  }
268  PassedFirst = true;
269  }
270 
271  // Get either previous decl or latest decl.
272  decl_type *Next = Current->getNextRedeclaration();
273  Current = (Next != Starter) ? Next : nullptr;
274  return *this;
275  }
276 
278  redecl_iterator tmp(*this);
279  ++(*this);
280  return tmp;
281  }
282 
284  return x.Current == y.Current;
285  }
287  return x.Current != y.Current;
288  }
289  };
290 
291  using redecl_range = llvm::iterator_range<redecl_iterator>;
292 
293  /// Returns an iterator range for all the redeclarations of the same
294  /// decl. It will iterate at least once (when this decl is the only one).
296  return redecl_range(redecl_iterator(const_cast<decl_type *>(
297  static_cast<const decl_type *>(this))),
298  redecl_iterator());
299  }
300 
301  redecl_iterator redecls_begin() const { return redecls().begin(); }
302  redecl_iterator redecls_end() const { return redecls().end(); }
303 };
304 
305 /// Get the primary declaration for a declaration from an AST file. That
306 /// will be the first-loaded declaration.
307 Decl *getPrimaryMergedDecl(Decl *D);
308 
309 /// Provides common interface for the Decls that cannot be redeclared,
310 /// but can be merged if the same declaration is brought in from multiple
311 /// modules.
312 template<typename decl_type>
313 class Mergeable {
314 public:
315  Mergeable() = default;
316 
317  /// Return the first declaration of this declaration or itself if this
318  /// is the only declaration.
319  decl_type *getFirstDecl() {
320  auto *D = static_cast<decl_type *>(this);
321  if (!D->isFromASTFile())
322  return D;
323  return cast<decl_type>(getPrimaryMergedDecl(const_cast<decl_type*>(D)));
324  }
325 
326  /// Return the first declaration of this declaration or itself if this
327  /// is the only declaration.
328  const decl_type *getFirstDecl() const {
329  const auto *D = static_cast<const decl_type *>(this);
330  if (!D->isFromASTFile())
331  return D;
332  return cast<decl_type>(getPrimaryMergedDecl(const_cast<decl_type*>(D)));
333  }
334 
335  /// Returns true if this is the first declaration.
336  bool isFirstDecl() const { return getFirstDecl() == this; }
337 };
338 
339 /// A wrapper class around a pointer that always points to its canonical
340 /// declaration.
341 ///
342 /// CanonicalDeclPtr<decl_type> behaves just like decl_type*, except we call
343 /// decl_type::getCanonicalDecl() on construction.
344 ///
345 /// This is useful for hashtables that you want to be keyed on a declaration's
346 /// canonical decl -- if you use CanonicalDeclPtr as the key, you don't need to
347 /// remember to call getCanonicalDecl() everywhere.
348 template <typename decl_type> class CanonicalDeclPtr {
349 public:
350  CanonicalDeclPtr() = default;
351  CanonicalDeclPtr(decl_type *Ptr)
352  : Ptr(Ptr ? Ptr->getCanonicalDecl() : nullptr) {}
353  CanonicalDeclPtr(const CanonicalDeclPtr &) = default;
354  CanonicalDeclPtr &operator=(const CanonicalDeclPtr &) = default;
355 
356  operator decl_type *() { return Ptr; }
357  operator const decl_type *() const { return Ptr; }
358 
359  decl_type *operator->() { return Ptr; }
360  const decl_type *operator->() const { return Ptr; }
361 
362  decl_type &operator*() { return *Ptr; }
363  const decl_type &operator*() const { return *Ptr; }
364 
366  return LHS.Ptr == RHS.Ptr;
367  }
369  return LHS.Ptr != RHS.Ptr;
370  }
371 
372 private:
373  friend struct llvm::DenseMapInfo<CanonicalDeclPtr<decl_type>>;
375 
376  decl_type *Ptr = nullptr;
377 };
378 
379 } // namespace clang
380 
381 namespace llvm {
382 
383 template <typename decl_type>
384 struct DenseMapInfo<clang::CanonicalDeclPtr<decl_type>> {
387 
389  // Construct our CanonicalDeclPtr this way because the regular constructor
390  // would dereference P.Ptr, which is not allowed.
392  P.Ptr = BaseInfo::getEmptyKey();
393  return P;
394  }
395 
398  P.Ptr = BaseInfo::getTombstoneKey();
399  return P;
400  }
401 
402  static unsigned getHashValue(const CanonicalDeclPtr &P) {
403  return BaseInfo::getHashValue(P);
404  }
405 
406  static bool isEqual(const CanonicalDeclPtr &LHS,
407  const CanonicalDeclPtr &RHS) {
408  return BaseInfo::isEqual(LHS, RHS);
409  }
410 };
411 
412 template <typename decl_type>
413 struct PointerLikeTypeTraits<clang::CanonicalDeclPtr<decl_type>> {
415  return P.Ptr;
416  }
420  return C;
421  }
422  static constexpr int NumLowBitsAvailable =
424 };
425 
426 } // namespace llvm
427 
428 #endif // LLVM_CLANG_AST_REDECLARABLE_H
clang::Redeclarable::redecl_iterator::operator*
reference operator*() const
Definition: Redeclarable.h:256
clang::Redeclarable::redecl_iterator
Iterates through all the redeclarations of the same decl.
Definition: Redeclarable.h:240
llvm
Definition: Dominators.h:30
clang::Redeclarable
Provides common interface for the Decls that can be redeclared.
Definition: Redeclarable.h:84
clang::ExternalASTSource::CompleteRedeclChain
virtual void CompleteRedeclChain(const Decl *D)
Gives the external AST source an opportunity to complete the redeclaration chain for a declaration.
Definition: ExternalASTSource.cpp:47
clang::Redeclarable::redecls_begin
redecl_iterator redecls_begin() const
Definition: Redeclarable.h:301
clang::Redeclarable::PreviousDeclLink
static DeclLink PreviousDeclLink(decl_type *D)
Definition: Redeclarable.h:166
clang::Mergeable::getFirstDecl
const decl_type * getFirstDecl() const
Return the first declaration of this declaration or itself if this is the only declaration.
Definition: Redeclarable.h:328
clang::Redeclarable::redecls_end
redecl_iterator redecls_end() const
Definition: Redeclarable.h:302
llvm::DenseMapInfo< clang::CanonicalDeclPtr< decl_type > >::getTombstoneKey
static CanonicalDeclPtr getTombstoneKey()
Definition: Redeclarable.h:396
clang::Redeclarable::getFirstDecl
decl_type * getFirstDecl()
Return the first declaration of this declaration or itself if this is the only declaration.
Definition: Redeclarable.h:216
clang::CanonicalDeclPtr::operator*
decl_type & operator*()
Definition: Redeclarable.h:362
clang::CanonicalDeclPtr::operator->
decl_type * operator->()
Definition: Redeclarable.h:359
clang::Redeclarable::redecl_iterator::reference
decl_type * reference
Definition: Redeclarable.h:248
clang::Redeclarable< VarDecl >::redecl_range
llvm::iterator_range< redecl_iterator > redecl_range
Definition: Redeclarable.h:291
clang::CodeGen::AlignmentSource::Decl
@ Decl
The l-value was an access to a declared entity or something equivalently strong, like the address of ...
clang::Redeclarable::redecl_iterator::redecl_iterator
redecl_iterator()=default
clang::Redeclarable::redecl_iterator::operator==
friend bool operator==(redecl_iterator x, redecl_iterator y)
Definition: Redeclarable.h:283
llvm::DenseMapInfo
Definition: TypeOrdering.h:37
clang::Redeclarable::setPreviousDecl
void setPreviousDecl(decl_type *PrevDecl)
Set the previous declaration.
Definition: Decl.h:4598
clang::Redeclarable::redecl_iterator::operator++
redecl_iterator operator++(int)
Definition: Redeclarable.h:277
clang::Redeclarable::redecl_iterator::value_type
decl_type * value_type
Definition: Redeclarable.h:247
clang::CanonicalDeclPtr::operator!=
friend bool operator!=(CanonicalDeclPtr LHS, CanonicalDeclPtr RHS)
Definition: Redeclarable.h:368
clang::ASTContext
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:212
clang::CanonicalDeclPtr::CanonicalDeclPtr
CanonicalDeclPtr()=default
clang::LazyGenerationalUpdatePtr
A lazy value (of type T) that is within an AST node of type Owner, where the value might change in la...
Definition: ExternalASTSource.h:388
clang::Mergeable::getFirstDecl
decl_type * getFirstDecl()
Return the first declaration of this declaration or itself if this is the only declaration.
Definition: Redeclarable.h:319
clang::Redeclarable::redecls
redecl_range redecls() const
Returns an iterator range for all the redeclarations of the same decl.
Definition: Redeclarable.h:295
clang::getPrimaryMergedDecl
Decl * getPrimaryMergedDecl(Decl *D)
Get the primary declaration for a declaration from an AST file.
Definition: Decl.cpp:76
clang::Redeclarable::redecl_iterator::difference_type
std::ptrdiff_t difference_type
Definition: Redeclarable.h:251
clang::Redeclarable::Redeclarable
Redeclarable(const ASTContext &Ctx)
Definition: Redeclarable.h:198
clang::Redeclarable::RedeclLink
DeclLink RedeclLink
Points to the next redeclaration in the chain.
Definition: Redeclarable.h:185
clang::Redeclarable::redecl_iterator::operator->
pointer operator->() const
Definition: Redeclarable.h:257
clang::Redeclarable::getPreviousDecl
decl_type * getPreviousDecl()
Return the previous declaration of this declaration or NULL if this is the first declaration.
Definition: Redeclarable.h:204
clang::Redeclarable::LatestDeclLink
static DeclLink LatestDeclLink(const ASTContext &Ctx)
Definition: Redeclarable.h:170
clang::Redeclarable::isFirstDecl
bool isFirstDecl() const
True if this is the first declaration in its redeclaration chain.
Definition: Redeclarable.h:223
clang::CanonicalDeclPtr::operator*
const decl_type & operator*() const
Definition: Redeclarable.h:363
x
IRgen optimization opportunities The common pattern of short x
Definition: README.txt:7
clang::CanonicalDeclPtr::operator->
const decl_type * operator->() const
Definition: Redeclarable.h:360
clang::Redeclarable::redecl_iterator::operator++
redecl_iterator & operator++()
Definition: Redeclarable.h:259
clang::IncrementalParser
Provides support for incremental compilation.
Definition: IncrementalParser.h:40
clang::CanonicalDeclPtr::CanonicalDeclPtr
CanonicalDeclPtr(decl_type *Ptr)
Definition: Redeclarable.h:351
ExternalASTSource.h
clang::Redeclarable::getMostRecentDecl
const decl_type * getMostRecentDecl() const
Returns the most recent (re)declaration of this declaration.
Definition: Redeclarable.h:231
clang::Mergeable
Provides common interface for the Decls that cannot be redeclared, but can be merged if the same decl...
Definition: Redeclarable.h:313
clang::Redeclarable::First
decl_type * First
Definition: Redeclarable.h:187
clang::LazyGenerationalUpdatePtr::set
void set(T NewValue)
Set the value of this pointer, in the current generation.
Definition: ExternalASTSource.h:425
P
StringRef P
Definition: ASTMatchersInternal.cpp:563
clang::Mergeable::Mergeable
Mergeable()=default
getCanonicalDecl
static const Decl * getCanonicalDecl(const Decl *D)
Definition: IndexingContext.cpp:301
clang::Redeclarable::getPreviousDecl
const decl_type * getPreviousDecl() const
Definition: Redeclarable.h:209
clang::Redeclarable::getNextRedeclaration
decl_type * getNextRedeclaration() const
Definition: Redeclarable.h:189
clang::Decl
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:89
clang::Redeclarable::redecl_iterator::pointer
decl_type * pointer
Definition: Redeclarable.h:249
clang::Redeclarable::getFirstDecl
const decl_type * getFirstDecl() const
Return the first declaration of this declaration or itself if this is the only declaration.
Definition: Redeclarable.h:220
clang::Redeclarable::getMostRecentDecl
decl_type * getMostRecentDecl()
Returns the most recent (re)declaration of this declaration.
Definition: Redeclarable.h:226
llvm::PointerLikeTypeTraits< clang::CanonicalDeclPtr< decl_type > >::getFromVoidPointer
static clang::CanonicalDeclPtr< decl_type > getFromVoidPointer(void *P)
Definition: Redeclarable.h:417
clang::Redeclarable::redecl_iterator::operator!=
friend bool operator!=(redecl_iterator x, redecl_iterator y)
Definition: Redeclarable.h:286
clang
Definition: CalledOnceCheck.h:17
ptrdiff_t
__PTRDIFF_TYPE__ ptrdiff_t
A signed integer type that is the result of subtracting two pointers.
Definition: opencl-c-base.h:110
llvm::PointerLikeTypeTraits
Definition: DeclGroup.h:139
llvm::DenseMapInfo< clang::CanonicalDeclPtr< decl_type > >::getHashValue
static unsigned getHashValue(const CanonicalDeclPtr &P)
Definition: Redeclarable.h:402
clang::Mergeable::isFirstDecl
bool isFirstDecl() const
Returns true if this is the first declaration.
Definition: Redeclarable.h:336
clang::CanonicalDeclPtr
A wrapper class around a pointer that always points to its canonical declaration.
Definition: Redeclarable.h:348
clang::CanonicalDeclPtr::operator=
CanonicalDeclPtr & operator=(const CanonicalDeclPtr &)=default
clang::CanonicalDeclPtr::operator==
friend bool operator==(CanonicalDeclPtr LHS, CanonicalDeclPtr RHS)
Definition: Redeclarable.h:365
llvm::DenseMapInfo< clang::CanonicalDeclPtr< decl_type > >::isEqual
static bool isEqual(const CanonicalDeclPtr &LHS, const CanonicalDeclPtr &RHS)
Definition: Redeclarable.h:406
clang::Redeclarable::redecl_iterator::redecl_iterator
redecl_iterator(decl_type *C)
Definition: Redeclarable.h:254
clang::ASTDeclReader
Definition: ASTReaderDecl.cpp:80
clang::Redeclarable::redecl_iterator::iterator_category
std::forward_iterator_tag iterator_category
Definition: Redeclarable.h:250
clang::ASTDeclWriter
Definition: ASTWriterDecl.cpp:34
llvm::PointerLikeTypeTraits< clang::CanonicalDeclPtr< decl_type > >::getAsVoidPointer
static void * getAsVoidPointer(clang::CanonicalDeclPtr< decl_type > P)
Definition: Redeclarable.h:414
llvm::DenseMapInfo< clang::CanonicalDeclPtr< decl_type > >::getEmptyKey
static CanonicalDeclPtr getEmptyKey()
Definition: Redeclarable.h:388