git.cworth.org Git - tar/blob - src/names.c

   1 /* Various processing of names.
   2
   3    Copyright (C) 1988, 1992, 1994, 1996, 1997, 1998, 1999, 2000, 2001,
   4    2003, 2004, 2005, 2006, 2007, 2009 Free Software Foundation, Inc.
   5
   6    This program is free software; you can redistribute it and/or modify it
   7    under the terms of the GNU General Public License as published by the
   8    Free Software Foundation; either version 3, or (at your option) any later
   9    version.
  10
  11    This program is distributed in the hope that it will be useful, but
  12    WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General
  14    Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License along
  17    with this program; if not, write to the Free Software Foundation, Inc.,
  18    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  19
  20 #include <system.h>
  21
  22 #include <fnmatch.h>
  23 #include <hash.h>
  24 #include <quotearg.h>
  25
  26 #include "common.h"
  27 \f
  28 /* User and group names.  */
  29
  30 /* Make sure you link with the proper libraries if you are running the
  31    Yellow Peril (thanks for the good laugh, Ian J.!), or, euh... NIS.
  32    This code should also be modified for non-UNIX systems to do something
  33    reasonable.  */
  34
  35 static char *cached_uname;
  36 static char *cached_gname;
  37
  38 static uid_t cached_uid;        /* valid only if cached_uname is not empty */
  39 static gid_t cached_gid;        /* valid only if cached_gname is not empty */
  40
  41 /* These variables are valid only if nonempty.  */
  42 static char *cached_no_such_uname;
  43 static char *cached_no_such_gname;
  44
  45 /* These variables are valid only if nonzero.  It's not worth optimizing
  46    the case for weird systems where 0 is not a valid uid or gid.  */
  47 static uid_t cached_no_such_uid;
  48 static gid_t cached_no_such_gid;
  49
  50 static void register_individual_file (char const *name);
  51
  52 /* Given UID, find the corresponding UNAME.  */
  53 void
  54 uid_to_uname (uid_t uid, char **uname)
  55 {
  56   struct passwd *passwd;
  57
  58   if (uid != 0 && uid == cached_no_such_uid)
  59     {
  60       *uname = xstrdup ("");
  61       return;
  62     }
  63
  64   if (!cached_uname || uid != cached_uid)
  65     {
  66       passwd = getpwuid (uid);
  67       if (passwd)
  68         {
  69           cached_uid = uid;
  70           assign_string (&cached_uname, passwd->pw_name);
  71         }
  72       else
  73         {
  74           cached_no_such_uid = uid;
  75           *uname = xstrdup ("");
  76           return;
  77         }
  78     }
  79   *uname = xstrdup (cached_uname);
  80 }
  81
  82 /* Given GID, find the corresponding GNAME.  */
  83 void
  84 gid_to_gname (gid_t gid, char **gname)
  85 {
  86   struct group *group;
  87
  88   if (gid != 0 && gid == cached_no_such_gid)
  89     {
  90       *gname = xstrdup ("");
  91       return;
  92     }
  93
  94   if (!cached_gname || gid != cached_gid)
  95     {
  96       group = getgrgid (gid);
  97       if (group)
  98         {
  99           cached_gid = gid;
 100           assign_string (&cached_gname, group->gr_name);
 101         }
 102       else
 103         {
 104           cached_no_such_gid = gid;
 105           *gname = xstrdup ("");
 106           return;
 107         }
 108     }
 109   *gname = xstrdup (cached_gname);
 110 }
 111
 112 /* Given UNAME, set the corresponding UID and return 1, or else, return 0.  */
 113 int
 114 uname_to_uid (char const *uname, uid_t *uidp)
 115 {
 116   struct passwd *passwd;
 117
 118   if (cached_no_such_uname
 119       && strcmp (uname, cached_no_such_uname) == 0)
 120     return 0;
 121
 122   if (!cached_uname
 123       || uname[0] != cached_uname[0]
 124       || strcmp (uname, cached_uname) != 0)
 125     {
 126       passwd = getpwnam (uname);
 127       if (passwd)
 128         {
 129           cached_uid = passwd->pw_uid;
 130           assign_string (&cached_uname, passwd->pw_name);
 131         }
 132       else
 133         {
 134           assign_string (&cached_no_such_uname, uname);
 135           return 0;
 136         }
 137     }
 138   *uidp = cached_uid;
 139   return 1;
 140 }
 141
 142 /* Given GNAME, set the corresponding GID and return 1, or else, return 0.  */
 143 int
 144 gname_to_gid (char const *gname, gid_t *gidp)
 145 {
 146   struct group *group;
 147
 148   if (cached_no_such_gname
 149       && strcmp (gname, cached_no_such_gname) == 0)
 150     return 0;
 151
 152   if (!cached_gname
 153       || gname[0] != cached_gname[0]
 154       || strcmp (gname, cached_gname) != 0)
 155     {
 156       group = getgrnam (gname);
 157       if (group)
 158         {
 159           cached_gid = group->gr_gid;
 160           assign_string (&cached_gname, gname);
 161         }
 162       else
 163         {
 164           assign_string (&cached_no_such_gname, gname);
 165           return 0;
 166         }
 167     }
 168   *gidp = cached_gid;
 169   return 1;
 170 }
 171
 172 \f
 173 static struct name *
 174 make_name (const char *file_name)
 175 {
 176   struct name *p = xzalloc (sizeof (*p));
 177   if (!file_name)
 178     file_name = "";
 179   p->name = xstrdup (file_name);
 180   p->length = strlen (p->name);
 181   return p;
 182 }
 183
 184 static void
 185 free_name (struct name *p)
 186 {
 187   if (p)
 188     {
 189       free (p->name);
 190       free (p->caname);
 191       free (p);
 192     }
 193 }
 194
 195 \f
 196 /* Names from the command call.  */
 197
 198 static struct name *namelist;   /* first name in list, if any */
 199 static struct name *nametail;   /* end of name list */
 200
 201 /* File name arguments are processed in two stages: first a
 202    name_array (see below) is filled, then the names from it
 203    are moved into the namelist.
 204
 205    This awkward process is needed only to implement --same-order option,
 206    which is meant to help process large archives on machines with
 207    limited memory.  With this option on, namelist contains at most one
 208    entry, which diminishes the memory consumption.
 209
 210    However, I very much doubt if we still need this -- Sergey */
 211
 212 /* A name_array element contains entries of three types: */
 213
 214 #define NELT_NAME  0   /* File name */
 215 #define NELT_CHDIR 1   /* Change directory request */
 216 #define NELT_FMASK 2   /* Change fnmatch options request */
 217
 218 struct name_elt        /* A name_array element. */
 219 {
 220   char type;           /* Element type, see NELT_* constants above */
 221   union
 222   {
 223     const char *name;  /* File or directory name */
 224     int matching_flags;/* fnmatch options if type == NELT_FMASK */
 225   } v;
 226 };
 227
 228 static struct name_elt *name_array;  /* store an array of names */
 229 static size_t allocated_entries; /* how big is the array? */
 230 static size_t entries;           /* how many entries does it have? */
 231 static size_t scanned;           /* how many of the entries have we scanned? */
 232 size_t name_count;               /* how many of the entries are names? */
 233
 234 /* Check the size of name_array, reallocating it as necessary.  */
 235 static void
 236 check_name_alloc (void)
 237 {
 238   if (entries == allocated_entries)
 239     {
 240       if (allocated_entries == 0)
 241         allocated_entries = 10; /* Set initial allocation */
 242       name_array = x2nrealloc (name_array, &allocated_entries,
 243                                sizeof (name_array[0]));
 244     }
 245 }
 246
 247 /* Add to name_array the file NAME with fnmatch options MATCHING_FLAGS */
 248 void
 249 name_add_name (const char *name, int matching_flags)
 250 {
 251   static int prev_flags = 0; /* FIXME: Or EXCLUDE_ANCHORED? */
 252   struct name_elt *ep;
 253
 254   check_name_alloc ();
 255   ep = &name_array[entries++];
 256   if (prev_flags != matching_flags)
 257     {
 258       ep->type = NELT_FMASK;
 259       ep->v.matching_flags = matching_flags;
 260       prev_flags = matching_flags;
 261       check_name_alloc ();
 262       ep = &name_array[entries++];
 263     }
 264   ep->type = NELT_NAME;
 265   ep->v.name = name;
 266   name_count++;
 267 }
 268
 269 /* Add to name_array a chdir request for the directory NAME */
 270 void
 271 name_add_dir (const char *name)
 272 {
 273   struct name_elt *ep;
 274   check_name_alloc ();
 275   ep = &name_array[entries++];
 276   ep->type = NELT_CHDIR;
 277   ep->v.name = name;
 278 }
 279
 280 \f
 281 /* Names from external name file.  */
 282
 283 static char *name_buffer;       /* buffer to hold the current file name */
 284 static size_t name_buffer_length; /* allocated length of name_buffer */
 285
 286 /* Set up to gather file names for tar.  They can either come from a
 287    file or were saved from decoding arguments.  */
 288 void
 289 name_init (void)
 290 {
 291   name_buffer = xmalloc (NAME_FIELD_SIZE + 2);
 292   name_buffer_length = NAME_FIELD_SIZE;
 293 }
 294
 295 void
 296 name_term (void)
 297 {
 298   free (name_buffer);
 299   free (name_array);
 300 }
 301
 302 static int matching_flags; /* exclude_fnmatch options */
 303
 304 /* Get the next NELT_NAME element from name_array.  Result is in
 305    static storage and can't be relied upon across two calls.
 306
 307    If CHANGE_DIRS is true, treat any entries of type NELT_CHDIR as
 308    the request to change to the given directory.
 309
 310    Entries of type NELT_FMASK cause updates of the matching_flags
 311    value. */
 312 static struct name_elt *
 313 name_next_elt (int change_dirs)
 314 {
 315   static struct name_elt entry;
 316   const char *source;
 317   char *cursor;
 318
 319   while (scanned != entries)
 320     {
 321       struct name_elt *ep;
 322       size_t source_len;
 323
 324       ep = &name_array[scanned++];
 325       if (ep->type == NELT_FMASK)
 326         {
 327           matching_flags = ep->v.matching_flags;
 328           continue;
 329         }
 330
 331       source = ep->v.name;
 332       source_len = strlen (source);
 333       if (name_buffer_length < source_len)
 334         {
 335           do
 336             {
 337               name_buffer_length *= 2;
 338               if (! name_buffer_length)
 339                 xalloc_die ();
 340             }
 341           while (name_buffer_length < source_len);
 342
 343           free (name_buffer);
 344           name_buffer = xmalloc (name_buffer_length + 2);
 345         }
 346       strcpy (name_buffer, source);
 347
 348       /* Zap trailing slashes.  */
 349
 350       cursor = name_buffer + strlen (name_buffer) - 1;
 351       while (cursor > name_buffer && ISSLASH (*cursor))
 352         *cursor-- = '\0';
 353
 354       if (change_dirs && ep->type == NELT_CHDIR)
 355         {
 356           if (chdir (name_buffer) < 0)
 357             chdir_fatal (name_buffer);
 358         }
 359       else
 360         {
 361           if (unquote_option)
 362             unquote_string (name_buffer);
 363           if (incremental_option)
 364             register_individual_file (name_buffer);
 365           entry.type = ep->type;
 366           entry.v.name = name_buffer;
 367           return &entry;
 368         }
 369     }
 370
 371   return NULL;
 372 }
 373
 374 const char *
 375 name_next (int change_dirs)
 376 {
 377   struct name_elt *nelt = name_next_elt (change_dirs);
 378   return nelt ? nelt->v.name : NULL;
 379 }
 380
 381 /* Gather names in a list for scanning.  Could hash them later if we
 382    really care.
 383
 384    If the names are already sorted to match the archive, we just read
 385    them one by one.  name_gather reads the first one, and it is called
 386    by name_match as appropriate to read the next ones.  At EOF, the
 387    last name read is just left in the buffer.  This option lets users
 388    of small machines extract an arbitrary number of files by doing
 389    "tar t" and editing down the list of files.  */
 390
 391 void
 392 name_gather (void)
 393 {
 394   /* Buffer able to hold a single name.  */
 395   static struct name *buffer = NULL;
 396
 397   struct name_elt *ep;
 398
 399   if (same_order_option)
 400     {
 401       static int change_dir;
 402
 403       while ((ep = name_next_elt (0)) && ep->type == NELT_CHDIR)
 404         change_dir = chdir_arg (xstrdup (ep->v.name));
 405
 406       if (ep)
 407         {
 408           free_name (buffer);
 409           buffer = make_name (ep->v.name);
 410           buffer->change_dir = change_dir;
 411           buffer->next = 0;
 412           buffer->found_count = 0;
 413           buffer->matching_flags = matching_flags;
 414           buffer->directory = NULL;
 415           buffer->parent = NULL;
 416           buffer->cmdline = true;
 417
 418           namelist = nametail = buffer;
 419         }
 420       else if (change_dir)
 421         addname (0, change_dir, false, NULL);
 422     }
 423   else
 424     {
 425       /* Non sorted names -- read them all in.  */
 426       int change_dir = 0;
 427
 428       for (;;)
 429         {
 430           int change_dir0 = change_dir;
 431           while ((ep = name_next_elt (0)) && ep->type == NELT_CHDIR)
 432             change_dir = chdir_arg (xstrdup (ep->v.name));
 433
 434           if (ep)
 435             addname (ep->v.name, change_dir, true, NULL);
 436           else
 437             {
 438               if (change_dir != change_dir0)
 439                 addname (NULL, change_dir, false, NULL);
 440               break;
 441             }
 442         }
 443     }
 444 }
 445
 446 /*  Add a name to the namelist.  */
 447 struct name *
 448 addname (char const *string, int change_dir, bool cmdline, struct name *parent)
 449 {
 450   struct name *name = make_name (string);
 451
 452   name->prev = nametail;
 453   name->next = NULL;
 454   name->found_count = 0;
 455   name->matching_flags = matching_flags;
 456   name->change_dir = change_dir;
 457   name->directory = NULL;
 458   name->parent = parent;
 459   name->cmdline = cmdline;
 460
 461   if (nametail)
 462     nametail->next = name;
 463   else
 464     namelist = name;
 465   nametail = name;
 466   return name;
 467 }
 468
 469 /* Find a match for FILE_NAME (whose string length is LENGTH) in the name
 470    list.  */
 471 static struct name *
 472 namelist_match (char const *file_name, size_t length)
 473 {
 474   struct name *p;
 475
 476   for (p = namelist; p; p = p->next)
 477     {
 478       if (p->name[0]
 479           && exclude_fnmatch (p->name, file_name, p->matching_flags))
 480         return p;
 481     }
 482
 483   return NULL;
 484 }
 485
 486 void
 487 remname (struct name *name)
 488 {
 489   struct name *p;
 490
 491   if ((p = name->prev) != NULL)
 492     p->next = name->next;
 493   else
 494     namelist = name->next;
 495
 496   if ((p = name->next) != NULL)
 497     p->prev = name->prev;
 498   else
 499     nametail = name->prev;
 500 }
 501
 502 /* Return true if and only if name FILE_NAME (from an archive) matches any
 503    name from the namelist.  */
 504 bool
 505 name_match (const char *file_name)
 506 {
 507   size_t length = strlen (file_name);
 508
 509   while (1)
 510     {
 511       struct name *cursor = namelist;
 512
 513       if (!cursor)
 514         return true;
 515
 516       if (cursor->name[0] == 0)
 517         {
 518           chdir_do (cursor->change_dir);
 519           namelist = NULL;
 520           nametail = NULL;
 521           return true;
 522         }
 523
 524       cursor = namelist_match (file_name, length);
 525       if (cursor)
 526         {
 527           if (!(ISSLASH (file_name[cursor->length]) && recursion_option)
 528               || cursor->found_count == 0)
 529             cursor->found_count++; /* remember it matched */
 530           if (starting_file_option)
 531             {
 532               free (namelist);
 533               namelist = NULL;
 534               nametail = NULL;
 535             }
 536           chdir_do (cursor->change_dir);
 537
 538           /* We got a match.  */
 539           return ISFOUND (cursor);
 540         }
 541
 542       /* Filename from archive not found in namelist.  If we have the whole
 543          namelist here, just return 0.  Otherwise, read the next name in and
 544          compare it.  If this was the last name, namelist->found_count will
 545          remain on.  If not, we loop to compare the newly read name.  */
 546
 547       if (same_order_option && namelist->found_count)
 548         {
 549           name_gather ();       /* read one more */
 550           if (namelist->found_count)
 551             return false;
 552         }
 553       else
 554         return false;
 555     }
 556 }
 557
 558 /* Returns true if all names from the namelist were processed.
 559    P is the stat_info of the most recently processed entry.
 560    The decision is postponed until the next entry is read if:
 561
 562    1) P ended with a slash (i.e. it was a directory)
 563    2) P matches any entry from the namelist *and* represents a subdirectory
 564    or a file lying under this entry (in the terms of directory structure).
 565
 566    This is necessary to handle contents of directories. */
 567 bool
 568 all_names_found (struct tar_stat_info *p)
 569 {
 570   struct name const *cursor;
 571   size_t len;
 572
 573   if (!p->file_name || occurrence_option == 0 || p->had_trailing_slash)
 574     return false;
 575   len = strlen (p->file_name);
 576   for (cursor = namelist; cursor; cursor = cursor->next)
 577     {
 578       if ((cursor->name[0] && !WASFOUND (cursor))
 579           || (len >= cursor->length && ISSLASH (p->file_name[cursor->length])))
 580         return false;
 581     }
 582   return true;
 583 }
 584
 585 static int
 586 regex_usage_warning (const char *name)
 587 {
 588   static int warned_once = 0;
 589
 590   if (warn_regex_usage && fnmatch_pattern_has_wildcards (name, 0))
 591     {
 592       warned_once = 1;
 593       WARN ((0, 0,
 594              _("Pattern matching characters used in file names")));
 595       WARN ((0, 0,
 596              _("Use --wildcards to enable pattern matching,"
 597                " or --no-wildcards to suppress this warning")));
 598     }
 599   return warned_once;
 600 }
 601
 602 /* Print the names of things in the namelist that were not matched.  */
 603 void
 604 names_notfound (void)
 605 {
 606   struct name const *cursor;
 607
 608   for (cursor = namelist; cursor; cursor = cursor->next)
 609     if (!WASFOUND (cursor) && cursor->name[0])
 610       {
 611         regex_usage_warning (cursor->name);
 612         ERROR ((0, 0,
 613                 (cursor->found_count == 0) ?
 614                      _("%s: Not found in archive") :
 615                      _("%s: Required occurrence not found in archive"),
 616                 quotearg_colon (cursor->name)));
 617       }
 618
 619   /* Don't bother freeing the name list; we're about to exit.  */
 620   namelist = NULL;
 621   nametail = NULL;
 622
 623   if (same_order_option)
 624     {
 625       const char *name;
 626
 627       while ((name = name_next (1)) != NULL)
 628         {
 629           regex_usage_warning (name);
 630           ERROR ((0, 0, _("%s: Not found in archive"),
 631                   quotearg_colon (name)));
 632         }
 633     }
 634 }
 635
 636 void
 637 label_notfound (void)
 638 {
 639   struct name const *cursor;
 640
 641   if (!namelist)
 642     return;
 643
 644   for (cursor = namelist; cursor; cursor = cursor->next)
 645     if (WASFOUND (cursor))
 646       return;
 647
 648   if (verbose_option)
 649     error (0, 0, _("Archive label mismatch"));
 650   set_exit_status (TAREXIT_DIFFERS);
 651
 652   for (cursor = namelist; cursor; cursor = cursor->next)
 653     {
 654       if (regex_usage_warning (cursor->name))
 655         break;
 656     }
 657
 658   /* Don't bother freeing the name list; we're about to exit.  */
 659   namelist = NULL;
 660   nametail = NULL;
 661
 662   if (same_order_option)
 663     {
 664       const char *name;
 665
 666       while ((name = name_next (1)) != NULL
 667              && regex_usage_warning (name) == 0)
 668         ;
 669     }
 670 }
 671 \f
 672 /* Sorting name lists.  */
 673
 674 /* Sort *singly* linked LIST of names, of given LENGTH, using COMPARE
 675    to order names.  Return the sorted list.  Note that after calling
 676    this function, the `prev' links in list elements are messed up.
 677
 678    Apart from the type `struct name' and the definition of SUCCESSOR,
 679    this is a generic list-sorting function, but it's too painful to
 680    make it both generic and portable
 681    in C.  */
 682
 683 static struct name *
 684 merge_sort_sll (struct name *list, int length,
 685                 int (*compare) (struct name const*, struct name const*))
 686 {
 687   struct name *first_list;
 688   struct name *second_list;
 689   int first_length;
 690   int second_length;
 691   struct name *result;
 692   struct name **merge_point;
 693   struct name *cursor;
 694   int counter;
 695
 696 # define SUCCESSOR(name) ((name)->next)
 697
 698   if (length == 1)
 699     return list;
 700
 701   if (length == 2)
 702     {
 703       if ((*compare) (list, SUCCESSOR (list)) > 0)
 704         {
 705           result = SUCCESSOR (list);
 706           SUCCESSOR (result) = list;
 707           SUCCESSOR (list) = 0;
 708           return result;
 709         }
 710       return list;
 711     }
 712
 713   first_list = list;
 714   first_length = (length + 1) / 2;
 715   second_length = length / 2;
 716   for (cursor = list, counter = first_length - 1;
 717        counter;
 718        cursor = SUCCESSOR (cursor), counter--)
 719     continue;
 720   second_list = SUCCESSOR (cursor);
 721   SUCCESSOR (cursor) = 0;
 722
 723   first_list = merge_sort_sll (first_list, first_length, compare);
 724   second_list = merge_sort_sll (second_list, second_length, compare);
 725
 726   merge_point = &result;
 727   while (first_list && second_list)
 728     if ((*compare) (first_list, second_list) < 0)
 729       {
 730         cursor = SUCCESSOR (first_list);
 731         *merge_point = first_list;
 732         merge_point = &SUCCESSOR (first_list);
 733         first_list = cursor;
 734       }
 735     else
 736       {
 737         cursor = SUCCESSOR (second_list);
 738         *merge_point = second_list;
 739         merge_point = &SUCCESSOR (second_list);
 740         second_list = cursor;
 741       }
 742   if (first_list)
 743     *merge_point = first_list;
 744   else
 745     *merge_point = second_list;
 746
 747   return result;
 748
 749 #undef SUCCESSOR
 750 }
 751
 752 /* Sort doubly linked LIST of names, of given LENGTH, using COMPARE
 753    to order names.  Return the sorted list.  */
 754 static struct name *
 755 merge_sort (struct name *list, int length,
 756             int (*compare) (struct name const*, struct name const*))
 757 {
 758   struct name *head, *p, *prev;
 759   head = merge_sort_sll (list, length, compare);
 760   /* Fixup prev pointers */
 761   for (prev = NULL, p = head; p; prev = p, p = p->next)
 762     p->prev = prev;
 763   return head;
 764 }
 765
 766 /* A comparison function for sorting names.  Put found names last;
 767    break ties by string comparison.  */
 768
 769 static int
 770 compare_names_found (struct name const *n1, struct name const *n2)
 771 {
 772   int found_diff = WASFOUND (n2) - WASFOUND (n1);
 773   return found_diff ? found_diff : strcmp (n1->name, n2->name);
 774 }
 775
 776 /* Simple comparison by names. */
 777 static int
 778 compare_names (struct name const *n1, struct name const *n2)
 779 {
 780   return strcmp (n1->name, n2->name);
 781 }
 782
 783 \f
 784 /* Add all the dirs under ST to the namelist NAME, descending the
 785    directory hierarchy recursively.  */
 786
 787 static void
 788 add_hierarchy_to_namelist (struct tar_stat_info *st, struct name *name)
 789 {
 790   const char *buffer;
 791
 792   name->directory = scan_directory (st);
 793   buffer = directory_contents (name->directory);
 794   if (buffer)
 795     {
 796       struct name *child_head = NULL, *child_tail = NULL;
 797       size_t name_length = name->length;
 798       size_t allocated_length = (name_length >= NAME_FIELD_SIZE
 799                                  ? name_length + NAME_FIELD_SIZE
 800                                  : NAME_FIELD_SIZE);
 801       char *namebuf = xmalloc (allocated_length + 1);
 802                                 /* FIXME: + 2 above?  */
 803       const char *string;
 804       size_t string_length;
 805       int change_dir = name->change_dir;
 806
 807       strcpy (namebuf, name->name);
 808       if (! ISSLASH (namebuf[name_length - 1]))
 809         {
 810           namebuf[name_length++] = '/';
 811           namebuf[name_length] = '\0';
 812         }
 813
 814       for (string = buffer; *string; string += string_length + 1)
 815         {
 816           string_length = strlen (string);
 817           if (*string == 'D')
 818             {
 819               struct name *np;
 820               struct tar_stat_info subdir;
 821               int subfd;
 822
 823               if (allocated_length <= name_length + string_length)
 824                 {
 825                   do
 826                     {
 827                       allocated_length *= 2;
 828                       if (! allocated_length)
 829                         xalloc_die ();
 830                     }
 831                   while (allocated_length <= name_length + string_length);
 832
 833                   namebuf = xrealloc (namebuf, allocated_length + 1);
 834                 }
 835               strcpy (namebuf + name_length, string + 1);
 836               np = addname (namebuf, change_dir, false, name);
 837               if (!child_head)
 838                 child_head = np;
 839               else
 840                 child_tail->sibling = np;
 841               child_tail = np;
 842
 843               tar_stat_init (&subdir);
 844               subdir.parent = st;
 845               if (st->fd < 0)
 846                 {
 847                   subfd = -1;
 848                   errno = - st->fd;
 849                 }
 850               else
 851                 subfd = subfile_open (st, string + 1,
 852                                       open_read_flags | O_DIRECTORY);
 853               if (subfd < 0)
 854                 open_diag (namebuf);
 855               else
 856                 {
 857                   subdir.fd = subfd;
 858                   if (fstat (subfd, &subdir.stat) != 0)
 859                     stat_diag (namebuf);
 860                   else if (! (O_DIRECTORY || S_ISDIR (subdir.stat.st_mode)))
 861                     {
 862                       errno = ENOTDIR;
 863                       open_diag (namebuf);
 864                     }
 865                   else
 866                     {
 867                       subdir.orig_file_name = xstrdup (namebuf);
 868                       add_hierarchy_to_namelist (&subdir, np);
 869                       restore_parent_fd (&subdir);
 870                     }
 871                 }
 872
 873               tar_stat_destroy (&subdir);
 874             }
 875         }
 876
 877       free (namebuf);
 878       name->child = child_head;
 879     }
 880 }
 881 \f
 882 /* Auxiliary functions for hashed table of struct name's. */
 883
 884 static size_t
 885 name_hash (void const *entry, size_t n_buckets)
 886 {
 887   struct name const *name = entry;
 888   return hash_string (name->caname, n_buckets);
 889 }
 890
 891 /* Compare two directories for equality of their names. */
 892 static bool
 893 name_compare (void const *entry1, void const *entry2)
 894 {
 895   struct name const *name1 = entry1;
 896   struct name const *name2 = entry2;
 897   return strcmp (name1->caname, name2->caname) == 0;
 898 }
 899
 900 \f
 901 /* Rebase `name' member of CHILD and all its siblings to
 902    the new PARENT. */
 903 static void
 904 rebase_child_list (struct name *child, struct name *parent)
 905 {
 906   size_t old_prefix_len = child->parent->length;
 907   size_t new_prefix_len = parent->length;
 908   char *new_prefix = parent->name;
 909
 910   for (; child; child = child->sibling)
 911     {
 912       size_t size = child->length - old_prefix_len + new_prefix_len;
 913       char *newp = xmalloc (size + 1);
 914       strcpy (newp, new_prefix);
 915       strcat (newp, child->name + old_prefix_len);
 916       free (child->name);
 917       child->name = newp;
 918       child->length = size;
 919
 920       rebase_directory (child->directory,
 921                         child->parent->name, old_prefix_len,
 922                         new_prefix, new_prefix_len);
 923     }
 924 }
 925
 926 /* Collect all the names from argv[] (or whatever), expand them into a
 927    directory tree, and sort them.  This gets only subdirectories, not
 928    all files.  */
 929
 930 void
 931 collect_and_sort_names (void)
 932 {
 933   struct name *name;
 934   struct name *next_name, *prev_name = NULL;
 935   int num_names;
 936   Hash_table *nametab;
 937
 938   name_gather ();
 939
 940   if (!namelist)
 941     addname (".", 0, false, NULL);
 942
 943   if (listed_incremental_option)
 944     {
 945       switch (chdir_count ())
 946         {
 947         case 0:
 948           break;
 949
 950         case 1:
 951           if (namelist->change_dir == 0)
 952             USAGE_ERROR ((0, 0,
 953                           _("Using -C option inside file list is not "
 954                             "allowed with --listed-incremental")));
 955           break;
 956
 957         default:
 958           USAGE_ERROR ((0, 0,
 959                         _("Only one -C option is allowed with "
 960                           "--listed-incremental")));
 961         }
 962
 963       read_directory_file ();
 964     }
 965
 966   num_names = 0;
 967   for (name = namelist; name; name = name->next, num_names++)
 968     {
 969       struct tar_stat_info st;
 970
 971       if (name->found_count || name->directory)
 972         continue;
 973       if (name->matching_flags & EXCLUDE_WILDCARDS)
 974         /* NOTE: EXCLUDE_ANCHORED is not relevant here */
 975         /* FIXME: just skip regexps for now */
 976         continue;
 977       chdir_do (name->change_dir);
 978
 979       if (name->name[0] == 0)
 980         continue;
 981
 982       tar_stat_init (&st);
 983
 984       if (deref_stat (name->name, &st.stat) != 0)
 985         {
 986           stat_diag (name->name);
 987           continue;
 988         }
 989       if (S_ISDIR (st.stat.st_mode))
 990         {
 991           int dir_fd = openat (chdir_fd, name->name,
 992                                open_read_flags | O_DIRECTORY);
 993           if (dir_fd < 0)
 994             open_diag (name->name);
 995           else
 996             {
 997               st.fd = dir_fd;
 998               if (fstat (dir_fd, &st.stat) != 0)
 999                 stat_diag (name->name);
1000               else if (O_DIRECTORY || S_ISDIR (st.stat.st_mode))
1001                 {
1002                   st.orig_file_name = xstrdup (name->name);
1003                   name->found_count++;
1004                   add_hierarchy_to_namelist (&st, name);
1005                 }
1006             }
1007         }
1008
1009       tar_stat_destroy (&st);
1010     }
1011
1012   namelist = merge_sort (namelist, num_names, compare_names);
1013
1014   num_names = 0;
1015   nametab = hash_initialize (0, 0,
1016                              name_hash,
1017                              name_compare, NULL);
1018   for (name = namelist; name; name = next_name)
1019     {
1020       next_name = name->next;
1021       name->caname = normalize_filename (name->name);
1022       if (prev_name)
1023         {
1024           struct name *p = hash_lookup (nametab, name);
1025           if (p)
1026             {
1027               /* Keep the one listed in the command line */
1028               if (!name->parent)
1029                 {
1030                   if (p->child)
1031                     rebase_child_list (p->child, name);
1032                   hash_delete (nametab, name);
1033                   /* FIXME: remove_directory (p->caname); ? */
1034                   remname (p);
1035                   free_name (p);
1036                   num_names--;
1037                 }
1038               else
1039                 {
1040                   if (name->child)
1041                     rebase_child_list (name->child, p);
1042                   /* FIXME: remove_directory (name->caname); ? */
1043                   remname (name);
1044                   free_name (name);
1045                   continue;
1046                 }
1047             }
1048         }
1049       name->found_count = 0;
1050       if (!hash_insert (nametab, name))
1051         xalloc_die ();
1052       prev_name = name;
1053       num_names++;
1054     }
1055   nametail = prev_name;
1056   hash_free (nametab);
1057
1058   namelist = merge_sort (namelist, num_names, compare_names_found);
1059
1060   if (listed_incremental_option)
1061     {
1062       for (name = namelist; name && name->name[0] == 0; name++)
1063         ;
1064       if (name)
1065         append_incremental_renames (name->directory);
1066     }
1067 }
1068
1069 /* This is like name_match, except that
1070     1. It returns a pointer to the name it matched, and doesn't set FOUND
1071     in structure. The caller will have to do that if it wants to.
1072     2. If the namelist is empty, it returns null, unlike name_match, which
1073     returns TRUE. */
1074 struct name *
1075 name_scan (const char *file_name)
1076 {
1077   size_t length = strlen (file_name);
1078
1079   while (1)
1080     {
1081       struct name *cursor = namelist_match (file_name, length);
1082       if (cursor)
1083         return cursor;
1084
1085       /* Filename from archive not found in namelist.  If we have the whole
1086          namelist here, just return 0.  Otherwise, read the next name in and
1087          compare it.  If this was the last name, namelist->found_count will
1088          remain on.  If not, we loop to compare the newly read name.  */
1089
1090       if (same_order_option && namelist && namelist->found_count)
1091         {
1092           name_gather ();       /* read one more */
1093           if (namelist->found_count)
1094             return 0;
1095         }
1096       else
1097         return 0;
1098     }
1099 }
1100
1101 /* This returns a name from the namelist which doesn't have ->found
1102    set.  It sets ->found before returning, so successive calls will
1103    find and return all the non-found names in the namelist.  */
1104 struct name *gnu_list_name;
1105
1106 struct name const *
1107 name_from_list ()
1108 {
1109   if (!gnu_list_name)
1110     gnu_list_name = namelist;
1111   while (gnu_list_name
1112          && (gnu_list_name->found_count || gnu_list_name->name[0] == 0))
1113     gnu_list_name = gnu_list_name->next;
1114   if (gnu_list_name)
1115     {
1116       gnu_list_name->found_count++;
1117       chdir_do (gnu_list_name->change_dir);
1118       return gnu_list_name;
1119     }
1120   return NULL;
1121 }
1122
1123 void
1124 blank_name_list (void)
1125 {
1126   struct name *name;
1127
1128   gnu_list_name = 0;
1129   for (name = namelist; name; name = name->next)
1130     name->found_count = 0;
1131 }
1132
1133 /* Yield a newly allocated file name consisting of FILE_NAME concatenated to
1134    NAME, with an intervening slash if FILE_NAME does not already end in one. */
1135 char *
1136 new_name (const char *file_name, const char *name)
1137 {
1138   size_t file_name_len = strlen (file_name);
1139   size_t namesize = strlen (name) + 1;
1140   int slash = file_name_len && ! ISSLASH (file_name[file_name_len - 1]);
1141   char *buffer = xmalloc (file_name_len + slash + namesize);
1142   memcpy (buffer, file_name, file_name_len);
1143   buffer[file_name_len] = '/';
1144   memcpy (buffer + file_name_len + slash, name, namesize);
1145   return buffer;
1146 }
1147
1148 /* Return nonzero if file NAME is excluded.  */
1149 bool
1150 excluded_name (char const *name)
1151 {
1152   return excluded_file_name (excluded, name + FILE_SYSTEM_PREFIX_LEN (name));
1153 }
1154 \f
1155 static Hash_table *individual_file_table;
1156
1157 static void
1158 register_individual_file (char const *name)
1159 {
1160   struct stat st;
1161
1162   if (deref_stat (name, &st) != 0)
1163     return; /* Will be complained about later */
1164   if (S_ISDIR (st.st_mode))
1165     return;
1166
1167   hash_string_insert (&individual_file_table, name);
1168 }
1169
1170 bool
1171 is_individual_file (char const *name)
1172 {
1173   return hash_string_lookup (individual_file_table, name);
1174 }
1175
1176 \f
1177
1178 /* Return the size of the prefix of FILE_NAME that is removed after
1179    stripping NUM leading file name components.  NUM must be
1180    positive.  */
1181
1182 size_t
1183 stripped_prefix_len (char const *file_name, size_t num)
1184 {
1185   char const *p = file_name + FILE_SYSTEM_PREFIX_LEN (file_name);
1186   while (ISSLASH (*p))
1187     p++;
1188   while (*p)
1189     {
1190       bool slash = ISSLASH (*p);
1191       p++;
1192       if (slash)
1193         {
1194           if (--num == 0)
1195             return p - file_name;
1196           while (ISSLASH (*p))
1197             p++;
1198         }
1199     }
1200   return -1;
1201 }
1202 \f
1203 /* Return nonzero if NAME contains ".." as a file name component.  */
1204 bool
1205 contains_dot_dot (char const *name)
1206 {
1207   char const *p = name + FILE_SYSTEM_PREFIX_LEN (name);
1208
1209   for (;; p++)
1210     {
1211       if (p[0] == '.' && p[1] == '.' && (ISSLASH (p[2]) || !p[2]))
1212         return 1;
1213
1214       while (! ISSLASH (*p))
1215         {
1216           if (! *p++)
1217             return 0;
1218         }
1219     }
1220 }