[clangd] Show background index status using LSP 3.15 work-done progress notifications

[sammccall]

Summary

It simply shows the completed/total items on the background queue, e.g.
indexing: 233/1000
The denominator is reset to zero every time the queue goes idle.

The protocol is fairly complicated here (requires creating a remote "progress"
resource before sending updates). We implement the full protocol, but I've added
an extension allowing it to be skipped to reduce the burden on clients - in
particular the lit test takes this shortcut.

The addition of background index progress to DiagnosticConsumer seems ridiculous
at first glance, but I believe that interface is trending in the direction of
"ClangdServer callbacks" anyway. It's due for a rename, but otherwise actually
fits.

[sammccall]

Revert changes to VSCode client. This experimental version of the VSCode libs
is fairly new and some corp mirrors we care about are behind ;-)

also clang-format

[sammccall]

revert accidental change

[merge_guards_bot]

Unit tests: unknown.

clang-tidy: fail. clang-tidy found 1 errors and 11 warnings.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt

[merge_guards_bot]

Unit tests: unknown.

clang-tidy: fail. clang-tidy found 1 errors and 11 warnings.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt

[merge_guards_bot]

Unit tests: unknown.

clang-tidy: fail. clang-tidy found 1 errors and 11 warnings.

clang-format: fail. Please format your changes with clang-format by running git-clang-format HEAD^ or applying this patch.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt

[kadircet]

clang-tools-extra/clangd/ClangdLSPServer.h

223

s/PendingBackgraundIndexProgress/PendingBackgroundIndexProgress/

232

initialize to false

clang-tools-extra/clangd/Protocol.cpp

383

why not have a single struct with that has a required kind field and a bunch of optional fields.
Later on we can assert on the existence of fields depending on the kind, I think it would simplify the implementation.

[sammccall]

address comments

clang-tools-extra/clangd/Protocol.cpp

383

Yeah, this was my first thought/attempt. It's possible but I think not ideal in the end.

The main downsides:

• this would diverge from LSP and so make it harder to cross-reference things
• this would diverge from LSP and usually we don't, so it's surprising
• the semantics of the "same" field across different events are sometimes subtly different. e.g. Begin.cancellable is whether a cancel button is shown (and in VSCode, the overall UI!) whereas End.cancellable controls its enablement.
• between replicating the LSP docs, documenting divergence, documenting varied optionality, and documenting varying semantics, the merged struct is really hard to document well
• it's a bit harder to see the structure of the messages clangd sends this way: e.g. we always send message in report, but never in begin/end, how we handle percentage etc

Mostly I think following LSP closely is a good thing, but it sucks when the spec is a mess :-(

[merge_guards_bot]

Unit tests: unknown.

clang-tidy: fail. clang-tidy found 8 errors and 12 warnings. 12 of them are added as review comments below (why?).

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

[kadircet]

clang-tools-extra/clangd/Protocol.cpp

383

this would diverge from LSP and so make it harder to cross-reference things

ah sorry, I didn't know LSP defined those in 3 different structs, that makes sense.

SG then

clang-tools-extra/clangd/ClangdLSPServer.h

 
 private:
   // Implement DiagnosticsConsumer.
   void onDiagnosticsReady(PathRef File, std::vector<Diag> Diagnostics) override;
   void onFileUpdated(PathRef File, const TUStatus &Status) override;
   void
   onHighlightingsReady(PathRef File,
                        std::vector<HighlightingToken> Highlightings) override;
+  void onBackgroundIndexProgress(const BackgroundQueue::Stats &Stats) override;
 
   // LSP methods. Notifications have signature void(const Params&).
   // Calls have signature void(const Params&, Callback<Response>).
   void onInitialize(const InitializeParams &, Callback<llvm::json::Value>);
   void onShutdown(const ShutdownParams &, Callback<std::nullptr_t>);
   void onSync(const NoParams &, Callback<std::nullptr_t>);
   void onDocumentDidOpen(const DidOpenTextDocumentParams &);
   void onDocumentDidChange(const DidChangeTextDocumentParams &);
auto HandleReply =
                                           ErrorCode::InvalidParams));
           }
         };
     callRaw(Method, std::move(Params), std::move(HandleReply));
   }
   void callRaw(StringRef Method, llvm::json::Value Params,
                Callback<llvm::json::Value> CB);
   void notify(StringRef Method, llvm::json::Value Params);
