如何通過(guò)poly實(shí)現(xiàn)C++編譯期多態(tài)

引言

前面的文章中我們更多的聚焦在運(yùn)行期反射，本篇我們將聚焦在一個(gè)與反射使用的機(jī)制有所類(lèi)同，但更依賴(lài)編譯期特性的機(jī)制-》編譯期多態(tài)實(shí)現(xiàn)。

c++最近幾版的更新添加了大量的compiler time特性支持，社區(qū)輪子的熱情又進(jìn)一步高漲。這幾年go與rust等語(yǔ)言也發(fā)展壯大，那么，我們能不能在c++中實(shí)現(xiàn)類(lèi)似go interface和rust traits的機(jī)制呢？

答案是肯定的，開(kāi)源社區(qū)早已經(jīng)開(kāi)始了自己的行動(dòng)，dyno與folly：：poly都已經(jīng)有了自己的實(shí)現(xiàn)。兩者的實(shí)現(xiàn)思路基本一致，差別主要在于dyno使用了boost：：hana和其他一些第三方庫(kù)來(lái)完成整體機(jī)制的實(shí)現(xiàn)。

而folly：：poly出來(lái)的晚一些，主要使用c++的新特性來(lái)實(shí)現(xiàn)相關(guān)的功能，依賴(lài)比較少，所以本文將更多的以poly的實(shí)現(xiàn)來(lái)分析編譯期多態(tài)的整體實(shí)現(xiàn)。

一、從c++的運(yùn)行時(shí)多態(tài)說(shuō)起

（一）一個(gè)簡(jiǎn)單的例子

struct Vehicle {
  virtual void accelerate() = 0;
  virtual ~Vechicle() {}
};


struct Car: public Vehicle {
  void accelerate() override;
};


struct Truck: public Vehicle {
  void accelerate() override;  
};

（二）對(duì)應(yīng)的運(yùn)行時(shí)內(nèi)存結(jié)構(gòu)

（三）運(yùn)行時(shí)多態(tài)帶來(lái)的問(wèn)題

性能問(wèn)題

大量的文章都提到，因?yàn)関irtual table的存在，對(duì)比純c的實(shí)現(xiàn)，c++運(yùn)行時(shí)多態(tài)的使用會(huì)付出額外的性能開(kāi)銷(xiāo)。

指針帶來(lái)的問(wèn)題

運(yùn)行時(shí)多態(tài)一般多配合指針一起使用，這也導(dǎo)致基本相關(guān)代碼都是配合堆內(nèi)存來(lái)使用的，后續(xù)又引入了智能指針緩解堆內(nèi)存分配導(dǎo)致的額外心智負(fù)擔(dān)，但智能指針的使用本身又帶來(lái)了其他問(wèn)題。

侵入性問(wèn)題

類(lèi)繼承需要強(qiáng)制指定子類(lèi)的基類(lèi)，當(dāng)我們引入第三方庫(kù)的時(shí)候，要么不可避免的需要對(duì)其進(jìn)行修改，要么需要額外的包裝類(lèi)，這些都會(huì)帶來(lái)復(fù)雜度的上升和性能的下降。還有一些其他的問(wèn)題，這里就不再展開(kāi)了，最近的cppconn多態(tài)本身相關(guān)的討論也是一個(gè)熱點(diǎn)，許多項(xiàng)目開(kāi)始嘗試用自己的方法試圖解決運(yùn)行時(shí)多態(tài)的問(wèn)題，感興趣的可以自行去了解相關(guān)的內(nèi)容。

本部分例子和內(nèi)容主要來(lái)自Louis Dionne的Runtime Polymorphism： Back To The Basics。

二、dyno與poly的實(shí)現(xiàn)思路

（一）dyno與poly的目的-編譯期多態(tài)

dyno想達(dá)成的效果其實(shí)就是實(shí)現(xiàn)編譯期多態(tài)，如作者所展示的代碼片段：

interface Vechicle { void accelerate(); };


