diff options
15 files changed, 359 insertions, 225 deletions
diff --git a/clang-tools-extra/clangd/CMakeLists.txt b/clang-tools-extra/clangd/CMakeLists.txt index ad50a4be9f2..f617f7931de 100644 --- a/clang-tools-extra/clangd/CMakeLists.txt +++ b/clang-tools-extra/clangd/CMakeLists.txt @@ -73,6 +73,7 @@ add_clang_library(clangDaemon XRefs.cpp index/Background.cpp + index/BackgroundIndexLoader.cpp index/BackgroundIndexStorage.cpp index/BackgroundQueue.cpp index/BackgroundRebuild.cpp diff --git a/clang-tools-extra/clangd/ClangdServer.cpp b/clang-tools-extra/clangd/ClangdServer.cpp index 10949ef001c..7e77e18725a 100644 --- a/clang-tools-extra/clangd/ClangdServer.cpp +++ b/clang-tools-extra/clangd/ClangdServer.cpp @@ -127,7 +127,8 @@ ClangdServer::ClangdServer(const GlobalCompilationDatabase &CDB, if (Opts.BackgroundIndex) { BackgroundIdx = llvm::make_unique<BackgroundIndex>( Context::current().clone(), FSProvider, CDB, - BackgroundIndexStorage::createDiskBackedStorageFactory()); + BackgroundIndexStorage::createDiskBackedStorageFactory( + [&CDB](llvm::StringRef File) { return CDB.getProjectInfo(File); })); AddIndex(BackgroundIdx.get()); } if (DynamicIdx) diff --git a/clang-tools-extra/clangd/index/Background.cpp b/clang-tools-extra/clangd/index/Background.cpp index 23445e16b2f..a9e28f8de99 100644 --- a/clang-tools-extra/clangd/index/Background.cpp +++ b/clang-tools-extra/clangd/index/Background.cpp @@ -10,6 +10,7 @@ #include "ClangdUnit.h" #include "Compiler.h" #include "Context.h" +#include "FSProvider.h" #include "Headers.h" #include "Logger.h" #include "Path.h" @@ -18,6 +19,7 @@ #include "Threading.h" #include "Trace.h" #include "URI.h" +#include "index/BackgroundIndexLoader.h" #include "index/FileIndex.h" #include "index/IndexAction.h" #include "index/MemIndex.h" @@ -28,6 +30,8 @@ #include "clang/Basic/SourceLocation.h" #include "clang/Basic/SourceManager.h" #include "clang/Driver/Types.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/DenseSet.h" #include "llvm/ADT/Hashing.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/ScopeExit.h" @@ -42,6 +46,7 @@ #include <atomic> #include <chrono> #include <condition_variable> +#include <cstddef> #include <memory> #include <mutex> #include <numeric> @@ -49,6 +54,8 @@ #include <random> #include <string> #include <thread> +#include <utility> +#include <vector> namespace clang { namespace clangd { @@ -119,6 +126,18 @@ llvm::SmallString<128> getAbsolutePath(const tooling::CompileCommand &Cmd) { } return AbsolutePath; } + +bool shardIsStale(const LoadedShard &LS, llvm::vfs::FileSystem *FS) { + auto Buf = FS->getBufferForFile(LS.AbsolutePath); + if (!Buf) { + elog("Background-index: Couldn't read {0} to validate stored index: {1}", + LS.AbsolutePath, Buf.getError().message()); + // There is no point in indexing an unreadable file. + return false; + } + return digest(Buf->get()->getBuffer()) != LS.Digest; +} + } // namespace BackgroundIndex::BackgroundIndex( @@ -156,14 +175,14 @@ BackgroundQueue::Task BackgroundIndex::changedFilesTask( log("Enqueueing {0} commands for indexing", ChangedFiles.size()); SPAN_ATTACH(Tracer, "files", int64_t(ChangedFiles.size())); - auto NeedsReIndexing = loadShards(std::move(ChangedFiles)); + auto NeedsReIndexing = loadProject(std::move(ChangedFiles)); // Run indexing for files that need to be updated. std::shuffle(NeedsReIndexing.begin(), NeedsReIndexing.end(), std::mt19937(std::random_device{}())); std::vector<BackgroundQueue::Task> Tasks; Tasks.reserve(NeedsReIndexing.size()); - for (auto &Elem : NeedsReIndexing) - Tasks.push_back(indexFileTask(std::move(Elem.first), Elem.second)); + for (auto &Cmd : NeedsReIndexing) + Tasks.push_back(indexFileTask(std::move(Cmd))); Queue.append(std::move(Tasks)); }); @@ -178,13 +197,12 @@ static llvm::StringRef filenameWithoutExtension(llvm::StringRef Path) { } BackgroundQueue::Task -BackgroundIndex::indexFileTask(tooling::CompileCommand Cmd, - BackgroundIndexStorage *Storage) { - BackgroundQueue::Task T([this, Storage, Cmd] { +BackgroundIndex::indexFileTask(tooling::CompileCommand Cmd) { + BackgroundQueue::Task T([this, Cmd] { // We can't use llvm::StringRef here since we are going to // move from Cmd during the call below. const std::string FileName = Cmd.Filename; - if (auto Error = index(std::move(Cmd), Storage)) + if (auto Error = index(std::move(Cmd))) elog("Indexing {0} failed: {1}", FileName, std::move(Error)); }); T.QueuePri = IndexFile; @@ -207,7 +225,7 @@ void BackgroundIndex::boostRelated(llvm::StringRef Path) { void BackgroundIndex::update( llvm::StringRef MainFile, IndexFileIn Index, const llvm::StringMap<ShardVersion> &ShardVersionsSnapshot, - BackgroundIndexStorage *IndexStorage, bool HadErrors) { + bool HadErrors) { // Partition symbols/references into files. struct File { llvm::DenseSet<const Symbol *> Symbols; @@ -291,22 +309,21 @@ void BackgroundIndex::update( // We need to store shards before updating the index, since the latter // consumes slabs. // FIXME: Also skip serializing the shard if it is already up-to-date. - if (IndexStorage) { - IndexFileOut Shard; - Shard.Symbols = SS.get(); - Shard.Refs = RS.get(); - Shard.Relations = RelS.get(); - Shard.Sources = IG.get(); - - // Only store command line hash for main files of the TU, since our - // current model keeps only one version of a header file. - if (Path == MainFile) - Shard.Cmd = Index.Cmd.getPointer(); - - if (auto Error = IndexStorage->storeShard(Path, Shard)) - elog("Failed to write background-index shard for file {0}: {1}", Path, - std::move(Error)); - } + BackgroundIndexStorage *IndexStorage = IndexStorageFactory(Path); + IndexFileOut Shard; + Shard.Symbols = SS.get(); + Shard.Refs = RS.get(); + Shard.Relations = RelS.get(); + Shard.Sources = IG.get(); + + // Only store command line hash for main files of the TU, since our + // current model keeps only one version of a header file. + if (Path == MainFile) + Shard.Cmd = Index.Cmd.getPointer(); + + if (auto Error = IndexStorage->storeShard(Path, Shard)) + elog("Failed to write background-index shard for file {0}: {1}", Path, + std::move(Error)); { std::lock_guard<std::mutex> Lock(ShardVersionsMu); @@ -329,8 +346,7 @@ void BackgroundIndex::update( } } -llvm::Error BackgroundIndex::index(tooling::CompileCommand Cmd, - BackgroundIndexStorage *IndexStorage) { +llvm::Error BackgroundIndex::index(tooling::CompileCommand Cmd) { trace::Span Tracer("BackgroundIndex"); SPAN_ATTACH(Tracer, "file", Cmd.Filename); auto AbsolutePath = getAbsolutePath(Cmd); @@ -424,176 +440,78 @@ llvm::Error BackgroundIndex::index(tooling::CompileCommand Cmd, for (auto &It : *Index.Sources) It.second.Flags |= IncludeGraphNode::SourceFlag::HadErrors; } - update(AbsolutePath, std::move(Index), ShardVersionsSnapshot, IndexStorage, - HadErrors); + update(AbsolutePath, std::move(Index), ShardVersionsSnapshot, HadErrors); Rebuilder.indexedTU(); return llvm::Error::success(); } -std::vector<BackgroundIndex::Source> -BackgroundIndex::loadShard(const tooling::CompileCommand &Cmd, - BackgroundIndexStorage *IndexStorage, - llvm::StringSet<> &LoadedShards) { - struct ShardInfo { - std::string AbsolutePath; - std::unique_ptr<IndexFileIn> Shard; - FileDigest Digest = {}; - bool CountReferences = false; - bool HadErrors = false; - }; - std::vector<ShardInfo> IntermediateSymbols; - // Make sure we don't have duplicate elements in the queue. Keys are absolute - // paths. - llvm::StringSet<> InQueue; - auto FS = FSProvider.getFileSystem(); - // Dependencies of this TU, paired with the information about whether they - // need to be re-indexed or not. - std::vector<Source> Dependencies; - std::queue<Source> ToVisit; - std::string AbsolutePath = getAbsolutePath(Cmd).str(); - // Up until we load the shard related to a dependency it needs to be - // re-indexed. - ToVisit.emplace(AbsolutePath, true); - InQueue.insert(AbsolutePath); - // Goes over each dependency. - while (!ToVisit.empty()) { - Dependencies.push_back(std::move(ToVisit.front())); - // Dependencies is not modified during the rest of the loop, so it is safe - // to keep the reference. - auto &CurDependency = Dependencies.back(); - ToVisit.pop(); - // If we have already seen this shard before(either loaded or failed) don't - // re-try again. Since the information in the shard won't change from one TU - // to another. - if (!LoadedShards.try_emplace(CurDependency.Path).second) { - // If the dependency needs to be re-indexed, first occurence would already - // have detected that, so we don't need to issue it again. - CurDependency.NeedsReIndexing = false; - continue; - } +// Restores shards for \p MainFiles from index storage. Then checks staleness of +// those shards and returns a list of TUs that needs to be indexed to update +// staleness. +std::vector<tooling::CompileCommand> +BackgroundIndex::loadProject(std::vector<std::string> MainFiles) { + std::vector<tooling::CompileCommand> NeedsReIndexing; - auto Shard = IndexStorage->loadShard(CurDependency.Path); - if (!Shard || !Shard->Sources) { - // File will be returned as requiring re-indexing to caller. - vlog("Failed to load shard: {0}", CurDependency.Path); - continue; - } - // These are the edges in the include graph for current dependency. - for (const auto &I : *Shard->Sources) { - auto U = URI::parse(I.getKey()); - if (!U) - continue; - auto AbsolutePath = URI::resolve(*U, CurDependency.Path); - if (!AbsolutePath) - continue; - // Add file as dependency if haven't seen before. - if (InQueue.try_emplace(*AbsolutePath).second) - ToVisit.emplace(*AbsolutePath, true); - // The node contains symbol information only for current file, the rest is - // just edges. - if (*AbsolutePath != CurDependency.Path) - continue; - - // We found source file info for current dependency. - assert(I.getValue().Digest != FileDigest{{0}} && "Digest is empty?"); - ShardInfo SI; - SI.AbsolutePath = CurDependency.Path; - SI.Shard = std::move(Shard); - SI.Digest = I.getValue().Digest; - SI.CountReferences = - I.getValue().Flags & IncludeGraphNode::SourceFlag::IsTU; - SI.HadErrors = - I.getValue().Flags & IncludeGraphNode::SourceFlag::HadErrors; - IntermediateSymbols.push_back(std::move(SI)); - // Check if the source needs re-indexing. - // Get the digest, skip it if file doesn't exist. - auto Buf = FS->getBufferForFile(CurDependency.Path); - if (!Buf) { - elog("Couldn't get buffer for file: {0}: {1}", CurDependency.Path, - Buf.getError().message()); - continue; - } - // If digests match then dependency doesn't need re-indexing. - // FIXME: Also check for dependencies(sources) of this shard and compile - // commands for cache invalidation. - CurDependency.NeedsReIndexing = - digest(Buf->get()->getBuffer()) != I.getValue().Digest; - } - } - // Load shard information into background-index. + Rebuilder.startLoading(); + // Load shards for all of the mainfiles. + const std::vector<LoadedShard> Result = + loadIndexShards(MainFiles, IndexStorageFactory, CDB); + size_t LoadedShards = 0; { + // Update in-memory state. std::lock_guard<std::mutex> Lock(ShardVersionsMu); - // This can override a newer version that is added in another thread, - // if this thread sees the older version but finishes later. This - // should be rare in practice. - for (const ShardInfo &SI : IntermediateSymbols) { + for (auto &LS : Result) { + if (!LS.Shard) + continue; auto SS = - SI.Shard->Symbols - ? llvm::make_unique<SymbolSlab>(std::move(*SI.Shard->Symbols)) + LS.Shard->Symbols + ? llvm::make_unique<SymbolSlab>(std::move(*LS.Shard->Symbols)) : nullptr; - auto RS = SI.Shard->Refs - ? llvm::make_unique<RefSlab>(std::move(*SI.Shard->Refs)) + auto RS = LS.Shard->Refs + ? llvm::make_unique<RefSlab>(std::move(*LS.Shard->Refs)) : nullptr; auto RelS = - SI.Shard->Relations - ? llvm::make_unique<RelationSlab>(std::move(*SI.Shard->Relations)) + LS.Shard->Relations + ? llvm::make_unique<RelationSlab>(std::move(*LS.Shard->Relations)) : nullptr; - ShardVersion &SV = ShardVersions[SI.AbsolutePath]; - SV.Digest = SI.Digest; - SV.HadErrors = SI.HadErrors; + ShardVersion &SV = ShardVersions[LS.AbsolutePath]; + SV.Digest = LS.Digest; + SV.HadErrors = LS.HadErrors; + ++LoadedShards; - IndexedSymbols.update(SI.AbsolutePath, std::move(SS), std::move(RS), - std::move(RelS), SI.CountReferences); + IndexedSymbols.update(LS.AbsolutePath, std::move(SS), std::move(RS), + std::move(RelS), LS.CountReferences); } } - if (!IntermediateSymbols.empty()) - Rebuilder.loadedTU(); + Rebuilder.loadedShard(LoadedShards); + Rebuilder.doneLoading(); - return Dependencies; -} + auto FS = FSProvider.getFileSystem(); + llvm::DenseSet<PathRef> TUsToIndex; + // We'll accept data from stale shards, but ensure the files get reindexed + // soon. + for (auto &LS : Result) { + if (!shardIsStale(LS, FS.get())) + continue; + PathRef TUForFile = LS.DependentTU; + assert(!TUForFile.empty() && "File without a TU!"); + + // FIXME: Currently, we simply schedule indexing on a TU whenever any of + // its dependencies needs re-indexing. We might do it smarter by figuring + // out a minimal set of TUs that will cover all the stale dependencies. + // FIXME: Try looking at other TUs if no compile commands are available + // for this TU, i.e TU was deleted after we performed indexing. + TUsToIndex.insert(TUForFile); + } -// Goes over each changed file and loads them from index. Returns the list of -// TUs that had out-of-date/no shards. -std::vector<std::pair<tooling::CompileCommand, BackgroundIndexStorage *>> -BackgroundIndex::loadShards(std::vector<std::string> ChangedFiles) { - std::vector<std::pair<tooling::CompileCommand, BackgroundIndexStorage *>> - NeedsReIndexing; - // Keeps track of the files that will be reindexed, to make sure we won't - // re-index same dependencies more than once. Keys are AbsolutePaths. - llvm::StringSet<> FilesToIndex; - // Keeps track of the loaded shards to make sure we don't perform redundant - // disk IO. Keys are absolute paths. - llvm::StringSet<> LoadedShards; - Rebuilder.startLoading(); - for (const auto &File : ChangedFiles) { - auto Cmd = CDB.getCompileCommand(File); + for (PathRef TU : TUsToIndex) { + auto Cmd = CDB.getCompileCommand(TU); if (!Cmd) continue; - - std::string ProjectRoot; - if (auto PI = CDB.getProjectInfo(File)) - ProjectRoot = std::move(PI->SourceRoot); - - BackgroundIndexStorage *IndexStorage = IndexStorageFactory(ProjectRoot); - auto Dependencies = loadShard(*Cmd, IndexStorage, LoadedShards); - for (const auto &Dependency : Dependencies) { - if (!Dependency.NeedsReIndexing || FilesToIndex.count(Dependency.Path)) - continue; - // FIXME: Currently, we simply schedule indexing on a TU whenever any of - // its dependencies needs re-indexing. We might do it smarter by figuring - // out a minimal set of TUs that will cover all the stale dependencies. - vlog("Enqueueing TU {0} because its dependency {1} needs re-indexing.", - Cmd->Filename, Dependency.Path); - NeedsReIndexing.push_back({std::move(*Cmd), IndexStorage}); - // Mark all of this TU's dependencies as to-be-indexed so that we won't - // try to re-index those. - for (const auto &Dependency : Dependencies) - FilesToIndex.insert(Dependency.Path); - break; - } + NeedsReIndexing.emplace_back(std::move(*Cmd)); } - Rebuilder.doneLoading(); + return NeedsReIndexing; } diff --git a/clang-tools-extra/clangd/index/Background.h b/clang-tools-extra/clangd/index/Background.h index 39fe8daeba8..7ce9e7bf17b 100644 --- a/clang-tools-extra/clangd/index/Background.h +++ b/clang-tools-extra/clangd/index/Background.h @@ -12,6 +12,7 @@ #include "Context.h" #include "FSProvider.h" #include "GlobalCompilationDatabase.h" +#include "Path.h" #include "SourceCode.h" #include "Threading.h" #include "index/BackgroundRebuild.h" @@ -49,15 +50,17 @@ public: virtual std::unique_ptr<IndexFileIn> loadShard(llvm::StringRef ShardIdentifier) const = 0; - // The factory provides storage for each CDB. + // The factory provides storage for each File. // It keeps ownership of the storage instances, and should manage caching // itself. Factory must be threadsafe and never returns nullptr. - using Factory = - llvm::unique_function<BackgroundIndexStorage *(llvm::StringRef)>; + using Factory = llvm::unique_function<BackgroundIndexStorage *(PathRef)>; // Creates an Index Storage that saves shards into disk. Index storage uses - // CDBDirectory + ".clangd/index/" as the folder to save shards. - static Factory createDiskBackedStorageFactory(); + // CDBDirectory + ".clangd/index/" as the folder to save shards. CDBDirectory + // is the first directory containing a CDB in parent directories of a file, or + // user's home directory if none was found, e.g. standard library headers. + static Factory createDiskBackedStorageFactory( + std::function<llvm::Optional<ProjectInfo>(PathRef)> GetProjectInfo); }; // A priority queue of tasks which can be run on (external) worker threads. @@ -157,15 +160,14 @@ private: /// information on IndexStorage. void update(llvm::StringRef MainFile, IndexFileIn Index, const llvm::StringMap<ShardVersion> &ShardVersionsSnapshot, - BackgroundIndexStorage *IndexStorage, bool HadErrors); + bool HadErrors); // configuration const FileSystemProvider &FSProvider; const GlobalCompilationDatabase &CDB; Context BackgroundContext; - llvm::Error index(tooling::CompileCommand, - BackgroundIndexStorage *IndexStorage); + llvm::Error index(tooling::CompileCommand); FileSymbols IndexedSymbols; BackgroundIndexRebuilder Rebuilder; @@ -173,25 +175,13 @@ private: std::mutex ShardVersionsMu; BackgroundIndexStorage::Factory IndexStorageFactory; - struct Source { - std::string Path; - bool NeedsReIndexing; - Source(llvm::StringRef Path, bool NeedsReIndexing) - : Path(Path), NeedsReIndexing(NeedsReIndexing) {} - }; - // Loads the shards for a single TU and all of its dependencies. Returns the - // list of sources and whether they need to be re-indexed. - std::vector<Source> loadShard(const tooling::CompileCommand &Cmd, - BackgroundIndexStorage *IndexStorage, - llvm::StringSet<> &LoadedShards); - // Tries to load shards for the ChangedFiles. - std::vector<std::pair<tooling::CompileCommand, BackgroundIndexStorage *>> - loadShards(std::vector<std::string> ChangedFiles); + // Tries to load shards for the MainFiles and their dependencies. + std::vector<tooling::CompileCommand> + loadProject(std::vector<std::string> MainFiles); BackgroundQueue::Task changedFilesTask(const std::vector<std::string> &ChangedFiles); - BackgroundQueue::Task indexFileTask(tooling::CompileCommand Cmd, - BackgroundIndexStorage *Storage); + BackgroundQueue::Task indexFileTask(tooling::CompileCommand Cmd); // from lowest to highest priority enum QueuePriority { diff --git a/clang-tools-extra/clangd/index/BackgroundIndexLoader.cpp b/clang-tools-extra/clangd/index/BackgroundIndexLoader.cpp new file mode 100644 index 00000000000..585d36716d2 --- /dev/null +++ b/clang-tools-extra/clangd/index/BackgroundIndexLoader.cpp @@ -0,0 +1,143 @@ +//===-- BackgroundIndexLoader.cpp - ---------------------------------------===// +// +// 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 "index/BackgroundIndexLoader.h" +#include "GlobalCompilationDatabase.h" +#include "Logger.h" +#include "Path.h" +#include "index/Background.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/SmallString.h" +#include "llvm/ADT/StringMap.h" +#include "llvm/Support/Path.h" +#include <string> +#include <utility> +#include <vector> + +namespace clang { +namespace clangd { +namespace { + +llvm::Optional<Path> uriToAbsolutePath(llvm::StringRef URI, PathRef HintPath) { + auto U = URI::parse(URI); + if (!U) + return llvm::None; + auto AbsolutePath = URI::resolve(*U, HintPath); + if (!AbsolutePath) + return llvm::None; + return *AbsolutePath; +} + +/// A helper class to cache BackgroundIndexStorage operations and keep the +/// inverse dependency mapping. +class BackgroundIndexLoader { +public: + BackgroundIndexLoader(BackgroundIndexStorage::Factory &IndexStorageFactory) + : IndexStorageFactory(IndexStorageFactory) {} + /// Load the shards for \p MainFile and all of its dependencies. + void load(PathRef MainFile); + + /// Consumes the loader and returns all shards. + std::vector<LoadedShard> takeResult() &&; + +private: + /// Returns the Shard for \p StartSourceFile from cache or loads it from \p + /// Storage. Also returns paths for dependencies of \p StartSourceFile if it + /// wasn't cached yet. + std::pair<const LoadedShard &, std::vector<Path>> + loadShard(PathRef StartSourceFile, PathRef DependentTU); + + /// Cache for Storage lookups. + llvm::StringMap<LoadedShard> LoadedShards; + + BackgroundIndexStorage::Factory &IndexStorageFactory; +}; + +std::pair<const LoadedShard &, std::vector<Path>> +BackgroundIndexLoader::loadShard(PathRef StartSourceFile, PathRef DependentTU) { + auto It = LoadedShards.try_emplace(StartSourceFile); + LoadedShard &LS = It.first->getValue(); + std::vector<Path> Edges = {}; + // Return the cached shard. + if (!It.second) + return {LS, Edges}; + + LS.AbsolutePath = StartSourceFile.str(); + LS.DependentTU = DependentTU; + BackgroundIndexStorage *Storage = IndexStorageFactory(LS.AbsolutePath); + auto Shard = Storage->loadShard(StartSourceFile); + if (!Shard || !Shard->Sources) { + vlog("Failed to load shard: {0}", StartSourceFile); + return {LS, Edges}; + } + + LS.Shard = std::move(Shard); + for (const auto &It : *LS.Shard->Sources) { + auto AbsPath = uriToAbsolutePath(It.getKey(), StartSourceFile); + if (!AbsPath) + continue; + // A shard contains only edges for non main-file sources. + if (*AbsPath != StartSourceFile) { + Edges.push_back(*AbsPath); + continue; + } + + // Fill in shard metadata. + const IncludeGraphNode &IGN = It.getValue(); + LS.Digest = IGN.Digest; + LS.CountReferences = IGN.Flags & IncludeGraphNode::SourceFlag::IsTU; + LS.HadErrors = IGN.Flags & IncludeGraphNode::SourceFlag::HadErrors; + } + assert(LS.Digest != FileDigest{{0}} && "Digest is empty?"); + return {LS, Edges}; +} + +void BackgroundIndexLoader::load(PathRef MainFile) { + llvm::StringSet<> InQueue; + // Following containers points to strings inside InQueue. + std::queue<PathRef> ToVisit; + InQueue.insert(MainFile); + ToVisit.push(MainFile); + + while (!ToVisit.empty()) { + PathRef SourceFile = ToVisit.front(); + ToVisit.pop(); + + auto ShardAndEdges = loadShard(SourceFile, MainFile); + for (PathRef Edge : ShardAndEdges.second) { + auto It = InQueue.insert(Edge); + if (It.second) + ToVisit.push(It.first->getKey()); + } + } +} + +std::vector<LoadedShard> BackgroundIndexLoader::takeResult() && { + std::vector<LoadedShard> Result; + Result.reserve(LoadedShards.size()); + for (auto &It : LoadedShards) + Result.push_back(std::move(It.getValue())); + return Result; +} +} // namespace + +std::vector<LoadedShard> +loadIndexShards(llvm::ArrayRef<Path> MainFiles, + BackgroundIndexStorage::Factory &IndexStorageFactory, + const GlobalCompilationDatabase &CDB) { + BackgroundIndexLoader Loader(IndexStorageFactory); + for (llvm::StringRef MainFile : MainFiles) { + assert(llvm::sys::path::is_absolute(MainFile)); + Loader.load(MainFile); + } + return std::move(Loader).takeResult(); +} + +} // namespace clangd +} // namespace clang diff --git a/clang-tools-extra/clangd/index/BackgroundIndexLoader.h b/clang-tools-extra/clangd/index/BackgroundIndexLoader.h new file mode 100644 index 00000000000..0caf1b46352 --- /dev/null +++ b/clang-tools-extra/clangd/index/BackgroundIndexLoader.h @@ -0,0 +1,54 @@ +//===--- BackgroundIndexLoader.h - Load shards from index storage-*- 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_INDEX_BACKGROUND_INDEX_LOADER_H +#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_BACKGROUND_INDEX_LOADER_H + +#include "Path.h" +#include "index/Background.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/Optional.h" +#include "llvm/ADT/StringMap.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/Support/VirtualFileSystem.h" +#include <memory> +#include <vector> + +namespace clang { +namespace clangd { + +/// Represents a shard loaded from storage, stores contents in \p Shard and +/// metadata about the source file that generated this shard. +struct LoadedShard { + /// Path of the source file that produced this shard. + Path AbsolutePath; + /// Digest of the source file contents that produced this shard. + FileDigest Digest = {}; + /// Whether the RefSlab in Shard should be used for updating symbol reference + /// counts when building an index. + bool CountReferences = false; + /// Whether the indexing action producing that shard had errors. + bool HadErrors = false; + /// Path to a TU that is depending on this shard. + Path DependentTU; + /// Will be nullptr when index storage couldn't provide a valid shard for + /// AbsolutePath. + std::unique_ptr<IndexFileIn> Shard; +}; + +/// Loads all shards for the TU \p MainFile from \p Storage. +std::vector<LoadedShard> +loadIndexShards(llvm::ArrayRef<Path> MainFiles, + BackgroundIndexStorage::Factory &IndexStorageFactory, + const GlobalCompilationDatabase &CDB); + +} // namespace clangd +} // namespace clang + +#endif diff --git a/clang-tools-extra/clangd/index/BackgroundIndexStorage.cpp b/clang-tools-extra/clangd/index/BackgroundIndexStorage.cpp index 80246b9ceea..8b2c411a166 100644 --- a/clang-tools-extra/clangd/index/BackgroundIndexStorage.cpp +++ b/clang-tools-extra/clangd/index/BackgroundIndexStorage.cpp @@ -6,13 +6,21 @@ // //===----------------------------------------------------------------------===// +#include "GlobalCompilationDatabase.h" #include "Logger.h" +#include "Path.h" #include "index/Background.h" +#include "llvm/ADT/Optional.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/ADT/ScopeExit.h" +#include "llvm/ADT/SmallString.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StringRef.h" #include "llvm/Support/Error.h" #include "llvm/Support/FileSystem.h" #include "llvm/Support/MemoryBuffer.h" #include "llvm/Support/Path.h" +#include <functional> namespace clang { namespace clangd { @@ -118,12 +126,21 @@ public: // Creates and owns IndexStorages for multiple CDBs. class DiskBackedIndexStorageManager { public: - DiskBackedIndexStorageManager() - : IndexStorageMapMu(llvm::make_unique<std::mutex>()) {} + DiskBackedIndexStorageManager( + std::function<llvm::Optional<ProjectInfo>(PathRef)> GetProjectInfo) + : IndexStorageMapMu(llvm::make_unique<std::mutex>()), + GetProjectInfo(std::move(GetProjectInfo)) { + llvm::SmallString<128> HomeDir; + llvm::sys::path::home_directory(HomeDir); + this->HomeDir = HomeDir.str().str(); + } - // Creates or fetches to storage from cache for the specified CDB. - BackgroundIndexStorage *operator()(llvm::StringRef CDBDirectory) { + // Creates or fetches to storage from cache for the specified project. + BackgroundIndexStorage *operator()(PathRef File) { std::lock_guard<std::mutex> Lock(*IndexStorageMapMu); + Path CDBDirectory = HomeDir; + if (auto PI = GetProjectInfo(File)) + CDBDirectory = PI->SourceRoot; auto &IndexStorage = IndexStorageMap[CDBDirectory]; if (!IndexStorage) IndexStorage = create(CDBDirectory); @@ -131,21 +148,28 @@ public: } private: - std::unique_ptr<BackgroundIndexStorage> create(llvm::StringRef CDBDirectory) { - if (CDBDirectory.empty()) + std::unique_ptr<BackgroundIndexStorage> create(PathRef CDBDirectory) { + if (CDBDirectory.empty()) { + elog("Tried to create storage for empty directory!"); return llvm::make_unique<NullStorage>(); + } return llvm::make_unique<DiskBackedIndexStorage>(CDBDirectory); } + Path HomeDir; + llvm::StringMap<std::unique_ptr<BackgroundIndexStorage>> IndexStorageMap; std::unique_ptr<std::mutex> IndexStorageMapMu; + + std::function<llvm::Optional<ProjectInfo>(PathRef)> GetProjectInfo; }; } // namespace BackgroundIndexStorage::Factory -BackgroundIndexStorage::createDiskBackedStorageFactory() { - return DiskBackedIndexStorageManager(); +BackgroundIndexStorage::createDiskBackedStorageFactory( + std::function<llvm::Optional<ProjectInfo>(PathRef)> GetProjectInfo) { + return DiskBackedIndexStorageManager(std::move(GetProjectInfo)); } } // namespace clangd diff --git a/clang-tools-extra/clangd/index/BackgroundRebuild.cpp b/clang-tools-extra/clangd/index/BackgroundRebuild.cpp index 4233e5c92a0..cb6ac0fc8bf 100644 --- a/clang-tools-extra/clangd/index/BackgroundRebuild.cpp +++ b/clang-tools-extra/clangd/index/BackgroundRebuild.cpp @@ -78,13 +78,13 @@ void BackgroundIndexRebuilder::idle() { void BackgroundIndexRebuilder::startLoading() { std::lock_guard<std::mutex> Lock(Mu); if (!Loading) - LoadedTUs = 0; + LoadedShards = 0; ++Loading; } -void BackgroundIndexRebuilder::loadedTU() { +void BackgroundIndexRebuilder::loadedShard(size_t ShardCount) { std::lock_guard<std::mutex> Lock(Mu); assert(Loading); - ++LoadedTUs; + LoadedShards += ShardCount; } void BackgroundIndexRebuilder::doneLoading() { maybeRebuild("after loading index from disk", [this] { @@ -93,7 +93,7 @@ void BackgroundIndexRebuilder::doneLoading() { if (Loading) // was loading multiple batches concurrently return false; // rebuild once the last batch is done. // Rebuild if we loaded any shards, or if we stopped an indexedTU rebuild. - return LoadedTUs > 0 || enoughTUsToRebuild(); + return LoadedShards > 0 || enoughTUsToRebuild(); }); } diff --git a/clang-tools-extra/clangd/index/BackgroundRebuild.h b/clang-tools-extra/clangd/index/BackgroundRebuild.h index f660957f624..d74c28be5cf 100644 --- a/clang-tools-extra/clangd/index/BackgroundRebuild.h +++ b/clang-tools-extra/clangd/index/BackgroundRebuild.h @@ -17,6 +17,7 @@ #include "index/FileIndex.h" #include "index/Index.h" #include "llvm/Support/Threading.h" +#include <cstddef> namespace clang { namespace clangd { @@ -61,7 +62,7 @@ public: // sessions may happen concurrently. void startLoading(); // Called to indicate some shards were actually loaded from disk. - void loadedTU(); + void loadedShard(size_t ShardCount); // Called to indicate we're finished loading shards from disk. // May rebuild (if any were loaded). void doneLoading(); @@ -89,7 +90,7 @@ private: unsigned IndexedTUsAtLastRebuild = 0; // Are we loading shards? May be multiple concurrent sessions. unsigned Loading = 0; - unsigned LoadedTUs; // In the current loading session. + unsigned LoadedShards; // In the current loading session. SwapIndex *Target; FileSymbols *Source; diff --git a/clang-tools-extra/clangd/test/Inputs/background-index/definition.jsonrpc b/clang-tools-extra/clangd/test/Inputs/background-index/definition.jsonrpc index 933e7791320..de99072b6a4 100644 --- a/clang-tools-extra/clangd/test/Inputs/background-index/definition.jsonrpc +++ b/clang-tools-extra/clangd/test/Inputs/background-index/definition.jsonrpc @@ -18,7 +18,7 @@ "uri": "file://DIRECTORY/bar.cpp", "languageId": "cpp", "version": 1, - "text": "#include \"foo.h\"\nint main(){\nreturn foo();\n}" + "text": "#include \"sub_dir/foo.h\"\nint main(){\nreturn foo();\n}" } } } diff --git a/clang-tools-extra/clangd/test/Inputs/background-index/foo.cpp b/clang-tools-extra/clangd/test/Inputs/background-index/foo.cpp index c42ca4d0737..21fc589166a 100644 --- a/clang-tools-extra/clangd/test/Inputs/background-index/foo.cpp +++ b/clang-tools-extra/clangd/test/Inputs/background-index/foo.cpp @@ -1,2 +1,2 @@ -#include "foo.h" +#include "sub_dir/foo.h" int foo() { return 42; } diff --git a/clang-tools-extra/clangd/test/Inputs/background-index/sub_dir/compile_flags.txt b/clang-tools-extra/clangd/test/Inputs/background-index/sub_dir/compile_flags.txt new file mode 100644 index 00000000000..e69de29bb2d --- /dev/null +++ b/clang-tools-extra/clangd/test/Inputs/background-index/sub_dir/compile_flags.txt diff --git a/clang-tools-extra/clangd/test/Inputs/background-index/foo.h b/clang-tools-extra/clangd/test/Inputs/background-index/sub_dir/foo.h index 9539f1d7588..9539f1d7588 100644 --- a/clang-tools-extra/clangd/test/Inputs/background-index/foo.h +++ b/clang-tools-extra/clangd/test/Inputs/background-index/sub_dir/foo.h diff --git a/clang-tools-extra/clangd/test/background-index.test b/clang-tools-extra/clangd/test/background-index.test index eabca2bcaf7..57118f2159a 100644 --- a/clang-tools-extra/clangd/test/background-index.test +++ b/clang-tools-extra/clangd/test/background-index.test @@ -5,7 +5,8 @@ # 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/* +# 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. @@ -14,6 +15,7 @@ # 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 diff --git a/clang-tools-extra/clangd/unittests/BackgroundIndexTests.cpp b/clang-tools-extra/clangd/unittests/BackgroundIndexTests.cpp index 79e081bd678..0401aeb1923 100644 --- a/clang-tools-extra/clangd/unittests/BackgroundIndexTests.cpp +++ b/clang-tools-extra/clangd/unittests/BackgroundIndexTests.cpp @@ -211,7 +211,7 @@ TEST_F(BackgroundIndexTest, ShardStorageTest) { OverlayCDB CDB(/*Base=*/nullptr); BackgroundIndex Idx(Context::empty(), FS, CDB, [&](llvm::StringRef) { return &MSS; }); - CDB.setCompileCommand(testPath("root"), Cmd); + CDB.setCompileCommand(testPath("root/A.cc"), Cmd); ASSERT_TRUE(Idx.blockUntilIdleForTest()); } EXPECT_EQ(CacheHits, 2U); // Check both A.cc and A.h loaded from cache. @@ -335,7 +335,7 @@ TEST_F(BackgroundIndexTest, ShardStorageLoad) { OverlayCDB CDB(/*Base=*/nullptr); BackgroundIndex Idx(Context::empty(), FS, CDB, [&](llvm::StringRef) { return &MSS; }); - CDB.setCompileCommand(testPath("root"), Cmd); + CDB.setCompileCommand(testPath("root/A.cc"), Cmd); ASSERT_TRUE(Idx.blockUntilIdleForTest()); } EXPECT_EQ(CacheHits, 2U); // Check both A.cc and A.h loaded from cache. @@ -353,7 +353,7 @@ TEST_F(BackgroundIndexTest, ShardStorageLoad) { OverlayCDB CDB(/*Base=*/nullptr); BackgroundIndex Idx(Context::empty(), FS, CDB, [&](llvm::StringRef) { return &MSS; }); - CDB.setCompileCommand(testPath("root"), Cmd); + CDB.setCompileCommand(testPath("root/A.cc"), Cmd); ASSERT_TRUE(Idx.blockUntilIdleForTest()); } EXPECT_EQ(CacheHits, 2U); // Check both A.cc and A.h loaded from cache. @@ -621,8 +621,8 @@ TEST_F(BackgroundIndexRebuilderTest, IndexingTUs) { TEST_F(BackgroundIndexRebuilderTest, LoadingShards) { Rebuilder.startLoading(); - Rebuilder.loadedTU(); - Rebuilder.loadedTU(); + Rebuilder.loadedShard(10); + Rebuilder.loadedShard(20); EXPECT_TRUE(checkRebuild([&] { Rebuilder.doneLoading(); })); // No rebuild for no shards. @@ -631,11 +631,11 @@ TEST_F(BackgroundIndexRebuilderTest, LoadingShards) { // Loads can overlap. Rebuilder.startLoading(); - Rebuilder.loadedTU(); + Rebuilder.loadedShard(1); Rebuilder.startLoading(); - Rebuilder.loadedTU(); + Rebuilder.loadedShard(1); EXPECT_FALSE(checkRebuild([&] { Rebuilder.doneLoading(); })); - Rebuilder.loadedTU(); + Rebuilder.loadedShard(1); EXPECT_TRUE(checkRebuild([&] { Rebuilder.doneLoading(); })); // No rebuilding for indexed files while loading. |
