Typescript: deep keyof of a nested object

UPDATE for TS4.1 It is now possible to concatenate string literals at the type level, using template literal types as implemented in microsoft/TypeScript#40336. The below implementation can be tweaked to use this instead of something like Cons (which itself can be implemented using variadic tuple types as introduced in TypeScript 4.0):

type Join<K, P> = K extends string | number ?
    P extends string | number ?
    `${K}${"" extends P ? "" : "."}${P}`
    : never : never;

Here Join concatenates two strings with a dot in the middle, unless the last string is empty. So Join<"a","b.c"> is "a.b.c" while Join<"a",""> is "a".

Then Paths and Leaves become:

type Paths<T, D extends number = 10> = [D] extends [never] ? never : T extends object ?
    { [K in keyof T]-?: K extends string | number ?
        `${K}` | Join<K, Paths<T[K], Prev[D]>>
        : never
    }[keyof T] : ""

type Leaves<T, D extends number = 10> = [D] extends [never] ? never : T extends object ?
    { [K in keyof T]-?: Join<K, Leaves<T[K], Prev[D]>> }[keyof T] : "";

And the other types fall out of it:

type NestedObjectPaths = Paths<NestedObjectType>;
// type NestedObjectPaths = "a" | "b" | "nest" | "otherNest" | "nest.c" | "otherNest.c"
type NestedObjectLeaves = Leaves<NestedObjectType>
// type NestedObjectLeaves = "a" | "b" | "nest.c" | "otherNest.c"

and

type MyGenericType<T extends object> = {
    keys: Array<Paths<T>>;
};

const test: MyGenericType<NestedObjectType> = {
    keys: ["a", "nest.c"]
}

The rest of the answer is basically the same. Recursive conditional types (as implemented in microsoft/TypeScript#40002) will be supported in TS4.1 also, but recursion limits still apply so you’d have a problem with tree-like structures without a depth limiter like Prev.

PLEASE NOTE that this will make dotted paths out of non-dottable keys, like {foo: [{"bar-baz": 1}]} might produce foo.0.bar-baz. So be careful to avoid keys like that, or rewrite the above to exclude them.

ALSO PLEASE NOTE: These recursive types are inherently “tricky” and tend to make the compiler unhappy if modified slightly. If you’re not lucky you will see errors like “type instantiation is excessively deep”, and if you’re very unlucky you will see the compiler eat up all your CPU and never complete type checking. I’m not sure what to say about this kind of problem in general… just that such things are sometimes more trouble than they’re worth.

Playground link to code



PRE-TS4.1 ANSWER:

As mentioned, it is not currently possible to concatenate string literals at the type level. There have been suggestions which might allow this, such as a suggestion to allow augmenting keys during mapped types and a suggestion to validate string literals via regular expression, but for now this is not possible.

Instead of representing paths as dotted strings, you can represent them as tuples of string literals. So "a" becomes ["a"]and "nest.c" becomes ["nest", "c"]. At runtime it’s easy enough to convert between these types via split() and join() methods.


So you might want something like Paths<T> that returns a union of all the paths for a given type Tor possibly Leaves<T> which is just those elements of Paths<T> which point to non-object types themselves. There is no built-in support for such a type; The ts-toolbelt library has this, but since I can’t use that library in the Playground, I will roll my own here.

Be warned Paths and Leaves are inherently recursive in a way that can be very taxing on the compiler. And recursive types of the sort needed for this are not officially supported in TypeScript either. What I will present below is recursive in this iffy/not-really-supported way, but I try to provide a way for you to specify a maximum recursion depth.

Here we go:

type Cons<H, T> = T extends readonly any[] ?
    ((h: H, ...t: T) => void) extends ((...r: infer R) => void) ? R : never
    : never;

type Prev = [never, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
    11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...0[]]

type Paths<T, D extends number = 10> = [D] extends [never] ? never : T extends object ?
    { [K in keyof T]-?: [K] | (Paths<T[K], Prev[D]> extends infer P ?
        P extends [] ? never : Cons<K, P> : never
    ) }[keyof T]
    : [];


type Leaves<T, D extends number = 10> = [D] extends [never] ? never : T extends object ?
    { [K in keyof T]-?: Cons<K, Leaves<T[K], Prev[D]>> }[keyof T]
    : [];

The intent of Cons<H, T> is to take any type H and a tuple-type T and produce a new tuple with H prepended onto T. So Cons<1, [2,3,4]> should be [1,2,3,4]. The implementation uses rest/spread tuples. We’ll need this to build up paths.

The type Prev is a long tuple that you can use to get the previous number (up to a max value). So Prev[10] is 9and Prev[1] is 0. We’ll need this to limit the recursion as we proceed deeper into the object tree.

Finally, Paths<T, D> and Leaves<T, D> are implemented by walking down into each object type T and collecting keys, and Consing them onto the Paths and Leaves of the properties at those keys. The difference between them is that Paths also includes the subpaths in the union directly. By default, the depth parameter D is 10and at each step down we reduce D by one until we try to go past 0at which point we stop recursing.


Okay, let’s test it:

type NestedObjectPaths = Paths<NestedObjectType>;
// type NestedObjectPaths = [] | ["a"] | ["b"] | ["c"] | 
// ["nest"] | ["nest", "c"] | ["otherNest"] | ["otherNest", "c"]
type NestedObjectLeaves = Leaves<NestedObjectType>
// type NestedObjectLeaves = ["a"] | ["b"] | ["nest", "c"] | ["otherNest", "c"]

And to see the depth-limiting usefulness, imagine we have a tree type like this:

interface Tree {
    left: Tree,
    right: Tree,
    data: string
}

Well, Leaves<Tree> is, uh, big:

type TreeLeaves = Leaves<Tree>; // sorry, compiler 💻⌛😫
// type TreeLeaves = ["data"] | ["left", "data"] | ["right", "data"] | 
// ["left", "left", "data"] | ["left", "right", "data"] | 
// ["right", "left", "data"] | ["right", "right", "data"] | 
// ["left", "left", "left", "data"] | ... 2038 more ... | [...]

And it takes a long time for the compiler to generate it and your editor’s performance will suddenly get very very poor. Let’s limit it to something more manageable:

type TreeLeaves = Leaves<Tree, 3>;
// type TreeLeaves2 = ["data"] | ["left", "data"] | ["right", "data"] |
// ["left", "left", "data"] | ["left", "right", "data"] | 
// ["right", "left", "data"] | ["right", "right", "data"]

That forces the compiler to stop looking at a depth of 3, so all your paths are at most of length 3.


So, that works. It’s quite likely that ts-toolbelt or some other implementation might take more care not to cause the compiler to have a heart attack. So I wouldn’t necessarily say you should use this in your production code without significant testing.

But anyway here’s your desired type, assuming you have and want Paths:

type MyGenericType<T extends object> = {
    keys: Array<Paths<T>>;
};

const test: MyGenericType<NestedObjectType> = {
    keys: [['a'], ['nest', 'c']]
}

Hope that helps; good luck!

Link to code

Leave a Comment