Folly.Poly: a library for creating type-erasing polymorphic wrappers

Summary:
`Poly` is a class template that makes it relatively easy to define a type-erasing polymorphic object wrapper.

== Type-erasure

`std::function` is one example of a type-erasing polymorphic object wrapper;
`folly::exception_wrapper` is another. Type-erasure is often used as an
alternative to dynamic polymorphism via inheritance-based virtual dispatch.
The distinguishing characteristic of type-erasing wrappers are:

* **Duck typing:** Types do not need to inherit from an abstract base
    class in order to be assignable to a type-erasing wrapper; they merely
    need to satisfy a particular interface.
* **Value semantics:** Type-erasing wrappers are objects that can be
    passed around _by value_. This is in contrast to abstract base classes
    which must be passed by reference or by pointer or else suffer from
    _slicing_, which causes them to lose their polymorphic behaviors.
    Reference semantics make it difficult to reason locally about code.
* **Automatic memory management:** When dealing with inheritance-based
    dynamic polymorphism, it is often necessary to allocate and manage
    objects on the heap. This leads to a proliferation of `shared_ptr`s and
    `unique_ptr`s in APIs, complicating their point-of-use. APIs that take
    type-erasing wrappers, on the other hand, can often store small objects
    in-situ, with no dynamic allocation. The memory management, if any, is
    handled for you, and leads to cleaner APIs: consumers of your API don't
    need to pass `shared_ptr<AbstractBase>`; they can simply pass any object
    that satisfies the interface you require. (`std::function` is a
    particularly compelling example of this benefit. Far worse would be an
    inheritance-based callable solution like
    `shared_ptr<ICallable<void(int)>>`. )

== Example: Defining a type-erasing function wrapper with `folly::Poly`

Defining a polymorphic wrapper with `Poly` is a matter of defining two
things:

* An *interface*, consisting of public member functions, and
* A *mapping* from a concrete type to a set of member function bindings.

Below is a (heavily commented) example of a simple implementation of a
`std::function`-like polymorphic wrapper. Its interface has only a single
member function: `operator()`

  lang=c++
  // An interface for a callable object of a particular signature, Fun
  // (most interfaces don't need to be templates, FWIW).
  template <class Fun>
  struct IFunction;

  template <class R, class... As>
  struct IFunction<R(As...)> {
    // An interface is defined as a nested class template called
    // Interface that takes a single template parameter, Base, from
    // which it inherits.
    template <class Base>
    struct Interface : Base {
      // The Interface has public member functions. These become the
      // public interface of the resulting Poly instantiation.
      // (Implementation note: Poly<IFunction<Sig>> will publicly
      // inherit from this struct, which is what gives it the right
      // member functions.)
      R operator()(As... as) const {
        // The definition of each member function in your interface will
        // always consist of a single line dispatching to folly::call<N>.
        // The "N" corresponds to the N-th member function in the
        // list of member function bindings, Members, defined below.
        // The first argument will always be *this, and the rest of the
        // arguments should simply forward (if necessary) the member
        // function's arguments.
        return static_cast<R>(
            folly::poly_call<0>(*this, std::forward<As>(as)...));
      }
    };
    // The "Members" alias template is a comma-separated list of bound
    // member functions for a given concrete type "T". The
    // "FOLLY_POLY_MEMBERS" macro accepts a comma-separated list, and the
    // (optional) "FOLLY_POLY_MEMBER" macro lets you disambiguate overloads
    // by explicitly specifying the function signature the target member
    // function should have. In this case, we require "T" to have a
    // function call operator with the signature `R(As...) const`.
    //
    // If you are using a C++17-compatible compiler, you can do away with
    // the macros and write this as:
    //
    //   template <class T>
    //   using Members =
    //       folly::PolyMembers<folly::sig<R(As...) const>(&T::operator())>;
    //
    // And since `folly::sig` is only needed for disambiguation in case of
    // overloads, if you are not concerned about objects with overloaded
    // function call operators, it could be further simplified to:
    //
    //   template <class T> using Members = folly::PolyMembers<&T::operator()>;
    //
    template <class T>
    using Members = FOLLY_POLY_MEMBERS(
        FOLLY_POLY_MEMBER(R(As...) const, &T::operator()));
  };

  // Now that we have defined the interface, we can pass it to Poly to
  // create our type-erasing wrapper:
  template <class Fun>
  using Function = Poly<IFunction<Fun>>;

Given the above definition of `Function`, users can now initialize instances
of (say) `Function<int(int, int)>` with function objects like
`std::plus<int>` and `std::multiplies<int>`, as below:

  lang=c++
  Function<int(int, int)> fun = std::plus<int>{};
  assert(5 == fun(2, 3));
  fun = std::multiplies<int>{};
  assert(6 = fun(2, 3));

== Defining an interface with C++17

With C++17, defining an interface to be used with `Poly` is fairly
straightforward. As in the `Function` example above, there is a struct with
a nested `Interface` class template and a nested `Members` alias template.
No macros are needed with C++17.

Imagine we were defining something like a Java-style iterator. If we are
using a C++17 compiler, our interface would look something like this:

  lang=c++
  template <class Value>
  struct IJavaIterator {
    template <class Base>
    struct Interface : Base {
      bool Done() const { return folly::poly_call<0>(*this); }
      Value Current() const { return folly::poly_call<1>(*this); }
      void Next() { folly::poly_call<2>(*this); }
    };
    // NOTE: This works in C++17 only:
    template <class T>
    using Members = folly::PolyMembers<&T::Done, &T::Current, &T::Next>;
  };

  template <class Value>
  using JavaIterator = Poly<IJavaIterator>;

Given the above definition, `JavaIterator<int>` can be used to hold instances
of any type that has `Done`, `Current`, and `Next` member functions with the
correct (or compatible) signatures.

The presence of overloaded member functions complicates this picture. Often,
property members are faked in C++ with `const` and non-`const` member
function overloads, like in the interface specified below:

  lang=c++
  struct IIntProperty {
    template <class Base>
    struct Interface : Base {
      int Value() const { return folly::poly_call<0>(*this); }
      void Value(int i) { folly::poly_call<1>(*this, i); }
    };
    // NOTE: This works in C++17 only:
    template <class T>
    using Members = folly::PolyMembers<
      folly::sig<int() const>(&T::Value),
      folly::sig<void(int)>(&T::Value)>;
  };

  using IntProperty = Poly<IIntProperty>;

Now, any object that has `Value` members of compatible signatures can be
assigned to instances of `IntProperty` object. Note how `folly::sig` is used
to disambiguate the overloads of `&T::Value`.

== Defining an interface with C++14

In C++14, the nice syntax above doesn't work, so we have to resort to macros.
The two examples above would look like this:

  lang=c++
  template <class Value>
  struct IJavaIterator {
    template <class Base>
    struct Interface : Base {
      bool Done() const { return folly::poly_call<0>(*this); }
      Value Current() const { return folly::poly_call<1>(*this); }
      void Next() { folly::poly_call<2>(*this); }
    };
    // NOTE: This works in C++14 and C++17:
    template <class T>
    using Members = FOLLY_POLY_MEMBERS(&T::Done, &T::Current, &T::Next);
  };

  template <class Value>
  using JavaIterator = Poly<IJavaIterator>;

and

  lang=c++
  struct IIntProperty {
    template <class Base>
    struct Interface : Base {
      int Value() const { return folly::poly_call<0>(*this); }
      void Value(int i) { return folly::poly_call<1>(*this, i); }
    };
    // NOTE: This works in C++14 and C++17:
    template <class T>
    using Members = FOLLY_POLY_MEMBERS(
      FOLLY_POLY_MEMBER(int() const, &T::Value),
      FOLLY_POLY_MEMBER(void(int), &T::Value));
  };

  using IntProperty = Poly<IIntProperty>;

== Extending interfaces

One typical advantage of inheritance-based solutions to runtime polymorphism
is that one polymorphic interface could extend another through inheritance.
The same can be accomplished with type-erasing polymorphic wrappers. In
the `Poly` library, you can use `folly::PolyExtends` to say that one interface
extends another.

  lang=c++
  struct IFoo {
    template <class Base>
    struct Interface : Base {
      void Foo() const { return folly::poly_call<0>(*this); }
    };
    template <class T>
    using Members = FOLLY_POLY_MEMBERS(&T::Foo);
  };

  // The IFooBar interface extends the IFoo interface
  struct IFooBar : PolyExtends<IFoo> {
    template <class Base>
    struct Interface : Base {
      void Bar() const { return folly::poly_call<0>(*this); }
    };
    template <class T>
    using Members = FOLLY_POLY_MEMBERS(&T::Bar);
  };

  using FooBar = Poly<IFooBar>;

Given the above definition, instances of type `FooBar` have both `Foo()` and
`Bar()` member functions.

The sensible conversions exist between a wrapped derived type and a wrapped
base type. For instance, assuming `IDerived` extends `IBase` with `Extends`:

  lang=c++
  Poly<IDerived> derived = ...;
  Poly<IBase> base = derived; // This conversion is OK.

As you would expect, there is no conversion in the other direction, and at
present there is no `Poly` equivalent to `dynamic_cast`.

== Type-erasing polymorphic reference wrappers

Sometimes you don't need to own a copy of an object; a reference will do. For
that you can use `Poly` to capture a //reference// to an object satisfying an
interface rather than the whole object itself. The syntax is intuitive.

  lang=c++
  int i = 42;

  // Capture a mutable reference to an object of any IRegular type:
  Poly<IRegular &> intRef = i;

  assert(42 == folly::poly_cast<int>(intRef));
  // Assert that we captured the address of "i":
  assert(&i == &folly::poly_cast<int>(intRef));

A reference-like `Poly` has a different interface than a value-like `Poly`.
Rather than calling member functions with the `obj.fun()` syntax, you would
use the `obj->fun()` syntax. This is for the sake of `const`-correctness.
For example, consider the code below:

  lang=c++
  struct IFoo {
    template <class Base>
    struct Interface {
      void Foo() { folly::poly_call<0>(*this); }
    };
    template <class T>
    using Members = folly::PolyMembers<&T::Foo>;
  };

  struct SomeFoo {
    void Foo() { std::printf("SomeFoo::Foo\n"); }
  };

  SomeFoo foo;
  Poly<IFoo &> const anyFoo = foo;
  anyFoo->Foo(); // prints "SomeFoo::Foo"

Notice in the above code that the `Foo` member function is non-`const`.
Notice also that the `anyFoo` object is `const`. However, since it has
captured a non-`const` reference to the `foo` object, it should still be
possible to dispatch to the non-`const` `Foo` member function. When
instantiated with a reference type, `Poly` has an overloaded `operator->`
member that returns a pointer to the `IFoo` interface with the correct
`const`-ness, which makes this work.

The same mechanism also prevents users from calling non-`const` member
functions on `Poly` objects that have captured `const` references, which
would violate `const`-correctness.

Sensible conversions exist between non-reference and reference `Poly`s. For
instance:

  lang=c++
  Poly<IRegular> value = 42;
  Poly<IRegular &> mutable_ref = value;
  Poly<IRegular const &> const_ref = mutable_ref;

  assert(&poly_cast<int>(value) == &poly_cast<int>(mutable_ref));
  assert(&poly_cast<int>(value) == &poly_cast<int>(const_ref));

== Non-member functions (C++17)

If you wanted to write the interface `ILogicallyNegatable`, which captures
all types that can be negated with unary `operator!`, you could do it
as we've shown above, by binding `&T::operator!` in the nested `Members`
alias template, but that has the problem that it won't work for types that
have defined unary `operator!` as a free function. To handle this case,
the `Poly` library lets you use a free function instead of a member function
when creating a binding.

With C++17 you may use a lambda to create a binding, as shown in the example
below:

  lang=c++
  struct ILogicallyNegatable {
    template <class Base>
    struct Interface : Base {
      bool operator!() const { return folly::poly_call<0>(*this); }
    };
    template <class T>
    using Members = folly::PolyMembers<
      +[](T const& t) -> decltype(!t) { return !t; }>;
  };

This requires some explanation. The unary `operator+` in front of the lambda
is necessary! It causes the lambda to decay to a C-style function pointer,
which is one of the types that `folly::PolyMembers` accepts. The `decltype` in
the lambda return type is also necessary. Through the magic of SFINAE, it
will cause `Poly<ILogicallyNegatable>` to reject any types that don't support
unary `operator!`.

If you are using a free function to create a binding, the first parameter is
implicitly the `this` parameter. It will receive the type-erased object.

== Non-member functions (C++14)

If you are using a C++14 compiler, the definition of `ILogicallyNegatable`
above will fail because lambdas are not `constexpr`. We can get the same
effect by writing the lambda as a named free function, as show below:

  lang=c++
  struct ILogicallyNegatable {
    template <class Base>
    struct Interface : Base {
      bool operator!() const { return folly::poly_call<0>(*this); }
    };
    template <class T>
    static auto negate(T const& t) -> decltype(!t) { return !t; }
    template <class T>
    using Members = FOLLY_POLY_MEMBERS(&negate<T>);
  };

As with the example that uses the lambda in the preceding section, the first
parameter is implicitly the `this` parameter. It will receive the type-erased
object.

== Multi-dispatch

What if you want to create an `IAddable` interface for things that can be
added? Adding requires //two// objects, both of which are type-erased. This
interface requires dispatching on both objects, doing the addition only
if the types are the same. For this we make use of the `Self` template
alias to define an interface that takes more than one object of the the
erased type.

  lang=c++
  struct IAddable {
    template <class Base>
    struct Interface : Base {
      friend Self<Base>
      operator+(Self<Base> const& a, Self<Base> const& b) const {
        return folly::poly_call<0>(a, b);
      }
    };
    template <class T>
    using Members = folly::PolyMembers<
      +[](T const& a, T const& b) -> decltype(a + b) { return a + b; }>;
  };

Given the above defintion of `IAddable` we would be able to do the following:

  lang=c++
  Poly<IAddable> a = 2, b = 3;
  Poly<IAddable> c = a + b;
  assert(poly_cast<int>(c) == 5);

If `a` and `b` stored objects of different types, a `BadPolyCast` exception
would be thrown.

== Move-only types

If you want to store move-only types, then your interface should extend the
`IMoveOnly` interface.

== Implementation notes

`Poly` will store "small" objects in an internal buffer, avoiding the cost of
of dynamic allocations. At present, this size is not configurable; it is
pegged at the size of two `double`s.

`Poly` objects are always nothrow movable. If you store an object in one that
has a potentially throwing move contructor, the object will be stored on the
heap, even if it could fit in the internal storage of the `Poly` object.
(So be sure to give your objects nothrow move constructors!)

`Poly` implements type-erasure in a manner very similar to how the compiler
accomplishes virtual dispatch. Every `Poly` object contains a pointer to a
table of function pointers. Member function calls involve a double-
indirection: once through the v-pointer, and other indirect function call
through the function pointer.

Reviewed By: yfeldblum

Differential Revision: D4897112

fbshipit-source-id: ff1c1156316bfbdd8f2205c4f57932c0067cacac

diff --git a/folly/Makefile.am b/folly/Makefile.am
index 337b1cd6d351c82155836f25f5a91e9c57f6d0c6..d535a3b6681c0ce3fdf1adf09353c58653bca8b0 100644 (file)
--- a/folly/Makefile.am
+++ b/folly/Makefile.am
@@ -77,6 +77,7 @@ nobase_follyinclude_HEADERS = \
        detail/IPAddressSource.h \
        detail/MemoryIdler.h \
        detail/MPMCPipelineDetail.h \
+       detail/PolyDetail.h \
        detail/RangeCommon.h \
        detail/RangeSse42.h \
        detail/Sleeper.h \
@@ -84,6 +85,7 @@ nobase_follyinclude_HEADERS = \
        detail/SocketFastOpen.h \
        detail/StaticSingletonManager.h \
        detail/ThreadLocalDetail.h \
+       detail/TypeList.h \
        detail/TurnSequencer.h \
        detail/UncaughtExceptionCounter.h \
        executors/Async.h \
@@ -341,6 +343,10 @@ nobase_follyinclude_HEADERS = \
        PackedSyncPtr.h \
        Padded.h \
        PicoSpinLock.h \
+       Poly.h \
+       Poly-inl.h \
+       poly/Nullable.h \
+       poly/Regular.h \
        Portability.h \
        portability/Asm.h \
        portability/Atomic.h \
@@ -565,6 +571,7 @@ libfolly_la_SOURCES = \
        detail/SocketFastOpen.cpp \
        MacAddress.cpp \
        memory/ThreadCachedArena.cpp \
+       Poly.cpp \
        portability/Dirent.cpp \
        portability/Fcntl.cpp \
        portability/Libgen.cpp \

