Please support negative lookahead (?!)

[reece]

Please add support for negative lookahead. It's quite hard to work around the absence of this functionality (e.g., in google sheets), and it seems like a significant shortcoming relative to other re packages.

[junyer]

As a matter of principle, RE2 does not support constructs for which only backtracking solutions are known to exist. Thus, backreferences and look-around assertions are not supported.

[leewz]

Where can I read more about this? I don't see where lookaheads goes wrong.

1. Say that we have this expression: PART1(?=PART2)PART3
2. Rewrite it as: (PART1(?=PART2)PART3).*
3. Return group 1 as the match.

In step 2, we take the intersection of PART2.* (implicitly) and PART3.*. Intersections are allowed in FSAs.

[junyer]

It is true that finite automata permit conjunction (&) and complement (!) operations, but these are problems with bounds that RE2 can't tolerate. See https://dl.acm.org/citation.cfm?id=2022911 and https://dl.acm.org/citation.cfm?id=2071372, for example.

[leewz]

Would it be possible to select a subset of lookaround regexes to support, like how bounded repetition is limited to 1000? When I read about that, I wondered why there wasn't simply a configurable limit on the number of states, rather than a limit on the feature itself.

[junyer]

RE2 doesn't use ε-free automata because they can be quadratic in the number of transitions, so we definitely won't adopt a technique that has exponential complexity. Sure, some regular expressions would fit within their memory budgets, but they wouldn't be making efficient use of that space. The compilation time and the execution time would also be highly problematic – probably even more so. And that is without even considering the intricacies of the implementation. (Would we use Antimirov partial derivatives as extended by Caron et al. as per that first paper? Or would we use De Morgan's laws and perform three subset constructions per conjunction? And how would we interpose either of those between the Regexp form and the Prog form? And what would their overheads likely be?)

[bukzor]

fixed-length lookbehind assertions can be translated to the current re2 syntax:

Invalid (?<!abc)def is equivalent to valid (?:(^|[^a])(^|[^b])(^|[^c]))def

I'm sure there's more efficient ways to do it, but this obviously won't have quadratic complexity, and I imagine at the automata level it can be done efficiently. As prior art, even pcre only allows fixed-length lookbehind assertions: https://man7.org/linux/man-pages/man3/pcresyntax.3.html#LOOKAHEAD_AND_LOOKBEHIND_ASSERTIONS

Each top-level branch of a look behind must be of a fixed length.

Although I do see that my translated regex will match more characters than the lookbehind does... is that a deal breaker?

[junyer]

Sorry, no dice. Hacks of that nature generalise/scale poorly (if at all) and, like you noted, break match ($0) semantics.