lib/sh/spell.c

/* 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 <http://www.gnu.org/licenses/>.
*/

#include <config.h>

#if defined (HAVE_UNISTD_H)
#  ifdef _MINIX
#    include <sys/types.h>
#  endif
#  include <unistd.h>
#endif

#include <bashtypes.h>
#include <posixdir.h>
#include <posixstat.h>
#if defined (HAVE_SYS_PARAM_H)
#include <sys/param.h>
#endif

#include <stdio.h>

#include <bashansi.h>
#include <maxpath.h>
#include <stdc.h>

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;
    }
}