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