(name_scan): Take an additional argument requesting the exact matching.

[chaz/tar] / src / names.c

/* Various processing of names.

   Copyright (C) 1988, 1992, 1994, 1996, 1997, 1998, 1999, 2000, 2001,
   2003, 2004, 2005 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.,
   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */

#include <system.h>

#include <fnmatch.h>
#include <hash.h>
#include <quotearg.h>

#include "common.h"
\f
/* User and group names.  */

struct group *getgrnam ();
struct passwd *getpwnam ();
#if ! HAVE_DECL_GETPWUID
struct passwd *getpwuid ();
#endif
#if ! HAVE_DECL_GETGRGID
struct group *getgrgid ();
#endif

/* Make sure you link with the proper libraries if you are running the
   Yellow Peril (thanks for the good laugh, Ian J.!), or, euh... NIS.
   This code should also be modified for non-UNIX systems to do something
   reasonable.  */

static char *cached_uname;
static char *cached_gname;

static uid_t cached_uid;        /* valid only if cached_uname is not empty */
static gid_t cached_gid;        /* valid only if cached_gname is not empty */

/* These variables are valid only if nonempty.  */
static char *cached_no_such_uname;
static char *cached_no_such_gname;

/* These variables are valid only if nonzero.  It's not worth optimizing
   the case for weird systems where 0 is not a valid uid or gid.  */
static uid_t cached_no_such_uid;
static gid_t cached_no_such_gid;

static void register_individual_file (char const *name);

/* Given UID, find the corresponding UNAME.  */
void
uid_to_uname (uid_t uid, char **uname)
{
  struct passwd *passwd;

  if (uid != 0 && uid == cached_no_such_uid)
    {
      *uname = xstrdup ("");
      return;
    }

  if (!cached_uname || uid != cached_uid)
    {
      passwd = getpwuid (uid);
      if (passwd)
        {
          cached_uid = uid;
          assign_string (&cached_uname, passwd->pw_name);
        }
      else
        {
          cached_no_such_uid = uid;
          *uname = xstrdup ("");
          return;
        }
    }
  *uname = xstrdup (cached_uname);
}

/* Given GID, find the corresponding GNAME.  */
void
gid_to_gname (gid_t gid, char **gname)
{
  struct group *group;

  if (gid != 0 && gid == cached_no_such_gid)
    {
      *gname = xstrdup ("");
      return;
    }

  if (!cached_gname || gid != cached_gid)
    {
      group = getgrgid (gid);
      if (group)
        {
          cached_gid = gid;
          assign_string (&cached_gname, group->gr_name);
        }
      else
        {
          cached_no_such_gid = gid;
          *gname = xstrdup ("");
          return;
        }
    }
  *gname = xstrdup (cached_gname);
}

/* Given UNAME, set the corresponding UID and return 1, or else, return 0.  */
int
uname_to_uid (char const *uname, uid_t *uidp)
{
  struct passwd *passwd;

  if (cached_no_such_uname
      && strcmp (uname, cached_no_such_uname) == 0)
    return 0;

  if (!cached_uname
      || uname[0] != cached_uname[0]
      || strcmp (uname, cached_uname) != 0)
    {
      passwd = getpwnam (uname);
      if (passwd)
        {
          cached_uid = passwd->pw_uid;
          assign_string (&cached_uname, passwd->pw_name);
        }
      else
        {
          assign_string (&cached_no_such_uname, uname);
          return 0;
        }
    }
  *uidp = cached_uid;
  return 1;
}

/* Given GNAME, set the corresponding GID and return 1, or else, return 0.  */
int
gname_to_gid (char const *gname, gid_t *gidp)
{
  struct group *group;

  if (cached_no_such_gname
      && strcmp (gname, cached_no_such_gname) == 0)
    return 0;

  if (!cached_gname
      || gname[0] != cached_gname[0]
      || strcmp (gname, cached_gname) != 0)
    {
      group = getgrnam (gname);
      if (group)
        {
          cached_gid = group->gr_gid;
          assign_string (&cached_gname, gname);
        }
      else
        {
          assign_string (&cached_no_such_gname, gname);
          return 0;
        }
    }
  *gidp = cached_gid;
  return 1;
}

