[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

373

is 2 really enough?

clangd/Quality.h

98

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

98

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

373

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

clangd/Quality.h

98

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

1307–1308

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

1521

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

98

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

98

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

1504

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

clangd/Quality.cpp

418

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 "ClangdUnit.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 {
   // 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?
   Optional<FuzzyMatcher> Filter;        // Initialized once Sema runs.
   std::vector<std::string> QueryScopes; // Initialized once Sema runs.
   // Initialized once QueryScopes is initialized, if there are scopes.
   Optional<ScopeDistance> ScopeProximity;
+  llvm::Optional<OpaqueType> PreferredType; // Initialized once Sema runs.
   // Whether to query symbols from any scope. Initialized once Sema runs.
   bool AllScopes = false;
   // Include-insertion and proximity scoring rely on the include structure.
   // This is available after Sema has run.
   Optional<IncludeInserter> Inserter;  // Available during runWithSema.
   Optional<URIDistance> FileProximity; // Initialized once Sema runs.
   /// Speculative request based on the cached request and the filter text before
   /// the cursor.
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}] (AnyScope={2})",
+      log("Code complete: sema context {0}, query scopes [{1}] (AnyScope={2}), "
+          "expected type {3}",
           getCompletionKindString(Recorder->CCContext.getKind()),
-          join(QueryScopes.begin(), QueryScopes.end(), ","), AllScopes);
+          join(QueryScopes.begin(), QueryScopes.end(), ","), AllScopes,
+          PreferredType ? Recorder->CCContext.getPreferredType().getAsString()
+                        : "<none>");
     });
 
     Recorder = RecorderOwner.get();
 
     semaCodeComplete(std::move(RecorderOwner), Opts.getClangCompleteOpts(),
                      SemaCCInput, &Includes);
 
     SPAN_ATTACH(Tracer, "sema_results", NSema);
if (CodeCompletionRange.isValid()) {
       TextEditRange.start = TextEditRange.end = Pos;
     }
     Filter = FuzzyMatcher(
         Recorder->CCSema->getPreprocessor().getCodeCompletionFilter());
     std::tie(QueryScopes, AllScopes) =
         getQueryScopes(Recorder->CCContext, *Recorder->CCSema, Opts);
     if (!QueryScopes.empty())
       ScopeProximity.emplace(QueryScopes);
+    PreferredType =
+        OpaqueType::fromType(Recorder->CCSema->getASTContext(),
+                             Recorder->CCContext.getPreferredType());
     // 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();
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();
     if (ScopeProximity)
       Relevance.ScopeProximityMatch = ScopeProximity.getPointer();
+    if (PreferredType)
+      Relevance.HadContextType = true;
 
     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 (!Candidate.IndexResult->Type.empty())
+          Relevance.HadSymbolType |= true;
+        if (PreferredType &&
+            PreferredType->raw() == Candidate.IndexResult->Type) {
+          Relevance.TypeMatchesPreferred = true;
+        }
       }
       if (Candidate.SemaResult) {
         Quality.merge(*Candidate.SemaResult);
         Relevance.merge(*Candidate.SemaResult);
+        if (PreferredType) {
+          if (auto CompletionType = OpaqueType::fromCompletionResult(
+                  Recorder->CCSema->getASTContext(), *Candidate.SemaResult)) {
+            Relevance.HadSymbolType |= true;
+            if (PreferredType == CompletionType)
+              Relevance.TypeMatchesPreferred = true;
+          }
+        }
         Origin |= SymbolOrigin::AST;
       }
     }
 
     CodeCompletion::Scores Scores;
     Scores.Quality = Quality.evaluate();
     Scores.Relevance = Relevance.evaluate();
     Scores.Total = evaluateSymbolAndRelevance(Scores.Quality, Scores.Relevance);

clangd/Quality.h

 ///   - 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 "FileDistance.h"
 #include "clang/Sema/CodeCompleteConsumer.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/StringRef.h"
 #include <algorithm>
 #include <functional>
 #include <vector>
 
