Go to Qiita Advent Calendar 2024 Top
LoginSignup
3
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@tsubasaogawa(Tsubasa Ogawa)inオープンワーク株式会社

shopt -s cdspell を読み解く

Last updated at Posted at 2018-09-30

背景

例
$ 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 文字以上の間違いがある) 場合は修正されない
3
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
3
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?