疑問
Gitを使っていると時々コマンドを入力し損ねたまま実行してしまうことがあります。
この時、Gitは親切にも近い名前のコマンドを列挙してくれます:
$ git clone git@github.com:git/git.git
$ cd git
$ git grep -n 'Did you mean' -- '*.c'
help.c:385: Q_("\nDid you mean this?",
help.c:386: "\nDid you mean one of these?",
help.c:444: Q_("\nDid you mean this?",
help.c:445: "\nDid you mean one of these?",
sha1_name.c:1234: "Did you mean '%.*s:%s' aka '%.*s:./%s'?",
sha1_name.c:1271: "Did you mean ':%d:%s'?",
sha1_name.c:1289: "Did you mean ':%d:%s' aka ':%d:./%s'?",これは一体どのように実装されているのでしょうか。
調査
手始めに
まずはGitのソースコードを問題のメッセージでgrepしてみましょう:
$ git clone git@github.com:git/git.git
$ cd git
$ git grep -n 'Did you mean' -- '*.c'
help.c:385: Q_("\nDid you mean this?",
help.c:386: "\nDid you mean one of these?",
help.c:444: Q_("\nDid you mean this?",
help.c:445: "\nDid you mean one of these?",
sha1_name.c:1234: "Did you mean '%.*s:%s' aka '%.*s:./%s'?",
sha1_name.c:1271: "Did you mean ':%d:%s'?",
sha1_name.c:1289: "Did you mean ':%d:%s' aka ':%d:./%s'?",このうちhelp.cの385-386行目が help_unknown_cmd という関数の中なので、これを見れば十分そうです。
385-386行目の周辺は以下のコードになっています:
fprintf_ln(stderr, _("git: '%s' is not a git command. See 'git --help'."), cmd);
if (SIMILAR_ENOUGH(best_similarity)) {
fprintf_ln(stderr,
Q_("\nDid you mean this?",
"\nDid you mean one of these?",
n));
for (i = 0; i < n; i++)
fprintf(stderr, "\t%s\n", main_cmds.names[i]->name);
}best_similarity は入力されたコマンドと実在する各コマンドの近似度で最も良い値のようです。main_cmds は……名前からすると組み込みのコマンド名の一覧のようですが、
このコードを見る限りではエイリアス等も含めた全てのコマンド名が含まれているようです。
この時点で若干嫌な予感がします。
利用可能なコマンドの列挙
ではこの関数の先頭の方を確認してみましょう:
const char *help_unknown_cmd(const char *cmd)
{
int i, n, best_similarity = 0;
struct cmdnames main_cmds, other_cmds;
memset(&main_cmds, 0, sizeof(main_cmds));
memset(&other_cmds, 0, sizeof(other_cmds));
memset(&aliases, 0, sizeof(aliases));
git_config(git_unknown_cmd_config, NULL);
load_command_list("git-", &main_cmds, &other_cmds);
add_cmd_list(&main_cmds, &aliases);
add_cmd_list(&main_cmds, &other_cmds);
qsort(main_cmds.names, main_cmds.cnt,
sizeof(main_cmds.names), cmdname_compare);
uniq(&main_cmds);存在するコマンドの名前の一覧を求めているようです。
変数名からすると
main_cmds: Gitの組み込みのコマンドの名前の一覧other_cmds: Gitの組み込みのコマンドではないが、あたかもGitのサブコマンドかのように見えるコマンドの名前の一覧(例えばgit-fooという形式の名前の実行可能ファイルがPATHにあるなら、それはgit fooで実行できる)alias: gitconfig に記載されたエイリアスの名前の一覧
のようですが、
最終的にこの3種類を全て連結して名前順にソートしたものを main_cmds としています。
副作用怖い……!
近似度の算出
き、気を取り直して後続の処理を見てみましょう:
/* This abuses cmdname->len for levenshtein distance */
for (i = 0, n = 0; i < main_cmds.cnt; i++) {
int cmp = 0; /* avoid compiler stupidity */
const char *candidate = main_cmds.names[i]->name;
/*
* An exact match means we have the command, but
* for some reason exec'ing it gave us ENOENT; probably
* it's a bad interpreter in the #! line.
*/
if (!strcmp(candidate, cmd))
die(_(bad_interpreter_advice), cmd, cmd);
/* Does the candidate appear in common_cmds list? */
while (n < ARRAY_SIZE(common_cmds) &&
(cmp = strcmp(common_cmds[n].name, candidate)) < 0)
n++;
if ((n < ARRAY_SIZE(common_cmds)) && !cmp) {
/* Yes, this is one of the common commands */
n++; /* use the entry from common_cmds[] */
if (!prefixcmp(candidate, cmd)) {
/* Give prefix match a very good score */
main_cmds.names[i]->len = 0;
continue;
}
}
main_cmds.names[i]->len =
levenshtein(cmd, candidate, 0, 2, 1, 3) + 1;
}
qsort(main_cmds.names, main_cmds.cnt,
sizeof(*main_cmds.names), levenshtein_compare);
if (!main_cmds.cnt)
die(_("Uh oh. Your system reports no Git commands at all."));何ということでしょう。
/* This abuses cmdname->len for levenshtein distance */と堂々と宣言されてます。ふえええ……まあ宣言されてるだけ良いか……
それに、この方が様々な労力が省かれるのでしょう
(上書きを避けるとなると「コマンド名と編集距離のペア」のリストを作る事になるが、
これをCでやるのは面倒臭いことこの上ない)
で、これは入力されたコマンド(cmd)と利用可能な各コマンド(main_cmds)の近似度を求めて、
各コマンドを近似度でソートしています。
近似度は両者のレーベンシュタイン距離で、
値が小さいほど近い名前という扱いになっています。
ただし、特例があり、
- 入力されたコマンドがよく使われるコマンドのいずれかに近いなら、それを最も近いものとして扱う
(statusのつもりでst等と入力した場合のように、
入力コマンド名が正しいコマンド名のプレフィックスになっている場合のみ「近い」と見做されます)。 - 完全に一致するコマンドが見つかった場合は専用のメッセージを表示して終了する
(入力されたコマンドが見つからなかった場合だけでなく、
見つかったコマンドを実行してみたけれど失敗した場合にもhelp_unknown_cmdが呼ばれるため)。
となっています。
特に前者は候補の一覧をユーザーの期待により近付けるための工夫になっています。
しかし、面白いのは「利用可能なコマンドが一つも存在しなかった」場合の対策処理です。
これは一体どういった経緯で追加されたんでしょうね……
候補の絞り込み
/* skip and count prefix matches */
for (n = 0; n < main_cmds.cnt && !main_cmds.names[n]->len; n++)
; /* still counting */
if (main_cmds.cnt <= n) {
/* prefix matches with everything? that is too ambiguous */
best_similarity = SIMILARITY_FLOOR + 1;
} else {
/* count all the most similar ones */
for (best_similarity = main_cmds.names[n++]->len;
(n < main_cmds.cnt &&
best_similarity == main_cmds.names[n]->len);
n++)
; /* still counting */
}ここでは以下の事が行われています:
- 「入力に対して名前が近い頻出コマンド」と「それ以外で最も名前が近いコマンド」の数を数える(
n)。 - 後者のコマンドにおける近さを
best_similarityとする。
を行っています。
ところで、
「prefix matches with everything? that is too ambiguous」で示されている特別扱いの部分は、
これはどうも実行されることがなさそうなのですが、必要なのでしょうか……
(プレフィックスマッチの対象は common_cmds にあるもののみで、
それは組み込みのコマンドの一覧の部分集合にしかならず、
どう足掻いても main_cmds より少ないはず)
自動補正
if (autocorrect && n == 1 && SIMILAR_ENOUGH(best_similarity)) {
const char *assumed = main_cmds.names[0]->name;
main_cmds.names[0] = NULL;
clean_cmdnames(&main_cmds);
fprintf_ln(stderr,
_("WARNING: You called a Git command named '%s', "
"which does not exist.\n"
"Continuing under the assumption that you meant '%s'"),
cmd, assumed);
if (autocorrect > 0) {
fprintf_ln(stderr, _("in %0.1f seconds automatically..."),
(float)autocorrect/10.0);
poll(NULL, 0, autocorrect * 100);
}
return assumed;
}@help.autocorrect@ が設定されていると、
候補が1個しかなくそれが入力されたコマンド名に十分近いならば自動でコマンドを読み替えて実行してくれます。clean_cmdnames の手前の2行に手動メモリ管理力の高さを感じて息苦しくなりますが、
それ以外は素直なコードになっています。
候補の表示
fprintf_ln(stderr, _("git: '%s' is not a git command. See 'git --help'."), cmd);
if (SIMILAR_ENOUGH(best_similarity)) {
fprintf_ln(stderr,
Q_("\nDid you mean this?",
"\nDid you mean one of these?",
n));
for (i = 0; i < n; i++)
fprintf(stderr, "\t%s\n", main_cmds.names[i]->name);
}
exit(1);最後は候補の表示ですが、これは見ての通りなので特に言うことはありませんね。
感想
「どうせ編集距離の近いものをある程度選んで出しているだけなんでしょ」
と思っていたのですが、
実際には利便性のための工夫が仕込まれていたり、
ありそうもないケースへの対処が含まれていたり、
労力を減らそうという工夫が垣間見られたりして面白かったですね。
どうせならレーベンシュタイン距離の算出関数も読んだら良いと思うのですが、
あれは頭が痛くなるので止めておきます。
次回予告
次回はMercurial編です。
＃人気の記事
＃タグ
