[include-cleaner] Add self-contained file support for PragmaIncludes.

[hokein]

Summary

Based on https://reviews.llvm.org/D137697

[kadircet]

i guess this patch needs a rebase for other pieces as well? but LG in general

clang-tools-extra/include-cleaner/lib/Analysis.cpp

47 ↗

(On Diff #474189)

with the API i suggested in the base revision this should look like:

while(FID != SM.getMainFileID() && !PI.isSelfContained(FID))
  FID = SM.getFileID(SM.getIncludeLoc(FID));
return SM.getFileEntryForID(FID);

i think feels more natural

clang-tools-extra/include-cleaner/lib/Record.cpp

138

FE->getUniqueID(), same below

clang-tools-extra/include-cleaner/unittests/AnalysisTest.cpp

77

nit: rather than introducing a 3rd header, i'd just include it in header2.h.

[hokein]

rebase and address comments.

[kadircet]

clang-tools-extra/include-cleaner/include/clang-include-cleaner/Record.h

100

s/during/detected during/

clang-tools-extra/include-cleaner/lib/FindHeaders.cpp

18

what about selfContainedHeader instead of getResponsibleHeader, responsibility is a concept that we rather define between which header should include what headers (e.g. a header providing return types of its APIs)

24

FID = SM.getDecomposedIncludedLoc(FID).first;

which does a cached lookup, so might be faster than getFileID, especially when performing repeated lookups (e.g. a single file importing multiple tablegen'd headers).

37

drop fixme

38

can you drop FID (as it isn't used elsewhere) and just pass Loc.physical() into helper?

39

i am not sure if sequencing of this and rest of the IWYU pragma handling is the right actually.

e.g. consider a scenario in which:
private.h:

// IWYU private, include "public.h"
void foo();

private-impl.h:

#pragma once
#include "private.h"

we'll actually now use private-impl.h as provider for foo rather than public.h, a similar argument goes for export pragma. i think intent of the developer is a lot more explicit when we have these pragmas around, so we should prioritize them and then pick the self contained one, if it's still needed. WDYT?

clang-tools-extra/include-cleaner/lib/Record.cpp

306

s/ID/File

clang-tools-extra/include-cleaner/unittests/AnalysisTest.cpp

31

drop the const

clang-tools-extra/include-cleaner/unittests/FindHeadersTest.cpp

20

again const

[hokein]

clang-tools-extra/include-cleaner/lib/FindHeaders.cpp

39

It looks reasonable to me. Thanks for raising this case, this is a good point. I mostly considered the case where the self-contained file has the IWYU private mapping.

My current thought is:

Overall algorithm: we check the original FE to see whether we can get any IWYU mapping (private, export) headers, if there is any, we use these mapping headers as final results; if not, we use the selfContainedHeader(FE) and its IWYU mapping headers;

Below are the cases I considered -- 1), 2), 4) works fine, but the 3) is not perfect (as we prioritize the IWYU mapping headers), but probably ok.

// Case1: Private
// findHeaders("private1.inc") => "path/public1.h"
Inputs.ExtraFiles["private1.h"] = R"cpp(
  #pragma once
  #include "private1.inc"
)cpp");
Inputs.ExtraFiles["private1.inc"] = R"cpp(
  // IWYU pragma: private, include "path/public1.h"
)cpp";

// Case2: Private
// findHeaders("private2.inc") => "path/public2.h"
Inputs.ExtraFiles["private2.h"] = R"cpp(
  #pragma once
  // IWYU pragma: private, include "path/public2.h"
  #include "private2.inc"
)cpp";
Inputs.ExtraFiles["private2.inc"] = "";

// Case3: Export
// findHeaders("details1.inc") => "details1.inc", "export1.h"
Inputs.ExtraFiles["export1.h"] = R"cpp(
  #include "details1.inc" // IWYU pragma: export
)cpp";
Inputs.ExtraFiles["details1.inc"] = "";

