std::tuple の型を実行時に選択したい

std::tuple<int, float>, std::tuple<double> のように型の異なる std::tuple のオブジェクトを動的に生成する方法を考えました。
ネットを探すと、既存の否定的な意見 が出てくるのですが、実現を不可能にする要因を消すためにいくつか制約を加えた結果、実現できましたので紹介します。
なお、困難なことに挑戦した結果、実装が少々難しくなっていますので、予めご了承ください。

背景

次のようなインタフェースの関数のテストに使用する引数を、ファイルから入力できないかと考えたのが始まりです。

template <typename ... Args>
void function(const Args& ... args);

これを実現する方法を考える中で、std::tuple を自動生成できれば std::apply 関数 で上記の関数を呼べると思いました。

問題

ただし、何の制約もなく自由に std::tuple の型を実行時に決めるというのは C++ の仕様上無理です。
C++ のテンプレートは、コンパイル時にソースコードで使用されている型における実装を機械語に翻訳するため、コンパイルの時点で型が決まっている必要があります。例えば std::tuple<int, float> という組み合わせを使用するには、コンパイルの時点で、コンパイラに std::tuple<int, float> の実装を生成してもらう必要があります。
そのため、制約なしにどのような型でも作れるようにするには、無限にあり得る組み合わせのすべてをコンパイル時に生成して機械語に翻訳しておく必要があります。時間もディスク容量も足りません。

実現方針

しかし、生成しないといけない組み合わせが有限個であれば、上記の問題はなくなります。
そこで、次の制約を考えました。

1. std::tuple の 1 要素として使用できる型は有限で、コンパイル時に分かっている。
2. std::tuple の最大の要素数は有限で、コンパイル時に分かっている。

例えば、int と float が使用可能で、2 要素まで可能とすると、あり得る std::tuple の組み合わせは

• std::tuple<>
• std::tuple<int>
• std::tuple<float>
• std::tuple<int, int>
• std::tuple<int, float>
• std::tuple<float, int>
• std::tuple<float, float>

のみです。

なお、一般に $m$ 種類の型を $n$ 個まで使用できるのであれば、あり得る組み合わせの数は以下のようになります。

\sum_{k=0}^n (k 要素の場合の組み合わせ)
= \sum_{k=0}^n m^k
= \frac{m^{n+1} - 1}{m-1}

最大要素数 $n$ が増えると指数関数的に組み合わせが増大してしまうことに注意が必要です。

組み合わせは有限に収まるようになりましたので、あとは、有限しかない組み合わせをうまくコンパイル時に生成させる方法を考えるだけです。（ここからが難しいところです。）

環境

• Ubuntu 20.04
• g++ 9.3.0
• CMake 3.19.0

ここで、この記事の主題となる std::tuple を保持するクラスは C++ 標準の機能だけで書いていますが、テストコードは結果の見やすさのために g++ 依存の機能を使用しています。

実装

上記に加えて、実装上の都合で

• 生成した std::tuple オブジェクトを代入するテンプレート関数は予め決まっている。（テンプレート引数で関数オブジェクトの型を与えておく。）

という条件も加えることでなんとか実装できました。
なお、実装は C++ 17 で書いています。（std::variant を使用したいため。）

長くなるため、ここでは順を追って説明します。ソースコードの全体は この GitLab リポジトリ で公開中です。

まず、内部で使用する定数とヘルパークラスがあります。

// 要素数の上限（指定がない場合はデフォルト値）
#ifndef DYNAMIC_TUPLE_MAX_ELEMENTS
#define DYNAMIC_TUPLE_MAX_ELEMENTS (3)
#endif


// 型の一覧を保持するだけの型
template <typename... Types>
struct type_list {};

続いて、実行時にしか分からない型のオブジェクトを内部に保持するため、保持するオブジェクトの型に依らない基底クラスと、具体的な型を持つ派生クラスを書きます。（std::any の実装とかで使用できる Type Erasure と呼ばれる手法です。）

// 基底クラス（実際に保持するオブジェクトの型を隠ぺいする。）
template <typename VisitorType, typename ElementTypeList>
class tuple_storage_base;

template <typename VisitorType, typename... ElementTypes>
class tuple_storage_base<VisitorType, type_list<ElementTypes...>> {
public:
    // 型定義
    using this_type =
        tuple_storage_base<VisitorType, type_list<ElementTypes...>>;
    using visitor_type = VisitorType;
    using element_types = type_list<ElementTypes...>;
    using variant_type = std::variant<ElementTypes...>;

