[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

194

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

201–202

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.

205

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/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/ErrorHandling.h"
 #include <optional>
+#include <queue>
+#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::queue<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()))
-        Results.emplace_back(Export, isPublicHeader(Export, *PI));
+        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(Export, SM.getFileManager()))
+        Exporters.push(Export);
+    }
     return Results;
   }
   case SymbolLocation::Standard: {
     return hintedHeadersForStdHeaders(Loc.standard().headers(), SM, PI);
   }
   }
   llvm_unreachable("unhandled SymbolLocation kind!");
 }

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:

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

Inputs.ExtraFiles["foo.h"] = guard(R"cpp(
     // IWYU pragma: private
     struct foo {};
   )cpp");
   buildAST();
   EXPECT_THAT(headersForFoo(),
               ElementsAre(physicalHeader("bar.h"), physicalHeader("foo.h")));
 }
 
+TEST_F(HeadersForSymbolTest, IWYUTransitiveExport) {
+  Inputs.Code = R"cpp(
+    #include "export1.h"
+  )cpp";
+  Inputs.ExtraFiles["export1.h"] = guard(R"cpp(
+    #include "export2.h" // IWYU pragma: export
+  )cpp");
+  Inputs.ExtraFiles["export2.h"] = guard(R"cpp(
+    #include "foo.h" // IWYU pragma: export
+  )cpp");
+  Inputs.ExtraFiles["foo.h"] = guard(R"cpp(
+    struct foo {};
+  )cpp");
+  buildAST();
+  EXPECT_THAT(headersForFoo(),
+              ElementsAre(physicalHeader("foo.h"), physicalHeader("export1.h"),
+                          physicalHeader("export2.h")));
+}
+
+TEST_F(HeadersForSymbolTest, IWYUTransitiveExportWithPrivate) {
+  Inputs.Code = R"cpp(
+    #include "export1.h"
+    void bar() { foo();}
+  )cpp";
+  Inputs.ExtraFiles["export1.h"] = guard(R"cpp(
+    // IWYU pragma: private, include "public1.h"
+    #include "export2.h" // IWYU pragma: export
+    void foo();
+  )cpp");
+  Inputs.ExtraFiles["export2.h"] = guard(R"cpp(
+    // IWYU pragma: private, include "public2.h"
+    #include "export3.h" // IWYU pragma: export
+  )cpp");
+  Inputs.ExtraFiles["export3.h"] = guard(R"cpp(
+    // IWYU pragma: private, include "public3.h"
+    #include "foo.h" // IWYU pragma: export
+  )cpp");
+  Inputs.ExtraFiles["foo.h"] = guard(R"cpp(
+    void foo();
+  )cpp");
+  buildAST();
+  EXPECT_THAT(headersForFoo(),
+              ElementsAre(physicalHeader("foo.h"),
+                                           Header(StringRef("\"public1.h\"")),
+                                           physicalHeader("export1.h"),
+                                           physicalHeader("export2.h"),
+                                           physicalHeader("export3.h")));
+}
+
 TEST_F(HeadersForSymbolTest, AmbiguousStdSymbols) {
   struct {
     llvm::StringRef Code;
     llvm::StringRef Name;
 
     llvm::StringRef ExpectedHeader;
   } TestCases[] = {
       {