merge from rm-fix branch

1 files changed, 743 insertions, 346 deletions

diff --git a/src/rm.c b/src/rm.c
index 4f226426f..8302ae4d2 100644
--- a/src/rm.c
+++ b/src/rm.c
@@ -15,15 +15,23 @@
    along with this program; if not, write to the Free Software Foundation,
    Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
 
-/* Written by Paul Rubin, David MacKenzie, and Richard Stallman.  */
+/* Written by Paul Rubin, David MacKenzie, and Richard Stallman.
+   Reworked to use chdir and hash tables by Jim Meyering.  */
 
 #include <config.h>
 #include <stdio.h>
 #include <getopt.h>
 #include <sys/types.h>
+#include <assert.h>
 
+#include "save-cwd.h"
 #include "system.h"
 #include "error.h"
+#include "obstack.h"
+#include "oa-hash.h"
+
+#define obstack_chunk_alloc malloc
+#define obstack_chunk_free free
 
 #ifdef D_INO_IN_DIRENT
 # define D_INO(dp) ((dp)->d_ino)
@@ -32,46 +40,76 @@
 # define D_INO(dp) 1
 #endif
 
-/* An element in a stack of pointers into `pathname'.
-   `pathp' points to where in `pathname' the terminating '\0' goes
-   for this level's directory name.  */
-struct pathstack
+#if !defined (S_ISLNK)
+# define S_ISLNK(Mode) 0
+#endif
+
+#define DOT_OR_DOTDOT(Basename) \
+  (Basename[0] == '.' && (Basename[1] == '\0' \
+			  || (Basename[1] == '.' && Basename[2] == '\0')))
+
+#if defined strdupa
+# define ASSIGN_STRDUPA(DEST, S)		\
+  do { DEST = strdupa(S); } while (0)
+#else
+# define ASSIGN_STRDUPA(DEST, S)		\
+  do						\
+    {						\
+      size_t len_ = strlen (S) + 1;		\
+      char *tmp_dest_ = alloca (len_);		\
+      memcpy (tmp_dest_, (S), len_);		\
+      DEST = tmp_dest_;				\
+    }						\
+  while (0)
+#endif
+
+enum RM_status
+{
+  /* FIXME: describe and explain ordering: `ok' increasing in seriousness. */
+  RM_OK = 2,
+  RM_USER_DECLINED,
+  RM_ERROR
+};
+
+#define VALID_STATUS(S) \
+  ((S) == RM_OK || (S) == RM_USER_DECLINED || (S) == RM_ERROR)
+
+/* Initial capacity of per-directory hash table of entries that have
+   been processed but not been deleted.  */
+#define HT_INITIAL_CAPACITY 13
+
+/* Initial capacity of the active directory hash table.  This table will
+   be resized only for hierarchies more than about 45 levels deep. */
+#define ACTIVE_DIR_INITIAL_CAPACITY 53
+
+struct File_spec
 {
-  struct pathstack *next;
-  char *pathp;
+  char *filename;
+  unsigned int have_filetype_mode:1;
+  unsigned int have_full_mode:1;
+  mode_t mode;
   ino_t inum;
 };
 
+#ifndef STDC_HEADERS
+void free ();
+char *malloc ();
+#endif
+
 char *base_name ();
+int euidaccess ();
 char *stpcpy ();
+char *stpncpy ();
+void strip_trailing_slashes ();
 char *xmalloc ();
 char *xrealloc ();
-int euidaccess ();
 int yesno ();
-void strip_trailing_slashes ();
 
-static int clear_directory __P ((struct stat *statp));
-static int duplicate_entry __P ((struct pathstack *stack, ino_t inum));
-static int remove_dir __P ((struct stat *statp));
-static int remove_file __P ((struct stat *statp));
-static int rm __P ((void));
-static void usage __P ((int status));
+static enum RM_status rm (struct File_spec *fs, int user_specified_name);
 
 /* Name this program was run with.  */
 char *program_name;
 
-/* Linked list of pathnames of directories in progress in recursive rm.
-   The entries actually contain pointers into `pathname'.
-   `pathstack' is the current deepest level.  */
-static struct pathstack *pathstack = NULL;
-
-/* Path of file now being processed; extended as necessary.  */
-static char *pathname;
-
-/* Number of bytes currently allocated for `pathname';
-   made larger when necessary, but never smaller.  */
-static int pnsize;
-
 /* If nonzero, display the name of each file removed.  */
 static int verbose;
 
@@ -98,6 +136,36 @@ static int show_help;
 /* If nonzero, print the version on standard output and exit.  */
 static int show_version;
 
+/* FIXME: describe */
+static struct obstack dir_stack;
+
+/* Stack of lengths of directory names (including trailing slash)
+   appended to dir_stack.  We have to have a separate stack of lengths
+   (rather than just popping back to previous slash) because the first
+   element pushed onto the dir stack may contain slashes.  */
+static struct obstack len_stack;
+
+/* Set of `active' directories from the current command-line parameter
+   to the level in the hierarchy at which files are being removed.
+   A directory is added to the active set when RM begins removing it
+   (or its entries), and it is removed from the set just after RM has
+   finished processing it.
+
+   This is actually a map (not a set), implemented with a hash table.
+   For each active directory, it maps the directory's inode number to the
+   depth of that directory relative to the root of the tree being deleted.
+   A directory specified on the command line has depth zero.
+   This construct is used to detect directory cycles so that RM can warn
+   about them rather than iterating endlessly.  */
+static struct hash_table *active_dir_map;
+
+/* An entry in the active_dir_map.  */
+struct active_dir_ent
+{
+  ino_t inum;
+  unsigned int depth;
+};
+
 static struct option const long_opts[] =
 {
   {"directory", no_argument, &unlink_dirs, 1},
@@ -110,437 +178,766 @@ static struct option const long_opts[] =
   {NULL, 0, NULL, 0}
 };
 
-int
-main (int argc, char **argv)
+static __inline unsigned int
+current_depth (void)
 {
-  int err = 0;
-  int c;
+  return obstack_object_size (&len_stack) / sizeof (size_t);
+}
 
-  program_name = argv[0];
-  setlocale (LC_ALL, "");
-  bindtextdomain (PACKAGE, LOCALEDIR);
-  textdomain (PACKAGE);
+static void
+print_nth_dir (FILE *stream, unsigned int depth)
+{
+  size_t *length = (size_t *) obstack_base (&len_stack);
+  char *dir_name = (char *) obstack_base (&dir_stack);
+  unsigned int sum = 0;
+  unsigned int i;
 
-  verbose = ignore_missing_files = recursive = interactive
-    = unlink_dirs = 0;
-  pnsize = 256;
-  pathname = xmalloc (pnsize);
+  assert (0 <= depth && depth < current_depth ());
 
-  while ((c = getopt_long (argc, argv, "dfirvR", long_opts, NULL)) != -1)
+  for (i = 0; i <= depth; i++)
     {
-      switch (c)
-	{
-	case 0:		/* Long option.  */
-	  break;
-	case 'd':
-	  unlink_dirs = 1;
-	  break;
-	case 'f':
-	  interactive = 0;
-	  ignore_missing_files = 1;
-	  break;
-	case 'i':
-	  interactive = 1;
-	  ignore_missing_files = 0;
-	  break;
-	case 'r':
-	case 'R':
-	  recursive = 1;
-	  break;
-	case 'v':
-	  verbose = 1;
-	  break;
-	default:
-	  usage (1);
-	}
+      sum += length[i];
     }
 
-  if (show_version)
+  fwrite (dir_name, 1, sum, stream);
+}
+
+static __inline struct active_dir_ent *
+make_active_dir_ent (ino_t inum, unsigned int depth)
+{
+  struct active_dir_ent *ent;
+  ent = (struct active_dir_ent *) xmalloc (sizeof *ent);
+  ent->inum = inum;
+  ent->depth = depth;
+  return ent;
+}
+
+static unsigned long
+hash_active_dir_ent_1 (void const *x)
+{
+  struct active_dir_ent const *ade = x;
+  return_INTEGER_HASH_1 (ade->inum);
+}
+
+static unsigned long
+hash_active_dir_ent_2 (void const *x)
+{
+  struct active_dir_ent const *ade = x;
+  return_INTEGER_HASH_2 (ade->inum);
+}
+
+static int
+hash_compare_active_dir_ents (void const *x, void const *y)
+{
+  struct active_dir_ent const *a = x;
+  struct active_dir_ent const *b = y;
+  return_INTEGER_COMPARE (a->inum, b->inum);
+}
+
+static unsigned long
+hash_string_1 (void const *x)
+{
+  return_STRING_HASH_1 (x);
+}
+
+static unsigned long
+hash_string_2 (void const *x)
+{
+  return_STRING_HASH_2 (x);
+}
+
+static int
+hash_compare_strings (void const *x, void const *y)
+{
+  return strcmp (x, y);
+}
+
+static void
+usage (int status)
+{
+  if (status != 0)
+    fprintf (stderr, _("Try `%s --help' for more information.\n"),
+	     program_name);
+  else
     {
-      printf ("rm (%s) %s\n", GNU_PACKAGE, VERSION);
-      exit (0);
+      printf (_("Usage: %s [OPTION]... FILE...\n"), program_name);
+      printf (_("\
+Remove (unlink) the FILE(s).\n\
+\n\
+  -d, --directory       unlink directory, even if non-empty (super-user only)\n\
+  -f, --force           ignore nonexistent files, never prompt\n\
+  -i, --interactive     prompt before any removal\n\
+  -r, -R, --recursive   remove the contents of directories recursively\n\
+  -v, --verbose         explain what is being done\n\
+      --help            display this help and exit\n\
+      --version         output version information and exit\n\
+"));
+      puts (_("\nReport bugs to <fileutils-bugs@gnu.ai.mit.edu>."));
     }
+  exit (status);
+}
 
