ターミナル用 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 をベースにしているので，名前は安直に Kiro にしました．
現時点で下記のような機能があります．
- 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 色
構文ハイライトは下記のものに簡易に対応しています．単純なパターンに基づいてハイライトします．
ベース実装
実装は今時点で全部で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 が実装できるのかを知ることができます．
- termios(3) を使って端末を設定し，インタラクティブな UI を実装するのに邪魔になる入力の echo back や canonical モードを無効にするなどの設定を行います（ターミナル Raw モード）
- ターミナルとプログラムの間でのやりとり（カーソル移動や特殊キー入力など）は制御シーケンスで標準入出力を介して行います
特に 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バイトの可変長です．なので，
また，文字によって表示幅が半角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}m16色と同じシーケンスだが{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: 各言語を表すLanguageenum を 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 でファイルの中身を読むことでファイル経由で別のターミナルにログを吐いています．
今後
直近では下記のような実装を考えています
これくらいあればとりあえずエディタとしてはそこそこ使えるかな…と思ってます．
さらに，今後の課題として
- テキストエディタのテキストの持ち方として，頻繁な変更に対して効率的なデータ構造が一般に知られています．例えば Rope), Gap Buffer, Piece Table など
- 現在の適当なパースによるハイライトを，まともなパーサに置き換えます．ただ，普通のパーサではエディタのハイライトの更新頻度的にパフォーマンスが厳しいことが知られていて，その対策として incremental parsing のアルゴリズムが知られています（paper）
- WebAssembly にビルドして xterm.js でブラウザに描画
- EditorConfig などのエディタ設定の反映
- zero width joiner を使った文字の対応
- マウスサポート
特に 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 を追加するパッチを書きました．
: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 リポジトリにプルリクします．
新機能の実装の場合，取り込まれるかどうかは作者の Bram さん次第なのでどうかなと思ったのですが，サクッとマージしてもらえました（Vim では変更をパッチとして取り込むので，GitHub のマージ機能を使っていません）．Bram さんは普段 JavaScript や TypeScript を書くらしく，同じことを考えたことがあったらしいです．Vim script の新機能を Bram さんに説明したいときは JavaScript を引き合いに出すと良いのかもしれません．
あまりに速くマージされたので，いくつか細かいミスに後から気付き追加のパッチを送りました．
Vim on Wasm on Web Worker on Browser with Atomics
この記事は以前の
の続編で，WebAssembly (Wasm) にポーティングした Vim の話です．
TLDR
Wasm にコンパイルした Vim のコードを Web Worker（ワーカスレッド）の中で動かすことで，メインスレッドで行われるユーザのインタラクションをエディタがブロックしなくなりました．
また，イベントループのポーリングを Atomics.wait() でやってキー入力を共有メモリバッファで受け取ることで Emterpreter を捨て，実行速度・安定性・バイナリサイズ・ビルド時間・メンテ性が向上しました．
実装:
これまでの問題点
前回の記事では Vim のコードベースに手を入れて emscripten と binaryen で Wasm にビルドし， <canvas/> に描画する JavaScript ランタイムを整備することでブラウザ上で動く Vim を実現しました．
ポーティングは概ね問題はありませんでしたが，一点 sleep() が Wasm 及び JavaScript では実現できないという問題がありました．
ウェブページでメインスレッドをブロックすることはユーザとのインタラクションをブロックすることを意味します．なので JavaScript では時間がかかる処理はすべて非同期な API として実装され，ブロックできないようになっています．これと同様にメインスレッドで実行される Wasm もスレッドをブロックする機能は提供されていません．
ですが，C プログラムは sleep() を使っているものがあり，Wasm 移植ではこれが問題になることがあります．Vim では GUI フロントエンドが実装する必要がある関数 gui_mch_wait_for_chars() がブロッキングでユーザの入力を待つ処理を要求するため，これに該当しました．
そこで前回の実装では emscripten が提供する Emterpreter という機能を利用して解決しました．Emterpreter は sleep() ができない代わりに emscripten_sleep() などのマジック関数を提供します．これらは C のコードからは sleep() のように同期的に待つ関数のように使えますが，実際は一旦処理を中断して非同期に待つ処理に変換されます．emcc（emscripten の C コンパイラ）は emscripten_sleep() を使っている関数を直接 Wasm にコンパイルせず，Wasm の上で動くインタープリタ (Emterpreter) で実行するためのバイトコードに変換します (emterpretify)．実行時にはそのバイトコードをインタープリタで実行し，emscripten_sleep() の呼び出し箇所で一旦実行状態を保存（suspend）して JavaScript 側の setTimeout() を読んで実行を中断します．タイマーがコールバックを呼んだら Wasm 側に戻り，インタープリタはその中で保存しておいた実行状態を復帰（resume）して実行を再開します．
このような力技により前回はどうにか Vim を動かすことに成功しました．ですが，前回の記事にも書いたように，次の問題が残りました
- Emterpreter で実行される関数は Wasm から直接呼び出すことができません（逆に Emterpreter から Wasm の関数は呼べる）．なので，
emscripten_sleep()を呼んでいる関数を呼んでいる関数，それを呼んでいる関数，... というふうに呼び出し元の関数も Wasm には直接コンパイルできず，Emterpreter のバイトコードにコンパイルする必要があります．Vim でsleep()が必要な関数（gui_mch_wait_for_chars()）は Vim のメインループの一番奥にあたる箇所で呼ばれる関数だったため，それを呼ぶコールスタック上の大量の関数を emterpretify する必要がありました．emterpretify する関数は手動でリスト化して管理する必要があるため，そのリストが膨大になってメンテが大変になりました．しかもこのリストが間違っていて Wasm にコンパイルした関数から emterpretify された関数を呼ぼうとすると実行時にプログラムがクラッシュします - Emterpreter バイトコードへのコンパイルは，同期的な C のコードを非同期なコード（
emscripten_sleep()の呼び出し箇所で処理を切ってコールバックを待つ）に置き換えるため，かなり大きな変換が走ります．そのためコンパイル時間がかなり延びます - Emterpreter バイトコードはかなりシンプルなので，その分バイトコードのバイナリサイズは膨れます
- Emterpreter は試験的な機能なので，かなりバグが多く不安定です．特に JavaScript 側から emterpretify された C の関数を呼ぶ時は不安定で，
char *を渡そうとすると何故かクラッシュしたりします（ccall()の{async: true}がバグっている説）
上記の理由からどうにか Emterpreter を使うのをやめるのが再優先事項でした．
- Sync XHR を使って同期でリクエストを投げ，ServiceWorker で受け取って待ってからレスポンスを返すことでなんとか
sleep()を実現しようとする → Chrome ではバグで動かず，Firefox ではビジーループに近いほど CPU 利用率が上がるためダメ - Vim のメインループ内で
gui_mch_wait_for_chars()を呼ぶ関数をすべて非同期（結果をreturnでなくコールバックで受け取る）に書き換え，emscripten の非同期メインループ機能でメインループを回す → 変換が大変すぎる．10000行ぐらい書き換えてみたところで先が見えないのでメンテが厳しすぎると判断し断念
など試してみましたが，うまくいきませんでした．
今回の実装の改善
Atomics API
emscripten の pthread 対応のコードを呼んでいた時に，JavaScript に同期プリミティブを提供する Atomics API があることを知りました．
その中に Atomics.wait() という futex システムコールのような機能を提供する関数があるのとを見つけました．
The static Atomics.wait() method verifies that a given position in an Int32Array still contains a given value and if so sleeps, awaiting a wakeup or a timeout. It returns a string which is either "ok", "not-equal", or "timed-out".
＿人人人人人人人人＿ ＞ if so sleeps ＜ ￣Y^Y^Y^Y^Y^Y^Y^Y^￣
なんと，無いと思っていた JavaScript の sleep() がこんなところにありました．
ですが，これを呼ぶとスレッドを止めてしまうので，もちろんこれをメインスレッドで呼ぶことはできません．Atomics.wait() はワーカスレッドからつまり Web Worker 内で呼ばなければならないという仕様があります．メインスレッドで呼ぶと待たず即座に例外を投げます．
- メインスレッド（
<script>で読まれるスクリプト）
// 共有メモリバッファをつくり，ワーカスレッド（dedicated Web Worker）を生成して渡す const shared = new SharedArrayBuffer(Int32Array.BYTES_PER_ELEMENT * 4); const buffer = new Int32Array(shared); const worker = new Worker('worker.js'); worker.postMessage(buffer); setTimeout(() => { // 最初の要素に 42 を保存 Atomics.store(buffer, 0, 42); // 最初の要素が変更されたことを別スレッドに通知 Atomics.notify(buffer, 0, 1); }, 3000);
- ワーカスレッド（worker.js）
onmessage = event => { const buffer = event.data; const start = Date.now(); // 5秒タイムアウトで同期的に待つ．この間ワーカスレッドは停止する const result = Atomics.wait(buffer, 0, 5000); console.log('slept', Date.now() - start, 'ms:', result); const val = Atomics.load(buffer, 0); console.log(val); // => 42 };
Vim をワーカスレッドで動かす
Vim をワーカスレッドで動かすにあたって，C 側のコードの修正はまったく必要ありませんでした．emcc は -o vim.js のように出力に JavaScript ファイルを指定すると，自動で WebWorker 内で動かす前提のコードを吐いてくれます．後は new Worker('vim.js') のように読み込めば Wasm ファイル（vim.wasm）を読み込んでくれます．
JavaScript 側はメインスレッドで動かすスクリプトとワーカスレッドで動かすスクリプトに分ける必要があります．
メインスレッド側は
- ワーカスレッドから描画情報を受け取って
<canvas>に描画する処理 - キー入力を受け取って共有バッファに書き，ワーカスレッド側に通知する
- ワーカを生成してスタートする
ワーカスレッド側は
という処理を行います． vim.wasm/wasm/main.ts がメインスレッド側，vim.wasm/wasm/runtime.ts がワーカスレッド側です．
全体の構成のイメージは下図のようになっています．
Wasm 側は Atomics.wait で待っている間停止するので，ワーカスレッド側の onmessage コールバックが発火せず，共有メモリバッファで値をやりとりする必要があります．
逆にワーカスレッドからメインスレッドに値を渡す時は postMessage() で値を渡せます．
キー入力が発生しない時と発生するときの処理のシーケンスは下図のようになっています．
キー入力が発生しない時 (上段，first tick）
- Vim (Wasm) が起動して入力待ち状態になると，最終的に
gui_mch_wait_for_chars()が呼ばれ，その中で JavaScript 側に処理を渡します（vimwasm_wait_for_event()) vimwasm_wait_for_event()内でAtomics.wait()を使って共有メモリへのメインスレッドからの変更通知を同期で待ちます- 今回は通知が来ず，
Atomics.wait()がタイムアウトしました - そのまま
vimwasm_wait_for_event()を抜け，Vim (Wasm) に処理を戻します
キー入力が発生する時 (下段，next tick）
vimwasm_wait_for_event()内でAtomics.wait()を使って共有メモリへのメインスレッドからの変更通知を同期で待ちます- キー入力が発生しました．
KeyEventをメインスレッド側で受け取って共有メモリバッファにキー入力情報（押されたキーの名前やキーコード，モディファイアキー情報など）を書きます - 共有メモリバッファのうちの1バイトを通知用の領域とし，そこに
Atomics.store()でキー入力情報を書いたことを知らせる値を書いてから，ワーカスレッド側にAtomics.notify()を通じて通知します - ワーカスレッド側は
Atomics.wait()で待っておき，通知が来たら共有メモリバッファを見に行ってキー入力情報を得ます - キー入力情報を元に Vim に与えるキーシーケンスを計算し，Vim 側に JavaScript to Wasm API を使って渡します
- Vim (Wasm) は受け取ったシーケンスを入力バッファに加えます
- Vim (Wasm) は入力バッファから入力シーケンスを読んで処理し，結果として描画イベントが発生した時は適宜 JavaScript を通じてメインスレッド側に通知します．メインスレッドは受け取った描画イベントをアニメーションフレームで
<canvas/>に描画します
本当は Atomics.wait() で待つ前や Vim の処理中にキー入力がバッファに書き込まれた場合など考えることが他にもあります．
今回の実装の結果
良くなった点
今回の実装の結果，Emterpreter を使わず，全ての Vim のコードが Wasm にコンパイルされてブラウザ上で動かすことができるようになりました．
メンテ性の向上
emterpretify する関数のリストを持つ必要がなくなり，メンテがしやすくなりました．以前はクラッシュする関数を見つけてはリストを更新する作業があり，upstream に追従した時に削除された関数や追加された関数を反映させないといけなかったのが解消されました
プログラムの安定性が向上
特に，たびたび報告されていた JavaScript 側から emterpretify された C の関数を呼ぶ時にアサーションエラーや不正メモリアクセスエラーがなくなりました．また，文字列（char *）を C 側に渡そうとするとクラッシュする問題が解消されました
バイナリサイズの削減
emterpretify のバイトコードが無くなり全て Wasm になったのと，Emterpreter 本体のコードが必要なくなったので，トータルのバイナリサイズがかなり小さくなりました．gzip 圧縮で，
- Before: 1025.49 KB
- After: 453.308 KB
と半分以下になりました．
ビルド速度
Emterpreter のための変換を行わなくて良くなったため，emcc によるビルド速度が向上しました．
- Before:
emcc 48.25s user 3.55s system 309% cpu 16.745 total
- After:
emcc 4.90s user 0.51s system 112% cpu 4.792 total
数倍速くなってますね．
ユーザとのインタラクション
Vim 本体はワーカスレッドで実行されているため，メインスレッドで処理されるユーザの入力処理（スクロールやキー入力など）を Vim がブロックしないようになりました．
実行速度
以前はユーザの入力を emscripten_sleep() で 10ms ごと polling しながら待っていたため，最大で 10ms の遅延がありました．
また，10ms ごとに Emterpreter の suspend/resume が起きていたため，おそらくそれも実行を遅くしていたと思います（未確認）．
10ms ごとのポーリングをやめ，ユーザからの入力を Atomics.wait() で待つため，メインスレッドから Atomics.notify() されてからの遅延は無くなり，少なくともその分速く実行できるようになりました．（比べないと分からないレベルですが…）
悪くなった点
Chrome （と Chromium ベースのブラウザ）以外ではデフォルトで動かなくなりました．これは Spectre 脆弱性によって SharedArrayBuffer や Atomics API が一時的に多くのブラウザで無効にされているためです．Firefox や Safari ではブラウザのフィーチャフラグを立てることで動かすことができます．
今後
- 今は Web Worker を使っていますが，Wasm のマルチスレッド対応が使えるかもしれないと思っています．同時に
i32.atomic.waitなどのアトミック命令も追加されているので，JavaScript のAtomicsAPI の代わりに使うことで，Wasm と JavaScript 間のインタラクションを無くしてワーカスレッド側の入力待ち処理を Wasm で完結させられるかもしれません - 今は
<canvas/>をメインスレッド側で描画していますが，ワーカスレッド側でキャンバスを描画してメインスレッド側に転送するOffscreenCanvasを使って描画処理をワーカスレッド側に持ってくることができるかもしれません - upstream の追従作業
- 'small' や 'normal' feature でビルドできるようにする
- ファイル保存や読み込み，クリップボード対応など
感想
最初に Atomics API を見た時は JavaScript で非同期処理ライブラリをつくるような人以外は用は無さそうだなと正直思っていたんですが，まさか自分が使うことになるとは思いませんでした…
Emterpreter の動作が不安定すぎる問題で長らく詰まってしまっていたのですが，ようやく次のステップに進めそうで良かったです．
