[clangd] Incorporate transitive #includes into code complete proximity scoring.

[sammccall]

Summary

We now compute a distance from the main file to the symbol header, which
is a weighted count of:

• some number of #include traversals from source file --> included file
• some number of FS traversals from file --> parent directory
• some number of FS traversals from parent directory --> child file/dir

This calculation is performed in the appropriate URI scheme.

This means we'll get some proximity boost from header files in main-file
contexts, even when these are in different directory trees.

This extended file proximity model is not yet incorporated in the index
interface/implementation.

Reviewer guide (decreasing order of complexity):

• FileDistance is new, and contains the algorithm/structures for computing the file distances efficiently from a set of weighted roots
• Headers has significant changes: the IncludeStructure class expands the scope of include info we previously captured
• Quality uses these to implement the new definition of SemaProximityScore
• CodeComplete has a bit of churn because the lifetimes there are so complicated
• the rest is boilerplate

[sammccall]

Document some more stuff, and clang-format

[ioeric]

Looks great! Thanks for doing this!

The algorithm looks pretty efficient. It might still make sense to collect some performance numbers for real files with potentially large #include tree (we have plenty of those in our internal codebase :)

clangd/CodeComplete.cpp

908

It might make sense to briefly explain somewhere how computational cost is distributed across the workflow.

938

nit: Style?

clangd/FileDistance.cpp

73

nit: this loop would probably be easier to understand if iterated reversely.

87

This is done for every index symbol, so I wonder if we could avoid parsing URIs by assuming some URI structures.

clangd/FileDistance.h

57

nit: It's unclear what the values of Roots are (it can be confused with tree roots or directory roots).

clangd/Headers.cpp

28

What does this do?

clangd/Headers.h

62

Does this return all transitive includes in the entire TU or just those from MainFileName? And what's MainFileName here? Is it the same as the main file in a TU?

67

The real name can be empty. How do we handle empty path?

75

Maybe fileIndex?

clangd/Quality.cpp

233

nit: static

unittests/clangd/FileDistanceTests.cpp

37

I think this is an interesting case. IIUC, 22u is contributed by 4 ups (4*5) and 1 include (1*2, via llvm/ADT/StringRef.h).

Suppose a/b/c/d/e/f.cc includes base/x.h, then the shortest path into directory other/ is likely to go via base/x.h. This might become a problem if base/x.h is very commonly used. One solution is probably to penalize edits that hit the root.

[sammccall]

Address review comments.

[sammccall]

clangd/FileDistance.cpp

36

Note there was a nasty bug in FileDistance::FileDistance that failed to consider down edges. Fixed and test case added.

87

(note we cache the URI string, so it's at most once per file)

We could, at the cost of potentially subtle bugs/dependencies. (what if the data doesn't make exactly the same choices regarding escaping?)

parse() is actually *fairly* cheap. Unlike resolve() or create(), it doesn't touch the URI scheme plugins at all, so nothing's virtual. It's a few calls to percentDecode() and a few string allocations.
I think there's room for optimization there (scheme should be a smallstring for one) but wouldn't go hacking around it unless it turns up on a profile.

clangd/FileDistance.h

57

Changed roots -> sources everywhere, which is less ambiguous.

clangd/Headers.h

62

It's transitive... there was actually a comment but it was in the wrong place!
Wrote a better comment and generalized slightly to make this seem less magic. You can actually ask for the files reachable starting at any file (MainFile is usually the one you want though).

67

We attempt to record it every time we see it.
Fixed includeDepth() to exclude files from the output if we never get a real name for them.
This shouldn't be the case in practice - real name is missing for FileEntry when using a preamble, but we should see their names when *building* the preamble.

unittests/clangd/FileDistanceTests.cpp

37

Yeah, this could be a weakness. I don't think this is specific to #includes, or to root directories.
I think the generalization is that there exist directories (like /usr/include) whose siblings are unrelated. Down-traversals in these directories should be more expensive. I've added a Caveats section to the FileDistance documentation, but I would like to avoid adding special cases until we can see how much difference they make.

[ioeric]

clangd/FileDistance.cpp

10

Is this intentionally reserved?

52

nit: this probably deserve a comment or a better formatting. It looks like part of the loop incremental.

87

Should we also check the cache here?

unittests/clangd/FileDistanceTests.cpp

37

As chatted offline, this could be still concerning as it's not uncommon for files to include headers from top-level directories. I think the idea you proposed - restricting up traversals from included files, could address the problem.

[sammccall]

Address review comments. Most notably: limit the up-traversals from some sources.

[ioeric]

lgtm.

Again, we might still want to measure the performance impact on files with potentially large #include tree ;)

clangd/FileDistance.cpp

27

Shouldn't /foo a down from / and 2+1 = 3?

[sammccall]

Sigh... sorry, forgot to send these comments with the last patch. Will measure performance today.

clangd/FileDistance.cpp

10

Oops, added implementation docs

52

Moved out of the loop, now the loop has a counter. Hopefully less confusing?

87

I'm not sure why - for the full path we'll look up the cached value in the first iteration through the loop. Ancestors will be empty, so this function should be pretty cheap for this happy path - dominated by computing the hash.

or do you mean to skip canonicalization?
This doesn't matter in practice as we'll use this through URIDistance which does a pre-canonicalization cache. If we used this directly then it might be worthwhile.

[sammccall]

Rebase

[sammccall]

Performance on a transitively big file.
Stress test - global scope completion with index turned off.
Benchmarking codeComplete() call 100x per trial, trials randomly ordered.

Before this patch (427ms 421ms 430ms)
After this patch (418ms 420ms 417ms)
So it seems this is slightly faster, maybe 2%.

[CarlosAlbertoEnciso]

Hi,

It seems that your patch is causing an error in the tests for

http://lab.llvm.org:8011/builders/clang-x64-ninja-win7

http://lab.llvm.org:8011/builders/clang-x64-ninja-win7/builds/11510/steps/ninja%20check%201/logs/FAIL%3A%20Extra%20Tools%20Unit%20Tests%3A%3AFileDistanceTests.URI

Thanks very much

[ioeric]

Hi Carlos, thanks for letting us know! I sent r336249 to fix the windows
test.

[CarlosAlbertoEnciso]

In D48441#1151889, @ioeric wrote:

Hi Carlos, thanks for letting us know! I sent r336249 to fix the windows
test.

Hi @ioeric,

Thanks very much. Happy to help.

clangd/CMakeLists.txt

add_clang_library(clangDaemon
   ClangdUnit.cpp
   CodeComplete.cpp
   CodeCompletionStrings.cpp
   Compiler.cpp
   Context.cpp
   Diagnostics.cpp
   DraftStore.cpp
   FindSymbols.cpp
+  FileDistance.cpp
   FuzzyMatch.cpp
   GlobalCompilationDatabase.cpp
   Headers.cpp
   JSONExpr.cpp
   JSONRPCDispatcher.cpp
   Logger.cpp
   Protocol.cpp
   ProtocolHandlers.cpp

clangd/ClangdServer.cpp

if (!IP)
       return CB(IP.takeError());
 
     auto PreambleData = IP->Preamble;
 
     // FIXME(ibiryukov): even if Preamble is non-null, we may want to check
     // both the old and the new version in case only one of them matches.
     CompletionList Result = clangd::codeComplete(
         File, IP->Command, PreambleData ? &PreambleData->Preamble : nullptr,
-        PreambleData ? PreambleData->Inclusions : std::vector<Inclusion>(),
+        PreambleData ? PreambleData->Includes : IncludeStructure(),
         IP->Contents, Pos, FS, PCHs, CodeCompleteOpts);
     CB(std::move(Result));
   };
 
   WorkScheduler.runWithPreamble("CodeComplete", File,
                                 Bind(Task, File.str(), std::move(CB)));
 }
 

clangd/ClangdUnit.h

 struct CompileCommand;
 }
 
 namespace clangd {
 
 // Stores Preamble and associated data.
 struct PreambleData {
   PreambleData(PrecompiledPreamble Preamble, std::vector<Diag> Diags,
-               std::vector<Inclusion> Inclusions);
+               IncludeStructure Includes);
 
   tooling::CompileCommand CompileCommand;
   PrecompiledPreamble Preamble;
   std::vector<Diag> Diags;
   // Processes like code completions and go-to-definitions will need #include
   // information, and their compile action skips preamble range.
-  std::vector<Inclusion> Inclusions;
+  IncludeStructure Includes;
 };
 
 /// Information required to run clang, e.g. to parse AST or do code completion.
 struct ParseInputs {
   tooling::CompileCommand CompileCommand;
   IntrusiveRefCntPtr<vfs::FileSystem> FS;
   std::string Contents;
 };
