wimlib.net Git - wimlib/blob - src/pattern.c

   1 /*
   2  * pattern.c
   3  *
   4  * Wildcard pattern matching functions.
   5  */
   6
   7 /*
   8  * Copyright (C) 2013, 2015 Eric Biggers
   9  *
  10  * This file is free software; you can redistribute it and/or modify it under
  11  * the terms of the GNU Lesser General Public License as published by the Free
  12  * Software Foundation; either version 3 of the License, or (at your option) any
  13  * later version.
  14  *
  15  * This file is distributed in the hope that it will be useful, but WITHOUT
  16  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  17  * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
  18  * details.
  19  *
  20  * You should have received a copy of the GNU Lesser General Public License
  21  * along with this file; if not, see http://www.gnu.org/licenses/.
  22  */
  23
  24 #ifdef HAVE_CONFIG_H
  25 #  include "config.h"
  26 #endif
  27
  28 #include <ctype.h>
  29
  30 #include "wimlib/dentry.h"
  31 #include "wimlib/encoding.h"
  32 #include "wimlib/paths.h"
  33 #include "wimlib/pattern.h"
  34
  35 static bool
  36 string_matches_pattern(const tchar *string, const tchar * const string_end,
  37                        const tchar *pattern, const tchar * const pattern_end)
  38 {
  39         for (; string != string_end; string++, pattern++) {
  40                 if (pattern == pattern_end)
  41                         return false;
  42                 if (*pattern == T('*')) {
  43                         return string_matches_pattern(string, string_end,
  44                                                       pattern + 1, pattern_end) ||
  45                                string_matches_pattern(string + 1, string_end,
  46                                                       pattern, pattern_end);
  47                 }
  48                 if (*string != *pattern && *pattern != T('?') &&
  49                     !(default_ignore_case &&
  50                       totlower(*string) == totlower(*pattern)))
  51                         return false;
  52         }
  53
  54         while (pattern != pattern_end && *pattern == T('*'))
  55                 pattern++;
  56         return pattern == pattern_end;
  57 }
  58
  59 /* Advance past zero or more path separators.  */
  60 static const tchar *
  61 advance_to_next_component(const tchar *p)
  62 {
  63         while (*p == WIM_PATH_SEPARATOR)
  64                 p++;
  65         return p;
  66 }
  67
  68 /* Advance past a nonempty path component.  */
  69 static const tchar *
  70 advance_through_component(const tchar *p)
  71 {
  72         do {
  73                 p++;
  74         } while (*p && *p != WIM_PATH_SEPARATOR);
  75         return p;
  76 }
  77
  78 /*
  79  * Determine whether a path matches a wildcard pattern.
  80  *
  81  * @path
  82  *      The null-terminated path string to match.
  83  * @pattern
  84  *      The null-terminated wildcard pattern to match.  It can contain the
  85  *      wildcard characters '*' (which matches zero or more characters) and '?'
  86  *      (which matches any single character).  If there is no leading path
  87  *      separator, then the match is attempted with the filename component of
  88  *      @path only; otherwise, the match is attempted with the entire @path.
  89  * @prefix_ok
  90  *      If %true, also allow a prefix of @path terminated by a path separator
  91  *      (a.k.a. an ancestor directory) to match the pattern.
  92  *
  93  * @path and @pattern can both contain path separators (character
  94  * WIM_PATH_SEPARATOR).  Leading and trailing path separators are not
  95  * significant, except when determining whether to match only the filename
  96  * component as noted above.  The lengths of interior path separator sequences
  97  * are not significant.  The '*' and '?' characters act within a single path
  98  * component only (they do not match path separators).
  99  *
 100  * Matching is done with the default case sensitivity behavior.
 101  *
 102  * Returns %true iff the path matched the pattern.
 103  */
 104 bool
 105 match_path(const tchar *path, const tchar *pattern, bool prefix_ok)
 106 {
 107         /* Filename only?  */
 108         if (*pattern != WIM_PATH_SEPARATOR)
 109                 path = path_basename(path);
 110
 111         for (;;) {
 112                 const tchar *path_component_end;
 113                 const tchar *pattern_component_end;
 114
 115                 path = advance_to_next_component(path);
 116                 pattern = advance_to_next_component(pattern);
 117
 118                 /* Is the pattern exhausted?  */
 119                 if (!*pattern)
 120                         return !*path || prefix_ok;
 121
 122                 /* Is the path exhausted (but not the pattern)?  */
 123                 if (!*path)
 124                         return false;
 125
 126                 path_component_end = advance_through_component(path);
 127                 pattern_component_end = advance_through_component(pattern);
 128
 129                 /* Do the components match?  */
 130                 if (!string_matches_pattern(path, path_component_end,
 131                                             pattern, pattern_component_end))
 132                         return false;
 133
 134                 path = path_component_end;
 135                 pattern = pattern_component_end;
 136         }
 137 }
 138
 139 /*
 140  * Expand a path pattern in an in-memory tree of dentries.
 141  *
 142  * @root
 143  *      The root of the directory tree in which to expand the pattern.
 144  * @pattern
 145  *      The path pattern to expand, which may contain the '*' and '?' wildcard
 146  *      characters.  Path separators must be WIM_PATH_SEPARATOR.  Leading and
 147  *      trailing path separators are ignored.  The default case sensitivity
 148  *      behavior is used.
 149  * @consume_dentry
 150  *      A callback function which will receive each matched directory entry.
 151  * @ctx
 152  *      Opaque context argument for @consume_dentry.
 153  *
 154  * @return 0 on success; a positive error code on failure; or the first nonzero
 155  * value returned by @consume_dentry.
 156  */
 157 int
 158 expand_path_pattern(struct wim_dentry *root, const tchar *pattern,
 159                     int (*consume_dentry)(struct wim_dentry *, void *),
 160                     void *ctx)
 161 {
 162         const tchar *pattern_component_end;
 163         struct wim_dentry *child;
 164
 165         if (!root)
 166                 return 0;
 167
 168         pattern = advance_to_next_component(pattern);
 169
 170         /* If there are no more components, then 'root' is matched.  */
 171         if (!*pattern)
 172                 return (*consume_dentry)(root, ctx);
 173
 174         pattern_component_end = advance_through_component(pattern);
 175
 176         /* For each child dentry that matches the current pattern component,
 177          * recurse with the remainder of the pattern.  */
 178         for_dentry_child(child, root) {
 179                 const tchar *name;
 180                 size_t name_nbytes;
 181                 int ret;
 182
 183                 ret = utf16le_get_tstr(child->d_name, child->d_name_nbytes,
 184                                        &name, &name_nbytes);
 185                 if (ret)
 186                         return ret;
 187
 188                 if (string_matches_pattern(name, &name[name_nbytes / sizeof(tchar)],
 189                                            pattern, pattern_component_end))
 190                         ret = expand_path_pattern(child, pattern_component_end,
 191                                                   consume_dentry, ctx);
 192                 utf16le_put_tstr(name);
 193                 if (ret)
 194                         return ret;
 195         }
 196         return 0;
 197 }