継続的にベンチマークを取るための GitHub Action をつくった

今年9月に GitHub Action v2 がリリースされました．GitHub Action は GitHub が提供する CI/CD サービスです． 既存のサービスと大きく違う点は，処理を汎用的に Action として切り出して再利用できることです． 例えば，GitHub からのリポジトリのクローン actions/fetch や Node.js のセットアップ actions/setup-node などの基本的な実行ステップも Action として実装されています．

今回はこの GitHub Action を利用して，前々からあると良いなと思っていたベンチマークを継続的に取るための Action をつくりました．

github.com

github-action-benchmark はベンチマークの実行の出力からベンチマーク結果を抽出し，GitHub pages のブランチに JSON で保存します． 保存された JSON は GitHub pages でグラフチャートで確認できます．

スクリーンショット

実際にベンチマークを取って表示しているデモは下記の URL で確認できます:

https://rhysd.github.io/github-action-benchmark/dev/bench/

ベンチマークツールの出力からベンチマーク結果を抽出するところでツール固有のロジックが必要で，現在は下記のツールに対応しています．

• cargo bench (Rust)
• go test -bench (Go)
• benchmark.js (JavaScript/TypeScript)

解決したい問題

アプリやライブラリの実行パフォーマンスを見るための手段としてベンチマークがあります． ベンチマークの結果は最適化の際に効果を検証するのに使ったり，開発の中で意図せずパフォーマンスがデグレしていないことを確認したりするために使うのが一般的だと思います． ここでは後者にフォーカスを当てます．

それなりにメジャーな言語には大抵ベンチマークを取るための公式ライブラリやデファクトなライブラリがあります． それらのツールはベンチマークを実行して結果を表示したり，指定したリビジョン間での比較を行ったりはできますが，開発の中で継続的に計測結果をモニタするような仕組みは提供してくれません．

ですが，意図しないパフォーマンスのデグレを防ぐには継続的にベンチマーク結果をチェックする必要があります． それを GitHub 上のリポジトリに絞って行うための Action が github-action-benchmark です．

使い方

Examples

リポジトリ内に Rust, Go, JavaScript のそれぞれの実際に動くデモを置いてあります．これらのデモは実際に github-action-benchmark のリポジトリで CI の一部として実行されています．

• Rust:
  • プロジェクト
  • ワークフロー
  • Action 実行ログ
• Go:
  • プロジェクト
  • ワークフロー
  • Action 実行ログ
• JavaScript:
  • プロジェクト
  • ワークフロー
  • Action 実行ログ

これらのワークフローを実行して収集されたログが github-action-benchmark の GitHub pages のページにホストされています．

github-action-benchmark は複数のベンチマーク結果を1箇所に集められるため，複数の言語で開発されているリポジトリや monorepo な構成のリポジトリでも問題なく使えます．

余談ですが，全てのプロジェクトでフィボナッチ数を求めるベンチマークを回していて，各言語のフィボナッチ数計算に対する実行パフォーマンスが何となく分かりますね．この超簡単な例では Rust が一番速く，Go は Rust に比べて1.6倍ほど遅く，Node.js は Go に比べて2倍ほど遅いです．

ワークフローの書き方

上記の Examples のワークフロー設定（YAML）を真似すれば問題ないと思いますが，一応ワークフローの書き方を説明します．どの言語でもほぼ変わらないので，ここでは Go プロジェクトを仮定します．

まずはベンチマークの出力を取得するステップを追加します．github-action-benchmark はベンチマーク出力を含むテキストファイルを入力とするので，tee コマンドなどを使ってベンチマーク結果をログに出しつつ保存します．

- name: Run benchmark
  run: go test -bench 'Benchmark' | tee output.txt

ここで得た output.txt を使って github-action-benchmark を実行します．

- name: Store benchmark result to gh-pages
  uses: rhysd/github-action-benchmark@v1
  with:
    name: My Project Go Benchmark
    tool: 'go'
    output-file-path: output.txt

ここで，uses: rhysd/github-action-benchmark@v1 はリポジトリ https://github.com/rhysd/github-action-benchmark の v1 をチェックアウトして使いますという宣言です．github-action-benchmark では v1 ブランチに v1.x.y の最新のバージョンをデプロイしているので，それがチェックアウトされます．もしバージョンを固定したければ v1.0.2 のようなタグも提供しています．

with: のセクションはこのアクションへの入力です．

• name はベンチマークの名前です．複数のベンチマークを取る場合はこの値がリポジトリ内で一意になるようにしてください． 指定しない場合のデフォルト値は "Benhcmark" です．
• tool はどのツールを使ってベンチマーク出力を取得したかを示すものです．"cargo", "go", "benchmarkjs" の中のいずれかの値を指定する必要があります．
• output-file-path はベンチマークの出力が保存されているファイルへのパスを指定します．リポジトリからの相対パスで記述できます．

これ以外にも，入力や出力をカスタマイズするためにいくつかの入力が定義されています．詳しくは下記の README の表を参照してください．

https://github.com/rhysd/github-action-benchmark#action-inputs

github-action-benchmark を実行すると，gh-pages ブランチの dev/bench/ 以下に結果が JavaScript ファイル data.js として出力され，（もし既に無ければ）同じディレクトリにグラフチャートを見るための index.html が生成され，それらを含むコミットが作られます． ブランチや生成場所のディレクトリパスは上記の with: に書く入力で変えられます．

最後にブランチをリモートに push します．github-action-benchmark がコミットの生成まで行い push をしないのは，Action は（GitHub API トークンを入力で受け取るなどしない限り）リモートに push する権限を持っていないからです． ここでは安全側に倒して github-action-benchmark 内では push しない設計にしました．

