functional 标准及 libcxx 实现. Part1 – 算数函数及基础设施

前言。。。

因为实在太长所以还是分几部分写吧。重中之重当然是 std::bind. std::function 其实实现不很难,就是体积大。

这篇主要说的是基础设施,包括最基本的定义和到处被用到的函数。

另因为 形如 template <Args...> struct {}; 的 和 形如 Ret(Args...) 的,前者是元编程里的元函数,后者是通常说法里的函数,下面可能统统会被叫做 函数,不作区分。

下面会从 标准对 functional 的定义,clang 对 functional 的实现 两方面做阐述。

大图片:

functional 里主要包括两大主要设施以及两个小块。
两大设施:std::bindstd::function.
两小块:各种 hash 以及各种运算符的函数格式(比如 + 对应 plus 什么的)。与之相关的是 deprecated 的 binary_functionunary_function. 。
在 clang 里,functional 主要包含了 type_traits__functional_base 两个头文件,阅读源码的时候也需要重点关注。另用到了 tuple 的一些设施。

其中使用了挺多元编程技巧以及各种 move,转发,感觉还是很有意思的。

话说之前很土地一直以为 std::bind 是 boost::mpl 里的那个 bind, 结果被砍爷糊了一脸。。。

然后 mem_fn 什么的不打算填坑了。

各类运算符映射函数:

这类函数包括:

###运算函数:
plus, minus, multiplies negate
###比较类函数:
equal_to, greater, less_equal
###逻辑比较:
logical_and, logical_or…,
位运算:
bit_and, bit_xor … 等。

挑一个典型:

    #if _LIBCPP_STD_VER > 11
    template < class _Tp = void >
    #else
    template < class _Tp>
    #endif
    struct _LIBCPP_TYPE_VIS_ONLY plus : binary_function<_Tp , _Tp, _Tp>
    {
        _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
        _Tp operator()(const _Tp& __x, const _Tp& __y) const
            {return __x + __y;}
    };

    #if _LIBCPP_STD_VER > 11
    template <>
    struct _LIBCPP_TYPE_VIS_ONLY plus<void>
    {
        template <class _T1 , class _T2>
        _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
        auto operator()(_T1&& __t , _T2&& __u) const
            { return _VSTD::forward <_T1>( __t) + _VSTD:: forward<_T2 >(__u); }
        typedef void is_transparent;
    };
    #endif

struct plus { }; 继承自 binary_function.
binary_function 定义了 first_argument_type, second_argument_type 以及 result_type. std::plus 需要这三种类型。
实现很简单,就是 l+r, 但为啥会有 plus<Tp>plus<void> 两种呢?
因为后者能自动 deduce 传入参数的类型。并且,可以看到 plus<Tp> 用了 const T&,而 plus<void> 使用了 perfect forwarding.
这里的 _VSTD 就是 std,长成这幅熊样是为了和 MSVC 的 _STD 做区分。
注意到 C++ 11 以后返回值就用 constexpr 修饰了,以方便编译器优化。

plus<void> 同时定义了 is_transparent. 这个东西告诉调用者,我这个函数接收任意类型作为输入,并且使用 perfect forwarding 来避免无意义的拷贝和转换。


各种定义:

见 ISO-14882 2011(下面的引用都是说 ISO2011) / 20.8.1

###定义:

  • function object type: 是一种可以作为 function call 前缀的 object type (比如 functor, reference to function, pointer to function 等)

    这一条包括下一条都在 20.8, 1

  • function object: 是 function object type 的 object. 绕口啊。

    注意 type 和 object 的区别:前者不给分配空间(没有肉身)。后者会占据空间(有一片肉身)

  • call signature: 返回值类型 加 括号包围,逗号分隔的参数类型列表。比如 void(int, int)

  • callable type: function object type(见前面 function object type 定义) 或者 pointer to member (成员指针,包括 pointer to member function 和 pointer to member object)
  • callable object: an object of callable type.
  • call wrapper type: hold 一个 callable object,支持用 call operator 调用那个 callable object.
  • call wrapper: 是 call wrapper type 的 object.
  • target object: 是被 call wrapper hold 的 callable object.

实现:

下面把 clang 里对应的 callable type 实现弄出来:
clang 里,用 std::__function::__base 代表 callable type, 而 std::__function::__func 则是其唯一实现类

__base

__base 模拟可以被调用的类型(callable type)。这是个纯虚类,要求子类实现 __clone(), clone(__base*) destroy() destroy_dellocate() 以及 operator()(Args...) 几个函数,以及把拷贝给禁了。

    // in header <functional>
    namespace __function
    {
        ...
        template<class _Rp, class ..._ArgTypes>
        class __base<_Rp(_ArgTypes...)>
        {
            __base(const __base&);
            __base& operator=(const __base&);
        public:
            _LIBCPP_INLINE_VISIBILITY __base() {}
            _LIBCPP_INLINE_VISIBILITY virtual ~__base() {}
            virtual __base* __clone() const = 0;
            virtual void __clone(__base*) const = 0;
            virtual void destroy() _NOEXCEPT = 0;
            virtual void destroy_deallocate() _NOEXCEPT = 0;
            virtual _Rp operator()(_ArgTypes&& ...) = 0;
        #ifndef _LIBCPP_NO_RTTI
            virtual const void* target(const type_info&) const _NOEXCEPT = 0;
            virtual const std::type_info& target_type() const _NOEXCEPT = 0;
        #endif  // _LIBCPP_NO_RTTI
        };
    }

__func

__func 继承自 __base. 是 base 的唯一实现(因此可以推断 __func 是 callable object 的实现),其有唯一成员 compressed_pair<Fp, _Alloc> __f_, compressed_pair 用来做 Tp1 和 Tp2 中有空基类时的空基类优化,目前没进标准。据说会进的。

它提供了函数的复制功能。
定义如下

    template<class _Fp, class _Alloc, class _Rp , class ..._ArgTypes>
    class __func<_Fp, _Alloc , _Rp( _ArgTypes...)>
````
可以看到有 Function Pointer, Alloc, Return_Type, ArgTypes 四个参数

