Auto merge of #44297 - laumann:suggest-misspelt-methods, r=arielb1

Add suggestions for misspelled method names

Use the syntax::util::lev_distance module to provide suggestions when a
named method cannot be found.

Part of #30197

6 files changed, 158 insertions, 10 deletions

diff --git a/src/librustc_typeck/check/method/mod.rs b/src/librustc_typeck/check/method/mod.rs
index 0afc482cb79..4ee0b4cb46f 100644
--- a/src/librustc_typeck/check/method/mod.rs
+++ b/src/librustc_typeck/check/method/mod.rs
@@ -70,6 +70,7 @@ pub struct NoMatchData<'tcx> {
     pub static_candidates: Vec<CandidateSource>,
     pub unsatisfied_predicates: Vec<TraitRef<'tcx>>,
     pub out_of_scope_traits: Vec<DefId>,
+    pub lev_candidate: Option<ty::AssociatedItem>,
     pub mode: probe::Mode,
 }
 
@@ -77,12 +78,14 @@ impl<'tcx> NoMatchData<'tcx> {
     pub fn new(static_candidates: Vec<CandidateSource>,
                unsatisfied_predicates: Vec<TraitRef<'tcx>>,
                out_of_scope_traits: Vec<DefId>,
+               lev_candidate: Option<ty::AssociatedItem>,
                mode: probe::Mode)
                -> Self {
         NoMatchData {
             static_candidates,
             unsatisfied_predicates,
             out_of_scope_traits,
+            lev_candidate,
             mode,
         }
     }
diff --git a/src/librustc_typeck/check/method/probe.rs b/src/librustc_typeck/check/method/probe.rs
index 7b947818325..a3b196f99d6 100644
--- a/src/librustc_typeck/check/method/probe.rs
+++ b/src/librustc_typeck/check/method/probe.rs
@@ -23,11 +23,13 @@ use rustc::infer::type_variable::TypeVariableOrigin;
 use rustc::util::nodemap::FxHashSet;
 use rustc::infer::{self, InferOk};
 use syntax::ast;
+use syntax::util::lev_distance::{lev_distance, find_best_match_for_name};
 use syntax_pos::Span;
 use rustc::hir;
 use std::mem;
 use std::ops::Deref;
 use std::rc::Rc;
+use std::cmp::max;
 
 use self::CandidateKind::*;
 pub use self::PickKind::*;
@@ -51,6 +53,10 @@ struct ProbeContext<'a, 'gcx: 'a + 'tcx, 'tcx: 'a> {
     /// used for error reporting
     static_candidates: Vec<CandidateSource>,
 
+    /// When probing for names, include names that are close to the
+    /// requested name (by Levensthein distance)
+    allow_similar_names: bool,
+
     /// Some(candidate) if there is a private candidate
     private_candidate: Option<Def>,
 
@@ -242,6 +248,7 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
                     return Err(MethodError::NoMatch(NoMatchData::new(Vec::new(),
                                                                      Vec::new(),
                                                                      Vec::new(),
+                                                                     None,
                                                                      mode)))
                 }
             }
