rewrite recursive conditional types to be tail-recursive

[DetachHead]

🍩 Feature Request

Is your feature request related to a problem?

many types in ts toolbelt use recursive conditional types, meaning that using them often results in stack depth errors.

Describe the solution you'd like

in typescript 4.5, tail-recursive conditional types are now optimized such that the recursion limit can be much higher (1000) instead of 100. see the blog post and https://github.com/microsoft/TypeScript/pull/45711

Describe alternatives you've considered

Teachability, Documentation, Adoption, Migration Strategy

[millsp]

That would be an awesome addition :) Have you evaluated which types aren't working out of the box?

[DetachHead]

ones i've noticed so far are listed in the description of #256 - will update the list as i come across more

[DetachHead]

there's also IterationMap which isn't a recursive type, but a hardcoded list of numbers from -100 to 100, so any type that depends on it won't benefit from the increased recursion limit when rewritten to be tail-recursive

i'm not sure how to go about updating it, i don't want to just add 1000 more entries to it because that seems gross. perhaps there's a better solution?

[millsp]

i'm not sure how to go about updating it, i don't want to just add 1000 more entries to it because that seems gross. perhaps there's a better solution?

That is totally fine. The map itself is not dynamic on purpose and is there to optimize TypeScript to make iteration convenient and efficient. In essence, it's there to teach TypeScript how to count. The Next and Prev operators operate through it in the most efficient manner.

[millsp]

That would be a conclusive experiment to know if types like Reverse just work out of the box with tail call optimization.

[DetachHead]

@millsp ok i've updated IterationMap to range from -1000 to 1000, and also added a script to make it easier to modify the range in the future. i'll continue looking for and updating types to be tail-recursive within the next few days

[DetachHead]

is there a reason for using 0 and 1 instead of booleans? seems there's quite a lot of types that use if expressions like this

type Foo<T> = {
    0: 'foo'
    1: 'bar'
}[Condition<T>]

but i don't think that works for tail recursion optimization. is it purely for readability?

example: https://github.com/millsp/ts-toolbelt/pull/256/files#diff-a747cda6ab8a3309c860b34d3482041926331d171b3766eb1eb724b897573447L15-R18

[millsp]

Yes, it's because you can index with 0 and 1 but not true and false. The reason for this is that extends clauses are way more expensive than a deterministic index. That means that the compiler is able to flatten such types faster that with an extends clause.

[DetachHead]

ah cool i had no idea. so are you ok with me rewriting some of them to use extends in order to get the tail recursion optimization to work? in my opinion having a 10x higher stack depth outweighs the performance concerns. however from what i understand the optimization results in it evaluating the type more efficiently anyway, but i'm not sure how that compares to the key method

what are your thoughts?

[millsp]

however from what i understand the optimization results in it evaluating the type more efficiently anyway

I also think so. That means that this will be quite an amount of work. In the entry point of the lib, I provided a regex for finding all the recursive types - that will give us an idea of how much there is to do. I'll be happy to contribute on this PR with you :)

[DetachHead]

sounds good, i had a look through the codebase and yeah it seems like a lot more work than i initially thought and probably won't have the time to do it all myself so any help is appreciated