Implemented remaining string pattern iterators.

- Added missing reverse versions of methods
- Added [r]matches()
- Generated the string pattern iterators with a macro
- Added where bounds to the methods returning reverse iterators
  for better error messages.

3 files changed, 753 insertions, 389 deletions

diff --git a/src/libcollections/str.rs b/src/libcollections/str.rs
index c22b6fb9286..08af7879688 100644
--- a/src/libcollections/str.rs
+++ b/src/libcollections/str.rs
@@ -69,9 +69,12 @@ use vec::Vec;
 use slice::SliceConcatExt;
 
 pub use core::str::{FromStr, Utf8Error, Str};
-pub use core::str::{Lines, LinesAny, MatchIndices, CharRange};
-pub use core::str::{Split, SplitTerminator, SplitN};
-pub use core::str::{RSplit, RSplitN};
+pub use core::str::{Lines, LinesAny, CharRange};
+pub use core::str::{Split, RSplit};
+pub use core::str::{SplitN, RSplitN};
+pub use core::str::{SplitTerminator, RSplitTerminator};
+pub use core::str::{Matches, RMatches};
+pub use core::str::{MatchIndices, RMatchIndices};
 pub use core::str::{from_utf8, Chars, CharIndices, Bytes};
 pub use core::str::{from_utf8_unchecked, ParseBoolError};
 pub use unicode::str::{Words, Graphemes, GraphemeIndices};
@@ -581,12 +584,22 @@ impl str {
     /// An iterator over substrings of `self`, separated by characters
     /// matched by a pattern.
     ///
-    /// The pattern can be a simple `&str`, or a closure that determines
+    /// The pattern can be a simple `&str`, `char`, or a closure that determines
     /// the split.
+    /// Additional libraries might provide more complex patterns like regular expressions.
+    ///
+    /// # Iterator behavior
+    ///
+    /// The returned iterator will be double ended if the pattern allows a reverse search
+    /// and forward/reverse search yields the same elements. This is true for, eg, `char` but not
+    /// for `&str`.
+    ///
+    /// If the pattern allows a reverse search but its results might differ
+    /// from a forward search, `rsplit()` can be used.
     ///
     /// # Examples
     ///
-    /// Simple `&str` patterns:
+    /// Simple patterns:
     ///
     /// ```
     /// let v: Vec<&str> = "Mary had a little lamb".split(' ').collect();
@@ -594,6 +607,12 @@ impl str {
     ///
     /// let v: Vec<&str> = "".split('X').collect();
     /// assert_eq!(v, [""]);
+    ///
+    /// let v: Vec<&str> = "lionXXtigerXleopard".split('X').collect();
+    /// assert_eq!(v, ["lion", "", "tiger", "leopard"]);
+    ///
+    /// let v: Vec<&str> = "lion::tiger::leopard".split("::").collect();
+    /// assert_eq!(v, ["lion", "tiger", "leopard"]);
     /// ```
     ///
     /// More complex patterns with a lambda:
@@ -602,69 +621,92 @@ impl str {
     /// let v: Vec<&str> = "abc1def2ghi".split(|c: char| c.is_numeric()).collect();
     /// assert_eq!(v, ["abc", "def", "ghi"]);
     ///
-    /// let v: Vec<&str> = "lionXXtigerXleopard".split('X').collect();
-    /// assert_eq!(v, ["lion", "", "tiger", "leopard"]);
+    /// let v: Vec<&str> = "lionXtigerXleopard".split(|c: char| c.is_uppercase()).collect();
+    /// assert_eq!(v, ["lion", "tiger", "leopard"]);
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn split<'a, P: Pattern<'a>>(&'a self, pat: P) -> Split<'a, P> {
         core_str::StrExt::split(&self[..], pat)
     }
 
-    /// An iterator over substrings of `self`, separated by characters matched
-    /// by a pattern, returning most `count` items.
+    /// An iterator over substrings of `self`, separated by characters
+    /// matched by a pattern and yielded in reverse order.
     ///
-    /// The pattern can be a simple `&str`, or a closure that determines
+    /// The pattern can be a simple `&str`, `char`, or a closure that determines
     /// the split.
+    /// Additional libraries might provide more complex patterns like regular expressions.
     ///
-    /// The last element returned, if any, will contain the remainder of the
-    /// string.
+    /// # Iterator behavior
     ///
-    /// # Examples
+    /// The returned iterator requires that the pattern supports a reverse search,
+    /// and it will be double ended if a forward/reverse search yields the same elements.
     ///
-    /// Simple `&str` patterns:
+    /// For iterating from the front, `split()` can be used.
     ///
-    /// ```
-    /// let v: Vec<&str> = "Mary had a little lambda".splitn(2, ' ').collect();
-    /// assert_eq!(v, ["Mary", "had a little lambda"]);
+    /// # Examples
     ///
-    /// let v: Vec<&str> = "lionXXtigerXleopard".splitn(2, 'X').collect();
-    /// assert_eq!(v, ["lion", "XtigerXleopard"]);
+    /// Simple patterns:
     ///
-    /// let v: Vec<&str> = "abcXdef".splitn(1, 'X').collect();
-    /// assert_eq!(v, ["abcXdef"]);
+    /// ```rust
+    /// let v: Vec<&str> = "Mary had a little lamb".rsplit(' ').collect();
+    /// assert_eq!(v, ["lamb", "little", "a", "had", "Mary"]);
     ///
-    /// let v: Vec<&str> = "".splitn(1, 'X').collect();
+    /// let v: Vec<&str> = "".rsplit('X').collect();
     /// assert_eq!(v, [""]);
+    ///
+    /// let v: Vec<&str> = "lionXXtigerXleopard".rsplit('X').collect();
+    /// assert_eq!(v, ["leopard", "tiger", "", "lion"]);
+    ///
+    /// let v: Vec<&str> = "lion::tiger::leopard".rsplit("::").collect();
+    /// assert_eq!(v, ["leopard", "tiger", "lion"]);
     /// ```
     ///
     /// More complex patterns with a lambda:
     ///
-    /// ```
-    /// let v: Vec<&str> = "abc1def2ghi".splitn(2, |c: char| c.is_numeric()).collect();
-    /// assert_eq!(v, ["abc", "def2ghi"]);
+    /// ```rust
+    /// let v: Vec<&str> = "abc1def2ghi".rsplit(|c: char| c.is_numeric()).collect();
+    /// assert_eq!(v, ["ghi", "def", "abc"]);
+    ///
+    /// let v: Vec<&str> = "lionXtigerXleopard".rsplit(|c: char| c.is_uppercase()).collect();
+    /// assert_eq!(v, ["leopard", "tiger", "lion"]);
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn splitn<'a, P: Pattern<'a>>(&'a self, count: usize, pat: P) -> SplitN<'a, P> {
-        core_str::StrExt::splitn(&self[..], count, pat)
+    pub fn rsplit<'a, P: Pattern<'a>>(&'a self, pat: P) -> RSplit<'a, P>
+        where P::Searcher: ReverseSearcher<'a>
+    {
+        core_str::StrExt::rsplit(&self[..], pat)
     }
 
     /// An iterator over substrings of `self`, separated by characters
     /// matched by a pattern.
     ///
+    /// The pattern can be a simple `&str`, `char`, or a closure that determines
+    /// the split.
+    /// Additional libraries might provide more complex patterns like regular expressions.
+    ///
     /// Equivalent to `split`, except that the trailing substring is skipped if empty.
     ///
-    /// The pattern can be a simple `&str`, or a closure that determines
-    /// the split.
+    /// This method can be used for string data that is _terminated_, rather than
+    /// _seperated_ by some string.
+    ///
+    /// # Iterator behavior
+    ///
+    /// The returned iterator will be double ended if the pattern allows a reverse search
+    /// and forward/reverse search yields the same elements. This is true for, eg, `char` but not
+    /// for `&str`.
+    ///
+    /// If the pattern allows a reverse search but its results might differ
+    /// from a forward search, `rsplit_terminator()` can be used.
     ///
     /// # Examples
     ///
-    /// Simple `&str` patterns:
+    /// Simple patterns:
     ///
     /// ```
     /// let v: Vec<&str> = "A.B.".split_terminator('.').collect();
     /// assert_eq!(v, ["A", "B"]);
     ///
-    /// let v: Vec<&str> = "A..B..".split_terminator('.').collect();
+    /// let v: Vec<&str> = "A..B..".split_terminator(".").collect();
     /// assert_eq!(v, ["A", "", "B", ""]);
     /// ```
     ///
@@ -679,32 +721,93 @@ impl str {
         core_str::StrExt::split_terminator(&self[..], pat)
     }
 
-    /// An iterator over substrings of `self`, separated by a pattern,
-    /// starting from the end of the string.
+    /// An iterator over substrings of `self`, separated by characters
+    /// matched by a pattern and yielded in reverse order.
+    ///
+    /// The pattern can be a simple `&str`, `char`, or a closure that determines
+    /// the split.
+    /// Additional libraries might provide more complex patterns like regular expressions.
+    ///
+    /// Equivalent to `split`, except that the trailing substring is skipped if empty.
+    ///
+    /// This method can be used for string data that is _terminated_, rather than
+    /// _seperated_ by some string.
+    ///
+    /// # Iterator behavior
+    ///
+    /// The returned iterator requires that the pattern supports a reverse search,
+    /// and it will be double ended if a forward/reverse search yields the same elements.
+    ///
+    /// For iterating from the front, `split_terminator()` can be used.
     ///
     /// # Examples
     ///
     /// Simple patterns:
     ///
     /// ```
-    /// let v: Vec<&str> = "Mary had a little lamb".rsplit(' ').collect();
-    /// assert_eq!(v, ["lamb", "little", "a", "had", "Mary"]);
+    /// let v: Vec<&str> = "A.B.".rsplit_terminator('.').collect();
+    /// assert_eq!(v, ["B", "A"]);
     ///
-    /// let v: Vec<&str> = "lion::tiger::leopard".rsplit("::").collect();
-    /// assert_eq!(v, ["leopard", "tiger", "lion"]);
+    /// let v: Vec<&str> = "A..B..".rsplit_terminator(".").collect();
+    /// assert_eq!(v, ["", "B", "", "A"]);
     /// ```
     ///
     /// More complex patterns with a lambda:
     ///
     /// ```
-    /// let v: Vec<&str> = "abc1def2ghi".rsplit(|c: char| c.is_numeric()).collect();
+    /// let v: Vec<&str> = "abc1def2ghi3".rsplit_terminator(|c: char| c.is_numeric()).collect();
     /// assert_eq!(v, ["ghi", "def", "abc"]);
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn rsplit<'a, P: Pattern<'a>>(&'a self, pat: P) -> RSplit<'a, P>
+    pub fn rsplit_terminator<'a, P: Pattern<'a>>(&'a self, pat: P) -> RSplitTerminator<'a, P>
         where P::Searcher: ReverseSearcher<'a>
     {
-        core_str::StrExt::rsplit(&self[..], pat)
+        core_str::StrExt::rsplit_terminator(&self[..], pat)
+    }
+
+    /// An iterator over substrings of `self`, separated by a pattern,
+    /// restricted to returning
+    /// at most `count` items.
+    ///
+    /// The last element returned, if any, will contain the remainder of the
+    /// string.
+    /// The pattern can be a simple `&str`, `char`, or a closure that determines
+    /// the split.
+    /// Additional libraries might provide more complex patterns like regular expressions.
+    ///
+    /// # Iterator behavior
+    ///
+    /// The returned iterator will not be double ended, because it is not efficient to support.
+    ///
+    /// If the pattern allows a reverse search, `rsplitn()` can be used.
+    ///
+    /// # Examples
+    ///
+    /// Simple patterns:
+    ///
+    /// ```
+    /// let v: Vec<&str> = "Mary had a little lambda".splitn(3, ' ').collect();
+    /// assert_eq!(v, ["Mary", "had", "a little lambda"]);
+    ///
+    /// let v: Vec<&str> = "lionXXtigerXleopard".splitn(3, "X").collect();
+    /// assert_eq!(v, ["lion", "", "tigerXleopard"]);
+    ///
+    /// let v: Vec<&str> = "abcXdef".splitn(1, 'X').collect();
+    /// assert_eq!(v, ["abcXdef"]);
+    ///
+    /// let v: Vec<&str> = "".splitn(1, 'X').collect();
+    /// assert_eq!(v, [""]);
+    /// ```
+    ///
+    /// More complex patterns with a lambda:
+    ///
+    /// ```
+    /// let v: Vec<&str> = "abc1def2ghi".splitn(2, |c: char| c.is_numeric()).collect();
+    /// assert_eq!(v, ["abc", "def2ghi"]);
+    /// ```
+    #[stable(feature = "rust1", since = "1.0.0")]
+    pub fn splitn<'a, P: Pattern<'a>>(&'a self, count: usize, pat: P) -> SplitN<'a, P> {
+        core_str::StrExt::splitn(&self[..], count, pat)
     }
 
     /// An iterator over substrings of `self`, separated by a pattern,
@@ -714,6 +817,16 @@ impl str {
     /// The last element returned, if any, will contain the remainder of the
     /// string.
     ///
+    /// The pattern can be a simple `&str`, `char`, or a closure that determines
+    /// the split.
+    /// Additional libraries might provide more complex patterns like regular expressions.
+    ///
+    /// # Iterator behavior
+    ///
+    /// The returned iterator will not be double ended, because it is not efficient to support.
+    ///
+    /// `splitn()` can be used for splitting from the front.
+    ///
     /// # Examples
     ///
     /// Simple patterns:
@@ -722,6 +835,9 @@ impl str {
     /// let v: Vec<&str> = "Mary had a little lamb".rsplitn(3, ' ').collect();
     /// assert_eq!(v, ["lamb", "little", "Mary had a"]);
     ///
+    /// let v: Vec<&str> = "lionXXtigerXleopard".rsplitn(3, 'X').collect();
+    /// assert_eq!(v, ["leopard", "tiger", "lionX"]);
+    ///
     /// let v: Vec<&str> = "lion::tiger::leopard".rsplitn(2, "::").collect();
     /// assert_eq!(v, ["leopard", "lion::tiger"]);
     /// ```
@@ -739,13 +855,87 @@ impl str {
         core_str::StrExt::rsplitn(&self[..], count, pat)
     }
 
-    /// An iterator over the start and end indices of the disjoint matches of a `&str` within
+    /// An iterator over the matches of a pattern within `self`.
+    ///
+    /// The pattern can be a simple `&str`, `char`, or a closure that determines
+    /// the split.
+    /// Additional libraries might provide more complex patterns like regular expressions.
+    ///
+    /// # Iterator behavior
+    ///
+    /// The returned iterator will be double ended if the pattern allows a reverse search
+    /// and forward/reverse search yields the same elements. This is true for, eg, `char` but not
+    /// for `&str`.
+    ///
+    /// If the pattern allows a reverse search but its results might differ
+    /// from a forward search, `rmatches()` can be used.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # #![feature(collections)]
+    /// let v: Vec<&str> = "abcXXXabcYYYabc".matches("abc").collect();
+    /// assert_eq!(v, ["abc", "abc", "abc"]);
+    ///
+    /// let v: Vec<&str> = "1abc2abc3".matches(|c: char| c.is_numeric()).collect();
+    /// assert_eq!(v, ["1", "2", "3"]);
+    /// ```
+    #[unstable(feature = "collections",
+               reason = "method got recently added")]
+    pub fn matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> Matches<'a, P> {
+        core_str::StrExt::matches(&self[..], pat)
+    }
+
+    /// An iterator over the matches of a pattern within `self`, yielded in reverse order.
+    ///
+    /// The pattern can be a simple `&str`, `char`, or a closure that determines
+    /// the split.
+    /// Additional libraries might provide more complex patterns like regular expressions.
+    ///
+    /// # Iterator behavior
+    ///
+    /// The returned iterator requires that the pattern supports a reverse search,
+    /// and it will be double ended if a forward/reverse search yields the same elements.
+    ///
+    /// For iterating from the front, `matches()` can be used.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # #![feature(collections)]
+    /// let v: Vec<&str> = "abcXXXabcYYYabc".rmatches("abc").collect();
+    /// assert_eq!(v, ["abc", "abc", "abc"]);
+    ///
+    /// let v: Vec<&str> = "1abc2abc3".rmatches(|c: char| c.is_numeric()).collect();
+    /// assert_eq!(v, ["3", "2", "1"]);
+    /// ```
+    #[unstable(feature = "collections",
+               reason = "method got recently added")]
+    pub fn rmatches<'a, P: Pattern<'a>>(&'a self, pat: P) -> RMatches<'a, P>
+        where P::Searcher: ReverseSearcher<'a>
+    {
+        core_str::StrExt::rmatches(&self[..], pat)
+    }
+
+    /// An iterator over the start and end indices of the disjoint matches of a pattern within
     /// `self`.
     ///
-    /// That is, each returned value `(start, end)` satisfies `self.slice(start, end) == sep`. For
-    /// matches of `sep` within `self` that overlap, only the indices corresponding to the first
+    /// For matches of `pat` within `self` that overlap, only the indices corresponding to the first
     /// match are returned.
     ///
+    /// The pattern can be a simple `&str`, `char`, or a closure that determines
+    /// the split.
+    /// Additional libraries might provide more complex patterns like regular expressions.
+    ///
+    /// # Iterator behavior
+    ///
+    /// The returned iterator will be double ended if the pattern allows a reverse search
+    /// and forward/reverse search yields the same elements. This is true for, eg, `char` but not
+    /// for `&str`.
+    ///
+    /// If the pattern allows a reverse search but its results might differ
+    /// from a forward search, `rmatch_indices()` can be used.
+    ///
     /// # Examples
     ///
     /// ```
@@ -761,12 +951,52 @@ impl str {
     /// ```
     #[unstable(feature = "collections",
                reason = "might have its iterator type changed")]
-    // NB: Right now MatchIndices yields `(usize, usize)`,
-    // but it would be more consistent and useful to return `(usize, &str)`
+    // NB: Right now MatchIndices yields `(usize, usize)`, but it would
+    // be more consistent with `matches` and `char_indices` to return `(usize, &str)`
     pub fn match_indices<'a, P: Pattern<'a>>(&'a self, pat: P) -> MatchIndices<'a, P> {
         core_str::StrExt::match_indices(&self[..], pat)
     }
 
+    /// An iterator over the start and end indices of the disjoint matches of a pattern within
+    /// `self`, yielded in reverse order.
+    ///
+    /// For matches of `pat` within `self` that overlap, only the indices corresponding to the last
+    /// match are returned.
+    ///
+    /// The pattern can be a simple `&str`, `char`, or a closure that determines
+    /// the split.
+    /// Additional libraries might provide more complex patterns like regular expressions.
+    ///
+    /// # Iterator behavior
+    ///
+    /// The returned iterator requires that the pattern supports a reverse search,
+    /// and it will be double ended if a forward/reverse search yields the same elements.
+    ///
+    /// For iterating from the front, `match_indices()` can be used.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # #![feature(collections)]
+    /// let v: Vec<(usize, usize)> = "abcXXXabcYYYabc".rmatch_indices("abc").collect();
+    /// assert_eq!(v, [(12,15), (6,9), (0,3)]);
+    ///
+    /// let v: Vec<(usize, usize)> = "1abcabc2".rmatch_indices("abc").collect();
+    /// assert_eq!(v, [(4,7), (1,4)]);
+    ///
+    /// let v: Vec<(usize, usize)> = "ababa".rmatch_indices("aba").collect();
+    /// assert_eq!(v, [(2, 5)]); // only the last `aba`
+    /// ```
+    #[unstable(feature = "collections",
+               reason = "might have its iterator type changed")]
+    // NB: Right now RMatchIndices yields `(usize, usize)`, but it would
+    // be more consistent with `rmatches` and `char_indices` to return `(usize, &str)`
+    pub fn rmatch_indices<'a, P: Pattern<'a>>(&'a self, pat: P) -> RMatchIndices<'a, P>
+        where P::Searcher: ReverseSearcher<'a>
+    {
+        core_str::StrExt::rmatch_indices(&self[..], pat)
+    }
+
     /// An iterator over the lines of a string, separated by `\n`.
     ///
     /// This does not include the empty string after a trailing `\n`.
diff --git a/src/libcore/str/mod.rs b/src/libcore/str/mod.rs
index dbb365c4e23..99284036fd2 100644
--- a/src/libcore/str/mod.rs
+++ b/src/libcore/str/mod.rs
@@ -39,96 +39,6 @@ pub use self::pattern::{Searcher, ReverseSearcher, DoubleEndedSearcher, SearchSt
 
 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()
-            }
-        }
-    };
-}
-
 /// A trait to abstract the idea of creating a new instance of a type from a
 /// string.
 #[stable(feature = "rust1", since = "1.0.0")]
@@ -444,11 +354,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 {
@@ -474,58 +382,173 @@ 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;
 
-/// 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,
-}
+    #[inline]
+    fn next(&mut self) -> Option<u8> {
+        self.0.next()
+    }
 
-/// 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,
+    #[inline]
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.0.size_hint()
+    }
 }
 
-/// 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,
+#[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 lines of a string, separated by `\n`.
 #[stable(feature = "rust1", since = "1.0.0")]
-pub struct Lines<'a> {
-    inner: CharSplits<'a, char>,
+impl<'a> ExactSizeIterator for Bytes<'a> {
+    #[inline]
+    fn len(&self) -> usize {
+        self.0.len()
+    }
 }
 
-/// 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>,
+/// 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()
+            }
+        }
+
+        $(#[$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()
+            }
+        }
+
+        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
+    } => {}
+}
+
+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) {
@@ -538,11 +561,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> {
@@ -558,13 +576,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 {
@@ -590,10 +606,41 @@ 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;
+}
+
+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 {
@@ -602,58 +649,151 @@ 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;
+}
+
+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;
+}
+
+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")]
+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")]
+pub struct LinesAny<'a>(Map<Lines<'a>, fn(&str) -> &str>);
+
 #[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()
     }
 }
 
