[Option] Fix PR37006 prefix choice in findNearest

[modocache]

Summary

In https://bugs.llvm.org/show_bug.cgi?id=37006 Nico Weber points out a
flaw in OptTable::findNearest: if an option "foo"'s prefixes are "--"
and "-", then the nearest option for "--fob" will be "-foo". This is
incorrect, however, since the function is expected to return "--foo".

The bug is due to a naive loop that attempts to predetermines which
prefix is best. Instead, compute the edit distance for each prefix/name
pair.

Test Plan: check-llvm

[thakis]

Thanks!

lib/Option/OptTable.cpp

284 ↗

(On Diff #146415)

Shouldn't getting the longest prefix here be good enough? Something like this:

StringRef Prefix;
int PrefixLength = 0;
for (int P = 0; Candidateinfo.Prefixes[P]; P++) {
  StringRef Candidate = CandidateInfo.Prefixes[P];
  if (Candiate.size() > PrefixLength && Option.startswith(Candidate)) {
    Prefix = Candidate;
    PrefixLength = Candidate.size();
  }
}

…and keep everything else the same?

[modocache]

lib/Option/OptTable.cpp

284 ↗

(On Diff #146415)

That's a good suggestion, but here's a case in which this loop wouldn't work: the user invokes clang -migrate foo.cpp, but the correct argument is --migrate. In this case, the --migrate option does not provide a - prefix, it only provides --. However the -- prefix is ruled out by the if statement above: -migrate does not start with --.

(The unit tests managed to catch the edge case above, hooray!)

My personal preference would be to check the edit distance of each prefix/name pair, as this diff currently does. It's slightly more computationally expensive, but I think it's a more comprehensive check.

[thakis]

Makes sense, lgtm. Thanks!

[modocache]

Thanks for the reviews, and for pointing out the bug!

[modocache]

I'm not yet sure why, but this change caused buildbot failures due to a test in Clang for the "did you mean" feature (example: http://lab.llvm.org:8011/builders/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/builds/29988). I couldn't figure out why the buildbots would fail whereas the Clang tests pass for me locally, and so reverted this change for the time being, in rL332304. I'll try to resubmit once I've figured out and fixed the issue.

[thakis]

My guess is it's because the clang tests check if the edit distance is > 1, when you really want to check > 0 instead. Maybe you can try changing that in clang, then relanding?

[modocache]

Hmm... but the >1 condition is such that an edit distance of greater than 1 results in no suggestion, whereas an edit distance of 1 or 0 results in a suggestion. In this case -- and apparently only on certain platforms' buildbots -- the edit distance between -debug-info-macros and -debug-info-macro is 1, and so it should display a suggestion.

The code:

if (OptTbl->findNearest(ArgString, Nearest, IncludedFlagsBitmask) > 1)
  Diags.Report(diag::err_drv_unknown_argument) << ArgString;
else
  Diags.Report(diag::err_drv_unknown_argument_with_suggestion)
      << ArgString << Nearest;

The failure:

FAIL: Clang :: Driver/unknown-arg.c (7531 of 40411)
******************** TEST 'Clang :: Driver/unknown-arg.c' FAILED ********************
Script:
--
not /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.obj/bin/clang /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.src/tools/clang/test/Driver/unknown-arg.c -cake-is-lie -%0 -%d -HHHH -munknown-to-clang-option -print-stats -funknown-to-clang-option -ifoo -imultilib dir -### 2>&1 |  /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.obj/bin/FileCheck /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.src/tools/clang/test/Driver/unknown-arg.c
/home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.obj/bin/clang /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.src/tools/clang/test/Driver/unknown-arg.c -imultilib dir -### 2>&1 |  /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.obj/bin/FileCheck /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.src/tools/clang/test/Driver/unknown-arg.c --check-prefix=MULTILIB
not /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.obj/bin/clang /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.src/tools/clang/test/Driver/unknown-arg.c -stdlibs=foo -hell -version -### 2>&1 |  /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.obj/bin/FileCheck /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.src/tools/clang/test/Driver/unknown-arg.c --check-prefix=DID-YOU-MEAN
/home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.obj/bin/clang --driver-mode=cl -cake-is-lie -%0 -%d -HHHH -munknown-to-clang-option -print-stats -funknown-to-clang-option -### -c -- /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.src/tools/clang/test/Driver/unknown-arg.c 2>&1 |  /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.obj/bin/FileCheck /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.src/tools/clang/test/Driver/unknown-arg.c --check-prefix=CL
/home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.obj/bin/clang --driver-mode=cl -Brepo -### -- /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.src/tools/clang/test/Driver/unknown-arg.c 2>&1 |  /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.obj/bin/FileCheck /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.src/tools/clang/test/Driver/unknown-arg.c --check-prefix=CL-DID-YOU-MEAN
not /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.obj/bin/clang --driver-mode=cl -cake-is-lie -%0 -%d -HHHH -munknown-to-clang-option -print-stats -funknown-to-clang-option -c -Werror=unknown-argument -### -- /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.src/tools/clang/test/Driver/unknown-arg.c 2>&1 |  /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.obj/bin/FileCheck /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.src/tools/clang/test/Driver/unknown-arg.c --check-prefix=CL-ERROR
not /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.obj/bin/clang --driver-mode=cl -helo -Werror=unknown-argument -### -- /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.src/tools/clang/test/Driver/unknown-arg.c 2>&1 |  /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.obj/bin/FileCheck /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.src/tools/clang/test/Driver/unknown-arg.c --check-prefix=CL-ERROR-DID-YOU-MEAN
/home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.obj/bin/clang --driver-mode=cl -cake-is-lie -%0 -%d -HHHH -munknown-to-clang-option -print-stats -funknown-to-clang-option -c -Wno-unknown-argument -### -- /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.src/tools/clang/test/Driver/unknown-arg.c 2>&1 |  /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.obj/bin/FileCheck /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.src/tools/clang/test/Driver/unknown-arg.c --check-prefix=SILENT
not /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.obj/bin/clang -cc1as -hell --version -debug-info-macros 2>&1 |  /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.obj/bin/FileCheck /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.src/tools/clang/test/Driver/unknown-arg.c --check-prefix=CC1AS-DID-YOU-MEAN
not /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.obj/bin/clang -cc1asphalt -help 2>&1 |  /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.obj/bin/FileCheck /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.src/tools/clang/test/Driver/unknown-arg.c --check-prefix=UNKNOWN-INTEGRATED
/home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.obj/bin/clang -S /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.src/tools/clang/test/Driver/unknown-arg.c -o /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.obj/tools/clang/test/Driver/Output/unknown-arg.c.tmp.s  -Wunknown-to-clang-option 2>&1 | /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.obj/bin/FileCheck --check-prefix=IGNORED /home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.src/tools/clang/test/Driver/unknown-arg.c
--
Exit Code: 1

Command Output (stderr):
--
/home/buildslave/ps4-buildslave4/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/llvm.src/tools/clang/test/Driver/unknown-arg.c:54:24: error: expected string not found in input
// CC1AS-DID-YOU-MEAN: error: unknown argument '-debug-info-macros', did you mean '-debug-info-macro'?
                       ^
<stdin>:3:1: note: scanning from here
clang -cc1as: error: unknown argument: '-debug-info-macros'
^
<stdin>:3:15: note: possible intended match here
clang -cc1as: error: unknown argument: '-debug-info-macros'
              ^

--

********************

What's more, it seems like the other checks in this file succeed. So whereas -debug-info-macros does not result in a suggestion of -debug-info-macro, --version does result in a suggestion -version.

Meanwhile, this test passes for me locally, on a Linux x86_84 machine. I wonder what gives...? I'll keep looking into it.

[thakis]

Hm, does this only happen on the ps4 bots? Maybe that toolchain sets some default behavior that changes if this flag is exposed or something. Does it repro if you pass -triple x86_64-scei-ps4-ubuntu in the RUN line?

[thakis]

I can repro the failure with the following diff. Investigating...

diff --git a/clang/test/Driver/unknown-arg.c b/clang/test/Driver/unknown-arg.c
index 4ea43278b7e..3e42ff0e2a4 100644
--- a/clang/test/Driver/unknown-arg.c
+++ b/clang/test/Driver/unknown-arg.c
@@ -16,7 +16,7 @@
 // RUN: FileCheck %s --check-prefix=SILENT
 // RUN: not %clang -cc1as -hell --version 2>&1 | \
 // RUN: FileCheck %s --check-prefix=CC1AS-DID-YOU-MEAN
-// RUN: not %clang -cc1asphalt -help 2>&1 | \
+// RUN: not %clang --target=x86_64-scei-ps4-ubuntu -cc1asphalt -help 2>&1 | \
 // RUN: FileCheck %s --check-prefix=UNKNOWN-INTEGRATED
 
 // CHECK: error: unknown argument: '-cake-is-lie'

[thakis]

Actually, it looks like 341327 already fixed the test problem and we just never relanded this change here. I'll try relanding.

[thakis]

Aha, this was then reverted again in r341333 due to "an MSAN error". Details are at https://reviews.llvm.org/D50515 . I'll shut up here and continue talking over there :)

llvm/trunk/lib/Option/OptTable.cpp

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.
+  // Consider each [option prefix + option name] pair 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.
+    // We can eliminate some option prefix/name pairs as candidates right away:
+    // * 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 were specified, ignore options that don't include
+    //   those flags.
     if (FlagsToInclude && !(CandidateInfo.Flags & FlagsToInclude))
       continue;
-    // Ignore options that contain the FlagsToExclude.
+    // * Ignore options that contain the FlagsToExclude.
     if (CandidateInfo.Flags & FlagsToExclude)
       continue;
 
-    // Ignore positional argument option candidates (which do not
-    // have prefixes).
+    // * 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 = CandidateInfo.Prefixes[0];
-    for (int P = 1; 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
+    // Now 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();
+    // Consider each possible prefix for each candidate to find the most
+    // appropriate one. For example, if a user asks for "--helm", suggest
+    // "--help" over "-help".
+    for (int P = 0; const char *const CandidatePrefix = CandidateInfo.Prefixes[P]; P++) {
+      std::string NormalizedName = (LHS + Delimiter).str();
+      StringRef Candidate = (CandidatePrefix + CandidateName).str();
       unsigned Distance =
-        CandidateName.edit_distance(NormalizedName, /*AllowReplacements=*/true,
-                                    /*MaxEditDistance=*/BestDistance);
+          Candidate.edit_distance(NormalizedName, /*AllowReplacements=*/true,
       if (Distance < BestDistance) {
         BestDistance = Distance;
-      NearestString = (Prefix + CandidateName + RHS).str();
+        NearestString = (Candidate + 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];

llvm/trunk/unittests/Option/OptionParsingTest.cpp

TEST(Option, FindNearest) {
   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");
+  EXPECT_EQ(1U, T.findNearest("-blarg", Nearest));
+  EXPECT_EQ(Nearest, "-blarn");
+  EXPECT_EQ(1U, T.findNearest("--blarm", Nearest));
+  EXPECT_EQ(Nearest, "--blarn");
   EXPECT_EQ(1U, T.findNearest("-fjormp", Nearest));
   EXPECT_EQ(Nearest, "--fjormp");
 
   // 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");
 

llvm/trunk/unittests/Option/Opts.td

 
 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 Blarn : Flag<["--", "-"], "blarn">, HelpText<"The blarn 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 Fjormp : Flag<["--"], "fjormp">, HelpText<"The fjormp option">, Flags<[OptFlag1]>;
 def DashDash : Option<["--"], "", KIND_REMAINING_ARGS>;