为 ES2018 移植的 LINQ 方法

为 ES2018 移植的 LINQ 方法

源码:https://github.com/Martin1994/es2018-linq

NPM:https://www.npmjs.com/package/es2018-linq

前言

自我在短暂的金融业生涯中短暂地接触过 C# 之后,对 C# / .NET 的喜爱便一发不可收拾,即便从此之后的工作中再没机会使用 .NET 却依然保持着对其的关注,而这份关注与喜爱这也一直延续到了 Andre 老爷子如今的工作重心——TypeScript。

最近在工作中大量使用了 TypeScript,但却苦于没有合适的函数式编程工具箱。underscore/lodash 对异步方法的支持有限且不支持延迟执行;RxJS 又感觉太过重量级、强制异步,而 API 又自成一派。有 C# 背景的我自然是以 LINQ 对标这些库,所以我想要不干脆自己移植一份 LINQ 好了。

LINQ

有些朋友可能对 C# 或是 LINQ 不太了解,在这里做一下简单的介绍。

LINQ 最初是设计成在 C# 代码中可以用类似 SQL 的方式操作一个可迭代对象(Enumerable),可以是普通的本地数据结构,甚至也可以是封装好的数据库操作。例如这个官方提供的样例

然而据我的理解,真正在代码里用 LINQ 语句的人并不多……大多数情况 LINQ 是直接通过扩展方法调用的:

说到这里其实 LINQ 并没有什么稀奇。类似的 API 如今其实满大街都是。而真正让 LINQ 与众不同的原因(至少在当年)其实还有更多:

一方面 LINQ 是扩展方法。所谓扩展方法其实是一个很简单的语法糖——它能让一个静态方法像一个成员方法一样调用。比如上述例子中的 Where 其实是个静态方法,而其第一个参数是个 IEnumerable<T>。可实际代码中却可以直接 myEnumerable.Where(...) 这样调用。扩展方法顾名思义强在它的扩展性,如果 LINQ 的那些默认方法满足不了你,那完全可以自行扩展,而且与其他的 LINQ 方法无缝衔接。

说起无缝衔接就要提到第二个特点了,那便是 LINQ 没有侵入性。LINQ API 几乎都是将一个 IEnumerable<T> 转换成另一个 IEnumerable<T>,或是做了聚合之后返回一个单一的值。而 IEnumerable<T> 又是一个相当基础的接口,它代表了一个可遍历的集合,因而只要是个数据结构都能实现这个接口。类似的设计在其他 runtime 中也很常见,例如 Java 与 JavaScript 的 Iterable<T>,或是 C++ std 中能返回 std::iterator 的类型。

而第三个特点则和 LINQ 基于 IEnumerable<T> 有关,即延迟执行。举例而言,

这个例子中首先将原来数组中的数值都乘以 100,再找其中有没有小于 80 的值。因为实际上第三个值就满足条件,所以 Any 中的匿名函数只会执行三次。而真正重要的是, Select 中的匿名函数也只会被执行三次。通过这个特性可以非常非常方便地写出空间复杂度很优秀的代码,性能与可读性兼顾。不光是空间复杂度上的考量,举例而言如果作为数据源的 Enumerable<T> 来自于一个分页 API 的话,也可以非常优雅且高效地处理分页结果。

在 TypeScript / JavaScript 中实现 LINQ

前提条件

首先来看一下支持 LINQ 几个特色的基础功能在 TypeScript 与 JavaScript 中是否完备:

  • 扩展方法 —— JavaScript 可以通过操作原型链的方式自行加入新的方法,而 TypeScript 也可以对这种情况提供类型支持。
  • 异步支持 —— ES2015 起支持 Promise。ES2017 起支持 async/await。
  • IEnumerable<T> —— ES2015 起支持 Iterable。ES2018 起支持 AsyncIterable<T>。一并支持的还有能方便生成他们的 generator function( function*)。

而 JavaScript 的世界还有一个妙处——不要怕标准太新没人用,因为 transpiler 遍地开花,Babel 一架说不定连 IE6 都能让你跑起来。

如此来看在 TypeScript 与 JavaScript 中实现 LINQ 的前提条件都具备了。是时候动手了。

第一个实现:Select

Select 可以说是最简单直观的一个 LINQ method 了。Select 在很多函数式编程实现中被称为 map。JavaScript 中的 Array.prototype.map 也是同样的功能——当然, Array.prototype.map 并不能延迟执行,因为它返回一个数组。

想要做一些先期验证,Select 是个很好的选择。我们来看看 TypeScript / JavaScript 中的 LINQ 体验会是怎样的。

要在 TypeScript / JavaScript 中还原 C# 的这个例子,首当其冲的第一个障碍便是没有扩展方法,而这意味着我们并不能直接给一个接口定义方法。因此还是要首先将一个 Iterable<T> 包装在一个带有 LINQ 实现的类型才行。因此最终使用起来看上去会是这样:

考虑到最初 LINQ 那个类似 SQL 查询的用法,这个额外的 from() 方法可一点都不违和呢。当然这不是我想出来的点子,而是另一位在六年前给 ES2015 实现过 LINQ 的前辈的方案:https://github.com/balazsbotond/eslinq。

