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 /* keep enum and structure of gpattern.c and patterntest.c in sync */
  33 typedef enum
  34 {
  35   G_MATCH_ALL,       /* "*A?A*" */
  36   G_MATCH_ALL_TAIL,  /* "*A?AA" */
  37   G_MATCH_HEAD,      /* "AAAA*" */
  38   G_MATCH_TAIL,      /* "*AAAA" */
  39   G_MATCH_EXACT,     /* "AAAAA" */
  40   G_MATCH_LAST
  41 } GMatchType;
  42
  43 struct _GPatternSpec
  44 {
  45   GMatchType match_type;
  46   guint      pattern_length;
  47   guint      min_length;
  48   gchar     *pattern;
  49 };
  50
  51
  52 /* --- functions --- */
  53
  54 static inline gboolean
  55 g_pattern_ph_match (const gchar *match_pattern,
  56                     const gchar *match_string)
  57 {
  58   register const gchar *pattern, *string;
  59   register gchar ch;
  60
  61   pattern = match_pattern;
  62   string = match_string;
  63
  64   ch = *pattern;
  65   pattern++;
  66   while (ch)
  67     {
  68       switch (ch)
  69         {
  70         case '?':
  71           if (!*string)
  72             return FALSE;
  73           string = g_utf8_next_char (string);
  74           break;
  75
  76         case '*':
  77           do
  78             {
  79               ch = *pattern;
  80               pattern++;
  81               if (ch == '?')
  82                 {
  83                   if (!*string)
  84                     return FALSE;
  85                   string = g_utf8_next_char (string);
  86                 }
  87             }
  88           while (ch == '*' || ch == '?');
  89           if (!ch)
  90             return TRUE;
  91           do
  92             {
  93               while (ch != *string)
  94                 {
  95                   if (!*string)
  96                     return FALSE;
  97                   string = g_utf8_next_char (string);
  98                 }
  99               string++;
 100               if (g_pattern_ph_match (pattern, string))
 101                 return TRUE;
 102             }
 103           while (*string);
 104           break;
 105
 106         default:
 107           if (ch == *string)
 108             string++;
 109           else
 110             return FALSE;
 111           break;
 112         }
 113
 114       ch = *pattern;
 115       pattern++;
 116     }
 117
 118   return *string == 0;
 119 }
 120
 121 gboolean
 122 g_pattern_match (GPatternSpec *pspec,
 123                  guint         string_length,
 124                  const gchar  *string,
 125                  const gchar  *string_reversed)
 126 {
 127   g_return_val_if_fail (pspec != NULL, FALSE);
 128   g_return_val_if_fail (string != NULL, FALSE);
 129
 130   if (pspec->min_length > string_length)
 131     return FALSE;
 132
 133   switch (pspec->match_type)
 134     {
 135     case G_MATCH_ALL:
 136       return g_pattern_ph_match (pspec->pattern, string);
 137     case G_MATCH_ALL_TAIL:
 138       if (string_reversed)
 139         return g_pattern_ph_match (pspec->pattern, string_reversed);
 140       else
 141         {
 142           gboolean result;
 143           gchar *tmp;
 144           tmp = g_utf8_strreverse (string, string_length);
 145           result = g_pattern_ph_match (pspec->pattern, tmp);
 146           g_free (tmp);
 147           return result;
 148         }
 149     case G_MATCH_HEAD:
 150       if (pspec->pattern_length == string_length)
 151         return strcmp (pspec->pattern, string) == 0;
 152       else if (pspec->pattern_length)
 153         return strncmp (pspec->pattern, string, pspec->pattern_length) == 0;
 154       else
 155         return TRUE;
 156     case G_MATCH_TAIL:
 157       if (pspec->pattern_length)
 158         return strcmp (pspec->pattern, string + (string_length - pspec->pattern_length)) == 0;
 159       else
 160         return TRUE;
 161     case G_MATCH_EXACT:
 162       if (pspec->pattern_length != string_length)
 163         return FALSE;
 164       else
 165         return strcmp (pspec->pattern, string) == 0;
 166     default:
 167       g_return_val_if_fail (pspec->match_type < G_MATCH_LAST, FALSE);
 168       return FALSE;
 169     }
 170 }
 171
 172 GPatternSpec*
 173 g_pattern_spec_new (const gchar *pattern)
 174 {
 175   GPatternSpec *pspec;
 176   gboolean seen_joker = FALSE, seen_wildcard = FALSE, more_wildcards = FALSE;
 177   gint hw_pos = -1, tw_pos = -1, hj_pos = -1, tj_pos = -1;
 178   gboolean follows_wildcard = FALSE;
 179   guint pending_jokers = 0;
 180   const gchar *s;
 181   gchar *d;
 182   guint i;
 183
 184   g_return_val_if_fail (pattern != NULL, NULL);
 185
 186   /* canonicalize pattern and collect necessary stats */
 187   pspec = g_new (GPatternSpec, 1);
 188   pspec->pattern_length = strlen (pattern);
 189   pspec->min_length = 0;
 190   pspec->pattern = g_new (gchar, pspec->pattern_length + 1);
 191   d = pspec->pattern;
 192   for (i = 0, s = pattern; *s != 0; s++)
 193     {
 194       switch (*s)
 195         {
 196         case '*':
 197           if (follows_wildcard) /* compress multiple wildcards */
 198             {
 199               pspec->pattern_length--;
 200               continue;
 201             }
 202           follows_wildcard = TRUE;
 203           if (hw_pos < 0)
 204             hw_pos = i;
 205           tw_pos = i;
 206           break;
 207         case '?':
 208           pending_jokers++;
 209           pspec->min_length++;
 210           continue;
 211         default:
 212           for (; pending_jokers; pending_jokers--, i++) {
 213             *d++ = '?';
 214             if (hj_pos < 0)
 215              hj_pos = i;
 216             tj_pos = i;
 217           }
 218           follows_wildcard = FALSE;
 219           pspec->min_length++;
 220           break;
 221         }
 222       *d++ = *s;
 223       i++;
 224     }
 225   for (; pending_jokers; pending_jokers--) {
 226     *d++ = '?';
 227     if (hj_pos < 0)
 228       hj_pos = i;
 229     tj_pos = i;
 230   }
 231   *d++ = 0;
 232   seen_joker = hj_pos >= 0;
 233   seen_wildcard = hw_pos >= 0;
 234   more_wildcards = seen_wildcard && hw_pos != tw_pos;
 235
 236   /* special case sole head/tail wildcard or exact matches */
 237   if (!seen_joker && !more_wildcards)
 238     {
 239       if (pspec->pattern[0] == '*')
 240         {
 241           pspec->match_type = G_MATCH_TAIL;
 242           memmove (pspec->pattern, pspec->pattern + 1, --pspec->pattern_length);
 243           pspec->pattern[pspec->pattern_length] = 0;
 244           return pspec;
 245         }
 246       if (pspec->pattern_length > 0 &&
 247           pspec->pattern[pspec->pattern_length - 1] == '*')
 248         {
 249           pspec->match_type = G_MATCH_HEAD;
 250           pspec->pattern[--pspec->pattern_length] = 0;
 251           return pspec;
 252         }
 253       if (!seen_wildcard)
 254         {
 255           pspec->match_type = G_MATCH_EXACT;
 256           return pspec;
 257         }
 258     }
 259
 260   /* now just need to distinguish between head or tail match start */
 261   tw_pos = pspec->pattern_length - 1 - tw_pos;  /* last pos to tail distance */
 262   tj_pos = pspec->pattern_length - 1 - tj_pos;  /* last pos to tail distance */
 263   if (seen_wildcard)
 264     pspec->match_type = tw_pos > hw_pos ? G_MATCH_ALL_TAIL : G_MATCH_ALL;
 265   else /* seen_joker */
 266     pspec->match_type = tj_pos > hj_pos ? G_MATCH_ALL_TAIL : G_MATCH_ALL;
 267   if (pspec->match_type == G_MATCH_ALL_TAIL) {
 268     gchar *tmp = pspec->pattern;
 269     pspec->pattern = g_utf8_strreverse (pspec->pattern, pspec->pattern_length);
 270     g_free (tmp);
 271   }
 272   return pspec;
 273 }
 274
 275 void
 276 g_pattern_spec_free (GPatternSpec *pspec)
 277 {
 278   g_return_if_fail (pspec != NULL);
 279
 280   g_free (pspec->pattern);
 281   g_free (pspec);
 282 }
 283
 284 gboolean
 285 g_pattern_spec_equal (GPatternSpec *pspec1,
 286                       GPatternSpec *pspec2)
 287 {
 288   g_return_val_if_fail (pspec1 != NULL, FALSE);
 289   g_return_val_if_fail (pspec2 != NULL, FALSE);
 290
 291   return (pspec1->pattern_length == pspec2->pattern_length &&
 292           pspec1->match_type == pspec2->match_type &&
 293           strcmp (pspec1->pattern, pspec2->pattern) == 0);
 294 }
 295
 296 gboolean
 297 g_pattern_match_string (GPatternSpec *pspec,
 298                         const gchar  *string)
 299 {
 300   g_return_val_if_fail (pspec != NULL, FALSE);
 301   g_return_val_if_fail (string != NULL, FALSE);
 302
 303   return g_pattern_match (pspec, strlen (string), string, NULL);
 304 }
 305
 306 gboolean
 307 g_pattern_match_simple (const gchar *pattern,
 308                         const gchar *string)
 309 {
 310   GPatternSpec *pspec;
 311   gboolean ergo;
 312
 313   g_return_val_if_fail (pattern != NULL, FALSE);
 314   g_return_val_if_fail (string != NULL, FALSE);
 315
 316   pspec = g_pattern_spec_new (pattern);
 317   ergo = g_pattern_match (pspec, strlen (string), string, NULL);
 318   g_pattern_spec_free (pspec);
 319
 320   return ergo;
 321 }