typescript - TypeScript 如何检查无限递归类型的相等性？

Question

TypeScript 如何检查无限递归类型的相等性？

例子:

// LL is the same as L unfolded once
type L = [] | {item: number, next: L}
type LL = [] | {item: number, next: ({item: number, next: LL} | [])}

// An L is assignable to an LL
declare const L1: L
const LL1: LL = L1

// An LL is assignable to an L
declare const LL2: LL
const L2: L = LL2

type Interassignable<T, U> = T extends U ? U extends T ? true : never : never

declare const check: Interassignable<L, LL>
const x: true = check // OK

playground link

这至少归结为两个问题:

1. TS 如何检查 L 是否可分配给 LL(反之亦然)。

2. TS 如何检查 L 是否扩展了 LL(反之亦然)

我认为答案可能是一样的，这与缓存递归类型以避免永远检查有关，但我不清楚细节。

我正在寻找的是可以应用于该示例的算法的一些伪代码或文本描述。

Answer 1

您对终止如何发生的直觉是正确的。 Typescript 确实有办法限制递归。兼容性检查的主力是 checker.ts 中的 isRelatedTo。此函数返回 False、Unknown、Maybe 或 True 之一。 True 和 False 非常明确，当可以明确确定关系时使用它们。 Maybe 是我们感兴趣的。 Maybe 在比较过程中遇到当前正在比较的两种类型时使用。为了跟踪这一点，编译器将保留它当前正在考虑的一系列关系。

考虑到这一点，让我们考虑一个更简单的递归示例:

type L = { next: L}
type LL = { next: ({ next: LL})}

declare const L1: L
const LL1: LL = L1

编译器将如何确定 L1 可分配给 LL1:

问题-1。 L1 是否可以分配给 LL1 ？
Q-2。只有 L.next 和 LL.next 是可分配的，它们也是可分配的吗？
Q-3。 L 是否可分配给 { next: LL}？
Q-4。仅当 L.next 和 { next: LL}.next 是可分配的
Q-5。 L1 是否可以分配给 LL1？
A-5。因为这是我们在 1 考虑的。让我们假设它们是，所以返回 Maybe
A-4。它们的类型可能兼容，所以它们可能兼容，所以返回 Maybe
A-3。由于它们的属性都不是绝对不兼容的，并且一个属性是 Maybe，也许它们是，所以返回 Maybe
A2。它们的类型可能兼容，所以它们可能兼容，所以返回 Maybe
A-1.由于我们没有发现明确的不兼容性，因此它们是可分配的。

代码的(过度)简化的伪代码版本是:

interface Type { id: string, properties: Map<string, { type: Type}> }

enum Ternary {
  True = -1,
  False = 0,
  Maybe = 3
}

function checkTypeRelatedTo(source: Type, target: Type){
  let maybeRelated: string[]
  return isRelatedTo(source, target) != Ternary.False;

  function isRelatedTo(source: Type, target: Type): Ternary {
    const relationId = source.id + "," + target.id;
    if(maybeRelated.indexOf(relationId) != -1) {
      return Ternary.Maybe
    }
    maybeRelated.push(relationId);
    const result = structureRelatedTo(source, target);
    maybeRelated.pop();
    return result;
  }

  function structureRelatedTo(source: Type, target: Type): Ternary{
    let result = Ternary.True;
    for(const prop of target.properties.keys()) {
      result &= isRelatedTo(source.properties.get(prop)!.type, target.properties.get(prop)!.type)
      if(!result){
        return Ternary.False
      }
    }
    return result;
  }
}

Playground Link

添加额外的成员和联合并没有从根本上改变这个算法，它只是在顶部添加了额外的层。如果一个联盟的任何成分与另一个联盟的任何成分兼容，则联盟被认为是兼容的。成员兼容性也不会对其产生太大影响。如果一个成员是 Maybe 兼容的，那么整个类型都是 Maybe 兼容的，即使所有其他属性肯定是兼容的。