\f
/* Names from the command call.  */

static struct name *namelist;   /* first name in list, if any */
static struct name **nametail = &namelist;      /* end of name list */
static const char **name_array; /* store an array of names */
static int allocated_names;     /* how big is the array? */
static int names;               /* how many entries does it have? */
static int name_index;          /* how many of the entries have we scanned? */

/* Initialize structures.  */
void
init_names (void)
{
  allocated_names = 10;
  name_array = xmalloc (sizeof (const char *) * allocated_names);
  names = 0;
}

/* Add NAME at end of name_array, reallocating it as necessary.  */
void
name_add (const char *name)
{
  if (names == allocated_names)
    {
      allocated_names *= 2;
      name_array =
        xrealloc (name_array, sizeof (const char *) * allocated_names);
    }
  name_array[names++] = name;
}

\f
/* Names from external name file.  */

static char *name_buffer;       /* buffer to hold the current file name */
static size_t name_buffer_length; /* allocated length of name_buffer */

/* FIXME: I should better check more closely.  It seems at first glance that
   is_pattern is only used when reading a file, and ignored for all
   command line arguments.  */

static inline int
is_pattern (const char *string)
{
  return strchr (string, '*') || strchr (string, '[') || strchr (string, '?');
}

/* Set up to gather file names for tar.  They can either come from a
   file or were saved from decoding arguments.  */
void
name_init (void)
{
  name_buffer = xmalloc (NAME_FIELD_SIZE + 2);
  name_buffer_length = NAME_FIELD_SIZE;
}

void
name_term (void)
{
  free (name_buffer);
  free (name_array);
}

/* Get the next name from ARGV or the file of names.  Result is in
   static storage and can't be relied upon across two calls.

   If CHANGE_DIRS is true, treat a filename of the form "-C" as
   meaning that the next filename is the name of a directory to change
   to.  If filename_terminator is NUL, CHANGE_DIRS is effectively
   always false.  */
char *
name_next (int change_dirs)
{
  const char *source;
  char *cursor;
  int chdir_flag = 0;

  if (filename_terminator == '\0')
    change_dirs = 0;

  while (name_index != names)
    {
      size_t source_len;
      source = name_array[name_index++];
      source_len = strlen (source);
      if (name_buffer_length < source_len)
        {
          do
            {
              name_buffer_length *= 2;
              if (! name_buffer_length)
                xalloc_die ();
            }
          while (name_buffer_length < source_len);

          free (name_buffer);
          name_buffer = xmalloc (name_buffer_length + 2);
        }
      strcpy (name_buffer, source);

      /* Zap trailing slashes.  */

      cursor = name_buffer + strlen (name_buffer) - 1;
      while (cursor > name_buffer && ISSLASH (*cursor))
        *cursor-- = '\0';

      if (chdir_flag)
        {
          if (chdir (name_buffer) < 0)
            chdir_fatal (name_buffer);
          chdir_flag = 0;
        }
      else if (change_dirs && strcmp (name_buffer, "-C") == 0)
        chdir_flag = 1;
      else
        {
          if (unquote_option)
            unquote_string (name_buffer);
          if (incremental_option)
            register_individual_file (name_buffer);
          return name_buffer;
        }
    }

  return 0;
}

/* Gather names in a list for scanning.  Could hash them later if we
   really care.

   If the names are already sorted to match the archive, we just read
   them one by one.  name_gather reads the first one, and it is called
   by name_match as appropriate to read the next ones.  At EOF, the
   last name read is just left in the buffer.  This option lets users
   of small machines extract an arbitrary number of files by doing
   "tar t" and editing down the list of files.  */

