Skip to content

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

@davidje13

Description

@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.

Metadata

Metadata

Assignees

Labels

BugA bug in TypeScriptFix AvailableA PR has been opened for this issue

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions