From bd7f6c78c1443c1c359e0ff256854341be1a49e4 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Mattias=20Engdeg=C3=A5rd?= Date: Fri, 10 May 2024 10:35:39 +0200 Subject: [PATCH] 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. (cherry picked from commit 184d6e8c02345583264b053bb59ae031bb1c5a00) --- lisp/subr.el | 20 +++++++++++++------- 1 file changed, 13 insertions(+), 7 deletions(-) diff --git a/lisp/subr.el b/lisp/subr.el index de5d5c72911..9abcecd7c04 100644 --- a/lisp/subr.el +++ b/lisp/subr.el @@ -5694,13 +5694,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." -- 2.39.5