[clangd] Add type boosting in code completion

[ilya-biryukov]

Ranking-related code should be moved to Quality.cpp

[ilya-biryukov]

• Rebase and update wrt to dependent changes

[sammccall]

clangd/Quality.cpp

341

is 2 really enough?

clangd/Quality.h

94

you've inserted in the middle of the file proximity stuff :-)

94

Generally we'd put both context/symbol types as the signal here, rather than just whether they match, unless it's prohibitive. They'd get populated manually, and by merge() overloads, respectively.

[ilya-biryukov]

• Increase the multiplier
• Move the member out of the file proximity group

clangd/Quality.cpp

341

Changed to 5. We can tweak it later if that turns out to be too big.

clangd/Quality.h

94

I did it to avoid inefficiencies of:

1. copying the context type for each completion item,
2. copying the symbol type for each of the indexed items.

My understanding is that (1) can be avoided by storing a reference to a type, since it outlives the signals.
But we'll still have to do a copy for (2), right?

That's probably not a bottleneck anyway, but keeping it a bool flag for now and happy to change it to your liking.

[sammccall]

clangd/CodeComplete.cpp

1304

Here would be a good place to include the expected type in a log message

1522

This is too verbose for vlog... could be dlog but I'm not sure it's actually needed in the end, we have code completion signal dumps. You should update Quality.cpp so the new signal is included :-)

clangd/Quality.h

94

Agree with your analysis.

I think our goal here should be to have a model with small # of per-symbol types, and small size of each type, so the per-symbol copy would be cheap. Sequencing is tricky - we don't have that optimization yet. Can we replay a session with some code completion and see if it shows up in a profiler?

(Perfect would be one type per symbol, types are 8-byte hashes. Unfortunately I think pointer->base conversions mean symbols must admit multiple tokens. But I have some ideas...)

[ilya-biryukov]

clangd/Quality.h

94

After discussing offline, we ended up with a bunch of flags to indicate whether:

1. a symbol or a sema decl had a type,
2. a context had a type,
3. those types were the same.

Let me know if that look ok. The bit that I don't like is that they're computed ad-hoc outside the merge function, which is a bit ugly.

[ilya-biryukov]

• Address comments, add more flags to signals

[sammccall]

You may want to add a FIXME in SymbolIndex to include opaque type in fuzzyfind request.

clangd/CodeComplete.cpp

1508

|= true is more traditionally known as = true :-)
(and below)

clangd/Quality.cpp

370

Consider combining these: "Type matched preferred: {0} (Context type: {1}, Symbol type: {2}"

[ilya-biryukov]

• Address comments

[ilya-biryukov]

• Add a FIXME to FuzzyFindRequest

clangd/CodeComplete.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "CodeComplete.h"
 #include "AST.h"
 #include "CodeCompletionStrings.h"
 #include "Compiler.h"
 #include "Diagnostics.h"
+#include "ExpectedTypes.h"
 #include "FileDistance.h"
 #include "FuzzyMatch.h"
 #include "Headers.h"
 #include "Logger.h"
 #include "Quality.h"
 #include "SourceCode.h"
 #include "TUScheduler.h"
 #include "Trace.h"
class CodeCompleteFlow {
   const CodeCompleteOptions &Opts;
 
