Index: clang-tools-extra/trunk/clangd/Headers.h =================================================================== --- clang-tools-extra/trunk/clangd/Headers.h +++ clang-tools-extra/trunk/clangd/Headers.h @@ -46,7 +46,7 @@ unsigned HashOffset = 0; // Byte offset from start of file to #. SrcMgr::CharacteristicKind FileKind = SrcMgr::C_User; }; -llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Inclusion&); +llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Inclusion &); // Contains information about one file in the build grpah and its direct // dependencies. Doesn't own the strings it references (IncludeGraph is @@ -60,6 +60,8 @@ }; // FileURI and FileInclusions are references to keys of the map containing // them. +// Important: The graph generated by those callbacks might contain cycles, self +// edges and multi edges. using IncludeGraph = llvm::StringMap; // Information captured about the inclusion graph in a translation unit. 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 @@ -342,7 +342,8 @@ RefSlab Refs; auto Action = createStaticIndexingAction( IndexOpts, [&](SymbolSlab S) { Symbols = std::move(S); }, - [&](RefSlab R) { Refs = std::move(R); }); + [&](RefSlab R) { Refs = std::move(R); }, + /*IncludeGraphCallback=*/nullptr); // We're going to run clang here, and it could potentially crash. // We could use CrashRecoveryContext to try to make indexing crashes nonfatal, Index: clang-tools-extra/trunk/clangd/index/IndexAction.h =================================================================== --- clang-tools-extra/trunk/clangd/index/IndexAction.h +++ clang-tools-extra/trunk/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); } // namespace clangd } // namespace clang Index: clang-tools-extra/trunk/clangd/index/IndexAction.cpp =================================================================== --- clang-tools-extra/trunk/clangd/index/IndexAction.cpp +++ clang-tools-extra/trunk/clangd/index/IndexAction.cpp @@ -9,6 +9,98 @@ namespace clangd { namespace { +llvm::Optional toURI(const FileEntry *File) { + if (!File) + return llvm::None; + auto AbsolutePath = File->tryGetRealPathName(); + if (AbsolutePath.empty()) + return llvm::None; + return URI::create(AbsolutePath).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 everything except direct includes for a node, which represents + // edges in the include graph and populated in inclusion directive. + // We cannot populate the fields in InclusionDirective because it does not + // have access to the contents of the included file. + 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 = toURI(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 = toURI(File); + if (!IncludeURI) + return; + + auto IncludingURI = toURI(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 = toURI(&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 +108,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 +143,33 @@ SymbolsCallback(Collector->takeSymbols()); if (RefsCallback != nullptr) RefsCallback(Collector->takeRefs()); + if (IncludeGraphCallback != nullptr) { +#ifndef NDEBUG + // This checks if all nodes are initialized. + 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 +185,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: clang-tools-extra/trunk/clangd/indexer/IndexerMain.cpp =================================================================== --- clang-tools-extra/trunk/clangd/indexer/IndexerMain.cpp +++ clang-tools-extra/trunk/clangd/indexer/IndexerMain.cpp @@ -62,7 +62,8 @@ for (const auto &Ref : Sym.second) Refs.insert(Sym.first, Ref); } - }) + }, + /*IncludeGraphCallback=*/nullptr) .release(); } Index: clang-tools-extra/trunk/unittests/clangd/CMakeLists.txt =================================================================== --- clang-tools-extra/trunk/unittests/clangd/CMakeLists.txt +++ clang-tools-extra/trunk/unittests/clangd/CMakeLists.txt @@ -28,6 +28,7 @@ FuzzyMatchTests.cpp GlobalCompilationDatabaseTests.cpp HeadersTests.cpp + IndexActionTests.cpp IndexTests.cpp JSONTransportTests.cpp QualityTests.cpp Index: clang-tools-extra/trunk/unittests/clangd/IndexActionTests.cpp =================================================================== --- clang-tools-extra/trunk/unittests/clangd/IndexActionTests.cpp +++ clang-tools-extra/trunk/unittests/clangd/IndexActionTests.cpp @@ -0,0 +1,230 @@ +//===------ 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 toUri(llvm::StringRef Path) { return URI::create(Path).toString(); } + +MATCHER(IsTU, "") { return arg.IsTU; } + +MATCHER_P(HasDigest, Digest, "") { return arg.Digest == Digest; } + +MATCHER(HasSameURI, "") { + llvm::StringRef URI = testing::get<0>(arg); + const std::string &Path = testing::get<1>(arg); + return toUri(Path) == URI; +} + +testing::Matcher +IncludesAre(const std::vector &Includes) { + return ::testing::Field(&IncludeGraphNode::DirectIncludes, + UnorderedPointwise(HasSameURI(), Includes)); +} + +void checkNodesAreInitialized(const IndexFileIn &IndexFile, + const std::vector &Paths) { + EXPECT_THAT(Paths.size(), IndexFile.Sources->size()); + for (llvm::StringRef Path : Paths) { + auto URI = toUri(Path); + const auto &Node = IndexFile.Sources->lookup(URI); + // Uninitialized nodes will have an empty URI. + EXPECT_EQ(Node.URI.data(), IndexFile.Sources->find(URI)->getKeyData()); + } +} + +std::map toMap(const IncludeGraph &IG) { + std::map Nodes; + for (auto &I : IG) + Nodes.emplace(I.getKey(), I.getValue()); + return Nodes; +} + +class IndexActionTest : public ::testing::Test { +public: + IndexActionTest() : InMemoryFileSystem(new llvm::vfs::InMemoryFileSystem) {} + + IndexFileIn + runIndexingAction(llvm::StringRef MainFilePath, + const std::vector &ExtraArgs = {}) { + IndexFileIn IndexFile; + IntrusiveRefCntPtr Files( + new FileManager(FileSystemOptions(), InMemoryFileSystem)); + + auto Action = createStaticIndexingAction( + SymbolCollector::Options(), + [&](SymbolSlab S) { IndexFile.Symbols = std::move(S); }, + [&](RefSlab R) { IndexFile.Refs = std::move(R); }, + [&](IncludeGraph IG) { IndexFile.Sources = 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(); + + checkNodesAreInitialized(IndexFile, FilePaths); + return IndexFile; + } + + void addFile(llvm::StringRef Path, llvm::StringRef Content) { + InMemoryFileSystem->addFile(Path, 0, + llvm::MemoryBuffer::getMemBuffer(Content)); + FilePaths.push_back(Path); + } + +protected: + std::vector FilePaths; + IntrusiveRefCntPtr InMemoryFileSystem; +}; + +TEST_F(IndexActionTest, CollectIncludeGraph) { + std::string MainFilePath = testPath("main.cpp"); + std::string MainCode = "#include \"level1.h\""; + std::string Level1HeaderPath = testPath("level1.h"); + std::string Level1HeaderCode = "#include \"level2.h\""; + std::string Level2HeaderPath = testPath("level2.h"); + std::string Level2HeaderCode = ""; + + addFile(MainFilePath, MainCode); + addFile(Level1HeaderPath, Level1HeaderCode); + addFile(Level2HeaderPath, Level2HeaderCode); + + IndexFileIn IndexFile = runIndexingAction(MainFilePath); + auto Nodes = toMap(*IndexFile.Sources); + + EXPECT_THAT(Nodes, + UnorderedElementsAre( + Pair(toUri(MainFilePath), + AllOf(IsTU(), IncludesAre({Level1HeaderPath}), + HasDigest(digest(MainCode)))), + Pair(toUri(Level1HeaderPath), + AllOf(Not(IsTU()), IncludesAre({Level2HeaderPath}), + HasDigest(digest(Level1HeaderCode)))), + Pair(toUri(Level2HeaderPath), + AllOf(Not(IsTU()), IncludesAre({}), + HasDigest(digest(Level2HeaderCode)))))); +} + +TEST_F(IndexActionTest, IncludeGraphSelfInclude) { + std::string MainFilePath = testPath("main.cpp"); + std::string MainCode = "#include \"header.h\""; + std::string HeaderPath = testPath("header.h"); + std::string HeaderCode = R"cpp( + #ifndef _GUARD_ + #define _GUARD_ + #include "header.h" + #endif)cpp"; + + addFile(MainFilePath, MainCode); + addFile(HeaderPath, HeaderCode); + + IndexFileIn IndexFile = runIndexingAction(MainFilePath); + auto Nodes = toMap(*IndexFile.Sources); + + EXPECT_THAT( + Nodes, + UnorderedElementsAre( + Pair(toUri(MainFilePath), AllOf(IsTU(), IncludesAre({HeaderPath}), + HasDigest(digest(MainCode)))), + Pair(toUri(HeaderPath), AllOf(Not(IsTU()), IncludesAre({HeaderPath}), + HasDigest(digest(HeaderCode)))))); +} + +TEST_F(IndexActionTest, IncludeGraphSkippedFile) { + std::string MainFilePath = testPath("main.cpp"); + std::string MainCode = R"cpp( + #include "common.h" + #include "header.h" + )cpp"; + + std::string CommonHeaderPath = testPath("common.h"); + std::string CommonHeaderCode = R"cpp( + #ifndef _GUARD_ + #define _GUARD_ + void f(); + #endif)cpp"; + + std::string HeaderPath = testPath("header.h"); + std::string HeaderCode = R"cpp( + #include "common.h" + void g();)cpp"; + + addFile(MainFilePath, MainCode); + addFile(HeaderPath, HeaderCode); + addFile(CommonHeaderPath, CommonHeaderCode); + + IndexFileIn IndexFile = runIndexingAction(MainFilePath); + auto Nodes = toMap(*IndexFile.Sources); + + EXPECT_THAT( + Nodes, UnorderedElementsAre( + Pair(toUri(MainFilePath), + AllOf(IsTU(), IncludesAre({HeaderPath, CommonHeaderPath}), + HasDigest(digest(MainCode)))), + Pair(toUri(HeaderPath), + AllOf(Not(IsTU()), IncludesAre({CommonHeaderPath}), + HasDigest(digest(HeaderCode)))), + Pair(toUri(CommonHeaderPath), + AllOf(Not(IsTU()), IncludesAre({}), + HasDigest(digest(CommonHeaderCode)))))); +} + +TEST_F(IndexActionTest, IncludeGraphDynamicInclude) { + std::string MainFilePath = testPath("main.cpp"); + std::string MainCode = R"cpp( + #ifndef FOO + #define FOO "main.cpp" + #else + #define FOO "header.h" + #endif + + #include FOO)cpp"; + std::string HeaderPath = testPath("header.h"); + std::string HeaderCode = ""; + + addFile(MainFilePath, MainCode); + addFile(HeaderPath, HeaderCode); + + IndexFileIn IndexFile = runIndexingAction(MainFilePath); + auto Nodes = toMap(*IndexFile.Sources); + + EXPECT_THAT( + Nodes, + UnorderedElementsAre( + Pair(toUri(MainFilePath), + AllOf(IsTU(), IncludesAre({MainFilePath, HeaderPath}), + HasDigest(digest(MainCode)))), + Pair(toUri(HeaderPath), AllOf(Not(IsTU()), IncludesAre({}), + HasDigest(digest(HeaderCode)))))); +} + +} // namespace +} // namespace clangd +} // namespace clang