/* spell.c -- spelling correction for pathnames. */
/* Copyright (C) 2000 Free Software Foundation, Inc.
This file is part of GNU Bash, the Bourne Again SHell.
Bash is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
Bash is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with Bash. If not, see .
*/
#include
#if defined (HAVE_UNISTD_H)
# ifdef _MINIX
# include
# endif
# include
#endif
#include
#include
#include
#ifndef _MINIX
#include
#endif
#include
#include
#include
#include
static int mindist __P((char *, char *, char *));
static int spdist __P((char *, char *));
/*
* `spname' and its helpers are inspired by the code in "The UNIX
* Programming Environment", Kernighan & Pike, Prentice-Hall 1984,
* pages 209 - 213.
*/
/*
* `spname' -- return a correctly spelled filename
*
* int spname(char * oldname, char * newname)
* Returns: -1 if no reasonable match found
* 0 if exact match found
* 1 if corrected
* Stores corrected name in `newname'.
*/
int
spname(oldname, newname)
char *oldname;
char *newname;
{
char *op, *np, *p;
char guess[PATH_MAX + 1], best[PATH_MAX + 1];
op = oldname;
np = newname;
for (;;)
{
while (*op == '/') /* Skip slashes */
*np++ = *op++;
*np = '\0';
if (*op == '\0') /* Exact or corrected */
{
/* `.' is rarely the right thing. */
if (oldname[1] == '\0' && newname[1] == '\0' &&
oldname[0] != '.' && newname[0] == '.')
return -1;
return strcmp(oldname, newname) != 0;
}
/* Copy next component into guess */
for (p = guess; *op != '/' && *op != '\0'; op++)
if (p < guess + PATH_MAX)
*p++ = *op;
*p = '\0';
if (mindist(newname, guess, best) >= 3)
return -1; /* Hopeless */
/*
* Add to end of newname
*/
for (p = best; *np = *p++; np++)
;
}
}
/*
* Search directory for a guess
*/
static int
mindist(dir, guess, best)
char *dir;
char *guess;
char *best;
{
DIR *fd;
struct dirent *dp;
int dist, x;
dist = 3; /* Worst distance */
if (*dir == '\0')
dir = ".";
if ((fd = opendir(dir)) == NULL)
return dist;
while ((dp = readdir(fd)) != NULL)
{
/*
* Look for a better guess. If the new guess is as
* good as the current one, we take it. This way,
* any single character match will be a better match
* than ".".
*/
x = spdist(dp->d_name, guess);
if (x <= dist && x != 3)
{
strcpy(best, dp->d_name);
dist = x;
if (dist == 0) /* Exact match */
break;
}
}
(void)closedir(fd);
/* Don't return `.' */
if (best[0] == '.' && best[1] == '\0')
dist = 3;
return dist;
}
/*
* `spdist' -- return the "distance" between two names.
*
* int spname(char * oldname, char * newname)
* Returns: 0 if strings are identical
* 1 if two characters are transposed
* 2 if one character is wrong, added or deleted
* 3 otherwise
*/
static int
spdist(cur, new)
char *cur, *new;
{
while (*cur == *new)
{
if (*cur == '\0')
return 0; /* Exact match */
cur++;
new++;
}
if (*cur)
{
if (*new)
{
if (cur[1] && new[1] && cur[0] == new[1] && cur[1] == new[0] && strcmp (cur + 2, new + 2) == 0)
return 1; /* Transposition */
if (strcmp (cur + 1, new + 1) == 0)
return 2; /* One character mismatch */
}
if (strcmp(&cur[1], &new[0]) == 0)
return 2; /* Extra character */
}
if (*new && strcmp(cur, new + 1) == 0)
return 2; /* Missing character */
return 3;
}
char *
dirspell (dirname)
char *dirname;
{
int n;
char *guess;
n = (strlen (dirname) * 3 + 1) / 2 + 1;
guess = (char *)malloc (n);
if (guess == 0)
return 0;
switch (spname (dirname, guess))
{
case -1:
default:
free (guess);
return (char *)NULL;
case 0:
case 1:
return guess;
}
}