lib/sh/spell.c

   1 /* spell.c -- spelling correction for pathnames. */
   2
   3 /* Copyright (C) 2000 Free Software Foundation, Inc.
   4
   5    This file is part of GNU Bash, the Bourne Again SHell.
   6
   7    Bash is free software: you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation, either version 3 of the License, or
  10    (at your option) any later version.
  11
  12    Bash is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with Bash.  If not, see <http://www.gnu.org/licenses/>.
  19 */
  20
  21 #include <config.h>
  22
  23 #if defined (HAVE_UNISTD_H)
  24 #  ifdef _MINIX
  25 #    include <sys/types.h>
  26 #  endif
  27 #  include <unistd.h>
  28 #endif
  29
  30 #include <bashtypes.h>
  31 #include <posixdir.h>
  32 #include <posixstat.h>
  33 #if defined (HAVE_SYS_PARAM_H)
  34 #include <sys/param.h>
  35 #endif
  36
  37 #include <stdio.h>
  38
  39 #include <bashansi.h>
  40 #include <maxpath.h>
  41 #include <stdc.h>
  42
  43 static int mindist __P((char *, char *, char *));
  44 static int spdist __P((char *, char *));
  45
  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 {
  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 */
  74         *np++ = *op++;
  75       *np = '\0';
  76
  77       if (*op == '\0')    /* Exact or corrected */
  78         {
  79           /* `.' is rarely the right thing. */
  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 */
  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)
  93         return -1;  /* Hopeless */
  94
  95       /*
  96        *  Add to end of newname
  97        */
  98       for (p = best; *np = *p++; np++)
  99         ;
 100     }
 101 }
 102
 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 */
 117   if (*dir == '\0')
 118     dir = ".";
 119
 120   if ((fd = opendir(dir)) == NULL)
 121     return dist;
 122
 123   while ((dp = readdir(fd)) != NULL)
 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);
 132       if (x <= dist && x != 3)
 133         {
 134           strcpy(best, dp->d_name);
 135           dist = x;
 136           if (dist == 0)    /* Exact match */
 137             break;
 138         }
 139     }
 140   (void)closedir(fd);
 141
 142   /* Don't return `.' */
 143   if (best[0] == '.' && best[1] == '\0')
 144     dist = 3;
 145   return dist;
 146 }
 147
 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  */
 157 static int
 158 spdist(cur, new)
 159      char *cur, *new;
 160 {
 161   while (*cur == *new)
 162     {
 163       if (*cur == '\0')
 164         return 0;    /* Exact match */
 165       cur++;
 166       new++;
 167     }
 168
 169   if (*cur)
 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 }
 189
 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 }