[Includecleaner] Introduce RefType to ast walking

[kadircet]

Summary

RefTypes are distinct categories for each reference to a symbol. They
are signals indicating strength of a reference, that'll enable different
decision making based on the finding being provided.

There are 3 kinds of ref types:

• Explicit, the reference is spelled in the code.
• Implicit, the reference is not directly visible in the code.
• Related, the reference exists but can't be proven as used (e.g. overloads brought in by a using decl but not used by the code).

[sammccall]

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

46–47

using default arguments here would reduce the noise level a lot

77

This doesn't correspond to the example given for RefKind: the docs suggest they are *unused* while here we don't know if they're used.

At least for this case it seems calling the RefKind Ambiguous would also be clearer.

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

120–123

This is very noisy. please find a way to avoid having to mark all test cases as $explicit, e.g. by splitting implicit cases into different tests

[hokein]

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

35

I'm wondering what's our plan of supporting policy (different coding-style may have different decisions about which includes are used)?

IIUC, the RefType is part of the picture, providing fine-grained information about each reference, and the caller can make their decisions based on it?

Thinking about the Implicit type, I think cases like non-spelled constructor call, implicit conversion calls (maybe more?) fall into this type, if we support Policy.Constructor, and Policy.Conversion, how do we distinguish with these cases? We can probably do some ad-hoc checks on the TargetDecl, but I'm not sure that the tuple <SourceLocation, TargetDecl, Ref> will provide enough information to implement different policy .

38

nit: default constructor call is vague -- S s = S(); it is a default constructor call, but it is not implicit, maybe more specific by giving a simple example, like default constructor call in S s;?

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

21

nit: it seems unused.

197–200

maybe add this following case, I think it will mark the the constructor S() implicit.

struct S { S(); };
S ^t;

198

nit: also add an implicit case

S t = 42;

[kadircet]

• Rename Related to Ambigious in RefKind
• Add more tests for implicit constructor calls
• Default to Explicit as RefKind when reporting references
• Don't report unused overloads, unless reference is inside a header

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

120–123

what about treating non-named points as explicit? that way we would only annotate non-explicit references (which are rare).

[kadircet]

• Clarify default constructor call example in RefType::Implicit

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

35

IIUC, the RefType is part of the picture, providing fine-grained information about each reference, and the caller can make their decisions based on it?

Exactly that's the idea.

if we support Policy.Constructor, and Policy.Conversion, how do we distinguish with these cases? We can probably do some ad-hoc checks on the TargetDecl

In our previous discussions we've also come to the conclusion that TargetDecl will have enough information for the caller to infer such information later on. We've decided to not make it part of the public api (at least initially) because it's unclear how widely useful those signals will be. But if it turns out to be needed by a variety of applications the design is extensible to either provide a:

• inferDetails(Symbol) helper, which would derive a signal structure that extracts most of those signals needed, or
• update Callback signature to also carry that information derived from the Symbol

Does that make sense?

[sammccall]

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

25

as discussed I moved the other vocab types into types.h

27

named by the reference? or am I missing a case

32

Ambiguous

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

35

In our previous discussions we've also come to the conclusion that TargetDecl will have enough information for the caller to infer such information later on

It was a while ago and my memory is bad, but this isn't my recollection (maybe you're talking about different discussions). I think it was rather "this is the bare minimum we need to get going, and we want to punt on real policy support for now".

At least "TargetDecl will have enough information" seems implausible on its face, e.g. how could you implement "types of variables are used, but types of expressions are not used" based on inspecting TargetDecl?

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

155–162

(this is the first assumption in this file that we're traversing the main file. Is it worth avoiding this by checking whether the root is written in the main file?)

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

51

ambiguous

51

tacking on boolean optional parameters to handle an uncommon option to a function called everywhere doesn't scale well.

What about detecting the string // header in ReferencingCode?
Or even // c++-header, thinking ahead to objc etc

120–123

Not sure implicit references are actually rare, more like our examples are trivial for now :-)

But I might be wrong, up to you.

(I would at least use $A^x instead of $ambiguous^x)

[kadircet]

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

35

It was a while ago and my memory is bad, but this isn't my recollection (maybe you're talking about different discussions). I think it was rather "this is the bare minimum we need to get going, and we want to punt on real policy support for now".
At least "TargetDecl will have enough information" seems implausible on its face, e.g. how could you implement "types of variables are used, but types of expressions are not used" based on inspecting TargetDecl?

Right. I wasn't talking about inferring signals about how a decl was found (e.g. type of an expression, as you've also mentioned), but rather talking about information about the decl itself (is this a member, constructor etc.).

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