    // 生成した tuple を使用して関数オブジェクト visitor を visitor(tuple) のように呼び出す
    virtual void visit(visitor_type& visitor) const = 0;

    /* 一旦省略 */
};

// 派生クラス（std::tuple<TupleElementTypes...> 型のオブジェクトを保持する。）
template <typename VisitorType, typename StorableElementTypeList,
    typename TupleType, typename = void>
class tuple_storage;

template <typename VisitorType, typename... StorableElementTypes,
    typename... TupleElementTypes>
class tuple_storage<VisitorType, type_list<StorableElementTypes...>,
    std::tuple<TupleElementTypes...>,
    std::enable_if_t<( // ここの enable_if_t は後述
        sizeof...(TupleElementTypes) <= DYNAMIC_TUPLE_MAX_ELEMENTS)>>
    : public tuple_storage_base<VisitorType,
          type_list<StorableElementTypes...>> {
public:
    // 型定義
    using base_type =
        tuple_storage_base<VisitorType, type_list<StorableElementTypes...>>;
    using visitor_type = typename base_type::visitor_type;
    using element_types = typename base_type::element_types;
    using tuple_type = std::tuple<TupleElementTypes...>;
    using variant_type = typename base_type::variant_type;

    // コンストラクタ（tuple を内部にコピーするだけ）
    explicit tuple_storage(const tuple_type& tuple) : tuple_(tuple) {}

    // 生成した tuple を使用して関数オブジェクト visitor を呼び出す
    void visit(visitor_type& visitor) const override { visitor(tuple_); }

    /* 一旦省略 */

private:
    tuple_type tuple_;
};

これで、具体的な tuple の型に依らない基底クラスで tuple のオブジェクトを保持できるようになりました。
続いて、型を動的に追加していく関数が必要です。

// 基底クラス
template <typename VisitorType, typename... ElementTypes>
class tuple_storage_base<VisitorType, type_list<ElementTypes...>> {
public:
    // 型定義
    using this_type =
        tuple_storage_base<VisitorType, type_list<ElementTypes...>>;
    using visitor_type = VisitorType;
    using element_types = type_list<ElementTypes...>;
    using variant_type = std::variant<ElementTypes...>;

    /* 省略（上記の visitor） */

    // このオブジェクトが持つ tuple に要素を追加する
    // 追加するオブジェクトは std::variant で与える
    virtual std::shared_ptr<this_type> concatenate(
        const variant_type& element) const = 0;

    /* 省略（仮想デストラクタなど、必要だけどこの記事にとって重要ではない関数） */
};
// 派生クラス
template <typename VisitorType, typename... StorableElementTypes,
    typename... TupleElementTypes>
class tuple_storage<VisitorType, type_list<StorableElementTypes...>,
    std::tuple<TupleElementTypes...>,
    std::enable_if_t<( // ここの enable_if_t は後述
        sizeof...(TupleElementTypes) <= DYNAMIC_TUPLE_MAX_ELEMENTS)>>
    : public tuple_storage_base<VisitorType,
          type_list<StorableElementTypes...>> {
public:
    // 型定義
    using base_type =
        tuple_storage_base<VisitorType, type_list<StorableElementTypes...>>;
    using visitor_type = typename base_type::visitor_type;
    using element_types = typename base_type::element_types;
    using tuple_type = std::tuple<TupleElementTypes...>;
    using variant_type = typename base_type::variant_type;

    // コンストラクタ（tuple を内部にコピーするだけ）
    explicit tuple_storage(const tuple_type& tuple) : tuple_(tuple) {}

    /* 省略（上記の visitor） */

    // このオブジェクトが持つ tuple に要素を追加する
    std::shared_ptr<base_type> concatenate(
        const variant_type& element) const override {
        return std::visit(
            // std::visit で std::variant の中のオブジェクトを引数 elem に取り出す
            [this](const auto& elem) {
                // 要素を追加したオブジェクトの型（長すぎるため一旦型定義）
                using new_obj_type = tuple_storage<visitor_type, element_types,
                    std::tuple<TupleElementTypes...,
                        std::decay_t<decltype(elem)>>>;
                // ↓↓↓ 以下の std::tuple_cat で tuple を結合する。
                const auto ptr = std::make_shared<new_obj_type>(
                    std::tuple_cat(tuple_, std::tie(elem))); 
                // std::visit で使用する関数の戻り値は
                // std::variant が保持するオブジェクトの型に依存して変わってはいけないため
                // 明示的に型変換しておく。
                return static_cast<std::shared_ptr<base_type>>(ptr);
            },
            element);
    }

private:
    tuple_type tuple_;
};

