[clangd] Cache FS stat() calls when building preamble.

[ioeric]

Summary

The file stats can be reused when preamble is reused (e.g. code
completion). It's safe to assume that cached status is not outdated as we
assume preamble files to remain unchanged.

On real file system, this made code completion ~20% faster on a measured file
(with big preamble). The preamble build time doesn't change much.

[ioeric]

• update comment

[ioeric]

clangd/ClangdUnit.cpp

117

Would it make sense to add a clang::vfs::ProxyFS that proxies calls to underlying FS by default and allows to override some methods?

[ilya-biryukov]

clangd/ClangdUnit.cpp

117

This makes sense, we seem to have a recurring pattern of forwarding all methods by default in this commit.
+1 to the suggestion

126

One can obtain file stats from the returned iterator.
I believe this is exactly what will start happening after Sam's patch to list dirs when processing include dirs.

We should probably also wrap iterators that we return and cache stats from those.

147

If we cache the stats, we should probably cache the file contents too.
Not sure how much of an extra memory this will require.

Though maybe we could get away with returning the old stat, but new file contents. It would look as if the file was between calls to stat() and openForRead.

284

We store absolute paths, but Path can be relative here.

285

Maybe remove parens?
Comparisons associate properly with ternary op and it's common enough to not cause any confusion with the reader.

clangd/CodeComplete.cpp

1057

Maybe pass a single pointer to PreambleData here?

1081

It feels like we could apply this caching one level higher, on the TUScheduler level when creating the filesystem. It makes sense not only for code completion, but also for all other features, including rebuilds of ASTs that were washed out of the cache.
WDYT?

1683

signatureHelp could also benefit from the cached fs, maybe pass it too?
See the other comments about applying this caching one level higher (on TUScheduler level) too.

clangd/CodeComplete.h

227

We should not be depending TUScheduler.h, I suggest to pass PreambleDatainstead of PrecompiledPreamble instead.

Depending on TUScheduler.h our layering in clangd: low-level implementation of features should not depend on higher-level building blocks like TUScheduler.

[sammccall]

Nice win!

This is missing high-level documentation explaining what problem it's trying to solve and what the lifetime is.
I think pulling the factories out into a dedicated header would give you good space for that.

clangd/ClangdUnit.cpp

126

The returned iterator can't be used to obtain file status (since my patch).

147

I don't think I agree, what's the argument for caching both?

In the observed profile, stats are a problem but openFileForRead is not (in fact the files are never open).

This can't be a hard correctness requirement, because stat->open is racy anyway.

153

why are you only caching success?

164

this isn't threadsafe.

Note that adding a lock here isn't enough, as you may have multiple FS instances referring to the same cache. The lock needs to live alongside the cache storage, so the latter should probably be a class.

257

outline this implementation next to the other one, and give them parallel names?

statCacheProducingFS/statCacheConsumingFS?

The design is hard to follow without this parallelism explicit.

clangd/ClangdUnit.h

54

This doesn't belong in ClangdUnit.
(Potentially it could live in clang as a VFS util, but a FS.h or so here seems fine. Maybe merge with FSProvider.h)

clangd/CodeComplete.h

227

+1. We're maybe not doing the best job of header encapsulation here, but InputsAndPreamble is an implementation detail of ClangdServer.

[ioeric]

• Address review comments

[ioeric]

Thanks for the reviews!

clangd/ClangdUnit.cpp

153

I had a comment in openFileForRead:

// Only cache stats for files that exist because, unlike building preamble,
// we only care about existing files when reusing preamble.

Another reason is that we are using the file name in the Status as the cache key.

284

This is because preamble stores absolute paths. Path should be an path from preamble. Added documentation.

clangd/CodeComplete.cpp

1081

It sounds like a reasonable thing to do. I took a quick look, and it seemed that this would probably require some refactoring/redesign on TUScheduler - it doesn't know about the VFS?

I think it shouldn't be hard to do this case by case. For example, code completion and signature help will be covered in this patch. And it should be pretty easy to make AST rebuild use the cache as well?

clangd/CodeComplete.h

227

I thought InputsAndPreamble was a pretty natural fit here, but I guess I hadn't understand the abstractions well enough. Thanks for the explanation!

[sammccall]

Generally LG. A few things I'm unsure about.

clangd/CodeComplete.cpp

1081

It sounds like a reasonable thing to do. I took a quick look, and it seemed that this would probably require some refactoring/redesign on TUScheduler - it doesn't know about the VFS?

Right, this is a bit of a mess...
Currently there are features that access the FS "directly". This includes CodeComplete which runs its own compile action, as well as things like switchSourceHeader or format. These invoke FSProvider.
Then there are features that build an AST (which may need file accesses), and then may implicitly read files by querying the AST (the FS is attached to the FileManager or something). These use the FS obtained from the FSProvider in the relevant addDocument call.
There's no fundamental reason we can't have both (access FS directly and use the AST) in which case we'll be using both filesystems together...

In the near term, making the TUScheduler-managed AST rebuild use the cache stored in the preamble seems like a nice win. (As you alluded to I don't think this change is in TUScheduler itself, rather buildAST?)

clangd/FS.cpp

2

Can we have unit tests for these?
It should be pretty straightforward, as you can inspect/seed the cache state directly.

30

lock

49

I'm not sure I get this: AFAICT (at least on linux) the status is never available on a newly opened file, so this will always be a stat() call, so we're just doing the work eagerly and caching it for later. Isn't this just moving the work around?

I'm sure you've verified this is important somehow, but a comment explaining how would be much appreciated :-)

clangd/FS.h

21

can you give a little more colour on *why* code completion tends to stat a bunch of the same files over again?
(One might assume it's to validate the preamble, but it shouldn't be, because we don't do that for other reasons)

22

whene -> when

unittests/clangd/ClangdTests.cpp

966

it's not obvious what this test does (without the rest of the patch as context).
Maybe a high-level comment: Check that running code completion doesn't stat() a bunch of files from the preamble again. (They should be using the preamble's stat-cache)

980

just ++CountStats[...]?
life is too short :-)

984

or just return ProxyFileSystem::status(Path); which is *slightly* less coupled

1018

I think this would be much clearer if we asserted the actual count here. It should be 1, right? Do you think it'd be too brittle?

As it stands, it seems entirely possible that the test is not seeing any stats for whatever reason and is spuriously passing.

[ilya-biryukov]

clangd/ClangdUnit.cpp

284

It's true that preamble stores and checks absolute paths, however clang can later access the same file using a relative path.
Calling makeAbsolute here shouldn't hurt and would obviously make it work in both cases.

clangd/CodeComplete.cpp

1081

My idea would be to create and pass the updated cached FS into both buildAST and codeComplete higher up the call chain. This would allow localizing the code that creates caching VFSes in one file (TUScheduler.h or similar).

The advantage of receiving the patched-up FS in buildAST and codeComplete is that they don't have to care about this trick, making the implementation simpler.
The fewer functions across the codebase have to apply the trick the better, e.g. this would make sure we won't accidentally forget it to apply it when implementing a new feature.

[ioeric]

• address review comments

[ioeric]

clangd/ClangdUnit.cpp

284

It would "obviously work"... until you have symlinks and tricks to handle symlinks ;)

clangd/CodeComplete.cpp

1081

Added the cache support to buildAST as we thinks it's beneficial (haven't profiled this though).

Currently, the trick is applied in two places (semaCodeComplete in CodeComplete and buildAST in ClangdUnit), and I'm not sure how much this would grow in the near future. It's also unclear to me whether baking this into TUScheduler would be less work in the long run. I would suggest revisiting this when we have more evidence.

clangd/FS.cpp

30

After a second thought, I'm wondering if the mutex is necessary, if the cache is only updated during preamble build in a single thread. The cache would also remain the same in preamble reuses.

49

Files opened via openFileForRead() wouldn't usually trigger status() calls on the wrap FS. And most header files are opened instead of stated.

Added comment explaining this.

[sammccall]

clangd/FS.cpp

30

Indeed if you have the following sequencing:

• one FS writes to the cache from one thread (or several but strictly sequenced)
• sequence point (no writes after this point, no reads before)
• several FSs read from the cache

