contrib/libarchive/cpio/pathmatch.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  *    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 "cpio_platform.h"
  28 __FBSDID("$FreeBSD$");
  29
  30 #ifdef HAVE_STRING_H
  31 #include <string.h>
  32 #endif
  33
  34 #include "pathmatch.h"
  35
  36 /*
  37  * Check whether a character 'c' is matched by a list specification [...]:
  38  *    * Leading '!' negates the class.
  39  *    * <char>-<char> is a range of characters
  40  *    * \<char> removes any special meaning for <char>
  41  *
  42  * Some interesting boundary cases:
  43  *   a-d-e is one range (a-d) followed by two single characters - and e.
  44  *   \a-\d is same as a-d
  45  *   a\-d is three single characters: a, d, -
  46  *   Trailing - is not special (so [a-] is two characters a and -).
  47  *   Initial - is not special ([a-] is same as [-a] is same as [\\-a])
  48  *   This function never sees a trailing \.
  49  *   [] always fails
  50  *   [!] always succeeds
  51  */
  52 static int
  53 pm_list(const char *start, const char *end, const char c, int flags)
  54 {
  55         const char *p = start;
  56         char rangeStart = '\0', nextRangeStart;
  57         int match = 1, nomatch = 0;
  58
  59         /* This will be used soon... */
  60         (void)flags; /* UNUSED */
  61
  62         /* If this is a negated class, return success for nomatch. */
  63         if (*p == '!' && p < end) {
  64                 match = 0;
  65                 nomatch = 1;
  66                 ++p;
  67         }
  68
  69         while (p < end) {
  70                 nextRangeStart = '\0';
  71                 switch (*p) {
  72                 case '-':
  73                         /* Trailing or initial '-' is not special. */
  74                         if ((rangeStart == '\0') || (p == end - 1)) {
  75                                 if (*p == c)
  76                                         return (match);
  77                         } else {
  78                                 char rangeEnd = *++p;
  79                                 if (rangeEnd == '\\')
  80                                         rangeEnd = *++p;
  81                                 if ((rangeStart <= c) && (c <= rangeEnd))
  82                                         return (match);
  83                         }
  84                         break;
  85                 case '\\':
  86                         ++p;
  87                         /* Fall through */
  88                 default:
  89                         if (*p == c)
  90                                 return (match);
  91                         nextRangeStart = *p; /* Possible start of range. */
  92                 }
  93                 rangeStart = nextRangeStart;
  94                 ++p;
  95         }
  96         return (nomatch);
  97 }
  98
  99 /*
 100  * If s is pointing to "./", ".//", "./././" or the like, skip it.
 101  */
 102 static const char *
 103 pm_slashskip(const char *s) {
 104         while ((*s == '/')
 105             || (s[0] == '.' && s[1] == '/')
 106             || (s[0] == '.' && s[1] == '\0'))
 107                 ++s;
 108         return (s);
 109 }
 110
 111 static int
 112 pm(const char *p, const char *s, int flags)
 113 {
 114         const char *end;
 115
 116         /*
 117          * Ignore leading './', './/', '././', etc.
 118          */
 119         if (s[0] == '.' && s[1] == '/')
 120                 s = pm_slashskip(s + 1);
 121         if (p[0] == '.' && p[1] == '/')
 122                 p = pm_slashskip(p + 1);
 123
 124         for (;;) {
 125                 switch (*p) {
 126                 case '\0':
 127                         if (s[0] == '/') {
 128                                 if (flags & PATHMATCH_NO_ANCHOR_END)
 129                                         return (1);
 130                                 /* "dir" == "dir/" == "dir/." */
 131                                 s = pm_slashskip(s);
 132                         }
 133                         return (*s == '\0');
 134                         break;
 135                 case '?':
 136                         /* ? always succeds, unless we hit end of 's' */
 137                         if (*s == '\0')
 138                                 return (0);
 139                         break;
 140                 case '*':
 141                         /* "*" == "**" == "***" ... */
 142                         while (*p == '*')
 143                                 ++p;
 144                         /* Trailing '*' always succeeds. */
 145                         if (*p == '\0')
 146                                 return (1);
 147                         while (*s) {
 148                                 if (pathmatch(p, s, flags))
 149                                         return (1);
 150                                 ++s;
 151                         }
 152                         return (0);
 153                         break;
 154                 case '[':
 155                         /*
 156                          * Find the end of the [...] character class,
 157                          * ignoring \] that might occur within the class.
 158                          */
 159                         end = p + 1;
 160                         while (*end != '\0' && *end != ']') {
 161                                 if (*end == '\\' && end[1] != '\0')
 162                                         ++end;
 163                                 ++end;
 164                         }
 165                         if (*end == ']') {
 166                                 /* We found [...], try to match it. */
 167                                 if (!pm_list(p + 1, end, *s, flags))
 168                                         return (0);
 169                                 p = end; /* Jump to trailing ']' char. */
 170                                 break;
 171                         } else
 172                                 /* No final ']', so just match '['. */
 173                                 if (*p != *s)
 174                                         return (0);
 175                         break;
 176                 case '\\':
 177                         /* Trailing '\\' matches itself. */
 178                         if (p[1] == '\0') {
 179                                 if (*s != '\\')
 180                                         return (0);
 181                         } else {
 182                                 ++p;
 183                                 if (*p != *s)
 184                                         return (0);
 185                         }
 186                         break;
 187                 case '/':
 188                         if (*s != '/' && *s != '\0')
 189                                 return (0);
 190                         /* Note: pattern "/\./" won't match "/";
 191                          * pm_slashskip() correctly stops at backslash. */
 192                         p = pm_slashskip(p);
 193                         s = pm_slashskip(s);
 194                         if (*p == '\0' && (flags & PATHMATCH_NO_ANCHOR_END))
 195                                 return (1);
 196                         --p; /* Counteract the increment below. */
 197                         --s;
 198                         break;
 199                 case '$':
 200                         /* '$' is special only at end of pattern and only
 201                          * if PATHMATCH_NO_ANCHOR_END is specified. */
 202                         if (p[1] == '\0' && (flags & PATHMATCH_NO_ANCHOR_END)){
 203                                 /* "dir" == "dir/" == "dir/." */
 204                                 return (*pm_slashskip(s) == '\0');
 205                         }
 206                         /* Otherwise, '$' is not special. */
 207                         /* FALL THROUGH */
 208                 default:
 209                         if (*p != *s)
 210                                 return (0);
 211                         break;
 212                 }
 213                 ++p;
 214                 ++s;
 215         }
 216 }
 217
 218 /* Main entry point. */
 219 int
 220 pathmatch(const char *p, const char *s, int flags)
 221 {
 222         /* Empty pattern only matches the empty string. */
 223         if (p == NULL || *p == '\0')
 224                 return (s == NULL || *s == '\0');
 225
 226         /* Leading '^' anchors the start of the pattern. */
 227         if (*p == '^') {
 228                 ++p;
 229                 flags &= ~PATHMATCH_NO_ANCHOR_START;
 230         }
 231
 232         /* Certain patterns anchor implicitly. */
 233         if (*p == '*' || *p == '/')
 234                 return (pm(p, s, flags));
 235
 236         /* If start is unanchored, try to match start of each path element. */
 237         if (flags & PATHMATCH_NO_ANCHOR_START) {
 238                 for ( ; s != NULL; s = strchr(s, '/')) {
 239                         if (*s == '/')
 240                                 s++;
 241                         if (pm(p, s, flags))
 242                                 return (1);
 243                 }
 244                 return (0);
 245         }
 246
 247         /* Default: Match from beginning. */
 248         return (pm(p, s, flags));
 249 }