Error when using recursive type in a function

Question

I have a recursive type that extracts the indices from a nested object and puts them in a flat, strongly-typed tuple, like so:

type NestedRecord = Record<string, any>

type RecursiveGetIndex<
  TRecord extends NestedRecord,
  TPreviousIndices extends any[] = []
> = {
  [K in keyof TRecord]: TRecord[K] extends NestedRecord
    ? RecursiveGetIndex<
        TRecord[K],
        AppendToTuple<TPreviousIndices,K>
      >
    : AppendToTuple<TPreviousIndices, K>
}[keyof TRecord]

type AppendToTuple<T extends any[], U> = [...T, U]

It works fine when called with a concrete instantiation of a nested object type, e.g.:

type AnIndex = RecursiveGetIndex<{ foo: { bar: { baz: number}}}>

In other words, as expected, AnIndex is typed as ["foo", "bar", "baz"]

But, when I try to use the Recursive type in a function, I get a recursion error:

function doSomething<T extends NestedRecord>(arg:T){
    type Nested = RecursiveGetIndex<T>
    const doMore = (n: Nested) => {
        console.log(n) //Type instantiation is excessively deep and possibly nested
    }
}

Which kind of makes sense to me because TS doesn't really know how deeply recursed T might be.

Is that correct? Why wouldn't TS just wait until it see's how doSomething is instantiated before worrying about recursion?

And, is there some way to avoid the error if I know in advance that the arg passed to the function will never exceed the TS recursion limit (50, i believe). I.e., can I somehow tell typescript that?

I've seen solutions that limit recursion basically by using a decrementing array type, e.g. this SO answer. Is that the best I can do here?

Playground with the code.

Updated

Per captain-yossarian's suggestion, the following works:

type RecursiveGetIndex<
  TRecord extends NestedRecord,
  TPreviousIndices extends any[] = [],
  TDepth extends number = 5
> = 10 extends TPreviousIndices["length"] ? TPreviousIndices : {
  [K in keyof TRecord]: TRecord[K] extends NestedRecord
    ? RecursiveGetIndex<
        TRecord[K],
        AppendToTuple<TPreviousIndices,K>
      >
    : AppendToTuple<TPreviousIndices, K>
}[keyof TRecord]

The error recurs, however, if this number is any higher than 10. I would have thought that should be 50. Is my type more recursive than I think?

Updated playground.

Here catchts.com/recursive-ds you can find recursive type with limitation. As for the second example, TS can't wait untic you call this function because these are two different stages — captain-yossarian from Ukraine
– captain-yossarian from Ukraine, Commented Nov 19, 2021 at 20:34
blah, recursive types like this are evaluated in a weird/funny way and I don't know of any good way to deal with the problem here. I haven't found anything great, anyway. — jcalz
– jcalz, Commented Nov 19, 2021 at 20:51
@captain-yossarian, that's clever. using that with my code it looks like starting the type with = 10 extends TPreviousIndices["length"] ? TPreviousIndices : //etc works, but if i make it 11 it has an error. is there some reason each level of recursion counts as more than 1 for purposes of TS's limit? — sam256
– sam256, Commented Nov 19, 2021 at 20:51
@sam256 could you please provide an example of how you calling it? — captain-yossarian from Ukraine
– captain-yossarian from Ukraine, Commented Nov 19, 2021 at 20:54

Tadhg McDonald-Jensen · Accepted Answer · 2021-11-19 22:36:09Z

2

RecursiveGetIndex<NestedRecord> is the real problem here and this is because of how any works for a conditional type.

Since your generic is constrained to NestedRecord typescript has to try to apply RecursiveGetIndex to the constrain inside the function in order to give you type checking, however this means that TRecord[K] is any so the condition TRecord[K] extends NestedRecord will end up evaluating both branches and since one branch ends up calling RecursiveGetIndex again in the same way.

Once TRecord=any with your original implementation it just keeps on looking for nested keys forever. So you can add a check for any and resolve to just ...any[] in that case so it doesn't get caught in infinite recursion. playground

type NestedRecord = Record<string, any>

type RecursiveGetIndex<
  TRecord extends NestedRecord,
  TPreviousIndices extends any[] = []
> = {
   // first check for any with 0 extends <clearly not 0> and opt out of recursing with just any nested keys
   // optionally you could use ...unknown[] if you wanted to be safer.
  [K in keyof TRecord]: 0 extends TRecord[K]&1 ? [...TPreviousIndices, K, ...any[]] 
  : TRecord[K] extends NestedRecord
    ? RecursiveGetIndex<
        TRecord[K],
        AppendToTuple<TPreviousIndices,K>
      >
    : AppendToTuple<TPreviousIndices, K>
}[keyof TRecord]


type AppendToTuple<T extends any[], U> = [...T, U] 

type AnIndex = RecursiveGetIndex<{ foo: { bar: number, baz: any}}> 
//   ^? ["foo", "bar"] | ["foo", "baz", ...any[]]

function doSomething<T extends NestedRecord>(arg:T){
    type Nested = RecursiveGetIndex<T>
    const doMore = (n: Nested) => {
        console.log(n) //here n will work a lot like unknown
    }
}

edited Nov 19, 2021 at 22:36

answered Nov 19, 2021 at 21:22

Tadhg McDonald-Jensen

21.6k5 gold badges40 silver badges69 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

sam256 Over a year ago

This seems right to me, in that I do tend to hit these problems when I have an any constraint in a conditional type. But could you explain the 2nd paragraph a little more? Specifically why is it passing any when it hits two levels deep? I'm missing a step there.

sam256 Over a year ago

oh, by two levels deep, you mean in the function, not the recursion, correct?

Tadhg McDonald-Jensen Over a year ago

yeah terminology is hard, I edited to try to be clearer but idk how successful I was. The point is that any makes most reasonable recursive types break in annoying ways since it evaluates both branches of conditionals so you often have to explicitly check for it to stop infinite recursion.

sam256 Over a year ago

your edits do make it clearer for me. thanks. this is one of two tough TS recursion problems in a project i'm working on, which is making me a think i need a non-recursive solution...

Collectives™ on Stack Overflow

Error when using recursive type in a function

Updated

1 Answer 1

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

Updated

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related