-  if (show_help)
-    usage (0);
+static __inline void
+push_dir (const char *dir_name)
+{
+  size_t len;
 
-  if (optind == argc)
+  len = strlen (dir_name);
+
+  /* Append the string onto the stack.  */
+  obstack_grow (&dir_stack, dir_name, len);
+
+  /* Append a trailing slash.  */
+  obstack_1grow (&dir_stack, '/');
+
+  /* Add one for the slash.  */
+  ++len;
+
+  /* Push the length (including slash) onto its stack.  */
+  obstack_grow (&len_stack, &len, sizeof (len));
+}
+
+static __inline void
+pop_dir (void)
+{
+  int n_lengths = obstack_object_size (&len_stack) / sizeof (size_t);
+  size_t *length = (size_t *) obstack_base (&len_stack);
+  size_t top_len;
+
+  assert (n_lengths > 0);
+  top_len = length[n_lengths - 1];
+  assert (top_len >= 2);
+
+  /* Pop off the specified length of pathname.  */
+  assert (obstack_object_size (&dir_stack) >= top_len);
+  obstack_blank (&dir_stack, -top_len);
+
+  /* Pop the length stack, too.  */
+  assert (obstack_object_size (&len_stack) >= sizeof (size_t));
+  obstack_blank (&len_stack, -(sizeof (size_t)));
+}
+
+/* Copy the SRC_LEN bytes of data beginning at SRC into the DST_LEN-byte
+   buffer, DST, so that the last source byte is at the end of the destination
+   buffer.  If SRC_LEN is longer than DST_LEN, then set *TRUNCATED to non-zero.
+   Set *RESULT to point to the beginning of (the portion of) the source data
+   in DST.  Return the number of bytes remaining in the destination buffer.  */
+
+static size_t
+right_justify (char *dst, size_t dst_len, const char *src, size_t src_len,
+	       char **result, int *truncated)
+{
+  const char *sp;
+  char *dp;
+
+  if (src_len <= dst_len)
     {
-      if (ignore_missing_files)
-	exit (0);
-      else
-	{
-	  error (0, 0, _("too few arguments"));
-	  usage (1);
-	}
+      sp = src;
+      dp = dst + (dst_len - src_len);
+      *truncated = 0;
+    }
+  else
+    {
+      sp = src + (src_len - dst_len);
+      dp = dst;
+      src_len = dst_len;
+      *truncated = 1;
     }
 
-  stdin_tty = isatty (STDIN_FILENO);
+  memcpy (dp, sp, src_len);
 
-  for (; optind < argc; optind++)
-    {
-      int len;
+  *result = dp;
+  return dst_len - src_len;
+}
 
-      /* Stripping slashes is harmless for rmdir;
-	 if the arg is not a directory, it will fail with ENOTDIR.  */
-      strip_trailing_slashes (argv[optind]);
-      len = strlen (argv[optind]);
-      if (len + 1 > pnsize)
+/* Using the global directory name obstack, create the full path to FILENAME.
+   Return it in sometimes-realloc'd space that should not be freed by the
+   caller.  Realloc as necessary.  If realloc fails, use a static buffer
+   and put as long a suffix in that buffer as possible.  */
+
+static char *
+full_filename (const char *filename)
+{
+  static char *buf = NULL;
+  static size_t n_allocated = 0;
+
+  int dir_len = obstack_object_size (&dir_stack);
+  char *dir_name = (char *) obstack_base (&dir_stack);
+  size_t n_bytes_needed;
+  size_t filename_len;
+
+  filename_len = strlen (filename);
+  n_bytes_needed = dir_len + filename_len + 1;
+
+  if (n_bytes_needed > n_allocated)
+    {
+      /* FIXME: use realloc, not xrealloc.  */
+      /* But be sure realloc accepts NULL first arg.
+	 FIXME: replace with rpl_realloc if not.  */
+      /* This funciton can't use xrealloc.  Otherwise, out-of-memory
+	 errors involving a file name to be expanded here wouldn't ever
+	 be issued.  Use realloc and fall back on using a static buffer
+	 if memory is a problem.  */
+      buf = xrealloc (buf, n_bytes_needed);
+      n_allocated = n_bytes_needed;
+
+      if (buf == NULL)
 	{
-	  free (pathname);
-	  pnsize = 2 * (len + 1);
-	  pathname = xmalloc (pnsize);
+#define SBUF_SIZE 512
+#define ELLIPSES_PREFIX "[...]"
+	  static char static_buf[SBUF_SIZE];
+	  int truncated;
+	  size_t len;
+	  char *p;
+
+	  len = right_justify (static_buf, SBUF_SIZE, filename,
+			       filename_len + 1, &p, &truncated);
+	  right_justify (static_buf, len, dir_name, dir_len, &p, &truncated);
+	  if (truncated)
+	    {
+	      memcpy (static_buf, ELLIPSES_PREFIX,
+		      sizeof (ELLIPSES_PREFIX) - 1);
+	    }
+	  return p;
 	}
-      strcpy (pathname, argv[optind]);
-      err += rm ();
     }
 
-  exit (err > 0);
+  /* Copy directory part, including trailing slash.  */
+  memcpy (buf, dir_name, dir_len);
+
+  /* Append filename part, including trailing zero byte.  */
+  memcpy (buf + dir_len, filename, filename_len + 1);
+
+  assert (strlen (buf) + 1 == n_bytes_needed);
+
+  return buf;
 }
 
-/* Remove file or directory `pathname' after checking appropriate things.
-   Return 0 if `pathname' is removed, 1 if not.  */
+static __inline void
+fspec_init_file (struct File_spec *fs, const char *filename)
+{
+  fs->filename = (char *) filename;
+  fs->have_full_mode = 0;
+  fs->have_filetype_mode = 0;
+}
 
-static int
-rm (void)
+static __inline void
+fspec_init_dp (struct File_spec *fs, struct dirent *dp)
 {
-  struct stat path_stats;
-  char *base = base_name (pathname);
+  fs->filename = dp->d_name;
+  fs->have_full_mode = 0;
+  fs->have_filetype_mode = 0;
+  fs->inum = D_INO (dp);
 
-  if (base[0] == '.' && (base[1] == '\0'
-			     || (base[1] == '.' && base[2] == '\0')))
+#if D_TYPE_IN_DIRENT && defined (DT_UNKNOWN)
+  if (filetype_mode != DT_UNKNOWN)
     {
-      error (0, 0, _("cannot remove `.' or `..'"));
-      return 1;
+      fs->have_filetype_mode = 1;
+      fs->mode = filetype_mode;
     }
+#endif
+}
+
+static __inline int
+fspec_get_full_mode (struct File_spec *fs, mode_t *full_mode)
+{
+  struct stat stat_buf;
 
-  if (lstat (pathname, &path_stats)
-      /* The following or-clause is solely for systems like SunOS 4.1.3
-         with (broken) lstat that interpret a zero-length file name
-	 argument as something meaningful.  For such systems, manually
-	 set errno to ENOENT.  */
-      || (pathname[0] == '\0' && (errno = ENOENT)))
+  if (fs->have_full_mode)
     {
-      if (errno == ENOENT && ignore_missing_files)
-	return 0;
-      error (0, errno, "%s", pathname);
-      return 1;
+      *full_mode = fs->mode;
+      return 0;
     }
 
-  if (S_ISDIR (path_stats.st_mode) && !unlink_dirs)
-    return remove_dir (&path_stats);
+  if (lstat (fs->filename, &stat_buf))
+    return 1;
+
+  fs->have_full_mode = 1;
+  fs->have_filetype_mode = 1;
+  fs->mode = stat_buf.st_mode;
+  fs->inum = stat_buf.st_ino;
+
+  *full_mode = stat_buf.st_mode;
+  return 0;
+}
+
+static __inline int
+fspec_get_filetype_mode (struct File_spec *fs, mode_t *filetype_mode)
+{
+  int fail;
+
+  if (fs->have_filetype_mode)
+    {
+      *filetype_mode = fs->mode;
+      fail = 0;
+    }
   else
-    return remove_file (&path_stats);
+    {
+      fail = fspec_get_full_mode (fs, filetype_mode);
+    }
+
+  return fail;
+}
+
+static __inline mode_t
+fspec_filetype_mode (const struct File_spec *fs)
+{
+  assert (fs->have_filetype_mode);
+  return fs->mode;
+}
+
+/* Recursively remove all of the entries in the current directory.
+   Return an indication of the success of the operation.  */
+
+enum RM_status
+remove_cwd_entries (void)
+{
+  /* NOTE: this is static.  */
+  static DIR *dirp = NULL;
+
+  /* NULL or a malloc'd and initialized hash table of entries in the
+     current directory that have been processed but not removed --
+     due either to an error or to an interactive `no' response.  */
+  struct hash_table *ht = NULL;
+
+  struct dirent *dp;
+  enum RM_status status = RM_OK;
+
+  if (dirp)
+    {
+      if (CLOSEDIR (dirp))
+	{
+	  /* FIXME-someday: but this is actually the previously opened dir.  */
+	  error (0, errno, "%s", full_filename ("."));
+	  status = RM_ERROR;
+	}
+    }
+
+  do
+    {
+      errno = 0;
+      dirp = opendir (".");
+      if (dirp == NULL)
+	{
+	  if (errno != ENOENT || !ignore_missing_files)
+	    {
+	      error (0, errno, "%s", full_filename ("."));
+	      status = RM_ERROR;
+	    }
+	  break;
+	}
+
+      while ((dp = readdir (dirp)) != NULL)
+	{
+	  /* Skip this entry if it's `.' or `..'.  */
+	  if (DOT_OR_DOTDOT (dp->d_name))
+	    continue;
+
+	  /* Skip this entry if it's in the table of ones we've already
+	     processed.  */
+	  if (ht && hash_find_item (ht, (dp)->d_name))
+	    continue;
+
+	  {
+	    struct File_spec fs;
+	    enum RM_status tmp_status;
+	    fspec_init_dp (&fs, dp);
+	    tmp_status = rm (&fs, 0);
+	    /* Update status.  */
+	    if (tmp_status > status)
+	      status = tmp_status;
+	    assert (VALID_STATUS (status));
+	  }
+
+	  /* If this entry was not removed (due either to an error or to
+	     an interactive `no' response), record it in the hash table so
+	     we don't consider it again if we reopen this directory later.  */
+	  if (status != RM_OK)
+	    {
+	      void *old_item;
+	      char *p;
+	      int fail;
+
+	      if (ht == NULL)
+		{
+		  ht = hash_init_table (NULL, HT_INITIAL_CAPACITY, 0, 0,
+					hash_string_1, hash_string_2,
+					hash_compare_strings);
+		  if (ht == NULL)
+		    error (1, 0, _("Memory exhausted"));
+		}
+	      p = xmalloc (NLENGTH (dp) + 1);
+	      stpncpy (p, (dp)->d_name, NLENGTH (dp));
+	      fail = hash_insert_item (ht, p, &old_item);
+	      assert (old_item == NULL);
+	      if (fail)
+		error (1, 0, _("Memory exhausted"));
+	    }
+
+	  if (dirp == NULL)
+	    break;
+	}
+    }
+  while (dirp == NULL);
+
+  if (CLOSEDIR (dirp))
+    {
+      error (0, errno, "%s", full_filename ("."));
+      status = 1;
+    }
+  dirp = NULL;
+
+  if (ht)
+    {
+      hash_free_items (ht);
+      hash_free_table (ht);
+      free (ht);
+    }
+
+  return status;
 }
 
 /* Query the user if appropriate, and if ok try to remove the
-   non-directory `pathname', which STATP contains info about.
-   Return 0 if `pathname' is removed, 1 if not.  */
+   file or directory specified by FS.  Return RM_OK if it is removed,
+   and RM_ERROR or RM_USER_DECLINED if not.
+   FIXME: describe IS_DIR parameter.  */
 
-static int
-remove_file (struct stat *statp)
+static enum RM_status
+remove_file (struct File_spec *fs)
 {
+  int asked = 0;
+  char *pathname = fs->filename;
+
   if (!ignore_missing_files && (interactive || stdin_tty)
-      && euidaccess (pathname, W_OK)
-#ifdef S_ISLNK
-      && !S_ISLNK (statp->st_mode)
-#endif
-      )
+      && euidaccess (pathname, W_OK) )
     {
-      fprintf (stderr, _("%s: remove %s`%s', overriding mode %04o? "),
-	       program_name,
-	       S_ISDIR (statp->st_mode) ? _("directory ") : "",
-	       pathname,
-	       (unsigned int) (statp->st_mode & 07777));
-      if (!yesno ())
-	return 1;
+      if (!S_ISLNK (fspec_filetype_mode (fs)))
+	{
+	  error (0, 0,
+		 (S_ISDIR (fspec_filetype_mode (fs))
+		  ? _("remove write-protected directory `%s'? ")
+		  : _("remove write-protected file `%s'? ")),
+		 full_filename (pathname));
+	  if (!yesno ())
+	    return RM_USER_DECLINED;
+
+	  asked = 1;
+	}
     }
-  else if (interactive)
+
+  if (!asked && interactive)
     {
-      fprintf (stderr, _("%s: remove %s`%s'? "), program_name,
-	       S_ISDIR (statp->st_mode) ? _("directory ") : "",
-	       pathname);
+      error (0, 0,
+	     (S_ISDIR (fspec_filetype_mode (fs))
+	      ? _("remove directory `%s'? ")
+	      : _("remove `%s'? ")),
+	     full_filename (pathname));
       if (!yesno ())
-	return 1;
+	return RM_USER_DECLINED;
     }
 
   if (verbose)
-    printf ("%s\n", pathname);
+    printf ("%s\n", full_filename (pathname));
 
   if (unlink (pathname) && (errno != ENOENT || !ignore_missing_files))
     {
-      error (0, errno, "%s", pathname);
-      return 1;
+      error (0, errno, _("cannot unlink `%s'"), full_filename (pathname));
+      return RM_ERROR;
     }
-  return 0;
+  return RM_OK;
 }
 
