可変長template引数でネスト機能付きタスクリストを作る

## 動機
タスクシステムでゲームを作るうえで、ポリモーフィズムを実現するために指定したクラスの順序ごとにオーバーライドされた関数が実行されてほしい。
例えばあらかじめ定められた基底`tasklist::task`にある`update`メンバ関数をオーバーライドするクラス`a0, a1, a2, ...`があったとして、それらを統括する`taskmain`にテンプレートパラメーターで`taskmain<sst::line<a0, a1, a2>>`などの様に引数を与えると、以降その型のアクティブなインスタンスの呼び出しで「`a0`のインスタンス全て→`a1`のインスタンス全て→`a2`のインスタンス全て→...」という実行挙動がなされてほしい。
次は`a0`から`a5`の実装の例です。ただし、`create_task`と`delete_task`についてはまだ説明することがあるので実装を保留しています。

```cpp
#include <iostream>
#include <string>

template<class T>
T *create_task();
template<class T>
tasklist::storage *delete_task(tasklist::arstorage);

struct a0 : public tasklist::task{
    void update(tasklist::arstorage t) override{
        std::cout << "struct a0" << std::endl;
        // 自身のタスクを削除する
        delete_task<a0>(t);
    }
};

struct a1 : public tasklist::task{
    int i;
    a1() : i(0){}

    void update(tasklist::arstorage) override{
        // メッセージを表示してtask a0を生成する
        std::cout << "struct a1 " << i << std::endl;
        ++i;
        create_task<a0>();
    }
};

struct a2 : public tasklist::task{
    void update(tasklist::arstorage t) override{
        // メッセージを表示するだけ
        std::cout << "struct a2" << std::endl;
    }
};

struct a3 : public tasklist::task{
    int i;
    a3() : i(0){}

    void update(tasklist::arstorage) override{
        // メッセージを表示してtask a1を生成する
        std::cout << "struct a3 " << i << std::endl;
        ++i;
        create_task<a1>();
    }
};

struct a4 : public tasklist::task{
    int i;
    a4() : i(0){}

    void update(tasklist::arstorage) override{
        // メッセージを表示してtask a3を生成する
        std::cout << "struct a4 " << i << std::endl;
        ++i;
        create_task<a3>();
    }
};

struct a5 : public tasklist::task{
    int i;
    a5() : i(0){}

    void update(tasklist::arstorage) override{
        // メッセージを表示してtask a4を生成する
        std::cout << "struct a5 " << i << std::endl;
        ++i;
        create_task<a4>();
    }
};
```

型を保持したいので、まず可変長template引数で以下のホルダーを実装します。

```cpp
namespace sst{
    namespace aux{
        template<int N, class... TS>
        struct get_type_helper;

        template<int N, class T, class... TS>
        struct get_type_helper<N, T, TS...>{
            using type = typename get_type_helper<N - 1, TS...>::type;
        };

        template<class T, class... TS>
        struct get_type_helper<0, T, TS...>{
            using type = T;
        };
    }

    template<class T, int N>
    struct task{
        static const int num = N; // Tの存在できるインスタンス数
        using type = T;
    };

    template<class... TS>
    struct line{
        static const int num = sizeof...(TS);
        template<int N>
        struct typeholder{
            using type = typename aux::get_type_helper<N, TS...>::type;
        };
    };
}
```

`sst::line`で複数の型を保持し、`typeholder`メンバで任意の位置の型を取得できるようになりました。
後述する理由によりやや手間ではありますが、以下の記法が可能になりました。

```cpp
tasklist::taskmain<
    sst::line<task<a0, 10>, task<a1, 10>, task<a2, 10>>
> taskmain;
```

しかしタスクを表現したクラス`a0, a1, a2`をただ直線上に並べるだけで、ヒエラルキーを構築して型をまとめてカテゴライズできないとなるとやや不便です。以下のようなwrapperをsst内部に書き足します。

```cpp
template<class T, class L>
struct nest{
    using type = T;
    using line = L;
};
```

`sst::nest`はタグとして機能する型`type`と、ネスト対象となる型`line`を保持します。
実際に使ってみると以下の様になります。

```cpp
tasklist::taskmain<
    sst::line<
        sst::task<a0, 10>,
        sst::task<a1, 10>,
        sst::nest<
            sst::task<a2, 0>,
            sst::line<
                sst::task<a3, 10>,
                sst::task<a4, 10>,
                sst::task<a5, 10>
            >
        >
    >
> taskmain;
```

一番上の実行ヒエラルキーに`a0, a1`があり、次のヒエラルキー`a2`に`a3, a4, a5`が存在する、という複雑な表現ができるようになりました。
後でこれらに関して、`a0, a1`や`a3, a4, a5`のインスタンスのイテレーターを定数時間で得たり、`a2`で括られた型のインスタンス群のイテレーターを包括して取得する方法を実装していきましょう。

## メモリ管理
タスクリストはリンクリストでメモリ管理を行います。そのクラスを`storage`とすると、以下の実装になります。

