shopt -s cdspell を読み解く

# 背景

- Bash のオプションを変更する `shopt` というコマンドがある
  - 参考: [shoptコマンドで設定できるbashの便利設定まとめ](https://orebibou.com/2017/04/shopt%E3%82%B3%E3%83%9E%E3%83%B3%E3%83%89%E3%81%A7%E8%A8%AD%E5%AE%9A%E3%81%A7%E3%81%8D%E3%82%8Bbash%E3%81%AE%E4%BE%BF%E5%88%A9%E8%A8%AD%E5%AE%9A%E3%81%BE%E3%81%A8%E3%82%81/)
- 設定項目の一つに `cdspell` というものがあり、`cd` 時に typo したディレクトリ名を自動で直してくれる

```bash:例
$ 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 行目がヒット。

```c:builtins/shopt.def
81: extern int cdspelling, expand_aliases;
```

`cdspelling` という変数が怪しい。

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

### cdspelling を頼りに

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

```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箇所をさらに見ていく。

```c: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` したときの挙動っぽい。

```c: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

```c: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 の中身を見てみる。

```c: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()

```c: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 プログラミング環境](https://www.amazon.co.jp/UNIX%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E7%92%B0%E5%A2%83-Brian-W-Kernighan/dp/4048930575) からインスパイアを得たらしい
- 戻り値の内訳:
  - -1 良い推測結果を得られなかった
  - 0 そもそも typo してなかった
  - 1 推測結果を得られた
- `oldname` (typo したやつ) を修正した結果が `newname` に格納される

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

```c
 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()

```c: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` したときの結果が以下。

```bash
$ 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()

```c: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 上記に該当しない

続いて処理の中身。

```c: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 文字以上の間違いがある) 場合は修正されない