TypeScript ignoring checks for deeply nested computed object types

[sinclairzx81]

🔎 Search Terms

inference, deeply nested, no error, type evaluation, typebox, hkt

🕗 Version & Regression Information

Hi,

I've come across some unusual behavior where TypeScript seems to be skipping checks for certain kinds of computed types. This seems to be specific to deeply nested object types that are computed via intersection. I note that the language service is reporting the correct type information in editor, however the compiler seems to be skipping checks on the reported type. This behavior can be observed using the TypeBox library, specifically for object types at least 2 levels deep.

• This is the behavior in every version I tried (5.1.6 onwards)

⏯ Playground Link

TypeScript Link Here

💻 Code

import { Static, Type } from "@sinclair/typebox"

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

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

// The following functions should all report errors for the return value, however the first does not.

function problematicFunction1(ors: Input[]): Output[] {
  return ors; // <-- this does not error 
}

function problematicFunction2<T extends Output[]>(ors: Input[]): T {
  return ors; // <-- ... but this does
}

function problematicFunction3(ors: (typeof Input.static)[]): Output[] {
  return ors; // <-- ... and so does this
}

🙁 Actual behavior

First function does not report an error

🙂 Expected behavior

All functions should report errors

Additional information about the issue

I get the feeling this may have something to do with TypeBox's implementation of Static<T> and where TypeScript may be implementing some optimizations around certain forms of computed / evaluated types (but not sure). TypeBox currently implements Static<T> as follows.

type Static<T extends TSchema, P extends unknown[] = []> = (T & { params: P; })["static"]

By removing the intersection of P, TypeScript correctly asserts the problematicFunction1 return type.

type Static<T extends TSchema, P extends unknown[] = []> = T["static"] // this is fine

[RyanCavanaugh]

Please inline the relevant parts of typebox

[sinclairzx81]

@RyanCavanaugh See link below for the relevant parts of TypeBox inlined

TypeScript Link Here

[RyanCavanaugh]

WIP reduction

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

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

function problematicFunction1(ors: Input): Output {
  return ors; // <-- this does not error
}
function f() {
  problematicFunction1(null as any);
}
f();
 
export type Evaluate<T> = T extends infer O ? { [K in keyof O]: O[K] } : never;
export interface TSchema {
  params: unknown[];
  static: unknown;
}
interface HasStatic { static: unknown }
interface HasParams { params: unknown[] }
type RecordOfHasStatics = Record<string, HasStatic>;
export type PropertiesReduce<T extends RecordOfHasStatics, P extends unknown[]> = Evaluate<{ [K in keyof T]: Static<T[K], P> }>;
export interface TObject<T extends RecordOfHasStatics> extends HasParams {
  static: PropertiesReduce<T, this['params']>;
  properties: T;
}
export type Static<T extends HasStatic, P extends unknown[] = []> = (T & { params: P; })['static']

declare namespace Type {
  function Object<T extends RecordOfHasStatics>(object: T): TObject<T>;
  function String(): TSchema & { static: string };;
}

[RyanCavanaugh]

As expected, we're hitting a depth limit

{"pid":1,"tid":1,"ph":"I","cat":"checkTypes","ts":416867.20000207424,"name":"recursiveTypeRelatedTo_DepthLimit","s":"g","args":{"sourceId":236,"sourceIdStack":[165,222,236],"targetId":229,"targetIdStack":[198,215,229],"depth":3,"targetDepth":3}},

Source 236 is Evaluate<T>
165 is Evaluate<T>
222 is Evaluate<T>
236 is Evaluate<T>

Target 229 is Evaluate<T>
198 is Evaluate<T>
215 is Evaluate<T>
229 is ... Evaluate<T>

The source stack is

{ level1: { level2: { foo: string; }; }; } -> { level2: { foo: string; }; } -> { foo: string; }

and the target stack is

{ level1: { level2: { foo: string; bar: string; }; }; } -> { level2: { foo: string; bar: string; }; } -> { foo: string; bar: string; }

Since each of these types are instantiations of the same symbol Evaluate<T>, it appears that we might be stuck in an infinitely-expanding recursive type like this one, where each level of expansion creates new fresh types that seem like they might be worth looking into:

type RabbitHole<T, K> = {
  next: RabbitHole<T, { obj: K }>
}

