Suggest similar flags in case of undefined flags.

Using Damerau-Levenshtein distance to calculate potential candidates to suggest.

PiperOrigin-RevId: 499449034
Change-Id: I805aafefcd0f4f85585ac33a041c15360619c96a

3 files changed, 148 insertions, 4 deletions

diff --git a/absl/flags/internal/parse.h b/absl/flags/internal/parse.h
index de706c89..0a7012fc 100644
--- a/absl/flags/internal/parse.h
+++ b/absl/flags/internal/parse.h
@@ -52,6 +52,10 @@ std::vector<char*> ParseCommandLineImpl(int argc, char* argv[],
 // command line or specified in flag file present on the original command line.
 bool WasPresentOnCommandLine(absl::string_view flag_name);
 
+// Return existing flags similar to the parameter, in order to help in case of
+// misspellings.
+std::vector<std::string> GetMisspellingHints(absl::string_view flag);
+
 }  // namespace flags_internal
 ABSL_NAMESPACE_END
 }  // namespace absl
diff --git a/absl/flags/parse.cc b/absl/flags/parse.cc
index 2851c0f7..cd61e80a 100644
--- a/absl/flags/parse.cc
+++ b/absl/flags/parse.cc
@@ -18,6 +18,7 @@
 #include <stdlib.h>
 
 #include <algorithm>
+#include <cstdint>
 #include <fstream>
 #include <iostream>
 #include <iterator>
@@ -47,7 +48,9 @@
 #include "absl/flags/usage.h"
 #include "absl/flags/usage_config.h"
 #include "absl/strings/ascii.h"
+#include "absl/strings/internal/damerau_levenshtein_distance.h"
 #include "absl/strings/str_cat.h"
+#include "absl/strings/str_join.h"
 #include "absl/strings/string_view.h"
 #include "absl/strings/strip.h"
 #include "absl/synchronization/mutex.h"
@@ -72,6 +75,11 @@ ABSL_CONST_INIT absl::Mutex specified_flags_guard(absl::kConstInit);
 ABSL_CONST_INIT std::vector<const CommandLineFlag*>* specified_flags
     ABSL_GUARDED_BY(specified_flags_guard) = nullptr;
 