diff --git a/folly/Poly-inl.h b/folly/Poly-inl.h
new file mode 100644 (file)
index 0000000..feb846b
--- /dev/null
+++ b/folly/Poly-inl.h
@@ -0,0 +1,226 @@
+/*
+ * Copyright 2017-present Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+namespace folly {
+namespace detail {
+
+template <class I>
+inline PolyVal<I>::PolyVal(PolyVal&& that) noexcept {
+  that.vptr_->ops_(Op::eMove, &that, static_cast<Data*>(this));
+  vptr_ = std::exchange(that.vptr_, vtable<I>());
+}
+
+template <class I>
+inline PolyVal<I>::PolyVal(PolyOrNonesuch const& that) {
+  that.vptr_->ops_(
+      Op::eCopy, const_cast<Data*>(that._data_()), PolyAccess::data(*this));
+  vptr_ = that.vptr_;
+}
+
+template <class I>
+inline PolyVal<I>::~PolyVal() {
+  vptr_->ops_(Op::eNuke, this, nullptr);
+}
+
+template <class I>
+inline Poly<I>& PolyVal<I>::operator=(PolyVal that) noexcept {
+  vptr_->ops_(Op::eNuke, _data_(), nullptr);
+  that.vptr_->ops_(Op::eMove, that._data_(), _data_());
+  vptr_ = std::exchange(that.vptr_, vtable<I>());
+  return static_cast<Poly<I>&>(*this);
+}
+
+template <class I>
+template <class T, std::enable_if_t<ModelsInterface<T, I>::value, int>>
+inline PolyVal<I>::PolyVal(T&& t) {
+  using U = std::decay_t<T>;
+  static_assert(
+      std::is_copy_constructible<U>::value || !Copyable::value,
+      "This Poly<> requires copyability, and the source object is not "
+      "copyable");
+  // The static and dynamic types should match; otherwise, this will slice.
+  assert(typeid(t) == typeid(_t<std::decay<T>>) ||
+       !"Dynamic and static exception types don't match. Object would "
+        "be sliced when storing in Poly.");
+  if (inSitu<U>()) {
+    ::new (static_cast<void*>(&_data_()->buff_)) U(static_cast<T&&>(t));
+  } else {
+    _data_()->pobj_ = new U(static_cast<T&&>(t));
+  }
+  vptr_ = vtableFor<I, U>();
+}
+
+template <class I>
+template <class I2, std::enable_if_t<ValueCompatible<I, I2>::value, int>>
+inline PolyVal<I>::PolyVal(Poly<I2> that) {
+  static_assert(
+      !Copyable::value || std::is_copy_constructible<Poly<I2>>::value,
+      "This Poly<> requires copyability, and the source object is not "
+      "copyable");
+  auto* that_vptr = PolyAccess::vtable(that);
+  if (that_vptr->state_ != State::eEmpty) {
+    that_vptr->ops_(Op::eMove, PolyAccess::data(that), _data_());
+    vptr_ = &select<I>(*std::exchange(that_vptr, vtable<std::decay_t<I2>>()));
+  }
+}
+
+template <class I>
+template <class T, std::enable_if_t<ModelsInterface<T, I>::value, int>>
+inline Poly<I>& PolyVal<I>::operator=(T&& t) {
+  *this = PolyVal(static_cast<T&&>(t));
+  return static_cast<Poly<I>&>(*this);
+}
+
+template <class I>
+template <class I2, std::enable_if_t<ValueCompatible<I, I2>::value, int>>
+inline Poly<I>& PolyVal<I>::operator=(Poly<I2> that) {
+  *this = PolyVal(std::move(that));
+  return static_cast<Poly<I>&>(*this);
+}
+
+template <class I>
+inline void PolyVal<I>::swap(Poly<I>& that) noexcept {
+  switch (vptr_->state_) {
+    case State::eEmpty:
+      *this = std::move(that);
+      break;
+    case State::eOnHeap:
+      if (State::eOnHeap == that.vptr_->state_) {
+        std::swap(_data_()->pobj_, _data_()->pobj_);
+        std::swap(vptr_, that.vptr_);
+      }
+      FOLLY_FALLTHROUGH;
+    case State::eInSitu:
+      std::swap(*this, that); // NOTE: qualified, not ADL
+  }
+}
+
+template <class I>
+inline AddCvrefOf<PolyRoot<I>, I>& PolyRef<I>::_polyRoot_() const noexcept {
+  return const_cast<AddCvrefOf<PolyRoot<I>, I>&>(
+      static_cast<PolyRoot<I> const&>(*this));
+}
+
+template <class I>
+constexpr RefType PolyRef<I>::refType() noexcept {
+  using J = std::remove_reference_t<I>;
+  return std::is_rvalue_reference<I>::value
+      ? RefType::eRvalue
+      : std::is_const<J>::value ? RefType::eConstLvalue : RefType::eLvalue;
+}
+
+template <class I>
+template <class That, class I2>
+inline PolyRef<I>::PolyRef(That&& that, Type<I2>) {
+  auto* that_vptr = PolyAccess::vtable(PolyAccess::root(that));
+  detail::State const that_state = that_vptr->state_;
+  if (that_state == State::eEmpty) {
+    throw BadPolyAccess();
+  }
+  auto* that_data = PolyAccess::data(PolyAccess::root(that));
+  _data_()->pobj_ = that_state == State::eInSitu
+      ? const_cast<void*>(static_cast<void const*>(&that_data->buff_))
+      : that_data->pobj_;
+  this->vptr_ = &select<std::decay_t<I>>(
+      *static_cast<VTable<std::decay_t<I2>> const*>(that_vptr->ops_(
+          Op::eRefr, nullptr, reinterpret_cast<void*>(refType()))));
+}
+
+template <class I>
+inline PolyRef<I>::PolyRef(PolyRef const& that) noexcept {
+  _data_()->pobj_ = that._data_()->pobj_;
+  this->vptr_ = that.vptr_;
+}
+
+template <class I>
+inline Poly<I>& PolyRef<I>::operator=(PolyRef const& that) noexcept {
+  _data_()->pobj_ = that._data_()->pobj_;
+  this->vptr_ = that.vptr_;
+  return static_cast<Poly<I>&>(*this);
+}
+
+template <class I>
+template <class T, std::enable_if_t<ModelsInterface<T, I>::value, int>>
+inline PolyRef<I>::PolyRef(T&& t) noexcept {
+  _data_()->pobj_ =
+      const_cast<void*>(static_cast<void const*>(std::addressof(t)));
+  this->vptr_ = vtableFor<std::decay_t<I>, AddCvrefOf<std::decay_t<T>, I>>();
+}
+
+template <class I>
+template <
+    class I2,
+    std::enable_if_t<ReferenceCompatible<I, I2, I2&&>::value, int>>
+inline PolyRef<I>::PolyRef(Poly<I2>&& that) noexcept(
+    std::is_reference<I2>::value)
+    : PolyRef{that, Type<I2>{}} {
+  static_assert(
+      Disjunction<std::is_reference<I2>, std::is_rvalue_reference<I>>::value,
+      "Attempting to construct a Poly that is a reference to a temporary. "
+      "This is probably a mistake.");
+}
+
+template <class I>
+template <class T, std::enable_if_t<ModelsInterface<T, I>::value, int>>
+inline Poly<I>& PolyRef<I>::operator=(T&& t) noexcept {
+  *this = PolyRef(static_cast<T&&>(t));
+  return static_cast<Poly<I>&>(*this);
+}
+
+template <class I>
+template <
+    class I2,
+    std::enable_if_t<ReferenceCompatible<I, I2, I2&&>::value, int>>
+inline Poly<I>& PolyRef<I>::operator=(Poly<I2>&& that) noexcept(
+    std::is_reference<I2>::value) {
+  *this = PolyRef(std::move(that));
+  return static_cast<Poly<I>&>(*this);
+}
+
+template <class I>
+template <
+    class I2,
+    std::enable_if_t<ReferenceCompatible<I, I2, I2&>::value, int>>
+inline Poly<I>& PolyRef<I>::operator=(Poly<I2>& that) noexcept(
+    std::is_reference<I2>::value) {
+  *this = PolyRef(that);
+  return static_cast<Poly<I>&>(*this);
+}
+
+template <class I>
+template <
+    class I2,
+    std::enable_if_t<ReferenceCompatible<I, I2, I2 const&>::value, int>>
+inline Poly<I>& PolyRef<I>::operator=(Poly<I2> const& that) noexcept(
+    std::is_reference<I2>::value) {
+  *this = PolyRef(that);
+  return static_cast<Poly<I>&>(*this);
+}
+
+template <class I>
+inline void PolyRef<I>::swap(Poly<I>& that) noexcept {
+  std::swap(_data_()->pobj_, that._data_()->pobj_);
+  std::swap(this->vptr_, that.vptr_);
+}
+
+template <class I>
+inline AddCvrefOf<PolyImpl<I>, I>& PolyRef<I>::get() const noexcept {
+  return const_cast<AddCvrefOf<PolyImpl<I>, I>&>(
+      static_cast<PolyImpl<I> const&>(*this));
+}
+
+} // namespace detail
+} // namespace folly

diff --git a/folly/Poly.cpp b/folly/Poly.cpp
new file mode 100644 (file)
index 0000000..352b1a0
--- /dev/null
+++ b/folly/Poly.cpp
@@ -0,0 +1,24 @@
+/*
+ * Copyright 2017-present Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <folly/Poly.h>
+
+namespace folly {
+namespace detail {
+[[noreturn]] void throwBadPolyAccess() { throw BadPolyAccess(); }
+[[noreturn]] void throwBadPolyCast() { throw BadPolyCast(); }
+} // namespace detail
+} // namespace folly

diff --git a/folly/Poly.h b/folly/Poly.h
new file mode 100644 (file)
index 0000000..218fbd8
--- /dev/null
+++ b/folly/Poly.h
@@ -0,0 +1,1184 @@
+/*
+ * Copyright 2017-present Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+// TODO: [x] "cast" from Poly<C&> to Poly<C&&>
+// TODO: [ ] copy/move from Poly<C&>/Poly<C&&> to Poly<C>
+// TODO: [ ] copy-on-write?
+// TODO: [ ] down- and cross-casting? (Possible?)
+// TODO: [ ] shared ownership? (Dubious.)
+// TODO: [ ] can games be played with making the VTable a member of a struct
+//           with strange alignment such that the address of the VTable can
+//           be used to tell whether the object is stored in-situ or not?
+
+#pragma once
+
+#include <cassert>
+#include <new>
+#include <type_traits>
+#include <typeinfo>
+#include <utility>
+
+#include <folly/Assume.h>
+#include <folly/CppAttributes.h>
+#include <folly/Traits.h>
+#include <folly/detail/TypeList.h>
+
+#if !defined(__cpp_inline_variables)
+#define FOLLY_INLINE_CONSTEXPR constexpr
+#else
+#define FOLLY_INLINE_CONSTEXPR inline constexpr
+#endif
+
+#include <folly/detail/PolyDetail.h>
+
+namespace folly {
+template <class I>
+struct Poly;
+
+/**
+ * Within the definition of interface `I`, `PolySelf<Base>` is an alias for
+ * the instance of `Poly` that is currently being instantiated. It is
+ * one of: `Poly<J>`, `Poly<J&&>`, `Poly<J&>`, or `Poly<J const&>`; where
+ * `J` is either `I` or some interface that extends `I`.
+ *
+ * It can be used within interface definitions to declare members that accept
+ * other `Poly` objects of the same type as `*this`.
+ *
+ * The first parameter may optionally be cv- and/or reference-qualified, in
+ * which case, the qualification is applies to the type of the interface in the
+ * resulting `Poly<>` instance. The second template parameter controls whether
+ * or not the interface is decayed before the cv-ref qualifiers of the first
+ * argument are applied. For example, given the following:
+ *
+ *     struct Foo {
+ *       template <class Base>
+ *       struct Interface : Base {
+ *         using A = PolySelf<Base>;
+ *         using B = PolySelf<Base &>;
+ *         using C = PolySelf<Base const &>;
+ *         using X = PolySelf<Base, PolyDecay>;
+ *         using Y = PolySelf<Base &, PolyDecay>;
+ *         using Z = PolySelf<Base const &, PolyDecay>;
+ *       };
+ *       // ...
+ *     };
+ *     struct Bar : PolyExtends<Foo> {
+ *       // ...
+ *     };
+ *
+ * Then for `Poly<Bar>`, the typedefs are aliases for the following types:
+ * - `A` is `Poly<Bar>`
+ * - `B` is `Poly<Bar &>`
+ * - `C` is `Poly<Bar const &>`
+ * - `X` is `Poly<Bar>`
+ * - `Y` is `Poly<Bar &>`
+ * - `Z` is `Poly<Bar const &>`
+ *
+ * And for `Poly<Bar &>`, the typedefs are aliases for the following types:
+ * - `A` is `Poly<Bar &>`
+ * - `B` is `Poly<Bar &>`
+ * - `C` is `Poly<Bar &>`
+ * - `X` is `Poly<Bar>`
+ * - `Y` is `Poly<Bar &>`
+ * - `Z` is `Poly<Bar const &>`
+ */
+template <
+    class Node,
+    class Tfx = detail::MetaIdentity,
+    class Access = detail::PolyAccess>
+using PolySelf = decltype(Access::template self_<Node, Tfx>());
+
+/**
+ * When used in conjunction with `PolySelf`, controls how to construct `Poly`
+ * types related to the one currently being instantiated.
+ *
+ * \sa PolySelf
+ */
+using PolyDecay = detail::MetaQuote<std::decay_t>;
+
+#if !defined(__cpp_template_auto)
+
+/**
+ * Use `FOLLY_POLY_MEMBERS(MEMS...)` on pre-C++17 compilers to specify a
+ * comma-separated list of member function bindings.
+ *
+ * For example:
+ *
+ *     struct IFooBar {
+ *       template <class Base>
+ *       struct Interface : Base {
+ *         int foo() const { return folly::poly_call<0>(*this); }
+ *         void bar() { folly::poly_call<1>(*this); }
+ *       };
+ *       template <class T>
+ *       using Members = FOLLY_POLY_MEMBERS(&T::foo, &T::bar);
+ *     };
+ */
+#define FOLLY_POLY_MEMBERS(...)                     \
+  typename decltype(::folly::detail::deduceMembers( \
+      __VA_ARGS__))::template Members<__VA_ARGS__>
+
+/**
+ * Use `FOLLY_POLY_MEMBER(SIG, MEM)` on pre-C++17 compilers to specify a member
+ * function binding that needs to be disambiguated because of overloads. `SIG`
+ * should the (possibly const-qualified) signature of the `MEM` member function
+ * pointer.
+ *
+ * For example:
+ *
+ *     struct IFoo {
+ *       template <class Base> struct Interface : Base {
+ *         int foo() const { return folly::poly_call<0>(*this); }
+ *       };
+ *       template <class T> using Members = FOLLY_POLY_MEMBERS(
+ *         // This works even if T::foo is overloaded:
+ *         FOLLY_POLY_MEMBER(int()const, &T::foo)
+ *       );
+ *     };
+ */
+#define FOLLY_POLY_MEMBER(SIG, MEM) \
+  ::folly::detail::MemberDef<       \
+      ::folly::detail::Member<decltype(::folly::sig<SIG>(MEM)), MEM>>::value
+
+/**
+ * A list of member function bindings.
+ */
+template <class... Ts>
+using PolyMembers = detail::TypeList<Ts...>;
+
+#else
+#define FOLLY_POLY_MEMBER(SIG, MEM) ::folly::sig<SIG>(MEM)
+#define FOLLY_POLY_MEMBERS(...) ::folly::PolyMembers<__VA_ARGS__>
+
+template <auto... Ps>
+struct PolyMembers {};
+
+#endif
+
+/**
+ * Exception type that is thrown on invalid access of an empty `Poly` object.
+ */
+struct BadPolyAccess : std::exception {
+  BadPolyAccess() = default;
+  char const* what() const noexcept override {
+    return "BadPolyAccess";
+  }
+};
+
+/**
+ * Exception type that is thrown when attempting to extract from a `Poly` a
+ * value of the wrong type.
+ */
+struct BadPolyCast : std::bad_cast {
+  BadPolyCast() = default;
+  char const* what() const noexcept override {
+    return "BadPolyCast";
+  }
+};
+
+/**
+ * Used in the definition of a `Poly` interface to say that the current
+ * interface is an extension of a set of zero or more interfaces.
+ *
+ * Example:
+ *
+ *   struct IFoo {
+ *     template <class Base> struct Interface : Base {
+ *       void foo() { folly::poly_call<0>(*this); }
+ *     };
+ *     template <class T> using Members = FOLLY_POLY_MEMBERS(&T::foo);
+ *   }
+ *   struct IBar : PolyExtends<IFoo> {
+ *     template <class Base> struct Interface : Base {
+ *       void bar(int i) { folly::poly_call<0>(*this, i); }
+ *     };
+ *     template <class T> using Members = FOLLY_POLY_MEMBERS(&T::bar);
+ *   }
+ */
+template <class... I>
+struct PolyExtends : virtual I... {
+  using Subsumptions = detail::TypeList<I...>;
+
+  template <class Base>
+  struct Interface : Base {
+    Interface() = default;
+    using Base::Base;
+  };
+
+  template <class...>
+  using Members = PolyMembers<>;
+};
+
+////////////////////////////////////////////////////////////////////////////////
+/**
+ * Call the N-th member of the currently-being-defined interface. When the
+ * first parameter is an object of type `PolySelf<Base>` (as opposed to `*this`)
+ * you must explicitly specify which interface through which to dispatch.
+ * For instance:
+ *
+ *     struct IAddable {
+ *       template <class Base>
+ *       struct Interface : Base {
+ *         friend PolySelf<Base, Decay>
+ *         operator+(PolySelf<Base> const& a, PolySelf<Base> const& b) {
+ *           return folly::poly_call<0, IAddable>(a, b);
+ *         }
+ *       };
+ *       template <class T>
+ *       static auto plus_(T const& a, T const& b) -> decltype(a + b) {
+ *         return a + b;
+ *       }
+ *       template <class T>
+ *       using Members = FOLLY_POLY_MEMBERS(&plus_<std::decay_t<T>>);
+ *     };
+ *
+ * \sa PolySelf
+ */
+template <std::size_t N, typename This, typename... As>
+auto poly_call(This&& _this, As&&... as)
+    -> decltype(detail::PolyAccess::call<N>(
+        static_cast<This&&>(_this),
+        static_cast<As&&>(as)...)) {
+  return detail::PolyAccess::call<N>(
+      static_cast<This&&>(_this), static_cast<As&&>(as)...);
+}
+
+/// \overload
+template <std::size_t N, class I, class Tail, typename... As>
+decltype(auto) poly_call(detail::PolyNode<I, Tail>&& _this, As&&... as) {
+  using This = detail::InterfaceOf<I, detail::PolyNode<I, Tail>>;
+  return detail::PolyAccess::call<N>(
+      static_cast<This&&>(_this), static_cast<As&&>(as)...);
+}
+
+/// \overload
+template <std::size_t N, class I, class Tail, typename... As>
+decltype(auto) poly_call(detail::PolyNode<I, Tail>& _this, As&&... as) {
+  using This = detail::InterfaceOf<I, detail::PolyNode<I, Tail>>;
+  return detail::PolyAccess::call<N>(
+      static_cast<This&>(_this), static_cast<As&&>(as)...);
+}
+
+/// \overload
+template <std::size_t N, class I, class Tail, typename... As>
+decltype(auto) poly_call(detail::PolyNode<I, Tail> const& _this, As&&... as) {
+  using This = detail::InterfaceOf<I, detail::PolyNode<I, Tail>>;
+  return detail::PolyAccess::call<N>(
+      static_cast<This const&>(_this), static_cast<As&&>(as)...);
+}
+
+/// \overload
+template <
+    std::size_t N,
+    class I,
+    class Poly,
+    typename... As,
+    std::enable_if_t<detail::IsPoly<Poly>::value, int> = 0>
+auto poly_call(Poly&& _this, As&&... as) -> decltype(poly_call<N, I>(
+    static_cast<Poly&&>(_this).get(),
+    static_cast<As&&>(as)...)) {
+  return poly_call<N, I>(
+      static_cast<Poly&&>(_this).get(), static_cast<As&&>(as)...);
+}
+
+/// \cond
+/// \overload
+template <std::size_t N, class I, typename... As>
+[[noreturn]] detail::Bottom poly_call(detail::ArchetypeBase const&, As&&...) {
+  assume_unreachable();
+}
+/// \endcond
+
+////////////////////////////////////////////////////////////////////////////////
+/**
+ * Try to cast the `Poly` object to the requested type. If the `Poly` stores an
+ * object of that type, return a reference to the object; otherwise, throw an
+ * exception.
+ * \tparam T The (unqualified) type to which to cast the `Poly` object.
+ * \tparam Poly The type of the `Poly` object.
+ * \param that The `Poly` object to be cast.
+ * \return A reference to the `T` object stored in or refered to by `that`.
+ * \throw BadPolyAccess if `that` is empty.
+ * \throw BadPolyCast if `that` does not store or refer to an object of type
+ *        `T`.
+ */
+template <class T, class I>
+detail::AddCvrefOf<T, I>&& poly_cast(detail::PolyRoot<I>&& that) {
+  return detail::PolyAccess::cast<T>(std::move(that));
+}
+
+/// \overload
+template <class T, class I>
+detail::AddCvrefOf<T, I>& poly_cast(detail::PolyRoot<I>& that) {
+  return detail::PolyAccess::cast<T>(that);
+}
+
+/// \overload
+template <class T, class I>
+detail::AddCvrefOf<T, I> const& poly_cast(detail::PolyRoot<I> const& that) {
+  return detail::PolyAccess::cast<T>(that);
+}
+
+/// \cond
+/// \overload
+template <class T, class I>
+[[noreturn]] detail::AddCvrefOf<T, I>&& poly_cast(detail::ArchetypeRoot<I>&&) {
+  assume_unreachable();
+}
+
+/// \overload
+template <class T, class I>
+[[noreturn]] detail::AddCvrefOf<T, I>& poly_cast(detail::ArchetypeRoot<I>&) {
+  assume_unreachable();
+}
+
+/// \overload
+template <class T, class I>
+[[noreturn]] detail::AddCvrefOf<T, I> const& poly_cast(
+    detail::ArchetypeRoot<I> const&) { assume_unreachable(); }
+/// \endcond
+
+/// \overload
+template <
+    class T,
+    class Poly,
+    std::enable_if_t<detail::IsPoly<Poly>::value, int> = 0>
+constexpr auto poly_cast(Poly&& that)
+    -> decltype(poly_cast<T>(std::declval<Poly>().get())) {
+  return poly_cast<T>(static_cast<Poly&&>(that).get());
+}
+
+////////////////////////////////////////////////////////////////////////////////
+/**
+ * Returns a reference to the `std::type_info` object corresponding to the
+ * object currently stored in `that`. If `that` is empty, returns
+ * `typeid(void)`.
+ */
+template <class I>
+std::type_info const& poly_type(detail::PolyRoot<I> const& that) noexcept {
+  return detail::PolyAccess::type(that);
+}
+
+/// \cond
+/// \overload
+[[noreturn]] inline std::type_info const& poly_type(
+    detail::ArchetypeBase const&) noexcept {
+  assume_unreachable();
+}
+/// \endcond
+
+/// \overload
+template <class Poly, std::enable_if_t<detail::IsPoly<Poly>::value, int> = 0>
+constexpr auto poly_type(Poly const& that) noexcept
+    -> decltype(poly_type(that.get())) {
+  return poly_type(that.get());
+}
+
+////////////////////////////////////////////////////////////////////////////////
+/**
+ * Returns `true` if `that` is not currently storing an object; `false`,
+ * otherwise.
+ */
+template <class I>
+bool poly_empty(detail::PolyRoot<I> const& that) noexcept {
+  return detail::State::eEmpty == detail::PolyAccess::vtable(that)->state_;
+}
+
+/// \overload
+template <class I>
+constexpr bool poly_empty(detail::PolyRoot<I&&> const&) noexcept {
+  return false;
+}
+
+/// \overload
+template <class I>
+constexpr bool poly_empty(detail::PolyRoot<I&> const&) noexcept {
+  return false;
+}
+
+/// \overload
+template <class I>
+constexpr bool poly_empty(Poly<I&&> const&) noexcept {
+  return false;
+}
+
+/// \overload
+template <class I>
+constexpr bool poly_empty(Poly<I&> const&) noexcept {
+  return false;
+}
+
+/// \cond
+[[noreturn]] inline bool poly_empty(detail::ArchetypeBase const&) noexcept {
+  assume_unreachable();
+}
+/// \endcond
+
+////////////////////////////////////////////////////////////////////////////////
+/**
+ * Given a `Poly<I&>`, return a `Poly<I&&>`. Otherwise, when `I` is not a
+ * reference type, returns a `Poly<I>&&` when given a `Poly<I>&`, like
+ * `std::move`.
+ */
+template <
+    class I,
+    std::enable_if_t<detail::Not<std::is_reference<I>>::value, int> = 0>
+constexpr Poly<I>&& poly_move(detail::PolyRoot<I>& that) noexcept {
+  return static_cast<Poly<I>&&>(static_cast<Poly<I>&>(that));
+}
+
+/// \overload
+template <
+    class I,
+    std::enable_if_t<detail::Not<std::is_const<I>>::value, int> = 0>
+Poly<I&&> poly_move(detail::PolyRoot<I&> const& that) noexcept {
+  return detail::PolyAccess::move(that);
+}
+
+/// \overload
+template <class I>
+Poly<I const&> poly_move(detail::PolyRoot<I const&> const& that) noexcept {
+  return detail::PolyAccess::move(that);
+}
+
+/// \cond
+/// \overload
+[[noreturn]] inline detail::ArchetypeBase poly_move(
+    detail::ArchetypeBase const&) noexcept {
+  assume_unreachable();
+}
+/// \endcond
+
+/// \overload
+template <class Poly, std::enable_if_t<detail::IsPoly<Poly>::value, int> = 0>
+constexpr auto poly_move(Poly& that) noexcept
+    -> decltype(poly_move(that.get())) {
+  return poly_move(that.get());
+}
+
+/// \cond
+namespace detail {
+/**
+ * The implementation for `Poly` for when the interface type is not
+ * reference-like qualified, as in `Poly<SemiRegular>`.
+ */
+template <class I>
+struct PolyVal : PolyImpl<I> {
+ private:
+  friend PolyAccess;
+
+  struct NoneSuch {};
+  using Copyable = std::is_copy_constructible<PolyImpl<I>>;
+  using PolyOrNonesuch = If<Copyable::value, PolyVal, NoneSuch>;
+
+  using PolyRoot<I>::vptr_;
+
+  PolyRoot<I>& _polyRoot_() noexcept {
+    return *this;
+  }
+  PolyRoot<I> const& _polyRoot_() const noexcept {
+    return *this;
+  }
+
+  Data* _data_() noexcept {
+    return PolyAccess::data(*this);
+  }
+  Data const* _data_() const noexcept {
+    return PolyAccess::data(*this);
+  }
+
+ public:
+  /**
+   * Default constructor.
+   * \post `poly_empty(*this) == true`
+   */
+  PolyVal() = default;
+  /**
+   * Move constructor.
+   * \post `poly_empty(that) == true`
+   */
+  PolyVal(PolyVal&& that) noexcept;
+  /**
+   * A copy constructor if `I` is copyable; otherwise, a useless constructor
+   * from a private, incomplete type.
+   */
+  /* implicit */ PolyVal(PolyOrNonesuch const& that);
+
+  ~PolyVal();
+
+  /**
+   * Inherit any constructors defined by any of the interfaces.
+   */
+  using PolyImpl<I>::PolyImpl;
+
+  /**
+   * Copy assignment, destroys the object currently held (if any) and makes
+   * `*this` equal to `that` by stealing its guts.
+   */
+  Poly<I>& operator=(PolyVal that) noexcept;
+
+  /**
+   * Construct a Poly<I> from a concrete type that satisfies the I concept
+   */
+  template <class T, std::enable_if_t<ModelsInterface<T, I>::value, int> = 0>
+  /* implicit */ PolyVal(T&& t);
+
+  /**
+   * Construct a `Poly` from a compatible `Poly`. "Compatible" here means: the
+   * other interface extends this one either directly or indirectly.
+   */
+  template <class I2, std::enable_if_t<ValueCompatible<I, I2>::value, int> = 0>
+  /* implicit */ PolyVal(Poly<I2> that);
+
+  /**
+   * Assign to this `Poly<I>` from a concrete type that satisfies the `I`
+   * concept.
+   */
+  template <class T, std::enable_if_t<ModelsInterface<T, I>::value, int> = 0>
+  Poly<I>& operator=(T&& t);
+
+  /**
+   * Assign a compatible `Poly` to `*this`. "Compatible" here means: the
+   * other interface extends this one either directly or indirectly.
+   */
+  template <class I2, std::enable_if_t<ValueCompatible<I, I2>::value, int> = 0>
+  Poly<I>& operator=(Poly<I2> that);
+
+  /**
+   * Swaps the values of two `Poly` objects.
+   */
+  void swap(Poly<I>& that) noexcept;
+};
+
+////////////////////////////////////////////////////////////////////////////////
+/**
+ * The implementation of `Poly` for when the interface type is
+ * reference-quelified, like `Poly<SemuRegular &>`.
+ */
+template <class I>
+struct PolyRef : private PolyImpl<I> {
+ private:
+  friend PolyAccess;
+
+  AddCvrefOf<PolyRoot<I>, I>& _polyRoot_() const noexcept;
+
+  Data* _data_() noexcept {
+    return PolyAccess::data(*this);
+  }
+  Data const* _data_() const noexcept {
+    return PolyAccess::data(*this);
+  }
+
+  static constexpr RefType refType() noexcept;
+
+ protected:
+  template <class That, class I2>
+  PolyRef(That&& that, Type<I2>);
+
+ public:
+  /**
+   * Copy constructor
+   * \post `&poly_cast<T>(*this) == &poly_cast<T>(that)`, where `T` is the
+   *       type of the object held by `that`.
+   */
+  PolyRef(PolyRef const& that) noexcept;
+
+  /**
+   * Copy assignment
+   * \post `&poly_cast<T>(*this) == &poly_cast<T>(that)`, where `T` is the
+   *       type of the object held by `that`.
+   */
+  Poly<I>& operator=(PolyRef const& that) noexcept;
+
+  /**
+   * Construct a `Poly<I>` from a concrete type that satisfies concept `I`.
+   * \post `!poly_empty(*this)`
+   */
+  template <class T, std::enable_if_t<ModelsInterface<T, I>::value, int> = 0>
+  /* implicit */ PolyRef(T&& t) noexcept;
+
+  /**
+   * Construct a `Poly<I>` from a compatible `Poly<I2>`.
+   */
+  template <
+      class I2,
+      std::enable_if_t<ReferenceCompatible<I, I2, I2&&>::value, int> = 0>
+  /* implicit */ PolyRef(Poly<I2>&& that) noexcept(
+      std::is_reference<I2>::value);
+
+  template <
+      class I2,
+      std::enable_if_t<ReferenceCompatible<I, I2, I2&>::value, int> = 0>
+  /* implicit */ PolyRef(Poly<I2>& that) noexcept(std::is_reference<I2>::value)
+      : PolyRef{that, Type<I2>{}} {}
+
+  template <
+      class I2,
+      std::enable_if_t<ReferenceCompatible<I, I2, I2 const&>::value, int> = 0>
+  /* implicit */ PolyRef(Poly<I2> const& that) noexcept(
+      std::is_reference<I2>::value)
+      : PolyRef{that, Type<I2>{}} {}
+
+  /**
+   * Assign to a `Poly<I>` from a concrete type that satisfies concept `I`.
+   * \post `!poly_empty(*this)`
+   */
+  template <class T, std::enable_if_t<ModelsInterface<T, I>::value, int> = 0>
+  Poly<I>& operator=(T&& t) noexcept;
+
+  /**
+   * Assign to `*this` from another compatible `Poly`.
+   */
+  template <
+      class I2,
+      std::enable_if_t<ReferenceCompatible<I, I2, I2&&>::value, int> = 0>
+  Poly<I>& operator=(Poly<I2>&& that) noexcept(std::is_reference<I2>::value);
+
+  /**
+   * \overload
+   */
+  template <
+      class I2,
+      std::enable_if_t<ReferenceCompatible<I, I2, I2&>::value, int> = 0>
+  Poly<I>& operator=(Poly<I2>& that) noexcept(std::is_reference<I2>::value);
+
+  /**
+   * \overload
+   */
+  template <
+      class I2,
+      std::enable_if_t<ReferenceCompatible<I, I2, I2 const&>::value, int> = 0>
+  Poly<I>& operator=(Poly<I2> const& that) noexcept(
+      std::is_reference<I2>::value);
+
+  /**
+   * Swap which object this `Poly` references ("shallow" swap).
+   */
+  void swap(Poly<I>& that) noexcept;
+
+  /**
+   * Get a reference to the interface, with correct `const`-ness applied.
+   */
+  AddCvrefOf<PolyImpl<I>, I>& get() const noexcept;
+
+  /**
+   * Get a reference to the interface, with correct `const`-ness applied.
+   */
+  AddCvrefOf<PolyImpl<I>, I>& operator*() const noexcept {
+    return get();
+  }
+
+  /**
+   * Get a pointer to the interface, with correct `const`-ness applied.
+   */
+  auto operator-> () const noexcept {
+    return &get();
+  }
+};
+
+template <class I>
+using PolyValOrRef = If<std::is_reference<I>::value, PolyRef<I>, PolyVal<I>>;
+} // namespace detail
+/// \endcond
+
+/**
+ * `Poly` is a class template that makes it relatively easy to define a
+ * type-erasing polymorphic object wrapper.
+ *
+ * \par Type-erasure
+ *
+ * \par
+ * `std::function` is one example of a type-erasing polymorphic object wrapper;
+ * `folly::exception_wrapper` is another. Type-erasure is often used as an
+ * alternative to dynamic polymorphism via inheritance-based virtual dispatch.
+ * The distinguishing characteristic of type-erasing wrappers are:
+ * \li **Duck typing:** Types do not need to inherit from an abstract base
+ *     class in order to be assignable to a type-erasing wrapper; they merely
+ *     need to satisfy a particular interface.
+ * \li **Value semantics:** Type-erasing wrappers are objects that can be
+ *     passed around _by value_. This is in contrast to abstract base classes
+ *     which must be passed by reference or by pointer or else suffer from
+ *     _slicing_, which causes them to lose their polymorphic behaviors.
+ *     Reference semantics make it difficult to reason locally about code.
+ * \li **Automatic memory management:** When dealing with inheritance-based
+ *     dynamic polymorphism, it is often necessary to allocate and manage
+ *     objects on the heap. This leads to a proliferation of `shared_ptr`s and
+ *     `unique_ptr`s in APIs, complicating their point-of-use. APIs that take
+ *     type-erasing wrappers, on the other hand, can often store small objects
+ *     in-situ, with no dynamic allocation. The memory management, if any, is
+ *     handled for you, and leads to cleaner APIs: consumers of your API don't
+ *     need to pass `shared_ptr<AbstractBase>`; they can simply pass any object
+ *     that satisfies the interface you require. (`std::function` is a
+ *     particularly compelling example of this benefit. Far worse would be an
+ *     inheritance-based callable solution like
+ *     `shared_ptr<ICallable<void(int)>>`. )
+ *
+ * \par Example: Defining a type-erasing function wrapper with `folly::Poly`
+ *
+ * \par
+ * Defining a polymorphic wrapper with `Poly` is a matter of defining two
+ * things:
+ * \li An *interface*, consisting of public member functions, and
+ * \li A *mapping* from a concrete type to a set of member function bindings.
+ *
+ * Below is a (heavily commented) example of a simple implementation of a
+ * `std::function`-like polymorphic wrapper. Its interface has only a simgle
+ * member function: `operator()`
+ *
+ *     // An interface for a callable object of a particular signature, Fun
+ *     // (most interfaces don't need to be templates, FWIW).
+ *     template <class Fun>
+ *     struct IFunction;
+ *
+ *     template <class R, class... As>
+ *     struct IFunction<R(As...)> {
+ *       // An interface is defined as a nested class template called
+ *       // Interface that takes a single template parameter, Base, from
+ *       // which it inherits.
+ *       template <class Base>
+ *       struct Interface : Base {
+ *         // The Interface has public member functions. These become the
+ *         // public interface of the resulting Poly instantiation.
+ *         // (Implementation note: Poly<IFunction<Sig>> will publicly
+ *         // inherit from this struct, which is what gives it the right
+ *         // member functions.)
+ *         R operator()(As... as) const {
+ *           // The definition of each member function in your interface will
+ *           // always consist of a single line dispatching to
+ *           // folly::poly_call<N>. The "N" corresponds to the N-th member
+ *           // function in the list of member function bindings, Members,
+ *           // defined below. The first argument will always be *this, and the
+ *           // rest of the arguments should simply forward (if necessary) the
+ *           // member function's arguments.
+ *           return static_cast<R>(
+ *               folly::poly_call<0>(*this, std::forward<As>(as)...));
+ *         }
+ *       };
+ *
+ *       // The "Members" alias template is a comma-separated list of bound
+ *       // member functions for a given concrete type "T". The
+ *       // "FOLLY_POLY_MEMBERS" macro accepts a comma-separated list, and the
+ *       // (optional) "FOLLY_POLY_MEMBER" macro lets you disambiguate overloads
+ *       // by explicitly specifying the function signature the target member
+ *       // function should have. In this case, we require "T" to have a
+ *       // function call operator with the signature `R(As...) const`.
+ *       //
+ *       // If you are using a C++17-compatible compiler, you can do away with
+ *       // the macros and write this as:
+ *       //
+ *       //   template <class T>
+ *       //   using Members = folly::PolyMembers<
+ *       //       folly::sig<R(As...) const>(&T::operator())>;
+ *       //
+ *       // And since `folly::sig` is only needed for disambiguation in case of
+ *       // overloads, if you are not concerned about objects with overloaded
+ *       // function call operators, it could be further simplified to:
+ *       //
+ *       //   template <class T>
+ *       //   using Members = folly::PolyMembers<&T::operator()>;
+ *       //
+ *       template <class T>
+ *       using Members = FOLLY_POLY_MEMBERS(
+ *           FOLLY_POLY_MEMBER(R(As...) const, &T::operator()));
+ *     };
+ *
+ *     // Now that we have defined the interface, we can pass it to Poly to
+ *     // create our type-erasing wrapper:
+ *     template <class Fun>
+ *     using Function = Poly<IFunction<Fun>>;
+ *
+ * \par
+ * Given the above definition of `Function`, users can now initialize instances
+ * of (say) `Function<int(int, int)>` with function objects like
+ * `std::plus<int>` and `std::multiplies<int>`, as below:
+ *
+ *     Function<int(int, int)> fun = std::plus<int>{};
+ *     assert(5 == fun(2, 3));
+ *     fun = std::multiplies<int>{};
+ *     assert(6 = fun(2, 3));
+ *
+ * \par Defining an interface with C++17
+ *
+ * \par
+ * With C++17, defining an interface to be used with `Poly` is fairly
+ * straightforward. As in the `Function` example above, there is a struct with
+ * a nested `Interface` class template and a nested `Members` alias template.
+ * No macros are needed with C++17.
+ * \par
+ * Imagine we were defining something like a Java-style iterator. If we are
+ * using a C++17 compiler, our interface would look something like this:
+ *
+ *     template <class Value>
+ *     struct IJavaIterator {
+ *       template <class Base>
+ *       struct Interface : Base {
+ *         bool Done() const { return folly::poly_call<0>(*this); }
+ *         Value Current() const { return folly::poly_call<1>(*this); }
+ *         void Next() { folly::poly_call<2>(*this); }
+ *       };
+ *       // NOTE: This works in C++17 only:
+ *       template <class T>
+ *       using Members = folly::PolyMembers<&T::Done, &T::Current, &T::Next>;
+ *     };
+ *
+ *     template <class Value>
+ *     using JavaIterator = Poly<IJavaIterator>;
+ *
+ * \par
+ * Given the above definition, `JavaIterator<int>` can be used to hold instances
+ * of any type that has `Done`, `Current`, and `Next` member functions with the
+ * correct (or compatible) signatures.
+ *
+ * \par
+ * The presence of overloaded member functions complicates this picture. Often,
+ * property members are faked in C++ with `const` and non-`const` member
+ * function overloads, like in the interface specified below:
+ *
+ *     struct IIntProperty {
+ *       template <class Base>
+ *       struct Interface : Base {
+ *         int Value() const { return folly::poly_call<0>(*this); }
+ *         void Value(int i) { folly::poly_call<1>(*this, i); }
+ *       };
+ *       // NOTE: This works in C++17 only:
+ *       template <class T>
+ *       using Members = folly::PolyMembers<
+ *         folly::sig<int() const>(&T::Value),
+ *         folly::sig<void(int)>(&T::Value)>;
+ *     };
+ *
+ *     using IntProperty = Poly<IIntProperty>;
+ *
+ * \par
+ * Now, any object that has `Value` members of compatible signatures can be
+ * assigned to instances of `IntProperty` object. Note how `folly::sig` is used
+ * to disambiguate the overloads of `&T::Value`.
+ *
+ * \par Defining an interface with C++14
+ *
+ * \par
+ * In C++14, the nice syntax above doesn't work, so we have to resort to macros.
+ * The two examples above would look like this:
+ *
+ *     template <class Value>
+ *     struct IJavaIterator {
+ *       template <class Base>
+ *       struct Interface : Base {
+ *         bool Done() const { return folly::poly_call<0>(*this); }
+ *         Value Current() const { return folly::poly_call<1>(*this); }
+ *         void Next() { folly::poly_call<2>(*this); }
+ *       };
+ *       // NOTE: This works in C++14 and C++17:
+ *       template <class T>
+ *       using Members = FOLLY_POLY_MEMBERS(&T::Done, &T::Current, &T::Next);
+ *     };
+ *
+ *     template <class Value>
+ *     using JavaIterator = Poly<IJavaIterator>;
+ *
+ * \par
+ * and
+ *
+ *     struct IIntProperty {
+ *       template <class Base>
+ *       struct Interface : Base {
+ *         int Value() const { return folly::poly_call<0>(*this); }
+ *         void Value(int i) { return folly::poly_call<1>(*this, i); }
+ *       };
+ *       // NOTE: This works in C++14 and C++17:
+ *       template <class T>
+ *       using Members = FOLLY_POLY_MEMBERS(
+ *         FOLLY_POLY_MEMBER(int() const, &T::Value),
+ *         FOLLY_POLY_MEMBER(void(int), &T::Value));
+ *     };
+ *
+ *     using IntProperty = Poly<IIntProperty>;
+ *
+ * \par Extending interfaces
+ *
+ * \par
+ * One typical advantage of inheritance-based solutions to runtime polymorphism
+ * is that one polymorphic interface could extend another through inheritance.
+ * The same can be accomplished with type-erasing polymorphic wrappers. In
+ * the `Poly` library, you can use `folly::PolyExtends` to say that one
+ * interface extends another.
+ *
+ *     struct IFoo {
+ *       template <class Base>
+ *       struct Interface : Base {
+ *         void Foo() const { return folly::poly_call<0>(*this); }
+ *       };
+ *       template <class T>
+ *       using Members = FOLLY_POLY_MEMBERS(&T::Foo);
+ *     };
+ *
+ *     // The IFooBar interface extends the IFoo interface
+ *     struct IFooBar : PolyExtends<IFoo> {
+ *       template <class Base>
+ *       struct Interface : Base {
+ *         void Bar() const { return folly::poly_call<0>(*this); }
+ *       };
+ *       template <class T>
+ *       using Members = FOLLY_POLY_MEMBERS(&T::Bar);
+ *     };
+ *
+ *     using FooBar = Poly<IFooBar>;
+ *
+ * \par
+ * Given the above defintion, instances of type `FooBar` have both `Foo()` and
+ * `Bar()` member functions.
+ *
+ * \par
+ * The sensible conversions exist between a wrapped derived type and a wrapped
+ * base type. For instance, assuming `IDerived` extends `IBase` with
+ * `PolyExtends`:
+ *
+ *     Poly<IDerived> derived = ...;
+ *     Poly<IBase> base = derived; // This conversion is OK.
+ *
+ * \par
+ * As you would expect, there is no conversion in the other direction, and at
+ * present there is no `Poly` equivalent to `dynamic_cast`.
+ *
+ * \par Type-erasing polymorphic reference wrappers
+ *
+ * \par
+ * Sometimes you don't need to own a copy of an object; a reference will do. For
+ * that you can use `Poly` to capture a _reference_ to an object satisfying an
+ * interface rather than the whole object itself. The syntax is intuitive.
+ *
+ *     int i = 42;
+ *     // Capture a mutable reference to an object of any IRegular type:
+ *     Poly<IRegular &> intRef = i;
+ *     assert(42 == folly::poly_cast<int>(intRef));
+ *     // Assert that we captured the address of "i":
+ *     assert(&i == &folly::poly_cast<int>(intRef));
+ *
+ * \par
+ * A reference-like `Poly` has a different interface than a value-like `Poly`.
+ * Rather than calling member functions with the `obj.fun()` syntax, you would
+ * use the `obj->fun()` syntax. This is for the sake of `const`-correctness.
+ * For example, consider the code below:
+ *
+ *     struct IFoo {
+ *       template <class Base>
+ *       struct Interface {
+ *         void Foo() { folly::poly_call<0>(*this); }
+ *       };
+ *       template <class T>
+ *       using Members = folly::PolyMembers<&T::Foo>;
+ *     };
+ *
+ *     struct SomeFoo {
+ *       void Foo() { std::printf("SomeFoo::Foo\n"); }
+ *     };
+ *
+ *     SomeFoo foo;
+ *     Poly<IFoo &> const anyFoo = foo;
+ *     anyFoo->Foo(); // prints "SomeFoo::Foo"
+ *
+ * \par
+ * Notice in the above code that the `Foo` member function is non-`const`.
+ * Notice also that the `anyFoo` object is `const`. However, since it has
+ * captured a non-`const` reference to the `foo` object, it should still be
+ * possible to dispatch to the non-`const` `Foo` member function. When
+ * instantiated with a reference type, `Poly` has an overloaded `operator->`
+ * member that returns a pointer to the `IFoo` interface with the correct
+ * `const`-ness, which makes this work.
+ *
+ * \par
+ * The same mechanism also prevents users from calling non-`const` member
+ * functions on `Poly` objects that have captured `const` references, which
+ * would violate `const`-correctness.
+ *
+ * \par
+ * Sensible conversions exist between non-reference and reference `Poly`s. For
+ * instance:
+ *
+ *     Poly<IRegular> value = 42;
+ *     Poly<IRegular &> mutable_ref = value;
+ *     Poly<IRegular const &> const_ref = mutable_ref;
+ *
+ *     assert(&poly_cast<int>(value) == &poly_cast<int>(mutable_ref));
+ *     assert(&poly_cast<int>(value) == &poly_cast<int>(const_ref));
+ *
+ * \par Non-member functions (C++17)
+ *
+ * \par
+ * If you wanted to write the interface `ILogicallyNegatable`, which captures
+ * all types that can be negated with unary `operator!`, you could do it
+ * as we've shown above, by binding `&T::operator!` in the nested `Members`
+ * alias template, but that has the problem that it won't work for types that
+ * have defined unary `operator!` as a free function. To handle this case,
+ * the `Poly` library lets you use a free function instead of a member function
+ * when creating a binding.
+ *
+ * \par
+ * With C++17 you may use a lambda to create a binding, as shown in the example
+ * below:
+ *
+ *     struct ILogicallyNegatable {
+ *       template <class Base>
+ *       struct Interface : Base {
+ *         bool operator!() const { return folly::poly_call<0>(*this); }
+ *       };
+ *       template <class T>
+ *       using Members = folly::PolyMembers<
+ *         +[](T const& t) -> decltype(!t) { return !t; }>;
+ *     };
+ *
+ * \par
+ * This requires some explanation. The unary `operator+` in front of the lambda
+ * is necessary! It causes the lambda to decay to a C-style function pointer,
+ * which is one of the types that `folly::PolyMembers` accepts. The `decltype`
+ * in the lambda return type is also necessary. Through the magic of SFINAE, it
+ * will cause `Poly<ILogicallyNegatable>` to reject any types that don't support
+ * unary `operator!`.
+ *
+ * \par
+ * If you are using a free function to create a binding, the first parameter is
+ * implicitly the `this` parameter. It will receive the type-erased object.
+ *
+ * \par Non-member functions (C++14)
+ *
+ * \par
+ * If you are using a C++14 compiler, the defintion of `ILogicallyNegatable`
+ * above will fail because lambdas are not `constexpr`. We can get the same
+ * effect by writing the lambda as a named free function, as show below:
+ *
+ *     struct ILogicallyNegatable {
+ *       template <class Base>
+ *       struct Interface : Base {
+ *         bool operator!() const { return folly::poly_call<0>(*this); }
+ *       };
+ *
+ *       template <class T>
+ *       static auto negate(T const& t) -> decltype(!t) { return !t; }
+ *
+ *       template <class T>
+ *       using Members = FOLLY_POLY_MEMBERS(&negate<T>);
+ *     };
+ *
+ * \par
+ * As with the example that uses the lambda in the preceding section, the first
+ * parameter is implicitly the `this` parameter. It will receive the type-erased
+ * object.
+ *
+ * \par Multi-dispatch
+ *
+ * \par
+ * What if you want to create an `IAddable` interface for things that can be
+ * added? Adding requires _two_ objects, both of which are type-erased. This
+ * interface requires dispatching on both objects, doing the addition only
+ * if the types are the same. For this we make use of the `PolySelf` template
+ * alias to define an interface that takes more than one object of the the
+ * erased type.
+ *
+ *     struct IAddable {
+ *       template <class Base>
+ *       struct Interface : Base {
+ *         friend PolySelf<Base, Decay>
+ *         operator+(PolySelf<Base> const& a, PolySelf<Base> const& b) {
+ *           return folly::poly_call<0, IAddable>(a, b);
+ *         }
+ *       };
+ *
+ *       template <class T>
+ *       using Members = folly::PolyMembers<
+ *         +[](T const& a, T const& b) -> decltype(a + b) { return a + b; }>;
+ *     };
+ *
+ * \par
+ * Given the above defintion of `IAddable` we would be able to do the following:
+ *
+ *     Poly<IAddable> a = 2, b = 3;
+ *     Poly<IAddable> c = a + b;
+ *     assert(poly_cast<int>(c) == 5);
+ *
+ * \par
+ * If `a` and `b` stored objects of different types, a `BadPolyCast` exception
+ * would be thrown.
+ *
+ * \par Move-only types
+ *
+ * \par
+ * If you want to store move-only types, then your interface should extend the
+ * `IMoveOnly` interface.
+ *
+ * \par Implementation notes
+ * \par
+ * `Poly` will store "small" objects in an internal buffer, avoiding the cost of
+ * of dynamic allocations. At present, this size is not configurable; it is
+ * pegged at the size of two `double`s.
+ *
+ * \par
+ * `Poly` objects are always nothrow movable. If you store an object in one that
+ * has a potentially throwing move contructor, the object will be stored on the
+ * heap, even if it could fit in the internal storage of the `Poly` object.
+ * (So be sure to give your objects nothrow move constructors!)
+ *
+ * \par
+ * `Poly` implements type-erasure in a manner very similar to how the compiler
+ * accomplishes virtual dispatch. Every `Poly` object contains a pointer to a
+ * table of function pointers. Member function calls involve a double-
+ * indirection: once through the v-pointer, and other indirect function call
+ * through the function pointer.
+ */
+template <class I>
+struct Poly final : detail::PolyValOrRef<I> {
+  friend detail::PolyAccess;
+  Poly() = default;
+  using detail::PolyValOrRef<I>::PolyValOrRef;
+  using detail::PolyValOrRef<I>::operator=;
+};
+
+/**
+ * Swap two `Poly<I>` instances.
+ */
+template <class I>
+void swap(Poly<I>& left, Poly<I>& right) noexcept {
+  left.swap(right);
+}
+
+/**
+ * Pseudo-function template handy for disambiguating function overloads.
+ *
+ * For example, given:
+ *     struct S {
+ *       int property() const;
+ *       void property(int);
+ *     };
+ *
+ * You can get a member function pointer to the first overload with:
+ *     folly::sig<int()const>(&S::property);
+ *
+ * This is arguably a nicer syntax that using the built-in `static_cast`:
+ *     static_cast<int (S::*)() const>(&S::property);
+ *
+ * `sig` is also more permissive than `static_cast` about `const`. For instance,
+ * the following also works:
+ *     folly::sig<int()>(&S::property);
+ *
+ * The above is permitted
+ */
+template <class Sig>
+FOLLY_INLINE_CONSTEXPR detail::Sig<Sig> const sig = {};
+
+} // namespace folly
+
+#include <folly/Poly-inl.h>
+
+#undef FOLLY_INLINE_CONSTEXPR

