Swiftのコンパイラを改造して独自構文を追加する

去る 12 月 3 日、ついに [Swift がオープンソースになりました](https://swift.org/)！！

僕は、今度 [try! Swift](http://blog.kishikawakatsumi.com/entry/2015/12/02/193302) で Swift について話す予定なんですが、 Swift がオープンソースになったからには、コンパイラの中身まで見て証拠を掴んだ上で話さなければならないこともあります。

そんなわけで早速コンパイラのソースを読もうと思ったんですが、目的なく漫然と読むのも辛いです。そこで、勉強がてら Swift のコンパイラを改造して前からほしいと思っていた構文を追加してみました（ [リポジトリはこちら](https://github.com/koher/swift-with-either) ）。

改造の内容は次の二つです。

- 標準ライブラリに `Either<L, R>` という型を追加
- `Either<L, R>` のシンタックスシュガー `L|R` を追加

これによって、次のようなコードが書けるようになりました。

```swift
// Int|String は Either<Int, String> のシンタックスシュガー
let e: Int|String = .Left(42)

switch e {
case let .Left(left):
    print("left: \(left)")
case let.Right(right):
    print("right: \(right)")
}
```

これは、 ["Swift 3.0で追加されそうなEitherについて"](http://qiita.com/koher/items/288f01cddb0bbb6aa4e1#either-%E3%81%AE%E8%A8%80%E8%AA%9E%E3%83%AC%E3%83%99%E3%83%AB%E3%81%A7%E3%81%AE%E7%89%B9%E5%88%A5%E3%81%AA%E3%82%B5%E3%83%9D%E3%83%BC%E3%83%88) で、 `Either` について言語レベルでこんなサポートがあればいいんじゃないかと述べたものの一部を、自分で実装してみたものになります。

この投稿を読めば、次の二つのことを学べます。

- Swift の標準ライブラリを改造して独自の型や関数、メソッドを追加する方法
- Swift のコンパイラを改造して独自構文を追加する方法

前者に関してはとても簡単なので完璧にわかると思います。後者については、とてもこの投稿を読んだからといって完璧に把握することはできません。どんな構文を追加するかにもよりますし、コンパイラの中身を隅々まで理解するのはほぼ不可能です。とはいえ、何の手がかりもないところから構文を拡張するのはなかなか大変なので、どういう風にやればいいかという雰囲気が伝わればと思います。

## 標準ライブラリに Either<L, R> という型を追加

これは Swift の範囲内なので話は簡単です。

標準ライブラリのコードは [apple/swift](https://github.com/apple/swift) の stdlib/public/core に入っています。 Optional.swift などもここにあります。そこに Either.swift を作って追加しましょう。

中身は、とりあえず今回は `Either` という型さえあればいいので、便利メソッドなどは作らず↓だけとします。

```swift
public enum Either<L, R> {
    case Left(L)
    case Right(R)
}
```

これだけで OK と言いたいところですが、 __ファイルを追加するだけではビルド対象となりません__。  stdlib/public/core/CMakeLists.txt に Either.swift を追加してやる必要があります。

ファイル名がアルファベット順で並んでいるので↓のように追加しました。

```
...
ContiguousArrayBuffer.swift
Either.swift
EmptyCollection.swift
...
```

これで、標準ライブラリに `Either` が追加されます。何も `import` しなくても次のようなコードが実行可能です。

```swift
let e: Either<Int, String> = .Left(42)

switch e {
case let .Left(left):
    print("left: \(left)")
case let.Right(right):
    print("right: \(right)")
}
```

結果は次の通りです。

```
left: 42
```

## Either\<L, R\> のシンタックスシュガー L|R を追加

さて、難しいのはここからです。

Swift において、 `Optional` を使ってエラーを扱うと[とても便利](http://qiita.com/koher/items/c6f446bad54442a28bf4)です。しかし `Optional` はエラー情報を保持できないのが辛いので、代わりに `Either` を[使いたくなります](http://qiita.com/koher/items/288f01cddb0bbb6aa4e1#optional%E3%81%A8%E3%81%AE%E6%AF%94%E8%BC%83)。ですが、 `Optional` には `Int?` のようなシンタックスシュガーや Optional Chaining などの便利な構文があるのに対し、 `Either` は自作した型なので何のサポートもありません。 `Optional` の代わりに `Either` を使うとコード中で使いまくることになるので、そのような構文がないのは辛いところです。

そこで、 `Foo?` が `Optional<Foo>` を表すように、コンパイラの中のパーサを改造して `Foo|Bar` と書けば `Either<Foo, Bar>` を表すようにしてしまいましょう。この構文は  TypeScript や Ceylon の Union type に似せたものです。

コンパイラ関連のコードは lib ディレクトリ下にあります（ヘッダーファイルは include/swift ）。 lib ディレクトリはさらにいくつかのサブディレクトリに分かれています。例えば、次のような感じです。

- Parse: 字句解析、構文解析関連
- AST: 抽象構文木関連
- Sema: 意味解析関連
- SIL: Swift の中間言語（ Swift Intermediate language ）関連

今回関連するのは Parse と、 Parse の中のコードを変更する過程で AST の中のクラスを使うくらいです。

### 方針

今回は、コンパイラの構文解析を改造して動作を変更できるか試すのと、その過程でソースを読むことで全体構造をおぼろげにもつかむことが目的なので、厳密に正しい実装は目指しません。

まず、 `Foo|Bar` を正確に写しとった抽象構文木を作ろうとすると、 `Either` の構文に対応したノードを抽象構文木にも加えるなど、 AST ディレクトリのソースにも色々と修正を加えなければなりません。今回は、 `Foo|Bar` をパースすると `Either<Foo, Bar>` の抽象構文木を吐き出すようにして誤魔化します。

また、本来は `(Foo|Bar)|Baz` が `Either<Either<Foo, Bar>, Baz>` と解釈されなければならないですが、括弧を考え始めるとタプルと競合するなどとても複雑になってしまうので、今回は括弧を扱いません。

最後に、 `Either` では `Optional` のように `let a: Optional<Int> = 42` のような暗黙の型変換もしくはサブタイピングを実現したいところですが、これも今回は扱いません。あくまで、型として `Foo|Bar` のように書くと `Either<Foo, Bar>` と解釈されることだけを目指します。

### パーサの修正

今回やるのは型のパースです。 lib/Parse ディレクトリの中を漁ってると ParseType.cpp というまさにドンピシャっぽいファイルがありました。

`Either` は `Optional` に近いので、ファイルを開いて "Optional" というキーワードで検索してみます。

#### parseTypeSimpleの変更

関連しそうなコードを調べると、 `parseTypeSimple` という関数が大元になってそうです。

```cpp
ParserResult<TypeRepr> Parser::parseTypeSimple(Diag<> MessageID,
                                                 bool HandleCodeCompletion) {
    ...
      if (isOptionalToken(Tok)) {
        ty = parseTypeOptional(ty.get());
        continue;
      }
      if (isImplicitlyUnwrappedOptionalToken(Tok)) {
        ty = parseTypeImplicitlyUnwrappedOptional(ty.get());
        continue;
      }
```

下のように、 `Either` 用のコードも追加しましょう。

```cpp
ParserResult<TypeRepr> Parser::parseTypeSimple(Diag<> MessageID,
                                                 bool HandleCodeCompletion) {
    ...
      if (isOptionalToken(Tok)) {
        ty = parseTypeOptional(ty.get());
        continue;
      }
      if (isImplicitlyUnwrappedOptionalToken(Tok)) {
        ty = parseTypeImplicitlyUnwrappedOptional(ty.get());
        continue;
      }
      if (isEitherToken(Tok)) {
        ty = parseTypeEither(ty.get());
        continue;
      }
```

これで、 `isEitherToken` と `parseTypeEither` の実装が必要となりました。それぞれ、 `isOptionalToken` と `parseTypeOptional` を真似して実装しましょう。

#### isEitherTokenの実装

`isOptionalToken` の実装は次のようになっています。

```cpp
bool Parser::isOptionalToken(const Token &T) const {
  // A postfix '?' by itself is obviously optional.
  if (T.is(tok::question_postfix))
    return true;

  // A postfix or bound infix operator token that begins with '?' can be
  // optional too. We'll munch off the '?', so long as it is left-bound with
  // the type (i.e., parsed as a postfix or unspaced binary operator).
  if ((T.is(tok::oper_postfix) || T.is(tok::oper_binary_unspaced)) &&
      T.getText().startswith("?"))
    return true;
  return false;
}
```

どうやら、トークンの種類と文字列が想定通りかチェックしているようです。 `tok` は include/swift/Parse/Token.h に次のように宣言されています。

```cpp
enum class tok {
  unknown = 0,
  eof,
  code_complete,
  identifier,
  oper_binary_unspaced,   // "x+y"
  oper_binary_spaced,     // "x + y"
  oper_postfix,
  oper_prefix,
  dollarident,
  integer_literal,
  floating_literal,
  string_literal,
  sil_local_name,      // %42 in SIL mode.
  pound_if,
  pound_else,
  pound_elseif,
  pound_endif,
  pound_line,
  pound_available,
  comment,

#define KEYWORD(X) kw_ ## X,
#define PUNCTUATOR(X, Y) X,
#include "swift/Parse/Tokens.def"

  NUM_TOKENS
};
```

`question_postfix` が見つかりませんが、 `include` された Tokens.def の中にあります。

さて、今 `Foo|Bar` のような型をパースできるようにしたいので、該当しそうなものは二項演算を扱っていそうな次の二つです。

```cpp
oper_binary_unspaced,   // "x+y"
oper_binary_spaced,     // "x + y"
```

`Int?` を `Int ?` のように書くことはできないので、 `Either` もそれをならって `Foo | Bar` のような表記はできないことにしましょう。そうすると `oper_binary_unspaced` が残ります。

`isOptionalToken` を真似て `isEitherToken` を実装すると次のような感じになります。

```cpp
bool Parser::isEitherToken(const Token &T) const {
  if (T.is(tok::oper_binary_unspaced) && T.getText().startswith("|"))
    return true;
  return false;
}
```

#### parseTypeEitherの実装

`parseTypeEither` を実装するには、同じく `parseTypeOptional` を参考にしましょう。

```cpp
ParserResult<OptionalTypeRepr> Parser::parseTypeOptional(TypeRepr *base) {
  SourceLoc questionLoc = consumeOptionalToken();
  return makeParserResult(new (Context) OptionalTypeRepr(base, questionLoc));
}
```

どうやら、トークンを読みだして位置を取得し、それを元に抽象構文木のノードを作っているようです。 grep して調べると `OptionalTypeRepr` は AST の中で宣言されているクラスです。

ここでは、方針で決めた通り `EitherTypeRepr` を実装するのではなく、ジェネリクスの構文木に置き換えてしまうことで対処します。

AST の中を探していると、 `GenericIdentTypeRepr` というそれっぽいクラスが見つかりました。

`GenericIdentTypeRepr` のコンストラクタの使い方は、ジェネリクスをパースしてる箇所を真似しましょう。

```cpp
SourceLoc LAngle, RAngle;
 SmallVector<TypeRepr*, 8> GenericArgs;
 if (startsWithLess(Tok)) {
   if (parseGenericArguments(GenericArgs, LAngle, RAngle))
     return nullptr;
 }
 EndLoc = Loc;

 ComponentIdentTypeRepr *CompT;
 if (!GenericArgs.empty())
   CompT = new (Context) GenericIdentTypeRepr(Loc, Name,
                                        Context.AllocateCopy(GenericArgs),
                                        SourceRange(LAngle, RAngle));
```

コンストラクタの引数には次のものを渡しているようです。

- 第一引数: トークンの位置
- 第二引数: 型の名前（今回は `Either` にしたい）
- 第三引数: 型パラメータ
- 第四引数: ジェネリクスの `<` から `>` までの位置の範囲

エラーメッセージがおかしくなるかもしれませんが、第一引数にはとりあえず `|` の位置を渡しておきましょう。

```cpp
// 第一引数に渡す値
SourceLoc verticalLoc = consumeEitherToken();
```

第二引数は `"Either"` を渡せば良さそうですが、引数の型が `Identifier` です。しかも、 `Identifier` のコンストラクタは隠蔽されてて、直接作成することができないようです。無理やり公開して呼んでみましたが、構文木のコンテキストにない文字列だったためエラーになってしまいました。

`Identifier` のコンストラクタをよく見ると、コメントで次のように書いてありました。

```cpp
class Identifier {
  ...

  /// Constructor, only accessible by ASTContext, which handles the uniquing.
  explicit Identifier(const char *Ptr) : Pointer(Ptr) {}
```

どうやら `ASTContext` を使えば良いようです。 `ASTContext` のメソッドを漁ると、 `getIdentifier` という、コンテキストに文字列を登録して `Identifier` を返してくれるメソッドがありました。これを使いましょう。

元に戻って ParseType.cpp の中を検索すると、 `Context.getIdentifier("...")` のような形で使っている箇所を発見しました。多分 `Context` が `Parser` のメンバ変数なのでしょう。これを真似て次のようにすれば良いでしょう。

```cpp
// 第二引数に渡す値
Context.getIdentifier("Either")
```

第三引数にはジェネリクスの型パラメータを渡さなければなりません。ジェネリックな型のパースでは `Context.AllocateCopy(GenericArgs)` と書かれていました。領域を確保し、 `GenericArgs` のコピーを生成しているようです。

この `GenericArgs` は `SmallVector<TypeRepr*, 8> GenericArgs;` と宣言されています。今、 `Either` では型パラメータは二つあればいいので、おそらく次のようにすれば良さそうです。

```cpp
SmallVector<TypeRepr*, 2> GenericArgs;
```

`SmallVector` の使い方がわかりませんが、 grep すると `push_back` メソッドで要素を追加できることがわかりました。

今、 `Foo|Bar` の `Foo` と `Bar` を追加したいわけです。 `parseTypeEither` は `parseTypeOptional` 同様に引数で `TypeRepr *` を受けています。おそらく `parseTypeOptional` が受けているのは `Foo?` のときの `Foo` でしょう。そうすると、 `parseTypeEither` では `GenericArgs` にこれを追加してやれば良さそうです。

```cpp
SmallVector<TypeRepr*, 2> GenericArgs;
GenericArgs.push_back(base);
```

`Foo|Bar` の `Bar` はどうすればいいでしょう？最初に `SourceLoc verticalLoc = consumeEitherToken();` でトークンを消費したので、名前からして次に `parseTypeXxx` を呼び出すと `|` の次からパースしてくれそうです。今、 `Foo|Bar` の `Bar` の部分にはどんな型も来ることができるので、特定の `parseTypeXxx` ではなく最も汎用な関数を使いたいです。探すと `parseType` がありました。これを使いましょう。

`parseType` の戻り値は `ParserResult` で包まれているので、中身の `TypeRepr` を取り出す必要があります。これも、適当に検索したらやり方が出てきました。

```cpp
SmallVector<TypeRepr*, 2> GenericArgs;
GenericArgs.push_back(base);
GenericArgs.push_back(parseType().get());

// 第三引数に渡す値
Context.AllocateCopy(GenericArgs)
```

さて、あとは第四引数だけです。これはジェネリクスの `<` と `>` の位置でしたが、重要ではなさそうなので今は `|` の位置を渡しておきます。

```cpp
// 第四引数に渡す値
SourceRange(verticalLoc, verticalLoc)
```

`consumeOptionalToken` に対応した `consumeEitherToken` は後で作るとして、これまでをまとめると `parseTypeEither` は次のように実装できます。

```cpp
ParserResult<GenericIdentTypeRepr> Parser::parseTypeEither(TypeRepr *base) {
  SourceLoc verticalLoc = consumeEitherToken();
  SmallVector<TypeRepr*, 2> GenericArgs;
  GenericArgs.push_back(base);
  GenericArgs.push_back(parseType().get());
  return makeParserResult(new (Context) GenericIdentTypeRepr(verticalLoc,
                                          Context.getIdentifier("Either"),
                                          Context.AllocateCopy(GenericArgs),
                                          SourceRange(verticalLoc, verticalLoc)));
}
```

#### consumeEitherTokenの実装

`consumeOptionalToken` は次のようになっています。

```cpp
SourceLoc Parser::consumeOptionalToken() {
  assert(isOptionalToken(Tok) && "not a '?' token?!");
  return consumeStartingCharacterOfCurrentToken();
}
```

`consumeEitherToken` を作るのは真似すれば簡単そうです。

```cpp
SourceLoc Parser::consumeEitherToken() {
  assert(isEitherToken(Tok) && "not a '|' token?!");
  return consumeStartingCharacterOfCurrentToken();
}
```

## ビルドと実行

さて、プログラムの修正が終わったのでビルドして実行してみましょう。

[apple/swift](https://github.com/apple/swift) のビルドと実行には↓の投稿が役に立ちました。

- [オープンソースになったSwiftをビルドしてみる](http://qiita.com/shu223/items/99b5ecc0ac5af2566c9c)
- [Swiftがオープンソース化されたので標準ライブラリにメソッド追加してみる](http://qiita.com/shimesaba/items/a6f6403f4208705e0c30)

ビルドができたら実行してみましょう。次のような either.swift というファイルを作ります。

```swift
let e: Int|String = .Left(42)

switch e {
case let .Left(left):
    print("left: \(left)")
case let.Right(right):
    print("right: \(right)")
}
```

実行結果は次の通りです。

```
left: 42
```

独自の構文 `Int|String` がちゃんと動きましたね！！

## まとめ

Swift のコンパイラを改造して独自の構文を追加する方法を説明しました。今回は構文解析を修正して新しいシンタックスシュガーを追加しました。

実際に自分でコンパイラを改造することは少ないかもしれませんが、自分で実装してみることで見えてくることもあるはずです。 Swift がオープンソース化されて、これから [Swift 3.0 をどんなものにすべきかみんなで話し合おう](https://github.com/apple/swift-evolution)ということになっているので、 Swift はこうあるべきだ、ここが気に入らない、と思うところのある人は、議論を深めるためにまず自分で実装してみるといいかもしれません。（間違っても自分で改造したものをいきなりプルリクで送りつけてはいけません。ちゃんと[コミュニティの指針](https://github.com/apple/swift-evolution/blob/master/README.md)に沿って行動しましょう。）