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