diff --git a/folly/Traits.h b/folly/Traits.h
index ebf69acf7e30628fe0f5d7b88811ad5966833e8d..f513462af9dc2045ee795df172861d1ffa36b3ff 100644 (file)
--- a/folly/Traits.h
+++ b/folly/Traits.h
@@ -312,8 +312,9 @@ using is_trivially_copyable = std::is_trivially_copyable<T>;
 } // namespace traits_detail
 
 struct Ignore {
+  Ignore() = default;
   template <class T>
-  /* implicit */ Ignore(const T&) {}
+  constexpr /* implicit */ Ignore(const T&) {}
   template <class T>
   const Ignore& operator=(T const&) const { return *this; }
 };

diff --git a/folly/Utility.h b/folly/Utility.h
index bb196080c683ca52a4b86b0ac62bcda89983c765..1969a9644b20e63c9a0e92e5878c6b3df62de375 100644 (file)
--- a/folly/Utility.h
+++ b/folly/Utility.h
@@ -310,4 +310,11 @@ class MoveOnly {
 } // namespace moveonly_
 
 using MoveOnly = moveonly_::MoveOnly;
+
+/**
+ * A pithy alias for std::integral_constant<bool, B>.
+ */
+template <bool B>
+using Bool = std::integral_constant<bool, B>;
+
 } // namespace folly

