From owner-svn-src-stable@FreeBSD.ORG Wed Mar 21 23:10:17 2012 Return-Path: Delivered-To: svn-src-stable@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 9B4E11065673; Wed, 21 Mar 2012 23:10:17 +0000 (UTC) (envelope-from jilles@FreeBSD.org) Received: from svn.freebsd.org (svn.freebsd.org [IPv6:2001:4f8:fff6::2c]) by mx1.freebsd.org (Postfix) with ESMTP id 856468FC17; Wed, 21 Mar 2012 23:10:17 +0000 (UTC) Received: from svn.freebsd.org (localhost [127.0.0.1]) by svn.freebsd.org (8.14.4/8.14.4) with ESMTP id q2LNAHtX097391; Wed, 21 Mar 2012 23:10:17 GMT (envelope-from jilles@svn.freebsd.org) Received: (from jilles@localhost) by svn.freebsd.org (8.14.4/8.14.4/Submit) id q2LNAHLd097389; Wed, 21 Mar 2012 23:10:17 GMT (envelope-from jilles@svn.freebsd.org) Message-Id: <201203212310.q2LNAHLd097389@svn.freebsd.org> From: Jilles Tjoelker Date: Wed, 21 Mar 2012 23:10:17 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-stable@freebsd.org, svn-src-stable-9@freebsd.org X-SVN-Group: stable-9 MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Cc: Subject: svn commit: r233289 - stable/9/bin/sh X-BeenThere: svn-src-stable@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: SVN commit messages for all the -stable branches of the src tree List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 21 Mar 2012 23:10:17 -0000 Author: jilles Date: Wed Mar 21 23:10:16 2012 New Revision: 233289 URL: http://svn.freebsd.org/changeset/base/233289 Log: MFC r229201: sh: Make patmatch() non-recursive. Modified: stable/9/bin/sh/expand.c Directory Properties: stable/9/bin/sh/ (props changed) Modified: stable/9/bin/sh/expand.c ============================================================================== --- stable/9/bin/sh/expand.c Wed Mar 21 20:55:21 2012 (r233288) +++ stable/9/bin/sh/expand.c Wed Mar 21 23:10:16 2012 (r233289) @@ -1440,57 +1440,63 @@ static 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; @@ -1502,7 +1508,7 @@ patmatch(const char *pattern, const char for (;;) { while (*endp == CTLQUOTEMARK) endp++; - if (*endp == '\0') + if (*endp == 0) goto dft; /* no matching ] */ if (*endp == CTLESC) endp++; @@ -1517,12 +1523,14 @@ patmatch(const char *pattern, const char 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) @@ -1563,21 +1571,34 @@ patmatch(const char *pattern, const char } } 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; }