1 //===- llvm/ADT/PointerSumType.h --------------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #ifndef LLVM_ADT_POINTERSUMTYPE_H
11 #define LLVM_ADT_POINTERSUMTYPE_H
13 #include "llvm/ADT/bit.h"
14 #include "llvm/ADT/DenseMapInfo.h"
15 #include "llvm/Support/PointerLikeTypeTraits.h"
18 #include <type_traits>
22 /// A compile time pair of an integer tag and the pointer-like type which it
23 /// indexes within a sum type. Also allows the user to specify a particular
24 /// traits class for pointer types with custom behavior such as over-aligned
26 template <uintptr_t N, typename PointerArgT,
27 typename TraitsArgT = PointerLikeTypeTraits<PointerArgT>>
28 struct PointerSumTypeMember {
30 using PointerT = PointerArgT;
31 using TraitsT = TraitsArgT;
36 template <typename TagT, typename... MemberTs> struct PointerSumTypeHelper;
38 } // end namespace detail
40 /// A sum type over pointer-like types.
42 /// This is a normal tagged union across pointer-like types that uses the low
43 /// bits of the pointers to store the tag.
45 /// Each member of the sum type is specified by passing a \c
46 /// PointerSumTypeMember specialization in the variadic member argument list.
47 /// This allows the user to control the particular tag value associated with
48 /// a particular type, use the same type for multiple different tags, and
49 /// customize the pointer-like traits used for a particular member. Note that
50 /// these *must* be specializations of \c PointerSumTypeMember, no other type
51 /// will suffice, even if it provides a compatible interface.
53 /// This type implements all of the comparison operators and even hash table
54 /// support by comparing the underlying storage of the pointer values. It
55 /// doesn't support delegating to particular members for comparisons.
57 /// It also default constructs to a zero tag with a null pointer, whatever that
58 /// would be. This means that the zero value for the tag type is significant
59 /// and may be desirable to set to a state that is particularly desirable to
60 /// default construct.
62 /// Having a supported zero-valued tag also enables getting the address of a
63 /// pointer stored with that tag provided it is stored in its natural bit
64 /// representation. This works because in the case of a zero-valued tag, the
65 /// pointer's value is directly stored into this object and we can expose the
66 /// address of that internal storage. This is especially useful when building an
67 /// `ArrayRef` of a single pointer stored in a sum type.
69 /// There is no support for constructing or accessing with a dynamic tag as
70 /// that would fundamentally violate the type safety provided by the sum type.
71 template <typename TagT, typename... MemberTs> class PointerSumType {
72 using HelperT = detail::PointerSumTypeHelper<TagT, MemberTs...>;
74 // We keep both the raw value and the min tag value's pointer in a union. When
75 // the minimum tag value is zero, this allows code below to cleanly expose the
76 // address of the zero-tag pointer instead of just the zero-tag pointer
77 // itself. This is especially useful when building `ArrayRef`s out of a single
78 // pointer. However, we have to carefully access the union due to the active
79 // member potentially changing. When we *store* a new value, we directly
80 // access the union to allow us to store using the obvious types. However,
81 // when we *read* a value, we copy the underlying storage out to avoid relying
82 // on one member or the other being active.
84 // Ensure we get a null default constructed value. We don't use a member
85 // initializer because some compilers seem to not implement those correctly
87 StorageT() : Value(0) {}
91 typename HelperT::template Lookup<HelperT::MinTag>::PointerT MinTagPointer;
97 constexpr PointerSumType() = default;
99 /// A typed setter to a given tagged member of the sum type.
101 void set(typename HelperT::template Lookup<N>::PointerT Pointer) {
102 void *V = HelperT::template Lookup<N>::TraitsT::getAsVoidPointer(Pointer);
103 assert((reinterpret_cast<uintptr_t>(V) & HelperT::TagMask) == 0 &&
104 "Pointer is insufficiently aligned to store the discriminant!");
105 Storage.Value = reinterpret_cast<uintptr_t>(V) | N;
108 /// A typed constructor for a specific tagged member of the sum type.
110 static PointerSumType
111 create(typename HelperT::template Lookup<N>::PointerT Pointer) {
112 PointerSumType Result;
113 Result.set<N>(Pointer);
117 /// Clear the value to null with the min tag type.
118 void clear() { set<HelperT::MinTag>(nullptr); }
120 TagT getTag() const {
121 return static_cast<TagT>(getOpaqueValue() & HelperT::TagMask);
124 template <TagT N> bool is() const { return N == getTag(); }
126 template <TagT N> typename HelperT::template Lookup<N>::PointerT get() const {
127 void *P = is<N>() ? getVoidPtr() : nullptr;
128 return HelperT::template Lookup<N>::TraitsT::getFromVoidPointer(P);
132 typename HelperT::template Lookup<N>::PointerT cast() const {
133 assert(is<N>() && "This instance has a different active member.");
134 return HelperT::template Lookup<N>::TraitsT::getFromVoidPointer(
138 /// If the tag is zero and the pointer's value isn't changed when being
139 /// stored, get the address of the stored value type-punned to the zero-tag's
141 typename HelperT::template Lookup<HelperT::MinTag>::PointerT const *
142 getAddrOfZeroTagPointer() const {
143 return const_cast<PointerSumType *>(this)->getAddrOfZeroTagPointer();
146 /// If the tag is zero and the pointer's value isn't changed when being
147 /// stored, get the address of the stored value type-punned to the zero-tag's
149 typename HelperT::template Lookup<HelperT::MinTag>::PointerT *
150 getAddrOfZeroTagPointer() {
151 static_assert(HelperT::MinTag == 0, "Non-zero minimum tag value!");
152 assert(is<HelperT::MinTag>() && "The active tag is not zero!");
153 // Store the initial value of the pointer when read out of our storage.
154 auto InitialPtr = get<HelperT::MinTag>();
155 // Now update the active member of the union to be the actual pointer-typed
156 // member so that accessing it indirectly through the returned address is
158 Storage.MinTagPointer = InitialPtr;
159 // Finally, validate that this was a no-op as expected by reading it back
160 // out using the same underlying-storage read as above.
161 assert(InitialPtr == get<HelperT::MinTag>() &&
162 "Switching to typed storage changed the pointer returned!");
163 // Now we can correctly return an address to typed storage.
164 return &Storage.MinTagPointer;
167 explicit operator bool() const {
168 return getOpaqueValue() & HelperT::PointerMask;
170 bool operator==(const PointerSumType &R) const {
171 return getOpaqueValue() == R.getOpaqueValue();
173 bool operator!=(const PointerSumType &R) const {
174 return getOpaqueValue() != R.getOpaqueValue();
176 bool operator<(const PointerSumType &R) const {
177 return getOpaqueValue() < R.getOpaqueValue();
179 bool operator>(const PointerSumType &R) const {
180 return getOpaqueValue() > R.getOpaqueValue();
182 bool operator<=(const PointerSumType &R) const {
183 return getOpaqueValue() <= R.getOpaqueValue();
185 bool operator>=(const PointerSumType &R) const {
186 return getOpaqueValue() >= R.getOpaqueValue();
189 uintptr_t getOpaqueValue() const {
190 // Read the underlying storage of the union, regardless of the active
192 return bit_cast<uintptr_t>(Storage);
196 void *getVoidPtr() const {
197 return reinterpret_cast<void *>(getOpaqueValue() & HelperT::PointerMask);
203 /// A helper template for implementing \c PointerSumType. It provides fast
204 /// compile-time lookup of the member from a particular tag value, along with
205 /// useful constants and compile time checking infrastructure..
206 template <typename TagT, typename... MemberTs>
207 struct PointerSumTypeHelper : MemberTs... {
208 // First we use a trick to allow quickly looking up information about
209 // a particular member of the sum type. This works because we arranged to
210 // have this type derive from all of the member type templates. We can select
211 // the matching member for a tag using type deduction during overload
213 template <TagT N, typename PointerT, typename TraitsT>
214 static PointerSumTypeMember<N, PointerT, TraitsT>
215 LookupOverload(PointerSumTypeMember<N, PointerT, TraitsT> *);
216 template <TagT N> static void LookupOverload(...);
217 template <TagT N> struct Lookup {
218 // Compute a particular member type by resolving the lookup helper ovorload.
219 using MemberT = decltype(
220 LookupOverload<N>(static_cast<PointerSumTypeHelper *>(nullptr)));
222 /// The Nth member's pointer type.
223 using PointerT = typename MemberT::PointerT;
225 /// The Nth member's traits type.
226 using TraitsT = typename MemberT::TraitsT;
229 // Next we need to compute the number of bits available for the discriminant
230 // by taking the min of the bits available for each member. Much of this
231 // would be amazingly easier with good constexpr support.
232 template <uintptr_t V, uintptr_t... Vs>
233 struct Min : std::integral_constant<
234 uintptr_t, (V < Min<Vs...>::value ? V : Min<Vs...>::value)> {
236 template <uintptr_t V>
237 struct Min<V> : std::integral_constant<uintptr_t, V> {};
238 enum { NumTagBits = Min<MemberTs::TraitsT::NumLowBitsAvailable...>::value };
240 // Also compute the smallest discriminant and various masks for convenience.
241 constexpr static TagT MinTag =
242 static_cast<TagT>(Min<MemberTs::Tag...>::value);
244 PointerMask = static_cast<uint64_t>(-1) << NumTagBits,
245 TagMask = ~PointerMask
248 // Finally we need a recursive template to do static checks of each
250 template <typename MemberT, typename... InnerMemberTs>
251 struct Checker : Checker<InnerMemberTs...> {
252 static_assert(MemberT::Tag < (1 << NumTagBits),
253 "This discriminant value requires too many bits!");
255 template <typename MemberT> struct Checker<MemberT> : std::true_type {
256 static_assert(MemberT::Tag < (1 << NumTagBits),
257 "This discriminant value requires too many bits!");
259 static_assert(Checker<MemberTs...>::value,
260 "Each member must pass the checker.");
263 } // end namespace detail
265 // Teach DenseMap how to use PointerSumTypes as keys.
266 template <typename TagT, typename... MemberTs>
267 struct DenseMapInfo<PointerSumType<TagT, MemberTs...>> {
268 using SumType = PointerSumType<TagT, MemberTs...>;
269 using HelperT = detail::PointerSumTypeHelper<TagT, MemberTs...>;
270 enum { SomeTag = HelperT::MinTag };
272 typename HelperT::template Lookup<HelperT::MinTag>::PointerT;
273 using SomePointerInfo = DenseMapInfo<SomePointerT>;
275 static inline SumType getEmptyKey() {
276 return SumType::create<SomeTag>(SomePointerInfo::getEmptyKey());
279 static inline SumType getTombstoneKey() {
280 return SumType::create<SomeTag>(SomePointerInfo::getTombstoneKey());
283 static unsigned getHashValue(const SumType &Arg) {
284 uintptr_t OpaqueValue = Arg.getOpaqueValue();
285 return DenseMapInfo<uintptr_t>::getHashValue(OpaqueValue);
288 static bool isEqual(const SumType &LHS, const SumType &RHS) {
293 } // end namespace llvm
295 #endif // LLVM_ADT_POINTERSUMTYPE_H