clang  6.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 an "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 // - To make matters confusing, the DeclLink type uses the term "next"
52 // for its pointer-storage internally (thus functions like
53 // NextIsPrevious). It's easiest to just ignore the implementation of
54 // DeclLink when making sense of the redeclaration chain.
55 //
56 // - There's also a "definition" link for several types of
57 // redeclarable, where only one definition should exist at any given
58 // time (and the defn pointer is stored in the decl's "data" which
59 // is copied to every element on the chain when it's changed).
60 //
61 // Here is some ASCII art:
62 //
63 // "first" "latest"
64 // "canonical" "most recent"
65 // +------------+ first +--------------+
66 // | | <--------------------------- | |
67 // | | | |
68 // | | | |
69 // | | +--------------+ | |
70 // | | first | | | |
71 // | | <---- | | | |
72 // | | | | | |
73 // | @class A | link | @interface A | link | @class A |
74 // | seen first | <---- | seen second | <---- | seen third |
75 // | | | | | |
76 // +------------+ +--------------+ +--------------+
77 // | data | defn | data | defn | data |
78 // | | ----> | | <---- | |
79 // +------------+ +--------------+ +--------------+
80 // | | ^ ^
81 // | |defn | |
82 // | link +-----+ |
83 // +-->-------------------------------------------+
84 
85 /// \brief Provides common interface for the Decls that can be redeclared.
86 template<typename decl_type>
87 class Redeclarable {
88 protected:
89  class DeclLink {
90  /// A pointer to a known latest declaration, either statically known or
91  /// generationally updated as decls are added by an external source.
92  using KnownLatest =
93  LazyGenerationalUpdatePtr<const Decl *, Decl *,
95 
96  /// We store a pointer to the ASTContext in the UninitializedLatest
97  /// pointer, but to avoid circular type dependencies when we steal the low
98  /// bits of this pointer, we use a raw void* here.
99  using UninitializedLatest = const void *;
100 
101  using Previous = Decl *;
102 
103  /// A pointer to either an uninitialized latest declaration (where either
104  /// we've not yet set the previous decl or there isn't one), or to a known
105  /// previous declaration.
106  using NotKnownLatest = llvm::PointerUnion<Previous, UninitializedLatest>;
107 
108  mutable llvm::PointerUnion<NotKnownLatest, KnownLatest> Next;
109 
110  public:
113 
115  : Next(NotKnownLatest(reinterpret_cast<UninitializedLatest>(&Ctx))) {}
116  DeclLink(PreviousTag, decl_type *D) : Next(NotKnownLatest(Previous(D))) {}
117 
118  bool NextIsPrevious() const {
119  return Next.is<NotKnownLatest>() &&
120  // FIXME: 'template' is required on the next line due to an
121  // apparent clang bug.
122  Next.get<NotKnownLatest>().template is<Previous>();
123  }
124 
125  bool NextIsLatest() const { return !NextIsPrevious(); }
126 
127  decl_type *getNext(const decl_type *D) const {
128  if (Next.is<NotKnownLatest>()) {
129  NotKnownLatest NKL = Next.get<NotKnownLatest>();
130  if (NKL.is<Previous>())
131  return static_cast<decl_type*>(NKL.get<Previous>());
132 
133  // Allocate the generational 'most recent' cache now, if needed.
134  Next = KnownLatest(*reinterpret_cast<const ASTContext *>(
135  NKL.get<UninitializedLatest>()),
136  const_cast<decl_type *>(D));
137  }
138 
139  return static_cast<decl_type*>(Next.get<KnownLatest>().get(D));
140  }
141 
142  void setPrevious(decl_type *D) {
143  assert(NextIsPrevious() && "decl became non-canonical unexpectedly");
144  Next = Previous(D);
145  }
146 
147  void setLatest(decl_type *D) {
148  assert(NextIsLatest() && "decl became canonical unexpectedly");
149  if (Next.is<NotKnownLatest>()) {
150  NotKnownLatest NKL = Next.get<NotKnownLatest>();
151  Next = KnownLatest(*reinterpret_cast<const ASTContext *>(
152  NKL.get<UninitializedLatest>()),
153  D);
154  } else {
155  auto Latest = Next.get<KnownLatest>();
156  Latest.set(D);
157  Next = Latest;
158  }
159  }
160 
161  void markIncomplete() { Next.get<KnownLatest>().markIncomplete(); }
162 
163  Decl *getLatestNotUpdated() const {
164  assert(NextIsLatest() && "expected a canonical decl");
165  if (Next.is<NotKnownLatest>())
166  return nullptr;
167  return Next.get<KnownLatest>().getNotUpdated();
168  }
169  };
170 
171  static DeclLink PreviousDeclLink(decl_type *D) {
172  return DeclLink(DeclLink::PreviousLink, D);
173  }
174 
175  static DeclLink LatestDeclLink(const ASTContext &Ctx) {
176  return DeclLink(DeclLink::LatestLink, Ctx);
177  }
178 
179  /// \brief Points to the next redeclaration in the chain.
180  ///
181  /// If NextIsPrevious() is true, this is a link to the previous declaration
182  /// of this same Decl. If NextIsLatest() is true, this is the first
183  /// declaration and Link points to the latest declaration. For example:
184  ///
185  /// #1 int f(int x, int y = 1); // <pointer to #3, true>
186  /// #2 int f(int x = 0, int y); // <pointer to #1, false>
187  /// #3 int f(int x, int y) { return x + y; } // <pointer to #2, false>
188  ///
189  /// If there is only one declaration, it is <pointer to self, true>
191 
192  decl_type *First;
193 
194  decl_type *getNextRedeclaration() const {
195  return RedeclLink.getNext(static_cast<const decl_type *>(this));
196  }
197 
198 public:
199  friend class ASTDeclReader;
200  friend class ASTDeclWriter;
201 
203  : RedeclLink(LatestDeclLink(Ctx)),
204  First(static_cast<decl_type *>(this)) {}
205 
206  /// \brief Return the previous declaration of this declaration or NULL if this
207  /// is the first declaration.
208  decl_type *getPreviousDecl() {
209  if (RedeclLink.NextIsPrevious())
210  return getNextRedeclaration();
211  return nullptr;
212  }
213  const decl_type *getPreviousDecl() const {
214  return const_cast<decl_type *>(
215  static_cast<const decl_type*>(this))->getPreviousDecl();
216  }
217 
218  /// \brief Return the first declaration of this declaration or itself if this
219  /// is the only declaration.
220  decl_type *getFirstDecl() { return First; }
221 
222  /// \brief Return the first declaration of this declaration or itself if this
223  /// is the only declaration.
224  const decl_type *getFirstDecl() const { return First; }
225 
226  /// \brief True if this is the first declaration in its redeclaration chain.
227  bool isFirstDecl() const { return RedeclLink.NextIsLatest(); }
228 
229  /// \brief Returns the most recent (re)declaration of this declaration.
230  decl_type *getMostRecentDecl() {
231  return getFirstDecl()->getNextRedeclaration();
232  }
233 
234  /// \brief Returns the most recent (re)declaration of this declaration.
235  const decl_type *getMostRecentDecl() const {
236  return getFirstDecl()->getNextRedeclaration();
237  }
238 
239  /// \brief Set the previous declaration. If PrevDecl is NULL, set this as the
240  /// first and only declaration.
241  void setPreviousDecl(decl_type *PrevDecl);
242 
243  /// \brief Iterates through all the redeclarations of the same decl.
245  /// Current - The current declaration.
246  decl_type *Current = nullptr;
247  decl_type *Starter;
248  bool PassedFirst = false;
249 
250  public:
251  using value_type = decl_type *;
252  using reference = decl_type *;
253  using pointer = decl_type *;
254  using iterator_category = std::forward_iterator_tag;
256 
257  redecl_iterator() = default;
258  explicit redecl_iterator(decl_type *C) : Current(C), Starter(C) {}
259 
260  reference operator*() const { return Current; }
261  pointer operator->() const { return Current; }
262 
264  assert(Current && "Advancing while iterator has reached end");
265  // Sanity check to avoid infinite loop on invalid redecl chain.
266  if (Current->isFirstDecl()) {
267  if (PassedFirst) {
268  assert(0 && "Passed first decl twice, invalid redecl chain!");
269  Current = nullptr;
270  return *this;
271  }
272  PassedFirst = true;
273  }
274 
275  // Get either previous decl or latest decl.
276  decl_type *Next = Current->getNextRedeclaration();
277  Current = (Next != Starter) ? Next : nullptr;
278  return *this;
279  }
280 
282  redecl_iterator tmp(*this);
283  ++(*this);
284  return tmp;
285  }
286 
288  return x.Current == y.Current;
289  }
291  return x.Current != y.Current;
292  }
293  };
294 
295  using redecl_range = llvm::iterator_range<redecl_iterator>;
296 
297  /// \brief Returns an iterator range for all the redeclarations of the same
298  /// decl. It will iterate at least once (when this decl is the only one).
300  return redecl_range(redecl_iterator(const_cast<decl_type *>(
301  static_cast<const decl_type *>(this))),
302  redecl_iterator());
303  }
304 
305  redecl_iterator redecls_begin() const { return redecls().begin(); }
306  redecl_iterator redecls_end() const { return redecls().end(); }
307 };
308 
309 /// \brief Get the primary declaration for a declaration from an AST file. That
310 /// will be the first-loaded declaration.
312 
313 /// \brief Provides common interface for the Decls that cannot be redeclared,
314 /// but can be merged if the same declaration is brought in from multiple
315 /// modules.
316 template<typename decl_type>
317 class Mergeable {
318 public:
319  Mergeable() = default;
320 
321  /// \brief Return the first declaration of this declaration or itself if this
322  /// is the only declaration.
323  decl_type *getFirstDecl() {
324  decl_type *D = static_cast<decl_type*>(this);
325  if (!D->isFromASTFile())
326  return D;
327  return cast<decl_type>(getPrimaryMergedDecl(const_cast<decl_type*>(D)));
328  }
329 
330  /// \brief Return the first declaration of this declaration or itself if this
331  /// is the only declaration.
332  const decl_type *getFirstDecl() const {
333  const decl_type *D = static_cast<const decl_type*>(this);
334  if (!D->isFromASTFile())
335  return D;
336  return cast<decl_type>(getPrimaryMergedDecl(const_cast<decl_type*>(D)));
337  }
338 
339  /// \brief Returns true if this is the first declaration.
340  bool isFirstDecl() const { return getFirstDecl() == this; }
341 };
342 
343 /// A wrapper class around a pointer that always points to its canonical
344 /// declaration.
345 ///
346 /// CanonicalDeclPtr<decl_type> behaves just like decl_type*, except we call
347 /// decl_type::getCanonicalDecl() on construction.
348 ///
349 /// This is useful for hashtables that you want to be keyed on a declaration's
350 /// canonical decl -- if you use CanonicalDeclPtr as the key, you don't need to
351 /// remember to call getCanonicalDecl() everywhere.
352 template <typename decl_type> class CanonicalDeclPtr {
353 public:
354  CanonicalDeclPtr() = default;
355  CanonicalDeclPtr(decl_type *Ptr)
356  : Ptr(Ptr ? Ptr->getCanonicalDecl() : nullptr) {}
357  CanonicalDeclPtr(const CanonicalDeclPtr &) = default;
358  CanonicalDeclPtr &operator=(const CanonicalDeclPtr &) = default;
359 
360  operator decl_type *() { return Ptr; }
361  operator const decl_type *() const { return Ptr; }
362 
363  decl_type *operator->() { return Ptr; }
364  const decl_type *operator->() const { return Ptr; }
365 
366  decl_type &operator*() { return *Ptr; }
367  const decl_type &operator*() const { return *Ptr; }
368 
369 private:
370  friend struct llvm::DenseMapInfo<CanonicalDeclPtr<decl_type>>;
371 
372  decl_type *Ptr = nullptr;
373 };
374 
375 } // namespace clang
376 
377 namespace llvm {
378 
379 template <typename decl_type>
380 struct DenseMapInfo<clang::CanonicalDeclPtr<decl_type>> {
383 
385  // Construct our CanonicalDeclPtr this way because the regular constructor
386  // would dereference P.Ptr, which is not allowed.
388  P.Ptr = BaseInfo::getEmptyKey();
389  return P;
390  }
391 
394  P.Ptr = BaseInfo::getTombstoneKey();
395  return P;
396  }
397 
398  static unsigned getHashValue(const CanonicalDeclPtr &P) {
399  return BaseInfo::getHashValue(P);
400  }
401 
402  static bool isEqual(const CanonicalDeclPtr &LHS,
403  const CanonicalDeclPtr &RHS) {
404  return BaseInfo::isEqual(LHS, RHS);
405  }
406 };
407 
408 } // namespace llvm
409 
410 #endif // LLVM_CLANG_AST_REDECLARABLE_H
static const Decl * getCanonicalDecl(const Decl *D)
decl_type & operator*()
Definition: Redeclarable.h:366
DominatorTree GraphTraits specialization so the DominatorTree can be iterable by generic graph iterat...
Definition: Dominators.h:26
void setPreviousDecl(decl_type *PrevDecl)
Set the previous declaration.
Definition: Decl.h:4105
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:86
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:398
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:175
Provides common interface for the Decls that can be redeclared.
Definition: Redeclarable.h:87
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:149
static bool isEqual(const CanonicalDeclPtr &LHS, const CanonicalDeclPtr &RHS)
Definition: Redeclarable.h:402
friend bool operator==(redecl_iterator x, redecl_iterator y)
Definition: Redeclarable.h:287
const decl_type * getPreviousDecl() const
Definition: Redeclarable.h:213
decl_type * operator->()
Definition: Redeclarable.h:363
DeclLink RedeclLink
Points to the next redeclaration in the chain.
Definition: Redeclarable.h:190
decl_type * getFirstDecl()
Return the first declaration of this declaration or itself if this is the only declaration.
Definition: Redeclarable.h:323
CanonicalDeclPtr(decl_type *Ptr)
Definition: Redeclarable.h:355
const decl_type & operator*() const
Definition: Redeclarable.h:367
redecl_iterator redecls_begin() const
Definition: Redeclarable.h:305
const decl_type * getMostRecentDecl() const
Returns the most recent (re)declaration of this declaration.
Definition: Redeclarable.h:235
Iterates through all the redeclarations of the same decl.
Definition: Redeclarable.h:244
static DeclLink PreviousDeclLink(decl_type *D)
Definition: Redeclarable.h:171
Decl * getPrimaryMergedDecl(Decl *D)
Get the primary declaration for a declaration from an AST file.
Definition: Decl.cpp:74
decl_type * getFirstDecl()
Return the first declaration of this declaration or itself if this is the only declaration.
Definition: Redeclarable.h:220
decl_type * getPreviousDecl()
Return the previous declaration of this declaration or NULL if this is the first declaration.
Definition: Redeclarable.h:208
redecl_range redecls() const
Returns an iterator range for all the redeclarations of the same decl.
Definition: Redeclarable.h:299
Redeclarable(const ASTContext &Ctx)
Definition: Redeclarable.h:202
const decl_type * operator->() const
Definition: Redeclarable.h:364
bool isFirstDecl() const
True if this is the first declaration in its redeclaration chain.
Definition: Redeclarable.h:227
const decl_type * getFirstDecl() const
Return the first declaration of this declaration or itself if this is the only declaration.
Definition: Redeclarable.h:332
__PTRDIFF_TYPE__ ptrdiff_t
A signed integer type that is the result of subtracting two pointers.
Definition: opencl-c.h:68
Dataflow Directional Tag Classes.
redecl_iterator redecls_end() const
Definition: Redeclarable.h:306
llvm::iterator_range< redecl_iterator > redecl_range
Definition: Redeclarable.h:295
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:317
friend bool operator!=(redecl_iterator x, redecl_iterator y)
Definition: Redeclarable.h:290
decl_type * getNextRedeclaration() const
Definition: Redeclarable.h:194
const decl_type * getFirstDecl() const
Return the first declaration of this declaration or itself if this is the only declaration.
Definition: Redeclarable.h:224
std::forward_iterator_tag iterator_category
Definition: Redeclarable.h:254
decl_type * getMostRecentDecl()
Returns the most recent (re)declaration of this declaration.
Definition: Redeclarable.h:230
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:340
A wrapper class around a pointer that always points to its canonical declaration. ...
Definition: Redeclarable.h:352