// Case4: Export
// findHeaders("details2.inc") => "export2.h", "export2_internal.h"
Inputs.ExtraFiles["export2.h"] =R"cpp(
  #pragma once
  #include "export2_internal.h" // IWYU pragma: export
)cpp";
Inputs.ExtraFiles["export2_internal.h"] = R"cpp(
  #pragma once
  #include "details2.inc"
)cpp";
Inputs.ExtraFiles["details2.inc"] = "";

Let me know what you think about it.

[hokein]

rebase and update based on the offline discussion

[hokein]

clang-tools-extra/include-cleaner/lib/FindHeaders.cpp

39

based on our offline discussion, we're going to preserve all header candidates here (and with proper private/export signals attached, which will be in in a followup patch), and let the later step to select proper headers.

[mstorsjo]

clang-tools-extra/include-cleaner/lib/CMakeLists.txt

12

Note that this file changed a bit further in 68294afa0836bb62be921e2143d147cdfdc8ba70, so you may want to rebase again.

(I tested this patch after rebasing, in a mingw+dylib build configuration, and it still builds correctly there.)

[kadircet]

thanks, mostly LG a bunch of suggestions for tests

clang-tools-extra/include-cleaner/include/clang-include-cleaner/Record.h

74

we also need tests for this

clang-tools-extra/include-cleaner/lib/FindHeaders.cpp

42–43

nit: Results.append(PI->getExporters(FE, SM.getFileManager()))

43

can we rather write this as:

if (!PI)
  return FE ? {Header(FE)} : {};

i think it makes it more clear that in the absence of PI we're just terminating the traversal no matter what (rather than getting into the code below with possibly a null PI, because FE also happened to be null).

clang-tools-extra/include-cleaner/unittests/FindHeadersTest.cpp

72

tests and assertions here are getting a little bit hard to follow. do you mind splitting them into smaller chunks instead? each testing different parts of the traversal behaviour. one for private->public mappings, another for exports, another for non-self contained traversal. having another big integration test for testing each might also be fine, but it's really hard to reason about so i don't think that should be the main test in which we're testing the behaviour.

apart from that this might be easier to follow if we did some renaming:

• header1.h -> private1.h
• header2.h -> exporter.h (also probably move non-exported includes to a different header)
• detailx.h -> exportedx.h
• impx.inc -> fragmentx.inc

86

Verify that we emit exporters for each header on the path.

96

i think it would be better to check we stop traversal once we hit the pragma (i.e. have a non-self contained file included by another non-self contained file that also has a IWYU private mapping).

[hokein]

address comment: split tests, add a smoke test for PragmaInclude::isSelfContained.

clang-tools-extra/include-cleaner/lib/CMakeLists.txt

12

sure, and thank you very much for taking care of the mingw+dylib build!

clang-tools-extra/include-cleaner/lib/FindHeaders.cpp

42–43

the type of two container is different (Header vs FileEntry, I updated to explicitly spell the Header type in the push_back) -- if we want to get rid of the for-loop, we could use the llvm::for_each.

43

I agree, we can do that, but but the sad bit is that we need to explicitly spell the return type in the conditional operator.

clang-tools-extra/include-cleaner/unittests/FindHeadersTest.cpp

72

that sounds fair enough, split into small tests.

96

I think this is covered by this case (though this case is quite simple) -- we started the traversing from the imp_private.inc, at the beginning we hit the the IWYU private mapping, we stop immediately.

[kadircet]

thanks, lgtm!

clang-tools-extra/include-cleaner/unittests/FindHeadersTest.cpp

39

nit: i'd actually rename this to astWithIncludes and take in a set of filenames, then set up Inputs.Code here, eg:

astWithIncludes({"foo.h", "bar.h"}); -> Inputs.Code = `#include "foo.h"\n#include "bar.h"`; AST = TestAST(Inputs);

72

also we should assert that there's nothing funky going on with exporter.h itself

81

s/priviate/private

