Add levenshtein distance based suggestions everywhere

Opened by Manish Goregaokar at 2020-04-22 21:03:46

Currently, we suggest typo fixes in case of function calls, locals, and field accesses. So, both the marked lines below will suggest the correct fix:

struct A {foo: u8}
fn main() {
    let x = A {foo: 1};
    x.fob; // here
    let aaaaaaa=1;
    let z = aaaaaab; // here
}

However, this is not the case for imports, crates, and inline paths. We should fix this.

This is probably not an easy bug, but should be fun. Basically you need to look for the source of the "could not find X" error, and do something similar to https://github.com/rust-lang/rust/blob/99925fb562086ff789df95220104f9d8d5fc8b3c/src/librustc_resolve/lib.rs#L3625

@apasel422 @Wafflespeanut want to work on this?

@Manishearth Thanks, I'll try :)
Ravi Shankar at 2015-12-08 17:33:37
Go ahead!
Manish Goregaokar at 2015-12-08 18:43:18
I was surprised that I didn't get a suggestion here
```
fn main() {
    "".is_emtpy();
}
```
mitaa at 2016-02-27 07:49:06
What could one possibly suggest there? :)
Ravi Shankar at 2016-02-27 07:52:35
is_empty? (p and t are flipped)
mitaa at 2016-02-27 07:56:03
Hmm, looks like we currently show suggestions only for the stuff that exist in the source file.
Ravi Shankar at 2016-02-27 08:01:34
No, we just don't handle methods.
Manish Goregaokar at 2016-02-27 08:02:50
Did crate and inline path support ever get added for this? If not, I'd be interested in giving it a shot.
Taylor Cramer at 2016-05-25 17:47:34
I don't think so. Go ahead!
Manish Goregaokar at 2016-05-25 18:03:52
@Manishearth can I pick this up if nobody else is working on it?
Nikhil Shagrithaya at 2016-07-10 13:59:01
Sure!
Manish Goregaokar at 2016-07-10 14:14:38

We do not make suggestions for fields behind a reference:

struct Ty { field: () }

fn test1(t: Ty) { t.fied }
fn test2(t: &mut Ty) { t.fied }

error: attempted access of field `fied` on type `Ty`, but no field with that name was found
 --> <anon>:3:19
  |
3 | fn test1(t: Ty) { t.fied }
  |                   ^^^^^^
  |
help: did you mean `field`?
 --> <anon>:3:21
  |
3 | fn test1(t: Ty) { t.fied }
  |                     ^^^^

error: attempted access of field `fied` on type `&mut Ty`, but no field with that name was found
 --> <anon>:4:24
  |
4 | fn test2(t: &mut Ty) { t.fied }
  |                        ^^^^^^

Simonas Kazlauskas at 2016-12-02 16:57:40

From Issue #38166. Some ideas from: https://gcc.gnu.org/gcc-7/changes.html

const MAX_ITEM: usize = 10;
fn foo_bar() {}
fn foo(c: esize) {} // Misspelled type name.
enum Bar { First, Second }
fn main() {
    let v = [0u32; MAXITEM]; // Misspelled constant name.
    foobar(); // Misspelled function name.
    let b: Bar = Bar::second; // Misspelled enum variant.
}

In all four cases I'd like the Rust compiler to suggest the closest names (usize/isize, MAX_ITEM, foo_bar, Bar::Second).

leonardo-m at 2016-12-05 12:24:36

