1/* spell.c -- spelling correction for pathnames. */ 2 3/* Copyright (C) 2000 Free Software Foundation, Inc. 4 5This file is part of GNU Bash, the Bourne Again SHell. 6 7Bash is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 2, or (at your option) any later 10version. 11 12Bash is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License along 18with Bash; see the file COPYING. If not, write to the Free Software 19Foundation, 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#include <stdc.h> 42 43static int mindist __P((char *, char *, char *)); 44static 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 */ 61int 62spname(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 */ 106static int 107mindist(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 */ 157static int 158spdist(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