[clangd] Use Decision Forest to score code completions.

[usaxena95]

Summary

By default clangd will score a code completion item using heuristics model.

Scoring can be done by Decision Forest model by passing --ranking_model=decision_forest to
clangd.

Features omitted from the model:

• NameMatch is excluded because the final score must be multiplicative in NameMatch to allow rescoring by the editor.
• NeedsFixIts is excluded because the generating dataset that needs 'fixits' is non-trivial.

There are multiple ways (heuristics) to combine the above two features with the prediction of the DF:

• NeedsFixIts is used as is with a penalty of 0.5.

Various alternatives of combining NameMatch N and Decision forest Prediction P

• N * scale(P, 0, 1): Linearly scale the output of model to range [0, 1]
• N * a^P:
  • More natural: Prediction of each Decision Tree can be considered as a multiplicative boost (like NameMatch)
  • Ordering is independent of the absolute value of P. Order of two items is proportional to a^{difference in model prediction score}. Higher a gives higher weightage to model output as compared to NameMatch score.

Baseline MRR = 0.619
MRR for various combinations:
N * P = 0.6346, advantage%=2.5768
N * 1.1^P = 0.6600, advantage%=6.6853
N * 1.2^P = 0.6669, advantage%=7.8005
N * 1.3^P = 0.6668, advantage%=7.7795
N * 1.4^P = 0.6659, advantage%=7.6270
N * 1.5^P = 0.6646, advantage%=7.4200
N * 1.6^P = 0.6636, advantage%=7.2671
N * 1.7^P = 0.6629, advantage%=7.1450
N * 2^P = 0.6612, advantage%=6.8673
N * 2.5^P = 0.6598, advantage%=6.6491
N * 3^P = 0.6590, advantage%=6.5242
N * scaled[0, 1] = 0.6465, advantage%=4.5054

[usaxena95]

Moved DF evaluation to Quality.cpp

[adamcz]

Could you add a test that sets this flag? Perhaps we can run CodeCompletionTests.cpp twice, once with this flag, once without? Just to exercise these code paths, I think most expectations there are unordered, so it should work?

clang-tools-extra/clangd/CodeComplete.cpp

1636

Ideally we'd rename the evaluate() here, since SymbolQualitySignals is used for both heuristic and DecisionForest version, but evaluate is heuristic-specific. I think in pefect world this would be out of SymbolQualitySignals class (which would become just storage), but at least it should be renamed to evaluateUsingHeuristic().

1656

Could we make the weight of Relevance.NameMatch configurable, maybe through CodeCompletionOptions or such? I'm worried it may dominate the score too much and being able to configure this would allow us to run experiments easily.

[usaxena95]

Addressed comments.

[usaxena95]

If we just consider ranking, there are not many code paths. Most of the code paths are for gathering and creating code completion items.
In the end all the code paths end up in the addCandidate method to get scored either by heuristics or by decision forest.
So I have added 2 tests for checking sanity and exercising the code path.

clang-tools-extra/clangd/CodeComplete.cpp

1636

Right. I plan to do this but the changes for a rename would include unrelated files. So I planed to do this another patch keeping this one tractable and clean.
Let me know if you want me to do it in this one itself.

1656

Since this is multiplicative, I don't think it is possible to weigh NameMatch.
Although we can weigh the contribution of DF prediction.
Did some maths and realised that the base in pow(base, Evaluate(E)) can effectively represent the weightage given to DF Model.

[adamcz]

clang-tools-extra/clangd/CodeComplete.cpp

1636

Separate change sounds good.

clang-tools-extra/clangd/tool/ClangdMain.cpp

185

typo: Decsion

[usaxena95]

Added fixme for renaming evaluate() and fixed typo.

[adamcz]

Just noticed: typo in commit description - compeltions

clang-tools-extra/clangd/CodeComplete.h

