Keyof nested child objects

Question

I have a recursively typed object that I want to get the keys of and any child keys of a certain type.

For instance. Below I want to get a union type of:

'/another' | '/parent' | '/child'

Example:

export interface RouteEntry {
    readonly name: string,
    readonly nested : RouteList | null
}
export interface RouteList {
    readonly [key : string] : RouteEntry
}

export const list : RouteList = {
    '/parent': {
        name: 'parentTitle',
        nested: {
            '/child': {
                name: 'child',
                nested: null,
            },
        },
    },
    '/another': {
        name: 'anotherTitle',
        nested: null
    },
}

In typescript you can use keyof typeof RouteList to get the union type:

'/another' | '/parent' 

Is there a method to also include the nested types

Answer 1

That's a tough one. TypeScript lacks both mapped conditional types and general recursive type definitions, which are both what I'd want to use to give you that union type. (Edit 2019-04-05: conditional types were introduced in TS2.8) There are some sticking points with what you want:

• The nested property of a RouteEntry can sometimes be null, and type expressions that evaluate to keyof null or null[keyof null] start to break things. One needs to be careful. My workaround involves adding a dummy key so that it's never null, and then removing it at the end.
• Whatever type alias you use (call it RouteListNestedKeys<X>) seems to need to be defined in terms of itself, and you will get a "circular reference" error. A workaround would be to provide something that works up to some finite level of nesting (say, 9 levels deep). This might cause the compiler to slow way down, since it could eagerly evaluate all 9 levels instead of deferring the evaluation until later.
• This needs a lot of type alias composition involving mapped types, and there is a bug with composing mapped types that won't be fixed until TypeScript 2.6. A workaround involves using generic default type parameters.
• The "remove a dummy key at the end" step involves a type operation called Diff which needs at least TypeScript 2.4 to run properly.

All that means: I have a solution which works, but I warn you, it's complex and crazy. One last thing before I drop in the code: you need to change

export const list: RouteList = { // ...

to

export const list = { // ...

That is, remove the type annotation from the list variable. If you specify it as RouteList, you are throwing away TypeScript's knowledge of the exact structure of list, and you will get nothing but string as the key type. By leaving off the annotation, you let TypeScript infer the type, and therefore it will remember the entire nested structure.

Okay, here goes:

type EmptyRouteList = {[K in 'remove_this_value']: RouteEntry};
type ValueOf<T> = T[keyof T];
type Diff<T extends string, U extends string> = ({[K in T]: K} &
  {[K in U]: never} & { [K: string]: never })[T];
type N0<X extends RouteList> = keyof X
type N1<X extends RouteList, Y = {[K in keyof X]: N0<X[K]['nested'] & EmptyRouteList>}> = keyof X | ValueOf<Y> 
type N2<X extends RouteList, Y = {[K in keyof X]: N1<X[K]['nested'] & EmptyRouteList>}> = keyof X | ValueOf<Y> 
type N3<X extends RouteList, Y = {[K in keyof X]: N2<X[K]['nested'] & EmptyRouteList>}> = keyof X | ValueOf<Y> 
type N4<X extends RouteList, Y = {[K in keyof X]: N3<X[K]['nested'] & EmptyRouteList>}> = keyof X | ValueOf<Y> 
type N5<X extends RouteList, Y = {[K in keyof X]: N4<X[K]['nested'] & EmptyRouteList>}> = keyof X | ValueOf<Y> 
type N6<X extends RouteList, Y = {[K in keyof X]: N5<X[K]['nested'] & EmptyRouteList>}> = keyof X | ValueOf<Y> 
type N7<X extends RouteList, Y = {[K in keyof X]: N6<X[K]['nested'] & EmptyRouteList>}> = keyof X | ValueOf<Y> 
type N8<X extends RouteList, Y = {[K in keyof X]: N7<X[K]['nested'] & EmptyRouteList>}> = keyof X | ValueOf<Y> 
type N9<X extends RouteList, Y = {[K in keyof X]: N8<X[K]['nested'] & EmptyRouteList>}> = keyof X | ValueOf<Y> 
type RouteListNestedKeys<X extends RouteList, Y = Diff<N9<X>,'remove_this_value'>> = Y;

Let's try it out:

export const list = {
    '/parent': {
        name: 'parentTitle',
        nested: {
            '/child': {
                name: 'child',
                nested: null,
            },
        },
    },
    '/another': {
        name: 'anotherTitle',
        nested: null
    },
}

type ListNestedKeys = RouteListNestedKeys<typeof list> 

If you inspect ListNestedKeys you will see that it is "parent" | "another" | "child", as you wanted. It's up to you whether that was worth it or not.

Whew! Hope that helps. Good luck!

Answer 2

Here's an infinitely recursive solution:

type Paths<T> = T extends RouteList
  ? keyof T | { [K in keyof T]: Paths<T[K]['nested']> }[keyof T]
  : never

type ListPaths = Paths<typeof list> // -> "/parent" | "/another" | "/child"

Tested on Typescript v3.5.1. Also you need to remove the type annotation from the list variable as advised by @jcalz.

Answer 3

The answer of @Aleksi shows how to obtain the requested type union "/parent" | "/another" | "/child".

Since the question deals with a route hierarchy i would like to add that since typescript 4.1 the feature Template Literal Types can be used to not only obtain all keys but to even generate all possible routes: "/parent" | "/another" | "/parent/child"

type ValueOf<T> = T[keyof T]
type AllPaths<T extends RouteList, Path extends string = ''> = ValueOf<{
    [K in keyof T & string]: 
        T[K]['nested'] extends null 
        ? K 
        : (`${Path}${K}` | `${Path}${K}${AllPaths<Extract<T[K]['nested'], RouteList>>}`)
}>

type AllRoutes = AllPaths<typeof list> // -> "/parent" | "/another" | "/parent/child"

Like the other answers mention the list object may not have the RouteList type annotation as it would erase the type information our AllPaths type operates on.