[IncludeCleaner] Introduce decl to location mapping

[kadircet]

Summary

Creates a one to many mapping, by returning all the possible locations
providing a decl. Also includes an "is definition" signal for the
location, that can be used for ranking afterwards.

This also takes care of stdlib symbols by having a variant of locations.

Depends on D135859.

[sammccall]

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

54

This is an important public API concept ==> It should be documented and part of a public header, I think

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

167 ↗

(On Diff #467715)

I don't think "definition" is the right concept here, the better signal in experiments was "is this declaration usable in general", which a function forward declaration is.
(In the prototype this was IsComplete and only set for template/class cases where completeness matters, InIncomplete is probably a bit cleaner.)

Also it would be nice to avoid passing bools around to represent subtle concepts (which definition is).

[tschuett]

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

54

IIRC, the supported Apple Clang does not support std::variant yet.

[tschuett]

We support Apple Clang 9.3, but std:variant ships with Apple Clang 10.0. :-(

[kadircet]

In D135953#3861180, @tschuett wrote:

We support Apple Clang 9.3, but std:variant ships with Apple Clang 10.0. :-(

Hi @tschuett, there are other pieces of LLVM that use <variant> today already, some big components include TableGen, DenseMap, CodeGen, flang, pseudo, MLIR. so i guess LLVM is already non-compilable today on apple clang 9.3 and someone needs to do a cleanup (i am happy to drop the usage here and in my other patches, but it won't prevent others from introducing more usage, so I don't see how useful my changes here would be)

I've brought this up in https://discourse.llvm.org/t/important-new-toolchain-requirements-to-build-llvm-will-most-likely-be-landing-within-a-week-prepare-your-buildbots/61447/12?u=kadircet. Please pile up on that thread if you're a maintainer for that particular toolchain, rather than just a concerned citizen.

[kadircet]

• Rebase
• Move to new file
• Handle macros
• Change from boolean output to enum for signalling

[sammccall]

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

85

can you explain the design of hints a bit?

In particular:

• are hints emitted by every mapping layer (node -> symbol -> location -> header -> include)? if so, are they the same kind (i.e. same enum?)
• are the hints from one stage provided to subsequent stages?
• node -> symbol mapping already produces hints in the form of RefKind, do we reconcile these concepts somehow?
• do hints for the same entity found on different paths get merged, or will we ultimately report a list of vector<HintedHeader> where the same header may repeat with different hints?

87

Is this intended to be:

• a bit? needs to be nonzero
• a set of bits? should be None or so as it does not set any bits
• something else? I don't understand

89

You're only setting this in cases where incompleteness is possible and significant. e.g. for AliasDecls it is not set even though they are (shallowly) complete.

I think the most self-documenting solution is to invert it to Incomplete.
Otherwise the docs here should explain when it is set vs not set.

96

Having been down this path, I think using a pair for this is too clumsy for such an important data type (and this may be repeated for each mapping layer).

I'd suggest a template that can attach hints to another type, and acts as a smart pointer to that type: Loc->kind(), Loc.hint() rather than Loc.first.kind(), Loc.second, can define a decent print function, etc.

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

21

Hmm, this isn't list (e.g. ObjCCategoryDecl), is hard to complete, and we don't actually have to complete it to get the correct behavior. This suggests it's not the right primitive, e.g. it's hard to look at the code and see whether there's a bug.

One option would be to make this function isIncomplete, call it on each redecl, and use isThisDeclarationADefinition.
But we can also avoid the chain of dyn_casts for each redecl by making this function something like Optional<Decl*> getCompletingDefinition() where None means any redecl is complete (usable without definition) and nullptr means no redecl is complete (definition needed but not found), and a pointer means that redecl is complete and no other is.

25

the net result of include VarDecl and FunctionDecl here is that we prefer headers defining these things over headers declaring them. How sure are we that this is a good heuristic?

I thought the idea here was "prefer declarations that are complete enough to use", which is basically for classes & templates, but not functions and variables.

If it's rather "definitions are more likely to be the thing we want" then the hint should probably be named Definition rather than Complete.

40

I think the same logic that says we include a header that is // IWYU pragma private says we should, probably with some Private hint.

42

nit: I think {{...}} is less confusing for both compilers and humans if you spell the inner type

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

20 ↗

(On Diff #476091)

unused? and the other two

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

37

this is a heavy helper that embeds the assertions inside itself, which is a pattern that has gotten us into trouble in the past.

locateSymbol has a pretty simple signature and seems possible to test more directly with something like:

LocateExample X("struct $decl^foo; struct $def^foo {};");
EXPECT_THAT(
    locateSymbol(X.findDecl("decl", "foo")),
    ElementsAre(
        Pair(X.loc("decl"), 0),
        Pair(X.loc("def"), Hint::Complete));

it's a little longer, but also more flexible (tests hints without hacks, can test standard library, can test macros), is attached to the right line, etc

72

def seems like a strange annotation for Complete - again definition/complete should be different concepts or have the same name

92

this doesn't actually test that it does the right thing: it would pass if it returns nothing

93

should we have at least a simple testcase for macros?

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

17 ↗

(On Diff #476091)

I can't see where twine/variant are used, is a tool suggesting these?

[kadircet]

• Leaving out all the pieces around signals as discussed.
• Update tests to use a LocateExample helper, have a test for macros.
• Get rid of residues in other test files.

[sammccall]

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

29

unused?

(flagging these in case these are tool-assisted but the tool is buggy)

30

unused?

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

53

or maybe clearer return Inputs, and you're calling AST(Inputs) as the member initializer

76

nit: you have an assertion here but not in findMacro

113

<< Case, or SCOPED_TRACE, or something so we can see what test it is

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

 //===----------------------------------------------------------------------===//
 
 #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 "clang/Tooling/Inclusions/StandardLibrary.h"
 #include "llvm/ADT/STLFunctionalExtras.h"
+#include <variant>
+#include <vector>
 
 namespace clang {
 class ASTContext;
 class Decl;
 class HeaderSearch;
 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.
 /// - the RefType describes the relation between the SourceLocation and the
 ///   NamedDecl.
 ///
 /// 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 &, RefType)>);
 
 /// A place 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).
 struct SymbolLocation {
   enum Kind {
     /// A position within a source file (or macro expansion) parsed by clang.
     Physical,
     /// A recognized standard library symbol, like std::string.
     Standard,
   };
 
   SymbolLocation(SourceLocation S) : Storage(S) {}
   SymbolLocation(tooling::stdlib::Symbol S) : Storage(S) {}
 
   Kind kind() const { return static_cast<Kind>(Storage.index()); }
   bool operator==(const SymbolLocation &RHS) const {
     return Storage == RHS.Storage;
   }
-
   SourceLocation physical() const { return std::get<Physical>(Storage); }
   tooling::stdlib::Symbol standard() const {
     return std::get<Standard>(Storage);
   }
 
 private:
   // Order must match Kind enum!
   std::variant<SourceLocation, tooling::stdlib::Symbol> Storage;
 };
 llvm::raw_ostream &operator<<(llvm::raw_ostream &, const SymbolLocation &);
 
 /// Finds the headers that provide the symbol location.
 // FIXME: expose signals
 llvm::SmallVector<Header> findHeaders(const SymbolLocation &Loc,
                                       const SourceManager &SM,
                                       const PragmaIncludes *PI);
 
 /// Write an HTML summary of the analysis to the given stream.
 void writeHTMLReport(FileID File, const Includes &,
                      llvm::ArrayRef<Decl *> Roots,
                      llvm::ArrayRef<SymbolReference> MacroRefs, ASTContext &Ctx,
                      HeaderSearch &HS, PragmaIncludes *PI,
                      llvm::raw_ostream &OS);
 
+/// A set of locations that provides the declaration.
+std::vector<SymbolLocation> locateSymbol(const Symbol &S);
+
 } // namespace include_cleaner
 } // namespace clang
 
 #endif

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

-//===--- LocateSymbol.cpp -------------------------------------------------===//
+//===--- LocateSymbol.cpp - Find locations providing a symbol -------------===//
 //
 // 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/DeclBase.h"
+#include "clang/Basic/SourceLocation.h"
+#include "clang/Tooling/Inclusions/StandardLibrary.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Support/raw_ostream.h"
+#include <utility>
+#include <vector>
 
 namespace clang::include_cleaner {
+namespace {
+
+std::vector<SymbolLocation> locateDecl(const Decl &D) {
+  std::vector<SymbolLocation> Result;
+  // FIXME: Should we also provide physical locations?
+  if (auto SS = tooling::stdlib::Recognizer()(&D))
+    return {SymbolLocation(*SS)};
+  for (auto *Redecl : D.redecls())
+    Result.push_back(Redecl->getLocation());
+  return Result;
+}
+
+} // namespace
 
 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const SymbolLocation &S) {
   switch (S.kind()) {
   case SymbolLocation::Physical:
     // We can't decode the Location without SourceManager. Its raw
     // representation isn't completely useless (and distinguishes
     // SymbolReference from Symbol).
     return OS << "@0x"
               << llvm::utohexstr(
                      S.physical().getRawEncoding(), /*LowerCase=*/false,
                      /*Width=*/CHAR_BIT * sizeof(SourceLocation::UIntTy));
   case SymbolLocation::Standard:
     return OS << S.standard().scope() << S.standard().name();
   }
   llvm_unreachable("Unhandled Symbol kind");
 }
 
-} // namespace clang::include_cleaner
+std::vector<SymbolLocation> locateSymbol(const Symbol &S) {
+  switch (S.kind()) {
+  case Symbol::Declaration:
+    return locateDecl(S.declaration());
+  case Symbol::Macro:
+    return {SymbolLocation(S.macro().Definition)};
+  }
+}
+
+} // 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
   FindHeadersTest.cpp
+  LocateSymbolTest.cpp
   RecordTest.cpp
   TypesTest.cpp
   WalkASTTest.cpp
 )
 
 target_include_directories(ClangIncludeCleanerTests
   PRIVATE
   ${CMAKE_CURRENT_SOURCE_DIR}/../lib)

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

+//===--- LocateSymbolTest.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-include-cleaner/Types.h"
+#include "clang/AST/Decl.h"
+#include "clang/AST/DeclBase.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/ASTMatchers/ASTMatchers.h"
+#include "clang/Basic/SourceLocation.h"
+#include "clang/Lex/Preprocessor.h"
+#include "clang/Testing/TestAST.h"
+#include "clang/Tooling/Inclusions/StandardLibrary.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Testing/Support/Annotations.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include <cstddef>
+#include <memory>
+#include <unordered_map>
+#include <utility>
+#include <variant>
+#include <vector>
+
+namespace clang::include_cleaner {
+namespace {
+using testing::ElementsAre;
+using testing::ElementsAreArray;
+using testing::Pair;
+using testing::UnorderedElementsAre;
+
+// A helper for building ASTs and getting decls out of it by name. Example usage
+// looks like:
+//   LocateExample X("void ^foo();");
+//   Decl &Foo = X.findDecl("foo");
+//   X.points(); // returns all the points in annotated test input.
+struct LocateExample {
+private:
+  llvm::Annotations Target;
+  TestAST AST;
+
+public:
+  LocateExample(llvm::StringRef AnnotatedCode)
+      : Target(AnnotatedCode), AST([this] {
+          TestInputs Inputs(Target.code());
+          Inputs.ExtraArgs.push_back("-std=c++17");
+          return Inputs;
+        }()) {}
+
+  const Decl &findDecl(llvm::StringRef SymbolName) {
+    const NamedDecl *DeclToLocate;
+    struct MatchCB : public ast_matchers::MatchFinder::MatchCallback {
+      MatchCB(const NamedDecl *&Out) : Out(Out) {}
+      void run(const ast_matchers::MatchFinder::MatchResult &Result) override {
+        Out = Result.Nodes.getNodeAs<NamedDecl>("id");
+        assert(Out);
+        Out = llvm::cast<NamedDecl>(Out->getCanonicalDecl());
+      }
+      const NamedDecl *&Out;
+    } CB(DeclToLocate);
+    ast_matchers::MatchFinder Finder;
+    Finder.addMatcher(ast_matchers::namedDecl(
+                          ast_matchers::unless(ast_matchers::isImplicit()),
+                          ast_matchers::hasName(SymbolName))
+                          .bind("id"),
+                      &CB);
+    Finder.matchAST(AST.context());
+    if (!DeclToLocate)
+      ADD_FAILURE() << "Couldn't find any decls with name: " << SymbolName;
+    assert(DeclToLocate);
+    return *DeclToLocate;
+  }
+
+  Macro findMacro(llvm::StringRef Name) {
+    auto &PP = AST.preprocessor();
+    auto *II = PP.getIdentifierInfo(Name);
+    if (!II || !II->hasMacroDefinition()) {
+      ADD_FAILURE() << "Couldn't find any macros with name: " << Name;
+      return {};
+    }
+    auto MD = PP.getMacroDefinition(II);
+    assert(MD.getMacroInfo());
+    return {II, MD.getMacroInfo()->getDefinitionLoc()};
+  }
+
+  std::vector<SymbolLocation> points() {
+    auto &SM = AST.sourceManager();
+    auto FID = SM.getMainFileID();
+    auto Offsets = Target.points();
+    std::vector<SymbolLocation> Results;
+    for (auto &Offset : Offsets)
+      Results.emplace_back(SM.getComposedLoc(FID, Offset));
+    return Results;
+  }
+};
+
+TEST(LocateSymbol, Decl) {
+  // Looks for decl with name 'foo' and performs locateSymbol on it.
+  // Expects all the locations in the case to be returned as a location.
+  const llvm::StringLiteral Cases[] = {
+      "struct ^foo; struct ^foo {};",
+      "namespace ns { void ^foo(); void ^foo() {} }",
+      "enum class ^foo; enum class ^foo {};",
+  };
+
+  for (auto &Case : Cases) {
+    SCOPED_TRACE(Case);
+    LocateExample Test(Case);
+    EXPECT_THAT(locateSymbol(Test.findDecl("foo")),
+                ElementsAreArray(Test.points()));
+  }
+}
+
+TEST(LocateSymbol, Stdlib) {
+  LocateExample Test("namespace std { struct vector; }");
+  EXPECT_THAT(locateSymbol(Test.findDecl("vector")),
+              ElementsAre(*tooling::stdlib::Symbol::named("std::", "vector")));
+}
+
+TEST(LocateSymbol, Macros) {
+  // Make sure we preserve the last one.
+  LocateExample Test("#define FOO\n#undef FOO\n#define ^FOO");
+  EXPECT_THAT(locateSymbol(Test.findMacro("FOO")),
+              ElementsAreArray(Test.points()));
+}
+
+} // namespace
+} // namespace clang::include_cleaner