rust-lang
Linear Time Lookaround
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?
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: https://github.com/rust-lang/regex/pull/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.
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.
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.
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!
