hphp/util/either.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16 #pragma once
  17
  18 #include <cassert>
  19 #include <cstdint>
  20 #include <cstddef>
  21 #include <type_traits>
  22 #include <utility>
  23
  24 // Workaround a bug that using std::common_type<void, void> causes error with
  25 // libc++. See https://llvm.org/bugs/show_bug.cgi?id=22135
  26 #ifdef _LIBCPP_VERSION
  27 namespace std {
  28
  29 template<>
  30 struct common_type<void, void> {
  31   typedef void type;
  32 };
  33
  34 }
  35 #endif
  36
  37 namespace HPHP {
  38
  39 //////////////////////////////////////////////////////////////////////
  40
  41 /*
  42  * Discriminated pointer to one of two types, or a nullptr.
  43  *
  44  * It does not distinguish between two types of null (for left and
  45  * right)---if the Either is nullptr it is effectively a third state.
  46  *
  47  * This class does not do any intelligent automatic ownership, and is
  48  * guaranteed to be a trivially copyable, standard layout class.
  49  * Zero-initializing it is guaranteed to have a nullptr value
  50  * (assuming null is represented with all bits zero, which of course
  51  * it is on our supported architectures).
  52  *
  53  * Requirements:
  54  *
  55  *   - The two types must be unrelated, and must be pointers.
  56  *
  57  *   - The pointer types used with this class must be known to be at least
  58  *     2-byte aligned with the default arguments, since it discriminates using
  59  *     the low bit (NB: this is not the case for string literals on gcc).  You
  60  *     can pass either_policy::high_bit to use the highest bit as the tag
  61  *     instead in cases where this doesn't apply.
  62  *
  63  *   - This class assumes pointers of L and R types never alias.
  64  *
  65  */
  66 namespace either_policy { struct high_bit {}; }
  67 template<class L, class R, class TagBitPolicy = void>
  68 struct Either {
  69   using Opaque = uintptr_t;
  70
  71   static_assert(
  72     std::is_same<TagBitPolicy,void>::value ||
  73       std::is_same<TagBitPolicy,either_policy::high_bit>::value,
  74     "Unknown policy in Either"
  75   );
  76   static constexpr Opaque TagBit =
  77     std::conditional<
  78       std::is_same<TagBitPolicy,void>::value,
  79       std::integral_constant<Opaque,0x1>,
  80       std::integral_constant<Opaque,0x8000000000000000>
  81     >::type::value;
  82
  83   /*
  84    * The default constructor creates an Either that isNull.
  85    *
  86    * Post: left() == nullptr && right() == nullptr
  87    *       isNull()
  88    */
  89   Either() noexcept : bits{0} {}
  90
  91   /*
  92    * Create an Either that isNull.
  93    *
  94    * Post: left() == nullptr && right() == nullptr
  95    *       isNull()
  96    */
  97   /* implicit */ Either(std::nullptr_t) noexcept : bits{0} {}
  98
  99   /*
 100    * Create an Either in the left mode.
 101    *
 102    * Post: left() == l && right() == nullptr
 103    */
 104   /* implicit */ Either(L l)
 105     noexcept : bits{reinterpret_cast<Opaque>(l)}
 106   {
 107     assert(!(reinterpret_cast<Opaque>(l) & TagBit));
 108   }
 109
 110   /*
 111    * Create an Either in the right mode.
 112    *
 113    * Post: left() == nullptr && right() == r
 114    */
 115   /* implicit */ Either(R r)
 116     noexcept : bits{reinterpret_cast<Opaque>(r) | TagBit}
 117   {
 118     assert(!(reinterpret_cast<Opaque>(r) & TagBit));
 119   }
 120
 121   /*
 122    * Raw access to allow using e.g., std::atomic<Opaque>. Values must come
 123    * from identical instantiations of the Either template, and nothing can
 124    * be assumed about the meaning of the bits.
 125    */
 126   static Either fromOpaque(Opaque raw) noexcept {
 127     Either result;
 128     result.bits = raw;
 129     return result;
 130   }
 131   Opaque toOpaque() const noexcept { return bits; }
 132
 133   /*
 134    * Equality comparison is shallow.  If the pointers are equal, the
 135    * Eithers are equal.
 136    */
 137   bool operator==(Either o) const {
 138     // We assume L* and R* don't alias, so we don't need to check type tags
 139     // when comparing.  But we have to put the TagBit in in case we constructed
 140     // a null from the right (we'll have a tagged null).
 141     return (bits | TagBit) == (o.bits | TagBit);
 142   }
 143   bool operator!=(Either o) const {
 144     return !(*this == o);
 145   }
 146
 147   /*
 148    * Matching on Eithers takes two functions, for left and right.  If
 149    * you know that the either is non-null, this is reasonable.  If it's
 150    * potentially null, the null case is passed as a null pointer to the
 151    * right branch.
 152    *
 153    * Example usage:
 154    *
 155    *   Either<A*,B*> foo;
 156    *   auto const count = foo.match(
 157    *     [&] (A* a) { return a->size(); },
 158    *     [&] (B* b) { return b->size(); }
 159    *   );
 160    */
 161   template<class LF, class RF>
 162   typename std::common_type<
 163     typename std::invoke_result<LF, L>::type,
 164     typename std::invoke_result<RF, R>::type
 165   >::type match(const LF& lf, const RF& rf) const {
 166     if (auto const l = left()) return lf(l);
 167     return rf(reinterpret_cast<R>(bits & ~TagBit));
 168   }
 169
 170   /*
 171    * Functions that simultaneously query the type tag and extract the
 172    * pointer of that type.  Both return nullptr if the Either does not
 173    * hold that type.
 174    */
 175   L left() const {
 176     return bits & TagBit ? nullptr : reinterpret_cast<L>(bits);
 177   }
 178   R right() const {
 179     return bits & TagBit ? reinterpret_cast<R>(bits & ~TagBit) : nullptr;
 180   }
 181
 182   /*
 183    * Returns whether this Either contains neither left nor right.
 184    */
 185   bool isNull() const { return !(bits & ~TagBit); }
 186
 187 private:
 188   static_assert(
 189     !std::is_convertible<L,R>::value && !std::is_convertible<R,L>::value,
 190     "Either<L,R> should not be used with compatible pointer types"
 191   );
 192   // Not implemented in gcc:
 193   // static_assert(
 194   //   std::is_standard_layout<Either>::value,
 195   //   "Either<L,R> should be a standard layout class"
 196   // );
 197   static_assert(
 198     std::is_pointer<L>::value && std::is_pointer<R>::value,
 199     "Either<L,R> should only be used with pointer types"
 200   );
 201
 202 private:
 203   Opaque bits;
 204 };
 205
 206 //////////////////////////////////////////////////////////////////////
 207
 208 /*
 209  * Like Either, but treats any stored pointer as if it was in a
 210  * unique_ptr (doesn't allow copies and automatically frees on
 211  * destruction).
 212  */
 213 template <typename L, typename R, typename TagBitPolicy = void>
 214 struct UniqueEither : private Either<L, R, TagBitPolicy> {
 215   using Parent = Either<L, R, TagBitPolicy>;
 216
 217   UniqueEither() noexcept : Parent{} {}
 218   /* implicit */ UniqueEither(std::nullptr_t) noexcept : Parent{nullptr} {}
 219   // Conversions here are explicit unlike in Either, because it takes
 220   // ownership of the pointer.
 221   explicit UniqueEither(L l) noexcept : Parent{l} {}
 222   explicit UniqueEither(R r) noexcept : Parent{r} {}
 223
 224   UniqueEither(const UniqueEither&) = delete;
 225   UniqueEither& operator=(const UniqueEither&) = delete;
 226
 227   UniqueEither(UniqueEither&& o) noexcept : Parent{o} {
 228     static_cast<Parent&&>(o) = nullptr;
 229   }
 230   UniqueEither& operator=(UniqueEither&& o) {
 231     reset();
 232     static_cast<Parent&>(*this) = o;
 233     static_cast<Parent&&>(o) = nullptr;
 234     return *this;
 235   }
 236   UniqueEither& operator=(std::nullptr_t) {
 237     reset();
 238     return *this;
 239   }
 240
 241   ~UniqueEither() { reset(); }
 242
 243   void reset() {
 244     if (auto l = left()) {
 245       delete l;
 246     } else if (auto r = right()) {
 247       delete r;
 248     }
 249     static_cast<Parent&>(*this) = nullptr;
 250   }
 251
 252   bool operator==(const UniqueEither& o) const {
 253     return Parent::operator==(o);
 254   }
 255   bool operator!=(const UniqueEither& o) const {
 256     return Parent::operator!=(o);
 257   }
 258
 259   using Parent::left;
 260   using Parent::right;
 261   using Parent::isNull;
 262   using Parent::match;
 263
 264   // We don't allow getOpaque because it's too easy to break the
 265   // ownership model.
 266   template <typename... Args>
 267   static UniqueEither makeL(Args&&... args) {
 268     auto const p = new std::remove_pointer_t<L>{std::forward<Args>(args)...};
 269     return UniqueEither{p};
 270   }
 271   template <typename... Args>
 272   static UniqueEither makeR(Args&&... args) {
 273     auto const p = new std::remove_pointer_t<R>{std::forward<Args>(args)...};
 274     return UniqueEither{p};
 275   }
 276 };
 277
 278 //////////////////////////////////////////////////////////////////////
 279
 280 }