Regression in 5.4: Excessive stack depth when comparing recursive type

[cjquines]

🔎 Search Terms

"excessive stack depth", "ts2321"

🕗 Version & Regression Information

• This changed in commit or PR Improve constraints of conditional types applied to constrained type variables #56004

⏯ Playground Link

https://www.typescriptlang.org/play?ts=5.4.3#code/C4TwDgpgBAShCGATA9gOwDYgCoFczogB4sAaKAOSggA9gJVEBnKVHAWwCMIAnMmK2vSZQAgt27wQxAHxQAvFADaAXVlyAUAEgYigOQFUAc2AALXcoF0Gzcuqj2oAfijcEKDCCUA6HzGV2HAC5YNzRMXHwiUgoyRWifLz9pAG51dVBIUXFJAFkAS1RyYjJKGithVk4eNRZ2Lm5LIRsA5zEJKSxpAODSwWsoAAYA+1bsjq6HKGDFBLgkMOw8AmKKaTIEtskZZVT1RAgAY3R4VygAMxxUA+A8tCgTeEYRYAAZBEZgFd7y5kr66QAFAFEPBgPBgnN3JhNuMSAE2AU8mx2D04QBKYIgsFQPLMGH5QpfFJAA

💻 Code

type ReadonlyTuple<T, N extends number, R extends Array<T> = []> =
	R['length'] extends N
    ? readonly [...R]
    : ReadonlyTuple<T, N, [T, ...R]>;

type ArrayMinN<T, N extends number> = number extends N
  ? Array<T>
  : N extends 0
    ? Array<T>
    : [...ReadonlyTuple<T, N>, ...Array<T>];

declare function hasAtLeast<T, N extends number>(
  data: ReadonlyArray<T>,
  minimum: N,
): data is ArrayMinN<T, N>;

🙁 Actual behavior

The function hasAtLeast does not typecheck, with an error on the return type data is ArrayMinN<T, N>;: "Excessive stack depth comparing types 'ArrayMinN<T, N>' and 'readonly T[]'.(2321)"

🙂 Expected behavior

No type error.

Additional information about the issue

This was reported in remeda/remeda#572.

It's not clear to me whether this is working as intended, though it is a regression. It's not hard to rewrite the type to make it work, but wondering if it's a Deeper Problem™.

[llllvvuu]

Just upon a naive reading of the PR description,

Previously, we'd obtain the constraint of IsArray by applying the distributive conditional type to the constraint of U

Sounds like ArrayMinN<T, N> would have been constrained to ArrayMinN<T, number> which just takes the first branch of your ternary to Array<T> whereas now,

A | B when C possibly extends X.

So it will take the union of all of your ternary branches, which will cause an infinite loop in ReadonlyTuple.

So it seems like this is intended behavior. And it is doing you a favor by showing that ArrayMinN<T, N> in fact does not extend ReadonlyArray<T>:

type foo = ReadonlyTuple<string, 2.5, []>
type bar = ArrayMinN<string, -1>

You can see this fails on any version of TypeScript, e.g. 5.0.4: https://www.typescriptlang.org/play?ts=5.0.4#code/C4TwDgpgBAShCGATA9gOwDYgCoFczogB4sAaKAOSggA9gJVEBnKVHAWwCMIAnMmK2vSZQAgt27wQxAHxQAvFADaAXVlyAUAEgYigOQFUAc2AALXcoF0Gzcuqj2oAfijcEKDCCUA6HzGV2HAC5YNzRMXHwiUgoyRWifLz9pAG51dVBIUXFJAFkAS1RyYjJKGithVk4eNRZ2Lm5LIRsA5zEJKSxpAODSwWsoAAYA+1bsjq6HKGDFBLgkMOw8AmKKaTIEtskZZVT08GgAM2RkeRD5jwjlxmBuAsMyACYvAFZY1T3MjngGhU2QfMKhGutyMZAAtABGLrqRAQADG6G+hxwqDhwDyaCgJngjBEwAAMghriteuVmJV6tIABQBRDwYDwYJzdyYP4yEgBNgFPJsdg9DkASmCdIZUDyzD+AKK0XIKSAA

Type instantiation is excessively deep and possibly infinite.

I don't know if there's a fully robust implementation of ArrayMinN that doesn't involve the Nat inductive type (TypeScript doesn't have inductive types in general AFAIK)

You could try using // @ts-expect-error if you don't care about the non-natural number case.

[RyanCavanaugh]

Unfortunately, whether or not you hit this limiter is very dependent on the exact order that things happen internally, so implementation details can cause this to happen or not happen pretty easily.