TypeScriptの正規表現にマシな型をつける

# 問題
TypeScript の正規表現は RegExp 型を持ち、マッチ結果は配列や、関数に関する可変個の引数として渡される。この時、正規表現に含まれるキャプチャーの個数や種類（必須か、オプションか）の情報は、型に表れない。

つまり、 TypeScript では --strictNullChecks が有効でも以下のコードの誤りを検出できないし：

```typescript
let m = str.match(/(a)(b)?/);
if (m) {
    let a: string = m[1];
    let b: string = m[2]; // 本当は string | undefined
}
```

次のコードにおいて関数の引数の型を推論することもできない：

```typescript
let str = "x\\yz";
let t = str.replace(/\\(.)/, (m, s) => s.toUpperCase());
// s は any 型なので、仮に s.toUpper() と書いてもエラーにならない
```

TypeScript は静的型がウリの言語なので、もうちょっとやりようはあるのではないか。

# 目標：型付き正規表現

これらの問題を解決するために、キャプチャーの型の情報を埋め込んだ型 `TypedRegExp<captures>` を作りたい。キャプチャーの型とは、具体的には

* `string`: 通常のキャプチャー
* `string | undefined`: 後ろに `?` や `*` がついたもの、あるいは `|` の一方に含まれるもの
* `undefined`: 否定先読み `(?! .. )` に含まれるキャプチャー

のいずれかである。例えば、 `/(a)(b)?/` という正規表現のキャプチャーの型は、順に `string`, `string | undefined` となる。

`captures` が `string`, `string | undefined` というリストの場合（最初の例）、 `r: TypedRegExp<captures>` に対し `s.match(r)` の型が `[string, string, string | undefined] & {index?:number;input?:string}` となるようにしたい[^1]。

[^1]: `index` と `input` プロパティーは `g` フラグが指定されていない場合に設定される。正規表現のフラグも型で管理すべき対象な気がするが、今回は扱わない。

# 準備：型レベルリスト

