RE2 alternative to negative assertions

[shen...@google.com]

Hi,

We are considering changing our regexp engine from PCRE to RE2. We have some expressions from customers that use PCRE's negative assertions (?!assertion). I wonder whether there is any alternative to that in RE2 that would allow us to automatically migrate customers' expressions to evaluate on RE2.

Thanks a lot,

shen...@google.com

[m...@google.com]

W dniu środa, 20 listopada 2013 03:08:09 UTC+1 użytkownik shen...@google.com napisał:

> We have some expressions from customers that use PCRE's negative
> assertions (?!assertion). I wonder whether there is any alternative
> to that in RE2 that would allow us to automatically migrate
> customers' expressions to evaluate on RE2.

Interesting that you have mentioned it, as I stumbled upon similar
problem, alas a bit simpler one.

In particular, I would like to be able to negate a match of a regular
expression. In other words, construct a regular r' expression which
matches everything that does not match regular expression r.

In PCRE the common way of expressing that is:
  (?!r).*
but that, not being a regular expression, is not supported by re2.

I would like to propose a partial solution to this such that if the
regex is of the form:
  (?!r).*
it is simplified to simply:
  r
and an internal flag “negate” is set. This step may be done
iteratively.

Do people think that would be feasible and useful?

A more advance set up could look for regexp of the form
  (?!r)s
and transform it into a pair r, s such that a string must match s and
must not much r, but that's probably for the future.

[Paul Wankadia]

On Wed, Mar 25, 2020 at 12:12 PM taylornichols via re2-dev <re2...@googlegroups.com> wrote:

Bump, +1. Any update on this feature request? We have to make separate "exclusion" regexes, e.g. path_regexp_exclusion.

IMO, what was proposed would be equivalent to implementing complement and conjunction. There are various ways of doing so, but none of them are a good fit for RE2 in terms of complexity bounds (i.e. anything superlinear is out of the question) and also in terms of compatibility of technique. Apart from that, complement can be mind-bending to reason about, so I shudder to imagine users writing complements nested within quantifiers or even other complements. Specifying one set of things to include and then another set of things to exclude is for the best and I will die on this hill. ;)