public:
   /// (These should be const, but RecursiveASTVisitor requires Decl*).
   ArrayRef<Decl *> getLocalTopLevelDecls();
 
   const std::vector<Diag> &getDiagnostics() const;
 
   /// Returns the esitmated size of the AST and the accessory structures, in
   /// bytes. Does not include the size of the preamble.
   std::size_t getUsedBytes() const;
-  const std::vector<Inclusion> &getInclusions() const;
+  const IncludeStructure &getIncludeStructure() const;
 
 private:
   ParsedAST(std::shared_ptr<const PreambleData> Preamble,
             std::unique_ptr<CompilerInstance> Clang,
             std::unique_ptr<FrontendAction> Action,
             std::vector<Decl *> LocalTopLevelDecls, std::vector<Diag> Diags,
-            std::vector<Inclusion> Inclusions);
+            IncludeStructure Includes);
 
   // In-memory preambles must outlive the AST, it is important that this member
   // goes before Clang and Action.
   std::shared_ptr<const PreambleData> Preamble;
   // We store an "incomplete" FrontendAction (i.e. no EndSourceFile was called
   // on it) and CompilerInstance used to run it. That way we don't have to do
   // complex memory management of all Clang structures on our own. (They are
   // stored in CompilerInstance and cleaned up by
   // FrontendAction.EndSourceFile).
   std::unique_ptr<CompilerInstance> Clang;
   std::unique_ptr<FrontendAction> Action;
 
   // Data, stored after parsing.
   std::vector<Diag> Diags;
   // Top-level decls inside the current file. Not that this does not include
   // top-level decls from the preamble.
   std::vector<Decl *> LocalTopLevelDecls;
-  std::vector<Inclusion> Inclusions;
+  IncludeStructure Includes;
 };
 
 using PreambleParsedCallback = std::function<void(
     PathRef Path, ASTContext &, std::shared_ptr<clang::Preprocessor>)>;
 
 /// Builds compiler invocation that could be used to build AST or preamble.
 std::unique_ptr<CompilerInvocation>
 buildCompilerInvocation(const ParseInputs &Inputs);

clangd/ClangdUnit.cpp

private:
   std::vector<Decl *> TopLevelDecls;
 };
 
 class CppFilePreambleCallbacks : public PreambleCallbacks {
 public:
   CppFilePreambleCallbacks(PathRef File, PreambleParsedCallback ParsedCallback)
       : File(File), ParsedCallback(ParsedCallback) {}
 
-  std::vector<Inclusion> takeInclusions() { return std::move(Inclusions); }
+  IncludeStructure takeIncludes() { return std::move(Includes); }
 
   void AfterExecute(CompilerInstance &CI) override {
     if (!ParsedCallback)
       return;
     trace::Span Tracer("Running PreambleCallback");
     ParsedCallback(File, CI.getASTContext(), CI.getPreprocessorPtr());
   }
 
   void BeforeExecute(CompilerInstance &CI) override {
     SourceMgr = &CI.getSourceManager();
   }
 
   std::unique_ptr<PPCallbacks> createPPCallbacks() override {
     assert(SourceMgr && "SourceMgr must be set at this point");
-    return collectInclusionsInMainFileCallback(
-        *SourceMgr,
-        [this](Inclusion Inc) { Inclusions.push_back(std::move(Inc)); });
+    return collectIncludeStructureCallback(*SourceMgr, &Includes);
   }
 
 private:
   PathRef File;
   PreambleParsedCallback ParsedCallback;
-  std::vector<Inclusion> Inclusions;
+  IncludeStructure Includes;
   SourceManager *SourceMgr = nullptr;
 };
 
 } // namespace
 
 void clangd::dumpAST(ParsedAST &AST, llvm::raw_ostream &OS) {
   AST.getASTContext().getTranslationUnitDecl()->dump(OS, true);
 }
