531 - String to Union

[swimmie0]

Question

String to Union

Solution

type StringToUnion<T extends string> = T extends ''
  ? never
  : T extends `${infer X}${infer R}`
  ? R extends ''
    ? X
    : X | StringToUnion<R>
  : T;

Better Solution

type StringToUnion<T extends string> 
   = T extends `${infer A}${infer B}` ? A | StringToUnion<B> : never;

• empty string ''는 첫번째 condition ${infer A}${infer B} 에서 제외된다. infer 키워드는 타입 추론이 가능한 variable을 반환한다는 점을 고려하자.

type Pass = '' extends `${infer X}` ? X : never; // ''
type NotPass = '' extends `${infer X}${infer Y}` ? X : never; // never

Optimized Solution (in a tail recursive form)

type StringToUnion3<T extends string> = StringToUnionHelper<T, never>;
type StringToUnionHelper<T, Acc> = T extends `${infer X}${infer R}` ? StringToUnionHelper<R, X | Acc> : Acc;   

• TS 4.5 버전부터 재귀적 타입 추론에 대한 Tail-Recursion Elimination (재귀문을 반복문의 형태로 재구성하는 최적화) 이 구현되었다. TRE는 Tail-Recursive 형태로 구현된 함수에 한해 수행될 수 있기 때문에 다음과 같이 작성하는 것이 좋다. #

• Tail-Recursive 형태로 작성된다는 것은, '조건문의 결과가 연산에 사용되지 않고 바로 반환되도록', 즉 인자로 넘기는 Acc 제네릭에 계산한 값을 저장한 후 값을 한번에 반환하도록 하면 된다.

• A | StringToUnion<B> : never 👉 StringToUnionHelper<R, X | Acc> : Acc

• 참고) 긴 문자열에 대한 TrimLeft 타입 예시 : TS 4.5 이상 버전, TS 4.5 이하 버전

TypeScript often needs to gracefully fail when it detects possibly infinite recursion, or any type expansions that can take a long time and affect your editor experience. TypeScript는 무한 재귀 가능성이 있거나 시간이 오래 걸리고 편집기 환경에 영향을 줄 수 있는 모든 유형 확장을 탐지할 때 종종 정상적으로 실패합니다.

But there’s a saving grace: TrimLeft is written in a way that is tail-recursive in one branch. When it calls itself again, it immediately returns the result and doesn’t do anything with it. Because these types don’t need to create any intermediate results, they can be implemented more quickly and in a way that avoids triggering many of type recursion heuristics that are built into TypeScript.

That’s why TypeScript 4.5 performs some tail-recursion elimination on conditional types. As long as one branch of a conditional type is simply another conditional type, TypeScript can avoid intermediate instantiations. There are still heuristics to ensure that these types don’t go off the rails, but they are much more generous.

# Specifically, when a conditional type ends in another (or, through recursion, another instantiation of the same) conditional type, the compiler now performs type resolution in a loop that consumes no extra call stack. We permit evaluation of such types to loop 1000 times before we consider the type non-terminating and issue an error.