[clangd] Add a Filesystem that overlays Dirty files.

[njames93]

Summary

Create a ThreadsafeFS in the DraftStore that overlays the dirty file contents over another ThreadsafeFS.
This provides a nice thread-safe interface for using dirty file contents throughout the codebase, for example cross file refactoring.
Creating a Filesystem view will overlay a snapshot of the current contents, so if the draft store is updated while the view is being used, it will contain stale contents.

[njames93]

Remove some unrelated changes

[njames93]

Refactor RefCntString out of DraftStore class
Remove MTime from Draft, other users of DraftStore don't need to see it.

[njames93]

Start Splitting this patch up

[njames93]

Rebase

[njames93]

Ping?

[sammccall]

Sorry for the long delay here. I've gotten myself buried in too many different things.

Overall the idea of exposing drafts as an overlay FS is definitely growing on me - it makes it easier and clearer to control which feature is seeing which version of the files.

At a high level my main requests are:

• we should move maintenance of the drafts from ClangdLSPServer into ClangdServer. (This should maybe have been done a while ago, but this change makes it more complicated and therefore pressing)
• we should simplify the implementation as much as possible, and lean on existing infrastructure - there's a lot of custom pieces here like RefCntString and DraftStoreFileSystem that seem like small optimizations over existing types

(I might take a crack at moving DraftStore by itself, as there probably are issues and I want to understand what they are...)

clang-tools-extra/clangd/ClangdServer.h

172–182

Passing in FS + DirtyFS doesn't seem quite right, because we also pass in all the mutations that create the differences.

It seem rather that *ClangdServer* should maintain the overlay containing the dirty buffers, and expose it (for use in the few places that ClangdLSPServer currently uses DraftStore).

