Tail recursion optimization limit 999 may be manipulated

[Alexsey]

Bug Report

🔎 Search Terms

tail recursion, tail recursion optimization, tail recursion detection, tail recursion limit

🕗 Version & Regression Information

• This is a crash: yes
• This is the behavior in every version I tried, and I reviewed the FAQ for entries about: yes

⏯ Playground Link

Playground link with relevant code

💻 Code

type NumberToTuple1<Num extends number, Tuple extends 0[] = []> = 0 extends 1 ? never :
  Tuple['length'] extends Num ? Tuple : NumberToTuple1<Num, [...Tuple, 0]>; // this line

type NumberToTuple2<Num extends number, Tuple extends 0[] = []> =
  Tuple['length'] extends Num ? Tuple : NumberToTuple2<Num, [...Tuple, 0]>; // is the same as this line

type BigTuple_Computed = NumberToTuple1<1000>

type BigTuple_Error = NumberToTuple2<1000> // Type instantiation is excessively deep and possibly infinite.(2589)

🙁 Actual behavior

NumberToTuple1 is using the tail recursion optimization so BigTuple_Computed type is [0, 0, 0, ..., 0], just as expected.
NumberToTuple2 is NOT using tail recursion optimization using tail recursion optimization in a different maneer so BigTuple_Error type is any.
The difference between them is only in junk piece of code 0 extends 1 ? never : that is doing nothing.

UPD: NumberToTuple2 is working up to 999, while NumberToTuple1 is working up to 3153

🙂 Expected behavior

According to the article introducing tail call optimization to TypeScript, tail call optimization should be applied to both NumberToTuple1 and NumberToTuple2 the same, because non of them is doing any on-stack transformations with the call results. Recursion limit is expected to remain the same

[jcalz]

Is this really a bug?

1000 is right on the edge of the recursion limit for tail-call optimizations, so I'm not surprised that two slightly different formulations would have two different behaviors near that limit. If you use something like 500 instead you'll see that both actually do use tail-call optimization, as opposed to something like

type NumberToTuple3<N, T extends 0[] = []> =
  T['length'] extends N ? T : (NumberToTuple3<N, [...T, 0]> & {});

which doesn't:

type BigT_Computed = NumberToTuple1<500> // ok
type BigT_StillOkay = NumberToTuple2<500> // ok
type BigT_Bad = NumberToTuple3<500> // ☠

I admit I'd think NumberToTuple1 would bomb out before NumberToTuple2 but I don't think that changes whether or not they are using tail-call detection.

(Also, you confused me for quite a bit by shadowing the Number interface with a type parameter named Number. I'd stick with N and T or even Num and Tuple unless you have some compelling reason to make X extends Number mean something other than what it normally means)

Playground link

[RyanCavanaugh]

Is this really a bug?

It's a bug in the sense that if someone can and will fix it, I'm not going to stop them. That's about it though.

[Alexsey]

@jcalz thank you for the comment, I've renamed Number - you are correct, it was a bad idea for a var name. Also, I agree with you that tail call optimization is getting applied in both cases, just differently: NumberToTuple2 is working well up to 999, while non-optimized recursion is failing at about 45. On the other hand, NumberToTuple1 is working up to 3153. I agree that we can consider it more as a hack then as a bug.

@RyanCavanaugh thank you for taking a look! Not sure that there is something can be fixed but ensuring that the limit for both types would be the same (probably 999?)

A funny thing to note is that adding more levels of nasting would get the limit back to 999

type NumberToTuple3<Num extends number, Tuple extends 0[] = []> = 0 extends 1 ? never : 0 extends 1 ? never :
  Tuple['length'] extends Num ? Tuple : NumberToTuple2<Num, [...Tuple, 0]>;

type StillWorking = NumberToTuple3<999>
type AlreadyAnError = NumberToTuple3<1000>

[lvjiaxuan]

Any conclusions?

[ENvironmentSet]

I faced a similar issue and I've investigated the compiler for a moment. Here I left what I've found for people who might wonder what's going on here.

I was looking for tricks to bypass recursion depth limit, eventually I've arrived to this magical type:

type Magic<T> = T

Wrapping any tail recursive conditional type with this type allows it bypass iteration limit of 1000.

type NumberToTuple3<Num extends number, Tuple extends 0[] = []> = 
  Magic<Tuple['length'] extends Num ? Tuple : NumberToTuple3<Num, [...Tuple, 0]>>;

// It's okay to duplicate `Magic`

type NumberToTuple4<Num extends number, Tuple extends 0[] = []> = 
  Magic<Magic<Tuple['length'] extends Num ? Tuple : NumberToTuple3<Num, [...Tuple, 0]>>>;

Surprised, I looked over the compiler, and found a function called canTailRecurse in checker.ts. It was for checking whether the given type is valid to perform tail call optimization. There was a one and only point of updating the tail recursion counter:

if (newRoot.aliasSymbol) {
    tailCount++;
}

This conditional statement was left with following comment:

Note that recursion is possible only through aliased conditional types, so we only increment the tail recursion counter for those.

It seems the author expected every recursive conditional type to have aliasSymbol. But somehow there were exceptions. I've examined example blow, and found that some recursive conditional types (including ones wrapped with Magic) doesn't have aliasSymbol in their representation.

type Magic<T> = T
type NTuple<N extends number, T, R extends unknown[] = []> = Magic<R['length'] extends N ? R : NTuple<N, T, [T, ...R]>>
type Inc<N extends number> = [0, ...NTuple<N, 0>]['length']

type Test = Inc<1003>

I don't know how aliasSymbol is constructed and maintained, but I think it's the one who makes this problem.

P.S this bug seems to exist from the beginning of TCO for recursive conditional types. (#45711)