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)
199 name = cur_dentry->file_name;
200 name_len = cur_dentry->file_name_nbytes;
202 ret = utf16le_to_tstr(cur_dentry->file_name,
203 cur_dentry->file_name_nbytes,
208 name_len /= sizeof(tchar);
210 if (match_wildcard(name,
211 &ctx->wildcard_path[ctx->cur_component_offset],
212 ctx->cur_component_len,
213 ctx->case_insensitive))
215 switch (wildcard_status(&ctx->wildcard_path[
216 ctx->cur_component_offset +
217 ctx->cur_component_len]))
219 case WILDCARD_STATUS_DONE_TRAILING_SLASHES:
220 if (!dentry_is_directory(cur_dentry)) {
225 case WILDCARD_STATUS_DONE_FULLY:
226 ret = (*ctx->consume_dentry)(cur_dentry,
227 ctx->consume_dentry_ctx);
228 ctx->consume_dentry_count++;
230 case WILDCARD_STATUS_NOT_DONE:
231 ret = expand_wildcard_recursive(cur_dentry, ctx);
238 #if !TCHAR_IS_UTF16LE
245 expand_wildcard_recursive(struct wim_dentry *cur_dentry,
246 struct match_dentry_ctx *ctx)
255 struct wim_dentry *child;
257 w = ctx->wildcard_path;
259 begin = ctx->cur_component_offset + ctx->cur_component_len;
260 while (w[begin] == WIM_PATH_SEPARATOR)
265 while (w[end] != T('\0') && w[end] != WIM_PATH_SEPARATOR)
273 offset_save = ctx->cur_component_offset;
274 len_save = ctx->cur_component_len;
276 ctx->cur_component_offset = begin;
277 ctx->cur_component_len = len;
280 for_dentry_child(child, cur_dentry) {
281 ret = match_dentry(child, ctx);
286 ctx->cur_component_len = len_save;
287 ctx->cur_component_offset = offset_save;
292 /* Expand a wildcard relative to the current WIM image.
295 * WIMStruct whose currently selected image is searched to expand the
298 * Wildcard path to expand, which may contain the '?' and '*' characters.
299 * Path separators must be WIM_PATH_SEPARATOR. Leading path separators are
300 * ignored, whereas one or more trailing path separators indicate that the
301 * wildcard path can only match directories (and not reparse points).
303 * Callback function which will receive each directory entry matched by the
305 * @consume_dentry_ctx
306 * Argument to pass to @consume_dentry.
308 * Zero or more of the following flags:
310 * WILDCARD_FLAG_WARN_IF_NO_MATCH:
311 * Issue a warning if the wildcard does not match any dentries.
313 * WILDCARD_FLAG_ERROR_IF_NO_MATCH:
314 * Issue an error and return WIMLIB_ERR_PATH_DOES_NOT_EXIST if the
315 * wildcard does not match any dentries.
317 * WILDCARD_FLAG_CASE_INSENSITIVE:
318 * Perform the matching case insensitively. Note that this may
319 * cause @wildcard to match multiple dentries, even if it does not
320 * contain wildcard characters.
322 * @return 0 on success; a positive error code on error; or the first nonzero
323 * value returned by @consume_dentry.
326 expand_wildcard(WIMStruct *wim,
327 const tchar *wildcard_path,
328 int (*consume_dentry)(struct wim_dentry *, void *),
329 void *consume_dentry_ctx,
332 struct wim_dentry *root;
335 root = wim_root_dentry(wim);
339 struct match_dentry_ctx ctx = {
340 .consume_dentry = consume_dentry,
341 .consume_dentry_ctx = consume_dentry_ctx,
342 .consume_dentry_count = 0,
343 .wildcard_path = TSTRDUP(wildcard_path),
344 .cur_component_offset = 0,
345 .cur_component_len = 0,
346 .case_insensitive = ((flags & WILDCARD_FLAG_CASE_INSENSITIVE) != 0),
349 if (ctx.wildcard_path == NULL)
350 return WIMLIB_ERR_NOMEM;
352 ret = expand_wildcard_recursive(root, &ctx);
353 FREE(ctx.wildcard_path);
354 if (ret == 0 && ctx.consume_dentry_count == 0)
360 if (flags & WILDCARD_FLAG_WARN_IF_NO_MATCH)
361 WARNING("No matches for wildcard path \"%"TS"\"", wildcard_path);
363 if (flags & WILDCARD_FLAG_ERROR_IF_NO_MATCH) {
364 ERROR("No matches for wildcard path \"%"TS"\"", wildcard_path);
365 ret = WIMLIB_ERR_PATH_DOES_NOT_EXIST;