Metaprogramming - TypeList

Metaprogramming 是 C++ 一個廣為人知的技巧，儘管 template programming 的技術本意並不是為了滿足 Metaprogramming，但在開發社群中程式設計師逐漸意識到 Metaprogramming 對終端開發者來說能減少程式碼量、增加可讀性、增進程式效率。但 Metaprogramming 是把雙面刃，對於透過 template programming 來實現 meta 的設計者來說，Metaprogramming 有許多較不直覺的寫法，並且有可能增加編譯時間。

來看一下 TypeList 這個例子，TypeList 是能將複數型別以 list 形式作為型別表示的技術，他的表示形式非常簡單：

struct TNull {};

template <typename TCurr, typename TNext> struct TList {
  using curr = TCurr;
  using next = TNext;
};

如果我們希望一個 {int, double, char} 的 TypeList 只要寫成 TList<int, TList<double, TList<char, TNull>>>，對編譯器來說這一型別其實是：

struct TList_char_null {
  using curr = char;
  using next = TNull;
};

struct TList_double_next {
  using curr = double;
  using next = TList_char_null;
};

struct TList_int_next {
  using curr = int;
  using next = TList_double_next;
};

也許會有人納悶，為何需要一個 TNull 這樣一個完全沒有任何屬性的 struct。這樣的 struct 在 Metaprogramming 被當作 tag 來使用；以程式設計的角度來說，我們可以把它當作一種 symbol。即便程式碼中充斥各種沒有屬性的 empty struct，只要它們名字不同，編譯器就不會混為一談。TNull作為 symbol，就像 CString 以 \0 結尾，TNull必須作為 TypeList 的結尾。我們來看看怎麼樣對 TypeList 進行遞迴以計算長度。

template <typename TList> struct TListLength {
  static const size_t result = 1 + TListLength<typename TList::next>::result;
};

這個 template struct 所要表達的意涵很單純。舉例來說如果你是隊伍的最後一個人，而你想要知道隊伍到底有多少人時，你很肯定的是這個隊伍只少有一個人也就是你自己，於是你問排在你前面的人：「從排首到你一共有多少人？」只要將得到的答案加上一，就是整個隊伍的長度。這個 template struct 正是以這種形式來推導出 TypeList 的長度。如果你前面的人也不知道答案，就再問更前面的人。

但是這個 template struct 存在一個致命的問題，那就是它無法推導成功。因為別忘了，TNull::next是不存在的。相當於，排首的人要如何回答「從排首到你一共有多少人？」這個問題呢？在排首的人意識到，因為他自己就是排首也無須過問，因此答案是 1 + 0 人。

template <> struct TListLength<TNull> { static const size_t result = 0; };

這也就是所謂的特化(specialization)，是學習 Metaprogramming 不可或缺的 template 技巧。我們來看看下一個情境：要如何存取 TypeList 特定位置的類型？我們一樣以隊伍說明，你要如何找到隊伍中的第 3 位呢？從遞迴的角度來看，第 3 位其實就是第 2 位的下一位，所以我們只要找到隊伍中的第 2 位就行了。同理，既然不知道誰是隊伍中的 2 位，那我只要知道隊伍中的第 1 位也就是排首就行了吧？所以找到第 N 位的問題，我們其實只需要兩個定義：

隊伍中的第 1 位
隊伍中的第 N 位，是隊伍中的第 N - 1 位的下一位

寫成 C++ 會像這樣：

template <typename TList, size_t index> struct TListAt {
  using result = typename TListAt<TList, index - 1>::next::curr;
  using next = typename TListAt<TList, index - 1>::next::next;
};

template <typename TList> struct TListAt<TList, 0> {
  using result = typename TList::curr;
  using next = typename TList::next;
};

TypeList 的具體用途是乘載複數的型別資訊，聽起來好像很方便，但有什麼實質用處呢？舉個例子：在以 binary 形式存取緩衝時，我們最常需要進行寫入與檢查的其實是使特定位置的 byte 符合特定的數值內容。傳統面臨的挑戰是這樣的資訊很難有效地表示，也很難復用。但是有 TypeList，我們完完全全可以把 byte 規範當作一個整體型別。

template <size_t _offset, uint8_t _value> struct Code {
  static const size_t offset = _offset;
  static const uint8_t value = _value;
};

template <typename TList, typename T, T... indexes>
inline void impl_fill(uint8_t *buffer, std::integer_sequence<T, indexes...> _) {
  ((buffer[TListAt<TList, indexes>::result::offset] =
        TListAt<TList, indexes>::result::value),
   ...);
}

template <typename TList> inline void fill(void *p) {
  constexpr auto length = TListLength<TList>::result;
  impl_fill<TList>((uint8_t *)p, std::make_index_sequence<length>{});
}

using b0 = Code<2, 0x03>;
using b1 = Code<3, 0x5E>;
using b2 = Code<5, 0x7C>;
using list = typename MakeList<b0, b1, b2>::result;
char buffer[8];
fill<list>(buffer);
ASSERT_TRUE(b0::value == buffer[b0::offset]);
ASSERT_TRUE(b1::value == buffer[b1::offset]);
ASSERT_TRUE(b2::value == buffer[b2::offset]);

熟稔 C++ 的讀者也許會好奇，上面這個片段其實並不需要 TypeList，只要稍微調整 fill 完全能夠以 parameter pack 來處理。但與 TypeList 不同，parameter pack 並不是一種型別。從語意上，我們很難將一連串的型別當作一個整體的資訊來看待，但是 TypeList 毫無疑問地是一種型別。parameter pack 展開要不是透過 fold-expression 以一致的邏輯來操作被 unpack 的資訊，要不然就是 forward 給真正的 function call。

另外由於 TypeList 被發明出來的時候，C++ 還沒有 parameter pack 這個技巧能使用。因此當時的 TypeList 通常都是以定義好的 macro 展開TList<T0, TList<T1, TList<T2, ...>>>這種相較不直覺的遞迴套入形式，但是現在有了 parameter pack 其實只要再下點功夫就能寫成 MakeList<T0, T1, T2, ...>::result 這種直覺又易讀的形式。