diff --git a/folly/detail/PolyDetail.h b/folly/detail/PolyDetail.h
new file mode 100644 (file)
index 0000000..144a941
--- /dev/null
+++ b/folly/detail/PolyDetail.h
@@ -0,0 +1,922 @@
+/*
+ * Copyright 2017-present Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#pragma once
+
+#include <functional>
+#include <new>
+#include <tuple>
+#include <type_traits>
+#include <typeinfo>
+#include <utility>
+
+#include <folly/Traits.h>
+#include <folly/Utility.h>
+#include <folly/detail/TypeList.h>
+#include <folly/functional/Invoke.h>
+
+namespace folly {
+/// \cond
+namespace detail {
+template <class I>
+struct PolyRoot;
+
+using RRef_ = MetaQuoteTrait<std::add_rvalue_reference>;
+using LRef_ = MetaQuoteTrait<std::add_lvalue_reference>;
+
+template <typename T>
+struct XRef_ : Type<MetaQuoteTrait<Type>> {};
+template <typename T>
+using XRef = _t<XRef_<T>>;
+template <typename T>
+struct XRef_<T&&> : Type<MetaCompose<RRef_, XRef<T>>> {};
+template <typename T>
+struct XRef_<T&> : Type<MetaCompose<LRef_, XRef<T>>> {};
+template <typename T>
+struct XRef_<T const> : Type<MetaQuoteTrait<std::add_const>> {};
+
+template <class A, class B>
+using AddCvrefOf = MetaApply<XRef<B>, A>;
+} // namespace detail
+/// \endcond
+
+template <class I>
+struct Poly;
+
+template <class T, class I>
+detail::AddCvrefOf<T, I>& poly_cast(detail::PolyRoot<I>&);
+
+template <class T, class I>
+detail::AddCvrefOf<T, I> const& poly_cast(detail::PolyRoot<I> const&);
+
+#if !defined(__cpp_template_auto)
+#define FOLLY_AUTO class
+template <class... Ts>
+using PolyMembers = detail::TypeList<Ts...>;
+#else
+#define FOLLY_AUTO auto
+template <auto...>
+struct PolyMembers;
+#endif
+
+/// \cond
+namespace detail {
+/* *****************************************************************************
+ * IMPLEMENTATION NOTES
+ *
+
+Building the Interface
+----------------------
+
+Here is a high-level description of how Poly works. Users write an interface
+such as:
+
+  struct Mine {
+    template <class Base>
+    struct Interface {
+      int Exec() const {
+        return folly::poly_call<0>(*this);
+      }
+    }
+    template <class T>
+    using Members = folly::PolyMembers<&T::Exec>;
+  };
+
+Then they instantiate Poly<Mine>, which will have an Exec member function
+of the correct signature. The Exec member function comes from
+Mine::Interface<PolyNode<Mine, PolyRoot<Mine>>>, from which Poly<Mine> inherits.
+Here's what each piece means:
+
+- PolyRoot<I>: stores Data, which is a union of a void* (used when the Poly is
+  storing an object on the heap or a reference) and some aligned storage (used
+  when the Poly is storing an object in-situ). PolyRoot also stores a vtable
+  pointer for interface I, which is a pointer to a struct containing function
+  pointers. The function pointers are bound member functions (e.g.,
+  SomeType::Exec). More on the vtable pointer and how it is generated below.
+
+- PolyNode: provides the hooks used by folly::poly_call to dispatch to the
+correctly bound member function for this interface. In the context of an
+interface I, folly::poly_call<K>(*this, args...) will:
+    1. Fetch the vtable pointer from PolyRoot,
+    2. Select the I portion of that vtable (which, in the case of interface
+       extension, may only be a part of the total vtable),
+    3. Fetch the K-th function pointer from that vtable part,
+    4. Call through that function pointer, passing Data (from PolyRoot) and any
+       additional arguments in the folly::poly_call<K> invocation.
+
+In the case of interface extension -- for instance, if interface Mine extended
+interface Yours by inheriting from PolyExtends<Yours> -- then interface Mine
+will have a list of base interfaces in a typelist called "Subsumptions".
+Poly<Mine> will fold all the subsumed interfaces together, linearly inheriting
+from them. To take the example of an interface Mine that extends Yours,
+Poly<Mine> would inherit from this type:
+
+  Mine::Interface<
+    PolyNode<Mine,
+      Your::Interface<
+        PolyNode<Your, PolyRoot<Mine>>>>>
+
+Through linear inheritance, Poly<Mine> ends up with the public member functions
+of both interfaces, Mine and Yours.
+
+VTables
+-------
+
+As mentioned above, PolyRoot<I> stores a vtable pointer for interface I. The
+vtable is a struct whose members are function pointers. How are the types of
+those function pointers computed from the interface? A dummy type is created,
+Archetype<I>, in much the same way that Poly<I>'s base type is computed. Instead
+of PolyNode and PolyRoot, there is ArchetypeNode and ArchetypeRoot. These types
+also provide hooks for folly::poly_call, but they are dummy hooks that do
+nothing. (Actually, they call std::terminate; they will never be called.) Once
+Archetype<I> has been constructed, it is a concrete type that has all the
+member functions of the interface and its subsumed interfaces. That type is
+passed to Mine::Members, which takes the address of Archetype<I>::Exec and
+inspects the resulting member function type. This is done for each member in the
+interface. From a list of [member] function pointers, it is a simple matter of
+metaprogramming to build a struct of function pointers. std::tuple is used for
+this.
+
+An extra field is added to the tuple for a function that handles all of the
+"special" operations: destruction, copying, moving, getting the type
+information, getting the address of the stored object, and fetching a fixed-up
+vtable pointer for reference conversions (e.g., I -> I&, I& -> I const&, etc).
+
+Subsumed interfaces are handled by having VTable<IDerived> inherit from
+BasePtr<IBase>, where BasePtr<IBase> has only one member of type
+VTable<IBase> const*.
+
+Now that the type of VTable<I> is computed, how are the fields populated?
+Poly<I> default-constructs to an empty state. Its vtable pointer points to a
+vtable whose fields are initialized with the addresses of functions that do
+nothing but throw a BadPolyAccess exception. That way, if you call a member
+function on an empty Poly, you get an exception. The function pointer
+corresponding to the "special" operations points to a no-op function; copying,
+moving and destroying an empty Poly does nothing.
+
+On the other hand, when you pass an object of type T satisfying interface I to
+Poly<I>'s constructor or assignment operator, a vtable for {I,T} is reified by
+passing type T to I::Members, thereby creating a list of bindings for T's member
+functions. The address of this vtable gets stored in the PolyRoot<I> subobject,
+imbuing the Poly object with the behaviors of type T. The T object itself gets
+stored either on the heap or in the aligned storage within the Poly object
+itself, depending on the size of T and whether or not it has a noexcept move
+constructor.
+*/
+
+template <class T>
+using Uncvref = std::remove_cv_t<std::remove_reference_t<T>>;
+
+template <class T, template <class...> class U>
+struct IsInstanceOf : std::false_type {};
+
+template <class... Ts, template <class...> class U>
+struct IsInstanceOf<U<Ts...>, U> : std::true_type {};
+
+template <class T>
+using Not = Bool<!T::value>;
+
+template <class T>
+struct StaticConst {
+  static constexpr T value{};
+};
+
+template <class T>
+constexpr T StaticConst<T>::value;
+
+template <class Fun>
+void if_constexpr(std::true_type, Fun fun) {
+  fun(Identity{});
+}
+
+template <class Fun>
+void if_constexpr(std::false_type, Fun) {}
+
+enum class Op : short { eNuke, eMove, eCopy, eType, eAddr, eRefr };
+
+enum class RefType : std::uintptr_t { eRvalue, eLvalue, eConstLvalue };
+
+struct Data;
+
+template <class I>
+struct PolyVal;
+
+template <class I>
+struct PolyRef;
+
+struct PolyAccess;
+
+template <class T>
+using IsPoly = IsInstanceOf<Uncvref<T>, Poly>;
+
+// Given an interface I and a concrete type T that satisfies the interface
+// I, create a list of member function bindings from members of T to members
+// of I.
+template <class I, class T>
+using MembersOf = typename I::template Members<Uncvref<T>>;
+
+// Given an interface I and a base type T, create a type that implements
+// the interface I in terms of the capabilities of T.
+template <class I, class T>
+using InterfaceOf = typename I::template Interface<T>;
+
+[[noreturn]] void throwBadPolyAccess();
+[[noreturn]] void throwBadPolyCast();
+
+#if !defined(__cpp_template_auto)
+template <class T, T V>
+using Member = std::integral_constant<T, V>;
+
+template <class M>
+using MemberType = typename M::value_type;
+
+template <class M>
+inline constexpr MemberType<M> memberValue() noexcept {
+  return M::value;
+}
+
+template <class... Ts>
+struct MakeMembers {
+  template <Ts... Vs>
+  using Members = PolyMembers<Member<Ts, Vs>...>;
+};
+
+template <class... Ts>
+MakeMembers<Ts...> deduceMembers(Ts...);
+
+template <class Member, class = MemberType<Member>>
+struct MemberDef;
+
+template <class Member, class R, class D, class... As>
+struct MemberDef<Member, R (D::*)(As...)> {
+  static R value(D& d, As... as) {
+    return folly::invoke(memberValue<Member>(), d, static_cast<As&&>(as)...);
+  }
+};
+
+template <class Member, class R, class D, class... As>
+struct MemberDef<Member, R (D::*)(As...) const> {
+  static R value(D const& d, As... as) {
+    return folly::invoke(memberValue<Member>(), d, static_cast<As&&>(as)...);
+  }
+};
+
+#else
+template <auto M>
+using MemberType = decltype(M);
+
+template <auto M>
+inline constexpr MemberType<M> memberValue() noexcept {
+  return M;
+}
+#endif
+
+struct PolyBase {};
+
+template <class I, class = void>
+struct SubsumptionsOf_ {
+  using type = TypeList<>;
+};
+
+template <class I>
+using InclusiveSubsumptionsOf = TypePushFront<_t<SubsumptionsOf_<I>>, I>;
+
+template <class I>
+struct SubsumptionsOf_<I, void_t<typename I::Subsumptions>> {
+  using type = TypeJoin<TypeTransform<
+      typename I::Subsumptions,
+      MetaQuote<InclusiveSubsumptionsOf>>>;
+};
+
+template <class I>
+using SubsumptionsOf = TypeReverseUnique<_t<SubsumptionsOf_<I>>>;
+
+struct Bottom {
+  template <class T>
+  [[noreturn]] /* implicit */ operator T &&() const {
+    std::terminate();
+  }
+};
+
+using ArchetypeNode = MetaQuote<InterfaceOf>;
+
+template <class I>
+struct ArchetypeRoot;
+
+template <class I>
+using Archetype =
+    TypeFold<InclusiveSubsumptionsOf<I>, ArchetypeRoot<I>, ArchetypeNode>;
+
+struct ArchetypeBase : Bottom {
+  ArchetypeBase() = default;
+  template <class T>
+  /* implicit */ ArchetypeBase(T&&);
+  template <std::size_t, class... As>
+  [[noreturn]] Bottom _polyCall_(As&&...) const { std::terminate(); }
+
+  friend bool operator==(ArchetypeBase const&, ArchetypeBase const&);
+  friend bool operator!=(ArchetypeBase const&, ArchetypeBase const&);
+  friend bool operator<(ArchetypeBase const&, ArchetypeBase const&);
+  friend bool operator<=(ArchetypeBase const&, ArchetypeBase const&);
+  friend bool operator>(ArchetypeBase const&, ArchetypeBase const&);
+  friend bool operator>=(ArchetypeBase const&, ArchetypeBase const&);
+  friend Bottom operator++(ArchetypeBase const&);
+  friend Bottom operator++(ArchetypeBase const&, int);
+  friend Bottom operator--(ArchetypeBase const&);
+  friend Bottom operator--(ArchetypeBase const&, int);
+  friend Bottom operator+(ArchetypeBase const&, ArchetypeBase const&);
+  friend Bottom operator+=(ArchetypeBase const&, ArchetypeBase const&);
+  friend Bottom operator-(ArchetypeBase const&, ArchetypeBase const&);
+  friend Bottom operator-=(ArchetypeBase const&, ArchetypeBase const&);
+  friend Bottom operator*(ArchetypeBase const&, ArchetypeBase const&);
+  friend Bottom operator*=(ArchetypeBase const&, ArchetypeBase const&);
+  friend Bottom operator/(ArchetypeBase const&, ArchetypeBase const&);
+  friend Bottom operator/=(ArchetypeBase const&, ArchetypeBase const&);
+  friend Bottom operator%(ArchetypeBase const&, ArchetypeBase const&);
+  friend Bottom operator%=(ArchetypeBase const&, ArchetypeBase const&);
+  friend Bottom operator<<(ArchetypeBase const&, ArchetypeBase const&);
+  friend Bottom operator<<=(ArchetypeBase const&, ArchetypeBase const&);
+  friend Bottom operator>>(ArchetypeBase const&, ArchetypeBase const&);
+  friend Bottom operator>>=(ArchetypeBase const&, ArchetypeBase const&);
+};
+
+template <class I>
+struct ArchetypeRoot : ArchetypeBase {
+  template <class Node, class Tfx>
+  using _polySelf_ = Archetype<AddCvrefOf<MetaApply<Tfx, I>, Node>>;
+  using _polyInterface_ = I;
+};
+
+struct Data {
+  Data() = default;
+  // Suppress compiler-generated copy ops to not copy anything:
+  Data(Data const&) {}
+  Data& operator=(Data const&) {
+    return *this;
+  }
+  union {
+    void* pobj_ = nullptr;
+    std::aligned_storage_t<sizeof(double[2])> buff_;
+  };
+};
+
+template <class U, class I>
+using Arg =
+    If<std::is_same<Uncvref<U>, Archetype<I>>::value,
+       Poly<AddCvrefOf<I, U const&>>,
+       U>;
+
+template <class U, class I>
+using Ret =
+    If<std::is_same<Uncvref<U>, Archetype<I>>::value,
+       AddCvrefOf<Poly<I>, U>,
+       U>;
+
+template <class Member, class I>
+struct SignatureOf_;
+
+template <class R, class C, class... As, class I>
+struct SignatureOf_<R (C::*)(As...), I> {
+  using type = Ret<R, I> (*)(Data&, Arg<As, I>...);
+};
+
+template <class R, class C, class... As, class I>
+struct SignatureOf_<R (C::*)(As...) const, I> {
+  using type = Ret<R, I> (*)(Data const&, Arg<As, I>...);
+};
+
+template <class R, class This, class... As, class I>
+struct SignatureOf_<R (*)(This&, As...), I> {
+  using type = Ret<R, I> (*)(Data&, Arg<As, I>...);
+};
+
+template <class R, class This, class... As, class I>
+struct SignatureOf_<R (*)(This const&, As...), I> {
+  using type = Ret<R, I> (*)(Data const&, Arg<As, I>...);
+};
+
+template <FOLLY_AUTO Arch, class I>
+using SignatureOf = _t<SignatureOf_<MemberType<Arch>, I>>;
+
+template <FOLLY_AUTO User, class I, class Sig = SignatureOf<User, I>>
+struct ArgTypes_;
+
+template <FOLLY_AUTO User, class I, class Ret, class Data, class... Args>
+struct ArgTypes_<User, I, Ret (*)(Data, Args...)> {
+  using type = TypeList<Args...>;
+};
+
+template <FOLLY_AUTO User, class I>
+using ArgTypes = _t<ArgTypes_<User, I>>;
+
+template <class R, class... Args>
+using FnPtr = R (*)(Args...);
+
+struct ThrowThunk {
+  template <class R, class... Args>
+  constexpr /* implicit */ operator FnPtr<R, Args...>() const noexcept {
+    struct _ {
+      static R call(Args...) {
+        throwBadPolyAccess();
+      }
+    };
+    return &_::call;
+  }
+};
+
+inline constexpr ThrowThunk throw_() noexcept {
+  return ThrowThunk{};
+}
+
+template <class T>
+inline constexpr bool inSitu() noexcept {
+  return !std::is_reference<T>::value &&
+      sizeof(std::decay_t<T>) <= sizeof(Data) &&
+      std::is_nothrow_move_constructible<std::decay_t<T>>::value;
+}
+
+template <class T>
+T& get(Data& d) noexcept {
+  if (inSitu<T>()) {
+    return *(std::add_pointer_t<T>)static_cast<void*>(&d.buff_);
+  } else {
+    return *static_cast<std::add_pointer_t<T>>(d.pobj_);
+  }
+}
+
+template <class T>
+T const& get(Data const& d) noexcept {
+  if (inSitu<T>()) {
+    return *(std::add_pointer_t<T const>)static_cast<void const*>(&d.buff_);
+  } else {
+    return *static_cast<std::add_pointer_t<T const>>(d.pobj_);
+  }
+}
+
+enum class State : short { eEmpty, eInSitu, eOnHeap };
+
+template <class, class U>
+U&& convert(U&& u) noexcept {
+  return static_cast<U&&>(u);
+}
+
+template <class Arg, class I>
+decltype(auto) convert(Poly<I&> u) {
+  return poly_cast<Uncvref<Arg>>(u.get());
+}
+
+template <class Fun>
+struct IsConstMember : std::false_type {};
+
+template <class R, class C, class... As>
+struct IsConstMember<R (C::*)(As...) const> : std::true_type {};
+
+template <class R, class C, class... As>
+struct IsConstMember<R (*)(C const&, As...)> : std::true_type {};
+
+template <
+    class T,
+    FOLLY_AUTO User,
+    class I,
+    class = ArgTypes<User, I>,
+    class = Bool<true>>
+struct ThunkFn {
+  template <class R, class D, class... As>
+  constexpr /* implicit */ operator FnPtr<R, D&, As...>() const noexcept {
+    return nullptr;
+  }
+};
+
+template <class T, FOLLY_AUTO User, class I, class... Args>
+struct ThunkFn<
+    T,
+    User,
+    I,
+    TypeList<Args...>,
+    Bool<
+        !std::is_const<std::remove_reference_t<T>>::value ||
+        IsConstMember<MemberType<User>>::value>> {
+  template <class R, class D, class... As>
+  constexpr /* implicit */ operator FnPtr<R, D&, As...>() const noexcept {
+    struct _ {
+      static R call(D& d, As... as) {
+        return folly::invoke(
+            memberValue<User>(),
+            get<T>(d),
+            convert<Args>(static_cast<As&&>(as))...);
+      }
+    };
+    return &_::call;
+  }
+};
+
+template <
+    class I,
+    class = MembersOf<I, Archetype<I>>,
+    class = SubsumptionsOf<I>>
+struct VTable;
+
+template <class T, FOLLY_AUTO User, class I>
+inline constexpr ThunkFn<T, User, I> thunk() noexcept {
+  return ThunkFn<T, User, I>{};
+}
+
+template <class I>
+constexpr VTable<I> const* vtable() noexcept {
+  return &StaticConst<VTable<I>>::value;
+}
+
+template <class I, class T>
+struct VTableFor : VTable<I> {
+  constexpr VTableFor() noexcept : VTable<I>{Type<T>{}} {}
+};
+
+template <class I, class T>
+constexpr VTable<I> const* vtableFor() noexcept {
+  return &StaticConst<VTableFor<I, T>>::value;
+}
+
+template <class I, class T>
+constexpr void* vtableForRef(RefType ref) {
+  switch (ref) {
+    case RefType::eRvalue:
+      return const_cast<VTable<I>*>(vtableFor<I, T&&>());
+    case RefType::eLvalue:
+      return const_cast<VTable<I>*>(vtableFor<I, T&>());
+    case RefType::eConstLvalue:
+      return const_cast<VTable<I>*>(vtableFor<I, T const&>());
+  }
+  return nullptr;
+}
+
+template <
+    class I,
+    class T,
+    std::enable_if_t<std::is_reference<T>::value, int> = 0>
+void* execOnHeap(Op op, Data* from, void* to) {
+  switch (op) {
+    case Op::eNuke:
+      break;
+    case Op::eMove:
+    case Op::eCopy:
+      static_cast<Data*>(to)->pobj_ = from->pobj_;
+      break;
+    case Op::eType:
+      return const_cast<void*>(static_cast<void const*>(&typeid(T)));
+    case Op::eAddr:
+      if (*static_cast<std::type_info const*>(to) == typeid(T)) {
+        return from->pobj_;
+      }
+      throwBadPolyCast();
+    case Op::eRefr:
+      return vtableForRef<I, Uncvref<T>>(
+          static_cast<RefType>(reinterpret_cast<std::uintptr_t>(to)));
+  }
+  return nullptr;
+}
+
+template <
+    class I,
+    class T,
+    std::enable_if_t<Not<std::is_reference<T>>::value, int> = 0>
+void* execOnHeap(Op op, Data* from, void* to) {
+  switch (op) {
+    case Op::eNuke:
+      delete &get<T>(*from);
+      break;
+    case Op::eMove:
+      static_cast<Data*>(to)->pobj_ = std::exchange(from->pobj_, nullptr);
+      break;
+    case Op::eCopy:
+      detail::if_constexpr(std::is_copy_constructible<T>(), [&](auto id) {
+        static_cast<Data*>(to)->pobj_ = new T(id(get<T>(*from)));
+      });
+      break;
+    case Op::eType:
+      return const_cast<void*>(static_cast<void const*>(&typeid(T)));
+    case Op::eAddr:
+      if (*static_cast<std::type_info const*>(to) == typeid(T)) {
+        return from->pobj_;
+      }
+      throwBadPolyCast();
+    case Op::eRefr:
+      return vtableForRef<I, Uncvref<T>>(
+          static_cast<RefType>(reinterpret_cast<std::uintptr_t>(to)));
+  }
+  return nullptr;
+}
+
+template <class I, class T>
+void* execInSitu(Op op, Data* from, void* to) {
+  switch (op) {
+    case Op::eNuke:
+      get<T>(*from).~T();
+      break;
+    case Op::eMove:
+      ::new (static_cast<void*>(&static_cast<Data*>(to)->buff_))
+          T(std::move(get<T>(*from)));
+      get<T>(*from).~T();
+      break;
+    case Op::eCopy:
+      detail::if_constexpr(std::is_copy_constructible<T>(), [&](auto id) {
+        ::new (static_cast<void*>(&static_cast<Data*>(to)->buff_))
+            T(id(get<T>(*from)));
+      });
+      break;
+    case Op::eType:
+      return const_cast<void*>(static_cast<void const*>(&typeid(T)));
+    case Op::eAddr:
+      if (*static_cast<std::type_info const*>(to) == typeid(T)) {
+        return &from->buff_;
+      }
+      throwBadPolyCast();
+    case Op::eRefr:
+      return vtableForRef<I, Uncvref<T>>(
+          static_cast<RefType>(reinterpret_cast<std::uintptr_t>(to)));
+  }
+  return nullptr;
+}
+
+inline void* noopExec(Op op, Data*, void*) {
+  if (op == Op::eAddr)
+    throwBadPolyAccess();
+  return const_cast<void*>(static_cast<void const*>(&typeid(void)));
+}
+
+template <class I>
+struct BasePtr {
+  VTable<I> const* vptr_;
+};
+
+template <class I, class T, std::enable_if_t<inSitu<T>(), int> = 0>
+constexpr void* (*getOps() noexcept)(Op, Data*, void*) {
+  return &execInSitu<I, T>;
+}
+
+template <class I, class T, std::enable_if_t<!inSitu<T>(), int> = 0>
+constexpr void* (*getOps() noexcept)(Op, Data*, void*) {
+  return &execOnHeap<I, T>;
+}
+
+template <class I, FOLLY_AUTO... Arch, class... S>
+struct VTable<I, PolyMembers<Arch...>, TypeList<S...>>
+    : BasePtr<S>..., std::tuple<SignatureOf<Arch, I>...> {
+ private:
+  template <class T, FOLLY_AUTO... User>
+  constexpr VTable(Type<T>, PolyMembers<User...>) noexcept
+      : BasePtr<S>{vtableFor<S, T>()}...,
+        std::tuple<SignatureOf<Arch, I>...>{thunk<T, User, I>()...},
+        state_{inSitu<T>() ? State::eInSitu : State::eOnHeap},
+        ops_{getOps<I, T>()} {}
+
+ public:
+  constexpr VTable() noexcept
+      : BasePtr<S>{vtable<S>()}...,
+        std::tuple<SignatureOf<Arch, I>...>{
+            static_cast<SignatureOf<Arch, I>>(throw_())...},
+        state_{State::eEmpty},
+        ops_{&noopExec} {}
+
+  template <class T>
+  explicit constexpr VTable(Type<T>) noexcept
+      : VTable{Type<T>{}, MembersOf<I, T>{}} {}
+
+  State state_;
+  void* (*ops_)(Op, Data*, void*);
+};
+
+template <class I>
+constexpr VTable<I> const& select(VTable<_t<Type<I>>> const& vtbl) noexcept {
+  return vtbl;
+}
+
+template <class I>
+constexpr VTable<I> const& select(BasePtr<_t<Type<I>>> const& base) noexcept {
+  return *base.vptr_;
+}
+
+struct PolyAccess {
+  template <std::size_t N, typename This, typename... As>
+  static auto call(This&& _this, As&&... args)
+      -> decltype(static_cast<This&&>(_this).template _polyCall_<N>(
+          static_cast<As&&>(args)...)) {
+    static_assert(
+        !IsInstanceOf<std::decay_t<This>, Poly>::value,
+        "When passing a Poly<> object to call(), you must explicitly "
+        "say which Interface to dispatch to, as in "
+        "call<0, MyInterface>(self, args...)");
+    return static_cast<This&&>(_this).template _polyCall_<N>(
+        static_cast<As&&>(args)...);
+  }
+
+  template <class Poly>
+  using Iface = typename Uncvref<Poly>::_polyInterface_;
+
+  template <class Node, class Tfx = MetaIdentity>
+  static typename Uncvref<Node>::template _polySelf_<Node, Tfx> self_();
+
+  template <class T, class Poly, class I = Iface<Poly>>
+  static decltype(auto) cast(Poly&& _this) {
+    using Ret = AddCvrefOf<AddCvrefOf<T, I>, Poly&&>;
+    return static_cast<Ret>(
+        *static_cast<std::add_pointer_t<Ret>>(_this.vptr_->ops_(
+            Op::eAddr,
+            const_cast<Data*>(static_cast<Data const*>(&_this)),
+            const_cast<void*>(static_cast<void const*>(&typeid(T))))));
+  }
+
+  template <class Poly>
+  static decltype(auto) root(Poly&& _this) noexcept {
+    return static_cast<Poly&&>(_this)._polyRoot_();
+  }
+
+  template <class I>
+  static std::type_info const& type(PolyRoot<I> const& _this) noexcept {
+    return *static_cast<std::type_info const*>(
+        _this.vptr_->ops_(Op::eType, nullptr, nullptr));
+  }
+
+  template <class I>
+  static VTable<Uncvref<I>> const* vtable(PolyRoot<I> const& _this) noexcept {
+    return _this.vptr_;
+  }
+
+  template <class I>
+  static Data* data(PolyRoot<I>& _this) noexcept {
+    return &_this;
+  }
+
+  template <class I>
+  static Data const* data(PolyRoot<I> const& _this) noexcept {
+    return &_this;
+  }
+
+  template <class I>
+  static Poly<I&&> move(PolyRoot<I&> const& _this) noexcept {
+    return Poly<I&&>{_this, Type<I&>{}};
+  }
+
+  template <class I>
+  static Poly<I const&> move(PolyRoot<I const&> const& _this) noexcept {
+    return Poly<I const&>{_this, Type<I const&>{}};
+  }
+};
+
+template <class I, class Tail>
+struct PolyNode : Tail {
+ private:
+  friend PolyAccess;
+  using Tail::Tail;
+
+  template <std::size_t K, typename... As>
+  decltype(auto) _polyCall_(As&&... as) {
+    return std::get<K>(select<I>(*PolyAccess::vtable(*this)))(
+        *PolyAccess::data(*this), static_cast<As&&>(as)...);
+  }
+  template <std::size_t K, typename... As>
+  decltype(auto) _polyCall_(As&&... as) const {
+    return std::get<K>(select<I>(*PolyAccess::vtable(*this)))(
+        *PolyAccess::data(*this), static_cast<As&&>(as)...);
+  }
+};
+
+struct MakePolyNode {
+  template <class I, class State>
+  using apply = InterfaceOf<I, PolyNode<I, State>>;
+};
+
+template <class I>
+struct PolyRoot : private PolyBase, private Data {
+  friend PolyAccess;
+  friend Poly<I>;
+  friend PolyVal<I>;
+  friend PolyRef<I>;
+  template <class Node, class Tfx>
+  using _polySelf_ = Poly<AddCvrefOf<MetaApply<Tfx, I>, Node>>;
+  using _polyInterface_ = I;
+
+ private:
+  PolyRoot& _polyRoot_() noexcept {
+    return *this;
+  }
+  PolyRoot const& _polyRoot_() const noexcept {
+    return *this;
+  }
+  VTable<std::decay_t<I>> const* vptr_ = vtable<std::decay_t<I>>();
+};
+
+template <class I>
+using PolyImpl =
+    TypeFold<InclusiveSubsumptionsOf<Uncvref<I>>, PolyRoot<I>, MakePolyNode>;
+
+// A const-qualified function type means the user is trying to disambiguate
+// a member function pointer.
+template <class Fun> // Fun = R(As...) const
+struct Sig {
+  template <class T>
+  constexpr Fun T::*operator()(Fun T::*t) const /* nolint */ volatile noexcept {
+    return t;
+  }
+  template <class F, class T>
+  constexpr F T::*operator()(F T::*t) const /* nolint */ volatile noexcept {
+    return t;
+  }
+};
+
+// A functon type with no arguments means the user is trying to disambiguate
+// a member function pointer.
+template <class R>
+struct Sig<R()> : Sig<R() const> {
+  using Fun = R();
+  using Sig<R() const>::operator();
+
+  template <class T>
+  constexpr Fun T::*operator()(Fun T::*t) const noexcept {
+    return t;
+  }
+};
+
+template <class R, class... As>
+struct SigImpl : Sig<R(As...) const> {
+  using Fun = R(As...);
+  using Sig<R(As...) const>::operator();
+
+  template <class T>
+  constexpr Fun T::*operator()(Fun T::*t) const noexcept {
+    return t;
+  }
+  constexpr Fun* operator()(Fun* t) const noexcept {
+    return t;
+  }
+  template <class F>
+  constexpr F* operator()(F* t) const noexcept {
+    return t;
+  }
+};
+
+// The user could be trying to disambiguate either a member or a free function.
+template <class R, class... As>
+struct Sig<R(As...)> : SigImpl<R, As...> {};
+
+// This case is like the one above, except we want to add an overload that
+// handles the case of a free function where the first argument is more
+// const-qualified than the user explicitly specified.
+template <class R, class A, class... As>
+struct Sig<R(A&, As...)> : SigImpl<R, A&, As...> {
+  using CCFun = R(A const&, As...);
+  using SigImpl<R, A&, As...>::operator();
+
+  constexpr CCFun* operator()(CCFun* t) const /* nolint */ volatile noexcept {
+    return t;
+  }
+};
+
+template <
+    class T,
+    class I,
+    class U = std::decay_t<T>,
+    std::enable_if_t<Not<std::is_base_of<PolyBase, U>>::value, int> = 0,
+    std::enable_if_t<std::is_constructible<AddCvrefOf<U, I>, T>::value, int> =
+        0,
+    class = MembersOf<std::decay_t<I>, U>>
+std::true_type modelsInterface_(int);
+template <class T, class I>
+std::false_type modelsInterface_(long);
+
+template <class T, class I>
+struct ModelsInterface : decltype(modelsInterface_<T, I>(0)) {};
+
+template <class I1, class I2>
+struct ValueCompatible : std::is_base_of<I1, I2> {};
+
+// This prevents PolyRef's converting constructors and assignment operators
+// from being considered as copy constructors and assignment operators:
+template <class I1>
+struct ValueCompatible<I1, I1> : std::false_type {};
+
+template <class I1, class I2, class I2Ref>
+struct ReferenceCompatible : std::is_constructible<I1, I2Ref> {};
+
+// This prevents PolyRef's converting constructors and assignment operators
+// from being considered as copy constructors and assignment operators:
+template <class I1, class I2Ref>
+struct ReferenceCompatible<I1, I1, I2Ref> : std::false_type {};
+
+} // namespace detail
+/// \endcond
+} // namespace folly
+
+#undef FOLLY_AUTO

