source: mainline/uspace/lib/posix/fnmatch.c@ 3e2952b

/*
 * Copyright (c) 2011 Jiri Zarevucky
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/** @addtogroup libposix
 * @{
 */
/** @file Filename-matching.
 */

/* This file contains an implementation of the fnmatch() pattern matching
 * function. There is more code than necessary to account for the possibility
 * of adding POSIX-like locale support to the system in the future. Functions
 * that are only necessary for locale support currently simply use single
 * characters for "collation elements". 
 * When (or if) locales are properly implemented, extending this implementation
 * will be fairly straightforward.
 */

#include "stdbool.h"
#include "ctype.h"
#include "string.h"
#include "stdlib.h"
#include "assert.h"

#define LIBPOSIX_INTERNAL

#include "internal/common.h"
#include "fnmatch.h"

/* Returned by _match... functions. */
#define INVALID_PATTERN -1

/* Type for collating element, simple identity with characters now,
 * but may be extended for better locale support.
 */
typedef int coll_elm_t;

/** Return value indicating that the element in question
 * is not valid in the current locale. (That is, if locales are supported.)
 */
#define COLL_ELM_INVALID -1

/**
 * Get collating element matching a string.
 *
 * @param str String representation of the element.
 * @return Matching collating element or COLL_ELM_INVALID.
 */
static coll_elm_t _coll_elm_get(const char* str)
{
        if (str[0] == '\0' || str[1] != '\0') {
                return COLL_ELM_INVALID;
        }
        return str[0];
}

/**
 * Get collating element matching a single character.
 *
 * @param c Character representation of the element.
 * @return Matching collating element.
 */
static coll_elm_t _coll_elm_char(int c)
{
        return c;
}

/**
 * Match collating element with a beginning of a string.
 *
 * @param elm Collating element to match.
 * @param str String which beginning should match the element.
 * @return 0 if the element doesn't match, or the number of characters matched.
 */
static int _coll_elm_match(coll_elm_t elm, const char *str)
{
        return elm == *str;
}

/**
 * Checks whether a string begins with a collating element in the given range.
 * Ordering depends on the locale (if locales are supported).
 *
 * @param first First element of the range.
 * @param second Last element of the range.
 * @param str String to match.
 * @return 0 if there is no match, or the number of characters matched.
 */
static int _coll_elm_between(coll_elm_t first, coll_elm_t second,
    const char *str)
{
        return *str >= first && *str <= second;
}

/**
 * Read a string delimited by [? and ?].
 *
 * @param pattern Pointer to the string to read from. Its position is moved
 *    to the first character after the closing ].
 * @param seq The character on the inside of brackets.
 * @param buf Read buffer.
 * @param buf_sz Read buffer's size. If the buffer is not large enough for
 *    the entire string, the string is cut with no error indication.
 * @param flags Flags modifying the behavior.
 * @return True on success, false if the pattern is invalid.
 */
static bool _get_delimited(
    const char **pattern, int seq,
    char *buf, size_t buf_sz, int flags)
{
        const bool noescape = (flags & FNM_NOESCAPE) != 0;
        const bool pathname = (flags & FNM_PATHNAME) != 0;

        const char *p = *pattern;
        assert(p[0] == '[' && p[1] == seq /* Caller should ensure this. */);
        p += 2;

        while (true) {
                if (*p == seq && *(p + 1) == ']') {
                        /* String properly ended, return. */
                        *pattern = p + 2;
                        *buf = '\0';
                        return true;
                }
                if (!noescape && *p == '\\') {
                        p++;
                }
                if (*p == '\0') {
                        /* String not ended properly, invalid pattern. */
                        return false;
                }
                if (pathname && *p == '/') {
                        /* Slash in a pathname pattern is invalid. */
                        return false;
                }
                if (buf_sz > 1) {
                        /* Only add to the buffer if there is space. */
                        *buf = *p;
                        buf++;
                        buf_sz--;
                }
                p++;
        }
}

/************** CHARACTER CLASSES ****************/

#define MAX_CLASS_OR_COLL_LEN 6

struct _char_class {
        const char *name;
        int (*func) (int);
};