then no lock is required, either for writer or reader.
The API doesn't particularly suggest this, so please explicitly document the threading model in the header.
(An API that would suggest it is to e.g. make the producing FS the top-level object, give it a &&-qualified method to retrieve the cache, and give the cache methods to retrieve the consuming FSes. But I think that's awkward here with the VFS interface)

49

Ah, OK.
The implementation comment is good, but this is significantly different from "caching stat calls" as described in the header files.

Maybe update the comment there: e.g. "Records status information for files open()ed or stat()ed during preamble build, so we can avoid stat()s on the underlying FS when reusing the preamble"

54

do you want to check if the file is already in the stat cache first?

[ioeric]

• Address review comments
• address review comments
• address review comments

clangd/FS.cpp

30

(Stole some wording here. Thanks!)

54

This would always invalidate status in cache when file is reopened or restated in case file status has changed during preamble build. Added a comment.

[sammccall]

Sorry for dropping this.

clangd/ClangdUnit.h

58

This deserves a comment, even if it's a bit repetitive.

// Cache of FS operations performed when building the preamble.
// When reusing a preamble, this cache can be consumed to save IO.

[ioeric]

• add comment for StatCache in PreambleData

[ioeric]

• Rebase

clangd/CMakeLists.txt

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

clangd/ClangdServer.cpp

void ClangdServer::codeComplete(PathRef File, Position Pos,
   auto Task = [PCHs, Pos, FS, CodeCompleteOpts,
                this](Path File, Callback<CodeCompleteResult> CB,
                      llvm::Expected<InputsAndPreamble> IP) {
     if (!IP)
       return CB(IP.takeError());
     if (isCancelled())
       return CB(llvm::make_error<CancelledError>());
 
-    auto PreambleData = IP->Preamble;
-
     llvm::Optional<SpeculativeFuzzyFind> SpecFuzzyFind;
     if (CodeCompleteOpts.Index && CodeCompleteOpts.SpeculativeIndexRequest) {
       SpecFuzzyFind.emplace();
       {
         std::lock_guard<std::mutex> Lock(CachedCompletionFuzzyFindRequestMutex);
         SpecFuzzyFind->CachedReq = CachedCompletionFuzzyFindRequestByFile[File];
       }
     }
 
     // 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->Includes : IncludeStructure(),
-        IP->Contents, Pos, FS, PCHs, CodeCompleteOpts,
-        SpecFuzzyFind ? SpecFuzzyFind.getPointer() : nullptr);
+        File, IP->Command, IP->Preamble, IP->Contents, Pos, FS, PCHs,
+        CodeCompleteOpts, SpecFuzzyFind ? SpecFuzzyFind.getPointer() : nullptr);
     {
       clang::clangd::trace::Span Tracer("Completion results callback");
       CB(std::move(Result));
     }
     if (SpecFuzzyFind && SpecFuzzyFind->NewReq.hasValue()) {
       std::lock_guard<std::mutex> Lock(CachedCompletionFuzzyFindRequestMutex);
       CachedCompletionFuzzyFindRequestByFile[File] =
           SpecFuzzyFind->NewReq.getValue();
void ClangdServer::signatureHelp(PathRef File, Position Pos,
   auto FS = FSProvider.getFileSystem();
   auto *Index = this->Index;
   auto Action = [Pos, FS, PCHs, Index](Path File, Callback<SignatureHelp> CB,
                                        llvm::Expected<InputsAndPreamble> IP) {
     if (!IP)
       return CB(IP.takeError());
 
     auto PreambleData = IP->Preamble;
-    CB(clangd::signatureHelp(File, IP->Command,
-                             PreambleData ? &PreambleData->Preamble : nullptr,
-                             IP->Contents, Pos, FS, PCHs, Index));
+    CB(clangd::signatureHelp(File, IP->Command, PreambleData, IP->Contents, Pos,
+                             FS, PCHs, Index));
   };
 
   // Unlike code completion, we wait for an up-to-date preamble here.
   // Signature help is often triggered after code completion. If the code
   // completion inserted a header to make the symbol available, then using
   // the old preamble would yield useless results.
   WorkScheduler.runWithPreamble("SignatureHelp", File, TUScheduler::Consistent,
                                 Bind(Action, File.str(), std::move(CB)));

clangd/ClangdUnit.h

 //===--- ClangdUnit.h --------------------------------------------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_CLANGDUNIT_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_CLANGDUNIT_H
 
 #include "Diagnostics.h"
+#include "FS.h"
 #include "Function.h"
 #include "Headers.h"
 #include "Path.h"
 #include "Protocol.h"
 #include "clang/Frontend/FrontendAction.h"
 #include "clang/Frontend/PrecompiledPreamble.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Serialization/ASTBitCodes.h"

 struct CompileCommand;
 }
 
 namespace clangd {
 
 // Stores Preamble and associated data.
 struct PreambleData {
   PreambleData(PrecompiledPreamble Preamble, std::vector<Diag> Diags,
-               IncludeStructure Includes);
+               IncludeStructure Includes,
+               std::unique_ptr<PreambleFileStatusCache> StatCache);
 
   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.
   IncludeStructure Includes;
+  // Cache of FS operations performed when building the preamble.
+  // When reusing a preamble, this cache can be consumed to save IO.
+  std::unique_ptr<PreambleFileStatusCache> StatCache;
 };
 
 /// 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;
 };

clangd/ClangdUnit.cpp

 
 private:
   PathRef File;
   PreambleParsedCallback ParsedCallback;
   IncludeStructure Includes;
   SourceManager *SourceMgr = nullptr;
 };
 
 } // namespace
 
 void clangd::dumpAST(ParsedAST &AST, llvm::raw_ostream &OS) {
   AST.getASTContext().getTranslationUnitDecl()->dump(OS, true);
 }
 
 llvm::Optional<ParsedAST>
 ParsedAST::build(std::unique_ptr<clang::CompilerInvocation> CI,
                  std::shared_ptr<const PreambleData> Preamble,
                  std::unique_ptr<llvm::MemoryBuffer> Buffer,
                  std::shared_ptr<PCHContainerOperations> PCHs,
                  IntrusiveRefCntPtr<vfs::FileSystem> VFS) {
   assert(CI);
   // Command-line parsing sets DisableFree to true by default, but we don't want
   // to leak memory in clangd.
   CI->getFrontendOpts().DisableFree = false;
   const PrecompiledPreamble *PreamblePCH =
       Preamble ? &Preamble->Preamble : nullptr;
 
   StoreDiags ASTDiags;
   auto Clang =
       prepareCompilerInstance(std::move(CI), PreamblePCH, std::move(Buffer),
                               std::move(PCHs), std::move(VFS), ASTDiags);
   if (!Clang)
     return llvm::None;
 
   // Recover resources if we crash before exiting this method.
   llvm::CrashRecoveryContextCleanupRegistrar<CompilerInstance> CICleanup(
       Clang.get());
 
   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 {0}",
         MainInput.getFile());
     return llvm::None;
   }
 
   // Copy over the includes from the preamble, then combine with the
   // non-preamble includes below.
   auto Includes = Preamble ? Preamble->Includes : IncludeStructure{};
   Clang->getPreprocessor().addPPCallbacks(
       collectIncludeStructureCallback(Clang->getSourceManager(), &Includes));
 
   if (!Action->Execute())
     log("Execute() failed when building AST for {0}", 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.
std::size_t ParsedAST::getUsedBytes() const {
   return Total;
 }
 
 const IncludeStructure &ParsedAST::getIncludeStructure() const {
   return Includes;
 }
 
 PreambleData::PreambleData(PrecompiledPreamble Preamble,
-                           std::vector<Diag> Diags, IncludeStructure Includes)
+                           std::vector<Diag> Diags, IncludeStructure Includes,
+                           std::unique_ptr<PreambleFileStatusCache> StatCache)
     : Preamble(std::move(Preamble)), Diags(std::move(Diags)),
-      Includes(std::move(Includes)) {}
+      Includes(std::move(Includes)), StatCache(std::move(StatCache)) {}
 
 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, IncludeStructure Includes)
     : Preamble(std::move(Preamble)), Clang(std::move(Clang)),
       Action(std::move(Action)), Diags(std::move(Diags)),
       LocalTopLevelDecls(std::move(LocalTopLevelDecls)),
       Includes(std::move(Includes)) {
   assert(this->Clang);
   assert(this->Action);
 }
if (Inputs.FS->setCurrentWorkingDirectory(Inputs.CompileCommand.Directory)) {
     // dirs.
   }
 
   // FIXME(ibiryukov): store diagnostics from CommandLine when we start
   // reporting them.
   IgnoreDiagnostics IgnoreDiagnostics;
   IntrusiveRefCntPtr<DiagnosticsEngine> CommandLineDiagsEngine =
       CompilerInstance::createDiagnostics(new DiagnosticOptions,
                                           &IgnoreDiagnostics, false);
   std::unique_ptr<CompilerInvocation> CI = createInvocationFromCommandLine(
       ArgStrs, CommandLineDiagsEngine, Inputs.FS);
   if (!CI)
     return nullptr;
   // createInvocationFromCommandLine sets DisableFree.
   CI->getFrontendOpts().DisableFree = false;
   CI->getLangOpts()->CommentOpts.ParseAllComments = true;
   return CI;
 }
