exit (EXIT_FAILURE);
    }

  if (lstat (".", &sb))
    error (EXIT_FAILURE, errno,
	   _("cannot lstat `.' in %s"), quote (full_filename (".")));

  if (1 < AD_stack_height ())
    {
      /*  Ensure that post-chdir dev/ino match the stored ones.  */
      if ( ! SAME_INODE (sb, top->u.a))
	error (EXIT_FAILURE, 0,
	       _("%s changed dev/ino"), quote (full_filename (".")));
    }

  return dir;
}

/* Initialize *HT if it is NULL.
   Insert FILENAME into HT.  */
static void
AD_mark_helper (Hash_table **ht, char const *filename)
{
  if (*ht == NULL)
    *ht = hash_initialize (HT_UNREMOVABLE_INITIAL_CAPACITY, NULL, hash_pjw,
			   hash_compare_strings, hash_freer);
  if (*ht == NULL)
    xalloc_die ();
  if (! hash_insert (*ht, filename))
    xalloc_die ();
}

/* Mark FILENAME (in current directory) as unremovable.  */
static void
AD_mark_as_unremovable (char const *filename)
{
  AD_mark_helper (&AD_stack_top()->unremovable, xstrdup (filename));
}

/* Mark the current directory as unremovable.  I.e., mark the entry
   in the parent directory corresponding to `.'.
   This happens e.g., when an opendir fails and the only name
   the caller has conveniently at hand is `.'.  */
static void
AD_mark_current_as_unremovable (void)
{
  struct AD_ent *top = AD_stack_top ();
  const char *curr = top_dir ();

  assert (1 < AD_stack_height ());

  --top;
  AD_mark_helper (&top->unremovable, curr);
}

/* Push the initial cwd info onto the stack.
   This will always be the bottommost entry on the stack.  */
static void
AD_push_initial (struct saved_cwd const *cwd)
{
  struct AD_ent *top;

  /* Extend the stack.  */
  obstack_blank (&Active_dir, sizeof (struct AD_ent));

  /* Fill in the new values.  */
  top = AD_stack_top ();
  top->u.saved_cwd = *cwd;
  top->status = RM_OK;
  top->unremovable = NULL;
}

/* Push info about the current working directory (".") onto the
   active directory stack.  DIR is the ./-relative name through
   which we've just `chdir'd to this directory.  DIR_SB_FROM_PARENT
   is the result of calling lstat on DIR from the parent of DIR.  */
static void
AD_push (char const *dir, struct stat const *dir_sb_from_parent)
{
  struct stat sb;
  struct AD_ent *top;

  push_dir (dir);

  if (lstat (".", &sb))
    error (EXIT_FAILURE, errno,
	   _("cannot lstat `.' in %s"), quote (full_filename (".")));

  if ( ! SAME_INODE (sb, *dir_sb_from_parent))
    error (EXIT_FAILURE, errno,
	   _("%s changed dev/ino"), quote (full_filename (".")));

  /* Extend the stack.  */
  obstack_blank (&Active_dir, sizeof (struct AD_ent));

  /* Fill in the new values.  */
  top = AD_stack_top ();
  top->u.a.st_dev = sb.st_dev;
  top->u.a.st_ino = sb.st_ino;
  top->status = RM_OK;
  top->unremovable = NULL;
}

static int
AD_is_removable (char const *file)
{
  struct AD_ent *top = AD_stack_top ();
  return ! (top->unremovable && hash_lookup (top->unremovable, file));
}

static inline bool
is_power_of_two (unsigned int i)
{
  return (i & (i - 1)) == 0;
}