void
name_gather (void)
{
  /* Buffer able to hold a single name.  */
  static struct name *buffer;
  static size_t allocated_size;

  char const *name;

  if (same_order_option)
    {
      static int change_dir;

      if (allocated_size == 0)
        {
          allocated_size = offsetof (struct name, name) + NAME_FIELD_SIZE + 1;
          buffer = xmalloc (allocated_size);
          /* FIXME: This memset is overkill, and ugly...  */
          memset (buffer, 0, allocated_size);
        }

      while ((name = name_next (0)) && strcmp (name, "-C") == 0)
        {
          char const *dir = name_next (0);
          if (! dir)
            FATAL_ERROR ((0, 0, _("Missing file name after -C")));
          change_dir = chdir_arg (xstrdup (dir));
        }

      if (name)
        {
          size_t needed_size;
          buffer->length = strlen (name);
          needed_size = offsetof (struct name, name) + buffer->length + 1;
          if (allocated_size < needed_size)
            {
              do
                {
                  allocated_size *= 2;
                  if (! allocated_size)
                    xalloc_die ();
                }
              while (allocated_size < needed_size);

              buffer = xrealloc (buffer, allocated_size);
            }
          buffer->change_dir = change_dir;
          strcpy (buffer->name, name);
          buffer->next = 0;
          buffer->found_count = 0;

          namelist = buffer;
          nametail = &namelist->next;
        }
      else if (change_dir)
        addname (0, change_dir);
    }
  else
    {
      /* Non sorted names -- read them all in.  */
      int change_dir = 0;

      for (;;)
        {
          int change_dir0 = change_dir;
          while ((name = name_next (0)) && strcmp (name, "-C") == 0)
            {
              char const *dir = name_next (0);
              if (! dir)
                FATAL_ERROR ((0, 0, _("Missing file name after -C")));
              change_dir = chdir_arg (xstrdup (dir));
            }
          if (name)
            addname (name, change_dir);
          else
            {
              if (change_dir != change_dir0)
                addname (0, change_dir);
              break;
            }
        }
    }
}

/*  Add a name to the namelist.  */
struct name *
addname (char const *string, int change_dir)
{
  size_t length = string ? strlen (string) : 0;
  struct name *name = xmalloc (offsetof (struct name, name) + length + 1);

  if (string)
    {
      name->fake = 0;
      strcpy (name->name, string);
    }
  else
    {
      name->fake = 1;

      /* FIXME: This initialization (and the byte of memory that it
         initializes) is probably not needed, but we are currently in
         bug-fix mode so we'll leave it in for now.  */
      name->name[0] = 0;
    }

  name->next = 0;
  name->length = length;
  name->found_count = 0;
  name->regexp = 0;             /* assume not a regular expression */
  name->firstch = 1;            /* assume first char is literal */
  name->change_dir = change_dir;
  name->dir_contents = 0;
  name->explicit = 1;
  
  if (string && is_pattern (string))
    {
      name->regexp = 1;
      if (string[0] == '*' || string[0] == '[' || string[0] == '?')
        name->firstch = 0;
    }

  *nametail = name;
  nametail = &name->next;
  return name;
}

/* Find a match for FILE_NAME (whose string length is LENGTH) in the name
   list.  */
static struct name *
namelist_match (char const *file_name, size_t length, bool exact)
{
  struct name *p;

  for (p = namelist; p; p = p->next)
    {
      /* If first chars don't match, quick skip.  */

      if (p->firstch && p->name[0] != file_name[0])
        continue;

      if (p->regexp
          ? fnmatch (p->name, file_name, recursion_option) == 0
          : exact ? (p->length == length
                     && memcmp (file_name, p->name, length) == 0)
          : (p->length <= length
             && (file_name[p->length] == '\0'
                 || (ISSLASH (file_name[p->length]) && recursion_option))
             && memcmp (file_name, p->name, p->length) == 0))
        return p;
    }

  return 0;
}

/* Return true if and only if name FILE_NAME (from an archive) matches any
   name from the namelist.  */
