liblttng-ust/string-utils.c

   1 /*
   2  * SPDX-License-Identifier: MIT
   3  *
   4  * Copyright (C) 2017 Philippe Proulx <pproulx@efficios.com>
   5  */
   6
   7 #define _LGPL_SOURCE
   8 #include <stdlib.h>
   9 #include <string.h>
  10 #include <stdbool.h>
  11 #include <assert.h>
  12
  13 #include "string-utils.h"
  14
  15 enum star_glob_pattern_type_flags {
  16         STAR_GLOB_PATTERN_TYPE_FLAG_NONE = 0,
  17         STAR_GLOB_PATTERN_TYPE_FLAG_PATTERN = 1,
  18         STAR_GLOB_PATTERN_TYPE_FLAG_END_ONLY = 2,
  19 };
  20
  21 static
  22 enum star_glob_pattern_type_flags strutils_test_glob_pattern(const char *pattern)
  23 {
  24         enum star_glob_pattern_type_flags ret =
  25                 STAR_GLOB_PATTERN_TYPE_FLAG_NONE;
  26         const char *p;
  27
  28         assert(pattern);
  29
  30         for (p = pattern; *p != '\0'; p++) {
  31                 switch (*p) {
  32                 case '*':
  33                         ret = STAR_GLOB_PATTERN_TYPE_FLAG_PATTERN;
  34
  35                         if (p[1] == '\0') {
  36                                 ret |= STAR_GLOB_PATTERN_TYPE_FLAG_END_ONLY;
  37                         }
  38
  39                         goto end;
  40                 case '\\':
  41                         p++;
  42
  43                         if (*p == '\0') {
  44                                 goto end;
  45                         }
  46                         break;
  47                 default:
  48                         break;
  49                 }
  50         }
  51
  52 end:
  53         return ret;
  54 }
  55
  56 /*
  57  * Returns true if `pattern` is a star-only globbing pattern, that is,
  58  * it contains at least one non-escaped `*`.
  59  */
  60 bool strutils_is_star_glob_pattern(const char *pattern)
  61 {
  62         return strutils_test_glob_pattern(pattern) &
  63                 STAR_GLOB_PATTERN_TYPE_FLAG_PATTERN;
  64 }
  65
  66 /*
  67  * Returns true if `pattern` is a globbing pattern with a globbing,
  68  * non-escaped star only at its very end.
  69  */
  70 bool strutils_is_star_at_the_end_only_glob_pattern(const char *pattern)
  71 {
  72         return strutils_test_glob_pattern(pattern) &
  73                 STAR_GLOB_PATTERN_TYPE_FLAG_END_ONLY;
  74 }
  75
  76 static inline
  77 bool at_end_of_pattern(const char *p, const char *pattern, size_t pattern_len)
  78 {
  79         return (p - pattern) == pattern_len || *p == '\0';
  80 }
  81
  82 /*
  83  * Globbing matching function with the star feature only (`?` and
  84  * character sets are not supported). This matches `candidate` (plain
  85  * string) against `pattern`. A literal star can be escaped with `\` in
  86  * `pattern`.
  87  *
  88  * `pattern_len` or `candidate_len` can be greater than the actual
  89  * string length of `pattern` or `candidate` if the string is
  90  * null-terminated.
  91  */
  92 bool strutils_star_glob_match(const char *pattern, size_t pattern_len,
  93                 const char *candidate, size_t candidate_len) {
  94         const char *retry_c = candidate, *retry_p = pattern, *c, *p;
  95         bool got_a_star = false;
  96
  97 retry:
  98         c = retry_c;
  99         p = retry_p;
 100
 101         /*
 102          * The concept here is to retry a match in the specific case
 103          * where we already got a star. The retry position for the
 104          * pattern is just after the most recent star, and the retry
 105          * position for the candidate is the character following the
 106          * last try's first character.
 107          *
 108          * Example:
 109          *
 110          *     candidate: hi ev every onyx one
 111          *                ^
 112          *     pattern:   hi*every*one
 113          *                ^
 114          *
 115          *     candidate: hi ev every onyx one
 116          *                 ^
 117          *     pattern:   hi*every*one
 118          *                 ^
 119          *
 120          *     candidate: hi ev every onyx one
 121          *                  ^
 122          *     pattern:   hi*every*one
 123          *                  ^
 124          *
 125          *     candidate: hi ev every onyx one
 126          *                  ^
 127          *     pattern:   hi*every*one
 128          *                   ^ MISMATCH
 129          *
 130          *     candidate: hi ev every onyx one
 131          *                   ^
 132          *     pattern:   hi*every*one
 133          *                   ^
 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          *                   ^ ^ MISMATCH
 144          *
 145          *     candidate: hi ev every onyx one
 146          *                    ^
 147          *     pattern:   hi*every*one
 148          *                   ^ MISMATCH
 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          *                   ^ ^
 169          *
 170          *     candidate: hi ev every onyx one
 171          *                      ^  ^
 172          *     pattern:   hi*every*one
 173          *                   ^  ^
 174          *
 175          *     candidate: hi ev every onyx one
 176          *                      ^   ^
 177          *     pattern:   hi*every*one
 178          *                   ^   ^
 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          *                         ^ MISMATCH
 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          *                         ^ ^ MISMATCH
 204          *
 205          *     candidate: hi ev every onyx one
 206          *                             ^
 207          *     pattern:   hi*every*one
 208          *                         ^ MISMATCH
 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          *                         ^ MISMATCH
 219          *
 220          *     candidate: hi ev every onyx one
 221          *                                ^
 222          *     pattern:   hi*every*one
 223          *                         ^ MISMATCH
 224          *
 225          *     candidate: hi ev every onyx one
 226          *                                 ^
 227          *     pattern:   hi*every*one
 228          *                         ^
 229          *
 230          *     candidate: hi ev every onyx one
 231          *                                 ^^
 232          *     pattern:   hi*every*one
 233          *                         ^^
 234          *
 235          *     candidate: hi ev every onyx one
 236          *                                 ^ ^
 237          *     pattern:   hi*every*one
 238          *                         ^ ^
 239          *
 240          *     candidate: hi ev every onyx one
 241          *                                 ^  ^
 242          *     pattern:   hi*every*one
 243          *                         ^  ^ SUCCESS
 244          */
 245         while ((c - candidate) < candidate_len && *c != '\0') {
 246                 assert(*c);
 247
 248                 if (at_end_of_pattern(p, pattern, pattern_len)) {
 249                         goto end_of_pattern;
 250                 }
 251
 252                 switch (*p) {
 253                 case '*':
 254                         got_a_star = true;
 255
 256                         /*
 257                          * Our first try starts at the current candidate
 258                          * character and after the star in the pattern.
 259                          */
 260                         retry_c = c;
 261                         retry_p = p + 1;
 262
 263                         if (at_end_of_pattern(retry_p, pattern, pattern_len)) {
 264                                 /*
 265                                  * Star at the end of the pattern at
 266                                  * this point: automatic match.
 267                                  */
 268                                 return true;
 269                         }
 270
 271                         goto retry;
 272                 case '\\':
 273                         /* Go to escaped character. */
 274                         p++;
 275
 276                         /*
 277                          * Fall through the default case which will
 278                          * compare the escaped character now.
 279                          */
 280                 default:
 281                         if (at_end_of_pattern(p, pattern, pattern_len) ||
 282                                         *c != *p) {
 283 end_of_pattern:
 284                                 /* Character mismatch OR end of pattern. */
 285                                 if (!got_a_star) {
 286                                         /*
 287                                          * We didn't get any star yet,
 288                                          * so this first mismatch
 289                                          * automatically makes the whole
 290                                          * test fail.
 291                                          */
 292                                         return false;
 293                                 }
 294
 295                                 /*
 296                                  * Next try: next candidate character,
 297                                  * original pattern character (following
 298                                  * the most recent star).
 299                                  */
 300                                 retry_c++;
 301                                 goto retry;
 302                         }
 303                         break;
 304                 }
 305
 306                 /* Next pattern and candidate characters. */
 307                 c++;
 308                 p++;
 309         }
 310
 311         /*
 312          * We checked every candidate character and we're still in a
 313          * success state: the only pattern character allowed to remain
 314          * is a star.
 315          */
 316         if (at_end_of_pattern(p, pattern, pattern_len)) {
 317                 return true;
 318         }
 319
 320         p++;
 321         return p[-1] == '*' && at_end_of_pattern(p, pattern, pattern_len);
 322 }