Index: clangd/CodeComplete.cpp =================================================================== --- clangd/CodeComplete.cpp +++ clangd/CodeComplete.cpp @@ -34,6 +34,8 @@ #include "Trace.h" #include "URI.h" #include "index/Index.h" +#include "clang/AST/Decl.h" +#include "clang/AST/DeclBase.h" #include "clang/ASTMatchers/ASTMatchFinder.h" #include "clang/Basic/LangOptions.h" #include "clang/Basic/SourceLocation.h" @@ -44,6 +46,7 @@ #include "clang/Sema/CodeCompleteConsumer.h" #include "clang/Sema/Sema.h" #include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/None.h" #include "llvm/ADT/Optional.h" #include "llvm/ADT/SmallVector.h" #include "llvm/Support/Error.h" @@ -548,10 +551,20 @@ } }; +/// Returns the first enclosing namespace scope starting from \p DC. +std::string getEnclosingScope(const DeclContext &DC) { + for (const auto *Ctx = &DC; Ctx != nullptr; Ctx = Ctx->getParent()) + if (const auto *NS = dyn_cast(Ctx)) + if (!NS->isAnonymousNamespace() && !NS->isInlineNamespace()) + return printQualifiedName(*NS) + "::"; + return ""; +} + // Get all scopes that will be queried in indexes and whether symbols from -// any scope is allowed. +// any scope is allowed. The first scope in the list is the preferred scope +// (e.g. enclosing namespace). std::pair, bool> -getQueryScopes(CodeCompletionContext &CCContext, const SourceManager &SM, +getQueryScopes(CodeCompletionContext &CCContext, const Sema &CCSema, const CodeCompleteOptions &Opts) { auto GetAllAccessibleScopes = [](CodeCompletionContext &CCContext) { SpecifiedScope Info; @@ -559,7 +572,7 @@ if (isa(Context)) Info.AccessibleScopes.push_back(""); // global namespace else if (const auto *NS = dyn_cast(Context)) - Info.AccessibleScopes.push_back(NS->getQualifiedNameAsString() + "::"); + Info.AccessibleScopes.push_back(printQualifiedName(*NS) + "::"); } return Info; }; @@ -568,12 +581,13 @@ // Unqualified completion (e.g. "vec^"). if (!SS) { - // FIXME: Once we can insert namespace qualifiers and use the in-scope - // namespaces for scoring, search in all namespaces. - // FIXME: Capture scopes and use for scoring, for example, - // "using namespace std; namespace foo {v^}" => - // foo::value > std::vector > boost::variant - auto Scopes = GetAllAccessibleScopes(CCContext).scopesForIndexQuery(); + std::vector Scopes; + std::string EnclosingScope = getEnclosingScope(*CCSema.CurContext); + Scopes.push_back(EnclosingScope); + for (auto &S : GetAllAccessibleScopes(CCContext).scopesForIndexQuery()) { + if (EnclosingScope != S) + Scopes.push_back(std::move(S)); + } // Allow AllScopes completion only for there is no explicit scope qualifier. return {Scopes, Opts.AllScopes}; } @@ -592,8 +606,8 @@ Info.AccessibleScopes.push_back(""); // global namespace Info.UnresolvedQualifier = - Lexer::getSourceText(CharSourceRange::getCharRange((*SS)->getRange()), SM, - clang::LangOptions()) + Lexer::getSourceText(CharSourceRange::getCharRange((*SS)->getRange()), + CCSema.SourceMgr, clang::LangOptions()) .ltrim("::"); // Sema excludes the trailing "::". if (!Info.UnresolvedQualifier->empty()) @@ -1216,6 +1230,8 @@ bool Incomplete = false; // Would more be available with a higher limit? llvm::Optional Filter; // Initialized once Sema runs. std::vector QueryScopes; // Initialized once Sema runs. + // Initialized once QueryScopes is initialized. + llvm::Optional ScopeProximity; // Whether to query symbols from any scope. Initialized once Sema runs. bool AllScopes = false; // Include-insertion and proximity scoring rely on the include structure. @@ -1341,8 +1357,9 @@ } Filter = FuzzyMatcher( Recorder->CCSema->getPreprocessor().getCodeCompletionFilter()); - std::tie(QueryScopes, AllScopes) = getQueryScopes( - Recorder->CCContext, Recorder->CCSema->getSourceManager(), Opts); + std::tie(QueryScopes, AllScopes) = + getQueryScopes(Recorder->CCContext, *Recorder->CCSema, Opts); + ScopeProximity.emplace(QueryScopes); // 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. @@ -1479,7 +1496,7 @@ Relevance.Context = Recorder->CCContext.getKind(); Relevance.Query = SymbolRelevanceSignals::CodeComplete; Relevance.FileProximityMatch = FileProximity.getPointer(); - // FIXME: incorparate scope proximity into relevance score. + Relevance.ScopeProximityMatch = ScopeProximity.getPointer(); auto &First = Bundle.front(); if (auto FuzzyScore = fuzzyScore(First)) Index: clangd/Quality.h =================================================================== --- clangd/Quality.h +++ clangd/Quality.h @@ -78,6 +78,20 @@ llvm::raw_ostream &operator<<(llvm::raw_ostream &, const SymbolQualitySignals &); +/// Proximity between symbol scope and query scopes. +class QueryScopeProximity { + public: + /// QueryScopes[0] is the preferred scope. + QueryScopeProximity(std::vector QueryScopes) + : QueryScopes(std::move(QueryScopes)) {} + + /// Returns a proximity score in [0, 1]. 1 is closest + float proximity(llvm::StringRef Scope) const; + + private: + std::vector QueryScopes; +}; + /// 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. @@ -87,13 +101,17 @@ bool NeedsFixIts = false; URIDistance *FileProximityMatch = nullptr; - /// This is used to calculate proximity between the index symbol and the + /// These are used to calculate proximity between the index symbol and the /// query. llvm::StringRef SymbolURI; - /// Proximity between best declaration and the query. [0-1], 1 is closest. + llvm::Optional SymbolScope; + QueryScopeProximity *ScopeProximityMatch = nullptr; + /// FIXME: unify with index proximity score - signals should be /// source-independent. - float SemaProximityScore = 0; + /// Proximity between best declaration and the query. [0-1], 1 is closest. + float SemaFileProximityScore = 0; + float SemaScopeProximityScore = 0; // An approximate measure of where we expect the symbol to be used. enum AccessibleScope { Index: clangd/Quality.cpp =================================================================== --- clangd/Quality.cpp +++ clangd/Quality.cpp @@ -18,10 +18,14 @@ #include "clang/Basic/CharInfo.h" #include "clang/Basic/SourceManager.h" #include "clang/Sema/CodeCompleteConsumer.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/StringExtras.h" +#include "llvm/ADT/StringRef.h" #include "llvm/Support/Casting.h" #include "llvm/Support/FormatVariadic.h" #include "llvm/Support/MathExtras.h" #include "llvm/Support/raw_ostream.h" +#include #include namespace clang { @@ -239,6 +243,21 @@ return OS; } +float QueryScopeProximity::proximity(llvm::StringRef Scope) const { + if (QueryScopes.empty()) + return 0.0; + StringRef Enclosing = QueryScopes[0]; + if (Scope == Enclosing) + return Enclosing == "" ? 0.6 : 1.0; + else if (std::find_if(QueryScopes.begin(), QueryScopes.end(), + [Scope](llvm::StringRef QScope) { + return QScope == Scope || + (!QScope.empty() && Scope.startswith(QScope)); + }) != QueryScopes.end()) + return Scope == "" ? 0.3 : 0.6; + return 0; +} + static SymbolRelevanceSignals::AccessibleScope computeScope(const NamedDecl *D) { // Injected "Foo" within the class "Foo" has file scope, not class scope. @@ -268,6 +287,7 @@ // relevant to non-completion requests, we should recognize class members etc. SymbolURI = IndexResult.CanonicalDeclaration.FileURI; + SymbolScope = IndexResult.Scope; IsInstanceMember |= isInstanceMember(IndexResult.SymInfo); } @@ -277,6 +297,11 @@ Forbidden = true; if (SemaCCResult.Declaration) { + // Use a constant scope boost for sema results, as scopes of sema results + // can be tricky (e.g. class/function scope). Set to 1.0 as we don't load + // top-level symbols from the preamble and sema results are always in the + // accessible scope. + SemaScopeProximityScore = 1.0; // We boost things that have decls in the main file. We give a fixed score // for all other declarations in sema as they are already included in the // translation unit. @@ -284,7 +309,7 @@ hasUsingDeclInMainFile(SemaCCResult)) ? 1.0 : 0.6; - SemaProximityScore = std::max(DeclProximity, SemaProximityScore); + SemaFileProximityScore = std::max(DeclProximity, SemaFileProximityScore); IsInstanceMember |= isInstanceMember(SemaCCResult.Declaration); } @@ -295,8 +320,8 @@ NeedsFixIts = !SemaCCResult.FixIts.empty(); } -static std::pair proximityScore(llvm::StringRef SymbolURI, - URIDistance *D) { +static std::pair uriProximity(llvm::StringRef SymbolURI, + URIDistance *D) { if (!D || SymbolURI.empty()) return {0.f, 0u}; unsigned Distance = D->distance(SymbolURI); @@ -304,6 +329,13 @@ return {std::exp(Distance * -0.4f / FileDistanceOptions().UpCost), Distance}; } +static float scopeProximity(llvm::Optional SymbolScope, + QueryScopeProximity *Proximity) { + if (!SymbolScope || !Proximity) + return 0; + return Proximity->proximity(*SymbolScope); +} + float SymbolRelevanceSignals::evaluate() const { float Score = 1; @@ -312,10 +344,13 @@ Score *= NameMatch; - // Proximity scores are [0,1] and we translate them into a multiplier in the - // range from 1 to 3. - Score *= 1 + 2 * std::max(proximityScore(SymbolURI, FileProximityMatch).first, - SemaProximityScore); + // File proximity scores are [0,1] and we translate them into a multiplier in + // the range from 1 to 3. + Score *= 1 + 2 * std::max(uriProximity(SymbolURI, FileProximityMatch).first, + SemaFileProximityScore); + + Score *= 1 + std::max(scopeProximity(SymbolScope, ScopeProximityMatch), + SemaScopeProximityScore); // 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. @@ -358,15 +393,24 @@ OS << formatv("\tNeedsFixIts: {0}\n", S.NeedsFixIts); OS << formatv("\tIsInstanceMember: {0}\n", S.IsInstanceMember); OS << formatv("\tContext: {0}\n", getCompletionKindString(S.Context)); + OS << formatv("\tQuery type: {0}\n", static_cast(S.Query)); + OS << formatv("\tScope: {0}\n", static_cast(S.Scope)); + OS << formatv("\tSymbol URI: {0}\n", S.SymbolURI); + OS << formatv("\tSymbol scope: {0}\n", + S.SymbolScope ? *S.SymbolScope : ""); + if (S.FileProximityMatch) { - auto Score = proximityScore(S.SymbolURI, S.FileProximityMatch); - OS << formatv("\tIndex proximity: {0} (distance={1})\n", Score.first, + auto Score = uriProximity(S.SymbolURI, S.FileProximityMatch); + OS << formatv("\tIndex URI 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(S.Query)); - OS << formatv("\tScope: {0}\n", static_cast(S.Scope)); + OS << formatv("\tSema file proximity: {0}\n", S.SemaFileProximityScore); + + OS << formatv("\tIndex scope proximity: {0}\n", + scopeProximity(S.SymbolScope, S.ScopeProximityMatch)); + OS << formatv("\tSema scope proximity: {0}\n", S.SemaScopeProximityScore); + return OS; } Index: unittests/clangd/CodeCompleteTests.cpp =================================================================== --- unittests/clangd/CodeCompleteTests.cpp +++ unittests/clangd/CodeCompleteTests.cpp @@ -1040,6 +1040,29 @@ UnorderedElementsAre("", "ns::", "std::")))); } +TEST(CompletionTest, EnclosingScopeComesFirst) { + auto Requests = captureIndexRequests(R"cpp( + namespace std {} + using namespace std; + namespace nx { + namespace ns { + namespace { + void f() { + vec^ + } + } + } + } + )cpp"); + + EXPECT_THAT(Requests, + ElementsAre(Field( + &FuzzyFindRequest::Scopes, + UnorderedElementsAre("", "std::", "nx::ns::", + "nx::ns::(anonymous)::", "nx::")))); + EXPECT_EQ(Requests[0].Scopes[0], "nx::ns::"); +} + TEST(CompletionTest, ResolvedQualifiedIdQuery) { auto Requests = captureIndexRequests(R"cpp( namespace ns1 {} Index: unittests/clangd/QualityTests.cpp =================================================================== --- unittests/clangd/QualityTests.cpp +++ unittests/clangd/QualityTests.cpp @@ -28,6 +28,7 @@ #include "llvm/Support/Casting.h" #include "gmock/gmock.h" #include "gtest/gtest.h" +#include namespace clang { namespace clangd { @@ -117,13 +118,14 @@ Relevance = {}; Relevance.merge(CodeCompletionResult(&findDecl(AST, "main"), 42)); - EXPECT_FLOAT_EQ(Relevance.SemaProximityScore, 1.0f) << "Decl in current file"; + EXPECT_FLOAT_EQ(Relevance.SemaFileProximityScore, 1.0f) + << "Decl in current file"; Relevance = {}; Relevance.merge(CodeCompletionResult(&findDecl(AST, "header"), 42)); - EXPECT_FLOAT_EQ(Relevance.SemaProximityScore, 0.6f) << "Decl from header"; + EXPECT_FLOAT_EQ(Relevance.SemaFileProximityScore, 0.6f) << "Decl from header"; Relevance = {}; Relevance.merge(CodeCompletionResult(&findDecl(AST, "header_main"), 42)); - EXPECT_FLOAT_EQ(Relevance.SemaProximityScore, 1.0f) + EXPECT_FLOAT_EQ(Relevance.SemaFileProximityScore, 1.0f) << "Current file and header"; auto constructShadowDeclCompletionResult = [&](const std::string DeclName) { @@ -146,10 +148,10 @@ Relevance = {}; Relevance.merge(constructShadowDeclCompletionResult("Bar")); - EXPECT_FLOAT_EQ(Relevance.SemaProximityScore, 1.0f) + EXPECT_FLOAT_EQ(Relevance.SemaFileProximityScore, 1.0f) << "Using declaration in main file"; Relevance.merge(constructShadowDeclCompletionResult("FLAGS_FOO")); - EXPECT_FLOAT_EQ(Relevance.SemaProximityScore, 1.0f) + EXPECT_FLOAT_EQ(Relevance.SemaFileProximityScore, 1.0f) << "Using declaration in main file"; Relevance = {}; @@ -210,9 +212,19 @@ PoorNameMatch.NameMatch = 0.2f; EXPECT_LT(PoorNameMatch.evaluate(), Default.evaluate()); - SymbolRelevanceSignals WithSemaProximity; - WithSemaProximity.SemaProximityScore = 0.2f; - EXPECT_GT(WithSemaProximity.evaluate(), Default.evaluate()); + SymbolRelevanceSignals WithSemaFileProximity; + WithSemaFileProximity.SemaFileProximityScore = 0.2f; + EXPECT_GT(WithSemaFileProximity.evaluate(), Default.evaluate()); + + SymbolRelevanceSignals WithSemaScopeProximity; + WithSemaScopeProximity.SemaScopeProximityScore = 1.2f; + EXPECT_GT(WithSemaScopeProximity.evaluate(), Default.evaluate()); + + SymbolRelevanceSignals WithIndexScopeProximity; + QueryScopeProximity ScopeProximity({"x::y::"}); + WithSemaFileProximity.ScopeProximityMatch = &ScopeProximity; + WithSemaScopeProximity.SymbolScope = "x::y::"; + EXPECT_GT(WithSemaScopeProximity.evaluate(), Default.evaluate()); SymbolRelevanceSignals IndexProximate; IndexProximate.SymbolURI = "unittest:/foo/bar.h"; @@ -242,6 +254,34 @@ EXPECT_EQ(Instance.evaluate(), Default.evaluate()); } +TEST(QualityTests, ScopeProximity) { + SymbolRelevanceSignals Default; + + SymbolRelevanceSignals Relevance; + QueryScopeProximity ScopeProximity({"x::y::", "x::", "std::", ""}); + Relevance.ScopeProximityMatch = &ScopeProximity; + + Relevance.SymbolScope = "other::"; + float NotMatched = Relevance.evaluate(); + EXPECT_EQ(NotMatched, Default.evaluate()); + + Relevance.SymbolScope = ""; + float Global = Relevance.evaluate(); + EXPECT_GT(Global, Default.evaluate()); + + Relevance.SymbolScope = "std::"; + float NonParent = Relevance.evaluate(); + EXPECT_GT(NonParent, Global); + + Relevance.SymbolScope = "x::"; + float Parent = Relevance.evaluate(); + EXPECT_EQ(Parent, NonParent); + + Relevance.SymbolScope = "x::y::"; + float Enclosing = Relevance.evaluate(); + EXPECT_GT(Enclosing, Parent); +} + TEST(QualityTests, SortText) { EXPECT_LT(sortText(std::numeric_limits::infinity()), sortText(1000.2f));