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