applied significant recursion complexity optimization, based on a patch
[platform/upstream/glib.git] / glib / gpattern.c
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
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
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*
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
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
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
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
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"