struct CodeCompleteOptions {
   /// before they are ranked (by -Score). Thus the results are yielded in
   /// arbitrary order.
   ///
   /// This callbacks allows capturing various internal structures used by clangd
   /// during code completion. Eg: Symbol quality and relevance signals.
   std::function<void(const CodeCompletion &, const SymbolQualitySignals &,
                      const SymbolRelevanceSignals &, float Score)>
       RecordCCResult;
+
+  /// Model to use for ranking code completion candidates.
+  enum CodeCompletionRankingModel {
+    Heuristic,
+    DecisionForest,
+  } RankingModel = Heuristic;
 };
 
 // Semi-structured representation of a code-complete suggestion for our C++ API.
 // We don't use the LSP structures here (unlike most features) as we want
 // to expose more data to allow for more precise testing and evaluation.
 struct CodeCompletion {
   // The unqualified name of the symbol or other completion item.
   std::string Name;

clang-tools-extra/clangd/CodeComplete.cpp

 // it's purely AST-based, and there are few candidates.
 //
 //===----------------------------------------------------------------------===//
 
 #include "CodeComplete.h"
 #include "AST.h"
 #include "CodeCompletionStrings.h"
 #include "Compiler.h"
+#include "CompletionModel.h"
 #include "Diagnostics.h"
 #include "ExpectedTypes.h"
 #include "FileDistance.h"
 #include "FuzzyMatch.h"
 #include "Headers.h"
 #include "Hover.h"
 #include "Preamble.h"
 #include "Protocol.h"
if (((C.SemaResult &&
           C.SemaResult->Kind == CodeCompletionResult::RK_Macro) ||
          (C.IndexResult &&
           C.IndexResult->SymInfo.Kind == index::SymbolKind::Macro)) &&
         !C.Name.startswith_lower(Filter->pattern()))
       return None;
     return Filter->match(C.Name);
   }
 
+  CodeCompletion::Scores
+  evaluateHeuristic(const SymbolQualitySignals &Quality,
+                    const SymbolRelevanceSignals &Relevance) {
+    CodeCompletion::Scores Scores;
+    Scores.Quality = Quality.evaluate();
+    Scores.Relevance = Relevance.evaluate();
+    Scores.Total = evaluateSymbolAndRelevance(Scores.Quality, Scores.Relevance);
+    // NameMatch is in fact a multiplier on total score, so rescoring is sound.
+    Scores.ExcludingName = Relevance.NameMatch
+                               ? Scores.Total / Relevance.NameMatch
+                               : Scores.Quality;
+    return Scores;
+  }
+
+  CodeCompletion::Scores
+  evaluateDecisionForest(const SymbolQualitySignals &Quality,
+                         const SymbolRelevanceSignals &Relevance) {
+    Example E;
+    E.setIsDeprecated(Quality.Deprecated);
+    E.setIsReservedName(Quality.ReservedName);
+    E.setIsImplementationDetail(Quality.ImplementationDetail);
+    E.setNumReferences(Quality.References);
+    E.setSymbolCategory(Quality.Category);
+
+    SymbolRelevanceSignals::DerivedSignals Derived =
+        Relevance.calculateDerivedSignals();
+    // FIXME(usx): Move FilterLength to RelevanceSignals.
+    E.setFilterLength(HeuristicPrefix.Name.size());
+    E.setIsNameInContext(Derived.NameMatchesContext);
+    E.setIsForbidden(Relevance.Forbidden);
+    E.setIsInBaseClass(Relevance.InBaseClass);
+    E.setFileProximityDistance(Derived.FileProximityDistance);
+    E.setSemaFileProximityScore(Relevance.SemaFileProximityScore);
+    E.setSymbolScopeDistance(Derived.ScopeProximityDistance);
+    E.setSemaSaysInScope(Relevance.SemaSaysInScope);
+    E.setScope(Relevance.Scope);
+    E.setContextKind(Relevance.Context);
+    E.setIsInstanceMember(Relevance.IsInstanceMember);
+    E.setHadContextType(Relevance.HadContextType);
+    E.setHadSymbolType(Relevance.HadSymbolType);
+    E.setTypeMatchesPreferred(Relevance.TypeMatchesPreferred);
+
+    CodeCompletion::Scores Scores;
+    Scores.ExcludingName = exp(Evaluate(E));
+    if (Relevance.NeedsFixIts)
+      Scores.ExcludingName *= 0.5;
+    Scores.Total = Relevance.NameMatch * Scores.ExcludingName;
+    // DO NOT SUBMIT: Remove before submitting.
+    log("{0} = {1} * {2}, {3}\t{4}", Scores.Total, Scores.ExcludingName,
+        Relevance.NameMatch, Relevance.SymbolScope, Relevance.Name);
+
+    return Scores;
+  }
+
+  CodeCompletion::Scores
+  evaluateCompletion(const SymbolQualitySignals &Quality,
+                     const SymbolRelevanceSignals &Relevance) {
+    using RM = CodeCompleteOptions::CodeCompletionRankingModel;
+    switch (Opts.RankingModel) {
+    case RM::Heuristic:
+      return evaluateHeuristic(Quality, Relevance);
+    case RM::DecisionForest:
+      return evaluateDecisionForest(Quality, Relevance);
+    }
+    llvm_unreachable("Unhandled CodeCompletion ranking model.");
+  }
+
   // Scores a candidate and adds it to the TopN structure.
   void addCandidate(TopN<ScoredBundle, ScoredBundleGreater> &Candidates,
                     CompletionCandidate::Bundle Bundle) {
     SymbolQualitySignals Quality;
     SymbolRelevanceSignals Relevance;
     Relevance.Context = CCContextKind;
     Relevance.Name = Bundle.front().Name;
     Relevance.Query = SymbolRelevanceSignals::CodeComplete;
for (const auto &Candidate : Bundle) {
       }
       if (Candidate.IdentifierResult) {
         Quality.References = Candidate.IdentifierResult->References;
         Relevance.Scope = SymbolRelevanceSignals::FileScope;
         Origin |= SymbolOrigin::Identifier;
       }
     }
 
