Linear Time Lookaround

[nyarly]

Describe your feature request

Recent research appears to have developed implementation limited lookarounds in linear time (c.f. e.g. https://systemf.epfl.ch/blog/re2-lookbehinds/)

Lookaround is a feature with occasional utility, but when it comes up it's irreplaceable.

Would it be possible to add table-based lookaround to regex?

[BurntSushi]

This has been asked for many times in the past and the answer has always been the same.

However, someone has actually contributed an implementation: #1266

It is a very large PR and I haven't had a chance to look at it yet. I don't know yet whether it's something I'm willing to accept.

[nyarly]

My understanding up until now was that lookaround wasn't possible inside the regex O(m*n) time complexity guarantee. That's completely laudable and part of why I reach for regex in Rust.

However, if I've followed the above work correctly, it gets a subset of lookaround inside of that linear guarantee, which would be really exciting.

I had no idea someone had already submitted an implementation. Looking at that PR, I can understand your reticence. As well structured as it looks to my naive eye, it's quite a lot to take on maintenance for.

[BurntSushi]

Yes there are all sorts of considerations at play. I have to read the paper thoroughly to understand the full solution and its actual trade-offs.

[Aurele-Barriere]

Hi!
Me and @cpitclaudel wrote the paper, and worked with @Multimodcrafter and @shilangyu for PR #1266 (also with @threddast for the RE2 fork).
We're happy to chat anytime, let us know if we can help!