[lldb] Make order of completions for expressions deterministic and sorted by…

Authored by teemperor on May 27 2020, 10:21 AM.


[lldb] Make order of completions for expressions deterministic and sorted by Clang's priority values.


It turns out that the order in which we provide completions for expressions is
nondeterministic. This leads to confusing user experience and also breaks the
reproducer tests (as two LLDB tests can go out of sync due to the
non-determinism in the completion lists)

The reason for the non-determinism is that the CompletionConsumer informs us
about decls in the order in which it finds declarations in the lookup store of
the DeclContexts it visits (mainly this snippet in SemaLookup.cpp):

// Enumerate all of the results in this context.
for (DeclContextLookupResult R :
     Load ? Ctx->lookups()
          : Ctx->noload_lookups(/*PreserveInternalState=*/false)) {

This storage of the lookup is sorted by pointer values (see the hash of
DeclarationName) and can therefore be non-deterministic. The LLDB code
completion consumer that receives these calls originally expected that the order
of declarations is defined by Clang, but it seems the API expects the client to
provide an order to the completions.

This patch fixes the issue as follows:

  • We sort the completions we get from Clang alphabetically and also by the

priority value we get from Clang (with priority value sorting having precedence
over the alphabetical sorting)

  • We make all the functions/variables that touch a completion before the sorting

const-qualified. The idea is that this should prevent that we never have
observable side-effect from touching these declarations in a non-deterministic
order (e.g., we don't try to complete the type by accident).

This way we behave like the other parts of Clang which also sort the results by
some deterministic value (usually the name or something computed from a name,
e.g., edit distance to a given string).

We most likely also need to fix the Clang code to make the loop I listed above
deterministic to prevent these issues in the future (tracked in rdar://63442513
). This wouldn't replace the functionality provided in this patch though as we
would still need the priority and overall alphabetical sorting.

Note: I had to increase the lldb-vscode completion limit to 100 as the tests
look for strings that aren't in the first 50 results anymore due to variable
names starting with letters like 'v' (which are now always shown much further
down in the list due to the alphabetical sorting).

Fixes rdar://63200995

Reviewers: JDevlieghere, clayborg

Reviewed By: JDevlieghere

Subscribers: mgrang, abidh

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