namespace lib{
  struct Motorcycle { void accelerate(); };
}
struct Car { void accelerate(); };
struct Truck { void accelerate(); };


int main() {
  std::vector vehicles;
  vehicles.push_back(Car{...});
  vehicles.push_back(Truck{...});
  vehicles.push_back(lib::Motorcycle{...});


  for(auto& vehicle: vehicles) {
    vehicle.accelerate();
  }
}

想法很美好， 但現(xiàn)實(shí)是殘酷的， 并沒(méi)有interface存在， 在可預(yù)知的一段時(shí)間里， 也不會(huì)有， 那么如果要自己實(shí)現(xiàn)相關(guān)的機(jī)制， 該如何來(lái)達(dá)成呢？ 我們?cè)谙挛闹邢葋?lái)看一下整體的實(shí)現(xiàn)思路。

（二）編譯期多態(tài)的設(shè)計(jì)思路

參考前面的運(yùn)行時(shí)多態(tài)模型：

dyno的思路比較直接，嘗試使用兩個(gè)獨(dú)立的部分來(lái)解決編譯期多態(tài)的支持問(wèn)題：

Storage policy-負(fù)責(zé)對(duì)象的存儲(chǔ)。

VTable policy-負(fù)責(zé)函數(shù)分發(fā)調(diào)用。

folly：：Poly的實(shí)現(xiàn)思路大量參考了dyno，與dyno一致，也是同樣的結(jié)構(gòu)。我們繼續(xù)以Vechicle舉例，假設(shè)真的存在Vechicle對(duì)象，那么它的組織肯定是如下圖所示的：

通過(guò)這種結(jié)構(gòu)，我們就能正常的訪問(wèn)到Car等具體對(duì)象的accelerate（）方法了，原理上還是比較簡(jiǎn)潔的，但是要做到完全的編譯期多態(tài)，并不是一個(gè)簡(jiǎn)單的事情。接下來(lái)我們先來(lái)看一個(gè)poly的示例代碼，先從應(yīng)用側(cè)了解一下它的使用。

三、poly的示例代碼

我們還是以Vechicle為例，給出一段poly的示例代碼：

#include 


struct IVehicle {
  // Define the interface for vehicle
  template <class Base> struct Interface : Base {
    void accelerate() const {
      folly::poly_call<0>(*this);
    }
  };
  // Define how concrete types can fulfill that interface (in C++17):
  template <class T> using Members = folly::PolyMembers<&T::accelerate>;
};


using vehicle = folly::Poly;




struct Car {
  void accelerate() const {
    std::cout << "Car accelerate!" << std::endl;
  }
};


struct Trunk {
  void accelerate() const {
    std::cout << "Trunk accelerate!" << std::endl;
  }
};




void accel_func(vehicle const& v) {
  v.accelerate();
}


int main() {
  accel_func(Car{});  // Car accelerate
  accel_func(Trunk{});  // Trunk accelerate
  return 0;
}

從上面的示例可以看到，poly的封裝使用還是比較簡(jiǎn)潔的，主要是兩個(gè)輔助對(duì)象的定義：

IVehicle 類(lèi)的定義

vehicle類(lèi)的定義

（一）IVehicle類(lèi)

struct IVehicle {
  // Define the interface for vehicle
  template <class Base> struct Interface : Base {
    void accelerate() const {
      folly::poly_call<0>(*this);
    }
  };
  // Define how concrete types can fulfill that interface (in C++17):
  template <class T> using Members = folly::PolyMembers<&T::accelerate>;
};

IVehicle類(lèi)主要提供兩個(gè)功能：

通過(guò)內(nèi)嵌類(lèi)型Members來(lái)完成接口包含的所有成員的定義，如上例中的&T：：accelerate。

通過(guò)內(nèi)嵌類(lèi)型Interface提供類(lèi)型擦除后的poly《》對(duì)象的訪問(wèn)接口。