   // Sema takes ownership of Recorder. Recorder is valid until Sema cleanup.
   CompletionRecorder *Recorder = nullptr;
   int NSema = 0, NIndex = 0, NBoth = 0; // Counters for logging.
   bool Incomplete = false; // Would more be available with a higher limit?
   llvm::Optional<FuzzyMatcher> Filter;       // Initialized once Sema runs.
   std::vector<std::string> QueryScopes;      // Initialized once Sema runs.
+  llvm::DenseMap<SType, float> ExpectedTypes; // Initialized once Sema runs.
   // Include-insertion and proximity scoring rely on the include structure.
   // This is available after Sema has run.
   llvm::Optional<IncludeInserter> Inserter;  // Available during runWithSema.
   llvm::Optional<URIDistance> FileProximity; // Initialized once Sema runs.
   /// Speculative request based on the cached request and the filter text before
   /// the cursor.
   /// Initialized right before sema run. This is only set if `SpecFuzzyFind` is
   /// set and contains a cached request.
auto RecorderOwner = llvm::make_unique<CompletionRecorder>(Opts, [&]() {
           Source.MaxUpTraversals = 1;
       }
       FileProximity.emplace(ProxSources, ProxOpts);
 
       Output = runWithSema();
       Inserter.reset(); // Make sure this doesn't out-live Clang.
       SPAN_ATTACH(Tracer, "sema_completion_kind",
                   getCompletionKindString(Recorder->CCContext.getKind()));
       log("Code complete: sema context {0}, query scopes [{1}]",
           getCompletionKindString(Recorder->CCContext.getKind()),
           llvm::join(QueryScopes.begin(), QueryScopes.end(), ","));
     });
 
     Recorder = RecorderOwner.get();
 
     semaCodeComplete(std::move(RecorderOwner), Opts.getClangCompleteOpts(),
                      SemaCCInput, &Includes);
if (CodeCompletionRange.isValid()) {
           Recorder->CCSema->getSourceManager(),
           Recorder->CCSema->getPreprocessor().getCodeCompletionLoc());
       TextEditRange.start = TextEditRange.end = Pos;
     }
     Filter = FuzzyMatcher(
         Recorder->CCSema->getPreprocessor().getCodeCompletionFilter());
     QueryScopes = getQueryScopes(Recorder->CCContext,
                                  Recorder->CCSema->getSourceManager());
+    ExpectedTypes =
+        SType::forCopyInitOf(Recorder->CCSema->getASTContext(),
+                             Recorder->CCContext.getPreferredType());
+    vlog("Added {0} expected types", ExpectedTypes.size());
     // Sema provides the needed context to query the index.
     // FIXME: in addition to querying for extra/overlapping symbols, we should
     //        explicitly request symbols corresponding to Sema results.
     //        We can use their signals even if the index can't suggest them.
     // We must copy index results to preserve them, but there are at most Limit.
     auto IndexResults = (Opts.Index && allowIndex(Recorder->CCContext))
                             ? queryIndex()
                             : SymbolSlab();
