llvm/ADT/PointerUnion.h

0001 //===- llvm/ADT/PointerUnion.h - Discriminated Union of 2 Ptrs --*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 ///
0009 /// \file
0010 /// This file defines the PointerUnion class, which is a discriminated union of
0011 /// pointer types.
0012 ///
0013 //===----------------------------------------------------------------------===//
0014
0015 #ifndef LLVM_ADT_POINTERUNION_H
0016 #define LLVM_ADT_POINTERUNION_H
0017
0018 #include "llvm/ADT/DenseMapInfo.h"
0019 #include "llvm/ADT/PointerIntPair.h"
0020 #include "llvm/ADT/STLExtras.h"
0021 #include "llvm/Support/Casting.h"
0022 #include "llvm/Support/PointerLikeTypeTraits.h"
0023 #include <algorithm>
0024 #include <cassert>
0025 #include <cstddef>
0026 #include <cstdint>
0027
0028 namespace llvm {
0029
0030 namespace pointer_union_detail {
0031   /// Determine the number of bits required to store integers with values < n.
0032   /// This is ceil(log2(n)).
0033   constexpr int bitsRequired(unsigned n) {
0034     return n > 1 ? 1 + bitsRequired((n + 1) / 2) : 0;
0035   }
0036
0037   template <typename... Ts> constexpr int lowBitsAvailable() {
0038     return std::min<int>({PointerLikeTypeTraits<Ts>::NumLowBitsAvailable...});
0039   }
0040
0041   /// Find the first type in a list of types.
0042   template <typename T, typename...> struct GetFirstType {
0043     using type = T;
0044   };
0045
0046   /// Provide PointerLikeTypeTraits for void* that is used by PointerUnion
0047   /// for the template arguments.
0048   template <typename ...PTs> class PointerUnionUIntTraits {
0049   public:
0050     static inline void *getAsVoidPointer(void *P) { return P; }
0051     static inline void *getFromVoidPointer(void *P) { return P; }
0052     static constexpr int NumLowBitsAvailable = lowBitsAvailable<PTs...>();
0053   };
0054
0055   template <typename Derived, typename ValTy, int I, typename ...Types>
0056   class PointerUnionMembers;
0057
0058   template <typename Derived, typename ValTy, int I>
0059   class PointerUnionMembers<Derived, ValTy, I> {
0060   protected:
0061     ValTy Val;
0062     PointerUnionMembers() = default;
0063     PointerUnionMembers(ValTy Val) : Val(Val) {}
0064
0065     friend struct PointerLikeTypeTraits<Derived>;
0066   };
0067
0068   template <typename Derived, typename ValTy, int I, typename Type,
0069             typename ...Types>
0070   class PointerUnionMembers<Derived, ValTy, I, Type, Types...>
0071       : public PointerUnionMembers<Derived, ValTy, I + 1, Types...> {
0072     using Base = PointerUnionMembers<Derived, ValTy, I + 1, Types...>;
0073   public:
0074     using Base::Base;
0075     PointerUnionMembers() = default;
0076     PointerUnionMembers(Type V)
0077         : Base(ValTy(const_cast<void *>(
0078                          PointerLikeTypeTraits<Type>::getAsVoidPointer(V)),
0079                      I)) {}
0080
0081     using Base::operator=;
0082     Derived &operator=(Type V) {
0083       this->Val = ValTy(
0084           const_cast<void *>(PointerLikeTypeTraits<Type>::getAsVoidPointer(V)),
0085           I);
0086       return static_cast<Derived &>(*this);
0087     };
0088   };
0089 }
0090
0091 // This is a forward declaration of CastInfoPointerUnionImpl
0092 // Refer to its definition below for further details
0093 template <typename... PTs> struct CastInfoPointerUnionImpl;
0094 /// A discriminated union of two or more pointer types, with the discriminator
0095 /// in the low bit of the pointer.
0096 ///
0097 /// This implementation is extremely efficient in space due to leveraging the
0098 /// low bits of the pointer, while exposing a natural and type-safe API.
0099 ///
0100 /// Common use patterns would be something like this:
0101 ///    PointerUnion<int*, float*> P;
0102 ///    P = (int*)0;
0103 ///    printf("%d %d", P.is<int*>(), P.is<float*>());  // prints "1 0"
0104 ///    X = P.get<int*>();     // ok.
0105 ///    Y = P.get<float*>();   // runtime assertion failure.
0106 ///    Z = P.get<double*>();  // compile time failure.
0107 ///    P = (float*)0;
0108 ///    Y = P.get<float*>();   // ok.
0109 ///    X = P.get<int*>();     // runtime assertion failure.
0110 ///    PointerUnion<int*, int*> Q; // compile time failure.
0111 template <typename... PTs>
0112 class PointerUnion
0113     : public pointer_union_detail::PointerUnionMembers<
0114           PointerUnion<PTs...>,
0115           PointerIntPair<
0116               void *, pointer_union_detail::bitsRequired(sizeof...(PTs)), int,
0117               pointer_union_detail::PointerUnionUIntTraits<PTs...>>,
0118           0, PTs...> {
0119   static_assert(TypesAreDistinct<PTs...>::value,
0120                 "PointerUnion alternative types cannot be repeated");
0121   // The first type is special because we want to directly cast a pointer to a
0122   // default-initialized union to a pointer to the first type. But we don't
0123   // want PointerUnion to be a 'template <typename First, typename ...Rest>'
0124   // because it's much more convenient to have a name for the whole pack. So
0125   // split off the first type here.
0126   using First = TypeAtIndex<0, PTs...>;
0127   using Base = typename PointerUnion::PointerUnionMembers;
0128
0129   /// This is needed to give the CastInfo implementation below access
0130   /// to protected members.
0131   /// Refer to its definition for further details.
0132   friend struct CastInfoPointerUnionImpl<PTs...>;
0133
0134 public:
0135   PointerUnion() = default;
0136
0137   PointerUnion(std::nullptr_t) : PointerUnion() {}
0138   using Base::Base;
0139
0140   /// Test if the pointer held in the union is null, regardless of
0141   /// which type it is.
0142   bool isNull() const { return !this->Val.getPointer(); }
0143
0144   explicit operator bool() const { return !isNull(); }
0145
0146   // FIXME: Replace the uses of is(), get() and dyn_cast() with
0147   //        isa<T>, cast<T> and the llvm::dyn_cast<T>
0148
0149   /// Test if the Union currently holds the type matching T.
0150   template <typename T>
0151   [[deprecated("Use isa instead")]]
0152   inline bool is() const {
0153     return isa<T>(*this);
0154   }
0155
0156   /// Returns the value of the specified pointer type.
0157   ///
0158   /// If the specified pointer type is incorrect, assert.
0159   template <typename T>
0160   [[deprecated("Use cast instead")]]
0161   inline T get() const {
0162     assert(isa<T>(*this) && "Invalid accessor called");
0163     return cast<T>(*this);
0164   }
0165
0166   /// Returns the current pointer if it is of the specified pointer type,
0167   /// otherwise returns null.
0168   template <typename T> inline T dyn_cast() const {
0169     return llvm::dyn_cast_if_present<T>(*this);
0170   }
0171
0172   /// If the union is set to the first pointer type get an address pointing to
0173   /// it.
0174   First const *getAddrOfPtr1() const {
0175     return const_cast<PointerUnion *>(this)->getAddrOfPtr1();
0176   }
0177
0178   /// If the union is set to the first pointer type get an address pointing to
0179   /// it.
0180   First *getAddrOfPtr1() {
0181     assert(isa<First>(*this) && "Val is not the first pointer");
0182     assert(
0183         PointerLikeTypeTraits<First>::getAsVoidPointer(cast<First>(*this)) ==
0184             this->Val.getPointer() &&
0185         "Can't get the address because PointerLikeTypeTraits changes the ptr");
0186     return const_cast<First *>(
0187         reinterpret_cast<const First *>(this->Val.getAddrOfPointer()));
0188   }
0189
0190   /// Assignment from nullptr which just clears the union.
0191   const PointerUnion &operator=(std::nullptr_t) {
0192     this->Val.initWithPointer(nullptr);
0193     return *this;
0194   }
0195
0196   /// Assignment from elements of the union.
0197   using Base::operator=;
0198
0199   void *getOpaqueValue() const { return this->Val.getOpaqueValue(); }
0200   static inline PointerUnion getFromOpaqueValue(void *VP) {
0201     PointerUnion V;
0202     V.Val = decltype(V.Val)::getFromOpaqueValue(VP);
0203     return V;
0204   }
0205 };
0206
0207 template <typename ...PTs>
0208 bool operator==(PointerUnion<PTs...> lhs, PointerUnion<PTs...> rhs) {
0209   return lhs.getOpaqueValue() == rhs.getOpaqueValue();
0210 }
0211
0212 template <typename ...PTs>
0213 bool operator!=(PointerUnion<PTs...> lhs, PointerUnion<PTs...> rhs) {
0214   return lhs.getOpaqueValue() != rhs.getOpaqueValue();
0215 }
0216
0217 template <typename ...PTs>
0218 bool operator<(PointerUnion<PTs...> lhs, PointerUnion<PTs...> rhs) {
0219   return lhs.getOpaqueValue() < rhs.getOpaqueValue();
0220 }
0221
0222 /// We can't (at least, at this moment with C++14) declare CastInfo
0223 /// as a friend of PointerUnion like this:
0224 /// ```
0225 ///   template<typename To>
0226 ///   friend struct CastInfo<To, PointerUnion<PTs...>>;
0227 /// ```
0228 /// The compiler complains 'Partial specialization cannot be declared as a
0229 /// friend'.
0230 /// So we define this struct to be a bridge between CastInfo and
0231 /// PointerUnion.
0232 template <typename... PTs> struct CastInfoPointerUnionImpl {
0233   using From = PointerUnion<PTs...>;
0234
0235   template <typename To> static inline bool isPossible(From &F) {
0236     return F.Val.getInt() == FirstIndexOfType<To, PTs...>::value;
0237   }
0238
0239   template <typename To> static To doCast(From &F) {
0240     assert(isPossible<To>(F) && "cast to an incompatible type!");
0241     return PointerLikeTypeTraits<To>::getFromVoidPointer(F.Val.getPointer());
0242   }
0243 };
0244
0245 // Specialization of CastInfo for PointerUnion
0246 template <typename To, typename... PTs>
0247 struct CastInfo<To, PointerUnion<PTs...>>
0248     : public DefaultDoCastIfPossible<To, PointerUnion<PTs...>,
0249                                      CastInfo<To, PointerUnion<PTs...>>> {
0250   using From = PointerUnion<PTs...>;
0251   using Impl = CastInfoPointerUnionImpl<PTs...>;
0252
0253   static inline bool isPossible(From &f) {
0254     return Impl::template isPossible<To>(f);
0255   }
0256
0257   static To doCast(From &f) { return Impl::template doCast<To>(f); }
0258
0259   static inline To castFailed() { return To(); }
0260 };
0261
0262 template <typename To, typename... PTs>
0263 struct CastInfo<To, const PointerUnion<PTs...>>
0264     : public ConstStrippingForwardingCast<To, const PointerUnion<PTs...>,
0265                                           CastInfo<To, PointerUnion<PTs...>>> {
0266 };
0267
0268 // Teach SmallPtrSet that PointerUnion is "basically a pointer", that has
0269 // # low bits available = min(PT1bits,PT2bits)-1.
0270 template <typename ...PTs>
0271 struct PointerLikeTypeTraits<PointerUnion<PTs...>> {
0272   static inline void *getAsVoidPointer(const PointerUnion<PTs...> &P) {
0273     return P.getOpaqueValue();
0274   }
0275
0276   static inline PointerUnion<PTs...> getFromVoidPointer(void *P) {
0277     return PointerUnion<PTs...>::getFromOpaqueValue(P);
0278   }
0279
0280   // The number of bits available are the min of the pointer types minus the
0281   // bits needed for the discriminator.
0282   static constexpr int NumLowBitsAvailable = PointerLikeTypeTraits<decltype(
0283       PointerUnion<PTs...>::Val)>::NumLowBitsAvailable;
0284 };
0285
0286 // Teach DenseMap how to use PointerUnions as keys.
0287 template <typename ...PTs> struct DenseMapInfo<PointerUnion<PTs...>> {
0288   using Union = PointerUnion<PTs...>;
0289   using FirstInfo =
0290       DenseMapInfo<typename pointer_union_detail::GetFirstType<PTs...>::type>;
0291
0292   static inline Union getEmptyKey() { return Union(FirstInfo::getEmptyKey()); }
0293
0294   static inline Union getTombstoneKey() {
0295     return Union(FirstInfo::getTombstoneKey());
0296   }
0297
0298   static unsigned getHashValue(const Union &UnionVal) {
0299     intptr_t key = (intptr_t)UnionVal.getOpaqueValue();
0300     return DenseMapInfo<intptr_t>::getHashValue(key);
0301   }
0302
0303   static bool isEqual(const Union &LHS, const Union &RHS) {
0304     return LHS == RHS;
0305   }
0306 };
0307
0308 } // end namespace llvm
0309
0310 #endif // LLVM_ADT_POINTERUNION_H