Expand description
A POSIX extended regular expression matcher over bytes.
Redis has one command that takes a regular expression, ARGREP ... RE, and
it gets it from TRE, which it vendors under deps/tre. What it asks TRE for
is narrow: REG_EXTENDED | REG_NOSUB | REG_USEBYTES, optionally REG_ICASE,
and then a yes or no per element. No capture groups are read, no match
offsets are read, and a pattern with a backreference in it is refused before
it is ever run. So the thing that has to be built is a boolean matcher for
extended regular expressions over bytes, which is a much smaller object than
a general purpose regex crate.
That is the whole reason this is here rather than a dependency. The
workspace has four third party crates in it and two of them are only for
tests, and adding a regex engine and its three transitive crates to the
engine that the C ABI and every language binding link against is a large
thing to pay for one command. Writing the narrow version is a few hundred
lines and it comes out with a property the general one cannot promise: the
simulation is a Thompson construction walked with a set of live states, so
matching is linear in the subject and cannot be made to blow up by a pattern.
ARGREP runs its predicates over every element a range touches, from a
pattern a client sent, so that is worth having rather than being clever.
The syntax is TRE’s, read off deps/tre/lib/tre-parse.c rather than off
POSIX, because the point is to agree with the server people are migrating
from. TRE has a table of macros that run before anything else, so \n is a
newline, \d is [[:digit:]] and \w is [[:alnum:]_], and after that a
switch with \b, \B, \<, \> and \xNN. The one that surprises people
is that a backslash inside a bracket expression is a literal backslash and
not an escape, so [\d] is a backslash or a d.
Bytes rather than characters, the same as glob, and for the same reason: an
array element is arbitrary bytes and deciding what a character is would mean
deciding what encoding it is in.
Every rule in here was either read off a line of TRE or measured against it.
The measuring was done by building TRE from deps/tre into a small program
that answers the same question this does, and then generating patterns from
the pieces TRE’s parser has cases for and comparing the two answers. That is
how the macro table was found, along with the way a repeated assertion stays
mandatory, the split between the two errors a bad bound gives, and the
handful of places where TRE and Redis’s own fast path disagree with each
other. Roughly a quarter of a million comparisons agree.
Structs§
Enums§
- Error
- Why a pattern would not compile.
Constants§
- DUP_MAX
- The largest
{n,m}repetition, which is TRE’sRE_DUP_MAX.