Subject: Re: bug#19873: Ill-formed regular expression is constructed in forward-paragraph.

From: Alan Mackenzie <[email-masked]>
Date: Thu, 2 Dec 2021 20:45:17 +0000

Hello, Lars.

On Thu, Dec 02, 2021 at 11:39:51 +0100, Lars Ingebrigtsen wrote:
> Alan Mackenzie <[email-masked]> writes:

> > I think this idea is workable, but you'll have to check for one or both
> > of paragraph-s{tart,eparate} starting with "[ \t]+".  A good strategy
> > here might be to begin the target regexp with "^[ \t]*", then begin one
> > or both components with "[ \t]" (without the "*").

> > There may be other gotchas which I haven't thought about yet.

> > One needs a twisted mind to do this sort of thing properly, so I offer my
> > services to review your upcoming patch.  ;-)

> The problem seems rather intractable to me.  Is there really any way to
> examine a regexp to determine "does this in practice match [ \t]*"?

Back when the bug was new, I started writing a library to analyse a
regular expression and convert it into an equivalent well formed regular
expression.  It's actually working, but is incomplete.  It's currently
2757 lines long, including pretty complete unit testing.  I actually
looked at it again at the start of November.

> I wonder whether instead of trying to construct a better overall regexp
> could rewrite the loop.  That is, instead of searching for sp-parstart,
> search for parstart "\\|" parsep, and then check whether
> (match-beginning 0) of that comes after "^[ \t]*".  Or something along
> those lines.

> But I don't know whether that'd be any faster in practice.

It strikes me as one of these things which needs to be done
systematically, which, as I said, I've already tried (and not yet given
up).  The question presents itself, would the effort be better spent
improving Emacs's regexp engine?

> Do you have a test case that demonstrates the slowness?  In that case I
> could try to see whether there's any alternate approach here that's
> faster.

Martin Rudalics had the original testcase.  The slowness was exponential
with the number of spaces typed, I think.

> -- 
> (domestic pets only, the antidote for overdose, milk.)
>    bloggy blog: http://lars.ingebrigtsen.no

-- 
Alan Mackenzie (Nuremberg, Germany).