TypeScript’s type system is known as “type gymnastics” because of its flexibility. People of all kinds have been working on the type system to achieve all kinds of incredible functions.

Recently, Uncle Xu Fei wrote a Chinese chess game, which can be said to be very curly. zhuanlan.zhihu.com/p/426966480

In fact, complex type operations are not traceless. This article tries to explore the potential of type systems from the perspective of metaprogramming, hoping to help you catch some ideas and context.

The foundation of metaprogramming is turing-complete subsystems. Is the TypeScript type system Turing-complete? The answer, of course, is yes.

The extends of the TypeScript type system? The ability to branch, the ability to allow recursion, and the ability to loop, together with the type dependence itself can form a sequential structure, meet the Turing completeness requirement.

TypeScript’s basic types include Number, Boolean, String, and Tuple, while its complex types include functions and objects. Although we are theoretically Turing-complete, we still need some basic operational support.

Yuan set of operations

The core of tuple operations is… Calculation and infer type,… Tuple expansion can be used to construct new tuples, and infer allows us to match and retrieve parts from a tuple.


type concat<A extends any[], B extends any[]> = [...A, ...B];

type shift<Tuple extends any[]> = Tuple extends [infer fist, ... infer rest] ? rest : void;
type unshift<Tuple extends any[], Type> = [Type, ...Tuple];

type pop<Tuple> = Tuple extends [... infer rest, infer last] ? rest : void;
type push<Tuple extends any[], Type> = [...Tuple, Type];
Copy the code

Of course, in fact, these methods do not exist meaning, in practice, we do not need such abstraction, directly write the expression on the right. This is just a simple warm-up exercise to familiarize yourself with the characteristics of tuples.

. Infer is almost equivalent to addition and subtraction in tuple operations and is the basis of all subsequent complex operations.

recursive

Recursion is the cornerstone of all complex type operations. In the absence of subtraction and comparison, we can only compare using the length and extends of tuples. The following code forms a fixed-length list:


type List<Type, n extends number, result extends any[] = []> = 
    result['length'] extends n ? result : List<Type, n, [...result, Type]>;

Copy the code

For a more complicated example, the name tells you what it does:

type slice<Tuple extends any[], begin extends number, end extends number, before extends any[] = [], result extends any[] = []> = 
    before['length'] extends begin ? 
        [...before, ...result]['length'] extends end ? 
            result :
            Tuple extends [...before, ...result, infer first, ...infer rest] ? 
                slice<Tuple, begin, end, before, [...result, first]> :
                void :
        Tuple extends [...before, infer first, ...infer rest] ?
            slice<Tuple, begin, end, [...before, first], result> :
            void ;

Copy the code

String related operations

String types, like tuples, are first-class citizens of the type system. Using template matching, we can intercept various parts of a string. Here are a few examples.


type numberToString<T extends number> = `${T}`;

type stringToChars<T extends string> = T extends `${infer char}${infer rest}` ? [char, ...stringToChars<rest>] : [];

type join<T extends (string|number|boolean|bigint|undefined|null)[], joiner extends string> = 
    T['length'] extends 1 ? `${T[0]}` :
    T extends [infer first, ...infer rest] ? `${first}${joiner}${join<rest, joiner>}` :
    ' '
Copy the code

Code style.

Because there are no statements, you can only use extends? Structure, it becomes extremely difficult to write clean code, and HERE I recommend an indentation style that I prefer.

Rule 1: Serial structure

Try to make nested extends? The: occurs in the false branch. This way, we can have a question mark corresponding to a result. All extends does not indent.

type decimalDigitToNumber<n extends string> =
    n extends '1' ? 1 :
    n extends '2' ? 2 :
    n extends '3' ? 3 :
    n extends '4' ? 4 :
    n extends '5' ? 5 :
    n extends '6' ? 5 :
    n extends '7' ? 7 :
    n extends '8' ? 8 :
    n extends '9' ? 9 :
    n extends '0' ? 0 :
        never
Copy the code

Rule 2: Merge conditions

