+++ /dev/null
-/*
- * SPDX-License-Identifier: MIT
- *
- * Copyright (C) 2017 Philippe Proulx <pproulx@efficios.com>
- */
-
-#define _LGPL_SOURCE
-#include <stdlib.h>
-#include <string.h>
-#include <stdbool.h>
-#include <assert.h>
-
-#include "string-utils.h"
-
-enum star_glob_pattern_type_flags {
- STAR_GLOB_PATTERN_TYPE_FLAG_NONE = 0,
- STAR_GLOB_PATTERN_TYPE_FLAG_PATTERN = 1,
- STAR_GLOB_PATTERN_TYPE_FLAG_END_ONLY = 2,
-};
-
-static
-enum star_glob_pattern_type_flags strutils_test_glob_pattern(const char *pattern)
-{
- enum star_glob_pattern_type_flags ret =
- STAR_GLOB_PATTERN_TYPE_FLAG_NONE;
- const char *p;
-
- assert(pattern);
-
- for (p = pattern; *p != '\0'; p++) {
- switch (*p) {
- case '*':
- ret = STAR_GLOB_PATTERN_TYPE_FLAG_PATTERN;
-
- if (p[1] == '\0') {
- ret |= STAR_GLOB_PATTERN_TYPE_FLAG_END_ONLY;
- }
-
- goto end;
- case '\\':
- p++;
-
- if (*p == '\0') {
- goto end;
- }
- break;
- default:
- break;
- }
- }
-
-end:
- return ret;
-}
-
-/*
- * Returns true if `pattern` is a star-only globbing pattern, that is,
- * it contains at least one non-escaped `*`.
- */
-bool strutils_is_star_glob_pattern(const char *pattern)
-{
- return strutils_test_glob_pattern(pattern) &
- STAR_GLOB_PATTERN_TYPE_FLAG_PATTERN;
-}
-
-/*
- * Returns true if `pattern` is a globbing pattern with a globbing,
- * non-escaped star only at its very end.
- */
-bool strutils_is_star_at_the_end_only_glob_pattern(const char *pattern)
-{
- return strutils_test_glob_pattern(pattern) &
- STAR_GLOB_PATTERN_TYPE_FLAG_END_ONLY;
-}
-
-static inline
-bool at_end_of_pattern(const char *p, const char *pattern, size_t pattern_len)
-{
- return (p - pattern) == pattern_len || *p == '\0';
-}
-
-/*
- * Globbing matching function with the star feature only (`?` and
- * character sets are not supported). This matches `candidate` (plain
- * string) against `pattern`. A literal star can be escaped with `\` in
- * `pattern`.
- *
- * `pattern_len` or `candidate_len` can be greater than the actual
- * string length of `pattern` or `candidate` if the string is
- * null-terminated.
- */
-bool strutils_star_glob_match(const char *pattern, size_t pattern_len,
- const char *candidate, size_t candidate_len) {
- const char *retry_c = candidate, *retry_p = pattern, *c, *p;
- bool got_a_star = false;
-
-retry:
- c = retry_c;
- p = retry_p;
-
- /*
- * The concept here is to retry a match in the specific case
- * where we already got a star. The retry position for the
- * pattern is just after the most recent star, and the retry
- * position for the candidate is the character following the
- * last try's first character.
- *
- * Example:
- *
- * candidate: hi ev every onyx one
- * ^
- * pattern: hi*every*one
- * ^
- *
- * candidate: hi ev every onyx one
- * ^
- * pattern: hi*every*one
- * ^
- *
- * candidate: hi ev every onyx one
- * ^
- * pattern: hi*every*one
- * ^
- *
- * candidate: hi ev every onyx one
- * ^
- * pattern: hi*every*one
- * ^ MISMATCH
- *
- * candidate: hi ev every onyx one
- * ^
- * pattern: hi*every*one
- * ^
- *
- * candidate: hi ev every onyx one
- * ^^
- * pattern: hi*every*one
- * ^^
- *
- * candidate: hi ev every onyx one
- * ^ ^
- * pattern: hi*every*one
- * ^ ^ MISMATCH
- *
- * candidate: hi ev every onyx one
- * ^
- * pattern: hi*every*one
- * ^ MISMATCH
- *
- * candidate: hi ev every onyx one
- * ^
- * pattern: hi*every*one
- * ^ MISMATCH
- *
- * candidate: hi ev every onyx one
- * ^
- * pattern: hi*every*one
- * ^
- *
- * candidate: hi ev every onyx one
- * ^^
- * pattern: hi*every*one
- * ^^
- *
- * candidate: hi ev every onyx one
- * ^ ^
- * pattern: hi*every*one
- * ^ ^
- *
- * candidate: hi ev every onyx one
- * ^ ^
- * pattern: hi*every*one
- * ^ ^
- *
- * candidate: hi ev every onyx one
- * ^ ^
- * pattern: hi*every*one
- * ^ ^
- *
- * candidate: hi ev every onyx one
- * ^
- * pattern: hi*every*one
- * ^
- *
- * candidate: hi ev every onyx one
- * ^
- * pattern: hi*every*one
- * ^ MISMATCH
- *
- * candidate: hi ev every onyx one
- * ^
- * pattern: hi*every*one
- * ^
- *
- * candidate: hi ev every onyx one
- * ^^
- * pattern: hi*every*one
- * ^^
- *
- * candidate: hi ev every onyx one
- * ^ ^
- * pattern: hi*every*one
- * ^ ^ MISMATCH
- *
- * candidate: hi ev every onyx one
- * ^
- * pattern: hi*every*one
- * ^ MISMATCH
- *
- * candidate: hi ev every onyx one
- * ^
- * pattern: hi*every*one
- * ^ MISMATCH
- *
- * candidate: hi ev every onyx one
- * ^
- * pattern: hi*every*one
- * ^ MISMATCH
- *
- * candidate: hi ev every onyx one
- * ^
- * pattern: hi*every*one
- * ^ MISMATCH
- *
- * candidate: hi ev every onyx one
- * ^
- * pattern: hi*every*one
- * ^
- *
- * candidate: hi ev every onyx one
- * ^^
- * pattern: hi*every*one
- * ^^
- *
- * candidate: hi ev every onyx one
- * ^ ^
- * pattern: hi*every*one
- * ^ ^
- *
- * candidate: hi ev every onyx one
- * ^ ^
- * pattern: hi*every*one
- * ^ ^ SUCCESS
- */
- while ((c - candidate) < candidate_len && *c != '\0') {
- assert(*c);
-
- if (at_end_of_pattern(p, pattern, pattern_len)) {
- goto end_of_pattern;
- }
-
- switch (*p) {
- case '*':
- got_a_star = true;
-
- /*
- * Our first try starts at the current candidate
- * character and after the star in the pattern.
- */
- retry_c = c;
- retry_p = p + 1;
-
- if (at_end_of_pattern(retry_p, pattern, pattern_len)) {
- /*
- * Star at the end of the pattern at
- * this point: automatic match.
- */
- return true;
- }
-
- goto retry;
- case '\\':
- /* Go to escaped character. */
- p++; /* Fallthrough */
-
- /*
- * Fall through the default case which will
- * compare the escaped character now.
- */
- default:
- if (at_end_of_pattern(p, pattern, pattern_len) ||
- *c != *p) {
-end_of_pattern:
- /* Character mismatch OR end of pattern. */
- if (!got_a_star) {
- /*
- * We didn't get any star yet,
- * so this first mismatch
- * automatically makes the whole
- * test fail.
- */
- return false;
- }
-
- /*
- * Next try: next candidate character,
- * original pattern character (following
- * the most recent star).
- */
- retry_c++;
- goto retry;
- }
- break;
- }
-
- /* Next pattern and candidate characters. */
- c++;
- p++;
- }
-
- /*
- * We checked every candidate character and we're still in a
- * success state: the only pattern character allowed to remain
- * is a star.
- */
- if (at_end_of_pattern(p, pattern, pattern_len)) {
- return true;
- }
-
- p++;
- return p[-1] == '*' && at_end_of_pattern(p, pattern, pattern_len);
-}