diff --git a/folly/detail/TypeList.h b/folly/detail/TypeList.h
new file mode 100644 (file)
index 0000000..bf0b303
--- /dev/null
+++ b/folly/detail/TypeList.h
@@ -0,0 +1,551 @@
+/*
+ * Copyright 2017-present Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#pragma once
+
+#include <cstddef>
+#include <utility>
+
+#include <folly/Traits.h>
+#include <folly/Utility.h>
+
+/**
+ * \file TypeList.h
+ * \author Eric Niebler
+ *
+ * The file contains facilities for manipulating lists of types, and for
+ * defining and composing operations over types.
+ *
+ * The type-operations behave like compile-time functions: they accept types as
+ * input and produce types as output. A simple example is a template alias, like
+ * `std::add_pointer_t`. However, templates are not themselves first class
+ * citizens of the language; they cannot be easily "returned" from a
+ * metafunction, and passing them to a metafunction is awkward and often
+ * requires the user to help the C++ parser by adding hints like `typename`
+ * and `template` to disambiguate the syntax. That makes higher-ordered
+ * metaprogramming difficult. (There is no simple way to e.g., compose two
+ * template aliases and pass the result as an argument to another template.)
+ *
+ * Instead, we wrap template aliases in a ordinary class, which _can_ be passed
+ * and returned simply from metafunctions. This is like Boost.MPL's notion of a
+ * "metafunction class"[1], and we adopt that terminology here.
+ *
+ * For the Folly.TypeList library, a metafunction class is a protocol that
+ * all the components of Folly.TypeList expect and agree upon. It is a class
+ * type that has a nested template alias called `Apply`. So for instance,
+ * `std::add_pointer_t` as a Folly metafunction class would look like this:
+ *
+ *     struct AddPointer {
+ *       template <class T>
+ *       using apply = T*;
+ *     };
+ *
+ * Folly.TypeList gives a simple way to "lift" an ordinary template alias into
+ * a metafunction class: `MetaQuote`. The above `AddPointer` could instead be
+ * written as:
+ *
+ *     using AddPointer = folly::MetaQuote<std::add_pointer_t>;
+ *
+ * \par Naming
+ *
+ * A word about naming. Components in Folly.TypeList fall into two buckets:
+ * utilities for manipulating lists of types, and utilities for manipulating
+ * metafunction classes. The former have names that start with `Type`, as in
+ * `TypeList` and `TypeTransform`. The latter have names that start with `Meta`,
+ * as in `MetaQuote` and `MetaApply`.
+ *
+ * [1] Boost.MPL Metafunction Class:
+ *     http://www.boost.org/libs/mpl/doc/refmanual/metafunction-class.html
+ */
+
+namespace folly {
+namespace detail {
+
+/**
+ * Handy shortcuts for some standard facilities
+ */
+template <bool B>
+using Bool = std::integral_constant<bool, B>;
+using True = std::true_type;
+using False = std::false_type;
+
+/**
+ * Given a metafunction class `Fn` and arguments `Ts...`, invoke `Fn`
+ * with `Ts...`.
+ */
+template <class Fn, class... Ts>
+using MetaApply = typename Fn::template apply<Ts...>;
+
+/**
+ * A list of types.
+ */
+template <class... Ts>
+struct TypeList {
+  /**
+   * An alias for this list of types
+   */
+  using type = TypeList;
+
+  /**
+   * \return the number of types in this list.
+   */
+  static constexpr std::size_t size() noexcept {
+    return sizeof...(Ts);
+  }
+
+  /**
+   * This list of types is also a metafunction class that accepts another
+   * metafunction class and invokes it with all the types in the list.
+   */
+  template <class Fn>
+  using apply = MetaApply<Fn, Ts...>;
+};
+
+/**
+ * A wrapper for a type
+ */
+template <class T>
+struct Type {
+  /**
+   * An alias for the wrapped type
+   */
+  using type = T;
+
+  /**
+   * This wrapper is a metafunction class that, when applied with any number
+   * of arguments, returns the wrapped type.
+   */
+  template <class...>
+  using apply = T;
+};
+
+/**
+ * An empty struct.
+ */
+struct Empty {};
+
+/// \cond
+namespace impl {
+template <bool B>
+struct If_ {
+  template <class T, class U>
+  using apply = T;
+};
+template <>
+struct If_<false> {
+  template <class T, class U>
+  using apply = U;
+};
+} // namespace impl
+/// \endcond
+
+/**
+ * Like std::conditional, but with fewer template instantiations
+ */
+template <bool If_, class Then, class Else>
+using If = MetaApply<impl::If_<If_>, Then, Else>;
+
+/**
+ * Defers the evaluation of an alias.
+ *
+ * Given a template `C` and arguments `Ts...`, then
+ * - If `C<Ts...>` is well-formed, `MetaApply<MetaDefer<C, Ts...>>` is well-
+ *   formed and is an alias for `C<Ts...>`.
+ * - Otherwise, `MetaApply<MetaDefer<C, Ts...>>` is ill-formed.
+ */
+template <template <class...> class C, class... Ts>
+class MetaDefer {
+  template <template <class...> class D = C, class = D<Ts...>>
+  static char (&try_(int))[1];
+  static char (&try_(long))[2];
+  struct Result {
+    using type = C<Ts...>;
+  };
+
+ public:
+  template <class... Us>
+  using apply = _t<If<sizeof(try_(0)) - 1 || sizeof...(Us), Empty, Result>>;
+};
+
+/**
+ * Compose two metafunction classes into one by chaining.
+ *
+ * `MetaApply<MetaCompose<P, Q>, Ts...>` is equivalent to
+ * `MetaApply<P, MetaApply<Q, Ts...>>`.
+ */
+template <class P, class Q>
+struct MetaCompose {
+  template <class... Ts>
+  using apply = MetaApply<P, MetaApply<Q, Ts...>>;
+};
+
+/**
+ * A metafunction class that always returns its argument unmodified.
+ *
+ * `MetaApply<MetaIdentity, int>` is equivalent to `int`.
+ */
+struct MetaIdentity {
+  template <class T>
+  using apply = T;
+};
+
+/**
+ * Lifts a class template or an alias template to be a metafunction class.
+ *
+ * `MetaApply<MetaQuote<C>, Ts...>` is equivalent to `C<Ts...>`.
+ */
+template <template <class...> class C>
+struct MetaQuote {
+  template <class... Ts>
+  using apply = MetaApply<MetaDefer<C, Ts...>>;
+};
+
+/// \cond
+// Specialization for TypeList since it doesn't need to go through MetaDefer
+template <>
+struct MetaQuote<TypeList> {
+  template <class... Ts>
+  using apply = TypeList<Ts...>;
+};
+/// \endcond
+
+/**
+ * Lifts a trait class template to be a metafunction class.
+ *
+ * `MetaApply<MetaQuoteTrait<C>, Ts...>` is equivalent to
+ * `typename C<Ts...>::type`.
+ */
+template <template <class...> class C>
+using MetaQuoteTrait = MetaCompose<MetaQuote<_t>, MetaQuote<C>>;
+
+/**
+ * Partially evaluate the metafunction class `Fn` by binding the arguments
+ * `Ts...` to the front of the argument list.
+ *
+ * `MetaApply<MetaBindFront<Fn, Ts...>, Us...>` is equivalent to
+ * `MetaApply<Fn, Ts..., Us...>`.
+ */
+template <class Fn, class... Ts>
+struct MetaBindFront {
+  template <class... Us>
+  using apply = MetaApply<Fn, Ts..., Us...>;
+};
+
+/**
+ * Partially evaluate the metafunction class `Fn` by binding the arguments
+ * `Ts...` to the back of the argument list.
+ *
+ * `MetaApply<MetaBindBack<Fn, Ts...>, Us...>` is equivalent to
+ * `MetaApply<Fn, Us..., Ts...>`.
+ */
+template <class Fn, class... Ts>
+struct MetaBindBack {
+  template <class... Us>
+  using apply = MetaApply<Fn, Us..., Ts...>;
+};
+
+/**
+ * Given a metafunction class `Fn` that expects a single `TypeList` argument,
+ * turn it into a metafunction class that takes `N` arguments, wraps them in
+ * a `TypeList`, and calls `Fn` with it.
+ *
+ * `MetaApply<MetaCurry<Fn>, Ts...>` is equivalent to
+ * `MetaApply<Fn, TypeList<Ts...>>`.
+ */
+template <class Fn>
+using MetaCurry = MetaCompose<Fn, MetaQuote<TypeList>>;
+
+/**
+ * Given a metafunction class `Fn` that expects `N` arguments,
+ * turn it into a metafunction class that takes a single `TypeList` arguments
+ * and calls `Fn` with the types in the `TypeList`.
+ *
+ * `MetaApply<MetaUncurry<Fn>, TypeList<Ts...>>` is equivalent to
+ * `MetaApply<Fn, Ts...>`.
+ */
+template <class Fn>
+using MetaUncurry = MetaBindBack<MetaQuote<MetaApply>, Fn>;
+
+/**
+ * Given a `TypeList` and some arguments, append those arguments to the end of
+ * the `TypeList`.
+ *
+ * `TypePushBack<TypeList<Ts...>, Us...>` is equivalent to
+ * `TypeList<Ts..., Us...>`.
+ */
+template <class List, class... Ts>
+using TypePushBack = MetaApply<List, MetaBindBack<MetaQuote<TypeList>, Ts...>>;
+
+/**
+ * Given a `TypeList` and some arguments, prepend those arguments to the start
+ * of the `TypeList`.
+ *
+ * `TypePushFront<TypeList<Ts...>, Us...>` is equivalent to
+ * `TypeList<Us..., Ts...>`.
+ */
+template <class List, class... Ts>
+using TypePushFront =
+    MetaApply<List, MetaBindFront<MetaQuote<TypeList>, Ts...>>;
+
+/**
+ * Given a metafunction class `Fn` and a `TypeList`, call `Fn` with the types
+ * in the `TypeList`.
+ */
+template <class Fn, class List>
+using MetaUnpack = MetaApply<List, Fn>;
+
+/// \cond
+namespace impl {
+template <class Fn>
+struct TypeTransform_ {
+  template <class... Ts>
+  using apply = TypeList<MetaApply<Fn, Ts>...>;
+};
+} // namespace impl
+/// \endcond
+
+/**
+ * Transform all the elements in a `TypeList` with the metafunction class `Fn`.
+ *
+ * `TypeTransform<TypeList<Ts..>, Fn>` is equivalent to
+ * `TypeList<MetaApply<Fn, Ts>...>`.
+ */
+template <class List, class Fn>
+using TypeTransform = MetaApply<List, impl::TypeTransform_<Fn>>;
+
+/**
+ * Given a binary metafunction class, convert it to another binary metafunction
+ * class with the argument order reversed.
+ */
+template <class Fn>
+struct MetaFlip {
+  template <class A, class B>
+  using apply = MetaApply<Fn, B, A>;
+};
+
+/// \cond
+namespace impl {
+template <class Fn>
+struct FoldR_ {
+  template <class... Ts>
+  struct Lambda : MetaIdentity {};
+  template <class A, class... Ts>
+  struct Lambda<A, Ts...> {
+    template <class State>
+    using apply = MetaApply<Fn, A, MetaApply<Lambda<Ts...>, State>>;
+  };
+  template <class A, class B, class C, class D, class... Ts>
+  struct Lambda<A, B, C, D, Ts...> { // manually unroll 4 elements
+    template <class State>
+    using apply = MetaApply<
+        Fn,
+        A,
+        MetaApply<
+            Fn,
+            B,
+            MetaApply<
+                Fn,
+                C,
+                MetaApply<Fn, D, MetaApply<Lambda<Ts...>, State>>>>>;
+  };
+  template <class... Ts>
+  using apply = Lambda<Ts...>;
+};
+} // namespace impl
+/// \endcond
+
+/**
+ * Given a `TypeList`, an initial state, and a binary function, reduce the
+ * `TypeList` by applying the function to each element and the current state,
+ * producing a new state to be used with the next element. This is a "right"
+ * fold in functional parlance.
+ *
+ * `TypeFold<TypeList<A, B, C>, X, Fn>` is equivalent to
+ * `MetaApply<Fn, A, MetaApply<Fn, B, MetaApply<Fn, C, X>>>`.
+ */
+template <class List, class State, class Fn>
+using TypeFold = MetaApply<MetaApply<List, impl::FoldR_<Fn>>, State>;
+
+/// \cond
+namespace impl {
+template <class Fn>
+struct FoldL_ {
+  template <class... Ts>
+  struct Lambda : MetaIdentity {};
+  template <class A, class... Ts>
+  struct Lambda<A, Ts...> {
+    template <class State>
+    using apply = MetaApply<Lambda<Ts...>, MetaApply<Fn, State, A>>;
+  };
+  template <class A, class B, class C, class D, class... Ts>
+  struct Lambda<A, B, C, D, Ts...> { // manually unroll 4 elements
+    template <class State>
+    using apply = MetaApply<
+        Lambda<Ts...>,
+        MetaApply<
+            Fn,
+            MetaApply<Fn, MetaApply<Fn, MetaApply<Fn, State, A>, B>, C>,
+            D>>;
+  };
+  template <class... Ts>
+  using apply = Lambda<Ts...>;
+};
+} // namespace impl
+/// \endcond
+
+/**
+ * Given a `TypeList`, an initial state, and a binary function, reduce the
+ * `TypeList` by applying the function to each element and the current state,
+ * producing a new state to be used with the next element. This is a "left"
+ * fold, in functional parlance.
+ *
+ * `TypeReverseFold<TypeList<A, B, C>, X, Fn>` is equivalent to
+ * `MetaApply<Fn, MetaApply<Fn, MetaApply<Fn, X, C>, B, A>`.
+ */
+template <class List, class State, class Fn>
+using TypeReverseFold = MetaApply<MetaApply<List, impl::FoldL_<Fn>>, State>;
+
+namespace impl {
+template <class List>
+struct Inherit_;
+template <class... Ts>
+struct Inherit_<TypeList<Ts...>> : Ts... {
+  using type = Inherit_;
+};
+} // namespace impl
+
+/**
+ * Given a `TypeList`, create a type that inherits from all the types in the
+ * list.
+ *
+ * Requires: all of the types in the list are non-final class types, and the
+ * types are all unique.
+ */
+template <class List>
+using Inherit = impl::Inherit_<List>;
+
+/// \cond
+namespace impl {
+// Avoid instantiating std::is_base_of when we have an intrinsic.
+#if defined(__GNUC__) || defined(_MSC_VER)
+template <class T, class... Set>
+using In_ = Bool<__is_base_of(Type<T>, Inherit<TypeList<Type<Set>...>>)>;
+#else
+template <class T, class... Set>
+using In_ = std::is_base_of<Type<T>, Inherit<TypeList<Type<Set>...>>>;
+#endif
+
+template <class T>
+struct InsertFront_ {
+  template <class... Set>
+  using apply =
+      If<In_<T, Set...>::value, TypeList<Set...>, TypeList<T, Set...>>;
+};
+
+struct Unique_ {
+  template <class T, class List>
+  using apply = MetaApply<List, impl::InsertFront_<T>>;
+};
+} // namespace impl
+/// \endcond
+
+/**
+ * Given a `TypeList`, produce a new list of types removing duplicates, keeping
+ * the first seen element.
+ *
+ * `TypeUnique<TypeList<int, short, int>>` is equivalent to
+ * `TypeList<int, short>`.
+ *
+ * \note This algorithm is O(N^2).
+ */
+template <class List>
+using TypeUnique = TypeFold<List, TypeList<>, impl::Unique_>;
+
+/**
+ * Given a `TypeList`, produce a new list of types removing duplicates, keeping
+ * the last seen element.
+ *
+ * `TypeUnique<TypeList<int, short, int>>` is equivalent to
+ * `TypeList<short, int>`.
+ *
+ * \note This algorithm is O(N^2).
+ */
+template <class List>
+using TypeReverseUnique =
+    TypeReverseFold<List, TypeList<>, MetaFlip<impl::Unique_>>;
+
+/// \cond
+namespace impl {
+template <class T>
+struct AsTypeList_ {};
+template <template <class...> class T, class... Ts>
+struct AsTypeList_<T<Ts...>> {
+  using type = TypeList<Ts...>;
+};
+template <class T, T... Is>
+struct AsTypeList_<folly::integer_sequence<T, Is...>> {
+  using type = TypeList<std::integral_constant<T, Is>...>;
+};
+} // namespace impl
+/// \endcond
+
+/**
+ * Convert a type to a list of types. Given a type `T`:
+ * - If `T` is of the form `C<Ts...>`, where `C` is a class template and
+ *   `Ts...` is a list of types, the result is `TypeList<Ts...>`.
+ * - Else, if `T` is of the form `std::integer_sequence<T, Is...>`, then
+ *   the result is `TypeList<std::integral_constant<T, Is>...>`.
+ * - Otherwise, `asTypeList<T>` is ill-formed.
+ */
+template <class T>
+using AsTypeList = _t<impl::AsTypeList_<T>>;
+
+/// \cond
+namespace impl {
+// TODO For a list of N lists, this algorithm is O(N). It does no unrolling.
+struct Join_ {
+  template <class Fn>
+  struct Lambda {
+    template <class... Ts>
+    using apply = MetaBindBack<Fn, Ts...>;
+  };
+  template <class List, class Fn>
+  using apply = MetaApply<List, Lambda<Fn>>;
+};
+} // namespace impl
+/// \endcond
+
+/**
+ * Given a `TypeList` of `TypeList`s, flatten the lists into a single list.
+ *
+ * `TypeJoin<TypeList<TypeList<As...>, TypeList<Bs...>>>` is equivalent to
+ * `TypeList<As..., Bs...>`
+ */
+template <class List>
+using TypeJoin = MetaApply<TypeFold<List, MetaQuote<TypeList>, impl::Join_>>;
+
+/**
+ * Given several `TypeList`s, flatten the lists into a single list.
+ *
+ * \note This is just the curried form of `TypeJoin`. (See `MetaCurry`.)
+ *
+ * `TypeConcat<TypeList<As...>, TypeList<Bs...>>` is equivalent to
+ * `TypeList<As..., Bs...>`
+ */
+template <class... Ts>
+using TypeConcat = TypeJoin<TypeList<Ts...>>;
+} // namespace detail
+} // namespace folly

