Author: jilles
Date: Sun Sep 27 12:52:18 2015
New Revision: 288309
URL: https://svnweb.freebsd.org/changeset/base/288309
Log:
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:
head/lib/libc/gen/fnmatch.c
Modified: head/lib/libc/gen/fnmatch.c
==============================================================================
--- head/lib/libc/gen/fnmatch.c Sun Sep 27 12:19:36 2015 (r288308)
+++ head/lib/libc/gen/fnmatch.c Sun Sep 27 12:52:18 2015 (r288309)
@@ -87,11 +87,14 @@ static int
fnmatch1(const char *pattern, const char *string, const char *stringstart,
int flags, mbstate_t patmbs, mbstate_t 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)
@@ -107,16 +110,18 @@ fnmatch1(const char *pattern, const char
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 '*':
@@ -128,7 +133,7 @@ fnmatch1(const char *pattern, const char
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)
@@ -144,33 +149,24 @@ fnmatch1(const char *pattern, const char
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)) {
@@ -180,7 +176,7 @@ fnmatch1(const char *pattern, const char
pattern = newp;
break;
case RANGE_NOMATCH:
- return (FNM_NOMATCH);
+ goto backtrack;
}
string += sclen;
break;
@@ -195,14 +191,39 @@ fnmatch1(const char *pattern, const char
/* 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;
}
}
_______________________________________________
svn-src-head@freebsd.org mailing list
https://lists.freebsd.org/mailman/listinfo/svn-src-head
To unsubscribe, send any mail to "svn-src-head-unsubscr...@freebsd.org"
