Line data    Source code

       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           0 : spname(oldname, newname)
      63             :      char *oldname;
      64             :      char *newname;
      65             : {
      66           0 :   char *op, *np, *p;
      67           0 :   char guess[PATH_MAX + 1], best[PATH_MAX + 1];
      68             : 
      69           0 :   op = oldname;
      70           0 :   np = newname;
      71             :   for (;;)
      72             :     {
      73           0 :       while (*op == '/')    /* Skip slashes */
      74           0 :         *np++ = *op++;
      75           0 :       *np = '\0';
      76             : 
      77           0 :       if (*op == '\0')    /* Exact or corrected */
      78             :         {
      79             :           /* `.' is rarely the right thing. */
      80           0 :           if (oldname[1] == '\0' && newname[1] == '\0' &&
      81           0 :                 oldname[0] != '.' && newname[0] == '.')
      82             :             return -1;
      83           0 :           return strcmp(oldname, newname) != 0;
      84             :         }
      85             : 
      86             :       /* Copy next component into guess */
      87           0 :       for (p = guess; *op != '/' && *op != '\0'; op++)
      88           0 :         if (p < guess + PATH_MAX)
      89           0 :           *p++ = *op;
      90           0 :       *p = '\0';
      91             : 
      92           0 :       if (mindist(newname, guess, best) >= 3)
      93             :         return -1;  /* Hopeless */
      94             : 
      95             :       /*
      96             :        *  Add to end of newname
      97             :        */
      98           0 :       for (p = best; *np = *p++; np++)
      99           0 :         ;
     100             :     }
     101             : }
     102             : 
     103             : /*
     104             :  *  Search directory for a guess
     105             :  */
     106             : static int
     107           0 : mindist(dir, guess, best)
     108             :      char *dir;
     109             :      char *guess;
     110             :      char *best;
     111             : {
     112           0 :   DIR *fd;
     113           0 :   struct dirent *dp;
     114           0 :   int dist, x;
     115             : 
     116           0 :   dist = 3;    /* Worst distance */
     117           0 :   if (*dir == '\0')
     118           0 :     dir = ".";
     119             : 
     120           0 :   if ((fd = opendir(dir)) == NULL)
     121             :     return dist;
     122             : 
     123           0 :   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           0 :       x = spdist(dp->d_name, guess);
     132           0 :       if (x <= dist && x != 3)
     133             :         {
     134           0 :           strcpy(best, dp->d_name);
     135           0 :           dist = x;
     136           0 :           if (dist == 0)    /* Exact match */
     137             :             break;
     138             :         }
     139             :     }
     140           0 :   (void)closedir(fd);
     141             : 
     142             :   /* Don't return `.' */
     143           0 :   if (best[0] == '.' && best[1] == '\0')
     144           0 :     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           0 : spdist(cur, new)
     159             :      char *cur, *new;
     160             : {
     161           0 :   while (*cur == *new)
     162             :     {
     163           0 :       if (*cur == '\0')
     164             :         return 0;    /* Exact match */
     165           0 :       cur++;
     166           0 :       new++;
     167             :     }
     168             : 
     169           0 :   if (*cur)
     170             :     {
     171           0 :       if (*new)
     172             :         {
     173           0 :           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           0 :           if (strcmp (cur + 1, new + 1) == 0)
     177             :             return 2;  /* One character mismatch */
     178             :         }
     179             : 
     180           0 :       if (strcmp(&cur[1], &new[0]) == 0)
     181             :         return 2;    /* Extra character */
     182             :     }
     183             : 
     184           0 :   if (*new && strcmp(cur, new + 1) == 0)
     185           0 :     return 2;      /* Missing character */
     186             : 
     187             :   return 3;
     188             : }
     189             : 
     190             : char *
     191           0 : dirspell (dirname)
     192             :      char *dirname;
     193             : {
     194           0 :   int n;
     195           0 :   char *guess;
     196             : 
     197           0 :   n = (strlen (dirname) * 3 + 1) / 2 + 1;
     198           0 :   guess = (char *)malloc (n);
     199           0 :   if (guess == 0)
     200             :     return 0;
     201             : 
     202           0 :   switch (spname (dirname, guess))
     203             :     {
     204           0 :     case -1:
     205             :     default:
     206           0 :       free (guess);
     207           0 :       return (char *)NULL;
     208             :     case 0:
     209             :     case 1:
     210             :       return guess;
     211             :     }
     212             : }