contrib/libarchive/libarchive/archive_match.c

   1 /*-
   2  * Copyright (c) 2003-2007 Tim Kientzle
   3  * Copyright (c) 2012 Michihiro NAKAJIMA
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the distribution.
  14  *
  15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR
  16  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  17  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  18  * IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT,
  19  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  20  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  21  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  22  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  24  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25  */
  26
  27 #include "archive_platform.h"
  28 __FBSDID("$FreeBSD$");
  29
  30 #ifdef HAVE_ERRNO_H
  31 #include <errno.h>
  32 #endif
  33 #ifdef HAVE_STDLIB_H
  34 #include <stdlib.h>
  35 #endif
  36 #ifdef HAVE_STRING_H
  37 #include <string.h>
  38 #endif
  39
  40 #include "archive.h"
  41 #include "archive_private.h"
  42 #include "archive_entry.h"
  43 #include "archive_getdate.h"
  44 #include "archive_pathmatch.h"
  45 #include "archive_rb.h"
  46 #include "archive_string.h"
  47
  48 struct match {
  49         struct match            *next;
  50         int                      matches;
  51         struct archive_mstring   pattern;
  52 };
  53
  54 struct match_list {
  55         struct match            *first;
  56         struct match            **last;
  57         int                      count;
  58         int                      unmatched_count;
  59         struct match            *unmatched_next;
  60         int                      unmatched_eof;
  61 };
  62
  63 struct match_file {
  64         struct archive_rb_node   node;
  65         struct match_file       *next;
  66         struct archive_mstring   pathname;
  67         int                      flag;
  68         time_t                   mtime_sec;
  69         long                     mtime_nsec;
  70         time_t                   ctime_sec;
  71         long                     ctime_nsec;
  72 };
  73
  74 struct entry_list {
  75         struct match_file       *first;
  76         struct match_file       **last;
  77         int                      count;
  78 };
  79
  80 struct id_array {
  81         size_t                   size;/* Allocated size */
  82         size_t                   count;
  83         int64_t                 *ids;
  84 };
  85
  86 #define PATTERN_IS_SET          1
  87 #define TIME_IS_SET             2
  88 #define ID_IS_SET               4
  89
  90 struct archive_match {
  91         struct archive           archive;
  92
  93         /* exclusion/inclusion set flag. */
  94         int                      setflag;
  95
  96         /* Recursively include directory content? */
  97         int                      recursive_include;
  98
  99         /*
 100          * Matching filename patterns.
 101          */
 102         struct match_list        exclusions;
 103         struct match_list        inclusions;
 104
 105         /*
 106          * Matching time stamps.
 107          */
 108         time_t                   now;
 109         int                      newer_mtime_filter;
 110         time_t                   newer_mtime_sec;
 111         long                     newer_mtime_nsec;
 112         int                      newer_ctime_filter;
 113         time_t                   newer_ctime_sec;
 114         long                     newer_ctime_nsec;
 115         int                      older_mtime_filter;
 116         time_t                   older_mtime_sec;
 117         long                     older_mtime_nsec;
 118         int                      older_ctime_filter;
 119         time_t                   older_ctime_sec;
 120         long                     older_ctime_nsec;
 121         /*
 122          * Matching time stamps with its filename.
 123          */
 124         struct archive_rb_tree   exclusion_tree;
 125         struct entry_list        exclusion_entry_list;
 126
 127         /*
 128          * Matching file owners.
 129          */
 130         struct id_array          inclusion_uids;
 131         struct id_array          inclusion_gids;
 132         struct match_list        inclusion_unames;
 133         struct match_list        inclusion_gnames;
 134 };
 135
 136 static int      add_pattern_from_file(struct archive_match *,
 137                     struct match_list *, int, const void *, int);
 138 static int      add_entry(struct archive_match *, int,
 139                     struct archive_entry *);
 140 static int      add_owner_id(struct archive_match *, struct id_array *,
 141                     int64_t);
 142 static int      add_owner_name(struct archive_match *, struct match_list *,
 143                     int, const void *);
 144 static int      add_pattern_mbs(struct archive_match *, struct match_list *,
 145                     const char *);
 146 static int      add_pattern_wcs(struct archive_match *, struct match_list *,
 147                     const wchar_t *);
 148 static int      cmp_key_mbs(const struct archive_rb_node *, const void *);
 149 static int      cmp_key_wcs(const struct archive_rb_node *, const void *);
 150 static int      cmp_node_mbs(const struct archive_rb_node *,
 151                     const struct archive_rb_node *);
 152 static int      cmp_node_wcs(const struct archive_rb_node *,
 153                     const struct archive_rb_node *);
 154 static void     entry_list_add(struct entry_list *, struct match_file *);
 155 static void     entry_list_free(struct entry_list *);
 156 static void     entry_list_init(struct entry_list *);
 157 static int      error_nomem(struct archive_match *);
 158 static void     match_list_add(struct match_list *, struct match *);
 159 static void     match_list_free(struct match_list *);
 160 static void     match_list_init(struct match_list *);
 161 static int      match_list_unmatched_inclusions_next(struct archive_match *,
 162                     struct match_list *, int, const void **);
 163 static int      match_owner_id(struct id_array *, int64_t);
 164 #if !defined(_WIN32) || defined(__CYGWIN__)
 165 static int      match_owner_name_mbs(struct archive_match *,
 166                     struct match_list *, const char *);
 167 #else
 168 static int      match_owner_name_wcs(struct archive_match *,
 169                     struct match_list *, const wchar_t *);
 170 #endif
 171 static int      match_path_exclusion(struct archive_match *,
 172                     struct match *, int, const void *);
 173 static int      match_path_inclusion(struct archive_match *,
 174                     struct match *, int, const void *);
 175 static int      owner_excluded(struct archive_match *,
 176                     struct archive_entry *);
 177 static int      path_excluded(struct archive_match *, int, const void *);
 178 static int      set_timefilter(struct archive_match *, int, time_t, long,
 179                     time_t, long);
 180 static int      set_timefilter_pathname_mbs(struct archive_match *,
 181                     int, const char *);
 182 static int      set_timefilter_pathname_wcs(struct archive_match *,
 183                     int, const wchar_t *);
 184 static int      set_timefilter_date(struct archive_match *, int, const char *);
 185 static int      set_timefilter_date_w(struct archive_match *, int,
 186                     const wchar_t *);
 187 static int      time_excluded(struct archive_match *,
 188                     struct archive_entry *);
 189 static int      validate_time_flag(struct archive *, int, const char *);
 190
 191 #define get_date __archive_get_date
 192
 193 static const struct archive_rb_tree_ops rb_ops_mbs = {
 194         cmp_node_mbs, cmp_key_mbs
 195 };
 196
 197 static const struct archive_rb_tree_ops rb_ops_wcs = {
 198         cmp_node_wcs, cmp_key_wcs
 199 };
 200
 201 /*
 202  * The matching logic here needs to be re-thought.  I started out to
 203  * try to mimic gtar's matching logic, but it's not entirely
 204  * consistent.  In particular 'tar -t' and 'tar -x' interpret patterns
 205  * on the command line as anchored, but --exclude doesn't.
 206  */
 207
 208 static int
 209 error_nomem(struct archive_match *a)
 210 {
 211         archive_set_error(&(a->archive), ENOMEM, "No memory");
 212         a->archive.state = ARCHIVE_STATE_FATAL;
 213         return (ARCHIVE_FATAL);
 214 }
 215
 216 /*
 217  * Create an ARCHIVE_MATCH object.
 218  */
 219 struct archive *
 220 archive_match_new(void)
 221 {
 222         struct archive_match *a;
 223
 224         a = (struct archive_match *)calloc(1, sizeof(*a));
 225         if (a == NULL)
 226                 return (NULL);
 227         a->archive.magic = ARCHIVE_MATCH_MAGIC;
 228         a->archive.state = ARCHIVE_STATE_NEW;
 229         a->recursive_include = 1;
 230         match_list_init(&(a->inclusions));
 231         match_list_init(&(a->exclusions));
 232         __archive_rb_tree_init(&(a->exclusion_tree), &rb_ops_mbs);
 233         entry_list_init(&(a->exclusion_entry_list));
 234         match_list_init(&(a->inclusion_unames));
 235         match_list_init(&(a->inclusion_gnames));
 236         time(&a->now);
 237         return (&(a->archive));
 238 }
 239
 240 /*
 241  * Free an ARCHIVE_MATCH object.
 242  */
 243 int
 244 archive_match_free(struct archive *_a)
 245 {
 246         struct archive_match *a;
 247
 248         if (_a == NULL)
 249                 return (ARCHIVE_OK);
 250         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
 251             ARCHIVE_STATE_ANY | ARCHIVE_STATE_FATAL, "archive_match_free");
 252         a = (struct archive_match *)_a;
 253         match_list_free(&(a->inclusions));
 254         match_list_free(&(a->exclusions));
 255         entry_list_free(&(a->exclusion_entry_list));
 256         free(a->inclusion_uids.ids);
 257         free(a->inclusion_gids.ids);
 258         match_list_free(&(a->inclusion_unames));
 259         match_list_free(&(a->inclusion_gnames));
 260         free(a);
 261         return (ARCHIVE_OK);
 262 }
 263
 264 /*
 265  * Convenience function to perform all exclusion tests.
 266  *
 267  * Returns 1 if archive entry is excluded.
 268  * Returns 0 if archive entry is not excluded.
 269  * Returns <0 if something error happened.
 270  */
 271 int
 272 archive_match_excluded(struct archive *_a, struct archive_entry *entry)
 273 {
 274         struct archive_match *a;
 275         int r;
 276
 277         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
 278             ARCHIVE_STATE_NEW, "archive_match_excluded_ae");
 279
 280         a = (struct archive_match *)_a;
 281         if (entry == NULL) {
 282                 archive_set_error(&(a->archive), EINVAL, "entry is NULL");
 283                 return (ARCHIVE_FAILED);
 284         }
 285
 286         r = 0;
 287         if (a->setflag & PATTERN_IS_SET) {
 288 #if defined(_WIN32) && !defined(__CYGWIN__)
 289                 r = path_excluded(a, 0, archive_entry_pathname_w(entry));
 290 #else
 291                 r = path_excluded(a, 1, archive_entry_pathname(entry));
 292 #endif
 293                 if (r != 0)
 294                         return (r);
 295         }
 296
 297         if (a->setflag & TIME_IS_SET) {
 298                 r = time_excluded(a, entry);
 299                 if (r != 0)
 300                         return (r);
 301         }
 302
 303         if (a->setflag & ID_IS_SET)
 304                 r = owner_excluded(a, entry);
 305         return (r);
 306 }
 307
 308 /*
 309  * Utility functions to manage exclusion/inclusion patterns
 310  */
 311
 312 int
 313 archive_match_exclude_pattern(struct archive *_a, const char *pattern)
 314 {
 315         struct archive_match *a;
 316         int r;
 317
 318         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
 319             ARCHIVE_STATE_NEW, "archive_match_exclude_pattern");
 320         a = (struct archive_match *)_a;
 321
 322         if (pattern == NULL || *pattern == '\0') {
 323                 archive_set_error(&(a->archive), EINVAL, "pattern is empty");
 324                 return (ARCHIVE_FAILED);
 325         }
 326         if ((r = add_pattern_mbs(a, &(a->exclusions), pattern)) != ARCHIVE_OK)
 327                 return (r);
 328         return (ARCHIVE_OK);
 329 }
 330
 331 int
 332 archive_match_exclude_pattern_w(struct archive *_a, const wchar_t *pattern)
 333 {
 334         struct archive_match *a;
 335         int r;
 336
 337         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
 338             ARCHIVE_STATE_NEW, "archive_match_exclude_pattern_w");
 339         a = (struct archive_match *)_a;
 340
 341         if (pattern == NULL || *pattern == L'\0') {
 342                 archive_set_error(&(a->archive), EINVAL, "pattern is empty");
 343                 return (ARCHIVE_FAILED);
 344         }
 345         if ((r = add_pattern_wcs(a, &(a->exclusions), pattern)) != ARCHIVE_OK)
 346                 return (r);
 347         return (ARCHIVE_OK);
 348 }
 349
 350 int
 351 archive_match_exclude_pattern_from_file(struct archive *_a,
 352     const char *pathname, int nullSeparator)
 353 {
 354         struct archive_match *a;
 355
 356         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
 357             ARCHIVE_STATE_NEW, "archive_match_exclude_pattern_from_file");
 358         a = (struct archive_match *)_a;
 359
 360         return add_pattern_from_file(a, &(a->exclusions), 1, pathname,
 361                 nullSeparator);
 362 }
 363
 364 int
 365 archive_match_exclude_pattern_from_file_w(struct archive *_a,
 366     const wchar_t *pathname, int nullSeparator)
 367 {
 368         struct archive_match *a;
 369
 370         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
 371             ARCHIVE_STATE_NEW, "archive_match_exclude_pattern_from_file_w");
 372         a = (struct archive_match *)_a;
 373
 374         return add_pattern_from_file(a, &(a->exclusions), 0, pathname,
 375                 nullSeparator);
 376 }
 377
 378 int
 379 archive_match_include_pattern(struct archive *_a, const char *pattern)
 380 {
 381         struct archive_match *a;
 382         int r;
 383
 384         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
 385             ARCHIVE_STATE_NEW, "archive_match_include_pattern");
 386         a = (struct archive_match *)_a;
 387
 388         if (pattern == NULL || *pattern == '\0') {
 389                 archive_set_error(&(a->archive), EINVAL, "pattern is empty");
 390                 return (ARCHIVE_FAILED);
 391         }
 392         if ((r = add_pattern_mbs(a, &(a->inclusions), pattern)) != ARCHIVE_OK)
 393                 return (r);
 394         return (ARCHIVE_OK);
 395 }
 396
 397 int
 398 archive_match_include_pattern_w(struct archive *_a, const wchar_t *pattern)
 399 {
 400         struct archive_match *a;
 401         int r;
 402
 403         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
 404             ARCHIVE_STATE_NEW, "archive_match_include_pattern_w");
 405         a = (struct archive_match *)_a;
 406
 407         if (pattern == NULL || *pattern == L'\0') {
 408                 archive_set_error(&(a->archive), EINVAL, "pattern is empty");
 409                 return (ARCHIVE_FAILED);
 410         }
 411         if ((r = add_pattern_wcs(a, &(a->inclusions), pattern)) != ARCHIVE_OK)
 412                 return (r);
 413         return (ARCHIVE_OK);
 414 }
 415
 416 int
 417 archive_match_include_pattern_from_file(struct archive *_a,
 418     const char *pathname, int nullSeparator)
 419 {
 420         struct archive_match *a;
 421
 422         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
 423             ARCHIVE_STATE_NEW, "archive_match_include_pattern_from_file");
 424         a = (struct archive_match *)_a;
 425
 426         return add_pattern_from_file(a, &(a->inclusions), 1, pathname,
 427                 nullSeparator);
 428 }
 429
 430 int
 431 archive_match_include_pattern_from_file_w(struct archive *_a,
 432     const wchar_t *pathname, int nullSeparator)
 433 {
 434         struct archive_match *a;
 435
 436         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
 437             ARCHIVE_STATE_NEW, "archive_match_include_pattern_from_file_w");
 438         a = (struct archive_match *)_a;
 439
 440         return add_pattern_from_file(a, &(a->inclusions), 0, pathname,
 441                 nullSeparator);
 442 }
 443
 444 /*
 445  * Test functions for pathname patterns.
 446  *
 447  * Returns 1 if archive entry is excluded.
 448  * Returns 0 if archive entry is not excluded.
 449  * Returns <0 if something error happened.
 450  */
 451 int
 452 archive_match_path_excluded(struct archive *_a,
 453     struct archive_entry *entry)
 454 {
 455         struct archive_match *a;
 456
 457         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
 458             ARCHIVE_STATE_NEW, "archive_match_path_excluded");
 459
 460         a = (struct archive_match *)_a;
 461         if (entry == NULL) {
 462                 archive_set_error(&(a->archive), EINVAL, "entry is NULL");
 463                 return (ARCHIVE_FAILED);
 464         }
 465
 466         /* If we don't have exclusion/inclusion pattern set at all,
 467          * the entry is always not excluded. */
 468         if ((a->setflag & PATTERN_IS_SET) == 0)
 469                 return (0);
 470 #if defined(_WIN32) && !defined(__CYGWIN__)
 471         return (path_excluded(a, 0, archive_entry_pathname_w(entry)));
 472 #else
 473         return (path_excluded(a, 1, archive_entry_pathname(entry)));
 474 #endif
 475 }
 476
 477 /*
 478  * When recursive inclusion of directory content is enabled,
 479  * an inclusion pattern that matches a directory will also
 480  * include everything beneath that directory. Enabled by default.
 481  *
 482  * For compatibility with GNU tar, exclusion patterns always
 483  * match if a subset of the full patch matches (i.e., they are
 484  * are not rooted at the beginning of the path) and thus there
 485  * is no corresponding non-recursive exclusion mode.
 486  */
 487 int
 488 archive_match_set_inclusion_recursion(struct archive *_a, int enabled)
 489 {
 490         struct archive_match *a;
 491
 492         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
 493             ARCHIVE_STATE_NEW, "archive_match_set_inclusion_recursion");
 494         a = (struct archive_match *)_a;
 495         a->recursive_include = enabled;
 496         return (ARCHIVE_OK);
 497 }
 498
 499 /*
 500  * Utility functions to get statistic information for inclusion patterns.
 501  */
 502 int
 503 archive_match_path_unmatched_inclusions(struct archive *_a)
 504 {
 505         struct archive_match *a;
 506
 507         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
 508             ARCHIVE_STATE_NEW, "archive_match_unmatched_inclusions");
 509         a = (struct archive_match *)_a;
 510
 511         return (a->inclusions.unmatched_count);
 512 }
 513
 514 int
 515 archive_match_path_unmatched_inclusions_next(struct archive *_a,
 516     const char **_p)
 517 {
 518         struct archive_match *a;
 519         const void *v;
 520         int r;
 521
 522         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
 523             ARCHIVE_STATE_NEW, "archive_match_unmatched_inclusions_next");
 524         a = (struct archive_match *)_a;
 525
 526         r = match_list_unmatched_inclusions_next(a, &(a->inclusions), 1, &v);
 527         *_p = (const char *)v;
 528         return (r);
 529 }
 530
 531 int
 532 archive_match_path_unmatched_inclusions_next_w(struct archive *_a,
 533     const wchar_t **_p)
 534 {
 535         struct archive_match *a;
 536         const void *v;
 537         int r;
 538
 539         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
 540             ARCHIVE_STATE_NEW, "archive_match_unmatched_inclusions_next_w");
 541         a = (struct archive_match *)_a;
 542
 543         r = match_list_unmatched_inclusions_next(a, &(a->inclusions), 0, &v);
 544         *_p = (const wchar_t *)v;
 545         return (r);
 546 }
 547
 548 /*
 549  * Add inclusion/exclusion patterns.
 550  */
 551 static int
 552 add_pattern_mbs(struct archive_match *a, struct match_list *list,
 553     const char *pattern)
 554 {
 555         struct match *match;
 556         size_t len;
 557
 558         match = calloc(1, sizeof(*match));
 559         if (match == NULL)
 560                 return (error_nomem(a));
 561         /* Both "foo/" and "foo" should match "foo/bar". */
 562         len = strlen(pattern);
 563         if (len && pattern[len - 1] == '/')
 564                 --len;
 565         archive_mstring_copy_mbs_len(&(match->pattern), pattern, len);
 566         match_list_add(list, match);
 567         a->setflag |= PATTERN_IS_SET;
 568         return (ARCHIVE_OK);
 569 }
 570
 571 static int
 572 add_pattern_wcs(struct archive_match *a, struct match_list *list,
 573     const wchar_t *pattern)
 574 {
 575         struct match *match;
 576         size_t len;
 577
 578         match = calloc(1, sizeof(*match));
 579         if (match == NULL)
 580                 return (error_nomem(a));
 581         /* Both "foo/" and "foo" should match "foo/bar". */
 582         len = wcslen(pattern);
 583         if (len && pattern[len - 1] == L'/')
 584                 --len;
 585         archive_mstring_copy_wcs_len(&(match->pattern), pattern, len);
 586         match_list_add(list, match);
 587         a->setflag |= PATTERN_IS_SET;
 588         return (ARCHIVE_OK);
 589 }
 590
 591 static int
 592 add_pattern_from_file(struct archive_match *a, struct match_list *mlist,
 593     int mbs, const void *pathname, int nullSeparator)
 594 {
 595         struct archive *ar;
 596         struct archive_entry *ae;
 597         struct archive_string as;
 598         const void *buff;
 599         size_t size;
 600         int64_t offset;
 601         int r;
 602
 603         ar = archive_read_new();
 604         if (ar == NULL) {
 605                 archive_set_error(&(a->archive), ENOMEM, "No memory");
 606                 return (ARCHIVE_FATAL);
 607         }
 608         r = archive_read_support_format_raw(ar);
 609         r = archive_read_support_format_empty(ar);
 610         if (r != ARCHIVE_OK) {
 611                 archive_copy_error(&(a->archive), ar);
 612                 archive_read_free(ar);
 613                 return (r);
 614         }
 615         if (mbs)
 616                 r = archive_read_open_filename(ar, pathname, 512*20);
 617         else
 618                 r = archive_read_open_filename_w(ar, pathname, 512*20);
 619         if (r != ARCHIVE_OK) {
 620                 archive_copy_error(&(a->archive), ar);
 621                 archive_read_free(ar);
 622                 return (r);
 623         }
 624         r = archive_read_next_header(ar, &ae);
 625         if (r != ARCHIVE_OK) {
 626                 archive_read_free(ar);
 627                 if (r == ARCHIVE_EOF) {
 628                         return (ARCHIVE_OK);
 629                 } else {
 630                         archive_copy_error(&(a->archive), ar);
 631                         return (r);
 632                 }
 633         }
 634
 635         archive_string_init(&as);
 636
 637         while ((r = archive_read_data_block(ar, &buff, &size, &offset))
 638             == ARCHIVE_OK) {
 639                 const char *b = (const char *)buff;
 640
 641                 while (size) {
 642                         const char *s = (const char *)b;
 643                         size_t length = 0;
 644                         int found_separator = 0;
 645
 646                         while (length < size) {
 647                                 if (nullSeparator) {
 648                                         if (*b == '\0') {
 649                                                 found_separator = 1;
 650                                                 break;
 651                                         }
 652                                 } else {
 653                                         if (*b == 0x0d || *b == 0x0a) {
 654                                                 found_separator = 1;
 655                                                 break;
 656                                         }
 657                                 }
 658                                 b++;
 659                                 length++;
 660                         }
 661                         if (!found_separator) {
 662                                 archive_strncat(&as, s, length);
 663                                 /* Read next data block. */
 664                                 break;
 665                         }
 666                         b++;
 667                         size -= length + 1;
 668                         archive_strncat(&as, s, length);
 669
 670                         /* If the line is not empty, add the pattern. */
 671                         if (archive_strlen(&as) > 0) {
 672                                 /* Add pattern. */
 673                                 r = add_pattern_mbs(a, mlist, as.s);
 674                                 if (r != ARCHIVE_OK) {
 675                                         archive_read_free(ar);
 676                                         archive_string_free(&as);
 677                                         return (r);
 678                                 }
 679                                 archive_string_empty(&as);
 680                         }
 681                 }
 682         }
 683
 684         /* If an error occurred, report it immediately. */
 685         if (r < ARCHIVE_OK) {
 686                 archive_copy_error(&(a->archive), ar);
 687                 archive_read_free(ar);
 688                 archive_string_free(&as);
 689                 return (r);
 690         }
 691
 692         /* If the line is not empty, add the pattern. */
 693         if (r == ARCHIVE_EOF && archive_strlen(&as) > 0) {
 694                 /* Add pattern. */
 695                 r = add_pattern_mbs(a, mlist, as.s);
 696                 if (r != ARCHIVE_OK) {
 697                         archive_read_free(ar);
 698                         archive_string_free(&as);
 699                         return (r);
 700                 }
 701         }
 702         archive_read_free(ar);
 703         archive_string_free(&as);
 704         return (ARCHIVE_OK);
 705 }
 706
 707 /*
 708  * Test if pathname is excluded by inclusion/exclusion patterns.
 709  */
 710 static int
 711 path_excluded(struct archive_match *a, int mbs, const void *pathname)
 712 {
 713         struct match *match;
 714         struct match *matched;
 715         int r;
 716
 717         if (a == NULL)
 718                 return (0);
 719
 720         /* Mark off any unmatched inclusions. */
 721         /* In particular, if a filename does appear in the archive and
 722          * is explicitly included and excluded, then we don't report
 723          * it as missing even though we don't extract it.
 724          */
 725         matched = NULL;
 726         for (match = a->inclusions.first; match != NULL;
 727             match = match->next){
 728                 if (match->matches == 0 &&
 729                     (r = match_path_inclusion(a, match, mbs, pathname)) != 0) {
 730                         if (r < 0)
 731                                 return (r);
 732                         a->inclusions.unmatched_count--;
 733                         match->matches++;
 734                         matched = match;
 735                 }
 736         }
 737
 738         /* Exclusions take priority */
 739         for (match = a->exclusions.first; match != NULL;
 740             match = match->next){
 741                 r = match_path_exclusion(a, match, mbs, pathname);
 742                 if (r)
 743                         return (r);
 744         }
 745
 746         /* It's not excluded and we found an inclusion above, so it's
 747          * included. */
 748         if (matched != NULL)
 749                 return (0);
 750
 751
 752         /* We didn't find an unmatched inclusion, check the remaining ones. */
 753         for (match = a->inclusions.first; match != NULL;
 754             match = match->next){
 755                 /* We looked at previously-unmatched inclusions already. */
 756                 if (match->matches > 0 &&
 757                     (r = match_path_inclusion(a, match, mbs, pathname)) != 0) {
 758                         if (r < 0)
 759                                 return (r);
 760                         match->matches++;
 761                         return (0);
 762                 }
 763         }
 764
 765         /* If there were inclusions, default is to exclude. */
 766         if (a->inclusions.first != NULL)
 767             return (1);
 768
 769         /* No explicit inclusions, default is to match. */
 770         return (0);
 771 }
 772
 773 /*
 774  * This is a little odd, but it matches the default behavior of
 775  * gtar.  In particular, 'a*b' will match 'foo/a1111/222b/bar'
 776  *
 777  */
 778 static int
 779 match_path_exclusion(struct archive_match *a, struct match *m,
 780     int mbs, const void *pn)
 781 {
 782         int flag = PATHMATCH_NO_ANCHOR_START | PATHMATCH_NO_ANCHOR_END;
 783         int r;
 784
 785         if (mbs) {
 786                 const char *p;
 787                 r = archive_mstring_get_mbs(&(a->archive), &(m->pattern), &p);
 788                 if (r == 0)
 789                         return (archive_pathmatch(p, (const char *)pn, flag));
 790         } else {
 791                 const wchar_t *p;
 792                 r = archive_mstring_get_wcs(&(a->archive), &(m->pattern), &p);
 793                 if (r == 0)
 794                         return (archive_pathmatch_w(p, (const wchar_t *)pn,
 795                                 flag));
 796         }
 797         if (errno == ENOMEM)
 798                 return (error_nomem(a));
 799         return (0);
 800 }
 801
 802 /*
 803  * Again, mimic gtar:  inclusions are always anchored (have to match
 804  * the beginning of the path) even though exclusions are not anchored.
 805  */
 806 static int
 807 match_path_inclusion(struct archive_match *a, struct match *m,
 808     int mbs, const void *pn)
 809 {
 810         /* Recursive operation requires only a prefix match. */
 811         int flag = a->recursive_include ?
 812                 PATHMATCH_NO_ANCHOR_END :
 813                 0;
 814         int r;
 815
 816         if (mbs) {
 817                 const char *p;
 818                 r = archive_mstring_get_mbs(&(a->archive), &(m->pattern), &p);
 819                 if (r == 0)
 820                         return (archive_pathmatch(p, (const char *)pn, flag));
 821         } else {
 822                 const wchar_t *p;
 823                 r = archive_mstring_get_wcs(&(a->archive), &(m->pattern), &p);
 824                 if (r == 0)
 825                         return (archive_pathmatch_w(p, (const wchar_t *)pn,
 826                                 flag));
 827         }
 828         if (errno == ENOMEM)
 829                 return (error_nomem(a));
 830         return (0);
 831 }
 832
 833 static void
 834 match_list_init(struct match_list *list)
 835 {
 836         list->first = NULL;
 837         list->last = &(list->first);
 838         list->count = 0;
 839 }
 840
 841 static void
 842 match_list_free(struct match_list *list)
 843 {
 844         struct match *p, *q;
 845
 846         for (p = list->first; p != NULL; ) {
 847                 q = p;
 848                 p = p->next;
 849                 archive_mstring_clean(&(q->pattern));
 850                 free(q);
 851         }
 852 }
 853
 854 static void
 855 match_list_add(struct match_list *list, struct match *m)
 856 {
 857         *list->last = m;
 858         list->last = &(m->next);
 859         list->count++;
 860         list->unmatched_count++;
 861 }
 862
 863 static int
 864 match_list_unmatched_inclusions_next(struct archive_match *a,
 865     struct match_list *list, int mbs, const void **vp)
 866 {
 867         struct match *m;
 868
 869         *vp = NULL;
 870         if (list->unmatched_eof) {
 871                 list->unmatched_eof = 0;
 872                 return (ARCHIVE_EOF);
 873         }
 874         if (list->unmatched_next == NULL) {
 875                 if (list->unmatched_count == 0)
 876                         return (ARCHIVE_EOF);
 877                 list->unmatched_next = list->first;
 878         }
 879
 880         for (m = list->unmatched_next; m != NULL; m = m->next) {
 881                 int r;
 882
 883                 if (m->matches)
 884                         continue;
 885                 if (mbs) {
 886                         const char *p;
 887                         r = archive_mstring_get_mbs(&(a->archive),
 888                                 &(m->pattern), &p);
 889                         if (r < 0 && errno == ENOMEM)
 890                                 return (error_nomem(a));
 891                         if (p == NULL)
 892                                 p = "";
 893                         *vp = p;
 894                 } else {
 895                         const wchar_t *p;
 896                         r = archive_mstring_get_wcs(&(a->archive),
 897                                 &(m->pattern), &p);
 898                         if (r < 0 && errno == ENOMEM)
 899                                 return (error_nomem(a));
 900                         if (p == NULL)
 901                                 p = L"";
 902                         *vp = p;
 903                 }
 904                 list->unmatched_next = m->next;
 905                 if (list->unmatched_next == NULL)
 906                         /* To return EOF next time. */
 907                         list->unmatched_eof = 1;
 908                 return (ARCHIVE_OK);
 909         }
 910         list->unmatched_next = NULL;
 911         return (ARCHIVE_EOF);
 912 }
 913
 914 /*
 915  * Utility functions to manage inclusion timestamps.
 916  */
 917 int
 918 archive_match_include_time(struct archive *_a, int flag, time_t sec,
 919     long nsec)
 920 {
 921         int r;
 922
 923         r = validate_time_flag(_a, flag, "archive_match_include_time");
 924         if (r != ARCHIVE_OK)
 925                 return (r);
 926         return set_timefilter((struct archive_match *)_a, flag,
 927                         sec, nsec, sec, nsec);
 928 }
 929
 930 int
 931 archive_match_include_date(struct archive *_a, int flag,
 932     const char *datestr)
 933 {
 934         int r;
 935
 936         r = validate_time_flag(_a, flag, "archive_match_include_date");
 937         if (r != ARCHIVE_OK)
 938                 return (r);
 939         return set_timefilter_date((struct archive_match *)_a, flag, datestr);
 940 }
 941
 942 int
 943 archive_match_include_date_w(struct archive *_a, int flag,
 944     const wchar_t *datestr)
 945 {
 946         int r;
 947
 948         r = validate_time_flag(_a, flag, "archive_match_include_date_w");
 949         if (r != ARCHIVE_OK)
 950                 return (r);
 951
 952         return set_timefilter_date_w((struct archive_match *)_a, flag, datestr);
 953 }
 954
 955 int
 956 archive_match_include_file_time(struct archive *_a, int flag,
 957     const char *pathname)
 958 {
 959         int r;
 960
 961         r = validate_time_flag(_a, flag, "archive_match_include_file_time");
 962         if (r != ARCHIVE_OK)
 963                 return (r);
 964         return set_timefilter_pathname_mbs((struct archive_match *)_a,
 965                         flag, pathname);
 966 }
 967
 968 int
 969 archive_match_include_file_time_w(struct archive *_a, int flag,
 970     const wchar_t *pathname)
 971 {
 972         int r;
 973
 974         r = validate_time_flag(_a, flag, "archive_match_include_file_time_w");
 975         if (r != ARCHIVE_OK)
 976                 return (r);
 977         return set_timefilter_pathname_wcs((struct archive_match *)_a,
 978                         flag, pathname);
 979 }
 980
 981 int
 982 archive_match_exclude_entry(struct archive *_a, int flag,
 983     struct archive_entry *entry)
 984 {
 985         struct archive_match *a;
 986         int r;
 987
 988         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
 989             ARCHIVE_STATE_NEW, "archive_match_time_include_entry");
 990         a = (struct archive_match *)_a;
 991
 992         if (entry == NULL) {
 993                 archive_set_error(&(a->archive), EINVAL, "entry is NULL");
 994                 return (ARCHIVE_FAILED);
 995         }
 996         r = validate_time_flag(_a, flag, "archive_match_exclude_entry");
 997         if (r != ARCHIVE_OK)
 998                 return (r);
 999         return (add_entry(a, flag, entry));
