[clangd] Introduce scoring mechanism for SignatureInformations.

[ilya-biryukov]

clangd/CodeComplete.cpp

706

Maybe use vector<ScoredSignature>, followed by std::sort at the end?

Or is there any functionality that we can reuse from the priority queue?

clangd/Quality.h

170

Maybe set some default value to avoid UB if someone forgets to set it?

172

Maybe write a direct comparison here instead of evaluate?
Having floating scores makes sense for completion, where lot's of different signals from multiple sources are taken into account and clients have to rescore on the client side.
Not so much for SignatureHelp, where we have all required information to compare the signatures is on clangd side and clients won't need to rescore.

A comparison operator should be easier to reason about, though.

[kadircet]

• Resolve discussions.

[ilya-biryukov]

Thanks! LGTM with a few NITs

clangd/CodeComplete.cpp

693

NIT: Maybe make it a function with a descriptive name, e.g. hasBetterSignature?
We could call it in a lambda, should make the code even clearer.

729

NIT: remove braces around the single-statement loop body

[kadircet]

• Rebase & Resolve discussions.
• Resolve discussions.

clangd/CodeComplete.cpp

case CodeCompletionResult::RK_Pattern:
     return CompletionItemKind::Snippet;
   }
   llvm_unreachable("Unhandled CodeCompletionResult::ResultKind.");
 }
 
 /// Get the optional chunk as a string. This function is possibly recursive.
 ///
 /// The parameter info for each parameter is appended to the Parameters.
