TUScheduler.cpp | Explore in Territory

//===--- TUScheduler.cpp -----------------------------------------*-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
//
//===----------------------------------------------------------------------===//
// TUScheduler manages a worker per active file. This ASTWorker processes
// updates (modifications to file contents) and reads (actions performed on
// preamble/AST) to the file.
//
// Each ASTWorker owns a dedicated thread to process updates and reads to the
// relevant file. Any request gets queued in FIFO order to be processed by that
// thread.
//
// An update request replaces current praser inputs to ensure any subsequent
// read sees the version of the file they were requested. It will also issue a
// build for new inputs.
//
// ASTWorker processes the file in two parts, a preamble and a main-file
// section. A preamble can be reused between multiple versions of the file until
// invalidated by a modification to a header, compile commands or modification
// to relevant part of the current file. Such a preamble is called compatible.
// An update is considered dead if no read was issued for that version and
// diagnostics weren't requested by client or could be generated for a later
// version of the file. ASTWorker eliminates such requests as they are
// redundant.
//
// In the presence of stale (non-compatible) preambles, ASTWorker won't publish
// diagnostics for update requests. Read requests will be served with ASTs build
// with stale preambles, unless the read is picky and requires a compatible
// preamble. In such cases it will block until new preamble is built.
//
// ASTWorker owns a PreambleThread for building preambles. If the preamble gets
// invalidated by an update request, a new build will be requested on
// PreambleThread. Since PreambleThread only receives requests for newer
// versions of the file, in case of multiple requests it will only build the
// last one and skip requests in between. Unless client force requested
// diagnostics(WantDiagnostics::Yes).
//
// When a new preamble is built, a "golden" AST is immediately built from that
// version of the file. This ensures diagnostics get updated even if the queue
// is full.
//
// Some read requests might just need preamble. Since preambles can be read
// concurrently, ASTWorker runs these requests on their own thread. These
// requests will receive latest build preamble, which might possibly be stale.

#include "TUScheduler.h"
#include "CompileCommands.h"
#include "Compiler.h"
#include "Config.h"
#include "Diagnostics.h"
#include "GlobalCompilationDatabase.h"
#include "ParsedAST.h"
#include "Preamble.h"
#include "clang-include-cleaner/Record.h"
#include "support/Cancellation.h"
#include "support/Context.h"
#include "support/Logger.h"
#include "support/MemoryTree.h"
#include "support/Path.h"
#include "support/ThreadCrashReporter.h"
#include "support/Threading.h"
#include "support/Trace.h"
#include "clang/Basic/Stack.h"
#include "clang/Frontend/CompilerInvocation.h"
#include "clang/Tooling/CompilationDatabase.h"
#include "llvm/ADT/FunctionExtras.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/ScopeExit.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/Errc.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/FormatVariadic.h"
#include "llvm/Support/Path.h"
#include "llvm/Support/Threading.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <functional>
#include <memory>
#include <mutex>
#include <optional>
#include <queue>
#include <string>
#include <thread>
#include <type_traits>
#include <utility>
#include <vector>