1000 }
1001
1002 /*
1003  * Test function for time stamps.
1004  *
1005  * Returns 1 if archive entry is excluded.
1006  * Returns 0 if archive entry is not excluded.
1007  * Returns <0 if something error happened.
1008  */
1009 int
1010 archive_match_time_excluded(struct archive *_a,
1011     struct archive_entry *entry)
1012 {
1013         struct archive_match *a;
1014
1015         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
1016             ARCHIVE_STATE_NEW, "archive_match_time_excluded_ae");
1017
1018         a = (struct archive_match *)_a;
1019         if (entry == NULL) {
1020                 archive_set_error(&(a->archive), EINVAL, "entry is NULL");
1021                 return (ARCHIVE_FAILED);
1022         }
1023
1024         /* If we don't have inclusion time set at all, the entry is always
1025          * not excluded. */
1026         if ((a->setflag & TIME_IS_SET) == 0)
1027                 return (0);
1028         return (time_excluded(a, entry));
1029 }
1030
1031 static int
1032 validate_time_flag(struct archive *_a, int flag, const char *_fn)
1033 {
1034         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
1035             ARCHIVE_STATE_NEW, _fn);
1036
1037         /* Check a type of time. */
1038         if (flag &
1039            ((~(ARCHIVE_MATCH_MTIME | ARCHIVE_MATCH_CTIME)) & 0xff00)) {
1040                 archive_set_error(_a, EINVAL, "Invalid time flag");
1041                 return (ARCHIVE_FAILED);
1042         }
1043         if ((flag & (ARCHIVE_MATCH_MTIME | ARCHIVE_MATCH_CTIME)) == 0) {
1044                 archive_set_error(_a, EINVAL, "No time flag");
1045                 return (ARCHIVE_FAILED);
1046         }
1047
1048         /* Check a type of comparison. */
1049         if (flag &
1050            ((~(ARCHIVE_MATCH_NEWER | ARCHIVE_MATCH_OLDER
1051                         | ARCHIVE_MATCH_EQUAL)) & 0x00ff)) {
1052                 archive_set_error(_a, EINVAL, "Invalid comparison flag");
1053                 return (ARCHIVE_FAILED);
1054         }
1055         if ((flag & (ARCHIVE_MATCH_NEWER | ARCHIVE_MATCH_OLDER
1056             | ARCHIVE_MATCH_EQUAL)) == 0) {
1057                 archive_set_error(_a, EINVAL, "No comparison flag");
1058                 return (ARCHIVE_FAILED);
1059         }
1060
1061         return (ARCHIVE_OK);
1062 }
1063
1064 #define JUST_EQUAL(t) (((t) &  (ARCHIVE_MATCH_EQUAL |\
1065         ARCHIVE_MATCH_NEWER | ARCHIVE_MATCH_OLDER)) == ARCHIVE_MATCH_EQUAL)
1066 static int
1067 set_timefilter(struct archive_match *a, int timetype,
1068     time_t mtime_sec, long mtime_nsec, time_t ctime_sec, long ctime_nsec)
1069 {
1070         if (timetype & ARCHIVE_MATCH_MTIME) {
1071                 if ((timetype & ARCHIVE_MATCH_NEWER) || JUST_EQUAL(timetype)) {
1072                         a->newer_mtime_filter = timetype;
1073                         a->newer_mtime_sec = mtime_sec;
1074                         a->newer_mtime_nsec = mtime_nsec;
1075                         a->setflag |= TIME_IS_SET;
1076                 }
1077                 if ((timetype & ARCHIVE_MATCH_OLDER) || JUST_EQUAL(timetype)) {
1078                         a->older_mtime_filter = timetype;
1079                         a->older_mtime_sec = mtime_sec;
1080                         a->older_mtime_nsec = mtime_nsec;
1081                         a->setflag |= TIME_IS_SET;
1082                 }
1083         }
1084         if (timetype & ARCHIVE_MATCH_CTIME) {
1085                 if ((timetype & ARCHIVE_MATCH_NEWER) || JUST_EQUAL(timetype)) {
1086                         a->newer_ctime_filter = timetype;
1087                         a->newer_ctime_sec = ctime_sec;
1088                         a->newer_ctime_nsec = ctime_nsec;
1089                         a->setflag |= TIME_IS_SET;
1090                 }
1091                 if ((timetype & ARCHIVE_MATCH_OLDER) || JUST_EQUAL(timetype)) {
1092                         a->older_ctime_filter = timetype;
1093                         a->older_ctime_sec = ctime_sec;
1094                         a->older_ctime_nsec = ctime_nsec;
1095                         a->setflag |= TIME_IS_SET;
1096                 }
1097         }
1098         return (ARCHIVE_OK);
1099 }
1100
1101 static int
1102 set_timefilter_date(struct archive_match *a, int timetype, const char *datestr)
1103 {
1104         time_t t;
1105
1106         if (datestr == NULL || *datestr == '\0') {
1107                 archive_set_error(&(a->archive), EINVAL, "date is empty");
1108                 return (ARCHIVE_FAILED);
1109         }
1110         t = get_date(a->now, datestr);
1111         if (t == (time_t)-1) {
1112                 archive_set_error(&(a->archive), EINVAL, "invalid date string");
1113                 return (ARCHIVE_FAILED);
1114         }
1115         return set_timefilter(a, timetype, t, 0, t, 0);
1116 }
1117
1118 static int
1119 set_timefilter_date_w(struct archive_match *a, int timetype,
1120     const wchar_t *datestr)
1121 {
1122         struct archive_string as;
1123         time_t t;
1124
1125         if (datestr == NULL || *datestr == L'\0') {
1126                 archive_set_error(&(a->archive), EINVAL, "date is empty");
1127                 return (ARCHIVE_FAILED);
1128         }
1129
1130         archive_string_init(&as);
1131         if (archive_string_append_from_wcs(&as, datestr, wcslen(datestr)) < 0) {
1132                 archive_string_free(&as);
1133                 if (errno == ENOMEM)
1134                         return (error_nomem(a));
1135                 archive_set_error(&(a->archive), -1,
1136                     "Failed to convert WCS to MBS");
1137                 return (ARCHIVE_FAILED);
1138         }
1139         t = get_date(a->now, as.s);
1140         archive_string_free(&as);
1141         if (t == (time_t)-1) {
1142                 archive_set_error(&(a->archive), EINVAL, "invalid date string");
1143                 return (ARCHIVE_FAILED);
1144         }
1145         return set_timefilter(a, timetype, t, 0, t, 0);
1146 }
1147
1148 #if defined(_WIN32) && !defined(__CYGWIN__)
1149 #define EPOC_TIME ARCHIVE_LITERAL_ULL(116444736000000000)
1150 static int
1151 set_timefilter_find_data(struct archive_match *a, int timetype,
1152     DWORD ftLastWriteTime_dwHighDateTime, DWORD ftLastWriteTime_dwLowDateTime,
1153     DWORD ftCreationTime_dwHighDateTime, DWORD ftCreationTime_dwLowDateTime)
1154 {
1155         ULARGE_INTEGER utc;
1156         time_t ctime_sec, mtime_sec;
1157         long ctime_ns, mtime_ns;
1158
1159         utc.HighPart = ftCreationTime_dwHighDateTime;
1160         utc.LowPart = ftCreationTime_dwLowDateTime;
1161         if (utc.QuadPart >= EPOC_TIME) {
1162                 utc.QuadPart -= EPOC_TIME;
1163                 ctime_sec = (time_t)(utc.QuadPart / 10000000);
1164                 ctime_ns = (long)(utc.QuadPart % 10000000) * 100;
1165         } else {
1166                 ctime_sec = 0;
1167                 ctime_ns = 0;
1168         }
1169         utc.HighPart = ftLastWriteTime_dwHighDateTime;
1170         utc.LowPart = ftLastWriteTime_dwLowDateTime;
1171         if (utc.QuadPart >= EPOC_TIME) {
1172                 utc.QuadPart -= EPOC_TIME;
1173                 mtime_sec = (time_t)(utc.QuadPart / 10000000);
1174                 mtime_ns = (long)(utc.QuadPart % 10000000) * 100;
1175         } else {
1176                 mtime_sec = 0;
1177                 mtime_ns = 0;
1178         }
1179         return set_timefilter(a, timetype,
1180                         mtime_sec, mtime_ns, ctime_sec, ctime_ns);
1181 }
1182
1183 static int
1184 set_timefilter_pathname_mbs(struct archive_match *a, int timetype,
1185     const char *path)
1186 {
1187         /* NOTE: stat() on Windows cannot handle nano seconds. */
1188         HANDLE h;
1189         WIN32_FIND_DATAA d;
1190
1191         if (path == NULL || *path == '\0') {
1192                 archive_set_error(&(a->archive), EINVAL, "pathname is empty");
1193                 return (ARCHIVE_FAILED);
1194         }
1195         h = FindFirstFileA(path, &d);
1196         if (h == INVALID_HANDLE_VALUE) {
1197                 la_dosmaperr(GetLastError());
1198                 archive_set_error(&(a->archive), errno,
1199                     "Failed to FindFirstFileA");
1200                 return (ARCHIVE_FAILED);
1201         }
1202         FindClose(h);
1203         return set_timefilter_find_data(a, timetype,
1204             d.ftLastWriteTime.dwHighDateTime, d.ftLastWriteTime.dwLowDateTime,
1205             d.ftCreationTime.dwHighDateTime, d.ftCreationTime.dwLowDateTime);
1206 }
1207
1208 static int
1209 set_timefilter_pathname_wcs(struct archive_match *a, int timetype,
1210     const wchar_t *path)
1211 {
1212         HANDLE h;
1213         WIN32_FIND_DATAW d;
1214
1215         if (path == NULL || *path == L'\0') {
1216                 archive_set_error(&(a->archive), EINVAL, "pathname is empty");
1217                 return (ARCHIVE_FAILED);
1218         }
1219         h = FindFirstFileW(path, &d);
1220         if (h == INVALID_HANDLE_VALUE) {
1221                 la_dosmaperr(GetLastError());
1222                 archive_set_error(&(a->archive), errno,
1223                     "Failed to FindFirstFile");
1224                 return (ARCHIVE_FAILED);
1225         }
1226         FindClose(h);
1227         return set_timefilter_find_data(a, timetype,
1228             d.ftLastWriteTime.dwHighDateTime, d.ftLastWriteTime.dwLowDateTime,
1229             d.ftCreationTime.dwHighDateTime, d.ftCreationTime.dwLowDateTime);
1230 }
1231
1232 #else /* _WIN32 && !__CYGWIN__ */
1233
1234 static int
1235 set_timefilter_stat(struct archive_match *a, int timetype, struct stat *st)
1236 {
1237         struct archive_entry *ae;
1238         time_t ctime_sec, mtime_sec;
1239         long ctime_ns, mtime_ns;
1240
1241         ae = archive_entry_new();
1242         if (ae == NULL)
1243                 return (error_nomem(a));
1244         archive_entry_copy_stat(ae, st);
1245         ctime_sec = archive_entry_ctime(ae);
1246         ctime_ns = archive_entry_ctime_nsec(ae);
1247         mtime_sec = archive_entry_mtime(ae);
1248         mtime_ns = archive_entry_mtime_nsec(ae);
1249         archive_entry_free(ae);
1250         return set_timefilter(a, timetype, mtime_sec, mtime_ns,
1251                         ctime_sec, ctime_ns);
1252 }
1253
1254 static int
1255 set_timefilter_pathname_mbs(struct archive_match *a, int timetype,
1256     const char *path)
1257 {
1258         struct stat st;
1259
1260         if (path == NULL || *path == '\0') {
1261                 archive_set_error(&(a->archive), EINVAL, "pathname is empty");
1262                 return (ARCHIVE_FAILED);
1263         }
1264         if (la_stat(path, &st) != 0) {
1265                 archive_set_error(&(a->archive), errno, "Failed to stat()");
1266                 return (ARCHIVE_FAILED);
1267         }
1268         return (set_timefilter_stat(a, timetype, &st));
1269 }
1270
1271 static int
1272 set_timefilter_pathname_wcs(struct archive_match *a, int timetype,
1273     const wchar_t *path)
1274 {
1275         struct archive_string as;
1276         int r;
1277
1278         if (path == NULL || *path == L'\0') {
1279                 archive_set_error(&(a->archive), EINVAL, "pathname is empty");
1280                 return (ARCHIVE_FAILED);
1281         }
1282
1283         /* Convert WCS filename to MBS filename. */
1284         archive_string_init(&as);
1285         if (archive_string_append_from_wcs(&as, path, wcslen(path)) < 0) {
1286                 archive_string_free(&as);
1287                 if (errno == ENOMEM)
1288                         return (error_nomem(a));
1289                 archive_set_error(&(a->archive), -1,
1290                     "Failed to convert WCS to MBS");
1291                 return (ARCHIVE_FAILED);
1292         }
1293
1294         r = set_timefilter_pathname_mbs(a, timetype, as.s);
1295         archive_string_free(&as);
1296
1297         return (r);
1298 }
1299 #endif /* _WIN32 && !__CYGWIN__ */
1300
1301 /*
1302  * Call back functions for archive_rb.
1303  */
1304 static int
1305 cmp_node_mbs(const struct archive_rb_node *n1,
1306     const struct archive_rb_node *n2)
1307 {
1308         struct match_file *f1 = (struct match_file *)(uintptr_t)n1;
1309         struct match_file *f2 = (struct match_file *)(uintptr_t)n2;
1310         const char *p1, *p2;
1311
1312         archive_mstring_get_mbs(NULL, &(f1->pathname), &p1);
1313         archive_mstring_get_mbs(NULL, &(f2->pathname), &p2);
1314         if (p1 == NULL)
1315                 return (1);
1316         if (p2 == NULL)
1317                 return (-1);
1318         return (strcmp(p1, p2));
1319 }
1320
1321 static int
1322 cmp_key_mbs(const struct archive_rb_node *n, const void *key)
1323 {
1324         struct match_file *f = (struct match_file *)(uintptr_t)n;
1325         const char *p;
1326
1327         archive_mstring_get_mbs(NULL, &(f->pathname), &p);
1328         if (p == NULL)
1329                 return (-1);
1330         return (strcmp(p, (const char *)key));
1331 }
1332
1333 static int
1334 cmp_node_wcs(const struct archive_rb_node *n1,
1335     const struct archive_rb_node *n2)
1336 {
1337         struct match_file *f1 = (struct match_file *)(uintptr_t)n1;
1338         struct match_file *f2 = (struct match_file *)(uintptr_t)n2;
1339         const wchar_t *p1, *p2;
1340
1341         archive_mstring_get_wcs(NULL, &(f1->pathname), &p1);
1342         archive_mstring_get_wcs(NULL, &(f2->pathname), &p2);
1343         if (p1 == NULL)
1344                 return (1);
1345         if (p2 == NULL)
1346                 return (-1);
1347         return (wcscmp(p1, p2));
1348 }
1349
1350 static int
1351 cmp_key_wcs(const struct archive_rb_node *n, const void *key)
1352 {
1353         struct match_file *f = (struct match_file *)(uintptr_t)n;
1354         const wchar_t *p;
1355
1356         archive_mstring_get_wcs(NULL, &(f->pathname), &p);
1357         if (p == NULL)
1358                 return (-1);
1359         return (wcscmp(p, (const wchar_t *)key));
1360 }
1361
1362 static void
1363 entry_list_init(struct entry_list *list)
1364 {
1365         list->first = NULL;
1366         list->last = &(list->first);
1367         list->count = 0;
1368 }
1369
1370 static void
1371 entry_list_free(struct entry_list *list)
1372 {
1373         struct match_file *p, *q;
1374
1375         for (p = list->first; p != NULL; ) {
1376                 q = p;
1377                 p = p->next;
1378                 archive_mstring_clean(&(q->pathname));
1379                 free(q);
1380         }
1381 }
1382
1383 static void
1384 entry_list_add(struct entry_list *list, struct match_file *file)
1385 {
1386         *list->last = file;
1387         list->last = &(file->next);
1388         list->count++;
1389 }
1390
1391 static int
1392 add_entry(struct archive_match *a, int flag,
1393     struct archive_entry *entry)
1394 {
1395         struct match_file *f;
1396         const void *pathname;
1397         int r;
1398
1399         f = calloc(1, sizeof(*f));
1400         if (f == NULL)
1401                 return (error_nomem(a));
1402
1403 #if defined(_WIN32) && !defined(__CYGWIN__)
1404         pathname = archive_entry_pathname_w(entry);
1405         if (pathname == NULL) {
1406                 free(f);
1407                 archive_set_error(&(a->archive), EINVAL, "pathname is NULL");
1408                 return (ARCHIVE_FAILED);
1409         }
1410         archive_mstring_copy_wcs(&(f->pathname), pathname);
1411         a->exclusion_tree.rbt_ops = &rb_ops_wcs;
1412 #else
1413         (void)rb_ops_wcs;
1414         pathname = archive_entry_pathname(entry);
1415         if (pathname == NULL) {
1416                 free(f);
1417                 archive_set_error(&(a->archive), EINVAL, "pathname is NULL");
1418                 return (ARCHIVE_FAILED);
1419         }
1420         archive_mstring_copy_mbs(&(f->pathname), pathname);
1421         a->exclusion_tree.rbt_ops = &rb_ops_mbs;
1422 #endif
1423         f->flag = flag;
1424         f->mtime_sec = archive_entry_mtime(entry);
1425         f->mtime_nsec = archive_entry_mtime_nsec(entry);
1426         f->ctime_sec = archive_entry_ctime(entry);
1427         f->ctime_nsec = archive_entry_ctime_nsec(entry);
1428         r = __archive_rb_tree_insert_node(&(a->exclusion_tree), &(f->node));
1429         if (!r) {
1430                 struct match_file *f2;
1431
1432                 /* Get the duplicated file. */
1433                 f2 = (struct match_file *)__archive_rb_tree_find_node(
1434                         &(a->exclusion_tree), pathname);
1435
1436                 /*
1437                  * We always overwrite comparison condition.
1438                  * If you do not want to overwrite it, you should not
1439                  * call archive_match_exclude_entry(). We cannot know
1440                  * what behavior you really expect since overwriting
1441                  * condition might be different with the flag.
1442                  */
1443                 if (f2 != NULL) {
1444                         f2->flag = f->flag;
1445                         f2->mtime_sec = f->mtime_sec;
1446                         f2->mtime_nsec = f->mtime_nsec;
1447                         f2->ctime_sec = f->ctime_sec;
1448                         f2->ctime_nsec = f->ctime_nsec;
1449                 }
1450                 /* Release the duplicated file. */
1451                 archive_mstring_clean(&(f->pathname));
1452                 free(f);
1453                 return (ARCHIVE_OK);
1454         }
1455         entry_list_add(&(a->exclusion_entry_list), f);
1456         a->setflag |= TIME_IS_SET;
1457         return (ARCHIVE_OK);
1458 }
1459
1460 /*
1461  * Test if entry is excluded by its timestamp.
1462  */
1463 static int
1464 time_excluded(struct archive_match *a, struct archive_entry *entry)
1465 {
1466         struct match_file *f;
1467         const void *pathname;
1468         time_t sec;
1469         long nsec;
1470
1471         /*
1472          * If this file/dir is excluded by a time comparison, skip it.
1473          */
1474         if (a->newer_ctime_filter) {
1475                 /* If ctime is not set, use mtime instead. */
1476                 if (archive_entry_ctime_is_set(entry))
1477                         sec = archive_entry_ctime(entry);
1478                 else
1479                         sec = archive_entry_mtime(entry);
1480                 if (sec < a->newer_ctime_sec)
1481                         return (1); /* Too old, skip it. */
1482                 if (sec == a->newer_ctime_sec) {
1483                         if (archive_entry_ctime_is_set(entry))
1484                                 nsec = archive_entry_ctime_nsec(entry);
1485                         else
1486                                 nsec = archive_entry_mtime_nsec(entry);
1487                         if (nsec < a->newer_ctime_nsec)
1488                                 return (1); /* Too old, skip it. */
1489                         if (nsec == a->newer_ctime_nsec &&
1490                             (a->newer_ctime_filter & ARCHIVE_MATCH_EQUAL)
1491                               == 0)
1492                                 return (1); /* Equal, skip it. */
1493                 }
1494         }
1495         if (a->older_ctime_filter) {
1496                 /* If ctime is not set, use mtime instead. */
1497                 if (archive_entry_ctime_is_set(entry))
1498                         sec = archive_entry_ctime(entry);
1499                 else
1500                         sec = archive_entry_mtime(entry);
1501                 if (sec > a->older_ctime_sec)
1502                         return (1); /* Too new, skip it. */
1503                 if (sec == a->older_ctime_sec) {
1504                         if (archive_entry_ctime_is_set(entry))
1505                                 nsec = archive_entry_ctime_nsec(entry);
1506                         else
1507                                 nsec = archive_entry_mtime_nsec(entry);
1508                         if (nsec > a->older_ctime_nsec)
1509                                 return (1); /* Too new, skip it. */
1510                         if (nsec == a->older_ctime_nsec &&
1511                             (a->older_ctime_filter & ARCHIVE_MATCH_EQUAL)
1512                               == 0)
1513                                 return (1); /* Equal, skip it. */
1514                 }
1515         }
1516         if (a->newer_mtime_filter) {
1517                 sec = archive_entry_mtime(entry);
1518                 if (sec < a->newer_mtime_sec)
1519                         return (1); /* Too old, skip it. */
1520                 if (sec == a->newer_mtime_sec) {
1521                         nsec = archive_entry_mtime_nsec(entry);
1522                         if (nsec < a->newer_mtime_nsec)
1523                                 return (1); /* Too old, skip it. */
1524                         if (nsec == a->newer_mtime_nsec &&
1525                             (a->newer_mtime_filter & ARCHIVE_MATCH_EQUAL)
1526                                == 0)
1527                                 return (1); /* Equal, skip it. */
1528                 }
1529         }
1530         if (a->older_mtime_filter) {
1531                 sec = archive_entry_mtime(entry);
1532                 if (sec > a->older_mtime_sec)
1533                         return (1); /* Too new, skip it. */
1534                 nsec = archive_entry_mtime_nsec(entry);
1535                 if (sec == a->older_mtime_sec) {
1536                         if (nsec > a->older_mtime_nsec)
1537                                 return (1); /* Too new, skip it. */
1538                         if (nsec == a->older_mtime_nsec &&
1539                             (a->older_mtime_filter & ARCHIVE_MATCH_EQUAL)
1540                                == 0)
1541                                 return (1); /* Equal, skip it. */
1542                 }
1543         }
1544
1545         /* If there is no exclusion list, include the file. */
1546         if (a->exclusion_entry_list.count == 0)
1547                 return (0);
1548
1549 #if defined(_WIN32) && !defined(__CYGWIN__)
1550         pathname = archive_entry_pathname_w(entry);
1551         a->exclusion_tree.rbt_ops = &rb_ops_wcs;
1552 #else
1553         (void)rb_ops_wcs;
1554         pathname = archive_entry_pathname(entry);
1555         a->exclusion_tree.rbt_ops = &rb_ops_mbs;
1556 #endif
1557         if (pathname == NULL)
1558                 return (0);
1559
1560         f = (struct match_file *)__archive_rb_tree_find_node(
1561                 &(a->exclusion_tree), pathname);
1562         /* If the file wasn't rejected, include it. */
1563         if (f == NULL)
1564                 return (0);
1565
1566         if (f->flag & ARCHIVE_MATCH_CTIME) {
1567                 sec = archive_entry_ctime(entry);
1568                 if (f->ctime_sec > sec) {
1569                         if (f->flag & ARCHIVE_MATCH_OLDER)
1570                                 return (1);
1571                 } else if (f->ctime_sec < sec) {
1572                         if (f->flag & ARCHIVE_MATCH_NEWER)
1573                                 return (1);
1574                 } else {
1575                         nsec = archive_entry_ctime_nsec(entry);
1576                         if (f->ctime_nsec > nsec) {
1577                                 if (f->flag & ARCHIVE_MATCH_OLDER)
1578                                         return (1);
1579                         } else if (f->ctime_nsec < nsec) {
1580                                 if (f->flag & ARCHIVE_MATCH_NEWER)
1581                                         return (1);
1582                         } else if (f->flag & ARCHIVE_MATCH_EQUAL)
1583                                 return (1);
1584                 }
1585         }
1586         if (f->flag & ARCHIVE_MATCH_MTIME) {
1587                 sec = archive_entry_mtime(entry);
1588                 if (f->mtime_sec > sec) {
1589                         if (f->flag & ARCHIVE_MATCH_OLDER)
1590                                 return (1);
1591                 } else if (f->mtime_sec < sec) {
1592                         if (f->flag & ARCHIVE_MATCH_NEWER)
1593                                 return (1);
1594                 } else {
1595                         nsec = archive_entry_mtime_nsec(entry);
1596                         if (f->mtime_nsec > nsec) {
1597                                 if (f->flag & ARCHIVE_MATCH_OLDER)
1598                                         return (1);
1599                         } else if (f->mtime_nsec < nsec) {
1600                                 if (f->flag & ARCHIVE_MATCH_NEWER)
1601                                         return (1);
1602                         } else if (f->flag & ARCHIVE_MATCH_EQUAL)
1603                                 return (1);
1604                 }
1605         }
1606         return (0);
1607 }
1608
1609 /*
1610  * Utility functions to manage inclusion owners
1611  */
1612
1613 int
1614 archive_match_include_uid(struct archive *_a, la_int64_t uid)
1615 {
1616         struct archive_match *a;
1617
1618         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
1619             ARCHIVE_STATE_NEW, "archive_match_include_uid");
1620         a = (struct archive_match *)_a;
1621         return (add_owner_id(a, &(a->inclusion_uids), uid));
1622 }
1623
1624 int
1625 archive_match_include_gid(struct archive *_a, la_int64_t gid)
1626 {
1627         struct archive_match *a;
1628
1629         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
1630             ARCHIVE_STATE_NEW, "archive_match_include_gid");
1631         a = (struct archive_match *)_a;
1632         return (add_owner_id(a, &(a->inclusion_gids), gid));
1633 }
1634
1635 int
1636 archive_match_include_uname(struct archive *_a, const char *uname)
1637 {
1638         struct archive_match *a;
1639
1640         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
1641             ARCHIVE_STATE_NEW, "archive_match_include_uname");
1642         a = (struct archive_match *)_a;
1643         return (add_owner_name(a, &(a->inclusion_unames), 1, uname));
1644 }
1645
1646 int
1647 archive_match_include_uname_w(struct archive *_a, const wchar_t *uname)
1648 {
1649         struct archive_match *a;
1650
1651         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
1652             ARCHIVE_STATE_NEW, "archive_match_include_uname_w");
1653         a = (struct archive_match *)_a;
1654         return (add_owner_name(a, &(a->inclusion_unames), 0, uname));
1655 }
1656
1657 int
1658 archive_match_include_gname(struct archive *_a, const char *gname)
1659 {
1660         struct archive_match *a;
1661
1662         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
1663             ARCHIVE_STATE_NEW, "archive_match_include_gname");
1664         a = (struct archive_match *)_a;
1665         return (add_owner_name(a, &(a->inclusion_gnames), 1, gname));
1666 }
1667
1668 int
1669 archive_match_include_gname_w(struct archive *_a, const wchar_t *gname)
1670 {
1671         struct archive_match *a;
1672
1673         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
1674             ARCHIVE_STATE_NEW, "archive_match_include_gname_w");
1675         a = (struct archive_match *)_a;
1676         return (add_owner_name(a, &(a->inclusion_gnames), 0, gname));
1677 }
1678
1679 /*
1680  * Test function for owner(uid, gid, uname, gname).
1681  *
1682  * Returns 1 if archive entry is excluded.
1683  * Returns 0 if archive entry is not excluded.
1684  * Returns <0 if something error happened.
1685  */
1686 int
1687 archive_match_owner_excluded(struct archive *_a,
1688     struct archive_entry *entry)
1689 {
1690         struct archive_match *a;
1691
1692         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
1693             ARCHIVE_STATE_NEW, "archive_match_id_excluded_ae");
1694
1695         a = (struct archive_match *)_a;
1696         if (entry == NULL) {
1697                 archive_set_error(&(a->archive), EINVAL, "entry is NULL");
1698                 return (ARCHIVE_FAILED);
1699         }
1700
1701         /* If we don't have inclusion id set at all, the entry is always
1702          * not excluded. */
1703         if ((a->setflag & ID_IS_SET) == 0)
1704                 return (0);
1705         return (owner_excluded(a, entry));
1706 }
1707
1708 static int
1709 add_owner_id(struct archive_match *a, struct id_array *ids, int64_t id)
1710 {
1711         unsigned i;
1712
1713         if (ids->count + 1 >= ids->size) {
1714                 void *p;
1715
1716                 if (ids->size == 0)
1717                         ids->size = 8;
1718                 else
1719                         ids->size *= 2;
1720                 p = realloc(ids->ids, sizeof(*ids->ids) * ids->size);
1721                 if (p == NULL)
1722                         return (error_nomem(a));
1723                 ids->ids = (int64_t *)p;
1724         }
1725
1726         /* Find an insert point. */
1727         for (i = 0; i < ids->count; i++) {
1728                 if (ids->ids[i] >= id)
1729                         break;
1730         }
1731
1732         /* Add owner id. */
1733         if (i == ids->count)
1734                 ids->ids[ids->count++] = id;
1735         else if (ids->ids[i] != id) {
1736                 memmove(&(ids->ids[i+1]), &(ids->ids[i]),
1737                     (ids->count - i) * sizeof(ids->ids[0]));
1738                 ids->ids[i] = id;
1739                 ids->count++;
1740         }
1741         a->setflag |= ID_IS_SET;
1742         return (ARCHIVE_OK);
1743 }
1744
1745 static int
1746 match_owner_id(struct id_array *ids, int64_t id)
1747 {
1748         unsigned b, m, t;
1749
1750         t = 0;
1751         b = (unsigned)ids->count;
1752         while (t < b) {
1753                 m = (t + b)>>1;
1754                 if (ids->ids[m] == id)
1755                         return (1);
1756                 if (ids->ids[m] < id)
1757                         t = m + 1;
1758                 else
1759                         b = m;
1760         }
1761         return (0);
1762 }
1763
1764 static int
1765 add_owner_name(struct archive_match *a, struct match_list *list,
1766     int mbs, const void *name)
1767 {
1768         struct match *match;
1769
1770         match = calloc(1, sizeof(*match));
1771         if (match == NULL)
1772                 return (error_nomem(a));
1773         if (mbs)
1774                 archive_mstring_copy_mbs(&(match->pattern), name);
1775         else
1776                 archive_mstring_copy_wcs(&(match->pattern), name);
1777         match_list_add(list, match);
1778         a->setflag |= ID_IS_SET;
1779         return (ARCHIVE_OK);
1780 }
1781
1782 #if !defined(_WIN32) || defined(__CYGWIN__)
1783 static int
1784 match_owner_name_mbs(struct archive_match *a, struct match_list *list,
1785     const char *name)
1786 {
1787         struct match *m;
1788         const char *p;
1789
1790         if (name == NULL || *name == '\0')
1791                 return (0);
1792         for (m = list->first; m; m = m->next) {
1793                 if (archive_mstring_get_mbs(&(a->archive), &(m->pattern), &p)
1794                     < 0 && errno == ENOMEM)
1795                         return (error_nomem(a));
1796                 if (p != NULL && strcmp(p, name) == 0) {
1797                         m->matches++;
1798                         return (1);
1799                 }
1800         }
1801         return (0);
1802 }
1803 #else
1804 static int
1805 match_owner_name_wcs(struct archive_match *a, struct match_list *list,
1806     const wchar_t *name)
1807 {
1808         struct match *m;
1809         const wchar_t *p;
1810
1811         if (name == NULL || *name == L'\0')
1812                 return (0);
1813         for (m = list->first; m; m = m->next) {
1814                 if (archive_mstring_get_wcs(&(a->archive), &(m->pattern), &p)
1815                     < 0 && errno == ENOMEM)
1816                         return (error_nomem(a));
1817                 if (p != NULL && wcscmp(p, name) == 0) {
1818                         m->matches++;
1819                         return (1);
1820                 }
1821         }
1822         return (0);
1823 }
1824 #endif
1825
1826 /*
1827  * Test if entry is excluded by uid, gid, uname or gname.
1828  */
1829 static int
1830 owner_excluded(struct archive_match *a, struct archive_entry *entry)
1831 {
1832         int r;
1833
1834         if (a->inclusion_uids.count) {
1835                 if (!match_owner_id(&(a->inclusion_uids),
1836                     archive_entry_uid(entry)))
1837                         return (1);
1838         }
1839
1840         if (a->inclusion_gids.count) {
1841                 if (!match_owner_id(&(a->inclusion_gids),
1842                     archive_entry_gid(entry)))
1843                         return (1);
1844         }
1845
1846         if (a->inclusion_unames.count) {
1847 #if defined(_WIN32) && !defined(__CYGWIN__)
1848                 r = match_owner_name_wcs(a, &(a->inclusion_unames),
1849                         archive_entry_uname_w(entry));
1850 #else
1851                 r = match_owner_name_mbs(a, &(a->inclusion_unames),
1852                         archive_entry_uname(entry));
1853 #endif
1854                 if (!r)
1855                         return (1);
1856                 else if (r < 0)
1857                         return (r);
1858         }
1859
1860         if (a->inclusion_gnames.count) {
1861 #if defined(_WIN32) && !defined(__CYGWIN__)
1862                 r = match_owner_name_wcs(a, &(a->inclusion_gnames),
1863                         archive_entry_gname_w(entry));
1864 #else
1865                 r = match_owner_name_mbs(a, &(a->inclusion_gnames),
1866                         archive_entry_gname(entry));
1867 #endif
1868                 if (!r)
1869                         return (1);
1870                 else if (r < 0)
1871                         return (r);
1872         }
1873         return (0);
1874 }
1875