clang  8.0.0svn
Redeclarable.h
Go to the documentation of this file.
1 //===- Redeclarable.h - Base for Decls that can be redeclared --*- C++ -*-====//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines the Redeclarable interface.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_CLANG_AST_REDECLARABLE_H
15 #define LLVM_CLANG_AST_REDECLARABLE_H
16 
18 #include "llvm/ADT/DenseMapInfo.h"
19 #include "llvm/ADT/PointerUnion.h"
20 #include "llvm/ADT/iterator_range.h"
21 #include "llvm/Support/Casting.h"
22 #include <cassert>
23 #include <cstddef>
24 #include <iterator>
25 
26 namespace clang {
27 
28 class ASTContext;
29 class Decl;
30 
31 // Some notes on redeclarables:
32 //
33 // - Every redeclarable is on a circular linked list.
34 //
35 // - Every decl has a pointer to the first element of the chain _and_ a
36 // DeclLink that may point to one of 3 possible states:
37 // - the "previous" (temporal) element in the chain
38 // - the "latest" (temporal) element in the chain
39 // - the "uninitialized-latest" value (when newly-constructed)
40 //
41 // - The first element is also often called the canonical element. Every
42 // element has a pointer to it so that "getCanonical" can be fast.
43 //
44 // - Most links in the chain point to previous, except the link out of
45 // the first; it points to latest.
46 //
47 // - Elements are called "first", "previous", "latest" or
48 // "most-recent" when referring to temporal order: order of addition
49 // to the chain.
50 //
51 // - It's easiest to just ignore the implementation of DeclLink when making
52 // sense of the redeclaration chain.
53 //
54 // - There's also a "definition" link for several types of
55 // redeclarable, where only one definition should exist at any given
56 // time (and the defn pointer is stored in the decl's "data" which
57 // is copied to every element on the chain when it's changed).
58 //
59 // Here is some ASCII art:
60 //
61 // "first" "latest"
62 // "canonical" "most recent"
63 // +------------+ first +--------------+
64 // | | <--------------------------- | |
65 // | | | |
66 // | | | |
67 // | | +--------------+ | |
68 // | | first | | | |
69 // | | <---- | | | |
70 // | | | | | |
71 // | @class A | link | @interface A | link | @class A |
72 // | seen first | <---- | seen second | <---- | seen third |
73 // | | | | | |
74 // +------------+ +--------------+ +--------------+
75 // | data | defn | data | defn | data |
76 // | | ----> | | <---- | |
77 // +------------+ +--------------+ +--------------+
78 // | | ^ ^
79 // | |defn | |
80 // | link +-----+ |
81 // +-->-------------------------------------------+
82 
83 /// Provides common interface for the Decls that can be redeclared.
84 template<typename decl_type>
85 class Redeclarable {
86 protected:
87  class DeclLink {
88  /// A pointer to a known latest declaration, either statically known or
89  /// generationally updated as decls are added by an external source.
90  using KnownLatest =
91  LazyGenerationalUpdatePtr<const Decl *, Decl *,
93 
94  /// We store a pointer to the ASTContext in the UninitializedLatest
95  /// pointer, but to avoid circular type dependencies when we steal the low
96  /// bits of this pointer, we use a raw void* here.
97  using UninitializedLatest = const void *;
98 
99  using Previous = Decl *;
100 
101  /// A pointer to either an uninitialized latest declaration (where either
102  /// we've not yet set the previous decl or there isn't one), or to a known
103  /// previous declaration.
104  using NotKnownLatest = llvm::PointerUnion<Previous, UninitializedLatest>;
105 
106  mutable llvm::PointerUnion<NotKnownLatest, KnownLatest> Link;
107 
108  public:
111 
113  : Link(NotKnownLatest(reinterpret_cast<UninitializedLatest>(&Ctx))) {}
114  DeclLink(PreviousTag, decl_type *D) : Link(NotKnownLatest(Previous(D))) {}
115 
116  bool isFirst() const {
117  return Link.is<KnownLatest>() ||
118  // FIXME: 'template' is required on the next line due to an
119  // apparent clang bug.
120  Link.get<NotKnownLatest>().template is<UninitializedLatest>();
121  }
122 
123  decl_type *getPrevious(const decl_type *D) const {
124  if (Link.is<NotKnownLatest>()) {
125  NotKnownLatest NKL = Link.get<NotKnownLatest>();
126  if (NKL.is<Previous>())
127  return static_cast<decl_type*>(NKL.get<Previous>());
128 
129  // Allocate the generational 'most recent' cache now, if needed.
130  Link = KnownLatest(*reinterpret_cast<const ASTContext *>(
131  NKL.get<UninitializedLatest>()),
132  const_cast<decl_type *>(D));
133  }
134 
135  return static_cast<decl_type*>(Link.get<KnownLatest>().get(D));
136  }
137 
138  void setPrevious(decl_type *D) {
139  assert(!isFirst() && "decl became non-canonical unexpectedly");
140  Link = Previous(D);
141  }
142 
143  void setLatest(decl_type *D) {
144  assert(isFirst() && "decl became canonical unexpectedly");
145  if (Link.is<NotKnownLatest>()) {
146  NotKnownLatest NKL = Link.get<NotKnownLatest>();
147  Link = KnownLatest(*reinterpret_cast<const ASTContext *>(
148  NKL.get<UninitializedLatest>()),
149  D);
150  } else {
151  auto Latest = Link.get<KnownLatest>();
152  Latest.set(D);
153  Link = Latest;
154  }
155  }
156 
157  void markIncomplete() { Link.get<KnownLatest>().markIncomplete(); }
158 
159  Decl *getLatestNotUpdated() const {
160  assert(isFirst() && "expected a canonical decl");
161  if (Link.is<NotKnownLatest>())
162  return nullptr;
163  return Link.get<KnownLatest>().getNotUpdated();
164  }
165  };
166 
167  static DeclLink PreviousDeclLink(decl_type *D) {
168  return DeclLink(DeclLink::PreviousLink, D);
169  }
170 
171  static DeclLink LatestDeclLink(const ASTContext &Ctx) {
172  return DeclLink(DeclLink::LatestLink, Ctx);
173  }
174 
175  /// Points to the next redeclaration in the chain.
176  ///
177  /// If isFirst() is false, this is a link to the previous declaration
178  /// of this same Decl. If isFirst() is true, this is the first
179  /// declaration and Link points to the latest declaration. For example:
180  ///
181  /// #1 int f(int x, int y = 1); // <pointer to #3, true>
182  /// #2 int f(int x = 0, int y); // <pointer to #1, false>
183  /// #3 int f(int x, int y) { return x + y; } // <pointer to #2, false>
184  ///
185  /// If there is only one declaration, it is <pointer to self, true>
187 
188  decl_type *First;
189 
190  decl_type *getNextRedeclaration() const {
191  return RedeclLink.getPrevious(static_cast<const decl_type *>(this));
192  }
193 
194 public:
195  friend class ASTDeclReader;
196  friend class ASTDeclWriter;
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.
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 
365 private:
366  friend struct llvm::DenseMapInfo<CanonicalDeclPtr<decl_type>>;
367 
368  decl_type *Ptr = nullptr;
369 };
370 
371 } // namespace clang
372 
373 namespace llvm {
374 
375 template <typename decl_type>
376 struct DenseMapInfo<clang::CanonicalDeclPtr<decl_type>> {
379 
381  // Construct our CanonicalDeclPtr this way because the regular constructor
382  // would dereference P.Ptr, which is not allowed.
384  P.Ptr = BaseInfo::getEmptyKey();
385  return P;
386  }
387 
390  P.Ptr = BaseInfo::getTombstoneKey();
391  return P;
392  }
393 
394  static unsigned getHashValue(const CanonicalDeclPtr &P) {
395  return BaseInfo::getHashValue(P);
396  }
397 
398  static bool isEqual(const CanonicalDeclPtr &LHS,
399  const CanonicalDeclPtr &RHS) {
400  return BaseInfo::isEqual(LHS, RHS);
401  }
402 };
403 
404 } // namespace llvm
405 
406 #endif // LLVM_CLANG_AST_REDECLARABLE_H
static const Decl * getCanonicalDecl(const Decl *D)
decl_type & operator*()
Definition: Redeclarable.h:362
DominatorTree GraphTraits specialization so the DominatorTree can be iterable by generic graph iterat...
Definition: Dominators.h:30
void setPreviousDecl(decl_type *PrevDecl)
Set the previous declaration.
Definition: Decl.h:4298
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:87
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:394
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:171
Provides common interface for the Decls that can be redeclared.
Definition: Redeclarable.h:85
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:398
friend bool operator==(redecl_iterator x, redecl_iterator y)
Definition: Redeclarable.h:283
const decl_type * getPreviousDecl() const
Definition: Redeclarable.h:209
decl_type * operator->()
Definition: Redeclarable.h:359
DeclLink RedeclLink
Points to the next redeclaration in the chain.
Definition: Redeclarable.h:186
decl_type * getFirstDecl()
Return the first declaration of this declaration or itself if this is the only declaration.
Definition: Redeclarable.h:319
CanonicalDeclPtr(decl_type *Ptr)
Definition: Redeclarable.h:351
const decl_type & operator*() const
Definition: Redeclarable.h:363
redecl_iterator redecls_begin() const
Definition: Redeclarable.h:301
const decl_type * getMostRecentDecl() const
Returns the most recent (re)declaration of this declaration.
Definition: Redeclarable.h:231
Iterates through all the redeclarations of the same decl.
Definition: Redeclarable.h:240
static DeclLink PreviousDeclLink(decl_type *D)
Definition: Redeclarable.h:167
Decl * getPrimaryMergedDecl(Decl *D)
Get the primary declaration for a declaration from an AST file.
Definition: Decl.cpp:76
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:216
decl_type * getPreviousDecl()
Return the previous declaration of this declaration or NULL if this is the first declaration.
Definition: Redeclarable.h:204
redecl_range redecls() const
Returns an iterator range for all the redeclarations of the same decl.
Definition: Redeclarable.h:295
Redeclarable(const ASTContext &Ctx)
Definition: Redeclarable.h:198
const decl_type * operator->() const
Definition: Redeclarable.h:360
bool isFirstDecl() const
True if this is the first declaration in its redeclaration chain.
Definition: Redeclarable.h:223
const decl_type * getFirstDecl() const
Return the first declaration of this declaration or itself if this is the only declaration.
Definition: Redeclarable.h:328
bool isFromASTFile() const
Determine whether this declaration came from an AST file (such as a precompiled header or module) rat...
Definition: DeclBase.h:695
__PTRDIFF_TYPE__ ptrdiff_t
A signed integer type that is the result of subtracting two pointers.
Definition: opencl-c.h:76
Dataflow Directional Tag Classes.
redecl_iterator redecls_end() const
Definition: Redeclarable.h:302
llvm::iterator_range< redecl_iterator > redecl_range
Definition: Redeclarable.h:291
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:313
friend bool operator!=(redecl_iterator x, redecl_iterator y)
Definition: Redeclarable.h:286
decl_type * getNextRedeclaration() const
Definition: Redeclarable.h:190
const decl_type * getFirstDecl() const
Return the first declaration of this declaration or itself if this is the only declaration.
Definition: Redeclarable.h:220
std::forward_iterator_tag iterator_category
Definition: Redeclarable.h:250
decl_type * getMostRecentDecl()
Returns the most recent (re)declaration of this declaration.
Definition: Redeclarable.h:226
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:336
A wrapper class around a pointer that always points to its canonical declaration. ...
Definition: Redeclarable.h:348