folly/detail/PolyDetail.h

   1 /*
   2  * Copyright 2017-present Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #pragma once
  18
  19 #include <functional>
  20 #include <new>
  21 #include <tuple>
  22 #include <type_traits>
  23 #include <typeinfo>
  24 #include <utility>
  25
  26 #include <folly/Traits.h>
  27 #include <folly/Utility.h>
  28 #include <folly/detail/TypeList.h>
  29 #include <folly/functional/Invoke.h>
  30
  31 namespace folly {
  32 /// \cond
  33 namespace detail {
  34 template <class I>
  35 struct PolyRoot;
  36
  37 using RRef_ = MetaQuoteTrait<std::add_rvalue_reference>;
  38 using LRef_ = MetaQuoteTrait<std::add_lvalue_reference>;
  39
  40 template <typename T>
  41 struct XRef_ : Type<MetaQuoteTrait<Type>> {};
  42 template <typename T>
  43 using XRef = _t<XRef_<T>>;
  44 template <typename T>
  45 struct XRef_<T&&> : Type<MetaCompose<RRef_, XRef<T>>> {};
  46 template <typename T>
  47 struct XRef_<T&> : Type<MetaCompose<LRef_, XRef<T>>> {};
  48 template <typename T>
  49 struct XRef_<T const> : Type<MetaQuoteTrait<std::add_const>> {};
  50
  51 template <class A, class B>
  52 using AddCvrefOf = MetaApply<XRef<B>, A>;
  53 } // namespace detail
  54 /// \endcond
  55
  56 template <class I>
  57 struct Poly;
  58
  59 template <class T, class I>
  60 detail::AddCvrefOf<T, I>& poly_cast(detail::PolyRoot<I>&);
  61
  62 template <class T, class I>
  63 detail::AddCvrefOf<T, I> const& poly_cast(detail::PolyRoot<I> const&);
  64
  65 #if !defined(__cpp_template_auto)
  66 #define FOLLY_AUTO class
  67 template <class... Ts>
  68 using PolyMembers = detail::TypeList<Ts...>;
  69 #else
  70 #define FOLLY_AUTO auto
  71 template <auto...>
  72 struct PolyMembers;
  73 #endif
  74
  75 /// \cond
  76 namespace detail {
  77 /* *****************************************************************************
  78  * IMPLEMENTATION NOTES
  79  *
  80
  81 Building the Interface
  82 ----------------------
  83
  84 Here is a high-level description of how Poly works. Users write an interface
  85 such as:
  86
  87   struct Mine {
  88     template <class Base>
  89     struct Interface {
  90       int Exec() const {
  91         return folly::poly_call<0>(*this);
  92       }
  93     }
  94     template <class T>
  95     using Members = folly::PolyMembers<&T::Exec>;
  96   };
  97
  98 Then they instantiate Poly<Mine>, which will have an Exec member function
  99 of the correct signature. The Exec member function comes from
 100 Mine::Interface<PolyNode<Mine, PolyRoot<Mine>>>, from which Poly<Mine> inherits.
 101 Here's what each piece means:
 102
 103 - PolyRoot<I>: stores Data, which is a union of a void* (used when the Poly is
 104   storing an object on the heap or a reference) and some aligned storage (used
 105   when the Poly is storing an object in-situ). PolyRoot also stores a vtable
 106   pointer for interface I, which is a pointer to a struct containing function
 107   pointers. The function pointers are bound member functions (e.g.,
 108   SomeType::Exec). More on the vtable pointer and how it is generated below.
 109
 110 - PolyNode: provides the hooks used by folly::poly_call to dispatch to the
 111 correctly bound member function for this interface. In the context of an
 112 interface I, folly::poly_call<K>(*this, args...) will:
 113     1. Fetch the vtable pointer from PolyRoot,
 114     2. Select the I portion of that vtable (which, in the case of interface
 115        extension, may only be a part of the total vtable),
 116     3. Fetch the K-th function pointer from that vtable part,
 117     4. Call through that function pointer, passing Data (from PolyRoot) and any
 118        additional arguments in the folly::poly_call<K> invocation.
 119
 120 In the case of interface extension -- for instance, if interface Mine extended
 121 interface Yours by inheriting from PolyExtends<Yours> -- then interface Mine
 122 will have a list of base interfaces in a typelist called "Subsumptions".
 123 Poly<Mine> will fold all the subsumed interfaces together, linearly inheriting
 124 from them. To take the example of an interface Mine that extends Yours,
 125 Poly<Mine> would inherit from this type:
 126
 127   Mine::Interface<
 128     PolyNode<Mine,
 129       Your::Interface<
 130         PolyNode<Your, PolyRoot<Mine>>>>>
 131
 132 Through linear inheritance, Poly<Mine> ends up with the public member functions
 133 of both interfaces, Mine and Yours.
 134
 135 VTables
 136 -------
 137
 138 As mentioned above, PolyRoot<I> stores a vtable pointer for interface I. The
 139 vtable is a struct whose members are function pointers. How are the types of
 140 those function pointers computed from the interface? A dummy type is created,
 141 Archetype<I>, in much the same way that Poly<I>'s base type is computed. Instead
 142 of PolyNode and PolyRoot, there is ArchetypeNode and ArchetypeRoot. These types
 143 also provide hooks for folly::poly_call, but they are dummy hooks that do
 144 nothing. (Actually, they call std::terminate; they will never be called.) Once
 145 Archetype<I> has been constructed, it is a concrete type that has all the
 146 member functions of the interface and its subsumed interfaces. That type is
 147 passed to Mine::Members, which takes the address of Archetype<I>::Exec and
 148 inspects the resulting member function type. This is done for each member in the
 149 interface. From a list of [member] function pointers, it is a simple matter of
 150 metaprogramming to build a struct of function pointers. std::tuple is used for
 151 this.
 152
 153 An extra field is added to the tuple for a function that handles all of the
 154 "special" operations: destruction, copying, moving, getting the type
 155 information, getting the address of the stored object, and fetching a fixed-up
 156 vtable pointer for reference conversions (e.g., I -> I&, I& -> I const&, etc).
 157
 158 Subsumed interfaces are handled by having VTable<IDerived> inherit from
 159 BasePtr<IBase>, where BasePtr<IBase> has only one member of type
 160 VTable<IBase> const*.
 161
 162 Now that the type of VTable<I> is computed, how are the fields populated?
 163 Poly<I> default-constructs to an empty state. Its vtable pointer points to a
 164 vtable whose fields are initialized with the addresses of functions that do
 165 nothing but throw a BadPolyAccess exception. That way, if you call a member
 166 function on an empty Poly, you get an exception. The function pointer
 167 corresponding to the "special" operations points to a no-op function; copying,
 168 moving and destroying an empty Poly does nothing.
 169
 170 On the other hand, when you pass an object of type T satisfying interface I to
 171 Poly<I>'s constructor or assignment operator, a vtable for {I,T} is reified by
 172 passing type T to I::Members, thereby creating a list of bindings for T's member
 173 functions. The address of this vtable gets stored in the PolyRoot<I> subobject,
 174 imbuing the Poly object with the behaviors of type T. The T object itself gets
 175 stored either on the heap or in the aligned storage within the Poly object
 176 itself, depending on the size of T and whether or not it has a noexcept move
 177 constructor.
 178 */
 179
 180 template <class T>
 181 using Uncvref = std::remove_cv_t<std::remove_reference_t<T>>;
 182
 183 template <class T, template <class...> class U>
 184 struct IsInstanceOf : std::false_type {};
 185
 186 template <class... Ts, template <class...> class U>
 187 struct IsInstanceOf<U<Ts...>, U> : std::true_type {};
 188
 189 template <class T>
 190 using Not = Bool<!T::value>;
 191
 192 template <class T>
 193 struct StaticConst {
 194   static constexpr T value{};
 195 };
 196
 197 template <class T>
 198 constexpr T StaticConst<T>::value;
 199
 200 template <class Then>
 201 decltype(auto) if_constexpr(std::true_type, Then then) {
 202   return then(Identity{});
 203 }
 204
 205 template <class Then>
 206 void if_constexpr(std::false_type, Then) {}
 207
 208 template <class Then, class Else>
 209 decltype(auto) if_constexpr(std::true_type, Then then, Else) {
 210   return then(Identity{});
 211 }
 212
 213 template <class Then, class Else>
 214 decltype(auto) if_constexpr(std::false_type, Then, Else else_) {
 215   return else_(Identity{});
 216 }
 217
 218 enum class Op : short { eNuke, eMove, eCopy, eType, eAddr, eRefr };
 219
 220 enum class RefType : std::uintptr_t { eRvalue, eLvalue, eConstLvalue };
 221
 222 struct Data;
 223
 224 template <class I>
 225 struct PolyVal;
 226
 227 template <class I>
 228 struct PolyRef;
 229
 230 struct PolyAccess;
 231
 232 template <class T>
 233 using IsPoly = IsInstanceOf<Uncvref<T>, Poly>;
 234
 235 // Given an interface I and a concrete type T that satisfies the interface
 236 // I, create a list of member function bindings from members of T to members
 237 // of I.
 238 template <class I, class T>
 239 using MembersOf = typename I::template Members<Uncvref<T>>;
 240
 241 // Given an interface I and a base type T, create a type that implements
 242 // the interface I in terms of the capabilities of T.
 243 template <class I, class T>
 244 using InterfaceOf = typename I::template Interface<T>;
 245
 246 [[noreturn]] void throwBadPolyAccess();
 247 [[noreturn]] void throwBadPolyCast();
 248
 249 #if !defined(__cpp_template_auto)
 250 template <class T, T V>
 251 using Member = std::integral_constant<T, V>;
 252
 253 template <class M>
 254 using MemberType = typename M::value_type;
 255
 256 template <class M>
 257 inline constexpr MemberType<M> memberValue() noexcept {
 258   return M::value;
 259 }
 260
 261 template <class... Ts>
 262 struct MakeMembers {
 263   template <Ts... Vs>
 264   using Members = PolyMembers<Member<Ts, Vs>...>;
 265 };
 266
 267 template <class... Ts>
 268 MakeMembers<Ts...> deduceMembers(Ts...);
 269
 270 template <class Member, class = MemberType<Member>>
 271 struct MemberDef;
 272
 273 template <class Member, class R, class D, class... As>
 274 struct MemberDef<Member, R (D::*)(As...)> {
 275   static R value(D& d, As... as) {
 276     return folly::invoke(memberValue<Member>(), d, static_cast<As&&>(as)...);
 277   }
 278 };
 279
 280 template <class Member, class R, class D, class... As>
 281 struct MemberDef<Member, R (D::*)(As...) const> {
 282   static R value(D const& d, As... as) {
 283     return folly::invoke(memberValue<Member>(), d, static_cast<As&&>(as)...);
 284   }
 285 };
 286
 287 #else
 288 template <auto M>
 289 using MemberType = decltype(M);
 290
 291 template <auto M>
 292 inline constexpr MemberType<M> memberValue() noexcept {
 293   return M;
 294 }
 295 #endif
 296
 297 struct PolyBase {};
 298
 299 template <class I, class = void>
 300 struct SubsumptionsOf_ {
 301   using type = TypeList<>;
 302 };
 303
 304 template <class I>
 305 using InclusiveSubsumptionsOf = TypePushFront<_t<SubsumptionsOf_<I>>, I>;
 306
 307 template <class I>
 308 struct SubsumptionsOf_<I, void_t<typename I::Subsumptions>> {
 309   using type = TypeJoin<TypeTransform<
 310       typename I::Subsumptions,
 311       MetaQuote<InclusiveSubsumptionsOf>>>;
 312 };
 313
 314 template <class I>
 315 using SubsumptionsOf = TypeReverseUnique<_t<SubsumptionsOf_<I>>>;
 316
 317 struct Bottom {
 318   template <class T>
 319   [[noreturn]] /* implicit */ operator T &&() const {
 320     std::terminate();
 321   }
 322 };
 323
 324 using ArchetypeNode = MetaQuote<InterfaceOf>;
 325
 326 template <class I>
 327 struct ArchetypeRoot;
 328
 329 template <class I>
 330 using Archetype =
 331     TypeFold<InclusiveSubsumptionsOf<I>, ArchetypeRoot<I>, ArchetypeNode>;
 332
 333 struct ArchetypeBase : Bottom {
 334   ArchetypeBase() = default;
 335   template <class T>
 336   /* implicit */ ArchetypeBase(T&&);
 337   template <std::size_t, class... As>
 338   [[noreturn]] Bottom _polyCall_(As&&...) const { std::terminate(); }
 339
 340   friend bool operator==(ArchetypeBase const&, ArchetypeBase const&);
 341   friend bool operator!=(ArchetypeBase const&, ArchetypeBase const&);
 342   friend bool operator<(ArchetypeBase const&, ArchetypeBase const&);
 343   friend bool operator<=(ArchetypeBase const&, ArchetypeBase const&);
 344   friend bool operator>(ArchetypeBase const&, ArchetypeBase const&);
 345   friend bool operator>=(ArchetypeBase const&, ArchetypeBase const&);
 346   friend Bottom operator++(ArchetypeBase const&);
 347   friend Bottom operator++(ArchetypeBase const&, int);
 348   friend Bottom operator--(ArchetypeBase const&);
 349   friend Bottom operator--(ArchetypeBase const&, int);
 350   friend Bottom operator+(ArchetypeBase const&, ArchetypeBase const&);
 351   friend Bottom operator+=(ArchetypeBase const&, ArchetypeBase const&);
 352   friend Bottom operator-(ArchetypeBase const&, ArchetypeBase const&);
 353   friend Bottom operator-=(ArchetypeBase const&, ArchetypeBase const&);
 354   friend Bottom operator*(ArchetypeBase const&, ArchetypeBase const&);
 355   friend Bottom operator*=(ArchetypeBase const&, ArchetypeBase const&);
 356   friend Bottom operator/(ArchetypeBase const&, ArchetypeBase const&);
 357   friend Bottom operator/=(ArchetypeBase const&, ArchetypeBase const&);
 358   friend Bottom operator%(ArchetypeBase const&, ArchetypeBase const&);
 359   friend Bottom operator%=(ArchetypeBase const&, ArchetypeBase const&);
 360   friend Bottom operator<<(ArchetypeBase const&, ArchetypeBase const&);
 361   friend Bottom operator<<=(ArchetypeBase const&, ArchetypeBase const&);
 362   friend Bottom operator>>(ArchetypeBase const&, ArchetypeBase const&);
 363   friend Bottom operator>>=(ArchetypeBase const&, ArchetypeBase const&);
 364 };
 365
 366 template <class I>
 367 struct ArchetypeRoot : ArchetypeBase {
 368   template <class Node, class Tfx>
 369   using _polySelf_ = Archetype<AddCvrefOf<MetaApply<Tfx, I>, Node>>;
 370   using _polyInterface_ = I;
 371 };
 372
 373 struct Data {
 374   Data() = default;
 375   // Suppress compiler-generated copy ops to not copy anything:
 376   Data(Data const&) {}
 377   Data& operator=(Data const&) {
 378     return *this;
 379   }
 380   union {
 381     void* pobj_ = nullptr;
 382     std::aligned_storage_t<sizeof(double[2])> buff_;
 383   };
 384 };
 385
 386 template <class U, class I>
 387 using Arg =
 388     If<std::is_same<Uncvref<U>, Archetype<I>>::value,
 389        Poly<AddCvrefOf<I, U const&>>,
 390        U>;
 391
 392 template <class U, class I>
 393 using Ret =
 394     If<std::is_same<Uncvref<U>, Archetype<I>>::value,
 395        AddCvrefOf<Poly<I>, U>,
 396        U>;
 397
 398 template <class Member, class I>
 399 struct SignatureOf_;
 400
 401 template <class R, class C, class... As, class I>
 402 struct SignatureOf_<R (C::*)(As...), I> {
 403   using type = Ret<R, I> (*)(Data&, Arg<As, I>...);
 404 };
 405
 406 template <class R, class C, class... As, class I>
 407 struct SignatureOf_<R (C::*)(As...) const, I> {
 408   using type = Ret<R, I> (*)(Data const&, Arg<As, I>...);
 409 };
 410
 411 template <class R, class This, class... As, class I>
 412 struct SignatureOf_<R (*)(This&, As...), I> {
 413   using type = Ret<R, I> (*)(Data&, Arg<As, I>...);
 414 };
 415
 416 template <class R, class This, class... As, class I>
 417 struct SignatureOf_<R (*)(This const&, As...), I> {
 418   using type = Ret<R, I> (*)(Data const&, Arg<As, I>...);
 419 };
 420
 421 template <FOLLY_AUTO Arch, class I>
 422 using SignatureOf = _t<SignatureOf_<MemberType<Arch>, I>>;
 423
 424 template <FOLLY_AUTO User, class I, class Sig = SignatureOf<User, I>>
 425 struct ArgTypes_;
 426
 427 template <FOLLY_AUTO User, class I, class Ret, class Data, class... Args>
 428 struct ArgTypes_<User, I, Ret (*)(Data, Args...)> {
 429   using type = TypeList<Args...>;
 430 };
 431
 432 template <FOLLY_AUTO User, class I>
 433 using ArgTypes = _t<ArgTypes_<User, I>>;
 434
 435 template <class R, class... Args>
 436 using FnPtr = R (*)(Args...);
 437
 438 struct ThrowThunk {
 439   template <class R, class... Args>
 440   constexpr /* implicit */ operator FnPtr<R, Args...>() const noexcept {
 441     struct _ {
 442       static R call(Args...) {
 443         throwBadPolyAccess();
 444       }
 445     };
 446     return &_::call;
 447   }
 448 };
 449
 450 inline constexpr ThrowThunk throw_() noexcept {
 451   return ThrowThunk{};
 452 }
 453
 454 template <class T>
 455 inline constexpr bool inSitu() noexcept {
 456   return !std::is_reference<T>::value &&
 457       sizeof(std::decay_t<T>) <= sizeof(Data) &&
 458       std::is_nothrow_move_constructible<std::decay_t<T>>::value;
 459 }
 460
 461 template <class T>
 462 T& get(Data& d) noexcept {
 463   if (inSitu<T>()) {
 464     return *(std::add_pointer_t<T>)static_cast<void*>(&d.buff_);
 465   } else {
 466     return *static_cast<std::add_pointer_t<T>>(d.pobj_);
 467   }
 468 }
 469
 470 template <class T>
 471 T const& get(Data const& d) noexcept {
 472   if (inSitu<T>()) {
 473     return *(std::add_pointer_t<T const>)static_cast<void const*>(&d.buff_);
 474   } else {
 475     return *static_cast<std::add_pointer_t<T const>>(d.pobj_);
 476   }
 477 }
 478
 479 enum class State : short { eEmpty, eInSitu, eOnHeap };
 480
 481 template <class T>
 482 struct IsPolyRef : std::false_type {};
 483
 484 template <class T>
 485 struct IsPolyRef<Poly<T&>> : std::true_type {};
 486
 487 template <class Arg, class U>
 488 decltype(auto) convert(U&& u) {
 489   return detail::if_constexpr(
 490       StrictConjunction<
 491           IsPolyRef<Uncvref<U>>,
 492           Negation<std::is_convertible<U, Arg>>>(),
 493       [&](auto id) -> decltype(auto) {
 494         return poly_cast<Uncvref<Arg>>(id(u).get());
 495       },
 496       [&](auto id) -> U&& { return static_cast<U&&>(id(u)); });
 497 }
 498
 499 template <class Fun>
 500 struct IsConstMember : std::false_type {};
 501
 502 template <class R, class C, class... As>
 503 struct IsConstMember<R (C::*)(As...) const> : std::true_type {};
 504
 505 template <class R, class C, class... As>
 506 struct IsConstMember<R (*)(C const&, As...)> : std::true_type {};
 507
 508 template <
 509     class T,
 510     FOLLY_AUTO User,
 511     class I,
 512     class = ArgTypes<User, I>,
 513     class = Bool<true>>
 514 struct ThunkFn {
 515   template <class R, class D, class... As>
 516   constexpr /* implicit */ operator FnPtr<R, D&, As...>() const noexcept {
 517     return nullptr;
 518   }
 519 };
 520
 521 template <class T, FOLLY_AUTO User, class I, class... Args>
 522 struct ThunkFn<
 523     T,
 524     User,
 525     I,
 526     TypeList<Args...>,
 527     Bool<
 528         !std::is_const<std::remove_reference_t<T>>::value ||
 529         IsConstMember<MemberType<User>>::value>> {
 530   template <class R, class D, class... As>
 531   constexpr /* implicit */ operator FnPtr<R, D&, As...>() const noexcept {
 532     struct _ {
 533       static R call(D& d, As... as) {
 534         return folly::invoke(
 535             memberValue<User>(),
 536             get<T>(d),
 537             convert<Args>(static_cast<As&&>(as))...);
 538       }
 539     };
 540     return &_::call;
 541   }
 542 };
 543
 544 template <
 545     class I,
 546     class = MembersOf<I, Archetype<I>>,
 547     class = SubsumptionsOf<I>>
 548 struct VTable;
 549
 550 template <class T, FOLLY_AUTO User, class I>
 551 inline constexpr ThunkFn<T, User, I> thunk() noexcept {
 552   return ThunkFn<T, User, I>{};
 553 }
 554
 555 template <class I>
 556 constexpr VTable<I> const* vtable() noexcept {
 557   return &StaticConst<VTable<I>>::value;
 558 }
 559
 560 template <class I, class T>
 561 struct VTableFor : VTable<I> {
 562   constexpr VTableFor() noexcept : VTable<I>{Type<T>{}} {}
 563 };
 564
 565 template <class I, class T>
 566 constexpr VTable<I> const* vtableFor() noexcept {
 567   return &StaticConst<VTableFor<I, T>>::value;
 568 }
 569
 570 template <class I, class T>
 571 constexpr void* vtableForRef(RefType ref) {
 572   switch (ref) {
 573     case RefType::eRvalue:
 574       return const_cast<VTable<I>*>(vtableFor<I, T&&>());
 575     case RefType::eLvalue:
 576       return const_cast<VTable<I>*>(vtableFor<I, T&>());
 577     case RefType::eConstLvalue:
 578       return const_cast<VTable<I>*>(vtableFor<I, T const&>());
 579   }
 580   return nullptr;
 581 }
 582
 583 template <
 584     class I,
 585     class T,
 586     std::enable_if_t<std::is_reference<T>::value, int> = 0>
 587 void* execOnHeap(Op op, Data* from, void* to) {
 588   switch (op) {
 589     case Op::eNuke:
 590       break;
 591     case Op::eMove:
 592     case Op::eCopy:
 593       static_cast<Data*>(to)->pobj_ = from->pobj_;
 594       break;
 595     case Op::eType:
 596       return const_cast<void*>(static_cast<void const*>(&typeid(T)));
 597     case Op::eAddr:
 598       if (*static_cast<std::type_info const*>(to) == typeid(T)) {
 599         return from->pobj_;
 600       }
 601       throwBadPolyCast();
 602     case Op::eRefr:
 603       return vtableForRef<I, Uncvref<T>>(
 604           static_cast<RefType>(reinterpret_cast<std::uintptr_t>(to)));
 605   }
 606   return nullptr;
 607 }
 608
 609 template <
 610     class I,
 611     class T,
 612     std::enable_if_t<Not<std::is_reference<T>>::value, int> = 0>
 613 void* execOnHeap(Op op, Data* from, void* to) {
 614   switch (op) {
 615     case Op::eNuke:
 616       delete &get<T>(*from);
 617       break;
 618     case Op::eMove:
 619       static_cast<Data*>(to)->pobj_ = std::exchange(from->pobj_, nullptr);
 620       break;
 621     case Op::eCopy:
 622       detail::if_constexpr(std::is_copy_constructible<T>(), [&](auto id) {
 623         static_cast<Data*>(to)->pobj_ = new T(id(get<T>(*from)));
 624       });
 625       break;
 626     case Op::eType:
 627       return const_cast<void*>(static_cast<void const*>(&typeid(T)));
 628     case Op::eAddr:
 629       if (*static_cast<std::type_info const*>(to) == typeid(T)) {
 630         return from->pobj_;
 631       }
 632       throwBadPolyCast();
 633     case Op::eRefr:
 634       return vtableForRef<I, Uncvref<T>>(
 635           static_cast<RefType>(reinterpret_cast<std::uintptr_t>(to)));
 636   }
 637   return nullptr;
 638 }
 639
 640 template <class I, class T>
 641 void* execInSitu(Op op, Data* from, void* to) {
 642   switch (op) {
 643     case Op::eNuke:
 644       get<T>(*from).~T();
 645       break;
 646     case Op::eMove:
 647       ::new (static_cast<void*>(&static_cast<Data*>(to)->buff_))
 648           T(std::move(get<T>(*from)));
 649       get<T>(*from).~T();
 650       break;
 651     case Op::eCopy:
 652       detail::if_constexpr(std::is_copy_constructible<T>(), [&](auto id) {
 653         ::new (static_cast<void*>(&static_cast<Data*>(to)->buff_))
 654             T(id(get<T>(*from)));
 655       });
 656       break;
 657     case Op::eType:
 658       return const_cast<void*>(static_cast<void const*>(&typeid(T)));
 659     case Op::eAddr:
 660       if (*static_cast<std::type_info const*>(to) == typeid(T)) {
 661         return &from->buff_;
 662       }
 663       throwBadPolyCast();
 664     case Op::eRefr:
 665       return vtableForRef<I, Uncvref<T>>(
 666           static_cast<RefType>(reinterpret_cast<std::uintptr_t>(to)));
 667   }
 668   return nullptr;
 669 }
 670
 671 inline void* noopExec(Op op, Data*, void*) {
 672   if (op == Op::eAddr)
 673     throwBadPolyAccess();
 674   return const_cast<void*>(static_cast<void const*>(&typeid(void)));
 675 }
 676
 677 template <class I>
 678 struct BasePtr {
 679   VTable<I> const* vptr_;
 680 };
 681
 682 template <class I, class T, std::enable_if_t<inSitu<T>(), int> = 0>
 683 constexpr void* (*getOps() noexcept)(Op, Data*, void*) {
 684   return &execInSitu<I, T>;
 685 }
 686
 687 template <class I, class T, std::enable_if_t<!inSitu<T>(), int> = 0>
 688 constexpr void* (*getOps() noexcept)(Op, Data*, void*) {
 689   return &execOnHeap<I, T>;
 690 }
 691
 692 template <class I, FOLLY_AUTO... Arch, class... S>
 693 struct VTable<I, PolyMembers<Arch...>, TypeList<S...>>
 694     : BasePtr<S>..., std::tuple<SignatureOf<Arch, I>...> {
 695  private:
 696   template <class T, FOLLY_AUTO... User>
 697   constexpr VTable(Type<T>, PolyMembers<User...>) noexcept
 698       : BasePtr<S>{vtableFor<S, T>()}...,
 699         std::tuple<SignatureOf<Arch, I>...>{thunk<T, User, I>()...},
 700         state_{inSitu<T>() ? State::eInSitu : State::eOnHeap},
 701         ops_{getOps<I, T>()} {}
 702
 703  public:
 704   constexpr VTable() noexcept
 705       : BasePtr<S>{vtable<S>()}...,
 706         std::tuple<SignatureOf<Arch, I>...>{
 707             static_cast<SignatureOf<Arch, I>>(throw_())...},
 708         state_{State::eEmpty},
 709         ops_{&noopExec} {}
 710
 711   template <class T>
 712   explicit constexpr VTable(Type<T>) noexcept
 713       : VTable{Type<T>{}, MembersOf<I, T>{}} {}
 714
 715   State state_;
 716   void* (*ops_)(Op, Data*, void*);
 717 };
 718
 719 template <class I>
 720 constexpr VTable<I> const& select(VTable<_t<Type<I>>> const& vtbl) noexcept {
 721   return vtbl;
 722 }
 723
 724 template <class I>
 725 constexpr VTable<I> const& select(BasePtr<_t<Type<I>>> const& base) noexcept {
 726   return *base.vptr_;
 727 }
 728
 729 struct PolyAccess {
 730   template <std::size_t N, typename This, typename... As>
 731   static auto call(This&& _this, As&&... args)
 732       -> decltype(static_cast<This&&>(_this).template _polyCall_<N>(
 733           static_cast<As&&>(args)...)) {
 734     static_assert(
 735         !IsInstanceOf<std::decay_t<This>, Poly>::value,
 736         "When passing a Poly<> object to call(), you must explicitly "
 737         "say which Interface to dispatch to, as in "
 738         "call<0, MyInterface>(self, args...)");
 739     return static_cast<This&&>(_this).template _polyCall_<N>(
 740         static_cast<As&&>(args)...);
 741   }
 742
 743   template <class Poly>
 744   using Iface = typename Uncvref<Poly>::_polyInterface_;
 745
 746   template <class Node, class Tfx = MetaIdentity>
 747   static typename Uncvref<Node>::template _polySelf_<Node, Tfx> self_();
 748
 749   template <class T, class Poly, class I = Iface<Poly>>
 750   static decltype(auto) cast(Poly&& _this) {
 751     using Ret = AddCvrefOf<AddCvrefOf<T, I>, Poly&&>;
 752     return static_cast<Ret>(
 753         *static_cast<std::add_pointer_t<Ret>>(_this.vptr_->ops_(
 754             Op::eAddr,
 755             const_cast<Data*>(static_cast<Data const*>(&_this)),
 756             const_cast<void*>(static_cast<void const*>(&typeid(T))))));
 757   }
 758
 759   template <class Poly>
 760   static decltype(auto) root(Poly&& _this) noexcept {
 761     return static_cast<Poly&&>(_this)._polyRoot_();
 762   }
 763
 764   template <class I>
 765   static std::type_info const& type(PolyRoot<I> const& _this) noexcept {
 766     return *static_cast<std::type_info const*>(
 767         _this.vptr_->ops_(Op::eType, nullptr, nullptr));
 768   }
 769
 770   template <class I>
 771   static VTable<Uncvref<I>> const* vtable(PolyRoot<I> const& _this) noexcept {
 772     return _this.vptr_;
 773   }
 774
 775   template <class I>
 776   static Data* data(PolyRoot<I>& _this) noexcept {
 777     return &_this;
 778   }
 779
 780   template <class I>
 781   static Data const* data(PolyRoot<I> const& _this) noexcept {
 782     return &_this;
 783   }
 784
 785   template <class I>
 786   static Poly<I&&> move(PolyRoot<I&> const& _this) noexcept {
 787     return Poly<I&&>{_this, Type<I&>{}};
 788   }
 789
 790   template <class I>
 791   static Poly<I const&> move(PolyRoot<I const&> const& _this) noexcept {
 792     return Poly<I const&>{_this, Type<I const&>{}};
 793   }
 794 };
 795
 796 template <class I, class Tail>
 797 struct PolyNode : Tail {
 798  private:
 799   friend PolyAccess;
 800   using Tail::Tail;
 801
 802   template <std::size_t K, typename... As>
 803   decltype(auto) _polyCall_(As&&... as) {
 804     return std::get<K>(select<I>(*PolyAccess::vtable(*this)))(
 805         *PolyAccess::data(*this), static_cast<As&&>(as)...);
 806   }
 807   template <std::size_t K, typename... As>
 808   decltype(auto) _polyCall_(As&&... as) const {
 809     return std::get<K>(select<I>(*PolyAccess::vtable(*this)))(
 810         *PolyAccess::data(*this), static_cast<As&&>(as)...);
 811   }
 812 };
 813
 814 struct MakePolyNode {
 815   template <class I, class State>
 816   using apply = InterfaceOf<I, PolyNode<I, State>>;
 817 };
 818
 819 template <class I>
 820 struct PolyRoot : private PolyBase, private Data {
 821   friend PolyAccess;
 822   friend Poly<I>;
 823   friend PolyVal<I>;
 824   friend PolyRef<I>;
 825   template <class Node, class Tfx>
 826   using _polySelf_ = Poly<AddCvrefOf<MetaApply<Tfx, I>, Node>>;
 827   using _polyInterface_ = I;
 828
 829  private:
 830   PolyRoot& _polyRoot_() noexcept {
 831     return *this;
 832   }
 833   PolyRoot const& _polyRoot_() const noexcept {
 834     return *this;
 835   }
 836   VTable<std::decay_t<I>> const* vptr_ = vtable<std::decay_t<I>>();
 837 };
 838
 839 template <class I>
 840 using PolyImpl =
 841     TypeFold<InclusiveSubsumptionsOf<Uncvref<I>>, PolyRoot<I>, MakePolyNode>;
 842
 843 // A const-qualified function type means the user is trying to disambiguate
 844 // a member function pointer.
 845 template <class Fun> // Fun = R(As...) const
 846 struct Sig {
 847   template <class T>
 848   constexpr Fun T::*operator()(Fun T::*t) const /* nolint */ volatile noexcept {
 849     return t;
 850   }
 851   template <class F, class T>
 852   constexpr F T::*operator()(F T::*t) const /* nolint */ volatile noexcept {
 853     return t;
 854   }
 855 };
 856
 857 // A functon type with no arguments means the user is trying to disambiguate
 858 // a member function pointer.
 859 template <class R>
 860 struct Sig<R()> : Sig<R() const> {
 861   using Fun = R();
 862   using Sig<R() const>::operator();
 863
 864   template <class T>
 865   constexpr Fun T::*operator()(Fun T::*t) const noexcept {
 866     return t;
 867   }
 868 };
 869
 870 template <class R, class... As>
 871 struct SigImpl : Sig<R(As...) const> {
 872   using Fun = R(As...);
 873   using Sig<R(As...) const>::operator();
 874
 875   template <class T>
 876   constexpr Fun T::*operator()(Fun T::*t) const noexcept {
 877     return t;
 878   }
 879   constexpr Fun* operator()(Fun* t) const noexcept {
 880     return t;
 881   }
 882   template <class F>
 883   constexpr F* operator()(F* t) const noexcept {
 884     return t;
 885   }
 886 };
 887
 888 // The user could be trying to disambiguate either a member or a free function.
 889 template <class R, class... As>
 890 struct Sig<R(As...)> : SigImpl<R, As...> {};
 891
 892 // This case is like the one above, except we want to add an overload that
 893 // handles the case of a free function where the first argument is more
 894 // const-qualified than the user explicitly specified.
 895 template <class R, class A, class... As>
 896 struct Sig<R(A&, As...)> : SigImpl<R, A&, As...> {
 897   using CCFun = R(A const&, As...);
 898   using SigImpl<R, A&, As...>::operator();
 899
 900   constexpr CCFun* operator()(CCFun* t) const /* nolint */ volatile noexcept {
 901     return t;
 902   }
 903 };
 904
 905 template <
 906     class T,
 907     class I,
 908     class U = std::decay_t<T>,
 909     std::enable_if_t<Not<std::is_base_of<PolyBase, U>>::value, int> = 0,
 910     std::enable_if_t<std::is_constructible<AddCvrefOf<U, I>, T>::value, int> =
 911         0,
 912     class = MembersOf<std::decay_t<I>, U>>
 913 std::true_type modelsInterface_(int);
 914 template <class T, class I>
 915 std::false_type modelsInterface_(long);
 916
 917 template <class T, class I>
 918 struct ModelsInterface : decltype(modelsInterface_<T, I>(0)) {};
 919
 920 template <class I1, class I2>
 921 struct ValueCompatible : std::is_base_of<I1, I2> {};
 922
 923 // This prevents PolyRef's converting constructors and assignment operators
 924 // from being considered as copy constructors and assignment operators:
 925 template <class I1>
 926 struct ValueCompatible<I1, I1> : std::false_type {};
 927
 928 template <class I1, class I2, class I2Ref>
 929 struct ReferenceCompatible : std::is_constructible<I1, I2Ref> {};
 930
 931 // This prevents PolyRef's converting constructors and assignment operators
 932 // from being considered as copy constructors and assignment operators:
 933 template <class I1, class I2Ref>
 934 struct ReferenceCompatible<I1, I1, I2Ref> : std::false_type {};
 935
 936 } // namespace detail
 937 /// \endcond
 938 } // namespace folly
 939
 940 #undef FOLLY_AUTO