Subject: bug#22090: Isearch is sluggish and eventually refuses further service with "[Too many words]".

From: Alan Mackenzie <[email-masked]>
Date: Fri, 4 Dec 2015 23:00:00 +0000

Hello, Artur.

On Fri, Dec 04, 2015 at 08:49:42PM +0000, Artur Malabarba wrote:
> 2015-12-04 19:21 GMT+00:00 Alan Mackenzie <[email-masked]>:
> > Would you like any help to sort out these regexps?  I have some expertise
> > in doing this, having half-written fix-re.el, a program which analyses
> > and corrects just the sort of thing you're talking about.

> Maybe you can help then. The situation is actually quite simple.
> We have a regexp for matching anything that 'a' should match (for
> instance, that might look like "\\(a[´`]?\\|[áà𝑎]\\)"), and we have
> another for matching anything that A could match (e.g.
> "\\(A[`´]?\\|[ÁÀ]\\)").

Each of these regexps looks intrinsically blameless..

> When case-fold-search is on the previous code would simply join these
> regexps with "\\(\\(a[´`]?\\|[áà𝑎]\\)\\|\\(A[`´]?\\|[ÁÀ]\\)\\)".

Quick question: _why_ do you need to join them?  Given that
case-fold-search is enabled, couldn't you just use, say, the lower case
version?

> The problem is that (when case-fold-search is on) this creates a lot
> of redundancy. There are two paths in that regexp that match "a",
> there are two paths that match "à" and so on (but it's not full
> redundancy, for instance, only one path matches 𝑎).

Yes.  This is the killer danger in regexps (at least with the sort of
regexp engine we've got).  But it looks to me that this redundancy would
be quite easy to eliminate - you just need three regexp fragments for
the letter "a" - a lower case one, an upper case one and a
case-fold-search one.

The other thing is that for that single character "a" a 39 character
regexp fragment is being generated.  Might this have something to do
with the "[Too many words]" error I got last night (which comes from the
regexp engine returning a "too long regexp" error)?

Even if you can reduce that to, say 19 characters, that's only winning a
factor of 2 in the slide towards a too long regexp.  It might well be
that for a very long regexp, you might have to divide it into shorter
sections (a typical long RE will by a sequence of sub expressions,
rather than lots of alternatives inside \(...\|........\)).

-- 
Alan Mackenzie (Nuremberg, Germany).