[include-cleaner] Make use of locateSymbol in WalkUsed

[kadircet]

Summary

Depens on D135953

[kadircet]

• Rebase

[hokein]

sorry for the delay, just realize it is sitting in the review list, left some comments.

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

25

nit: this name is similar to findHeaders (not sure this is intended), I'd rather use a different name (something like headersForSymbol)

44

I agree the place here might be on a performance-critical path, but I think the idea of using cache probably needs some bits of design, the current implementation seems half baked (there is also a FIXME in the findAllHeaders saying we should implement another cache for it, so it is unclear to me what's the whole picture).

Can we just leave out all cache in this patch with a FIXME? And having a follow-up patch for that?

46

any reason not using llvm::DenseMap?

52–55

nit: consider using structure binding to get rid of the Insert.first, Insert.second magic names.

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

112–113

it feels weird that all other tests are using WalkUsedTest, but not this one.

The logic are mostly the same except that this test doesn't need to build the AST nodes, if we change offsetToProviders method to offset(llvm::ArrayRef<Decl*> TopLevelDecl, llvm::ArrayRef<SymbolReference> MacroRef, SourceManager &SM), I think we can use it in this test.

[kadircet]

• Address comments

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

44

i agree that the cache for findHeaders is a bit more nuanced, as it'll need to have assumptions about a given SymbolLocation, no matter how/where it was acquired will return the same results.
but i am not sure what's complicated/unclear about the cache for decl to headers. The benefit is clear as explained in the comment around saving computations every time a foo is referenced inside the file.
Since both the benefit is clear and the assumption around "a decl having the same set of providers" sounds simple and sane enough, i'd actually keep this one in.

[sammccall]

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

44

I also think this needs a bit more examination. It seems cheap, but there are several overlapping concerns and addressing the first is always cheap but makes the others more expensive.

e.g. here, it's not obvious which of these is most desirable and therefore should probably be done first:

• caching symbol => header
• caching (part of) location => header
• caching/optimizing location => fileid
• propagating signals across these steps
• exposing location from the API
• keeping the implementation simple

I don't personally have a strong intuition of which of these steps should be cached for performance, if any of them will really matter, and whether we're better off caching end-to-end (cache a longer computation, lower hit-rate) vs individual steps (small computation, higher hit-rate).

To me this seems premature without *at least* measuring that it improves performance, but ideally showing that it's better than caching at a different level.

clang-tools-extra/include-cleaner/test/html.cpp

7

I'd like to keep a very simple smoke test of the HTML report.

If you're aiming to test something specific here about the HTML report, I'd suggest creating a new test describing what it is. (Though generally speaking, the HTML test has poor test coverage of its details, which I think is unfortunately the right tradeoff)

If you're aiming to provide an integration test (these locations are taken into account in making overall decisions), I think this should be a test using -print=changes rather than -html.

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

61

shouldn't we have a location filter for the decls, to simulate RecordAST?

[kadircet]

clang-tools-extra/include-cleaner/test/html.cpp

7

thanks makes sense. print-changes didn't exist back in the day when i was putting together this patch and i forgot to update this piece.

i wasn't trying to test HTMLReport behaviour specifically, and it's probably not worth adding that anyways.

[kadircet]

• Drop the cache
• Use -print=changes in lit test
• Update unittest helper to limit decls to main file

[kadircet]

• Fix RUN: line in lit test

[hokein]

looks good from my side.

[sammccall]

LG, thanks!

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

30

nit: I think this would be better as a vaguer comment at a higher level (in walkUsed) like "it might be useful to cache some parts of this computation to save repeated work"

clang-tools-extra/include-cleaner/test/multiple-providers.cpp

1 ↗

(On Diff #480420)

nit: splitting RUN lines over lines makes copy/pasting/debugging lit tests harder and ends up being net-negative IMO. I've added a .clang-format file so that >80 col lines won't get split

[kadircet]

clang-tools-extra/include-cleaner/test/multiple-providers.cpp

1 ↗

(On Diff #480420)

i also have some extra enforcement by my editor for line breaks :P. i didn't know copy pasting run lines were a workflow (because they usually have place holders one needs to change afterwards), i've always used the command line printed with the failing test. makes sense to keep it in a single line for people with such a workflow though.

[kadircet]

• Address comments

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-include-cleaner/Record.h"
 #include "clang-include-cleaner/Types.h"
 #include "clang/AST/ASTContext.h"
+#include "clang/AST/Decl.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Tooling/Inclusions/StandardLibrary.h"
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
 
 namespace clang::include_cleaner {
 
+namespace {
+// Gets all the providers for a symbol by tarversing each location.
+llvm::SmallVector<Header> headersForSymbol(const Symbol &S,
+                                           const SourceManager &SM,
+                                           const PragmaIncludes *PI) {
+  llvm::SmallVector<Header> Headers;
+  for (auto &Loc : locateSymbol(S))
+    // FIXME: findHeaders in theory returns the same result for all source
+    // locations in the same FileID. Have a cache for that, since we can have
+    // multiple declarations coming from the same file.
+    Headers.append(findHeaders(Loc, SM, PI));
+  return Headers;
+}
+} // namespace
+
 void walkUsed(llvm::ArrayRef<Decl *> ASTRoots,
               llvm::ArrayRef<SymbolReference> MacroRefs,
               const PragmaIncludes *PI, const SourceManager &SM,
               UsedSymbolCB CB) {
   // This is duplicated in writeHTMLReport, changes should be mirrored there.
+
+  // Cache for decl to header mappings, as the same decl might be referenced in
+  // multiple locations and finding providers for each location is expensive.
+  llvm::DenseMap<NamedDecl *, llvm::SmallVector<Header>> DeclToHeaders;
   tooling::stdlib::Recognizer Recognizer;
   for (auto *Root : ASTRoots) {
     auto &SM = Root->getASTContext().getSourceManager();
     walkAST(*Root, [&](SourceLocation Loc, NamedDecl &ND, RefType RT) {
       SymbolReference SymRef{Loc, ND, RT};
-      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(SymRef, findHeaders(*SS, SM, PI));
-      }
-      // FIXME: Extract locations from redecls.
-      return CB(SymRef, findHeaders(ND.getLocation(), SM, PI));
+      auto [It, Inserted] = DeclToHeaders.try_emplace(&ND);
+      if (Inserted)
+        It->second = headersForSymbol(ND, SM, PI);
+      return CB(SymRef, It->second);
     });
   }
   for (const SymbolReference &MacroRef : MacroRefs) {
     assert(MacroRef.Target.kind() == Symbol::Macro);
-    CB(MacroRef, findHeaders(MacroRef.Target.macro().Definition, SM, PI));
+    return CB(MacroRef, headersForSymbol(MacroRef.Target, SM, PI));
   }
 }
 
 } // namespace clang::include_cleaner

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

struct Ref {
     SmallVector<SymbolLocation> Locations = {};
     SmallVector<Header> Headers = {};
     SmallVector<const Include *> Includes = {};
     bool Satisfied = false;  // Is the include present?
     std::string Insert = {}; // If we had no includes, what would we insert?
   };
   std::vector<Ref> Refs;
   llvm::DenseMap<const Include *, std::vector<unsigned>> IncludeRefs;
-  llvm::StringMap<std::vector</*RefIndex*/unsigned>> Insertion;
+  llvm::StringMap<std::vector</*RefIndex*/ unsigned>> Insertion;
 
   llvm::StringRef includeType(const Include *I) {
     auto &List = IncludeRefs[I];
     if (List.empty())
       return "unused";
     if (llvm::any_of(List, [&](unsigned I) {
           return Refs[I].Type == RefType::Explicit;
         }))
std::string spellHeader(const Header &H) {
     case Header::Verbatim:
       return H.verbatim().str();
     }
     llvm_unreachable("Unknown Header kind");
   }
 
   void fillTarget(Ref &R) {
     // Duplicates logic from walkUsed(), which doesn't expose SymbolLocations.
-    // FIXME: use locateDecl and friends once implemented.
-    // This doesn't use stdlib::Recognizer, but locateDecl will soon do that.
-    switch (R.Sym.kind()) {
-    case Symbol::Declaration:
-      R.Locations.push_back(R.Sym.declaration().getLocation());
-      break;
-    case Symbol::Macro:
-      R.Locations.push_back(R.Sym.macro().Definition);
-      break;
-    }
-
+    for (auto &Loc : locateSymbol(R.Sym))
+      R.Locations.push_back(Loc);
     for (const auto &Loc : R.Locations)
       R.Headers.append(findHeaders(Loc, SM, PI));
 
     for (const auto &H : R.Headers) {
       R.Includes.append(Includes.match(H));
       // FIXME: library should signal main-file refs somehow.
       // Non-physical refs to the main-file should be possible.
       if (H.kind() == Header::Physical && H.physical() == MainFE)
         R.Satisfied = true;
     }
     if (!R.Includes.empty())
       R.Satisfied = true;
     // Include pointers are meaningfully ordered as they are backed by a vector.
     llvm::sort(R.Includes);
     R.Includes.erase(std::unique(R.Includes.begin(), R.Includes.end()),
                      R.Includes.end());
 
     if (!R.Headers.empty())
       // FIXME: library should tell us which header to use.
       R.Insert = spellHeader(R.Headers.front());
   }
 
 public:
   Reporter(llvm::raw_ostream &OS, ASTContext &Ctx, HeaderSearch &HS,
-           const include_cleaner::Includes &Includes,
-           const PragmaIncludes *PI, FileID MainFile)
+           const include_cleaner::Includes &Includes, const PragmaIncludes *PI,
+           FileID MainFile)
       : OS(OS), Ctx(Ctx), SM(Ctx.getSourceManager()), HS(HS),
         Includes(Includes), PI(PI), MainFile(MainFile),
         MainFE(SM.getFileEntryForID(MainFile)) {}
 
   void addRef(const SymbolReference &SR) {
     auto [File, Offset] = SM.getDecomposedLoc(SM.getFileLoc(SR.RefLocation));
     if (File != this->MainFile) {
       // Can get here e.g. if there's an #include inside a root Decl.
if (!Loc.isMacroID())
       return printFilename(Loc.printToString(SM));
 
     // Replicating printToString() is a bit simpler than parsing/reformatting.
     printFilename(SM.getExpansionLoc(Loc).printToString(SM));
     OS << " &lt;Spelling=";
     printFilename(SM.getSpellingLoc(Loc).printToString(SM));
     OS << ">";
   }
-  
   // Write "Provides: " rows of an include or include-insertion table.
   // These describe the symbols the header provides, referenced by RefIndices.
   void writeProvides(llvm::ArrayRef<unsigned> RefIndices) {
     // We show one ref for each symbol: first by (RefType != Explicit, Sequence)
     llvm::DenseMap<Symbol, /*RefIndex*/ unsigned> FirstRef;
     for (unsigned RefIndex : RefIndices) {
       const Ref &R = Refs[RefIndex];
       auto I = FirstRef.try_emplace(R.Sym, RefIndex);
void writeInclude(const Include &Inc) {
     if (Inc.Resolved) {
       OS << "<tr><th>Resolved</td><td>";
       escapeString(Inc.Resolved->getName());
       OS << "</td></tr>\n";
       writeProvides(IncludeRefs[&Inc]);
     }
     OS << "</table>";
   }
-  
   void writeInsertion(llvm::StringRef Text, llvm::ArrayRef<unsigned> Refs) {
     OS << "<table class='insertion'>";
     writeProvides(Refs);
     OS << "</table>";
   }
 
   void writeTarget(const Ref &R) {
     OS << "<table class='target " << refType(R.Type) << "'>";
void writeCode() {
 
     OS << "<pre onclick='select(event)' class='code'>";
 
     std::vector<llvm::StringRef> Insertions{Insertion.keys().begin(),
                                             Insertion.keys().end()};
     llvm::sort(Insertions);
     for (llvm::StringRef Insertion : Insertions) {
       OS << "<code class='line added'>"
-          << "<span class='inc sel inserted' data-hover='i";
       escapeString(Insertion);
       OS << "'>#include ";
       escapeString(Insertion);
       OS << "</span></code>\n";
     }
 
     const Include *Inc = nullptr;
     unsigned LineNum = 0;

clang-tools-extra/include-cleaner/test/Inputs/foo2.h

+#ifndef FOO2_H
+#define FOO2_H
+
+int foo();
+
+#endif

clang-tools-extra/include-cleaner/test/html.cpp

 // RUN: clang-include-cleaner -html=- %s -- -I %S/Inputs | FileCheck %s
 #include "bar.h"
 #include "foo.h"
+#include "foo2.h"
 
 int n = foo();
+// CHECK: Symbol{{.*}}foo
+// CHECK-NEXT: int foo()
+// CHECK-NEXT: Location{{.*}}foo.h:4:5
+// CHECK-NEXT: Location{{.*}}foo2.h:4:5
 // CHECK: <span class='ref sel' data-hover='t{{[0-9]+}}'>foo</span>()

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

 #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/Support/Error.h"
 #include "llvm/Testing/Support/Annotations.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include <cstddef>
 
 namespace clang::include_cleaner {
 namespace {
+using testing::Contains;
 using testing::Pair;
 using testing::UnorderedElementsAre;
 
 std::string guard(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"] = guard(R"cpp(
-  void foo();
-  namespace std { class vector {}; }
-  )cpp");
-  Inputs.ExtraFiles["private.h"] = guard(R"cpp(
-    // IWYU pragma: private, include "path/public.h"
-    class Private {};
-  )cpp");
-
+class WalkUsedTest : public testing::Test {
+protected:
+  TestInputs Inputs;
   PragmaIncludes PI;
-  Inputs.MakeAction = [&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;
         }
 
         PragmaIncludes *Out;
       };
       return std::make_unique<Hook>(&PI);
     };
-  TestAST AST(Inputs);
+  }
 
+  llvm::DenseMap<size_t, std::vector<Header>>
+  offsetToProviders(TestAST &AST, SourceManager &SM,
+                    llvm::ArrayRef<SymbolReference> MacroRefs = {}) {
     llvm::SmallVector<Decl *> TopLevelDecls;
-  for (Decl *D : AST.context().getTranslationUnitDecl()->decls()) {
+    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,
+    walkUsed(TopLevelDecls, MacroRefs, &PI, SM,
              [&](const SymbolReference &Ref, llvm::ArrayRef<Header> Providers) {
                auto [FID, Offset] = SM.getDecomposedLoc(Ref.RefLocation);
-             EXPECT_EQ(FID, SM.getMainFileID());
+               if (FID != SM.getMainFileID())
+                 ADD_FAILURE() << "Reference outside of the main file!";
                OffsetToProviders.try_emplace(Offset, Providers.vec());
              });
-  auto &FM = AST.fileManager();
-  auto HeaderFile = Header(FM.getFile("header.h").get());
+    return OffsetToProviders;
+  }
+};
+
+TEST_F(WalkUsedTest, Basic) {
+  llvm::Annotations Code(R"cpp(
+  #include "header.h"
+  #include "private.h"
+
+  void $bar^bar($private^Private) {
+    $foo^foo();
+    std::$vector^vector $vconstructor^v;
+  }
+  )cpp");
+  Inputs.Code = Code.code();
+  Inputs.ExtraFiles["header.h"] = guard(R"cpp(
+  void foo();
+  namespace std { class vector {}; }
+  )cpp");
+  Inputs.ExtraFiles["private.h"] = guard(R"cpp(
+    // IWYU pragma: private, include "path/public.h"
+    class Private {};
+  )cpp");
+
+  TestAST AST(Inputs);
+  auto &SM = AST.sourceManager();
+  auto HeaderFile = Header(AST.fileManager().getFile("header.h").get());
+  auto PrivateFile = Header(AST.fileManager().getFile("private.h").get());
+  auto PublicFile = Header("\"path/public.h\"");
   auto MainFile = Header(SM.getFileEntryForID(SM.getMainFileID()));
   auto VectorSTL = Header(tooling::stdlib::Header::named("<vector>").value());
   EXPECT_THAT(
-      OffsetToProviders,
+      offsetToProviders(AST, SM),
       UnorderedElementsAre(
           Pair(Code.point("bar"), UnorderedElementsAre(MainFile)),
           Pair(Code.point("private"),
-               UnorderedElementsAre(Header("\"path/public.h\""),
-                                    Header(FM.getFile("private.h").get()))),
+               UnorderedElementsAre(PublicFile, PrivateFile)),
           Pair(Code.point("foo"), UnorderedElementsAre(HeaderFile)),
           Pair(Code.point("vector"), UnorderedElementsAre(VectorSTL)),
           Pair(Code.point("vconstructor"), UnorderedElementsAre(VectorSTL))));
 }
 
-TEST(WalkUsed, MacroRefs) {
-  llvm::Annotations Hdr(R"cpp(
-    #define ^ANSWER 42
+TEST_F(WalkUsedTest, MultipleProviders) {
+  llvm::Annotations Code(R"cpp(
+  #include "header1.h"
+  #include "header2.h"
+  void foo();
+
+  void bar() {
+    $foo^foo();
+  }
+  )cpp");
+  Inputs.Code = Code.code();
+  Inputs.ExtraFiles["header1.h"] = guard(R"cpp(
+  void foo();
+  )cpp");
+  Inputs.ExtraFiles["header2.h"] = guard(R"cpp(
+  void foo();
   )cpp");
-  llvm::Annotations Main(R"cpp(
+
+  TestAST AST(Inputs);
+  auto &SM = AST.sourceManager();
+  auto HeaderFile1 = Header(AST.fileManager().getFile("header1.h").get());
+  auto HeaderFile2 = Header(AST.fileManager().getFile("header2.h").get());
+  auto MainFile = Header(SM.getFileEntryForID(SM.getMainFileID()));
+  EXPECT_THAT(
+      offsetToProviders(AST, SM),
+      Contains(Pair(Code.point("foo"),
+                    UnorderedElementsAre(HeaderFile1, HeaderFile2, MainFile))));
+}
+
+TEST_F(WalkUsedTest, MacroRefs) {
+  llvm::Annotations Code(R"cpp(
     #include "hdr.h"
     int x = ^ANSWER;
   )cpp");
-
-  SourceManagerForFile SMF("main.cpp", Main.code());
-  auto &SM = SMF.get();
-  const FileEntry *HdrFile =
-      SM.getFileManager().getVirtualFile("hdr.h", Hdr.code().size(), 0);
-  SM.overrideFileContents(HdrFile,
-                          llvm::MemoryBuffer::getMemBuffer(Hdr.code().str()));
-  FileID HdrID = SM.createFileID(HdrFile, SourceLocation(), SrcMgr::C_User);
+  llvm::Annotations Hdr(guard("#define ^ANSWER 42"));
+  Inputs.Code = Code.code();
+  Inputs.ExtraFiles["hdr.h"] = Hdr.code();
+  TestAST AST(Inputs);
+  auto &SM = AST.sourceManager();
+  auto HdrFile = SM.getFileManager().getFile("hdr.h").get();
+  auto HdrID = SM.translateFile(HdrFile);
 
   IdentifierTable Idents;
   Symbol Answer =
       Macro{&Idents.get("ANSWER"), SM.getComposedLoc(HdrID, Hdr.point())};
-  llvm::DenseMap<size_t, std::vector<Header>> OffsetToProviders;
-  walkUsed(/*ASTRoots=*/{}, /*MacroRefs=*/
-           {SymbolReference{SM.getComposedLoc(SM.getMainFileID(), Main.point()),
-                            Answer, RefType::Explicit}},
-           /*PI=*/nullptr, 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());
-           });
-
   EXPECT_THAT(
-      OffsetToProviders,
-      UnorderedElementsAre(Pair(Main.point(), UnorderedElementsAre(HdrFile))));
+      offsetToProviders(
+          AST, SM,
+          {SymbolReference{SM.getComposedLoc(SM.getMainFileID(), Code.point()),
+                           Answer, RefType::Explicit}}),
+      UnorderedElementsAre(Pair(Code.point(), UnorderedElementsAre(HdrFile))));
 }
 
-
 } // namespace
 } // namespace clang::include_cleaner