usr.bin/tar/matching.c

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