https://github.com/rust-lang/rust/pull/38154 uses Levenshtein-based suggestions in all path contexts, but there are two more serious problems:
- ~~candidate set for names in lexical scope (name) is very poor, it includes only local variables and type parameters ("bindings in ribs"), it needs to include items as well.~~ (fixed in https://github.com/rust-lang/rust/pull/38927)
- ~~candidate set for names in some module's scope (a::b::name) is not built at all, so these names don't get suggestions.~~ (fixed in https://github.com/rust-lang/rust/pull/38927)
Vadim Petrochenkov at 2016-12-05 12:49:25
Suggestions for last segments of non-import paths are implemented in https://github.com/rust-lang/rust/pull/38927

Remaining items:
- [x] Segments in path prefixes.
- [x] Segments in import paths.
- [ ] Extern crates (what is the source of suggestions, command line?). - not that useful these days so can be skipped
- [ ] Lifetime names.
- [x] Label names (#45173).
- [ ] Macro names in #[macro_use].
- [x] Macro names in #[derive] (#39752).
  - [x] Include use imports.
- [x] Improvements to fields? (https://github.com/rust-lang/rust/issues/30197#issuecomment-264503964)
- [x] Method calls (https://github.com/rust-lang/rust/pull/44297).
Vadim Petrochenkov at 2017-01-14 11:30:19
@Manishearth, is anybody working on this currently?
Connor Gray at 2017-04-27 17:31:00
Feel free to take it!
Manish Goregaokar at 2017-04-27 17:41:16
Great! This is the first issue I've worked on in the compiler–do you have any idea about a good place to start? I'm happy to dive in on my own, but any advice would be appreciated.
Connor Gray at 2017-04-28 00:45:32
@Wafflespeanut, want to help?

I'm a bit busy for the next few days.
Manish Goregaokar at 2017-04-28 15:44:02
@ConnorGray Now that this has turned into a tracking bug, a good idea would be to pick something more specific and start playing with the code. I usually start with a git grep for the error message, and backtrack from there. For example, invalid method calls (like "".foo()) always show something like,
```
no method named `foo` for type ...
```
... and the error appears to emit from here, whose caller appears to be this. The name suggests that it's doing a lookup, which returns a MethodError::NoMatch with some near misses. Perhaps, we could get an alternative from the NoMatchData, or if it doesn't exist, we could tweak the function (and probably the struct too?) to get alternative names. Would that be good to get you started? :)
Ravi Shankar at 2017-04-29 06:03:35
@Wafflespeanut thanks for the nice workflow example. Excuse my ignorance, but what's the significance of tracking vs non-tracking bug?

I've been working my way down through the code. These are sort of notes for myself, but also can give you an idea of the direction I'm going, in case I'm looking at this wrong. The source for all the method suggestions is a carried early return in lookup_method to probe_for_name. probe_for_name looks to be just a helper method which ultimately calls out to InferContext::probe. The probe method takes a closure and seems to facilitate the rolling-back of state-changing operations made as part of the name lookup process. That closure creates an instance of ProbeContext, which seems to do most of the heavy lifting.

@Manishearth, @Wafflespeanut within ProbeContext's methods, there are these "steps" that are referred to (CandidateStep's), and seem to have something to do with type resolution, but I'm having a bit of trouble understanding what they actually are in aggregate. Do you know anything about the overall design, what they represent?
Connor Gray at 2017-04-30 20:21:40
A tracking bug contains multiple bugs, all of which may not be doable in one go (because even though they're related, they could be at different places, or might need more work, etc.). Also, I'm sorry, I won't be able to fill you about the overall design (because frankly, I don't know). I just go by inserting debug statements, build stage1 rustc and figure things by backtracking (like I said earlier) and it goes in a loop.
Ravi Shankar at 2017-05-02 15:57:14
Okay, thanks for the clarification. And thanks anyway. I'm still wading through it, and I think I've made some progress understanding nonetheless.
Connor Gray at 2017-05-02 17:23:54
Hi! Is anyone working on adding suggestions for method names (re @mitaa's is_emtpy() example)? I have a patch that I wrote some time ago that implements this, but if someone else is working on it I don't want to get in the way.
Thomas Bracht Laumann Jespersen at 2017-08-19 15:47:22
If @petrochenkov's list is being kept up-to-date, I think the "method calls" point can be crossed off.
Thomas Bracht Laumann Jespersen at 2017-09-26 07:01:16
@laumann Updated the list. Thanks for working on this.
Vadim Petrochenkov at 2017-09-26 09:35:39
@petrochenkov Happy to help :-)

I considered looking into suggestions for "Lifetime and label names" next - that sounds like it should be more or less straight-forward...
Thomas Bracht Laumann Jespersen at 2017-09-26 09:42:08
@laumann It should be straightforward, but note that with https://github.com/rust-lang/rust/issues/44524 typos in lifetimes will be impossible by definition (every typo becomes a new lifetime, modulo some corner cases).
Vadim Petrochenkov at 2017-10-03 09:39:04
Triage: do we plan on doing more of this? I'm not sure.
Steve Klabnik at 2018-12-25 20:02:59