Eric's range-v3の実装を見る

前回、Boost Range 2.0の作者 Eric Nieblerのrange-v3の基本設計を簡単に解説した。
今回は実装を調べる。
特にrange conceptの実装を見てみる。

準備

ソースはgithub上にある。
お好きな場所でgit cloneすれば良い。

コンパイラとstdlibはC++11をサポートしていなければならない。
READMEによると、コンパイラはgcc4.9.0以上又は、clang3.4.0以上がサポートされている。
c++11をサポートしているlibstdc++かlibc++を用意するのを忘れずに。（他のでも良いが）

早速コードにダイブして見よう。

Concepts Lite概要

range-v3のC++STLプロポーザルはConcepts Liteを仮定して書かれているが、githubにあるソースコードはC++11で動くリファレンス実装となっている。
そのため、C++11の範囲内でConcepts Liteをシミュレートしている。
(次期C++にそのうち入る規格通りかどうかは分からない)

厳密にはこのConcepts Liteのシミュレーションはrange-v3の一部では無いが、面白そうなので解説してみる。
興味無い人は飛ばすべきである。
range/v3/utility/concepts.hppから大体辿っていける。

まずは ranges::v3::concepts::models<Concept,Ts...>を見てみる。

            template<typename Concept, typename...Ts>
            struct models
              : std::integral_constant<bool,
                    decltype(detail::models_(nullval<Concept>(), std::declval<Ts>()...))::value>
            {};

            template<typename Concept, typename...Args, typename...Ts>
            struct models<Concept(Args...), Ts...>
              : models<Concept, typelist_element_t<Args::value, typelist<Ts...> >...>
            {};

なにやら奇怪だが、意味的には Ts...がConceptを満たしているかどうかを判定するメタ関数だろう。
Ts...のうち、実際にどの引数をどの順序で渡すかも指定できる様である。
Concept(Args...)という関数型をConceptとしてmodelsに渡せば良い。
実態は ranges::v3::concepts::details::models(Concept*, Ts &&...)関数らしいのでこちらを見てみる。

            template<typename...Ts>
            auto models_(any, Ts &&...) ->
                std::false_type;

            template<typename Concept, typename...Ts>
            auto models_(Concept *c, Ts &&...ts) ->
                always_t<
                    typelist_expand_t<
                        lazy_and,
                        typelist_transform_t<
                            base_concepts_of_t<Concept>,
                            meta_bind_back<concepts::models, Ts...>::template apply>>,
                    decltype(c->requires_(std::forward<Ts>(ts)...))>;

この意味はこうだ。
コンセプトは複数のコンセプトを組み合わせて作られている事もある。
その様な場合、元になるコンセプトはConcept::base_concepts_tにtypeilstという型の独自のタプルに格納してある。
これらの、謂わば親コンセプトに対してconcepts::model<EachParentConcept,Ts..>メタ関数を再帰的に呼び出して、typelistに格納する。
concepts::modelはstd::integral_constant<bool,value>を返すので、それらをand取って真ならば、Concept::requires_(TS&&...)メンバ関数が呼び出せるかチェックし、std::true_typeを返す。そうでなければstd::false_typeを返す。

まぁ、ようするに、親コンセプトも含めて全てのコンセプトに対してrequires_(TS&&...)メンバ関数が呼び出せるかチェックしているだけである。
なんだそれだけか。分かってしまえば簡単である。
さっそく使ってみよう。

#include <range/3/all.hpp>

struct foo_concept
{
    template<typename T>
    auto requires_(T && t) -> decltype(
        t.bar
    );
};

struct foo { double bar; };
struct not_foo { double not_bar; };

static_assert(ranges::v3::concepts::models<foo_concept,foo>::value,"assert");
static_assert(ranges::v3::concepts::models<foo_concept,not_foo>::value,"assert"); //error

どうやら正しく動作している。

requires_を簡単に記述するためのメタ関数も用意されている。
まずはvalid_expr_t valid_expr関数オブジェクト。

template<typename ...Ts>
auto requiers_(Ts &&.. ts) -> decltype(
    ranges::v3::concepts::valid_expr(
    //ここで好きなだけ関数を呼び出せば良い。
    ));

ある型がコンセプトを満たしているかどうかチェックする関数concepts::models_of<Concept,Ts...>(Ts &&...)（ようするにconcepts::modelsメタ関数のラッパー)

struct cat_concept
{
    template<typename T>
    auto requires_(T && t) -> decltype(
        ranges::v3::concepts::valid_expr(
            ranges::v3::concepts::models_of<animal_concept,T>(t)
        ));
};

これと同じ事は先ほど述べた様に、base_concepts_t typedef名をコンセプト内で定義すれば良い。
その様な作業をかっこ良く行う方法が用意されている。
concepts::refines<Concepts...>をコンセプトに継承させれば良い。

つまり、

struct cat_comcept : range::v3::concepts::refines<animal_concept>
{
    template<tpename T>
    auto requires_(T && t) -> decltype(
        ranges::v3::concepts::valid_expr(

        ));
};

としても同じである。

尤も、concepts::models_ofは親コンセプト以外にも使えるので、concepts::refinesイディオムと等価というわけではない。

ここまで理解できれば、きっとrange_concepts.hppを読み解く事ができる。

Iterable Concept

Iteratable Conceptはrange_concepts.hppとutility/iterator_concepts.hppに書いてある。
TがコンセプトIteratableを満たすとは

begin(t)が呼び出せる。
end(t)が呼び出せる。
begin(t)の返り値の型がIteratorコンセプトを満たす。
end(t)の返り値の型がRegularコンセプトを満たす。
begin(t)の返り値の型とend(t)の返り値の型がEqualityComparableコンセプトを満たす。

RangeのアルゴリズムはIterableに基づいて実装される。
Iterableはconstructbilityやassignabilityについては何も言っていない。
これは、配列型がこれらを満たさないためである。

後はInput-, Forward-, Bidirectional-, RandomAccess-等おきまりのコンセプトの他、Bounded-(beginとendの返り値が同じ型)、Sized-(size(t)が定義されている)等がある。

Range Concept

Range ConceptはSemiRegularコンセプトとIterableコンセプトを合わせたコンセプト。
SemiRegularコンセプトは

DefaultConstructible
CopyConstructible
Destructible
CopyAssignable
Allocatable

のそれぞれのコンセプトを合わせたコンセプト。

RangeもIteratableと同じ様に色々な派生がある。

次回は実際にRangeを使ってみる。
楽しい。

Eric's range-v3の実装を見る[Concept編]

Eric's range-v3の実装を見る

準備

Concepts Lite概要

Iterable Concept

Range Concept