Inference of a nested recursive type from a flat configuration

Question

I am trying to properly type the return value of a function that converts a flat configuration of a tree-like structure into the tree-like structure itself, e.g.:

turning this

{
  key1: { property: "value1" },
  key2: { property: "value2" },
  key3: { property: "value3", parentKey: "key2"},
  key4: { property: "value4", parentKey: "key3" }
}

into

{
  key1: { property: "value1", ... },
  key2: {
    property: "value2",
    key3: {
      property: "value3", ...,
      key4: { property: "value4", ... }
    }
  }
}

in a way that captures key names and not just allowing nested string indexing (with potentially non-existent keys).

I was trying to start with typing the configuration (first code snippet above) without much luck to make Typescript properly infer they keys union type while restricting "parentKey" to available values, e.g.:

type Config<T extends string> = Record<T, Properties & { parentKey?: T }>;

does not work because Typescript narrows T to be only union of values specified in parentKey. Not tying parentKey to other keys (e.g. specify it as string instead of T) make TS infer T as union of all the keys but lets putting nonexistent values as parents.

---

Reason behind trying to do something like this is to embed some default property values/behaviors into each node of the tree without need in specifying them manually repeatedly.

---

Appreciate any pointers as to whether this is possible to express at all, if yes, then how to approach it. Also, maybe there is a better form for representing the config and resulting tree that would allow better inference while still letting some augmentation of each node - would be nice to see any other ideas.

Answer 1

I'm only going to consider the type-level transformation and not issues about type inference or any sort of implementation. My goal here is to write a utility type toTree<T> such that given a "flat" data structure like

type Flat = {
  key1: { property: "value1" },
  key2: { property: "value2" },
  key3: { property: "value3", parentKey: "key2" },
  key4: { property: "value4", parentKey: "key3" }
};

the transformed type ToTree<Flat> is the corresponding tree structure:

type Tree = ToTree<Flat>;
/* type Tree = {
    key1: { property: "value1"; };
    key2: {
        property: "value2";
        key3: {
            property: "value3";
            key4: { property: "value4"; };
        };
    };
 */

This is necessarily going to be a recursive conditional type, which tend to have interesting edge cases. And if the edge-case behavior of a recursive conditional type isn't desirable, it sometimes requires significant refactoring to account for it. So be warned.

---

My approach looks like this. First I'm going to write an intermediate utility type ToTreeInner<T> that assumes every property in T has a parentKey property which is either a key or undefined. So instead of { key1: { property: "value1" }}, it would need { key1: { property: "value1", parentKey: undefined }}. This just makes it a lot more straightforward to implement, since we can always just grab the parentKey property without having to write logic for dealing with missing keys every time. Then if we have ToTreeInner, we can write ToTree like this:

type ToTree<T extends Record<keyof T, {
  parentKey?: PropertyKey, [k: string]: any
}>> = ToTreeInner<{ [K in keyof T]: T[K] & (
  "parentKey" extends keyof T[K] ? unknown : { parentKey: undefined }
) }>;

That allows each property of T to optionally have a parentKey property (and I've added a catch-all index signature so as to not run into weak type detection). It then adds an undefined value for parentKey to any property that doesn't have such a property, before passing it to ToTreeInner.

So now let's implement ToTreeInner:

type ToTreeInner<
  T extends Record<keyof T, { parentKey: PropertyKey | undefined }>,
  P extends PropertyKey | undefined = undefined
> = { [K in keyof T as P extends T[K]["parentKey"] ? K : never]:
    (Omit<T[K], "parentKey"> & ToTreeInner<T, K>) extends
    infer O ? { [K in keyof O]: O[K] } : never
  };

This type function takes two type arguments. The type T is the full flat structure, while P is the name of the parent key for the current node in the output tree. This can be undefined if we're at the root of the tree, and it defaults to undefined so you can leave out that type argument to get the full tree.

Then we have a key-remapped type { [K in keyof T as P extends T[K]["parentKey"] ? K : never]: ⋯ } which uses that as clause to filter the keys. The output object will only have a key K if P extends T[K]["parentKey"], meaning that it will only have a key K if the corresponding property in T has a parentKey of P.

And the value at key K is essentially Omit<T[K], "parentKey"> & ToTreeInner<T, K>. We use the Omit utility type to strip the parentKey property out (since we don't want the output to have parentKey properties). And we intersect it with the recursive call ToTreeInner<T, K>, meaning that we will also add a new tree right here, rooted at the current key K.

That's basically the whole thing, but if you use that directly and display the output type you'd get an awful mess with nested Omits and intersections and DeepTreeInner types. So I use a trick described at How can I see the full expanded contract of a Typescript type? to expand the type to a single property type. Instead of PossiblyUglyType, I write PossiblyUglyType extends infer O ? { [K in keyof O]: O[K] } : never, which "copies" PossiblyUglyType into a new type parameter O, and then walks over the properties of O without modifying them. This is essentially a big no-op more or less, but it affects the display.

---

So let's try it:

type Tree = ToTree<Flat>;
/* type Tree = {
    key1: { property: "value1"; };
    key2: {
        property: "value2";
        key3: {
            property: "value3";
            key4: { property: "value4"; };
        };
    };
 */

Looks good. Let's just try something else:

type Test = ToTree<{
  a: { b: string, c: number },
  d: { e: boolean, parentKey: "a" },
  f: { g: Date, parentKey: "a" },
  h: { i: any, parentKey: "d" }
}>
/* type Test = {
    a: {
        b: string;
        c: number;
        d: {
            e: boolean;
            h: {
                i: any;
            };
        };
        f: {
            g: Date;
        };
    };
} */

Also looks good!

Playground link to code

Answer 2

This is a start. Not very pretty, and doesn't work recursively:

type UnionToIntersection<U> = 
  (U extends any ? (k: U)=>void : never) extends ((k: infer I)=>void) ? I : never;

type ParentKeys<T> = keyof T extends infer K
  ? K extends keyof T
    ? T[K] extends { parentKey: any; }
      ? K
      : never
    : never
  : never;

type GetChildren<T extends {}> = keyof T extends infer K
  ? K extends keyof T
    ? T[K] extends { readonly parentKey: infer U; }
      ? U extends string ? { [u in U]: { [k in K]: T[K] } } : never
      : never
    : never
  : never;

type Convert<T extends {}> = {
  [K in keyof Omit<T, ParentKeys<T>>]: K extends keyof UnionToIntersection<GetChildren<T>>
    ? T[K] & UnionToIntersection<GetChildren<T>>[K]
    : T[K]
};

const test = {
  key1: { property: "value1" },
  key2: { property: "value2" },
  key3: { property: "value3", parentKey: "key2" },
  key4: { property: "value4", parentKey: "key3" }
} as const;

type Result = Convert<typeof test>;