[include-cleaner] Initial version for the "Location=>Header" step

[hokein]

Summary

This patch implements the initial version of "Location => Header" step:

• define the interface;
• integrate into the existing workflow, and use the PragmaIncludes;

[kadircet]

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

53

can you add comments here describing what this case is used for

64

let's move this to AnalysisInternal.h, as it isn't used in any of the public apis.

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

45

nit: if (auto *Loc = std::get_if<SourceLocation>(&SLoc))

55

what about exporters here?

58

not sure i follow the fixme here, are you suggesting we should also compute transitive exporters?

63

nit: if (auto *Sym = std::get<tooling::stdlib::Symbol>(&SLoc))

clang-tools-extra/include-cleaner/lib/AnalysisInternal.h

49

this is fine for the initial version, but we'll likely lose a lot of performance here going forward. we can address it later on though, as this is an internal api and those performance concerns won't be a problem until this is used more widely.

we're likely going to call this function multiple times for each symbol, and also despite having different sourcelocations, there'll probably be lots of declarations that're originating from the same FileID.
Hence we'll want to accumulate outputs on a single container, rather than returning a new container at each call, and also have some sort of file-id based cache.

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

117

can we use findIncludeHeaders directly?

that way we don't need to set up a referencing file, e.g. you can directly create a SourceLocation inside private.h (in this case even the decl is not important).

(same for the export test)

136

calling this private is somewhat confusing, maybe call it Detail?

[hokein]

address comments

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

64

I'm not quite sure about this --the SymbolLocation is an important concept and API, even though it is not used in public APIs. Moved anyway.

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

55

based on our previous discussion, we decided to initially treat the spelling header in the IWYU private pragma as the final public header, so no need to do the exporters here.

58

Yeah, rephrased the FIXME.

clang-tools-extra/include-cleaner/lib/AnalysisInternal.h

49

Acked, agree that this is likely a hot function, we should not be concern about it at the moment.

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

117

the intention was to do an end-to-end test of the walkUsed API.

but you're right, we should have a unittest for findIncludeHeaders, added one, and simplified the end-to-end walkUsed test.

[kadircet]

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

54

nit: . at the end of comment

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

55

yeah SG, can you put a comment about that though? saying // Note that we might need to look for exporters in this case as well.

58

i see, i am not sure if that's desired though.

e.g. if we have foo.h exporting bar.h exporting baz.h, I don't think baz.h counts (or should count) as an alternative to foo.h. do we have information proving otherwise?

67

can you actually put an llvm_unreachable here?

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

117

the intention was to do an end-to-end test of the walkUsed API.

We can update the Basic test above for that purpose (and turn it into a smoke test instead).

but you're right, we should have a unittest for findIncludeHeaders, added one, and simplified the end-to-end walkUsed test.

Since these are all trying to test specific IWYU pragma behaviour, I still think it's better to test them in isolation, both for test brevity but also for debuggability in the future when something breaks.
Also making sure majority of the tests are smaller is good for incremental progress as well, when we update ast walking logic, we shouldn't be updating these tests for whatever reasons (+ arguments around test times).

135

you can still use the same fixture here, if you want a different name you can always do: using FindIncludeHeaders = WalkUsedTest; or class FindIncludeHeaders : public WalkUsedTest {};

[hokein]

address comments

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

58

The classical IWYU tool has this semantic, see the nested_export test in https://github.com/include-what-you-use/include-what-you-use/commit/9945e543d894e90fab5ebd0b685cabd5aa8dd21f.

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

117

ok, moved to WalkUsedTest.Basic. now the test is just a smoke test for IWYU pragma.

135

There is not much code being shared between these two tests (only the MakeAction, walk() is not used) -- the FindIncludeHeaders test is simpler than the WalkUsedTest, we don't need to build an AST or traverse the AST nodes.

[kadircet]

thanks, lgtm!

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

58

wow, that's surprising. but i guess is a valid point.

[hokein]

rebase

[sammccall]

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

64

FWIW +1 to the idea that this belongs in Types.h even if it's not used in public APIs at present, as discussed offline.

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

