Auto merge of #23952 - Kimundi:more_string_pattern, r=alexcrichton

This adds the missing methods and turns `str::pattern` in a user facing module, as per RFC.

This also contains some big internal refactorings:
- string iterator pairs are implemented with a central macro to reduce redundancy 
- Moved all tests from `coretest::str` into `collectionstest::str` and left a note to prevent the two sets of tests drifting apart further.

See https://github.com/rust-lang/rust/issues/22477

2 files changed, 587 insertions, 363 deletions

diff --git a/src/libcore/str/mod.rs b/src/libcore/str/mod.rs
index 471e3c5ea67..5c8b6a774cd 100644
--- a/src/libcore/str/mod.rs
+++ b/src/libcore/str/mod.rs
@@ -17,6 +17,8 @@
 #![doc(primitive = "str")]
 
 use self::OldSearcher::{TwoWay, TwoWayLong};
+use self::pattern::Pattern;
+use self::pattern::{Searcher, ReverseSearcher, DoubleEndedSearcher};
 
 use char::CharExt;
 use clone::Clone;
@@ -34,100 +36,7 @@ use result::Result::{self, Ok, Err};
 use slice::{self, SliceExt};
 use usize;
 
-pub use self::pattern::Pattern;
-pub use self::pattern::{Searcher, ReverseSearcher, DoubleEndedSearcher, SearchStep};
-
-mod pattern;
-
-macro_rules! delegate_iter {
-    (exact $te:ty : $ti:ty) => {
-        delegate_iter!{$te : $ti}
-        impl<'a> ExactSizeIterator for $ti {
-            #[inline]
-            fn len(&self) -> usize {
-                self.0.len()
-            }
-        }
-    };
-    ($te:ty : $ti:ty) => {
-        #[stable(feature = "rust1", since = "1.0.0")]
-        impl<'a> Iterator for $ti {
-            type Item = $te;
-
-            #[inline]
-            fn next(&mut self) -> Option<$te> {
-                self.0.next()
-            }
-            #[inline]
-            fn size_hint(&self) -> (usize, Option<usize>) {
-                self.0.size_hint()
-            }
-        }
-        #[stable(feature = "rust1", since = "1.0.0")]
-        impl<'a> DoubleEndedIterator for $ti {
-            #[inline]
-            fn next_back(&mut self) -> Option<$te> {
-                self.0.next_back()
-            }
-        }
-    };
-    (pattern $te:ty : $ti:ty) => {
-        #[stable(feature = "rust1", since = "1.0.0")]
-        impl<'a, P: Pattern<'a>> Iterator for $ti {
-            type Item = $te;
-
-            #[inline]
-            fn next(&mut self) -> Option<$te> {
-                self.0.next()
-            }
-            #[inline]
-            fn size_hint(&self) -> (usize, Option<usize>) {
-                self.0.size_hint()
-            }
-        }
-        #[stable(feature = "rust1", since = "1.0.0")]
-        impl<'a, P: Pattern<'a>> DoubleEndedIterator for $ti
-        where P::Searcher: DoubleEndedSearcher<'a> {
-            #[inline]
-            fn next_back(&mut self) -> Option<$te> {
-                self.0.next_back()
-            }
-        }
-    };
-    (pattern forward $te:ty : $ti:ty) => {
-        #[stable(feature = "rust1", since = "1.0.0")]
-        impl<'a, P: Pattern<'a>> Iterator for $ti
-        where P::Searcher: DoubleEndedSearcher<'a> {
-            type Item = $te;
-
-            #[inline]
-            fn next(&mut self) -> Option<$te> {
-                self.0.next()
-            }
-            #[inline]
-            fn size_hint(&self) -> (usize, Option<usize>) {
-                self.0.size_hint()
-            }
-        }
-    };
-    (pattern reverse $te:ty : $ti:ty) => {
-        #[stable(feature = "rust1", since = "1.0.0")]
-        impl<'a, P: Pattern<'a>> Iterator for $ti
-            where P::Searcher: ReverseSearcher<'a>
-        {
-            type Item = $te;
-
-            #[inline]
-            fn next(&mut self) -> Option<$te> {
-                self.0.next()
-            }
-            #[inline]
-            fn size_hint(&self) -> (usize, Option<usize>) {
-                self.0.size_hint()
-            }
-        }
-    };
-}
+pub mod pattern;
 
 /// A trait to abstract the idea of creating a new instance of a type from a
 /// string.
@@ -443,11 +352,9 @@ impl<'a> DoubleEndedIterator for CharIndices<'a> {
 #[stable(feature = "rust1", since = "1.0.0")]
 #[derive(Clone)]
 pub struct Bytes<'a>(Map<slice::Iter<'a, u8>, BytesDeref>);
-delegate_iter!{exact u8 : Bytes<'a>}
 
-/// A temporary fn new type that ensures that the `Bytes` iterator
-/// is cloneable.
-#[derive(Copy, Clone)]
+/// A nameable, clonable fn type
+#[derive(Clone)]
 struct BytesDeref;
 
 impl<'a> Fn<(&'a u8,)> for BytesDeref {
@@ -473,58 +380,210 @@ impl<'a> FnOnce<(&'a u8,)> for BytesDeref {
     }
 }
 
-/// An iterator over the substrings of a string, separated by `sep`.
-struct CharSplits<'a, P: Pattern<'a>> {
-    /// The slice remaining to be iterated
-    start: usize,
-    end: usize,
-    matcher: P::Searcher,
-    /// Whether an empty string at the end is allowed
-    allow_trailing_empty: bool,
-    finished: bool,
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a> Iterator for Bytes<'a> {
+    type Item = u8;
+
+    #[inline]
+    fn next(&mut self) -> Option<u8> {
+        self.0.next()
+    }
+
+    #[inline]
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.0.size_hint()
+    }
 }
 
