这段时间有些颓废，这一篇鸽了好久甚至不想往下写了，太奇技淫巧的东西可能也没人会用到，不过还是编完吧。上一篇里我们用类型实现了一个脚本语言的 parser，其实试一下就会发现，如果多写几条语句就会出现类型实例化过深的错误： // ts2589: Type instantiation is excessively deep and possibly infinite. type manyStatements = Parse < [ 1 , 2 , 3 , 4 , 5 , 6 ] > ; // ts2589: Type instantiation is excessively deep and possibly infinite. type deepDepth = Parse < [ If , true , [ If , true , [ If , true , [ ] ] ] ] >
上面的代码才几条表达式语句或者三层语句块就报错了，这太不 scale 了，是时候使用黑魔法了。
先来看第一种情况，只有连续的多条语句，我们现在分析多条语句是这样实现的： // 分析多条语句 type ParseStatements < Context > = Switch < PeekToken < Context >, { // 如果发生错误或输入结束，退出循环 EOF Context ; ERROR Context ; default : // 每次迭代返回的是已经分析的语句数组 GetReturn < Context > extends infer StatementList // 分析下一条语句 ParseStatement < Context > extends infer Context GetReturn < Context > extends infer Statement // 将语句 Push 进数组进入下一次迭代 ParseStatements < SetReturn < Context , Push < StatementList , Statement > > > : never : never : never ; } > ; // 分析多条语句 type ParseStatements < Context > = Switch < PeekToken < Context >, { // 如果发生错误或输入结束，退出循环 EOF Context ; ERROR Context ; default : ParseStatements < // 每次迭代返回的是已经分析的语句数组 GetReturn < Context > extends infer StatementList // 分析下一条语句 ParseStatement < Context > extends infer Context GetReturn < Context > extends infer Statement // 将语句 Push 进数组 SetReturn < Context , Push < StatementList , Statement > > : never : never : never > ; } > ;Switch 和其第二个参数的对象类型，以及分支中的 条件类型 都是类型实例。类型实例化时会递增深度计数，返回时递减回去。在上面的代码中，整个类型都依赖递归的部分，递归的部分返回整个类型才能确定，所以每次递归都会增加几次实例化计数，难怪递归了几次就超出上限了。
其实仔细看一下会发现，之前这段代码的写法有点问题，我把对 ParseStatements 的递归调用放在了 条件类型 里，其实在递归之前这些类型都是可以确定的，可以改下一下让它们提前返回：manyStatements 就不会报错了。
但是继续增加语句发现到 12 个就又报错了： // ts2589: Type instantiation is excessively deep and possibly infinite. type manyStatements = Parse < [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 1 , 2 , ] > ; type ParseStatements < Context > = Switch < PeekToken < Context >, { EOF Context ; ERROR Context ; default : ParseStatements < ParseStatements2 < Context > > } > ; type ParseStatements1 < Context > = GetReturn < Context > extends infer StatementList // 如果上一次返回值是错误，停止分析 StatementList extends SyntaxError Context // 分析一条语句 : ParseStatement < Context > extends infer Context GetReturn < Context > extends infer Statement // push 进语句数组并返回 SetReturn < Context , Push < StatementList , Statement > > : never : never : never ; type ParseStatements2 < Context > = // 连续分析两条语句 ParseStatements1 < ParseStatements1 < Context > >ParseStatements1），连续调用两次就可以一次解析最多两条语句。
再试一下，可以分析最多 20 条语句了： type manyStatements = Parse < [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , ] > ;getTypeAliasInstantiation 的实现），这导致连续调用带泛型类型会递归地实例化参数，所以实例化深度会随调用次数增加。如果尝试这么做，最多也只能提高到分析 60 多条语句。
如果只是做到这种程度的话就不叫黑魔法了，其实还可以继续 hack。
我们现在知道，连续调用两次 ParseStatements1 深度增加两层，可以分析两条语句。如果调用两次 ParseStatements2 呢？不出意外的话深度应该是 2 + 2 = 4 层，可以解析 2 x 2 = 4 条语句。以此类推，如果我们继续这样嵌套下去，可以在实例化深度为 2n 的情况下一次性分析 2 的 n 次方 条语句， 2 的 n 次方 增长速度是比 2n 快的，所以我们可以用较少的实例化深度迭代更多次。
但如果实际写一下会发现，即使我们写成多个泛型类型，实例化的时候最终都是惰性（递归地）计算的，也就是说深度也是按 type ParseStatements2 < Context > = ParseStatements1 < Context > extends infer Context ParseStatements1 < Context > : never ; type ParseStatements4 < Context > = ParseStatements2 < Context > extends infer Context ParseStatements2 < Context > : never ; type ParseStatements8 < Context > = ...2 的 n 次方 增长的。好在我们可以用 infer 语法来提前计算出类型：infer 提前计算了类型，第二次调用时参数使用 infer 出的类型变量，避免了递归实例化类型，所以两次调用都只会增加一层实例化深度。但是由于 条件类型 本身也要实例化，所以总体仍然是两层，和改写前其实一样，但是互相调用时不会递归了。实际上在 leetcode 上有一个整数拆分问题，题解中证明了将整数拆分成最接近常数 e 也就是 3 时，乘积最大。
但实际上上面的类型不止会产生 2 层类型，这么写已经是最接近 3 了。试了一下，如果一次迭代分析 32 条语句，上面的例子可以提高到分析 160 多条语句，没法继续 hack 了。再来看 deepDepth 的例子，上面的奇技淫巧之所以管用是因为类型计算是向量化的，在分析时并不关心具体是什么语句。但是代码块存在于各种语句中，不能简单的组合到一起连续分析，所以上面的黑魔法就不管用了。
然而还是有办法的。因为我们的语法是上下文无关的，分析语句块时也不需要关心前后上下文，所以我们可以把整个输入中所有语句块分别分析，技巧就是利用 // 当前的实现直接从输入分析连续的语句 type Parse < Tokens extends any [] > = GetReturn < ParseStatements < ParserContext < Tokens , [] > >> ; // 示例代码 type ast = Parse < [ If , "y" , gt , "x" , [ Return , "y" ], Return , "x" ] > ; // 从输入的 token 分析语法树 type Parse < Tokens extends any [] > = GetReturn < FullParse < Tokens > > ; // 完全分析一段输入 type FullParse < Tokens > = PreParse < Tokens > extends infer R PostParse < R > : never ; // 预先分析输入中的语句块 type PreParse < Tokens > = { [ P in keyof Tokens ] : Tokens [ P ] extends any [] // 如果当前 token 是数组，分析语句块 FullParse < Tokens [ P ] > // 其他 token 不做处理 : Tokens [ P ]; } // 后续分析其余的语句 type PostParse < Tokens > = ParseStatements < ParserContext < Tokens , [] > > ; // 修改一下语句块的实现 type ParseBlock < Context > = // 输入的语句块经过预先分析应该变成了包含结果的上下文对象 Scan < Context , any > extends infer Context GetReturn < Context > extends infer BlockContext BlockContext extends ParserContext // 返回预先分析出的语句块的结果 SetReturn < Context , GetReturn < BlockContext > > : ThrowSyntaxError < Context , " code block " > : never : never ;映射类型。按照我们之前的设计，输入的代码是一个 token 数组，其中嵌套的数组表示代码块：Parse 和 ParseBlock 的逻辑修改一下：Parse 拆成了 PreParse 和 PostParse，再组合成 FullParse。PreParse 利用 映射类型 对输入中的语句块（数组）先行分析，PostParse 继续将其余的输入分析成语句。
其实到这里我也没法解释了，因为其实有一些怪异的现象，不过现在我们可以分析更长、更多嵌套（虽然不是很多）的语句了。其实还有个问题是表达式不能过长，可能得稍微修改一下语法，先就这样吧……仿照之前的内容，可以很容易地实现更多语法，不过如果尝试解释执行又会遇到限制不能执行较长的代码，要想用上面的技巧解决这个问题就得使代码向量化，也就是编译成中间表示。然而下一篇又要鸽了，以上都是我胡编的。
最后放上 Playground。
免责声明：本平台仅供信息发布交流之途，请谨慎判断信息真伪。如遇虚假诈骗信息，请立即举报
举报
