D言語の構文を拡張する

D言語 Advent Calendar 2014の23日目の記事です。
更に、[Aizu Advent Calendar 2014](http://www.adventar.org/calendars/533)の23日目の記事でもあります。

D言語には文字列mixin([宣言](http://www.kmonos.net/alang/d/module.html#MixinDeclaration)、[文](http://www.kmonos.net/alang/d/statement.html#MixinStatement)、[式](http://www.kmonos.net/alang/d/expression.html#MixinExpression))とCTFE([コンパイル時関数実行](http://www.kmonos.net/alang/d/function.html#interpretation))という機能があります。
文字通り、文字列mixinは文字列の中身をソースコードとして展開する機能で、
CTFEはコンパイル時に関数を実行する機能です。
上の２つの機能を組み合わせて、D言語の構文を拡張できるライブラリを作りました。

## TL;DR
構文拡張ライブラリ：[Tcenal](https://github.com/youxkei/tcenal)
Swap演算子追加の例：[swapop](https://github.com/youxkei/swapop)

## Tcenal
D言語の構文拡張ライブラリです。
https://github.com/youxkei/tcenal

## どうやって拡張するの？
Tcenalは内部でD言語の大部分のパーサを持っていて、そのパーサをオーバーライドする形で拡張します。
その後、パースツリーからD言語のソースコードを生成して文字列mixinします。

## 使っている構文解析のアルゴリズム
直接左再帰に対応したPackrat Parsingを使っています。

## 例：Swap演算子の追加
本当はパターンマッチとかやりたかったんですが、大変そうなので・・・

### dubでTcenalを使う
```json:dub.json
{
    "dependencies": {
        "tcenal" : "~>0.0.1"
    }
}
```

### パーサをオーバーライドする
Tcenalの`views/drules.peg`を見て、パーサをオーバーライドします。

```d:source/swap_op.d
import parser_combinator.parsing_result : ParsingResult;
import parser_combinator.memo : Memo;
import parser_combinator.combinators;

import tcenal.dparsers : skip;
import tcenal.dsl.generate_parsers : generateParsers;


mixin (generateParsers(`
    AssignExpression <- SwapExpression / super;
    SwapExpression <- ConditionalExpression ":=:" ConditionalExpression;
`));
```

PEGに似たDSLを使います。ほとんどPEGですが、セミコロンで区切る必要があります。
規則の右辺でsuperを使うことによって、元々のD言語パーサの`AssignExpression`を指定しています。
`ParsingResult`、`ParseTreeNode`、`Memo`は`generateParsers`が生成するコードに含まれるので、必ずimportしてください。このへんは後々どうにかしたいと思ってます。
今回はimportすることによって元々のD言語パーサの`skip`を使っていますが、importせずに自分で定義した`skip`を使うことも出来ます。

### パーサをインスタンス化する
パーサは、`RuleSelector`を渡してインスタンス化する必要があります。
`RuleSelector`は、実際にオーバーライドの処理を行っているテンプレートです。

```d:source/swap_op.d(続き)
import tcenal.rule_selector : createRuleSelector;
import tcenal.dparsers : Module, skip;

alias parse = Module!(createRuleSelector!().RuleSelector);
```

とりあえず一番外側のパーサであるModuleに`RuleSelector`を渡してパーサをインスタンス化してます。
`createRuleSelector`をインスタンス化するモジュールが重要で、
例えば`createRuleSelector`をインスタンス化したモジュール内に`AssignExpression`が存在する場合にはそれを使い、
存在しなかった場合は`tcenal.dparsers.AssignExpression`が使われます。
このようにオーバーライド的な挙動を実現しています。

### パースツリーを見てみる
この時点でパースツリーを見てみます。

```d:source/app.d
import parser_combinator.memo : Memo;
import std.stdio : writeln;
import swap_op : parse;

void main()
{
    Memo memo;
    writeln(parse("void f(){ int a,b; a :=: b; }", 0, memo).node);
}
```

```
$ dub
+-Module
  +-DeclDefs
    +-#repeat
      +-DeclDef
        +-Declaration
          +-FuncDeclaration
            +-#sequence
              +-#option
              +-BasicType
              | +-IdentifierList
              |   +-Identifier
              |     +-"void"
              +-FuncDeclarator
              | +-#sequence
              |   +-#option
              |   +-Identifier
              |   | +-"f"
              |   +-FuncDeclaratorSuffix
              |     +-#sequence
              |       +-Parameters
              |       | +-#sequence
              |       |   +-"("
              |       |   +-#option
              |       |   +-")"
              |       +-#option
              +-FunctionBody
                +-BlockStatement
                  +-#sequence
                    +-"{"
                    +-StatementList
                    | +-#sequence
                    |   +-Statement
                    |   | +-NonEmptyStatement
                    |   |   +-NonEmptyStatementNoCaseNoDefault
                    |   |     +-DeclarationStatement
                    |   |       +-Declaration
                    |   |         +-VarDeclarations
                    |   |           +-#sequence
                    |   |             +-#option
                    |   |             +-BasicType
                    |   |             | +-IdentifierList
                    |   |             |   +-Identifier
                    |   |             |     +-"int"
                    |   |             +-Declarators
                    |   |             | +-#sequence
                    |   |             |   +-DeclaratorInitializer
                    |   |             |   | +-VarDeclarator
                    |   |             |   |   +-#sequence
                    |   |             |   |     +-#option
                    |   |             |   |     +-Identifier
                    |   |             |   |       +-"a"
                    |   |             |   +-#repeat
                    |   |             |     +-#sequence
                    |   |             |       +-","
                    |   |             |       +-DeclaratorInitializer
                    |   |             |         +-VarDeclarator
                    |   |             |           +-#sequence
                    |   |             |             +-#option
                    |   |             |             +-Identifier
                    |   |             |               +-"b"
                    |   |             +-";"
                    |   +-StatementList
                    |     +-Statement
                    |       +-NonEmptyStatement
                    |         +-NonEmptyStatementNoCaseNoDefault
                    |           +-ExpressionStatement
                    |             +-#sequence
                    |               +-Expression
                    |               | +-CommaExpression
                    |               |   +-AssignExpression
                    |               |     +-SwapExpression
                    |               |       +-#sequence
                    |               |         +-ConditionalExpression
                    |               |         | +-OrOrExpression
                    |               |         |   +-AndAndExpression
                    |               |         |     +-CmpExpression
                    |               |         |       +-ShiftExpression
                    |               |         |         +-AddExpression
                    |               |         |           +-MulExpression
                    |               |         |             +-UnaryExpression
                    |               |         |               +-PowExpression
                    |               |         |                 +-PostfixExpression
                    |               |         |                   +-PrimaryExpression
                    |               |         |                     +-Identifier
                    |               |         |                       +-"a"
                    |               |         +-":=:"
                    |               |         +-ConditionalExpression
                    |               |           +-OrOrExpression
                    |               |             +-AndAndExpression
                    |               |               +-CmpExpression
                    |               |                 +-ShiftExpression
                    |               |                   +-AddExpression
                    |               |                     +-MulExpression
                    |               |                       +-UnaryExpression
                    |               |                         +-PowExpression
                    |               |                           +-PostfixExpression
                    |               |                             +-PrimaryExpression
                    |               |                               +-Identifier
                    |               |                                 +-"b"
                    |               +-";"
                    +-"}"
```
追加した`SwapExpression`がちゃんと動いてますね！！！

### パースツリーからD言語のソースコードを生成する
パースツリーなので、基本的に葉の値をつなげていけば元の文字列になります。
追加した`SwapExpression`を特別に扱い、それ以外は単純に連結するようなVisitorを書きます。

```d:source/swap_op(続き)
import parser_combinator.parse_tree_node : ParseTreeNode;

string generateVisitor(ParseTreeNode node)
{
    if (node.ruleName == "SwapExpression")
    {
        return "(){"
            "static import std.algorithm;"
            "std.algorithm.swap(" ~ node.children[0].children[0].generateVisitor() ~ ","
                                  ~ node.children[0].children[2].generateVisitor() ~ ");"
        "}()";
    }
    else if (node.ruleName.length > 0)
    {
        string codeSegment;
        foreach (child; node.children)
        {
            codeSegment ~= child.generateVisitor();
        }
        return codeSegment;
    }
    else
    {
        return node.value ~ " ";
    }
}

string SWAP_OP(string src)
{
    Memo memo;
    return parse(src, 0, memo).node.generateVisitor();
}
```

`SwapExpression`の直下は`#sequence`であることに気をつけてください。
swapの実装は、`std.algorithm.swap`をそのまま使っています。
マクロっぽさを出すために、`SWAP_OP`は大文字にしています。

### 試す
```d:source/app.d
import swap_op;

mixin (SWAP_OP(q{
    void bubblesort(T)(T[] array)
    {
        foreach (base; 0 .. array.length - 1)
        {
            foreach_reverse (i; base .. array.length - 1)
            {
                if (array[i] > array[i + 1])
                {
                    array[i] :=: array[i + 1];
                }
            }
        }
    }

    void main()
    {
        import std.stdio : writeln;

        int[] array = [3, 1, 4, 1, 5, 9, 2];
        array.bubblesort();
        writeln(array);
    }
}));
```

```
$ dub
[1, 1, 2, 3, 4, 5, 9]
```

ちゃんと動いてます！！！！！

### 動くコード
https://github.com/youxkei/swapop

## 対応していないD言語の構文
- C言語スタイルの宣言
- asm文
- 浮動小数点リテラル（！？）

## 既知のバグ
関数の仮引数の型に`int`を使うと、`in`と`t`として構文解析されてしまいます。
これは、ストレージクラス`in`が`int`よりも優先されているのが原因です。
D言語のパーサはgrammar.ddから自動生成したものなので、
これ以外にも、おそらくバグがあると思います。
さらに、文字列などのリテラルも、エスケープシーケンスに対応していないなど、実装がかなり適当です。

## まとめ
アドベントカレンダー用にネタとして作り始めたTcenalですが、意外に時間がかかってしまいました。
現状かなり荒削りなので、その辺をどうにかしたいです。