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 it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 Bash is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License along
  18 with Bash; see the file COPYING.  If not, write to the Free Software
  19 Foundation, 59 Temple Place, Suite 330, Boston, MA 02111 USA. */
  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 #ifndef _MINIX
  34 #include <sys/param.h>
  35 #endif
  36
  37 #include <stdio.h>
  38
  39 #include <bashansi.h>
  40 #include <maxpath.h>
  41
  42 static int mindist (), spdist ();
  43
  44 /*
  45  * `spname' and its helpers are inspired by the code in "The UNIX
  46  * Programming Environment", Kernighan & Pike, Prentice-Hall 1984,
  47  * pages 209 - 213.
  48  */
  49
  50 /*
  51  *      `spname' -- return a correctly spelled filename
  52  *
  53  *      int spname(char * oldname, char * newname)
  54  *      Returns:  -1 if no reasonable match found
  55  *                 0 if exact match found
  56  *                 1 if corrected
  57  *      Stores corrected name in `newname'.
  58  */
  59 int
  60 spname(oldname, newname)
  61      char *oldname;
  62      char *newname;
  63 {
  64   char *op, *np, *p;
  65   char guess[PATH_MAX + 1], best[PATH_MAX + 1];
  66
  67   op = oldname;
  68   np = newname;
  69   for (;;)
  70     {
  71       while (*op == '/')    /* Skip slashes */
  72         *np++ = *op++;
  73       *np = '\0';
  74
  75       if (*op == '\0')    /* Exact or corrected */
  76         {
  77           /* `.' is rarely the right thing. */
  78           if (oldname[1] == '\0' && newname[1] == '\0' &&
  79                 oldname[0] != '.' && newname[0] == '.')
  80             return -1;
  81           return strcmp(oldname, newname) != 0;
  82         }
  83
  84       /* Copy next component into guess */
  85       for (p = guess; *op != '/' && *op != '\0'; op++)
  86         if (p < guess + PATH_MAX)
  87           *p++ = *op;
  88       *p = '\0';
  89
  90       if (mindist(newname, guess, best) >= 3)
  91         return -1;  /* Hopeless */
  92
  93       /*
  94        *  Add to end of newname
  95        */
  96       for (p = best; *np = *p++; np++)
  97         ;
  98     }
  99 }
 100
 101 /*
 102  *  Search directory for a guess
 103  */
 104 static int
 105 mindist(dir, guess, best)
 106      char *dir;
 107      char *guess;
 108      char *best;
 109 {
 110   DIR *fd;
 111   struct dirent *dp;
 112   int dist, x;
 113
 114   dist = 3;    /* Worst distance */
 115   if (*dir == '\0')
 116     dir = ".";
 117
 118   if ((fd = opendir(dir)) == NULL)
 119     return dist;
 120
 121   while ((dp = readdir(fd)) != NULL)
 122     {
 123       /*
 124        *  Look for a better guess.  If the new guess is as
 125        *  good as the current one, we take it.  This way,
 126        *  any single character match will be a better match
 127        *  than ".".
 128        */
 129       x = spdist(dp->d_name, guess);
 130       if (x <= dist && x != 3)
 131         {
 132           strcpy(best, dp->d_name);
 133           dist = x;
 134           if (dist == 0)    /* Exact match */
 135             break;
 136         }
 137     }
 138   (void)closedir(fd);
 139
 140   /* Don't return `.' */
 141   if (best[0] == '.' && best[1] == '\0')
 142     dist = 3;
 143   return dist;
 144 }
 145
 146 /*
 147  *  `spdist' -- return the "distance" between two names.
 148  *
 149  *  int spname(char * oldname, char * newname)
 150  *  Returns:  0 if strings are identical
 151  *      1 if two characters are transposed
 152  *      2 if one character is wrong, added or deleted
 153  *      3 otherwise
 154  */
 155 static int
 156 spdist(cur, new)
 157      char *cur, *new;
 158 {
 159   while (*cur == *new)
 160     {
 161       if (*cur == '\0')
 162         return 0;    /* Exact match */
 163       cur++;
 164       new++;
 165     }
 166
 167   if (*cur)
 168     {
 169       if (*new)
 170         {
 171           if (cur[1] && new[1] && cur[0] == new[1] && cur[1] == new[0] && strcmp (cur + 2, new + 2) == 0)
 172             return 1;  /* Transposition */
 173
 174           if (strcmp (cur + 1, new + 1) == 0)
 175             return 2;  /* One character mismatch */
 176         }
 177
 178       if (strcmp(&cur[1], &new[0]) == 0)
 179         return 2;    /* Extra character */
 180     }
 181
 182   if (*new && strcmp(cur, new + 1) == 0)
 183     return 2;      /* Missing character */
 184
 185   return 3;
 186 }