兩者的部分信息其實(shí)有所重復(fù)，另外因?yàn)閜oly是基于c++17特性的，所以也沒(méi)有使用concept對(duì)Interface的類(lèi)型提供約束，這個(gè)地方約束性和簡(jiǎn)潔性上會(huì)有一點(diǎn)折扣。

（二） vehicle類(lèi)

using vehicle = folly：：Poly《IVehicle》;

這個(gè)類(lèi)使用我們前面定義的IVehicle類(lèi)來(lái)定義一個(gè)folly：：Poly《IVechicle》容器對(duì)象，所有滿(mǎn)足IVehicle定義的類(lèi)型都可以被它所容納，與std：：any類(lèi)似，只是std：：any用于裝填任意類(lèi)型，folly：：Poly《》只能用來(lái)裝填符合相關(guān)Interface定義的對(duì)象，比如上面定義的vehicle，就能用來(lái)容納前面示例中定義的Car和Trunk等實(shí)現(xiàn)了void accelerate（） const方法的類(lèi)型。同樣，區(qū)別于std：：any只是用作一個(gè)萬(wàn)能容器，這里的vehicle本身也是支持函數(shù)調(diào)用的，比如例子中的：accelerate（）。

（三）示例小結(jié)

通過(guò)上面的示例代碼，我們對(duì)poly的使用有了初步的了解，從上面的代碼中可以看出，編譯期多態(tài)的使用還是比較簡(jiǎn)潔的，整體過(guò)程跟c++標(biāo)準(zhǔn)的繼承比較類(lèi)似，有幾點(diǎn)差別比較大：

我們不需要侵入性的去指定子類(lèi)的基類(lèi)，我們通過(guò)非侵入性的方式來(lái)使用poly庫(kù)。

我們是通過(guò)構(gòu)建的folly：：Poly《》來(lái)完成對(duì)各種子類(lèi)型的容納的，而不是直接使用基類(lèi)來(lái)進(jìn)行類(lèi)型退化再統(tǒng)一存儲(chǔ)所有子類(lèi)，這樣也就避免了繼承一般搭配堆內(nèi)存分配使用的問(wèn)題。

那么，整套機(jī)制是如何實(shí)現(xiàn)的呢？ 我們?cè)谙挛闹袑⒕唧w展開(kāi)。

四、關(guān)于實(shí)現(xiàn)的猜想

前面的文章中我們介紹了運(yùn)行時(shí)反射的相關(guān)機(jī)制，所以類(lèi)似poly這種使用側(cè)的包裝，如果我們拋開(kāi)性能，考慮用反射實(shí)現(xiàn)類(lèi)似機(jī)制，還是比較容易的。

（一）VTable與meta：：class

VTable的概念其實(shí)與前面的篇章里提到的meta：：class功能基本一致：

meta：：class上存的meta：：method都是已經(jīng)完成類(lèi)型擦除的版本，所以我們可以通過(guò)名稱(chēng)很容易的從中查詢(xún)出自己需要的函數(shù)，比如上例中的accelerate，相關(guān)代碼類(lèi)似于：

const reflection::Function* accel_func = nullptr;
car_meta_class.TryGetFunction("accelerate", accel_func);
runtime::Call(*accel_func, car_obj);

當(dāng)然，此處我們省略了meta：：class的注冊(cè)過(guò)程，也省略了car_obj這個(gè)UserObject的創(chuàng)建過(guò)程。

（二）folly：：Poly《》與UserObject

我們很容易想到，使用UserObject作為Car和Trunk的容器，能夠起到跟folly:Poly《》類(lèi)似的效果。利用UserObject，我們可以很好的完成各種不同類(lèi)型對(duì)象的類(lèi)型擦除，很好的完全不同類(lèi)型對(duì)象的統(tǒng)一存儲(chǔ)和函數(shù)參數(shù)傳遞的目的。

（三）運(yùn)行時(shí)反射實(shí)現(xiàn)的例子

這樣，對(duì)于原來(lái)的例子，省略meta class的注冊(cè)過(guò)程，大致的代碼如下：

struct Car {
  void accelerate() const {
    std::cout << "Car accelerate!" << std::endl;
  }
};


struct Trunk {
  void accelerate() const {
    std::cout << "Trunk accelerate!" << std::endl;
  }
};




void accel_func(UserObject& v) {
  auto& meta_class = v.GetClass();
  const reflection::Function* accel_func = nullptr;
  meta_class.TryGetFunction("accelerate", accel_func);
  runtime::Call(*accel_func, v);
}


int main() {
  //Car meta class register ignore here
  // ...


  //Trunk meta class register ignore here


  accel_func(UserObject::MakeOwned(Car{}));  // Car accelerate
  accel_func(UserObject::MakeOwned(Trunk{}));  // Trunk accelerate


  return 0;
}

功能上似乎是那么回事，甚至因?yàn)檫\(yùn)行時(shí)反射本身各部分類(lèi)型擦除很徹底，好像實(shí)現(xiàn)上更靈活了，但是，這其實(shí)只是形勢(shì)上實(shí)現(xiàn)了一個(gè)運(yùn)行時(shí)interface like的功能，我們?nèi)菀卓闯?，這個(gè)實(shí)現(xiàn)達(dá)成了以下目的：

非侵入性，Car與Trunk不需要額外的修改就能支持interface like的功能。

我們可以利用類(lèi)型擦除的UserObject對(duì)Car和Trunk這些不同類(lèi)型的對(duì)象進(jìn)行存儲(chǔ)。

不同對(duì)象上的accelerate（）實(shí)現(xiàn)可以被正確的調(diào)用。

同時(shí)，這個(gè)實(shí)現(xiàn)存在諸多的問(wèn)題：

運(yùn)行時(shí)實(shí)現(xiàn)，性能肯定有比較大的折扣。

比較徹底的類(lèi)型擦除帶來(lái)的問(wèn)題，整個(gè)實(shí)現(xiàn)一點(diǎn)都不compiler time，編譯期的基礎(chǔ)類(lèi)型檢查也完全沒(méi)有了。

那么我們肯定會(huì)想到，poly是如何利用compiler time特性，實(shí)現(xiàn)更快的interface like的版本的呢？ 這也是我們下一章節(jié)開(kāi)始想展開(kāi)的內(nèi)容。

五、poly的實(shí)現(xiàn)分析

在開(kāi)始分析前，我們先來(lái)回顧一下前面的示例代碼：

using vehicle = folly::Poly;
void accel_func(vehicle const& v) {
  v.accelerate();
}


int main() {
  accel_func(Car{});  // Car accelerate
  accel_func(Trunk{});
  return 0;
}

一切的起點(diǎn)發(fā)生在accel_func()將臨時(shí)構(gòu)造的Car{}和Trunk{}向vehicle轉(zhuǎn)換的過(guò)程中，而我們知道vehicle實(shí)際類(lèi)型是folly::Poly，這也是一個(gè)Duck Type，可以容納所有滿(mǎn)足IVehicle聲明的類(lèi)型，如上例中的Car和Trunk。

上例中，Car和Trunk類(lèi)型向Duck Type類(lèi)型轉(zhuǎn)換的代碼如下：

template <class I>
template ::value, int>>
inline PolyVal::PolyVal(T&& t) {
  using U = std::decay_t;
  //some compiler time && runtime check ignore here
  //...
  if (inSitu()) {
    auto const buff = static_cast<void*>(&_data_()->buff_);
    ::new (buff) U(static_cast(t));
  } else {
    _data_()->pobj_ = new U(static_cast(t));
  }
  vptr_ = vtableFor();
}

  if (inSitu()) {
    auto const buff = static_cast<void*>(&_data_()->buff_);
    ::new (buff) U(static_cast(t));
  } else {
    _data_()->pobj_ = new U(static_cast(t));
  }

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 T>
inline constexpr bool inSitu() noexcept {
  return !std::is_reference::value &&
      sizeof(std::decay_t) <= sizeof(Data) &&
      std::is_nothrow_move_constructible<std::decay_t>::value;
}

