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 #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 #include "err.h"
  41
  42 struct match {
  43         struct match     *next;
  44         int               matches;
  45         char              pattern[1];
  46 };
  47
  48 struct matching {
  49         struct match     *exclusions;
  50         int               exclusions_count;
  51         struct match     *inclusions;
  52         int               inclusions_count;
  53         int               inclusions_unmatched_count;
  54 };
  55
  56
  57 static void     add_pattern(struct match **list,
  58                     const char *pattern);
  59 static int      bsdtar_fnmatch(const char *p, const char *s);
  60 static void     initialize_matching(struct bsdtar *);
  61 static int      match_exclusion(struct match *, const char *pathname);
  62 static int      match_inclusion(struct match *, const char *pathname);
  63 static int      pathmatch(const char *p, const char *s);
  64
  65 /*
  66  * The matching logic here needs to be re-thought.  I started out to
  67  * try to mimic gtar's matching logic, but it's not entirely
  68  * consistent.  In particular 'tar -t' and 'tar -x' interpret patterns
  69  * on the command line as anchored, but --exclude doesn't.
  70  */
  71
  72 /*
  73  * Utility functions to manage exclusion/inclusion patterns
  74  */
  75
  76 int
  77 exclude(struct bsdtar *bsdtar, const char *pattern)
  78 {
  79         struct matching *matching;
  80
  81         if (bsdtar->matching == NULL)
  82                 initialize_matching(bsdtar);
  83         matching = bsdtar->matching;
  84         add_pattern(&(matching->exclusions), pattern);
  85         matching->exclusions_count++;
  86         return (0);
  87 }
  88
  89 int
  90 exclude_from_file(struct bsdtar *bsdtar, const char *pathname)
  91 {
  92         return (process_lines(bsdtar, pathname, &exclude));
  93 }
  94
  95 int
  96 include(struct bsdtar *bsdtar, const char *pattern)
  97 {
  98         struct matching *matching;
  99
 100         if (bsdtar->matching == NULL)
 101                 initialize_matching(bsdtar);
 102         matching = bsdtar->matching;
 103         add_pattern(&(matching->inclusions), pattern);
 104         matching->inclusions_count++;
 105         matching->inclusions_unmatched_count++;
 106         return (0);
 107 }
 108
 109 int
 110 include_from_file(struct bsdtar *bsdtar, const char *pathname)
 111 {
 112         return (process_lines(bsdtar, pathname, &include));
 113 }
 114
 115 static void
 116 add_pattern(struct match **list, const char *pattern)
 117 {
 118         struct match *match;
 119
 120         match = malloc(sizeof(*match) + strlen(pattern) + 1);
 121         if (match == NULL)
 122                 bsdtar_errc(1, errno, "Out of memory");
 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 static int
 193 match_exclusion(struct match *match, const char *pathname)
 194 {
 195         const char *p;
 196
 197         if (*match->pattern == '*' || *match->pattern == '/')
 198                 return (pathmatch(match->pattern, pathname) == 0);
 199
 200         for (p = pathname; p != NULL; p = strchr(p, '/')) {
 201                 if (*p == '/')
 202                         p++;
 203                 if (pathmatch(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 (pathmatch(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(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(0, "%s: %s",
 277                             p->pattern, msg);
 278                 }
 279                 p = p->next;
 280         }
 281         return (matching->inclusions_unmatched_count);
 282 }
 283
 284 /*
 285  * TODO: Extend this so that the following matches work:
 286  *     "foo//bar" == "foo/bar"
 287  *     "foo/./bar" == "foo/bar"
 288  *     "./foo" == "foo"
 289  *
 290  * The POSIX fnmatch() function doesn't handle any of these, but
 291  * all are common situations that arise when paths are generated within
 292  * large scripts.  E.g., the following is quite common:
 293  *      MYPATH=foo/  TARGET=$MYPATH/bar
 294  * It may be worthwhile to edit such paths at write time as well,
 295  * especially when such editing may avoid the need for long pathname
 296  * extensions.
 297  */
 298 static int
 299 pathmatch(const char *pattern, const char *string)
 300 {
 301         /*
 302          * Strip leading "./" or ".//" so that, e.g.,
 303          * "foo" matches "./foo".  In particular, this
 304          * opens up an optimization for the writer to
 305          * elide leading "./".
 306          */
 307         if (pattern[0] == '.' && pattern[1] == '/') {
 308                 pattern += 2;
 309                 while (pattern[0] == '/')
 310                         ++pattern;
 311         }
 312         if (string[0] == '.' && string[1] == '/') {
 313                 string += 2;
 314                 while (string[0] == '/')
 315                         ++string;
 316         }
 317         return (bsdtar_fnmatch(pattern, string));
 318 }
 319
 320
 321 #if defined(HAVE_FNMATCH) && defined(HAVE_FNM_LEADING_DIR)
 322
 323 /* Use system fnmatch() if it suits our needs. */
 324 /* On Linux, _GNU_SOURCE must be defined to get FNM_LEADING_DIR. */
 325 #define _GNU_SOURCE
 326 #include <fnmatch.h>
 327 static int
 328 bsdtar_fnmatch(const char *pattern, const char *string)
 329 {
 330         return (fnmatch(pattern, string, FNM_LEADING_DIR));
 331 }
 332
 333 #else
 334 /*
 335  * The following was hacked from BSD C library
 336  * code:  src/lib/libc/gen/fnmatch.c,v 1.15 2002/02/01
 337  *
 338  * In particular, most of the flags were ripped out: this always
 339  * behaves like FNM_LEADING_DIR is set and other flags specified
 340  * by POSIX are unset.
 341  *
 342  * Normally, I would not conditionally compile something like this: If
 343  * I have to support it anyway, everyone may as well use it. ;-)
 344  * However, the full POSIX spec for fnmatch() includes a lot of
 345  * advanced character handling that I'm not ready to put in here, so
 346  * it's probably best if people use a local version when it's available.
 347  */
 348
 349 /*
 350  * Copyright (c) 1989, 1993, 1994
 351  *      The Regents of the University of California.  All rights reserved.
 352  *
 353  * This code is derived from software contributed to Berkeley by
 354  * Guido van Rossum.
 355  *
 356  * Redistribution and use in source and binary forms, with or without
 357  * modification, are permitted provided that the following conditions
 358  * are met:
 359  * 1. Redistributions of source code must retain the above copyright
 360  *    notice, this list of conditions and the following disclaimer.
 361  * 2. Redistributions in binary form must reproduce the above copyright
 362  *    notice, this list of conditions and the following disclaimer in the
 363  *    documentation and/or other materials provided with the distribution.
 364  * 4. Neither the name of the University nor the names of its contributors
 365  *    may be used to endorse or promote products derived from this software
 366  *    without specific prior written permission.
 367  *
 368  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 369  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 370  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 371  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 372  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 373  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 374  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 375  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 376  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 377  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 378  * SUCH DAMAGE.
 379  */
 380
 381 static int
 382 bsdtar_fnmatch(const char *pattern, const char *string)
 383 {
 384         const char *saved_pattern;
 385         int negate, matched;
 386         char c;
 387
 388         for (;;) {
 389                 switch (c = *pattern++) {
 390                 case '\0':
 391                         if (*string == '/' || *string == '\0')
 392                                 return (0);
 393                         return (1);
 394                 case '?':
 395                         if (*string == '\0')
 396                                 return (1);
 397                         ++string;
 398                         break;
 399                 case '*':
 400                         c = *pattern;
 401                         /* Collapse multiple stars. */
 402                         while (c == '*')
 403                                 c = *++pattern;
 404
 405                         /* Optimize for pattern with * at end. */
 406                         if (c == '\0')
 407                                 return (0);
 408
 409                         /* General case, use recursion. */
 410                         while (*string != '\0') {
 411                                 if (!bsdtar_fnmatch(pattern, string))
 412                                         return (0);
 413                                 ++string;
 414                         }
 415                         return (1);
 416                 case '[':
 417                         if (*string == '\0')
 418                                 return (1);
 419                         saved_pattern = pattern;
 420                         if (*pattern == '!' || *pattern == '^') {
 421                                 negate = 1;
 422                                 ++pattern;
 423                         } else
 424                                 negate = 0;
 425                         matched = 0;
 426                         c = *pattern++;
 427                         do {
 428                                 if (c == '\\')
 429                                         c = *pattern++;
 430                                 if (c == '\0') {
 431                                         pattern = saved_pattern;
 432                                         c = '[';
 433                                         goto norm;
 434                                 }
 435                                 if (*pattern == '-') {
 436                                         char c2 = *(pattern + 1);
 437                                         if (c2 == '\0') {
 438                                                 pattern = saved_pattern;
 439                                                 c = '[';
 440                                                 goto norm;
 441                                         }
 442                                         if (c2 == ']') {
 443                                                 /* [a-] is not a range. */
 444                                                 if (c == *string
 445                                                     || '-' == *string)
 446                                                         matched = 1;
 447                                                 pattern ++;
 448                                         } else {
 449                                                 if (c <= *string
 450                                                     && *string <= c2)
 451                                                         matched = 1;
 452                                                 pattern += 2;
 453                                         }
 454                                 } else if (c == *string)
 455                                         matched = 1;
 456                                 c = *pattern++;
 457                         } while (c != ']');
 458                         if (matched == negate)
 459                                 return (1);
 460                         ++string;
 461                         break;
 462                 case '\\':
 463                         if ((c = *pattern++) == '\0') {
 464                                 c = '\\';
 465                                 --pattern;
 466                         }
 467                         /* FALLTHROUGH */
 468                 default:
 469                 norm:
 470                         if (c != *string)
 471                                 return (1);
 472                         string++;
 473                         break;
 474                 }
 475         }
 476         /* NOTREACHED */
 477 }
 478
 479 #endif