Chess notation: TypeScript template literals: TS2590: Expression produces a union type that is too complex to represent

I'm trying to represent Algebraic Chess Notation with TypeScript Template Literals.

Types I used:

export type ChessPiece = 'P' | 'K' | 'Q' | 'R' | 'B' | 'N';
export type ChessX = 'a' | 'b' | 'c' | 'd' | 'e' | 'f' | 'g' | 'h';
export type ChessY = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8;

export type AlgebraicMoveNotationDisambiguate = '' | ChessX | ChessY | `${ChessX}${ChessY}`;
export type AlgebraicMoveNotationBase = `${ChessPiece | ChessX}${AlgebraicMoveNotationDisambiguate}${'x' | ''}${ChessX}${ChessY}`;
export type AlgebraicMoveNotationPromote = `${ChessX}8${ChessPiece}`;
export type AlgebraicMoveNotationDecoration = `${'' | '+' | '#'}`;
export type AlgebraicMoveNotation = 'O-O' | 'O-O-O' | `${AlgebraicMoveNotationBase|AlgebraicMoveNotationPromote}${AlgebraicMoveNotationDecoration}`;

This gives an error on line 6 (AlgebraicMoveNotationBase):

TS2590: Expression produces a union type that is too complex to represent.

I understand this is quite a complex expression and calculating all possible values all the time might be not feasible (I did the math, there's about 3.5 billion combinations in the final type AlgebraicMoveNotation).

My question is - is there a way to configure TS to only evaluate assigned values without trying to understand all possible types, f.e.:

// Example 1 =======

const someMove: AlgebraicMoveNotation = 'exd5'; // <- Checks provided literal is valid

// Example 2 =======

const validateMoves(moves: AlgebraicMoveNotation[]): void {
    // ...
}

validateMoves([ // <- Checks provided literals in array are valid
    'Nf6+',
    'a8Q',
    'Qexe1#',
]);

I tried to check similar errors but didn't find anything related.

Simpler example for easier reproduction:

export type ChessPiece = 'P' | 'K' | 'Q' | 'R' | 'B' | 'N';
export type ChessX = 'a' | 'b' | 'c' | 'd' | 'e' | 'f' | 'g' | 'h';
export type ChessY = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8;

export type AlgebraicMoveNotationDisambiguate = '' | ChessX | ChessY | `${ChessX}${ChessY}`;
export type AlgebraicMoveNotationCapture = '' | 'x';
export type AlgebraicMoveNotationBase = `${ChessPiece | ChessX}${AlgebraicMoveNotationDisambiguate}${AlgebraicMoveNotationCapture}${ChessX}${ChessY}`;

Solution

Instead of going over the specific type function for chess moves, which is already written in the other answer, I'll talk about the general class of problem.

TypeScript is unable to represent union types with more than approximately 100,000 members. That's plenty for many purposes, but when template literal types were introduced in microsoft/TypeScript#40336 it made it possible to easily generate huge unions by concatenating unions-of-string-literal types together. If you a type M which is a union of 𝒎 string literal types, and a type N which is a union of 𝒏 string literal types, then the template literal type `${M}${N}` will be a union of 𝒎×𝒏 string literal types. This very quickly gets out of hand as you repeat concatenations: concatenate 𝒌 copies of N together and you'll get a union of 𝒏^𝒌 string literals. Even for modestly small 𝒏 and 𝒌 you will quickly exceed the language's capacity to represent unions.

Like most such limits of the language, this is not configurable. Generally speaking they are considered implementation details of the compiler that are not meant to be tweaked by users. (See microsoft/TypeScript#45025 at the end of the description, for example.) Large unions are taxing on compiler resources as it is, and increasing the limit would almost certainly just make things worse, so you could expect the compiler to become unusably slow or crash instead of issuing a warning. So this is not an option.

Instead you will generally need a different approach. Generating every possible valid string literal type in a giant union isn't needed if all you want to do is check individual string literal types for validity. Checking membership in a set might be conceptually simple, but often it's a lot easier to implement a predicate instead. (If I ask you if "abc" has three letters, you do not want to first generate the set of all three letter words.)

This means you can change from

type ValidString = ⋯;

to a generic type like

type ValidateString<T extends string> = ⋯;

where T extends ValidateString<T> if and only if T extends ValidString would have been true. Then Validate<T> string acts like a constraint on a type T. To avoid having to write out the type argument yourself, you can make a helper function to infer it.

The ideal helper function would look like

const validateString = 
  <T extends ValidateString<T>>(t: T) => t;

but this will usually set off circularity detectors. You can rephrase it to something like

const validateString = 
  <T extends string>(t: T & ValidateString<T>) => t;

or even

const validateString = <T extends string>(
  t: T extends ValidateString<T> ? T : ValidateString<T>
) => t;

which will allow the compiler to infer T from the value of t and then check it with ValidateString<T>.

And so, instead of writing

const str: ValidString = "⋯";  // need huge union

you would write

const str = validateString("⋯"); // only check the passed-in string

which isn't very different.

As for the general approach to converting from a big union to a constraint, you can use conditional type inference to parse your candidate string. If you had something like

type ValidString = `${M}${N}${O}`

you might change it to

type ValidateString<T extends string> =
  T extends `${M}${infer _NO}` ?
  _NO extends `${N}${infer __O}` ?
  __O extends `${O}` ? T :
  never : never : never;

That splits the string into chunks, first seeing if it is M followed by the rest of the string which we call _NO... then seeing if _NO is N followed by the rest of the string which we call __O, and finally seeing if __O is O after all. Each of these steps only deals with unions the sizes of M, N, and O without multiplying them together.

There are alternatives to never which can make error messages more palatable, but they get more difficult to write. The goal is to make it so that ValidateString<T> produces the "closest" valid string to T, for some heuristic idea of "close". That way when you call validateString("inkorrekt") the compiler will give you an error message of the form '"inkorrekt" is not assignable to "correct"' which will hopefully prompt you to fix it. I'm not going to go into how to do it for the chess example or for the general problem... the tricky part is that finding the failed partial matches can create unions, and you don't want big unions in your output or you run the risk of hitting the limits again.

Playground link to code