static void
cycle_check (struct stat const *sb)
{
#ifdef ENABLE_CYCLE_CHECK
  /* If there is a directory cycle, detect it (lazily) and die.  */
  static struct dev_ino dir_cycle_detect_dev_ino;
  static unsigned int chdir_counter;

  /* If the current directory ever happens to be the same
     as the one we last recorded for the cycle detection,
     then it's obviously part of a cycle.  */
  if (chdir_counter && SAME_INODE (*sb, dir_cycle_detect_dev_ino))
    {
      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 directory is part of the cycle:\n  %s\n"),
	     quote (full_filename (".")));
      exit (EXIT_FAILURE);
    }

  /* If the number of `descending' chdir calls is a power of two,
     record the dev/ino of the current directory.  */
  if (is_power_of_two (++chdir_counter))
    {
      dir_cycle_detect_dev_ino.st_dev = sb->st_dev;
      dir_cycle_detect_dev_ino.st_ino = sb->st_ino;
    }
#endif
}

static bool
is_empty_dir (char const *dir)
{
  DIR *dirp = opendir (dir);
  if (dirp == NULL)
    {
      closedir (dirp);
      return false;
    }

  while (1)
    {
      struct dirent *dp;
      const char *f;

      errno = 0;
      dp = readdir (dirp);
      if (dp == NULL)
	{
	  closedir (dirp);
	  return errno == 0 ? true : false;
	}

      f = dp->d_name;
      if ( ! DOT_OR_DOTDOT (f))
	{
	  closedir (dirp);
	  return false;
	}
    }
}

/* Prompt whether to remove FILENAME, if required via a combination of
   the options specified by X and/or file attributes.  If the file may
   be removed, return RM_OK.  If the user declines to remove the file,
   return RM_USER_DECLINED.  If not ignoring missing files and we
   cannot lstat FILENAME, then return RM_ERROR.

   Depending on MODE, ask whether to `descend into' or to `remove' the
   directory FILENAME.  MODE is ignored when FILENAME is not a directory.
   Set *IS_EMPTY to T_YES if FILENAME is an empty directory, and it is
   appropriate to try to remove it with rmdir (e.g. recursive mode).
   Don't even try to set *IS_EMPTY when MODE == PA_REMOVE_DIR.
   Set *IS_DIR to T_YES or T_NO if we happen to determine whether
   FILENAME is a directory.  */
static enum RM_status
prompt (char const *filename, struct rm_options const *x,
	enum Prompt_action mode, Ternary *is_dir, Ternary *is_empty)
{
  int write_protected = 0;
  struct stat sbuf, sbuf0;
  int _stat;
  *is_empty = T_UNKNOWN;
  *is_dir = T_UNKNOWN;
  _stat = lstat (filename, &sbuf);

  // Handle the special case of dangling/recursive symlinks - they shouldn't
  // appear write protected.
  write_protected = euidaccess (filename, W_OK);
  if (write_protected && errno == EACCES && S_ISLNK (sbuf.st_mode)
      && stat (filename, &sbuf0))
    write_protected = 0;

  if ((!x->ignore_missing_files && (x->interactive || x->stdin_tty)
       && write_protected)
      || x->interactive)
    {
      if (_stat)
	{
	  /* lstat failed.  This happens e.g., with `rm '''.  */
	  error (0, errno, _("cannot lstat %s"),
		 quote (full_filename (filename)));
	  return RM_ERROR;
	}

      /* Using permissions doesn't make sense for symlinks.  */
      if (S_ISLNK (sbuf.st_mode))
	{
	  if ( ! x->interactive)
	    return RM_OK;
	  write_protected = 0;
	}

      /* Issue the prompt.  */
      {
	char const *quoted_name = quote (full_filename (filename));

	*is_dir = (S_ISDIR (sbuf.st_mode) ? T_YES : T_NO);
	*is_empty = (is_empty_dir (filename) ? T_YES : T_NO);

	/* FIXME: use a variant of error (instead of fprintf) that doesn't
	   append a newline.  Then we won't have to declare program_name in
	   this file.  */
	if (S_ISDIR (sbuf.st_mode)
	    && x->recursive
	    && mode == PA_DESCEND_INTO_DIR
	    && *is_empty == T_NO)
	  fprintf (stderr,
		   (write_protected
		    ? _("%s: descend into write-protected directory %s? ")
		    : _("%s: descend into directory %s? ")),
		   program_name, quoted_name);
	else
	  {
	    /* TRANSLATORS: You may find it more convenient to translate
	       the equivalent of _("%s: remove %s (write-protected) %s? ").
	       It should avoid grammatical problems with the output
	       of file_type.  */
	    fprintf (stderr,
		     (write_protected
		      ? _("%s: remove write-protected %s %s? ")
		      : _("%s: remove %s %s? ")),
		     program_name, file_type (&sbuf), quoted_name);
	  }

	if (!yesno ())
	  return RM_USER_DECLINED;
      }
    }
  return RM_OK;
}

