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 Fun>
 201 void if_constexpr(std::true_type, Fun fun) {
 202   fun(Identity{});
 203 }
 204
 205 template <class Fun>
 206 void if_constexpr(std::false_type, Fun) {}
 207
 208 enum class Op : short { eNuke, eMove, eCopy, eType, eAddr, eRefr };
 209
 210 enum class RefType : std::uintptr_t { eRvalue, eLvalue, eConstLvalue };
 211
 212 struct Data;
 213
 214 template <class I>
 215 struct PolyVal;
 216
 217 template <class I>
 218 struct PolyRef;
 219
 220 struct PolyAccess;
 221
 222 template <class T>
 223 using IsPoly = IsInstanceOf<Uncvref<T>, Poly>;
 224
 225 // Given an interface I and a concrete type T that satisfies the interface
 226 // I, create a list of member function bindings from members of T to members
 227 // of I.
 228 template <class I, class T>
 229 using MembersOf = typename I::template Members<Uncvref<T>>;
 230
 231 // Given an interface I and a base type T, create a type that implements
 232 // the interface I in terms of the capabilities of T.
 233 template <class I, class T>
 234 using InterfaceOf = typename I::template Interface<T>;
 235
 236 [[noreturn]] void throwBadPolyAccess();
 237 [[noreturn]] void throwBadPolyCast();
 238
 239 #if !defined(__cpp_template_auto)
 240 template <class T, T V>
 241 using Member = std::integral_constant<T, V>;
 242
 243 template <class M>
 244 using MemberType = typename M::value_type;
 245
 246 template <class M>
 247 inline constexpr MemberType<M> memberValue() noexcept {
 248   return M::value;
 249 }
 250
 251 template <class... Ts>
 252 struct MakeMembers {
 253   template <Ts... Vs>
 254   using Members = PolyMembers<Member<Ts, Vs>...>;
 255 };
 256
 257 template <class... Ts>
 258 MakeMembers<Ts...> deduceMembers(Ts...);
 259
 260 template <class Member, class = MemberType<Member>>
 261 struct MemberDef;
 262
 263 template <class Member, class R, class D, class... As>
 264 struct MemberDef<Member, R (D::*)(As...)> {
 265   static R value(D& d, As... as) {
 266     return folly::invoke(memberValue<Member>(), d, static_cast<As&&>(as)...);
 267   }
 268 };
 269
 270 template <class Member, class R, class D, class... As>
 271 struct MemberDef<Member, R (D::*)(As...) const> {
 272   static R value(D const& d, As... as) {
 273     return folly::invoke(memberValue<Member>(), d, static_cast<As&&>(as)...);
 274   }
 275 };
 276
 277 #else
 278 template <auto M>
 279 using MemberType = decltype(M);
 280
 281 template <auto M>
 282 inline constexpr MemberType<M> memberValue() noexcept {
 283   return M;
 284 }
 285 #endif
 286
 287 struct PolyBase {};
 288
 289 template <class I, class = void>
 290 struct SubsumptionsOf_ {
 291   using type = TypeList<>;
 292 };
 293
 294 template <class I>
 295 using InclusiveSubsumptionsOf = TypePushFront<_t<SubsumptionsOf_<I>>, I>;
 296
 297 template <class I>
 298 struct SubsumptionsOf_<I, void_t<typename I::Subsumptions>> {
 299   using type = TypeJoin<TypeTransform<
 300       typename I::Subsumptions,
 301       MetaQuote<InclusiveSubsumptionsOf>>>;
 302 };
 303
 304 template <class I>
 305 using SubsumptionsOf = TypeReverseUnique<_t<SubsumptionsOf_<I>>>;
 306
 307 struct Bottom {
 308   template <class T>
 309   [[noreturn]] /* implicit */ operator T &&() const {
 310     std::terminate();
 311   }
 312 };
 313
 314 using ArchetypeNode = MetaQuote<InterfaceOf>;
 315
 316 template <class I>
 317 struct ArchetypeRoot;
 318
 319 template <class I>
 320 using Archetype =
 321     TypeFold<InclusiveSubsumptionsOf<I>, ArchetypeRoot<I>, ArchetypeNode>;
 322
 323 struct ArchetypeBase : Bottom {
 324   ArchetypeBase() = default;
 325   template <class T>
 326   /* implicit */ ArchetypeBase(T&&);
 327   template <std::size_t, class... As>
 328   [[noreturn]] Bottom _polyCall_(As&&...) const { std::terminate(); }
 329
 330   friend bool operator==(ArchetypeBase const&, ArchetypeBase const&);
 331   friend bool operator!=(ArchetypeBase const&, ArchetypeBase const&);
 332   friend bool operator<(ArchetypeBase const&, ArchetypeBase const&);
 333   friend bool operator<=(ArchetypeBase const&, ArchetypeBase const&);
 334   friend bool operator>(ArchetypeBase const&, ArchetypeBase const&);
 335   friend bool operator>=(ArchetypeBase const&, ArchetypeBase const&);
 336   friend Bottom operator++(ArchetypeBase const&);
 337   friend Bottom operator++(ArchetypeBase const&, int);
 338   friend Bottom operator--(ArchetypeBase const&);
 339   friend Bottom operator--(ArchetypeBase const&, int);
 340   friend Bottom operator+(ArchetypeBase const&, ArchetypeBase const&);
 341   friend Bottom operator+=(ArchetypeBase const&, ArchetypeBase const&);
 342   friend Bottom operator-(ArchetypeBase const&, ArchetypeBase const&);
 343   friend Bottom operator-=(ArchetypeBase const&, ArchetypeBase const&);
 344   friend Bottom operator*(ArchetypeBase const&, ArchetypeBase const&);
 345   friend Bottom operator*=(ArchetypeBase const&, ArchetypeBase const&);
 346   friend Bottom operator/(ArchetypeBase const&, ArchetypeBase const&);
 347   friend Bottom operator/=(ArchetypeBase const&, ArchetypeBase const&);
 348   friend Bottom operator%(ArchetypeBase const&, ArchetypeBase const&);
 349   friend Bottom operator%=(ArchetypeBase const&, ArchetypeBase const&);
 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 };
 355
 356 template <class I>
 357 struct ArchetypeRoot : ArchetypeBase {
 358   template <class Node, class Tfx>
 359   using _polySelf_ = Archetype<AddCvrefOf<MetaApply<Tfx, I>, Node>>;
 360   using _polyInterface_ = I;
 361 };
 362
 363 struct Data {
 364   Data() = default;
 365   // Suppress compiler-generated copy ops to not copy anything:
 366   Data(Data const&) {}
 367   Data& operator=(Data const&) {
 368     return *this;
 369   }
 370   union {
 371     void* pobj_ = nullptr;
 372     std::aligned_storage_t<sizeof(double[2])> buff_;
 373   };
 374 };
 375
 376 template <class U, class I>
 377 using Arg =
 378     If<std::is_same<Uncvref<U>, Archetype<I>>::value,
 379        Poly<AddCvrefOf<I, U const&>>,
 380        U>;
 381
 382 template <class U, class I>
 383 using Ret =
 384     If<std::is_same<Uncvref<U>, Archetype<I>>::value,
 385        AddCvrefOf<Poly<I>, U>,
 386        U>;
 387
 388 template <class Member, class I>
 389 struct SignatureOf_;
 390
 391 template <class R, class C, class... As, class I>
 392 struct SignatureOf_<R (C::*)(As...), I> {
 393   using type = Ret<R, I> (*)(Data&, Arg<As, I>...);
 394 };
 395
 396 template <class R, class C, class... As, class I>
 397 struct SignatureOf_<R (C::*)(As...) const, I> {
 398   using type = Ret<R, I> (*)(Data const&, Arg<As, I>...);
 399 };
 400
 401 template <class R, class This, class... As, class I>
 402 struct SignatureOf_<R (*)(This&, As...), I> {
 403   using type = Ret<R, I> (*)(Data&, Arg<As, I>...);
 404 };
 405
 406 template <class R, class This, class... As, class I>
 407 struct SignatureOf_<R (*)(This const&, As...), I> {
 408   using type = Ret<R, I> (*)(Data const&, Arg<As, I>...);
 409 };
 410
 411 template <FOLLY_AUTO Arch, class I>
 412 using SignatureOf = _t<SignatureOf_<MemberType<Arch>, I>>;
 413
 414 template <FOLLY_AUTO User, class I, class Sig = SignatureOf<User, I>>
 415 struct ArgTypes_;
 416
 417 template <FOLLY_AUTO User, class I, class Ret, class Data, class... Args>
 418 struct ArgTypes_<User, I, Ret (*)(Data, Args...)> {
 419   using type = TypeList<Args...>;
 420 };
 421
 422 template <FOLLY_AUTO User, class I>
 423 using ArgTypes = _t<ArgTypes_<User, I>>;
 424
 425 template <class R, class... Args>
 426 using FnPtr = R (*)(Args...);
 427
 428 struct ThrowThunk {
 429   template <class R, class... Args>
 430   constexpr /* implicit */ operator FnPtr<R, Args...>() const noexcept {
 431     struct _ {
 432       static R call(Args...) {
 433         throwBadPolyAccess();
 434       }
 435     };
 436     return &_::call;
 437   }
 438 };
 439
 440 inline constexpr ThrowThunk throw_() noexcept {
 441   return ThrowThunk{};
 442 }
 443
 444 template <class T>
 445 inline constexpr bool inSitu() noexcept {
 446   return !std::is_reference<T>::value &&
 447       sizeof(std::decay_t<T>) <= sizeof(Data) &&
 448       std::is_nothrow_move_constructible<std::decay_t<T>>::value;
 449 }
 450
 451 template <class T>
 452 T& get(Data& d) noexcept {
 453   if (inSitu<T>()) {
 454     return *(std::add_pointer_t<T>)static_cast<void*>(&d.buff_);
 455   } else {
 456     return *static_cast<std::add_pointer_t<T>>(d.pobj_);
 457   }
 458 }
 459
 460 template <class T>
 461 T const& get(Data const& d) noexcept {
 462   if (inSitu<T>()) {
 463     return *(std::add_pointer_t<T const>)static_cast<void const*>(&d.buff_);
 464   } else {
 465     return *static_cast<std::add_pointer_t<T const>>(d.pobj_);
 466   }
 467 }
 468
 469 enum class State : short { eEmpty, eInSitu, eOnHeap };
 470
 471 template <class, class U>
 472 U&& convert(U&& u) noexcept {
 473   return static_cast<U&&>(u);
 474 }
 475
 476 template <class Arg, class I>
 477 decltype(auto) convert(Poly<I&> u) {
 478   return poly_cast<Uncvref<Arg>>(u.get());
 479 }
 480
 481 template <class Fun>
 482 struct IsConstMember : std::false_type {};
 483
 484 template <class R, class C, class... As>
 485 struct IsConstMember<R (C::*)(As...) const> : std::true_type {};
 486
 487 template <class R, class C, class... As>
 488 struct IsConstMember<R (*)(C const&, As...)> : std::true_type {};
 489
 490 template <
 491     class T,
 492     FOLLY_AUTO User,
 493     class I,
 494     class = ArgTypes<User, I>,
 495     class = Bool<true>>
 496 struct ThunkFn {
 497   template <class R, class D, class... As>
 498   constexpr /* implicit */ operator FnPtr<R, D&, As...>() const noexcept {
 499     return nullptr;
 500   }
 501 };
 502
 503 template <class T, FOLLY_AUTO User, class I, class... Args>
 504 struct ThunkFn<
 505     T,
 506     User,
 507     I,
 508     TypeList<Args...>,
 509     Bool<
 510         !std::is_const<std::remove_reference_t<T>>::value ||
 511         IsConstMember<MemberType<User>>::value>> {
 512   template <class R, class D, class... As>
 513   constexpr /* implicit */ operator FnPtr<R, D&, As...>() const noexcept {
 514     struct _ {
 515       static R call(D& d, As... as) {
 516         return folly::invoke(
 517             memberValue<User>(),
 518             get<T>(d),
 519             convert<Args>(static_cast<As&&>(as))...);
 520       }
 521     };
 522     return &_::call;
 523   }
 524 };
 525
 526 template <
 527     class I,
 528     class = MembersOf<I, Archetype<I>>,
 529     class = SubsumptionsOf<I>>
 530 struct VTable;
 531
 532 template <class T, FOLLY_AUTO User, class I>
 533 inline constexpr ThunkFn<T, User, I> thunk() noexcept {
 534   return ThunkFn<T, User, I>{};
 535 }
 536
 537 template <class I>
 538 constexpr VTable<I> const* vtable() noexcept {
 539   return &StaticConst<VTable<I>>::value;
 540 }
 541
 542 template <class I, class T>
 543 struct VTableFor : VTable<I> {
 544   constexpr VTableFor() noexcept : VTable<I>{Type<T>{}} {}
 545 };
 546
 547 template <class I, class T>
 548 constexpr VTable<I> const* vtableFor() noexcept {
 549   return &StaticConst<VTableFor<I, T>>::value;
 550 }
 551
 552 template <class I, class T>
 553 constexpr void* vtableForRef(RefType ref) {
 554   switch (ref) {
 555     case RefType::eRvalue:
 556       return const_cast<VTable<I>*>(vtableFor<I, T&&>());
 557     case RefType::eLvalue:
 558       return const_cast<VTable<I>*>(vtableFor<I, T&>());
 559     case RefType::eConstLvalue:
 560       return const_cast<VTable<I>*>(vtableFor<I, T const&>());
 561   }
 562   return nullptr;
 563 }
 564
 565 template <
 566     class I,
 567     class T,
 568     std::enable_if_t<std::is_reference<T>::value, int> = 0>
 569 void* execOnHeap(Op op, Data* from, void* to) {
 570   switch (op) {
 571     case Op::eNuke:
 572       break;
 573     case Op::eMove:
 574     case Op::eCopy:
 575       static_cast<Data*>(to)->pobj_ = from->pobj_;
 576       break;
 577     case Op::eType:
 578       return const_cast<void*>(static_cast<void const*>(&typeid(T)));
 579     case Op::eAddr:
 580       if (*static_cast<std::type_info const*>(to) == typeid(T)) {
 581         return from->pobj_;
 582       }
 583       throwBadPolyCast();
 584     case Op::eRefr:
 585       return vtableForRef<I, Uncvref<T>>(
 586           static_cast<RefType>(reinterpret_cast<std::uintptr_t>(to)));
 587   }
 588   return nullptr;
 589 }
 590
 591 template <
 592     class I,
 593     class T,
 594     std::enable_if_t<Not<std::is_reference<T>>::value, int> = 0>
 595 void* execOnHeap(Op op, Data* from, void* to) {
 596   switch (op) {
 597     case Op::eNuke:
 598       delete &get<T>(*from);
 599       break;
 600     case Op::eMove:
 601       static_cast<Data*>(to)->pobj_ = std::exchange(from->pobj_, nullptr);
 602       break;
 603     case Op::eCopy:
 604       detail::if_constexpr(std::is_copy_constructible<T>(), [&](auto id) {
 605         static_cast<Data*>(to)->pobj_ = new T(id(get<T>(*from)));
 606       });
 607       break;
 608     case Op::eType:
 609       return const_cast<void*>(static_cast<void const*>(&typeid(T)));
 610     case Op::eAddr:
 611       if (*static_cast<std::type_info const*>(to) == typeid(T)) {
 612         return from->pobj_;
 613       }
 614       throwBadPolyCast();
 615     case Op::eRefr:
 616       return vtableForRef<I, Uncvref<T>>(
 617           static_cast<RefType>(reinterpret_cast<std::uintptr_t>(to)));
 618   }
 619   return nullptr;
 620 }
 621
 622 template <class I, class T>
 623 void* execInSitu(Op op, Data* from, void* to) {
 624   switch (op) {
 625     case Op::eNuke:
 626       get<T>(*from).~T();
 627       break;
 628     case Op::eMove:
 629       ::new (static_cast<void*>(&static_cast<Data*>(to)->buff_))
 630           T(std::move(get<T>(*from)));
 631       get<T>(*from).~T();
 632       break;
 633     case Op::eCopy:
 634       detail::if_constexpr(std::is_copy_constructible<T>(), [&](auto id) {
 635         ::new (static_cast<void*>(&static_cast<Data*>(to)->buff_))
 636             T(id(get<T>(*from)));
 637       });
 638       break;
 639     case Op::eType:
 640       return const_cast<void*>(static_cast<void const*>(&typeid(T)));
 641     case Op::eAddr:
 642       if (*static_cast<std::type_info const*>(to) == typeid(T)) {
 643         return &from->buff_;
 644       }
 645       throwBadPolyCast();
 646     case Op::eRefr:
 647       return vtableForRef<I, Uncvref<T>>(
 648           static_cast<RefType>(reinterpret_cast<std::uintptr_t>(to)));
 649   }
 650   return nullptr;
 651 }
 652
 653 inline void* noopExec(Op op, Data*, void*) {
 654   if (op == Op::eAddr)
 655     throwBadPolyAccess();
 656   return const_cast<void*>(static_cast<void const*>(&typeid(void)));
 657 }
 658
 659 template <class I>
 660 struct BasePtr {
 661   VTable<I> const* vptr_;
 662 };
 663
 664 template <class I, class T, std::enable_if_t<inSitu<T>(), int> = 0>
 665 constexpr void* (*getOps() noexcept)(Op, Data*, void*) {
 666   return &execInSitu<I, T>;
 667 }
 668
 669 template <class I, class T, std::enable_if_t<!inSitu<T>(), int> = 0>
 670 constexpr void* (*getOps() noexcept)(Op, Data*, void*) {
 671   return &execOnHeap<I, T>;
 672 }
 673
 674 template <class I, FOLLY_AUTO... Arch, class... S>
 675 struct VTable<I, PolyMembers<Arch...>, TypeList<S...>>
 676     : BasePtr<S>..., std::tuple<SignatureOf<Arch, I>...> {
 677  private:
 678   template <class T, FOLLY_AUTO... User>
 679   constexpr VTable(Type<T>, PolyMembers<User...>) noexcept
 680       : BasePtr<S>{vtableFor<S, T>()}...,
 681         std::tuple<SignatureOf<Arch, I>...>{thunk<T, User, I>()...},
 682         state_{inSitu<T>() ? State::eInSitu : State::eOnHeap},
 683         ops_{getOps<I, T>()} {}
 684
 685  public:
 686   constexpr VTable() noexcept
 687       : BasePtr<S>{vtable<S>()}...,
 688         std::tuple<SignatureOf<Arch, I>...>{
 689             static_cast<SignatureOf<Arch, I>>(throw_())...},
 690         state_{State::eEmpty},
 691         ops_{&noopExec} {}
 692
 693   template <class T>
 694   explicit constexpr VTable(Type<T>) noexcept
 695       : VTable{Type<T>{}, MembersOf<I, T>{}} {}
 696
 697   State state_;
 698   void* (*ops_)(Op, Data*, void*);
 699 };
 700
 701 template <class I>
 702 constexpr VTable<I> const& select(VTable<_t<Type<I>>> const& vtbl) noexcept {
 703   return vtbl;
 704 }
 705
 706 template <class I>
 707 constexpr VTable<I> const& select(BasePtr<_t<Type<I>>> const& base) noexcept {
 708   return *base.vptr_;
 709 }
 710
 711 struct PolyAccess {
 712   template <std::size_t N, typename This, typename... As>
 713   static auto call(This&& _this, As&&... args)
 714       -> decltype(static_cast<This&&>(_this).template _polyCall_<N>(
 715           static_cast<As&&>(args)...)) {
 716     static_assert(
 717         !IsInstanceOf<std::decay_t<This>, Poly>::value,
 718         "When passing a Poly<> object to call(), you must explicitly "
 719         "say which Interface to dispatch to, as in "
 720         "call<0, MyInterface>(self, args...)");
 721     return static_cast<This&&>(_this).template _polyCall_<N>(
 722         static_cast<As&&>(args)...);
 723   }
 724
 725   template <class Poly>
 726   using Iface = typename Uncvref<Poly>::_polyInterface_;
 727
 728   template <class Node, class Tfx = MetaIdentity>
 729   static typename Uncvref<Node>::template _polySelf_<Node, Tfx> self_();
 730
 731   template <class T, class Poly, class I = Iface<Poly>>
 732   static decltype(auto) cast(Poly&& _this) {
 733     using Ret = AddCvrefOf<AddCvrefOf<T, I>, Poly&&>;
 734     return static_cast<Ret>(
 735         *static_cast<std::add_pointer_t<Ret>>(_this.vptr_->ops_(
 736             Op::eAddr,
 737             const_cast<Data*>(static_cast<Data const*>(&_this)),
 738             const_cast<void*>(static_cast<void const*>(&typeid(T))))));
 739   }
 740
 741   template <class Poly>
 742   static decltype(auto) root(Poly&& _this) noexcept {
 743     return static_cast<Poly&&>(_this)._polyRoot_();
 744   }
 745
 746   template <class I>
 747   static std::type_info const& type(PolyRoot<I> const& _this) noexcept {
 748     return *static_cast<std::type_info const*>(
 749         _this.vptr_->ops_(Op::eType, nullptr, nullptr));
 750   }
 751
 752   template <class I>
 753   static VTable<Uncvref<I>> const* vtable(PolyRoot<I> const& _this) noexcept {
 754     return _this.vptr_;
 755   }
 756
 757   template <class I>
 758   static Data* data(PolyRoot<I>& _this) noexcept {
 759     return &_this;
 760   }
 761
 762   template <class I>
 763   static Data const* data(PolyRoot<I> const& _this) noexcept {
 764     return &_this;
 765   }
 766
 767   template <class I>
 768   static Poly<I&&> move(PolyRoot<I&> const& _this) noexcept {
 769     return Poly<I&&>{_this, Type<I&>{}};
 770   }
 771
 772   template <class I>
 773   static Poly<I const&> move(PolyRoot<I const&> const& _this) noexcept {
 774     return Poly<I const&>{_this, Type<I const&>{}};
 775   }
 776 };
 777
 778 template <class I, class Tail>
 779 struct PolyNode : Tail {
 780  private:
 781   friend PolyAccess;
 782   using Tail::Tail;
 783
 784   template <std::size_t K, typename... As>
 785   decltype(auto) _polyCall_(As&&... as) {
 786     return std::get<K>(select<I>(*PolyAccess::vtable(*this)))(
 787         *PolyAccess::data(*this), static_cast<As&&>(as)...);
 788   }
 789   template <std::size_t K, typename... As>
 790   decltype(auto) _polyCall_(As&&... as) const {
 791     return std::get<K>(select<I>(*PolyAccess::vtable(*this)))(
 792         *PolyAccess::data(*this), static_cast<As&&>(as)...);
 793   }
 794 };
 795
 796 struct MakePolyNode {
 797   template <class I, class State>
 798   using apply = InterfaceOf<I, PolyNode<I, State>>;
 799 };
 800
 801 template <class I>
 802 struct PolyRoot : private PolyBase, private Data {
 803   friend PolyAccess;
 804   friend Poly<I>;
 805   friend PolyVal<I>;
 806   friend PolyRef<I>;
 807   template <class Node, class Tfx>
 808   using _polySelf_ = Poly<AddCvrefOf<MetaApply<Tfx, I>, Node>>;
 809   using _polyInterface_ = I;
 810
 811  private:
 812   PolyRoot& _polyRoot_() noexcept {
 813     return *this;
 814   }
 815   PolyRoot const& _polyRoot_() const noexcept {
 816     return *this;
 817   }
 818   VTable<std::decay_t<I>> const* vptr_ = vtable<std::decay_t<I>>();
 819 };
 820
 821 template <class I>
 822 using PolyImpl =
 823     TypeFold<InclusiveSubsumptionsOf<Uncvref<I>>, PolyRoot<I>, MakePolyNode>;
 824
 825 // A const-qualified function type means the user is trying to disambiguate
 826 // a member function pointer.
 827 template <class Fun> // Fun = R(As...) const
 828 struct Sig {
 829   template <class T>
 830   constexpr Fun T::*operator()(Fun T::*t) const /* nolint */ volatile noexcept {
 831     return t;
 832   }
 833   template <class F, class T>
 834   constexpr F T::*operator()(F T::*t) const /* nolint */ volatile noexcept {
 835     return t;
 836   }
 837 };
 838
 839 // A functon type with no arguments means the user is trying to disambiguate
 840 // a member function pointer.
 841 template <class R>
 842 struct Sig<R()> : Sig<R() const> {
 843   using Fun = R();
 844   using Sig<R() const>::operator();
 845
 846   template <class T>
 847   constexpr Fun T::*operator()(Fun T::*t) const noexcept {
 848     return t;
 849   }
 850 };
 851
 852 template <class R, class... As>
 853 struct SigImpl : Sig<R(As...) const> {
 854   using Fun = R(As...);
 855   using Sig<R(As...) const>::operator();
 856
 857   template <class T>
 858   constexpr Fun T::*operator()(Fun T::*t) const noexcept {
 859     return t;
 860   }
 861   constexpr Fun* operator()(Fun* t) const noexcept {
 862     return t;
 863   }
 864   template <class F>
 865   constexpr F* operator()(F* t) const noexcept {
 866     return t;
 867   }
 868 };
 869
 870 // The user could be trying to disambiguate either a member or a free function.
 871 template <class R, class... As>
 872 struct Sig<R(As...)> : SigImpl<R, As...> {};
 873
 874 // This case is like the one above, except we want to add an overload that
 875 // handles the case of a free function where the first argument is more
 876 // const-qualified than the user explicitly specified.
 877 template <class R, class A, class... As>
 878 struct Sig<R(A&, As...)> : SigImpl<R, A&, As...> {
 879   using CCFun = R(A const&, As...);
 880   using SigImpl<R, A&, As...>::operator();
 881
 882   constexpr CCFun* operator()(CCFun* t) const /* nolint */ volatile noexcept {
 883     return t;
 884   }
 885 };
 886
 887 template <
 888     class T,
 889     class I,
 890     class U = std::decay_t<T>,
 891     std::enable_if_t<Not<std::is_base_of<PolyBase, U>>::value, int> = 0,
 892     std::enable_if_t<std::is_constructible<AddCvrefOf<U, I>, T>::value, int> =
 893         0,
 894     class = MembersOf<std::decay_t<I>, U>>
 895 std::true_type modelsInterface_(int);
 896 template <class T, class I>
 897 std::false_type modelsInterface_(long);
 898
 899 template <class T, class I>
 900 struct ModelsInterface : decltype(modelsInterface_<T, I>(0)) {};
 901
 902 template <class I1, class I2>
 903 struct ValueCompatible : std::is_base_of<I1, I2> {};
 904
 905 // This prevents PolyRef's converting constructors and assignment operators
 906 // from being considered as copy constructors and assignment operators:
 907 template <class I1>
 908 struct ValueCompatible<I1, I1> : std::false_type {};
 909
 910 template <class I1, class I2, class I2Ref>
 911 struct ReferenceCompatible : std::is_constructible<I1, I2Ref> {};
 912
 913 // This prevents PolyRef's converting constructors and assignment operators
 914 // from being considered as copy constructors and assignment operators:
 915 template <class I1, class I2Ref>
 916 struct ReferenceCompatible<I1, I1, I2Ref> : std::false_type {};
 917
 918 } // namespace detail
 919 /// \endcond
 920 } // namespace folly
 921
 922 #undef FOLLY_AUTO