struct SymbolRelevanceSignals {
   bool NeedsFixIts = false;
   bool InBaseClass = false; // A member from base class of the accessed class.
 
   URIDistance *FileProximityMatch = nullptr;
   /// These are used to calculate proximity between the index symbol and the
   /// query.
   llvm::StringRef SymbolURI;
   /// FIXME: unify with index proximity score - signals should be
   /// source-independent.
   /// Proximity between best declaration and the query. [0-1], 1 is closest.
   float SemaFileProximityScore = 0;
 
   // Scope proximity is only considered (both index and sema) when this is set.
   ScopeDistance *ScopeProximityMatch = nullptr;
   llvm::Optional<llvm::StringRef> SymbolScope;
   // A symbol from sema should be accessible from the current scope.
   bool SemaSaysInScope = false;
enum QueryType {
     Generic,
   } Query = Generic;
 
   CodeCompletionContext::Kind Context = CodeCompletionContext::CCC_Other;
 
   // Whether symbol is an instance member of a class.
   bool IsInstanceMember = false;
 
+  // Whether clang provided a preferred type in the completion context.
+  bool HadContextType = false;
+  // Whether a source completion item or a symbol had a type information.
+  bool HadSymbolType = false;
+  // Whether the item matches the type expected in the completion context.
+  bool TypeMatchesPreferred = false;
+
   void merge(const CodeCompletionResult &SemaResult);
   void merge(const Symbol &IndexResult);
 
   // Condense these signals down to a single number, higher is better.
   float evaluate() const;
 };
 llvm::raw_ostream &operator<<(llvm::raw_ostream &,
                               const SymbolRelevanceSignals &);

clangd/Quality.cpp

case ClassScope:
       Score *= 2;
       break;
     case FunctionScope:
       Score *= 4;
       break;
     }
   }
 
+  if (TypeMatchesPreferred)
+    Score *= 5.0;
+
   // Penalize non-instance members when they are accessed via a class instance.
   if (!IsInstanceMember &&
       (Context == CodeCompletionContext::CCC_DotMemberAccess ||
        Context == CodeCompletionContext::CCC_ArrowMemberAccess)) {
     Score *= 0.2f;
   }
 
   if (InBaseClass)
raw_ostream &operator<<(raw_ostream &OS, const SymbolRelevanceSignals &S) {
   }
   OS << formatv("\tSema file proximity: {0}\n", S.SemaFileProximityScore);
 
   OS << formatv("\tSema says in scope: {0}\n", S.SemaSaysInScope);
   if (S.ScopeProximityMatch)
     OS << formatv("\tIndex scope boost: {0}\n",
                   scopeBoost(*S.ScopeProximityMatch, S.SymbolScope));
 
+  OS << formatv(
+      "\tType matched preferred: {0} (Context type: {1}, Symbol type: {2}\n",
+      S.TypeMatchesPreferred, S.HadContextType, S.HadSymbolType);
+
   return OS;
 }
 
 float evaluateSymbolAndRelevance(float SymbolQuality, float SymbolRelevance) {
   return SymbolQuality * SymbolRelevance;
 }
 
 // Produces an integer that sorts in the same order as F.

clangd/index/Index.h

struct FuzzyFindRequest {
   /// return more than this, e.g. if it doesn't know which candidates are best.
   llvm::Optional<uint32_t> Limit;
   /// If set to true, only symbols for completion support will be considered.
   bool RestrictForCodeCompletion = false;
   /// Contextually relevant files (e.g. the file we're code-completing in).
   /// Paths should be absolute.
   std::vector<std::string> ProximityPaths;
 
+  // FIXME(ibiryukov): add expected type to the request.
+
   bool operator==(const FuzzyFindRequest &Req) const {
     return std::tie(Query, Scopes, Limit, RestrictForCodeCompletion,
                     ProximityPaths) ==
            std::tie(Req.Query, Req.Scopes, Req.Limit,
                     Req.RestrictForCodeCompletion, Req.ProximityPaths);
   }
   bool operator!=(const FuzzyFindRequest &Req) const { return !(*this == Req); }
 };