而剩下的实现就很简单了,只要借助 function* 就能很轻松地实现 Select 的功能。

这里插一句:考虑到 C# 有非常多针对 Enumerable 的优化,例如使用 struct 而非 class 实现 Enumerator<T>,C# 的 Enumerable<T> 遍历效率可以非常高而且对 GC 很友好。但我并不清楚主流的 JavaScript 引擎包括 v8 对这种场景的优化究竟如何。

为 Select 支持异步调用

异步分为两个使用情况:数据源就是异步的( AsyncIterable),以及作为函数的参数是异步的。

简单来说,只需要把上面的代码复制一遍稍作修改就能支持异步了:

异步,但是 DRY(Do not Repeat Yourself)!

上述的例子是可行没错,但是 LINQ(C# 的实现)一共有总计 56 个方法及 182 个重载,要如此维护两份几乎完全一样的实现是不现实的:实现工作量大、维护工作量大、甚至还会导致存在不一致的实现。

然而 TypeScript 又不像 C++ 有那么强的模板系统,因此只好利用代码生成了。

这里简单讲一下我的方案:实现一份完整的异步代码,然后通过 TypeScript 编译器 API 读取它的 AST(抽象语法树),再做一些预设的替换让它成为一份同步的实现。至于为什么不是反过来,那毕竟删除代码比插入代码要简单得多嘛……

举例而言,如果要剔除掉所有的 await(包括 await 表达式和 for await),大致代码会是这样:

生成 wrapper method

在 Select 的例子中,Select 的实现在一个私有方法 selectImpl 中,而又有另一个公有方法 select 将其返回的 Iterable<T> 转换成拥有 LINQ method 的 Enumerable<T>(不然就不能链式调用啦)。考虑到大多数 LINQ method 都是返回 Enumerable<T> 的,这种 wrapper method 最终一定会到处都是……秉承着 DRY 的原则,另一方面也因为反正都用 TypeScript 编译器 API 做代码生成了,不如把那些 wrapper method 一并生成了。

代码生成本身的思路很简单,就只举例说明了。源代码中的实现模板会是这样:

代码生成后就会生成一份同步一份异步的代码,其中同步的代码就会长这样:

当然了……具体实现的时候还是会遇到很多零碎的情况需要处理:比如如何识别哪些方法需要生成 wrapper method 而哪些不要、如何处理 TypeScript 的函数重载签名、如何保证模板代码本身也是合法的 TypeScript 代码。这里就不一一展开了,具体情况还是请参考源代码。

泛型特化:Average、Min、Max 及 Sum 的实现

在 C# 的 LINQ 方法中,有四个非常特殊的方法:Average、Min、Max 和 Sum。它们的特点是都只能对数值类型的 IEnumerable<T> 进行操作。这在 C# 中并不是一个问题,因为 LINQ method 本身就是扩展方法,只要只给数值类型的 IEnumerable<T> 定义方法就行了。然而在这个给 TypeScript 的实现中,所有方法都是类方法,而只给某些泛型类型实现某些方法并不是一个被正式支持的功能。

在纯 JavaScript 的语境下这并不是一个问题,因为 JavaScript 并没有任何泛型信息,更不保证任何编译时的类型检查(压根没有编译时好吗)。因此只要保证 TypeScript 的类型正确就行了。

我最终采用的思路是给这些方法引入一个额外参数,利用 TypeScript 条件类型让这个参数在数值类型下变成可选参数,而在其他情况下参数类型为 never——一个没有任何实参可以满足其类型的必要参数。例如最终 Average 的签名是这样:

其中那个 DO_NOT_ASSIGN 就是魔法的本质。对于数值类型而言,它的类型是 void,也就意味着这个参数将变成可选参数。而在其他情况下它的类型是 never,而 never 是 TypeScript 类型系统中的 bottom type,在 OOP 语境中相当于它是任何类型的子类,也就是一个 never 类型的变量不能被赋予任何的值。

当然要想蓄意破坏还是可以的……

目标:100% 测试覆盖率

由于同时有同步和异步两份实现的关系,测试的重复性会很高。因此绝大多数的测试用例都是自动覆盖全部同步、异步的情况的。例如:

自定义扩展

TypeScript 自身的 Module Argumentation 就很够用了。

目前缺失的部分

有一些方法和重载,诸如 Cast,由于 TypeScript / JavaScript 中缺失相应的功能,就不打算实现了。

另外一些集合相关的操作,例如 Union,目前并不支持自定义的 comparer,因为 JavaScript 自带的 Set 实现并不支持 comparer。这块根据反馈可能会以后慢慢加。

还有一些缺失的重载则是由于重载起来实在过于复杂,尤其是一些参数顺序完全打乱的重载,因为 TypeScript 层面的重载仅仅是做类型标记,而 JavaScript 层面的重载则要在运行时手动检查参数类型。

后记

TypeScript 编译器 API 的官方文档几乎没有,要想利用一些没用过的功能就必须去找一个现成的例子来学。但这不影响 TypeScript 编译器 API 玩起来实在是很有趣,用来做代码生成也很合适。可惜这次只接触到了语法的部分而不涉及到语义,那下一次要不要试试移植个 Dagger 呢?

发表评论?

0 条评论。

发表评论


注意 - 你可以用以下 HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">