-std::string
-getOptionalParameters(const CodeCompletionString &CCS,
-                      std::vector<ParameterInformation> &Parameters) {
+std::string getOptionalParameters(const CodeCompletionString &CCS,
+                                  std::vector<ParameterInformation> &Parameters,
+                                  SignatureQualitySignals &Signal) {
   std::string Result;
   for (const auto &Chunk : CCS) {
     switch (Chunk.Kind) {
     case CodeCompletionString::CK_Optional:
       assert(Chunk.Optional &&
              "Expected the optional code completion string to be non-null.");
-      Result += getOptionalParameters(*Chunk.Optional, Parameters);
+      Result += getOptionalParameters(*Chunk.Optional, Parameters, Signal);
       break;
     case CodeCompletionString::CK_VerticalSpace:
       break;
     case CodeCompletionString::CK_Placeholder:
       // A string that acts as a placeholder for, e.g., a function call
       // argument.
       // Intentional fallthrough here.
     case CodeCompletionString::CK_CurrentParameter: {
       // A piece of text that describes the parameter that corresponds to
       // the code-completion location within a function call, message send,
       // macro invocation, etc.
       Result += Chunk.Text;
       ParameterInformation Info;
       Info.label = Chunk.Text;
       Parameters.push_back(std::move(Info));
+      Signal.ContainsActiveParameter = true;
+      Signal.NumberOfOptionalParameters++;
       break;
     }
     default:
       Result += Chunk.Text;
       break;
     }
   }
   return Result;

 
 private:
   CodeCompleteOptions Opts;
   std::shared_ptr<GlobalCodeCompletionAllocator> CCAllocator;
   CodeCompletionTUInfo CCTUInfo;
   llvm::unique_function<void()> ResultsCallback;
 };
 
+using ScoredSignature =
+    std::pair<SignatureQualitySignals, SignatureInformation>;
+
 class SignatureHelpCollector final : public CodeCompleteConsumer {
 
 public:
   SignatureHelpCollector(const clang::CodeCompleteOptions &CodeCompleteOpts,
                          SignatureHelp &SigHelp)
       : CodeCompleteConsumer(CodeCompleteOpts, /*OutputIsBinary=*/false),
         SigHelp(SigHelp),
         Allocator(std::make_shared<clang::GlobalCodeCompletionAllocator>()),
         CCTUInfo(Allocator) {}
 
   void ProcessOverloadCandidates(Sema &S, unsigned CurrentArg,
                                  OverloadCandidate *Candidates,
                                  unsigned NumCandidates) override {
+    std::vector<ScoredSignature> ScoredSignatures;
     SigHelp.signatures.reserve(NumCandidates);
+    ScoredSignatures.reserve(NumCandidates);
     // FIXME(rwols): How can we determine the "active overload candidate"?
     // Right now the overloaded candidates seem to be provided in a "best fit"
     // order, so I'm not too worried about this.
     SigHelp.activeSignature = 0;
     assert(CurrentArg <= (unsigned)std::numeric_limits<int>::max() &&
            "too many arguments");
     SigHelp.activeParameter = static_cast<int>(CurrentArg);
     for (unsigned I = 0; I < NumCandidates; ++I) {
       const auto &Candidate = Candidates[I];
       const auto *CCS = Candidate.CreateSignatureString(
           CurrentArg, S, *Allocator, CCTUInfo, true);
       assert(CCS && "Expected the CodeCompletionString to be non-null");
       // FIXME: for headers, we need to get a comment from the index.
-      SigHelp.signatures.push_back(processOverloadCandidate(
+      ScoredSignatures.push_back(processOverloadCandidate(
           Candidate, *CCS,
           getParameterDocComment(S.getASTContext(), Candidate, CurrentArg,
                                  /*CommentsFromHeaders=*/false)));
     }
+    std::sort(ScoredSignatures.begin(), ScoredSignatures.end(),
+              [](const ScoredSignature &L, const ScoredSignature &R) {
+                // Ordering follows:
+                // - Less number of parameters is better.
+                // - Function is better than FunctionType which is better than
+                // Function Template.
+                // - High score is better.
+                // - Shorter signature is better.
+                // - Alphebatically smaller is better.
+                if (L.first.NumberOfParameters != R.first.NumberOfParameters)
+                  return L.first.NumberOfParameters <
+                         R.first.NumberOfParameters;
+                if (L.first.NumberOfOptionalParameters !=
+                    R.first.NumberOfOptionalParameters)
+                  return L.first.NumberOfOptionalParameters <
+                         R.first.NumberOfOptionalParameters;
+                if (L.first.Kind != R.first.Kind) {
+                  using OC = CodeCompleteConsumer::OverloadCandidate;
+                  switch (L.first.Kind) {
+                  case OC::CK_Function:
+                    return true;
+                  case OC::CK_FunctionType:
+                    return R.first.Kind != OC::CK_Function;
+                  case OC::CK_FunctionTemplate:
+                    return false;
+                  }
+                  llvm_unreachable("Unknown overload candidate type.");
+                }
+                if (L.second.label.size() != R.second.label.size())
+                  return L.second.label.size() < R.second.label.size();
+                return L.second.label < R.second.label;
+              });
+    for (const auto &SS : ScoredSignatures)
+      SigHelp.signatures.push_back(SS.second);
   }
 
   GlobalCodeCompletionAllocator &getAllocator() override { return *Allocator; }
 
   CodeCompletionTUInfo &getCodeCompletionTUInfo() override { return CCTUInfo; }
 
 private:
   // FIXME(ioeric): consider moving CodeCompletionString logic here to
   // CompletionString.h.
-  SignatureInformation
-  processOverloadCandidate(const OverloadCandidate &Candidate,
+  ScoredSignature processOverloadCandidate(const OverloadCandidate &Candidate,
                                            const CodeCompletionString &CCS,
                                            llvm::StringRef DocComment) const {
     SignatureInformation Result;
+    SignatureQualitySignals Signal;
     const char *ReturnType = nullptr;
 
     Result.documentation = formatDocumentation(CCS, DocComment);
+    Signal.Kind = Candidate.getKind();
 
     for (const auto &Chunk : CCS) {
       switch (Chunk.Kind) {
       case CodeCompletionString::CK_ResultType:
         // A piece of text that describes the type of an entity or,
         // for functions and methods, the return type.
         assert(!ReturnType && "Unexpected CK_ResultType");
         ReturnType = Chunk.Text;
         break;
       case CodeCompletionString::CK_Placeholder:
         // A string that acts as a placeholder for, e.g., a function call
         // argument.
         // Intentional fallthrough here.
       case CodeCompletionString::CK_CurrentParameter: {
         // A piece of text that describes the parameter that corresponds to
         // the code-completion location within a function call, message send,
         // macro invocation, etc.
         Result.label += Chunk.Text;
         ParameterInformation Info;
         Info.label = Chunk.Text;
         Result.parameters.push_back(std::move(Info));
+        Signal.NumberOfParameters++;
+        Signal.ContainsActiveParameter = true;
         break;
       }
       case CodeCompletionString::CK_Optional: {
         // The rest of the parameters are defaulted/optional.
         assert(Chunk.Optional &&
                "Expected the optional code completion string to be non-null.");
         Result.label +=
-            getOptionalParameters(*Chunk.Optional, Result.parameters);
+            getOptionalParameters(*Chunk.Optional, Result.parameters, Signal);
         break;
       }
       case CodeCompletionString::CK_VerticalSpace:
         break;
       default:
         Result.label += Chunk.Text;
         break;
       }
     }
     if (ReturnType) {
       Result.label += " -> ";
       Result.label += ReturnType;
     }
-    return Result;
+    dlog("Signal for {0}: {1}", Result, Signal);
+    return {Signal, Result};
   }
 
   SignatureHelp &SigHelp;
   std::shared_ptr<clang::GlobalCodeCompletionAllocator> Allocator;
   CodeCompletionTUInfo CCTUInfo;
 
 }; // SignatureHelpCollector
 

clangd/Quality.h

private:
   std::vector<value_type> Heap; // Min-heap, comparator is Greater.
   Compare Greater;
 };
 
 /// Returns a string that sorts in the same order as (-Score, Tiebreak), for
 /// LSP. (The highest score compares smallest so it sorts at the top).
 std::string sortText(float Score, llvm::StringRef Tiebreak = "");
 
+struct SignatureQualitySignals {
+  uint32_t NumberOfParameters = 0;
+  uint32_t NumberOfOptionalParameters = 0;
+  bool ContainsActiveParameter = false;
+  CodeCompleteConsumer::OverloadCandidate::CandidateKind Kind =
+      CodeCompleteConsumer::OverloadCandidate::CandidateKind::CK_Function;
+};
+llvm::raw_ostream &operator<<(llvm::raw_ostream &,
+                              const SignatureQualitySignals &);
+
 } // namespace clangd
 } // namespace clang
 
 #endif

clangd/Quality.cpp

std::string sortText(float Score, llvm::StringRef Name) {
   llvm::raw_string_ostream OS(S);
   write_hex(OS, encodeFloat(-Score), llvm::HexPrintStyle::Lower,
             /*Width=*/2 * sizeof(Score));
   OS << Name;
   OS.flush();
   return S;
 }
 
+llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
+                              const SignatureQualitySignals &S) {
+  OS << formatv("=== Signature Quality:\n");
+  OS << formatv("\tNumber of parameters: {0}\n", S.NumberOfParameters);
+  OS << formatv("\tNumber of optional parameters: {0}\n",
+                S.NumberOfOptionalParameters);
+  OS << formatv("\tContains active parameter: {0}\n",
+                S.ContainsActiveParameter);
+  OS << formatv("\tKind: {0}\n", S.Kind);
+  return OS;
+}
+
 } // namespace clangd
 } // namespace clang

