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 #ifndef incl_HPHP_EITHER_H_
  17 #define incl_HPHP_EITHER_H_
  18
  19 #include <cassert>
  20 #include <cstdint>
  21 #include <cstddef>
  22 #include <type_traits>
  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) : 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     : 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     : 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) {
 127     Either result;
 128     result.bits = raw;
 129     return result;
 130   }
 131   Opaque toOpaque() const { return bits; }
 132
 133   /*
 134    * Equality comparison is shallow.  If the pointers are equal, the
 135    * Eithers are equal.
 136    */
 137   bool operator==(Either<L,R> 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<L,R> 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::result_of<LF(L)>::type,
 164     typename std::result_of<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
 210 #endif