bug#44861: 27.1; [PATCH] signal in `replace-regexp-in-string'

bug#44861: 27.1; [PATCH] signal in `replace-regexp-in-string'

[Shigeru Fukaya]

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


`replace-regexp-in-string' sometimes signals an error when REGEXP
contains some bondary sequence.  Difference of searches between
against an original passed string and against an extracted substring
causes the incident.


(replace-regexp-in-string-simple "a\\B" "A" "a aaaa")
	error --> cons: Args out of range: 2, 3
    expected
	==> "a AAAa"

(replace-regexp-in-string "\\Ba" "A" "a aaaa")
	error --> cons: Args out of range: 3, 4
    expected
	==> "a aAAA"

--
Shigeru

[-- Attachment #2: subr.diff --]
[-- Type: application/octet-stream, Size: 937 bytes --]

diff -u /usr/local/share/emacs/27.1/lisp/subr.el /usr/local/share/emacs/27.1/fix/subr-replaceRegexpInString.el
--- /usr/local/share/emacs/27.1/lisp/subr.el	2020-07-30 06:40:41.000000000 +0900
+++ /usr/local/share/emacs/27.1/fix/subr-replaceRegexpInString.el	2020-11-25 12:25:53.954515500 +0900
@@ -4426,9 +4426,9 @@
 	;; Generate a replacement for the matched substring.
 	;; Operate on only the substring to minimize string consing.
 	;; Set up match data for the substring for replacement;
-	;; presumably this is likely to be faster than munging the
-	;; match data directly in Lisp.
-	(string-match regexp (setq str (substring string mb me)))
+	;; reset match-data for substring by subtracting offsets.
+	(set-match-data (mapcar (lambda (n) (and n (- n mb))) (match-data)))
+	(setq str (substring string mb me))
 	(setq matches
 	      (cons (replace-match (if (stringp rep)
 				       rep

Diff finished.  Wed Nov 25 12:29:28 2020

bug#44861: 27.1; [PATCH] signal in `replace-regexp-in-string'

[Mattias Engdegård]

Thank you, and I agree, we probably want to do something like your suggested patch.
We would need to write a test suite, of course, but it looks like the general approach would solve bug#15107 as well which looks like the same bug.

Some benchmarking would also be in order.

bug#44861: 27.1; [PATCH] signal in `replace-regexp-in-string'

[Mattias Engdegård]

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

forcemerge 15107 44861
stop

Suggested patch attached. A small test suite for replace-regexp-in-string has already been pushed to master -- very rudimentary, but better than nothing -- and the patch amends it with some new relevant cases that didn't work before.

It is basically your patch but slightly optimised; it turned out that the function call and allocation overhead of the original patch made it a tad too expensive (a pity, because it was very neat). Now performance is about the same as before when the pattern contains no submatches, and slightly above (< 10% slower) with one submatch. It seems worth the correctness.


