contrib/libarchive-2.1/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.11 2007/03/11 10:36:42 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
 263 #if defined(HAVE_FNMATCH) && defined(HAVE_FNM_LEADING_DIR)
 264
 265 /* Use system fnmatch() if it suits our needs. */
 266 /* On Linux, _GNU_SOURCE must be defined to get FNM_LEADING_DIR. */
 267 #define _GNU_SOURCE
 268 #include <fnmatch.h>
 269 static int
 270 bsdtar_fnmatch(const char *pattern, const char *string)
 271 {
 272         return (fnmatch(pattern, string, FNM_LEADING_DIR));
 273 }
 274
 275 #else
 276 /*
 277  * The following was hacked from BSD C library
 278  * code:  src/lib/libc/gen/fnmatch.c,v 1.15 2002/02/01
 279  *
 280  * In particular, most of the flags were ripped out: this always
 281  * behaves like FNM_LEADING_DIR is set and other flags specified
 282  * by POSIX are unset.
 283  *
 284  * Normally, I would not conditionally compile something like this: If
 285  * I have to support it anyway, everyone may as well use it. ;-)
 286  * However, the full POSIX spec for fnmatch() includes a lot of
 287  * advanced character handling that I'm not ready to put in here, so
 288  * it's probably best if people use a local version when it's available.
 289  */
 290
 291 /*
 292  * Copyright (c) 1989, 1993, 1994
 293  *      The Regents of the University of California.  All rights reserved.
 294  *
 295  * This code is derived from software contributed to Berkeley by
 296  * Guido van Rossum.
 297  *
 298  * Redistribution and use in source and binary forms, with or without
 299  * modification, are permitted provided that the following conditions
 300  * are met:
 301  * 1. Redistributions of source code must retain the above copyright
 302  *    notice, this list of conditions and the following disclaimer.
 303  * 2. Redistributions in binary form must reproduce the above copyright
 304  *    notice, this list of conditions and the following disclaimer in the
 305  *    documentation and/or other materials provided with the distribution.
 306  * 4. Neither the name of the University nor the names of its contributors
 307  *    may be used to endorse or promote products derived from this software
 308  *    without specific prior written permission.
 309  *
 310  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 311  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 312  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 313  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 314  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 315  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 316  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 317  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 318  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 319  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 320  * SUCH DAMAGE.
 321  */
 322
 323 static int
 324 bsdtar_fnmatch(const char *pattern, const char *string)
 325 {
 326         const char *saved_pattern;
 327         int negate, matched;
 328         char c;
 329
 330         for (;;) {
 331                 switch (c = *pattern++) {
 332                 case '\0':
 333                         if (*string == '/' || *string == '\0')
 334                                 return (0);
 335                         return (1);
 336                 case '?':
 337                         if (*string == '\0')
 338                                 return (1);
 339                         ++string;
 340                         break;
 341                 case '*':
 342                         c = *pattern;
 343                         /* Collapse multiple stars. */
 344                         while (c == '*')
 345                                 c = *++pattern;
 346
 347                         /* Optimize for pattern with * at end. */
 348                         if (c == '\0')
 349                                 return (0);
 350
 351                         /* General case, use recursion. */
 352                         while (*string != '\0') {
 353                                 if (!bsdtar_fnmatch(pattern, string))
 354                                         return (0);
 355                                 ++string;
 356                         }
 357                         return (1);
 358                 case '[':
 359                         if (*string == '\0')
 360                                 return (1);
 361                         saved_pattern = pattern;
 362                         if (*pattern == '!' || *pattern == '^') {
 363                                 negate = 1;
 364                                 ++pattern;
 365                         } else
 366                                 negate = 0;
 367                         matched = 0;
 368                         c = *pattern++;
 369                         do {
 370                                 if (c == '\\')
 371                                         c = *pattern++;
 372                                 if (c == '\0') {
 373                                         pattern = saved_pattern;
 374                                         c = '[';
 375                                         goto norm;
 376                                 }
 377                                 if (*pattern == '-') {
 378                                         char c2 = *(pattern + 1);
 379                                         if (c2 == '\0') {
 380                                                 pattern = saved_pattern;
 381                                                 c = '[';
 382                                                 goto norm;
 383                                         }
 384                                         if (c2 == ']') {
 385                                                 /* [a-] is not a range. */
 386                                                 if (c == *string
 387                                                     || '-' == *string)
 388                                                         matched = 1;
 389                                                 pattern ++;
 390                                         } else {
 391                                                 if (c <= *string
 392                                                     && *string <= c2)
 393                                                         matched = 1;
 394                                                 pattern += 2;
 395                                         }
 396                                 } else if (c == *string)
 397                                         matched = 1;
 398                                 c = *pattern++;
 399                         } while (c != ']');
 400                         if (matched == negate)
 401                                 return (1);
 402                         ++string;
 403                         break;
 404                 case '\\':
 405                         if ((c = *pattern++) == '\0') {
 406                                 c = '\\';
 407                                 --pattern;
 408                         }
 409                         /* FALLTHROUGH */
 410                 default:
 411                 norm:
 412                         if (c != *string)
 413                                 return (1);
 414                         string++;
 415                         break;
 416                 }
 417         }
 418         /* NOTREACHED */
 419 }
 420
 421 #endif