diff --git a/folly/docs/Overview.md b/folly/docs/Overview.md
index e65e12f1139c067667ddd7fe0ab9b2d2604d1ecb..9bd527ba896fdcd8e8e94d33f398c2999cfcb472 100644 (file)
--- a/folly/docs/Overview.md
+++ b/folly/docs/Overview.md
@@ -163,6 +163,11 @@ chain several queues together with processing steps in between.
 A highly specialized data structure consisting of a pointer, a 1-bit
 spin lock, and a 15-bit integral, all inside one 64-bit word.
 
+#### [`Poly.h`](Poly.md)
+
+A class template that makes it relatively easy to define a type-erasing
+polymorphic object wrapper.
+
 #### `Preprocessor.h`
 
 Necessarily evil stuff.

diff --git a/folly/docs/Poly.md b/folly/docs/Poly.md
new file mode 100644 (file)
index 0000000..7064767
--- /dev/null
+++ b/folly/docs/Poly.md
@@ -0,0 +1,454 @@
+`folly/Poly.h`
+-------------------------------
+
+`Poly` is a class template that makes it relatively easy to define a
+type-erasing polymorphic object wrapper.
+
+### Type-erasure
+***
+
+`std::function` is one example of a type-erasing polymorphic object wrapper;
+`folly::exception_wrapper` is another. Type-erasure is often used as an
+alternative to dynamic polymorphism via inheritance-based virtual dispatch.
+The distinguishing characteristic of type-erasing wrappers are:
+
+* **Duck typing:** Types do not need to inherit from an abstract base
+    class in order to be assignable to a type-erasing wrapper; they merely
+    need to satisfy a particular interface.
+* **Value semantics:** Type-erasing wrappers are objects that can be
+    passed around _by value_. This is in contrast to abstract base classes
+    which must be passed by reference or by pointer or else suffer from
+    _slicing_, which causes them to lose their polymorphic behaviors.
+    Reference semantics make it difficult to reason locally about code.
+* **Automatic memory management:** When dealing with inheritance-based
+    dynamic polymorphism, it is often necessary to allocate and manage
+    objects on the heap. This leads to a proliferation of `shared_ptr`s and
+    `unique_ptr`s in APIs, complicating their point-of-use. APIs that take
+    type-erasing wrappers, on the other hand, can often store small objects
+    in-situ, with no dynamic allocation. The memory management, if any, is
+    handled for you, and leads to cleaner APIs: consumers of your API don't
+    need to pass `shared_ptr<AbstractBase>`; they can simply pass any object
+    that satisfies the interface you require. (`std::function` is a
+    particularly compelling example of this benefit. Far worse would be an
+    inheritance-based callable solution like
+    `shared_ptr<ICallable<void(int)>>`. )
+
+### Example: Defining a type-erasing function wrapper with `folly::Poly`
+***
+
+Defining a polymorphic wrapper with `Poly` is a matter of defining two
+things:
+
+* An *interface*, consisting of public member functions, and
+* A *mapping* from a concrete type to a set of member function bindings.
+
+Below is a (heavily commented) example of a simple implementation of a
+`std::function`-like polymorphic wrapper. Its interface has only a single
+member function: `operator()`
+
+``` Cpp
+    // An interface for a callable object of a particular signature, Fun
+    // (most interfaces don't need to be templates, FWIW).
+    template <class Fun>
+    struct IFunction;
+
+    template <class R, class... As>
+    struct IFunction<R(As...)> {
+      // An interface is defined as a nested class template called
+      // Interface that takes a single template parameter, Base, from
+      // which it inherits.
+      template <class Base>
+      struct Interface : Base {
+        // The Interface has public member functions. These become the
+        // public interface of the resulting Poly instantiation.
+        // (Implementation note: Poly<IFunction<Sig>> will publicly
+        // inherit from this struct, which is what gives it the right
+        // member functions.)
+        R operator()(As... as) const {
+          // The definition of each member function in your interface will
+          // always consist of a single line dispatching to folly::poly_call<N>.
+          // The "N" corresponds to the N-th member function in the
+          // list of member function bindings, Members, defined below.
+          // The first argument will always be *this, and the rest of the
+          // arguments should simply forward (if necessary) the member
+          // function's arguments.
+          return static_cast<R>(
+              folly::poly_call<0>(*this, std::forward<As>(as)...));
+        }
+      };
+      // The "Members" alias template is a comma-separated list of bound
+      // member functions for a given concrete type "T". The
+      // "FOLLY_POLY_MEMBERS" macro accepts a comma-separated list, and the
+      // (optional) "FOLLY_POLY_MEMBER" macro lets you disambiguate overloads
+      // by explicitly specifying the function signature the target member
+      // function should have. In this case, we require "T" to have a
+      // function call operator with the signature `R(As...) const`.
+      //
+      // If you are using a C++17-compatible compiler, you can do away with
+      // the macros and write this as:
+      //
+      //   template <class T>
+      //   using Members =
+      //       folly::PolyMembers<folly::sig<R(As...) const>(&T::operator())>;
+      //
+      // And since `folly::sig` is only needed for disambiguation in case of
+      // overloads, if you are not concerned about objects with overloaded
+      // function call operators, it could be further simplified to:
+      //
+      //   template <class T>
+      //   using Members = folly::PolyMembers<&T::operator()>;
+      //
+      template <class T>
+      using Members = FOLLY_POLY_MEMBERS(
+          FOLLY_POLY_MEMBER(R(As...) const, &T::operator()));
+    };
+
+    // Now that we have defined the interface, we can pass it to Poly to
+    // create our type-erasing wrapper:
+    template <class Fun>
+    using Function = Poly<IFunction<Fun>>;
+```
+
+Given the above definition of `Function`, users can now initialize instances
+of (say) `Function<int(int, int)>` with function objects like
+`std::plus<int>` and `std::multiplies<int>`, as below:
+
+``` Cpp
+    Function<int(int, int)> fun = std::plus<int>{};
+    assert(5 == fun(2, 3));
+    fun = std::multiplies<int>{};
+    assert(6 = fun(2, 3));
+```
+
+### Defining an interface with C++17
+***
+
+With C++17, defining an interface to be used with `Poly` is fairly
+straightforward. As in the `Function` example above, there is a struct with
+a nested `Interface` class template and a nested `Members` alias template.
+No macros are needed with C++17.
+
+Imagine we were defining something like a Java-style iterator. If we are
+using a C++17 compiler, our interface would look something like this:
+
+``` Cpp
+    template <class Value>
+    struct IJavaIterator {
+      template <class Base>
+      struct Interface : Base {
+        bool Done() const { return folly::poly_call<0>(*this); }
+        Value Current() const { return folly::poly_call<1>(*this); }
+        void Next() { folly::poly_call<2>(*this); }
+      };
+      // NOTE: This works in C++17 only:
+      template <class T>
+      using Members = folly::PolyMembers<&T::Done, &T::Current, &T::Next>;
+    };
+
+    template <class Value>
+    using JavaIterator = Poly<IJavaIterator>;
+```
+
+Given the above definition, `JavaIterator<int>` can be used to hold instances
+of any type that has `Done`, `Current`, and `Next` member functions with the
+correct (or compatible) signatures.
+
+The presence of overloaded member functions complicates this picture. Often,
+property members are faked in C++ with `const` and non-`const` member
+function overloads, like in the interface specified below:
+
+``` Cpp
+    struct IIntProperty {
+      template <class Base>
+      struct Interface : Base {
+        int Value() const { return folly::poly_call<0>(*this); }
+        void Value(int i) { folly::poly_call<1>(*this, i); }
+      };
+      // NOTE: This works in C++17 only:
+      template <class T>
+      using Members = folly::PolyMembers<
+        folly::sig<int() const>(&T::Value),
+        folly::sig<void(int)>(&T::Value)>;
+    };
+
+    using IntProperty = Poly<IIntProperty>;
+```
+
+Now, any object that has `Value` members of compatible signatures can be
+assigned to instances of `IntProperty` object. Note how `folly::sig` is used
+to disambiguate the overloads of `&T::Value`.
+
+### Defining an interface with C++14
+***
+
+In C++14, the nice syntax above doesn't work, so we have to resort to macros.
+The two examples above would look like this:
+
+``` Cpp
+    template <class Value>
+    struct IJavaIterator {
+      template <class Base>
+      struct Interface : Base {
+        bool Done() const { return folly::poly_call<0>(*this); }
+        Value Current() const { return folly::poly_call<1>(*this); }
+        void Next() { folly::poly_call<2>(*this); }
+      };
+      // NOTE: This works in C++14 and C++17:
+      template <class T>
+      using Members = FOLLY_POLY_MEMBERS(&T::Done, &T::Current, &T::Next);
+    };
+
+    template <class Value>
+    using JavaIterator = Poly<IJavaIterator>;
+```
+
+and
+
+``` Cpp
+    struct IIntProperty {
+      template <class Base>
+      struct Interface : Base {
+        int Value() const { return folly::poly_call<0>(*this); }
+        void Value(int i) { return folly::poly_call<1>(*this, i); }
+      };
+      // NOTE: This works in C++14 and C++17:
+      template <class T>
+      using Members = FOLLY_POLY_MEMBERS(
+        FOLLY_POLY_MEMBER(int() const, &T::Value),
+        FOLLY_POLY_MEMBER(void(int), &T::Value));
+    };
+
+    using IntProperty = Poly<IIntProperty>;
+```
+
+### Extending interfaces
+***
+
+One typical advantage of inheritance-based solutions to runtime polymorphism
+is that one polymorphic interface could extend another through inheritance.
+The same can be accomplished with type-erasing polymorphic wrappers. In
+the `Poly` library, you can use `folly::Extends` to say that one interface
+extends another.
+
+``` Cpp
+    struct IFoo {
+      template <class Base>
+      struct Interface : Base {
+        void Foo() const { return folly::poly_call<0>(*this); }
+      };
+      template <class T>
+      using Members = FOLLY_POLY_MEMBERS(&T::Foo);
+    };
+
+    // The IFooBar interface extends the IFoo interface
+    struct IFooBar : Extends<IFoo> {
+      template <class Base>
+      struct Interface : Base {
+        void Bar() const { return folly::poly_call<0>(*this); }
+      };
+      template <class T>
+      using Members = FOLLY_POLY_MEMBERS(&T::Bar);
+    };
+
+    using FooBar = Poly<IFooBar>;
+```
+
+Given the above defintion, instances of type `FooBar` have both `Foo()` and
+`Bar()` member functions.
+
+The sensible conversions exist between a wrapped derived type and a wrapped
+base type. For instance, assuming `IDerived` extends `IBase` with `Extends`:
+
+``` Cpp
+    Poly<IDerived> derived = ...;
+    Poly<IBase> base = derived; // This conversion is OK.
+```
+
+As you would expect, there is no conversion in the other direction, and at
+present there is no `Poly` equivalent to `dynamic_cast`.
+
+### Type-erasing polymorphic reference wrappers
+***
+
+Sometimes you don't need to own a copy of an object; a reference will do. For
+that you can use `Poly` to capture a _reference_ to an object satisfying an
+interface rather than the whole object itself. The syntax is intuitive.
+
+``` Cpp
+    int i = 42;
+
+    // Capture a mutable reference to an object of any IRegular type:
+    Poly<IRegular &> intRef = i;
+
+    assert(42 == folly::poly_cast<int>(intRef));
+    // Assert that we captured the address of "i":
+    assert(&i == &folly::poly_cast<int>(intRef));
+```
+
+A reference-like `Poly` has a different interface than a value-like `Poly`.
+Rather than calling member functions with the `obj.fun()` syntax, you would
+use the `obj->fun()` syntax. This is for the sake of `const`-correctness.
+For example, consider the code below:
+
+``` Cpp
+    struct IFoo {
+      template <class Base>
+      struct Interface {
+        void Foo() { folly::poly_call<0>(*this); }
+      };
+      template <class T>
+      using Members = folly::PolyMembers<&T::Foo>;
+    };
+
+    struct SomeFoo {
+      void Foo() { std::printf("SomeFoo::Foo\n"); }
+    };
+
+    SomeFoo foo;
+    Poly<IFoo &> const anyFoo = foo;
+    anyFoo->Foo(); // prints "SomeFoo::Foo"
+```
+
+Notice in the above code that the `Foo` member function is non-`const`.
+Notice also that the `anyFoo` object is `const`. However, since it has
+captured a non-`const` reference to the `foo` object, it should still be
+possible to dispatch to the non-`const` `Foo` member function. When
+instantiated with a reference type, `Poly` has an overloaded `operator->`
+member that returns a pointer to the `IFoo` interface with the correct
+`const`-ness, which makes this work.
+
+The same mechanism also prevents users from calling non-`const` member
+functions on `Poly` objects that have captured `const` references, which
+would violate `const`-correctness.
+
+Sensible conversions exist between non-reference and reference `Poly`s. For
+instance:
+
+``` Cpp
+    Poly<IRegular> value = 42;
+    Poly<IRegular &> mutable_ref = value;
+    Poly<IRegular const &> const_ref = mutable_ref;
+
+    assert(&poly_cast<int>(value) == &poly_cast<int>(mutable_ref));
+    assert(&poly_cast<int>(value) == &poly_cast<int>(const_ref));
+```
+
+### Non-member functions (C++17)
+***
+
+If you wanted to write the interface `ILogicallyNegatable`, which captures
+all types that can be negated with unary `operator!`, you could do it
+as we've shown above, by binding `&T::operator!` in the nested `Members`
+alias template, but that has the problem that it won't work for types that
+have defined unary `operator!` as a free function. To handle this case,
+the `Poly` library lets you use a free function instead of a member function
+when creating a binding.
+
+With C++17 you may use a lambda to create a binding, as shown in the example
+below:
+
+``` Cpp
+    struct ILogicallyNegatable {
+      template <class Base>
+      struct Interface : Base {
+        bool operator!() const { return folly::poly_call<0>(*this); }
+      };
+      template <class T>
+      using Members = folly::PolyMembers<
+        +[](T const& t) -> decltype(!t) { return !t; }>;
+    };
+```
+
+This requires some explanation. The unary `operator+` in front of the lambda
+is necessary! It causes the lambda to decay to a C-style function pointer,
+which is one of the types that `folly::PolyMembers` accepts. The `decltype` in
+the lambda return type is also necessary. Through the magic of SFINAE, it
+will cause `Poly<ILogicallyNegatable>` to reject any types that don't support
+unary `operator!`.
+
+If you are using a free function to create a binding, the first parameter is
+implicitly the `this` parameter. It will receive the type-erased object.
+
+### Non-member functions (C++14)
+***
+
+If you are using a C++14 compiler, the defintion of `ILogicallyNegatable`
+above will fail because lambdas are not `constexpr`. We can get the same
+effect by writing the lambda as a named free function, as show below:
+
+``` Cpp
+    struct ILogicallyNegatable {
+      template <class Base>
+      struct Interface : Base {
+        bool operator!() const { return folly::poly_call<0>(*this); }
+      };
+      template <class T>
+      static auto negate(T const& t) -> decltype(!t) { return !t; }
+      template <class T>
+      using Members = FOLLY_POLY_MEMBERS(&negate<T>);
+    };
+```
+
+As with the example that uses the lambda in the preceding section, the first
+parameter is implicitly the `this` parameter. It will receive the type-erased
+object.
+
+### Multi-dispatch
+***
+
+What if you want to create an `IAddable` interface for things that can be
+added? Adding requires _two_ objects, both of which are type-erased. This
+interface requires dispatching on both objects, doing the addition only
+if the types are the same. For this we make use of the `PolySelf` template
+alias to define an interface that takes more than one object of the the
+erased type.
+
+``` Cpp
+    struct IAddable {
+      template <class Base>
+      struct Interface : Base {
+        friend PolySelf<Base>
+        operator+(PolySelf<Base> const& a, PolySelf<Base> const& b) const {
+          return folly::poly_call<0>(a, b);
+        }
+      };
+      template <class T>
+      using Members = folly::PolyMembers<
+        +[](T const& a, T const& b) -> decltype(a + b) { return a + b; }>;
+    };
+```
+
+Given the above definition of `IAddable` we would be able to do the following:
+
+``` Cpp
+    Poly<IAddable> a = 2, b = 3;
+    Poly<IAddable> c = a + b;
+    assert(poly_cast<int>(c) == 5);
+```
+
+If `a` and `b` stored objects of different types, a `BadPolyCast` exception
+would be thrown.
+
+### Move-only types
+***
+
+If you want to store move-only types, then your interface should extend the
+`poly::IMoveOnly` interface.
+
+### Implementation notes
+***
+
+`Poly` will store "small" objects in an internal buffer, avoiding the cost of
+of dynamic allocations. At present, this size is not configurable; it is
+pegged at the size of two `double`s.
+
+`Poly` objects are always nothrow movable. If you store an object in one that
+has a potentially throwing move constructor, the object will be stored on the
+heap, even if it could fit in the internal storage of the `Poly` object.
+(So be sure to give your objects nothrow move constructors!)
+
+`Poly` implements type-erasure in a manner very similar to how the compiler
+accomplishes virtual dispatch. Every `Poly` object contains a pointer to a
+table of function pointers. Member function calls involve a double-
+indirection: once through the v-pointer, and other indirect function call
+through the function pointer.

