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

   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/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 *,
  94                                   &ExternalASTSource::CompleteRedeclChain>;
  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:
 111     enum PreviousTag { PreviousLink };
 112     enum LatestTag { LatestLink };
 113
 114     DeclLink(LatestTag, const ASTContext &Ctx)
 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>
 190   DeclLink RedeclLink;
 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
 202   Redeclarable(const ASTContext &Ctx)
 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.
 244   class redecl_iterator {
 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;
 255     using difference_type = std::ptrdiff_t;
 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
 263     redecl_iterator& operator++() {
 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
 281     redecl_iterator operator++(int) {
 282       redecl_iterator tmp(*this);
 283       ++(*this);
 284       return tmp;
 285     }
 286
 287     friend bool operator==(redecl_iterator x, redecl_iterator y) {
 288       return x.Current == y.Current;
 289     }
 290     friend bool operator!=(redecl_iterator x, redecl_iterator y) {
 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).
 299   redecl_range redecls() const {
 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.
 311 Decl *getPrimaryMergedDecl(Decl *D);
 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>> {
 381   using CanonicalDeclPtr = clang::CanonicalDeclPtr<decl_type>;
 382   using BaseInfo = DenseMapInfo<decl_type *>;
 383
 384   static CanonicalDeclPtr getEmptyKey() {
 385     // Construct our CanonicalDeclPtr this way because the regular constructor
 386     // would dereference P.Ptr, which is not allowed.
 387     CanonicalDeclPtr P;
 388     P.Ptr = BaseInfo::getEmptyKey();
 389     return P;
 390   }
 391
 392   static CanonicalDeclPtr getTombstoneKey() {
 393     CanonicalDeclPtr P;
 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