31–40 of 82 posts
Wait, what? I thought this was about finding all matches. With a minor tweak to the opening example:
We want to match `(.*a | b)` against `bbbbbabbbbb`.
I want to detect each `b` individually, and I also want to detect `bbbbba`, `bbbba`, `bbba`, `bba`, `ba`, and `a`. That's what it means to find all matches.
> the problem we're talking about in this post (finding all longest matches without quadratic blowup) Wait, what? I thought this was about finding all matches. With a minor tweak to the opening example: We want to match `(.*a | b)` against `bbbbbabbbbb`. I want to detect each `b` individually, and I also want to detect `bbbbba`, `bbbba`, `bbba`, `bba`, `ba`, and `a`. That's what it means to find all matches.
I find it weird to have the Perl innovation (?:...) be called "traditional regex". Perl was rather innovative back then, even if it's more than 30 years ago now. Traditional regex is what came before it (grep -E being the most advanced form). I wonder what counts as nontraditional in the author's eyes.
I find it weird to have the Perl innovation (?:...) be called "traditional regex". Perl was rather innovative back then, even if it's more than 30 years ago now. Traditional regex is what came before it (grep -E being the most advanced form). I wonder what counts as nontraditional in the author's eyes.
The strategy this engine uses is just to evolve the state as a function of time. A match can be successfully completed, yet not be emitted because some other longer match could still supercede it by being longer or more leftmost.
I tried the pattern /d+s+/g on 10,000,000 digits followed by no space. It took 4 seconds to return no results. I tried it on 20,000,000 digits followed by no space. It took 8 seconds to return no results. I tried on 100,000,000 and I ran out of heap space.
Test setup: https://gist.github.com/conartist6/051838025af1e04d966e03aa9...
@ievev Have you ever seen an implementation like @bablr/regex? https://github.com/bablr-lang/regex-vm It's an NFA system so it isn't going to be winning any awards for throughput, but in this particular case it does seem to completely avoid the complexity blowup. It will run your heap out of memory though on really big inputs. The strategy this engine uses is just to evolve the state as a function of time. A match ca…
[0]: https://github.com/BurntSushi/rebar/pull/20#issuecomment-256...
Restricting regex features to guarantee time complexity works , but it requires sacrificing potentially useful features like backtracking (or in the article's case, constraining oneself to fixed-upper-bound-length needles). In a real-world deployment where you want to run any arbitrary regex in an idiot/malice-proof manner, the best solution is the same solution you'd use for running any other kind of untrusted code…
wait! you haven't reached the important part of the post yet