/* List of supported character classes. */
static const struct _char_class _char_classes[] = {
        { "alnum", isalnum },
        { "alpha", isalpha },
        { "blank", isblank },
        { "cntrl", iscntrl },
        { "digit", isdigit },
        { "graph", isgraph },
        { "lower", islower },
        { "print", isprint },
        { "punct", ispunct },
        { "space", isspace },
        { "upper", isupper },
        { "xdigit", isxdigit }
};

/**
 * Compare function for binary search in the _char_classes array.
 * 
 * @param key Key of the searched element.
 * @param elem Element of _char_classes array.
 * @return Ordering indicator (-1 less than, 0 equal, 1 greater than).
 */
static int _class_compare(const void *key, const void *elem)
{
        const struct _char_class *class = elem;
        return strcmp((const char *) key, class->name);
}

/**
 * Returns whether the given character belongs to the specified character class.
 * 
 * @param cname Name of the character class.
 * @param c Character.
 * @return True if the character belongs to the class, false otherwise.
 */
static bool _is_in_class (const char *cname, int c)
{
        /* Search for class in the array of supported character classes. */
        const struct _char_class *class = bsearch(cname, _char_classes,
            sizeof(_char_classes) / sizeof(struct _char_class),
            sizeof(struct _char_class), _class_compare);

        if (class == NULL) {
                /* No such class supported - treat as an empty class. */
                return false;
        } else {
                /* Class matched. */
                return class->func(c);
        }
}

/**
 * Tries to parse an initial part of the pattern as a character class pattern,
 * and if successful, matches the beginning of the given string against the class.
 * 
 * @param pattern Pointer to the pattern to match. Must begin with a class
 *    specifier and is repositioned to the first character after the specifier
 *    if successful.
 * @param str String to match.
 * @param flags Flags modifying the behavior (see fnmatch()).
 * @return INVALID_PATTERN if the pattern doesn't start with a valid class
 *    specifier, 0 if the beginning of the matched string doesn't belong
 *    to the class, or positive number of characters matched.
 */
static int _match_char_class(const char **pattern, const char *str, int flags)
{
        char class[MAX_CLASS_OR_COLL_LEN + 1];

        if (!_get_delimited(pattern, ':', class, sizeof(class), flags)) {
                return INVALID_PATTERN;
        }

        return _is_in_class(class, *str);
}

/************** END CHARACTER CLASSES ****************/

/**
 * Reads the next collating element in the pattern, taking into account
 * locale (if supported) and flags (see fnmatch()).
 * 
 * @param pattern Pattern.
 * @param flags Flags given to fnmatch().
 * @return Collating element on success,
 *     or COLL_ELM_INVALID if the pattern is invalid.
 */
static coll_elm_t _next_coll_elm(const char **pattern, int flags)
{
        assert(pattern != NULL);
        assert(*pattern != NULL);
        assert(**pattern != '\0');

        const char *p = *pattern;
        const bool noescape = (flags & FNM_NOESCAPE) != 0;
        const bool pathname = (flags & FNM_PATHNAME) != 0;

        if (*p == '[') {
                if (*(p + 1) == '.') {
                        char buf[MAX_CLASS_OR_COLL_LEN + 1];
                        if (!_get_delimited(pattern, '.', buf, sizeof(buf), flags)) {
                                return COLL_ELM_INVALID;
                        }
                        return _coll_elm_get(buf);
                }

                if (*(p + 1) == '=') {
                        char buf[MAX_CLASS_OR_COLL_LEN + 1];
                        if (!_get_delimited(pattern, '=', buf, sizeof(buf), flags)) {
                                return COLL_ELM_INVALID;
                        }
                        return _coll_elm_get(buf);
                }
        }

        if (!noescape && *p == '\\') {
                p++;
                if (*p == '\0') {
                        *pattern = p;
                        return COLL_ELM_INVALID;
                }
        }
        if (pathname && *p == '/') {
                return COLL_ELM_INVALID;
        }
        
        *pattern = p + 1;
        return _coll_elm_char(*p);
}

/**
 * Matches the beginning of the given string against a bracket expression
 * the pattern begins with.
 * 
 * @param pattern Pointer to the beginning of a bracket expression in a pattern.
 *     On success, the pointer is moved to the first character after the
 *     bracket expression.
 * @param str Unmatched part of the string.
 * @param flags Flags given to fnmatch().
 * @return INVALID_PATTERN if the pattern is invalid, 0 if there is no match
 *     or the number of matched characters on success.
 */
