lttng-string-utils.c

   1 /* SPDX-License-Identifier: (GPL-2.0 or LGPL-2.1)
   2  *
   3  * Copyright (C) 2017 Philippe Proulx <pproulx@efficios.com>
   4  */
   5
   6 #include <linux/types.h>
   7
   8 #include <lttng-string-utils.h>
   9
  10 enum star_glob_pattern_type_flags {
  11         STAR_GLOB_PATTERN_TYPE_FLAG_NONE        = 0,
  12         STAR_GLOB_PATTERN_TYPE_FLAG_PATTERN     = (1U << 0),
  13         STAR_GLOB_PATTERN_TYPE_FLAG_END_ONLY    = (1U << 1),
  14 };
  15
  16 static
  17 enum star_glob_pattern_type_flags strutils_test_glob_pattern(const char *pattern)
  18 {
  19         enum star_glob_pattern_type_flags ret =
  20                 STAR_GLOB_PATTERN_TYPE_FLAG_NONE;
  21         const char *p;
  22
  23         for (p = pattern; *p != '\0'; p++) {
  24                 switch (*p) {
  25                 case '*':
  26                         ret = STAR_GLOB_PATTERN_TYPE_FLAG_PATTERN;
  27
  28                         if (p[1] == '\0') {
  29                                 ret |= STAR_GLOB_PATTERN_TYPE_FLAG_END_ONLY;
  30                         }
  31                         goto end;
  32                 case '\\':
  33                         p++;
  34
  35                         if (*p == '\0') {
  36                                 goto end;
  37                         }
  38                         break;
  39                 default:
  40                         break;
  41                 }
  42         }
  43
  44 end:
  45         return ret;
  46 }
  47
  48 /*
  49  * Returns true if `pattern` is a star-only globbing pattern, that is,
  50  * it contains at least one non-escaped `*`.
  51  */
  52 bool strutils_is_star_glob_pattern(const char *pattern)
  53 {
  54         return strutils_test_glob_pattern(pattern) &
  55                 STAR_GLOB_PATTERN_TYPE_FLAG_PATTERN;
  56 }
  57
  58 /*
  59  * Returns true if `pattern` is a globbing pattern with a globbing,
  60  * non-escaped star only at its very end.
  61  */
  62 bool strutils_is_star_at_the_end_only_glob_pattern(const char *pattern)
  63 {
  64         return strutils_test_glob_pattern(pattern) &
  65                 STAR_GLOB_PATTERN_TYPE_FLAG_END_ONLY;
  66 }
  67
  68 struct string_with_len {
  69         const char *str;
  70         size_t len;
  71 };
  72
  73 static
  74 char string_get_char_at_cb(size_t at, void *data)
  75 {
  76         struct string_with_len *string_with_len = data;
  77
  78         if (at >= string_with_len->len) {
  79                 return '\0';
  80         }
  81
  82         return string_with_len->str[at];
  83 }
  84
  85 /*
  86  * Globbing matching function with the star feature only (`?` and
  87  * character sets are not supported). This matches `candidate` (plain
  88  * string) against `pattern`. A literal star can be escaped with `\` in
  89  * `pattern`.
  90  *
  91  * `pattern_len` or `candidate_len` can be greater than the actual
  92  * string length of `pattern` or `candidate` if the string is
  93  * null-terminated.
  94  */
  95 bool strutils_star_glob_match(const char *pattern, size_t pattern_len,
  96                 const char *candidate, size_t candidate_len) {
  97         struct string_with_len pattern_with_len = {
  98                 pattern, pattern_len
  99         };
 100         struct string_with_len candidate_with_len = {
 101                 candidate, candidate_len
 102         };
 103
 104         return strutils_star_glob_match_char_cb(string_get_char_at_cb,
 105                 &pattern_with_len, string_get_char_at_cb,
 106                 &candidate_with_len);
 107 }
 108
 109 bool strutils_star_glob_match_char_cb(
 110                 strutils_get_char_at_cb pattern_get_char_at_cb,
 111                 void *pattern_get_char_at_cb_data,
 112                 strutils_get_char_at_cb candidate_get_char_at_cb,
 113                 void *candidate_get_char_at_cb_data)
 114 {
 115         size_t retry_p_at = 0, retry_c_at = 0, c_at, p_at;
 116         char c, p, prev_p;
 117         bool got_a_star = false;
 118
 119 retry:
 120         c_at = retry_c_at;
 121         c = candidate_get_char_at_cb(c_at, candidate_get_char_at_cb_data);
 122         p_at = retry_p_at;
 123         p = pattern_get_char_at_cb(p_at, pattern_get_char_at_cb_data);
 124
 125         /*
 126          * The concept here is to retry a match in the specific case
 127          * where we already got a star. The retry position for the
 128          * pattern is just after the most recent star, and the retry
 129          * position for the candidate is the character following the
 130          * last try's first character.
 131          *
 132          * Example:
 133          *
 134          *     candidate: hi ev every onyx one
 135          *                ^
 136          *     pattern:   hi*every*one
 137          *                ^
 138          *
 139          *     candidate: hi ev every onyx one
 140          *                 ^
 141          *     pattern:   hi*every*one
 142          *                 ^
 143          *
 144          *     candidate: hi ev every onyx one
 145          *                  ^
 146          *     pattern:   hi*every*one
 147          *                  ^
 148          *
 149          *     candidate: hi ev every onyx one
 150          *                  ^
 151          *     pattern:   hi*every*one
 152          *                   ^ MISMATCH
 153          *
 154          *     candidate: hi ev every onyx one
 155          *                   ^
 156          *     pattern:   hi*every*one
 157          *                   ^
 158          *
 159          *     candidate: hi ev every onyx one
 160          *                   ^^
 161          *     pattern:   hi*every*one
 162          *                   ^^
 163          *
 164          *     candidate: hi ev every onyx one
 165          *                   ^ ^
 166          *     pattern:   hi*every*one
 167          *                   ^ ^ MISMATCH
 168          *
 169          *     candidate: hi ev every onyx one
 170          *                    ^
 171          *     pattern:   hi*every*one
 172          *                   ^ MISMATCH
 173          *
 174          *     candidate: hi ev every onyx one
 175          *                     ^
 176          *     pattern:   hi*every*one
 177          *                   ^ MISMATCH
 178          *
 179          *     candidate: hi ev every onyx one
 180          *                      ^
 181          *     pattern:   hi*every*one
 182          *                   ^
 183          *
 184          *     candidate: hi ev every onyx one
 185          *                      ^^
 186          *     pattern:   hi*every*one
 187          *                   ^^
 188          *
 189          *     candidate: hi ev every onyx one
 190          *                      ^ ^
 191          *     pattern:   hi*every*one
 192          *                   ^ ^
 193          *
 194          *     candidate: hi ev every onyx one
 195          *                      ^  ^
 196          *     pattern:   hi*every*one
 197          *                   ^  ^
 198          *
 199          *     candidate: hi ev every onyx one
 200          *                      ^   ^
 201          *     pattern:   hi*every*one
 202          *                   ^   ^
 203          *
 204          *     candidate: hi ev every onyx one
 205          *                           ^
 206          *     pattern:   hi*every*one
 207          *                        ^
 208          *
 209          *     candidate: hi ev every onyx one
 210          *                           ^
 211          *     pattern:   hi*every*one
 212          *                         ^ MISMATCH
 213          *
 214          *     candidate: hi ev every onyx one
 215          *                            ^
 216          *     pattern:   hi*every*one
 217          *                         ^
 218          *
 219          *     candidate: hi ev every onyx one
 220          *                            ^^
 221          *     pattern:   hi*every*one
 222          *                         ^^
 223          *
 224          *     candidate: hi ev every onyx one
 225          *                            ^ ^
 226          *     pattern:   hi*every*one
 227          *                         ^ ^ MISMATCH
 228          *
 229          *     candidate: hi ev every onyx one
 230          *                             ^
 231          *     pattern:   hi*every*one
 232          *                         ^ MISMATCH
 233          *
 234          *     candidate: hi ev every onyx one
 235          *                              ^
 236          *     pattern:   hi*every*one
 237          *                         ^ MISMATCH
 238          *
 239          *     candidate: hi ev every onyx one
 240          *                               ^
 241          *     pattern:   hi*every*one
 242          *                         ^ MISMATCH
 243          *
 244          *     candidate: hi ev every onyx one
 245          *                                ^
 246          *     pattern:   hi*every*one
 247          *                         ^ MISMATCH
 248          *
 249          *     candidate: hi ev every onyx one
 250          *                                 ^
 251          *     pattern:   hi*every*one
 252          *                         ^
 253          *
 254          *     candidate: hi ev every onyx one
 255          *                                 ^^
 256          *     pattern:   hi*every*one
 257          *                         ^^
 258          *
 259          *     candidate: hi ev every onyx one
 260          *                                 ^ ^
 261          *     pattern:   hi*every*one
 262          *                         ^ ^
 263          *
 264          *     candidate: hi ev every onyx one
 265          *                                 ^  ^
 266          *     pattern:   hi*every*one
 267          *                         ^  ^ SUCCESS
 268          */
 269         while (c != '\0') {
 270                 if (p == '\0') {
 271                         goto end_of_pattern;
 272                 }
 273
 274                 switch (p) {
 275                 case '*':
 276                 {
 277                         char retry_p;
 278                         got_a_star = true;
 279
 280                         /*
 281                          * Our first try starts at the current candidate
 282                          * character and after the star in the pattern.
 283                          */
 284                         retry_c_at = c_at;
 285                         retry_p_at = p_at + 1;
 286                         retry_p = pattern_get_char_at_cb(retry_p_at,
 287                                 pattern_get_char_at_cb_data);
 288
 289                         if (retry_p == '\0') {
 290                                 /*
 291                                  * Star at the end of the pattern at
 292                                  * this point: automatic match.
 293                                  */
 294                                 return true;
 295                         }
 296
 297                         goto retry;
 298                 }
 299                 case '\\':
 300                         /* Go to escaped character. */
 301                         p_at++;
 302                         p = pattern_get_char_at_cb(p_at,
 303                                 pattern_get_char_at_cb_data);
 304
 305                         /* Fall-through. */
 306                 default:
 307                         /*
 308                          * Default case which will compare the escaped
 309                          * character now.
 310                          */
 311                         if (p == '\0' || c != p) {
 312 end_of_pattern:
 313                                 /* Character mismatch OR end of pattern. */
 314                                 if (!got_a_star) {
 315                                         /*
 316                                          * We didn't get any star yet,
 317                                          * so this first mismatch
 318                                          * automatically makes the whole
 319                                          * test fail.
 320                                          */
 321                                         return false;
 322                                 }
 323
 324                                 /*
 325                                  * Next try: next candidate character,
 326                                  * original pattern character (following
 327                                  * the most recent star).
 328                                  */
 329                                 retry_c_at++;
 330                                 goto retry;
 331                         }
 332                         break;
 333                 }
 334
 335                 /* Next pattern and candidate characters. */
 336                 c_at++;
 337                 c = candidate_get_char_at_cb(c_at,
 338                         candidate_get_char_at_cb_data);
 339                 p_at++;
 340                 p = pattern_get_char_at_cb(p_at, pattern_get_char_at_cb_data);
 341         }
 342
 343         /*
 344          * We checked every candidate character and we're still in a
 345          * success state: the only pattern character allowed to remain
 346          * is a star.
 347          */
 348         if (p == '\0') {
 349                 return true;
 350         }
 351
 352         prev_p = p;
 353         p_at++;
 354         p = pattern_get_char_at_cb(p_at, pattern_get_char_at_cb_data);
 355         return prev_p == '*' && p == '\0';
 356 }