4 * Wildcard pattern matching functions.
8 * Copyright (C) 2013, 2015 Eric Biggers
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
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
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/.
30 #include "wimlib/dentry.h"
31 #include "wimlib/encoding.h"
32 #include "wimlib/paths.h"
33 #include "wimlib/pattern.h"
36 string_matches_pattern(const tchar *string, const tchar * const string_end,
37 const tchar *pattern, const tchar * const pattern_end)
39 for (; string != string_end; string++, pattern++) {
40 if (pattern == pattern_end)
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);
48 if (*string != *pattern && *pattern != T('?') &&
49 !(default_ignore_case &&
50 totlower(*string) == totlower(*pattern)))
54 while (pattern != pattern_end && *pattern == T('*'))
56 return pattern == pattern_end;
59 /* Advance past zero or more path separators. */
61 advance_to_next_component(const tchar *p)
63 while (*p == WIM_PATH_SEPARATOR)
68 /* Advance past a nonempty path component. */
70 advance_through_component(const tchar *p)
74 } while (*p && *p != WIM_PATH_SEPARATOR);
79 * Determine whether a path matches a wildcard pattern.
82 * The null-terminated path string to match.
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.
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.
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).
100 * Matching is done with the default case sensitivity behavior.
102 * Returns %true iff the path matched the pattern.
105 match_path(const tchar *path, const tchar *pattern, bool prefix_ok)
108 if (*pattern != WIM_PATH_SEPARATOR)
109 path = path_basename(path);
112 const tchar *path_component_end;
113 const tchar *pattern_component_end;
115 path = advance_to_next_component(path);
116 pattern = advance_to_next_component(pattern);
118 /* Is the pattern exhausted? */
120 return !*path || prefix_ok;
122 /* Is the path exhausted (but not the pattern)? */
126 path_component_end = advance_through_component(path);
127 pattern_component_end = advance_through_component(pattern);
129 /* Do the components match? */
130 if (!string_matches_pattern(path, path_component_end,
131 pattern, pattern_component_end))
134 path = path_component_end;
135 pattern = pattern_component_end;
140 * Expand a path pattern in an in-memory tree of dentries.
143 * The root of the directory tree in which to expand the 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
150 * A callback function which will receive each matched directory entry.
152 * Opaque context argument for @consume_dentry.
154 * @return 0 on success; a positive error code on failure; or the first nonzero
155 * value returned by @consume_dentry.
158 expand_path_pattern(struct wim_dentry *root, const tchar *pattern,
159 int (*consume_dentry)(struct wim_dentry *, void *),
162 const tchar *pattern_component_end;
163 struct wim_dentry *child;
168 pattern = advance_to_next_component(pattern);
170 /* If there are no more components, then 'root' is matched. */
172 return (*consume_dentry)(root, ctx);
174 pattern_component_end = advance_through_component(pattern);
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) {
183 ret = utf16le_get_tstr(child->d_name, child->d_name_nbytes,
184 &name, &name_nbytes);
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);