[clangd] Boost code completion results that are narrowly scoped (local, members)

[sammccall]

Summary

This signal is considered a relevance rather than a quality signal because it's
dependent on the query (the fact that it's completion, and implicitly the query
context).

This is part of the effort to reduce reliance on Sema priority, so we can have
consistent ranking between Index and Sema results.

[ioeric]

Looks like a great improvement on ranking!

clangd/Quality.cpp

62 ↗

(On Diff #149910)

nit: maybe stop when`!DC->isFileContext()`?

66 ↗

(On Diff #149910)

DC->isRecord()?

70 ↗

(On Diff #149910)

I wonder if this comparison is a common practice. Any reason not to use !=?

71 ↗

(On Diff #149910)

Does FileScope indicate that D is defined in the current *translation unit*? If so, I think this is a good signal (boosting symbols in the same TU), but something like TUScope might be a bit clearer?

76 ↗

(On Diff #149910)

What's here to be fixed? Do we plan to get rid of this assumption in the future?

86 ↗

(On Diff #149910)

nit: does this assume that "smaller" scopes are better? If so, it might make sense to document.

unittests/clangd/QualityTests.cpp

1 ↗

(On Diff #149910)

Could you also add a test case for code completion?

[sammccall]

Address review comments and sync.

[sammccall]

clangd/Quality.cpp

70 ↗

(On Diff #149910)

The orderedness in linkage is used e.g. in isExternallyVisible().
I prefer < because while with this particular threshold value != would be equivalent, I'm not actually particularly sure it's the right threshold (vs e.g. ModuleLinkage), and with any other threshold < would be required.

71 ↗

(On Diff #149910)

File rather than TU is intended here. AccessibleScope is only an approximate concept (it doesn't need to be precise as it's just a scoring signal).
The idea is "this is a symbol likely to be only used in the same file that declares it", and this is true of e.g. variables in anonymous namespaces, despite the fact that you can technically put them in headers and reference them in the main file.

Added a comment to AccessibleScope to clarify this approximate nature.

86 ↗

(On Diff #149910)

There's no connection with "better" here, just that items are assumed to have maximum scope (global) until proven otherwise.

There's no intent here (or with other signals) for merging conflicting results from different sources to do anything clever - it's fine to choose one arbitrarily.

unittests/clangd/QualityTests.cpp

1 ↗

(On Diff #149910)

The code completion scoring is tested in SymbolRelevanceSignalsSanity: file scope is boosted compared to default when the query is code-complete, but not when it's generic.

What kind of test do you mean?

[ioeric]

lgtm

clangd/Quality.cpp

70 ↗

(On Diff #149910)

sounds good. this would probably deserve a comment though as it's a little confusing...

71 ↗

(On Diff #149910)

Cool. Thanks for the explanation!

unittests/clangd/QualityTests.cpp

1 ↗

(On Diff #149910)

I was thinking a test case that covers the changes in CodeComplete.cpp e.g. check that Relevance and Quality play well together, and locals/members are boosted? Would that make sense?

[sammccall]

unittests/clangd/QualityTests.cpp

1 ↗

(On Diff #149910)

Actually one of the purposes of pulling out the Quality module is to stop writing such tests :-)
They're fragile because ranking depends on many factors, e.g. at the moment you can't construct a completion candidate with a different scope that won't also get a different sema priority, so it's not clear why a test is passing/failing.
And for every signal, you need a test in code complete, and in workspace symbols...

It *would* be useful to have a smoke test in CodeCompletion to make sure we're using those scores. Maybe it would make sense to turn ReferencesAffectRanking or so into that?

[ioeric]

unittests/clangd/QualityTests.cpp

1 ↗

(On Diff #149910)

That makes sense. A smoke test in code completion sounds good.

clang-tools-extra/trunk/clangd/ClangdUnit.h

public:
   const ASTContext &getASTContext() const;
 
   Preprocessor &getPreprocessor();
   std::shared_ptr<Preprocessor> getPreprocessorPtr();
   const Preprocessor &getPreprocessor() const;
 
   /// This function returns top-level decls present in the main file of the AST.
   /// The result does not include the decls that come from the preamble.
-  ArrayRef<const Decl *> getLocalTopLevelDecls();
+  /// (These should be const, but RecursiveASTVisitor requires Decl*).
+  ArrayRef<Decl *> getLocalTopLevelDecls();
 
   const std::vector<Diag> &getDiagnostics() const;
 
   /// Returns the esitmated size of the AST and the accessory structures, in
   /// bytes. Does not include the size of the preamble.
   std::size_t getUsedBytes() const;
   const std::vector<Inclusion> &getInclusions() const;
 
 private:
   ParsedAST(std::shared_ptr<const PreambleData> Preamble,
             std::unique_ptr<CompilerInstance> Clang,
             std::unique_ptr<FrontendAction> Action,
-            std::vector<const Decl *> LocalTopLevelDecls,
-            std::vector<Diag> Diags, std::vector<Inclusion> Inclusions);
+            std::vector<Decl *> LocalTopLevelDecls, std::vector<Diag> Diags,
+            std::vector<Inclusion> Inclusions);
 
   // In-memory preambles must outlive the AST, it is important that this member
   // goes before Clang and Action.
   std::shared_ptr<const PreambleData> Preamble;
   // We store an "incomplete" FrontendAction (i.e. no EndSourceFile was called
   // on it) and CompilerInstance used to run it. That way we don't have to do
   // complex memory management of all Clang structures on our own. (They are
   // stored in CompilerInstance and cleaned up by
   // FrontendAction.EndSourceFile).
   std::unique_ptr<CompilerInstance> Clang;
   std::unique_ptr<FrontendAction> Action;
 
   // Data, stored after parsing.
   std::vector<Diag> Diags;
   // Top-level decls inside the current file. Not that this does not include
   // top-level decls from the preamble.
-  std::vector<const Decl *> LocalTopLevelDecls;
+  std::vector<Decl *> LocalTopLevelDecls;
   std::vector<Inclusion> Inclusions;
 };
 
 using PreambleParsedCallback = std::function<void(
     PathRef Path, ASTContext &, std::shared_ptr<clang::Preprocessor>)>;
 
 /// Builds compiler invocation that could be used to build AST or preamble.
 std::unique_ptr<CompilerInvocation>

clang-tools-extra/trunk/clangd/ClangdUnit.cpp

 }
 
 template <class T> std::size_t getUsedBytes(const std::vector<T> &Vec) {
   return Vec.capacity() * sizeof(T);
 }
 
 class DeclTrackingASTConsumer : public ASTConsumer {
 public:
-  DeclTrackingASTConsumer(std::vector<const Decl *> &TopLevelDecls)
+  DeclTrackingASTConsumer(std::vector<Decl *> &TopLevelDecls)
       : TopLevelDecls(TopLevelDecls) {}
 
   bool HandleTopLevelDecl(DeclGroupRef DG) override {
-    for (const Decl *D : DG) {
+    for (Decl *D : DG) {
       // ObjCMethodDecl are not actually top-level decls.
       if (isa<ObjCMethodDecl>(D))
         continue;
 
       TopLevelDecls.push_back(D);
     }
     return true;
   }
 
 private:
-  std::vector<const Decl *> &TopLevelDecls;
+  std::vector<Decl *> &TopLevelDecls;
 };
 
 class ClangdFrontendAction : public SyntaxOnlyAction {
 public:
-  std::vector<const Decl *> takeTopLevelDecls() {
-    return std::move(TopLevelDecls);
-  }
+  std::vector<Decl *> takeTopLevelDecls() { return std::move(TopLevelDecls); }
 
 protected:
   std::unique_ptr<ASTConsumer> CreateASTConsumer(CompilerInstance &CI,
                                                  StringRef InFile) override {
     return llvm::make_unique<DeclTrackingASTConsumer>(/*ref*/ TopLevelDecls);
   }
 
 private:
-  std::vector<const Decl *> TopLevelDecls;
+  std::vector<Decl *> TopLevelDecls;
 };
 
 class CppFilePreambleCallbacks : public PreambleCallbacks {
 public:
   CppFilePreambleCallbacks(PathRef File, PreambleParsedCallback ParsedCallback)
       : File(File), ParsedCallback(ParsedCallback) {}
 
   std::vector<Inclusion> takeInclusions() { return std::move(Inclusions); }
if (!Action->Execute())
     log("Execute() failed when building AST for " + MainInput.getFile());
 
   // UnitDiagsConsumer is local, we can not store it in CompilerInstance that
   // has a longer lifetime.
   Clang->getDiagnostics().setClient(new IgnoreDiagnostics);
   // CompilerInstance won't run this callback, do it directly.
   ASTDiags.EndSourceFile();
 
-  std::vector<const Decl *> ParsedDecls = Action->takeTopLevelDecls();
+  std::vector<Decl *> ParsedDecls = Action->takeTopLevelDecls();
   std::vector<Diag> Diags = ASTDiags.take();
   // Add diagnostics from the preamble, if any.
   if (Preamble)
     Diags.insert(Diags.begin(), Preamble->Diags.begin(), Preamble->Diags.end());
   return ParsedAST(std::move(Preamble), std::move(Clang), std::move(Action),
                    std::move(ParsedDecls), std::move(Diags),
                    std::move(Inclusions));
 }

 std::shared_ptr<Preprocessor> ParsedAST::getPreprocessorPtr() {
   return Clang->getPreprocessorPtr();
 }
 
 const Preprocessor &ParsedAST::getPreprocessor() const {
   return Clang->getPreprocessor();
 }
 
-ArrayRef<const Decl *> ParsedAST::getLocalTopLevelDecls() {
+ArrayRef<Decl *> ParsedAST::getLocalTopLevelDecls() {
   return LocalTopLevelDecls;
 }
 
 const std::vector<Diag> &ParsedAST::getDiagnostics() const { return Diags; }
 
 std::size_t ParsedAST::getUsedBytes() const {
   auto &AST = getASTContext();
   // FIXME(ibiryukov): we do not account for the dynamically allocated part of
PreambleData::PreambleData(PrecompiledPreamble Preamble,
                            std::vector<Diag> Diags,
                            std::vector<Inclusion> Inclusions)
     : Preamble(std::move(Preamble)), Diags(std::move(Diags)),
       Inclusions(std::move(Inclusions)) {}
 
 ParsedAST::ParsedAST(std::shared_ptr<const PreambleData> Preamble,
                      std::unique_ptr<CompilerInstance> Clang,
                      std::unique_ptr<FrontendAction> Action,
-                     std::vector<const Decl *> LocalTopLevelDecls,
+                     std::vector<Decl *> LocalTopLevelDecls,
                      std::vector<Diag> Diags, std::vector<Inclusion> Inclusions)
     : Preamble(std::move(Preamble)), Clang(std::move(Clang)),
       Action(std::move(Action)), Diags(std::move(Diags)),
       LocalTopLevelDecls(std::move(LocalTopLevelDecls)),
       Inclusions(std::move(Inclusions)) {
   assert(this->Clang);
   assert(this->Action);
 }

clang-tools-extra/trunk/clangd/CodeComplete.cpp

void addCandidate(TopN<ScoredCandidate, ScoredCandidateGreater> &Candidates,
                     const Symbol *IndexResult) {
     CompletionCandidate C;
     C.SemaResult = SemaResult;
     C.IndexResult = IndexResult;
     C.Name = IndexResult ? IndexResult->Name : Recorder->getName(*SemaResult);
 
     SymbolQualitySignals Quality;
     SymbolRelevanceSignals Relevance;
+    Relevance.Query = SymbolRelevanceSignals::CodeComplete;
     if (auto FuzzyScore = Filter->match(C.Name))
       Relevance.NameMatch = *FuzzyScore;
     else
       return;
-    if (IndexResult)
+    if (IndexResult) {
       Quality.merge(*IndexResult);
+      Relevance.merge(*IndexResult);
+    }
     if (SemaResult) {
       Quality.merge(*SemaResult);
       Relevance.merge(*SemaResult);
     }
 
     float QualScore = Quality.evaluate(), RelScore = Relevance.evaluate();
     CompletionItemScores Scores;
     Scores.finalScore = evaluateSymbolAndRelevance(QualScore, RelScore);

clang-tools-extra/trunk/clangd/Quality.h

 /// Attributes of a symbol-query pair that affect how much we like it.
 struct SymbolRelevanceSignals {
   /// 0-1 fuzzy-match score for unqualified name. Must be explicitly assigned.
   float NameMatch = 1;
   bool Forbidden = false; // Unavailable (e.g const) or inaccessible (private).
   /// Proximity between best declaration and the query. [0-1], 1 is closest.
   float ProximityScore = 0;
 
+  // An approximate measure of where we expect the symbol to be used.
+  enum AccessibleScope {
+    FunctionScope,
+    ClassScope,
+    FileScope,
+    GlobalScope,
+  } Scope = GlobalScope;
+
+  enum QueryType {
+    CodeComplete,
+    Generic,
+  } Query = Generic;
+
   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 &);
 
 /// Combine symbol quality and relevance into a single score.

clang-tools-extra/trunk/clangd/Quality.cpp

raw_ostream &operator<<(raw_ostream &OS, const SymbolQualitySignals &S) {
   OS << formatv("=== Symbol quality: {0}\n", S.evaluate());
   if (S.SemaCCPriority)
     OS << formatv("\tSemaCCPriority: {0}\n", S.SemaCCPriority);
   OS << formatv("\tReferences: {0}\n", S.References);
   OS << formatv("\tDeprecated: {0}\n", S.Deprecated);
   return OS;
 }
 
+static SymbolRelevanceSignals::AccessibleScope
+ComputeScope(const NamedDecl &D) {
+  bool InClass;
+  for (const DeclContext *DC = D.getDeclContext(); !DC->isFileContext();
+       DC = DC->getParent()) {
+    if (DC->isFunctionOrMethod())
+      return SymbolRelevanceSignals::FunctionScope;
+    InClass = InClass || DC->isRecord();
+  }
+  if (InClass)
+    return SymbolRelevanceSignals::ClassScope;
+  // This threshold could be tweaked, e.g. to treat module-visible as global.
+  if (D.getLinkageInternal() < ExternalLinkage)
+    return SymbolRelevanceSignals::FileScope;
+  return SymbolRelevanceSignals::GlobalScope;
+}
+
+void SymbolRelevanceSignals::merge(const Symbol &IndexResult) {
+  // FIXME: Index results always assumed to be at global scope. If Scope becomes
+  // relevant to non-completion requests, we should recognize class members etc.
+}
+
 void SymbolRelevanceSignals::merge(const CodeCompletionResult &SemaCCResult) {
   if (SemaCCResult.Availability == CXAvailability_NotAvailable ||
       SemaCCResult.Availability == CXAvailability_NotAccessible)
     Forbidden = true;
 
   if (SemaCCResult.Declaration) {
     // We boost things that have decls in the main file.
     // The real proximity scores would be more general when we have them.
     float DeclProximity =
         hasDeclInMainFile(*SemaCCResult.Declaration) ? 1.0 : 0.0;
     ProximityScore = std::max(DeclProximity, ProximityScore);
   }
+
+  // Declarations are scoped, others (like macros) are assumed global.
+  if (SemaCCResult.Kind == CodeCompletionResult::RK_Declaration)
+    Scope = std::min(Scope, ComputeScope(*SemaCCResult.Declaration));
 }
 
 float SymbolRelevanceSignals::evaluate() const {
+  float Score = 1;
+
   if (Forbidden)
     return 0;
 
-  float Score = NameMatch;
+  Score *= NameMatch;
+
   // Proximity scores are [0,1] and we translate them into a multiplier in the
   // range from 1 to 2.
   Score *= 1 + ProximityScore;
+
+  // Symbols like local variables may only be referenced within their scope.
+  // Conversely if we're in that scope, it's likely we'll reference them.
+  if (Query == CodeComplete) {
+    // The narrower the scope where a symbol is visible, the more likely it is
+    // to be relevant when it is available.
+    switch (Scope) {
+    case GlobalScope:
+      break;
+    case FileScope:
+      Score *= 1.5;
+    case ClassScope:
+      Score *= 2;
+    case FunctionScope:
+      Score *= 4;
+    }
+  }
+
   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);
   return OS;
 }

clang-tools-extra/trunk/unittests/clangd/QualityTests.cpp

Test.HeaderCode = R"cpp(
     int header_main();
     )cpp";
   Test.Code = R"cpp(
     int ::header_main() {}
     int main();
 
     [[deprecated]]
     int deprecated() { return 0; }
+
+    namespace { struct X { void y() { int z; } }; }
   )cpp";
   auto AST = Test.build();
 
   SymbolRelevanceSignals Relevance;
   Relevance.merge(CodeCompletionResult(&findDecl(AST, "deprecated"),
                                        /*Priority=*/42, nullptr, false,
                                        /*Accessible=*/false));
   EXPECT_EQ(Relevance.NameMatch, SymbolRelevanceSignals().NameMatch);
   EXPECT_TRUE(Relevance.Forbidden);
+  EXPECT_EQ(Relevance.Scope, SymbolRelevanceSignals::GlobalScope);
 
   Relevance = {};
   Relevance.merge(CodeCompletionResult(&findDecl(AST, "main"), 42));
   EXPECT_FLOAT_EQ(Relevance.ProximityScore, 1.0) << "Decl in current file";
   Relevance = {};
   Relevance.merge(CodeCompletionResult(&findDecl(AST, "header"), 42));
   EXPECT_FLOAT_EQ(Relevance.ProximityScore, 0.0) << "Decl from header";
   Relevance = {};
   Relevance.merge(CodeCompletionResult(&findDecl(AST, "header_main"), 42));
   EXPECT_FLOAT_EQ(Relevance.ProximityScore, 1.0) << "Current file and header";
+
+  Relevance = {};
+  Relevance.merge(CodeCompletionResult(&findAnyDecl(AST, "X"), 42));
+  EXPECT_EQ(Relevance.Scope, SymbolRelevanceSignals::FileScope);
+  Relevance = {};
+  Relevance.merge(CodeCompletionResult(&findAnyDecl(AST, "y"), 42));
+  EXPECT_EQ(Relevance.Scope, SymbolRelevanceSignals::ClassScope);
+  Relevance = {};
+  Relevance.merge(CodeCompletionResult(&findAnyDecl(AST, "z"), 42));
+  EXPECT_EQ(Relevance.Scope, SymbolRelevanceSignals::FunctionScope);
 }
 
 // Do the signals move the scores in the direction we expect?
 TEST(QualityTests, SymbolQualitySignalsSanity) {
   SymbolQualitySignals Default;
   EXPECT_EQ(Default.evaluate(), 1);
 
   SymbolQualitySignals Deprecated;
TEST(QualityTests, SymbolRelevanceSignalsSanity) {
 
   SymbolRelevanceSignals PoorNameMatch;
   PoorNameMatch.NameMatch = 0.2f;
   EXPECT_LT(PoorNameMatch.evaluate(), Default.evaluate());
 
   SymbolRelevanceSignals WithProximity;
   WithProximity.ProximityScore = 0.2f;
   EXPECT_GT(WithProximity.evaluate(), Default.evaluate());
+
+  SymbolRelevanceSignals Scoped;
+  Scoped.Scope = SymbolRelevanceSignals::FileScope;
+  EXPECT_EQ(Scoped.evaluate(), Default.evaluate());
+  Scoped.Query = SymbolRelevanceSignals::CodeComplete;
+  EXPECT_GT(Scoped.evaluate(), Default.evaluate());
 }
 
 TEST(QualityTests, SortText) {
   EXPECT_LT(sortText(std::numeric_limits<float>::infinity()), sortText(1000.2f));
   EXPECT_LT(sortText(1000.2f), sortText(1));
   EXPECT_LT(sortText(1), sortText(0.3f));
   EXPECT_LT(sortText(0.3f), sortText(0));
   EXPECT_LT(sortText(0), sortText(-10));

clang-tools-extra/trunk/unittests/clangd/TestTU.h

struct TestTU {
   SymbolSlab headerSymbols() const;
   std::unique_ptr<SymbolIndex> index() const;
 };
 
 // Look up an index symbol by qualified name, which must be unique.
 const Symbol &findSymbol(const SymbolSlab &, llvm::StringRef QName);
 // Look up an AST symbol by qualified name, which must be unique and top-level.
 const NamedDecl &findDecl(ParsedAST &AST, llvm::StringRef QName);
+// Look up a main-file AST symbol by unqualified name, which must be unique.
+const NamedDecl &findAnyDecl(ParsedAST &AST, llvm::StringRef Name);
 
 } // namespace clangd
 } // namespace clang
 #endif

clang-tools-extra/trunk/unittests/clangd/TestTU.cpp

 //===--- TestTU.cpp - Scratch source files for testing --------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===---------------------------------------------------------------------===//
 #include "TestTU.h"
 #include "TestFS.h"
 #include "index/FileIndex.h"
 #include "index/MemIndex.h"
+#include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/Frontend/CompilerInvocation.h"
 #include "clang/Frontend/PCHContainerOperations.h"
 #include "clang/Frontend/Utils.h"
 
 namespace clang {
 namespace clangd {
 using namespace llvm;
 
SymbolSlab TestTU::headerSymbols() const {
   auto AST = build();
   return indexAST(AST.getASTContext(), AST.getPreprocessorPtr());
 }
 
 std::unique_ptr<SymbolIndex> TestTU::index() const {
   return MemIndex::build(headerSymbols());
 }
 
-// Look up a symbol by qualified name, which must be unique.
 const Symbol &findSymbol(const SymbolSlab &Slab, llvm::StringRef QName) {
   const Symbol *Result = nullptr;
   for (const Symbol &S : Slab) {
     if (QName != (S.Scope + S.Name).str())
       continue;
     if (Result) {
       ADD_FAILURE() << "Multiple symbols named " << QName << ":\n"
                     << *Result << "\n---\n"
const NamedDecl &findDecl(ParsedAST &AST, llvm::StringRef QName) {
   const DeclContext *Scope = Ctx.getTranslationUnitDecl();
   for (auto NameIt = Components.begin(), End = Components.end() - 1;
        NameIt != End; ++NameIt) {
     Scope = &cast<DeclContext>(LookupDecl(*Scope, *NameIt));
   }
   return LookupDecl(*Scope, Components.back());
 }
 
+const NamedDecl &findAnyDecl(ParsedAST &AST, llvm::StringRef Name) {
+  struct Visitor : RecursiveASTVisitor<Visitor> {
+    llvm::StringRef Name;
+    llvm::SmallVector<const NamedDecl *, 1> Decls;
+    bool VisitNamedDecl(const NamedDecl *ND) {
+      if (auto *ID = ND->getIdentifier())
+        if (ID->getName() == Name)
+          Decls.push_back(ND);
+      return true;
+    }
+  } Visitor;
+  Visitor.Name = Name;
+  for (Decl *D : AST.getLocalTopLevelDecls())
+    Visitor.TraverseDecl(D);
+  if (Visitor.Decls.size() != 1) {
+    ADD_FAILURE() << Visitor.Decls.size() << " symbols named " << Name;
+    assert(Visitor.Decls.size() == 1);
+  }
+  return *Visitor.Decls.front();
+}
+
 } // namespace clangd
 } // namespace clang