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