-/// An iterator over the substrings of a string, separated by `sep`,
-/// splitting at most `count` times.
-struct CharSplitsN<'a, P: Pattern<'a>> {
-    iter: CharSplits<'a, P>,
-    /// The number of items remaining
-    count: usize,
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a> DoubleEndedIterator for Bytes<'a> {
+    #[inline]
+    fn next_back(&mut self) -> Option<u8> {
+        self.0.next_back()
+    }
 }
 
-/// An iterator over the substrings of a string, separated by a
-/// pattern, in reverse order.
-struct RCharSplits<'a, P: Pattern<'a>> {
-    /// The slice remaining to be iterated
-    start: usize,
-    end: usize,
-    matcher: P::Searcher,
-    /// Whether an empty string at the end of iteration is allowed
-    allow_final_empty: bool,
-    finished: bool,
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a> ExactSizeIterator for Bytes<'a> {
+    #[inline]
+    fn len(&self) -> usize {
+        self.0.len()
+    }
 }
 
-/// An iterator over the substrings of a string, separated by a
-/// pattern, splitting at most `count` times, in reverse order.
-struct RCharSplitsN<'a, P: Pattern<'a>> {
-    iter: RCharSplits<'a, P>,
-    /// The number of splits remaining
-    count: usize,
+/// This macro generates a Clone impl for string pattern API
+/// wrapper types of the form X<'a, P>
+macro_rules! derive_pattern_clone {
+    (clone $t:ident with |$s:ident| $e:expr) => {
+        impl<'a, P: Pattern<'a>> Clone for $t<'a, P>
+            where P::Searcher: Clone
+        {
+            fn clone(&self) -> Self {
+                let $s = self;
+                $e
+            }
+        }
+    }
 }
 
-/// An iterator over the lines of a string, separated by `\n`.
-#[stable(feature = "rust1", since = "1.0.0")]
-pub struct Lines<'a> {
-    inner: CharSplits<'a, char>,
+/// This macro generates two public iterator structs
+/// wrapping an private internal one that makes use of the `Pattern` API.
+///
+/// For all patterns `P: Pattern<'a>` the following items will be
+/// generated (generics ommitted):
+///
+/// struct $forward_iterator($internal_iterator);
+/// struct $reverse_iterator($internal_iterator);
+///
+/// impl Iterator for $forward_iterator
+/// { /* internal ends up calling Searcher::next_match() */ }
+///
+/// impl DoubleEndedIterator for $forward_iterator
+///       where P::Searcher: DoubleEndedSearcher
+/// { /* internal ends up calling Searcher::next_match_back() */ }
+///
+/// impl Iterator for $reverse_iterator
+///       where P::Searcher: ReverseSearcher
+/// { /* internal ends up calling Searcher::next_match_back() */ }
+///
+/// impl DoubleEndedIterator for $reverse_iterator
+///       where P::Searcher: DoubleEndedSearcher
+/// { /* internal ends up calling Searcher::next_match() */ }
+///
+/// The internal one is defined outside the macro, and has almost the same
+/// semantic as a DoubleEndedIterator by delegating to `pattern::Searcher` and
+/// `pattern::ReverseSearcher` for both forward and reverse iteration.
+///
+/// "Almost", because a `Searcher` and a `ReverseSearcher` for a given
+/// `Pattern` might not return the same elements, so actually implementing
+/// `DoubleEndedIterator` for it would be incorrect.
+/// (See the docs in `str::pattern` for more details)
+///
+/// However, the internal struct still represents a single ended iterator from
+/// either end, and depending on pattern is also a valid double ended iterator,
+/// so the two wrapper structs implement `Iterator`
+/// and `DoubleEndedIterator` depending on the concrete pattern type, leading
+/// to the complex impls seen above.
+macro_rules! generate_pattern_iterators {
+    {
+        // Forward iterator
+        forward:
+            $(#[$forward_iterator_attribute:meta])*
+            struct $forward_iterator:ident;
+
+        // Reverse iterator
+        reverse:
+            $(#[$reverse_iterator_attribute:meta])*
+            struct $reverse_iterator:ident;
+
+        // Stability of all generated items
+        stability:
+            $(#[$common_stability_attribute:meta])*
+
+        // Internal almost-iterator that is being delegated to
+        internal:
+            $internal_iterator:ident yielding ($iterty:ty);
+
+        // Kind of delgation - either single ended or double ended
+        delegate $($t:tt)*
+    } => {
+        $(#[$forward_iterator_attribute])*
+        $(#[$common_stability_attribute])*
+        pub struct $forward_iterator<'a, P: Pattern<'a>>($internal_iterator<'a, P>);
+
+        $(#[$common_stability_attribute])*
+        impl<'a, P: Pattern<'a>> Iterator for $forward_iterator<'a, P> {
+            type Item = $iterty;
+
+            #[inline]
+            fn next(&mut self) -> Option<$iterty> {
+                self.0.next()
+            }
+        }
+
+        $(#[$common_stability_attribute])*
+        impl<'a, P: Pattern<'a>> Clone for $forward_iterator<'a, P>
+            where P::Searcher: Clone
+        {
+            fn clone(&self) -> Self {
+                $forward_iterator(self.0.clone())
+            }
+        }
+
+        $(#[$reverse_iterator_attribute])*
+        $(#[$common_stability_attribute])*
+        pub struct $reverse_iterator<'a, P: Pattern<'a>>($internal_iterator<'a, P>);
+
+        $(#[$common_stability_attribute])*
+        impl<'a, P: Pattern<'a>> Iterator for $reverse_iterator<'a, P>
+            where P::Searcher: ReverseSearcher<'a>
+        {
+            type Item = $iterty;
+
+            #[inline]
+            fn next(&mut self) -> Option<$iterty> {
+                self.0.next_back()
+            }
+        }
+
+        $(#[$common_stability_attribute])*
+        impl<'a, P: Pattern<'a>> Clone for $reverse_iterator<'a, P>
+            where P::Searcher: Clone
+        {
+            fn clone(&self) -> Self {
+                $reverse_iterator(self.0.clone())
+            }
+        }
+
+        generate_pattern_iterators!($($t)* with $(#[$common_stability_attribute])*,
+                                                $forward_iterator,
+                                                $reverse_iterator, $iterty);
+    };
+    {
+        double ended; with $(#[$common_stability_attribute:meta])*,
+                           $forward_iterator:ident,
+                           $reverse_iterator:ident, $iterty:ty
+    } => {
+        $(#[$common_stability_attribute])*
+        impl<'a, P: Pattern<'a>> DoubleEndedIterator for $forward_iterator<'a, P>
+            where P::Searcher: DoubleEndedSearcher<'a>
+        {
+            #[inline]
+            fn next_back(&mut self) -> Option<$iterty> {
+                self.0.next_back()
+            }
+        }
+
+        $(#[$common_stability_attribute])*
+        impl<'a, P: Pattern<'a>> DoubleEndedIterator for $reverse_iterator<'a, P>
+            where P::Searcher: DoubleEndedSearcher<'a>
+        {
+            #[inline]
+            fn next_back(&mut self) -> Option<$iterty> {
+                self.0.next()
+            }
+        }
+    };
+    {
+        single ended; with $(#[$common_stability_attribute:meta])*,
+                           $forward_iterator:ident,
+                           $reverse_iterator:ident, $iterty:ty
+    } => {}
 }
 
-/// An iterator over the lines of a string, separated by either `\n` or (`\r\n`).
-#[stable(feature = "rust1", since = "1.0.0")]
-pub struct LinesAny<'a> {
-    inner: Map<Lines<'a>, fn(&str) -> &str>,
+derive_pattern_clone!{
+    clone SplitInternal
+    with |s| SplitInternal { matcher: s.matcher.clone(), ..*s }
+}
+struct SplitInternal<'a, P: Pattern<'a>> {
+    start: usize,
+    end: usize,
+    matcher: P::Searcher,
+    allow_trailing_empty: bool,
+    finished: bool,
 }
 
-impl<'a, P: Pattern<'a>> CharSplits<'a, P> {
+impl<'a, P: Pattern<'a>> SplitInternal<'a, P> {
     #[inline]
     fn get_end(&mut self) -> Option<&'a str> {
         if !self.finished && (self.allow_trailing_empty || self.end - self.start > 0) {
@@ -537,11 +596,6 @@ impl<'a, P: Pattern<'a>> CharSplits<'a, P> {
             None
         }
     }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<'a, P: Pattern<'a>> Iterator for CharSplits<'a, P> {
-    type Item = &'a str;
 
     #[inline]
     fn next(&mut self) -> Option<&'a str> {
@@ -557,13 +611,11 @@ impl<'a, P: Pattern<'a>> Iterator for CharSplits<'a, P> {
             None => self.get_end(),
         }
     }
-}
 
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<'a, P: Pattern<'a>> DoubleEndedIterator for CharSplits<'a, P>
-where P::Searcher: DoubleEndedSearcher<'a> {
     #[inline]
-    fn next_back(&mut self) -> Option<&'a str> {
+    fn next_back(&mut self) -> Option<&'a str>
+        where P::Searcher: ReverseSearcher<'a>
+    {
         if self.finished { return None }
 
         if !self.allow_trailing_empty {
@@ -589,10 +641,45 @@ where P::Searcher: DoubleEndedSearcher<'a> {
     }
 }
 
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<'a, P: Pattern<'a>> Iterator for CharSplitsN<'a, P> {
-    type Item = &'a str;
+generate_pattern_iterators! {
+    forward:
+        /// Return type of `str::split()`
+        struct Split;
+    reverse:
+        /// Return type of `str::rsplit()`
+        struct RSplit;
+    stability:
+        #[stable(feature = "rust1", since = "1.0.0")]
+    internal:
+        SplitInternal yielding (&'a str);
+    delegate double ended;
+}
+
+generate_pattern_iterators! {
+    forward:
+        /// Return type of `str::split_terminator()`
+        struct SplitTerminator;
+    reverse:
+        /// Return type of `str::rsplit_terminator()`
+        struct RSplitTerminator;
+    stability:
+        #[stable(feature = "rust1", since = "1.0.0")]
+    internal:
+        SplitInternal yielding (&'a str);
+    delegate double ended;
+}
 
+derive_pattern_clone!{
+    clone SplitNInternal
+    with |s| SplitNInternal { iter: s.iter.clone(), ..*s }
+}
+struct SplitNInternal<'a, P: Pattern<'a>> {
+    iter: SplitInternal<'a, P>,
+    /// The number of splits remaining
+    count: usize,
+}
+
+impl<'a, P: Pattern<'a>> SplitNInternal<'a, P> {
     #[inline]
     fn next(&mut self) -> Option<&'a str> {
         match self.count {
@@ -601,58 +688,190 @@ impl<'a, P: Pattern<'a>> Iterator for CharSplitsN<'a, P> {
             _ => { self.count -= 1; self.iter.next() }
         }
     }
-}
 
-impl<'a, P: Pattern<'a>> RCharSplits<'a, P> {
     #[inline]
-    fn get_remainder(&mut self) -> Option<&'a str> {
-        if !self.finished && (self.allow_final_empty || self.end - self.start > 0) {
-            self.finished = true;
-            unsafe {
-                let string = self.matcher.haystack().slice_unchecked(self.start, self.end);
-                Some(string)
-            }
-        } else {
-            None
+    fn next_back(&mut self) -> Option<&'a str>
+        where P::Searcher: ReverseSearcher<'a>
+    {
+        match self.count {
+            0 => None,
+            1 => { self.count = 0; self.iter.get_end() }
+            _ => { self.count -= 1; self.iter.next_back() }
         }
     }
 }
 
+generate_pattern_iterators! {
+    forward:
+        /// Return type of `str::splitn()`
+        struct SplitN;
+    reverse:
+        /// Return type of `str::rsplitn()`
+        struct RSplitN;
+    stability:
+        #[stable(feature = "rust1", since = "1.0.0")]
+    internal:
+        SplitNInternal yielding (&'a str);
+    delegate single ended;
+}
+
+derive_pattern_clone!{
+    clone MatchIndicesInternal
+    with |s| MatchIndicesInternal(s.0.clone())
+}
+struct MatchIndicesInternal<'a, P: Pattern<'a>>(P::Searcher);
+
+impl<'a, P: Pattern<'a>> MatchIndicesInternal<'a, P> {
+    #[inline]
+    fn next(&mut self) -> Option<(usize, usize)> {
+        self.0.next_match()
+    }
+
+    #[inline]
+    fn next_back(&mut self) -> Option<(usize, usize)>
+        where P::Searcher: ReverseSearcher<'a>
+    {
+        self.0.next_match_back()
+    }
+}
+
+generate_pattern_iterators! {
+    forward:
+        /// Return type of `str::match_indices()`
+        struct MatchIndices;
+    reverse:
+        /// Return type of `str::rmatch_indices()`
+        struct RMatchIndices;
+    stability:
+        #[unstable(feature = "core",
+                   reason = "type may be removed or have its iterator impl changed")]
+    internal:
+        MatchIndicesInternal yielding ((usize, usize));
+    delegate double ended;
+}
+
+derive_pattern_clone!{
+    clone MatchesInternal
+    with |s| MatchesInternal(s.0.clone())
+}
+struct MatchesInternal<'a, P: Pattern<'a>>(P::Searcher);
+
+impl<'a, P: Pattern<'a>> MatchesInternal<'a, P> {
+    #[inline]
+    fn next(&mut self) -> Option<&'a str> {
+        self.0.next_match().map(|(a, b)| unsafe {
+            // Indices are known to be on utf8 boundaries
+            self.0.haystack().slice_unchecked(a, b)
+        })
+    }
+
+    #[inline]
+    fn next_back(&mut self) -> Option<&'a str>
+        where P::Searcher: ReverseSearcher<'a>
+    {
+        self.0.next_match_back().map(|(a, b)| unsafe {
+            // Indices are known to be on utf8 boundaries
+            self.0.haystack().slice_unchecked(a, b)
+        })
+    }
+}
+
+generate_pattern_iterators! {
+    forward:
+        /// Return type of `str::matches()`
+        struct Matches;
+    reverse:
+        /// Return type of `str::rmatches()`
+        struct RMatches;
+    stability:
+        #[unstable(feature = "core", reason = "type got recently added")]
+    internal:
+        MatchesInternal yielding (&'a str);
+    delegate double ended;
+}
+
+/// Return type of `str::lines()`
+#[stable(feature = "rust1", since = "1.0.0")]
+#[derive(Clone)]
+pub struct Lines<'a>(SplitTerminator<'a, char>);
+
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<'a, P: Pattern<'a>> Iterator for RCharSplits<'a, P>
-    where P::Searcher: ReverseSearcher<'a>
-{
+impl<'a> Iterator for Lines<'a> {
     type Item = &'a str;
 
     #[inline]
     fn next(&mut self) -> Option<&'a str> {
-        if self.finished { return None }
+        self.0.next()
+    }
 
-        let haystack = self.matcher.haystack();
-        match self.matcher.next_match_back() {
-            Some((a, b)) => unsafe {
-                let elt = haystack.slice_unchecked(b, self.end);
-                self.end = a;
-                Some(elt)
-            },
-            None => self.get_remainder(),
-        }
+    #[inline]
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.0.size_hint()
+    }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a> DoubleEndedIterator for Lines<'a> {
+    #[inline]
+    fn next_back(&mut self) -> Option<&'a str> {
+        self.0.next_back()
+    }
+}
+
+/// Return type of `str::lines_any()`
+#[stable(feature = "rust1", since = "1.0.0")]
+#[derive(Clone)]
+pub struct LinesAny<'a>(Map<Lines<'a>, LinesAnyMap>);
+
+/// A nameable, clonable fn type
+#[derive(Clone)]
+struct LinesAnyMap;
+
+impl<'a> Fn<(&'a str,)> for LinesAnyMap {
+    #[inline]
+    extern "rust-call" fn call(&self, (line,): (&'a str,)) -> &'a str {
+        let l = line.len();
+        if l > 0 && line.as_bytes()[l - 1] == b'\r' { &line[0 .. l - 1] }
+        else { line }
+    }
+}
+
+impl<'a> FnMut<(&'a str,)> for LinesAnyMap {
+    #[inline]
+    extern "rust-call" fn call_mut(&mut self, (line,): (&'a str,)) -> &'a str {
+        Fn::call(&*self, (line,))
+    }
+}
+
+impl<'a> FnOnce<(&'a str,)> for LinesAnyMap {
+    type Output = &'a str;
+
+    #[inline]
+    extern "rust-call" fn call_once(self, (line,): (&'a str,)) -> &'a str {
+        Fn::call(&self, (line,))
     }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<'a, P: Pattern<'a>> Iterator for RCharSplitsN<'a, P>
-    where P::Searcher: ReverseSearcher<'a>
-{
+impl<'a> Iterator for LinesAny<'a> {
     type Item = &'a str;
 
     #[inline]
     fn next(&mut self) -> Option<&'a str> {
-        match self.count {
-            0 => None,
-            1 => { self.count -= 1; self.iter.get_remainder() }
-            _ => { self.count -= 1; self.iter.next() }
-        }
+        self.0.next()
+    }
+
+    #[inline]
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.0.size_hint()
+    }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a> DoubleEndedIterator for LinesAny<'a> {
+    #[inline]
+    fn next_back(&mut self) -> Option<&'a str> {
+        self.0.next_back()
     }
 }
 
@@ -938,22 +1157,6 @@ struct OldMatchIndices<'a, 'b> {
     searcher: OldSearcher
 }
 
-// FIXME: #21637 Prevents a Clone impl
-/// An iterator over the start and end indices of the matches of a
-/// substring within a larger string
-#[unstable(feature = "core", reason = "type may be removed")]
-pub struct MatchIndices<'a, P: Pattern<'a>>(P::Searcher);
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<'a, P: Pattern<'a>> Iterator for MatchIndices<'a, P> {
-    type Item = (usize, usize);
-
-    #[inline]
-    fn next(&mut self) -> Option<(usize, usize)> {
-        self.0.next_match()
-    }
-}
-
 impl<'a, 'b>  OldMatchIndices<'a, 'b> {
     #[inline]
     #[allow(dead_code)]
@@ -1291,31 +1494,6 @@ impl<'a, S: ?Sized> Str for &'a S where S: Str {
     fn as_slice(&self) -> &str { Str::as_slice(*self) }
 }
 
-/// Return type of `str::split`
-#[stable(feature = "rust1", since = "1.0.0")]
-pub struct Split<'a, P: Pattern<'a>>(CharSplits<'a, P>);
-delegate_iter!{pattern &'a str : Split<'a, P>}
-
-/// Return type of `str::split_terminator`
-#[stable(feature = "rust1", since = "1.0.0")]
-pub struct SplitTerminator<'a, P: Pattern<'a>>(CharSplits<'a, P>);
-delegate_iter!{pattern &'a str : SplitTerminator<'a, P>}
-
-/// Return type of `str::splitn`
-#[stable(feature = "rust1", since = "1.0.0")]
-pub struct SplitN<'a, P: Pattern<'a>>(CharSplitsN<'a, P>);
-delegate_iter!{pattern forward &'a str : SplitN<'a, P>}
-
-/// Return type of `str::rsplit`
-#[stable(feature = "rust1", since = "1.0.0")]
-pub struct RSplit<'a, P: Pattern<'a>>(RCharSplits<'a, P>);
-delegate_iter!{pattern reverse &'a str : RSplit<'a, P>}
-
-/// Return type of `str::rsplitn`
-#[stable(feature = "rust1", since = "1.0.0")]
-pub struct RSplitN<'a, P: Pattern<'a>>(RCharSplitsN<'a, P>);
-delegate_iter!{pattern reverse &'a str : RSplitN<'a, P>}
-
 /// Methods for string slices
 #[allow(missing_docs)]
 pub trait StrExt {
@@ -1328,13 +1506,20 @@ pub trait StrExt {
     fn bytes<'a>(&'a self) -> Bytes<'a>;
     fn char_indices<'a>(&'a self) -> CharIndices<'a>;
     fn split<'a, P: Pattern<'a>>(&'a self, pat: P) -> Split<'a, P>;
-    fn splitn<'a, P: Pattern<'a>>(&'a self, count: usize, pat: P) -> SplitN<'a, P>;
-    fn split_terminator<'a, P: Pattern<'a>>(&'a self, pat: P) -> SplitTerminator<'a, P>;
     fn rsplit<'a, P: Pattern<'a>>(&'a self, pat: P) -> RSplit<'a, P>
         where P::Searcher: ReverseSearcher<'a>;
+    fn splitn<'a, P: Pattern<'a>>(&'a self, count: usize, pat: P) -> SplitN<'a, P>;
     fn rsplitn<'a, P: Pattern<'a>>(&'a self, count: usize, pat: P) -> RSplitN<'a, P>
         where P::Searcher: ReverseSearcher<'a>;
+    fn split_terminator<'a, P: Pattern<'a>>(&'a self, pat: P) -> SplitTerminator<'a, P>;
+    fn rsplit_terminator<'a, P: Pattern<'a>>(&'a self, pat: P) -> RSplitTerminator<'a, P>
+        where P::Searcher: ReverseSearcher<'a>;
+    fn matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> Matches<'a, P>;
+    fn rmatches<'a, P: Pattern<'a>>(&'a self, pat: P) -> RMatches<'a, P>
+        where P::Searcher: ReverseSearcher<'a>;
     fn match_indices<'a, P: Pattern<'a>>(&'a self, pat: P) -> MatchIndices<'a, P>;
+    fn rmatch_indices<'a, P: Pattern<'a>>(&'a self, pat: P) -> RMatchIndices<'a, P>
+        where P::Searcher: ReverseSearcher<'a>;
     fn lines<'a>(&'a self) -> Lines<'a>;
     fn lines_any<'a>(&'a self) -> LinesAny<'a>;
     fn char_len(&self) -> usize;
@@ -1401,7 +1586,7 @@ impl StrExt for str {
 
     #[inline]
     fn split<'a, P: Pattern<'a>>(&'a self, pat: P) -> Split<'a, P> {
-        Split(CharSplits {
+        Split(SplitInternal {
             start: 0,
             end: self.len(),
             matcher: pat.into_searcher(self),
@@ -1411,63 +1596,73 @@ impl StrExt for str {
     }
 
     #[inline]
+    fn rsplit<'a, P: Pattern<'a>>(&'a self, pat: P) -> RSplit<'a, P>
+        where P::Searcher: ReverseSearcher<'a>
+    {
+        RSplit(self.split(pat).0)
+    }
+
+    #[inline]
     fn splitn<'a, P: Pattern<'a>>(&'a self, count: usize, pat: P) -> SplitN<'a, P> {
-        SplitN(CharSplitsN {
+        SplitN(SplitNInternal {
             iter: self.split(pat).0,
             count: count,
         })
     }
 
     #[inline]
+    fn rsplitn<'a, P: Pattern<'a>>(&'a self, count: usize, pat: P) -> RSplitN<'a, P>
+        where P::Searcher: ReverseSearcher<'a>
+    {
+        RSplitN(self.splitn(count, pat).0)
+    }
+
+    #[inline]
     fn split_terminator<'a, P: Pattern<'a>>(&'a self, pat: P) -> SplitTerminator<'a, P> {
-        SplitTerminator(CharSplits {
+        SplitTerminator(SplitInternal {
             allow_trailing_empty: false,
             ..self.split(pat).0
         })
     }
 
     #[inline]
-    fn rsplit<'a, P: Pattern<'a>>(&'a self, pat: P) -> RSplit<'a, P>
+    fn rsplit_terminator<'a, P: Pattern<'a>>(&'a self, pat: P) -> RSplitTerminator<'a, P>
         where P::Searcher: ReverseSearcher<'a>
     {
-        RSplit(RCharSplits {
-            start: 0,
-            end: self.len(),
-            matcher: pat.into_searcher(self),
-            allow_final_empty: true,
-            finished: false,
-        })
+        RSplitTerminator(self.split_terminator(pat).0)
     }
 
     #[inline]
-    fn rsplitn<'a, P: Pattern<'a>>(&'a self, count: usize, pat: P) -> RSplitN<'a, P>
+    fn matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> Matches<'a, P> {
+        Matches(MatchesInternal(pat.into_searcher(self)))
+    }
+
+    #[inline]
+    fn rmatches<'a, P: Pattern<'a>>(&'a self, pat: P) -> RMatches<'a, P>
         where P::Searcher: ReverseSearcher<'a>
     {
-        RSplitN(RCharSplitsN {
-            iter: self.rsplit(pat).0,
-            count: count,
-        })
+        RMatches(self.matches(pat).0)
     }
 
     #[inline]
     fn match_indices<'a, P: Pattern<'a>>(&'a self, pat: P) -> MatchIndices<'a, P> {
-        MatchIndices(pat.into_searcher(self))
+        MatchIndices(MatchIndicesInternal(pat.into_searcher(self)))
     }
 
     #[inline]
+    fn rmatch_indices<'a, P: Pattern<'a>>(&'a self, pat: P) -> RMatchIndices<'a, P>
+        where P::Searcher: ReverseSearcher<'a>
+    {
+        RMatchIndices(self.match_indices(pat).0)
+    }
+    #[inline]
     fn lines(&self) -> Lines {
-        Lines { inner: self.split_terminator('\n').0 }
+        Lines(self.split_terminator('\n'))
     }
 
+    #[inline]
     fn lines_any(&self) -> LinesAny {
-        fn f(line: &str) -> &str {
-            let l = line.len();
-            if l > 0 && line.as_bytes()[l - 1] == b'\r' { &line[0 .. l - 1] }
-            else { line }
-        }
-
-        let f: fn(&str) -> &str = f; // coerce to fn pointer
-        LinesAny { inner: self.lines().map(f) }
+        LinesAny(self.lines().map(LinesAnyMap))
     }
 
     #[inline]
@@ -1708,35 +1903,3 @@ impl<'a> Default for &'a str {
     #[stable(feature = "rust1", since = "1.0.0")]
     fn default() -> &'a str { "" }
 }
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<'a> Iterator for Lines<'a> {
-    type Item = &'a str;
-
-    #[inline]
-    fn next(&mut self) -> Option<&'a str> { self.inner.next() }
-    #[inline]
-    fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<'a> DoubleEndedIterator for Lines<'a> {
-    #[inline]
-    fn next_back(&mut self) -> Option<&'a str> { self.inner.next_back() }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<'a> Iterator for LinesAny<'a> {
-    type Item = &'a str;
-
-    #[inline]
-    fn next(&mut self) -> Option<&'a str> { self.inner.next() }
-    #[inline]
-    fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
-}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-impl<'a> DoubleEndedIterator for LinesAny<'a> {
-    #[inline]
-    fn next_back(&mut self) -> Option<&'a str> { self.inner.next_back() }
-}
diff --git a/src/libcore/str/pattern.rs b/src/libcore/str/pattern.rs
index 922ab2c14a6..9f701e1b031 100644
--- a/src/libcore/str/pattern.rs
+++ b/src/libcore/str/pattern.rs
@@ -8,6 +8,11 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+//! The string Pattern API.
+//!
+//! For more details, see the traits `Pattern`, `Searcher`,
+//! `ReverseSearcher` and `DoubleEndedSearcher`.
+
 use prelude::*;
 
 // Pattern
@@ -223,7 +228,9 @@ pub unsafe trait ReverseSearcher<'a>: Searcher<'a> {
 /// `"[aa]a"` or `"a[aa]"`, depending from which side it is searched.
 pub trait DoubleEndedSearcher<'a>: ReverseSearcher<'a> {}
 
+/////////////////////////////////////////////////////////////////////////////
 // Impl for a CharEq wrapper
+/////////////////////////////////////////////////////////////////////////////
 
 #[doc(hidden)]
 trait CharEq {
@@ -261,6 +268,7 @@ impl<'a> CharEq for &'a [char] {
 
 struct CharEqPattern<C: CharEq>(C);
 
+#[derive(Clone)]
 struct CharEqSearcher<'a, C: CharEq> {
     char_eq: C,
     haystack: &'a str,
@@ -330,17 +338,27 @@ unsafe impl<'a, C: CharEq> ReverseSearcher<'a> for CharEqSearcher<'a, C> {
 
 impl<'a, C: CharEq> DoubleEndedSearcher<'a> for CharEqSearcher<'a, C> {}
 
+/////////////////////////////////////////////////////////////////////////////
 // Impl for &str
+/////////////////////////////////////////////////////////////////////////////
 
 // Todo: Optimize the naive implementation here
 
+/// Associated type for `<&str as Pattern<'a>>::Searcher`.
 #[derive(Clone)]
-struct StrSearcher<'a, 'b> {
+pub struct StrSearcher<'a, 'b> {
     haystack: &'a str,
     needle: &'b str,
     start: usize,
     end: usize,
-    done: bool,
+    state: State,
+}
+
+#[derive(Clone, PartialEq)]
+enum State { Done, NotDone, Reject(usize, usize) }
+impl State {
+    #[inline] fn done(&self) -> bool { *self == State::Done }
+    #[inline] fn take(&mut self) -> State { ::mem::replace(self, State::NotDone) }
 }
 
 /// Non-allocating substring search.
@@ -357,7 +375,7 @@ impl<'a, 'b> Pattern<'a> for &'b str {
             needle: self,
             start: 0,
             end: haystack.len(),
-            done: false,
+            state: State::NotDone,
         }
     }
 }
@@ -374,8 +392,9 @@ unsafe impl<'a, 'b> Searcher<'a> for StrSearcher<'a, 'b>  {
         |m: &mut StrSearcher| {
             // Forward step for empty needle
             let current_start = m.start;
-            if !m.done {
+            if !m.state.done() {
                 m.start = m.haystack.char_range_at(current_start).next;
+                m.state = State::Reject(current_start, m.start);
             }
             SearchStep::Match(current_start, current_start)
         },
@@ -404,8 +423,9 @@ unsafe impl<'a, 'b> ReverseSearcher<'a> for StrSearcher<'a, 'b>  {
         |m: &mut StrSearcher| {
             // Backward step for empty needle
             let current_end = m.end;
-            if !m.done {
+            if !m.state.done() {
                 m.end = m.haystack.char_range_at_reverse(current_end).next;
+                m.state = State::Reject(m.end, current_end);
             }
             SearchStep::Match(current_end, current_end)
         },
@@ -435,137 +455,178 @@ fn str_search_step<F, G>(mut m: &mut StrSearcher,
     where F: FnOnce(&mut StrSearcher) -> SearchStep,
           G: FnOnce(&mut StrSearcher) -> SearchStep
 {
-    if m.done {
+    if m.state.done() {
         SearchStep::Done
     } else if m.needle.len() == 0 && m.start <= m.end {
         // Case for needle == ""
-        if m.start == m.end {
-            m.done = true;
+        if let State::Reject(a, b) = m.state.take() {
+            SearchStep::Reject(a, b)
+        } else {
+            if m.start == m.end {
+                m.state = State::Done;
+            }
+            empty_needle_step(&mut m)
         }
-        empty_needle_step(&mut m)
     } else if m.start + m.needle.len() <= m.end {
         // Case for needle != ""
         nonempty_needle_step(&mut m)
     } else if m.start < m.end {
         // Remaining slice shorter than needle, reject it
-        m.done = true;
+        m.state = State::Done;
         SearchStep::Reject(m.start, m.end)
     } else {
-        m.done = true;
+        m.state = State::Done;
         SearchStep::Done
     }
 }
 
-macro_rules! char_eq_pattern_impl {
-    ($wrapper:ty, $wrapper_ident:ident) => {
-        fn into_searcher(self, haystack: &'a str) -> $wrapper {
-            $wrapper_ident(CharEqPattern(self).into_searcher(haystack))
+/////////////////////////////////////////////////////////////////////////////
+
+macro_rules! pattern_methods {
+    ($t:ty, $pmap:expr, $smap:expr) => {
+        type Searcher = $t;
+
+        #[inline]
+        fn into_searcher(self, haystack: &'a str) -> $t {
+            ($smap)(($pmap)(self).into_searcher(haystack))
         }
+
         #[inline]
         fn is_contained_in(self, haystack: &'a str) -> bool {
-            CharEqPattern(self).is_contained_in(haystack)
+            ($pmap)(self).is_contained_in(haystack)
         }
+
         #[inline]
         fn is_prefix_of(self, haystack: &'a str) -> bool {
-            CharEqPattern(self).is_prefix_of(haystack)
+            ($pmap)(self).is_prefix_of(haystack)
         }
+
         #[inline]
         fn is_suffix_of(self, haystack: &'a str) -> bool
-            where $wrapper: ReverseSearcher<'a>
+            where $t: ReverseSearcher<'a>
         {
-            CharEqPattern(self).is_suffix_of(haystack)
+            ($pmap)(self).is_suffix_of(haystack)
         }
     }
 }
 
-// Pattern for char
-
-impl<'a> Pattern<'a> for char {
-    type Searcher = CharSearcher<'a>;
-    char_eq_pattern_impl!(CharSearcher<'a>, CharSearcher);
+macro_rules! searcher_methods {
+    (forward) => {
+        #[inline]
+        fn haystack(&self) -> &'a str {
+            self.0.haystack()
+        }
+        #[inline]
+        fn next(&mut self) -> SearchStep {
+            self.0.next()
+        }
+        #[inline]
+        fn next_match(&mut self) -> Option<(usize, usize)> {
+            self.0.next_match()
+        }
+        #[inline]
+        fn next_reject(&mut self) -> Option<(usize, usize)> {
+            self.0.next_reject()
+        }
+    };
+    (reverse) => {
+        #[inline]
+        fn next_back(&mut self) -> SearchStep {
+            self.0.next_back()
+        }
+        #[inline]
+        fn next_match_back(&mut self) -> Option<(usize, usize)> {
+            self.0.next_match_back()
+        }
+        #[inline]
+        fn next_reject_back(&mut self) -> Option<(usize, usize)> {
+            self.0.next_reject_back()
+        }
+    }
 }
 
-pub struct CharSearcher<'a>(CharEqSearcher<'a, char>);
+/////////////////////////////////////////////////////////////////////////////
+// Impl for char
+/////////////////////////////////////////////////////////////////////////////
+
+/// Associated type for `<char as Pattern<'a>>::Searcher`.
+#[derive(Clone)]
+pub struct CharSearcher<'a>(<CharEqPattern<char> as Pattern<'a>>::Searcher);
 
 unsafe impl<'a> Searcher<'a> for CharSearcher<'a> {
-    #[inline]
-    fn haystack(&self) -> &'a str { self.0.haystack() }
-    #[inline]
-    fn next(&mut self) -> SearchStep { self.0.next() }
+    searcher_methods!(forward);
 }
+
 unsafe impl<'a> ReverseSearcher<'a> for CharSearcher<'a> {
-    #[inline]
-    fn next_back(&mut self) -> SearchStep { self.0.next_back() }
+    searcher_methods!(reverse);
 }
-impl<'a> DoubleEndedSearcher<'a> for CharSearcher<'a> {}
 
-// Pattern for &[char]
+impl<'a> DoubleEndedSearcher<'a> for CharSearcher<'a> {}
 
-impl<'a, 'b> Pattern<'a> for &'b [char] {
-    type Searcher = CharSliceSearcher<'a, 'b>;
-    char_eq_pattern_impl!(CharSliceSearcher<'a, 'b>, CharSliceSearcher);
+/// Searches for chars that are equal to a given char
+impl<'a> Pattern<'a> for char {
+    pattern_methods!(CharSearcher<'a>, CharEqPattern, CharSearcher);
 }
 
-pub struct CharSliceSearcher<'a, 'b>(CharEqSearcher<'a, &'b [char]>);
+/////////////////////////////////////////////////////////////////////////////
+// Impl for &[char]
+/////////////////////////////////////////////////////////////////////////////
+
+// Todo: Change / Remove due to ambiguity in meaning.
+
+/// Associated type for `<&[char] as Pattern<'a>>::Searcher`.
+#[derive(Clone)]
+pub struct CharSliceSearcher<'a, 'b>(<CharEqPattern<&'b [char]> as Pattern<'a>>::Searcher);
 
 unsafe impl<'a, 'b> Searcher<'a> for CharSliceSearcher<'a, 'b> {
-    #[inline]
-    fn haystack(&self) -> &'a str { self.0.haystack() }
-    #[inline]
-    fn next(&mut self) -> SearchStep { self.0.next() }
+    searcher_methods!(forward);
 }
+
 unsafe impl<'a, 'b> ReverseSearcher<'a> for CharSliceSearcher<'a, 'b> {
-    #[inline]
-    fn next_back(&mut self) -> SearchStep { self.0.next_back() }
+    searcher_methods!(reverse);
 }
-impl<'a, 'b> DoubleEndedSearcher<'a> for CharSliceSearcher<'a, 'b> {}
 
-// Pattern for predicates
+impl<'a, 'b> DoubleEndedSearcher<'a> for CharSliceSearcher<'a, 'b> {}
 
-impl<'a, F: FnMut(char) -> bool> Pattern<'a> for F {
-    type Searcher = CharPredSearcher<'a, F>;
-    char_eq_pattern_impl!(CharPredSearcher<'a, F>, CharPredSearcher);
+/// Searches for chars that are equal to any of the chars in the array
+impl<'a, 'b> Pattern<'a> for &'b [char] {
+    pattern_methods!(CharSliceSearcher<'a, 'b>, CharEqPattern, CharSliceSearcher);
 }
 
-pub struct CharPredSearcher<'a, F: FnMut(char) -> bool>(CharEqSearcher<'a, F>);
+/////////////////////////////////////////////////////////////////////////////
+// Impl for F: FnMut(char) -> bool
+/////////////////////////////////////////////////////////////////////////////
+
+/// Associated type for `<F as Pattern<'a>>::Searcher`.
+#[derive(Clone)]
+pub struct CharPredicateSearcher<'a, F>(<CharEqPattern<F> as Pattern<'a>>::Searcher)
+    where F: FnMut(char) -> bool;
 
-unsafe impl<'a, F> Searcher<'a> for CharPredSearcher<'a, F>
+unsafe impl<'a, F> Searcher<'a> for CharPredicateSearcher<'a, F>
     where F: FnMut(char) -> bool
 {
-    #[inline]
-    fn haystack(&self) -> &'a str { self.0.haystack() }
-    #[inline]
-    fn next(&mut self) -> SearchStep { self.0.next() }
+    searcher_methods!(forward);
 }
-unsafe impl<'a, F> ReverseSearcher<'a> for CharPredSearcher<'a, F>
+
+unsafe impl<'a, F> ReverseSearcher<'a> for CharPredicateSearcher<'a, F>
     where F: FnMut(char) -> bool
 {
-    #[inline]
-    fn next_back(&mut self) -> SearchStep { self.0.next_back() }
+    searcher_methods!(reverse);
 }
-impl<'a, F> DoubleEndedSearcher<'a> for CharPredSearcher<'a, F>
-    where F: FnMut(char) -> bool
-{}
 
-// Pattern for &&str
+impl<'a, F> DoubleEndedSearcher<'a> for CharPredicateSearcher<'a, F>
+    where F: FnMut(char) -> bool {}
 
+/// Searches for chars that match the given predicate
+impl<'a, F> Pattern<'a> for F where F: FnMut(char) -> bool {
+    pattern_methods!(CharPredicateSearcher<'a, F>, CharEqPattern, CharPredicateSearcher);
+}
+
+/////////////////////////////////////////////////////////////////////////////
+// Impl for &&str
+/////////////////////////////////////////////////////////////////////////////
+
+/// Delegates to the `&str` impl.
 impl<'a, 'b> Pattern<'a> for &'b &'b str {
-    type Searcher = <&'b str as Pattern<'a>>::Searcher;
-    #[inline]
-    fn into_searcher(self, haystack: &'a str)
-                     -> <&'b str as Pattern<'a>>::Searcher {
-        (*self).into_searcher(haystack)
-    }
-    #[inline]
-    fn is_contained_in(self, haystack: &'a str) -> bool {
-        (*self).is_contained_in(haystack)
-    }
-    #[inline]
-    fn is_prefix_of(self, haystack: &'a str) -> bool {
-        (*self).is_prefix_of(haystack)
-    }
-    #[inline]
-    fn is_suffix_of(self, haystack: &'a str) -> bool {
-        (*self).is_suffix_of(haystack)
-    }
+    pattern_methods!(StrSearcher<'a, 'b>, |&s| s, |s| s);
 }