how do i get a deep Keyof with dot access paths that allow circular referencing

Question

I am attempting to make a generic type that takes an object, and returns a union of path strings for all of its nested keys that are objects or object arrays.

For example:

type Tag = { name: string, countries: Country[], companies: Company[] }
type Company = { name: string, country: Country, tags: Tag[]  };
type Country = { name: string, companies: Company[], tags: Tag[] };

type RelationsOf<T extends object> = { // ...need help // }
type CompanyRelations = RelationsOf<Company> // "country" | "country.companies" | "tags" | "tags.countries" | etc (up to depth limit)
type CountryRelations = RelationsOf<Country> // "companies" | "companies.country" | "tags" | "tags.companies" | etc (up to depth limit)

// ... elsewhere ///
type Populated<T extends object, Relations extends RelationsOf<T> = { // ... different problem, but shows intention // }
type SuperPopulatedCompany = Populated<Company, "country" | "country.companies" | "country.companies.tags" | "tags" | "tags.company" | etc (depth limit) >
/** 
{
    name: string;
    country: null | Populated<Country, "companies" | "companies.tags">
    tags: Populated<Tag, "company">[]
}

All of my attempts are met with an error like 'expression is too deep and possibly infinite' due to the cyclical referencing. Setting a depth limit of, say, 3 would be fine if it's possible to increment a depth counter. The point of this is to be used with TypeORM so that when I query relations on an entity, I can cast the result to an entity type with those relations populated instead of everything optional (it doesn't do this out of the box, and I can't find any tips on how to get that happening). So it would end up being used by something like:

const getCompany = <T extends RelationsOf<Company>[]>(id: string, relations: T) => {
    return companyRepository.find({
        id, 
        relations, // eg ['countries', 'tags', 'tags.companies'] 
    }) as Populated<Company, T[number]>
}



// ... elsewhere //
getCompany(['countries', 'tags', 'tags.companies']) // returns Populated<Company, "countries" | "tags" | "tags.companies">

In your example you write `| etc` twice, but what exact value do you expect to see there? If it's truly an infinite list as would be implied, then what are looking for is impossible, since TypeScript unions can hold up to ~100K members max, which is a bit less than infinite. — jcalz, Apr 20 '22 at 15:57
And yes, this seems to be multiple questions in one and you should focus on just one of them for a single post. Please [edit] the question so it has a primary question and try to remove dependencies on other stuff; you can always open a new post for the other part. — jcalz, Apr 20 '22 at 15:58
@jcalz Yes, I'll update the question to allow for a max depth. Could just be set to an arbitrary number of 10 — Gisheri, Apr 20 '22 at 17:12
You are imagining 10 to be a small number, here, but the size of the union increases exponentially with depth. Look at [this implementation](https://tsplay.dev/WKqK8N) of `RelationsOf`, for example. Will you really be using such depths in your code? — jcalz, Apr 20 '22 at 17:42
I could reduce to 3 and still hit probably all real world use cases. Your implementation seems to work great. If you want to use it as an answer, I'll mark it as accepted. — Gisheri, Apr 20 '22 at 17:56
Okay, but what about `Populated`? Is that important for this question or not? If so, then it needs to be explained more (because I don't understand where `null` comes from in the output), but *ideally* should be broken into a second question. Otherwise it should be removed. (Either way, [this](https://tsplay.dev/w2av4W) is my first attempt) — jcalz, Apr 20 '22 at 17:59
As you said, it's definitely two questions. I changed the wording in the question to make it clearer that I'm only after the deep key of aspect in this scope. — Gisheri, Apr 20 '22 at 18:53
I created another question for the second part of this if you're interested in taking a look. https://stackoverflow.com/questions/71946569/how-can-i-populate-an-object-types-optional-nested-relations-using-string-union — Gisheri, Apr 20 '22 at 21:54
I might look but I’m not familiar with typeorm so maybe that’s why I can’t understand why some properties are “null” and others are not — jcalz, Apr 20 '22 at 22:13
For sure, I put a comment in that question regarding that if you end up checking it out. — Gisheri, Apr 20 '22 at 22:22

score 3 · Accepted Answer · answered Apr 20 '22 at 19:32

Your RelationsOf<T> is similar in spirit to Paths<T> as described in the answer to a similar question. Like Paths<T>, such deeply nested types are tricky and fragile, and can easily cause the compiler to complain about instantiation depth (if you're lucky) or get completely bogged down and unresponsive (if you're unlucky). For any recursive type, the number of potential paths through an object type tends to be exponential in the path depth. Depth limiting is therefore a good idea, although sometimes even with depth limiting there are problems with compiler performance.

Here's one way to implement RelationsOf<T, D> where D is an optional numeric literal type corresponding to the desired depth (if you don't specify D then it defaults to 3):

type RelationsOf<T extends object, D extends number = 3> =
  [D] extends [0] ? never :
  T extends object[] ? RelationsOf<T[number], D> :
  keyof T extends infer K ?
  K extends string & keyof T ?
  T[K] extends object ?
  K | `${K}.${RelationsOf<T[K], Prev[D]>}` :
  never : never : never;

type Prev = [never, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];

The Prev type is a helper so that the compiler can easily subtract one from anything you give as D (e.g., Prev[10] is 9); it currently stops at 15. You could make it longer, but you'll probably run into depth problems.

The way it works: to compute RelationsOf<T, D> we first check to see if D is 0. If so, we bail out. Otherwise we check to see if T is an array of objects. If so, we compute RelationsOf<T[number], D> where T[number] is the element type of the T array. (We do this to skip one level of depth corresponding to the keys of arrays; otherwise you'd end up with paths like `tags.${number}.companies` instead of "tags.companies".)

At this point we use a distributive conditional type to take keyof T and perform a type operation for each string union member K. So if keyof T is "name" | "country" | "tags", then K will be "name", "country", and "tags" in turn, and the result of our type operation will be joined in a union.

The type operation is: if the property type of T at key K (T[K]) is an object, then we compute K | `${K}.${RelationsOf<T[K], Prev[D]>}`. Meaning, we take the key itself plain, and we prepend it (and a dot) to the results of RelationsOf operating on the property type with the depth reduced by one. If T[K] isn't an object, then we use never, since we don't want that key in our output type.

Let's test it out:

type CompanyRelations = RelationsOf<Company>;
/* type CompanyRelations = "country" | "tags" | "tags.companies" | 
    "tags.countries" | "country.tags" | "country.companies" | 
    "country.tags.companies" | "country.tags.countries" | 
    "country.companies.country" | "country.companies.tags" | 
    "tags.companies.country" | "tags.companies.tags" | 
    "tags.countries.tags" | "tags.countries.companies" */

type CountryRelations = RelationsOf<Country>;
/* type CountryRelations = "companies" | "tags" | "tags.companies" | 
    "tags.countries" | "companies.tags" |   "companies.country" | 
    "companies.tags.companies" | "companies.tags.countries" | 
    "companies.country.companies" | "companies.country.tags" | 
    "tags.companies.tags" |   "tags.companies.country" | 
    "tags.countries.companies" | "tags.countries.tags" */

That looks right. Everything has a path length of at most 3. If we increase D, we see how the union gets longer (with the paths getting longer too):

type CompanyRelations4 = RelationsOf<Company, 4>
/* type CompanyRelations4 = "country" | "tags" | "tags.companies" | 
     "tags.countries" | "tags.companies.country" | "tags.companies.tags" | 
     "tags.countries.tags" | "tags.countries.companies" | "country.tags" |
     "country.companies" | "country.companies.country" | 
     "country.companies.tags" | "country.tags.companies" | 
     "country.tags.countries" | "country.tags.companies.country" | 
     "country.tags.companies.tags" | "country.tags.countries.tags" | 
     "country.tags.countries.companies" | "country.companies.tags.companies" | 
     "country.companies.tags.countries" | "country.companies.country.tags" | 
     "country.companies.country.companies" | "tags.companies.tags.companies" | 
     "tags.companies.tags.countries" | "tags.companies.country.tags" | 
     "tags.companies.country.companies" | "tags.countries.companies.country" | 
     "tags.countries.companies.tags" | "tags.countries.tags.companies" | 
     "tags.countries.tags.countries" */

If we try 10 the compile won't even list them out individually because there are more than 2000 entries;

type CompanyRelations10 = RelationsOf<Company, 10>;
/* type CompanyRelations10 = "country" | "tags" | "tags.companies" | 
     "tags.countries" | "tags.companies.country" | "tags.companies.tags" | 
     "tags.countries.tags" | "tags.countries.companies" | "country.tags" | 
     ... 2036 more ... | 
     "tags.countries.tags.countries.companies.country.companies.country.tags.countries" 
*/

Okay, looks good.

Playground link to code

how do i get a deep Keyof with dot access paths that allow circular referencing

1 Answers1

Linked