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_pathmatch.h"
  44 #include "archive_rb.h"
  45 #include "archive_string.h"
  46
  47 struct match {
  48         struct match            *next;
  49         int                      matches;
  50         struct archive_mstring   pattern;
  51 };
  52
  53 struct match_list {
  54         struct match            *first;
  55         struct match            **last;
  56         int                      count;
  57         int                      unmatched_count;
  58         struct match            *unmatched_next;
  59         int                      unmatched_eof;
  60 };
  61
  62 struct match_file {
  63         struct archive_rb_node   node;
  64         struct match_file       *next;
  65         struct archive_mstring   pathname;
  66         int                      flag;
  67         time_t                   mtime_sec;
  68         long                     mtime_nsec;
  69         time_t                   ctime_sec;
  70         long                     ctime_nsec;
  71 };
  72
  73 struct entry_list {
  74         struct match_file       *first;
  75         struct match_file       **last;
  76         int                      count;
  77 };
  78
  79 struct id_array {
  80         size_t                   size;/* Allocated size */
  81         size_t                   count;
  82         int64_t                 *ids;
  83 };
  84
  85 #define PATTERN_IS_SET          1
  86 #define TIME_IS_SET             2
  87 #define ID_IS_SET               4
  88
  89 struct archive_match {
  90         struct archive           archive;
  91
  92         /* exclusion/inclusion set flag. */
  93         int                      setflag;
  94
  95         /*
  96          * Matching filename patterns.
  97          */
  98         struct match_list        exclusions;
  99         struct match_list        inclusions;
 100
 101         /*
 102          * Matching time stamps.
 103          */
 104         time_t                   now;
 105         int                      newer_mtime_filter;
 106         time_t                   newer_mtime_sec;
 107         long                     newer_mtime_nsec;
 108         int                      newer_ctime_filter;
 109         time_t                   newer_ctime_sec;
 110         long                     newer_ctime_nsec;
 111         int                      older_mtime_filter;
 112         time_t                   older_mtime_sec;
 113         long                     older_mtime_nsec;
 114         int                      older_ctime_filter;
 115         time_t                   older_ctime_sec;
 116         long                     older_ctime_nsec;
 117         /*
 118          * Matching time stamps with its filename.
 119          */
 120         struct archive_rb_tree   exclusion_tree;
 121         struct entry_list        exclusion_entry_list;
 122
 123         /*
 124          * Matching file owners.
 125          */
 126         struct id_array          inclusion_uids;
 127         struct id_array          inclusion_gids;
 128         struct match_list        inclusion_unames;
 129         struct match_list        inclusion_gnames;
 130 };
 131
 132 static int      add_pattern_from_file(struct archive_match *,
 133                     struct match_list *, int, const void *, int);
 134 static int      add_entry(struct archive_match *, int,
 135                     struct archive_entry *);
 136 static int      add_owner_id(struct archive_match *, struct id_array *,
 137                     int64_t);
 138 static int      add_owner_name(struct archive_match *, struct match_list *,
 139                     int, const void *);
 140 static int      add_pattern_mbs(struct archive_match *, struct match_list *,
 141                     const char *);
 142 static int      add_pattern_wcs(struct archive_match *, struct match_list *,
 143                     const wchar_t *);
 144 static int      cmp_key_mbs(const struct archive_rb_node *, const void *);
 145 static int      cmp_key_wcs(const struct archive_rb_node *, const void *);
 146 static int      cmp_node_mbs(const struct archive_rb_node *,
 147                     const struct archive_rb_node *);
 148 static int      cmp_node_wcs(const struct archive_rb_node *,
 149                     const struct archive_rb_node *);
 150 static void     entry_list_add(struct entry_list *, struct match_file *);
 151 static void     entry_list_free(struct entry_list *);
 152 static void     entry_list_init(struct entry_list *);
 153 static int      error_nomem(struct archive_match *);
 154 static void     match_list_add(struct match_list *, struct match *);
 155 static void     match_list_free(struct match_list *);
 156 static void     match_list_init(struct match_list *);
 157 static int      match_list_unmatched_inclusions_next(struct archive_match *,
 158                     struct match_list *, int, const void **);
 159 static int      match_owner_id(struct id_array *, int64_t);
 160 #if !defined(_WIN32) || defined(__CYGWIN__)
 161 static int      match_owner_name_mbs(struct archive_match *,
 162                     struct match_list *, const char *);
 163 #else
 164 static int      match_owner_name_wcs(struct archive_match *,
 165                     struct match_list *, const wchar_t *);
 166 #endif
 167 static int      match_path_exclusion(struct archive_match *,
 168                     struct match *, int, const void *);
 169 static int      match_path_inclusion(struct archive_match *,
 170                     struct match *, int, const void *);
 171 static int      owner_excluded(struct archive_match *,
 172                     struct archive_entry *);
 173 static int      path_excluded(struct archive_match *, int, const void *);
 174 static int      set_timefilter(struct archive_match *, int, time_t, long,
 175                     time_t, long);
 176 static int      set_timefilter_pathname_mbs(struct archive_match *,
 177                     int, const char *);
 178 static int      set_timefilter_pathname_wcs(struct archive_match *,
 179                     int, const wchar_t *);
 180 static int      set_timefilter_date(struct archive_match *, int, const char *);
 181 static int      set_timefilter_date_w(struct archive_match *, int,
 182                     const wchar_t *);
 183 static int      time_excluded(struct archive_match *,
 184                     struct archive_entry *);
 185 static int      validate_time_flag(struct archive *, int, const char *);
 186
 187 time_t __archive_get_date(time_t now, const char *);
 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  * Utilty 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         if (r != ARCHIVE_OK) {
 584                 archive_copy_error(&(a->archive), ar);
 585                 archive_read_free(ar);
 586                 return (r);
 587         }
 588         if (mbs)
 589                 r = archive_read_open_filename(ar, pathname, 512*20);
 590         else
 591                 r = archive_read_open_filename_w(ar, pathname, 512*20);
 592         if (r != ARCHIVE_OK) {
 593                 archive_copy_error(&(a->archive), ar);
 594                 archive_read_free(ar);
 595                 return (r);
 596         }
 597         r = archive_read_next_header(ar, &ae);
 598         if (r != ARCHIVE_OK) {
 599                 archive_copy_error(&(a->archive), ar);
 600                 archive_read_free(ar);
 601                 return (r);
 602         }
 603
 604         archive_string_init(&as);
 605
 606         while ((r = archive_read_data_block(ar, &buff, &size, &offset))
 607             == ARCHIVE_OK) {
 608                 const char *b = (const char *)buff;
 609
 610                 while (size) {
 611                         const char *s = (const char *)b;
 612                         size_t length = 0;
 613                         int found_separator = 0;
 614
 615                         while (length < size) {
 616                                 if (nullSeparator) {
 617                                         if (*b == '\0') {
 618                                                 found_separator = 1;
 619                                                 break;
 620                                         }
 621                                 } else {
 622                                         if (*b == 0x0d || *b == 0x0a) {
 623                                                 found_separator = 1;
 624                                                 break;
 625                                         }
 626                                 }
 627                                 b++;
 628                                 length++;
 629                         }
 630                         if (!found_separator) {
 631                                 archive_strncat(&as, s, length);
 632                                 /* Read next data block. */
 633                                 break;
 634                         }
 635                         b++;
 636                         size -= length + 1;
 637                         archive_strncat(&as, s, length);
 638
 639                         /* If the line is not empty, add the pattern. */
 640                         if (archive_strlen(&as) > 0) {
 641                                 /* Add pattern. */
 642                                 r = add_pattern_mbs(a, mlist, as.s);
 643                                 if (r != ARCHIVE_OK) {
 644                                         archive_read_free(ar);
 645                                         archive_string_free(&as);
 646                                         return (r);
 647                                 }
 648                                 archive_string_empty(&as);
 649                         }
 650                 }
 651         }
 652
 653         /* If something error happend, report it immediately. */
 654         if (r < ARCHIVE_OK) {
 655                 archive_copy_error(&(a->archive), ar);
 656                 archive_read_free(ar);
 657                 archive_string_free(&as);
 658                 return (r);
 659         }
 660
 661         /* If the line is not empty, add the pattern. */
 662         if (r == ARCHIVE_EOF && archive_strlen(&as) > 0) {
 663                 /* Add pattern. */
 664                 r = add_pattern_mbs(a, mlist, as.s);
 665                 if (r != ARCHIVE_OK) {
 666                         archive_read_free(ar);
 667                         archive_string_free(&as);
 668                         return (r);
 669                 }
 670         }
 671         archive_read_free(ar);
 672         archive_string_free(&as);
 673         return (ARCHIVE_OK);
 674 }
 675
 676 /*
 677  * Test if pathname is excluded by inclusion/exclusion patterns.
 678  */
 679 static int
 680 path_excluded(struct archive_match *a, int mbs, const void *pathname)
 681 {
 682         struct match *match;
 683         struct match *matched;
 684         int r;
 685
 686         if (a == NULL)
 687                 return (0);
 688
 689         /* Mark off any unmatched inclusions. */
 690         /* In particular, if a filename does appear in the archive and
 691          * is explicitly included and excluded, then we don't report
 692          * it as missing even though we don't extract it.
 693          */
 694         matched = NULL;
 695         for (match = a->inclusions.first; match != NULL;
 696             match = match->next){
 697                 if (match->matches == 0 &&
 698                     (r = match_path_inclusion(a, match, mbs, pathname)) != 0) {
 699                         if (r < 0)
 700                                 return (r);
 701                         a->inclusions.unmatched_count--;
 702                         match->matches++;
 703                         matched = match;
 704                 }
 705         }
 706
 707         /* Exclusions take priority */
 708         for (match = a->exclusions.first; match != NULL;
 709             match = match->next){
 710                 r = match_path_exclusion(a, match, mbs, pathname);
 711                 if (r)
 712                         return (r);
 713         }
 714
 715         /* It's not excluded and we found an inclusion above, so it's
 716          * included. */
 717         if (matched != NULL)
 718                 return (0);
 719
 720
 721         /* We didn't find an unmatched inclusion, check the remaining ones. */
 722         for (match = a->inclusions.first; match != NULL;
 723             match = match->next){
 724                 /* We looked at previously-unmatched inclusions already. */
 725                 if (match->matches > 0 &&
 726                     (r = match_path_inclusion(a, match, mbs, pathname)) != 0) {
 727                         if (r < 0)
 728                                 return (r);
 729                         match->matches++;
 730                         return (0);
 731                 }
 732         }
 733
 734         /* If there were inclusions, default is to exclude. */
 735         if (a->inclusions.first != NULL)
 736             return (1);
 737
 738         /* No explicit inclusions, default is to match. */
 739         return (0);
 740 }
 741
 742 /*
 743  * This is a little odd, but it matches the default behavior of
 744  * gtar.  In particular, 'a*b' will match 'foo/a1111/222b/bar'
 745  *
 746  */
 747 static int
 748 match_path_exclusion(struct archive_match *a, struct match *m,
 749     int mbs, const void *pn)
 750 {
 751         int flag = PATHMATCH_NO_ANCHOR_START | PATHMATCH_NO_ANCHOR_END;
 752         int r;
 753
 754         if (mbs) {
 755                 const char *p;
 756                 r = archive_mstring_get_mbs(&(a->archive), &(m->pattern), &p);
 757                 if (r == 0)
 758                         return (archive_pathmatch(p, (const char *)pn, flag));
 759         } else {
 760                 const wchar_t *p;
 761                 r = archive_mstring_get_wcs(&(a->archive), &(m->pattern), &p);
 762                 if (r == 0)
 763                         return (archive_pathmatch_w(p, (const wchar_t *)pn,
 764                                 flag));
 765         }
 766         if (errno == ENOMEM)
 767                 return (error_nomem(a));
 768         return (0);
 769 }
 770
 771 /*
 772  * Again, mimic gtar:  inclusions are always anchored (have to match
 773  * the beginning of the path) even though exclusions are not anchored.
 774  */
 775 static int
 776 match_path_inclusion(struct archive_match *a, struct match *m,
 777     int mbs, const void *pn)
 778 {
 779         int flag = PATHMATCH_NO_ANCHOR_END;
 780         int r;
 781
 782         if (mbs) {
 783                 const char *p;
 784                 r = archive_mstring_get_mbs(&(a->archive), &(m->pattern), &p);
 785                 if (r == 0)
 786                         return (archive_pathmatch(p, (const char *)pn, flag));
 787         } else {
 788                 const wchar_t *p;
 789                 r = archive_mstring_get_wcs(&(a->archive), &(m->pattern), &p);
 790                 if (r == 0)
 791                         return (archive_pathmatch_w(p, (const wchar_t *)pn,
 792                                 flag));
 793         }
 794         if (errno == ENOMEM)
 795                 return (error_nomem(a));
 796         return (0);
 797 }
 798
 799 static void
 800 match_list_init(struct match_list *list)
 801 {
 802         list->first = NULL;
 803         list->last = &(list->first);
 804         list->count = 0;
 805 }
 806
 807 static void
 808 match_list_free(struct match_list *list)
 809 {
 810         struct match *p, *q;
 811
 812         for (p = list->first; p != NULL; ) {
 813                 q = p;
 814                 p = p->next;
 815                 archive_mstring_clean(&(q->pattern));
 816                 free(q);
 817         }
 818 }
 819
 820 static void
 821 match_list_add(struct match_list *list, struct match *m)
 822 {
 823         *list->last = m;
 824         list->last = &(m->next);
 825         list->count++;
 826         list->unmatched_count++;
 827 }
 828
 829 static int
 830 match_list_unmatched_inclusions_next(struct archive_match *a,
 831     struct match_list *list, int mbs, const void **vp)
 832 {
 833         struct match *m;
 834
 835         *vp = NULL;
 836         if (list->unmatched_eof) {
 837                 list->unmatched_eof = 0;
 838                 return (ARCHIVE_EOF);
 839         }
 840         if (list->unmatched_next == NULL) {
 841                 if (list->unmatched_count == 0)
 842                         return (ARCHIVE_EOF);
 843                 list->unmatched_next = list->first;
 844         }
 845
 846         for (m = list->unmatched_next; m != NULL; m = m->next) {
 847                 int r;
 848
 849                 if (m->matches)
 850                         continue;
 851                 if (mbs) {
 852                         const char *p;
 853                         r = archive_mstring_get_mbs(&(a->archive),
 854                                 &(m->pattern), &p);
 855                         if (r < 0 && errno == ENOMEM)
 856                                 return (error_nomem(a));
 857                         if (p == NULL)
 858                                 p = "";
 859                         *vp = p;
 860                 } else {
 861                         const wchar_t *p;
 862                         r = archive_mstring_get_wcs(&(a->archive),
 863                                 &(m->pattern), &p);
 864                         if (r < 0 && errno == ENOMEM)
 865                                 return (error_nomem(a));
 866                         if (p == NULL)
 867                                 p = L"";
 868                         *vp = p;
 869                 }
 870                 list->unmatched_next = m->next;
 871                 if (list->unmatched_next == NULL)
 872                         /* To return EOF next time. */
 873                         list->unmatched_eof = 1;
 874                 return (ARCHIVE_OK);
 875         }
 876         list->unmatched_next = NULL;
 877         return (ARCHIVE_EOF);
 878 }
 879
 880 /*
 881  * Utility functions to manage inclusion timestamps.
 882  */
 883 int
 884 archive_match_include_time(struct archive *_a, int flag, time_t sec,
 885     long nsec)
 886 {
 887         int r;
 888
 889         r = validate_time_flag(_a, flag, "archive_match_include_time");
 890         if (r != ARCHIVE_OK)
 891                 return (r);
 892         return set_timefilter((struct archive_match *)_a, flag,
 893                         sec, nsec, sec, nsec);
 894 }
 895
 896 int
 897 archive_match_include_date(struct archive *_a, int flag,
 898     const char *datestr)
 899 {
 900         int r;
 901
 902         r = validate_time_flag(_a, flag, "archive_match_include_date");
 903         if (r != ARCHIVE_OK)
 904                 return (r);
 905         return set_timefilter_date((struct archive_match *)_a, flag, datestr);
 906 }
 907
 908 int
 909 archive_match_include_date_w(struct archive *_a, int flag,
 910     const wchar_t *datestr)
 911 {
 912         int r;
 913
 914         r = validate_time_flag(_a, flag, "archive_match_include_date_w");
 915         if (r != ARCHIVE_OK)
 916                 return (r);
 917
 918         return set_timefilter_date_w((struct archive_match *)_a, flag, datestr);
 919 }
 920
 921 int
 922 archive_match_include_file_time(struct archive *_a, int flag,
 923     const char *pathname)
 924 {
 925         int r;
 926
 927         r = validate_time_flag(_a, flag, "archive_match_include_file_time");
 928         if (r != ARCHIVE_OK)
 929                 return (r);
 930         return set_timefilter_pathname_mbs((struct archive_match *)_a,
 931                         flag, pathname);
 932 }
 933
 934 int
 935 archive_match_include_file_time_w(struct archive *_a, int flag,
 936     const wchar_t *pathname)
 937 {
 938         int r;
 939
 940         r = validate_time_flag(_a, flag, "archive_match_include_file_time_w");
 941         if (r != ARCHIVE_OK)
 942                 return (r);
 943         return set_timefilter_pathname_wcs((struct archive_match *)_a,
 944                         flag, pathname);
 945 }
 946
 947 int
 948 archive_match_exclude_entry(struct archive *_a, int flag,
 949     struct archive_entry *entry)
 950 {
 951         struct archive_match *a;
 952         int r;
 953
 954         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
 955             ARCHIVE_STATE_NEW, "archive_match_time_include_entry");
 956         a = (struct archive_match *)_a;
 957
 958         if (entry == NULL) {
 959                 archive_set_error(&(a->archive), EINVAL, "entry is NULL");
 960                 return (ARCHIVE_FAILED);
 961         }
 962         r = validate_time_flag(_a, flag, "archive_match_exclude_entry");
 963         if (r != ARCHIVE_OK)
 964                 return (r);
 965         return (add_entry(a, flag, entry));
 966 }
 967
 968 /*
 969  * Test function for time stamps.
 970  *
 971  * Returns 1 if archive entry is excluded.
 972  * Returns 0 if archive entry is not excluded.
 973  * Returns <0 if something error happened.
 974  */
 975 int
 976 archive_match_time_excluded(struct archive *_a,
 977     struct archive_entry *entry)
 978 {
 979         struct archive_match *a;
 980
 981         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
 982             ARCHIVE_STATE_NEW, "archive_match_time_excluded_ae");
 983
 984         a = (struct archive_match *)_a;
 985         if (entry == NULL) {
 986                 archive_set_error(&(a->archive), EINVAL, "entry is NULL");
 987                 return (ARCHIVE_FAILED);
 988         }
 989
 990         /* If we don't have inclusion time set at all, the entry is always
 991          * not excluded. */
 992         if ((a->setflag & TIME_IS_SET) == 0)
 993                 return (0);
 994         return (time_excluded(a, entry));
 995 }
 996
 997 static int
 998 validate_time_flag(struct archive *_a, int flag, const char *_fn)
 999 {
1000         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
1001             ARCHIVE_STATE_NEW, _fn);
1002
1003         /* Check a type of time. */
1004         if (flag &
1005            ((~(ARCHIVE_MATCH_MTIME | ARCHIVE_MATCH_CTIME)) & 0xff00)) {
1006                 archive_set_error(_a, EINVAL, "Invalid time flag");
1007                 return (ARCHIVE_FAILED);
1008         }
1009         if ((flag & (ARCHIVE_MATCH_MTIME | ARCHIVE_MATCH_CTIME)) == 0) {
1010                 archive_set_error(_a, EINVAL, "No time flag");
1011                 return (ARCHIVE_FAILED);
1012         }
1013
1014         /* Check a type of comparison. */
1015         if (flag &
1016            ((~(ARCHIVE_MATCH_NEWER | ARCHIVE_MATCH_OLDER
1017                         | ARCHIVE_MATCH_EQUAL)) & 0x00ff)) {
1018                 archive_set_error(_a, EINVAL, "Invalid comparison flag");
1019                 return (ARCHIVE_FAILED);
1020         }
1021         if ((flag & (ARCHIVE_MATCH_NEWER | ARCHIVE_MATCH_OLDER
1022             | ARCHIVE_MATCH_EQUAL)) == 0) {
1023                 archive_set_error(_a, EINVAL, "No comparison flag");
1024                 return (ARCHIVE_FAILED);
1025         }
1026
1027         return (ARCHIVE_OK);
1028 }
1029
1030 #define JUST_EQUAL(t) (((t) &  (ARCHIVE_MATCH_EQUAL |\
1031         ARCHIVE_MATCH_NEWER | ARCHIVE_MATCH_OLDER)) == ARCHIVE_MATCH_EQUAL)
1032 static int
1033 set_timefilter(struct archive_match *a, int timetype,
1034     time_t mtime_sec, long mtime_nsec, time_t ctime_sec, long ctime_nsec)
1035 {
1036         if (timetype & ARCHIVE_MATCH_MTIME) {
1037                 if ((timetype & ARCHIVE_MATCH_NEWER) || JUST_EQUAL(timetype)) {
1038                         a->newer_mtime_filter = timetype;
1039                         a->newer_mtime_sec = mtime_sec;
1040                         a->newer_mtime_nsec = mtime_nsec;
1041                         a->setflag |= TIME_IS_SET;
1042                 }
1043                 if ((timetype & ARCHIVE_MATCH_OLDER) || JUST_EQUAL(timetype)) {
1044                         a->older_mtime_filter = timetype;
1045                         a->older_mtime_sec = mtime_sec;
1046                         a->older_mtime_nsec = mtime_nsec;
1047                         a->setflag |= TIME_IS_SET;
1048                 }
1049         }
1050         if (timetype & ARCHIVE_MATCH_CTIME) {
1051                 if ((timetype & ARCHIVE_MATCH_NEWER) || JUST_EQUAL(timetype)) {
1052                         a->newer_ctime_filter = timetype;
1053                         a->newer_ctime_sec = ctime_sec;
1054                         a->newer_ctime_nsec = ctime_nsec;
1055                         a->setflag |= TIME_IS_SET;
1056                 }
1057                 if ((timetype & ARCHIVE_MATCH_OLDER) || JUST_EQUAL(timetype)) {
1058                         a->older_ctime_filter = timetype;
1059                         a->older_ctime_sec = ctime_sec;
1060                         a->older_ctime_nsec = ctime_nsec;
1061                         a->setflag |= TIME_IS_SET;
1062                 }
1063         }
1064         return (ARCHIVE_OK);
1065 }
1066
1067 static int
1068 set_timefilter_date(struct archive_match *a, int timetype, const char *datestr)
1069 {
1070         time_t t;
1071
1072         if (datestr == NULL || *datestr == '\0') {
1073                 archive_set_error(&(a->archive), EINVAL, "date is empty");
1074                 return (ARCHIVE_FAILED);
1075         }
1076         t = get_date(a->now, datestr);
1077         if (t == (time_t)-1) {
1078                 archive_set_error(&(a->archive), EINVAL, "invalid date string");
1079                 return (ARCHIVE_FAILED);
1080         }
1081         return set_timefilter(a, timetype, t, 0, t, 0);
1082 }
1083
1084 static int
1085 set_timefilter_date_w(struct archive_match *a, int timetype,
1086     const wchar_t *datestr)
1087 {
1088         struct archive_string as;
1089         time_t t;
1090
1091         if (datestr == NULL || *datestr == L'\0') {
1092                 archive_set_error(&(a->archive), EINVAL, "date is empty");
1093                 return (ARCHIVE_FAILED);
1094         }
1095
1096         archive_string_init(&as);
1097         if (archive_string_append_from_wcs(&as, datestr, wcslen(datestr)) < 0) {
1098                 archive_string_free(&as);
1099                 if (errno == ENOMEM)
1100                         return (error_nomem(a));
1101                 archive_set_error(&(a->archive), -1,
1102                     "Failed to convert WCS to MBS");
1103                 return (ARCHIVE_FAILED);
1104         }
1105         t = get_date(a->now, as.s);
1106         archive_string_free(&as);
1107         if (t == (time_t)-1) {
1108                 archive_set_error(&(a->archive), EINVAL, "invalid date string");
1109                 return (ARCHIVE_FAILED);
1110         }
1111         return set_timefilter(a, timetype, t, 0, t, 0);
1112 }
1113
1114 #if defined(_WIN32) && !defined(__CYGWIN__)
1115 #define EPOC_TIME ARCHIVE_LITERAL_ULL(116444736000000000)
1116 static int
1117 set_timefilter_find_data(struct archive_match *a, int timetype,
1118     DWORD ftLastWriteTime_dwHighDateTime, DWORD ftLastWriteTime_dwLowDateTime,
1119     DWORD ftCreationTime_dwHighDateTime, DWORD ftCreationTime_dwLowDateTime)
1120 {
1121         ULARGE_INTEGER utc;
1122         time_t ctime_sec, mtime_sec;
1123         long ctime_ns, mtime_ns;
1124
1125         utc.HighPart = ftCreationTime_dwHighDateTime;
1126         utc.LowPart = ftCreationTime_dwLowDateTime;
1127         if (utc.QuadPart >= EPOC_TIME) {
1128                 utc.QuadPart -= EPOC_TIME;
1129                 ctime_sec = (time_t)(utc.QuadPart / 10000000);
1130                 ctime_ns = (long)(utc.QuadPart % 10000000) * 100;
1131         } else {
1132                 ctime_sec = 0;
1133                 ctime_ns = 0;
1134         }
1135         utc.HighPart = ftLastWriteTime_dwHighDateTime;
1136         utc.LowPart = ftLastWriteTime_dwLowDateTime;
1137         if (utc.QuadPart >= EPOC_TIME) {
1138                 utc.QuadPart -= EPOC_TIME;
1139                 mtime_sec = (time_t)(utc.QuadPart / 10000000);
1140                 mtime_ns = (long)(utc.QuadPart % 10000000) * 100;
1141         } else {
1142                 mtime_sec = 0;
1143                 mtime_ns = 0;
1144         }
1145         return set_timefilter(a, timetype,
1146                         mtime_sec, mtime_ns, ctime_sec, ctime_ns);
1147 }
1148
1149 static int
1150 set_timefilter_pathname_mbs(struct archive_match *a, int timetype,
1151     const char *path)
1152 {
1153         /* NOTE: stat() on Windows cannot handle nano seconds. */
1154         HANDLE h;
1155         WIN32_FIND_DATA d;
1156
1157         if (path == NULL || *path == '\0') {
1158                 archive_set_error(&(a->archive), EINVAL, "pathname is empty");
1159                 return (ARCHIVE_FAILED);
1160         }
1161         h = FindFirstFileA(path, &d);
1162         if (h == INVALID_HANDLE_VALUE) {
1163                 la_dosmaperr(GetLastError());
1164                 archive_set_error(&(a->archive), errno,
1165                     "Failed to FindFirstFileA");
1166                 return (ARCHIVE_FAILED);
1167         }
1168         FindClose(h);
1169         return set_timefilter_find_data(a, timetype,
1170             d.ftLastWriteTime.dwHighDateTime, d.ftLastWriteTime.dwLowDateTime,
1171             d.ftCreationTime.dwHighDateTime, d.ftCreationTime.dwLowDateTime);
1172 }
1173
1174 static int
1175 set_timefilter_pathname_wcs(struct archive_match *a, int timetype,
1176     const wchar_t *path)
1177 {
1178         HANDLE h;
1179         WIN32_FIND_DATAW d;
1180
1181         if (path == NULL || *path == L'\0') {
1182                 archive_set_error(&(a->archive), EINVAL, "pathname is empty");
1183                 return (ARCHIVE_FAILED);
1184         }
1185         h = FindFirstFileW(path, &d);
1186         if (h == INVALID_HANDLE_VALUE) {
1187                 la_dosmaperr(GetLastError());
1188                 archive_set_error(&(a->archive), errno,
1189                     "Failed to FindFirstFile");
1190                 return (ARCHIVE_FAILED);
1191         }
1192         FindClose(h);
1193         return set_timefilter_find_data(a, timetype,
1194             d.ftLastWriteTime.dwHighDateTime, d.ftLastWriteTime.dwLowDateTime,
1195             d.ftCreationTime.dwHighDateTime, d.ftCreationTime.dwLowDateTime);
1196 }
1197
1198 #else /* _WIN32 && !__CYGWIN__ */
1199
1200 static int
1201 set_timefilter_stat(struct archive_match *a, int timetype, struct stat *st)
1202 {
1203         struct archive_entry *ae;
1204         time_t ctime_sec, mtime_sec;
1205         long ctime_ns, mtime_ns;
1206
1207         ae = archive_entry_new();
1208         if (ae == NULL)
1209                 return (error_nomem(a));
1210         archive_entry_copy_stat(ae, st);
1211         ctime_sec = archive_entry_ctime(ae);
1212         ctime_ns = archive_entry_ctime_nsec(ae);
1213         mtime_sec = archive_entry_mtime(ae);
1214         mtime_ns = archive_entry_mtime_nsec(ae);
1215         archive_entry_free(ae);
1216         return set_timefilter(a, timetype, mtime_sec, mtime_ns,
1217                         ctime_sec, ctime_ns);
1218 }
1219
1220 static int
1221 set_timefilter_pathname_mbs(struct archive_match *a, int timetype,
1222     const char *path)
1223 {
1224         struct stat st;
1225
1226         if (path == NULL || *path == '\0') {
1227                 archive_set_error(&(a->archive), EINVAL, "pathname is empty");
1228                 return (ARCHIVE_FAILED);
1229         }
1230         if (stat(path, &st) != 0) {
1231                 archive_set_error(&(a->archive), errno, "Failed to stat()");
1232                 return (ARCHIVE_FAILED);
1233         }
1234         return (set_timefilter_stat(a, timetype, &st));
1235 }
1236
1237 static int
1238 set_timefilter_pathname_wcs(struct archive_match *a, int timetype,
1239     const wchar_t *path)
1240 {
1241         struct archive_string as;
1242         int r;
1243
1244         if (path == NULL || *path == L'\0') {
1245                 archive_set_error(&(a->archive), EINVAL, "pathname is empty");
1246                 return (ARCHIVE_FAILED);
1247         }
1248
1249         /* Convert WCS filename to MBS filename. */
1250         archive_string_init(&as);
1251         if (archive_string_append_from_wcs(&as, path, wcslen(path)) < 0) {
1252                 archive_string_free(&as);
1253                 if (errno == ENOMEM)
1254                         return (error_nomem(a));
1255                 archive_set_error(&(a->archive), -1,
1256                     "Failed to convert WCS to MBS");
1257                 return (ARCHIVE_FAILED);
1258         }
1259
1260         r = set_timefilter_pathname_mbs(a, timetype, as.s);
1261         archive_string_free(&as);
1262
1263         return (r);
1264 }
1265 #endif /* _WIN32 && !__CYGWIN__ */
1266
1267 /*
1268  * Call back funtions for archive_rb.
1269  */
1270 static int
1271 cmp_node_mbs(const struct archive_rb_node *n1,
1272     const struct archive_rb_node *n2)
1273 {
1274         struct match_file *f1 = (struct match_file *)(uintptr_t)n1;
1275         struct match_file *f2 = (struct match_file *)(uintptr_t)n2;
1276         const char *p1, *p2;
1277
1278         archive_mstring_get_mbs(NULL, &(f1->pathname), &p1);
1279         archive_mstring_get_mbs(NULL, &(f2->pathname), &p2);
1280         if (p1 == NULL)
1281                 return (1);
1282         if (p2 == NULL)
1283                 return (-1);
1284         return (strcmp(p1, p2));
1285 }
1286
1287 static int
1288 cmp_key_mbs(const struct archive_rb_node *n, const void *key)
1289 {
1290         struct match_file *f = (struct match_file *)(uintptr_t)n;
1291         const char *p;
1292
1293         archive_mstring_get_mbs(NULL, &(f->pathname), &p);
1294         if (p == NULL)
1295                 return (-1);
1296         return (strcmp(p, (const char *)key));
1297 }
1298
1299 static int
1300 cmp_node_wcs(const struct archive_rb_node *n1,
1301     const struct archive_rb_node *n2)
1302 {
1303         struct match_file *f1 = (struct match_file *)(uintptr_t)n1;
1304         struct match_file *f2 = (struct match_file *)(uintptr_t)n2;
1305         const wchar_t *p1, *p2;
1306
1307         archive_mstring_get_wcs(NULL, &(f1->pathname), &p1);
1308         archive_mstring_get_wcs(NULL, &(f2->pathname), &p2);
1309         if (p1 == NULL)
1310                 return (1);
1311         if (p2 == NULL)
1312                 return (-1);
1313         return (wcscmp(p1, p2));
1314 }
1315
1316 static int
1317 cmp_key_wcs(const struct archive_rb_node *n, const void *key)
1318 {
1319         struct match_file *f = (struct match_file *)(uintptr_t)n;
1320         const wchar_t *p;
1321
1322         archive_mstring_get_wcs(NULL, &(f->pathname), &p);
1323         if (p == NULL)
1324                 return (-1);
1325         return (wcscmp(p, (const wchar_t *)key));
1326 }
1327
1328 static void
1329 entry_list_init(struct entry_list *list)
1330 {
1331         list->first = NULL;
1332         list->last = &(list->first);
1333         list->count = 0;
1334 }
1335
1336 static void
1337 entry_list_free(struct entry_list *list)
1338 {
1339         struct match_file *p, *q;
1340
1341         for (p = list->first; p != NULL; ) {
1342                 q = p;
1343                 p = p->next;
1344                 archive_mstring_clean(&(q->pathname));
1345                 free(q);
1346         }
1347 }
1348
1349 static void
1350 entry_list_add(struct entry_list *list, struct match_file *file)
1351 {
1352         *list->last = file;
1353         list->last = &(file->next);
1354         list->count++;
1355 }
1356
1357 static int
1358 add_entry(struct archive_match *a, int flag,
1359     struct archive_entry *entry)
1360 {
1361         struct match_file *f;
1362         const void *pathname;
1363         int r;
1364
1365         f = calloc(1, sizeof(*f));
1366         if (f == NULL)
1367                 return (error_nomem(a));
1368
1369 #if defined(_WIN32) && !defined(__CYGWIN__)
1370         pathname = archive_entry_pathname_w(entry);
1371         if (pathname == NULL) {
1372                 free(f);
1373                 archive_set_error(&(a->archive), EINVAL, "pathname is NULL");
1374                 return (ARCHIVE_FAILED);
1375         }
1376         archive_mstring_copy_wcs(&(f->pathname), pathname);
1377         a->exclusion_tree.rbt_ops = &rb_ops_wcs;
1378 #else
1379         (void)rb_ops_wcs;
1380         pathname = archive_entry_pathname(entry);
1381         if (pathname == NULL) {
1382                 free(f);
1383                 archive_set_error(&(a->archive), EINVAL, "pathname is NULL");
1384                 return (ARCHIVE_FAILED);
1385         }
1386         archive_mstring_copy_mbs(&(f->pathname), pathname);
1387         a->exclusion_tree.rbt_ops = &rb_ops_mbs;
1388 #endif
1389         f->flag = flag;
1390         f->mtime_sec = archive_entry_mtime(entry);
1391         f->mtime_nsec = archive_entry_mtime_nsec(entry);
1392         f->ctime_sec = archive_entry_ctime(entry);
1393         f->ctime_nsec = archive_entry_ctime_nsec(entry);
1394         r = __archive_rb_tree_insert_node(&(a->exclusion_tree), &(f->node));
1395         if (!r) {
1396                 struct match_file *f2;
1397
1398                 /* Get the duplicated file. */
1399                 f2 = (struct match_file *)__archive_rb_tree_find_node(
1400                         &(a->exclusion_tree), pathname);
1401
1402                 /*
1403                  * We always overwrite comparison condision.
1404                  * If you do not want to overwrite it, you should not
1405                  * call archive_match_exclude_entry(). We cannot know
1406                  * what behavior you really expect since overwriting
1407                  * condition might be different with the flag.
1408                  */
1409                 if (f2 != NULL) {
1410                         f2->flag = f->flag;
1411                         f2->mtime_sec = f->mtime_sec;
1412                         f2->mtime_nsec = f->mtime_nsec;
1413                         f2->ctime_sec = f->ctime_sec;
1414                         f2->ctime_nsec = f->ctime_nsec;
1415                 }
1416                 /* Release the duplicated file. */
1417                 archive_mstring_clean(&(f->pathname));
1418                 free(f);
1419                 return (ARCHIVE_OK);
1420         }
1421         entry_list_add(&(a->exclusion_entry_list), f);
1422         a->setflag |= TIME_IS_SET;
1423         return (ARCHIVE_OK);
1424 }
1425
1426 /*
1427  * Test if entry is excluded by its timestamp.
1428  */
1429 static int
1430 time_excluded(struct archive_match *a, struct archive_entry *entry)
1431 {
1432         struct match_file *f;
1433         const void *pathname;
1434         time_t sec;
1435         long nsec;
1436
1437         /*
1438          * If this file/dir is excluded by a time comparison, skip it.
1439          */
1440         if (a->newer_ctime_filter) {
1441                 /* If ctime is not set, use mtime instead. */
1442                 if (archive_entry_ctime_is_set(entry))
1443                         sec = archive_entry_ctime(entry);
1444                 else
1445                         sec = archive_entry_mtime(entry);
1446                 if (sec < a->newer_ctime_sec)
1447                         return (1); /* Too old, skip it. */
1448                 if (sec == a->newer_ctime_sec) {
1449                         if (archive_entry_ctime_is_set(entry))
1450                                 nsec = archive_entry_ctime_nsec(entry);
1451                         else
1452                                 nsec = archive_entry_mtime_nsec(entry);
1453                         if (nsec < a->newer_ctime_nsec)
1454                                 return (1); /* Too old, skip it. */
1455                         if (nsec == a->newer_ctime_nsec &&
1456                             (a->newer_ctime_filter & ARCHIVE_MATCH_EQUAL)
1457                               == 0)
1458                                 return (1); /* Equal, skip it. */
1459                 }
1460         }
1461         if (a->older_ctime_filter) {
1462                 /* If ctime is not set, use mtime instead. */
1463                 if (archive_entry_ctime_is_set(entry))
1464                         sec = archive_entry_ctime(entry);
1465                 else
1466                         sec = archive_entry_mtime(entry);
1467                 if (sec > a->older_ctime_sec)
1468                         return (1); /* Too new, skip it. */
1469                 if (sec == a->older_ctime_sec) {
1470                         if (archive_entry_ctime_is_set(entry))
1471                                 nsec = archive_entry_ctime_nsec(entry);
1472                         else
1473                                 nsec = archive_entry_mtime_nsec(entry);
1474                         if (nsec > a->older_ctime_nsec)
1475                                 return (1); /* Too new, skip it. */
1476                         if (nsec == a->older_ctime_nsec &&
1477                             (a->older_ctime_filter & ARCHIVE_MATCH_EQUAL)
1478                               == 0)
1479                                 return (1); /* Eeual, skip it. */
1480                 }
1481         }
1482         if (a->newer_mtime_filter) {
1483                 sec = archive_entry_mtime(entry);
1484                 if (sec < a->newer_mtime_sec)
1485                         return (1); /* Too old, skip it. */
1486                 if (sec == a->newer_mtime_sec) {
1487                         nsec = archive_entry_mtime_nsec(entry);
1488                         if (nsec < a->newer_mtime_nsec)
1489                                 return (1); /* Too old, skip it. */
1490                         if (nsec == a->newer_mtime_nsec &&
1491                             (a->newer_mtime_filter & ARCHIVE_MATCH_EQUAL)
1492                                == 0)
1493                                 return (1); /* Equal, skip it. */
1494                 }
1495         }
1496         if (a->older_mtime_filter) {
1497                 sec = archive_entry_mtime(entry);
1498                 if (sec > a->older_mtime_sec)
1499                         return (1); /* Too new, skip it. */
1500                 nsec = archive_entry_mtime_nsec(entry);
1501                 if (sec == a->older_mtime_sec) {
1502                         if (nsec > a->older_mtime_nsec)
1503                                 return (1); /* Too new, skip it. */
1504                         if (nsec == a->older_mtime_nsec &&
1505                             (a->older_mtime_filter & ARCHIVE_MATCH_EQUAL)
1506                                == 0)
1507                                 return (1); /* Equal, skip it. */
1508                 }
1509         }
1510
1511         /* If there is no excluson list, include the file. */
1512         if (a->exclusion_entry_list.count == 0)
1513                 return (0);
1514
1515 #if defined(_WIN32) && !defined(__CYGWIN__)
1516         pathname = archive_entry_pathname_w(entry);
1517         a->exclusion_tree.rbt_ops = &rb_ops_wcs;
1518 #else
1519         (void)rb_ops_wcs;
1520         pathname = archive_entry_pathname(entry);
1521         a->exclusion_tree.rbt_ops = &rb_ops_mbs;
1522 #endif
1523         if (pathname == NULL)
1524                 return (0);
1525
1526         f = (struct match_file *)__archive_rb_tree_find_node(
1527                 &(a->exclusion_tree), pathname);
1528         /* If the file wasn't rejected, include it. */
1529         if (f == NULL)
1530                 return (0);
1531
1532         if (f->flag & ARCHIVE_MATCH_CTIME) {
1533                 sec = archive_entry_ctime(entry);
1534                 if (f->ctime_sec > sec) {
1535                         if (f->flag & ARCHIVE_MATCH_OLDER)
1536                                 return (1);
1537                 } else if (f->ctime_sec < sec) {
1538                         if (f->flag & ARCHIVE_MATCH_NEWER)
1539                                 return (1);
1540                 } else {
1541                         nsec = archive_entry_ctime_nsec(entry);
1542                         if (f->ctime_nsec > nsec) {
1543                                 if (f->flag & ARCHIVE_MATCH_OLDER)
1544                                         return (1);
1545                         } else if (f->ctime_nsec < nsec) {
1546                                 if (f->flag & ARCHIVE_MATCH_NEWER)
1547                                         return (1);
1548                         } else if (f->flag & ARCHIVE_MATCH_EQUAL)
1549                                 return (1);
1550                 }
1551         }
1552         if (f->flag & ARCHIVE_MATCH_MTIME) {
1553                 sec = archive_entry_mtime(entry);
1554                 if (f->mtime_sec > sec) {
1555                         if (f->flag & ARCHIVE_MATCH_OLDER)
1556                                 return (1);
1557                 } else if (f->mtime_sec < sec) {
1558                         if (f->flag & ARCHIVE_MATCH_NEWER)
1559                                 return (1);
1560                 } else {
1561                         nsec = archive_entry_mtime_nsec(entry);
1562                         if (f->mtime_nsec > nsec) {
1563                                 if (f->flag & ARCHIVE_MATCH_OLDER)
1564                                         return (1);
1565                         } else if (f->mtime_nsec < nsec) {
1566                                 if (f->flag & ARCHIVE_MATCH_NEWER)
1567                                         return (1);
1568                         } else if (f->flag & ARCHIVE_MATCH_EQUAL)
1569                                 return (1);
1570                 }
1571         }
1572         return (0);
1573 }
1574
1575 /*
1576  * Utility functions to manage inclusion owners
1577  */
1578
1579 int
1580 archive_match_include_uid(struct archive *_a, int64_t uid)
1581 {
1582         struct archive_match *a;
1583
1584         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
1585             ARCHIVE_STATE_NEW, "archive_match_include_uid");
1586         a = (struct archive_match *)_a;
1587         return (add_owner_id(a, &(a->inclusion_uids), uid));
1588 }
1589
1590 int
1591 archive_match_include_gid(struct archive *_a, int64_t gid)
1592 {
1593         struct archive_match *a;
1594
1595         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
1596             ARCHIVE_STATE_NEW, "archive_match_include_gid");
1597         a = (struct archive_match *)_a;
1598         return (add_owner_id(a, &(a->inclusion_gids), gid));
1599 }
1600
1601 int
1602 archive_match_include_uname(struct archive *_a, const char *uname)
1603 {
1604         struct archive_match *a;
1605
1606         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
1607             ARCHIVE_STATE_NEW, "archive_match_include_uname");
1608         a = (struct archive_match *)_a;
1609         return (add_owner_name(a, &(a->inclusion_unames), 1, uname));
1610 }
1611
1612 int
1613 archive_match_include_uname_w(struct archive *_a, const wchar_t *uname)
1614 {
1615         struct archive_match *a;
1616
1617         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
1618             ARCHIVE_STATE_NEW, "archive_match_include_uname_w");
1619         a = (struct archive_match *)_a;
1620         return (add_owner_name(a, &(a->inclusion_unames), 0, uname));
1621 }
1622
1623 int
1624 archive_match_include_gname(struct archive *_a, const char *gname)
1625 {
1626         struct archive_match *a;
1627
1628         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
1629             ARCHIVE_STATE_NEW, "archive_match_include_gname");
1630         a = (struct archive_match *)_a;
1631         return (add_owner_name(a, &(a->inclusion_gnames), 1, gname));
1632 }
1633
1634 int
1635 archive_match_include_gname_w(struct archive *_a, const wchar_t *gname)
1636 {
1637         struct archive_match *a;
1638
1639         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
1640             ARCHIVE_STATE_NEW, "archive_match_include_gname_w");
1641         a = (struct archive_match *)_a;
1642         return (add_owner_name(a, &(a->inclusion_gnames), 0, gname));
1643 }
1644
1645 /*
1646  * Test function for owner(uid, gid, uname, gname).
1647  *
1648  * Returns 1 if archive entry is excluded.
1649  * Returns 0 if archive entry is not excluded.
1650  * Returns <0 if something error happened.
1651  */
1652 int
1653 archive_match_owner_excluded(struct archive *_a,
1654     struct archive_entry *entry)
1655 {
1656         struct archive_match *a;
1657
1658         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
1659             ARCHIVE_STATE_NEW, "archive_match_id_excluded_ae");
1660
1661         a = (struct archive_match *)_a;
1662         if (entry == NULL) {
1663                 archive_set_error(&(a->archive), EINVAL, "entry is NULL");
1664                 return (ARCHIVE_FAILED);
1665         }
1666
1667         /* If we don't have inclusion id set at all, the entry is always
1668          * not excluded. */
1669         if ((a->setflag & ID_IS_SET) == 0)
1670                 return (0);
1671         return (owner_excluded(a, entry));
1672 }
1673
1674 static int
1675 add_owner_id(struct archive_match *a, struct id_array *ids, int64_t id)
1676 {
1677         unsigned i;
1678
1679         if (ids->count + 1 >= ids->size) {
1680                 void *p;
1681
1682                 if (ids->size == 0)
1683                         ids->size = 8;
1684                 else
1685                         ids->size *= 2;
1686                 p = realloc(ids->ids, sizeof(*ids->ids) * ids->size);
1687                 if (p == NULL)
1688                         return (error_nomem(a));
1689                 ids->ids = (int64_t *)p;
1690         }
1691
1692         /* Find an insert point. */
1693         for (i = 0; i < ids->count; i++) {
1694                 if (ids->ids[i] >= id)
1695                         break;
1696         }
1697
1698         /* Add oowner id. */
1699         if (i == ids->count)
1700                 ids->ids[ids->count++] = id;
1701         else if (ids->ids[i] != id) {
1702                 memmove(&(ids->ids[i+1]), &(ids->ids[i]),
1703                     (ids->count - i) * sizeof(ids->ids[0]));
1704                 ids->ids[i] = id;
1705                 ids->count++;
1706         }
1707         a->setflag |= ID_IS_SET;
1708         return (ARCHIVE_OK);
1709 }
1710
1711 static int
1712 match_owner_id(struct id_array *ids, int64_t id)
1713 {
1714         unsigned b, m, t;
1715
1716         t = 0;
1717         b = (unsigned)ids->count;
1718         while (t < b) {
1719                 m = (t + b)>>1;
1720                 if (ids->ids[m] == id)
1721                         return (1);
1722                 if (ids->ids[m] < id)
1723                         t = m + 1;
1724                 else
1725                         b = m;
1726         }
1727         return (0);
1728 }
1729
1730 static int
1731 add_owner_name(struct archive_match *a, struct match_list *list,
1732     int mbs, const void *name)
1733 {
1734         struct match *match;
1735
1736         match = calloc(1, sizeof(*match));
1737         if (match == NULL)
1738                 return (error_nomem(a));
1739         if (mbs)
1740                 archive_mstring_copy_mbs(&(match->pattern), name);
1741         else
1742                 archive_mstring_copy_wcs(&(match->pattern), name);
1743         match_list_add(list, match);
1744         a->setflag |= ID_IS_SET;
1745         return (ARCHIVE_OK);
1746 }
1747
1748 #if !defined(_WIN32) || defined(__CYGWIN__)
1749 static int
1750 match_owner_name_mbs(struct archive_match *a, struct match_list *list,
1751     const char *name)
1752 {
1753         struct match *m;
1754         const char *p;
1755
1756         if (name == NULL || *name == '\0')
1757                 return (0);
1758         for (m = list->first; m; m = m->next) {
1759                 if (archive_mstring_get_mbs(&(a->archive), &(m->pattern), &p)
1760                     < 0 && errno == ENOMEM)
1761                         return (error_nomem(a));
1762                 if (p != NULL && strcmp(p, name) == 0) {
1763                         m->matches++;
1764                         return (1);
1765                 }
1766         }
1767         return (0);
1768 }
1769 #else
1770 static int
1771 match_owner_name_wcs(struct archive_match *a, struct match_list *list,
1772     const wchar_t *name)
1773 {
1774         struct match *m;
1775         const wchar_t *p;
1776
1777         if (name == NULL || *name == L'\0')
1778                 return (0);
1779         for (m = list->first; m; m = m->next) {
1780                 if (archive_mstring_get_wcs(&(a->archive), &(m->pattern), &p)
1781                     < 0 && errno == ENOMEM)
1782                         return (error_nomem(a));
1783                 if (p != NULL && wcscmp(p, name) == 0) {
1784                         m->matches++;
1785                         return (1);
1786                 }
1787         }
1788         return (0);
1789 }
1790 #endif
1791
1792 /*
1793  * Test if entry is excluded by uid, gid, uname or gname.
1794  */
1795 static int
1796 owner_excluded(struct archive_match *a, struct archive_entry *entry)
1797 {
1798         int r;
1799
1800         if (a->inclusion_uids.count) {
1801                 if (!match_owner_id(&(a->inclusion_uids),
1802                     archive_entry_uid(entry)))
1803                         return (1);
1804         }
1805
1806         if (a->inclusion_gids.count) {
1807                 if (!match_owner_id(&(a->inclusion_gids),
1808                     archive_entry_gid(entry)))
1809                         return (1);
1810         }
1811
1812         if (a->inclusion_unames.count) {
1813 #if defined(_WIN32) && !defined(__CYGWIN__)
1814                 r = match_owner_name_wcs(a, &(a->inclusion_unames),
1815                         archive_entry_uname_w(entry));
1816 #else
1817                 r = match_owner_name_mbs(a, &(a->inclusion_unames),
1818                         archive_entry_uname(entry));
1819 #endif
1820                 if (!r)
1821                         return (1);
1822                 else if (r < 0)
1823                         return (r);
1824         }
1825
1826         if (a->inclusion_gnames.count) {
1827 #if defined(_WIN32) && !defined(__CYGWIN__)
1828                 r = match_owner_name_wcs(a, &(a->inclusion_gnames),
1829                         archive_entry_gname_w(entry));
1830 #else
1831                 r = match_owner_name_mbs(a, &(a->inclusion_gnames),
1832                         archive_entry_gname(entry));
1833 #endif
1834                 if (!r)
1835                         return (1);
1836                 else if (r < 0)
1837                         return (r);
1838         }
1839         return (0);
1840 }
1841