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

Eric's range-v3の実装を見る
==========================
[前回](http://qiita.com/kktk-KO/items/41e85427864365dd88fd)、Boost Range 2.0の作者 Eric Nieblerのrange-v3の基本設計を簡単に解説した。
今回は実装を調べる。
特にrange conceptの実装を見てみる。

準備
----

ソースは[github上](https://github.com/ericniebler/range-v3)にある。
お好きな場所で`git clone`すれば良い。

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

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

Concepts Lite概要
-------

range-v3の[C++STLプロポーザル](https://github.com/ericniebler/range-v3/blob/master/doc/D4128.md)は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...>`を見てみる。

```cpp
            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 &&...)`関数らしいのでこちらを見てみる。

```cpp
            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&&...)`メンバ関数が呼び出せるかチェックしているだけである。
なんだそれだけか。分かってしまえば簡単である。
さっそく使ってみよう。

```cpp
#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`関数オブジェクト。

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

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

```cpp
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...>`をコンセプトに継承させれば良い。

つまり、

```cpp
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を使ってみる。
楽しい。