libc/regex: Replace old regex library with modified TRE
authorJohn Marino <draco@marino.st>
Thu, 6 Aug 2015 21:26:49 +0000 (23:26 +0200)
committerJohn Marino <draco@marino.st>
Thu, 6 Aug 2015 22:07:33 +0000 (00:07 +0200)
The existing DragonFly REGEX library has several limitations, including
lack of wide character support and no collation ability due to its being
locked to POSIX/C locale.  It's also slow and doesn't pass a number of
tests of the AT&T Research Regex testsuite:

   basic       : TEST testregex, 539 tests,  0 errors
   categorize  : TEST testregex,  20 tests,  0 errors
   nullsubexpr : TEST testregex,  84 tests, 31 errors
   leftassoc   : TEST testregex,  12 tests, 12 errors
   rightassoc  : TEST testregex,  24 tests,  0 errors
   forcedassoc : TEST testregex,  48 tests,  8 errors
   repetition  : TEST testregex, 129 tests, 37 errors

Now it achieves these scores (elevated with new regnexec support):

   basic       : TEST testregex, 808 tests,  0 errors
   categorize  : TEST testregex,  26 tests,  0 errors
   nullsubexpr : TEST testregex, 172 tests,  0 errors
   leftassoc   : TEST testregex,  12 tests, 12 errors
   rightassoc  : TEST testregex,  36 tests,  0 errors
   forcedassoc : TEST testregex,  84 tests,  0 errors
   repetition  : TEST testregex, 241 tests,  0 errors

Here's proof that the regex library is now locale sensitive:

> env LANG=C sed /abandonn[a-z]/d fwl-sort-C.txt
a
abandonnâmes
abandonnât
abandonnâtes
abandonnèrent
abandonné
abandonnée
abandonnées
abandonnés
abord
abords
absence

> env LANG=fr_FR sed /abandonn[a-z]/d fwl-sort-C.txt
a
abord
abords
absence
accepta
acceptai
acceptaient
acceptais
acceptait
acceptant
acceptas
acceptasse

Several new functions have been added to to libc:

  variations of regcomp: regcomp_l,
    regncomp,  regncomp_l,
    regwcomp,  regwcomp_l,
    regnwcomp, regnwcomp_l

  variations of regexec: regnexec, regwexec, regwnexec

The regex.3 and re_format.7 map pages have been updated and symlinked
accordingly.

23 files changed:
include/Makefile
include/regex.h [deleted file]
lib/libc/Makefile.inc
lib/libc/regex/COPYRIGHT [deleted file]
lib/libc/regex/Makefile.inc [deleted file]
lib/libc/regex/Symbol.map [deleted file]
lib/libc/regex/WHATSNEW [deleted file]
lib/libc/regex/cname.h [deleted file]
lib/libc/regex/engine.c [deleted file]
lib/libc/regex/regcomp.c [deleted file]
lib/libc/regex/regerror.c [deleted file]
lib/libc/regex/regex2.h [deleted file]
lib/libc/regex/regexec.c [deleted file]
lib/libc/regex/regfree.c [deleted file]
lib/libc/regex/utils.h [deleted file]
lib/libc/tre-regex/Makefile.inc [new file with mode: 0644]
lib/libc/tre-regex/Symbol.map [new file with mode: 0644]
lib/libc/tre-regex/cname.h [new file with mode: 0644]
lib/libc/tre-regex/config.h [new file with mode: 0644]
lib/libc/tre-regex/re_format.7 [moved from lib/libc/regex/re_format.7 with 56% similarity]
lib/libc/tre-regex/regex.3 [moved from lib/libc/regex/regex.3 with 69% similarity]
lib/libc/tre-regex/regex.h [new file with mode: 0644]
lib/libc/tre-regex/tre.h [new file with mode: 0644]

index 26b2497..8a59409 100644 (file)
@@ -17,7 +17,7 @@ INCS= a.out.h ar.h assert.h bitstring.h cpio.h ctype.h db.h \
        mntopts.h mpool.h mqueue.h monetary.h ndbm.h netconfig.h \
        netdb.h nl_types.h nlist.h nss.h nsswitch.h objformat.h \
        paths.h printf.h pthread.h pthread_np.h pwd.h \
-       ranlib.h readpassphrase.h regex.h \
+       ranlib.h readpassphrase.h \
        res_update.h resolv.h re_comp.h rmd160.h \
        runetype.h search.h setjmp.h sgtty.h \
        signal.h spawn.h stab.h stdalign.h stdarg.h stdbool.h \
diff --git a/include/regex.h b/include/regex.h
deleted file mode 100644 (file)
index 366dde6..0000000
+++ /dev/null
@@ -1,120 +0,0 @@
-/*-
- * Copyright (c) 1992 Henry Spencer.
- * Copyright (c) 1992, 1993
- *     The Regents of the University of California.  All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Henry Spencer of the University of Toronto.
- *
- * 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.h     8.2 (Berkeley) 1/3/94
- * $FreeBSD: src/include/regex.h,v 1.11 2004/07/12 06:07:26 tjr Exp $
- */
-
-#ifndef _REGEX_H_
-#define        _REGEX_H_
-
-#include <sys/cdefs.h>
-#include <sys/types.h>
-
-/* types */
-typedef        __off_t         regoff_t;
-
-#ifndef _SIZE_T_DECLARED
-typedef        __size_t        size_t;
-#define        _SIZE_T_DECLARED
-#endif
-
-typedef struct {
-       int re_magic;
-       size_t re_nsub;         /* number of parenthesized subexpressions */
-       const char *re_endp;    /* end pointer for REG_PEND */
-       struct re_guts *re_g;   /* none of your business :-) */
-} regex_t;
-
-typedef struct {
-       regoff_t rm_so;         /* start of match */
-       regoff_t rm_eo;         /* end of match */
-} regmatch_t;
-
-/* regcomp() flags */
-#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
-
-/* regerror() flags */
-#define        REG_ENOSYS      (-1)
-#define        REG_NOMATCH      1
-#define        REG_BADPAT       2
-#define        REG_ECOLLATE     3
-#define        REG_ECTYPE       4
-#define        REG_EESCAPE      5
-#define        REG_ESUBREG      6
-#define        REG_EBRACK       7
-#define        REG_EPAREN       8
-#define        REG_EBRACE       9
-#define        REG_BADBR       10
-#define        REG_ERANGE      11
-#define        REG_ESPACE      12
-#define        REG_BADRPT      13
-#define        REG_EMPTY       14
-#define        REG_ASSERT      15
-#define        REG_INVARG      16
-#define        REG_ILLSEQ      17
-#define        REG_ATOI        255     /* convert name to number (!) */
-#define        REG_ITOA        0400    /* convert number to name (!) */
-
-/* regexec() flags */
-#define        REG_NOTBOL      00001
-#define        REG_NOTEOL      00002
-#define        REG_STARTEND    00004
-#define        REG_TRACE       00400   /* tracing of execution */
-#define        REG_LARGE       01000   /* force large representation */
-#define        REG_BACKR       02000   /* force use of backref code */
-
-__BEGIN_DECLS
-int    regcomp(regex_t * __restrict, const char * __restrict, int);
-size_t regerror(int, const regex_t * __restrict, char * __restrict, size_t);
-/*
- * XXX fourth parameter should be `regmatch_t [__restrict]', but isn't because
- * of a bug in GCC (when -std=c99 is specified) which perceives this as a
- * syntax error.
- */
-int    regexec(const regex_t * __restrict, const char * __restrict, size_t,
-               regmatch_t * __restrict, int);
-void   regfree(regex_t *);
-__END_DECLS
-
-#endif /* !_REGEX_H_ */
index fc05846..661336e 100644 (file)
@@ -26,7 +26,7 @@ WARNS=2
 .include "${.CURDIR}/../libc/locale/Makefile.inc"
 .include "${.CURDIR}/../libc/net/Makefile.inc"
 .include "${.CURDIR}/../libc/nls/Makefile.inc"
-.include "${.CURDIR}/../libc/regex/Makefile.inc"
+.include "${.CURDIR}/../libc/tre-regex/Makefile.inc"
 .include "${.CURDIR}/../libc/resolv/Makefile.inc"
 .include "${.CURDIR}/../libc/stdio/Makefile.inc"
 .include "${.CURDIR}/../libc/stdlib/Makefile.inc"