-    CodeCompletion::Scores Scores;
-    Scores.Quality = Quality.evaluate();
-    Scores.Relevance = Relevance.evaluate();
-    Scores.Total = evaluateSymbolAndRelevance(Scores.Quality, Scores.Relevance);
-    // NameMatch is in fact a multiplier on total score, so rescoring is sound.
-    Scores.ExcludingName = Relevance.NameMatch
-                               ? Scores.Total / Relevance.NameMatch
-                               : Scores.Quality;
-
+    CodeCompletion::Scores Scores = evaluateCompletion(Quality, Relevance);
     if (Opts.RecordCCResult)
       Opts.RecordCCResult(toCodeCompletion(Bundle), Quality, Relevance,
                           Scores.Total);
 
     dlog("CodeComplete: {0} ({1}) = {2}\n{3}{4}\n", First.Name,
          llvm::to_string(Origin), Scores.Total, llvm::to_string(Quality),
          llvm::to_string(Relevance));
 

clang-tools-extra/clangd/tool/ClangdMain.cpp

values(clEnumValN(CodeCompleteOptions::AlwaysParse, "always",
                       "Use text-based completion if the parser "
                       "is not ready"),
            clEnumValN(CodeCompleteOptions::NeverParse, "never",
                       "Always used text-based completion")),
     init(CodeCompleteOptions().RunParser),
     Hidden,
 };
 