clang-tools-extra/include-cleaner/unittests/RecordTest.cpp

400 ↗

(On Diff #476410)

nit: might be easier to just have #pragma once

[hokein]

update

clang-tools-extra/include-cleaner/unittests/FindHeadersTest.cpp

39

I think hiding and synthesizing the code of main file inside a function will hurt the code readability (though the main-file code is boilerplate). As a reader, I will prefer much that the main code and the all #includes are defined in a single place which is inside the TEST_F.

clang-tools-extra/include-cleaner/include/clang-include-cleaner/Record.h

public:
   /// Returns "" if there is none.
   llvm::StringRef getPublic(const FileEntry *File) const;
 
   /// Returns all direct exporter headers for the given header file.
   /// Returns empty if there is none.
   llvm::SmallVector<const FileEntry *> getExporters(const FileEntry *File,
                                                     FileManager &FM) const;
 
+  /// Returns true if the given file is a self-contained file.
+  bool isSelfContained(const FileEntry *File) const;
+
 private:
   class RecordPragma;
   /// 1-based Line numbers for the #include directives of the main file that
   /// should always keep (e.g. has the `IWYU pragma: keep` or `IWYU pragma:
   /// export` right after).
   llvm::DenseSet</*LineNumber*/ unsigned> ShouldKeep;
 
   /// The public header mapping by the IWYU private pragma.
   //
   // !!NOTE: instead of using a FileEntry* to identify the physical file, we
   // deliberately use the UniqueID to ensure the result is stable across
   // FileManagers (for clangd's preamble and main-file builds).
   llvm::DenseMap<llvm::sys::fs::UniqueID, llvm::StringRef /*VerbatimSpelling*/>
       IWYUPublic;
 
   /// A reverse map from the underlying header to its exporter headers.
   //
   //  There's no way to get a FileEntry from a UniqueID, especially when it
   //  hasn't been opened before. So store the full path and convert it to a
   //  FileEntry by opening the file again through a FileManager.
   llvm::DenseMap<llvm::sys::fs::UniqueID,
                  llvm::SmallVector</*RealPathNames*/ llvm::StringRef>>
       IWYUExportBy;
 
+  /// Contains all non self-contained files during the parsing.
+  llvm::DenseSet<llvm::sys::fs::UniqueID> NonSelfContainedFiles;
+
   /// Owns the strings.
   llvm::BumpPtrAllocator Arena;
 
   // FIXME: add support for clang use_instead pragma
-  // FIXME: add selfcontained file.
 };
 
 /// Recorded main-file parser events relevant to include-cleaner.
 struct RecordedAST {
   /// The consumer (when installed into clang) tracks declarations in `*this`.
   std::unique_ptr<ASTConsumer> record();
 
   ASTContext *Ctx = nullptr;

clang-tools-extra/include-cleaner/lib/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS Support)
 
 add_clang_library(clangIncludeCleaner
   Analysis.cpp
   FindHeaders.cpp
   HTMLReport.cpp
   LocateSymbol.cpp
   Record.cpp
   Types.cpp
   WalkAST.cpp
 
   LINK_LIBS
   clangAST
   clangBasic
   clangLex
+  clangToolingInclusions
   clangToolingInclusionsStdlib
   )
 

