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

[teemperor]

Summary

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

[teemperor]

lldb/tools/lldb-vscode/lldb-vscode.cpp

970

@clayborg Can you check that this doesn't break any VSCode functionality? I guess the frontend should be able to handle lists of 100 items.

[JDevlieghere]

lldb/source/Plugins/ExpressionParser/Clang/ClangExpressionParser.cpp

759

Any reason you didn't make this the regular comparison operator for CompletionWithPriority?

787

Doing this stuff in the destructor seems a bit magical. Is there no better place for this?

900

Can this be a range-based for loop?

[teemperor]

• Moved code out of destructor. Also moved the CompletionRequest parameter to the place where we actually need it.
• Moved completion sorting code to operator<.

[teemperor]

• Removed some unrelated whitespace change.

lldb/packages/Python/lldbsuite/test/lldbtest.py

def match(
             if matched:
                 break
 
         self.assertTrue(matched if matching else not matched,
                         msg if msg else EXP_MSG(str, output, exe))
 
         return match_object
 
-    def check_completion_with_desc(self, str_input, match_desc_pairs):
+    def check_completion_with_desc(self, str_input, match_desc_pairs, enforce_order=False):
+        """
+        Checks that when the given input is completed at the given list of
+        completions and descriptions is returned.
+        :param str_input: The input that should be completed. The completion happens at the end of the string.
+        :param match_desc_pairs: A list of pairs that indicate what completions have to be in the list of
+                                 completions returned by LLDB. The first element of the pair is the completion
+                                 string that LLDB should generate and the second element the description.
+        :param enforce_order: True iff the order in which the completions are returned by LLDB
+                              should match the order of the match_desc_pairs pairs.
+        """
         interp = self.dbg.GetCommandInterpreter()
         match_strings = lldb.SBStringList()
         description_strings = lldb.SBStringList()
         num_matches = interp.HandleCompletionWithDescriptions(str_input, len(str_input), 0, -1, match_strings, description_strings)
         self.assertEqual(len(description_strings), len(match_strings))
 
+        # The index of the last matched description in description_strings or
+        # -1 if no description has been matched yet.
+        last_found_index = -1
+        out_of_order_errors = ""
         missing_pairs = []
         for pair in match_desc_pairs:
             found_pair = False
             for i in range(num_matches + 1):
                 match_candidate = match_strings.GetStringAtIndex(i)
                 description_candidate = description_strings.GetStringAtIndex(i)
                 if match_candidate == pair[0] and description_candidate == pair[1]:
                     found_pair = True
+                    if enforce_order and last_found_index > i:
+                        new_err = ("Found completion " + pair[0] + " at index " +
+                                  str(i) + " in returned completion list but " +
+                                  "should have been after completion " +
+                                  match_strings.GetStringAtIndex(last_found_index) +
+                                  " (index:" + str(last_found_index) + ")\n")
+                        out_of_order_errors += new_err
+                    last_found_index = i
                     break
             if not found_pair:
                 missing_pairs.append(pair)
 
+        error_msg = ""
+        got_failure = False
         if len(missing_pairs):
-            error_msg = "Missing pairs:\n"
+            got_failure = True
+            error_msg += "Missing pairs:\n"
             for pair in missing_pairs:
                 error_msg += " [" + pair[0] + ":" + pair[1] + "]\n"
+        if len(out_of_order_errors):
+            got_failure = True
+            error_msg += out_of_order_errors
+        if got_failure:
             error_msg += "Got the following " + str(num_matches) + " completions back:\n"
             for i in range(num_matches + 1):
                 match_candidate = match_strings.GetStringAtIndex(i)
                 description_candidate = description_strings.GetStringAtIndex(i)
-                error_msg += "[" + match_candidate + ":" + description_candidate + "]\n"
-            self.assertEqual(0, len(missing_pairs), error_msg)
+                error_msg += "[" + match_candidate + ":" + description_candidate + "] index " + str(i) + "\n"
+            self.assertFalse(got_failure, error_msg)
 
     def complete_exactly(self, str_input, patterns):
         self.complete_from_to(str_input, patterns, True)
 
     def complete_from_to(self, str_input, patterns, turn_off_re_match=False):
         """Test that the completion mechanism completes str_input to patterns,
         where patterns could be a pattern-string or a list of pattern-strings"""
         # Patterns should not be None in order to proceed.

lldb/source/Plugins/ExpressionParser/Clang/ClangExpressionParser.cpp

 /// A code completion consumer for the clang Sema that is responsible for
 /// creating the completion suggestions when a user requests completion
 /// of an incomplete `expr` invocation.
 class CodeComplete : public CodeCompleteConsumer {
   CodeCompletionTUInfo m_info;
 
   std::string m_expr;
   unsigned m_position = 0;
-  CompletionRequest &m_request;
   /// The printing policy we use when printing declarations for our completion
   /// descriptions.
   clang::PrintingPolicy m_desc_policy;
 
+  struct CompletionWithPriority {
+    CompletionResult::Completion completion;
+    /// See CodeCompletionResult::Priority;
+    unsigned Priority;
+
+    /// Establishes a deterministic order in a list of CompletionWithPriority.
+    /// The order returned here is the order in which the completions are
+    /// displayed to the user.
+    bool operator<(const CompletionWithPriority &o) const {
+      // High priority results should come first.
+      if (Priority != o.Priority)
+        return Priority > o.Priority;
+
+      // Identical priority, so just make sure it's a deterministic order.
+      return completion.GetUniqueKey() < o.completion.GetUniqueKey();
+    }
+  };
+
+  /// The stored completions.
+  /// Warning: These are in a non-deterministic order until they are sorted
+  /// and returned back to the caller.
+  std::vector<CompletionWithPriority> m_completions;
+
   /// Returns true if the given character can be used in an identifier.
   /// This also returns true for numbers because for completion we usually
   /// just iterate backwards over iterators.
   ///
   /// Note: lldb uses '$' in its internal identifiers, so we also allow this.
   static bool IsIdChar(char c) {
     return c == '_' || std::isalnum(c) || c == '$';
   }
 
   /// Returns true if the given character is used to separate arguments
   /// in the command line of lldb.
   static bool IsTokenSeparator(char c) { return c == ' ' || c == '\t'; }
 
   /// Drops all tokens in front of the expression that are unrelated for
   /// the completion of the cmd line. 'unrelated' means here that the token
   /// is not interested for the lldb completion API result.
-  StringRef dropUnrelatedFrontTokens(StringRef cmd) {
+  StringRef dropUnrelatedFrontTokens(StringRef cmd) const {
     if (cmd.empty())
       return cmd;
 
     // If we are at the start of a word, then all tokens are unrelated to
     // the current completion logic.
     if (IsTokenSeparator(cmd.back()))
       return StringRef();
 
     // Remove all previous tokens from the string as they are unrelated
     // to completing the current token.
     StringRef to_remove = cmd;
     while (!to_remove.empty() && !IsTokenSeparator(to_remove.back())) {
       to_remove = to_remove.drop_back();
     }
     cmd = cmd.drop_front(to_remove.size());
 
     return cmd;
   }
 
   /// Removes the last identifier token from the given cmd line.
-  StringRef removeLastToken(StringRef cmd) {
+  StringRef removeLastToken(StringRef cmd) const {
     while (!cmd.empty() && IsIdChar(cmd.back())) {
       cmd = cmd.drop_back();
     }
     return cmd;
   }
 
   /// Attempts to merge the given completion from the given position into the
   /// existing command. Returns the completion string that can be returned to
   /// the lldb completion API.
   std::string mergeCompletion(StringRef existing, unsigned pos,
-                              StringRef completion) {
+                              StringRef completion) const {
     StringRef existing_command = existing.substr(0, pos);
     // We rewrite the last token with the completion, so let's drop that
     // token from the command.
     existing_command = removeLastToken(existing_command);
     // We also should remove all previous tokens from the command as they
     // would otherwise be added to the completion that already has the
     // completion.
     existing_command = dropUnrelatedFrontTokens(existing_command);
     return existing_command.str() + completion.str();
   }
 
 public:
   /// Constructs a CodeComplete consumer that can be attached to a Sema.
   ///
   /// \param[out] expr
   ///    The whole expression string that we are currently parsing. This
   ///    string needs to be equal to the input the user typed, and NOT the
   ///    final code that Clang is parsing.
   /// \param[out] position
   ///    The character position of the user cursor in the `expr` parameter.
   ///
-  CodeComplete(CompletionRequest &request, clang::LangOptions ops,
-               std::string expr, unsigned position)
+  CodeComplete(clang::LangOptions ops, std::string expr, unsigned position)
       : CodeCompleteConsumer(CodeCompleteOptions()),
         m_info(std::make_shared<GlobalCodeCompletionAllocator>()), m_expr(expr),
-        m_position(position), m_request(request), m_desc_policy(ops) {
+        m_position(position), m_desc_policy(ops) {
 
     // Ensure that the printing policy is producing a description that is as
     // short as possible.
     m_desc_policy.SuppressScope = true;
     m_desc_policy.SuppressTagKeyword = true;
     m_desc_policy.FullyQualifiedName = false;
     m_desc_policy.TerseOutput = true;
     m_desc_policy.IncludeNewlines = false;
     m_desc_policy.UseVoidForZeroParams = false;
     m_desc_policy.Bool = true;
   }
 
-  /// Deregisters and destroys this code-completion consumer.
-  ~CodeComplete() override {}
-
   /// \name Code-completion filtering
   /// Check if the result should be filtered out.
   bool isResultFilteredOut(StringRef Filter,
                            CodeCompletionResult Result) override {
     // This code is mostly copied from CodeCompleteConsumer.
     switch (Result.Kind) {
     case CodeCompletionResult::RK_Declaration:
       return !(
           Result.Declaration->getIdentifier() &&
           Result.Declaration->getIdentifier()->getName().startswith(Filter));
     case CodeCompletionResult::RK_Keyword:
       return !StringRef(Result.Keyword).startswith(Filter);
     case CodeCompletionResult::RK_Macro:
       return !Result.Macro->getName().startswith(Filter);
     case CodeCompletionResult::RK_Pattern:
       return !StringRef(Result.Pattern->getAsString()).startswith(Filter);
     }
     // If we trigger this assert or the above switch yields a warning, then
     // CodeCompletionResult has been enhanced with more kinds of completion
     // results. Expand the switch above in this case.
     assert(false && "Unknown completion result type?");
     // If we reach this, then we should just ignore whatever kind of unknown
     // result we got back. We probably can't turn it into any kind of useful
     // completion suggestion with the existing code.
     return true;
   }
 
-  /// \name Code-completion callbacks
-  /// Process the finalized code-completion results.
-  void ProcessCodeCompleteResults(Sema &SemaRef, CodeCompletionContext Context,
-                                  CodeCompletionResult *Results,
-                                  unsigned NumResults) override {
-
-    // The Sema put the incomplete token we try to complete in here during
-    // lexing, so we need to retrieve it here to know what we are completing.
-    StringRef Filter = SemaRef.getPreprocessor().getCodeCompletionFilter();
-
-    // Iterate over all the results. Filter out results we don't want and
-    // process the rest.
-    for (unsigned I = 0; I != NumResults; ++I) {
-      // Filter the results with the information from the Sema.
-      if (!Filter.empty() && isResultFilteredOut(Filter, Results[I]))
-        continue;
-
-      CodeCompletionResult &R = Results[I];
-      std::string ToInsert;
-      std::string Description;
-      // Handle the different completion kinds that come from the Sema.
-      switch (R.Kind) {
-      case CodeCompletionResult::RK_Declaration: {
-        const NamedDecl *D = R.Declaration;
-        ToInsert = R.Declaration->getNameAsString();
-        // If we have a function decl that has no arguments we want to
-        // complete the empty parantheses for the user. If the function has
-        // arguments, we at least complete the opening bracket.
-        if (const FunctionDecl *F = dyn_cast<FunctionDecl>(D)) {
-          if (F->getNumParams() == 0)
-            ToInsert += "()";
-          else
-            ToInsert += "(";
-          raw_string_ostream OS(Description);
-          F->print(OS, m_desc_policy, false);
-          OS.flush();
-        } else if (const VarDecl *V = dyn_cast<VarDecl>(D)) {
-          Description = V->getType().getAsString(m_desc_policy);
-        } else if (const FieldDecl *F = dyn_cast<FieldDecl>(D)) {
-          Description = F->getType().getAsString(m_desc_policy);
-        } else if (const NamespaceDecl *N = dyn_cast<NamespaceDecl>(D)) {
-          // If we try to complete a namespace, then we can directly append
-          // the '::'.
-          if (!N->isAnonymousNamespace())
-            ToInsert += "::";
-        }
-        break;
-      }
-      case CodeCompletionResult::RK_Keyword:
-        ToInsert = R.Keyword;
-        break;
-      case CodeCompletionResult::RK_Macro:
-        ToInsert = R.Macro->getName().str();
-        break;
-      case CodeCompletionResult::RK_Pattern:
-        ToInsert = R.Pattern->getTypedText();
-        break;
-      }
-      // At this point all information is in the ToInsert string.
-
-      // We also filter some internal lldb identifiers here. The user
-      // shouldn't see these.
-      if (StringRef(ToInsert).startswith("$__lldb_"))
-        continue;
-      if (!ToInsert.empty()) {
-        // Merge the suggested Token into the existing command line to comply
-        // with the kind of result the lldb API expects.
-        std::string CompletionSuggestion =
-            mergeCompletion(m_expr, m_position, ToInsert);
-        m_request.AddCompletion(CompletionSuggestion, Description);
-      }
+private:
+  /// Generate the completion strings for the given CodeCompletionResult.
+  /// Note that this function has to process results that could come in
+  /// non-deterministic order, so this function should have no side effects.
+  /// To make this easier to enforce, this function and all its parameters
+  /// should always be const-qualified.
+  /// \return Returns llvm::None if no completion should be provided for the
+  ///         given CodeCompletionResult.
+  llvm::Optional<CompletionWithPriority>
+  getCompletionForResult(const CodeCompletionResult &R) const {
+    if (llvm::StringRef(ToInsert).startswith("$__lldb_"))
+      return llvm::None;
+    if (ToInsert.empty())
+      return llvm::None;
+
+    CompletionResult::Completion completion(CompletionSuggestion, Description,
+                                            CompletionMode::Normal);
+    return {{completion, R.Priority}};
+
+public:
+  /// Adds the completions to the given CompletionRequest.
+  void GetCompletions(CompletionRequest &request) {
+    // Bring m_completions into a deterministic order and pass it on to the
+    // CompletionRequest.
+    llvm::sort(m_completions);
+
+    for (const CompletionWithPriority &C : m_completions)
+      request.AddCompletion(C.completion.GetCompletion(),
+                            C.completion.GetDescription(),
+                            C.completion.GetMode());
+  }
+
+  /// \name Code-completion callbacks
+  /// Process the finalized code-completion results.
+  void ProcessCodeCompleteResults(Sema &SemaRef, CodeCompletionContext Context,
+                                  CodeCompletionResult *Results,
+                                  unsigned NumResults) override {
+
+    // The Sema put the incomplete token we try to complete in here during
+    // lexing, so we need to retrieve it here to know what we are completing.
+    StringRef Filter = SemaRef.getPreprocessor().getCodeCompletionFilter();
+
+    // Iterate over all the results. Filter out results we don't want and
+    // process the rest.
+    for (unsigned I = 0; I != NumResults; ++I) {
+      // Filter the results with the information from the Sema.
+      if (!Filter.empty() && isResultFilteredOut(Filter, Results[I]))
+        continue;
+
+      CodeCompletionResult &R = Results[I];
+      llvm::Optional<CompletionWithPriority> CompletionAndPriority =
+          getCompletionForResult(R);
+      if (!CompletionAndPriority)
+        continue;
+      m_completions.push_back(*CompletionAndPriority);
     }
   }
 
   /// \param S the semantic-analyzer object for which code-completion is being
   /// done.
   ///
   /// \param CurrentArg the index of the current argument.
   ///
bool ClangExpressionParser::Complete(CompletionRequest &request, unsigned line,
   DiagnosticManager mgr;
   // We need the raw user expression here because that's what the CodeComplete
   // class uses to provide completion suggestions.
   // However, the `Text` method only gives us the transformed expression here.
   // To actually get the raw user input here, we have to cast our expression to
   // the LLVMUserExpression which exposes the right API. This should never fail
   // as we always have a ClangUserExpression whenever we call this.
   ClangUserExpression *llvm_expr = cast<ClangUserExpression>(&m_expr);
-  CodeComplete CC(request, m_compiler->getLangOpts(), llvm_expr->GetUserText(),
+  CodeComplete CC(m_compiler->getLangOpts(), llvm_expr->GetUserText(),
                   typed_pos);
   // We don't need a code generator for parsing.
   m_code_generator.reset();
   // Start parsing the expression with our custom code completion consumer.
   ParseInternal(mgr, &CC, line, pos);
+  CC.GetCompletions(request);
   return true;
 }
 
 unsigned ClangExpressionParser::Parse(DiagnosticManager &diagnostic_manager) {
   return ParseInternal(diagnostic_manager);
 }
 
 unsigned

lldb/test/API/commands/expression/completion/TestExprCompletion.py

def test_expr_completion_with_descriptions(self):
         self.main_source = "main.cpp"
         self.main_source_spec = lldb.SBFileSpec(self.main_source)
         self.dbg.CreateTarget(self.getBuildArtifact("a.out"))
 
         (target, process, thread, bkpt) = lldbutil.run_to_source_breakpoint(self,
                                           '// Break here', self.main_source_spec)
 
         self.check_completion_with_desc("expr ", [
-            # VarDecls have their type as description.
-            ["some_expr", "Expr &"],
             # builtin types have no description.
             ["int", ""],
-            ["float", ""]
-        ])
+            ["float", ""],
+            # VarDecls have their type as description.
+            ["some_expr", "Expr &"],
+        ], enforce_order = True)
         self.check_completion_with_desc("expr some_expr.", [
             # Functions have their signature as description.
-            ["some_expr.Self()", "Expr &Self()"],
+            ["some_expr.~Expr()", "inline ~Expr()"],
             ["some_expr.operator=(", "inline Expr &operator=(const Expr &)"],
-            ["some_expr.FooNumbersBar1()", "int FooNumbersBar1()"],
+            # FieldDecls have their type as description.
+            ["some_expr.MemberVariableBar", "int"],
             ["some_expr.StaticMemberMethodBar()", "static int StaticMemberMethodBar()"],
-            ["some_expr.FooWithArgsBar(", "int FooWithArgsBar(int)"],
+            ["some_expr.Self()", "Expr &Self()"],
             ["some_expr.FooNoArgsBar()", "int FooNoArgsBar()"],
+            ["some_expr.FooWithArgsBar(", "int FooWithArgsBar(int)"],
+            ["some_expr.FooNumbersBar1()", "int FooNumbersBar1()"],
             ["some_expr.FooUnderscoreBar_()", "int FooUnderscoreBar_()"],
             ["some_expr.FooWithMultipleArgsBar(", "int FooWithMultipleArgsBar(int, int)"],
-            ["some_expr.~Expr()", "inline ~Expr()"],
-            # FieldDecls have their type as description.
-            ["some_expr.MemberVariableBar", "int"],
-        ])
+        ], enforce_order = True)
 
     def assume_no_completions(self, str_input, cursor_pos = None):
         interp = self.dbg.GetCommandInterpreter()
         match_strings = lldb.SBStringList()
         if cursor_pos is None:
           cursor_pos = len(str_input)
         num_matches = interp.HandleCompletion(str_input, cursor_pos, 0, -1, match_strings)
 

lldb/tools/lldb-vscode/lldb-vscode.cpp

if (!text.empty() && text[0] == '`') {
     actual_column += 2;
   }
   lldb::SBStringList matches;
   lldb::SBStringList descriptions;
   g_vsc.debugger.GetCommandInterpreter().HandleCompletionWithDescriptions(
     text.c_str(),
     actual_column,
     0, -1, matches, descriptions);
-  size_t count = std::min((uint32_t)50, matches.GetSize());
+  size_t count = std::min((uint32_t)100, matches.GetSize());
   targets.reserve(count);
   for (size_t i = 0; i < count; i++) {
     std::string match = matches.GetStringAtIndex(i);
     std::string description = descriptions.GetStringAtIndex(i);
 
     llvm::json::Object item;
 
     llvm::StringRef match_ref = match;