```cpp
template<class = void>
struct xstorage{
    using fn_type = void (*)(xstorage<>*&);

    xstorage<> *next, *prev;
    void *wa;
    fn_type fn;
    enum class sp{
        storage,
        begin,
        end
    };
    sp spflag; 
};

using storage = xstorage<>;
using arstorage = storage*&;
```

双方向リンクリストなので`next`と`prev`が用意されています。
`void *wa`はワーキングエリアで、ここに`a0, a1, a2, ...`のインスタンスの実体がアロケートされます。
`fn_type`及び`fn`は、継承関係にある型構造のインターフェイスのメンバ関数の実行をType Erasureで一般化して仲介する関数ポインタです。
`spflag`は、現在のストレージが通常のストレージであるか、それともイテレータのために用意された`begin/end`ダミーストレージであるかを区別するフラグです。
ストレージの操作は通常ポインタを介して行われますが、ストレージ内部のインスタンスで関数実行中に自分自身を削除するケースがあるはずなのでその時のためにポインタの参照である`arstorage`型を記述しておきます。

## 全てのタスクの基底クラス

```cpp
class task{
    template<class L>
    friend class taskmain;

private:
    inline static void fn(tasklist::arstorage t){
        static_cast<task*>(t->wa)->update(t);
    }

public:
    inline virtual void update(tasklist::arstorage){}
};
```

後述するクラス`taskmain`内でのみ`fn`関数を認識可能な状態にしたいのでfriend宣言しておきます。その実態はワーキングエリアを自身の型にキャストして継承先の`update`メンバ関数を呼び出す事です。

## タスクを統括するクラス
次はタスクを統括するクラスです。想定する機能としては、タスク巡回のために

- 指定した型のタスクのイテレーターを定数時間で持ってくる。
- タスクのメモリ領域を事前に保持しておく。

その他、型操作としてネストされている型を判定したり取り除いたりします。

```cpp
template<class L>
class taskmain{
private:
    int *tasknum;
    storage
        xbegin_,
        xend_,
        *sysarray,
        **taskarray;
    void **workingarea;
    using allocator = void *(*)();
    using deallocator = void (*)(void*&);
    allocator *alloc_;
    deallocator *dealloc_;
    // ....
};
```

`tasknum` は型ごとに現在のタスク数を保持する配列です。
`xbegin_`, `xend_` はトップレベルのイテレーターとして機能するダミーのストレージです。
`sysarray` は型ごとのイテレーターを保持するダミーストレージ配列です。
`taskarray` は型ごとにタスクのストレージを保持します。型->タスクとなっているので二重の配列です。
`alloc_`, `dealloc_` は `workingarea` をアロケートするためのアロケーターで、型に依存しないようにtemplate関数の実体を函数ポインタで保持するようになっています。

```cpp
template<class T, int N>
inline static void *alloc(){
    return new T[N];
}

template<class T>
inline static void dealloc(void *&ptr){
    delete[] static_cast<T*>(ptr);
    ptr = nullptr;
}
```

型操作は次の通りです。

```cpp
// ネスト型を取り除く
template<class T>
struct nested_test;

template<class T, int i>
struct nested_test<sst::task<T, i>>{
    using type = T;
    using line = void;
};

template<class T, class K>
struct nested_test<sst::nest<T, K>>{
    using type = T;
    using line = K;
};

//タスク型を取り除く
template<class T>
struct distasktype{
    using type = T;
};

template<class T, int i>
struct distasktype<sst::task<T, i>>{
    using type = T;
};

//ネスト型を取り除く
template<class T>
struct disnesttype{
    using type = T;
};

template<class T, class U>
struct disnesttype<sst::nest<T, U>>{
    using type = T;
};
```

## 実際に使ってみる

今までの実装を踏まえて例です。

```cpp
int main(){
    // タスクのメモリ領域を確保する
    taskmain.reserve<a0>();
    taskmain.reserve<a1>();
    taskmain.reserve<a2>();
    taskmain.reserve<a3>();
    taskmain.reserve<a4>();
    taskmain.reserve<a5>();

    // タスク a5 を生成する
    taskmain.create_task<a5>();

    // タスクを回す
    for(int i = 0; i < 6; ++i){
        std::cout << i << "--------" << std::endl;
        taskmain();
    }

    // a2で束ねられたタスクをカウントする
    int n = 0;
    for(
        tasklist::storage *t = taskmain.begin<a2>();
        t != taskmain.end<a2>();
        t = t->next
    ){
        if(t->spflag == tasklist::storage::sp::storage){
            ++n;
        }
    }

    std::cout
        << "a2で束ねられたタスクの数は"
        << n
        << "個です"
        << std::endl;

    return 0;
}
```

## 終わりに
大体の形はこんなものになります。
ネストを考慮した型の操作など、入り組んだコードはありますが説明が長くなるので割愛します。
[ソースコードの全容をgistに掲載しておきました](https://gist.github.com/pointwiseproduct/8e7af48aabd43e0868f23201cf654564)