contrib/llvm/tools/clang/include/clang/AST/Redeclarable.h

   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
  25 namespace clang {
  26
  27 class ASTContext;
  28 class 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.
  83 template<typename decl_type>
  84 class Redeclarable {
  85 protected:
  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
 193 public:
 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.
 306 Decl *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.
 311 template<typename decl_type>
 312 class Mergeable {
 313 public:
 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.
 347 template <typename decl_type> class CanonicalDeclPtr {
 348 public:
 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
 371 private:
 372   friend struct llvm::DenseMapInfo<CanonicalDeclPtr<decl_type>>;
 373
 374   decl_type *Ptr = nullptr;
 375 };
 376
 377 } // namespace clang
 378
 379 namespace llvm {
 380
 381 template <typename decl_type>
 382 struct 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