I use an object to hold all of the state in an app. This object is arbitrarily deeply nested and so I want to be able to describe a path to select only a part of this state.
I have written a recursive type which is covering all my needs:
- It allows to describe any path through an object from the top (root) node down to every child property in the object as a string array
- It allows to stop at any level
- It doesn’t allow to select sibling or ancestor nodes, only children
- If a property of the object holds an array, it allows to select an array entry either via a predicate function or a numeric index
This works but when playing around with a quite simple state interface, the recursion already made it super slow.
So I decided to limit the depth of the typing support to only some levels, after that it would fall back to an “any” type:
// Helpers for limiting levels
type Digit = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15;
type NextDigit = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 'STOP'];
type Increment<Depth> = Depth extends Digit ? NextDigit[Depth] : 'STOP';
export type PredicateFunction<ArrayType> = (array: ArrayType, index?: number) => boolean;
export type IndexOrPredicateFunction<Type> = number | PredicateFunction<Type>;
export type StatePathKey = IndexOrPredicateFunction<any> | string;
// The type for the path
export type StatePath<Obj, Path extends (string | IndexOrPredicateFunction<any>)[] = [], Depth = 0> = Obj extends object ?
(Path |
// Check if depth > max allowed
(Depth extends string ?
// ...if yes, don't typecheck deeper levels and allow everything (for performance reasons)
[...Path, ...any[]] :
// ...otherwise check if object is array
(Obj extends readonly any[] ?
// ...when array only allow index or PredicateFunction
StatePath<Obj[number], [...Path, IndexOrPredicateFunction<Obj[number]>], Increment<Depth>>
// ...when object generate type of all possible keys
: { [Key in string & keyof Obj]: StatePath<Obj[Key], [...Path, Key], Increment<Depth>> }[string & keyof Obj])))
: Path;
// Sample State:
export interface State {
app: {
testEntry: string;
testArray: {
firstname: string,
lastname: string,
address?: {
zip: number;
street: string;
doorNumbers: {
number: number;
appendixes: number[];
}[]
}
}[];
}
}
// Samples for valid paths (StatePath<State>):
['app', 'testEntry']
['app', 'testArray']
['app', 'testArray', 1, 'firstname']
['app', 'testArray', 5, 'address', 'doorNumbers', doorNumber => doorNumber.number === 1, 'appendixes']
...
This is working “okay” with the small state interface (though I already had long compile times), but is way too slow with a real life state interface.
Any idea how I could change this type to achieve the same with better performance?
Recursion without limits would be the optimum, but it would be acceptable to take out the recursion and manually loops for e.g. 10 levels and fall back to “any” for longer arrays.
18
When you have a generic type implemented as a deeply nested recursive conditional type, you should take care to deal with what happens for arbitrary/unexpected type arguments, and try to make sure that there’s no input that will either fail to hit your base case, or cause a combinatorial explosion of computation. Where applicable, try inputs like {}, object, unknown, null, undefined, and unions of types.
Even if you never plan on passing such type arguments to your type, TypeScript might compute those types itself while it tries to compute constraints for things that use your type.
In your case, if you have StatePath<Obj> where Obj is generic, you can expect TypeScript might decide to substitute Obj with its constraint, which is (implicitly) unknown. So if StatePath<unknown> never reaches the base case of your recursion, then you can expect terrible compile times.
I’d say that in your case you are checking if Obj extends object, but if Obj is itself object or unknown it looks like TypeScript spends a lot of time recursing down. Let’s nip that in the bud by adding a way to bail out if Obj is wide:
type StatePath<Obj, Path extends (string | IndexOrPredicateFunction<any>)[] = [], Depth = 0> =
object extends Obj ? Path : ( ⋯ )
where ⋯ is your original definition.
Another problem is what happens when an input is a big union of things. If you’re using any distributive conditional types then TypeScript will evaluate the conditional type once per union member. If this recurses you can end up with a big explosion of types, even if the unions aren’t that large to start with.
For example, your Depth type parameter might be specified as a union of things like Digit. Do you care about supporting the bizarre case where the depth is 0 | 4 | 10? Probably not. Ideally you’d want to just bail out at that point also. So you can move away from the distributive conditional type Depth extends string ? ⋯ : ⋯ and use the non-distributive version [Depth] extends [string] ? ⋯ : ⋯.
Anywhere you use distributive conditional types in a deeply recursive type, you should do so because you really want to process unions. Otherwise you’re just making more work for the compiler.
So now you have something like
type StatePath<Obj, Path extends (string | IndexOrPredicateFunction<any>)[] = [], Depth = 0> =
object extends Obj ? Path : (
Obj extends object ? (Path |
([Depth] extends [string] ? ⋯ : (⋯))
) : Path
);
This should speed up computation quite a bit. There of course could be other edge cases, so you’ll need to do lots of testing and handle any remaining problems.
Playground link to code
1