#if HAVE_STRUCT_DIRENT_D_TYPE
# define DT_IS_DIR(D) ((D)->d_type == DT_DIR)
#else
/* Use this only if the member exists -- i.e., don't return 0.  */
# define DT_IS_DIR(D) do_not_use_this_macro
#endif

#define DO_UNLINK(Filename, X)						\
  do									\
    {									\
      if (unlink (Filename) == 0)					\
	{								\
	  if ((X)->verbose)						\
	    printf (_("removed %s\n"), quote (full_filename (Filename))); \
	  return RM_OK;							\
	}								\
									\
      if (errno == ENOENT && (X)->ignore_missing_files)			\
	return RM_OK;							\
    }									\
  while (0)

#define DO_RMDIR(Filename, X)				\
  do							\
    {							\
      if (rmdir (Filename) == 0)			\
	{						\
	  if ((X)->verbose)				\
	    printf (_("removed directory: %s\n"),	\
		    quote (full_filename (Filename)));	\
	  return RM_OK;					\
	}						\
							\
      if (errno == ENOENT && (X)->ignore_missing_files)	\
	return RM_OK;					\
							\
      if (errno == ENOTEMPTY || errno == EEXIST)	\
	return RM_NONEMPTY_DIR;				\
    }							\
  while (0)

/* Remove the file or directory specified by FILENAME.
   Return RM_OK if it is removed, and RM_ERROR or RM_USER_DECLINED if not.
   But if FILENAME specifies a non-empty directory, return RM_NONEMPTY_DIR. */

static enum RM_status
remove_entry (char const *filename, struct rm_options const *x,
	      struct dirent const *dp)
{
  Ternary is_dir;
  Ternary is_empty_directory;
  enum RM_status s = prompt (filename, x, PA_DESCEND_INTO_DIR,
			     &is_dir, &is_empty_directory);

  if (s != RM_OK)
    return s;

  /* Why bother with the following #if/#else block?  Because on systems with
     an unlink function that *can* unlink directories, we must determine the
     type of each entry before removing it.  Otherwise, we'd risk unlinking an
     entire directory tree simply by unlinking a single directory;  then all
     the storage associated with that hierarchy would not be freed until the
     next reboot.  Not nice.  To avoid that, on such slightly losing systems, we
     need to call lstat to determine the type of each entry, and that represents
     extra overhead that -- it turns out -- we can avoid on GNU-libc-based
     systems, since there, unlink will never remove a directory.  */

#if ROOT_CAN_UNLINK_DIRS

  /* If we don't already know whether FILENAME is a directory, find out now.
     Then, if it's a non-directory, we can use unlink on it.  */
  if (is_dir == T_UNKNOWN)
    {
# if HAVE_STRUCT_DIRENT_D_TYPE
      if (dp)
	is_dir = DT_IS_DIR (dp) ? T_YES : T_NO;
      else
# endif
	{
	  struct stat sbuf;
	  if (lstat (filename, &sbuf))
	    {
	      if (errno == ENOENT && x->ignore_missing_files)
		return RM_OK;

	      error (0, errno,
		     _("cannot lstat %s"), quote (full_filename (filename)));
	      return RM_ERROR;
	    }

	  is_dir = S_ISDIR (sbuf.st_mode) ? T_YES : T_NO;
	}
    }

  if (is_dir == T_NO)
    {
      /* At this point, barring race conditions, FILENAME is known
	 to be a non-directory, so it's ok to try to unlink it.  */
      DO_UNLINK (filename, x);

      /* unlink failed with some other error code.  report it.  */