Cache specific utility types

[tjjfvi]

Search Terms

cache types

Suggestion

(WIP; syntax bikeshed-able)

A new keyword expensive, used as below

expensive type T<U> = /* ... */;

When a generic type uses the expensive keyword, it marks it to be cached by the compiler.
The compiler will hash the type alias (generics unresolved) and the passed type parameters, and use that to memoize the resulting type.

Suggestions for hashing the types:

• For referenced external type aliases, hash the definition recursively
• For unique symbol types and classes with private properties, it also hashes the relevant name & source file path
• For type parameters & infers, it labels them T0, T1, etc. (as they appear), and hashes them as such
• Object types & interface types hash their properties in a specific order
• Labeled tuples do not hash their labels
• JSDoc is ignored (possible exception of Feature Request: Documented Utility Type #41165)

Use Cases

With complex utility types, perf can often be sluggish as "semantic information produced from type computation is recomputed fresh on each edit"

Suggestion adapted from a comment on #41254

Examples

expensive type SplitStr<T extends string> = T extends `${A}${B}` ? [A, ...SplitStr<B>] : B;

Checklist

My suggestion meets these guidelines:

• This wouldn't be a breaking change in existing TypeScript/JavaScript code
• This wouldn't change the runtime behavior of existing JavaScript code
• This could be implemented without emitting different JS based on the types of the expressions
• This isn't a runtime feature (e.g. library functionality, non-ECMAScript syntax with JavaScript output, etc.)
• This feature would agree with the rest of TypeScript's Design Goals.

[RyanCavanaugh]

If this were possible to implement tractably, we would have done it a really long time ago. The problem is that you can't just say "re-use this type", because a type can depend on any number of other types which are changing as the program is edited. If you write

expensive type T = U extends V ? Z : W;

then anything about U, V, Z, W, or any type they depend on in turn is a cache invalidator for T. You have to form a reverse dependency graph, then figure out for a given text edit, which types are possibly invalidated. You can't just say "tell me when U or V changes" since there's no old copy of U or V to compare with, and even if you did have them, determining if two type objects are "identical" for the purposes of cache validation for every type would be just as expensive as anything you'd potentially be saving on T.

I speak from experience because this is how TypeScript 0.8 worked, and it was incredibly, incredibly buggy, because any single bug here effectively corrupts the editing session because types get out of date. We literally rewrote the compiler from scratch instead of using a cached approach.

A plausible path forward would be to automatically compute when a type was somehow provably isolated from the rest of the world (maybe it's entirely contained within a sourcefile, or something) and somehow make that thing stick around, but we if we did that, we'd do it automatically for everything, not ask for a user opt-in.

[tjjfvi]

Thanks for the detailed response; I didn't know typescript 0.8 cached.

I recognize the issues/difficulties with a reverse dependency graph and/or things closer to incremental semantic analysis.

Instead, I was suggesting to memoize specific generic types based on the hash, to benefit from previous computations without restructuring the existing type instantiation process; i.e. given

type A = /* ... */;
expensive type X<T> = /* ... */;
type B = X<A>;

before instantiating the X<A>, since X is expensive, it uses the hashes of X and A, and looks in its memoization cache for that hash. If the hash is found, it uses the corresponding type; otherwise, it computes it as normal, and then stores it in its memoization cache. I believe this eliminates the need for a reverse dependency graph and for diffing types against their "old" values.

Complex recursive utility types would benefit greatly, as for each analysis you only need to traverse them once to hash it, rather than multiple times to reinstantiate it.

I suspect that a hashing approach could be easier to test, as existing unit tests can be utilized without individual modification by running them with different initial memoization caches.

If an approach like this could work, giving it to users behind a keyword would be great, but if it could be done automatically, that would be even better. 🙂

[harrysolovay]

Would it make a difference if the user manually specified cache invalidation with the utility type (similar to certain React hooks, eg. useMemo, useEffect, useCallback)?

Considering the use case of #41254, the Parse utility type would never be edited by its user. Only its sole type argument would be edited. What if I––as the library developer––could specify the conditions under which to invalidate?

node_modules/type-level-graphql-parser/index.d.ts

import {UnsafeParse} from "./internal";

export type Parse<Src extends string> = Memo<
  UnsafeParse<Src>,
  [Src] // <-- only recompute when `Src` changes
>

If a library developer wants to create a particularly-complex type––and they are certain that the computation is finite––they have no way to bypass the recursion limiter.

Yes, enabling such bypassing could be dangerous, as type library consumers might accidentally allow types to eat up resources. Maybe a new compiler option could require users to be deliberate about usage.

...
"compilerOptions": {
  ...
  "disableLimiting": ["type-level-graphql-parser"]
  ...
}
...

An Expensive utility would also make sense––allowing users to specify different breakpoints for the limiter (60 type IDs vs. 50, .... perhaps an amount of memory used).

The crux of this issue is that the recursion limiter prevents the creation of would-be-valuable type-safe experiences. I won't go on about the value of single-env interop of type systems of embedded languages... there are too many other experiences that would also benefit.

[tjjfvi]

I think it would be bad if editor session "corruption" could occur because of user error.

Additionally, I think a challenge with it would be identifying that old Parse is the same as new Parse; as RyanCavanaugh mentioned, "there's no old copy of U or V to compare with".

While I think discussing a change to the recursion limiter has merit, I do not think that is within the scope of this issue.

Slight aside

However, I do like the concept of the Memo, but mostly just as a way to abuse it to set variables:

type MyVar<NewVal = never, Set extends true | false = false> = Memo<
  true extends Set ? MyVar<NewVal, false> : NewVal,
  [Set],
>;

But that would just be evil.