1 /* GLIB - Library of useful routines for C programming
2 * Copyright (C) 1995-1997, 1999 Peter Mattis, Red Hat, Inc.
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the License, or (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library; if not, write to the
16 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17 * Boston, MA 02111-1307, USA.
18 */
19
20 #include "config.h"
21
22 #include <string.h>
23
24 #include "gpattern.h"
25
26 #include "gmacros.h"
27 #include "gmessages.h"
28 #include "gmem.h"
29 #include "gunicode.h"
30 #include "gutils.h"
31 #include "galias.h"
32
33 /* keep enum and structure of gpattern.c and patterntest.c in sync */
34 typedef enum
35 {
36 G_MATCH_ALL, /* "*A?A*" */
37 G_MATCH_ALL_TAIL, /* "*A?AA" */
38 G_MATCH_HEAD, /* "AAAA*" */
39 G_MATCH_TAIL, /* "*AAAA" */
40 G_MATCH_EXACT, /* "AAAAA" */
41 G_MATCH_LAST
42 } GMatchType;
43
44 struct _GPatternSpec
45 {
46 GMatchType match_type;
47 guint pattern_length;
48 guint min_length;
49 guint max_length;
50 gchar *pattern;
51 };
52
53
54 /* --- functions --- */
55 static inline gboolean
g_pattern_ph_match(const gchar * match_pattern,const gchar * match_string,gboolean * wildcard_reached_p)56 g_pattern_ph_match (const gchar *match_pattern,
57 const gchar *match_string,
58 gboolean *wildcard_reached_p)
59 {
60 register const gchar *pattern, *string;
61 register gchar ch;
62
63 pattern = match_pattern;
64 string = match_string;
65
66 ch = *pattern;
67 pattern++;
68 while (ch)
69 {
70 switch (ch)
71 {
72 case '?':
73 if (!*string)
74 return FALSE;
75 string = g_utf8_next_char (string);
76 break;
77
78 case '*':
79 *wildcard_reached_p = TRUE;
80 do
81 {
82 ch = *pattern;
83 pattern++;
84 if (ch == '?')
85 {
86 if (!*string)
87 return FALSE;
88 string = g_utf8_next_char (string);
89 }
90 }
91 while (ch == '*' || ch == '?');
92 if (!ch)
93 return TRUE;
94 do
95 {
96 gboolean next_wildcard_reached = FALSE;
97 while (ch != *string)
98 {
99 if (!*string)
100 return FALSE;
101 string = g_utf8_next_char (string);
102 }
103 string++;
104 if (g_pattern_ph_match (pattern, string, &next_wildcard_reached))
105 return TRUE;
106 if (next_wildcard_reached)
107 /* the forthcoming pattern substring up to the next wildcard has
108 * been matched, but a mismatch occoured for the rest of the
109 * pattern, following the next wildcard.
110 * there's no need to advance the current match position any
111 * further if the rest pattern will not match.
112 */
113 return FALSE;
114 }
115 while (*string);
116 break;
117
118 default:
119 if (ch == *string)
120 string++;
121 else
122 return FALSE;
123 break;
124 }
125
126 ch = *pattern;
127 pattern++;
128 }
129
130 return *string == 0;
131 }
132
133 gboolean
g_pattern_match(GPatternSpec * pspec,guint string_length,const gchar * string,const gchar * string_reversed)134 g_pattern_match (GPatternSpec *pspec,
135 guint string_length,
136 const gchar *string,
137 const gchar *string_reversed)
138 {
139 g_return_val_if_fail (pspec != NULL, FALSE);
140 g_return_val_if_fail (string != NULL, FALSE);
141
142 if (string_length < pspec->min_length ||
143 string_length > pspec->max_length)
144 return FALSE;
145
146 switch (pspec->match_type)
147 {
148 gboolean dummy;
149 case G_MATCH_ALL:
150 return g_pattern_ph_match (pspec->pattern, string, &dummy);
151 case G_MATCH_ALL_TAIL:
152 if (string_reversed)
153 return g_pattern_ph_match (pspec->pattern, string_reversed, &dummy);
154 else
155 {
156 gboolean result;
157 gchar *tmp;
158 tmp = g_utf8_strreverse (string, string_length);
159 result = g_pattern_ph_match (pspec->pattern, tmp, &dummy);
160 g_free (tmp);
161 return result;
162 }
163 case G_MATCH_HEAD:
164 if (pspec->pattern_length == string_length)
165 return strcmp (pspec->pattern, string) == 0;
166 else if (pspec->pattern_length)
167 return strncmp (pspec->pattern, string, pspec->pattern_length) == 0;
168 else
169 return TRUE;
170 case G_MATCH_TAIL:
171 if (pspec->pattern_length)
172 return strcmp (pspec->pattern, string + (string_length - pspec->pattern_length)) == 0;
173 else
174 return TRUE;
175 case G_MATCH_EXACT:
176 if (pspec->pattern_length != string_length)
177 return FALSE;
178 else
179 return strcmp (pspec->pattern, string) == 0;
180 default:
181 g_return_val_if_fail (pspec->match_type < G_MATCH_LAST, FALSE);
182 return FALSE;
183 }
184 }
185
186 GPatternSpec*
g_pattern_spec_new(const gchar * pattern)187 g_pattern_spec_new (const gchar *pattern)
188 {
189 GPatternSpec *pspec;
190 gboolean seen_joker = FALSE, seen_wildcard = FALSE, more_wildcards = FALSE;
191 gint hw_pos = -1, tw_pos = -1, hj_pos = -1, tj_pos = -1;
192 gboolean follows_wildcard = FALSE;
193 guint pending_jokers = 0;
194 const gchar *s;
195 gchar *d;
196 guint i;
197
198 g_return_val_if_fail (pattern != NULL, NULL);
199
200 /* canonicalize pattern and collect necessary stats */
201 pspec = g_new (GPatternSpec, 1);
202 pspec->pattern_length = strlen (pattern);
203 pspec->min_length = 0;
204 pspec->max_length = 0;
205 pspec->pattern = g_new (gchar, pspec->pattern_length + 1);
206 d = pspec->pattern;
207 for (i = 0, s = pattern; *s != 0; s++)
208 {
209 switch (*s)
210 {
211 case '*':
212 if (follows_wildcard) /* compress multiple wildcards */
213 {
214 pspec->pattern_length--;
215 continue;
216 }
217 follows_wildcard = TRUE;
218 if (hw_pos < 0)
219 hw_pos = i;
220 tw_pos = i;
221 break;
222 case '?':
223 pending_jokers++;
224 pspec->min_length++;
225 pspec->max_length += 4; /* maximum UTF-8 character length */
226 continue;
227 default:
228 for (; pending_jokers; pending_jokers--, i++) {
229 *d++ = '?';
230 if (hj_pos < 0)
231 hj_pos = i;
232 tj_pos = i;
233 }
234 follows_wildcard = FALSE;
235 pspec->min_length++;
236 pspec->max_length++;
237 break;
238 }
239 *d++ = *s;
240 i++;
241 }
242 for (; pending_jokers; pending_jokers--) {
243 *d++ = '?';
244 if (hj_pos < 0)
245 hj_pos = i;
246 tj_pos = i;
247 }
248 *d++ = 0;
249 seen_joker = hj_pos >= 0;
250 seen_wildcard = hw_pos >= 0;
251 more_wildcards = seen_wildcard && hw_pos != tw_pos;
252 if (seen_wildcard)
253 pspec->max_length = G_MAXUINT;
254
255 /* special case sole head/tail wildcard or exact matches */
256 if (!seen_joker && !more_wildcards)
257 {
258 if (pspec->pattern[0] == '*')
259 {
260 pspec->match_type = G_MATCH_TAIL;
261 memmove (pspec->pattern, pspec->pattern + 1, --pspec->pattern_length);
262 pspec->pattern[pspec->pattern_length] = 0;
263 return pspec;
264 }
265 if (pspec->pattern_length > 0 &&
266 pspec->pattern[pspec->pattern_length - 1] == '*')
267 {
268 pspec->match_type = G_MATCH_HEAD;
269 pspec->pattern[--pspec->pattern_length] = 0;
270 return pspec;
271 }
272 if (!seen_wildcard)
273 {
274 pspec->match_type = G_MATCH_EXACT;
275 return pspec;
276 }
277 }
278
279 /* now just need to distinguish between head or tail match start */
280 tw_pos = pspec->pattern_length - 1 - tw_pos; /* last pos to tail distance */
281 tj_pos = pspec->pattern_length - 1 - tj_pos; /* last pos to tail distance */
282 if (seen_wildcard)
283 pspec->match_type = tw_pos > hw_pos ? G_MATCH_ALL_TAIL : G_MATCH_ALL;
284 else /* seen_joker */
285 pspec->match_type = tj_pos > hj_pos ? G_MATCH_ALL_TAIL : G_MATCH_ALL;
286 if (pspec->match_type == G_MATCH_ALL_TAIL) {
287 gchar *tmp = pspec->pattern;
288 pspec->pattern = g_utf8_strreverse (pspec->pattern, pspec->pattern_length);
289 g_free (tmp);
290 }
291 return pspec;
292 }
293
294 void
g_pattern_spec_free(GPatternSpec * pspec)295 g_pattern_spec_free (GPatternSpec *pspec)
296 {
297 g_return_if_fail (pspec != NULL);
298
299 g_free (pspec->pattern);
300 g_free (pspec);
301 }
302
303 gboolean
g_pattern_spec_equal(GPatternSpec * pspec1,GPatternSpec * pspec2)304 g_pattern_spec_equal (GPatternSpec *pspec1,
305 GPatternSpec *pspec2)
306 {
307 g_return_val_if_fail (pspec1 != NULL, FALSE);
308 g_return_val_if_fail (pspec2 != NULL, FALSE);
309
310 return (pspec1->pattern_length == pspec2->pattern_length &&
311 pspec1->match_type == pspec2->match_type &&
312 strcmp (pspec1->pattern, pspec2->pattern) == 0);
313 }
314
315 gboolean
g_pattern_match_string(GPatternSpec * pspec,const gchar * string)316 g_pattern_match_string (GPatternSpec *pspec,
317 const gchar *string)
318 {
319 g_return_val_if_fail (pspec != NULL, FALSE);
320 g_return_val_if_fail (string != NULL, FALSE);
321
322 return g_pattern_match (pspec, strlen (string), string, NULL);
323 }
324
325 gboolean
g_pattern_match_simple(const gchar * pattern,const gchar * string)326 g_pattern_match_simple (const gchar *pattern,
327 const gchar *string)
328 {
329 GPatternSpec *pspec;
330 gboolean ergo;
331
332 g_return_val_if_fail (pattern != NULL, FALSE);
333 g_return_val_if_fail (string != NULL, FALSE);
334
335 pspec = g_pattern_spec_new (pattern);
336 ergo = g_pattern_match (pspec, strlen (string), string, NULL);
337 g_pattern_spec_free (pspec);
338
339 return ergo;
340 }
341
342 #define __G_PATTERN_C__
343 #include "galiasdef.c"
344