+// Suggesting at most kMaxHints flags in case of misspellings.
+ABSL_CONST_INIT const size_t kMaxHints = 100;
+// Suggesting only flags which have a smaller distance than kMaxDistance.
+ABSL_CONST_INIT const size_t kMaxDistance = 3;
+
 struct SpecifiedFlagsCompare {
   bool operator()(const CommandLineFlag* a, const CommandLineFlag* b) const {
     return a->Name() < b->Name();
@@ -605,6 +613,55 @@ bool WasPresentOnCommandLine(absl::string_view flag_name) {
 
 // --------------------------------------------------------------------
 
+struct BestHints {
+  explicit BestHints(uint8_t _max) : best_distance(_max + 1) {}
+  bool AddHint(absl::string_view hint, uint8_t distance) {
+    if (hints.size() >= kMaxHints) return false;
+    if (distance == best_distance) {
+      hints.emplace_back(hint);
+    }
+    if (distance < best_distance) {
+      best_distance = distance;
+      hints = std::vector<std::string>{std::string(hint)};
+    }
+    return true;
+  }
+
+  uint8_t best_distance;
+  std::vector<std::string> hints;
+};
+
+// Return the list of flags with the smallest Damerau-Levenshtein distance to
+// the given flag.
+std::vector<std::string> GetMisspellingHints(const absl::string_view flag) {
+  const size_t maxCutoff = std::min(flag.size() / 2 + 1, kMaxDistance);
+  auto undefok = absl::GetFlag(FLAGS_undefok);
+  BestHints best_hints(static_cast<uint8_t>(maxCutoff));
+  absl::flags_internal::ForEachFlag([&](const CommandLineFlag& f) {
+    if (best_hints.hints.size() >= kMaxHints) return;
+    uint8_t distance = strings_internal::CappedDamerauLevenshteinDistance(
+        flag, f.Name(), best_hints.best_distance);
+    best_hints.AddHint(f.Name(), distance);
+    // For boolean flags, also calculate distance to the negated form.
+    if (f.IsOfType<bool>()) {
+      const std::string negated_flag = absl::StrCat("no", f.Name());
+      distance = strings_internal::CappedDamerauLevenshteinDistance(
+          flag, negated_flag, best_hints.best_distance);
+      best_hints.AddHint(negated_flag, distance);
+    }
+  });
+  // Finally calculate distance to flags in "undefok".
+  absl::c_for_each(undefok, [&](const absl::string_view f) {
+    if (best_hints.hints.size() >= kMaxHints) return;
+    uint8_t distance = strings_internal::CappedDamerauLevenshteinDistance(
+        flag, f, best_hints.best_distance);
+    best_hints.AddHint(absl::StrCat(f, " (undefok)"), distance);
+  });
+  return best_hints.hints;
+}
+
+// --------------------------------------------------------------------
+
 std::vector<char*> ParseCommandLineImpl(int argc, char* argv[],
                                         ArgvListAction arg_list_act,
                                         UsageFlagsAction usage_flag_act,
@@ -755,10 +812,19 @@ std::vector<char*> ParseCommandLineImpl(int argc, char* argv[],
 
   for (const auto& flag_name : undefined_flag_names) {
     if (CanIgnoreUndefinedFlag(flag_name.second)) continue;
-
-    flags_internal::ReportUsageError(
-        absl::StrCat("Unknown command line flag '", flag_name.second, "'"),
-        true);
+    // Verify if flag_name has the "no" already removed
+    std::vector<std::string> flags;
+    if (flag_name.first) flags = GetMisspellingHints(flag_name.second);
+    if (flags.empty()) {
+      flags_internal::ReportUsageError(
+          absl::StrCat("Unknown command line flag '", flag_name.second, "'"),
+          true);
+    } else {
+      flags_internal::ReportUsageError(
+          absl::StrCat("Unknown command line flag '", flag_name.second,
+                       "'. Did you mean: ", absl::StrJoin(flags, ", "), " ?"),
+          true);
+    }
 
     success = false;
   }
diff --git a/absl/flags/parse_test.cc b/absl/flags/parse_test.cc
index 8dc91db2..418b0e55 100644
--- a/absl/flags/parse_test.cc
+++ b/absl/flags/parse_test.cc
@@ -17,6 +17,7 @@
 
 #include <stdlib.h>
 
+#include <cstddef>
 #include <fstream>
 #include <string>
 #include <vector>
@@ -39,6 +40,36 @@
 #include <windows.h>
 #endif
 
+// Define 125 similar flags to test kMaxHints for flag suggestions.
+#define FLAG_MULT(x) F3(x)
+#define TEST_FLAG_HEADER FLAG_HEADER_
+
+#define F(name) ABSL_FLAG(int, name, 0, "");
+
+#define F1(name) \
+  F(name##1);    \
+  F(name##2);    \
+  F(name##3);    \
+  F(name##4);    \
+  F(name##5);
+/**/
+#define F2(name) \
+  F1(name##1);   \
+  F1(name##2);   \
+  F1(name##3);   \
+  F1(name##4);   \
+  F1(name##5);
+/**/
+#define F3(name) \
+  F2(name##1);   \
+  F2(name##2);   \
+  F2(name##3);   \
+  F2(name##4);   \
+  F2(name##5);
+/**/
+
+FLAG_MULT(TEST_FLAG_HEADER)
+
 namespace {
 
 using absl::base_internal::ScopedSetEnv;
@@ -565,6 +596,49 @@ TEST_F(ParseDeathTest, TestInvalidUDTFlagFormat) {
 
 // --------------------------------------------------------------------
 
+TEST_F(ParseDeathTest, TestFlagSuggestions) {
+  const char* in_args1[] = {
+      "testbin",
+      "--legacy_boo",
+  };
+  EXPECT_DEATH_IF_SUPPORTED(
+      InvokeParse(in_args1),
+      "Unknown command line flag 'legacy_boo'. Did you mean: legacy_bool ?");
+
+  const char* in_args2[] = {"testbin", "--foo", "--undefok=foo1"};
+  EXPECT_DEATH_IF_SUPPORTED(
+      InvokeParse(in_args2),
+      "Unknown command line flag 'foo'. Did you mean: foo1 \\(undefok\\)?");
+
+  const char* in_args3[] = {
+      "testbin",
+      "--nolegacy_ino",
+  };
+  EXPECT_DEATH_IF_SUPPORTED(InvokeParse(in_args3),
+                            "Unknown command line flag 'nolegacy_ino'. Did "
+                            "you mean: nolegacy_bool, legacy_int ?");
+}
+
+// --------------------------------------------------------------------
+
+TEST_F(ParseTest, GetHints) {
+  EXPECT_THAT(absl::flags_internal::GetMisspellingHints("legacy_boo"),
+              testing::ContainerEq(std::vector<std::string>{"legacy_bool"}));
+  EXPECT_THAT(absl::flags_internal::GetMisspellingHints("nolegacy_itn"),
+              testing::ContainerEq(std::vector<std::string>{"legacy_int"}));
+  EXPECT_THAT(absl::flags_internal::GetMisspellingHints("nolegacy_int1"),
+              testing::ContainerEq(std::vector<std::string>{"legacy_int"}));
+  EXPECT_THAT(absl::flags_internal::GetMisspellingHints("nolegacy_int"),
+              testing::ContainerEq(std::vector<std::string>{"legacy_int"}));
+  EXPECT_THAT(absl::flags_internal::GetMisspellingHints("nolegacy_ino"),
+              testing::ContainerEq(
+                  std::vector<std::string>{"nolegacy_bool", "legacy_int"}));
+  EXPECT_THAT(
+      absl::flags_internal::GetMisspellingHints("FLAG_HEADER_000").size(), 100);
+}
+
+// --------------------------------------------------------------------
+
 TEST_F(ParseTest, TestLegacyFlags) {
   const char* in_args1[] = {
       "testbin",