[IncludeCleaner] Add public API

[kadircet]

Summary

Introduces walkUsed, a very simple version of the public API to enable
incremental development on rest of the pieces.

[sammccall]

Thanks! Looks good, feel free to address/disregard design comments as you see fit.

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

15

This is awful but: as mentioned on another patch, we can't actually use variant. AFAIK all C++17 *language* features are available, but LLVM supports apple clang 9.3, which doesn't provide <variant> at all.

There's an IntrusiveVariant in review somewhere but seems stalled (and honestly the Intrusive part makes it pretty ugly to use).

I think for now our best option is a Kind enum and some kind of uintptr_t storage :-(

33

nit: that's providing -> that provides, includeable -> includable

A bit unclear "what might not be includeable" means, say why?

35

a short comment for each case is pretty easy-to-read way to doc sum types, and these are important enough concepts it might be justified here. Up to you though.

48

this is so the caller can filter the references and rank the results, right?

I think it's worth saying so, mostly because that's an important design decision, and I keep forgetting to write them down

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

45

IMO this function really deserves its own impl file I think (at least Analysis.cpp) - I think it + walkAST are going to be the two biggest bundles of complexity in the library. (if so, same with the tests)

51

nit: remove debug

52

(I think the patch is fine, but could use some extra docs/fixmes depending on what the choices are here).

In general we want a forward declaration in the main file to suppress any include insertion.
Two obvious ways to achieve that:
A) walkUsed doesn't report refs of symbols that have a decl in the main file
B) walkUsed reports the refs, the header list includes the main file, the caller recognizes it when checking if the ref is satisfied

A) feels more ad-hoc, but seems to work and *does* naturally achieve the nice effect that #include "foo.h" is marked as unused if the only used symbols are also forward-declared locally. In this case, maybe add a FIXME for this filtering? Also A seems surprising enough to be worth documenting.

B) falls more naturally out of the implementation. It looks like we have a bug here: by bailing out early, we'll omit any forward declarations from the main file. For symbols in namespace std we're arguably within our rights as such decls are UB. However such forward decls are legal in C, so maybe we should care after all? In any case, this subtlety deserves some sort of comment.

57

FIXME: handle locations from macros

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

22

needed in the main lib too?

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

121

signal-to-noise in this test is a bit low, and there'll be a bunch more tests as the features get extended.

I think adding a TEST_F fixture and splitting the stdlib out into its own test, trying to maximize the shared code, may lead to cleaner tests.

Feel free to defer this, just watch out for incremental inertia giving you a 1000 line monster before you know it!

[hokein]

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

8

would be nice to have some high-level descriptions in the file comment.

30

I see we use Decl* here and elsewhere (WalkAST etc), is there any reason of not using const Decl*?

49

nit: rename the Visitor to CB? Visitor reminds me too much of ASTVisitor...

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

45

+1

56

nit: remove.

[kadircet]

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

15

right, i've seen that comment as well and wanted to pile up there. there are already uses of <variant> in LLVM today, TableGen, DenseMap, CodeGen, flang, pseudo, MLIR and lldb are some examples of big components. I don't see what they're doing to compile those today.

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

121

yup, that's definitely something i've in pending patches.

[kadircet]

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

52

thanks, i think the conclusion is B) here, but definitely didn't notice the implications of early bailout here. adding some comments.

[kadircet]

• Address comments

[kadircet]

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

15

as mentioned in https://discourse.llvm.org/t/rfc-bump-minimal-requirements-apple-clang-9-3-10-0-0-before-4th-tue-in-january/66156/7?u=kadircet, LLVM is already enforcing apple clang 10.0.0 effectively (and hopefully documentation will also change soon).

hence i am moving forward with this change. in the unlikely event of community taking a different approach (like downgrading the minimum requirements), i am more than happy to get rid of the std::variant usage here.

[sammccall]

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

27

Doh, I was skimming and missed that you removed the Location concept and folded stdlib handling into Symbol.

tooling::stdlib::Symbol only captures top-level symbols, so we've thrown away the identity of the actual symbol being accessed. This is not a complete disaster, but I think it causes problems, and I think we should be very deliberate and consistent about what information we preserve vs throw away.

Some examples of how this might bite us:

