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