[Option] Add 'findNearest' method to catch typos

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`

Reviewers: yamaguchi, v.g.vassilev, teemperor, ruiu, jroelofs

Reviewed By: jroelofs

Subscribers: jroelofs, llvm-commits

Differential Revision: https://reviews.llvm.org/D41732

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@321877 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 63 insertions, 0 deletions

diff --git a/lib/Option/OptTable.cpp b/lib/Option/OptTable.cpp
index c1bb05e817f..f85b9043091 100644
--- a/lib/Option/OptTable.cpp
+++ b/lib/Option/OptTable.cpp
@@ -247,6 +247,69 @@ OptTable::findByPrefix(StringRef Cur, unsigned short DisableFlags) const {
   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];