ieviev

> lazy quantifiers for inclusion into the next release of POSIX

That is surprising!

We've found that in certain simpler scenarios it's possible to use complement to express lazy quantifiers, but in the general case it appears very fragile.

a simple example: a.*?b can be rewritten to something like (a.*b&~(a.*b_+)) in RE# syntax, which effectively means "there is a match, but must not contain a shorter match"

> 1998 TOPLAS

I will read through it properly, but i can already see from page 8 that it requires a table of (DFA size x input length) which makes me very suspicious that it is more of a thought exercise than a real world solution.

> It is true that you can’t stream the haystack in the general case, but to what precise extent you can is an interesting question with a known algorithmic answer[3].

Thank you for this, this is an interesting paper

I have not verified it but i assume matching the whole line grep-style would bypass this problem entirely

Since a regex with ^<pattern>$ can not have overlapping matches it should guarantee linearity, given a linear engine. Or in the case of preprocessing lines first and then running is_match it's also linear

It's still O(n * m). The matches are non-overlapping, even if you run a separate engine on the matches post-match it will at most traverse the full input once across all matches.

I don't agree that overlapping matches is the only interpretation of "all matches". it very clearly does return all matches and it removes overlap

The post states clearly "finding all leftmost-longest non-overlapping matches without quadratic blowup"

The engines mentioned at the beginning all return nonoverlapping matches. Basic document search returns nonoverlapping matches.

Finding overlapping matches is exotic and rarely ever used in practice outside of network security. It does solve a different problem

I’m still open to it and thinking about it actually. I will explore if it’s possible to eliminate the large losses on common patterns and if it turns out it is then it’s a no brainer.

Going forward this and the extended operators + large pattern perf will hopefully be a strong selling point to gain more traction

Oh that is interesting! I haven't even looked Nim regex until now, is it similar to the approach in Go?

> constraining oneself to fixed-upper-bound-length needles

wait! you haven't reached the important part of the post yet

I have not heard of this before, i will have a look!

Haha, you're right about that. I was looking for another word for "default"

Good catch! I changed this to leftmost-longest nonoverlapping matches so it's not misleading

with all-matches semantics it returns a significantly higher number of matches than leftmost greedy.

eg. /abc*/ and abccccc will return you matches at ab|c|c|c|c|c|

I think it's very common and ok that people reason about other engines in terms of backtracking but it works very differently. And fixed length lookbehinds are more of a Java/Python thing, other engines support all lookbehinds.

The main idea of linear regex and intuitive semantics is that it should be declarative and the engine does whatever is the fastest without you having to worry about it. Instead of describing character by character how to perform the search and where it can blow up, think of it as just a specification. Then you can truly express whatever is the shortest/most convenient to explain.

Something i'm still trying to figure out and perhaps failing to understand is what are the killer features of backtracking regex that you would really miss if you were to use linear regex? It would help me a lot to know, i'm trying to convince others to make the switch

> I would say that regexes that matter in practice, e.g. when digging through logs, have clear boundaries that curb the pathological backtracking behavior

I agree with you in the sense that most practical regexes do not expose this quadratic blowup (from all matches) but i do not think the same about backtracking. The effect of backtracking is immediately clear when you're searching inside text without a clear anchor like \A or ^ or a very rare string prefix. It is much more visible with either larger patterns or larger character classes like unicode

It is human written and i've thoroughly went over every paragraph but i did use some help with wording. i suppose it does show now that you mention it

The part that makes it difficult is that it doesn't return the same matches, it returns almost the same matches but not exactly.

But if PCRE semantics isn't set in stone then i hope leftmost longest could be the default some day. There's a lot of nice things you get for free with the two pass approach