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
游乐场连接
这至少可以归结为两个问题：
TS如何检查L是否可分配给LL(反之亦然)。
TS如何检查L扩展LL(反之亦然)
我认为答案可能是一样的，这与缓存递归类型有关，以避免永远检查，但我对细节不清楚。
我要找的是可以应用于示例的算法的一些伪代码或文本描述。
您对终止发生方式的直觉是正确的。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:
Q-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
A-2。它们的类型可能是兼容的，所以它们可能是，所以返回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;
}
}
游乐场链接
添加额外的成员和联合并不能从根本上改变这种算法，它只是在顶部添加了额外的层。如果一个联盟的任何成员与另一个联盟中的任何成员兼容，则联盟被视为兼容。成员兼容性也不会对其产生太大影响。如果一个成员是Maybe兼容的，那么整个类型是Maybe兼容的，即使所有其他道具都是绝对兼容的。
算法，您正在讨论文档中描述的
TypeScript结构类型系统的基本规则是，如果y至少有与x相同的成员，则x与y兼容。
为了检查y是否可以分配给x，编译器检查x的每个属性，以在y 中找到相应的兼容属性
让我们回到您的示例。
// LL is the same as L unfolded once
type L = [] | { item: number, next: L }
/**
* It s because here you went one level deeper, but type is practicaly the same
*/
type LL = [] | { item: number, next: ({ item: number, next: LL } | []) }
L和LL都可以是空数组或具有两个属性的对象
这里有一个小例子：
type A = [] | {}
type B = [] | {}
let a: A = []
let b: B = {}
a = b // a can be an empty object as well
b = a // b can be an empty array as well
L和LL也可以是具有item属性和next属性的对象
因此，TS编译器转到L并询问：
TS：HejL，我可以把你当作一个有两个属性的对象吗？
L：当然可以，因为我被键入为具有两个属性(item&next)的对象。
TS：Hej，LL，我可以把你当作具有item和next属性的对象吗？
当然，这是我喜欢的类型。你甚至可以把我当作空数组。
TS：好的，L和LL，也许我可以把你当作一个空数组？
L，LL：完全没有问题)
由于TS具有结构类型系统，所以这两种类型的处理方式相同。
这就是我对这个算法的理解。
UPDATE for recursion我无法比docs 更好地解释它
但引入界面的变通方法对用户来说并不直观。原则上，直接使用Array的ValueOrArray的原始版本确实没有任何问题。如果编译器有点"懒惰"，并且只在必要时计算Array的类型参数，那么TypeScript可以正确地表达这些参数。
这正是TypeScript 3.7引入的内容。在类型别名的"顶级"，TypeScript将推迟解析类型参数以允许这些模式。
在TS 3.7之前，有一个擦剂：
过去你不能引用你在类型本身内部定义的类型。
由于TS 3.7，您可以做到这一点。以前，要制作递归类型，您应该在使用类型的同时使用接口。
示例：
type ValueOrArray2<T> = T | ArrayOfValueOrArray<T>;
interface ArrayOfValueOrArray<T> extends Array<ValueOrArray2<T>> {}
游乐场
据我所知，如果你引用类型本身(间接引用)，TS会生成一个别名
为了更好地理解递归类型是如何工作的，您可以检查这些测试
我不知道这么好的TS回购做一个循序渐进的分析这个算法