summaryrefslogtreecommitdiffstats
path: root/bin/sh
diff options
context:
space:
mode:
authorjilles <jilles@FreeBSD.org>2012-01-01 20:50:19 +0000
committerjilles <jilles@FreeBSD.org>2012-01-01 20:50:19 +0000
commit109579dd42f40c0f666f87c45fb3397c55adfe97 (patch)
tree2ef52c3e9046c8265d517f9820bf78c10d56b9df /bin/sh
parent2dd2060131bbfd7b617356a2384aa027270c3b9d (diff)
downloadFreeBSD-src-109579dd42f40c0f666f87c45fb3397c55adfe97.zip
FreeBSD-src-109579dd42f40c0f666f87c45fb3397c55adfe97.tar.gz
sh: Make patmatch() non-recursive.
Diffstat (limited to 'bin/sh')
-rw-r--r--bin/sh/expand.c95
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;
}
OpenPOWER on IntegriCloud