Date: Sun, 25 Oct 2015 21:39:23 +0000 (UTC) From: Jilles Tjoelker <jilles@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-stable@freebsd.org, svn-src-stable-10@freebsd.org Subject: svn commit: r289943 - stable/10/lib/libc/gen Message-ID: <201510252139.t9PLdNJL099204@repo.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: jilles Date: Sun Oct 25 21:39:23 2015 New Revision: 289943 URL: https://svnweb.freebsd.org/changeset/base/289943 Log: 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. Modified: stable/10/lib/libc/gen/fnmatch.c Directory Properties: stable/10/ (props changed) Modified: stable/10/lib/libc/gen/fnmatch.c ============================================================================== --- stable/10/lib/libc/gen/fnmatch.c Sun Oct 25 19:55:48 2015 (r289942) +++ stable/10/lib/libc/gen/fnmatch.c Sun Oct 25 21:39:23 2015 (r289943) @@ -91,11 +91,14 @@ fnmatch1(pattern, string, stringstart, f 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, f 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, f 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, f 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, f pattern = newp; break; case RANGE_NOMATCH: - return (FNM_NOMATCH); + goto backtrack; } string += sclen; break; @@ -199,14 +195,39 @@ fnmatch1(pattern, string, stringstart, f /* 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; } }
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201510252139.t9PLdNJL099204>