31–71

@kadircet gentle reminder - you wanted to defer this, this patch adds a copy/paste of the test setup - want me to try to pull something out before this gets out of hand?

[sammccall]

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

31–71

disregard, I misread this, the new test isn't calling walkUsed at all so belongs somewhere else

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

 //===--- Analysis.h - Analyze symbol references in AST ------------- C++-*-===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 /// A library that provides usage analysis for symbols based on AST analysis.
 //===----------------------------------------------------------------------===//
 
 #ifndef CLANG_INCLUDE_CLEANER_ANALYSIS_H
 #define CLANG_INCLUDE_CLEANER_ANALYSIS_H
 
+#include "clang-include-cleaner/Record.h"
 #include "clang-include-cleaner/Types.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/STLFunctionalExtras.h"
 #include <variant>
 
 namespace clang {
 class SourceLocation;
 class Decl;

 /// of a single source file.
 /// FIXME: Handle macro uses.
 ///
 /// This is the main entrypoint of the include-cleaner library, and can be used:
 ///  - to diagnose missing includes: a referenced symbol is provided by
 ///    headers which don't match any #include in the main file
 ///  - to diagnose unused includes: an #include in the main file does not match
 ///    the headers for any referenced symbol
-/// FIXME: Take in an include structure to improve location to header mappings
-/// (e.g. IWYU pragmas).
-void walkUsed(llvm::ArrayRef<Decl *> ASTRoots, UsedSymbolCB CB);
+void walkUsed(llvm::ArrayRef<Decl *> ASTRoots, const PragmaIncludes &PI,
+              UsedSymbolCB CB);
 
 } // namespace include_cleaner
 } // namespace clang
 
 #endif

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

 // keeping the API clean. For example, Symbol may be a Decl AST node, a macro,
 // or a recognized standard library symbol.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef CLANG_INCLUDE_CLEANER_TYPES_H
 #define CLANG_INCLUDE_CLEANER_TYPES_H
 
+#include "clang/Basic/FileEntry.h"
 #include "clang/Tooling/Inclusions/StandardLibrary.h"
+#include "llvm/ADT/StringRef.h"
 #include <memory>
 #include <vector>
 
 namespace clang {
 class Decl;
 class FileEntry;
 namespace include_cleaner {
 

 
 /// Represents a file that provides some symbol. Might not be includeable, e.g.
 /// built-in or main-file itself.
 struct Header {
   /// A physical (or logical, in case of a builtin) file.
   Header(const FileEntry *FE) : Storage(FE) {}
   /// A logical file representing a stdlib header.
   Header(tooling::stdlib::Header H) : Storage(H) {}
+  /// A verbatim header spelling, a string quoted with <> or "" that can be
+  /// #included directly
+  Header(StringRef VerbatimSpelling) : Storage(VerbatimSpelling) {}
 
   bool operator==(const Header &RHS) const { return Storage == RHS.Storage; }
 
 private:
-  // FIXME: Handle verbatim spellings.
-  std::variant<const FileEntry *, tooling::stdlib::Header> Storage;
+  std::variant<const FileEntry *, tooling::stdlib::Header, StringRef> Storage;
 };
 
 } // namespace include_cleaner
 } // namespace clang
 
 #endif
 

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

 //===--- Analysis.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 "clang-include-cleaner/Analysis.h"
-#include "clang-include-cleaner/Types.h"
 #include "AnalysisInternal.h"
