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

引言

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

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

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

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

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

（一）一個簡單的例子

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


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


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

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

（三）運(yùn)行時多態(tài)帶來的問題

性能問題

大量的文章都提到，因為virtual table的存在，對比純c的實現(xiàn)，c++運(yùn)行時多態(tài)的使用會付出額外的性能開銷。

指針帶來的問題

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

侵入性問題

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

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

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

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

dyno想達(dá)成的效果其實就是實現(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)實是殘酷的， 并沒有interface存在， 在可預(yù)知的一段時間里， 也不會有， 那么如果要自己實現(xiàn)相關(guān)的機(jī)制， 該如何來達(dá)成呢？ 我們在下文中先來看一下整體的實現(xiàn)思路。

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

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

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

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

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

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

通過這種結(jié)構(gòu)，我們就能正常的訪問到Car等具體對象的accelerate（）方法了，原理上還是比較簡潔的，但是要做到完全的編譯期多態(tài)，并不是一個簡單的事情。接下來我們先來看一個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的封裝使用還是比較簡潔的，主要是兩個輔助對象的定義：

IVehicle 類的定義

vehicle類的定義

（一）IVehicle類

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類主要提供兩個功能：

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

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

兩者的部分信息其實有所重復(fù)，另外因為poly是基于c++17特性的，所以也沒有使用concept對Interface的類型提供約束，這個地方約束性和簡潔性上會有一點折扣。

（二） vehicle類

using vehicle = folly：：Poly《IVehicle》;

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

（三）示例小結(jié)

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

我們不需要侵入性的去指定子類的基類，我們通過非侵入性的方式來使用poly庫。

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

那么，整套機(jī)制是如何實現(xiàn)的呢？ 我們在下文中將具體展開。

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

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

（一）VTable與meta：：class

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

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

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

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

（二）folly：：Poly《》與UserObject

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

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

這樣，對于原來的例子，省略meta class的注冊過程，大致的代碼如下：

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)行時反射本身各部分類型擦除很徹底，好像實現(xiàn)上更靈活了，但是，這其實只是形勢上實現(xiàn)了一個運(yùn)行時interface like的功能，我們?nèi)菀卓闯?，這個實現(xiàn)達(dá)成了以下目的：

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

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

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

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

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

比較徹底的類型擦除帶來的問題，整個實現(xiàn)一點都不compiler time，編譯期的基礎(chǔ)類型檢查也完全沒有了。

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

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

在開始分析前，我們先來回顧一下前面的示例代碼：

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


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

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

上例中，Car和Trunk類型向Duck Type類型轉(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
//...