[Option] Add 'findNearest' method to catch typos

[modocache]

Summary

Add a method OptTable::findNearest, which allows users of OptTable to
check user input for misspelled options. In addition, have llvm-mt
check for misspelled options. For example, if a user invokes
llvm-mt /oyt:foo, the error message will indicate that while an
option named /oyt: does not exist, /out: does.

The method ports the functionality of the LookupNearestOption method
from LLVM CommandLine to libLLVMOption. This allows tools like Clang
and Swift, which do not use CommandLine, to use this functionality to
suggest similarly spelled options.

As room for future improvement, the new method as-is cannot yet properly suggest
nearby "joined" options -- that is, for an option string "-FozBar", where
"-Foo" is the correct option name and "Bar" is the value being passed along
with the misspelled option, this method will calculate an edit distance of 4,
by deleting "Bar" and changing "z" to "o". It should instead calculate an edit
distance of just 1, by changing "z" to "o" and recognizing "Bar" as a
value. This commit includes a disabled test that expresses this limitation.

Test Plan: check-llvm

[jroelofs]

lib/Option/OptTable.cpp

258

I think you can use range-for via:

for (const Info &CandidateInfo : ArrayRef(OptionInfos).drop_front(FirstSearchableIndex))

260

The ctor call here isn't needed, it's implicit in the assign if you drop it.

293

I think this is a dangling reference to a dead temporary. Make Delimiter a std::string?

301

std::tie(LHS, RHS) = Option.split(Last)

tools/llvm-mt/llvm-mt.cpp

29

Include raw_ostream.h instead, and use llvm::raw_string_ostream instead of ostringstream.

[modocache]

Thanks for the review, @jroelofs! I think I addressed your comments and adopted your suggestions.

[ruiu]

lib/Option/OptTable.cpp

280

I wonder why you chose to use the prefix matching instead of edit distance. Conveniently, StringRef has edit_distance function, so you can use that if you want.

[jroelofs]

lib/Option/OptTable.cpp

280

+1

308

These are the same whether RHS is empty or not.

[modocache]

lib/Option/OptTable.cpp

280

Ah, my apologies, I think this code may not be clear.

Just to make sure we're on the same page: this loop isn't matching input string --hel to valid option --help, it's matching each valid option's set of prefixes (for most LLVM programs' options, those are -, --, or both) to --hel.

The goal here is to find the prefix that matches the one the user provided. The reason I'm doing this is because, below when we compare using StringRef::edit_distance, we get an edit distance of 1 between --hel and both --help (add one p) and -help (remove one -).

But I think it would be nice, if the user provided the input --hel, for LLVM to suggest an option with the same prefix, so I'd like to deterministically return --help. That is, I do *not* want to return -help.

Maybe that's not as desirable behavior as I think it is. But, in order to implement it, I believe I'm unable to use StringRef::edit_distance here. I need to check whether a prefix (of any length, although conventionally they're one or two characters in most LLVM programs) exists at the front of both a valid option and the option string being passed in. StringRef::startswith seems like a natural fit for this, as opposed to StringRef::edit_distance.

[modocache]

Remove unnecessary branch for RHS.empty(). Thanks, @jroelofs!

[jroelofs]

lib/Option/OptTable.cpp

280

Ohh I see, you are using edit_distance below for sorting the actual option name matches, and this is just a heuristic tweak to give preference to options with the same lead characters as what the user wrote.

[v.g.vassilev]

+1 Thanks for working on this. Great to see this happening!

[jroelofs]

lib/Option/OptTable.cpp

301

I think NormalizedName is also a dangling reference to a temporary. It needs to be a std::string since you're concatenating.

[modocache]

Fixed a dangling reference to concatenated string and re-ran clang-format. Thanks, @jroelofs!

[jroelofs]

LGTM

[modocache]

Great, thanks for the reviews, everyone! Some of you have already commented on https://reviews.llvm.org/D41733, which adds "did you mean?" suggestions to Clang, but let me know if there's anything else I can do on that revision.

include/llvm/Option/OptTable.h

public:
   ///
   /// \param [in] Cur - String prefix that all returned flags need
   //  to start with.
   ///
   /// \return The vector of flags which start with Cur.
   std::vector<std::string> findByPrefix(StringRef Cur,
                                         unsigned short DisableFlags) const;
 
+  /// Find the OptTable option that most closely matches the given string.
+  ///
+  /// \param [in] Option - A string, such as "-stdlibs=l", that represents user
+  /// input of an option that may not exist in the OptTable. Note that the
+  /// string includes prefix dashes "-" as well as values "=l".
+  /// \param [out] NearestString - The nearest option string found in the
+  /// OptTable.
+  /// \param [in] FlagsToInclude - Only find options with any of these flags.
+  /// Zero is the default, which includes all flags.
+  /// \param [in] FlagsToExclude - Don't find options with this flag. Zero
+  /// is the default, and means exclude nothing.
+  /// \param [in] MinimumLength - Don't find options shorter than this length.
+  /// For example, a minimum length of 3 prevents "-x" from being considered
+  /// near to "-S".
+  ///
+  /// \return The edit distance of the nearest string found.
+  unsigned findNearest(StringRef Option, std::string &NearestString,
+                       unsigned FlagsToInclude = 0, unsigned FlagsToExclude = 0,
+                       unsigned MinimumLength = 4) const;
+
   /// Add Values to Option's Values class
   ///
   /// \param [in] Option - Prefix + Name of the flag which Values will be
   ///  changed. For example, "-analyzer-checker".
   /// \param [in] Values - String of Values seperated by ",", such as
   ///  "foo, bar..", where foo and bar is the argument which the Option flag
   ///  takes
   ///

lib/Option/OptTable.cpp

for (int I = 0; In.Prefixes[I]; I++) {
         S += In.HelpText;
       if (StringRef(S).startswith(Cur))
         Ret.push_back(S);
     }
   }
   return Ret;
 }
 