ParsedAST::Build(std::unique_ptr<clang::CompilerInvocation> CI,
   auto Action = llvm::make_unique<ClangdFrontendAction>();
   const FrontendInputFile &MainInput = Clang->getFrontendOpts().Inputs[0];
   if (!Action->BeginSourceFile(*Clang, MainInput)) {
     log("BeginSourceFile() failed when building AST for " +
         MainInput.getFile());
     return llvm::None;
   }
 
-  std::vector<Inclusion> Inclusions;
   // Copy over the includes from the preamble, then combine with the
   // non-preamble includes below.
-  if (Preamble)
-    Inclusions = Preamble->Inclusions;
-
-  Clang->getPreprocessor().addPPCallbacks(collectInclusionsInMainFileCallback(
+  auto Includes = Preamble ? Preamble->Includes : IncludeStructure{};
+  Clang->getPreprocessor().addPPCallbacks(collectIncludeStructureCallback(
       Clang->getSourceManager(),
-      [&Inclusions](Inclusion Inc) { Inclusions.push_back(std::move(Inc)); }));
+      &Includes));
 
   if (!Action->Execute())
     log("Execute() failed when building AST for " + MainInput.getFile());
 
   // UnitDiagsConsumer is local, we can not store it in CompilerInstance that
   // has a longer lifetime.
   Clang->getDiagnostics().setClient(new IgnoreDiagnostics);
   // CompilerInstance won't run this callback, do it directly.
   ASTDiags.EndSourceFile();
 
   std::vector<Decl *> ParsedDecls = Action->takeTopLevelDecls();
   std::vector<Diag> Diags = ASTDiags.take();
   // Add diagnostics from the preamble, if any.
   if (Preamble)
     Diags.insert(Diags.begin(), Preamble->Diags.begin(), Preamble->Diags.end());
   return ParsedAST(std::move(Preamble), std::move(Clang), std::move(Action),
                    std::move(ParsedDecls), std::move(Diags),
-                   std::move(Inclusions));
+                   std::move(Includes));
 }
 
 ParsedAST::ParsedAST(ParsedAST &&Other) = default;
 
 ParsedAST &ParsedAST::operator=(ParsedAST &&Other) = default;
 
 ParsedAST::~ParsedAST() {
   if (Action) {
std::size_t ParsedAST::getUsedBytes() const {
   Total += PP.getTotalMemory();
   if (PreprocessingRecord *PRec = PP.getPreprocessingRecord())
     Total += PRec->getTotalMemory();
   Total += PP.getHeaderSearchInfo().getTotalMemory();
 
   return Total;
 }
 
-const std::vector<Inclusion> &ParsedAST::getInclusions() const {
-  return Inclusions;
+const IncludeStructure &ParsedAST::getIncludeStructure() const {
+  return Includes;
 }
 
 PreambleData::PreambleData(PrecompiledPreamble Preamble,
                            std::vector<Diag> Diags,
-                           std::vector<Inclusion> Inclusions)
+                           IncludeStructure Includes)
     : Preamble(std::move(Preamble)), Diags(std::move(Diags)),
-      Inclusions(std::move(Inclusions)) {}
+      Includes(std::move(Includes)) {}
 
 ParsedAST::ParsedAST(std::shared_ptr<const PreambleData> Preamble,
                      std::unique_ptr<CompilerInstance> Clang,
                      std::unique_ptr<FrontendAction> Action,
                      std::vector<Decl *> LocalTopLevelDecls,
-                     std::vector<Diag> Diags, std::vector<Inclusion> Inclusions)
+                     std::vector<Diag> Diags, IncludeStructure Includes)
     : Preamble(std::move(Preamble)), Clang(std::move(Clang)),
       Action(std::move(Action)), Diags(std::move(Diags)),
       LocalTopLevelDecls(std::move(LocalTopLevelDecls)),
-      Inclusions(std::move(Inclusions)) {
+      Includes(std::move(Includes)) {
   assert(this->Clang);
   assert(this->Action);
 }
 
 std::unique_ptr<CompilerInvocation>
 clangd::buildCompilerInvocation(const ParseInputs &Inputs) {
   std::vector<const char *> ArgStrs;
   for (const auto &S : Inputs.CompileCommand.CommandLine)
std::shared_ptr<const PreambleData> clangd::buildPreamble(
   // bodies.
   CI.getFrontendOpts().SkipFunctionBodies = false;
 
   if (BuiltPreamble) {
     log("Built preamble of size " + Twine(BuiltPreamble->getSize()) +
         " for file " + Twine(FileName));
     return std::make_shared<PreambleData>(
         std::move(*BuiltPreamble), PreambleDiagnostics.take(),
-        SerializedDeclsCollector.takeInclusions());
+        SerializedDeclsCollector.takeIncludes());
   } else {
     log("Could not build a preamble for file " + Twine(FileName));
     return nullptr;
   }
 }
 
 llvm::Optional<ParsedAST> clangd::buildAST(
     PathRef FileName, std::unique_ptr<CompilerInvocation> Invocation,

clangd/CodeComplete.h

struct CodeCompleteOptions {
   /// clangd.
   const SymbolIndex *Index = nullptr;
 };
 
 /// Get code completions at a specified \p Pos in \p FileName.
 CompletionList codeComplete(PathRef FileName,
                             const tooling::CompileCommand &Command,
                             PrecompiledPreamble const *Preamble,
-                            const std::vector<Inclusion> &PreambleInclusions,
+                            const IncludeStructure &PreambleInclusions,
                             StringRef Contents, Position Pos,
                             IntrusiveRefCntPtr<vfs::FileSystem> VFS,
                             std::shared_ptr<PCHContainerOperations> PCHs,
                             CodeCompleteOptions Opts);
 
 /// Get signature help at a specified \p Pos in \p FileName.
 SignatureHelp signatureHelp(PathRef FileName,
                             const tooling::CompileCommand &Command,

clangd/CodeComplete.cpp

 // Signature help works in a similar way as code completion, but it is simpler:
 // it's purely AST-based, and there are few candidates.
 //
 //===---------------------------------------------------------------------===//
 
 #include "CodeComplete.h"
 #include "CodeCompletionStrings.h"
 #include "Compiler.h"
+#include "FileDistance.h"
 #include "FuzzyMatch.h"
 #include "Headers.h"
 #include "Logger.h"
 #include "Quality.h"
 #include "SourceCode.h"
 #include "Trace.h"
 #include "URI.h"
 #include "index/Index.h"
private:
   CodeCompletionTUInfo CCTUInfo;
 
 }; // SignatureHelpCollector
 
 struct SemaCompleteInput {
   PathRef FileName;
   const tooling::CompileCommand &Command;
   PrecompiledPreamble const *Preamble;
-  const std::vector<Inclusion> &PreambleInclusions;
   StringRef Contents;
   Position Pos;
   IntrusiveRefCntPtr<vfs::FileSystem> VFS;
   std::shared_ptr<PCHContainerOperations> PCHs;
 };
 
 // Invokes Sema code completion on a file.
-// If \p Includes is set, it will be initialized after a compiler instance has
-// been set up.
+// If \p Includes is set, it will be updated based on the compiler invocation.
 bool semaCodeComplete(std::unique_ptr<CodeCompleteConsumer> Consumer,
                       const clang::CodeCompleteOptions &Options,
                       const SemaCompleteInput &Input,
-                      std::unique_ptr<IncludeInserter> *Includes = nullptr) {
+                      IncludeStructure *Includes = nullptr) {
   trace::Span Tracer("Sema completion");
   std::vector<const char *> ArgStrs;
   for (const auto &S : Input.Command.CommandLine)
     ArgStrs.push_back(S.c_str());
 
   if (Input.VFS->setCurrentWorkingDirectory(Input.Command.Directory)) {
     log("Couldn't set working directory");
     // We run parsing anyway, our lit-tests rely on results for non-existing
bool semaCodeComplete(std::unique_ptr<CodeCompleteConsumer> Consumer,
   Clang->setCodeCompletionConsumer(Consumer.release());
 
   SyntaxOnlyAction Action;
   if (!Action.BeginSourceFile(*Clang, Clang->getFrontendOpts().Inputs[0])) {
     log("BeginSourceFile() failed when running codeComplete for " +
         Input.FileName);
     return false;
   }
-  if (Includes) {
-    // Initialize Includes if provided.
-
-    // FIXME(ioeric): needs more consistent style support in clangd server.
-    auto Style = format::getStyle("file", Input.FileName, "LLVM",
-                                  Input.Contents, Input.VFS.get());
-    if (!Style) {
-      log("Failed to get FormatStyle for file" + Input.FileName +
-          ". Fall back to use LLVM style. Error: " +
-          llvm::toString(Style.takeError()));
-      Style = format::getLLVMStyle();
-    }
-    *Includes = llvm::make_unique<IncludeInserter>(
-        Input.FileName, Input.Contents, *Style, Input.Command.Directory,
-        Clang->getPreprocessor().getHeaderSearchInfo());
-    for (const auto &Inc : Input.PreambleInclusions)
-      Includes->get()->addExisting(Inc);
-    Clang->getPreprocessor().addPPCallbacks(collectInclusionsInMainFileCallback(
-        Clang->getSourceManager(), [Includes](Inclusion Inc) {
-          Includes->get()->addExisting(std::move(Inc));
-        }));
-  }
+  if (Includes)
+    Clang->getPreprocessor().addPPCallbacks(
+        collectIncludeStructureCallback(Clang->getSourceManager(), Includes));
   if (!Action.Execute()) {
     log("Execute() failed when running codeComplete for " + Input.FileName);
     return false;
   }
   Action.EndSourceFile();
 
   return true;
 }

 //     Each candidate points to an underlying CodeCompletionResult (Sema), a
 //     Symbol (Index), or both. It computes the result quality score.
 //     CompletionCandidate also does conversion to CompletionItem (at the end).
 //   - FuzzyMatcher scores how the candidate matches the partial identifier.
 //     This score is combined with the result quality score for the final score.
 //   - TopN determines the results with the best score.
 class CodeCompleteFlow {
   PathRef FileName;
+  IncludeStructure Includes; // Complete once the compiler runs.
   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;
+  llvm::Optional<IncludeInserter> Inserter; // Available during runWithSema.
+  llvm::Optional<URIDistance> FileProximity; // Initialized once Sema runs.
 
 public:
   // A CodeCompleteFlow object is only useful for calling run() exactly once.
-  CodeCompleteFlow(PathRef FileName, const CodeCompleteOptions &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(ArrayRef<StringRef>({FileName})) {}
+  CodeCompleteFlow(PathRef FileName, const IncludeStructure &Includes,
+                   const CodeCompleteOptions &Opts)
+      : FileName(FileName), Includes(Includes), Opts(Opts) {}
 
   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;
     auto RecorderOwner = llvm::make_unique<CompletionRecorder>(Opts, [&]() {
       assert(Recorder && "Recorder is not set");
-      assert(Includes && "Includes is not set");
+       // FIXME(ioeric): needs more consistent style support in clangd server.
+      auto Style =
+          format::getStyle("file", SemaCCInput.FileName, "LLVM",
+                           SemaCCInput.Contents, SemaCCInput.VFS.get());
+      if (!Style) {
+        log("Failed to get FormatStyle for file" + SemaCCInput.FileName + ": " +
+            llvm::toString(Style.takeError()) + ". Fallback is LLVM style.");
+        Style = format::getLLVMStyle();
+      }
       // If preprocessor was run, inclusions from preprocessor callback should
-      // already be added to Inclusions.
+      // already be added to Includes.
+      Inserter.emplace(
+          SemaCCInput.FileName, SemaCCInput.Contents,
+          format::getLLVMStyle(), // XXX
+          SemaCCInput.Command.Directory,
+          Recorder->CCSema->getPreprocessor().getHeaderSearchInfo());
+      for (const auto &Inc : Includes.MainFileIncludes)
+        Inserter->addExisting(Inc);
+
+      FileDistanceOptions ProxOpts{}; // Use defaults.
+      const auto &SM = Recorder->CCSema->getSourceManager();
+      llvm::StringMap<unsigned> ProxRoots = Includes.includeDepth(
+          SM.getFileEntryForID(SM.getMainFileID())->getName());
+      for (auto &Entry : ProxRoots)
+        Entry.second *= ProxOpts.IncludeCost;
+      FileProximity.emplace(ProxRoots, ProxOpts);
+
       Output = runWithSema();
-      Includes.reset(); // Make sure this doesn't out-live Clang.
+      Inserter.reset(); // Make sure this doesn't out-live Clang.
       SPAN_ATTACH(Tracer, "sema_completion_kind",
                   getCompletionKindString(Recorder->CCContext.getKind()));
     });
 
     Recorder = RecorderOwner.get();
     semaCodeComplete(std::move(RecorderOwner), Opts.getClangCompleteOpts(),
                      SemaCCInput, &Includes);
 
SymbolSlab queryIndex() {
     // Build the query.
     FuzzyFindRequest Req;
     if (Opts.Limit)
       Req.MaxCandidateCount = Opts.Limit;
     Req.Query = Filter->pattern();
     Req.RestrictForCodeCompletion = true;
     Req.Scopes = getQueryScopes(Recorder->CCContext,
                                 Recorder->CCSema->getSourceManager());
+    // FIXME: we should send multiple weighted paths here.
     Req.ProximityPaths.push_back(FileName);
     log(llvm::formatv("Code complete: fuzzyFind(\"{0}\", scopes=[{1}])",
                       Req.Query,
                       llvm::join(Req.Scopes.begin(), Req.Scopes.end(), ",")));
     // Run the query against the index.
     if (Opts.Index->fuzzyFind(
             Req, [&](const Symbol &Sym) { ResultsBuilder.insert(Sym); }))
       Incomplete = true;
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.Query = SymbolRelevanceSignals::CodeComplete;
-    Relevance.FileProximityMatch = &FileProximityMatch;
+    Relevance.FileProximityMatch = FileProximity.getPointer();
     auto &First = Bundle.front();
     if (auto FuzzyScore = fuzzyScore(First))
       Relevance.NameMatch = *FuzzyScore;
     else
       return;
     unsigned SemaResult = 0, IndexResult = 0;
     for (const auto &Candidate : Bundle) {
       if (Candidate.IndexResult) {
if (auto *SR = Bundle.front().SemaResult) {
       if (Opts.IncludeComments) {
         assert(Recorder->CCSema);
         FrontDocComment = getDocComment(Recorder->CCSema->getASTContext(), *SR,
                                         /*CommentsFromHeader=*/false);
       }
     }
     return CompletionCandidate::build(
         Bundle,
-        Bundle.front().build(FileName, Scores, Opts, SemaCCS, *Includes,
+        Bundle.front().build(FileName, Scores, Opts, SemaCCS, *Inserter,
                              FrontDocComment),
         Opts);
   }
 };
 
 CompletionList codeComplete(PathRef FileName,
                             const tooling::CompileCommand &Command,
                             PrecompiledPreamble const *Preamble,
-                            const std::vector<Inclusion> &PreambleInclusions,
+                            const IncludeStructure &PreambleInclusions,
                             StringRef Contents, Position Pos,
                             IntrusiveRefCntPtr<vfs::FileSystem> VFS,
                             std::shared_ptr<PCHContainerOperations> PCHs,
                             CodeCompleteOptions Opts) {
-  return CodeCompleteFlow(FileName, Opts)
-      .run({FileName, Command, Preamble, PreambleInclusions, Contents, Pos, VFS,
-            PCHs});
+  return CodeCompleteFlow(FileName, PreambleInclusions, Opts)
+      .run({FileName, Command, Preamble, Contents, Pos, VFS, PCHs});
 }
 
 SignatureHelp signatureHelp(PathRef FileName,
                             const tooling::CompileCommand &Command,
                             PrecompiledPreamble const *Preamble,
                             StringRef Contents, Position Pos,
                             IntrusiveRefCntPtr<vfs::FileSystem> VFS,
                             std::shared_ptr<PCHContainerOperations> PCHs) {
   SignatureHelp Result;
   clang::CodeCompleteOptions Options;
   Options.IncludeGlobals = false;
   Options.IncludeMacros = false;
   Options.IncludeCodePatterns = false;
   Options.IncludeBriefComments = false;
-  std::vector<Inclusion> PreambleInclusions = {}; // Unused for signatureHelp
+  IncludeStructure PreambleInclusions; // Unused for signatureHelp
   semaCodeComplete(llvm::make_unique<SignatureHelpCollector>(Options, Result),
                    Options,
-                   {FileName, Command, Preamble, PreambleInclusions, Contents,
-                    Pos, std::move(VFS), std::move(PCHs)});
+                   {FileName, Command, Preamble, Contents, Pos, std::move(VFS),
+                    std::move(PCHs)});
   return Result;
 }
 
 bool isIndexedForCodeCompletion(const NamedDecl &ND, ASTContext &ASTCtx) {
   using namespace clang::ast_matchers;
   auto InTopLevelScope = hasDeclContext(
       anyOf(namespaceDecl(), translationUnitDecl(), linkageSpecDecl()));
   return !match(decl(anyOf(InTopLevelScope,
                            hasDeclContext(
                                enumDecl(InTopLevelScope, unless(isScoped()))))),
                 ND, ASTCtx)
               .empty();
 }
 
 } // namespace clangd
 } // namespace clang

clangd/FileDistance.h

+//===--- FileDistance.h - File proximity scoring -----------------*- C++-*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This library measures the distance between file paths.
+// It's used for ranking symbols, e.g. in code completion.
+//  |foo/bar.h -> foo/bar.h| = 0.
+//  |foo/bar.h -> foo/baz.h| < |foo/bar.h -> baz.h|.
+// This is an edit-distance, where edits go up or down the directory tree.
+// It's not symmetrical, the costs of going up and down may not match.
+//
+// Dealing with multiple roots:
+// In practice we care about the distance from a source file, but files near
+// its main-header and #included files are considered "close".
+// So we start with a set of (root, cost) pairs, and call the distance to a path
+// the minimum of `cost + |root -> path|`.
+//
+// Symbol URI schemes:
+// Symbol locations may be represented by URIs rather than file paths directly.
+// In this case we want to perform distance computations in URI space rather
+// than in file-space, without performing redundant conversions.
+// Therefore we have a lookup structure that accepts URIs, so that intermediate
+// calculations for the same scheme can be reused.
+//
+//===----------------------------------------------------------------------===//
+
+#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"
+
+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|
+};
+
+// Supports lookups to find the minimum distance to a file from any root.
+// This object should be reused, it memoizes intermediate computations.
+class FileDistance {
+public:
+  static constexpr unsigned kUnreachable = std::numeric_limits<unsigned>::max();
+
+  FileDistance(llvm::StringMap<unsigned> Roots,
+               const FileDistanceOptions &Opts = {});
+
+  // Computes the minimum distance from any root to the file path.
+  unsigned distance(llvm::StringRef Path);
+
+ private:
+  // Costs computed so far. Always contains roots and their ancestors.
+  // We store hash codes only. Collisions are rare and consequences aren't dire.
+  llvm::DenseMap<llvm::hash_code, unsigned> Cache;
+  FileDistanceOptions Opts;
+};
+
+// Supports lookups like FileDistance, but the lookup keys are URIs.
+// We convert each of the roots to the scheme of the URI and do a FileDistance
+// comparison on the bodies.
+class URIDistance {
+public:
+  URIDistance(llvm::StringMap<unsigned> Roots,
+              const FileDistanceOptions &Opts = {})
+      : Roots(Roots), Opts(Opts) {}
+
+  // Computes the minimum distance from any root to the URI.
+  // Only roots that can be mapped into the URI's scheme are considered.
+  unsigned distance(llvm::StringRef URI);
+
+private:
+  // Returns the FileDistance for a URI scheme, creating it if needed.
+  FileDistance& forScheme(llvm::StringRef Scheme);
+
+  // We cache the results using the original strings so we can skip URI parsing.
+  llvm::DenseMap<llvm::hash_code, unsigned> Cache;
+  llvm::StringMap<unsigned> Roots;
+  llvm::StringMap<std::unique_ptr<FileDistance>> ByScheme;
+  FileDistanceOptions Opts;
+};
+
+} // namespace clangd
+} // namespace clang
+

clangd/FileDistance.cpp

+//===--- FileDistance.cpp - File contents container -------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+#include "FileDistance.h"
+#include "Logger.h"
+#define DEBUG_TYPE "FileDistance"
+
+namespace clang {
+namespace clangd {
+using namespace llvm;
+
+// Convert a path into the canonical form.
+// Canonical form is either "/", or "/segment" * N:
+//   C:\foo\bar --> /c:/foo/bar
+//   /foo/      --> /foo
+//   a/b/c      --> /a/b/c
+static SmallString<128> canonicalize(StringRef Path) {
+  SmallString<128> Result = Path.rtrim('/');
+  native(Result, sys::path::Style::posix);
+  if (Result.empty() || Result.front() != '/')
+    Result.insert(Result.begin(), '/');
+  return Result;
+}
+
+const unsigned FileDistance::kUnreachable;
+
+FileDistance::FileDistance(StringMap<unsigned> Roots,
+                           const FileDistanceOptions &Opts)
+    : Opts(Opts) {
+  for (const auto &R : Roots) {
+    auto Canonical = canonicalize(R.getKey());
+    LLVM_DEBUG(dbgs() << "Root " << Canonical << " = " << R.getValue() << "\n");
+    // Walk up to ancestors of this root, assigning cost.
+    unsigned Cost = R.getValue();
+    for (StringRef Rest = Canonical; !Rest.empty();
+         Rest = parent_path(Rest, sys::path::Style::posix)) {
+      auto R = Cache.try_emplace(hash_value(Rest), Cost);
+      if (!R.second) {
+        if (Cost < R.first->second) {
+          R.first->second = Cost;
+        } else {
+          // If we're not the best way to get to this path, stop assigning.
+          break;
+        }
+      }
+      Cost += Opts.UpCost;
+    }
+  }
+}
+
+unsigned FileDistance::distance(StringRef Path) {
+  auto Canonical = canonicalize(Path);
+  unsigned Cost = kUnreachable;
+  SmallVector<hash_code, 16> Ancestors;
+  // Walk up ancestors until we find a path we know the distance for.
+  for (StringRef Rest = Canonical; !Rest.empty();
+       Rest = parent_path(Rest, sys::path::Style::posix)) {
+    auto Hash = hash_value(Rest);
+    auto It = Cache.find(Hash);
+    if (It != Cache.end()) {
+      Cost = It->second;
+      break;
+    }
+    Ancestors.push_back(Hash);
+  }
+  // Fill in all ancestors between the query and the known.
+  for (unsigned I = 0; I < Ancestors.size(); ++I) {
+    if (Cost != kUnreachable)
+      Cost += Opts.DownCost;
+    auto Hash = Ancestors[Ancestors.size() - 1 - I];
+    Cache.try_emplace(Hash, Cost);
+  }
+  LLVM_DEBUG(dbgs() << "distance(" << Path << ") = " << Cost << "\n");
+  return Cost;
+}
+
+unsigned URIDistance::distance(llvm::StringRef URI) {
+  auto R = Cache.try_emplace(llvm::hash_value(URI), FileDistance::kUnreachable);
+  if (!R.second)
+    return R.first->getSecond();
+  if (auto U = clangd::URI::parse(URI)) {
+    LLVM_DEBUG(dbgs() << "distance(" << URI << ") = distance(" << U->body()
+                      << ")\n");
+    R.first->second = forScheme(U->scheme()).distance(U->body());
+  } else {
+    log("URIDistance::distance() of unparseable " + URI + ": " +
+        llvm::toString(U.takeError()));
+  }
+  return R.first->second;
+}
+
+FileDistance &URIDistance::forScheme(llvm::StringRef Scheme) {
+  auto &Delegate = ByScheme[Scheme];
+  if (!Delegate) {
+    llvm::StringMap<unsigned> SchemeRoots;
+    for (const auto &Root : Roots) {
+      if (auto U = clangd::URI::create(Root.getKey(), Scheme))
+        SchemeRoots.try_emplace(U->body(), Root.getValue());
+      else
+        consumeError(U.takeError());
+    }
+    LLVM_DEBUG(dbgs() << "FileDistance for scheme " << Scheme << ": "
+                      << SchemeRoots.size() << "/" << Roots.size()
+                      << " roots\n");
+    Delegate.reset(new FileDistance(SchemeRoots, Opts));
+  }
+  return *Delegate;
+}
+
+} // namespace clangd
+} // namespace clang

clangd/Headers.h

 
 // An #include directive that we found in the main file.
 struct Inclusion {
   Range R;             // Inclusion range.
   std::string Written; // Inclusion name as written e.g. <vector>.
   Path Resolved;       // Resolved path of included file. Empty if not resolved.
 };
 
+class IncludeStructure {
+public:
+  // All transitive includes (absolute paths), with their minimum include depth.
+  // Main file --> 0, #included file --> 1, etc.
+  std::vector<Inclusion> MainFileIncludes;
+  llvm::StringMap<unsigned> includeDepth(llvm::StringRef MainFileName) const;
+
+  // This updates IncludeDepth(), but not MainFileIncludes.
+  void recordInclude(llvm::StringRef IncludingName,
+                     llvm::StringRef IncludedName,
+                     llvm::StringRef IncludedRealName);
+
+private:
+  // Identifying files in a way that persists from preamble build to subsequent
+  // builds is surprisingly hard. FileID is unavailable in InclusionDirective(),
+  // and RealPathName and UniqueID are not preseved in the preamble.
+  // We use the FileEntry::Name, which is stable.
+  // The paths we want to expose are the RealPathName, so store those too.
+  unsigned fileNumber(llvm::StringRef Name);
+  llvm::StringMap<unsigned> NameToIndex;  // Values are file numbers.
+  std::vector<std::string> RealPathNames; // Indexed by the file number.
+  // Maps a file's number to that of the files it includes.
+  llvm::DenseMap<unsigned, SmallVector<unsigned, 8>> IncludeChildren;
+};
+
 /// Returns a PPCallback that visits all inclusions in the main file.
 std::unique_ptr<PPCallbacks>
-collectInclusionsInMainFileCallback(const SourceManager &SM,
-                                    std::function<void(Inclusion)> Callback);
+collectIncludeStructureCallback(const SourceManager &SM, IncludeStructure *Out);
 
 // Calculates insertion edit for including a new header in a file.
 class IncludeInserter {
 public:
   IncludeInserter(StringRef FileName, StringRef Code,
                   const format::FormatStyle &Style, StringRef BuildDir,
                   HeaderSearch &HeaderSearchInfo)
       : FileName(FileName), Code(Code), BuildDir(BuildDir),

clangd/Headers.cpp

 #include "llvm/Support/Path.h"
 
 namespace clang {
 namespace clangd {
 namespace {
 
 class RecordHeaders : public PPCallbacks {
 public:
-  RecordHeaders(const SourceManager &SM,
-                std::function<void(Inclusion)> Callback)
-      : SM(SM), Callback(std::move(Callback)) {}
+  RecordHeaders(const SourceManager &SM, IncludeStructure *Out)
+      : SM(SM), Out(Out) {
+        SM.getMainFileID();
+      }
 
   // Record existing #includes - both written and resolved paths. Only #includes
   // in the main file are collected.
   void InclusionDirective(SourceLocation HashLoc, const Token & /*IncludeTok*/,
                           llvm::StringRef FileName, bool IsAngled,
                           CharSourceRange FilenameRange, const FileEntry *File,
                           llvm::StringRef /*SearchPath*/,
                           llvm::StringRef /*RelativePath*/,
                           const Module * /*Imported*/,
                           SrcMgr::CharacteristicKind /*FileType*/) override {
-    // Only inclusion directives in the main file make sense. The user cannot
-    // select directives not in the main file.
-    if (HashLoc.isInvalid() || !SM.isInMainFile(HashLoc))
-      return;
-    std::string Written =
-        (IsAngled ? "<" + FileName + ">" : "\"" + FileName + "\"").str();
-    std::string Resolved = (!File || File->tryGetRealPathName().empty())
-                               ? ""
-                               : File->tryGetRealPathName();
-    Callback({halfOpenToRange(SM, FilenameRange), Written, Resolved});
+    if (SM.isInMainFile(HashLoc))
+      Out->MainFileIncludes.push_back({
+          halfOpenToRange(SM, FilenameRange),
+          (IsAngled ? "<" + FileName + ">" : "\"" + FileName + "\"").str(),
+          File ? File->tryGetRealPathName() : "",
+      });
+    if (File) {
+      auto *IncludingFileEntry=SM.getFileEntryForID(SM.getFileID(HashLoc));
+      if (!IncludingFileEntry){
+        assert(SM.getBufferName(HashLoc).startswith("<") &&
+               "Expected #include location to be a file or <built-in>");
+        // Treat as if included from the main file.
+        IncludingFileEntry = SM.getFileEntryForID(SM.getMainFileID());
+      }
+      Out->recordInclude(IncludingFileEntry->getName(), File->getName(),
+                         File->tryGetRealPathName());
+    }
   }
 
 private:
   const SourceManager &SM;
-  std::function<void(Inclusion)> Callback;
+  IncludeStructure *Out;
 };
 
 } // namespace
 
 bool isLiteralInclude(llvm::StringRef Include) {
   return Include.startswith("<") || Include.startswith("\"");
 }
 
 bool HeaderFile::valid() const {
   return (Verbatim && isLiteralInclude(File)) ||
          (!Verbatim && llvm::sys::path::is_absolute(File));
 }
 
 std::unique_ptr<PPCallbacks>
-collectInclusionsInMainFileCallback(const SourceManager &SM,
-                                    std::function<void(Inclusion)> Callback) {
-  return llvm::make_unique<RecordHeaders>(SM, std::move(Callback));
+collectIncludeStructureCallback(const SourceManager &SM,
+                                IncludeStructure *Out) {
+  return llvm::make_unique<RecordHeaders>(SM, Out);
+}
+
+void IncludeStructure::recordInclude(llvm::StringRef IncludingName,
+                                     llvm::StringRef IncludedName,
+                                     llvm::StringRef IncludedRealName) {
+  auto Child = fileNumber(IncludedName);
+  if (!IncludedRealName.empty() && RealPathNames[Child].empty())
+    RealPathNames[Child] = IncludedRealName;
+  auto Parent = fileNumber(IncludingName);
+  IncludeChildren[Parent].push_back(Child);
+}
+
+unsigned IncludeStructure::fileNumber(llvm::StringRef Name) {
+  auto R = NameToIndex.try_emplace(Name, RealPathNames.size());
+  if (R.second)
+    RealPathNames.emplace_back();
+  return R.first->getValue();
+}
+
+llvm::StringMap<unsigned>
+IncludeStructure::includeDepth(llvm::StringRef MainFileName) const {
+  llvm::StringMap<unsigned> Result;
+  Result[MainFileName] = 0;
+
+  std::vector<unsigned> CurrentLevel;
+  llvm::DenseSet<unsigned> Seen;
+  auto It = NameToIndex.find(MainFileName);
+  if (It != NameToIndex.end()) {
+    CurrentLevel.push_back(It->second);
+    Seen.insert(It->second);
+  }
+
+  std::vector<unsigned> PreviousLevel;
+  for (unsigned Level = 1; !CurrentLevel.empty(); ++Level) {
+    PreviousLevel.clear();
+    PreviousLevel.swap(CurrentLevel);
+    for (const auto& Parent : PreviousLevel) {
+      for (const auto& Child : IncludeChildren.lookup(Parent)) {
+        if (Seen.insert(Child).second) {
+          CurrentLevel.push_back(Child);
+          Result[RealPathNames[Child]] = Level;
+        }
+      }
+    }
+  }
+  return Result;
 }
 
 /// FIXME(ioeric): we might not want to insert an absolute include path if the
 /// path is not shortened.
 bool IncludeInserter::shouldInsertInclude(
     const HeaderFile &DeclaringHeader, const HeaderFile &InsertedHeader) const {
   assert(DeclaringHeader.valid() && InsertedHeader.valid());
   if (FileName == DeclaringHeader.File || FileName == InsertedHeader.File)

clangd/Quality.h

 #include <vector>
 namespace llvm {
 class raw_ostream;
 }
 namespace clang {
 class CodeCompletionResult;
 namespace clangd {
 struct Symbol;
+class URIDistance;
 
 // Signals structs are designed to be aggregated from 0 or more sources.
 // A default instance has neutral signals, and sources are merged into it.
 // They can be dumped for debugging, and evaluate()d into a score.
 
 /// Attributes of a symbol that affect how much we like it.
 struct SymbolQualitySignals {
   bool Deprecated = false;
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;
+  URIDistance *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.
   /// FIXME: unify with index proximity score - signals should be
   /// source-independent.
   float SemaProximityScore = 0;
 
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.

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 "FileDistance.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"
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 (SemaCCResult.Declaration) {
     SemaProximityScore = std::max(DeclProximity, SemaProximityScore);
   }
 
   // Declarations are scoped, others (like macros) are assumed global.
   if (SemaCCResult.Declaration)
     Scope = std::min(Scope, ComputeScope(*SemaCCResult.Declaration));
 }
 
+std::pair<float, unsigned> proximityScore(llvm::StringRef SymbolURI, URIDistance *D) {
+  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};
+}
+
 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 + std::max(IndexProximityScore, SemaProximityScore);
+  // range from 1 to 3.
+  Score *= 1 + 2 * std::max(proximityScore(SymbolURI, FileProximityMatch).first,
+                            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:

 }
 
 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("\tSymbol URI: {0}\n", S.SymbolURI);
   if (S.FileProximityMatch) {
-    OS << formatv("\tIndex proximity: {0}\n",
-                  S.FileProximityMatch->uriProximity(S.SymbolURI))
-       << " (" << *S.FileProximityMatch << ")\n";
+    auto Score = proximityScore(S.SymbolURI, S.FileProximityMatch);
+    OS << formatv("\tIndex 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));
   return OS;
 }
 
 float evaluateSymbolAndRelevance(float SymbolQuality, float SymbolRelevance) {

clangd/XRefs.cpp

llvm::Optional<SymbolID> getSymbolID(const Decl *D) {
   return SymbolID(USR);
 }
 
 } // namespace
 
 std::vector<Location> findDefinitions(ParsedAST &AST, Position Pos,
                                       const SymbolIndex *Index) {
   const SourceManager &SourceMgr = AST.getASTContext().getSourceManager();
-  SourceLocation SourceLocationBeg =
-      getBeginningOfIdentifier(AST, Pos, SourceMgr.getMainFileID());
 
   std::vector<Location> Result;
   // Handle goto definition for #include.
-  for (auto &Inc : AST.getInclusions()) {
-    Position Pos = sourceLocToPosition(SourceMgr, SourceLocationBeg);
+  for (auto &Inc : AST.getIncludeStructure().MainFileIncludes) {
     if (!Inc.Resolved.empty() && Inc.R.contains(Pos))
       Result.push_back(Location{URIForFile{Inc.Resolved}, {}});
   }
   if (!Result.empty())
     return Result;
 
   // Identified symbols at a specific position.
+  SourceLocation SourceLocationBeg =
+      getBeginningOfIdentifier(AST, Pos, SourceMgr.getMainFileID());
   auto Symbols = getSymbolAtPosition(AST, SourceLocationBeg);
 
   for (auto Item : Symbols.Macros) {
     auto Loc = Item.Info->getDefinitionLoc();
     auto L = makeLocation(AST, SourceRange(Loc, Loc));
     if (L)
       Result.push_back(*L);
   }

unittests/clangd/CMakeLists.txt

add_extra_unittest(ClangdTests
   Annotations.cpp
   ClangdTests.cpp
   ClangdUnitTests.cpp
   CodeCompleteTests.cpp
   CodeCompletionStringsTests.cpp
   ContextTests.cpp
   DraftStoreTests.cpp
   FileIndexTests.cpp
+  FileDistanceTests.cpp
   FindSymbolsTests.cpp
   FuzzyMatchTests.cpp
   GlobalCompilationDatabaseTests.cpp
   HeadersTests.cpp
   IndexTests.cpp
   JSONExprTests.cpp
   QualityTests.cpp
   SourceCodeTests.cpp

unittests/clangd/FileDistanceTests.cpp

+//===-- FileDistanceTests.cpp  ------------------------*- C++ -*-----------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "FileDistance.h"
+#include "TestFS.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+namespace clang {
+namespace clangd {
+namespace {
+
+TEST(FileDistanceTests, Distance) {
+  FileDistanceOptions Opts;
+  Opts.UpCost = 5;
+  Opts.DownCost = 3;
+  FileDistance D({{"tools/clang/lib/Format/FormatToken.cpp", 0},
+                  {"tools/clang/include/clang/Format/FormatToken.h", 0},
+                  {"include/llvm/ADT/StringRef.h", 2}},
+                 Opts);
+
+  // Root
+  EXPECT_EQ(D.distance("tools/clang/lib/Format/FormatToken.cpp"), 0u);
+  EXPECT_EQ(D.distance("include/llvm/ADT/StringRef.h"), 2u);
+  // Parent
+  EXPECT_EQ(D.distance("tools/clang/lib/Format/"), 5u);
+  // Child
+  EXPECT_EQ(D.distance("tools/clang/lib/Format/FormatToken.cpp/Oops"), 3u);
+  // Ancestor (up+up+up+up)
+  EXPECT_EQ(D.distance("/"), 22u);
+  // Sibling (up+down)
+  EXPECT_EQ(D.distance("tools/clang/lib/Format/AnotherFile.cpp"), 8u);
+  // Cousin (up+up+down+down)
+  EXPECT_EQ(D.distance("include/llvm/Support/Allocator.h"), 18u);
+  // First cousin, once removed (up+up+up+down+down)
+  EXPECT_EQ(D.distance("include/llvm-c/Core.h"), 23u);
+}
+
+auto UseUnittestScheme = UnittestSchemeAnchorSource;
+
+TEST(FileDistanceTests, URI) {
+  FileDistanceOptions Opts;
+  Opts.UpCost = 5;
+  Opts.DownCost = 3;
+
+  URIDistance D({{testPath("foo"), 1000}, {"/not/a/testpath", 0}}, Opts);
+  EXPECT_EQ(D.distance("file:///not/a/testpath/either"), 3u);
+  EXPECT_EQ(D.distance("unittest:foo"), 1000u);
+  EXPECT_EQ(D.distance("unittest:bar"), 1008u);
+}
+
+} // namespace
+} // namespace clangd
+} // namespace clang

unittests/clangd/HeadersTests.cpp

auto Clang = prepareCompilerInstance(
         llvm::MemoryBuffer::getMemBuffer(FS.Files[MainFile], MainFile),
         std::make_shared<PCHContainerOperations>(), VFS, IgnoreDiags);
 
     EXPECT_FALSE(Clang->getFrontendOpts().Inputs.empty());
     return Clang;
   }
 
 protected:
-  std::vector<Inclusion> collectIncludes() {
+  IncludeStructure collectIncludes() {
     auto Clang = setupClang();
     PreprocessOnlyAction Action;
     EXPECT_TRUE(
         Action.BeginSourceFile(*Clang, Clang->getFrontendOpts().Inputs[0]));
-    std::vector<Inclusion> Inclusions;
-    Clang->getPreprocessor().addPPCallbacks(collectInclusionsInMainFileCallback(
-        Clang->getSourceManager(),
-        [&](Inclusion Inc) { Inclusions.push_back(std::move(Inc)); }));
+    IncludeStructure Includes;
+    Clang->getPreprocessor().addPPCallbacks(
+        collectIncludeStructureCallback(Clang->getSourceManager(), &Includes));
     EXPECT_TRUE(Action.Execute());
     Action.EndSourceFile();
-    return Inclusions;
+    return Includes;
   }
 
   // Calculates the include path, or returns "" on error or header should not be
   // inserted.
   std::string calculate(PathRef Original, PathRef Preferred = "",
                         const std::vector<Inclusion> &Inclusions = {}) {
     auto Clang = setupClang();
     PreprocessOnlyAction Action;
protected:
   std::string Subdir = testPath("sub");
   std::string SearchDirArg = (llvm::Twine("-I") + Subdir).str();
   IgnoringDiagConsumer IgnoreDiags;
 };
 
 MATCHER_P(Written, Name, "") { return arg.Written == Name; }
 MATCHER_P(Resolved, Name, "") { return arg.Resolved == Name; }
 
+MATCHER_P2(Distance,File, D, "") {
+  if (arg.getKey() != File)
+    *result_listener << "file =" << arg.getKey().str();
+  if (arg.getValue() != D)
+    *result_listener << "distance =" << arg.getValue();
+  return arg.getKey() == File && arg.getValue() == D;
+}
+
 TEST_F(HeadersTest, CollectRewrittenAndResolved) {
   FS.Files[MainFile] = R"cpp(
 #include "sub/bar.h" // not shortest
 )cpp";
   std::string BarHeader = testPath("sub/bar.h");
   FS.Files[BarHeader] = "";
 
-  EXPECT_THAT(collectIncludes(),
+  EXPECT_THAT(collectIncludes().MainFileIncludes,
               UnorderedElementsAre(
                   AllOf(Written("\"sub/bar.h\""), Resolved(BarHeader))));
+  EXPECT_THAT(collectIncludes().includeDepth(MainFile),
+              UnorderedElementsAre(Distance(MainFile, 0u),
+                                   Distance(testPath("sub/bar.h"), 1u)));
 }
 
 TEST_F(HeadersTest, OnlyCollectInclusionsInMain) {
   std::string BazHeader = testPath("sub/baz.h");
   FS.Files[BazHeader] = "";
   std::string BarHeader = testPath("sub/bar.h");
   FS.Files[BarHeader] = R"cpp(
 #include "baz.h"
 )cpp";
   FS.Files[MainFile] = R"cpp(
 #include "bar.h"
 )cpp";
   EXPECT_THAT(
-      collectIncludes(),
+      collectIncludes().MainFileIncludes,
       UnorderedElementsAre(AllOf(Written("\"bar.h\""), Resolved(BarHeader))));
+  EXPECT_THAT(collectIncludes().includeDepth(MainFile),
+              UnorderedElementsAre(Distance(MainFile, 0u),
+                                   Distance(testPath("sub/bar.h"), 1u),
+                                   Distance(testPath("sub/baz.h"), 2u)));
 }
 
 TEST_F(HeadersTest, UnResolvedInclusion) {
   FS.Files[MainFile] = R"cpp(
 #include "foo.h"
 )cpp";
 
-  EXPECT_THAT(collectIncludes(),
+  EXPECT_THAT(collectIncludes().MainFileIncludes,
               UnorderedElementsAre(AllOf(Written("\"foo.h\""), Resolved(""))));
+  EXPECT_THAT(collectIncludes().includeDepth(MainFile),
+              UnorderedElementsAre(Distance(MainFile, 0u)));
 }
 
 TEST_F(HeadersTest, InsertInclude) {
   std::string Path = testPath("sub/bar.h");
   FS.Files[Path] = "";
   EXPECT_EQ(calculate(Path), "\"bar.h\"");
 }
 

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 "FileDistance.h"
 #include "TestFS.h"
 #include "TestTU.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 namespace clang {
 namespace clangd {
 
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 WithProximity;
-  WithProximity.SemaProximityScore = 0.2f;
-  EXPECT_GT(WithProximity.evaluate(), Default.evaluate());
+  SymbolRelevanceSignals WithSemaProximity;
+  WithSemaProximity.SemaProximityScore = 0.2f;
+  EXPECT_GT(WithSemaProximity.evaluate(), Default.evaluate());
+
+  SymbolRelevanceSignals IndexProximate;
+  IndexProximate.SymbolURI = "unittest:/foo/bar.h";
+  llvm::StringMap<unsigned> ProxRoots;
+  ProxRoots[testPath("foo/baz.h")] = 0;
+  URIDistance Distance(ProxRoots);
+  IndexProximate.FileProximityMatch = &Distance;
+  EXPECT_GT(IndexProximate.evaluate(), Default.evaluate());
+  SymbolRelevanceSignals IndexDistant = IndexProximate;
+  IndexDistant.SymbolURI = "unittest:/elsewhere/path.h";
+  EXPECT_GT(IndexProximate.evaluate(), IndexDistant.evaluate()) << IndexProximate << IndexDistant;
+  EXPECT_GT(IndexDistant.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