Typescript fails to generate an error when comparing deeply nested TypeBox types

[sanderalvin]

🔎 Search Terms

"typebox no Typescript error"

🕗 Version & Regression Information

• This is a crash

⏯ Playground Link

https://www.typescriptlang.org/play?ts=5.3.0-dev.20231031#code/JYWwDg9gTgLgBAbzgZRgQxsAxgGjgFQE8wBTOAXzgDMoIQ4ByAAQGdgA7LAGzWCgHoYxEgCMIADwYBuAFAz+-OADkAgvgCSANQCicbQA0VAWQAKAGV0Baazdu25Q0ihBouXJRmAA3EkScBeRBk4ELguEh8uAEYALiDQhLCIki4AJjiEYMTsqggIOJYYKA4Ac1lskPJy0KqZWplHMgAhYBKPTB8-MkDMhPDI2PiK-pT0oYrQ3Py4QuL2MqyJkJE0KAKi0urs2oTa+oUCAHcIOAATEhIwLkI4dhJCklO4RpY4Eu8yLGgoEix4EigtCgMioAFdOJgIOxbp4fE1VgAKMCrNAgOLIFxudofLoAbQAugBKOItNqw3zCAnjOA-GCgqDQ5FQVGychyA52Tk2dmKfAATRM2iaAHl9HpDKYLHAuVyHMJnK4uF0xOIunBAqhPFgADyNCBUBVuZUSLoAPlkX3YhUNSuEKrVgS6ADphSIAFa-GAI3qhEbROLOlSAtCEBHO10ev7exaJP1jQPB0Ph92e6NLSZ5APCJ2oOYlBGEnAx3aEwsx8ilosV2QNeWk42q+Ua9CYHV6g31u0m4TmmSW62d0j2psEbMR1M+kJ+wYJ5lJscpqOT2PJNJZ0hOoNzsMLyNe5cTKbrkg5jbzAtF9PLVbH095i-FmqV8vP6s86jgv7AKHUPJIlFojaDZdMScCDqI3ZOJkBwhLS9KMgBsgHGy8iKAAwvSPzsDA1zPAAFsAryEXAHBfICnpOnA6jwCwoJgJALCPM8Jx4WgPhwACQJwGgRHQgAROw5LwlAfEceIqJXCQqFUQahAQKCcCfnQIAkNhcB8VMoloGIPgBgRryHMAbhvB8HGAtAcAImRPx-HAIgkKxXjflAhLSeosnyYpnDKap8AaXkon2VwECHHpxGGcZSjCvgJnsZxFkIqR3yenZDlsc5rlghC37QisUD-sygEYoqwGUkSJKtKVpBUsucEMnATIsnU75ZV+P5TAVqLopitpDpBJCgeBw5QdJsEkHS9WNSASGKChHIygtMhAA

💻 Code

import { Static, Type } from '@sinclair/typebox';

// NATIVE EXAMPLE --------------

type SmallNativeType = {
    level1: {
        level2: {
            foo: string;
        };
    };
};

type BigNativeType = {
    level1: {
        level2: {
            foo: string;
            bar: string;
        };
    };
};

// Two deeply nested types give correct error
function nativeBar(param: SmallNativeType[]): BigNativeType[] {
    return param;
}

// --------------

// TYPEBOX EXAMPLE --------------

type SmallTypeboxType = Static<typeof SmallTypeboxType>;
const SmallTypeboxType = Type.Object({
    level1: Type.Array(Type.Object({
        level2: Type.Array(Type.Object({
            foo: Type.String(),
        })),
    })),
});

type BigTypeboxType = Static<typeof BigTypeboxType>;
const BigTypeboxType = Type.Object({
    level1: Type.Array(Type.Object({
        level2: Type.Array(Type.Object({
            foo: Type.String(),
            bar: Type.String(),
        })),
    })),
});

// function foo(param: SmallTypeboxType): BigTypeboxType {
//   return param;
// }