declare let x: RabbitHole<string, number>;
let y = x.next.next.next.next.next.next.next;

So we need some way to tell apart OP's situation - where the types are actually converging, probably - from the infinite-descent case where they'll never converge.

[RyanCavanaugh]

I'm going to put up a PR to change the object type depth limit from 3 to 5 but it's almost certainly going to break someone else's performance or cause them to hit a depth limit which they previously didn't...

[RyanCavanaugh]

The PR tanked xstate performance; we'll need something smarter.

Reduced and annotated example (apologies for renaming but these make more sense to me and avoid conflicting with certain terms we use internally):

type Input = GetType<typeof Input, []>
const Input = MakeObject({
    level1: MakeObject({
        level2: MakeObject({
            foo: MakeString(),
        })
    })
});

type Output = GetType<typeof Output, []>;
const Output = MakeObject({
    level1: MakeObject({
        level2: MakeObject({
            foo: MakeString(),
            bar: MakeString(),
        })
    })
});

function problematicFunction1(ors: Input): Output {
    // Should error
    return ors;
}

// Representational types have a 'myType' field that represents
// the TypeScript type of the object, e.g.: MakeString below
interface HasType { myType: unknown }
declare function MakeString(): { myType: string };

// Reads the 'myType' field out of an object. 'P' exists for
// reverse inference purposes when dealing with object types (see MakeObject below)
type GetType<T extends HasType, P> = (T & { objectProps: P; })['myType'];
// Mapped version of above
type GetTypeMapped<T extends RecordOfTypes, P> = { [K in keyof T]: GetType<T[K], P> };

// Creates an object type
declare function MakeObject<T extends RecordOfTypes>(object: T): TObject<T>;
interface TObject<T extends RecordOfTypes> {
    objectProps: unknown;
    myType: GetTypeMapped<T, this['objectProps']>;
}

// Any dictionary from string -> statically-typed type
type RecordOfTypes = Record<string, HasType>;

This example defeats the existing "are we making progress" heuristics because of

    myType: GetTypeMapped<T, this['objectProps']>;

When computing Output.level1.level2, this is computing this['objectProps']['objectProps']['objectProps'], which looks a heck of a lot like the infinite series of nexts in RabbitHole.

[sinclairzx81]

@RyanCavanaugh

Reduced and annotated example (apologies for renaming but these make more sense to me and avoid conflicting with certain terms we use internally):

Hey no problem. Also, thank you for taking the time to investigate this issue (and for the test PR), that was very much appreciated. If there is anything that can be done library side to help work within TS depth limits here, please let me know.

[fatcerberus]

The PR tanked xstate performance; we'll need something smarter.

Didn't @ahejlsberg recently author a PR with smarter logic for this that went beyond the usual "stop after 3 levels of Foo<T>"?

[sinclairzx81]

Related #55638

[fatcerberus]

@sinclairzx81 That was the PR I was thinking of, thanks!

[webstrand]

Could we perhaps explicitly mark these cases instead, if detecting them automatically proves infeasible?

[fatcerberus]

@webstrand I think the halting problem goes both ways - if you can't prove that a program halts (or, equivalently, that a type is not infinitely recursive), then you also can't prove that it doesn't. So you'd have to rely on equally inaccurate heuristics to do that marking, no?

[webstrand]

I mean an intrinsic Converges<T> (or a keyword) which may loop infinitely if poorly written. I recognize that detecting these cases automatically may be impossible, but rather than an esoteric "you must write your recursive types in a particular pattern that typescript recognizes, but is only known to the few who frequent issues" mark it explicitly.

[ahejlsberg]

With #55638 we got pretty close to fixing the issue. However, use of the non-homomorphic Pick and the Evaluate conditional causes the compiler to loose track of the symbol of the original literal type. Once that happens, all of the transformed types have the same symbol and we stop relating them after three levels. The code works if I remove the use of Evaluate and change to a homomorphic definition of Pick:

type Pick<T, K extends keyof T> = { [P in keyof T as P & K]: T[P] };

I'll keep thinking about this, but it's a really tricky issue to solve.

[ahejlsberg]

Actually, it appears possible to fix this by improving our logic for tracking deeply nested types in relationships. I will put up a PR.

[sinclairzx81]

@ahejlsberg This PR is amazing. Thank you so much!