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.

CodePudding user response：

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
    }
}