contrib/libarchive/libarchive_fe/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 "lafe_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 '!' or '^' 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 == '^') && 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                 case '?':
 135                         /* ? always succeds, unless we hit end of 's' */
 136                         if (*s == '\0')
 137                                 return (0);
 138                         break;
 139                 case '*':
 140                         /* "*" == "**" == "***" ... */
 141                         while (*p == '*')
 142                                 ++p;
 143                         /* Trailing '*' always succeeds. */
 144                         if (*p == '\0')
 145                                 return (1);
 146                         while (*s) {
 147                                 if (lafe_pathmatch(p, s, flags))
 148                                         return (1);
 149                                 ++s;
 150                         }
 151                         return (0);
 152                 case '[':
 153                         /*
 154                          * Find the end of the [...] character class,
 155                          * ignoring \] that might occur within the class.
 156                          */
 157                         end = p + 1;
 158                         while (*end != '\0' && *end != ']') {
 159                                 if (*end == '\\' && end[1] != '\0')
 160                                         ++end;
 161                                 ++end;
 162                         }
 163                         if (*end == ']') {
 164                                 /* We found [...], try to match it. */
 165                                 if (!pm_list(p + 1, end, *s, flags))
 166                                         return (0);
 167                                 p = end; /* Jump to trailing ']' char. */
 168                                 break;
 169                         } else
 170                                 /* No final ']', so just match '['. */
 171                                 if (*p != *s)
 172                                         return (0);
 173                         break;
 174                 case '\\':
 175                         /* Trailing '\\' matches itself. */
 176                         if (p[1] == '\0') {
 177                                 if (*s != '\\')
 178                                         return (0);
 179                         } else {
 180                                 ++p;
 181                                 if (*p != *s)
 182                                         return (0);
 183                         }
 184                         break;
 185                 case '/':
 186                         if (*s != '/' && *s != '\0')
 187                                 return (0);
 188                         /* Note: pattern "/\./" won't match "/";
 189                          * pm_slashskip() correctly stops at backslash. */
 190                         p = pm_slashskip(p);
 191                         s = pm_slashskip(s);
 192                         if (*p == '\0' && (flags & PATHMATCH_NO_ANCHOR_END))
 193                                 return (1);
 194                         --p; /* Counteract the increment below. */
 195                         --s;
 196                         break;
 197                 case '$':
 198                         /* '$' is special only at end of pattern and only
 199                          * if PATHMATCH_NO_ANCHOR_END is specified. */
 200                         if (p[1] == '\0' && (flags & PATHMATCH_NO_ANCHOR_END)){
 201                                 /* "dir" == "dir/" == "dir/." */
 202                                 return (*pm_slashskip(s) == '\0');
 203                         }
 204                         /* Otherwise, '$' is not special. */
 205                         /* FALL THROUGH */
 206                 default:
 207                         if (*p != *s)
 208                                 return (0);
 209                         break;
 210                 }
 211                 ++p;
 212                 ++s;
 213         }
 214 }
 215
 216 /* Main entry point. */
 217 int
 218 lafe_pathmatch(const char *p, const char *s, int flags)
 219 {
 220         /* Empty pattern only matches the empty string. */
 221         if (p == NULL || *p == '\0')
 222                 return (s == NULL || *s == '\0');
 223
 224         /* Leading '^' anchors the start of the pattern. */
 225         if (*p == '^') {
 226                 ++p;
 227                 flags &= ~PATHMATCH_NO_ANCHOR_START;
 228         }
 229
 230         if (*p == '/' && *s != '/')
 231                 return (0);
 232
 233         /* Certain patterns and file names anchor implicitly. */
 234         if (*p == '*' || *p == '/' || *p == '/') {
 235                 while (*p == '/')
 236                         ++p;
 237                 while (*s == '/')
 238                         ++s;
 239                 return (pm(p, s, flags));
 240         }
 241
 242         /* If start is unanchored, try to match start of each path element. */
 243         if (flags & PATHMATCH_NO_ANCHOR_START) {
 244                 for ( ; s != NULL; s = strchr(s, '/')) {
 245                         if (*s == '/')
 246                                 s++;
 247                         if (pm(p, s, flags))
 248                                 return (1);
 249                 }
 250                 return (0);
 251         }
 252
 253         /* Default: Match from beginning. */
 254         return (pm(p, s, flags));
 255 }