Performance and usablity of .exhaustive

[m-rutter]

So I noticed that exhaustive has some pretty punishing compile times for any moderately complicated types it needs to match on. I've even found it hitting the "union type that is too complex to represent" limit regularly. I don't have any benchmarks. but I think you are aware of the problem as you mention it your docs. I'm not sure if exhaustive is actually usable except for the most simple cases.

If I had to guess it is because if you have a type like this:

type A = {type: "a", mode: "b" | "c" | "d"} |  {type: "b", mode: "f" | "g"}

You have to generate a union that looks like this?:

  | {type: "a", mode: "b"} 
  | {type: "a", mode: "c"} 
  | {type: "a", mode: "d"} 
  | {type: "b", mode: "f"} 
  | {type: "b", mode: "g"}   

So for example this fairly simple to understand union will completely break exhaustive:

import { Property } from "csstype";

declare const a:
  | { type: "textWithColor"; color: Property.Color }
  | { type: "textWithColorAndBackground"; color: Property.Color; backgroundColor: Property.Color };

match2(a).exhaustive(); // "union type that is too complex to represent"

playground link - takes serveral minutes on my machine to hit the limit

The reason being is that Property.Color is a string union with hundreds of variants. (this is the same kind of example that eventually lead the typescript team to abandon by default inference of template string literals types in 4.2 - microsoft/TypeScript#42416)

So this makes exhaustive pretty much unusable if you have a type with properties that are unions of any moderate size. Either because you will hit the union limit or because the compile times are too extreme to make it practical to use.

This is all fair, and I don't think I see a way around the issue and keeping the full pattern matching features of the lib.

That said, in 80-90% of cases all I want to match on is the discriminator of a union in order to narrow the types. For example this works in a simple switch and I still get some kind of exhaustiveness checks:

declare const a:
  | { type: "textWithColor"; color: Property.Color }
  | { type: "textWithColorAndBackground"; color: Property.Color; backgroundColor: Property.Color };
  
  
 const aToDescription (a: typeof a): string  => { 
   switch(a.type) {
    case "textWithColor":
       return a.color
     case "textWithColorAndBackground":
       return `${a.color} with a background of ${a.backgroundColor}`
   }
}

I'm wondering if you can offer something that still allows for some kind of exhaustiveness checks on discriminators in order to narrow types down, but compromises on pattern matching features elsewhere for the sake of compile time performance. In the back of my mind I'm thinking about this lib https://paarthenon.github.io/variant/ (mentioned in my my previous issue) because this library can do exhaustiveness checks because it only concerns itself with the discriminators of unions.

[m-rutter]

I do like the library - the pattern matching outside of exhaustive seems pretty cool. I quite like select.

[gvergnaud]

Hey!

If I had to guess it is because if you have a type like this:
type A = {type: "a", mode: "b" | "c" | "d"} | {type: "b", variant: "f" | "g"}
You have to generate a union that looks like this?:
| {type: "a", mode: "b"}
| {type: "a", mode: "c"}
| {type: "a", mode: "d"}
| {type: "b", mode: "f"}
| {type: "b", mode: "g"}

That's exactly right.

I'm wondering if you can offer something that still allows for some kind of exhaustiveness checks on discriminators in order to narrow types down, but compromises on pattern matching features elsewhere for the sake of compile time performance. In the back of my mind I'm thinking about this lib https://paarthenon.github.io/variant/ (mentioned in my my previous issue) because this library can do exhaustiveness checks because it only concerns itself with the discriminators of unions.

It looks like the constrains are a bit different between ts-pattern and variant (a lib I didn't know before to be honest). If I'm not mistaken, variant wants to control the way you create your union type, which means that you always end up with a flat union of objects. ts-pattern however wants to work with any data-structure and support recursive patterns, that's why it's computing all possible cases of the input type upfront.

That said, I'm aware the current state of exhaustive matching isn't ideal and I agree on the fact that we should find a better balance between 1. letting you exclude cases based on a deep patterns, matching several unions at once and 2. support input containing huge union types, like Property.Color.

Here are the possible options I can think of:

1. When traversing the input type, if we encounter a union of objects, stop the recursion here and don't try to find unions contained in each case.

The down side is that cases like:

type Input = { kind: 'none' } | { kind: 'some', value: number | string }

match<Input>(input)
  .exhaustive()
  .with({ kind: 'none' }, () => out)
  .with({ kind: 'some', value: __.number }, () => out)
  .with({ kind: 'some', value: __.string }, () => out)
  .run()

wouldn't work anymore.

2. have some kind of heuristic to avoid including unions that exceed n elements (but then what n should be?). This n should probably be smaller and smaller for every level of nesting... This would probably be kind of hard to implement, < and > are pretty expensive operations at the type level.

3. Instead of computing all cases upfront when calling .exhaustive(), compute the remaining cases on every .with() by traversing the pattern instead of the input type? I don't know if this would really be feasible, be we can at least try.

Do you see any other solution I might be missing?

[m-rutter]

It looks like the constrains are a bit different between ts-pattern and variant (a lib I didn't know before to be honest). If I'm not mistaken, variant wants to control the way you create your union type, which means that you always end up with a flat union of objects. ts-pattern however wants to work with any data-structure and support recursive patterns, that's why it's computing all possible cases of the input type upfront.

Yes, I've realised now that the two libraries are similar in terms of the problem they are trying to solve and their means of solving it, but are quite different and maybe even complement each other to a certain extent.

The variants docs linger on their constructors for creating union types upfront, but actually the most valuable thing in the library is probably the match and newer matcher functions, which like ts-pattern's match can work with existing data structure. variant's match is trying to provide what kinda should be a language feature in user land - expressions based switch statement for narrowing discriminated unions - to partially mimic the match on ADTs in languages like rust and ocaml (obviously without the full pattern matching features of both). ts-pattern is trying to provide full pattern matching capabilities against complete data structures more closely mimicking the tc39 proposal - which I imagine will cause similar headaches for the typescript team if it were ever standarised.

Do you see any other solution I might be missing?

I'm not sure if I have another option to add, but I think it might be wise to make the disclaimer around .exhaustive stronger, because I can imagine people using it and then dismissing your library because of the poor compiler performance or hitting union limits. I can imagine people wanting to use ts-pattern to eliminate existing boilerplate with switch statements and wanting the exhaustiveness checks of switch. However, from what I can tell the compile time issues are limited to just .exhaustive and not your entire lib.

[m-rutter]

Another options:

match(a)exhaustive("type") // exhaustively match on this property only?

[m-rutter]

match(a)exhaustive("type", "mode") // exhaustively match on these two properties?

[m-rutter]

The idea is essentially you give the user control over how exhaustive the pattern matching checks are by forcing them to opt into the relevant fields.

Downside is you probably cannot allow matching on properties outside of that list.

[gvergnaud]

Interesting idea, but how would this look like for non-object patterns (tuples for instance), and what if you want to have exhaustive checking on properties at different level of nesting?

let's say you have an input like this for instance:

type Option<T> = { kind: "none" } | { kind: "some", value: T };
type Input = [Option<{ type: 'a' } | { type: 'b' }>, 'c' | 'd']

match<Input>(input)
  .exhaustive(?)

this can sound a bit theoretical, but this is the kind of usecase this lib tries to handle well

[gvergnaud]

Btw I've started thinking about option 3, and I think it might be possible to avoid distributing all the possible cases contained in the input upfront by writing a DeepExclude<A, B> type that would only distribute what is actually necessary:

type Input =
   | { type: "textWithColor"; color: Property.Color }
   | { type: "textWithColorAndBackground"; color: Property.Color; backgroundColor: Property.Color };

type x1 = DeepExclude<Input, { type: "textWithColor" }>
// => { type: "textWithColorAndBackground"; color: Property.Color; backgroundColor: Property.Color };

type x2 = DeepExclude<Input, { type: "textWithColor", color: "grey" }>
// => | { type: "textWithColorAndBackground"; color: Property.Color; backgroundColor: Property.Color }
//    | { type: "textWithColor", color: "pink" }
//    | { type: "textWithColor", color: "purple" }
//    | { type: "textWithColor", color: "red" }
//    | ... all possible colors, because we need to distribute at this point, but not that the `type: "textWithColorAndBackground"` case hasn't been distributed

The first argument is the input, and the second argument is the type of the pattern given to .with

I'll try to do that this weekend, but it will probably be hard, and the perf might not be good enough. Also it took me ~ 2 months to find a way to implement the current version of the exhaustive matching, so it might take a while :)

[m-rutter]

Oh that is interesting. If that is possible, then it at least makes it less likely that the match will hit or go near the union limit. I guess it still means that if a user does match on color say then the union might very well grow to be too large, but at least this gives the user a way of avoiding problematic matches.

[gvergnaud]

👋 I think I found a pretty good implementation of the DeepExclude<A, B> I described above that doesn't distribute every unions upfront. It seems to work pretty well and performances seem acceptable. See PR #17

I just released the [email protected] pre-release with the updated types for exhaustive(), do you mind installing it on your project and telling me if it solves the performance problem you were facing or at least if it's better?

You can also play with it in this sandbox: https://codesandbox.io/s/autumn-https-41um5?file=/src/index.ts

[m-rutter]

I'll be sure to check out the pre-release!

[m-rutter]

Just gave it a quick whirl. It feels great - performance is significantly better. I threw a few large and complex types at it, and I didn't run into any issues. The error messages you are able to get on run are wonderful. I think you managed to do it - you have made the union explosion an opt in that a user can mitigate by say nesting a match within a match.

Having a usable exhaustive makes me much more likely to start using this library in lots of places, and get buy in by my team.

[m-rutter]

I suggest you document why something like this is problematic:

const output = match<Input>(input)
  .exhaustive() // it works and it's fast!
  .with({ type: "text", color: "grey" }, () => `<p>some text</p>`)
  .with({ type: "button", color: "grey" }, () => `<button>click</button>`)
  .with({ type: "button", bgColor: "grey" }, () => `<button>click</button>`)
  .run();

// Type instantiation is excessively deep and possibly infinite.ts(2589)

[m-rutter]

possible mitigation example:

const output = match<Input>(input)
  .exhaustive() // it works and it's fast!
  .with({ type: "text" }, () => `<p>some text</p>`)
  .with({ type: "button"}, (input) => 
    match(input)
      .with({color: "grey"}, () => "<button> grey button click</button>" )
      .otherwise(() => "<button>click</button>" )
  )
  .run();

You are exhaustive on the things you care about, and handle more narrow patterns within a separate match on the narrowed type which itself may or may not be exhaustive

[gvergnaud]

Good call, I'll add some documentation about this once I ship the new version

[gvergnaud]

Closing this issue as the 2.1.3 release has been shipped