[clangd] Boost completion score according to file proximity.

[ioeric]

Summary

Also move unittest: URI scheme to TestFS so that it can be shared by
different tests.

[ioeric]

Rebase on D47931

[ioeric]

• Rebase again...

[sammccall]

Can you benchmark this? I'm nervous about the URI stuff in the hot path.
Timing CodeCompleteFlow::measureResults before/after with index enabled seems like a reasonable test.
(But you might want to make this apply to sema first too for realistic numbers?)

clangd/Quality.cpp

203 ↗

(On Diff #150477)

how do we know proximitypath is set at this point?
Better to copy the symbol URL path I think :-(

208 ↗

(On Diff #150477)

Why U->toString() rather than ->body()?

215 ↗

(On Diff #150477)

proximity path needs to be set here too

clangd/Quality.h

74 ↗

(On Diff #150477)

It seems OK to have ProximityPath or ProximityScore, but we shouldn't have both: drop proximityscore and calculate it during evaluate()?

[sammccall]

Oops, couple more comments.
But the big things I think are:

• what's the performance impact of doing all this work (including the URI stuff) inside the scoring loop?
• what's the most useful formula for the proximity score

clangd/Quality.cpp

171 ↗

(On Diff #150477)

This doesn't look quite right to me.
We can tune the details later, but in practice this seems like it's *very* hard to get zero proximity, which is our neutral score - you need to be 18 directories away?

FWIW, fozzie appears to give an additive boost proportional to 5-up, where up is the number of directories from the context you have to traverse up from the context to get to a parent of the symbol. (There's no penalty for down-traversals probably for implementation reasons, this should be smaller than the up-traversal penalty I think)

clangd/Quality.h

74 ↗

(On Diff #150477)

what's the plan for associated-header? should this be a smallvector<2>?

[ioeric]

In D47935#1126283, @sammccall wrote:

Can you benchmark this? I'm nervous about the URI stuff in the hot path.
Timing CodeCompleteFlow::measureResults before/after with index enabled seems like a reasonable test.
(But you might want to make this apply to sema first too for realistic numbers?)

Sure! I had some numbers but they are on some paper that I don't access to right now... will collect some new figures (with URI manipulations in sema).

clangd/Quality.cpp

171 ↗

(On Diff #150477)

The numbers are guessed... definitely happy to tune.

We can tune the details later, but in practice this seems like it's *very* hard to get zero proximity, which is our neutral score - you need to be 18 directories away?

It's 18 directories away if one file is in an ancestor directories of the other (i.e. only traverse up or down). If you need to traverse up and down, the penalty for each directory is 0.1, which takes 10 directories (up+down, so
5 up in average). I think it's useful to make this distinction because I think it's more likely for a file to use a header if it's in the file path.

I'm not sure if we should use zero as the neutral score. For example, if a codebase has deep directory structure, most scores are probably going to be small; conversely, most scores would be relatively big. I think relative scores are more useful.

(There's no penalty for down-traversals probably for implementation reasons, this should be smaller than the up-traversal penalty I think)

Why do you think down-traversal should take less penalty?

208 ↗

(On Diff #150477)

Because both URIs need to be parsed in order to use body(). Here we don't parse SymURI.

215 ↗

(On Diff #150477)

Alternatively, I wonder if we could give sema result a fixed proximity score as they are symbols that are already included?

clangd/Quality.h

74 ↗

(On Diff #150477)

Just want to make sure I understand. We would copy the symbol URI to use in merge right?

74 ↗

(On Diff #150477)

I think it should be easy to change this to vector when it's actually needed?

[ioeric]

Here are some numbers by completing "clang::^" 40 times (with result limit 1000 instead of 100).

Timing in CodeCompleteFlow::measureResults

Before: Avg: 1811 us Med: 1792 us 
After: Avg: 2714 us Med: 2689 us

As a reference, a full CodeCompleteFlow (with 1000 candidates) takes ~70 ms (using LLVM's yaml index).

So, with the current limit of 100 results, the increase for measureResults should be roughly 0.18ms -> 0.27ms, which I think is reasonable.

[ioeric]

• Merge branch 'uri' into proximity
• Addressed review comments.

[ioeric]

• Cleanup comment a bit.

[ioeric]

PTAL

clangd/Quality.cpp

215 ↗

(On Diff #150477)

As discussed offline, sema symbols now have a fixed proximity score (not entirely sure about the value though).

clangd/Quality.h

74 ↗

(On Diff #150477)

Changed to vector anyway...

74 ↗

(On Diff #150477)

Experimented with this a bit (removing ProximityScore). As we print the proximity score for debugging, we would still want to keep the store. Alternatively, I made the proximity paths a parameter of merge as we only use them for index result anyway.

[sammccall]

Sorry for the delay on this change. There's a bunch of complexity in this problem that I haven't seen how to slice through:

1. the signals needed seem like a weird fit for the Symbol*Signals structs for some reason (maybe my misdesign)
2. the inconsistency between how we do this for Sema and for Index results has... only slightly good reasons
3. the URI vs filename thing is awkward
4. with all this, the actual scoring still seems ad-hoc and is missing important parts (main header, transitive includes)

Not all your fault that the code reflects this, the problem is tangly. But it's hard for me to reason about APIs or performance or layering.

Looking at the last point (scoring model) because it seems the most tractable. I think this is basically an edit distance problem?
(We can call the result "proximity", start at one, and multiply by <1, or call it "distance" and start at 0 and add penalties, but it's equivalent).

• we're computing distances between files (glossing over URI-space vs file-space)
• the roots are the main file, and maybe the matching header
• edits take us from a filepath to a related filepath:
  • from a file to a header it #includes
  • from a file to its parent directory
  • from a parent directory to a child directory
  • from a parent directory to a file in it
• the distance is the smallest sum-of-penalties for any path leading from the root to the symbol

What do you think of this model?

---

If the model seems reasonable, then it suggests an approach of building a one-per-query data structure that computes the needed edit-distance recursively, memoizing results. SymbolRelevanceResults could store the symbol path and a pointer to the edit-distance machine, and for debugging the machine would know how to describe its configuration. URI/path mapping wouldn't be a performance concern (I think) if the memoization captured it.

Let's chat offline?

clangd/Quality.cpp

171 ↗

(On Diff #150477)

If you need to traverse up and down, the penalty for each directory is 0.1, which takes 10 directories (up+down, so 5 up in average).

I think you've halved twice there - it still seems to be 10, which is a lot.

I'm not sure if we should use zero as the neutral score.

Well, zero is currently the neutral score, and this patch doesn't change it :-)
I think starting at 1 for the current file and *multiplying* by p<1 to apply penalties should give a reasonable 0-1 score that's relatively sane even for codebases of different sizes. Happy to have a different model, but you need to explain/implement how it combines with other signals.

Why do you think down-traversal should take less penalty?

Intuitively, because subprojects are more closely related than superprojects. But this didn't occur to me until someone mentioned it, we should check with Matei and Alexander.

[ioeric]

• Introduced a one-per-query structure for relevance signals; use multiplication for proximity; simplify tests a bit; separate index and sema proximity scores.

[ioeric]

In D47935#1129987, @sammccall wrote:

Sorry for the delay on this change. There's a bunch of complexity in this problem that I haven't seen how to slice through:

1. the signals needed seem like a weird fit for the Symbol*Signals structs for some reason (maybe my misdesign)

According to offline discussion, I added a structure SymbolRelevanceContext that captures per-query signals like proximity paths. Not sure about the name though.

2. the inconsistency between how we do this for Sema and for Index results has... only slightly good reasons

The proximity scores for index and sema are now explicitly separated to make it easier to understand and debug.

3. the URI vs filename thing is awkward
4. with all this, the actual scoring still seems ad-hoc and is missing important parts (main header, transitive includes)

Not all your fault that the code reflects this, the problem is tangly. But it's hard for me to reason about APIs or performance or layering.

Looking at the last point (scoring model) because it seems the most tractable. I think this is basically an edit distance problem?
(We can call the result "proximity", start at one, and multiply by <1, or call it "distance" and start at 0 and add penalties, but it's equivalent).

• we're computing distances between files (glossing over URI-space vs file-space)
• the roots are the main file, and maybe the matching header
• edits take us from a filepath to a related filepath:
  • from a file to a header it #includes
  • from a file to its parent directory
  • from a parent directory to a child directory
  • from a parent directory to a file in it
• the distance is the smallest sum-of-penalties for any path leading from the root to the symbol

What do you think of this model?

---

If the model seems reasonable, then it suggests an approach of building a one-per-query data structure that computes the needed edit-distance recursively, memoizing results. SymbolRelevanceResults could store the symbol path and a pointer to the edit-distance machine, and for debugging the machine would know how to describe its configuration. URI/path mapping wouldn't be a performance concern (I think) if the memoization captured it.

I like how this model addresses the proximity for src/ and include/ setup. I think we could start with something simple and iterate, although I agree that we should strike for a design that would be easy to replace the proximity algorithm in the future.

Let's chat offline?

clangd/Quality.cpp

171 ↗

(On Diff #150477)

I think you've halved twice there - it still seems to be 10, which is a lot.

OK you are right. It would behave badly when there are many ups and only one down.

I think starting at 1 for the current file and *multiplying* by p<1 to apply penalties should give a reasonable 0-1 score that's relatively sane even for codebases of different sizes.

Sounds good. Picked p=0.7 which seems to give reasonable scores.

[ioeric]

• Rebased.

[sammccall]

Thanks, this looks much clearer/more modular/more extensible to me!
A couple of notes on the abstractions before digging into details again.

clangd/Quality.h

71 ↗

(On Diff #151172)

This is ambiguously a couple of different (and good!) things:

• an encapsulation of the proximitypaths state and logic
• a grouping together of the "query-dependent, symbol-invariant" inputs to the relevance calculation.

There's a place for both of these, but I'd argue for separating them (and only doing the second in this patch). Reasons:

• the former doesn't need to be in this file if it gets complex (FuzzyMatch.h is a similar case), while the latter does
• easier to understand/name if this hierarchy is expressed explicitly
• I suspect we may want the context to be a separate struct, passed to SymbolRelevanceSignals::evaluate(), rather than a member of SymbolRelevanceSignals. That would add more churn than needs to be in this patch though.

If this makes sense to you then I think this class looks great but should be called something specific like FileProximityMatcher.

91 ↗

(On Diff #151172)

One of the simplifying assumptions in the model is that all signals are optional - can we make Context a pointer = nullptr and drop the constructor?

[ioeric]

• addressed review comments.

[ioeric]

• Rebase...

[ioeric]

clangd/Quality.h

71 ↗

(On Diff #151172)

Sounds good. Thanks for the explanation!

[sammccall]

Thanks, just details now!

clangd/Quality.cpp

185 ↗

(On Diff #151322)

why is this a special case?

• /x/a/b vs /x/a/c is 1 up + 1 down --> 0.59
• /a/b vs /a/c is 1 up + 1 down --> 0.59
• /b vs /c is unrelated --> 0

I don't doubt the assertion that these are unrelated paths, but I'm not sure fixing just this case is an improvement overall. (In a perfect world, we'd define the algorithm so that this case yields 0 without a discontinuity)

216 ↗

(On Diff #151322)

For composability, you could consider styling more tersely e.g. as ProximityPaths{/path/to/file}, and in the RelevanceSignals operator<< including it like other fields, yielding:

== Symbol relevance: 0.8 ==
 Name match: 0.7
 File proximity matcher: ProximityPaths{/path/to/file}
 ...

clangd/Quality.h

78 ↗

(On Diff #151322)

Should mention the semantics of the score, maybe via the other extreme: when the SymbolURI exactly matches a proximity path, score is 1.

98 ↗

(On Diff #151322)

This is redundant with (IndexSymbolURI, FileProximityMatch) I think, and will only be correctly set if FileProximityMatch is set before calling merge(Symbol).

Can we defer calculation until evaluate()?
(If you want to dump this intermediate score, you can recompute it in operator<<, I'm not sure it's necessary).

unittests/clangd/TestFS.cpp

66 ↗

(On Diff #151322)

These helpers would be more coherent if this used the same test root as above - any reason we can't do that?

Then this comment could just be "unittest: is a scheme that refers to files relative to testRoot()"

107 ↗

(On Diff #151322)

This is really surprising to me - is this the common pattern for registries?
(i.e. we don't have something more declarative like bazel's cc_library.alwayslink)?

If so, can we move the declaration to TestFS.h and give a usage example, so the consuming libraries don't have to repeat the decl?

[ioeric]

• addressed review comments

clangd/Quality.cpp

185 ↗

(On Diff #151322)

The intuition is that when we hit the root, it's very likely that we are switching projects. But we could leave this out of the patch and evaluate whether this is an improvement later.

clangd/Quality.h

98 ↗

(On Diff #151322)

Done.

(If you want to dump this intermediate score, you can recompute it in operator<<, I'm not sure it's necessary).

I think the proximity score would be useful for debugging, no?

unittests/clangd/TestFS.cpp

66 ↗

(On Diff #151322)

Good idea.

107 ↗

(On Diff #151322)

yeah... this pattern is also used in tooling::CompilationDatabase (e.g. https://github.com/llvm-mirror/clang/blob/master/lib/Tooling/CompilationDatabase.cpp#L398), and I'm not aware of a good way to deal without alwayslink.

If so, can we move the declaration to TestFS.h and give a usage example, so the consuming libraries don't have to repeat the decl?

Done.

[sammccall]

Thanks! Just nits

clangd/Quality.cpp

304 ↗

(On Diff #151358)

No camel case here, just words

305 ↗

(On Diff #151358)

Could this just be inlined like the others?

Index proximity: 0.5 (ProximityRoots{foo/bar.h})

clangd/Quality.h

71 ↗

(On Diff #151358)

nit: can we forward declare this here and move it down (e.g. above TopN) to keep the signals at the top?
(I suspect it'll end up in another header eventually)

99 ↗

(On Diff #151358)

nit: just SymbolURI (signals should be conceptually source-independent, may be missing)

101 ↗

(On Diff #151358)

can you add a FIXME to unify with index proximity score? signals should be source-independent

unittests/clangd/TestFS.h

60 ↗

(On Diff #151358)

document the unittest: scheme here?

[ioeric]

• addressed review comments and rebase.

[ioeric]

Thanks for the review!

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

class CodeCompleteFlow {
   PathRef FileName;
   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::unique_ptr<IncludeInserter> Includes; // Initialized once compiler runs.
+  FileProximityMatcher FileProximityMatch;
 
 public:
   // A CodeCompleteFlow object is only useful for calling run() exactly once.
   CodeCompleteFlow(PathRef FileName, const CodeCompleteOptions &Opts)
-      : FileName(FileName), Opts(Opts) {}
+      : FileName(FileName), Opts(Opts),
+        // FIXME: also use path of the main header corresponding to FileName to
+        // calculate the file proximity, which would capture include/ and src/
+        // project setup where headers and implementations are not in the same
+        // directory.
+        FileProximityMatch({FileName}) {}
 
   CompletionList run(const SemaCompleteInput &SemaCCInput) && {
     trace::Span Tracer("CodeCompleteFlow");
 
     // We run Sema code completion first. It builds an AST and calculates:
     //   - completion results based on the AST.
     //   - partial identifier and context. We need these for the index query.
     CompletionList Output;
void addCandidate(TopN<ScoredCandidate, ScoredCandidateGreater> &Candidates,
     CompletionCandidate C;
     C.SemaResult = SemaResult;
     C.IndexResult = IndexResult;
     C.Name = IndexResult ? IndexResult->Name : Recorder->getName(*SemaResult);
 
     SymbolQualitySignals Quality;
     SymbolRelevanceSignals Relevance;
     Relevance.Query = SymbolRelevanceSignals::CodeComplete;
+    Relevance.FileProximityMatch = &FileProximityMatch;
     if (auto FuzzyScore = fuzzyScore(C))
       Relevance.NameMatch = *FuzzyScore;
     else
       return;
     if (IndexResult) {
       Quality.merge(*IndexResult);
       Relevance.merge(*IndexResult);
     }

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

 ///     consistent regardless of the source.
 ///   - 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 "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/StringRef.h"
 #include <algorithm>
 #include <functional>
 #include <vector>
 namespace llvm {
 class raw_ostream;
 }
 namespace clang {
struct SymbolQualitySignals {
   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 SymbolQualitySignals &);
 
+class FileProximityMatcher;
+
 /// 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).
+
+  const FileProximityMatcher *FileProximityMatch = nullptr;
+  /// This is 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.
-  float ProximityScore = 0;
+  /// 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,
     ClassScope,
     FileScope,
     GlobalScope,
   } Scope = GlobalScope;
struct SymbolRelevanceSignals {
   float evaluate() const;
 };
 llvm::raw_ostream &operator<<(llvm::raw_ostream &,
                               const SymbolRelevanceSignals &);
 
 /// Combine symbol quality and relevance into a single score.
 float evaluateSymbolAndRelevance(float SymbolQuality, float SymbolRelevance);
 
+class FileProximityMatcher {
+  public:
+    /// \p ProximityPaths are used to compute proximity scores from symbol's
+    /// declaring file. The best score will be used.
+    explicit FileProximityMatcher(
+        llvm::ArrayRef<llvm::StringRef> ProximityPaths);
+
+    /// Calculates the best proximity score from proximity paths to the symbol's
+    /// URI. Score is [0-1], 1 means \p SymbolURI exactly matches a proximity
+    /// path. When a path cannot be encoded into the same scheme as \p
+    /// SymbolURI, the proximity will be 0.
+    float uriProximity(llvm::StringRef SymbolURI) const;
+
+  private:
+    llvm::SmallVector<std::string, 2> ProximityPaths;
+    friend llvm::raw_ostream &operator<<(llvm::raw_ostream &,
+                                         const FileProximityMatcher &);
+};
+
 /// TopN<T> is a lossy container that preserves only the "best" N elements.
 template <typename T, typename Compare = std::greater<T>> class TopN {
 public:
   using value_type = T;
   TopN(size_t N, Compare Greater = Compare())
       : N(N), Greater(std::move(Greater)) {}
 
   // Adds a candidate to the set.

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

 //===--- Quality.cpp --------------------------------------------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===---------------------------------------------------------------------===//
 #include "Quality.h"
+#include "URI.h"
 #include "index/Index.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/Basic/CharInfo.h"
 #include "clang/AST/DeclVisitor.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Sema/CodeCompleteConsumer.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/MathExtras.h"
raw_ostream &operator<<(raw_ostream &OS, const SymbolQualitySignals &S) {
   OS << formatv("=== Symbol quality: {0}\n", S.evaluate());
   OS << formatv("\tReferences: {0}\n", S.References);
   OS << formatv("\tDeprecated: {0}\n", S.Deprecated);
   OS << formatv("\tReserved name: {0}\n", S.ReservedName);
   OS << formatv("\tCategory: {0}\n", static_cast<int>(S.Category));
   return OS;
 }
 
+/// Calculates a proximity score from \p From and \p To, which are URI strings
+/// that have the same scheme. This does not parse URI. A URI (sans "<scheme>:")
+/// is split into chunks by '/' and each chunk is considered a file/directory.
+/// For example, "uri:///a/b/c" will be treated as /a/b/c
+static float uriProximity(StringRef From, StringRef To) {
+  auto SchemeSplitFrom = From.split(':');
+  auto SchemeSplitTo = To.split(':');
+  assert((SchemeSplitFrom.first == SchemeSplitTo.first) &&
+         "URIs must have the same scheme in order to compute proximity.");
+  auto Split = [](StringRef URIWithoutScheme) {
+    SmallVector<StringRef, 8> Split;
+    URIWithoutScheme.split(Split, '/', /*MaxSplit=*/-1, /*KeepEmpty=*/false);
+    return Split;
+  };
+  SmallVector<StringRef, 8> Fs = Split(SchemeSplitFrom.second);
+  SmallVector<StringRef, 8> Ts = Split(SchemeSplitTo.second);
+  auto F = Fs.begin(), T = Ts.begin(), FE = Fs.end(), TE = Ts.end();
+  for (; F != FE && T != TE && *F == *T; ++F, ++T) {
+  }
+  // We penalize for traversing up and down from \p From to \p To but penalize
+  // less for traversing down because subprojects are more closely related than
+  // superprojects.
+  int UpDist = FE - F;
+  int DownDist = TE - T;
+  return std::pow(0.7, UpDist + DownDist/2);
+}
+
+FileProximityMatcher::FileProximityMatcher(ArrayRef<StringRef> ProximityPaths)
+    : ProximityPaths(ProximityPaths.begin(), ProximityPaths.end()) {}
+
+float FileProximityMatcher::uriProximity(StringRef SymbolURI) const {
+  float Score = 0;
+  if (!ProximityPaths.empty() && !SymbolURI.empty()) {
+    for (const auto &Path : ProximityPaths)
+      // Only calculate proximity score for two URIs with the same scheme so
+      // that the computation can be purely text-based and thus avoid expensive
+      // URI encoding/decoding.
+      if (auto U = URI::create(Path, SymbolURI.split(':').first)) {
+        Score = std::max(Score, clangd::uriProximity(U->toString(), SymbolURI));
+      } else {
+        llvm::consumeError(U.takeError());
+      }
+  }
+  return Score;
+}
+
+llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
+                              const FileProximityMatcher &M) {
+  OS << formatv("File proximity matcher: ");
+  OS << formatv("ProximityPaths{{0}}", llvm::join(M.ProximityPaths.begin(),
+                                                  M.ProximityPaths.end(), ","));
+  return OS;
+}
+
 static SymbolRelevanceSignals::AccessibleScope
 ComputeScope(const NamedDecl &D) {
   bool InClass = false;
   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.
+
+  SymbolURI = IndexResult.CanonicalDeclaration.FileURI;
 }
 
 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.
+    // 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) ? 1.0 : 0.0;
-    ProximityScore = std::max(DeclProximity, ProximityScore);
+        hasDeclInMainFile(*SemaCCResult.Declaration) ? 1.0 : 0.6;
+    SemaProximityScore = std::max(DeclProximity, SemaProximityScore);
   }
 
   // Declarations are scoped, others (like macros) are assumed global.
   if (SemaCCResult.Declaration)
     Scope = std::min(Scope, ComputeScope(*SemaCCResult.Declaration));
 }
 
 float SymbolRelevanceSignals::evaluate() const {
   float Score = 1;
 
   if (Forbidden)
     return 0;
 
   Score *= NameMatch;
 
+  float IndexProximityScore =
+      FileProximityMatch ? FileProximityMatch->uriProximity(SymbolURI) : 0;
   // Proximity scores are [0,1] and we translate them into a multiplier in the
   // range from 1 to 2.
-  Score *= 1 + ProximityScore;
+  Score *= 1 + std::max(IndexProximityScore, SemaProximityScore);
 
   // 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;
       break;
     case ClassScope:
       Score *= 2;
       break;
     case FunctionScope:
       Score *= 4;
       break;
     }
   }
 
   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("\tProximity: {0}\n", S.ProximityScore);
+  OS << formatv("\tSymbol URI: {0}\n", S.SymbolURI);
+  if (S.FileProximityMatch) {
+    OS << formatv("\tIndex proximity: {0}\n",
+                  S.FileProximityMatch->uriProximity(S.SymbolURI))
+       << " (" << *S.FileProximityMatch << ")\n";
+  }
+  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;
 }

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

 //
 // Here we test the signal extraction and sanity-check that signals point in
 // the right direction. This should be supplemented by quality metrics which
 // we can compute from a corpus of queries and preferred rankings.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Quality.h"
+#include "TestFS.h"
 #include "TestTU.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 namespace clang {
 namespace clangd {
+
+// Force the unittest URI scheme to be linked,
+static int LLVM_ATTRIBUTE_UNUSED UnittestSchemeAnchorDest =
+    UnittestSchemeAnchorSource;
+
 namespace {
 
 TEST(QualityTests, SymbolQualitySignalExtraction) {
   auto Header = TestTU::withHeaderCode(R"cpp(
     int _X;
 
     [[deprecated]]
     int _f() { return _X; }
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";
+  EXPECT_FLOAT_EQ(Relevance.SemaProximityScore, 1.0) << "Decl in current file";
   Relevance = {};
   Relevance.merge(CodeCompletionResult(&findDecl(AST, "header"), 42));
-  EXPECT_FLOAT_EQ(Relevance.ProximityScore, 0.0) << "Decl from header";
+  EXPECT_FLOAT_EQ(Relevance.SemaProximityScore, 0.6) << "Decl from header";
   Relevance = {};
   Relevance.merge(CodeCompletionResult(&findDecl(AST, "header_main"), 42));
-  EXPECT_FLOAT_EQ(Relevance.ProximityScore, 1.0) << "Current file and header";
+  EXPECT_FLOAT_EQ(Relevance.SemaProximityScore, 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 = {};
TEST(QualityTests, SymbolRelevanceSignalsSanity) {
   Forbidden.Forbidden = true;
   EXPECT_LT(Forbidden.evaluate(), Default.evaluate());
 
   SymbolRelevanceSignals PoorNameMatch;
   PoorNameMatch.NameMatch = 0.2f;
   EXPECT_LT(PoorNameMatch.evaluate(), Default.evaluate());
 
   SymbolRelevanceSignals WithProximity;
-  WithProximity.ProximityScore = 0.2f;
+  WithProximity.SemaProximityScore = 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));
   EXPECT_LT(sortText(-10), sortText(-std::numeric_limits<float>::infinity()));
 
   EXPECT_LT(sortText(1, "z"), sortText(0, "a"));
   EXPECT_LT(sortText(0, "a"), sortText(0, "z"));
 }
 
+// {a,b,c} becomes /clangd-test/a/b/c
+std::string joinPaths(llvm::ArrayRef<StringRef> Parts) {
+  return testPath(
+      llvm::join(Parts.begin(), Parts.end(), llvm::sys::path::get_separator()));
+}
+
+static constexpr float ProximityBase = 0.7;
+
+// Calculates a proximity score for an index symbol with declaration file
+// SymPath with the given URI scheme.
+float URIProximity(const FileProximityMatcher &Matcher, StringRef SymPath,
+                     StringRef Scheme = "file") {
+  auto U = URI::create(SymPath, Scheme);
+  EXPECT_TRUE(static_cast<bool>(U)) << llvm::toString(U.takeError());
+  return Matcher.uriProximity(U->toString());
+}
+
+TEST(QualityTests, URIProximityScores) {
+  FileProximityMatcher Matcher(
+      /*ProximityPaths=*/{joinPaths({"a", "b", "c", "d", "x"})});
+
+  EXPECT_FLOAT_EQ(URIProximity(Matcher, joinPaths({"a", "b", "c", "d", "x"})),
+                  1);
+  EXPECT_FLOAT_EQ(URIProximity(Matcher, joinPaths({"a", "b", "c", "d", "y"})),
+                  ProximityBase);
+  EXPECT_FLOAT_EQ(URIProximity(Matcher, joinPaths({"a", "y", "z"})),
+                  std::pow(ProximityBase, 5));
+  EXPECT_FLOAT_EQ(
+      URIProximity(Matcher, joinPaths({"a", "b", "c", "d", "e", "y"})),
+      std::pow(ProximityBase, 2));
+  EXPECT_FLOAT_EQ(
+      URIProximity(Matcher, joinPaths({"a", "b", "m", "n", "o", "y"})),
+      std::pow(ProximityBase, 5));
+  EXPECT_FLOAT_EQ(
+      URIProximity(Matcher, joinPaths({"a", "t", "m", "n", "o", "y"})),
+      std::pow(ProximityBase, 6));
+  // Note the common directory is /clang-test/
+  EXPECT_FLOAT_EQ(URIProximity(Matcher, joinPaths({"m", "n", "o", "p", "y"})),
+                  std::pow(ProximityBase, 7));
+}
+
+TEST(QualityTests, URIProximityScoresWithTestURI) {
+  FileProximityMatcher Matcher(
+      /*ProximityPaths=*/{joinPaths({"b", "c", "x"})});
+  EXPECT_FLOAT_EQ(URIProximity(Matcher, joinPaths({"b", "c", "x"}), "unittest"),
+                  1);
+  EXPECT_FLOAT_EQ(URIProximity(Matcher, joinPaths({"b", "y"}), "unittest"),
+                  std::pow(ProximityBase, 2));
+  // unittest:///b/c/x vs unittest:///m/n/y. No common directory.
+  EXPECT_FLOAT_EQ(URIProximity(Matcher, joinPaths({"m", "n", "y"}), "unittest"),
+                  std::pow(ProximityBase, 4));
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang