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