diff options
| author | christos <christos@NetBSD.org> | 2021-02-23 22:14:59 +0000 |
|---|---|---|
| committer | christos <christos@NetBSD.org> | 2021-02-23 22:14:59 +0000 |
| commit | bfebdf2c643a82fdcdd30777e262587ad110fbbe (patch) | |
| tree | 613d2a000e5796ad815949c48ed406c97a9290d0 /lib/libc/regex | |
| parent | c2e378cee20c8d688168cec79ecc1bd8214a95aa (diff) | |
sync with FreeBSD:
- NLS support
- GNU extensions
- bug fixes
Diffstat (limited to 'lib/libc/regex')
| -rw-r--r-- | lib/libc/regex/cclass.h | 104 | ||||
| -rw-r--r-- | lib/libc/regex/cname.h | 237 | ||||
| -rw-r--r-- | lib/libc/regex/engine.c | 807 | ||||
| -rw-r--r-- | lib/libc/regex/re_format.7 | 451 | ||||
| -rw-r--r-- | lib/libc/regex/regcomp.c | 2186 | ||||
| -rw-r--r-- | lib/libc/regex/regerror.c | 142 | ||||
| -rw-r--r-- | lib/libc/regex/regex.3 | 520 | ||||
| -rw-r--r-- | lib/libc/regex/regex2.h | 195 | ||||
| -rw-r--r-- | lib/libc/regex/regexec.c | 170 | ||||
| -rw-r--r-- | lib/libc/regex/regfree.c | 77 | ||||
| -rw-r--r-- | lib/libc/regex/utils.h | 47 |
11 files changed, 2744 insertions, 2192 deletions
diff --git a/lib/libc/regex/cclass.h b/lib/libc/regex/cclass.h deleted file mode 100644 index 3ab2ccba47c..00000000000 --- a/lib/libc/regex/cclass.h +++ /dev/null @@ -1,104 +0,0 @@ -/* $NetBSD: cclass.h,v 1.7 2003/08/07 16:43:19 agc Exp $ */ - -/*- - * Copyright (c) 1992, 1993, 1994 - * The Regents of the University of California. All rights reserved. - * - * This code is derived from software contributed to Berkeley by - * Henry Spencer. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * 3. Neither the name of the University nor the names of its contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND - * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE - * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL - * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS - * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) - * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT - * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY - * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF - * SUCH DAMAGE. - * - * @(#)cclass.h 8.3 (Berkeley) 3/20/94 - */ - -/*- - * Copyright (c) 1992, 1993, 1994 Henry Spencer. - * - * This code is derived from software contributed to Berkeley by - * Henry Spencer. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * 3. All advertising materials mentioning features or use of this software - * must display the following acknowledgement: - * This product includes software developed by the University of - * California, Berkeley and its contributors. - * 4. Neither the name of the University nor the names of its contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND - * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE - * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL - * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS - * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) - * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT - * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY - * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF - * SUCH DAMAGE. - * - * @(#)cclass.h 8.3 (Berkeley) 3/20/94 - */ - -/* character-class table */ -static const struct cclass { - const char *name; - const char *chars; - const char *multis; -} cclasses[] = { - { "alnum", "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz\ -0123456789", "" }, - { "alpha", "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz", - "" }, - { "blank", " \t", "" }, - { "cntrl", "\007\b\t\n\v\f\r\1\2\3\4\5\6\16\17\20\21\22\23\24\ -\25\26\27\30\31\32\33\34\35\36\37\177", "" }, - { "digit", "0123456789", "" }, - { "graph", "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz\ -0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~", - "" }, - { "lower", "abcdefghijklmnopqrstuvwxyz", - "" }, - { "print", "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz\ -0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ ", - "" }, - { "punct", "!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~", - "" }, - { "space", "\t\n\v\f\r ", "" }, - { "upper", "ABCDEFGHIJKLMNOPQRSTUVWXYZ", - "" }, - { "xdigit", "0123456789ABCDEFabcdef", - "" }, - { NULL, 0, "" } -}; diff --git a/lib/libc/regex/cname.h b/lib/libc/regex/cname.h index 4b9ef3919da..47e57ac0087 100644 --- a/lib/libc/regex/cname.h +++ b/lib/libc/regex/cname.h @@ -1,6 +1,9 @@ -/* $NetBSD: cname.h,v 1.7 2003/08/07 16:43:19 agc Exp $ */ +/* $NetBSD: cname.h,v 1.8 2021/02/23 22:14:59 christos Exp $ */ /*- + * SPDX-License-Identifier: BSD-3-Clause + * + * Copyright (c) 1992, 1993, 1994 Henry Spencer. * Copyright (c) 1992, 1993, 1994 * The Regents of the University of California. All rights reserved. * @@ -32,144 +35,108 @@ * SUCH DAMAGE. * * @(#)cname.h 8.3 (Berkeley) 3/20/94 - */ - -/*- - * Copyright (c) 1992, 1993, 1994 Henry Spencer. - * - * This code is derived from software contributed to Berkeley by - * Henry Spencer. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * 3. All advertising materials mentioning features or use of this software - * must display the following acknowledgement: - * This product includes software developed by the University of - * California, Berkeley and its contributors. - * 4. Neither the name of the University nor the names of its contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND - * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE - * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL - * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS - * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) - * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT - * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY - * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF - * SUCH DAMAGE. - * - * @(#)cname.h 8.3 (Berkeley) 3/20/94 + * $FreeBSD: head/lib/libc/regex/cname.h 326025 2017-11-20 19:49:47Z pfg $ */ /* character-name table */ -static const struct cname { +static struct cname { const char *name; char code; } cnames[] = { - { "NUL", '\0' }, - { "SOH", '\001' }, - { "STX", '\002' }, - { "ETX", '\003' }, - { "EOT", '\004' }, - { "ENQ", '\005' }, - { "ACK", '\006' }, - { "BEL", '\007' }, - { "alert", '\007' }, - { "BS", '\010' }, - { "backspace", '\b' }, - { "HT", '\011' }, - { "tab", '\t' }, - { "LF", '\012' }, - { "newline", '\n' }, - { "VT", '\013' }, - { "vertical-tab", '\v' }, - { "FF", '\014' }, - { "form-feed", '\f' }, - { "CR", '\015' }, - { "carriage-return", '\r' }, - { "SO", '\016' }, - { "SI", '\017' }, - { "DLE", '\020' }, - { "DC1", '\021' }, - { "DC2", '\022' }, - { "DC3", '\023' }, - { "DC4", '\024' }, - { "NAK", '\025' }, - { "SYN", '\026' }, - { "ETB", '\027' }, - { "CAN", '\030' }, - { "EM", '\031' }, - { "SUB", '\032' }, - { "ESC", '\033' }, - { "IS4", '\034' }, - { "FS", '\034' }, - { "IS3", '\035' }, - { "GS", '\035' }, - { "IS2", '\036' }, - { "RS", '\036' }, - { "IS1", '\037' }, - { "US", '\037' }, - { "space", ' ' }, - { "exclamation-mark", '!' }, - { "quotation-mark", '"' }, - { "number-sign", '#' }, - { "dollar-sign", '$' }, - { "percent-sign", '%' }, - { "ampersand", '&' }, - { "apostrophe", '\'' }, - { "left-parenthesis", '(' }, - { "right-parenthesis", ')' }, - { "asterisk", '*' }, - { "plus-sign", '+' }, - { "comma", ',' }, - { "hyphen", '-' }, - { "hyphen-minus", '-' }, - { "period", '.' }, - { "full-stop", '.' }, - { "slash", '/' }, - { "solidus", '/' }, - { "zero", '0' }, - { "one", '1' }, - { "two", '2' }, - { "three", '3' }, - { "four", '4' }, - { "five", '5' }, - { "six", '6' }, - { "seven", '7' }, - { "eight", '8' }, - { "nine", '9' }, - { "colon", ':' }, - { "semicolon", ';' }, - { "less-than-sign", '<' }, - { "equals-sign", '=' }, - { "greater-than-sign", '>' }, - { "question-mark", '?' }, - { "commercial-at", '@' }, - { "left-square-bracket", '[' }, - { "backslash", '\\' }, - { "reverse-solidus", '\\' }, - { "right-square-bracket", ']' }, - { "circumflex", '^' }, - { "circumflex-accent", '^' }, - { "underscore", '_' }, - { "low-line", '_' }, - { "grave-accent", '`' }, - { "left-brace", '{' }, - { "left-curly-bracket", '{' }, - { "vertical-line", '|' }, - { "right-brace", '}' }, - { "right-curly-bracket", '}' }, - { "tilde", '~' }, - { "DEL", '\177' }, - { NULL, 0 }, + {"NUL", '\0'}, + {"SOH", '\001'}, + {"STX", '\002'}, + {"ETX", '\003'}, + {"EOT", '\004'}, + {"ENQ", '\005'}, + {"ACK", '\006'}, + {"BEL", '\007'}, + {"alert", '\007'}, + {"BS", '\010'}, + {"backspace", '\b'}, + {"HT", '\011'}, + {"tab", '\t'}, + {"LF", '\012'}, + {"newline", '\n'}, + {"VT", '\013'}, + {"vertical-tab", '\v'}, + {"FF", '\014'}, + {"form-feed", '\f'}, + {"CR", '\015'}, + {"carriage-return", '\r'}, + {"SO", '\016'}, + {"SI", '\017'}, + {"DLE", '\020'}, + {"DC1", '\021'}, + {"DC2", '\022'}, + {"DC3", '\023'}, + {"DC4", '\024'}, + {"NAK", '\025'}, + {"SYN", '\026'}, + {"ETB", '\027'}, + {"CAN", '\030'}, + {"EM", '\031'}, + {"SUB", '\032'}, + {"ESC", '\033'}, + {"IS4", '\034'}, + {"FS", '\034'}, + {"IS3", '\035'}, + {"GS", '\035'}, + {"IS2", '\036'}, + {"RS", '\036'}, + {"IS1", '\037'}, + {"US", '\037'}, + {"space", ' '}, + {"exclamation-mark", '!'}, + {"quotation-mark", '"'}, + {"number-sign", '#'}, + {"dollar-sign", '$'}, + {"percent-sign", '%'}, + {"ampersand", '&'}, + {"apostrophe", '\''}, + {"left-parenthesis", '('}, + {"right-parenthesis", ')'}, + {"asterisk", '*'}, + {"plus-sign", '+'}, + {"comma", ','}, + {"hyphen", '-'}, + {"hyphen-minus", '-'}, + {"period", '.'}, + {"full-stop", '.'}, + {"slash", '/'}, + {"solidus", '/'}, + {"zero", '0'}, + {"one", '1'}, + {"two", '2'}, + {"three", '3'}, + {"four", '4'}, + {"five", '5'}, + {"six", '6'}, + {"seven", '7'}, + {"eight", '8'}, + {"nine", '9'}, + {"colon", ':'}, + {"semicolon", ';'}, + {"less-than-sign", '<'}, + {"equals-sign", '='}, + {"greater-than-sign", '>'}, + {"question-mark", '?'}, + {"commercial-at", '@'}, + {"left-square-bracket", '['}, + {"backslash", '\\'}, + {"reverse-solidus", '\\'}, + {"right-square-bracket",']'}, + {"circumflex", '^'}, + {"circumflex-accent", '^'}, + {"underscore", '_'}, + {"low-line", '_'}, + {"grave-accent", '`'}, + {"left-brace", '{'}, + {"left-curly-bracket", '{'}, + {"vertical-line", '|'}, + {"right-brace", '}'}, + {"right-curly-bracket", '}'}, + {"tilde", '~'}, + {"DEL", '\177'}, + {NULL, 0} }; diff --git a/lib/libc/regex/engine.c b/lib/libc/regex/engine.c index 2a800d4ffae..863b732d5dc 100644 --- a/lib/libc/regex/engine.c +++ b/lib/libc/regex/engine.c @@ -1,6 +1,7 @@ -/* $NetBSD: engine.c,v 1.24 2012/03/13 21:13:42 christos Exp $ */ - /*- + * SPDX-License-Identifier: BSD-3-Clause + * + * Copyright (c) 1992, 1993, 1994 Henry Spencer. * Copyright (c) 1992, 1993, 1994 * The Regents of the University of California. All rights reserved. * @@ -34,42 +35,13 @@ * @(#)engine.c 8.5 (Berkeley) 3/20/94 */ -/*- - * Copyright (c) 1992, 1993, 1994 Henry Spencer. - * - * This code is derived from software contributed to Berkeley by - * Henry Spencer. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * 3. All advertising materials mentioning features or use of this software - * must display the following acknowledgement: - * This product includes software developed by the University of - * California, Berkeley and its contributors. - * 4. Neither the name of the University nor the names of its contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND - * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE - * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL - * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS - * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) - * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT - * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY - * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF - * SUCH DAMAGE. - * - * @(#)engine.c 8.5 (Berkeley) 3/20/94 - */ +#include <sys/cdefs.h> +#ifdef __FBSDID +__FBSDID("$FreeBSD: head/lib/libc/regex/engine.c 368358 2020-12-05 03:16:05Z kevans $"); +#endif +__RCSID("$NetBSD: engine.c,v 1.25 2021/02/23 22:14:59 christos Exp $"); + +#include <stdbool.h> /* * The matching engine and friends. This file is #included by regexec.c @@ -79,28 +51,37 @@ */ #ifdef SNAMES +#define stepback sstepback #define matcher smatcher -#define fast sfast -#define slow sslow +#define walk swalk #define dissect sdissect #define backref sbackref #define step sstep #define print sprint #define at sat #define match smat -#define nope snope #endif #ifdef LNAMES +#define stepback lstepback #define matcher lmatcher -#define fast lfast -#define slow lslow +#define walk lwalk #define dissect ldissect #define backref lbackref #define step lstep #define print lprint #define at lat #define match lmat -#define nope lnope +#endif +#ifdef MNAMES +#define stepback mstepback +#define matcher mmatcher +#define walk mwalk +#define dissect mdissect +#define backref mbackref +#define step mstep +#define print mprint +#define at mat +#define match mmat #endif /* another structure passed up and down to avoid zillions of parameters */ @@ -118,6 +99,7 @@ struct match { states fresh; /* states for a fresh start */ states tmp; /* temporary */ states empty; /* empty set of states */ + mbstate_t mbs; /* multibyte conversion state */ }; /* ========= begin header generated by ./mkh ========= */ @@ -128,27 +110,31 @@ extern "C" { /* === engine.c === */ static int matcher(struct re_guts *g, const char *string, size_t nmatch, regmatch_t pmatch[], int eflags); static const char *dissect(struct match *m, const char *start, const char *stop, sopno startst, sopno stopst); -static const char *backref(struct match *m, const char *start, const char *stop, sopno startst, sopno stopst, sopno lev); -static const char *fast(struct match *m, const char *start, const char *stop, sopno startst, sopno stopst); -static const char *slow(struct match *m, const char *start, const char *stop, sopno startst, sopno stopst); -static states step(struct re_guts *g, sopno start, sopno stop, states bef, int ch, states aft); -#define BOL (OUT+1) -#define EOL (BOL+1) -#define BOLEOL (BOL+2) -#define NOTHING (BOL+3) -#define BOW (BOL+4) -#define EOW (BOL+5) -#define CODEMAX (BOL+5) /* highest code used */ -#define NONCHAR(c) ((c) > CHAR_MAX) -#define NNONCHAR (CODEMAX-CHAR_MAX) +static const char *backref(struct match *m, const char *start, const char *stop, sopno startst, sopno stopst, sopno lev, int); +static const char *walk(struct match *m, const char *start, const char *stop, sopno startst, sopno stopst, bool fast); +static states step(struct re_guts *g, sopno start, sopno stop, states bef, wint_t ch, states aft, int sflags); +#define MAX_RECURSION 100 +#define BOL (OUT-1) +#define EOL (BOL-1) +#define BOLEOL (BOL-2) +#define NOTHING (BOL-3) +#define BOW (BOL-4) +#define EOW (BOL-5) +#define BADCHAR (BOL-6) +#define NWBND (BOL-7) +#define NONCHAR(c) ((c) <= OUT) +/* sflags */ +#define SBOS 0x0001 +#define SEOS 0x0002 + #ifdef REDEBUG -static void print(struct match *m, char *caption, states st, int ch, FILE *d); +static void print(struct match *m, const char *caption, states st, int ch, FILE *d); #endif #ifdef REDEBUG -static void at(struct match *m, char *title, char *start, char *stop, sopno startst, sopno stopst); +static void at(struct match *m, const char *title, const char *start, const char *stop, sopno startst, sopno stopst); #endif #ifdef REDEBUG -static char *pchar(int ch); +static const char *pchar(int ch); #endif #ifdef __cplusplus @@ -160,7 +146,6 @@ static char *pchar(int ch); #define SP(t, s, c) print(m, t, s, c, stdout) #define AT(t, p1, p2, s1, s2) at(m, t, p1, p2, s1, s2) #define NOTE(str) { if (m->eflags®_TRACE) printf("=%s\n", (str)); } -static int nope = 0; #else #define SP(t, s, c) /* nothing */ #define AT(t, p1, p2, s1, s2) /* nothing */ @@ -168,27 +153,66 @@ static int nope = 0; #endif /* + * Given a multibyte string pointed to by start, step back nchar characters + * from current position pointed to by cur. + */ +static const char * +stepback(const char *start, const char *cur, int nchar) +{ + const char *ret; + size_t wc, mbc; + mbstate_t mbs; + size_t clen; + + if (MB_CUR_MAX == 1) + return ((cur - nchar) > start ? cur - nchar : NULL); + + ret = cur; + for (wc = nchar; wc > 0; wc--) { + for (mbc = 1; mbc <= MB_CUR_MAX; mbc++) { + if ((ret - mbc) < start) + return (NULL); + memset(&mbs, 0, sizeof(mbs)); + clen = mbrtowc(NULL, ret - mbc, mbc, &mbs); + if (clen != (size_t)-1 && clen != (size_t)-2) + break; + } + if (mbc > MB_CUR_MAX) + return (NULL); + ret -= mbc; + } + + return (ret); +} + +/* - matcher - the actual matching engine - == static int matcher(struct re_guts *g, char *string, \ + == static int matcher(struct re_guts *g, const char *string, \ == size_t nmatch, regmatch_t pmatch[], int eflags); */ static int /* 0 success, REG_NOMATCH failure */ -matcher( - struct re_guts *g, - const char *string, - size_t nmatch, - regmatch_t pmatch[], - int eflags) +matcher(struct re_guts *g, + const char *string, + size_t nmatch, + regmatch_t pmatch[], + int eflags) { const char *endp; size_t i; struct match mv; struct match *m = &mv; - const char *dp; + const char *dp = NULL; const sopno gf = g->firststate+1; /* +1 for OEND */ const sopno gl = g->laststate; const char *start; const char *stop; + /* Boyer-Moore algorithms variables */ + const char *pp; + int cj, mj; + const char *mustfirst; + const char *mustlast; + size_t *matchjump; + size_t *charjump; int error = 0; _DIAGASSERT(g != NULL); @@ -211,12 +235,46 @@ matcher( /* prescreening; this does wonders for this rather slow code */ if (g->must != NULL) { - for (dp = start; dp < stop; dp++) - if (*dp == g->must[0] && (size_t)(stop - dp) >= g->mlen && - memcmp(dp, g->must, g->mlen) == 0) - break; - if (dp == stop) /* we didn't find g->must */ - return(REG_NOMATCH); + if (g->charjump != NULL && g->matchjump != NULL) { + mustfirst = g->must; + mustlast = g->must + g->mlen - 1; + charjump = g->charjump; + matchjump = g->matchjump; + pp = mustlast; + for (dp = start+g->mlen-1; dp < stop;) { + /* Fast skip non-matches */ + while (dp < stop && charjump[(int)*dp]) + dp += charjump[(int)*dp]; + + if (dp >= stop) + break; + + /* Greedy matcher */ + /* We depend on not being used for + * for strings of length 1 + */ + while (*--dp == *--pp && pp != mustfirst); + + if (*dp == *pp) + break; + + /* Jump to next possible match */ + mj = matchjump[pp - mustfirst]; + cj = charjump[(int)*dp]; + dp += (cj < mj ? mj : cj); + pp = mustlast; + } + if (pp != mustfirst) + return(REG_NOMATCH); + } else { + for (dp = start; dp < stop; dp++) + if (*dp == g->must[0] && + (size_t)(stop - dp) >= g->mlen && + memcmp(dp, g->must, (size_t)g->mlen) == 0) + break; + if (dp == stop) /* we didn't find g->must */ + return(REG_NOMATCH); + } } /* match struct setup */ @@ -233,10 +291,22 @@ matcher( SETUP(m->tmp); SETUP(m->empty); CLEAR(m->empty); + ZAPSTATE(&m->mbs); + + /* Adjust start according to moffset, to speed things up */ + if (dp != NULL && g->moffset > -1) { + const char *nstart; + + nstart = stepback(start, dp, g->moffset); + if (nstart != NULL) + start = nstart; + } + + SP("mloop", m->st, *start); /* this loop does only one repetition except for backrefs */ for (;;) { - endp = fast(m, start, stop, gf, gl); + endp = walk(m, start, stop, gf, gl, true); if (endp == NULL) { /* a miss */ error = REG_NOMATCH; goto done; @@ -248,11 +318,12 @@ matcher( assert(m->coldp != NULL); for (;;) { NOTE("finding start"); - endp = slow(m, m->coldp, stop, gf, gl); + endp = walk(m, m->coldp, stop, gf, gl, false); if (endp != NULL) break; assert(m->coldp < m->endp); - m->coldp++; + m->coldp += XMBRTOWC(NULL, m->coldp, + m->endp - m->coldp, &m->mbs, 0); } if (nmatch == 1 && !g->backrefs) break; /* no further info needed */ @@ -266,20 +337,20 @@ matcher( goto done; } for (i = 1; i <= m->g->nsub; i++) - m->pmatch[i].rm_so = m->pmatch[i].rm_eo = (regoff_t)-1; + m->pmatch[i].rm_so = m->pmatch[i].rm_eo = -1; if (!g->backrefs && !(m->eflags®_BACKR)) { NOTE("dissecting"); dp = dissect(m, m->coldp, endp, gf, gl); } else { if (g->nplus > 0 && m->lastpos == NULL) m->lastpos = malloc((g->nplus+1) * - sizeof(const char *)); + sizeof(const char *)); if (g->nplus > 0 && m->lastpos == NULL) { error = REG_ESPACE; goto done; } NOTE("backref dissect"); - dp = backref(m, m->coldp, endp, gf, gl, (sopno)0); + dp = backref(m, m->coldp, endp, gf, gl, (sopno)0, 0); } if (dp != NULL) break; @@ -291,7 +362,7 @@ matcher( if (dp != NULL || endp <= m->coldp) break; /* defeat */ NOTE("backoff"); - endp = slow(m, m->coldp, endp-1, gf, gl); + endp = walk(m, m->coldp, endp-1, gf, gl, false); if (endp == NULL) break; /* defeat */ /* try it on a shorter possibility */ @@ -302,7 +373,7 @@ matcher( } #endif NOTE("backoff dissect"); - dp = backref(m, m->coldp, endp, gf, gl, (sopno)0); + dp = backref(m, m->coldp, endp, gf, gl, (sopno)0, 0); } assert(dp == NULL || dp == endp); if (dp != NULL) /* found a shorter one */ @@ -310,7 +381,9 @@ matcher( /* despite initial appearances, there is no match here */ NOTE("false alarm"); - start = m->coldp + 1; /* recycle starting later */ + /* recycle starting later */ + start = m->coldp + XMBRTOWC(NULL, m->coldp, + stop - m->coldp, &m->mbs, 0); assert(start <= stop); } @@ -337,7 +410,7 @@ done: m->pmatch = NULL; } if (m->lastpos != NULL) { - free(m->lastpos); + free((char *)m->lastpos); m->lastpos = NULL; } STATETEARDOWN(m); @@ -349,29 +422,27 @@ done: == static const char *dissect(struct match *m, const char *start, \ == const char *stop, sopno startst, sopno stopst); */ -static const char * /* == stop (success) always */ +static const char * /* == stop (success) always */ dissect( - struct match *m, - const char *start, - const char *stop, - sopno startst, - sopno stopst) + struct match *m, + const char *start, + const char *stop, + sopno startst, + sopno stopst) { int i; - sopno ss; /* start sop of current subRE */ - sopno es; /* end sop of current subRE */ - const char *sp; /* start of string matched by it */ - const char *stp; /* string matched by it cannot pass here */ - const char *rest; /* start of rest of string */ - const char *tail; /* string unmatched by rest of RE */ - sopno ssub; /* start sop of subsubRE */ - sopno esub; /* end sop of subsubRE */ - const char *ssp; /* start of string matched by subsubRE */ - const char *sep; /* end of string matched by subsubRE */ - const char *oldssp; /* previous ssp */ -#ifndef NDEBUG - const char *dp; -#endif + sopno ss; /* start sop of current subRE */ + sopno es; /* end sop of current subRE */ + const char *sp; /* start of string matched by it */ + const char *stp; /* string matched by it cannot pass here */ + const char *rest; /* start of rest of string */ + const char *tail; /* string unmatched by rest of RE */ + sopno ssub; /* start sop of subsubRE */ + sopno esub; /* end sop of subsubRE */ + const char *ssp; /* start of string matched by subsubRE */ + const char *sep; /* end of string matched by subsubRE */ + const char *oldssp; /* previous ssp */ + const char *dp __unused; _DIAGASSERT(m != NULL); _DIAGASSERT(start != NULL); @@ -388,7 +459,7 @@ dissect( es += OPND(m->g->strip[es]); break; case OCH_: - while (OP(m->g->strip[es]) != O_CH) + while (OP(m->g->strip[es]) != (sop)O_CH) es += OPND(m->g->strip[es]); break; } @@ -400,16 +471,20 @@ dissect( assert(nope); break; case OCHAR: - sp++; + sp += XMBRTOWC(NULL, sp, stop - start, &m->mbs, 0); break; case OBOL: case OEOL: case OBOW: case OEOW: + case OBOS: + case OEOS: + case OWBND: + case ONWBND: break; case OANY: case OANYOF: - sp++; + sp += XMBRTOWC(NULL, sp, stop - start, &m->mbs, 0); break; case OBACK_: case O_BACK: @@ -420,10 +495,10 @@ dissect( stp = stop; for (;;) { /* how long could this one be? */ - rest = slow(m, sp, stp, ss, es); + rest = walk(m, sp, stp, ss, es, false); assert(rest != NULL); /* it did match */ /* could the rest match the rest? */ - tail = slow(m, rest, stop, es, stopst); + tail = walk(m, rest, stop, es, stopst, false); if (tail == stop) break; /* yes! */ /* no -- try a shorter match for this one */ @@ -433,13 +508,8 @@ dissect( ssub = ss + 1; esub = es - 1; /* did innards match? */ - if (slow(m, sp, rest, ssub, esub) != NULL) { -#ifdef NDEBUG - (void) -#else - dp = -#endif - dissect(m, sp, rest, ssub, esub); + if (walk(m, sp, rest, ssub, esub, false) != NULL) { + dp = dissect(m, sp, rest, ssub, esub); assert(dp == rest); } else /* no */ assert(sp == rest); @@ -449,10 +519,10 @@ dissect( stp = stop; for (;;) { /* how long could this one be? */ - rest = slow(m, sp, stp, ss, es); + rest = walk(m, sp, stp, ss, es, false); assert(rest != NULL); /* it did match */ /* could the rest match the rest? */ - tail = slow(m, rest, stop, es, stopst); + tail = walk(m, rest, stop, es, stopst, false); if (tail == stop) break; /* yes! */ /* no -- try a shorter match for this one */ @@ -464,7 +534,7 @@ dissect( ssp = sp; oldssp = ssp; for (;;) { /* find last match of innards */ - sep = slow(m, ssp, rest, ssub, esub); + sep = walk(m, ssp, rest, ssub, esub, false); if (sep == NULL || sep == ssp) break; /* failed or matched null */ oldssp = ssp; /* on to next try */ @@ -476,13 +546,8 @@ dissect( ssp = oldssp; } assert(sep == rest); /* must exhaust substring */ - assert(slow(m, ssp, sep, ssub, esub) == rest); -#ifdef NDEBUG - (void) -#else - dp = -#endif - dissect(m, ssp, sep, ssub, esub); + assert(walk(m, ssp, sep, ssub, esub, false) == rest); + dp = dissect(m, ssp, sep, ssub, esub); assert(dp == sep); sp = rest; break; @@ -490,10 +555,10 @@ dissect( stp = stop; for (;;) { /* how long could this one be? */ - rest = slow(m, sp, stp, ss, es); + rest = walk(m, sp, stp, ss, es, false); assert(rest != NULL); /* it did match */ /* could the rest match the rest? */ - tail = slow(m, rest, stop, es, stopst); + tail = walk(m, rest, stop, es, stopst, false); if (tail == stop) break; /* yes! */ /* no -- try a shorter match for this one */ @@ -504,7 +569,7 @@ dissect( esub = ss + OPND(m->g->strip[ss]) - 1; assert(OP(m->g->strip[esub]) == OOR1); for (;;) { /* find first matching branch */ - if (slow(m, sp, rest, ssub, esub) == rest) + if (walk(m, sp, rest, ssub, esub, false) == rest) break; /* it matched all of it */ /* that one missed, try next one */ assert(OP(m->g->strip[esub]) == OOR1); @@ -512,17 +577,12 @@ dissect( assert(OP(m->g->strip[esub]) == OOR2); ssub = esub + 1; esub += OPND(m->g->strip[esub]); - if (OP(m->g->strip[esub]) == OOR2) + if (OP(m->g->strip[esub]) == (sop)OOR2) esub--; else assert(OP(m->g->strip[esub]) == O_CH); } -#ifdef NDEBUG - (void) -#else - dp = -#endif - dissect(m, sp, rest, ssub, esub); + dp = dissect(m, sp, rest, ssub, esub); assert(dp == rest); sp = rest; break; @@ -553,6 +613,17 @@ dissect( return(sp); } +#define ISBOW(m, sp) \ + (sp < m->endp && ISWORD(*sp) && \ + ((sp == m->beginp && !(m->eflags®_NOTBOL)) || \ + (sp > m->offp && !ISWORD(*(sp-1))))) +#define ISEOW(m, sp) \ + (((sp == m->endp && !(m->eflags®_NOTEOL)) || \ + (sp < m->endp && *sp == '\n' && \ + (m->g->cflags®_NEWLINE)) || \ + (sp < m->endp && !ISWORD(*sp)) ) && \ + (sp > m->beginp && ISWORD(*(sp-1)))) \ + /* - backref - figure out what matched what, figuring in back references == static const char *backref(struct match *m, const char *start, \ @@ -560,25 +631,27 @@ dissect( */ static const char * /* == stop (success) or NULL (failure) */ backref( - struct match *m, - const char *start, - const char *stop, - sopno startst, - sopno stopst, - sopno lev) /* PLUS nesting level */ + struct match *m, + const char *start, + const char *stop, + sopno startst, + sopno stopst, + sopno lev, /* PLUS nesting level */ + int rec) { int i; - sopno ss; /* start sop of current subRE */ - const char *sp; /* start of string matched by it */ - sopno ssub; /* start sop of subsubRE */ - sopno esub; /* end sop of subsubRE */ - const char *ssp; /* start of string matched by subsubRE */ + sopno ss; /* start sop of current subRE */ + const char *sp; /* start of string matched by it */ + sopno ssub; /* start sop of subsubRE */ + sopno esub; /* end sop of subsubRE */ + const char *ssp; /* start of string matched by subsubRE */ const char *dp; size_t len; int hard; sop s; regoff_t offsave; cset *cs; + wint_t wc; _DIAGASSERT(m != NULL); _DIAGASSERT(start != NULL); @@ -592,23 +665,43 @@ backref( for (ss = startst; !hard && ss < stopst; ss++) switch (OP(s = m->g->strip[ss])) { case OCHAR: - if (sp == stop || *sp++ != (char)OPND(s)) + if (sp == stop) + return(NULL); + sp += XMBRTOWC(&wc, sp, stop - sp, &m->mbs, BADCHAR); + if (wc != (wint_t)OPND(s)) return(NULL); break; case OANY: if (sp == stop) return(NULL); - sp++; + sp += XMBRTOWC(&wc, sp, stop - sp, &m->mbs, BADCHAR); + if (wc == BADCHAR) + return (NULL); break; case OANYOF: + if (sp == stop) + return (NULL); cs = &m->g->sets[OPND(s)]; - if (sp == stop || !CHIN(cs, *sp++)) + sp += XMBRTOWC(&wc, sp, stop - sp, &m->mbs, BADCHAR); + if (wc == BADCHAR || !CHIN(cs, wc)) + return(NULL); + break; + case OBOS: + if (sp == m->beginp && (m->eflags & REG_NOTBOL) == 0) + { /* yes */ } + else + return(NULL); + break; + case OEOS: + if (sp == m->endp && (m->eflags & REG_NOTEOL) == 0) + { /* yes */ } + else return(NULL); break; case OBOL: - if ( (sp == m->beginp && !(m->eflags®_NOTBOL)) || - (sp < m->endp && *(sp-1) == '\n' && - (m->g->cflags®_NEWLINE)) ) + if ((sp == m->beginp && !(m->eflags®_NOTBOL)) || + (sp > m->offp && sp < m->endp && + *(sp-1) == '\n' && (m->g->cflags®_NEWLINE))) { /* yes */ } else return(NULL); @@ -621,23 +714,29 @@ backref( else return(NULL); break; + case OWBND: + if (ISBOW(m, sp) || ISEOW(m, sp)) + { /* yes */ } + else + return(NULL); + break; + case ONWBND: + if (((sp == m->beginp) && !ISWORD(*sp)) || + (sp == m->endp && !ISWORD(*(sp - 1)))) + { /* yes, beginning/end of subject */ } + else if (ISWORD(*(sp - 1)) == ISWORD(*sp)) + { /* yes, beginning/end of subject */ } + else + return(NULL); + break; case OBOW: - if (( (sp == m->beginp && !(m->eflags®_NOTBOL)) || - (sp < m->endp && *(sp-1) == '\n' && - (m->g->cflags®_NEWLINE)) || - (sp > m->beginp && - !ISWORD(*(sp-1))) ) && - (sp < m->endp && ISWORD(*sp)) ) + if (ISBOW(m, sp)) { /* yes */ } else return(NULL); break; case OEOW: - if (( (sp == m->endp && !(m->eflags®_NOTEOL)) || - (sp < m->endp && *sp == '\n' && - (m->g->cflags®_NEWLINE)) || - (sp < m->endp && !ISWORD(*sp)) ) && - (sp > m->beginp && ISWORD(*(sp-1))) ) + if (ISEOW(m, sp)) { /* yes */ } else return(NULL); @@ -650,7 +749,7 @@ backref( do { assert(OP(s) == OOR2); ss += OPND(s); - } while (OP(s = m->g->strip[ss]) != O_CH); + } while (OP(s = m->g->strip[ss]) != (sop)O_CH); /* note that the ss++ gets us past the O_CH */ break; default: /* have to make a choice */ @@ -671,87 +770,83 @@ backref( case OBACK_: /* the vilest depths */ i = OPND(s); assert(0 < i && i <= m->g->nsub); - if (m->pmatch[i].rm_eo == (regoff_t)-1) + if (m->pmatch[i].rm_eo == -1) return(NULL); - assert(m->pmatch[i].rm_so != (regoff_t)-1); - len = (size_t)(m->pmatch[i].rm_eo - m->pmatch[i].rm_so); - if (len == 0) + assert(m->pmatch[i].rm_so != -1); + len = m->pmatch[i].rm_eo - m->pmatch[i].rm_so; + if (len == 0 && rec++ > MAX_RECURSION) return(NULL); assert(stop - m->beginp >= len); if (sp > stop - len) return(NULL); /* not enough left to match */ - ssp = m->offp + (size_t)m->pmatch[i].rm_so; + ssp = m->offp + m->pmatch[i].rm_so; if (memcmp(sp, ssp, len) != 0) return(NULL); - while (m->g->strip[ss] != SOP(O_BACK, i)) + while (m->g->strip[ss] != (sop)SOP(O_BACK, i)) ss++; - return(backref(m, sp+len, stop, ss+1, stopst, lev)); - + return(backref(m, sp+len, stop, ss+1, stopst, lev, rec)); case OQUEST_: /* to null or not */ - dp = backref(m, sp, stop, ss+1, stopst, lev); + dp = backref(m, sp, stop, ss+1, stopst, lev, rec); if (dp != NULL) return(dp); /* not */ - return(backref(m, sp, stop, ss+OPND(s)+1, stopst, lev)); - + return(backref(m, sp, stop, ss+OPND(s)+1, stopst, lev, rec)); case OPLUS_: assert(m->lastpos != NULL); assert(lev+1 <= m->g->nplus); m->lastpos[lev+1] = sp; - return(backref(m, sp, stop, ss+1, stopst, lev+1)); - + return(backref(m, sp, stop, ss+1, stopst, lev+1, rec)); case O_PLUS: if (sp == m->lastpos[lev]) /* last pass matched null */ - return(backref(m, sp, stop, ss+1, stopst, lev-1)); + return(backref(m, sp, stop, ss+1, stopst, lev-1, rec)); /* try another pass */ m->lastpos[lev] = sp; - dp = backref(m, sp, stop, ss-OPND(s)+1, stopst, lev); + dp = backref(m, sp, stop, ss-OPND(s)+1, stopst, lev, rec); if (dp == NULL) - dp = backref(m, sp, stop, ss+1, stopst, lev-1); - return(dp); - + return(backref(m, sp, stop, ss+1, stopst, lev-1, rec)); + else + return(dp); case OCH_: /* find the right one, if any */ ssub = ss + 1; esub = ss + OPND(s) - 1; assert(OP(m->g->strip[esub]) == OOR1); for (;;) { /* find first matching branch */ - dp = backref(m, sp, stop, ssub, esub, lev); + dp = backref(m, sp, stop, ssub, esub, lev, rec); if (dp != NULL) return(dp); /* that one missed, try next one */ - if (OP(m->g->strip[esub]) == O_CH) + if (OP(m->g->strip[esub]) == (sop)O_CH) return(NULL); /* there is none */ esub++; - assert(OP(m->g->strip[esub]) == OOR2); + assert(OP(m->g->strip[esub]) == (sop)OOR2); ssub = esub + 1; esub += OPND(m->g->strip[esub]); - if (OP(m->g->strip[esub]) == OOR2) + if (OP(m->g->strip[esub]) == (sop)OOR2) esub--; else assert(OP(m->g->strip[esub]) == O_CH); } - + /* NOTREACHED */ + break; case OLPAREN: /* must undo assignment if rest fails */ i = OPND(s); assert(0 < i && i <= m->g->nsub); offsave = m->pmatch[i].rm_so; m->pmatch[i].rm_so = sp - m->offp; - dp = backref(m, sp, stop, ss+1, stopst, lev); + dp = backref(m, sp, stop, ss+1, stopst, lev, rec); if (dp != NULL) return(dp); m->pmatch[i].rm_so = offsave; return(NULL); - case ORPAREN: /* must undo assignment if rest fails */ i = OPND(s); assert(0 < i && i <= m->g->nsub); offsave = m->pmatch[i].rm_eo; m->pmatch[i].rm_eo = sp - m->offp; - dp = backref(m, sp, stop, ss+1, stopst, lev); + dp = backref(m, sp, stop, ss+1, stopst, lev, rec); if (dp != NULL) return(dp); m->pmatch[i].rm_eo = offsave; return(NULL); - default: /* uh oh */ assert(nope); break; @@ -760,141 +855,65 @@ backref( /* "can't happen" */ assert(nope); /* NOTREACHED */ - return NULL; + return "shut up gcc"; } /* - - fast - step through the string at top speed - == static const char *fast(struct match *m, const char *start, \ - == const char *stop, sopno startst, sopno stopst); + - walk - step through the string either quickly or slowly + == static const char *walk(struct match *m, const char *start, \ + == const char *stop, sopno startst, sopno stopst, bool fast); */ -static const char * /* where tentative match ended, or NULL */ -fast( - struct match *m, - const char *start, - const char *stop, - sopno startst, - sopno stopst) +static const char * /* where it ended, or NULL */ +walk(struct match *m, const char *start, const char *stop, sopno startst, + sopno stopst, bool fast) { states st = m->st; states fresh = m->fresh; - states tmp = m->tmp; - const char *p = start; - int c = (start == m->beginp) ? OUT : *(start-1); - int lastc; /* previous c */ - int flagch; - size_t i; - const char *coldp; /* last p after which no match was underway */ - - _DIAGASSERT(m != NULL); - _DIAGASSERT(start != NULL); - _DIAGASSERT(stop != NULL); - - CLEAR(st); - SET1(st, startst); - st = step(m->g, startst, stopst, st, NOTHING, st); - ASSIGN(fresh, st); - SP("start", st, *p); - coldp = NULL; - for (;;) { - /* next character */ - lastc = c; - c = (p == m->endp) ? OUT : *p; - if (EQ(st, fresh)) - coldp = p; - - /* is there an EOL and/or BOL between lastc and c? */ - flagch = '\0'; - i = 0; - if ( (lastc == '\n' && m->g->cflags®_NEWLINE) || - (lastc == OUT && !(m->eflags®_NOTBOL)) ) { - flagch = BOL; - i = m->g->nbol; - } - if ( (c == '\n' && m->g->cflags®_NEWLINE) || - (c == OUT && !(m->eflags®_NOTEOL)) ) { - flagch = (flagch == BOL) ? BOLEOL : EOL; - i += m->g->neol; - } - if (i != 0) { - for (; i > 0; i--) - st = step(m->g, startst, stopst, st, flagch, st); - SP("boleol", st, c); - } - - /* how about a word boundary? */ - if ( (flagch == BOL || (lastc != OUT && !ISWORD(lastc))) && - (c != OUT && ISWORD(c)) ) { - flagch = BOW; - } - if ( (lastc != OUT && ISWORD(lastc)) && - (flagch == EOL || (c != OUT && !ISWORD(c))) ) { - flagch = EOW; - } - if (flagch == BOW || flagch == EOW) { - st = step(m->g, startst, stopst, st, flagch, st); - SP("boweow", st, c); - } - - /* are we done? */ - if (ISSET(st, stopst) || p == stop) - break; /* NOTE BREAK OUT */ - - /* no, we must deal with this character */ - ASSIGN(tmp, st); - ASSIGN(st, fresh); - assert(c != OUT); - st = step(m->g, startst, stopst, tmp, c, st); - SP("aft", st, c); - assert(EQ(step(m->g, startst, stopst, st, NOTHING, st), st)); - p++; - } - - assert(coldp != NULL); - m->coldp = coldp; - if (ISSET(st, stopst)) - return(p+1); - else - return(NULL); -} - -/* - - slow - step through the string more deliberately - == static const char *slow(struct match *m, const char *start, \ - == const char *stop, sopno startst, sopno stopst); - */ -static const char * /* where it ended */ -slow( - struct match *m, - const char *start, - const char *stop, - sopno startst, - sopno stopst) -{ - states st = m->st; states empty = m->empty; states tmp = m->tmp; const char *p = start; - int c = (start == m->beginp) ? OUT : *(start-1); - int lastc; /* previous c */ - int flagch; - size_t i; + wint_t c; + wint_t lastc; /* previous c */ + wint_t flagch; + int i, sflags; const char *matchp; /* last p at which a match ended */ + size_t clen; _DIAGASSERT(m != NULL); _DIAGASSERT(start != NULL); _DIAGASSERT(stop != NULL); - AT("slow", start, stop, startst, stopst); + sflags = 0; + AT("walk", start, stop, startst, stopst); CLEAR(st); SET1(st, startst); SP("sstart", st, *p); - st = step(m->g, startst, stopst, st, NOTHING, st); + st = step(m->g, startst, stopst, st, NOTHING, st, sflags); + if (fast) + ASSIGN(fresh, st); matchp = NULL; + if (start == m->offp || (start == m->beginp && !(m->eflags®_NOTBOL))) + c = OUT; + else { + /* + * XXX Wrong if the previous character was multi-byte. + * Newline never is (in encodings supported by FreeBSD), + * so this only breaks the ISWORD tests below. + */ + c = (uch)*(start - 1); + } for (;;) { /* next character */ lastc = c; - c = (p == m->endp) ? OUT : *p; + sflags = 0; + if (p == m->endp) { + c = OUT; + clen = 0; + } else + clen = XMBRTOWC(&c, p, m->endp - p, &m->mbs, BADCHAR); + + if (fast && EQ(st, fresh)) + matchp = p; /* is there an EOL and/or BOL between lastc and c? */ flagch = '\0'; @@ -909,9 +928,20 @@ slow( flagch = (flagch == BOL) ? BOLEOL : EOL; i += m->g->neol; } + if (lastc == OUT && (m->eflags & REG_NOTBOL) == 0) { + sflags |= SBOS; + /* Step one more for BOS. */ + i++; + } + if (c == OUT && (m->eflags & REG_NOTEOL) == 0) { + sflags |= SEOS; + /* Step one more for EOS. */ + i++; + } if (i != 0) { for (; i > 0; i--) - st = step(m->g, startst, stopst, st, flagch, st); + st = step(m->g, startst, stopst, st, flagch, st, + sflags); SP("sboleol", st, c); } @@ -925,52 +955,77 @@ slow( flagch = EOW; } if (flagch == BOW || flagch == EOW) { - st = step(m->g, startst, stopst, st, flagch, st); + st = step(m->g, startst, stopst, st, flagch, st, sflags); SP("sboweow", st, c); } + if (lastc != OUT && c != OUT && + ISWORD(lastc) == ISWORD(c)) { + flagch = NWBND; + } else if ((lastc == OUT && !ISWORD(c)) || + (c == OUT && !ISWORD(lastc))) { + flagch = NWBND; + } + if (flagch == NWBND) { + st = step(m->g, startst, stopst, st, flagch, st, sflags); + SP("snwbnd", st, c); + } /* are we done? */ - if (ISSET(st, stopst)) - matchp = p; - if (EQ(st, empty) || p == stop) + if (ISSET(st, stopst)) { + if (fast) + break; + else + matchp = p; + } + if (EQ(st, empty) || p == stop || clen > (size_t)(stop - p)) break; /* NOTE BREAK OUT */ /* no, we must deal with this character */ ASSIGN(tmp, st); - ASSIGN(st, empty); + if (fast) + ASSIGN(st, fresh); + else + ASSIGN(st, empty); assert(c != OUT); - st = step(m->g, startst, stopst, tmp, c, st); + st = step(m->g, startst, stopst, tmp, c, st, sflags); SP("saft", st, c); - assert(EQ(step(m->g, startst, stopst, st, NOTHING, st), st)); - p++; + assert(EQ(step(m->g, startst, stopst, st, NOTHING, st, sflags), + st)); + p += clen; } - return(matchp); + if (fast) { + assert(matchp != NULL); + m->coldp = matchp; + if (ISSET(st, stopst)) + return (p + XMBRTOWC(NULL, p, stop - p, &m->mbs, 0)); + else + return (NULL); + } else + return (matchp); } - /* - step - map set of states reachable before char to set reachable after == static states step(struct re_guts *g, sopno start, sopno stop, \ == states bef, int ch, states aft); - == #define BOL (OUT+1) - == #define EOL (BOL+1) - == #define BOLEOL (BOL+2) - == #define NOTHING (BOL+3) - == #define BOW (BOL+4) - == #define EOW (BOL+5) - == #define CODEMAX (BOL+5) // highest code used - == #define NONCHAR(c) ((c) > CHAR_MAX) - == #define NNONCHAR (CODEMAX-CHAR_MAX) + == #define BOL (OUT-1) + == #define EOL (BOL-1) + == #define BOLEOL (BOL-2) + == #define NOTHING (BOL-3) + == #define BOW (BOL-4) + == #define EOW (BOL-5) + == #define BADCHAR (BOL-6) + == #define NONCHAR(c) ((c) <= OUT) */ static states -step( - struct re_guts *g, - sopno start, /* start state within strip */ - sopno stop, /* state after stop state within strip */ - states bef, /* states reachable before */ - int ch, /* character or NONCHAR code */ - states aft) /* states already known reachable after */ +step(struct re_guts *g, + sopno start, /* start state within strip */ + sopno stop, /* state after stop state within strip */ + states bef, /* states reachable before */ + wint_t ch, /* character or NONCHAR code */ + states aft, /* states already known reachable after */ + int sflags) /* state flags */ { cset *cs; sop s; @@ -989,8 +1044,16 @@ step( break; case OCHAR: /* only characters can match */ - assert(!NONCHAR(ch) || ch != (char)OPND(s)); - if (ch == (char)OPND(s)) + assert(!NONCHAR(ch) || ch != OPND(s)); + if (ch == (wint_t)OPND(s)) + FWD(aft, bef, 1); + break; + case OBOS: + if ((ch == BOL || ch == BOLEOL) && (sflags & SBOS) != 0) + FWD(aft, bef, 1); + break; + case OEOS: + if ((ch == EOL || ch == BOLEOL) && (sflags & SEOS) != 0) FWD(aft, bef, 1); break; case OBOL: @@ -1009,6 +1072,14 @@ step( if (ch == EOW) FWD(aft, bef, 1); break; + case OWBND: + if (ch == BOW || ch == EOW) + FWD(aft, bef, 1); + break; + case ONWBND: + if (ch == NWBND) + FWD(aft, aft, 1); + break; case OANY: if (!NONCHAR(ch)) FWD(aft, bef, 1); @@ -1048,22 +1119,22 @@ step( break; case OCH_: /* mark the first two branches */ FWD(aft, aft, 1); - assert(OP(g->strip[pc+OPND(s)]) == OOR2); + assert(OP(g->strip[pc+OPND(s)]) == (sop)OOR2); FWD(aft, aft, OPND(s)); break; case OOR1: /* done a branch, find the O_CH */ if (ISSTATEIN(aft, here)) { for (look = 1; - OP(s = g->strip[pc+look]) != O_CH; - look += OPND(s)) - assert(OP(s) == OOR2); - FWD(aft, aft, look); + OP(s = g->strip[pc+look]) != (sop)O_CH; + look += OPND(s)) + assert(OP(s) == (sop)OOR2); + FWD(aft, aft, look + 1); } break; case OOR2: /* propagate OCH_'s marking */ FWD(aft, aft, 1); - if (OP(g->strip[pc+OPND(s)]) != O_CH) { - assert(OP(g->strip[pc+OPND(s)]) == OOR2); + if (OP(g->strip[pc+OPND(s)]) != (sop)O_CH) { + assert(OP(g->strip[pc+OPND(s)]) == (sop)OOR2); FWD(aft, aft, OPND(s)); } break; @@ -1083,20 +1154,19 @@ step( /* - print - print a set of states == #ifdef REDEBUG - == static void print(struct match *m, char *caption, states st, \ + == static void print(struct match *m, const char *caption, states st, \ == int ch, FILE *d); == #endif */ static void -print( - struct match *m, - char *caption, - states st, - int ch, - FILE *d) +print(struct match *m, + const char *caption, + states st, + int ch, + FILE *d) { struct re_guts *g = m->g; - int i; + sopno i; int first = 1; _DIAGASSERT(m != NULL); @@ -1112,27 +1182,26 @@ print( fprintf(d, " %s", pchar(ch)); for (i = 0; i < g->nstates; i++) if (ISSET(st, i)) { - fprintf(d, "%s%d", (first) ? "\t" : ", ", i); + fprintf(d, "%s%lu", (first) ? "\t" : ", ", i); first = 0; } fprintf(d, "\n"); } -/* +/* - at - print current situation == #ifdef REDEBUG - == static void at(struct match *m, char *title, char *start, char *stop, \ - == sopno startst, sopno stopst); + == static void at(struct match *m, const char *title, const char *start, \ + == const char *stop, sopno startst, sopno stopst); == #endif */ static void -at( - struct match *m, - char *title, - char *start, - char *stop, - sopno startst, - sopno stopst) +at( struct match *m, + const char *title, + const char *start, + const char *stop, + sopno startst, + sopno stopst) { _DIAGASSERT(m != NULL); @@ -1153,7 +1222,7 @@ at( /* - pchar - make a character printable == #ifdef REDEBUG - == static char *pchar(int ch); + == static const char *pchar(int ch); == #endif * * Is this identical to regchar() over in debug.c? Well, yes. But a @@ -1161,28 +1230,26 @@ at( * a matching debug.o, and this is convenient. It all disappears in * the non-debug compilation anyway, so it doesn't matter much. */ -static char * /* -> representation */ -pchar( - int ch) +static const char * /* -> representation */ +pchar(int ch) { static char pbuf[10]; - if (isprint(ch) || ch == ' ') - (void)snprintf(pbuf, sizeof pbuf, "%c", ch); + if (isprint((uch)ch) || ch == ' ') + snprintf(pbuf, sizeof(pbuf), "%c", ch); else - (void)snprintf(pbuf, sizeof pbuf, "\\%o", ch); + snprintf(pbuf, sizeof(pbuf), "\\%o", ch); return(pbuf); } #endif #endif +#undef stepback #undef matcher -#undef fast -#undef slow +#undef walk #undef dissect #undef backref #undef step #undef print #undef at #undef match -#undef nope diff --git a/lib/libc/regex/re_format.7 b/lib/libc/regex/re_format.7 index 026d6a31fb1..9e74b9fdce7 100644 --- a/lib/libc/regex/re_format.7 +++ b/lib/libc/regex/re_format.7 @@ -1,5 +1,4 @@ -.\" $NetBSD: re_format.7,v 1.12 2017/07/03 21:32:49 wiz Exp $ -.\" +.\" Copyright (c) 1992, 1993, 1994 Henry Spencer. .\" Copyright (c) 1992, 1993, 1994 .\" The Regents of the University of California. All rights reserved. .\" @@ -14,35 +13,6 @@ .\" 2. Redistributions in binary form must reproduce the above copyright .\" notice, this list of conditions and the following disclaimer in the .\" documentation and/or other materials provided with the distribution. -.\" 3. Neither the name of the University nor the names of its contributors -.\" may be used to endorse or promote products derived from this software -.\" without specific prior written permission. -.\" -.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND -.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE -.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE -.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE -.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS -.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) -.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT -.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY -.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF -.\" SUCH DAMAGE. -.\" -.\" Copyright (c) 1992, 1993, 1994 Henry Spencer. -.\" -.\" This code is derived from software contributed to Berkeley by -.\" Henry Spencer. -.\" -.\" Redistribution and use in source and binary forms, with or without -.\" modification, are permitted provided that the following conditions -.\" are met: -.\" 1. Redistributions of source code must retain the above copyright -.\" notice, this list of conditions and the following disclaimer. -.\" 2. Redistributions in binary form must reproduce the above copyright -.\" notice, this list of conditions and the following disclaimer in the -.\" documentation and/or other materials provided with the distribution. .\" 3. All advertising materials mentioning features or use of this software .\" must display the following acknowledgement: .\" This product includes software developed by the University of @@ -64,34 +34,46 @@ .\" SUCH DAMAGE. .\" .\" @(#)re_format.7 8.3 (Berkeley) 3/20/94 +.\" $FreeBSD: head/lib/libc/regex/re_format.7 314373 2017-02-28 05:14:42Z glebius $ .\" -.Dd March 20, 1994 +.Dd February 22, 2021 .Dt RE_FORMAT 7 .Os .Sh NAME .Nm re_format .Nd POSIX 1003.2 regular expressions .Sh DESCRIPTION -Regular expressions (``RE''s), -as defined in POSIX 1003.2, come in two forms: +Regular expressions +.Pq Dq RE Ns s , +as defined in +.St -p1003.2 , +come in two forms: modern REs (roughly those of .Xr egrep 1 ; -1003.2 calls these ``extended'' REs) +1003.2 calls these +.Dq extended +REs) and obsolete REs (roughly those of .Xr ed 1 ; -1003.2 ``basic'' REs). +1003.2 +.Dq basic +REs). Obsolete REs mostly exist for backward compatibility in some old programs; they will be discussed at the end. -1003.2 leaves some aspects of RE syntax and semantics open; -`(*)' marks decisions on these aspects that -may not be fully portable to other 1003.2 implementations. +.St -p1003.2 +leaves some aspects of RE syntax and semantics open; +`\(dd' marks decisions on these aspects that +may not be fully portable to other +.St -p1003.2 +implementations. .Pp -A (modern) RE is one(*) or more non-empty(*) +A (modern) RE is one\(dd or more non-empty\(dd .Em branches , -separated by `|'. +separated by +.Ql \&| . It matches anything that matches one of the branches. .Pp -A branch is one(*) or more +A branch is one\(dd or more .Em pieces , concatenated. It matches a match for the first, followed by a match for the second, etc. @@ -99,114 +81,205 @@ It matches a match for the first, followed by a match for the second, etc. A piece is an .Em atom possibly followed -by a single(*) `*', `+', `?', or +by a single\(dd +.Ql \&* , +.Ql \&+ , +.Ql \&? , +or .Em bound . -An atom followed by `*' matches a sequence of 0 or more matches of the atom. -An atom followed by `+' matches a sequence of 1 or more matches of the atom. -An atom followed by `?' matches a sequence of 0 or 1 matches of the atom. +An atom followed by +.Ql \&* +matches a sequence of 0 or more matches of the atom. +An atom followed by +.Ql \&+ +matches a sequence of 1 or more matches of the atom. +An atom followed by +.Ql ?\& +matches a sequence of 0 or 1 matches of the atom. .Pp A .Em bound -is `{' followed by an unsigned decimal integer, possibly followed by `,' +is +.Ql \&{ +followed by an unsigned decimal integer, +possibly followed by +.Ql \&, possibly followed by another unsigned decimal integer, -always followed by `}'. -The integers must lie between 0 and RE_DUP_MAX (255(*)) inclusive, +always followed by +.Ql \&} . +The integers must lie between 0 and +.Dv RE_DUP_MAX +(255\(dd) inclusive, and if there are two of them, the first may not exceed the second. An atom followed by a bound containing one integer .Em i -and no comma matches a sequence of exactly +and no comma matches +a sequence of exactly .Em i matches of the atom. -An atom followed by a bound containing one integer +An atom followed by a bound +containing one integer .Em i -and a comma matches a sequence of +and a comma matches +a sequence of .Em i or more matches of the atom. -An atom followed by a bound containing two integers +An atom followed by a bound +containing two integers .Em i and .Em j -matches a sequence of +matches +a sequence of .Em i through .Em j (inclusive) matches of the atom. .Pp -An atom is a regular expression enclosed in `()' (matching a match for the -regular expression), an empty set of `()' (matching the null string)(*), a +An atom is a regular expression enclosed in +.Ql () +(matching a match for the +regular expression), +an empty set of +.Ql () +(matching the null string)\(dd, +a .Em bracket expression -(see below), `.' (matching any single character), -`^' (matching the null string at the beginning of a line), -`$' (matching the null string at the end of a line), -a `\e' followed by one of the characters `^.[$()|*+?{\e' +(see below), +.Ql .\& +(matching any single character), +.Ql \&^ +(matching the null string at the beginning of a line), +.Ql \&$ +(matching the null string at the end of a line), a +.Ql \e +followed by one of the characters +.Ql ^.[$()|*+?{\e (matching that character taken as an ordinary character), -a `\e' followed by any other character(*) +a +.Ql \e +followed by any other character\(dd (matching that character taken as an ordinary character, -as if the `\e' had not been present(*)), +as if the +.Ql \e +had not been present\(dd), or a single character with no other significance (matching that character). -A `{' followed by a character other than a digit is an ordinary -character, not the beginning of a bound(*). -It is illegal to end an RE with `\e'. +A +.Ql \&{ +followed by a character other than a digit is an ordinary +character, not the beginning of a bound\(dd. +It is illegal to end an RE with +.Ql \e . .Pp A .Em bracket expression -is a list of characters enclosed in `[]'. +is a list of characters enclosed in +.Ql [] . It normally matches any single character from the list (but see below). -If the list begins with `^', -it matches any single character (but see below) +If the list begins with +.Ql \&^ , +it matches any single character +(but see below) .Em not from the rest of the list. -If two characters in the list are separated by `\-', this is shorthand +If two characters in the list are separated by +.Ql \&- , +this is shorthand for the full .Em range -of characters between those two (inclusive) in the collating sequence, -e.g. `[0-9]' in ASCII matches any decimal digit. -It is illegal(*) for two ranges to share an endpoint, e.g. `a-c-e'. +of characters between those two (inclusive) in the +collating sequence, +.No e.g. Ql [0-9] +in ASCII matches any decimal digit. +It is illegal\(dd for two ranges to share an +endpoint, +.No e.g. Ql a-c-e . Ranges are very collating-sequence-dependent, and portable programs should avoid relying on them. .Pp -To include a literal `]' in the list, make it the first character -(following a possible `^'). -To include a literal `\-', make it the first or last character, +To include a literal +.Ql \&] +in the list, make it the first character +(following a possible +.Ql \&^ ) . +To include a literal +.Ql \&- , +make it the first or last character, or the second endpoint of a range. -To use a literal `\-' as the first endpoint of a range, -enclose it in `[.' and `.]' to make it a collating element (see below). -With the exception of these and some combinations using `[' (see next -paragraphs), all other special characters, including `\e', lose their -special significance within a bracket expression. +To use a literal +.Ql \&- +as the first endpoint of a range, +enclose it in +.Ql [.\& +and +.Ql .]\& +to make it a collating element (see below). +With the exception of these and some combinations using +.Ql \&[ +(see next paragraphs), all other special characters, including +.Ql \e , +lose their special significance within a bracket expression. .Pp Within a bracket expression, a collating element (a character, a multi-character sequence that collates as if it were a single character, or a collating-sequence name for either) -enclosed in `[.' and `.]' stands for the +enclosed in +.Ql [.\& +and +.Ql .]\& +stands for the sequence of characters of that collating element. The sequence is a single element of the bracket expression's list. A bracket expression containing a multi-character collating element can thus match more than one character, -e.g. if the collating sequence includes a `ch' collating element, -then the RE `[[.ch.]]*c' matches the first five characters -of `chchcc'. +e.g.\& if the collating sequence includes a +.Ql ch +collating element, +then the RE +.Ql [[.ch.]]*c +matches the first five characters +of +.Ql chchcc . .Pp -Within a bracket expression, a collating element enclosed in `[=' and -`=]' is an equivalence class, standing for the sequences of characters +Within a bracket expression, a collating element enclosed in +.Ql [= +and +.Ql =] +is an equivalence class, standing for the sequences of characters of all collating elements equivalent to that one, including itself. (If there are no other equivalent collating elements, -the treatment is as if the enclosing delimiters were `[.' and `.]'.) -For example, if o and '\(^o' are the members of an equivalence class, -then `[[=o=]]', `[[=\(^o'=]]', and `[o\(^o']' are all synonymous. -An equivalence class may not(*) be an endpoint +the treatment is as if the enclosing delimiters were +.Ql [.\& +and +.Ql .] . ) +For example, if +.Ql x +and +.Ql y +are the members of an equivalence class, +then +.Ql [[=x=]] , +.Ql [[=y=]] , +and +.Ql [xy] +are all synonymous. +An equivalence class may not\(dd be an endpoint of a range. .Pp Within a bracket expression, the name of a .Em character class -enclosed in `[:' and `:]' stands for the list of all characters -belonging to that class. +enclosed in +.Ql [: +and +.Ql :] +stands for the list of all characters belonging to that +class. Standard character class names are: -.Bl -column "alnum" "digit" "xdigit" -.It alnum digit punct -.It alpha graph space -.It blank lower upper -.It cntrl print xdigit +.Bl -column "alnum" "digit" "xdigit" -offset indent +.It Em "alnum digit punct" +.It Em "alpha graph space" +.It Em "blank lower upper" +.It Em "cntrl print xdigit" .El .Pp These stand for the character classes defined in @@ -214,22 +287,44 @@ These stand for the character classes defined in A locale may provide others. A character class may not be used as an endpoint of a range. .Pp -There are two special cases(*) of bracket expressions: -the bracket expressions `[[:<:]]' and `[[:>:]]' match -the null string at the beginning and end of a word respectively. +A bracketed expression like +.Ql [[:class:]] +can be used to match a single character that belongs to a character +class. +The reverse, matching any character that does not belong to a specific +class, the negation operator of bracket expressions may be used: +.Ql [^[:class:]] . +.Pp +There are two special cases\(dd of bracket expressions: +the bracket expressions +.Ql [[:<:]] +and +.Ql [[:>:]] +match the null string at the beginning and end of a word respectively. A word is defined as a sequence of word characters -which is neither preceded nor followed by word characters. +which is neither preceded nor followed by +word characters. A word character is an .Em alnum character (as defined by .Xr ctype 3 ) or an underscore. -This is an extension, compatible with but not specified by POSIX 1003.2, -and should be used with caution in software intended to be portable -to other systems. +This is an extension, +compatible with but not specified by +.St -p1003.2 , +and should be used with +caution in software intended to be portable to other systems. +The additional word delimiters +.Ql \e< +and +.Ql \e> +are provided to ease compatibility with traditional +SVR4 +systems but are not portable and should be avoided. .Pp In the event that an RE could match more than one substring of a given -string, the RE matches the one starting earliest in the string. +string, +the RE matches the one starting earliest in the string. If the RE could match more than one substring starting at that point, it matches the longest. Subexpressions also match the longest possible substrings, subject to @@ -242,11 +337,23 @@ their lower-level component subexpressions. Match lengths are measured in characters, not collating elements. A null string is considered longer than no match at all. For example, -`bb*' matches the three middle characters of `abbbc', -`(wee|week)(knights|nights)' matches all ten characters of `weeknights', -when `(.*).*' is matched against `abc' the parenthesized subexpression +.Ql bb* +matches the three middle characters of +.Ql abbbc , +.Ql (wee|week)(knights|nights) +matches all ten characters of +.Ql weeknights , +when +.Ql (.*).*\& +is matched against +.Ql abc +the parenthesized subexpression matches all three characters, and -when `(a*)*' is matched against `bc' both the whole RE and the parenthesized +when +.Ql (a*)* +is matched against +.Ql bc +both the whole RE and the parenthesized subexpression match the null string. .Pp If case-independent matching is specified, @@ -255,61 +362,131 @@ alphabet. When an alphabetic that exists in multiple cases appears as an ordinary character outside a bracket expression, it is effectively transformed into a bracket expression containing both cases, -e.g. `x' becomes `[xX]'. +.No e.g. Ql x +becomes +.Ql [xX] . When it appears inside a bracket expression, all case counterparts -of it are added to the bracket expression, so that (e.g.) `[x]' -becomes `[xX]' and `[^x]' becomes `[^xX]'. +of it are added to the bracket expression, so that (e.g.) +.Ql [x] +becomes +.Ql [xX] +and +.Ql [^x] +becomes +.Ql [^xX] . .Pp -No particular limit is imposed on the length of REs(*). +No particular limit is imposed on the length of REs\(dd. Programs intended to be portable should not employ REs longer than 256 bytes, as an implementation can refuse to accept such REs and remain POSIX-compliant. .Pp -Obsolete (``basic'') regular expressions differ in several respects. -`|', `+', and `?' are ordinary characters and there is no equivalent -for their functionality. -The delimiters for bounds are `\e{' and `\e}', -with `{' and `}' by themselves ordinary characters. -The parentheses for nested subexpressions are `\e(' and `\e)', -with `(' and `)' by themselves ordinary characters. -`^' is an ordinary character except at the beginning of the -RE or(*) the beginning of a parenthesized subexpression, -`$' is an ordinary character except at the end of the -RE or(*) the end of a parenthesized subexpression, -and `*' is an ordinary character if it appears at the beginning of the +Obsolete +.Pq Dq basic +regular expressions differ in several respects. +.Ql \&| +is an ordinary character and there is no equivalent +for its functionality. +.Ql \&+ +and +.Ql ?\& +are ordinary characters, and their functionality +can be expressed using bounds +.Po +.Ql {1,} +or +.Ql {0,1} +respectively +.Pc . +Also note that +.Ql x+ +in modern REs is equivalent to +.Ql xx* . +The delimiters for bounds are +.Ql \e{ +and +.Ql \e} , +with +.Ql \&{ +and +.Ql \&} +by themselves ordinary characters. +The parentheses for nested subexpressions are +.Ql \e( +and +.Ql \e) , +with +.Ql \&( +and +.Ql \&) +by themselves ordinary characters. +.Ql \&^ +is an ordinary character except at the beginning of the +RE or\(dd the beginning of a parenthesized subexpression, +.Ql \&$ +is an ordinary character except at the end of the +RE or\(dd the end of a parenthesized subexpression, +and +.Ql \&* +is an ordinary character if it appears at the beginning of the RE or the beginning of a parenthesized subexpression -(after a possible leading `^'). +(after a possible leading +.Ql \&^ ) . Finally, there is one new type of atom, a .Em back reference : -`\e' followed by a non-zero decimal digit +.Ql \e +followed by a non-zero decimal digit .Em d matches the same sequence of characters matched by the -.Em d Ns th parenthesized subexpression +.Em d Ns th +parenthesized subexpression (numbering subexpressions by the positions of their opening parentheses, left to right), -so that (e.g.) `\e([bc]\e)\e1' matches `bb' or `cc' but not `bc'. +so that (e.g.) +.Ql \e([bc]\e)\e1 +matches +.Ql bb +or +.Ql cc +but not +.Ql bc . .Sh SEE ALSO .Xr regex 3 -.Pp -POSIX 1003.2, section 2.8 (Regular Expression Notation). +.Rs +.%T Regular Expression Notation +.%R IEEE Std +.%N 1003.2 +.%P section 2.8 +.Re .Sh BUGS Having two kinds of REs is a botch. .Pp -The current 1003.2 spec says that `)' is an ordinary character in -the absence of an unmatched `('; -this was an unintentional result of a wording error, and change is likely. +The current +.St -p1003.2 +spec says that +.Ql \&) +is an ordinary character in +the absence of an unmatched +.Ql \&( ; +this was an unintentional result of a wording error, +and change is likely. Avoid relying on it. .Pp Back references are a dreadful botch, posing major problems for efficient implementations. They are also somewhat vaguely defined -(does `a\e(\e(b\e)*\e2\e)*d' match `abbbd'?). +(does +.Ql a\e(\e(b\e)*\e2\e)*d +match +.Ql abbbd ? ) . Avoid using them. .Pp -1003.2's specification of case-independent matching is vague. -The ``one case implies all cases'' definition given above +.St -p1003.2 +specification of case-independent matching is vague. +The +.Dq one case implies all cases +definition given above is current consensus among implementors as to the right interpretation. .Pp The syntax for word boundaries is incredibly ugly. diff --git a/lib/libc/regex/regcomp.c b/lib/libc/regex/regcomp.c index 4a0d99af9a1..20cdcb4eba8 100644 --- a/lib/libc/regex/regcomp.c +++ b/lib/libc/regex/regcomp.c @@ -1,41 +1,16 @@ -/* $NetBSD: regcomp.c,v 1.38 2019/02/07 22:22:31 christos Exp $ */ +/* $NetBSD: regcomp.c,v 1.39 2021/02/23 22:14:59 christos Exp $ */ /*- + * SPDX-License-Identifier: BSD-3-Clause + * + * Copyright (c) 1992, 1993, 1994 Henry Spencer. * Copyright (c) 1992, 1993, 1994 * The Regents of the University of California. All rights reserved. * - * This code is derived from software contributed to Berkeley by - * Henry Spencer. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * 3. Neither the name of the University nor the names of its contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND - * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE - * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL - * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS - * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) - * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT - * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY - * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF - * SUCH DAMAGE. - * - * @(#)regcomp.c 8.5 (Berkeley) 3/20/94 - */ - -/*- - * Copyright (c) 1992, 1993, 1994 Henry Spencer. + * Copyright (c) 2011 The FreeBSD Foundation + * All rights reserved. + * Portions of this software were developed by David Chisnall + * under sponsorship from the FreeBSD Foundation. * * This code is derived from software contributed to Berkeley by * Henry Spencer. @@ -48,11 +23,7 @@ * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. - * 3. All advertising materials mentioning features or use of this software - * must display the following acknowledgement: - * This product includes software developed by the University of - * California, Berkeley and its contributors. - * 4. Neither the name of the University nor the names of its contributors + * 3. Neither the name of the University nor the names of its contributors * may be used to endorse or promote products derived from this software * without specific prior written permission. * @@ -72,36 +43,59 @@ */ #include <sys/cdefs.h> -#if defined(LIBC_SCCS) && !defined(lint) #if 0 static char sccsid[] = "@(#)regcomp.c 8.5 (Berkeley) 3/20/94"; -#else -__RCSID("$NetBSD: regcomp.c,v 1.38 2019/02/07 22:22:31 christos Exp $"); +__FBSDID("$FreeBSD: head/lib/libc/regex/regcomp.c 368359 2020-12-05 03:18:48Z kevans $"); #endif -#endif /* LIBC_SCCS and not lint */ +__RCSID("$NetBSD: regcomp.c,v 1.39 2021/02/23 22:14:59 christos Exp $"); + +#define _OPENBSD_SOURCE +#define REGEX_GNU_EXTENSIONS #include "namespace.h" #include <sys/types.h> - -#include <assert.h> +#include <stdio.h> +#include <string.h> #include <ctype.h> #include <limits.h> -#include <stdio.h> #include <stdlib.h> -#include <string.h> #include <regex.h> +#include <stdbool.h> +#include <wchar.h> +#include <wctype.h> #ifdef __weak_alias __weak_alias(regcomp,_regcomp) #endif +#ifdef REGEX_LIBC_COLLATE +#include "collate.h" +#endif + #include "utils.h" #include "regex2.h" -#include "cclass.h" #include "cname.h" /* + * Branching context, used to keep track of branch state for all of the branch- + * aware functions. In addition to keeping track of branch positions for the + * p_branch_* functions, we use this to simplify some clumsiness in BREs for + * detection of whether ^ is acting as an anchor or being used erroneously and + * also for whether we're in a sub-expression or not. + */ +struct branchc { + sopno start; + sopno back; + sopno fwd; + + int nbranch; + int nchain; + bool outer; + bool terminate; +}; + +/* * parse structure, passed up and down to avoid global variables and * other clumsinesses */ @@ -109,6 +103,7 @@ struct parse { const char *next; /* next character in RE */ const char *end; /* end of string (-> NUL normally) */ int error; /* has an error been seen? */ + int gnuext; sop *strip; /* malloced strip */ sopno ssize; /* malloced strip size (allocated) */ sopno slen; /* malloced strip length (used) */ @@ -117,56 +112,70 @@ struct parse { # define NPAREN 10 /* we need to remember () 1-9 for back refs */ sopno pbegin[NPAREN]; /* -> ( ([0] unused) */ sopno pend[NPAREN]; /* -> ) ([0] unused) */ + bool allowbranch; /* can this expression branch? */ + bool bre; /* convenience; is this a BRE? */ + int pflags; /* other parsing flags -- legacy escapes? */ + bool (*parse_expr)(struct parse *, struct branchc *); + void (*pre_parse)(struct parse *, struct branchc *); + void (*post_parse)(struct parse *, struct branchc *); }; +#define PFLAG_LEGACY_ESC 0x00000001 + /* ========= begin header generated by ./mkh ========= */ #ifdef __cplusplus extern "C" { #endif /* === regcomp.c === */ -static void p_ere(struct parse *p, int stop, size_t reclimit); -static void p_ere_exp(struct parse *p, size_t reclimit); +static bool p_ere_exp(struct parse *p, struct branchc *bc); static void p_str(struct parse *p); -static void p_bre(struct parse *p, int end1, int end2, size_t reclimit); -static int p_simp_re(struct parse *p, int starordinary, size_t reclimit); +static int p_branch_eat_delim(struct parse *p, struct branchc *bc); +static void p_branch_ins_offset(struct parse *p, struct branchc *bc); +static void p_branch_fix_tail(struct parse *p, struct branchc *bc); +static bool p_branch_empty(struct parse *p, struct branchc *bc); +static bool p_branch_do(struct parse *p, struct branchc *bc); +static void p_bre_pre_parse(struct parse *p, struct branchc *bc); +static void p_bre_post_parse(struct parse *p, struct branchc *bc); +static void p_re(struct parse *p, int end1, int end2); +static bool p_simp_re(struct parse *p, struct branchc *bc); static int p_count(struct parse *p); static void p_bracket(struct parse *p); +static int p_range_cmp(wchar_t c1, wchar_t c2); static void p_b_term(struct parse *p, cset *cs); +#ifdef REGEX_GNU_EXTENSIONS +static int p_b_pseudoclass(struct parse *p, char c); +#endif static void p_b_cclass(struct parse *p, cset *cs); +static void p_b_cclass_named(struct parse *p, cset *cs, const char[]); static void p_b_eclass(struct parse *p, cset *cs); -static char p_b_symbol(struct parse *p); -static char p_b_coll_elem(struct parse *p, int endc); -static int othercase(int ch); -static void bothcases(struct parse *p, int ch); -static void ordinary(struct parse *p, int ch); +static wint_t p_b_symbol(struct parse *p); +static wint_t p_b_coll_elem(struct parse *p, wint_t endc); +static bool may_escape(struct parse *p, const wint_t ch); +static wint_t othercase(wint_t ch); +static void bothcases(struct parse *p, wint_t ch); +static void ordinary(struct parse *p, wint_t ch); static void nonnewline(struct parse *p); -static void repeat(struct parse *p, sopno start, int from, int to, size_t reclimit); +static void repeat(struct parse *p, sopno start, int from, int to); static int seterr(struct parse *p, int e); static cset *allocset(struct parse *p); static void freeset(struct parse *p, cset *cs); -static sopno freezeset(struct parse *p, cset *cs); -static int firstch(struct parse *p, cset *cs); -static int nch(struct parse *p, cset *cs); -static void mcadd(struct parse *p, cset *cs, const char *cp); -#if 0 -static void mcsub(cset *cs, char *cp); -static int mcin(cset *cs, char *cp); -static char *mcfind(cset *cs, char *cp); -#endif -static void mcinvert(struct parse *p, cset *cs); -static void mccase(struct parse *p, cset *cs); -static int isinsets(struct re_guts *g, int c); -static int samesets(struct re_guts *g, int c1, int c2); -static void categorize(struct parse *p, struct re_guts *g); +static void CHadd(struct parse *p, cset *cs, wint_t ch); +static void CHaddrange(struct parse *p, cset *cs, wint_t min, wint_t max); +static void CHaddtype(struct parse *p, cset *cs, wctype_t wct); +static wint_t singleton(cset *cs); static sopno dupl(struct parse *p, sopno start, sopno finish); -static void doemit(struct parse *p, sop op, sopno opnd); -static void doinsert(struct parse *p, sop op, sopno opnd, sopno pos); -static void dofwd(struct parse *p, sopno pos, sopno value); +static void doemit(struct parse *p, sop op, size_t opnd); +static void doinsert(struct parse *p, sop op, size_t opnd, sopno pos); +static void dofwd(struct parse *p, sopno pos, sop value); static int enlarge(struct parse *p, sopno size); static void stripsnug(struct parse *p, struct re_guts *g); static void findmust(struct parse *p, struct re_guts *g); +static int altoffset(sop *scan, int offset); +static void computejumps(struct parse *p, struct re_guts *g); +static void computematchjumps(struct parse *p, struct re_guts *g); static sopno pluscount(struct parse *p, struct re_guts *g); +static wint_t wgetnext(struct parse *p); #ifdef __cplusplus } @@ -185,18 +194,21 @@ static char nuls[10]; /* place to point scanner in event of error */ #define MORE2() (p->next+1 < p->end) #define SEE(c) (MORE() && PEEK() == (c)) #define SEETWO(a, b) (MORE() && MORE2() && PEEK() == (a) && PEEK2() == (b)) +#define SEESPEC(a) (p->bre ? SEETWO('\\', a) : SEE(a)) #define EAT(c) ((SEE(c)) ? (NEXT(), 1) : 0) #define EATTWO(a, b) ((SEETWO(a, b)) ? (NEXT2(), 1) : 0) +#define EATSPEC(a) (p->bre ? EATTWO('\\', a) : EAT(a)) #define NEXT() (p->next++) #define NEXT2() (p->next += 2) #define NEXTn(n) (p->next += (n)) #define GETNEXT() (*p->next++) +#define WGETNEXT() wgetnext(p) #define SETERROR(e) seterr(p, (e)) -#define REQUIRE(co, e) (void) ((co) || SETERROR(e)) +#define REQUIRE(co, e) ((co) || SETERROR(e)) #define MUSTSEE(c, e) (REQUIRE(MORE() && PEEK() == (c), e)) -#define MUSTEAT(c, e) (void) (REQUIRE(MORE() && GETNEXT() == (c), e)) +#define MUSTEAT(c, e) (REQUIRE(MORE() && GETNEXT() == (c), e)) #define MUSTNOTSEE(c, e) (REQUIRE(!MORE() || PEEK() != (c), e)) -#define EMIT(op, sopnd) doemit(p, (sop)(op), sopnd) +#define EMIT(op, sopnd) doemit(p, (sop)(op), (size_t)(sopnd)) #define INSERT(op, pos) doinsert(p, (sop)(op), HERE()-(pos)+1, pos) #define AHEAD(pos) dofwd(p, pos, HERE()-(pos)) #define ASTERN(sop, pos) EMIT(sop, HERE()-pos) @@ -205,42 +217,20 @@ static char nuls[10]; /* place to point scanner in event of error */ #define THERETHERE() (p->slen - 2) #define DROP(n) (p->slen -= (n)) -#ifndef NDEBUG -static int never = 0; /* for use in asserts; shuts lint up */ -#else -#define never 0 /* some <assert.h>s have bugs too */ -#endif - -#define MEMLIMIT 0x8000000 -#define MEMSIZE(p) \ - ((p)->ncsalloc / CHAR_BIT * (p)->g->csetsize + \ - (p)->ncsalloc * sizeof(cset) + \ - (p)->ssize * sizeof(sop)) -#define RECLIMIT 256 +/* Macro used by computejump()/computematchjump() */ +#define MIN(a,b) ((a)<(b)?(a):(b)) -/* - - regcomp - interface for parser and compilation - = extern int regcomp(regex_t *, const char *, int); - = #define REG_BASIC 0000 - = #define REG_EXTENDED 0001 - = #define REG_ICASE 0002 - = #define REG_NOSUB 0004 - = #define REG_NEWLINE 0010 - = #define REG_NOSPEC 0020 - = #define REG_PEND 0040 - = #define REG_DUMP 0200 - */ -int /* 0 success, otherwise REG_something */ -regcomp( - regex_t *preg, - const char *pattern, - int cflags) +static int /* 0 success, otherwise REG_something */ +regcomp_internal(regex_t * __restrict preg, + const char * __restrict pattern, + int cflags, int pflags) { struct parse pa; struct re_guts *g; struct parse *p = &pa; int i; size_t len; + size_t maxlen; #ifdef REDEBUG # define GOODFLAGS(f) (f) #else @@ -262,59 +252,103 @@ regcomp( len = strlen(pattern); /* do the mallocs early so failure handling is easy */ - g = malloc(sizeof(struct re_guts) + (NC - 1) * sizeof(cat_t)); + g = malloc(sizeof(*g)); if (g == NULL) return(REG_ESPACE); + /* + * Limit the pattern space to avoid a 32-bit overflow on buffer + * extension. Also avoid any signed overflow in case of conversion + * so make the real limit based on a 31-bit overflow. + * + * Likely not applicable on 64-bit systems but handle the case + * generically (who are we to stop people from using ~715MB+ + * patterns?). + */ + maxlen = ((size_t)-1 >> 1) / sizeof(sop) * 2 / 3; + if (len >= maxlen) { + free((char *)g); + return(REG_ESPACE); + } p->ssize = len/(size_t)2*(size_t)3 + (size_t)1; /* ugh */ - p->strip = calloc(p->ssize, sizeof(sop)); + assert(p->ssize >= len); + + p->strip = calloc(p->ssize, sizeof(*p->strip)); p->slen = 0; if (p->strip == NULL) { - free(g); + free((char *)g); return(REG_ESPACE); } /* set things up */ p->g = g; - p->next = pattern; + p->next = pattern; /* convenience; we do not modify it */ p->end = p->next + len; p->error = 0; p->ncsalloc = 0; + p->pflags = pflags; for (i = 0; i < NPAREN; i++) { p->pbegin[i] = 0; p->pend[i] = 0; } - g->csetsize = NC; +#ifdef REGEX_GNU_EXTENSIONS + if ((cflags & REG_GNU) == 0) { + p->gnuext = false; + p->allowbranch = (cflags & REG_EXTENDED) != 0; + } else + p->gnuext = p->allowbranch = true; +#else + p->gnuext = false; + p->allowbranch = (cflags & REG_EXTENDED) != 0; +#endif + if (cflags & REG_EXTENDED) { + p->bre = false; + p->parse_expr = p_ere_exp; + p->pre_parse = NULL; + p->post_parse = NULL; + } else { + p->bre = true; + p->parse_expr = p_simp_re; + p->pre_parse = p_bre_pre_parse; + p->post_parse = p_bre_post_parse; + } g->sets = NULL; - g->setbits = NULL; g->ncsets = 0; g->cflags = cflags; g->iflags = 0; g->nbol = 0; g->neol = 0; g->must = NULL; + g->moffset = -1; + g->charjump = NULL; + g->matchjump = NULL; g->mlen = 0; g->nsub = 0; - g->ncategories = 1; /* category 0 is "everything else" */ - g->categories = &g->catspace[-(CHAR_MIN)]; - (void) memset((char *)g->catspace, 0, NC*sizeof(cat_t)); g->backrefs = 0; /* do it */ EMIT(OEND, 0); g->firststate = THERE(); - if (cflags®_EXTENDED) - p_ere(p, OUT, 0); - else if (cflags®_NOSPEC) + if (cflags & REG_NOSPEC) p_str(p); else - p_bre(p, OUT, OUT, 0); + p_re(p, OUT, OUT); EMIT(OEND, 0); g->laststate = THERE(); /* tidy up loose ends and fill things in */ - categorize(p, g); stripsnug(p, g); findmust(p, g); + /* only use Boyer-Moore algorithm if the pattern is bigger + * than three characters + */ + if(g->mlen > 3) { + computejumps(p, g); + computematchjumps(p, g); + if(g->matchjump == NULL && g->charjump != NULL) { + free(g->charjump); + g->charjump = NULL; + } + } g->nplus = pluscount(p, g); g->magic = MAGIC2; preg->re_nsub = g->nsub; @@ -333,97 +367,72 @@ regcomp( } /* - - p_ere - ERE parser top level, concatenation and alternation - == static void p_ere(struct parse *p, int stop, size_t reclimit); + - regcomp - interface for parser and compilation + = extern int regcomp(regex_t *, const char *, int); + = #define REG_BASIC 0000 + = #define REG_EXTENDED 0001 + = #define REG_ICASE 0002 + = #define REG_NOSUB 0004 + = #define REG_NEWLINE 0010 + = #define REG_NOSPEC 0020 + = #define REG_PEND 0040 + = #define REG_DUMP 0200 */ -static void -p_ere( - struct parse *p, - int stop, /* character this ERE should end at */ - size_t reclimit) +int /* 0 success, otherwise REG_something */ +regcomp(regex_t * __restrict preg, + const char * __restrict pattern, + int cflags) { - char c; - sopno prevback = 0; /* pacify gcc */ - sopno prevfwd = 0; /* pacify gcc */ - sopno conc; - int first = 1; /* is this the first alternative? */ - - _DIAGASSERT(p != NULL); - - if (reclimit++ > RECLIMIT || p->error == REG_ESPACE) { - p->error = REG_ESPACE; - return; - } - - for (;;) { - /* do a bunch of concatenated expressions */ - conc = HERE(); - while (MORE() && (c = PEEK()) != '|' && c != stop) - p_ere_exp(p, reclimit); - REQUIRE(HERE() != conc, REG_EMPTY); /* require nonempty */ - - if (!EAT('|')) - break; /* NOTE BREAK OUT */ - - if (first) { - INSERT(OCH_, conc); /* offset is wrong */ - prevfwd = conc; - prevback = conc; - first = 0; - } - ASTERN(OOR1, prevback); - prevback = THERE(); - AHEAD(prevfwd); /* fix previous offset */ - prevfwd = HERE(); - EMIT(OOR2, 0); /* offset is very wrong */ - } - - if (!first) { /* tail-end fixups */ - AHEAD(prevfwd); - ASTERN(O_CH, prevback); - } - assert(!MORE() || SEE(stop)); + return (regcomp_internal(preg, pattern, cflags, 0)); } /* - - p_ere_exp - parse one subERE, an atom possibly followed by a repetition op - == static void p_ere_exp(struct parse *p, size_t reclimit); + - p_ere_exp - parse one subERE, an atom possibly followed by a repetition op, + - return whether we should terminate or not + == static bool p_ere_exp(struct parse *p); */ -static void -p_ere_exp( - struct parse *p, - size_t reclimit) +static bool +p_ere_exp(struct parse *p, struct branchc *bc) { char c; + wint_t wc; sopno pos; int count; int count2; +#ifdef REGEX_GNU_EXTENSIONS + int i; + int handled; +#endif sopno subno; int wascaret = 0; _DIAGASSERT(p != NULL); + (void)bc; assert(MORE()); /* caller should have ensured this */ c = GETNEXT(); +#ifdef REGEX_GNU_EXTENSIONS + handled = 0; +#endif pos = HERE(); switch (c) { case '(': - REQUIRE(MORE(), REG_EPAREN); + (void)REQUIRE(MORE(), REG_EPAREN); p->g->nsub++; subno = p->g->nsub; if (subno < NPAREN) p->pbegin[subno] = HERE(); EMIT(OLPAREN, subno); if (!SEE(')')) - p_ere(p, ')', reclimit); + p_re(p, ')', IGN); if (subno < NPAREN) { p->pend[subno] = HERE(); assert(p->pend[subno] != 0); } EMIT(ORPAREN, subno); - MUSTEAT(')', REG_EPAREN); + (void)MUSTEAT(')', REG_EPAREN); break; #ifndef POSIX_MISTAKE case ')': /* happens only if no current unmatched ( */ @@ -454,6 +463,7 @@ p_ere_exp( case '*': case '+': case '?': + case '{': SETERROR(REG_BADRPT); break; case '.': @@ -466,30 +476,97 @@ p_ere_exp( p_bracket(p); break; case '\\': - REQUIRE(MORE(), REG_EESCAPE); - c = GETNEXT(); - ordinary(p, c); + (void)REQUIRE(MORE(), REG_EESCAPE); + wc = WGETNEXT(); +#ifdef REGEX_GNU_EXTENSIONS + if (p->gnuext) { + handled = 1; + switch (wc) { + case '`': + EMIT(OBOS, 0); + break; + case '\'': + EMIT(OEOS, 0); + break; + case 'B': + EMIT(ONWBND, 0); + break; + case 'b': + EMIT(OWBND, 0); + break; + case 'W': + case 'w': + case 'S': + case 's': + p_b_pseudoclass(p, wc); + break; + case '1': + case '2': + case '3': + case '4': + case '5': + case '6': + case '7': + case '8': + case '9': + i = wc - '0'; + assert(i < NPAREN); + if (p->pend[i] != 0) { + assert(i <= p->g->nsub); + EMIT(OBACK_, i); + assert(p->pbegin[i] != 0); + assert(OP(p->strip[p->pbegin[i]]) == OLPAREN); + assert(OP(p->strip[p->pend[i]]) == ORPAREN); + (void) dupl(p, p->pbegin[i]+1, p->pend[i]); + EMIT(O_BACK, i); + } else + SETERROR(REG_ESUBREG); + p->g->backrefs = 1; + break; + default: + handled = 0; + } + /* Don't proceed to the POSIX bits if we've already handled it */ + if (handled) + break; + } +#endif + switch (wc) { + case '<': + EMIT(OBOW, 0); + break; + case '>': + EMIT(OEOW, 0); + break; + default: + if (may_escape(p, wc)) + ordinary(p, wc); + else + SETERROR(REG_EESCAPE); + break; + } break; - case '{': /* okay as ordinary except if digit follows */ - REQUIRE(!MORE() || !isdigit((unsigned char)PEEK()), REG_BADRPT); - /* FALLTHROUGH */ default: if (p->error != 0) - return; - ordinary(p, c); + return (false); + p->next--; + wc = WGETNEXT(); + ordinary(p, wc); break; } if (!MORE()) - return; + return (false); c = PEEK(); /* we call { a repetition if followed by a digit */ - if (!( c == '*' || c == '+' || c == '?' || - (c == '{' && MORE2() && isdigit((unsigned char)PEEK2())) )) - return; /* no repetition, we're done */ + if (!( c == '*' || c == '+' || c == '?' || c == '{')) + return (false); /* no repetition, we're done */ + else if (c == '{') + (void)REQUIRE(MORE2() && \ + (isdigit((uch)PEEK2()) || PEEK2() == ','), REG_BADRPT); NEXT(); - REQUIRE(!wascaret, REG_BADRPT); + (void)REQUIRE(!wascaret, REG_BADRPT); switch (c) { case '*': /* implemented as +? */ /* this case does not require the (y|) trick, noKLUDGE */ @@ -514,30 +591,31 @@ p_ere_exp( case '{': count = p_count(p); if (EAT(',')) { - if (isdigit((unsigned char)PEEK())) { + if (isdigit((uch)PEEK())) { count2 = p_count(p); - REQUIRE(count <= count2, REG_BADBR); + (void)REQUIRE(count <= count2, REG_BADBR); } else /* single number with comma */ count2 = INFINITY; } else /* just a single number */ count2 = count; - repeat(p, pos, count, count2, 0); + repeat(p, pos, count, count2); if (!EAT('}')) { /* error heuristics */ while (MORE() && PEEK() != '}') NEXT(); - REQUIRE(MORE(), REG_EBRACE); + (void)REQUIRE(MORE(), REG_EBRACE); SETERROR(REG_BADBR); } break; } if (!MORE()) - return; + return (false); c = PEEK(); if (!( c == '*' || c == '+' || c == '?' || - (c == '{' && MORE2() && isdigit((unsigned char)PEEK2())) ) ) - return; + (c == '{' && MORE2() && isdigit((uch)PEEK2())) ) ) + return (false); SETERROR(REG_BADRPT); + return (false); } /* @@ -545,159 +623,329 @@ p_ere_exp( == static void p_str(struct parse *p); */ static void -p_str( - struct parse *p) +p_str(struct parse *p) { + (void)REQUIRE(MORE(), REG_EMPTY); + while (MORE()) + ordinary(p, WGETNEXT()); +} - _DIAGASSERT(p != NULL); +/* + * Eat consecutive branch delimiters for the kind of expression that we are + * parsing, return the number of delimiters that we ate. + */ +static int +p_branch_eat_delim(struct parse *p, struct branchc *bc) +{ + int nskip; - REQUIRE(MORE(), REG_EMPTY); - while (MORE()) - ordinary(p, GETNEXT()); + (void)bc; + nskip = 0; + while (EATSPEC('|')) + ++nskip; + return (nskip); } /* - - p_bre - BRE parser top level, anchoring and concatenation - == static void p_bre(struct parse *p, int end1, \ - == int end2, size_t reclimit); - * Giving end1 as OUT essentially eliminates the end1/end2 check. - * - * This implementation is a bit of a kludge, in that a trailing $ is first - * taken as an ordinary character and then revised to be an anchor. The - * only undesirable side effect is that '$' gets included as a character - * category in such cases. This is fairly harmless; not worth fixing. - * The amount of lookahead needed to avoid this kludge is excessive. + * Insert necessary branch book-keeping operations. This emits a + * bogus 'next' offset, since we still have more to parse */ static void -p_bre( - struct parse *p, - int end1, /* first terminating character */ - int end2, /* second terminating character */ - size_t reclimit) +p_branch_ins_offset(struct parse *p, struct branchc *bc) { - sopno start; - int first = 1; /* first subexpression? */ - int wasdollar = 0; - _DIAGASSERT(p != NULL); + if (bc->nbranch == 0) { + INSERT(OCH_, bc->start); /* offset is wrong */ + bc->fwd = bc->start; + bc->back = bc->start; + } - if (reclimit++ > RECLIMIT || p->error == REG_ESPACE) { - p->error = REG_ESPACE; - return; + ASTERN(OOR1, bc->back); + bc->back = THERE(); + AHEAD(bc->fwd); /* fix previous offset */ + bc->fwd = HERE(); + EMIT(OOR2, 0); /* offset is very wrong */ + ++bc->nbranch; +} + +/* + * Fix the offset of the tail branch, if we actually had any branches. + * This is to correct the bogus placeholder offset that we use. + */ +static void +p_branch_fix_tail(struct parse *p, struct branchc *bc) +{ + + /* Fix bogus offset at the tail if we actually have branches */ + if (bc->nbranch > 0) { + AHEAD(bc->fwd); + ASTERN(O_CH, bc->back); } +} + +/* + * Signal to the parser that an empty branch has been encountered; this will, + * in the future, be used to allow for more permissive behavior with empty + * branches. The return value should indicate whether parsing may continue + * or not. + */ +static bool +p_branch_empty(struct parse *p, struct branchc *bc) +{ + + (void)bc; + SETERROR(REG_EMPTY); + return (false); +} + +/* + * Take care of any branching requirements. This includes inserting the + * appropriate branching instructions as well as eating all of the branch + * delimiters until we either run out of pattern or need to parse more pattern. + */ +static bool +p_branch_do(struct parse *p, struct branchc *bc) +{ + int ate = 0; + + ate = p_branch_eat_delim(p, bc); + if (ate == 0) + return (false); + else if ((ate > 1 || (bc->outer && !MORE())) && !p_branch_empty(p, bc)) + /* + * Halt parsing only if we have an empty branch and p_branch_empty + * indicates that we must not continue. In the future, this will not + * necessarily be an error. + */ + return (false); + p_branch_ins_offset(p, bc); - start = HERE(); + return (true); +} + +static void +p_bre_pre_parse(struct parse *p, struct branchc *bc) +{ + (void) bc; + /* + * Does not move cleanly into expression parser because of + * ordinary interpration of * at the beginning position of + * an expression. + */ if (EAT('^')) { EMIT(OBOL, 0); p->g->iflags |= USEBOL; p->g->nbol++; } - while (MORE() && !SEETWO(end1, end2)) { - wasdollar = p_simp_re(p, first, reclimit); - first = 0; - } - if (wasdollar) { /* oops, that was a trailing anchor */ +} + +static void +p_bre_post_parse(struct parse *p, struct branchc *bc) +{ + + /* Expression is terminating due to EOL token */ + if (bc->terminate) { DROP(1); EMIT(OEOL, 0); p->g->iflags |= USEEOL; p->g->neol++; } +} + +/* + - p_re - Top level parser, concatenation and BRE anchoring + == static void p_re(struct parse *p, int end1, int end2); + * Giving end1 as OUT essentially eliminates the end1/end2 check. + * + * This implementation is a bit of a kludge, in that a trailing $ is first + * taken as an ordinary character and then revised to be an anchor. + * The amount of lookahead needed to avoid this kludge is excessive. + */ +static void +p_re(struct parse *p, + int end1, /* first terminating character */ + int end2) /* second terminating character; ignored for EREs */ +{ + struct branchc bc; - REQUIRE(HERE() != start, REG_EMPTY); /* require nonempty */ + bc.nbranch = 0; + if (end1 == OUT && end2 == OUT) + bc.outer = true; + else + bc.outer = false; +#define SEEEND() (!p->bre ? SEE(end1) : SEETWO(end1, end2)) + for (;;) { + bc.start = HERE(); + bc.nchain = 0; + bc.terminate = false; + if (p->pre_parse != NULL) + p->pre_parse(p, &bc); + while (MORE() && (!p->allowbranch || !SEESPEC('|')) && !SEEEND()) { + bc.terminate = p->parse_expr(p, &bc); + ++bc.nchain; + } + if (p->post_parse != NULL) + p->post_parse(p, &bc); + (void) REQUIRE(p->gnuext || HERE() != bc.start, REG_EMPTY); +#ifdef REGEX_GNU_EXTENSIONS + if (p->gnuext && HERE() == bc.start && !p_branch_empty(p, &bc)) + break; +#endif + if (!p->allowbranch) + break; + /* + * p_branch_do's return value indicates whether we should + * continue parsing or not. This is both for correctness and + * a slight optimization, because it will check if we've + * encountered an empty branch or the end of the string + * immediately following a branch delimiter. + */ + if (!p_branch_do(p, &bc)) + break; + } +#undef SEE_END + if (p->allowbranch) + p_branch_fix_tail(p, &bc); + assert(!MORE() || SEE(end1)); } /* - p_simp_re - parse a simple RE, an atom possibly followed by a repetition - == static int p_simp_re(struct parse *p, int starordinary, size_t reclimit); + == static bool p_simp_re(struct parse *p, struct branchc *bc); */ -static int /* was the simple RE an unbackslashed $? */ -p_simp_re( - struct parse *p, - int starordinary, /* is a leading * an ordinary character? */ - size_t reclimit) +static bool /* was the simple RE an unbackslashed $? */ +p_simp_re(struct parse *p, struct branchc *bc) { int c; + int cc; /* convenient/control character */ int count; int count2; - sopno pos, i; + sopno pos; + bool handled; + int i; + wint_t wc; sopno subno; # define BACKSL (1<<CHAR_BIT) - _DIAGASSERT(p != NULL); - - pos = HERE(); /* repetion op, if any, covers from here */ + pos = HERE(); /* repetition op, if any, covers from here */ + handled = false; assert(MORE()); /* caller should have ensured this */ c = GETNEXT(); if (c == '\\') { - REQUIRE(MORE(), REG_EESCAPE); - c = BACKSL | (unsigned char)GETNEXT(); + (void)REQUIRE(MORE(), REG_EESCAPE); + cc = GETNEXT(); + c = BACKSL | cc; +#ifdef REGEX_GNU_EXTENSIONS + if (p->gnuext) { + handled = true; + switch (c) { + case BACKSL|'`': + EMIT(OBOS, 0); + break; + case BACKSL|'\'': + EMIT(OEOS, 0); + break; + case BACKSL|'B': + EMIT(ONWBND, 0); + break; + case BACKSL|'b': + EMIT(OWBND, 0); + break; + case BACKSL|'W': + case BACKSL|'w': + case BACKSL|'S': + case BACKSL|'s': + p_b_pseudoclass(p, cc); + break; + default: + handled = false; + } + } +#endif } - switch (c) { - case '.': - if (p->g->cflags®_NEWLINE) - nonnewline(p); - else - EMIT(OANY, 0); - break; - case '[': - p_bracket(p); - break; - case BACKSL|'{': - SETERROR(REG_BADRPT); - break; - case BACKSL|'(': - p->g->nsub++; - subno = p->g->nsub; - if (subno < NPAREN) - p->pbegin[subno] = HERE(); - EMIT(OLPAREN, subno); - /* the MORE here is an error heuristic */ - if (MORE() && !SEETWO('\\', ')')) - p_bre(p, '\\', ')', reclimit); - if (subno < NPAREN) { - p->pend[subno] = HERE(); - assert(p->pend[subno] != 0); + if (!handled) { + switch (c) { + case '.': + if (p->g->cflags®_NEWLINE) + nonnewline(p); + else + EMIT(OANY, 0); + break; + case '[': + p_bracket(p); + break; + case BACKSL|'<': + EMIT(OBOW, 0); + break; + case BACKSL|'>': + EMIT(OEOW, 0); + break; + case BACKSL|'{': + SETERROR(REG_BADRPT); + break; + case BACKSL|'(': + p->g->nsub++; + subno = p->g->nsub; + if (subno < NPAREN) + p->pbegin[subno] = HERE(); + EMIT(OLPAREN, subno); + /* the MORE here is an error heuristic */ + if (MORE() && !SEETWO('\\', ')')) + p_re(p, '\\', ')'); + if (subno < NPAREN) { + p->pend[subno] = HERE(); + assert(p->pend[subno] != 0); + } + EMIT(ORPAREN, subno); + (void)REQUIRE(EATTWO('\\', ')'), REG_EPAREN); + break; + case BACKSL|')': /* should not get here -- must be user */ + SETERROR(REG_EPAREN); + break; + case BACKSL|'1': + case BACKSL|'2': + case BACKSL|'3': + case BACKSL|'4': + case BACKSL|'5': + case BACKSL|'6': + case BACKSL|'7': + case BACKSL|'8': + case BACKSL|'9': + i = (c&~BACKSL) - '0'; + assert(i < NPAREN); + if (p->pend[i] != 0) { + assert(i <= p->g->nsub); + EMIT(OBACK_, i); + assert(p->pbegin[i] != 0); + assert(OP(p->strip[p->pbegin[i]]) == OLPAREN); + assert(OP(p->strip[p->pend[i]]) == ORPAREN); + (void) dupl(p, p->pbegin[i]+1, p->pend[i]); + EMIT(O_BACK, i); + } else + SETERROR(REG_ESUBREG); + p->g->backrefs = 1; + break; + case '*': + /* + * Ordinary if used as the first character beyond BOL anchor of + * a (sub-)expression, counts as a bad repetition operator if it + * appears otherwise. + */ + (void)REQUIRE(bc->nchain == 0, REG_BADRPT); + /* FALLTHROUGH */ + default: + if (p->error != 0) + return (false); /* Definitely not $... */ + p->next--; + wc = WGETNEXT(); + if ((c & BACKSL) == 0 || may_escape(p, wc)) + ordinary(p, wc); + else + SETERROR(REG_EESCAPE); + break; } - EMIT(ORPAREN, subno); - REQUIRE(EATTWO('\\', ')'), REG_EPAREN); - break; - case BACKSL|')': /* should not get here -- must be user */ - case BACKSL|'}': - SETERROR(REG_EPAREN); - break; - case BACKSL|'1': - case BACKSL|'2': - case BACKSL|'3': - case BACKSL|'4': - case BACKSL|'5': - case BACKSL|'6': - case BACKSL|'7': - case BACKSL|'8': - case BACKSL|'9': - i = (c&~BACKSL) - '0'; - assert(i < NPAREN); - if (p->pend[i] != 0) { - assert(i <= p->g->nsub); - EMIT(OBACK_, i); - assert(p->pbegin[i] != 0); - assert(OP(p->strip[p->pbegin[i]]) == OLPAREN); - assert(OP(p->strip[p->pend[i]]) == ORPAREN); - (void) dupl(p, p->pbegin[i]+1, p->pend[i]); - EMIT(O_BACK, i); - } else - SETERROR(REG_ESUBREG); - p->g->backrefs = 1; - break; - case '*': - REQUIRE(starordinary, REG_BADRPT); - /* FALLTHROUGH */ - default: - if (p->error != 0) - return(0); - ordinary(p, c &~ BACKSL); - break; } if (EAT('*')) { /* implemented as +? */ @@ -706,27 +954,35 @@ p_simp_re( ASTERN(O_PLUS, pos); INSERT(OQUEST_, pos); ASTERN(O_QUEST, pos); +#ifdef REGEX_GNU_EXTENSIONS + } else if (p->gnuext && EATTWO('\\', '?')) { + INSERT(OQUEST_, pos); + ASTERN(O_QUEST, pos); + } else if (p->gnuext && EATTWO('\\', '+')) { + INSERT(OPLUS_, pos); + ASTERN(O_PLUS, pos); +#endif } else if (EATTWO('\\', '{')) { count = p_count(p); if (EAT(',')) { - if (MORE() && isdigit((unsigned char)PEEK())) { + if (MORE() && isdigit((uch)PEEK())) { count2 = p_count(p); - REQUIRE(count <= count2, REG_BADBR); + (void)REQUIRE(count <= count2, REG_BADBR); } else /* single number with comma */ count2 = INFINITY; } else /* just a single number */ count2 = count; - repeat(p, pos, count, count2, 0); + repeat(p, pos, count, count2); if (!EATTWO('\\', '}')) { /* error heuristics */ while (MORE() && !SEETWO('\\', '}')) NEXT(); - REQUIRE(MORE(), REG_EBRACE); + (void)REQUIRE(MORE(), REG_EBRACE); SETERROR(REG_BADBR); } - } else if (c == (unsigned char)'$') /* $ (but not \$) ends it */ - return(1); + } else if (c == '$') /* $ (but not \$) ends it */ + return (true); - return(0); + return (false); } /* @@ -734,105 +990,87 @@ p_simp_re( == static int p_count(struct parse *p); */ static int /* the value */ -p_count( - struct parse *p) +p_count(struct parse *p) { int count = 0; int ndigits = 0; - _DIAGASSERT(p != NULL); - - while (MORE() && isdigit((unsigned char)PEEK()) && count <= DUPMAX) { + while (MORE() && isdigit((uch)PEEK()) && count <= DUPMAX) { count = count*10 + (GETNEXT() - '0'); ndigits++; } - REQUIRE(ndigits > 0 && count <= DUPMAX, REG_BADBR); + (void)REQUIRE(ndigits > 0 && count <= DUPMAX, REG_BADBR); return(count); } /* - p_bracket - parse a bracketed character list == static void p_bracket(struct parse *p); - * - * Note a significant property of this code: if the allocset() did SETERROR, - * no set operations are done. */ static void -p_bracket( - struct parse *p) +p_bracket(struct parse *p) { cset *cs; - int invert = 0; - _DIAGASSERT(p != NULL); - - cs = allocset(p); - if (cs == NULL) - return; + wint_t ch; /* Dept of Truly Sickening Special-Case Kludges */ - if (p->next + 5 < p->end && strncmp(p->next, "[:<:]]", - (size_t)6) == 0) { + if (p->next + 5 < p->end && strncmp(p->next, "[:<:]]", 6) == 0) { EMIT(OBOW, 0); NEXTn(6); return; } - if (p->next + 5 < p->end && strncmp(p->next, "[:>:]]", - (size_t)6) == 0) { + if (p->next + 5 < p->end && strncmp(p->next, "[:>:]]", 6) == 0) { EMIT(OEOW, 0); NEXTn(6); return; } + if ((cs = allocset(p)) == NULL) + return; + + if (p->g->cflags®_ICASE) + cs->icase = 1; if (EAT('^')) - invert++; /* make note to invert set at end */ + cs->invert = 1; if (EAT(']')) - CHadd(cs, ']'); + CHadd(p, cs, ']'); else if (EAT('-')) - CHadd(cs, '-'); + CHadd(p, cs, '-'); while (MORE() && PEEK() != ']' && !SEETWO('-', ']')) p_b_term(p, cs); if (EAT('-')) - CHadd(cs, '-'); - MUSTEAT(']', REG_EBRACK); + CHadd(p, cs, '-'); + (void)MUSTEAT(']', REG_EBRACK); if (p->error != 0) /* don't mess things up further */ return; - if (p->g->cflags®_ICASE) { - ssize_t i; - int ci; - - for (i = p->g->csetsize - 1; i >= 0; i--) - if (CHIN(cs, i) && isalpha(i)) { - ci = othercase((int)i); - if (ci != i) - CHadd(cs, ci); - } - if (cs->multis != NULL) - mccase(p, cs); - } - if (invert) { - ssize_t i; - - for (i = p->g->csetsize - 1; i >= 0; i--) - if (CHIN(cs, i)) - CHsub(cs, (int)i); - else - CHadd(cs, (int)i); - if (p->g->cflags®_NEWLINE) - CHsub(cs, '\n'); - if (cs->multis != NULL) - mcinvert(p, cs); - } - - assert(cs->multis == NULL); /* xxx */ + if (cs->invert && p->g->cflags®_NEWLINE) + cs->bmp['\n' >> 3] |= 1 << ('\n' & 7); - if (nch(p, cs) == 1) { /* optimize singleton sets */ - ordinary(p, firstch(p, cs)); + if ((ch = singleton(cs)) != OUT) { /* optimize singleton sets */ + ordinary(p, ch); freeset(p, cs); } else - EMIT(OANYOF, freezeset(p, cs)); + EMIT(OANYOF, (int)(cs - p->g->sets)); +} + +static int +p_range_cmp(wchar_t c1, wchar_t c2) +{ +#ifdef REGEX_LIBC_COLLATE + return __wcollate_range_cmp(c1, c2); +#else + /* Copied from libc/collate __wcollate_range_cmp */ + wchar_t s1[2], s2[2]; + + s1[0] = c1; + s1[1] = L'\0'; + s2[0] = c2; + s2[1] = L'\0'; + return (wcscoll(s1, s2)); +#endif } /* @@ -840,13 +1078,15 @@ p_bracket( == static void p_b_term(struct parse *p, cset *cs); */ static void -p_b_term( - struct parse *p, - cset *cs) +p_b_term(struct parse *p, cset *cs) { char c; - char start, finish; - int i; + wint_t start, finish; + wint_t i; +#ifdef REGEX_LIBC_COLLATE + struct xlocale_collate *table = + (struct xlocale_collate*)__get_locale()->components[XLC_COLLATE]; +#endif _DIAGASSERT(p != NULL); _DIAGASSERT(cs != NULL); @@ -856,11 +1096,9 @@ p_b_term( case '[': c = (MORE2()) ? PEEK2() : '\0'; break; - case '-': SETERROR(REG_ERANGE); return; /* NOTE RETURN */ - default: c = '\0'; break; @@ -869,24 +1107,23 @@ p_b_term( switch (c) { case ':': /* character class */ NEXT2(); - REQUIRE(MORE(), REG_EBRACK); + (void)REQUIRE(MORE(), REG_EBRACK); c = PEEK(); - REQUIRE(c != '-' && c != ']', REG_ECTYPE); + (void)REQUIRE(c != '-' && c != ']', REG_ECTYPE); p_b_cclass(p, cs); - REQUIRE(MORE(), REG_EBRACK); - REQUIRE(EATTWO(':', ']'), REG_ECTYPE); + (void)REQUIRE(MORE(), REG_EBRACK); + (void)REQUIRE(EATTWO(':', ']'), REG_ECTYPE); break; case '=': /* equivalence class */ NEXT2(); - REQUIRE(MORE(), REG_EBRACK); + (void)REQUIRE(MORE(), REG_EBRACK); c = PEEK(); - REQUIRE(c != '-' && c != ']', REG_ECOLLATE); + (void)REQUIRE(c != '-' && c != ']', REG_ECOLLATE); p_b_eclass(p, cs); - REQUIRE(MORE(), REG_EBRACK); - REQUIRE(EATTWO('=', ']'), REG_ECOLLATE); + (void)REQUIRE(MORE(), REG_EBRACK); + (void)REQUIRE(EATTWO('=', ']'), REG_ECOLLATE); break; default: /* symbol, ordinary character, or range */ -/* xxx revision needed for multichar stuff */ start = p_b_symbol(p); if (SEE('-') && MORE2() && PEEK2() != ']') { /* range */ @@ -897,51 +1134,102 @@ p_b_term( finish = p_b_symbol(p); } else finish = start; -/* xxx what about signed chars here... */ - REQUIRE(start <= finish, REG_ERANGE); - for (i = start; i <= finish; i++) - CHadd(cs, i); + if (start == finish) + CHadd(p, cs, start); + else { +#ifdef REGEX_LIBC_COLLATE + if (table->__collate_load_error || MB_CUR_MAX > 1) { +#else + if (MB_CUR_MAX > 1) { +#endif + (void)REQUIRE(start <= finish, REG_ERANGE); + CHaddrange(p, cs, start, finish); + } else { + (void)REQUIRE(p_range_cmp(start, finish) <= 0, REG_ERANGE); + for (i = 0; i <= UCHAR_MAX; i++) { + if (p_range_cmp(start, i) <= 0 && + p_range_cmp(i, finish) <= 0 ) + CHadd(p, cs, i); + } + } + } break; } } +#ifdef REGEX_GNU_EXTENSIONS +/* + - p_b_pseudoclass - parse a pseudo-class (\w, \W, \s, \S) + == static int p_b_pseudoclass(struct parse *p, char c) + */ +static int +p_b_pseudoclass(struct parse *p, char c) { + cset *cs; + + if ((cs = allocset(p)) == NULL) + return(0); + + if (p->g->cflags®_ICASE) + cs->icase = 1; + + switch (c) { + case 'W': + cs->invert = 1; + /* FALLTHROUGH */ + case 'w': + p_b_cclass_named(p, cs, "alnum"); + break; + case 'S': + cs->invert = 1; + /* FALLTHROUGH */ + case 's': + p_b_cclass_named(p, cs, "space"); + break; + default: + return(0); + } + + EMIT(OANYOF, (int)(cs - p->g->sets)); + return(1); +} +#endif + /* - p_b_cclass - parse a character-class name and deal with it == static void p_b_cclass(struct parse *p, cset *cs); */ static void -p_b_cclass( - struct parse *p, - cset *cs) +p_b_cclass(struct parse *p, cset *cs) { - const char *sp; - const struct cclass *cp; + const char *sp = p->next; size_t len; - const char *u; - char c; - - _DIAGASSERT(p != NULL); - _DIAGASSERT(cs != NULL); - - sp = p->next; + char clname[16]; - while (MORE() && isalpha((unsigned char)PEEK())) + while (MORE() && isalpha((uch)PEEK())) NEXT(); len = p->next - sp; - for (cp = cclasses; cp->name != NULL; cp++) - if (strncmp(cp->name, sp, len) == 0 && cp->name[len] == '\0') - break; - if (cp->name == NULL) { - /* oops, didn't find it */ + if (len >= sizeof(clname) - 1) { SETERROR(REG_ECTYPE); return; } + memcpy(clname, sp, len); + clname[len] = '\0'; + + p_b_cclass_named(p, cs, clname); +} +/* + - p_b_cclass_named - deal with a named character class + == static void p_b_cclass_named(struct parse *p, cset *cs, const char []); + */ +static void +p_b_cclass_named(struct parse *p, cset *cs, const char clname[]) { + wctype_t wct; - u = cp->chars; - while ((c = *u++) != '\0') - CHadd(cs, c); - for (u = cp->multis; *u != '\0'; u += strlen(u) + 1) - MCadd(p, cs, u); + if ((wct = wctype(clname)) == 0) { + SETERROR(REG_ECTYPE); + return; + } + CHaddtype(p, cs, wct); } /* @@ -951,58 +1239,54 @@ p_b_cclass( * This implementation is incomplete. xxx */ static void -p_b_eclass( - struct parse *p, - cset *cs) +p_b_eclass(struct parse *p, cset *cs) { - char c; + wint_t c; _DIAGASSERT(p != NULL); _DIAGASSERT(cs != NULL); c = p_b_coll_elem(p, '='); - CHadd(cs, c); + CHadd(p, cs, c); } /* - p_b_symbol - parse a character or [..]ed multicharacter collating symbol - == static char p_b_symbol(struct parse *p); + == static wint_t p_b_symbol(struct parse *p); */ -static char /* value of symbol */ -p_b_symbol( - struct parse *p) +static wint_t /* value of symbol */ +p_b_symbol(struct parse *p) { - char value; + wint_t value; _DIAGASSERT(p != NULL); - REQUIRE(MORE(), REG_EBRACK); + (void)REQUIRE(MORE(), REG_EBRACK); if (!EATTWO('[', '.')) - return(GETNEXT()); + return(WGETNEXT()); /* collating symbol */ value = p_b_coll_elem(p, '.'); - REQUIRE(EATTWO('.', ']'), REG_ECOLLATE); + (void)REQUIRE(EATTWO('.', ']'), REG_ECOLLATE); return(value); } /* - p_b_coll_elem - parse a collating-element name and look it up - == static char p_b_coll_elem(struct parse *p, int endc); + == static wint_t p_b_coll_elem(struct parse *p, wint_t endc); */ -static char /* value of collating element */ -p_b_coll_elem( - struct parse *p, - int endc) /* name ended by endc,']' */ +static wint_t /* value of collating element */ +p_b_coll_elem(struct parse *p, + wint_t endc) /* name ended by endc,']' */ { - const char *sp; - const struct cname *cp; - size_t len; + const char *sp = p->next; + struct cname *cp; + mbstate_t mbs; + wchar_t wc; + size_t clen, len; _DIAGASSERT(p != NULL); - sp = p->next; - while (MORE() && !SEETWO(endc, ']')) NEXT(); if (!MORE()) { @@ -1013,85 +1297,136 @@ p_b_coll_elem( for (cp = cnames; cp->name != NULL; cp++) if (strncmp(cp->name, sp, len) == 0 && strlen(cp->name) == len) return(cp->code); /* known name */ - if (len == 1) - return(*sp); /* single character */ - SETERROR(REG_ECOLLATE); /* neither */ + memset(&mbs, 0, sizeof(mbs)); + if ((clen = mbrtowc(&wc, sp, len, &mbs)) == len) + return (wc); /* single character */ + else if (clen == (size_t)-1 || clen == (size_t)-2) + SETERROR(REG_ILLSEQ); + else + SETERROR(REG_ECOLLATE); /* neither */ return(0); } /* + - may_escape - determine whether 'ch' is escape-able in the current context + == static int may_escape(struct parse *p, const wint_t ch) + */ +static bool +may_escape(struct parse *p, const wint_t ch) +{ + + if ((p->pflags & PFLAG_LEGACY_ESC) != 0) + return (true); + if (isalpha(ch) || ch == '\'' || ch == '`') + return (false); + return (true); +#ifdef NOTYET + /* + * Build a whitelist of characters that may be escaped to produce an + * ordinary in the current context. This assumes that these have not + * been otherwise interpreted as a special character. Escaping an + * ordinary character yields undefined results according to + * IEEE 1003.1-2008. Some extensions (notably, some GNU extensions) take + * advantage of this and use escaped ordinary characters to provide + * special meaning, e.g. \b, \B, \w, \W, \s, \S. + */ + switch(ch) { + case '|': + case '+': + case '?': + /* The above characters may not be escaped in BREs */ + if (!(p->g->cflags®_EXTENDED)) + return (false); + /* Fallthrough */ + case '(': + case ')': + case '{': + case '}': + case '.': + case '[': + case ']': + case '\\': + case '*': + case '^': + case '$': + return (true); + default: + return (false); + } +#endif +} + +/* - othercase - return the case counterpart of an alphabetic - == static int othercase(int ch); + == static wint_t othercase(wint_t ch); */ -static int /* if no counterpart, return ch */ -othercase( - int ch) +static wint_t /* if no counterpart, return ch */ +othercase(wint_t ch) { - assert(isalpha(ch)); - if (isupper(ch)) - return(tolower(ch)); - else if (islower(ch)) - return(toupper(ch)); + assert(iswalpha(ch)); + if (iswupper(ch)) + return(towlower(ch)); + else if (iswlower(ch)) + return(towupper(ch)); else /* peculiar, but could happen */ return(ch); } /* - bothcases - emit a dualcase version of a two-case character - == static void bothcases(struct parse *p, int ch); + == static void bothcases(struct parse *p, wint_t ch); * * Boy, is this implementation ever a kludge... */ static void -bothcases( - struct parse *p, - int ch) +bothcases(struct parse *p, wint_t ch) { - const char *oldnext; - const char *oldend; - char bracket[3]; + const char *oldnext = p->next; + const char *oldend = p->end; + char bracket[3 + MB_LEN_MAX]; + size_t n; + mbstate_t mbs; _DIAGASSERT(p != NULL); - oldnext = p->next; - oldend = p->end; - assert(othercase(ch) != ch); /* p_bracket() would recurse */ p->next = bracket; - p->end = bracket+2; - bracket[0] = ch; - bracket[1] = ']'; - bracket[2] = '\0'; + memset(&mbs, 0, sizeof(mbs)); + n = wcrtomb(bracket, ch, &mbs); + assert(n != (size_t)-1); + bracket[n] = ']'; + bracket[n + 1] = '\0'; + p->end = bracket+n+1; p_bracket(p); - assert(p->next == bracket+2); + assert(p->next == p->end); p->next = oldnext; p->end = oldend; } /* - ordinary - emit an ordinary character - == static void ordinary(struct parse *p, int ch); + == static void ordinary(struct parse *p, wint_t ch); */ static void -ordinary( - struct parse *p, - int ch) +ordinary(struct parse *p, wint_t ch) { - cat_t *cap; - unsigned char uc = (unsigned char)ch; + cset *cs; _DIAGASSERT(p != NULL); - cap = p->g->categories; - if ((p->g->cflags & REG_ICASE) && isalpha(uc) && othercase(uc) != uc) - bothcases(p, uc); + if ((p->g->cflags®_ICASE) && iswalpha(ch) && othercase(ch) != ch) + bothcases(p, ch); + else if ((ch & OPDMASK) == ch) + EMIT(OCHAR, ch); else { - EMIT(OCHAR, (sopno)uc); - if (cap[uc] == 0) { - _DIAGASSERT(__type_fit(unsigned char, - p->g->ncategories + 1)); - cap[uc] = (unsigned char)p->g->ncategories++; - } + /* + * Kludge: character is too big to fit into an OCHAR operand. + * Emit a singleton set. + */ + if ((cs = allocset(p)) == NULL) + return; + CHadd(p, cs, ch); + EMIT(OANYOF, (int)(cs - p->g->sets)); } } @@ -1102,18 +1437,14 @@ ordinary( * Boy, is this implementation ever a kludge... */ static void -nonnewline( - struct parse *p) +nonnewline(struct parse *p) { - const char *oldnext; - const char *oldend; + const char *oldnext = p->next; + const char *oldend = p->end; char bracket[4]; _DIAGASSERT(p != NULL); - oldnext = p->next; - oldend = p->end; - p->next = bracket; p->end = bracket+3; bracket[0] = '^'; @@ -1128,18 +1459,15 @@ nonnewline( /* - repeat - generate code for a bounded repetition, recursively if needed - == static void repeat(struct parse *p, sopno start, int from, int to, - == size_t reclimit); + == static void repeat(struct parse *p, sopno start, int from, int to); */ static void -repeat( - struct parse *p, - sopno start, /* operand from here to end of strip */ - int from, /* repeated from this number */ - int to, /* to this number of times (maybe INFINITY) */ - size_t reclimit) +repeat(struct parse *p, + sopno start, /* operand from here to end of strip */ + int from, /* repeated from this number */ + int to) /* to this number of times (maybe INFINITY) */ { - sopno finish; + sopno finish = HERE(); # define N 2 # define INF 3 # define REP(f, t) ((f)*8 + (t)) @@ -1148,13 +1476,9 @@ repeat( _DIAGASSERT(p != NULL); - if (reclimit++ > RECLIMIT) - p->error = REG_ESPACE; - if (p->error) + if (p->error != 0) /* head off possible runaway recursion */ return; - finish = HERE(); - assert(from <= to); switch (REP(MAP(from), MAP(to))) { @@ -1166,7 +1490,7 @@ repeat( case REP(0, INF): /* as x{1,}? */ /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */ INSERT(OCH_, start); /* offset is wrong... */ - repeat(p, start+1, 1, to, reclimit); + repeat(p, start+1, 1, to); ASTERN(OOR1, start); AHEAD(start); /* ... fix it */ EMIT(OOR2, 0); @@ -1186,7 +1510,7 @@ repeat( ASTERN(O_CH, THERETHERE()); copy = dupl(p, start+1, finish+1); assert(copy == finish+4); - repeat(p, copy, 1, to-1, reclimit); + repeat(p, copy, 1, to-1); break; case REP(1, INF): /* as x+ */ INSERT(OPLUS_, start); @@ -1194,11 +1518,11 @@ repeat( break; case REP(N, N): /* as xx{m-1,n-1} */ copy = dupl(p, start, finish); - repeat(p, copy, from-1, to-1, reclimit); + repeat(p, copy, from-1, to-1); break; case REP(N, INF): /* as xx{n-1,INF} */ copy = dupl(p, start, finish); - repeat(p, copy, from-1, to, reclimit); + repeat(p, copy, from-1, to); break; default: /* "can't happen" */ SETERROR(REG_ASSERT); /* just in case */ @@ -1207,13 +1531,35 @@ repeat( } /* + - wgetnext - helper function for WGETNEXT() macro. Gets the next wide + - character from the parse struct, signals a REG_ILLSEQ error if the + - character can't be converted. Returns the number of bytes consumed. + */ +static wint_t +wgetnext(struct parse *p) +{ + mbstate_t mbs; + wchar_t wc; + size_t n; + + memset(&mbs, 0, sizeof(mbs)); + n = mbrtowc(&wc, p->next, p->end - p->next, &mbs); + if (n == (size_t)-1 || n == (size_t)-2) { + SETERROR(REG_ILLSEQ); + return (0); + } + if (n == 0) + n = 1; + p->next += n; + return (wc); +} + +/* - seterr - set an error condition == static int seterr(struct parse *p, int e); */ static int /* useless but makes type checking happy */ -seterr( - struct parse *p, - int e) +seterr(struct parse *p, int e) { _DIAGASSERT(p != NULL); @@ -1230,55 +1576,22 @@ seterr( == static cset *allocset(struct parse *p); */ static cset * -allocset( - struct parse *p) +allocset(struct parse *p) { - size_t no; - size_t nc; - size_t nbytes; - cset *cs; - size_t css; - size_t i; - void *old_ptr; + cset *cs, *ncs; _DIAGASSERT(p != NULL); - no = p->g->ncsets++; - css = (size_t)p->g->csetsize; - if (no >= p->ncsalloc) { /* need another column of space */ - p->ncsalloc += CHAR_BIT; - nc = p->ncsalloc; - assert(nc % CHAR_BIT == 0); - nbytes = nc / CHAR_BIT * css; - if (MEMSIZE(p) > MEMLIMIT) - goto oomem; - if (reallocarr(&p->g->sets, nc, sizeof(cset))) - goto oomem; - old_ptr = p->g->setbits; - if (reallocarr(&p->g->setbits, nc / CHAR_BIT, css)) { - free(old_ptr); - goto oomem; - } - if (old_ptr != p->g->setbits) { - for (i = 0; i < no; i++) - p->g->sets[i].ptr = p->g->setbits + css*(i/CHAR_BIT); - } - (void) memset((char *)p->g->setbits + (nbytes - css), 0, css); + ncs = reallocarray(p->g->sets, p->g->ncsets + 1, sizeof(*ncs)); + if (ncs == NULL) { + SETERROR(REG_ESPACE); + return (NULL); } - - cs = &p->g->sets[no]; - cs->ptr = p->g->setbits + css*((no)/CHAR_BIT); - cs->mask = 1 << (unsigned int)((no) % CHAR_BIT); - cs->hash = 0; - cs->smultis = 0; - cs->multis = NULL; + p->g->sets = ncs; + cs = &p->g->sets[p->g->ncsets++]; + memset(cs, 0, sizeof(*cs)); return(cs); - -oomem: - SETERROR(REG_ESPACE); - /* caller's responsibility not to do set ops */ - return NULL; } /* @@ -1286,353 +1599,128 @@ oomem: == static void freeset(struct parse *p, cset *cs); */ static void -freeset( - struct parse *p, - cset *cs) +freeset(struct parse *p, cset *cs) { - size_t i; cset *top; - size_t css; _DIAGASSERT(p != NULL); _DIAGASSERT(cs != NULL); top = &p->g->sets[p->g->ncsets]; - css = (size_t)p->g->csetsize; - for (i = 0; i < css; i++) - CHsub(cs, (int)i); + free(cs->wides); + free(cs->ranges); + free(cs->types); + memset(cs, 0, sizeof(*cs)); if (cs == top-1) /* recover only the easy case */ p->g->ncsets--; } /* - - freezeset - final processing on a set of characters - == static int freezeset(struct parse *p, cset *cs); - * - * The main task here is merging identical sets. This is usually a waste - * of time (although the hash code minimizes the overhead), but can win - * big if REG_ICASE is being used. REG_ICASE, by the way, is why the hash - * is done using addition rather than xor -- all ASCII [aA] sets xor to - * the same value! - */ -static sopno /* set number */ -freezeset( - struct parse *p, - cset *cs) -{ - uch h; - size_t i; - cset *top; - cset *cs2; - size_t css; - - _DIAGASSERT(p != NULL); - _DIAGASSERT(cs != NULL); - - h = cs->hash; - top = &p->g->sets[p->g->ncsets]; - css = (size_t)p->g->csetsize; - - /* look for an earlier one which is the same */ - for (cs2 = &p->g->sets[0]; cs2 < top; cs2++) - if (cs2->hash == h && cs2 != cs) { - /* maybe */ - for (i = 0; i < css; i++) - if (!!CHIN(cs2, i) != !!CHIN(cs, i)) - break; /* no */ - if (i == css) - break; /* yes */ - } - - if (cs2 < top) { /* found one */ - freeset(p, cs); - cs = cs2; - } - - return (sopno)(cs - p->g->sets); -} - -/* - - firstch - return first character in a set (which must have at least one) - == static int firstch(struct parse *p, cset *cs); - */ -static int /* character; there is no "none" value */ -firstch( - struct parse *p, - cset *cs) -{ - size_t i; - size_t css; - - _DIAGASSERT(p != NULL); - _DIAGASSERT(cs != NULL); - - css = (size_t)p->g->csetsize; - - for (i = 0; i < css; i++) - if (CHIN(cs, i)) - return((char)i); - assert(never); - return(0); /* arbitrary */ -} - -/* - - nch - number of characters in a set - == static int nch(struct parse *p, cset *cs); + - singleton - Determine whether a set contains only one character, + - returning it if so, otherwise returning OUT. */ -static int -nch( - struct parse *p, - cset *cs) +static wint_t +singleton(cset *cs) { - size_t i; - size_t css; - int n = 0; - - _DIAGASSERT(p != NULL); - _DIAGASSERT(cs != NULL); - - css = (size_t)p->g->csetsize; + wint_t i, s, n; - for (i = 0; i < css; i++) - if (CHIN(cs, i)) + for (i = n = 0; i < NC; i++) + if (CHIN(cs, i)) { n++; - return(n); + s = i; + } + if (n == 1) + return (s); + if (cs->nwides == 1 && cs->nranges == 0 && cs->ntypes == 0 && + cs->icase == 0) + return (cs->wides[0]); + /* Don't bother handling the other cases. */ + return (OUT); } /* - - mcadd - add a collating element to a cset - == static void mcadd(struct parse *p, cset *cs, \ - == char *cp); + - CHadd - add character to character set. */ static void -mcadd( - struct parse *p, - cset *cs, - const char *cp) +CHadd(struct parse *p, cset *cs, wint_t ch) { - size_t oldend; + wint_t nch, *newwides; _DIAGASSERT(p != NULL); _DIAGASSERT(cs != NULL); - _DIAGASSERT(cp != NULL); - - oldend = cs->smultis; - cs->smultis += strlen(cp) + 1; - if (cs->multis == NULL) - cs->multis = malloc(cs->smultis); - else - cs->multis = realloc(cs->multis, cs->smultis); - if (cs->multis == NULL) { - SETERROR(REG_ESPACE); - return; + assert(ch >= 0); + if (ch < NC) + cs->bmp[ch >> 3] |= 1 << (ch & 7); + else { + newwides = reallocarray(cs->wides, cs->nwides + 1, + sizeof(*cs->wides)); + if (newwides == NULL) { + SETERROR(REG_ESPACE); + return; + } + cs->wides = newwides; + cs->wides[cs->nwides++] = ch; } - - (void) strcpy(cs->multis + oldend - 1, cp); - cs->multis[cs->smultis - 1] = '\0'; -} - -#if 0 -/* - - mcsub - subtract a collating element from a cset - == static void mcsub(cset *cs, char *cp); - */ -static void -mcsub( - cset *cs, - char *cp) -{ - char *fp; - size_t len; - - _DIAGASSERT(cs != NULL); - _DIAGASSERT(cp != NULL); - - fp = mcfind(cs, cp); - len = strlen(fp); - - assert(fp != NULL); - (void) memmove(fp, fp + len + 1, - cs->smultis - (fp + len + 1 - cs->multis)); - cs->smultis -= len; - - if (cs->smultis == 0) { - free(cs->multis); - cs->multis = NULL; - return; + if (cs->icase) { + if ((nch = towlower(ch)) < NC) + cs->bmp[nch >> 3] |= 1 << (nch & 7); + if ((nch = towupper(ch)) < NC) + cs->bmp[nch >> 3] |= 1 << (nch & 7); } - - cs->multis = realloc(cs->multis, cs->smultis); - assert(cs->multis != NULL); -} - -/* - - mcin - is a collating element in a cset? - == static int mcin(cset *cs, char *cp); - */ -static int -mcin( - cset *cs, - char *cp) -{ - - _DIAGASSERT(cs != NULL); - _DIAGASSERT(cp != NULL); - - return(mcfind(cs, cp) != NULL); -} - -/* - - mcfind - find a collating element in a cset - == static char *mcfind(cset *cs, char *cp); - */ -static char * -mcfind( - cset *cs, - char *cp) -{ - char *p; - - _DIAGASSERT(cs != NULL); - _DIAGASSERT(cp != NULL); - - if (cs->multis == NULL) - return(NULL); - for (p = cs->multis; *p != '\0'; p += strlen(p) + 1) - if (strcmp(cp, p) == 0) - return(p); - return(NULL); } -#endif /* - - mcinvert - invert the list of collating elements in a cset - == static void mcinvert(struct parse *p, cset *cs); - * - * This would have to know the set of possibilities. Implementation - * is deferred. + - CHaddrange - add all characters in the range [min,max] to a character set. */ -/* ARGSUSED */ static void -mcinvert( - struct parse *p, - cset *cs) +CHaddrange(struct parse *p, cset *cs, wint_t min, wint_t max) { + crange *newranges; _DIAGASSERT(p != NULL); _DIAGASSERT(cs != NULL); - assert(cs->multis == NULL); /* xxx */ + for (; min < NC && min <= max; min++) + CHadd(p, cs, min); + if (min >= max) + return; + newranges = reallocarray(cs->ranges, cs->nranges + 1, + sizeof(*cs->ranges)); + if (newranges == NULL) { + SETERROR(REG_ESPACE); + return; + } + cs->ranges = newranges; + cs->ranges[cs->nranges].min = min; + cs->ranges[cs->nranges].max = max; + cs->nranges++; } /* - - mccase - add case counterparts of the list of collating elements in a cset - == static void mccase(struct parse *p, cset *cs); - * - * This would have to know the set of possibilities. Implementation - * is deferred. + - CHaddtype - add all characters of a certain type to a character set. */ -/* ARGSUSED */ static void -mccase( - struct parse *p, - cset *cs) +CHaddtype(struct parse *p, cset *cs, wctype_t wct) { + wint_t i; + wctype_t *newtypes; _DIAGASSERT(p != NULL); _DIAGASSERT(cs != NULL); - assert(cs->multis == NULL); /* xxx */ -} - -/* - - isinsets - is this character in any sets? - == static int isinsets(struct re_guts *g, int c); - */ -static int /* predicate */ -isinsets( - struct re_guts *g, - int c) -{ - uch *col; - size_t i; - size_t ncols; - unsigned uc = (unsigned char)c; - - _DIAGASSERT(g != NULL); - - if (g->setbits == NULL) - return 0; - - ncols = (g->ncsets+(CHAR_BIT-1)) / CHAR_BIT; - - for (i = 0, col = g->setbits; i < ncols; i++, col += g->csetsize) - if (col[uc] != 0) - return(1); - return(0); -} - -/* - - samesets - are these two characters in exactly the same sets? - == static int samesets(struct re_guts *g, int c1, int c2); - */ -static int /* predicate */ -samesets( - struct re_guts *g, - int c1, - int c2) -{ - uch *col; - size_t i; - size_t ncols; - unsigned uc1 = (unsigned char)c1; - unsigned uc2 = (unsigned char)c2; - - _DIAGASSERT(g != NULL); - - ncols = (g->ncsets+(CHAR_BIT-1)) / CHAR_BIT; - - for (i = 0, col = g->setbits; i < ncols; i++, col += g->csetsize) - if (col[uc1] != col[uc2]) - return(0); - return(1); -} - -/* - - categorize - sort out character categories - == static void categorize(struct parse *p, struct re_guts *g); - */ -static void -categorize( - struct parse *p, - struct re_guts *g) -{ - cat_t *cats; - int c; - int c2; - cat_t cat; - - _DIAGASSERT(p != NULL); - _DIAGASSERT(g != NULL); - - cats = g->categories; - - /* avoid making error situations worse */ - if (p->error != 0) + for (i = 0; i < NC; i++) + if (iswctype(i, wct)) + CHadd(p, cs, i); + newtypes = reallocarray(cs->types, cs->ntypes + 1, + sizeof(*cs->types)); + if (newtypes == NULL) { + SETERROR(REG_ESPACE); return; - - for (c = CHAR_MIN; c <= CHAR_MAX; c++) - if (cats[c] == 0 && isinsets(g, c)) { - _DIAGASSERT(__type_fit(unsigned char, - g->ncategories + 1)); - cat = g->ncategories++; - cats[c] = cat; - for (c2 = c+1; c2 <= CHAR_MAX; c2++) - if (cats[c2] == 0 && samesets(g, c, c2)) - cats[c2] = cat; - } + } + cs->types = newtypes; + cs->types[cs->ntypes++] = wct; } /* @@ -1640,25 +1728,22 @@ categorize( == static sopno dupl(struct parse *p, sopno start, sopno finish); */ static sopno /* start of duplicate */ -dupl( - struct parse *p, - sopno start, /* from here */ - sopno finish) /* to this less one */ +dupl(struct parse *p, + sopno start, /* from here */ + sopno finish) /* to this less one */ { - sopno ret; + sopno ret = HERE(); sopno len = finish - start; _DIAGASSERT(p != NULL); - ret = HERE(); - assert(finish >= start); if (len == 0) return(ret); - if (!enlarge(p, p->ssize + len))/* this many unexpected additions */ - return ret; - (void)memcpy(p->strip + p->slen, p->strip + start, - (size_t)len * sizeof(sop)); + if (!enlarge(p, p->ssize + len)) /* this many unexpected additions */ + return(ret); + (void) memcpy((char *)(p->strip + p->slen), + (char *)(p->strip + start), (size_t)len*sizeof(sop)); p->slen += len; return(ret); } @@ -1672,17 +1757,14 @@ dupl( * some changes to the data structures. Maybe later. */ static void -doemit( - struct parse *p, - sop op, - sopno opnd) +doemit(struct parse *p, sop op, size_t opnd) { - _DIAGASSERT(p != NULL); - /* avoid making error situations worse */ if (p->error != 0) return; + _DIAGASSERT(p != NULL); + /* deal with oversize operands ("can't happen", more or less) */ assert(opnd < 1<<OPSHIFT); @@ -1692,7 +1774,7 @@ doemit( return; /* finally, it's all reduced to the easy case */ - p->strip[p->slen++] = (sop)SOP(op, opnd); + p->strip[p->slen++] = SOP(op, opnd); } /* @@ -1700,11 +1782,7 @@ doemit( == static void doinsert(struct parse *p, sop op, size_t opnd, sopno pos); */ static void -doinsert( - struct parse *p, - sop op, - sopno opnd, - sopno pos) +doinsert(struct parse *p, sop op, size_t opnd, sopno pos) { sopno sn; sop s; @@ -1732,7 +1810,8 @@ doinsert( } } - memmove(&p->strip[pos+1], &p->strip[pos], (HERE()-pos-1)*sizeof(sop)); + memmove((char *)&p->strip[pos+1], (char *)&p->strip[pos], + (HERE()-pos-1)*sizeof(sop)); p->strip[pos] = s; } @@ -1741,10 +1820,7 @@ doinsert( == static void dofwd(struct parse *p, sopno pos, sop value); */ static void -dofwd( - struct parse *p, - sopno pos, - sopno value) +dofwd(struct parse *p, sopno pos, sop value) { _DIAGASSERT(p != NULL); @@ -1754,25 +1830,29 @@ dofwd( return; assert(value < 1<<OPSHIFT); - p->strip[pos] = (sop)(OP(p->strip[pos]) | value); + p->strip[pos] = OP(p->strip[pos]) | value; } /* - enlarge - enlarge the strip - == static void enlarge(struct parse *p, sopno size); + == static int enlarge(struct parse *p, sopno size); */ static int enlarge(struct parse *p, sopno size) { + sop *sp; + _DIAGASSERT(p != NULL); if (p->ssize >= size) return 1; - if (MEMSIZE(p) > MEMLIMIT || reallocarr(&p->strip, size, sizeof(sop))) { + sp = reallocarray(p->strip, size, sizeof(sop)); + if (sp == NULL) { SETERROR(REG_ESPACE); return 0; } + p->strip = sp; p->ssize = size; return 1; } @@ -1782,18 +1862,18 @@ enlarge(struct parse *p, sopno size) == static void stripsnug(struct parse *p, struct re_guts *g); */ static void -stripsnug( - struct parse *p, - struct re_guts *g) +stripsnug(struct parse *p, struct re_guts *g) { _DIAGASSERT(p != NULL); _DIAGASSERT(g != NULL); g->nstates = p->slen; - g->strip = p->strip; - reallocarr(&g->strip, p->slen, sizeof(sop)); - /* Ignore error as tries to free memory only. */ + g->strip = reallocarray((char *)p->strip, p->slen, sizeof(sop)); + if (g->strip == NULL) { + SETERROR(REG_ESPACE); + g->strip = p->strip; + } } /* @@ -1807,9 +1887,7 @@ stripsnug( * Note that must and mlen got initialized during setup. */ static void -findmust( - struct parse *p, - struct re_guts *g) +findmust(struct parse *p, struct re_guts *g) { sop *scan; sop *start = NULL; @@ -1817,7 +1895,10 @@ findmust( sopno newlen; sop s; char *cp; - sopno i; + int offset; + char buf[MB_LEN_MAX]; + size_t clen; + mbstate_t mbs; _DIAGASSERT(p != NULL); _DIAGASSERT(g != NULL); @@ -1826,16 +1907,34 @@ findmust( if (p->error != 0) return; +#ifdef notyet + /* + * It's not generally safe to do a ``char'' substring search on + * multibyte character strings, but it's safe for at least + * UTF-8 (see RFC 3629). + */ + if (MB_CUR_MAX > 1 && + strcmp(_CurrentRuneLocale->__encoding, "UTF-8") != 0) + return; +#endif + /* find the longest OCHAR sequence in strip */ newlen = 0; + offset = 0; + g->moffset = 0; scan = g->strip + 1; do { s = *scan++; switch (OP(s)) { case OCHAR: /* sequence member */ - if (newlen == 0) /* new sequence */ + if (newlen == 0) { /* new sequence */ + memset(&mbs, 0, sizeof(mbs)); newstart = scan - 1; - newlen++; + } + clen = wcrtomb(buf, OPND(s), &mbs); + if (clen == (size_t)-1) + goto toohard; + newlen += clen; break; case OPLUS_: /* things that don't break one */ case OLPAREN: @@ -1843,60 +1942,339 @@ findmust( break; case OQUEST_: /* things that must be skipped */ case OCH_: + offset = altoffset(scan, offset); scan--; do { scan += OPND(s); s = *scan; /* assert() interferes w debug printouts */ - if (OP(s) != O_QUEST && OP(s) != O_CH && - OP(s) != OOR2) { + if (OP(s) != (sop)O_QUEST && + OP(s) != (sop)O_CH && OP(s) != (sop)OOR2) { g->iflags |= BAD; return; } - } while (OP(s) != O_QUEST && OP(s) != O_CH); + } while (OP(s) != (sop)O_QUEST && OP(s) != (sop)O_CH); /* FALLTHROUGH */ - default: /* things that break a sequence */ - if (newlen > g->mlen) { /* ends one */ + case OBOW: /* things that break a sequence */ + case OEOW: + case OBOL: + case OEOL: + case OBOS: + case OEOS: + case OWBND: + case ONWBND: + case O_QUEST: + case O_CH: + case OEND: + if (newlen > (sopno)g->mlen) { /* ends one */ + start = newstart; + g->mlen = newlen; + if (offset > -1) { + g->moffset += offset; + offset = newlen; + } else + g->moffset = offset; + } else { + if (offset > -1) + offset += newlen; + } + newlen = 0; + break; + case OANY: + if (newlen > (sopno)g->mlen) { /* ends one */ + start = newstart; + g->mlen = newlen; + if (offset > -1) { + g->moffset += offset; + offset = newlen; + } else + g->moffset = offset; + } else { + if (offset > -1) + offset += newlen; + } + if (offset > -1) + offset++; + newlen = 0; + break; + case OANYOF: /* may or may not invalidate offset */ + /* First, everything as OANY */ + if (newlen > (sopno)g->mlen) { /* ends one */ start = newstart; g->mlen = newlen; + if (offset > -1) { + g->moffset += offset; + offset = newlen; + } else + g->moffset = offset; + } else { + if (offset > -1) + offset += newlen; } + if (offset > -1) + offset++; + newlen = 0; + break; + toohard: + default: + /* Anything here makes it impossible or too hard + * to calculate the offset -- so we give up; + * save the last known good offset, in case the + * must sequence doesn't occur later. + */ + if (newlen > (sopno)g->mlen) { /* ends one */ + start = newstart; + g->mlen = newlen; + if (offset > -1) + g->moffset += offset; + else + g->moffset = offset; + } + offset = -1; newlen = 0; break; } } while (OP(s) != OEND); - if (start == NULL) - g->mlen = 0; - - if (g->mlen == 0) /* there isn't one */ + if (g->mlen == 0) { /* there isn't one */ + g->moffset = -1; return; + } /* turn it into a character string */ g->must = malloc((size_t)g->mlen + 1); if (g->must == NULL) { /* argh; just forget it */ g->mlen = 0; + g->moffset = -1; return; } cp = g->must; scan = start; - for (i = g->mlen; i > 0; i--) { + memset(&mbs, 0, sizeof(mbs)); + while (cp < g->must + g->mlen) { while (OP(s = *scan++) != OCHAR) continue; - assert(cp < g->must + g->mlen); - *cp++ = (char)OPND(s); + clen = wcrtomb(cp, OPND(s), &mbs); + assert(clen != (size_t)-1); + cp += clen; } assert(cp == g->must + g->mlen); *cp++ = '\0'; /* just on general principles */ } /* + - altoffset - choose biggest offset among multiple choices + == static int altoffset(sop *scan, int offset); + * + * Compute, recursively if necessary, the largest offset among multiple + * re paths. + */ +static int +altoffset(sop *scan, int offset) +{ + int largest; + int try; + sop s; + + _DIAGASSERT(scan != NULL); + + /* If we gave up already on offsets, return */ + if (offset == -1) + return -1; + + largest = 0; + try = 0; + s = *scan++; + while (OP(s) != (sop)O_QUEST && OP(s) != (sop)O_CH) { + switch (OP(s)) { + case OOR1: + if (try > largest) + largest = try; + try = 0; + break; + case OQUEST_: + case OCH_: + try = altoffset(scan, try); + if (try == -1) + return -1; + scan--; + do { + scan += OPND(s); + s = *scan; + if (OP(s) != (sop)O_QUEST && + OP(s) != (sop)O_CH && OP(s) != (sop)OOR2) + return -1; + } while (OP(s) != (sop)O_QUEST && OP(s) != (sop)O_CH); + /* We must skip to the next position, or we'll + * leave altoffset() too early. + */ + scan++; + break; + case OANYOF: + case OCHAR: + case OANY: + try++; + case OBOW: + case OEOW: + case OWBND: + case ONWBND: + case OLPAREN: + case ORPAREN: + case OOR2: + break; + default: + try = -1; + break; + } + if (try == -1) + return -1; + s = *scan++; + } + + if (try > largest) + largest = try; + + return largest+offset; +} + +/* + - computejumps - compute char jumps for BM scan + == static void computejumps(struct parse *p, struct re_guts *g); + * + * This algorithm assumes g->must exists and is has size greater than + * zero. It's based on the algorithm found on Computer Algorithms by + * Sara Baase. + * + * A char jump is the number of characters one needs to jump based on + * the value of the character from the text that was mismatched. + */ +static void +computejumps(struct parse *p, struct re_guts *g) +{ + int ch; + size_t mindex; + + _DIAGASSERT(p != NULL); + _DIAGASSERT(g != NULL); + + /* Avoid making errors worse */ + if (p->error != 0) + return; + + g->charjump = calloc((NC_MAX + 1), sizeof(*g->charjump)); + if (g->charjump == NULL) /* Not a fatal error */ + return; + /* Adjust for signed chars, if necessary */ + g->charjump = &g->charjump[-(CHAR_MIN)]; + + /* If the character does not exist in the pattern, the jump + * is equal to the number of characters in the pattern. + */ + for (ch = CHAR_MIN; ch < (CHAR_MAX + 1); ch++) + g->charjump[ch] = g->mlen; + + /* If the character does exist, compute the jump that would + * take us to the last character in the pattern equal to it + * (notice that we match right to left, so that last character + * is the first one that would be matched). + */ + for (mindex = 0; mindex < g->mlen; mindex++) + g->charjump[(int)g->must[mindex]] = g->mlen - mindex - 1; +} + +/* + - computematchjumps - compute match jumps for BM scan + == static void computematchjumps(struct parse *p, struct re_guts *g); + * + * This algorithm assumes g->must exists and is has size greater than + * zero. It's based on the algorithm found on Computer Algorithms by + * Sara Baase. + * + * A match jump is the number of characters one needs to advance based + * on the already-matched suffix. + * Notice that all values here are minus (g->mlen-1), because of the way + * the search algorithm works. + */ +static void +computematchjumps(struct parse *p, struct re_guts *g) +{ + size_t mindex; /* General "must" iterator */ + size_t suffix; /* Keeps track of matching suffix */ + size_t ssuffix; /* Keeps track of suffixes' suffix */ + size_t* pmatches; /* pmatches[k] points to the next i + * such that i+1...mlen is a substring + * of k+1...k+mlen-i-1 + */ + + _DIAGASSERT(p != NULL); + _DIAGASSERT(g != NULL); + + /* Avoid making errors worse */ + if (p->error != 0) + return; + + pmatches = calloc(g->mlen, sizeof(*pmatches)); + if (pmatches == NULL) { + g->matchjump = NULL; + return; + } + + g->matchjump = calloc(g->mlen, sizeof(*g->matchjump)); + if (g->matchjump == NULL) { /* Not a fatal error */ + free(pmatches); + return; + } + + /* Set maximum possible jump for each character in the pattern */ + for (mindex = 0; mindex < g->mlen; mindex++) + g->matchjump[mindex] = 2 * g->mlen - mindex - 1; + + /* Compute pmatches[] */ + for (suffix = mindex = g->mlen; mindex-- > 0; suffix--) { + pmatches[mindex] = suffix; + + /* If a mismatch is found, interrupting the substring, + * compute the matchjump for that position. If no + * mismatch is found, then a text substring mismatched + * against the suffix will also mismatch against the + * substring. + */ + while (suffix < g->mlen + && g->must[mindex] != g->must[suffix]) { + g->matchjump[suffix] = MIN(g->matchjump[suffix], + g->mlen - mindex - 1); + suffix = pmatches[suffix]; + } + } + + /* Compute the matchjump up to the last substring found to jump + * to the beginning of the largest must pattern prefix matching + * it's own suffix. + */ + for (mindex = 0; mindex <= suffix; mindex++) + g->matchjump[mindex] = MIN(g->matchjump[mindex], + g->mlen + suffix - mindex); + + ssuffix = pmatches[suffix]; + while (suffix < g->mlen) { + while (suffix <= ssuffix && suffix < g->mlen) { + g->matchjump[suffix] = MIN(g->matchjump[suffix], + g->mlen + ssuffix - suffix); + suffix++; + } + if (suffix < g->mlen) + ssuffix = pmatches[ssuffix]; + } + + free(pmatches); +} + +/* - pluscount - count + nesting == static sopno pluscount(struct parse *p, struct re_guts *g); */ static sopno /* nesting depth */ -pluscount( - struct parse *p, - struct re_guts *g) +pluscount(struct parse *p, struct re_guts *g) { sop *scan; sop s; diff --git a/lib/libc/regex/regerror.c b/lib/libc/regex/regerror.c index e00d7c035f4..c788a9c49e3 100644 --- a/lib/libc/regex/regerror.c +++ b/lib/libc/regex/regerror.c @@ -1,6 +1,9 @@ -/* $NetBSD: regerror.c,v 1.23 2007/02/09 23:44:18 junyoung Exp $ */ +/* $NetBSD: regerror.c,v 1.24 2021/02/23 22:14:59 christos Exp $ */ /*- + * SPDX-License-Identifier: BSD-3-Clause + * + * Copyright (c) 1992, 1993, 1994 Henry Spencer. * Copyright (c) 1992, 1993, 1994 * The Regents of the University of California. All rights reserved. * @@ -34,76 +37,34 @@ * @(#)regerror.c 8.4 (Berkeley) 3/20/94 */ -/*- - * Copyright (c) 1992, 1993, 1994 Henry Spencer. - * - * This code is derived from software contributed to Berkeley by - * Henry Spencer. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * 3. All advertising materials mentioning features or use of this software - * must display the following acknowledgement: - * This product includes software developed by the University of - * California, Berkeley and its contributors. - * 4. Neither the name of the University nor the names of its contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND - * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE - * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL - * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS - * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) - * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT - * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY - * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF - * SUCH DAMAGE. - * - * @(#)regerror.c 8.4 (Berkeley) 3/20/94 - */ - #include <sys/cdefs.h> -#if defined(LIBC_SCCS) && !defined(lint) #if 0 static char sccsid[] = "@(#)regerror.c 8.4 (Berkeley) 3/20/94"; -#else -__RCSID("$NetBSD: regerror.c,v 1.23 2007/02/09 23:44:18 junyoung Exp $"); +__FBSDID("$FreeBSD: head/lib/libc/regex/regerror.c 326025 2017-11-20 19:49:47Z pfg $"); #endif -#endif /* LIBC_SCCS and not lint */ +__RCSID("$NetBSD: regerror.c,v 1.24 2021/02/23 22:14:59 christos Exp $"); #include "namespace.h" #include <sys/types.h> - -#include <assert.h> -#include <ctype.h> -#include <limits.h> #include <stdio.h> -#include <stdlib.h> #include <string.h> +#include <limits.h> +#include <stdlib.h> #include <regex.h> +#include "utils.h" + #ifdef __weak_alias __weak_alias(regerror,_regerror) #endif -#include "utils.h" - /* ========= begin header generated by ./mkh ========= */ #ifdef __cplusplus extern "C" { #endif /* === regerror.c === */ -static const char *regatoi(const regex_t *preg, char *localbuf, size_t buflen); +static const char *regatoi(const regex_t *preg, char *localbufm, size_t buflen); #ifdef __cplusplus } @@ -126,6 +87,8 @@ static const char *regatoi(const regex_t *preg, char *localbuf, size_t buflen); = #define REG_EMPTY 14 = #define REG_ASSERT 15 = #define REG_INVARG 16 + = #define REG_ENOSYS 17 + = #define REG_ILLSEQ 18 = #define REG_ATOI 255 // convert name to number (!) = #define REG_ITOA 0400 // convert number to name (!) */ @@ -134,36 +97,36 @@ static const struct rerr { const char *name; const char *explain; } rerrs[] = { - { REG_NOMATCH, "REG_NOMATCH", "regexec() failed to match" }, - { REG_BADPAT, "REG_BADPAT", "invalid regular expression" }, - { REG_ECOLLATE, "REG_ECOLLATE", "invalid collating element" }, - { REG_ECTYPE, "REG_ECTYPE", "invalid character class" }, - { REG_EESCAPE, "REG_EESCAPE", "trailing backslash (\\)" }, - { REG_ESUBREG, "REG_ESUBREG", "invalid backreference number" }, - { REG_EBRACK, "REG_EBRACK", "brackets ([ ]) not balanced" }, - { REG_EPAREN, "REG_EPAREN", "parentheses not balanced" }, - { REG_EBRACE, "REG_EBRACE", "braces not balanced" }, - { REG_BADBR, "REG_BADBR", "invalid repetition count(s)" }, - { REG_ERANGE, "REG_ERANGE", "invalid character range" }, - { REG_ESPACE, "REG_ESPACE", "out of memory" }, - { REG_BADRPT, "REG_BADRPT", "repetition-operator operand invalid" }, - { REG_EMPTY, "REG_EMPTY", "empty (sub)expression" }, - { REG_ASSERT, "REG_ASSERT", "\"can't happen\" -- you found a bug" }, - { REG_INVARG, "REG_INVARG", "invalid argument to regex routine" }, - { 0, "", "*** unknown regexp error code ***" } + {REG_NOMATCH, "REG_NOMATCH", "regexec() failed to match"}, + {REG_BADPAT, "REG_BADPAT", "invalid regular expression"}, + {REG_ECOLLATE, "REG_ECOLLATE", "invalid collating element"}, + {REG_ECTYPE, "REG_ECTYPE", "invalid character class"}, + {REG_EESCAPE, "REG_EESCAPE", "trailing backslash (\\)"}, + {REG_ESUBREG, "REG_ESUBREG", "invalid backreference number"}, + {REG_EBRACK, "REG_EBRACK", "brackets ([ ]) not balanced"}, + {REG_EPAREN, "REG_EPAREN", "parentheses not balanced"}, + {REG_EBRACE, "REG_EBRACE", "braces not balanced"}, + {REG_BADBR, "REG_BADBR", "invalid repetition count(s)"}, + {REG_ERANGE, "REG_ERANGE", "invalid character range"}, + {REG_ESPACE, "REG_ESPACE", "out of memory"}, + {REG_BADRPT, "REG_BADRPT", "repetition-operator operand invalid"}, + {REG_EMPTY, "REG_EMPTY", "empty (sub)expression"}, + {REG_ASSERT, "REG_ASSERT", "\"can't happen\" -- you found a bug"}, + {REG_INVARG, "REG_INVARG", "invalid argument to regex routine"}, + {REG_ILLSEQ, "REG_ILLSEQ", "illegal byte sequence"}, + {0, "", "*** unknown regexp error code ***"} }; /* - * regerror - the interface to error numbers - * extern size_t regerror(int, const regex_t *, char *, size_t); + - regerror - the interface to error numbers + = extern size_t regerror(int, const regex_t *, char *, size_t); */ /* ARGSUSED */ size_t -regerror( - int errcode, - const regex_t *preg, - char *errbuf, - size_t errbuf_size) +regerror(int errcode, + const regex_t * __restrict preg, + char * __restrict errbuf, + size_t errbuf_size) { const struct rerr *r; size_t len; @@ -174,19 +137,18 @@ regerror( _DIAGASSERT(errcode != REG_ATOI || preg != NULL); _DIAGASSERT(errbuf != NULL); - if (errcode == REG_ATOI) + if (errcode == REG_ATOI) { s = regatoi(preg, convbuf, sizeof convbuf); - else { + } else { for (r = rerrs; r->code != 0; r++) if (r->code == target) break; - - if (errcode & REG_ITOA) { - if (r->code != 0) { - (void)strlcpy(convbuf, r->name, sizeof convbuf); - } else - (void)snprintf(convbuf, sizeof convbuf, - "REG_0x%x", target); + + if (errcode®_ITOA) { + if (r->code != 0) + (void) strlcpy(convbuf, r->name, sizeof(convbuf)); + else + snprintf(convbuf, sizeof(convbuf), "REG_0x%x", target); s = convbuf; } else s = r->explain; @@ -194,21 +156,17 @@ regerror( len = strlen(s) + 1; if (errbuf_size > 0) - (void)strlcpy(errbuf, s, errbuf_size); + (void) strlcpy(errbuf, s, errbuf_size); return(len); } /* - * regatoi - internal routine to implement REG_ATOI - * static const char *regatoi(const regex_t *preg, char *localbuf, - * size_t buflen); + - regatoi - internal routine to implement REG_ATOI + == static char *regatoi(const regex_t *preg, char *localbuf); */ static const char * -regatoi( - const regex_t *preg, - char *localbuf, - size_t buflen) +regatoi(const regex_t *preg, char *localbuf, size_t buflen) { const struct rerr *r; @@ -218,6 +176,6 @@ regatoi( if (r->code == 0) return "0"; - (void)snprintf(localbuf, buflen, "%d", r->code); + snprintf(localbuf, buflen, "%d", r->code); return localbuf; } diff --git a/lib/libc/regex/regex.3 b/lib/libc/regex/regex.3 index bf24eaffbff..e0b206c8d2d 100644 --- a/lib/libc/regex/regex.3 +++ b/lib/libc/regex/regex.3 @@ -1,5 +1,4 @@ -.\" $NetBSD: regex.3,v 1.26 2018/02/26 14:04:43 kamil Exp $ -.\" +.\" Copyright (c) 1992, 1993, 1994 Henry Spencer. .\" Copyright (c) 1992, 1993, 1994 .\" The Regents of the University of California. All rights reserved. .\" @@ -30,46 +29,13 @@ .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF .\" SUCH DAMAGE. .\" -.\" Copyright (c) 1992, 1993, 1994 Henry Spencer. -.\" -.\" This code is derived from software contributed to Berkeley by -.\" Henry Spencer. -.\" -.\" Redistribution and use in source and binary forms, with or without -.\" modification, are permitted provided that the following conditions -.\" are met: -.\" 1. Redistributions of source code must retain the above copyright -.\" notice, this list of conditions and the following disclaimer. -.\" 2. Redistributions in binary form must reproduce the above copyright -.\" notice, this list of conditions and the following disclaimer in the -.\" documentation and/or other materials provided with the distribution. -.\" 3. All advertising materials mentioning features or use of this software -.\" must display the following acknowledgement: -.\" This product includes software developed by the University of -.\" California, Berkeley and its contributors. -.\" 4. Neither the name of the University nor the names of its contributors -.\" may be used to endorse or promote products derived from this software -.\" without specific prior written permission. -.\" -.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND -.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE -.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE -.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE -.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS -.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) -.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT -.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY -.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF -.\" SUCH DAMAGE. -.\" .\" @(#)regex.3 8.4 (Berkeley) 3/20/94 +.\" $FreeBSD: head/lib/libc/regex/regex.3 363817 2020-08-04 02:06:49Z kevans $ .\" -.Dd February 26, 2018 +.Dd February 22, 2021 .Dt REGEX 3 .Os .Sh NAME -.Nm regex , .Nm regcomp , .Nm regexec , .Nm regerror , @@ -82,11 +48,19 @@ .Sh SYNOPSIS .In regex.h .Ft int -.Fn regcomp "regex_t * restrict preg" "const char * restrict pattern" "int cflags" +.Fo regcomp +.Fa "regex_t * restrict preg" "const char * restrict pattern" "int cflags" +.Fc .Ft int -.Fn regexec "const regex_t * restrict preg" "const char * restrict string" "size_t nmatch" "regmatch_t pmatch[]" "int eflags" +.Fo regexec +.Fa "const regex_t * restrict preg" "const char * restrict string" +.Fa "size_t nmatch" "regmatch_t pmatch[restrict]" "int eflags" +.Fc .Ft size_t -.Fn regerror "int errcode" "const regex_t * restrict preg" "char * restrict errbuf" "size_t errbuf_size" +.Fo regerror +.Fa "int errcode" "const regex_t * restrict preg" +.Fa "char * restrict errbuf" "size_t errbuf_size" +.Fc .Ft void .Fn regfree "regex_t *preg" .Ft ssize_t @@ -95,11 +69,14 @@ .Fn regasub "char **buf" "const char *sub" "const regmatch_t *rm" "const char *sstr" .Sh DESCRIPTION These routines implement -.St -p1003.2-92 -regular expressions (``RE''s); +.St -p1003.2 +regular expressions +.Pq Do RE Dc Ns s ; see .Xr re_format 7 . +The .Fn regcomp +function compiles an RE written as a string into an internal form, .Fn regexec matches that internal form against a string and reports results, @@ -113,92 +90,152 @@ of an RE. The header .In regex.h declares two structure types, -.Fa regex_t +.Ft regex_t and -.Fa regmatch_t , +.Ft regmatch_t , the former for compiled internal forms and the latter for match reporting. It also declares the four functions, a type -.Fa regoff_t , -and a number of constants with names starting with ``REG_''. +.Ft regoff_t , +and a number of constants with names starting with +.Dq Dv REG_ . .Pp +The .Fn regcomp +function compiles the regular expression contained in the .Fa pattern string, subject to the flags in .Fa cflags , and places the results in the -.Fa regex_t +.Ft regex_t structure pointed to by .Fa preg . +The .Fa cflags +argument is the bitwise OR of zero or more of the following flags: -.Bl -tag -width XXXREG_EXTENDED +.Bl -tag -width REG_EXTENDED .It Dv REG_EXTENDED -Compile modern (``extended'') REs, rather than the obsolete -(``basic'') REs that are the default. +Compile modern +.Pq Dq extended +REs, +rather than the obsolete +.Pq Dq basic +REs that +are the default. .It Dv REG_BASIC This is a synonym for 0, -provided as a counterpart to REG_EXTENDED to improve readability. +provided as a counterpart to +.Dv REG_EXTENDED +to improve readability. .It Dv REG_NOSPEC Compile with recognition of all special characters turned off. -All characters are thus considered ordinary, so the ``RE'' is a literal -string. -This is an extension, compatible with but not specified by -.St -p1003.2-92 , -and should be used with caution in software intended to be portable to -other systems. +All characters are thus considered ordinary, +so the +.Dq RE +is a literal string. +This is an extension, +compatible with but not specified by +.St -p1003.2 , +and should be used with +caution in software intended to be portable to other systems. .Dv REG_EXTENDED and .Dv REG_NOSPEC -may not be used in the same call to +may not be used +in the same call to .Fn regcomp . .It Dv REG_ICASE Compile for matching that ignores upper/lower case distinctions. See .Xr re_format 7 . .It Dv REG_NOSUB -Compile for matching that need only report success or failure, not -what was matched. +Compile for matching that need only report success or failure, +not what was matched. .It Dv REG_NEWLINE Compile for newline-sensitive matching. By default, newline is a completely ordinary character with no special meaning in either REs or strings. With this flag, -`[^' bracket expressions and `.' never match newline, -a `^' anchor matches the null string after any newline in the string +.Ql [^ +bracket expressions and +.Ql .\& +never match newline, +a +.Ql ^\& +anchor matches the null string after any newline in the string in addition to its normal function, -and the `$' anchor matches the null string before any newline in the +and the +.Ql $\& +anchor matches the null string before any newline in the string in addition to its normal function. .It Dv REG_PEND -The regular expression ends, not at the first NUL, but just before the -character pointed to by the -.Fa re_endp +The regular expression ends, +not at the first NUL, +but just before the character pointed to by the +.Va re_endp member of the structure pointed to by .Fa preg . The -.Fa re_endp +.Va re_endp member is of type -.Fa "const\ char\ *" . -This flag permits inclusion of NULs in the RE; they are considered -ordinary characters. -This is an extension, compatible with but not specified by -.St -p1003.2-92 , -and should be used with caution in software intended to be portable to -other systems. +.Ft "const char *" . +This flag permits inclusion of NULs in the RE; +they are considered ordinary characters. +This is an extension, +compatible with but not specified by +.St -p1003.2 , +and should be used with +caution in software intended to be portable to other systems. +.It Dv REG_GNU +Include GNU-inspired extensions: +.Pp +.Bl -tag -offset indent -width XX -compact +.It \eN +Use backreference +.Dv N +where +.Dv N +is between +.Dv [1-9] . +.It \eb +Match a position that is a word boundary. +.It \eB +Match a position that is a not word boundary. +.It \es +Alias for [[:space:]] +.It \eS +Alias for [^[:space:]] +.It \ew +Alias for [[:alnum:]] +.It \eW +Alias for [^[:alnum:]] +.It \e' +Matches the end of the subject. +.It \e` +Matches the beginning of the subject. +.El +.Pp +This is an extension, +compatible with but not specified by +.St -p1003.2 , +and should be used with +caution in software intended to be portable to other systems. .El .Pp When successful, .Fn regcomp returns 0 and fills in the structure pointed to by .Fa preg . -One member of that structure (other than -.Fa re_endp ) +One member of that structure +(other than +.Va re_endp ) is publicized: -.Fa re_nsub , +.Va re_nsub , of type -.Fa size_t , +.Ft size_t , contains the number of parenthesized subexpressions within the RE (except that the value of this member is undefined if the .Dv REG_NOSUB @@ -209,7 +246,9 @@ fails, it returns a non-zero error code; see .Sx DIAGNOSTICS . .Pp +The .Fn regexec +function matches the compiled RE pointed to by .Fa preg against the @@ -234,43 +273,77 @@ newline. The .Fa eflags argument is the bitwise OR of zero or more of the following flags: -.Bl -tag -width XXXREG_NOTBOL +.Bl -tag -width REG_STARTEND .It Dv REG_NOTBOL -The first character of the string -is not the beginning of a line, so the `^' anchor should not match before it. +The first character of the string is treated as the continuation +of a line. +This means that the anchors +.Ql ^\& , +.Ql [[:<:]] , +and +.Ql \e< +do not match before it; but see +.Dv REG_STARTEND +below. This does not affect the behavior of newlines under .Dv REG_NEWLINE . .It Dv REG_NOTEOL -The NUL terminating the string does not end a line, so the `$' anchor -should not match before it. +The NUL terminating +the string +does not end a line, so the +.Ql $\& +anchor does not match before it. This does not affect the behavior of newlines under .Dv REG_NEWLINE . .It Dv REG_STARTEND The string is considered to start at -.Fa string -+ -.Fa pmatch[0].rm_so -and to have a terminating NUL located at -.Fa string -+ -.Fa pmatch[0].rm_eo -(there need not actually be a NUL at that location), +.Fa string No + +.Fa pmatch Ns [0]. Ns Fa rm_so +and to end before the byte located at +.Fa string No + +.Fa pmatch Ns [0]. Ns Fa rm_eo , regardless of the value of .Fa nmatch . See below for the definition of .Fa pmatch and .Fa nmatch . -This is an extension, compatible with but not specified by -.St -p1003.2-92 , -and should be used with caution in software intended to be portable to -other systems. -Note that a non-zero +This is an extension, +compatible with but not specified by +.St -p1003.2 , +and should be used with +caution in software intended to be portable to other systems. +.Pp +Without +.Dv REG_NOTBOL , +the position .Fa rm_so -does not imply -.Dv REG_NOTBOL ; -.Dv REG_STARTEND -affects only the location of the string, not how it is matched. +is considered the beginning of a line, such that +.Ql ^ +matches before it, and the beginning of a word if there is a word +character at this position, such that +.Ql [[:<:]] +and +.Ql \e< +match before it. +.Pp +With +.Dv REG_NOTBOL , +the character at position +.Fa rm_so +is treated as the continuation of a line, and if +.Fa rm_so +is greater than 0, the preceding character is taken into consideration. +If the preceding character is a newline and the regular expression was compiled +with +.Dv REG_NEWLINE , +.Ql ^ +matches before the string; if the preceding character is not a word character +but the string starts with a word character, +.Ql [[:<:]] +and +.Ql \e< +match before the string. .El .Pp See @@ -290,7 +363,8 @@ see .Pp If .Dv REG_NOSUB -was specified in the compilation of the RE, or if +was specified in the compilation of the RE, +or if .Fa nmatch is 0, .Fn regexec @@ -304,17 +378,17 @@ Otherwise, points to an array of .Fa nmatch structures of type -.Fa regmatch_t . +.Ft regmatch_t . Such a structure has at least the members -.Fa rm_so +.Va rm_so and -.Fa rm_eo , +.Va rm_eo , both of type -.Fa regoff_t +.Ft regoff_t (a signed arithmetic type at least as large as an -.Fa off_t +.Ft off_t and a -.Fa ssize_t ) , +.Ft ssize_t ) , containing respectively the offset of the first character of a substring and the offset of the first character after the end of the substring. Offsets are measured from the beginning of the @@ -332,27 +406,33 @@ was matched by the entire RE. Remaining members report what substring was matched by parenthesized subexpressions within the RE; member -.Fa i +.Va i reports subexpression -.Fa i , -with subexpressions counted (starting at 1) by the order of their -opening parentheses in the RE, left to right. -Unused entries in the array\(emcorresponding either to subexpressions that +.Va i , +with subexpressions counted (starting at 1) by the order of their opening +parentheses in the RE, left to right. +Unused entries in the array (corresponding either to subexpressions that did not participate in the match at all, or to subexpressions that do not exist in the RE (that is, -.Fa i +.Va i > -.Fa preg->re_nsub ) -\(emhave both -.Fa rm_so +.Fa preg Ns -> Ns Va re_nsub ) ) +have both +.Va rm_so and -.Fa rm_eo +.Va rm_eo set to -1. If a subexpression participated in the match several times, the reported substring is the last one it matched. -(Note, as an example in particular, that when the RE `(b*)+' matches `bbb', -the parenthesized subexpression matches each of the three `b's and then -an infinite number of empty strings following the last `b', +(Note, as an example in particular, that when the RE +.Ql "(b*)+" +matches +.Ql bbb , +the parenthesized subexpression matches each of the three +.So Li b Sc Ns s +and then +an infinite number of empty strings following the last +.Ql b , so the reported substring is one of the empties.) .Pp If @@ -360,7 +440,7 @@ If is specified, .Fa pmatch must point to at least one -.Fa regmatch_t +.Ft regmatch_t (even if .Fa nmatch is 0 or @@ -376,11 +456,13 @@ is 0 or .Dv REG_NOSUB was specified, the value of -.Fa pmatch [0] +.Fa pmatch Ns [0] will not be changed by a successful .Fn regexec . .Pp +The .Fn regerror +function maps a non-zero .Fa errcode from either @@ -390,9 +472,11 @@ or to a human-readable, printable message. If .Fa preg -is non-NULL, -the error code should have arisen from use of the -.Fa regex_t +is +.No non\- Ns Dv NULL , +the error code should have arisen from use of +the +.Ft regex_t pointed to by .Fa preg , and if the error code came from @@ -400,18 +484,23 @@ and if the error code came from it should have been the result from the most recent .Fn regcomp using that -.Fa regex_t . -.Po Fn regerror +.Ft regex_t . +The +.Po +.Fn regerror may be able to supply a more detailed message using information from the -.Fa regex_t . Pc +.Ft regex_t . +.Pc +The .Fn regerror +function places the NUL-terminated message into the buffer pointed to by .Fa errbuf , limiting the length (including the NUL) to at most .Fa errbuf_size bytes. -If the whole message won't fit, +If the whole message will not fit, as much of it as will fit before the terminating NUL is supplied. In any case, the returned value is the size of buffer needed to hold the whole @@ -428,8 +517,11 @@ given to .Fn regerror is first ORed with .Dv REG_ITOA , -the ``message'' that results is the printable name of the error code, -e.g. ``REG_NOMATCH'', +the +.Dq message +that results is the printable name of the error code, +e.g.\& +.Dq Dv REG_NOMATCH , rather than an explanation thereof. If .Fa errcode @@ -437,8 +529,10 @@ is .Dv REG_ATOI , then .Fa preg -shall be non-NULL and the -.Fa re_endp +shall be +.No non\- Ns Dv NULL +and the +.Va re_endp member of the structure it points to must point to the printable name of an error code; in this case, the result in @@ -450,18 +544,21 @@ the numeric value of the error code and .Dv REG_ATOI are intended primarily as debugging facilities; -they are extensions, compatible with but not specified by -.St -p1003.2-92 , -and should be used with caution in software intended to be portable to -other systems. +they are extensions, +compatible with but not specified by +.St -p1003.2 , +and should be used with +caution in software intended to be portable to other systems. Be warned also that they are considered experimental and changes are possible. .Pp +The .Fn regfree +function frees any dynamically-allocated storage associated with the compiled RE pointed to by .Fa preg . The remaining -.Fa regex_t +.Ft regex_t is no longer a valid compiled RE and the effect of supplying it to .Fn regexec @@ -517,9 +614,11 @@ The argument contains the source string to apply the transformation to. .Sh IMPLEMENTATION CHOICES There are a number of decisions that -.St -p1003.2-92 +.St -p1003.2 leaves up to the implementor, -either by explicitly saying ``undefined'' or by virtue of them being +either by explicitly saying +.Dq undefined +or by virtue of them being forbidden by the RE grammar. This implementation treats them as follows. .Pp @@ -531,16 +630,22 @@ There is no particular limit on the length of REs, except insofar as memory is limited. Memory usage is approximately linear in RE size, and largely insensitive to RE complexity, except for bounded repetitions. -See BUGS for one short RE using them +See +.Sx BUGS +for one short RE using them that will run almost any system out of memory. .Pp A backslashed character other than one specifically given a magic meaning by -.St -p1003.2-92 -(such magic meanings occur only in obsolete [``basic''] REs) +.St -p1003.2 +(such magic meanings occur only in obsolete +.Bq Dq basic +REs) is taken as an ordinary character. .Pp -Any unmatched [ is a +Any unmatched +.Ql [\& +is a .Dv REG_EBRACK error. .Pp @@ -550,24 +655,45 @@ The endpoint of one range cannot begin another. .Dv RE_DUP_MAX , the limit on repetition counts in bounded repetitions, is 255. .Pp -A repetition operator (?, *, +, or bounds) cannot follow another +A repetition operator +.Ql ( ?\& , +.Ql *\& , +.Ql +\& , +or bounds) +cannot follow another repetition operator. A repetition operator cannot begin an expression or subexpression -or follow `^' or `|'. -.Pp -`|' cannot appear first or last in a (sub)expression or after another `|', -i.e. an operand of `|' cannot be an empty subexpression. -An empty parenthesized subexpression, `()', is legal and matches an +or follow +.Ql ^\& +or +.Ql |\& . +.Pp +.Ql |\& +cannot appear first or last in a (sub)expression or after another +.Ql |\& , +i.e., an operand of +.Ql |\& +cannot be an empty subexpression. +An empty parenthesized subexpression, +.Ql "()" , +is legal and matches an empty (sub)string. An empty string is not a legal RE. .Pp -A `{' followed by a digit is considered the beginning of bounds for a +A +.Ql {\& +followed by a digit is considered the beginning of bounds for a bounded repetition, which must then follow the syntax for bounds. -A `{' +A +.Ql {\& .Em not followed by a digit is considered an ordinary character. .Pp -`^' and `$' beginning and ending subexpressions in obsolete (``basic'') +.Ql ^\& +and +.Ql $\& +beginning and ending subexpressions in obsolete +.Pq Dq basic REs are anchors, not ordinary characters. .Sh DIAGNOSTICS Non-zero error codes from @@ -576,9 +702,11 @@ and .Fn regexec include the following: .Pp -.Bl -tag -width XXXREG_ECOLLATE -compact +.Bl -tag -width REG_ECOLLATE -compact .It Dv REG_NOMATCH +The .Fn regexec +function failed to match .It Dv REG_BADPAT invalid regular expression @@ -587,41 +715,56 @@ invalid collating element .It Dv REG_ECTYPE invalid character class .It Dv REG_EESCAPE -\e applied to unescapable character +.Ql \e +applied to unescapable character .It Dv REG_ESUBREG invalid backreference number .It Dv REG_EBRACK -brackets [ ] not balanced +brackets +.Ql "[ ]" +not balanced .It Dv REG_EPAREN -parentheses ( ) not balanced +parentheses +.Ql "( )" +not balanced .It Dv REG_EBRACE -braces { } not balanced +braces +.Ql "{ }" +not balanced .It Dv REG_BADBR -invalid repetition count(s) in { } +invalid repetition count(s) in +.Ql "{ }" .It Dv REG_ERANGE -invalid character range in [ ] +invalid character range in +.Ql "[ ]" .It Dv REG_ESPACE ran out of memory .It Dv REG_BADRPT -?, *, or + operand invalid +.Ql ?\& , +.Ql *\& , +or +.Ql +\& +operand invalid .It Dv REG_EMPTY empty (sub)expression .It Dv REG_ASSERT -``can't happen''\(emyou found a bug +cannot happen - you found a bug .It Dv REG_INVARG -invalid argument, e.g. negative-length string +invalid argument, e.g.\& negative-length string +.It Dv REG_ILLSEQ +illegal byte sequence (bad multibyte character) .El .Sh SEE ALSO .Xr grep 1 , -.Xr sed 1 , .Xr re_format 7 .Pp -.St -p1003.2-92 , +.St -p1003.2 , sections 2.8 (Regular Expression Notation) and B.5 (C Binding for Regular Expression Matching). .Sh HISTORY -Originally written by Henry Spencer. +Originally written by +.An Henry Spencer . Altered for inclusion in the .Bx 4.4 distribution. @@ -633,36 +776,42 @@ and functions appeared in .Nx 8 . .Sh BUGS -There is one known functionality bug. -The implementation of internationalization is incomplete: -the locale is always assumed to be the default one of -.St -p1003.2-92 , -and only the collating elements etc. of that locale are available. +This is an alpha release with known defects. +Please report problems. .Pp The back-reference code is subtle and doubts linger about its correctness in complex cases. .Pp +The .Fn regexec +function performance is poor. This will improve with later releases. +The .Fa nmatch +argument exceeding 0 is expensive; .Fa nmatch exceeding 1 is worse. -.Fa regexec +The +.Fn regexec +function is largely insensitive to RE complexity .Em except -that back references are massively expensive. +that back +references are massively expensive. RE length does matter; in particular, there is a strong speed bonus for keeping RE length under about 30 characters, with most special characters counting roughly double. .Pp +The .Fn regcomp +function implements bounded repetitions by macro expansion, which is costly in time and space if counts are large or bounded repetitions are nested. An RE like, say, -`((((a{1,100}){1,100}){1,100}){1,100}){1,100}' +.Ql "((((a{1,100}){1,100}){1,100}){1,100}){1,100}" will (eventually) run almost any existing machine out of swap space. .Pp There are suspected problems with response to obscure error conditions. @@ -672,16 +821,25 @@ produced only by truly enormous REs or by multiply nested bounded repetitions, are probably not handled well. .Pp Due to a mistake in -.St -p1003.2-92 , -things like `a)b' are legal REs because `)' is a special character -only in the presence of a previous unmatched `('. -This can't be fixed until the spec is fixed. +.St -p1003.2 , +things like +.Ql "a)b" +are legal REs because +.Ql )\& +is +a special character only in the presence of a previous unmatched +.Ql (\& . +This cannot be fixed until the spec is fixed. .Pp The standard's definition of back references is vague. For example, does -`a\e(\e(b\e)*\e2\e)*d' match `abbbd'? -Until the standard is clarified, behavior in such cases should not be -relied on. +.Ql "a\e(\e(b\e)*\e2\e)*d" +match +.Ql "abbbd" ? +Until the standard is clarified, +behavior in such cases should not be relied on. .Pp The implementation of word-boundary matching is a bit of a kludge, and bugs may lurk in combinations of word-boundary matching and anchoring. +.Pp +Word-boundary matching does not work properly in multibyte locales. diff --git a/lib/libc/regex/regex2.h b/lib/libc/regex/regex2.h index 7c877ee87a2..a971b34751d 100644 --- a/lib/libc/regex/regex2.h +++ b/lib/libc/regex/regex2.h @@ -1,6 +1,9 @@ -/* $NetBSD: regex2.h,v 1.13 2011/10/09 18:23:00 christos Exp $ */ +/* $NetBSD: regex2.h,v 1.14 2021/02/23 22:14:59 christos Exp $ */ /*- + * SPDX-License-Identifier: BSD-3-Clause + * + * Copyright (c) 1992, 1993, 1994 Henry Spencer. * Copyright (c) 1992, 1993, 1994 * The Regents of the University of California. All rights reserved. * @@ -32,43 +35,7 @@ * SUCH DAMAGE. * * @(#)regex2.h 8.4 (Berkeley) 3/20/94 - */ - -/*- - * Copyright (c) 1992, 1993, 1994 Henry Spencer. - * - * This code is derived from software contributed to Berkeley by - * Henry Spencer. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * 3. All advertising materials mentioning features or use of this software - * must display the following acknowledgement: - * This product includes software developed by the University of - * California, Berkeley and its contributors. - * 4. Neither the name of the University nor the names of its contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND - * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE - * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL - * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS - * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) - * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT - * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY - * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF - * SUCH DAMAGE. - * - * @(#)regex2.h 8.4 (Berkeley) 3/20/94 + * $FreeBSD: head/lib/libc/regex/regex2.h 368359 2020-12-05 03:18:48Z kevans $ */ /* @@ -109,68 +76,100 @@ * In state representations, an operator's bit is on to signify a state * immediately *preceding* "execution" of that operator. */ -typedef u_int32_t sop; /* strip operator */ -typedef size_t sopno; -#define OPRMASK ((u_int32_t)0xf8000000UL) -#define OPDMASK ((u_int32_t)0x07ffffffUL) +typedef unsigned long sop; /* strip operator */ +typedef unsigned long sopno; +#define OPRMASK 0xf8000000L +#define OPDMASK 0x07ffffffL #define OPSHIFT ((unsigned)27) #define OP(n) ((n)&OPRMASK) -#define OPND(n) ((int)((n)&OPDMASK)) +#define OPND(n) ((n)&OPDMASK) #define SOP(op, opnd) ((op)|(opnd)) - -#define OPC(n) (((u_int32_t)(n))<<OPSHIFT) -/* operators meaning operand */ -/* (back, fwd are offsets) */ -#define OEND OPC(1) /* endmarker - */ -#define OCHAR OPC(2) /* character unsigned char */ -#define OBOL OPC(3) /* left anchor - */ -#define OEOL OPC(4) /* right anchor - */ -#define OANY OPC(5) /* . - */ -#define OANYOF OPC(6) /* [...] set number */ -#define OBACK_ OPC(7) /* begin \d paren number */ -#define O_BACK OPC(8) /* end \d paren number */ -#define OPLUS_ OPC(9) /* + prefix fwd to suffix */ -#define O_PLUS OPC(10) /* + suffix back to prefix */ -#define OQUEST_ OPC(11) /* ? prefix fwd to suffix */ -#define O_QUEST OPC(12) /* ? suffix back to prefix */ -#define OLPAREN OPC(13) /* ( fwd to ) */ -#define ORPAREN OPC(14) /* ) back to ( */ -#define OCH_ OPC(15) /* begin choice fwd to OOR2 */ -#define OOR1 OPC(16) /* | pt. 1 back to OOR1 or OCH_ */ -#define OOR2 OPC(17) /* | pt. 2 fwd to OOR2 or O_CH */ -#define O_CH OPC(18) /* end choice back to OOR1 */ -#define OBOW OPC(19) /* begin word - */ -#define OEOW OPC(20) /* end word - */ +/* operators meaning operand */ +/* (back, fwd are offsets) */ +#define OEND (1L<<OPSHIFT) /* endmarker - */ +#define OCHAR (2L<<OPSHIFT) /* character wide character */ +#define OBOL (3L<<OPSHIFT) /* left anchor - */ +#define OEOL (4L<<OPSHIFT) /* right anchor - */ +#define OANY (5L<<OPSHIFT) /* . - */ +#define OANYOF (6L<<OPSHIFT) /* [...] set number */ +#define OBACK_ (7L<<OPSHIFT) /* begin \d paren number */ +#define O_BACK (8L<<OPSHIFT) /* end \d paren number */ +#define OPLUS_ (9L<<OPSHIFT) /* + prefix fwd to suffix */ +#define O_PLUS (10L<<OPSHIFT) /* + suffix back to prefix */ +#define OQUEST_ (11L<<OPSHIFT) /* ? prefix fwd to suffix */ +#define O_QUEST (12L<<OPSHIFT) /* ? suffix back to prefix */ +#define OLPAREN (13L<<OPSHIFT) /* ( fwd to ) */ +#define ORPAREN (14L<<OPSHIFT) /* ) back to ( */ +#define OCH_ (15L<<OPSHIFT) /* begin choice fwd to OOR2 */ +#define OOR1 (16L<<OPSHIFT) /* | pt. 1 back to OOR1 or OCH_ */ +#define OOR2 (17L<<OPSHIFT) /* | pt. 2 fwd to OOR2 or O_CH */ +#define O_CH (18L<<OPSHIFT) /* end choice back to OOR1 */ +#define OBOW (19L<<OPSHIFT) /* begin word - */ +#define OEOW (20L<<OPSHIFT) /* end word - */ +#define OBOS (21L<<OPSHIFT) /* begin subj. - */ +#define OEOS (22L<<OPSHIFT) /* end subj. - */ +#define OWBND (23L<<OPSHIFT) /* word bound - */ +#define ONWBND (24L<<OPSHIFT) /* not bound - */ /* - * Structure for [] character-set representation. Character sets are - * done as bit vectors, grouped 8 to a byte vector for compactness. - * The individual set therefore has both a pointer to the byte vector - * and a mask to pick out the relevant bit of each byte. A hash code - * simplifies testing whether two sets could be identical. - * - * This will get trickier for multicharacter collating elements. As - * preliminary hooks for dealing with such things, we also carry along - * a string of multi-character elements, and decide the size of the - * vectors at run time. + * Structures for [] character-set representation. */ typedef struct { - uch *ptr; /* -> uch [csetsize] */ - uch mask; /* bit within array */ - uch hash; /* hash code */ - size_t smultis; - char *multis; /* -> char[smulti] ab\0cd\0ef\0\0 */ + wint_t min; + wint_t max; +} crange; +typedef struct { + unsigned char bmp[NC_MAX / 8]; + wctype_t *types; + unsigned int ntypes; + wint_t *wides; + unsigned int nwides; + crange *ranges; + unsigned int nranges; + int invert; + int icase; } cset; -/* note that CHadd and CHsub are unsafe, and CHIN doesn't yield 0/1 */ -#define CHadd(cs, c) ((cs)->ptr[(uch)(c)] |= (cs)->mask, (cs)->hash += (c)) -#define CHsub(cs, c) ((cs)->ptr[(uch)(c)] &= ~(cs)->mask, (cs)->hash -= (c)) -#define CHIN(cs, c) ((cs)->ptr[(uch)(c)] & (cs)->mask) -#define MCadd(p, cs, cp) mcadd(p, cs, cp) /* regcomp() internal fns */ -#define MCsub(p, cs, cp) mcsub(p, cs, cp) -#define MCin(p, cs, cp) mcin(p, cs, cp) -/* stuff for character categories */ -typedef unsigned char cat_t; +static int +CHIN1(cset *cs, wint_t ch) +{ + unsigned int i; + + assert(ch >= 0); + if (ch < NC) + return (((cs->bmp[ch >> 3] & (1 << (ch & 7))) != 0) ^ + cs->invert); + for (i = 0; i < cs->nwides; i++) { + if (cs->icase) { + if (ch == towlower(cs->wides[i]) || + ch == towupper(cs->wides[i])) + return (!cs->invert); + } else if (ch == cs->wides[i]) + return (!cs->invert); + } + for (i = 0; i < cs->nranges; i++) + if (cs->ranges[i].min <= ch && ch <= cs->ranges[i].max) + return (!cs->invert); + for (i = 0; i < cs->ntypes; i++) + if (iswctype(ch, cs->types[i])) + return (!cs->invert); + return (cs->invert); +} + +static __inline int +CHIN(cset *cs, wint_t ch) +{ + + assert(ch >= 0); + if (ch < NC) + return (((cs->bmp[ch >> 3] & (1 << (ch & 7))) != 0) ^ + cs->invert); + else if (cs->icase) + return (CHIN1(cs, ch) || CHIN1(cs, towlower(ch)) || + CHIN1(cs, towupper(ch))); + else + return (CHIN1(cs, ch)); +} /* * main compiled-expression structure @@ -179,10 +178,8 @@ struct re_guts { int magic; # define MAGIC2 ((('R'^0200)<<8)|'E') sop *strip; /* malloced area for strip */ - size_t csetsize; /* number of bits in a cset vector */ size_t ncsets; /* number of csets in use */ cset *sets; /* -> cset [ncsets] */ - uch *setbits; /* -> uch[csetsize][ncsets/CHAR_BIT] */ int cflags; /* copy of regcomp() cflags argument */ sopno nstates; /* = number of sops */ sopno firststate; /* the initial OEND (normally 0) */ @@ -193,17 +190,17 @@ struct re_guts { # define BAD 04 /* something wrong */ size_t nbol; /* number of ^ used */ size_t neol; /* number of $ used */ - size_t ncategories; /* how many character categories */ - cat_t *categories; /* ->catspace[-CHAR_MIN] */ char *must; /* match must contain this string */ + int moffset; /* latest point at which must may be located */ + size_t *charjump; /* Boyer-Moore char jump table */ + size_t *matchjump; /* Boyer-Moore match jump table */ size_t mlen; /* length of must */ size_t nsub; /* copy of re_nsub */ int backrefs; /* does it use back references? */ sopno nplus; /* how deep does it nest +s? */ - /* catspace must be last */ - cat_t catspace[1]; /* actually [NC] */ }; /* misc utilities */ -#define OUT (CHAR_MAX+1) /* a non-character value */ -#define ISWORD(c) (isalnum((unsigned char)c) || (c) == '_') +#define OUT (CHAR_MIN - 1) /* a non-character value */ +#define IGN (CHAR_MIN - 2) +#define ISWORD(c) (iswalnum((uch)(c)) || (c) == '_') diff --git a/lib/libc/regex/regexec.c b/lib/libc/regex/regexec.c index f16e0b6b485..0975b85399e 100644 --- a/lib/libc/regex/regexec.c +++ b/lib/libc/regex/regexec.c @@ -1,6 +1,9 @@ -/* $NetBSD: regexec.c,v 1.22 2012/03/13 21:13:43 christos Exp $ */ +/* $NetBSD: regexec.c,v 1.23 2021/02/23 22:14:59 christos Exp $ */ /*- + * SPDX-License-Identifier: BSD-3-Clause + * + * Copyright (c) 1992, 1993, 1994 Henry Spencer. * Copyright (c) 1992, 1993, 1994 * The Regents of the University of California. All rights reserved. * @@ -34,69 +37,31 @@ * @(#)regexec.c 8.3 (Berkeley) 3/20/94 */ -/*- - * Copyright (c) 1992, 1993, 1994 Henry Spencer. - * - * This code is derived from software contributed to Berkeley by - * Henry Spencer. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * 3. All advertising materials mentioning features or use of this software - * must display the following acknowledgement: - * This product includes software developed by the University of - * California, Berkeley and its contributors. - * 4. Neither the name of the University nor the names of its contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND - * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE - * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL - * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS - * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) - * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT - * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY - * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF - * SUCH DAMAGE. - * - * @(#)regexec.c 8.3 (Berkeley) 3/20/94 - */ - #include <sys/cdefs.h> -#if defined(LIBC_SCCS) && !defined(lint) #if 0 static char sccsid[] = "@(#)regexec.c 8.3 (Berkeley) 3/20/94"; -#else -__RCSID("$NetBSD: regexec.c,v 1.22 2012/03/13 21:13:43 christos Exp $"); +__FBSDID("$FreeBSD: head/lib/libc/regex/regexec.c 326025 2017-11-20 19:49:47Z pfg $"); #endif -#endif /* LIBC_SCCS and not lint */ +__RCSID("$NetBSD: regexec.c,v 1.23 2021/02/23 22:14:59 christos Exp $"); /* * the outer shell of regexec() * - * This file includes engine.c *twice*, after muchos fiddling with the + * This file includes engine.c three times, after muchos fiddling with the * macros that code uses. This lets the same code operate on two different - * representations for state sets. + * representations for state sets and characters. */ + #include "namespace.h" #include <sys/types.h> - -#include <assert.h> -#include <ctype.h> -#include <limits.h> #include <stdio.h> #include <stdlib.h> #include <string.h> +#include <limits.h> +#include <ctype.h> #include <regex.h> +#include <wchar.h> +#include <wctype.h> #ifdef __weak_alias __weak_alias(regexec,_regexec) @@ -105,20 +70,55 @@ __weak_alias(regexec,_regexec) #include "utils.h" #include "regex2.h" +static int nope __unused = 0; /* for use in asserts; shuts lint up */ + +static __inline size_t +xmbrtowc(wint_t *wi, const char *s, size_t n, mbstate_t *mbs, wint_t dummy) +{ + size_t nr; + wchar_t wc; + + nr = mbrtowc(&wc, s, n, mbs); + if (wi != NULL) + *wi = wc; + if (nr == 0) + return (1); + else if (nr == (size_t)-1 || nr == (size_t)-2) { + memset(mbs, 0, sizeof(*mbs)); + if (wi != NULL) + *wi = dummy; + return (1); + } else + return (nr); +} + +static __inline size_t +xmbrtowc_dummy(wint_t *wi, + const char *s, + size_t n __unused, + mbstate_t *mbs __unused, + wint_t dummy __unused) +{ + + if (wi != NULL) + *wi = (unsigned char)*s; + return (1); +} + /* macros for manipulating states, small version */ -#define states unsigned long -#define states1 unsigned long /* for later use in regexec() decision */ +#define states long +#define states1 states /* for later use in regexec() decision */ #define CLEAR(v) ((v) = 0) #define SET0(v, n) ((v) &= ~((unsigned long)1 << (n))) #define SET1(v, n) ((v) |= (unsigned long)1 << (n)) #define ISSET(v, n) (((v) & ((unsigned long)1 << (n))) != 0) #define ASSIGN(d, s) ((d) = (s)) #define EQ(a, b) ((a) == (b)) -#define STATEVARS int dummy /* dummy version */ +#define STATEVARS long dummy /* dummy version */ #define STATESETUP(m, n) /* nothing */ #define STATETEARDOWN(m) /* nothing */ #define SETUP(v) ((v) = 0) -#define onestate unsigned long +#define onestate long #define INIT(o, n) ((o) = (unsigned long)1 << (n)) #define INC(o) ((o) <<= 1) #define ISSTATEIN(v, o) (((v) & (o)) != 0) @@ -127,6 +127,9 @@ __weak_alias(regexec,_regexec) #define FWD(dst, src, n) ((dst) |= ((unsigned long)(src)&(here)) << (n)) #define BACK(dst, src, n) ((dst) |= ((unsigned long)(src)&(here)) >> (n)) #define ISSETBACK(v, n) (((v) & ((unsigned long)here >> (n))) != 0) +/* no multibyte support */ +#define XMBRTOWC xmbrtowc_dummy +#define ZAPSTATE(mbs) ((void)(mbs)) /* function names */ #define SNAMES /* engine.c looks after details */ @@ -152,26 +155,25 @@ __weak_alias(regexec,_regexec) #undef BACK #undef ISSETBACK #undef SNAMES +#undef XMBRTOWC +#undef ZAPSTATE /* macros for manipulating states, large version */ #define states char * -#define CLEAR(v) memset(v, 0, (size_t)m->g->nstates) +#define CLEAR(v) memset(v, 0, m->g->nstates) #define SET0(v, n) ((v)[n] = 0) #define SET1(v, n) ((v)[n] = 1) #define ISSET(v, n) ((v)[n]) -#define ASSIGN(d, s) memcpy(d, s, (size_t)m->g->nstates) -#define EQ(a, b) (memcmp(a, b, (size_t)m->g->nstates) == 0) -#define STATEVARS int vn; char *space -#define STATESETUP(m, nv) \ - if (((m)->space = malloc((size_t)((nv)*(m)->g->nstates))) == NULL) \ - return(REG_ESPACE); \ - else \ - (m)->vn = 0 - -#define STATETEARDOWN(m) { free((m)->space); m->space = NULL; } -#define SETUP(v) ((v) = &m->space[(size_t)(m->vn++ * m->g->nstates)]) -#define onestate int -#define INIT(o, n) ((o) = (int)(n)) +#define ASSIGN(d, s) memcpy(d, s, m->g->nstates) +#define EQ(a, b) (memcmp(a, b, m->g->nstates) == 0) +#define STATEVARS long vn; char *space +#define STATESETUP(m, nv) { (m)->space = malloc((nv)*(m)->g->nstates); \ + if ((m)->space == NULL) return(REG_ESPACE); \ + (m)->vn = 0; } +#define STATETEARDOWN(m) { free((m)->space); } +#define SETUP(v) ((v) = &m->space[m->vn++ * m->g->nstates]) +#define onestate long +#define INIT(o, n) ((o) = (n)) #define INC(o) ((o)++) #define ISSTATEIN(v, o) ((v)[o]) /* some abbreviations; note that some of these know variable names! */ @@ -179,11 +181,24 @@ __weak_alias(regexec,_regexec) #define FWD(dst, src, n) ((dst)[here+(n)] |= (src)[here]) #define BACK(dst, src, n) ((dst)[here-(n)] |= (src)[here]) #define ISSETBACK(v, n) ((v)[here - (n)]) +/* no multibyte support */ +#define XMBRTOWC xmbrtowc_dummy +#define ZAPSTATE(mbs) ((void)(mbs)) /* function names */ #define LNAMES /* flag */ #include "engine.c" +/* multibyte character & large states version */ +#undef LNAMES +#undef XMBRTOWC +#undef ZAPSTATE +#define XMBRTOWC xmbrtowc +#define ZAPSTATE(mbs) memset((mbs), 0, sizeof(*(mbs))) +#define MNAMES + +#include "engine.c" + /* - regexec - interface for matching = extern int regexec(const regex_t *, const char *, size_t, \ @@ -200,21 +215,18 @@ __weak_alias(regexec,_regexec) * have been prototyped. */ int /* 0 success, REG_NOMATCH failure */ -regexec( - const regex_t *preg, - const char *string, - size_t nmatch, - regmatch_t pmatch[], - int eflags) +regexec(const regex_t * __restrict preg, + const char * __restrict string, + size_t nmatch, + regmatch_t pmatch[__restrict], + int eflags) { struct re_guts *g = preg->re_g; - char *s; #ifdef REDEBUG # define GOODFLAGS(f) (f) #else # define GOODFLAGS(f) ((f)&(REG_NOTBOL|REG_NOTEOL|REG_STARTEND)) #endif - _DIAGASSERT(preg != NULL); _DIAGASSERT(string != NULL); @@ -225,10 +237,10 @@ regexec( return(REG_BADPAT); eflags = GOODFLAGS(eflags); - s = __UNCONST(string); - - if (g->nstates <= (sopno)(CHAR_BIT*sizeof(states1)) && !(eflags®_LARGE)) - return(smatcher(g, s, nmatch, pmatch, eflags)); + if (MB_CUR_MAX > 1) + return(mmatcher(g, string, nmatch, pmatch, eflags)); + else if (g->nstates <= CHAR_BIT*sizeof(states1) && !(eflags®_LARGE)) + return(smatcher(g, string, nmatch, pmatch, eflags)); else - return(lmatcher(g, s, nmatch, pmatch, eflags)); + return(lmatcher(g, string, nmatch, pmatch, eflags)); } diff --git a/lib/libc/regex/regfree.c b/lib/libc/regex/regfree.c index ce011eade6b..a126d8cfc83 100644 --- a/lib/libc/regex/regfree.c +++ b/lib/libc/regex/regfree.c @@ -1,6 +1,9 @@ -/* $NetBSD: regfree.c,v 1.15 2007/02/09 23:44:18 junyoung Exp $ */ +/* $NetBSD: regfree.c,v 1.16 2021/02/23 22:14:59 christos Exp $ */ /*- + * SPDX-License-Identifier: BSD-3-Clause + * + * Copyright (c) 1992, 1993, 1994 Henry Spencer. * Copyright (c) 1992, 1993, 1994 * The Regents of the University of California. All rights reserved. * @@ -34,63 +37,25 @@ * @(#)regfree.c 8.3 (Berkeley) 3/20/94 */ -/*- - * Copyright (c) 1992, 1993, 1994 Henry Spencer. - * - * This code is derived from software contributed to Berkeley by - * Henry Spencer. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * 3. All advertising materials mentioning features or use of this software - * must display the following acknowledgement: - * This product includes software developed by the University of - * California, Berkeley and its contributors. - * 4. Neither the name of the University nor the names of its contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND - * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE - * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL - * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS - * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) - * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT - * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY - * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF - * SUCH DAMAGE. - * - * @(#)regfree.c 8.3 (Berkeley) 3/20/94 - */ - #include <sys/cdefs.h> -#if defined(LIBC_SCCS) && !defined(lint) #if 0 static char sccsid[] = "@(#)regfree.c 8.3 (Berkeley) 3/20/94"; -#else -__RCSID("$NetBSD: regfree.c,v 1.15 2007/02/09 23:44:18 junyoung Exp $"); +__FBSDID("$FreeBSD: head/lib/libc/regex/regfree.c 326025 2017-11-20 19:49:47Z pfg $"); #endif -#endif /* LIBC_SCCS and not lint */ +__RCSID("$NetBSD: regfree.c,v 1.16 2021/02/23 22:14:59 christos Exp $"); #include "namespace.h" #include <sys/types.h> - -#include <assert.h> #include <stdio.h> #include <stdlib.h> +#include <limits.h> #include <regex.h> #ifdef __weak_alias __weak_alias(regfree,_regfree) #endif +#include <wchar.h> +#include <wctype.h> #include "utils.h" #include "regex2.h" @@ -100,10 +65,10 @@ __weak_alias(regfree,_regfree) = extern void regfree(regex_t *); */ void -regfree( - regex_t *preg) +regfree(regex_t *preg) { struct re_guts *g; + unsigned int i; _DIAGASSERT(preg != NULL); @@ -118,12 +83,20 @@ regfree( g->magic = 0; /* mark it invalid */ if (g->strip != NULL) - free(g->strip); - if (g->sets != NULL) - free(g->sets); - if (g->setbits != NULL) - free(g->setbits); + free((char *)g->strip); + if (g->sets != NULL) { + for (i = 0; i < g->ncsets; i++) { + free(g->sets[i].ranges); + free(g->sets[i].wides); + free(g->sets[i].types); + } + free((char *)g->sets); + } if (g->must != NULL) free(g->must); - free(g); + if (g->charjump != NULL) + free(&g->charjump[CHAR_MIN]); + if (g->matchjump != NULL) + free(g->matchjump); + free((char *)g); } diff --git a/lib/libc/regex/utils.h b/lib/libc/regex/utils.h index 762caeeb697..0aedb653198 100644 --- a/lib/libc/regex/utils.h +++ b/lib/libc/regex/utils.h @@ -1,6 +1,9 @@ -/* $NetBSD: utils.h,v 1.6 2003/08/07 16:43:21 agc Exp $ */ +/* $NetBSD: utils.h,v 1.7 2021/02/23 22:14:59 christos Exp $ */ /*- + * SPDX-License-Identifier: BSD-3-Clause + * + * Copyright (c) 1992, 1993, 1994 Henry Spencer. * Copyright (c) 1992, 1993, 1994 * The Regents of the University of California. All rights reserved. * @@ -32,49 +35,15 @@ * SUCH DAMAGE. * * @(#)utils.h 8.3 (Berkeley) 3/20/94 - */ - -/*- - * Copyright (c) 1992, 1993, 1994 Henry Spencer. - * - * This code is derived from software contributed to Berkeley by - * Henry Spencer. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * 3. All advertising materials mentioning features or use of this software - * must display the following acknowledgement: - * This product includes software developed by the University of - * California, Berkeley and its contributors. - * 4. Neither the name of the University nor the names of its contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND - * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE - * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL - * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS - * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) - * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT - * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY - * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF - * SUCH DAMAGE. - * - * @(#)utils.h 8.3 (Berkeley) 3/20/94 + * $FreeBSD: head/lib/libc/regex/utils.h 341838 2018-12-12 04:23:00Z yuripv $ */ /* utility definitions */ #define DUPMAX _POSIX2_RE_DUP_MAX /* xxx is this right? */ #define INFINITY (DUPMAX + 1) -#define NC (CHAR_MAX - CHAR_MIN + 1) + +#define NC_MAX (CHAR_MAX - CHAR_MIN + 1) +#define NC ((MB_CUR_MAX) == 1 ? (NC_MAX) : (128)) typedef unsigned char uch; /* switch off assertions (if not already off) if no REDEBUG */ |