[-- Attachment #2: 0001-Fix-replace-regexp-in-string-substring-match-data-tr.patch --]
[-- Type: application/octet-stream, Size: 2929 bytes --]

From 9bc8dc80be5cee517fa53e6b8f37881d4220f162 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Mattias=20Engdeg=C3=A5rd?= <mattiase@acm.org>
Date: Wed, 25 Nov 2020 15:32:08 +0100
Subject: [PATCH] Fix replace-regexp-in-string substring match data translation

For certain patterns, re-matching the same regexp on the matched
substring does not produce correctly translated match data
(bug#15107 and bug#44861).

Reported by Kevin Ryde and Shigeru Fukaya.

* lisp/subr.el (replace-regexp-in-string): Translate the match data
by explicit manipulation instead of trusting a call to string-match on
the matched string to do the job.
* test/lisp/subr-tests.el (subr-replace-regexp-in-string):
Add test cases.
---
 lisp/subr.el            | 17 ++++++++++++-----
 test/lisp/subr-tests.el |  6 +++++-
 2 files changed, 17 insertions(+), 6 deletions(-)

diff --git a/lisp/subr.el b/lisp/subr.el
index 1fb0f9ab7e..0ee2199933 100644
--- a/lisp/subr.el
+++ b/lisp/subr.el
@@ -4537,7 +4537,7 @@ replace-regexp-in-string
   ;; might be reasonable to do so for long enough STRING.]
   (let ((l (length string))
 	(start (or start 0))
-	matches str mb me)
+	matches str mb me md)
     (save-match-data
       (while (and (< start l) (string-match regexp string start))
 	(setq mb (match-beginning 0)
@@ -4546,10 +4546,17 @@ replace-regexp-in-string
 	(when (= me mb) (setq me (min l (1+ mb))))
 	;; Generate a replacement for the matched substring.
 	;; Operate on only the substring to minimize string consing.
-	;; Set up match data for the substring for replacement;
-	;; presumably this is likely to be faster than munging the
-	;; match data directly in Lisp.
-	(string-match regexp (setq str (substring string mb me)))
+
+        ;; Translate the match data so that it applies to the matched substring.
+        (setq md (match-data nil md t))  ; Reuse list from previous match.
+        (let ((m md))
+          (while m
+            (when (car m)
+              (setcar m (- (car m) mb)))
+            (setq m (cdr m)))
+          (set-match-data md))
+
+        (setq str (substring string mb me))
 	(setq matches
 	      (cons (replace-match (if (stringp rep)
 				       rep
diff --git a/test/lisp/subr-tests.el b/test/lisp/subr-tests.el
index c77be511dc..67f7fc9749 100644
--- a/test/lisp/subr-tests.el
+++ b/test/lisp/subr-tests.el
@@ -545,7 +545,11 @@ subr-replace-regexp-in-string
                             (match-beginning 1) (match-end 1)))
                   "babbcaacabc")
                  "b<abbc,0,4,1,3>a<ac,0,2,1,1><abc,0,3,1,2>"))
-  )
+  ;; anchors (bug#15107, bug#44861)
+  (should (equal (replace-regexp-in-string "a\\B" "b" "a aaaa")
+                 "a bbba"))
+  (should (equal (replace-regexp-in-string "\\`\\|x" "z" "--xx--")
+                 "z--zz--")))
 
 (provide 'subr-tests)
 ;;; subr-tests.el ends here
-- 
2.21.1 (Apple Git-122.3)

bug#44861: 27.1; [PATCH] signal in `replace-regexp-in-string'

[Stefan Kangas]

Mattias Engdegård <mattiase@acm.org> writes:

> It is basically your patch but slightly optimised; it turned out that
> the function call and allocation overhead of the original patch made
> it a tad too expensive (a pity, because it was very neat). Now
> performance is about the same as before when the pattern contains no
> submatches, and slightly above (< 10% slower) with one submatch. It
> seems worth the correctness.

Presumably this hasn't worked correctly for a long time, if ever.  Is
that correct?

I personally worry about the performance here.  Since we use regexps
heavily all over, it is not clear (to me) that 10 % overall performance
drop with subexpressions is worth it to work correctly in these rare
edge-cases.  I suppose we do have to fix the bug here, but is it
feasible to solve this in a way that has less performance impact?

bug#44861: 27.1; [PATCH] signal in `replace-regexp-in-string'

[Mattias Engdegård]

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

25 nov. 2020 kl. 22.39 skrev Stefan Kangas <stefankangas@gmail.com>:

> I personally worry about the performance here.  Since we use regexps
> heavily all over, it is not clear (to me) that 10 % overall performance
> drop with subexpressions is worth it to work correctly in these rare
> edge-cases.  I suppose we do have to fix the bug here, but is it
> feasible to solve this in a way that has less performance impact?

We can't really let it remain buggy, especially as the consequence can be an error or silently wrong results. Also remember that one man's edge case is another's reasonable use.

However, unlike Boris we can eat our cake and have it! The attached patch performs the match-data translation in a C function, which obviously is much faster and indeed speeds up replace-regexp-in-string in all cases (as long as there is any match at all). The new primitive is a bit ad-hoc, but does one well-defined thing and isn't intended for use by the general public anyway.


[-- Attachment #2: 0001-Fix-replace-regexp-in-string-substring-match-data-tr.patch --]
[-- Type: application/octet-stream, Size: 3894 bytes --]

From 88d5a8d847045e23c2ab39786dc6e5a9a5412a32 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Mattias=20Engdeg=C3=A5rd?= <mattiase@acm.org>
Date: Wed, 25 Nov 2020 15:32:08 +0100
Subject: [PATCH] Fix replace-regexp-in-string substring match data translation

For certain patterns, re-matching the same regexp on the matched
substring does not produce correctly translated match data
(bug#15107 and bug#44861).

Using a new builtin function also improves performance since the
number of calls to string-match is halved.

Reported by Kevin Ryde and Shigeru Fukaya.

* lisp/subr.el (replace-regexp-in-string): Translate the match data
using match-data--translate instead of trusting a call to string-match
on the matched string to do the job.
* test/lisp/subr-tests.el (subr-replace-regexp-in-string):
Add test cases.
* src/search.c (Fmatch_data__translate): New internal function.
(syms_of_search): Register it as a subroutine.
---
 lisp/subr.el            |  7 +++----
 src/search.c            | 18 ++++++++++++++++++
 test/lisp/subr-tests.el |  6 +++++-
 3 files changed, 26 insertions(+), 5 deletions(-)

diff --git a/lisp/subr.el b/lisp/subr.el
index 1fb0f9ab7e..e009dcc2b9 100644
--- a/lisp/subr.el
+++ b/lisp/subr.el
@@ -4546,10 +4546,9 @@ replace-regexp-in-string
 	(when (= me mb) (setq me (min l (1+ mb))))
 	;; Generate a replacement for the matched substring.
 	;; Operate on only the substring to minimize string consing.
-	;; Set up match data for the substring for replacement;
-	;; presumably this is likely to be faster than munging the
-	;; match data directly in Lisp.
-	(string-match regexp (setq str (substring string mb me)))
+        ;; Translate the match data so that it applies to the matched substring.
+        (match-data--translate (- mb))
+        (setq str (substring string mb me))
 	(setq matches
 	      (cons (replace-match (if (stringp rep)
 				       rep
diff --git a/src/search.c b/src/search.c
index e7f9094946..4eb634a3c0 100644
--- a/src/search.c
+++ b/src/search.c
@@ -3031,6 +3031,23 @@ DEFUN ("set-match-data", Fset_match_data, Sset_match_data, 1, 2, 0,
   return Qnil;
 }
 
+DEFUN ("match-data--translate", Fmatch_data__translate, Smatch_data__translate,
+       1, 1, 0,
+       doc: /* Add N to all string positions in the match data.  Internal.  */)
+  (Lisp_Object n)
+{
+  CHECK_FIXNUM (n);
+  EMACS_INT delta = XFIXNUM (n);
+  if (EQ (last_thing_searched, Qt))   /* String match data only.  */
+    for (ptrdiff_t i = 0; i < search_regs.num_regs; i++)
+      if (search_regs.start[i] >= 0)
+        {
+          search_regs.start[i] = max (0, search_regs.start[i] + delta);
+          search_regs.end[i] = max (0, search_regs.end[i] + delta);
+        }
+  return Qnil;
+}
+
 /* Called from Flooking_at, Fstring_match, search_buffer, Fstore_match_data
    if asynchronous code (filter or sentinel) is running. */
 static void
@@ -3388,6 +3405,7 @@ syms_of_search (void)
   defsubr (&Smatch_end);
   defsubr (&Smatch_data);
   defsubr (&Sset_match_data);
+  defsubr (&Smatch_data__translate);
   defsubr (&Sregexp_quote);
   defsubr (&Snewline_cache_check);
 
diff --git a/test/lisp/subr-tests.el b/test/lisp/subr-tests.el
index c77be511dc..67f7fc9749 100644
--- a/test/lisp/subr-tests.el
+++ b/test/lisp/subr-tests.el
@@ -545,7 +545,11 @@ subr-replace-regexp-in-string
                             (match-beginning 1) (match-end 1)))
                   "babbcaacabc")
                  "b<abbc,0,4,1,3>a<ac,0,2,1,1><abc,0,3,1,2>"))
-  )
+  ;; anchors (bug#15107, bug#44861)
+  (should (equal (replace-regexp-in-string "a\\B" "b" "a aaaa")
+                 "a bbba"))
+  (should (equal (replace-regexp-in-string "\\`\\|x" "z" "--xx--")
+                 "z--zz--")))
 
 (provide 'subr-tests)
 ;;; subr-tests.el ends here
-- 
2.21.1 (Apple Git-122.3)

bug#44861: 27.1; [PATCH] signal in `replace-regexp-in-string'

[Lars Ingebrigtsen]

Mattias Engdegård <mattiase@acm.org> writes:

> However, unlike Boris we can eat our cake and have it! The attached
> patch performs the match-data translation in a C function, which
> obviously is much faster and indeed speeds up replace-regexp-in-string
> in all cases (as long as there is any match at all).

I'm all for speeding up replace-regexp-in-string (which is used all over
the place), so your change looks reasonable to me.

But I wonder -- would it make sense to move the entire
replace-regexp-in-string function to C?

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

bug#44861: 27.1; [PATCH] signal in `replace-regexp-in-string'

[Mattias Engdegård]

26 nov. 2020 kl. 14.12 skrev Lars Ingebrigtsen <larsi@gnus.org>:

> I'm all for speeding up replace-regexp-in-string (which is used all over
> the place), so your change looks reasonable to me.

Thank you! Pushed to master.

> But I wonder -- would it make sense to move the entire
> replace-regexp-in-string function to C?

Probably, but that would be a pure performance improvement. Most of the time is currently consumed in primitives (string-match, replace-match, substring, concat) so don't expect huge savings unless a substantially different approach is taken.

(Dmitry Gutov asked for a C implementation in bug#20273 for improving the speed of json encoding; is that still relevant?)

A bigger saving yet would be to use the much faster string-replace wherever possible. A little sweeping refactoring project perhaps? It would also improve readability -- no regexp quoting, fewer mysterious arguments like LITERAL and FIXEDCASE to worry about, etc.

bug#44861: 27.1; [PATCH] signal in `replace-regexp-in-string'

[Stefan Kangas]

Lars Ingebrigtsen <larsi@gnus.org> writes:

> But I wonder -- would it make sense to move the entire
> replace-regexp-in-string function to C?

Before we undertake any major changes in that direction, perhaps we
should benchmark the relevant functions on the native-comp branch?  It
changes the benchmarks by quite a lot in some cases.

bug#44861: 27.1; [PATCH] signal in `replace-regexp-in-string'

[Lars Ingebrigtsen]

Mattias Engdegård <mattiase@acm.org> writes:

> Probably, but that would be a pure performance improvement. Most of
> the time is currently consumed in primitives (string-match,
> replace-match, substring, concat) so don't expect huge savings unless
> a substantially different approach is taken.

Yeah, perhaps there's isn't a lot to be gained there, unless a lot of
the re-checking of all the arguments (etc.) (which is unnecessary once
we've ascertained that everything is, indeed, a string) can be done by
refactoring some of the underlying primitives.

> (Dmitry Gutov asked for a C implementation in bug#20273 for improving
> the speed of json encoding; is that still relevant?)

No, probably not, since it's now done by Jansson?  So I'm closing that
one.

> A bigger saving yet would be to use the much faster string-replace
> wherever possible. A little sweeping refactoring project perhaps? It
> would also improve readability -- no regexp quoting, fewer mysterious
> arguments like LITERAL and FIXEDCASE to worry about, etc.

I started looking at that, and there's a huge pile of calls like

(replace-regexp-in-string ":" ";" string)

that can be rewritten to use string-replace.  But!  Every single case
requires careful analysis, exactly because replace-regexp-in-string sets
the match data.  Perhaps five lines later, there's a reference to
(match-string 0 string)?  Perhaps the reference is in the function that
called this function?

So most changes are fraught with possible unforeseen breakages, the code
is super-duper straightforward like

(setq string (replace-regexp-in-string ":" ";" string))
(setq string (replace-regexp-in-string "a" "b" string))

Then you know that you can replace the first one without any danger.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

bug#44861: 27.1; [PATCH] signal in `replace-regexp-in-string'

[Lars Ingebrigtsen]

Stefan Kangas <stefankangas@gmail.com> writes:

> Before we undertake any major changes in that direction, perhaps we
> should benchmark the relevant functions on the native-comp branch?  It
> changes the benchmarks by quite a lot in some cases.

Yes, that's true.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

bug#44861: 27.1; [PATCH] signal in `replace-regexp-in-string'

[Eli Zaretskii]

> From: Stefan Kangas <stefankangas@gmail.com>
> Date: Thu, 26 Nov 2020 05:43:29 -0800
> Cc: 44861@debbugs.gnu.org, Shigeru Fukaya <shigeru.fukaya@gmail.com>
> 
> Lars Ingebrigtsen <larsi@gnus.org> writes:
> 
> > But I wonder -- would it make sense to move the entire
> > replace-regexp-in-string function to C?
> 
> Before we undertake any major changes in that direction, perhaps we
> should benchmark the relevant functions on the native-comp branch?  It
> changes the benchmarks by quite a lot in some cases.

Benchmarking is always welcome, but I don't think we should dismiss
performance improvements by assuming everyone will use the
natively-compiled Lisp code VSN.  I'm quite sure *.elc files will be
used in the observable future by many people.  I also expect C code to
run faster than natively-compiled Lisp, when significant
implementation changes, such as those suggested by Mattias, are
involved.

bug#44861: 27.1; [PATCH] signal in `replace-regexp-in-string'

[Mattias Engdegård]

26 nov. 2020 kl. 15.03 skrev Lars Ingebrigtsen <larsi@gnus.org>:

> I started looking at that, and there's a huge pile of calls like
> 
> (replace-regexp-in-string ":" ";" string)
> 
> that can be rewritten to use string-replace.  But!  Every single case
> requires careful analysis, exactly because replace-regexp-in-string sets
> the match data.

No it doesn't; the entire body is wrapped in save-match-data.
It does set the match data locally for use in the replacement function, if any, but then string-replace cannot be used anyway.

There are other things that may need investigating for a switch to string-replace: whether case-folding is relevant, and whether a nil-or-absent argument to FIXEDCASE is intended, an oversight, or irrelevant.

In my experience, most code does not take case-folding into account at all or tacitly assume it does not apply. (Having a global variable controlling it is a terrible interface, by the way.) Similarly, most calls that omit FIXEDCASE do it without any thought that the replacement would be anything but literal. Thus, the risk isn't very big for either but these are still issues requiring some consideration.

bug#44861: 27.1; [PATCH] signal in `replace-regexp-in-string'

[Basil L. Contovounesios]

Lars Ingebrigtsen <larsi@gnus.org> writes:

> Mattias Engdegård <mattiase@acm.org> writes:
>
>> (Dmitry Gutov asked for a C implementation in bug#20273 for improving
>> the speed of json encoding; is that still relevant?)
>
> No, probably not, since it's now done by Jansson?  So I'm closing that
> one.

Also, bug#20273 was prompted by bug#20154, which was addressed by
avoiding replace-regexp-in-string, and further optimised in bug#40693.

-- 
Basil