static int _match_bracket_expr(const char **pattern, const char *str, int flags)
{
        const bool pathname = (flags & FNM_PATHNAME) != 0;
        const bool special_period = (flags & FNM_PERIOD) != 0;
        const char *p = *pattern;
        bool negative = false;
        int matched = 0;

        #define _matched(match) { \
                int _match = match; \
                if (_match < 0) { \
                        /* Invalid pattern */ \
                        return _match; \
                } else if (matched == 0 && _match > 0) { \
                        /* First match */ \
                        matched = _match; \
                } \
        }

        assert(*p == '[');  /* calling code should ensure this */
        p++;

        if (*str == '\0' || (pathname && *str == '/') ||
            (pathname && special_period && *str == '.' && *(str - 1) == '/')) {
                /* No bracket expression matches end of string,
                 * slash in pathname match or initial period with FNM_PERIOD
                 * option.
                 */
                return 0;
        }

        if (*p == '^' || *p == '!') {
                negative = true;
                p++;
        }

        if (*p == ']') {
                /* When ']' is first, treat it as a normal character. */
                _matched(*str == ']');
                p++;
        }
        
        coll_elm_t current_elm = COLL_ELM_INVALID;
        
        while (*p != ']') {
                if (*p == '-' && *(p + 1) != ']' &&
                    current_elm != COLL_ELM_INVALID) {
                        /* Range expression. */
                        p++;
                        coll_elm_t end_elm = _next_coll_elm(&p, flags);
                        if (end_elm == COLL_ELM_INVALID) {
                                return INVALID_PATTERN;
                        }
                        _matched(_coll_elm_between(current_elm, end_elm, str));
                        continue;
                }
        
                if (*p == '[' && *(p + 1) == ':') {
                        current_elm = COLL_ELM_INVALID;
                        _matched(_match_char_class(&p, str, flags));
                        continue;
                }
                
                current_elm = _next_coll_elm(&p, flags);
                if (current_elm == COLL_ELM_INVALID) {
                        return INVALID_PATTERN;
                }
                _matched(_coll_elm_match(current_elm, str));
        }

        /* No error occured - update pattern pointer. */
        *pattern = p + 1;

        if (matched == 0) {
                /* No match found */
                return negative;
        } else {
                /* Matched 'match' characters. */
                return negative ? 0 : matched;
        }

        #undef _matched
}

/**
 * Matches a portion of the pattern containing no asterisks (*) against
 * the given string.
 * 
 * @param pattern Pointer to the unmatched portion of the pattern.
 *     On success, the pointer is moved to the first asterisk, or to the
 *     terminating nul character, whichever occurs first.
 * @param string Pointer to the input string. On success, the pointer is moved
 *     to the first character that wasn't explicitly matched.
 * @param flags Flags given to fnmatch().
 * @return True if the entire subpattern matched. False otherwise.
 */