@@ -261,7 +268,7 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
         // that we create during the probe process are removed later
         self.probe(|_| {
             let mut probe_cx =
-                ProbeContext::new(self, span, mode, method_name, return_type, steps);
+                ProbeContext::new(self, span, mode, method_name, return_type, Rc::new(steps));
 
             probe_cx.assemble_inherent_candidates();
             match scope {
@@ -333,7 +340,7 @@ impl<'a, 'gcx, 'tcx> ProbeContext<'a, 'gcx, 'tcx> {
            mode: Mode,
            method_name: Option<ast::Name>,
            return_type: Option<Ty<'tcx>>,
-           steps: Vec<CandidateStep<'tcx>>)
+           steps: Rc<Vec<CandidateStep<'tcx>>>)
            -> ProbeContext<'a, 'gcx, 'tcx> {
         ProbeContext {
             fcx,
@@ -344,8 +351,9 @@ impl<'a, 'gcx, 'tcx> ProbeContext<'a, 'gcx, 'tcx> {
             inherent_candidates: Vec::new(),
             extension_candidates: Vec::new(),
             impl_dups: FxHashSet(),
-            steps: Rc::new(steps),
+            steps: steps,
             static_candidates: Vec::new(),
+            allow_similar_names: false,
             private_candidate: None,
             unsatisfied_predicates: Vec::new(),
         }
@@ -798,10 +806,12 @@ impl<'a, 'gcx, 'tcx> ProbeContext<'a, 'gcx, 'tcx> {
         if let Some(def) = private_candidate {
             return Err(MethodError::PrivateMatch(def, out_of_scope_traits));
         }
+        let lev_candidate = self.probe_for_lev_candidate()?;
 
         Err(MethodError::NoMatch(NoMatchData::new(static_candidates,
                                                   unsatisfied_predicates,
                                                   out_of_scope_traits,
+                                                  lev_candidate,
                                                   self.mode)))
     }
 
@@ -913,11 +923,8 @@ impl<'a, 'gcx, 'tcx> ProbeContext<'a, 'gcx, 'tcx> {
         debug!("applicable_candidates: {:?}", applicable_candidates);
 
         if applicable_candidates.len() > 1 {
-            match self.collapse_candidates_to_trait_pick(&applicable_candidates[..]) {
-                Some(pick) => {
-                    return Some(Ok(pick));
-                }
-                None => {}
+            if let Some(pick) = self.collapse_candidates_to_trait_pick(&applicable_candidates[..]) {
+                return Some(Ok(pick));
             }
         }
 
@@ -1126,6 +1133,54 @@ impl<'a, 'gcx, 'tcx> ProbeContext<'a, 'gcx, 'tcx> {
         })
     }
 
+    /// Similarly to `probe_for_return_type`, this method attempts to find the best matching
+    /// candidate method where the method name may have been misspelt. Similarly to other
+    /// Levenshtein based suggestions, we provide at most one such suggestion.
+    fn probe_for_lev_candidate(&mut self) -> Result<Option<ty::AssociatedItem>, MethodError<'tcx>> {
+        debug!("Probing for method names similar to {:?}",
+               self.method_name);
+
+        let steps = self.steps.clone();
+        self.probe(|_| {
+            let mut pcx = ProbeContext::new(self.fcx, self.span, self.mode, self.method_name,
+                                            self.return_type, steps);
+            pcx.allow_similar_names = true;
+            pcx.assemble_inherent_candidates();
+            pcx.assemble_extension_candidates_for_traits_in_scope(ast::DUMMY_NODE_ID)?;
+
+            let method_names = pcx.candidate_method_names();
+            pcx.allow_similar_names = false;
+            let applicable_close_candidates: Vec<ty::AssociatedItem> = method_names
+                .iter()
+                .filter_map(|&method_name| {
+                    pcx.reset();
+                    pcx.method_name = Some(method_name);
+                    pcx.assemble_inherent_candidates();
+                    pcx.assemble_extension_candidates_for_traits_in_scope(ast::DUMMY_NODE_ID)
+                        .ok().map_or(None, |_| {
+                            pcx.pick_core()
+                                .and_then(|pick| pick.ok())
+                                .and_then(|pick| Some(pick.item))
+                        })
+                })
+               .collect();
+
+            if applicable_close_candidates.is_empty() {
+                Ok(None)
+            } else {
+                let best_name = {
+                    let names = applicable_close_candidates.iter().map(|cand| &cand.name);
+                    find_best_match_for_name(names,
+                                             &self.method_name.unwrap().as_str(),
+                                             None)
+                }.unwrap();
+                Ok(applicable_close_candidates
+                   .into_iter()
+                   .find(|method| method.name == best_name))
+            }
+        })
+    }
+
     ///////////////////////////////////////////////////////////////////////////
     // MISCELLANY
     fn has_applicable_self(&self, item: &ty::AssociatedItem) -> bool {
@@ -1253,10 +1308,21 @@ impl<'a, 'gcx, 'tcx> ProbeContext<'a, 'gcx, 'tcx> {
         self.tcx.erase_late_bound_regions(value)
     }
 
-    /// Find the method with the appropriate name (or return type, as the case may be).
+    /// Find the method with the appropriate name (or return type, as the case may be). If
+    /// `allow_similar_names` is set, find methods with close-matching names.
     fn impl_or_trait_item(&self, def_id: DefId) -> Vec<ty::AssociatedItem> {
         if let Some(name) = self.method_name {
-            self.fcx.associated_item(def_id, name).map_or(Vec::new(), |x| vec![x])
+            if self.allow_similar_names {
+                let max_dist = max(name.as_str().len(), 3) / 3;
+                self.tcx.associated_items(def_id)
+                    .filter(|x| {
+                        let dist = lev_distance(&*name.as_str(), &x.name.as_str());
+                        dist > 0 && dist <= max_dist
+                    })
+                    .collect()
+            } else {
+                self.fcx.associated_item(def_id, name).map_or(Vec::new(), |x| vec![x])
+            }
         } else {
             self.tcx.associated_items(def_id).collect()
         }
diff --git a/src/librustc_typeck/check/method/suggest.rs b/src/librustc_typeck/check/method/suggest.rs
index 7fa3dd7472d..90c5297b399 100644
--- a/src/librustc_typeck/check/method/suggest.rs
+++ b/src/librustc_typeck/check/method/suggest.rs
@@ -164,6 +164,7 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
             MethodError::NoMatch(NoMatchData { static_candidates: static_sources,
                                                unsatisfied_predicates,
                                                out_of_scope_traits,
+                                               lev_candidate,
                                                mode,
                                                .. }) => {
                 let tcx = self.tcx;
@@ -282,6 +283,10 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
                                               item_name,
                                               rcvr_expr,
                                               out_of_scope_traits);
+
+                if let Some(lev_candidate) = lev_candidate {
+                    err.help(&format!("did you mean `{}`?", lev_candidate.name));
+                }
                 err.emit();
             }
 
diff --git a/src/test/ui/block-result/issue-3563.stderr b/src/test/ui/block-result/issue-3563.stderr
index 4b1f8b032b7..e3f0df6fb5f 100644
--- a/src/test/ui/block-result/issue-3563.stderr
+++ b/src/test/ui/block-result/issue-3563.stderr
@@ -3,6 +3,8 @@ error[E0599]: no method named `b` found for type `&Self` in the current scope
    |
 13 |         || self.b()
    |                 ^
+   |
+   = help: did you mean `a`?
 
 error[E0308]: mismatched types
   --> $DIR/issue-3563.rs:13:9
diff --git a/src/test/ui/suggestions/suggest-methods.rs b/src/test/ui/suggestions/suggest-methods.rs
new file mode 100644
index 00000000000..b02881dc7ee
--- /dev/null
+++ b/src/test/ui/suggestions/suggest-methods.rs
@@ -0,0 +1,40 @@
+// Copyright 2017 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+struct Foo;
+
+impl Foo {
+    fn bar(self) {}
+    fn baz(&self, x: f64) {}
+}
+
+trait FooT {
+    fn bag(&self);
+}
+
+impl FooT for Foo {
+    fn bag(&self) {}
+}
+
+fn main() {
+    let f = Foo;
+    f.bat(1.0);
+
+    let s = "foo".to_string();
+    let _ = s.is_emtpy();
+
+    // Generates a warning for `count_zeros()`. `count_ones()` is also a close
+    // match, but the former is closer.
+    let _ = 63u32.count_eos();
+
+    // Does not generate a warning
+    let _ = 63u32.count_o();
+
+}
diff --git a/src/test/ui/suggestions/suggest-methods.stderr b/src/test/ui/suggestions/suggest-methods.stderr
new file mode 100644
index 00000000000..41beb73b1bc
--- /dev/null
+++ b/src/test/ui/suggestions/suggest-methods.stderr
@@ -0,0 +1,32 @@
+error[E0599]: no method named `bat` found for type `Foo` in the current scope
+  --> $DIR/suggest-methods.rs:28:7
+   |
+28 |     f.bat(1.0);
+   |       ^^^
+   |
+   = help: did you mean `bar`?
+
+error[E0599]: no method named `is_emtpy` found for type `std::string::String` in the current scope
+  --> $DIR/suggest-methods.rs:31:15
+   |
+31 |     let _ = s.is_emtpy();
+   |               ^^^^^^^^
+   |
+   = help: did you mean `is_empty`?
+
+error[E0599]: no method named `count_eos` found for type `u32` in the current scope
+  --> $DIR/suggest-methods.rs:35:19
+   |
+35 |     let _ = 63u32.count_eos();
+   |                   ^^^^^^^^^
+   |
+   = help: did you mean `count_zeros`?
+
+error[E0599]: no method named `count_o` found for type `u32` in the current scope
+  --> $DIR/suggest-methods.rs:38:19
+   |
+38 |     let _ = 63u32.count_o();
+   |                   ^^^^^^^
+
+error: aborting due to 4 previous errors
+