template <class I, class T>
constexpr VTable const* vtableFor() noexcept {
  return &StaticConst>>::value;
}

//  StaticConst
//
//  A template for defining ODR-usable constexpr instances. Safe from ODR
//  violations and initialization-order problems.


template <typename T>
struct StaticConst {
  static constexpr T value{};
};


template <typename T>
constexpr T StaticConst::value;

template <class I, class T>
struct VTableFor : VTable {
  constexpr VTableFor() noexcept : VTable{Type{}} {}
};


template <
    class I,
    class = MembersOf<I, Archetype>>,
    class = SubsumptionsOf<I>>
struct VTable;


template <class I, FOLLY_AUTO... Arch, class... S>
struct VTable, TypeList>
    : BasePtr..., std::tuple...> {
 private:
  template <class T, FOLLY_AUTO... User>
  constexpr VTable(Type, PolyMembers) noexcept
      : BasePtr{vtableFor()}...,
        std::tuple...>{thunk_()...},
        state_{inSitu() ? State::eInSitu : State::eOnHeap},
        ops_{getOps()} {}


 public:
  constexpr VTable() noexcept
      : BasePtr{vtable()}...,
        std::tuple...>{
            static_cast>(throw_())...},
        state_{State::eEmpty},
        ops_{&noopExec} {}


  template <class T>
  explicit constexpr VTable(Type) noexcept
      : VTable{Type{}, MembersOf{}} {}


  State state_;
  void* (*ops_)(Op, Data*, void*);
};

void(const Car::*)();

void(*)(const folly::Data &);

template <
    class T,
    FOLLY_AUTO User,
    class I,
    class = ArgTypes,
    class = Bool>
struct ThunkFn {
  template <class R, class D, class... As>
  constexpr /* implicit */ operator FnPtr() const noexcept {
    return nullptr;
  }
};


template <class T, FOLLY_AUTO User, class I, class... Args>
struct ThunkFn<
    T,
    User,
    I,
    TypeList,
    Bool<
        !std::is_const>::value ||
        IsConstMember>::value>> {
  template <class R, class D, class... As>
  constexpr /* implicit */ operator FnPtr() const noexcept {
    struct _ {
      static R call(D& d, As... as) {
        return folly::invoke(
            memberValue(),
            get(d),
            convert(static_cast(as))...);
      }
    };
    return &_::call;
  }
};

struct VTable, TypeList>
    : BasePtr..., std::tuple...> 


template <class T, FOLLY_AUTO... User>
  constexpr VTable(Type, PolyMembers) noexcept
      : BasePtr{vtableFor()}...,
        std::tuple...>{thunk_()...},
        state_{inSitu() ? State::eInSitu : State::eOnHeap},
        ops_{getOps()} {}

//...
accel_func(Car{});  // Car accelerate
00007FF696421166  mov         qword ptr [rsp+20h],0  
00007FF69642116F  lea         rdi,[__ImageBase (07FF696420000h)]  
00007FF696421176  lea         rax,[rdi+33B0h]  
00007FF69642117D  mov         qword ptr [rsp+30h],rax  
00007FF696421182  lea         rcx,[rsp+20h]  
00007FF696421187  call         ?? ::`folly::ThunkFn,std::integral_constant1> >::operatorconst > void (__cdecl*)(folly::Data const &)'::`2'::call (07FF696421490h)  
00007FF69642118C  nop  
00007FF69642118D  mov         rax,qword ptr [rsp+30h]  
00007FF696421192  mov         r9,qword ptr [rax+10h]  
00007FF696421196  xor         ecx,ecx  
00007FF696421198  xor         r8d,r8d  
00007FF69642119B  lea         rdx,[rsp+20h]  
00007FF6964211A0  call        r9  
00007FF6964211A3  nop  
  accel_func(Trunk{});  // Trunk accelerate
//...