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,18 @@ // in any non-preamble inclusions. class IncludeStructure { public: - std::vector MainFileIncludes; + // HeaderID identifies file in the include graph. It corresponds to a + // FileEntry rather than a FileID, but stays stable across preamble & main + // file builds. + 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 +132,23 @@ // 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: + std::vector RealPathNames; // In HeaderID order. + // HeaderID maps the FileEntry::Name to the internal representation. // 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; + // builds is surprisingly hard. FileID is unavailable in + // InclusionDirective(), and RealPathName and UniqueID are not preserved in + // the preamble. + llvm::StringMap NameToIndex; }; /// Returns a PPCallback that visits all inclusions in the main file. @@ -205,4 +214,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,45 @@ 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(); + std::string &RealPathName = RealPathNames[static_cast(Result)]; + if (RealPathName.empty()) + RealPathName = Entry->tryGetRealPathName().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 +201,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" @@ -29,8 +30,10 @@ using ::testing::AllOf; using ::testing::Contains; using ::testing::ElementsAre; +using ::testing::IsEmpty; using ::testing::Not; using ::testing::UnorderedElementsAre; +using ::testing::UnorderedElementsAreArray; class HeadersTest : public ::testing::Test { public: @@ -64,8 +67,15 @@ } protected: + IncludeStructure::HeaderID getID(StringRef Filename, + IncludeStructure &Includes) { + 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 +91,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 +117,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 +136,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 +145,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) { @@ -148,12 +159,14 @@ std::string BarHeader = testPath("sub/bar.h"); FS.Files[BarHeader] = ""; - EXPECT_THAT(collectIncludes().MainFileIncludes, + auto Includes = collectIncludes(); + EXPECT_THAT(Includes.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, Includes)), + UnorderedElementsAre( + Distance(getID(MainFile, Includes), 0u), + Distance(getID(testPath("sub/bar.h"), Includes), 1u))); } TEST_F(HeadersTest, OnlyCollectInclusionsInMain) { @@ -166,17 +179,21 @@ FS.Files[MainFile] = R"cpp( #include "bar.h" )cpp"; + auto Includes = collectIncludes(); 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(Includes.includeDepth(getID(MainFile, Includes)), + UnorderedElementsAre( + Distance(getID(MainFile, Includes), 0u), + Distance(getID(testPath("sub/bar.h"), Includes), 1u), + Distance(getID(testPath("sub/baz.h"), Includes), 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"), Includes)), + UnorderedElementsAre( + Distance(getID(testPath("sub/bar.h"), Includes), 0u), + Distance(getID(testPath("sub/baz.h"), Includes), 1u))); } TEST_F(HeadersTest, PreambleIncludesPresentOnce) { @@ -202,8 +219,33 @@ EXPECT_THAT(collectIncludes().MainFileIncludes, UnorderedElementsAre(AllOf(Written("\"foo.h\""), Resolved("")))); - EXPECT_THAT(collectIncludes().includeDepth(MainFile), - UnorderedElementsAre(Distance(MainFile, 0u))); + EXPECT_THAT(collectIncludes().IncludeChildren, IsEmpty()); +} + +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, Includes)], + UnorderedElementsAreArray( + {getID(FooHeader, Includes), getID(BarHeader, Includes)})); + EXPECT_THAT(Includes.IncludeChildren[getID(BarHeader, Includes)], IsEmpty()); + EXPECT_THAT(Includes.IncludeChildren[getID(FooHeader, Includes)], + UnorderedElementsAreArray( + {getID(BarHeader, Includes), getID(BazHeader, Includes)})); + EXPECT_THAT(Includes.IncludeChildren[getID(BazHeader, Includes)], IsEmpty()); } 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 @@ -44,9 +44,11 @@ namespace { using ::testing::AllOf; +using ::testing::Contains; using ::testing::ElementsAre; using ::testing::ElementsAreArray; using ::testing::IsEmpty; +using ::testing::UnorderedElementsAreArray; MATCHER_P(DeclNamed, Name, "") { if (NamedDecl *ND = dyn_cast(arg)) @@ -493,7 +495,7 @@ auto EmptyPreamble = buildPreamble(testPath("foo.cpp"), *CI, Inputs, true, nullptr); ASSERT_TRUE(EmptyPreamble); - EXPECT_THAT(EmptyPreamble->Includes.MainFileIncludes, testing::IsEmpty()); + EXPECT_THAT(EmptyPreamble->Includes.MainFileIncludes, IsEmpty()); // Now build an AST using empty preamble and ensure patched includes worked. TU.Code = ModifiedContents.str(); @@ -507,18 +509,17 @@ EXPECT_THAT(PatchedAST->getIncludeStructure().MainFileIncludes, testing::Pointwise( EqInc(), ExpectedAST.getIncludeStructure().MainFileIncludes)); - auto StringMapToVector = [](const llvm::StringMap SM) { - std::vector> Res; - for (const auto &E : SM) - Res.push_back({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 &FM = PatchedAST->getSourceManager().getFileManager(); + // Copy so that we can use operator[] to get the children. + IncludeStructure Includes = PatchedAST->getIncludeStructure(); + auto MainFE = FM.getFile(testPath("foo.cpp")); + ASSERT_TRUE(MainFE); + auto MainID = Includes.getID(*MainFE); + auto AuxFE = FM.getFile(testPath("sub/aux.h")); + ASSERT_TRUE(AuxFE); + auto AuxID = Includes.getID(*AuxFE); + EXPECT_THAT(Includes.IncludeChildren[*MainID], Contains(AuxID)); } TEST(ParsedASTTest, PatchesDeletedIncludes) { @@ -551,18 +552,20 @@ EXPECT_THAT(PatchedAST->getIncludeStructure().MainFileIncludes, testing::Pointwise( EqInc(), ExpectedAST.getIncludeStructure().MainFileIncludes)); - auto StringMapToVector = [](const llvm::StringMap SM) { - std::vector> Res; - for (const auto &E : SM) - Res.push_back({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 &FM = ExpectedAST.getSourceManager().getFileManager(); + // Copy so that we can getOrCreateID(). + IncludeStructure Includes = ExpectedAST.getIncludeStructure(); + auto MainFE = FM.getFile(testPath("foo.cpp")); + ASSERT_TRUE(MainFE); + auto MainID = Includes.getOrCreateID(*MainFE); + auto &PatchedFM = PatchedAST->getSourceManager().getFileManager(); + IncludeStructure PatchedIncludes = PatchedAST->getIncludeStructure(); + auto PatchedMainFE = PatchedFM.getFile(testPath("foo.cpp")); + ASSERT_TRUE(PatchedMainFE); + auto PatchedMainID = PatchedIncludes.getOrCreateID(*PatchedMainFE); + EXPECT_EQ(Includes.includeDepth(MainID), + PatchedIncludes.includeDepth(PatchedMainID)); } // Returns Code guarded by #ifndef guards