Filtering the types of a tuple at compile time in typescript
Tags: typescript, tuples, metaprogramming
Published: 2020-04-18 17:26:56

I needed to remove all of the boolean types from a tuple for a parser generator I'm writing. The code turned out to be way crazier than I would have liked:

```typescript
type NumberMap = {
  0: 1
  1: 2
  2: 3
  3: 4
  4: 5
  5: 6
  6: 7
  7: 8
  8: 9
  9: 10
  10: 11
  11: 12
  // up to twelve supported
  12: 12
}

// prepending is relatively easy
type Prepend<H, T extends any[]> = ((h: H, ...t: T) => void) extends (
  ...l: infer L
) => void
  ? L
  : never

// appending is possible but expensive and hard, must
// build lists in reverse and reverse the result when done
type Reverse<L extends any[], R extends any[] = []> = {
  0: R
  1: ((...l: L) => void) extends (h: infer H, ...t: infer T) => void
    ? Reverse<T, Prepend<H, R>>
    : never
}[L extends [any, ...any[]] ? 1 : 0]

type Equals<I extends number, L extends number> = I extends L ? 1 : 0

type FilterBoolean<T, R extends any[]> = T extends boolean ? R : Prepend<T, R>

type FilterBooleansNext<
  I extends keyof NumberMap,
  T extends any[],
  R extends any[]
> = T extends []
  ? R
  : {
      0: FilterBooleansNext<NumberMap[I], T, FilterBoolean<T[I], R>>
      1: R
    }[Equals<I, T['length']>]

// append is hard/expensive, so keep prepending and reverse the result
export type FilterBooleans<T extends any[]> = Reverse<
  FilterBooleansNext<0, T, []>
>
```

Oh boy. Going through it bit by bit:

```typescript
type NumberMap = {
  0: 1
  1: 2
  2: 3
  3: 4
  4: 5
  5: 6
  6: 7
  7: 8
  8: 9
  9: 10
  10: 11
  11: 12
  // up to twelve supported
  12: 12
}
```

Can't do `I + 1` in a typescript type. Nope. So instead there is this map. The last map item has to point to itself or the code won't compile, because even when no tuples with 12 items are used, the code will still instantiate up the limit and then complain about item 13 not existing.

```typescript
type Prepend<H, T extends any[]> = ((h: H, ...t: T) => void) extends (
  ...l: infer L
) => void
  ? L
  : never
```

This prepends a type to the head of a list. It's a bit disappointing that it's necessary to use a function just to infer the prepended type but that's how typescript is. This is used to build the "result type". You're probably thinking, isn't it better to append types gradually when building the result? Well yeah, but writing an append type turns out to be far more complicated and much more expensive, it involves reversing the list twice. No way, this metaprogram already uses up a ridiculous amount of CPU.

```typescript
type Equals<I extends number, L extends number> = I extends L ? 1 : 0

type FilterBoolean<T, R extends any[]> = T extends boolean ? R : Prepend<T, R>

type FilterBooleansNext<
  I extends keyof NumberMap,
  T extends any[],
  R extends any[]
> = T extends []
  ? R
  : {
      0: FilterBooleansNext<NumberMap[I], T, FilterBoolean<T[I], R>>
      1: R
    }[Equals<I, T['length']>]

export type FilterBooleans<T extends any[]> = Reverse<
  FilterBooleansNext<0, T, []>
>
```

Oh dear, why the object and why the `Equals`? Why not just `I extends T['length'] ? ... : ...`. Well that introduces a recursive reference from `FilterBooleansNext` back to itself that typescript just won't tolerate. But it will tolerate this hack. Now the final bit:

```typescript
export type FilterBooleans<T extends any[]> = Reverse<
  FilterBooleansNext<0, T, []>
>
```

Remember I said appending was too hard, so we keep pretending types to the result and reverse it at the end.

The result of all this? While I'm editing my project with this type one of my CPU cores is constantly at 100%. The compile time of my program doubled from 3 seconds to 6. I threw it away and my API suffers for it because now the user has to manually specify types when they shouldn't have to.