bug#25751: Query replace lazy highlighting

bug#25751: Query replace lazy highlighting

[Antoine Levitt]

(apologies if this has been posted before, but I can't find any
references)

When query-replacing and confirming, matches get unhighlighted, and then
highlighted again, which is very distracting. E.g. open a file, M-% a ->
a, y, other matches of a get unhighlighted then highlighted again.

(setq lazy-highlight-initial-delay 0) (shouldn't it be default by the
way, at least on graphical displays?) reduces the problem but does not
eliminate it (it produces small flickers). There's
lazy-highlight-cleanup, but that disables cleanup completely, which I
don't want.

Can't this be eliminated?

Best,
Antoine

bug#25751: Query replace lazy highlighting

[Juri Linkov]

> When query-replacing and confirming, matches get unhighlighted, and then
> highlighted again, which is very distracting. E.g. open a file, M-% a ->
> a, y, other matches of a get unhighlighted then highlighted again.
>
> (setq lazy-highlight-initial-delay 0) (shouldn't it be default by the
> way, at least on graphical displays?) reduces the problem but does not
> eliminate it (it produces small flickers). There's
> lazy-highlight-cleanup, but that disables cleanup completely, which I
> don't want.
>
> Can't this be eliminated?

The reason why it works this way is because lazy-highlight is not yet
optimized to handle changes: it needs to dehighlight the replaced text,
and to add highlighting in the new replacing text after every replacement.
I see no simpler solution than to write a new function with a name like
‘isearch-lazy-highlight-update-in-region’ that given the region boundaries
of the last replacement will rehighlight matches in that region.

bug#25751: Query replace lazy highlighting

[Juri Linkov]

>> When query-replacing and confirming, matches get unhighlighted, and then
>> highlighted again, which is very distracting. E.g. open a file, M-% a ->
>> a, y, other matches of a get unhighlighted then highlighted again.
>>
>> (setq lazy-highlight-initial-delay 0) (shouldn't it be default by the
>> way, at least on graphical displays?) reduces the problem but does not
>> eliminate it (it produces small flickers). There's
>> lazy-highlight-cleanup, but that disables cleanup completely, which I
>> don't want.
>>
>> Can't this be eliminated?
>
> The reason why it works this way is because lazy-highlight is not yet
> optimized to handle changes: it needs to dehighlight the replaced text,
> and to add highlighting in the new replacing text after every replacement.
> I see no simpler solution than to write a new function with a name like
> ‘isearch-lazy-highlight-update-in-region’ that given the region boundaries
> of the last replacement will rehighlight matches in that region.

Actually, there are too many special casing to optimize that makes this
solution too brittle: for example, replacing a string with shorter text
requires highlighting new matches at the window-end minus the length of the
deleted text, i.e. deletion shifts previously invisible text into the view
where matches should be highlighted.

But I realized that fortunately there is a better and simpler solution.
The problem is not specific to replacement, the same flicker exists in isearch,
e.g. while scrolling by one line where all overlays are deleted, and
created again in the same places.  To void flickering the best solution is
to delete old overlays AFTER adding new ones, not BEFORE as it is now -
this works pleasingly well:

diff --git a/lisp/isearch.el b/lisp/isearch.el
index 5262435..9cb5399 100644
--- a/lisp/isearch.el
+++ b/lisp/isearch.el
@@ -3101,6 +3101,7 @@ (defun isearch-dehighlight ()
 ;;    only if `isearch-string' is an invalid regexp.
 
 (defvar isearch-lazy-highlight-overlays nil)
+(defvar isearch-lazy-highlight-overlays-old nil)
 (defvar isearch-lazy-highlight-wrapped nil)
 (defvar isearch-lazy-highlight-start-limit nil)
 (defvar isearch-lazy-highlight-end-limit nil)
@@ -3173,7 +3174,7 @@ (defun isearch-lazy-highlight-new-loop (&optional beg end)
 		 (not (equal isearch-error
 			     isearch-lazy-highlight-error))))
     ;; something important did indeed change
-    (lazy-highlight-cleanup t)        ;kill old loop & remove overlays
+    (setq isearch-lazy-highlight-overlays-old isearch-lazy-highlight-overlays)
     (setq isearch-lazy-highlight-error isearch-error)
     ;; It used to check for `(not isearch-error)' here, but actually
     ;; lazy-highlighting might find matches to highlight even when
@@ -3315,6 +3316,11 @@ (defun isearch-lazy-highlight-update ()
 			(setq isearch-lazy-highlight-start (window-group-end))
 			(goto-char (min (or isearch-lazy-highlight-end-limit (point-max))
 					(window-group-end))))))))
