Auto merge of #87062 - poliorcetics:fix-85462, r=dtolnay

Make StrSearcher behave correctly on empty needle

Fix #85462.

This will not affect ABI since the other variant of the enum is bigger.
It may break some code, but that would be very strange: usually people
don't continue after the first `Done` (or `None` for a normal iterator).

`@rustbot` label T-libs A-str A-patterns

2 files changed, 58 insertions, 2 deletions

diff --git a/library/alloc/tests/str.rs b/library/alloc/tests/str.rs
index a1e819cf8f9..d3a87c056cf 100644
--- a/library/alloc/tests/str.rs
+++ b/library/alloc/tests/str.rs
@@ -1873,6 +1873,47 @@ mod pattern {
         "* \t",
         [Reject(0, 1), Reject(1, 2), Reject(2, 3),]
     );
+
+    // See #85462
+    #[test]
+    fn str_searcher_empty_needle_after_done() {
+        // Empty needle and haystack
+        {
+            let mut searcher = "".into_searcher("");
+
+            assert_eq!(searcher.next(), SearchStep::Match(0, 0));
+            assert_eq!(searcher.next(), SearchStep::Done);
+            assert_eq!(searcher.next(), SearchStep::Done);
+            assert_eq!(searcher.next(), SearchStep::Done);
+
+            let mut searcher = "".into_searcher("");
+
+            assert_eq!(searcher.next_back(), SearchStep::Match(0, 0));
+            assert_eq!(searcher.next_back(), SearchStep::Done);
+            assert_eq!(searcher.next_back(), SearchStep::Done);
+            assert_eq!(searcher.next_back(), SearchStep::Done);
+        }
+        // Empty needle and non-empty haystack
+        {
+            let mut searcher = "".into_searcher("a");
+
+            assert_eq!(searcher.next(), SearchStep::Match(0, 0));
+            assert_eq!(searcher.next(), SearchStep::Reject(0, 1));
+            assert_eq!(searcher.next(), SearchStep::Match(1, 1));
+            assert_eq!(searcher.next(), SearchStep::Done);
+            assert_eq!(searcher.next(), SearchStep::Done);
+            assert_eq!(searcher.next(), SearchStep::Done);
+
+            let mut searcher = "".into_searcher("a");
+
+            assert_eq!(searcher.next_back(), SearchStep::Match(1, 1));
+            assert_eq!(searcher.next_back(), SearchStep::Reject(0, 1));
+            assert_eq!(searcher.next_back(), SearchStep::Match(0, 0));
+            assert_eq!(searcher.next_back(), SearchStep::Done);
+            assert_eq!(searcher.next_back(), SearchStep::Done);
+            assert_eq!(searcher.next_back(), SearchStep::Done);
+        }
+    }
 }
 
 macro_rules! generate_iterator_test {
diff --git a/library/core/src/str/pattern.rs b/library/core/src/str/pattern.rs
index 508c522e71a..55ac1aa765c 100644
--- a/library/core/src/str/pattern.rs
+++ b/library/core/src/str/pattern.rs
@@ -928,6 +928,8 @@ struct EmptyNeedle {
     end: usize,
     is_match_fw: bool,
     is_match_bw: bool,
+    // Needed in case of an empty haystack, see #85462
+    is_finished: bool,
 }
 
 impl<'a, 'b> StrSearcher<'a, 'b> {
@@ -941,6 +943,7 @@ impl<'a, 'b> StrSearcher<'a, 'b> {
                     end: haystack.len(),
                     is_match_fw: true,
                     is_match_bw: true,
+                    is_finished: false,
                 }),
             }
         } else {
@@ -966,13 +969,19 @@ unsafe impl<'a, 'b> Searcher<'a> for StrSearcher<'a, 'b> {
     fn next(&mut self) -> SearchStep {
         match self.searcher {
             StrSearcherImpl::Empty(ref mut searcher) => {
+                if searcher.is_finished {
+                    return SearchStep::Done;
+                }
                 // empty needle rejects every char and matches every empty string between them
                 let is_match = searcher.is_match_fw;
                 searcher.is_match_fw = !searcher.is_match_fw;
                 let pos = searcher.position;
                 match self.haystack[pos..].chars().next() {
                     _ if is_match => SearchStep::Match(pos, pos),
-                    None => SearchStep::Done,
+                    None => {
+                        searcher.is_finished = true;
+                        SearchStep::Done
+                    }
                     Some(ch) => {
                         searcher.position += ch.len_utf8();
                         SearchStep::Reject(pos, searcher.position)
@@ -1045,12 +1054,18 @@ unsafe impl<'a, 'b> ReverseSearcher<'a> for StrSearcher<'a, 'b> {
     fn next_back(&mut self) -> SearchStep {
         match self.searcher {
             StrSearcherImpl::Empty(ref mut searcher) => {
+                if searcher.is_finished {
+                    return SearchStep::Done;
+                }
                 let is_match = searcher.is_match_bw;
                 searcher.is_match_bw = !searcher.is_match_bw;
                 let end = searcher.end;
                 match self.haystack[..end].chars().next_back() {
                     _ if is_match => SearchStep::Match(end, end),
-                    None => SearchStep::Done,
+                    None => {
+                        searcher.is_finished = true;
+                        SearchStep::Done
+                    }
                     Some(ch) => {
                         searcher.end -= ch.len_utf8();
                         SearchStep::Reject(searcher.end, end)