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