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 容器和迭代器实现相对其他语言的不便性. 它的使用并不复杂, 我们先来看一个具体的例子:

代码语言：javascript复制

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`

代码语言：javascript复制

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的对象, 以

代码语言：javascript复制

auto pipe = l | r;

为例 , 能够以 r(l)的形式调用的两个对象, 即可满足pipe约束.

4.1.2 `_Can_compose`

代码语言：javascript复制

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>` 类

4.2.2 `struct _Pipeline<class _Left, class _Right>` 类

相关代码如下:

代码语言：javascript复制

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进行复合的情况 , 比如下面的情况:

代码语言：javascript复制

auto v = std::views::filter(even_func) | std::views::transform(square_func);

这个时候我们会构建 _Pipeline 对象, 区别于这种情况则是不依赖中间 _Pipeline对象, 比如下面的情况:

代码语言：javascript复制

auto ints = {1, 2, 3, 4, 5};
auto v = ints | std::views::filter(even_func);

这种情况 , 我们就不需要依赖_Pipeline对象, 直接触发的是_Pipe这个版本的operator|重载:

代码语言：javascript复制

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, 使用形式不如其他语言简洁外.

额外需要关注的一点是:

代码语言：javascript复制

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类中的使用一样:

代码语言：javascript复制

_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!]], 下篇见~~

6. 参考

ranges - cppreference

c++ linq pipeline 对象设计

0 人点赞

3. exectuions 依赖的管道实现 - 在C++中实现LINQ

1. 前言

2. 从ranges示例说起

3. 特殊的DSL实现

4. pipeline机制浅析

4.1 Pipe实现相关的concept:

4.1.1 _Pipe::_Can_pipe

4.1.2 _Can_compose

4.2 Pipe实现相关的类

4.2.1 struct _Base<class _Derived> 类

4.2.2 struct _Pipeline<class _Left, class _Right> 类

5. 总结

6. 参考

4.1.1 `_Pipe::_Can_pipe`

4.1.2 `_Can_compose`

4.2.1 `struct _Base<class _Derived>` 类

4.2.2 `struct _Pipeline<class _Left, class _Right>` 类