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