[include-cleaner] Follow `IWYU pragma: export` links transitively.

[VitaNuo]

Remove accidental comment.

[VitaNuo]

Remove the preferred header hint for exporters.

[kadircet]

i think we should also have some unittests in FindHeadersTest, some sample scenarios:

foo.h

#pragma once
void foo();

export1.h

#pragma once
// IWYU pragma: private, include "public1.h"
#include "foo.h" // IWYU pragma: export

export2.h

#pragma once
// IWYU pragma: private, include "public2.h"
#include "export2.h" // IWYU pragma: export

export3.h

#pragma once
// IWYU pragma: private, include "public3.h"
#include "export3.h" // IWYU pragma: export
void foo(); // we also have a declaration here, hence this is another provider root.

user.cc

#include "export3.h"
void bar() { foo(); }

headersForFoo() should look like foo.h, public3.h, export1.h, export2.h, export3.h

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

195

what about writing this as:

std::queue<const FileEntry*> Exporters;
while (FE) {
     Results.emplace_back(FE,
                           isPublicHeader(FE, *PI) |
                               (IsOrigin ? Hints::OriginHeader : Hints::None));
      for (const auto *Export : PI->getExporters(FE, SM.getFileManager()))
        Exporters.push(Export);

      if (auto Verbatim = PI->getPublic(FE); !Verbatim.empty()) {
        Results.emplace_back(Verbatim,
                             Hints::PublicHeader | Hints::PreferredHeader);
        break;
      }
      if (PI->isSelfContained(FE) || FID == SM.getMainFileID())
        break;

      // Walkup the include stack for non self-contained headers.
      FID = SM.getDecomposedIncludedLoc(FID).first;
      FE = SM.getFileEntryForID(FID);
      IsOrigin = false;
}
// Now traverse provider trees rooted at exporters.
// Note that we only traverse export edges, and ignore private -> public mappings,
// as those pragmas apply to exporter, and not the main provider being exported in
// this header.
std::set<const FileEntry*> SeenExports;
while (!Exporters.empty()) {
  auto *Export = Exporters.front();
  Exporters.pop();
  if (!SeenExports.insert(Export).second) // In case of cyclic exports
     continue;
  Results.emplace_back(Export, isPublicHeader(Export, *PI));
  for (const auto *Export : PI->getExporters(FE, SM.getFileManager()))
     Exporters.push(Export);
}

That way we don't need to change the contracts around getExporter in PragmaIncludes

204

FE here is always a "provider" for the symbol in question, so we should actually respect the private pragmas in them. we should only ignore those pragmas if they're discovered inside a header, that we found because we followed an export edge.

207

verbatim spellings are relative to an include search path (or even worse, relative to the file containing the include directive) so we can't rely on being able to resolve it directly through FileManager (it can only resolve either absolute paths nor paths relative to CWD).

[VitaNuo]

Address the comments.

[VitaNuo]

Add a test with private headers involved. Order of exporters is from outermost to innermost.

[kadircet]

Order of exporters is from outermost to innermost.

FWIW, that's mostly a coincidence. all 3 exporters are private headers, hence they're penalized for it. Afterwards "export1.h" is actually boosted among other exporters as it is also an "origin" provider. "export2.h" and "export3.h" are pretty much equal hence they're ranked based on their name. (discovery order of includes doesn't determine the ranking).

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

 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.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"
 #include "llvm/Support/Casting.h"
+#include "llvm/Support/Error.h"
 #include "llvm/Support/ErrorHandling.h"
+#include <algorithm>
 #include <optional>