-/* If not in recursive mode, print an error message and return 1.
+/* If not in recursive mode, print an error message and return RM_ERROR.
    Otherwise, query the user if appropriate, then try to recursively
    remove directory `pathname', which STATP contains info about.
-   Return 0 if `pathname' is removed, 1 if not.  */
+   Return 0 if `pathname' is removed, 1 if not.
+   FIXME: describe need_save_cwd parameter.  */
 
-static int
-remove_dir (struct stat *statp)
+static enum RM_status
+remove_dir (struct File_spec *fs, int need_save_cwd)
 {
-  int err;
+  enum RM_status status;
+  struct saved_cwd cwd;
+  char *dir_name = fs->filename;
+  const char *fmt = NULL;
 
   if (!recursive)
     {
-      error (0, 0, _("%s: is a directory"), pathname);
-      return 1;
+      error (0, 0, _("%s: is a directory"), full_filename (dir_name));
+      return RM_ERROR;
     }
 
   if (!ignore_missing_files && (interactive || stdin_tty)
-      && euidaccess (pathname, W_OK))
+      && euidaccess (dir_name, W_OK))
     {
-      fprintf (stderr,
-	       _("%s: descend directory `%s', overriding mode %04o? "),
-	       program_name, pathname,
-	       (unsigned int) (statp->st_mode & 07777));
-      if (!yesno ())
-	return 1;
+      fmt = _("directory `%s' is write protected; descend into it anyway? ");
     }
   else if (interactive)
     {
-      fprintf (stderr, _("%s: descend directory `%s'? "),
-	       program_name, pathname);
+      fmt = _("descend into directory `%s'? ");
+    }
+
+  if (fmt)
+    {
+      error (0, 0, fmt, full_filename (dir_name));
       if (!yesno ())
-	return 1;
+	return RM_USER_DECLINED;
     }
 
   if (verbose)
