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;
}
}
_______________________________________________
svn-src-stable-10@freebsd.org mailing list
https://lists.freebsd.org/mailman/listinfo/svn-src-stable-10
To unsubscribe, send any mail to "svn-src-stable-10-unsubscr...@freebsd.org"
