Vim本体に組み込み関数を追加するパッチを投げた

この記事は [第2のドワンゴ Advent Calendar 2018](https://qiita.com/advent-calendar/2018/dwango2) の10日目の記事です。



# はじめに
私のVim歴は現時点で約6年です。
しかし、今までVim本体に貢献したことはありませんでした。

やってみるか、と思ったきっかけは、先日開催された[VimConf 2018](https://vimconf.org/2018/)でVimの作者であるBramが「多くの人が欲している機能のパッチを送ってくれればもちろん追加を検討するし、そんなに多くの人が欲していなくとも小さなパッチであれば追加するかもしれない」と話していたことです。
(参加記事はこちら[VimConf 2018のスポンサーをしました - dwango on GitHub](https://dwango.github.io/articles/vimconf2018/))
Vim本体の開発では、彼を通さないと変更は適応されません。
これまで私はBramは非常に保守的で、厳しい感じの人なんだろうな、という(勝手な)印象を持っていました。
しかし、VimConf 2018での交流を経てカジュアルにパッチを送ってもちゃんと見てもらえそうだ、と考えを改めました。
そして、少し前から`flatten`関数が組み込みで欲しいと思っていたのでやってみることにしました。



# flatten関数と追加したかった動機
最初に私が求めていたのは以下のような特に変哲のないflatten関数です。

```vim
echo flatten([1, [2], 3])
" => [1, 2, 3]
```

もちろんこの関数はVim scriptを使って実装可能です。
例として[How to flatten a nested list in Vim script? - Stack Overflow](https://stackoverflow.com/questions/11912688/how-to-flatten-a-nested-list-in-vim-script)で回答されているものを引用します。

```vim
function! Flatten(list)
  let val = []
  for elem in a:list
    if type(elem) == type([])
      call extend(val, Flatten(elem))
    else
      call add(val, elem)
    endif
    unlet elem
  endfor
  return val
endfunction
```

flattenを使いたい場所は.vimrcだったのでこういうよくあるutil関数を追加するのはいやでした。
またVim scriptは実行速度が遅いことで有名です。
なので、こういう関数は組み込みで入っている方がいいと考えました。
特に`map()`関数があるのに`flatten()`が無いのは不便になることが多い気がします。
あった場合は以下のように組み合わせてシンプルに書けるようになります。
(そしてきっと`flatmap()`も欲しくなる)

```vim
# パスを集める
echo flatten(map(['./xxx/*', './yyy/*'], 'glob(v:val, 0, 1)'))
```



# Vim本体に手を加える
次に本体への修正ですが、大体1週間くらいで出来ました。
しかし、これは私一人の力ではなく、7割りくらい[vim-jp](https://vim-jp.org/)のおかげです。
vim-jpは日本のVim開発者(Pluginなどを含む)をサポートするためのグループです。
そのSlackチャンネルでいろいろと教えてもらいつつ、コード読み、パッチ作成、を行いました。

これ以降はどのような流れで開発をしたかを書いていきます。
(わかりやすさのために必ずしも自分が行った順ではありません。)


## 下調べ
きっと記事があるはず、と思って調べてみると案の定、最適な記事がありました。
[Vim のソースのいじり方(:terminal を作るまで)](https://qiita.com/mattn/items/ee438479b09055a2f305)の[Vim script に関数を足す方法](https://qiita.com/mattn/items/ee438479b09055a2f305#vim-script-%E3%81%AB%E9%96%A2%E6%95%B0%E3%82%92%E8%B6%B3%E3%81%99%E6%96%B9%E6%B3%95)という部分です。
`trim()`関数を追加するPRが解説されています。
そして、そのPRはこちら
[add small inner trim function by bukn · Pull Request #1280 · vim/vim](https://github.com/vim/vim/pull/1280)
新規関数の追加、ドキュメント、テストの3つでdiffが+119なのでかなり優しい方だと思われます。

これらを参考にし、実際にVimのソースコードも軽く見ます。
その後にやることを列挙しました。

1. `:help develop.txt`でコード変更時のルールを見る
2. `src/list.c`に`list_flatten`を実装
3. `src/evalfunc.c`に`f_flatten`を実装
4. テストを書く
5. Slackで見てもらって改善をする
6. ドキュメントを書く
7. PRを出す

これらを要所要所にてvim-jp Slackで詳しい方々に教えを請いながら進めました。


## コーディングルール
Vimは様々な環境で動作するように作られているためにいくつかルールがあります。
読むまでは知らなかったのですが、Vimの最小サポートコンパイラはC89のようでした。
しかし、C99のいくつかの機能は使ってもいいそうです。
(C89でも何かの拡張でC99で正式に追加された機能が使える、などがあるのかと思います。)

他にも用語などいろいろ書いてあるのをさっと読み、後は雰囲気で周りのソースに合わせて変更を行うことにしました。


## `list_flatten`の実装
list処理を追加するのでまずはその構造体を確認する必要があります
`src/struct.h`の[`struct listvar_S`](https://github.com/vim/vim/blob/55d46913084745a48749d7ac4f48930852e1d87e/src/structs.h#L1273-L1291)がそのようです。
ここを見るとVimの内部実装でリストは双方向リストとして実装されていることがわかります。
そのリストの要素は[`listitem_T`](https://github.com/vim/vim/blob/55d46913084745a48749d7ac4f48930852e1d87e/src/structs.h#L1253-L1260)として同じく`src/struct.h`に定義されています。

C言語の双方向リストの実装ではリンク用のポインタ2つとデータ用の`void*`、という構成をよく見かけますがVimでは`void*`ではなく、[`typval_T`](https://github.com/vim/vim/blob/55d46913084745a48749d7ac4f48930852e1d87e/src/structs.h#L1217-L1239)を使ってリストの保持する値を表現していました。
メンバには保持する型が何かを示す変数と、値用の共用体があります。
これを踏まえて他のコードを眺めると`list->lv_first->li_tv.vval.v_number`のように要素にアクセスできることがわかりました。

あとは、リストに関する処理は大体`src/list.c`に入っているようだったので、それらの振る舞いを伺いつつ、真似をして書くことにしました。

そうして出来上がった初版がこれです。

```c
    void
list_flatten(list_T *l1, list_T *l2)
{
    listitem_T *item;
    listitem_T *copy_item;

    if (l1 == NULL || l2 == NULL)
        return;

    for (item = l2->lv_first; item != NULL; item = item->li_next)
    {
        if (item->li_tv.v_type == VAR_LIST)
            list_flatten(l1, item->li_tv.vval.v_list);
        else
        {
            copy_item = listitem_alloc();
            copy_tv(&item->li_tv, &copy_item->li_tv);
            list_append(l1, copy_item);
        }
    }
}
```

Stack Overflowの回答と殆ど同じような感じです。
引数`l1`に引数`l2`を展開しながらコピーしていきます。
`l2`には特に変更を加えず、`l1`は呼び出し側で新しく確保している、ことを想定しています。

## `f_flatten`を実装
こちらも見様見真似で以下のように実装しました。

```c
    static void
f_flatten(typval_T *argvars, typval_T *rettv)
{
    list_T *l;

    if (argvars[0].v_type != VAR_LIST)
    {
        EMSG2(_(e_listarg), "flatten()");
        return;
    }

    if ((l = argvars[0].vval.v_list) != NULL
            && !tv_check_lock(l->lv_lock, (char_u *)N_("flatten() argument"), TRUE)
            && rettv_list_alloc(rettv) == OK)
        list_flatten(rettv->vval.v_list, l);
}
```

`argvars`にVim script組み込み関数を実行したときの引数が入ります。
なので、リストかどうかのチェックをしています。
`rettv_list_alloc`という関数を使って戻り値である`rettv`にリスト用のメモリを割り当て、`list_flatten`を実行しています。


## デバッグについて
さて、ここまで実装するためにはもちろん動かして確認し、デバッグをするという作業が必要です。
Vimに最近追加された素晴らしい機能の一つにGDBとVimのターミナルを連携させる`:Termdebug`があります。
この機能は標準Pluginとして実装されています。
[VimConf 2018のujihisaさんの発表スライド](https://speakerdeck.com/ujihisa/vimconf-2018
)が参考になります。
というか、私もこの発表で知りました。
これはかなり最近の機能なのでNeovimにはまだ入っていないようでした。

使っている画面はこんな感じです。
(見やすいようにwindowのレイアウトは変えています)
![2018-12-09-184748_1476x1035_scrot.png](https://qiita-image-store.s3.amazonaws.com/0/40445/adb05de0-f308-26de-7ef3-73f2e749e0f7.png)

左に実行中のソースコード、右上がGDB、右下がVimです。
VimのリポジトリディレクトリのルートでVimを起動し、以下のコマンドを実行すると使うことが出来ます。

```vim
:packadd termdebug
:TermdebugCommand ./src/vim --clean
```

GDBのWindowに移動して直接GDBコマンドを実行してもいいですし、このPluginが提供してくれる`:Break`, `:Next`などのコマンドを使うことも出来ます。
このPluginのおかげで自分の実装のデバッグと真似したい箇所の振る舞いを確認するときにかなり捗りました。
詳しい人に聞ける環境といい感じのデバッガーがあるとスピードが上がって嬉しいですね。
詳細は`:help terminal-debugger`を見てください。


## テストを書く
`trim()`の追加PRを真似て、雰囲気で`src/testdir/test_flatten.vim`にテストを追加して、Makefileを修正しました。
`make test`でVimのテスト全てを実行できることは以前から知っていましたが、個別にテストを実行する方法がわからず、ここでもvim-jp Slackで質問して教えていただきました。
いわく、テストの追加や実行については[`src/testdir/README.txt`](https://github.com/vim/vim/blob/55d46913084745a48749d7ac4f48930852e1d87e/src/testdir/README.txt)に書いてあるようでした。
実行は`src`ディレクトリ内で`make test_flatten`することで出来ました。

```vim
" Test for triming strings.
func Test_flatten()
    call assert_equal(flatten([], []))
    call assert_equal(flatten([1, 2, 3]), [1, 2, 3])
    call assert_equal(flatten([[1], [2], [3]]), [1, 2, 3])
    call assert_equal(flatten([[[[1]]], [2], [3]]), [1, 2, 3])
endfunc
```

`assert_equal`の引数が逆ですがちゃんと無事に動きました。


## Slackで見てもらって改善をする
既に何度も言及していますが、このSlackでわいわい開発できたことによって初心者である自分の投げるPRのクオリティが100倍くらいになりました。
時系列順ではありませんが、そこで出たことをつらつらと書いていきます。

### オプション引数(`maxdepth`)で展開する深さを指定できたほうがいい
最初、私はオプション引数が省略されたら全て展開してくれる挙動がいいと思っていましたが、デフォルトは深さ1だけ展開する、という挙動もあるようです。
ここで、再帰で実装すると後述する都合でスタックオーバーフローする危険についても指摘をいただけました。
最終的にはデフォルト値を1にしました。

### エラー番号を必要なら追加すること
`maxdepth`が負の値のときにエラーを挙げるように修正をしました。

### リスト操作系は引数に破壊的を行うことが多い
Vimは破壊されたくない場合は`copy()`, `deepcopy()`を使う方針だそうです。
確かに自分でPluginを書いたりしたときに辞書の`deepcopy()`などを使っていたような気がします。
これを受けて、破壊的変更に実装を修正しました。

### 参照カウンタのバグを見つける
以下のようにわざとVimのGCを実行してやると、参照カウンタのバグに気づきやすいと教えていただきました。

```vim
let x = flatten(v)
call garbagecollect()
echo x
```

GCを使っていることは知っていましたが、`garbagecollect()`関数の存在は知りませんでした。
また、テストファイルで実行したいときは`test_garbagecollect_now()`関数を使うそうです。

### `CTRL-C`の割り込み中断
`line_breakcheck()`を実行し、`got_int`というグローバル変数を確認して行います。
長くて入れ子の深いリストなどを考えると実装しておいたほうがよさそうでした。

### 無限再帰リスト
以下のようにして無限再帰リストを作ることが可能です。
リストなので確かにできるのですが言われてみれば…という感じでした。

```vim
let x = [1]
let y = [2]
call add(x, y)
" x = [1, [2]]
call add(y, x) 
" y = [2, [1, [...]]]
" 注: echoコマンドの出力なので省略される
```

再帰による実装だとこの無限再帰リストを与えられたときに駄目になってしまいます。

### ループに対応
家に帰ったら実装してみるか、と考えていたらなんと @mattn さんがスッと実装していました。
これによって無限再帰リストにも対応でき、関数呼出しも減って更に高速になりました。
ちょっと悔しかったので次は頑張りたいです。

### Vimのドキュメントは"Two Spaces After a Period"スタイル
この記事を書いているときに教えていただきました。
確認してみると確かに行末以外のピリオドの後にはスペースが2つ付いていたので急いで直してpushしました。


## ドキュメントを書く
これはVimのドキュメント形式に倣って追加していくだけです。
PRを投げた後にSlackチャンネルには入っていない方からTwitter経由で上記のスタイルと、追加もれなどを修正していただきました。


## PRを出す
最終的な変更では以下のようになりました。

```c
    int
list_flatten(list_T *list, long maxdepth)
{
    listitem_T  *item;
    int     n;

    if (maxdepth == 0)
        return OK;

    n = 0;
    item = list->lv_first;
    while (item != NULL && !got_int)
    {
        line_breakcheck();

        if (item->li_tv.v_type == VAR_LIST)
        {
            listitem_T *next = item->li_next;

            vimlist_remove(list, item, item);
            if (list_extend(list, item->li_tv.vval.v_list, next) == FAIL)
                return FAIL;

            if (item->li_prev == NULL)
                item = list->lv_first;
            else
                item = item->li_prev->li_next;

            if (++n >= maxdepth)
            {
                n = 0;
                item = next;
            }
        }
        else
        {
            n = 0;
            item = item->li_next;
        }
    }

    return OK;
}
```

```c
    static void
f_flatten(typval_T *argvars, typval_T *rettv)
{
    list_T  *l;
    long    maxdepth;
    int     error = FALSE;

    if (argvars[0].v_type != VAR_LIST)
    {
        EMSG2(_(e_listarg), "flatten()");
        return;
    }

    if (argvars[1].v_type == VAR_UNKNOWN)
        maxdepth = 1;
    else
    {
        maxdepth = (long)get_tv_number_chk(&argvars[1], &error);
        if (error)
            return;
        if (maxdepth < 0)
        {
            EMSG2(_(e_nonneg), "maxdepth");
            return;
        }
    }

    if ((l = argvars[0].vval.v_list) != NULL && !tv_check_lock(l->lv_lock,
                (char_u *)N_("flatten() argument"), TRUE)
            && list_flatten(l, maxdepth) == OK)
        copy_tv(&argvars[0], rettv);
}
```



テストをいくらか増やした後に、PRを出しました。
そのPRはこちらです。
[add flatten() to flatten list by mopp · Pull Request #3676 · vim/vim](https://github.com/vim/vim/pull/3676)

PRコメントでは他の言語にもあるということ、使用例、Vim scriptライブラリで既にあって使用されていること、を書きました。

数時間後にBramがコメントを付けてくれたのでそれに返信して今に至る、という感じです。
コメントから否定的な印象は感じないのでこのままマージしてもらえればいいなと思っています。
結果が分かり次第ここにも追記します。

# おわりに
アドベントカレンダーというよりなんだか雑記のようになってしまいました。
ですが、Vim本体の開発に興味がある人の助けになれればと思っています。

今後も機会があればVim本体にコントリビュートしていくつもりです。