Recursive conditional type throws maximum call stack size exceeded

[cameron-martin]

The following recursive conditional type makes the compiler infinitely recurse and throw a maximum call stack size exceeded error. However, it shouldn't cause this because the R type parameter, a string literal type, is decreasing in length on each recursive call, and will hit the base case after a few iterations.

TypeScript Version: 4.1.2

Search Terms:

condtional types, recursion, stack overflow

Expected behavior:

There is no "maximum call stack size exceeded" error.

Actual behavior:

There is a "maximum call stack size exceeded" error.

Related Issues:

Code

/**
 * Represents a successful parse, yielding the value `X` with remaining input `R`.
 */
export type ParseSuccess<X extends string, R extends string> = { success: true, result: X, rest: R };

/**
 * Represents a failed parse.
 */
export type ParseFail = { success: false };

/**
 * Greedily consumes 0 or more characters of whitespace, yielding the consumed whitespace.
 */
export type ParseManyWhitespace<S extends string> =
  S extends ` ${infer R0}` ? (
    ParseManyWhitespace<R0> extends ParseSuccess<infer X, infer R1> ? ParseSuccess<` ${X}`, R1> : ParseSuccess<' ', R0>
  ) : ParseSuccess<'', S>;

// Uncomment this line and see "Maximum call stack size exceeded" in the console
// type Test = ParseManyWhitespace<" foo">;

Output

export {};
// Uncomment this line and see "Maximum call stack size exceeded" in the console
// type Test = ParseManyWhitespace<" foo">;

Compiler Options

{
  "compilerOptions": {
    "noImplicitAny": true,
    "strictNullChecks": true,
    "strictFunctionTypes": true,
    "strictPropertyInitialization": true,
    "strictBindCallApply": true,
    "noImplicitThis": true,
    "noImplicitReturns": true,
    "alwaysStrict": true,
    "esModuleInterop": true,
    "declaration": true,
    "experimentalDecorators": true,
    "emitDecoratorMetadata": true,
    "moduleResolution": 2,
    "target": "ES2017",
    "jsx": "React",
    "module": "ESNext"
  }
}

Playground Link: Provided

[cameron-martin]

I have updated the example to be smaller and hopefully easier to understand.

[cameron-martin]

I have further whittled the code down and determined that this works:

type ParseSuccess<R extends string> = { rest: R };

type ParseManyWhitespace<S extends string> =
  S extends ` ${infer R0}` ? (
    ParseManyWhitespace<R0>
  ) : ParseSuccess<S>;

type Test = ParseManyWhitespace<" foo">;

but this does not

type ParseSuccess<R extends string> = { rest: R };

type ParseManyWhitespace<S extends string> =
  S extends ` ${infer R0}` ? (
    ParseManyWhitespace<R0> extends ParseSuccess<infer R1> ? ParseSuccess<R1> : null
  ) : ParseSuccess<S>;

type Test = ParseManyWhitespace<" foo">;

If I extract the offending part into a helper function I get the error:

Type instantiation is excessively deep and possibly infinite. (2589)

type ParseSuccess<R extends string> = { rest: R };

type ParseManyWhitespace<S extends string> =
  S extends ` ${infer R0}` ? (
    Helper<ParseManyWhitespace<R0>>
  ) : ParseSuccess<S>;

type Helper<T> = T extends ParseSuccess<infer R> ? ParseSuccess<R> : null

type Test = ParseManyWhitespace<" foo">;

But this error doesn't make much sense to me. Which type is trying to be instantiated too deep?