bug#54733: Match again in perform-replace

bug#54733: Match again in perform-replace

[Juri Linkov]

[This is a spin-off from bug#14013 and bug#53758]

There is a long-standing bug in query-replace.
The optimization that uses `match-again` and `looking-at`
ignores search-related variables such as
isearch-search-fun-function, replace-re-search-function, etc.

Here's is a test case that demonstrates the problem in current master
with the recent addition of dired-isearch-search-filenames:

1. cd /tmp; touch file1; ln -s file1 file2
2. enter Wdired and move point to the beginning of file2
3. C-M-% .* RET foo RET
4. answer `n` when asked to replace `file2`

After that the remaining part of the same line is highlighted,
i.e. the part after "file2" (that is a symbolic link) in:

  file2 -> file1

This is because the `match-again` optimization uses `(looking-at ".*")`
after the previous replacement "file2" to ask about the next replacement
of " -> file1" that ignores isearch-search-fun-function.

Also in bug#53758 Dmitry explained that xref--query-replace-1
needed such a hack to let-bind isearch-filter-predicate
because of this problem in perform-replace that uses
`looking-at` instead of `replace-re-search-function`.

So now we have two cases that require fixing perform-replace.

bug#54733: Match again in perform-replace

[Juri Linkov]

> So now we have two cases that require fixing perform-replace.

To be able to redesign the match-again part of perform-replace,
there is a need to have a test suite that will confirm nothing
is broken after redesign.  So I pushed a new test in replace-tests.el.

bug#54733: Match again in perform-replace

[Juri Linkov]

>> So now we have two cases that require fixing perform-replace.
>
> To be able to redesign the match-again part of perform-replace,
> there is a need to have a test suite that will confirm nothing
> is broken after redesign.  So I pushed a new test in replace-tests.el.

The need to have `looking-at` in `perform-replace` is explained
in the commit message of 5632eb272c7.  So now added it to replace-tests.

bug#54733: Match again in perform-replace

[Juri Linkov]

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

>>> So now we have two cases that require fixing perform-replace.
>>
>> To be able to redesign the match-again part of perform-replace,
>> there is a need to have a test suite that will confirm nothing
>> is broken after redesign.  So I pushed a new test in replace-tests.el.
>
> The need to have `looking-at` in `perform-replace` is explained
> in the commit message of 5632eb272c7.  So now added it to replace-tests.

The only way to fix all reported problems is to always use
search functions in perform-replace:


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: perform-replace-match-again.patch --]
[-- Type: text/x-diff, Size: 2909 bytes --]

diff --git a/lisp/replace.el b/lisp/replace.el
index 81282deb14..7fbaa93ead 100644
--- a/lisp/replace.el
+++ b/lisp/replace.el
@@ -3013,9 +3013,10 @@ perform-replace
 	  (setq match-again
 		(and nonempty-match
 		     (or (not regexp-flag)
-			 (and (if backward
-				  (looking-back search-string nil)
-				(looking-at search-string))
+			 (and (save-excursion
+				(replace-search search-string limit
+						regexp-flag delimited-flag
+						case-fold-search backward))
 			      (let ((match (match-data)))
 				(and (/= (nth 0 match) (nth 1 match))
 				     match))))))
@@ -3298,8 +3299,12 @@ perform-replace
 			 ;; decide whether the search string
 			 ;; can match again just after this match.
 			 (if (and regexp-flag nonempty-match)
-			     (setq match-again (and (looking-at search-string)
-						    (match-data)))))
+			     (setq match-again
+				   (and (save-window-excursion
+					  (replace-search search-string limit
+						          regexp-flag delimited-flag
+						          case-fold-search backward))
+					(match-data)))))
 			;; Edit replacement.
 			((eq def 'edit-replacement)
 			 (setq real-match-data (replace-match-data
diff --git a/test/lisp/replace-tests.el b/test/lisp/replace-tests.el
index ef1e5c3eaf..f7a2e043ff 100644
--- a/test/lisp/replace-tests.el
+++ b/test/lisp/replace-tests.el
@@ -472,8 +472,7 @@ query-replace-search-function-tests
               found)))
          (tests
           '(
-            ;; FIXME: this test should pass after fixing bug#54733:
-            ;; ("aaaa" "C-M-% .* RET 1 RET !" "1a1a")
+            ("aaaa" "C-M-% .* RET 1 RET !" "1a1a")
             )))
     (query-replace--run-tests tests)))
 
@@ -485,8 +484,7 @@ perform-replace-tests
     ;; Test case from commit 5632eb272c7
     ("a a a " "\\ba " "c" nil t nil nil nil nil nil nil nil "ccc") ; not "ca c"
     ;; The same with region inside the second match