// Currently this is incorrect. It supposed to have error as in "nativeBar" example
// If you uncomment "foo" above: This will give error (correct behavior)
// If you uncomment "foo" below: This will NOT give error (incorrect behavior)
function bar(param: SmallTypeboxType[]): BigTypeboxType[] {
    return param;
}

// function foo(param: SmallTypeboxType): BigTypeboxType {
//   return param;
// }

// ------------------

🙁 Actual behavior

No Typescript error generated on line 58 inside bar function.

🙂 Expected behavior

There should be an TS error on line 58 inside bar function just like there is a similar error inside nativeBar function on line 24.

Additional information about the issue

I first reported this issue to TypeBox repo, but I was advised that this is actually a Typescript problem.
Link to Typebox issue: sinclairzx81/typebox#636

[sanderalvin]

Some PR-s which are related to the reported issue:
#56169
#55638

A previous issue opened by TypeBox creator:
#56138

[fatcerberus]

TS failing to produce an expected error isn’t a crash.

[sinclairzx81]

When unwrapping the Array types, everything works fine on 5.3.0-dev.20231031. @RyanCavanaugh If it's helpful, the relevant TypeBox parts are inlined at the link below.

TypeScript Link Here

[ahejlsberg]

Problem here is that SmallTypeboxType and BigTypeboxType have three levels of nested Array<T> instances after which we consider the types deeply nested. The instances all originate in the same generic declaration (the static property in TArray) and we simply don't have a way to recognize that the instantiations eventually terminate.

[sinclairzx81]

@ahejlsberg Hi, thank you for taking the time to look into this.

Problem here is that SmallTypeboxType and BigTypeboxType have three levels of nested Array instances after which we consider the types deeply nested. The instances all originate in the same generic declaration (the static property in TArray) and we simply don't have a way to recognize that the instantiations eventually terminate.

I note that the use of (T & { params: P })['static'] on Static seems to be the source of these issues (which TypeBox is using for recursive inference); but was wondering if there might be a more compiler friendly way to uniformly handle recursive inference when applied to both recursive and non-recursive mapped types (somehow proving to the compiler in advance a type was finite when non-recursive)

Workarounds

Based on the above, I had experimented with a library level workaround to perform a forward query on the type searching for interior instances of TThis (indicating the type is recursive) and only perform the reverse inference if found, otherwise just use T['static']. This does allow nested Arrays to go very deep (8 levels and beyond) for finite types while retaining support for singular recursive inference (albeit with a possible inference performance hit)

Workaround 1 (Inline)

Workaround 2 (Integrated)

Recommendations

Honestly, I think the update on #56169 would likely solve the vast majority of cases (where I'd imagine deeply nested arrays of this form to be quite uncommon), but was wondering if there were recommendations from the TypeScript team for handling recursive mapped types in general; possibly approaches that would allow the compiler to quickly prove in advance a type was finite using something akin to the above HasThis<T> check.

Are there any recommendations for approaching recursive mapped inference?

[ahejlsberg]

I note that the use of (T & { params: P })['static'] on Static seems to be the source of these issues

It's actually a combination of things, most of which are implementation details of the compiler. The workarounds you present ultimately depend on the (implementation defined) order in which generic type instantiations are materialized.

When a type is materialized, it is assigned a type ID, which is simply a sequentially increasing number. When checking for deeply nested types, we only count types that have increasing type IDs because increasing IDs typically are an indication of some pattern of recursively occurring instantiations.

In the workarounds, the use of (recursive) inference in the Static conditional type causes types to be materialized inside-out, meaning that the deepest Array<T> instantiations have the lowest type IDs, and the types therefore don't appear to be deeply nested. But minor (and seemingly irrelevant) changes to the workarounds cause instantiation to instead occur outside-in (which would be typical because type instantiation is deferred for as long as possible).

So, the workarounds work due to implementation details that could change. That's unfortunate, but as of now we have no better solutions. We'll continue to think about it though.

[typescript-bot]

This issue has been marked as "Design Limitation" and has seen no recent activity. It has been automatically closed for house-keeping purposes.