Index: clang-tools-extra/trunk/clangd/Headers.h =================================================================== --- clang-tools-extra/trunk/clangd/Headers.h +++ clang-tools-extra/trunk/clangd/Headers.h @@ -53,9 +53,9 @@ // self-contained). struct IncludeGraphNode { // True if current file is a main file rather than a header. - bool IsTU; + bool IsTU = false; llvm::StringRef URI; - FileDigest Digest; + FileDigest Digest{0}; std::vector DirectIncludes; }; // FileURI and FileInclusions are references to keys of the map containing Index: clang-tools-extra/trunk/clangd/index/Background.cpp =================================================================== --- clang-tools-extra/trunk/clangd/index/Background.cpp +++ clang-tools-extra/trunk/clangd/index/Background.cpp @@ -35,6 +35,58 @@ using namespace llvm; namespace clang { namespace clangd { +namespace { +// Resolves URI to file paths with cache. +class URIToFileCache { +public: + URIToFileCache(llvm::StringRef HintPath) : HintPath(HintPath) {} + + llvm::StringRef resolve(llvm::StringRef FileURI) { + auto I = URIToPathCache.try_emplace(FileURI); + if (I.second) { + auto U = URI::parse(FileURI); + if (!U) { + elog("Failed to parse URI {0}: {1}", FileURI, U.takeError()); + assert(false && "Failed to parse URI"); + return ""; + } + auto Path = URI::resolve(*U, HintPath); + if (!Path) { + elog("Failed to resolve URI {0}: {1}", FileURI, Path.takeError()); + assert(false && "Failed to resolve URI"); + return ""; + } + I.first->second = *Path; + } + return I.first->second; + } + +private: + std::string HintPath; + llvm::StringMap URIToPathCache; +}; + +// We keep only the node "U" and its edges. Any node other than "U" will be +// empty in the resultant graph. +IncludeGraph getSubGraph(const URI &U, const IncludeGraph &FullGraph) { + IncludeGraph IG; + + std::string FileURI = U.toString(); + auto Entry = IG.try_emplace(FileURI).first; + auto &Node = Entry->getValue(); + Node = FullGraph.lookup(Entry->getKey()); + Node.URI = Entry->getKey(); + + // URIs inside nodes must point into the keys of the same IncludeGraph. + for (auto &Include : Node.DirectIncludes) { + auto I = IG.try_emplace(Include).first; + I->getValue().URI = I->getKey(); + Include = I->getKey(); + } + + return IG; +} +} // namespace BackgroundIndex::BackgroundIndex( Context BackgroundContext, StringRef ResourceDir, @@ -150,36 +202,6 @@ QueueCV.notify_all(); } -// Resolves URI to file paths with cache. -class URIToFileCache { -public: - URIToFileCache(llvm::StringRef HintPath) : HintPath(HintPath) {} - - llvm::StringRef resolve(llvm::StringRef FileURI) { - auto I = URIToPathCache.try_emplace(FileURI); - if (I.second) { - auto U = URI::parse(FileURI); - if (!U) { - elog("Failed to parse URI {0}: {1}", FileURI, U.takeError()); - assert(false && "Failed to parse URI"); - return ""; - } - auto Path = URI::resolve(*U, HintPath); - if (!Path) { - elog("Failed to resolve URI {0}: {1}", FileURI, Path.takeError()); - assert(false && "Failed to resolve URI"); - return ""; - } - I.first->second = *Path; - } - return I.first->second; - } - -private: - std::string HintPath; - llvm::StringMap URIToPathCache; -}; - /// Given index results from a TU, only update files in \p FilesToUpdate. void BackgroundIndex::update(StringRef MainFile, IndexFileIn Index, const StringMap &FilesToUpdate, @@ -233,6 +255,8 @@ auto SS = llvm::make_unique(std::move(Syms).build()); auto RS = llvm::make_unique(std::move(Refs).build()); + auto IG = llvm::make_unique( + getSubGraph(URI::create(Path), Index.Sources.getValue())); auto Hash = FilesToUpdate.lookup(Path); // We need to store shards before updating the index, since the latter @@ -241,6 +265,7 @@ IndexFileOut Shard; Shard.Symbols = SS.get(); Shard.Refs = RS.get(); + Shard.Sources = IG.get(); if (auto Error = IndexStorage->storeShard(Path, Shard)) elog("Failed to write background-index shard for file {0}: {1}", Path, @@ -260,9 +285,9 @@ // digests. // \p FileDigests contains file digests for the current indexed files, and all // changed files will be added to \p FilesToUpdate. -decltype(SymbolCollector::Options::FileFilter) createFileFilter( - const llvm::StringMap &FileDigests, - llvm::StringMap &FilesToUpdate) { +decltype(SymbolCollector::Options::FileFilter) +createFileFilter(const llvm::StringMap &FileDigests, + llvm::StringMap &FilesToUpdate) { return [&FileDigests, &FilesToUpdate](const SourceManager &SM, FileID FID) { StringRef Path; if (const auto *F = SM.getFileEntryForID(FID)) @@ -338,12 +363,11 @@ SymbolCollector::Options IndexOpts; StringMap FilesToUpdate; IndexOpts.FileFilter = createFileFilter(DigestsSnapshot, FilesToUpdate); - SymbolSlab Symbols; - RefSlab Refs; + IndexFileIn Index; auto Action = createStaticIndexingAction( - IndexOpts, [&](SymbolSlab S) { Symbols = std::move(S); }, - [&](RefSlab R) { Refs = std::move(R); }, - /*IncludeGraphCallback=*/nullptr); + IndexOpts, [&](SymbolSlab S) { Index.Symbols = std::move(S); }, + [&](RefSlab R) { Index.Refs = std::move(R); }, + [&](IncludeGraph IG) { Index.Sources = std::move(IG); }); // We're going to run clang here, and it could potentially crash. // We could use CrashRecoveryContext to try to make indexing crashes nonfatal, @@ -358,13 +382,12 @@ return createStringError(inconvertibleErrorCode(), "Execute() failed"); Action->EndSourceFile(); - log("Indexed {0} ({1} symbols, {2} refs)", Inputs.CompileCommand.Filename, - Symbols.size(), Refs.numRefs()); - SPAN_ATTACH(Tracer, "symbols", int(Symbols.size())); - SPAN_ATTACH(Tracer, "refs", int(Refs.numRefs())); - IndexFileIn Index; - Index.Symbols = std::move(Symbols); - Index.Refs = std::move(Refs); + log("Indexed {0} ({1} symbols, {2} refs, {3} files)", + Inputs.CompileCommand.Filename, Index.Symbols->size(), + Index.Refs->numRefs(), Index.Sources->size()); + SPAN_ATTACH(Tracer, "symbols", int(Index.Symbols->size())); + SPAN_ATTACH(Tracer, "refs", int(Index.Refs->numRefs())); + SPAN_ATTACH(Tracer, "sources", int(Index.Sources->size())); update(AbsolutePath, std::move(Index), FilesToUpdate, IndexStorage); { Index: clang-tools-extra/trunk/unittests/clangd/BackgroundIndexTests.cpp =================================================================== --- clang-tools-extra/trunk/unittests/clangd/BackgroundIndexTests.cpp +++ clang-tools-extra/trunk/unittests/clangd/BackgroundIndexTests.cpp @@ -24,6 +24,11 @@ RefsAre(std::vector> Matchers) { return ElementsAre(testing::Pair(_, UnorderedElementsAreArray(Matchers))); } +// URI cannot be empty since it references keys in the IncludeGraph. +MATCHER(EmptyIncludeNode, "") { + return !arg.IsTU && !arg.URI.empty() && arg.Digest == FileDigest{0} && + arg.DirectIncludes.empty(); +} class MemoryShardStorage : public BackgroundIndexStorage { mutable std::mutex StorageMu; @@ -93,7 +98,7 @@ Cmd.Filename = testPath("root/A.cc"); Cmd.Directory = testPath("root"); Cmd.CommandLine = {"clang++", "-DA=1", testPath("root/A.cc")}; - CDB.setCompileCommand(testPath("root"), Cmd); + CDB.setCompileCommand(testPath("root/A.cc"), Cmd); ASSERT_TRUE(Idx.blockUntilIdleForTest()); EXPECT_THAT( @@ -103,7 +108,7 @@ Cmd.Filename = testPath("root/B.cc"); Cmd.CommandLine = {"clang++", Cmd.Filename}; - CDB.setCompileCommand(testPath("root"), Cmd); + CDB.setCompileCommand(testPath("root/A.cc"), Cmd); ASSERT_TRUE(Idx.blockUntilIdleForTest()); // B_CC is dropped as we don't collect symbols from A.h in this compilation. @@ -143,7 +148,7 @@ 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, 0U); @@ -165,5 +170,56 @@ EXPECT_THAT(*ShardSource->Refs, RefsAre({FileURI("unittest:///root/A.cc")})); } +TEST_F(BackgroundIndexTest, DirectIncludesTest) { + MockFSProvider FS; + FS.Files[testPath("root/B.h")] = ""; + FS.Files[testPath("root/A.h")] = R"cpp( + #include "B.h" + void common(); + void f_b(); + class A_CC {}; + )cpp"; + std::string A_CC = "#include \"A.h\"\nvoid g() { (void)common; }"; + FS.Files[testPath("root/A.cc")] = A_CC; + + llvm::StringMap Storage; + size_t CacheHits = 0; + MemoryShardStorage MSS(Storage, CacheHits); + + tooling::CompileCommand Cmd; + Cmd.Filename = testPath("root/A.cc"); + Cmd.Directory = testPath("root"); + Cmd.CommandLine = {"clang++", testPath("root/A.cc")}; + { + OverlayCDB CDB(/*Base=*/nullptr); + BackgroundIndex Idx(Context::empty(), "", FS, CDB, + [&](llvm::StringRef) { return &MSS; }); + CDB.setCompileCommand(testPath("root/A.cc"), Cmd); + ASSERT_TRUE(Idx.blockUntilIdleForTest()); + } + + auto ShardSource = MSS.loadShard(testPath("root/A.cc")); + EXPECT_TRUE(ShardSource->Sources); + EXPECT_EQ(ShardSource->Sources->size(), 2U); // A.cc, A.h + EXPECT_THAT( + ShardSource->Sources->lookup("unittest:///root/A.cc").DirectIncludes, + UnorderedElementsAre("unittest:///root/A.h")); + EXPECT_NE(ShardSource->Sources->lookup("unittest:///root/A.cc").Digest, + FileDigest{0}); + EXPECT_THAT(ShardSource->Sources->lookup("unittest:///root/A.h"), + EmptyIncludeNode()); + + auto ShardHeader = MSS.loadShard(testPath("root/A.h")); + EXPECT_TRUE(ShardHeader->Sources); + EXPECT_EQ(ShardHeader->Sources->size(), 2U); // A.h, B.h + EXPECT_THAT( + ShardHeader->Sources->lookup("unittest:///root/A.h").DirectIncludes, + UnorderedElementsAre("unittest:///root/B.h")); + EXPECT_NE(ShardHeader->Sources->lookup("unittest:///root/A.h").Digest, + FileDigest{0}); + EXPECT_THAT(ShardHeader->Sources->lookup("unittest:///root/B.h"), + EmptyIncludeNode()); +} + } // namespace clangd } // namespace clang