-    ;; FIXME: this test should pass after fixing bug#54733:
-    ;; ("a a a " "\\ba " "c" nil t nil nil nil 1 4 nil nil "ca a ")
+    ("a a a " "\\ba " "c" nil t nil nil nil 1 4 nil nil "ca a ")
     ))
 
 (defun perform-replace--run-tests (tests)
diff --git a/lisp/progmodes/xref.el b/lisp/progmodes/xref.el
index 6e763eef01..981f51c30a 100644
--- a/lisp/progmodes/xref.el
+++ b/lisp/progmodes/xref.el
@@ -856,14 +856,6 @@ xref--query-replace-1
          (continue t)
          did-it-once buf-pairs pairs
          current-beg current-end
-         ;; Counteract the "do the next match now" hack in
-         ;; `perform-replace'.  And still, it'll report that those
-         ;; matches were "filtered out" at the end.
-         (isearch-filter-predicate
-          (lambda (beg end)
-            (and current-beg
-                 (>= beg current-beg)
-                 (<= end current-end))))
          (replace-re-search-function
           (lambda (from &optional _bound noerror)
             (let (found pair)

bug#54733: Match again in perform-replace

[Dmitry Gutov]

Hi Juri,

Thanks for working on this.

On 03.05.2022 10:10, Juri Linkov wrote:
> +				(replace-search search-string limit
> +						regexp-flag delimited-flag
> +						case-fold-search backward))

I don't know this code too well, but perhaps SEARCH_STRING here should 
be anchored with something like "\\=" at the beginning?

Otherwise the search can succeed here even if the next match is not 
here. Not sure how important that is, though.

> -         ;; Counteract the "do the next match now" hack in
> -         ;; `perform-replace'.  And still, it'll report that those
> -         ;; matches were "filtered out" at the end.
> -         (isearch-filter-predicate
> -          (lambda (beg end)
> -            (and current-beg
> -                 (>= beg current-beg)
> -                 (<= end current-end))))

Please note that we'll likely have to keep this code here for a number 
of Emacs releases. So the patch should be tested with both versions: 
with this code present and with it removed, to ensure present and future 
compatibility.

bug#54733: Match again in perform-replace

[Juri Linkov]

>> +				(replace-search search-string limit
>> +						regexp-flag delimited-flag
>> +						case-fold-search backward))
>
> I don't know this code too well, but perhaps SEARCH_STRING here should be
> anchored with something like "\\=" at the beginning?
>
> Otherwise the search can succeed here even if the next match is not
> here. Not sure how important that is, though.

I'm afraid that prepending "\\=" might break a complex regexp somehow.
So maybe using replace-search is not the best thing to do.  I'm inclined
to leave looking-at, but only when the default search function is used.
Currently I'm writing a new function to search in rectangular regions
in bug#14013, but there are many corner cases, so it will take more time.
Then this new function could be used in xref as well since the rectangular
region uses the same pairs of points as xref--query-replace-1 does.
Then perform-replace could detect if this search function is used,
and not to do "the next match now" hack.