clang-tools-extra/include-cleaner/lib/FindHeaders.cpp

 //===--- FindHeaders.cpp --------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "AnalysisInternal.h"
 #include "clang-include-cleaner/Record.h"
 #include "clang/Basic/SourceManager.h"
 
 namespace clang::include_cleaner {
 
+// Find a responsible header for the given file FID. If the file is non
+// self-contained, we find its first includer that is self-contained by walking
+// up the include stack.
+static const FileEntry *getResponsibleHeader(FileID FID,
+                                             const SourceManager &SM,
+                                             const PragmaIncludes &PI) {
+  const FileEntry *FE = SM.getFileEntryForID(FID);
+
+  while (FE && FID != SM.getMainFileID() && !PI.isSelfContained(FE)) {
+    FID = SM.getFileID(SM.getIncludeLoc(FID));
+    FE = SM.getFileEntryForID(FID);
+  }
+  return FE;
+}
+
 llvm::SmallVector<Header> findHeaders(const SymbolLocation &Loc,
                                       const SourceManager &SM,
                                       const PragmaIncludes &PI) {
   llvm::SmallVector<Header> Results;
   switch (Loc.kind()) {
   case SymbolLocation::Physical: {
     // FIXME: Handle macro locations.
     // FIXME: Handle non self-contained files.
     FileID FID = SM.getFileID(Loc.physical());
-    const auto *FE = SM.getFileEntryForID(FID);
+    const auto *FE = getResponsibleHeader(FID, SM, PI);
     if (!FE)
       return {};
 
     // We treat the spelling header in the IWYU pragma as the final public
     // header.
     // FIXME: look for exporters if the public header is exported by another
     // header.
     llvm::StringRef VerbatimSpelling = PI.getPublic(FE);
     if (!VerbatimSpelling.empty())
       return {Header(VerbatimSpelling)};
 
     Results = {Header(FE)};
     // FIXME: compute transitive exporter headers.
     for (const auto *Export : PI.getExporters(FE, SM.getFileManager()))
       Results.push_back(Export);
     return Results;
   }
   case SymbolLocation::Standard: {
     for (const auto &H : Loc.standard().headers())
       Results.push_back(H);
     return Results;
   }
   }
   llvm_unreachable("unhandled SymbolLocation kind!");
 }
 
 } // namespace clang::include_cleaner
 No newline at end of file

clang-tools-extra/include-cleaner/lib/Record.cpp

 #include "clang/AST/ASTConsumer.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/DeclGroup.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Lex/MacroInfo.h"
 #include "clang/Lex/PPCallbacks.h"
 #include "clang/Lex/Preprocessor.h"