-    printf ("%s\n", pathname);
+    printf ("%s\n", full_filename (dir_name));
+
+  /* Save cwd if needed.  */
+  if (need_save_cwd && save_cwd (&cwd))
+    return RM_ERROR;
+
+  /* Make target directory the current one.  */
+  if (chdir (dir_name) < 0)
+    {
+      error (0, errno, _("cannot change to directory %s"),
+	     full_filename (dir_name));
+      if (need_save_cwd)
+	free_cwd (&cwd);
+      return RM_ERROR;
+    }
+
+  push_dir (dir_name);
 
-  err = clear_directory (statp);
+  /* Save a copy of dir_name.  Otherwise, remove_cwd_entries may clobber
+     dir_name because dir_name is just a pointer to the dir entry's d_name
+     field, and remove_cwd_entries may close the directory.  */
+  ASSIGN_STRDUPA (dir_name, dir_name);
+
+  status = remove_cwd_entries ();
+
+  pop_dir ();
+
+  /* Restore cwd.  */
+  if (need_save_cwd)
+    {
+      if (restore_cwd (&cwd, NULL, NULL))
+	{
+	  free_cwd (&cwd);
+	  return RM_ERROR;
+	}
+      free_cwd (&cwd);
+    }
+  else if (chdir ("..") < 0)
+    {
+      error (0, errno, _("cannot change back to directory %s via `..'"),
+	     full_filename (dir_name));
+      return RM_ERROR;
+    }
 
   if (interactive)
     {
-      if (err)
-	fprintf (stderr, _("%s: remove directory `%s' (might be nonempty)? "),
-		 program_name, pathname);
-      else
-	fprintf (stderr, _("%s: remove directory `%s'? "),
-		 program_name, pathname);
+      error (0, 0, _("remove directory `%s'%s? "), full_filename (dir_name),
+	     (status != RM_OK ? _(" (might be nonempty)") : ""));
       if (!yesno ())
-	return 1;
+	{
+	  return RM_USER_DECLINED;
+	}
     }
 
