[clangd] Support scope proximity in code completion.

[ioeric]

Summary

This should make all-scope completion more usable. Scope proximity for
indexes will be added in followup patch.

[sammccall]

clangd/CodeComplete.cpp

558 ↗

(On Diff #169180)

does this do the right thing if it's anonymous or inline, or a parent is?

For indexing, we call a function in AST.h, we should probably do something similar.

The catch is that function relies on NamedDecl::printQualifiedName, maybe we need to factor out the relevant part so we can call it on a DeclContext.

559 ↗

(On Diff #169180)

shouldn't this be ""? That's a definite scope, not a failure to find one.
(It's not a *namespace* scope, but I'm not sure why that's important)

clangd/Quality.cpp

246 ↗

(On Diff #169180)

If you're going to decide these numbers directly...

a) I think you should just return a multiplier here, rather than a 0-1 score
b) we should more aggressively downrank non-preferred symbols: currently by only ~1/3 vs symbols from a preferred scopes

e.g. I'd suggest returning 1, 2, 1.5, 1, 1, 1.5, 0.3 or similar

301 ↗

(On Diff #169180)

I don't think "always in the accessible scope" is sufficient justification to give a score of 1.
However "we don't load top-level symbols from the preamble" might be?

clangd/Quality.h

92 ↗

(On Diff #169180)

hmm, can/should we use FileProximity for this, and just transform the strings?

This isn't going to cache for symbols sharing a namespace, isn't going to handle "symbol is in a child namespace of an included namespace", and some other combinations.

[ioeric]

• address review comments

[ioeric]

clangd/CodeComplete.cpp

558 ↗

(On Diff #169180)

Good catch.

NamedDecl::printQualifiedName doesn't skip the (anonymous) part if the decl itself is anonymous, even with SuppressUnwrittenScope set. So I think we should explicitly filter those out here and then call printQualifiedName.

559 ↗

(On Diff #169180)

Make sense.

I think we might still want to special-case the global scope (not here, maybe in proximity scoring) because:

• if any scope is specified, it's probably more desireable than the global scope.
• there are patterns like below in cpp files (instead of using enclosing namespace):

using namespace clang;
using namespace clang::clangd;

Currently, if the enclosing scope is "", then we would treat it the same as the scopes from using-namespace directives.

clangd/Quality.cpp

246 ↗

(On Diff #169180)

a) I think you should just return a multiplier here, rather than a 0-1 score.

I tried this. Unfortunately, allowing <1 multiplier would make the default value (for sema proximity) tricky. And [0,1] proximity score seems to be less confusing as it's consistent with the file proximity scale. If [0,1] isn't enough, we could still increase the upper bound?

b) we should more aggressively downrank non-preferred symbols: currently by only ~1/3 vs symbols from a preferred scopes

It's ~1/3 only for the global scope vs non-preferred symbols, which seems reasonable to me. I worry penalizing non-preferred scopes too much can make cross-namespace completion less useable.

clangd/Quality.h

92 ↗

(On Diff #169180)

It seems to me that it'd be less trivial to associate scopes with up/down traverses. Currently, the query scopes contain all enclosing namespaces, so the distance seems less important here. In general, I think the characteristics of scope proximity (e.g. all enclosing namespaces are already in query scopes) allow us to get away with something more trivial than file proximity?

This isn't going to cache for symbols sharing a namespace.

This seems to be less a concern if we are not calculating up/down distance.

isn't going to handle "symbol is in a child namespace of an included namespace"

This can be covered by SymbolScope.startswith(QueryScope)? It might not work well for using-namespaces, but it's unclear how important that is.

Still happy to consider FileDistance-approach as I might be missing something.

[sammccall]

(BTW I wouldn't expect to see improvements on eval here, as

clangd/CodeComplete.cpp

558 ↗

(On Diff #169180)

can you move this function to AST.h? e.g. printScope? It seems like an obvious peer to printQualifiedName.

clangd/Quality.cpp

246 ↗

(On Diff #169180)

Unfortunately, allowing <1 multiplier would make the default value (for sema proximity) tricky.

There are three types of symbols:

• those we get from sema only. Here your patch decides to give max boost (I think?) because we don't trust scope comparison for all these cases.
• those we get from index only. We choose a boost by matching the stated scope to the query scopes.
• those we get from sema and index. We should *probably* treat these like Sema-only and give max boost.

Note the category of results which we have neither sema nor index for doesn't actually exist. The framework allows for it and we should respect that as best we can, but it can't be the top priority.

So can't we just change the SemaScopeProximityScore to bool SemaSaysInScope or something and evaluate as SemaSaysInScope ? MaxBoost : QueryScopeProximity ? evaluateUsingQueryScopeProximity() : 1?

It's ~1/3 only for the global scope vs non-preferred symbols

Queried scopes (not most-preferred, and not the global scope!) get a boost of 1.6, while completely irrelevant scopes get a boost of 1. This is a relative penalty of only 37.5%.
(I think a more reasonable penalty would be in the range of 75% or 80%, i.e. a 3-4x boost for symbols that are in-scope)

clangd/Quality.h

92 ↗

(On Diff #169180)

Currently, the query scopes contain all enclosing namespaces, so the distance seems less important here.

Sure. But there cases like using namespace std and then _1 which should resolve to std::placeholders::_1.
Or being in namespace clang::clangd and wanting to use a symbol clang::tooling::CompilationDatabase.

allow us to get away with something more trivial than file proximity?

Maybe we can. But we should only be trying to get away with it if it's some combination of {less complex, better, faster}. It doesn't seem clear to me that it's any of these.

This isn't going to cache for symbols sharing a namespace.

This seems to be less a concern if we are not calculating up/down distance.

Again, less of a concern, but not obviously a non-issue. With this implementation, you compare the scope string of each symbol to every query scope. With FileDistance, you hash the scope string and then almost-always hit the cache.

This can be covered by SymbolScope.startswith(QueryScope)?

You've updated the code for this, but now you're not giving nested-within-query-scope any penalty compared to directly-in-query-scope. All of this can be implemented, but I don't really understand why - does reusing the impl not seem simpler?

[ioeric]

• refactor to use FileDistance and address review comments.

[sammccall]

clangd/AST.cpp

77 ↗

(On Diff #169814)

It would be nice to have the invariant splitQualifiedName(printQualifiedName(D)) == printScope(D.getContext()) for Decl D.

That's why I was suggesting splitting NamedDecl::printQualifiedName.

Given the limited functionality here it should probably be called printNamespaceScope, lest someone try to reuse it to get a symbol's scope.

clangd/AST.h

51 ↗

(On Diff #169814)

next to printQualifiedName?

clangd/CodeComplete.cpp

562 ↗

(On Diff #169814)

do you also want to use printScope here?

clangd/Quality.cpp

250 ↗

(On Diff #169814)

kepp -> keep

251 ↗

(On Diff #169814)

might be clearer to explicitly prepend "/" rather than relying on normalization to do it?

261 ↗

(On Diff #169814)

My intuition is that mostly the ranking should look like:

1. results from queried namespaces
2. results from nearby namespaces
3. results from unrelated namespaces

That would require Source.Cost < (UpCost, DownCost), which isn't possible when they're 1.
WDYT?

262 ↗

(On Diff #169814)

I thought we concluded down cost was likely to be significantly higher than up cost?

267 ↗

(On Diff #169814)

This seems a little focused on the implementation rather than the intent...
maybe "The global namespace is not 'near' its children"?

272 ↗

(On Diff #169814)

This seems like an odd rule, what's the intuition?

• if the preferred scope is a::b::c:: then we're considering a::b:: and a:: to be equal, rather than preferring the former
• you're defining the cost in terms of UpCost, but it's not clear why - is this just being used as a scale?
• for the direct parent of the preferred scope, this is a no-op. So this only does anything when the preferred scope is at least 3 deep

As a first approximation, ; // just rely on up-traversals might be OK,
otherwise, I guess you're trying to boost these compared to just relying on up-traversals, so I'd expect this to look something like Cost = UpCost * (len(preferred) - len(S)) / 2

274 ↗

(On Diff #169814)

Again, if this just means "parents of preferred are 1, others are 2", I'm not sure that sounds right.
A using-directive is explicit in the user's code, I'm not sure it should rank lower?

Happy enough to try this out as it is though, maybe just drop the references to UpCost.

276 ↗

(On Diff #169814)

Why is this +=?

Seems like there's three cases here:

• global is the preferred scope: I think the cost has to be 0 in this case, no?
• global is another acceptable scope: some large fixed cost seems appropriate
• global is not listed: no source to worry about

287 ↗

(On Diff #169814)

0.6 seems too high for AnyScope matches, to me. And you're not distinguishing anyScope matches from bad path matches.

I think the linear scale is too flat: if you're in clang::clangd::, then clangd symbols will only get a 13% boost over clang ones.

Given the current UpCost == DownCost == 1, I'd consider something like

if (D == FileDistance::Unreachable)
  return 0.1;
return max(0.5, MaxBoost * pow(0.6, D))

382 ↗

(On Diff #169814)

hmm, if you have no scopes in the query I think you're boosting the sema results and not the index ones. Intended?

clangd/Quality.h

83 ↗

(On Diff #169814)

This is mechanism, not signals, and makes this header harder to understand.

Can you move the string-translation/wrapping part to FileDistance.h (returning Distance) and the boost part to Quality.cpp?

84 ↗

(On Diff #169814)

clang-format

93 ↗

(On Diff #169814)

why is this optional? does FileDistance not work with an empty set of roots?
If the idea is to avoid downranking everything if there are no scopes, QueryScopeProximity itself is already optional.

94 ↗

(On Diff #169814)

unused

106 ↗

(On Diff #169814)

you've now got scope-proximity and file-proximity info interleaved. These are analogous signals, but separate, so probably clearest to group each one.

[ioeric]

• Addressed review comments.

[ioeric]

Thanks for the suggestions! After taking a closer look at boosting factors for other signals, I think I was being too conservative about boosting preferred scopes and penalizing non-preferred ones. I have tuned the parameters to make these more aggressive now according to your suggestion.

clangd/Quality.cpp

262 ↗

(On Diff #169814)

Sorry, forgot to make that change. Made UpCost=1, DownCost=2

272 ↗

(On Diff #169814)

As a first approximation, ; // just rely on up-traversals might be OK,

This sounds good to me.

276 ↗

(On Diff #169814)

global is the preferred scope: I think the cost has to be 0 in this case, no?

I think we should still apply some penalty here because

1. All projects can define symbols in the global scope. For example, if I work on a project without namespace, symbols from global namespaces are not necessarily relevant.
2. A use pattern is that using-namespace is used in place of enclosing namespaces in implementation files.

Otherwise, done.

287 ↗

(On Diff #169814)

Done except for the scope for unreachable paths.

I think 0.1 is too much penalty and would probably make cross-namespace completions not useful. As cross-namespace completion is not enabled by default, it should be safe to give it a higher score (0.4?).

382 ↗

(On Diff #169814)

Not intended. Changed to only boost scopes if there are query scopes.

[sammccall]

Awesome! Just nits.

clangd/CodeComplete.cpp

1224 ↗

(On Diff #169962)

, if there are scopes?

clangd/FileDistance.cpp

206 ↗

(On Diff #169962)

I think this sets MaxUpTraversals to -1 for the empty scope.
*probably* harmless in the end, but I think an explicit if !S.empty() might be clearer

clangd/FileDistance.h

125 ↗

(On Diff #169962)

nit: It seems slightly odd to make this a unique_ptr just to make the constructor simpler - could also just define a helper function in the CC file that the constructor could call: ScopeDistance::ScopeDistance(ArrayRef<string> Scopes) : Distance(createScopeFileDistance(Scopes))

[ioeric]

• address comments

[ioeric]

• rebase

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

 /// The returned location is usually the spelling location where the name of the
 /// decl occurs in the code.
 SourceLocation findNameLoc(const clang::Decl *D);
 
 /// Returns the qualified name of ND. The scope doesn't contain unwritten scopes
 /// like inline namespaces.
 std::string printQualifiedName(const NamedDecl &ND);
 
+/// Returns the first enclosing namespace scope starting from \p DC.
+std::string printNamespaceScope(const DeclContext &DC);
+
 /// Gets the symbol ID for a declaration, if possible.
 llvm::Optional<SymbolID> getSymbolID(const Decl *D);
 
 /// Gets the symbol ID for a macro, if possible.
 /// Currently, this is an encoded USR of the macro, which incorporates macro
 /// locations (e.g. file name, offset in file).
 /// FIXME: the USR semantics might not be stable enough as the ID for index
 /// macro (e.g. a change in definition offset can result in a different USR). We

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

std::string printQualifiedName(const NamedDecl &ND) {
   // namespaces to query: the preamble doesn't have a dedicated list.
   Policy.SuppressUnwrittenScope = true;
   ND.printQualifiedName(OS, Policy);
   OS.flush();
   assert(!StringRef(QName).startswith("::"));
   return QName;
 }
 
+std::string printNamespaceScope(const DeclContext &DC) {
+  for (const auto *Ctx = &DC; Ctx != nullptr; Ctx = Ctx->getParent())
+    if (const auto *NS = dyn_cast<NamespaceDecl>(Ctx))
+      if (!NS->isAnonymousNamespace() && !NS->isInlineNamespace())
+        return printQualifiedName(*NS) + "::";
+  return "";
+}
+
 llvm::Optional<SymbolID> getSymbolID(const Decl *D) {
   llvm::SmallString<128> USR;
   if (index::generateUSRForDecl(D, USR))
     return None;
   return SymbolID(USR);
 }
 
 llvm::Optional<SymbolID> getSymbolID(const IdentifierInfo &II,

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

 #include "Headers.h"
 #include "Logger.h"
 #include "Quality.h"
 #include "SourceCode.h"
 #include "TUScheduler.h"
 #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"
 #include "clang/Format/Format.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Frontend/FrontendActions.h"
 #include "clang/Lex/PreprocessorOptions.h"
 #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"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/ScopedPrinter.h"
 #include <algorithm>
 #include <iterator>
for (llvm::StringRef AS : AccessibleScopes) {
       if (UnresolvedQualifier)
         Results.back() += *UnresolvedQualifier;
     }
     return Results;
   }
 };
 
 // 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<std::vector<std::string>, bool>
-getQueryScopes(CodeCompletionContext &CCContext, const SourceManager &SM,
+getQueryScopes(CodeCompletionContext &CCContext, const Sema &CCSema,
                const CodeCompleteOptions &Opts) {
   auto GetAllAccessibleScopes = [](CodeCompletionContext &CCContext) {
     SpecifiedScope Info;
     for (auto *Context : CCContext.getVisitedContexts()) {
       if (isa<TranslationUnitDecl>(Context))
         Info.AccessibleScopes.push_back(""); // global namespace
       else if (const auto *NS = dyn_cast<NamespaceDecl>(Context))
-        Info.AccessibleScopes.push_back(NS->getQualifiedNameAsString() + "::");
+        Info.AccessibleScopes.push_back(printNamespaceScope(*Context));
     }
     return Info;
   };
 
   auto SS = CCContext.getCXXScopeSpecifier();
 
   // 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<std::string> Scopes;
+    std::string EnclosingScope = printNamespaceScope(*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};
   }
 
   // Qualified completion ("std::vec^"), we have two cases depending on whether
   // the qualifier can be resolved by Sema.
   if ((*SS)->isValid()) { // Resolved qualifier.
     return {GetAllAccessibleScopes(CCContext).scopesForIndexQuery(), false};
   }
 
   // Unresolved qualifier.
   // FIXME: When Sema can resolve part of a scope chain (e.g.
   // "known::unknown::id"), we should expand the known part ("known::") rather
   // than treating the whole thing as unknown.
   SpecifiedScope Info;
   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())
     *Info.UnresolvedQualifier += "::";
 
   return {Info.scopesForIndexQuery(), false};
 }
 
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.
+  // Initialized once QueryScopes is initialized, if there are scopes.
+  llvm::Optional<ScopeDistance> 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.
   // 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.
CodeCompleteResult runWithSema() {
     } else {
       const auto &Pos = sourceLocToPosition(
           Recorder->CCSema->getSourceManager(),
           Recorder->CCSema->getPreprocessor().getCodeCompletionLoc());
       TextEditRange.start = TextEditRange.end = Pos;
     }
     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);
+    if (!QueryScopes.empty())
+      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.
     //        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:
   // 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 = Recorder->CCContext.getKind();
     Relevance.Query = SymbolRelevanceSignals::CodeComplete;
     Relevance.FileProximityMatch = FileProximity.getPointer();
-    // FIXME: incorparate scope proximity into relevance score.
+    if (ScopeProximity)
+      Relevance.ScopeProximityMatch = ScopeProximity.getPointer();
 
     auto &First = Bundle.front();
     if (auto FuzzyScore = fuzzyScore(First))
       Relevance.NameMatch = *FuzzyScore;
     else
       return;
     SymbolOrigin Origin = SymbolOrigin::Unknown;
     bool FromIndex = false;

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

 #include "URI.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseMapInfo.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/StringSaver.h"
+#include <memory>
 
 namespace clang {
 namespace clangd {
 
 struct FileDistanceOptions {
   unsigned UpCost = 2;      // |foo/bar.h -> foo|
   unsigned DownCost = 1;    // |foo -> foo/bar.h|
   unsigned IncludeCost = 2; // |foo.cc -> included_header.h|
private:
 
   // We cache the results using the original strings so we can skip URI parsing.
   llvm::DenseMap<llvm::hash_code, unsigned> Cache;
   llvm::StringMap<SourceParams> Sources;
   llvm::StringMap<std::unique_ptr<FileDistance>> ByScheme;
   FileDistanceOptions Opts;
 };
 
+/// Support lookups like FileDistance, but the lookup keys are symbol scopes.
+/// For example, a scope "na::nb::" is converted to "/na/nb".
+class ScopeDistance {
+public:
+  /// QueryScopes[0] is the preferred scope.
+  ScopeDistance(llvm::ArrayRef<std::string> QueryScopes);
+
+  unsigned distance(llvm::StringRef SymbolScope);
+
+private:
+  FileDistance Distance;
+};
+
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_FILEDISTANCE_H

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

if (!Delegate) {
     }
     dlog("FileDistance for scheme {0}: {1}/{2} sources", Scheme,
          SchemeSources.size(), Sources.size());
     Delegate.reset(new FileDistance(std::move(SchemeSources), Opts));
   }
   return *Delegate;
 }
 
+static std::pair<std::string, int> scopeToPath(llvm::StringRef Scope) {
+  SmallVector<StringRef, 4> Split;
+  Scope.split(Split, "::", /*MaxSplit=*/-1, /*KeepEmpty=*/false);
+  return {"/" + llvm::join(Split, "/"), Split.size()};
+}
+
+static FileDistance
+createScopeFileDistance(llvm::ArrayRef<std::string> QueryScopes) {
+  FileDistanceOptions Opts;
+  Opts.UpCost = 2;
+  Opts.DownCost = 4;
+  Opts.AllowDownTraversalFromRoot = false;
+
+  StringMap<SourceParams> Sources;
+  StringRef Preferred = QueryScopes.empty() ? "" : QueryScopes.front().c_str();
+  for (StringRef S : QueryScopes) {
+    SourceParams Param;
+    // Penalize the global scope even it's preferred, as all projects can define
+    // symbols in it, and there is pattern where using-namespace is used in
+    // place of enclosing namespaces (e.g. in implementation files).
+    if (S == Preferred)
+      Param.Cost = S == "" ? 2 : 0;
+    else if (Preferred.startswith(S) && !S.empty())
+      continue; // just rely on up-traversals.
+    else
+      Param.Cost = S == "" ? 5 : 2;
+    auto Path = scopeToPath(S);
+    // The global namespace is not 'near' its children.
+    Param.MaxUpTraversals = std::max(Path.second - 1, 0);
+    Sources[Path.first] = std::move(Param);
+  }
+  return FileDistance(Sources, Opts);
+}
+
+ScopeDistance::ScopeDistance(llvm::ArrayRef<std::string> QueryScopes)
+    : Distance(createScopeFileDistance(QueryScopes)) {}
+
+unsigned ScopeDistance::distance(llvm::StringRef SymbolScope) {
+  return Distance.distance(scopeToPath(SymbolScope).first);
+}
+
 } // namespace clangd
 } // namespace clang

clang-tools-extra/trunk/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 "FileDistance.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 {
   /// 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).
   /// 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
+  /// 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.
   /// 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;
+
+  // 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;
 
   // An approximate measure of where we expect the symbol to be used.
   enum AccessibleScope {
     FunctionScope,
     ClassScope,
     FileScope,
     GlobalScope,
   } Scope = GlobalScope;

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

 #include "clang/AST/ASTContext.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/DeclTemplate.h"
 #include "clang/AST/DeclVisitor.h"
 #include "clang/Basic/CharInfo.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Sema/CodeCompleteConsumer.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/SmallVector.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 <algorithm>
 #include <cmath>
 
 namespace clang {
 namespace clangd {
 using namespace llvm;
 static bool isReserved(StringRef Name) {
   // FIXME: Should we exclude _Bool and others recognized by the standard?
   return Name.size() >= 2 && Name[0] == '_' &&
computeScope(const NamedDecl *D) {
   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.
 
   SymbolURI = IndexResult.CanonicalDeclaration.FileURI;
+  SymbolScope = IndexResult.Scope;
   IsInstanceMember |= isInstanceMember(IndexResult.SymInfo);
 }
 
 void SymbolRelevanceSignals::merge(const CodeCompletionResult &SemaCCResult) {
   if (SemaCCResult.Availability == CXAvailability_NotAvailable ||
       SemaCCResult.Availability == CXAvailability_NotAccessible)
     Forbidden = true;
 
   if (SemaCCResult.Declaration) {
+    SemaSaysInScope = true;
     // 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.
     float DeclProximity = (hasDeclInMainFile(*SemaCCResult.Declaration) ||
                            hasUsingDeclInMainFile(SemaCCResult))
                               ? 1.0
                               : 0.6;
-    SemaProximityScore = std::max(DeclProximity, SemaProximityScore);
+    SemaFileProximityScore = std::max(DeclProximity, SemaFileProximityScore);
     IsInstanceMember |= isInstanceMember(SemaCCResult.Declaration);
   }
 
   // Declarations are scoped, others (like macros) are assumed global.
   if (SemaCCResult.Declaration)
     Scope = std::min(Scope, computeScope(SemaCCResult.Declaration));
 
   NeedsFixIts = !SemaCCResult.FixIts.empty();
 }
 
-static std::pair<float, unsigned> proximityScore(llvm::StringRef SymbolURI,
-                                                 URIDistance *D) {
+static std::pair<float, unsigned> uriProximity(llvm::StringRef SymbolURI,
   if (!D || SymbolURI.empty())
     return {0.f, 0u};
   unsigned Distance = D->distance(SymbolURI);
   // Assume approximately default options are used for sensible scoring.
   return {std::exp(Distance * -0.4f / FileDistanceOptions().UpCost), Distance};
 }
 
+static float scopeBoost(ScopeDistance &Distance,
+                        llvm::Optional<llvm::StringRef> SymbolScope) {
+  if (!SymbolScope)
+    return 1;
+  auto D = Distance.distance(*SymbolScope);
+  if (D == FileDistance::Unreachable)
+    return 0.4;
+  return std::max(0.5, 2.0 * std::pow(0.6, D / 2.0));
+}
+
 float SymbolRelevanceSignals::evaluate() const {
   float Score = 1;
 
   if (Forbidden)
     return 0;
 
   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);
+
+  if (ScopeProximityMatch)
+    // Use a constant scope boost for sema results, as scopes of sema results
+    // can be tricky (e.g. class/function scope). Set to the max boost as we
+    // don't load top-level symbols from the preamble and sema results are
+    // always in the accessible scope.
+    Score *=
+        SemaSaysInScope ? 2.0 : scopeBoost(*ScopeProximityMatch, SymbolScope);
 
   // 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:

 
 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("\tQuery type: {0}\n", static_cast<int>(S.Query));
+  OS << formatv("\tScope: {0}\n", static_cast<int>(S.Scope));
+
   OS << formatv("\tSymbol URI: {0}\n", S.SymbolURI);
+  OS << formatv("\tSymbol scope: {0}\n",
+                S.SymbolScope ? *S.SymbolScope : "<None>");
+
   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<int>(S.Query));
-  OS << formatv("\tScope: {0}\n", static_cast<int>(S.Scope));
+  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));
+
   return OS;
 }
 
 float evaluateSymbolAndRelevance(float SymbolQuality, float SymbolRelevance) {
   return SymbolQuality * SymbolRelevance;
 }
 
 // Produces an integer that sorts in the same order as F.

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

auto Requests = captureIndexRequests(R"cpp(
       }
   )cpp");
 
   EXPECT_THAT(Requests,
               ElementsAre(Field(&FuzzyFindRequest::Scopes,
                                 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::"))));
+  EXPECT_EQ(Requests[0].Scopes[0], "nx::ns::");
+}
+
 TEST(CompletionTest, ResolvedQualifiedIdQuery) {
   auto Requests = captureIndexRequests(R"cpp(
       namespace ns1 {}
       namespace ns2 {} // ignore
       namespace ns3 { namespace nns3 {} }
       namespace foo {
       using namespace ns1;
       using namespace ns3::nns3;

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

TEST(FileDistance, DisallowDownTraversalsFromRoot) {
 
   FileDistance D({{"/", SourceParams()}, {"/a/b/c", CostLots}}, Opts);
   EXPECT_EQ(D.distance("/"), 0u);
   EXPECT_EQ(D.distance("/a"), 102u);
   EXPECT_EQ(D.distance("/a/b"), 101u);
   EXPECT_EQ(D.distance("/x"), FileDistance::Unreachable);
 }
 
+TEST(ScopeDistance, Smoke) {
+  ScopeDistance D({"x::y::z", "x::", "", "a::"});
+  EXPECT_EQ(D.distance("x::y::z::"), 0u);
+  EXPECT_GT(D.distance("x::y::"), D.distance("x::y::z::"));
+  EXPECT_GT(D.distance("x::"), D.distance("x::y::"));
+  EXPECT_GT(D.distance("x::y::z::down::"), D.distance("x::y::"));
+  EXPECT_GT(D.distance(""), D.distance("a::"));
+  EXPECT_GT(D.distance("x::"), D.distance("a::"));
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang

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

 #include "TestTU.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/Type.h"
 #include "clang/Sema/CodeCompleteConsumer.h"
 #include "llvm/Support/Casting.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
+#include <vector>
 
 namespace clang {
 namespace clangd {
 
 // Force the unittest URI scheme to be linked,
 static int LLVM_ATTRIBUTE_UNUSED UnittestSchemeAnchorDest =
     UnittestSchemeAnchorSource;
 
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.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) {
     auto *Shadow =
         *dyn_cast<UsingDecl>(
              &findAnyDecl(AST,
                           [&](const NamedDecl &ND) {
                             if (const UsingDecl *Using =
                                     dyn_cast<UsingDecl>(&ND))
                               if (Using->shadow_size() &&
                                   Using->getQualifiedNameAsString() == DeclName)
                                 return true;
                             return false;
                           }))
              ->shadow_begin();
     CodeCompletionResult Result(Shadow->getTargetDecl(), 42);
     Result.ShadowDecl = Shadow;
     return Result;
   };
 
   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 = {};
   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);
TEST(QualityTests, SymbolRelevanceSignalsSanity) {
   SymbolRelevanceSignals Forbidden;
   Forbidden.Forbidden = true;
   EXPECT_LT(Forbidden.evaluate(), Default.evaluate());
 
   SymbolRelevanceSignals PoorNameMatch;
   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());
+
+  ScopeDistance ScopeProximity({"x::y::"});
+
+  SymbolRelevanceSignals WithSemaScopeProximity;
+  WithSemaScopeProximity.ScopeProximityMatch = &ScopeProximity;
+  WithSemaScopeProximity.SemaSaysInScope = true;
+  EXPECT_GT(WithSemaScopeProximity.evaluate(), Default.evaluate());
+
+  SymbolRelevanceSignals WithIndexScopeProximity;
+  WithIndexScopeProximity.ScopeProximityMatch = &ScopeProximity;
+  WithIndexScopeProximity.SymbolScope = "x::";
+  EXPECT_GT(WithSemaScopeProximity.evaluate(), Default.evaluate());
 
   SymbolRelevanceSignals IndexProximate;
   IndexProximate.SymbolURI = "unittest:/foo/bar.h";
   llvm::StringMap<SourceParams> ProxSources;
   ProxSources.try_emplace(testPath("foo/baz.h"));
   URIDistance Distance(ProxSources);
   IndexProximate.FileProximityMatch = &Distance;
   EXPECT_GT(IndexProximate.evaluate(), Default.evaluate());
TEST(QualityTests, SymbolRelevanceSignalsSanity) {
   Instance.IsInstanceMember = false;
   EXPECT_EQ(Instance.evaluate(), Default.evaluate());
   Instance.Context = CodeCompletionContext::CCC_DotMemberAccess;
   EXPECT_LT(Instance.evaluate(), Default.evaluate());
   Instance.IsInstanceMember = true;
   EXPECT_EQ(Instance.evaluate(), Default.evaluate());
 }
 
+TEST(QualityTests, ScopeProximity) {
+  SymbolRelevanceSignals Relevance;
+  ScopeDistance ScopeProximity({"x::y::z::", "x::", "llvm::", ""});
+  Relevance.ScopeProximityMatch = &ScopeProximity;
+
+  Relevance.SymbolScope = "other::";
+  float NotMatched = Relevance.evaluate();
+
+  Relevance.SymbolScope = "";
+  float Global = Relevance.evaluate();
+  EXPECT_GT(Global, NotMatched);
+
+  Relevance.SymbolScope = "llvm::";
+  float NonParent = Relevance.evaluate();
+  EXPECT_GT(NonParent, Global);
+
+  Relevance.SymbolScope = "x::";
+  float GrandParent = Relevance.evaluate();
+  EXPECT_GT(GrandParent, Global);
+
+  Relevance.SymbolScope = "x::y::";
+  float Parent = Relevance.evaluate();
+  EXPECT_GT(Parent, GrandParent);
+
+  Relevance.SymbolScope = "x::y::z::";
+  float Enclosing = Relevance.evaluate();
+  EXPECT_GT(Enclosing, Parent);
+}
+
 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));
   EXPECT_LT(sortText(-10), sortText(-std::numeric_limits<float>::infinity()));