はじめに
みなさんこんにちは。Sansan事業部プロダクト開発部のiOSエンジニア荒川です。
以前はRDBMSの記事*1を寄稿し、好評いただいたこともあり、定期的に車輪の再発明系の記事を書いていこうと思います。
さて本日はタイトルの通り、VimやEmacsに代表されるターミナルで動作するインラインテキストエディタをGoで開発してみました。
ソースコードは以下のリポジトリに置いているため、ぜひ参考にしてください。
完成品
文字だけだとイメージも湧きにくいので、まずは完成品をお見せします。
最低限エディタの動きは出来ている、というレベルの完成度ですね🙏
特徴
- 1000行インラインエディタ
- 文字入力/挿入/削除
- 画面スクロール
- キーボードショートカット
- ファイル読み込み/保存
- Goのコードハイライト機能
実装の方針
今回はただ開発するだけではなく、いくつかのこだわりポイントを持ちながら進めていきました。
1000行以内に抑える
実は今回のエディタ開発のきっかけとなったkiloという素晴らしい入門用のテキストエディタがあります。 kiloは、C言語かつ1000行以内にもかかわらず、コードハイライトや検索をはじめとする多機能なエディタです。
今回はkiloにインスパイアされて開発したエディタなので、1000行以内に抑えようという前提を持って作り始めました。フォーマッタをかけたうえでコメントを除いた1000行以内を目標としています。*2
1000行という単位であれば、エディタに詳しくない人でも頑張れば読み解くことができるため、学習用にも適しているかと思うので是非。
またrhysdさんのRustによるブログ・実装も大変参考になりました。非常にレベルが高いため私の実装など足元にも及びませんが、この場を借りてお礼申し上げます。
外部ライブラリを利用しない
今回は外部ライブラリを一切使用していません。*3
Goは標準ライブラリで十分なほど強力ではありますが、外部ライブラリを利用を許可してしまうと、1000行というレギュレーションであったとしても、際限なく機能を拡張できる可能性が出てきます。なので今回は標準ライブラリだけを利用することとし、1000行でどこまで多機能性を実現できるかというチャレンジとしました。
アルゴリズムやデータ構造にこだわりすぎない
過度な最適化はせずに、パフォーマンス上は非効率だとしてもシンプルなコードを心がけています。何かを0から作る場合、小さくインクリメンタルに開発をし続け、早すぎる最適化は避けることが肝要です。
一方で、今回は単純性を重要視しましたが、高速化や効率化にはコンピュータサイエンスの知識と実装力が求められます。ぜひさらなるチャレンジとして取り組んで行こうと思っています。
実装について
1000行のソースコードすべてを紹介することはできないため、実装の要点をかいつまんで解説します。
エディタに適したデータ構造GapBuffer
入力したテキストをどのようにメモリに保存しておくかという問題は、エディタにおいて最も考慮すべき観点の一つでしょう。最もプリミティブな方法としては文字列を配列もしくは連結リストに保存する、ということを思いつきます。しかし、配列は挿入・削除操作がO(n)であること、連結リストは挿入は早いものの参照がO(n)であることを踏まえる*4と、エディタのデータ構造としては適していない事がわかります。
そこで、いくつかテキストエディタに適したデータ構造を探していたのですが、Emacsでも採用されているGapBuffer（GapTable）というデータ構造を採用することにしました。 おそらく知らない方が多いと思うので、簡単にGapBufferの紹介をさせてください。
GapBufferは挿入操作のときは以下のような動きとなります。ポイントは文字列の間に挿入するときに配列に隙間を開け、その隙間を利用して以降の挿入処理の計算量を減らすことにあります。つまり、文字列の間に文字を挿入したタイミングで隙間を開けるために一度だけコピー処理が走りますが、同位置（＝隙間の端であれば）での新規挿入はO(1)で行うことが出来る*5というものです。これは挿入した位置から連続して文字を入力するという人のエディタの動きに適したデータ構造になっています。
また削除のときも同様に隙間の端であれば無駄なコピー処理を走らせる必要がありません。各要素への参照は当然ながらO(1)です。詳しくは mille/gap_table.goにコードがあるので細かい動きが気になる方はそちらを参考にしてみてください。
その他にもテキストエディタに適したデータ構造としてはRope、PieceTableなどもあるのですが、実装がシンプルだと感じたこともありGapBufferを採用することにしました。
余談ですが、当初は配列で開発をしていました。しかし、せっかくエディタを開発しているのに、データ構造ひとつも語れないようでは面白みにかけたので、ある程度動きが出来てきた段階でGapBufferに切り替えました。*6 ただこの判断は1000行という制約のうえでは微妙でした。例えば、kiloでは検索機能が実装されているのですが、自分の場合はGapBufferの実装が膨らんだゆえに検索機能まで収まりきりませんでした。*7
チャネルを有効活用する
Goにはgoroutine/channelという素晴らしい並列処理用の機構が備わっており、エディタ開発においても大いにその力を発揮してくれたので紹介します。
キーボード入力の受け付け
当然ながらエディタなのでキーボード操作を受け付ける必要があります。 特に画面描画処理中などに別のキー入力があった場合にもキー入力自体は受け付けている必要があるため、キー入力待ち受け用のgoroutineを走らせています。
Goのchannelは排他制御に加えてバッファリングも請け負ってくれるので、キー入力を基本的に取りこぼさないようになっています。
func (e *Editor) readKeys() { buf := make([]byte, 64) for { if n, err := syscall.Read(0, buf); err == nil { b := buf[:n] for { r, n := e.parseKey(b) if n == 0 { break } e.keyChan <- r b = b[n:] } } } }
タイマー処理
以下のように、メッセージバーにはヘルプが表示されていますが、ファイルを保存したときは「Saved!」というメッセージを表示し、数秒後にはもとに戻したいという要望があります。こちらもGoのchannelを利用すれば、非常に簡単に実装することができます。
コードハイライト機能
冒頭の画像で分かるようにGoで開発したエディタということで、Goの予約語と文字列リテラルで表示されるようになっています。
リアルタイムに反映されますが、仕組みはシンプルに操作された行を、操作されるたびに毎回パースし、色付けしているだけです。 このあたりはよりしっかりとしたパース処理を書いたうえで洗練させていきたいと思っています。
また毎回パースするため、大規模ファイルになると少々つらい実装となっておりパフォーマンス上は懸念が大きいですが、小規模であれば上手く動いているようです。
キーボードショートカット機能
以下のキーボードショートカットに対応しています。シンプルに物足りなさはありますが、これも実装するだけのものなのであまり力は入れていません。
| キー | 操作 |
|---|---|
Ctrl-H |
左1文字を削除 |
Ctrl-A |
行の先頭へ移動 |
Ctrl-E |
行の末尾へ移動 |
Ctrl-P |
カーソルを上に1文字移動 |
Ctrl-F |
カーソルを右に1文字移動 |
Ctrl-N |
カーソルを下に1文字移動 |
Ctrl-B |
カーソルを左に1文字移動 |
Ctrl-S |
ファイルの保存 |
Ctrl-C |
編集終了 |
Ctrl-V |
標準エラー出力にデバッグ情報を吐き出す |
今後の課題
今回は1000行というところで機能の拡充にも一定の区切りをつけましたが、以下まで実装できればそれなりにエディタとして利用できるのかな、と思っています。今後は1000行という単位に囚われすぎず引き続き実装を進めていければと思っています。
- マルチバイト対応
- 検索機能
- 置換機能
- Undo/Redo
- コピー/ペースト
その他にもテストを書ける実装にしていかなければ、開発速度が上がらないな、と強く感じます。1000行程度であればなんとかなりますが...
まとめ
さていかがだったでしょうか。車輪の再発明は楽しいですね。個人的にはコンパイラ、エミュレータ、RDBMSに続く再発明でした。
エディタを開発したGoのソースコードを自作エディタで編集できるって夢がありますよね。車輪の再発明はメタいことができるので非常に達成感あるので皆さんもぜひ。
そろそろiOSの記事を書かないといけないという雰囲気を感じるので、次はiOS開発の何かを書こうと思います。