+opt<CodeCompleteOptions::CodeCompletionRankingModel> RankingModel{
+    "ranking-model",
+    cat(Features),
+    desc("Model to use to rank code-completion items"),
+    values(clEnumValN(CodeCompleteOptions::Heuristic, "heuristic",
+                      "Use hueristics to rank code completion items"),
+           clEnumValN(CodeCompleteOptions::DecisionForest, "df",
+                      "Use Decision Forest model to rank completion items")),
+    init(CodeCompleteOptions().RankingModel),
+    Hidden,
+};
+
 // FIXME: also support "plain" style where signatures are always omitted.
 enum CompletionStyleFlag { Detailed, Bundled };
 opt<CompletionStyleFlag> CompletionStyle{
     "completion-style",
     cat(Features),
     desc("Granularity of code completion suggestions"),
     values(clEnumValN(Detailed, "detailed",
                       "One completion item for each semantically distinct "
                       "completion, with full type information"),
            clEnumValN(Bundled, "bundled",
                       "Similar completion items (e.g. function overloads) are "
                       "combined. Type information shown where possible")),
#endif
   if (!HeaderInsertionDecorators) {
     CCOpts.IncludeIndicator.Insert.clear();
     CCOpts.IncludeIndicator.NoInsert.clear();
   }
   CCOpts.SpeculativeIndexRequest = Opts.StaticIndex;
   CCOpts.EnableFunctionArgSnippets = EnableFunctionArgSnippets;
   CCOpts.AllScopes = AllScopesCompletion;
   CCOpts.RunParser = CodeCompletionParse;
+  CCOpts.RankingModel = RankingModel;
 
   RealThreadsafeFS TFS;
   std::vector<std::unique_ptr<config::Provider>> ProviderStack;
   std::unique_ptr<config::Provider> Config;
   if (EnableConfig) {
     ProviderStack.push_back(
         config::Provider::fromAncestorRelativeYAMLFiles(".clangd", TFS));
     llvm::SmallString<256> UserConfig;

clang-tools-extra/clangd/unittests/CodeCompleteTests.cpp

 #include "TestTU.h"
 #include "index/Index.h"
 #include "index/MemIndex.h"
 #include "support/Threading.h"
 #include "clang/Sema/CodeCompleteConsumer.h"
 #include "clang/Tooling/CompilationDatabase.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/Path.h"
+#include "llvm/Support/Timer.h"
+#include "llvm/Support/raw_ostream.h"
 #include "llvm/Testing/Support/Annotations.h"
 #include "llvm/Testing/Support/Error.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include <condition_variable>
 #include <functional>
 #include <mutex>
+#include <sstream>
 #include <vector>
 
 namespace clang {
 namespace clangd {
 
 namespace {
 using ::llvm::Failed;
 using ::testing::AllOf;
auto Results = completions(
           void f() { ::ns::^ }
       )cpp",
       {cls("ns::XYZ")});
   EXPECT_THAT(Results.Completions,
               AllOf(Has("XYZ", CompletionItemKind::Class),
                     Has("bar", CompletionItemKind::Function)));
 }
 
+/*
+TEST(CompletionTest, DO_NOT_SUBMIT_SpeedTestForReviewOnly) {
+
+  auto randFunction = []() {
+    std::stringstream ss;
+    ss << "void ";
+    for (int i = 0; i < 10; ++i)
+      ss << char(rand() % 3 == 0 ? 'a' + rand() % 3 : 'A' + rand() % 3);
+    ss << "();\n";
+    return ss.str();
+  };
+  int Trials = 1;
+  std::vector<Symbol> IndexedResults;
+  IndexedResults.push_back(cls({"ns::ABCDabc"}));
+  IndexedResults.push_back(cls({"ns::abcABC"}));
+
+  std::string code = R"cpp(
+      namespace ns {
+        void abc();
+    )cpp";
+  for (int i = 0; i < 50; ++i)
+    code += randFunction();
+  code += "namepsace ns2 {\n";
+  for (int i = 0; i < 50; ++i)
+    code += randFunction();
+  code += "} //namespace ns2\n";
+  code += R"cpp(} // namespace ns
+      void f() { abc^ }
+   )cpp";
+  llvm::errs() << code << "\n";
+
+  CodeCompleteOptions Opts;
+  Opts.AllScopes = true;
+
+  llvm::Timer DF("DF", "Decision Forest");
+  llvm::Timer Heuristic("Heuristic", "Heuristic ranking.");
+
+  Opts.RankingModel = CodeCompleteOptions::DecisionForest;
+  DF.startTimer();
+  auto DFCompletions = completions(code, IndexedResults, Opts);
+  for (int i = 0; i < Trials; ++i)
+    completions(code, IndexedResults, Opts);
+  DF.stopTimer();
+
+  Opts.RankingModel = CodeCompleteOptions::Heuristic;
+  Heuristic.startTimer();
+  auto HeuristicCompletions = completions(code, IndexedResults, Opts);
+  for (int i = 0; i < Trials; ++i)
+    completions(code, IndexedResults, Opts);
+  Heuristic.stopTimer();
+
+  for (const auto &M : {DFCompletions, HeuristicCompletions}) {
+    auto S = M.Completions;
+    std::sort(S.begin(), S.end(),
+              [&](const CodeCompletion &a, const CodeCompletion &b) {
+                return a.Score.Total > b.Score.Total ||
+                       (a.Score.Total == b.Score.Total && a.Name < b.Name);
+              });
+    int r = 0;
+    for (const auto &C : S) {
+      llvm::errs() << r++ << ".\t" << C.Scope << " " << C.Name << " "
+                   << C.Score.Total << " / " << C.Score.ExcludingName
+                   << "\t\tNameMatch = "
+                   << C.Score.Total / C.Score.ExcludingName << "\n";
+    }
+    llvm::errs() << "\n\n";
+  }
+  EXPECT_LT(int(DFCompletions.Completions.size()), 0LL);
+}
+*/
 TEST(CompletionTest, SemaIndexMerge) {
   auto Results = completions(
       R"cpp(
           namespace ns { int local; void both(); }
           void f() { ::ns::^ }
       )cpp",
       {func("ns::both"), cls("ns::Index")});
   // We get results from both index and sema, with no duplicates.