Add spell-checking to `gn help`.
I tried porting a gyp copies step to gn, and one of the things I tried while
doing so whas `gn help copies`. If help had spell-checking, it would've
suggested `gn help copy`. Since that seems like a nice change, add this.
Also stop printing full help output when a topic is not found, because then
the "not found" error scrolls by so fast that I never see it.
Demo:
$ out/gn/gn help copyasdfasdf
ERROR No help on "copyasdfasdf".
Run `gn help` for a list of available topics.
$ out/gn/gn help copies
ERROR No help on "copies".
Did you mean `gn help copy`?
(There's another implementation of EditDistance() in
components/ssl/error_classification.cc -- but that works based on strings
not StringPieces and it doesn't have a "max_distance" parameter.
Since there's only one other instance of this function, just having a second version
of it seems preferrable over finding some place to put this function so it can be used
from both places. I'm however improving the other copy a bit in
https://codereview.chromium.org/1690593002/)
BUG=none
Review URL: https://codereview.chromium.org/1681363003
Cr-Original-Commit-Position: refs/heads/master@{#375673}
Cr-Mirrored-From: https://chromium.googlesource.com/chromium/src
Cr-Mirrored-Commit: 11afb324fa322a3d651124f3ca244c9595f84768
diff --git a/tools/gn/command_help.cc b/tools/gn/command_help.cc
index 3479597..18cb6d1 100644
--- a/tools/gn/command_help.cc
+++ b/tools/gn/command_help.cc
@@ -16,6 +16,7 @@
#include "tools/gn/runtime_deps.h"
#include "tools/gn/setup.h"
#include "tools/gn/standard_out.h"
+#include "tools/gn/string_utils.h"
#include "tools/gn/substitution_writer.h"
#include "tools/gn/switches.h"
#include "tools/gn/variables.h"
@@ -176,85 +177,83 @@
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;
}
diff --git a/tools/gn/string_utils.cc b/tools/gn/string_utils.cc
index 83a98bd..6f47b91 100644
--- a/tools/gn/string_utils.cc
+++ b/tools/gn/string_utils.cc
@@ -284,3 +284,62 @@
}
return true;
}
+
+size_t EditDistance(const base::StringPiece& s1,
+ 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 base::StringPiece& 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;
+}
diff --git a/tools/gn/string_utils.h b/tools/gn/string_utils.h
index 07be4c8..744714a 100644
--- a/tools/gn/string_utils.h
+++ b/tools/gn/string_utils.h
@@ -5,6 +5,8 @@
#ifndef TOOLS_GN_STRING_UTILS_H_
#define TOOLS_GN_STRING_UTILS_H_
+#include <vector>
+
#include "base/strings/string_piece.h"
class Err;
@@ -35,4 +37,17 @@
Value* result,
Err* err);
+// Returns the minimum number of inserts, deleted, and replacements of
+// characters needed to transform s1 to s2, or max_edit_distance + 1 if
+// transforming s1 into s2 isn't possible in at most max_edit_distance steps.
+size_t EditDistance(const base::StringPiece& s1,
+ const base::StringPiece& s2,
+ size_t max_edit_distance);
+
+// Given a string |text| and a vector of correctly-spelled strings |words|,
+// returns the first string in |words| closest to |text|, or an empty
+// StringPiece if none of the strings in |words| is close.
+base::StringPiece SpellcheckString(const base::StringPiece& text,
+ const std::vector<base::StringPiece>& words);
+
#endif // TOOLS_GN_STRING_UTILS_H_
diff --git a/tools/gn/string_utils_unittest.cc b/tools/gn/string_utils_unittest.cc
index d62e17e..570997f 100644
--- a/tools/gn/string_utils_unittest.cc
+++ b/tools/gn/string_utils_unittest.cc
@@ -111,3 +111,44 @@
EXPECT_TRUE(CheckExpansionCase("${1 + 2}", nullptr, false));
EXPECT_TRUE(CheckExpansionCase("${print(1)}", nullptr, false));
}
+
+TEST(StringUtils, EditDistance) {
+ EXPECT_EQ(3u, EditDistance("doom melon", "dune melon", 100));
+ EXPECT_EQ(2u, EditDistance("doom melon", "dune melon", 1));
+
+ EXPECT_EQ(2u, EditDistance("ab", "ba", 100));
+ EXPECT_EQ(2u, EditDistance("ba", "ab", 100));
+
+ EXPECT_EQ(2u, EditDistance("ananas", "banana", 100));
+ EXPECT_EQ(2u, EditDistance("banana", "ananas", 100));
+
+ EXPECT_EQ(2u, EditDistance("unclear", "nuclear", 100));
+ EXPECT_EQ(2u, EditDistance("nuclear", "unclear", 100));
+
+ EXPECT_EQ(3u, EditDistance("chrome", "chromium", 100));
+ EXPECT_EQ(3u, EditDistance("chromium", "chrome", 100));
+
+ EXPECT_EQ(4u, EditDistance("", "abcd", 100));
+ EXPECT_EQ(4u, EditDistance("abcd", "", 100));
+
+ EXPECT_EQ(4u, EditDistance("xxx", "xxxxxxx", 100));
+ EXPECT_EQ(4u, EditDistance("xxxxxxx", "xxx", 100));
+
+ EXPECT_EQ(7u, EditDistance("yyy", "xxxxxxx", 100));
+ EXPECT_EQ(7u, EditDistance("xxxxxxx", "yyy", 100));
+}
+
+TEST(StringUtils, SpellcheckString) {
+ std::vector<base::StringPiece> words;
+ words.push_back("your");
+ words.push_back("bravado");
+ words.push_back("won\'t");
+ words.push_back("help");
+ words.push_back("you");
+ words.push_back("now");
+
+ EXPECT_EQ("help", SpellcheckString("halp", words));
+
+ // barbados has an edit distance of 4 from bravado, so there's no suggestion.
+ EXPECT_TRUE(SpellcheckString("barbados", words).empty());
+}