int
name_match (const char *file_name)
{
  size_t length = strlen (file_name);

  while (1)
    {
      struct name *cursor = namelist;

      if (!cursor)
        return 1;

      if (cursor->fake)
        {
          chdir_do (cursor->change_dir);
          namelist = 0;
          nametail = &namelist;
          return 1;
        }

      cursor = namelist_match (file_name, length, false);
      if (cursor)
        {
          if (!(ISSLASH (file_name[cursor->length]) && recursion_option)
              || cursor->found_count == 0)
            cursor->found_count++; /* remember it matched */
          if (starting_file_option)
            {
              free (namelist);
              namelist = 0;
              nametail = &namelist;
            }
          chdir_do (cursor->change_dir);

          /* We got a match.  */
          return ISFOUND (cursor);
        }

      /* Filename from archive not found in namelist.  If we have the whole
         namelist here, just return 0.  Otherwise, read the next name in and
         compare it.  If this was the last name, namelist->found_count will
         remain on.  If not, we loop to compare the newly read name.  */

      if (same_order_option && namelist->found_count)
        {
          name_gather ();       /* read one more */
          if (namelist->found_count)
            return 0;
        }
      else
        return 0;
    }
}

/* Returns true if all names from the namelist were processed.
   P is the stat_info of the most recently processed entry.
   The decision is postponed until the next entry is read if:

   1) P ended with a slash (i.e. it was a directory)
   2) P matches any entry from the namelist *and* represents a subdirectory
   or a file lying under this entry (in the terms of directory structure).

   This is necessary to handle contents of directories. */
bool
all_names_found (struct tar_stat_info *p)
{
  struct name const *cursor;
  size_t len;

  if (test_label_option)
    return true;
  if (!p->file_name || occurrence_option == 0 || p->had_trailing_slash)
    return false;
  len = strlen (p->file_name);
  for (cursor = namelist; cursor; cursor = cursor->next)
    {
      if (cursor->regexp
          || (!WASFOUND(cursor) && !cursor->fake)
          || (len >= cursor->length && ISSLASH (p->file_name[cursor->length])))
        return false;
    }
  return true;
}

/* Print the names of things in the namelist that were not matched.  */
void
names_notfound (void)
{
  struct name const *cursor;

  for (cursor = namelist; cursor; cursor = cursor->next)
    if (!WASFOUND(cursor) && !cursor->fake)
      {
        if (cursor->found_count == 0)
          ERROR ((0, 0, _("%s: Not found in archive"),
                  quotearg_colon (cursor->name)));
        else
          ERROR ((0, 0, _("%s: Required occurrence not found in archive"),
                  quotearg_colon (cursor->name)));
      }

  /* Don't bother freeing the name list; we're about to exit.  */
  namelist = 0;
  nametail = &namelist;

  if (same_order_option)
    {
      char *name;

      while ((name = name_next (1)) != NULL)
        ERROR ((0, 0, _("%s: Not found in archive"),
                quotearg_colon (name)));
    }
}
\f
/* Sorting name lists.  */

/* Sort linked LIST of names, of given LENGTH, using COMPARE to order
   names.  Return the sorted list.  Apart from the type `struct name'
   and the definition of SUCCESSOR, this is a generic list-sorting
   function, but it's too painful to make it both generic and portable
   in C.  */

static struct name *
merge_sort (struct name *list, int length,
            int (*compare) (struct name const*, struct name const*))
{
  struct name *first_list;
  struct name *second_list;
  int first_length;
  int second_length;
  struct name *result;
  struct name **merge_point;
  struct name *cursor;
  int counter;

# define SUCCESSOR(name) ((name)->next)

  if (length == 1)
    return list;

  if (length == 2)
    {
      if ((*compare) (list, SUCCESSOR (list)) > 0)
        {
          result = SUCCESSOR (list);
          SUCCESSOR (result) = list;
          SUCCESSOR (list) = 0;
          return result;
        }
      return list;
    }

  first_list = list;
  first_length = (length + 1) / 2;
  second_length = length / 2;
  for (cursor = list, counter = first_length - 1;
       counter;
       cursor = SUCCESSOR (cursor), counter--)
    continue;
  second_list = SUCCESSOR (cursor);
  SUCCESSOR (cursor) = 0;

  first_list = merge_sort (first_list, first_length, compare);
  second_list = merge_sort (second_list, second_length, compare);

  merge_point = &result;
  while (first_list && second_list)
    if ((*compare) (first_list, second_list) < 0)
      {
        cursor = SUCCESSOR (first_list);
        *merge_point = first_list;
        merge_point = &SUCCESSOR (first_list);
        first_list = cursor;
      }
    else
      {
        cursor = SUCCESSOR (second_list);
        *merge_point = second_list;
        merge_point = &SUCCESSOR (second_list);
        second_list = cursor;
      }
  if (first_list)
    *merge_point = first_list;
  else
    *merge_point = second_list;

  return result;

#undef SUCCESSOR
}

