Supporting Circularly Referenced Mapped Types in Typescript
Tags: typescript
Published: 2023-09-22 10:03:27

Recursive structures are very common across many applications but they can pose a big challenge to Typescript. While in our real data the recursion may only go a few levels, Typescript does not know this which can prose big problems for custom types. Just [search](https://www.google.com/search?q=Type+of+property+circularly+references+itself+in+mapped+type) for the following error and see all the results!

```ts
Type of property circularly references itself in mapped type 
```

In the remainder of this post I will share how I resolved this error for a type called `NestedFieldPaths<TData>` that is a key part of the [AG Grid](https://ag-grid.com/) library. 

## Context for Error

In AG Grid when configuring the grid that are two main parts, columns and rowData. The most important part of the column is the `field` property which describes which property from the row data should be displayed. The `field` property can access deeply nested properties via a dot separated string.

So if the user provides the `Person` interface to `ColDef<Person>` the valid field properties will be as follows: `name`, `age`, `address`, `address.firstLine` and `address.city`.

```ts
interface Person {
    name: string;
    age: number;
    address:  {
        firstLine: string;
        city: string;
    }
}
```

We achieve this via a generic type helper called `NestedFieldPaths<TData>` which extracts all the possible paths from the provided interface. This works great and brought a new level of type checking an DX via auto completion for the `field` property.


## Recursive Interface Issue

This works great until you update the `Person` interface to also include a `child: Person` property making the interface recursive.

```ts
interface Person {
    name: string;
    age: number;
    // interface refers to itself recursively
    child: Person;
}
```

Pass this to `NestedFieldPaths<Person>` and instead of getting all the possible paths, i.e `value`, `child.value`, `child.child.value` and so on and you will get the following error.

```ts
Type of property 'children' circularly references itself in mapped type
```

This prevents the use of recursive interfaces with the `NestedFieldPaths`. Which makes people sad ([Github Issue](https://github.com/ag-grid/ag-grid/issues/6741#issuecomment-1590574851)). So what can we do about this?

### Potential Solutions

There are a number of unsatisfactory approaches such as not supporting recursive interfaces, or forcing the user to do some trickery to the interface that they provide to make it less recursive. 

We cannot get round the fact that Typescript has to bail at some point so that it does not get stuck in an infinite loop. But is there something that we can do to make a type practically useable?

Best of both worlds is:
 - support a fixed number of recursions 
 - beyond this give the user freedom to do whatever they like

We definitely want to be able to support these interfaces as they correctly explain the data that users want to display with AG Grid. So how can we do it?

## Count Recursion Levels and exit at a given depth

The idea is to count how deep we have recursed and at a given level, say 6, bail from the recursion and let the rest of the path match anything. This last part is key because as soon as you set an arbitrary limit someone is going to actually specify a path that goes beyond that limit and we do not want to prevent that.

The first typing tool that we need is to be able to count levels of recursion. We can achieve this with the following type structure. 

We first define a union of numbers that are within the depth level that we support. For this type we will go 7 levels deep so have the digits up to 7.

```ts
// Union of numbers within our depth limit
type Digit = 1 | 2 | 3 | 4 | 5 | 6 | 7 ;
```

We then construct an array of those same digits but crucially where their index in the array is one less then their own value. So for example at index `1` we have the value `2` and at index `2` we have `3`. 

```ts
// Array where each value is one greater than its index in the array
type NextDigit = [1, 2, 3, 4, 5, 6, 7, 'STOP'];
```

You can see how by using our current digit we can index the `NextDigit` array to get the next value. Putting these together we can setup the `Inc<T>` type utility which will give us the next digit. 

```ts
// Type to get the number from the index in the array
type Inc<T> = T extends Digit ? NextDigit[T] : 'STOP'; 
```

But how do we stop? Well you can see that the last element in the `NextDigit` type is the string `STOP` which clearly is not a `Digit`. We can use this along with a check in `Inc<T>` to ensure that we stop changing the value returned from `Inc` and we will be able to pick a different path based on the return type of `STOP`.

```ts
type ShouldStop = Inc<7> extends 'STOP' ? true : false;
```

For our use case stopping the recursion means letting the user type any string path after the given path. The key part of our type to achieve this is as follows:

```ts
type NestedPath<TValue, Prefix extends string, TDepth> = 
    TValue extends object
        // Return any to allow any further string to be appended
        ? `${Prefix}.${ TDepth extends 'STOP' ? any : NestedFieldPaths<TValue, TDepth>}`
        : never;
```

This type checks if the current `TValue` is an object and if it is then it checks if the current `TDepth` = `STOP`. If it is then we append `any` to the string literal type. If we have not reached `STOP` yet it will recurse on the child properties of `TValue`. 

Note that we are not incrementing `TDepth` in this type because the recursion happens across two interfaces. The higher level interface of `NestedFieldPaths` is responsible for calling `Inc<TDepth>` when it calls `NestedPath`. In this way each level of the input type will increment depth by one.

```ts
type NestedFieldPaths<TData = any, TDepth = 0> = {
    [TKey in StringOrNumKeys<TData>]:
        | `${TKey}`
        | NestedPath<TData[TKey], `${TKey}`, Inc<TDepth>>;
}[StringOrNumKeys<TData>];
```

## Recursive Support for Nested Field Paths

By introducing this counter and stop logic we can now support recursive interfaces with the desired goals of:
 - support a fixed number of recursions 
 - beyond this limit give the user freedom to do whatever they like

Autocompletion clearly shows the depth value kicking in and stopping the recursion.


![Auto complete with limited recursion](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/nycav8zrsl6kp1298zmi.png)

## Considerations

One potential downside of this approach is that if you have a nested object with *no* recursion, that goes beyond our depth limit, then those deeper levels will no longer be autocompleted. This is a trade off that we have decided to accept as we hope that nesting beyond 6 levels should be less common then having recursive interfaces.

The only other consideration is that you cannot increase the depth limit arbitrarily as you can still cause Typescript to bail on you if it thinks the type is getting too complex. This is why we have set a limit of 7, as in testing we found going above this caused the following error.

```ts
error TS2589: Type instantiation is excessively deep and possibly infinite.
```

## Playground

If you want to experiment this type yourself you can find it in the following [Ts Playground](https://www.typescriptlang.org/play?ts=4.3.5#code/C4TwDgpgBAIglgczsKBeKBGKAfKAmHKAZkIBZCBWQgNkIHZCAOQgTgG4AoUSKAOQgAeweEhToA2hgA0+GURmkZFGdRl0ZAcgDKAFQDyABQ0BdTt2gBJAHYBjADw6AfGig6og4BCsATAM6xEZCgAfj4PEWRxHWMoAC4obX0jNigucGgtYAAnOCsEPSzeAFcAWwBpCBBfBz0AIwArZ3QAa0qAewAzVzr6qAAyKAAKX2zchEIrUtqILIBKM3SwkYhvAwBDYAALBwA1NYAbIogZAyyIDrgBdyEvPygRnLyZHT3DiH5l7wBhTbh972eMAgYC2TVSUAhrleR2unh8-jaDQgNmAHEh6JCUAABgASADep3OlwAvgA6fGuIEgzaw27+RKGDSYtZWEBxJaebwAMTgEH+6y21ReByOz2h7wgnx+fwBlOBoOJWLRGIh8SsEAAbjNOIIwG0sihzFAvm19kCOjy+d4HDANmsXCyQGKRdB0I6wTpbcB7R46VBHZiPpzLfyNpshV61s63jIMM41ZrtRxdfrDYsgysQ6swxG7Q7WdGYW6C3LqS4AAxgvHKiFRCps3JQTKPfKFUr13PexzGWI1jG4Qaeu11yoxX3wqEuzG4vE6euK9nqrVzPvo3AZ7NbG3DuejmQz3cgRWF45Qaz2T3yzaORycYniZtjArFcqVTtrbucDgcAD0ACo-zRP9XEWYA2n9BA1lyEZwT-H8OFyTwsg6NYbGgE0zXObdvXzJ1JzeXDnGrdELitYJ4gw80s2wqN8KOW8OGJb9EJmFC0LPAAlNoAHdIygYioCsNYSggeIHjGKRlTWBBRMEqYkwhGxfn+eILC43i81wSYSmmLI72-Gw2isGDDP2CjTXNFw8SgUiVI0R0tjGAB9AB1ZBNic3g2icnR0g0JjDOMlBTP8czMI6Ow1J4yNHHEGIJGVASIVs7x4nsmSNGVYlJIhH8f2NFlaR8f1-H2IzxjWfwQDaIooG4lkUETKwoDgLo1iKMCoEMkowH2CBgDgIz7jAsB-G4-VmjGRKUrSpSZVJOb-gW5TvGW+bFtWja1qWratqEkT-I4UxvxTA0WqsJC2MsSN1P4vs4FS4aWxyyERN8XxpNk8Snj7EYNiKXw0rOepkU5JlcA0M49QNFZwYSNYwDALI2i1bwNBkcFIQ2s4rFUm6eLiwgih8Il1W8fTApM01fCwMLzUi-HuNi+KoHERK+xmhJsa8TKIWy6beRUhIHsO47mIu1jUMsdTIywAT9q+0YfohT61XkvTlQ2+Ikq6laFbEpWEE4Pn9I4SngtNPA6fOKybMF1L7NZRy8lc9zPO83zIEO82uupghrYiqKNO9ONCYSiEdc59KIF5qB+YjqPdr14SY6Y0wgA).

Would love to know if you find this useful or if you spot any issues that I have missed!