From 230a6edb49c31e2c96613f5b7deefd4f4faf9a6d Mon Sep 17 00:00:00 2001 From: Kirill Bobyrev Date: Thu, 30 Sep 2021 11:36:34 +0200 Subject: [PATCH] Revert "[clangd] Reland D110386" This reverts commits - dd13f45e04366cc4f648b57ec87d20a5569e27c3 - d084c42bdfac4a5879bdabe645b14cf72f7685a7 - 87817bc523daba1d2bd0492144a5d6adba8a649c --- clang-tools-extra/clangd/CodeComplete.cpp | 12 ++-- clang-tools-extra/clangd/Headers.cpp | 61 ++++++++-------- clang-tools-extra/clangd/Headers.h | 84 +++++----------------- .../clangd/unittests/HeadersTests.cpp | 84 ++++++---------------- .../clangd/unittests/ParsedASTTests.cpp | 49 ++++++------- 5 files changed, 97 insertions(+), 193 deletions(-) diff --git a/clang-tools-extra/clangd/CodeComplete.cpp b/clang-tools-extra/clangd/CodeComplete.cpp index 1033e5e..6933881 100644 --- a/clang-tools-extra/clangd/CodeComplete.cpp +++ b/clang-tools-extra/clangd/CodeComplete.cpp @@ -1379,16 +1379,14 @@ public: FileDistanceOptions ProxOpts{}; // Use defaults. const auto &SM = Recorder->CCSema->getSourceManager(); llvm::StringMap ProxSources; - 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; + 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 (HeaderIDAndDepth.getSecond() > 0) + if (Entry.getValue() > 0) Source.MaxUpTraversals = 1; } FileProximity.emplace(ProxSources, ProxOpts); diff --git a/clang-tools-extra/clangd/Headers.cpp b/clang-tools-extra/clangd/Headers.cpp index 0b189e5..111b058 100644 --- a/clang-tools-extra/clangd/Headers.cpp +++ b/clang-tools-extra/clangd/Headers.cpp @@ -67,9 +67,8 @@ public: // Treat as if included from the main file. IncludingFileEntry = SM.getFileEntryForID(MainFID); } - auto IncludingID = Out->getOrCreateID(IncludingFileEntry), - IncludedID = Out->getOrCreateID(File); - Out->IncludeChildren[IncludingID].push_back(IncludedID); + Out->recordInclude(IncludingFileEntry->getName(), File->getName(), + File->tryGetRealPathName()); } } @@ -155,43 +154,38 @@ collectIncludeStructureCallback(const SourceManager &SM, return std::make_unique(SM, Out); } -llvm::Optional -IncludeStructure::getID(const FileEntry *Entry) const { - auto It = NameToIndex.find(Entry->getName()); - if (It == NameToIndex.end()) - return llvm::None; - return It->second; +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); } -IncludeStructure::HeaderID -IncludeStructure::getOrCreateID(const FileEntry *Entry) { - auto R = NameToIndex.try_emplace( - Entry->getName(), - static_cast(RealPathNames.size())); - if (R.second) { +unsigned IncludeStructure::fileIndex(llvm::StringRef Name) { + auto R = NameToIndex.try_emplace(Name, RealPathNames.size()); + if (R.second) RealPathNames.emplace_back(); - FileEntryIDs.push_back(Entry->getUID()); - } - IncludeStructure::HeaderID Result = R.first->getValue(); - std::string &RealPathName = RealPathNames[static_cast(Result)]; - if (RealPathName.empty()) - RealPathName = Entry->tryGetRealPathName().str(); - return Result; + return R.first->getValue(); } -llvm::DenseMap -IncludeStructure::includeDepth(HeaderID Root) const { +llvm::StringMap +IncludeStructure::includeDepth(llvm::StringRef Root) const { // Include depth 0 is the main file only. - llvm::DenseMap Result; - assert(static_cast(Root) < RealPathNames.size()); + llvm::StringMap Result; Result[Root] = 0; - std::vector CurrentLevel; - CurrentLevel.push_back(Root); - llvm::DenseSet Seen; - Seen.insert(Root); + std::vector CurrentLevel; + llvm::DenseSet Seen; + auto It = NameToIndex.find(Root); + if (It != NameToIndex.end()) { + CurrentLevel.push_back(It->second); + Seen.insert(It->second); + } // 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); @@ -199,7 +193,10 @@ IncludeStructure::includeDepth(HeaderID Root) const { for (const auto &Child : IncludeChildren.lookup(Parent)) { if (Seen.insert(Child).second) { CurrentLevel.push_back(Child); - Result[Child] = Level; + const auto &Name = RealPathNames[Child]; + // Can't include files if we don't have their real path. + if (!Name.empty()) + Result[Name] = Level; } } } diff --git a/clang-tools-extra/clangd/Headers.h b/clang-tools-extra/clangd/Headers.h index f8a938f..f4ca364 100644 --- a/clang-tools-extra/clangd/Headers.h +++ b/clang-tools-extra/clangd/Headers.h @@ -12,7 +12,6 @@ #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" @@ -63,7 +62,7 @@ struct Inclusion { 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 graph and its direct +// Contains information about one file in the build grpah and its direct // dependencies. Doesn't own the strings it references (IncludeGraph is // self-contained). struct IncludeGraphNode { @@ -113,18 +112,7 @@ operator|=(IncludeGraphNode::SourceFlag &A, IncludeGraphNode::SourceFlag B) { // in any non-preamble inclusions. class IncludeStructure { public: - // 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)]; - } + std::vector MainFileIncludes; // Return all transitively reachable files. llvm::ArrayRef allHeaders() const { return RealPathNames; } @@ -132,35 +120,26 @@ public: // 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 the ID of the header being visited first. - // Usually it is getID(SM.getFileEntryForID(SM.getMainFileID())->getName()). - llvm::DenseMap includeDepth(HeaderID Root) const; + // 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; - // Maps HeaderID to the ids of the files included from it. - llvm::DenseMap> IncludeChildren; - - std::vector MainFileIncludes; - - std::string dump() { - std::string Result = - "RealPathNames: " + - llvm::join(RealPathNames.begin(), RealPathNames.end(), ", ") + - "\nFileEntryIDs: "; - for (const auto &FEID : FileEntryIDs) { - Result += std::to_string(FEID) + ", "; - } - return Result + '\n'; - } + // This updates IncludeDepth(), but not MainFileIncludes. + void recordInclude(llvm::StringRef IncludingName, + llvm::StringRef IncludedName, + llvm::StringRef IncludedRealName); private: - std::vector RealPathNames; // In HeaderID order. - std::vector FileEntryIDs; // 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. - llvm::StringMap NameToIndex; + // 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; }; /// Returns a PPCallback that visits all inclusions in the main file. @@ -226,31 +205,4 @@ private: } // 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/unittests/HeadersTests.cpp b/clang-tools-extra/clangd/unittests/HeadersTests.cpp index f6f1f4a..13babb8 100644 --- a/clang-tools-extra/clangd/unittests/HeadersTests.cpp +++ b/clang-tools-extra/clangd/unittests/HeadersTests.cpp @@ -17,7 +17,6 @@ #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" @@ -30,10 +29,8 @@ namespace { 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: @@ -67,15 +64,8 @@ private: } protected: - IncludeStructure::HeaderID getID(StringRef Filename, - IncludeStructure &Includes) { - auto Entry = Clang->getSourceManager().getFileManager().getFile(Filename); - EXPECT_TRUE(Entry); - return Includes.getOrCreateID(*Entry); - } - IncludeStructure collectIncludes() { - Clang = setupClang(); + auto Clang = setupClang(); PreprocessOnlyAction Action; EXPECT_TRUE( Action.BeginSourceFile(*Clang, Clang->getFrontendOpts().Inputs[0])); @@ -91,7 +81,7 @@ protected: // inserted. std::string calculate(PathRef Original, PathRef Preferred = "", const std::vector &Inclusions = {}) { - Clang = setupClang(); + auto Clang = setupClang(); PreprocessOnlyAction Action; EXPECT_TRUE( Action.BeginSourceFile(*Clang, Clang->getFrontendOpts().Inputs[0])); @@ -117,7 +107,7 @@ protected: } llvm::Optional insert(llvm::StringRef VerbatimHeader) { - Clang = setupClang(); + auto Clang = setupClang(); PreprocessOnlyAction Action; EXPECT_TRUE( Action.BeginSourceFile(*Clang, Clang->getFrontendOpts().Inputs[0])); @@ -136,7 +126,6 @@ protected: 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; } @@ -145,11 +134,11 @@ MATCHER_P(IncludeLine, N, "") { return arg.HashLine == N; } MATCHER_P(Directive, D, "") { return arg.Directive == D; } MATCHER_P2(Distance, File, 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; + 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; } TEST_F(HeadersTest, CollectRewrittenAndResolved) { @@ -159,14 +148,12 @@ TEST_F(HeadersTest, CollectRewrittenAndResolved) { std::string BarHeader = testPath("sub/bar.h"); FS.Files[BarHeader] = ""; - auto Includes = collectIncludes(); - EXPECT_THAT(Includes.MainFileIncludes, + EXPECT_THAT(collectIncludes().MainFileIncludes, UnorderedElementsAre( AllOf(Written("\"sub/bar.h\""), Resolved(BarHeader)))); - EXPECT_THAT(Includes.includeDepth(getID(MainFile, Includes)), - UnorderedElementsAre(Distance(getID(MainFile, Includes), 0u), - Distance(getID(BarHeader, Includes), 1u))) - << Includes.dump(); + EXPECT_THAT(collectIncludes().includeDepth(MainFile), + UnorderedElementsAre(Distance(MainFile, 0u), + Distance(testPath("sub/bar.h"), 1u))); } TEST_F(HeadersTest, OnlyCollectInclusionsInMain) { @@ -179,20 +166,17 @@ TEST_F(HeadersTest, OnlyCollectInclusionsInMain) { FS.Files[MainFile] = R"cpp( #include "bar.h" )cpp"; - auto Includes = collectIncludes(); EXPECT_THAT( - Includes.MainFileIncludes, + collectIncludes().MainFileIncludes, UnorderedElementsAre(AllOf(Written("\"bar.h\""), Resolved(BarHeader)))); - EXPECT_THAT(Includes.includeDepth(getID(MainFile, Includes)), - UnorderedElementsAre(Distance(getID(MainFile, Includes), 0u), - Distance(getID(BarHeader, Includes), 1u), - Distance(getID(BazHeader, Includes), 2u))) - << Includes.dump(); + EXPECT_THAT(collectIncludes().includeDepth(MainFile), + UnorderedElementsAre(Distance(MainFile, 0u), + Distance(testPath("sub/bar.h"), 1u), + Distance(testPath("sub/baz.h"), 2u))); // includeDepth() also works for non-main files. - EXPECT_THAT(Includes.includeDepth(getID(BarHeader, Includes)), - UnorderedElementsAre(Distance(getID(BarHeader, Includes), 0u), - Distance(getID(BazHeader, Includes), 1u))) - << Includes.dump(); + EXPECT_THAT(collectIncludes().includeDepth(testPath("sub/bar.h")), + UnorderedElementsAre(Distance(testPath("sub/bar.h"), 0u), + Distance(testPath("sub/baz.h"), 1u))); } TEST_F(HeadersTest, PreambleIncludesPresentOnce) { @@ -218,32 +202,8 @@ TEST_F(HeadersTest, UnResolvedInclusion) { EXPECT_THAT(collectIncludes().MainFileIncludes, UnorderedElementsAre(AllOf(Written("\"foo.h\""), Resolved("")))); - 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(); - llvm::DenseMap> - Expected = {{getID(MainFile, Includes), - {getID(BarHeader, Includes), getID(FooHeader, Includes)}}, - {getID(FooHeader, Includes), - {getID(BarHeader, Includes), getID(BazHeader, Includes)}}}; - EXPECT_EQ(Includes.IncludeChildren, Expected) << Includes.dump(); + EXPECT_THAT(collectIncludes().includeDepth(MainFile), + UnorderedElementsAre(Distance(MainFile, 0u))); } TEST_F(HeadersTest, IncludeDirective) { diff --git a/clang-tools-extra/clangd/unittests/ParsedASTTests.cpp b/clang-tools-extra/clangd/unittests/ParsedASTTests.cpp index dde3371..7288acb 100644 --- a/clang-tools-extra/clangd/unittests/ParsedASTTests.cpp +++ b/clang-tools-extra/clangd/unittests/ParsedASTTests.cpp @@ -44,11 +44,9 @@ namespace clangd { 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)) @@ -495,7 +493,7 @@ TEST(ParsedASTTest, PatchesAdditionalIncludes) { auto EmptyPreamble = buildPreamble(testPath("foo.cpp"), *CI, Inputs, true, nullptr); ASSERT_TRUE(EmptyPreamble); - EXPECT_THAT(EmptyPreamble->Includes.MainFileIncludes, IsEmpty()); + EXPECT_THAT(EmptyPreamble->Includes.MainFileIncludes, testing::IsEmpty()); // Now build an AST using empty preamble and ensure patched includes worked. TU.Code = ModifiedContents.str(); @@ -509,17 +507,18 @@ TEST(ParsedASTTest, PatchesAdditionalIncludes) { 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. - 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) << Includes.dump(); - auto AuxID = Includes.getID(*AuxFE); - EXPECT_THAT(Includes.IncludeChildren[*MainID], Contains(*AuxID)); + EXPECT_EQ(StringMapToVector(PatchedAST->getIncludeStructure().includeDepth( + testPath("foo.cpp"))), + StringMapToVector(ExpectedAST.getIncludeStructure().includeDepth( + testPath("foo.cpp")))); } TEST(ParsedASTTest, PatchesDeletedIncludes) { @@ -552,20 +551,18 @@ TEST(ParsedASTTest, PatchesDeletedIncludes) { 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. - 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)[MainID], - PatchedIncludes.includeDepth(PatchedMainID)[PatchedMainID]); + EXPECT_EQ(StringMapToVector(PatchedAST->getIncludeStructure().includeDepth( + testPath("foo.cpp"))), + StringMapToVector(ExpectedAST.getIncludeStructure().includeDepth( + testPath("foo.cpp")))); } // Returns Code guarded by #ifndef guards -- 2.7.4