static bool _partial_match(const char **pattern, const char **string, int flags)
{
        /* Only a single *-delimited subpattern is matched here.
         * So in this function, '*' is understood as the end of pattern.
         */

        const bool pathname = (flags & FNM_PATHNAME) != 0;
        const bool special_period = (flags & FNM_PERIOD) != 0;
        const bool noescape = (flags & FNM_NOESCAPE) != 0;
        const bool leading_dir = (flags & FNM_LEADING_DIR) != 0;

        const char *s = *string;
        const char *p = *pattern;

        while (*p != '*') {
                /* Bracket expression. */
                if (*p == '[') {
                        int matched = _match_bracket_expr(&p, s, flags);
                        if (matched == 0) {
                                /* Doesn't match. */
                                return false;
                        }
                        if (matched != INVALID_PATTERN) {
                                s += matched;
                                continue;
                        }

                        assert(matched == INVALID_PATTERN);
                        /* Fall through to match [ as an ordinary character. */
                }

                /* Wildcard match. */
                if (*p == '?') {
                        if (*s == '\0') {
                                /* No character to match. */
                                return false;
                        }
                        if (pathname && *s == '/') {
                                /* Slash must be matched explicitly. */
                                return false;
                        }
                        if (special_period && pathname &&
                            *s == '.' && *(s - 1) == '/') {
                                /* Initial period must be matched explicitly. */
                                return false;
                        }
                        
                        /* None of the above, match anything else. */
                        p++;
                        s++;
                        continue;
                }

                if (!noescape && *p == '\\') {
                        /* Escaped character. */
                        p++;
                }

                if (*p == '\0') {
                        /* End of pattern, must match end of string or
                         * an end of subdirectory name (optional).
                         */

                        if (*s == '\0' || (leading_dir && *s == '/')) {
                                break;
                        }

                        return false;
                }

                if (*p == *s) {
                        /* Exact match. */
                        p++;
                        s++;
                        continue;
                }

                /* Nothing matched. */
                return false;
        }

        /* Entire sub-pattern matched. */
        
        /* postconditions */
        assert(*p == '\0' || *p == '*');
        assert(*p != '\0' || *s == '\0' || (leading_dir && *s == '/'));
        
        *pattern = p;
        *string = s;
        return true;
}

/**
 * Match string against a pattern.
 * 
 * @param pattern Pattern.
 * @param string String to match.
 * @param flags Flags given to fnmatch().
 * @return True if the string matched the pattern, false otherwise.
 */
static bool _full_match(const char *pattern, const char *string, int flags)
{
        const bool pathname = (flags & FNM_PATHNAME) != 0;
        const bool special_period = (flags & FNM_PERIOD) != 0;
        const bool leading_dir = (flags & FNM_LEADING_DIR) != 0;

        if (special_period && *string == '.') {
                /* Initial dot must be matched by an explicit dot in pattern. */
                if (*pattern != '.') {
                        return false;
                }
                pattern++;
                string++;
        }

        if (*pattern != '*') {
                if (!_partial_match(&pattern, &string, flags)) {
                        /* The initial match must succeed. */
                        return false;
                }
        }

        while (*pattern != '\0') {
                assert(*pattern == '*');
                pattern++;

                bool matched = false;

                const char *end;
                if (pathname && special_period &&
                    *string == '.' && *(string - 1) == '/') {
                        end = string;
                } else {
                        end = strchrnul(string, pathname ? '/' : '\0');
                }

                /* Try to match every possible offset. */
                while (string <= end) {
                        if (_partial_match(&pattern, &string, flags)) {
                                matched = true;
                                break;
                        }
                        string++;
                }

                if (matched) {
                        continue;
                }

                return false;
        }

        return *string == '\0' || (leading_dir && *string == '/');
}

/**
 * Transform the entire string to lowercase.
 * 
 * @param s Input string.
 * @return Newly allocated copy of the input string with all uppercase
 *     characters folded to their lowercase variants.
 */
static char *_casefold(const char *s)
{
        assert(s != NULL);
        char *result = strdup(s);
        for (char *i = result; *i != '\0'; ++i) {
                *i = tolower(*i);
        }
        return result;
}

/**
 * Filename pattern matching.
 *
 * @param pattern Pattern to match the string against.
 * @param string Matched string.
 * @param flags Flags altering the matching of special characters
 *     (mainly for dot and slash).
 * @return Zero if the string matches the pattern, FNM_NOMATCH otherwise.
 */
int posix_fnmatch(const char *pattern, const char *string, int flags)
{
        assert(pattern != NULL);
        assert(string != NULL);

        // TODO: don't fold everything in advance, but only when needed

        if ((flags & FNM_CASEFOLD) != 0) {
                /* Just fold the entire pattern and string. */
                pattern = _casefold(pattern);
                string = _casefold(string);
        }

        bool result = _full_match(pattern, string, flags);

        if ((flags & FNM_CASEFOLD) != 0) {
                if (pattern) {
                        free((char *) pattern);
                }
                if (string) {
                        free((char *) string);
                }
        }

        return result ? 0 : FNM_NOMATCH;
}

// FIXME: put the testcases to the app/tester after fnmatch is included into libc

#if 0

#include <stdio.h>

