How can I recursively and conditionally gather keys from a TypeScript nested type?

Question

I am trying to type a nested data structure in such a way that I can conditionally have all keys under which a property will always have the value of true. An example of said data structure:

type NestedData = {
  first: {
    name: string;
    age: number;
    hasPets: true;
    children: {
      second: {
        name: string;
        age: number;
        hasPets: false;
        children: {
          third: {
            name: string;
            age: number;
            hasPets: true;
          };
        };
      };
    };
  };
};

// type KeysWithPets recursively finds out exactly which of the parent objects have the "hasPets" property as true

// const someoneWithPets: KeysWithPets<NestedData> 
// should have " 'first' | 'third' " as its typing

I googled everywhere on how to do these recursive typings. So far, I tried everything I found on this (very quality) blog post to no avail: https://www.bbss.dev/posts/typescript-recursive-omit/ .

I also questioned GPT deeply, and it came up with the following typing:

type HasPetsKeys<T> = {
  [K in keyof T]: T[K] extends { hasPets: true }
    ? K
    : T[K] extends object
    ? HasPetsKeys<T[K]>
    : never;
}[keyof T];

Sadly, when I tried this, it could only gather the keys from the first level.

By my understanding, it should iterate over the keys of the Type passed as the generic parameter, and then it ask if our condition of having pets is true; if it is, it returns the current key. If not, it asks if it is an object, upon which, if truthy, should call itself again. Otherwise, it ends the particular iteration.

I suspect something wrong is happening on the recursion part of it, but can't seem to find out why. Any ideas?

You can play around with it in the following StackBlitz repro:

https://stackblitz.com/edit/typescript-n4kk61?file=index.ts&view=editor

Answer 1

The problem is that once it hits a true condition on ? K, it stops right there because it has no need to check anything after :. If you want it to go on to check the children, you need to add a union type to the ? K part that's the exact same as everything after :.

type HasPetsKeys<T> = {
  [K in keyof T]: T[K] extends { hasPets: true }
    // if true, include K and then check nested children
    ? (K | (
        T[K] extends object
        ? HasPetsKeys<T[K]>
        : never
      ))
    // otherwise, just check nested children
    : (
        T[K] extends object
        ? HasPetsKeys<T[K]>
        : never
    );
}[keyof T];

With this, it essentially goes to each node and asks "Is hasPets true? If so, add K and then check K's children. Otherwise, just check K's children." As shown below, it works.

Answer 2

The approach you've attempted is almost correct, but it lacks the handling of nested properties. The problem is that your recursive type doesn't dive into the nested 'children' property of your object structure.

To solve this, we need to make the type recursively check not only the immediate children of the object, but also the nested children. In other words, the recursion needs to happen on the 'children' field, not on the whole object.

We can achieve this by modifying your HasPetsKeys type as follows:

type HasPetsKeys<T> = {
  [K in keyof T]: T[K] extends { hasPets: true }
    ? K
    : T[K] extends { children: infer U }
    ? HasPetsKeys<U>
    : never;
}[keyof T];