+  template <typename T> void progress(const llvm::json::Value &Token, T Value) {
+    ProgressParams<T> Params;
+    Params.token = Token;
+    Params.value = std::move(Value);
+    notify("$/progress", Params);
+  }
 
   const FileSystemProvider &FSProvider;
   /// Options used for code completion
   clangd::CodeCompleteOptions CCOpts;
   /// Options used for diagnostics.
   ClangdDiagnosticOptions DiagOpts;
   /// The supported kinds of the client.
   SymbolKindBitset SupportedSymbolKinds;
   /// The supported completion item kinds of the client.
   CompletionItemKindBitset SupportedCompletionItemKinds;
   /// Whether the client supports CodeAction response objects.
   bool SupportsCodeAction = false;
   /// From capabilities of textDocument/documentSymbol.
   bool SupportsHierarchicalDocumentSymbol = false;
   /// Whether the client supports showing file status.
   bool SupportFileStatus = false;
   /// Which kind of markup should we use in textDocument/hover responses.
   MarkupKind HoverContentFormat = MarkupKind::PlainText;
   /// Whether the client supports offsets for parameter info labels.
   bool SupportsOffsetsInSignatureHelp = false;
+  std::mutex BackgroundIndexProgressMutex;
+  enum class BackgroundIndexProgress {
+    // Client doesn't support reporting progress. No transitions possible.
+    Unsupported,
+    // The queue is idle, and the client has no progress bar.
+    // Can transition to Creating when we have some activity.
+    Empty,
+    // We've requested the client to create a progress bar.
+    // Meanwhile, the state is buffered in PendingBackgroundIndexProgress.
+    Creating,
+    // The client has a progress bar, and we can send it updates immediately.
+    Live,
+  } BackgroundIndexProgressState = BackgroundIndexProgress::Unsupported;
+  // The progress to send when the progress bar is created.
+  // Only valid in state Creating.
+  BackgroundQueue::Stats PendingBackgroundIndexProgress;
+  /// LSP extension: skip WorkDoneProgressCreate, just send progress streams.
+  bool BackgroundIndexSkipCreate = false;
   // Store of the current versions of the open documents.
   DraftStore DraftMgr;
 
   // The CDB is created by the "initialize" LSP method.
   bool UseDirBasedCDB;                     // FIXME: make this a capability.
   llvm::Optional<Path> CompileCommandsDir; // FIXME: merge with capability?
   std::unique_ptr<GlobalCompilationDatabase> BaseCDB;
   // CDB is BaseCDB plus any commands overridden via LSP extensions.

clang-tools-extra/clangd/ClangdLSPServer.cpp

 #include "llvm/Support/Error.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/JSON.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/SHA1.h"
 #include "llvm/Support/ScopedPrinter.h"
 #include <cstddef>
 #include <memory>
