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"