+#include "clang/Tooling/Inclusions/HeaderAnalysis.h"
+
 
 namespace clang::include_cleaner {
 namespace {
 
 class PPRecorder : public PPCallbacks {
 public:
   PPRecorder(RecordedPP &Recorded, const Preprocessor &PP)
       : Recorded(Recorded), PP(PP), SM(PP.getSourceManager()) {}
static llvm::Optional<StringRef> parseIWYUPragma(const char *Text) {
   while (*End != 0 && *End != '\n')
     ++End;
   return StringRef(Text, End - Text);
 }
 
 class PragmaIncludes::RecordPragma : public PPCallbacks, public CommentHandler {
 public:
   RecordPragma(const CompilerInstance &CI, PragmaIncludes *Out)
-      : SM(CI.getSourceManager()), Out(Out), UniqueStrings(Arena) {}
+      : SM(CI.getSourceManager()),
+        HeaderInfo(CI.getPreprocessor().getHeaderSearchInfo()), Out(Out),
+        UniqueStrings(Arena) {}
 
   void FileChanged(SourceLocation Loc, FileChangeReason Reason,
                    SrcMgr::CharacteristicKind FileType,
                    FileID PrevFID) override {
     InMainFile = SM.isWrittenInMainFile(Loc);
+
+    if (Reason == PPCallbacks::ExitFile) {
+      // At file exit time HeaderSearchInfo is valid and can be used to
+      // determine whether the file was a self-contained header or not.
+      if (const FileEntry *FE = SM.getFileEntryForID(PrevFID)) {
+        if (tooling::isSelfContainedHeader(FE, SM, HeaderInfo))
+          Out->NonSelfContainedFiles.erase(FE->getUniqueID());
+        else
+          Out->NonSelfContainedFiles.insert(FE->getUniqueID());
+      }
+    }
   }
 
   void EndOfMainFile() override {
     for (auto &It : Out->IWYUExportBy) {
       llvm::sort(It.getSecond());
       It.getSecond().erase(
           std::unique(It.getSecond().begin(), It.getSecond().end()),
           It.getSecond().end());
bool HandleComment(Preprocessor &PP, SourceRange Range) override {
     return false;
   }
 
 private:
   StringRef save(llvm::StringRef S) { return UniqueStrings.save(S); }
 
   bool InMainFile = false;
   const SourceManager &SM;
+  HeaderSearch &HeaderInfo;
   PragmaIncludes *Out;
   llvm::BumpPtrAllocator Arena;
   /// Intern table for strings. Contents are on the arena.
   llvm::StringSaver UniqueStrings;
   // Track the last line "IWYU pragma: keep" was seen in the main file, 1-based.
   int LastPragmaKeepInMainFileLine = -1;
   struct ExportPragma {
     // The line number where we saw the begin_exports or export pragma.
PragmaIncludes::getExporters(const FileEntry *File, FileManager &FM) const {
   for (auto Export : It->getSecond()) {
     // FIMXE: log the failing cases?
     if (auto FE = expectedToOptional(FM.getFileRef(Export)))
       Results.push_back(*FE);
   }
   return Results;
 }
 
+bool PragmaIncludes::isSelfContained(const FileEntry *ID) const {
+  return !NonSelfContainedFiles.contains(ID->getUniqueID());
+}
+
 std::unique_ptr<ASTConsumer> RecordedAST::record() {
   class Recorder : public ASTConsumer {
     RecordedAST *Out;
 
   public:
     Recorder(RecordedAST *Out) : Out(Out) {}
     void Initialize(ASTContext &Ctx) override { Out->Ctx = &Ctx; }
     bool HandleTopLevelDecl(DeclGroupRef DG) override {

clang-tools-extra/include-cleaner/unittests/AnalysisTest.cpp

 #include "gtest/gtest.h"
 #include <cstddef>
 
 namespace clang::include_cleaner {
 namespace {
 using testing::Pair;
 using testing::UnorderedElementsAre;
 
+std::string guard(const llvm::StringRef Code) {
+  return "#pragma once\n" + Code.str();
+}
+
 TEST(WalkUsed, Basic) {
   // FIXME: Have a fixture for setting up tests.
   llvm::Annotations Code(R"cpp(
   #include "header.h"
   #include "private.h"
 
   void $bar^bar($private^Private) {
     $foo^foo();
     std::$vector^vector $vconstructor^v;
   }
   )cpp");
   TestInputs Inputs(Code.code());
-  Inputs.ExtraFiles["header.h"] = R"cpp(
+  Inputs.ExtraFiles["header.h"] = guard(R"cpp(
   void foo();
   namespace std { class vector {}; }
-  )cpp";
-  Inputs.ExtraFiles["private.h"] = R"cpp(
+  )cpp");
+  Inputs.ExtraFiles["private.h"] = guard(R"cpp(
     // IWYU pragma: private, include "path/public.h"
     class Private {};
-  )cpp";
+  )cpp");
 
   PragmaIncludes PI;
   Inputs.MakeAction = [&PI] {
     struct Hook : public SyntaxOnlyAction {
     public:
       Hook(PragmaIncludes *Out) : Out(Out) {}
       bool BeginSourceFileAction(clang::CompilerInstance &CI) override {
         Out->record(CI);
         return true;
       }
 
       PragmaIncludes *Out;
     };
     return std::make_unique<Hook>(&PI);
   };
   TestAST AST(Inputs);
 
   llvm::SmallVector<Decl *> TopLevelDecls;
   for (Decl *D : AST.context().getTranslationUnitDecl()->decls()) {
     TopLevelDecls.emplace_back(D);
   }
 
   auto &SM = AST.sourceManager();
   llvm::DenseMap<size_t, std::vector<Header>> OffsetToProviders;
   walkUsed(TopLevelDecls, /*MacroRefs=*/{}, PI, SM,
            [&](const SymbolReference &Ref, llvm::ArrayRef<Header> Providers) {
              auto [FID, Offset] = SM.getDecomposedLoc(Ref.RefLocation);
              EXPECT_EQ(FID, SM.getMainFileID());
              OffsetToProviders.try_emplace(Offset, Providers.vec());
            });
   auto HeaderFile = Header(AST.fileManager().getFile("header.h").get());

clang-tools-extra/include-cleaner/unittests/FindHeadersTest.cpp

 #include "clang/Testing/TestAST.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 namespace clang::include_cleaner {
 namespace {
 using testing::UnorderedElementsAre;
 
+std::string guard(const llvm::StringRef Code) {
+  return "#pragma once\n" + Code.str();
+}
+
 TEST(FindIncludeHeaders, IWYU) {
   TestInputs Inputs;
   PragmaIncludes PI;
   Inputs.MakeAction = [&PI] {
     struct Hook : public PreprocessOnlyAction {
     public:
       Hook(PragmaIncludes *Out) : Out(Out) {}
       bool BeginSourceFileAction(clang::CompilerInstance &CI) override {
         Out->record(CI);
         return true;
       }
 
       PragmaIncludes *Out;
     };
     return std::make_unique<Hook>(&PI);
   };
 
   Inputs.Code = R"cpp(
     #include "header1.h"
     #include "header2.h"
   )cpp";
-  Inputs.ExtraFiles["header1.h"] = R"cpp(
+  Inputs.ExtraFiles["header1.h"] = guard(R"cpp(
     // IWYU pragma: private, include "path/public.h"
-  )cpp";
-  Inputs.ExtraFiles["header2.h"] = R"cpp(
+  )cpp");
+  Inputs.ExtraFiles["header2.h"] = guard(R"cpp(
     #include "detail1.h" // IWYU pragma: export
 
     // IWYU pragma: begin_exports
     #include "detail2.h"
     // IWYU pragma: end_exports
 
+    #include "imp.inc"
+
     #include "normal.h"
-  )cpp";
+
+  )cpp");
   Inputs.ExtraFiles["normal.h"] = Inputs.ExtraFiles["detail1.h"] =
-      Inputs.ExtraFiles["detail2.h"] = "";
+      Inputs.ExtraFiles["detail2.h"] = guard("");
+  Inputs.ExtraFiles["imp.inc"] = "";
   TestAST AST(Inputs);
   const auto &SM = AST.sourceManager();
   auto &FM = SM.getFileManager();
   // Returns the source location for the start of the file.
   auto SourceLocFromFile = [&](llvm::StringRef FileName) {
     return SM.translateFileLineCol(FM.getFile(FileName).get(),
                                    /*Line=*/1, /*Col=*/1);
   };
 
   EXPECT_THAT(findHeaders(SourceLocFromFile("header1.h"), SM, PI),
               UnorderedElementsAre(Header("\"path/public.h\"")));
 
   EXPECT_THAT(findHeaders(SourceLocFromFile("detail1.h"), SM, PI),
               UnorderedElementsAre(Header(FM.getFile("header2.h").get()),
                                    Header(FM.getFile("detail1.h").get())));
   EXPECT_THAT(findHeaders(SourceLocFromFile("detail2.h"), SM, PI),
               UnorderedElementsAre(Header(FM.getFile("header2.h").get()),
                                    Header(FM.getFile("detail2.h").get())));
+  // header2.h is the first #includer for the  non self-contained header imp.inc
+  EXPECT_THAT(findHeaders(SourceLocFromFile("imp.inc"), SM, PI),
+              UnorderedElementsAre(Header(FM.getFile("header2.h").get())));
 
   EXPECT_THAT(findHeaders(SourceLocFromFile("normal.h"), SM, PI),
               UnorderedElementsAre(Header(FM.getFile("normal.h").get())));
 }
 
 } // namespace
 } // namespace clang::include_cleaner
 No newline at end of file