auto merge of #5096 : luqmana/rust/spell, r=catamorphism

Address #2281


```
-> % cat foo.rs
fn foo() -> int {
    let bar = 10;

    bad
}
```

```
-> % rustc foo.rs
foo.rs:4:4: 4:7 error: unresolved name: `bad`. Did you mean: `bar`?
foo.rs:4     bad
             ^~~
error: aborting due to previous error
```

10 files changed, 92 insertions, 11 deletions

diff --git a/src/libcore/str.rs b/src/libcore/str.rs
index 3c15a89081d..92e980e34d0 100644
--- a/src/libcore/str.rs
+++ b/src/libcore/str.rs
@@ -590,6 +590,40 @@ pub pure fn split_str_nonempty(s: &a/str, sep: &b/str) -> ~[~str] {
     result
 }
 
+/// Levenshtein Distance between two strings
+pub fn levdistance(s: &str, t: &str) -> uint {
+
+    let slen = str::len(s);
+    let tlen = str::len(t);
+
+    if slen == 0 { return tlen; }
+    if tlen == 0 { return slen; }
+
+    let mut dcol = vec::from_fn(tlen + 1, |x| x);
+
+    for str::each_chari(s) |i, sc| {
+
+        let mut current = i;
+        dcol[0] = current + 1;
+
+        for str::each_chari(t) |j, tc| {
+
+            let mut next = dcol[j + 1];
+
+            if sc == tc {
+                dcol[j + 1] = current;
+            } else {
+                dcol[j + 1] = ::cmp::min(current, next);
+                dcol[j + 1] = ::cmp::min(dcol[j + 1], dcol[j]) + 1;
+            }
+
+            current = next;
+        }
+    }
+
+    return dcol[tlen];
+}
+
 /**
  * Splits a string into a vector of the substrings separated by LF ('\n')
  */
diff --git a/src/librustc/middle/resolve.rs b/src/librustc/middle/resolve.rs
index 7058f802bc4..e75a73650b4 100644
--- a/src/librustc/middle/resolve.rs
+++ b/src/librustc/middle/resolve.rs
@@ -4816,6 +4816,42 @@ pub impl Resolver {
         }
     }
 
+    fn find_best_match_for_name(@mut self, name: &str) -> Option<~str> {
+        let mut maybes: ~[~str] = ~[];
+        let mut values: ~[uint] = ~[];
+
+        let mut j = self.value_ribs.len();
+        while j != 0 {
+            j -= 1;
+            let rib = self.value_ribs.get_elt(j);
+            for rib.bindings.each_entry |e| {
+                vec::push(&mut maybes, copy *self.session.str_of(e.key));
+                vec::push(&mut values, uint::max_value);
+            }
+        }
+
+        let mut smallest = 0;
+        for vec::eachi(maybes) |i, &other| {
+
+            values[i] = str::levdistance(name, other);
+
+            if values[i] <= values[smallest] {
+                smallest = i;
+            }
+        }
+
+        if vec::len(values) > 0 &&
+            values[smallest] != uint::max_value &&
+            values[smallest] < str::len(name) + 2 &&
+            maybes[smallest] != name.to_owned() {
+
+            Some(vec::swap_remove(&mut maybes, smallest))
+
+        } else {
+            None
+        }
+    }
+
     fn name_exists_in_scope_struct(@mut self, name: &str) -> bool {
         let mut i = self.type_ribs.len();
         while i != 0 {
@@ -4882,9 +4918,20 @@ pub impl Resolver {
                                         wrong_name));
                         }
                         else {
-                            self.session.span_err(expr.span,
-                                                fmt!("unresolved name: %s",
+                            match self.find_best_match_for_name(wrong_name) {
+
+                                Some(m) => {
+                                    self.session.span_err(expr.span,
+                                            fmt!("unresolved name: `%s`. \
+                                                Did you mean: `%s`?",
+                                                wrong_name, m));
+                                }
+                                None => {
+                                    self.session.span_err(expr.span,
+                                            fmt!("unresolved name: `%s`.",
                                                 wrong_name));
+                                }
+                            }
                         }
                     }
                 }
diff --git a/src/test/compile-fail/alt-join.rs b/src/test/compile-fail/alt-join.rs
index a94709c5774..94488fbb552 100644
--- a/src/test/compile-fail/alt-join.rs
+++ b/src/test/compile-fail/alt-join.rs
@@ -16,6 +16,6 @@ fn my_fail() -> ! { fail!(); }
 fn main() {
     match true { false => { my_fail(); } true => { } }
 
-    log(debug, x); //~ ERROR unresolved name: x
+    log(debug, x); //~ ERROR unresolved name: `x`.
     let x: int;
 }