diff --git a/folly/poly/Nullable.h b/folly/poly/Nullable.h
new file mode 100644 (file)
index 0000000..7b8d405
--- /dev/null
+++ b/folly/poly/Nullable.h
@@ -0,0 +1,90 @@
+/*
+ * Copyright 2017-present Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#pragma once
+
+#include <folly/Poly.h>
+#include <folly/poly/Regular.h>
+
+namespace folly {
+namespace poly {
+/**
+ * A `Poly` interface that can be used to make Poly objects initializable from
+ * `nullptr` (to create an empty `Poly`) and equality comparable to `nullptr`
+ * (to test for emptiness).
+ */
+struct INullablePointer : PolyExtends<IEqualityComparable> {
+  template <class Base>
+  struct Interface : Base {
+    Interface() = default;
+    using Base::Base;
+
+    /* implicit */ Interface(std::nullptr_t) : Base{} {
+      static_assert(
+          std::is_default_constructible<PolySelf<Base>>::value,
+          "Cannot initialize a non-default constructible Poly with nullptr");
+    }
+
+    PolySelf<Base>& operator=(std::nullptr_t) {
+      static_assert(
+          std::is_default_constructible<PolySelf<Base>>::value,
+          "Cannot initialize a non-default constructible Poly with nullptr");
+      auto& self = static_cast<PolySelf<Base>&>(*this);
+      self = PolySelf<Base>();
+      return self;
+    }
+
+    friend bool operator==(
+        std::nullptr_t,
+        PolySelf<Base> const& self) noexcept {
+      return poly_empty(self);
+    }
+    friend bool operator==(
+        PolySelf<Base> const& self,
+        std::nullptr_t) noexcept {
+      return poly_empty(self);
+    }
+    friend bool operator!=(
+        std::nullptr_t,
+        PolySelf<Base> const& self) noexcept {
+      return !poly_empty(self);
+    }
+    friend bool operator!=(
+        PolySelf<Base> const& self,
+        std::nullptr_t) noexcept {
+      return !poly_empty(self);
+    }
+  };
+};
+
+/**
+ * A `Poly` interface that can be used to make `Poly` objects contextually
+ * convertible to `bool` (`true` if and only if non-empty). It also gives
+ * `Poly` objects a unary logical negation operator.
+ */
+struct IBooleanTestable : PolyExtends<> {
+  template <class Base>
+  struct Interface : Base {
+    constexpr bool operator!() const noexcept {
+      return poly_empty(*this);
+    }
+    constexpr explicit operator bool() const noexcept {
+      return !!*this;
+    }
+  };
+};
+} // namespace poly
+} // namespace folly

diff --git a/folly/poly/Regular.h b/folly/poly/Regular.h
new file mode 100644 (file)
index 0000000..ec02ead
--- /dev/null
+++ b/folly/poly/Regular.h
@@ -0,0 +1,92 @@
+/*
+ * Copyright 2017-present Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#pragma once
+
+#include <folly/Poly.h>
+
+namespace folly {
+namespace poly {
+/**
+ * A `Poly` interface for types that are equality comparable.
+ */
+struct IEqualityComparable : PolyExtends<> {
+  template <class T>
+  static auto isEqual_(T const& _this, T const& that)
+      -> decltype(std::declval<bool (&)(bool)>()(_this == that)) {
+    return _this == that;
+  }
+
+  template <class T>
+  using Members = FOLLY_POLY_MEMBERS(&isEqual_<T>);
+};
+} // namespace poly
+
+/// \cond
+namespace detail {
+template <class I1, class I2>
+using Comparable = Conjunction<
+    std::is_same<std::decay_t<I1>, std::decay_t<I2>>,
+    std::is_base_of<poly::IEqualityComparable, std::decay_t<I1>>>;
+} // namespace detail
+/// \endcond
+
+template <
+    class I1,
+    class I2,
+    std::enable_if_t<detail::Comparable<I1, I2>::value, int> = 0>
+bool operator==(Poly<I1> const& _this, Poly<I2> const& that) {
+  return (poly_empty(_this) && poly_empty(that)) ||
+      (poly_type(_this) == poly_type(that) &&
+       ::folly::poly_call<0, poly::IEqualityComparable>(_this, that));
+}
+
+template <
+    class I1,
+    class I2,
+    std::enable_if_t<detail::Comparable<I1, I2>::value, int> = 0>
+bool operator!=(Poly<I1> const& _this, Poly<I2> const& that) {
+  return !(_this == that);
+}
+
+namespace poly {
+/**
+ * A `Poly` interface for types that are move-only.
+ */
+struct IMoveOnly : PolyExtends<> {
+  template <class Base>
+  struct Interface : Base {
+    Interface() = default;
+    Interface(Interface const&) = delete;
+    Interface(Interface&&) = default;
+    Interface& operator=(Interface const&) = delete;
+    Interface& operator=(Interface&&) = default;
+    using Base::Base;
+  };
+};
+
+/**
+ * A `Poly` interface for types that are copyable and movable.
+ */
+struct ISemiRegular : PolyExtends<> {};
+
+/**
+ * A `Poly` interface for types that are copyable, movable, and equality
+ * comparable.
+ */
+struct IRegular : PolyExtends<ISemiRegular, IEqualityComparable> {};
+} // namespace poly
+} // namespace folly

diff --git a/folly/test/Makefile.am b/folly/test/Makefile.am
index 0a5669308c1c3500bb1c302edd45209d9805f104..b55bc800d4826b362b91ffc961d257bffc22c678 100644 (file)
--- a/folly/test/Makefile.am
+++ b/folly/test/Makefile.am
@@ -223,6 +223,10 @@ fingerprint_test_SOURCES = FingerprintTest.cpp
 fingerprint_test_LDADD = libfollytestmain.la $(top_builddir)/libfollybenchmark.la
 TESTS += fingerprint_test
 
+poly_test_SOURCES = PolyTest.cpp
+poly_test_LDADD = libfollytestmain.la
+TESTS += poly_test
+
 portability_test_SOURCES = PortabilityTest.cpp
 portability_test_LDADD = libfollytestmain.la
 TESTS += portability_test
@@ -268,6 +272,10 @@ try_test_SOURCES = TryTest.cpp
 try_test_LDADD = libfollytestmain.la
 TESTS += try_test
 
+typelist_test_SOURCES = TypeListTest.cpp
+typelist_test_LDADD = libfollytestmain.la
+TESTS += typelist_test
+
 uncaught_exceptions_test_SOURCES = UncaughtExceptionsTest.cpp
 uncaught_exceptions_test_LDADD = libfollytestmain.la
 TESTS += uncaught_exceptions_test