+#include <mutex>
 #include <string>
 #include <vector>
 
 namespace clang {
 namespace clangd {
 namespace {
 /// Transforms a tweak into a code action that would apply it if executed.
 /// EXPECTS: T.prepare() was called and returned true.
void ClangdLSPServer::onInitialize(const InitializeParams &Params,
   if (Params.capabilities.CompletionItemKinds)
     SupportedCompletionItemKinds |= *Params.capabilities.CompletionItemKinds;
   SupportsCodeAction = Params.capabilities.CodeActionStructure;
   SupportsHierarchicalDocumentSymbol =
       Params.capabilities.HierarchicalDocumentSymbol;
   SupportFileStatus = Params.initializationOptions.FileStatus;
   HoverContentFormat = Params.capabilities.HoverContentFormat;
   SupportsOffsetsInSignatureHelp = Params.capabilities.OffsetsInSignatureHelp;
+  if (Params.capabilities.WorkDoneProgress)
+    BackgroundIndexProgressState = BackgroundIndexProgress::Empty;
+  BackgroundIndexSkipCreate = Params.capabilities.ImplicitProgressCreation;
 
   // Per LSP, renameProvider can be either boolean or RenameOptions.
   // RenameOptions will be specified if the client states it supports prepare.
   llvm::json::Value RenameProvider =
       llvm::json::Object{{"prepareProvider", true}};
   if (!Params.capabilities.RenamePrepareSupport) // Only boolean allowed per LSP
     RenameProvider = true;
 
// Cache FixIts
     std::lock_guard<std::mutex> Lock(FixItsMutex);
     FixItsMap[File] = LocalFixIts;
   }
 
   // Send a notification to the LSP client.
   publishDiagnostics(URI, std::move(LSPDiagnostics));
 }
 
+void ClangdLSPServer::onBackgroundIndexProgress(
+    const BackgroundQueue::Stats &Stats) {
+  static const char ProgressToken[] = "backgroundIndexProgress";
+  std::lock_guard<std::mutex> Lock(BackgroundIndexProgressMutex);
+
+  auto NotifyProgress = [this](const BackgroundQueue::Stats &Stats) {
+    if (BackgroundIndexProgressState != BackgroundIndexProgress::Live) {
+      WorkDoneProgressBegin Begin;
+      Begin.percentage = true;
+      Begin.title = "indexing";
+      progress(ProgressToken, std::move(Begin));
+      BackgroundIndexProgressState = BackgroundIndexProgress::Live;
+    }
+
+    if (Stats.Completed < Stats.Enqueued) {
+      assert(Stats.Enqueued > Stats.LastIdle);
+      WorkDoneProgressReport Report;
+      Report.percentage = 100.0 * (Stats.Completed - Stats.LastIdle) /
+                          (Stats.Enqueued - Stats.LastIdle);
+      Report.message =
+          llvm::formatv("{0}/{1}", Stats.Completed - Stats.LastIdle,
+                        Stats.Enqueued - Stats.LastIdle);
+      progress(ProgressToken, std::move(Report));
+    } else {
+      assert(Stats.Completed == Stats.Enqueued);
+      progress(ProgressToken, WorkDoneProgressEnd());
+      BackgroundIndexProgressState = BackgroundIndexProgress::Empty;
+    }
+  };
+
+  switch (BackgroundIndexProgressState) {
+  case BackgroundIndexProgress::Unsupported:
+    return;
+  case BackgroundIndexProgress::Creating:
+    // Cache this update for when the progress bar is available.
+    PendingBackgroundIndexProgress = Stats;
+    return;
+  case BackgroundIndexProgress::Empty: {
+    if (BackgroundIndexSkipCreate) {
+      NotifyProgress(Stats);
+      break;
+    }
+    // Cache this update for when the progress bar is available.
+    PendingBackgroundIndexProgress = Stats;
+    BackgroundIndexProgressState = BackgroundIndexProgress::Creating;
+    WorkDoneProgressCreateParams CreateRequest;
+    CreateRequest.token = ProgressToken;
+    call<std::nullptr_t>(
+        "window/workDoneProgress/create", CreateRequest,
+        [this, NotifyProgress](llvm::Expected<std::nullptr_t> E) {
+          std::lock_guard<std::mutex> Lock(BackgroundIndexProgressMutex);
+          if (E) {
+            NotifyProgress(this->PendingBackgroundIndexProgress);
+          } else {
+            elog("Failed to create background index progress bar: {0}",
+                 E.takeError());
+            // give up forever rather than thrashing about
+            BackgroundIndexProgressState = BackgroundIndexProgress::Unsupported;
+          }
+        });
+    break;
+  }
+  case BackgroundIndexProgress::Live:
+    NotifyProgress(Stats);
+    break;
+  }
+}
+
 void ClangdLSPServer::onFileUpdated(PathRef File, const TUStatus &Status) {
   if (!SupportFileStatus)
     return;
   // FIXME: we don't emit "BuildingFile" and `RunningAction`, as these
   // two statuses are running faster in practice, which leads the UI constantly
   // changing, and doesn't provide much value. We may want to emit status at a
   // reasonable time interval (e.g. 0.5s).
   if (Status.Action.S == TUAction::BuildingFile ||

clang-tools-extra/clangd/ClangdServer.h

virtual void onDiagnosticsReady(PathRef File,
                                   std::vector<Diag> Diagnostics) = 0;
   /// Called whenever the file status is updated.
   virtual void onFileUpdated(PathRef File, const TUStatus &Status){};
 
   /// Called by ClangdServer when some \p Highlightings for \p File are ready.
   virtual void
   onHighlightingsReady(PathRef File,
                        std::vector<HighlightingToken> Highlightings) {}
+
+  // Called when background indexing tasks are enqueued, started, or completed.
+  virtual void onBackgroundIndexProgress(const BackgroundQueue::Stats &Stats) {}
 };
 
 /// When set, used by ClangdServer to get clang-tidy options for each particular
 /// file. Must be thread-safe. We use this instead of ClangTidyOptionsProvider
 /// to allow reading tidy configs from the VFS used for parsing.
 using ClangTidyOptionsBuilder = std::function<tidy::ClangTidyOptions(
     llvm::vfs::FileSystem &, llvm::StringRef /*File*/)>;
 

clang-tools-extra/clangd/ClangdServer.cpp

ClangdServer::ClangdServer(const GlobalCompilationDatabase &CDB,
   };
   if (Opts.StaticIndex)
     AddIndex(Opts.StaticIndex);
   if (Opts.BackgroundIndex) {
     BackgroundIdx = std::make_unique<BackgroundIndex>(
         Context::current().clone(), FSProvider, CDB,
         BackgroundIndexStorage::createDiskBackedStorageFactory(
             [&CDB](llvm::StringRef File) { return CDB.getProjectInfo(File); }),
-        std::max(Opts.AsyncThreadsCount, 1u));
+        std::max(Opts.AsyncThreadsCount, 1u),
+        [&DiagConsumer](BackgroundQueue::Stats S) {
+          DiagConsumer.onBackgroundIndexProgress(S);
+        });
     AddIndex(BackgroundIdx.get());
   }
   if (DynamicIdx)
     AddIndex(DynamicIdx.get());
 }
 
 void ClangdServer::addDocument(PathRef File, llvm::StringRef Contents,
                                WantDiagnostics WantDiags) {

clang-tools-extra/clangd/Protocol.h

struct ClientCapabilities {
 
   /// The content format that should be used for Hover requests.
   /// textDocument.hover.contentEncoding
   MarkupKind HoverContentFormat = MarkupKind::PlainText;
 
   /// The client supports testing for validity of rename operations
   /// before execution.
   bool RenamePrepareSupport = false;
+
+  /// The client supports progress notifications.
+  /// window.workDoneProgress
+  bool WorkDoneProgress = false;
+
+  /// The client supports implicit $/progress work-done progress streams,
+  /// without a preceding window/workDoneProgress/create.
+  /// This is a clangd extension.
+  /// window.implicitWorkDoneProgressCreate
+  bool ImplicitProgressCreation = false;
 };
 bool fromJSON(const llvm::json::Value &, ClientCapabilities &);
 
 /// Clangd extension that's used in the 'compilationDatabaseChanges' in
 /// workspace/didChangeConfiguration to record updates to the in-memory
 /// compilation database.
 struct ClangdCompileCommand {
   std::string workingDirectory;
struct InitializeParams {
   /// The initial trace setting. If omitted trace is disabled ('off').
   llvm::Optional<TraceLevel> trace;
 
   /// User-provided initialization options.
   InitializationOptions initializationOptions;
 };
 bool fromJSON(const llvm::json::Value &, InitializeParams &);
 
+struct WorkDoneProgressCreateParams {
+  /// The token to be used to report progress.
+  llvm::json::Value token = nullptr;
+};
+llvm::json::Value toJSON(const WorkDoneProgressCreateParams &P);
+
+template <typename T> struct ProgressParams {
+  /// The progress token provided by the client or server.
+  llvm::json::Value token = nullptr;
+
+  /// The progress data.
+  T value;
+};
+template <typename T> llvm::json::Value toJSON(const ProgressParams<T> &P) {
+  return llvm::json::Object{{"token", P.token}, {"value", P.value}};
+}
+/// To start progress reporting a $/progress notification with the following
+/// payload must be sent.
+struct WorkDoneProgressBegin {
+  /// Mandatory title of the progress operation. Used to briefly inform about
+  /// the kind of operation being performed.
+  ///
+  /// Examples: "Indexing" or "Linking dependencies".
+  std::string title;
+
+  /// Controls if a cancel button should show to allow the user to cancel the
+  /// long-running operation. Clients that don't support cancellation are
+  /// allowed to ignore the setting.
+  bool cancellable = false;
+
+  /// Optional progress percentage to display (value 100 is considered 100%).
+  /// If not provided infinite progress is assumed and clients are allowed
+  /// to ignore the `percentage` value in subsequent in report notifications.
+  ///
+  /// The value should be steadily rising. Clients are free to ignore values
+  /// that are not following this rule.
+  ///
+  /// Clangd implementation note: we only send nonzero percentages in
+  /// the WorkProgressReport. 'true' here means percentages will be used.
+  bool percentage = false;
+};
+llvm::json::Value toJSON(const WorkDoneProgressBegin &);
+
+/// Reporting progress is done using the following payload.
+struct WorkDoneProgressReport {
+  /// Mandatory title of the progress operation. Used to briefly inform about
+  /// the kind of operation being performed.
+  ///
+  /// Examples: "Indexing" or "Linking dependencies".
+  std::string title;
+
+  /// Controls enablement state of a cancel button. This property is only valid
+  /// if a cancel button got requested in the `WorkDoneProgressStart` payload.
+  ///
+  /// Clients that don't support cancellation or don't support control
+  /// the button's enablement state are allowed to ignore the setting.
+  llvm::Optional<bool> cancellable;
+
+  /// Optional, more detailed associated progress message. Contains
+  /// complementary information to the `title`.
+  ///
+  /// Examples: "3/25 files", "project/src/module2", "node_modules/some_dep".
+  /// If unset, the previous progress message (if any) is still valid.
+  llvm::Optional<std::string> message;
+
+  /// Optional progress percentage to display (value 100 is considered 100%).
+  /// If not provided infinite progress is assumed and clients are allowed
+  /// to ignore the `percentage` value in subsequent in report notifications.
+  ///
+  /// The value should be steadily rising. Clients are free to ignore values
+  /// that are not following this rule.
+  llvm::Optional<double> percentage;
+};
+llvm::json::Value toJSON(const WorkDoneProgressReport &);
+//
+/// Signals the end of progress reporting.
+struct WorkDoneProgressEnd {
+  /// Optional, a final message indicating to for example indicate the outcome
+  /// of the operation.
+  llvm::Optional<std::string> message;
+};
+llvm::json::Value toJSON(const WorkDoneProgressEnd &);
+
 enum class MessageType {
   /// An error message.
   Error = 1,
   /// A warning message.
   Warning = 2,
   /// An information message.
   Info = 3,
   /// A log message.

clang-tools-extra/clangd/Protocol.cpp

if (auto *Symbol = Workspace->getObject("symbol")) {
         if (auto *ValueSet = SymbolKind->get("valueSet")) {
           R.WorkspaceSymbolKinds.emplace();
           if (!fromJSON(*ValueSet, *R.WorkspaceSymbolKinds))
             return false;
         }
       }
     }
   }
+  if (auto *Window = O->getObject("window")) {
+    if (auto WorkDoneProgress = Window->getBoolean("workDoneProgress"))
+      R.WorkDoneProgress = *WorkDoneProgress;
+    if (auto Implicit = Window->getBoolean("implicitWorkDoneProgressCreate"))
+      R.ImplicitProgressCreation = *Implicit;
+  }
   if (auto *OffsetEncoding = O->get("offsetEncoding")) {
     R.offsetEncoding.emplace();
     if (!fromJSON(*OffsetEncoding, *R.offsetEncoding))
       return false;
   }
   return true;
 }
 
 bool fromJSON(const llvm::json::Value &Params, InitializeParams &R) {
   llvm::json::ObjectMapper O(Params);
   if (!O)
     return false;
   // We deliberately don't fail if we can't parse individual fields.
   // Failing to handle a slightly malformed initialize would be a disaster.
   O.map("processId", R.processId);
   O.map("rootUri", R.rootUri);
   O.map("rootPath", R.rootPath);
   O.map("capabilities", R.capabilities);
   O.map("trace", R.trace);
   O.map("initializationOptions", R.initializationOptions);
   return true;
 }
 
+llvm::json::Value toJSON(const WorkDoneProgressCreateParams &P) {
+  return llvm::json::Object{{"token", P.token}};
+}
+
+llvm::json::Value toJSON(const WorkDoneProgressBegin &P) {
+  llvm::json::Object Result{
+      {"kind", "begin"},
+      {"title", P.title},
+  };
+  if (P.cancellable)
+    Result["cancellable"] = true;
+  if (P.percentage)
+    Result["percentage"] = 0;
+  return Result;
+}
+
+llvm::json::Value toJSON(const WorkDoneProgressReport &P) {
+  llvm::json::Object Result{{"kind", "report"}};
+  if (P.cancellable)
+    Result["cancellable"] = *P.cancellable;
+  if (P.message)
+    Result["message"] = *P.message;
+  if (P.percentage)
+    Result["percentage"] = *P.percentage;
+  return Result;
+}
+
+llvm::json::Value toJSON(const WorkDoneProgressEnd &P) {
+  llvm::json::Object Result{{"kind", "end"}};
+  if (P.message)
+    Result["message"] = *P.message;
+  return Result;
+}
+
 llvm::json::Value toJSON(const MessageType &R) {
   return static_cast<int64_t>(R);
 }
 
 llvm::json::Value toJSON(const ShowMessageParams &R) {
   return llvm::json::Object{{"type", R.type}, {"message", R.message}};
 }
 

clang-tools-extra/clangd/index/Background.h

struct Task {
     std::function<void()> Run;
     llvm::ThreadPriority ThreadPri = llvm::ThreadPriority::Background;
     unsigned QueuePri = 0; // Higher-priority tasks will run first.
     std::string Tag;       // Allows priority to be boosted later.
 
     bool operator<(const Task &O) const { return QueuePri < O.QueuePri; }
   };
 
+  // Describes the number of tasks processed by the queue.
+  struct Stats {
+    unsigned Enqueued = 0;  // Total number of tasks ever enqueued.
+    unsigned Active = 0;    // Tasks being currently processed by a worker.
+    unsigned Completed = 0; // Tasks that have been finished.
+    unsigned LastIdle = 0;  // Number of completed tasks when last empty.
+  };
+
+  BackgroundQueue(std::function<void(Stats)> OnProgress = nullptr)
+      : OnProgress(OnProgress) {}
+
   // Add tasks to the queue.
   void push(Task);
   void append(std::vector<Task>);
   // Boost priority of current and new tasks with matching Tag, if they are
   // lower priority.
   // Reducing the boost of a tag affects future tasks but not current ones.
   void boost(llvm::StringRef Tag, unsigned NewPriority);
 
   // Process items on the queue until the queue is stopped.
   // If the queue becomes empty, OnIdle will be called (on one worker).
   void work(std::function<void()> OnIdle = nullptr);
 
   // Stop processing new tasks, allowing all work() calls to return soon.
   void stop();
 
   // Disables thread priority lowering to ensure progress on loaded systems.
   // Only affects tasks that run after the call.
   static void preventThreadStarvationInTests();
   LLVM_NODISCARD bool
   blockUntilIdleForTest(llvm::Optional<double> TimeoutSeconds);
 
 private:
+  void notifyProgress() const; // Requires lock Mu
+
   std::mutex Mu;
-  unsigned NumActiveTasks = 0; // Only idle when queue is empty *and* no tasks.
+  Stats Stat;
   std::condition_variable CV;
   bool ShouldStop = false;
   std::vector<Task> Queue; // max-heap
   llvm::StringMap<unsigned> Boosts;
+  std::function<void(Stats)> OnProgress;
 };
 
 // Builds an in-memory index by by running the static indexer action over
 // all commands in a compilation database. Indexing happens in the background.
 // FIXME: it should also persist its state on disk for fast start.
 // FIXME: it should watch for changes to files on disk.
 class BackgroundIndex : public SwapIndex {
 public:
   /// If BuildIndexPeriodMs is greater than 0, the symbol index will only be
   /// rebuilt periodically (one per \p BuildIndexPeriodMs); otherwise, index is
   /// rebuilt for each indexed file.
   BackgroundIndex(
       Context BackgroundContext, const FileSystemProvider &,
       const GlobalCompilationDatabase &CDB,
       BackgroundIndexStorage::Factory IndexStorageFactory,
-      size_t ThreadPoolSize = llvm::heavyweight_hardware_concurrency());
+      size_t ThreadPoolSize = llvm::heavyweight_hardware_concurrency(),
+      std::function<void(BackgroundQueue::Stats)> OnProgress = nullptr);
   ~BackgroundIndex(); // Blocks while the current task finishes.
 
   // Enqueue translation units for indexing.
   // The indexing happens in a background thread, so the symbols will be
   // available sometime later.
   void enqueue(const std::vector<std::string> &ChangedFiles) {
     Queue.push(changedFilesTask(ChangedFiles));
   }