diff --git a/lib/libc/regex/COPYRIGHT b/lib/libc/regex/COPYRIGHT
deleted file mode 100644 (file)
index 574f6bc..0000000
+++ /dev/null
@@ -1,56 +0,0 @@
-Copyright 1992, 1993, 1994 Henry Spencer.  All rights reserved.
-This software is not subject to any license of the American Telephone
-and Telegraph Company or of the Regents of the University of California.
-
-Permission is granted to anyone to use this software for any purpose on
-any computer system, and to alter it and redistribute it, subject
-to the following restrictions:
-
-1. The author is not responsible for the consequences of use of this
-   software, no matter how awful, even if they arise from flaws in it.
-
-2. The origin of this software must not be misrepresented, either by
-   explicit claim or by omission.  Since few users ever read sources,
-   credits must appear in the documentation.
-
-3. Altered versions must be plainly marked as such, and must not be
-   misrepresented as being the original software.  Since few users
-   ever read sources, credits must appear in the documentation.
-
-4. This notice may not be removed or altered.
-
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
-/*-
- * Copyright (c) 1994
- *     The Regents of the University of California.  All rights reserved.
- *
- * 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.
- *
- *     @(#)COPYRIGHT   8.1 (Berkeley) 3/16/94
- */
diff --git a/lib/libc/regex/Makefile.inc b/lib/libc/regex/Makefile.inc
deleted file mode 100644 (file)
index e3859a9..0000000
+++ /dev/null
@@ -1,19 +0,0 @@
-#      from @(#)Makefile.inc   8.1 (Berkeley) 6/4/93
-# $FreeBSD: src/lib/libc/regex/Makefile.inc,v 1.5.2.1 2001/04/25 10:04:08 ru Exp $
-
-# regex sources
-.PATH: ${.CURDIR}/../libc/regex
-
-CMAPS+=        ${.CURDIR}/regex/Symbol.map
-
-CFLAGS+=-DPOSIX_MISTAKE
-
-SRCS+= regcomp.c regerror.c regexec.c regfree.c
-
-.if ${LIB} == "c"
-MAN+=  regex.3
-MAN+=  re_format.7
-
-MLINKS+=regex.3 regcomp.3 regex.3 regexec.3 regex.3 regerror.3
-MLINKS+=regex.3 regfree.3
-.endif
diff --git a/lib/libc/regex/Symbol.map b/lib/libc/regex/Symbol.map
deleted file mode 100644 (file)
index bc94387..0000000
+++ /dev/null
@@ -1,6 +0,0 @@
-DF402.0 {
-    regcomp;
-    regerror;
-    regexec;
-    regfree;
-};
diff --git a/lib/libc/regex/WHATSNEW b/lib/libc/regex/WHATSNEW
deleted file mode 100644 (file)
index f4301d3..0000000
+++ /dev/null
@@ -1,94 +0,0 @@
-# @(#)WHATSNEW 8.3 (Berkeley) 3/18/94
-
-New in alpha3.4:  The complex bug alluded to below has been fixed (in a
-slightly kludgey temporary way that may hurt efficiency a bit; this is
-another "get it out the door for 4.4" release).  The tests at the end of
-the tests file have accordingly been uncommented.  The primary sign of
-the bug was that something like a?b matching ab matched b rather than ab.
-(The bug was essentially specific to this exact situation, else it would
-have shown up earlier.)
-
-New in alpha3.3:  The definition of word boundaries has been altered
-slightly, to more closely match the usual programming notion that "_"
-is an alphabetic.  Stuff used for pre-ANSI systems is now in a subdir,
-and the makefile no longer alludes to it in mysterious ways.  The
-makefile has generally been cleaned up some.  Fixes have been made
-(again!) so that the regression test will run without -DREDEBUG, at
-the cost of weaker checking.  A workaround for a bug in some folks'
-<assert.h> has been added.  And some more things have been added to
-tests, including a couple right at the end which are commented out
-because the code currently flunks them (complex bug; fix coming).
-Plus the usual minor cleanup.
-
-New in alpha3.2:  Assorted bits of cleanup and portability improvement
-(the development base is now a BSDI system using GCC instead of an ancient
-Sun system, and the newer compiler exposed some glitches).  Fix for a
-serious bug that affected REs using many [] (including REG_ICASE REs
-because of the way they are implemented), *sometimes*, depending on
-memory-allocation patterns.  The header-file prototypes no longer name
-the parameters, avoiding possible name conflicts.  The possibility that
-some clot has defined CHAR_MIN as (say) `-128' instead of `(-128)' is
-now handled gracefully.  "uchar" is no longer used as an internal type
-name (too many people have the same idea).  Still the same old lousy
-performance, alas.
-
-New in alpha3.1:  Basically nothing, this release is just a bookkeeping
-convenience.  Stay tuned.
-
-New in alpha3.0:  Performance is no better, alas, but some fixes have been
-made and some functionality has been added.  (This is basically the "get
-it out the door in time for 4.4" release.)  One bug fix:  regfree() didn't
-free the main internal structure (how embarrassing).  It is now possible
-to put NULs in either the RE or the target string, using (resp.) a new
-REG_PEND flag and the old REG_STARTEND flag.  The REG_NOSPEC flag to
-regcomp() makes all characters ordinary, so you can match a literal
-string easily (this will become more useful when performance improves!).
-There are now primitives to match beginnings and ends of words, although
-the syntax is disgusting and so is the implementation.  The REG_ATOI
-debugging interface has changed a bit.  And there has been considerable
-internal cleanup of various kinds.
-
-New in alpha2.3:  Split change list out of README, and moved flags notes
-into Makefile.  Macro-ized the name of regex(7) in regex(3), since it has
-to change for 4.4BSD.  Cleanup work in engine.c, and some new regression
-tests to catch tricky cases thereof.
-
-New in alpha2.2:  Out-of-date manpages updated.  Regerror() acquires two
-small extensions -- REG_ITOA and REG_ATOI -- which avoid debugging kludges
-in my own test program and might be useful to others for similar purposes.
-The regression test will now compile (and run) without REDEBUG.  The
-BRE \$ bug is fixed.  Most uses of "uchar" are gone; it's all chars now.
-Char/uchar parameters are now written int/unsigned, to avoid possible
-portability problems with unpromoted parameters.  Some unsigned casts have
-been introduced to minimize portability problems with shifting into sign
-bits.
-
-New in alpha2.1:  Lots of little stuff, cleanup and fixes.  The one big
-thing is that regex.h is now generated, using mkh, rather than being
-supplied in the distribution; due to circularities in dependencies,
-you have to build regex.h explicitly by "make h".  The two known bugs
-have been fixed (and the regression test now checks for them), as has a
-problem with assertions not being suppressed in the absence of REDEBUG.
-No performance work yet.
-
-New in alpha2:  Backslash-anything is an ordinary character, not an
-error (except, of course, for the handful of backslashed metacharacters
-in BREs), which should reduce script breakage.  The regression test
-checks *where* null strings are supposed to match, and has generally
-been tightened up somewhat.  Small bug fixes in parameter passing (not
-harmful, but technically errors) and some other areas.  Debugging
-invoked by defining REDEBUG rather than not defining NDEBUG.
-
-New in alpha+3:  full prototyping for internal routines, using a little
-helper program, mkh, which extracts prototypes given in stylized comments.
-More minor cleanup.  Buglet fix:  it's CHAR_BIT, not CHAR_BITS.  Simple
-pre-screening of input when a literal string is known to be part of the
-RE; this does wonders for performance.
-
-New in alpha+2:  minor bits of cleanup.  Notably, the number "32" for the
-word width isn't hardwired into regexec.c any more, the public header
-file prototypes the functions if __STDC__ is defined, and some small typos
-in the manpages have been fixed.
-
-New in alpha+1:  improvements to the manual pages, and an important
-extension, the REG_STARTEND option to regexec().
diff --git a/lib/libc/regex/cname.h b/lib/libc/regex/cname.h
deleted file mode 100644 (file)
index 018728e..0000000
+++ /dev/null
@@ -1,139 +0,0 @@
-/*-
- * 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.
- * 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: src/lib/libc/regex/cname.h,v 1.4 2007/01/09 00:28:04 imp Exp $
- * $DragonFly: src/lib/libc/regex/cname.h,v 1.2 2005/04/27 11:26:18 joerg Exp $
- */
-
-/* character-name table */
-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}
-};
diff --git a/lib/libc/regex/engine.c b/lib/libc/regex/engine.c
deleted file mode 100644 (file)
index 7395411..0000000
+++ /dev/null
@@ -1,1186 +0,0 @@
-/*-
- * 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.
- *
- * $FreeBSD: head/lib/libc/regex/engine.c 279104 2015-02-21 15:02:27Z pfg $
- *
- *     @(#)engine.c    8.5 (Berkeley) 3/20/94
- */
-
-
-/*
- * The matching engine and friends.  This file is #included by regexec.c
- * after suitable #defines of a variety of macros used herein, so that
- * different state representations can be used without duplicating masses
- * of code.
- */
-
-#ifdef SNAMES
-#define        matcher smatcher
-#define        fast    sfast
-#define        slow    sslow
-#define        dissect sdissect
-#define        backref sbackref
-#define        step    sstep
-#define        print   sprint
-#define        at      sat
-#define        match   smat
-#endif
-#ifdef LNAMES
-#define        matcher lmatcher
-#define        fast    lfast
-#define        slow    lslow
-#define        dissect ldissect
-#define        backref lbackref
-#define        step    lstep
-#define        print   lprint
-#define        at      lat
-#define        match   lmat
-#endif
-#ifdef MNAMES
-#define        matcher mmatcher
-#define        fast    mfast
-#define        slow    mslow
-#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 */
-struct match {
-       struct re_guts *g;
-       int eflags;
-       regmatch_t *pmatch;     /* [nsub+1] (0 element unused) */
-       const char *offp;       /* offsets work from here */
-       const char *beginp;     /* start of string -- virtual NUL precedes */
-       const char *endp;       /* end of string -- virtual NUL here */
-       const char *coldp;      /* can be no match starting before here */
-       const char **lastpos;   /* [nplus+1] */
-       STATEVARS;
-       states st;              /* current states */
-       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 ========= */
-#ifdef __cplusplus
-extern "C" {
-#endif
-
-/* === 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, int);
-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, wint_t ch, states aft);
-#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        NONCHAR(c)      ((c) <= OUT)
-#ifdef REDEBUG
-static void print(struct match *m, const char *caption, states st, int ch, FILE *d);
-#endif
-#ifdef REDEBUG
-static void at(struct match *m, const char *title, const char *start, const char *stop, sopno startst, sopno stopst);
-#endif
-#ifdef REDEBUG
-static const char *pchar(int ch);
-#endif
-
-#ifdef __cplusplus
-}
-#endif
-/* ========= end header generated by ./mkh ========= */
-
-#ifdef REDEBUG
-#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&REG_TRACE) printf("=%s\n", (str)); }
-#else
-#define        SP(t, s, c)     /* nothing */
-#define        AT(t, p1, p2, s1, s2)   /* nothing */
-#define        NOTE(s) /* nothing */
-#endif
-
-/*
- - matcher - the actual matching engine
- == 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)
-{
-       const char *endp;
-       int i;
-       struct match mv;
-       struct match *m = &mv;
-       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;
-       int *matchjump;
-       int *charjump;
-
-       /* simplify the situation where possible */
-       if (g->cflags&REG_NOSUB)
-               nmatch = 0;
-       if (eflags&REG_STARTEND) {
-               start = string + pmatch[0].rm_so;
-               stop = string + pmatch[0].rm_eo;
-       } else {
-               start = string;
-               stop = start + strlen(start);
-       }
-       if (stop < start)
-               return(REG_INVARG);
-
-       /* prescreening; this does wonders for this rather slow code */
-       if (g->must != NULL) {
-               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] &&
-                                   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 */
-       m->g = g;
-       m->eflags = eflags;
-       m->pmatch = NULL;
-       m->lastpos = NULL;
-       m->offp = string;
-       m->beginp = start;
-       m->endp = stop;
-       STATESETUP(m, 4);
-       SETUP(m->st);
-       SETUP(m->fresh);
-       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)
-               start = ((dp - g->moffset) < start) ? start : dp - g->moffset;
-
-       SP("mloop", m->st, *start);
-
-       /* this loop does only one repetition except for backrefs */
-       for (;;) {
-               endp = fast(m, start, stop, gf, gl);
-               if (endp == NULL) {             /* a miss */
-                       if (m->pmatch != NULL)
-                               free((char *)m->pmatch);
-                       if (m->lastpos != NULL)
-                               free((char *)m->lastpos);
-                       STATETEARDOWN(m);
-                       return(REG_NOMATCH);
-               }
-               if (nmatch == 0 && !g->backrefs)
-                       break;          /* no further info needed */
-
-               /* where? */
-               assert(m->coldp != NULL);
-               for (;;) {
-                       NOTE("finding start");
-                       endp = slow(m, m->coldp, stop, gf, gl);
-                       if (endp != NULL)
-                               break;
-                       assert(m->coldp < m->endp);
-                       m->coldp += XMBRTOWC(NULL, m->coldp,
-                           m->endp - m->coldp, &m->mbs, 0);
-               }
-               if (nmatch == 1 && !g->backrefs)
-                       break;          /* no further info needed */
-
-               /* oh my, he wants the subexpressions... */
-               if (m->pmatch == NULL)
-                       m->pmatch = (regmatch_t *)malloc((m->g->nsub + 1) *
-                                                       sizeof(regmatch_t));
-               if (m->pmatch == NULL) {
-                       STATETEARDOWN(m);
-                       return(REG_ESPACE);
-               }
-               for (i = 1; i <= m->g->nsub; i++)
-                       m->pmatch[i].rm_so = m->pmatch[i].rm_eo = -1;
-               if (!g->backrefs && !(m->eflags&REG_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 *));
-                       if (g->nplus > 0 && m->lastpos == NULL) {
-                               free(m->pmatch);
-                               STATETEARDOWN(m);
-                               return(REG_ESPACE);
-                       }
-                       NOTE("backref dissect");
-                       dp = backref(m, m->coldp, endp, gf, gl, (sopno)0, 0);
-               }
-               if (dp != NULL)
-                       break;
-
-               /* uh-oh... we couldn't find a subexpression-level match */
-               assert(g->backrefs);    /* must be back references doing it */
-               assert(g->nplus == 0 || m->lastpos != NULL);
-               for (;;) {
-                       if (dp != NULL || endp <= m->coldp)
-                               break;          /* defeat */
-                       NOTE("backoff");
-                       endp = slow(m, m->coldp, endp-1, gf, gl);
-                       if (endp == NULL)
-                               break;          /* defeat */
-                       /* try it on a shorter possibility */
-#ifndef NDEBUG
-                       for (i = 1; i <= m->g->nsub; i++) {
-                               assert(m->pmatch[i].rm_so == -1);
-                               assert(m->pmatch[i].rm_eo == -1);
-                       }
-#endif
-                       NOTE("backoff dissect");
-                       dp = backref(m, m->coldp, endp, gf, gl, (sopno)0, 0);
-               }
-               assert(dp == NULL || dp == endp);
-               if (dp != NULL)         /* found a shorter one */
-                       break;
-
-               /* despite initial appearances, there is no match here */
-               NOTE("false alarm");
-               /* recycle starting later */
-               start = m->coldp + XMBRTOWC(NULL, m->coldp,
-                   stop - m->coldp, &m->mbs, 0);
-               assert(start <= stop);
-       }
-
-       /* fill in the details if requested */
-       if (nmatch > 0) {
-               pmatch[0].rm_so = m->coldp - m->offp;
-               pmatch[0].rm_eo = endp - m->offp;
-       }
-       if (nmatch > 1) {
-               assert(m->pmatch != NULL);
-               for (i = 1; i < nmatch; i++)
-                       if (i <= m->g->nsub)
-                               pmatch[i] = m->pmatch[i];
-                       else {
-                               pmatch[i].rm_so = -1;
-                               pmatch[i].rm_eo = -1;
-                       }
-       }
-
-       if (m->pmatch != NULL)
-               free((char *)m->pmatch);
-       if (m->lastpos != NULL)
-               free((char *)m->lastpos);
-       STATETEARDOWN(m);
-       return(0);
-}
-
-/*
- - dissect - figure out what matched what, no back references
- == static const char *dissect(struct match *m, const char *start, \
- ==    const char *stop, sopno startst, sopno stopst);
- */
-static const char *            /* == stop (success) always */
-dissect(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 */
-       const char *dp __unused; /* actually used for assert checks */
-
-       AT("diss", start, stop, startst, stopst);
-       sp = start;
-       for (ss = startst; ss < stopst; ss = es) {
-               /* identify end of subRE */
-               es = ss;
-               switch (OP(m->g->strip[es])) {
-               case OPLUS_:
-               case OQUEST_:
-                       es += OPND(m->g->strip[es]);
-                       break;
-               case OCH_:
-                       while (OP(m->g->strip[es]) != O_CH)
-                               es += OPND(m->g->strip[es]);
-                       break;
-               }
-               es++;
-
-               /* figure out what it matched */
-               switch (OP(m->g->strip[ss])) {
-               case OEND:
-                       assert(nope);
-                       break;
-               case OCHAR:
-                       sp += XMBRTOWC(NULL, sp, stop - start, &m->mbs, 0);
-                       break;
-               case OBOL:
-               case OEOL:
-               case OBOW:
-               case OEOW:
-                       break;
-               case OANY:
-               case OANYOF:
-                       sp += XMBRTOWC(NULL, sp, stop - start, &m->mbs, 0);
-                       break;
-               case OBACK_:
-               case O_BACK:
-                       assert(nope);
-                       break;
-               /* cases where length of match is hard to find */
-               case OQUEST_:
-                       stp = stop;
-                       for (;;) {
-                               /* how long could this one be? */
-                               rest = slow(m, sp, stp, ss, es);
-                               assert(rest != NULL);   /* it did match */
-                               /* could the rest match the rest? */
-                               tail = slow(m, rest, stop, es, stopst);
-                               if (tail == stop)
-                                       break;          /* yes! */
-                               /* no -- try a shorter match for this one */
-                               stp = rest - 1;
-                               assert(stp >= sp);      /* it did work */
-                       }
-                       ssub = ss + 1;
-                       esub = es - 1;
-                       /* did innards match? */
-                       if (slow(m, sp, rest, ssub, esub) != NULL) {
-                               dp = dissect(m, sp, rest, ssub, esub);
-                               assert(dp == rest);
-                       } else          /* no */
-                               assert(sp == rest);
-                       sp = rest;
-                       break;
-               case OPLUS_:
-                       stp = stop;
-                       for (;;) {
-                               /* how long could this one be? */
-                               rest = slow(m, sp, stp, ss, es);
-                               assert(rest != NULL);   /* it did match */
-                               /* could the rest match the rest? */
-                               tail = slow(m, rest, stop, es, stopst);
-                               if (tail == stop)
-                                       break;          /* yes! */
-                               /* no -- try a shorter match for this one */
-                               stp = rest - 1;
-                               assert(stp >= sp);      /* it did work */
-                       }
-                       ssub = ss + 1;
-                       esub = es - 1;
-                       ssp = sp;
-                       oldssp = ssp;
-                       for (;;) {      /* find last match of innards */
-                               sep = slow(m, ssp, rest, ssub, esub);
-                               if (sep == NULL || sep == ssp)
-                                       break;  /* failed or matched null */
-                               oldssp = ssp;   /* on to next try */
-                               ssp = sep;
-                       }
-                       if (sep == NULL) {
-                               /* last successful match */
-                               sep = ssp;
-                               ssp = oldssp;
-                       }
-                       assert(sep == rest);    /* must exhaust substring */
-                       assert(slow(m, ssp, sep, ssub, esub) == rest);
-                       dp = dissect(m, ssp, sep, ssub, esub);
-                       assert(dp == sep);
-                       sp = rest;
-                       break;
-               case OCH_:
-                       stp = stop;
-                       for (;;) {
-                               /* how long could this one be? */
-                               rest = slow(m, sp, stp, ss, es);
-                               assert(rest != NULL);   /* it did match */
-                               /* could the rest match the rest? */
-                               tail = slow(m, rest, stop, es, stopst);
-                               if (tail == stop)
-                                       break;          /* yes! */
-                               /* no -- try a shorter match for this one */
-                               stp = rest - 1;
-                               assert(stp >= sp);      /* it did work */
-                       }
-                       ssub = ss + 1;
-                       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)
-                                       break;  /* it matched all of it */
-                               /* that one missed, try next one */
-                               assert(OP(m->g->strip[esub]) == OOR1);
-                               esub++;
-                               assert(OP(m->g->strip[esub]) == OOR2);
-                               ssub = esub + 1;
-                               esub += OPND(m->g->strip[esub]);
-                               if (OP(m->g->strip[esub]) == OOR2)
-                                       esub--;
-                               else
-                                       assert(OP(m->g->strip[esub]) == O_CH);
-                       }
-                       dp = dissect(m, sp, rest, ssub, esub);
-                       assert(dp == rest);
-                       sp = rest;
-                       break;
-               case O_PLUS:
-               case O_QUEST:
-               case OOR1:
-               case OOR2:
-               case O_CH:
-                       assert(nope);
-                       break;
-               case OLPAREN:
-                       i = OPND(m->g->strip[ss]);
-                       assert(0 < i && i <= m->g->nsub);
-                       m->pmatch[i].rm_so = sp - m->offp;
-                       break;
-               case ORPAREN:
-                       i = OPND(m->g->strip[ss]);
-                       assert(0 < i && i <= m->g->nsub);
-                       m->pmatch[i].rm_eo = sp - m->offp;
-                       break;
-               default:                /* uh oh */
-                       assert(nope);
-                       break;
-               }
-       }
-
-       assert(sp == stop);
-       return(sp);
-}
-
-/*
- - backref - figure out what matched what, figuring in back references
- == static const char *backref(struct match *m, const char *start, \
- ==    const char *stop, sopno startst, sopno stopst, sopno lev);
- */
-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 */
-       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 */
-       const char *dp;
-       size_t len;
-       int hard;
-       sop s;
-       regoff_t offsave;
-       cset *cs;
-       wint_t wc;
-
-       AT("back", start, stop, startst, stopst);
-       sp = start;
-
-       /* get as far as we can with easy stuff */
-       hard = 0;
-       for (ss = startst; !hard && ss < stopst; ss++)
-               switch (OP(s = m->g->strip[ss])) {
-               case OCHAR:
-                       if (sp == stop)
-                               return(NULL);
-                       sp += XMBRTOWC(&wc, sp, stop - sp, &m->mbs, BADCHAR);
-                       if (wc != OPND(s))
-                               return(NULL);
-                       break;
-               case OANY:
-                       if (sp == stop)
-                               return(NULL);
-                       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)];
-                       sp += XMBRTOWC(&wc, sp, stop - sp, &m->mbs, BADCHAR);
-                       if (wc == BADCHAR || !CHIN(cs, wc))
-                               return(NULL);
-                       break;
-               case OBOL:
-                       if ( (sp == m->beginp && !(m->eflags&REG_NOTBOL)) ||
-                                       (sp < m->endp && *(sp-1) == '\n' &&
-                                               (m->g->cflags&REG_NEWLINE)) )
-                               { /* yes */ }
-                       else
-                               return(NULL);
-                       break;
-               case OEOL:
-                       if ( (sp == m->endp && !(m->eflags&REG_NOTEOL)) ||
-                                       (sp < m->endp && *sp == '\n' &&
-                                               (m->g->cflags&REG_NEWLINE)) )
-                               { /* yes */ }
-                       else
-                               return(NULL);
-                       break;
-               case OBOW:
-                       if (( (sp == m->beginp && !(m->eflags&REG_NOTBOL)) ||
-                                       (sp < m->endp && *(sp-1) == '\n' &&
-                                               (m->g->cflags&REG_NEWLINE)) ||
-                                       (sp > m->beginp &&
-                                                       !ISWORD(*(sp-1))) ) &&
-                                       (sp < m->endp && ISWORD(*sp)) )
-                               { /* yes */ }
-                       else
-                               return(NULL);
-                       break;
-               case OEOW:
-                       if (( (sp == m->endp && !(m->eflags&REG_NOTEOL)) ||
-                                       (sp < m->endp && *sp == '\n' &&
-                                               (m->g->cflags&REG_NEWLINE)) ||
-                                       (sp < m->endp && !ISWORD(*sp)) ) &&
-                                       (sp > m->beginp && ISWORD(*(sp-1))) )
-                               { /* yes */ }
-                       else
-                               return(NULL);
-                       break;
-               case O_QUEST:
-                       break;
-               case OOR1:      /* matches null but needs to skip */
-                       ss++;
-                       s = m->g->strip[ss];
-                       do {
-                               assert(OP(s) == OOR2);
-                               ss += OPND(s);
-                       } while (OP(s = m->g->strip[ss]) != O_CH);
-                       /* note that the ss++ gets us past the O_CH */
-                       break;
-               default:        /* have to make a choice */
-                       hard = 1;
-                       break;
-               }
-       if (!hard) {            /* that was it! */
-               if (sp != stop)
-                       return(NULL);
-               return(sp);
-       }
-       ss--;                   /* adjust for the for's final increment */
-
-       /* the hard stuff */
-       AT("hard", sp, stop, ss, stopst);
-       s = m->g->strip[ss];
-       switch (OP(s)) {
-       case OBACK_:            /* the vilest depths */
-               i = OPND(s);
-               assert(0 < i && i <= m->g->nsub);
-               if (m->pmatch[i].rm_eo == -1)
-                       return(NULL);
-               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 + m->pmatch[i].rm_so;
-               if (memcmp(sp, ssp, len) != 0)
-                       return(NULL);
-               while (m->g->strip[ss] != SOP(O_BACK, i))
-                       ss++;
-               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, rec);
-               if (dp != NULL)
-                       return(dp);     /* not */
-               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, rec));
-       case O_PLUS:
-               if (sp == m->lastpos[lev])      /* last pass matched null */
-                       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, rec);
-               if (dp == NULL)
-                       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, rec);
-                       if (dp != NULL)
-                               return(dp);
-                       /* that one missed, try next one */
-                       if (OP(m->g->strip[esub]) == O_CH)
-                               return(NULL);   /* there is none */
-                       esub++;
-                       assert(OP(m->g->strip[esub]) == OOR2);
-                       ssub = esub + 1;
-                       esub += OPND(m->g->strip[esub]);
-                       if (OP(m->g->strip[esub]) == 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, 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, rec);
-               if (dp != NULL)
-                       return(dp);
-               m->pmatch[i].rm_eo = offsave;
-               return(NULL);
-       default:                /* uh oh */
-               assert(nope);
-               break;
-       }
-
-       /* "can't happen" */
-       assert(nope);
-       /* NOTREACHED */
-       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);
- */
-static const char *            /* where tentative match ended, or NULL */
-fast(  struct match *m,
-       const char *start,
-       const char *stop,
-       sopno startst,
-       sopno stopst)
-{
-       states st = m->st;
-       states fresh = m->fresh;
-       states tmp = m->tmp;
-       const char *p = start;
-       wint_t c;
-       wint_t lastc;           /* previous c */
-       wint_t flagch;
-       int i;
-       const char *coldp;      /* last p after which no match was underway */
-       size_t clen;
-
-       CLEAR(st);
-       SET1(st, startst);
-       SP("fast", st, *p);
-       st = step(m->g, startst, stopst, st, NOTHING, st);
-       ASSIGN(fresh, st);
-       SP("start", st, *p);
-       coldp = NULL;
-       if (start == m->beginp)
-               c = OUT;
-       else {
-               /*
-                * XXX Wrong if the previous character was multi-byte.
-                * Newline never is (in supported encodings),
-                * so this only breaks the ISWORD tests below.
-                */
-               c = (uch)*(start - 1);
-       }
-       for (;;) {
-               /* next character */
-               lastc = c;
-               if (p == m->endp) {
-                       clen = 0;
-                       c = OUT;
-               } else
-                       clen = XMBRTOWC(&c, p, m->endp - p, &m->mbs, BADCHAR);
-               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&REG_NEWLINE) ||
-                               (lastc == OUT && !(m->eflags&REG_NOTBOL)) ) {
-                       flagch = BOL;
-                       i = m->g->nbol;
-               }
-               if ( (c == '\n' && m->g->cflags&REG_NEWLINE) ||
-                               (c == OUT && !(m->eflags&REG_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 || clen > stop - p)
-                       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 += clen;
-       }
-
-       assert(coldp != NULL);
-       m->coldp = coldp;
-       if (ISSET(st, stopst))
-               return(p+XMBRTOWC(NULL, p, stop - p, &m->mbs, 0));
-       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;
-       wint_t c;
-       wint_t lastc;           /* previous c */
-       wint_t flagch;
-       int i;
-       const char *matchp;     /* last p at which a match ended */
-       size_t clen;
-
-       AT("slow", start, stop, startst, stopst);
-       CLEAR(st);
-       SET1(st, startst);
-       SP("sstart", st, *p);
-       st = step(m->g, startst, stopst, st, NOTHING, st);
-       matchp = NULL;
-       if (start == m->beginp)
-               c = OUT;
-       else {
-               /*
-                * XXX Wrong if the previous character was multi-byte.
-                * Newline never is (in supported encodings),
-                * so this only breaks the ISWORD tests below.
-                */
-               c = (uch)*(start - 1);
-       }
-       for (;;) {
-               /* next character */
-               lastc = c;
-               if (p == m->endp) {
-                       c = OUT;
-                       clen = 0;
-               } else
-                       clen = XMBRTOWC(&c, p, m->endp - p, &m->mbs, BADCHAR);
-
-               /* is there an EOL and/or BOL between lastc and c? */
-               flagch = '\0';
-               i = 0;
-               if ( (lastc == '\n' && m->g->cflags&REG_NEWLINE) ||
-                               (lastc == OUT && !(m->eflags&REG_NOTBOL)) ) {
-                       flagch = BOL;
-                       i = m->g->nbol;
-               }
-               if ( (c == '\n' && m->g->cflags&REG_NEWLINE) ||
-                               (c == OUT && !(m->eflags&REG_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("sboleol", 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("sboweow", st, c);
-               }
-
-               /* are we done? */
-               if (ISSET(st, stopst))
-                       matchp = p;
-               if (EQ(st, empty) || p == stop || clen > stop - p)
-                       break;          /* NOTE BREAK OUT */
-
-               /* no, we must deal with this character */
-               ASSIGN(tmp, st);
-               ASSIGN(st, empty);
-               assert(c != OUT);
-               st = step(m->g, startst, stopst, tmp, c, st);
-               SP("saft", st, c);
-               assert(EQ(step(m->g, startst, stopst, st, NOTHING, st), st));
-               p += clen;
-       }
-
-       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    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 */
-       wint_t ch,              /* character or NONCHAR code */
-       states aft)             /* states already known reachable after */
-{
-       cset *cs;
-       sop s;
-       sopno pc;
-       onestate here;          /* note, macros know this name */
-       sopno look;
-       int i;
-
-       for (pc = start, INIT(here, pc); pc != stop; pc++, INC(here)) {
-               s = g->strip[pc];
-               switch (OP(s)) {
-               case OEND:
-                       assert(pc == stop-1);
-                       break;
-               case OCHAR:
-                       /* only characters can match */
-                       assert(!NONCHAR(ch) || ch != OPND(s));
-                       if (ch == OPND(s))
-                               FWD(aft, bef, 1);
-                       break;
-               case OBOL:
-                       if (ch == BOL || ch == BOLEOL)
-                               FWD(aft, bef, 1);
-                       break;
-               case OEOL:
-                       if (ch == EOL || ch == BOLEOL)
-                               FWD(aft, bef, 1);
-                       break;
-               case OBOW:
-                       if (ch == BOW)
-                               FWD(aft, bef, 1);
-                       break;
-               case OEOW:
-                       if (ch == EOW)
-                               FWD(aft, bef, 1);
-                       break;
-               case OANY:
-                       if (!NONCHAR(ch))
-                               FWD(aft, bef, 1);
-                       break;
-               case OANYOF:
-                       cs = &g->sets[OPND(s)];
-                       if (!NONCHAR(ch) && CHIN(cs, ch))
-                               FWD(aft, bef, 1);
-                       break;
-               case OBACK_:            /* ignored here */
-               case O_BACK:
-                       FWD(aft, aft, 1);
-                       break;
-               case OPLUS_:            /* forward, this is just an empty */
-                       FWD(aft, aft, 1);
-                       break;
-               case O_PLUS:            /* both forward and back */
-                       FWD(aft, aft, 1);
-                       i = ISSETBACK(aft, OPND(s));
-                       BACK(aft, aft, OPND(s));
-                       if (!i && ISSETBACK(aft, OPND(s))) {
-                               /* oho, must reconsider loop body */
-                               pc -= OPND(s) + 1;
-                               INIT(here, pc);
-                       }
-                       break;
-               case OQUEST_:           /* two branches, both forward */
-                       FWD(aft, aft, 1);
-                       FWD(aft, aft, OPND(s));
-                       break;
-               case O_QUEST:           /* just an empty */
-                       FWD(aft, aft, 1);
-                       break;
-               case OLPAREN:           /* not significant here */
-               case ORPAREN:
-                       FWD(aft, aft, 1);
-                       break;
-               case OCH_:              /* mark the first two branches */
-                       FWD(aft, aft, 1);
-                       assert(OP(g->strip[pc+OPND(s)]) == 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 + 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);
-                               FWD(aft, aft, OPND(s));
-                       }
-                       break;
-               case O_CH:              /* just empty */
-                       FWD(aft, aft, 1);
-                       break;
-               default:                /* ooooops... */
-                       assert(nope);
-                       break;
-               }
-       }
-
-       return(aft);
-}
-
-#ifdef REDEBUG
-/*
- - print - print a set of states
- == #ifdef REDEBUG
- == static void print(struct match *m, const char *caption, states st, \
- ==    int ch, FILE *d);
- == #endif
- */
-static void
-print(struct match *m,
-       const char *caption,
-       states st,
-       int ch,
-       FILE *d)
-{
-       struct re_guts *g = m->g;
-       int i;
-       int first = 1;
-
-       if (!(m->eflags&REG_TRACE))
-               return;
-
-       fprintf(d, "%s", caption);
-       if (ch != '\0')
-               fprintf(d, " %s", pchar(ch));
-       for (i = 0; i < g->nstates; i++)
-               if (ISSET(st, i)) {
-                       fprintf(d, "%s%d", (first) ? "\t" : ", ", i);
-                       first = 0;
-               }
-       fprintf(d, "\n");
-}
-
-/*
- - at - print current situation
- == #ifdef REDEBUG
- == 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,
-       const char *title,
-       const char *start,
-       const char *stop,
-       sopno startst,
-       sopno stopst)
-{
-       if (!(m->eflags&REG_TRACE))
-               return;
-
-       printf("%s %s-", title, pchar(*start));
-       printf("%s ", pchar(*stop));
-       printf("%ld-%ld\n", (long)startst, (long)stopst);
-}
-
-#ifndef PCHARDONE
-#define        PCHARDONE       /* never again */
-/*
- - pchar - make a character printable
- == #ifdef REDEBUG
- == static const char *pchar(int ch);
- == #endif
- *
- * Is this identical to regchar() over in debug.c?  Well, yes.  But a
- * duplicate here avoids having a debugging-capable regexec.o tied to
- * a matching debug.o, and this is convenient.  It all disappears in
- * the non-debug compilation anyway, so it doesn't matter much.
- */
-static const char *            /* -> representation */
-pchar(int ch)
-{
-       static char pbuf[10];
-
-       if (isprint((uch)ch) || ch == ' ')
-               sprintf(pbuf, "%c", ch);
-       else
-               sprintf(pbuf, "\\%o", ch);
-       return(pbuf);
-}
-#endif
-#endif
-
-#undef matcher
-#undef fast
-#undef slow
-#undef dissect
-#undef backref
-#undef step
-#undef print
-#undef at
-#undef match
diff --git a/lib/libc/regex/regcomp.c b/lib/libc/regex/regcomp.c
deleted file mode 100644 (file)
index 223b989..0000000
+++ /dev/null
@@ -1,1823 +0,0 @@
-/*-
- * Copyright (c) 1992, 1993, 1994 Henry Spencer.
- * Copyright (c) 1992, 1993, 1994
- *     The Regents of the University of California.  All rights reserved.
- *
- * 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.
- *
- * 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
- * $FreeBSD: head/lib/libc/regex/regcomp.c 281858 2015-04-22 17:09:02Z pfg $
- *
- *     @(#)regcomp.c   8.5 (Berkeley) 3/20/94
- */
-
-/*
- * This implementation currently only works with C locale
- * It's definitely limited by UCHAR_MAX, but not even ISO-8859 charsets
- * are working.  The forced changing of locale to C for the comparison
- * is considered a workaround until a better solution is found.
- */
-
-#include <sys/types.h>
-#include <stdio.h>
-#include <string.h>
-#include <ctype.h>
-#include <limits.h>
-#include <stdlib.h>
-#include <regex.h>
-#include <runetype.h>
-#include <wchar.h>
-#include <wctype.h>
-
-#include "collate.h"
-
-#include "utils.h"
-#include "regex2.h"
-
-#include "cname.h"
-
-/*
- * parse structure, passed up and down to avoid global variables and
- * other clumsinesses
- */
-struct parse {
-       char *next;             /* next character in RE */
-       char *end;              /* end of string (-> NUL normally) */
-       int error;              /* has an error been seen? */
-       sop *strip;             /* malloced strip */
-       sopno ssize;            /* malloced strip size (allocated) */
-       sopno slen;             /* malloced strip length (used) */
-       int ncsalloc;           /* number of csets allocated */
-       struct re_guts *g;
-#      define  NPAREN  10      /* we need to remember () 1-9 for back refs */
-       sopno pbegin[NPAREN];   /* -> ( ([0] unused) */
-       sopno pend[NPAREN];     /* -> ) ([0] unused) */
-};
-
-/* ========= begin header generated by ./mkh ========= */
-#ifdef __cplusplus
-extern "C" {
-#endif
-
-/* === regcomp.c === */
-static void p_ere(struct parse *p, int stop);
-static void p_ere_exp(struct parse *p);
-static void p_str(struct parse *p);
-static void p_bre(struct parse *p, int end1, int end2);
-static int p_simp_re(struct parse *p, int starordinary);
-static int p_count(struct parse *p);
-static void p_bracket(struct parse *p);
-static void p_b_term(struct parse *p, cset *cs);
-static void p_b_cclass(struct parse *p, cset *cs);
-static void p_b_eclass(struct parse *p, cset *cs);
-static wint_t p_b_symbol(struct parse *p);
-static wint_t p_b_coll_elem(struct parse *p, wint_t endc);
-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);
-static int seterr(struct parse *p, int e);
-static cset *allocset(struct parse *p);
-static void freeset(struct parse *p, cset *cs);
-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, 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
-}
-#endif
-/* ========= end header generated by ./mkh ========= */
-
-static char nuls[10];          /* place to point scanner in event of error */
-
-/*
- * macros for use with parse structure
- * BEWARE:  these know that the parse structure is named `p' !!!
- */
-#define        PEEK()  (*p->next)
-#define        PEEK2() (*(p->next+1))
-#define        MORE()  (p->next < p->end)
-#define        MORE2() (p->next+1 < p->end)
-#define        SEE(c)  (MORE() && PEEK() == (c))
-#define        SEETWO(a, b)    (MORE() && MORE2() && PEEK() == (a) && PEEK2() == (b))
-#define        EAT(c)  ((SEE(c)) ? (NEXT(), 1) : 0)
-#define        EATTWO(a, b)    ((SEETWO(a, b)) ? (NEXT2(), 1) : 0)
-#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)  ((co) || SETERROR(e))
-#define        MUSTSEE(c, e)   (REQUIRE(MORE() && PEEK() == (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), (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)
-#define        HERE()          (p->slen)
-#define        THERE()         (p->slen - 1)
-#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
-
-/* 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 * __restrict preg,
-       const char * __restrict pattern,
-       int cflags)
-{
-       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
-#      define  GOODFLAGS(f)    ((f)&~REG_DUMP)
-#endif
-
-       cflags = GOODFLAGS(cflags);
-       if ((cflags&REG_EXTENDED) && (cflags&REG_NOSPEC))
-               return(REG_INVARG);
-
-       if (cflags&REG_PEND) {
-               if (preg->re_endp < pattern)
-                       return(REG_INVARG);
-               len = preg->re_endp - pattern;
-       } else
-               len = strlen((char *)pattern);
-
-       /* do the mallocs early so failure handling is easy */
-       g = (struct re_guts *)malloc(sizeof(struct re_guts));
-       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 */
-       assert(p->ssize >= len);
-
-       p->strip = (sop *)malloc(p->ssize * sizeof(sop));
-       p->slen = 0;
-       if (p->strip == NULL) {
-               free((char *)g);
-               return(REG_ESPACE);
-       }
-
-       /* set things up */
-       p->g = g;
-       p->next = (char *)pattern;      /* convenience; we do not modify it */
-       p->end = p->next + len;
-       p->error = 0;
-       p->ncsalloc = 0;
-       for (i = 0; i < NPAREN; i++) {
-               p->pbegin[i] = 0;
-               p->pend[i] = 0;
-       }
-       g->sets = 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->backrefs = 0;
-
-       /* do it */
-       EMIT(OEND, 0);
-       g->firststate = THERE();
-       if (cflags&REG_EXTENDED)
-               p_ere(p, OUT);
-       else if (cflags&REG_NOSPEC)
-               p_str(p);
-       else
-               p_bre(p, OUT, OUT);
-       EMIT(OEND, 0);
-       g->laststate = THERE();
-
-       /* tidy up loose ends and fill things in */
-       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;
-       preg->re_g = g;
-       preg->re_magic = MAGIC1;
-#ifndef REDEBUG
-       /* not debugging, so can't rely on the assert() in regexec() */
-       if (g->iflags&BAD)
-               SETERROR(REG_ASSERT);
-#endif
-
-       /* win or lose, we're done */
-       if (p->error != 0)      /* lose */
-               regfree(preg);
-       return(p->error);
-}
-
-/*
- - p_ere - ERE parser top level, concatenation and alternation
- == static void p_ere(struct parse *p, int_t stop);
- */
-static void
-p_ere(struct parse *p,
-       int stop)               /* character this ERE should end at */
-{
-       char c;
-       sopno prevback;
-       sopno prevfwd;
-       sopno conc;
-       int first = 1;          /* is this the first alternative? */
-
-       for (;;) {
-               /* do a bunch of concatenated expressions */
-               conc = HERE();
-               while (MORE() && (c = PEEK()) != '|' && c != stop)
-                       p_ere_exp(p);
-               (void)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));
-}
-
-/*
- - p_ere_exp - parse one subERE, an atom possibly followed by a repetition op
- == static void p_ere_exp(struct parse *p);
- */
-static void
-p_ere_exp(struct parse *p)
-{
-       char c;
-       wint_t wc;
-       sopno pos;
-       int count;
-       int count2;
-       sopno subno;
-       int wascaret = 0;
-
-       assert(MORE());         /* caller should have ensured this */
-       c = GETNEXT();
-
-       pos = HERE();
-       switch (c) {
-       case '(':
-               (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, ')');
-               if (subno < NPAREN) {
-                       p->pend[subno] = HERE();
-                       assert(p->pend[subno] != 0);
-               }
-               EMIT(ORPAREN, subno);
-               (void)MUSTEAT(')', REG_EPAREN);
-               break;
-#ifndef POSIX_MISTAKE
-       case ')':               /* happens only if no current unmatched ( */
-               /*
-                * You may ask, why the ifndef?  Because I didn't notice
-                * this until slightly too late for 1003.2, and none of the
-                * other 1003.2 regular-expression reviewers noticed it at
-                * all.  So an unmatched ) is legal POSIX, at least until
-                * we can get it fixed.
-                */
-               SETERROR(REG_EPAREN);
-               break;
-#endif
-       case '^':
-               EMIT(OBOL, 0);
-               p->g->iflags |= USEBOL;
-               p->g->nbol++;
-               wascaret = 1;
-               break;
-       case '$':
-               EMIT(OEOL, 0);
-               p->g->iflags |= USEEOL;
-               p->g->neol++;
-               break;
-       case '|':
-               SETERROR(REG_EMPTY);
-               break;
-       case '*':
-       case '+':
-       case '?':
-               SETERROR(REG_BADRPT);
-               break;
-       case '.':
-               if (p->g->cflags&REG_NEWLINE)
-                       nonnewline(p);
-               else
-                       EMIT(OANY, 0);
-               break;
-       case '[':
-               p_bracket(p);
-               break;
-       case '\\':
-               (void)REQUIRE(MORE(), REG_EESCAPE);
-               wc = WGETNEXT();
-               switch (wc) {
-               case '<':
-                       EMIT(OBOW, 0);
-                       break;
-               case '>':
-                       EMIT(OEOW, 0);
-                       break;
-               default:
-                       ordinary(p, wc);
-                       break;
-               }
-               break;
-       case '{':               /* okay as ordinary except if digit follows */
-               (void)REQUIRE(!MORE() || !isdigit((uch)PEEK()), REG_BADRPT);
-               /* FALLTHROUGH */
-       default:
-               p->next--;
-               wc = WGETNEXT();
-               ordinary(p, wc);
-               break;
-       }
-
-       if (!MORE())
-               return;
-       c = PEEK();
-       /* we call { a repetition if followed by a digit */
-       if (!( c == '*' || c == '+' || c == '?' ||
-                               (c == '{' && MORE2() && isdigit((uch)PEEK2())) ))
-               return;         /* no repetition, we're done */
-       NEXT();
-
-       (void)REQUIRE(!wascaret, REG_BADRPT);
-       switch (c) {
-       case '*':       /* implemented as +? */
-               /* this case does not require the (y|) trick, noKLUDGE */
-               INSERT(OPLUS_, pos);
-               ASTERN(O_PLUS, pos);
-               INSERT(OQUEST_, pos);
-               ASTERN(O_QUEST, pos);
-               break;
-       case '+':
-               INSERT(OPLUS_, pos);
-               ASTERN(O_PLUS, pos);
-               break;
-       case '?':
-               /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
-               INSERT(OCH_, pos);              /* offset slightly wrong */
-               ASTERN(OOR1, pos);              /* this one's right */
-               AHEAD(pos);                     /* fix the OCH_ */
-               EMIT(OOR2, 0);                  /* offset very wrong... */
-               AHEAD(THERE());                 /* ...so fix it */
-               ASTERN(O_CH, THERETHERE());
-               break;
-       case '{':
-               count = p_count(p);
-               if (EAT(',')) {
-                       if (isdigit((uch)PEEK())) {
-                               count2 = p_count(p);
-                               (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);
-               if (!EAT('}')) {        /* error heuristics */
-                       while (MORE() && PEEK() != '}')
-                               NEXT();
-                       (void)REQUIRE(MORE(), REG_EBRACE);
-                       SETERROR(REG_BADBR);
-               }
-               break;
-       }
-
-       if (!MORE())
-               return;
-       c = PEEK();
-       if (!( c == '*' || c == '+' || c == '?' ||
-                               (c == '{' && MORE2() && isdigit((uch)PEEK2())) ) )
-               return;
-       SETERROR(REG_BADRPT);
-}
-
-/*
- - p_str - string (no metacharacters) "parser"
- == static void p_str(struct parse *p);
- */
-static void
-p_str(struct parse *p)
-{
-       (void)REQUIRE(MORE(), REG_EMPTY);
-       while (MORE())
-               ordinary(p, WGETNEXT());
-}
-
-/*
- - p_bre - BRE parser top level, anchoring and concatenation
- == static void p_bre(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_bre(struct parse *p,
-       int end1,               /* first terminating character */
-       int end2)               /* second terminating character */
-{
-       sopno start = HERE();
-       int first = 1;                  /* first subexpression? */
-       int wasdollar = 0;
-
-       if (EAT('^')) {
-               EMIT(OBOL, 0);
-               p->g->iflags |= USEBOL;
-               p->g->nbol++;
-       }
-       while (MORE() && !SEETWO(end1, end2)) {
-               wasdollar = p_simp_re(p, first);
-               first = 0;
-       }
-       if (wasdollar) {        /* oops, that was a trailing anchor */
-               DROP(1);
-               EMIT(OEOL, 0);
-               p->g->iflags |= USEEOL;
-               p->g->neol++;
-       }
-
-       (void)REQUIRE(HERE() != start, REG_EMPTY);      /* require nonempty */
-}
-
-/*
- - p_simp_re - parse a simple RE, an atom possibly followed by a repetition
- == static int p_simp_re(struct parse *p, int starordinary);
- */
-static int                     /* was the simple RE an unbackslashed $? */
-p_simp_re(struct parse *p,
-       int starordinary)       /* is a leading * an ordinary character? */
-{
-       int c;
-       int count;
-       int count2;
-       sopno pos;
-       int i;
-       wint_t wc;
-       sopno subno;
-#      define  BACKSL  (1<<CHAR_BIT)
-
-       pos = HERE();           /* repetion op, if any, covers from here */
-
-       assert(MORE());         /* caller should have ensured this */
-       c = GETNEXT();
-       if (c == '\\') {
-               (void)REQUIRE(MORE(), REG_EESCAPE);
-               c = BACKSL | GETNEXT();
-       }
-       switch (c) {
-       case '.':
-               if (p->g->cflags&REG_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_bre(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 */
-       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 '*':
-               (void)REQUIRE(starordinary, REG_BADRPT);
-               /* FALLTHROUGH */
-       default:
-               p->next--;
-               wc = WGETNEXT();
-               ordinary(p, wc);
-               break;
-       }
-
-       if (EAT('*')) {         /* implemented as +? */
-               /* this case does not require the (y|) trick, noKLUDGE */
-               INSERT(OPLUS_, pos);
-               ASTERN(O_PLUS, pos);
-               INSERT(OQUEST_, pos);
-               ASTERN(O_QUEST, pos);
-       } else if (EATTWO('\\', '{')) {
-               count = p_count(p);
-               if (EAT(',')) {
-                       if (MORE() && isdigit((uch)PEEK())) {
-                               count2 = p_count(p);
-                               (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);
-               if (!EATTWO('\\', '}')) {       /* error heuristics */
-                       while (MORE() && !SEETWO('\\', '}'))
-                               NEXT();
-                       (void)REQUIRE(MORE(), REG_EBRACE);
-                       SETERROR(REG_BADBR);
-               }
-       } else if (c == '$')     /* $ (but not \$) ends it */
-               return(1);
-
-       return(0);
-}
-
-/*
- - p_count - parse a repetition count
- == static int p_count(struct parse *p);
- */
-static int                     /* the value */
-p_count(struct parse *p)
-{
-       int count = 0;
-       int ndigits = 0;
-
-       while (MORE() && isdigit((uch)PEEK()) && count <= DUPMAX) {
-               count = count*10 + (GETNEXT() - '0');
-               ndigits++;
-       }
-
-       (void)REQUIRE(ndigits > 0 && count <= DUPMAX, REG_BADBR);
-       return(count);
-}
-
-/*
- - p_bracket - parse a bracketed character list
- == static void p_bracket(struct parse *p);
- */
-static void
-p_bracket(struct parse *p)
-{
-       cset *cs;
-       wint_t ch;
-
-       /* Dept of Truly Sickening Special-Case Kludges */
-       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, "[:>:]]", 6) == 0) {
-               EMIT(OEOW, 0);
-               NEXTn(6);
-               return;
-       }
-
-       if ((cs = allocset(p)) == NULL)
-               return;
-
-       if (p->g->cflags&REG_ICASE)
-               cs->icase = 1;
-       if (EAT('^'))
-               cs->invert = 1;
-       if (EAT(']'))
-               CHadd(p, cs, ']');
-       else if (EAT('-'))
-               CHadd(p, cs, '-');
-       while (MORE() && PEEK() != ']' && !SEETWO('-', ']'))
-               p_b_term(p, cs);
-       if (EAT('-'))
-               CHadd(p, cs, '-');
-       (void)MUSTEAT(']', REG_EBRACK);
-
-       if (p->error != 0)      /* don't mess things up further */
-               return;
-
-       if (cs->invert && p->g->cflags&REG_NEWLINE)
-               cs->bmp['\n' >> 3] |= 1 << ('\n' & 7);
-
-       if ((ch = singleton(cs)) != OUT) {      /* optimize singleton sets */
-               ordinary(p, ch);
-               freeset(p, cs);
-       } else
-               EMIT(OANYOF, (int)(cs - p->g->sets));
-}
-
-/*
- - p_b_term - parse one term of a bracketed character list
- == static void p_b_term(struct parse *p, cset *cs);
- */
-static void
-p_b_term(struct parse *p, cset *cs)
-{
-       char c;
-       wint_t start, finish;
-       wint_t i;
-       locale_t loc = &__xlocale_C_locale;  /* see note under license */
-       struct xlocale_collate *table =
-               (struct xlocale_collate*)loc->components[XLC_COLLATE];
-
-       /* classify what we've got */
-       switch ((MORE()) ? PEEK() : '\0') {
-       case '[':
-               c = (MORE2()) ? PEEK2() : '\0';
-               break;
-       case '-':
-               SETERROR(REG_ERANGE);
-               return;                 /* NOTE RETURN */
-       default:
-               c = '\0';
-               break;
-       }
-
-       switch (c) {
-       case ':':               /* character class */
-               NEXT2();
-               (void)REQUIRE(MORE(), REG_EBRACK);
-               c = PEEK();
-               (void)REQUIRE(c != '-' && c != ']', REG_ECTYPE);
-               p_b_cclass(p, cs);
-               (void)REQUIRE(MORE(), REG_EBRACK);
-               (void)REQUIRE(EATTWO(':', ']'), REG_ECTYPE);
-               break;
-       case '=':               /* equivalence class */
-               NEXT2();
-               (void)REQUIRE(MORE(), REG_EBRACK);
-               c = PEEK();
-               (void)REQUIRE(c != '-' && c != ']', REG_ECOLLATE);
-               p_b_eclass(p, cs);
-               (void)REQUIRE(MORE(), REG_EBRACK);
-               (void)REQUIRE(EATTWO('=', ']'), REG_ECOLLATE);
-               break;
-       default:                /* symbol, ordinary character, or range */
-               start = p_b_symbol(p);
-               if (SEE('-') && MORE2() && PEEK2() != ']') {
-                       /* range */
-                       NEXT();
-                       if (EAT('-'))
-                               finish = '-';
-                       else
-                               finish = p_b_symbol(p);
-               } else
-                       finish = start;
-               if (start == finish)
-                       CHadd(p, cs, start);
-               else {
-                       if (table->__collate_load_error) {
-                               (void)REQUIRE((uch)start <= (uch)finish, REG_ERANGE);
-                               CHaddrange(p, cs, start, finish);
-                       } else {
-                               (void)REQUIRE(__collate_range_cmp(table, start, finish) <= 0, REG_ERANGE);
-                               for (i = 0; i <= UCHAR_MAX; i++) {
-                                       if (   __collate_range_cmp(table, start, i) <= 0
-                                           && __collate_range_cmp(table, i, finish) <= 0
-                                          )
-                                               CHadd(p, cs, i);
-                               }
-                       }
-               }
-               break;
-       }
-}
-
-/*
- - 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)
-{
-       char *sp = p->next;
-       size_t len;
-       wctype_t wct;
-       char clname[16];
-
-       while (MORE() && isalpha((uch)PEEK()))
-               NEXT();
-       len = p->next - sp;
-       if (len >= sizeof(clname) - 1) {
-               SETERROR(REG_ECTYPE);
-               return;
-       }
-       memcpy(clname, sp, len);
-       clname[len] = '\0';
-       if ((wct = wctype(clname)) == 0) {
-               SETERROR(REG_ECTYPE);
-               return;
-       }
-       CHaddtype(p, cs, wct);
-}
-
-/*
- - p_b_eclass - parse an equivalence-class name and deal with it
- == static void p_b_eclass(struct parse *p, cset *cs);
- *
- * This implementation is incomplete. xxx
- */
-static void
-p_b_eclass(struct parse *p, cset *cs)
-{
-       wint_t c;
-
-       c = p_b_coll_elem(p, '=');
-       CHadd(p, cs, c);
-}
-
-/*
- - p_b_symbol - parse a character or [..]ed multicharacter collating symbol
- == static wint_t p_b_symbol(struct parse *p);
- */
-static wint_t                  /* value of symbol */
-p_b_symbol(struct parse *p)
-{
-       wint_t value;
-
-       (void)REQUIRE(MORE(), REG_EBRACK);
-       if (!EATTWO('[', '.'))
-               return(WGETNEXT());
-
-       /* collating symbol */
-       value = p_b_coll_elem(p, '.');
-       (void)REQUIRE(EATTWO('.', ']'), REG_ECOLLATE);
-       return(value);
-}
-
-/*
- - p_b_coll_elem - parse a collating-element name and look it up
- == static wint_t p_b_coll_elem(struct parse *p, wint_t endc);
- */
-static wint_t                  /* value of collating element */
-p_b_coll_elem(struct parse *p,
-       wint_t endc)            /* name ended by endc,']' */
-{
-       char *sp = p->next;
-       struct cname *cp;
-       int len;
-       mbstate_t mbs;
-       wchar_t wc;
-       size_t clen;
-
-       while (MORE() && !SEETWO(endc, ']'))
-               NEXT();
-       if (!MORE()) {
-               SETERROR(REG_EBRACK);
-               return(0);
-       }
-       len = p->next - sp;
-       for (cp = cnames; cp->name != NULL; cp++)
-               if (strncmp(cp->name, sp, len) == 0 && cp->name[len] == '\0')
-                       return(cp->code);       /* known name */
-       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);
-}
-
-/*
- - othercase - return the case counterpart of an alphabetic
- == static wint_t othercase(wint_t ch);
- */
-static wint_t                  /* if no counterpart, return ch */
-othercase(wint_t 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, wint_t ch);
- *
- * Boy, is this implementation ever a kludge...
- */
-static void
-bothcases(struct parse *p, wint_t ch)
-{
-       char *oldnext = p->next;
-       char *oldend = p->end;
-       char bracket[3 + MB_LEN_MAX];
-       size_t n;
-       mbstate_t mbs;
-
-       assert(othercase(ch) != ch);    /* p_bracket() would recurse */
-       p->next = bracket;
-       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 == p->end);
-       p->next = oldnext;
-       p->end = oldend;
-}
-
-/*
- - ordinary - emit an ordinary character
- == static void ordinary(struct parse *p, wint_t ch);
- */
-static void
-ordinary(struct parse *p, wint_t ch)
-{
-       cset *cs;
-
-       if ((p->g->cflags&REG_ICASE) && iswalpha(ch) && othercase(ch) != ch)
-               bothcases(p, ch);
-       else if ((ch & OPDMASK) == ch)
-               EMIT(OCHAR, ch);
-       else {
-               /*
-                * 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));
-       }
-}
-
-/*
- - nonnewline - emit REG_NEWLINE version of OANY
- == static void nonnewline(struct parse *p);
- *
- * Boy, is this implementation ever a kludge...
- */
-static void
-nonnewline(struct parse *p)
-{
-       char *oldnext = p->next;
-       char *oldend = p->end;
-       char bracket[4];
-
-       p->next = bracket;
-       p->end = bracket+3;
-       bracket[0] = '^';
-       bracket[1] = '\n';
-       bracket[2] = ']';
-       bracket[3] = '\0';
-       p_bracket(p);
-       assert(p->next == bracket+3);
-       p->next = oldnext;
-       p->end = oldend;
-}
-
-/*
- - repeat - generate code for a bounded repetition, recursively if needed
- == 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) */
-{
-       sopno finish = HERE();
-#      define  N       2
-#      define  INF     3
-#      define  REP(f, t)       ((f)*8 + (t))
-#      define  MAP(n)  (((n) <= 1) ? (n) : ((n) == INFINITY) ? INF : N)
-       sopno copy;
-
-       if (p->error != 0)      /* head off possible runaway recursion */
-               return;
-
-       assert(from <= to);
-
-       switch (REP(MAP(from), MAP(to))) {
-       case REP(0, 0):                 /* must be user doing this */
-               DROP(finish-start);     /* drop the operand */
-               break;
-       case REP(0, 1):                 /* as x{1,1}? */
-       case REP(0, N):                 /* as x{1,n}? */
-       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);
-               ASTERN(OOR1, start);
-               AHEAD(start);                   /* ... fix it */
-               EMIT(OOR2, 0);
-               AHEAD(THERE());
-               ASTERN(O_CH, THERETHERE());
-               break;
-       case REP(1, 1):                 /* trivial case */
-               /* done */
-               break;
-       case REP(1, N):                 /* as x?x{1,n-1} */
-               /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
-               INSERT(OCH_, start);
-               ASTERN(OOR1, start);
-               AHEAD(start);
-               EMIT(OOR2, 0);                  /* offset very wrong... */
-               AHEAD(THERE());                 /* ...so fix it */
-               ASTERN(O_CH, THERETHERE());
-               copy = dupl(p, start+1, finish+1);
-               assert(copy == finish+4);
-               repeat(p, copy, 1, to-1);
-               break;
-       case REP(1, INF):               /* as x+ */
-               INSERT(OPLUS_, start);
-               ASTERN(O_PLUS, start);
-               break;
-       case REP(N, N):                 /* as xx{m-1,n-1} */
-               copy = dupl(p, start, finish);
-               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);
-               break;
-       default:                        /* "can't happen" */
-               SETERROR(REG_ASSERT);   /* just in case */
-               break;
-       }
-}
-
-/*
- - 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)
-{
-       if (p->error == 0)      /* keep earliest error condition */
-               p->error = e;
-       p->next = nuls;         /* try to bring things to a halt */
-       p->end = nuls;
-       return(0);              /* make the return value well-defined */
-}
-
-/*
- - allocset - allocate a set of characters for []
- == static cset *allocset(struct parse *p);
- */
-static cset *
-allocset(struct parse *p)
-{
-       cset *cs, *ncs;
-
-       ncs = realloc(p->g->sets, (p->g->ncsets + 1) * sizeof(*ncs));
-       if (ncs == NULL) {
-               SETERROR(REG_ESPACE);
-               return (NULL);
-       }
-       p->g->sets = ncs;
-       cs = &p->g->sets[p->g->ncsets++];
-       memset(cs, 0, sizeof(*cs));
-
-       return(cs);
-}
-
-/*
- - freeset - free a now-unused set
- == static void freeset(struct parse *p, cset *cs);
- */
-static void
-freeset(struct parse *p, cset *cs)
-{
-       cset *top = &p->g->sets[p->g->ncsets];
-
-       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--;
-}
-
-/*
- - singleton - Determine whether a set contains only one character,
- - returning it if so, otherwise returning OUT.
- */
-static wint_t
-singleton(cset *cs)
-{
-       wint_t i, s, n;
-
-       for (i = n = 0; i < NC; i++)
-               if (CHIN(cs, i)) {
-                       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);
-}
-
-/*
- - CHadd - add character to character set.
- */
-static void
-CHadd(struct parse *p, cset *cs, wint_t ch)
-{
-       wint_t nch, *newwides;
-       assert(ch >= 0);
-       if (ch < NC)
-               cs->bmp[ch >> 3] |= 1 << (ch & 7);
-       else {
-               newwides = realloc(cs->wides, (cs->nwides + 1) *
-                   sizeof(*cs->wides));
-               if (newwides == NULL) {
-                       SETERROR(REG_ESPACE);
-                       return;
-               }
-               cs->wides = newwides;
-               cs->wides[cs->nwides++] = ch;
-       }
-       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);
-       }
-}
-
-/*
- - CHaddrange - add all characters in the range [min,max] to a character set.
- */
-static void
-CHaddrange(struct parse *p, cset *cs, wint_t min, wint_t max)
-{
-       crange *newranges;
-
-       for (; min < NC && min <= max; min++)
-               CHadd(p, cs, min);
-       if (min >= max)
-               return;
-       newranges = realloc(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++;
-}
-
-/*
- - CHaddtype - add all characters of a certain type to a character set.
- */
-static void
-CHaddtype(struct parse *p, cset *cs, wctype_t wct)
-{
-       wint_t i;
-       wctype_t *newtypes;
-
-       for (i = 0; i < NC; i++)
-               if (iswctype(i, wct))
-                       CHadd(p, cs, i);
-       newtypes = realloc(cs->types, (cs->ntypes + 1) *
-           sizeof(*cs->types));
-       if (newtypes == NULL) {
-               SETERROR(REG_ESPACE);
-               return;
-       }
-       cs->types = newtypes;
-       cs->types[cs->ntypes++] = wct;
-}
-
-/*
- - dupl - emit a duplicate of a bunch of sops
- == 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 */
-{
-       sopno ret = HERE();
-       sopno len = finish - start;
-
-       assert(finish >= start);
-       if (len == 0)
-               return(ret);
-       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);
-}
-
-/*
- - doemit - emit a strip operator
- == static void doemit(struct parse *p, sop op, size_t opnd);
- *
- * It might seem better to implement this as a macro with a function as
- * hard-case backup, but it's just too big and messy unless there are
- * some changes to the data structures.  Maybe later.
- */
-static void
-doemit(struct parse *p, sop op, size_t opnd)
-{
-       /* avoid making error situations worse */
-       if (p->error != 0)
-               return;
-
-       /* deal with oversize operands ("can't happen", more or less) */
-       assert(opnd < 1<<OPSHIFT);
-
-       /* deal with undersized strip */
-       if (p->slen >= p->ssize)
-               if (!enlarge(p, (p->ssize+1) / 2 * 3))  /* +50% */
-                       return;
-
-       /* finally, it's all reduced to the easy case */
-       p->strip[p->slen++] = SOP(op, opnd);
-}
-
-/*
- - doinsert - insert a sop into the strip
- == static void doinsert(struct parse *p, sop op, size_t opnd, sopno pos);
- */
-static void
-doinsert(struct parse *p, sop op, size_t opnd, sopno pos)
-{
-       sopno sn;
-       sop s;
-       int i;
-
-       /* avoid making error situations worse */
-       if (p->error != 0)
-               return;
-
-       sn = HERE();
-       EMIT(op, opnd);         /* do checks, ensure space */
-       assert(HERE() == sn+1);
-       s = p->strip[sn];
-
-       /* adjust paren pointers */
-       assert(pos > 0);
-       for (i = 1; i < NPAREN; i++) {
-               if (p->pbegin[i] >= pos) {
-                       p->pbegin[i]++;
-               }
-               if (p->pend[i] >= pos) {
-                       p->pend[i]++;
-               }
-       }
-
-       memmove((char *)&p->strip[pos+1], (char *)&p->strip[pos],
-                                               (HERE()-pos-1)*sizeof(sop));
-       p->strip[pos] = s;
-}
-
-/*
- - dofwd - complete a forward reference
- == static void dofwd(struct parse *p, sopno pos, sop value);
- */
-static void
-dofwd(struct parse *p, sopno pos, sop value)
-{
-       /* avoid making error situations worse */
-       if (p->error != 0)
-               return;
-
-       assert(value < 1<<OPSHIFT);
-       p->strip[pos] = OP(p->strip[pos]) | value;
-}
-
-/*
- - enlarge - enlarge the strip
- == static int enlarge(struct parse *p, sopno size);
- */
-static int
-enlarge(struct parse *p, sopno size)
-{
-       sop *sp;
-
-       if (p->ssize >= size)
-               return 1;
-
-       sp = (sop *)realloc(p->strip, size*sizeof(sop));
-       if (sp == NULL) {
-               SETERROR(REG_ESPACE);
-               return 0;
-       }
-       p->strip = sp;
-       p->ssize = size;
-       return 1;
-}
-
-/*
- - stripsnug - compact the strip
- == static void stripsnug(struct parse *p, struct re_guts *g);
- */
-static void
-stripsnug(struct parse *p, struct re_guts *g)
-{
-       g->nstates = p->slen;
-       g->strip = (sop *)realloc((char *)p->strip, p->slen * sizeof(sop));
-       if (g->strip == NULL) {
-               SETERROR(REG_ESPACE);
-               g->strip = p->strip;
-       }
-}
-
-/*
- - findmust - fill in must and mlen with longest mandatory literal string
- == static void findmust(struct parse *p, struct re_guts *g);
- *
- * This algorithm could do fancy things like analyzing the operands of |
- * for common subsequences.  Someday.  This code is simple and finds most
- * of the interesting cases.
- *
- * Note that must and mlen got initialized during setup.
- */
-static void
-findmust(struct parse *p, struct re_guts *g)
-{
-       sop *scan;
-       sop *start = NULL;
-       sop *newstart = NULL;
-       sopno newlen;
-       sop s;
-       char *cp;
-       int offset;
-       char buf[MB_LEN_MAX];
-       size_t clen;
-       mbstate_t mbs;
-
-       /* avoid making error situations worse */
-       if (p->error != 0)
-               return;
-
-       /*
-        * 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;
-
-       /* 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 */
-                               memset(&mbs, 0, sizeof(mbs));
-                               newstart = scan - 1;
-                       }
-                       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:
-               case ORPAREN:
-                       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) {
-                                       g->iflags |= BAD;
-                                       return;
-                               }
-                       } while (OP(s) != O_QUEST && OP(s) != O_CH);
-                       /* FALLTHROUGH */
-               case OBOW:              /* things that break a sequence */
-               case OEOW:
-               case OBOL:
-               case OEOL:
-               case O_QUEST:
-               case O_CH:
-               case OEND:
-                       if (newlen > 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 > 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 > 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 > 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 (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;
-       memset(&mbs, 0, sizeof(mbs));
-       while (cp < g->must + g->mlen) {
-               while (OP(s = *scan++) != OCHAR)
-                       continue;
-               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;
-
-       /* If we gave up already on offsets, return */
-       if (offset == -1)
-               return -1;
-
-       largest = 0;
-       try = 0;
-       s = *scan++;
-       while (OP(s) != O_QUEST && OP(s) != 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) != O_QUEST && OP(s) != O_CH &&
-                                                       OP(s) != OOR2)
-                                       return -1;
-                       } while (OP(s) != O_QUEST && OP(s) != 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 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;
-       int mindex;
-
-       /* Avoid making errors worse */
-       if (p->error != 0)
-               return;
-
-       g->charjump = (int*) malloc((NC + 1) * sizeof(int));
-       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)
-{
-       int mindex;             /* General "must" iterator */
-       int suffix;             /* Keeps track of matching suffix */
-       int ssuffix;            /* Keeps track of suffixes' suffix */
-       int* pmatches;          /* pmatches[k] points to the next i
-                                * such that i+1...mlen is a substring
-                                * of k+1...k+mlen-i-1
-                                */
-
-       /* Avoid making errors worse */
-       if (p->error != 0)
-               return;
-
-       pmatches = (int*) malloc(g->mlen * sizeof(unsigned int));
-       if (pmatches == NULL) {
-               g->matchjump = NULL;
-               return;
-       }
-
-       g->matchjump = (int*) malloc(g->mlen * sizeof(unsigned int));
-       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 (mindex = g->mlen - 1, suffix = g->mlen; mindex >= 0;
-           mindex--, 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)
-{
-       sop *scan;
-       sop s;
-       sopno plusnest = 0;
-       sopno maxnest = 0;
-
-       if (p->error != 0)
-               return(0);      /* there may not be an OEND */
-
-       scan = g->strip + 1;
-       do {
-               s = *scan++;
-               switch (OP(s)) {
-               case OPLUS_:
-                       plusnest++;
-                       break;
-               case O_PLUS:
-                       if (plusnest > maxnest)
-                               maxnest = plusnest;
-                       plusnest--;
-                       break;
-               }
-       } while (OP(s) != OEND);
-       if (plusnest != 0)
-               g->iflags |= BAD;
-       return(maxnest);
-}
diff --git a/lib/libc/regex/regerror.c b/lib/libc/regex/regerror.c
deleted file mode 100644 (file)
index ba1b170..0000000
+++ /dev/null
@@ -1,170 +0,0 @@
-/*-
- * 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.
- *
- *     @(#)regerror.c  8.4 (Berkeley) 3/20/94
- * $FreeBSD: src/lib/libc/regex/regerror.c,v 1.11 2007/06/11 03:05:54 delphij Exp $
- * $DragonFly: src/lib/libc/regex/regerror.c,v 1.6 2005/11/13 02:17:18 swildner Exp $
- */
-
-#include <sys/types.h>
-#include <stdio.h>
-#include <string.h>
-#include <limits.h>
-#include <stdlib.h>
-#include <regex.h>
-
-#include "utils.h"
-
-/* ========= begin header generated by ./mkh ========= */
-#ifdef __cplusplus
-extern "C" {
-#endif
-
-/* === regerror.c === */
-static char *regatoi(const regex_t *preg, char *localbuf);
-
-#ifdef __cplusplus
-}
-#endif
-/* ========= end header generated by ./mkh ========= */
-/*
- = #define     REG_NOMATCH      1
- = #define     REG_BADPAT       2
- = #define     REG_ECOLLATE     3
- = #define     REG_ECTYPE       4
- = #define     REG_EESCAPE      5
- = #define     REG_ESUBREG      6
- = #define     REG_EBRACK       7
- = #define     REG_EPAREN       8
- = #define     REG_EBRACE       9
- = #define     REG_BADBR       10
- = #define     REG_ERANGE      11
- = #define     REG_ESPACE      12
- = #define     REG_BADRPT      13
- = #define     REG_EMPTY       14
- = #define     REG_ASSERT      15
- = #define     REG_INVARG      16
- = #define     REG_ILLSEQ      17
- = #define     REG_ATOI        255     // convert name to number (!)
- = #define     REG_ITOA        0400    // convert number to name (!)
- */
-static struct rerr {
-       int code;
-       char *name;
-       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"},
-       {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);
- */
-/* ARGSUSED */
-size_t
-regerror(int errcode,
-        const regex_t * __restrict preg,
-        char * __restrict errbuf,
-        size_t errbuf_size)
-{
-       struct rerr *r;
-       size_t len;
-       int target = errcode &~ REG_ITOA;
-       char *s;
-       char convbuf[50];
-
-       if (errcode == REG_ATOI)
-               s = regatoi(preg, convbuf);
-       else {
-               for (r = rerrs; r->code != 0; r++)
-                       if (r->code == target)
-                               break;
-
-               if (errcode&REG_ITOA) {
-                       if (r->code != 0)
-                               strcpy(convbuf, r->name);
-                       else
-                               sprintf(convbuf, "REG_0x%x", target);
-                       assert(strlen(convbuf) < sizeof(convbuf));
-                       s = convbuf;
-               } else
-                       s = r->explain;
-       }
-
-       len = strlen(s) + 1;
-       if (errbuf_size > 0) {
-               if (errbuf_size > len)
-                       strcpy(errbuf, s);
-               else {
-                       strncpy(errbuf, s, errbuf_size-1);
-                       errbuf[errbuf_size-1] = '\0';
-               }
-       }
-
-       return(len);
-}
-
-/*
- - regatoi - internal routine to implement REG_ATOI
- == static char *regatoi(const regex_t *preg, char *localbuf);
- */
-static char *
-regatoi(const regex_t *preg, char *localbuf)
-{
-       struct rerr *r;
-
-       for (r = rerrs; r->code != 0; r++)
-               if (strcmp(r->name, preg->re_endp) == 0)
-                       break;
-       if (r->code == 0)
-               return("0");
-
-       sprintf(localbuf, "%d", r->code);
-       return(localbuf);
-}
diff --git a/lib/libc/regex/regex2.h b/lib/libc/regex/regex2.h
deleted file mode 100644 (file)
index 1c39495..0000000
+++ /dev/null
@@ -1,193 +0,0 @@
-/*-
- * 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.
- * 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: src/lib/libc/regex/regex2.h,v 1.11 2007/01/09 00:28:04 imp Exp $
- * $DragonFly: src/lib/libc/regex/regex2.h,v 1.2 2003/06/17 04:26:44 dillon Exp $
- */
-
-/*
- * First, the stuff that ends up in the outside-world include file
- = typedef off_t regoff_t;
- = typedef struct {
- =     int re_magic;
- =     size_t re_nsub;         // number of parenthesized subexpressions
- =     const char *re_endp;    // end pointer for REG_PEND
- =     struct re_guts *re_g;   // none of your business :-)
- = } regex_t;
- = typedef struct {
- =     regoff_t rm_so;         // start of match
- =     regoff_t rm_eo;         // end of match
- = } regmatch_t;
- */
-/*
- * internals of regex_t
- */
-#define        MAGIC1  ((('r'^0200)<<8) | 'e')
-
-/*
- * The internal representation is a *strip*, a sequence of
- * operators ending with an endmarker.  (Some terminology etc. is a
- * historical relic of earlier versions which used multiple strips.)
- * Certain oddities in the representation are there to permit running
- * the machinery backwards; in particular, any deviation from sequential
- * flow must be marked at both its source and its destination.  Some
- * fine points:
- *
- * - OPLUS_ and O_PLUS are *inside* the loop they create.
- * - OQUEST_ and O_QUEST are *outside* the bypass they create.
- * - OCH_ and O_CH are *outside* the multi-way branch they create, while
- *   OOR1 and OOR2 are respectively the end and the beginning of one of
- *   the branches.  Note that there is an implicit OOR2 following OCH_
- *   and an implicit OOR1 preceding O_CH.
- *
- * In state representations, an operator's bit is on to signify a state
- * immediately *preceding* "execution" of that operator.
- */
-typedef unsigned long sop;     /* strip operator */
-typedef long sopno;
-#define        OPRMASK 0xf8000000L
-#define        OPDMASK 0x07ffffffL
-#define        OPSHIFT ((unsigned)27)
-#define        OP(n)   ((n)&OPRMASK)
-#define        OPND(n) ((n)&OPDMASK)
-#define        SOP(op, opnd)   ((op)|(opnd))
-/* 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     -                       */
-
-/*
- * Structures for [] character-set representation.
- */
-typedef struct {
-       wint_t          min;
-       wint_t          max;
-} crange;
-typedef struct {
-       unsigned char   bmp[NC / 8];
-       wctype_t        *types;
-       int             ntypes;
-       wint_t          *wides;
-       int             nwides;
-       crange          *ranges;
-       int             nranges;
-       int             invert;
-       int             icase;
-} cset;
-
-static int
-CHIN1(cset *cs, wint_t ch)
-{
-       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 (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
- */
-struct re_guts {
-       int magic;
-#              define  MAGIC2  ((('R'^0200)<<8)|'E')
-       sop *strip;             /* malloced area for strip */
-       int ncsets;             /* number of csets in use */
-       cset *sets;             /* -> cset [ncsets] */
-       int cflags;             /* copy of regcomp() cflags argument */
-       sopno nstates;          /* = number of sops */
-       sopno firststate;       /* the initial OEND (normally 0) */
-       sopno laststate;        /* the final OEND */
-       int iflags;             /* internal flags */
-#              define  USEBOL  01      /* used ^ */
-#              define  USEEOL  02      /* used $ */
-#              define  BAD     04      /* something wrong */
-       int nbol;               /* number of ^ used */
-       int neol;               /* number of $ used */
-       char *must;             /* match must contain this string */
-       int moffset;            /* latest point at which must may be located */
-       int *charjump;          /* Boyer-Moore char jump table */
-       int *matchjump;         /* Boyer-Moore match jump table */
-       int 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? */
-};
-
-/* misc utilities */
-#define        OUT     (CHAR_MIN - 1)  /* a non-character value */
-#define ISWORD(c)       (iswalnum((uch)(c)) || (c) == '_')
diff --git a/lib/libc/regex/regexec.c b/lib/libc/regex/regexec.c
deleted file mode 100644 (file)
index 2e6e51a..0000000
+++ /dev/null
@@ -1,229 +0,0 @@
-/*-
- * 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.
- *
- *     @(#)regexec.c   8.3 (Berkeley) 3/20/94
- * $FreeBSD: src/lib/libc/regex/regexec.c,v 1.8 2007/06/11 03:05:54 delphij Exp $
- * $DragonFly: src/lib/libc/regex/regexec.c,v 1.4 2005/11/20 09:18:37 swildner Exp $
- */
-
-/*
- * the outer shell of regexec()
- *
- * 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 and characters.
- */
-#include <sys/types.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>
-
-#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  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       long dummy      /* dummy version */
-#define        STATESETUP(m, n)        /* nothing */
-#define        STATETEARDOWN(m)        /* nothing */
-#define        SETUP(v)        ((v) = 0)
-#define        onestate        long
-#define        INIT(o, n)      ((o) = (unsigned long)1 << (n))
-#define        INC(o)  ((o) <<= 1)
-#define        ISSTATEIN(v, o) (((v) & (o)) != 0)
-/* some abbreviations; note that some of these know variable names! */
-/* do "if I'm here, I can also be there" etc without branches */
-#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 */
-
-#include "engine.c"
-
-/* now undo things */
-#undef states
-#undef CLEAR
-#undef SET0
-#undef SET1
-#undef ISSET
-#undef ASSIGN
-#undef EQ
-#undef STATEVARS
-#undef STATESETUP
-#undef STATETEARDOWN
-#undef SETUP
-#undef onestate
-#undef INIT
-#undef INC
-#undef ISSTATEIN
-#undef FWD
-#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, 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, 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! */
-/* do "if I'm here, I can also be there" etc without branches */
-#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, \
- =                                     regmatch_t [], int);
- = #define     REG_NOTBOL      00001
- = #define     REG_NOTEOL      00002
- = #define     REG_STARTEND    00004
- = #define     REG_TRACE       00400   // tracing of execution
- = #define     REG_LARGE       01000   // force large representation
- = #define     REG_BACKR       02000   // force use of backref code
- *
- * We put this here so we can exploit knowledge of the state representation
- * when choosing which matcher to call.  Also, by this point the matchers
- * have been prototyped.
- */
-int                            /* 0 success, REG_NOMATCH failure */
-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;
-#ifdef REDEBUG
-#      define  GOODFLAGS(f)    (f)
-#else
-#      define  GOODFLAGS(f)    ((f)&(REG_NOTBOL|REG_NOTEOL|REG_STARTEND))
-#endif
-
-       if (preg->re_magic != MAGIC1 || g->magic != MAGIC2)
-               return(REG_BADPAT);
-       assert(!(g->iflags&BAD));
-       if (g->iflags&BAD)              /* backstop for no-debug case */
-               return(REG_BADPAT);
-       eflags = GOODFLAGS(eflags);
-
-       if (MB_CUR_MAX > 1)
-               return(mmatcher(g, (char *)string, nmatch, pmatch, eflags));
-       else if (g->nstates <= CHAR_BIT*sizeof(states1) && !(eflags&REG_LARGE))
-               return(smatcher(g, (char *)string, nmatch, pmatch, eflags));
-       else
-               return(lmatcher(g, (char *)string, nmatch, pmatch, eflags));
-}
diff --git a/lib/libc/regex/regfree.c b/lib/libc/regex/regfree.c
deleted file mode 100644 (file)
index b277899..0000000
+++ /dev/null
@@ -1,85 +0,0 @@
-/*-
- * 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.
- *
- *     @(#)regfree.c   8.3 (Berkeley) 3/20/94
- * $FreeBSD: src/lib/libc/regex/regfree.c,v 1.8 2007/06/11 03:05:54 delphij Exp $
- * $DragonFly: src/lib/libc/regex/regfree.c,v 1.3 2004/02/06 22:36:50 joerg Exp $
- */
-
-#include <sys/types.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <limits.h>
-#include <regex.h>
-#include <wchar.h>
-#include <wctype.h>
-
-#include "utils.h"
-#include "regex2.h"
-
-/*
- - regfree - free everything
- = extern void regfree(regex_t *);
- */
-void
-regfree(regex_t *preg)
-{
-       struct re_guts *g;
-       int i;
-
-       if (preg->re_magic != MAGIC1)   /* oops */
-               return;                 /* nice to complain, but hard */
-
-       g = preg->re_g;
-       if (g == NULL || g->magic != MAGIC2)    /* oops again */
-               return;
-       preg->re_magic = 0;             /* mark it invalid */
-       g->magic = 0;                   /* mark it invalid */
-
-       if (g->strip != NULL)
-               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);
-       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
deleted file mode 100644 (file)
index 2a2ed96..0000000
+++ /dev/null
@@ -1,54 +0,0 @@
-/*-
- * 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.
- * 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: src/lib/libc/regex/utils.h,v 1.3 2007/01/09 00:28:04 imp Exp $
- */
-
-/* utility definitions */
-#define        DUPMAX          _POSIX2_RE_DUP_MAX      /* xxx is this right? */
-#define        INFINITY        (DUPMAX + 1)
-#define        NC              (CHAR_MAX - CHAR_MIN + 1)
-typedef unsigned char uch;
-
-/* switch off assertions (if not already off) if no REDEBUG */
-#ifndef REDEBUG
-#ifndef NDEBUG
-#define        NDEBUG  /* no assertions please */
-#endif
-#endif
-#include <assert.h>
-
-/* for old systems with bcopy() but no memmove() */
-#ifdef USEBCOPY
-#define        memmove(d, s, c)        bcopy(s, d, c)
-#endif
diff --git a/lib/libc/tre-regex/Makefile.inc b/lib/libc/tre-regex/Makefile.inc
new file mode 100644 (file)
index 0000000..0d972d1
--- /dev/null
@@ -0,0 +1,42 @@
+TRESRC=        ${.CURDIR}/../../contrib/tre/lib
+
+.PATH: ${TRESRC} ${.CURDIR}/../libc/tre-regex
+
+CMAPS+=        ${.CURDIR}/regex/Symbol.map
+
+SRCS+= tre-ast.c \
+       tre-compile.c \
+       tre-match-backtrack.c \
+       tre-match-parallel.c \
+       tre-mem.c \
+       tre-parse.c \
+       tre-stack.c \
+       regcomp.c \
+       regerror.c \
+       regexec.c
+
+CFLAGS+=       -I${.CURDIR}/../libc/tre-regex
+CFLAGS+=       -I${.CURDIR}/../libc/locale
+CFLAGS+=       -I${TRESRC}
+CFLAGS+=       -DHAVE_CONFIG_H
+
+.if ${LIB} == "c"
+INCS=  ${.CURDIR}/../libc/tre-regex/regex.h
+MAN+=  regex.3
+MAN+=  re_format.7
+
+MLINKS+=regex.3 regcomp.3 \
+       regex.3 regcomp_l.3 \
+       regex.3 regncomp.3 \
+       regex.3 regncomp_l.3 \
+       regex.3 regnwcomp.3 \
+       regex.3 regnwcomp_l.3 \
+       regex.3 regwcomp.3 \
+       regex.3 regwcomp_l.3 \
+       regex.3 regnexec.3 \
+       regex.3 regnwexec.3 \
+       regex.3 regwexec.3 \
+       regex.3 regexec.3 \
+       regex.3 regerror.3 \
+       regex.3 regfree.3
+.endif
diff --git a/lib/libc/tre-regex/Symbol.map b/lib/libc/tre-regex/Symbol.map
new file mode 100644 (file)
index 0000000..e451687
--- /dev/null
@@ -0,0 +1,23 @@
+DF402.0 {
+    regcomp;
+    regerror;
+    regexec;
+    regfree;
+};
+
+DF404.0 {
+    regcomp_l
+    regncomp
+    regncomp_l
+    regnwcomp
+    regnwcomp_l
+    regwcomp
+    regwcomp_l
+    regnexec
+    regnwexec
+    regwexec
+    tre_version
+    tre_config
+    tre_have_backrefs
+    tre_have_approx
+};
diff --git a/lib/libc/tre-regex/cname.h b/lib/libc/tre-regex/cname.h
new file mode 100644 (file)
index 0000000..26355e8
--- /dev/null
@@ -0,0 +1,140 @@
+/*-
+ * 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.
+ * 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: src/lib/libc/regex/cname.h,v 1.4 2007/01/09 00:28:04 imp Exp $
+ */
+
+/* character-name table */
+static const struct cname {
+       const wchar_t *name;
+       wchar_t code;
+} cnames[] = {
+       {L"",                           (wchar_t)-1}, /* sentinel */
+       {L"ACK",                        L'\006'},
+       {L"BEL",                        L'\007'},
+       {L"BS",                         L'\010'},
+       {L"CAN",                        L'\030'},
+       {L"CR",                         L'\015'},
+       {L"DC1",                        L'\021'},
+       {L"DC2",                        L'\022'},
+       {L"DC3",                        L'\023'},
+       {L"DC4",                        L'\024'},
+       {L"DEL",                        L'\177'},
+       {L"DLE",                        L'\020'},
+       {L"EM",                         L'\031'},
+       {L"ENQ",                        L'\005'},
+       {L"EOT",                        L'\004'},
+       {L"ESC",                        L'\033'},
+       {L"ETB",                        L'\027'},
+       {L"ETX",                        L'\003'},
+       {L"FF",                         L'\014'},
+       {L"FS",                         L'\034'},
+       {L"GS",                         L'\035'},
+       {L"HT",                         L'\011'},
+       {L"IS1",                        L'\037'},
+       {L"IS2",                        L'\036'},
+       {L"IS3",                        L'\035'},
+       {L"IS4",                        L'\034'},
+       {L"LF",                         L'\012'},
+       {L"NAK",                        L'\025'},
+       {L"NUL",                        L'\0'},
+       {L"RS",                         L'\036'},
+       {L"SI",                         L'\017'},
+       {L"SO",                         L'\016'},
+       {L"SOH",                        L'\001'},
+       {L"STX",                        L'\002'},
+       {L"SUB",                        L'\032'},
+       {L"SYN",                        L'\026'},
+       {L"US",                         L'\037'},
+       {L"VT",                         L'\013'},
+       {L"alert",                      L'\007'},
+       {L"ampersand",                  L'&'},
+       {L"apostrophe",                 L'\''},
+       {L"asterisk",                   L'*'},
+       {L"backslash",                  L'\\'},
+       {L"backspace",                  L'\b'},
+       {L"carriage-return",            L'\r'},
+       {L"circumflex",                 L'^'},
+       {L"circumflex-accent",          L'^'},
+       {L"colon",                      L':'},
+       {L"comma",                      L','},
+       {L"commercial-at",              L'@'},
+       {L"dollar-sign",                L'$'},
+       {L"eight",                      L'8'},
+       {L"equals-sign",                L'='},
+       {L"exclamation-mark",           L'!'},
+       {L"five",                       L'5'},
+       {L"form-feed",                  L'\f'},
+       {L"four",                       L'4'},
+       {L"full-stop",                  L'.'},
+       {L"grave-accent",               L'`'},
+       {L"greater-than-sign",          L'>'},
+       {L"hyphen",                     L'-'},
+       {L"hyphen-minus",               L'-'},
+       {L"left-brace",                 L'{'},
+       {L"left-curly-bracket",         L'{'},
+       {L"left-parenthesis",           L'('},
+       {L"left-square-bracket",        L'['},
+       {L"less-than-sign",             L'<'},
+       {L"low-line",                   L'_'},
+       {L"newline",                    L'\n'},
+       {L"nine",                       L'9'},
+       {L"number-sign",                L'#'},
+       {L"one",                        L'1'},
+       {L"percent-sign",               L'%'},
+       {L"period",                     L'.'},
+       {L"plus-sign",                  L'+'},
+       {L"question-mark",              L'?'},
+       {L"quotation-mark",             L'"'},
+       {L"reverse-solidus",            L'\\'},
+       {L"right-brace",                L'}'},
+       {L"right-curly-bracket",        L'}'},
+       {L"right-parenthesis",          L')'},
+       {L"right-square-bracket",       L']'},
+       {L"semicolon",                  L';'},
+       {L"seven",                      L'7'},
+       {L"six",                        L'6'},
+       {L"slash",                      L'/'},
+       {L"solidus",                    L'/'},
+       {L"space",                      L' '},
+       {L"tab",                        L'\t'},
+       {L"three",                      L'3'},
+       {L"tilde",                      L'~'},
+       {L"two",                        L'2'},
+       {L"underscore",                 L'_'},
+       {L"vertical-line",              L'|'},
+       {L"vertical-tab",               L'\v'},
+       {L"zero",                       L'0'},
+};
+
+#define NCNAMES                (sizeof(cnames) / sizeof(*cnames))
diff --git a/lib/libc/tre-regex/config.h b/lib/libc/tre-regex/config.h
new file mode 100644 (file)
index 0000000..57c1539
--- /dev/null
@@ -0,0 +1,259 @@
+/* config.h.  Generated from config.h.in by configure.  */
+/* config.h.in.  Generated from configure.ac by autoheader.  */
+
+/* Define to one of `_getb67', `GETB67', `getb67' for Cray-2 and Cray-YMP
+   systems. This function is required for `alloca.c' support on those systems.
+   */
+/* #undef CRAY_STACKSEG_END */
+
+/* Define to 1 if using `alloca.c'. */
+/* #undef C_ALLOCA */
+
+/* Define to 1 if translation of program messages to the user's native
+   language is requested. */
+/* #undef ENABLE_NLS */
+
+/* Define to 1 if you have `alloca', as a function or macro. */
+/* #undef HAVE_ALLOCA */
+
+/* Define to 1 if you have <alloca.h> and it should be used (not on Ultrix).
+   */
+/* #undef HAVE_ALLOCA_H */
+
+/* Define to 1 if you have the MacOS X function CFLocaleCopyCurrent in the
+   CoreFoundation framework. */
+/* #undef HAVE_CFLOCALECOPYCURRENT */
+
+/* Define to 1 if you have the MacOS X function CFPreferencesCopyAppValue in
+   the CoreFoundation framework. */
+/* #undef HAVE_CFPREFERENCESCOPYAPPVALUE */
+
+/* Define if the GNU dcgettext() function is already present or preinstalled.
+   */
+/* #undef HAVE_DCGETTEXT */
+
+/* Define to 1 if you have the <dlfcn.h> header file. */
+#define HAVE_DLFCN_H 1
+
+/* Define to 1 if you have the <getopt.h> header file. */
+#define HAVE_GETOPT_H 1
+
+/* Define to 1 if you have the `getopt_long' function. */
+#define HAVE_GETOPT_LONG 1
+
+/* Define if the GNU gettext() function is already present or preinstalled. */
+/* #undef HAVE_GETTEXT */
+
+/* Define if you have the iconv() function and it works. */
+/* #undef HAVE_ICONV */
+
+/* Define to 1 if you have the <inttypes.h> header file. */
+#define HAVE_INTTYPES_H 1
+
+/* Define to 1 if you have the `isascii' function. */
+#define HAVE_ISASCII 1
+
+/* Define to 1 if you have the `isblank' function. */
+#define HAVE_ISBLANK 1
+
+/* Define to 1 if you have the `iswascii' function or macro. */
+#define HAVE_ISWASCII 1
+
+/* Define to 1 if you have the `iswblank' function or macro. */
+#define HAVE_ISWBLANK 1
+
+/* Define to 1 if you have the `iswctype' function or macro. */
+#define HAVE_ISWCTYPE 1
+
+/* Define to 1 if you have the `iswlower' function or macro. */
+#define HAVE_ISWLOWER 1
+
+/* Define to 1 if you have the `iswupper' function or macro. */
+#define HAVE_ISWUPPER 1
+
+/* Define to 1 if you have the <libutf8.h> header file. */
+/* #undef HAVE_LIBUTF8_H */
+
+/* Define to 1 if you have the `mbrtowc' function or macro. */
+#define HAVE_MBRTOWC 1
+
+/* Define to 1 if the system has the type `mbstate_t'. */
+#define HAVE_MBSTATE_T 1
+
+/* Define to 1 if you have the `mbtowc' function or macro. */
+/* #undef HAVE_MBTOWC */
+
+/* Define to 1 if you have the <memory.h> header file. */
+#define HAVE_MEMORY_H 1
+
+/* Define to 1 if you have the <regex.h> header file. */
+/* #undef HAVE_REGEX_H */
+
+/* Define to 1 if the system has the type `reg_errcode_t'. */
+/* #undef HAVE_REG_ERRCODE_T */
+
+/* Define to 1 if you have the <stdint.h> header file. */
+#define HAVE_STDINT_H 1
+
+/* Define to 1 if you have the <stdlib.h> header file. */
+#define HAVE_STDLIB_H 1
+
+/* Define to 1 if you have the <strings.h> header file. */
+#define HAVE_STRINGS_H 1
+
+/* Define to 1 if you have the <string.h> header file. */
+#define HAVE_STRING_H 1
+
+/* Define to 1 if you have the <sys/stat.h> header file. */
+#define HAVE_SYS_STAT_H 1
+
+/* Define to 1 if you have the <sys/types.h> header file. */
+#define HAVE_SYS_TYPES_H 1
+
+/* Define to 1 if you have the `towlower' function or macro. */
+#define HAVE_TOWLOWER 1
+
+/* Define to 1 if you have the `towupper' function or macro. */
+#define HAVE_TOWUPPER 1
+
+/* Define to 1 if you have the <unistd.h> header file. */
+#define HAVE_UNISTD_H 1
+
+/* Define to 1 if you have the <wchar.h> header file. */
+#define HAVE_WCHAR_H 1
+
+/* Define to 1 if the system has the type `wchar_t'. */
+#define HAVE_WCHAR_T 1
+
+/* Define to 1 if you have the `wcschr' function or macro. */
+#define HAVE_WCSCHR 1
+
+/* Define to 1 if you have the `wcscpy' function or macro. */
+#define HAVE_WCSCPY 1
+
+/* Define to 1 if you have the `wcslen' function or macro. */
+#define HAVE_WCSLEN 1
+
+/* Define to 1 if you have the `wcsncpy' function or macro. */
+#define HAVE_WCSNCPY 1
+
+/* Define to 1 if you have the `wcsrtombs' function or macro. */
+#define HAVE_WCSRTOMBS 1
+
+/* Define to 1 if you have the `wcstombs' function or macro. */
+/* #undef HAVE_WCSTOMBS */
+
+/* Define to 1 if you have the `wctype' function or macro. */
+#define HAVE_WCTYPE 1
+
+/* Define to 1 if you have the <wctype.h> header file. */
+#define HAVE_WCTYPE_H 1
+
+/* Define to 1 if the system has the type `wint_t'. */
+#define HAVE_WINT_T 1
+
+/* Define if you want to disable debug assertions. */
+#define NDEBUG 1
+
+/* Define to 1 if your C compiler doesn't accept -c and -o together. */
+/* #undef NO_MINUS_C_MINUS_O */
+
+/* Name of package */
+#define PACKAGE "tre"
+
+/* Define to the address where bug reports for this package should be sent. */
+#define PACKAGE_BUGREPORT "tre-general@lists.laurikari.net"
+
+/* Define to the full name of this package. */
+#define PACKAGE_NAME "TRE"
+
+/* Define to the full name and version of this package. */
+#define PACKAGE_STRING "TRE 0.8.0"
+
+/* Define to the one symbol short name of this package. */
+#define PACKAGE_TARNAME "tre"
+
+/* Define to the version of this package. */
+#define PACKAGE_VERSION "0.8.0"
+
+/* If using the C implementation of alloca, define if you know the
+   direction of stack growth for your system; otherwise it will be
+   automatically deduced at runtime.
+       STACK_DIRECTION > 0 => grows toward higher addresses
+       STACK_DIRECTION < 0 => grows toward lower addresses
+       STACK_DIRECTION = 0 => direction of growth unknown */
+/* #undef STACK_DIRECTION */
+
+/* Define to 1 if you have the ANSI C header files. */
+#define STDC_HEADERS 1
+
+/* Define if you want to enable approximate matching functionality. */
+/* #undef TRE_APPROX */
+
+/* Define if you want TRE to print debug messages to stdout. */
+/* #undef TRE_DEBUG */
+
+/* Define to enable multibyte character set support. */
+#define TRE_MULTIBYTE 1
+
+/* Define to a field in the regex_t struct where TRE should store a pointer to
+   the internal tre_tnfa_t structure */
+#define TRE_REGEX_T_FIELD value
+
+/* Define to the absolute path to the system regex.h */
+#define TRE_SYSTEM_REGEX_H_PATH <regex.h>
+
+/* Define if you want TRE to use alloca() instead of malloc() when allocating
+   memory needed for regexec operations. */
+/* #undef TRE_USE_ALLOCA */
+
+/* Define to include the system regex.h from TRE regex.h */
+#define TRE_USE_SYSTEM_REGEX_H 1
+
+/* TRE version string. */
+#define TRE_VERSION "0.8.0"
+
+/* TRE version level 1. */
+#define TRE_VERSION_1 0
+
+/* TRE version level 2. */
+#define TRE_VERSION_2 8
+
+/* TRE version level 3. */
+#define TRE_VERSION_3 0
+
+/* Define to enable wide character (wchar_t) support. */
+#define TRE_WCHAR 1
+
+/* Version number of package */
+#define VERSION "0.8.0"
+
+/* Define to the maximum value of wchar_t if not already defined elsewhere */
+/* #undef WCHAR_MAX */
+
+/* Define if wchar_t is signed */
+/* #undef WCHAR_T_SIGNED */
+
+/* Define if wchar_t is unsigned */
+/* #undef WCHAR_T_UNSIGNED */
+
+/* Number of bits in a file offset, on hosts where this is settable. */
+/* #undef _FILE_OFFSET_BITS */
+
+/* Define to enable GNU extensions in glibc */
+/* #undefine _GNU_SOURCE */
+
+/* Define for large files, on AIX-style hosts. */
+/* #undef _LARGE_FILES */
+
+/* Define on IRIX */
+/* #undef _REGCOMP_INTERNAL */
+
+/* Define to empty if `const' does not conform to ANSI C. */
+/* #undef const */
+
+/* Define to `__inline__' or `__inline' if that's what the C compiler
+   calls it, or to nothing if 'inline' is not supported under any name.  */
+#ifndef __cplusplus
+/* #undef inline */
+#endif
similarity index 56%
rename from lib/libc/regex/re_format.7
rename to lib/libc/tre-regex/re_format.7
index bcc6a4a..fc05cc7 100644 (file)
@@ -30,9 +30,9 @@
 .\" SUCH DAMAGE.
 .\"
 .\"    @(#)re_format.7 8.3 (Berkeley) 3/20/94
-.\" $FreeBSD: head/lib/libc/regex/re_format.7 282007 2015-04-26 10:55:39Z bapt $
+.\" $FreeBSD: src/lib/libc/regex/re_format.7,v 1.12 2008/09/05 17:41:20 keramida Exp $
 .\"
-.Dd June 30, 2014
+.Dd August 6, 2015
 .Dt RE_FORMAT 7
 .Os
 .Sh NAME
@@ -310,13 +310,6 @@ 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
-.Xr svr4 4
-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,
@@ -445,6 +438,347 @@ or
 .Ql cc
 but not
 .Ql bc .
+.Sh ENHANCED FEATURES
+When the
+.Dv REG_ENHANCED
+flag is passed to one of the
+.Fn regcomp
+variants, additional features are activated.
+Like the enhanced
+.Nm regex
+implementations in scripting languages such as
+.Xr perl 1
+and
+.Xr python 1 ,
+these additional features may conflict with the
+.St -p1003.2
+standards in some ways.
+Use this with care in situations which require portability
+(including to past versions of the Mac OS X using the previous
+.Nm regex
+implementation).
+.Pp
+For enhanced basic REs,
+.Ql \&+ ,
+.Ql \&?
+and
+.Ql \&|
+remain regular characters, but
+.Ql \e+ ,
+.Ql \e?
+and
+.Ql \e|
+have the same special meaning as the unescaped characters do for
+extended REs, i.e., one or more matches, zero or one matches and alteration,
+respectively.
+For enhanced extended REs,
+back references are available.
+Additional enhanced features are listed below.
+.Pp
+Within a bracket expression, most characters lose their magic.
+This also applies to the additional enhanced features, which don't operate
+inside a bracket expression.
+.Ss Assertions (available for both enhanced basic and enhanced extended REs)
+In addition to
+.Ql \&^
+and
+.Ql \&$
+(the assertions that match the null string at the beginning and end of line,
+respectively), the following assertions become available:
+.Bl -tag -width ".Sy \eB" -offset indent
+.It Sy \e<
+Matches the null string at the beginning of a word.
+This is equivalent to
+.Ql [[:<:]] .
+.It Sy \e>
+Matches the null string at the end of a word.
+This is equivalent to
+.Ql [[:>:]] .
+.It Sy \eb
+Matches the null string at a word boundary (either the beginning or end of
+a word).
+.It Sy \eB
+Matches the null string where there is no word boundary.
+This is the opposite of
+.Ql \eb .
+.El
+.Ss Shortcuts (available for both enhanced basic and enhanced extended REs)
+The following shortcuts can be used to replace more complicated
+bracket expressions.
+.Bl -tag -width ".Sy \eD" -offset indent
+.It Sy \ed
+Matches a digit character.
+This is equivalent to
+.Ql [[:digit:]] .
+.It Sy \eD
+Matches a non-digit character.
+This is equivalent to
+.Ql [^[:digit:]] .
+.It Sy \es
+Matches a space character.
+This is equivalent to
+.Ql [[:space:]] .
+.It Sy \eS
+Matches a non-space character.
+This is equivalent to
+.Ql [^[:space:]] .
+.It Sy \ew
+Matches a word character.
+This is equivalent to
+.Ql [[:alnum:]_] .
+.It Sy \eW
+Matches a non-word character.
+This is equivalent to
+.Ql [^[:alnum:]_] .
+.El
+.Ss Literal Sequences (available for both enhanced basic and enhanced extended REs)
+Literals are normally just ordinary characters that are matched directly.
+Under enhanced mode, certain character sequences are
+converted to specific literals.
+.Bl -tag -width ".Sy \ea" -offset indent
+.It Sy \ea
+The
+.Dq bell
+character (ASCII code 7).
+.It Sy \ee
+The
+.Dq escape
+character (ASCII code 27).
+.It Sy \ef
+The
+.Dq form-feed
+character (ASCII code 12).
+.It Sy \en
+The
+.Dq new-line/line-feed
+character (ASCII code 10).
+.It Sy \er
+The
+.Dq carriage-return
+character (ASCII code 13).
+.It Sy \et
+The
+.Dq horizontal-tab
+character (ASCII code 9).
+.El
+.Pp
+Literals can also be specified directly, using their wide character values.
+Note that when matching a multibyte character string, the string's bytes
+are converted to wide character before comparing.
+This means that a single literal wide character value may match more than
+one string byte, depending on the locale's wide character encoding.
+.Bl -tag -width ".Sy \ex{ Ns Em x.. Ns Sy \&}" -offset indent
+.It Sy \ex Ns Em x..
+An arbitray eight-bit value.
+The
+.Em x..
+sequence represents zero, one or two hexadecimal digits.
+(Note: if
+.Em x..
+is less than two hexadecimal digits, and the character following this sequence
+happens to be a hexadecimal digit, use the (following) brace form to avoid
+confusion.)
+.It Sy \ex{ Ns Em x.. Ns Sy \&}
+An arbitrary, up to 32-bit value.
+The
+.Em x..
+sequence is an arbitrary sequence of hexadecimal digits that is long enough
+to represent the necessary value.
+.El
+.Ss Inline Literal Mode (available for both enhanced basic and enhanced extended REs)
+A
+.Ql \eQ
+sequence causes literal
+.Pq Dq quote
+mode to be entered,
+while
+.Ql \eE
+ends literal mode, and returns to normal regular expression processing.
+This is similar to specifying the
+.Dv REG_NOSPEC
+(or
+.Dv REG_LITERAL )
+option to
+.Fn regcomp ,
+except that rather than applying to the whole RE string, it only applies to
+the part between the
+.Ql \eQ
+and
+.Ql \eE .
+Note that it is not possible to have a
+.Ql \eE
+in the middle of an inline literal range, as that would terminate literal mode
+prematurely.
+.Ss Minimal Repetitions (available for enhanced extended REs only)
+By default, the repetition operators,
+.Ql \&* ,
+.Em bound ,
+.Ql \&?
+and
+.Ql \&+
+are
+.Em greedy ;
+they try to match as many times as possible.
+In enhanced mode, appending a
+.Ql \&?
+to a repetition operator makes it minimal (or
+.Em ungreedy ) ;
+it tries to match the fewest number of times (including zero times, as
+appropriate).
+.Pp
+For example, against the string
+.Ql aaa ,
+the RE
+.Ql a*
+would match the entire string,
+while
+.Ql a*?
+would match the null string at the beginning of the line
+(matches zero times).
+Likewise, against the string
+.Ql ababab ,
+the RE
+.Ql .*b ,
+would also match the entire string,
+while
+.Ql .*?b
+would only match the first two characters.
+.Pp
+The
+.Fn regcomp
+flag
+.Dv REG_UNGREEDY
+will make the regular
+.Pq greedy
+repetition operators ungreedy by default.
+Appending
+.Ql \&?
+makes them greedy again.
+.Pp
+Note that minimal repetitions are not specified by an official
+standard, so there may be differences between different implementations.
+In the current implementation, minimal repetitions have a high precedence,
+and can cause other standards requirements to be violated.
+For instance, on the string
+.Ql aaaaa ,
+the RE
+.Ql (aaa??)*
+will only match the first four characters, violating the rules that the longest
+possible match is made and the longest subexpressions are matched.
+Using
+.Ql (aaa??)*$
+forces the entire string to be matched.
+.Ss Non-capturing Parenthesized Subexpressions (available for enhanced extended REs only)
+Normally, the match offsets to parenthesized subexpressions are
+recorded in the
+.Fa pmatch
+array (that is, when
+.Dv REG_NOSUB
+is not specified, and
+.Fa nmatch
+is large enough to encompass the parenthesized subexpression in question).
+In enhanced mode, if the first two characters following the left parenthesis
+are
+.Ql ?: ,
+grouping of the remaining contents is done, but the corresponding offsets are
+not recorded in the
+.Fa pmatch
+array.
+For example, against the string
+.Ql fubar ,
+the RE
+.Ql (fu)(bar)
+would have two subexpression matches in
+.Fa pmatch ;
+the first for
+.Ql fu
+and the second for
+.Ql bar .
+But with the RE
+.Ql (?:fu)(bar) ,
+there would only be one subexpression match, that of
+.Ql bar .
+Furthermore,
+against the string
+.Ql fufubar ,
+the RE
+.Ql (?fu)*(bar)
+would again match the entire string, but only
+.Ql bar
+would be recorded in
+.Fa pmatch .
+.Ss Inline Options (available for enhanced extended REs only)
+Like the inline literal mode mentioned above, other options can be switched
+on and off for part of a RE.
+.Ql (? Ns Em o.. Ns \&)
+will turn on the options specified in
+.Em o..
+(one or more options characters; see below), while
+.Ql (?- Ns Em o.. Ns \&)
+will turn off the specified options, and
+.Ql (? Ns Em o1.. Ns \&- Ns Em o2.. Ns \&)
+will turn on the first set of options, and turn off the second set.
+.Pp
+The available options are:
+.Bl -tag -width ".Sy \&U" -offset indent
+.It Sy \&i
+Turning on this option will ignore case during matching, while turning off
+will restore case-sensitive matching.
+If
+.Dv REG_ICASE
+was specified to
+.Fn regcomp ,
+this option can be use to turn that off.
+.It Sy \&n
+Turn on or off special handling of the newline character.
+If
+.Dv REG_NEWLINE
+was specified to
+.Fn regcomp ,
+this option can be use to turn that off.
+.It Sy \&U
+Turning on this option will make ungreedy repetitions the default, while
+turning off will make greedy repetitions the default.
+If
+.Dv REG_UNGREEDY
+was specified to
+.Fn regcomp ,
+this option can be use to turn that off.
+.El
+.Pp
+The scope of the option change begins immediately following the right
+parenthesis,
+but up to the end of the enclosing subexpression (if any).
+Thus, for example, given the RE
+.Ql (fu(?i)bar)baz ,
+the
+.Ql fu
+portion matches case sensitively,
+.Ql bar
+matches case insensitively, and
+.Ql baz
+matches case sensitively again (since is it outside the scope of the
+subexpression in which the inline option was specified).
+.Pp
+The inline options syntax can be combined with the non-capturing parenthesized
+subexpression to limit the option scope to just that of the subexpression.
+Then, for example,
+.Ql fu(?i:bar)baz
+is similar to the previous example, except for the parenthesize subexpression
+around
+.Ql fu(?i)bar
+in the previous example.
+.Ss Inline Comments (available for enhanced extended REs only)
+The syntax
+.Ql (?# Ns Em comment Ns \&)
+can be used to embed comments within a RE.
+Note that
+.Em comment
+can not contain a right parenthesis.
+Also note that while syntactically, option characters can be added before
+the
+.Ql \&#
+character, they will be ignored.
 .Sh SEE ALSO
 .Xr regex 3
 .Rs
@@ -483,4 +817,4 @@ The
 definition given above
 is current consensus among implementors as to the right interpretation.
 .Pp
-The syntax for word boundaries is incredibly ugly.
+The bracket syntax for word boundaries is incredibly ugly.
similarity index 69%
rename from lib/libc/regex/regex.3
rename to lib/libc/tre-regex/regex.3
index 38d11c9..f176d42 100644 (file)
 .\"
 .\"    @(#)regex.3     8.4 (Berkeley) 3/20/94
 .\" $FreeBSD: src/lib/libc/regex/regex.3,v 1.21 2007/01/09 00:28:04 imp Exp $
-.\" $DragonFly: src/lib/libc/regex/regex.3,v 1.5 2008/06/02 06:50:08 hasso Exp $
 .\"
-.Dd August 17, 2005
+.Dd August 6, 2015
 .Dt REGEX 3
 .Os
 .Sh NAME
 .Nm regcomp ,
-.Nm regexec ,
+.Nm regcomp_l ,
 .Nm regerror ,
-.Nm regfree
+.Nm regexec ,
+.Nm regfree ,
+.Nm regncomp ,
+.Nm regncomp_l ,
+.Nm regnexec ,
+.Nm regnwcomp ,
+.Nm regnwcomp_l ,
+.Nm regnwexec ,
+.Nm regwcomp ,
+.Nm regwcomp_l ,
+.Nm regwexec
 .Nd regular-expression library
-.Sh LIBRARY
-.Lb libc
 .Sh SYNOPSIS
+.Sy (Standards-compliant APIs)
+.Pp
 .In regex.h
 .Ft int
 .Fo regcomp
-.Fa "regex_t * restrict preg" "const char * restrict pattern" "int cflags"
-.Fc
-.Ft int
-.Fo regexec
-.Fa "const regex_t * restrict preg" "const char * restrict string"
-.Fa "size_t nmatch" "regmatch_t pmatch[restrict]" "int eflags"
+.Fa "regex_t *restrict preg"
+.Fa "const char *restrict pattern"
+.Fa "int cflags"
 .Fc
 .Ft size_t
 .Fo regerror
-.Fa "int errcode" "const regex_t * restrict preg"
-.Fa "char * restrict errbuf" "size_t errbuf_size"
+.Fa "int errcode"
+.Fa "const regex_t *restrict preg"
+.Fa "char *restrict errbuf"
+.Fa "size_t errbuf_size"
+.Fc
+.Ft int
+.Fo regexec
+.Fa "const regex_t *restrict preg"
+.Fa "const char *restrict string"
+.Fa "size_t nmatch"
+.Fa "regmatch_t pmatch[restrict]"
+.Fa "int eflags"
 .Fc
 .Ft void
-.Fn regfree "regex_t *preg"
+.Fo regfree
+.Fa "regex_t *preg"
+.Fc
+.Pp
+.Sy (Non-portable extensions)
+.Ft int
+.Fo regncomp
+.Fa "regex_t *restrict preg"
+.Fa "const char *restrict pattern"
+.Fa "size_t len"
+.Fa "int cflags"
+.Fc
+.Ft int
+.Fo regnexec
+.Fa "const regex_t *restrict preg"
+.Fa "const char *restrict string"
+.Fa "size_t len"
+.Fa "size_t nmatch"
+.Fa "regmatch_t pmatch[restrict]"
+.Fa "int eflags"
+.Fc
+.Ft int
+.Fo regwcomp
+.Fa "regex_t *restrict preg"
+.Fa "const wchar_t *restrict widepat"
+.Fa "int cflags"
+.Fc
+.Ft int
+.Fo regwexec
+.Fa "const regex_t *restrict preg"
+.Fa "const wchar_t *restrict widestr"
+.Fa "size_t nmatch"
+.Fa "regmatch_t pmatch[restrict]"
+.Fa "int eflags"
+.Fc
+.Ft int
+.Fo regwncomp
+.Fa "regex_t *restrict preg"
+.Fa "const wchar_t *restrict widepat"
+.Fa "size_t len"
+.Fa "int cflags"
+.Fc
+.Ft int
+.Fo regwnexec
+.Fa "const regex_t *restrict preg"
+.Fa "const wchar_t *restrict widestr"
+.Fa "size_t len"
+.Fa "size_t nmatch"
+.Fa "regmatch_t pmatch[restrict]"
+.Fa "int eflags"
+.Fc
+.In regex.h
+.In xlocale.h
+.Ft int
+.Fo regcomp_l
+.Fa "regex_t *restrict preg"
+.Fa "const char *restrict pattern"
+.Fa "int cflags"
+.Fa "locale_t restrict"
+.Fc
+.Ft int
+.Fo regncomp_l
+.Fa "regex_t *restrict preg"
+.Fa "const char *restrict pattern"
+.Fa "size_t len"
+.Fa "int cflags"
+.Fa "locale_t restrict"
+.Fc
+.Ft int
+.Fo regwcomp_l
+.Fa "regex_t *restrict preg"
+.Fa "const wchar_t *restrict widepat"
+.Fa "int cflags"
+.Fa "locale_t restrict"
+.Fc
+.Ft int
+.Fo regwncomp_l
+.Fa "regex_t *restrict preg"
+.Fa "const wchar_t *restrict widepat"
+.Fa "size_t len"
+.Fa "int cflags"
+.Fa "locale_t restrict"
+.Fc
 .Sh DESCRIPTION
 These routines implement
 .St -p1003.2
@@ -72,12 +170,11 @@ see
 The
 .Fn regcomp
 function
-compiles an RE written as a string into an internal form,
+compiles an RE, written as a string, into an internal form.
 .Fn regexec
-matches that internal form against a string and reports results,
+matches that internal form against a string and reports results.
 .Fn regerror
-transforms error codes from either into human-readable messages,
-and
+transforms error codes from either into human-readable messages.
 .Fn regfree
 frees any dynamically-allocated storage used by the internal form
 of an RE.
@@ -142,6 +239,9 @@ and
 may not be used
 in the same call to
 .Fn regcomp .
+.It Dv REG_LITERAL
+An alias of
+.Dv REG_NOSPEC .
 .It Dv REG_ICASE
 Compile for matching that ignores upper/lower case distinctions.
 See
@@ -167,6 +267,16 @@ and the
 anchor matches the null string before any newline in the
 string in addition to its normal function.
 .It Dv REG_PEND
+(Note that
+.Dv REG_PEND
+is not recognized by any of the wide character or
+.Dq Nm n
+variants.
+Besides, the
+.Dq Nm n
+variants can be used instead of
+.Dv REG_PEND ;
+see EXTENDED APIS below.)
 The regular expression ends,
 not at the first NUL,
 but just before the character pointed to by the
@@ -184,6 +294,30 @@ 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_ENHANCED
+Recognized enhanced regular expression features; see
+.Xr re_format 7
+for details.
+This is an extension not specified by
+.St -p1003.2 ,
+and should be used with
+caution in software intended to be portable to other systems.
+.It Dv REG_MINIMAL
+Use minimal (non-greedy) repetitions instead of the normal greedy ones; see
+.Xr re_format 7
+for details.
+(This only applies when both
+.Dv REG_ENHANCED
+and
+.Dv REG_EXTENDED
+are also set.)
+This is an extension not specified by
+.St -p1003.2 ,
+and should be used with
+caution in software intended to be portable to other systems.
+.It Dv REG_UNGREEDY
+Alias of
+.Dv REG_MINIMAL .
 .El
 .Pp
 When successful,
@@ -502,7 +636,95 @@ is undefined.
 None of these functions references global variables except for tables
 of constants;
 all are safe for use from multiple threads if the arguments are safe.
+.Sh EXTENDED APIS
+These extended APIs are available in Mac OS X 10.8 and beyond, when the
+deployment target is 10.8 or later.
+It should also be noted that any of the
+.Fn regcomp
+variants may be used to initialize a
+.Ft regex_t
+structure, that can then be passed to any of the
+.Fn regexec
+variants.
+So it is quite legal to compile a wide character RE and use it to match a
+multibyte character string, or vice versa.
+.Pp
+The
+.Fn regncomp
+routine compiles regular expressions like
+.Fn regcomp ,
+but the length of the regular expression string is specified, allowing a string
+that is not NUL terminated and/or contains NUL characters.
+This is a modern replacement for using
+.Fn regcomp
+with the
+.Dv REG_PEND
+option.
+.Pp
+Similarly, the
+.Fn regnexec
+routine is like
+.Fn regexec ,
+but the length of the string to match is specified, allowing a string
+that is not NUL terminated and/or contains NUL characters.
+.Pp
+The
+.Fn regwcomp
+and
+.Fn regwexec
+variants take a wide-character
+.Vt ( wchar_t )
+string for the regular expression and string to match.
+And
+.Fn regwncomp
+and
+.Fn regwnexec
+are variants that allow specifying the wide character string length, and
+so allows wide character strings that are not NUL terminated and/or
+contains NUL characters.
+.Sh INTERACTION WITH THE LOCALE
+When
+.Fn regcomp
+or one of its variants is run, the regular expression is compiled into an
+internal form, which may include specific information about the locale currently
+in effect, such as equivalence classes or multi-character collation symbols.
+So a reference to the current locale is also stored with the internal form,
+so that when
+.Fn regexec
+is run, it can use the same locale (even if the locale is changed in-between
+the calls to
+.Fn regcomp
+and
+.Fn regexec ) .
+.Pp
+To provide more direct control over which locale is used,
+routines with
+.Dq Nm _l
+appended to their names are provided that work just like the variants
+without the
+.Dq Nm _l ,
+except that a locale (via a
+.Vt locale_t
+variable type) is specified directly.
+Note that only variants of
+.Fn regcomp
+have
+.Dq Nm _l
+variants, since the
+.Fn regexec
+variants just use the reference to the locale stored in the internal form.
 .Sh IMPLEMENTATION CHOICES
+The
+.Nm regex
+implementation in Mac OS X 10.8 and later is based on a heavily modified subset
+of TRE (http://laurikari.net/tre/).
+This provides improved performance, better conformance and additional features.
+However, both API and binary compatibility have been maintained with previous
+releases, so binaries
+built on previous releases should work on 10.8 and later, and binaries built on
+10.8 and later should be able to run on previous releases (as long as none of
+the new variants or new features are used.
+.Pp
 There are a number of decisions that
 .St -p1003.2
 leaves up to the implementor,
@@ -551,7 +773,11 @@ A repetition operator
 .Ql +\& ,
 or bounds)
 cannot follow another
-repetition operator.
+repetition operator, except for the use of
+.Ql ?\&
+for minimal repetition (for enhanced extended REs; see
+.Xr re_format 7
+for details).
 A repetition operator cannot begin an expression or subexpression
 or follow
 .Ql ^\&
@@ -653,43 +879,43 @@ sections 2.8 (Regular Expression Notation)
 and
 B.5 (C Binding for Regular Expression Matching).
 .Sh HISTORY
-Originally written by
-.An Henry Spencer .
-Altered for inclusion in the
+The
+.Nm regex
+implementation is based on a heavily modified subset of TRE
+(http://laurikari.net/tre/), originally written by Ville Laurikari.
+Previous releases used an implementation originally written by
+.An Henry Spencer ,
+and altered for inclusion in the
 .Bx 4.4
 distribution.
 .Sh BUGS
-This is an alpha release with known defects.
-Please report problems.
+The beginning-of-line and end-of-line anchors (
+.Dq ^\&
+and
+.Dq $\& )
+are currently implemented so that repetitions can not be applied to them.
+The standards are unclear about whether this is legal, but other
+.Nm regex
+packages do support this case.
+It is best to avoid this non-portable (and not really very useful) case.
 .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.
-The
-.Fn regexec
-function
-is largely insensitive to RE complexity
-.Em except
-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.
+variants use one of two internal matching engines.
+The normal one is linear worst-case time in the length of the text being
+searched, and quadratic worst-case time in the length of the used regular
+expression.
+When back-references are used, a slower, backtracking engine is used.
+While all backtracking matching engines suffer from extreme slowness for certain
+pathological cases, the normal engines doesn't suffer from these cases.
+It is advised to avoid back-references whenever possible.
 .Pp
 The
 .Fn regcomp
-function
+variants
 implements bounded repetitions by macro expansion,
 which is costly in time and space if counts are large
 or bounded repetitions are nested.
@@ -697,12 +923,6 @@ An RE like, say,
 .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.
-Notably,
-certain kinds of internal overflow,
-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 ,
 things like
@@ -721,8 +941,3 @@ 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/tre-regex/regex.h b/lib/libc/tre-regex/regex.h
new file mode 100644 (file)
index 0000000..88a670a
--- /dev/null
@@ -0,0 +1,232 @@
+/*
+ * Copyright (c) 2001-2009 Ville Laurikari <vl@iki.fi>
+ * All rights reserved.
+ *
+ * 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.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER 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 COPYRIGHT
+ * HOLDER 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.
+ *
+ */
+
+#ifndef _REGEX_H_
+#define        _REGEX_H_
+
+#include <sys/cdefs.h>
+#include <sys/types.h>
+#include <wchar.h>
+
+#define tre_regcomp   regcomp
+#define tre_regexec   regexec
+#define tre_regerror  regerror
+#define tre_regfree   regfree
+
+#define tre_regwcomp  regwcomp
+#define tre_regwexec  regwexec
+#define tre_regncomp  regncomp
+#define tre_regnexec  regnexec
+#define tre_regnwcomp regnwcomp
+#define tre_regnwexec regnwexec
+
+typedef enum {
+  REG_OK = 0,          /* No error. */
+  REG_NOMATCH,         /* No match. */
+  REG_BADPAT,          /* Invalid regexp. */
+  REG_ECOLLATE,                /* Unknown collating element. */
+  REG_ECTYPE,          /* Unknown character class name. */
+  REG_EESCAPE,         /* Trailing backslash. */
+  REG_ESUBREG,         /* Invalid back reference. */
+  REG_EBRACK,          /* "[]" imbalance */
+  REG_EPAREN,          /* "\(\)" or "()" imbalance */
+  REG_EBRACE,          /* "\{\}" or "{}" imbalance */
+  REG_BADBR,           /* Invalid content of {} */
+  REG_ERANGE,          /* Invalid use of range operator */
+  REG_ESPACE,          /* Out of memory.  */
+  REG_BADRPT,           /* Invalid use of repetition operators. */
+  REG_EMPTY,            /* rexexp was zero-length string */
+  REG_INVARG,           /* invalid argument to regex routine */
+  REG_ILLSEQ            /* illegal byte sequence */
+} reg_errcode_t;
+
+enum {
+  TRE_CONFIG_APPROX,
+  TRE_CONFIG_WCHAR,
+  TRE_CONFIG_MULTIBYTE,
+  TRE_CONFIG_SYSTEM_ABI,
+  TRE_CONFIG_VERSION
+};
+
+typedef int regoff_t;
+typedef wchar_t tre_char_t;
+
+typedef struct {
+  int re_magic;
+  size_t re_nsub;  /* Number of parenthesized subexpressions. */
+  const void *re_endp; /* regex string end pointer (REG_PEND) */
+  void *value;    /* For internal use only. */
+} regex_t;
+
+typedef struct {
+  regoff_t rm_so;
+  regoff_t rm_eo;
+} regmatch_t;
+
+/* Approximate matching parameter struct. */
+typedef struct {
+  int cost_ins;                /* Default cost of an inserted character. */
+  int cost_del;                /* Default cost of a deleted character. */
+  int cost_subst;      /* Default cost of a substituted character. */
+  int max_cost;                /* Maximum allowed cost of a match. */
+
+  int max_ins;         /* Maximum allowed number of inserts. */
+  int max_del;         /* Maximum allowed number of deletes. */
+  int max_subst;       /* Maximum allowed number of substitutes. */
+  int max_err;         /* Maximum allowed number of errors total. */
+} regaparams_t;
+
+/* Approximate matching result struct. */
+typedef struct {
+  size_t nmatch;       /* Length of pmatch[] array. */
+  regmatch_t *pmatch;  /* Submatch data. */
+  int cost;            /* Cost of the match. */
+  int num_ins;         /* Number of inserts in the match. */
+  int num_del;         /* Number of deletes in the match. */
+  int num_subst;       /* Number of substitutes in the match. */
+} regamatch_t;
+
+typedef struct {
+  int (*get_next_char)(tre_char_t *c, unsigned int *pos_add, void *context);
+  void (*rewind)(size_t pos, void *context);
+  int (*compare)(size_t pos1, size_t pos2, size_t len, void *context);
+  void *context;
+} tre_str_source;
+
+/* POSIX tre_regcomp() flags. */
+#define REG_EXTENDED   1
+#define REG_ICASE      (REG_EXTENDED << 1)
+#define REG_NEWLINE    (REG_ICASE << 1)
+#define REG_NOSUB      (REG_NEWLINE << 1)
+
+/* Extra tre_regcomp() flags. */
+#define REG_BASIC      0
+#define REG_LITERAL    (REG_NOSUB << 1)
+#define REG_RIGHT_ASSOC (REG_LITERAL << 1)
+#define REG_UNGREEDY    (REG_RIGHT_ASSOC << 1)
+#define REG_PEND       (REG_UNGREEDY << 1)
+#define REG_ENHANCED   (REG_PEND << 1)
+
+/* alias regcomp flags. */
+#define REG_NOSPEC     REG_LITERAL
+#define REG_MINIMAL    REG_UNGREEDY
+
+/* POSIX tre_regexec() flags. */
+#define REG_NOTBOL     1
+#define REG_NOTEOL     (REG_NOTBOL << 1)
+#define REG_STARTEND   (REG_NOTEOL << 1)
+#define        REG_BACKR       (REG_STARTEND << 1)
+
+/* Extra tre_regexec() flags. */
+#define REG_APPROX_MATCHER      (REG_NOTEOL << 1)
+#define REG_BACKTRACKING_MATCHER (REG_APPROX_MATCHER << 1)
+
+/* The maximum number of iterations in a bound expression. */
+#define RE_DUP_MAX 255
+
+#define _REG_nexec 1
+
+__BEGIN_DECLS
+
+/* The POSIX.2 regexp functions */
+int
+tre_regcomp(regex_t *preg, const char *regex, int cflags);
+
+int
+tre_regexec(const regex_t *preg, const char *string, size_t nmatch,
+       regmatch_t pmatch[], int eflags);
+
+size_t
+tre_regerror(int errcode, const regex_t *preg, char *errbuf,
+        size_t errbuf_size);
+
+void
+tre_regfree(regex_t *preg);
+
+/* Wide character versions (not in POSIX.2). */
+int
+tre_regwcomp(regex_t *preg, const wchar_t *regex, int cflags);
+
+int
+tre_regwexec(const regex_t *preg, const wchar_t *string,
+        size_t nmatch, regmatch_t pmatch[], int eflags);
+
+/* Versions with a maximum length argument and therefore the capability to
+   handle null characters in the middle of the strings (not in POSIX.2). */
+int
+tre_regncomp(regex_t *preg, const char *regex, size_t len, int cflags);
+
+int
+tre_regnexec(const regex_t *preg, const char *string, size_t len,
+        size_t nmatch, regmatch_t pmatch[], int eflags);
+
+int
+tre_regwncomp(regex_t *preg, const wchar_t *regex, size_t len, int cflags);
+
+int
+tre_regwnexec(const regex_t *preg, const wchar_t *string, size_t len,
+         size_t nmatch, regmatch_t pmatch[], int eflags);
+
+/* Returns the version string. The returned string is static. */
+char *
+tre_version(void);
+
+/* Returns the value for a config parameter.  The type to which `result'
+   must point to depends of the value of `query', see documentation for
+   more details. */
+int
+tre_config(int query, void *result);
+
+/* Returns 1 if the compiled pattern has back references, 0 if not. */
+int
+tre_have_backrefs(const regex_t *preg);
+
+/* Returns 1 if the compiled pattern uses approximate matching features,
+   0 if not. */
+int
+tre_have_approx(const regex_t *preg);
+__END_DECLS
+
+/* The POSIX.2 regexp functions, locale version */
+int
+tre_regcomp_l(regex_t *preg, const char *regex, int cflags, locale_t locale);
+
+int
+tre_regncomp_l(regex_t *preg, const char *regex, size_t len, int cflags,
+    locale_t locale);
+
+int
+tre_regwcomp_l(regex_t *preg, const wchar_t *regex, int cflags,
+    locale_t locale);
+
+int
+tre_regwncomp_l(regex_t *preg, const wchar_t *regex, size_t len, int cflags,
+    locale_t locale);
+
+#endif /* !_REGEX_H_ */
diff --git a/lib/libc/tre-regex/tre.h b/lib/libc/tre-regex/tre.h
new file mode 100644 (file)
index 0000000..536496b
--- /dev/null
@@ -0,0 +1,8 @@
+#ifndef TRE_H
+#define TRE_H 1
+
+#define RE_MAGIC  ((('r'^0200)<<8) | 'e')
+
+#include "regex.h"
+
+#endif