src/names.c

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