clang-tools-extra/clangd/index/Background.cpp

bool shardIsStale(const LoadedShard &LS, llvm::vfs::FileSystem *FS) {
   return digest(Buf->get()->getBuffer()) != LS.Digest;
 }
 
 } // namespace
 
 BackgroundIndex::BackgroundIndex(
     Context BackgroundContext, const FileSystemProvider &FSProvider,
     const GlobalCompilationDatabase &CDB,
-    BackgroundIndexStorage::Factory IndexStorageFactory, size_t ThreadPoolSize)
-    : SwapIndex(std::make_unique<MemIndex>()), FSProvider(FSProvider),
-      CDB(CDB), BackgroundContext(std::move(BackgroundContext)),
+    BackgroundIndexStorage::Factory IndexStorageFactory, size_t ThreadPoolSize,
+    std::function<void(BackgroundQueue::Stats)> OnProgress)
+    : SwapIndex(std::make_unique<MemIndex>()), FSProvider(FSProvider), CDB(CDB),
+      BackgroundContext(std::move(BackgroundContext)),
       Rebuilder(this, &IndexedSymbols, ThreadPoolSize),
       IndexStorageFactory(std::move(IndexStorageFactory)),
+      Queue(std::move(OnProgress)),
       CommandsChanged(
           CDB.watch([&](const std::vector<std::string> &ChangedFiles) {
             enqueue(ChangedFiles);
           })) {
   assert(ThreadPoolSize > 0 && "Thread pool size can't be zero.");
   assert(this->IndexStorageFactory && "Storage factory can not be null!");
   for (unsigned I = 0; I < ThreadPoolSize; ++I) {
     ThreadPool.runAsync("background-worker-" + llvm::Twine(I + 1), [this] {

clang-tools-extra/clangd/index/BackgroundQueue.cpp

 //===-- BackgroundQueue.cpp - Task queue for background index -------------===//
 //
 // 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 "Logger.h"
 #include "index/Background.h"
 
 namespace clang {
 namespace clangd {
 
 static std::atomic<bool> PreventStarvation = {false};
 
 void BackgroundQueue::preventThreadStarvationInTests() {
   PreventStarvation.store(true);
 }
 
 void BackgroundQueue::work(std::function<void()> OnIdle) {
   while (true) {
     llvm::Optional<Task> Task;
     {
       std::unique_lock<std::mutex> Lock(Mu);
       CV.wait(Lock, [&] { return ShouldStop || !Queue.empty(); });
       if (ShouldStop) {
         Queue.clear();
         CV.notify_all();
         return;
       }
-      ++NumActiveTasks;
+      ++Stat.Active;
       std::pop_heap(Queue.begin(), Queue.end());
       Task = std::move(Queue.back());
       Queue.pop_back();
+      notifyProgress();
     }
 
     if (Task->ThreadPri != llvm::ThreadPriority::Default &&
         !PreventStarvation.load())
       llvm::set_thread_priority(Task->ThreadPri);
     Task->Run();
     if (Task->ThreadPri != llvm::ThreadPriority::Default)
       llvm::set_thread_priority(llvm::ThreadPriority::Default);
 
     {
       std::unique_lock<std::mutex> Lock(Mu);
-      if (NumActiveTasks == 1 && Queue.empty() && OnIdle) {
+      ++Stat.Completed;
+      if (Stat.Active == 1 && Queue.empty()) {
         // We just finished the last item, the queue is going idle.
+        assert(ShouldStop || Stat.Completed == Stat.Enqueued);
+        Stat.LastIdle = Stat.Completed;
+        if (OnIdle) {
           Lock.unlock();
           OnIdle();
           Lock.lock();
         }
-      assert(NumActiveTasks > 0 && "before decrementing");
-      --NumActiveTasks;
+      }
+      assert(Stat.Active > 0 && "before decrementing");
+      --Stat.Active;
+      notifyProgress();
     }
     CV.notify_all();
   }
 }
 
 void BackgroundQueue::stop() {
   {
     std::lock_guard<std::mutex> QueueLock(Mu);
     ShouldStop = true;
   }
   CV.notify_all();
 }
 
 void BackgroundQueue::push(Task T) {
   {
     std::lock_guard<std::mutex> Lock(Mu);
     T.QueuePri = std::max(T.QueuePri, Boosts.lookup(T.Tag));
     Queue.push_back(std::move(T));
     std::push_heap(Queue.begin(), Queue.end());
+    ++Stat.Enqueued;
+    notifyProgress();
   }
   CV.notify_all();
 }
 
 void BackgroundQueue::append(std::vector<Task> Tasks) {
   {
     std::lock_guard<std::mutex> Lock(Mu);
     for (Task &T : Tasks)
       T.QueuePri = std::max(T.QueuePri, Boosts.lookup(T.Tag));
     std::move(Tasks.begin(), Tasks.end(), std::back_inserter(Queue));
     std::make_heap(Queue.begin(), Queue.end());
+    Stat.Enqueued += Tasks.size();
+    notifyProgress();
   }
   CV.notify_all();
 }
 
 void BackgroundQueue::boost(llvm::StringRef Tag, unsigned NewPriority) {
   std::lock_guard<std::mutex> Lock(Mu);
   unsigned &Boost = Boosts[Tag];
   bool Increase = NewPriority > Boost;
if (Changes)
     std::make_heap(Queue.begin(), Queue.end());
   // No need to signal, only rearranged items in the queue.
 }
 
 bool BackgroundQueue::blockUntilIdleForTest(
     llvm::Optional<double> TimeoutSeconds) {
   std::unique_lock<std::mutex> Lock(Mu);
   return wait(Lock, CV, timeoutSeconds(TimeoutSeconds),
-              [&] { return Queue.empty() && NumActiveTasks == 0; });
+              [&] { return Queue.empty() && Stat.Active == 0; });
+}
+
+void BackgroundQueue::notifyProgress() const {
+  dlog("Queue: {0}/{1} ({2} active). Last idle at {3}", Stat.Completed,
+       Stat.Enqueued, Stat.Active, Stat.LastIdle);
+  if (OnProgress)
+    OnProgress(Stat);
 }
 
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/test/Inputs/background-index/definition.jsonrpc

 {
   "jsonrpc": "2.0",
   "id": 0,
   "method": "initialize",
   "params": {
     "processId": 123,
     "rootPath": "clangd",
-    "capabilities": {},
+    "capabilities": { "window": { "workDoneProgress": true, "implicitWorkDoneProgressCreate": true} },
     "trace": "off"
   }
 }
 ---
 {
   "jsonrpc": "2.0",
   "method": "textDocument/didOpen",
   "params": {
     "textDocument": {
       "uri": "file://DIRECTORY/bar.cpp",
       "languageId": "cpp",
       "version": 1,
       "text": "#include \"sub_dir/foo.h\"\nint main(){\nreturn foo();\n}"
     }
   }
 }
+# BUILD:      "method": "$/progress"
+# BUILD-NEXT: "params": {
+# BUILD-NEXT:   "token": "backgroundIndexProgress",
+# BUILD-NEXT:   "value": {
+# BUILD-NEXT:     "kind": "begin",
+# BUILD-NEXT:     "percentage": 0,
+# BUILD-NEXT:     "title": "indexing"
+# BUILD-NEXT:   }
+# BUILD-NEXT: }
+# BUILD:      "method": "$/progress"
+# BUILD-NEXT: "params": {
+# BUILD-NEXT:   "token": "backgroundIndexProgress",
+# BUILD-NEXT:   "value": {
+# BUILD-NEXT:     "kind": "report",
+# BUILD-NEXT:     "message": "0/1",
+# BUILD-NEXT:     "percentage": 0
+# BUILD-NEXT:   }
+# BUILD-NEXT: }
+#    later...
+# BUILD:          "message": "1/2",
+# BUILD-NEXT:     "percentage": 50
+#    finally...
+# BUILD:          "kind": "end"
+# when using the index, we spawn one task to read it, but not more.
+# USE-NOT:        "message": "1/2",
 ---
 {
   "jsonrpc": "2.0",
   "id": 1,
   "method": "sync",
   "params": null
 }
 ---

clang-tools-extra/clangd/test/background-index.test

 # We need to splice paths into file:// URIs for this test.
 # UNSUPPORTED: windows-msvc
 
 # Use a copy of inputs, as we'll mutate it (as will the background index).
 # RUN: rm -rf %t
 # RUN: cp -r %S/Inputs/background-index %t
 # Need to embed the correct temp path in the actual JSON-RPC requests.
 # RUN: sed -i -e "s|DIRECTORY|%t|" %t/definition.jsonrpc
 # RUN: sed -i -e "s|DIRECTORY|%t|" %t/compile_commands.json
 
 # We're editing bar.cpp, which includes foo.h.
 # foo() is declared in foo.h and defined in foo.cpp.
 # The background index should allow us to go-to-definition on foo().
-# RUN: clangd -background-index -lit-test < %t/definition.jsonrpc | FileCheck %t/definition.jsonrpc
+# We should also see indexing progress notifications.
+# RUN: clangd -background-index -lit-test < %t/definition.jsonrpc | FileCheck %t/definition.jsonrpc --check-prefixes=CHECK,BUILD
 
 # Test that the index is writing files in the expected location.
 # RUN: ls %t/.clangd/index/foo.cpp.*.idx
 # RUN: ls %t/sub_dir/.clangd/index/foo.h.*.idx
 
 # Test the index is read from disk: delete code and restart clangd.
 # RUN: rm %t/foo.cpp
-# RUN: clangd -background-index -lit-test < %t/definition.jsonrpc | FileCheck %t/definition.jsonrpc
+# RUN: clangd -background-index -lit-test < %t/definition.jsonrpc | FileCheck %t/definition.jsonrpc --check-prefixes=CHECK,USE

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

Sequence.clear();
     BackgroundQueue Q;
     Q.append({A, B});
     Q.boost("A", 3);
     Q.work([&] { Q.stop(); });
     EXPECT_EQ("AB", Sequence) << "A was boosted after enqueueing";
   }
 }
 
+TEST(BackgroundQueueTest, Progress) {
+  using testing::AnyOf;
+  BackgroundQueue::Stats S;
+  BackgroundQueue Q([&](BackgroundQueue::Stats New) {
+    // Verify values are sane.
+    // Items are enqueued one at a time (at least in this test).
+    EXPECT_THAT(New.Enqueued, AnyOf(S.Enqueued, S.Enqueued + 1));
+    // Items are completed one at a time.
+    EXPECT_THAT(New.Completed, AnyOf(S.Completed, S.Completed + 1));
+    // Items are started or completed one at a time.
+    EXPECT_THAT(New.Active, AnyOf(S.Active - 1, S.Active, S.Active + 1));
+    // Idle point only advances in time.
+    EXPECT_GE(New.LastIdle, S.LastIdle);
+    // Idle point is a task that has been completed in the past.
+    EXPECT_LE(New.LastIdle, New.Completed);
+    // LastIdle is now only if we're really idle.
+    EXPECT_EQ(New.LastIdle == New.Enqueued,
+              New.Completed == New.Enqueued && New.Active == 0u);
+    S = New;
+  });
+
+  // Two types of tasks: a ping task enqueues a pong task.
+  // This avoids all enqueues followed by all completions (boring!)
+  std::atomic<int> PingCount(0), PongCount(0);
+  BackgroundQueue::Task Pong([&] { ++PongCount; });
+  BackgroundQueue::Task Ping([&] {
+    ++PingCount;
+    Q.push(Pong);
+  });
+
+  for (int I = 0; I < 1000; ++I)
+    Q.push(Ping);
+  // Spin up some workers and stop while idle.
+  AsyncTaskRunner ThreadPool;
+  for (unsigned I = 0; I < 5; ++I)
+    ThreadPool.runAsync("worker", [&] { Q.work([&] { Q.stop(); }); });
+  ThreadPool.wait();
+
+  // Everything's done, check final stats.
+  // Assertions above ensure we got from 0 to 2000 in a reasonable way.
+  EXPECT_EQ(PingCount.load(), 1000);
+  EXPECT_EQ(PongCount.load(), 1000);
+  EXPECT_EQ(S.Active, 0u);
+  EXPECT_EQ(S.Enqueued, 2000u);
+  EXPECT_EQ(S.Completed, 2000u);
+  EXPECT_EQ(S.LastIdle, 2000u);
+}
+
 } // namespace clangd
 } // namespace clang

llvm/include/llvm/Support/JSON.h

 }
 inline bool fromJSON(const Value &E, bool &Out) {
   if (auto S = E.getAsBoolean()) {
     Out = *S;
     return true;
   }
   return false;
 }
+inline bool fromJSON(const Value &E, std::nullptr_t &Out) {
+  if (auto S = E.getAsNull()) {
+    Out = *S;
+    return true;
+  }
+  return false;
+}
 template <typename T> bool fromJSON(const Value &E, llvm::Optional<T> &Out) {
   if (E.getAsNull()) {
     Out = llvm::None;
     return true;
   }
   T Result;
   if (!fromJSON(E, Result))
     return false;