OOME/Excessively deep type on upgrade from 4.9.4 to 5.x, introduced in 5.0.0-dev.20230203

[stephenh]

Bug Report

🔎 Search Terms

tsc 5.x Out of Memory Heap

🕗 Version & Regression Information

• This is a crash
• This changed between versions 5.0.0-dev.20230202 and 5.0.0-dev.20230203

⏯ Playground Link

Unavailable, as I'm trying to compile an internal codebase, but I can provide access to our github repo if possible.

💻 Code

The "Type is excessively deep" is being triggered in code that calls this function:

export type LoadedCollaboration = Loaded<Collaboration, "parent">;
export async function getCollaborationMetadata(c: LoadedCollaboration): Promise<CollaborationMetadata> {
  ...
}

Where Loaded is a mapped type (which is available in our open source project):

https://github.com/stephenh/joist-ts/blob/main/packages/orm/src/loadHints.ts#L168

And the Collaboration "parent" key (from our internal project) is a union type with ~20 different types in it:

export type CollaborationParent =
  | ScheduleSubPhase
  | Approval
  ...15 others...
  | ToDo
  | SchedulePhase;

🙁 Actual behavior

In TS 4.9.4, our codebase compiled fine, in about 50 seconds.

I tried upgrading to TS 5.1.3, and the compile now OOMEs, and if given enough RAM, eventually after ~10-15 minutes, fails with a "Type instantiation is excessively deep and possibly infinite" error.

By using the 5.0.0 nightlies published to npm, I was able to bisect that version 5.0.0-dev.20230203 is what introducing the issue, and caused our compile times to jump from ~50 seconds -> 10+ minutes & fail with the type error.

🙂 Expected behavior

[stephenh]

Hi @jakebailey , hope the tag is okay, I saw your note on #53087 that any non-4.8 -> 4.9 OOME issue should be failed as a new bug.

This one is not 5.0 -> 5.1, but 4.9.4 -> 5.0.2 (with the specific nightly identified in the ticket description). I have also tried the latest 5.1.3 but have the same issue.

I haven't tried running tracing/diagnostics yet, b/c I kind of assumed that would fail, but I'll try that and see what happens. Thank you!

[stephenh]

Here's a trace (I haven't looked at it, just attaching it--generated with tar -Jcvf to make it below the github upload limit), and the compile error when giving 16gb of ram:

src/utils/collaborationMetadata.test.ts:33:39 - error TS2589: Type instantiation is excessively deep and possibly infinite.

33       const collaborationMeta = await getCollaborationMetadata(collaboration);
                                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

src/utils/collaborationMetadata.test.ts:33:64 - error TS2345: Argument of type 'Loaded<Collaboration, DeepLoadHint<Collaboration>>' is not assignable to parameter of type 'LoadedCollaboration'.
  The types of 'parent[RelationU]' are incompatible between these types.
    Type '(Task & { collaboration: LoadedOneToOneReference<CollaborationParent, Loaded<Collaboration, DeepLoadHint<Collaboration>>>; }) | ... 243 more ... | (Product & ... 1 more ... & { ...; })' is not assignable to type '(Task & {}) | (Project & {}) | (Document & {}) | (Approval & {}) | (Bill & {}) | (ToDo & {}) | (DevelopmentCommitment & {}) | ... 237 more ... | (Product & ... 1 more ... & {})'.
      Type 'Task & BidContract & { collaboration: LoadedOneToOneReference<CollaborationParent, Loaded<Collaboration, DeepLoadHint<Collaboration>>>; }' is not assignable to type '(Task & {}) | (Project & {}) | (Document & {}) | (Approval & {}) | (Bill & {}) | (ToDo & {}) | (DevelopmentCommitment & {}) | ... 237 more ... | (Product & ... 1 more ... & {})'.
        Type 'Task & BidContract & { collaboration: LoadedOneToOneReference<CollaborationParent, Loaded<Collaboration, DeepLoadHint<Collaboration>>>; }' is not assignable to type 'BidContract & Task & {}'.
          Types of property 'parent' are incompatible.
            Type 'Reference<Task, ScheduleParent, never> & ManyToOneReference<BidContract, Development, never>' is not assignable to type 'ManyToOneReference<BidContract, Development, never> & Reference<Task, ScheduleParent, never>'.
              Type 'Reference<Task, ScheduleParent, never> & ManyToOneReference<BidContract, Development, never>' is missing the following properties from type 'ManyToOneReference<BidContract, Development, never>': [RelationT], [RelationU]