void __posix_fnmatch_test()
{
        int fail = 0;

        #undef assert
        #define assert(x) { if (x) printf("SUCCESS: "#x"\n"); else { printf("FAILED: "#x"\n"); fail++; } }
        #define match(s1, s2, flags) assert(posix_fnmatch(s1, s2, flags) == 0)
        #define nomatch(s1, s2, flags) assert(posix_fnmatch(s1, s2, flags) == FNM_NOMATCH)

        assert(FNM_PATHNAME == FNM_FILE_NAME);
        match("", "", 0);
        match("*", "hello", 0);
        match("hello", "hello", 0);
        match("hello*", "hello", 0);
        nomatch("hello?", "hello", 0);
        match("*hello", "prdel hello", 0);
        match("he[sl]lo", "hello", 0);
        match("he[sl]lo", "heslo", 0);
        nomatch("he[sl]lo", "heblo", 0);
        nomatch("he[^sl]lo", "hello", 0);
        nomatch("he[^sl]lo", "heslo", 0);
        match("he[^sl]lo", "heblo", 0);
        nomatch("he[!sl]lo", "hello", 0);
        nomatch("he[!sl]lo", "heslo", 0);
        match("he[!sl]lo", "heblo", 0);
        match("al*[c-t]a*vis*ta", "alheimer talir jehovista", 0);
        match("al*[c-t]a*vis*ta", "alfons had jehovista", 0);
        match("[a-ce-z]", "a", 0);
        match("[a-ce-z]", "c", 0);
        nomatch("[a-ce-z]", "d", 0);
        match("[a-ce-z]", "e", 0);
        match("[a-ce-z]", "z", 0);
        nomatch("[^a-ce-z]", "a", 0);
        nomatch("[^a-ce-z]", "c", 0);
        match("[^a-ce-z]", "d", 0);
        nomatch("[^a-ce-z]", "e", 0);
        nomatch("[^a-ce-z]", "z", 0);
        match("helen??", "helenos", 0);
        match("****booo****", "booo", 0);
        
        match("hello[[:space:]]world", "hello world", 0);
        nomatch("hello[[:alpha:]]world", "hello world", 0);
        
        match("/hoooo*", "/hooooooo/hooo", 0);
        nomatch("/hoooo*", "/hooooooo/hooo", FNM_PATHNAME);
        nomatch("/hoooo*/", "/hooooooo/hooo", FNM_PATHNAME);
        match("/hoooo*/*", "/hooooooo/hooo", FNM_PATHNAME);
        match("/hoooo*/hooo", "/hooooooo/hooo", FNM_PATHNAME);
        match("/hoooo*", "/hooooooo/hooo", FNM_PATHNAME | FNM_LEADING_DIR);
        nomatch("/hoooo*/", "/hooooooo/hooo", FNM_PATHNAME | FNM_LEADING_DIR);
        nomatch("/hoooo", "/hooooooo/hooo", FNM_LEADING_DIR);
        match("/hooooooo", "/hooooooo/hooo", FNM_LEADING_DIR);
        
        match("*", "hell", 0);
        match("*?", "hell", 0);
        match("?*?", "hell", 0);
        match("?*??", "hell", 0);
        match("??*??", "hell", 0);
        nomatch("???*??", "hell", 0);
        
        nomatch("", "hell", 0);
        nomatch("?", "hell", 0);
        nomatch("??", "hell", 0);
        nomatch("???", "hell", 0);
        match("????", "hell", 0);
        
        match("*", "h.ello", FNM_PERIOD);
        match("*", "h.ello", FNM_PATHNAME | FNM_PERIOD);
        nomatch("*", ".hello", FNM_PERIOD);
        match("h?ello", "h.ello", FNM_PERIOD);
        nomatch("?hello", ".hello", FNM_PERIOD);
        match("/home/user/.*", "/home/user/.hello", FNM_PATHNAME | FNM_PERIOD);
        match("/home/user/*", "/home/user/.hello", FNM_PERIOD);
        nomatch("/home/user/*", "/home/user/.hello", FNM_PATHNAME | FNM_PERIOD);

        nomatch("HeLlO", "hello", 0);
        match("HeLlO", "hello", FNM_CASEFOLD);

        printf("Failed: %d\n", fail);
}

#endif

/** @}
 */