追記(2019/11/11 20:28): どうやら Action は現在 private リポジトリのみで GitHub pages をデプロイすることが可能なようです．いただいた情報によるとこれは GitHub Action 側の問題らしいので，いずれ解消されて GitHub pages への push は github-action-benchmark 側でできるようになるかもしれません（thanks to @pris314 さん）

GitHub Action ではワークフローの実行で GitHub API トークンを自動で発行してくれるので，push するのは簡単です．

- name: Push benchmark result
  run: git push 'https://you:${{ secrets.GITHUB_TOKEN }}@github.com/you/repo-name.git' gh-pages:gh-pages

トークンは secrets に保存されているのでそれを展開して git push します．もちろん実行ログでは secrets の展開部分は隠されます．

ちなみに複数のベンチマークを複数ワークフローで並列で実行している場合は，他のワークフローによって GitHub pages のブランチが更新されていて直接 push できない場合があるので，push 前に git pull --rebase などを挟んでください．

また，github-push-action を使う手もあります（push は自前でやるのがおすすめですが）．

- name: Push changes
  uses: ad-m/github-push-action@master
  with:
    branch: gh-pages
    github_token: ${{ secrets.GITHUB_TOKEN }}

gh-pages ブランチがリモートにまだ無い場合は作成しておいてください．

$ git checkout -b --orphan gh-pages
$ git commit -m 'first commit' --allow-empty
$ git push origin gh-pages

これでワークフローが走ったときにベンチマーク結果が gh-pages 内に保存され，https://you.github.io/repo-name/dev/bench で確認できるようになります．

ページを開くとベンチマークのテストケースごとにグラフが表示されます．縦軸がベンチマークの値，横軸がコミットで，右に行くほど新しいコミットを示しています．これを確認することで，ベンチマーク結果の変化が確認できます．

グラフのデータポイント上にマウスカーソルを置くと

• コミットハッシュ
• コミットメッセージ
• コミットの作成日時とコミッター
• ベンチマークの値

が表示されます．

さらにここでクリックすると GitHub 上でそのコミットのページが開くので，そこでコードの変更内容を確認できます．

また，最下部にベンチマークデータをダウンロードできるボタンを置いてあるので，それをクリックするとベンチマーク結果を JSON としてダウンロードできます．

もし GitHub pages のブランチにデフォルトで生成される index.html が気に入らなければ，好きに変更したり自前で作ったものに差し替えて OK です．github-action-benchmark は既に index.html がある場合は関与しませんし，データは全て data.js 側にあって window.BENCHMARK_DATA に格納されています．

使用の注意点

上記で説明したとおり，github-action-benchmark はリポジトリ上のブランチを変更し，それをワークフロー側でリモートに push するユースケースを想定しています．

なので，pull request ではこの Action が実行されないように注意してください．万一悪意あるユーザが pull request を作成し，gh-pages に悪意ある変更を加える処理を入れて pull request を投げると，それが反映されてしまいます．

ワークフローの指定で master のみで実行するように制限するか，

on:
  push:
    branches:
      - master

ジョブの実行ステップに記述できる if: セクションで pull request で gh-pages ブランチを push するステップを実行しないようにガードしてください．if: の書き方は公式ドキュメントを読むと分かります:

https://help.github.com/en/actions/automating-your-workflow-with-github-actions/contexts-and-expression-syntax-for-github-actions

GitHub Action 実行環境の注意

そもそも GitHub Action の実行環境がベンチマークに適しているのか？という疑問が残っていると思います．

ずっと同じ内容の単純なベンチマークを実行しているデモページでは大体 10~20% のブレがどのベンチマークでも出ています． そのブレを許容できない場合は使えませんし，許容できるなら使えます．そこはプロジェクト次第だと思います．また，あまり無いと思いますが，ネットワークなどのリソースが絡むともっとブレ幅が大きくなる可能性があります．

安定した環境を自前で用意し，self-hosted runner として使うのも手だと思います．

今後

• 以前のベンチマーク結果と比較して結果が極端に悪くなっている（e.g. 2倍以上遅くなっているなど）時にコミットへのコメントで通知する機能
• ベンチマークツールの出力フォーマットに JSON を追加し，ユーザがベンチマーク結果を JSON で用意することで，どんなベンチマークツールでも対応できるようにする
• ベンチマーク結果を GitHub pages にデプロイする代わりに Elasticsearch や Mackerel のようなサービスにアップロードする機能
• GitHub pages のページとして出力する以外に生の JSON データを生成するオプションを追加する．ベンチマーク結果だけ JSON で欲しくて，後の処理は自前でやりたいときに便利

などがアイデアとしてありますが，今のところ機能的に自分のユースケースでは満足しているため，あまり追加の予定はありません． もし何かアイデアがあれば，issue や pull request で提案していただくのは歓迎です．

感想

GitHub Action のための Action を初めて作成しました．kiro-editor のためにつくったので，早速活用していきたいと思います．

ちなみに JavaScript Action として，TypeScript で作ってみました．GitHub Action 自体まだリリースされたところで情報がほとんどありませんが，実行は速くバグにも逢わなかったので，手探りでもあまり困ったことはありませんでした．微妙にハマったポイントもありましたが，それは別エントリで書こうかなと思います．

ターミナル用 UTF-8 テキストエディタを Rust でスクラッチからつくった

言語処理系やテキストエディタなどのプログラミングツールが好きなので，その周辺を趣味で触ってます．Vim を Wasm にポートするために Vim の実装を読んだりはしているのですが，フルスクラッチでテキストエディタをつくったことはありませんでした．

