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/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*,
  86                                       &ExternalASTSource::CompleteRedeclChain>
  87                                           KnownLatest;
  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:
 104     enum PreviousTag { PreviousLink };
 105     enum LatestTag { LatestLink };
 106
 107     DeclLink(LatestTag, const ASTContext &Ctx)
 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>
 184   DeclLink RedeclLink;
 185   decl_type *First;
 186
 187   decl_type *getNextRedeclaration() const {
 188     return RedeclLink.getNext(static_cast<const decl_type *>(this));
 189   }
 190
 191 public:
 192  Redeclarable(const ASTContext &Ctx)
 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.
 233   class redecl_iterator {
 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;
 244     typedef std::ptrdiff_t            difference_type;
 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
 253     redecl_iterator& operator++() {
 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
 271     redecl_iterator operator++(int) {
 272       redecl_iterator tmp(*this);
 273       ++(*this);
 274       return tmp;
 275     }
 276
 277     friend bool operator==(redecl_iterator x, redecl_iterator y) {
 278       return x.Current == y.Current;
 279     }
 280     friend bool operator!=(redecl_iterator x, redecl_iterator y) {
 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.
 304 Decl *getPrimaryMergedDecl(Decl *D);
 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:
 312   Mergeable() {}
 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>> {
 372   using CanonicalDeclPtr = clang::CanonicalDeclPtr<decl_type>;
 373   using BaseInfo = DenseMapInfo<decl_type *>;
 374
 375   static CanonicalDeclPtr getEmptyKey() {
 376     // Construct our CanonicalDeclPtr this way because the regular constructor
 377     // would dereference P.Ptr, which is not allowed.
 378     CanonicalDeclPtr P;
 379     P.Ptr = BaseInfo::getEmptyKey();
 380     return P;
 381   }
 382
 383   static CanonicalDeclPtr getTombstoneKey() {
 384     CanonicalDeclPtr P;
 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