Add spell-checking to `gn help`.

tools/gn/command_help.cc

Index: tools/gn/command_help.cc
diff --git a/tools/gn/command_help.cc b/tools/gn/command_help.cc
index 3479597f4bdf953379c46527bc20d9a4c055784f..da599cfb21879b8be76d7e98d422a9791b122364 100644
--- a/tools/gn/command_help.cc
+++ b/tools/gn/command_help.cc
@@ -143,6 +143,65 @@ bool PrintHelpOnSwitch(const std::string& what) {
   return true;
 }
 
+size_t EditDistance(const base::StringPiece& s1,

[brettw, 2016/02/16 20:48:28]

This is exciting, I've been wanting to add spellchecking to various commands.

As such, can you put this in tools/gn/string_utils.h and add a unit test for it?

+                    const base::StringPiece& s2,
+                    size_t max_edit_distance) {
+  // The algorithm implemented below is the "classic"
+  // dynamic-programming algorithm for computing the Levenshtein
+  // distance, which is described here:
+  //
+  //   http://en.wikipedia.org/wiki/Levenshtein_distance
+  //
+  // Although the algorithm is typically described using an m x n
+  // array, only one row plus one element are used at a time, so this
+  // implementation just keeps one vector for the row.  To update one entry,
+  // only the entries to the left, top, and top-left are needed.  The left
+  // entry is in row[x-1], the top entry is what's in row[x] from the last
+  // iteration, and the top-left entry is stored in previous.
+  size_t m = s1.size();
+  size_t n = s2.size();
+
+  std::vector<size_t> row(n + 1);
+  for (size_t i = 1; i <= n; ++i)
+    row[i] = i;
+
+  for (size_t y = 1; y <= m; ++y) {
+    row[0] = y;
+    size_t best_this_row = row[0];
+
+    size_t previous = y - 1;
+    for (size_t x = 1; x <= n; ++x) {
+      size_t old_row = row[x];
+      row[x] = std::min(previous + (s1[y - 1] == s2[x - 1] ? 0u : 1u),
+                        std::min(row[x - 1], row[x]) + 1u);
+      previous = old_row;
+      best_this_row = std::min(best_this_row, row[x]);
+    }
+
+    if (max_edit_distance && best_this_row > max_edit_distance)
+      return max_edit_distance + 1;
+  }
+
+  return row[n];
+}
+
+base::StringPiece SpellcheckString(
+    const std::string& text,
+    const std::vector<base::StringPiece>& words) {
+  const size_t kMaxValidEditDistance = 3u;
+
+  size_t min_distance = kMaxValidEditDistance + 1u;
+  base::StringPiece result;
+  for (base::StringPiece word : words) {
+    size_t distance = EditDistance(word, text, kMaxValidEditDistance);
+    if (distance < min_distance) {
+      min_distance = distance;
+      result = word;
+    }
+  }
+  return result;
+}
+
 }  // namespace
 
 const char kHelp[] = "help";
@@ -176,85 +235,83 @@ int RunHelp(const std::vector<std::string>& args) {
     what = args[0];
   }
 
+  std::vector<base::StringPiece> all_help_topics;
+
   // Check commands.
   const commands::CommandInfoMap& command_map = commands::GetCommands();
-  commands::CommandInfoMap::const_iterator found_command =
-      command_map.find(what);
+  auto found_command = command_map.find(what);
   if (found_command != command_map.end()) {
     PrintLongHelp(found_command->second.help);
     return 0;
   }
+  for (const auto& entry : command_map)
+    all_help_topics.push_back(entry.first);
 
   // Check functions.
   const functions::FunctionInfoMap& function_map = functions::GetFunctions();
-  functions::FunctionInfoMap::const_iterator found_function =
-      function_map.find(what);
+  auto found_function = function_map.find(what);
   if (found_function != function_map.end()) {
     PrintLongHelp(found_function->second.help);
     return 0;
   }
+  for (const auto& entry : function_map)
+    all_help_topics.push_back(entry.first);
 
   // Builtin variables.
   const variables::VariableInfoMap& builtin_vars =
       variables::GetBuiltinVariables();
-  variables::VariableInfoMap::const_iterator found_builtin_var =
-      builtin_vars.find(what);
+  auto found_builtin_var = builtin_vars.find(what);
   if (found_builtin_var != builtin_vars.end()) {
     PrintLongHelp(found_builtin_var->second.help);
     return 0;
   }
+  for (const auto& entry : builtin_vars)
+    all_help_topics.push_back(entry.first);
 
   // Target variables.
   const variables::VariableInfoMap& target_vars =
       variables::GetTargetVariables();
-  variables::VariableInfoMap::const_iterator found_target_var =
-      target_vars.find(what);
+  auto found_target_var = target_vars.find(what);
   if (found_target_var != target_vars.end()) {
     PrintLongHelp(found_target_var->second.help);
     return 0;
   }
+  for (const auto& entry : target_vars)
+    all_help_topics.push_back(entry.first);
 
   // Random other topics.
-  if (what == "all") {
-    PrintAllHelp();
-    return 0;
-  }
-  if (what == "buildargs") {
-    PrintLongHelp(kBuildArgs_Help);
-    return 0;
-  }
-  if (what == "dotfile") {
-    PrintLongHelp(kDotfile_Help);
-    return 0;
-  }
-  if (what == "grammar") {
-    PrintLongHelp(kGrammar_Help);
-    return 0;
-  }
-  if (what == "input_conversion") {
+  std::map<std::string, std::function<void()>> random_topics;
+  random_topics["all"] = PrintAllHelp;
+  random_topics["buildargs"] = [=]() { PrintLongHelp(kBuildArgs_Help); };
+  random_topics["dotfile"] = [=]() { PrintLongHelp(kDotfile_Help); };
+  random_topics["grammar"] = [=]() { PrintLongHelp(kGrammar_Help); };
+  random_topics["input_conversion"] = [=]() {
     PrintLongHelp(kInputConversion_Help);
-    return 0;
-  }
-  if (what == "label_pattern") {
-    PrintLongHelp(kLabelPattern_Help);
-    return 0;
-  }
-  if (what == "runtime_deps") {
-    PrintLongHelp(kRuntimeDeps_Help);
-    return 0;
-  }
-  if (what == "source_expansion") {
+  };
+  random_topics["label_pattern"] = [=]() { PrintLongHelp(kLabelPattern_Help); };
+  random_topics["runtime_deps"] = [=]() { PrintLongHelp(kRuntimeDeps_Help); };
+  random_topics["source_expansion"] = [=]() {
     PrintLongHelp(kSourceExpansion_Help);
+  };
+  random_topics["switches"] = PrintSwitchHelp;
+  auto found_random_topic = random_topics.find(what);
+  if (found_random_topic != random_topics.end()) {
+    found_random_topic->second();
     return 0;
   }
-  if (what == "switches") {
-    PrintSwitchHelp();
-    return 0;
-  }
+  for (const auto& entry : random_topics)
+    all_help_topics.push_back(entry.first);
 
   // No help on this.
   Err(Location(), "No help on \"" + what + "\".").PrintToStdout();
-  RunHelp(std::vector<std::string>());
+  base::StringPiece suggestion = SpellcheckString(what, all_help_topics);
+  if (suggestion.empty()) {
+    OutputString("Run `gn help` for a list of available topics.\n",
+                 DECORATION_NONE);
+  } else {
+    OutputString("Did you mean `gn help " + suggestion.as_string() + "`?\n",
+                 DECORATION_NONE);
+  }
   return 1;
 }