From e678bd4b4289e536e998057bf9a9cf415f21b74c Mon Sep 17 00:00:00 2001 From: David Oberhollenzer Date: Sat, 20 Mar 2021 17:35:41 +0100 Subject: Add libcompat fallback implementation for fnmatch This has basically been copied over from Musl and slightly modifed. Signed-off-by: David Oberhollenzer --- lib/compat/Makemodule.am | 1 + lib/compat/fnmatch.c | 305 ++++++++++++++++++++++++++++++++++++++++++ lib/fstree/fstree_from_file.c | 2 +- 3 files changed, 307 insertions(+), 1 deletion(-) create mode 100644 lib/compat/fnmatch.c (limited to 'lib') diff --git a/lib/compat/Makemodule.am b/lib/compat/Makemodule.am index 4f4fc9c..6c3c2b4 100644 --- a/lib/compat/Makemodule.am +++ b/lib/compat/Makemodule.am @@ -3,5 +3,6 @@ libcompat_a_SOURCES += lib/compat/strndup.c lib/compat/mockups.c libcompat_a_SOURCES += lib/compat/chdir.c include/compat.h libcompat_a_SOURCES += lib/compat/path_to_windows.c libcompat_a_SOURCES += lib/compat/w32_perror.c +libcompat_a_SOURCES += lib/compat/fnmatch.c noinst_LIBRARIES += libcompat.a diff --git a/lib/compat/fnmatch.c b/lib/compat/fnmatch.c new file mode 100644 index 0000000..ed4dde1 --- /dev/null +++ b/lib/compat/fnmatch.c @@ -0,0 +1,305 @@ +/* + * An implementation of what I call the "Sea of Stars" algorithm for + * POSIX fnmatch(). The basic idea is that we factor the pattern into + * a head component (which we match first and can reject without ever + * measuring the length of the string), an optional tail component + * (which only exists if the pattern contains at least one star), and + * an optional "sea of stars", a set of star-separated components + * between the head and tail. After the head and tail matches have + * been removed from the input string, the components in the "sea of + * stars" are matched sequentially by searching for their first + * occurrence past the end of the previous match. + * + * - Rich Felker, April 2012 + */ + +#include "compat.h" + +#include +#include + +#ifndef HAVE_FNMATCH +#define END 0 +#define UNMATCHABLE -2 +#define BRACKET -3 +#define QUESTION -4 +#define STAR -5 + +static int str_next(const char *str, size_t n, size_t *step) +{ + if (!n) { + *step = 0; + return 0; + } + if (str[0] >= 128U) { + wchar_t wc; + int k = mbtowc(&wc, str, n); + if (k<0) { + *step = 1; + return -1; + } + *step = k; + return wc; + } + *step = 1; + return str[0]; +} + +static int pat_next(const char *pat, size_t m, size_t *step) +{ + int esc = 0; + if (!m || !*pat) { + *step = 0; + return END; + } + *step = 1; + if (pat[0]=='\\' && pat[1]) { + *step = 2; + pat++; + esc = 1; + goto escaped; + } + if (pat[0]=='[') { + size_t k = 1; + if (k= 128U) { + wchar_t wc; + int k = mbtowc(&wc, pat, m); + if (k<0) { + *step = 0; + return UNMATCHABLE; + } + *step = k + esc; + return wc; + } + return pat[0]; +} + +static int match_bracket(const char *p, int k, int kfold) +{ + wchar_t wc; + int inv = 0; + p++; + if (*p=='^' || *p=='!') { + inv = 1; + p++; + } + if (*p==']') { + if (k==']') return !inv; + p++; + } else if (*p=='-') { + if (k=='-') return !inv; + p++; + } + wc = p[-1]; + for (; *p != ']'; p++) { + if (p[0]=='-' && p[1]!=']') { + wchar_t wc2; + int l = mbtowc(&wc2, p+1, 4); + if (l < 0) return 0; + if (wc <= wc2) + if ((unsigned)k-wc <= wc2-wc || + (unsigned)kfold-wc <= wc2-wc) + return !inv; + p += l-1; + continue; + } + if (p[0]=='[' && (p[1]==':' || p[1]=='.' || p[1]=='=')) { + const char *p0 = p+2; + int z = p[1]; + p+=3; + while (p[-1]!=z || p[0]!=']') p++; + if (z == ':' && p-1-p0 < 16) { + char buf[16]; + memcpy(buf, p0, p-1-p0); + buf[p-1-p0] = 0; + if (iswctype(k, wctype(buf)) || + iswctype(kfold, wctype(buf))) + return !inv; + } + continue; + } + if (*p < 128U) { + wc = (unsigned char)*p; + } else { + int l = mbtowc(&wc, p, 4); + if (l < 0) return 0; + p += l-1; + } + if (wc==k || wc==kfold) return !inv; + } + return inv; +} + +static int fnmatch_internal(const char *pat, size_t m, const char *str, size_t n) +{ + const char *p, *ptail, *endpat; + const char *s, *stail, *endstr; + size_t pinc, sinc, tailcnt=0; + int c, k, kfold; + + for (;;) { + switch ((c = pat_next(pat, m, &pinc))) { + case UNMATCHABLE: + return FNM_NOMATCH; + case STAR: + pat++; + m--; + break; + default: + k = str_next(str, n, &sinc); + if (k <= 0) + return (c==END) ? 0 : FNM_NOMATCH; + str += sinc; + n -= sinc; + kfold = k; + if (c == BRACKET) { + if (!match_bracket(pat, k, kfold)) + return FNM_NOMATCH; + } else if (c != QUESTION && k != c && kfold != c) { + return FNM_NOMATCH; + } + pat+=pinc; + m-=pinc; + continue; + } + break; + } + + /* Compute real pat length if it was initially unknown/-1 */ + m = strnlen(pat, m); + endpat = pat + m; + + /* Find the last * in pat and count chars needed after it */ + for (p=ptail=pat; pstr && tailcnt; tailcnt--) { + if (s[-1] < 128U || MB_CUR_MAX==1) s--; + else while ((unsigned char)*--s-0x80U<0x40 && s>str); + } + if (tailcnt) return FNM_NOMATCH; + stail = s; + + /* Check that the pat and str tails match */ + p = ptail; + for (;;) { + c = pat_next(p, endpat-p, &pinc); + p += pinc; + if ((k = str_next(s, endstr-s, &sinc)) <= 0) { + if (c != END) return FNM_NOMATCH; + break; + } + s += sinc; + kfold = k; + if (c == BRACKET) { + if (!match_bracket(p-pinc, k, kfold)) + return FNM_NOMATCH; + } else if (c != QUESTION && k != c && kfold != c) { + return FNM_NOMATCH; + } + } + + /* We're all done with the tails now, so throw them out */ + endstr = stail; + endpat = ptail; + + /* Match pattern components until there are none left */ + while (pat 0) str += sinc; + else for (str++; str_next(str, endstr-str, &sinc)<0; str++); + } + + return 0; +} + +int fnmatch(const char *pat, const char *str, int flags) +{ + const char *s, *p; + size_t inc; + int c; + if (flags & FNM_PATHNAME) for (;;) { + for (s=str; *s && *s!='/'; s++); + for (p=pat; (c=pat_next(p, -1, &inc))!=END && c!='/'; p+=inc); + if (c!=*s) + return FNM_NOMATCH; + if (fnmatch_internal(pat, p-pat, str, s-str)) + return FNM_NOMATCH; + if (!c) return 0; + str = s+1; + pat = p+inc; + } + return fnmatch_internal(pat, -1, str, -1); +} +#endif /* HAVE_FNMATCH */ diff --git a/lib/fstree/fstree_from_file.c b/lib/fstree/fstree_from_file.c index 9a34b36..dd7ca22 100644 --- a/lib/fstree/fstree_from_file.c +++ b/lib/fstree/fstree_from_file.c @@ -8,8 +8,8 @@ #include "fstree.h" #include "fstream.h" +#include "compat.h" -#include #include #include #include -- cgit v1.2.3