contrib/libarchive-2/tar/matching.c

   1 /*-
   2  * Copyright (c) 2003-2007 Tim Kientzle
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR
  15  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  16  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  17  * IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT,
  18  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  19  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  20  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  21  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  23  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #include "bsdtar_platform.h"
  27 __FBSDID("$FreeBSD: src/usr.bin/tar/matching.c,v 1.13 2008/05/26 17:10:10 kientzle Exp $");
  28
  29 #ifdef HAVE_ERRNO_H
  30 #include <errno.h>
  31 #endif
  32 #ifdef HAVE_STDLIB_H
  33 #include <stdlib.h>
  34 #endif
  35 #ifdef HAVE_STRING_H
  36 #include <string.h>
  37 #endif
  38
  39 #include "bsdtar.h"
  40
  41 struct match {
  42         struct match     *next;
  43         int               matches;
  44         char              pattern[1];
  45 };
  46
  47 struct matching {
  48         struct match     *exclusions;
  49         int               exclusions_count;
  50         struct match     *inclusions;
  51         int               inclusions_count;
  52         int               inclusions_unmatched_count;
  53 };
  54
  55
  56 static void     add_pattern(struct bsdtar *, struct match **list,
  57                     const char *pattern);
  58 static int      bsdtar_fnmatch(const char *p, const char *s);
  59 static void     initialize_matching(struct bsdtar *);
  60 static int      match_exclusion(struct match *, const char *pathname);
  61 static int      match_inclusion(struct match *, const char *pathname);
  62
  63 /*
  64  * The matching logic here needs to be re-thought.  I started out to
  65  * try to mimic gtar's matching logic, but it's not entirely
  66  * consistent.  In particular 'tar -t' and 'tar -x' interpret patterns
  67  * on the command line as anchored, but --exclude doesn't.
  68  */
  69
  70 /*
  71  * Utility functions to manage exclusion/inclusion patterns
  72  */
  73
  74 int
  75 exclude(struct bsdtar *bsdtar, const char *pattern)
  76 {
  77         struct matching *matching;
  78
  79         if (bsdtar->matching == NULL)
  80                 initialize_matching(bsdtar);
  81         matching = bsdtar->matching;
  82         add_pattern(bsdtar, &(matching->exclusions), pattern);
  83         matching->exclusions_count++;
  84         return (0);
  85 }
  86
  87 int
  88 exclude_from_file(struct bsdtar *bsdtar, const char *pathname)
  89 {
  90         return (process_lines(bsdtar, pathname, &exclude));
  91 }
  92
  93 int
  94 include(struct bsdtar *bsdtar, const char *pattern)
  95 {
  96         struct matching *matching;
  97
  98         if (bsdtar->matching == NULL)
  99                 initialize_matching(bsdtar);
 100         matching = bsdtar->matching;
 101         add_pattern(bsdtar, &(matching->inclusions), pattern);
 102         matching->inclusions_count++;
 103         matching->inclusions_unmatched_count++;
 104         return (0);
 105 }
 106
 107 int
 108 include_from_file(struct bsdtar *bsdtar, const char *pathname)
 109 {
 110         return (process_lines(bsdtar, pathname, &include));
 111 }
 112
 113 static void
 114 add_pattern(struct bsdtar *bsdtar, struct match **list, const char *pattern)
 115 {
 116         struct match *match;
 117
 118         match = malloc(sizeof(*match) + strlen(pattern) + 1);
 119         if (match == NULL)
 120                 bsdtar_errc(bsdtar, 1, errno, "Out of memory");
 121         if (pattern[0] == '/')
 122                 pattern++;
 123         strcpy(match->pattern, pattern);
 124         /* Both "foo/" and "foo" should match "foo/bar". */
 125         if (match->pattern[strlen(match->pattern)-1] == '/')
 126                 match->pattern[strlen(match->pattern)-1] = '\0';
 127         match->next = *list;
 128         *list = match;
 129         match->matches = 0;
 130 }
 131
 132
 133 int
 134 excluded(struct bsdtar *bsdtar, const char *pathname)
 135 {
 136         struct matching *matching;
 137         struct match *match;
 138         struct match *matched;
 139
 140         matching = bsdtar->matching;
 141         if (matching == NULL)
 142                 return (0);
 143
 144         /* Exclusions take priority */
 145         for (match = matching->exclusions; match != NULL; match = match->next){
 146                 if (match_exclusion(match, pathname))
 147                         return (1);
 148         }
 149
 150         /* Then check for inclusions */
 151         matched = NULL;
 152         for (match = matching->inclusions; match != NULL; match = match->next){
 153                 if (match_inclusion(match, pathname)) {
 154                         /*
 155                          * If this pattern has never been matched,
 156                          * then we're done.
 157                          */
 158                         if (match->matches == 0) {
 159                                 match->matches++;
 160                                 matching->inclusions_unmatched_count--;
 161                                 return (0);
 162                         }
 163                         /*
 164                          * Otherwise, remember the match but keep checking
 165                          * in case we can tick off an unmatched pattern.
 166                          */
 167                         matched = match;
 168                 }
 169         }
 170         /*
 171          * We didn't find a pattern that had never been matched, but
 172          * we did find a match, so count it and exit.
 173          */
 174         if (matched != NULL) {
 175                 matched->matches++;
 176                 return (0);
 177         }
 178
 179         /* If there were inclusions, default is to exclude. */
 180         if (matching->inclusions != NULL)
 181             return (1);
 182
 183         /* No explicit inclusions, default is to match. */
 184         return (0);
 185 }
 186
 187 /*
 188  * This is a little odd, but it matches the default behavior of
 189  * gtar.  In particular, 'a*b' will match 'foo/a1111/222b/bar'
 190  *
 191  */
 192 int
 193 match_exclusion(struct match *match, const char *pathname)
 194 {
 195         const char *p;
 196
 197         if (*match->pattern == '*' || *match->pattern == '/')
 198                 return (bsdtar_fnmatch(match->pattern, pathname) == 0);
 199
 200         for (p = pathname; p != NULL; p = strchr(p, '/')) {
 201                 if (*p == '/')
 202                         p++;
 203                 if (bsdtar_fnmatch(match->pattern, p) == 0)
 204                         return (1);
 205         }
 206         return (0);
 207 }
 208
 209 /*
 210  * Again, mimic gtar:  inclusions are always anchored (have to match
 211  * the beginning of the path) even though exclusions are not anchored.
 212  */
 213 int
 214 match_inclusion(struct match *match, const char *pathname)
 215 {
 216         return (bsdtar_fnmatch(match->pattern, pathname) == 0);
 217 }
 218
 219 void
 220 cleanup_exclusions(struct bsdtar *bsdtar)
 221 {
 222         struct match *p, *q;
 223
 224         if (bsdtar->matching) {
 225                 p = bsdtar->matching->inclusions;
 226                 while (p != NULL) {
 227                         q = p;
 228                         p = p->next;
 229                         free(q);
 230                 }
 231                 p = bsdtar->matching->exclusions;
 232                 while (p != NULL) {
 233                         q = p;
 234                         p = p->next;
 235                         free(q);
 236                 }
 237                 free(bsdtar->matching);
 238         }
 239 }
 240
 241 static void
 242 initialize_matching(struct bsdtar *bsdtar)
 243 {
 244         bsdtar->matching = malloc(sizeof(*bsdtar->matching));
 245         if (bsdtar->matching == NULL)
 246                 bsdtar_errc(bsdtar, 1, errno, "No memory");
 247         memset(bsdtar->matching, 0, sizeof(*bsdtar->matching));
 248 }
 249
 250 int
 251 unmatched_inclusions(struct bsdtar *bsdtar)
 252 {
 253         struct matching *matching;
 254
 255         matching = bsdtar->matching;
 256         if (matching == NULL)
 257                 return (0);
 258         return (matching->inclusions_unmatched_count);
 259 }
 260
 261
 262 int
 263 unmatched_inclusions_warn(struct bsdtar *bsdtar, const char *msg)
 264 {
 265         struct matching *matching;
 266         struct match *p;
 267
 268         matching = bsdtar->matching;
 269         if (matching == NULL)
 270                 return (0);
 271
 272         p = matching->inclusions;
 273         while (p != NULL) {
 274                 if (p->matches == 0) {
 275                         bsdtar->return_value = 1;
 276                         bsdtar_warnc(bsdtar, 0, "%s: %s",
 277                             p->pattern, msg);
 278                 }
 279                 p = p->next;
 280         }
 281         return (matching->inclusions_unmatched_count);
 282 }
 283
 284
 285
 286 #if defined(HAVE_FNMATCH) && defined(HAVE_FNM_LEADING_DIR)
 287
 288 /* Use system fnmatch() if it suits our needs. */
 289 /* On Linux, _GNU_SOURCE must be defined to get FNM_LEADING_DIR. */
 290 #define _GNU_SOURCE
 291 #include <fnmatch.h>
 292 static int
 293 bsdtar_fnmatch(const char *pattern, const char *string)
 294 {
 295         return (fnmatch(pattern, string, FNM_LEADING_DIR));
 296 }
 297
 298 #else
 299 /*
 300  * The following was hacked from BSD C library
 301  * code:  src/lib/libc/gen/fnmatch.c,v 1.15 2002/02/01
 302  *
 303  * In particular, most of the flags were ripped out: this always
 304  * behaves like FNM_LEADING_DIR is set and other flags specified
 305  * by POSIX are unset.
 306  *
 307  * Normally, I would not conditionally compile something like this: If
 308  * I have to support it anyway, everyone may as well use it. ;-)
 309  * However, the full POSIX spec for fnmatch() includes a lot of
 310  * advanced character handling that I'm not ready to put in here, so
 311  * it's probably best if people use a local version when it's available.
 312  */
 313
 314 /*
 315  * Copyright (c) 1989, 1993, 1994
 316  *      The Regents of the University of California.  All rights reserved.
 317  *
 318  * This code is derived from software contributed to Berkeley by
 319  * Guido van Rossum.
 320  *
 321  * Redistribution and use in source and binary forms, with or without
 322  * modification, are permitted provided that the following conditions
 323  * are met:
 324  * 1. Redistributions of source code must retain the above copyright
 325  *    notice, this list of conditions and the following disclaimer.
 326  * 2. Redistributions in binary form must reproduce the above copyright
 327  *    notice, this list of conditions and the following disclaimer in the
 328  *    documentation and/or other materials provided with the distribution.
 329  * 4. Neither the name of the University nor the names of its contributors
 330  *    may be used to endorse or promote products derived from this software
 331  *    without specific prior written permission.
 332  *
 333  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 334  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 335  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 336  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 337  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 338  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 339  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 340  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 341  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 342  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 343  * SUCH DAMAGE.
 344  */
 345
 346 static int
 347 bsdtar_fnmatch(const char *pattern, const char *string)
 348 {
 349         const char *saved_pattern;
 350         int negate, matched;
 351         char c;
 352
 353         for (;;) {
 354                 switch (c = *pattern++) {
 355                 case '\0':
 356                         if (*string == '/' || *string == '\0')
 357                                 return (0);
 358                         return (1);
 359                 case '?':
 360                         if (*string == '\0')
 361                                 return (1);
 362                         ++string;
 363                         break;
 364                 case '*':
 365                         c = *pattern;
 366                         /* Collapse multiple stars. */
 367                         while (c == '*')
 368                                 c = *++pattern;
 369
 370                         /* Optimize for pattern with * at end. */
 371                         if (c == '\0')
 372                                 return (0);
 373
 374                         /* General case, use recursion. */
 375                         while (*string != '\0') {
 376                                 if (!bsdtar_fnmatch(pattern, string))
 377                                         return (0);
 378                                 ++string;
 379                         }
 380                         return (1);
 381                 case '[':
 382                         if (*string == '\0')
 383                                 return (1);
 384                         saved_pattern = pattern;
 385                         if (*pattern == '!' || *pattern == '^') {
 386                                 negate = 1;
 387                                 ++pattern;
 388                         } else
 389                                 negate = 0;
 390                         matched = 0;
 391                         c = *pattern++;
 392                         do {
 393                                 if (c == '\\')
 394                                         c = *pattern++;
 395                                 if (c == '\0') {
 396                                         pattern = saved_pattern;
 397                                         c = '[';
 398                                         goto norm;
 399                                 }
 400                                 if (*pattern == '-') {
 401                                         char c2 = *(pattern + 1);
 402                                         if (c2 == '\0') {
 403                                                 pattern = saved_pattern;
 404                                                 c = '[';
 405                                                 goto norm;
 406                                         }
 407                                         if (c2 == ']') {
 408                                                 /* [a-] is not a range. */
 409                                                 if (c == *string
 410                                                     || '-' == *string)
 411                                                         matched = 1;
 412                                                 pattern ++;
 413                                         } else {
 414                                                 if (c <= *string
 415                                                     && *string <= c2)
 416                                                         matched = 1;
 417                                                 pattern += 2;
 418                                         }
 419                                 } else if (c == *string)
 420                                         matched = 1;
 421                                 c = *pattern++;
 422                         } while (c != ']');
 423                         if (matched == negate)
 424                                 return (1);
 425                         ++string;
 426                         break;
 427                 case '\\':
 428                         if ((c = *pattern++) == '\0') {
 429                                 c = '\\';
 430                                 --pattern;
 431                         }
 432                         /* FALLTHROUGH */
 433                 default:
 434                 norm:
 435                         if (c != *string)
 436                                 return (1);
 437                         string++;
 438                         break;
 439                 }
 440         }
 441         /* NOTREACHED */
 442 }
 443
 444 #endif