Assignability false positive for recursive mapped types, even when fully instantiated

[ahrjarrett]

🔎 Search Terms

recursive mapped types, assignability, depth check, deeply nested

🕗 Version & Regression Information

If this is in fact a bug, it looks like it was introduced in v4.5

• This can cause a runtime error when using incompatible values whose types are derived from recursive mapped types with more than 2 levels of nesting because the compiler seems to consider them equal (even when the derived type is fully instantiated (not infinite)).
• This changed between versions v4.4 and v4.5

⏯ Playground Link

https://tsplay.dev/WoM1gN

💻 Code

type Id<T> = { [K in keyof T]: Id<T[K]> }

type HasNumeric = Id<{ x: { y: { z: number } } }>
//   ^? type HasNumeric = { x: { y: { z: number } } }

type HasString = Id<{ x: { y: { z: string } } }>
//   ^? type HasString = { x: { y: { z: string } } }

const toDollarsAndCents = (_: HasNumeric): string => _.x.y.z.toFixed(2)

declare const illegalValue: HasString
//            ^? const illegalValue:  { x: { y: { z: string } } }
 
/** 😵 */
toDollarsAndCents(illegalValue) 

🙁 Actual behavior

I passed a value known by the compiler to be of type { x: { y: { z: string } } } to a function expecting { x: { y: { z: number } } } and did not get a compile time error warning me about it.

🙂 Expected behavior

I expect to get a compile time error when I pass a value known by the compiler to be of type { x: { y: { z: string } } } to a function expecting { x: { y: { z: number } } }

Additional information about the issue

Hey team! First of all, thank you for your work on this project. I have used TypeScript every day for years, and since the release of v5 in particular, saw a noticeable increase in my productivity at work :)

Regarding this issue, after further testing, it seems pretty trivial to reproduce with any recursive mapped type more than 2 levels deep (even with a "no-op" transformation, as is the case with Id).

Even if the type were not fully instantiated, the assignability rules in this case seem to work exactly backwards from what I'd expect, which makes me think this might not be the intended behavior.

This issue might be related to #46599, which fits given that the playground's type-checker does complain in v4.4

Let me know if there's anything you'd like me to elaborate on!

[fatcerberus]

Possibly related to #35533

[Andarist]

I'm glad that you mentioned this:

types are derived from recursive mapped types with more than 2 levels of nesting

as it immediately pointed me to the right place in the code. 😉

Those objects are classified as maybe related. 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.

So, you are hitting this "highly unlikely" (😜) scenario here.

I already was debugging a similar-ish case in the past, see the comment here

cc @ahejlsberg

[webstrand]

It has become somewhat popular to use a type like

type Expand<T> = T extends string | number | symbol 
                         | bigint | null | undefined | Function 
    ? T 
    : { [P in keyof T]: T[P] };

to force typescript to show actual structure of the provided type, rather than opaque aliases, in typescript tooltips. This may contribute to people hitting this issue.

[ssalbdivad]

@Andarist Definitely feels like the threshold for "deeply" nested should be higher than 3 given this, but maybe more importantly, is it possible to give a potential false negative instead of a false positive in this case?

I'd much rather two types that were actually structurally identical not be mutually assignable than have two types be assignable that shouldn't be.

[ahrjarrett]

@RyanCavanaugh made a comment here that has me thinking I'm missing something. He said,

The root cause here is that we need to bail out at some point during nested evaluation of a type, since we have no way to know that we're not encountering an infinitely generatively-nested recursive type...

Looking at the example I shared, TypeScript seems to fully know that HasNumeric is a { x: { y: { z: number } } }, and that HasString is a { x: { y: { z: string } } }.

Given that HasNumeric and HasString have already been fully evaluated by the compiler (and that toDollarsAndCents does not depend on a type parameter), I can't help but wonder: where in the code sample I provided is there a possibly-infinite type?

[Andarist]

Note that TS really has to "fully know" what those 2 are when it compares them. Types are often lazily evaluated. So what might fully evaluate them is the fact that you hover over the related symbol in your IDE (the compiler has to evaluate them at this point - if it didn't do that already - since it has to print their content). I didn't recheck if that's the case here or not - jus saying that "fully evaluated" in this context isn't exactly the right mental model for how the compiler works.

[ssalbdivad]

@Andarist Ideally, whatever TS deems worth computing for an assignment should be at least as thorough as what it computes for a hover, no?

Obviously missing the compiler-side context here but I took a look at the thread @ahrjarrett mentioned and it seems to me the fix should be clear:

• Treat types where this type of "bail-out" occurs as nominal
• Probably increase the depth to at least whatever is computed on hover

Neither of these seem like they'd be particularly complex. I suppose it could break some existing types but given that nothing is being enforced at that point anyways, it's more of a fix than a breaking change if anyone suddenly sees an assignment fail.

[fatcerberus]

From the linked issue, straight from the mouth of the TS project lead:

Fair warning: if we had any idea how to fix this, it wouldn't be Cursed (and would have been fixed already). PRs surely welcomed but this isn't a case of us simply not having tried to fix it before.

[ahrjarrett]

@Andarist Ideally, whatever TS deems worth computing for an assignment should be at least as thorough as what it computes for a hover, no?

@fatcerberus I think an acceptable fix would actually be the opposite, and not show type information on hover if that information will never actually be used by the compiler type-checker.

[ahrjarrett]

@Andarist I'd also point out types like Id are often used because they seem to "force evaluation".

This, I just realized, seems to be the point that @webstrand made here.

Users are probably unaware that when they do this, that they're making a rather poor tradeoff, because by trying to "see" the underlying type, they're effectively (and unwittingly) erasing it altogether.

[ssalbdivad]

@fatcerberus I presumed he was referring to the difficulty of identifying structurally compatible recursively generative types.

I'm not suggesting any actual computational improvements, just different behavior when "giving up." It is possible that due to some design limitation, it's actually very hard to just treat the resulting type as nominal in that case, it's just hard to imagine.

[ssalbdivad]

@ahejlsberg I think this issue stemming from #46599 may be more significant than it might initially seem.

Consider the RequiredDeep type from type-fest. In accordance with the issue, we don't get any errors after the 3rd level of depth:

import { RequiredDeep } from "type-fest"

declare const b: RequiredDeep<{
    a: { b: { c: "B" } }
}>

const a: RequiredDeep<{
    a: { b: { c: "A" } }
    // no error
}> = b

These kinds of types are quite common, and this limitation is not difficult to run into. In fact, as far as I can tell, it is currently impossible to write a version of RequiredDeep that circumvents this problem. I think the reason we haven't heard more about this bug is exactly the reason it is so insidious- no normal form of type testing would catch this.

ArkType has hundreds of tests both snapshotting typeToString() results as well as comparing types directly for equivalency. This issue has always affected any ArkType definition that is more than 3 levels deep, but I'm just now learning about it because why would I write a test comparing two types that I can see serialize the way I expect and give type hints?

However, that doesn't mean there aren't potentially hundreds or thousands of errors out there being ignored as a result of this logic.

I understand these kinds of recursive structural comparisons are complex and perf-intensive, and having a depth cutoff is necessary. Is there any reason we can't adjust the behavior upon hitting this limit so that instead of allowing the mutual assignment, it fails?

The false negative here would be much more easily discovered and solved via a simple cast, unlike the current behavior which is extremely hard to find and seemingly impossible to resolve, even with knowledge of it.