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         pathname = archive_entry_pathname(entry);
1380         if (pathname == NULL) {
1381                 free(f);
1382                 archive_set_error(&(a->archive), EINVAL, "pathname is NULL");
1383                 return (ARCHIVE_FAILED);
1384         }
1385         archive_mstring_copy_mbs(&(f->pathname), pathname);
1386         a->exclusion_tree.rbt_ops = &rb_ops_mbs;
1387 #endif
1388         f->flag = flag;
1389         f->mtime_sec = archive_entry_mtime(entry);
1390         f->mtime_nsec = archive_entry_mtime_nsec(entry);
1391         f->ctime_sec = archive_entry_ctime(entry);
1392         f->ctime_nsec = archive_entry_ctime_nsec(entry);
1393         r = __archive_rb_tree_insert_node(&(a->exclusion_tree), &(f->node));
1394         if (!r) {
1395                 struct match_file *f2;
1396
1397                 /* Get the duplicated file. */
1398                 f2 = (struct match_file *)__archive_rb_tree_find_node(
1399                         &(a->exclusion_tree), pathname);
1400
1401                 /*
1402                  * We always overwrite comparison condision.
1403                  * If you do not want to overwrite it, you should not
1404                  * call archive_match_exclude_entry(). We cannot know
1405                  * what behavior you really expect since overwriting
1406                  * condition might be different with the flag.
1407                  */
1408                 if (f2 != NULL) {
1409                         f2->flag = f->flag;
1410                         f2->mtime_sec = f->mtime_sec;
1411                         f2->mtime_nsec = f->mtime_nsec;
1412                         f2->ctime_sec = f->ctime_sec;
1413                         f2->ctime_nsec = f->ctime_nsec;
1414                 }
1415                 /* Release the duplicated file. */
1416                 archive_mstring_clean(&(f->pathname));
1417                 free(f);
1418                 return (ARCHIVE_OK);
1419         }
1420         entry_list_add(&(a->exclusion_entry_list), f);
1421         a->setflag |= TIME_IS_SET;
1422         return (ARCHIVE_OK);
1423 }
1424
1425 /*
1426  * Test if entry is excluded by its timestamp.
1427  */
1428 static int
1429 time_excluded(struct archive_match *a, struct archive_entry *entry)
1430 {
1431         struct match_file *f;
1432         const void *pathname;
1433         time_t sec;
1434         long nsec;
1435
1436         /*
1437          * If this file/dir is excluded by a time comparison, skip it.
1438          */
1439         if (a->newer_ctime_filter) {
1440                 /* If ctime is not set, use mtime instead. */
1441                 if (archive_entry_ctime_is_set(entry))
1442                         sec = archive_entry_ctime(entry);
1443                 else
1444                         sec = archive_entry_mtime(entry);
1445                 if (sec < a->newer_ctime_sec)
1446                         return (1); /* Too old, skip it. */
1447                 if (sec == a->newer_ctime_sec) {
1448                         if (archive_entry_ctime_is_set(entry))
1449                                 nsec = archive_entry_ctime_nsec(entry);
1450                         else
1451                                 nsec = archive_entry_mtime_nsec(entry);
1452                         if (nsec < a->newer_ctime_nsec)
1453                                 return (1); /* Too old, skip it. */
1454                         if (nsec == a->newer_ctime_nsec &&
1455                             (a->newer_ctime_filter & ARCHIVE_MATCH_EQUAL)
1456                               == 0)
1457                                 return (1); /* Equal, skip it. */
1458                 }
1459         }
1460         if (a->older_ctime_filter) {
1461                 /* If ctime is not set, use mtime instead. */
1462                 if (archive_entry_ctime_is_set(entry))
1463                         sec = archive_entry_ctime(entry);
1464                 else
1465                         sec = archive_entry_mtime(entry);
1466                 if (sec > a->older_ctime_sec)
1467                         return (1); /* Too new, skip it. */
1468                 if (sec == a->older_ctime_sec) {
1469                         if (archive_entry_ctime_is_set(entry))
1470                                 nsec = archive_entry_ctime_nsec(entry);
1471                         else
1472                                 nsec = archive_entry_mtime_nsec(entry);
1473                         if (nsec > a->older_ctime_nsec)
1474                                 return (1); /* Too new, skip it. */
1475                         if (nsec == a->older_ctime_nsec &&
1476                             (a->older_ctime_filter & ARCHIVE_MATCH_EQUAL)
1477                               == 0)
1478                                 return (1); /* Eeual, skip it. */
1479                 }
1480         }
1481         if (a->newer_mtime_filter) {
1482                 sec = archive_entry_mtime(entry);
1483                 if (sec < a->newer_mtime_sec)
1484                         return (1); /* Too old, skip it. */
1485                 if (sec == a->newer_mtime_sec) {
1486                         nsec = archive_entry_mtime_nsec(entry);
1487                         if (nsec < a->newer_mtime_nsec)
1488                                 return (1); /* Too old, skip it. */
1489                         if (nsec == a->newer_mtime_nsec &&
1490                             (a->newer_mtime_filter & ARCHIVE_MATCH_EQUAL)
1491                                == 0)
1492                                 return (1); /* Equal, skip it. */
1493                 }
1494         }
1495         if (a->older_mtime_filter) {
1496                 sec = archive_entry_mtime(entry);
1497                 if (sec > a->older_mtime_sec)
1498                         return (1); /* Too new, skip it. */
1499                 nsec = archive_entry_mtime_nsec(entry);
1500                 if (sec == a->older_mtime_sec) {
1501                         if (nsec > a->older_mtime_nsec)
1502                                 return (1); /* Too new, skip it. */
1503                         if (nsec == a->older_mtime_nsec &&
1504                             (a->older_mtime_filter & ARCHIVE_MATCH_EQUAL)
1505                                == 0)
1506                                 return (1); /* Equal, skip it. */
1507                 }
1508         }
1509
1510         /* If there is no excluson list, include the file. */
1511         if (a->exclusion_entry_list.count == 0)
1512                 return (0);
1513
1514 #if defined(_WIN32) && !defined(__CYGWIN__)
1515         pathname = archive_entry_pathname_w(entry);
1516         a->exclusion_tree.rbt_ops = &rb_ops_wcs;
1517 #else
1518         pathname = archive_entry_pathname(entry);
1519         a->exclusion_tree.rbt_ops = &rb_ops_mbs;
1520 #endif
1521         if (pathname == NULL)
1522                 return (0);
1523
1524         f = (struct match_file *)__archive_rb_tree_find_node(
1525                 &(a->exclusion_tree), pathname);
1526         /* If the file wasn't rejected, include it. */
1527         if (f == NULL)
1528                 return (0);
1529
1530         if (f->flag & ARCHIVE_MATCH_CTIME) {
1531                 sec = archive_entry_ctime(entry);
1532                 if (f->ctime_sec > sec) {
1533                         if (f->flag & ARCHIVE_MATCH_OLDER)
1534                                 return (1);
1535                 } else if (f->ctime_sec < sec) {
1536                         if (f->flag & ARCHIVE_MATCH_NEWER)
1537                                 return (1);
1538                 } else {
1539                         nsec = archive_entry_ctime_nsec(entry);
1540                         if (f->ctime_nsec > nsec) {
1541                                 if (f->flag & ARCHIVE_MATCH_OLDER)
1542                                         return (1);
1543                         } else if (f->ctime_nsec < nsec) {
1544                                 if (f->flag & ARCHIVE_MATCH_NEWER)
1545                                         return (1);
1546                         } else if (f->flag & ARCHIVE_MATCH_EQUAL)
1547                                 return (1);
1548                 }
1549         }
1550         if (f->flag & ARCHIVE_MATCH_MTIME) {
1551                 sec = archive_entry_mtime(entry);
1552                 if (f->mtime_sec > sec) {
1553                         if (f->flag & ARCHIVE_MATCH_OLDER)
1554                                 return (1);
1555                 } else if (f->mtime_sec < sec) {
1556                         if (f->flag & ARCHIVE_MATCH_NEWER)
1557                                 return (1);
1558                 } else {
1559                         nsec = archive_entry_mtime_nsec(entry);
1560                         if (f->mtime_nsec > nsec) {
1561                                 if (f->flag & ARCHIVE_MATCH_OLDER)
1562                                         return (1);
1563                         } else if (f->mtime_nsec < nsec) {
1564                                 if (f->flag & ARCHIVE_MATCH_NEWER)
1565                                         return (1);
1566                         } else if (f->flag & ARCHIVE_MATCH_EQUAL)
1567                                 return (1);
1568                 }
1569         }
1570         return (0);
1571 }
1572
1573 /*
1574  * Utility functions to manage inclusion owners
1575  */
1576
1577 int
1578 archive_match_include_uid(struct archive *_a, int64_t uid)
1579 {
1580         struct archive_match *a;
1581
1582         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
1583             ARCHIVE_STATE_NEW, "archive_match_include_uid");
1584         a = (struct archive_match *)_a;
1585         return (add_owner_id(a, &(a->inclusion_uids), uid));
1586 }
1587
1588 int
1589 archive_match_include_gid(struct archive *_a, int64_t gid)
1590 {
1591         struct archive_match *a;
1592
1593         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
1594             ARCHIVE_STATE_NEW, "archive_match_include_gid");
1595         a = (struct archive_match *)_a;
1596         return (add_owner_id(a, &(a->inclusion_gids), gid));
1597 }
1598
1599 int
1600 archive_match_include_uname(struct archive *_a, const char *uname)
1601 {
1602         struct archive_match *a;
1603
1604         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
1605             ARCHIVE_STATE_NEW, "archive_match_include_uname");
1606         a = (struct archive_match *)_a;
1607         return (add_owner_name(a, &(a->inclusion_unames), 1, uname));
1608 }
1609
1610 int
1611 archive_match_include_uname_w(struct archive *_a, const wchar_t *uname)
1612 {
1613         struct archive_match *a;
1614
1615         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
1616             ARCHIVE_STATE_NEW, "archive_match_include_uname_w");
1617         a = (struct archive_match *)_a;
1618         return (add_owner_name(a, &(a->inclusion_unames), 0, uname));
1619 }
1620
1621 int
1622 archive_match_include_gname(struct archive *_a, const char *gname)
1623 {
1624         struct archive_match *a;
1625
1626         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
1627             ARCHIVE_STATE_NEW, "archive_match_include_gname");
1628         a = (struct archive_match *)_a;
1629         return (add_owner_name(a, &(a->inclusion_gnames), 1, gname));
1630 }
1631
1632 int
1633 archive_match_include_gname_w(struct archive *_a, const wchar_t *gname)
1634 {
1635         struct archive_match *a;
1636
1637         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
1638             ARCHIVE_STATE_NEW, "archive_match_include_gname_w");
1639         a = (struct archive_match *)_a;
1640         return (add_owner_name(a, &(a->inclusion_gnames), 0, gname));
1641 }
1642
1643 /*
1644  * Test function for owner(uid, gid, uname, gname).
1645  *
1646  * Returns 1 if archive entry is excluded.
1647  * Returns 0 if archive entry is not excluded.
1648  * Returns <0 if something error happened.
1649  */
1650 int
1651 archive_match_owner_excluded(struct archive *_a,
1652     struct archive_entry *entry)
1653 {
1654         struct archive_match *a;
1655
1656         archive_check_magic(_a, ARCHIVE_MATCH_MAGIC,
1657             ARCHIVE_STATE_NEW, "archive_match_id_excluded_ae");
1658
1659         a = (struct archive_match *)_a;
1660         if (entry == NULL) {
1661                 archive_set_error(&(a->archive), EINVAL, "entry is NULL");
1662                 return (ARCHIVE_FAILED);
1663         }
1664
1665         /* If we don't have inclusion id set at all, the entry is always
1666          * not excluded. */
1667         if ((a->setflag & ID_IS_SET) == 0)
1668                 return (0);
1669         return (owner_excluded(a, entry));
1670 }
1671
1672 static int
1673 add_owner_id(struct archive_match *a, struct id_array *ids, int64_t id)
1674 {
1675         unsigned i;
1676
1677         if (ids->count + 1 >= ids->size) {
1678                 if (ids->size == 0)
1679                         ids->size = 8;
1680                 else
1681                         ids->size *= 2;
1682                 ids->ids = realloc(ids->ids, sizeof(*ids->ids) * ids->size);
1683                 if (ids->ids == NULL)
1684                         return (error_nomem(a));
1685         }
1686
1687         /* Find an insert point. */
1688         for (i = 0; i < ids->count; i++) {
1689                 if (ids->ids[i] >= id)
1690                         break;
1691         }
1692
1693         /* Add oowner id. */
1694         if (i == ids->count)
1695                 ids->ids[ids->count++] = id;
1696         else if (ids->ids[i] != id) {
1697                 memmove(&(ids->ids[i+1]), &(ids->ids[i]),
1698                     (ids->count - i) * sizeof(ids->ids[0]));
1699                 ids->ids[i] = id;
1700                 ids->count++;
1701         }
1702         a->setflag |= ID_IS_SET;
1703         return (ARCHIVE_OK);
1704 }
1705
1706 static int
1707 match_owner_id(struct id_array *ids, int64_t id)
1708 {
1709         unsigned b, m, t;
1710
1711         t = 0;
1712         b = ids->count;
1713         while (t < b) {
1714                 m = (t + b)>>1;
1715                 if (ids->ids[m] == id)
1716                         return (1);
1717                 if (ids->ids[m] < id)
1718                         t = m + 1;
1719                 else
1720                         b = m;
1721         }
1722         return (0);
1723 }
1724
1725 static int
1726 add_owner_name(struct archive_match *a, struct match_list *list,
1727     int mbs, const void *name)
1728 {
1729         struct match *match;
1730
1731         match = calloc(1, sizeof(*match));
1732         if (match == NULL)
1733                 return (error_nomem(a));
1734         if (mbs)
1735                 archive_mstring_copy_mbs(&(match->pattern), name);
1736         else
1737                 archive_mstring_copy_wcs(&(match->pattern), name);
1738         match_list_add(list, match);
1739         a->setflag |= ID_IS_SET;
1740         return (ARCHIVE_OK);
1741 }
1742
1743 #if !defined(_WIN32) || defined(__CYGWIN__)
1744 static int
1745 match_owner_name_mbs(struct archive_match *a, struct match_list *list,
1746     const char *name)
1747 {
1748         struct match *m;
1749         const char *p;
1750
1751         if (name == NULL || *name == '\0')
1752                 return (0);
1753         for (m = list->first; m; m = m->next) {
1754                 if (archive_mstring_get_mbs(&(a->archive), &(m->pattern), &p)
1755                     < 0 && errno == ENOMEM)
1756                         return (error_nomem(a));
1757                 if (p != NULL && strcmp(p, name) == 0) {
1758                         m->matches++;
1759                         return (1);
1760                 }
1761         }
1762         return (0);
1763 }
1764 #else
1765 static int
1766 match_owner_name_wcs(struct archive_match *a, struct match_list *list,
1767     const wchar_t *name)
1768 {
1769         struct match *m;
1770         const wchar_t *p;
1771
1772         if (name == NULL || *name == L'\0')
1773                 return (0);
1774         for (m = list->first; m; m = m->next) {
1775                 if (archive_mstring_get_wcs(&(a->archive), &(m->pattern), &p)
1776                     < 0 && errno == ENOMEM)
1777                         return (error_nomem(a));
1778                 if (p != NULL && wcscmp(p, name) == 0) {
1779                         m->matches++;
1780                         return (1);
1781                 }
1782         }
1783         return (0);
1784 }
1785 #endif
1786
1787 /*
1788  * Test if entry is excluded by uid, gid, uname or gname.
1789  */
1790 static int
1791 owner_excluded(struct archive_match *a, struct archive_entry *entry)
1792 {
1793         int r;
1794
1795         if (a->inclusion_uids.count) {
1796                 if (!match_owner_id(&(a->inclusion_uids),
1797                     archive_entry_uid(entry)))
1798                         return (1);
1799         }
1800
1801         if (a->inclusion_gids.count) {
1802                 if (!match_owner_id(&(a->inclusion_gids),
1803                     archive_entry_gid(entry)))
1804                         return (1);
1805         }
1806
1807         if (a->inclusion_unames.count) {
1808 #if defined(_WIN32) && !defined(__CYGWIN__)
1809                 r = match_owner_name_wcs(a, &(a->inclusion_unames),
1810                         archive_entry_uname_w(entry));
1811 #else
1812                 r = match_owner_name_mbs(a, &(a->inclusion_unames),
1813                         archive_entry_uname(entry));
1814 #endif
1815                 if (!r)
1816                         return (1);
1817                 else if (r < 0)
1818                         return (r);
1819         }
1820
1821         if (a->inclusion_gnames.count) {
1822 #if defined(_WIN32) && !defined(__CYGWIN__)
1823                 r = match_owner_name_wcs(a, &(a->inclusion_gnames),
1824                         archive_entry_gname_w(entry));
1825 #else
1826                 r = match_owner_name_mbs(a, &(a->inclusion_gnames),
1827                         archive_entry_gname(entry));
1828 #endif
1829                 if (!r)
1830                         return (1);
1831                 else if (r < 0)
1832                         return (r);
1833         }
1834         return (0);
1835 }
1836