include/llvm/ADT/PointerUnion.h

   1 //===- llvm/ADT/PointerUnion.h - Discriminated Union of 2 Ptrs --*- 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 // This file defines the PointerUnion class, which is a discriminated union of
  10 // pointer types.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_ADT_POINTERUNION_H
  15 #define LLVM_ADT_POINTERUNION_H
  16
  17 #include "llvm/ADT/DenseMapInfo.h"
  18 #include "llvm/ADT/PointerIntPair.h"
  19 #include "llvm/Support/PointerLikeTypeTraits.h"
  20 #include <cassert>
  21 #include <cstddef>
  22 #include <cstdint>
  23
  24 namespace llvm {
  25
  26 template <typename T> struct PointerUnionTypeSelectorReturn {
  27   using Return = T;
  28 };
  29
  30 /// Get a type based on whether two types are the same or not.
  31 ///
  32 /// For:
  33 ///
  34 /// \code
  35 ///   using Ret = typename PointerUnionTypeSelector<T1, T2, EQ, NE>::Return;
  36 /// \endcode
  37 ///
  38 /// Ret will be EQ type if T1 is same as T2 or NE type otherwise.
  39 template <typename T1, typename T2, typename RET_EQ, typename RET_NE>
  40 struct PointerUnionTypeSelector {
  41   using Return = typename PointerUnionTypeSelectorReturn<RET_NE>::Return;
  42 };
  43
  44 template <typename T, typename RET_EQ, typename RET_NE>
  45 struct PointerUnionTypeSelector<T, T, RET_EQ, RET_NE> {
  46   using Return = typename PointerUnionTypeSelectorReturn<RET_EQ>::Return;
  47 };
  48
  49 template <typename T1, typename T2, typename RET_EQ, typename RET_NE>
  50 struct PointerUnionTypeSelectorReturn<
  51     PointerUnionTypeSelector<T1, T2, RET_EQ, RET_NE>> {
  52   using Return =
  53       typename PointerUnionTypeSelector<T1, T2, RET_EQ, RET_NE>::Return;
  54 };
  55
  56 /// Provide PointerLikeTypeTraits for void* that is used by PointerUnion
  57 /// for the two template arguments.
  58 template <typename PT1, typename PT2> class PointerUnionUIntTraits {
  59 public:
  60   static inline void *getAsVoidPointer(void *P) { return P; }
  61   static inline void *getFromVoidPointer(void *P) { return P; }
  62
  63   enum {
  64     PT1BitsAv = (int)(PointerLikeTypeTraits<PT1>::NumLowBitsAvailable),
  65     PT2BitsAv = (int)(PointerLikeTypeTraits<PT2>::NumLowBitsAvailable),
  66     NumLowBitsAvailable = PT1BitsAv < PT2BitsAv ? PT1BitsAv : PT2BitsAv
  67   };
  68 };
  69
  70 /// A discriminated union of two pointer types, with the discriminator in the
  71 /// low bit of the pointer.
  72 ///
  73 /// This implementation is extremely efficient in space due to leveraging the
  74 /// low bits of the pointer, while exposing a natural and type-safe API.
  75 ///
  76 /// Common use patterns would be something like this:
  77 ///    PointerUnion<int*, float*> P;
  78 ///    P = (int*)0;
  79 ///    printf("%d %d", P.is<int*>(), P.is<float*>());  // prints "1 0"
  80 ///    X = P.get<int*>();     // ok.
  81 ///    Y = P.get<float*>();   // runtime assertion failure.
  82 ///    Z = P.get<double*>();  // compile time failure.
  83 ///    P = (float*)0;
  84 ///    Y = P.get<float*>();   // ok.
  85 ///    X = P.get<int*>();     // runtime assertion failure.
  86 template <typename PT1, typename PT2> class PointerUnion {
  87 public:
  88   using ValTy =
  89       PointerIntPair<void *, 1, bool, PointerUnionUIntTraits<PT1, PT2>>;
  90
  91 private:
  92   ValTy Val;
  93
  94   struct IsPT1 {
  95     static const int Num = 0;
  96   };
  97   struct IsPT2 {
  98     static const int Num = 1;
  99   };
 100   template <typename T> struct UNION_DOESNT_CONTAIN_TYPE {};
 101
 102 public:
 103   PointerUnion() = default;
 104   PointerUnion(PT1 V)
 105       : Val(const_cast<void *>(
 106             PointerLikeTypeTraits<PT1>::getAsVoidPointer(V))) {}
 107   PointerUnion(PT2 V)
 108       : Val(const_cast<void *>(PointerLikeTypeTraits<PT2>::getAsVoidPointer(V)),
 109             1) {}
 110
 111   /// Test if the pointer held in the union is null, regardless of
 112   /// which type it is.
 113   bool isNull() const {
 114     // Convert from the void* to one of the pointer types, to make sure that
 115     // we recursively strip off low bits if we have a nested PointerUnion.
 116     return !PointerLikeTypeTraits<PT1>::getFromVoidPointer(Val.getPointer());
 117   }
 118
 119   explicit operator bool() const { return !isNull(); }
 120
 121   /// Test if the Union currently holds the type matching T.
 122   template <typename T> int is() const {
 123     using Ty = typename ::llvm::PointerUnionTypeSelector<
 124         PT1, T, IsPT1,
 125         ::llvm::PointerUnionTypeSelector<PT2, T, IsPT2,
 126                                          UNION_DOESNT_CONTAIN_TYPE<T>>>::Return;
 127     int TyNo = Ty::Num;
 128     return static_cast<int>(Val.getInt()) == TyNo;
 129   }
 130
 131   /// Returns the value of the specified pointer type.
 132   ///
 133   /// If the specified pointer type is incorrect, assert.
 134   template <typename T> T get() const {
 135     assert(is<T>() && "Invalid accessor called");
 136     return PointerLikeTypeTraits<T>::getFromVoidPointer(Val.getPointer());
 137   }
 138
 139   /// Returns the current pointer if it is of the specified pointer type,
 140   /// otherwises returns null.
 141   template <typename T> T dyn_cast() const {
 142     if (is<T>())
 143       return get<T>();
 144     return T();
 145   }
 146
 147   /// If the union is set to the first pointer type get an address pointing to
 148   /// it.
 149   PT1 const *getAddrOfPtr1() const {
 150     return const_cast<PointerUnion *>(this)->getAddrOfPtr1();
 151   }
 152
 153   /// If the union is set to the first pointer type get an address pointing to
 154   /// it.
 155   PT1 *getAddrOfPtr1() {
 156     assert(is<PT1>() && "Val is not the first pointer");
 157     assert(
 158         get<PT1>() == Val.getPointer() &&
 159         "Can't get the address because PointerLikeTypeTraits changes the ptr");
 160     return const_cast<PT1 *>(
 161         reinterpret_cast<const PT1 *>(Val.getAddrOfPointer()));
 162   }
 163
 164   /// Assignment from nullptr which just clears the union.
 165   const PointerUnion &operator=(std::nullptr_t) {
 166     Val.initWithPointer(nullptr);
 167     return *this;
 168   }
 169
 170   /// Assignment operators - Allow assigning into this union from either
 171   /// pointer type, setting the discriminator to remember what it came from.
 172   const PointerUnion &operator=(const PT1 &RHS) {
 173     Val.initWithPointer(
 174         const_cast<void *>(PointerLikeTypeTraits<PT1>::getAsVoidPointer(RHS)));
 175     return *this;
 176   }
 177   const PointerUnion &operator=(const PT2 &RHS) {
 178     Val.setPointerAndInt(
 179         const_cast<void *>(PointerLikeTypeTraits<PT2>::getAsVoidPointer(RHS)),
 180         1);
 181     return *this;
 182   }
 183
 184   void *getOpaqueValue() const { return Val.getOpaqueValue(); }
 185   static inline PointerUnion getFromOpaqueValue(void *VP) {
 186     PointerUnion V;
 187     V.Val = ValTy::getFromOpaqueValue(VP);
 188     return V;
 189   }
 190 };
 191
 192 template <typename PT1, typename PT2>
 193 bool operator==(PointerUnion<PT1, PT2> lhs, PointerUnion<PT1, PT2> rhs) {
 194   return lhs.getOpaqueValue() == rhs.getOpaqueValue();
 195 }
 196
 197 template <typename PT1, typename PT2>
 198 bool operator!=(PointerUnion<PT1, PT2> lhs, PointerUnion<PT1, PT2> rhs) {
 199   return lhs.getOpaqueValue() != rhs.getOpaqueValue();
 200 }
 201
 202 template <typename PT1, typename PT2>
 203 bool operator<(PointerUnion<PT1, PT2> lhs, PointerUnion<PT1, PT2> rhs) {
 204   return lhs.getOpaqueValue() < rhs.getOpaqueValue();
 205 }
 206
 207 // Teach SmallPtrSet that PointerUnion is "basically a pointer", that has
 208 // # low bits available = min(PT1bits,PT2bits)-1.
 209 template <typename PT1, typename PT2>
 210 struct PointerLikeTypeTraits<PointerUnion<PT1, PT2>> {
 211   static inline void *getAsVoidPointer(const PointerUnion<PT1, PT2> &P) {
 212     return P.getOpaqueValue();
 213   }
 214
 215   static inline PointerUnion<PT1, PT2> getFromVoidPointer(void *P) {
 216     return PointerUnion<PT1, PT2>::getFromOpaqueValue(P);
 217   }
 218
 219   // The number of bits available are the min of the two pointer types.
 220   enum {
 221     NumLowBitsAvailable = PointerLikeTypeTraits<
 222         typename PointerUnion<PT1, PT2>::ValTy>::NumLowBitsAvailable
 223   };
 224 };
 225
 226 /// A pointer union of three pointer types. See documentation for PointerUnion
 227 /// for usage.
 228 template <typename PT1, typename PT2, typename PT3> class PointerUnion3 {
 229 public:
 230   using InnerUnion = PointerUnion<PT1, PT2>;
 231   using ValTy = PointerUnion<InnerUnion, PT3>;
 232
 233 private:
 234   ValTy Val;
 235
 236   struct IsInnerUnion {
 237     ValTy Val;
 238
 239     IsInnerUnion(ValTy val) : Val(val) {}
 240
 241     template <typename T> int is() const {
 242       return Val.template is<InnerUnion>() &&
 243              Val.template get<InnerUnion>().template is<T>();
 244     }
 245
 246     template <typename T> T get() const {
 247       return Val.template get<InnerUnion>().template get<T>();
 248     }
 249   };
 250
 251   struct IsPT3 {
 252     ValTy Val;
 253
 254     IsPT3(ValTy val) : Val(val) {}
 255
 256     template <typename T> int is() const { return Val.template is<T>(); }
 257     template <typename T> T get() const { return Val.template get<T>(); }
 258   };
 259
 260 public:
 261   PointerUnion3() = default;
 262   PointerUnion3(PT1 V) { Val = InnerUnion(V); }
 263   PointerUnion3(PT2 V) { Val = InnerUnion(V); }
 264   PointerUnion3(PT3 V) { Val = V; }
 265
 266   /// Test if the pointer held in the union is null, regardless of
 267   /// which type it is.
 268   bool isNull() const { return Val.isNull(); }
 269   explicit operator bool() const { return !isNull(); }
 270
 271   /// Test if the Union currently holds the type matching T.
 272   template <typename T> int is() const {
 273     // If T is PT1/PT2 choose IsInnerUnion otherwise choose IsPT3.
 274     using Ty = typename ::llvm::PointerUnionTypeSelector<
 275         PT1, T, IsInnerUnion,
 276         ::llvm::PointerUnionTypeSelector<PT2, T, IsInnerUnion, IsPT3>>::Return;
 277     return Ty(Val).template is<T>();
 278   }
 279
 280   /// Returns the value of the specified pointer type.
 281   ///
 282   /// If the specified pointer type is incorrect, assert.
 283   template <typename T> T get() const {
 284     assert(is<T>() && "Invalid accessor called");
 285     // If T is PT1/PT2 choose IsInnerUnion otherwise choose IsPT3.
 286     using Ty = typename ::llvm::PointerUnionTypeSelector<
 287         PT1, T, IsInnerUnion,
 288         ::llvm::PointerUnionTypeSelector<PT2, T, IsInnerUnion, IsPT3>>::Return;
 289     return Ty(Val).template get<T>();
 290   }
 291
 292   /// Returns the current pointer if it is of the specified pointer type,
 293   /// otherwises returns null.
 294   template <typename T> T dyn_cast() const {
 295     if (is<T>())
 296       return get<T>();
 297     return T();
 298   }
 299
 300   /// Assignment from nullptr which just clears the union.
 301   const PointerUnion3 &operator=(std::nullptr_t) {
 302     Val = nullptr;
 303     return *this;
 304   }
 305
 306   /// Assignment operators - Allow assigning into this union from either
 307   /// pointer type, setting the discriminator to remember what it came from.
 308   const PointerUnion3 &operator=(const PT1 &RHS) {
 309     Val = InnerUnion(RHS);
 310     return *this;
 311   }
 312   const PointerUnion3 &operator=(const PT2 &RHS) {
 313     Val = InnerUnion(RHS);
 314     return *this;
 315   }
 316   const PointerUnion3 &operator=(const PT3 &RHS) {
 317     Val = RHS;
 318     return *this;
 319   }
 320
 321   void *getOpaqueValue() const { return Val.getOpaqueValue(); }
 322   static inline PointerUnion3 getFromOpaqueValue(void *VP) {
 323     PointerUnion3 V;
 324     V.Val = ValTy::getFromOpaqueValue(VP);
 325     return V;
 326   }
 327 };
 328
 329 // Teach SmallPtrSet that PointerUnion3 is "basically a pointer", that has
 330 // # low bits available = min(PT1bits,PT2bits,PT2bits)-2.
 331 template <typename PT1, typename PT2, typename PT3>
 332 struct PointerLikeTypeTraits<PointerUnion3<PT1, PT2, PT3>> {
 333   static inline void *getAsVoidPointer(const PointerUnion3<PT1, PT2, PT3> &P) {
 334     return P.getOpaqueValue();
 335   }
 336
 337   static inline PointerUnion3<PT1, PT2, PT3> getFromVoidPointer(void *P) {
 338     return PointerUnion3<PT1, PT2, PT3>::getFromOpaqueValue(P);
 339   }
 340
 341   // The number of bits available are the min of the two pointer types.
 342   enum {
 343     NumLowBitsAvailable = PointerLikeTypeTraits<
 344         typename PointerUnion3<PT1, PT2, PT3>::ValTy>::NumLowBitsAvailable
 345   };
 346 };
 347
 348 template <typename PT1, typename PT2, typename PT3>
 349 bool operator<(PointerUnion3<PT1, PT2, PT3> lhs,
 350                PointerUnion3<PT1, PT2, PT3> rhs) {
 351   return lhs.getOpaqueValue() < rhs.getOpaqueValue();
 352 }
 353
 354 /// A pointer union of four pointer types. See documentation for PointerUnion
 355 /// for usage.
 356 template <typename PT1, typename PT2, typename PT3, typename PT4>
 357 class PointerUnion4 {
 358 public:
 359   using InnerUnion1 = PointerUnion<PT1, PT2>;
 360   using InnerUnion2 = PointerUnion<PT3, PT4>;
 361   using ValTy = PointerUnion<InnerUnion1, InnerUnion2>;
 362
 363 private:
 364   ValTy Val;
 365
 366 public:
 367   PointerUnion4() = default;
 368   PointerUnion4(PT1 V) { Val = InnerUnion1(V); }
 369   PointerUnion4(PT2 V) { Val = InnerUnion1(V); }
 370   PointerUnion4(PT3 V) { Val = InnerUnion2(V); }
 371   PointerUnion4(PT4 V) { Val = InnerUnion2(V); }
 372
 373   /// Test if the pointer held in the union is null, regardless of
 374   /// which type it is.
 375   bool isNull() const { return Val.isNull(); }
 376   explicit operator bool() const { return !isNull(); }
 377
 378   /// Test if the Union currently holds the type matching T.
 379   template <typename T> int is() const {
 380     // If T is PT1/PT2 choose InnerUnion1 otherwise choose InnerUnion2.
 381     using Ty = typename ::llvm::PointerUnionTypeSelector<
 382         PT1, T, InnerUnion1,
 383         ::llvm::PointerUnionTypeSelector<PT2, T, InnerUnion1,
 384                                          InnerUnion2>>::Return;
 385     return Val.template is<Ty>() && Val.template get<Ty>().template is<T>();
 386   }
 387
 388   /// Returns the value of the specified pointer type.
 389   ///
 390   /// If the specified pointer type is incorrect, assert.
 391   template <typename T> T get() const {
 392     assert(is<T>() && "Invalid accessor called");
 393     // If T is PT1/PT2 choose InnerUnion1 otherwise choose InnerUnion2.
 394     using Ty = typename ::llvm::PointerUnionTypeSelector<
 395         PT1, T, InnerUnion1,
 396         ::llvm::PointerUnionTypeSelector<PT2, T, InnerUnion1,
 397                                          InnerUnion2>>::Return;
 398     return Val.template get<Ty>().template get<T>();
 399   }
 400
 401   /// Returns the current pointer if it is of the specified pointer type,
 402   /// otherwises returns null.
 403   template <typename T> T dyn_cast() const {
 404     if (is<T>())
 405       return get<T>();
 406     return T();
 407   }
 408
 409   /// Assignment from nullptr which just clears the union.
 410   const PointerUnion4 &operator=(std::nullptr_t) {
 411     Val = nullptr;
 412     return *this;
 413   }
 414
 415   /// Assignment operators - Allow assigning into this union from either
 416   /// pointer type, setting the discriminator to remember what it came from.
 417   const PointerUnion4 &operator=(const PT1 &RHS) {
 418     Val = InnerUnion1(RHS);
 419     return *this;
 420   }
 421   const PointerUnion4 &operator=(const PT2 &RHS) {
 422     Val = InnerUnion1(RHS);
 423     return *this;
 424   }
 425   const PointerUnion4 &operator=(const PT3 &RHS) {
 426     Val = InnerUnion2(RHS);
 427     return *this;
 428   }
 429   const PointerUnion4 &operator=(const PT4 &RHS) {
 430     Val = InnerUnion2(RHS);
 431     return *this;
 432   }
 433
 434   void *getOpaqueValue() const { return Val.getOpaqueValue(); }
 435   static inline PointerUnion4 getFromOpaqueValue(void *VP) {
 436     PointerUnion4 V;
 437     V.Val = ValTy::getFromOpaqueValue(VP);
 438     return V;
 439   }
 440 };
 441
 442 // Teach SmallPtrSet that PointerUnion4 is "basically a pointer", that has
 443 // # low bits available = min(PT1bits,PT2bits,PT2bits)-2.
 444 template <typename PT1, typename PT2, typename PT3, typename PT4>
 445 struct PointerLikeTypeTraits<PointerUnion4<PT1, PT2, PT3, PT4>> {
 446   static inline void *
 447   getAsVoidPointer(const PointerUnion4<PT1, PT2, PT3, PT4> &P) {
 448     return P.getOpaqueValue();
 449   }
 450
 451   static inline PointerUnion4<PT1, PT2, PT3, PT4> getFromVoidPointer(void *P) {
 452     return PointerUnion4<PT1, PT2, PT3, PT4>::getFromOpaqueValue(P);
 453   }
 454
 455   // The number of bits available are the min of the two pointer types.
 456   enum {
 457     NumLowBitsAvailable = PointerLikeTypeTraits<
 458         typename PointerUnion4<PT1, PT2, PT3, PT4>::ValTy>::NumLowBitsAvailable
 459   };
 460 };
 461
 462 // Teach DenseMap how to use PointerUnions as keys.
 463 template <typename T, typename U> struct DenseMapInfo<PointerUnion<T, U>> {
 464   using Pair = PointerUnion<T, U>;
 465   using FirstInfo = DenseMapInfo<T>;
 466   using SecondInfo = DenseMapInfo<U>;
 467
 468   static inline Pair getEmptyKey() { return Pair(FirstInfo::getEmptyKey()); }
 469
 470   static inline Pair getTombstoneKey() {
 471     return Pair(FirstInfo::getTombstoneKey());
 472   }
 473
 474   static unsigned getHashValue(const Pair &PairVal) {
 475     intptr_t key = (intptr_t)PairVal.getOpaqueValue();
 476     return DenseMapInfo<intptr_t>::getHashValue(key);
 477   }
 478
 479   static bool isEqual(const Pair &LHS, const Pair &RHS) {
 480     return LHS.template is<T>() == RHS.template is<T>() &&
 481            (LHS.template is<T>() ? FirstInfo::isEqual(LHS.template get<T>(),
 482                                                       RHS.template get<T>())
 483                                  : SecondInfo::isEqual(LHS.template get<U>(),
 484                                                        RHS.template get<U>()));
 485   }
 486 };
 487
 488 } // end namespace llvm
 489
 490 #endif // LLVM_ADT_POINTERUNION_H