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 private:
 110   /// \brief Kind ids.
 111   ///
 112   /// Includes all possible base and derived kinds.
 113   enum NodeKindId {
 114     NKI_None,
 115     NKI_CXXCtorInitializer,
 116     NKI_TemplateArgument,
 117     NKI_NestedNameSpecifier,
 118     NKI_NestedNameSpecifierLoc,
 119     NKI_QualType,
 120     NKI_TypeLoc,
 121     NKI_Decl,
 122 #define DECL(DERIVED, BASE) NKI_##DERIVED##Decl,
 123 #include "clang/AST/DeclNodes.inc"
 124     NKI_Stmt,
 125 #define STMT(DERIVED, BASE) NKI_##DERIVED,
 126 #include "clang/AST/StmtNodes.inc"
 127     NKI_Type,
 128 #define TYPE(DERIVED, BASE) NKI_##DERIVED##Type,
 129 #include "clang/AST/TypeNodes.def"
 130     NKI_NumberOfKinds
 131   };
 132
 133   /// \brief Use getFromNodeKind<T>() to construct the kind.
 134   ASTNodeKind(NodeKindId KindId) : KindId(KindId) {}
 135
 136   /// \brief Returns \c true if \c Base is a base kind of (or same as) \c
 137   ///   Derived.
 138   /// \param Distance If non-null, used to return the distance between \c Base
 139   /// and \c Derived in the class hierarchy.
 140   static bool isBaseOf(NodeKindId Base, NodeKindId Derived, unsigned *Distance);
 141
 142   /// \brief Helper meta-function to convert a kind T to its enum value.
 143   ///
 144   /// This struct is specialized below for all known kinds.
 145   template <class T> struct KindToKindId {
 146     static const NodeKindId Id = NKI_None;
 147   };
 148   template <class T>
 149   struct KindToKindId<const T> : KindToKindId<T> {};
 150
 151   /// \brief Per kind info.
 152   struct KindInfo {
 153     /// \brief The id of the parent kind, or None if it has no parent.
 154     NodeKindId ParentId;
 155     /// \brief Name of the kind.
 156     const char *Name;
 157   };
 158   static const KindInfo AllKindInfo[NKI_NumberOfKinds];
 159
 160   NodeKindId KindId;
 161 };
 162
 163 #define KIND_TO_KIND_ID(Class)                                                 \
 164   template <> struct ASTNodeKind::KindToKindId<Class> {                        \
 165     static const NodeKindId Id = NKI_##Class;                                  \
 166   };
 167 KIND_TO_KIND_ID(CXXCtorInitializer)
 168 KIND_TO_KIND_ID(TemplateArgument)
 169 KIND_TO_KIND_ID(NestedNameSpecifier)
 170 KIND_TO_KIND_ID(NestedNameSpecifierLoc)
 171 KIND_TO_KIND_ID(QualType)
 172 KIND_TO_KIND_ID(TypeLoc)
 173 KIND_TO_KIND_ID(Decl)
 174 KIND_TO_KIND_ID(Stmt)
 175 KIND_TO_KIND_ID(Type)
 176 #define DECL(DERIVED, BASE) KIND_TO_KIND_ID(DERIVED##Decl)
 177 #include "clang/AST/DeclNodes.inc"
 178 #define STMT(DERIVED, BASE) KIND_TO_KIND_ID(DERIVED)
 179 #include "clang/AST/StmtNodes.inc"
 180 #define TYPE(DERIVED, BASE) KIND_TO_KIND_ID(DERIVED##Type)
 181 #include "clang/AST/TypeNodes.def"
 182 #undef KIND_TO_KIND_ID
 183
 184 inline raw_ostream &operator<<(raw_ostream &OS, ASTNodeKind K) {
 185   OS << K.asStringRef();
 186   return OS;
 187 }
 188
 189 /// \brief A dynamically typed AST node container.
 190 ///
 191 /// Stores an AST node in a type safe way. This allows writing code that
 192 /// works with different kinds of AST nodes, despite the fact that they don't
 193 /// have a common base class.
 194 ///
 195 /// Use \c create(Node) to create a \c DynTypedNode from an AST node,
 196 /// and \c get<T>() to retrieve the node as type T if the types match.
 197 ///
 198 /// See \c ASTNodeKind for which node base types are currently supported;
 199 /// You can create DynTypedNodes for all nodes in the inheritance hierarchy of
 200 /// the supported base types.
 201 class DynTypedNode {
 202 public:
 203   /// \brief Creates a \c DynTypedNode from \c Node.
 204   template <typename T>
 205   static DynTypedNode create(const T &Node) {
 206     return BaseConverter<T>::create(Node);
 207   }
 208
 209   /// \brief Retrieve the stored node as type \c T.
 210   ///
 211   /// Returns NULL if the stored node does not have a type that is
 212   /// convertible to \c T.
 213   ///
 214   /// For types that have identity via their pointer in the AST
 215   /// (like \c Stmt, \c Decl, \c Type and \c NestedNameSpecifier) the returned
 216   /// pointer points to the referenced AST node.
 217   /// For other types (like \c QualType) the value is stored directly
 218   /// in the \c DynTypedNode, and the returned pointer points at
 219   /// the storage inside DynTypedNode. For those nodes, do not
 220   /// use the pointer outside the scope of the DynTypedNode.
 221   template <typename T>
 222   const T *get() const {
 223     return BaseConverter<T>::get(NodeKind, Storage.buffer);
 224   }
 225
 226   /// \brief Retrieve the stored node as type \c T.
 227   ///
 228   /// Similar to \c get(), but asserts that the type is what we are expecting.
 229   template <typename T>
 230   const T &getUnchecked() const {
 231     return BaseConverter<T>::getUnchecked(NodeKind, Storage.buffer);
 232   }
 233
 234   ASTNodeKind getNodeKind() const { return NodeKind; }
 235
 236   /// \brief Returns a pointer that identifies the stored AST node.
 237   ///
 238   /// Note that this is not supported by all AST nodes. For AST nodes
 239   /// that don't have a pointer-defined identity inside the AST, this
 240   /// method returns NULL.
 241   const void *getMemoizationData() const { return MemoizationData; }
 242
 243   /// \brief Prints the node to the given output stream.
 244   void print(llvm::raw_ostream &OS, const PrintingPolicy &PP) const;
 245
 246   /// \brief Dumps the node to the given output stream.
 247   void dump(llvm::raw_ostream &OS, SourceManager &SM) const;
 248
 249   /// \brief For nodes which represent textual entities in the source code,
 250   /// return their SourceRange.  For all other nodes, return SourceRange().
 251   SourceRange getSourceRange() const;
 252
 253   /// @{
 254   /// \brief Imposes an order on \c DynTypedNode.
 255   ///
 256   /// Supports comparison of nodes that support memoization.
 257   /// FIXME: Implement comparsion for other node types (currently
 258   /// only Stmt, Decl, Type and NestedNameSpecifier return memoization data).
 259   bool operator<(const DynTypedNode &Other) const {
 260     assert(getMemoizationData() && Other.getMemoizationData());
 261     return getMemoizationData() < Other.getMemoizationData();
 262   }
 263   bool operator==(const DynTypedNode &Other) const {
 264     // DynTypedNode::create() stores the exact kind of the node in NodeKind.
 265     // If they contain the same node, their NodeKind must be the same.
 266     if (!NodeKind.isSame(Other.NodeKind))
 267       return false;
 268
 269     // FIXME: Implement for other types.
 270     if (ASTNodeKind::getFromNodeKind<QualType>().isSame(NodeKind))
 271       return getUnchecked<QualType>() == Other.getUnchecked<QualType>();
 272
 273     assert(getMemoizationData() && Other.getMemoizationData());
 274     return getMemoizationData() == Other.getMemoizationData();
 275   }
 276   bool operator!=(const DynTypedNode &Other) const {
 277     return !operator==(Other);
 278   }
 279   /// @}
 280
 281 private:
 282   /// \brief Takes care of converting from and to \c T.
 283   template <typename T, typename EnablerT = void> struct BaseConverter;
 284
 285   /// \brief Converter that uses dyn_cast<T> from a stored BaseT*.
 286   template <typename T, typename BaseT> struct DynCastPtrConverter {
 287     static const T *get(ASTNodeKind NodeKind, const char Storage[]) {
 288       if (ASTNodeKind::getFromNodeKind<T>().isBaseOf(NodeKind))
 289         return cast<T>(*reinterpret_cast<BaseT *const *>(Storage));
 290       return nullptr;
 291     }
 292     static const T &getUnchecked(ASTNodeKind NodeKind, const char Storage[]) {
 293       assert(ASTNodeKind::getFromNodeKind<T>().isBaseOf(NodeKind));
 294       return *cast<T>(*reinterpret_cast<BaseT *const *>(Storage));
 295     }
 296     static DynTypedNode create(const BaseT &Node) {
 297       DynTypedNode Result;
 298       Result.NodeKind = ASTNodeKind::getFromNode(Node);
 299       Result.MemoizationData = &Node;
 300       new (Result.Storage.buffer) const BaseT * (&Node);
 301       return Result;
 302     }
 303   };
 304
 305   /// \brief Converter that stores T* (by pointer).
 306   template <typename T> struct PtrConverter {
 307     static const T *get(ASTNodeKind NodeKind, const char Storage[]) {
 308       if (ASTNodeKind::getFromNodeKind<T>().isSame(NodeKind))
 309         return *reinterpret_cast<T *const *>(Storage);
 310       return nullptr;
 311     }
 312     static const T &getUnchecked(ASTNodeKind NodeKind, const char Storage[]) {
 313       assert(ASTNodeKind::getFromNodeKind<T>().isSame(NodeKind));
 314       return **reinterpret_cast<T *const *>(Storage);
 315     }
 316     static DynTypedNode create(const T &Node) {
 317       DynTypedNode Result;
 318       Result.NodeKind = ASTNodeKind::getFromNodeKind<T>();
 319       Result.MemoizationData = &Node;
 320       new (Result.Storage.buffer) const T * (&Node);
 321       return Result;
 322     }
 323   };
 324
 325   /// \brief Converter that stores T (by value).
 326   template <typename T> struct ValueConverter {
 327     static const T *get(ASTNodeKind NodeKind, const char Storage[]) {
 328       if (ASTNodeKind::getFromNodeKind<T>().isSame(NodeKind))
 329         return reinterpret_cast<const T *>(Storage);
 330       return nullptr;
 331     }
 332     static const T &getUnchecked(ASTNodeKind NodeKind, const char Storage[]) {
 333       assert(ASTNodeKind::getFromNodeKind<T>().isSame(NodeKind));
 334       return *reinterpret_cast<const T *>(Storage);
 335     }
 336     static DynTypedNode create(const T &Node) {
 337       DynTypedNode Result;
 338       Result.NodeKind = ASTNodeKind::getFromNodeKind<T>();
 339       Result.MemoizationData = nullptr;
 340       new (Result.Storage.buffer) T(Node);
 341       return Result;
 342     }
 343   };
 344
 345   ASTNodeKind NodeKind;
 346   const void *MemoizationData;
 347
 348   /// \brief Stores the data of the node.
 349   ///
 350   /// Note that we can store \c Decls, \c Stmts, \c Types,
 351   /// \c NestedNameSpecifiers and \c CXXCtorInitializer by pointer as they are
 352   /// guaranteed to be unique pointers pointing to dedicated storage in the AST.
 353   /// \c QualTypes, \c NestedNameSpecifierLocs, \c TypeLocs and
 354   /// \c TemplateArguments on the other hand do not have storage or unique
 355   /// pointers and thus need to be stored by value.
 356   typedef llvm::AlignedCharArrayUnion<
 357       Decl *, Stmt *, Type *, NestedNameSpecifier *, CXXCtorInitializer *>
 358       KindsByPointer;
 359   llvm::AlignedCharArrayUnion<KindsByPointer, TemplateArgument,
 360                               NestedNameSpecifierLoc, QualType, TypeLoc>
 361       Storage;
 362 };
 363
 364 template <typename T>
 365 struct DynTypedNode::BaseConverter<
 366     T, typename std::enable_if<std::is_base_of<Decl, T>::value>::type>
 367     : public DynCastPtrConverter<T, Decl> {};
 368
 369 template <typename T>
 370 struct DynTypedNode::BaseConverter<
 371     T, typename std::enable_if<std::is_base_of<Stmt, T>::value>::type>
 372     : public DynCastPtrConverter<T, Stmt> {};
 373
 374 template <typename T>
 375 struct DynTypedNode::BaseConverter<
 376     T, typename std::enable_if<std::is_base_of<Type, T>::value>::type>
 377     : public DynCastPtrConverter<T, Type> {};
 378
 379 template <>
 380 struct DynTypedNode::BaseConverter<
 381     NestedNameSpecifier, void> : public PtrConverter<NestedNameSpecifier> {};
 382
 383 template <>
 384 struct DynTypedNode::BaseConverter<
 385     CXXCtorInitializer, void> : public PtrConverter<CXXCtorInitializer> {};
 386
 387 template <>
 388 struct DynTypedNode::BaseConverter<
 389     TemplateArgument, void> : public ValueConverter<TemplateArgument> {};
 390
 391 template <>
 392 struct DynTypedNode::BaseConverter<
 393     NestedNameSpecifierLoc,
 394     void> : public ValueConverter<NestedNameSpecifierLoc> {};
 395
 396 template <>
 397 struct DynTypedNode::BaseConverter<QualType,
 398                                    void> : public ValueConverter<QualType> {};
 399
 400 template <>
 401 struct DynTypedNode::BaseConverter<
 402     TypeLoc, void> : public ValueConverter<TypeLoc> {};
 403
 404 // The only operation we allow on unsupported types is \c get.
 405 // This allows to conveniently use \c DynTypedNode when having an arbitrary
 406 // AST node that is not supported, but prevents misuse - a user cannot create
 407 // a DynTypedNode from arbitrary types.
 408 template <typename T, typename EnablerT> struct DynTypedNode::BaseConverter {
 409   static const T *get(ASTNodeKind NodeKind, const char Storage[]) {
 410     return NULL;
 411   }
 412 };
 413
 414 } // end namespace ast_type_traits
 415 } // end namespace clang
 416
 417 namespace llvm {
 418
 419 template <>
 420 struct DenseMapInfo<clang::ast_type_traits::ASTNodeKind>
 421     : clang::ast_type_traits::ASTNodeKind::DenseMapInfo {};
 422
 423 }  // end namespace llvm
 424
 425 #endif