Improve inference of Recursive types

[alesmenzel]

Suggestion

It would be nice to be able to infer all variants from a recursive type. Playground link.

// SETUP

// E.g. for nested selectable lists
type Recursive<Id> = {
    id: Id
    children: readonly Recursive<Id>[]
}

// Function to return all ids from the type
function getIds<Id>(items: readonly Recursive<Id>[]): Id[] {
    return [] // return value is not important
}

// EXAMPLE USAGE

const items = [{
    id: 'a',
    children: [{
        id: 'b',
        children: []
    }]
}] as const satisfies readonly Recursive<string>[]

const foo = getIds(items)
// EXPECTED: ("a" | "b")[] but returns just "a"[]

🔍 Search Terms

recursive types

✅ Viability Checklist

My suggestion meets these guidelines:

• This wouldn't be a breaking change in existing TypeScript/JavaScript code
  It might be breaking from types perspective if some code relies on the current behaviour.
• This wouldn't change the runtime behavior of existing JavaScript code
• This could be implemented without emitting different JS based on the types of the expressions
• This isn't a runtime feature (e.g. library functionality, non-ECMAScript syntax with JavaScript output, new syntax sugar for JS, etc.)
• This feature would agree with the rest of TypeScript's Design Goals.

⭐ Suggestion

Generics inside recursive types would be expanded.

📃 Motivating Example

E.g. for selectable nested lists, we could provide auto-complete for onSelect(itemId: <union of all ids from recursive type>).

💻 Use Cases

I haven't found a workaround that would work for the getIds function in the example. One semi working workaround is written below - it returns correctly union of all ids literals, but TS shows an error and it cannot be used as return value for getIds(...) because then TS show that the type is recursive and possible infinite.

type GetRecursiveType<T extends readonly Recursive<any>[]> = T[number]['id'] | (T[number]['children'] extends undefined ? never : GetRecursiveType<T[number]['children']>)

Playground link.

[whzx5byb]

You could "expand" it with a mapped type like this:

type GetRecursiveType<T extends readonly Recursive[]> = {
    [K in keyof T]: T[K] extends infer U extends Recursive
        ? U['id'] | (U['children'] extends infer R extends readonly Recursive[]
            ? GetRecursiveType<R>
            : never)
        : never
}[number]

Playground

[alesmenzel]

@whzx5byb thanks for the example, could you please explain why using mapped type is different from conditional type I was trying to do? It seems to me that it should do the same, but it doesn't.

type GetRecursiveType<T extends readonly Recursive[]> = T[number] extends infer U extends Recursive ? U['id'] | (U['children'] extends infer R extends Recursive[] ? GetRecursiveType<R> : never) : never

Playground

[whzx5byb]

@alesmenzel

T[number] is a union of all value type but it doesn't have the distribution behavior. So if you want to write recursive types in this way you should add another "extends" condition to make it distributive. Also note that you missed readonly in infer R extends readonly Recursive[].

type GetRecursiveType<T extends readonly Recursive[]> = 
    T[number] extends infer U extends Recursive 
+    ? U extends infer V extends Recursive
-        ? U['id'] | (U['children'] extends infer R extends Recursive[] 
+        ? V['id'] | (V['children'] extends infer R extends readonly Recursive[] 
            ? GetRecursiveType<R> 
            : never) 
        : never
+    : never

Playground

[alesmenzel]

@whzx5byb Thanks for explanation. So the T[number] is not distributive because the distributive behaviour is only default for generic types, but not for derived types from generics, e.g. T[number], correct?

[whzx5byb]

@alesmenzel

Generally correct. A distributive type parameter T is usually called naked.
However, there are very few special cases as discussed in #43727.

[RyanCavanaugh]

This just seems like a bug. There's not anything super different between the provided example and this variant (which works as expected):

type NotRecursive<Id> = {
    id: Id
    other: Id;
}
function getIds<Id>(items: readonly NotRecursive<Id>[]): Id[] {
    return [] // return value is not important
}

const items = [{
    id: 'a',
    other: 'b'
}] as const satisfies readonly NotRecursive<string>[]

const foo = getIds(items)
// inferred type arg is "a" | "b"

[Andarist]

It turns out that the issue is essentially the same as the one reported here and I have a PR with a potential fix for this inference issue here