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