Stefan Monnier <[email protected]> writes:

> Actually, no, this is still O(N²) on `master` as well, still (the regexp
> search causes O(N) calls to `re_match` and *that* one is reduced to
> O(N)).

Ah, thanks for the explanation, I had missed that. On Emacs 31 my
timings grew linearly for the inputs I tried, but I can't rule out a
worse case.

I also found another problem with my regexp: on a tag longer than about
300 KB the [^<>]* part fails with "Stack overflow in regexp matcher".
So please drop that patch.

An alternative that avoids both problems is to stop matching attributes
with a regexp and walk the tags instead: find "<" followed by a letter,
then read the attributes one by one (name, optional =, then a "..." or
'...' or bare value) until ">". Each character is looked at once and
none of the regexps can backtrack over a long span, so it's linear and
doesn't overflow the stack. In my tests it:

- finds nothing in the HTML from my old README and nothing in the new
  one,
- still finds relative src values in tags spanning several lines, with
  single quotes or no quotes, and when another attribute's value
  contains ">",
- skips escaped text like &lt;img src="foo.png", and src= inside another
  attribute's value,
- takes 0.01 s on a 1.6 MB data: URI and grows linearly elsewhere.

But of course, it has some limits:

- it's about maybe 20 lines of code instead of one regexp,
- it isn't a real HTML parser: it doesn't skip the contents of <script>,
  <style> or <!-- comments --> (but neither does the current code),
- as you said, nobody has hit a real false positive yet, so it only
  fixes a problem that doesn't exist in practice so far.

If you think it's worth it now, or once a real case shows up, I'm happy
to send it as a patch. If not, no problem.

Thanks,
Szymon

Reply via email to