@@ -939,22 +1079,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)]
@@ -1292,31 +1416,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 {
@@ -1329,13 +1428,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;
@@ -1402,7 +1508,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),
@@ -1412,54 +1518,71 @@ 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();
@@ -1468,7 +1591,7 @@ impl StrExt for str {
         }
 
         let f: fn(&str) -> &str = f; // coerce to fn pointer
-        LinesAny { inner: self.lines().map(f) }
+        LinesAny(self.lines().map(f))
     }
 
     #[inline]
@@ -1709,35 +1832,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..0c2a58f3ca7 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,12 +338,15 @@ 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,
@@ -456,116 +467,148 @@ fn str_search_step<F, G>(mut m: &mut StrSearcher,
     }
 }
 
-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) => {
+        // FIXME: #22463
+        //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 {
+    type Searcher =  CharSearcher<'a>;
+    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] {
+    type Searcher =  CharSliceSearcher<'a, 'b>;
+    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 {}
 
-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)
-    }
+/// Searches for chars that match the given predicate
+impl<'a, F> Pattern<'a> for F where F: FnMut(char) -> bool {
+    type Searcher =  CharPredicateSearcher<'a, F>;
+    pattern_methods!(CharPredicateSearcher<'a, F>, CharEqPattern, CharPredicateSearcher);
 }