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

From: Artur Malabarba <[email-masked]>
Date: Sun, 6 Dec 2015 12:50:24 +0000

2015-12-05 18:52 GMT+00:00 Alan Mackenzie <[email-masked]>:
> But it seems the complexity (and it can't honestly be that much,
> surely?) is intrinsic to the task being carried out.  Sticking a "\\|"
> between the upper case and lower case versions clearly doesn't work.
>
> Seriously, how difficult can it be to generate
>
>     "\\([Aa][´`]?\\|[áà𝑎ÁÀ]\\)"
>
> , which is a blameless regexp, given where you've already got to?

Oh. I see. I thought you were talking about mutually exclusive
regexps. Indeed a regexp like that would be trivial to generate. But
is it really blameless? I mean, if "\\(A\\|a\\)" can lead to extremely
slow searches, doesn't the same happen with "[Aa]"?

Anyway, at this point I'm just asking for future knowledge/reference.
According to Eli, the current implementation is in accordance with the
Unicode Standard. So it's probably best to keep it this way at least
for the first release of the feature.

> Once you've generated the long regexp, if it's too long, you can split
> it up into, say, 3 pieces A, B, C, such that (equal re (concat A B C)).
>
> Then you can do something like:
>
>     (and (search-forward-regexp A bound noerror)
>          (search-forward-regexp (concat "\\=" B) bound noerror)
>          (search-forward-regexp (concat "\\=" C) bound noerror))
>
> .  Though, thinking about it, it might be less painful to enhance the
> regexp engine to take longer regexps.

Besides. Char-folding is supposed to turn strings into regexps usable
anywhere, and this wouldn't work with that.

I've added a clause to the function so that it won't do any
charfolding if the resulting regexp would be longer than 5k chars
(instead it will just regexp-quote). That will at least prevent the
too-many words error in isearch. (I already had this clause in there
before, but it was using 10k, which apparently is not enough).