+            (when nomore
+              ;; Remove old overlays
+              (let ((isearch-lazy-highlight-overlays isearch-lazy-highlight-overlays-old)
+                    (isearch-lazy-highlight-timer nil))
+                (lazy-highlight-cleanup t)))
 	    (unless nomore
 	      (setq isearch-lazy-highlight-timer
 		    (run-at-time lazy-highlight-interval nil

bug#25751: Query replace lazy highlighting

[Eli Zaretskii]

> From: Juri Linkov <juri@linkov.net>
> Date: Thu, 16 Feb 2017 23:01:28 +0200
> Cc: 25751@debbugs.gnu.org
> 
> > (setq lazy-highlight-initial-delay 0) (shouldn't it be default by the
> > way, at least on graphical displays?) reduces the problem but does not
> > eliminate it (it produces small flickers). There's
> > lazy-highlight-cleanup, but that disables cleanup completely, which I
> > don't want.
> >
> > Can't this be eliminated?
> 
> The reason why it works this way is because lazy-highlight is not yet
> optimized to handle changes: it needs to dehighlight the replaced text,
> and to add highlighting in the new replacing text after every replacement.
> I see no simpler solution than to write a new function with a name like
> ‘isearch-lazy-highlight-update-in-region’ that given the region boundaries
> of the last replacement will rehighlight matches in that region.

I think the problem is not that we remove the highlight and add it
anew, the problem is that there's a redisplay cycle in between the
removal and the following addition.  The fact that setting
lazy-highlight-initial-delay alleviates the problem to some extent,
but still leaves the flicker tells me that there's a call to sit-for
or some such somewhere in the code that processes replacements, and
the removal and addition of the highlight are on two different sides
of that sit-for call.  One possible solution would be to remove the
highlight and add it without triggering redisplay, then I'd expect the
flicker to go away.

Does this make sense?

bug#25751: Query replace lazy highlighting

[Juri Linkov]

>> > (setq lazy-highlight-initial-delay 0) (shouldn't it be default by the
>> > way, at least on graphical displays?) reduces the problem but does not
>> > eliminate it (it produces small flickers). There's
>> > lazy-highlight-cleanup, but that disables cleanup completely, which I
>> > don't want.
>> >
>> > Can't this be eliminated?
>>
>> The reason why it works this way is because lazy-highlight is not yet
>> optimized to handle changes: it needs to dehighlight the replaced text,
>> and to add highlighting in the new replacing text after every replacement.
>> I see no simpler solution than to write a new function with a name like
>> ‘isearch-lazy-highlight-update-in-region’ that given the region boundaries
>> of the last replacement will rehighlight matches in that region.
>
> I think the problem is not that we remove the highlight and add it
> anew, the problem is that there's a redisplay cycle in between the
> removal and the following addition.  The fact that setting
> lazy-highlight-initial-delay alleviates the problem to some extent,
> but still leaves the flicker tells me that there's a call to sit-for
> or some such somewhere in the code that processes replacements, and
> the removal and addition of the highlight are on two different sides
> of that sit-for call.  One possible solution would be to remove the
> highlight and add it without triggering redisplay, then I'd expect the
> flicker to go away.
>
> Does this make sense?

This feature is called _lazy_ highlighting where _lazy_ implies that it's
intended to highlight matches much later after a lot of redisplay cycles.
Currently its steps are the following:

1. Delete old overlays
2. Wait for 0.25 seconds of idle time
3. Highlight first 20 matches
4. Wait 0.0625 seconds
5. Highlight next 20 matches
6. Repeat 4 until all matches are highlighted

It makes a big improvement to avoid flicker by moving ‘Delete old overlays’
to the end when all new matches are highlighted, essentially extending
lazy-highlight with ‘lazy-cleanup’, i.e. making its cleanup _lazy_ as well.

Here is a more tested patch that works especially well for the most
frequently used isearch operation of adding characters into the
search string - there is no more flicker while typing the search string.

diff --git a/lisp/isearch.el b/lisp/isearch.el
index 5262435..f8796dd 100644
--- a/lisp/isearch.el
+++ b/lisp/isearch.el
@@ -3101,6 +3101,7 @@ (defun isearch-dehighlight ()
 ;;    only if `isearch-string' is an invalid regexp.
 
 (defvar isearch-lazy-highlight-overlays nil)
+(defvar isearch-lazy-highlight-overlays-old nil)
 (defvar isearch-lazy-highlight-wrapped nil)
 (defvar isearch-lazy-highlight-start-limit nil)
 (defvar isearch-lazy-highlight-end-limit nil)
@@ -3122,13 +3123,22 @@ (define-obsolete-variable-alias 'isearch-lazy-highlight-word
 (defvar isearch-lazy-highlight-forward nil)
 (defvar isearch-lazy-highlight-error nil)
 
-(defun lazy-highlight-cleanup (&optional force)
+(defun lazy-highlight-cleanup (&optional force lazy)
   "Stop lazy highlighting and remove extra highlighting from current buffer.
 FORCE non-nil means do it whether or not `lazy-highlight-cleanup'
 is nil.  This function is called when exiting an incremental search if
 `lazy-highlight-cleanup' is non-nil."
   (interactive '(t))
-  (if (or force lazy-highlight-cleanup)
+  (if (eq lazy t)
+      (setq isearch-lazy-highlight-overlays-old
+            (append isearch-lazy-highlight-overlays-old
+                    isearch-lazy-highlight-overlays))
+    (while isearch-lazy-highlight-overlays-old
+      (delete-overlay (car isearch-lazy-highlight-overlays-old))
+      (setq isearch-lazy-highlight-overlays-old
+            (cdr isearch-lazy-highlight-overlays-old))))
+  (when (and (or force lazy-highlight-cleanup)
+             (not lazy))
       (while isearch-lazy-highlight-overlays
         (delete-overlay (car isearch-lazy-highlight-overlays))
         (setq isearch-lazy-highlight-overlays
@@ -3173,7 +3183,7 @@ (defun isearch-lazy-highlight-new-loop (&optional beg end)
 		 (not (equal isearch-error
 			     isearch-lazy-highlight-error))))
     ;; something important did indeed change
-    (lazy-highlight-cleanup t)        ;kill old loop & remove overlays
+    (lazy-highlight-cleanup t (not (equal isearch-string "")))
     (setq isearch-lazy-highlight-error isearch-error)
     ;; It used to check for `(not isearch-error)' here, but actually
     ;; lazy-highlighting might find matches to highlight even when
@@ -3315,7 +3325,8 @@ (defun isearch-lazy-highlight-update ()
 			(setq isearch-lazy-highlight-start (window-group-end))
 			(goto-char (min (or isearch-lazy-highlight-end-limit (point-max))
 					(window-group-end))))))))
