ややプログラム紀行

博士1年のプログラムに関する日記

C++のstd::functionを読んでみる

この記事はIS18er Advent Calendar 2017の6日目の記事として書かれました。


前回の記事でC++11テンプレートの土台に触れてみたので、今回はstd::functionを読んでいこうと思います😇*1
ライブラリによって実装の仕方は違うのであくまで一例を見ていくことになりますが、思ったよりタメになることが多くて、std::functionを題材にしてよかったなぁなんて思ってます
毎度おなじみですが、間違っているとこもあると思うのでぜひ指摘してください(´・ω・`)

先に言っておくと、さすがにstd::functionを全てみるのはしんどすぎるので、とりあえずラムダ式を保持した時の動きを元に話を進めようと思います

目次

そもそもstd::functionってなんぞ

std::functionとはC++11で導入された、あらゆる関数ポインタ、ラムダ式、関数オブジェクト*2などを保持できるクラスです
ちなみにラムダ式とはC++11で追加された機能ですが、下のリンクによると簡易的な関数オブジェクトを作成する機能のようです
cpprefjp.github.io

#include <iostream>
#include <functional>

using namespace std;

class Add{
public:
	int operator() (int a, int b) {
		return a + b;
	}
};

int Sub(int a, int b) {
	return a - b;
}

int main() {
	// 関数オブジェクト
	Add add;
	function<int(int, int)> f = add;
	cout<<"f(10, 20) = "<<f(10, 20)<<endl;

	// 関数ポインタ
	function<int(int, int)> g = Sub;
	cout<<"g(10, 20) = "<<g(10, 20)<<endl;

	// ラムダ式
	function<int(int, int)> h = [](int a, int b){ return a * b; };
	cout<<"h(10, 20) = "<<h(10, 20)<<endl;

	return 0;
}

出力:

f(10, 20) = 30
g(10, 20) = -10
h(10, 20) = 200

function<返り値の型(引数1の型, 引数2の型,...)>と書くことで、それに対応したものならなんでも保持することができます
関数ポインタなんて、int (*g)(int, int) = Sub;って書くよりよっぽど楽でいいですね

std::functionの実装に必要なこと

さて、これの実装ですが、一体どうやっているんでしょーか???
パッと考える限り次の要件を満たす必要がありそうです

  1. function<返り値の型(引数1の型, 引数2の型,...)>と書けるようにする
  2. コンストラクタ及びoperator=で、関数オブジェクト、関数ポインタなどの代入を行うのでテンプレートを使って頑張る
  3. operator()*3で保持しているオブジェクトの関数呼び出しを行う

「頑張る」ってところが重要

さらに考えてみると、もう2つほどめんどくさい事実が思いつきます
第一に、「function<返り値の型(引数1の型, 引数2の型,...)>」という書き方で関数オブジェクトや関数ポインタを保持することができますが、根本的に関数オブジェクトと関数ポインタの型は違います
それを意識させずに使えるのがstd::functionのすごいところなわけですが、実装は大変そうですね

型の違いを吸収するテクニックとしてType Erasureというものがあります
例えばBoostライブラリにはanyという型があり、これはあらゆる型のオブジェクトを入れることができる*4魔法のようなものですが、これにもType Erasureが使われているわけです
これの実装は様々なやり方がありますが、std::functionでもこのテクニックが使われていることは間違いなさそうです


第二に、次のコードを見てみてください

#include <iostream>

using namespace std;

int main() {
	int x[10000];
	auto a = [=](){
		cout<<x[0]<<endl;
	};

	cout<<sizeof(a)<<endl;
}

出力:

40000

ラムダ式にはキャプチャという機能があり、ラムダ式の外から変数をコピーすることができます
なんでこの機能があるの〜〜っていう話は下のサイトを参照してみてください(C++14だけど)
d.hatena.ne.jp

上のコードでは馬鹿でかい配列をキャプチャしていますが、おかげでラムダ式のサイズが40000バイトになっています
つまりラムダ式のサイズは可変な訳です

std::functionは関数ポインタも関数オブジェクトもラムダ式も保持できるわけですが、ラムダ式(つまり関数オブジェクト)のサイズが可変だとめっちゃ困りますね
この事実より、std::functionにはメモリを動的確保する機構が必要なことも分かります


以上の事柄をもう一度まとめてみましょう

  1. function<返り値の型(引数1の型, 引数2の型,...)>と書けるようにする
  2. コンストラクタ及びoperator=で、関数オブジェクト、関数ポインタなどの代入を行うのでテンプレートを使って頑張る
  3. operator()で保持しているオブジェクトの関数呼び出しを行う
  4. Type Erasureによって型の違いを吸収する
  5. メモリの動的確保

道のり険しそうですね

実際の実装

具体的にコードを見ていく前にstd::functionがどんな感じの構成になっているか軽く見てみます
まずstd::functionは下のように定義されています*5

template<class _Fp> class function; // undefined

// 中略

template<class _Rp, class ..._ArgTypes>
class function<_Rp(_ArgTypes...)>
    : public __function::__maybe_derive_from_unary_function<_Rp(_ArgTypes...)>,
      public __function::__maybe_derive_from_binary_function<_Rp(_ArgTypes...)>
{
// いろいろ

あれ、functionが2個定義されてる?(すっとぼけ

これはテンプレートの部分特殊化ですね
まずクラステンプレートのfunctionを定義だけして、そのあとにテンプレートの型の書き方を「class function<_Rp(_ArgTypes...)>」と指定することで、これ以外の書き方をした場合はfunctionクラスが未定義となりエラーになるわけです
こんな書き方もできるんだなぁって感じです


次にstd::functionはメンバ変数は下のようになっています

typedef __function::__base<_Rp(_ArgTypes...)> __base;
typename aligned_storage<3*sizeof(void*)>::type __buf_;
__base* __f_;

std::functionで保持するオブジェクトのサイズは可変ですが、大抵の場合は関数ポインタのような小さいサイズのものばかりなので、ある程度のサイズまでは用意してあるバッファに保存することで最適化しようというテクニックがあり、これをSmall Size Optimization(SSO)と言います*6

今回見てみる実装はSSOが用いられているようで、「__buf_」というのがバッファに当たります

また、「__f_」は保持している関数ポインタや関数オブジェクトなどを指すポインタです

コンストラクタ

それでは実際にどう動くか見てみようと思います
まず、std::functionを作成と同時にラムダ式で初期化したことにします*7

template<class _Rp, class ..._ArgTypes>
template <class _Fp>
function<_Rp(_ArgTypes...)>::function(_Fp __f,
                                     typename enable_if
                                     <
                                        __callable<_Fp>::value &&
                                        !is_same<_Fp, function>::value
                                     >::type*)
    : __f_(0)
{
    if (__not_null(__f))
    {
        typedef __function::__func<_Fp, allocator<_Fp>, _Rp(_ArgTypes...)> _FF;
        if (sizeof(_FF) <= sizeof(__buf_) && is_nothrow_copy_constructible<_Fp>::value)
        {
            __f_ = (__base*)&__buf_;
            new (__f_) _FF(move(__f));
        }
        else
        {
            typedef allocator<_FF> _Ap;
            _Ap __a;
            typedef __allocator_destructor<_Ap> _Dp;
            unique_ptr<__base, _Dp> __hold(__a.allocate(1), _Dp(__a, 1));
            new (__hold.get()) _FF(move(__f), allocator<_Fp>(__a));
            __f_ = __hold.release();
        }
    }
}

邪魔なとこ少し消しました
まず、引数の2番目にenable_ifがありますね
enable_ifの中では__callableとis_sameが書いてあります、おそらく__callableは名前の通り関数呼び出し可能な型かどうかでしょうか🤔*8
is_sameは1つ目の型と2つ目の型が同じ時に::valueがtrueになります
つまり結論から言うと、「_Fpは関数呼び出し可能」かつ「_Fpとfunctionは同じ型でない」ときのみ、この関数が定義されると言うことですね


「__not_null」は__fの型によって場合分けされており、泥臭く実装してあります
ここでif(__f)とせず__not_nullを介している理由はマジでわからないです、教えてください😇*9

そのあとは__f_にオブジェクトを保持するために、_FFという型のサイズがバッファより小さければ*10あらかじめ用意していたバッファ__buf_を、バッファに収まりきらなさそうな場合はどうやらunique_ptrを使って動的にバッファを確保し、あとはどちらも保持するオブジェクトをムーブ*11し、__base型の__f_にplacement newするという流れになっているみたいですね


さて、_FFってなんだよって話ですが、実はこれがType Erasureを実現するモノになっています

// _FF
typedef __function::__func<_Fp, allocator<_Fp>, _Rp(_ArgTypes...)> _FF;

// __func
template<class _FD, class _Alloc, class _FB> class __func;

template<class _Fp, class _Alloc, class _Rp, class ..._ArgTypes>
class __func<_Fp, _Alloc, _Rp(_ArgTypes...)>
    : public  __base<_Rp(_ArgTypes...)>
{
    __compressed_pair<_Fp, _Alloc> __f_;
// いろいろ

_FFの定義を再掲し、ついでに__funcの定義も冒頭だけ載せました

__funcの定義を見てみると、これは__baseクラスを継承していることがわかります

template<class _Fp> class __base;

template<class _Rp, class ..._ArgTypes>
class __base<_Rp(_ArgTypes...)>
{
// いろいろ

どうやら__funcクラスには実際に保持するオブジェクトが__compressed_pair::__first_に保持されていて、この__funcクラスを__baseのポインターである__f_に代入することで保持するオブジェクトの型を隠蔽する(=Type Erasure)みたいです

そうすると__f_から保持したオブジェクトにアクセスできないじゃん!!となりそうですが、関数呼び出しを行うoperator()をオーバーライドすることで、__f_->operator()によって__func::operator()を呼び出すことができ、そこから保持したオブジェクトの呼び出しができるようです、うまいですね

関数呼び出し

template<class _Rp, class ..._ArgTypes>
_Rp
function<_Rp(_ArgTypes...)>::operator()(_ArgTypes... __arg) const
{
    if (__f_ == 0)
        throw bad_function_call();
    return (*__f_)(forward<_ArgTypes>(__arg)...);
}

__base型である__f_のoperator()を実行していますが、コンストラクタの項でも言ったように、実際には__func::operator()が呼び出されます

operator()の引数のforward関数は、よく完全転送*12で用いられますが今回はそれとは別です


d.hatena.ne.jp


まぁ要するに今回の場合「_ArgTypes」という型はあらかじめ決まっているのでユニバーサル参照とかとは違うよって話です(適当
ちなみにforward()...となっていますが、これは可変引数テンプレートの拡張というものです(今更


次に__func::operator()を見てみましょう

template<class _Fp, class _Alloc, class _Rp, class ..._ArgTypes>
_Rp
__func<_Fp, _Alloc, _Rp(_ArgTypes...)>::operator()(_ArgTypes&& ... __arg)
{
    typedef __invoke_void_return_wrapper<_Rp> _Invoker;
    return _Invoker::__call(__f_.first(),forward<_ArgTypes>(__arg)...);
}

__f_というのは__funcクラスの__compressed_pairというメンバ変数*13で、__f_.first()には保持しているオブジェクトが入っています
関数呼び出しをするオブジェクトなのに__call関数の第1引数に渡していて「あれ??」となりますが、先に__invoke_void_return_wrapperを見てみます

template <class _Ret>
struct __invoke_void_return_wrapper
{
    template <class ..._Args>
    static _Ret __call(_Args&&... __args) {
        return __invoke(forward<_Args>(__args)...);
    }
};

template <>
struct __invoke_void_return_wrapper<void>
{
    template <class ..._Args>
    static void __call(_Args&&... __args) {
        __invoke(forward<_Args>(__args)...);
    }
};

返り値がvoid型かそうでないかでreturnを用いるかどうか分けているようです
これ場合分けする必要あるのかな??と思いましたが、どうやら一部のコンパイラだと場合分けしないといけないみたいですね

ちなみにめちゃくちゃわかりにくいですが、ここで出てくるforward関数は完全転送のためのものです*14

INVOKE

さて、ようやくここまで来たって感じですが、__invoke関数が実際に関数を呼び出している部分になります
ダンジョン最深部感ありますね(ない

// bullets 1 and 2

template <class _Fp, class _A0, class ..._Args,
            class>
auto
__invoke(_Fp&& __f, _A0&& __a0, _Args&& ...__args)
    -> decltype((forward<_A0>(__a0).*__f)(forward<_Args>(__args)...))
{
    return (forward<_A0>(__a0).*__f)(forward<_Args>(__args)...);
}

template <class _Fp, class _A0, class ..._Args,
            class>
auto
__invoke(_Fp&& __f, _A0&& __a0, _Args&& ...__args)
    -> decltype(((*forward<_A0>(__a0)).*__f)(forward<_Args>(__args)...))
{
    return ((*forward<_A0>(__a0)).*__f)(forward<_Args>(__args)...);
}

// bullets 3 and 4

template <class _Fp, class _A0,
            class>
auto
__invoke(_Fp&& __f, _A0&& __a0)
    -> decltype(forward<_A0>(__a0).*__f)
{
    return forward<_A0>(__a0).*__f;
}

template <class _Fp, class _A0,
            class>
auto
__invoke(_Fp&& __f, _A0&& __a0)
    -> decltype((*forward<_A0>(__a0)).*__f)
{
    return (*forward<_A0>(__a0)).*__f;
}

// bullet 5

template <class _Fp, class ..._Args>
auto
__invoke(_Fp&& __f, _Args&& ...__args)
    -> decltype(forward<_Fp>(__f)(forward<_Args>(__args)...))
{
    return forward<_Fp>(__f)(forward<_Args>(__args)...);
}

decltypeというのは式の型を取得する機能で、返り値をautoにしといて「-> decltype(式)」とすることで式の型を返り値の型にすることができます

上のコードではdecltypeの中身は全てreturn文で評価する式と同じなので、これとSFINAEを利用することで式が成立しうる__invoke関数を実行することができるというカラクリです
例えばstd::functionにラムダ式を代入した場合は//bullet 5の__invokeが呼ばれます


唐突ですが、std::functionでは様々なものを保持できますが、これには厳格な決まりがあります
C++14の規格によると、

20.9.11.2.4 function invocation
R operator()(ArgTypes... args) const
Effects: INVOKE(f, std::forward(args)..., R) (20.9.2), where f is the target object (20.9.1) of *this.
Returns: Nothing if R is void, otherwise the return value of INVOKE (f, std::forward( args)..., R).
Throws: bad_function_call if !*this; otherwise, any exception thrown by the wrapped callable object.

とあります
実はこのEffectsに書いてあるINVOKEという関数が__invokeの正体なわけですね*15
INVOKEについては、

Define INVOKE (f, t1, t2, ..., tN) as follows:
(1.1)— (t1.*f)(t2, ..., tN) when f is a pointer to a member function of a class T and t1 is an object of type T or a reference to an object of type T or a reference to an object of a type derived from T;
(1.2)— ((*t1).*f)(t2, ..., tN) when f is a pointer to a member function of a class T and t1 is not one of the types described in the previous item;
(1.3)— t1.*f when N == 1and f is a pointer to member data of a class T and t1 is an object of type T or a reference to an object of type T or a reference to an object of a type derived from T;
(1.4)— (*t1).*f when N == 1 and f is a pointer to member data of a class T and t1 is not one of the types described in the previous item;
(1.5)— f(t1, t2, ..., tN) in all other cases.

と書いてあり、これが__invoke関数の各種実装に相当していたということです


以上のような流れで関数呼び出しが行われます

まとめ

  1. テンプレートの部分特殊化によってfunction<返り値の型(引数1の型, 引数2の型,...)>と書けるようにする
  2. __baseから__funcを継承させることでType Erasureを実現
  3. unique_ptrでメモリの動的確保
  4. std::functionで保持するオブジェクトはINVOKEコンセプトに従うもの

今回はstd::functionを読んでみましたが、思ったよりちょうどいい長さで学べることもあったので良かったです(小学生並みの感想
文章におこすのめっちゃ疲れますね

*1:libc++の実装です

*2:【C++】色々な関数オブジェクト【ラムダ ファンクタ 関数ポインタ】 | MaryCore

*3:関数呼び出し演算子っていうんですかね

*4:一応条件はあるっぽい

*5:unary_functionとbinary_functionについては触れません

*6:std::stringやstd::vectorなどいろんなところで使われているみたいです

*7:operator=は中でfunctionを作成してスワップしているのでとばす、また、C++17でアロケータのサポートはしなくなるのでアロケータは指定しないで進めます

*8:__callableは結構内容が多かったので省きます

*9:参考になるかもしれないリンク:23589 – std::function doesn't recognize null pointer to varargs function, rL245335

*10:かつコピー可能でコピーコンストラクタが例外を投げない

*11:詳しくは右辺値参照の記事を見てください

*12:Perfect Forwardって言い方もかっこいい

*13:名前が被っててややこしい

*14:引数がユニバーサル参照になっているかとかで見分けやすい

*15:C++17ではINVOKEコンセプトに従うinvoke関数が追加されました