120–123

i don't like the idea of splitting tests because i feel like that'll lead to duplicating lots of test cases when we have a mixture of references happening (e.g. implicit type conversion and an explicitly spelled type from same reference).

so another option i can think of here is returning annotations for points from testWalk and building expectations on top of that, e.g:

EXPECT_REFERENCES("void ^foo();", "void bar() { ^foo(); }", {"explicit"}); // checks that points in target have respective reference types
EXPECT_EXPLICIT_REFERENCES("void ^foo();", "void bar() { ^foo(); }"); // shorthand representation for making sure all the references are with a single annotation.

WDYT?

[kadircet]

• Fix typo in Ambiguous
• Rebase for Types.h, introduce SymbolReference
• Use comments rather than an optional parameter to indicate header-ness of main files in tests
• Rather than assuming Root is in main file, check that either root isn't in main file or main file is a header.

[hokein]

The current patch looks good from my side. There is a remaining discussion around the verbosity of unittests, but I think we should not be blocked by that.

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

112

nit: locaition => location.

116

what's is the edge? I understand it in some degree, but I'd avoid introducing new concept as it might lead to some confusions (and we haven't defined a graph anywhere in the code).

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

24

this is out-of-date, I think, the RefType is in Types.h.

[kadircet]

• Fix typo
• Change comment
• Use Types.h

[tschuett]

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

25

There is a cuter way to use anonymous namespaces:
https://llvm.org/docs/CodingStandards.html#anonymous-namespaces

[kadircet]

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

25

sorry missed that one, were you referring to definitions of methods? because AFAICT there isn't anything else inside this anon namespace that i can declare static in a named-namespace instead.
if that's the case, i don't think it's actually common in the codebase to define your methods out-of-line when the whole class is an implementation detail.

[tschuett]

No worries. The style asks to move the definitions out of the anonymous namespace, but ....

[maryammo]

@kadircet, this commit causes failure on https://lab.llvm.org/buildbot/#/builders/121 which is possible to reproduce locally, can you please take a look?

[35/111] Linking CXX executable tools/clang/tools/extra/include-cleaner/unittests/ClangIncludeCleanerTests
FAILED: tools/clang/tools/extra/include-cleaner/unittests/ClangIncludeCleanerTests 
: && /usr/lib64/ccache/c++  -fPIC -fno-semantic-interposition -fvisibility-inlines-hidden -Werror=date-time -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wno-missing-field-initializers -pedantic -Wno-long-long -Wimplicit-fallthrough -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-noexcept-type -Wdelete-non-virtual-dtor -Wno-comment -Wno-misleading-indentation -fdiagnostics-color -ffunction-sections -fdata-sections -fno-common -Woverloaded-virtual -fno-strict-aliasing -O3 -DNDEBUG  -Wl,--gc-sections tools/clang/tools/extra/include-cleaner/unittests/CMakeFiles/ClangIncludeCleanerTests.dir/AnalysisTest.cpp.o tools/clang/tools/extra/include-cleaner/unittests/CMakeFiles/ClangIncludeCleanerTests.dir/RecordTest.cpp.o tools/clang/tools/extra/include-cleaner/unittests/CMakeFiles/ClangIncludeCleanerTests.dir/WalkASTTest.cpp.o  -o tools/clang/tools/extra/include-cleaner/unittests/ClangIncludeCleanerTests  -Wl,-rpath,/home/buildbots/ppc64le-clang-multistage-test/clang-ppc64le-multistage/stage1/lib  -lpthread  lib/libllvm_gtest_main.so.16git  -lpthread  lib/libclangIncludeCleaner.so.16git  lib/libclangTesting.so.16git  lib/libLLVMTestingSupport.so.16git  lib/libclangToolingInclusionsStdlib.so.16git  lib/libllvm_gtest.so.16git  lib/libclangFrontend.so.16git  lib/libclangAST.so.16git  lib/libclangBasic.so.16git  lib/libLLVMSupport.so.16git  -Wl,-rpath-link,/home/buildbots/ppc64le-clang-multistage-test/clang-ppc64le-multistage/stage1/lib && :
/usr/bin/ld: tools/clang/tools/extra/include-cleaner/unittests/CMakeFiles/ClangIncludeCleanerTests.dir/RecordTest.cpp.o: undefined reference to symbol '_ZTVN5clang18PPChainedCallbacksE'
/home/buildbots/ppc64le-clang-multistage-test/clang-ppc64le-multistage/stage1/lib/libclangLex.so.16git: error adding symbols: DSO missing from command line
collect2: error: ld returned 1 exit status
[79/111] cd /home/buildbots/ppc64le-clang-multistage-test/clang-ppc64le-multistage/llvm/clang/bindings/python && /usr/local/bin/cmake -E env CLANG_LIBRARY_PATH=/home/buildbots/ppc64le-clang-multistage-test/clang-ppc64le-multistage/stage1/lib /usr/bin/python3.6 -m unittest discover
..............


cmake -G Ninja ../llvm-project/llvm -DCMAKE_BUILD_TYPE=Release -DLLVM_ENABLE_ASSERTIONS=True '-DLLVM_LIT_ARGS='"'"'-v'"'"'' -DCMAKE_INSTALL_PREFIX=../stage1.install -DLLVM_ENABLE_ASSERTIONS=ON -DLLVM_ENABLE_RUNTIMES=compiler-rt -DBUILD_SHARED_LIBS=ON -DLLVM_CCACHE_BUILD=ON '-DLLVM_ENABLE_PROJECTS=clang;clang-tools-extra;llvm'

...

[ilya-biryukov]

Sent out rG453c2879cb2ad6c46267ef8f39f0274aed69d9ee to fix this

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

 #include <variant>
 
 namespace clang {
 class SourceLocation;
 class Decl;
 class FileEntry;
 namespace include_cleaner {
 
 /// 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)>;
+/// FIXME: Provide signals about the providing headers so the caller can filter
+/// and rank the results.
+using UsedSymbolCB = llvm::function_ref<void(SymbolReference SymRef,
+                                             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:

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

 namespace include_cleaner {
 
 /// We consider a macro to be a different symbol each time it is defined.
 struct Macro {
   IdentifierInfo *Name;
   /// The location of the Name where the macro is defined.
   SourceLocation Definition;
 
-  bool operator==(const Macro &S) const {
-    return Definition == S.Definition;
-  }
+  bool operator==(const Macro &S) const { return Definition == S.Definition; }
 };
 
 /// An entity that can be referenced in the code.
 struct Symbol {
   enum Kind {
     /// A canonical clang declaration.
     Declaration,
     /// A preprocessor macro, as defined in a specific location.

 
 private:
   // FIXME: Add support for macros.
   // Order must match Kind enum!
   std::variant<const Decl *, struct Macro, tooling::stdlib::Symbol> Storage;
 };
 llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Symbol &);
 
+/// Indicates the relation between the reference and the target.
+enum class RefType {
+  /// Target is named by the reference, e.g. function call.
+  Explicit,
+  /// Target isn't spelled, e.g. default constructor call in `Foo f;`
+  Implicit,
+  /// Target's use can't be proven, e.g. a candidate for an unresolved overload.
+  Ambiguous,
+};
+
 /// Indicates that a piece of code refers to a symbol.
 struct SymbolReference {
-  /// The symbol referred to.
-  Symbol Symbol;
   /// The point in the code that refers to the symbol.
   SourceLocation RefLocation;
+  /// The symbol referred to.
+  Symbol Target;
+  /// Relation type between the reference location and the target.
+  RefType RT;
 };
 llvm::raw_ostream &operator<<(llvm::raw_ostream &, const SymbolReference &);
 
 /// Represents a file that provides some symbol. Might not be includeable, e.g.
 /// built-in or main-file itself.
 struct Header {
   enum Kind {
     /// A source file parsed by clang. (May also be a <built-in> buffer).
     Physical,
     /// A recognized standard library header, like <string>.
     Standard,
   };
 
   Header(const FileEntry *FE) : Storage(FE) {}
   Header(tooling::stdlib::Header H) : Storage(H) {}
 
   Kind kind() const { return static_cast<Kind>(Storage.index()); }
   bool operator==(const Header &RHS) const { return Storage == RHS.Storage; }
 
   const FileEntry *physical() const { return std::get<Physical>(Storage); }
   tooling::stdlib::Header standard() const {
     return std::get<Standard>(Storage);
   }
 
 private:
   // FIXME: Handle verbatim spellings.
   // Order must match Kind enum!
   std::variant<const FileEntry *, tooling::stdlib::Header> Storage;

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/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) {
   tooling::stdlib::Recognizer Recognizer;
   for (auto *Root : ASTRoots) {
     auto &SM = Root->getASTContext().getSourceManager();
-    walkAST(*Root, [&](SourceLocation Loc, NamedDecl &ND) {
+    walkAST(*Root, [&](SourceLocation Loc, NamedDecl &ND, RefType 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(Loc, Symbol(*SS), toHeader(SS->headers()));
+        return CB({Loc, Symbol(*SS), RT}, 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)});
+        return CB({Loc, Symbol(ND), RT}, {Header(FE)});
     });
   }
   // FIXME: Handle references of macros.
 }
 
 } // 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/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.
+/// - 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 &)>);
+void walkAST(Decl &Root,
+             llvm::function_ref<void(SourceLocation, NamedDecl &, RefType)>);
 
 /// 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/lib/HTMLReport.cpp

 //===--- HTMLReport.cpp - Explain the analysis for humans -----------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
 // If we're debugging this tool or trying to explain its conclusions, we need to
 // be able to identify specific facts about the code and the inferences made.
 //
 // This library prints an annotated version of the code
 //
 //===----------------------------------------------------------------------===//
 
 #include "AnalysisInternal.h"
+#include "clang-include-cleaner/Analysis.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/PrettyPrinter.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Lex/Lexer.h"
 #include "llvm/Support/raw_ostream.h"
 
 namespace clang::include_cleaner {

 };
 
 } // namespace
 
 void writeHTMLReport(FileID File, llvm::ArrayRef<Decl *> Roots, ASTContext &Ctx,
                      llvm::raw_ostream &OS) {
   Reporter R(OS, Ctx, File);
   for (Decl *Root : Roots)
-    walkAST(*Root,
-            [&](SourceLocation Loc, const NamedDecl &D) { R.addRef(Loc, D); });
+    walkAST(*Root, [&](SourceLocation Loc, const NamedDecl &D, RefType) {
+      R.addRef(Loc, D);
+    });
   R.write();
 }
 
 } // namespace clang::include_cleaner

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/SourceManager.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Lex/MacroInfo.h"
 #include "clang/Lex/PPCallbacks.h"
 #include "clang/Lex/Preprocessor.h"
if (const auto *MI = MD.getMacroInfo())
       recordMacroRef(MacroName, *MI);
   }
 
 private:
   void recordMacroRef(const Token &Tok, const MacroInfo &MI) {
     if (MI.isBuiltinMacro())
       return; // __FILE__ is not a reference.
     Recorded.MacroReferences.push_back(
-        SymbolReference{Macro{Tok.getIdentifierInfo(), MI.getDefinitionLoc()},
-                        Tok.getLocation()});
+        SymbolReference{Tok.getLocation(),
+                        Macro{Tok.getIdentifierInfo(), MI.getDefinitionLoc()},
+                        RefType::Explicit});
   }
 
   bool Active = false;
   RecordedPP &Recorded;
   const Preprocessor &PP;
   const SourceManager &SM;
 };
 
