]> wimlib.net Git - wimlib/blob - src/pattern.c
Add a clang-format file
[wimlib] / src / pattern.c
1 /*
2  * pattern.c
3  *
4  * Wildcard pattern matching functions.
5  */
6
7 /*
8  * Copyright (C) 2013, 2015 Eric Biggers
9  *
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
13  * later version.
14  *
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
18  * details.
19  *
20  * You should have received a copy of the GNU Lesser General Public License
21  * along with this file; if not, see https://www.gnu.org/licenses/.
22  */
23
24 #ifdef HAVE_CONFIG_H
25 #  include "config.h"
26 #endif
27
28 #include <ctype.h>
29
30 #include "wimlib/dentry.h"
31 #include "wimlib/encoding.h"
32 #include "wimlib/paths.h"
33 #include "wimlib/pattern.h"
34
35 static bool
36 string_matches_pattern(const tchar *string, const tchar * const string_end,
37                        const tchar *pattern, const tchar * const pattern_end)
38 {
39         for (; string != string_end; string++, pattern++) {
40                 if (pattern == pattern_end)
41                         return false;
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);
47                 }
48                 if (*string != *pattern && *pattern != T('?') &&
49                     !(default_ignore_case &&
50                       totlower(*string) == totlower(*pattern)))
51                         return false;
52         }
53
54         while (pattern != pattern_end && *pattern == T('*'))
55                 pattern++;
56         return pattern == pattern_end;
57 }
58
59 /* Advance past zero or more path separators.  */
60 static const tchar *
61 advance_to_next_component(const tchar *p)
62 {
63         while (*p == WIM_PATH_SEPARATOR)
64                 p++;
65         return p;
66 }
67
68 /* Advance past a nonempty path component.  */
69 static const tchar *
70 advance_through_component(const tchar *p)
71 {
72         do {
73                 p++;
74         } while (*p && *p != WIM_PATH_SEPARATOR);
75         return p;
76 }
77
78 /*
79  * Determine whether a path matches a wildcard pattern.
80  *
81  * @path
82  *      The null-terminated path string to match.
83  * @pattern
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.
89  * @match_flags
90  *      MATCH_* flags, see the flag definitions.
91  *
92  * @path and @pattern can both contain path separators (character
93  * WIM_PATH_SEPARATOR).  Leading and trailing path separators are not
94  * significant, except when determining whether to match only the filename
95  * component as noted above.  The lengths of interior path separator sequences
96  * are not significant.  The '*' and '?' characters act within a single path
97  * component only (they do not match path separators).
98  *
99  * Matching is done with the default case sensitivity behavior.
100  *
101  * Returns %true iff the path matched the pattern.
102  */
103 bool
104 match_path(const tchar *path, const tchar *pattern, int match_flags)
105 {
106         /* Filename only?  */
107         if (*pattern != WIM_PATH_SEPARATOR)
108                 path = path_basename(path);
109
110         for (;;) {
111                 const tchar *path_component_end;
112                 const tchar *pattern_component_end;
113
114                 path = advance_to_next_component(path);
115                 pattern = advance_to_next_component(pattern);
116
117                 /* Is the pattern exhausted?  */
118                 if (!*pattern)
119                         return !*path || (match_flags & MATCH_RECURSIVELY);
120
121                 /* Is the path exhausted (but not the pattern)?  */
122                 if (!*path)
123                         return (match_flags & MATCH_ANCESTORS);
124
125                 path_component_end = advance_through_component(path);
126                 pattern_component_end = advance_through_component(pattern);
127
128                 /* Do the components match?  */
129                 if (!string_matches_pattern(path, path_component_end,
130                                             pattern, pattern_component_end))
131                         return false;
132
133                 path = path_component_end;
134                 pattern = pattern_component_end;
135         }
136 }
137
138 /*
139  * Expand a path pattern in an in-memory tree of dentries.
140  *
141  * @root
142  *      The root of the directory tree in which to expand the pattern.
143  * @pattern
144  *      The path pattern to expand, which may contain the '*' and '?' wildcard
145  *      characters.  Path separators must be WIM_PATH_SEPARATOR.  Leading and
146  *      trailing path separators are ignored.  The default case sensitivity
147  *      behavior is used.
148  * @consume_dentry
149  *      A callback function which will receive each matched directory entry.
150  * @ctx
151  *      Opaque context argument for @consume_dentry.
152  *
153  * @return 0 on success; a positive error code on failure; or the first nonzero
154  * value returned by @consume_dentry.
155  */
156 int
157 expand_path_pattern(struct wim_dentry *root, const tchar *pattern,
158                     int (*consume_dentry)(struct wim_dentry *, void *),
159                     void *ctx)
160 {
161         const tchar *pattern_component_end;
162         struct wim_dentry *child;
163
164         if (!root)
165                 return 0;
166
167         pattern = advance_to_next_component(pattern);
168
169         /* If there are no more components, then 'root' is matched.  */
170         if (!*pattern)
171                 return (*consume_dentry)(root, ctx);
172
173         pattern_component_end = advance_through_component(pattern);
174
175         /* For each child dentry that matches the current pattern component,
176          * recurse with the remainder of the pattern.  */
177         for_dentry_child(child, root) {
178                 const tchar *name;
179                 size_t name_nbytes;
180                 int ret;
181
182                 ret = utf16le_get_tstr(child->d_name, child->d_name_nbytes,
183                                        &name, &name_nbytes);
184                 if (ret)
185                         return ret;
186
187                 if (string_matches_pattern(name, &name[name_nbytes / sizeof(tchar)],
188                                            pattern, pattern_component_end))
189                         ret = expand_path_pattern(child, pattern_component_end,
190                                                   consume_dentry, ctx);
191                 utf16le_put_tstr(name);
192                 if (ret)
193                         return ret;
194         }
195         return 0;
196 }