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