`A rest element type must be an array type.` error regression on 4.5.0-dev.20211003 when using spread expression with a generic that returns a tuple (does not hapen on v4.4.3)

[ruohola]

Bug Report

🔎 Search Terms

• A rest element type must be an array type.
• Error on spread expression with a generic that returns a tuple

🕗 Version & Regression Information

• This changed between versions v4.4.3 and 4.5.0-dev.20211003

⏯ Playground Link

4.5.0-dev.20211003 Playground link (error happens)
v4.4.3 Playground link (no errors)

💻 Code

type NTuple<N extends number, Tup extends unknown[] = []> =
  Tup['length'] extends N ? Tup : NTuple<N, [...Tup, unknown]>;

type Add<A extends number, B extends number> =
  [...NTuple<A>, ...NTuple<B>]['length'];
/* ~~~~~~~~~~~~
   A rest element type must be an array type. (2574)
*/

let five: Add<2, 3>;

🙁 Actual behavior

Getting a A rest element type must be an array type. error for ...NTuple<A>.

🙂 Expected behavior

No errors should happen, and no error happens on TypeScript v4.4.3.

[ahejlsberg]

@weswigham This is caused by #41821. When exploring the constraint of the recursive conditional type NTuple<...> we'd get five levels deep and then return a Ternary.Maybe due to isDeeplyNestedType being true on both sides. It's now only true on one side, so in order to not infinitely recur there's an extra isDeeplyNestedType check in conditional constraint exploration. But that simply stops exploring after five levels, causing Ternary.False instead of Ternary.Maybe.

[weswigham]

You think we should return Maybe if conditional constraint exploration is deeply nested (rather than False)? Or do you think we should have some new rule governing recursive conditional constraint relation? Because one branch of NTuple, Tup is obviously array like, while the other is (infinitely) self-recursive. I think a combination of both might be correct - right now we union both branches of the constraint before attempting a relation; we probably need to split that and test one branch at a time (so one can return true/false/maybe independently of others). Once we have that, we can rig it so if one branch returns Maybe, we use the other branch's result exclusively (and potentially still return False if both branches are Maybe).

[ahejlsberg]

I tried returning Ternary.Maybe when we see a deeply nested source in the conditional constraint exploration logic, but we then get a failure in the genericConditionalConstrainedToUnknownNotAssignableToConcreteObject.ts test (which was added by #41821 and presumably solved by it). Not sure what to do about that.

[ahejlsberg]

So the reason we get the test failure I mention above when returning Ternary.Maybe is simply that it takes five levels of recursion to fully explore the constraint of the ReturnType<T[M]> type in the test. Compiling the test with --keyofStringsOnly (which removes one level of nesting because keyof then doesn't have a union constraint) causes the test to error as expected. So, guess we need to find a way to selectively keep the depth lower.

[ahejlsberg]

I'm sort of feeling like maybe simplifications of conditional types (as they occur when exploring constraints of distributive conditional types) shouldn't be counted in the depth (or should count less) because they're never circular and are never the cause of deep recursion.

[weswigham]

We could increase the limit for the mono-directional checks in constraint comparison by making isDeeplyNestedType take the allowed nesting level as an argument, rather than just reusing the hardcoded 5. Potentially something dynamic like 3/4ths the total depth this far (or 5, whichever is greater) might be more flexible for that. (Since infinite constraints are truly infinite, we can make the required repitions quite large and all we might loose is some time)