上記において、tuple の要素に利用できる型はテンプレート引数 StorableElementTypes または ElementTypes により制限されていますが、tuple の要素数を制限するため、SFINAE を使用します。

// tuple の要素数が一定値以下の場合に使用される実装
template <typename VisitorType, typename... StorableElementTypes,
    typename... TupleElementTypes>
class tuple_storage<VisitorType, type_list<StorableElementTypes...>,
    std::tuple<TupleElementTypes...>,
    std::enable_if_t<( // ここで要素数が DYNAMIC_TUPLE_MAX_ELEMENTS 以下であることを確認
        sizeof...(TupleElementTypes) <= DYNAMIC_TUPLE_MAX_ELEMENTS)>>
    : public tuple_storage_base<VisitorType,
          type_list<StorableElementTypes...>> {
public:
    /* 上記で既に書いているため省略 */
};
// tuple の要素数が一定値を超える場合に使用される実装
template <typename VisitorType, typename... StorableElementTypes,
    typename... TupleElementTypes>
class tuple_storage<VisitorType, type_list<StorableElementTypes...>,
    std::tuple<TupleElementTypes...>,
    std::enable_if_t<( // ここで要素数が DYNAMIC_TUPLE_MAX_ELEMENTS を超えていることを確認
        sizeof...(TupleElementTypes) > DYNAMIC_TUPLE_MAX_ELEMENTS)>>
    : public tuple_storage_base<VisitorType,
          type_list<StorableElementTypes...>> {
public:
    // 型定義
    using base_type =
        tuple_storage_base<VisitorType, type_list<StorableElementTypes...>>;
    using visitor_type = typename base_type::visitor_type;
    using tuple_type = std::tuple<TupleElementTypes...>;
    using variant_type = typename base_type::variant_type;

    // 要素数が多すぎるという例外を投げるコンストラクタ
    explicit tuple_storage(const tuple_type& /*tuple*/) {
        throw std::runtime_error("too many tuple elements");
    }

    // コンストラクタで例外を投げることにより、残りの関数は使用されないため、適当に実装しておく。
    void visit(visitor_type& /*visitor*/) const override {}
    std::shared_ptr<base_type> concatenate(
        const variant_type& /*element*/) const override {
        return nullptr;
    }
};

以上で、std::tuple の型を実行時に選択することができるようになります。
あとは、簡単なラッパークラスを書きました。

template <typename VisitorType, typename... ElementTypes>
class dynamic_tuple {
public:
    // 型定義
    using visitor_type = VisitorType;
    using element_types = impl::type_list<ElementTypes...>;
    using variant_type = std::variant<ElementTypes...>;

    // 最初は空の tuple を生成する
    dynamic_tuple() = default;

    // オブジェクトを追加する
    void push_back(const variant_type& element) {
        storage_ = storage_->concatenate(element);
    }

    // 生成した tuple で関数を呼び出す
    void visit(visitor_type& visitor) const { storage_->visit(visitor); }

private:
    // 上記で作成したクラスにより tuple を保持する
    std::shared_ptr<impl::tuple_storage_base<visitor_type, element_types>>
        storage_{std::make_shared<
            impl::tuple_storage<visitor_type, element_types, std::tuple<>>>(
            std::tuple<>())};
};

上記のクラスで実際に異なる型の tuple が保持できるか確認してみました。

test_dynamic_tuple.cpp

#include <iostream>
#include <string>

// typeid(型).name() の結果を見やすく変換するための g++ 依存のヘッダ
#include <cxxabi.h>

#include "dynamic_tuple.h"

// 引数の tuple の型を人間が見やすいものに変換して標準出力する関数オブジェクト
struct type_name_visitor {
    template <typename Tuple>
    void operator()(const Tuple& /*data*/) const {
        int status = 0;
        std::cout << abi::__cxa_demangle(typeid(Tuple).name(), 0, 0, &status)
                  << std::endl;
    }
};

int main(int argc, char** argv) {
    try {
        dynamic_tuple::dynamic_tuple<type_name_visitor, int, double,
            std::string>
            tuple;

        // コマンド引数に与えられた型のオブジェクトを追加する
        for (int i = 1; i < argc; ++i) {
            const std::string type = argv[i];
            if (type == "int") {
                tuple.push_back(int());
            } else if (type == "double") {
                tuple.push_back(double());
            } else if (type == "str") {
                tuple.push_back(std::string());
            } else {
                throw std::runtime_error("invalid type " + type);
            }
        }

        // 期待する型のオブジェクトが生成されたか確認する
        type_name_visitor visitor;
        tuple.visit(visitor);

        return 0;
    } catch (const std::exception& e) {
        std::cerr << e.what() << std::endl;
        return 1;
    }
}