diff --git a/folly/test/PolyTest.cpp b/folly/test/PolyTest.cpp
new file mode 100644 (file)
index 0000000..bbd13b8
--- /dev/null
+++ b/folly/test/PolyTest.cpp
@@ -0,0 +1,562 @@
+/*
+ * Copyright 2017 Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <folly/Poly.h>
+
+#include <folly/Conv.h>
+#include <folly/poly/Nullable.h>
+#include <folly/poly/Regular.h>
+#include <folly/portability/GTest.h>
+
+#include <array>
+
+using namespace folly;
+using namespace folly::poly;
+
+namespace {
+struct Big {
+ private:
+  std::array<char, sizeof(Poly<ISemiRegular>) + 1> data_;
+  int i_;
+
+ public:
+  Big() : data_{}, i_(0) {
+    ++s_count;
+  }
+  explicit Big(int i) : data_{}, i_(i) {
+    ++s_count;
+  }
+  Big(Big const& that) : data_(that.data_), i_(that.i_) {
+    ++s_count;
+  }
+  ~Big() {
+    --s_count;
+  }
+  Big& operator=(Big const&) = default;
+  int value() const {
+    return i_;
+  }
+  friend bool operator==(Big const& a, Big const& b) {
+    return a.value() == b.value();
+  }
+  friend bool operator!=(Big const& a, Big const& b) {
+    return !(a == b);
+  }
+  static std::ptrdiff_t s_count;
+};
+std::ptrdiff_t Big::s_count = 0;
+} // namespace
+
+TEST(Poly, SemiRegular) {
+  {
+    // A small object, storable in-situ:
+    Poly<ISemiRegular> p = 42;
+    EXPECT_EQ(typeid(int), poly_type(p));
+    EXPECT_EQ(42, poly_cast<int>(p));
+    EXPECT_THROW(poly_cast<short>(p), BadPolyCast);
+    Poly<ISemiRegular> p2 = p;
+    EXPECT_EQ(typeid(int), poly_type(p2));
+    EXPECT_EQ(42, poly_cast<int>(p2));
+    EXPECT_THROW(poly_cast<short>(p2), BadPolyCast);
+  }
+
+  EXPECT_EQ(0, Big::s_count);
+  {
+    // A big object, stored on the heap:
+    Poly<ISemiRegular> p = Big(42);
+    EXPECT_EQ(1, Big::s_count);
+    EXPECT_EQ(typeid(Big), poly_type(p));
+    EXPECT_EQ(42, poly_cast<Big>(p).value());
+    EXPECT_THROW(poly_cast<short>(p), BadPolyCast);
+    Poly<ISemiRegular> p2 = p;
+    EXPECT_EQ(2, Big::s_count);
+    EXPECT_EQ(typeid(Big), poly_type(p2));
+    EXPECT_EQ(42, poly_cast<Big>(p2).value());
+    EXPECT_THROW(poly_cast<short>(p2), BadPolyCast);
+  }
+  EXPECT_EQ(0, Big::s_count);
+}
+
+TEST(Poly, SemiRegularReference) {
+  int i = 42;
+  Poly<ISemiRegular&> p = i;
+  EXPECT_EQ(42, i);
+  EXPECT_EQ(typeid(int), poly_type(p));
+  EXPECT_EQ(42, poly_cast<int>(p));
+  EXPECT_EQ(&i, &poly_cast<int>(p));
+  EXPECT_THROW(poly_cast<short>(p), BadPolyCast);
+  // Can't default-initialize reference-like Poly's:
+  static_assert(!std::is_default_constructible<Poly<ISemiRegular&>>::value, "");
+}
+
+TEST(Poly, Conversions) {
+  int i = 42;
+  Poly<ISemiRegular> p1 = i;
+  Poly<ISemiRegular&> p2 = p1;
+  EXPECT_EQ(&poly_cast<int>(p1), &poly_cast<int>(p2));
+  Poly<ISemiRegular const&> p3 = p1;
+  Poly<ISemiRegular const&> p4 = p2;
+  EXPECT_EQ(&poly_cast<int>(p3), &poly_cast<int>(p1));
+  EXPECT_EQ(&poly_cast<int>(p4), &poly_cast<int>(p1));
+  static_assert(
+      !std::is_constructible<Poly<ISemiRegular&>, Poly<ISemiRegular const&>&>::
+          value,
+      "");
+  static_assert(
+      !std::is_constructible<Poly<ISemiRegular>, Poly<ISemiRegular const&>&>::
+          value,
+      "");
+}
+
+TEST(Poly, EqualityComparableReference) {
+  int i = 42;
+  int j = 42;
+  Poly<IEqualityComparable&> p1 = i;
+  Poly<IEqualityComparable&> p2 = j;
+  EXPECT_EQ(&i, &poly_cast<int>(p1));
+  EXPECT_EQ(&j, &poly_cast<int>(p2));
+  EXPECT_TRUE(p1 == p2);
+  EXPECT_FALSE(p1 != p2);
+  j = 43;
+  EXPECT_FALSE(p1 == p2);
+  EXPECT_TRUE(p1 != p2);
+  EXPECT_EQ(42, poly_cast<int>(p1));
+  EXPECT_EQ(43, poly_cast<int>(p2));
+}
+
+namespace {
+struct Foo {
+  template <class Base>
+  struct Interface : Base {
+    void foo(int& i) {
+      folly::poly_call<0>(*this, i);
+    }
+  };
+
+  template <class T>
+  using Members = FOLLY_POLY_MEMBERS(&T::foo);
+};
+
+struct foo_ {
+  foo_() = default;
+  explicit foo_(int i) : j_(i) {}
+  void foo(int& i) {
+    i += j_;
+  }
+
+ private:
+  int j_ = 0;
+};
+} // namespace
+
+TEST(Poly, Singular) {
+  Poly<Foo> p = foo_{42};
+  int i = 1;
+  p.foo(i);
+  EXPECT_EQ(43, i);
+  EXPECT_EQ(typeid(foo_), poly_type(p));
+}
+
+namespace {
+struct FooBar : PolyExtends<Foo> {
+  template <class Base>
+  struct Interface : Base {
+    std::string bar(int i) const {
+      return folly::poly_call<0>(*this, i);
+    }
+  };
+
+  template <class T>
+  using Members = FOLLY_POLY_MEMBERS(&T::bar);
+};
+
+struct foo_bar {
+  foo_bar() = default;
+  explicit foo_bar(int i) : j_(i) {}
+  void foo(int& i) {
+    i += j_;
+  }
+  std::string bar(int i) const {
+    i += j_;
+    return folly::to<std::string>(i);
+  }
+
+ private:
+  int j_ = 0;
+};
+} // namespace
+
+TEST(Poly, SingleInheritance) {
+  Poly<FooBar> p = foo_bar{42};
+  int i = 1;
+  p.foo(i);
+  EXPECT_EQ(43, i);
+  EXPECT_EQ("43", p.bar(1));
+  EXPECT_EQ(typeid(foo_bar), poly_type(p));
+
+  Poly<Foo> q = p; // OK, conversion works.
+  q.foo(i);
+  EXPECT_EQ(85, i);
+
+  Poly<Foo&> r = p;
+  r->foo(i);
+  EXPECT_EQ(127, i);
+  const_cast<Poly<Foo&> const&>(r)->foo(i);
+  EXPECT_EQ(169, i);
+
+  Poly<FooBar const&> cr = p;
+  // cr->foo(i); // ERROR: calls a non-const member through a const reference
+  cr->bar(i); // OK
+}
+
+namespace {
+struct Baz {
+  template <class Base>
+  struct Interface : Base {
+    std::string baz(int i, int j) const {
+      return folly::poly_call<0>(*this, i, j);
+    }
+  };
+
+  template <class T>
+  using Members = FOLLY_POLY_MEMBERS(&T::baz);
+};
+
+struct FooBarBazFizz : PolyExtends<FooBar, Baz> {
+  template <class Base>
+  struct Interface : Base {
+    std::string fizz() const {
+      return folly::poly_call<0>(*this);
+    }
+  };
+
+  template <class T>
+  using Members = FOLLY_POLY_MEMBERS(&T::fizz);
+};
+
+struct foo_bar_baz_fizz {
+  foo_bar_baz_fizz() = default;
+  explicit foo_bar_baz_fizz(int i) : j_(i) {}
+  void foo(int& i) {
+    i += j_;
+  }
+  std::string bar(int i) const {
+    return folly::to<std::string>(i + j_);
+  }
+  std::string baz(int i, int j) const {
+    return folly::to<std::string>(i + j);
+  }
+  std::string fizz() const {
+    return "fizz";
+  }
+
+ private:
+  int j_ = 0;
+};
+} // namespace
+
+TEST(Poly, MultipleInheritance) {
+  Poly<FooBarBazFizz> p = foo_bar_baz_fizz{42};
+  int i = 1;
+  p.foo(i);
+  EXPECT_EQ(43, i);
+  EXPECT_EQ("43", p.bar(1));
+  EXPECT_EQ("3", p.baz(1, 2));
+  EXPECT_EQ("fizz", p.fizz());
+  EXPECT_EQ(typeid(foo_bar_baz_fizz), poly_type(p));
+}
+
+namespace {
+struct Property {
+  template <class Base>
+  struct Interface : Base {
+    int prop() const {
+      return folly::poly_call<0>(*this);
+    }
+    void prop(int i) {
+      folly::poly_call<1>(*this, i);
+    }
+  };
+
+  template <class T>
+  using Members = FOLLY_POLY_MEMBERS(
+      FOLLY_POLY_MEMBER(int() const, &T::prop),
+      FOLLY_POLY_MEMBER(void(int), &T::prop));
+};
+
+struct property {
+  property() = default;
+  explicit property(int i) : j(i) {}
+  int prop() const {
+    return j;
+  }
+  void prop(int i) {
+    j = i;
+  }
+
+ private:
+  int j = 0;
+};
+} // namespace
+
+TEST(Poly, OverloadedMembers) {
+  Poly<Property> p = property{42};
+  EXPECT_EQ(typeid(property), poly_type(p));
+  EXPECT_EQ(42, p.prop());
+  p.prop(68);
+  EXPECT_EQ(68, p.prop());
+}
+
+TEST(Poly, NullablePointer) {
+  Poly<INullablePointer> p = nullptr;
+  Poly<INullablePointer> q{};
+  EXPECT_EQ(typeid(void), poly_type(p));
+  EXPECT_TRUE(poly_empty(p));
+  EXPECT_TRUE(p == q);
+  EXPECT_FALSE(p != q);
+  EXPECT_TRUE(p == nullptr);
+  EXPECT_TRUE(nullptr == p);
+  EXPECT_FALSE(p != nullptr);
+  EXPECT_FALSE(nullptr != p);
+
+  // No null references ever.
+  Poly<INullablePointer> r = 42;
+  Poly<INullablePointer&> s = r;
+  static_assert(!poly_empty(s), "");
+  EXPECT_THROW(Poly<INullablePointer&> r(q), BadPolyAccess);
+}
+
+namespace {
+struct MoveOnly_ {
+  MoveOnly_() = default;
+  MoveOnly_(MoveOnly_&&) = default;
+  MoveOnly_(MoveOnly_ const&) = delete;
+  MoveOnly_& operator=(MoveOnly_&&) = default;
+  MoveOnly_& operator=(MoveOnly_ const&) = delete;
+};
+} // namespace
+
+TEST(Poly, Move) {
+  {
+    int i = 42;
+    Poly<IMoveOnly&> p = i;
+    static_assert(
+        !std::is_convertible<Poly<IMoveOnly&>, Poly<IMoveOnly&&>>::value, "");
+    auto q = poly_move(p);
+    static_assert(std::is_same<decltype(q), Poly<IMoveOnly&&>>::value, "");
+    EXPECT_EQ(&poly_cast<int>(p), &poly_cast<int>(q));
+  }
+  {
+    int i = 42;
+    Poly<ISemiRegular const&> p = i;
+    auto q = poly_move(p);
+    static_assert(
+        std::is_same<decltype(q), Poly<ISemiRegular const&>>::value, "");
+    EXPECT_EQ(&poly_cast<int>(p), &poly_cast<int>(q));
+  }
+  {
+    Poly<IMoveOnly> p = MoveOnly_{};
+    static_assert(!std::is_copy_constructible<Poly<IMoveOnly>>::value, "");
+    auto q = poly_move(p);
+    static_assert(std::is_same<decltype(q), Poly<IMoveOnly>>::value, "");
+  }
+}
+
+TEST(Poly, RValueRef) {
+  int i = 42;
+  Poly<ISemiRegular&&> p = std::move(i);
+  static_assert(std::is_same<decltype(poly_cast<int>(p)), int&>::value, "");
+  EXPECT_EQ(&i, &poly_cast<int>(p));
+}
+
+namespace {
+template <class Fun>
+struct IFunction;
+
+template <class R, class... As>
+struct IFunction<R(As...)> {
+  template <class Base>
+  struct Interface : Base {
+    R operator()(As... as) const {
+      return static_cast<R>(
+          folly::poly_call<0>(*this, std::forward<As>(as)...));
+    }
+  };
+
+  template <class T>
+  using Members =
+      FOLLY_POLY_MEMBERS(FOLLY_POLY_MEMBER(R(As...) const, &T::operator()));
+};
+
+template <class Fun>
+using Function = Poly<IFunction<Fun>>;
+} // namespace
+
+TEST(Poly, Function) {
+  Function<int(int, int)> fun = std::plus<int>{};
+  EXPECT_EQ(42, fun(22, 20));
+  fun = std::multiplies<int>{};
+  EXPECT_EQ(22 * 20, fun(22, 20));
+}
+
+namespace {
+// This multiply extends IEqualityComparable
+struct IDiamond : PolyExtends<IRegular, INullablePointer> {};
+} // namespace
+
+TEST(Poly, DiamondInheritance) {
+  {
+    // A small object, storable in-situ:
+    Poly<IDiamond> p = 42;
+    EXPECT_EQ(typeid(int), poly_type(p));
+    EXPECT_EQ(42, poly_cast<int>(p));
+    EXPECT_THROW(poly_cast<short>(p), BadPolyCast);
+    Poly<IDiamond> p2 = p;
+    EXPECT_EQ(typeid(int), poly_type(p2));
+    EXPECT_EQ(42, poly_cast<int>(p2));
+    EXPECT_THROW(poly_cast<short>(p2), BadPolyCast);
+    Poly<IEqualityComparable&> eq = p;
+    EXPECT_EQ(&poly_cast<int>(p), &poly_cast<int>(eq));
+  }
+
+  EXPECT_EQ(0, Big::s_count);
+  {
+    // A big object, stored on the heap:
+    Poly<IDiamond> p = Big(42);
+    EXPECT_EQ(1, Big::s_count);
+    EXPECT_EQ(typeid(Big), poly_type(p));
+    EXPECT_EQ(42, poly_cast<Big>(p).value());
+    EXPECT_THROW(poly_cast<short>(p), BadPolyCast);
+    Poly<IDiamond> p2 = p;
+    EXPECT_EQ(2, Big::s_count);
+    EXPECT_EQ(typeid(Big), poly_type(p2));
+    EXPECT_EQ(42, poly_cast<Big>(p2).value());
+    EXPECT_THROW(poly_cast<short>(p2), BadPolyCast);
+    Poly<IEqualityComparable&> eq = p;
+    EXPECT_EQ(&poly_cast<Big>(p), &poly_cast<Big>(eq));
+  }
+  EXPECT_EQ(0, Big::s_count);
+}
+
+namespace {
+struct Struct {
+  int property() const {
+    return 42;
+  }
+  void property(int) {}
+};
+struct Struct2 : Struct {
+  int meow() {
+    return 42;
+  }
+
+  int purr() {
+    return 1;
+  }
+  int purr() const {
+    return 2;
+  }
+};
+
+int property(Struct const&) {
+  return 42;
+}
+void property(Struct&, int) {}
+
+int meow(Struct2&) {
+  return 42;
+}
+
+int purr(Struct2&) {
+  return 1;
+}
+int purr(Struct2 const&) {
+  return 2;
+}
+} // namespace
+
+TEST(Poly, Sig) {
+  {
+    auto m0 = folly::sig<int() const>(&Struct::property);
+    EXPECT_EQ(static_cast<int (Struct::*)() const>(&Struct::property), m0);
+    auto m1 = folly::sig<int()>(&Struct::property);
+    EXPECT_EQ(static_cast<int (Struct::*)() const>(&Struct::property), m1);
+
+    auto m2 = folly::sig<int() const>(&Struct2::property);
+    EXPECT_EQ(static_cast<int (Struct2::*)() const>(&Struct2::property), m2);
+    auto m3 = folly::sig<int()>(&Struct2::property);
+    EXPECT_EQ(static_cast<int (Struct2::*)() const>(&Struct2::property), m3);
+
+    auto m4 = folly::sig<long()>(&Struct2::meow);
+    EXPECT_EQ(&Struct2::meow, m4);
+
+    auto m5 = folly::sig<int()>(&Struct2::purr);
+    EXPECT_EQ(static_cast<int (Struct2::*)()>(&Struct2::purr), m5);
+    auto m6 = folly::sig<int() const>(&Struct2::purr);
+    EXPECT_EQ(static_cast<int (Struct2::*)() const>(&Struct2::purr), m6);
+  }
+  {
+    auto m0 = folly::sig<int(Struct const&)>(&::property);
+    EXPECT_EQ(static_cast<int (*)(Struct const&)>(&::property), m0);
+    auto m1 = folly::sig<int(Struct&)>(&::property);
+    EXPECT_EQ(static_cast<int (*)(Struct const&)>(&::property), m1);
+
+    auto m2 = folly::sig<long(Struct2&)>(&::meow);
+    EXPECT_EQ(&::meow, m2);
+
+    auto m3 = folly::sig<int(Struct2&)>(&::purr);
+    EXPECT_EQ(static_cast<int (*)(Struct2&)>(&::purr), m3);
+    auto m4 = folly::sig<int(Struct2 const&)>(&::purr);
+    EXPECT_EQ(static_cast<int (*)(Struct2 const&)>(&::purr), m4);
+  }
+}
+
+namespace {
+struct IAddable {
+  template <class Base>
+  struct Interface : Base {
+    friend PolySelf<Base, PolyDecay> operator+(
+        PolySelf<Base> const& a,
+        PolySelf<Base> const& b) {
+      return folly::poly_call<0, IAddable>(a, b);
+    }
+  };
+  template <class T>
+  static auto plus_(T const& a, T const& b) -> decltype(a + b) {
+    return a + b;
+  }
+
+  template <class T>
+  using Members = FOLLY_POLY_MEMBERS(&plus_<std::decay_t<T>>);
+};
+} // namespace
+
+TEST(Poly, Addable) {
+  Poly<IAddable> a = 2, b = 3;
+  Poly<IAddable> c = a + b;
+  EXPECT_EQ(typeid(int), poly_type(c));
+  EXPECT_EQ(5, poly_cast<int>(c));
+
+  Poly<IAddable const&> aref = a, bref = b;
+  auto cc = aref + bref;
+  static_assert(std::is_same<decltype(cc), Poly<IAddable>>::value, "");
+  EXPECT_EQ(typeid(int), poly_type(cc));
+  EXPECT_EQ(5, poly_cast<int>(cc));
+  b = 4;
+  EXPECT_EQ(5, poly_cast<int>(cc));
+  cc = aref + bref;
+  EXPECT_EQ(6, poly_cast<int>(cc));
+}

diff --git a/folly/test/TypeListTest.cpp b/folly/test/TypeListTest.cpp
new file mode 100644 (file)
index 0000000..70b3d68
--- /dev/null
+++ b/folly/test/TypeListTest.cpp
@@ -0,0 +1,122 @@
+/*
+ * Copyright 2017 Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <folly/detail/TypeList.h>
+#include <folly/portability/GTest.h>
+
+using namespace folly;
+using namespace detail;
+
+namespace {
+template <class T, class Ts, class = void>
+struct IsApplicable_ : std::false_type {};
+template <class T, class... Ts>
+struct IsApplicable_<T, TypeList<Ts...>, void_t<MetaApply<T, Ts...>>>
+    : std::true_type {};
+template <class T, class... Ts>
+using IsApplicable = IsApplicable_<T, TypeList<Ts...>>;
+} // namespace
+
+TEST(TypeList, Basic) {
+  static_assert(TypeList<>::size() == 0, "");
+  static_assert(TypeList<int>::size() == 1, "");
+  static_assert(TypeList<int, short, float>::size() == 3, "");
+}
+
+template <class T>
+using AddPointer = T*;
+
+TEST(TypeList, Defer) {
+  static_assert(
+      std::is_same<MetaApply<MetaDefer<AddPointer, int>>, int*>::value, "");
+  static_assert(!IsApplicable<MetaDefer<AddPointer, int, short>>::value, "");
+  static_assert(!IsApplicable<MetaDefer<AddPointer, int&>>::value, "");
+}
+
+TEST(TypeList, Transform) {
+  using Fn = MetaQuote<AddPointer>;
+  using T1 = TypeTransform<TypeList<>, Fn>;
+  static_assert(std::is_same<T1, TypeList<>>::value, "");
+  using T2 = TypeTransform<TypeList<int>, Fn>;
+  static_assert(std::is_same<T2, TypeList<int*>>::value, "");
+  using T3 = TypeTransform<TypeList<int, short, void>, Fn>;
+  static_assert(std::is_same<T3, TypeList<int*, short*, void*>>::value, "");
+}
+
+using Nil = Empty;
+template <class Car, class Cdr = Nil>
+struct Cons {};
+
+TEST(TypeList, Fold) {
+  using Fn = MetaQuote<Cons>;
+  using T1 = TypeFold<TypeList<int, short, void>, Nil, Fn>;
+  using E1 = Cons<int, Cons<short, Cons<void, Nil>>>;
+  static_assert(std::is_same<T1, E1>::value, "");
+
+  using T2 = TypeFold<TypeList<int, short, void, int*, short*, void*>, Nil, Fn>;
+  using E2 = Cons<
+      int,
+      Cons<short, Cons<void, Cons<int*, Cons<short*, Cons<void*, Nil>>>>>>;
+  static_assert(std::is_same<T2, E2>::value, "");
+
+  using T3 = TypeReverseFold<TypeList<int, short, void>, Nil, MetaFlip<Fn>>;
+  using E3 = Cons<void, Cons<short, Cons<int, Nil>>>;
+  static_assert(std::is_same<T3, E3>::value, "");
+
+  using T4 = TypeReverseFold<
+      TypeList<int, short, void, int*, short*, void*>,
+      Nil,
+      MetaFlip<Fn>>;
+  using E4 = Cons<
+      void*,
+      Cons<short*, Cons<int*, Cons<void, Cons<short, Cons<int, Nil>>>>>>;
+  static_assert(std::is_same<T4, E4>::value, "");
+}
+
+TEST(TypeList, Unique) {
+  using T1 = TypeUnique<TypeList<int, int, int, short, int, short>>;
+  static_assert(std::is_same<T1, TypeList<int, short>>::value, "");
+
+  using T2 = TypeReverseUnique<TypeList<int, int, int, short, int, short>>;
+  static_assert(std::is_same<T2, TypeList<short, int>>::value, "");
+}
+
+TEST(TypeList, PushFront) {
+  using T1 = TypePushFront<TypeList<>, int, short>;
+  static_assert(std::is_same<T1, TypeList<int, short>>::value, "");
+
+  using T2 = TypePushFront<T1, float, double, struct XXX>;
+  static_assert(
+      std::is_same<T2, TypeList<float, double, struct XXX, int, short>>::value,
+      "");
+}
+
+TEST(TypeList, PushBack) {
+  using T1 = TypePushBack<TypeList<>, int, short>;
+  static_assert(std::is_same<T1, TypeList<int, short>>::value, "");
+
+  using T2 = TypePushBack<T1, float, double, struct XXX>;
+  static_assert(
+      std::is_same<T2, TypeList<int, short, float, double, struct XXX>>::value,
+      "");
+}
+
+TEST(TypeList, Join) {
+  using T1 = TypeJoin<
+      TypeList<TypeList<int>, TypeList<short, float>, TypeList<void*>>>;
+  static_assert(
+      std::is_same<T1, TypeList<int, short, float, void*>>::value, "");
+}