[AutoComplete] Use stronger sort predicate for autocomplete candidates to remove non-deterministic ordering

[mgrang]

Summary

This fixes the failure in test/Driver/autocomplete.c uncovered by D39245.

[mgrang]

This is the order of options observed when the candidates are randomly shuffled:

Run 1:
cl
CL
cl1.1
CL1.1
cl1.2
CL1.2
cl2.0
CL2.0

Run 2:
CL
cl
cl1.1
CL1.1
cl1.2
CL1.2
CL2.0
cl2.0

[yamaguchi]

LGTM, thanks!

[ruiu]

Maybe we should do case-insensitive string comparison first, and if two strings are considered the same, try again in case-sensitive manner? Otherwise, even though the output is now deterministic, the output order is still dependent on the order of input strings.

[mgrang]

Added a stronger sorting predicate instead of stable sort.

[mgrang]

In D40234#929919, @ruiu wrote:

Maybe we should do case-insensitive string comparison first, and if two strings are considered the same, try again in case-sensitive manner? Otherwise, even though the output is now deterministic, the output order is still dependent on the order of input strings.

Thanks! I agree it's a better idea to use a stronger sort predicate. I have updated the patch accordingly.

[ruiu]

Perhaps, this is a bit more straightforward.

if (int X = A.compare_lower(B))
  return X < 0;
return A.compare(B) < 0;

[mgrang]

In D40234#929943, @ruiu wrote:

Perhaps, this is a bit more straightforward.

if (int X = A.compare_lower(B))
  return X < 0;
return A.compare(B) < 0;

Thanks. Done.

[ruiu]

LGTM

lib/Driver/Driver.cpp

1207

I believe that if you use clang-format, }); will be put to a separate line like this.

std::sort(SuggestedCompletions.begin(), SuggestedCompletions.end(),
          [](StringRef A, StringRef B) {
            if (int X = A.compare_lower(B))
              return X < 0;
            return A.compare(B) > 0;
          });

lib/Driver/Driver.cpp

if (PassedFlags.find(',') == StringRef::npos) {
     std::tie(Option, Arg) = PassedFlags.split(',');
     SuggestedCompletions = Opts->suggestValueCompletions(Option, Arg);
   }
 
   // Sort the autocomplete candidates so that shells print them out in a
   // deterministic order. We could sort in any way, but we chose
   // case-insensitive sorting for consistency with the -help option
   // which prints out options in the case-insensitive alphabetical order.
-  std::sort(SuggestedCompletions.begin(), SuggestedCompletions.end(),
+  std::stable_sort(SuggestedCompletions.begin(), SuggestedCompletions.end(),
             [](StringRef A, StringRef B) { return A.compare_lower(B) < 0; });
 
   llvm::outs() << llvm::join(SuggestedCompletions, "\n") << '\n';
 }
 
 bool Driver::HandleImmediateArgs(const Compilation &C) {
   // The order these options are handled in gcc is all over the place, but we
   // don't expect inconsistencies w.r.t. that to matter in practice.
 
   if (C.getArgs().hasArg(options::OPT_dumpmachine)) {
     llvm::outs() << C.getDefaultToolChain().getTripleString() << '\n';
     return false;
   }