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 == '.' || *s == '/') {
 105                 if (s[0] != '/' && s[1] != '/')
 106                         break;
 107                 ++s;
 108         }
 109         return (s);
 110 }
 111
 112 static int
 113 pm(const char *p, const char *s, int flags)
 114 {
 115         const char *end;
 116
 117         /*
 118          * Ignore leading './', './/', '././', etc.
 119          */
 120         if (s[0] == '.' && s[1] == '/')
 121                 s = pm_slashskip(s + 1);
 122         if (p[0] == '.' && p[1] == '/')
 123                 p = pm_slashskip(p + 1);
 124
 125         for (;;) {
 126                 switch (*p) {
 127                 case '\0':
 128                         if (s[0] == '/') {
 129                                 if (flags & PATHMATCH_NO_ANCHOR_END)
 130                                         return (1);
 131                                 /* "dir" == "dir/" == "dir/." */
 132                                 s = pm_slashskip(s);
 133                                 if (s[0] == '.' && s[1] == '\0')
 134                                         return (1);
 135                         }
 136                         return (*s == '\0');
 137                         break;
 138                 case '?':
 139                         /* ? always succeds, unless we hit end of 's' */
 140                         if (*s == '\0')
 141                                 return (0);
 142                         break;
 143                 case '*':
 144                         /* "*" == "**" == "***" ... */
 145                         while (*p == '*')
 146                                 ++p;
 147                         /* Trailing '*' always succeeds. */
 148                         if (*p == '\0')
 149                                 return (1);
 150                         while (*s) {
 151                                 if (pathmatch(p, s, flags))
 152                                         return (1);
 153                                 ++s;
 154                         }
 155                         return (0);
 156                         break;
 157                 case '[':
 158                         /*
 159                          * Find the end of the [...] character class,
 160                          * ignoring \] that might occur within the class.
 161                          */
 162                         end = p + 1;
 163                         while (*end != '\0' && *end != ']') {
 164                                 if (*end == '\\' && end[1] != '\0')
 165                                         ++end;
 166                                 ++end;
 167                         }
 168                         if (*end == ']') {
 169                                 /* We found [...], try to match it. */
 170                                 if (!pm_list(p + 1, end, *s, flags))
 171                                         return (0);
 172                                 p = end; /* Jump to trailing ']' char. */
 173                                 break;
 174                         } else
 175                                 /* No final ']', so just match '['. */
 176                                 if (*p != *s)
 177                                         return (0);
 178                         break;
 179                 default:
 180                         if (*p == *s)
 181                                 break;
 182                         if ((*s == '\0') && (*p == '/')) {
 183                                 p = pm_slashskip(p);
 184                                 if (*p == '\0')
 185                                         return (1);
 186                                 if (p[0] == '.' && p[1] == '\0')
 187                                         return (1);
 188                                 return (0);
 189                         }
 190                         return (0);
 191                         break;
 192                 case '\\':
 193                         /* Trailing '\\' matches itself. */
 194                         if (p[1] == '\0') {
 195                                 if (*s != '\\')
 196                                         return (0);
 197                         } else {
 198                                 ++p;
 199                                 if (*p != *s)
 200                                         return (0);
 201                         }
 202                         break;
 203                 }
 204                 /*
 205                  * TODO: pattern of "\/\.\/" should not match plain "/",
 206                  * it should only match explicit "/./".
 207                  */
 208                 if (*p == '/')
 209                         p = pm_slashskip(p);
 210                 else
 211                         ++p;
 212                 if (*s == '/')
 213                         s = pm_slashskip(s);
 214                 else
 215                         ++s;
 216         }
 217 }
 218
 219 /* Main entry point. */
 220 int
 221 pathmatch(const char *p, const char *s, int flags)
 222 {
 223         /* Empty pattern only matches the empty string. */
 224         if (p == NULL || *p == '\0')
 225                 return (s == NULL || *s == '\0');
 226
 227         /* Leading '^' anchors the start of the pattern. */
 228         if (*p == '^') {
 229                 ++p;
 230                 flags &= ~PATHMATCH_NO_ANCHOR_START;
 231         }
 232
 233         /* Certain patterns anchor implicitly. */
 234         if (*p == '*' || *p == '/')
 235                 return (pm(p, s, flags));
 236
 237         /* If start is unanchored, try to match start of each path element. */
 238         if (flags & PATHMATCH_NO_ANCHOR_START) {
 239                 for ( ; p != NULL; p = strchr(p, '/')) {
 240                         if (*p == '/')
 241                                 p++;
 242                         if (pm(p, s, flags))
 243                                 return (1);
 244                 }
 245                 return (0);
 246         }
 247
 248         /* Default: Match from beginning. */
 249         return (pm(p, s, flags));
 250 }