3. exectuions 依赖的管道实现 - 在C++中实现LINQ
3. exectuions 依赖的管道实现 - 在C++中实现LINQ
1. 前言
在正式分析libunifex之前, 我们需要了解一部分它依赖的基础机制, 方便我们更容易的理解它的实现. 本篇介绍的主要内容是关于c++ linq的, 可能很多读者对c++的linq实现会比较陌生, 但说到C#的linq, 大家可能马上就能对应上了. 没错, c++的linq就是在c++下实现类似C# linq的机制, 本身其实就是在定义一个特殊的DSL, 相关的机制已经被使用在c++20的ranges库, 以及不知道何时会正式推出的execution库中, 作为它们实现的基础之一. 本篇我们主要围绕已进入标准的ranges实现来展开关于c++ linq的探讨, 同时也将以ranges的一段代码为起点, 逐步展开本篇的相关内容.
2. 从ranges示例说起
ranges是c++20新增的特性, 很好的弥补了c++容器和迭代器实现相对其他语言的不便性. 它的使用并不复杂, 我们先来看一个具体的例子:
auto const ints = { 0, 1, 2, 3, 4, 5 };
auto even_func = [](int i) { return i % 2 == 0; };
auto square_func = [](int i) { return i * i; };
auto tmpv = ints
| std::views::filter(even_func)
| std::views::transform(square_func);
for (int i : tmpv) {
std::cout << i << ' ';
}初次接触, 相信很多人都会疑惑: - 这是如何实现的? - c++里也能有LINQ? - 为什么这种表达虽然其他语言常见, 在c++里存在却显得有点格格不入?
从逻辑上来讲, 上述代码起到的是类似语法糖的效果, linq表达: ints | std::views::filter(even_func) | std::views::transform(square_func);
等价函数调用方式为: std::views::transform(std::views::filter(ints, event_func), square_func);
所以表面上来看, 它似乎是通过特殊的|操作符重载来规避掉了多层函数嵌套表达, 让代码有了更好的可读性, 表达更简洁了.
但这里的深层次的设计其实并没有那么简单, 这也是大家读ranges相关的文章, 会发现这 "语法糖" 居然还会带来额外的好处, 最终compiler生成的目标代码相当简洁. 这是为什么呢? 我们将在下一章中探讨这部分的实现机制.
3. 特殊的DSL实现
其实本质上来说, 这种实现很巧妙的利用了部分compiler time的特性, 最终在c++中实现了一个从 "代码 -> Compiler -> Runtime" 的一个DSL, 后续我们也介绍到, execution里也复用并发扬了这种机制. 我们先来看一下ranges这部分的机制: 1. DSL定义(BNF组成) - 首先是范式的组成, ranges的linq用到的范式比较简单, 我们可以认为, 它是由Ranges Pipeline ::= Data Source { '|' Range Adapter } '|' Range Adapter 组成的. 2. Compiler(Pipeline操作) - ranges实现里我们可以认为|运算的过程就是编译过程. 3. Execute - 具体的iterator过程, ranges里一般就是 std::ranges::begin(), std::ranges::end(), 以及iterator本身所支持的++操作等.
这种设计本身带来的好处, 对比原始的容器和迭代器操作, Compiler部分和Execute过程被显示分离了, Compiler的时候, 并不会对Data Source做任何的访问和操作, 所有访问相关的操作其实是后续Execute过程再发生的(Lazy特性).
另外, 因为Compiler过程本身是结合comipler time特性来处理的, 这样DSL本身在这个阶段是类型完备的, 一方面compiler过程本身就能完成一些常规的类型匹配问题检查等操作, 另外我们也能在该阶段在类型完备的情况下更好的处理相关逻辑.
大量使用compiler time特性带来的额外好处是原始的std容器和迭代器很多在运行时进行处理的操作, 都可以在编译期完成, 编译器会生成比原来运行效率高效很多的代码.
像这种设计精巧, 系统性完备, 优势又很明显的机制, 必然会得到发扬光大. 所以我们会看到, ranges库本身使用了相关机制, 到几经迭代尚未正式推出的execution库, 都已经拥抱了这种设计, 将其作为自己基础的一部分, 作为sender/receivers机制的基石, 相关的实现也被越来越多的c++ coder所认可.
本篇我们还是回到ranges本身, 先关注Compiler部分也就是Pipeline机制实现的细节, 以微软官方的ranges实现为例, 来 详细了解一下它的实现机制.
4. pipeline机制浅析
4.1 Pipe实现相关的concept:
4.1.1 _Pipe::_Can_pipe
namespace _Pipe {
template <class _Left, class _Right>
concept _Can_pipe = requires(_Left&& __l, _Right&& __r) {
static_cast<_Right&&>(__r)(static_cast<_Left&&>(__l));
};
}这个concept比较简洁, 能够组织成pipe的对象, 以
auto pipe = l | r;为例 , 能够以 r(l)的形式调用的两个对象, 即可满足pipe约束.
4.1.2 _Can_compose
namespace _Pipe {
template <class _Left, class _Right>
concept _Can_compose = constructible_from<remove_cvref_t<_Left>, _Left>
&& constructible_from<remove_cvref_t<_Right>, _Right>;
}这个主要是因为lazy evaluate的过程中, 我们可能需要在中间对象中(如下文中的_Pipeline对象), 对_Left和_Right进行存储, 所以需要它们是可构建的.
4.2 Pipe实现相关的类
4.2.1 struct _Base<class _Derived> 类
相关源代码如下:
namespace _Pipe {
template <class, class>
struct _Pipeline;
template <class _Derived>
struct _Base {
template <class _Other>
constexpr auto operator|(_Base<_Other>&& __r) && {
return _Pipeline{static_cast<_Derived&&>(*this), static_cast<_Other&&>(__r)};
}
template <class _Other>
constexpr auto operator|(const _Base<_Other>& __r) && {
return _Pipeline{static_cast<_Derived&&>(*this), static_cast<const _Other&>(__r)};
}
template <class _Other>
constexpr auto operator|(_Base<_Other>&& __r) const& {
return _Pipeline{static_cast<const _Derived&>(*this), static_cast<_Other&&>(__r)};
}
template <class _Other>
constexpr auto operator|(const _Base<_Other>& __r) const& {
return _Pipeline{static_cast<const _Derived&>(*this), static_cast<const _Other&>(__r)};
}
template <_Can_pipe<const _Derived&> _Left>
friend constexpr auto operator|(_Left&& __l, const _Base& __r)
{
return static_cast<const _Derived&>(__r)(_STD forward<_Left>(__l));
}
template <_Can_pipe<_Derived> _Left>
friend constexpr auto operator|(_Left&& __l, _Base&& __r)
{
return static_cast<_Derived&&>(__r)(_STD forward<_Left>(__l));
}
};
}以微软版range库的实现为例, 各个range adapter - 如std::views::filter, std::views::transform 等都继承自_Base类, _Base类主要完成以下两个功能: 1. 完成对其它_Base类的管道操作 2. 通过友元和模板来完成对其它类的管道操作(自己作为右操作数) 具体的重载不再具体展开了, 主要是不同_Right类型的差异处理, 可自行参阅相关代码.
4.2.2 struct _Pipeline<class _Left, class _Right> 类
相关代码如下:
template <class _Left, class _Right>
struct _Pipeline : _Base<_Pipeline<_Left, _Right>> {
_Left __l;
_Right __r;
template <class _Ty1, class _Ty2>
constexpr explicit _Pipeline(_Ty1&& _Val1, _Ty2&& _Val2)
: __l(std::forward<_Ty1>(_Val1))
, __r(std::forward<_Ty2>(_Val2)) {
}
template <class _Ty>
constexpr auto operator()(_Ty&& _Val)
requires requires {
__r(__l(static_cast<_Ty&&>(_Val)));
}
{ return __r(__l(_STD forward<_Ty>(_Val))); }
template <class _Ty>
constexpr auto operator()(_Ty&& _Val) const
requires requires {
__r(__l(static_cast<_Ty&&>(_Val)));
}
{ return __r(__l(std::forward<_Ty>(_Val))); }
};
template <class _Ty1, class _Ty2>
_Pipeline(_Ty1, _Ty2) -> _Pipeline<_Ty1, _Ty2>;_Pipeline主要用于将两个range adapter进行复合的情况 , 比如下面的情况:
auto v = std::views::filter(even_func) | std::views::transform(square_func);这个时候我们会构建 _Pipeline 对象, 区别于这种情况则是不依赖中间 _Pipeline对象, 比如下面的情况:
auto ints = {1, 2, 3, 4, 5};
auto v = ints | std::views::filter(even_func);这种情况 , 我们就不需要依赖_Pipeline对象, 直接触发的是_Pipe这个版本的operator|重载:
template <_Can_pipe<_Derived> _Left>
friend constexpr auto operator|(_Left&& __l, _Base&& __r)
{
return static_cast<_Derived&&>(__r)(_STD forward<_Left>(__l));
}std::views::filter本身是一个CPO closure对象, 不理解CPO没关系, 下篇中将进行具体介绍, 我们可以先将它简单理解成一个带up value的函数对象, 上例中的even_func被携带到了一个std::views::filter CPO对象中, 然后我们可以以 filter_cpo(ints) 的方式来产生一个预期的views, cpo的这个特性倒是跟其他语言的closure特性基本一致, 除了C++的CPO对象比较Hack, 使用形式不如其他语言简洁外.
额外需要关注的一点是:
template <class _Ty1, class _Ty2>
_Pipeline(_Ty1, _Ty2) -> _Pipeline<_Ty1, _Ty2>;这个是c++17添加的 Custom template argument deduction rules(或者 user-defined template argument deduction rules), 利用用户自行指定的推导规则, 我们可以使用简单的 _Pipeline(a, b)来替换_Pipeline<a, b>(), 以得到更简单的表达, 如_Base类中的使用一样:
_Pipeline{static_cast<const _Derived&>(*this), static_cast<_Other&&>(__r)};5. 总结
本篇中我们简单介绍了c++ linq, 以及ranges中相关机制的使用, 也侧重介绍了作为linq Compiler部分的Pipeline的具体实现. 但可能有细心的读者已经发现了, ranges中的各种range adapter - 如std::views::transform() 和std::views::filter()的实现, 好像跟自己之前见到的惯用的C++封装方式不太一样, 这也是我们下一篇中将介绍的内容, [[4. executions 依赖的定制机制 - 揭秘 cpo与tag_invoke!]], 下篇见~~