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 matchis attempted with the whole
113 * Path separator character in @path and @wildcard.
116 * If %true, allow a prefix of @path, terminated by a path separator, to
117 * match, in addition to @path itself. a.k.a. also return true if the
118 * wildcard actually matches one of the ancestor directories of @path.
120 * Returns %true if there was a match; %false if there was not.
123 match_path(const tchar *path, size_t path_nchars,
124 const tchar *wildcard, tchar path_sep, bool prefix_ok)
126 if (*wildcard != path_sep) {
127 /* Pattern doesn't begin with path separator. Try to match the
129 return match_wildcard(path_basename_with_len(path, path_nchars),
130 wildcard, tstrlen(wildcard),
131 default_ignore_case);
133 /* Pattern begins with path separator. Try to match the whole
137 /* Path has more components than pattern */
141 size_t path_component_len = 0;
142 size_t wildcard_component_len = 0;
145 path_component_len++;
146 } while (path[path_component_len] != path_sep &&
147 path[path_component_len] != T('\0'));
149 wildcard_component_len++;
150 } while (wildcard[wildcard_component_len] != path_sep &&
151 wildcard[wildcard_component_len] != T('\0'));
152 if (!do_match_wildcard(path, path_component_len,
153 wildcard, wildcard_component_len,
154 default_ignore_case))
156 path += path_component_len;
157 wildcard += wildcard_component_len;
160 return (*wildcard == '\0');
165 expand_wildcard_recursive(struct wim_dentry *cur_dentry,
166 struct match_dentry_ctx *ctx);
169 WILDCARD_STATUS_DONE_FULLY,
170 WILDCARD_STATUS_DONE_TRAILING_SLASHES,
171 WILDCARD_STATUS_NOT_DONE,
175 wildcard_status(const tchar *wildcard)
177 if (*wildcard == T('\0'))
178 return WILDCARD_STATUS_DONE_FULLY;
179 while (*wildcard == WIM_PATH_SEPARATOR)
181 if (*wildcard == T('\0'))
182 return WILDCARD_STATUS_DONE_TRAILING_SLASHES;
184 return WILDCARD_STATUS_NOT_DONE;
188 match_dentry(struct wim_dentry *cur_dentry, struct match_dentry_ctx *ctx)
194 if (cur_dentry->file_name_nbytes == 0)
198 name = cur_dentry->file_name;
199 name_len = cur_dentry->file_name_nbytes;
201 ret = utf16le_to_tstr(cur_dentry->file_name,
202 cur_dentry->file_name_nbytes,
207 name_len /= sizeof(tchar);
209 if (match_wildcard(name,
210 &ctx->wildcard_path[ctx->cur_component_offset],
211 ctx->cur_component_len,
212 ctx->case_insensitive))
214 switch (wildcard_status(&ctx->wildcard_path[
215 ctx->cur_component_offset +
216 ctx->cur_component_len]))
218 case WILDCARD_STATUS_DONE_TRAILING_SLASHES:
219 if (!dentry_is_directory(cur_dentry)) {
224 case WILDCARD_STATUS_DONE_FULLY:
225 ret = (*ctx->consume_dentry)(cur_dentry,
226 ctx->consume_dentry_ctx);
227 ctx->consume_dentry_count++;
229 case WILDCARD_STATUS_NOT_DONE:
230 ret = expand_wildcard_recursive(cur_dentry, ctx);
237 #if !TCHAR_IS_UTF16LE
244 expand_wildcard_recursive(struct wim_dentry *cur_dentry,
245 struct match_dentry_ctx *ctx)
254 struct wim_dentry *child;
256 w = ctx->wildcard_path;
258 begin = ctx->cur_component_offset + ctx->cur_component_len;
259 while (w[begin] == WIM_PATH_SEPARATOR)
264 while (w[end] != T('\0') && w[end] != WIM_PATH_SEPARATOR)
272 offset_save = ctx->cur_component_offset;
273 len_save = ctx->cur_component_len;
275 ctx->cur_component_offset = begin;
276 ctx->cur_component_len = len;
279 for_dentry_child(child, cur_dentry) {
280 ret = match_dentry(child, ctx);
285 ctx->cur_component_len = len_save;
286 ctx->cur_component_offset = offset_save;
291 /* Expand a wildcard relative to the current WIM image.
294 * WIMStruct whose currently selected image is searched to expand the
297 * Wildcard path to expand, which may contain the '?' and '*' characters.
298 * Path separators must be WIM_PATH_SEPARATOR. Leading path separators are
299 * ignored, whereas one or more trailing path separators indicate that the
300 * wildcard path can only match directories (and not reparse points).
302 * Callback function which will receive each directory entry matched by the
304 * @consume_dentry_ctx
305 * Argument to pass to @consume_dentry.
307 * Zero or more of the following flags:
309 * WILDCARD_FLAG_WARN_IF_NO_MATCH:
310 * Issue a warning if the wildcard does not match any dentries.
312 * WILDCARD_FLAG_ERROR_IF_NO_MATCH:
313 * Issue an error and return WIMLIB_ERR_PATH_DOES_NOT_EXIST if the
314 * wildcard does not match any dentries.
316 * WILDCARD_FLAG_CASE_INSENSITIVE:
317 * Perform the matching case insensitively. Note that this may
318 * cause @wildcard to match multiple dentries, even if it does not
319 * contain wildcard characters.
321 * @return 0 on success; a positive error code on error; or the first nonzero
322 * value returned by @consume_dentry.
325 expand_wildcard(WIMStruct *wim,
326 const tchar *wildcard_path,
327 int (*consume_dentry)(struct wim_dentry *, void *),
328 void *consume_dentry_ctx,
331 struct wim_dentry *root;
334 root = wim_root_dentry(wim);
338 struct match_dentry_ctx ctx = {
339 .consume_dentry = consume_dentry,
340 .consume_dentry_ctx = consume_dentry_ctx,
341 .consume_dentry_count = 0,
342 .wildcard_path = TSTRDUP(wildcard_path),
343 .cur_component_offset = 0,
344 .cur_component_len = 0,
345 .case_insensitive = ((flags & WILDCARD_FLAG_CASE_INSENSITIVE) != 0),
348 if (ctx.wildcard_path == NULL)
349 return WIMLIB_ERR_NOMEM;
351 ret = expand_wildcard_recursive(root, &ctx);
352 FREE(ctx.wildcard_path);
353 if (ret == 0 && ctx.consume_dentry_count == 0)
359 if (flags & WILDCARD_FLAG_WARN_IF_NO_MATCH)
360 WARNING("No matches for wildcard path \"%"TS"\"", wildcard_path);
362 if (flags & WILDCARD_FLAG_ERROR_IF_NO_MATCH) {
363 ERROR("No matches for wildcard path \"%"TS"\"", wildcard_path);
364 ret = WIMLIB_ERR_PATH_DOES_NOT_EXIST;