今年のお盆はめちゃ暑かったので，引きこもって夏休みの自由工作的に Rust でテキストエディタをつくっていたという話です．普段ターミナルで作業しているので，つくるのもターミナル向けテキストエディタです．最近 vim.wasm で C と TypeScript ばかりだったので，そろそろまた Rust か Go を書きたかったのですが，Go はすでに micro という良さそうなテキストエディタ実装があったので，Rust で書いてみることにしました．

まずは Build Your Own Text Editor というガイドを利用して，1000行の C で書かれたエディタ kilo を Rust で再実装し，それをリファクタリング・拡張していく形で実装しています．

目次

• Kiro エディタ
• 使い方
• ベース実装
• kilo 実装を拡張する（効率的な描画，UTF-8 対応，24-bit 色対応）
• Rust による実装（モジュール分割，入出力の抽象化）
• 今後
• 感想

Kiro エディタ

今回作成したエディタはこちらのリポジトリにあります．kilo をベースにしているので，名前は安直に Kiro にしました．

github.com

現時点で下記のような機能があります．

• UTF-8 のテキストファイルを開いて読み込む・新規作成する・保存する（複数ファイル対応）
• UTF-8 テキストを編集する（文字の追加・削除，行の追加・削除など）
• キーショートカット（カーソル移動やテキスト編集など）
• 24-bit 色 (true color) によるシンプルな構文ハイライト（C, Rust, Go, JavaScript, C++）
• インクリメンタルな単純テキスト検索
• ターミナルウィンドウのリサイズ対応

Kiro は xterm 系のターミナルと Unix 系の OS を対象にしています．xterm, urxvt, Gnome-Terminal, Terminal.app, iTerm2, あとできれば Windows Terminal (WSL) で動かしたいと思ってます．今はまだ 24-bit 色の環境として iTerm2，256色の環境として Terminal.app でしか試せてません（もし動かないターミナルがあれば教えてくれるとありがたいです）．

使い方

使い方について簡単に説明します．もし実装だけに興味がある場合は，この章は飛ばしてください．

現時点ではバイナリリリースはしていないので， cargo install kiro-editor で crate をインストールします．小さい数個の crate に依存しているだけなので，ビルドはすぐに終わるはずです．インストールすると kiro コマンドが使えるようになります．

$ kiro                 # Start with an empty text buffer
$ kiro file1 file2...  # Open files to edit

kiro --help するとオプション一覧（といっても --help と --version だけですが）とキーマップ一覧が表示されます． キーマップは Ctrl-? でほぼいつでも確認できるので，それ以外を覚えていなくても大丈夫です．

引数無しで開くと無名のテキストバッファ（後にファイルとして保存可）を開くことができます．引数にファイル（複数指定可）を指定するとそれをエディタ内で開きます．構文ハイライトの種類はファイルの拡張子から自動で特定されます．

以下は新しいファイルを開いて，それを Go として保存する例です：

基本的にはメモ帳などのテキストエディタと同じで，キーを入力するとテキストを入力することができます．kilo とは異なり，Kiro は UTF-8 のテキストを編集することができます．

ユニコード文字単位で編集が行なえます．例えばマルチバイト文字をバックスペースキーで消すとその文字が一気に消えますし，カーソルは文字単位で移動します．また，行がターミナルウィンドウの幅に対して長すぎると wrap せず切れて水平スクロールするようになっているのですが，そのスクロールも文字単位で行われます．倍幅文字の途中で切れたりといったことはありません．ただし，まだ家族絵文字👪のようなzero width joiner を使った文字には対応できていません．

また，Ctrl-G でインクリメンタル単純テキスト検索を行えます．

文字を入力するとそのテキストが検索されてハイライトされ，Ctrl-N（または ↓）および Ctrl-P（または ↑）で次/前のマッチに移動できます．

カーソルを移動する

下記のようなショートカットが用意されています．

キーマップ	説明
Ctrl-F or →	カーソルを1つ右に移動
Ctrl-B or ←	カーソルを1つ左に移動
Ctrl-N or ↓	カーソルを1つ下に移動
Ctrl-P or ↑	カーソルを1つ上に移動
Ctrl-A or Alt-← or HOME	カーソルを行の頭に移動
Ctrl-E or Alt-→ or END	カーソルを行の末尾（最後の文字の次）に移動
Ctrl-[ or Ctrl-V or PAGE DOWN	カーソルを1ページ分下に移動
Ctrl-] or Alt-V or PAGE UP	カーソルを1ページ分上に移動
Alt-F or Ctrl-→	カーソルを1ワード分右に移動
Alt-B or Ctrl-←	カーソルを1ワード分左に移動
Alt-N or Ctrl-↓	カーソルを1段落分下に移動
Alt-P or Ctrl-↑	カーソルを1段落分上に移動
Alt-<	カーソルをファイルの先頭行に移動
Alt->	カーソルをファイルの末尾行に移動

テキストを編集する

下記のようなショートカットが用意されています

キーマップ	説明
Ctrl-H or BACKSPACE	カーソルの左1文字を削除
Ctrl-D or DELETE	カーソルの右1文字を削除
Ctrl-W	カーソルの左1ワードを削除
Ctrl-J	カーソルの左行頭までを削除
Ctrl-K	カーソルの右行末までを削除
Ctrl-M or ENTER	カーソル位置に改行を挿入

その他の操作

その他の操作です．複数ファイル開いている場合は Ctrl-Z/Ctrl-X で編集するファイルを切り替えます．

