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()); +}