+unsigned OptTable::findNearest(StringRef Option, std::string &NearestString,
+                               unsigned FlagsToInclude, unsigned FlagsToExclude,
+                               unsigned MinimumLength) const {
+  assert(!Option.empty());
+
+  // Consider each option as a candidate, finding the closest match.
+  unsigned BestDistance = UINT_MAX;
+  for (const Info &CandidateInfo :
+       ArrayRef<Info>(OptionInfos).drop_front(FirstSearchableIndex)) {
+    StringRef CandidateName = CandidateInfo.Name;
+
+    // Ignore option candidates with empty names, such as "--", or names
+    // that do not meet the minimum length.
+    if (CandidateName.empty() || CandidateName.size() < MinimumLength)
+      continue;
+
+    // If FlagsToInclude were specified, ignore options that don't include
+    // those flags.
+    if (FlagsToInclude && !(CandidateInfo.Flags & FlagsToInclude))
+      continue;
+    // Ignore options that contain the FlagsToExclude.
+    if (CandidateInfo.Flags & FlagsToExclude)
+      continue;
+
+    // Ignore positional argument option candidates (which do not
+    // have prefixes).
+    if (!CandidateInfo.Prefixes)
+      continue;
+    // Find the most appropriate prefix. For example, if a user asks for
+    // "--helm", suggest "--help" over "-help".
+    StringRef Prefix;
+    for (int P = 0; CandidateInfo.Prefixes[P]; P++) {
+      if (Option.startswith(CandidateInfo.Prefixes[P]))
+        Prefix = CandidateInfo.Prefixes[P];
+    }
+
+    // Check if the candidate ends with a character commonly used when
+    // delimiting an option from its value, such as '=' or ':'. If it does,
+    // attempt to split the given option based on that delimiter.
+    std::string Delimiter = "";
+    char Last = CandidateName.back();
+    if (Last == '=' || Last == ':')
+      Delimiter = std::string(1, Last);
+
+    StringRef LHS, RHS;
+    if (Delimiter.empty())
+      LHS = Option;
+    else
+      std::tie(LHS, RHS) = Option.split(Last);
+
+    std::string NormalizedName =
+        (LHS.drop_front(Prefix.size()) + Delimiter).str();
+    unsigned Distance =
+        CandidateName.edit_distance(NormalizedName, /*AllowReplacements=*/true,
+                                    /*MaxEditDistance=*/BestDistance);
+    if (Distance < BestDistance) {
+      BestDistance = Distance;
+      NearestString = (Prefix + CandidateName + RHS).str();
+    }
+  }
+  return BestDistance;
+}
+
 bool OptTable::addValues(const char *Option, const char *Values) {
   for (size_t I = FirstSearchableIndex, E = OptionInfos.size(); I < E; I++) {
     Info &In = OptionInfos[I];
     if (optionMatches(In, Option)) {
       In.Values = Values;
       return true;
     }
   }

test/tools/llvm-mt/help.test

 RUN: llvm-mt /h | FileCheck %s -check-prefix=HELP
 
 HELP:      OVERVIEW: Manifest Tool
 
 RUN: not llvm-mt /foo 2>&1 >/dev/null | FileCheck %s -check-prefix=INVALID
+INVALID: llvm-mt error: invalid option '/foo'
+
+RUN: not llvm-mt /oyt:%t 2>&1 | FileCheck %s -check-prefix=INVALID-BUT-CLOSE
+INVALID-BUT-CLOSE: llvm-mt error: invalid option '/oyt:{{.*}}/help.test.tmp', did you mean '/out:{{.*}}/help.test.tmp'?
 
-INVALID: llvm-mt error: invalid option /foo

tools/llvm-mt/llvm-mt.cpp

 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/PrettyStackTrace.h"
 #include "llvm/Support/Process.h"
 #include "llvm/Support/Signals.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/WindowsManifest/WindowsManifestMerger.h"
 
 #include <system_error>
 
 using namespace llvm;
 
 namespace {
 
 enum ID {
   OPT_INVALID = 0, // This is not an option ID.
 #define OPTION(PREFIX, NAME, ID, KIND, GROUP, ALIAS, ALIASARGS, FLAGS, PARAM,  \
ExitOnErr(errorCodeToError(sys::Process::GetArgumentVector(
       argv_buf, makeArrayRef(argv, argc), ArgAllocator)));
   llvm_shutdown_obj Y; // Call llvm_shutdown() on exit.
 
   CvtResOptTable T;
   unsigned MAI, MAC;
   ArrayRef<const char *> ArgsArr = makeArrayRef(argv + 1, argc);
   opt::InputArgList InputArgs = T.ParseArgs(ArgsArr, MAI, MAC);
 
-  for (auto *Arg : InputArgs.filtered(OPT_INPUT))
-    reportError(Twine("invalid option ") + Arg->getSpelling());
+  for (auto *Arg : InputArgs.filtered(OPT_INPUT)) {
+    auto ArgString = Arg->getAsString(InputArgs);
+    std::string Diag;
+    raw_string_ostream OS(Diag);
+    OS << "invalid option '" << ArgString << "'";
+
+    std::string Nearest;
+    if (T.findNearest(ArgString, Nearest) < 2)
+      OS << ", did you mean '" << Nearest << "'?";
+
+    reportError(OS.str());
+  }
 
   for (auto &Arg : InputArgs) {
     if (Arg->getOption().matches(OPT_unsupported)) {
       outs() << "llvm-mt: ignoring unsupported '" << Arg->getOption().getName()
              << "' option\n";
     }
   }
 

unittests/Option/OptionParsingTest.cpp

TEST(Option, FlagAliasToJoined) {
   // Check that a flag alias provides an empty argument to a joined option.
   const char *MyArgs[] = { "-K" };
   InputArgList AL = T.ParseArgs(MyArgs, MAI, MAC);
   EXPECT_EQ(AL.size(), 1U);
   EXPECT_TRUE(AL.hasArg(OPT_B));
   EXPECT_EQ(1U, AL.getAllArgValues(OPT_B).size());
   EXPECT_EQ("", AL.getAllArgValues(OPT_B)[0]);
 }
+
+TEST(Option, FindNearest) {
+  TestOptTable T;
+  std::string Nearest;
+
+  // Options that are too short should not be considered
+  // "near" other short options.
+  EXPECT_GT(T.findNearest("-A", Nearest), 4U);
+  EXPECT_GT(T.findNearest("/C", Nearest), 4U);
+  EXPECT_GT(T.findNearest("--C=foo", Nearest), 4U);
+
+  // The nearest candidate should mirror the amount of prefix
+  // characters used in the original string.
+  EXPECT_EQ(1U, T.findNearest("-blorb", Nearest));
+  EXPECT_EQ(Nearest, "-blorp");
+  EXPECT_EQ(1U, T.findNearest("--blorm", Nearest));
+  EXPECT_EQ(Nearest, "--blorp");
+
+  // The nearest candidate respects the prefix and value delimiter
+  // of the original string.
+  EXPECT_EQ(1U, T.findNearest("/framb:foo", Nearest));
+  EXPECT_EQ(Nearest, "/cramb:foo");
+
+  // Flags should be included and excluded as specified.
+  EXPECT_EQ(1U, T.findNearest("-doopf", Nearest, /*FlagsToInclude=*/OptFlag2));
+  EXPECT_EQ(Nearest, "-doopf2");
+  EXPECT_EQ(1U, T.findNearest("-doopf", Nearest,
+                              /*FlagsToInclude=*/0,
+                              /*FlagsToExclude=*/OptFlag2));
+  EXPECT_EQ(Nearest, "-doopf1");
+}
+
+TEST(DISABLED_Option, FindNearestFIXME) {
+  TestOptTable T;
+  std::string Nearest;
+
+  // FIXME: Options with joined values should not have those values considered
+  // when calculating distance. The test below would fail if run, but it should
+  // succeed.
+  EXPECT_EQ(1U, T.findNearest("--erbghFoo", Nearest));
+  EXPECT_EQ(Nearest, "--ermghFoo");
+
+}

unittests/Option/Opts.td

 def J : Flag<["-"], "J">, Alias<B>, AliasArgs<["foo"]>;
 def Joo : Flag<["-"], "Joo">, Alias<B>, AliasArgs<["bar"]>;
 
 def K : Flag<["-"], "K">, Alias<B>;
 
 def Slurp : Option<["-"], "slurp", KIND_REMAINING_ARGS>;
 
 def SlurpJoined : Option<["-"], "slurpjoined", KIND_REMAINING_ARGS_JOINED>;
+
+def Blorp : Flag<["-", "--"], "blorp">, HelpText<"The blorp option">, Flags<[OptFlag1]>;
+def Cramb : Joined<["/"], "cramb:">, HelpText<"The cramb option">, MetaVarName<"CRAMB">, Flags<[OptFlag1]>;
+def Doopf1 : Flag<["-"], "doopf1">, HelpText<"The doopf1 option">, Flags<[OptFlag1]>;
+def Doopf2 : Flag<["-"], "doopf2">, HelpText<"The doopf2 option">, Flags<[OptFlag2]>;
+def Ermgh : Joined<["--"], "ermgh">, HelpText<"The ermgh option">, MetaVarName<"ERMGH">, Flags<[OptFlag1]>;
+def DashDash : Option<["--"], "", KIND_REMAINING_ARGS>;