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 #include "gpattern.h"
  20
  21 #include "gmacros.h"
  22 #include "gmessages.h"
  23 #include "gmem.h"
  24 #include "gunicode.h"
  25 #include "gutils.h"
  26 #include <string.h>
  27
  28 /* keep enum and structure of gpattern.c and patterntest.c in sync */
  29 typedef enum
  30 {
  31   G_MATCH_ALL,       /* "*A?A*" */
  32   G_MATCH_ALL_TAIL,  /* "*A?AA" */
  33   G_MATCH_HEAD,      /* "AAAA*" */
  34   G_MATCH_TAIL,      /* "*AAAA" */
  35   G_MATCH_EXACT,     /* "AAAAA" */
  36   G_MATCH_LAST
  37 } GMatchType;
  38
  39 struct _GPatternSpec
  40 {
  41   GMatchType match_type;
  42   guint      pattern_length;
  43   guint      min_length;
  44   gchar     *pattern;
  45 };
  46
  47
  48 /* --- functions --- */
  49 /**
  50  * g_utf8_reverse:
  51  * string: a UTF-8 string.
  52  *
  53  * Reverses a UTF-8 string. The @string must be valid UTF-8 encoded text.
  54  * (Use g_utf8_validate() on all text before trying to use UTF-8
  55  * utility functions with it.)
  56  *
  57  * Note that unlike g_strreverse(), this function returns
  58  * newly-allocated memory, which should be freed with g_free() when
  59  * no longer needed.
  60  *
  61  * Returns: a newly-allocated string which is the reverse of @string.
  62  */
  63 static gchar *
  64 g_utf8_reverse (guint len, const gchar *string)
  65 {
  66   gchar *result;
  67   const gchar *p;
  68   gchar *m, *r, skip;
  69
  70   result = g_new (gchar, len + 1);
  71   r = result + len;
  72   p = string;
  73   while (*p)
  74     {
  75       skip = g_utf8_skip[*(guchar*)p];
  76       r -= skip;
  77       for (m = r; skip; skip--)
  78         *m++ = *p++;
  79     }
  80   result[len] = 0;
  81
  82   return result;
  83 }
  84
  85 static inline gboolean
  86 g_pattern_ph_match (const gchar *match_pattern,
  87                     const gchar *match_string)
  88 {
  89   register const gchar *pattern, *string;
  90   register gchar ch;
  91
  92   pattern = match_pattern;
  93   string = match_string;
  94
  95   ch = *pattern;
  96   pattern++;
  97   while (ch)
  98     {
  99       switch (ch)
 100         {
 101         case '?':
 102           if (!*string)
 103             return FALSE;
 104           string = g_utf8_next_char (string);
 105           break;
 106
 107         case '*':
 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               while (ch != *string)
 125                 {
 126                   if (!*string)
 127                     return FALSE;
 128                   string = g_utf8_next_char (string);
 129                 }
 130               string++;
 131               if (g_pattern_ph_match (pattern, string))
 132                 return TRUE;
 133             }
 134           while (*string);
 135           break;
 136
 137         default:
 138           if (ch == *string)
 139             string++;
 140           else
 141             return FALSE;
 142           break;
 143         }
 144
 145       ch = *pattern;
 146       pattern++;
 147     }
 148
 149   return *string == 0;
 150 }
 151
 152 gboolean
 153 g_pattern_match (GPatternSpec *pspec,
 154                  guint         string_length,
 155                  const gchar  *string,
 156                  const gchar  *string_reversed)
 157 {
 158   g_return_val_if_fail (pspec != NULL, FALSE);
 159   g_return_val_if_fail (string != NULL, FALSE);
 160
 161   if (pspec->min_length > string_length)
 162     return FALSE;
 163
 164   switch (pspec->match_type)
 165     {
 166     case G_MATCH_ALL:
 167       return g_pattern_ph_match (pspec->pattern, string);
 168     case G_MATCH_ALL_TAIL:
 169       if (string_reversed)
 170         return g_pattern_ph_match (pspec->pattern, string_reversed);
 171       else
 172         {
 173           gboolean result;
 174           gchar *tmp;
 175           tmp = g_utf8_reverse (string_length, string);
 176           result = g_pattern_ph_match (pspec->pattern, tmp);
 177           g_free (tmp);
 178           return result;
 179         }
 180     case G_MATCH_HEAD:
 181       if (pspec->pattern_length == string_length)
 182         return strcmp (pspec->pattern, string) == 0;
 183       else if (pspec->pattern_length)
 184         return strncmp (pspec->pattern, string, pspec->pattern_length) == 0;
 185       else
 186         return TRUE;
 187     case G_MATCH_TAIL:
 188       if (pspec->pattern_length)
 189         return strcmp (pspec->pattern, string + (string_length - pspec->pattern_length)) == 0;
 190       else
 191         return TRUE;
 192     case G_MATCH_EXACT:
 193       if (pspec->pattern_length != string_length)
 194         return FALSE;
 195       else
 196         return strcmp (pspec->pattern, string) == 0;
 197     default:
 198       g_return_val_if_fail (pspec->match_type < G_MATCH_LAST, FALSE);
 199       return FALSE;
 200     }
 201 }
 202
 203 GPatternSpec*
 204 g_pattern_spec_new (const gchar *pattern)
 205 {
 206   GPatternSpec *pspec;
 207   gboolean seen_joker = FALSE, seen_wildcard = FALSE, more_wildcards = FALSE;
 208   gint hw_pos = -1, tw_pos = -1, hj_pos = -1, tj_pos = -1;
 209   gboolean follows_wildcard = FALSE;
 210   guint pending_jokers = 0;
 211   const gchar *s;
 212   gchar *d;
 213   guint i;
 214
 215   g_return_val_if_fail (pattern != NULL, NULL);
 216
 217   /* canonicalize pattern and collect necessary stats */
 218   pspec = g_new (GPatternSpec, 1);
 219   pspec->pattern_length = strlen (pattern);
 220   pspec->min_length = 0;
 221   pspec->pattern = g_new (gchar, pspec->pattern_length + 1);
 222   d = pspec->pattern;
 223   for (i = 0, s = pattern; *s != 0; s++)
 224     {
 225       switch (*s)
 226         {
 227         case '*':
 228           if (follows_wildcard) /* compress multiple wildcards */
 229             {
 230               pspec->pattern_length--;
 231               continue;
 232             }
 233           follows_wildcard = TRUE;
 234           if (hw_pos < 0)
 235             hw_pos = i;
 236           tw_pos = i;
 237           break;
 238         case '?':
 239           pending_jokers++;
 240           pspec->min_length++;
 241           continue;
 242         default:
 243           for (; pending_jokers; pending_jokers--, i++) {
 244             *d++ = '?';
 245             if (hj_pos < 0)
 246              hj_pos = i;
 247             tj_pos = i;
 248           }
 249           follows_wildcard = FALSE;
 250           pspec->min_length++;
 251           break;
 252         }
 253       *d++ = *s;
 254       i++;
 255     }
 256   for (; pending_jokers; pending_jokers--) {
 257     *d++ = '?';
 258     if (hj_pos < 0)
 259       hj_pos = i;
 260     tj_pos = i;
 261   }
 262   *d++ = 0;
 263   seen_joker = hj_pos >= 0;
 264   seen_wildcard = hw_pos >= 0;
 265   more_wildcards = seen_wildcard && hw_pos != tw_pos;
 266
 267   /* special case sole head/tail wildcard or exact matches */
 268   if (!seen_joker && !more_wildcards)
 269     {
 270       if (pspec->pattern[0] == '*')
 271         {
 272           pspec->match_type = G_MATCH_TAIL;
 273           memmove (pspec->pattern, pspec->pattern + 1, --pspec->pattern_length);
 274           pspec->pattern[pspec->pattern_length] = 0;
 275           return pspec;
 276         }
 277       if (pspec->pattern[pspec->pattern_length - 1] == '*')
 278         {
 279           pspec->match_type = G_MATCH_HEAD;
 280           pspec->pattern[--pspec->pattern_length] = 0;
 281           return pspec;
 282         }
 283       if (!seen_wildcard)
 284         {
 285           pspec->match_type = G_MATCH_EXACT;
 286           return pspec;
 287         }
 288     }
 289
 290   /* now just need to distinguish between head or tail match start */
 291   tw_pos = pspec->pattern_length - 1 - tw_pos;  /* last pos to tail distance */
 292   tj_pos = pspec->pattern_length - 1 - tj_pos;  /* last pos to tail distance */
 293   if (seen_wildcard)
 294     pspec->match_type = tw_pos > hw_pos ? G_MATCH_ALL_TAIL : G_MATCH_ALL;
 295   else /* seen_joker */
 296     pspec->match_type = tj_pos > hj_pos ? G_MATCH_ALL_TAIL : G_MATCH_ALL;
 297   if (pspec->match_type == G_MATCH_ALL_TAIL) {
 298     gchar *tmp = pspec->pattern;
 299     pspec->pattern = g_utf8_reverse (pspec->pattern_length, pspec->pattern);
 300     g_free (tmp);
 301   }
 302   return pspec;
 303 }
 304
 305 void
 306 g_pattern_spec_free (GPatternSpec *pspec)
 307 {
 308   g_return_if_fail (pspec != NULL);
 309
 310   g_free (pspec->pattern);
 311   g_free (pspec);
 312 }
 313
 314 gboolean
 315 g_pattern_spec_equal (GPatternSpec *pspec1,
 316                       GPatternSpec *pspec2)
 317 {
 318   g_return_val_if_fail (pspec1 != NULL, FALSE);
 319   g_return_val_if_fail (pspec2 != NULL, FALSE);
 320
 321   return (pspec1->pattern_length == pspec2->pattern_length &&
 322           pspec1->match_type == pspec2->match_type &&
 323           strcmp (pspec1->pattern, pspec2->pattern) == 0);
 324 }
 325
 326 gboolean
 327 g_pattern_match_string (GPatternSpec *pspec,
 328                         const gchar  *string)
 329 {
 330   g_return_val_if_fail (pspec != NULL, FALSE);
 331   g_return_val_if_fail (string != NULL, FALSE);
 332
 333   return g_pattern_match (pspec, strlen (string), string, NULL);
 334 }
 335
 336 gboolean
 337 g_pattern_match_simple (const gchar *pattern,
 338                         const gchar *string)
 339 {
 340   GPatternSpec *pspec;
 341   gboolean ergo;
 342
 343   g_return_val_if_fail (pattern != NULL, FALSE);
 344   g_return_val_if_fail (string != NULL, FALSE);
 345
 346   pspec = g_pattern_spec_new (pattern);
 347   ergo = g_pattern_match (pspec, strlen (string), string, NULL);
 348   g_pattern_spec_free (pspec);
 349
 350   return ergo;
 351 }