RecordedPP::RecordedIncludes::match(Header H) const {
   }
   return Result;
 }
 
 std::unique_ptr<PPCallbacks> RecordedPP::record(const Preprocessor &PP) {
   return std::make_unique<PPRecorder>(*this, PP);
 }
 
-
 } // namespace clang::include_cleaner

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

 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Include &I) {
   return OS << I.Line << ": " << I.Spelled << " => "
             << (I.Resolved ? I.Resolved->getName() : "<missing>");
 }
 
 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const SymbolReference &R) {
   // We can't decode the Location without SourceManager. Its raw representation
   // isn't completely useless (and distinguishes SymbolReference from Symbol).
-  return OS << R.Symbol << "@0x"
+  return OS << R.Target << "@0x"
             << llvm::utohexstr(R.RefLocation.getRawEncoding(),
                                /*Width=*/CHAR_BIT *
                                    sizeof(SourceLocation::UIntTy));
 }
 
 } // namespace clang::include_cleaner

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-include-cleaner/Analysis.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/Expr.h"
 #include "clang/AST/ExprCXX.h"
 #include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/AST/TemplateName.h"
 #include "clang/AST/Type.h"
 #include "clang/AST/TypeLoc.h"
 #include "clang/Basic/SourceLocation.h"
+#include "clang/Basic/SourceManager.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/Casting.h"
 
 namespace clang::include_cleaner {
 namespace {
-using DeclCallback = llvm::function_ref<void(SourceLocation, NamedDecl &)>;
+using DeclCallback =
+    llvm::function_ref<void(SourceLocation, NamedDecl &, RefType)>;
 
 class ASTWalker : public RecursiveASTVisitor<ASTWalker> {
   DeclCallback Callback;
+  // Whether we're traversing declarations coming from a header file.
+  // This helps figure out whether certain symbols can be assumed as unused
+  // (e.g. overloads brought into an implementation file, but not used).
+  bool IsHeader = false;
 
   bool handleTemplateName(SourceLocation Loc, TemplateName TN) {
     // For using-templates, only mark the alias.
     if (auto *USD = TN.getAsUsingShadowDecl()) {
       report(Loc, USD);
       return true;
     }
     report(Loc, TN.getAsTemplateDecl());
     return true;
   }
 
-  void report(SourceLocation Loc, NamedDecl *ND) {
+  void report(SourceLocation Loc, NamedDecl *ND,
+              RefType RT = RefType::Explicit) {
     if (!ND || Loc.isInvalid())
       return;
-    Callback(Loc, *cast<NamedDecl>(ND->getCanonicalDecl()));
+    Callback(Loc, *cast<NamedDecl>(ND->getCanonicalDecl()), RT);
   }
 
 public:
-  ASTWalker(DeclCallback Callback) : Callback(Callback) {}
+  ASTWalker(DeclCallback Callback, bool IsHeader)
+      : Callback(Callback), IsHeader(IsHeader) {}
 
   bool VisitDeclRefExpr(DeclRefExpr *DRE) {
     report(DRE->getLocation(), DRE->getFoundDecl());
     return true;
   }
 
   bool VisitMemberExpr(MemberExpr *E) {
     report(E->getMemberLoc(), E->getFoundDecl().getDecl());
     return true;
   }
 
   bool VisitCXXConstructExpr(CXXConstructExpr *E) {
-    report(E->getLocation(), E->getConstructor());
+    report(E->getLocation(), E->getConstructor(),
+           E->getParenOrBraceRange().isValid() ? RefType::Explicit
+                                               : RefType::Implicit);
     return true;
   }
 
   bool VisitOverloadExpr(OverloadExpr *E) {
     // Since we can't prove which overloads are used, report all of them.
-    // FIXME: Provide caller with the ability to make a decision for such uses.
-    llvm::for_each(E->decls(),
-                   [this, E](NamedDecl *D) { report(E->getNameLoc(), D); });
+    llvm::for_each(E->decls(), [this, E](NamedDecl *D) {
+      report(E->getNameLoc(), D, RefType::Ambiguous);
+    });
     return true;
   }
 
   bool VisitUsingDecl(UsingDecl *UD) {
-    // FIXME: Provide caller with the ability to tell apart used/non-used
-    // targets.
-    for (const auto *Shadow : UD->shadows())
-      report(UD->getLocation(), Shadow->getTargetDecl());
+    for (const auto *Shadow : UD->shadows()) {
+      auto *TD = Shadow->getTargetDecl();
+      auto IsUsed = TD->isUsed() || TD->isReferenced();
+      // We ignore unused overloads inside implementation files, as the ones in
+      // headers might still be used by the dependents of the header.
+      if (!IsUsed && !IsHeader)
+        continue;
+      report(UD->getLocation(), TD,
+             IsUsed ? RefType::Explicit : RefType::Ambiguous);
+    }
     return true;
   }
 
   bool VisitFunctionDecl(FunctionDecl *FD) {
     // Mark declaration from definition as it needs type-checking.
     if (FD->isThisDeclarationADefinition())
       report(FD->getLocation(), FD);
     return true;
if (Arg.getKind() == TemplateArgument::Template ||
                                 Arg.getAsTemplateOrTemplatePattern());
     return RecursiveASTVisitor::TraverseTemplateArgumentLoc(TL);
   }
 };
 
 } // namespace
 
 void walkAST(Decl &Root, DeclCallback Callback) {
-  ASTWalker(Callback).TraverseDecl(&Root);
+  auto &AST = Root.getASTContext();
+  auto &SM = AST.getSourceManager();
+  // If decl isn't written in main file, assume it's coming from an include,
+  // hence written in a header.
+  bool IsRootedAtHeader =
+      AST.getLangOpts().IsHeaderFile ||
+      !SM.isWrittenInMainFile(SM.getSpellingLoc(Root.getLocation()));
+  ASTWalker(Callback, IsRootedAtHeader).TraverseDecl(&Root);
 }
 
 } // namespace clang::include_cleaner

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

TEST(WalkUsed, Basic) {
 
   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);
+  walkUsed(TopLevelDecls,
+           [&](SymbolReference SymRef, llvm::ArrayRef<Header> Providers) {
+             auto [FID, Offset] = SM.getDecomposedLoc(SymRef.RefLocation);
              EXPECT_EQ(FID, SM.getMainFileID());
              OffsetToProviders.try_emplace(Offset, Providers.vec());
            });
   auto HeaderFile = Header(AST.fileManager().getFile("header.h").get());
   auto MainFile = Header(SM.getFileEntryForID(SM.getMainFileID()));
   auto VectorSTL = Header(tooling::stdlib::Header::named("<vector>").value());
   EXPECT_THAT(
       OffsetToProviders,
       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))));
 }
 
 } // namespace
 } // namespace clang::include_cleaner

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

