Re: master 184d6e8c023: Avoid resizing mutation in subst-char-in-string

Re: master 184d6e8c023: Avoid resizing mutation in subst-char-in-string

[Arash Esbati]

Mattias Engdegård via Mailing list for Emacs changes <emacs-diffs@gnu.org> writes:

> branch: master
> commit 184d6e8c02345583264b053bb59ae031bb1c5a00
> Author: Mattias Engdegård <mattiase@acm.org>
> Commit: Mattias Engdegård <mattiase@acm.org>
>
>     Avoid resizing mutation in subst-char-in-string
>     
>     * lisp/subr.el (subst-char-in-string):
>     Use string-replace to avoid resizing mutation and O(n^2) time.
> ---
>  lisp/subr.el | 20 +++++++++++++-------
>  1 file changed, 13 insertions(+), 7 deletions(-)
>
> diff --git a/lisp/subr.el b/lisp/subr.el
> index 0ac71560c59..444afc0e486 100644
> --- a/lisp/subr.el
> +++ b/lisp/subr.el
> @@ -5690,13 +5690,19 @@ The SEPARATOR regexp defaults to \"\\s-+\"."
>  (defun subst-char-in-string (fromchar tochar string &optional inplace)
>    "Replace FROMCHAR with TOCHAR in STRING each time it occurs.
>  Unless optional argument INPLACE is non-nil, return a new string."
> -  (let ((i (length string))
> -	(newstr (if inplace string (copy-sequence string))))
> -    (while (> i 0)
> -      (setq i (1- i))
> -      (if (eq (aref newstr i) fromchar)
> -	  (aset newstr i tochar)))
> -    newstr))
> +  (if (and (not inplace)
> +           (if (multibyte-string-p string)
> +               (> (max fromchar tochar) 127)
> +             (> tochar 255)))
> +      ;; Avoid quadratic behaviour from resizing replacement.
> +      (string-replace (string fromchar) (string tochar) string)
> +    (let ((i (length string))
> +	  (newstr (if inplace string (copy-sequence string))))
> +      (while (> i 0)
> +        (setq i (1- i))
> +        (if (eq (aref newstr i) fromchar)
> +	    (aset newstr i tochar)))
> +      newstr)))
>  
>  (defun string-replace (from-string to-string in-string)
>    "Replace FROM-STRING with TO-STRING in IN-STRING each time it occurs."

This changes breaks Gnus for me: In the Summary buffer, point moves to
last article in Summary when I hit RET and doesn't shows the article
under point.  Building Emacs with 78761d699 gives me good results.
grep'ing for `subst-char-in-string' in the lisp/gnus gives:

--8<---------------cut here---------------start------------->8---
-> grep subst-char-in-string *.el
gnus-art.el:  (setq url (subst-char-in-string ?+ ?\  url))
gnus-art.el:  (setq url (subst-char-in-string ?_ ?\  url))
gnus-sum.el:  (subst-char-in-string
gnus-sum.el:   (subst-char-in-string ?\n ?\- string t) t))
gnus-sum.el:               (subst-char-in-string
nnheader.el:  (subst-char-in-string from to string))
nnimap.el:	  (insert (format "%S" (subst-char-in-string ?\n ?\s string))))
--8<---------------cut here---------------end--------------->8---

Best, Arash

Re: master 184d6e8c023: Avoid resizing mutation in subst-char-in-string

[Mattias Engdegård]

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

12 maj 2024 kl. 13.53 skrev Arash Esbati <arash@gnu.org>:

> This changes breaks Gnus for me

Thank you very much for reporting it, and for taking the trouble to find out whom to blame!

It's not obvious to me what is wrong, so maybe you could run some highly advanced print debugging for me?
I'd be very grateful if you would apply this patch and report what appears in your *Messages* buffer.


[-- Attachment #2: subst-char-in-string-debug.diff --]
[-- Type: application/octet-stream, Size: 677 bytes --]

diff --git a/lisp/subr.el b/lisp/subr.el
index 444afc0e486..a3273276221 100644
--- a/lisp/subr.el
+++ b/lisp/subr.el
@@ -5695,7 +5695,10 @@ subst-char-in-string
                (> (max fromchar tochar) 127)
              (> tochar 255)))
       ;; Avoid quadratic behaviour from resizing replacement.
-      (string-replace (string fromchar) (string tochar) string)
+      (let ((r (string-replace (string fromchar) (string tochar) string)))
+        (message "(subst-char-in-string %S %S %S %S) -> %S"
+                 fromchar tochar string inplace r)
+        r)
     (let ((i (length string))
 	  (newstr (if inplace string (copy-sequence string))))
       (while (> i 0)

Re: master 184d6e8c023: Avoid resizing mutation in subst-char-in-string

[Mattias Engdegård]

> It's not obvious to me what is wrong

Nevermind that, wiser people told me it was the text properties.
The change has been backed out. I'll do a proper job a bit later.

Re: master 184d6e8c023: Avoid resizing mutation in subst-char-in-string

[Arash Esbati]

Mattias Engdegård <mattias.engdegard@gmail.com> writes:

>> It's not obvious to me what is wrong
>
> Nevermind that, wiser people told me it was the text properties.
> The change has been backed out. I'll do a proper job a bit later.

Thank you and thanks to those wiser people.  Reverting the change fixes
the issue for now and I can use Gnus again.

Best, Arash