Make a 'did you mean' suggestion when referencing a non-existent label.

It works for both labels on the command-line and labels in BUILD files.

--
MOS_MIGRATED_REVID=123967347
diff --git a/src/main/java/com/google/devtools/build/lib/packages/Package.java b/src/main/java/com/google/devtools/build/lib/packages/Package.java
index 8a666b0..cbfeb5b 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/Package.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/Package.java
@@ -34,6 +34,7 @@
 import com.google.devtools.build.lib.packages.AttributeMap.AcceptsLabelAttribute;
 import com.google.devtools.build.lib.packages.License.DistributionType;
 import com.google.devtools.build.lib.util.Preconditions;
+import com.google.devtools.build.lib.util.SpellChecker;
 import com.google.devtools.build.lib.vfs.Canonicalizer;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
@@ -528,7 +529,12 @@
       suffix = "; however, a source file of this name exists.  (Perhaps add "
           + "'exports_files([\"" + targetName + "\"])' to " + name + "/BUILD?)";
     } else {
-      suffix = "";
+      String suggestion = SpellChecker.suggest(targetName, targets.keySet());
+      if (suggestion != null) {
+        suffix = " (did you mean '" + suggestion + "'?)";
+      } else {
+        suffix = "";
+      }
     }
 
     throw makeNoSuchTargetException(targetName, suffix);
diff --git a/src/main/java/com/google/devtools/build/lib/util/SpellChecker.java b/src/main/java/com/google/devtools/build/lib/util/SpellChecker.java
index e453ebc..b8fda8f 100644
--- a/src/main/java/com/google/devtools/build/lib/util/SpellChecker.java
+++ b/src/main/java/com/google/devtools/build/lib/util/SpellChecker.java
@@ -14,6 +14,8 @@
 
 package com.google.devtools.build.lib.util;
 
+import javax.annotation.Nullable;
+
 /**
  * Class that provides functions to do spell checking, i.e. detect typos
  * and make suggestions.
@@ -71,4 +73,25 @@
     int result = row[s2.length()];
     return result <= maxEditDistance ? result : -1;
   }
+
+  /**
+   * Find in words which string is the most similar to input (according to
+   * the edit distance, ignoring case) - or null if no string is similar
+   * enough. In case of equality, the first one in words wins.
+   */
+  @Nullable
+  public static String suggest(String input, Iterable<String> words) {
+    String best = null;
+    // Heuristic: the expected number of typos depends on the length of the word.
+    int bestDistance = Math.min(5, input.length() / 2 + 1);
+    input = input.toLowerCase();
+    for (String candidate : words) {
+      int d = editDistance(input, candidate.toLowerCase(), bestDistance);
+      if (d >= 0 && d < bestDistance) {
+        bestDistance = d;
+        best = candidate;
+      }
+    }
+    return best;
+  }
 }