Why am I getting "Type instantiation is excessively deep and possibly infinite"?

Question

I have these general definitions:

type Module<P extends Payloads, C extends Children> = {
    payloads: P;
    children: C;
};

type Children = Record<string, any>; // some values will be nested Modules

type Payloads = Record<string, any>;

type ExtractPayloads<M extends Module<any, any>> = M extends Module<infer P, any> ? P : never;

type ExtractChildren<M extends Module<any, any>> = M extends Module<any, infer C> ? C : never;

Basically, Modules are types that specify a children type, which can contain nested Modules.

I have this type that can generate Actions based on a Module's payload type:

type ModuleRootActions<
  MODULE extends Module<any, any>,
  PAYLOADS = ExtractPayloads<MODULE>,
> = {
  [NAME in keyof PAYLOADS]: {
    type: NAME;
    payload: PAYLOADS[NAME];
  };
}[keyof PAYLOADS];

Next, I have a recursive type that helps me generate Actions for ALL Modules in a Module's tree (i.e., including its child modules, and grandchildren, etc):

type AllModuleActions<
  MODULE extends Module<any, any>,
  CHILDREN = ExtractChildren<MODULE>,
> =
  | ModuleRootActions<MODULE>
  | {
      [KEY in keyof CHILDREN]: CHILDREN[KEY] extends Module<any, any>
        ? AllModuleActions<CHILDREN[KEY]>
        : never;
    }[keyof CHILDREN];

Finally, I have these concrete examples:

type C = Module<{
  "incrementBy": number;
}, {}>;

type B = Module<{
  "setIsSignedIn": boolean;
}, {
  c: C;
}>;

type A = Module<{
  "concat": string;
  "setIsDarkMode": boolean;
}, {
  b: B;
}>;

All my types thus far are correct -- I've verified this manually. Now, I'm writing a function that takes in an Action of a generic Module. I can successfully define these types:

type ConcreteAction<M extends Module<any, any>> = AllModuleActions<M>;

const concreteAction: ConcreteAction<A> = {
  type: "concat",
  payload: "str",
}

But once I try to put them in a generic function, I get the error in the title.

const composedReducer = <MODULE extends Module<any, any>>(
  action: AllModuleActions<MODULE>,
) => {
  if (action) {

  }
};

You'll notice in the Playground link that action has the error: "Type instantiation is excessively deep and possibly infinite". I assume this is happening because the MODULE type is generic, and it's possible that there could be cycles in the Module definition, even though semantically I know that it's a tree.

How can I fix this error? Is there a way to tell the compiler that the graph will always be a tree and never contain infinite cycles?