/* A comparison function for sorting names.  Put found names last;
   break ties by string comparison.  */

static int
compare_names (struct name const *n1, struct name const *n2)
{
  int found_diff = WASFOUND(n2) - WASFOUND(n1);
  return found_diff ? found_diff : strcmp (n1->name, n2->name);
}
\f
/* Add all the dirs under NAME, which names a directory, to the namelist.
   If any of the files is a directory, recurse on the subdirectory.
   DEVICE is the device not to leave, if the -l option is specified.  */

static void
add_hierarchy_to_namelist (struct name *name, dev_t device)
{
  char *file_name = name->name;
  char *buffer = get_directory_contents (file_name, device);

  if (! buffer)
    name->dir_contents = "\0\0\0\0";
  else
    {
      size_t name_length = name->length;
      size_t allocated_length = (name_length >= NAME_FIELD_SIZE
                                 ? name_length + NAME_FIELD_SIZE
                                 : NAME_FIELD_SIZE);
      char *namebuf = xmalloc (allocated_length + 1);
                                /* FIXME: + 2 above?  */
      char *string;
      size_t string_length;
      int change_dir = name->change_dir;

      name->dir_contents = buffer;
      strcpy (namebuf, file_name);
      if (! ISSLASH (namebuf[name_length - 1]))
        {
          namebuf[name_length++] = '/';
          namebuf[name_length] = '\0';
        }

      for (string = buffer; *string; string += string_length + 1)
        {
          string_length = strlen (string);
          if (*string == 'D')
            {
              struct name *np;
              
              if (allocated_length <= name_length + string_length)
                {
                  do
                    {
                      allocated_length *= 2;
                      if (! allocated_length)
                        xalloc_die ();
                    }
                  while (allocated_length <= name_length + string_length);

                  namebuf = xrealloc (namebuf, allocated_length + 1);
                }
              strcpy (namebuf + name_length, string + 1);
              np = addname (namebuf, change_dir);
              np->explicit = 0;
              add_hierarchy_to_namelist (np, device);
            }
        }

      free (namebuf);
    }
}
\f
/* Collect all the names from argv[] (or whatever), expand them into a
   directory tree, and sort them.  This gets only subdirectories, not
   all files.  */

void
collect_and_sort_names (void)
{
  struct name *name;
  struct name *next_name;
  int num_names;
  struct stat statbuf;

  name_gather ();

  if (listed_incremental_option)
    read_directory_file ();

  if (!namelist)
    addname (".", 0);

  for (name = namelist; name; name = next_name)
    {
      next_name = name->next;
      if (name->found_count || name->dir_contents)
        continue;
      if (name->regexp)         /* FIXME: just skip regexps for now */
        continue;
      chdir_do (name->change_dir);
      if (name->fake)
        continue;

      if (deref_stat (dereference_option, name->name, &statbuf) != 0)
        {
          stat_diag (name->name);
          continue;
        }
      if (S_ISDIR (statbuf.st_mode))
        {
          name->found_count++;
          add_hierarchy_to_namelist (name, statbuf.st_dev);
        }
    }

  num_names = 0;
  for (name = namelist; name; name = name->next)
    num_names++;
  namelist = merge_sort (namelist, num_names, compare_names);

  for (name = namelist; name; name = name->next)
    name->found_count = 0;
}

/* This is like name_match, except that
    1. It returns a pointer to the name it matched, and doesn't set FOUND
    in structure. The caller will have to do that if it wants to.  
    2. If the namelist is empty, it returns null, unlike name_match, which
    returns TRUE.
    3. The second argument (EXACT) controls matching algorithm. If it
    is TRUE, the exact matching is used. However, regular expressions are
    always matched as such, no matter what the value of EXACT is. */
