Regression: type guard function returning recursive utility type fails to apply the second time

[jcalz]

Bug Report

🔎 Search Terms

recursive nested conditional type guard function

🕗 Version & Regression Information

• This changed between versions 5.1.0-dev.20230303 and 5.1.0-dev.20230304

⏯ Playground Link

Playground link with relevant code

💻 Code

type NestedRecord<K extends string, V> =
  K extends `${infer K0}.${infer KR}` ?
  { [P in K0]: NestedRecord<KR, V> } :
  { [P in K]: V };

declare function guardPathX<T>(x: T): x is T & NestedRecord<'a.b.x.c', string>;
declare function guardPathY<T>(x: T): x is T & NestedRecord<'a.b.y.c', string>;

function foo(obj: {}) {
  if (guardPathX(obj) && guardPathY(obj)) {
    obj.a.b.x.c.toUpperCase(); // okay
    obj.a.b.y.c.toUpperCase(); // <-- error, what?
  }
}

🙁 Actual behavior

obj has been narrowed only to {a:{b:{x:{c: string}}}}.

🙂 Expected behavior

obj should be narrowed to {a:{b:{x:{c: string}}}} & {a:{b:{y:{c: string}}}}.

---

This is a weird one. Seems to be caused by the recursive NestedRecord utility type (if I replace that with hardcoded types it works) interacting with multiple type guard applications. Probably hitting some limit somewhere where it gives up? Or an inaccurate variance shortcut? Not sure. Anyway this broke some Stack Overflow answer I was working on and it would be nice to know what's up with it.

[Andarist]

Regression introduced by #52984

[Andarist]

@jcalz could you also share the code with hardcoded types that works?

[jcalz]

declare function guardPathX<T>(x: T): x is T & { a: { b: { x: { c: string; }; }; }; }
declare function guardPathY<T>(x: T): x is T & { a: { b: { y: { c: string; }; }; }; }
function foo(obj: {}) {
  if (guardPathX(obj) && guardPathY(obj)) {
    obj.a.b.x.c.toUpperCase(); // okay
    obj.a.b.y.c.toUpperCase(); // okay
  }
}

Playground link

[Andarist]

So the problem is that the resulting types are classified as "maybe" related and thus isTypeStrictSubtypeOf returns true and t gets chosen where:

t // { a: { b: { x: { c: string; }; }; }; }
c // { a: { b: { x: { c: string; }; }; }; } & { a: { b: { y: { c: string; }; }; }; }

You might ask, why those types are "maybe" related? This is assessed based on isDeeplyNestedType and getRecursionIdentity.

isDeeplyNested comes with a comment that mentions this:

    // [...] It is possible, though highly unlikely, for
    // the deeply nested check to be true in a situation where a chain of instantiations is not infinitely expanding.
    // Effectively, we will generate a false positive when two types are structurally equal to at least maxDepth levels,
    // but unequal at some level beyond that.

And this example here hits exactly the "highly unlikely" case 😅 All of the objects on the sourceStack (and on the targetStack similarly, but in there we also have to deal with intersections) share the same recursion identity because that is grabbed from the type.symbol:
https://github.dev/microsoft/TypeScript/blob/8fae437660ba89353fc7104beae8c6856528e5b6/src/compiler/checker.ts#L22984-L22988

All of those objects share this information as they are computed based on the same recursive type (the declaration of this symbol is { [P in K0]: NestedRecord<KR, V> })

cc @ahejlsberg

[ahrjarrett]

@Andarist is there a workaround for this?

The problem I'm running into in #55535 is actually worse than I thought -- as far as I can tell, the type checker silently turns off past a depth of 3 for types that are recursively generated.

This is happening silently -- which makes me think that the change you linked (where the check for isTypeIdenticalTo was removed) might have changed this from being a "highly unlikely" case to being "somewhat common".

It's also quite difficult to identify that type-checking is not happening at all, which makes me think that this could be a serious issue (since even when a runtime exception is thrown, which is the only way you'd discover that there might be a problem, there's still no indication by looking at the types that they don't actually check anything).

Which makes me think that any bugs that this is creating are not getting reported, or are being reported as something else.

[ahrjarrett]

To clarify, I'm trying to figure out how to write a recursively mapped type so that the output still type-checks past a depth of 3.

https://tsplay.dev/Wvy3rm

If I don't have a way to do this, I'm not sure what to explore next... possibly writing an eslint rule that bans recursively mapped types altogether? Otherwise, I'm not sure how to trust that the type my IDE shows me is actually what gets type checked.

[ahejlsberg]

This one is really tricky. We lack the ability to recognize that the NestedRecord conditional type will eventually terminate. Therefore we need a mechanism to limit runaway recursion, and our approach is to terminate after three recursive instantiations of the same type with an assumption that the result may be true (because we know it to be true to at least three levels). Lacking any information to say otherwise, we take that to be adequate proof. This isn't perfect, but the alternative is generally worse.

One way to extend the depth we explore recursive type instantiations is to have a circular ladder:

type NestedRecord<K extends string, V> =
  K extends `${infer K0}.${infer KR}` ?
  { [P in K0]: NestedRecord1<KR, V> } :
  { [P in K]: V };

type NestedRecord1<K extends string, V> =
  K extends `${infer K0}.${infer KR}` ?
  { [P in K0]: NestedRecord2<KR, V> } :
  { [P in K]: V };

type NestedRecord2<K extends string, V> =
  K extends `${infer K0}.${infer KR}` ?
  { [P in K0]: NestedRecord<KR, V> } :
  { [P in K]: V };

Each type adds another three levels of possible nesting. That's probably the best workaround.