diff --git a/clang-tools-extra/clangd/CodeComplete.cpp b/clang-tools-extra/clangd/CodeComplete.cpp --- a/clang-tools-extra/clangd/CodeComplete.cpp +++ b/clang-tools-extra/clangd/CodeComplete.cpp @@ -1379,15 +1379,23 @@ FileDistanceOptions ProxOpts{}; // Use defaults. const auto &SM = Recorder->CCSema->getSourceManager(); llvm::StringMap ProxSources; - for (auto &Entry : Includes.includeDepth( - SM.getFileEntryForID(SM.getMainFileID())->getName())) { - auto &Source = ProxSources[Entry.getKey()]; - Source.Cost = Entry.getValue() * ProxOpts.IncludeCost; - // Symbols near our transitive includes are good, but only consider - // things in the same directory or below it. Otherwise there can be - // many false positives. - if (Entry.getValue() > 0) - Source.MaxUpTraversals = 1; + auto IncludeStructureID = + Includes.getFile(SM.getFileEntryForID(SM.getMainFileID())); + if (IncludeStructureID) { + for (auto &HeaderIDAndDepth : + Includes.includeDepth(*IncludeStructureID)) { + auto &Source = + ProxSources[Includes.realPath(HeaderIDAndDepth.getFirst())]; + Source.Cost = HeaderIDAndDepth.getSecond() * ProxOpts.IncludeCost; + // Symbols near our transitive includes are good, but only consider + // things in the same directory or below it. Otherwise there can be + // many false positives. + if (HeaderIDAndDepth.getSecond() > 0) + Source.MaxUpTraversals = 1; + } + } else { + elog("Could not get includeDepth in CodeComplete: {0}", + llvm::toString(IncludeStructureID.takeError())); } FileProximity.emplace(ProxSources, ProxOpts); diff --git a/clang-tools-extra/clangd/Headers.h b/clang-tools-extra/clangd/Headers.h --- a/clang-tools-extra/clangd/Headers.h +++ b/clang-tools-extra/clangd/Headers.h @@ -12,6 +12,7 @@ #include "Protocol.h" #include "SourceCode.h" #include "index/Symbol.h" +#include "support/Logger.h" #include "support/Path.h" #include "clang/Basic/TokenKinds.h" #include "clang/Format/Format.h" @@ -62,7 +63,7 @@ llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Inclusion &); bool operator==(const Inclusion &LHS, const Inclusion &RHS); -// Contains information about one file in the build grpah and its direct +// Contains information about one file in the build graph and its direct // dependencies. Doesn't own the strings it references (IncludeGraph is // self-contained). struct IncludeGraphNode { @@ -112,7 +113,27 @@ // in any non-preamble inclusions. class IncludeStructure { public: - std::vector MainFileIncludes; + // Identifying files in a way that persists from preamble build to subsequent + // builds is surprisingly hard. FileID is unavailable in InclusionDirective(), + // and RealPathName and UniqueID are not preserved in the preamble. + // We use the FileEntry::Name, which is stable, interned into a "file index". + // HeaderID is mapping the FileEntry::Name to the internal representation: + // RealPathName stores header names in the order they were "discovered". + // Main file HeaderID is always 0, hence RealPathName.front() has its name. + using HeaderID = unsigned; + + llvm::Expected getFile(const FileEntry *Entry) const; + + StringRef getRealPath(HeaderID ID) const { + return ID < RealPathNames.size() ? RealPathNames[ID] : StringRef(); + } + + llvm::ArrayRef getIncludedFiles(HeaderID Index) const { + auto It = IncludeChildren.find(Index); + if (It == IncludeChildren.end()) + return {}; + return It->second; + } // Return all transitively reachable files. llvm::ArrayRef allHeaders() const { return RealPathNames; } @@ -121,25 +142,27 @@ // All transitive includes (absolute paths), with their minimum include depth. // Root --> 0, #included file --> 1, etc. // Root is clang's name for a file, which may not be absolute. - // Usually it should be SM.getFileEntryForID(SM.getMainFileID())->getName(). - llvm::StringMap includeDepth(llvm::StringRef Root) const; + // Usually it should be + // getFile(SM.getFileEntryForID(SM.getMainFileID())->getName()). + llvm::DenseMap includeDepth(HeaderID Root) const; // This updates IncludeDepth(), but not MainFileIncludes. void recordInclude(llvm::StringRef IncludingName, llvm::StringRef IncludedName, llvm::StringRef IncludedRealName); + // Create main file entry in the structure. + void setMainFile(const FileEntry *MainFileEntry); + + std::vector MainFileIncludes; + private: - // Identifying files in a way that persists from preamble build to subsequent - // builds is surprisingly hard. FileID is unavailable in InclusionDirective(), - // and RealPathName and UniqueID are not preserved in the preamble. - // We use the FileEntry::Name, which is stable, interned into a "file index". - // The paths we want to expose are the RealPathName, so store those too. std::vector RealPathNames; // In file index order. - unsigned fileIndex(llvm::StringRef Name); - llvm::StringMap NameToIndex; // Values are file indexes. + llvm::StringMap NameToIndex; // Values are file indexes. // Maps a file's index to that of the files it includes. - llvm::DenseMap> IncludeChildren; + llvm::DenseMap> IncludeChildren; + + HeaderID fileIndex(llvm::StringRef Name); }; /// Returns a PPCallback that visits all inclusions in the main file. diff --git a/clang-tools-extra/clangd/Headers.cpp b/clang-tools-extra/clangd/Headers.cpp --- a/clang-tools-extra/clangd/Headers.cpp +++ b/clang-tools-extra/clangd/Headers.cpp @@ -27,7 +27,12 @@ class RecordHeaders : public PPCallbacks { public: RecordHeaders(const SourceManager &SM, IncludeStructure *Out) - : SM(SM), Out(Out) {} + : SM(SM), Out(Out) { + // recordInclude() has not been called yet but the main file should exist + // in the structure. + if (const FileEntry *MainFile = SM.getFileEntryForID(SM.getMainFileID())) + Out->setMainFile(MainFile); + } // Record existing #includes - both written and resolved paths. Only #includes // in the main file are collected. @@ -164,25 +169,35 @@ IncludeChildren[Parent].push_back(Child); } -unsigned IncludeStructure::fileIndex(llvm::StringRef Name) { +IncludeStructure::HeaderID IncludeStructure::fileIndex(llvm::StringRef Name) { auto R = NameToIndex.try_emplace(Name, RealPathNames.size()); if (R.second) RealPathNames.emplace_back(); return R.first->getValue(); } -llvm::StringMap -IncludeStructure::includeDepth(llvm::StringRef Root) const { +llvm::Expected +IncludeStructure::getFile(const FileEntry *Entry) const { + auto It = NameToIndex.find(Entry->getName()); + if (It == NameToIndex.end()) + return error("{0} is not in IncludeStructure", Entry->getName()); + return It->second; +} + +llvm::DenseMap +IncludeStructure::includeDepth(HeaderID Root) const { // Include depth 0 is the main file only. - llvm::StringMap Result; + llvm::DenseMap Result; + if (Root >= RealPathNames.size()) { + elog("Requested includeDepth for {0} which doesn't exist IncludeStructure", + Root); + return Result; + } Result[Root] = 0; std::vector CurrentLevel; - llvm::DenseSet Seen; - auto It = NameToIndex.find(Root); - if (It != NameToIndex.end()) { - CurrentLevel.push_back(It->second); - Seen.insert(It->second); - } + CurrentLevel.push_back(Root); + llvm::DenseSet Seen; + Seen.insert(Root); // Each round of BFS traversal finds the next depth level. std::vector PreviousLevel; @@ -193,10 +208,9 @@ for (const auto &Child : IncludeChildren.lookup(Parent)) { if (Seen.insert(Child).second) { CurrentLevel.push_back(Child); - const auto &Name = RealPathNames[Child]; // Can't include files if we don't have their real path. - if (!Name.empty()) - Result[Name] = Level; + if (!RealPathNames[Child].empty()) + Result[Child] = Level; } } } @@ -204,6 +218,13 @@ return Result; } +void IncludeStructure::setMainFile(const FileEntry *MainFileEntry) { + auto R = + NameToIndex.try_emplace(MainFileEntry->getName(), RealPathNames.size()); + if (R.second) + RealPathNames.emplace_back(); +} + void IncludeInserter::addExisting(const Inclusion &Inc) { IncludedHeaders.insert(Inc.Written); if (!Inc.Resolved.empty()) diff --git a/clang-tools-extra/clangd/unittests/HeadersTests.cpp b/clang-tools-extra/clangd/unittests/HeadersTests.cpp --- a/clang-tools-extra/clangd/unittests/HeadersTests.cpp +++ b/clang-tools-extra/clangd/unittests/HeadersTests.cpp @@ -17,6 +17,7 @@ #include "clang/Frontend/FrontendActions.h" #include "clang/Lex/PreprocessorOptions.h" #include "llvm/ADT/StringRef.h" +#include "llvm/Support/Error.h" #include "llvm/Support/FormatVariadic.h" #include "llvm/Support/Path.h" #include "gmock/gmock.h" @@ -31,6 +32,7 @@ using ::testing::ElementsAre; using ::testing::Not; using ::testing::UnorderedElementsAre; +using ::testing::UnorderedElementsAreArray; class HeadersTest : public ::testing::Test { public: @@ -64,8 +66,18 @@ } protected: + IncludeStructure::HeaderID getID(StringRef Filename) { + auto Includes = collectIncludes(); + auto Entry = Clang->getSourceManager().getFileManager().getFile(Filename); + EXPECT_TRUE(Entry); + llvm::Expected EntryID = + Includes.getFile(*Entry); + EXPECT_TRUE(static_cast(EntryID)); + return *EntryID; + } + IncludeStructure collectIncludes() { - auto Clang = setupClang(); + Clang = setupClang(); PreprocessOnlyAction Action; EXPECT_TRUE( Action.BeginSourceFile(*Clang, Clang->getFrontendOpts().Inputs[0])); @@ -81,7 +93,7 @@ // inserted. std::string calculate(PathRef Original, PathRef Preferred = "", const std::vector &Inclusions = {}) { - auto Clang = setupClang(); + Clang = setupClang(); PreprocessOnlyAction Action; EXPECT_TRUE( Action.BeginSourceFile(*Clang, Clang->getFrontendOpts().Inputs[0])); @@ -107,7 +119,7 @@ } llvm::Optional insert(llvm::StringRef VerbatimHeader) { - auto Clang = setupClang(); + Clang = setupClang(); PreprocessOnlyAction Action; EXPECT_TRUE( Action.BeginSourceFile(*Clang, Clang->getFrontendOpts().Inputs[0])); @@ -126,6 +138,7 @@ std::string Subdir = testPath("sub"); std::string SearchDirArg = (llvm::Twine("-I") + Subdir).str(); IgnoringDiagConsumer IgnoreDiags; + std::unique_ptr Clang; }; MATCHER_P(Written, Name, "") { return arg.Written == Name; } @@ -134,11 +147,11 @@ MATCHER_P(Directive, D, "") { return arg.Directive == D; } MATCHER_P2(Distance, File, D, "") { - if (arg.getKey() != File) - *result_listener << "file =" << arg.getKey().str(); - if (arg.getValue() != D) - *result_listener << "distance =" << arg.getValue(); - return arg.getKey() == File && arg.getValue() == D; + if (arg.getFirst() != File) + *result_listener << "file =" << arg.getFirst(); + if (arg.getSecond() != D) + *result_listener << "distance =" << arg.getSecond(); + return arg.getFirst() == File && arg.getSecond() == D; } TEST_F(HeadersTest, CollectRewrittenAndResolved) { @@ -151,9 +164,9 @@ EXPECT_THAT(collectIncludes().MainFileIncludes, UnorderedElementsAre( AllOf(Written("\"sub/bar.h\""), Resolved(BarHeader)))); - EXPECT_THAT(collectIncludes().includeDepth(MainFile), - UnorderedElementsAre(Distance(MainFile, 0u), - Distance(testPath("sub/bar.h"), 1u))); + EXPECT_THAT(collectIncludes().includeDepth(getID(MainFile)), + UnorderedElementsAre(Distance(getID(MainFile), 0u), + Distance(getID(testPath("sub/bar.h")), 1u))); } TEST_F(HeadersTest, OnlyCollectInclusionsInMain) { @@ -169,14 +182,14 @@ EXPECT_THAT( collectIncludes().MainFileIncludes, UnorderedElementsAre(AllOf(Written("\"bar.h\""), Resolved(BarHeader)))); - EXPECT_THAT(collectIncludes().includeDepth(MainFile), - UnorderedElementsAre(Distance(MainFile, 0u), - Distance(testPath("sub/bar.h"), 1u), - Distance(testPath("sub/baz.h"), 2u))); + EXPECT_THAT(collectIncludes().includeDepth(getID(MainFile)), + UnorderedElementsAre(Distance(getID(MainFile), 0u), + Distance(getID(testPath("sub/bar.h")), 1u), + Distance(getID(testPath("sub/baz.h")), 2u))); // includeDepth() also works for non-main files. - EXPECT_THAT(collectIncludes().includeDepth(testPath("sub/bar.h")), - UnorderedElementsAre(Distance(testPath("sub/bar.h"), 0u), - Distance(testPath("sub/baz.h"), 1u))); + EXPECT_THAT(collectIncludes().includeDepth(getID(testPath("sub/bar.h"))), + UnorderedElementsAre(Distance(getID(testPath("sub/bar.h")), 0u), + Distance(getID(testPath("sub/baz.h")), 1u))); } TEST_F(HeadersTest, PreambleIncludesPresentOnce) { @@ -202,8 +215,32 @@ EXPECT_THAT(collectIncludes().MainFileIncludes, UnorderedElementsAre(AllOf(Written("\"foo.h\""), Resolved("")))); - EXPECT_THAT(collectIncludes().includeDepth(MainFile), - UnorderedElementsAre(Distance(MainFile, 0u))); + EXPECT_THAT(collectIncludes().includeDepth(getID(MainFile)), + UnorderedElementsAre(Distance(getID(MainFile), 0u))); +} + +TEST_F(HeadersTest, IncludedFilesGraph) { + FS.Files[MainFile] = R"cpp( +#include "bar.h" +#include "foo.h" +)cpp"; + std::string BarHeader = testPath("bar.h"); + FS.Files[BarHeader] = ""; + std::string FooHeader = testPath("foo.h"); + FS.Files[FooHeader] = R"cpp( +#include "bar.h" +#include "baz.h" +)cpp"; + std::string BazHeader = testPath("baz.h"); + FS.Files[BazHeader] = ""; + + auto Includes = collectIncludes(); + EXPECT_THAT(Includes.getIncludedFiles(getID(MainFile)), + UnorderedElementsAreArray({getID(FooHeader), getID(BarHeader)})); + EXPECT_TRUE(Includes.getIncludedFiles(getID(BarHeader)).empty()); + EXPECT_THAT(Includes.getIncludedFiles(getID(FooHeader)), + UnorderedElementsAreArray({getID(BarHeader), getID(BazHeader)})); + EXPECT_TRUE(Includes.getIncludedFiles(getID(BazHeader)).empty()); } TEST_F(HeadersTest, IncludeDirective) { diff --git a/clang-tools-extra/clangd/unittests/ParsedASTTests.cpp b/clang-tools-extra/clangd/unittests/ParsedASTTests.cpp --- a/clang-tools-extra/clangd/unittests/ParsedASTTests.cpp +++ b/clang-tools-extra/clangd/unittests/ParsedASTTests.cpp @@ -505,18 +505,33 @@ EXPECT_THAT(PatchedAST->getIncludeStructure().MainFileIncludes, testing::Pointwise( EqInc(), ExpectedAST.getIncludeStructure().MainFileIncludes)); - auto StringMapToVector = [](const llvm::StringMap SM) { + auto Flatten = [](const llvm::DenseMap + &IncludeDepth, + const IncludeStructure &Structure) { std::vector> Res; - for (const auto &E : SM) - Res.push_back({E.first().str(), E.second}); + for (const auto &E : IncludeDepth) + Res.emplace_back(Structure.getRealPath(E.first).str(), E.second); llvm::sort(Res); return Res; }; // Ensure file proximity signals are correct. - EXPECT_EQ(StringMapToVector(PatchedAST->getIncludeStructure().includeDepth( - testPath("foo.cpp"))), - StringMapToVector(ExpectedAST.getIncludeStructure().includeDepth( - testPath("foo.cpp")))); + auto PatchedEntry = PatchedAST->getSourceManager().getFileManager().getFile( + testPath("foo.cpp")); + ASSERT_TRUE(PatchedEntry); + auto PatchedEntryID = + PatchedAST->getIncludeStructure().getFile(*PatchedEntry); + ASSERT_TRUE(static_cast(PatchedEntryID)); + auto ExpectedEntry = PatchedAST->getSourceManager().getFileManager().getFile( + testPath("foo.cpp")); + ASSERT_TRUE(ExpectedEntry); + auto ExpectedEntryID = + PatchedAST->getIncludeStructure().getFile(*PatchedEntry); + ASSERT_TRUE(static_cast(ExpectedEntryID)); + EXPECT_EQ( + Flatten(PatchedAST->getIncludeStructure().includeDepth(*PatchedEntryID), + PatchedAST->getIncludeStructure()), + Flatten(ExpectedAST.getIncludeStructure().includeDepth(*ExpectedEntryID), + ExpectedAST.getIncludeStructure())); } TEST(ParsedASTTest, PatchesDeletedIncludes) { @@ -549,18 +564,33 @@ EXPECT_THAT(PatchedAST->getIncludeStructure().MainFileIncludes, testing::Pointwise( EqInc(), ExpectedAST.getIncludeStructure().MainFileIncludes)); - auto StringMapToVector = [](const llvm::StringMap SM) { + auto Flatten = [](const llvm::DenseMap + &IncludeDepth, + const IncludeStructure &Structure) { std::vector> Res; - for (const auto &E : SM) - Res.push_back({E.first().str(), E.second}); + for (const auto &E : IncludeDepth) + Res.emplace_back(Structure.getRealPath(E.first).str(), E.second); llvm::sort(Res); return Res; }; // Ensure file proximity signals are correct. - EXPECT_EQ(StringMapToVector(PatchedAST->getIncludeStructure().includeDepth( - testPath("foo.cpp"))), - StringMapToVector(ExpectedAST.getIncludeStructure().includeDepth( - testPath("foo.cpp")))); + auto PatchedEntry = PatchedAST->getSourceManager().getFileManager().getFile( + testPath("foo.cpp")); + ASSERT_TRUE(PatchedEntry); + auto PatchedEntryID = + PatchedAST->getIncludeStructure().getFile(*PatchedEntry); + ASSERT_TRUE(static_cast(PatchedEntryID)); + auto ExpectedEntry = PatchedAST->getSourceManager().getFileManager().getFile( + testPath("foo.cpp")); + ASSERT_TRUE(ExpectedEntry); + auto ExpectedEntryID = + PatchedAST->getIncludeStructure().getFile(*PatchedEntry); + ASSERT_TRUE(static_cast(ExpectedEntryID)); + EXPECT_EQ( + Flatten(PatchedAST->getIncludeStructure().includeDepth(*PatchedEntryID), + PatchedAST->getIncludeStructure()), + Flatten(ExpectedAST.getIncludeStructure().includeDepth(*ExpectedEntryID), + ExpectedAST.getIncludeStructure())); } // Returns Code guarded by #ifndef guards