src/names.c

   1 /* Various processing of names.
   2
   3    Copyright 1988-2023 Free Software Foundation, Inc.
   4
   5    This program is free software; you can redistribute it and/or modify it
   6    under the terms of the GNU General Public License as published by the
   7    Free Software Foundation; either version 3, or (at your option) any later
   8    version.
   9
  10    This program is distributed in the hope that it will be useful, but
  11    WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General
  13    Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License along
  16    with this program.  If not, see <http://www.gnu.org/licenses/>.  */
  17
  18 #include <system.h>
  19
  20 #include <fnmatch.h>
  21 #include <hash.h>
  22 #include <quotearg.h>
  23 #include <wordsplit.h>
  24 #include <argp.h>
  25
  26 #include "common.h"
  27 \f
  28 static void name_add_option (int option, const char *arg);
  29 static void name_add_dir (const char *name);
  30 static void name_add_file (const char *name);
  31 \f
  32 enum
  33   {
  34     ADD_FILE_OPTION = 256,
  35     EXCLUDE_BACKUPS_OPTION,
  36     EXCLUDE_CACHES_OPTION,
  37     EXCLUDE_CACHES_UNDER_OPTION,
  38     EXCLUDE_CACHES_ALL_OPTION,
  39     EXCLUDE_OPTION,
  40     EXCLUDE_IGNORE_OPTION,
  41     EXCLUDE_IGNORE_RECURSIVE_OPTION,
  42     EXCLUDE_TAG_OPTION,
  43     EXCLUDE_TAG_UNDER_OPTION,
  44     EXCLUDE_TAG_ALL_OPTION,
  45     EXCLUDE_VCS_OPTION,
  46     EXCLUDE_VCS_IGNORES_OPTION,
  47     IGNORE_CASE_OPTION,
  48     NO_IGNORE_CASE_OPTION,
  49     ANCHORED_OPTION,
  50     NO_ANCHORED_OPTION,
  51     RECURSION_OPTION,
  52     NO_RECURSION_OPTION,
  53     UNQUOTE_OPTION,
  54     NO_UNQUOTE_OPTION,
  55     NO_VERBATIM_FILES_FROM_OPTION,
  56     NO_WILDCARDS_MATCH_SLASH_OPTION,
  57     NO_WILDCARDS_OPTION,
  58     NULL_OPTION,
  59     NO_NULL_OPTION,
  60     VERBATIM_FILES_FROM_OPTION,
  61     WILDCARDS_MATCH_SLASH_OPTION,
  62     WILDCARDS_OPTION
  63   };
  64
  65 enum
  66   {
  67     GRH_LOCAL,
  68     GRID_LOCAL,
  69     GRH_MATCH,
  70     GRID_MATCH,
  71   };
  72
  73 static struct argp_option names_options[] = {
  74   {NULL, 0, NULL, 0,
  75    N_("Local file name selection:"), GRH_LOCAL },
  76
  77   {"add-file", ADD_FILE_OPTION, N_("FILE"), 0,
  78    N_("add given FILE to the archive (useful if its name starts with a dash)"), GRID_LOCAL },
  79   {"directory", 'C', N_("DIR"), 0,
  80    N_("change to directory DIR"), GRID_LOCAL },
  81   {"files-from", 'T', N_("FILE"), 0,
  82    N_("get names to extract or create from FILE"), GRID_LOCAL },
  83   {"null", NULL_OPTION, 0, 0,
  84    N_("-T reads null-terminated names; implies --verbatim-files-from"),
  85       GRID_LOCAL },
  86   {"no-null", NO_NULL_OPTION, 0, 0,
  87    N_("disable the effect of the previous --null option"), GRID_LOCAL },
  88   {"unquote", UNQUOTE_OPTION, 0, 0,
  89    N_("unquote input file or member names (default)"), GRID_LOCAL },
  90   {"no-unquote", NO_UNQUOTE_OPTION, 0, 0,
  91    N_("do not unquote input file or member names"), GRID_LOCAL },
  92   {"verbatim-files-from", VERBATIM_FILES_FROM_OPTION, 0, 0,
  93    N_("-T reads file names verbatim (no escape or option handling)"), GRID_LOCAL },
  94   {"no-verbatim-files-from", NO_VERBATIM_FILES_FROM_OPTION, 0, 0,
  95    N_("-T treats file names starting with dash as options (default)"),
  96       GRID_LOCAL },
  97   {"exclude", EXCLUDE_OPTION, N_("PATTERN"), 0,
  98    N_("exclude files, given as a PATTERN"), GRID_LOCAL },
  99   {"exclude-from", 'X', N_("FILE"), 0,
 100    N_("exclude patterns listed in FILE"), GRID_LOCAL },
 101   {"exclude-caches", EXCLUDE_CACHES_OPTION, 0, 0,
 102    N_("exclude contents of directories containing CACHEDIR.TAG, "
 103       "except for the tag file itself"), GRID_LOCAL },
 104   {"exclude-caches-under", EXCLUDE_CACHES_UNDER_OPTION, 0, 0,
 105    N_("exclude everything under directories containing CACHEDIR.TAG"),
 106    GRID_LOCAL },
 107   {"exclude-caches-all", EXCLUDE_CACHES_ALL_OPTION, 0, 0,
 108    N_("exclude directories containing CACHEDIR.TAG"), GRID_LOCAL },
 109   {"exclude-tag", EXCLUDE_TAG_OPTION, N_("FILE"), 0,
 110    N_("exclude contents of directories containing FILE, except"
 111       " for FILE itself"), GRID_LOCAL },
 112   {"exclude-ignore", EXCLUDE_IGNORE_OPTION, N_("FILE"), 0,
 113     N_("read exclude patterns for each directory from FILE, if it exists"),
 114    GRID_LOCAL },
 115   {"exclude-ignore-recursive", EXCLUDE_IGNORE_RECURSIVE_OPTION, N_("FILE"), 0,
 116     N_("read exclude patterns for each directory and its subdirectories "
 117        "from FILE, if it exists"), GRID_LOCAL },
 118   {"exclude-tag-under", EXCLUDE_TAG_UNDER_OPTION, N_("FILE"), 0,
 119    N_("exclude everything under directories containing FILE"), GRID_LOCAL },
 120   {"exclude-tag-all", EXCLUDE_TAG_ALL_OPTION, N_("FILE"), 0,
 121    N_("exclude directories containing FILE"), GRID_LOCAL },
 122   {"exclude-vcs", EXCLUDE_VCS_OPTION, NULL, 0,
 123    N_("exclude version control system directories"), GRID_LOCAL },
 124   {"exclude-vcs-ignores", EXCLUDE_VCS_IGNORES_OPTION, NULL, 0,
 125    N_("read exclude patterns from the VCS ignore files"), GRID_LOCAL },
 126   {"exclude-backups", EXCLUDE_BACKUPS_OPTION, NULL, 0,
 127    N_("exclude backup and lock files"), GRID_LOCAL },
 128   {"recursion", RECURSION_OPTION, 0, 0,
 129    N_("recurse into directories (default)"), GRID_LOCAL },
 130   {"no-recursion", NO_RECURSION_OPTION, 0, 0,
 131    N_("avoid descending automatically in directories"), GRID_LOCAL },
 132
 133   {NULL, 0, NULL, 0,
 134    N_("File name matching options (affect both exclude and include patterns):"),
 135    GRH_MATCH },
 136   {"anchored", ANCHORED_OPTION, 0, 0,
 137    N_("patterns match file name start"), GRID_MATCH },
 138   {"no-anchored", NO_ANCHORED_OPTION, 0, 0,
 139    N_("patterns match after any '/' (default for exclusion)"), GRID_MATCH },
 140   {"ignore-case", IGNORE_CASE_OPTION, 0, 0,
 141    N_("ignore case"), GRID_MATCH },
 142   {"no-ignore-case", NO_IGNORE_CASE_OPTION, 0, 0,
 143    N_("case sensitive matching (default)"), GRID_MATCH },
 144   {"wildcards", WILDCARDS_OPTION, 0, 0,
 145    N_("use wildcards (default for exclusion)"), GRID_MATCH },
 146   {"no-wildcards", NO_WILDCARDS_OPTION, 0, 0,
 147    N_("verbatim string matching"), GRID_MATCH },
 148   {"wildcards-match-slash", WILDCARDS_MATCH_SLASH_OPTION, 0, 0,
 149    N_("wildcards match '/' (default for exclusion)"), GRID_MATCH },
 150   {"no-wildcards-match-slash", NO_WILDCARDS_MATCH_SLASH_OPTION, 0, 0,
 151    N_("wildcards do not match '/'"), GRID_MATCH },
 152
 153   {NULL}
 154 };
 155
 156 static struct argp_option const *
 157 file_selection_option (int key)
 158 {
 159   struct argp_option *p;
 160
 161   for (p = names_options;
 162        !(p->name == NULL && p->key == 0 && p->doc == NULL); p++)
 163     if (p->key == key)
 164       return p;
 165   return NULL;
 166 }
 167
 168 static char const *
 169 file_selection_option_name (int key)
 170 {
 171   struct argp_option const *opt = file_selection_option (key);
 172   return opt ? opt->name : NULL;
 173 }
 174
 175 static bool
 176 is_file_selection_option (int key)
 177 {
 178   return file_selection_option (key) != NULL;
 179 }
 180 \f
 181 /* Either NL or NUL, as decided by the --null option.  */
 182 static char filename_terminator = '\n';
 183 /* Treat file names read from -T input verbatim */
 184 static bool verbatim_files_from_option;
 185
 186 static error_t
 187 names_parse_opt (int key, char *arg, struct argp_state *state)
 188 {
 189   switch (key)
 190     {
 191     case 'C':
 192       name_add_dir (arg);
 193       break;
 194
 195     case 'T':
 196       name_add_file (arg);
 197       break;
 198
 199     case ADD_FILE_OPTION:
 200       name_add_name (arg);
 201       break;
 202
 203     case ARGP_KEY_ERROR:
 204       {
 205         struct tar_args *args = state->input;
 206         if (args->loc->source == OPTS_FILE)
 207           {
 208             error (0, 0, _("%s:%lu: unrecognized option"), args->loc->name,
 209                    (unsigned long) args->loc->line);
 210             set_exit_status (TAREXIT_FAILURE);
 211           }
 212         return ARGP_ERR_UNKNOWN;
 213       }
 214
 215     default:
 216       if (is_file_selection_option (key))
 217         name_add_option (key, arg);
 218       else
 219         return ARGP_ERR_UNKNOWN;
 220
 221     }
 222   return 0;
 223 }
 224 \f
 225 /* Wildcard matching settings */
 226 enum wildcards
 227   {
 228     default_wildcards, /* For exclusion == enable_wildcards,
 229                           for inclusion == disable_wildcards */
 230     disable_wildcards,
 231     enable_wildcards
 232   };
 233
 234 static enum wildcards wildcards = default_wildcards;
 235   /* Wildcard settings (--wildcards/--no-wildcards) */
 236 static int matching_flags = 0;
 237   /* exclude_fnmatch options */
 238 static int include_anchored = EXCLUDE_ANCHORED;
 239   /* Pattern anchoring options used for file inclusion */
 240
 241 #define EXCLUDE_OPTIONS                                         \
 242   (((wildcards != disable_wildcards) ? EXCLUDE_WILDCARDS : 0)   \
 243   | matching_flags                                              \
 244   | recursion_option)
 245
 246 #define INCLUDE_OPTIONS                                             \
 247   (((wildcards == enable_wildcards) ? EXCLUDE_WILDCARDS : 0)        \
 248   | include_anchored                                                \
 249   | matching_flags                                                  \
 250   | recursion_option)
 251 \f
 252 static char const * const vcs_file_table[] = {
 253   /* CVS: */
 254   "CVS",
 255   ".cvsignore",
 256   /* RCS: */
 257   "RCS",
 258   /* SCCS: */
 259   "SCCS",
 260   /* SVN: */
 261   ".svn",
 262   /* git: */
 263   ".git",
 264   ".gitignore",
 265   ".gitattributes",
 266   ".gitmodules",
 267   /* Arch: */
 268   ".arch-ids",
 269   "{arch}",
 270   "=RELEASE-ID",
 271   "=meta-update",
 272   "=update",
 273   /* Bazaar */
 274   ".bzr",
 275   ".bzrignore",
 276   ".bzrtags",
 277   /* Mercurial */
 278   ".hg",
 279   ".hgignore",
 280   ".hgtags",
 281   /* darcs */
 282   "_darcs",
 283   NULL
 284 };
 285
 286 static char const * const backup_file_table[] = {
 287   ".#*",
 288   "*~",
 289   "#*#",
 290   NULL
 291 };
 292
 293 static void
 294 add_exclude_array (char const * const * fv, int opts)
 295 {
 296   int i;
 297
 298   for (i = 0; fv[i]; i++)
 299     add_exclude (excluded, fv[i], opts);
 300 }
 301 \f
 302 static void
 303 handle_file_selection_option (int key, const char *arg)
 304 {
 305   switch (key)
 306     {
 307     case EXCLUDE_BACKUPS_OPTION:
 308       add_exclude_array (backup_file_table, EXCLUDE_WILDCARDS);
 309       break;
 310
 311     case EXCLUDE_OPTION:
 312       add_exclude (excluded, arg, EXCLUDE_OPTIONS);
 313       break;
 314
 315     case EXCLUDE_CACHES_OPTION:
 316       add_exclusion_tag ("CACHEDIR.TAG", exclusion_tag_contents,
 317                          cachedir_file_p);
 318       break;
 319
 320     case EXCLUDE_CACHES_UNDER_OPTION:
 321       add_exclusion_tag ("CACHEDIR.TAG", exclusion_tag_under,
 322                          cachedir_file_p);
 323       break;
 324
 325     case EXCLUDE_CACHES_ALL_OPTION:
 326       add_exclusion_tag ("CACHEDIR.TAG", exclusion_tag_all,
 327                          cachedir_file_p);
 328       break;
 329
 330     case EXCLUDE_IGNORE_OPTION:
 331       excfile_add (arg, EXCL_NON_RECURSIVE);
 332       break;
 333
 334     case EXCLUDE_IGNORE_RECURSIVE_OPTION:
 335       excfile_add (arg, EXCL_RECURSIVE);
 336       break;
 337
 338     case EXCLUDE_TAG_OPTION:
 339       add_exclusion_tag (arg, exclusion_tag_contents, NULL);
 340       break;
 341
 342     case EXCLUDE_TAG_UNDER_OPTION:
 343       add_exclusion_tag (arg, exclusion_tag_under, NULL);
 344       break;
 345
 346     case EXCLUDE_TAG_ALL_OPTION:
 347       add_exclusion_tag (arg, exclusion_tag_all, NULL);
 348       break;
 349
 350     case EXCLUDE_VCS_OPTION:
 351       add_exclude_array (vcs_file_table, FNM_LEADING_DIR);
 352       break;
 353
 354     case EXCLUDE_VCS_IGNORES_OPTION:
 355       exclude_vcs_ignores ();
 356       break;
 357
 358     case RECURSION_OPTION:
 359       recursion_option = FNM_LEADING_DIR;
 360       break;
 361
 362     case NO_RECURSION_OPTION:
 363       recursion_option = 0;
 364       break;
 365
 366     case UNQUOTE_OPTION:
 367       unquote_option = true;
 368       break;
 369
 370     case NO_UNQUOTE_OPTION:
 371       unquote_option = false;
 372       break;
 373
 374     case NULL_OPTION:
 375       filename_terminator = '\0';
 376       verbatim_files_from_option = true;
 377       break;
 378
 379     case NO_NULL_OPTION:
 380       filename_terminator = '\n';
 381       verbatim_files_from_option = false;
 382       break;
 383
 384     case 'X':
 385       if (add_exclude_file (add_exclude, excluded, arg, EXCLUDE_OPTIONS, '\n')
 386           != 0)
 387         {
 388           int e = errno;
 389           FATAL_ERROR ((0, e, "%s", quotearg_colon (arg)));
 390         }
 391       break;
 392
 393     case ANCHORED_OPTION:
 394       matching_flags |= EXCLUDE_ANCHORED;
 395       break;
 396
 397     case NO_ANCHORED_OPTION:
 398       include_anchored = 0; /* Clear the default for command line args */
 399       matching_flags &= ~ EXCLUDE_ANCHORED;
 400       break;
 401
 402     case IGNORE_CASE_OPTION:
 403       matching_flags |= FNM_CASEFOLD;
 404       break;
 405
 406     case NO_IGNORE_CASE_OPTION:
 407       matching_flags &= ~ FNM_CASEFOLD;
 408       break;
 409
 410     case WILDCARDS_OPTION:
 411       wildcards = enable_wildcards;
 412       break;
 413
 414     case NO_WILDCARDS_OPTION:
 415       wildcards = disable_wildcards;
 416       break;
 417
 418     case WILDCARDS_MATCH_SLASH_OPTION:
 419       matching_flags &= ~ FNM_FILE_NAME;
 420       break;
 421
 422     case NO_WILDCARDS_MATCH_SLASH_OPTION:
 423       matching_flags |= FNM_FILE_NAME;
 424       break;
 425
 426     case VERBATIM_FILES_FROM_OPTION:
 427       verbatim_files_from_option = true;
 428       break;
 429
 430     case NO_VERBATIM_FILES_FROM_OPTION:
 431       verbatim_files_from_option = false;
 432       break;
 433
 434     default:
 435       FATAL_ERROR ((0, 0, "unhandled positional option %d", key));
 436     }
 437 }
 438
 439 struct argp names_argp = {
 440   names_options,
 441   names_parse_opt,
 442   NULL,
 443   NULL,
 444   NULL,
 445   NULL,
 446   NULL
 447 };
 448
 449 \f
 450 /* User and group names.  */
 451
 452 /* Make sure you link with the proper libraries if you are running the
 453    Yellow Peril (thanks for the good laugh, Ian J.!), or, euh... NIS.
 454    This code should also be modified for non-UNIX systems to do something
 455    reasonable.  */
 456
 457 static char *cached_uname;
 458 static char *cached_gname;
 459
 460 static uid_t cached_uid;        /* valid only if cached_uname is not empty */
 461 static gid_t cached_gid;        /* valid only if cached_gname is not empty */
 462
 463 /* These variables are valid only if nonempty.  */
 464 static char *cached_no_such_uname;
 465 static char *cached_no_such_gname;
 466
 467 /* These variables are valid only if nonzero.  It's not worth optimizing
 468    the case for weird systems where 0 is not a valid uid or gid.  */
 469 static uid_t cached_no_such_uid;
 470 static gid_t cached_no_such_gid;
 471
 472 /* Given UID, find the corresponding UNAME.  */
 473 void
 474 uid_to_uname (uid_t uid, char **uname)
 475 {
 476   struct passwd *passwd;
 477
 478   if (uid != 0 && uid == cached_no_such_uid)
 479     {
 480       *uname = xstrdup ("");
 481       return;
 482     }
 483
 484   if (!cached_uname || uid != cached_uid)
 485     {
 486       passwd = getpwuid (uid);
 487       if (passwd)
 488         {
 489           cached_uid = uid;
 490           assign_string (&cached_uname, passwd->pw_name);
 491         }
 492       else
 493         {
 494           cached_no_such_uid = uid;
 495           *uname = xstrdup ("");
 496           return;
 497         }
 498     }
 499   *uname = xstrdup (cached_uname);
 500 }
 501
 502 /* Given GID, find the corresponding GNAME.  */
 503 void
 504 gid_to_gname (gid_t gid, char **gname)
 505 {
 506   struct group *group;
 507
 508   if (gid != 0 && gid == cached_no_such_gid)
 509     {
 510       *gname = xstrdup ("");
 511       return;
 512     }
 513
 514   if (!cached_gname || gid != cached_gid)
 515     {
 516       group = getgrgid (gid);
 517       if (group)
 518         {
 519           cached_gid = gid;
 520           assign_string (&cached_gname, group->gr_name);
 521         }
 522       else
 523         {
 524           cached_no_such_gid = gid;
 525           *gname = xstrdup ("");
 526           return;
 527         }
 528     }
 529   *gname = xstrdup (cached_gname);
 530 }
 531
 532 /* Given UNAME, set the corresponding UID and return 1, or else, return 0.  */
 533 int
 534 uname_to_uid (char const *uname, uid_t *uidp)
 535 {
 536   struct passwd *passwd;
 537
 538   if (cached_no_such_uname
 539       && strcmp (uname, cached_no_such_uname) == 0)
 540     return 0;
 541
 542   if (!cached_uname
 543       || uname[0] != cached_uname[0]
 544       || strcmp (uname, cached_uname) != 0)
 545     {
 546       passwd = getpwnam (uname);
 547       if (passwd)
 548         {
 549           cached_uid = passwd->pw_uid;
 550           assign_string (&cached_uname, passwd->pw_name);
 551         }
 552       else
 553         {
 554           assign_string (&cached_no_such_uname, uname);
 555           return 0;
 556         }
 557     }
 558   *uidp = cached_uid;
 559   return 1;
 560 }
 561
 562 /* Given GNAME, set the corresponding GID and return 1, or else, return 0.  */
 563 int
 564 gname_to_gid (char const *gname, gid_t *gidp)
 565 {
 566   struct group *group;
 567
 568   if (cached_no_such_gname
 569       && strcmp (gname, cached_no_such_gname) == 0)
 570     return 0;
 571
 572   if (!cached_gname
 573       || gname[0] != cached_gname[0]
 574       || strcmp (gname, cached_gname) != 0)
 575     {
 576       group = getgrnam (gname);
 577       if (group)
 578         {
 579           cached_gid = group->gr_gid;
 580           assign_string (&cached_gname, gname);
 581         }
 582       else
 583         {
 584           assign_string (&cached_no_such_gname, gname);
 585           return 0;
 586         }
 587     }
 588   *gidp = cached_gid;
 589   return 1;
 590 }
 591
 592 \f
 593 static struct name *
 594 make_name (const char *file_name)
 595 {
 596   struct name *p = xzalloc (sizeof (*p));
 597   if (!file_name)
 598     file_name = "";
 599   p->name = xstrdup (file_name);
 600   p->length = strlen (p->name);
 601   return p;
 602 }
 603
 604 static void
 605 free_name (struct name *p)
 606 {
 607   if (p)
 608     {
 609       free (p->name);
 610       free (p->caname);
 611       free (p);
 612     }
 613 }
 614
 615 \f
 616 /* Names from the command call.  */
 617
 618 static struct name *namelist;   /* first name in list, if any */
 619 static struct name *nametail;   /* end of name list */
 620
 621 /* File name arguments are processed in two stages: first a
 622    name element list (see below) is filled, then the names from it
 623    are moved into the namelist.
 624
 625    This awkward process is needed only to implement --same-order option,
 626    which is meant to help process large archives on machines with
 627    limited memory.  With this option on, namelist contains at most one
 628    entry, which diminishes the memory consumption.
 629
 630    However, I very much doubt if we still need this -- Sergey */
 631
 632 /* A name_list element contains entries of three types: */
 633
 634 enum nelt_type
 635   {
 636     NELT_NAME,   /* File name */
 637     NELT_CHDIR,  /* Change directory request */
 638     NELT_FILE,   /* Read file names from that file */
 639     NELT_NOOP,   /* No operation */
 640     NELT_OPTION  /* Filename-selection option */
 641   };
 642
 643 struct name_elt        /* A name_array element. */
 644 {
 645   struct name_elt *next, *prev;
 646   enum nelt_type type; /* Element type, see NELT_* constants above */
 647   union
 648   {
 649     const char *name;  /* File or directory name */
 650     struct             /* File, if type == NELT_FILE */
 651     {
 652       const char *name;/* File name */
 653       size_t line;     /* Input line number */
 654       int term;        /* File name terminator in the list */
 655       bool verbatim;   /* Verbatim handling of file names: no white-space
 656                           trimming, no option processing */
 657       FILE *fp;
 658     } file;
 659     struct
 660     {
 661       int option;
 662       char const *arg;
 663     } opt; /* NELT_OPTION */
 664   } v;
 665 };
 666
 667 static struct name_elt *name_head; /* store a list of names */
 668
 669 /* how many of the entries are file names? */
 670 enum files_count filename_args = FILES_NONE;
 671
 672 static struct name_elt *
 673 name_elt_alloc (void)
 674 {
 675   struct name_elt *elt;
 676
 677   elt = xmalloc (sizeof (*elt));
 678   if (!name_head)
 679     {
 680       name_head = elt;
 681       name_head->prev = name_head->next = NULL;
 682       name_head->type = NELT_NOOP;
 683       elt = xmalloc (sizeof (*elt));
 684     }
 685
 686   elt->prev = name_head->prev;
 687   if (name_head->prev)
 688     name_head->prev->next = elt;
 689   elt->next = name_head;
 690   name_head->prev = elt;
 691   return elt;
 692 }
 693
 694 static void
 695 name_list_adjust (void)
 696 {
 697   if (name_head)
 698     while (name_head->prev)
 699       name_head = name_head->prev;
 700 }
 701 \f
 702 /* For error-reporting purposes, keep a doubly-linked list of unconsumed file
 703    selection options.  The option is deemed unconsumed unless followed by one
 704    or more file/member name arguments.  When archive creation is requested,
 705    each file selection option encountered is pushed into the list.  The list
 706    is cleared upon encountering a file name argument.
 707
 708    If the list is not empty when all arguments have been processed, an error
 709    message is issued reporting the options that had no effect.
 710
 711    For simplicity, only a tail pointer of the list is maintained.
 712 */
 713
 714 struct name_elt *unconsumed_option_tail;
 715
 716 /* Push an option to the list */
 717 static void
 718 unconsumed_option_push (struct name_elt *elt)
 719 {
 720   elt->next = NULL;
 721   elt->prev = unconsumed_option_tail;
 722   if (unconsumed_option_tail)
 723     unconsumed_option_tail->next = elt;
 724   unconsumed_option_tail = elt;
 725 }
 726
 727 /* Clear the unconsumed option list */
 728 static void
 729 unconsumed_option_free (void)
 730 {
 731   while (unconsumed_option_tail)
 732     {
 733       struct name_elt *elt = unconsumed_option_tail;
 734       unconsumed_option_tail = unconsumed_option_tail->prev;
 735       free (elt);
 736     }
 737 }
 738
 739 /* Report any options that have not been consumed */
 740 static void
 741 unconsumed_option_report (void)
 742 {
 743   if (unconsumed_option_tail)
 744     {
 745       struct name_elt *elt;
 746
 747       ERROR ((0, 0, _("The following options were used after any non-optional arguments in archive create or update mode.  These options are positional and affect only arguments that follow them.  Please, rearrange them properly.")));
 748
 749       elt = unconsumed_option_tail;
 750       while (elt->prev)
 751         elt = elt->prev;
 752
 753       while (elt)
 754         {
 755           switch (elt->type)
 756             {
 757             case NELT_CHDIR:
 758               ERROR ((0, 0, _("-C %s has no effect"), quote (elt->v.name)));
 759               break;
 760
 761             case NELT_OPTION:
 762               if (elt->v.opt.arg)
 763                 ERROR ((0, 0, _("--%s %s has no effect"),
 764                         file_selection_option_name (elt->v.opt.option),
 765                         quote (elt->v.opt.arg)));
 766               else
 767                 ERROR ((0, 0, _("--%s has no effect"),
 768                         file_selection_option_name (elt->v.opt.option)));
 769               break;
 770
 771             default:
 772               break;
 773             }
 774           elt = elt->next;
 775         }
 776
 777       unconsumed_option_free ();
 778     }
 779 }
 780 \f
 781 static void
 782 name_list_advance (void)
 783 {
 784   struct name_elt *elt = name_head;
 785   name_head = elt->next;
 786   if (name_head)
 787     name_head->prev = NULL;
 788   if (elt->type == NELT_OPTION || elt->type == NELT_CHDIR)
 789     {
 790       if (subcommand_option == CREATE_SUBCOMMAND
 791           || subcommand_option == UPDATE_SUBCOMMAND)
 792         unconsumed_option_push (elt);
 793     }
 794   else
 795     {
 796       if (elt->type != NELT_NOOP)
 797         unconsumed_option_free ();
 798       free (elt);
 799     }
 800 }
 801
 802 /* Add to name_array the file NAME with fnmatch options MATFLAGS */
 803 void
 804 name_add_name (const char *name)
 805 {
 806   struct name_elt *ep = name_elt_alloc ();
 807
 808   ep->type = NELT_NAME;
 809   ep->v.name = name;
 810
 811   switch (filename_args)
 812     {
 813     case FILES_NONE:
 814       filename_args = FILES_ONE;
 815       break;
 816
 817     case FILES_ONE:
 818       filename_args = FILES_MANY;
 819       break;
 820
 821     default:
 822       break;
 823     }
 824 }
 825
 826 static void
 827 name_add_option (int option, const char *arg)
 828 {
 829   struct name_elt *elt = name_elt_alloc ();
 830   elt->type = NELT_OPTION;
 831   elt->v.opt.option = option;
 832   elt->v.opt.arg = arg;
 833 }
 834
 835 /* Add to name_array a chdir request for the directory NAME */
 836 static void
 837 name_add_dir (const char *name)
 838 {
 839   struct name_elt *ep = name_elt_alloc ();
 840   ep->type = NELT_CHDIR;
 841   ep->v.name = name;
 842 }
 843
 844 static void
 845 name_add_file (const char *name)
 846 {
 847   struct name_elt *ep = name_elt_alloc ();
 848
 849   ep->type = NELT_FILE;
 850   ep->v.file.name = name;
 851   ep->v.file.line = 0;
 852   ep->v.file.fp = NULL;
 853
 854   /* We don't know beforehand how many files are listed.
 855      Assume more than one. */
 856   filename_args = FILES_MANY;
 857 }
 858 \f
 859 /* Names from external name file.  */
 860
 861 static char *name_buffer;       /* buffer to hold the current file name */
 862 static size_t name_buffer_length; /* allocated length of name_buffer */
 863
 864 /* Set up to gather file names for tar.  They can either come from a
 865    file or were saved from decoding arguments.  */
 866 void
 867 name_init (void)
 868 {
 869   name_buffer = xmalloc (NAME_FIELD_SIZE + 2);
 870   name_buffer_length = NAME_FIELD_SIZE;
 871   name_list_adjust ();
 872 }
 873
 874 void
 875 name_term (void)
 876 {
 877   free (name_buffer);
 878 }
 879 \f
 880 /* Prevent recursive inclusion of the same file */
 881 struct file_id_list
 882 {
 883   struct file_id_list *next;
 884   ino_t ino;
 885   dev_t dev;
 886   const char *from_file;
 887 };
 888
 889 static struct file_id_list *file_id_list;
 890
 891 /* Return the name of the file from which the file names and options
 892    are being read.
 893 */
 894 static const char *
 895 file_list_name (void)
 896 {
 897   struct name_elt *elt;
 898
 899   for (elt = name_head; elt; elt = elt->next)
 900     if (elt->type == NELT_FILE && elt->v.file.fp)
 901       return elt->v.file.name;
 902   return _("command line");
 903 }
 904
 905 static int
 906 add_file_id (const char *filename)
 907 {
 908   struct file_id_list *p;
 909   struct stat st;
 910   const char *reading_from;
 911
 912   if (stat (filename, &st))
 913     stat_fatal (filename);
 914   reading_from = file_list_name ();
 915   for (p = file_id_list; p; p = p->next)
 916     if (p->ino == st.st_ino && p->dev == st.st_dev)
 917       {
 918         int oldc = set_char_quoting (NULL, ':', 1);
 919         ERROR ((0, 0,
 920                 _("%s: file list requested from %s already read from %s"),
 921                 quotearg_n (0, filename),
 922                 reading_from, p->from_file));
 923         set_char_quoting (NULL, ':', oldc);
 924         return 1;
 925       }
 926   p = xmalloc (sizeof *p);
 927   p->next = file_id_list;
 928   p->ino = st.st_ino;
 929   p->dev = st.st_dev;
 930   p->from_file = reading_from;
 931   file_id_list = p;
 932   return 0;
 933 }
 934
 935 /* Chop trailing slashes.  */
 936 static void
 937 chopslash (char *str)
 938 {
 939   char *p = str + strlen (str) - 1;
 940   while (p > str && ISSLASH (*p))
 941     *p-- = '\0';
 942 }
 943 \f
 944 enum read_file_list_state  /* Result of reading file name from the list file */
 945   {
 946     file_list_success,     /* OK, name read successfully */
 947     file_list_end,         /* End of list file */
 948     file_list_zero,        /* Zero separator encountered where it should not */
 949     file_list_skip         /* Empty (zero-length) entry encountered, skip it */
 950   };
 951
 952 /* Read from FP a sequence of characters up to TERM and put them
 953    into STK.
 954  */
 955 static enum read_file_list_state
 956 read_name_from_file (struct name_elt *ent)
 957 {
 958   int c;
 959   size_t counter = 0;
 960   FILE *fp = ent->v.file.fp;
 961   int term = ent->v.file.term;
 962
 963   ++ent->v.file.line;
 964   for (c = getc (fp); c != EOF && c != term; c = getc (fp))
 965     {
 966       if (counter == name_buffer_length)
 967         name_buffer = x2realloc (name_buffer, &name_buffer_length);
 968       name_buffer[counter++] = c;
 969       if (c == 0)
 970         {
 971           /* We have read a zero separator. The file possibly is
 972              zero-separated */
 973           return file_list_zero;
 974         }
 975     }
 976
 977   if (counter == 0 && c != EOF)
 978     return file_list_skip;
 979
 980   if (counter == name_buffer_length)
 981     name_buffer = x2realloc (name_buffer, &name_buffer_length);
 982   name_buffer[counter] = 0;
 983   return (counter == 0 && c == EOF) ? file_list_end : file_list_success;
 984 }
 985
 986 static int
 987 handle_option (const char *str, struct name_elt const *ent)
 988 {
 989   struct wordsplit ws;
 990   int i;
 991   struct option_locus loc;
 992
 993   while (*str && isspace (*str))
 994     ++str;
 995   if (*str != '-')
 996     return 1;
 997
 998   ws.ws_offs = 1;
 999   if (wordsplit (str, &ws, WRDSF_DEFFLAGS|WRDSF_DOOFFS))
1000     FATAL_ERROR ((0, 0, _("cannot split string '%s': %s"),
1001                   str, wordsplit_strerror (&ws)));
1002   ws.ws_wordv[0] = (char *) program_name;
1003   loc.source = OPTS_FILE;
1004   loc.name = ent->v.file.name;
1005   loc.line = ent->v.file.line;
1006   more_options (ws.ws_wordc+ws.ws_offs, ws.ws_wordv, &loc);
1007   for (i = 0; i < ws.ws_wordc+ws.ws_offs; i++)
1008     ws.ws_wordv[i] = NULL;
1009
1010   wordsplit_free (&ws);
1011   return 0;
1012 }
1013
1014 static int
1015 read_next_name (struct name_elt *ent, struct name_elt *ret)
1016 {
1017   if (!ent->v.file.fp)
1018     {
1019       if (!strcmp (ent->v.file.name, "-"))
1020         {
1021           request_stdin ("-T");
1022           ent->v.file.fp = stdin;
1023         }
1024       else
1025         {
1026           if (add_file_id (ent->v.file.name))
1027             {
1028               name_list_advance ();
1029               return 1;
1030             }
1031           FILE *fp = fopen (ent->v.file.name, "r");
1032           if (!fp)
1033             open_fatal (ent->v.file.name);
1034           ent->v.file.fp = fp;
1035         }
1036       ent->v.file.term = filename_terminator;
1037       ent->v.file.verbatim = verbatim_files_from_option;
1038     }
1039
1040   while (1)
1041     {
1042       switch (read_name_from_file (ent))
1043         {
1044         case file_list_skip:
1045           continue;
1046
1047         case file_list_zero:
1048           WARNOPT (WARN_FILENAME_WITH_NULS,
1049                    (0, 0, N_("%s: file name read contains nul character"),
1050                     quotearg_colon (ent->v.file.name)));
1051           ent->v.file.term = 0;
1052           FALLTHROUGH;
1053         case file_list_success:
1054           if (!ent->v.file.verbatim)
1055             {
1056               if (unquote_option)
1057                 unquote_string (name_buffer);
1058               if (handle_option (name_buffer, ent) == 0)
1059                 {
1060                   name_list_adjust ();
1061                   return 1;
1062                 }
1063             }
1064           chopslash (name_buffer);
1065           ret->type = NELT_NAME;
1066           ret->v.name = name_buffer;
1067           return 0;
1068
1069         case file_list_end:
1070           if (strcmp (ent->v.file.name, "-"))
1071             fclose (ent->v.file.fp);
1072           ent->v.file.fp = NULL;
1073           name_list_advance ();
1074           return 1;
1075         }
1076     }
1077 }
1078 \f
1079 static void
1080 copy_name (struct name_elt *ep)
1081 {
1082   const char *source;
1083   size_t source_len;
1084
1085   source = ep->v.name;
1086   source_len = strlen (source);
1087   while (name_buffer_length <= source_len)
1088     name_buffer = x2realloc(name_buffer, &name_buffer_length);
1089   strcpy (name_buffer, source);
1090   chopslash (name_buffer);
1091 }
1092
1093 \f
1094 /* Get the next NELT_NAME element from name_array.  Result is in
1095    static storage and can't be relied upon across two calls.
1096
1097    If CHANGE_DIRS is true, treat any entries of type NELT_CHDIR as
1098    the request to change to the given directory.
1099
1100 */
1101 static struct name_elt *
1102 name_next_elt (int change_dirs)
1103 {
1104   static struct name_elt entry;
1105   struct name_elt *ep;
1106
1107   while ((ep = name_head) != NULL)
1108     {
1109       switch (ep->type)
1110         {
1111         case NELT_NOOP:
1112           name_list_advance ();
1113           break;
1114
1115         case NELT_FILE:
1116           if (read_next_name (ep, &entry) == 0)
1117             return &entry;
1118           continue;
1119
1120         case NELT_CHDIR:
1121           if (change_dirs)
1122             {
1123               chdir_do (chdir_arg (xstrdup (ep->v.name)));
1124               name_list_advance ();
1125               break;
1126             }
1127           FALLTHROUGH;
1128         case NELT_NAME:
1129           copy_name (ep);
1130           if (unquote_option)
1131             unquote_string (name_buffer);
1132           entry.type = ep->type;
1133           entry.v.name = name_buffer;
1134           name_list_advance ();
1135           return &entry;
1136
1137         case NELT_OPTION:
1138           handle_file_selection_option (ep->v.opt.option, ep->v.opt.arg);
1139           name_list_advance ();
1140           continue;
1141         }
1142     }
1143
1144   unconsumed_option_report ();
1145
1146   return NULL;
1147 }
1148
1149 const char *
1150 name_next (int change_dirs)
1151 {
1152   struct name_elt *nelt = name_next_elt (change_dirs);
1153   return nelt ? nelt->v.name : NULL;
1154 }
1155
1156 /* Gather names in a list for scanning.  Could hash them later if we
1157    really care.
1158
1159    If the names are already sorted to match the archive, we just read
1160    them one by one.  name_gather reads the first one, and it is called
1161    by name_match as appropriate to read the next ones.  At EOF, the
1162    last name read is just left in the buffer.  This option lets users
1163    of small machines extract an arbitrary number of files by doing
1164    "tar t" and editing down the list of files.  */
1165
1166 void
1167 name_gather (void)
1168 {
1169   /* Buffer able to hold a single name.  */
1170   static struct name *buffer = NULL;
1171
1172   struct name_elt *ep;
1173
1174   if (same_order_option)
1175     {
1176       static int change_dir;
1177
1178       while ((ep = name_next_elt (0)) && ep->type == NELT_CHDIR)
1179         change_dir = chdir_arg (xstrdup (ep->v.name));
1180
1181       if (ep)
1182         {
1183           free_name (buffer);
1184           buffer = make_name (ep->v.name);
1185           buffer->change_dir = change_dir;
1186           buffer->next = 0;
1187           buffer->found_count = 0;
1188           buffer->matching_flags = INCLUDE_OPTIONS;
1189           buffer->directory = NULL;
1190           buffer->parent = NULL;
1191           buffer->cmdline = true;
1192
1193           namelist = nametail = buffer;
1194         }
1195       else if (change_dir)
1196         addname (0, change_dir, false, NULL);
1197     }
1198   else
1199     {
1200       /* Non sorted names -- read them all in.  */
1201       int change_dir = 0;
1202
1203       for (;;)
1204         {
1205           int change_dir0 = change_dir;
1206           while ((ep = name_next_elt (0)) && ep->type == NELT_CHDIR)
1207             change_dir = chdir_arg (xstrdup (ep->v.name));
1208
1209           if (ep)
1210             addname (ep->v.name, change_dir, true, NULL);
1211           else
1212             {
1213               if (change_dir != change_dir0)
1214                 addname (NULL, change_dir, false, NULL);
1215               break;
1216             }
1217         }
1218     }
1219 }
1220
1221 /*  Add a name to the namelist.  */
1222 struct name *
1223 addname (char const *string, int change_dir, bool cmdline, struct name *parent)
1224 {
1225   struct name *name = make_name (string);
1226
1227   name->prev = nametail;
1228   name->next = NULL;
1229   name->found_count = 0;
1230   name->matching_flags = INCLUDE_OPTIONS;
1231   name->change_dir = change_dir;
1232   name->directory = NULL;
1233   name->parent = parent;
1234   name->cmdline = cmdline;
1235
1236   if (nametail)
1237     nametail->next = name;
1238   else
1239     namelist = name;
1240   nametail = name;
1241   return name;
1242 }
1243
1244 void
1245 add_starting_file (char const *file_name)
1246 {
1247   struct name *name = make_name (file_name);
1248
1249   if (starting_file_option)
1250     {
1251       struct name *head = namelist;
1252       remname (head);
1253       free_name (head);
1254     }
1255
1256   name->prev = NULL;
1257   name->next = namelist;
1258   namelist = name;
1259   if (!nametail)
1260     nametail = namelist;
1261
1262   name->found_count = 0;
1263   name->matching_flags = INCLUDE_OPTIONS;
1264   name->change_dir = 0;
1265   name->directory = NULL;
1266   name->parent = NULL;
1267   name->cmdline = true;
1268
1269   starting_file_option = true;
1270 }
1271
1272 /* Find a match for FILE_NAME (whose string length is LENGTH) in the name
1273    list.  */
1274 static struct name *
1275 namelist_match (char const *file_name, size_t length)
1276 {
1277   struct name *p;
1278
1279   for (p = namelist; p; p = p->next)
1280     {
1281       if (p->name[0]
1282           && exclude_fnmatch (p->name, file_name, p->matching_flags))
1283         return p;
1284     }
1285
1286   return NULL;
1287 }
1288
1289 void
1290 remname (struct name *name)
1291 {
1292   struct name *p;
1293
1294   if ((p = name->prev) != NULL)
1295     p->next = name->next;
1296   else
1297     namelist = name->next;
1298
1299   if ((p = name->next) != NULL)
1300     p->prev = name->prev;
1301   else
1302     nametail = name->prev;
1303 }
1304
1305 /* Return true if and only if name FILE_NAME (from an archive) matches any
1306    name from the namelist.  */
1307 bool
1308 name_match (const char *file_name)
1309 {
1310   size_t length = strlen (file_name);
1311
1312   while (1)
1313     {
1314       struct name *cursor = namelist;
1315
1316       if (!cursor)
1317         return true;
1318
1319       if (cursor->name[0] == 0)
1320         {
1321           chdir_do (cursor->change_dir);
1322           namelist = NULL;
1323           nametail = NULL;
1324           return true;
1325         }
1326
1327       cursor = namelist_match (file_name, length);
1328       if (starting_file_option)
1329         {
1330           /* If starting_file_option is set, the head of the list is the name
1331              of the member to start extraction from. Skip the match unless it
1332              is head. */
1333           if (cursor == namelist)
1334             starting_file_option = false;
1335           else
1336             cursor = NULL;
1337         }
1338       if (cursor)
1339         {
1340           if (!(ISSLASH (file_name[cursor->length]) && recursion_option)
1341               || cursor->found_count == 0)
1342             cursor->found_count++; /* remember it matched */
1343           chdir_do (cursor->change_dir);
1344           /* We got a match.  */
1345           return ISFOUND (cursor);
1346         }
1347
1348       /* Filename from archive not found in namelist.  If we have the whole
1349          namelist here, just return 0.  Otherwise, read the next name in and
1350          compare it.  If this was the last name, namelist->found_count will
1351          remain on.  If not, we loop to compare the newly read name.  */
1352
1353       if (same_order_option && namelist->found_count)
1354         {
1355           name_gather ();       /* read one more */
1356           if (namelist->found_count)
1357             return false;
1358         }
1359       else
1360         return false;
1361     }
1362 }
1363
1364 /* Returns true if all names from the namelist were processed.
1365    P is the stat_info of the most recently processed entry.
1366    The decision is postponed until the next entry is read if:
1367
1368    1) P ended with a slash (i.e. it was a directory)
1369    2) P matches any entry from the namelist *and* represents a subdirectory
1370    or a file lying under this entry (in the terms of directory structure).
1371
1372    This is necessary to handle contents of directories. */
1373 bool
1374 all_names_found (struct tar_stat_info *p)
1375 {
1376   struct name const *cursor;
1377   size_t len;
1378
1379   if (!p->file_name || occurrence_option == 0 || p->had_trailing_slash)
1380     return false;
1381   len = strlen (p->file_name);
1382   for (cursor = namelist; cursor; cursor = cursor->next)
1383     {
1384       if ((cursor->name[0] && !WASFOUND (cursor))
1385           || (len >= cursor->length && ISSLASH (p->file_name[cursor->length])))
1386         return false;
1387     }
1388   return true;
1389 }
1390
1391 static int
1392 regex_usage_warning (const char *name)
1393 {
1394   static int warned_once = 0;
1395
1396   /* Warn about implicit use of the wildcards in command line arguments.
1397      (Default for tar prior to 1.15.91, but changed afterwards) */
1398   if (wildcards == default_wildcards
1399       && fnmatch_pattern_has_wildcards (name, 0))
1400     {
1401       warned_once = 1;
1402       WARN ((0, 0,
1403              _("Pattern matching characters used in file names")));
1404       WARN ((0, 0,
1405              _("Use --wildcards to enable pattern matching,"
1406                " or --no-wildcards to suppress this warning")));
1407     }
1408   return warned_once;
1409 }
1410
1411 /* Print the names of things in the namelist that were not matched.  */
1412 void
1413 names_notfound (void)
1414 {
1415   struct name const *cursor;
1416
1417   for (cursor = namelist; cursor; cursor = cursor->next)
1418     if (!WASFOUND (cursor) && cursor->name[0])
1419       {
1420         regex_usage_warning (cursor->name);
1421         ERROR ((0, 0,
1422                 (cursor->found_count == 0) ?
1423                      _("%s: Not found in archive") :
1424                      _("%s: Required occurrence not found in archive"),
1425                 quotearg_colon (cursor->name)));
1426       }
1427
1428   /* Don't bother freeing the name list; we're about to exit.  */
1429   namelist = NULL;
1430   nametail = NULL;
1431
1432   if (same_order_option)
1433     {
1434       const char *name;
1435
1436       while ((name = name_next (1)) != NULL)
1437         {
1438           regex_usage_warning (name);
1439           ERROR ((0, 0, _("%s: Not found in archive"),
1440                   quotearg_colon (name)));
1441         }
1442     }
1443 }
1444
1445 void
1446 label_notfound (void)
1447 {
1448   struct name const *cursor;
1449
1450   if (!namelist)
1451     return;
1452
1453   for (cursor = namelist; cursor; cursor = cursor->next)
1454     if (WASFOUND (cursor))
1455       return;
1456
1457   if (verbose_option)
1458     error (0, 0, _("Archive label mismatch"));
1459   set_exit_status (TAREXIT_DIFFERS);
1460
1461   for (cursor = namelist; cursor; cursor = cursor->next)
1462     {
1463       if (regex_usage_warning (cursor->name))
1464         break;
1465     }
1466
1467   /* Don't bother freeing the name list; we're about to exit.  */
1468   namelist = NULL;
1469   nametail = NULL;
1470
1471   if (same_order_option)
1472     {
1473       const char *name;
1474
1475       while ((name = name_next (1)) != NULL
1476              && regex_usage_warning (name) == 0)
1477         ;
1478     }
1479 }
1480 \f
1481 /* Sorting name lists.  */
1482
1483 /* Sort *singly* linked LIST of names, of given LENGTH, using COMPARE
1484    to order names.  Return the sorted list.  Note that after calling
1485    this function, the 'prev' links in list elements are messed up.
1486
1487    Apart from the type 'struct name' and the definition of SUCCESSOR,
1488    this is a generic list-sorting function, but it's too painful to
1489    make it both generic and portable
1490    in C.  */
1491
1492 static struct name *
1493 merge_sort_sll (struct name *list, int length,
1494                 int (*compare) (struct name const*, struct name const*))
1495 {
1496   struct name *first_list;
1497   struct name *second_list;
1498   int first_length;
1499   int second_length;
1500   struct name *result;
1501   struct name **merge_point;
1502   struct name *cursor;
1503   int counter;
1504
1505 # define SUCCESSOR(name) ((name)->next)
1506
1507   if (length == 1)
1508     return list;
1509
1510   if (length == 2)
1511     {
1512       if ((*compare) (list, SUCCESSOR (list)) > 0)
1513         {
1514           result = SUCCESSOR (list);
1515           SUCCESSOR (result) = list;
1516           SUCCESSOR (list) = 0;
1517           return result;
1518         }
1519       return list;
1520     }
1521
1522   first_list = list;
1523   first_length = (length + 1) / 2;
1524   second_length = length / 2;
1525   for (cursor = list, counter = first_length - 1;
1526        counter;
1527        cursor = SUCCESSOR (cursor), counter--)
1528     continue;
1529   second_list = SUCCESSOR (cursor);
1530   SUCCESSOR (cursor) = 0;
1531
1532   first_list = merge_sort_sll (first_list, first_length, compare);
1533   second_list = merge_sort_sll (second_list, second_length, compare);
1534
1535   merge_point = &result;
1536   while (first_list && second_list)
1537     if ((*compare) (first_list, second_list) < 0)
1538       {
1539         cursor = SUCCESSOR (first_list);
1540         *merge_point = first_list;
1541         merge_point = &SUCCESSOR (first_list);
1542         first_list = cursor;
1543       }
1544     else
1545       {
1546         cursor = SUCCESSOR (second_list);
1547         *merge_point = second_list;
1548         merge_point = &SUCCESSOR (second_list);
1549         second_list = cursor;
1550       }
1551   if (first_list)
1552     *merge_point = first_list;
1553   else
1554     *merge_point = second_list;
1555
1556   return result;
1557
1558 #undef SUCCESSOR
1559 }
1560
1561 /* Sort doubly linked LIST of names, of given LENGTH, using COMPARE
1562    to order names.  Return the sorted list.  */
1563 static struct name *
1564 merge_sort (struct name *list, int length,
1565             int (*compare) (struct name const*, struct name const*))
1566 {
1567   struct name *head, *p, *prev;
1568   head = merge_sort_sll (list, length, compare);
1569   /* Fixup prev pointers */
1570   for (prev = NULL, p = head; p; prev = p, p = p->next)
1571     p->prev = prev;
1572   return head;
1573 }
1574
1575 /* A comparison function for sorting names.  Put found names last;
1576    break ties by string comparison.  */
1577
1578 static int
1579 compare_names_found (struct name const *n1, struct name const *n2)
1580 {
1581   int found_diff = WASFOUND (n2) - WASFOUND (n1);
1582   return found_diff ? found_diff : strcmp (n1->name, n2->name);
1583 }
1584
1585 /* Simple comparison by names. */
1586 static int
1587 compare_names (struct name const *n1, struct name const *n2)
1588 {
1589   return strcmp (n1->name, n2->name);
1590 }
1591
1592 \f
1593 /* Add all the dirs under ST to the namelist NAME, descending the
1594    directory hierarchy recursively.  */
1595
1596 static void
1597 add_hierarchy_to_namelist (struct tar_stat_info *st, struct name *name)
1598 {
1599   const char *buffer;
1600
1601   name->directory = scan_directory (st);
1602   buffer = directory_contents (name->directory);
1603   if (buffer)
1604     {
1605       struct name *child_head = NULL, *child_tail = NULL;
1606       size_t name_length = name->length;
1607       size_t allocated_length = (name_length >= NAME_FIELD_SIZE
1608                                  ? name_length + NAME_FIELD_SIZE
1609                                  : NAME_FIELD_SIZE) + 2;
1610       char *namebuf = xmalloc (allocated_length);
1611       const char *string;
1612       size_t string_length;
1613       int change_dir = name->change_dir;
1614
1615       strcpy (namebuf, name->name);
1616       if (! ISSLASH (namebuf[name_length - 1]))
1617         {
1618           namebuf[name_length++] = '/';
1619           namebuf[name_length] = '\0';
1620         }
1621
1622       for (string = buffer; *string; string += string_length + 1)
1623         {
1624           string_length = strlen (string);
1625           if (*string == 'D')
1626             {
1627               struct name *np;
1628               struct tar_stat_info subdir;
1629               int subfd;
1630
1631               /* need to have at least string_length bytes above the
1632                  name_length, this includes the trailing null character */
1633               while (allocated_length < name_length + string_length)
1634                 namebuf = x2realloc (namebuf, &allocated_length);
1635               strcpy (namebuf + name_length, string + 1);
1636               np = addname (namebuf, change_dir, false, name);
1637               if (!child_head)
1638                 child_head = np;
1639               else
1640                 child_tail->sibling = np;
1641               child_tail = np;
1642
1643               tar_stat_init (&subdir);
1644               subdir.parent = st;
1645               if (st->fd < 0)
1646                 {
1647                   subfd = -1;
1648                   errno = - st->fd;
1649                 }
1650               else
1651                 subfd = subfile_open (st, string + 1,
1652                                       open_read_flags | O_DIRECTORY);
1653               if (subfd < 0)
1654                 open_diag (namebuf);
1655               else
1656                 {
1657                   subdir.fd = subfd;
1658                   if (fstat (subfd, &subdir.stat) != 0)
1659                     stat_diag (namebuf);
1660                   else if (! (O_DIRECTORY || S_ISDIR (subdir.stat.st_mode)))
1661                     {
1662                       errno = ENOTDIR;
1663                       open_diag (namebuf);
1664                     }
1665                   else
1666                     {
1667                       subdir.orig_file_name = xstrdup (namebuf);
1668                       add_hierarchy_to_namelist (&subdir, np);
1669                       restore_parent_fd (&subdir);
1670                     }
1671                 }
1672
1673               tar_stat_destroy (&subdir);
1674             }
1675         }
1676
1677       free (namebuf);
1678       name->child = child_head;
1679     }
1680 }
1681 \f
1682 /* Auxiliary functions for hashed table of struct name's. */
1683
1684 static size_t
1685 name_hash (void const *entry, size_t n_buckets)
1686 {
1687   struct name const *name = entry;
1688   return hash_string (name->caname, n_buckets);
1689 }
1690
1691 /* Compare two directories for equality of their names. */
1692 static bool
1693 name_compare (void const *entry1, void const *entry2)
1694 {
1695   struct name const *name1 = entry1;
1696   struct name const *name2 = entry2;
1697   return strcmp (name1->caname, name2->caname) == 0;
1698 }
1699
1700 \f
1701 /* Rebase 'name' member of CHILD and all its siblings to
1702    the new PARENT. */
1703 static void
1704 rebase_child_list (struct name *child, struct name *parent)
1705 {
1706   size_t old_prefix_len = child->parent->length;
1707   size_t new_prefix_len = parent->length;
1708   char *new_prefix = parent->name;
1709
1710   for (; child; child = child->sibling)
1711     {
1712       size_t size = child->length - old_prefix_len + new_prefix_len;
1713       char *newp = xmalloc (size + 1);
1714       strcpy (newp, new_prefix);
1715       strcat (newp, child->name + old_prefix_len);
1716       free (child->name);
1717       child->name = newp;
1718       child->length = size;
1719
1720       rebase_directory (child->directory,
1721                         child->parent->name, old_prefix_len,
1722                         new_prefix, new_prefix_len);
1723     }
1724 }
1725
1726 /* Collect all the names from argv[] (or whatever), expand them into a
1727    directory tree, and sort them.  This gets only subdirectories, not
1728    all files.  */
1729
1730 void
1731 collect_and_sort_names (void)
1732 {
1733   struct name *name;
1734   struct name *next_name, *prev_name = NULL;
1735   int num_names;
1736   Hash_table *nametab;
1737
1738   name_gather ();
1739
1740   if (!namelist)
1741     addname (".", 0, false, NULL);
1742
1743   if (listed_incremental_option)
1744     {
1745       switch (chdir_count ())
1746         {
1747         case 0:
1748           break;
1749
1750         case 1:
1751           if (namelist->change_dir == 0)
1752             USAGE_ERROR ((0, 0,
1753                           _("Using -C option inside file list is not "
1754                             "allowed with --listed-incremental")));
1755           break;
1756
1757         default:
1758           USAGE_ERROR ((0, 0,
1759                         _("Only one -C option is allowed with "
1760                           "--listed-incremental")));
1761         }
1762
1763       read_directory_file ();
1764     }
1765
1766   num_names = 0;
1767   for (name = namelist; name; name = name->next, num_names++)
1768     {
1769       struct tar_stat_info st;
1770
1771       if (name->found_count || name->directory)
1772         continue;
1773       if (name->matching_flags & EXCLUDE_WILDCARDS)
1774         /* NOTE: EXCLUDE_ANCHORED is not relevant here */
1775         /* FIXME: just skip regexps for now */
1776         continue;
1777       chdir_do (name->change_dir);
1778
1779       if (name->name[0] == 0)
1780         continue;
1781
1782       tar_stat_init (&st);
1783
1784       if (deref_stat (name->name, &st.stat) != 0)
1785         {
1786           stat_diag (name->name);
1787           continue;
1788         }
1789       if (S_ISDIR (st.stat.st_mode))
1790         {
1791           int dir_fd = openat (chdir_fd, name->name,
1792                                open_read_flags | O_DIRECTORY);
1793           if (dir_fd < 0)
1794             open_diag (name->name);
1795           else
1796             {
1797               st.fd = dir_fd;
1798               if (fstat (dir_fd, &st.stat) != 0)
1799                 stat_diag (name->name);
1800               else if (O_DIRECTORY || S_ISDIR (st.stat.st_mode))
1801                 {
1802                   st.orig_file_name = xstrdup (name->name);
1803                   name->found_count++;
1804                   add_hierarchy_to_namelist (&st, name);
1805                 }
1806               else
1807                 {
1808                   errno = ENOTDIR;
1809                   open_diag (name->name);
1810                 }
1811             }
1812         }
1813
1814       tar_stat_destroy (&st);
1815     }
1816
1817   namelist = merge_sort (namelist, num_names, compare_names);
1818
1819   num_names = 0;
1820   nametab = hash_initialize (0, 0, name_hash, name_compare, NULL);
1821   for (name = namelist; name; name = next_name)
1822     {
1823       next_name = name->next;
1824       name->caname = normalize_filename (name->change_dir, name->name);
1825       if (prev_name)
1826         {
1827           struct name *p = hash_lookup (nametab, name);
1828           if (p)
1829             {
1830               /* Keep the one listed in the command line */
1831               if (!name->parent)
1832                 {
1833                   if (p->child)
1834                     rebase_child_list (p->child, name);
1835                   hash_remove (nametab, name);
1836                   /* FIXME: remove_directory (p->caname); ? */
1837                   remname (p);
1838                   free_name (p);
1839                   num_names--;
1840                 }
1841               else
1842                 {
1843                   if (name->child)
1844                     rebase_child_list (name->child, p);
1845                   /* FIXME: remove_directory (name->caname); ? */
1846                   remname (name);
1847                   free_name (name);
1848                   continue;
1849                 }
1850             }
1851         }
1852       name->found_count = 0;
1853       if (!hash_insert (nametab, name))
1854         xalloc_die ();
1855       prev_name = name;
1856       num_names++;
1857     }
1858   nametail = prev_name;
1859   hash_free (nametab);
1860
1861   namelist = merge_sort (namelist, num_names, compare_names_found);
1862
1863   if (listed_incremental_option)
1864     {
1865       for (name = namelist; name && name->name[0] == 0; name = name->next)
1866         ;
1867       if (name)
1868         append_incremental_renames (name->directory);
1869     }
1870 }
1871
1872 /* This is like name_match, except that
1873     1. It returns a pointer to the name it matched, and doesn't set FOUND
1874     in structure. The caller will have to do that if it wants to.
1875     2. If the namelist is empty, it returns null, unlike name_match, which
1876     returns TRUE. */
1877 struct name *
1878 name_scan (const char *file_name)
1879 {
1880   size_t length = strlen (file_name);
1881
1882   while (1)
1883     {
1884       struct name *cursor = namelist_match (file_name, length);
1885       if (cursor)
1886         return cursor;
1887
1888       /* Filename from archive not found in namelist.  If we have the whole
1889          namelist here, just return 0.  Otherwise, read the next name in and
1890          compare it.  If this was the last name, namelist->found_count will
1891          remain on.  If not, we loop to compare the newly read name.  */
1892
1893       if (same_order_option && namelist && namelist->found_count)
1894         {
1895           name_gather ();       /* read one more */
1896           if (namelist->found_count)
1897             return 0;
1898         }
1899       else
1900         return 0;
1901     }
1902 }
1903
1904 /* This returns a name from the namelist which doesn't have ->found
1905    set.  It sets ->found before returning, so successive calls will
1906    find and return all the non-found names in the namelist.  */
1907 struct name *gnu_list_name;
1908
1909 struct name const *
1910 name_from_list (void)
1911 {
1912   if (!gnu_list_name)
1913     gnu_list_name = namelist;
1914   while (gnu_list_name
1915          && (gnu_list_name->found_count || gnu_list_name->name[0] == 0))
1916     gnu_list_name = gnu_list_name->next;
1917   if (gnu_list_name)
1918     {
1919       gnu_list_name->found_count++;
1920       chdir_do (gnu_list_name->change_dir);
1921       return gnu_list_name;
1922     }
1923   return NULL;
1924 }
1925
1926 void
1927 blank_name_list (void)
1928 {
1929   struct name *name;
1930
1931   gnu_list_name = 0;
1932   for (name = namelist; name; name = name->next)
1933     name->found_count = 0;
1934 }
1935
1936 /* Yield a newly allocated file name consisting of DIR_NAME concatenated to
1937    NAME, with an intervening slash if DIR_NAME does not already end in one. */
1938 char *
1939 make_file_name (const char *directory_name, const char *name)
1940 {
1941   size_t dirlen = strlen (directory_name);
1942   size_t namelen = strlen (name) + 1;
1943   int slash = dirlen && ! ISSLASH (directory_name[dirlen - 1]);
1944   char *buffer = xmalloc (dirlen + slash + namelen);
1945   memcpy (buffer, directory_name, dirlen);
1946   buffer[dirlen] = '/';
1947   memcpy (buffer + dirlen + slash, name, namelen);
1948   return buffer;
1949 }
1950
1951 \f
1952
1953 /* Return the size of the prefix of FILE_NAME that is removed after
1954    stripping NUM leading file name components.  NUM must be
1955    positive.  */
1956
1957 size_t
1958 stripped_prefix_len (char const *file_name, size_t num)
1959 {
1960   char const *p = file_name + FILE_SYSTEM_PREFIX_LEN (file_name);
1961   while (ISSLASH (*p))
1962     p++;
1963   while (*p)
1964     {
1965       bool slash = ISSLASH (*p);
1966       p++;
1967       if (slash)
1968         {
1969           if (--num == 0)
1970             return p - file_name;
1971           while (ISSLASH (*p))
1972             p++;
1973         }
1974     }
1975   return -1;
1976 }
1977 \f
1978 /* Return nonzero if NAME contains ".." as a file name component.  */
1979 bool
1980 contains_dot_dot (char const *name)
1981 {
1982   char const *p = name + FILE_SYSTEM_PREFIX_LEN (name);
1983
1984   for (;; p++)
1985     {
1986       if (p[0] == '.' && p[1] == '.' && (ISSLASH (p[2]) || !p[2]))
1987         return 1;
1988
1989       while (! ISSLASH (*p))
1990         {
1991           if (! *p++)
1992             return 0;
1993         }
1994     }
1995 }