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