I could be wrong about this, but I think the infinite recursion is because the type never bottoms out in a "leaf" node: children is not optional. — Jared Smith, Dec 31 '21 at 22:58
@Jared Smith I don't think this is it, because even if children is optional, it is still in theory possible that the module graph is cyclic and therefore type resolution does not terminate. I think the only way around this is some way to constrain my types so that a cycle is impossible. — wwohlers, Jan 01 '22 at 00:19
`AllModuleActions` is recursive in a way that the compiler can't handle well; it's like the `Paths`/`Leaves` type in [this answer](//stackoverflow.com/a/58436959/2887218) in that it builds a big union out of arbitrarily nested input types. You can try to defer the evaluation like [this](//tsplay.dev/NaYQ2N) (in that example I removed a lot of indirection to make it more of a [mre], but the behavior is the same). Or you can do an explicit depth limiter like [this](//tsplay.dev/WzLneN). Let me know if you want either of these as an answer. — jcalz, Jan 01 '22 at 02:45
@jcalz So I ended up using a bottom-up approach to recursion rather than top-down, basically defining actions concretely based on only the immediate child's actions. Not sure why I didn't think of this earlier. That being said, if you want to add one of your answers for future people, feel free to do that and I'll mark it as answered. — wwohlers, Jan 01 '22 at 04:02

score 13 · Accepted Answer · answered Jan 01 '22 at 21:45

The AllModuleActions<M> type is recursive in a way that the compiler cannot handle very well. You are indexing arbitrarily deep into an object type all at once to produce a big union type; I've run into this problem before here when generating all the dotted paths of an object type (e.g., {a: {b: string, c: number}} becomes "a.b" | "a.c").

You don't usually see the problem when you evaluate something like AllModuleActions<M> when M is a specific type; but when it's an unspecified generic type parameter (or a type that depends on such a type parameter), you can run into trouble. You might see that "excessively deep" error. Even worse, the compiler tends to get bogged down, spiking CPU usage and slowing down your IDE. I don't know exactly why this happens.

Probably the best advice is not to build types like this. If you have to, then there are some ways I've found to help, but they aren't foolproof:

Sometimes you can cause the compiler to defer evaluation of one of these types by rephrasing it as a distributive conditional type. If M is a generic type parameter and AllModuleActions<M> gives you trouble, maybe M extends any ? AllModuleActions<M> : never won't:

const generic = <M extends Module<any, any>>(
  action: M extends any ? AllModuleActions<M> : never, // <-- defer
) => {
  action; // okay
};

If that doesn't work you can try to explicitly depth-limit your recursive type so that by default things only descend three or four levels:

type Prev = [never, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9];

type AllModuleActions<M extends Module<any, any>, D extends Prev[number] = 4> =
  [D] extends [never] ? never :
  | ModuleRootActions<M>
  | {
    [K in keyof M["children"]]: M["children"][K] extends Module<any, any>
    ? AllModuleActions<M["children"][K], Prev[D]>
    : never;
  }[keyof M["children"]];

This is similar to yours, except we have added a D parameter which (by default) starts at 4 and decreases each time AllModuleActions is evaluated (note that Prev[4] is 3 and Prev[3] is 2) until eventually it reaches never and the recursive type bails out:

const generic = <M extends Module<any, any>>(
  action: AllModuleActions<M>
) => {
  action; // okay
};

These workarounds may or may not help for a particular use case, and there may be observable side effects (e.g., types might not be identical; type inference may behave differently; displayed quickinfo might be more complicated), so be careful!

Playground link to code

Thank you! This helped me fix this problem on a hideously complicated recursive type. (rephrasing it as a distributive conditional type). — ciscoheat, Mar 19 '23 at 20:52

score 6 · Answer 2 · answered Apr 21 '22 at 21:41

6

Make sure you don't have an old Typescript version, as there is some bug with old versions for type inference

for me updating from 3.9 to 4.6.3 fixed the issue.

answered Apr 21 '22 at 21:41

Ali80

6,333
2
43
33

Samuel RIGAUD · Answer 3 · 2023-06-21T12:47:48.590

The error is pretty generic so I don't know if my post will really help but I was struggling with it on a Vue project with Typescript and vueI18n. When I was referencing the VueI18n.global.t method in utility code outside *.vue files and the error was raised by the compiler. I was using Vue3, Vuetify and vueI18n and my file was looking like this

import { createI18n } from 'vue-i18n'
import en from 'vuetify/lib/locale/en'
import fr from 'vuetify/lib/locale/fr'

const messages = {
  en: {
    ...require('@/locales/en.json'),
    $vuetify: en
  },
  fr: {
    ...require('@/locales/fr.json'),
    $vuetify: fr
  }
}

export default createI18n({
    locale: localStorage.getItem('locale') || process.env.VUE_APP_I18N_LOCALE || 'en',
    fallbackLocale: process.env.VUE_APP_I18N_FALLBACK_LOCALE || 'en',
    messages
  })

And after struggling for hours I found this really simple example here. So I updated my file and now it compiles correctly.

import { createI18n, FallbackLocale } from 'vue-i18n'
import en from '@/locales/en.json'
import fr from '@/locales/fr.json'

const locale: string = localStorage.getItem('locale') || process.env.VUE_APP_I18N_LOCALE || 'en'
const fallbackLocale: FallbackLocale = process.env.VUE_APP_I18N_FALLBACK_LOCALE || 'en'

export default createI18n({
  locale: locale,
  fallbackLocale: fallbackLocale,
  messages: {
    en,
    fr,
  }
})

I solved it by adding `// @ts-ignore` on top of the line that gave the error. Not the best solution, but works... — Maurici Abad, Nov 28 '22 at 06:58

Ilya Ordin · Answer 4 · 2022-12-22T17:57:57.960

You can avoid this error by checking whether the type is any in your recursion type. Let's look at a simple example at the beginning, and then yours.

For example, we want to extract all values used in an object.

type AllValues<T extends object, K = keyof T> = K extends keyof T
  ? T[K] extends object
    ? AllValues<T[K]>
    : T[K]
  : never;

interface Data {
  num: number
  deep: {
    deep: {
      str: string
    }
  }
}

type A = AllValues<Data> // string | number
type B = AllValues<any> // Type instantiation is excessively deep and possibly infinite

See playground.

TypeScript throws an error because the type AllValues is called infinitely with the any type. To avoid it, in the recursive type AllValues we should add a check for the type any as follows:

type IsAny<T> = unknown extends T & string ? true : false;

type AllValues<T extends object, K = keyof T> = IsAny<T> extends true
  ? string
  : K extends keyof T
  ? T[K] extends object
    ? AllValues<T[K]>
    : T[K]
  : never;

interface Data {
  num: number
  deep: {
    deep: {
      str: string
    }
  }
}

type A = AllValues<Data> // string | number
type B = AllValues<any> // string

See playground.

Let's go back to your example. All you have to do is add a check for any in the type AllModuleActions.

type IsAny<T> = unknown extends T & string ? true : false;

type AllModuleActions<
  MODULE extends Module<any, any>,
  CHILDREN = ExtractChildren<MODULE>
> = IsAny<MODULE> extends true
  ? any
  : ...

See playground.

Earlier, as a solution, you were offered to limit the maximum number of nested calls of the recursive type (code with type Prev = [never, 0, 1, 2, ...]). It works, but in this case the generated type declarations turn out to be huge.

score 0 · Answer 5 · answered Jul 25 '23 at 08:11

0

If anyone is still having this problem then try upgrade Typescript version to latest.

I faced this error when used AntD Datepicker with its DatePickerProps, and after many tryings, just upgraded TS and issue gone.

Hope this will help someone else.

answered Jul 25 '23 at 08:11

Erik P_yan

608
5
6

score -1 · Answer 6 · answered Sep 08 '22 at 07:54

-1

add to tsconfig.json :

"ts-node": {
      "swc": true
}

and install this:

npm i -D @swc/core @swc/helpers regenerator-runtime

it works for me .

answered Sep 08 '22 at 07:54

Abdullah alkış

325
4
13

Why am I getting "Type instantiation is excessively deep and possibly infinite"?

6 Answers6