Tail recursive evaluation of conditional types (#45711)

ahejlsberg · web-flow · commit b9eeb74f3723 · 2021-09-08T15:42:09.000-07:00
* Implement tail-recursion for conditional types and lower general instantiation depth limit to 100

* Add tests

* Skip caching for tail recursive temporary conditional types
diff --git a/src/compiler/checker.ts b/src/compiler/checker.ts
@@ -15265,10 +15265,18 @@ namespace ts {
         function getConditionalType(root: ConditionalRoot, mapper: TypeMapper | undefined, aliasSymbol?: Symbol, aliasTypeArguments?: readonly Type[]): Type {
             let result;
             let extraTypes: Type[] | undefined;
+            let tailCount = 0;
             // We loop here for an immediately nested conditional type in the false position, effectively treating
             // types of the form 'A extends B ? X : C extends D ? Y : E extends F ? Z : ...' as a single construct for
-            // purposes of resolution. This means such types aren't subject to the instantiation depth limiter.
+            // purposes of resolution. We also loop here when resolution of a conditional type ends in resolution of
+            // another (or, through recursion, possibly the same) conditional type. In the potentially tail-recursive
+            // cases we increment the tail recursion counter and stop after 1000 iterations.
             while (true) {
+                if (tailCount === 1000) {
+                    error(currentNode, Diagnostics.Type_instantiation_is_excessively_deep_and_possibly_infinite);
+                    result = errorType;
+                    break;
+                }
                 const isUnwrapped = isTypicalNondistributiveConditional(root);
                 const checkType = instantiateType(unwrapNondistributiveConditionalTuple(root, getActualTypeVariable(root.checkType)), mapper);
                 const checkTypeInstantiable = isGenericType(checkType);
@@ -15312,6 +15320,9 @@ namespace ts {
                                 root = newRoot;
                                 continue;
                             }
+                            if (canTailRecurse(falseType, mapper)) {
+                                continue;
+                            }
                         }
                         result = instantiateType(falseType, mapper);
                         break;
@@ -15322,7 +15333,12 @@ namespace ts {
                     //   type Foo<T extends { x: any }> = T extends { x: string } ? string : number
                     // doesn't immediately resolve to 'string' instead of being deferred.
                     if (inferredExtendsType.flags & TypeFlags.AnyOrUnknown || isTypeAssignableTo(getRestrictiveInstantiation(checkType), getRestrictiveInstantiation(inferredExtendsType))) {
-                        result = instantiateType(getTypeFromTypeNode(root.node.trueType), combinedMapper || mapper);
+                        const trueType = getTypeFromTypeNode(root.node.trueType);
+                        const trueMapper = combinedMapper || mapper;
+                        if (canTailRecurse(trueType, trueMapper)) {
+                            continue;
+                        }
+                        result = instantiateType(trueType, trueMapper);
                         break;
                     }
                 }
@@ -15338,6 +15354,32 @@ namespace ts {
                 break;
             }
             return extraTypes ? getUnionType(append(extraTypes, result)) : result;
+            // We tail-recurse for generic conditional types that (a) have not already been evaluated and cached, and
+            // (b) are non distributive, have a check type that is unaffected by instantiation, or have a non-union check
+            // type. Note that recursion is possible only through aliased conditional types, so we only increment the tail
+            // recursion counter for those.
+            function canTailRecurse(newType: Type, newMapper: TypeMapper | undefined) {
+                if (newType.flags & TypeFlags.Conditional && newMapper) {
+                    const newRoot = (newType as ConditionalType).root;
+                    if (newRoot.outerTypeParameters) {
+                        const typeParamMapper = combineTypeMappers((newType as ConditionalType).mapper, newMapper);
+                        const typeArguments = map(newRoot.outerTypeParameters, t => getMappedType(t, typeParamMapper));
+                        const newRootMapper = createTypeMapper(newRoot.outerTypeParameters, typeArguments);
+                        const newCheckType = newRoot.isDistributive ? getMappedType(newRoot.checkType, newRootMapper) : undefined;
+                        if (!newCheckType || newCheckType === newRoot.checkType || !(newCheckType.flags & (TypeFlags.Union | TypeFlags.Never))) {
+                            root = newRoot;
+                            mapper = newRootMapper;
+                            aliasSymbol = undefined;
+                            aliasTypeArguments = undefined;
+                            if (newRoot.aliasSymbol) {
+                                tailCount++;
+                            }
+                            return true;
+                        }
+                    }
+                }
+                return false;
+            }
         }
 
         function getTrueTypeFromConditionalType(type: ConditionalType) {
@@ -16358,8 +16400,8 @@ namespace ts {
             if (!couldContainTypeVariables(type)) {
                 return type;
             }
-            if (instantiationDepth === 500 || instantiationCount >= 5000000) {
-                // We have reached 500 recursive type instantiations, or 5M type instantiations caused by the same statement
+            if (instantiationDepth === 100 || instantiationCount >= 5000000) {
+                // We have reached 100 recursive type instantiations, or 5M type instantiations caused by the same statement
                 // or expression. There is a very high likelyhood we're dealing with a combination of infinite generic types
                 // that perpetually generate new type identities, so we stop the recursion here by yielding the error type.
                 tracing?.instant(tracing.Phase.CheckTypes, "instantiateType_DepthLimit", { typeId: type.id, instantiationDepth, instantiationCount });
diff --git a/tests/baselines/reference/tailRecursiveConditionalTypes.js b/tests/baselines/reference/tailRecursiveConditionalTypes.js
@@ -0,0 +1,49 @@
+//// [tailRecursiveConditionalTypes.ts]
+type Trim<S extends string> =
+    S extends ` ${infer T}` ? Trim<T> :
+    S extends `${infer T} ` ? Trim<T> :
+    S;
+
+type T10 = Trim<'                                                                                                                                                hello '>;
+type T11 = Trim<' hello                                                                                                                                                '>;
+
+type GetChars<S> = GetCharsRec<S, never>;
+type GetCharsRec<S, Acc> =
+    S extends `${infer Char}${infer Rest}` ? GetCharsRec<Rest, Char | Acc> : Acc;
+
+type T20 = GetChars<'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789'>;
+
+type Reverse<T> = any[] extends T ? T : ReverseRec<T, []>;
+type ReverseRec<T, Acc extends unknown[]> =
+    T extends [infer Head, ...infer Tail] ? ReverseRec<Tail, [Head, ...Acc]> : Acc;
+
+type T30 = Reverse<[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]>;
+type T31 = Reverse<string[]>;
+
+type TupleOf<T, N extends number> = number extends N ? T[] : TupleOfRec<T, N, []>;
+type TupleOfRec<T, N extends number, Acc extends unknown[]> =
+    Acc["length"] extends N ? Acc : TupleOfRec<T, N, [T, ...Acc]>;
+
+type T40 = TupleOf<any, 200>;
+type T41 = TupleOf<any, number>;
+
+
+//// [tailRecursiveConditionalTypes.js]
+"use strict";
+
+
+//// [tailRecursiveConditionalTypes.d.ts]
+declare type Trim<S extends string> = S extends ` ${infer T}` ? Trim<T> : S extends `${infer T} ` ? Trim<T> : S;
+declare type T10 = Trim<'                                                                                                                                                hello '>;
+declare type T11 = Trim<' hello                                                                                                                                                '>;
+declare type GetChars<S> = GetCharsRec<S, never>;
+declare type GetCharsRec<S, Acc> = S extends `${infer Char}${infer Rest}` ? GetCharsRec<Rest, Char | Acc> : Acc;
+declare type T20 = GetChars<'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789'>;
+declare type Reverse<T> = any[] extends T ? T : ReverseRec<T, []>;
+declare type ReverseRec<T, Acc extends unknown[]> = T extends [infer Head, ...infer Tail] ? ReverseRec<Tail, [Head, ...Acc]> : Acc;
+declare type T30 = Reverse<[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]>;
+declare type T31 = Reverse<string[]>;
+declare type TupleOf<T, N extends number> = number extends N ? T[] : TupleOfRec<T, N, []>;
+declare type TupleOfRec<T, N extends number, Acc extends unknown[]> = Acc["length"] extends N ? Acc : TupleOfRec<T, N, [T, ...Acc]>;
+declare type T40 = TupleOf<any, 200>;
+declare type T41 = TupleOf<any, number>;
diff --git a/tests/baselines/reference/tailRecursiveConditionalTypes.symbols b/tests/baselines/reference/tailRecursiveConditionalTypes.symbols
@@ -0,0 +1,118 @@
+=== tests/cases/compiler/tailRecursiveConditionalTypes.ts ===
+type Trim<S extends string> =
+>Trim : Symbol(Trim, Decl(tailRecursiveConditionalTypes.ts, 0, 0))
+>S : Symbol(S, Decl(tailRecursiveConditionalTypes.ts, 0, 10))
+
+    S extends ` ${infer T}` ? Trim<T> :
+>S : Symbol(S, Decl(tailRecursiveConditionalTypes.ts, 0, 10))
+>T : Symbol(T, Decl(tailRecursiveConditionalTypes.ts, 1, 23))
+>Trim : Symbol(Trim, Decl(tailRecursiveConditionalTypes.ts, 0, 0))
+>T : Symbol(T, Decl(tailRecursiveConditionalTypes.ts, 1, 23))
+
+    S extends `${infer T} ` ? Trim<T> :
+>S : Symbol(S, Decl(tailRecursiveConditionalTypes.ts, 0, 10))
+>T : Symbol(T, Decl(tailRecursiveConditionalTypes.ts, 2, 22))
+>Trim : Symbol(Trim, Decl(tailRecursiveConditionalTypes.ts, 0, 0))
+>T : Symbol(T, Decl(tailRecursiveConditionalTypes.ts, 2, 22))
+
+    S;
+>S : Symbol(S, Decl(tailRecursiveConditionalTypes.ts, 0, 10))
+
+type T10 = Trim<'                                                                                                                                                hello '>;
+>T10 : Symbol(T10, Decl(tailRecursiveConditionalTypes.ts, 3, 6))
+>Trim : Symbol(Trim, Decl(tailRecursiveConditionalTypes.ts, 0, 0))
+
+type T11 = Trim<' hello                                                                                                                                                '>;
+>T11 : Symbol(T11, Decl(tailRecursiveConditionalTypes.ts, 5, 170))
+>Trim : Symbol(Trim, Decl(tailRecursiveConditionalTypes.ts, 0, 0))
+
+type GetChars<S> = GetCharsRec<S, never>;
+>GetChars : Symbol(GetChars, Decl(tailRecursiveConditionalTypes.ts, 6, 170))
+>S : Symbol(S, Decl(tailRecursiveConditionalTypes.ts, 8, 14))
+>GetCharsRec : Symbol(GetCharsRec, Decl(tailRecursiveConditionalTypes.ts, 8, 41))
+>S : Symbol(S, Decl(tailRecursiveConditionalTypes.ts, 8, 14))
+
+type GetCharsRec<S, Acc> =
+>GetCharsRec : Symbol(GetCharsRec, Decl(tailRecursiveConditionalTypes.ts, 8, 41))
+>S : Symbol(S, Decl(tailRecursiveConditionalTypes.ts, 9, 17))
+>Acc : Symbol(Acc, Decl(tailRecursiveConditionalTypes.ts, 9, 19))
+
+    S extends `${infer Char}${infer Rest}` ? GetCharsRec<Rest, Char | Acc> : Acc;
+>S : Symbol(S, Decl(tailRecursiveConditionalTypes.ts, 9, 17))
+>Char : Symbol(Char, Decl(tailRecursiveConditionalTypes.ts, 10, 22))
+>Rest : Symbol(Rest, Decl(tailRecursiveConditionalTypes.ts, 10, 35))
+>GetCharsRec : Symbol(GetCharsRec, Decl(tailRecursiveConditionalTypes.ts, 8, 41))
+>Rest : Symbol(Rest, Decl(tailRecursiveConditionalTypes.ts, 10, 35))
+>Char : Symbol(Char, Decl(tailRecursiveConditionalTypes.ts, 10, 22))
+>Acc : Symbol(Acc, Decl(tailRecursiveConditionalTypes.ts, 9, 19))
+>Acc : Symbol(Acc, Decl(tailRecursiveConditionalTypes.ts, 9, 19))
+
+type T20 = GetChars<'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789'>;
+>T20 : Symbol(T20, Decl(tailRecursiveConditionalTypes.ts, 10, 81))
+>GetChars : Symbol(GetChars, Decl(tailRecursiveConditionalTypes.ts, 6, 170))
+
+type Reverse<T> = any[] extends T ? T : ReverseRec<T, []>;
+>Reverse : Symbol(Reverse, Decl(tailRecursiveConditionalTypes.ts, 12, 86))
+>T : Symbol(T, Decl(tailRecursiveConditionalTypes.ts, 14, 13))
+>T : Symbol(T, Decl(tailRecursiveConditionalTypes.ts, 14, 13))
+>T : Symbol(T, Decl(tailRecursiveConditionalTypes.ts, 14, 13))
+>ReverseRec : Symbol(ReverseRec, Decl(tailRecursiveConditionalTypes.ts, 14, 58))
+>T : Symbol(T, Decl(tailRecursiveConditionalTypes.ts, 14, 13))
+
+type ReverseRec<T, Acc extends unknown[]> =
+>ReverseRec : Symbol(ReverseRec, Decl(tailRecursiveConditionalTypes.ts, 14, 58))
+>T : Symbol(T, Decl(tailRecursiveConditionalTypes.ts, 15, 16))
+>Acc : Symbol(Acc, Decl(tailRecursiveConditionalTypes.ts, 15, 18))
+
+    T extends [infer Head, ...infer Tail] ? ReverseRec<Tail, [Head, ...Acc]> : Acc;
+>T : Symbol(T, Decl(tailRecursiveConditionalTypes.ts, 15, 16))
+>Head : Symbol(Head, Decl(tailRecursiveConditionalTypes.ts, 16, 20))
+>Tail : Symbol(Tail, Decl(tailRecursiveConditionalTypes.ts, 16, 35))
+>ReverseRec : Symbol(ReverseRec, Decl(tailRecursiveConditionalTypes.ts, 14, 58))
+>Tail : Symbol(Tail, Decl(tailRecursiveConditionalTypes.ts, 16, 35))
+>Head : Symbol(Head, Decl(tailRecursiveConditionalTypes.ts, 16, 20))
+>Acc : Symbol(Acc, Decl(tailRecursiveConditionalTypes.ts, 15, 18))
+>Acc : Symbol(Acc, Decl(tailRecursiveConditionalTypes.ts, 15, 18))
+
+type T30 = Reverse<[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]>;
+>T30 : Symbol(T30, Decl(tailRecursiveConditionalTypes.ts, 16, 83))
+>Reverse : Symbol(Reverse, Decl(tailRecursiveConditionalTypes.ts, 12, 86))
+
+type T31 = Reverse<string[]>;
+>T31 : Symbol(T31, Decl(tailRecursiveConditionalTypes.ts, 18, 171))
+>Reverse : Symbol(Reverse, Decl(tailRecursiveConditionalTypes.ts, 12, 86))
+
+type TupleOf<T, N extends number> = number extends N ? T[] : TupleOfRec<T, N, []>;
+>TupleOf : Symbol(TupleOf, Decl(tailRecursiveConditionalTypes.ts, 19, 29))
+>T : Symbol(T, Decl(tailRecursiveConditionalTypes.ts, 21, 13))
+>N : Symbol(N, Decl(tailRecursiveConditionalTypes.ts, 21, 15))
+>N : Symbol(N, Decl(tailRecursiveConditionalTypes.ts, 21, 15))
+>T : Symbol(T, Decl(tailRecursiveConditionalTypes.ts, 21, 13))
+>TupleOfRec : Symbol(TupleOfRec, Decl(tailRecursiveConditionalTypes.ts, 21, 82))
+>T : Symbol(T, Decl(tailRecursiveConditionalTypes.ts, 21, 13))
+>N : Symbol(N, Decl(tailRecursiveConditionalTypes.ts, 21, 15))
+
+type TupleOfRec<T, N extends number, Acc extends unknown[]> =
+>TupleOfRec : Symbol(TupleOfRec, Decl(tailRecursiveConditionalTypes.ts, 21, 82))
+>T : Symbol(T, Decl(tailRecursiveConditionalTypes.ts, 22, 16))
+>N : Symbol(N, Decl(tailRecursiveConditionalTypes.ts, 22, 18))
+>Acc : Symbol(Acc, Decl(tailRecursiveConditionalTypes.ts, 22, 36))
+
+    Acc["length"] extends N ? Acc : TupleOfRec<T, N, [T, ...Acc]>;
+>Acc : Symbol(Acc, Decl(tailRecursiveConditionalTypes.ts, 22, 36))
+>N : Symbol(N, Decl(tailRecursiveConditionalTypes.ts, 22, 18))
+>Acc : Symbol(Acc, Decl(tailRecursiveConditionalTypes.ts, 22, 36))
+>TupleOfRec : Symbol(TupleOfRec, Decl(tailRecursiveConditionalTypes.ts, 21, 82))
+>T : Symbol(T, Decl(tailRecursiveConditionalTypes.ts, 22, 16))
+>N : Symbol(N, Decl(tailRecursiveConditionalTypes.ts, 22, 18))
+>T : Symbol(T, Decl(tailRecursiveConditionalTypes.ts, 22, 16))
+>Acc : Symbol(Acc, Decl(tailRecursiveConditionalTypes.ts, 22, 36))
+
+type T40 = TupleOf<any, 200>;
+>T40 : Symbol(T40, Decl(tailRecursiveConditionalTypes.ts, 23, 66))
+>TupleOf : Symbol(TupleOf, Decl(tailRecursiveConditionalTypes.ts, 19, 29))
+
+type T41 = TupleOf<any, number>;
+>T41 : Symbol(T41, Decl(tailRecursiveConditionalTypes.ts, 25, 29))
+>TupleOf : Symbol(TupleOf, Decl(tailRecursiveConditionalTypes.ts, 19, 29))
+
diff --git a/tests/baselines/reference/tailRecursiveConditionalTypes.types b/tests/baselines/reference/tailRecursiveConditionalTypes.types
@@ -0,0 +1,53 @@
+=== tests/cases/compiler/tailRecursiveConditionalTypes.ts ===
+type Trim<S extends string> =
+>Trim : Trim<S>
+
+    S extends ` ${infer T}` ? Trim<T> :
+    S extends `${infer T} ` ? Trim<T> :
+    S;
+
+type T10 = Trim<'                                                                                                                                                hello '>;
+>T10 : "hello"
+
+type T11 = Trim<' hello                                                                                                                                                '>;
+>T11 : "hello"
+
+type GetChars<S> = GetCharsRec<S, never>;
+>GetChars : GetChars<S>
+
+type GetCharsRec<S, Acc> =
+>GetCharsRec : GetCharsRec<S, Acc>
+
+    S extends `${infer Char}${infer Rest}` ? GetCharsRec<Rest, Char | Acc> : Acc;
+
+type T20 = GetChars<'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789'>;
+>T20 : "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" | "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z" | "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
+
+type Reverse<T> = any[] extends T ? T : ReverseRec<T, []>;
+>Reverse : Reverse<T>
+
+type ReverseRec<T, Acc extends unknown[]> =
+>ReverseRec : ReverseRec<T, Acc>
+
+    T extends [infer Head, ...infer Tail] ? ReverseRec<Tail, [Head, ...Acc]> : Acc;
+
+type T30 = Reverse<[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]>;
+>T30 : [9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
+
+type T31 = Reverse<string[]>;
+>T31 : string[]
+
+type TupleOf<T, N extends number> = number extends N ? T[] : TupleOfRec<T, N, []>;
+>TupleOf : TupleOf<T, N>
+
+type TupleOfRec<T, N extends number, Acc extends unknown[]> =
+>TupleOfRec : TupleOfRec<T, N, Acc>
+
+    Acc["length"] extends N ? Acc : TupleOfRec<T, N, [T, ...Acc]>;
+
+type T40 = TupleOf<any, 200>;
+>T40 : [any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any]
+
+type T41 = TupleOf<any, number>;
+>T41 : any[]
+
diff --git a/tests/cases/compiler/tailRecursiveConditionalTypes.ts b/tests/cases/compiler/tailRecursiveConditionalTypes.ts
