GNU expr syntax

[tertsdiepraam]

Hi! Over at uutils, we are happily using this library and highly appreciate all the work you all put in! However, we have a bit of a problem, because GNU expr (which we try to be compatible with) uses a custom syntax (explained in the manual, see details element below). Of course, we don't expect this syntax to be supported by the regex crate directly, since it's such a niche use-case. However, I still wanted to ask what you think the best way to support this is, since you might have some insight on this. For example, can we build on the regex-syntax crate or should we maybe fork that? Are there already examples of crates that implement an alternative syntax for regexes that we can look at for inspiration?

Many thanks!

Quote from the GNU manual about the syntax

Perform pattern matching. The arguments are converted to strings and the second is considered to be a (basic, a la GNU grep) regular expression, with a ^ implicitly prepended. The first argument is then matched against this regular expression.

If regex does not use ‘(’ and ‘)’, the : expression returns the number of characters matched, or 0 if the match fails.

If regex uses ‘(’ and ‘)’, the : expression returns the part of string that matched the subexpression, or the null string if the match failed or the subexpression did not contribute to the match.

Only the first ‘( … )’ pair is relevant to the return value; additional pairs are meaningful only for grouping the regular expression operators.

In the regular expression, +, ?, and | are operators which respectively match one or more, zero or one, or separate alternatives. These operators are GNU extensions. See Regular Expressions in The GNU Grep Manual, for details of regular expression syntax. Some examples are in Examples of using expr.

Source: https://www.gnu.org/software/coreutils/manual/html_node/String-expressions.html

[BurntSushi]

Unfortunately, it's way worse than what you're picturing here. In theory, if it were just a matter of syntax, then you could write your own parser and lower it to regex-syntax's Hir type (skipping its Ast). From there, you could build a regex from the Hir and you'd be good to go.

But "GNU expr" is, AIUI, built on top of POSIX regexes and POSIX regexes have different match semantics for the same regexes. For example:

$ echo 'samwise' | rg -o 'sam|samwise'
sam
$ echo 'samwise' | grep -E -o 'sam|samwise'
samwise

This is because POSIX uses leftmost-longest semantics where as this crate uses leftmost-first. You can see a description of these modes here: https://docs.rs/aho-corasick/latest/aho_corasick/enum.MatchKind.html

And note that it isn't limited to just literals. It applies to arbitrary regexes too:

$ echo 'ab' | grep -E -o '\w|\w\w'
ab
$ echo 'ab' | rg -o '\w|\w\w'
a
b

In theory, I want to support leftmost-longest semantics in the regex engine. But it's a herculean task and I neither have the time to do it myself or mentor it unfortunately.

There may be other differences in match semantics that I'm unaware of. You also have the whole locale mess to contend with that this crate won't help you with.

IMO, your quickest and easiest path is to fork regex-lite and make the changes you need there. Whether that's viable for you or not will depend on whether you're find with very slow match times.

[tertsdiepraam]

That is indeed unfortunate. I'll relay this information to the other maintainers and discuss with them what the best path forward is. Maybe we can indeed fork regex-lite and choose compatibility over performance. Thank you so much for your input! This is extremely helpful!