← Commit list

997f66e465

Joshua Rogers
Joshua Rogers
2026-09-11
SUCCESS Duration: 402s

Subject

fnmatch: replace recursive matcher with iterative greedy algorithm

Binary

No binary (build failed)

Architecture & Compiler Flags

Architecture: x86_64-linux-gnu Compiler: gcc (Ubuntu 11.4.0-1ubuntu1~22.04.3) 11.4.0

—

Build Log

(log yok)

Commit Diff GitHub →

lib/curl_fnmatch.c +108 -75tests/unit/unit1307.c +4 -1
lib/curl_fnmatch.c+108 -75
@@ -248,99 +248,132 @@ fail:
return SETCHARSET_FAIL;
}
-static int loop(const unsigned char *pattern, const unsigned char *string,
- int maxstars)
+/* match one pattern token against one string character, advancing both */
+static int matchtoken(const unsigned char **pp, const unsigned char **sp)
+{
+ const unsigned char *p = *pp;
+ const unsigned char *s = *sp;
+
+ switch(*p) {
+ case '?':
+ break;
+ case '\\':
+ if(p[1])
+ p++;
+ if(*s != *p)
+ return 0;
+ break;
+ case '[': {
+ unsigned char charset[CURLFNM_CHSET_SIZE];
+ const unsigned char *pp2 = p + 1; /* Copy in case of syntax error. */
+ bool found = FALSE;
+ if(!setcharset(&pp2, charset))
+ return -1; /* Syntax error in set; mismatch! */
+ if(charset[(unsigned int)*s])
+ found = TRUE;
+ else if(charset[CURLFNM_ALNUM])
+ found = ISALNUM(*s);
+ else if(charset[CURLFNM_ALPHA])
+ found = ISALPHA(*s);
+ else if(charset[CURLFNM_DIGIT])
+ found = ISDIGIT(*s);
+ else if(charset[CURLFNM_XDIGIT])
+ found = ISXDIGIT(*s);
+ else if(charset[CURLFNM_PRINT])
+ found = ISPRINT(*s);
+ else if(charset[CURLFNM_SPACE])
+ found = ISBLANK(*s);
+ else if(charset[CURLFNM_UPPER])
+ found = ISUPPER(*s);
+ else if(charset[CURLFNM_LOWER])
+ found = ISLOWER(*s);
+ else if(charset[CURLFNM_BLANK])
+ found = ISBLANK(*s);
+ else if(charset[CURLFNM_GRAPH])
+ found = ISGRAPH(*s);
+
+ if(charset[CURLFNM_NEGATE])
+ found = !found;
+
+ if(!found)
+ return 0;
+ *pp = pp2 + 1;
+ *sp = s + 1;
+ return 1;
+ }
+ default:
+ if(*p != *s)
+ return 0;
+ break;
+ }
+ *pp = p + 1;
+ *sp = s + 1;
+ return 1;
+}
+
+/* greedy match with backtracking to the most recent '*' */
+static int loop(const unsigned char *pattern, const unsigned char *string)
{
const unsigned char *p = pattern;
const unsigned char *s = string;
- unsigned char charset[CURLFNM_CHSET_SIZE] = { 0 };
-
- for(;;) {
- const unsigned char *pp;
+ const unsigned char *star_p = NULL;
+ const unsigned char *star_s = NULL;
+ int maxstars = 2;
- switch(*p) {
- case '*':
+ while(*s) {
+ if(*p == '*') {
if(!maxstars)
return CURL_FNMATCH_NOMATCH;
- /* Regroup consecutive stars and question marks. This can be done because
- '*?*?*' can be expressed as '??*'. */
+ maxstars--;
for(;;) {
- if(*++p == '\0')
+ p++;
+ if(!*p)
return CURL_FNMATCH_MATCH;
if(*p == '?') {
- if(!*s++)
+ if(!*s)
return CURL_FNMATCH_NOMATCH;
+ s++;
}
else if(*p != '*')
break;
}
- /* Skip string characters until we find a match with pattern suffix. */
- for(maxstars--; *s; s++) {
- if(loop(p, s, maxstars) == CURL_FNMATCH_MATCH)
- return CURL_FNMATCH_MATCH;
- }
- return CURL_FNMATCH_NOMATCH;
- case '?':
- if(!*s)
- return CURL_FNMATCH_NOMATCH;
- s++;
- p++;
- break;
- case '\0':
- return *s ? CURL_FNMATCH_NOMATCH : CURL_FNMATCH_MATCH;
- case '\\':
- if(p[1])
- p++;
- if(*s++ != *p++)
+ star_p = p;
+ star_s = s;
+ }
+ else if(*p) {
+ const unsigned char *np = p;
+ const unsigned char *ns = s;
+ int r = matchtoken(&np, &ns);
+ if(r < 0)
return CURL_FNMATCH_NOMATCH;
- break;
- case '[':
- pp = p + 1; /* Copy in case of syntax error in set. */
- if(setcharset(&pp, charset)) {
- bool found = FALSE;
- if(!*s)
- return CURL_FNMATCH_NOMATCH;
- if(charset[(unsigned int)*s])
- found = TRUE;
- else if(charset[CURLFNM_ALNUM])
- found = ISALNUM(*s);
- else if(charset[CURLFNM_ALPHA])
- found = ISALPHA(*s);
- else if(charset[CURLFNM_DIGIT])
- found = ISDIGIT(*s);
- else if(charset[CURLFNM_XDIGIT])
- found = ISXDIGIT(*s);
- else if(charset[CURLFNM_PRINT])
- found = ISPRINT(*s);
- else if(charset[CURLFNM_SPACE])
- found = ISBLANK(*s);
- else if(charset[CURLFNM_UPPER])
- found = ISUPPER(*s);
- else if(charset[CURLFNM_LOWER])
- found = ISLOWER(*s);
- else if(charset[CURLFNM_BLANK])
- found = ISBLANK(*s);
- else if(charset[CURLFNM_GRAPH])
- found = ISGRAPH(*s);
-
- if(charset[CURLFNM_NEGATE])
- found = !found;
-
- if(!found)
- return CURL_FNMATCH_NOMATCH;
- p = pp + 1;
- s++;
- break;
+ if(r) {
+ p = np;
+ s = ns;
+ continue;
}
- /* Syntax error in set; mismatch! */
- return CURL_FNMATCH_NOMATCH;
-
- default:
- if(*p++ != *s++)
+ if(!star_p)
return CURL_FNMATCH_NOMATCH;
- break;
+ p = star_p;
+ s = ++star_s;
}
+ else if(star_p) {
+ p = star_p;
+ s = ++star_s;
+ }
+ else
+ return CURL_FNMATCH_NOMATCH;
+ }
+ while(*p == '*') {
+ if(!maxstars)
+ return CURL_FNMATCH_NOMATCH;
+ maxstars--;
+ do {
+ p++;
+ if(*p == '?')
+ return CURL_FNMATCH_NOMATCH;
+ } while(*p == '*');
}
+ return *p ? CURL_FNMATCH_NOMATCH : CURL_FNMATCH_MATCH;
}
/*
@@ -354,7 +387,7 @@ int Curl_fnmatch(void *ptr, const char *pattern, const char *string)
return CURL_FNMATCH_FAIL;
}
return loop((const unsigned char *)pattern,
- (const unsigned char *)string, 2);
+ (const unsigned char *)string);
}
#else /* HAVE_FNMATCH */
tests/unit/unit1307.c+4 -1
@@ -43,8 +43,8 @@
#define MAC_DIFFER 0x40
#define MAC_SHIFT 16
-#if 0
#define MAC_MATCH ((CURL_FNMATCH_MATCH << MAC_SHIFT) | MAC_DIFFER)
+#if 0
#define MAC_NOMATCH ((CURL_FNMATCH_NOMATCH << MAC_SHIFT) | MAC_DIFFER)
#endif
#define MAC_FAIL ((CURL_FNMATCH_FAIL << MAC_SHIFT) | MAC_DIFFER)
@@ -219,6 +219,9 @@ static CURLcode test_unit1307(const char *arg)
{ "***.txt", "t.txt", MATCH },
{ "****.txt", ".txt", MATCH },
+ /* custom matcher limits wildcard star groups */
+ { "*a*b*c", "abc", NOMATCH|LINUX_MATCH|MAC_MATCH },
+
/* empty string or pattern */
{ "", "", MATCH },
{ "", "hello", NOMATCH },