I'm trying to improve my knowledge of types in typescript, so I'm doing some type challenges. One of the challenges is to make a type that capitalises a generic string, as shown below (here).
type capitalized = CapitalizeWords<'hello world, my friends'> // expected to be 'Hello World, My Friends'
Although I have solved this now, my first attempt resulted in type instatiation too deep and possibly infinite. I redid the problem with some online help, but just looking at the code differences, the their is the same amount of recursion. As a result, I don't understand why one fails, and the other succeeds. I also suspect that for a sufficiently large string, the second type will also fail. However, I don't know how to predict how long a string would make it fail.
This was my first attempt at making a capitalised words type.
type CapitalizeWords<S extends string, C extends boolean = true> =
S extends `${infer A}${infer B}`
? Lowercase<A> extends Uppercase<A>
? `${A}${CapitalizeWords<B, true>}`
: C extends true
? `${Uppercase<A>}${CapitalizeWords<B, false>}`
: `${A}${CapitalizeWords<B, false>}`
: S
It works on small strings, (e.g. hello world), but fails with longer strings (e.g.aa!bb@cc#dd$ee%ff^gg&hh*ii(jj)kk_ll+mm{nn}oo|pp🤣qq) with type instatiation too deep and possibly infinite. My second attempt, with some online help, was:
type CapitalizeWords<S extends string, W extends string = ""> =
S extends `${infer A}${infer B}`
? Lowercase<A> extends Uppercase<A>
? `${Capitalize<W>}${A}${CapitalizeWords<B>}`
: CapitalizeWords<B, `${W}${A}`>
: Capitalize<W>
This works for the longer string. However, this looks like the same level of recursion to me (one level per char), so I don't understand why this one is fine.
Looking elsewhere online, this question (and others) sidesteps the issue and simply cuts the level of recursion, or defering evaluation. This does not help me predict why different methods may be more forgiving, or how much recursion I can allow.
In general it's hard to predict exactly how and when TypeScript will decide that a type instantiation is too deep. It depends on the details of how TypeScript evaluates types, and if it decides to do something eagerly where you expected it to defer evaluation, you can easily get an unexpected circularity warning. It's a hard problem. In general.
But for the specific type you're talking about, the issue is that you're using a recursive conditional type, and generally those are only allowed to recurse about 50 (or is it 100?) levels deep before TypeScript decides to stop evaluation. If you want to be able to write a deeper recursive conditional type, you should rewrite it to be tail recursive, meaning that the recursion should only happen at the "top level" of the evaluated expression. TypeScript is able to optimize tail-recursive conditional types and will allow you to recurse up to 1000 levels deep before bailing out.
In your original CapitalizeWords, all of your recursive calls of CapitalizedWords appear embedded within some other expression and are therefore not tail-recursive. You have `${A}${CapitalizeWords<B, true>}` and `${Uppercase<A>}${CapitalizeWords<B, false>}` and `${A}${CapitalizeWords<B, false>}`, all of which require TypeScript to build up a stack of partially evaluated template literal types. So we can expect long strings to fail.
Your updated CapitalizeWords improves this by having CapitalizeWords<B, `${W}${A}`> appear in the top-level or tail position. But it still has a `${Capitalize<W>}${A}${CapitalizeWords<B>}` so I'd expect it to be unable to recurse too deeply if that path is chosen. Presumably this only happens if you have lots of non-letters in a row (where a "non-letter" is approximated by a character that doesn't change when you Uppercase or Lowercase it), so maybe it doesn't come up in practice.
For a truly tail-recusive version of CapitalizeWords I'd suggest writing it like
type CapitalizeWords<T extends string, A extends string = ""> =
T extends `${infer F}${infer R}` ?
CapitalizeWords<Lowercase<F> extends Uppercase<F> ? Capitalize<R> : R, `${A}${F}`> :
Capitalize<A>;
You can see that there's only one recursive call to CapitalizeWords, and it only appears in tail position. The entire calculation takes place within the type arguments to CapitalizeWords:
type Capitalized = CapitalizeWords<'hello world, my friends'>
// type Capitalized = "Hello World, My Friends"
type Z = CapitalizeWords<".........................................................\
................................................................">
// okay
type Y = CapitalizeWords<"it was the best of times, it was the worst of times,\
it was the age of wisdom, it was the age of foolishness,\
it was the epoch of belief, it was the epoch of incredulity,\
it was the season of light, it was the season of darkness,\
it was the spring of hope, it was the winter of despair.">
/* type Y = "It Was The Best Of Times, It Was The Worst Of Times,\
It Was The Age Of Wisdom, It Was The Age Of Foolishness,\
It Was The Epoch Of Belief, It Was The Epoch Of Incredulity,\
It Was The Season Of Light, It Was The Season Of Darkness,\
It Was The Spring Of Hope, It Was The Winter Of Despair." */