构造针对 Fp 和 Alloc 是否可被拷贝提供了多种多样的版本. 一个样例是:
```cxx
    _LIBCPP_INLINE_VISIBILITY
    explicit __func (_Fp&& __f, _Alloc && __a)
        : __f_( piecewise_construct, _VSTD::forward_as_tuple(_VSTD::move (__f)),
                                    _VSTD::forward_as_tuple(_VSTD::move (__a))) {}

其他版本是 _Fp&&, const _Fp&_Alloc&&, const _Alloc& 的组合,一共四组。

其中 __f_ 的定义是 __compressed_pair<_Fp, _Alloc> __f_

__clone 的代码很有意思:

    template<class _Fp, class _Alloc, class _Rp , class ..._ArgTypes>
    __base<_Rp (_ArgTypes...)>*
    __func<_Fp , _Alloc, _Rp(_ArgTypes ...)>::__clone() const
    {
        typedef typename _Alloc::template rebind<__func>::other _Ap ;
        _Ap __a(__f_ .second());
        typedef __allocator_destructor <_Ap> _Dp;
        unique_ptr<__func , _Dp> __hold(__a .allocate(1), _Dp (__a, 1 ));
        ::new (__hold .get()) __func(__f_ .first(), _Alloc(__a ));
        return __hold .release();
    }

首先拿到 Alloc<__func> 的类型(rebind)。

构造一个 allocator, 并拿到相应的 dellocator

unique_ptr 申请空间,用 placement new 分配空间。这样的做法的原因是:

unique_ptr 提供了 exception save 的 resource handling,使得 __func 在构造的时候抛出异常不会造成资源泄露。
接着让 unique_ptr 释放资源,返回纯指针。


然后是基础的基础:传说中的 INVOKE:

INVOKE

###定义:

20.8.2, 1, 2

  • 定义 INVOKE(f, t1, t2, ... , tN) 如下:
    1. (t1.*f)(t2, ..., tN): 如果 f 是指向 T 的成员函数的指针,且 t1 是 T 类型的 object,或对 T 类型的 object 的引用,或 T 的子类的 object 的引用
    2. (*t1.*f)(t2, ..., tN): 如果 f 是指向 T 的成员函数的指针,且 t1 的类型不符合上述描述。
    3. t1.*f: 当 N == 1, f 是指向 T 的成员变量的指针,且 t1 是 T 类型的 object,或对 T 类型的 object 的引用,或 T 的子类的 object 的引用
    4. t1.*f: 当 N == 1, f 是指向 T 的成员变量的指针,且 t1 的类型不符合上述描述。
    5. f(t1, t2, ... tN): 所有其他情况。
  • 定义 INVOKE(f, t1, t2, ..., tN, R) 为隐式转换 INVOKE(f, t1,... tN) 的返回值类型到 R。

###实现:
INVOKE 的声明在 <type_trait> 头文件,而定义定义在 __functional_base (恕我直接无视 03 …

bullet 1 ~ 5

这里一一对应地实现上面定义的 INVOKE 五兄弟。
比方拣出第一个看看:

    template <class _Fp, class _A0, class ..._Args,
                class = typename enable_if
                <
                    is_member_function_pointer<typename remove_reference<_Fp>::type>::value &&
                    is_base_of<typename remove_reference<typename __member_pointer_traits<typename remove_reference<_Fp>::type>::_ClassType>::type,
                               typename remove_reference<_A0>::type>::value
                >::type
             >
    _LIBCPP_INLINE_VISIBILITY
    auto
    __invoke(_Fp&& __f, _A0&& __a0, _Args&& ...__args)
        -> decltype((_VSTD::forward<_A0>(__a0).*__f)(_VSTD::forward<_Args>(__args)...));

这是声明。看到它的参数:<_Fp, _A0, ... Args, condition>
回来看一下标准怎么说的:

(t1.*f)(t2, ..., tN): 如果 f 是指向 T 的 成员函数的指针 ,且 t1 是 T 类型的 object,或对 T 类型的 object 的引用,或 T 的子类的 object 的引用

所以 Fp 对应 f, A0 对应 t1, Args… 对应 t2, …, tN
看一下 Condition 怎么写的:
enable_if< 条件, 省略 >,
我们知道 enable_if 后一个参数省略的话默认是 void. 省略的意思就是,这里是什么类型不重要。

条件呢:

  • Fp 被 remove_referenceis_member_function_pointer
    is_member_function_pointer<typename remove_reference<_Fp>::type>::value
    
  • Fp 经过总总操作后得到的其 ClassType 的类型是 A0 经过 remove_reference 等等操作后的 base class
    is_base_of<typename remove_reference<
        typename __member_pointer_traits<
           typename remove_reference<_Fp>::type>::_ClassType
        >::type,
        typename remove_reference<_A0>::type
    >::value
    

如果这两个条件符合,则 enable_if 有效,该函数对参数 Fp, A0, ... Args 有声名。否则,根据 SFINAE, 该函数对这组类型没有定义。
看到它返回值用的是 auto f() ->ret_type() 声明的。

想起来 is_base_of 的实现很巧妙, 可以去围观一下。记得 modern C++ design 里有提到过。

        -> decltype((_VSTD::forward<_A0>(__a0).*__f)(_VSTD::forward<_Args>(__args)...));

这里一路 forward.
函数定义在 __functional_base
参数是:

    template <class _Fp, class _A0, class ..._Args,
                class>

最后一个参数因为是 void (enable_if 的 guard), 所以被丢掉了,只剩一个 class 孤零零地表示存在感

函数体如下:

    return (_VSTD::forward<_A0>(__a0).*__f)(_VSTD::forward<_Args>(__args)...);

这样 bullet 1 就弄完了。bullet 4 ~ 5 都差不多。不废话了。

fallback

如果上述五个 bullet 都不符合,那就 fallback 到这个定义上,返回 __nat. not a type, 以警示后人。

    // fall back - none of the bullets

    template <class ..._Args>
    auto
    __invoke(__any, _Args&& ...__args)
        -> __nat;

weak_result_type:

20.8.2, 3

这是一个帮助确定函数返回值的类。

  • 如果 T 是一个指向函数类型的指针,result_type 就是 T 的返回值类型
  • 如果 T 是一个指向成员函数的指针,result_type 就是 T 的返回值类型
  • 如果 T 是一个含有成员类型 result_type 的类,result_type 就是 T::result_type 的类型
  • 其他情况下 result_type 都不应该被定义。

clang 里的实现没啥好说的,不断特化就是了。讲一下里面一个技巧。

weak_result_type 的主模板继承自 weak_result_type_imp

    template <class _Tp, bool = __has_result_type<_Tp>::value>
    struct __weak_result_type_imp // bool is true
        : public __maybe_derive_from_unary_function<_Tp>,
          public __maybe_derive_from_binary_function<_Tp>
    {
        typedef typename _Tp::result_type result_type;
    };

    template <class _Tp>
    struct __weak_result_type_imp<_Tp, false>
        : public __maybe_derive_from_unary_function<_Tp>,
          public __maybe_derive_from_binary_function<_Tp>
    {
    };

看到如果后面的 bool 是 true, 说明 derive_from binary or unary 函数,这样就直接把它们的 result_type 拿来用。否则啥都不定义。

在元编程里这样的空基类继承技巧用得很多,反正空基类都会被优化掉。

这里的 __maybe_derive_from_xxx 的实现也是:

    template <class _Tp, bool = __derives_from_binary_function<_Tp>::value>
    struct __maybe_derive_from_binary_function  // bool is true
        : public __derives_from_binary_function<_Tp>::type
    {
    };

    template <class _Tp>
    struct __maybe_derive_from_binary_function<_Tp, false>
    {
    };

如果 继承自 xxx_function 是 true, 那么继承它,否则不继承它。


call wrapper

20.8.4

call wrapper 必须是 MoveConstrutible.
一个 simple call wrapper 是一个 CopyConstrutible, CopyAssignable, 且 copy-ctor, move-ctor, assignment operator 都不掷出异常的 call wrapper
一个 forwarding call wrapper 是一个可以被任意参数列表调用,并将所有参数以引用方式传给 wrapped callable objectcall wrapper. 这样的传递必须保证左值按左值传,右值按右值传。所谓 call wrapper 嘛, std::function<> 啊,std::bind<> 的返回值啊,都是 call wrapper.

reference_wrapper:

20.8.3

ref< T >
cref< T > 的返回值类型就是它了。

###定义
要定义
“`cxx
typedef T type;
typedef * result_type
typedef * argument_type;
typedef * first_argument_type;
typedef * second_argument_type;

