clang  9.0.0svn
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 =
90  LazyGenerationalUpdatePtr<const Decl *, Decl *,
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 
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>
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 
198  : RedeclLink(LatestDeclLink(Ctx)),
199  First(static_cast<decl_type *>(this)) {}
200 
201  /// Return the previous declaration of this declaration or NULL if this
202  /// is the first declaration.
203  decl_type *getPreviousDecl() {
204  if (!RedeclLink.isFirst())
205  return getNextRedeclaration();
206  return nullptr;
207  }
208  const decl_type *getPreviousDecl() const {
209  return const_cast<decl_type *>(
210  static_cast<const decl_type*>(this))->getPreviousDecl();
211  }
212 
213  /// Return the first declaration of this declaration or itself if this
214  /// is the only declaration.
215  decl_type *getFirstDecl() { return First; }
216 
217  /// Return the first declaration of this declaration or itself if this
218  /// is the only declaration.
219  const decl_type *getFirstDecl() const { return First; }
220 
221  /// True if this is the first declaration in its redeclaration chain.
222  bool isFirstDecl() const { return RedeclLink.isFirst(); }
223 
224  /// Returns the most recent (re)declaration of this declaration.
225  decl_type *getMostRecentDecl() {
226  return getFirstDecl()->getNextRedeclaration();
227  }
228 
229  /// Returns the most recent (re)declaration of this declaration.
230  const decl_type *getMostRecentDecl() const {
231  return getFirstDecl()->getNextRedeclaration();
232  }
233 
234  /// Set the previous declaration. If PrevDecl is NULL, set this as the
235  /// first and only declaration.
236  void setPreviousDecl(decl_type *PrevDecl);
237 
238  /// Iterates through all the redeclarations of the same decl.
240  /// Current - The current declaration.
241  decl_type *Current = nullptr;
242  decl_type *Starter;
243  bool PassedFirst = false;
244 
245  public:
246  using value_type = decl_type *;
247  using reference = decl_type *;
248  using pointer = decl_type *;
249  using iterator_category = std::forward_iterator_tag;
251 
252  redecl_iterator() = default;
253  explicit redecl_iterator(decl_type *C) : Current(C), Starter(C) {}
254 
255  reference operator*() const { return Current; }
256  pointer operator->() const { return Current; }
257 
259  assert(Current && "Advancing while iterator has reached end");
260  // Sanity check to avoid infinite loop on invalid redecl chain.
261  if (Current->isFirstDecl()) {
262  if (PassedFirst) {
263  assert(0 && "Passed first decl twice, invalid redecl chain!");
264  Current = nullptr;
265  return *this;
266  }
267  PassedFirst = true;
268  }
269 
270  // Get either previous decl or latest decl.
271  decl_type *Next = Current->getNextRedeclaration();
272  Current = (Next != Starter) ? Next : nullptr;
273  return *this;
274  }
275 
277  redecl_iterator tmp(*this);
278  ++(*this);
279  return tmp;
280  }
281 
283  return x.Current == y.Current;
284  }
286  return x.Current != y.Current;
287  }
288  };
289 
290  using redecl_range = llvm::iterator_range<redecl_iterator>;
291 
292  /// Returns an iterator range for all the redeclarations of the same
293  /// decl. It will iterate at least once (when this decl is the only one).
295  return redecl_range(redecl_iterator(const_cast<decl_type *>(
296  static_cast<const decl_type *>(this))),
297  redecl_iterator());
298  }
299 
300  redecl_iterator redecls_begin() const { return redecls().begin(); }
301  redecl_iterator redecls_end() const { return redecls().end(); }
302 };
303 
304 /// Get the primary declaration for a declaration from an AST file. That
305 /// will be the first-loaded declaration.
307 
308 /// Provides common interface for the Decls that cannot be redeclared,
309 /// but can be merged if the same declaration is brought in from multiple
310 /// modules.
311 template<typename decl_type>
312 class Mergeable {
313 public:
314  Mergeable() = default;
315 
316  /// Return the first declaration of this declaration or itself if this
317  /// is the only declaration.
318  decl_type *getFirstDecl() {
319  auto *D = static_cast<decl_type *>(this);
320  if (!D->isFromASTFile())
321  return D;
322  return cast<decl_type>(getPrimaryMergedDecl(const_cast<decl_type*>(D)));
323  }
324 
325  /// Return the first declaration of this declaration or itself if this
326  /// is the only declaration.
327  const decl_type *getFirstDecl() const {
328  const auto *D = static_cast<const decl_type *>(this);
329  if (!D->isFromASTFile())
330  return D;
331  return cast<decl_type>(getPrimaryMergedDecl(const_cast<decl_type*>(D)));
332  }
333 
334  /// Returns true if this is the first declaration.
335  bool isFirstDecl() const { return getFirstDecl() == this; }
336 };
337 
338 /// A wrapper class around a pointer that always points to its canonical
339 /// declaration.
340 ///
341 /// CanonicalDeclPtr<decl_type> behaves just like decl_type*, except we call
342 /// decl_type::getCanonicalDecl() on construction.
343 ///
344 /// This is useful for hashtables that you want to be keyed on a declaration's
345 /// canonical decl -- if you use CanonicalDeclPtr as the key, you don't need to
346 /// remember to call getCanonicalDecl() everywhere.
347 template <typename decl_type> class CanonicalDeclPtr {
348 public:
349  CanonicalDeclPtr() = default;
350  CanonicalDeclPtr(decl_type *Ptr)
351  : Ptr(Ptr ? Ptr->getCanonicalDecl() : nullptr) {}
352  CanonicalDeclPtr(const CanonicalDeclPtr &) = default;
353  CanonicalDeclPtr &operator=(const CanonicalDeclPtr &) = default;
354 
355  operator decl_type *() { return Ptr; }
356  operator const decl_type *() const { return Ptr; }
357 
358  decl_type *operator->() { return Ptr; }
359  const decl_type *operator->() const { return Ptr; }
360 
361  decl_type &operator*() { return *Ptr; }
362  const decl_type &operator*() const { return *Ptr; }
363 
365  return LHS.Ptr == RHS.Ptr;
366  }
368  return LHS.Ptr != RHS.Ptr;
369  }
370 
371 private:
372  friend struct llvm::DenseMapInfo<CanonicalDeclPtr<decl_type>>;
373 
374  decl_type *Ptr = nullptr;
375 };
376 
377 } // namespace clang
378 
379 namespace llvm {
380 
381 template <typename decl_type>
382 struct DenseMapInfo<clang::CanonicalDeclPtr<decl_type>> {
385 
387  // Construct our CanonicalDeclPtr this way because the regular constructor
388  // would dereference P.Ptr, which is not allowed.
390  P.Ptr = BaseInfo::getEmptyKey();
391  return P;
392  }
393 
396  P.Ptr = BaseInfo::getTombstoneKey();
397  return P;
398  }
399 
400  static unsigned getHashValue(const CanonicalDeclPtr &P) {
401  return BaseInfo::getHashValue(P);
402  }
403 
404  static bool isEqual(const CanonicalDeclPtr &LHS,
405  const CanonicalDeclPtr &RHS) {
406  return BaseInfo::isEqual(LHS, RHS);
407  }
408 };
409 
410 } // namespace llvm
411 
412 #endif // LLVM_CLANG_AST_REDECLARABLE_H
static const Decl * getCanonicalDecl(const Decl *D)
decl_type & operator*()
Definition: Redeclarable.h:361
DominatorTree GraphTraits specialization so the DominatorTree can be iterable by generic graph iterat...
Definition: Dominators.h:29
void setPreviousDecl(decl_type *PrevDecl)
Set the previous declaration.
Definition: Decl.h:4329
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:88
StringRef P
The l-value was an access to a declared entity or something equivalently strong, like the address of ...
static unsigned getHashValue(const CanonicalDeclPtr &P)
Definition: Redeclarable.h:400
virtual void CompleteRedeclChain(const Decl *D)
Gives the external AST source an opportunity to complete the redeclaration chain for a declaration...
static DeclLink LatestDeclLink(const ASTContext &Ctx)
Definition: Redeclarable.h:170
Provides common interface for the Decls that can be redeclared.
Definition: Redeclarable.h:84
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:154
static bool isEqual(const CanonicalDeclPtr &LHS, const CanonicalDeclPtr &RHS)
Definition: Redeclarable.h:404
friend bool operator==(redecl_iterator x, redecl_iterator y)
Definition: Redeclarable.h:282
const decl_type * getPreviousDecl() const
Definition: Redeclarable.h:208
decl_type * operator->()
Definition: Redeclarable.h:358
DeclLink RedeclLink
Points to the next redeclaration in the chain.
Definition: Redeclarable.h:185
decl_type * getFirstDecl()
Return the first declaration of this declaration or itself if this is the only declaration.
Definition: Redeclarable.h:318
CanonicalDeclPtr(decl_type *Ptr)
Definition: Redeclarable.h:350
const decl_type & operator*() const
Definition: Redeclarable.h:362
redecl_iterator redecls_begin() const
Definition: Redeclarable.h:300
friend bool operator!=(CanonicalDeclPtr LHS, CanonicalDeclPtr RHS)
Definition: Redeclarable.h:367
const decl_type * getMostRecentDecl() const
Returns the most recent (re)declaration of this declaration.
Definition: Redeclarable.h:230
Iterates through all the redeclarations of the same decl.
Definition: Redeclarable.h:239
static DeclLink PreviousDeclLink(decl_type *D)
Definition: Redeclarable.h:166
Decl * getPrimaryMergedDecl(Decl *D)
Get the primary declaration for a declaration from an AST file.
Definition: Decl.cpp:75
T get(Owner O)
Get the value of this pointer, updating its owner if necessary.
decl_type * getFirstDecl()
Return the first declaration of this declaration or itself if this is the only declaration.
Definition: Redeclarable.h:215
friend bool operator==(CanonicalDeclPtr LHS, CanonicalDeclPtr RHS)
Definition: Redeclarable.h:364
decl_type * getPreviousDecl()
Return the previous declaration of this declaration or NULL if this is the first declaration.
Definition: Redeclarable.h:203
redecl_range redecls() const
Returns an iterator range for all the redeclarations of the same decl.
Definition: Redeclarable.h:294
Redeclarable(const ASTContext &Ctx)
Definition: Redeclarable.h:197
const decl_type * operator->() const
Definition: Redeclarable.h:359
bool isFirstDecl() const
True if this is the first declaration in its redeclaration chain.
Definition: Redeclarable.h:222
const decl_type * getFirstDecl() const
Return the first declaration of this declaration or itself if this is the only declaration.
Definition: Redeclarable.h:327
bool isFromASTFile() const
Determine whether this declaration came from an AST file (such as a precompiled header or module) rat...
Definition: DeclBase.h:702
__v16qu tmp
Definition: emmintrin.h:2133
Dataflow Directional Tag Classes.
redecl_iterator redecls_end() const
Definition: Redeclarable.h:301
llvm::iterator_range< redecl_iterator > redecl_range
Definition: Redeclarable.h:290
void set(T NewValue)
Set the value of this pointer, in the current generation.
Provides common interface for the Decls that cannot be redeclared, but can be merged if the same decl...
Definition: Redeclarable.h:312
friend bool operator!=(redecl_iterator x, redecl_iterator y)
Definition: Redeclarable.h:285
decl_type * getNextRedeclaration() const
Definition: Redeclarable.h:189
__PTRDIFF_TYPE__ ptrdiff_t
A signed integer type that is the result of subtracting two pointers.
Definition: opencl-c-base.h:48
const decl_type * getFirstDecl() const
Return the first declaration of this declaration or itself if this is the only declaration.
Definition: Redeclarable.h:219
std::forward_iterator_tag iterator_category
Definition: Redeclarable.h:249
decl_type * getMostRecentDecl()
Returns the most recent (re)declaration of this declaration.
Definition: Redeclarable.h:225
A lazy value (of type T) that is within an AST node of type Owner, where the value might change in la...
bool isFirstDecl() const
Returns true if this is the first declaration.
Definition: Redeclarable.h:335
A wrapper class around a pointer that always points to its canonical declaration. ...
Definition: Redeclarable.h:347