>> -         ;; Counteract the "do the next match now" hack in
>> -         ;; `perform-replace'.  And still, it'll report that those
>> -         ;; matches were "filtered out" at the end.
>> -         (isearch-filter-predicate
>> -          (lambda (beg end)
>> -            (and current-beg
>> -                 (>= beg current-beg)
>> -                 (<= end current-end))))
>
> Please note that we'll likely have to keep this code here for a number of
> Emacs releases. So the patch should be tested with both versions: with this
> code present and with it removed, to ensure present and future
> compatibility.

Keeping compatibility should be concerned here definitely.
I hope to post the complete patch in a few days.

bug#54733: Match again in perform-replace

[Juri Linkov]

>>> +				(replace-search search-string limit
>>> +						regexp-flag delimited-flag
>>> +						case-fold-search backward))
>>
>> I don't know this code too well, but perhaps SEARCH_STRING here should be
>> anchored with something like "\\=" at the beginning?
>>
>> Otherwise the search can succeed here even if the next match is not
>> here. Not sure how important that is, though.
>
> I'm afraid that prepending "\\=" might break a complex regexp somehow.

Another variant without modifying the original regexp is still to call
replace-search, but afterwards check if it stayed at the old position
with something like

  (let ((old-pos (point)))
    (and (replace-search ...)
	 (eq (match-beginning 0) old-pos)))

Less efficient, but looking-at is a real problem since it's incompatible
with search functions.  This is one of the problems faced in bug#14013
where isearch matches `C-M-r ^' outside of positions handled by the
search function because `isearch-search-and-update' uses a hack with
looking-at.  This is a long-standing flaw in isearch that needs to be fixed.
Any uses of looking-at in search/replace should be substituted
with an equivalent code that relies on the search function.

bug#54733: Match again in perform-replace

[Juri Linkov]

>>>> +				(replace-search search-string limit
>>>> +						regexp-flag delimited-flag
>>>> +						case-fold-search backward))
>>>
>>> I don't know this code too well, but perhaps SEARCH_STRING here should be
>>> anchored with something like "\\=" at the beginning?
>>>
>>> Otherwise the search can succeed here even if the next match is not
>>> here. Not sure how important that is, though.
>>
>> I'm afraid that prepending "\\=" might break a complex regexp somehow.
>
> Another variant without modifying the original regexp is still to call
> replace-search, but afterwards check if it stayed at the old position

A third variant is to add a new variable `looking-at-function'
that is like `isearch-search-fun-function', so everyone who needs
to redefine the search function, will also need to redefine
the looking-at function.

bug#54733: Match again in perform-replace

[Juri Linkov]

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

Hi Dmitry,

> Thanks for working on this.
>
>> +				(replace-search search-string limit
>> +						regexp-flag delimited-flag
>> +						case-fold-search backward))
>
> I don't know this code too well, but perhaps SEARCH_STRING here should be
> anchored with something like "\\=" at the beginning?
>
> Otherwise the search can succeed here even if the next match is not
> here. Not sure how important that is, though.

Stefan confirmed that "\\=" is reliable.  Thanks for the suggestion.
Now everything is ready.  Please try the latest patch in bug#14013
together with the patch for xref.el below.  I've tested with your
test cases from bug#53758, and everything works well.

>> -         ;; Counteract the "do the next match now" hack in
>> -         ;; `perform-replace'.  And still, it'll report that those
>> -         ;; matches were "filtered out" at the end.
>> -         (isearch-filter-predicate
>> -          (lambda (beg end)
>> -            (and current-beg
>> -                 (>= beg current-beg)
>> -                 (<= end current-end))))
>
> Please note that we'll likely have to keep this code here for a number of
> Emacs releases. So the patch should be tested with both versions: with this
> code present and with it removed, to ensure present and future
> compatibility.

I guess this might need more conditionals like (>= emacs-major-version 29).


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: xref--query-replace-1.patch --]
[-- Type: text/x-diff, Size: 2018 bytes --]

diff --git a/lisp/progmodes/xref.el b/lisp/progmodes/xref.el
index 0213ab3cc5..9b4adffa41 100644
--- a/lisp/progmodes/xref.el
+++ b/lisp/progmodes/xref.el
@@ -858,29 +858,9 @@ xref--outdated-p
 
 ;; FIXME: Write a nicer UI.
 (defun xref--query-replace-1 (from to iter)
-  (let* ((query-replace-lazy-highlight nil)
-         (continue t)
+  (let* ((continue t)
          did-it-once buf-pairs pairs
-         current-beg current-end
-         ;; Counteract the "do the next match now" hack in
-         ;; `perform-replace'.  And still, it'll report that those
-         ;; matches were "filtered out" at the end.
-         (isearch-filter-predicate
-          (lambda (beg end)
-            (and current-beg
-                 (>= beg current-beg)
-                 (<= end current-end))))
-         (replace-re-search-function
-          (lambda (from &optional _bound noerror)
-            (let (found pair)
-              (while (and (not found) pairs)
-                (setq pair (pop pairs)
-                      current-beg (car pair)
-                      current-end (cdr pair))
-                (goto-char current-beg)
-                (when (re-search-forward from current-end noerror)
-                  (setq found t)))
-              found))))
+         (region-extract-function (lambda (_) pairs)))
     (while (and continue (setq buf-pairs (funcall iter :next)))
       (if did-it-once
           ;; Reuse the same window for subsequent buffers.
@@ -889,8 +869,10 @@ xref--query-replace-1
          (pop-to-buffer (car buf-pairs)))
         (setq did-it-once t))
       (setq pairs (cdr buf-pairs))
+      (goto-char (point-min))
       (setq continue
-            (perform-replace from to t t nil nil multi-query-replace-map)))
+            (perform-replace from to t t nil nil multi-query-replace-map
+                             nil nil nil t)))
     (unless did-it-once (user-error "No suitable matches here"))
     (when (and continue (not buf-pairs))
       (message "All results processed"))))