実行例

実行例を以下に示します。

$ ./test_dynamic_tuple
std::tuple<>
$ ./test_dynamic_tuple int str
std::tuple<int, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >
$ ./test_dynamic_tuple double
std::tuple<double>
$ ./test_dynamic_tuple double str int
std::tuple<double, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int>
$ ./test_dynamic_tuple double str int double
too many tuple elements

3 要素以内の tuple までしっかり生成できていることが確認できました。

組み合わせが生成される仕組み

ここで、コンパイラがどのようにして必要な組み合わせを全てコンパイル時に生成しているのか探っていきましょう。

まず、コンパイラは dynamic_tuple クラスの以下のソースコードから、空の tuple を示す tuple_storage<visitor_type, element_types, std::tuple<>> 型の実装を生成し始めます。

    std::shared_ptr<impl::tuple_storage_base<visitor_type, element_types>>
        storage_{std::make_shared<
            impl::tuple_storage<visitor_type, element_types, std::tuple<>>>(
            std::tuple<>())};

すると、tuple_storage<visitor_type, element_types, std::tuple<>> 型の concatenate 関数

    std::shared_ptr<base_type> concatenate(
        const variant_type& element) const override {
        return std::visit(
            [this](const auto& elem) {
                using new_obj_type = tuple_storage<visitor_type, element_types,
                    std::tuple<TupleElementTypes...,
                        std::decay_t<decltype(elem)>>>;
                const auto ptr = std::make_shared<new_obj_type>(
                    std::tuple_cat(tuple_, std::tie(elem)));
                return static_cast<std::shared_ptr<base_type>>(ptr);
            },
            element);
    }

で std::visit 関数が使用されています。この std::visit 関数は、std::variant の内部に保持されたオブジェクトを第一引数の関数オブジェクトに渡します。ここで、実行時の型に応じた分岐が行われます。
std::visit 関数の第一引数に渡しているラムダ関数は、ラムダ関数の引数に渡されるオブジェクトを追加した型の tuple_storage クラスのオブジェクトを生成します。

例えば、tuple_storage<visitor_type, type_list<int, float>, std::tuple<>> 型の実装を生成する過程では

• tuple_storage<visitor_type, type_list<int, float>, std::tuple<int>>
• tuple_storage<visitor_type, type_list<int, float>, std::tuple<float>>

型の使用が見つかるため、コンパイラはこれらの型に対する実装を追加で生成します。
そして、tuple_storage<visitor_type, type_list<int, float>, std::tuple<int>> 型の実装を生成する過程では

• tuple_storage<visitor_type, type_list<int, float>, std::tuple<int, int>>
• tuple_storage<visitor_type, type_list<int, float>, std::tuple<int, float>>

型の使用が見つかり、コンパイラはこれらの型に対する実装を追加で生成します。

このように再帰的に tuple_storage クラスの実装が追加されていき、要素数が DYNAMIC_TUPLE_MAX_ELEMENTS を超える場合の実装において、追加の tuple_storage クラスの使用が見つからないため、実装の追加生成が終了します。

最大の要素数を変更した場合

ここで、最大要素数 DYNAMIC_TUPLE_MAX_ELEMENTS を増やしていったときにどうなるか見てみました。

上記のテストコードで

#define DYNAMIC_TUPLE_MAX_ELEMENTS 2
#include "dynamic_tuple.h"

のようにマクロ定義を追加してビルドを行いました。

最大要素数	ビルド時間 [秒]	バイナリのサイズ [KB]
0	0.594	52
1	0.975	108
2	2.407	280
3	6.830	800
4	21.598	2396
5	73.945	7304

指数関数的にビルド時間とバイナリのサイズが増加しています。
あまり要素数を増やさない方が良さそうです。

まとめ

本記事では、std::tuple の型の組み合わせを実行時に選択できるようにする方法を考えた結果を紹介しました。型の種類と最大要素数を制限することで、必要な組み合わせをコンパイル時に全て生成できるようにすることで実現しました。ただし、最大要素数を増やすと指数関数的に組み合わせが増大し、ビルド時間やバイナリのサイズも合わせて指数関数的に増加するため、注意が必要です。