Subject: RE: bug#29360: 26.0; Add full-buffer choice for `isearch-lazy-highlight'

From: Drew Adams <[email-masked]>
Date: Sat, 20 Oct 2018 16:09:29 -0700 (PDT)

> The biggest obstacle is this - currently the traversal order of
> visiting matches to lazy-highlight is the following:
> 
> 1. start from the current match forward to the bottom of the window;
> 
> 2. wrap from the bottom to the top of the window;
> 
> 3. start from the top of the window down to the current match.
> 
> Visually you can observe how the current algorithm works by setting:
> 
>   (setq lazy-highlight-max-at-a-time 1
>         lazy-highlight-initial-delay 1
>         lazy-highlight-interval 1)
> 
> This works well when matches are highlighted only on the screen.
> 
> But when boundaries will be extended from the window to the full buffer,
> the problem of performance creeps in.  Lazy-highlighting will work
> in the following order:
> 
> 1. start from the current match forward to the end of the buffer;
> 
> 2. wrap from the end to the beginning of the buffer;
> 
> 3. start from the beginning of the buffer down to the current match.
> 
> The problem is that matches in the upper part of the window might be
> highlighted too late - only when all matches in the full buffer
> are highlighted, and most of these matches likely will be outside
> of the displayed part of the buffer in the window.
> 
> IOW, highlighting of the matches above the current match will be delayed
> until all other matches in the whole buffer will get a highlighting
> overlay.
> 
> Do you think we should change the algorithm and adapt it to highlighting
> of the buffer?  Maybe we should first highlight matches on the bottom
> and the top part of the window before going to highlight matches in
> other parts of the buffer that are not visible on the screen?

Thanks for the explanation - very clear. I don't have any brilliant
insight into this.

I'd imagine that most uses of full-buffer highlighting are either:

1. On relatively small buffers, just for convenience of getting it
all done at once (i.e., non-lazy).

2. On any size buffer, for some other purpose than just Isearch.
IOW, use Isearch as a UI to get parts of a buffer highlighted (and
so propertized), for other purposes than just Isearch.

I'm not sure that #1 is a real use case. If it is then it's anyway
not problematic for the problem you mention - by definition.

It may be that for many of the #2 use cases immediate response
for the Isearch part is not that important. (Dunno.)

In any case, yes, your suggestion of first doing what we do now
(highlight the immediate area, using the current algorith), and
then following that with highlighting the rest of the buffer,
could be a good idea. Dunno how much that might change
the existing code.

Another possibility (?) is that for some of the #2 use cases it
might even be enough to highlight the rest of the buffer when
Emacs is idle. Again, dunno whether that option would be
important. But if we do that it should be controllable by
users and program, I'd think.

You likely have better ideas about all this. These are just a
few thoughts that came to mind now.

(BTW, I already sometimes see Isearch paint the lazy-highlighting
slowly, eventually coming down from the top of the window. Not
sure what the circumstances are in which I see that sometimes.
Probably when matching takes longer for some reason.)