What’s the algorithm used in diagnostics for suggesting similarly named stuff?

[steffahn]

I just ran into this error message because I was typing too quickly.

error: cannot find macro `prinltn` in this scope
 --> src/main.rs:4:5
  |
4 |     prinltn!("s1 = {}, s2 = {}", s1, s2);
  |     ^^^^^^^ help: a macro with a similar name exists: `print`
 --> /rustc/fc594f15669680fa70d255faec3ca3fb507c3405/library/std/src/macros.rs:78:1
  |
  = note: similarly named macro `print` defined here

error: could not compile `playground` due to previous error

Does anyone know what the algorithm used was that determined that “print” is more similar to “prinltn” than “println” is? Presumably some kind of edit-distance? Are there alternative/better algorithms that would handle a letter swap like this better?

[jhpratt]

I'm pretty sure it's a Levenshtein distance. Using a Damerau-Levenshtein distance would solve this problem, and shouldn't be too hard to work in. I'll check when I'm on my laptop — I recall seeing a single method that does the suggestions.

[steffahn]

@jhpratt

I'm pretty sure it's a Levenshtein distance.

With that name, it’s fairly straightforward to find. rustc_span::lev_distance - Rust

[jhpratt]

Sometimes I remember things

[jhpratt]

Update: I finally got around to playing around with this. I have a naïve implementation (using the full matrix), and just need to optimize it. Amazingly, it only changes one ui test. Needless to say I'll be adding the example from this post as a test.

Edit: PR is up