Extract nested type by condition while tracking deep path

Issue

Given the following object structure:

type IObject = { id: string, path: string, children?: IObject[] }

const tree = [
    {
      id: 'obj1' as const,
      path: 'path1' as const,
      children: [
        {
          id: 'obj2' as const,
          path: ':pathParam' as const,
          children: [
            {
              id: 'obj3' as const,
              path: 'path3' as const
            }
          ]
        },
        {
          id: 'obj4' as const,
          path: 'path4' as const,
          children: [
            {
              id: 'obj5' as const,
              path: 'path5' as const
            }
          ]
        }
      ]
    }
  ];

I am trying to extract the type of a nested object PLUS the an accumulation of the path fragments to that nested type. (assuming ids are unique across the object) example

type ok = FindAndTrackDeepPath<'obj2', typeof tree>['fullPath'];
// type ok = "/path1/:pathParam"

I tried the following which i think is close. However, as you can see in the second (non working) example, there seems to be an issue when descending the type recursively.

export type FindAndTrackDeepPath<
  ID,
  T extends IObject[],
  depth extends number = 1,
  path extends string = '',
  maxDepth extends number = 10
> = depth extends maxDepth
  ? never
  : FindByID<ID, T> extends never
    ? FindAndTrackDeepPath<
        ID,
        Descend<T>['children'],
        Increment<depth>,
        Descend<T>['path'] extends undefined ? '' : `${path}/${Descend<T>['path']}`
      >
    : FindByID<ID, T> & { fullPath: `${path}/${FindByID<ID, T>['path']}` };


// helpers
type FindByID<ID, T extends IObject[]> = Extract<T[number], { id: ID }>;
type Descend<T extends IObject[]> = Extract<T[number], { children: IObject[] }>;
type Increment<N extends number> = [1,2,3,4,5,6,7,8,9,10,11,12,...number[]][N];

// examples
type ok = FindAndTrackDeepPath<'obj2', typeof tree>['fullPath'];
// type ok = "/path1/:pathParam"
type notOK = FindAndTrackDeepPath<'obj3', typeof tree>['fullPath'];
// type notOK = "/path1/:pathParam/path3" | "/path1/path4/path3"

type notOK has two alternatives, one of which is obviously wrong.

I think the problem is that when descending recursively a union of all options at each level is created in a "breadth first" kind of way. (i.e. somthing like this happens: ${("/path1/:pathParam" | "/path1/path4")}/path3"}) I have tried several ways to further prune unsuccessful descends/"parts of the unions" while descending. To no avail.

I have found a few related questions here and here. These, however, extract all possible paths. Instead i want to only extract the path for a child type matching specific criteria (in my case extends { id: ID}).

Can anyone help me out here? Is this even possible?

TS Playground example

Solution

Here's one possible implementation of what I'm calling IdxWithFullPath<I, T>, where I is the generic id type you're looking for inside of the IObject-or-IObject[] T type. It will evaluate to the intersection of the IObject that has an id assignable to type I, and an object with a fullPath property corresponding to the concatenation of all the path properties in the tree from the root down to the IObject in question:

type IdxWithFullPath<I, T, P extends string = ""> =
  T extends IObject[] ? IdxWithFullPath<I, T[number], P> :
  T extends IObject ? (
    I extends T["id"] ? (
      T & { fullPath: `${P}/${T["path"]}` }
    ) : (
      IdxWithFullPath<I, T["children"], `${P}/${T["path"]}`>
    )
  ) :
  never;

There's a third generic type parameter P corresponding to the parent path; this allows IdxWithFullPath to be recursive. It defaults to the empty string literal type, the path of the root of the tree.

Note that it is a distributive conditional type in T. That means if T is a union, then it will be split into individual members which will be processed separately, and the results will be joined back into a union. Since the never type gets absorbed into unions, that means we can just return never for anything we don't want to include.

So, if T is an array of IObjects, then we want to operate instead on T[number], the union of IObject element types.

Otherwise, if T is an IObject, we check its id property. If it matches I then we return the desired intersection, where the fullPath is the parent path stored in P concatenated with the path property of the current IObject, using template literal types. If it doesn't match I then we have to recurse down into children, appending path to P to be the new parent path.

And finally, if T is something else then we return never so that it's not included in the result. This will happen when the search bottoms out, such as with a missing children property: I think if children is missing, then T["children"] will evaluate to unknown, and when children is present but undefined then T["children"] will evaluate to undefined. We want neither of those to be included.

---

Let's test it out:

type Ok = IdxWithFullPath<'obj2', typeof tree>;
/* type Ok = {
    id: "obj2";
    path: ":pathParam";
    children: {
        id: "obj3";
        path: "path3";
    }[];
} & {
    fullPath: "/path1/:pathParam";
} */

type AlsoOK = IdxWithFullPath<'obj3', typeof tree>;
/* type AlsoOK = {
    id: "obj3";
    path: "path3";
} & {
    fullPath: "/path1/:pathParam/path3";
} */

---

Looks good. Note that such deeply recursive conditional types tend to have bizarre edge cases that sometimes require significant refactoring in order to resolve. With any such type, you should test heavily against expected use cases before proceeding, and be prepared to have to modify or even abandon an approach if you find unacceptably bad edge case behavior.

Playground link to code

Answered By - jcalz