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

[Arash Esbati <arash@gnu.org>]

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