namespace clang {
namespace clangd {
steady_clock;

namespace {
// Tracks latency (in seconds) of FS operations done during a preamble build.
// build_type allows to split by expected VFS cache state (cold on first
// preamble, somewhat warm after that when building first preamble for new file,
// likely ~everything cached on preamble rebuild.
constexpr trace::Metric
    PreambleBuildFilesystemLatency("preamble_fs_latency",
                                   trace::Metric::Distribution, "build_type");
// Tracks latency of FS operations done during a preamble build as a ratio of
// preamble build time. build_type is same as above.
constexpr trace::Metric PreambleBuildFilesystemLatencyRatio(
    "preamble_fs_latency_ratio", trace::Metric::Distribution, "build_type");

constexpr trace::Metric PreambleBuildSize("preamble_build_size",
                                          trace::Metric::Distribution);
constexpr trace::Metric PreambleSerializedSize("preamble_serialized_size",
                                               trace::Metric::Distribution);

void reportPreambleBuild(const PreambleBuildStats &Stats,
                         bool IsFirstPreamble) { … }

class ASTWorker;
} // namespace

static clang::clangd::Key<std::string> FileBeingProcessed;

std::optional<llvm::StringRef> TUScheduler::getFileBeingProcessedInContext() { … }

/// An LRU cache of idle ASTs.
/// Because we want to limit the overall number of these we retain, the cache
/// owns ASTs (and may evict them) while their workers are idle.
/// Workers borrow ASTs when active, and return them when done.
class TUScheduler::ASTCache { … };

/// A map from header files to an opened "proxy" file that includes them.
/// If you open the header, the compile command from the proxy file is used.
///
/// This inclusion information could also naturally live in the index, but there
/// are advantages to using open files instead:
///  - it's easier to achieve a *stable* choice of proxy, which is important
///    to avoid invalidating the preamble
///  - context-sensitive flags for libraries with multiple configurations
///    (e.g. C++ stdlib sensitivity to -std version)
///  - predictable behavior, e.g. guarantees that go-to-def landing on a header
///    will have a suitable command available
///  - fewer scaling problems to solve (project include graphs are big!)
///
/// Implementation details:
/// - We only record this for mainfiles where the command was trustworthy
///   (i.e. not inferred). This avoids a bad inference "infecting" other files.
/// - Once we've picked a proxy file for a header, we stick with it until the
///   proxy file is invalidated *and* a new candidate proxy file is built.
///   Switching proxies is expensive, as the compile flags will (probably)
///   change and therefore we'll end up rebuilding the header's preamble.
/// - We don't capture the actual compile command, but just the filename we
///   should query to get it. This avoids getting out of sync with the CDB.
///
/// All methods are threadsafe. In practice, update() comes from preamble
/// threads, remove()s mostly from the main thread, and get() from ASTWorker.
/// Writes are rare and reads are cheap, so we don't expect much contention.
class TUScheduler::HeaderIncluderCache { … };

namespace {

bool isReliable(const tooling::CompileCommand &Cmd) { … }

/// Threadsafe manager for updating a TUStatus and emitting it after each
/// update.
class SynchronizedTUStatus { … };

// An attempt to acquire resources for a task using PreambleThrottler.
// Initially it is unsatisfied, it (hopefully) becomes satisfied later but may
// be destroyed before then. Destruction releases all resources.
class PreambleThrottlerRequest { … };

/// Responsible for building preambles. Whenever the thread is idle and the
/// preamble is outdated, it starts to build a fresh preamble from the latest
/// inputs. If RunSync is true, preambles are built synchronously in update()
/// instead.
class PreambleThread { … };

class ASTWorkerHandle;

/// Owns one instance of the AST, schedules updates and reads of it.
/// Also responsible for building and providing access to the preamble.
/// Each ASTWorker processes the async requests sent to it on a separate
/// dedicated thread.
/// The ASTWorker that manages the AST is shared by both the processing thread
/// and the TUScheduler. The TUScheduler should discard an ASTWorker when
/// remove() is called, but its thread may be busy and we don't want to block.
/// So the workers are accessed via an ASTWorkerHandle. Destroying the handle
/// signals the worker to exit its run loop and gives up shared ownership of the
/// worker.
class ASTWorker { … };

/// A smart-pointer-like class that points to an active ASTWorker.
/// In destructor, signals to the underlying ASTWorker that no new requests will
/// be sent and the processing loop may exit (after running all pending
/// requests).
class ASTWorkerHandle { … };

ASTWorkerHandle
ASTWorker::create(PathRef FileName, const GlobalCompilationDatabase &CDB,
                  TUScheduler::ASTCache &IdleASTs,
                  TUScheduler::HeaderIncluderCache &HeaderIncluders,
                  AsyncTaskRunner *Tasks, Semaphore &Barrier,
                  const TUScheduler::Options &Opts,
                  ParsingCallbacks &Callbacks) { … }

ASTWorker::ASTWorker(PathRef FileName, const GlobalCompilationDatabase &CDB,
                     TUScheduler::ASTCache &LRUCache,
                     TUScheduler::HeaderIncluderCache &HeaderIncluders,
                     Semaphore &Barrier, bool RunSync,
                     const TUScheduler::Options &Opts,
                     ParsingCallbacks &Callbacks)
    : … { … }

ASTWorker::~ASTWorker() { … }

void ASTWorker::update(ParseInputs Inputs, WantDiagnostics WantDiags,
                       bool ContentChanged) { … }

void ASTWorker::runWithAST(
    llvm::StringRef Name,
    llvm::unique_function<void(llvm::Expected<InputsAndAST>)> Action,
    TUScheduler::ASTActionInvalidation Invalidation) { … }

/// To be called from ThreadCrashReporter's signal handler.
static void crashDumpCompileCommand(llvm::raw_ostream &OS,
                                    const tooling::CompileCommand &Command) { … }

/// To be called from ThreadCrashReporter's signal handler.
static void crashDumpFileContents(llvm::raw_ostream &OS,
                                  const std::string &Contents) { … }

/// To be called from ThreadCrashReporter's signal handler.
static void crashDumpParseInputs(llvm::raw_ostream &OS,
                                 const ParseInputs &FileInputs) { … }

void PreambleThread::build(Request Req) { … }

void ASTWorker::updatePreamble(std::unique_ptr<CompilerInvocation> CI,
                               ParseInputs PI,
                               std::shared_ptr<const PreambleData> Preamble,
                               std::vector<Diag> CIDiags,
                               WantDiagnostics WantDiags) { … }

void ASTWorker::updateASTSignals(ParsedAST &AST) { … }

void ASTWorker::generateDiagnostics(
    std::unique_ptr<CompilerInvocation> Invocation, ParseInputs Inputs,
    std::vector<Diag> CIDiags) { … }

std::shared_ptr<const PreambleData> ASTWorker::getPossiblyStalePreamble(
    std::shared_ptr<const ASTSignals> *ASTSignals) const { … }

void ASTWorker::waitForFirstPreamble() const { … }

tooling::CompileCommand ASTWorker::getCurrentCompileCommand() const { … }

TUScheduler::FileStats ASTWorker::stats() const { … }

bool ASTWorker::isASTCached() const { … }

void ASTWorker::stop() { … }

void ASTWorker::runTask(llvm::StringRef Name, llvm::function_ref<void()> Task) { … }

void ASTWorker::startTask(llvm::StringRef Name,
                          llvm::unique_function<void()> Task,
                          std::optional<UpdateType> Update,
                          TUScheduler::ASTActionInvalidation Invalidation) { … }

void ASTWorker::run() { … }

Deadline ASTWorker::scheduleLocked() { … }

// Returns true if Requests.front() is a dead update that can be skipped.
bool ASTWorker::shouldSkipHeadLocked() const { … }

bool ASTWorker::blockUntilIdle(Deadline Timeout) const { … }

// Render a TUAction to a user-facing string representation.
// TUAction represents clangd-internal states, we don't intend to expose them
// to users (say C++ programmers) directly to avoid confusion, we use terms that
// are familiar by C++ programmers.
std::string renderTUAction(const PreambleAction PA, const ASTAction &AA) { … }

} // namespace

unsigned getDefaultAsyncThreadsCount() { … }

FileStatus TUStatus::render(PathRef File) const { … }

struct TUScheduler::FileData { … };

TUScheduler::TUScheduler(const GlobalCompilationDatabase &CDB,
                         const Options &Opts,
                         std::unique_ptr<ParsingCallbacks> Callbacks)
    : … { … }

TUScheduler::~TUScheduler() { … }

bool TUScheduler::blockUntilIdle(Deadline D) const { … }

bool TUScheduler::update(PathRef File, ParseInputs Inputs,
                         WantDiagnostics WantDiags) { … }

void TUScheduler::remove(PathRef File) { … }

void TUScheduler::run(llvm::StringRef Name, llvm::StringRef Path,
                      llvm::unique_function<void()> Action) { … }

void TUScheduler::runQuick(llvm::StringRef Name, llvm::StringRef Path,
                           llvm::unique_function<void()> Action) { … }

void TUScheduler::runWithSemaphore(llvm::StringRef Name, llvm::StringRef Path,
                                   llvm::unique_function<void()> Action,
                                   Semaphore &Sem) { … }

void TUScheduler::runWithAST(
    llvm::StringRef Name, PathRef File,
    llvm::unique_function<void(llvm::Expected<InputsAndAST>)> Action,
    TUScheduler::ASTActionInvalidation Invalidation) { … }

void TUScheduler::runWithPreamble(llvm::StringRef Name, PathRef File,
                                  PreambleConsistency Consistency,
                                  Callback<InputsAndPreamble> Action) { … }

llvm::StringMap<TUScheduler::FileStats> TUScheduler::fileStats() const { … }

std::vector<Path> TUScheduler::getFilesWithCachedAST() const { … }

DebouncePolicy::clock::duration
DebouncePolicy::compute(llvm::ArrayRef<clock::duration> History) const { … }

DebouncePolicy DebouncePolicy::fixed(clock::duration T) { … }

void TUScheduler::profile(MemoryTree &MT) const { … }
} // namespace clangd
} // namespace clang
llvm/clang-tools-extra/clangd/TUScheduler.cpp
