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, see <http://www.gnu.org/licenses/>.
  16  */
  17
  18 #include "config.h"
  19
  20 #include <string.h>
  21
  22 #include "gpattern.h"
  23
  24 #include "gmacros.h"
  25 #include "gmessages.h"
  26 #include "gmem.h"
  27 #include "gunicode.h"
  28 #include "gutils.h"
  29
  30 /**
  31  * SECTION:patterns
  32  * @title: Glob-style pattern matching
  33  * @short_description: matches strings against patterns containing '*'
  34  *                     (wildcard) and '?' (joker)
  35  *
  36  * The <function>g_pattern_match*</function> functions match a string
  37  * against a pattern containing '*' and '?' wildcards with similar
  38  * semantics as the standard glob() function: '*' matches an arbitrary,
  39  * possibly empty, string, '?' matches an arbitrary character.
  40  *
  41  * Note that in contrast to glob(), the '/' character
  42  * <emphasis>can</emphasis> be matched by the wildcards, there are no
  43  * '[...]' character ranges and '*' and '?' can
  44  * <emphasis>not</emphasis> be escaped to include them literally in a
  45  * pattern.
  46  *
  47  * When multiple strings must be matched against the same pattern, it
  48  * is better to compile the pattern to a #GPatternSpec using
  49  * g_pattern_spec_new() and use g_pattern_match_string() instead of
  50  * g_pattern_match_simple(). This avoids the overhead of repeated
  51  * pattern compilation.
  52  **/
  53
  54 /**
  55  * GPatternSpec:
  56  *
  57  * A #GPatternSpec-struct is the 'compiled' form of a pattern. This
  58  * structure is opaque and its fields cannot be accessed directly.
  59  */
  60
  61 /* keep enum and structure of gpattern.c and patterntest.c in sync */
  62 typedef enum
  63 {
  64   G_MATCH_ALL,       /* "*A?A*" */
  65   G_MATCH_ALL_TAIL,  /* "*A?AA" */
  66   G_MATCH_HEAD,      /* "AAAA*" */
  67   G_MATCH_TAIL,      /* "*AAAA" */
  68   G_MATCH_EXACT,     /* "AAAAA" */
  69   G_MATCH_LAST
  70 } GMatchType;
  71
  72 struct _GPatternSpec
  73 {
  74   GMatchType match_type;
  75   guint      pattern_length;
  76   guint      min_length;
  77   guint      max_length;
  78   gchar     *pattern;
  79 };
  80
  81
  82 /* --- functions --- */
  83 static inline gboolean
  84 g_pattern_ph_match (const gchar *match_pattern,
  85                     const gchar *match_string,
  86                     gboolean    *wildcard_reached_p)
  87 {
  88   register const gchar *pattern, *string;
  89   register gchar ch;
  90
  91   pattern = match_pattern;
  92   string = match_string;
  93
  94   ch = *pattern;
  95   pattern++;
  96   while (ch)
  97     {
  98       switch (ch)
  99         {
 100         case '?':
 101           if (!*string)
 102             return FALSE;
 103           string = g_utf8_next_char (string);
 104           break;
 105
 106         case '*':
 107           *wildcard_reached_p = TRUE;
 108           do
 109             {
 110               ch = *pattern;
 111               pattern++;
 112               if (ch == '?')
 113                 {
 114                   if (!*string)
 115                     return FALSE;
 116                   string = g_utf8_next_char (string);
 117                 }
 118             }
 119           while (ch == '*' || ch == '?');
 120           if (!ch)
 121             return TRUE;
 122           do
 123             {
 124               gboolean next_wildcard_reached = FALSE;
 125               while (ch != *string)
 126                 {
 127                   if (!*string)
 128                     return FALSE;
 129                   string = g_utf8_next_char (string);
 130                 }
 131               string++;
 132               if (g_pattern_ph_match (pattern, string, &next_wildcard_reached))
 133                 return TRUE;
 134               if (next_wildcard_reached)
 135                 /* the forthcoming pattern substring up to the next wildcard has
 136                  * been matched, but a mismatch occoured for the rest of the
 137                  * pattern, following the next wildcard.
 138                  * there's no need to advance the current match position any
 139                  * further if the rest pattern will not match.
 140                  */
 141                 return FALSE;
 142             }
 143           while (*string);
 144           break;
 145
 146         default:
 147           if (ch == *string)
 148             string++;
 149           else
 150             return FALSE;
 151           break;
 152         }
 153
 154       ch = *pattern;
 155       pattern++;
 156     }
 157
 158   return *string == 0;
 159 }
 160
 161 /**
 162  * g_pattern_match:
 163  * @pspec: a #GPatternSpec
 164  * @string_length: the length of @string (in bytes, i.e. strlen(),
 165  *                 <emphasis>not</emphasis> g_utf8_strlen())
 166  * @string: the UTF-8 encoded string to match
 167  * @string_reversed: (allow-none): the reverse of @string or %NULL
 168  *
 169  * Matches a string against a compiled pattern. Passing the correct
 170  * length of the string given is mandatory. The reversed string can be
 171  * omitted by passing %NULL, this is more efficient if the reversed
 172  * version of the string to be matched is not at hand, as
 173  * g_pattern_match() will only construct it if the compiled pattern
 174  * requires reverse matches.
 175  *
 176  * Note that, if the user code will (possibly) match a string against a
 177  * multitude of patterns containing wildcards, chances are high that
 178  * some patterns will require a reversed string. In this case, it's
 179  * more efficient to provide the reversed string to avoid multiple
 180  * constructions thereof in the various calls to g_pattern_match().
 181  *
 182  * Note also that the reverse of a UTF-8 encoded string can in general
 183  * <emphasis>not</emphasis> be obtained by g_strreverse(). This works
 184  * only if the string doesn't contain any multibyte characters. GLib
 185  * offers the g_utf8_strreverse() function to reverse UTF-8 encoded
 186  * strings.
 187  *
 188  * Returns: %TRUE if @string matches @pspec
 189  **/
 190 gboolean
 191 g_pattern_match (GPatternSpec *pspec,
 192                  guint         string_length,
 193                  const gchar  *string,
 194                  const gchar  *string_reversed)
 195 {
 196   g_return_val_if_fail (pspec != NULL, FALSE);
 197   g_return_val_if_fail (string != NULL, FALSE);
 198
 199   if (string_length < pspec->min_length ||
 200       string_length > pspec->max_length)
 201     return FALSE;
 202
 203   switch (pspec->match_type)
 204     {
 205       gboolean dummy;
 206     case G_MATCH_ALL:
 207       return g_pattern_ph_match (pspec->pattern, string, &dummy);
 208     case G_MATCH_ALL_TAIL:
 209       if (string_reversed)
 210         return g_pattern_ph_match (pspec->pattern, string_reversed, &dummy);
 211       else
 212         {
 213           gboolean result;
 214           gchar *tmp;
 215           tmp = g_utf8_strreverse (string, string_length);
 216           result = g_pattern_ph_match (pspec->pattern, tmp, &dummy);
 217           g_free (tmp);
 218           return result;
 219         }
 220     case G_MATCH_HEAD:
 221       if (pspec->pattern_length == string_length)
 222         return strcmp (pspec->pattern, string) == 0;
 223       else if (pspec->pattern_length)
 224         return strncmp (pspec->pattern, string, pspec->pattern_length) == 0;
 225       else
 226         return TRUE;
 227     case G_MATCH_TAIL:
 228       if (pspec->pattern_length)
 229         return strcmp (pspec->pattern, string + (string_length - pspec->pattern_length)) == 0;
 230       else
 231         return TRUE;
 232     case G_MATCH_EXACT:
 233       if (pspec->pattern_length != string_length)
 234         return FALSE;
 235       else
 236         return strcmp (pspec->pattern, string) == 0;
 237     default:
 238       g_return_val_if_fail (pspec->match_type < G_MATCH_LAST, FALSE);
 239       return FALSE;
 240     }
 241 }
 242
 243 /**
 244  * g_pattern_spec_new:
 245  * @pattern: a zero-terminated UTF-8 encoded string
 246  *
 247  * Compiles a pattern to a #GPatternSpec.
 248  *
 249  * Returns: a newly-allocated #GPatternSpec
 250  **/
 251 GPatternSpec*
 252 g_pattern_spec_new (const gchar *pattern)
 253 {
 254   GPatternSpec *pspec;
 255   gboolean seen_joker = FALSE, seen_wildcard = FALSE, more_wildcards = FALSE;
 256   gint hw_pos = -1, tw_pos = -1, hj_pos = -1, tj_pos = -1;
 257   gboolean follows_wildcard = FALSE;
 258   guint pending_jokers = 0;
 259   const gchar *s;
 260   gchar *d;
 261   guint i;
 262
 263   g_return_val_if_fail (pattern != NULL, NULL);
 264
 265   /* canonicalize pattern and collect necessary stats */
 266   pspec = g_new (GPatternSpec, 1);
 267   pspec->pattern_length = strlen (pattern);
 268   pspec->min_length = 0;
 269   pspec->max_length = 0;
 270   pspec->pattern = g_new (gchar, pspec->pattern_length + 1);
 271   d = pspec->pattern;
 272   for (i = 0, s = pattern; *s != 0; s++)
 273     {
 274       switch (*s)
 275         {
 276         case '*':
 277           if (follows_wildcard) /* compress multiple wildcards */
 278             {
 279               pspec->pattern_length--;
 280               continue;
 281             }
 282           follows_wildcard = TRUE;
 283           if (hw_pos < 0)
 284             hw_pos = i;
 285           tw_pos = i;
 286           break;
 287         case '?':
 288           pending_jokers++;
 289           pspec->min_length++;
 290           pspec->max_length += 4; /* maximum UTF-8 character length */
 291           continue;
 292         default:
 293           for (; pending_jokers; pending_jokers--, i++) {
 294             *d++ = '?';
 295             if (hj_pos < 0)
 296              hj_pos = i;
 297             tj_pos = i;
 298           }
 299           follows_wildcard = FALSE;
 300           pspec->min_length++;
 301           pspec->max_length++;
 302           break;
 303         }
 304       *d++ = *s;
 305       i++;
 306     }
 307   for (; pending_jokers; pending_jokers--) {
 308     *d++ = '?';
 309     if (hj_pos < 0)
 310       hj_pos = i;
 311     tj_pos = i;
 312   }
 313   *d++ = 0;
 314   seen_joker = hj_pos >= 0;
 315   seen_wildcard = hw_pos >= 0;
 316   more_wildcards = seen_wildcard && hw_pos != tw_pos;
 317   if (seen_wildcard)
 318     pspec->max_length = G_MAXUINT;
 319
 320   /* special case sole head/tail wildcard or exact matches */
 321   if (!seen_joker && !more_wildcards)
 322     {
 323       if (pspec->pattern[0] == '*')
 324         {
 325           pspec->match_type = G_MATCH_TAIL;
 326           memmove (pspec->pattern, pspec->pattern + 1, --pspec->pattern_length);
 327           pspec->pattern[pspec->pattern_length] = 0;
 328           return pspec;
 329         }
 330       if (pspec->pattern_length > 0 &&
 331           pspec->pattern[pspec->pattern_length - 1] == '*')
 332         {
 333           pspec->match_type = G_MATCH_HEAD;
 334           pspec->pattern[--pspec->pattern_length] = 0;
 335           return pspec;
 336         }
 337       if (!seen_wildcard)
 338         {
 339           pspec->match_type = G_MATCH_EXACT;
 340           return pspec;
 341         }
 342     }
 343
 344   /* now just need to distinguish between head or tail match start */
 345   tw_pos = pspec->pattern_length - 1 - tw_pos;  /* last pos to tail distance */
 346   tj_pos = pspec->pattern_length - 1 - tj_pos;  /* last pos to tail distance */
 347   if (seen_wildcard)
 348     pspec->match_type = tw_pos > hw_pos ? G_MATCH_ALL_TAIL : G_MATCH_ALL;
 349   else /* seen_joker */
 350     pspec->match_type = tj_pos > hj_pos ? G_MATCH_ALL_TAIL : G_MATCH_ALL;
 351   if (pspec->match_type == G_MATCH_ALL_TAIL) {
 352     gchar *tmp = pspec->pattern;
 353     pspec->pattern = g_utf8_strreverse (pspec->pattern, pspec->pattern_length);
 354     g_free (tmp);
 355   }
 356   return pspec;
 357 }
 358
 359 /**
 360  * g_pattern_spec_free:
 361  * @pspec: a #GPatternSpec
 362  *
 363  * Frees the memory allocated for the #GPatternSpec.
 364  **/
 365 void
 366 g_pattern_spec_free (GPatternSpec *pspec)
 367 {
 368   g_return_if_fail (pspec != NULL);
 369
 370   g_free (pspec->pattern);
 371   g_free (pspec);
 372 }
 373
 374 /**
 375  * g_pattern_spec_equal:
 376  * @pspec1: a #GPatternSpec
 377  * @pspec2: another #GPatternSpec
 378  *
 379  * Compares two compiled pattern specs and returns whether they will
 380  * match the same set of strings.
 381  *
 382  * Returns: Whether the compiled patterns are equal
 383  **/
 384 gboolean
 385 g_pattern_spec_equal (GPatternSpec *pspec1,
 386                       GPatternSpec *pspec2)
 387 {
 388   g_return_val_if_fail (pspec1 != NULL, FALSE);
 389   g_return_val_if_fail (pspec2 != NULL, FALSE);
 390
 391   return (pspec1->pattern_length == pspec2->pattern_length &&
 392           pspec1->match_type == pspec2->match_type &&
 393           strcmp (pspec1->pattern, pspec2->pattern) == 0);
 394 }
 395
 396 /**
 397  * g_pattern_match_string:
 398  * @pspec: a #GPatternSpec
 399  * @string: the UTF-8 encoded string to match
 400  *
 401  * Matches a string against a compiled pattern. If the string is to be
 402  * matched against more than one pattern, consider using
 403  * g_pattern_match() instead while supplying the reversed string.
 404  *
 405  * Returns: %TRUE if @string matches @pspec
 406  **/
 407 gboolean
 408 g_pattern_match_string (GPatternSpec *pspec,
 409                         const gchar  *string)
 410 {
 411   g_return_val_if_fail (pspec != NULL, FALSE);
 412   g_return_val_if_fail (string != NULL, FALSE);
 413
 414   return g_pattern_match (pspec, strlen (string), string, NULL);
 415 }
 416
 417 /**
 418  * g_pattern_match_simple:
 419  * @pattern: the UTF-8 encoded pattern
 420  * @string: the UTF-8 encoded string to match
 421  *
 422  * Matches a string against a pattern given as a string. If this
 423  * function is to be called in a loop, it's more efficient to compile
 424  * the pattern once with g_pattern_spec_new() and call
 425  * g_pattern_match_string() repeatedly.
 426  *
 427  * Returns: %TRUE if @string matches @pspec
 428  **/
 429 gboolean
 430 g_pattern_match_simple (const gchar *pattern,
 431                         const gchar *string)
 432 {
 433   GPatternSpec *pspec;
 434   gboolean ergo;
 435
 436   g_return_val_if_fail (pattern != NULL, FALSE);
 437   g_return_val_if_fail (string != NULL, FALSE);
 438
 439   pspec = g_pattern_spec_new (pattern);
 440   ergo = g_pattern_match (pspec, strlen (string), string, NULL);
 441   g_pattern_spec_free (pspec);
 442
 443   return ergo;
 444 }