bug#43598: replace-in-string: finishing touches

bug#43598: replace-in-string: finishing touches

[Mattias Engdegård]

The new replace-in-string function is welcome but needs a few tweaks before we can call it done:

1. It doesn't quite work correctly with raw bytes:

  (replace-in-string "\377" "x" "a\377b")
  => "axb"
  (replace-in-string "\377" "x" "a\377ø")
  => "a\377ø"

The easiest solution is to reimplement it in terms of replace-regexp-in-string for now, and optimise it later (although I feel a bit bad undoing Lars's pretty handiwork...)

We have messy semantics here, because string-equal does not equate "\377" and (string-to-multibyte "\377"), but string-match-p does...

2. It is documented always to return a new string, but that's a tad over-generous nowadays; very few string functions do that. If we drop that guarantee, we get some optimisation opportunities:

- it can return the input string itself if no matches were found (a fairly common case)
- it can be marked pure, not just side-effect-free, so that the byte compiler can constant-propagate through calls to it

3. The name is somewhat unfortunate since a function by that name in XEmacs uses regexp matching.
In fact, the new function probably broke prolog-mode because of that (see prolog-replace-in-string).
While we can fix prolog-mode, we can't easily fix code outside the Emacs tree that may have similar problems.

Perhaps we should rename it to string-replace, in line with the modern naming convention discussed some time ago.

bug#43598: replace-in-string: finishing touches

[Lars Ingebrigtsen]

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

> The new replace-in-string function is welcome but needs a few tweaks
> before we can call it done:
>
> 1. It doesn't quite work correctly with raw bytes:
>
>   (replace-in-string "\377" "x" "a\377b")
>   => "axb"
>   (replace-in-string "\377" "x" "a\377ø")
>   => "a\377ø"
>
> The easiest solution is to reimplement it in terms of
> replace-regexp-in-string for now, and optimise it later (although I
> feel a bit bad undoing Lars's pretty handiwork...)

The point of the function is to have something very lightweight, so if
it's reimplemented on top of replace-regexp-in-string, there's not much
point of the function.

> We have messy semantics here, because string-equal does not equate
> "\377" and (string-to-multibyte "\377"), but string-match-p does...

Yes, I don't even know what the semantics should be.

(string-replace "\377" "x" "a\377ø")
=> "axø"

would make sense, but what about

(string-replace "\270" "x" "a\377ø")
=> ?

(\270 is the last byte in the ø.)

Doing anything here wouldn't make much sense at all, which means...  we
could just throw up our hands and say "don't do that, then", which is
approx. what string-equal does.

> 2. It is documented always to return a new string, but that's a tad
> over-generous nowadays; very few string functions do that. If we drop
> that guarantee, we get some optimisation opportunities:
>
> - it can return the input string itself if no matches were found (a
> fairly common case)
> - it can be marked pure, not just side-effect-free, so that the byte
> compiler can constant-propagate through calls to it

Yup, good idea.

> 3. The name is somewhat unfortunate since a function by that name in
> XEmacs uses regexp matching.
> In fact, the new function probably broke prolog-mode because of that
> (see prolog-replace-in-string).
> While we can fix prolog-mode, we can't easily fix code outside the
> Emacs tree that may have similar problems.
>
> Perhaps we should rename it to string-replace, in line with the modern
> naming convention discussed some time ago.

string-replace seems like a good name.

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

bug#43598: replace-in-string: finishing touches

[Lars Ingebrigtsen]

That is, we could just say "the results are undefined if the strings
contain raw bytes".  Well, rather, if both strings are raw bytes, or
none of them are, then it's well-defined, but not otherwise.

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

bug#43598: replace-in-string: finishing touches

[Lars Ingebrigtsen]

Lars Ingebrigtsen <larsi@gnus.org> writes:

> That is, we could just say "the results are undefined if the strings
> contain raw bytes".  Well, rather, if both strings are raw bytes, or
> none of them are, then it's well-defined, but not otherwise.

Or...  OK, I've never actually looked at the strings this closely, I've
just used the various accessors which hide all the complexity.

So: "a\377ø" is a multibyte string with five bytes (the "raw byte" is in
the private plane).

"a\377a" is a unibyte string with three bytes.

So searching for "\377" (one-byte unibyte string) and (make-string 1
255) (two-byte multibyte string) should be well-defined in either
combination here?

"\377" is in both "a\377ø" and "a\377a".

(make-string 1 255) is in neither "a\377ø", nor "a\377a".

And:

(eq (elt (make-string 1 255) 0) (elt "\377" 0))
=> t

But, like, whatevs.

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

bug#43598: replace-in-string: finishing touches

[Eli Zaretskii]

> From: Lars Ingebrigtsen <larsi@gnus.org>
> Date: Fri, 25 Sep 2020 01:18:13 +0200
> Cc: 43598@debbugs.gnu.org
> 
> So: "a\377ø" is a multibyte string with five bytes (the "raw byte" is in
> the private plane).
> 
> "a\377a" is a unibyte string with three bytes.
> 
> So searching for "\377" (one-byte unibyte string) and (make-string 1
> 255) (two-byte multibyte string) should be well-defined in either
> combination here?
> 
> "\377" is in both "a\377ø" and "a\377a".
> 
> (make-string 1 255) is in neither "a\377ø", nor "a\377a".
> 
> And:
> 
> (eq (elt (make-string 1 255) 0) (elt "\377" 0))
> => t

Would it help to always convert the first argument of
replace-in-string to a multibyte string, before replacing?

bug#43598: replace-in-string: finishing touches

[Lars Ingebrigtsen]

Eli Zaretskii <eliz@gnu.org> writes:

> Would it help to always convert the first argument of
> replace-in-string to a multibyte string, before replacing?

Yes, but not when the third argument is a unibyte string.

I've now done the conversion in the new string-search C-level function,
converting the search string both ways, depending on what the HAYSTACK
string is.  I'm not 100% sure that I'm doing the right thing here,
though, but it seems to pass all the test cases I could come up with.  I
wrote it very late last night, though, so...  :-/

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

bug#43598: replace-in-string: finishing touches

[Lars Ingebrigtsen]

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

> The new replace-in-string function is welcome but needs a few tweaks
> before we can call it done:
>
> 1. It doesn't quite work correctly with raw bytes:
>
>   (replace-in-string "\377" "x" "a\377b")
>   => "axb"
>   (replace-in-string "\377" "x" "a\377ø")
>   => "a\377ø"

I went ahead and checked in a new C-level function string-search, which
should be an efficient way to search for strings in strings (using
memmem, which Emacs has via Gnulib?), and this fixed these corner cases.

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

bug#43598: replace-in-string: finishing touches

[Mattias Engdegård]

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

25 sep. 2020 kl. 01.54 skrev Lars Ingebrigtsen <larsi@gnus.org>:

> I went ahead and checked in a new C-level function string-search, which
> should be an efficient way to search for strings in strings (using
> memmem, which Emacs has via Gnulib?), and this fixed these corner cases.

Thank you! Here are some proposed tweaks (diff attached):

1. Check the range of the START-POS argument so that we don't crash.
The permitted range is [0..N] where N is (length HAYSTACK), thus we permit a start right after the last character but no further.
We could also return nil in these cases but I think an error is more useful.

2. Make the docs more precise about various things.

3. Slight simplification of the implementation logic to avoid testing the same conditions multiple times.

4. More tests, especially for edge cases. Can't have too many!
One test still fails:

 (string-search "ø" "\303\270")

which should return nil but currently matches.
I think it's wrong to convert the needle to unibyte (using Fstring_as_unibyte) in this case, but I haven't decided what the best solution would be.

We should also consider the optimisations:
- If SCHARS(needle)>SCHARS(haystack) then no match is possible.
- If either needle or haystack is all-ASCII (all bytes in 0..127), then we can use memmem without conversion.


[-- Attachment #2: string-search.diff --]
[-- Type: application/octet-stream, Size: 5058 bytes --]

diff --git a/doc/lispref/strings.texi b/doc/lispref/strings.texi
index 6eb3d6f310..0f157c39d6 100644
--- a/doc/lispref/strings.texi
+++ b/doc/lispref/strings.texi
@@ -660,8 +660,10 @@ Text Comparison
 Return the position of the first instance of @var{needle} in
 @var{haystack}, both of which are strings.  If @var{start-pos} is
 non-@code{nil}, start searching from that position in @var{needle}.
+Return @code{nil} if no match was found.
 This function only considers the characters in the strings when doing
-the comparison; text properties are ignored.
+the comparison; text properties are ignored.  Matching is always
+case-sensitive.
 @end defun
 
 @defun compare-strings string1 start1 end1 string2 start2 end2 &optional ignore-case
diff --git a/src/fns.c b/src/fns.c
index 3927e4306e..2f64d95576 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -5456,15 +5456,18 @@ DEFUN ("buffer-hash", Fbuffer_hash, Sbuffer_hash, 0, 1, 0,
 
 DEFUN ("string-search", Fstring_search, Sstring_search, 2, 3, 0,
        doc: /* Search for the string NEEDLE in the string HAYSTACK.
-The return value is the position of the first instance of NEEDLE in
-HAYSTACK.
+The return value is the position of the first occurrence of NEEDLE in
+HAYSTACK, or nil if no match was found.
 
 The optional START-POS argument says where to start searching in
-HAYSTACK.  If not given, start at the beginning. */)
+HAYSTACK and defaults to zero (start at the beginning).
+It must be between zero and the length of HAYSTACK, inclusive.
+
+Case is always significant and text properties are ignored. */)
   (register Lisp_Object needle, Lisp_Object haystack, Lisp_Object start_pos)
 {
   ptrdiff_t start_byte = 0, haybytes;
-  char *res = NULL, *haystart;
+  char *res, *haystart;
 
   CHECK_STRING (needle);
   CHECK_STRING (haystack);
@@ -5472,7 +5475,10 @@ DEFUN ("string-search", Fstring_search, Sstring_search, 2, 3, 0,
   if (!NILP (start_pos))
     {
       CHECK_FIXNUM (start_pos);
-      start_byte = string_char_to_byte (haystack, XFIXNUM (start_pos));
+      EMACS_INT start = XFIXNUM (start_pos);
+      if (start < 0 || start > SCHARS (haystack))
+        xsignal1 (Qargs_out_of_range, start_pos);
+      start_byte = string_char_to_byte (haystack, start);
     }
 
   haystart = SSDATA (haystack) + start_byte;
@@ -5481,13 +5487,13 @@ DEFUN ("string-search", Fstring_search, Sstring_search, 2, 3, 0,
   if (STRING_MULTIBYTE (haystack) == STRING_MULTIBYTE (needle))
     res = memmem (haystart, haybytes,
 		  SSDATA (needle), SBYTES (needle));
-  else if (STRING_MULTIBYTE (haystack) && !STRING_MULTIBYTE (needle))
+  else if (STRING_MULTIBYTE (haystack))  /* unibyte needle */
     {
       Lisp_Object multi_needle = string_to_multibyte (needle);
       res = memmem (haystart, haybytes,
 		    SSDATA (multi_needle), SBYTES (multi_needle));
     }
-  else if (!STRING_MULTIBYTE (haystack) && STRING_MULTIBYTE (needle))
+  else                        /* unibyte haystack, multibyte needle */
     {
       Lisp_Object uni_needle = Fstring_as_unibyte (needle);
       res = memmem (haystart, haybytes,
diff --git a/test/src/fns-tests.el b/test/src/fns-tests.el
index 8c2b1300dc..323743d842 100644
--- a/test/src/fns-tests.el
+++ b/test/src/fns-tests.el
@@ -907,6 +907,12 @@ string-search
   (should (equal (string-search "foo" "foobarzot") 0))
   (should (not (string-search "fooz" "foobarzot")))
   (should (not (string-search "zot" "foobarzo")))
+  (should (equal (string-search "ab" "ab") 0))
+  (should (equal (string-search "ab\0" "ab") nil))
+  (should (equal (string-search "ab" "abababab" 3) 4))
+  (should (equal (string-search "ab" "ababac" 3) nil))
+  (let ((case-fold-search t))
+    (should (equal (string-search "ab" "AB") nil)))
 
   (should (equal
            (string-search (make-string 2 130)
@@ -923,4 +929,26 @@ string-search
   (should (not (string-search (make-string 1 255) "a\377ø")))
   (should (not (string-search (make-string 1 255) "a\377a")))
 
-  (should (equal (string-search "fóo" "zotfóo") 3)))
+  (should (equal (string-search "fóo" "zotfóo") 3))
+
+  (should (equal (string-search (string-to-multibyte "\377") "ab\377c") 2))
+  (should (equal (string-search "\303" "aøb") nil))
+  (should (equal (string-search "\270" "aøb") nil))
+  ;; This test currently fails, but it shouldn't!
+  ;;(should (equal (string-search "ø" "\303\270") nil))
+
+  (should-error (string-search "a" "abc" -1))
+  (should-error (string-search "a" "abc" 4))
+  (should-error (string-search "a" "abc" 100000000000))
+
+  (should (equal (string-search "a" "aaa" 3) nil))
+  (should (equal (string-search "\0" "") nil))
+
+  (should (equal (string-search "" "") 0))
+  (should-error (string-search "" "" 1))
+  (should (equal (string-search "" "abc") 0))
+  (should (equal (string-search "" "abc" 2) 2))
+  (should (equal (string-search "" "abc" 3) 3))
+  (should-error (string-search "" "abc" 4))
+  (should-error (string-search "" "abc" -1))
+  )

bug#43598: replace-in-string: finishing touches

[Lars Ingebrigtsen]

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

> 1. Check the range of the START-POS argument so that we don't crash.
> The permitted range is [0..N] where N is (length HAYSTACK), thus we
> permit a start right after the last character but no further.
> We could also return nil in these cases but I think an error is more useful.

Good point.  :-)

> 2. Make the docs more precise about various things.
>
> 3. Slight simplification of the implementation logic to avoid testing
> the same conditions multiple times.
>
> 4. More tests, especially for edge cases. Can't have too many!

It all looks good to me; please apply.

> One test still fails:
>
>  (string-search "ø" "\303\270")
>
> which should return nil but currently matches.
> I think it's wrong to convert the needle to unibyte (using
> Fstring_as_unibyte) in this case, but I haven't decided what the best
> solution would be.

Yeah, that's the bit I was most unsure about, because it just didn't
look quite correct to me, but I couldn't come up with the correct test
case last night; thanks.

> We should also consider the optimisations:
> - If SCHARS(needle)>SCHARS(haystack) then no match is possible.

Yup.

> - If either needle or haystack is all-ASCII (all bytes in 0..127),
> then we can use memmem without conversion.

Right, so if the multibyteness differs, then do another check to see
whether both strings are all-ASCII anyway, and do the comparison without
conversion...  Yes, makes sense to me.

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

bug#43598: replace-in-string: finishing touches

[Mattias Engdegård]

25 sep. 2020 kl. 13.11 skrev Lars Ingebrigtsen <larsi@gnus.org>:

> It all looks good to me; please apply.

Thanks, will do shortly.

> Right, so if the multibyteness differs, then do another check to see
> whether both strings are all-ASCII anyway, and do the comparison without
> conversion...

Both strings don't need to be all-ASCII; one of them suffices.

By the way, I added an argument check to replace-in-string to prevent it from entering an infinite loop.

bug#43598: replace-in-string: finishing touches

[Lars Ingebrigtsen]

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

>> Right, so if the multibyteness differs, then do another check to see
>> whether both strings are all-ASCII anyway, and do the comparison without
>> conversion...
>
> Both strings don't need to be all-ASCII; one of them suffices.

Hm, yes, that's true...  and I guess a further micro-optimisation would
be if NEEDLE is non-ASCII and HAYSTACK is all-ASCII, then there's no
point in memmem-ing at all. 

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

bug#43598: replace-in-string: finishing touches

[Lars Ingebrigtsen]

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

> Both strings don't need to be all-ASCII; one of them suffices.

I've now added that, and after that, everything fell into place for the
multibyte-needle/unibyte-haystack case, too.

That can only match if the needle contains nothing but ASCII and
eighth-bit chars, so I've altered it to return Qnil if there's any other
chars, and then convert to unibyte and do memmem otherwise.

*phew*

Is that all cases covered now?

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

bug#43598: replace-in-string: finishing touches

[Lars Ingebrigtsen]

Lars Ingebrigtsen <larsi@gnus.org> writes:

> Is that all cases covered now?

Well, I can't think of any more, but I said that before.  :-/

Anyway, we now have this slightly amusing situation:

(string-search (string-to-multibyte "o\303\270") "o\303\270")
=> 0

(string-match (string-to-multibyte "o\303\270") "o\303\270")
=> 0

(equal (string-to-multibyte "o\303\270") "o\303\270")
=> nil

But I guess we've lived with this for...  decades?  So that's probably
OK.

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

bug#43598: replace-in-string: finishing touches

[Mattias Engdegård]

27 sep. 2020 kl. 02.34 skrev Lars Ingebrigtsen <larsi@gnus.org>:

> (string-search (string-to-multibyte "o\303\270") "o\303\270")
> => 0
> 
> (string-match (string-to-multibyte "o\303\270") "o\303\270")
> => 0
> 
> (equal (string-to-multibyte "o\303\270") "o\303\270")
> => nil

(compare-strings (string-to-multibyte "o\303\270") nil nil "o\303\270" nil nil)
=> t

I'd say it's equal, string-equal, string-lessp and string-greaterp that are odd and that we probably should fix if it can be done without making them slower. Unless, of course, we can come up with an alternative theory of operation that is satisfactory.

> But I guess we've lived with this for...  decades?  So that's probably
> OK.

Yes, there is no hurry.

bug#43598: replace-in-string: finishing touches

[Richard Stallman]

[[[ To any NSA and FBI agents reading my email: please consider    ]]]
[[[ whether defending the US Constitution against all enemies,     ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

  > (string-match (string-to-multibyte "o\303\270") "o\303\270")
  > => 0

  > (equal (string-to-multibyte "o\303\270") "o\303\270")
  > => nil

It is paradoxical, but I think it is correct.
Equal compares the type of the string, not just the
characters in it.

-- 
Dr Richard Stallman
Chief GNUisance of the GNU Project (https://gnu.org)
Founder, Free Software Foundation (https://fsf.org)
Internet Hall-of-Famer (https://internethalloffame.org)

bug#43598: replace-in-string: finishing touches

[Mattias Engdegård]

28 sep. 2020 kl. 05.41 skrev Richard Stallman <rms@gnu.org>:

> It is paradoxical, but I think it is correct.
> Equal compares the type of the string, not just the
> characters in it.

No it doesn't. (equal (string-to-multibyte "A") "A") => t.

There is no deep reason for the current behaviour. It's just how things came to be, and nobody has been sufficiently annoyed to change it. The implementation is efficient and good enough for most purposes.

It is inconsistent and confusing though, and occasionally it does break down. One such case is when two strings that are not 'equal' become 'equal' after printing and reading them back, since unibyte and multibyte strings have the same printed representation. This can arise in conjunction with byte compilation.

Again, I have no plans to do anything about it right now.

bug#43598: replace-in-string: finishing touches

[Richard Stallman]

[[[ To any NSA and FBI agents reading my email: please consider    ]]]
[[[ whether defending the US Constitution against all enemies,     ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

  > > It is paradoxical, but I think it is correct.
  > > Equal compares the type of the string, not just the
  > > characters in it.

  > No it doesn't. (equal (string-to-multibyte "A") "A") => t.

I am puzzled, then.  Why DOES the other example return nil?

-- 
Dr Richard Stallman
Chief GNUisance of the GNU Project (https://gnu.org)
Founder, Free Software Foundation (https://fsf.org)
Internet Hall-of-Famer (https://internethalloffame.org)

bug#43598: replace-in-string: finishing touches

[Eli Zaretskii]

On September 29, 2020 6:29:34 AM GMT+03:00, Richard Stallman <rms@gnu.org> wrote:
> 
>   > > It is paradoxical, but I think it is correct.
>   > > Equal compares the type of the string, not just the
>   > > characters in it.
> 
>   > No it doesn't. (equal (string-to-multibyte "A") "A") => t.
> 
> I am puzzled, then.  Why DOES the other example return nil?

Because the byte sequences of the two strings are different when there are non-ASCII bytes in the original unibyte string.

bug#43598: replace-in-string: finishing touches

[Mattias Engdegård]

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

27 sep. 2020 kl. 02.03 skrev Lars Ingebrigtsen <larsi@gnus.org>:

> *phew*

Not bad! This seems to work all right.
Here are some minor optimisations:

- Do the fast all-ASCII test (bytes == chars) before iterating through the bytes to check for non-ASCII chars.
- Faster check for non-ASCII non-raw bytes (no need for the complex code in string_char_advance).

It is tempting to vectorise the all-ASCII loop. Maybe another day...

The patch also adds some more test cases for completeness.


[-- Attachment #2: string-search-tweaks.diff --]
[-- Type: application/octet-stream, Size: 5808 bytes --]

diff --git a/src/fns.c b/src/fns.c
index 0f76871154..f626fe11b2 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -5457,16 +5457,11 @@ DEFUN ("buffer-hash", Fbuffer_hash, Sbuffer_hash, 0, 1, 0,
 static bool
 string_ascii_p (Lisp_Object string)
 {
-  if (STRING_MULTIBYTE (string))
-    return SBYTES (string) == SCHARS (string);
-  else
-    {
-      ptrdiff_t nbytes = SBYTES (string);
-      for (ptrdiff_t i = 0; i < nbytes; i++)
-	if (SREF (string, i) > 127)
-	  return false;
-      return true;
-    }
+  ptrdiff_t nbytes = SBYTES (string);
+  for (ptrdiff_t i = 0; i < nbytes; i++)
+    if (SREF (string, i) > 127)
+      return false;
+  return true;
 }
 
 DEFUN ("string-search", Fstring_search, Sstring_search, 2, 3, 0,
@@ -5505,9 +5500,14 @@ DEFUN ("string-search", Fstring_search, Sstring_search, 2, 3, 0,
   haystart = SSDATA (haystack) + start_byte;
   haybytes = SBYTES (haystack) - start_byte;
 
-  if (STRING_MULTIBYTE (haystack) == STRING_MULTIBYTE (needle)
-      || string_ascii_p (needle)
-      || string_ascii_p (haystack))
+  /* We can do a direct byte-string search if both strings have the
+     same multibyteness, or if at least one of them consists of ASCII
+     characters only.  */
+  if (STRING_MULTIBYTE (haystack)
+      ? (STRING_MULTIBYTE (needle)
+         || SCHARS (haystack) == SBYTES (haystack) || string_ascii_p (needle))
+      : (!STRING_MULTIBYTE (needle)
+         || SCHARS (needle) == SBYTES (needle) || string_ascii_p (haystack)))
     res = memmem (haystart, haybytes,
 		  SSDATA (needle), SBYTES (needle));
   else if (STRING_MULTIBYTE (haystack))  /* unibyte needle */
@@ -5521,26 +5521,21 @@ DEFUN ("string-search", Fstring_search, Sstring_search, 2, 3, 0,
       /* The only possible way we can find the multibyte needle in the
 	 unibyte stack (since we know that neither are pure-ASCII) is
 	 if they contain "raw bytes" (and no other non-ASCII chars.)  */
-      ptrdiff_t chars = SCHARS (needle);
-      const unsigned char *src = SDATA (needle);
-
-      for (ptrdiff_t i = 0; i < chars; i++)
-	{
-	  int c = string_char_advance (&src);
-
-	  if (!CHAR_BYTE8_P (c)
-	      && !ASCII_CHAR_P (c))
-	    /* Found a char that can't be in the haystack.  */
-	    return Qnil;
-	}
+      ptrdiff_t nbytes = SBYTES (needle);
+      for (ptrdiff_t i = 0; i < nbytes; i++)
+        {
+          int c = SREF (needle, i);
+          if (CHAR_BYTE8_HEAD_P (c))
+            i++;                /* Skip raw byte.  */
+          else if (!ASCII_CHAR_P (c))
+            return Qnil;  /* Found a char that can't be in the haystack.  */
+        }
 
-      {
-	/* "Raw bytes" (aka eighth-bit) are represented differently in
-	   multibyte and unibyte strings.  */
-	Lisp_Object uni_needle = Fstring_to_unibyte (needle);
-	res = memmem (haystart, haybytes,
-		      SSDATA (uni_needle), SBYTES (uni_needle));
-      }
+      /* "Raw bytes" (aka eighth-bit) are represented differently in
+         multibyte and unibyte strings.  */
+      Lisp_Object uni_needle = Fstring_to_unibyte (needle);
+      res = memmem (haystart, haybytes,
+                    SSDATA (uni_needle), SBYTES (uni_needle));
     }
 
   if (! res)
diff --git a/test/src/fns-tests.el b/test/src/fns-tests.el
index 41969f2af2..d3c22f966e 100644
--- a/test/src/fns-tests.el
+++ b/test/src/fns-tests.el
@@ -913,6 +913,7 @@ string-search
   (should (equal (string-search "ab\0" "ab") nil))
   (should (equal (string-search "ab" "abababab" 3) 4))
   (should (equal (string-search "ab" "ababac" 3) nil))
+  (should (equal (string-search "aaa" "aa") nil))
   (let ((case-fold-search t))
     (should (equal (string-search "ab" "AB") nil)))
 
@@ -936,14 +937,16 @@ string-search
   (should (equal (string-search (string-to-multibyte "\377") "ab\377c") 2))
   (should (equal (string-search "\303" "aøb") nil))
   (should (equal (string-search "\270" "aøb") nil))
-  ;; This test currently fails, but it shouldn't!
-  ;;(should (equal (string-search "ø" "\303\270") nil))
+  (should (equal (string-search "ø" "\303\270") nil))
+
+  (should (equal (string-search "a\U00010f98z" "a\U00010f98a\U00010f98z") 2))
 
   (should-error (string-search "a" "abc" -1))
   (should-error (string-search "a" "abc" 4))
   (should-error (string-search "a" "abc" 100000000000))
 
   (should (equal (string-search "a" "aaa" 3) nil))
+  (should (equal (string-search "aa" "aa" 1) nil))
   (should (equal (string-search "\0" "") nil))
 
   (should (equal (string-search "" "") 0))
@@ -955,6 +958,21 @@ string-search
   (should-error (string-search "" "abc" -1))
 
   (should-not (string-search "ø" "foo\303\270"))
+  (should-not (string-search "\303\270" "ø"))
+  (should-not (string-search "\370" "ø"))
+  (should-not (string-search (string-to-multibyte "\370") "ø"))
+  (should-not (string-search "ø" "\370"))
+  (should-not (string-search "ø" (string-to-multibyte "\370")))
+  (should-not (string-search "\303\270" "\370"))
+  (should-not (string-search (string-to-multibyte "\303\270") "\370"))
+  (should-not (string-search "\303\270" (string-to-multibyte "\370")))
+  (should-not (string-search (string-to-multibyte "\303\270")
+                             (string-to-multibyte "\370")))
+  (should-not (string-search "\370" "\303\270"))
+  (should-not (string-search (string-to-multibyte "\370") "\303\270"))
+  (should-not (string-search "\370" (string-to-multibyte "\303\270")))
+  (should-not (string-search (string-to-multibyte "\370")
+                             (string-to-multibyte "\303\270")))
   (should (equal (string-search (string-to-multibyte "o\303\270") "foo\303\270")
                  2))
   (should (equal (string-search "\303\270" "foo\303\270") 3)))

bug#43598: replace-in-string: finishing touches

[Lars Ingebrigtsen]

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

> Here are some minor optimisations:
>
> - Do the fast all-ASCII test (bytes == chars) before iterating through
> the bytes to check for non-ASCII chars.

[...]

> -  if (STRING_MULTIBYTE (string))
> -    return SBYTES (string) == SCHARS (string);

[...]

> -  if (STRING_MULTIBYTE (haystack) == STRING_MULTIBYTE (needle)
> -      || string_ascii_p (needle)
> -      || string_ascii_p (haystack))
> +  /* We can do a direct byte-string search if both strings have the
> +     same multibyteness, or if at least one of them consists of ASCII
> +     characters only.  */
> +  if (STRING_MULTIBYTE (haystack)
> +      ? (STRING_MULTIBYTE (needle)
> +         || SCHARS (haystack) == SBYTES (haystack) || string_ascii_p (needle))
> +      : (!STRING_MULTIBYTE (needle)
> +         || SCHARS (needle) == SBYTES (needle) || string_ascii_p (haystack)))

Didn't you just move the STRING_MULTIBYTE bits of the test from the
string_ascii_p function and open-code it into Fstring_search function
here?  I'm not sure how that's an optimisation? 

> +      ptrdiff_t nbytes = SBYTES (needle);
> +      for (ptrdiff_t i = 0; i < nbytes; i++)
> +        {
> +          int c = SREF (needle, i);
> +          if (CHAR_BYTE8_HEAD_P (c))
> +            i++;                /* Skip raw byte.  */
> +          else if (!ASCII_CHAR_P (c))
> +            return Qnil;  /* Found a char that can't be in the haystack.  */
> +        }

Looks good.

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

bug#43598: replace-in-string: finishing touches

[Mattias Engdegård]

27 sep. 2020 kl. 13.48 skrev Lars Ingebrigtsen <larsi@gnus.org>:

> Didn't you just move the STRING_MULTIBYTE bits of the test from the
> string_ascii_p function and open-code it into Fstring_search function
> here?

No, look again. Previously, we would loop through all bytes of a unibyte needle before checking the lengths of a multibyte haystack. With the patch, we always do the cheap (length) check first. That's why that check had to be moved out of the helper function.

bug#43598: replace-in-string: finishing touches

[Lars Ingebrigtsen]

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

> No, look again. Previously, we would loop through all bytes of a
> unibyte needle before checking the lengths of a multibyte
> haystack.

Duh; you're right.  Please go ahead and apply.

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

bug#43598: replace-in-string: finishing touches

[Mattias Engdegård]

27 sep. 2020 kl. 14.02 skrev Lars Ingebrigtsen <larsi@gnus.org>:

> Please go ahead and apply.

Applied, thank you.

Looks like we are done now. string-replace seems to be substantially faster than replace-regexp-in-string.
Good job!

bug#43598: replace-in-string: finishing touches

[Eli Zaretskii]

> From: Mattias Engdegård <mattiase@acm.org>
> Date: Sun, 27 Sep 2020 18:14:36 +0200
> Cc: 43598-done@debbugs.gnu.org
> 
> Looks like we are done now. string-replace seems to be substantially faster than replace-regexp-in-string.
> Good job!

Thanks.  Is it possible to have some speed comparison for these two?

bug#43598: replace-in-string: finishing touches

[Lars Ingebrigtsen]

Eli Zaretskii <eliz@gnu.org> writes:

> Thanks.  Is it possible to have some speed comparison for these two?

This is what I used:

(let ((elems (mapcar (lambda (s)
		       (let ((start (random 80)))
			 (cons (substring s start (+ start (random 20)))
			       s)))
		     (cl-loop repeat 1000
			      collect (cl-coerce
				       (cl-loop repeat 100
						collect (+ (random 26) ?a))
				       'string)))))
  (list
   (benchmark-run 10000 (dolist (elem elems)
			  (string-search (car elem) (cdr elem))))
   (benchmark-run 10000 (dolist (elem elems)
			  (string-match (car elem) (cdr elem))))))

=>
((7.47099299 29 3.773541741999992)
 (19.673036086 74 9.616665831000006))

This is rather geared towards the weaknesses of string-match, though --
we're blowing through the regexp cache.

If you decrease the number of regexps to 10 and the run to 1000000, we get:

((7.818917279000001 37 4.791844609999998)
 (11.049133279 37 4.713127558000011))

And to compare with a "do-nothing" version:

   (benchmark-run 10000 (dolist (elem elems)
			  elem))))

=>

((5.74714395 28 3.722243896000009))

Using that as a baseline, the difference is 2s vs 5.2s.  

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

bug#43598: replace-in-string: finishing touches

[Eli Zaretskii]

> From: Lars Ingebrigtsen <larsi@gnus.org>
> Cc: Mattias Engdegård <mattiase@acm.org>,
>   43598@debbugs.gnu.org
> Date: Sun, 27 Sep 2020 18:41:39 +0200
> 
> Using that as a baseline, the difference is 2s vs 5.2s.  

Thanks.  So a factor of 2.5, not bad.

bug#43598: replace-in-string: finishing touches

[Lars Ingebrigtsen]

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

> We should also consider the optimisations:
> - If SCHARS(needle)>SCHARS(haystack) then no match is possible.

I've now done this.

> - If either needle or haystack is all-ASCII (all bytes in 0..127),
> then we can use memmem without conversion.

I thought that surely there's be a function like that in Emacs, but I
can't find it?

Instead there's code like

          && (STRING_MULTIBYTE (string)
              ? (chars == bytes) : string_ascii_p (string))
[...]
/* Whether STRING only contains chars in the 0..127 range.  */
static bool
string_ascii_p (Lisp_Object string)
{
  ptrdiff_t nbytes = SBYTES (string);
  for (ptrdiff_t i = 0; i < nbytes; i++)
    if (SREF (string, i) > 127)
      return false;
  return true;
}

and

	  unsigned char *p = SDATA (name);
	  while (*p && ASCII_CHAR_P (*p))
	    p++;

sprinkled around the code base.

Would it make sense to add a new utility function that does the right
thing for both multibyte and unibyte strings?  (The multibyte case is
just chars == bytes, but the unibyte case would be a loop.)

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

bug#43598: replace-in-string: finishing touches

[Lars Ingebrigtsen]

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

> 3. The name is somewhat unfortunate since a function by that name in
> XEmacs uses regexp matching.

[...]

> Perhaps we should rename it to string-replace, in line with the modern
> naming convention discussed some time ago.

Yup; now done.

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