Skip to content

Tail recursion optimization limit 999 may be manipulated #49459

Open
Open
Tail recursion optimization limit 999 may be manipulated#49459
Labels
BugA bug in TypeScriptDomain: Conditional TypesThe issue relates to conditional typesHelp WantedYou can do this
Milestone
Backlog

Description

@Alexsey
Aleksey Bobyr (Alexsey)
opened on Jun 9, 2022

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

Activity

  1. Ryan Cavanaugh (RyanCavanaugh)
    added
    BugA bug in TypeScript
    Help WantedYou can do this
    on Jun 9, 2022
  2. Ryan Cavanaugh (RyanCavanaugh)
    added this to the Backlog milestone on Jun 9, 2022

  3. jcalz commented on Jun 9, 2022

    @jcalz
    Joe Calzaretta (jcalz)
    on Jun 9, 2022
    Contributor

    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

  4. RyanCavanaugh commented on Jun 9, 2022

    @RyanCavanaugh
    Ryan Cavanaugh (RyanCavanaugh)
    on Jun 9, 2022
    Member

    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.

  5. Alexsey commented on Jun 9, 2022

    @Alexsey
    Aleksey Bobyr (Alexsey)
    on Jun 9, 2022
    Author

    Joe Calzaretta (@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.

    Ryan Cavanaugh (@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>
  6. Aleksey Bobyr (Alexsey)
    changed the title [-]Tail recursion optimization detection bug[/-] [+]Tail recursion optimization limit 999 may be manipulated[/+] on Jun 9, 2022

  7. lvjiaxuan commented on Oct 8, 2022

    @lvjiaxuan
    lvjiaxuan (lvjiaxuan)
    on Oct 8, 2022

    Any conclusions?

  8. ENvironmentSet commented on Feb 10, 2024

    @ENvironmentSet
    Jaewon Seo (ENvironmentSet)
    on Feb 10, 2024

    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)

  9. Ryan Cavanaugh (RyanCavanaugh)
    added
    Domain: Conditional TypesThe issue relates to conditional types
    on Oct 16, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    BugA bug in TypeScriptDomain: Conditional TypesThe issue relates to conditional typesHelp WantedYou can do this

    Type

    No type

    Projects

    No projects

      Milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions