Re-push "[Option] Fix PR37006 prefix choice in findNearest"

[acoomans]

Summary

Original changeset (https://reviews.llvm.org/D46776) by @modocache. It was reverted after the PS4 bot failed.

The issue has been determined to be with the way the PS4 SDK handles this particular option. https://reviews.llvm.org/D50410 removes this test, so we can push this again.

[modocache]

Thanks! I'll land D50410, then this, and monitor the buildbots to see what happens. If they fail again I may revert this once again. Thanks again for looking into this, sorry for the delay in landing it.

[modocache]

Excellent, I think pushing this along with D50410 revealed the true error, as an MSAN buildbot tells use there's a use of an uninitialized value: http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-fast/builds/23176/steps/check-clang%20msan/logs/stdio

I haven't looked into it a ton yet but it seems promising. However, for the time being, I reverted this change in rL341333.

[thakis]

I re-landed this to get access to the msan output, since the link above has long expired. Here's the new link: http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-fast/builds/31821/steps/check-clang%20msan/logs/stdio

Sadly, the bot output isn't super useful:

Command Output (stderr):
--
/b/sanitizer-x86_64-linux-fast/build/llvm/tools/clang/test/CodeGen/thinlto_backend.ll:10:18: error: CHECK-WARNING: expected string not found in input
; CHECK-WARNING: error: invalid argument '-fthinlto-index={{.*}}' only allowed with '-x ir'
                 ^
<stdin>:1:1: note: scanning from here
==7832==WARNING: MemorySanitizer: use-of-uninitialized-value
^

--

I'll see if I can figure out how to do an msan build of llvm.

[thakis]

vitalybuka told me that this should repro things locally:

mkdir /tmp/bot
cd /tmp/bot
svn checkout https://llvm.org/svn/llvm-project/zorg
BUILDBOT_CLOBBER= BUILDBOT_REVISION=YOUR_REV zorg/trunk/zorg/buildbot/builders/sanitizers/buildbot_fast.sh 2>&1 | tee buildlog.txt

I'm now running that and waiting for it.

In the meantime, http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-fast/builds/31821/steps/check-llvm%20asan/logs/stdio has a possibly better error:

[ RUN      ] Option.FindNearest
=================================================================
==64567==ERROR: AddressSanitizer: stack-use-after-scope on address 0x7f488a118db1 at pc 0x000000577ebb bp 0x7ffcd3a9ba90 sp 0x7ffcd3a9ba88
READ of size 1 at 0x7f488a118db1 thread T0
    #0 0x577eba in unsigned int llvm::ComputeEditDistance<char>(llvm::ArrayRef<char>, llvm::ArrayRef<char>, bool, unsigned int) /b/sanitizer-x86_64-linux-fast/build/llvm/include/llvm/ADT/edit_distance.h:81:25
    #1 0x56a016 in llvm::opt::OptTable::findNearest(llvm::StringRef, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >&, unsigned int, unsigned int, unsigned int) const /b/sanitizer-x86_64-linux-fast/build/llvm/lib/Option/OptTable.cpp:301:21
    #2 0x54d0fa in Option_FindNearest_Test::TestBody() /b/sanitizer-x86_64-linux-fast/build/llvm/unittests/Option/OptionParsingTest.cpp:279:3
    #3 0x5f81a1 in HandleExceptionsInMethodIfSupported<testing::Test, void> /b/sanitizer-x86_64-linux-fast/build/llvm/utils/unittest/googletest/src/gtest.cc
    #4 0x5f81a1 in testing::Test::Run() /b/sanitizer-x86_64-linux-fast/build/llvm/utils/unittest/googletest/src/gtest.cc:2474
    #5 0x5fa758 in testing::TestInfo::Run() /b/sanitizer-x86_64-linux-fast/build/llvm/utils/unittest/googletest/src/gtest.cc:2656:11
    #6 0x5fbd14 in testing::TestCase::Run() /b/sanitizer-x86_64-linux-fast/build/llvm/utils/unittest/googletest/src/gtest.cc:2774:28
    #7 0x619834 in testing::internal::UnitTestImpl::RunAllTests() /b/sanitizer-x86_64-linux-fast/build/llvm/utils/unittest/googletest/src/gtest.cc:4649:43
    #8 0x6189af in HandleExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool> /b/sanitizer-x86_64-linux-fast/build/llvm/utils/unittest/googletest/src/gtest.cc
    #9 0x6189af in testing::UnitTest::Run() /b/sanitizer-x86_64-linux-fast/build/llvm/utils/unittest/googletest/src/gtest.cc:4257
    #10 0x5ded86 in RUN_ALL_TESTS /b/sanitizer-x86_64-linux-fast/build/llvm/utils/unittest/googletest/include/gtest/gtest.h:2233:46
    #11 0x5ded86 in main /b/sanitizer-x86_64-linux-fast/build/llvm/utils/unittest/UnitTestMain/TestMain.cpp:50
    #12 0x7f488d38a2e0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x202e0)
    #13 0x42a3a9 in _start (/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan/unittests/Option/OptionTests+0x42a3a9)

Address 0x7f488a118db1 is located in stack of thread T0 at offset 433 in frame
    #0 0x56935f in llvm::opt::OptTable::findNearest(llvm::StringRef, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >&, unsigned int, unsigned int, unsigned int) const /b/sanitizer-x86_64-linux-fast/build/llvm/lib/Option/OptTable.cpp:251

[thakis]

I think I figured it out. r359604 should fix the bug that caused this to be reverted twice.

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>;