+#include "clang-include-cleaner/Record.h"
+#include "clang-include-cleaner/Types.h"
 #include "clang/AST/ASTContext.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"
 
 namespace clang::include_cleaner {
-namespace {
-llvm::SmallVector<Header>
-toHeader(llvm::ArrayRef<tooling::stdlib::Header> Headers) {
-  llvm::SmallVector<Header> Result;
-  llvm::for_each(Headers, [&](tooling::stdlib::Header H) {
-    Result.emplace_back(Header(H));
-  });
-  return Result;
-}
 
-} // namespace
-void walkUsed(llvm::ArrayRef<Decl *> ASTRoots, UsedSymbolCB CB) {
+void walkUsed(llvm::ArrayRef<Decl *> ASTRoots, const PragmaIncludes &PI,
+              UsedSymbolCB CB) {
   tooling::stdlib::Recognizer Recognizer;
   for (auto *Root : ASTRoots) {
     auto &SM = Root->getASTContext().getSourceManager();
     walkAST(*Root, [&](SourceLocation Loc, NamedDecl &ND) {
       if (auto SS = Recognizer(&ND)) {
         // FIXME: Also report forward decls from main-file, so that the caller
         // can decide to insert/ignore a header.
-        return CB(Loc, Symbol(*SS), toHeader(SS->headers()));
+        return CB(Loc, Symbol(*SS), findIncludeHeaders({*SS}, SM, PI));
       }
       // FIXME: Extract locations from redecls.
-      // FIXME: Handle IWYU pragmas, non self-contained files.
       // FIXME: Handle macro locations.
-      if (auto *FE = SM.getFileEntryForID(SM.getFileID(ND.getLocation())))
-        return CB(Loc, Symbol(ND), {Header(FE)});
+      return CB(Loc, Symbol(ND),
+                findIncludeHeaders({ND.getLocation()}, SM, PI));
     });
   }
   // FIXME: Handle references of macros.
 }
 
+llvm::SmallVector<Header> findIncludeHeaders(const SymbolLocation &SLoc,
+                                             const SourceManager &SM,
+                                             const PragmaIncludes &PI) {
+  llvm::SmallVector<Header> Results;
+  if (auto *Loc = std::get_if<SourceLocation>(&SLoc)) {
+    // FIXME: Handle non self-contained files.
+    FileID FID = SM.getFileID(*Loc);
+    const auto *FE = SM.getFileEntryForID(FID);
+    if (!FE)
+      return {};
+
+    llvm::StringRef VerbatimSpelling = PI.getPublic(FE);
+    if (!VerbatimSpelling.empty())
+      return {{VerbatimSpelling}};
+
+    Results = {{FE}};
+    // FIXME: compute transitive exporter headers.
+    for (const auto *Export : PI.getExporters(FE, SM.getFileManager()))
+      Results.push_back(Export);
+    return Results;
+  }
+  if (auto *Sym = std::get_if<tooling::stdlib::Symbol>(&SLoc)) {
+    for (const auto &H : Sym->headers())
+      Results.push_back(H);
+    return Results;
+  }
+  return Results;
+}
+
 } // namespace clang::include_cleaner

clang-tools-extra/include-cleaner/lib/AnalysisInternal.h

 // The individual steps are declared here.
 // (AST => AST Node => Symbol is one API to avoid materializing DynTypedNodes).
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef CLANG_INCLUDE_CLEANER_ANALYSISINTERNAL_H
 #define CLANG_INCLUDE_CLEANER_ANALYSISINTERNAL_H
 
+#include "clang-include-cleaner/Record.h"
+#include "clang-include-cleaner/Types.h"
 #include "clang/Basic/SourceLocation.h"
 #include "llvm/ADT/STLFunctionalExtras.h"
 
 namespace clang {
 class ASTContext;
 class Decl;
 class NamedDecl;
 namespace include_cleaner {
 
 /// Traverses part of the AST from \p Root, finding uses of symbols.
 ///
 /// Each use is reported to the callback:
 /// - the SourceLocation describes where the symbol was used. This is usually
 ///   the primary location of the AST node found under Root.
 /// - the NamedDecl is the symbol referenced. It is canonical, rather than e.g.
 ///   the redecl actually found by lookup.
 ///
 /// walkAST is typically called once per top-level declaration in the file
 /// being analyzed, in order to find all references within it.
 void walkAST(Decl &Root, llvm::function_ref<void(SourceLocation, NamedDecl &)>);
 
+/// A location where a symbol can be provided.
+/// It is either a physical file of the TU (SourceLocation) or a logical
+/// location in the standard library (stdlib::Symbol).
+// FIXME: use a real Class!
+using SymbolLocation = std::variant<SourceLocation, tooling::stdlib::Symbol>;
+
+/// Finds the headers that provide the symbol location.
+// FIXME: expose signals
+llvm::SmallVector<Header> findIncludeHeaders(const SymbolLocation &Loc,
+                                             const SourceManager &SM,
+                                             const PragmaIncludes &PI);
+
 /// Write an HTML summary of the analysis to the given stream.
 /// FIXME: Once analysis has a public API, this should be public too.
 void writeHTMLReport(FileID File, llvm::ArrayRef<Decl *> Roots, ASTContext &Ctx,
                      llvm::raw_ostream &OS);
 
 } // namespace include_cleaner
 } // namespace clang
 
 #endif

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

 //===--- AnalysisTest.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 "clang-include-cleaner/Analysis.h"
+#include "AnalysisInternal.h"
+#include "clang-include-cleaner/Record.h"
 #include "clang-include-cleaner/Types.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/Basic/FileManager.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
+#include "clang/Frontend/FrontendActions.h"
 #include "clang/Testing/TestAST.h"
 #include "clang/Tooling/Inclusions/StandardLibrary.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Testing/Support/Annotations.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include <cstddef>
 
 namespace clang::include_cleaner {
 namespace {
 using testing::Pair;
 using testing::UnorderedElementsAre;
 
-TEST(WalkUsed, Basic) {
-  // FIXME: Have a fixture for setting up tests.
-  llvm::Annotations HeaderCode(R"cpp(
-  void foo();
-  namespace std { class vector {}; })cpp");
-  llvm::Annotations Code(R"cpp(
-  void $bar^bar() {
-    $foo^foo();
-    std::$vector^vector $vconstructor^v;
+class WalkUsedTest : public ::testing::Test {
+protected:
+  TestInputs Inputs;
+  PragmaIncludes PI;
+
+  WalkUsedTest() {
+    Inputs.MakeAction = [this] {
+      struct Hook : public SyntaxOnlyAction {
+      public:
+        Hook(PragmaIncludes *Out) : Out(Out) {}
+        bool BeginSourceFileAction(clang::CompilerInstance &CI) override {
+          Out->record(CI);
+          return true;
         }
-  )cpp");
-  TestInputs Inputs(Code.code());
-  Inputs.ExtraFiles["header.h"] = HeaderCode.code().str();
-  Inputs.ExtraArgs.push_back("-include");
-  Inputs.ExtraArgs.push_back("header.h");
-  TestAST AST(Inputs);
 
-  llvm::SmallVector<Decl *> TopLevelDecls;
-  for (Decl *D : AST.context().getTranslationUnitDecl()->decls()) {
-    TopLevelDecls.emplace_back(D);
+        PragmaIncludes *Out;
+      };
+      return std::make_unique<Hook>(&PI);
+    };
   }
 
+  llvm::DenseMap</*offset*/ size_t, std::vector<Header>> walk(TestAST &AST) {
+    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, [&](SourceLocation RefLoc, Symbol S,
-                              llvm::ArrayRef<Header> Providers) {
+    walkUsed(
+        TopLevelDecls, PI,
+        [&](SourceLocation RefLoc, Symbol S, llvm::ArrayRef<Header> Providers) {
           auto [FID, Offset] = SM.getDecomposedLoc(RefLoc);
           EXPECT_EQ(FID, SM.getMainFileID());
           OffsetToProviders.try_emplace(Offset, Providers.vec());
         });
+    return OffsetToProviders;
+  }
+};
+
+TEST_F(WalkUsedTest, Basic) {
+  llvm::Annotations Code(R"cpp(
+  void $bar^bar() {
+    $foo^foo();
+    std::$vector^vector $vconstructor^v;
+  }
+  )cpp");
+  Inputs.Code = Code.code();
+  Inputs.ExtraFiles["header.h"] = R"cpp(
+  void foo();
+  namespace std { class vector {}; }
+  )cpp";
+  Inputs.ExtraArgs.push_back("-include");
+  Inputs.ExtraArgs.push_back("header.h");
+  TestAST AST(Inputs);
+
   auto HeaderFile = Header(AST.fileManager().getFile("header.h").get());
-  auto MainFile = Header(SM.getFileEntryForID(SM.getMainFileID()));
+  auto MainFile = Header(AST.sourceManager().getFileEntryForID(
+      AST.sourceManager().getMainFileID()));
   auto VectorSTL = Header(tooling::stdlib::Header::named("<vector>").value());
   EXPECT_THAT(
-      OffsetToProviders,
+      walk(AST),
       UnorderedElementsAre(
           Pair(Code.point("bar"), UnorderedElementsAre(MainFile)),
           Pair(Code.point("foo"), UnorderedElementsAre(HeaderFile)),
           Pair(Code.point("vector"), UnorderedElementsAre(VectorSTL)),
           Pair(Code.point("vconstructor"), UnorderedElementsAre(VectorSTL))));
 }
 
+TEST_F(WalkUsedTest, IWYUBasic) {
+  llvm::Annotations Code(R"cpp(
+  #include "private.h"
+  #include "header1.h"
+  void $bar^bar($private^Private, $detail^Detail) {
+  }
+  )cpp");
+  Inputs.Code = Code.code();
+  Inputs.ExtraFiles["private.h"] = R"cpp(
+    // IWYU pragma: private, include "path/public.h"
+    class Private {};
+  )cpp";
+  Inputs.ExtraFiles["header1.h"] = R"cpp(
+    #include "header2.h"
+  )cpp";
+  Inputs.ExtraFiles["header2.h"] = R"cpp(
+    #include "detail.h" // IWYU pragma: export
+  )cpp";
+  Inputs.ExtraFiles["detail.h"] = "class Detail {};";
+  TestAST AST(Inputs);
+
+  auto PublicH = Header("\"path/public.h\"");
+  const auto &SM = AST.sourceManager();
+
+  auto MainFile = Header(SM.getFileEntryForID(SM.getMainFileID()));
+  auto Header2File = Header(AST.fileManager().getFile("header2.h").get());
+  auto DetailFile = Header(AST.fileManager().getFile("detail.h").get());
+  EXPECT_THAT(walk(AST),
+              UnorderedElementsAre(
+                  Pair(Code.point("bar"), UnorderedElementsAre(MainFile)),
+                  Pair(Code.point("private"), UnorderedElementsAre(PublicH)),
+                  Pair(Code.point("detail"),
+                       UnorderedElementsAre(DetailFile, Header2File))));
+}
+
+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(
+    // IWYU pragma: private, include "path/public.h"
+  )cpp";
+  Inputs.ExtraFiles["header2.h"] = R"cpp(
+    #include "detail1.h" // IWYU pragma: export
+
+    // IWYU pragma: begin_exports
+    #include "detail2.h"
+    // IWYU pragma: end_exports
+
+    #include "normal.h"
+  )cpp";
+  Inputs.ExtraFiles["normal.h"] = Inputs.ExtraFiles["detail1.h"] =
+      Inputs.ExtraFiles["detail2.h"] = "";
+  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(findIncludeHeaders(SourceLocFromFile("header1.h"), SM, PI),
+              UnorderedElementsAre(Header("\"path/public.h\"")));
+
+  EXPECT_THAT(findIncludeHeaders(SourceLocFromFile("detail1.h"), SM, PI),
+              UnorderedElementsAre(Header(FM.getFile("header2.h").get()),
+                                   Header(FM.getFile("detail1.h").get())));
+  EXPECT_THAT(findIncludeHeaders(SourceLocFromFile("detail2.h"), SM, PI),
+              UnorderedElementsAre(Header(FM.getFile("header2.h").get()),
+                                   Header(FM.getFile("detail2.h").get())));
+
+  EXPECT_THAT(findIncludeHeaders(SourceLocFromFile("normal.h"), SM, PI),
+              UnorderedElementsAre(Header(FM.getFile("normal.h").get())));
+}
+
 } // namespace
 } // namespace clang::include_cleaner