[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 ↗

(On Diff #152326)

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

938 ↗

(On Diff #152326)

nit: Style?

clangd/FileDistance.cpp

72 ↗

(On Diff #152326)

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

86 ↗

(On Diff #152326)

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

clangd/FileDistance.h

56 ↗

(On Diff #152326)

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

clangd/Headers.cpp

28 ↗

(On Diff #152326)

What does this do?

clangd/Headers.h

62 ↗

(On Diff #152326)

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 ↗

(On Diff #152326)

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

75 ↗

(On Diff #152326)

Maybe fileIndex?

clangd/Quality.cpp

233 ↗

(On Diff #152326)

nit: static

unittests/clangd/FileDistanceTests.cpp

36 ↗

(On Diff #152326)

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

35 ↗

(On Diff #152326)

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

86 ↗

(On Diff #152326)

(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

56 ↗

(On Diff #152326)

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

clangd/Headers.h

62 ↗

(On Diff #152326)

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 ↗

(On Diff #152326)

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

36 ↗

(On Diff #152326)

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

9 ↗

(On Diff #152479)

Is this intentionally reserved?

51 ↗

(On Diff #152479)

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

86 ↗

(On Diff #152479)

Should we also check the cache here?

unittests/clangd/FileDistanceTests.cpp

36 ↗

(On Diff #152326)

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

26 ↗

(On Diff #153504)

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

9 ↗

(On Diff #152479)

Oops, added implementation docs

51 ↗

(On Diff #152479)

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

86 ↗

(On Diff #152479)

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.

clang-tools-extra/trunk/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

clang-tools-extra/trunk/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.
     CodeCompleteResult 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)));
 }
 

clang-tools-extra/trunk/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);

clang-tools-extra/trunk/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(
-      Clang->getSourceManager(),
-      [&Inclusions](Inclusion Inc) { Inclusions.push_back(std::move(Inc)); }));
+  auto Includes = Preamble ? Preamble->Includes : IncludeStructure{};
+  Clang->getPreprocessor().addPPCallbacks(
+      collectIncludeStructureCallback(Clang->getSourceManager(), &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)
+                           std::vector<Diag> Diags, 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,

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

 raw_ostream &operator<<(raw_ostream &, const CodeCompletion &);
 struct CodeCompleteResult {
   std::vector<CodeCompletion> Completions;
   bool HasMore = false;
 };
 raw_ostream &operator<<(raw_ostream &, const CodeCompleteResult &);
 
 /// Get code completions at a specified \p Pos in \p FileName.
-CodeCompleteResult codeComplete(
-    PathRef FileName, const tooling::CompileCommand &Command,
+CodeCompleteResult codeComplete(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, CodeCompleteOptions Opts);
+                                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,
                             PrecompiledPreamble const *Preamble,
                             StringRef Contents, Position Pos,
                             IntrusiveRefCntPtr<vfs::FileSystem> VFS,
                             std::shared_ptr<PCHContainerOperations> PCHs);

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

 // it's purely AST-based, and there are few candidates.
 //
 //===---------------------------------------------------------------------===//
 
 #include "CodeComplete.h"
 #include "AST.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(format::DefaultFormatStyle, Input.FileName,
-                                  format::DefaultFallbackStyle, Input.Contents,
-                                  Input.VFS.get());
-    if (!Style) {
-      log("ERROR: 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;
+  // Include-insertion and proximity scoring rely on the include structure.
+  // This is available after Sema has run.
+  llvm::Optional<IncludeInserter> Inserter;  // Available during runWithSema.
+  llvm::Optional<URIDistance> FileProximity; // Initialized once Sema runs.
 
 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) {}
 
   CodeCompleteResult 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.
     CodeCompleteResult 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, *Style,
+          SemaCCInput.Command.Directory,
+          Recorder->CCSema->getPreprocessor().getHeaderSearchInfo());
+      for (const auto &Inc : Includes.MainFileIncludes)
+        Inserter->addExisting(Inc);
+
+      // Most of the cost of file proximity is in initializing the FileDistance
+      // structures based on the observed includes, once per query. Conceptually
+      // that happens here (though the per-URI-scheme initialization is lazy).
+      // The per-result proximity scoring is (amortized) very cheap.
+      FileDistanceOptions ProxOpts{}; // Use defaults.
+      const auto &SM = Recorder->CCSema->getSourceManager();
+      llvm::StringMap<SourceParams> ProxSources;
+      for (auto &Entry : Includes.includeDepth(
+               SM.getFileEntryForID(SM.getMainFileID())->getName())) {
+        auto &Source = ProxSources[Entry.getKey()];
+        Source.Cost = Entry.getValue() * ProxOpts.IncludeCost;
+        // Symbols near our transitive includes are good, but only consider
+        // things in the same directory or below it. Otherwise there can be
+        // many false positives.
+        if (Entry.getValue() > 0)
+          Source.MaxUpTraversals = 1;
+      }
+      FileProximity.emplace(ProxSources, 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) {
private:
   CodeCompletion toCodeCompletion(const CompletionCandidate::Bundle &Bundle) {
     llvm::Optional<CodeCompletionBuilder> Builder;
     for (const auto &Item : Bundle) {
       CodeCompletionString *SemaCCS =
           Item.SemaResult ? Recorder->codeCompletionString(*Item.SemaResult)
                           : nullptr;
       if (!Builder)
         Builder.emplace(Recorder->CCSema->getASTContext(), Item, SemaCCS,
-                        *Includes, FileName, Opts);
+                        *Inserter, FileName, Opts);
       else
         Builder->add(Item, SemaCCS);
     }
     return Builder->build();
   }
 };
 
-CodeCompleteResult codeComplete(
-    PathRef FileName, const tooling::CompileCommand &Command,
+CodeCompleteResult codeComplete(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, CodeCompleteOptions Opts) {
-  return CodeCompleteFlow(FileName, Opts)
-      .run({FileName, Command, Preamble, PreambleInclusions, Contents, Pos, VFS,
-            PCHs});
+                                const IncludeStructure &PreambleInclusions,
+                                StringRef Contents, Position Pos,
+                                IntrusiveRefCntPtr<vfs::FileSystem> VFS,
+                                std::shared_ptr<PCHContainerOperations> PCHs,
+                                CodeCompleteOptions Opts) {
+  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,

clang-tools-extra/trunk/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 sources:
+// 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 (anchor, cost) pairs, and call the distance to a
+// path the minimum of `cost + |source -> path|`.
+//
+// We allow each source to limit the number of up-traversals paths may start
+// with. Up-traversals may reach things that are not "semantically near".
+//
+// 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.
+//
+// Caveats:
+// Assuming up and down traversals each have uniform costs is simplistic.
+// Often there are "semantic roots" whose children are almost unrelated.
+// (e.g. /usr/include/, or / in an umbrella repository). We ignore this.
+//
+//===----------------------------------------------------------------------===//
+
+#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|
+};
+
+struct SourceParams {
+  // Base cost for paths starting at this source.
+  unsigned Cost = 0;
+  // Limits the number of upwards traversals allowed from this source.
+  unsigned MaxUpTraversals = std::numeric_limits<unsigned>::max();
+};
+
+// Supports lookups to find the minimum distance to a file from any source.
+// This object should be reused, it memoizes intermediate computations.
+class FileDistance {
+public:
+  static constexpr unsigned kUnreachable = std::numeric_limits<unsigned>::max();
+
+  FileDistance(llvm::StringMap<SourceParams> Sources,
+               const FileDistanceOptions &Opts = {});
+
+  // Computes the minimum distance from any source to the file path.
+  unsigned distance(llvm::StringRef Path);
+
+private:
+  // Costs computed so far. Always contains sources 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 sources to the scheme of the URI and do a FileDistance
+// comparison on the bodies.
+class URIDistance {
+public:
+  URIDistance(llvm::StringMap<SourceParams> Sources,
+              const FileDistanceOptions &Opts = {})
+      : Sources(Sources), Opts(Opts) {}
+
+  // Computes the minimum distance from any source to the URI.
+  // Only sources 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<SourceParams> Sources;
+  llvm::StringMap<std::unique_ptr<FileDistance>> ByScheme;
+  FileDistanceOptions Opts;
+};
+
+} // namespace clangd
+} // namespace clang

clang-tools-extra/trunk/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.
+//
+//===----------------------------------------------------------------------===//
+//
+// The FileDistance structure allows calculating the minimum distance to paths
+// in a single tree.
+// We simply walk up the path's ancestors until we find a node whose cost is
+// known, and add the cost of walking back down. Initialization ensures this
+// gives the correct path to the roots.
+// We cache the results, so that the runtime is O(|A|), where A is the set of
+// all distinct ancestors of visited paths.
+//
+// Example after initialization with /=2, /bar=0, DownCost = 1:
+//  / = 2
+//    /bar = 0
+//
+// After querying /foo/bar and /bar/foo:
+//  / = 2
+//    /bar = 0
+//      /bar/foo = 1
+//    /foo = 3
+//      /foo/bar = 4
+//
+// URIDistance creates FileDistance lazily for each URI scheme encountered. In
+// practice this is a small constant factor.
+//
+//===-------------------------------------------------------------------------//
+
+#include "FileDistance.h"
+#include "Logger.h"
+#include "llvm/ADT/STLExtras.h"
+#include <queue>
+#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<SourceParams> Sources,
+                           const FileDistanceOptions &Opts)
+    : Opts(Opts) {
+  llvm::DenseMap<hash_code, SmallVector<hash_code, 4>> DownEdges;
+  // Compute the best distance following only up edges.
+  // Keep track of down edges, in case we can use them to improve on this.
+  for (const auto &S : Sources) {
+    auto Canonical = canonicalize(S.getKey());
+    LLVM_DEBUG(dbgs() << "Source " << Canonical << " = " << S.second.Cost
+                      << ", MaxUp=" << S.second.MaxUpTraversals << "\n");
+    // Walk up to ancestors of this source, assigning cost.
+    StringRef Rest = Canonical;
+    llvm::hash_code Hash = hash_value(Rest);
+    for (unsigned I = 0; !Rest.empty(); ++I) {
+      Rest = parent_path(Rest, sys::path::Style::posix);
+      auto NextHash = hash_value(Rest);
+      DownEdges[NextHash].push_back(Hash);
+      // We can't just break after MaxUpTraversals, must still set DownEdges.
+      if (I > S.getValue().MaxUpTraversals) {
+        if (Cache.find(Hash) != Cache.end())
+          break;
+      } else {
+        unsigned Cost = S.getValue().Cost + I * Opts.UpCost;
+        auto R = Cache.try_emplace(Hash, 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;
+          }
+        }
+      }
+      Hash = NextHash;
+    }
+  }
+  // Now propagate scores parent -> child if that's an improvement.
+  // BFS ensures we propagate down chains (must visit parents before children).
+  std::queue<hash_code> Next;
+  for (auto Child : DownEdges.lookup(hash_value(llvm::StringRef(""))))
+    Next.push(Child);
+  while (!Next.empty()) {
+    auto ParentCost = Cache.lookup(Next.front());
+    for (auto Child : DownEdges.lookup(Next.front())) {
+      auto &ChildCost =
+          Cache.try_emplace(Child, kUnreachable).first->getSecond();
+      if (ParentCost + Opts.DownCost < ChildCost)
+        ChildCost = ParentCost + Opts.DownCost;
+      Next.push(Child);
+    }
+    Next.pop();
+  }
+}
+
+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);
+  }
+  // Now we know the costs for (known node, queried node].
+  // Fill these in, walking down the directory tree.
+  for (hash_code Hash : reverse(Ancestors)) {
+    if (Cost != kUnreachable)
+      Cost += Opts.DownCost;
+    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<SourceParams> SchemeSources;
+    for (const auto &Source : Sources) {
+      if (auto U = clangd::URI::create(Source.getKey(), Scheme))
+        SchemeSources.try_emplace(U->body(), Source.getValue());
+      else
+        consumeError(U.takeError());
+    }
+    LLVM_DEBUG(dbgs() << "FileDistance for scheme " << Scheme << ": "
+                      << SchemeSources.size() << "/" << Sources.size()
+                      << " sources\n");
+    Delegate.reset(new FileDistance(std::move(SchemeSources), Opts));
+  }
+  return *Delegate;
+}
+
+} // namespace clangd
+} // namespace clang

clang-tools-extra/trunk/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.
 };
 
+// Information captured about the inclusion graph in a translation unit.
+// This includes detailed information about the direct #includes, and summary
+// information about all transitive includes.
+//
+// It should be built incrementally with collectIncludeStructureCallback().
+// When we build the preamble, we capture and store its include structure along
+// with the preamble data. When we use the preamble, we can copy its
+// IncludeStructure and use another collectIncludeStructureCallback() to fill
+// in any non-preamble inclusions.
+class IncludeStructure {
+public:
+  std::vector<Inclusion> MainFileIncludes;
+
+  // Return all transitively reachable files, and their minimum include depth.
+  // All transitive includes (absolute paths), with their minimum include depth.
+  // Root --> 0, #included file --> 1, etc.
+  // Root is clang's name for a file, which may not be absolute.
+  // Usually it should be SM.getFileEntryForID(SM.getMainFileID())->getName().
+  llvm::StringMap<unsigned> includeDepth(llvm::StringRef Root) 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, interned into a "file index".
+  // The paths we want to expose are the RealPathName, so store those too.
+  std::vector<std::string> RealPathNames; // In file index order.
+  unsigned fileIndex(llvm::StringRef Name);
+  llvm::StringMap<unsigned> NameToIndex; // Values are file indexes.
+  // Maps a file's index 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),

clang-tools-extra/trunk/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) {}
 
   // 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 = fileIndex(IncludedName);
+  if (!IncludedRealName.empty() && RealPathNames[Child].empty())
+    RealPathNames[Child] = IncludedRealName;
+  auto Parent = fileIndex(IncludingName);
+  IncludeChildren[Parent].push_back(Child);
+}
+
+unsigned IncludeStructure::fileIndex(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 Root) const {
+  // Include depth 0 is the main file only.
+  llvm::StringMap<unsigned> Result;
+  Result[Root] = 0;
+  std::vector<unsigned> CurrentLevel;
+  llvm::DenseSet<unsigned> Seen;
+  auto It = NameToIndex.find(Root);
+  if (It != NameToIndex.end()) {
+    CurrentLevel.push_back(It->second);
+    Seen.insert(It->second);
+  }
+
+  // Each round of BFS traversal finds the next depth level.
+  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);
+          const auto &Name = RealPathNames[Child];
+          // Can't include files if we don't have their real path.
+          if (!Name.empty())
+            Result[Name] = 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)

clang-tools-extra/trunk/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.

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 <cmath>
+#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/CharInfo.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Sema/CodeCompleteConsumer.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/raw_ostream.h"
+#include <cmath>
 
 namespace clang {
 namespace clangd {
 using namespace llvm;
 static bool IsReserved(StringRef Name) {
   // FIXME: Should we exclude _Bool and others recognized by the standard?
   return Name.size() >= 2 && Name[0] == '_' &&
          (isUppercase(Name[1]) || Name[1] == '_');
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) {
   // Injected "Foo" within the class "Foo" has file scope, not class scope.
   const DeclContext *DC = D->getDeclContext();
   if (auto *R = dyn_cast_or_null<RecordDecl>(D))
     if (R->isInjectedClassName())
       DC = DC->getParent();
   bool InClass = false;
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));
 }
 
+static 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 << "\tIndex proximity: "
-       << 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) {

clang-tools-extra/trunk/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);
   }

clang-tools-extra/trunk/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

clang-tools-extra/trunk/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;
+  SourceParams CostTwo;
+  CostTwo.Cost = 2;
+  FileDistance D(
+      {{"tools/clang/lib/Format/FormatToken.cpp", SourceParams()},
+       {"tools/clang/include/clang/Format/FormatToken.h", SourceParams()},
+       {"include/llvm/ADT/StringRef.h", CostTwo}},
+      Opts);
+
+  // Source
+  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);
+}
+
+TEST(FileDistanceTests, BadSource) {
+  // We mustn't assume that paths above sources are best reached via them.
+  FileDistanceOptions Opts;
+  Opts.UpCost = 5;
+  Opts.DownCost = 3;
+  SourceParams CostLots;
+  CostLots.Cost = 100;
+  FileDistance D({{"a", SourceParams()}, {"b/b/b", CostLots}}, Opts);
+  EXPECT_EQ(D.distance("b"), 8u);        // a+up+down, not b+up+up
+  EXPECT_EQ(D.distance("b/b/b"), 14u);   // a+up+down+down+down, not b
+  EXPECT_EQ(D.distance("b/b/b/c"), 17u); // a+up+down+down+down+down, not b+down
+}
+
+auto UseUnittestScheme = UnittestSchemeAnchorSource;
+
+TEST(FileDistanceTests, URI) {
+  FileDistanceOptions Opts;
+  Opts.UpCost = 5;
+  Opts.DownCost = 3;
+  SourceParams CostLots;
+  CostLots.Cost = 1000;
+
+  URIDistance D(
+      {{testPath("foo"), CostLots}, {"/not/a/testpath", SourceParams()}}, 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);
+}
+
+TEST(FileDistance, LimitUpTraversals) {
+  FileDistanceOptions Opts;
+  Opts.UpCost = Opts.DownCost = 1;
+  SourceParams CheapButLimited, CostLots;
+  CheapButLimited.MaxUpTraversals = 1;
+  CostLots.Cost = 100;
+
+  FileDistance D({{"/", CostLots}, {"/a/b/c", CheapButLimited}}, Opts);
+  EXPECT_EQ(D.distance("/a"), 101u);
+  EXPECT_EQ(D.distance("/a/z"), 102u);
+  EXPECT_EQ(D.distance("/a/b"), 1u);
+  EXPECT_EQ(D.distance("/a/b/z"), 2u);
+}
+
+} // namespace
+} // namespace clangd
+} // namespace clang

clang-tools-extra/trunk/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)));
+  // includeDepth() also works for non-main files.
+  EXPECT_THAT(collectIncludes().includeDepth(testPath("sub/bar.h")),
+              UnorderedElementsAre(Distance(testPath("sub/bar.h"), 0u),
+                                   Distance(testPath("sub/baz.h"), 1u)));
 }
 
 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\"");
 }
 

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

 // make good hard assertions.
 //
 // 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 "FileDistance.h"
 #include "Quality.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<SourceParams> ProxSources;
+  ProxSources.try_emplace(testPath("foo/baz.h"));
+  URIDistance Distance(ProxSources);
+  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.7f;
-
-// 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