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