contrib/llvm/include/llvm/ADT/PointerSumType.h

   1 //===- llvm/ADT/PointerSumType.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 #ifndef LLVM_ADT_POINTERSUMTYPE_H
  11 #define LLVM_ADT_POINTERSUMTYPE_H
  12
  13 #include "llvm/ADT/DenseMapInfo.h"
  14 #include "llvm/Support/PointerLikeTypeTraits.h"
  15 #include <cassert>
  16 #include <cstdint>
  17 #include <type_traits>
  18
  19 namespace llvm {
  20
  21 /// A compile time pair of an integer tag and the pointer-like type which it
  22 /// indexes within a sum type. Also allows the user to specify a particular
  23 /// traits class for pointer types with custom behavior such as over-aligned
  24 /// allocation.
  25 template <uintptr_t N, typename PointerArgT,
  26           typename TraitsArgT = PointerLikeTypeTraits<PointerArgT>>
  27 struct PointerSumTypeMember {
  28   enum { Tag = N };
  29   using PointerT = PointerArgT;
  30   using TraitsT = TraitsArgT;
  31 };
  32
  33 namespace detail {
  34
  35 template <typename TagT, typename... MemberTs> struct PointerSumTypeHelper;
  36
  37 } // end namespace detail
  38
  39 /// A sum type over pointer-like types.
  40 ///
  41 /// This is a normal tagged union across pointer-like types that uses the low
  42 /// bits of the pointers to store the tag.
  43 ///
  44 /// Each member of the sum type is specified by passing a \c
  45 /// PointerSumTypeMember specialization in the variadic member argument list.
  46 /// This allows the user to control the particular tag value associated with
  47 /// a particular type, use the same type for multiple different tags, and
  48 /// customize the pointer-like traits used for a particular member. Note that
  49 /// these *must* be specializations of \c PointerSumTypeMember, no other type
  50 /// will suffice, even if it provides a compatible interface.
  51 ///
  52 /// This type implements all of the comparison operators and even hash table
  53 /// support by comparing the underlying storage of the pointer values. It
  54 /// doesn't support delegating to particular members for comparisons.
  55 ///
  56 /// It also default constructs to a zero tag with a null pointer, whatever that
  57 /// would be. This means that the zero value for the tag type is significant
  58 /// and may be desirable to set to a state that is particularly desirable to
  59 /// default construct.
  60 ///
  61 /// There is no support for constructing or accessing with a dynamic tag as
  62 /// that would fundamentally violate the type safety provided by the sum type.
  63 template <typename TagT, typename... MemberTs> class PointerSumType {
  64   uintptr_t Value = 0;
  65
  66   using HelperT = detail::PointerSumTypeHelper<TagT, MemberTs...>;
  67
  68 public:
  69   constexpr PointerSumType() = default;
  70
  71   /// A typed constructor for a specific tagged member of the sum type.
  72   template <TagT N>
  73   static PointerSumType
  74   create(typename HelperT::template Lookup<N>::PointerT Pointer) {
  75     PointerSumType Result;
  76     void *V = HelperT::template Lookup<N>::TraitsT::getAsVoidPointer(Pointer);
  77     assert((reinterpret_cast<uintptr_t>(V) & HelperT::TagMask) == 0 &&
  78            "Pointer is insufficiently aligned to store the discriminant!");
  79     Result.Value = reinterpret_cast<uintptr_t>(V) | N;
  80     return Result;
  81   }
  82
  83   TagT getTag() const { return static_cast<TagT>(Value & HelperT::TagMask); }
  84
  85   template <TagT N> bool is() const { return N == getTag(); }
  86
  87   template <TagT N> typename HelperT::template Lookup<N>::PointerT get() const {
  88     void *P = is<N>() ? getImpl() : nullptr;
  89     return HelperT::template Lookup<N>::TraitsT::getFromVoidPointer(P);
  90   }
  91
  92   template <TagT N>
  93   typename HelperT::template Lookup<N>::PointerT cast() const {
  94     assert(is<N>() && "This instance has a different active member.");
  95     return HelperT::template Lookup<N>::TraitsT::getFromVoidPointer(getImpl());
  96   }
  97
  98   explicit operator bool() const { return Value & HelperT::PointerMask; }
  99   bool operator==(const PointerSumType &R) const { return Value == R.Value; }
 100   bool operator!=(const PointerSumType &R) const { return Value != R.Value; }
 101   bool operator<(const PointerSumType &R) const { return Value < R.Value; }
 102   bool operator>(const PointerSumType &R) const { return Value > R.Value; }
 103   bool operator<=(const PointerSumType &R) const { return Value <= R.Value; }
 104   bool operator>=(const PointerSumType &R) const { return Value >= R.Value; }
 105
 106   uintptr_t getOpaqueValue() const { return Value; }
 107
 108 protected:
 109   void *getImpl() const {
 110     return reinterpret_cast<void *>(Value & HelperT::PointerMask);
 111   }
 112 };
 113
 114 namespace detail {
 115
 116 /// A helper template for implementing \c PointerSumType. It provides fast
 117 /// compile-time lookup of the member from a particular tag value, along with
 118 /// useful constants and compile time checking infrastructure..
 119 template <typename TagT, typename... MemberTs>
 120 struct PointerSumTypeHelper : MemberTs... {
 121   // First we use a trick to allow quickly looking up information about
 122   // a particular member of the sum type. This works because we arranged to
 123   // have this type derive from all of the member type templates. We can select
 124   // the matching member for a tag using type deduction during overload
 125   // resolution.
 126   template <TagT N, typename PointerT, typename TraitsT>
 127   static PointerSumTypeMember<N, PointerT, TraitsT>
 128   LookupOverload(PointerSumTypeMember<N, PointerT, TraitsT> *);
 129   template <TagT N> static void LookupOverload(...);
 130   template <TagT N> struct Lookup {
 131     // Compute a particular member type by resolving the lookup helper ovorload.
 132     using MemberT = decltype(
 133         LookupOverload<N>(static_cast<PointerSumTypeHelper *>(nullptr)));
 134
 135     /// The Nth member's pointer type.
 136     using PointerT = typename MemberT::PointerT;
 137
 138     /// The Nth member's traits type.
 139     using TraitsT = typename MemberT::TraitsT;
 140   };
 141
 142   // Next we need to compute the number of bits available for the discriminant
 143   // by taking the min of the bits available for each member. Much of this
 144   // would be amazingly easier with good constexpr support.
 145   template <uintptr_t V, uintptr_t... Vs>
 146   struct Min : std::integral_constant<
 147                    uintptr_t, (V < Min<Vs...>::value ? V : Min<Vs...>::value)> {
 148   };
 149   template <uintptr_t V>
 150   struct Min<V> : std::integral_constant<uintptr_t, V> {};
 151   enum { NumTagBits = Min<MemberTs::TraitsT::NumLowBitsAvailable...>::value };
 152
 153   // Also compute the smallest discriminant and various masks for convenience.
 154   enum : uint64_t {
 155     MinTag = Min<MemberTs::Tag...>::value,
 156     PointerMask = static_cast<uint64_t>(-1) << NumTagBits,
 157     TagMask = ~PointerMask
 158   };
 159
 160   // Finally we need a recursive template to do static checks of each
 161   // member.
 162   template <typename MemberT, typename... InnerMemberTs>
 163   struct Checker : Checker<InnerMemberTs...> {
 164     static_assert(MemberT::Tag < (1 << NumTagBits),
 165                   "This discriminant value requires too many bits!");
 166   };
 167   template <typename MemberT> struct Checker<MemberT> : std::true_type {
 168     static_assert(MemberT::Tag < (1 << NumTagBits),
 169                   "This discriminant value requires too many bits!");
 170   };
 171   static_assert(Checker<MemberTs...>::value,
 172                 "Each member must pass the checker.");
 173 };
 174
 175 } // end namespace detail
 176
 177 // Teach DenseMap how to use PointerSumTypes as keys.
 178 template <typename TagT, typename... MemberTs>
 179 struct DenseMapInfo<PointerSumType<TagT, MemberTs...>> {
 180   using SumType = PointerSumType<TagT, MemberTs...>;
 181   using HelperT = detail::PointerSumTypeHelper<TagT, MemberTs...>;
 182   enum { SomeTag = HelperT::MinTag };
 183   using SomePointerT =
 184       typename HelperT::template Lookup<HelperT::MinTag>::PointerT;
 185   using SomePointerInfo = DenseMapInfo<SomePointerT>;
 186
 187   static inline SumType getEmptyKey() {
 188     return SumType::create<SomeTag>(SomePointerInfo::getEmptyKey());
 189   }
 190
 191   static inline SumType getTombstoneKey() {
 192     return SumType::create<SomeTag>(SomePointerInfo::getTombstoneKey());
 193   }
 194
 195   static unsigned getHashValue(const SumType &Arg) {
 196     uintptr_t OpaqueValue = Arg.getOpaqueValue();
 197     return DenseMapInfo<uintptr_t>::getHashValue(OpaqueValue);
 198   }
 199
 200   static bool isEqual(const SumType &LHS, const SumType &RHS) {
 201     return LHS == RHS;
 202   }
 203 };
 204
 205 } // end namespace llvm
 206
 207 #endif // LLVM_ADT_POINTERSUMTYPE_H