* 不启用 move_ctor , `reference_wrapper(T&&) = delete`;
*  `reference_wrapper<T>` 是 CopyAssignable 的外覆器,外覆一个对象或者函数的引用。
* `reference_wrapper` 是一个 `weak_result_type`
* 如果 T 满足某些条件,要定义 `result_type`, `argument_type` 或 `first_argument_type` 和 `second_argument_type`.

其他的拷贝复制啊 const 拷贝复制啊赋值啊都不说了,还有做 access T 的也不说了,
`reference_wrapper` 里主要的功能函数是 operator().
```cxx
    template <class... ArgTypes>
    typename result_of<T&(ArgTypes&&... )>::type
    operator()(ArgTypes&&... args) const;

返回 INVOKE(get(), std::forward<ArgTypes>(args)...).

实现

大家都是来看 __invoke 的:

    // invoke
    template <class... _ArgTypes>
       _LIBCPP_INLINE_VISIBILITY
       typename __invoke_of<type&, _ArgTypes...>::type
          operator() (_ArgTypes&&... __args) const
          {
              return __invoke(get(), _VSTD::forward<_ArgTypes>(__args)...);
          }

这里的 __invoke_of 是作者的得意之作,

revision 13639 里作者如是说: __invoke_of is carefully crafted so that it can serve as its own enable_if

用人话说,就是 __invoke_of subsitude failed 的话会把整个用它的 函数/类 干掉。 真是一个很可怕的坑啊。。。

实现:
先看 invokable, 待会要用它

    // __invokable

    template <class _Fp, class ..._Args>
    struct __invokable_imp
        : private __check_complete<_Fp>
    {
        typedef decltype(
                __invoke(_VSTD::declval<_Fp>(), _VSTD::declval<_Args>()...)
                        ) type;
        static const bool value = !is_same<type, __nat>::value;
    };

    template <class _Fp, class ..._Args>
    struct __invokable
        : public integral_constant<bool,
              __invokable_imp<_Fp, _Args...>::value>
    {
    };

很简单,如果 __invokable_imp::value 是 true, 那么它返回 true (通过从 integral_constant 继承而来。否则返回 false.)

__invokable_imp 用的技巧是:取得 decltype(_invoke(args...)), 然后判断它的返回值是不是 __nat. 请注意这些都是在编译期完成的。

check_complete 确认 Fp 是不是个 complete type, 不是就丢 static_assert;

非要加个 invokable_impl 包装一下是怕 ::type 返回值污染后续元函数。

总结一下,invokable 在 INVOKE 有定义的时候是 true. 这里又能证明 INVOKE 到底有多重要了。

    // __invoke_of

    template <bool _Invokable, class _Fp, class ..._Args>
    struct __invoke_of_imp  // false
    {
    };

    template <class _Fp, class ..._Args>
    struct __invoke_of_imp<true, _Fp, _Args...>
    {
        typedef typename __invokable_imp<_Fp, _Args...>::type type;
    };

    template <class _Fp, class ..._Args>
    struct __invoke_of
        : public __invoke_of_imp<__invokable<_Fp, _Args...>::value, _Fp, _Args...>
    {
    };

看一下 invoke_of. 继承自 : invoke_of_impl<bool invokable, Args...>
如果 not invokable, 那么 invoke_of 里没有 ::type 的定义。那么往后所有对 invoke_of::type 的引用都会导致模板推导失败。

如果 invokable, 那返回值 type 是 invokable_impl::type

Leave a Reply

Your email address will not be published. Required fields are marked *