liblttng-ust/string-utils.c

   1 /*
   2  * Copyright (C) 2017 - Philippe Proulx <pproulx@efficios.com>
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a copy
   5  * of this software and associated documentation files (the "Software"), to deal
   6  * in the Software without restriction, including without limitation the rights
   7  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   8  * copies of the Software, and to permit persons to whom the Software is
   9  * furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice shall be included in
  12  * all copies or substantial portions of the Software.
  13  *
  14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  17  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  18  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  19  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  20  * SOFTWARE.
  21  */
  22
  23 #define _LGPL_SOURCE
  24 #include <stdlib.h>
  25 #include <string.h>
  26 #include <stdbool.h>
  27 #include <assert.h>
  28
  29 #include "string-utils.h"
  30
  31 enum star_glob_pattern_type_flags {
  32         STAR_GLOB_PATTERN_TYPE_FLAG_NONE = 0,
  33         STAR_GLOB_PATTERN_TYPE_FLAG_PATTERN = 1,
  34         STAR_GLOB_PATTERN_TYPE_FLAG_END_ONLY = 2,
  35 };
  36
  37 static
  38 enum star_glob_pattern_type_flags strutils_test_glob_pattern(const char *pattern)
  39 {
  40         enum star_glob_pattern_type_flags ret =
  41                 STAR_GLOB_PATTERN_TYPE_FLAG_NONE;
  42         const char *p;
  43
  44         assert(pattern);
  45
  46         for (p = pattern; *p != '\0'; p++) {
  47                 switch (*p) {
  48                 case '*':
  49                         ret = STAR_GLOB_PATTERN_TYPE_FLAG_PATTERN;
  50
  51                         if (p[1] == '\0') {
  52                                 ret |= STAR_GLOB_PATTERN_TYPE_FLAG_END_ONLY;
  53                         }
  54
  55                         goto end;
  56                 case '\\':
  57                         p++;
  58
  59                         if (*p == '\0') {
  60                                 goto end;
  61                         }
  62                         break;
  63                 default:
  64                         break;
  65                 }
  66         }
  67
  68 end:
  69         return ret;
  70 }
  71
  72 /*
  73  * Returns true if `pattern` is a star-only globbing pattern, that is,
  74  * it contains at least one non-escaped `*`.
  75  */
  76 bool strutils_is_star_glob_pattern(const char *pattern)
  77 {
  78         return strutils_test_glob_pattern(pattern) &
  79                 STAR_GLOB_PATTERN_TYPE_FLAG_PATTERN;
  80 }
  81
  82 /*
  83  * Returns true if `pattern` is a globbing pattern with a globbing,
  84  * non-escaped star only at its very end.
  85  */
  86 bool strutils_is_star_at_the_end_only_glob_pattern(const char *pattern)
  87 {
  88         return strutils_test_glob_pattern(pattern) &
  89                 STAR_GLOB_PATTERN_TYPE_FLAG_END_ONLY;
  90 }
  91
  92 static inline
  93 bool at_end_of_pattern(const char *p, const char *pattern, size_t pattern_len)
  94 {
  95         return (p - pattern) == pattern_len || *p == '\0';
  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         const char *retry_c = candidate, *retry_p = pattern, *c, *p;
 111         bool got_a_star = false;
 112
 113 retry:
 114         c = retry_c;
 115         p = retry_p;
 116
 117         /*
 118          * The concept here is to retry a match in the specific case
 119          * where we already got a star. The retry position for the
 120          * pattern is just after the most recent star, and the retry
 121          * position for the candidate is the character following the
 122          * last try's first character.
 123          *
 124          * Example:
 125          *
 126          *     candidate: hi ev every onyx one
 127          *                ^
 128          *     pattern:   hi*every*one
 129          *                ^
 130          *
 131          *     candidate: hi ev every onyx one
 132          *                 ^
 133          *     pattern:   hi*every*one
 134          *                 ^
 135          *
 136          *     candidate: hi ev every onyx one
 137          *                  ^
 138          *     pattern:   hi*every*one
 139          *                  ^
 140          *
 141          *     candidate: hi ev every onyx one
 142          *                  ^
 143          *     pattern:   hi*every*one
 144          *                   ^ MISMATCH
 145          *
 146          *     candidate: hi ev every onyx one
 147          *                   ^
 148          *     pattern:   hi*every*one
 149          *                   ^
 150          *
 151          *     candidate: hi ev every onyx one
 152          *                   ^^
 153          *     pattern:   hi*every*one
 154          *                   ^^
 155          *
 156          *     candidate: hi ev every onyx one
 157          *                   ^ ^
 158          *     pattern:   hi*every*one
 159          *                   ^ ^ MISMATCH
 160          *
 161          *     candidate: hi ev every onyx one
 162          *                    ^
 163          *     pattern:   hi*every*one
 164          *                   ^ MISMATCH
 165          *
 166          *     candidate: hi ev every onyx one
 167          *                     ^
 168          *     pattern:   hi*every*one
 169          *                   ^ MISMATCH
 170          *
 171          *     candidate: hi ev every onyx one
 172          *                      ^
 173          *     pattern:   hi*every*one
 174          *                   ^
 175          *
 176          *     candidate: hi ev every onyx one
 177          *                      ^^
 178          *     pattern:   hi*every*one
 179          *                   ^^
 180          *
 181          *     candidate: hi ev every onyx one
 182          *                      ^ ^
 183          *     pattern:   hi*every*one
 184          *                   ^ ^
 185          *
 186          *     candidate: hi ev every onyx one
 187          *                      ^  ^
 188          *     pattern:   hi*every*one
 189          *                   ^  ^
 190          *
 191          *     candidate: hi ev every onyx one
 192          *                      ^   ^
 193          *     pattern:   hi*every*one
 194          *                   ^   ^
 195          *
 196          *     candidate: hi ev every onyx one
 197          *                           ^
 198          *     pattern:   hi*every*one
 199          *                        ^
 200          *
 201          *     candidate: hi ev every onyx one
 202          *                           ^
 203          *     pattern:   hi*every*one
 204          *                         ^ MISMATCH
 205          *
 206          *     candidate: hi ev every onyx one
 207          *                            ^
 208          *     pattern:   hi*every*one
 209          *                         ^
 210          *
 211          *     candidate: hi ev every onyx one
 212          *                            ^^
 213          *     pattern:   hi*every*one
 214          *                         ^^
 215          *
 216          *     candidate: hi ev every onyx one
 217          *                            ^ ^
 218          *     pattern:   hi*every*one
 219          *                         ^ ^ MISMATCH
 220          *
 221          *     candidate: hi ev every onyx one
 222          *                             ^
 223          *     pattern:   hi*every*one
 224          *                         ^ MISMATCH
 225          *
 226          *     candidate: hi ev every onyx one
 227          *                              ^
 228          *     pattern:   hi*every*one
 229          *                         ^ MISMATCH
 230          *
 231          *     candidate: hi ev every onyx one
 232          *                               ^
 233          *     pattern:   hi*every*one
 234          *                         ^ MISMATCH
 235          *
 236          *     candidate: hi ev every onyx one
 237          *                                ^
 238          *     pattern:   hi*every*one
 239          *                         ^ MISMATCH
 240          *
 241          *     candidate: hi ev every onyx one
 242          *                                 ^
 243          *     pattern:   hi*every*one
 244          *                         ^
 245          *
 246          *     candidate: hi ev every onyx one
 247          *                                 ^^
 248          *     pattern:   hi*every*one
 249          *                         ^^
 250          *
 251          *     candidate: hi ev every onyx one
 252          *                                 ^ ^
 253          *     pattern:   hi*every*one
 254          *                         ^ ^
 255          *
 256          *     candidate: hi ev every onyx one
 257          *                                 ^  ^
 258          *     pattern:   hi*every*one
 259          *                         ^  ^ SUCCESS
 260          */
 261         while ((c - candidate) < candidate_len && *c != '\0') {
 262                 assert(*c);
 263
 264                 if (at_end_of_pattern(p, pattern, pattern_len)) {
 265                         goto end_of_pattern;
 266                 }
 267
 268                 switch (*p) {
 269                 case '*':
 270                         got_a_star = true;
 271
 272                         /*
 273                          * Our first try starts at the current candidate
 274                          * character and after the star in the pattern.
 275                          */
 276                         retry_c = c;
 277                         retry_p = p + 1;
 278
 279                         if (at_end_of_pattern(retry_p, pattern, pattern_len)) {
 280                                 /*
 281                                  * Star at the end of the pattern at
 282                                  * this point: automatic match.
 283                                  */
 284                                 return true;
 285                         }
 286
 287                         goto retry;
 288                 case '\\':
 289                         /* Go to escaped character. */
 290                         p++;
 291
 292                         /*
 293                          * Fall through the default case which will
 294                          * compare the escaped character now.
 295                          */
 296                 default:
 297                         if (at_end_of_pattern(p, pattern, pattern_len) ||
 298                                         *c != *p) {
 299 end_of_pattern:
 300                                 /* Character mismatch OR end of pattern. */
 301                                 if (!got_a_star) {
 302                                         /*
 303                                          * We didn't get any star yet,
 304                                          * so this first mismatch
 305                                          * automatically makes the whole
 306                                          * test fail.
 307                                          */
 308                                         return false;
 309                                 }
 310
 311                                 /*
 312                                  * Next try: next candidate character,
 313                                  * original pattern character (following
 314                                  * the most recent star).
 315                                  */
 316                                 retry_c++;
 317                                 goto retry;
 318                         }
 319                         break;
 320                 }
 321
 322                 /* Next pattern and candidate characters. */
 323                 c++;
 324                 p++;
 325         }
 326
 327         /*
 328          * We checked every candidate character and we're still in a
 329          * success state: the only pattern character allowed to remain
 330          * is a star.
 331          */
 332         if (at_end_of_pattern(p, pattern, pattern_len)) {
 333                 return true;
 334         }
 335
 336         p++;
 337         return p[-1] == '*' && at_end_of_pattern(p, pattern, pattern_len);
 338 }