How to implement a type-level max function over a union of literals, in TypeScript?

user_795876 0
Viewed 224

Given a union of number literals, e.g.:

type Values = 1 | 2 | 5

Is it possible to create a generic type-level function that extracts the maximum, i.e.:

type Max<T> = ???

type V = Max<Values>
//   V = 5
typescript types
2 Answers

The tersest illegal (see microsoft/TypeScript#26980) version of Max I can come up with (that uses variadic tuples slated to come out in TS4.0) is this:

type MaxIllegal<N extends number, T extends any[] = []> = {
    b: T['length'], r: MaxIllegal<N, [0, ...T]>
}[[N] extends [Partial<T>['length']] ? "b" : "r"];

type MaxValuesIllegal = MaxIllegal<Values>; // 5

That sort of illegal circularity works until it doesn't, which is one reason it's not supported. If you put in a value other than a non-negative integer, it recurses until there's a compiler error:

type OopsNegative = MaxIllegal<-1 | 3>; // error! Type instantiation is excessively deep and possibly infinite.

This can probably be worked around, but it gets worse: the recursion here bottoms out after only a few dozen levels, so you can't even use a number like 55 without getting an error:

type OopsTooBig = MaxIllegal<3 | 55 | 9>; // error! Type instantiation is excessively deep and possibly infinite.

One alternative is to programmatically generate a helper type like LEQ consisting of all the non-negative integers less than or equal to a given key, up to some max value you can choose... here I'm doing 100 or 99 or something:

// console.log("type LEQ={"+Array.from({length:100},(_,i)=>i+":"+Array.from({length: i+1},(_,j)=>j).join("|")).join(", ")+"}")
type LEQ = { 0: 0, 1: 0 | 1, 2: 0 | 1 | 2, 3: 0 | 1 | 2 | 3, 4: 0 | 1 | 2 | 3 | 4, 5: 0 | 1 | 2 | 3 | 4 | 5, 6: 0 | 1 | 2 | 3 | 4 | 5 | 6, 7: 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7, 8: 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8, 9: 0 | 1 | 2 | 3 | 4 | 5 ... SNIP!

Then you can write some code to pluck out the right values without using illegal circularity:

type Same<T, U, Y = T, N = never> = [T] extends [U] ? [U] extends [T] ? Y : N : N;
type ToLEQ<N extends number> = { [K in keyof LEQ]: [N] extends [Exclude<LEQ[K], K>] ? never : K }[keyof LEQ]
type Max<N extends number, U extends number = ToLEQ<N>> = { [K in keyof LEQ]: Same<U, LEQ[K], K> }[keyof LEQ]

It works for your example:

type MaxValues = Max<Values>; // 5

This works for 55 now because we're not overloading the stack:

type NotTooBigAnymore = Max<3 | 55 | 9> // 55

It still doesn't work when you give it an unexpected value like -1, but here it at least just gives you the max value it has instead of going completely off the deep end:

type OopsNegativeOkayIGuess = Max<-1 | 3> // 99

and as I said you can probably work around it by filtering the passed-in value before running Max on it. After all we have a big LEQ type sitting around:

type Max<N extends number, U extends number = ToLEQ<Extract<N, keyof LEQ>>> = { [K in keyof LEQ]: Same<U, LEQ[K], K> }[keyof LEQ]

And that gives you

type OopsNegativeOkayIGuess = Max<-1 | 3> // 3

which happens to be true (although Max<1 | 2.5> will be 1 which is false).

In any case, this is really pushing the compiler past anything I'd be comfortable recommending for a production code base. Really we should be pushing for microsoft/TypeScript#26382 to be implemented so that the compiler can just do math at the type level. So you might want to go there and give it a and possibly describe your (hopefully compelling) use case.

Okay, hope that helps; good luck!

Playground link to code

user_28872180

Oh boy. I created a monster that seems to work, but because of the limitations of circular types, it cannot be done as a single step.

type DropFirst<T extends TupleLike> = T extends readonly [any, ...infer U] ? U : [...T];

type Longer<T, U extends TupleLike> = U extends [] ? T : T extends [any, ...U] ? T : U;

type TupleLike<T = unknown> = readonly T[] | readonly [T];

type Head<T> = T extends [infer U, ...any[]] ? U : never;

type TupleOf<T, Length extends number, Queue extends any[] = []> = {
  done: Queue,
  next: TupleOf<T, Length, Prepend<T, Queue>>;
}[Yield<Queue, Length>]

type Yield<Queue extends any[], Length extends number> =
  Queue['length'] extends Length
    ? "done"
    : "next"

type Prepend<T, U extends any[]> =
  ((head: T, ...tail: U) => void) extends ((...all: infer V) => void)
    ? V
    : []

type FindLongestTuple<T extends readonly number[][], Accumulator extends number[] = []> = {
  done: Accumulator;
  next: FindLongestTuple<DropFirst<T>, Longer<Head<T>, Accumulator>>;
}[T extends [] ? 'done' : 'next'];

type GenerateTuples<T extends readonly number[]> = {
  [K in keyof T]: TupleOf<1, T[K] & number>
}

/**
 * Usage:
 */
type Input = [4, 5, 6, 1, 2];

type Step1 = GenerateTuples<Input>;
type Step2 = FindLongestTuple<Step1>
type Result = Step2['length']; // 6

Playground

I bet there is a simpler way to do that. ;-)

user_103250320
Related