hphp/util/either.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-2015 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   static_assert(
  70     std::is_same<TagBitPolicy,void>::value ||
  71       std::is_same<TagBitPolicy,either_policy::high_bit>::value,
  72     "Unknown policy in Either"
  73   );
  74   static constexpr uintptr_t TagBit =
  75     std::conditional<
  76       std::is_same<TagBitPolicy,void>::value,
  77       std::integral_constant<uintptr_t,0x1>,
  78       std::integral_constant<uintptr_t,0x8000000000000000>
  79     >::type::value;
  80
  81   /*
  82    * The default constructor creates an Either that isNull.
  83    *
  84    * Post: left() == nullptr && right() == nullptr
  85    *       isNull()
  86    */
  87   Either() : bits{0} {}
  88
  89   /*
  90    * Create an Either that isNull.
  91    *
  92    * Post: left() == nullptr && right() == nullptr
  93    *       isNull()
  94    */
  95   /* implicit */ Either(std::nullptr_t) : bits{0} {}
  96
  97   /*
  98    * Create an Either in the left mode.
  99    *
 100    * Post: left() == l && right() == nullptr
 101    */
 102   /* implicit */ Either(L l)
 103     : bits{reinterpret_cast<uintptr_t>(l)}
 104   {
 105     assert(!(reinterpret_cast<uintptr_t>(l) & TagBit));
 106   }
 107
 108   /*
 109    * Create an Either in the right mode.
 110    *
 111    * Post: left() == nullptr && right() == r
 112    */
 113   /* implicit */ Either(R r)
 114     : bits{reinterpret_cast<uintptr_t>(r) | TagBit}
 115   {
 116     assert(!(reinterpret_cast<uintptr_t>(r) & TagBit));
 117   }
 118
 119   /*
 120    * Equality comparison is shallow.  If the pointers are equal, the
 121    * Eithers are equal.
 122    */
 123   bool operator==(Either<L,R> o) const {
 124     // We assume L* and R* don't alias, so we don't need to check type tags
 125     // when comparing.  But we have to put the TagBit in in case we constructed
 126     // a null from the right (we'll have a tagged null).
 127     return (bits | TagBit) == (o.bits | TagBit);
 128   }
 129   bool operator!=(Either<L,R> o) const {
 130     return !(*this == o);
 131   }
 132
 133   /*
 134    * Matching on Eithers takes two functions, for left and right.  If
 135    * you know that the either is non-null, this is reasonable.  If it's
 136    * potentially null, the null case is passed as a null pointer to the
 137    * right branch.
 138    *
 139    * Example usage:
 140    *
 141    *   Either<A*,B*> foo;
 142    *   auto const count = foo.match(
 143    *     [&] (A* a) { return a->size(); },
 144    *     [&] (B* b) { return b->size(); }
 145    *   );
 146    */
 147   template<class LF, class RF>
 148   typename std::common_type<
 149     typename std::result_of<LF(L)>::type,
 150     typename std::result_of<RF(R)>::type
 151   >::type match(const LF& lf, const RF& rf) const {
 152     if (auto const l = left()) return lf(l);
 153     return rf(reinterpret_cast<R>(bits & ~TagBit));
 154   }
 155
 156   /*
 157    * Functions that simultaneously query the type tag and extract the
 158    * pointer of that type.  Both return nullptr if the Either does not
 159    * hold that type.
 160    */
 161   L left() const {
 162     return bits & TagBit ? nullptr : reinterpret_cast<L>(bits);
 163   }
 164   R right() const {
 165     return bits & TagBit ? reinterpret_cast<R>(bits & ~TagBit) : nullptr;
 166   }
 167
 168   /*
 169    * Returns whether this Either contains neither left nor right.
 170    */
 171   bool isNull() const { return !(bits & ~TagBit); }
 172
 173 private:
 174   static_assert(
 175     !std::is_convertible<L,R>::value && !std::is_convertible<R,L>::value,
 176     "Either<L,R> should not be used with compatible pointer types"
 177   );
 178   // Not implemented in gcc:
 179   // static_assert(
 180   //   std::is_standard_layout<Either>::value,
 181   //   "Either<L,R> should be a standard layout class"
 182   // );
 183   static_assert(
 184     std::is_pointer<L>::value && std::is_pointer<R>::value,
 185     "Either<L,R> should only be used with pointer types"
 186   );
 187
 188 private:
 189   uintptr_t bits;
 190 };
 191
 192 //////////////////////////////////////////////////////////////////////
 193
 194 }
 195
 196 #endif