Allow -DNO_STRICT_REGEX to restore historic regex behavior

Allow restoring the behavior of '{' as described in regex(3).
Ie. only treat it as start of bounds if followed by a digit.

If NO_STRICT_REGEX is not defined, the behavior introduced by
commit a4a801688c909ef39cbcbc3488bc4fdbabd69d66 is retained,
otherwise the previous behavior is restored.

Differential Revision: https://reviews.freebsd.org/D45134

regex: fix freeing g->charjump in low memory condition

computejumps() moves g->charjump to a position relativ to the value of
CHAR_MIN. As such, g->charjump doesn't necessarily point to the address
actually allocated. While regfree() takes that into account, the low
memory handling in regcomp_internal() doesn't. Fix that by free'ing
the actually allocated address, as in regfree().

MFC After: 2 weeks
Reviewed by: imp,jrtc27
Pull Request: https://github.com/freebsd/freebsd-src/pull/692

regex: mixed sets are misidentified as singletons

Fix "singleton" function used by regcomp() to turn character set matches
into exact character matches if a character set has exactly one
element.

The underlying cset representation is complex; most critically it
records"small" characters (codepoint less than either 128
or 256 depending on locale) in a bit vector, and "wide" characters in
a secondary array.

Unfortunately the "singleton" function uses to identify singleton sets
treated a cset as a singleton if either the "small" or the "wide" sets
had exactly one element (it would then ignore the other set).

The easiest way to demonstrate this bug:

$ export LANG=C.UTF-8
$ echo 'a' | grep '[abà]'

It should match (and print "a") but instead it doesn't match because the
single accented character in the set is misinterpreted as a singleton.

Reviewed by: kevans, yuripv
Obtained from: illumos
Differential Revision: https://reviews.freebsd.org/D43149

lib: Remove ancient SCCS tags.

Remove ancient SCCS tags from the tree, automated scripting, with two
minor fixup to keep things compiling. All the common forms in the tree
were removed with a perl script.

Sponsored by: Netflix

libc: Purge unneeded cdefs.h

These sys/cdefs.h are not needed. Purge them. They are mostly left-over
from the $FreeBSD$ removal. A few in libc are still required for macros
that cdefs.h defines. Keep those.

Sponsored by: Netflix
Differential Revision: https://reviews.freebsd.org/D42385

regcomp: use unsigned char when testing for escapes

- cast GETNEXT to unsigned where it is being promoted to int to prevent
sign-extension (really it would have been better for PEEK*() and
GETNEXT() to return unsigned char; this would have removed a ton of
(uch) casts, but it is too intrusive for now).
- fix an isalpha that should have been iswalpha

PR: 264275, 274032
Reviewed by: kevans, eugen (previous version)
Obtained from: NetBSD
Differential Revision: https://reviews.freebsd.org/D41947

Remove $FreeBSD$: one-line .c pattern

Remove /^[\s*]*__FBSDID\("\$FreeBSD\$"\);?\s*\n/

libc: drop "All rights reserved" from Foundation copyrights

This has already been done for most files that have the Foundation as
the only listed copyright holder. Do it now for files that list
multiple copyright holders, but have the Foundation copyright in its own
section.

Sponsored by: The FreeBSD Foundation

libc: regex: rework unsafe pointer arithmetic

regcomp.c uses the "start + count < end" idiom to check that there are
"count" bytes available in an array of char "start" and "end" both point to.

This is fine, unless "start + count" goes beyond the last element of the
array. In this case, pedantic interpretation of the C standard makes the
comparison of such a pointer against "end" undefined, and optimizers from
hell will happily remove as much code as possible because of this.

An example of this occurs in regcomp.c's bothcases(), which defines
bracket[3], sets "next" to "bracket" and "end" to "bracket + 2". Then it
invokes p_bracket(), which starts with "if (p->next + 5 < p->end)"...

Because bothcases() and p_bracket() are static functions in regcomp.c, there
is a real risk of miscompilation if aggressive inlining happens.