-	    (unless nomore
+            (if nomore
+                (lazy-highlight-cleanup t 'delete-old)
 	      (setq isearch-lazy-highlight-timer
 		    (run-at-time lazy-highlight-interval nil
 				 'isearch-lazy-highlight-update)))))))))

bug#25751: Query replace lazy highlighting

[Eli Zaretskii]

> From: Juri Linkov <juri@linkov.net>
> Cc: antoine.levitt@gmail.com,  25751@debbugs.gnu.org
> Date: Sat, 18 Feb 2017 00:52:47 +0200
> 
> > I think the problem is not that we remove the highlight and add it
> > anew, the problem is that there's a redisplay cycle in between the
> > removal and the following addition.  The fact that setting
> > lazy-highlight-initial-delay alleviates the problem to some extent,
> > but still leaves the flicker tells me that there's a call to sit-for
> > or some such somewhere in the code that processes replacements, and
> > the removal and addition of the highlight are on two different sides
> > of that sit-for call.  One possible solution would be to remove the
> > highlight and add it without triggering redisplay, then I'd expect the
> > flicker to go away.
> >
> > Does this make sense?
> 
> This feature is called _lazy_ highlighting where _lazy_ implies that it's
> intended to highlight matches much later after a lot of redisplay cycles.

You could still leave the "lazy" part, if you both remove and re-add
the overlays after the idle delay.  IOW, the important thing is not to
have redisplay between removal and addition of the highlight.

bug#25751: Query replace lazy highlighting

[Juri Linkov]

[-- Attachment #1: Type: text/plain, Size: 1217 bytes --]

>> > I think the problem is not that we remove the highlight and add it
>> > anew, the problem is that there's a redisplay cycle in between the
>> > removal and the following addition.  The fact that setting
>> > lazy-highlight-initial-delay alleviates the problem to some extent,
>> > but still leaves the flicker tells me that there's a call to sit-for
>> > or some such somewhere in the code that processes replacements, and
>> > the removal and addition of the highlight are on two different sides
>> > of that sit-for call.  One possible solution would be to remove the
>> > highlight and add it without triggering redisplay, then I'd expect the
>> > flicker to go away.
>> >
>> > Does this make sense?
>>
>> This feature is called _lazy_ highlighting where _lazy_ implies that it's
>> intended to highlight matches much later after a lot of redisplay cycles.
>
> You could still leave the "lazy" part, if you both remove and re-add
> the overlays after the idle delay.  IOW, the important thing is not to
> have redisplay between removal and addition of the highlight.

That's an option too, and here is the tested patch (it sets
lazy-highlight-max-at-a-time to nil to avoid redisplay between
lazy iterations):

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: Type: text/x-patch, Size: 2864 bytes --]

diff --git a/lisp/isearch.el b/lisp/isearch.el
index 5262435..15143ce 100644
--- a/lisp/isearch.el
+++ b/lisp/isearch.el
@@ -332,7 +332,7 @@ (define-obsolete-variable-alias 'isearch-lazy-highlight-max-at-a-time
                                 'lazy-highlight-max-at-a-time
                                 "22.1")
 
-(defcustom lazy-highlight-max-at-a-time 20
+(defcustom lazy-highlight-max-at-a-time nil
   "Maximum matches to highlight at a time (for `lazy-highlight').
 Larger values may reduce Isearch's responsiveness to user input;
 smaller values make matches highlight slowly.
@@ -3122,13 +3122,13 @@ (define-obsolete-variable-alias 'isearch-lazy-highlight-word
 (defvar isearch-lazy-highlight-forward nil)
 (defvar isearch-lazy-highlight-error nil)
 
-(defun lazy-highlight-cleanup (&optional force)
+(defun lazy-highlight-cleanup (&optional force postpone)
   "Stop lazy highlighting and remove extra highlighting from current buffer.
 FORCE non-nil means do it whether or not `lazy-highlight-cleanup'
 is nil.  This function is called when exiting an incremental search if
 `lazy-highlight-cleanup' is non-nil."
   (interactive '(t))
-  (if (or force lazy-highlight-cleanup)
+  (when (and (or force lazy-highlight-cleanup) (not postpone))
       (while isearch-lazy-highlight-overlays
         (delete-overlay (car isearch-lazy-highlight-overlays))
         (setq isearch-lazy-highlight-overlays
@@ -3173,7 +3173,7 @@ (defun isearch-lazy-highlight-new-loop (&optional beg end)
 		 (not (equal isearch-error
 			     isearch-lazy-highlight-error))))
     ;; something important did indeed change
-    (lazy-highlight-cleanup t)        ;kill old loop & remove overlays
+    (lazy-highlight-cleanup t (not (equal isearch-string ""))) ;stop old timer
     (setq isearch-lazy-highlight-error isearch-error)
     ;; It used to check for `(not isearch-error)' here, but actually
     ;; lazy-highlighting might find matches to highlight even when
@@ -3204,7 +3204,7 @@ (defun isearch-lazy-highlight-new-loop (&optional beg end)
     (unless (equal isearch-string "")
       (setq isearch-lazy-highlight-timer
             (run-with-idle-timer lazy-highlight-initial-delay nil
-                                 'isearch-lazy-highlight-update)))))
+                                 'isearch-lazy-highlight-start)))))
 
 (defun isearch-lazy-highlight-search ()
   "Search ahead for the next or previous match, for lazy highlighting.
@@ -3249,6 +3249,10 @@ (defun isearch-lazy-highlight-search ()
 	success)
     (error nil)))
 
+(defun isearch-lazy-highlight-start ()
+  (lazy-highlight-cleanup t) ;remove old overlays
+  (isearch-lazy-highlight-update))
+
 (defun isearch-lazy-highlight-update ()
   "Update highlighting of other matches for current search."
   (let ((max lazy-highlight-max-at-a-time)

bug#25751: Query replace lazy highlighting

[Drew Adams]

> > You could still leave the "lazy" part, if you both remove and re-add
> > the overlays after the idle delay.  IOW, the important thing is not to
> > have redisplay between removal and addition of the highlight.
> 
> That's an option too, and here is the tested patch (it sets
> lazy-highlight-max-at-a-time to nil to avoid redisplay between
> lazy iterations):

How does this relate to what has been discussed so far in bug #21092?

bug#25751: Query replace lazy highlighting

[Juri Linkov]

>> > You could still leave the "lazy" part, if you both remove and re-add
>> > the overlays after the idle delay.  IOW, the important thing is not to
>> > have redisplay between removal and addition of the highlight.
>>
>> That's an option too, and here is the tested patch (it sets
>> lazy-highlight-max-at-a-time to nil to avoid redisplay between
>> lazy iterations):
>
> How does this relate to what has been discussed so far in bug #21092?

I'm sorry to say that, but setting lazy-highlight-max-at-a-time to nil
in the patch here in bug#25751 is a better way to avoid flicker
than highlighting all matches in the buffer as it was discussed
in bug#21092.

I believe that modern hardware can quickly highlight all matches
on the screen in one loop without a noticeable delay.  But highlighting
matches in the whole buffer is another thing.  Could you try to see
how fast this could be by trying to highlight a single character
in a large buffer, e.g. with ‘M-x highlight-regexp RET a RET RET’

bug#25751: Query replace lazy highlighting

[Juri Linkov]

>>> > I think the problem is not that we remove the highlight and add it
>>> > anew, the problem is that there's a redisplay cycle in between the
>>> > removal and the following addition.  The fact that setting
>>> > lazy-highlight-initial-delay alleviates the problem to some extent,
>>> > but still leaves the flicker tells me that there's a call to sit-for
>>> > or some such somewhere in the code that processes replacements, and
>>> > the removal and addition of the highlight are on two different sides
>>> > of that sit-for call.  One possible solution would be to remove the
>>> > highlight and add it without triggering redisplay, then I'd expect the
>>> > flicker to go away.
>>> >
>>> > Does this make sense?
>>>
>>> This feature is called _lazy_ highlighting where _lazy_ implies that it's
>>> intended to highlight matches much later after a lot of redisplay cycles.
>>
>> You could still leave the "lazy" part, if you both remove and re-add
>> the overlays after the idle delay.  IOW, the important thing is not to
>> have redisplay between removal and addition of the highlight.
>
> That's an option too, and here is the tested patch (it sets
> lazy-highlight-max-at-a-time to nil to avoid redisplay between
> lazy iterations):

Installed and closed.