git.gag.com Git - debian/tar/blob - src/names.c

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