diff options
author | jilles <jilles@FreeBSD.org> | 2015-10-25 21:39:23 +0000 |
---|---|---|
committer | jilles <jilles@FreeBSD.org> | 2015-10-25 21:39:23 +0000 |
commit | f733542c6cc57cf57b34b0e78fe737ad7c882794 (patch) | |
tree | 2ffe8b4424462da40227d81685a89b9da04d2ee2 /lib/libc | |
parent | aff97c8f1f5dfb2c92a3497ef0dfdc9f5068361b (diff) | |
download | FreeBSD-src-f733542c6cc57cf57b34b0e78fe737ad7c882794.zip FreeBSD-src-f733542c6cc57cf57b34b0e78fe737ad7c882794.tar.gz |
MFC r288309: fnmatch(): Remove exponential behaviour as in sh r229201.
The old code was exponential in the number of asterisks in the pattern.
However, once a match has been found upto the next asterisk, the previous
asterisks are no longer relevant.
Diffstat (limited to 'lib/libc')
-rw-r--r-- | lib/libc/gen/fnmatch.c | 77 |
1 files changed, 49 insertions, 28 deletions
diff --git a/lib/libc/gen/fnmatch.c b/lib/libc/gen/fnmatch.c index 47d0a41..db0bf89 100644 --- a/lib/libc/gen/fnmatch.c +++ b/lib/libc/gen/fnmatch.c @@ -91,11 +91,14 @@ fnmatch1(pattern, string, stringstart, flags, patmbs, strmbs) int flags; mbstate_t patmbs, strmbs; { + const char *bt_pattern, *bt_string; + mbstate_t bt_patmbs, bt_strmbs; char *newp; char c; wchar_t pc, sc; size_t pclen, sclen; + bt_pattern = bt_string = NULL; for (;;) { pclen = mbrtowc(&pc, pattern, MB_LEN_MAX, &patmbs); if (pclen == (size_t)-1 || pclen == (size_t)-2) @@ -111,16 +114,18 @@ fnmatch1(pattern, string, stringstart, flags, patmbs, strmbs) case EOS: if ((flags & FNM_LEADING_DIR) && sc == '/') return (0); - return (sc == EOS ? 0 : FNM_NOMATCH); + if (sc == EOS) + return (0); + goto backtrack; case '?': if (sc == EOS) return (FNM_NOMATCH); if (sc == '/' && (flags & FNM_PATHNAME)) - return (FNM_NOMATCH); + goto backtrack; if (sc == '.' && (flags & FNM_PERIOD) && (string == stringstart || ((flags & FNM_PATHNAME) && *(string - 1) == '/'))) - return (FNM_NOMATCH); + goto backtrack; string += sclen; break; case '*': @@ -132,7 +137,7 @@ fnmatch1(pattern, string, stringstart, flags, patmbs, strmbs) if (sc == '.' && (flags & FNM_PERIOD) && (string == stringstart || ((flags & FNM_PATHNAME) && *(string - 1) == '/'))) - return (FNM_NOMATCH); + goto backtrack; /* Optimize for pattern with * at end or before /. */ if (c == EOS) @@ -148,33 +153,24 @@ fnmatch1(pattern, string, stringstart, flags, patmbs, strmbs) break; } - /* General case, use recursion. */ - while (sc != EOS) { - if (!fnmatch1(pattern, string, stringstart, - flags, patmbs, strmbs)) - return (0); - sclen = mbrtowc(&sc, string, MB_LEN_MAX, - &strmbs); - if (sclen == (size_t)-1 || - sclen == (size_t)-2) { - sc = (unsigned char)*string; - sclen = 1; - memset(&strmbs, 0, sizeof(strmbs)); - } - if (sc == '/' && flags & FNM_PATHNAME) - break; - string += sclen; - } - return (FNM_NOMATCH); + /* + * First try the shortest match for the '*' that + * could work. We can forget any earlier '*' since + * there is no way having it match more characters + * can help us, given that we are already here. + */ + bt_pattern = pattern, bt_patmbs = patmbs; + bt_string = string, bt_strmbs = strmbs; + break; case '[': if (sc == EOS) return (FNM_NOMATCH); if (sc == '/' && (flags & FNM_PATHNAME)) - return (FNM_NOMATCH); + goto backtrack; if (sc == '.' && (flags & FNM_PERIOD) && (string == stringstart || ((flags & FNM_PATHNAME) && *(string - 1) == '/'))) - return (FNM_NOMATCH); + goto backtrack; switch (rangematch(pattern, sc, flags, &newp, &patmbs)) { @@ -184,7 +180,7 @@ fnmatch1(pattern, string, stringstart, flags, patmbs, strmbs) pattern = newp; break; case RANGE_NOMATCH: - return (FNM_NOMATCH); + goto backtrack; } string += sclen; break; @@ -199,14 +195,39 @@ fnmatch1(pattern, string, stringstart, flags, patmbs, strmbs) /* FALLTHROUGH */ default: norm: + string += sclen; if (pc == sc) ; else if ((flags & FNM_CASEFOLD) && (towlower(pc) == towlower(sc))) ; - else - return (FNM_NOMATCH); - string += sclen; + else { + backtrack: + /* + * If we have a mismatch (other than hitting + * the end of the string), go back to the last + * '*' seen and have it match one additional + * character. + */ + if (bt_pattern == NULL) + return (FNM_NOMATCH); + sclen = mbrtowc(&sc, bt_string, MB_LEN_MAX, + &bt_strmbs); + if (sclen == (size_t)-1 || + sclen == (size_t)-2) { + sc = (unsigned char)*bt_string; + sclen = 1; + memset(&bt_strmbs, 0, + sizeof(bt_strmbs)); + } + if (sc == EOS) + return (FNM_NOMATCH); + if (sc == '/' && flags & FNM_PATHNAME) + return (FNM_NOMATCH); + bt_string += sclen; + pattern = bt_pattern, patmbs = bt_patmbs; + string = bt_string, strmbs = bt_strmbs; + } break; } } |