diff options
author | jilles <jilles@FreeBSD.org> | 2012-01-01 20:50:19 +0000 |
---|---|---|
committer | jilles <jilles@FreeBSD.org> | 2012-01-01 20:50:19 +0000 |
commit | 109579dd42f40c0f666f87c45fb3397c55adfe97 (patch) | |
tree | 2ef52c3e9046c8265d517f9820bf78c10d56b9df /bin | |
parent | 2dd2060131bbfd7b617356a2384aa027270c3b9d (diff) | |
download | FreeBSD-src-109579dd42f40c0f666f87c45fb3397c55adfe97.zip FreeBSD-src-109579dd42f40c0f666f87c45fb3397c55adfe97.tar.gz |
sh: Make patmatch() non-recursive.
Diffstat (limited to 'bin')
-rw-r--r-- | bin/sh/expand.c | 95 |
1 files changed, 58 insertions, 37 deletions
diff --git a/bin/sh/expand.c b/bin/sh/expand.c index 75dcf5c..197be7e 100644 --- a/bin/sh/expand.c +++ b/bin/sh/expand.c @@ -1445,57 +1445,63 @@ int patmatch(const char *pattern, const char *string, int squoted) { const char *p, *q, *end; + const char *bt_p, *bt_q; char c; wchar_t wc, wc2; p = pattern; q = string; + bt_p = NULL; + bt_q = NULL; for (;;) { switch (c = *p++) { case '\0': - goto breakloop; + if (*q != '\0') + goto backtrack; + return 1; case CTLESC: if (squoted && *q == CTLESC) q++; if (*q++ != *p++) - return 0; + goto backtrack; break; case CTLQUOTEMARK: continue; case '?': if (squoted && *q == CTLESC) q++; - if (localeisutf8) + if (*q == '\0') + return 0; + if (localeisutf8) { wc = get_wc(&q); - else + /* + * A '?' does not match invalid UTF-8 but a + * '*' does, so backtrack. + */ + if (wc == 0) + goto backtrack; + } else wc = (unsigned char)*q++; - if (wc == '\0') - return 0; break; case '*': c = *p; while (c == CTLQUOTEMARK || c == '*') c = *++p; - if (c != CTLESC && c != CTLQUOTEMARK && - c != '?' && c != '*' && c != '[') { - while (*q != c) { - if (squoted && *q == CTLESC && - q[1] == c) - break; - if (*q == '\0') - return 0; - if (squoted && *q == CTLESC) - q++; - q++; - } - } - do { - if (patmatch(p, q, squoted)) - return 1; - if (squoted && *q == CTLESC) - q++; - } while (*q++ != '\0'); - return 0; + /* + * If the pattern ends here, we know the string + * matches without needing to look at the rest of it. + */ + if (c == '\0') + return 1; + /* + * 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_p = p; + bt_q = q; + break; case '[': { const char *endp; int invert, found; @@ -1507,7 +1513,7 @@ patmatch(const char *pattern, const char *string, int squoted) for (;;) { while (*endp == CTLQUOTEMARK) endp++; - if (*endp == '\0') + if (*endp == 0) goto dft; /* no matching ] */ if (*endp == CTLESC) endp++; @@ -1522,12 +1528,14 @@ patmatch(const char *pattern, const char *string, int squoted) found = 0; if (squoted && *q == CTLESC) q++; - if (localeisutf8) + if (*q == '\0') + return 0; + if (localeisutf8) { chr = get_wc(&q); - else + if (chr == 0) + goto backtrack; + } else chr = (unsigned char)*q++; - if (chr == '\0') - return 0; c = *p++; do { if (c == CTLQUOTEMARK) @@ -1568,21 +1576,34 @@ patmatch(const char *pattern, const char *string, int squoted) } } while ((c = *p++) != ']'); if (found == invert) - return 0; + goto backtrack; break; } dft: default: if (squoted && *q == CTLESC) q++; - if (*q++ != c) + if (*q == '\0') + return 0; + if (*q++ == c) + break; +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_p == NULL) + return 0; + if (squoted && *bt_q == CTLESC) + bt_q++; + if (*bt_q == '\0') return 0; + bt_q++; + p = bt_p; + q = bt_q; break; } } -breakloop: - if (*q != '\0') - return 0; - return 1; } |