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