• distinguishing between macros/decls is non-uniform (need to check separately for decl vs macro vs stdlib-decl vs stdlib-macro)
• can't treat different types of symbols e.g. constructors vs classes differently (you suggested elsewhere we could check the kind of targetdecl to implement external policies)
• can't treat nested classes differently (i.e. must treat std::vector and decltype(myvec)::iterator the same).
• can't print the name, e.g. the fixit hint for auto x = TimePoint<>::min() becomes include header <chrono> for 'std::chrono::time_point' instead of include header <chrono> for 'std::chrono::time_point<...>::min()'
• can't insert forward declarations with a code action (legal for c symbols)
• harder to understand/debug (is this an implicit reference to a copy constructor, move constructor, conversion operator, or the type itself? where *are* all the redecls? is this misclassified user code, such as a trait specialization)?

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/Tooling/Inclusions/StandardLibrary.h"
+#include "llvm/ADT/STLFunctionalExtras.h"
+#include <variant>
+
+namespace clang {
+class SourceLocation;
+class Decl;
+class FileEntry;
+namespace include_cleaner {
+
+/// An entity that can be referenced in the code.
+struct Symbol {
+  Symbol(Decl &D) : Storage(&D) {}
+  Symbol(tooling::stdlib::Symbol S) : Storage(S) {}
+
+private:
+  // FIXME: Add support for macros.
+  std::variant<const Decl *, tooling::stdlib::Symbol> Storage;
+};
+
+/// 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) {}
+
+  bool operator==(const Header &RHS) const { return Storage == RHS.Storage; }
+
+private:
+  // FIXME: Handle verbatim spellings.
+  std::variant<const FileEntry *, tooling::stdlib::Header> Storage;
+};
+/// A UsedSymbolCB is a callback invoked for each symbol reference seen.
+///
+/// References occur at a particular location, refer to a single symbol, and
+/// that symbol may be provided by several headers.
+/// FIXME: Provide signals about the reference type and providing headers so the
+/// caller can filter and rank the results.
+using UsedSymbolCB = llvm::function_ref<void(
+    SourceLocation RefLoc, Symbol Target, llvm::ArrayRef<Header> Providers)>;
+
+/// Find and report all references to symbols in a region of code.
+///
+/// The AST traversal is rooted at ASTRoots - typically top-level declarations
+/// 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);
+
+} // 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 "AnalysisInternal.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) {
+  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()));
+      }
+      // 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)});
+    });
+  }
+  // FIXME: Handle references of macros.
+}
+
+} // namespace clang::include_cleaner

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

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

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

 //===--- WalkAST.cpp - Find declaration references in the AST -------------===//
 //
 // 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/AST/RecursiveASTVisitor.h"
 
-namespace clang {
-namespace include_cleaner {
+namespace clang::include_cleaner {
 namespace {
 using DeclCallback = llvm::function_ref<void(SourceLocation, NamedDecl &)>;
 
 class ASTWalker : public RecursiveASTVisitor<ASTWalker> {
   DeclCallback Callback;
 
   void report(SourceLocation Loc, NamedDecl *ND) {
     if (!ND || Loc.isInvalid())

 };
 
 } // namespace
 
 void walkAST(Decl &Root, DeclCallback Callback) {
   ASTWalker(Callback).TraverseDecl(&Root);
 }
 
-} // namespace include_cleaner
-} // namespace clang
+} // namespace clang::include_cleaner

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 "clang/AST/ASTContext.h"
+#include "clang/Basic/FileManager.h"
+#include "clang/Basic/SourceLocation.h"
+#include "clang/Basic/SourceManager.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() {
+    $foo^foo();
+    std::$vector^vector v;
+  }
+  )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);
+  }
+
+  auto &SM = AST.sourceManager();
+  llvm::DenseMap<size_t, std::vector<Header>> OffsetToProviders;
+  walkUsed(TopLevelDecls, [&](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());
+  });
+  auto HeaderFile = AST.fileManager().getFile("header.h").get();
+  EXPECT_THAT(
+      OffsetToProviders,
+      UnorderedElementsAre(
+          Pair(Code.point("foo"), UnorderedElementsAre(Header(HeaderFile))),
+          Pair(Code.point("vector"),
+               UnorderedElementsAre(Header(
+                   tooling::stdlib::Header::named("<vector>").value())))));
+}
+
+} // namespace
+} // namespace clang::include_cleaner

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

 set(LLVM_LINK_COMPONENTS
   Support
   TestingSupport
   )
 
 add_custom_target(ClangIncludeCleanerUnitTests)
 add_unittest(ClangIncludeCleanerUnitTests ClangIncludeCleanerTests
+  AnalysisTest.cpp
   RecordTest.cpp
   WalkASTTest.cpp
 )
 
 target_include_directories(ClangIncludeCleanerTests
   PRIVATE
   ${CMAKE_CURRENT_SOURCE_DIR}/../lib)
 
 clang_target_link_libraries(ClangIncludeCleanerTests
   PRIVATE
   clangAST
   clangBasic
   clangFrontend
+  clangToolingInclusionsStdlib
   )
 
 target_link_libraries(ClangIncludeCleanerTests
   PRIVATE
   clangIncludeCleaner
   clangTesting
   LLVMTestingSupport
   )
 

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

+//===--- WalkASTTest.cpp ------------------------------------------- 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
+//
+//===----------------------------------------------------------------------===//
 #include "AnalysisInternal.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/Basic/FileManager.h"
+#include "clang/Basic/SourceLocation.h"
 #include "clang/Frontend/TextDiagnostic.h"
 #include "clang/Testing/TestAST.h"
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Testing/Support/Annotations.h"
+#include "gmock/gmock.h"
 #include "gtest/gtest.h"
+#include <cstddef>
+#include <vector>
 
-namespace clang {
-namespace include_cleaner {
+namespace clang::include_cleaner {
 namespace {
+using testing::Pair;
+using testing::UnorderedElementsAre;
 
 // Specifies a test of which symbols are referenced by a piece of code.
 //
 // Example:
 //   Target:      int ^foo();
 //   Referencing: int x = ^foo();
 // There must be exactly one referencing location marked.
 void testWalk(llvm::StringRef TargetCode, llvm::StringRef ReferencingCode) {
)cpp",
            "int y = ^x;");
   testWalk(R"cpp(
     namespace ns { struct S; } // Not used
     using ns::S; // FIXME: S should be used
   )cpp",
            "^S *x;");
 }
 
 } // namespace
-} // namespace include_cleaner
-} // namespace clang
+} // namespace clang::include_cleaner