/* remove.c -- core functions for removing files and directories
   Copyright (C) 88, 90, 91, 1994-2002 Free Software Foundation, Inc.

   This program 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 2, or (at your option)
   any later version.

   This program 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 this program; if not, write to the Free Software Foundation,
   Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */

/* Extracted from rm.c and librarified, then rewritten by Jim Meyering.  */

#ifdef _AIX
 #pragma alloca
#endif

#include <config.h>
#include <stdio.h>
#include <sys/types.h>
#include <assert.h>

#include "save-cwd.h"
#include "system.h"
#include "dirname.h"
#include "error.h"
#include "file-type.h"
#include "hash.h"
#include "hash-pjw.h"
#include "obstack.h"
#include "quote.h"
#include "remove.h"

/* Avoid shadowing warnings because these are functions declared
   in dirname.h as well as locals used below.  */
#define dir_name rm_dir_name
#define dir_len rm_dir_len

#define obstack_chunk_alloc malloc
#define obstack_chunk_free free

#ifndef PARAMS
# if defined (__GNUC__) || __STDC__
#  define PARAMS(args) args
# else
#  define PARAMS(args) ()
# endif
#endif

/* FIXME: if possible, use autoconf...  */
#ifdef __GLIBC__
# define ROOT_CAN_UNLINK_DIRS 0
#else
# define ROOT_CAN_UNLINK_DIRS 1
#endif

enum Ternary
  {
    T_UNKNOWN = 2,
    T_NO,
    T_YES
  };
typedef enum Ternary Ternary;

/* The prompt function may be called twice a given directory.
   The first time, we ask whether to descend into it, and the
   second time, we ask whether to remove it.  */
enum Prompt_action
  {
    PA_DESCEND_INTO_DIR = 2,
    PA_REMOVE_DIR
  };

/* On systems with an lstat function that accepts the empty string,
   arrange to make lstat calls go through the wrapper function.  */
#if HAVE_LSTAT_EMPTY_STRING_BUG
int rpl_lstat PARAMS((const char *, struct stat *));
# define lstat(Name, Stat_buf) rpl_lstat(Name, Stat_buf)
#endif

#ifdef D_INO_IN_DIRENT
# define D_INO(dp) ((dp)->d_ino)
# define ENABLE_CYCLE_CHECK
#else
/* Some systems don't have inodes, so fake them to avoid lots of ifdefs.  */
# define D_INO(dp) 1
#endif

#if !defined S_ISLNK
# define S_ISLNK(Mode) 0
#endif

/* Initial capacity of per-directory hash table of entries that have
   been processed but not been deleted.  */
#define HT_UNREMOVABLE_INITIAL_CAPACITY 13

/* An entry in the active directory stack.
   Each entry corresponds to an `active' directory.  */
struct AD_ent
{
  /* For a given active directory, this is the set of names of
     entries in that directory that could/should not be removed.
     For example, `.' and `..', as well as files/dirs for which
     unlink/rmdir failed e.g., due to access restrictions.  */
  Hash_table *unremovable;

  /* Record the status for a given active directory; we need to know
     whether an entry was not removed, either because of an error or
     because the user declined.  */
  enum RM_status status;

  union
  {
    /* The directory's dev/ino.  Used to ensure that `chdir some-subdir', then
       `chdir ..' takes us back to the same directory from which we started).
       (valid for all but the bottommost entry on the stack.  */
    struct dev_ino a;

    /* Enough information to restore the initial working directory.
       (valid only for the bottommost entry on the stack)  */
    struct saved_cwd saved_cwd;
  } u;
};

int euidaccess ();
int yesno ();

extern char *program_name;

/* The name of the directory (starting with and relative to a command
   line argument) being processed.  When a subdirectory is entered, a new
   component is appended (pushed).  When RM chdir's out of a directory,
   the top component is removed (popped).  This is used to form a full
   file name when necessary.  */
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;

/* Stack of active directory entries.
   The first `active' directory is the initial working directory.
   Additional active dirs are pushed onto the stack as rm `chdir's
   into each nonempty directory it must remove.  When rm has finished
   removing the hierarchy under a directory, it pops the active dir stack.  */
static struct obstack Active_dir;

static void
hash_freer (void *x)
{
  free (x);
}

static bool
hash_compare_strings (void const *x, void const *y)
{
  return STREQ (x, y) ? true : false;
}

static inline void
push_dir (const char *dir_name)
{
  size_t len;

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

/* Return the entry name of the directory on the top of the stack
   in malloc'd storage.  */
static inline char *
top_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 = length[n_lengths - 1];
  char const *p = obstack_next_free (&dir_stack) - top_len;
  char *q = xmalloc (top_len);
  memcpy (q, p, top_len - 1);
  q[top_len - 1] = 0;
  return q;
}

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, (int) -(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)
    {
      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;
    }

  *result = memcpy (dp, sp, src_len);
  return dst_len - src_len;
}

/* 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)
    {
      /* This code requires that realloc accept NULL as the first arg.
         This function must not use xrealloc.  Otherwise, an out-of-memory
	 error 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 allocation fails.  */
      buf = realloc (buf, n_bytes_needed);
      n_allocated = n_bytes_needed;

      if (buf == NULL)
	{
#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;
	}
    }

  /* Copy directory part, including trailing slash, and then
     append the filename part, including a trailing zero byte.  */
  memcpy (mempcpy (buf, dir_name, dir_len), filename, filename_len + 1);

  assert (strlen (buf) + 1 == n_bytes_needed);

  return buf;
}

static size_t
AD_stack_height (void)
{
  return obstack_object_size (&Active_dir) / sizeof (struct AD_ent);
}

static struct AD_ent *
AD_stack_top (void)
{
  return (struct AD_ent *)
    ((char *) obstack_next_free (&Active_dir) - sizeof (struct AD_ent));
}

static void
AD_stack_pop (void)
{
  /* operate on Active_dir.  pop and free top entry */
  struct AD_ent *top = AD_stack_top ();
  if (top->unremovable)
    hash_free (top->unremovable);
  obstack_blank (&Active_dir, -sizeof (struct AD_ent));
  pop_dir ();
}

/* chdir `up' one level.
   Whenever using chdir '..', verify that the post-chdir
   dev/ino numbers for `.' match the saved ones.
   Return the name (in malloc'd storage) of the
   directory (usually now empty) from which we're coming.  */
static char *
AD_pop_and_chdir (void)
{
  /* Get the name of the current directory from the top of the stack.  */
  char *dir = top_dir ();
  enum RM_status old_status = AD_stack_top()->status;
  struct stat sb;
  struct AD_ent *top;

  AD_stack_pop ();

  /* Propagate any failure to parent.  */
  UPDATE_STATUS (AD_stack_top()->status, old_status);

  assert (AD_stack_height ());

  top = AD_stack_top ();
  if (1 < AD_stack_height ())
    {
      /* We can give a better diagnostic here, since the target is relative. */
      if (chdir (".."))
	{
	  error (EXIT_FAILURE, errno,
		 _("cannot chdir from %s to .."),
		 quote (full_filename (".")));
	}
    }
  else
    {
      if (restore_cwd (&top->u.saved_cwd, NULL, NULL))