unittests/clangd/CodeCompleteTests.cpp

for (const auto &Text : TestCodes) {
     Annotations TestCode(Text);
     auto Results = completions(Server, TestCode.code(), TestCode.point());
 
     EXPECT_EQ(Results.Completions.size(), 1u);
     EXPECT_THAT(Results.Completions.front().CompletionTokenRange, TestCode.range());
   }
 }
 
+TEST(SignatureHelpTest, OverloadsOrdering) {
+  const auto Results = signatures(R"cpp(
+    void foo(int x);
+    void foo(int x, float y);
+    void foo(float x, int y);
+    void foo(float x, float y);
+    void foo(int x, int y = 0);
+    int main() { foo(^); }
+  )cpp");
+  EXPECT_THAT(
+      Results.signatures,
+      ElementsAre(
+          Sig("foo(int x) -> void", {"int x"}),
+          Sig("foo(int x, int y = 0) -> void", {"int x", "int y = 0"}),
+          Sig("foo(float x, int y) -> void", {"float x", "int y"}),
+          Sig("foo(int x, float y) -> void", {"int x", "float y"}),
+          Sig("foo(float x, float y) -> void", {"float x", "float y"})));
+  // We always prefer the first signature.
+  EXPECT_EQ(0, Results.activeSignature);
+  EXPECT_EQ(0, Results.activeParameter);
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang