Edited at

shopt -s cdspell を読み解く

More than 1 year has passed since last update.


背景



$ shopt -s cdspell

$ cd /homme
/home

$ pwd
/home

$ cd /vir/lg
/var/log

$ pwd
/var/log



  • この仕組みがふと気になり、Bash のソースを巡ってみた


    • 一体どんなスーパーテクニックが駆使されているのか...ごくり




知りたいこと


  • スペル修正のアルゴリズム


ソースの入手

ver. 4.4 のものが落ちていたのでこれを用いることにする。

http://ftp.gnu.org/gnu/bash/bash-4.4.tar.gz


読解開始


shopt コマンドの探索

手がかりを掴むため、まずは shopt コマンドのソースから見ていく。

ファイル名は builtins/shopt.def であり、ソース内を cdspell で grep してみると 81 行目がヒット。


builtins/shopt.def

81: extern int cdspelling, expand_aliases;


cdspelling という変数が怪しい。


スペル修正処理の大元を探す


cdspelling を頼りに

cdspelling で Bash ソース全体を対象にして検索。

$ grep 'cdspelling' -r ./*

./builtins/cd.def:int cdspelling = 0;
./builtins/cd.def: ((interactive && cdspelling) ? LCD_DOSPELL : 0);
./builtins/shopt.def:extern int cdspelling, expand_aliases;
./builtins/shopt.def: { "cdspell", &cdspelling, (shopt_set_func_t *)NULL },
./builtins/shopt.def: autocd = cdable_vars = cdspelling = 0;

ここでは、cd.def でヒットした2箇所をさらに見ていく。


builtins/cd.def

 69: /* Change this to 1 to get cd spelling correction by default. */

70: int cdspelling = 0;

1箇所目。どうやら cdspelling が 1 だと、スペル修正機能がオンになるらしい。これはまさに shopt -s cdspell したときの挙動っぽい。


builtins/cd.def

256: /* This builtin is ultimately the way that all user-visible commands should

257: change the current working directory. It is called by cd_to_string (),
258: so the programming interface is simple, and it handles errors and
259: restrictions properly. */

