Subject: Re: bug#61514: 30.0.50; sadistically long xml line hangs emacs

From: Stefan Monnier <[email-masked]>
Date: Mon, 20 Feb 2023 14:37:51 -0500

>> The patch below fixes the stack overflow.
> Together with the "\\<" in xmltok.el, this fixes this bug indeed in all
> cases (truncated and non-truncated ones).  Congrats!

We probably still have an O(N²) behavior which can bite with a line like

   <id * name="N_N_N_N_N_N_N_N_.....">

My patch should significantly improve the constant factor, but with
a long enough "N_N_N_N_N..." I suspect it can still end up painful.

Maybe we should reduce the scope of the search for the fallback case
(the case where we add the "[^...]+\\<" prefix) since AFAICT its only
purpose is to try and guess a helpful error messages when the XML is
ill-formed.

>> I don't think we want that for `emacs-29`, but unless there's some
>> objection I'll push this to `master`,
> I'd say it fixes an important bug in the regexp engine, but I cannot judge
> whether it's important enough for emacs-29.

It's a missing optimization that's been with us for many many years, so
I don't see any urgency to fix it.

        Stefan