How does TypeScript check equality for infinite recursive types?

Question

How does TypeScript check equality for infinite recursive types?

Example:

// 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

This boils down to at least two questions:

1. How does TS check that an L is assignable to an LL (and vice versa).

2. How does TS check that L extends LL (and vice versa)

I think the answer might be the same, and that it has something to do with caching recursive types in order to avoid checking forever, but I'm fuzzy on the details.

What I'm looking for is some pseudocode or textual description of the algorithm that can be applied to the example.

Answer 1

Your intuition about how the termination occurs is right. Typescript indeed has a way to limit recursion. The workhorse of compatibility checking is isRelatedTo in checker.ts. This function returns one of False, Unknown, Maybe or True. True and False are pretty explicit, they are used when the relation can be unequivocally determined. Maybe is what is of interest to us. Maybe is used when two types that are currently being compared are encountered during the comparison. To keep track of this the compiler will keep an array of relations that it is currently considering.

With this in mind, let's consider a simpler recursive example:

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

declare const L1: L
const LL1: LL = L1

How will the compiler determine L1 is assignable to LL1:

Q-1. Is L1 assignable to LL1 ?
Q-2. Only if L.next and LL.next are assignable, so are they?
Q-3. Is L assignable to { next: LL}?
Q-4. Only if L.next and { next: LL}.next are assignable
Q-5. Is L1 assignable to LL1?
A-5. Since this is what we are considering at 1. Lets assume they are, so return Maybe
A-4. Their types are maybe compatible, so they might be, so return Maybe
A-3. Since none of their properties are definitely not compatible, and one property was Maybe, maybe they are, so return Maybe
A-2. Their types are maybe compatible, so they might be, so return Maybe
A-1. Since we didn't find a definite incompatibility, they are assignable.

An (overly) simplified pseudocode version of the code would be:

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

Adding the extra members and the union does not fundamentally change this algorithm, it just adds extra layers on top. Union are considered compatible if any constituent of one union is compatible with any constituent of the other union. And member compatibility doesn't influence it much either. If one member is Maybe compatible then the whole type is Maybe compatible, even if all other props are definitely compatible.

Answer 2

Algorithm, you are talking about described in docs here

The basic rule for TypeScript’s structural type system is that x is compatible with y if y has at least the same members as x.

To check whether y can be assigned to x, the compiler checks each property of x to find a corresponding compatible property in y

Let's go back to your example.

// 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 } | []) }

1. L and LL both could be an empty array or object with two properties

Here is a small example:

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

2. L and LL also could be an objects with item property and next property.

So, TS compiler goes to L and asks:

TS: Hej L, can I treat you as an object with 2 properties?

L: Sure you can can, because I was typed as an object with two properties (item & next).

TS: Hej, LL, can I treat you as object with item and next properties?

LL: Sure, this is my type. You can even treat me as empty array as well.

TS: Ok, L and LL, maybe I can treat you as an empty array?

L,LL: No problem at all )

Because TS has structural type system, both types are treated in same way.

This is how I understand this algorithm.

UPDATE for recursion I can't explain it better than docs

But workaround of introducing the interface wasn’t intuitive for users. And in principle there really wasn’t anything wrong with the original version of ValueOrArray that used Array directly. If the compiler was a little bit “lazier” and only calculated the type arguments to Array when necessary, then TypeScript could express these correctly.

That’s exactly what TypeScript 3.7 introduces. At the “top level” of a type alias, TypeScript will defer resolving type arguments to permit these patterns.

Before TS 3.7, there was a linitation:

It used to be that you could not refer to the type you are defining inside the type itself.

Since TS 3.7 you are able to do it. Previously, to make recursive type, you should have use an interface along with type.

Example:

type ValueOrArray2<T> = T | ArrayOfValueOrArray<T>;
interface ArrayOfValueOrArray<T> extends Array<ValueOrArray2<T>> {}

Playground

As far as I understand, TS makes an alias if you are refering to the type itself (indirect referring)

To understand better how recursive types works, you can check these tests

I don't know so good TS repo to make a step by step analysis of this algorithm