キャプチャーのリストを扱うには、型レベルリストが必要となる。そこで、適当に型レベルリストをでっち上げる。[TypeScript の型システムはチューリング完全](https://github.com/Microsoft/TypeScript/issues/14833)らしいので、このくらいは造作もない[^2]。

[^2]: 「チューリング完全だから〜」という推論はもちろん正しくない。TypeScript の型システムが強力だと言いたいだけである。

```typescript
type SNil = {
    "tag": "Nil";
};
type SCons<a, b extends SList> = {
    "tag": "Cons";
    "head": a;
    "tail": b;
};
type SList = SNil | {
    "tag": "Cons";
    "head": any;
    "tail": SList;
};
// type SList = SNil | SCons<any, SList>; とは書けないが、上のようには書ける

// リストの連結
type Concat<a extends SList, b extends SList> = {
    "Nil": b;
    "Cons": SCons<a["head"], Concat<a["tail"], b>>;
}[a["tag"]];

// リストの要素を全て undefined で置き換える
type FillUndefined<a extends SList> = {
    "Nil": SNil;
    "Cons": SCons<undefined, FillUndefined<a["tail"]>>;
}[a["tag"]];

// リストの要素に対して | undefined を行う
type MaybeUndefined<a extends SList> = {
    "Nil": SNil;
    "Cons": SCons<a["head"] | undefined, MaybeUndefined<a["tail"]>>;
}[a["tag"]];
```

型レベルリストが期待通りに動作することを確かめるには、試しにコンパイルエラーを起こしてみれば良い：

```typescript
// error TS2322: Type '0' is not assignable to type 'SCons<"a", SCons<"b", SCons<"c", SCons<"d", SNil>>>>'.
let x : Concat<SCons<"a", SCons<"b", SNil>>, SCons<"c", SCons<"d", SNil>>> = 0; 

// error TS2322: Type '0' is not assignable to type 'SCons<undefined, SCons<undefined, SCons<undefined, SNil>>>'.
let y : FillUndefined<SCons<string, SCons<number, SCons<null, SNil>>>> = 0;

// error TS2322: Type '0' is not assignable to type 'SCons<string | undefined, SCons<number | undefined, SCons<null | undefined, SNil>>>'.
let z : MaybeUndefined<SCons<string, SCons<number, SCons<null, SNil>>>> = 0;
```

## 型レベルリストから、タプル型および関数型への変換

`String.match` メソッドの型を記述するには、型レベルリストをタプル型に変換する必要がある。残念ながら、あまり綺麗な書き方は思いつかなかった：

```typescript
type ToTuple5<a0, a1, a2, a3, a4, a extends SList> = {
    "Nil": [a0, a1, a2, a3, a4];
    "Cons": [a0, a1, a2, a3, a4, a["head"]]; // a["tail"] is dropped...
}[a["tag"]];
type ToTuple4<a0, a1, a2, a3, a extends SList> = {
    "Nil": [a0, a1, a2, a3];
    "Cons": ToTuple5<a0, a1, a2, a3, a["head"], a["tail"]>;
}[a["tag"]];
type ToTuple3<a0, a1, a2, a extends SList> = {
    "Nil": [a0, a1, a2];
    "Cons": ToTuple4<a0, a1, a2, a["head"], a["tail"]>;
}[a["tag"]];
type ToTuple2<a0, a1, a extends SList> = {
    "Nil": [a0, a1];
    "Cons": ToTuple3<a0, a1, a["head"], a["tail"]>;
}[a["tag"]];
type ToTuple1<a0, a extends SList> = {
    "Nil": [a0];
    "Cons": ToTuple2<a0, a["head"], a["tail"]>;
}[a["tag"]];
type ToTuple<a extends SList> = {
    "Nil": [];
    "Cons": ToTuple1<a["head"], a["tail"]>;
}[a["tag"]];
```

このようなコードの羅列を見ていると、C++が10年以上前に通った道が思い起こされる。

追憶は置いておいて、この `ToTuple` 型を使うと、 `RegExp.exec` と `String.match` の結果の型はそれぞれ次のように書ける：

```typescript
type TypedRegExpExecArray<captures extends SList> = ToTuple<SCons<string, captures>> & {index: number; input: string};
type TypedRegExpMatchArray<captures extends SList> = ToTuple<SCons<string, captures>> & {index?: number; input?: string};
```

結果の配列の最初（0番目）には、マッチした部分全体（文字列）が入るので、 `captures` ではなく `SCons<string, captures>` を `ToTuple` に渡している。

型レベルリストから関数の型への変換も、似たように書ける。

```typescript
type ToFunction5<r, a0, a1, a2, a3, a4, a extends SList> = {
    "Nil": (a0: a0, a1: a1, a2: a2, a3: a3, a4: a4) => r;
    "Cons": (a0: a0, a1: a1, a2: a2, a3: a3, a4: a4, a5: a["head"]) => r; // a["tail"] is dropped...
}[a["tag"]];
type ToFunction4<r, a0, a1, a2, a3, a extends SList> = {
    "Nil": (a0: a0, a1: a1, a2: a2, a3: a3) => r;
    "Cons": ToFunction5<r, a0, a1, a2, a3, a["head"], a["tail"]>;
}[a["tag"]];
type ToFunction3<r, a0, a1, a2, a extends SList> = {
    "Nil": (a0: a0, a1: a1, a2: a2) => r;
    "Cons": ToFunction4<r, a0, a1, a2, a["head"], a["tail"]>;
}[a["tag"]];
type ToFunction2<r, a0, a1, a extends SList> = {
    "Nil": (a0: a0, a1: a1) => r;
    "Cons": ToFunction3<r, a0, a1, a["head"], a["tail"]>;
}[a["tag"]];
type ToFunction1<r, a0, a extends SList> = {
    "Nil": (a0: a0) => r;
    "Cons": ToFunction2<r, a0, a["head"], a["tail"]>;
}[a["tag"]];
type ToFunction<r, a extends SList> = {
    "Nil": () => r;
    "Cons": ToFunction1<r, a["head"], a["tail"]>;
}[a["tag"]];
```

# TypedRegExp 型の定義

ここまで準備したものを使うと、 `TypedRegExp` 型および、「より良い型のついた」 `RegExp.exec`, `String.match`, および `String.replace` 関数の定義は次のように書けるだろう：

```typescript
// interface TypedRegExp<> extends RegExp では 'exec' の型が違うと言われて怒られた、ので交差型を使う
type TypedRegExp<captures extends SList> = {
    exec(string: string): TypedRegExpExecArray<captures> | null;
} & RegExp; /* RegExp が & の後でないとメソッドの型を上書きできないようなので注意 */

interface String {
    match<captures extends SList>(regexp: TypedRegExp<captures>): TypedRegExpMatchArray<captures> | null;
    replace<captures extends SList>(searchValue: TypedRegExp<captures>, replacer: ToFunction<string, SCons<string, Concat<captures, SCons<number, SCons<string, SNil>>>>>): string;
}
```

replace に渡す関数の引数には、キャプチャーの他に、マッチ部分（先頭）および位置と文字列全体（末尾）が渡されるので、型レベルリストの操作でそれに対応している。

この定義の下で、最初に挙げたコード例に型注釈を足したものがコンパイルエラーになることが確認できる：

```typescript
let str = "abc"
let m = str.match(/(a)(b)?/ as TypedRegExp<SCons<string, SCons<string | undefined, SNil>>>);
if (m) {
    let a: string = m[1];
    let b: string = m[2]; // --strictNullChecks でエラー
}
```

しかし残念なことに、 replace に渡す関数の引数の型は相変わらず推論されないままである：

```typescript
let str = "x\\yz";
let t = str.replace(/\\(.)/ as TypedRegExp<SCons<string, SNil>>, (m, s) => s.toUpper()); // エラーにならない！
console.log(t);
```

筆者が TypeScript が関数の引数を推論する仕組みについてよく理解していないので場当たり的な対応となるが、 `String.replace` の定義で `ToFunction` を使わないように変えたらうまくいった：

```typescript
interface String {
    match<captures extends SList>(regexp: TypedRegExp<captures>): TypedRegExpMatchArray<captures> | null;
    replace<a0, a1, a2>(searchValue: TypedRegExp<SCons<a0, SCons<a1, SCons<a2, SNil>>>>, replacer: (match: string, a0: a0, a1: a1, a2: a2, offset: number, string: string) => string): string;
    replace<a0, a1>(searchValue: TypedRegExp<SCons<a0, SCons<a1, SNil>>>, replacer: (match: string, a0: a0, a1: a1, offset: number, string: string) => string): string;
    replace<a0>(searchValue: TypedRegExp<SCons<a0, SNil>>, replacer: (match: string, a0: a0, offset: number, string: string) => string): string;
    replace(searchValue: TypedRegExp<SNil>, replacer: (match: string, offset: number, string: string) => string): string;
}
```

# 結論と課題

キャプチャーの情報を持った正規表現型を作る、という目標は概ね達成できた。課題は、

- 正規表現リテラルにつく型は相変わらず普通の `RegExp` なので、型付き正規表現の恩恵を受けるには自分で適切な型注釈を書く必要がある。
- `ToTuple` 型の定義と `String.replace` メソッドの型定義が長ったらしい。

である。

前者については、 TypeScript のソースに前処理を施すという案が考えられるが、やりたくない。

後者は、手書きせずにスクリプトで自動生成する（メタプログラミング）という手もある。ただ、キャプチャーの個数はせいぜい1ケタだろうと思われるので、10個の定義を手書き＆コピペするのでも十分だろう。