git コマンドを typo したとき、正しいコマンドを再実行する CLI ツール reg を Go で書いたのでメモ。
直前に実行したコマンドを取得する
history コマンド
普通にコマンドラインから実行したコマンドの履歴を確認するときは ↑ キーや Ctrl+R で検索したり、 history コマンドで実行してきた過去のコマンド履歴を確認したりする。
Go で外部コマンドを実行するときは os/exec パッケージを用いる。 exec.Command() の引数に実行したいコマンドを指定して Output() や Run() などを呼ぶ。しかし、 history はビルトインコマンドで exec.Command() に直接指定して実行することはできない。 exec.Command() 内では exec.LookPath() で指定された外部コマンドの実行ファイルの場所を探していて、見つからない場合はエラーを返しているが、シェルのビルトインコマンドはその名の通りどこかに実行ファイルとして存在しているわけではない。ビルトインコマンドを実行したい場合は exec.Command("/bin/bash", "-c", command) のように別のシェルを起動してその引数にコマンドを指定する。
今回のケースでは、 CLI ツールが実行されるシェルの一つ前に実行されたコマンドを取得したい。上記の通り exec.Command("/bin/bash", "-c", command) でコマンドを実行すると別のシェルが起動され、そのシェルでコマンドが実行される。履歴を取得したいシェルプロセスとは別のプロセスに対して history コマンドを実行することになり、ほしい結果が取得できない。
history file を参照する
今回は history file の中身から直前に実行されたコマンドを取得することにした。 zsh の場合、シェル変数の HISTFILE に設定されたパスのファイルに実行されたコマンドが書き込まれる。デフォルトでは設定されておらず、ユーザーが .zshrc などで任意のパスを設定できるようになっているため、一意にファイルを特定できない。ここでは ~/.zsh_history に設定されていることを仮定して、というか自分がここに設定しているのでそう決めて進めた。 oh-my-zsh を使っていると ~/.zhistory とからしいが使っていないので知らない。
ファイル内容すべてを読み込む必要はなく終盤だけ読み込むことができればよいので、効率的な tail を考える。ファイルをオープンしたあとに即座に内容を読み込むのではなく、ファイルサイズを別途取得して os.File.ReadAt() で読み込み開始位置をファイル終盤に指定して読み込む。 ~/.zsh_history には実行したかった typo した git コマンドとその後に実行したこの CLI ツールが書き込まれているので、読み込んだデータの末尾から改行文字を確認しながら2個前に実行されたコマンドを取得するようにした。
zsh 以外の場合
開発環境は macOS で、 macOS のデフォルトシェルは zsh なので今回はまず zsh に対応するように作成した。 bash でも history file はあるが、実行されたコマンドの履歴がファイルにフラッシュされるのは、シェルから抜ける（exit）ときか history -a を実行してシェル内部に保存しているコマンド履歴をファイルに追記するとき。前述の通り exec.Command() にはビルトインコマンドを直接指定できないため exec.Command("bin/bash", "-c", "history", "-a") とするしかなく、またこれを実行したとしても別に起動したシェルに対して history -a が実行されるだけでこれは意味がない。
いろいろ調べたが、 CLI ツールの実行は子プロセスとして起動し、子プロセスから親プロセスの bash の history をファイルに書き込むことが難しそうだったので、 bash 対応は断念した。もしかしたらやりようがあるかもしれない。あと、 fish は zsh 同様コマンド実行で即時に history file に書き込まれるので対応できそうだが、使っていないのであまり良く調べていない。
正しいコマンドを推測する
git はサブコマンドを typo したとき、存在しないコマンドであるというエラーの他に、入力された文字列と似ているサブコマンドを探して similar command として出力してくれる。似たようなことを CLI ツールでも実現することで、 history file から取得した直前のコマンドをもとに、実行したかった正しいコマンドを推測して実行する。
レーベンシュタイン距離
ある2つの文字列について一方からもう一方への文字列に変換するまでの最小ステップを計算する処理を考える。この処理について、一方の文字列を typo したコマンド文字列で固定し、もう一方の文字列を正しい git のサブコマンド群から一つずつ選び、最小ステップ計算処理を行う。すべての git サブコマンドについて計算処理を行った結果から、最小の最小ステップ数で変換できるサブコマンドを正しいコマンドと推測する。
上記の処理は文字列の編集距離であるレーベンシュタイン距離の計算アルゴリズムを用いることで実現できる。これはいわゆる動的計画法 DP のアルゴリズムで、2つの文字列の個々の文字ごとに距離を計算して二次元行列を作成することで計算する。アルゴリズムの内容自体はそこまで難しくなく、
- 空文字列からある文字列への編集距離は、ある文字列の個々の文字を追加していくのが最小ステップなので、ある文字列の長さが編集距離になる
- ある文字列 A,B の編集距離を LD(A,B) と表すとき、この値は以下の三通りの最小値（ X-1 は文字列 X の末尾一文字を削除した文字列）
- LD(A-1,B) + 1 (挿入)
- LD(A,B-1) + 1 (削除)
- LD(A-1,B-1) + 1 (置換)
より再帰的に求めることができる。実際は2つの文字列に対して以下のような表を作成するイメージで、最後の右下のセルが結果になる。
| s i t t i n g
--+----------------
| 0 1 2 3 4 5 6 7
k | 1 1 2 3 4 5 6 7
i | 2 2 1 2 3 4 5 6
t | 3 3 2 1 2 3 4 5
t | 4 4 3 2 1 2 3 4
e | 5 5 4 3 2 2 3 4
n | 6 6 5 4 3 3 2 3
余談だが、結構前に2つの文字列の diff を取得するツールを作成したときにこのアルゴリズムを実装した。
ダメラウ・レーベンシュタイン距離
上記レーベンシュタイン距離でも実行したかった正しい git のサブコマンドを推測することは可能だが、 git ではこれを拡張したダメラウ・レーベンシュタイン距離を利用している。これはレーベンシュタイン距離が文字列の編集操作として文字の挿入・削除・置換を認めているのに加え、文字の転置を認めているもの。
置換と転置がどう違うのかというと、このサイトで図示されているのがわかりやすい。隣り合う文字に対して2つの文字列で交差している関係にあれば、置換を2回するのではなく転置を1回することで編集できる。
git では levenshtein.c でこのアルゴリズムが実装されている。挿入・削除・置換・転置の操作それぞれに対して重みを付けられるよう引数が設けられていて、これを利用している箇所でもすべての操作が同じコストではなく重み付けがされている。
おわりに
これで reg の README にあるとおり、 git status を git statu に typo して実行しても、直後に reg を実行すれば git status を実行してくれるようになった。
なお普段は git status を gs に alias しているので使わない模様。「レーベンシュタイン距離」という単語を見て遊びで作ったが、シェルの履歴周り、特に bash の history file 書き込みタイミングなんかは知らなかったので勉強になった。