33       const collaborationMeta = await getCollaborationMetadata(collaboration);
                                                                  ~~~~~~~~~~~~~

trace2.tar.gz

[fesieg]

we have this issue as well, upgrading from 4.9 to 5+ breaks our tsc build with an eventual heap allocation error

[ernestostifano]

Updated from 4.9.5 to 5.1.3 today and having the same exact issue. Build hangs until it runs OOM. Using references and paths in a Yarn PnP monorepo.

[Andarist]

I bisected this to: #52392 and managed to get a (somewhat) minimal repro case. It might still have some red herrings in it but well, it's still worth sharing 😉

300 LOC repro

type MaybeBaseType = any;
interface Flavoring<FlavorT> {
  _type?: FlavorT;
}
type Flavor<T, FlavorT> = T & Flavoring<FlavorT>;
type IdOf<T> = T extends {
  id: infer I | undefined;
}
  ? I
  : never;

type ValueFilter<V, N> =
  | V
  | V[]
  | N
  | undefined
  | {
      eq: V | N | undefined;
    }
  | {
      ne: V | N | undefined;
    }
  | {
      in: (V | N)[] | undefined;
    }
  | {
      nin: (V | N)[] | undefined;
    }
  | {
      gt: V | undefined;
    }
  | {
      gte: V | undefined;
    }
  | {
      lt: V | undefined;
    }
  | {
      lte: V | undefined;
    }
  | {
      like: V | undefined;
    }
  | {
      ilike: V | undefined;
    }
  | {
      contains: V | undefined;
    }
  | {
      overlaps: V | undefined;
    }
  | {
      containedBy: V | undefined;
    }
  | {
      gte: V | undefined;
      lte: V | undefined;
    }
  | {
      between: [V, V] | undefined;
    };

interface Collection<T extends Entity, U extends Entity>
  extends Relation<T, U> {
  load(opts?: { withDeleted: boolean }): Promise<ReadonlyArray<U>>;
  find(id: IdOf<U>): Promise<U | undefined>;
  includes(other: U): Promise<boolean>;
  add(other: U): void;
  remove(other: U): void;
  readonly isLoaded: boolean;
}

type SuffixSeperator = ":" | "_";
type DropSuffix<K> = K extends `${infer key}${SuffixSeperator}ro` ? key : K;
type NormalizeHint<T extends Entity, H> = H extends string
  ? Record<DropSuffix<H>, {}>
  : H extends ReadonlyArray<any>
  ? Record<DropSuffix<H[number]>, {}>
  : {
      [K in keyof H as DropSuffix<K>]: H[K];
    };
declare const I: unique symbol;
interface AsyncProperty<T extends Entity, V> {
  isLoaded: boolean;
  load(): Promise<V>;
  [I]?: T;
}
type LoadableValue<V> = V extends Reference<any, infer U, any>
  ? U
  : V extends Collection<any, infer U>
  ? U
  : V extends AsyncProperty<any, infer P>
  ? P extends infer U extends Entity | undefined
    ? U
    : P
  : never;
type Loadable<T extends Entity> = {
  -readonly [K in keyof T as LoadableValue<T[K]> extends never
    ? never
    : K]: LoadableValue<T[K]>;
};
interface LoadedReference<
  T extends Entity,
  U extends Entity,
  N extends never | undefined
