diff --git a/clang-tools-extra/include-cleaner/include/clang-include-cleaner/Types.h b/clang-tools-extra/include-cleaner/include/clang-include-cleaner/Types.h --- a/clang-tools-extra/include-cleaner/include/clang-include-cleaner/Types.h +++ b/clang-tools-extra/include-cleaner/include/clang-include-cleaner/Types.h @@ -29,6 +29,7 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringMap.h" #include +#include #include namespace llvm { @@ -127,6 +128,10 @@ private: // Order must match Kind enum! std::variant Storage; + + Header(std::in_place_t, decltype(Storage) Sentinel) + : Storage(std::move(Sentinel)) {} + friend llvm::DenseMapInfo
; }; llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Header &); @@ -202,6 +207,23 @@ return Base::isEqual(LHS.Definition, RHS.Definition); } }; +template <> struct DenseMapInfo { + using Outer = clang::include_cleaner::Header; + using Base = DenseMapInfo; + + static inline Outer getEmptyKey() { + return {std::in_place, Base::getEmptyKey()}; + } + static inline Outer getTombstoneKey() { + return {std::in_place, Base::getTombstoneKey()}; + } + static unsigned getHashValue(const Outer &Val) { + return Base::getHashValue(Val.Storage); + } + static bool isEqual(const Outer &LHS, const Outer &RHS) { + return Base::isEqual(LHS.Storage, RHS.Storage); + } +}; } // namespace llvm #endif diff --git a/clang-tools-extra/include-cleaner/lib/Analysis.cpp b/clang-tools-extra/include-cleaner/lib/Analysis.cpp --- a/clang-tools-extra/include-cleaner/lib/Analysis.cpp +++ b/clang-tools-extra/include-cleaner/lib/Analysis.cpp @@ -12,29 +12,19 @@ #include "clang-include-cleaner/Types.h" #include "clang/AST/ASTContext.h" #include "clang/AST/Decl.h" +#include "clang/AST/DeclBase.h" #include "clang/Basic/SourceManager.h" #include "clang/Format/Format.h" #include "clang/Lex/HeaderSearch.h" #include "clang/Tooling/Core/Replacement.h" -#include "clang/Tooling/Inclusions/HeaderIncludes.h" #include "clang/Tooling/Inclusions/StandardLibrary.h" #include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StringRef.h" namespace clang::include_cleaner { -namespace { -// Gets all the providers for a symbol by tarversing each location. -llvm::SmallVector
headersForSymbol(const Symbol &S, - const SourceManager &SM, - const PragmaIncludes *PI) { - llvm::SmallVector
Headers; - for (auto &Loc : locateSymbol(S)) - Headers.append(findHeaders(Loc, SM, PI)); - return Headers; -} -} // namespace - void walkUsed(llvm::ArrayRef ASTRoots, llvm::ArrayRef MacroRefs, const PragmaIncludes *PI, const SourceManager &SM, diff --git a/clang-tools-extra/include-cleaner/lib/AnalysisInternal.h b/clang-tools-extra/include-cleaner/lib/AnalysisInternal.h --- a/clang-tools-extra/include-cleaner/lib/AnalysisInternal.h +++ b/clang-tools-extra/include-cleaner/lib/AnalysisInternal.h @@ -25,6 +25,7 @@ #include "clang-include-cleaner/Types.h" #include "clang/Basic/SourceLocation.h" #include "clang/Tooling/Inclusions/StandardLibrary.h" +#include "llvm/ADT/BitmaskEnum.h" #include "llvm/ADT/STLFunctionalExtras.h" #include #include @@ -80,11 +81,32 @@ }; llvm::raw_ostream &operator<<(llvm::raw_ostream &, const SymbolLocation &); +/// Represents properties of a symbol provider. +enum class Hint : uint8_t { + None = 0x00, + /// Complete definition for the symbol, only set for cases that it makes a + /// difference. e.g. types or templated functions/classes. + Complete = 0x01, + /// Provides a non-private declaration for the symbol. Only absent in the + /// cases where file is explicitly marked as such, e.g. non self-contained or + /// IWYU private pragmas. + Public = 0x02, + /// Declaration is explicitly marked as canonical, e.g. with a IWYU private + /// pragma that points at this provider. + Canonical = 0x04, + LLVM_MARK_AS_BITMASK_ENUM(Canonical), +}; +LLVM_ENABLE_BITMASK_ENUMS_IN_NAMESPACE(); +/// A wrapper to augment types with hints. +template struct Hinted : public T { + Hint Hints; + Hinted(T &&Wrapped, Hint H) : T(std::forward(Wrapped)), Hints(H) {} +}; + /// Finds the headers that provide the symbol location. -// FIXME: expose signals -llvm::SmallVector
findHeaders(const SymbolLocation &Loc, - const SourceManager &SM, - const PragmaIncludes *PI); +llvm::SmallVector> findHeaders(const SymbolLocation &Loc, + const SourceManager &SM, + const PragmaIncludes *PI); /// Write an HTML summary of the analysis to the given stream. void writeHTMLReport(FileID File, const Includes &, @@ -94,7 +116,14 @@ llvm::raw_ostream &OS); /// A set of locations that provides the declaration. -std::vector locateSymbol(const Symbol &S); +std::vector> locateSymbol(const Symbol &S); + +/// Gets all the providers for a symbol by tarversing each location. +/// Returned headers are sorted per relevance, i.e. first element is the most +/// likely provider for the symbol. +llvm::SmallVector
headersForSymbol(const Symbol &S, + const SourceManager &SM, + const PragmaIncludes *PI); } // namespace include_cleaner } // namespace clang diff --git a/clang-tools-extra/include-cleaner/lib/FindHeaders.cpp b/clang-tools-extra/include-cleaner/lib/FindHeaders.cpp old mode 100644 new mode 100755 --- a/clang-tools-extra/include-cleaner/lib/FindHeaders.cpp +++ b/clang-tools-extra/include-cleaner/lib/FindHeaders.cpp @@ -8,32 +8,96 @@ #include "AnalysisInternal.h" #include "clang-include-cleaner/Record.h" +#include "clang-include-cleaner/Types.h" +#include "clang/Basic/SourceLocation.h" #include "clang/Basic/SourceManager.h" +#include "clang/Tooling/Inclusions/StandardLibrary.h" +#include "llvm/ADT/BitmaskEnum.h" +#include "llvm/ADT/DenseMapInfo.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/raw_ostream.h" +#include +#include namespace clang::include_cleaner { +namespace { +llvm::SmallVector> +applyHints(llvm::SmallVector> Headers, Hint H) { + for (auto &Header : Headers) + Header.Hints |= H; + return Headers; +} + +std::string printHeader(const Header &H) { + std::string Spelled; + llvm::raw_string_ostream OS(Spelled); + OS << H; + return OS.str(); +} + +llvm::SmallVector
ranked(llvm::SmallVector> Headers) { + auto Score = [](const Hinted
&H) { + return static_cast(H.Hints); + }; + + llvm::sort(Headers, + [&Score](const Hinted
&LHS, const Hinted
&RHS) { + auto LHSScore = Score(LHS); + auto RHSScore = Score(RHS); + if (LHSScore == RHSScore) + return printHeader(LHS) < printHeader(RHS); + return LHSScore > RHSScore; + }); + return llvm::SmallVector
(Headers.begin(), Headers.end()); +} + +llvm::SmallVector> +nameMatch(llvm::StringRef DeclName, llvm::SmallVector> Headers) { + for (auto &H : Headers) { + auto SpelledH = printHeader(H); + llvm::StringRef SpelledHRef(SpelledH); + SpelledHRef = SpelledHRef.trim("<>\""); + if (auto LastSlash = SpelledH.rfind('/'); LastSlash != SpelledH.npos) + SpelledHRef = SpelledHRef.drop_front(LastSlash + 1); + // Drop everything after first `.` (dot). + // foo.h -> foo + // foo.cu.h -> foo + SpelledHRef = SpelledHRef.substr(0, SpelledHRef.find('.')); + if (SpelledHRef.equals_insensitive(DeclName)) + H.Hints |= Hint::Canonical; + } + return Headers; +} + +} // namespace -llvm::SmallVector
findHeaders(const SymbolLocation &Loc, - const SourceManager &SM, - const PragmaIncludes *PI) { - llvm::SmallVector
Results; +llvm::SmallVector> findHeaders(const SymbolLocation &Loc, + const SourceManager &SM, + const PragmaIncludes *PI) { + llvm::SmallVector> Results; switch (Loc.kind()) { case SymbolLocation::Physical: { // FIXME: Handle macro locations. FileID FID = SM.getFileID(Loc.physical()); const FileEntry *FE = SM.getFileEntryForID(FID); - if (!PI) { - return FE ? llvm::SmallVector
{Header(FE)} - : llvm::SmallVector
(); - } + if (!FE) + return {}; + if (!PI) + return {{FE, Hint::Public}}; while (FE) { - Results.push_back(Header(FE)); + Hint CurrentHints = (PI->isPrivate(FE) || !PI->isSelfContained(FE)) + ? Hint::None + : Hint::Public; + Results.emplace_back(FE, CurrentHints); // FIXME: compute transitive exporter headers. for (const auto *Export : PI->getExporters(FE, SM.getFileManager())) - Results.push_back(Header(Export)); + Results.emplace_back(Export, CurrentHints); - llvm::StringRef VerbatimSpelling = PI->getPublic(FE); - if (!VerbatimSpelling.empty()) { - Results.push_back(VerbatimSpelling); + if (auto Verbatim = PI->getPublic(FE); !Verbatim.empty()) { + Results.emplace_back(Verbatim, CurrentHints | Hint::Canonical); break; } if (PI->isSelfContained(FE) || FID == SM.getMainFileID()) @@ -47,11 +111,52 @@ } case SymbolLocation::Standard: { for (const auto &H : Loc.standard().headers()) - Results.push_back(H); + Results.emplace_back(H, Hint::Canonical | Hint::Public); return Results; } } llvm_unreachable("unhandled SymbolLocation kind!"); } -} // namespace clang::include_cleaner \ No newline at end of file +llvm::SmallVector
headersForSymbol(const Symbol &S, + const SourceManager &SM, + const PragmaIncludes *PI) { + llvm::SmallVector> Headers; + for (auto &Loc : locateSymbol(S)) + Headers.append(applyHints(findHeaders(Loc, SM, PI), Loc.Hints)); + // We just want to de-duplicate providers by merging them. So use some sort of + // ordering to make sure duplicates are grouped together. + auto HashHeader = [](const Header &H) { + return llvm::DenseMapInfo
::getHashValue(H); + }; + // FIXME: This doesn't de-duplicate if the same header gets mentioned in + // multiple ways (e.g. one through physical includes and another through a + // verbatim spelling). + llvm::sort(Headers, [&HashHeader](const Hinted
&LHS, + const Hinted
&RHS) { + return HashHeader(LHS) < HashHeader(RHS); + }); + auto *Write = Headers.begin(); + for (auto *Read = Headers.begin(); Read != Headers.end(); ++Write) { + *Write = *Read++; + while (Read != Headers.end() && + static_cast
(*Write) == static_cast
(*Read)) { + Write->Hints |= Read->Hints; + ++Read; + } + } + Headers.erase(Write, Headers.end()); + + // Add name match hints to deduplicated providers. + std::string SymbolName; + { + llvm::raw_string_ostream OS(SymbolName); + OS << S; + } + llvm::StringRef DeclName(SymbolName); + if (auto LastQualifier = DeclName.rfind("::"); LastQualifier != DeclName.npos) + DeclName = DeclName.drop_front(LastQualifier); + // FIXME: Introduce a MainFile header kind or signal and boost it. + return ranked(nameMatch(DeclName, std::move(Headers))); +} +} // namespace clang::include_cleaner diff --git a/clang-tools-extra/include-cleaner/lib/HTMLReport.cpp b/clang-tools-extra/include-cleaner/lib/HTMLReport.cpp --- a/clang-tools-extra/include-cleaner/lib/HTMLReport.cpp +++ b/clang-tools-extra/include-cleaner/lib/HTMLReport.cpp @@ -187,8 +187,7 @@ // Duplicates logic from walkUsed(), which doesn't expose SymbolLocations. for (auto &Loc : locateSymbol(R.Sym)) R.Locations.push_back(Loc); - for (const auto &Loc : R.Locations) - R.Headers.append(findHeaders(Loc, SM, PI)); + R.Headers = headersForSymbol(R.Sym, SM, PI); for (const auto &H : R.Headers) { R.Includes.append(Includes.match(H)); @@ -205,7 +204,6 @@ R.Includes.end()); if (!R.Headers.empty()) - // FIXME: library should tell us which header to use. R.Insert = spellHeader(R.Headers.front()); } diff --git a/clang-tools-extra/include-cleaner/lib/LocateSymbol.cpp b/clang-tools-extra/include-cleaner/lib/LocateSymbol.cpp --- a/clang-tools-extra/include-cleaner/lib/LocateSymbol.cpp +++ b/clang-tools-extra/include-cleaner/lib/LocateSymbol.cpp @@ -7,10 +7,14 @@ //===----------------------------------------------------------------------===// #include "AnalysisInternal.h" +#include "clang/AST/Decl.h" #include "clang/AST/DeclBase.h" +#include "clang/AST/DeclCXX.h" +#include "clang/AST/DeclTemplate.h" #include "clang/Basic/SourceLocation.h" #include "clang/Tooling/Inclusions/StandardLibrary.h" #include "llvm/ADT/StringExtras.h" +#include "llvm/Support/Casting.h" #include "llvm/Support/raw_ostream.h" #include #include @@ -18,13 +22,36 @@ namespace clang::include_cleaner { namespace { -std::vector locateDecl(const Decl &D) { - std::vector Result; +Hint hints(const Decl *D) { + Hint Hints = Hint::None; + // Check if completeness matters for this decl. + if (auto *TD = llvm::dyn_cast(D)) { + if (TD->isThisDeclarationADefinition()) + Hints |= Hint::Complete; + } else if (auto *CTD = llvm::dyn_cast(D)) { + if (CTD->isThisDeclarationADefinition()) + Hints |= Hint::Complete; + } else if (auto *FTD = llvm::dyn_cast(D)) { + if (FTD->isThisDeclarationADefinition()) + Hints |= Hint::Complete; + } + return Hints; +} + +std::vector> locateDecl(const Decl &D) { + std::vector> Result; // FIXME: Should we also provide physical locations? if (auto SS = tooling::stdlib::Recognizer()(&D)) - return {SymbolLocation(*SS)}; + return {{*SS, Hint::Complete}}; + // FIXME: Signal foreign decls, e.g. a forward declaration not owned by a + // library. Some useful signals could be derived by checking the DeclContext. + // Most incidental forward decls look like: + // namespace clang { + // class SourceManager; // likely an incidental forward decl. + // namespace my_own_ns {} + // } for (auto *Redecl : D.redecls()) - Result.push_back(Redecl->getLocation()); + Result.push_back({Redecl->getLocation(), hints(Redecl)}); return Result; } @@ -46,12 +73,12 @@ llvm_unreachable("Unhandled Symbol kind"); } -std::vector locateSymbol(const Symbol &S) { +std::vector> locateSymbol(const Symbol &S) { switch (S.kind()) { case Symbol::Declaration: return locateDecl(S.declaration()); case Symbol::Macro: - return {SymbolLocation(S.macro().Definition)}; + return {{S.macro().Definition, Hint::Complete}}; } llvm_unreachable("Unknown Symbol::Kind enum"); } diff --git a/clang-tools-extra/include-cleaner/unittests/FindHeadersTest.cpp b/clang-tools-extra/include-cleaner/unittests/FindHeadersTest.cpp --- a/clang-tools-extra/include-cleaner/unittests/FindHeadersTest.cpp +++ b/clang-tools-extra/include-cleaner/unittests/FindHeadersTest.cpp @@ -8,16 +8,20 @@ #include "AnalysisInternal.h" #include "clang-include-cleaner/Record.h" +#include "clang-include-cleaner/Types.h" +#include "clang/AST/RecursiveASTVisitor.h" #include "clang/Basic/FileEntry.h" #include "clang/Basic/FileManager.h" #include "clang/Frontend/FrontendActions.h" #include "clang/Testing/TestAST.h" +#include "llvm/ADT/SmallVector.h" #include "gmock/gmock.h" #include "gtest/gtest.h" #include namespace clang::include_cleaner { namespace { +using testing::ElementsAre; using testing::UnorderedElementsAre; std::string guard(llvm::StringRef Code) { @@ -31,7 +35,7 @@ std::unique_ptr AST; FindHeadersTest() { Inputs.MakeAction = [this] { - struct Hook : public PreprocessOnlyAction { + struct Hook : public SyntaxOnlyAction { public: Hook(PragmaIncludes *Out) : Out(Out) {} bool BeginSourceFileAction(clang::CompilerInstance &CI) override { @@ -47,11 +51,12 @@ void buildAST() { AST = std::make_unique(Inputs); } llvm::SmallVector
findHeaders(llvm::StringRef FileName) { - return include_cleaner::findHeaders( + auto Headers = include_cleaner::findHeaders( AST->sourceManager().translateFileLineCol( AST->fileManager().getFile(FileName).get(), /*Line=*/1, /*Col=*/1), AST->sourceManager(), &PI); + return {Headers.begin(), Headers.end()}; } const FileEntry *physicalHeader(llvm::StringRef FileName) { return AST->fileManager().getFile(FileName).get(); @@ -153,5 +158,129 @@ physicalHeader("exporter.h"))); } +class HeadersForSymbolTest : public FindHeadersTest { +protected: + llvm::SmallVector
headersForFoo() { + struct Visitor : public RecursiveASTVisitor { + const NamedDecl *Out = nullptr; + bool VisitNamedDecl(const NamedDecl *ND) { + if (ND->getName() == "foo") { + EXPECT_TRUE(Out == nullptr || Out == ND->getCanonicalDecl()) + << "Found multiple matches for foo."; + Out = cast(ND->getCanonicalDecl()); + } + return true; + } + }; + Visitor V; + V.TraverseDecl(AST->context().getTranslationUnitDecl()); + if (!V.Out) + ADD_FAILURE() << "Couldn't find any decls named foo."; + assert(V.Out); + return headersForSymbol(*V.Out, AST->sourceManager(), &PI); + } +}; + +TEST_F(HeadersForSymbolTest, Deduplicates) { + Inputs.Code = R"cpp( + #include "foo.h" + )cpp"; + Inputs.ExtraFiles["foo.h"] = guard(R"cpp( + // IWYU pragma: private, include "foo.h" + void foo(); + void foo(); + )cpp"); + buildAST(); + EXPECT_THAT( + headersForFoo(), + UnorderedElementsAre(physicalHeader("foo.h"), + // FIXME: de-duplicate across different kinds. + Header("\"foo.h\""))); +} + +TEST_F(HeadersForSymbolTest, RankingSortsByName) { + Inputs.Code = R"cpp( + #include "bar.h" + #include "fox.h" + )cpp"; + Inputs.ExtraFiles["fox.h"] = guard(R"cpp( + void foo(); + )cpp"); + Inputs.ExtraFiles["bar.h"] = guard(R"cpp( + void foo(); + )cpp"); + buildAST(); + EXPECT_THAT(headersForFoo(), + ElementsAre(physicalHeader("bar.h"), physicalHeader("fox.h"))); +} + +TEST_F(HeadersForSymbolTest, Ranking) { + // Sorting is done over (canonical, public, complete) triplet. + Inputs.Code = R"cpp( + #include "private.h" + #include "public.h" + #include "public_complete.h" + )cpp"; + Inputs.ExtraFiles["public.h"] = guard(R"cpp( + struct foo; + )cpp"); + Inputs.ExtraFiles["private.h"] = guard(R"cpp( + // IWYU pragma: private, include "canonical.h" + struct foo; + )cpp"); + Inputs.ExtraFiles["public_complete.h"] = guard("struct foo {};"); + buildAST(); + EXPECT_THAT(headersForFoo(), ElementsAre(Header("\"canonical.h\""), + physicalHeader("public_complete.h"), + physicalHeader("public.h"), + physicalHeader("private.h"))); +} + +TEST_F(HeadersForSymbolTest, PreferPublicOverComplete) { + Inputs.Code = R"cpp( + #include "complete_private.h" + #include "public.h" + )cpp"; + Inputs.ExtraFiles["complete_private.h"] = guard(R"cpp( + // IWYU pragma: private + struct foo {}; + )cpp"); + Inputs.ExtraFiles["public.h"] = guard("struct foo;"); + buildAST(); + EXPECT_THAT(headersForFoo(), + ElementsAre(physicalHeader("public.h"), + physicalHeader("complete_private.h"))); +} + +TEST_F(HeadersForSymbolTest, PreferNameMatch) { + Inputs.Code = R"cpp( + #include "public_complete.h" + #include "test/foo.proto.h" + )cpp"; + Inputs.ExtraFiles["public_complete.h"] = guard(R"cpp( + struct foo {}; + )cpp"); + Inputs.ExtraFiles["test/foo.proto.h"] = guard("struct foo;"); + buildAST(); + EXPECT_THAT(headersForFoo(), + ElementsAre(physicalHeader("test/foo.proto.h"), + physicalHeader("public_complete.h"))); +} + +TEST_F(HeadersForSymbolTest, MainFile) { + Inputs.Code = R"cpp( + #include "public_complete.h" + struct foo; + )cpp"; + Inputs.ExtraFiles["public_complete.h"] = guard(R"cpp( + struct foo {}; + )cpp"); + buildAST(); + auto &SM = AST->sourceManager(); + // FIXME: Mainfile should be boosted. + EXPECT_THAT(headersForFoo(), + ElementsAre(physicalHeader("public_complete.h"), + Header(SM.getFileEntryForID(SM.getMainFileID())))); +} } // namespace -} // namespace clang::include_cleaner \ No newline at end of file +} // namespace clang::include_cleaner