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