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,
203 name_len /= sizeof(tchar);
205 if (match_wildcard(name,
206 &ctx->wildcard_path[ctx->cur_component_offset],
207 ctx->cur_component_len,
208 ctx->case_insensitive))
210 switch (wildcard_status(&ctx->wildcard_path[
211 ctx->cur_component_offset +
212 ctx->cur_component_len]))
214 case WILDCARD_STATUS_DONE_TRAILING_SLASHES:
215 if (!dentry_is_directory(cur_dentry)) {
220 case WILDCARD_STATUS_DONE_FULLY:
221 ret = (*ctx->consume_dentry)(cur_dentry,
222 ctx->consume_dentry_ctx);
223 ctx->consume_dentry_count++;
225 case WILDCARD_STATUS_NOT_DONE:
226 ret = expand_wildcard_recursive(cur_dentry, ctx);
233 utf16le_put_tstr(name);
239 expand_wildcard_recursive(struct wim_dentry *cur_dentry,
240 struct match_dentry_ctx *ctx)
249 struct wim_dentry *child;
251 w = ctx->wildcard_path;
253 begin = ctx->cur_component_offset + ctx->cur_component_len;
254 while (w[begin] == WIM_PATH_SEPARATOR)
259 while (w[end] != T('\0') && w[end] != WIM_PATH_SEPARATOR)
267 offset_save = ctx->cur_component_offset;
268 len_save = ctx->cur_component_len;
270 ctx->cur_component_offset = begin;
271 ctx->cur_component_len = len;
274 for_dentry_child(child, cur_dentry) {
275 ret = match_dentry(child, ctx);
280 ctx->cur_component_len = len_save;
281 ctx->cur_component_offset = offset_save;
286 /* Expand a wildcard relative to the current WIM image.
289 * WIMStruct whose currently selected image is searched to expand the
292 * Wildcard path to expand, which may contain the '?' and '*' characters.
293 * Path separators must be WIM_PATH_SEPARATOR. Leading path separators are
294 * ignored, whereas one or more trailing path separators indicate that the
295 * wildcard path can only match directories (and not reparse points).
297 * Callback function which will receive each directory entry matched by the
299 * @consume_dentry_ctx
300 * Argument to pass to @consume_dentry.
302 * Zero or more of the following flags:
304 * WILDCARD_FLAG_WARN_IF_NO_MATCH:
305 * Issue a warning if the wildcard does not match any dentries.
307 * WILDCARD_FLAG_ERROR_IF_NO_MATCH:
308 * Issue an error and return WIMLIB_ERR_PATH_DOES_NOT_EXIST if the
309 * wildcard does not match any dentries.
311 * WILDCARD_FLAG_CASE_INSENSITIVE:
312 * Perform the matching case insensitively. Note that this may
313 * cause @wildcard to match multiple dentries, even if it does not
314 * contain wildcard characters.
316 * @return 0 on success; a positive error code on error; or the first nonzero
317 * value returned by @consume_dentry.
320 expand_wildcard(WIMStruct *wim,
321 const tchar *wildcard_path,
322 int (*consume_dentry)(struct wim_dentry *, void *),
323 void *consume_dentry_ctx,
326 struct wim_dentry *root;
329 root = wim_root_dentry(wim);
333 struct match_dentry_ctx ctx = {
334 .consume_dentry = consume_dentry,
335 .consume_dentry_ctx = consume_dentry_ctx,
336 .consume_dentry_count = 0,
337 .wildcard_path = TSTRDUP(wildcard_path),
338 .cur_component_offset = 0,
339 .cur_component_len = 0,
340 .case_insensitive = ((flags & WILDCARD_FLAG_CASE_INSENSITIVE) != 0),
343 if (ctx.wildcard_path == NULL)
344 return WIMLIB_ERR_NOMEM;
346 ret = expand_wildcard_recursive(root, &ctx);
347 FREE(ctx.wildcard_path);
348 if (ret == 0 && ctx.consume_dentry_count == 0)
354 if (flags & WILDCARD_FLAG_WARN_IF_NO_MATCH)
355 WARNING("No matches for wildcard path \"%"TS"\"", wildcard_path);
357 if (flags & WILDCARD_FLAG_ERROR_IF_NO_MATCH) {
358 ERROR("No matches for wildcard path \"%"TS"\"", wildcard_path);
359 ret = WIMLIB_ERR_PATH_DOES_NOT_EXIST;