-  if (rmdir (pathname) && (errno != ENOENT || !ignore_missing_files))
+  if (rmdir (dir_name) && (errno != ENOENT || !ignore_missing_files))
     {
-      error (0, errno, "%s", pathname);
-      return 1;
+      error (0, errno, _("cannot remove directory `%s'"),
+	     full_filename (dir_name));
+      return RM_ERROR;
     }
-  return 0;
+
+  return RM_OK;
 }
 
-/* Read directory `pathname' and remove all of its entries,
-   avoiding use of chdir.
-   On entry, STATP points to the results of stat on `pathname'.
-   Return 0 for success, error count for failure.
-   Upon return, `pathname' will have the same contents as before,
-   but its address might be different; in that case, `pnsize' will
-   be larger, as well.  */
+/* Remove the file or directory specified by FS after checking appropriate
+   things.  Return RM_OK if it is removed, and RM_ERROR or RM_USER_DECLINED
+   if not.  If USER_SPECIFIED_NAME is non-zero, then the name part of FS may
+   be `.', `..', or may contain slashes.  Otherwise, it must be a simple file
+   name (and hence must specify a file in the current directory).  */
 
-static int
-clear_directory (struct stat *statp)
+static enum RM_status
+rm (struct File_spec *fs, int user_specified_name)
 {
-  DIR *dirp;
-  struct dirent *dp;
-  char *name_space;		/* Copy of directory's filenames.  */
-  char *namep;			/* Current entry in `name_space'.  */
-  unsigned name_size;		/* Bytes allocated for `name_space'.  */
-  int name_length;		/* Length of filename in `namep' plus '\0'.  */
-  int pathname_length;		/* Length of `pathname'.  */
-  ino_t *inode_space;		/* Copy of directory's inodes.  */
-  ino_t *inodep;		/* Current entry in `inode_space'.  */
-  unsigned n_inodes_allocated;	/* There is space for this many inodes
-					  in `inode_space'.  */
-  int err = 0;			/* Return status.  */
-  struct pathstack pathframe;	/* New top of stack.  */
-  struct pathstack *pp;		/* Temporary.  */
-
-  name_size = statp->st_size;
-  name_space = (char *) xmalloc (name_size);
-
-  n_inodes_allocated = (statp->st_size + sizeof (ino_t) - 1) / sizeof (ino_t);
-  inode_space = (ino_t *) xmalloc (n_inodes_allocated * sizeof (ino_t));
+  mode_t filetype_mode;
 
-  do
+  if (user_specified_name)
     {
-      namep = name_space;
-      inodep = inode_space;
+      char *base = base_name (fs->filename);
 
-      errno = 0;
-      dirp = opendir (pathname);
-      if (dirp == NULL)
+      if (DOT_OR_DOTDOT (base))
 	{
-	  if (errno != ENOENT || !ignore_missing_files)
-	    {
-	      error (0, errno, "%s", pathname);
-	      err = 1;
-	    }
-	  free (name_space);
-	  free (inode_space);
-	  return err;
+	  error (0, 0, _("cannot remove `.' or `..'"));
+	  return RM_ERROR;
 	}
+    }
 
-      while ((dp = readdir (dirp)) != NULL)
-	{
-	  /* Skip "." and "..".  */
-	  if (dp->d_name[0] != '.'
-	      || (dp->d_name[1] != '\0'
-		  && (dp->d_name[1] != '.' || dp->d_name[2] != '\0')))
-	    {
-	      unsigned size_needed = (namep - name_space) + NLENGTH (dp) + 2;
-
-	      if (size_needed > name_size)
-		{
-		  char *new_name_space;
+  if (fspec_get_filetype_mode (fs, &filetype_mode))
+    {
+      if (ignore_missing_files && errno == ENOENT)
+	return RM_OK;
 
-		  while (size_needed > name_size)
-		    name_size += 1024;
+      error (0, errno, _("cannot remove `%s'"), full_filename (fs->filename));
+      return RM_ERROR;
+    }
 
-		  new_name_space = xrealloc (name_space, name_size);
-		  namep += new_name_space - name_space;
-		  name_space = new_name_space;
-		}
-	      namep = stpcpy (namep, dp->d_name) + 1;
+  if (S_ISDIR (filetype_mode))
+    {
+      int fail;
+      struct active_dir_ent *old_ent;
+
+      /* Insert this directory in the active_dir_map.
+	 If there is already a directory in the map with the same inum,
+	 then there's *probably* a directory cycle.  This test can get
+	 a false positive if two directories have the same inode number
+	 but different device numbers and one directory contains the
+	 other.  But since people don't often try to delete hierarchies
+	 containing mount points, and when they do, duplicate inode
+	 numbers are not that likely, this isn't worth detecting.  */
+      fail = hash_insert_item (active_dir_map,
+			       make_active_dir_ent (fs->inum, current_depth ()),
+			       (void **) &old_ent);
+      if (fail)
+	error (1, 0, _("Memory exhausted"));
+
+      if (old_ent)
+	{
+	  error (0, 0, _("\
+WARNING: Circular directory structure.\n\
+This almost certainly means that you have a corrupted file system.\n\
+NOTIFY YOUR SYSTEM MANAGER.\n\
+The following two directories have the same inode number:\n"));
+	  print_nth_dir (stderr, current_depth ());
+	  fputc ('\n', stderr);
+	  print_nth_dir (stderr, old_ent->depth);
+	  fputc ('\n', stderr);
+	  fflush (stderr);
 
-	      if (inodep == inode_space + n_inodes_allocated)
-		{
-		  ino_t *new_inode_space;
+	  free (old_ent);
 
-		  n_inodes_allocated += 1024;
-		  new_inode_space = (ino_t *) xrealloc (inode_space,
-					n_inodes_allocated * sizeof (ino_t));
-		  inodep += new_inode_space - inode_space;
-		  inode_space = new_inode_space;
-		}
-	      *inodep++ = D_INO (dp);
+	  if (interactive)
+	    {
+	      error (0, 0, _("continue? "));
+	      if (yesno ())
+		return RM_ERROR;
 	    }
+	  exit (1);
 	}
-      *namep = '\0';
-      if (CLOSEDIR (dirp))
-	{
-	  error (0, errno, "%s", pathname);
-	  err = 1;
-	}
+    }
 
-      pathname_length = strlen (pathname);
+  if (!S_ISDIR (filetype_mode) || unlink_dirs)
+    {
+      return remove_file (fs);
+    }
+  else
+    {
+      int need_save_cwd = user_specified_name;
+      enum RM_status status;
+      struct active_dir_ent tmp;
+      struct active_dir_ent *old_ent;
 
-      for (namep = name_space, inodep = inode_space; *namep != '\0';
-	   namep += name_length, inodep++)
-	{
-	  name_length = strlen (namep) + 1;
+      if (need_save_cwd)
+	need_save_cwd = (strchr (fs->filename, '/') != NULL);
 
-	  /* Handle arbitrarily long filenames.  */
-	  if (pathname_length + 1 + name_length > pnsize)
-	    {
-	      char *new_pathname;
-
-	      pnsize = (pathname_length + 1 + name_length) * 2;
-	      new_pathname = xrealloc (pathname, pnsize);
-	      /* Update all pointers in the stack to use the new area.  */
-	      for (pp = pathstack; pp != NULL; pp = pp->next)
-		pp->pathp += new_pathname - pathname;
-	      pathname = new_pathname;
-	    }
+      status = remove_dir (fs, need_save_cwd);
 
-	  /* Add a new frame to the top of the path stack.  */
-	  pathframe.pathp = pathname + pathname_length;
-	  pathframe.inum = *inodep;
-	  pathframe.next = pathstack;
-	  pathstack = &pathframe;
+      /* Remove this directory from the active_dir_map.  */
+      tmp.inum = fs->inum;
+      hash_delete_item (active_dir_map, &tmp, (void **) &old_ent);
+      assert (old_ent != NULL);
+      free (old_ent);
 
-	  /* Append '/' and the filename to current pathname, take care of
-	     the file (which could result in recursive calls), and take
-	     the filename back off.  */
+      return status;
+    }
+}
 
-	  *pathstack->pathp = '/';
-	  strcpy (pathstack->pathp + 1, namep);
+int
+main (int argc, char **argv)
+{
+  int fail = 0;
+  int c;
 
-	  /* If the i-number has already appeared, there's an error.  */
-	  if (duplicate_entry (pathstack->next, pathstack->inum))
-	    err++;
-	  else if (rm ())
-	    err++;
+  program_name = argv[0];
+  setlocale (LC_ALL, "");
+  bindtextdomain (PACKAGE, LOCALEDIR);
+  textdomain (PACKAGE);
 
-	  *pathstack->pathp = '\0';
-	  pathstack = pathstack->next;	/* Pop the stack.  */
+  verbose = ignore_missing_files = recursive = interactive
+    = unlink_dirs = 0;
+
+  while ((c = getopt_long (argc, argv, "dfirvR", long_opts, NULL)) != -1)
+    {
+      switch (c)
+	{
+	case 0:		/* Long option.  */
+	  break;
+	case 'd':
+	  unlink_dirs = 1;
+	  break;
+	case 'f':
+	  interactive = 0;
+	  ignore_missing_files = 1;
+	  break;
+	case 'i':
+	  interactive = 1;
+	  ignore_missing_files = 0;
+	  break;
+	case 'r':
+	case 'R':
+	  recursive = 1;
+	  break;
+	case 'v':
+	  verbose = 1;
+	  break;
+	default:
+	  usage (1);
 	}
     }
-  /* Keep trying while there are still files to remove.  */
-  while (namep > name_space && err == 0);
-
-  free (name_space);
-  free (inode_space);
-  return err;
-}
 
-/* If STACK does not already have an entry with the same i-number as INUM,
-   return 0. Otherwise, ask the user whether to continue;
-   if yes, return 1, and if no, exit.
-   This assumes that no one tries to remove filesystem mount points;
-   doing so could cause duplication of i-numbers that would not indicate
-   a corrupted file system.  */
+  if (show_version)
+    {
+      printf ("rm (%s) %s\n", GNU_PACKAGE, VERSION);
+      exit (0);
+    }
 
-static int
-duplicate_entry (struct pathstack *stack, ino_t inum)
-{
-#ifdef D_INO_IN_DIRENT
-  struct pathstack *p;
+  if (show_help)
+    usage (0);
 
-  for (p = stack; p != NULL; p = p->next)
+  if (optind == argc)
     {
-      if (p->inum == inum)
+      if (ignore_missing_files)
+	exit (0);
+      else
 	{
-	  fprintf (stderr, _("\
-%s: WARNING: Circular directory structure.\n\
-This almost certainly means that you have a corrupted file system.\n\
-NOTIFY YOUR SYSTEM MANAGER.\n\
-Cycle detected:\n\
-%s\n\
-is the same file as\n"), program_name, pathname);
-	  *p->pathp = '\0';	/* Truncate pathname.  */
-	  fprintf (stderr, "%s\n", pathname);
-	  *p->pathp = '/';	/* Put it back.  */
-	  if (interactive)
-	    {
-	      fprintf (stderr, _("%s: continue? "), program_name);
-	      if (!yesno ())
-		exit (1);
-	      return 1;
-	    }
-	  else
-	    exit (1);
+	  error (0, 0, _("too few arguments"));
+	  usage (1);
 	}
     }
-#endif /* D_INO_IN_DIRENT */
-  return 0;
-}
 
-static void
-usage (int status)
-{
-  if (status != 0)
-    fprintf (stderr, _("Try `%s --help' for more information.\n"),
-	     program_name);
-  else
+  stdin_tty = isatty (STDIN_FILENO);
+
+  /* Initialize dir-stack obstacks.  */
+  obstack_init (&dir_stack);
+  obstack_init (&len_stack);
+
+  active_dir_map = hash_init_table (NULL, ACTIVE_DIR_INITIAL_CAPACITY, 0, 0,
+				    hash_active_dir_ent_1,
+				    hash_active_dir_ent_2,
+				    hash_compare_active_dir_ents);
+
+  for (; optind < argc; optind++)
     {
-      printf (_("Usage: %s [OPTION]... FILE...\n"), program_name);
-      printf (_("\
-Remove (unlink) the FILE(s).\n\
-\n\
-  -d, --directory       unlink directory, even if non-empty (super-user only)\n\
-  -f, --force           ignore nonexistent files, never prompt\n\
-  -i, --interactive     prompt before any removal\n\
-  -r, -R, --recursive   remove the contents of directories recursively\n\
-  -v, --verbose         explain what is being done\n\
-      --help            display this help and exit\n\
-      --version         output version information and exit\n\
-"));
-      puts (_("\nReport bugs to <fileutils-bugs@gnu.ai.mit.edu>."));
+      struct File_spec fs;
+      enum RM_status status;
+
+      /* Stripping slashes is harmless for rmdir;
+	 if the arg is not a directory, it will fail with ENOTDIR.  */
+      strip_trailing_slashes (argv[optind]);
+      fspec_init_file (&fs, argv[optind]);
+      status = rm (&fs, 1);
+      assert (VALID_STATUS (status));
+      if (status == RM_ERROR)
+	fail = 1;
     }
-  exit (status);
+
+  exit (fail);
 }