キーマップ	説明
Ctrl-?	キーマップ一覧を表示します
Ctrl-Q	エディタを終了します．保存していない変更がある場合は確認のため2回入力する必要があります
Ctrl-S	編集中のテキストをファイルに保存します．無名バッファの場合はファイル名を入力するためのプロンプトが出ます
Ctrl-G	インクリメンタル単純テキスト検索を開始します
Ctrl-O	新たにファイルを開くか，空のバッファを開きます
Ctrl-X	次のファイルを表示します
Alt-X	前のファイルを表示します
Ctrl-L	画面を再描画します（万一描画が壊れた時用）

カラースキームと構文ハイライト

現時点では，カラースキームは gruvbox 固定です．お使いのターミナルが 24-bit 色（true color）対応ならそれを使い，使えなければ 256 色に，それもダメなら 16 色に自動でフォールバックします．

• 24-bit 色

• 256 色

• 16 色

構文ハイライトは下記のものに簡易に対応しています．単純なパターンに基づいてハイライトします．

• 組み込み型
• 制御構文 (if, while など）
• その他キーワード
• 数値リテラル（2進&16進整数対応）
• 文字列リテラル
• 文字リテラル
• コメント

ベース実装

実装は今時点で全部で3000行ほどです．

Write Your Own Text Editor

Build Your Own Text Editor というチュートリアルガイドがあります．これは1000行の C で実装されたミニマルなテキストエディタ kilo をフルスクラッチから実装していく実装解説です．まずはこれに従ってベースになる実装をつくっていきました．

全部で7つのステップがあり，全てのコード追加・修正が解説されています．英語ですが，中身は非常に平穏な解説なので特に困ることはありませんでした．どうしても日本語で読みたい人は非公式に日本語訳されたものもあるようです．

下記のような構成になっていて，一通りやると C っぽいハイライト（16色）と単純テキスト検索を備えた，ファイルを1つだけ編集できる ASCII テキストエディタを C で作成できます．

• Step1: C コンパイラと Makefile のセットアップ
• Step2: ターミナルを canonical モードから raw モードに変更する実装
• Step3: キー入力のハンドリングと空のウィンドウの描画
• Step4: ウィンドウ内でのカーソル移動と指定したファイルの中身をスクロール表示するための画面描画の実装（＋ステータスバー）
• Step5: 行や文字の追加・削除といったテキスト編集機能の実装とファイルへの書き出し実装
• Step6: インクリメンタルな単純テキスト検索の実装
• Step7: 色付きの文字を出力することで構文ハイライトを実装

トータルで1ファイル1000行ほどの C 実装で，git log によるとお盆の暇な時に進めて5日ほどで Step7 まで実装できたようです．

具体的な実装についてはそれぞれのステップを読んでいただければ良いので，ここでは 'Write Your Own Text Editor' を読むとざっくりどんなことが分かるのか紹介します．

ターミナル上で interactive に動く UI の実装

テキストエディタはターミナル上で interactive な UI を提供します．これは一般的なコマンドラインツール（実行すると何か出力が出たり出なかったりしてその後終了する）とはかなり異なっており，ウィンドウ内でカーソルを自由に移動できます．

'Build Your Own Text Editor' では ncurses などのライブラリを使わず，どういう仕組みでこの UI が実装できるのかを知ることができます．

1. termios(3) を使って端末を設定し，インタラクティブな UI を実装するのに邪魔になる入力の echo back や canonical モードを無効にするなどの設定を行います（ターミナル Raw モード）
2. ターミナルとプログラムの間でのやりとり（カーソル移動や特殊キー入力など）は制御シーケンスで標準入出力を介して行います

特に 2. に関しては今までまともに触ったことが無かったので色々勉強になりました．例えば下記のようなものがあります．\x1b は ASCII コード 0x1b エスケープ文字です．

• プログラム → ターミナル に送られる制御シーケンス
  • \x1b[2J: 画面全体をクリアする
  • \x1b[{n}H: カーソルを {n} 行目の行頭に移動する
  • \x1b[K: カーソル位置から行末までをクリアする
• ターミナル → プログラム に送られる制御シーケンス
  • \x1b[C: '←' キー（特殊キー）
  • \x1b[{r};{c}R: カーソル位置レポート．現在のカーソル位置が {r} 行目 {c} 桁目にいることを伝える

例えばターミナルを開いて echo "\e[2J" とすると画面がクリアされるのが分かります．

\x1b[1H を出力して1行目に移動し，\x1b[K を出力して行末までクリアし，その後でテキストを出力することで，1行目を任意のテキストに書き換えることができます． また，標準出力から（矢印キーや Home/End など）特殊キーのシーケンスをパースすることでユーザが特殊キーを入力したことが分かります．

これらの制御シーケンスは VT100 ユーザガイド や Xterm Control Sequences などで仕様を確認することができます．'Build Your Own Text Editor' では主に VT100 で定義されたシーケンスを使います．

なお，Vim で <Tab> と <C-i> や <Esc> キーと <C-[> がなぜ同じキーとして扱われているか，<C-`> がマップできないのかなどの理由も分かります．

ユーザからの入力とターミナルの描画処理を同時に捌く

一般的なプログラムでは stdin からの read はブロッキングです．ですが，テキストエディタで入力でブロッキングしてしまうと，ユーザからの入力を受けていないタイミングでは一切の処理ができなくなってしまいます． そこで，kilo では termios(3) で VTIME をセットすることで100ミリ秒ごとに read をタイムアウトさせることで，ユーザの入力の間にもエディタ側の処理を挟むことができるようにしています．

このタイムアウトは特殊キーなどのターミナルからの制御シーケンスを賢くパースするのにも役立ちます． 例えば \x1b[C という入力が標準入力に来た時，エディタ側からはこれがターミナルから送られたのか，ユーザが ESC, [, C を入力したものなのか区別できません．

ですが，例えば ESC と [ の間に1回タイムアウトが挟まると，これはターミナルが送ったのではなくユーザが送ったのだなと判断して ESC, [, C をそれぞれ普通のキー入力として処理できます．もしこのシーケンスがターミナルから送られたのなら，間に100ミリ秒もの間隔が空くことはありえないからです．

これは主に ESC キーの入力がユーザからなのか，ターミナルの制御シーケンスの一部なのかを判別するのに役立ちます．

テキストエディタのテキストの持ち方

kilo では各行を単純に char * の配列で持っているので，あまり特筆することはありませんが，テキストエディタで編集対象のテキストバッファと表示されるテキストが別に管理されていることが分かります．カーソル位置についても，編集対象のテキスト上での位置とエディタのスクリーンの表示上での位置を分けて管理しています．これは例えばタブ文字など，表示サイズが半角1文字分でない文字に対応するために必須です．

また，UTF-8 対応（後述）で，テキスト上の文字の位置は (1) テキストバッファ上のバイトインデックス，(2) 文字単位で数えたインデックス，(3) スクリーンの表示上の位置，の3種類を管理しなければいけないことが分かりました．

kilo 実装を拡張する

Kiro は kilo からさらに実践的なエディタとして実装を色々拡張しています． かなり色々手を加えて，実装は元の2倍以上になっているのでここでは全てを解説できませんが，その中で面白いと思ったものをいくつか紹介します．

効率的な描画

kilo では実装の簡略化のため，ハイライトの計算と画面の描画を毎回行う実装になっていました．ですが，これは効率的ではありません．実際に10000行ぐらいの C コードを PageDown キーリピートでスクロールすると数千行あたりで処理がカクカクになってしまいました．

そこで，Kiro ではもう少しハイライトの計算範囲と再描画範囲を行単位で絞って必要がある時のみ再描画しています．

例えば，次のような C コードを編集するとします．

int main()
{
    printf("hello\n");
}

ここで hello\n に ! を挿入して hello!\n にしたとします．この時，

• printf より上の行は変わっていないので再描画する必要はありません．一方で，printf の行だけでなく } の行も再描画する必要があります．これは，例えばブロックコメントの /* が挿入された時など，次の行以降のハイライトが変更され再描画が必要になるケースがあるためです
• ハイライトについては，（何かをキャッシュしない限り）頭から順にパースする必要があるため，毎回ファイルの頭から計算し直す必要があります．ただし，スクリーンの下端以降の行は表示されないため，ハイライトの計算は不要なのでそこで処理を打ち切ります

さらに，カーソル移動のみでスクロールが発生しない時など，描画するテキストに一切変更が無いときは描画自体をスキップします．

再描画する範囲の管理など処理が少し煩雑になりますが，画面全体を毎回描画しなおすのに比べるとかなり改善します．

UTF-8 対応

kilo は編集するテキストとして ASCII のみを対象としています．例えば日本語のテキストを編集しようとするとカーソルが行末を突き抜けたり，配列の範囲外にアクセスしてプログラムがクラッシュしたりします．

Kiro では UTF-8 テキストを ASCII テキストと同様に編集できるよう，対応を行いました．これにより，カーソルは1文字ごとに移動でき，バックスペースキーは1文字単位で文字を削除でき，横方向のスクロールでも表示が壊れたりしません．

kilo の「編集対象を ASCII 文字のみにする」というのは非常に強力な前提です．ASCII 文字は1文字1バイト固定なので

• バイトインデックスと文字のインデックスが一致し，s[n] のように添字アクセスすると s の n 文字目に O(1) でアクセスできます

• バイト数と文字数が一致するので，文字列内の文字数は O(1) で分かります

• タブ文字を除く表示可能文字は半角幅で描画できるので，桁位置を別途考慮する必要がありません（タブ文字は kilo では特別扱いされてアドホックに処理されています）

ですが，UTF-8 は1文字のバイトサイズは（一部の特別な文字を除いて）1〜4バイトの可変長です．なので，

• UTF-8 文字列中の N 文字目にアクセスするには，前から順番に文字列をなめていかないといけません
• UTF-8 文字列の文字数を知るには頭から順番に数える必要があります

また，文字によって表示幅が半角1文字になったり2文字分になったりします．

ランダムアクセスや文字数の取得はテキストの編集処理やカーソル移動なので頻繁に行うので，全てを毎回 O(n) で計算するのは効率的ではありません．

そこで，Kiro では必要に応じて文字列中の各文字のバイトインデックスをキャッシュしておくことで，任意の文字のバイトインデックスを O(1) で計算できるようにします．

1行のテキストを表す Row 構造体は以下のような構造になっています

struct Row {
    buffer: String, // 編集対象の生の UTF-8 文字列
    render: String, // 表示用の文字列
    indices: Vec<usize>, // 各文字のバイトインデックスを持つ配列
}

具体的に例を見てみます．今，"Rust🦀良い" という文字列があるとします．

蟹絵文字は4バイト，後ろの2文字はそれぞれ3バイトなので，それぞれのバイトインデックスを indices フィールドに格納しておきます．indices の各要素の添字は文字列中の各文字に対応しており，要素の値はそれぞれの文字のバイトインデックスです．これにより，

let i = 3; // 4文字目にアクセスしたい
let c = self.buffer[self.indices[3]..].chars().next().unwrap(); // O(1) でアクセス

のようにアクセスすることができ，ASCII 文字のときと同じ効率で文字アクセスや文字列サイズの取得が行なえます． インデックスのキャッシュ（self.indices の構築）は表示用文字列 self.render を計算する際に一緒に構築できるので効率的です．

しかし，毎回このインデックスを全ての行でキャッシュするのはメモリ効率が非常に悪いです．char 1文字4バイトのために usize 1つ8バイトを消費しています．

Kiro はプログラムの編集を主に考えてつくられているため，ASCII 以外の文字が登場する行は多くないと想定できます．

そもそも ASCII 文字のみを含んでいる文字列はバイトインデックスと文字のインデックスが一致するためキャッシュをする必要はありません．そこで，self.indices にはキャパシティが 0 の Vec をセットしておきます．

これにより，キャッシュが存在しない（self.indices の長さが 0）ときはそのまま文字インデックスでアクセスし，キャッシュが存在するときは文字インデックスをバイトインデックスに変換する処理を挟んでアクセスすれば良いです．

Vec はキャパシティが 0 の時，ヒープメモリの確保を行わないことが明記されているので，ASCII 文字のみを含む行におけるメモリのオーバーヘッドはわずか 8 (ptr) + 8 (cap) + 8 (len) = 24 バイトで済みます．

24-bit 色（true color）対応

kilo は16色のみをハイライトに使っていますが，最近のモダンなターミナルでは 24-bit 色がサポートされているものも多いです． そこで，24-bit 色のカラーシーケンスを使ってリッチなカラースキーム（今回はレトロな色合いの gruvbox を採用しました）を実装しました．256 色しか使えない Terminal.app のようなターミナルでは 256 色に，万一それも使えない場合は16色にフォールバックするようにしています．

端末に色を伝えるには各色ごとに決められたコントロールシーケンス（カラーシーケンス）を送ります（\x1b は ESC）．詳しくは英語版の Wikipediaに載っています．

• 16 色 → \x1b[{n}m ただし {n} は 30〜37, 90〜97, 40〜47, 100〜107
• 256 色 → \x1b[{n}m 16色と同じシーケンスだが {n} は 0〜255
• 24-bit 色 → foreground は \x1b[38;2;{r};{g};{b}m，background は \x1b[48;2;{r};{g};{b}m

後は端末がどの色数に対応しているかを知る必要があり，下記の方法で知ることができます

• 256 色対応 → terminfo(5) の colors の値が 256
• 24-bit 色 → $COLORTERM 環境変数の値が truecolor

これらのチェックを使って対応している色数を判断し，出力するカラーシーケンスを出し分ければ OK です．

Rust による実装

kilo は「1000行でテキストエディタを実装する」というプロジェクトなので，処理は極力簡潔になるように実装されています． ですが，そういった実装は拡張時やテスト時の足かせになります．そこで，Rust で実装するにあたりいくつかリファクタリングを加えながら実装を行いました．あまり特筆する箇所は無いですが，いくつかポイントを紹介します．

ロジックごとにモジュール分割

kilo は全ての状態を E というグローバル変数に持ち，あらゆるところからそれにアクセスするようなコードになっています．

Kiro ではそれをエディタのロジックごとにモジュールに分割し，モジュール内の構造体に状態を持たせています．

エディタは下記の9つのモジュールからなります．

• editor.rs: エディタ全体のライフサイクル（キー入力を読んでパース→テキストバッファを更新→ハイライトを更新→画面を描画 のループ）を管理する Editor 構造体を export します．1つのファイルごとに1つのテキストバッファを作成し，バッファの切替も管理しています．
• text_buffer.rs: 編集対象のテキストを Vec<Row> として持ち，文字や行の挿入・削除などのテキスト変更処理を管理する TextBuffer 構造体を export します．
• row.rs: 1行のテキストを管理する Row 構造体を export します．Row では編集対象の文字列が TextBuffer に変更された時に表示用の文字列とバイトインデックスを更新します．
• input.rs: ターミナルの設定を管理する StdinRawMode 構造体と，ターミナルからのバイト列の入力をパースしてキー入力や制御シーケンスの列に変換する InputSequences 構造体を export します．
• highlight.rs: 各文字ごとのハイライト情報を持つ Highlighting 構造体を export します．ハイライトの更新が必要かどうかを管理するフラグを持ち，必要な範囲を必要な時にハイライト再計算します．
• screen.rs: TextBuffer を画面に描画する Screen 構造体を export します．どの行から再描画すべきかを管理して，効率的に再描画します．
• ansi_color.rs: ターミナルの対応する色数に応じたカラーシーケンスを生成する AnsiColor 構造体を export します．
• language.rs: 各言語を表す Language enum を export します．ファイルの拡張子から言語を検知するロジックもここで持っています．
• signal.rs: ターミナルのリサイズに必要な SIGWINCH シグナルを補足して Screen に通知するための構造体 SigwinchWatcher を export します．

エラーハンドリングとリソースの解放

kilo ではエラーハンドリングは perror() でメッセージを出して即 exit() で終了する実装でしたが，Kiro では Rust のイディオムに従い，Result と後置 ? で処理しています．

また，kilo では atexit でリソース解放を行っていましたが，Kiro では Drop trait を使って後処理を行っています．特に標準入力を Raw モードに変更し最後に元に戻す StdinRawMode 構造体では Drop と Deref，DerefMut を使い，

struct StdinRawMode {
    stdin: io::Stdin,
    // ...
}

impl StdinRawMode {
    fn new() -> io::Result<StdinRawMode> {
        // ここで termios(3) によりターミナルを Raw モードに設定
        // ...
    }
}

impl Drop for StdinRawMode {
    fn drop(&mut self) {
        // 元の状態に復元
    }
}

impl Deref for StdinRawMode {
    type Target = io::Stdin;
    fn deref(&self) -> &Self::Target {
        &self.stdin
    }
}

impl DerefMut for StdinRawMode {
    fn deref_mut(&mut self) -> &mut Self::Target {
        &mut self.stdin
    }
}

のようにして，元の io::Stdin のように使えるがターミナル設定の変更と復元も行うような実装になっています．

入力と出力の抽象化

pub struct Editor<I, W>
where
    I: Iterator<Item = io::Result<InputSeq>>,
    W: Write,
{
    // ...
}

impl<I, W> Editor<I, W>
where
    I: Iterator<Item = io::Result<InputSeq>>,
    W: Write,
{
    // Initialize Editor struct with given input and output
    pub fn new(input: I, output: W) -> io::Result<Editor<I, W>> {
        // ...
    }
}

エディタの入力はキーシーケンスの列なので，Iterator trait を用いて実際にキーシーケンスを生成する値を抽象化しています．InputSeq はキー入力または制御シーケンスを表しており，io::Result<InputSeq> はシーケンスのパース結果を表しています．

また，エディタの出力はバイト列を書き込む stdout なので，Write trait を用いて書き出す対象の値を抽象化しています．

これらの trait を用いた抽象化はテストを書く時に重要になります．入力と出力をすげ替えられるようになるので，標準入出力から切り離してロジックだけをテストすることができるようになります．

例えば入力については Iterator<Item = io::Result<InputSeq>> を実装したダミーの構造体を用意します．

struct DummyInput(Vec<InputSeq>);

impl Iterator for DummyInput {
    type Item = io::Result<InputSeq>;

    fn next(&mut self) -> Option<Self::Item> {
        if self.0.is_empty() {
            None
        } else {
            Some(Ok(self.0.remove(0)))
        }
    }
}

// Ctrl-Q を1回だけ入力（エディタをすぐ閉じる）
let dummy_input = DummyInput(vec![ InputSeq::ctrl(b'q') ]);

また，出力は何もせずに捨てる処理を Write trait を実装することで実装できます．

struct Discard;

impl Write for Discard {
    fn write(&mut self, buf: &[u8]) -> io::Result<usize> {
        Ok(buf.len())
    }

    fn flush(&mut self) -> io::Result<()> {
        Ok(())
    }
}

これらを使って，下記のようなテストを書けます．

#[test]
fn test_editor_welcome_screen() {
    // ダミーの入出力でエディタインスタンスを生成
    let mut editor = Editor::new(dummy_input, Discard).unwrap();
    // ロジックを実行
    editor.edit().unwrap();
    for line in editor.lines() {
        // 結果の各行をチェック
    }
}

デバッグ

普段 macOS で開発しているので，公式の rust-lldb を使いたいところですが，エディタを起動した後に rust-lldb -p {プロセスID} でアタッチすると Interrupted system call (os error 4) で read が失敗してエディタが終了してしまうのでうまくいきませんでした（要調査）。

今のところは次のように標準エラー出力でプリントデバッグしています．普通に出力を吐いてもエディタがすぐスクリーンを上書きしてしまうので，

cargo run -- 2>log.txt

のようにファイルにデバッグログを吐いておき，

tail -f log.txt

のように tail でファイルの中身を読むことでファイル経由で別のターミナルにログを吐いています．

今後

直近では下記のような実装を考えています

• テストが足りてないのでもっと追加
• undo/redo を実装
• テキスト選択とクリップボードを実装

これくらいあればとりあえずエディタとしてはそこそこ使えるかな…と思ってます．

さらに，今後の課題として

1. テキストエディタのテキストの持ち方として，頻繁な変更に対して効率的なデータ構造が一般に知られています．例えば Rope), Gap Buffer, Piece Table など
2. 現在の適当なパースによるハイライトを，まともなパーサに置き換えます．ただ，普通のパーサではエディタのハイライトの更新頻度的にパフォーマンスが厳しいことが知られていて，その対策として incremental parsing のアルゴリズムが知られています（paper）
3. WebAssembly にビルドして xterm.js でブラウザに描画
4. EditorConfig などのエディタ設定の反映
5. zero width joiner を使った文字の対応
6. マウスサポート

特に 1. と 2. はかなり楽しそうなのでどこかで時間を見つけてやりたいです．

感想

超ミニマルなテキストエディタ kilo と 'Write Your Own Text Editor' チュートリアルによる実装をベースに，UTF-8 テキストエディタ Kiro を実装しました． テキストエディタをフルスクラッチでつくるのは初めてだったので，少しずつテキストエディタっぽくなっていくのがかなり楽しかったです．（編集できるようになるのが Step5 なので少し遅いですが…）

今回の知識を生かして，いつか「ぼくのかんがえたさいきょうのターミナルテキストエディタ」をつくりたいと思ってます．が，実装言語含めて予定は未定です．

ちなみに今回は Rust で実装しましたが，Go で実装するのも楽しそうな題材でした．例えば入力のパースとハイライトの更新と画面への描画を別ゴルーチンが担当して，間を channel でつないでパイプラインにすると，おそらく画面の更新のレスポンスがさらに改善するのではないかとか思いました．興味がある人がもしいれば是非トライしてみてほしいです．

目黒.vim #16 に参加して Vim script に const を実装するパッチを書いた

あいにくの雨でしたが，Meguro.vim #16 に参加しました．

「この雨の中 Vim のもくもく会に来た者たちだ．面構えが違う」 #megurovim

— ドッグ (@Linda_pp) June 15, 2019

目黒.vim は Vim に関したり関しなかったりする作業をするもくもく会で，今回は Vim に :const を追加するパッチを書きました．

github.com

:const コマンドの機能

Vim script では変数を :let で定義・代入します．ですが，

• 新しい変数定義時も代入時も同じ :let を使う
• if などで新しいスコープが作成されない（動的スコープ）

により，意図せず既存の変数を上書きしてしまうケースがあります．

" Define variable
let i = 0

if some_condition
    " In heavily nested or big statements...
    let i = 1 " Unexpectedly using the same name variable
endif

echo i
" => 1 (expected 0)

意図せず変数が上書きされないようにするためのコマンドとして :lockvar があります．他のプラグインなどから勝手に上書きされないようにグローバル変数をロックするのに使われたりはしますが，ローカル変数に使うほどのお手軽さはありませんでした．

• 毎回ロックするのは面倒だし忘れる
• 余分に1コマンド実行するコスト（パースおよび解釈）がかかる

一方，JavaScript では ES2015 から const が追加されました．これは JavaScript の変数定義をレキシカルスコープにし，参照を変更不能にする構文です．

const number = 42;
number = 99;  // TypeError: invalid assignment to const `number'

Vim script でも内部的に :lockvar の実装を使えば，これと似たような実装ができると思い， 変更しない変数の定義に :let の代替として使える :const を実装しました．:let の代わりに :const を使うだけなので，別途 :lockvar を使うのに比べ面倒ではありません．また，変数の定義と同時にロックするので別コマンドで実行するのに比べてコストが遥かに安いです（実際，ただフラグを立てるだけ）．

" Define locked variable
const i = 0

if some_condition
    let i = 1 " Error! `i` is locked
endif

echo i
" => 0 (expected)

リストの分解など複雑な定義式も :let と同様に使えます．

const [a, b, c] = [1, 2, 3]
const [x; xs] = [1, 2, 3]

さらに，:const は安全のため，既存の変数を上書きできないようになっています．もし既存の変数をロックしたい場合は従来どおり :lockvar を使ってください．

let i = 1
const i = 2 " E995 cannot modify existing variable

:const でロックする深さは 1 です（:lockvar 1 相当）．なので例えばリストを定義した時，要素まではロックされません．

const l = [1]
call add(l, 2)
echo l
" => [1, 2]

なぜ再帰的に全ての値をロックする :lockvar! 相当にしないのかというと，

let a = 1
let l = [a]
lockvar! l " 再帰的にロックするので a もロックしてしまう
let a = 2 " エラー！a はロックされているので変更できない

のように意図せず変数をロックしてしまう可能性があるからです．また，ネストが深い辞書やリストをロックすると深さに比例したコストがかかってしまいます．

その他，注意する点は

• その性質上，環境変数（$FOO）やオプション値（&filetype）には :const は使えません（E996）
• :unlockvar で無理やり :const で定義した変数のロックを解除することが可能です
• JavaScript の const はスコープがレキシカルですが，Vim script の :const はスコープがダイナミックのままです
• JavaScript 処理系はコードのパース時に const 定義された変数への再代入を検知してエラーにできますが，Vim スクリプト処理系は素朴なインタープリタなので :const で定義された変数が実際に書き換えられようとするまでエラーになりません

:const コマンドの実装

diff はこちら． src/eval.c に ex_const() を定義し， src/ex_cmds.h に追加したいコマンドを定義して ex_const 関数ポインタを登録しておくと，:const で ex_const() が呼ばれます．

ちなみに新しいコマンドを追加した時は make cmdidxs でコマンド検索表である src/ex_cmdidxs.h を再生成する必要があります．

:const は変数をロックする以外は :let と同じ挙動のため，実装を :let と共有しています．定義した変数をロックするかどうかのフラグを :let の実装関数に追加し，フラグが立っている場合は変数定義時に di_flags の DI_FLAGS_LOCK フラグと di_tv.v_lock の VAR_LOCKED フラグを立てるだけです．複合代入（+= など）や環境変数への代入やオプション変数への代入のパスはフラグが立っているとエラーにします．

テストの作成方法は src/testdir/README.txt に書いてありますが，src/testdir 内に test_const.vim を作成し，src/testdir/Make_all.mak をちょっといじるだけでかなり簡単に実装できます．test_const.vim 内に Test_* な名前の関数を定義しておくと， make test_const でテストが実行できます．

:const コマンドのデバッグ

変数に値をセットする関数 set_var_lval() で，一時的に読み先の文字に NUL をセットしてあとで復帰している部分にエラーチェックを追加した際に復帰処理を追加するのを忘れてエンバグしてしまいました（const [a] = ... の解釈途中で Internal error）．

Vim では標準出力はエディタが使っているので printf() などで出力することは基本的にできません．デバッグ方法は src/README.md に書いてあり，

• デバッグプリントを ch_log() で出しておき，デバッグのための Vim 起動時に :call ch_logfile('log.txt', 'w') のようにしてファイルにデバッグログを吐く．タイミング問題を追う時などに便利
• :packadd termdebug し，:Termdebug で Vim の中で Vim を起動して gdb を使ってデバッグする．Mac で gdb を使うには実行ファイルをコード署名する必要があり若干面倒ですが，大変便利です

vim/vim へのプルリク

ドキュメントを書いて，パッチを GitHub の vim/vim リポジトリにプルリクします．

github.com

新機能の実装の場合，取り込まれるかどうかは作者の Bram さん次第なのでどうかなと思ったのですが，サクッとマージしてもらえました（Vim では変更をパッチとして取り込むので，GitHub のマージ機能を使っていません）．Bram さんは普段 JavaScript や TypeScript を書くらしく，同じことを考えたことがあったらしいです．Vim script の新機能を Bram さんに説明したいときは JavaScript を引き合いに出すと良いのかもしれません．

あまりに速くマージされたので，いくつか細かいミスに後から気付き追加のパッチを送りました．

github.com