Addressed PR comments

18 files changed, 233 insertions, 86 deletions

diff --git a/src/compiletest/compiletest.rs b/src/compiletest/compiletest.rs
index 30de253fbad..278ce5565d9 100644
--- a/src/compiletest/compiletest.rs
+++ b/src/compiletest/compiletest.rs
@@ -23,7 +23,7 @@
 #![feature(env)]
 #![feature(core)]
 
-// #![deny(warnings)]
+#![deny(warnings)]
 
 extern crate test;
 extern crate getopts;
diff --git a/src/compiletest/errors.rs b/src/compiletest/errors.rs
index d8faa53a2de..7411a9b48d4 100644
--- a/src/compiletest/errors.rs
+++ b/src/compiletest/errors.rs
@@ -58,7 +58,7 @@ pub fn load_errors(testfile: &Path) -> Vec<ExpectedError> {
 fn parse_expected(last_nonfollow_error: Option<uint>,
                   line_num: uint,
                   line: &str) -> Option<(WhichLine, ExpectedError)> {
-    let start = match line.find_str("//~") { Some(i) => i, None => return None };
+    let start = match line.find("//~") { Some(i) => i, None => return None };
     let (follow, adjusts) = if line.char_at(start + 3) == '|' {
         (true, 0)
     } else {
diff --git a/src/compiletest/header.rs b/src/compiletest/header.rs
index c2539679643..9c217651c3e 100644
--- a/src/compiletest/header.rs
+++ b/src/compiletest/header.rs
@@ -330,7 +330,7 @@ fn parse_name_directive(line: &str, directive: &str) -> bool {
 pub fn parse_name_value_directive(line: &str, directive: &str)
                                   -> Option<String> {
     let keycolon = format!("{}:", directive);
-    match line.find_str(&keycolon) {
+    match line.find(&keycolon) {
         Some(colon) => {
             let value = line[(colon + keycolon.len()) .. line.len()].to_string();
             debug!("{}: {}", directive, value);
diff --git a/src/compiletest/runtest.rs b/src/compiletest/runtest.rs
index 1cbb8742bbc..39ecc323125 100644
--- a/src/compiletest/runtest.rs
+++ b/src/compiletest/runtest.rs
@@ -847,7 +847,7 @@ fn check_debugger_output(debugger_run_result: &ProcRes, check_lines: &[String])
             check_lines.iter().map(|s| {
                 s
                  .trim()
-                 .split_str("[...]")
+                 .split("[...]")
                  .map(|x| x.to_string())
                  .collect()
             }).collect();
@@ -866,7 +866,7 @@ fn check_debugger_output(debugger_run_result: &ProcRes, check_lines: &[String])
                         None
                     }
                 } else {
-                    rest.find_str(frag)
+                    rest.find(frag)
                 };
                 match found {
                     None => {
diff --git a/src/libcollections/str.rs b/src/libcollections/str.rs
index e86cf462cab..92dc01dc3e4 100644
--- a/src/libcollections/str.rs
+++ b/src/libcollections/str.rs
@@ -547,8 +547,8 @@ pub trait StrExt: Index<RangeFull, Output = str> {
     /// ```rust
     /// assert!("hello".contains_char('e'));
     /// ```
-    #[unstable(feature = "collections",
-               reason = "might get removed in favour of a more generic contains()")]
+    #[unstable(feature = "collections")]
+    #[deprecated(since = "1.0.0", reason = "use `contains()` with a char")]
     fn contains_char<'a, P: Pattern<'a>>(&'a self, pat: P) -> bool {
         core_str::StrExt::contains_char(&self[..], pat)
     }
@@ -660,7 +660,7 @@ pub trait StrExt: Index<RangeFull, Output = str> {
     /// let v: Vec<&str> = "lionXXtigerXleopard".split('X').rev().collect();
     /// assert_eq!(v, vec!["leopard", "tiger", "", "lion"]);
     /// ```
-    #[unstable(feature = "collections", reason = "might get removed")]
+    #[stable(feature = "rust1", since = "1.0.0")]
     fn split_terminator<'a, P: Pattern<'a>>(&'a self, pat: P) -> SplitTerminator<'a, P> {
         core_str::StrExt::split_terminator(&self[..], pat)
     }
@@ -708,6 +708,8 @@ pub trait StrExt: Index<RangeFull, Output = 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)`
     fn match_indices<'a, P: Pattern<'a>>(&'a self, pat: P) -> MatchIndices<'a, P> {
         core_str::StrExt::match_indices(&self[..], pat)
     }
@@ -723,8 +725,8 @@ pub trait StrExt: Index<RangeFull, Output = str> {
     /// let v: Vec<&str> = "1abcabc2".split_str("abc").collect();
     /// assert_eq!(v, vec!["1", "", "2"]);
     /// ```
-    #[unstable(feature = "collections",
-               reason = "might get removed in the future in favor of a more generic split()")]
+    #[unstable(feature = "collections")]
+    #[deprecated(since = "1.0.0", reason = "use `split()` with a `&str`")]
     fn split_str<'a, P: Pattern<'a>>(&'a self, pat: P) -> SplitStr<'a, P> {
         core_str::StrExt::split_str(&self[..], pat)
     }
@@ -840,7 +842,8 @@ pub trait StrExt: Index<RangeFull, Output = str> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     fn ends_with<'a, P: Pattern<'a>>(&'a self, pat: P) -> bool
-    where P::Searcher: ReverseSearcher<'a> {
+        where P::Searcher: ReverseSearcher<'a>
+    {
         core_str::StrExt::ends_with(&self[..], pat)
     }
 
@@ -861,7 +864,8 @@ pub trait StrExt: Index<RangeFull, Output = str> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     fn trim_matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> &'a str
-    where P::Searcher: DoubleEndedSearcher<'a> {
+        where P::Searcher: DoubleEndedSearcher<'a>
+    {
         core_str::StrExt::trim_matches(&self[..], pat)
     }
 
@@ -902,7 +906,8 @@ pub trait StrExt: Index<RangeFull, Output = str> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     fn trim_right_matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> &'a str
-    where P::Searcher: ReverseSearcher<'a> {
+        where P::Searcher: ReverseSearcher<'a>
+    {
         core_str::StrExt::trim_right_matches(&self[..], pat)
     }
 
@@ -1108,7 +1113,8 @@ pub trait StrExt: Index<RangeFull, Output = str> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     fn rfind<'a, P: Pattern<'a>>(&'a self, pat: P) -> Option<usize>
-    where P::Searcher: ReverseSearcher<'a> {
+        where P::Searcher: ReverseSearcher<'a>
+    {
         core_str::StrExt::rfind(&self[..], pat)
     }
 
@@ -1131,8 +1137,8 @@ pub trait StrExt: Index<RangeFull, Output = str> {
     /// assert_eq!(s.find_str("老虎 L"), Some(6));
     /// assert_eq!(s.find_str("muffin man"), None);
     /// ```
-    #[unstable(feature = "collections",
-               reason = "might get removed in favor of a more generic find in the future")]
+    #[unstable(feature = "collections")]
+    #[deprecated(since = "1.0.0", reason = "use `find()` with a `&str`")]
     fn find_str<'a, P: Pattern<'a>>(&'a self, needle: P) -> Option<usize> {
         core_str::StrExt::find_str(&self[..], needle)
     }
diff --git a/src/libcore/str/mod.rs b/src/libcore/str/mod.rs
index 820ad4d8586..7e51f8e8503 100644
--- a/src/libcore/str/mod.rs
+++ b/src/libcore/str/mod.rs
@@ -242,8 +242,10 @@ pub unsafe fn from_c_str(s: *const i8) -> &'static str {
 }
 
 /// Something that can be used to compare against a character
-#[unstable(feature = "core",
-           reason = "definition may change as pattern-related methods are stabilized")]
+#[unstable(feature = "core")]
+#[deprecated(since = "1.0.0",
+             reason = "use `Pattern` instead")]
+// NB: Rather than removing it, make it private and move it into self::pattern
 pub trait CharEq {
     /// Determine if the splitter should split at the given character
     fn matches(&mut self, char) -> bool;
@@ -252,6 +254,7 @@ pub trait CharEq {
     fn only_ascii(&self) -> bool;
 }
 
+#[allow(deprecated) /* for CharEq */ ]
 impl CharEq for char {
     #[inline]
     fn matches(&mut self, c: char) -> bool { *self == c }
@@ -260,6 +263,7 @@ impl CharEq for char {
     fn only_ascii(&self) -> bool { (*self as u32) < 128 }
 }
 
+#[allow(deprecated) /* for CharEq */ ]
 impl<F> CharEq for F where F: FnMut(char) -> bool {
     #[inline]
     fn matches(&mut self, c: char) -> bool { (*self)(c) }
@@ -268,13 +272,16 @@ impl<F> CharEq for F where F: FnMut(char) -> bool {
     fn only_ascii(&self) -> bool { false }
 }
 
+#[allow(deprecated) /* for CharEq */ ]
 impl<'a> CharEq for &'a [char] {
     #[inline]
+    #[allow(deprecated) /* for CharEq */ ]
     fn matches(&mut self, c: char) -> bool {
         self.iter().any(|&m| { let mut m = m; m.matches(c) })
     }
 
     #[inline]
+    #[allow(deprecated) /* for CharEq */ ]
     fn only_ascii(&self) -> bool {
         self.iter().all(|m| m.only_ascii())
     }
@@ -764,7 +771,7 @@ impl TwoWaySearcher {
     // that (u, v) is a critical factorization for the needle.
     #[inline]
     fn next(&mut self, haystack: &[u8], needle: &[u8], long_period: bool)
-    -> Option<(usize, usize)> {
+            -> Option<(usize, usize)> {
         'search: loop {
             // Check that we have room to search in
             if self.position + needle.len() > haystack.len() {
@@ -866,6 +873,8 @@ impl TwoWaySearcher {
 /// The internal state of an iterator that searches for matches of a substring
 /// within a larger string using a dynamically chosen search algorithm
 #[derive(Clone)]
+// NB: This is kept around for convenience because
+// it is planned to be used again in the future
 enum OldSearcher {
     TwoWay(TwoWaySearcher),
     TwoWayLong(TwoWaySearcher),
@@ -896,6 +905,8 @@ impl OldSearcher {
 }
 
 #[derive(Clone)]
+// NB: This is kept around for convenience because
+// it is planned to be used again in the future
 struct OldMatchIndices<'a, 'b> {
     // constants
     haystack: &'a str,
@@ -921,7 +932,8 @@ impl<'a, P: Pattern<'a>> Iterator for MatchIndices<'a, P> {
 
 /// An iterator over the substrings of a string separated by a given
 /// search string
-#[unstable(feature = "core", reason = "type may be removed")]
+#[unstable(feature = "core")]
+#[deprecated(since = "1.0.0", reason = "use `Split` with a `&str`")]
 pub struct SplitStr<'a, P: Pattern<'a>>(Split<'a, P>);
 impl<'a, P: Pattern<'a>> Iterator for SplitStr<'a, P> {
     type Item = &'a str;
@@ -1282,8 +1294,7 @@ where P::Searcher: DoubleEndedSearcher<'a> {
 }
 
 /// Return type of `StrExt::split_terminator`
-#[unstable(feature = "core",
-           reason = "might get removed in favour of a constructor method on Split")]
+#[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>}
 
@@ -1421,6 +1432,7 @@ impl StrExt for str {
     }
 
     #[inline]
+    #[allow(deprecated) /* for SplitStr */ ]
     fn split_str<'a, P: Pattern<'a>>(&'a self, pat: P) -> SplitStr<'a, P> {
         SplitStr(self.split(pat))
     }
@@ -1477,18 +1489,20 @@ impl StrExt for str {
 
     #[inline]
     fn starts_with<'a, P: Pattern<'a>>(&'a self, pat: P) -> bool {
-        pat.match_starts_at(self, 0)
+        pat.is_prefix_of(self)
     }
 
     #[inline]
     fn ends_with<'a, P: Pattern<'a>>(&'a self, pat: P) -> bool
-    where P::Searcher: ReverseSearcher<'a> {
-        pat.match_ends_at(self, self.len())
+        where P::Searcher: ReverseSearcher<'a>
+    {
+        pat.is_suffix_of(self)
     }
 
     #[inline]
     fn trim_matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> &'a str
-    where P::Searcher: DoubleEndedSearcher<'a> {
+        where P::Searcher: DoubleEndedSearcher<'a>
+    {
         let mut i = 0;
         let mut j = 0;
         let mut matcher = pat.into_searcher(self);
@@ -1521,7 +1535,8 @@ impl StrExt for str {
 
     #[inline]
     fn trim_right_matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> &'a str
-    where P::Searcher: ReverseSearcher<'a> {
+        where P::Searcher: ReverseSearcher<'a>
+    {
         let mut j = 0;
         let mut matcher = pat.into_searcher(self);
         if let Some((_, b)) = matcher.next_reject_back() {
@@ -1599,7 +1614,8 @@ impl StrExt for str {
     }
 
     fn rfind<'a, P: Pattern<'a>>(&'a self, pat: P) -> Option<usize>
-    where P::Searcher: ReverseSearcher<'a> {
+        where P::Searcher: ReverseSearcher<'a>
+    {
         pat.into_searcher(self).next_match_back().map(|(i, _)| i)
     }
 
diff --git a/src/libcore/str/pattern.rs b/src/libcore/str/pattern.rs
index 9cd5510db37..1f669c66eb1 100644
--- a/src/libcore/str/pattern.rs
+++ b/src/libcore/str/pattern.rs
@@ -8,66 +8,117 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-#![allow(missing_docs)]
+#![allow(deprecated) /* for CharEq */ ]
 
 use prelude::*;
 use super::CharEq;
 
 // Pattern
 
+/// A string pattern.
+///
+/// A `Pattern<'a>` expresses that the implementing type
+/// can be used as a string pattern for searching in a `&'a str`.
+///
+/// For example, both `'a'` and `"aa"` are patterns that
+/// would match at index `1` in the string `"baaaab"`.
+///
+/// The trait itself acts as a builder for an associated
+/// `Searcher` type, which does the actual work of finding
+/// occurences of the pattern in a string.
 pub trait Pattern<'a>: Sized {
+    /// Associated searcher for this pattern
     type Searcher: Searcher<'a>;
+
+    /// Construct the associated searcher from
+    /// `self` and the `haystack` to search in.
     fn into_searcher(self, haystack: &'a str) -> Self::Searcher;
 
+    /// Check whether the pattern matches anywhere in the haystack
     #[inline]
     fn is_contained_in(self, haystack: &'a str) -> bool {
         self.into_searcher(haystack).next_match().is_some()
     }
 
+    /// Check whether the pattern matches at the front of the haystack
     #[inline]
-    fn match_starts_at(self, haystack: &'a str, idx: usize) -> bool {
-        let mut matcher = self.into_searcher(haystack);
-        loop {
-            match matcher.next() {
-                SearchStep::Match(i, _) if i == idx => return true,
-                SearchStep::Match(i, _)
-                | SearchStep::Reject(i, _) if i >= idx => break,
-                SearchStep::Done => break,
-                _ => continue,
-            }
+    fn is_prefix_of(self, haystack: &'a str) -> bool {
+        match self.into_searcher(haystack).next() {
+            SearchStep::Match(0, _) => true,
+            _ => false,
         }
-        false
     }
 
+    /// Check whether the pattern matches at the back of the haystack
     #[inline]
-    fn match_ends_at(self, haystack: &'a str, idx: usize) -> bool
-    where Self::Searcher: ReverseSearcher<'a> {
-        let mut matcher = self.into_searcher(haystack);
-        loop {
-            match matcher.next_back() {
-                SearchStep::Match(_, j) if idx == j => return true,
-                SearchStep::Match(_, j)
-                | SearchStep::Reject(_, j) if idx >= j => break,
-                SearchStep::Done => break,
-                _ => continue,
-            }
+    fn is_suffix_of(self, haystack: &'a str) -> bool
+        where Self::Searcher: ReverseSearcher<'a>
+    {
+        match self.into_searcher(haystack).next_back() {
+            SearchStep::Match(_, j) if haystack.len() == j => true,
+            _ => false,
         }
-        false
     }
 }
 
 // Searcher
 
+/// Result of calling `Searcher::next()` or `ReverseSearcher::next_back()`.
 #[derive(Copy, Clone, Eq, PartialEq, Debug)]
 pub enum SearchStep {
+    /// Expresses that a match of the pattern has been found at
+    /// `haystack[a..b]`.
     Match(usize, usize),
+    /// Expresses that `haystack[a..b]` has been rejected as a possible match
+    /// of the pattern.
+    ///
+    /// Note that there might be more than one `Reject` betwen two `Match`es,
+    /// there is no requirement for them to be combined into one.
     Reject(usize, usize),
+    /// Expresses that every byte of the haystack has been visted, ending
+    /// the iteration.
     Done
 }
 
+/// A searcher for a string pattern.
+///
+/// This trait provides methods for searching for non-overlapping
+/// matches of a pattern starting from the front (left) of a string.
+///
+/// It will be implemented by associated `Searcher`
+/// types of the `Pattern` trait.
+///
+/// The trait is marked unsafe because the indices returned by the
+/// `next()` methods are required to lie on valid utf8 boundaries in
+/// the haystack. This enables consumers of this trait to
+/// slice the haystack without additional runtime checks.
 pub unsafe trait Searcher<'a> {
+    /// Getter for the underlaying string to be searched in
+    ///
+    /// Will always return the same `&str`
     fn haystack(&self) -> &'a str;
+
+    /// Performs the next search step starting from the front.
+    ///
+    /// - Returns `Match(a, b)` if `haystack[a..b]` matches the pattern.
+    /// - Returns `Reject(a, b)` if `haystack[a..b]` can not match the
+    ///   pattern, even partially.
+    /// - Returns `Done` if every byte of the haystack has been visited
+    ///
+    /// The stream of `Match` and `Reject` values up to a `Done`
+    /// will contain index ranges that are adjacent, non-overlapping,
+    /// covering the whole haystack, and laying on utf8 boundaries.
+    ///
+    /// A `Match` result needs to contain the whole matched pattern,
+    /// however `Reject` results may be split up into arbitrary
+    /// many adjacent fragments. Both ranges may have zero length.
+    ///
+    /// As an example, the pattern `"aaa"` and the haystack `"cbaaaaab"`
+    /// might produce the stream
+    /// `[Reject(0, 1), Reject(1, 2), Match(2, 5), Reject(5, 8)]`
     fn next(&mut self) -> SearchStep;
+
+    /// Find the next `Match` result. See `next()`
     #[inline]
     fn next_match(&mut self) -> Option<(usize, usize)> {
         loop {
@@ -78,8 +129,10 @@ pub unsafe trait Searcher<'a> {
             }
         }
     }
+
+    /// Find the next `Reject` result. See `next()`
     #[inline]
-    fn next_reject(&mut self) -> Option<(usize, usize)>{
+    fn next_reject(&mut self) -> Option<(usize, usize)> {
         loop {
             match self.next() {
                 SearchStep::Reject(a, b) => return Some((a, b)),
@@ -90,8 +143,42 @@ pub unsafe trait Searcher<'a> {
     }
 }
 
+/// A reverse searcher for a string pattern.
+///
+/// This trait provides methods for searching for non-overlapping
+/// matches of a pattern starting from the back (right) of a string.
+///
+/// It will be implemented by associated `Searcher`
+/// types of the `Pattern` trait if the pattern supports searching
+/// for it from the back.
+///
+/// The index ranges returned by this trait are not required
+/// to exactly match those of the forward search in reverse.
+///
+/// For the reason why this trait is marked unsafe, see them
+/// parent trait `Searcher`.
 pub unsafe trait ReverseSearcher<'a>: Searcher<'a> {
+    /// Performs the next search step starting from the back.
+    ///
+    /// - Returns `Match(a, b)` if `haystack[a..b]` matches the pattern.
+    /// - Returns `Reject(a, b)` if `haystack[a..b]` can not match the
+    ///   pattern, even partially.
+    /// - Returns `Done` if every byte of the haystack has been visited
+    ///
+    /// The stream of `Match` and `Reject` values up to a `Done`
+    /// will contain index ranges that are adjacent, non-overlapping,
+    /// covering the whole haystack, and laying on utf8 boundaries.
+    ///
+    /// A `Match` result needs to contain the whole matched pattern,
+    /// however `Reject` results may be split up into arbitrary
+    /// many adjacent fragments. Both ranges may have zero length.
+    ///
+    /// As an example, the pattern `"aaa"` and the haystack `"cbaaaaab"`
+    /// might produce the stream
+    /// `[Reject(7, 8), Match(4, 7), Reject(1, 4), Reject(0, 1)]`
     fn next_back(&mut self) -> SearchStep;
+
+    /// Find the next `Match` result. See `next_back()`
     #[inline]
     fn next_match_back(&mut self) -> Option<(usize, usize)>{
         loop {
@@ -102,6 +189,8 @@ pub unsafe trait ReverseSearcher<'a>: Searcher<'a> {
             }
         }
     }
+
+    /// Find the next `Reject` result. See `next_back()`
     #[inline]
     fn next_reject_back(&mut self) -> Option<(usize, usize)>{
         loop {
@@ -114,13 +203,34 @@ pub unsafe trait ReverseSearcher<'a>: Searcher<'a> {
     }
 }
 
+/// A marker trait to express that a `ReverseSearcher`
+/// can be used for a `DoubleEndedIterator` implementation.
+///
+/// For this, the impl of `Searcher` and `ReverseSearcher` need
+/// to follow these conditions:
+///
+/// - All results of `next()` need to be identical
+///   to the results of `next_back()` in reverse order.
+/// - `next()` and `next_back()` need to behave as
+///   the two ends of a range of values, that is they
+///   can not "walk past each other".
+///
+/// # Example
+///
+/// `char::Searcher` is a `DoubleEndedSearcher` because searching for a
+/// `char` only requires looking at one at a time, which behaves the same
+/// from both ends.
+///
+/// `(&str)::Searcher` is not a `DoubleEndedSearcher` because
+/// the pattern `"aa"` in the haystack `"aaa"` matches as either
+/// `"[aa]a"` or `"a[aa]"`, depending from which side it is searched.
 pub trait DoubleEndedSearcher<'a>: ReverseSearcher<'a> {}
 
 // Impl for a CharEq wrapper
 
 struct CharEqPattern<C: CharEq>(C);
 
-pub struct CharEqSearcher<'a, C: CharEq> {
+struct CharEqSearcher<'a, C: CharEq> {
     char_eq: C,
     haystack: &'a str,
     char_indices: super::CharIndices<'a>,
@@ -194,7 +304,7 @@ impl<'a, C: CharEq> DoubleEndedSearcher<'a> for CharEqSearcher<'a, C> {}
 // Todo: Optimize the naive implementation here
 
 #[derive(Clone)]
-pub struct StrSearcher<'a, 'b> {
+struct StrSearcher<'a, 'b> {
     haystack: &'a str,
     needle: &'b str,
     start: usize,
@@ -202,6 +312,10 @@ pub struct StrSearcher<'a, 'b> {
     done: bool,
 }
 
+/// Non-allocating substring search.
+///
+/// Will handle the pattern `""` as returning empty matches at each utf8
+/// boundary.
 impl<'a, 'b> Pattern<'a> for &'b str {
     type Searcher = StrSearcher<'a, 'b>;
 
@@ -236,9 +350,9 @@ unsafe impl<'a, 'b> Searcher<'a> for StrSearcher<'a, 'b>  {
         },
         |m: &mut StrSearcher| {
             // Forward step for nonempty needle
-            // Compare if bytes are equal
-            let possible_match = &m.haystack.as_bytes()[m.start .. m.start + m.needle.len()];
             let current_start = m.start;
+            // Compare byte window because this might break utf8 boundaries
+            let possible_match = &m.haystack.as_bytes()[m.start .. m.start + m.needle.len()];
             if possible_match == m.needle.as_bytes() {
                 m.start += m.needle.len();
                 SearchStep::Match(current_start, m.start)
@@ -266,9 +380,9 @@ unsafe impl<'a, 'b> ReverseSearcher<'a> for StrSearcher<'a, 'b>  {
         },
         |m: &mut StrSearcher| {
             // Backward step for nonempty needle
-            // Compare if bytes are equal
-            let possible_match = &m.haystack.as_bytes()[m.end - m.needle.len() .. m.end];
             let current_end = m.end;
+            // Compare byte window because this might break utf8 boundaries
+            let possible_match = &m.haystack.as_bytes()[m.end - m.needle.len() .. m.end];
             if possible_match == m.needle.as_bytes() {
                 m.end -= m.needle.len();
                 SearchStep::Match(m.end, current_end)
@@ -282,9 +396,13 @@ unsafe impl<'a, 'b> ReverseSearcher<'a> for StrSearcher<'a, 'b>  {
     }
 }
 
-fn str_search_step<F, G>(mut m: &mut StrSearcher, f: F, g: G) -> SearchStep
-where F: FnOnce(&mut StrSearcher) -> SearchStep,
-      G: FnOnce(&mut StrSearcher) -> SearchStep
+// Helper function for encapsulating the common control flow
+// of doing a search step from the front or doing a search step from the back
+fn str_search_step<F, G>(mut m: &mut StrSearcher,
+                         empty_needle_step: F,
+                         nonempty_needle_step: G) -> SearchStep
+    where F: FnOnce(&mut StrSearcher) -> SearchStep,
+          G: FnOnce(&mut StrSearcher) -> SearchStep
 {
     if m.done {
         SearchStep::Done
@@ -293,11 +411,12 @@ where F: FnOnce(&mut StrSearcher) -> SearchStep,
         if m.start == m.end {
             m.done = true;
         }
-        f(&mut m)
+        empty_needle_step(&mut m)
     } else if m.start + m.needle.len() <= m.end {
         // Case for needle != ""
-        g(&mut m)
+        nonempty_needle_step(&mut m)
     } else if m.start < m.end {
+        // Remaining slice shorter than needle, reject it
         m.done = true;
         SearchStep::Reject(m.start, m.end)
     } else {
@@ -323,35 +442,39 @@ macro_rules! associated_items {
         }
 
         #[inline]
-        fn match_starts_at(self, haystack: &'a str, idx: usize) -> bool {
+        fn is_prefix_of(self, haystack: &'a str) -> bool {
             let $s = self;
-            $e.match_starts_at(haystack, idx)
+            $e.is_prefix_of(haystack)
         }
 
         // FIXME: #21750
         /*#[inline]
-        fn match_ends_at(self, haystack: &'a str, idx: usize) -> bool
-        where $t: ReverseSearcher<'a> {
+        fn is_suffix_of(self, haystack: &'a str) -> bool
+            where $t: ReverseSearcher<'a>
+        {
             let $s = self;
-            $e.match_ends_at(haystack, idx)
+            $e.is_suffix_of(haystack)
         }*/
     }
 }
 
 // CharEq delegation impls
 
-impl<'a, 'b> Pattern<'a> for &'b [char] {
+/// Searches for chars that are equal to a given char
+impl<'a> Pattern<'a> for char {
     type Searcher =   <CharEqPattern<Self> as Pattern<'a>>::Searcher;
     associated_items!(<CharEqPattern<Self> as Pattern<'a>>::Searcher,
                       s, CharEqPattern(s));
 }
 
-impl<'a> Pattern<'a> for char {
+/// Searches for chars that are equal to any of the chars in the array
+impl<'a, 'b> Pattern<'a> for &'b [char] {
     type Searcher =   <CharEqPattern<Self> as Pattern<'a>>::Searcher;
     associated_items!(<CharEqPattern<Self> as Pattern<'a>>::Searcher,
                       s, CharEqPattern(s));
 }
 
+/// Searches for chars that match the given predicate
 impl<'a, F> Pattern<'a> for F where F: FnMut(char) -> bool {
     type Searcher =   <CharEqPattern<Self> as Pattern<'a>>::Searcher;
     associated_items!(<CharEqPattern<Self> as Pattern<'a>>::Searcher,
@@ -362,8 +485,10 @@ impl<'a, F> Pattern<'a> for F where F: FnMut(char) -> bool {
 
 use ops::Deref;
 
+/// Delegates to the next deref coercion of `Self` that implements `Pattern`
 impl<'a, 'b, P: 'b + ?Sized, T: Deref<Target = P> + ?Sized> Pattern<'a> for &'b T
-where &'b P: Pattern<'a> {
+    where &'b P: Pattern<'a>
+{
     type Searcher =   <&'b P as Pattern<'a>>::Searcher;
     associated_items!(<&'b P as Pattern<'a>>::Searcher,
                       s, (&**s));
diff --git a/src/libgraphviz/lib.rs b/src/libgraphviz/lib.rs
index acd52c752e8..09fbf4935e4 100644
--- a/src/libgraphviz/lib.rs
+++ b/src/libgraphviz/lib.rs
@@ -463,7 +463,7 @@ impl<'a> LabelText<'a> {
     fn pre_escaped_content(self) -> Cow<'a, str> {
         match self {
             EscStr(s) => s,
-            LabelStr(s) => if s.contains_char('\\') {
+            LabelStr(s) => if s.contains('\\') {
                 (&*s).escape_default().into_cow()
             } else {
                 s
diff --git a/src/librustc/lint/builtin.rs b/src/librustc/lint/builtin.rs
index dc81e89902b..74ae9692abd 100644
--- a/src/librustc/lint/builtin.rs
+++ b/src/librustc/lint/builtin.rs
@@ -784,7 +784,7 @@ impl NonCamelCaseTypes {
 
             // start with a non-lowercase letter rather than non-uppercase
             // ones (some scripts don't have a concept of upper/lowercase)
-            ident.len() > 0 && !ident.char_at(0).is_lowercase() && !ident.contains_char('_')
+            ident.len() > 0 && !ident.char_at(0).is_lowercase() && !ident.contains('_')
         }
 
         fn to_camel_case(s: &str) -> String {
diff --git a/src/librustc/metadata/filesearch.rs b/src/librustc/metadata/filesearch.rs
index 3caa0f5b4db..d63b3dd60d0 100644
--- a/src/librustc/metadata/filesearch.rs
+++ b/src/librustc/metadata/filesearch.rs
@@ -219,7 +219,7 @@ pub fn rust_path() -> Vec<Path> {
     let mut env_rust_path: Vec<Path> = match get_rust_path() {
         Some(env_path) => {
             let env_path_components =
-                env_path.split_str(PATH_ENTRY_SEPARATOR);
+                env_path.split(PATH_ENTRY_SEPARATOR);
             env_path_components.map(|s| Path::new(s)).collect()
         }
         None => Vec::new()
diff --git a/src/librustc/middle/infer/region_inference/graphviz.rs b/src/librustc/middle/infer/region_inference/graphviz.rs
index 67875ae2252..43cd1fc8edb 100644
--- a/src/librustc/middle/infer/region_inference/graphviz.rs
+++ b/src/librustc/middle/infer/region_inference/graphviz.rs
@@ -90,7 +90,7 @@ pub fn maybe_print_constraints_for<'a, 'tcx>(region_vars: &RegionVarBindings<'a,
             tcx.sess.bug("empty string provided as RUST_REGION_GRAPH");
         }
 
-        if output_template.contains_char('%') {
+        if output_template.contains('%') {
             let mut new_str = String::new();
             for c in output_template.chars() {
                 if c == '%' {
diff --git a/src/librustc/session/mod.rs b/src/librustc/session/mod.rs
index c1c55188875..4a3efc861d1 100644
--- a/src/librustc/session/mod.rs
+++ b/src/librustc/session/mod.rs
@@ -280,9 +280,9 @@ fn split_msg_into_multilines(msg: &str) -> Option<String> {
     }
 
     let mut tail = &msg[head..];
-    let third = tail.find_str("(values differ")
-                   .or(tail.find_str("(lifetime"))
-                   .or(tail.find_str("(cyclic type of infinite size"));
+    let third = tail.find("(values differ")
+                   .or(tail.find("(lifetime"))
+                   .or(tail.find("(cyclic type of infinite size"));
     // Insert `\n` before any remaining messages which match.
     if let Some(pos) = third {
         // The end of the message may just be wrapped in `()` without
diff --git a/src/librustc_driver/pretty.rs b/src/librustc_driver/pretty.rs
index 0fbfa5fd89d..e349e8d7bb5 100644
--- a/src/librustc_driver/pretty.rs
+++ b/src/librustc_driver/pretty.rs
@@ -348,7 +348,7 @@ impl FromStr for UserIdentifiedItem {
     type Err = ();
     fn from_str(s: &str) -> Result<UserIdentifiedItem, ()> {
         Ok(s.parse().map(ItemViaNode).unwrap_or_else(|_| {
-            ItemViaPath(s.split_str("::").map(|s| s.to_string()).collect())
+            ItemViaPath(s.split("::").map(|s| s.to_string()).collect())
         }))
     }
 }
diff --git a/src/librustdoc/html/render.rs b/src/librustdoc/html/render.rs
index fc3c8738991..735487611dc 100644
--- a/src/librustdoc/html/render.rs
+++ b/src/librustdoc/html/render.rs
@@ -1469,7 +1469,7 @@ fn full_path(cx: &Context, item: &clean::Item) -> String {
 
 fn shorter<'a>(s: Option<&'a str>) -> &'a str {
     match s {
-        Some(s) => match s.find_str("\n\n") {
+        Some(s) => match s.find("\n\n") {
             Some(pos) => &s[..pos],
             None => s,
         },
diff --git a/src/libstd/old_path/windows.rs b/src/libstd/old_path/windows.rs
index 887dc804c7a..80c19816bd5 100644
--- a/src/libstd/old_path/windows.rs
+++ b/src/libstd/old_path/windows.rs
@@ -522,7 +522,7 @@ impl GenericPath for Path {
 
     fn path_relative_from(&self, base: &Path) -> Option<Path> {
         fn comp_requires_verbatim(s: &str) -> bool {
-            s == "." || s == ".." || s.contains_char(SEP2)
+            s == "." || s == ".." || s.contains(SEP2)
         }
 
         if !self.equiv_prefix(base) {
diff --git a/src/libsyntax/parse/lexer/comments.rs b/src/libsyntax/parse/lexer/comments.rs
index 1f06db60027..7a5d75581a5 100644
--- a/src/libsyntax/parse/lexer/comments.rs
+++ b/src/libsyntax/parse/lexer/comments.rs
@@ -92,7 +92,7 @@ pub fn strip_doc_comment_decoration(comment: &str) -> String {
         let mut first = true;
         for line in &lines {
             for (j, c) in line.chars().enumerate() {
-                if j > i || !"* \t".contains_char(c) {
+                if j > i || !"* \t".contains(c) {
                     can_trim = false;
                     break;
                 }
@@ -264,7 +264,7 @@ fn read_block_comment(rdr: &mut StringReader,
         if is_block_doc_comment(&curr_line[..]) {
             return
         }
-        assert!(!curr_line.contains_char('\n'));
+        assert!(!curr_line.contains('\n'));
         lines.push(curr_line);
     } else {
         let mut level: isize = 1;
diff --git a/src/libsyntax/parse/parser.rs b/src/libsyntax/parse/parser.rs
index 370201e5382..eb5688b3ed8 100644
--- a/src/libsyntax/parse/parser.rs
+++ b/src/libsyntax/parse/parser.rs
@@ -2496,7 +2496,7 @@ impl<'a> Parser<'a> {
                     let fstr = n.as_str();
                     self.span_err(last_span,
                                   &format!("unexpected token: `{}`", n.as_str()));
-                    if fstr.chars().all(|x| "0123456789.".contains_char(x)) {
+                    if fstr.chars().all(|x| "0123456789.".contains(x)) {
                         let float = match fstr.parse::<f64>().ok() {
                             Some(f) => f,
                             None => continue,
diff --git a/src/libunicode/u_str.rs b/src/libunicode/u_str.rs
index 9bd8c5525a0..38cbe5c7dea 100644
--- a/src/libunicode/u_str.rs
+++ b/src/libunicode/u_str.rs
@@ -84,7 +84,7 @@ impl UnicodeStr for str {
 
     #[inline]
     fn trim(&self) -> &str {
-        self.trim_left().trim_right()
+        self.trim_matches(|c: char| c.is_whitespace())
     }
 
     #[inline]