Index: clangd/index/IndexAction.h =================================================================== --- clangd/index/IndexAction.h +++ clangd/index/IndexAction.h @@ -9,6 +9,7 @@ #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_ACTION_H #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_ACTION_H +#include "Headers.h" #include "SymbolCollector.h" #include "clang/Frontend/FrontendActions.h" @@ -23,10 +24,11 @@ // - references are always counted // - all references are collected (if RefsCallback is non-null) // - the symbol origin is always Static -std::unique_ptr -createStaticIndexingAction(SymbolCollector::Options Opts, - std::function SymbolsCallback, - std::function RefsCallback); +std::unique_ptr createStaticIndexingAction( + SymbolCollector::Options Opts, + std::function SymbolsCallback, + std::function RefsCallback, + std::function IncludeGraphCallback = nullptr); } // namespace clangd } // namespace clang Index: clangd/index/IndexAction.cpp =================================================================== --- clangd/index/IndexAction.cpp +++ clangd/index/IndexAction.cpp @@ -9,6 +9,101 @@ namespace clangd { namespace { +llvm::Optional URIFromFileEntry(const FileEntry *File) { + if (!File) + return llvm::None; + auto AbsolutePath = File->tryGetRealPathName(); + if (AbsolutePath.empty()) + return llvm::None; + auto U = URI::create(AbsolutePath); + return U.toString(); +} + +// Collects the nodes and edges of include graph during indexing action. +// Important: The graph generated by those callbacks might contain cycles and +// self edges. +struct IncludeGraphCollector : public PPCallbacks { +public: + IncludeGraphCollector(const SourceManager &SM, IncludeGraph &IG) + : SM(SM), IG(IG) {} + + // Populates the following fields of the corresponding node for a new include: + // - Digest -> SHA1 hash of the file. + // - IsTU -> true if the file is the main file the indexing action has been + // started on. + // - URI -> Reference to the key for this node in the include graph. + void FileChanged(SourceLocation Loc, FileChangeReason Reason, + SrcMgr::CharacteristicKind FileType, + FileID PrevFID) override { + // We only need to process each file once. So we don't care about anything + // but entries. + if (Reason != FileChangeReason::EnterFile) + return; + + const auto FileID = SM.getFileID(Loc); + const auto File = SM.getFileEntryForID(FileID); + auto URI = URIFromFileEntry(File); + if (!URI) + return; + auto I = IG.try_emplace(*URI).first; + + auto &Node = I->getValue(); + // Node has already been populated. + if (Node.URI.data() == I->getKeyData()) { +#ifndef NDEBUG + auto Digest = digestFile(SM, FileID); + assert(Digest && Node.Digest == *Digest && + "Same file, different digest?"); +#endif + return; + } + if (auto Digest = digestFile(SM, FileID)) + Node.Digest = std::move(*Digest); + Node.IsTU = FileID == SM.getMainFileID(); + Node.URI = I->getKey(); + } + + // Add edges from including files to includes. + void InclusionDirective(SourceLocation HashLoc, const Token &IncludeTok, + StringRef FileName, bool IsAngled, + CharSourceRange FilenameRange, const FileEntry *File, + StringRef SearchPath, StringRef RelativePath, + const Module *Imported, + SrcMgr::CharacteristicKind FileType) override { + auto IncludeURI = URIFromFileEntry(File); + if (!IncludeURI) + return; + + auto IncludingURI = + URIFromFileEntry(SM.getFileEntryForID(SM.getFileID(HashLoc))); + if (!IncludingURI) + return; + + auto NodeForInclude = IG.try_emplace(*IncludeURI).first->getKey(); + auto NodeForIncluding = IG.try_emplace(*IncludingURI); + + NodeForIncluding.first->getValue().DirectIncludes.push_back(NodeForInclude); + } + + // Sanity check to ensure we have already populated a skipped file. + void FileSkipped(const FileEntry &SkippedFile, const Token &FilenameTok, + SrcMgr::CharacteristicKind FileType) override { +#ifndef NDEBUG + auto URI = URIFromFileEntry(&SkippedFile); + if (!URI) + return; + auto I = IG.try_emplace(*URI); + assert(!I.second && "File inserted for the first time on skip."); + assert(I.first->getKeyData() == I.first->getValue().URI.data() && + "Node have not been populated yet"); +#endif + } + +private: + const SourceManager &SM; + IncludeGraph &IG; +}; + // Wraps the index action and reports index data after each translation unit. class IndexAction : public WrapperFrontendAction { public: @@ -16,15 +111,20 @@ std::unique_ptr Includes, const index::IndexingOptions &Opts, std::function SymbolsCallback, - std::function RefsCallback) + std::function RefsCallback, + std::function IncludeGraphCallback) : WrapperFrontendAction(index::createIndexingAction(C, Opts, nullptr)), SymbolsCallback(SymbolsCallback), RefsCallback(RefsCallback), - Collector(C), Includes(std::move(Includes)), + IncludeGraphCallback(IncludeGraphCallback), Collector(C), + Includes(std::move(Includes)), PragmaHandler(collectIWYUHeaderMaps(this->Includes.get())) {} std::unique_ptr CreateASTConsumer(CompilerInstance &CI, StringRef InFile) override { CI.getPreprocessor().addCommentHandler(PragmaHandler.get()); + if (IncludeGraphCallback != nullptr) + CI.getPreprocessor().addPPCallbacks( + llvm::make_unique(CI.getSourceManager(), IG)); return WrapperFrontendAction::CreateASTConsumer(CI, InFile); } @@ -46,22 +146,32 @@ SymbolsCallback(Collector->takeSymbols()); if (RefsCallback != nullptr) RefsCallback(Collector->takeRefs()); + if (IncludeGraphCallback != nullptr) { +#ifndef NDEBUG + for (const auto &Node : IG) + assert(Node.getKeyData() == Node.getValue().URI.data()); +#endif + IncludeGraphCallback(std::move(IG)); + } } private: std::function SymbolsCallback; std::function RefsCallback; + std::function IncludeGraphCallback; std::shared_ptr Collector; std::unique_ptr Includes; std::unique_ptr PragmaHandler; + IncludeGraph IG; }; } // namespace -std::unique_ptr -createStaticIndexingAction(SymbolCollector::Options Opts, - std::function SymbolsCallback, - std::function RefsCallback) { +std::unique_ptr createStaticIndexingAction( + SymbolCollector::Options Opts, + std::function SymbolsCallback, + std::function RefsCallback, + std::function IncludeGraphCallback) { index::IndexingOptions IndexOpts; IndexOpts.SystemSymbolFilter = index::IndexingOptions::SystemSymbolFilterKind::All; @@ -77,7 +187,7 @@ Opts.Includes = Includes.get(); return llvm::make_unique( std::make_shared(std::move(Opts)), std::move(Includes), - IndexOpts, SymbolsCallback, RefsCallback); + IndexOpts, SymbolsCallback, RefsCallback, IncludeGraphCallback); } } // namespace clangd Index: unittests/clangd/CMakeLists.txt =================================================================== --- unittests/clangd/CMakeLists.txt +++ unittests/clangd/CMakeLists.txt @@ -28,6 +28,7 @@ FuzzyMatchTests.cpp GlobalCompilationDatabaseTests.cpp HeadersTests.cpp + IndexActionTests.cpp IndexTests.cpp JSONTransportTests.cpp QualityTests.cpp Index: unittests/clangd/IndexActionTests.cpp =================================================================== --- /dev/null +++ unittests/clangd/IndexActionTests.cpp @@ -0,0 +1,219 @@ +//===------ IndexActionTests.cpp -------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "TestFS.h" +#include "index/IndexAction.h" +#include "clang/Tooling/Tooling.h" +#include "gmock/gmock.h" +#include "gtest/gtest.h" + +namespace clang { +namespace clangd { +namespace { + +using ::testing::AllOf; +using ::testing::ElementsAre; +using ::testing::Not; +using ::testing::Pair; +using ::testing::UnorderedElementsAre; +using ::testing::UnorderedPointwise; + +std::string PathToURI(llvm::StringRef Path) { + return URI::create(Path).toString(); +} + +MATCHER(IsTU, "") { + const IncludeGraphNode &Node = arg; + return Node.IsTU; +} + +MATCHER_P(HasDigest, Digest, "") { + const IncludeGraphNode &Node = arg; + return Node.Digest == Digest; +} + +MATCHER(HasSameURI, "") { + llvm::StringRef URI = testing::get<0>(arg); + const std::string &Path = testing::get<1>(arg); + return PathToURI(Path) == URI; +} + +testing::Matcher +IncludesAre(const std::vector &Includes) { + return ::testing::Field(&IncludeGraphNode::DirectIncludes, + UnorderedPointwise(HasSameURI(), Includes)); +} + +class IndexActionTest : public ::testing::Test { +public: + IndexActionTest() : InMemoryFileSystem(new llvm::vfs::InMemoryFileSystem) {} + + void runIndexingAction(llvm::StringRef MainFilePath, + const std::vector &ExtraArgs = {}) { + IntrusiveRefCntPtr Files( + new FileManager(FileSystemOptions(), InMemoryFileSystem)); + + auto Action = createStaticIndexingAction( + SymbolCollector::Options(), + [&](SymbolSlab S) { Symbols = std::move(S); }, + [&](RefSlab R) { Refs = std::move(R); }, + [&](IncludeGraph IG) { this->IG = std::move(IG); }); + + std::vector Args = {"index_action", "-fsyntax-only", + "-xc++", "-std=c++11", + "-iquote", testRoot()}; + Args.insert(Args.end(), ExtraArgs.begin(), ExtraArgs.end()); + Args.push_back(MainFilePath); + + tooling::ToolInvocation Invocation( + Args, Action.release(), Files.get(), + std::make_shared()); + + Invocation.run(); + } + + void addFile(llvm::StringRef Path, llvm::StringRef Content) { + InMemoryFileSystem->addFile(Path, 0, + llvm::MemoryBuffer::getMemBuffer(Content)); + } + +protected: + IntrusiveRefCntPtr InMemoryFileSystem; + SymbolSlab Symbols; + RefSlab Refs; + IncludeGraph IG; + SymbolCollector::Options CollectorOpts; +}; + +TEST_F(IndexActionTest, CollectIncludeGraph) { + std::string MainFilePath = testPath("main.cpp"); + std::pair Level1Header = {testPath("level1.h"), + "#include \"level2.h\""}; + std::pair Level2Header = {testPath("level2.h"), ""}; + + std::string MainCode = R"cpp( + #include "level1.h" + )cpp"; + addFile(MainFilePath, MainCode); + addFile(Level1Header.first, Level1Header.second); + addFile(Level2Header.first, Level2Header.second); + + runIndexingAction(MainFilePath); + std::vector> IGFlattened; + for (auto &I : IG) + IGFlattened.push_back({I.getKey(), I.getValue()}); + + EXPECT_THAT(IGFlattened, + UnorderedElementsAre( + Pair(PathToURI(MainFilePath), + AllOf(IsTU(), IncludesAre({Level1Header.first}), + HasDigest(digest(MainCode)))), + Pair(PathToURI(Level1Header.first), + AllOf(Not(IsTU()), IncludesAre({Level2Header.first}), + HasDigest(digest(Level1Header.second)))), + Pair(PathToURI(Level2Header.first), + AllOf(Not(IsTU()), IncludesAre({}), + HasDigest(digest(Level2Header.second)))))); + + for (const auto &Path : + {MainFilePath, Level1Header.first, Level2Header.first}) { + auto URI = PathToURI(Path); + const auto &Node = IG.lookup(URI); + EXPECT_EQ(Node.URI.data(), IG.find(URI)->getKeyData()); + } +} + +TEST_F(IndexActionTest, IncludeGraphSelfInclude) { + std::string MainFilePath = testPath("main.cpp"); + std::pair Header = {testPath("header.h"), + R"cpp( + #ifndef _GUARD_ + #define _GUARD_ + #include "header.h" + #endif + )cpp"}; + std::string MainCode = R"cpp( + #include "header.h" + )cpp"; + + addFile(MainFilePath, MainCode); + addFile(Header.first, Header.second); + + runIndexingAction(MainFilePath); + std::vector> IGFlattened; + for (auto &I : IG) + IGFlattened.push_back({I.getKey(), I.getValue()}); + + EXPECT_THAT( + IGFlattened, + UnorderedElementsAre(Pair(PathToURI(MainFilePath), + AllOf(IsTU(), IncludesAre({Header.first}), + HasDigest(digest(MainCode)))), + Pair(PathToURI(Header.first), + AllOf(Not(IsTU()), IncludesAre({Header.first}), + HasDigest(digest(Header.second)))))); + + for (const auto &Path : {MainFilePath, Header.first}) { + auto URI = PathToURI(Path); + const auto &Node = IG.lookup(URI); + EXPECT_EQ(Node.URI.data(), IG.find(URI)->getKeyData()); + } +} + +TEST_F(IndexActionTest, IncludeGraphSkippedFile) { + std::string MainFilePath = testPath("main.cpp"); + std::pair CommonHeader = {testPath("common.h"), + R"cpp( + #ifndef _GUARD_ + #define _GUARD_ + void f(); + #endif + )cpp"}; + std::pair Header = {testPath("header.h"), + R"cpp( + #include "common.h" + void g(); + )cpp"}; + std::string MainCode = R"cpp( + #include "common.h" + #include "header.h" + )cpp"; + + addFile(MainFilePath, MainCode); + addFile(Header.first, Header.second); + addFile(CommonHeader.first, CommonHeader.second); + + runIndexingAction(MainFilePath); + std::vector> IGFlattened; + for (auto &I : IG) + IGFlattened.push_back({I.getKey(), I.getValue()}); + + EXPECT_THAT( + IGFlattened, + UnorderedElementsAre( + Pair(PathToURI(MainFilePath), + AllOf(IsTU(), IncludesAre({Header.first, CommonHeader.first}), + HasDigest(digest(MainCode)))), + Pair(PathToURI(Header.first), + AllOf(Not(IsTU()), IncludesAre({CommonHeader.first}), + HasDigest(digest(Header.second)))), + Pair(PathToURI(CommonHeader.first), + AllOf(Not(IsTU()), IncludesAre({}), + HasDigest(digest(CommonHeader.second)))))); + + for (const auto &Path : {MainFilePath, Header.first, CommonHeader.first}) { + auto URI = PathToURI(Path); + const auto &Node = IG.lookup(URI); + EXPECT_EQ(Node.URI.data(), IG.find(URI)->getKeyData()); + } +} + +} // namespace +} // namespace clangd +} // namespace clang