260: int
261: cd_builtin (list)
262: WORD_LIST *list;
263: {
:
309: lflag = (cdable_vars ? LCD_DOVARS : 0) |
310: ((interactive && cdspelling) ? LCD_DOSPELL : 0);

2箇所目。cd コマンドの大元の部分のようだ。

この中で cdspelling が作用しているのは 310 行目で、 lflag という変数に影響を与えている。


lflag


builtins/cd.def

260: int

261: cd_builtin (list)
262: WORD_LIST *list;
263: {
:
432: /* If the user requests it, try to find a directory name similar in
433: spelling to the one requested, in case the user made a simple
434: typo. This is similar to the UNIX 8th and 9th Edition shells. */

435: if (lflag & LCD_DOSPELL)
436: {
437: temp = dirspell (dirname);
438: if (temp && change_to_directory (temp, no_symlinks, xattrflag))
439: {
440: printf ("%s\n", temp);
441: free (temp);
442: return (bindpwd (no_symlinks));
443: }
444: else
445: FREE (temp);
446: }

cdspelling が作用した lflag の使いみちを追ってみると、 L.437 で dirspell() を呼んでいた。スペル直してるのめっちゃこれっぽい。


スペル修正のアルゴリズムを追う


スペル修正関数を呼ぶ dirspell()

早速 dirspell の中身を見てみる。


lib/sh/spell.c

190: char *

191: dirspell (dirname)
192: char *dirname;
193: {
194: int n;
195: char *guess;
196:
197: n = (strlen (dirname) * 3 + 1) / 2 + 1;
198: guess = (char *)malloc (n);
199: if (guess == 0)
200: return 0;
201:
202: switch (spname (dirname, guess))
203: {
204: case -1:
205: default:
206: free (guess);
207: return (char *)NULL;
208: case 0:
209: case 1:
210: return guess;
211: }
212: }

L.202 で spname という関数をさらに呼んでいて、どうやら本処理はここで行われているっぽい。


スペル修正の準備を行う spname()


lib/sh/shell.c

 46: /*

47: * `spname' and its helpers are inspired by the code in "The UNIX
48: * Programming Environment", Kernighan & Pike, Prentice-Hall 1984,
49: * pages 209 - 213.
50: */

51
52: /*
53: * `spname' -- return a correctly spelled filename
54: *
55: * int spname(char * oldname, char * newname)
56: * Returns: -1 if no reasonable match found
57: * 0 if exact match found
58: * 1 if corrected
59: * Stores corrected name in `newname'.
60: */

61: int
62: spname(oldname, newname)
63: char *oldname;
64: char *newname;
65: {

まずは spname 関数の冒頭から見ていく。


  • 名著 UNIX プログラミング環境 からインスパイアを得たらしい

  • 戻り値の内訳:


    • -1 良い推測結果を得られなかった

    • 0 そもそも typo してなかった

    • 1 推測結果を得られた




  • oldname (typo したやつ) を修正した結果が newname に格納される

関数の処理内容が以下。カッコでコメントした箇所は筆者によるもの。

 66:   char *op, *np, *p;

67: char guess[PATH_MAX + 1], best[PATH_MAX + 1];
68:
69: op = oldname;
70: np = newname;
71: for (;;)
72: {
73: while (*op == '/') /* Skip slashes */ // ... (1)
74: *np++ = *op++;
75: *np = '\0';
76:
77: if (*op == '\0') /* Exact or corrected */
78: {
79: /* `.' is rarely the right thing. */ // ... (2)
80: if (oldname[1] == '\0' && newname[1] == '\0' &&
81: oldname[0] != '.' && newname[0] == '.')
82: return -1;
83: return strcmp(oldname, newname) != 0;
84: }
85:
86: /* Copy next component into guess */ // ... (3)
87: for (p = guess; *op != '/' && *op != '\0'; op++)
88: if (p < guess + PATH_MAX)
89: *p++ = *op;
90: *p = '\0';
91:
92: if (mindist(newname, guess, best) >= 3) // ... (4)
93: return -1; /* Hopeless */
94:
95: /*
96: * Add to end of newname // ... (5)
97: */

98: for (p = best; *np = *p++; np++)
99: ;
100: }

(1) 冒頭のスラッシュは修正対象としない

(2) 修正処理の結果、末尾がピリオドで終わってしまった場合は「修正失敗」としている

(3) oldname から単一のディレクトリ名 (next component) を抜き出している。これが修正対象となる

  - スラッシュを区切り文字にしていることから、ディレクトリごとに分割して処理しているみたい

  - 抜き出したディレクトリ名のコピー先は作業用ポインタ *p = &guess[0]

(4) mindist() を呼び出し、その返り値が 3 以上であれば匙を投げている (Hopeless)

(5) 修正結果 (best) を newname にコピーしている

まとめると、この関数で行っているのは以下となる。


  • スラッシュで区切られたディレクトリ名の一部を抜き出す

  • 抜き出したディレクトリ名 (guess) を mindist() に渡す


    • 最終的に返却する予定の newname も一緒に渡している



ということで、ここでも行っているのは下準備のみで肝心の修正処理は mindist() の模様。


スペル修正の総本山 mindist()


lib/sh/shell.c

103: /*

104: * Search directory for a guess
105: */

106: static int
107: mindist(dir, guess, best)
108: char *dir;
109: char *guess;
110: char *best;
111: {
112: DIR *fd;
113: struct dirent *dp;
114: int dist, x;
115:
116: dist = 3; /* Worst distance */ // ... (6)
117: if (*dir == '\0')
118: dir = ".";
119:
120: if ((fd = opendir(dir)) == NULL) // ... (7)
121: return dist;
122:
123: while ((dp = readdir(fd)) != NULL) // ... (7)
124: {
125: /*
126: * Look for a better guess. If the new guess is as
127: * good as the current one, we take it. This way,
128: * any single character match will be a better match
129: * than ".".
130: */

131: x = spdist(dp->d_name, guess); // ... (8)
132: if (x <= dist && x != 3)
133: {
134: strcpy(best, dp->d_name); // ... (9)
135: dist = x;
136: if (dist == 0) /* Exact match */
137: break;
138: }
139: }
140: (void)closedir(fd);
141:
142: /* Don't return `.' */ // ... (10)
143: if (best[0] == '.' && best[1] == '\0')
144: dist = 3;
145: return dist;
146: }

(6) 戻り値のデフォルト値 3 (= worst distance) を定義

(7) dir (= newname) のファイル一覧を取得

(8) ファイル一覧を foreach し、ファイルごとに guess との distance を比較 (後述)

(9) distance がこれまでよりも小さい場合は best にファイル名をコピー

(10) best. で終わっている場合は worst distance を返す

例えば、 /var/mail と入力しようとして /var/mil と typo してしまったときの場合を考える。1st component である var は正しいので pass し、2nd component の mil を比較するフェーズを想定すると、引数には以下が入る。



  • *dir = /var


  • *guess = mil

まず、 dir のファイル一覧を取得する。筆者の環境で ls /var したときの結果が以下。

$ ls /var

adm cache db empty games gopher kerberos lib local lock log mail nis opt preserve run spool tmp www yp

次に、得られた結果を上からチョイスして guess の内容と比較する。

「adm と mil」、「cache と mil」、「db と mil」... と比較していくと、じきに「mail と mil」に当たる。これは後述の spdist() によれば distance は 3 未満となるため、best に 'mail' がコピーされる。

その後も「nis と mil」「opt と mil」... と虱潰しに比較していくが、最も distance が小さくなったのは結局 mail だったため、 best には mail が格納される。

ということで、「スペル修正処理」とは「distance が最も小さくなるディレクトリ名から取ってくる」ことだった。なるほど、これは確実だ…

では、distance を一体どのように求めているのか。それが (8) で呼び出されている spdist() に記述されている。


スペル修正するべきかどうかを判定する spdist()


lib/sh/shell.c

148: /*

149: * `spdist' -- return the "distance" between two names.
150: *
151: * int spname(char * oldname, char * newname)
152: * Returns: 0 if strings are identical
153: * 1 if two characters are transposed
154: * 2 if one character is wrong, added or deleted
155: * 3 otherwise
156: */


まずは関数の冒頭部分。戻り値 (= distance) の内訳は以下の通りだった。


  • 0 一致

  • 1 文字が入れ替わっている (ex. homehmoe)

  • 2 文字が追加 or 削除されている (ex. homehomme)

  • 3 上記に該当しない

続いて処理の中身。


lib/sh/shell.c

157: static int

158: spdist(cur, new)
159: char *cur, *new;
160: {
161: while (*cur == *new) // ... (11)
162: {
163: if (*cur == '\0')
164: return 0; /* Exact match */
165: cur++;
166: new++;
167: }
168
169: if (*cur) // ... (12)
170: {
171: if (*new)
172: {
173: if (cur[1] && new[1] && cur[0] == new[1] && cur[1] == new[0] && strcmp (cur + 2, new + 2) == 0)
174: return 1; /* Transposition */
175
176: if (strcmp (cur + 1, new + 1) == 0)
177: return 2; /* One character mismatch */
178: }
179
180: if (strcmp(&cur[1], &new[0]) == 0)
181: return 2; /* Extra character */
182: }
183
184: if (*new && strcmp(cur, new + 1) == 0)
185: return 2; /* Missing character */
186
187: return 3;
188: }

(11) 2 つの文字列を走査し、一致しない文字が登場するまでポインタを移動

  - おさらい: cur には dp->dname すなわち取得したファイル名, new には guess がそれぞれ入る

(12) 一致しなかった理由を地道に調べている。該当しなかった場合は 3 が返る

1文字レベルの typo しか許容していない模様。


まとめ


  • 実在するディレクトリの一覧から、最も typo された文字列に近いものが修正後のディレクトリ名となる

  • typo の程度が大きすぎる (= distance が大きい、2 文字以上の間違いがある) 場合は修正されない