TEST_F(RecordPPTest, CapturesMacroRefs) {
   Inputs.ExtraFiles["header.h"] = Header.code();
   auto AST = build();
   const auto &SM = AST.sourceManager();
 
   SourceLocation Def = SM.getComposedLoc(
       SM.translateFile(AST.fileManager().getFile("header.h").get()),
       Header.point("def"));
   ASSERT_THAT(Recorded.MacroReferences, Not(IsEmpty()));
-  Symbol OrigX = Recorded.MacroReferences.front().Symbol;
+  Symbol OrigX = Recorded.MacroReferences.front().Target;
   EXPECT_EQ("X", OrigX.macro().Name->getName());
   EXPECT_EQ(Def, OrigX.macro().Definition);
 
   std::vector<unsigned> RefOffsets;
   std::vector<unsigned> ExpOffsets; // Expansion locs of refs in macro locs.
   std::vector<SourceLocation> RefMacroLocs;
   for (const auto &Ref : Recorded.MacroReferences) {
-    if (Ref.Symbol == OrigX) {
+    if (Ref.Target == OrigX) {
       auto [FID, Off] = SM.getDecomposedLoc(Ref.RefLocation);
       if (FID == SM.getMainFileID()) {
         RefOffsets.push_back(Off);
       } else if (Ref.RefLocation.isMacroID() &&
                  SM.isWrittenInMainFile(SM.getExpansionLoc(Ref.RefLocation))) {
         ExpOffsets.push_back(
             SM.getDecomposedExpansionLoc(Ref.RefLocation).second);
       } else {

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/ADT/StringRef.h"
 #include "llvm/Support/Error.h"
+#include "llvm/Support/ErrorHandling.h"
 #include "llvm/Testing/Support/Annotations.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include <cstddef>
+#include <unordered_map>
+#include <utility>
 #include <vector>
 
 namespace clang::include_cleaner {
 namespace {
 using testing::Pair;
 using testing::UnorderedElementsAre;
 
+llvm::StringLiteral to_string(RefType RT) {
+  switch (RT) {
+  case RefType::Explicit:
+    return "explicit";
+  case RefType::Implicit:
+    return "implicit";
+  case RefType::Ambiguous:
+    return "ambiguous";
+  }
+  llvm_unreachable("Unexpected RefType");
+}
+
 // Specifies a test of which symbols are referenced by a piece of code.
-//
+// If `// c++-header` is present, treats referencing code as a header file.
+// Target should contain points annotated with the reference kind.
 // Example:
-//   Target:      int ^foo();
+//   Target:      int $explicit^foo();
 //   Referencing: int x = ^foo();
 // There must be exactly one referencing location marked.
 void testWalk(llvm::StringRef TargetCode, llvm::StringRef ReferencingCode) {
   llvm::Annotations Target(TargetCode);
   llvm::Annotations Referencing(ReferencingCode);
 
   TestInputs Inputs(Referencing.code());
   Inputs.ExtraFiles["target.h"] = Target.code().str();
   Inputs.ExtraArgs.push_back("-include");
   Inputs.ExtraArgs.push_back("target.h");
   Inputs.ExtraArgs.push_back("-std=c++17");
+  if (Referencing.code().contains("// c++-header\n"))
+    Inputs.ExtraArgs.push_back("-xc++-header");
   TestAST AST(Inputs);
   const auto &SM = AST.sourceManager();
 
   // We're only going to record references from the nominated point,
   // to the target file.
   FileID ReferencingFile = SM.getMainFileID();
   SourceLocation ReferencingLoc =
       SM.getComposedLoc(ReferencingFile, Referencing.point());
   FileID TargetFile = SM.translateFile(
       llvm::cantFail(AST.fileManager().getFileRef("target.h")));
 
   // Perform the walk, and capture the offsets of the referenced targets.
-  std::vector<size_t> ReferencedOffsets;
+  std::unordered_map<RefType, std::vector<size_t>> ReferencedOffsets;
   for (Decl *D : AST.context().getTranslationUnitDecl()->decls()) {
     if (ReferencingFile != SM.getDecomposedExpansionLoc(D->getLocation()).first)
       continue;
-    walkAST(*D, [&](SourceLocation Loc, NamedDecl &ND) {
+    walkAST(*D, [&](SourceLocation Loc, NamedDecl &ND, RefType RT) {
       if (SM.getFileLoc(Loc) != ReferencingLoc)
         return;
       auto NDLoc = SM.getDecomposedLoc(SM.getFileLoc(ND.getLocation()));
       if (NDLoc.first != TargetFile)
         return;
-      ReferencedOffsets.push_back(NDLoc.second);
+      ReferencedOffsets[RT].push_back(NDLoc.second);
     });
   }
-  llvm::sort(ReferencedOffsets);
+  for (auto &Entry : ReferencedOffsets)
+    llvm::sort(Entry.second);
 
   // Compare results to the expected points.
   // For each difference, show the target point in context, like a diagnostic.
   std::string DiagBuf;
   llvm::raw_string_ostream DiagOS(DiagBuf);
   auto *DiagOpts = new DiagnosticOptions();
   DiagOpts->ShowLevel = 0;
   DiagOpts->ShowNoteIncludeStack = 0;
   TextDiagnostic Diag(DiagOS, AST.context().getLangOpts(), DiagOpts);
-  auto DiagnosePoint = [&](const char *Message, unsigned Offset) {
+  auto DiagnosePoint = [&](llvm::StringRef Message, unsigned Offset) {
     Diag.emitDiagnostic(
         FullSourceLoc(SM.getComposedLoc(TargetFile, Offset), SM),
         DiagnosticsEngine::Note, Message, {}, {});
   };
-  for (auto Expected : Target.points())
-    if (!llvm::is_contained(ReferencedOffsets, Expected))
-      DiagnosePoint("location not marked used", Expected);
-  for (auto Actual : ReferencedOffsets)
-    if (!llvm::is_contained(Target.points(), Actual))
-      DiagnosePoint("location unexpectedly used", Actual);
+  for (auto RT : {RefType::Explicit, RefType::Implicit, RefType::Ambiguous}) {
+    auto RTStr = to_string(RT);
+    for (auto Expected : Target.points(RTStr))
+      if (!llvm::is_contained(ReferencedOffsets[RT], Expected))
+        DiagnosePoint(("location not marked used with type " + RTStr).str(),
+                      Expected);
+    for (auto Actual : ReferencedOffsets[RT])
+      if (!llvm::is_contained(Target.points(RTStr), Actual))
+        DiagnosePoint(("location unexpectedly used with type " + RTStr).str(),
+                      Actual);
+  }
 
   // If there were any differences, we print the entire referencing code once.
   if (!DiagBuf.empty())
     ADD_FAILURE() << DiagBuf << "\nfrom code:\n" << ReferencingCode;
 }
 
 TEST(WalkAST, DeclRef) {
-  testWalk("int ^x;", "int y = ^x;");
-  testWalk("int ^foo();", "int y = ^foo();");
-  testWalk("namespace ns { int ^x; }", "int y = ns::^x;");
-  testWalk("struct S { static int ^x; };", "int y = S::^x;");
+  testWalk("int $explicit^x;", "int y = ^x;");
+  testWalk("int $explicit^foo();", "int y = ^foo();");
+  testWalk("namespace ns { int $explicit^x; }", "int y = ns::^x;");
+  testWalk("struct S { static int $explicit^x; };", "int y = S::^x;");
   // Canonical declaration only.
-  testWalk("extern int ^x; int x;", "int y = ^x;");
+  testWalk("extern int $explicit^x; int x;", "int y = ^x;");
   // Return type of `foo` isn't used.
-  testWalk("struct S{}; S ^foo();", "auto bar() { return ^foo(); }");
+  testWalk("struct S{}; S $explicit^foo();", "auto bar() { return ^foo(); }");
 }
 
 TEST(WalkAST, TagType) {
-  testWalk("struct ^S {};", "^S *y;");
-  testWalk("enum ^E {};", "^E *y;");
-  testWalk("struct ^S { static int x; };", "int y = ^S::x;");
+  testWalk("struct $explicit^S {};", "^S *y;");
+  testWalk("enum $explicit^E {};", "^E *y;");
+  testWalk("struct $explicit^S { static int x; };", "int y = ^S::x;");
 }
 
 TEST(WalkAST, Alias) {
   testWalk(R"cpp(
     namespace ns { int x; }
-    using ns::^x;
+    using ns::$explicit^x;
   )cpp",
            "int y = ^x;");
-  testWalk("using ^foo = int;", "^foo x;");
-  testWalk("struct S {}; using ^foo = S;", "^foo x;");
+  testWalk("using $explicit^foo = int;", "^foo x;");
+  testWalk("struct S {}; using $explicit^foo = S;", "^foo x;");
 }
 
 TEST(WalkAST, Using) {
-  testWalk("namespace ns { void ^x(); void ^x(int); }", "using ns::^x;");
-  testWalk("namespace ns { struct S; } using ns::^S;", "^S *s;");
+  // Make sure we ignore unused overloads.
+  testWalk(R"cpp(
+    namespace ns {
+      void $explicit^x(); void x(int); void x(char);
+    })cpp",
+           "using ns::^x; void foo() { x(); }");
+  // We should report unused overloads if main file is a header.
+  testWalk(R"cpp(
+    namespace ns {
+      void $ambiguous^x(); void $ambiguous^x(int); void $ambiguous^x(char);
+    })cpp",
+           "// c++-header\n using ns::^x;");
+  testWalk("namespace ns { struct S; } using ns::$explicit^S;", "^S *s;");
 }
 
 TEST(WalkAST, Namespaces) {
   testWalk("namespace ns { void x(); }", "using namespace ^ns;");
 }
 
 TEST(WalkAST, TemplateNames) {
-  testWalk("template<typename> struct ^S {};", "^S<int> s;");
+  testWalk("template<typename> struct $explicit^S {};", "^S<int> s;");
   // FIXME: Template decl has the wrong primary location for type-alias template
   // decls.
   testWalk(R"cpp(
       template <typename> struct S {};
-      template <typename T> ^using foo = S<T>;)cpp",
+      template <typename T> $explicit^using foo = S<T>;)cpp",
            "^foo<int> x;");
   testWalk(R"cpp(
       namespace ns {template <typename> struct S {}; }
-      using ns::^S;)cpp",
+      using ns::$explicit^S;)cpp",
            "^S<int> x;");
-  testWalk("template<typename> struct ^S {};",
+  testWalk("template<typename> struct $explicit^S {};",
            R"cpp(
       template <template <typename> typename> struct X {};
       X<^S> x;)cpp");
-  testWalk("template<typename T> struct ^S { S(T); };", "^S s(42);");
+  testWalk("template<typename T> struct $explicit^S { S(T); };", "^S s(42);");
   // Should we mark the specialization instead?
-  testWalk("template<typename> struct ^S {}; template <> struct S<int> {};",
-           "^S<int> s;");
+  testWalk(
+      "template<typename> struct $explicit^S {}; template <> struct S<int> {};",
 }
 
 TEST(WalkAST, MemberExprs) {
-  testWalk("struct S { void ^foo(); };", "void foo() { S{}.^foo(); }");
-  testWalk("struct S { void foo(); }; struct X : S { using S::^foo; };",
-           "void foo() { X{}.^foo(); }");
+  testWalk("struct S { void $explicit^foo(); };", "void foo() { S{}.^foo(); }");
+  testWalk(
+      "struct S { void foo(); }; struct X : S { using S::$explicit^foo; };",
 }
 
 TEST(WalkAST, ConstructExprs) {
-  testWalk("struct ^S {};", "S ^t;");
-  testWalk("struct S { ^S(int); };", "S ^t(42);");
+  testWalk("struct $implicit^S {};", "S ^t;");
+  testWalk("struct S { $implicit^S(); };", "S ^t;");
+  testWalk("struct S { $explicit^S(int); };", "S ^t(42);");
+  testWalk("struct S { $implicit^S(int); };", "S t = ^42;");
 }
 
 TEST(WalkAST, Functions) {
   // Definition uses declaration, not the other way around.
-  testWalk("void ^foo();", "void ^foo() {}");
+  testWalk("void $explicit^foo();", "void ^foo() {}");
   testWalk("void foo() {}", "void ^foo();");
 
   // Unresolved calls marks all the overloads.
-  testWalk("void ^foo(int); void ^foo(char);",
+  testWalk("void $ambiguous^foo(int); void $ambiguous^foo(char);",
            "template <typename T> void bar() { ^foo(T{}); }");
 }
 
 TEST(WalkAST, Enums) {
-  testWalk("enum E { ^A = 42, B = 43 };", "int e = ^A;");
-  testWalk("enum class ^E : int;", "enum class ^E : int {};");
+  testWalk("enum E { $explicit^A = 42, B = 43 };", "int e = ^A;");
+  testWalk("enum class $explicit^E : int;", "enum class ^E : int {};");
   testWalk("enum class E : int {};", "enum class ^E : int ;");
 }
 
 } // namespace
 } // namespace clang::include_cleaner