recursive type crashes tsc with RangeError: Maximum call stack size exceeded

[davidje13]

TypeScript Version: 3.8.3 / 3.9.0-dev.20200426

Search Terms:

RangeError: Maximum call stack size exceeded, getTypeFromTypeNode, inferTypes

Code

{ "compilerOptions": { "strict": true } }

type Recur<T> = (
  T extends (unknown[]) ? {} : { [K in keyof T]?: Recur<T[K]> }
) | ['marker', ...Recur<T>[]];

function join<T>(l: Recur<T>[]): Recur<T> {
  return ['marker', ...l];
}

function a<T>(l: Recur<T>[]): void {
  const x: Recur<T> | undefined = join(l);
}

Expected result:

Success, or a compiler error explaining why this is not permitted.

Actual behavior:

tsc crashes with one of the following stacktraces:

<project>/node_modules/typescript/lib/tsc.js:82855
                throw e;
                ^

RangeError: Maximum call stack size exceeded
    at getSimplifiedType (<project>/node_modules/typescript/lib/tsc.js:38643:35)
    at getNormalizedType (<project>/node_modules/typescript/lib/tsc.js:40573:57)
    at isRelatedTo (<project>/node_modules/typescript/lib/tsc.js:40832:30)
    at typeRelatedToSomeType (<project>/node_modules/typescript/lib/tsc.js:41076:35)
    at eachTypeRelatedToSomeType (<project>/node_modules/typescript/lib/tsc.js:41061:35)
    at isIdenticalTo (<project>/node_modules/typescript/lib/tsc.js:40970:36)
    at isRelatedTo (<project>/node_modules/typescript/lib/tsc.js:40837:28)
    at typeArgumentsRelatedTo (<project>/node_modules/typescript/lib/tsc.js:41154:39)
    at relateVariances (<project>/node_modules/typescript/lib/tsc.js:41525:34)
    at structuredTypeRelatedTo (<project>/node_modules/typescript/lib/tsc.js:41475:46)

or

<project>/node_modules/typescript/lib/tsc.js:82855
                throw e;
                ^

RangeError: Maximum call stack size exceeded
    at getMappedType (<project>/node_modules/typescript/lib/tsc.js:39384:31)
    at getMappedType (<project>/node_modules/typescript/lib/tsc.js:39401:30)
    at instantiateTypeWorker (<project>/node_modules/typescript/lib/tsc.js:39683:24)
    at instantiateType (<project>/node_modules/typescript/lib/tsc.js:39670:26)
    at instantiateTypeWorker (<project>/node_modules/typescript/lib/tsc.js:39717:37)
    at instantiateType (<project>/node_modules/typescript/lib/tsc.js:39670:26)
    at getConstraintFromTypeParameter (<project>/node_modules/typescript/lib/tsc.js:37303:67)
    at computeBaseConstraint (<project>/node_modules/typescript/lib/tsc.js:36469:38)
    at getImmediateBaseConstraint (<project>/node_modules/typescript/lib/tsc.js:36442:34)
    at getResolvedBaseConstraint (<project>/node_modules/typescript/lib/tsc.js:36430:72)

or

<project>/node_modules/typescript/lib/tsc.js:82855
                throw e;
                ^

RangeError: Maximum call stack size exceeded
    at recursiveTypeRelatedTo (<project>/node_modules/typescript/lib/tsc.js:41179:44)
    at isIdenticalTo (<project>/node_modules/typescript/lib/tsc.js:40976:24)
    at isRelatedTo (<project>/node_modules/typescript/lib/tsc.js:40837:28)
    at typeRelatedToSomeType (<project>/node_modules/typescript/lib/tsc.js:41076:35)
    at eachTypeRelatedToSomeType (<project>/node_modules/typescript/lib/tsc.js:41061:35)
    at isIdenticalTo (<project>/node_modules/typescript/lib/tsc.js:40970:36)
    at isRelatedTo (<project>/node_modules/typescript/lib/tsc.js:40837:28)
    at typeArgumentsRelatedTo (<project>/node_modules/typescript/lib/tsc.js:41154:39)
    at relateVariances (<project>/node_modules/typescript/lib/tsc.js:41525:34)
    at structuredTypeRelatedTo (<project>/node_modules/typescript/lib/tsc.js:41475:46)

(probably others too, but these seem typical. Line numbers are for the 3.9.0-dev.20200426 version)

Note that the problem disappears (and the code compiles successfully) if any of the following is changed:

• |undefined is removed from the type of x (though the problem remains if it is swapped for anything else, such as |number)
• join<T>(l) is used explicitly
• the implementation of join is inlined
• the Recur type is changed to type Recur<T> = { [K in keyof T]?: Recur<T[K]> } | ['marker', ...Recur<T>[]];
• strict is set to false in tsconfig.json (and then it continues to work even if |undefined is replaced with |number or similar)

Playground Link: I am unable to get a playground link, possibly because this is crashing the compiler, but just put the source above into the playground with default configuration to replicate.

[biogin]

Straight from the doc: "Similar to union and intersection types, conditional types are not permitted to reference themselves recursively. For example the following is an error."
This T extends (unknown[]) ? {} : { [K in keyof T]?: Recur<T[K]> } is where it fails in your case.
And yeah, i guess a more descriptive error message would be great here.

[davidje13]

Is that still true in 3.8? Worth noting that at least one well-used library does this: https://github.com/kolodny/immutability-helper/blob/master/index.d.ts#L15 (the only obvious difference is that in that library, there is no direct recursion like ['marker', ...Recur<T>[]], but it does have the nested recursion of { [K in keyof T]?: Recur<T[K]> })

Also a reduced experiment focusing just on that sort of recursion seems to be fine:

type Deep<T> = T extends ReadonlyArray<any> ? never : (Deep<T> | T)[]

function flatMap<T>(l: Deep<T>): T[] {
  const result: T[] = [];
  recur(result, l);
  return result;
}

function recur<T>(result: T[], l: Deep<T>): void {
  l.forEach((o) => {
    if (Array.isArray(o)) { recur(result, o); } else { result.push(o); }
  });
}

[davidje13]

Digging through a bit more, I think this might be a manifestation of #37475 which links it directly to tuples. But apparently that got fixed last month and I still see this with the latest build.

[ahejlsberg]

The issue appears to be infinite recursion through inferTypeForHomomorphicMappedType which only has a very weak recursion guard in place. I don't know that there are any meaningful scenarios that require recursion in this function, so I think a simple bail out based on a boolean that flags an existing invocation should do the trick. I'll work on a PR for that.