private:
   void addCandidate(TopN<ScoredBundle, ScoredBundleGreater> &Candidates,
                     CompletionCandidate::Bundle Bundle) {
     SymbolQualitySignals Quality;
     SymbolRelevanceSignals Relevance;
     Relevance.Context = Recorder->CCContext.getKind();
     Relevance.Query = SymbolRelevanceSignals::CodeComplete;
     Relevance.FileProximityMatch = FileProximity.getPointer();
     auto &First = Bundle.front();
     if (auto FuzzyScore = fuzzyScore(First))
       Relevance.NameMatch = *FuzzyScore;
     else
       return;
     SymbolOrigin Origin = SymbolOrigin::Unknown;
     bool FromIndex = false;
     for (const auto &Candidate : Bundle) {
       if (Candidate.IndexResult) {
         Quality.merge(*Candidate.IndexResult);
         Relevance.merge(*Candidate.IndexResult);
         Origin |= Candidate.IndexResult->Origin;
         FromIndex = true;
+        if (!ExpectedTypes.empty()) {
+          // FIXME(ibiryukov): this should live in Quality.cpp
+          auto TypeMatchMult =
+              typesMatch(ExpectedTypes, Candidate.IndexResult->Types);
+          if (TypeMatchMult) {
+            vlog("Types matched in sema for {0}", Candidate.Name);
+            Relevance.TypeMatchMultiplier =
+                std::max(*TypeMatchMult, Relevance.TypeMatchMultiplier);
+          }
+        }
       }
       if (Candidate.SemaResult) {
         Quality.merge(*Candidate.SemaResult);
         Relevance.merge(*Candidate.SemaResult);
+        if (!ExpectedTypes.empty()) {
+          // FIXME(ibiryukov): this should live in Quality.cpp
+          auto TypeMatchMult = typesMatch(
+              ExpectedTypes,
+              SType::fromCompletionResult(Recorder->CCSema->getASTContext(),
+                                          *Candidate.SemaResult));
+          if (TypeMatchMult) {
+            vlog("Types matched in sema for {0}", Candidate.Name);
+            Relevance.TypeMatchMultiplier =
+                std::max(*TypeMatchMult, Relevance.TypeMatchMultiplier);
+          }
+        }
         Origin |= SymbolOrigin::AST;
       }
     }
 
     CodeCompletion::Scores Scores;
     Scores.Quality = Quality.evaluate();
     Scores.Relevance = Relevance.evaluate();
     Scores.Total = evaluateSymbolAndRelevance(Scores.Quality, Scores.Relevance);

clangd/Quality.h

 ///   - compute scores from scoring signals. These are suitable for sorting.
 ///   - sorting utilities like the TopN container.
 /// These could be split up further to isolate dependencies if we care.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_QUALITY_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_QUALITY_H
-
+#include "ExpectedTypes.h"
 #include "clang/Sema/CodeCompleteConsumer.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/StringRef.h"
 #include <algorithm>
 #include <functional>
 #include <vector>
 
 namespace llvm {
struct SymbolRelevanceSignals {
   bool Forbidden = false; // Unavailable (e.g const) or inaccessible (private).
   /// Whether fixits needs to be applied for that completion or not.
   bool NeedsFixIts = false;
 
   URIDistance *FileProximityMatch = nullptr;
   /// This is used to calculate proximity between the index symbol and the
   /// query.
   llvm::StringRef SymbolURI;
+  /// A multiplier to be applied due to matching type.
+  float TypeMatchMultiplier = 1.0;
   /// Proximity between best declaration and the query. [0-1], 1 is closest.
   /// FIXME: unify with index proximity score - signals should be
   /// source-independent.
   float SemaProximityScore = 0;
 
   // An approximate measure of where we expect the symbol to be used.
   enum AccessibleScope {
     FunctionScope,

clangd/Quality.cpp

case ClassScope:
       break;
     case FunctionScope:
       Score *= 4;
       break;
     }
   }
 
   // Penalize non-instance members when they are accessed via a class instance.
   if (!IsInstanceMember &&
       (Context == CodeCompletionContext::CCC_DotMemberAccess ||
        Context == CodeCompletionContext::CCC_ArrowMemberAccess)) {
     Score *= 0.5;
   }
 
   // Penalize for FixIts.
   if (NeedsFixIts)
     Score *= 0.5;
 
+  Score *= TypeMatchMultiplier;
+
   return Score;
 }
 
 raw_ostream &operator<<(raw_ostream &OS, const SymbolRelevanceSignals &S) {
   OS << formatv("=== Symbol relevance: {0}\n", S.evaluate());
   OS << formatv("\tName match: {0}\n", S.NameMatch);
   OS << formatv("\tForbidden: {0}\n", S.Forbidden);
   OS << formatv("\tNeedsFixIts: {0}\n", S.NeedsFixIts);
   OS << formatv("\tIsInstanceMember: {0}\n", S.IsInstanceMember);
   OS << formatv("\tContext: {0}\n", getCompletionKindString(S.Context));
   OS << formatv("\tSymbol URI: {0}\n", S.SymbolURI);
   if (S.FileProximityMatch) {
     auto Score = proximityScore(S.SymbolURI, S.FileProximityMatch);
     OS << formatv("\tIndex proximity: {0} (distance={1})\n", Score.first,
                   Score.second);
   }
   OS << formatv("\tSema proximity: {0}\n", S.SemaProximityScore);
   OS << formatv("\tQuery type: {0}\n", static_cast<int>(S.Query));
   OS << formatv("\tScope: {0}\n", static_cast<int>(S.Scope));
   return OS;
 }
 
 float evaluateSymbolAndRelevance(float SymbolQuality, float SymbolRelevance) {
   return SymbolQuality * SymbolRelevance;
 }