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

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