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 for the following error and see all the results!
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 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.
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.
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.
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). 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.
// 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.
// 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.
// 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.
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:
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.
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.
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.
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.
Would love to know if you find this useful or if you spot any issues that I have missed!
Top comments (3)
Turns out is is much easier to use the following to count levels of recursion
Along with the following to increment the level
Very cool, thanks for the write up!
Hello,
i think we shoud add 0 in type
Digit.