diff --git a/src/test/compile-fail/bad-expr-path.rs b/src/test/compile-fail/bad-expr-path.rs
index 576f9ef677e..30014817308 100644
--- a/src/test/compile-fail/bad-expr-path.rs
+++ b/src/test/compile-fail/bad-expr-path.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-// error-pattern: unresolved name: m1::a
+// error-pattern: unresolved name: `m1::a`. Did you mean: `args`?
 
 mod m1 {}
 
diff --git a/src/test/compile-fail/bad-expr-path2.rs b/src/test/compile-fail/bad-expr-path2.rs
index 5545bbf68f0..88239a4cc3f 100644
--- a/src/test/compile-fail/bad-expr-path2.rs
+++ b/src/test/compile-fail/bad-expr-path2.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-// error-pattern: unresolved name: m1::a
+// error-pattern: unresolved name: `m1::a`. Did you mean: `args`?
 
 mod m1 {
     pub mod a {}
diff --git a/src/test/compile-fail/does-nothing.rs b/src/test/compile-fail/does-nothing.rs
index c6115f40853..a360d657957 100644
--- a/src/test/compile-fail/does-nothing.rs
+++ b/src/test/compile-fail/does-nothing.rs
@@ -1,3 +1,3 @@
-// error-pattern: unresolved name: this_does_nothing_what_the
+// error-pattern: unresolved name: `this_does_nothing_what_the`.
 fn main() { debug!("doing"); this_does_nothing_what_the; debug!("boing"); }
 
diff --git a/src/test/compile-fail/issue-1476.rs b/src/test/compile-fail/issue-1476.rs
index 4f21e30cc16..7a45ecc83b0 100644
--- a/src/test/compile-fail/issue-1476.rs
+++ b/src/test/compile-fail/issue-1476.rs
@@ -9,5 +9,5 @@
 // except according to those terms.
 
 fn main() {
-    log(error, x); //~ ERROR unresolved name: x
+    log(error, x); //~ ERROR unresolved name: `x`.
 }
diff --git a/src/test/compile-fail/issue-3021-b.rs b/src/test/compile-fail/issue-3021-b.rs
index a782dd58ee6..1d4cd69c54e 100644
--- a/src/test/compile-fail/issue-3021-b.rs
+++ b/src/test/compile-fail/issue-3021-b.rs
@@ -19,7 +19,7 @@ fn siphash(k0 : u64) {
     impl siphash {
         fn reset(&mut self) {
            self.v0 = k0 ^ 0x736f6d6570736575; //~ ERROR attempted dynamic environment-capture
-           //~^ ERROR unresolved name: k0
+           //~^ ERROR unresolved name: `k0`.
         }
     }
 }
diff --git a/src/test/compile-fail/issue-3021-d.rs b/src/test/compile-fail/issue-3021-d.rs
index 38bd007f189..7381d36a223 100644
--- a/src/test/compile-fail/issue-3021-d.rs
+++ b/src/test/compile-fail/issue-3021-d.rs
@@ -31,9 +31,9 @@ fn siphash(k0 : u64, k1 : u64) -> siphash {
    impl siphash for sipstate {
         fn reset() {
             self.v0 = k0 ^ 0x736f6d6570736575;  //~ ERROR attempted dynamic environment-capture
-            //~^ ERROR unresolved name: k0
+            //~^ ERROR unresolved name: `k0`.
             self.v1 = k1 ^ 0x646f72616e646f6d;   //~ ERROR attempted dynamic environment-capture
-            //~^ ERROR unresolved name: k1
+            //~^ ERROR unresolved name: `k1`.
         }
         fn result() -> u64 { return mk_result(self); }
     }
diff --git a/src/test/compile-fail/issue-3021.rs b/src/test/compile-fail/issue-3021.rs
index fdfd2562175..e5a7a7990e5 100644
--- a/src/test/compile-fail/issue-3021.rs
+++ b/src/test/compile-fail/issue-3021.rs
@@ -23,7 +23,7 @@ fn siphash(k0 : u64) -> siphash {
    impl siphash for sipstate {
         fn reset() {
            self.v0 = k0 ^ 0x736f6d6570736575; //~ ERROR attempted dynamic environment-capture
-           //~^ ERROR unresolved name: k0
+           //~^ ERROR unresolved name: `k0`.
         }
     }
     fail!();