clang-tools-extra/clangd/TUScheduler.h

   1 //===--- TUScheduler.h -------------------------------------------*-C++-*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_TUSCHEDULER_H
  10 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_TUSCHEDULER_H
  11
  12 #include "ASTSignals.h"
  13 #include "Compiler.h"
  14 #include "Diagnostics.h"
  15 #include "GlobalCompilationDatabase.h"
  16 #include "index/CanonicalIncludes.h"
  17 #include "support/Function.h"
  18 #include "support/MemoryTree.h"
  19 #include "support/Path.h"
  20 #include "support/Threading.h"
  21 #include "llvm/ADT/Optional.h"
  22 #include "llvm/ADT/StringMap.h"
  23 #include "llvm/ADT/StringRef.h"
  24 #include <chrono>
  25 #include <string>
  26
  27 namespace clang {
  28 namespace clangd {
  29 class ParsedAST;
  30 struct PreambleData;
  31
  32 /// Returns a number of a default async threads to use for TUScheduler.
  33 /// Returned value is always >= 1 (i.e. will not cause requests to be processed
  34 /// synchronously).
  35 unsigned getDefaultAsyncThreadsCount();
  36
  37 struct InputsAndAST {
  38   const ParseInputs &Inputs;
  39   ParsedAST &AST;
  40 };
  41
  42 struct InputsAndPreamble {
  43   llvm::StringRef Contents;
  44   const tooling::CompileCommand &Command;
  45   // This can be nullptr if no preamble is available.
  46   const PreambleData *Preamble;
  47   // This can be nullptr if no ASTSignals are available.
  48   const ASTSignals *Signals;
  49 };
  50
  51 /// Determines whether diagnostics should be generated for a file snapshot.
  52 enum class WantDiagnostics {
  53   Yes,  /// Diagnostics must be generated for this snapshot.
  54   No,   /// Diagnostics must not be generated for this snapshot.
  55   Auto, /// Diagnostics must be generated for this snapshot or a subsequent one,
  56         /// within a bounded amount of time.
  57 };
  58
  59 /// Configuration of the AST retention policy. This only covers retention of
  60 /// *idle* ASTs. If queue has operations requiring the AST, they might be
  61 /// kept in memory.
  62 struct ASTRetentionPolicy {
  63   /// Maximum number of ASTs to be retained in memory when there are no pending
  64   /// requests for them.
  65   unsigned MaxRetainedASTs = 3;
  66 };
  67
  68 /// Clangd may wait after an update to see if another one comes along.
  69 /// This is so we rebuild once the user stops typing, not when they start.
  70 /// Debounce may be disabled/interrupted if we must build this version.
  71 /// The debounce time is responsive to user preferences and rebuild time.
  72 /// In the future, we could also consider different types of edits.
  73 struct DebouncePolicy {
  74   using clock = std::chrono::steady_clock;
  75
  76   /// The minimum time that we always debounce for.
  77   clock::duration Min = /*zero*/ {};
  78   /// The maximum time we may debounce for.
  79   clock::duration Max = /*zero*/ {};
  80   /// Target debounce, as a fraction of file rebuild time.
  81   /// e.g. RebuildRatio = 2, recent builds took 200ms => debounce for 400ms.
  82   float RebuildRatio = 1;
  83
  84   /// Compute the time to debounce based on this policy and recent build times.
  85   clock::duration compute(llvm::ArrayRef<clock::duration> History) const;
  86   /// A policy that always returns the same duration, useful for tests.
  87   static DebouncePolicy fixed(clock::duration);
  88 };
  89
  90 /// PreambleThrottler controls which preambles can build at any given time.
  91 /// This can be used to limit overall concurrency, and to prioritize some
  92 /// preambles over others.
  93 /// In a distributed environment, a throttler may be able to coordinate resource
  94 /// use across several clangd instances.
  95 ///
  96 /// This class is threadsafe.
  97 class PreambleThrottler {
  98 public:
  99   virtual ~PreambleThrottler() = default;
 100
 101   using RequestID = unsigned;
 102   using Callback = llvm::unique_function<void()>;
 103   /// Attempt to acquire resources to build a file's preamble.
 104   ///
 105   /// Does not block, may eventually invoke the callback to satisfy the request.
 106   /// If the callback is invoked, release() must be called afterwards.
 107   virtual RequestID acquire(llvm::StringRef Filename, Callback) = 0;
 108   /// Abandons the request/releases any resources that have been acquired.
 109   ///
 110   /// Must be called exactly once after acquire().
 111   /// acquire()'s callback will not be invoked after release() returns.
 112   virtual void release(RequestID) = 0;
 113
 114   // FIXME: we may want to be able attach signals to filenames.
 115   //        this would allow the throttler to make better scheduling decisions.
 116 };
 117
 118 enum class PreambleAction {
 119   Queued,
 120   Building,
 121   Idle,
 122 };
 123
 124 struct ASTAction {
 125   enum Kind {
 126     Queued,        // The action is pending in the thread task queue to be run.
 127     RunningAction, // Started running actions on the TU.
 128     Building,      // The AST is being built.
 129     Idle, // Indicates the worker thread is idle, and ready to run any upcoming
 130           // actions.
 131   };
 132   ASTAction() = default;
 133   ASTAction(Kind K, llvm::StringRef Name) : K(K), Name(Name) {}
 134   Kind K = ASTAction::Idle;
 135   /// The name of the action currently running, e.g. Update, GoToDef, Hover.
 136   /// Empty if we are in the idle state.
 137   std::string Name;
 138 };
 139
 140 // Internal status of the TU in TUScheduler.
 141 struct TUStatus {
 142   struct BuildDetails {
 143     /// Indicates whether clang failed to build the TU.
 144     bool BuildFailed = false;
 145     /// Indicates whether we reused the prebuilt AST.
 146     bool ReuseAST = false;
 147   };
 148   /// Serialize this to an LSP file status item.
 149   FileStatus render(PathRef File) const;
 150
 151   PreambleAction PreambleActivity = PreambleAction::Idle;
 152   ASTAction ASTActivity;
 153   /// Stores status of the last build for the translation unit.
 154   BuildDetails Details;
 155 };
 156
 157 class ParsingCallbacks {
 158 public:
 159   virtual ~ParsingCallbacks() = default;
 160
 161   /// Called on the AST that was built for emitting the preamble. The built AST
 162   /// contains only AST nodes from the #include directives at the start of the
 163   /// file. AST node in the current file should be observed on onMainAST call.
 164   virtual void onPreambleAST(PathRef Path, llvm::StringRef Version,
 165                              const CompilerInvocation &CI, ASTContext &Ctx,
 166                              Preprocessor &PP, const CanonicalIncludes &) {}
 167
 168   /// The argument function is run under the critical section guarding against
 169   /// races when closing the files.
 170   using PublishFn = llvm::function_ref<void(llvm::function_ref<void()>)>;
 171   /// Called on the AST built for the file itself. Note that preamble AST nodes
 172   /// are not deserialized and should be processed in the onPreambleAST call
 173   /// instead.
 174   /// The \p AST always contains all AST nodes for the main file itself, and
 175   /// only a portion of the AST nodes deserialized from the preamble. Note that
 176   /// some nodes from the preamble may have been deserialized and may also be
 177   /// accessed from the main file AST, e.g. redecls of functions from preamble,
 178   /// etc. Clients are expected to process only the AST nodes from the main file
 179   /// in this callback (obtained via ParsedAST::getLocalTopLevelDecls) to obtain
 180   /// optimal performance.
 181   ///
 182   /// When information about the file (e.g. diagnostics) is
 183   /// published to clients, this should be wrapped in Publish, e.g.
 184   ///   void onMainAST(...) {
 185   ///     Diags = renderDiagnostics();
 186   ///     Publish([&] { notifyDiagnostics(Path, Diags); });
 187   ///   }
 188   /// This guarantees that clients will see results in the correct sequence if
 189   /// the file is concurrently closed and/or reopened. (The lambda passed to
 190   /// Publish() may never run in this case).
 191   virtual void onMainAST(PathRef Path, ParsedAST &AST, PublishFn Publish) {}
 192
 193   /// Called whenever the AST fails to build. \p Diags will have the diagnostics
 194   /// that led to failure.
 195   virtual void onFailedAST(PathRef Path, llvm::StringRef Version,
 196                            std::vector<Diag> Diags, PublishFn Publish) {}
 197
 198   /// Called whenever the TU status is updated.
 199   virtual void onFileUpdated(PathRef File, const TUStatus &Status) {}
 200
 201   /// Preamble for the TU have changed. This might imply new semantics (e.g.
 202   /// different highlightings). Any actions on the file are guranteed to see new
 203   /// preamble after the callback.
 204   virtual void onPreamblePublished(PathRef File) {}
 205 };
 206
 207 /// Handles running tasks for ClangdServer and managing the resources (e.g.,
 208 /// preambles and ASTs) for opened files.
 209 /// TUScheduler is not thread-safe, only one thread should be providing updates
 210 /// and scheduling tasks.
 211 /// Callbacks are run on a threadpool and it's appropriate to do slow work in
 212 /// them. Each task has a name, used for tracing (should be UpperCamelCase).
 213 class TUScheduler {
 214 public:
 215   struct Options {
 216     /// Number of concurrent actions.
 217     /// Governs per-file worker threads and threads spawned for other tasks.
 218     /// (This does not prevent threads being spawned, but rather blocks them).
 219     /// If 0, executes actions synchronously on the calling thread.
 220     unsigned AsyncThreadsCount = getDefaultAsyncThreadsCount();
 221
 222     /// Cache (large) preamble data in RAM rather than temporary files on disk.
 223     bool StorePreamblesInMemory = false;
 224
 225     /// Time to wait after an update to see if another one comes along.
 226     /// This tries to ensure we rebuild once the user stops typing.
 227     DebouncePolicy UpdateDebounce;
 228
 229     /// Determines when to keep idle ASTs in memory for future use.
 230     ASTRetentionPolicy RetentionPolicy;
 231
 232     /// This throttler controls which preambles may be built at a given time.
 233     clangd::PreambleThrottler *PreambleThrottler = nullptr;
 234
 235     /// Used to create a context that wraps each single operation.
 236     /// Typically to inject per-file configuration.
 237     /// If the path is empty, context sholud be "generic".
 238     std::function<Context(PathRef)> ContextProvider;
 239   };
 240
 241   TUScheduler(const GlobalCompilationDatabase &CDB, const Options &Opts,
 242               std::unique_ptr<ParsingCallbacks> ASTCallbacks = nullptr);
 243   ~TUScheduler();
 244
 245   struct FileStats {
 246     std::size_t UsedBytesAST = 0;
 247     std::size_t UsedBytesPreamble = 0;
 248     unsigned PreambleBuilds = 0;
 249     unsigned ASTBuilds = 0;
 250   };
 251   /// Returns resources used for each of the currently open files.
 252   /// Results are inherently racy as they measure activity of other threads.
 253   llvm::StringMap<FileStats> fileStats() const;
 254
 255   /// Returns a list of files with ASTs currently stored in memory. This method
 256   /// is not very reliable and is only used for test. E.g., the results will not
 257   /// contain files that currently run something over their AST.
 258   std::vector<Path> getFilesWithCachedAST() const;
 259
 260   /// Schedule an update for \p File.
 261   /// The compile command in \p Inputs is ignored; worker queries CDB to get
 262   /// the actual compile command.
 263   /// If diagnostics are requested (Yes), and the context is cancelled
 264   /// before they are prepared, they may be skipped if eventual-consistency
 265   /// permits it (i.e. WantDiagnostics is downgraded to Auto).
 266   /// Returns true if the file was not previously tracked.
 267   bool update(PathRef File, ParseInputs Inputs, WantDiagnostics WD);
 268
 269   /// Remove \p File from the list of tracked files and schedule removal of its
 270   /// resources. Pending diagnostics for closed files may not be delivered, even
 271   /// if requested with WantDiags::Auto or WantDiags::Yes.
 272   void remove(PathRef File);
 273
 274   /// Schedule an async task with no dependencies.
 275   /// Path may be empty (it is used only to set the Context).
 276   void run(llvm::StringRef Name, llvm::StringRef Path,
 277            llvm::unique_function<void()> Action);
 278
 279   /// Similar to run, except the task is expected to be quick.
 280   /// This function will not honor AsyncThreadsCount (except
 281   /// if threading is disabled with AsyncThreadsCount=0)
 282   /// It is intended to run quick tasks that need to run ASAP
 283   void runQuick(llvm::StringRef Name, llvm::StringRef Path,
 284                 llvm::unique_function<void()> Action);
 285
 286   /// Defines how a runWithAST action is implicitly cancelled by other actions.
 287   enum ASTActionInvalidation {
 288     /// The request will run unless explicitly cancelled.
 289     NoInvalidation,
 290     /// The request will be implicitly cancelled by a subsequent update().
 291     /// (Only if the request was not yet cancelled).
 292     /// Useful for requests that are generated by clients, without any explicit
 293     /// user action. These can otherwise e.g. force every version to be built.
 294     InvalidateOnUpdate,
 295   };
 296
 297   /// Schedule an async read of the AST. \p Action will be called when AST is
 298   /// ready. The AST passed to \p Action refers to the version of \p File
 299   /// tracked at the time of the call, even if new updates are received before
 300   /// \p Action is executed.
 301   /// If an error occurs during processing, it is forwarded to the \p Action
 302   /// callback.
 303   /// If the context is cancelled before the AST is ready, or the invalidation
 304   /// policy is triggered, the callback will receive a CancelledError.
 305   void runWithAST(llvm::StringRef Name, PathRef File,
 306                   Callback<InputsAndAST> Action,
 307                   ASTActionInvalidation = NoInvalidation);
 308
 309   /// Controls whether preamble reads wait for the preamble to be up-to-date.
 310   enum PreambleConsistency {
 311     /// The preamble may be generated from an older version of the file.
 312     /// Reading from locations in the preamble may cause files to be re-read.
 313     /// This gives callers two options:
 314     /// - validate that the preamble is still valid, and only use it if so
 315     /// - accept that the preamble contents may be outdated, and try to avoid
 316     ///   reading source code from headers.
 317     /// This is the fastest option, usually a preamble is available immediately.
 318     Stale,
 319     /// Besides accepting stale preamble, this also allow preamble to be absent
 320     /// (not ready or failed to build).
 321     StaleOrAbsent,
 322   };
 323
 324   /// Schedule an async read of the preamble.
 325   /// If there's no up-to-date preamble, we follow the PreambleConsistency
 326   /// policy.
 327   /// If an error occurs, it is forwarded to the \p Action callback.
 328   /// Context cancellation is ignored and should be handled by the Action.
 329   /// (In practice, the Action is almost always executed immediately).
 330   void runWithPreamble(llvm::StringRef Name, PathRef File,
 331                        PreambleConsistency Consistency,
 332                        Callback<InputsAndPreamble> Action);
 333
 334   /// Wait until there are no scheduled or running tasks.
 335   /// Mostly useful for synchronizing tests.
 336   bool blockUntilIdle(Deadline D) const;
 337
 338 private:
 339   /// This class stores per-file data in the Files map.
 340   struct FileData;
 341
 342 public:
 343   /// Responsible for retaining and rebuilding idle ASTs. An implementation is
 344   /// an LRU cache.
 345   class ASTCache;
 346   /// Tracks headers included by open files, to get known-good compile commands.
 347   class HeaderIncluderCache;
 348
 349   // The file being built/processed in the current thread. This is a hack in
 350   // order to get the file name into the index implementations. Do not depend on
 351   // this inside clangd.
 352   // FIXME: remove this when there is proper index support via build system
 353   // integration.
 354   // FIXME: move to ClangdServer via createProcessingContext.
 355   static llvm::Optional<llvm::StringRef> getFileBeingProcessedInContext();
 356
 357   void profile(MemoryTree &MT) const;
 358
 359 private:
 360   void runWithSemaphore(llvm::StringRef Name, llvm::StringRef Path,
 361                         llvm::unique_function<void()> Action, Semaphore &Sem);
 362
 363   const GlobalCompilationDatabase &CDB;
 364   Options Opts;
 365   std::unique_ptr<ParsingCallbacks> Callbacks; // not nullptr
 366   Semaphore Barrier;
 367   Semaphore QuickRunBarrier;
 368   llvm::StringMap<std::unique_ptr<FileData>> Files;
 369   std::unique_ptr<ASTCache> IdleASTs;
 370   std::unique_ptr<HeaderIncluderCache> HeaderIncluders;
 371   // None when running tasks synchronously and non-None when running tasks
 372   // asynchronously.
 373   llvm::Optional<AsyncTaskRunner> PreambleTasks;
 374   llvm::Optional<AsyncTaskRunner> WorkerThreads;
 375   // Used to create contexts for operations that are not bound to a particular
 376   // file (e.g. index queries).
 377   std::string LastActiveFile;
 378 };
 379
 380 } // namespace clangd
 381 } // namespace clang
 382
 383 #endif