std::shared_ptr<const PreambleData> clangd::buildPreamble(
   CI.getPreprocessorOpts().WriteCommentListToPCH = false;
 
   CppFilePreambleCallbacks SerializedDeclsCollector(FileName, PreambleCallback);
   if (Inputs.FS->setCurrentWorkingDirectory(Inputs.CompileCommand.Directory)) {
     log("Couldn't set working directory when building the preamble.");
     // We proceed anyway, our lit-tests rely on results for non-existing working
     // dirs.
   }
+
+  auto StatCache = llvm::make_unique<PreambleFileStatusCache>();
   auto BuiltPreamble = PrecompiledPreamble::Build(
-      CI, ContentsBuffer.get(), Bounds, *PreambleDiagsEngine, Inputs.FS, PCHs,
-      StoreInMemory, SerializedDeclsCollector);
+      CI, ContentsBuffer.get(), Bounds, *PreambleDiagsEngine,
+      StatCache->getProducingFS(Inputs.FS), PCHs, StoreInMemory,
+      SerializedDeclsCollector);
 
   // When building the AST for the main file, we do want the function
   // bodies.
   CI.getFrontendOpts().SkipFunctionBodies = false;
 
   if (BuiltPreamble) {
     vlog("Built preamble of size {0} for file {1}", BuiltPreamble->getSize(),
          FileName);
     return std::make_shared<PreambleData>(
         std::move(*BuiltPreamble), PreambleDiagnostics.take(),
-        SerializedDeclsCollector.takeIncludes());
+        SerializedDeclsCollector.takeIncludes(), std::move(StatCache));
   } else {
     elog("Could not build a preamble for file {0}", FileName);
     return nullptr;
   }
 }
 
 llvm::Optional<ParsedAST> clangd::buildAST(
     PathRef FileName, std::unique_ptr<CompilerInvocation> Invocation,
     const ParseInputs &Inputs, std::shared_ptr<const PreambleData> Preamble,
     std::shared_ptr<PCHContainerOperations> PCHs) {
   trace::Span Tracer("BuildAST");
   SPAN_ATTACH(Tracer, "File", FileName);
 
-  if (Inputs.FS->setCurrentWorkingDirectory(Inputs.CompileCommand.Directory)) {
+  auto VFS = Inputs.FS;
+  if (Preamble && Preamble->StatCache)
+    VFS = Preamble->StatCache->getConsumingFS(std::move(VFS));
+  if (VFS->setCurrentWorkingDirectory(Inputs.CompileCommand.Directory)) {
     log("Couldn't set working directory when building the preamble.");
     // We proceed anyway, our lit-tests rely on results for non-existing working
     // dirs.
   }
 
-  return ParsedAST::build(
-      llvm::make_unique<CompilerInvocation>(*Invocation), Preamble,
-      llvm::MemoryBuffer::getMemBufferCopy(Inputs.Contents), PCHs, Inputs.FS);
+  return ParsedAST::build(llvm::make_unique<CompilerInvocation>(*Invocation),
+                          Preamble,
+                          llvm::MemoryBuffer::getMemBufferCopy(Inputs.Contents),
+                          PCHs, std::move(VFS));
 }
 
 SourceLocation clangd::getBeginningOfIdentifier(ParsedAST &Unit,
                                                 const Position &Pos,
                                                 const FileID FID) {
   const ASTContext &AST = Unit.getASTContext();
   const SourceManager &SourceMgr = AST.getSourceManager();
   auto Offset = positionToOffset(SourceMgr.getBufferData(FID), Pos);

clangd/CodeComplete.h

 // After "std::string S; S." we might suggest members of std::string.
 // Signature help describes the parameters of a function as you type them.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_CODECOMPLETE_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_CODECOMPLETE_H
 
+#include "ClangdUnit.h"
 #include "Headers.h"
 #include "Logger.h"
 #include "Path.h"
 #include "Protocol.h"
 #include "index/Index.h"
 #include "clang/Frontend/PrecompiledPreamble.h"
 #include "clang/Sema/CodeCompleteConsumer.h"
 #include "clang/Sema/CodeCompleteOptions.h"
struct CodeCompleteOptions {
 
   /// Include completions that require small corrections, e.g. change '.' to
   /// '->' on member access etc.
   bool IncludeFixIts = false;
 
   /// Whether to generate snippets for function arguments on code-completion.
   /// Needs snippets to be enabled as well.
   bool EnableFunctionArgSnippets = true;
+
+  /// Whether to include index symbols that are not defined in the scopes
+  /// visible from the code completion point. This applies in contexts without
+  /// explicit scope qualifiers.
+  ///
+  /// Such completions can insert scope qualifiers.
+  bool AllScopes = false;
 };
 
 // Semi-structured representation of a code-complete suggestion for our C++ API.
 // We don't use the LSP structures here (unlike most features) as we want
 // to expose more data to allow for more precise testing and evaluation.
 struct CodeCompletion {
   // The unqualified name of the symbol or other completion item.
   std::string Name;

 /// Get code completions at a specified \p Pos in \p FileName.
 /// If \p SpecFuzzyFind is set, a speculative and asynchronous fuzzy find index
 /// request (based on cached request) will be run before parsing sema. In case
 /// the speculative result is used by code completion (e.g. speculation failed),
 /// the speculative result is not consumed, and `SpecFuzzyFind` is only
 /// destroyed when the async request finishes.
 CodeCompleteResult codeComplete(PathRef FileName,
                                 const tooling::CompileCommand &Command,
-                                PrecompiledPreamble const *Preamble,
-                                const IncludeStructure &PreambleInclusions,
+                                const PreambleData *Preamble,
                                 StringRef Contents, Position Pos,
                                 IntrusiveRefCntPtr<vfs::FileSystem> VFS,
                                 std::shared_ptr<PCHContainerOperations> PCHs,
                                 CodeCompleteOptions Opts,
                                 SpeculativeFuzzyFind *SpecFuzzyFind = nullptr);
 
 /// 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,
+                            const PreambleData *Preamble, StringRef Contents,
+                            Position Pos,
                             IntrusiveRefCntPtr<vfs::FileSystem> VFS,
                             std::shared_ptr<PCHContainerOperations> PCHs,
                             const SymbolIndex *Index);
 
 // For index-based completion, we only consider:
 //   * symbols in namespaces or translation unit scopes (e.g. no class
 //     members, no locals)
 //   * enum constants in unscoped enum decl (e.g. "red" in "enum {red};")

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 "AST.h"
+#include "ClangdUnit.h"
 #include "CodeCompletionStrings.h"
 #include "Compiler.h"
 #include "Diagnostics.h"
 #include "FileDistance.h"
 #include "FuzzyMatch.h"
 #include "Headers.h"
 #include "Logger.h"
 #include "Quality.h"
 #include "SourceCode.h"
 #include "TUScheduler.h"
 #include "Trace.h"
 #include "URI.h"
 #include "index/Index.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
 #include "clang/Basic/LangOptions.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Format/Format.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Frontend/FrontendActions.h"
 #include "clang/Index/USRGeneration.h"
 #include "clang/Lex/PreprocessorOptions.h"
 #include "clang/Sema/CodeCompleteConsumer.h"
 #include "clang/Sema/Sema.h"
 #include "clang/Tooling/Core/Replacement.h"
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/ScopedPrinter.h"
 #include <algorithm>
 #include <iterator>

 // the candidate bundle is going to be returned.
 //
 // Many fields are the same for all candidates in a bundle (e.g. name), and are
 // computed from the first candidate, in the constructor.
 // Others vary per candidate, so add() must be called for remaining candidates.
 struct CodeCompletionBuilder {
   CodeCompletionBuilder(ASTContext &ASTCtx, const CompletionCandidate &C,
                         CodeCompletionString *SemaCCS,
+                        llvm::ArrayRef<std::string> QueryScopes,
                         const IncludeInserter &Includes, StringRef FileName,
                         CodeCompletionContext::Kind ContextKind,
                         const CodeCompleteOptions &Opts)
       : ASTCtx(ASTCtx), ExtractDocumentation(Opts.IncludeComments),
         EnableFunctionArgSnippets(Opts.EnableFunctionArgSnippets) {
     add(C, SemaCCS);
     if (C.SemaResult) {
       Completion.Origin |= SymbolOrigin::AST;
CodeCompletionBuilder(ASTContext &ASTCtx, const CompletionCandidate &C,
     if (C.IndexResult) {
       Completion.Origin |= C.IndexResult->Origin;
       if (Completion.Scope.empty())
         Completion.Scope = C.IndexResult->Scope;
       if (Completion.Kind == CompletionItemKind::Missing)
         Completion.Kind = toCompletionItemKind(C.IndexResult->SymInfo.Kind);
       if (Completion.Name.empty())
         Completion.Name = C.IndexResult->Name;
+      // If the completion was visible to Sema, no qualifier is needed. This
+      // avoids unneeded qualifiers in cases like with `using ns::X`.
+      if (Completion.RequiredQualifier.empty() && !C.SemaResult) {
+        StringRef ShortestQualifier = C.IndexResult->Scope;
+        for (StringRef Scope : QueryScopes) {
+          StringRef Qualifier = C.IndexResult->Scope;
+          if (Qualifier.consume_front(Scope) &&
+              Qualifier.size() < ShortestQualifier.size())
+            ShortestQualifier = Qualifier;
+        }
+        Completion.RequiredQualifier = ShortestQualifier;
+      }
       Completion.Deprecated |= (C.IndexResult->Flags & Symbol::Deprecated);
     }
 
     // Turn absolute path into a literal string that can be #included.
     auto Inserted =
         [&](StringRef Header) -> Expected<std::pair<std::string, bool>> {
       auto ResolvedDeclaring =
           toHeaderFile(C.IndexResult->CanonicalDeclaration.FileURI, FileName);
for (llvm::StringRef AS : AccessibleScopes) {
       Results.push_back(AS);
       if (UnresolvedQualifier)
         Results.back() += *UnresolvedQualifier;
     }
     return Results;
   }
 };
 
-// Get all scopes that will be queried in indexes.
-std::vector<std::string> getQueryScopes(CodeCompletionContext &CCContext,
-                                        const SourceManager &SM) {
+// Get all scopes that will be queried in indexes and whether symbols from
+// any scope is allowed.
+std::pair<std::vector<std::string>, bool>
+getQueryScopes(CodeCompletionContext &CCContext, const SourceManager &SM,
+               const CodeCompleteOptions &Opts) {
   auto GetAllAccessibleScopes = [](CodeCompletionContext &CCContext) {
     SpecifiedScope Info;
     for (auto *Context : CCContext.getVisitedContexts()) {
       if (isa<TranslationUnitDecl>(Context))
         Info.AccessibleScopes.push_back(""); // global namespace
       else if (const auto *NS = dyn_cast<NamespaceDecl>(Context))
         Info.AccessibleScopes.push_back(NS->getQualifiedNameAsString() + "::");
     }
     return Info;
   };
 
   auto SS = CCContext.getCXXScopeSpecifier();
 
   // Unqualified completion (e.g. "vec^").
   if (!SS) {
     // FIXME: Once we can insert namespace qualifiers and use the in-scope
     //        namespaces for scoring, search in all namespaces.
     // FIXME: Capture scopes and use for scoring, for example,
     //        "using namespace std; namespace foo {v^}" =>
     //        foo::value > std::vector > boost::variant
-    return GetAllAccessibleScopes(CCContext).scopesForIndexQuery();
+    auto Scopes = GetAllAccessibleScopes(CCContext).scopesForIndexQuery();
+    // Allow AllScopes completion only for there is no explicit scope qualifier.
+    return {Scopes, Opts.AllScopes};
   }
 
   // Qualified completion ("std::vec^"), we have two cases depending on whether
   // the qualifier can be resolved by Sema.
   if ((*SS)->isValid()) { // Resolved qualifier.
-    return GetAllAccessibleScopes(CCContext).scopesForIndexQuery();
+    return {GetAllAccessibleScopes(CCContext).scopesForIndexQuery(), false};
   }
 
   // Unresolved qualifier.
   // FIXME: When Sema can resolve part of a scope chain (e.g.
   // "known::unknown::id"), we should expand the known part ("known::") rather
   // than treating the whole thing as unknown.
   SpecifiedScope Info;
   Info.AccessibleScopes.push_back(""); // global namespace
 
   Info.UnresolvedQualifier =
       Lexer::getSourceText(CharSourceRange::getCharRange((*SS)->getRange()), SM,
                            clang::LangOptions())
           .ltrim("::");
   // Sema excludes the trailing "::".
   if (!Info.UnresolvedQualifier->empty())
     *Info.UnresolvedQualifier += "::";
 
-  return Info.scopesForIndexQuery();
+  return {Info.scopesForIndexQuery(), false};
 }
 
 // Should we perform index-based completion in a context of the specified kind?
 // FIXME: consider allowing completion, but restricting the result types.
 bool contextAllowsIndex(enum CodeCompletionContext::Kind K) {
   switch (K) {
   case CodeCompletionContext::CCC_TopLevel:
   case CodeCompletionContext::CCC_ObjCInterface:
private:
   std::shared_ptr<clang::GlobalCodeCompletionAllocator> Allocator;
   CodeCompletionTUInfo CCTUInfo;
   const SymbolIndex *Index;
 }; // SignatureHelpCollector
 
 struct SemaCompleteInput {
   PathRef FileName;
   const tooling::CompileCommand &Command;
-  PrecompiledPreamble const *Preamble;
+  const PreambleData *Preamble;
   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 updated based on the compiler invocation.
 bool semaCodeComplete(std::unique_ptr<CodeCompleteConsumer> Consumer,
                       const clang::CodeCompleteOptions &Options,
                       const SemaCompleteInput &Input,
                       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
     // working dirs.
   }
 
+  IntrusiveRefCntPtr<vfs::FileSystem> VFS = Input.VFS;
+  if (Input.Preamble && Input.Preamble->StatCache)
+    VFS = Input.Preamble->StatCache->getConsumingFS(std::move(VFS));
   IgnoreDiagnostics DummyDiagsConsumer;
   auto CI = createInvocationFromCommandLine(
       ArgStrs,
       CompilerInstance::createDiagnostics(new DiagnosticOptions,
                                           &DummyDiagsConsumer, false),
-      Input.VFS);
+      VFS);
   if (!CI) {
     elog("Couldn't create CompilerInvocation");
     return false;
   }
   auto &FrontendOpts = CI->getFrontendOpts();
   FrontendOpts.DisableFree = false;
   FrontendOpts.SkipFunctionBodies = true;
   CI->getLangOpts()->CommentOpts.ParseAllComments = true;
bool semaCodeComplete(std::unique_ptr<CodeCompleteConsumer> Consumer,
   // overriding the preamble will break sema completion. Fortunately we can just
   // skip all includes in this case; these completions are really simple.
   bool CompletingInPreamble =
       ComputePreambleBounds(*CI->getLangOpts(), ContentsBuffer.get(), 0).Size >
       *Offset;
   // NOTE: we must call BeginSourceFile after prepareCompilerInstance. Otherwise
   // the remapped buffers do not get freed.
   auto Clang = prepareCompilerInstance(
-      std::move(CI), CompletingInPreamble ? nullptr : Input.Preamble,
-      std::move(ContentsBuffer), std::move(Input.PCHs), std::move(Input.VFS),
+      std::move(CI),
+      (Input.Preamble && !CompletingInPreamble) ? &Input.Preamble->Preamble
+                                                : nullptr,
+      std::move(ContentsBuffer), std::move(Input.PCHs), std::move(VFS),
       DummyDiagsConsumer);
   Clang->getPreprocessorOpts().SingleFileParseMode = CompletingInPreamble;
   Clang->setCodeCompletionConsumer(Consumer.release());
 
   SyntaxOnlyAction Action;
   if (!Action.BeginSourceFile(*Clang, Clang->getFrontendOpts().Inputs[0])) {
     log("BeginSourceFile() failed when running codeComplete for {0}",
         Input.FileName);
class CodeCompleteFlow {
   IncludeStructure Includes; // Complete once the compiler runs.
   SpeculativeFuzzyFind *SpecFuzzyFind; // Can be nullptr.
   const CodeCompleteOptions &Opts;
 
   // Sema takes ownership of Recorder. Recorder is valid until Sema cleanup.
   CompletionRecorder *Recorder = nullptr;
   int NSema = 0, NIndex = 0, NBoth = 0; // Counters for logging.
   bool Incomplete = false; // Would more be available with a higher limit?
-  llvm::Optional<FuzzyMatcher> Filter;       // Initialized once Sema runs.
-  std::vector<std::string> QueryScopes;      // Initialized once Sema runs.
+  llvm::Optional<FuzzyMatcher> Filter;  // Initialized once Sema runs.
+  std::vector<std::string> QueryScopes; // Initialized once Sema runs.
+  // Whether to query symbols from any scope. Initialized once Sema runs.
+  bool AllScopes = false;
   // Include-insertion and proximity scoring rely on the include structure.
   // This is available after Sema has run.
   llvm::Optional<IncludeInserter> Inserter;  // Available during runWithSema.
   llvm::Optional<URIDistance> FileProximity; // Initialized once Sema runs.
   /// Speculative request based on the cached request and the filter text before
   /// the cursor.
   /// Initialized right before sema run. This is only set if `SpecFuzzyFind` is
   /// set and contains a cached request.
auto RecorderOwner = llvm::make_unique<CompletionRecorder>(Opts, [&]() {
           Source.MaxUpTraversals = 1;
       }
       FileProximity.emplace(ProxSources, ProxOpts);
 
       Output = runWithSema();
       Inserter.reset(); // Make sure this doesn't out-live Clang.
       SPAN_ATTACH(Tracer, "sema_completion_kind",
                   getCompletionKindString(Recorder->CCContext.getKind()));
-      log("Code complete: sema context {0}, query scopes [{1}]",
+      log("Code complete: sema context {0}, query scopes [{1}] (AnyScope={2})",
           getCompletionKindString(Recorder->CCContext.getKind()),
-          llvm::join(QueryScopes.begin(), QueryScopes.end(), ","));
+          llvm::join(QueryScopes.begin(), QueryScopes.end(), ","), AllScopes);
     });
 
     Recorder = RecorderOwner.get();
 
     semaCodeComplete(std::move(RecorderOwner), Opts.getClangCompleteOpts(),
                      SemaCCInput, &Includes);
 
     SPAN_ATTACH(Tracer, "sema_results", NSema);
CodeCompleteResult runWithSema() {
     } else {
       const auto &Pos = sourceLocToPosition(
           Recorder->CCSema->getSourceManager(),
           Recorder->CCSema->getPreprocessor().getCodeCompletionLoc());
       TextEditRange.start = TextEditRange.end = Pos;
     }
     Filter = FuzzyMatcher(
         Recorder->CCSema->getPreprocessor().getCodeCompletionFilter());
-    QueryScopes = getQueryScopes(Recorder->CCContext,
-                                 Recorder->CCSema->getSourceManager());
+    std::tie(QueryScopes, AllScopes) = getQueryScopes(
+        Recorder->CCContext, Recorder->CCSema->getSourceManager(), Opts);
     // Sema provides the needed context to query the index.
     // FIXME: in addition to querying for extra/overlapping symbols, we should
     //        explicitly request symbols corresponding to Sema results.
     //        We can use their signals even if the index can't suggest them.
     // We must copy index results to preserve them, but there are at most Limit.
     auto IndexResults = (Opts.Index && allowIndex(Recorder->CCContext))
                             ? queryIndex()
                             : SymbolSlab();
SymbolSlab queryIndex() {
 
     // Build the query.
     FuzzyFindRequest Req;
     if (Opts.Limit)
       Req.Limit = Opts.Limit;
     Req.Query = Filter->pattern();
     Req.RestrictForCodeCompletion = true;
     Req.Scopes = QueryScopes;
+    Req.AnyScope = AllScopes;
     // FIXME: we should send multiple weighted paths here.
     Req.ProximityPaths.push_back(FileName);
     vlog("Code complete: fuzzyFind({0:2})", toJSON(Req));
 
     if (SpecFuzzyFind)
       SpecFuzzyFind->NewReq = Req;
     if (SpecFuzzyFind && SpecFuzzyFind->Result.valid() && (*SpecReq == Req)) {
       vlog("Code complete: speculative fuzzy request matches the actual index "
private:
   // Scores a candidate and adds it to the TopN structure.
   void addCandidate(TopN<ScoredBundle, ScoredBundleGreater> &Candidates,
                     CompletionCandidate::Bundle Bundle) {
     SymbolQualitySignals Quality;
     SymbolRelevanceSignals Relevance;
     Relevance.Context = Recorder->CCContext.getKind();
     Relevance.Query = SymbolRelevanceSignals::CodeComplete;
     Relevance.FileProximityMatch = FileProximity.getPointer();
+    // FIXME: incorparate scope proximity into relevance score.
+
     auto &First = Bundle.front();
     if (auto FuzzyScore = fuzzyScore(First))
       Relevance.NameMatch = *FuzzyScore;
     else
       return;
     SymbolOrigin Origin = SymbolOrigin::Unknown;
     bool FromIndex = false;
     for (const auto &Candidate : Bundle) {
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,
-                        *Inserter, FileName, Recorder->CCContext.getKind(),
-                        Opts);
+                        QueryScopes, *Inserter, FileName,
+                        Recorder->CCContext.getKind(), Opts);
       else
         Builder->add(Item, SemaCCS);
     }
     return Builder->build();
   }
 };
 
 llvm::Expected<llvm::StringRef>
speculateCompletionFilter(llvm::StringRef Content, Position Pos) {
   }
   if (Len > 0)
     St++; // Shift to the first valid character.
   return Content.substr(St, Len);
 }
 
 CodeCompleteResult
 codeComplete(PathRef FileName, const tooling::CompileCommand &Command,
-             PrecompiledPreamble const *Preamble,
-             const IncludeStructure &PreambleInclusions, StringRef Contents,
-             Position Pos, IntrusiveRefCntPtr<vfs::FileSystem> VFS,
+             const PreambleData *Preamble, StringRef Contents, Position Pos,
+             IntrusiveRefCntPtr<vfs::FileSystem> VFS,
              std::shared_ptr<PCHContainerOperations> PCHs,
              CodeCompleteOptions Opts, SpeculativeFuzzyFind *SpecFuzzyFind) {
-  return CodeCompleteFlow(FileName, PreambleInclusions, SpecFuzzyFind, Opts)
+  return CodeCompleteFlow(FileName,
+                          Preamble ? Preamble->Includes : IncludeStructure(),
+                          SpecFuzzyFind, Opts)
       .run({FileName, Command, Preamble, Contents, Pos, VFS, PCHs});
 }
 
 SignatureHelp signatureHelp(PathRef FileName,
                             const tooling::CompileCommand &Command,
-                            PrecompiledPreamble const *Preamble,
-                            StringRef Contents, Position Pos,
+                            const PreambleData *Preamble, StringRef Contents,
+                            Position Pos,
                             IntrusiveRefCntPtr<vfs::FileSystem> VFS,
                             std::shared_ptr<PCHContainerOperations> PCHs,
                             const SymbolIndex *Index) {
   SignatureHelp Result;
   clang::CodeCompleteOptions Options;
   Options.IncludeGlobals = false;
   Options.IncludeMacros = false;
   Options.IncludeCodePatterns = false;
   Options.IncludeBriefComments = false;
   IncludeStructure PreambleInclusions; // Unused for signatureHelp
   semaCodeComplete(
       llvm::make_unique<SignatureHelpCollector>(Options, Index, Result),
       Options,
       {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,

clangd/FS.h

+//===--- FS.h - File system related utils ------------------------*- C++-*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_FS_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_FS_H
+
+#include "clang/Basic/VirtualFileSystem.h"
+#include "llvm/ADT/Optional.h"
+
+namespace clang {
+namespace clangd {
+
+/// Records status information for files open()ed or stat()ed during preamble
+/// build, so we can avoid stat()s on the underlying FS when reusing the
+/// preamble. For example, code completion can re-stat files when getting FileID
+/// for source locations stored in preamble (e.g. checking whether a location is
+/// in the main file).
+///
+/// The cache is keyed by absolute path of file name in cached status, as this
+/// is what preamble stores.
+///
+/// The cache is not thread-safe when updates happen, so the use pattern should
+/// be:
+///   - One FS writes to the cache from one thread (or several but strictly
+///   sequenced), e.g. when building preamble.
+///   - Sequence point (no writes after this point, no reads before).
+///   - Several FSs can read from the cache, e.g. code completions.
+///
+/// Note that the cache is only valid when reusing preamble.
+class PreambleFileStatusCache {
+public:
+  void update(const vfs::FileSystem &FS, vfs::Status S);
+  /// \p Path is a path stored in preamble.
+  llvm::Optional<vfs::Status> lookup(llvm::StringRef Path) const;
+
+  /// Returns a VFS that collects file status.
+  /// Only cache stats for files that exist because
+  ///   1) we only care about existing files when reusing preamble, unlike
+  ///   building preamble.
+  ///   2) we use the file name in the Status as the cache key.
+  ///
+  /// Note that the returned VFS should not outlive the cache.
+  IntrusiveRefCntPtr<vfs::FileSystem>
+  getProducingFS(IntrusiveRefCntPtr<vfs::FileSystem> FS);
+
+  /// Returns a VFS that uses the cache collected.
+  ///
+  /// Note that the returned VFS should not outlive the cache.
+  IntrusiveRefCntPtr<vfs::FileSystem>
+  getConsumingFS(IntrusiveRefCntPtr<vfs::FileSystem> FS) const;
+
+private:
+  llvm::StringMap<vfs::Status> StatCache;
+};
+
+} // namespace clangd
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_FS_H

clangd/FS.cpp

+//===--- FS.cpp - File system related utils ----------------------*- C++-*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "FS.h"
+#include "clang/Basic/VirtualFileSystem.h"
+#include "llvm/ADT/None.h"
+
+namespace clang {
+namespace clangd {
+
+void PreambleFileStatusCache::update(const vfs::FileSystem &FS, vfs::Status S) {
+  SmallString<32> PathStore(S.getName());
+  if (auto Err = FS.makeAbsolute(PathStore))
+    return;
+  // Stores the latest status in cache as it can change in a preamble build.
+  StatCache.insert({PathStore, std::move(S)});
+}
+
+llvm::Optional<vfs::Status>
+PreambleFileStatusCache::lookup(llvm::StringRef File) const {
+  auto I = StatCache.find(File);
+  if (I != StatCache.end())
+    return I->getValue();
+  return llvm::None;
+}
+
+IntrusiveRefCntPtr<vfs::FileSystem> PreambleFileStatusCache::getProducingFS(
+    IntrusiveRefCntPtr<vfs::FileSystem> FS) {
+  // This invalidates old status in cache if files are re-`open()`ed or
+  // re-`stat()`ed in case file status has changed during preamble build.
+  class CollectFS : public vfs::ProxyFileSystem {
+  public:
+    CollectFS(IntrusiveRefCntPtr<vfs::FileSystem> FS,
+              PreambleFileStatusCache &StatCache)
+        : ProxyFileSystem(std::move(FS)), StatCache(StatCache) {}
+
+    llvm::ErrorOr<std::unique_ptr<vfs::File>>
+    openFileForRead(const Twine &Path) override {
+      auto File = getUnderlyingFS().openFileForRead(Path);
+      if (!File || !*File)
+        return File;
+      // Eagerly stat opened file, as the followup `status` call on the file
+      // doesn't necessarily go through this FS. This puts some extra work on
+      // preamble build, but it should be worth it as preamble can be reused
+      // many times (e.g. code completion) and the repeated status call is
+      // likely to be cached in the underlying file system anyway.
+      if (auto S = File->get()->status())
+        StatCache.update(getUnderlyingFS(), std::move(*S));
+      return File;
+    }
+
+    llvm::ErrorOr<vfs::Status> status(const Twine &Path) override {
+      auto S = getUnderlyingFS().status(Path);
+      if (S)
+        StatCache.update(getUnderlyingFS(), *S);
+      return S;
+    }
+
+  private:
+    PreambleFileStatusCache &StatCache;
+  };
+  return IntrusiveRefCntPtr<CollectFS>(new CollectFS(std::move(FS), *this));
+}
+
+IntrusiveRefCntPtr<vfs::FileSystem> PreambleFileStatusCache::getConsumingFS(
+    IntrusiveRefCntPtr<vfs::FileSystem> FS) const {
+  class CacheVFS : public vfs::ProxyFileSystem {
+  public:
+    CacheVFS(IntrusiveRefCntPtr<vfs::FileSystem> FS,
+             const PreambleFileStatusCache &StatCache)
+        : ProxyFileSystem(std::move(FS)), StatCache(StatCache) {}
+
+    llvm::ErrorOr<vfs::Status> status(const Twine &Path) override {
+      if (auto S = StatCache.lookup(Path.str()))
+        return *S;
+      return getUnderlyingFS().status(Path);
+    }
+
+  private:
+    const PreambleFileStatusCache &StatCache;
+  };
+  return IntrusiveRefCntPtr<CacheVFS>(new CacheVFS(std::move(FS), *this));
+}
+
+} // namespace clangd
+} // namespace clang

clangd/index/Index.h

struct FuzzyFindRequest {
   /// un-qualified identifiers and should not contain qualifiers like "::".
   std::string Query;
   /// \brief If this is non-empty, symbols must be in at least one of the scopes
   /// (e.g. namespaces) excluding nested scopes. For example, if a scope "xyz::"
   /// is provided, the matched symbols must be defined in namespace xyz but not
   /// namespace xyz::abc.
   ///
   /// The global scope is "", a top level scope is "foo::", etc.
+  /// FIXME: drop the special case for empty list, which is the same as
+  /// `AnyScope = true`.
+  /// FIXME: support scope proximity.
   std::vector<std::string> Scopes;
+  /// If set to true, allow symbols from any scope. Scopes explicitly listed
+  /// above will be ranked higher.
+  bool AnyScope = false;
   /// \brief The number of top candidates to return. The index may choose to
   /// return more than this, e.g. if it doesn't know which candidates are best.
   llvm::Optional<uint32_t> Limit;
   /// If set to true, only symbols for completion support will be considered.
   bool RestrictForCodeCompletion = false;
   /// Contextually relevant files (e.g. the file we're code-completing in).
   /// Paths should be absolute.
   std::vector<std::string> ProximityPaths;

clangd/index/MemIndex.cpp

 //===--- MemIndex.cpp - Dynamic in-memory symbol index. ----------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===-------------------------------------------------------------------===//
 
 #include "MemIndex.h"
 #include "FuzzyMatch.h"
 #include "Logger.h"
 #include "Quality.h"
+#include "Trace.h"
 
 namespace clang {
 namespace clangd {
 
 std::unique_ptr<SymbolIndex> MemIndex::build(SymbolSlab Slab, RefSlab Refs) {
   // Store Slab size before it is moved.
   const auto BackingDataSize = Slab.bytes() + Refs.bytes();
   auto Data = std::make_pair(std::move(Slab), std::move(Refs));
   return llvm::make_unique<MemIndex>(Data.first, Data.second, std::move(Data),
                                      BackingDataSize);
 }
 
 bool MemIndex::fuzzyFind(
     const FuzzyFindRequest &Req,
     llvm::function_ref<void(const Symbol &)> Callback) const {
   assert(!StringRef(Req.Query).contains("::") &&
          "There must be no :: in query.");
+  trace::Span Tracer("MemIndex fuzzyFind");
 
   TopN<std::pair<float, const Symbol *>> Top(
       Req.Limit ? *Req.Limit : std::numeric_limits<size_t>::max());
   FuzzyMatcher Filter(Req.Query);
   bool More = false;
   for (const auto Pair : Index) {
     const Symbol *Sym = Pair.second;
 
     // Exact match against all possible scopes.
-    if (!Req.Scopes.empty() && !llvm::is_contained(Req.Scopes, Sym->Scope))
+    if (!Req.AnyScope && !Req.Scopes.empty() &&
+        !llvm::is_contained(Req.Scopes, Sym->Scope))
       continue;
     if (Req.RestrictForCodeCompletion &&
         !(Sym->Flags & Symbol::IndexedForCodeCompletion))
       continue;
 
     if (auto Score = Filter.match(Sym->Name))
       if (Top.push({*Score * quality(*Sym), Sym}))
         More = true; // An element with smallest score was discarded.
   }
-  for (const auto &Item : std::move(Top).items())
+  auto Results = std::move(Top).items();
+  SPAN_ATTACH(Tracer, "results", static_cast<int>(Results.size()));
+  for (const auto &Item : Results)
     Callback(*Item.second);
   return More;
 }
 
 void MemIndex::lookup(const LookupRequest &Req,
                       llvm::function_ref<void(const Symbol &)> Callback) const {
+  trace::Span Tracer("MemIndex lookup");
   for (const auto &ID : Req.IDs) {
     auto I = Index.find(ID);
     if (I != Index.end())
       Callback(*I->second);
   }
 }
 
 void MemIndex::refs(const RefsRequest &Req,
                     llvm::function_ref<void(const Ref &)> Callback) const {
+  trace::Span Tracer("MemIndex refs");
   for (const auto &ReqID : Req.IDs) {
     auto SymRefs = Refs.find(ReqID);
     if (SymRefs == Refs.end())
       continue;
     for (const auto &O : SymRefs->second)
       if (static_cast<int>(Req.Filter & O.Kind))
         Callback(O);
   }
 }
 
 size_t MemIndex::estimateMemoryUsage() const {
   return Index.getMemorySize() + Refs.getMemorySize() + BackingDataSize;
 }
 
 } // namespace clangd
 } // namespace clang

clangd/index/Merge.cpp

 //===--- Merge.cpp -----------------------------------------------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Merge.h"
 #include "Logger.h"
+#include "Trace.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/Support/raw_ostream.h"
 #include <set>
 
 namespace clang {
 namespace clangd {
 namespace {
public:
    bool fuzzyFind(const FuzzyFindRequest &Req,
                   function_ref<void(const Symbol &)> Callback) const override {
      // We can't step through both sources in parallel. So:
      //  1) query all dynamic symbols, slurping results into a slab
      //  2) query the static symbols, for each one:
      //    a) if it's not in the dynamic slab, yield it directly
      //    b) if it's in the dynamic slab, merge it and yield the result
      //  3) now yield all the dynamic symbols we haven't processed.
+     trace::Span Tracer("MergedIndex fuzzyFind");
      bool More = false; // We'll be incomplete if either source was.
      SymbolSlab::Builder DynB;
-     More |= Dynamic->fuzzyFind(Req, [&](const Symbol &S) { DynB.insert(S); });
+     unsigned DynamicCount = 0;
+     unsigned StaticCount = 0;
+     unsigned MergedCount = 0;
+     More |= Dynamic->fuzzyFind(Req, [&](const Symbol &S) {
+       ++DynamicCount;
+       DynB.insert(S);
+     });
      SymbolSlab Dyn = std::move(DynB).build();
 
      DenseSet<SymbolID> SeenDynamicSymbols;
      More |= Static->fuzzyFind(Req, [&](const Symbol &S) {
        auto DynS = Dyn.find(S.ID);
+       ++StaticCount;
        if (DynS == Dyn.end())
          return Callback(S);
+       ++MergedCount;
        SeenDynamicSymbols.insert(S.ID);
        Callback(mergeSymbol(*DynS, S));
      });
+     SPAN_ATTACH(Tracer, "dynamic", DynamicCount);
+     SPAN_ATTACH(Tracer, "static", StaticCount);
+     SPAN_ATTACH(Tracer, "merged", MergedCount);
      for (const Symbol &S : Dyn)
        if (!SeenDynamicSymbols.count(S.ID))
          Callback(S);
      return More;
   }
 
   void
   lookup(const LookupRequest &Req,
          llvm::function_ref<void(const Symbol &)> Callback) const override {
+    trace::Span Tracer("MergedIndex lookup");
     SymbolSlab::Builder B;
 
     Dynamic->lookup(Req, [&](const Symbol &S) { B.insert(S); });
 
     auto RemainingIDs = Req.IDs;
     Static->lookup(Req, [&](const Symbol &S) {
       const Symbol *Sym = B.find(S.ID);
       RemainingIDs.erase(S.ID);
       if (!Sym)
         Callback(S);
       else
         Callback(mergeSymbol(*Sym, S));
     });
     for (const auto &ID : RemainingIDs)
       if (const Symbol *Sym = B.find(ID))
         Callback(*Sym);
   }
 
   void refs(const RefsRequest &Req,
             llvm::function_ref<void(const Ref &)> Callback) const override {
+    trace::Span Tracer("MergedIndex refs");
     // We don't want duplicated refs from the static/dynamic indexes,
     // and we can't reliably duplicate them because offsets may differ slightly.
     // We consider the dynamic index authoritative and report all its refs,
     // and only report static index refs from other files.
     //
     // FIXME: The heuristic fails if the dynamic index contains a file, but all
     // refs were removed (we will report stale ones from the static index).
     // Ultimately we should explicit check which index has the file instead.

clangd/index/dex/Dex.cpp

 //===--- Dex.cpp - Dex Symbol Index Implementation --------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Dex.h"
 #include "FileDistance.h"
 #include "FuzzyMatch.h"
 #include "Logger.h"
 #include "Quality.h"
+#include "Trace.h"
+#include "index/Index.h"
+#include "index/dex/Iterator.h"
 #include "llvm/ADT/StringSet.h"
 #include <algorithm>
 #include <queue>
 
 namespace clang {
 namespace clangd {
 namespace dex {
 

 
 /// Constructs iterators over tokens extracted from the query and exhausts it
 /// while applying Callback to each symbol in the order of decreasing quality
 /// of the matched symbols.
 bool Dex::fuzzyFind(const FuzzyFindRequest &Req,
                     llvm::function_ref<void(const Symbol &)> Callback) const {
   assert(!StringRef(Req.Query).contains("::") &&
          "There must be no :: in query.");
+  // FIXME: attach the query tree to the trace span.
+  trace::Span Tracer("Dex fuzzyFind");
   FuzzyMatcher Filter(Req.Query);
   bool More = false;
 
   std::vector<std::unique_ptr<Iterator>> TopLevelChildren;
   const auto TrigramTokens = generateIdentifierTrigrams(Req.Query);
 
   // Generate query trigrams and construct AND iterator over all query
   // trigrams.
   std::vector<std::unique_ptr<Iterator>> TrigramIterators;
   for (const auto &Trigram : TrigramTokens) {
     const auto It = InvertedIndex.find(Trigram);
     if (It != InvertedIndex.end())
       TrigramIterators.push_back(It->second.iterator());
   }
   if (!TrigramIterators.empty())
     TopLevelChildren.push_back(createAnd(move(TrigramIterators)));
 
   // Generate scope tokens for search query.
   std::vector<std::unique_ptr<Iterator>> ScopeIterators;
   for (const auto &Scope : Req.Scopes) {
     const auto It = InvertedIndex.find(Token(Token::Kind::Scope, Scope));
     if (It != InvertedIndex.end())
       ScopeIterators.push_back(It->second.iterator());
   }
+  if (Req.AnyScope)
+    ScopeIterators.push_back(createBoost(createTrue(Symbols.size()),
+                                         ScopeIterators.empty() ? 1.0 : 0.2));
+
   // Add OR iterator for scopes if there are any Scope Iterators.
   if (!ScopeIterators.empty())
     TopLevelChildren.push_back(createOr(move(ScopeIterators)));
 
   // Add proximity paths boosting.
   auto BoostingIterators = createFileProximityIterators(
       Req.ProximityPaths, URISchemes, InvertedIndex);
   // Boosting iterators do not actually filter symbols. In order to preserve
bool Dex::fuzzyFind(const FuzzyFindRequest &Req,
   // order of cumulative score.
   for (const auto &Item : std::move(Top).items())
     Callback(*Symbols[Item.first]);
   return More;
 }
 
 void Dex::lookup(const LookupRequest &Req,
                  llvm::function_ref<void(const Symbol &)> Callback) const {
+  trace::Span Tracer("Dex lookup");
   for (const auto &ID : Req.IDs) {
     auto I = LookupTable.find(ID);
     if (I != LookupTable.end())
       Callback(*I->second);
   }
 }
 
 void Dex::refs(const RefsRequest &Req,
                llvm::function_ref<void(const Ref &)> Callback) const {
+  trace::Span Tracer("Dex refs");
   log("refs is not implemented.");
 }
 
 size_t Dex::estimateMemoryUsage() const {
   size_t Bytes = Symbols.size() * sizeof(const Symbol *);
   Bytes += SymbolQuality.size() * sizeof(float);
   Bytes += LookupTable.getMemorySize();
   Bytes += InvertedIndex.getMemorySize();

clangd/tool/ClangdMain.cpp

 static llvm::cl::opt<bool> EnableIndex(
     "index",
     llvm::cl::desc(
         "Enable index-based features. By default, clangd maintains an index "
         "built from symbols in opened files. Global index support needs to "
         "enabled separatedly."),
     llvm::cl::init(true), llvm::cl::Hidden);
 
+static llvm::cl::opt<bool> AllScopesCompletion(
+    "all-scopes-completion",
+    llvm::cl::desc(
+        "If set to true, code completion will include index symbols that are "
+        "not defined in the scopes (e.g. "
+        "namespaces) visible from the code completion point. Such completions "
+        "can insert scope qualifiers."),
+    llvm::cl::init(false), llvm::cl::Hidden);
+
 static llvm::cl::opt<bool>
     ShowOrigins("debug-origin",
                 llvm::cl::desc("Show origins of completion items"),
                 llvm::cl::init(clangd::CodeCompleteOptions().ShowOrigins),
                 llvm::cl::Hidden);
 
 static llvm::cl::opt<bool> HeaderInsertionDecorators(
     "header-insertion-decorators",
int main(int argc, char *argv[]) {
   CCOpts.BundleOverloads = CompletionStyle != Detailed;
   CCOpts.ShowOrigins = ShowOrigins;
   if (!HeaderInsertionDecorators) {
     CCOpts.IncludeIndicator.Insert.clear();
     CCOpts.IncludeIndicator.NoInsert.clear();
   }
   CCOpts.SpeculativeIndexRequest = Opts.StaticIndex;
   CCOpts.EnableFunctionArgSnippets = EnableFunctionArgSnippets;
+  CCOpts.AllScopes = AllScopesCompletion;
 
   // Initialize and run ClangdLSPServer.
   ClangdLSPServer LSPServer(
       Out, CCOpts, CompileCommandsDirPath,
       /*ShouldUseInMemoryCDB=*/CompileArgsFrom == LSPCompileArgs, Opts);
   constexpr int NoShutdownRequestErrorCode = 1;
   llvm::set_thread_name("clangd.main");
   // Change stdin to binary to not lose \r\n on windows.
   llvm::sys::ChangeStdinToBinary();
   return LSPServer.run(stdin, InputStyle) ? 0 : NoShutdownRequestErrorCode;
 }

unittests/clangd/CMakeLists.txt

add_extra_unittest(ClangdTests
   CodeCompleteTests.cpp
   CodeCompletionStringsTests.cpp
   ContextTests.cpp
   DexTests.cpp
   DraftStoreTests.cpp
   FileDistanceTests.cpp
   FileIndexTests.cpp
   FindSymbolsTests.cpp
+  FSTests.cpp
   FuzzyMatchTests.cpp
   GlobalCompilationDatabaseTests.cpp
   HeadersTests.cpp
   IndexTests.cpp
   QualityTests.cpp
   RIFFTests.cpp
   SerializationTests.cpp
   SourceCodeTests.cpp

unittests/clangd/ClangdTests.cpp

TEST_F(ClangdVFSTest, ChangedHeaderFromISystem) {
   Completions = cantFail(runCodeComplete(Server, SourcePath, Code.point(),
                                          clangd::CodeCompleteOptions()))
                     .Completions;
   // We want to make sure we see the updated version.
   EXPECT_THAT(Completions, ElementsAre(Field(&CodeCompletion::Name, "bar"),
                                        Field(&CodeCompletion::Name, "baz")));
 }
 
+// Check that running code completion doesn't stat() a bunch of files from the
+// preamble again. (They should be using the preamble's stat-cache)
+TEST(ClangdTests, PreambleVFSStatCache) {
+  class ListenStatsFSProvider : public FileSystemProvider {
+  public:
+    ListenStatsFSProvider(llvm::StringMap<unsigned> &CountStats)
+        : CountStats(CountStats) {}
+
+    IntrusiveRefCntPtr<vfs::FileSystem> getFileSystem() override {
+      class ListenStatVFS : public vfs::ProxyFileSystem {
+      public:
+        ListenStatVFS(IntrusiveRefCntPtr<vfs::FileSystem> FS,
+                      llvm::StringMap<unsigned> &CountStats)
+            : ProxyFileSystem(std::move(FS)), CountStats(CountStats) {}
+
+        llvm::ErrorOr<std::unique_ptr<vfs::File>>
+        openFileForRead(const Twine &Path) override {
+          ++CountStats[llvm::sys::path::filename(Path.str())];
+          return ProxyFileSystem::openFileForRead(Path);
+        }
+        llvm::ErrorOr<vfs::Status> status(const Twine &Path) override {
+          ++CountStats[llvm::sys::path::filename(Path.str())];
+          return ProxyFileSystem::status(Path);
+        }
+
+      private:
+        llvm::StringMap<unsigned> &CountStats;
+      };
+
+      return IntrusiveRefCntPtr<ListenStatVFS>(
+          new ListenStatVFS(buildTestFS(Files), CountStats));
+    }
+
+    // If relative paths are used, they are resolved with testPath().
+    llvm::StringMap<std::string> Files;
+    llvm::StringMap<unsigned> &CountStats;
+  };
+
+  llvm::StringMap<unsigned> CountStats;
+  ListenStatsFSProvider FS(CountStats);
+  ErrorCheckingDiagConsumer DiagConsumer;
+  MockCompilationDatabase CDB;
+  ClangdServer Server(CDB, FS, DiagConsumer, ClangdServer::optsForTest());
+
+  auto SourcePath = testPath("foo.cpp");
+  auto HeaderPath = testPath("foo.h");
+  FS.Files[HeaderPath] = "struct TestSym {};";
+  Annotations Code(R"cpp(
+    #include "foo.h"
+
+    int main() {
+      TestSy^
+    })cpp");
+
+  runAddDocument(Server, SourcePath, Code.code());
+
+  EXPECT_EQ(CountStats["foo.h"], 1u);
+  auto Completions = cantFail(runCodeComplete(Server, SourcePath, Code.point(),
+                                              clangd::CodeCompleteOptions()))
+                         .Completions;
+  EXPECT_EQ(CountStats["foo.h"], 1u);
+  EXPECT_THAT(Completions,
+              ElementsAre(Field(&CodeCompletion::Name, "TestSym")));
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang

unittests/clangd/CodeCompleteTests.cpp

auto Results = completions(Server,
         #include "^"
       )cpp"
       );
   EXPECT_THAT(Results.Completions,
               AllOf(Has("sub/", CompletionItemKind::Folder),
                     Has("bar.h\"", CompletionItemKind::File)));
 }
 
+TEST(CompletionTest, NoAllScopesCompletionWhenQualified) {
+  clangd::CodeCompleteOptions Opts = {};
+  Opts.AllScopes = true;
+
+  auto Results = completions(
+      R"cpp(
+    void f() { na::Clangd^ }
+  )cpp",
+      {cls("na::ClangdA"), cls("nx::ClangdX"), cls("Clangd3")}, Opts);
+  EXPECT_THAT(Results.Completions,
+              UnorderedElementsAre(
+                  AllOf(Qualifier(""), Scope("na::"), Named("ClangdA"))));
+}
+
+TEST(CompletionTest, AllScopesCompletion) {
+  clangd::CodeCompleteOptions Opts = {};
+  Opts.AllScopes = true;
+
+  auto Results = completions(
+      R"cpp(
+    namespace na {
+    void f() { Clangd^ }
+    }
+  )cpp",
+      {cls("nx::Clangd1"), cls("ny::Clangd2"), cls("Clangd3"),
+       cls("na::nb::Clangd4")},
+      Opts);
+  EXPECT_THAT(
+      Results.Completions,
+      UnorderedElementsAre(AllOf(Qualifier("nx::"), Named("Clangd1")),
+                           AllOf(Qualifier("ny::"), Named("Clangd2")),
+                           AllOf(Qualifier(""), Scope(""), Named("Clangd3")),
+                           AllOf(Qualifier("nb::"), Named("Clangd4"))));
+}
+
+TEST(CompletionTest, NoQualifierIfShadowed) {
+  clangd::CodeCompleteOptions Opts = {};
+  Opts.AllScopes = true;
+
+  auto Results = completions(R"cpp(
+    namespace nx { class Clangd1 {}; }
+    using nx::Clangd1;
+    void f() { Clangd^ }
+  )cpp",
+                             {cls("nx::Clangd1"), cls("nx::Clangd2")}, Opts);
+  // Although Clangd1 is from another namespace, Sema tells us it's in-scope and
+  // needs no qualifier.
+  EXPECT_THAT(Results.Completions,
+              UnorderedElementsAre(AllOf(Qualifier(""), Named("Clangd1")),
+                                   AllOf(Qualifier("nx::"), Named("Clangd2"))));
+}
 
 } // namespace
 } // namespace clangd
 } // namespace clang

unittests/clangd/DexTests.cpp

 TEST(DexTest, NoMatchNestedScopes) {
   auto I = Dex::build(generateSymbols({"a::y1", "a::b::y2"}), URISchemes);
   FuzzyFindRequest Req;
   Req.Query = "y";
   Req.Scopes = {"a::"};
   EXPECT_THAT(match(*I, Req), UnorderedElementsAre("a::y1"));
 }
 
+TEST(DexTest, WildcardScope) {
+  auto I =
+      Dex::build(generateSymbols({"a::y1", "a::b::y2", "c::y3"}), URISchemes);
+  FuzzyFindRequest Req;
+  Req.Query = "y";
+  Req.Scopes = {"a::"};
+  Req.AnyScope = true;
+  EXPECT_THAT(match(*I, Req),
+              UnorderedElementsAre("a::y1", "a::b::y2", "c::y3"));
+}
+
 TEST(DexTest, IgnoreCases) {
   auto I = Dex::build(generateSymbols({"ns::ABC", "ns::abc"}), URISchemes);
   FuzzyFindRequest Req;
   Req.Query = "AB";
   Req.Scopes = {"ns::"};
   EXPECT_THAT(match(*I, Req), UnorderedElementsAre("ns::ABC", "ns::abc"));
 }
 

unittests/clangd/FSTests.cpp

+//===-- FSTests.cpp - File system related tests -----------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "FS.h"
+#include "TestFS.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+namespace clang {
+namespace clangd {
+namespace {
+
+TEST(FSTests, PreambleStatusCache) {
+  llvm::StringMap<std::string> Files;
+  Files["x"] = "";
+  Files["y"] = "";
+  auto FS = buildTestFS(Files);
+  FS->setCurrentWorkingDirectory(testRoot());
+
+  PreambleFileStatusCache StatCache;
+  auto ProduceFS = StatCache.getProducingFS(FS);
+  EXPECT_TRUE(ProduceFS->openFileForRead("x"));
+  EXPECT_TRUE(ProduceFS->status("y"));
+
+  EXPECT_TRUE(StatCache.lookup(testPath("x")).hasValue());
+  EXPECT_TRUE(StatCache.lookup(testPath("y")).hasValue());
+
+  vfs::Status S("fake", llvm::sys::fs::UniqueID(0, 0),
+                std::chrono::system_clock::now(), 0, 0, 1024,
+                llvm::sys::fs::file_type::regular_file, llvm::sys::fs::all_all);
+  StatCache.update(*FS, S);
+  auto ConsumeFS = StatCache.getConsumingFS(FS);
+  auto Cached = ConsumeFS->status(testPath("fake"));
+  EXPECT_TRUE(Cached);
+  EXPECT_EQ(Cached->getName(), S.getName());
+}
+
+} // namespace
+} // namespace clangd
+} // namespace clang

unittests/clangd/TestFS.cpp

 namespace clangd {
 using namespace llvm;
 
 IntrusiveRefCntPtr<vfs::FileSystem>
 buildTestFS(llvm::StringMap<std::string> const &Files,
             llvm::StringMap<time_t> const &Timestamps) {
   IntrusiveRefCntPtr<vfs::InMemoryFileSystem> MemFS(
       new vfs::InMemoryFileSystem);
+  MemFS->setCurrentWorkingDirectory(testRoot());
   for (auto &FileAndContents : Files) {
     StringRef File = FileAndContents.first();
     MemFS->addFile(
         File, Timestamps.lookup(File),
         MemoryBuffer::getMemBufferCopy(FileAndContents.second, File));
   }
   return MemFS;
 }