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
16#include "clang/AST/ExternalASTSource.h"
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
25namespace clang {
26
27class ASTContext;
28class 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.
83template<typename decl_type>
84class Redeclarable {
85protected:
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 *,
91                                  &ExternalASTSource::CompleteRedeclChain>;
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:
108    enum PreviousTag { PreviousLink };
109    enum LatestTag { LatestLink };
110
111    DeclLink(LatestTag, const ASTContext &Ctx)
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>
185  DeclLink RedeclLink;
186
187  decl_type *First;
188
189  decl_type *getNextRedeclaration() const {
190    return RedeclLink.getPrevious(static_cast<const decl_type *>(this));
191  }
192
193public:
194  friend class ASTDeclReader;
195  friend class ASTDeclWriter;
196
197  Redeclarable(const ASTContext &Ctx)
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.
239  class redecl_iterator {
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;
250    using difference_type = std::ptrdiff_t;
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
258    redecl_iterator& operator++() {
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
276    redecl_iterator operator++(int) {
277      redecl_iterator tmp(*this);
278      ++(*this);
279      return tmp;
280    }
281
282    friend bool operator==(redecl_iterator x, redecl_iterator y) {
283      return x.Current == y.Current;
284    }
285    friend bool operator!=(redecl_iterator x, redecl_iterator y) {
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).
294  redecl_range redecls() const {
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.
306Decl *getPrimaryMergedDecl(Decl *D);
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.
311template<typename decl_type>
312class Mergeable {
313public:
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.
347template <typename decl_type> class CanonicalDeclPtr {
348public:
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
364  friend bool operator==(CanonicalDeclPtr LHS, CanonicalDeclPtr RHS) {
365    return LHS.Ptr == RHS.Ptr;
366  }
367  friend bool operator!=(CanonicalDeclPtr LHS, CanonicalDeclPtr RHS) {
368    return LHS.Ptr != RHS.Ptr;
369  }
370
371private:
372  friend struct llvm::DenseMapInfo<CanonicalDeclPtr<decl_type>>;
373
374  decl_type *Ptr = nullptr;
375};
376
377} // namespace clang
378
379namespace llvm {
380
381template <typename decl_type>
382struct DenseMapInfo<clang::CanonicalDeclPtr<decl_type>> {
383  using CanonicalDeclPtr = clang::CanonicalDeclPtr<decl_type>;
384  using BaseInfo = DenseMapInfo<decl_type *>;
385
386  static CanonicalDeclPtr getEmptyKey() {
387    // Construct our CanonicalDeclPtr this way because the regular constructor
388    // would dereference P.Ptr, which is not allowed.
389    CanonicalDeclPtr P;
390    P.Ptr = BaseInfo::getEmptyKey();
391    return P;
392  }
393
394  static CanonicalDeclPtr getTombstoneKey() {
395    CanonicalDeclPtr P;
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
413