struct name *
name_scan (const char *file_name, bool exact)
{
  size_t length = strlen (file_name);

  while (1)
    {
      struct name *cursor = namelist_match (file_name, length, exact);
      if (cursor)
        return cursor;

      /* Filename from archive not found in namelist.  If we have the whole
         namelist here, just return 0.  Otherwise, read the next name in and
         compare it.  If this was the last name, namelist->found_count will
         remain on.  If not, we loop to compare the newly read name.  */

      if (same_order_option && namelist && namelist->found_count)
        {
          name_gather ();       /* read one more */
          if (namelist->found_count)
            return 0;
        }
      else
        return 0;
    }
}

/* This returns a name from the namelist which doesn't have ->found
   set.  It sets ->found before returning, so successive calls will
   find and return all the non-found names in the namelist.  */
struct name *gnu_list_name;

char *
name_from_list (void)
{
  if (!gnu_list_name)
    gnu_list_name = namelist;
  while (gnu_list_name && (gnu_list_name->found_count || gnu_list_name->fake))
    gnu_list_name = gnu_list_name->next;
  if (gnu_list_name)
    {
      gnu_list_name->found_count++;
      chdir_do (gnu_list_name->change_dir);
      return gnu_list_name->name;
    }
  return 0;
}

void
blank_name_list (void)
{
  struct name *name;

  gnu_list_name = 0;
  for (name = namelist; name; name = name->next)
    name->found_count = 0;
}

/* Yield a newly allocated file name consisting of FILE_NAME concatenated to
   NAME, with an intervening slash if FILE_NAME does not already end in one.  */
char *
new_name (const char *file_name, const char *name)
{
  size_t file_name_len = strlen (file_name);
  size_t namesize = strlen (name) + 1;
  int slash = file_name_len && ! ISSLASH (file_name[file_name_len - 1]);
  char *buffer = xmalloc (file_name_len + slash + namesize);
  memcpy (buffer, file_name, file_name_len);
  buffer[file_name_len] = '/';
  memcpy (buffer + file_name_len + slash, name, namesize);
  return buffer;
}

/* Return nonzero if file NAME is excluded.  */
bool
excluded_name (char const *name)
{
  return excluded_file_name (excluded, name + FILE_SYSTEM_PREFIX_LEN (name));
}
\f
/* Names to avoid dumping.  */
static Hash_table *avoided_name_table;

/* Remember to not archive NAME.  */
void
add_avoided_name (char const *name)
{
  hash_string_insert (&avoided_name_table, name);
}

/* Should NAME be avoided when archiving?  */
bool
is_avoided_name (char const *name)
{
  return hash_string_lookup (avoided_name_table, name);
}

\f
static Hash_table *individual_file_table;

static void
register_individual_file (char const *name)
{
  struct stat st;

  if (deref_stat (dereference_option, name, &st) != 0)
    return; /* Will be complained about later */
  if (S_ISDIR (st.st_mode))
    return;

  hash_string_insert (&individual_file_table, name);
}

bool
is_individual_file (char const *name)
{
  return hash_string_lookup (individual_file_table, name);
}

\f

/* Return the size of the prefix of FILE_NAME that is removed after
   stripping NUM leading file name components.  NUM must be
   positive.  */

size_t
stripped_prefix_len (char const *file_name, size_t num)
{
  char const *p = file_name + FILE_SYSTEM_PREFIX_LEN (file_name);
  while (ISSLASH (*p))
    p++;
  while (*p)
    {
      bool slash = ISSLASH (*p);
      p++;
      if (slash)
        {
          if (--num == 0)
            return p - file_name;
          while (ISSLASH (*p))
            p++;
        }
    }
  return -1;
}
\f
/* Return nonzero if NAME contains ".." as a file name component.  */
bool
contains_dot_dot (char const *name)
{
  char const *p = name + FILE_SYSTEM_PREFIX_LEN (name);

  for (;; p++)
    {
      if (p[0] == '.' && p[1] == '.' && (ISSLASH (p[2]) || !p[2]))
        return 1;

      do
        {
          if (! *p++)
            return 0;
        }
      while (! ISSLASH (*p));
    }
}