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