lttng-string-utils.c

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