shopt -s cdspell を読み解く

背景

• Bash のオプションを変更する shopt というコマンドがある
  • 参考: shoptコマンドで設定できるbashの便利設定まとめ
• 設定項目の一つに cdspell というものがあり、cd 時に typo したディレクトリ名を自動で直してくれる

例

$ 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. home と hmoe)
• 2 文字が追加 or 削除されている (ex. home と homme)
• 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 文字以上の間違いがある) 場合は修正されない