Page MenuHomePhabricator

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

Authored by mgrang on Nov 19 2017, 9:10 PM.

Diff Detail

Repository
rL LLVM

Event Timeline

mgrang created this revision.Nov 19 2017, 9:10 PM

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 accepted this revision.Nov 19 2017, 9:22 PM

LGTM, thanks!

This revision is now accepted and ready to land.Nov 19 2017, 9:22 PM
ruiu edited edge metadata.Nov 19 2017, 10:03 PM

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 updated this revision to Diff 123538.Nov 19 2017, 10:19 PM
mgrang retitled this revision from [AutoComplete] Stable sort autocomplete candidates to remove non-deterministic ordering to [AutoComplete] Use stronger sort predicate for autocomplete candidates to remove non-deterministic ordering.

Added a stronger sorting predicate instead of stable sort.

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 added a comment.Nov 19 2017, 10:25 PM

Perhaps, this is a bit more straightforward.

if (int X = A.compare_lower(B))
  return X < 0;
return A.compare(B) < 0;
mgrang updated this revision to Diff 123546.Nov 20 2017, 12:10 AM
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 accepted this revision.Nov 20 2017, 12:16 AM

LGTM

lib/Driver/Driver.cpp
1204 ↗(On Diff #123546)

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;
          });
This revision was automatically updated to reflect the committed changes.