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.getID(SM.getFileEntryForID(SM.getMainFileID())); + if (IncludeStructureID) { + for (auto &HeaderIDAndDepth : + Includes.includeDepth(*IncludeStructureID)) { + 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 (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,21 @@ // 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 getID(const FileEntry *Entry) const; + HeaderID getOrCreateID(const FileEntry *Entry); + + StringRef getRealPath(HeaderID ID) const { + return ID < RealPathNames.size() ? RealPathNames[ID] : StringRef(); + } // Return all transitively reachable files. llvm::ArrayRef allHeaders() const { return RealPathNames; } @@ -121,25 +136,22 @@ // 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); + // This updates IncludeChildren, but not MainFileIncludes. + void recordInclude(HeaderID Including, HeaderID Included); + + // Maps HeaderID to the ids of the files included from it. + llvm::DenseMap> IncludeChildren; + + 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. + // Maps filenames to corresponding HeaderIDs. + llvm::StringMap NameToIndex; }; /// 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 @@ -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,35 +155,40 @@ 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::Expected +IncludeStructure::getID(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; } -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(), 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[Result].empty()) + RealPathNames[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; + 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 +199,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; } } } 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,17 @@ } protected: + IncludeStructure::HeaderID getID(StringRef Filename) { + auto Includes = collectIncludes(); + auto Entry = Clang->getSourceManager().getFileManager().getFile(Filename); + EXPECT_TRUE(Entry); + llvm::Expected EntryID = Includes.getID(*Entry); + EXPECT_TRUE(bool(EntryID)) << EntryID.takeError(); + return *EntryID; + } + IncludeStructure collectIncludes() { - auto Clang = setupClang(); + Clang = setupClang(); PreprocessOnlyAction Action; EXPECT_TRUE( Action.BeginSourceFile(*Clang, Clang->getFrontendOpts().Inputs[0])); @@ -81,7 +92,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 +118,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 +137,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 +146,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 +163,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 +181,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 +214,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)) << PatchedEntryID.takeError(); + auto ExpectedEntry = PatchedAST->getSourceManager().getFileManager().getFile( + testPath("foo.cpp")); + ASSERT_TRUE(ExpectedEntry); + auto ExpectedEntryID = PatchedAST->getIncludeStructure().getID(*PatchedEntry); + ASSERT_TRUE(bool(ExpectedEntryID)) << ExpectedEntryID.takeError(); + 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)) << PatchedEntryID.takeError(); + 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