Branch data Line data Source code
1 : : /* GLIB - Library of useful routines for C programming
2 : : * Copyright (C) 1995-1997, 1999 Peter Mattis, Red Hat, Inc.
3 : : *
4 : : * SPDX-License-Identifier: LGPL-2.1-or-later
5 : : *
6 : : * This library is free software; you can redistribute it and/or
7 : : * modify it under the terms of the GNU Lesser General Public
8 : : * License as published by the Free Software Foundation; either
9 : : * version 2.1 of the License, or (at your option) any later version.
10 : : *
11 : : * This library is distributed in the hope that it will be useful,
12 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 : : * Lesser General Public License for more details.
15 : : *
16 : : * You should have received a copy of the GNU Lesser General Public
17 : : * License along with this library; if not, see <http://www.gnu.org/licenses/>.
18 : : */
19 : :
20 : : #include "config.h"
21 : :
22 : : #include <string.h>
23 : :
24 : : #include "gpattern.h"
25 : :
26 : : #include "gmacros.h"
27 : : #include "gmem.h"
28 : : #include "gmessages.h"
29 : : #include "gstrfuncs.h"
30 : : #include "gunicode.h"
31 : : #include "gutils.h"
32 : :
33 : : /**
34 : : * GPatternSpec:
35 : : *
36 : : * A `GPatternSpec` struct is the ‘compiled’ form of a glob-style pattern.
37 : : *
38 : : * The [func@GLib.pattern_match_simple] and [method@GLib.PatternSpec.match] functions
39 : : * match a string against a pattern containing `*` and `?` wildcards with similar
40 : : * semantics as the standard `glob()` function: `*` matches an arbitrary,
41 : : * possibly empty, string, `?` matches an arbitrary character.
42 : : *
43 : : * Note that in contrast to [`glob()`](man:glob(3)), the `/` character can be
44 : : * matched by the wildcards, there are no `[…]` character ranges and `*` and `?`
45 : : * can not be escaped to include them literally in a pattern.
46 : : *
47 : : * When multiple strings must be matched against the same pattern, it is better
48 : : * to compile the pattern to a [struct@GLib.PatternSpec] using
49 : : * [ctor@GLib.PatternSpec.new] and use [method@GLib.PatternSpec.match_string]
50 : : * instead of [func@GLib.pattern_match_simple]. This avoids the overhead of repeated
51 : : * pattern compilation.
52 : : */
53 : :
54 : : /* keep enum and structure of gpattern.c and patterntest.c in sync */
55 : : typedef enum
56 : : {
57 : : G_MATCH_ALL, /* "*A?A*" */
58 : : G_MATCH_ALL_TAIL, /* "*A?AA" */
59 : : G_MATCH_HEAD, /* "AAAA*" */
60 : : G_MATCH_TAIL, /* "*AAAA" */
61 : : G_MATCH_EXACT, /* "AAAAA" */
62 : : G_MATCH_LAST
63 : : } GMatchType;
64 : :
65 : : struct _GPatternSpec
66 : : {
67 : : GMatchType match_type;
68 : : size_t pattern_length;
69 : : size_t min_length;
70 : : size_t max_length;
71 : : gchar *pattern;
72 : : };
73 : :
74 : :
75 : : /* --- functions --- */
76 : : static inline gboolean
77 : 11093 : g_pattern_ph_match (const gchar *match_pattern,
78 : : const gchar *match_string,
79 : : gboolean *wildcard_reached_p)
80 : : {
81 : : const gchar *pattern, *string;
82 : : gchar ch;
83 : :
84 : 11093 : pattern = match_pattern;
85 : 11093 : string = match_string;
86 : :
87 : 11093 : ch = *pattern;
88 : 11093 : pattern++;
89 : 95763 : while (ch)
90 : : {
91 : 95687 : switch (ch)
92 : : {
93 : 95 : case '?':
94 : 95 : if (!*string)
95 : 5 : return FALSE;
96 : 90 : string = g_utf8_next_char (string);
97 : 90 : break;
98 : :
99 : 7509 : case '*':
100 : 7509 : *wildcard_reached_p = TRUE;
101 : : do
102 : : {
103 : 7509 : ch = *pattern;
104 : 7509 : pattern++;
105 : 7509 : if (ch == '?')
106 : : {
107 : 0 : if (!*string)
108 : 0 : return FALSE;
109 : 0 : string = g_utf8_next_char (string);
110 : : }
111 : : }
112 : 7509 : while (ch == '*' || ch == '?');
113 : 7509 : if (!ch)
114 : 2801 : return TRUE;
115 : : do
116 : : {
117 : 8211 : gboolean next_wildcard_reached = FALSE;
118 : 156158 : while (ch != *string)
119 : : {
120 : 148135 : if (!*string)
121 : 4708 : return FALSE;
122 : 147947 : string = g_utf8_next_char (string);
123 : : }
124 : 8023 : string++;
125 : 8023 : if (g_pattern_ph_match (pattern, string, &next_wildcard_reached))
126 : 4513 : return TRUE;
127 : 3510 : if (next_wildcard_reached)
128 : : /* the forthcoming pattern substring up to the next wildcard has
129 : : * been matched, but a mismatch occurred for the rest of the
130 : : * pattern, following the next wildcard.
131 : : * there's no need to advance the current match position any
132 : : * further if the rest pattern will not match.
133 : : */
134 : 7 : return FALSE;
135 : : }
136 : 3503 : while (*string);
137 : 0 : break;
138 : :
139 : 88083 : default:
140 : 88083 : if (ch == *string)
141 : 84580 : string++;
142 : : else
143 : 3503 : return FALSE;
144 : 84580 : break;
145 : : }
146 : :
147 : 84670 : ch = *pattern;
148 : 84670 : pattern++;
149 : : }
150 : :
151 : 76 : return *string == 0;
152 : : }
153 : :
154 : : /**
155 : : * g_pattern_spec_match:
156 : : * @pspec: a #GPatternSpec
157 : : * @string_length: the length of @string (in bytes, i.e. `strlen()`,
158 : : * not [func@GLib.utf8_strlen])
159 : : * @string: the UTF-8 encoded string to match
160 : : * @string_reversed: (nullable): the reverse of @string
161 : : *
162 : : * Matches a string against a compiled pattern.
163 : : *
164 : : * Passing the correct
165 : : * length of the string given is mandatory. The reversed string can be
166 : : * omitted by passing `NULL`, this is more efficient if the reversed
167 : : * version of the string to be matched is not at hand, as
168 : : * [method@GLib.PatternSpec.match] will only construct it if the compiled pattern
169 : : * requires reverse matches.
170 : : *
171 : : * Note that, if the user code will (possibly) match a string against a
172 : : * multitude of patterns containing wildcards, chances are high that
173 : : * some patterns will require a reversed string. In this case, it’s
174 : : * more efficient to provide the reversed string to avoid multiple
175 : : * constructions thereof in the various calls to [method@GLib.PatternSpec.match].
176 : : *
177 : : * Note also that the reverse of a UTF-8 encoded string can in general
178 : : * not be obtained by [func@GLib.strreverse]. This works only if the string
179 : : * does not contain any multibyte characters. GLib offers the
180 : : * [func@GLib.utf8_strreverse] function to reverse UTF-8 encoded strings.
181 : : *
182 : : * Returns: %TRUE if @string matches @pspec
183 : : *
184 : : * Since: 2.70
185 : : **/
186 : : gboolean
187 : 3254 : g_pattern_spec_match (GPatternSpec *pspec,
188 : : gsize string_length,
189 : : const gchar *string,
190 : : const gchar *string_reversed)
191 : : {
192 : 3254 : g_return_val_if_fail (pspec != NULL, FALSE);
193 : 3254 : g_return_val_if_fail (string != NULL, FALSE);
194 : :
195 : 3254 : if (string_length < pspec->min_length ||
196 : 3185 : string_length > pspec->max_length)
197 : 74 : return FALSE;
198 : :
199 : 3180 : switch (pspec->match_type)
200 : : {
201 : : gboolean dummy;
202 : 2942 : case G_MATCH_ALL:
203 : 2942 : return g_pattern_ph_match (pspec->pattern, string, &dummy);
204 : 128 : case G_MATCH_ALL_TAIL:
205 : 128 : if (string_reversed)
206 : 44 : return g_pattern_ph_match (pspec->pattern, string_reversed, &dummy);
207 : : else
208 : : {
209 : : gboolean result;
210 : : gchar *tmp;
211 : 84 : tmp = g_utf8_strreverse (string, string_length);
212 : 84 : result = g_pattern_ph_match (pspec->pattern, tmp, &dummy);
213 : 84 : g_free (tmp);
214 : 84 : return result;
215 : : }
216 : 17 : case G_MATCH_HEAD:
217 : 17 : if (pspec->pattern_length == string_length)
218 : 5 : return strcmp (pspec->pattern, string) == 0;
219 : 12 : else if (pspec->pattern_length)
220 : 12 : return strncmp (pspec->pattern, string, pspec->pattern_length) == 0;
221 : : else
222 : 0 : return TRUE;
223 : 44 : case G_MATCH_TAIL:
224 : 44 : if (pspec->pattern_length)
225 : 39 : return strcmp (pspec->pattern, string + (string_length - pspec->pattern_length)) == 0;
226 : : else
227 : 5 : return TRUE;
228 : 49 : case G_MATCH_EXACT:
229 : 49 : if (pspec->pattern_length != string_length)
230 : 0 : return FALSE;
231 : : else
232 : 49 : return strcmp (pspec->pattern, string) == 0;
233 : 0 : default:
234 : 0 : g_return_val_if_fail (pspec->match_type < G_MATCH_LAST, FALSE);
235 : 0 : return FALSE;
236 : : }
237 : : }
238 : :
239 : : /**
240 : : * g_pattern_match: (skip)
241 : : * @pspec: a #GPatternSpec
242 : : * @string_length: the length of @string (in bytes, i.e. `strlen()`,
243 : : * not [func@GLib.utf8_strlen])
244 : : * @string: the UTF-8 encoded string to match
245 : : * @string_reversed: (nullable): the reverse of @string
246 : : *
247 : : * Matches a string against a compiled pattern.
248 : : *
249 : : * Passing the correct
250 : : * length of the string given is mandatory. The reversed string can be
251 : : * omitted by passing `NULL`, this is more efficient if the reversed
252 : : * version of the string to be matched is not at hand, as
253 : : * `g_pattern_match()` will only construct it if the compiled pattern
254 : : * requires reverse matches.
255 : : *
256 : : * Note that, if the user code will (possibly) match a string against a
257 : : * multitude of patterns containing wildcards, chances are high that
258 : : * some patterns will require a reversed string. In this case, it’s
259 : : * more efficient to provide the reversed string to avoid multiple
260 : : * constructions thereof in the various calls to `g_pattern_match()`.
261 : : *
262 : : * Note also that the reverse of a UTF-8 encoded string can in general
263 : : * not be obtained by [func@GLib.strreverse]. This works only if the string
264 : : * does not contain any multibyte characters. GLib offers the
265 : : * [func@GLib.utf8_strreverse] function to reverse UTF-8 encoded strings.
266 : : *
267 : : * Returns: %TRUE if @string matches @pspec
268 : : * Deprecated: 2.70: Use [method@GLib.PatternSpec.match] instead
269 : : **/
270 : : gboolean
271 : 51 : g_pattern_match (GPatternSpec *pspec,
272 : : guint string_length,
273 : : const gchar *string,
274 : : const gchar *string_reversed)
275 : : {
276 : 51 : return g_pattern_spec_match (pspec, string_length, string, string_reversed);
277 : : }
278 : :
279 : : /**
280 : : * g_pattern_spec_new:
281 : : * @pattern: a zero-terminated UTF-8 encoded string
282 : : *
283 : : * Compiles a pattern to a [type@GLib.PatternSpec].
284 : : *
285 : : * Returns: (transfer full): a newly-allocated [type@GLib.PatternSpec]
286 : : **/
287 : : GPatternSpec*
288 : 3153 : g_pattern_spec_new (const gchar *pattern)
289 : : {
290 : : GPatternSpec *pspec;
291 : 3153 : gboolean seen_joker = FALSE, seen_wildcard = FALSE, more_wildcards = FALSE;
292 : 3153 : size_t hw_pos = 0, tw_pos = 0, hj_pos = 0, tj_pos = 0;
293 : 3153 : gboolean hw_pos_set = FALSE, hj_pos_set = FALSE;
294 : 3153 : gboolean follows_wildcard = FALSE;
295 : 3153 : size_t pending_jokers = 0;
296 : : const gchar *s;
297 : : gchar *d;
298 : : size_t i;
299 : :
300 : 3153 : g_return_val_if_fail (pattern != NULL, NULL);
301 : :
302 : : /* canonicalize pattern and collect necessary stats */
303 : 3153 : pspec = g_new (GPatternSpec, 1);
304 : 3153 : pspec->pattern_length = strlen (pattern);
305 : 3153 : pspec->min_length = 0;
306 : 3153 : pspec->max_length = 0;
307 : 3153 : pspec->pattern = g_new (gchar, pspec->pattern_length + 1);
308 : 3153 : d = pspec->pattern;
309 : 102319 : for (i = 0, s = pattern; *s != 0; s++)
310 : : {
311 : 99166 : switch (*s)
312 : : {
313 : 7763 : case '*':
314 : 7763 : if (follows_wildcard) /* compress multiple wildcards */
315 : : {
316 : 33 : pspec->pattern_length--;
317 : 33 : continue;
318 : : }
319 : 7730 : follows_wildcard = TRUE;
320 : 7730 : if (!hw_pos_set)
321 : : {
322 : 3078 : hw_pos = i;
323 : 3078 : hw_pos_set = TRUE;
324 : : }
325 : 7730 : tw_pos = i;
326 : 7730 : break;
327 : 87 : case '?':
328 : 87 : pending_jokers++;
329 : 87 : pspec->min_length++;
330 : 87 : pspec->max_length += 4; /* maximum UTF-8 character length */
331 : 87 : continue;
332 : 91316 : default:
333 : 91382 : for (; pending_jokers; pending_jokers--, i++) {
334 : 66 : *d++ = '?';
335 : 66 : if (!hj_pos_set)
336 : : {
337 : 58 : hj_pos = i;
338 : 58 : hj_pos_set = TRUE;
339 : : }
340 : 66 : tj_pos = i;
341 : : }
342 : 91316 : follows_wildcard = FALSE;
343 : 91316 : pspec->min_length++;
344 : 91316 : pspec->max_length++;
345 : 91316 : break;
346 : : }
347 : 99046 : *d++ = *s;
348 : 99046 : i++;
349 : : }
350 : 3174 : for (; pending_jokers; pending_jokers--) {
351 : 21 : *d++ = '?';
352 : 21 : if (!hj_pos_set)
353 : : {
354 : 15 : hj_pos = i;
355 : 15 : hj_pos_set = TRUE;
356 : : }
357 : 21 : tj_pos = i;
358 : : }
359 : 3153 : *d++ = 0;
360 : 3153 : seen_joker = hj_pos_set;
361 : 3153 : seen_wildcard = hw_pos_set;
362 : 3153 : more_wildcards = seen_wildcard && hw_pos != tw_pos;
363 : 3153 : if (seen_wildcard)
364 : 3078 : pspec->max_length = G_MAXSIZE;
365 : :
366 : : /* special case sole head/tail wildcard or exact matches */
367 : 3153 : if (!seen_joker && !more_wildcards)
368 : : {
369 : 114 : if (pspec->pattern[0] == '*')
370 : : {
371 : 30 : pspec->match_type = G_MATCH_TAIL;
372 : 30 : memmove (pspec->pattern, pspec->pattern + 1, --pspec->pattern_length);
373 : 30 : pspec->pattern[pspec->pattern_length] = 0;
374 : 30 : return pspec;
375 : : }
376 : 84 : if (pspec->pattern_length > 0 &&
377 : 63 : pspec->pattern[pspec->pattern_length - 1] == '*')
378 : : {
379 : 18 : pspec->match_type = G_MATCH_HEAD;
380 : 18 : pspec->pattern[--pspec->pattern_length] = 0;
381 : 18 : return pspec;
382 : : }
383 : 66 : if (!seen_wildcard)
384 : : {
385 : 50 : pspec->match_type = G_MATCH_EXACT;
386 : 50 : return pspec;
387 : : }
388 : : }
389 : :
390 : : /* now just need to distinguish between head or tail match start */
391 : 3055 : tw_pos = pspec->pattern_length - 1 - tw_pos; /* last pos to tail distance */
392 : 3055 : tj_pos = pspec->pattern_length - 1 - tj_pos; /* last pos to tail distance */
393 : 3055 : if (seen_wildcard)
394 : 3030 : pspec->match_type = tw_pos > hw_pos ? G_MATCH_ALL_TAIL : G_MATCH_ALL;
395 : : else /* seen_joker */
396 : 25 : pspec->match_type = tj_pos > hj_pos ? G_MATCH_ALL_TAIL : G_MATCH_ALL;
397 : 3055 : if (pspec->match_type == G_MATCH_ALL_TAIL) {
398 : 94 : gchar *tmp = pspec->pattern;
399 : 94 : pspec->pattern = g_utf8_strreverse (pspec->pattern, pspec->pattern_length);
400 : 94 : g_free (tmp);
401 : : }
402 : 3055 : return pspec;
403 : : }
404 : :
405 : : /**
406 : : * g_pattern_spec_copy:
407 : : * @pspec: a #GPatternSpec
408 : : *
409 : : * Copies @pspec in a new [type@GLib.PatternSpec].
410 : : *
411 : : * Returns: (transfer full): a copy of @pspec.
412 : : *
413 : : * Since: 2.70
414 : : **/
415 : : GPatternSpec *
416 : 15 : g_pattern_spec_copy (GPatternSpec *pspec)
417 : : {
418 : : GPatternSpec *pspec_copy;
419 : :
420 : 15 : g_return_val_if_fail (pspec != NULL, NULL);
421 : :
422 : 15 : pspec_copy = g_new (GPatternSpec, 1);
423 : 15 : *pspec_copy = *pspec;
424 : 15 : pspec_copy->pattern = g_strndup (pspec->pattern, pspec->pattern_length);
425 : :
426 : 15 : return pspec_copy;
427 : : }
428 : :
429 : : /**
430 : : * g_pattern_spec_free:
431 : : * @pspec: a #GPatternSpec
432 : : *
433 : : * Frees the memory allocated for the [type@GLib.PatternSpec].
434 : : **/
435 : : void
436 : 3168 : g_pattern_spec_free (GPatternSpec *pspec)
437 : : {
438 : 3168 : g_return_if_fail (pspec != NULL);
439 : :
440 : 3168 : g_free (pspec->pattern);
441 : 3168 : g_free (pspec);
442 : : }
443 : :
444 : : /**
445 : : * g_pattern_spec_equal:
446 : : * @pspec1: a #GPatternSpec
447 : : * @pspec2: another #GPatternSpec
448 : : *
449 : : * Compares two compiled pattern specs and returns whether they will
450 : : * match the same set of strings.
451 : : *
452 : : * Returns: Whether the compiled patterns are equal
453 : : **/
454 : : gboolean
455 : 12 : g_pattern_spec_equal (GPatternSpec *pspec1,
456 : : GPatternSpec *pspec2)
457 : : {
458 : 12 : g_return_val_if_fail (pspec1 != NULL, FALSE);
459 : 12 : g_return_val_if_fail (pspec2 != NULL, FALSE);
460 : :
461 : 22 : return (pspec1->pattern_length == pspec2->pattern_length &&
462 : 22 : pspec1->match_type == pspec2->match_type &&
463 : 10 : strcmp (pspec1->pattern, pspec2->pattern) == 0);
464 : : }
465 : :
466 : : /**
467 : : * g_pattern_spec_match_string:
468 : : * @pspec: a #GPatternSpec
469 : : * @string: the UTF-8 encoded string to match
470 : : *
471 : : * Matches a string against a compiled pattern.
472 : : *
473 : : * If the string is to be
474 : : * matched against more than one pattern, consider using
475 : : * [method@GLib.PatternSpec.match] instead while supplying the reversed string.
476 : : *
477 : : * Returns: %TRUE if @string matches @pspec
478 : : *
479 : : * Since: 2.70
480 : : **/
481 : : gboolean
482 : 102 : g_pattern_spec_match_string (GPatternSpec *pspec,
483 : : const gchar *string)
484 : : {
485 : 102 : g_return_val_if_fail (pspec != NULL, FALSE);
486 : 102 : g_return_val_if_fail (string != NULL, FALSE);
487 : :
488 : 102 : return g_pattern_spec_match (pspec, strlen (string), string, NULL);
489 : : }
490 : :
491 : : /**
492 : : * g_pattern_match_string: (skip)
493 : : * @pspec: a #GPatternSpec
494 : : * @string: the UTF-8 encoded string to match
495 : : *
496 : : * Matches a string against a compiled pattern.
497 : : *
498 : : * If the string is to be
499 : : * matched against more than one pattern, consider using
500 : : * [method@GLib.PatternSpec.match] instead while supplying the reversed string.
501 : : *
502 : : * Returns: %TRUE if @string matches @pspec
503 : : * Deprecated: 2.70: Use [method@GLib.PatternSpec.match_string] instead
504 : : **/
505 : : gboolean
506 : 51 : g_pattern_match_string (GPatternSpec *pspec,
507 : : const gchar *string)
508 : : {
509 : 51 : return g_pattern_spec_match_string (pspec, string);
510 : : }
511 : :
512 : : /**
513 : : * g_pattern_match_simple:
514 : : * @pattern: the UTF-8 encoded pattern
515 : : * @string: the UTF-8 encoded string to match
516 : : *
517 : : * Matches a string against a pattern given as a string.
518 : : *
519 : : * If this
520 : : * function is to be called in a loop, it’s more efficient to compile
521 : : * the pattern once with [ctor@GLib.PatternSpec.new] and call
522 : : * [method@GLib.PatternSpec.match_string] repeatedly.
523 : : *
524 : : * Returns: %TRUE if @string matches @pspec
525 : : **/
526 : : gboolean
527 : 3050 : g_pattern_match_simple (const gchar *pattern,
528 : : const gchar *string)
529 : : {
530 : : GPatternSpec *pspec;
531 : : gboolean ergo;
532 : :
533 : 3050 : g_return_val_if_fail (pattern != NULL, FALSE);
534 : 3050 : g_return_val_if_fail (string != NULL, FALSE);
535 : :
536 : 3050 : pspec = g_pattern_spec_new (pattern);
537 : 3050 : ergo = g_pattern_spec_match (pspec, strlen (string), string, NULL);
538 : 3050 : g_pattern_spec_free (pspec);
539 : :
540 : 3050 : return ergo;
541 : : }
|