> extends Reference<T, U, N> {
  id: IdOf<U> | N;
  get: U | N;
  getWithDeleted: U | N;
  isSet: boolean;
}
interface LoadedOneToOneReference<T extends Entity, U extends Entity>
  extends LoadedReference<T, U, undefined> {
  get: U | undefined;
  getWithDeleted: U | undefined;
  idOrFail: IdOf<U>;
  idUntagged: string | undefined;
  idUntaggedOrFail: string;
  readonly isSet: boolean;
}
interface LoadedCollection<T extends Entity, U extends Entity>
  extends Collection<T, U> {
  get: ReadonlyArray<U>;
  getWithDeleted: ReadonlyArray<U>;
  set(values: U[]): void;
  removeAll(): void;
}
interface LoadedProperty<T extends Entity, V> {
  get: V;
}

type LoadHint<T extends Entity> =
  | (keyof Loadable<T> & string)
  | ReadonlyArray<keyof Loadable<T> & string>
  | NestedLoadHint<T>;

type NestedLoadHint<T extends Entity> = {
  [K in keyof Loadable<T>]?: Loadable<T>[K] extends infer U extends Entity
    ? LoadHint<U>
    : {};
};

declare const deepLoad: unique symbol;
type DeepLoadHint<T extends Entity> = NestedLoadHint<T> & {
  [deepLoad]: true;
};

type MarkDeepLoaded<T extends Entity, P> = P extends OneToOneReference<
  MaybeBaseType,
  infer U
>
  ? LoadedOneToOneReference<T, Loaded<U, DeepLoadHint<U>>>
  : P extends Reference<MaybeBaseType, infer U, infer N>
  ? LoadedReference<T, Loaded<U, DeepLoadHint<U>>, N>
  : P extends Collection<MaybeBaseType, infer U>
  ? LoadedCollection<T, Loaded<U, DeepLoadHint<U>>>
  : P extends AsyncProperty<MaybeBaseType, infer V>
  ? [V] extends [(infer U extends Entity) | undefined]
    ? LoadedProperty<T, Loaded<U, DeepLoadHint<U>> | Exclude<V, U>>
    : V extends readonly (infer U extends Entity)[]
    ? LoadedProperty<T, Loaded<U, DeepLoadHint<U>>[]>
    : LoadedProperty<T, V>
  : unknown;

type MarkLoaded<T extends Entity, P, UH = {}> = P extends OneToOneReference<
  MaybeBaseType,
  infer U
>
  ? LoadedOneToOneReference<T, Loaded<U, UH>>
  : P extends Reference<MaybeBaseType, infer U, infer N>
  ? LoadedReference<T, Loaded<U, UH>, N>
  : P extends Collection<MaybeBaseType, infer U>
  ? LoadedCollection<T, Loaded<U, UH>>
  : P extends AsyncProperty<MaybeBaseType, infer V>
  ? [V] extends [(infer U extends Entity) | undefined]
    ? LoadedProperty<T, Loaded<U, UH> | Exclude<V, U>>
    : V extends readonly (infer U extends Entity)[]
    ? LoadedProperty<T, Loaded<U, UH>[]>
    : LoadedProperty<T, V>
  : unknown;

type Loaded<T extends Entity, H> = T & {
  [K in keyof T & keyof NormalizeHint<T, H>]: H extends DeepLoadHint<T>
    ? MarkDeepLoaded<T, T[K]>
    : MarkLoaded<T, T[K], NormalizeHint<T, H>[K]>;
};

interface Entity {}

declare const RelationT: unique symbol;
declare const RelationU: unique symbol;
interface Relation<T extends Entity, U extends Entity> {
  [RelationT]: T;
  [RelationU]: U;
  isLoaded: boolean;
}

declare const ReferenceN: unique symbol;
interface Reference<
  T extends Entity,
  U extends Entity,
  N extends never | undefined
> extends Relation<T, U> {
  readonly isLoaded: boolean;
  load(opts?: { withDeleted?: boolean; forceReload?: true }): Promise<U | N>;
  set(other: U | N): void;
  [ReferenceN]: N;
}
declare const OneToOne: unique symbol;
interface OneToOneReference<T extends Entity, U extends Entity>
  extends Reference<T, U, undefined> {
  [OneToOne]: T;
}

interface PolymorphicReference<
  T extends Entity,
  U extends Entity,
  N extends never | undefined
