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,14 +1379,16 @@ 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; + auto MainFileID = + Includes.getOrCreateID(SM.getFileEntryForID(SM.getMainFileID())); + for (auto &HeaderIDAndDepth : Includes.includeDepth(MainFileID)) { + auto &Source = + ProxSources[Includes.getRealPath(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 (Entry.getValue() > 0) + if (HeaderIDAndDepth.getSecond() > 0) Source.MaxUpTraversals = 1; } 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,19 @@ // 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. + // HeaderID is mapping the FileEntry::Name to the internal representation. + enum class HeaderID : unsigned {}; + + llvm::Optional getID(const FileEntry *Entry) const; + HeaderID getOrCreateID(const FileEntry *Entry); + + StringRef getRealPath(HeaderID ID) const { + assert(static_cast(ID) <= RealPathNames.size()); + return RealPathNames[static_cast(ID)]; + } // Return all transitively reachable files. llvm::ArrayRef allHeaders() const { return RealPathNames; } @@ -120,26 +133,21 @@ // Return all transitively reachable files, and their minimum include depth. // 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; + // Root is the ID of the header being visited first. + // Usually it is getID(SM.getFileEntryForID(SM.getMainFileID())->getName()). + llvm::DenseMap includeDepth(HeaderID Root) const; + + // Maps HeaderID to the ids of the files included from it. + llvm::DenseMap> IncludeChildren; - // This updates IncludeDepth(), but not MainFileIncludes. - void recordInclude(llvm::StringRef IncludingName, - llvm::StringRef IncludedName, - llvm::StringRef IncludedRealName); + 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. - // Maps a file's index to that of the files it includes. - llvm::DenseMap> IncludeChildren; + std::vector RealPathNames; // In HeaderID order. + // HeaderID identifies file in the include graph. It corresponds to a + // FileEntry rather than a FileID, but stays stable across preamble & main + // file builds. + llvm::StringMap NameToIndex; }; /// Returns a PPCallback that visits all inclusions in the main file. @@ -205,4 +213,31 @@ } // namespace clangd } // namespace clang +namespace llvm { + +// Support Tokens as DenseMap keys. +template <> struct DenseMapInfo { + static inline clang::clangd::IncludeStructure::HeaderID getEmptyKey() { + return static_cast( + DenseMapInfo::getEmptyKey()); + } + + static inline clang::clangd::IncludeStructure::HeaderID getTombstoneKey() { + return static_cast( + DenseMapInfo::getTombstoneKey()); + } + + static unsigned + getHashValue(const clang::clangd::IncludeStructure::HeaderID &Tag) { + return hash_value(static_cast(Tag)); + } + + static bool isEqual(const clang::clangd::IncludeStructure::HeaderID &LHS, + const clang::clangd::IncludeStructure::HeaderID &RHS) { + return LHS == RHS; + } +}; + +} // namespace llvm + #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_HEADERS_H 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 @@ -67,8 +67,9 @@ // Treat as if included from the main file. IncludingFileEntry = SM.getFileEntryForID(MainFID); } - Out->recordInclude(IncludingFileEntry->getName(), File->getName(), - File->tryGetRealPathName()); + auto IncludingID = Out->getOrCreateID(IncludingFileEntry), + IncludedID = Out->getOrCreateID(File); + Out->IncludeChildren[IncludingID].push_back(IncludedID); } } @@ -154,38 +155,46 @@ return std::make_unique(SM, Out); } -void IncludeStructure::recordInclude(llvm::StringRef IncludingName, - llvm::StringRef IncludedName, - llvm::StringRef IncludedRealName) { - auto Child = fileIndex(IncludedName); - if (!IncludedRealName.empty() && RealPathNames[Child].empty()) - RealPathNames[Child] = std::string(IncludedRealName); - auto Parent = fileIndex(IncludingName); - IncludeChildren[Parent].push_back(Child); +llvm::Optional +IncludeStructure::getID(const FileEntry *Entry) const { + auto It = NameToIndex.find(Entry->getName()); + if (It == NameToIndex.end()) + return llvm::None; + return It->second; } -unsigned IncludeStructure::fileIndex(llvm::StringRef Name) { - auto R = NameToIndex.try_emplace(Name, RealPathNames.size()); +IncludeStructure::HeaderID +IncludeStructure::getOrCreateID(const FileEntry *Entry) { + auto R = NameToIndex.try_emplace( + Entry->getName(), + static_cast(RealPathNames.size())); if (R.second) RealPathNames.emplace_back(); - return R.first->getValue(); + IncludeStructure::HeaderID Result = R.first->getValue(); + auto RealPathName = Entry->tryGetRealPathName(); + if (!RealPathName.empty() && + RealPathNames[static_cast(Result)].empty()) + RealPathNames[static_cast(Result)] = RealPathName.str(); + return Result; } -llvm::StringMap -IncludeStructure::includeDepth(llvm::StringRef Root) const { +llvm::DenseMap +IncludeStructure::includeDepth(HeaderID Root) const { // Include depth 0 is the main file only. - llvm::StringMap 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); + llvm::DenseMap Result; + if (static_cast(Root) >= RealPathNames.size()) { + elog("Requested includeDepth for {0} which doesn't exist IncludeStructure", + static_cast(Root)); + return Result; } + Result[Root] = 0; + std::vector CurrentLevel; + CurrentLevel.push_back(Root); + llvm::DenseSet Seen; + Seen.insert(Root); // Each round of BFS traversal finds the next depth level. - std::vector PreviousLevel; + std::vector PreviousLevel; for (unsigned Level = 1; !CurrentLevel.empty(); ++Level) { PreviousLevel.clear(); PreviousLevel.swap(CurrentLevel); @@ -193,10 +202,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[static_cast(Child)].empty()) + Result[Child] = Level; } } } 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,15 @@ } protected: + IncludeStructure::HeaderID getID(StringRef Filename) { + auto Includes = collectIncludes(); + auto Entry = Clang->getSourceManager().getFileManager().getFile(Filename); + EXPECT_TRUE(Entry); + return Includes.getOrCreateID(*Entry); + } + IncludeStructure collectIncludes() { - auto Clang = setupClang(); + Clang = setupClang(); PreprocessOnlyAction Action; EXPECT_TRUE( Action.BeginSourceFile(*Clang, Clang->getFrontendOpts().Inputs[0])); @@ -81,7 +90,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 +116,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 +135,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 +144,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 =" << static_cast(arg.getFirst()); + if (arg.getSecond() != D) + *result_listener << "distance =" << arg.getSecond(); + return arg.getFirst() == File && arg.getSecond() == D; } TEST_F(HeadersTest, CollectRewrittenAndResolved) { @@ -151,9 +161,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 +179,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 +212,31 @@ EXPECT_THAT(collectIncludes().MainFileIncludes, UnorderedElementsAre(AllOf(Written("\"foo.h\""), Resolved("")))); - EXPECT_THAT(collectIncludes().includeDepth(MainFile), - UnorderedElementsAre(Distance(MainFile, 0u))); + EXPECT_TRUE(collectIncludes().IncludeChildren.empty()); +} + +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.IncludeChildren[getID(MainFile)], + UnorderedElementsAreArray({getID(FooHeader), getID(BarHeader)})); + EXPECT_TRUE(Includes.IncludeChildren[getID(BarHeader)].empty()); + EXPECT_THAT(Includes.IncludeChildren[getID(FooHeader)], + UnorderedElementsAreArray({getID(BarHeader), getID(BazHeader)})); + EXPECT_TRUE(Includes.IncludeChildren[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 @@ -47,6 +47,7 @@ using ::testing::ElementsAre; using ::testing::ElementsAreArray; using ::testing::IsEmpty; +using ::testing::UnorderedElementsAreArray; MATCHER_P(DeclNamed, Name, "") { if (NamedDecl *ND = dyn_cast(arg)) @@ -507,18 +508,31 @@ 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().getID(*PatchedEntry); + ASSERT_TRUE(bool(PatchedEntryID)); + auto ExpectedEntry = PatchedAST->getSourceManager().getFileManager().getFile( + testPath("foo.cpp")); + ASSERT_TRUE(ExpectedEntry); + auto ExpectedEntryID = PatchedAST->getIncludeStructure().getID(*PatchedEntry); + ASSERT_TRUE(bool(ExpectedEntryID)); + EXPECT_EQ( + Flatten(PatchedAST->getIncludeStructure().includeDepth(*PatchedEntryID), + PatchedAST->getIncludeStructure()), + Flatten(ExpectedAST.getIncludeStructure().includeDepth(*ExpectedEntryID), + ExpectedAST.getIncludeStructure())); } TEST(ParsedASTTest, PatchesDeletedIncludes) { @@ -551,18 +565,31 @@ EXPECT_THAT(PatchedAST->getIncludeStructure().MainFileIncludes, testing::Pointwise( EqInc(), ExpectedAST.getIncludeStructure().MainFileIncludes)); - auto StringMapToVector = [](const llvm::StringMap SM) { + // Ensure file proximity signals are correct. + 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().getID(*PatchedEntry); + ASSERT_TRUE(bool(PatchedEntryID)); + EXPECT_EQ( + Flatten(PatchedAST->getIncludeStructure().includeDepth(*PatchedEntryID), + PatchedAST->getIncludeStructure()) + .size(), + 1u); + EXPECT_TRUE( + Flatten(ExpectedAST.getIncludeStructure().includeDepth(*PatchedEntryID), + ExpectedAST.getIncludeStructure()) + .empty()); } // Returns Code guarded by #ifndef guards