The following diff rewrites the "start + count < end" constructs into "end -
start > count". Assuming "end" and "start" are always pointing in the array
(such as "bracket[3]" above), "end - start" is well-defined and can be
compared without trouble.

As a bonus, MORE2() implies MORE() therefore SEETWO() can be simplified a
bit.

PR: 252403

libc: regex: retire internal EMPTBR ("Empty branch present")

It was realized just a little too late that this was a hack that belonged in
individual regex(3)-using applications. It was surrounded in NOTYET and not
implemented in the engine, so remove it.

libregex: implement \b and \B (word boundary, not word boundary)

This is the last of the needed GNU expressions before we can unleash bsdgrep
by default. \b is effectively an agnostic equivalent of \< and \>, while
\B will match every space that isn't making a transition from
nonchar -> char or char -> nonchar.

libregex: implement \` and \' (begin-of-subj, end-of-subj)

These are GNU extensions, generally equivalent to ^ and $ except that the
new syntax will not match beginning of line after the first in a multi-line
expression or the end of line before absolute last in a multi-line
expression.

libregex: Implement a subset of the GNU extensions

The entire patch-set is not yet mature enough for commit, but this usable
subset is generally enough for googletest to be happy with and mostly map to
some existing concepts, so they're not as invasive.

The specific changes included here are:

- Branching in BREs with \|
- \w and \W for [[:alnum:]] and [^[:alnum:]] respectively
- \s and \S for [[:space:]] and [^[:space:]] respectively
- Additional quantifiers in BREs, \? and \+ (self-explanatory)

There's some #ifdef'd out work for allowing empty branches as a match-all.
This is a feature that's under assessment... future work will determine
how standard this behavior is and act accordingly.

regex(3): Interpret many escaped ordinary characters as EESCAPE

In IEEE 1003.1-2008 [1] and earlier revisions, BRE/ERE grammar allows for
any character to be escaped, but "ORD_CHAR preceded by an unescaped
<backslash> character [gives undefined results]".

Historically, we've interpreted an escaped ordinary character as the
ordinary character itself. This becomes problematic when some extensions
give special meanings to an otherwise ordinary character
(e.g. GNU's \b, \s, \w), meaning we may have two different valid
interpretations of the same sequence.

To make this easier to deal with and given that the standard calls this
undefined, we should throw an error (EESCAPE) if we run into this scenario
to ease transition into a state where some escaped ordinaries are blessed
with a special meaning -- it will either error out or have extended
behavior, rather than have two entirely different versions of undefined
behavior that leave the consumer of regex(3) guessing as to what behavior
will be used or leaving them with false impressions.

This change bumps the symbol version of regcomp to FBSD_1.6 and provides the
old escape semantics for legacy applications, just in case one has an older
application that would immediately turn into a pumpkin because of an
extraneous escape that's embedded or otherwise critical to its operation.

This is the final piece needed before enhancing libregex with GNU extensions
and flipping the switch on bsdgrep.

[1] http://pubs.opengroup.org/onlinepubs/9699919799.2016edition/

PR: 229925 (exp-run, courtesy of antoine)
Differential Revision: https://reviews.freebsd.org/D10510

lib/libc/regex: fix build with REDEBUG defined

Reviewed by: kevans
Differential Revision: https://reviews.freebsd.org/D21760

regcomp: revert part of r341838 which turned out to be unrelated
and caused issues with search in less.

PR: 234066
Reviewed by: pfg
Differential revision: https://reviews.freebsd.org/D18611

regcomp: reduce size of bitmap for multibyte locales

This fixes the obscure endless loop seen with case-insensitive
patterns containing characters in 128-255 range; originally
found running GNU grep test suite.

Our regex implementation being kludgy translates the characters
in case-insensitive pattern to bracket expression containing both
cases for the character and doesn't correctly handle the case when
original character is in bitmap and the other case is not, falling
into the endless loop going through in p_bracket(), ordinary(),
and bothcases().

Reducing the bitmap to 0-127 range for multibyte locales solves this
as none of these characters have other case mapping outside of bitmap.
We are also safe in the case when the original character outside of
bitmap has other case mapping in the bitmap (there are several of those
in our current ctype maps having unidirectional mapping into bitmap).

Reviewed by: bapt, kevans, pfg
Differential revision: https://reviews.freebsd.org/D18302

Add missing patch from r328240

regcomp uses some libc internal collation bits that are not available in the
libregex context. It's easy enough to bring in the needed parts that can
work in a libregex world, so do so.

Pointy hat to: me

regex(3): Resolve issues with higher WARNS levels

libc is set for WARNS=2, but the incoming libregex will use WARNS=6.
Sprinkle some casts and (void)bc's to alleviate the warnings that come along
with the higher WARNS level.

These 'bc' parameters could be outright removed, but as of right now they
will be used in some parts of libregex land. Silence the warnings instead
rather than flip-flopping.

General further adoption of SPDX licensing ID tags.

Mainly focus on files that use BSD 3-Clause license.

The Software Package Data Exchange (SPDX) group provides a specification
to make it easier for automated tools to detect and summarize well known
opensource licenses. We are gradually adopting the specification, noting
that the tags are considered only advisory and do not, in any way,
superceed or replace the license texts.

Special thanks to Wind River for providing access to "The Duke of
Highlander" tool: an older (2014) run over FreeBSD tree was useful as a
starting point.

Fix out-of-bounds read in libc/regex.

The bug is an out-of-bounds read detected with address sanitizer that
happens when 'sp' in p_b_coll_elems() includes NUL byte[s], e.g. if it's
equal to "GS\x00". In that case len will be equal to 4, and the
strncmp(cp->name, sp, len) call will succeed when cp->name is "GS" but the
cp->name[len] == '\0' comparison will cause the read to go out-of-bounds.

Checking the length using strlen() instead eliminates the issue.

The bug was found in LLVM with oss-fuzz:
https://reviews.llvm.org/D39380

MFC after: 1 week
Obtained from: Vlad Tsyrklevich through posting on openbsd-tech

regex(3): Handle invalid {} constructs consistently and adjust tests

Currently, regex(3) exhibits the following wrong behavior as demonstrated
with sed:

- echo "a{1,2,3}b" | sed -r "s/{/_/" (1)
- echo "a{1,2,3}b" | sed "s/\}/_/" (2)
- echo "a{1,2,3}b" | sed -r "s/{}/_/" (3)

Cases (1) and (3) should throw errors but they actually succeed, and (2)
throws an error when it should match the literal '}'. The correct behavior
was decided by comparing to the behavior with the equivalent BRE (1)(3) or
ERE (2) and consulting POSIX, along with some reasonable evaluation.

Tests were also adjusted/added accordingly.

PR: 166861
Reviewed by: emaste, ngie, pfg
Approved by: emaste (mentor)
MFC after: never
Differential Revision: https://reviews.freebsd.org/D10315

Correctly ignore branch operators in the top-level parser when applicable.

An oversight in r320742 caused BREs to become sensitive to the branching operator prematurely, which caused
breakage in some limited situations -- namely, those that tried to use branching in a BRE. Most of these scenarios
had already been corrected beforehand to properly use gsed or grep for GNU extensions, so the damage is
slightly mitigated.

Reported by: antoine

Reported by: antoine
Approved by: emaste (mentor)
Differential Revision: https://reviews.freebsd.org/D11522

Fix sparc64 libc build after r320742.

p_branch_empty was declared but never used due to an oversight. Use it as
designed, further comment on its return value.

Reported by: Jenkins (head-sparc64)
Reviewed by: emaste
Approved by: emaste (mentor)
MFC with: r320742
Differential Revision: https://reviews.freebsd.org/D11506

The impending libregex will implement GNU extensions to bring BREs and
EREs closer together. Prepare for this and reduce the diff of libregex changes by
refactoring and combining the top-level parsers for EREs/BREs ahead of time.

Branching functionality has been split out to make it easier to follow the combined
version of the top-level parser. It may also be enabled in the parsing context to make
it easier when libregex enables branching for BREs.

A branching context was also added for the various branching functions and so that
BREs, for instance, can determine if they're the first expression in a chain of expressions
within the current branch and treat '*' as ordinary if so.

This should have no functional impact and negligible performance impact.

Reviewed by: cem, emaste, pfg
Approved by: emaste (mentor)
MFC after: 1 month
Differential Revision: https://reviews.freebsd.org/D10920

Correct an out-of-bounds read in regcomp when the RE is bad.

When passed the invalid regular expression "a**", the error is
eventually detected and seterr() is called. It sets p->error
appropriatly and p->next and p->end to nuls which is a never used char
nuls[10] which is zeros due to .bss initialization. Unfortunatly,
p_ere_exp() and p_simp_re() both have fall through cases where they set
the error, decrement p->next and access it which means a read from what
ever .bss variable comes before nuls.

Found with regex_test:repet_multi and CHERI bounds checking.

Reviewed by: ngie, pfg, emaste
Obtained from: CheriBSD
Sponsored by: DARPA, AFRL
MFC after: 1 week
Differential Revision: https://reviews.freebsd.org/D10541

regex: unsign and constify some variables.

Taking some hints from the regex variant in nvi(1) and higher-level
compiler warnings, update some types in our regex(3) implementation.

Joint work with: Kyle Evans
MFC after: 2 weeks

libc: provide some bounds-checking through reallocarray(3).

reallocarray(3) is a non portable extension that originated in OpenBSD.
Given that it is already in FreeBSD's libc it is useful for the cases
where reallocation involves a multiplication.

MFC after: 2 weeks
Differential Revision: https://reviews.freebsd.org/D9955

Renumber copyright clause 4

Renumber cluase 4 to 3, per what everybody else did when BSD granted
them permission to remove clause 3. My insistance on keeping the same
numbering for legal reasons is too pedantic, so give up on that point.

Submitted by: Jan Schaumann <jschauma@stevens.edu>
Pull Request: https://github.com/freebsd/freebsd/pull/96

1) Eliminate possibility to call __*collate_range_cmp() with inclomplete
locale (which cause core dump) by removing whole 'table' argument
by which it passed.

2) Restore __collate_range_cmp() in __sccl().

3) Collating [a-z] range in regcomp() only for single bytes locales
(we can't do it now for other ones). In previous state only first 256
wchars are considered and all others are just silently dropped from the
range.

Back out non-collating [a-z] ranges.
Instead of changing whole course to another POSIX-permitted way
for consistency and uniformity I decide to completely ignore missing
regex fucntionality and concentrace on fixing bugs in what we have now,
too many small obstacles instead, counting ports.

Remove broken support for collation in [a-z] type ranges.
Only first 256 wide chars are considered currently, all other are just
dropped from the range. Proper implementation require reverse tables
database lookup, since objects are really big as max UTF-8 (1114112
code points), so just the same scanning as it was for 256 chars will
slow things down.

POSIX does not require collation for [a-z] type ranges and does not
prohibit it for non-POSIX locales. POSIX require collation for ranges
only for POSIX (or C) locale which is equal to ASCII and binary for
other chars, so we already have it.

No other *BSD implements collation for [a-z] type ranges.

Restore ABI compatibility with unused now __collate_range_cmp() which
is visible from outside (will be removed later).

libc/locale: Fix type breakage in __collate_range_cmp().

When collation support was brought in, the second and third
arguments in __collate_range_cmp() were changed from int to
wchar_t, breaking the ABI. Change them to a "char" type which
makes more sense and keeps the ABI compatible.

Also introduce __wcollate_range_cmp() which does work with wide
characters. This function is used only internally in libc so
we don't export it. Use the new function in glob(3), fnmatch(3),
and regexec(3).

PR: 179721
Suggested by: ache. jilles
MFC after: 3 weeks (perhaps partial only)

libc: spelling fixes.

Mostly on comments.

Revert r286465. Retesting it showed that it just works. it might have been
a local issue in my previous tests.

The regex code does not work with multibyte codesets like UTF-8.
In fact, it doesn't even work with single-byte codesets like ISO-8859-1.
The comparison blows up at index 128 (the range is 0 to UCHAR_MAX (255).

As a temporary workaround, all comparisons will be done in C locale
regardless of the environment setting. The regex library needs to be
updated to handle all codesets.

Obtained from: Dragonfly

computematchjumps(): fix allocator sizeof operand mismatch.

Mostly cosmetical warning.

Found by: Clang static analyzer

regex(3): Fix uninitialized pointer values.

CID: 405582 (also clang static checker)
CID: 1018724

Disallow pattern spaces which would cause intermediate calculations to
overflow size_t.

Obtained from: DragonFly (2841837793bd095a82f477e9c370cfe6cfb3862c dillon)
Security: CERT VU#695940
MFC after: 3 days

Plug a memory leak.

Obtained from: DragonFlyBSD (commit 5119ece)
MFC after: 2 weeks

regex(3): Add support for \< and \> word delimiters

Solaris and other OSs have support for \< and \> as word
delimiters in utilities like sed(1). These are useful to
have for general compatiblity with Solaris but should be
avoided for portability with other systems, including the
traditional BSDs.

Bump __FreeBSD_version as this is likely to affect some
userland utilities.

Reference:
https://www.illumos.org/issues/516

PR: bin/153257
Obtained from: Illumos
MFC after: 1 month

Revert r267675:

The code doesn't really benefit of using reallocf() in this case.
Also, the realloc() results being assigned temporary variable which
makes blind replacement with reallocf() mostly useless.

Pointed out by: stefanf, bde

regex: Make use of reallocf().

Use of reallocf is useful in libraries as we are not certain the
application will exit after NULL.

This somewhat reduces portability but if since you are building
this as part of libc it is likely you have our non-standard
reallocf(3) already.

Reviewed by: ache
MFC after: 5 days

Revert r265367:
Use of calloc instead of malloc in regex (from OpenBSD).

In this case the change makes no sense since we are using realloc() later.

Reported by: ache

regex: Use calloc instead of malloc.

Mostly to reduce differences with OpenBSD.

Obtained from: OpenBSD (CVS rev. 1.17)
MFC after: 3 days

regex: Remove some unreachable breaks.

This is based on a much bigger cleanup done in Illumos.

Reference:
https://www.illumos.org/issues/2077

MFC after: 1 week

Fix assignment of maximum bounadary.

Submitted by: Sascha Wildner <saw online de>
Obtained from: DragonFly rev fd39c81ba220f7ad6e4dc9b30d45e828cf58a1ad
MFC after: 2 weeks

Remove some duplicated copyright notices.

Approved by: dim (mentor)

Implement xlocale APIs from Darwin, mainly for use by libc++. This adds a
load of _l suffixed versions of various standard library functions that use
the global locale, making them take an explicit locale parameter. Also
adds support for per-thread locales. This work was funded by the FreeBSD
Foundation.

Please test any code you have that uses the C standard locale functions!

Reviewed by: das (gdtoa changes)
Approved by: dim (mentor)

Converting int to wint_t leads to broekn comparison of raw char
and encoded wint_t.

Spotted by: ache

- Don't handle out-of-memory condition
- Fix types of function arguments match their declaration

Reviewed by: delphij
Obtained from: NetBSD

A new jail(8) with a configuration file, to replace the work currently done
by /etc/rc.d/jail.

Create the altix project branch. The altix project will add support
for the SGI Altix 350 to FreeBSD/ia64. The hardware used for porting
is a two-module system, consisting of a base compute module and a
CPU expansion module. SGI's NUMAFlex architecture can be an excellent
platform to test CPU affinity and NUMA-aware features in FreeBSD.

- Import the HEAD csup code which is the basis for the cvsmode work.

Diff reduction against other *BSDs: ANSIfy function
prototypes. No function changes.

Per Regents of the University of Calfornia letter, remove advertising
clause.

# If I've done so improperly on a file, please let me know.

Directly include <runetype.h> for _CurrentRuneLocale, <_ctype.h> doesn't
include it in all cases.

Fix two problems with REG_ICASE that were introduced with the addition of
multibyte character support:
- In CHadd(), avoid writing past the end of the character set bitmap when
the opposite-case counterpart of wide characters with values less than
NC have values greater than or equal to NC.
- In CHaddtype(), fix a braino that caused alphabetic characters to be
added to all character classes! (but only with REG_ICASE)

PR: 71367

Make regular expression matching aware of multibyte characters. The general
idea is that we perform multibyte->wide character conversion while parsing
and compiling, then convert byte sequences to wide characters when they're
needed for comparison and stepping through the string during execution.

As with tr(1), the main complication is to efficiently represent sets of
characters in bracket expressions. The old bitmap representation is replaced
by a bitmap for the first 256 characters combined with a vector of individual
wide characters, a vector of character ranges (for [A-Z] etc.), and a vector
of character classes (for [[:alpha:]] etc.).

One other point of interest is that although the Boyer-Moore algorithm had
to be disabled in the general multibyte case, it is still enabled for UTF-8
because of its self-synchronizing nature. This greatly speeds up matching
by reducing the number of multibyte conversions that need to be done.

Remove incomplete support for multi-character collating elements. Remove
unused character category calculations.

Eliminate 61 warnings emitted at WARNS=2 (leaving 53 to go).
Only warnings that could be fixed without changing the generated object
code and without restructuring the source code have been handled.

Reviewed by: /sbin/md5

Add restrict type-qualifier.

Replace various spelling with FALLTHROUGH which is lint()able

Fix the style of the SCM ID's.
I believe have made all of libc .c's as consistent as possible.

Remove __P() usage.

Remove 'register' keyword.

The algorithm that computes the tables used in the BM search algorithm sometimes
access an array beyond it's length. This only happens in the last iteration of
a loop, and the value fetched is not used then, so the bug is a relatively
innocent one. Fix this by not fetching any value on the last iteration of said
loop.

Submitted by: MKI <mki@mozone.net>
MFC after: 1 week

altoffset() always returned whenever it recursed, because at the end
of the processing of the recursion, "scan" would be pointing to O_CH
(or O_QUEST), which would then be interpreted as being the end character
for altoffset().

We avoid this by properly increasing scan before leaving the switch.

Without this, something like (a?b?)?cc would result in a g->moffset of
1 instead of 2.

I added a case to the soon-to-be-imported regex(3) test code to catch
this error.

Add some casts here and there.

Do not free NULL pointers.

Deal with the signed/unsigned chars issue in a more proper manner. We
use a CHAR_MIN-based array, like elsewhere in the code.

Remove a number of unused variables (some due to the above change, one
that was left after a number of optimizing steps through the source).

Brucified by: bde

I hate signed chars.^W^W^W^W^WCast to unsigned char before using signed
chars as array indices.

Correct comment to work with test code.

Prevent out of bounds array access in some specific cases.

Use UCHAR_MAX consistently.

Enhance the optimization provided by pre-matching. Fix style bugs with
previous commits.

At the time we search the pattern for the "must" string, we now compute
the longest offset from the beginning of the pattern at which the must
string might be found. If that offset is found to be infinite (through
use of "+" or "*"), we set it to -1 to disable the heuristics applied
later.

After we are done with pre-matching, we use that offset and the point in
the text at which the must string was found to compute the earliest
point at which the pattern might be found.

Special care should be taken here. The variable "start" is passed to the
automata-processing functions fast() and slow() to indicate the point in
the text at which they should start working from. The real beginning of
the text is passed in a struct match variable m, which is used to check
for anchors. That variable, though, is initialized with "start", so we
must not adjust "start" before "m" is properly initialized.

Simple tests showed a speed increase from 100% to 400%, but they were
biased in that regexec() was called for the whole file instead of line
by line, and parenthized subexpressions were not searched for.

This change adds a single integer to the size of the "guts" structure,
and does not change the ABI.

Further improvements possible:

Since the speed increase observed here is so huge, one intuitive
optimization would be to introduce a bias in the function that computes
the "must" string so as to prefer a smaller string with a finite offset
over a larger one with an infinite offset. Tests have shown this to be a
bad idea, though, as the cost of false pre-matches far outweights the
benefits of a must offset, even in biased situations.

A number of other improvements suggest themselves, though:

* identify the cases where the pattern is identical to the must
string, and avoid entering fast() and slow() in these cases.

* compute the maximum offset from the must string to the end of
the pattern, and use that to set the point at which fast() and
slow() should give up trying to find a match, and return then
return to pre-matching.

* return all the way to pre-matching if a "match" was found and
later invalidated by back reference processing. Since back
references are evil and should be avoided anyway, this is of
little use.

Initialize variables used by the Boyer-Moore algorithm.

This should fix core dumps when the must pattern is of length
three or less.

Bug found by: knu

Add Boyler-Moore algorithm to pre-matching test.

The BM algorithm works by scanning the pattern from right to left,
and jumping as many characters as viable based on the text's mismatched
character and the pattern's already matched suffix.

This typically enable us to test only a fraction of the text's characters,
but has a worse performance than the straight-forward method for small
patterns. Because of this, the BM algorithm will only be used if the
pattern size is at least 4 characters.

Notice that this pre-matching is done on the largest substring of the
regular expression that _must_ be present on the text for a succesful
match to be possible at all.

For instance, "(xyzzy|grues)" will yield a null "must" substring, and,
therefore, not benefit from the BM algorithm at all. Because of the
lack of intelligence of the algorithm that finds the "must" string,
things like "charjump|matchjump" will also yield a null string. To
optimize that, "(char|match)jump" should be used.

The setup time (at regcomp()) for the BM algorithm will most likely
outweight any benefits for one-time matches. Given the slow regex(3)
we have, this is unlikely to be even perceptible, though.

The size of a regex_t structure is increased by 2*sizeof(char*) +
256*sizeof(int) + strlen(must)*sizeof(int). This is all inside the
regex_t's "guts", which is allocated dynamically by regcomp(). If
allocation of either of the two tables fail, the other one is freed.
In this case, the straight-forward algorithm is used for pre-matching.

Tests exercising the code path affected have shown a speed increase of
50% for "must" strings of length four or five.

API and ABI remain unchanged by this commit.

The patch submitted on the PR was not used, as it was non-functional.

PR: 14342

unsigned char cleanup
fix wrong index from p_simp_re()

PR: 8790
Submitted by: Alexander Viro <viro@math.psu.edu> (partially)

Replace memory leaking instances of realloc with non-leaking reallocf.
In some cases replace if (a == null) a = malloc(x); else a =
realloc(a, x); with simple reallocf(a, x). Per ANSI-C, this is
guaranteed to be the same thing.

I've been running these on my system here w/o ill effects for some
time. However, the CTM-express is at part 6 of 34 for the CAM
changes, so I've not been able to do a build world with the CAM in the
tree with these changes. Shouldn't impact anything, but...

Speedup in case locale not used

collate_range_cmp -> __collate_range_cmp

Convert to newly aded collate compare function

Remove static collcmp, use new internal function now

Use collate data for national alpha character ranges like [a-z]

Short value is better for hash due to easy overflow in 8bit characters

Use locale for character classes instead of hardcoded values
Misc 8bit cleanup

General -Wall warning cleanup, part I.
Submitted-By: Kent Vander Velden <graphix@iastate.edu>

8bit clean fixes

More cleanup.
Uhm, I also forgot: I took "EXTRA_SANITY" out of malloc.c

BSD 4.4 Lite Lib Sources