4 * Wildcard matching functions.
8 * Copyright (C) 2013 Eric Biggers
10 * This file is part of wimlib, a library for working with WIM files.
12 * wimlib is free software; you can redistribute it and/or modify it under the
13 * terms of the GNU General Public License as published by the Free
14 * Software Foundation; either version 3 of the License, or (at your option)
17 * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY
18 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
19 * A PARTICULAR PURPOSE. See the GNU General Public License for more
22 * You should have received a copy of the GNU General Public License
23 * along with wimlib; if not, see http://www.gnu.org/licenses/.
31 #include "wimlib/dentry.h"
32 #include "wimlib/encoding.h"
33 #include "wimlib/error.h"
34 #include "wimlib/metadata.h"
35 #include "wimlib/paths.h"
36 #include "wimlib/wildcard.h"
38 struct match_dentry_ctx {
39 int (*consume_dentry)(struct wim_dentry *, void *);
40 void *consume_dentry_ctx;
41 size_t consume_dentry_count;
43 size_t cur_component_offset;
44 size_t cur_component_len;
45 bool case_insensitive;
49 do_match_wildcard(const tchar *string, size_t string_len,
50 const tchar *wildcard, size_t wildcard_len,
54 if (string_len == 0) {
55 while (wildcard_len != 0 && *wildcard == T('*')) {
59 return (wildcard_len == 0);
60 } else if (wildcard_len == 0) {
62 } else if (*string == *wildcard || *wildcard == T('?') ||
63 (ignore_case && totlower(*string) == totlower(*wildcard)))
70 } else if (*wildcard == T('*')) {
71 return do_match_wildcard(string, string_len,
72 wildcard + 1, wildcard_len - 1,
74 do_match_wildcard(string + 1, string_len - 1,
75 wildcard, wildcard_len,
84 match_wildcard(const tchar *string, const tchar *wildcard,
85 size_t wildcard_len, bool ignore_case)
87 return do_match_wildcard(string, tstrlen(string),
88 wildcard, wildcard_len, ignore_case);
92 * Determines whether a path matches a wildcard pattern.
95 * The path to match. Assumptions: All path separators must be @path_sep,
96 * there cannot be consecutive path separators, there cannot be a trailing
97 * path separator, and there must be exactly one leading path separator.
100 * Number of characters in @path.
103 * The wildcard pattern to match. It can contain the wildcard characters
104 * '*' and '?'. The former matches zero or more characters except
105 * @path_sep, and the latter matches any character except @path_sep. All
106 * path separators in the pattern must be @path_sep, and there cannot be
107 * consecutive path separators, and there cannot be a trailing path
108 * separator. If there is a leading path separator, the match is attempted
109 * with the filename only; otherwise, the match is attempted with the whole
113 * Path separator character used in @path and @wildcard.
116 * If %true, allow a prefix of @path, terminated by a path separator, to
117 * match the pattern, in addition to @path itself. In other words, return
118 * %true if the pattern actually matches one of the ancestor directories of
121 * Returns %true if there was a match; %false if there was not.
124 match_path(const tchar *path, size_t path_nchars,
125 const tchar *wildcard, tchar path_sep, bool prefix_ok)
127 if (*wildcard != path_sep) {
128 /* Pattern doesn't begin with path separator. Try to match the
130 return match_wildcard(path_basename_with_len(path, path_nchars),
131 wildcard, tstrlen(wildcard),
132 default_ignore_case);
134 /* Pattern begins with path separator. Try to match the whole
138 /* Path has more components than pattern */
142 size_t path_component_len = 0;
143 size_t wildcard_component_len = 0;
146 path_component_len++;
147 } while (path[path_component_len] != path_sep &&
148 path[path_component_len] != T('\0'));
150 wildcard_component_len++;
151 } while (wildcard[wildcard_component_len] != path_sep &&
152 wildcard[wildcard_component_len] != T('\0'));
153 if (!do_match_wildcard(path, path_component_len,
154 wildcard, wildcard_component_len,
155 default_ignore_case))
157 path += path_component_len;
158 wildcard += wildcard_component_len;
161 return (*wildcard == '\0');
166 expand_wildcard_recursive(struct wim_dentry *cur_dentry,
167 struct match_dentry_ctx *ctx);
170 WILDCARD_STATUS_DONE_FULLY,
171 WILDCARD_STATUS_DONE_TRAILING_SLASHES,
172 WILDCARD_STATUS_NOT_DONE,
176 wildcard_status(const tchar *wildcard)
178 if (*wildcard == T('\0'))
179 return WILDCARD_STATUS_DONE_FULLY;
180 while (*wildcard == WIM_PATH_SEPARATOR)
182 if (*wildcard == T('\0'))
183 return WILDCARD_STATUS_DONE_TRAILING_SLASHES;
185 return WILDCARD_STATUS_NOT_DONE;
189 match_dentry(struct wim_dentry *cur_dentry, struct match_dentry_ctx *ctx)
195 if (cur_dentry->file_name_nbytes == 0)
198 ret = utf16le_get_tstr(cur_dentry->file_name,
199 cur_dentry->file_name_nbytes,
200 &name, &name_nchars);
203 name_nchars /= sizeof(tchar);
205 if (do_match_wildcard(name,
207 &ctx->wildcard_path[ctx->cur_component_offset],
208 ctx->cur_component_len,
209 ctx->case_insensitive))
211 switch (wildcard_status(&ctx->wildcard_path[
212 ctx->cur_component_offset +
213 ctx->cur_component_len]))
215 case WILDCARD_STATUS_DONE_TRAILING_SLASHES:
216 if (!dentry_is_directory(cur_dentry)) {
221 case WILDCARD_STATUS_DONE_FULLY:
222 ret = (*ctx->consume_dentry)(cur_dentry,
223 ctx->consume_dentry_ctx);
224 ctx->consume_dentry_count++;
226 case WILDCARD_STATUS_NOT_DONE:
227 ret = expand_wildcard_recursive(cur_dentry, ctx);
234 utf16le_put_tstr(name);
240 expand_wildcard_recursive(struct wim_dentry *cur_dentry,
241 struct match_dentry_ctx *ctx)
250 struct wim_dentry *child;
252 w = ctx->wildcard_path;
254 begin = ctx->cur_component_offset + ctx->cur_component_len;
255 while (w[begin] == WIM_PATH_SEPARATOR)
260 while (w[end] != T('\0') && w[end] != WIM_PATH_SEPARATOR)
268 offset_save = ctx->cur_component_offset;
269 len_save = ctx->cur_component_len;
271 ctx->cur_component_offset = begin;
272 ctx->cur_component_len = len;
275 for_dentry_child(child, cur_dentry) {
276 ret = match_dentry(child, ctx);
281 ctx->cur_component_len = len_save;
282 ctx->cur_component_offset = offset_save;
287 /* Expand a wildcard relative to the current WIM image.
290 * WIMStruct whose currently selected image is searched to expand the
293 * Wildcard path to expand, which may contain the '?' and '*' characters.
294 * Path separators must be WIM_PATH_SEPARATOR. Leading path separators are
295 * ignored, whereas one or more trailing path separators indicate that the
296 * wildcard path can only match directories (and not reparse points).
298 * Callback function which will receive each directory entry matched by the
300 * @consume_dentry_ctx
301 * Argument to pass to @consume_dentry.
303 * Zero or more of the following flags:
305 * WILDCARD_FLAG_WARN_IF_NO_MATCH:
306 * Issue a warning if the wildcard does not match any dentries.
308 * WILDCARD_FLAG_ERROR_IF_NO_MATCH:
309 * Issue an error and return WIMLIB_ERR_PATH_DOES_NOT_EXIST if the
310 * wildcard does not match any dentries.
312 * WILDCARD_FLAG_CASE_INSENSITIVE:
313 * Perform the matching case insensitively. Note that this may
314 * cause @wildcard to match multiple dentries, even if it does not
315 * contain wildcard characters.
317 * @return 0 on success; a positive error code on error; or the first nonzero
318 * value returned by @consume_dentry.
321 expand_wildcard(WIMStruct *wim,
322 const tchar *wildcard_path,
323 int (*consume_dentry)(struct wim_dentry *, void *),
324 void *consume_dentry_ctx,
327 struct wim_dentry *root;
330 root = wim_get_current_root_dentry(wim);
334 struct match_dentry_ctx ctx = {
335 .consume_dentry = consume_dentry,
336 .consume_dentry_ctx = consume_dentry_ctx,
337 .consume_dentry_count = 0,
338 .wildcard_path = TSTRDUP(wildcard_path),
339 .cur_component_offset = 0,
340 .cur_component_len = 0,
341 .case_insensitive = ((flags & WILDCARD_FLAG_CASE_INSENSITIVE) != 0),
344 if (ctx.wildcard_path == NULL)
345 return WIMLIB_ERR_NOMEM;
347 ret = expand_wildcard_recursive(root, &ctx);
348 FREE(ctx.wildcard_path);
349 if (ret == 0 && ctx.consume_dentry_count == 0)
355 if (flags & WILDCARD_FLAG_WARN_IF_NO_MATCH)
356 WARNING("No matches for wildcard path \"%"TS"\"", wildcard_path);
358 if (flags & WILDCARD_FLAG_ERROR_IF_NO_MATCH) {
359 ERROR("No matches for wildcard path \"%"TS"\"", wildcard_path);
360 ret = WIMLIB_ERR_PATH_DOES_NOT_EXIST;