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

   1 //===--- ASTTypeTraits.h ----------------------------------------*- 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 //  Provides a dynamic type identifier and a dynamically typed node container
  11 //  that can be used to store an AST base node at runtime in the same storage in
  12 //  a type safe way.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #ifndef LLVM_CLANG_AST_ASTTYPETRAITS_H
  17 #define LLVM_CLANG_AST_ASTTYPETRAITS_H
  18
  19 #include "clang/AST/ASTFwd.h"
  20 #include "clang/AST/Decl.h"
  21 #include "clang/AST/NestedNameSpecifier.h"
  22 #include "clang/AST/Stmt.h"
  23 #include "clang/AST/TemplateBase.h"
  24 #include "clang/AST/TypeLoc.h"
  25 #include "clang/Basic/LLVM.h"
  26 #include "llvm/ADT/DenseMapInfo.h"
  27 #include "llvm/Support/AlignOf.h"
  28
  29 namespace llvm {
  30
  31 class raw_ostream;
  32
  33 }
  34
  35 namespace clang {
  36
  37 struct PrintingPolicy;
  38
  39 namespace ast_type_traits {
  40
  41 /// \brief Kind identifier.
  42 ///
  43 /// It can be constructed from any node kind and allows for runtime type
  44 /// hierarchy checks.
  45 /// Use getFromNodeKind<T>() to construct them.
  46 class ASTNodeKind {
  47 public:
  48   /// \brief Empty identifier. It matches nothing.
  49   ASTNodeKind() : KindId(NKI_None) {}
  50
  51   /// \brief Construct an identifier for T.
  52   template <class T>
  53   static ASTNodeKind getFromNodeKind() {
  54     return ASTNodeKind(KindToKindId<T>::Id);
  55   }
  56
  57   /// \{
  58   /// \brief Construct an identifier for the dynamic type of the node
  59   static ASTNodeKind getFromNode(const Decl &D);
  60   static ASTNodeKind getFromNode(const Stmt &S);
  61   static ASTNodeKind getFromNode(const Type &T);
  62   /// \}
  63
  64   /// \brief Returns \c true if \c this and \c Other represent the same kind.
  65   bool isSame(ASTNodeKind Other) const;
  66
  67   /// \brief Returns \c true only for the default \c ASTNodeKind()
  68   bool isNone() const { return KindId == NKI_None; }
  69
  70   /// \brief Returns \c true if \c this is a base kind of (or same as) \c Other.
  71   /// \param Distance If non-null, used to return the distance between \c this
  72   /// and \c Other in the class hierarchy.
  73   bool isBaseOf(ASTNodeKind Other, unsigned *Distance = nullptr) const;
  74
  75   /// \brief String representation of the kind.
  76   StringRef asStringRef() const;
  77
  78   /// \brief Strict weak ordering for ASTNodeKind.
  79   bool operator<(const ASTNodeKind &Other) const {
  80     return KindId < Other.KindId;
  81   }
  82
  83   /// \brief Return the most derived type between \p Kind1 and \p Kind2.
  84   ///
  85   /// Return ASTNodeKind() if they are not related.
  86   static ASTNodeKind getMostDerivedType(ASTNodeKind Kind1, ASTNodeKind Kind2);
  87
  88   /// \brief Return the most derived common ancestor between Kind1 and Kind2.
  89   ///
  90   /// Return ASTNodeKind() if they are not related.
  91   static ASTNodeKind getMostDerivedCommonAncestor(ASTNodeKind Kind1,
  92                                                   ASTNodeKind Kind2);
  93
  94   /// \brief Hooks for using ASTNodeKind as a key in a DenseMap.
  95   struct DenseMapInfo {
  96     // ASTNodeKind() is a good empty key because it is represented as a 0.
  97     static inline ASTNodeKind getEmptyKey() { return ASTNodeKind(); }
  98     // NKI_NumberOfKinds is not a valid value, so it is good for a
  99     // tombstone key.
 100     static inline ASTNodeKind getTombstoneKey() {
 101       return ASTNodeKind(NKI_NumberOfKinds);
 102     }
 103     static unsigned getHashValue(const ASTNodeKind &Val) { return Val.KindId; }
 104     static bool isEqual(const ASTNodeKind &LHS, const ASTNodeKind &RHS) {
 105       return LHS.KindId == RHS.KindId;
 106     }
 107   };
 108
 109   /// Check if the given ASTNodeKind identifies a type that offers pointer
 110   /// identity. This is useful for the fast path in DynTypedNode.
 111   bool hasPointerIdentity() const {
 112     return KindId > NKI_LastKindWithoutPointerIdentity;
 113   }
 114
 115 private:
 116   /// \brief Kind ids.
 117   ///
 118   /// Includes all possible base and derived kinds.
 119   enum NodeKindId {
 120     NKI_None,
 121     NKI_TemplateArgument,
 122     NKI_NestedNameSpecifierLoc,
 123     NKI_QualType,
 124     NKI_TypeLoc,
 125     NKI_LastKindWithoutPointerIdentity = NKI_TypeLoc,
 126     NKI_CXXCtorInitializer,
 127     NKI_NestedNameSpecifier,
 128     NKI_Decl,
 129 #define DECL(DERIVED, BASE) NKI_##DERIVED##Decl,
 130 #include "clang/AST/DeclNodes.inc"
 131     NKI_Stmt,
 132 #define STMT(DERIVED, BASE) NKI_##DERIVED,
 133 #include "clang/AST/StmtNodes.inc"
 134     NKI_Type,
 135 #define TYPE(DERIVED, BASE) NKI_##DERIVED##Type,
 136 #include "clang/AST/TypeNodes.def"
 137     NKI_NumberOfKinds
 138   };
 139
 140   /// \brief Use getFromNodeKind<T>() to construct the kind.
 141   ASTNodeKind(NodeKindId KindId) : KindId(KindId) {}
 142
 143   /// \brief Returns \c true if \c Base is a base kind of (or same as) \c
 144   ///   Derived.
 145   /// \param Distance If non-null, used to return the distance between \c Base
 146   /// and \c Derived in the class hierarchy.
 147   static bool isBaseOf(NodeKindId Base, NodeKindId Derived, unsigned *Distance);
 148
 149   /// \brief Helper meta-function to convert a kind T to its enum value.
 150   ///
 151   /// This struct is specialized below for all known kinds.
 152   template <class T> struct KindToKindId {
 153     static const NodeKindId Id = NKI_None;
 154   };
 155   template <class T>
 156   struct KindToKindId<const T> : KindToKindId<T> {};
 157
 158   /// \brief Per kind info.
 159   struct KindInfo {
 160     /// \brief The id of the parent kind, or None if it has no parent.
 161     NodeKindId ParentId;
 162     /// \brief Name of the kind.
 163     const char *Name;
 164   };
 165   static const KindInfo AllKindInfo[NKI_NumberOfKinds];
 166
 167   NodeKindId KindId;
 168 };
 169
 170 #define KIND_TO_KIND_ID(Class)                                                 \
 171   template <> struct ASTNodeKind::KindToKindId<Class> {                        \
 172     static const NodeKindId Id = NKI_##Class;                                  \
 173   };
 174 KIND_TO_KIND_ID(CXXCtorInitializer)
 175 KIND_TO_KIND_ID(TemplateArgument)
 176 KIND_TO_KIND_ID(NestedNameSpecifier)
 177 KIND_TO_KIND_ID(NestedNameSpecifierLoc)
 178 KIND_TO_KIND_ID(QualType)
 179 KIND_TO_KIND_ID(TypeLoc)
 180 KIND_TO_KIND_ID(Decl)
 181 KIND_TO_KIND_ID(Stmt)
 182 KIND_TO_KIND_ID(Type)
 183 #define DECL(DERIVED, BASE) KIND_TO_KIND_ID(DERIVED##Decl)
 184 #include "clang/AST/DeclNodes.inc"
 185 #define STMT(DERIVED, BASE) KIND_TO_KIND_ID(DERIVED)
 186 #include "clang/AST/StmtNodes.inc"
 187 #define TYPE(DERIVED, BASE) KIND_TO_KIND_ID(DERIVED##Type)
 188 #include "clang/AST/TypeNodes.def"
 189 #undef KIND_TO_KIND_ID
 190
 191 inline raw_ostream &operator<<(raw_ostream &OS, ASTNodeKind K) {
 192   OS << K.asStringRef();
 193   return OS;
 194 }
 195
 196 /// \brief A dynamically typed AST node container.
 197 ///
 198 /// Stores an AST node in a type safe way. This allows writing code that
 199 /// works with different kinds of AST nodes, despite the fact that they don't
 200 /// have a common base class.
 201 ///
 202 /// Use \c create(Node) to create a \c DynTypedNode from an AST node,
 203 /// and \c get<T>() to retrieve the node as type T if the types match.
 204 ///
 205 /// See \c ASTNodeKind for which node base types are currently supported;
 206 /// You can create DynTypedNodes for all nodes in the inheritance hierarchy of
 207 /// the supported base types.
 208 class DynTypedNode {
 209 public:
 210   /// \brief Creates a \c DynTypedNode from \c Node.
 211   template <typename T>
 212   static DynTypedNode create(const T &Node) {
 213     return BaseConverter<T>::create(Node);
 214   }
 215
 216   /// \brief Retrieve the stored node as type \c T.
 217   ///
 218   /// Returns NULL if the stored node does not have a type that is
 219   /// convertible to \c T.
 220   ///
 221   /// For types that have identity via their pointer in the AST
 222   /// (like \c Stmt, \c Decl, \c Type and \c NestedNameSpecifier) the returned
 223   /// pointer points to the referenced AST node.
 224   /// For other types (like \c QualType) the value is stored directly
 225   /// in the \c DynTypedNode, and the returned pointer points at
 226   /// the storage inside DynTypedNode. For those nodes, do not
 227   /// use the pointer outside the scope of the DynTypedNode.
 228   template <typename T>
 229   const T *get() const {
 230     return BaseConverter<T>::get(NodeKind, Storage.buffer);
 231   }
 232
 233   /// \brief Retrieve the stored node as type \c T.
 234   ///
 235   /// Similar to \c get(), but asserts that the type is what we are expecting.
 236   template <typename T>
 237   const T &getUnchecked() const {
 238     return BaseConverter<T>::getUnchecked(NodeKind, Storage.buffer);
 239   }
 240
 241   ASTNodeKind getNodeKind() const { return NodeKind; }
 242
 243   /// \brief Returns a pointer that identifies the stored AST node.
 244   ///
 245   /// Note that this is not supported by all AST nodes. For AST nodes
 246   /// that don't have a pointer-defined identity inside the AST, this
 247   /// method returns NULL.
 248   const void *getMemoizationData() const {
 249     return NodeKind.hasPointerIdentity()
 250                ? *reinterpret_cast<void *const *>(Storage.buffer)
 251                : nullptr;
 252   }
 253
 254   /// \brief Prints the node to the given output stream.
 255   void print(llvm::raw_ostream &OS, const PrintingPolicy &PP) const;
 256
 257   /// \brief Dumps the node to the given output stream.
 258   void dump(llvm::raw_ostream &OS, SourceManager &SM) const;
 259
 260   /// \brief For nodes which represent textual entities in the source code,
 261   /// return their SourceRange.  For all other nodes, return SourceRange().
 262   SourceRange getSourceRange() const;
 263
 264   /// @{
 265   /// \brief Imposes an order on \c DynTypedNode.
 266   ///
 267   /// Supports comparison of nodes that support memoization.
 268   /// FIXME: Implement comparsion for other node types (currently
 269   /// only Stmt, Decl, Type and NestedNameSpecifier return memoization data).
 270   bool operator<(const DynTypedNode &Other) const {
 271     if (!NodeKind.isSame(Other.NodeKind))
 272       return NodeKind < Other.NodeKind;
 273
 274     if (ASTNodeKind::getFromNodeKind<QualType>().isSame(NodeKind))
 275       return getUnchecked<QualType>().getAsOpaquePtr() <
 276              Other.getUnchecked<QualType>().getAsOpaquePtr();
 277
 278     if (ASTNodeKind::getFromNodeKind<TypeLoc>().isSame(NodeKind)) {
 279       auto TLA = getUnchecked<TypeLoc>();
 280       auto TLB = Other.getUnchecked<TypeLoc>();
 281       return std::make_pair(TLA.getType().getAsOpaquePtr(),
 282                             TLA.getOpaqueData()) <
 283              std::make_pair(TLB.getType().getAsOpaquePtr(),
 284                             TLB.getOpaqueData());
 285     }
 286
 287     if (ASTNodeKind::getFromNodeKind<NestedNameSpecifierLoc>().isSame(
 288             NodeKind)) {
 289       auto NNSLA = getUnchecked<NestedNameSpecifierLoc>();
 290       auto NNSLB = Other.getUnchecked<NestedNameSpecifierLoc>();
 291       return std::make_pair(NNSLA.getNestedNameSpecifier(),
 292                             NNSLA.getOpaqueData()) <
 293              std::make_pair(NNSLB.getNestedNameSpecifier(),
 294                             NNSLB.getOpaqueData());
 295     }
 296
 297     assert(getMemoizationData() && Other.getMemoizationData());
 298     return getMemoizationData() < Other.getMemoizationData();
 299   }
 300   bool operator==(const DynTypedNode &Other) const {
 301     // DynTypedNode::create() stores the exact kind of the node in NodeKind.
 302     // If they contain the same node, their NodeKind must be the same.
 303     if (!NodeKind.isSame(Other.NodeKind))
 304       return false;
 305
 306     // FIXME: Implement for other types.
 307     if (ASTNodeKind::getFromNodeKind<QualType>().isSame(NodeKind))
 308       return getUnchecked<QualType>() == Other.getUnchecked<QualType>();
 309
 310     if (ASTNodeKind::getFromNodeKind<TypeLoc>().isSame(NodeKind))
 311       return getUnchecked<TypeLoc>() == Other.getUnchecked<TypeLoc>();
 312
 313     if (ASTNodeKind::getFromNodeKind<NestedNameSpecifierLoc>().isSame(NodeKind))
 314       return getUnchecked<NestedNameSpecifierLoc>() ==
 315              Other.getUnchecked<NestedNameSpecifierLoc>();
 316
 317     assert(getMemoizationData() && Other.getMemoizationData());
 318     return getMemoizationData() == Other.getMemoizationData();
 319   }
 320   bool operator!=(const DynTypedNode &Other) const {
 321     return !operator==(Other);
 322   }
 323   /// @}
 324
 325   /// \brief Hooks for using DynTypedNode as a key in a DenseMap.
 326   struct DenseMapInfo {
 327     static inline DynTypedNode getEmptyKey() {
 328       DynTypedNode Node;
 329       Node.NodeKind = ASTNodeKind::DenseMapInfo::getEmptyKey();
 330       return Node;
 331     }
 332     static inline DynTypedNode getTombstoneKey() {
 333       DynTypedNode Node;
 334       Node.NodeKind = ASTNodeKind::DenseMapInfo::getTombstoneKey();
 335       return Node;
 336     }
 337     static unsigned getHashValue(const DynTypedNode &Val) {
 338       // FIXME: Add hashing support for the remaining types.
 339       if (ASTNodeKind::getFromNodeKind<TypeLoc>().isSame(Val.NodeKind)) {
 340         auto TL = Val.getUnchecked<TypeLoc>();
 341         return llvm::hash_combine(TL.getType().getAsOpaquePtr(),
 342                                   TL.getOpaqueData());
 343       }
 344
 345       if (ASTNodeKind::getFromNodeKind<NestedNameSpecifierLoc>().isSame(
 346               Val.NodeKind)) {
 347         auto NNSL = Val.getUnchecked<NestedNameSpecifierLoc>();
 348         return llvm::hash_combine(NNSL.getNestedNameSpecifier(),
 349                                   NNSL.getOpaqueData());
 350       }
 351
 352       assert(Val.getMemoizationData());
 353       return llvm::hash_value(Val.getMemoizationData());
 354     }
 355     static bool isEqual(const DynTypedNode &LHS, const DynTypedNode &RHS) {
 356       auto Empty = ASTNodeKind::DenseMapInfo::getEmptyKey();
 357       auto TombStone = ASTNodeKind::DenseMapInfo::getTombstoneKey();
 358       return (ASTNodeKind::DenseMapInfo::isEqual(LHS.NodeKind, Empty) &&
 359               ASTNodeKind::DenseMapInfo::isEqual(RHS.NodeKind, Empty)) ||
 360              (ASTNodeKind::DenseMapInfo::isEqual(LHS.NodeKind, TombStone) &&
 361               ASTNodeKind::DenseMapInfo::isEqual(RHS.NodeKind, TombStone)) ||
 362              LHS == RHS;
 363     }
 364   };
 365
 366 private:
 367   /// \brief Takes care of converting from and to \c T.
 368   template <typename T, typename EnablerT = void> struct BaseConverter;
 369
 370   /// \brief Converter that uses dyn_cast<T> from a stored BaseT*.
 371   template <typename T, typename BaseT> struct DynCastPtrConverter {
 372     static const T *get(ASTNodeKind NodeKind, const char Storage[]) {
 373       if (ASTNodeKind::getFromNodeKind<T>().isBaseOf(NodeKind))
 374         return &getUnchecked(NodeKind, Storage);
 375       return nullptr;
 376     }
 377     static const T &getUnchecked(ASTNodeKind NodeKind, const char Storage[]) {
 378       assert(ASTNodeKind::getFromNodeKind<T>().isBaseOf(NodeKind));
 379       return *cast<T>(static_cast<const BaseT *>(
 380           *reinterpret_cast<const void *const *>(Storage)));
 381     }
 382     static DynTypedNode create(const BaseT &Node) {
 383       DynTypedNode Result;
 384       Result.NodeKind = ASTNodeKind::getFromNode(Node);
 385       new (Result.Storage.buffer) const void *(&Node);
 386       return Result;
 387     }
 388   };
 389
 390   /// \brief Converter that stores T* (by pointer).
 391   template <typename T> struct PtrConverter {
 392     static const T *get(ASTNodeKind NodeKind, const char Storage[]) {
 393       if (ASTNodeKind::getFromNodeKind<T>().isSame(NodeKind))
 394         return &getUnchecked(NodeKind, Storage);
 395       return nullptr;
 396     }
 397     static const T &getUnchecked(ASTNodeKind NodeKind, const char Storage[]) {
 398       assert(ASTNodeKind::getFromNodeKind<T>().isSame(NodeKind));
 399       return *static_cast<const T *>(
 400           *reinterpret_cast<const void *const *>(Storage));
 401     }
 402     static DynTypedNode create(const T &Node) {
 403       DynTypedNode Result;
 404       Result.NodeKind = ASTNodeKind::getFromNodeKind<T>();
 405       new (Result.Storage.buffer) const void *(&Node);
 406       return Result;
 407     }
 408   };
 409
 410   /// \brief Converter that stores T (by value).
 411   template <typename T> struct ValueConverter {
 412     static const T *get(ASTNodeKind NodeKind, const char Storage[]) {
 413       if (ASTNodeKind::getFromNodeKind<T>().isSame(NodeKind))
 414         return reinterpret_cast<const T *>(Storage);
 415       return nullptr;
 416     }
 417     static const T &getUnchecked(ASTNodeKind NodeKind, const char Storage[]) {
 418       assert(ASTNodeKind::getFromNodeKind<T>().isSame(NodeKind));
 419       return *reinterpret_cast<const T *>(Storage);
 420     }
 421     static DynTypedNode create(const T &Node) {
 422       DynTypedNode Result;
 423       Result.NodeKind = ASTNodeKind::getFromNodeKind<T>();
 424       new (Result.Storage.buffer) T(Node);
 425       return Result;
 426     }
 427   };
 428
 429   ASTNodeKind NodeKind;
 430
 431   /// \brief Stores the data of the node.
 432   ///
 433   /// Note that we can store \c Decls, \c Stmts, \c Types,
 434   /// \c NestedNameSpecifiers and \c CXXCtorInitializer by pointer as they are
 435   /// guaranteed to be unique pointers pointing to dedicated storage in the AST.
 436   /// \c QualTypes, \c NestedNameSpecifierLocs, \c TypeLocs and
 437   /// \c TemplateArguments on the other hand do not have storage or unique
 438   /// pointers and thus need to be stored by value.
 439   llvm::AlignedCharArrayUnion<const void *, TemplateArgument,
 440                               NestedNameSpecifierLoc, QualType,
 441                               TypeLoc> Storage;
 442 };
 443
 444 template <typename T>
 445 struct DynTypedNode::BaseConverter<
 446     T, typename std::enable_if<std::is_base_of<Decl, T>::value>::type>
 447     : public DynCastPtrConverter<T, Decl> {};
 448
 449 template <typename T>
 450 struct DynTypedNode::BaseConverter<
 451     T, typename std::enable_if<std::is_base_of<Stmt, T>::value>::type>
 452     : public DynCastPtrConverter<T, Stmt> {};
 453
 454 template <typename T>
 455 struct DynTypedNode::BaseConverter<
 456     T, typename std::enable_if<std::is_base_of<Type, T>::value>::type>
 457     : public DynCastPtrConverter<T, Type> {};
 458
 459 template <>
 460 struct DynTypedNode::BaseConverter<
 461     NestedNameSpecifier, void> : public PtrConverter<NestedNameSpecifier> {};
 462
 463 template <>
 464 struct DynTypedNode::BaseConverter<
 465     CXXCtorInitializer, void> : public PtrConverter<CXXCtorInitializer> {};
 466
 467 template <>
 468 struct DynTypedNode::BaseConverter<
 469     TemplateArgument, void> : public ValueConverter<TemplateArgument> {};
 470
 471 template <>
 472 struct DynTypedNode::BaseConverter<
 473     NestedNameSpecifierLoc,
 474     void> : public ValueConverter<NestedNameSpecifierLoc> {};
 475
 476 template <>
 477 struct DynTypedNode::BaseConverter<QualType,
 478                                    void> : public ValueConverter<QualType> {};
 479
 480 template <>
 481 struct DynTypedNode::BaseConverter<
 482     TypeLoc, void> : public ValueConverter<TypeLoc> {};
 483
 484 // The only operation we allow on unsupported types is \c get.
 485 // This allows to conveniently use \c DynTypedNode when having an arbitrary
 486 // AST node that is not supported, but prevents misuse - a user cannot create
 487 // a DynTypedNode from arbitrary types.
 488 template <typename T, typename EnablerT> struct DynTypedNode::BaseConverter {
 489   static const T *get(ASTNodeKind NodeKind, const char Storage[]) {
 490     return NULL;
 491   }
 492 };
 493
 494 } // end namespace ast_type_traits
 495 } // end namespace clang
 496
 497 namespace llvm {
 498
 499 template <>
 500 struct DenseMapInfo<clang::ast_type_traits::ASTNodeKind>
 501     : clang::ast_type_traits::ASTNodeKind::DenseMapInfo {};
 502
 503 template <>
 504 struct DenseMapInfo<clang::ast_type_traits::DynTypedNode>
 505     : clang::ast_type_traits::DynTypedNode::DenseMapInfo {};
 506
 507 }  // end namespace llvm
 508
 509 #endif