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