+#include <set>
 #include <utility>
 
 namespace clang::include_cleaner {
 namespace {
 llvm::SmallVector<Hinted<Header>>
 applyHints(llvm::SmallVector<Hinted<Header>> Headers, Hints H) {
   for (auto &Header : Headers)
     Header.Hint |= H;
llvm::SmallVector<Hinted<Header>> findHeaders(const SymbolLocation &Loc,
   case SymbolLocation::Physical: {
     FileID FID = SM.getFileID(SM.getExpansionLoc(Loc.physical()));
     const FileEntry *FE = SM.getFileEntryForID(FID);
     if (!FE)
       return {};
     if (!PI)
       return {{FE, Hints::PublicHeader | Hints::OriginHeader}};
     bool IsOrigin = true;
+    std::set<const FileEntry *> Exporters;
     while (FE) {
       Results.emplace_back(FE,
                            isPublicHeader(FE, *PI) |
                                (IsOrigin ? Hints::OriginHeader : Hints::None));
-      // FIXME: compute transitive exporter headers.
-      for (const auto *Export : PI->getExporters(FE, SM.getFileManager()))
+      for (const auto *Export : PI->getExporters(FE, SM.getFileManager())) {
+        Exporters.insert(Export);
         Results.emplace_back(Export, isPublicHeader(Export, *PI));
+      }
 
       if (auto Verbatim = PI->getPublic(FE); !Verbatim.empty()) {
-        Results.emplace_back(Verbatim,
-                             Hints::PublicHeader | Hints::PreferredHeader);
+        Hints Hint = Hints::PublicHeader;
+        auto FE =
+                expectedToOptional(SM.getFileManager().getFileRef(Verbatim));
+        if (!FE || std::find(Exporters.begin(), Exporters.end(), FE) ==
+              Exporters.end())
+          Hint |= Hints::PreferredHeader;
+        Results.emplace_back(Verbatim, Hint);
         break;
       }
       if (PI->isSelfContained(FE) || FID == SM.getMainFileID())
         break;
 
       // Walkup the include stack for non self-contained headers.
       FID = SM.getDecomposedIncludedLoc(FID).first;
       FE = SM.getFileEntryForID(FID);

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

 //===--- Record.cpp - Record compiler events ------------------------------===//
 //
 // 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 "clang-include-cleaner/Record.h"
 #include "clang-include-cleaner/Types.h"
 #include "clang/AST/ASTConsumer.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/DeclGroup.h"
 #include "clang/Basic/FileEntry.h"
+#include "clang/Basic/FileManager.h"
 #include "clang/Basic/LLVM.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Basic/Specifiers.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Lex/DirectoryLookup.h"
 #include "clang/Lex/MacroInfo.h"
 #include "clang/Lex/PPCallbacks.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Tooling/Inclusions/HeaderAnalysis.h"
 #include "clang/Tooling/Inclusions/StandardLibrary.h"
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/iterator_range.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Error.h"
+#include "llvm/Support/FileSystem/UniqueID.h"
 #include "llvm/Support/StringSaver.h"
 #include <algorithm>
 #include <assert.h>
 #include <memory>
 #include <optional>
+#include <set>
 #include <utility>
 #include <vector>
 
 namespace clang::include_cleaner {
 namespace {
 
 class PPRecorder : public PPCallbacks {
 public:

 
 llvm::StringRef PragmaIncludes::getPublic(const FileEntry *F) const {
   auto It = IWYUPublic.find(F->getUniqueID());
   if (It == IWYUPublic.end())
     return "";
   return It->getSecond();
 }
 
+template <typename Iter>
 static llvm::SmallVector<const FileEntry *>
-toFileEntries(llvm::ArrayRef<StringRef> FileNames, FileManager &FM) {
+toFileEntries(Iter FileNamesBegin, Iter FileNamesEnd, FileManager &FM) {
   llvm::SmallVector<const FileEntry *> Results;
 
-  for (auto FName : FileNames) {
+  for (auto FNameIt = FileNamesBegin; FNameIt != FileNamesEnd; ++FNameIt) {
     // FIMXE: log the failing cases?
-    if (auto FE = expectedToOptional(FM.getFileRef(FName)))
+    if (auto FE = expectedToOptional(FM.getFileRef(*FNameIt)))
       Results.push_back(*FE);
   }
   return Results;
 }
-llvm::SmallVector<const FileEntry *>
-PragmaIncludes::getExporters(const FileEntry *File, FileManager &FM) const {
-  auto It = IWYUExportBy.find(File->getUniqueID());
+
+void collectExportersRecursively(
+    llvm::DenseMap<llvm::sys::fs::UniqueID,
+                   llvm::SmallVector</*FileEntry::getName()*/ llvm::StringRef>>
+        IWYUExportBy,
+    const llvm::sys::fs::UniqueID &UID, std::set<const FileEntry *> &Result,
+    FileManager &FM) {
+  auto It = IWYUExportBy.find(UID);
   if (It == IWYUExportBy.end())
-    return {};
+    return;
+  auto Exporters =
+      toFileEntries(It->getSecond().begin(), It->getSecond().end(), FM);
+  for (const auto &E : Exporters) {
+    Result.insert(E);
+    collectExportersRecursively(IWYUExportBy, E->getUniqueID(), Result, FM);
+  }
+}
 
-  return toFileEntries(It->getSecond(), FM);
+llvm::SmallVector<const FileEntry *>
+PragmaIncludes::getExporters(const FileEntry *File, FileManager &FM) const {
+  std::set<const FileEntry *> UniqueExporters;
+  collectExportersRecursively(IWYUExportBy, File->getUniqueID(),
+                              UniqueExporters, FM);
+  llvm::SmallVector<const FileEntry *> Exporters{UniqueExporters.begin(),
+                                                 UniqueExporters.end()};
+  return Exporters;
 }
 llvm::SmallVector<const FileEntry *>
 PragmaIncludes::getExporters(tooling::stdlib::Header StdHeader,
                              FileManager &FM) const {
   auto It = StdIWYUExportBy.find(StdHeader);
   if (It == StdIWYUExportBy.end())
     return {};
-  return toFileEntries(It->getSecond(), FM);
+  return toFileEntries(It->getSecond().begin(), It->getSecond().end(), FM);
 }
 
 bool PragmaIncludes::isSelfContained(const FileEntry *FE) const {
   return !NonSelfContainedFiles.contains(FE->getUniqueID());
 }
 
 bool PragmaIncludes::isPrivate(const FileEntry *FE) const {
   return IWYUPublic.contains(FE->getUniqueID());

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

TEST_F(PragmaIncludeTest, IWYUExport) {
 
   EXPECT_TRUE(PI.getExporters(FM.getFile("export1.h").get(), FM).empty());
   EXPECT_TRUE(PI.getExporters(FM.getFile("export2.h").get(), FM).empty());
   EXPECT_TRUE(PI.getExporters(FM.getFile("export3.h").get(), FM).empty());
   EXPECT_TRUE(
       PI.getExporters(SM.getFileEntryForID(SM.getMainFileID()), FM).empty());
 }
 
+TEST_F(PragmaIncludeTest, IWYUTransitiveExport) {
+  Inputs.Code = R"cpp(
+    #include "export1.h"
+  )cpp";
+  Inputs.ExtraFiles["export1.h"] = R"cpp(
+    #include "export2.h" // IWYU pragma: export
+  )cpp";
+  Inputs.ExtraFiles["export2.h"] = R"cpp(
+    #include "provider.h" // IWYU pragma: export
+  )cpp";
+  Inputs.ExtraFiles["provider.h"] = "";
+  TestAST Processed = build();
+  auto &FM = Processed.fileManager();
+
+  EXPECT_THAT(PI.getExporters(FM.getFile("provider.h").get(), FM),
+              testing::UnorderedElementsAre(FileNamed("export1.h"),
+                                            FileNamed("export2.h")));
+}
+
 TEST_F(PragmaIncludeTest, IWYUExportForStandardHeaders) {
   Inputs.Code = R"cpp(
     #include "export.h"
   )cpp";
   Inputs.ExtraFiles["export.h"] = R"cpp(
     #include <string> // IWYU pragma: export
   )cpp";
   Inputs.ExtraFiles["string"] = "";
createEmptyFiles(
       {"private1.h", "private2.h", "private3.h", "foo.h", "bar.h"});
   TestAST Processed = build();
   auto &FM = Processed.fileManager();
 
   EXPECT_THAT(PI.getExporters(FM.getFile("private1.h").get(), FM),
               testing::UnorderedElementsAre(FileNamed("export1.h"),
                                             FileNamed("normal.h")));
   EXPECT_THAT(PI.getExporters(FM.getFile("private2.h").get(), FM),
-              testing::UnorderedElementsAre(FileNamed("export1.h")));
+              testing::UnorderedElementsAre(FileNamed("export1.h"),
+                                            FileNamed("normal.h")));
   EXPECT_THAT(PI.getExporters(FM.getFile("private3.h").get(), FM),
-              testing::UnorderedElementsAre(FileNamed("export1.h")));
+              testing::UnorderedElementsAre(FileNamed("export1.h"),
+                                            FileNamed("normal.h")));
 
   EXPECT_TRUE(PI.getExporters(FM.getFile("foo.h").get(), FM).empty());
   EXPECT_TRUE(PI.getExporters(FM.getFile("bar.h").get(), FM).empty());
 }
 
 TEST_F(PragmaIncludeTest, SelfContained) {
   Inputs.Code = R"cpp(
   #include "guarded.h"