(the fact that DraftStore isn't accessible from ClangdServer did also come up when trying to split the *Server classes into Modules, so this seems like a helpful direction from that perspective too)

clang-tools-extra/clangd/DraftStore.cpp

95

These classes need comments describing why they exist :-)
(I think you're right that buffers may outlive the VFS)

98

Is there any reason to think we need this micro-optimization? It's quite invasive.

163

can't we use InMemoryFileSystem for this?

237

doing IO in view() doesn't seem obviously OK.

what's the practical consequence of the overlay's inodes not matching that of the underlying FS? (It seems reasonable to say that the files always have different identity, and may/may not have the same content)

clang-tools-extra/clangd/DraftStore.h

25

shared_ptr<const string> seems like a cheap alternative here.

However if the point is ultimately to obtain MemoryBuffers that we can hand out with the underlying data being refcounted, can we do that directly?

class SharedBuffer : public MemoryBuffer {
  std::shared_ptr<const std::string> Data;
public:
  Shared(StringRef Name, std::string Data);
  Shared(const RefcountBuffer &); // copyable
};

31

providing non-explicit string conversion operators is IME very likely to cause ambiguous overload errors when using this in variaous places :-(

52

avoid assert in headers for ODR reasons (ooh, we have a couple of violations i should clean up)

[njames93]

clang-tools-extra/clangd/ClangdServer.h

172–182

I was never a fan of this tbh. But moving DraftStore would result in this being too big,

clang-tools-extra/clangd/DraftStore.cpp

98

Its basically copied from llvm/support/MemoryBuffer.cpp

163

InMemoryFileSystem Would work in theory. However using that requires building a lot of unnecessary nodes for thing like intermediate directories.

237

It's probably not necessary, but I know preambles use the UniqueID. It may just be safer to create a uniqueID for each item in the DraftStore and leave it at that.

[njames93]

Address some comments, though I have a feeling @sammccall, I may have to wait until DraftStore has been refactored first before continuing on with this.

[sammccall]

In D94554#2595625, @njames93 wrote:

Address some comments, though I have a feeling @sammccall, I may have to wait until DraftStore has been refactored first before continuing on with this.

D97738 is an attempt at this. It is... sprawly, but it's an overdue cleanup that should fit together well with this patch, I think.

There may be some conflicts but I don't think it'll be terrible actually... I think we should keep going here, it looks really good.

clang-tools-extra/clangd/DraftStore.cpp

98

Sure, but this doesn't really answer the question! Can we keep this trivial until we have a reason to optimize it? (Clang typically holds tens of thousands of MemoryBuffers, but we're only likely to have a few hundred of these)

163

Probably, but it would keep this code simpler, supports directory iteration and status (used in code completion), and I'm fairly confident its path handling is solid.

It's certainly possible to add this optimization later if it seems important, but in this patch I think it distracts from the design questions.

237

The biggest risks I can see with this approach:

• in build-preamble-from-dirty-FS mode, would opening a draft cause the preamble to be considered invalid and needing rebuilding? My read of PrecompiledPreamble::CanReuse is no (UniqueIDs are not stored)
• when parsing, if the file can be read through the overlay *and* underlying via different paths (e.g. hardlinks), these won't be deduplicated. However giving them the same inode only changes the nature of the bug: the file would get whichever content was read first.

So I think it's as good as we can expect.

clang-tools-extra/clangd/DraftStore.h

35

having DraftStore sit on top of TFS seems a bit inside-out, giving it bigger scope than necessary.

What about giving DraftStore an asVFS() method that returns an in-memory filesystem?

then separately we can have a separate DirtyFS : TFS, that has a DraftStore& and a TFS &Base and implements viewImpl() on top of their public interfaces. Having the dependency in that direction seems more natural to me.

54

alternatively you can define whichever internal struct you like, like

struct FileData {
  std::string Filename;
  std::string Contents;
  // and MTime and UID
}

and store DenseMap<StringRef, shared_ptr<FileData>> (with the keys pointing into the values).

You can still hand out shared_ptr<const std::string> using the aliasing constructor of shared_ptr.

The advantages of this:

• it avoids the internal representation from being too constrained by the public API
• SharedStringBuffer can easily wrap the whole shared_ptr<FileData>, and so you doesn't need a *copy* of the filename

this is a little bit of complexity though, up to you

[njames93]

Getting there.

[njames93]

clang-tools-extra/clangd/DraftStore.h

35

How I had it was a symptom of using the underlying TFS for getting the UniqueID of files. But yes now that's gone this approach works.

[njames93]

clang-tools-extra/clangd/ClangdServer.h

400

Probably needs moving to its own place, but wasn't sure where best to put it.

clang-tools-extra/clangd/DraftStore.cpp

237

Unfortunately in the current implementation, opening a draft will invalidate and preambles that use the underlying file.
This is due to the last modification times not matching.
This could be addressed by querying the TFS on the textDocument/didOpen request to get the actual last modification time, but we shouldn't really be doing any kind of IO on that thread.

[sammccall]

Thanks, LG!

clang-tools-extra/clangd/ClangdServer.h

400

I think ClangdServer is fine, but this can be a unique_ptr<ThreadsafeFS> with the class moved to the implementation file

clang-tools-extra/clangd/DraftStore.cpp

80–84

we don't need try_emplace here, we overwrite the whole value regardless.
Can we use Draft &D = Drafts[File] again?

83

nit: std::time() (and std::time_t)

112

nit: /*RequiresNullTerminator=*/

[njames93]

clang-tools-extra/clangd/ClangdServer.h

400

How about privately inheriting from ThreadsafeFS :P
I agree, hiding the impl in the cpp is probably a much nicer way.

clang-tools-extra/clangd/DraftStore.cpp

80–84

I changed this because in an older version I wanted to set the UniqueID on the first time the file was added, however now we don't do that (or check the return value for insertion at all) its safe to go back to the operator[] access.

237

@sammccall Any further comments with regard to this. Is calling IO to get modification time in didOpen ok, or just accept opening a file would invalidate a preamble if the DirtyFS was used for preambles.

[njames93]

Address comments.

[sammccall]

clang-tools-extra/clangd/DraftStore.cpp

237

There's no urgency in resolving this:

• preambles-from-dirty-fs doesn't exist in this patch
• even once it does, we can introduce the problem first (in this experimental mode) and then solve it

That said, my suspicion is that having ClangdLSPServer stat the file, conditional on being in preambles-from-dirty-fs mode, would be OK.
(If the filesize matches I think it's safe to say the content does, and copy the timestamp. If the filesize mismatches... well, there are a number of scenarios involving encodings, and it's hard to say which will matter in practice, so we'd probably want to log and wait for the bug reports)

[sammccall]

Still LG btw!

clang-tools-extra/clangd/ClangdServer.h

351–353

Maybe add an explicit comment that this returns nullptr if the file is not open.
(When the type was Optional this was fairly self-explanatory)

400

nit: we don't use const on pointer members, just on the pointee where appropriate.
Maybe not the best style in a vacuum but it's fairly consistent and diverging from it is a bit confusing.

clang-tools-extra/clangd/ClangdLSPServer.cpp

WantDiags = Params.wantDiagnostics.getValue() ? WantDiagnostics::Yes
                                                   : WantDiagnostics::No;
 
   PathRef File = Params.textDocument.uri.file();
   auto Code = Server->getDraft(File);
   if (!Code) {
     log("Trying to incrementally change non-added document: {0}", File);
     return;
   }
+  std::string NewCode(*Code);
   for (const auto &Change : Params.contentChanges) {
-    if (auto Err = applyChange(*Code, Change)) {
+    if (auto Err = applyChange(NewCode, Change)) {
       // If this fails, we are most likely going to be not in sync anymore with
       // the client.  It is better to remove the draft and let further
       // operations fail rather than giving wrong results.
       Server->removeDocument(File);
       elog("Failed to update {0}: {1}", File, std::move(Err));
       return;
     }
   }
-  Server->addDocument(File, *Code, encodeVersion(Params.textDocument.version),
+  Server->addDocument(File, NewCode, encodeVersion(Params.textDocument.version),
                       WantDiags, Params.forceRebuild);
 }
 
 void ClangdLSPServer::onDocumentDidSave(
     const DidSaveTextDocumentParams &Params) {
   Server->reparseOpenFilesIfNeeded([](llvm::StringRef) { return true; });
 }
 

clang-tools-extra/clangd/ClangdServer.h

public:
   /// Creates a new ClangdServer instance.
   ///
   /// ClangdServer uses \p CDB to obtain compilation arguments for parsing. Note
   /// that ClangdServer only obtains compilation arguments once for each newly
   /// added file (i.e., when processing a first call to addDocument) and reuses
   /// those arguments for subsequent reparses. However, ClangdServer will check
   /// if compilation arguments changed on calls to forceReparse().
   ClangdServer(const GlobalCompilationDatabase &CDB, const ThreadsafeFS &TFS,
                const Options &Opts, Callbacks *Callbacks = nullptr);
   ~ClangdServer();
 
   /// Gets the installed feature module of a given type, if any.
   /// This exposes access the public interface of feature modules that have one.
   template <typename Mod> Mod *featureModule() {
     return FeatureModules ? FeatureModules->get<Mod>() : nullptr;
   }
   template <typename Mod> const Mod *featureModule() const {
     return FeatureModules ? FeatureModules->get<Mod>() : nullptr;
   }
 
   /// Add a \p File to the list of tracked C++ files or update the contents if
   /// \p File is already tracked. Also schedules parsing of the AST for it on a
   /// separate thread. When the parsing is complete, DiagConsumer passed in
   /// constructor will receive onDiagnosticsReady callback.
   /// Version identifies this snapshot and is propagated to ASTs, preambles,
   /// diagnostics etc built from it. If empty, a version number is generated.
   void addDocument(PathRef File, StringRef Contents,
public:
   /// currently open files.
   /// Overall memory usage of clangd may be significantly more than reported
   /// here, as this metric does not account (at least) for:
   ///   - memory occupied by static and dynamic index,
   ///   - memory required for in-flight requests,
   /// FIXME: those metrics might be useful too, we should add them.
   llvm::StringMap<TUScheduler::FileStats> fileStats() const;
 
-  llvm::Optional<std::string> getDraft(PathRef File) const;
+  /// Gets the contents of a currently tracked file. Returns nullptr if the file
+  /// isn't being tracked.
+  std::shared_ptr<const std::string> getDraft(PathRef File) const;
 
   // Blocks the main thread until the server is idle. Only for use in tests.
   // Returns false if the timeout expires.
   // FIXME: various subcomponents each get the full timeout, so it's more of
   // an order of magnitude than a hard deadline.
   LLVM_NODISCARD bool
   blockUntilIdleForTest(llvm::Optional<double> TimeoutSeconds = 10);
 
private:
 
   llvm::Optional<std::string> WorkspaceRoot;
   llvm::Optional<TUScheduler> WorkScheduler;
 
   // Store of the current versions of the open documents.
   // Only written from the main thread (despite being threadsafe).
   // FIXME: TUScheduler also keeps these, unify?
   DraftStore DraftMgr;
+
+  std::unique_ptr<ThreadsafeFS> DirtyFS;
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif

clang-tools-extra/clangd/ClangdServer.cpp

if (ServerCallbacks)
       ServerCallbacks->onFileUpdated(File, Status);
   }
 
 private:
   FileIndex *FIndex;
   ClangdServer::Callbacks *ServerCallbacks;
 };
 
+class DraftStoreFS : public ThreadsafeFS {
+public:
+  DraftStoreFS(const ThreadsafeFS &Base, const DraftStore &Drafts)
+      : Base(Base), DirtyFiles(Drafts) {}
+
+private:
+  llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem> viewImpl() const override {
+    auto OFS = llvm::makeIntrusiveRefCnt<llvm::vfs::OverlayFileSystem>(
+        Base.view(llvm::None));
+    OFS->pushOverlay(DirtyFiles.asVFS());
+    return OFS;
+  }
+
+  const ThreadsafeFS &Base;
+  const DraftStore &DirtyFiles;
+};
+
 } // namespace
 
 ClangdServer::Options ClangdServer::optsForTest() {
   ClangdServer::Options Opts;
   Opts.UpdateDebounce = DebouncePolicy::fixed(/*zero*/ {});
   Opts.StorePreamblesInMemory = true;
   Opts.AsyncThreadsCount = 4; // Consistent!
   return Opts;

 }
 
 ClangdServer::ClangdServer(const GlobalCompilationDatabase &CDB,
                            const ThreadsafeFS &TFS, const Options &Opts,
                            Callbacks *Callbacks)
     : FeatureModules(Opts.FeatureModules), CDB(CDB), TFS(TFS),
       DynamicIdx(Opts.BuildDynamicSymbolIndex ? new FileIndex() : nullptr),
       ClangTidyProvider(Opts.ClangTidyProvider),
-      WorkspaceRoot(Opts.WorkspaceRoot) {
+      WorkspaceRoot(Opts.WorkspaceRoot),
+      DirtyFS(std::make_unique<DraftStoreFS>(TFS, DraftMgr)) {
   // Pass a callback into `WorkScheduler` to extract symbols from a newly
   // parsed file and rebuild the file index synchronously each time an AST
   // is parsed.
   WorkScheduler.emplace(
       CDB, TUScheduler::Options(Opts),
       std::make_unique<UpdateIndexCallbacks>(DynamicIdx.get(), Callbacks));
   // Adds an index to the stack, at higher priority than existing indexes.
   auto AddIndex = [&](SymbolIndex *Idx) {

 }
 
 void ClangdServer::reparseOpenFilesIfNeeded(
     llvm::function_ref<bool(llvm::StringRef File)> Filter) {
   // Reparse only opened files that were modified.
   for (const Path &FilePath : DraftMgr.getActiveFiles())
     if (Filter(FilePath))
       if (auto Draft = DraftMgr.getDraft(FilePath)) // else disappeared in race?
-        addDocument(FilePath, std::move(Draft->Contents), Draft->Version,
+        addDocument(FilePath, *Draft->Contents, Draft->Version,
                     WantDiagnostics::Auto);
 }
 
-llvm::Optional<std::string> ClangdServer::getDraft(PathRef File) const {
+std::shared_ptr<const std::string> ClangdServer::getDraft(PathRef File) const {
   auto Draft = DraftMgr.getDraft(File);
   if (!Draft)
-    return llvm::None;
+    return nullptr;
   return std::move(Draft->Contents);
 }
 
 std::function<Context(PathRef)>
 ClangdServer::createConfiguredContextProvider(const config::Provider *Provider,
                                               Callbacks *Publish) {
   if (!Provider)
     return [](llvm::StringRef) { return Context::current().clone(); };

clang-tools-extra/clangd/DraftStore.h

 //===--- DraftStore.h - File contents container -----------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_DRAFTSTORE_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_DRAFTSTORE_H
 
 #include "Protocol.h"
 #include "support/Path.h"
 #include "clang/Basic/LLVM.h"
 #include "llvm/ADT/StringMap.h"
+#include "llvm/Support/VirtualFileSystem.h"
 #include <mutex>
 #include <string>
 #include <vector>
 
 namespace clang {
 namespace clangd {
 
 /// A thread-safe container for files opened in a workspace, addressed by
 /// filenames. The contents are owned by the DraftStore.
 /// Each time a draft is updated, it is assigned a version. This can be
 /// specified by the caller or incremented from the previous version.
 class DraftStore {
 public:
   struct Draft {
-    std::string Contents;
+    std::shared_ptr<const std::string> Contents;
     std::string Version;
   };
 
   /// \return Contents of the stored document.
   /// For untracked files, a llvm::None is returned.
   llvm::Optional<Draft> getDraft(PathRef File) const;
 
   /// \return List of names of the drafts in this store.
   std::vector<Path> getActiveFiles() const;
 
   /// Replace contents of the draft for \p File with \p Contents.
   /// If version is empty, one will be automatically assigned.
   /// Returns the version.
   std::string addDraft(PathRef File, llvm::StringRef Version,
                        StringRef Contents);
 
   /// Remove the draft from the store.
   void removeDraft(PathRef File);
 
+  llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem> asVFS() const;
+
 private:
+  struct DraftAndTime {
+    Draft Draft;
+    std::time_t MTime;
+  };
   mutable std::mutex Mutex;
-  llvm::StringMap<Draft> Drafts;
+  llvm::StringMap<DraftAndTime> Drafts;
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif

clang-tools-extra/clangd/DraftStore.cpp

 //===--- DraftStore.cpp - File contents container ---------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "DraftStore.h"
 #include "SourceCode.h"
 #include "support/Logger.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Support/Errc.h"
+#include "llvm/Support/VirtualFileSystem.h"
+#include <memory>
 
 namespace clang {
 namespace clangd {
 
 llvm::Optional<DraftStore::Draft> DraftStore::getDraft(PathRef File) const {
   std::lock_guard<std::mutex> Lock(Mutex);
 
   auto It = Drafts.find(File);
   if (It == Drafts.end())
     return None;
 
-  return It->second;
+  return It->second.Draft;
 }
 
 std::vector<Path> DraftStore::getActiveFiles() const {
   std::lock_guard<std::mutex> Lock(Mutex);
   std::vector<Path> ResultVector;
 
   for (auto DraftIt = Drafts.begin(); DraftIt != Drafts.end(); DraftIt++)
     ResultVector.push_back(std::string(DraftIt->getKey()));
if (!SpecifiedVersion.empty()) {
     increment(D.Version);
   }
 }
 
 std::string DraftStore::addDraft(PathRef File, llvm::StringRef Version,
                                  llvm::StringRef Contents) {
   std::lock_guard<std::mutex> Lock(Mutex);
 
-  Draft &D = Drafts[File];
-  updateVersion(D, Version);
-  D.Contents = Contents.str();
-  return D.Version;
+  auto &D = Drafts[File];
+  updateVersion(D.Draft, Version);
+  std::time(&D.MTime);
+  D.Draft.Contents = std::make_shared<std::string>(Contents);
+  return D.Draft.Version;
 }
 
 void DraftStore::removeDraft(PathRef File) {
   std::lock_guard<std::mutex> Lock(Mutex);
 
   Drafts.erase(File);
 }
 
+namespace {
+
+/// A read only MemoryBuffer shares ownership of a ref counted string. The
+/// shared string object must not be modified while an owned by this buffer.
+class SharedStringBuffer : public llvm::MemoryBuffer {
+  const std::shared_ptr<const std::string> BufferContents;
+  const std::string Name;
+
+public:
+  BufferKind getBufferKind() const override {
+    return MemoryBuffer::MemoryBuffer_Malloc;
+  }
+
+  StringRef getBufferIdentifier() const override { return Name; }
+
+  SharedStringBuffer(std::shared_ptr<const std::string> Data, StringRef Name)
+      : BufferContents(std::move(Data)), Name(Name) {
+    assert(BufferContents && "Can't create from empty shared_ptr");
+    MemoryBuffer::init(BufferContents->c_str(),
+                       BufferContents->c_str() + BufferContents->size(),
+                       /*RequiresNullTerminator=*/true);
+  }
+};
+} // namespace
+
+llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem> DraftStore::asVFS() const {
+  auto MemFS = llvm::makeIntrusiveRefCnt<llvm::vfs::InMemoryFileSystem>();
+  std::lock_guard<std::mutex> Guard(Mutex);
+  for (const auto &Draft : Drafts)
+    MemFS->addFile(Draft.getKey(), Draft.getValue().MTime,
+                   std::make_unique<SharedStringBuffer>(
+                       Draft.getValue().Draft.Contents, Draft.getKey()));
+  return MemFS;
+}
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/unittests/DraftStoreTests.cpp

 namespace {
 
 TEST(DraftStore, Versions) {
   DraftStore DS;
   Path File = "foo.cpp";
 
   EXPECT_EQ("25", DS.addDraft(File, "25", ""));
   EXPECT_EQ("25", DS.getDraft(File)->Version);
-  EXPECT_EQ("", DS.getDraft(File)->Contents);
+  EXPECT_EQ("", *DS.getDraft(File)->Contents);
 
   EXPECT_EQ("26", DS.addDraft(File, "", "x"));
   EXPECT_EQ("26", DS.getDraft(File)->Version);
-  EXPECT_EQ("x", DS.getDraft(File)->Contents);
+  EXPECT_EQ("x", *DS.getDraft(File)->Contents);
 
   EXPECT_EQ("27", DS.addDraft(File, "", "x")) << "no-op change";
   EXPECT_EQ("27", DS.getDraft(File)->Version);
-  EXPECT_EQ("x", DS.getDraft(File)->Contents);
+  EXPECT_EQ("x", *DS.getDraft(File)->Contents);
 
   // We allow versions to go backwards.
   EXPECT_EQ("7", DS.addDraft(File, "7", "y"));
   EXPECT_EQ("7", DS.getDraft(File)->Version);
-  EXPECT_EQ("y", DS.getDraft(File)->Contents);
+  EXPECT_EQ("y", *DS.getDraft(File)->Contents);
 }
 
 } // namespace
 } // namespace clangd
 } // namespace clang