When the road? : appears in the true branch and can merge lines if necessary, should always keep the line? And: equal in number and ending with a colon, as:

type and<v1 extends boolean, v2 extends boolean> =
    v1 extends true ? v2 extends true ? true : false :
        false
Copy the code

Rule 3: Nested structures

When the road? : occurs in the True branch and can break the line after the question mark and indent the next line

type or<v1 extends boolean, v2 extends boolean> =
    v1 extends false ? 
        v2 extends true ? true : false :
        true
Copy the code

Number operation

TypeScript supports constants, but they are not inherently friendly. They do almost nothing in the type system. There is no addition or subtraction of their own, but we can convert numbers into arrays to do some simple operations:

type add<x extends number, y extends number> = [...List<any, x>, ... List<any, y>]['length'];

type minus<x extends number, y extends number> = List<any, x> extends [...rest, ...List<any, y>] ? rest['length'] : void;

type multiple<x extends number, y extends number, result extends any[] = [], i extends any[] = 
    []> = i extends y ? result['length'] : multiple<x, y, [...result, List<x>], [...i, any>;Copy the code

The tuple [‘length’] can be used to simulate the operations on number. If a number is not large, it must be converted to a string by numberToString. The front article zhuanlan.zhihu.com/p/423175613 can refer to byte

Use binary to represent integers

A more scientific approach is to use binary numbers to represent integers, which can be used for larger calculations


type fromBinary<bin extends (0 | 1)[], i extends any[] = [], v extends any[] = [0] , r extends any[] = []> = 
    i['length'] extends bin['length']? r['length'] :
    fromBinary<bin, [...i, 0], [...v, ...v], bin[i['length']] extends 0 ? r : [...r, ...v]>

Copy the code
type not<bit extends (0|1)> = bit extends 0 ? 1 : 0; 
type binaryAdd<bin1 extends (0 | 1)[], bin2 extends (0 | 1)[],
i extends any[] = [], extra extends (0 | 1) = 0, r extends (0|1)[] = []> =
	i['length'] extends bin1['length']? r : bin1[i['length']] extends 1 ?
			bin2[i['length']] extends 1 ?
				[extra, ...binaryAdd<bin1, bin2, [...i, 0].1>] :
				[not<extra>, ...binaryAdd<bin1, bin2, [...i, 0], extra>] :
			bin2[i['length']] extends 1 ?
				[not<extra>, ...binaryAdd<bin1, bin2, [...i, 0], extra>] :
				[extra, ...binaryAdd<bin1, bin2, [...i, 0].0>]

let g:fromBinary<binaryAdd<[...count<10.0>, 1], [...count<9.0>, 1.0] > >;Copy the code

A profound

All right, the above examples are relatively simple and seem to lack some of the flavor of metaprogramming, so let’s take a challenge: write a TicTacToe AI.


type not<b extends boolean> = b extends true ? false : true;

type Pattern = [
  (' '|'⭘'|'✖), (' '|'⭘'|'✖), (' '|'⭘'|'✖),
  (' '|'⭘'|'✖), (' '|'⭘'|'✖), (' '|'⭘'|'✖),
  (' '|'⭘'|'✖), (' '|'⭘'|'✖), (' '|'⭘'|'✖)];

type toggleColor<color extends ('⭘'|'✖)> = color extends '⭘' ? '✖ : '⭘';



type checkline<v1, v2 , v3, color extends ('⭘'|'✖)> = 
    v1 extends color ? v2 extends color ? v3 extends color ? true : false : false : false;


type move<pattern extends Pattern, pos extends number, color extends ('⭘'|'✖), _result extends (' '|'⭘'|'✖)[] = []> =
    _result['length'] extends pattern['length']? _result : _result['length'] extends pos ? move<pattern, pos, color, [..._result, color]> :
        move<pattern, pos, color, [..._result, pattern[_result['length']]] >;type isWinner<pattern extends Pattern, color extends ('⭘'|'✖)> = 
    checkline<pattern[0], pattern[1], pattern[2], color> extends true ? true :
    checkline<pattern[3], pattern[4], pattern[5], color> extends true ? true :
    checkline<pattern[6], pattern[7], pattern[8], color> extends true ? true :
    checkline<pattern[0], pattern[3], pattern[6], color> extends true ? true :
    checkline<pattern[1], pattern[4], pattern[7], color> extends true ? true :
    checkline<pattern[2], pattern[5], pattern[8], color> extends true ? true :
    checkline<pattern[0], pattern[4], pattern[8], color> extends true ? true :
    checkline<pattern[2], pattern[4], pattern[6], color> extends true ? true :
        false;

type emptyPoints<pattern extends Pattern, _startPoint extends any[] = [], _result extends any[] = []> =
    _startPoint['length'] extends pattern['length']? _result : pattern[_startPoint['length']] extends ' ' ? emptyPoints<pattern, [..._startPoint, any], [..._result, _startPoint['length']]> : 
        emptyPoints<pattern, [..._startPoint, any], [..._result]>;

type canWin<pattern extends Pattern, color extends ('⭘'|'✖), _points extends any[] = emptyPoints<pattern>, _unchecked extends any[] = emptyPoints<pattern>, canDraw extends boolean = false> = 
    isWinner<pattern, toggleColor<color>> extends true ? "loose" :
    _points['length'] extends 0 ? "draw" :
    _unchecked['length'] extends 0 ? canDraw extends true ? "draw" : "loose" :
    _unchecked extends [infer first, ...infer rest] ? 
        canWin<move<pattern, first, color>, toggleColor<color>> extends "loose" ? "win" : 
        canWin<move<pattern, first, color>, toggleColor<color>> extends "draw" ? canWin<pattern, color, _points, rest, true> :
        canWin<move<pattern, first, color>, toggleColor<color>> extends "win" ? canWin<pattern, color, _points, rest, canDraw> : 
        `error1:${canWin<move<pattern, first, color>, toggleColor<color>>}` :
    "error2";


type computerMove<pattern extends Pattern, color extends ('⭘'|'✖), _points extends any[] = emptyPoints<pattern>, _unchecked extends any[] = emptyPoints<pattern>, canDraw extends boolean = false, bestPos = -1> =
    checkOpenings<pattern, color> extends [true, infer pos] ? pos :
    _unchecked['length'] extends 0 ? bestPos extends -1 ? _points[0] : bestPos :
    _unchecked extends [infer first, ...infer rest] ? 
        canWin<move<pattern, first, color>, toggleColor<color>> extends "loose" ? first : 
        canWin<move<pattern, first, color>, toggleColor<color>> extends "draw" ? computerMove<pattern, color, _points, rest, true, first> :
        canWin<move<pattern, first, color>, toggleColor<color>> extends "win" ? computerMove<pattern, color, _points, rest, canDraw, bestPos> : 
        `error1:${canWin<move<pattern, first, color>, toggleColor<color>>}` :
    "error2";

type checkOpenings<pattern extends Pattern, color extends ('⭘'|'✖)> =
  pattern extends [' '.' '.' '.' '.' '.' '.' '.' '.' ']? [true.4] : [false.never]

class Game<pattern extends Pattern.color extends(' ⭘ '|' ✖ ') >{

  board: {line1: `${pattern[0]}${pattern[1]}${pattern[2]}`
    line2: `${pattern[3]}${pattern[4]}${pattern[5]}`
    line3: `${pattern[6]}${pattern[7]}${pattern[8]}`
    canWin:canWin<pattern, color>
    emptyPoints:emptyPoints<pattern>
    color:color
    computer:computerMove<pattern, color>
  },
  
  move<pos extends (0|1|2|3|4|5|6|7|8)>(p:pos) {
    return new Game<move<pattern, pos, color>, toggleColor<color>>()
  }

}

let c:Game<[' '.' '.' '.' '.' '.' '.' '.' '.' '].'⭘'>;
c.move(4).move(1).board


Copy the code

www.typescriptlang.org/play?ts=4.5…

Now, if you’ve seen this, you’ve probably gained some familiarity with TypeScript type metaprogramming, so you can use it in your daily work.