Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Finding all regex matches has always been O(n²)

iev.ee

Post reply on HN
Print view View original

61–70 of 82 posts

Re: Finding all regex matches has always been O(n²)

#61

Post by yxhuvud »

Hmm. I kinda wonder how something like a regexp engine based on marpa would fall. It would probably be slower in the common well behaved cases, as well as preprocessing. But I wonder if there are any cases that couldn't be done in a O(n) way if you limit yourself to only one match (instead of finding all possible matches like it actually can do). Marpa definitely handles most degenerate regexp cases linearly (once you make the match generation not do overlapping entries), but there may be some regexp feature it can't handle?

Bringing a fully general CFG parser to parse regexps would be like hunting mosquitos with a nuke though..

Re: Finding all regex matches has always been O(n²)

#62

Post by leoc »

MathMonkeyMan wrote: post #49
leoc wrote: post #35

Earlier quoted context omitted.

In my head a regex-like thing of Perl origin is known as a 'perlex'.

can call it PCRE now

'PCRE' never really caught on broadly, unfortunately.

It seems that Boost actually uses 'perlex' https://www.boost.org/doc/libs/1_31_0/libs/regex/doc/syntax_... .

Re: Finding all regex matches has always been O(n²)

#63

Post by ogogmad »

hyperpape wrote: post #51
conartist6 wrote: post #37

@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…

Returning no results is going to be linear in any DFA or NFA based implementation, though. You go character by character, and confirm that there are no matches. It's only when you return multiple matches that the engines have a problem and become superlinear.

It might be possible to use a randomised algorithm to estimate the number of matches in only linear time.

Re: Finding all regex matches has always been O(n²)

#64

Post by thaumasiotes »

ieviev wrote: post #33
thaumasiotes wrote: post #31

> 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.

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

> I changed this to leftmost-longest nonoverlapping matches so it's not misleading

Well, you changed the sentence I quoted. That doesn't really address what I was objecting to; I quoted that sentence because that's the first point in the essay where it's clear that you don't mean "all matches". That's where the reader becomes confused, but they don't become confused because that sentence is unclear - they become confused because everything else on the page is misleading, and that sentence unambiguously contradicts the misleading impression created by everything else.

Your headline says "all matches", your subheadline says "all matches", and your text both before and (still) after the sentence you changed frequently says "all matches", and in none of those cases do you actually mean "all matches". You mention that there is an existing solution, REmatch, but only to dismiss it as "solving a different problem", the problem of finding all matches. You also note that "all matches" is inherently quadratic because the size of the output is potentially quadratic, leading me to wonder why it's a surprise that asking for all matches yields quadratic performance.

Re: Finding all regex matches has always been O(n²)

#65

Post by trashb »

coldtea wrote: post #56
gpvos wrote: post #34

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.

> even if it's more than 30 years ago now. Here's your answer. > Traditional regex is what came before it No, that's "ancient regex".

> No, that's "ancient regex".

wouldn't the "ancient regex" be the ed "g/re/p" version?

  -E, --extended-regexp
    Interpret PATTERNS as extended regular expressions (EREs, see below).
  -G, --basic-regexp
    Interpret PATTERNS as basic regular expressions (BREs, see below).  This is the default.
  -P, --perl-regexp
    Interpret I as Perl-compatible regular expressions (PCREs).  This option is experimental when combined with the -z (--null-data) option, and grep  -P  may  warn of unimplemented features.
From the manpage it seems my grep make distinction between "Extended" "Basic" and "Perl" regexes.

Re: Finding all regex matches has always been O(n²)

#66

Post by ieviev »

thaumasiotes wrote: post #64
ieviev wrote: post #33

Earlier quoted context omitted.

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

> I changed this to leftmost-longest nonoverlapping matches so it's not misleading Well, you changed the sentence I quoted. That doesn't really address what I was objecting to; I quoted that sentence because that's the first point in the essay where it's clear that you don't mean "all matches". That's where the reader becomes confused, but they don't become confused because that sentence is unclear - they become conf…

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

Re: Finding all regex matches has always been O(n²)

#67

Post by ieviev »

mjmas wrote: post #55

> no capture groups > [...] > no lazy quantifiers - .*? Here's the caveats. And so running a regex engine on the matches seems like it would get you back to O(regexlen * haystacklen * matchcount) or roughly O(mn²) again.

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.

Re: Finding all regex matches has always been O(n²)

#69

Post by saidnooneever »

i want to say threats dont only come from inputs gathered over the internet.

there are many reasons to exploit things. one example is local privilege escalation. If your service has high privileges and somehow someone can edit an input source for it (like some file it reads thats accessible to the user, or even by tricking the service into looking at the wrong file) it will still be a useful vector.

now this might seem far fetched, but a lot of exploits i've seen actually do this type of stuff.

for example you find a program which gatheres some debug or support info package, and touches a directory which is user accessible. user put some kind of link or tricky file in there and boom, service compromised.

I would only not use hardened mode if the regex is actually embedded directly into the program, because that would atleast require the program itself to be touched before it breaks (which would already require the same level of privileges as the program runs on).

So, long story short. Be aware that if your program touches local resources that are not matching its own privilege level, like some log locations, tmp, etc , be sure that stuff doesn not get turned into regex or use the hardened mode to prevent problems.

its not always about users providing some input via an webpage or some online service that causes something to break..

Re: Finding all regex matches has always been O(n²)

#70

Post by coldtea »

trashb wrote: post #65
coldtea wrote: post #56

Earlier quoted context omitted.

> even if it's more than 30 years ago now. Here's your answer. > Traditional regex is what came before it No, that's "ancient regex".

> No, that's "ancient regex". wouldn't the "ancient regex" be the ed "g/re/p" version? -E, --extended-regexp Interpret PATTERNS as extended regular expressions (EREs, see below). -G, --basic-regexp Interpret PATTERNS as basic regular expressions (BREs, see below). This is the default. -P, --perl-regexp Interpret I as Perl-compatible regular expressions (PCREs). This option is experimental when combined with the -z (-…

>wouldn't the "ancient regex" be the ed "g/re/p" version?

That's "prehistoric regex"

Post reply on HN