Fork us on GitHub Follow us on Facebook Follow us on Twitter

Changeset a43fbc95 in mainline


Ignore:
Timestamp:
2011-07-01T21:51:00Z (11 years ago)
Author:
Jiří Zárevúcky <zarevucky.jiri@…>
Branches:
lfn, master
Children:
06cb827
Parents:
6b4c64a
Message:

fnmatch.h: Finish and fix bugs. Also add some basic tests (at the bottom, commented out until a proper place is found).

File:
1 edited

Legend:

Unmodified
Added
Removed
  • uspace/lib/posix/fnmatch.c

    r6b4c64a ra43fbc95  
    3333 */
    3434
     35// TODO: clean this up a bit
     36
     37#include "stdbool.h"
     38#include "ctype.h"
     39#include "string.h"
     40#include "stdlib.h"
     41#include "assert.h"
     42
    3543#define LIBPOSIX_INTERNAL
    3644
     
    3846#include "fnmatch.h"
    3947
    40 #include "stdlib.h"
    41 #include "string.h"
    42 #include "ctype.h"
    43 
    4448#define INVALID_PATTERN -1
    4549
     
    5155#define COLL_ELM_INVALID -1
    5256
     57/** Get collating element matching a string.
     58 *
     59 * @param str
     60 * @return
     61 */
    5362static _coll_elm_t _coll_elm_get(const char* str)
    5463{
     
    5968}
    6069
     70/** Get collating element matching a single character.
     71 *
     72 * @param c
     73 * @return
     74 */
    6175static _coll_elm_t _coll_elm_char(int c)
    6276{
     
    6478}
    6579
    66 /**
     80/** Match collating element with a beginning of a string.
    6781 *
    6882 * @param elm
    69  * @param pattern
     83 * @param str
    7084 * @return 0 if the element doesn't match, or the number of characters matched.
    7185 */
     
    143157        { "alnum", isalnum },
    144158        { "alpha", isalpha },
    145         { "blank", posix_isblank },
    146         { "cntrl", posix_iscntrl },
     159        { "blank", isblank },
     160        { "cntrl", iscntrl },
    147161        { "digit", isdigit },
    148         { "graph", posix_isgraph },
     162        { "graph", isgraph },
    149163        { "lower", islower },
    150         { "print", posix_isprint },
    151         { "punct", posix_ispunct },
     164        { "print", isprint },
     165        { "punct", ispunct },
    152166        { "space", isspace },
    153167        { "upper", isupper },
    154         { "xdigit", posix_isxdigit }
     168        { "xdigit", isxdigit }
    155169};
    156170
     
    158172{
    159173        const struct _char_class *class = elem;
    160         return posix_strcmp((const char *) key, class->name);
     174        return strcmp((const char *) key, class->name);
    161175}
    162176
     
    164178{
    165179        /* Search for class in the array of supported character classes. */
    166         const struct _char_class *class = posix_bsearch(cname, _char_classes,
     180        const struct _char_class *class = bsearch(cname, _char_classes,
    167181            sizeof(_char_classes) / sizeof(struct _char_class),
    168182            sizeof(struct _char_class), _class_compare);
     
    324338        const bool special_period = (flags & FNM_PERIOD) != 0;
    325339        const bool noescape = (flags & FNM_NOESCAPE) != 0;
     340        const bool leading_dir = (flags & FNM_LEADING_DIR) != 0;
     341
    326342        const char *s = *string;
    327343        const char *p = *pattern;
    328344
    329         for (; *p != '*'; p++) {
     345        while (*p != '*') {
     346                /* Bracket expression. */
    330347                if (*p == '[') {
    331                         /* Bracket expression. */
    332348                        int matched = _match_bracket_expr(&p, s, flags);
    333349                        if (matched == 0) {
     
    335351                                return false;
    336352                        }
    337                         if (matched == INVALID_PATTERN) {
    338                                 /* Fall through to match [ as an ordinary
    339                                  * character.
    340                                  */
    341                         } else {
     353                        if (matched != INVALID_PATTERN) {
    342354                                s += matched;
    343355                                continue;
    344356                        }
    345                 }
    346 
     357
     358                        assert(matched == INVALID_PATTERN);
     359                        /* Fall through to match [ as an ordinary character. */
     360                }
     361
     362                /* Wildcard match. */
    347363                if (*p == '?') {
    348                         /* Wildcard match. */
    349                         if (*s == '\0' || (pathname && *s == '/') ||
    350                             (special_period && pathname && *s == '.' &&
    351                             *(s - 1) == '/')) {
     364                        if (*s == '\0') {
     365                                /* No character to match. */
    352366                                return false;
    353367                        }
     368                        if (pathname && *s == '/') {
     369                                /* Slash must be matched explicitly. */
     370                                return false;
     371                        }
     372                        if (special_period && pathname &&
     373                            *s == '.' && *(s - 1) == '/') {
     374                                /* Initial period must be matched explicitly. */
     375                                return false;
     376                        }
     377                       
     378                        /* None of the above, match anything else. */
    354379                        p++;
    355380                        s++;
     
    362387                }
    363388
     389                if (*p == '\0') {
     390                        /* End of pattern, must match end of string or
     391                         * an end of subdirectory name (optional).
     392                         */
     393
     394                        if (*s == '\0' || (leading_dir && *s == '/')) {
     395                                break;
     396                        }
     397
     398                        return false;
     399                }
     400
    364401                if (*p == *s) {
    365402                        /* Exact match. */
    366                         if (*s == '\0') {
    367                                 break;
    368                         }
     403                        p++;
     404                        s++;
    369405                        continue;
    370406                }
     
    374410        }
    375411
    376         /* Entire pattern matched. */
     412        /* Entire sub-pattern matched. */
     413       
     414        /* postconditions */
     415        assert(*p == '\0' || *p == '*');
     416        assert(*p != '\0' || *s == '\0' || (leading_dir && *s == '/'));
     417       
    377418        *pattern = p;
    378419        *string = s;
     
    382423static bool _full_match(const char *pattern, const char *string, int flags)
    383424{
     425        const bool pathname = (flags & FNM_PATHNAME) != 0;
    384426        const bool special_period = (flags & FNM_PERIOD) != 0;
     427        const bool leading_dir = (flags & FNM_LEADING_DIR) != 0;
    385428
    386429        if (special_period && *string == '.') {
     
    402445        while (*pattern != '\0') {
    403446                assert(*pattern == '*');
    404 
    405                 while (*pattern == '*') {
    406                         pattern++;
     447                pattern++;
     448
     449                bool matched = false;
     450
     451                const char *end;
     452                if (pathname && special_period &&
     453                    *string == '.' && *(string - 1) == '/') {
     454                        end = string;
     455                } else {
     456                        end= strchrnul(string, pathname ? '/' : '\0');
    407457                }
    408458
    409459                /* Try to match every possible offset. */
    410                 while (*string != '\0') {
     460                while (string <= end) {
    411461                        if (_partial_match(&pattern, &string, flags)) {
     462                                matched = true;
    412463                                break;
    413464                        }
    414465                        string++;
    415466                }
    416         }
    417 
    418         return *string == '\0';
     467
     468                if (matched) {
     469                        continue;
     470                }
     471
     472                return false;
     473        }
     474
     475        return *string == '\0' || (leading_dir && *string == '/');
     476}
     477
     478static char *_casefold(const char *s)
     479{
     480        char *result = strdup(s);
     481        for (char *i = result; *i != '\0'; ++i) {
     482                *i = tolower(*i);
     483        }
     484        return result;
    419485}
    420486
     
    429495int posix_fnmatch(const char *pattern, const char *string, int flags)
    430496{
     497        // TODO: don't fold everything in advance, but only when needed
     498
     499        if ((flags & FNM_CASEFOLD) != 0) {
     500                /* Just fold the entire pattern and string. */
     501                pattern = _casefold(pattern);
     502                string = _casefold(string);
     503        }
     504
    431505        bool result = _full_match(pattern, string, flags);
     506
     507        if ((flags & FNM_CASEFOLD) != 0) {
     508                free((char *) pattern);
     509                free((char *) string);
     510        }
     511
    432512        return result ? 0 : FNM_NOMATCH;
    433513}
    434514
     515// FIXME: put the testcases somewhere else
     516
     517#if 0
     518
     519#include <stdio.h>
     520
     521void __posix_fnmatch_test()
     522{
     523        int fail = 0;
     524
     525        #undef assert
     526        #define assert(x) { if (x) printf("SUCCESS: "#x"\n"); else { printf("FAILED: "#x"\n"); fail++; } }
     527        #define match(s1, s2, flags) assert(posix_fnmatch(s1, s2, flags) == 0)
     528        #define nomatch(s1, s2, flags) assert(posix_fnmatch(s1, s2, flags) == FNM_NOMATCH)
     529
     530        assert(FNM_PATHNAME == FNM_FILE_NAME);
     531        match("", "", 0);
     532        match("*", "hello", 0);
     533        match("hello", "hello", 0);
     534        match("hello*", "hello", 0);
     535        nomatch("hello?", "hello", 0);
     536        match("*hello", "prdel hello", 0);
     537        match("he[sl]lo", "hello", 0);
     538        match("he[sl]lo", "heslo", 0);
     539        nomatch("he[sl]lo", "heblo", 0);
     540        nomatch("he[^sl]lo", "hello", 0);
     541        nomatch("he[^sl]lo", "heslo", 0);
     542        match("he[^sl]lo", "heblo", 0);
     543        nomatch("he[!sl]lo", "hello", 0);
     544        nomatch("he[!sl]lo", "heslo", 0);
     545        match("he[!sl]lo", "heblo", 0);
     546        match("al*[c-t]a*vis*ta", "alheimer talir jehovista", 0);
     547        match("al*[c-t]a*vis*ta", "alfons had jehovista", 0);
     548        match("[a-ce-z]", "a", 0);
     549        match("[a-ce-z]", "c", 0);
     550        nomatch("[a-ce-z]", "d", 0);
     551        match("[a-ce-z]", "e", 0);
     552        match("[a-ce-z]", "z", 0);
     553        nomatch("[^a-ce-z]", "a", 0);
     554        nomatch("[^a-ce-z]", "c", 0);
     555        match("[^a-ce-z]", "d", 0);
     556        nomatch("[^a-ce-z]", "e", 0);
     557        nomatch("[^a-ce-z]", "z", 0);
     558        match("helen??", "helenos", 0);
     559        match("****booo****", "booo", 0);
     560       
     561        match("hello[[:space:]]world", "hello world", 0);
     562        nomatch("hello[[:alpha:]]world", "hello world", 0);
     563       
     564        match("/hoooo*", "/hooooooo/hooo", 0);
     565        nomatch("/hoooo*", "/hooooooo/hooo", FNM_PATHNAME);
     566        nomatch("/hoooo*/", "/hooooooo/hooo", FNM_PATHNAME);
     567        match("/hoooo*/*", "/hooooooo/hooo", FNM_PATHNAME);
     568        match("/hoooo*/hooo", "/hooooooo/hooo", FNM_PATHNAME);
     569        match("/hoooo*", "/hooooooo/hooo", FNM_PATHNAME | FNM_LEADING_DIR);
     570        nomatch("/hoooo*/", "/hooooooo/hooo", FNM_PATHNAME | FNM_LEADING_DIR);
     571        nomatch("/hoooo", "/hooooooo/hooo", FNM_LEADING_DIR);
     572        match("/hooooooo", "/hooooooo/hooo", FNM_LEADING_DIR);
     573       
     574        match("*", "hell", 0);
     575        match("*?", "hell", 0);
     576        match("?*?", "hell", 0);
     577        match("?*??", "hell", 0);
     578        match("??*??", "hell", 0);
     579        nomatch("???*??", "hell", 0);
     580       
     581        nomatch("", "hell", 0);
     582        nomatch("?", "hell", 0);
     583        nomatch("??", "hell", 0);
     584        nomatch("???", "hell", 0);
     585        match("????", "hell", 0);
     586       
     587        match("*", "h.ello", FNM_PERIOD);
     588        match("*", "h.ello", FNM_PATHNAME | FNM_PERIOD);
     589        nomatch("*", ".hello", FNM_PERIOD);
     590        match("h?ello", "h.ello", FNM_PERIOD);
     591        nomatch("?hello", ".hello", FNM_PERIOD);
     592        match("/home/user/.*", "/home/user/.hello", FNM_PATHNAME | FNM_PERIOD);
     593        match("/home/user/*", "/home/user/.hello", FNM_PERIOD);
     594        nomatch("/home/user/*", "/home/user/.hello", FNM_PATHNAME | FNM_PERIOD);
     595
     596        nomatch("HeLlO", "hello", 0);
     597        match("HeLlO", "hello", FNM_CASEFOLD);
     598
     599        printf("Failed: %d\n", fail);
     600}
     601
     602#endif
     603
    435604/** @}
    436605 */
Note: See TracChangeset for help on using the changeset viewer.