为 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），可以是普通的本地数据结构，甚至也可以是封装好的数据库操作。例如这个官方提供的样例：
|
1 2 3 4 5 6 7 |
int[] scores = new int[] { 97, 92, 81, 60 }; // Define the query expression. IEnumerable<int> scoreQuery = from score in scores where score > 80 select score; |
然而据我的理解，真正在代码里用 LINQ 语句的人并不多……大多数情况 LINQ 是直接通过扩展方法调用的：
|
1 2 3 4 |
int[] scores = new int[] { 97, 92, 81, 60 }; // Call LINQ methods IEnumerable<int> scoreQuery = scores.Where(score => score > 80); |
说到这里其实 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> 有关，即延迟执行。举例而言，
|
1 2 3 |
int[] scores = new int[] { 0.97, 0.92, 0.81, 0.60 }; bool hasLowScore = scores.Select(score => score * 100).Any(score => score < 80); |
这个例子中首先将原来数组中的数值都乘以 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 体验会是怎样的。
|
1 2 3 |
int[] scores = new int[] { 97, 92, 81, 60 }; IEnumerable<int> scoreQuery = scores.Select(score => Math.Sqrt(score) * 10); |
要在 TypeScript / JavaScript 中还原 C# 的这个例子，首当其冲的第一个障碍便是没有扩展方法，而这意味着我们并不能直接给一个接口定义方法。因此还是要首先将一个 Iterable<T> 包装在一个带有 LINQ 实现的类型才行。因此最终使用起来看上去会是这样：
|
1 2 3 |
const scores: number[] = [97, 92, 81, 60]; const scoreQuery: Iterable<number> = from(scores).select(score => Math.sqrt(score) * 10); |
考虑到最初 LINQ 那个类似 SQL 查询的用法，这个额外的 from() 方法可一点都不违和呢。当然这不是我想出来的点子，而是另一位在六年前给 ES2015 实现过 LINQ 的前辈的方案：https://github.com/balazsbotond/eslinq。
而剩下的实现就很简单了，只要借助 function* 就能很轻松地实现 Select 的功能。
这里插一句：考虑到 C# 有非常多针对 Enumerable 的优化，例如使用 struct 而非 class 实现 Enumerator<T>，C# 的 Enumerable<T> 遍历效率可以非常高而且对 GC 很友好。但我并不清楚主流的 JavaScript 引擎包括 v8 对这种场景的优化究竟如何。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
export function from<T>(iterable: Iterable<T>): Enumerable<T> { return new Enumerable(iterable); } class Enumerable<T> implements Iterable<T> { private readonly iterable: Iterable<T>; public constructor(iterable: Iterable<T>) { this.iterable = iterable; } public select<TResult>(selector: (element: T) => TResult): Enumerable<T> { return new Enumerable(this.selectImpl(selector)); } private *selectImpl<TResult>(selector: (element: T) => TResult): Iterable<T> { for (const element of this.iterable) { yield selector(element); } } } |
为 Select 支持异步调用
异步分为两个使用情况：数据源就是异步的（ AsyncIterable），以及作为函数的参数是异步的。
简单来说，只需要把上面的代码复制一遍稍作修改就能支持异步了：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
export function from<T>(iterable: AsyncIterable<T>): AsyncEnumerable<T> { return new AsyncEnumerable(iterable); } class AsyncEnumerable<T> implements AsyncIterable<T> { private readonly iterable: AsyncIterable<T>; public constructor(iterable: AsyncIterable<T>) { this.iterable = iterable; } public select<TResult>(selector: (element: T) => TResult): AsyncEnumerable<T> { return new AsyncEnumerable(this.selectImpl(selector)); } private async *selectImpl<TResult>(selector: (element: T) => Promise<TResult>): AsyncIterable<T> { for await (const element of this.iterable) { yield selector(element); } } } |
异步，但是 DRY（Do not Repeat Yourself）！
上述的例子是可行没错，但是 LINQ（C# 的实现）一共有总计 56 个方法及 182 个重载，要如此维护两份几乎完全一样的实现是不现实的：实现工作量大、维护工作量大、甚至还会导致存在不一致的实现。
然而 TypeScript 又不像 C++ 有那么强的模板系统，因此只好利用代码生成了。
这里简单讲一下我的方案：实现一份完整的异步代码，然后通过 TypeScript 编译器 API 读取它的 AST（抽象语法树），再做一些预设的替换让它成为一份同步的实现。至于为什么不是反过来，那毕竟删除代码比插入代码要简单得多嘛……
举例而言，如果要剔除掉所有的 await（包括 await 表达式和 for await），大致代码会是这样：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
function convertMethodBody(block: Block): Block { function visitor(node: Node): Node { // Remove await from for await if (TypeScript.isForOfStatement(node)) { if (node.awaitModifier) { return TypeScript.factory.createForOfStatement( undefined, TypeScript.visitEachChild(node.initializer, visitor, context), TypeScript.visitEachChild(node.expression, visitor, context), TypeScript.visitEachChild(node.statement, visitor, context) ); } } // Remove await from await statements if (TypeScript.isAwaitExpression(node)) { return node.expression; } return TypeScript.visitEachChild(node, visitor, context); } return TypeScript.visitEachChild(block, visitor, context); } |
生成 wrapper method
在 Select 的例子中，Select 的实现在一个私有方法 selectImpl 中，而又有另一个公有方法 select 将其返回的 Iterable<T> 转换成拥有 LINQ method 的 Enumerable<T>（不然就不能链式调用啦）。考虑到大多数 LINQ method 都是返回 Enumerable<T> 的，这种 wrapper method 最终一定会到处都是……秉承着 DRY 的原则，另一方面也因为反正都用 TypeScript 编译器 API 做代码生成了，不如把那些 wrapper method 一并生成了。
代码生成本身的思路很简单，就只举例说明了。源代码中的实现模板会是这样：
|
1 2 3 4 5 6 7 |
class EnumerableTemplate<T> { public async *selectImpl<TResult>(selector: (element: T) => Promise<TResult>): AsyncIterable<T> { for await (const element of this.iterable) { yield selector(element); } } } |
代码生成后就会生成一份同步一份异步的代码，其中同步的代码就会长这样：
|
1 2 3 4 5 6 7 8 9 10 |
class Enumerable<T> implements Iterable<T> { public select<TResult>(selector: (element: T) => TResult): Enumerable<T> { return new Enumerable(this.selectImpl(element)); } public async *selectImpl<TResult>(selector: (element: T) => TResult): Iterable<T> { for (const element of this.iterable) { yield selector(element); } } } |
当然了……具体实现的时候还是会遇到很多零碎的情况需要处理：比如如何识别哪些方法需要生成 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 的签名是这样：
|
1 2 3 4 5 6 7 8 9 |
class Enumerable<T> implements Iterable<T> { public average(DO_NOT_ASSIGN: T extends number ? void : never): number; } from([0]).average(); // OK from([0]).average(42); // Argument of type 'number' is not assignable to parameter of type 'void'. from([""]).average(); // An argument for 'DO_NOT_ASSIGN' was not provided. from([""]).average(42 as any); // Argument of type 'any' is not assignable to parameter of type 'never'. |
其中那个 DO_NOT_ASSIGN 就是魔法的本质。对于数值类型而言，它的类型是 void，也就意味着这个参数将变成可选参数。而在其他情况下它的类型是 never，而 never 是 TypeScript 类型系统中的 bottom type，在 OOP 语境中相当于它是任何类型的子类，也就是一个 never 类型的变量不能被赋予任何的值。
当然要想蓄意破坏还是可以的……
|
1 2 |
from([0]).average(undefined); // OK from([""]).average(42 as never); // OK |
目标：100% 测试覆盖率
由于同时有同步和异步两份实现的关系，测试的重复性会很高。因此绝大多数的测试用例都是自动覆盖全部同步、异步的情况的。例如：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
describe("LINQ", () => { describe.each([ { name: "should map iterables without index", input: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], output: ["0", "1", "2", "3", "4", "5", "6", "7", "10", "11"], selector: x => x.toString(8) }, // ... more cases ])("Select", ({name, input, output, selector}) => { it(`${name} synchronously`, () => { expect(from(input).select(selector).toArray()).toEqual(output); }); it(`${name} asynchronously with synchronous selector`, async () => { expect(await from(input).asAsync().select(selector).toArray()).toEqual(output); }); it(`${name} asynchronously with asynchronous selector`, async () => { expect(await from(input).asAsync().select((x, i) => Promise.resolve(selector(x, i))).toArray()).toEqual(output); }); }); }); |
自定义扩展
TypeScript 自身的 Module Argumentation 就很够用了。
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// ./partition.ts import { Enumerable } from "es2018-linq/lib/enumerable"; declare module "es2018-linq" { interface Enumerable<T> { partition<T>(this: Enumerable<T>, predicate: (element: T) => boolean): [Enumerable<T>, Enumerable<T>]; } } Enumerable.prototype.partition = function<T>(this: Enumerable<T>, predicate: (element: T) => boolean): [Enumerable<T>, Enumerable<T>] { return [this.where(predicate), this.where(element => !predicate(element))]; } |
|
1 2 3 4 5 6 7 8 9 |
import { from } from "es2018-linq"; import "./partition"; console.log(from([0, 1, 2, 3]).partition(x => x % 2 === 0).map(e => e.toArray())); // Output: // [ // [0, 2], // [1, 3], // ] |
目前缺失的部分
有一些方法和重载，诸如 Cast，由于 TypeScript / JavaScript 中缺失相应的功能，就不打算实现了。
另外一些集合相关的操作，例如 Union，目前并不支持自定义的 comparer，因为 JavaScript 自带的 Set 实现并不支持 comparer。这块根据反馈可能会以后慢慢加。
还有一些缺失的重载则是由于重载起来实在过于复杂，尤其是一些参数顺序完全打乱的重载，因为 TypeScript 层面的重载仅仅是做类型标记，而 JavaScript 层面的重载则要在运行时手动检查参数类型。
后记
TypeScript 编译器 API 的官方文档几乎没有，要想利用一些没用过的功能就必须去找一个现成的例子来学。但这不影响 TypeScript 编译器 API 玩起来实在是很有趣，用来做代码生成也很合适。可惜这次只接触到了语法的部分而不涉及到语义，那下一次要不要试试移植个 Dagger 呢？
0 条评论。