> extends Reference<T, U, N> {
  id: IdOf<U> | undefined;
  idOrFail: IdOf<U>;
  idUntagged: string | undefined;
  idUntaggedOrFail: string;
  readonly isSet: boolean;
}

type BidContractId = Flavor<string, BidContract>;

interface BidContractFilter {
  id?: ValueFilter<BidContractId, never>;
}

declare abstract class BidContractCodegen {
  static readonly tagName = "bc";

  readonly __orm: {
    filterType: BidContractFilter;
  };

  readonly collaboration: OneToOneReference<BidContract, Collaboration>;
}

class BidContract extends BidContractCodegen {}

type BidItemId = Flavor<string, BidItem>;

interface BidItemFilter {
  id?: ValueFilter<BidItemId, never>;
}

declare abstract class BidItemCodegen {
  static readonly tagName = "bi";

  readonly __orm: {
    filterType: BidItemFilter;
  };

  readonly collaboration: OneToOneReference<BidItem, Collaboration>;
}

declare class BidItem extends BidItemCodegen {}

type BillId = Flavor<string, Bill>;

interface BillFilter {
  id?: ValueFilter<BillId, never>;
}

declare abstract class BillCodegen {
  static readonly tagName = "b";

  readonly __orm: {
    filterType: BillFilter;
  };

  readonly collaboration: OneToOneReference<Bill, Collaboration>;
}

declare class Bill extends BillCodegen {}

// original union contained 19 types, might be worth introducing more here to stress test this
export type CollaborationParent = BidContract | BidItem | Bill;

declare abstract class CollaborationCodegen {
  static readonly tagName = "collab";
  readonly parent: PolymorphicReference<
    Collaboration,
    CollaborationParent,
    never
  >;
}

class Collaboration extends CollaborationCodegen {}

type LoadedCollaboration = Loaded<Collaboration, "parent">;

type CollaborationMetadata = {
  id: string;
  projectId: string | undefined;
  name: string;
  blueprintPath: string;
  type: string;
};

declare function getCollaborationMetadata(
  c: LoadedCollaboration
): Promise<CollaborationMetadata>;

declare const collaboration: Loaded<Collaboration, DeepLoadHint<Collaboration>>;

getCollaborationMetadata(collaboration);

export {};

I can't exactly end up with OOM using this repro but It just can't finish up running. So perhaps this is an infinite loop and this small extracted repro just can't push the whole thing over the edge when it comes to memory.

[jakebailey]

I tried the above code; it takes a good 15 seconds to run and uses 800MB of memory, but it still completes and doesn't OOM. It's an interesting case but I'm not 100% sure if it's representative of the original issue. The timing is right based on the issue title, though, so it probably is good enough to start looking into this.

---

FWIW, I recently published a tool which should make it a lot easier to figure out what changed things: https://www.npmjs.com/package/every-ts#bisecting

@stephenh (and others in this thread), it'd be super helpful if you could use this tool to identify what change actually caused the problem.

[jakebailey]

In fact, main now declines to compile that code:

index.ts:312:1 - error TS2859: Excessive complexity comparing types 'Loaded<Collaboration, DeepLoadHint<Collaboration>>' and 'LoadedCollaboration'.

312 getCollaborationMetadata(collaboration);
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

index.ts:312:26 - error TS2345: Argument of type 'Loaded<Collaboration, DeepLoadHint<Collaboration>>' is not assignable to parameter of type 'LoadedCollaboration'.

312 getCollaborationMetadata(collaboration);
                             ~~~~~~~~~~~~~


Found 2 errors in the same file, starting at: index.ts:312

[Andarist]

I tried the above code; it takes a good 15 seconds to run and uses 800MB of memory, but it still completes and doesn't OOM.

Interesting. When reducing this test case from their private repo I could make it to finish - I didn't check the mem usage levels. It looked like an infinite loop that couldn't finish. I think I was still OOMing this within the repo but when executed standalone it was just hanging for a loooong time.

@stephenh (and others in this thread), it'd be super helpful if you could use this tool to identify what change actually caused the problem.

I already bisected this to #52392

[jakebailey]

Yeah, sorry, I noticed but forgot to change my text to say "anyone else with this problem"!