typescript - Inferencia de un tipo recursivo anidado a partir de una configuración plana

Estoy tratando de escribir correctamente el tipo del valor de retorno de una función que convierte una configuración plana de una estructura similar a un árbol en la propia estructura similar a un árbol, por ejemplo:

girando esto

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

en

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

de una manera que capture nombres clave y no solo permita la indexación de cadenas anidadas (con claves que podrían no existir).

Estaba intentando empezar escribiendo la configuración (primer fragmento de código arriba) sin mucho éxito para hacer que Typescript infiriera correctamente el tipo unión de las claves mientras restringía "parentKey" a los valores disponibles, por ejemplo:

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

no funciona porque Typescript reduce T para que sea solo la unión de valores especificados en parentKey. No vincular parentKey con otras claves (por ejemplo, especificarlo como string en lugar de T) hace que TS infiera T como la unión de todas las claves pero permite poner valores inexistentes como padres.

La razón detrás de intentar hacer algo como esto es incorporar algunos valores/comportamientos de propiedades predeterminados en cada nodo del árbol sin necesidad de especificarlos manualmente repetidamente.

Agradecería cualquier indicación sobre si esto es posible de expresar en absoluto, y si es así, cómo abordarlo. Además, tal vez haya una mejor forma de representar la configuración y el árbol resultante que permita una mejor inferencia mientras aún se permite cierta augmentación de cada nodo; sería bueno ver cualquier otra idea.

Respuesta #1

Solo voy a considerar la transformación a nivel de tipo y no los problemas relacionados con la inferencia de tipos ni ningún tipo de implementación. Mi objetivo aquí es escribir un tipo de utilidad toTree<T> de manera que, dado una estructura de datos "plana" como

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

el tipo transformado ToTree<Flat> es la estructura de árbol correspondiente:

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

Esto va a ser necesariamente un tipo condicional recursivo, que tiende a tener casos límite interesantes. Y si el comportamiento en casos límite de un tipo condicional recursivo no es deseable, a veces requiere una refactorización significativa para tenerlo en cuenta. Así que ten cuidado.

Mi enfoque se ve así. Primero voy a escribir un tipo de utilidad intermedio ToTreeInner<T> que asume que cada propiedad en T tiene una propiedad parentKey que es una clave o undefined. Así que en lugar de { key1: { property: "value1" }}, necesitaría { key1: { property: "value1", parentKey: undefined }}. Esto simplemente hace que sea mucho más sencillo de implementar, ya que siempre podemos simplemente tomar la propiedad parentKey sin tener que escribir lógica para manejar claves faltantes cada vez. Luego, si tenemos ToTreeInner, podemos escribir ToTree así:

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

Eso permite que cada propiedad de T tenga opcionalmente una propiedad parentKey (y he añadido una firma de índice genérica para no encontrarse con detección de tipo débil). Luego añade un valor undefined para parentKey a cualquier propiedad que no tenga dicha propiedad, antes de pasarlo a ToTreeInner.

Así que ahora implementemos 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
  };

Esta función de tipo toma dos argumentos de tipo. El tipo T es la estructura completa y plana, mientras que P es el nombre de la clave principal para el nodo actual en el árbol de salida. Esto puede ser undefined si estamos en la raíz del árbol, y por defecto es undefined, por lo que puedes omitir ese argumento de tipo para obtener el árbol completo.

Luego tenemos un tipo con clave remapeada { [K in keyof T as P extends T[K]["parentKey"] ? K : never]: ⋯ } que utiliza esa cláusula as para filtrar las claves. El objeto de salida solo tendrá una clave K si P extends T[K]["parentKey"], lo que significa que solo tendrá una clave K si la propiedad correspondiente en T tiene un parentKey de P.

Y el valor en la clave K es esencialmente Omit<T[K], "parentKey"> & ToTreeInner<T, K>. Usamos el tipo de utilidad Omit para eliminar la propiedad parentKey (ya que no queremos que la salida tenga propiedades parentKey). Y lo intersectamos con la llamada recursiva ToTreeInner<T, K>, lo que significa que también añadiremos un nuevo árbol aquí mismo, con raíz en la clave actual K.

Eso es básicamente todo, pero si usas eso directamente y muestras el tipo de salida, obtendrías un desastre horrible con Omit anidados e intersecciones y tipos DeepTreeInner. Así que uso un truco descrito en Cómo puedo ver el contrato completo expandido de un tipo de Typescript? para expandir el tipo a un tipo de propiedad único. En lugar de PossiblyUglyType, escribo PossiblyUglyType extends infer O ? { [K in keyof O]: O[K] } : never, lo que "copia" PossiblyUglyType en un nuevo parámetro de tipo O, y luego recorre las propiedades de O sin modificarlas. Esto es esencialmente un gran no-op más o menos, pero afecta la visualización.

Así que probémoslo:

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

Se ve bien. Solo intentemos otra cosa:

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;
        };
    };
} */

¡También se ve bien!

Enlace de Playground al código

Respuesta #2

Esto es un comienzo. No es muy bonito, y no funciona de manera recursiva:

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