[include-cleaner] Ranking of providers based on hints

[kadircet]

Summary

Introduce signals to rank providers of a symbol.

[hokein]

I haven't read all code yet, left a few initial comments.

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

62

IIUC, we're using a union bit for symbols and headers: some properties are for both (e.g. Complete); some properties are just for headers (e.g. Public, Canonical).

I found that this model is hard to follow (e.g. for each property, I need to keep thinking about whether this property is for just symbols/headers or both, the hint conversion step from Symbol to Header is not obvious).

What do you think about the following alternative ?

• define two hints (SymbolHint, HeaderHint)
• an explicit conversion from SymbolHint to HeaderHint
• SymbolLocation class has a SymbolHint member (for Header as well)

66

nit: since this is a bit union, I'd suggest to use = 1 << 0, = 1 << 1 syntax to define the value.

67

I think this is no non-private declaration. The Public property is for headers, it indicates the symbol is provided by a non-private header.

70

In most cases, this bit is set. If we use a flipped bit (Private), we don't need to set it in many places.

72

This comment is hard to follow, it doesn't explain the Canonical. From the design doc, it means NameMatch and Annotated headers, I think it would be nice to document them in the comment.

I'd suggest avoid using the Canonical name, it remains me too much about the canonical decl in clang. Maybe Preferred?

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

1

any reason to change the file property?

109

I think Exporter is the case we need to handle -- the exporter header should have a higher value (we probably need to add another hint bit).

112

if FE is private, do we want the Verbatim set the public bit? My inclination is yes (the current code behavior is no), it feels counterintuitive that headers from getPublic() is not marked as Public.

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

22–40

nit: declHints?

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

179

I think we should have some tests for the hints bit (verify the hint bits are set correctly).

284

The result is correct according to the (canonical, public, complete) triple order.

But we can come up with a counterexample, e.g.

// transitive.h
#include "public_complete.h"

// main.cpp
#include "transitive.h"
Foo foo;

We will remove the transitive.h and insert the foo.proto.h, then we cause a compiling error (incomplete type of Foo). Not sure what we should do about it.

[sammccall]

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

61

along with SymbolLocation, I think mixing our fundamental types and analysis functions in this header makes the structure harder to understand and think they both belong in Types.h

62

I agree the model isn't obvious, but I think it is the right one and should be explained.
Breaking into a bunch of different types would be a mistake IMO. It would make it look less like algebra and more like domain logic. The problem is the algebra is important, e.g. it tells you how to merge hints to rank providers.

I think the model is:

• we have a "provides" DAG, headers provide locations which provide symbols which satisfy AST nodes
• these hints are "capabilities" that can be provided by edges (or subpaths).
• if any path from Header => AST Node sees a capability, the header provides that capability.
• this explains why most hints are expressed positively, and we take the union. (if a header provides a complete definition and an incomplete one, we want to call that "complete")

64

As discussed elsewhere, we could define this as "provides a generally-usable definition for a symbol", i.e. clear it for template/class forward-decls and set it for everything else. This isn't really more code, and makes it less likely we're going to subtly misinterpret the value.

67

I agree with this one: because hints aggregate as union, it would be a mistake to flag a Symbol as Public - that would mean any header that provided it would end up with the Public hint, even if the header file is private!

I wonder if we should use a naming-convention for this, e.g. CompleteSymbol, PublicHeader etc, indicating the layer at which the signal is expected to be set.

72

+1 to Preferred and also documenting the conditions when a signal is set here in some detail (also for Public and Complete).

I think we really have to understand what the signal is quite precisely to make correct use of it.

74–75

missed this in the previous review: both locateSymbol and headersForSymbol should probably be above writeHTMLReport

76

tarversing -> traversing
sorted per -> sorted by

(uber-nit: i.e. should be e.g. or simply deleted, as "top element first" is not equivalent to "list is sorted")

80

std::forward should just be std::move here, T is not a reference type

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

44

I would suggest making this function public (or operator< on Hinted<Header>) and unit-testing it to demonstrate the intended behavior.

The implementation is trivial now but may not always be, and editing enum constants at the end rather than in the correct position seems like an easy mistake to make.

53

doing string rendering in a comparator seems gratuitously wasteful.

call stable_sort instead? the input order was used prior to this patch and seems OK.
(or define a meaningful operator< on Header and call that, but it need not be done now)

62

again, this seems unneccesary - switch over the variants instead?

103

why never canonical?

In general, handling !PI as a special case up front seems like a bad idea: the purpose of supporting it being nullable is to allow the code below to used/tested without one. Seems we can get away with guarding PI-bits with if (PI) below.
(Avoiding the ternary initializer for CurrentHints would be a readability side-benefit!)

109

I think we discussed and thought that was a bit unsafe. export can simply mean "downstream code can assumes this symbol is available", not "i'm the real owner of these symbols".

Prominent example: https://github.com/protocolbuffers/protobuf/blob/14e579436fb53d0e8271c4d26d3d88c394d96454/src/google/protobuf/stubs/port.h#L90
(it's not relevant that the exported header in question is a standardish one)

112

+1, conceptually this is a reference to a sibling edge in the DAG, not an edge chaining off this one, so it should not inherit hints

183

why not define operator< on Header if you need one? this will come up again.

188

not sure if this is really a FIXME: it's a pretty deep consequence of the design that will never be fixed.

Since you're relying on the distinction between "header" and "Header" here, maybe be a bit more explicit? "If two Headers probably refer to the same file (e.g. Verbatim(foo.h) and Physical(/path/to/foo.h), we won't deduplicate them or merge their hints".

209

again, no need to stringify and then reparse here (in fact operator<< for Symbol is extra-inefficient, assuming that we never call it in algorithms), we have a perfectly good underlying string that's pretty easy to get at in the cases where matching is appropriate

213

BTW This stringify-and-parse isn't quite correct, e.g. for operator std::string it yields operator string but for operator typename T::foo() it yields foo!

(I realize we do this in clangd, which isn't great...)

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

179

these tests seem to be in the wrong file

179

yes, I think this will be easier to maintain & make complete if you test the hints extracted, test the sort order, and only smoke-test the interaction between the two

281

This is confusing, the most obvious interpretation is "this is the generated header for the .proto file that defines foo", but such a header would have a complete definition.

I can't think of a remotely realistic proto example that actually triggers this case, so maybe drop the references to proto? It seems to give some false intuitions about whether this behavior is correct.

284

yeah, this is one of the tradeoffs of not examining completeness requirements at use sites.

However it's also a reason to believe that operator< on Hints may not be a simple lexicographic compare, several "lesser" hints may be able to overpower a "greater" one ==> another reason to make the comparison public & test it.

298

This comment describes an implementation (IMO is unlikely to be the right one) to solve a problem (which is left implicit) - it would be nice to state the problem instead.

I think we should have some special handling for the main-file, but it's not clear that boosting it is the way to go.

For example, if the main-file provides a forward-decl for a class, we probably shouldn't consider any other decl of that class used. (The forward decl clearly signals that it doesn't intend to rely on some external decl). So maybe headersForSymbol should only return the main file, or return some sentinel "provided in main file" value instead of a list.

[kadircet]

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

61

i still don't feel great about exposing these types as public API. would it help if I moved these into a TypesInternal.h ?

62

Yes, as discussed offline and Sam mentions in the comment idea is to have all hints expressed positively and take union of all the capabilities on the path from an AST node to a provider (also union in case there are multiple paths ending at the same provider). Each hint is to be provided by at most a single stage of the traversal (not sure why you think Complete is for both), I'll make this more concrete by renaming hint types to encode that in the name. I'll also add some docs explaining the model.

67

i agree with renaming these to indicate the stage that produced them.

70

as discussed, these need to be positively expressed (like others).

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

103

in the absence of PI, we can't really do much in the loop below (as we would assume each file is self-contained by default) and would bail out in the first run. Hence i don't see much difference between handling it here vs right after the calculation of CurrentHints down below (I am slightly inclined towards this version as it prevents thinking about both cases in the loop for no reason). I can move it into the body if you feel strongly about it though.

regarding canonicalness, right now it's inferred either by namematch (which is calculated in headersForSymbol) or via IWYU pragmas, which isn't available in absence of PI.

109

agreed, exports shouldn't really be boosted.

112

oops you're right. this was an oversight. same applies to exporters.

213

i think using the identifier name should be fine here, operators will be unnamed and won't get any name match.

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

179

these tests seem to be in the wrong file

I've chosen this one as the implementation lives in FindHeaders.cpp, do you think it belongs to AnalysisTests instead?

284

in addition to what Sam said, note that we'll preserve public_complete.h if it's already included directly.

[kadircet]

• Address all comments but the ones on tests.

[sammccall]

LG, just nits really!

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

137

this is a bit confusing... kind of the opposite of what std::in_place means?
(All of the other constructors build the state in-place in some sense, but this one doesn't)

Maybe just a private struct Sentinel{}; instead of in_place_t?

Symbol does this without any sentinel at all, if that's causing ambiguity then it might be worth fixing both to be the same.

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

61

AnalysisInternal < TypesInternal < Types I think, so yes

(I think separating the concepts/data structures from the algorithm/implementation is the important concern here. I don't think defensively minimizing surface area is important as the library simply won't have many users, and that exposing these is a net win because it makes the structure of the system easier for human readers to understand. Anyway, up to you)

63

nit: touched => traversed? Since you haven't explicitly mentioned a graph here (which is fine), hint at it more specifically

68

"positive" makes intuitive sense, but not *quite* the right concept. (existential vs universal quantification)

Maybe just give an example:

We choose the boolean sense accordingly, e.g. "Public" rather than "Private",
because a header is good if it provides any public definition, even if it also provides private ones.

71

nit: maybe Hints over Hint to indicate it's a bitset

72

nit: the conditions seem well-documented now, but I think we should drop the e.g. these should be the actual definitions, not just examples.

87

nit: augment values with hints? (or "augment types with Hint", but I think values is clearer)

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

37

just stable_sort(reverse(Headers))?

(reverse() returns an rbegin/rend view which should DTRT)

45

this signature seems unneccesarily complicated/hard to understand

what about nameMatch(DeclName, Header) -> Hint (or ->bool) and write the trivial loop in the caller?

59

debug stuff, and below

60

even though it's a few lines, if you pull out StringRef basename(StringRef Header) this code looks a lot clearer (and if returning bool, directly return basename(H.physical()->getName()).equals_insensitive(DeclName) etc inline above)

127–134

headers() returns the alternatives in preferred order, so you only want to set PreferredHeader on the first.

146

Somewhere say what you're doing: deduplicating headers and merging their hints

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

115

I think comparing pointers is going to give inconsistent results, and would suggest comparing Name (without trying to normalize, just for at least reproducibility across identical runs)

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

179

Nope, I think I was just confused, sorry

274

I don't think it does, it looks like you're sorting by the FileEntry pointers - this may happen to be discovery order a lot of the time but it's of course not guaranteed.

[kadircet]

• Address comments & rebase

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

137

without a disambiguation tag we get an ambigious conversion when we have a constructor call that looks like Header("foo.h") (whether to use Header(StringRef) or Header(variant<StringRef>), not sure if it's fine for an "inaccessible" constructor to participate in overload resolution, nor how variant can be viable here despite needing a double implicit conversion from stringref to variant)

This didn't bite us with Symbol yet because constructor takes a Decl& but variant stores a Decl*, and for Macro case we always explicitly initialized with spelling of Macro.

You're right about usage of inplace_t though, I was confused. using a sentinel tag instead.

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

115

i was rather worried about correctness of a name based match, e.g. we can have the same FileEntry pointers for foo.h and bar/foo.h but i guess it's OK to assume that a FileManager won't be accessed in the middle of a comparison sequence.

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

 
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Tooling/Inclusions/StandardLibrary.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringMap.h"
 #include <memory>
+#include <utility>
 #include <vector>
 
 namespace llvm {
 class raw_ostream;
 } // namespace llvm
 namespace clang {
 class Decl;
 class FileEntry;
struct Symbol {
 
   const Decl &declaration() const { return *std::get<Declaration>(Storage); }
   struct Macro macro() const { return std::get<Macro>(Storage); }
 
 private:
   // Order must match Kind enum!
   std::variant<const Decl *, struct Macro> Storage;
 
-  Symbol(decltype(Storage) Sentinel) : Storage(std::move(Sentinel)) {}
+  // Disambiguation tag to make sure we can call the right constructor from
+  // DenseMapInfo methods.
+  struct SentinelTag {};
+  Symbol(SentinelTag, decltype(Storage) Sentinel)
+      : Storage(std::move(Sentinel)) {}
   friend llvm::DenseMapInfo<Symbol>;
 };
 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,
struct Header {
   };
 
   Header(const FileEntry *FE) : Storage(FE) {}
   Header(tooling::stdlib::Header H) : Storage(H) {}
   Header(StringRef VerbatimSpelling) : Storage(VerbatimSpelling) {}
 
   Kind kind() const { return static_cast<Kind>(Storage.index()); }
   bool operator==(const Header &RHS) const { return Storage == RHS.Storage; }
+  bool operator<(const Header &RHS) const;
 
   const FileEntry *physical() const { return std::get<Physical>(Storage); }
   tooling::stdlib::Header standard() const {
     return std::get<Standard>(Storage);
   }
   StringRef verbatim() const { return std::get<Verbatim>(Storage); }
 
 private:
   // Order must match Kind enum!
   std::variant<const FileEntry *, tooling::stdlib::Header, StringRef> Storage;
+
+  // Disambiguation tag to make sure we can call the right constructor from
+  // DenseMapInfo methods.
+  struct SentinelTag {};
+  Header(SentinelTag, decltype(Storage) Sentinel)
+      : Storage(std::move(Sentinel)) {}
+  friend llvm::DenseMapInfo<Header>;
 };
 llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Header &);
 
 /// A single #include directive written in the main file.
 struct Include {
   llvm::StringRef Spelled;             // e.g. vector
   const FileEntry *Resolved = nullptr; // e.g. /path/to/c++/v1/vector
                                        // nullptr if the header was not found

 } // namespace clang
 
 namespace llvm {
 
 template <> struct DenseMapInfo<clang::include_cleaner::Symbol> {
   using Outer = clang::include_cleaner::Symbol;
   using Base = DenseMapInfo<decltype(Outer::Storage)>;
 
-  static inline Outer getEmptyKey() { return {Base::getEmptyKey()}; }
-  static inline Outer getTombstoneKey() { return {Base::getTombstoneKey()}; }
+  static inline Outer getEmptyKey() {
+    return {Outer::SentinelTag{}, Base::getEmptyKey()};
+  }
+  static inline Outer getTombstoneKey() {
+    return {Outer::SentinelTag{}, Base::getTombstoneKey()};
+  }
   static unsigned getHashValue(const Outer &Val) {
     return Base::getHashValue(Val.Storage);
   }
   static bool isEqual(const Outer &LHS, const Outer &RHS) {
     return Base::isEqual(LHS.Storage, RHS.Storage);
   }
 };
 template <> struct DenseMapInfo<clang::include_cleaner::Macro> {
   using Outer = clang::include_cleaner::Macro;
   using Base = DenseMapInfo<decltype(Outer::Definition)>;
 
   static inline Outer getEmptyKey() { return {nullptr, Base::getEmptyKey()}; }
   static inline Outer getTombstoneKey() {
     return {nullptr, Base::getTombstoneKey()};
   }
   static unsigned getHashValue(const Outer &Val) {
     return Base::getHashValue(Val.Definition);
   }
   static bool isEqual(const Outer &LHS, const Outer &RHS) {
     return Base::isEqual(LHS.Definition, RHS.Definition);
   }
 };
+template <> struct DenseMapInfo<clang::include_cleaner::Header> {
+  using Outer = clang::include_cleaner::Header;
+  using Base = DenseMapInfo<decltype(Outer::Storage)>;
+
+  static inline Outer getEmptyKey() {
+    return {Outer::SentinelTag{}, Base::getEmptyKey()};
+  }
+  static inline Outer getTombstoneKey() {
+    return {Outer::SentinelTag{}, Base::getTombstoneKey()};
+  }
+  static unsigned getHashValue(const Outer &Val) {
+    return Base::getHashValue(Val.Storage);
+  }
+  static bool isEqual(const Outer &LHS, const Outer &RHS) {
+    return Base::isEqual(LHS.Storage, RHS.Storage);
+  }
+};
 } // namespace llvm
 
 #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-include-cleaner/Record.h"
 #include "clang-include-cleaner/Types.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/Decl.h"
+#include "clang/AST/DeclBase.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Format/Format.h"
 #include "clang/Lex/HeaderSearch.h"
 #include "clang/Tooling/Core/Replacement.h"
-#include "clang/Tooling/Inclusions/HeaderIncludes.h"
 #include "clang/Tooling/Inclusions/StandardLibrary.h"
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/StringRef.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))
-    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.
   tooling::stdlib::Recognizer Recognizer;
   for (auto *Root : ASTRoots) {
     walkAST(*Root, [&](SourceLocation Loc, NamedDecl &ND, RefType RT) {
       if (!SM.isWrittenInMainFile(SM.getSpellingLoc(Loc)))
         return;
       // FIXME: Most of the work done here is repetative. It might be useful to
       // have a cache/batching.
       SymbolReference SymRef{Loc, ND, RT};
       return CB(SymRef, headersForSymbol(ND, SM, PI));
     });
   }
   for (const SymbolReference &MacroRef : MacroRefs) {
     assert(MacroRef.Target.kind() == Symbol::Macro);
     if (!SM.isWrittenInMainFile(SM.getSpellingLoc(MacroRef.RefLocation)))
       continue;
-    CB(MacroRef, findHeaders(MacroRef.Target.macro().Definition, SM, PI));
+    CB(MacroRef, headersForSymbol(MacroRef.Target, SM, PI));
   }
 }
 
 static std::string spellHeader(const Header &H, HeaderSearch &HS,
                                const FileEntry *Main) {
   switch (H.kind()) {
   case Header::Physical: {
     bool IsSystem = false;

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 "TypesInternal.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;
+class SourceLocation;
 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,
+llvm::SmallVector<Hinted<Header>> findHeaders(const SymbolLocation &Loc,
+                                              const SourceManager &SM,
+                                              const PragmaIncludes *PI);
+
+/// A set of locations that provides the declaration.
+std::vector<Hinted<SymbolLocation>> locateSymbol(const Symbol &S);
+
+/// Gets all the providers for a symbol by traversing each location.
+/// Returned headers are sorted by relevance, first element is the most
+/// likely provider for the symbol.
+llvm::SmallVector<Header> headersForSymbol(const Symbol &S,
                                            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/FindHeaders.cpp

 //===--- FindHeaders.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 "AnalysisInternal.h"
+#include "TypesInternal.h"
 #include "clang-include-cleaner/Record.h"
+#include "clang-include-cleaner/Types.h"
+#include "clang/AST/Decl.h"
+#include "clang/AST/DeclBase.h"
+#include "clang/Basic/FileEntry.h"
+#include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
+#include "clang/Tooling/Inclusions/StandardLibrary.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/ErrorHandling.h"
+#include <string>
+#include <utility>
 
 namespace clang::include_cleaner {
+namespace {
+llvm::SmallVector<Hinted<Header>>
+applyHints(llvm::SmallVector<Hinted<Header>> Headers, Hints H) {
+  for (auto &Header : Headers)
+    Header.Hint |= H;
+  return Headers;
+}
+
+llvm::SmallVector<Header> ranked(llvm::SmallVector<Hinted<Header>> Headers) {
+  llvm::stable_sort(llvm::reverse(Headers),
+                    [](const Hinted<Header> &LHS, const Hinted<Header> &RHS) {
+                      return LHS < RHS;
+                    });
+  return llvm::SmallVector<Header>(Headers.begin(), Headers.end());
+}
+
+// Return the basename from a verbatim header spelling, leaves only the file
+// name.
+llvm::StringRef basename(llvm::StringRef Header) {
+  Header = Header.trim("<>\"");
+  if (auto LastSlash = Header.rfind('/'); LastSlash != Header.npos)
+    Header = Header.drop_front(LastSlash + 1);
+  // Drop everything after first `.` (dot).
+  // foo.h -> foo
+  // foo.cu.h -> foo
+  Header = Header.substr(0, Header.find('.'));
+  return Header;
+}
+
+// Check if spelling of \p H matches \p DeclName.
+bool nameMatch(llvm::StringRef DeclName, Header H) {
+  switch (H.kind()) {
+  case Header::Physical:
+    return basename(H.physical()->getName()).equals_insensitive(DeclName);
+  case Header::Standard:
+    return basename(H.standard().name()).equals_insensitive(DeclName);
+  case Header::Verbatim:
+    return basename(H.verbatim()).equals_insensitive(DeclName);
+  }
+  llvm_unreachable("unhandled Header kind!");
+}
+
+llvm::StringRef symbolName(const Symbol &S) {
+  switch (S.kind()) {
+  case Symbol::Declaration:
+    // Unnamed decls like operators and anonymous structs won't get any name
+    // match.
+    if (const auto *ND = llvm::dyn_cast<NamedDecl>(&S.declaration()))
+      if (auto *II = ND->getIdentifier())
+        return II->getName();
+    return "";
+  case Symbol::Macro:
+    return S.macro().Name->getName();
+  }
+  llvm_unreachable("unhandled Symbol kind!");
+}
+
+} // namespace
 
-llvm::SmallVector<Header> findHeaders(const SymbolLocation &Loc,
+llvm::SmallVector<Hinted<Header>> findHeaders(const SymbolLocation &Loc,
                                               const SourceManager &SM,
                                               const PragmaIncludes *PI) {
-  llvm::SmallVector<Header> Results;
+  auto IsPublicHeader = [&PI](const FileEntry *FE) {
+    return (PI->isPrivate(FE) || !PI->isSelfContained(FE))
+               ? Hints::None
+               : Hints::PublicHeader;
+  };
+  llvm::SmallVector<Hinted<Header>> Results;
   switch (Loc.kind()) {
   case SymbolLocation::Physical: {
     FileID FID = SM.getFileID(SM.getExpansionLoc(Loc.physical()));
     const FileEntry *FE = SM.getFileEntryForID(FID);
-    if (!PI) {
-      return FE ? llvm::SmallVector<Header>{Header(FE)}
-                : llvm::SmallVector<Header>();
-    }
+    if (!FE)
+      return {};
+    if (!PI)
+      return {{FE, Hints::PublicHeader}};
     while (FE) {
-      Results.push_back(Header(FE));
+      Hints CurrentHints = IsPublicHeader(FE);
+      Results.emplace_back(FE, CurrentHints);
       // FIXME: compute transitive exporter headers.
       for (const auto *Export : PI->getExporters(FE, SM.getFileManager()))
-        Results.push_back(Header(Export));
+        Results.emplace_back(Export, IsPublicHeader(Export));
 
-      llvm::StringRef VerbatimSpelling = PI->getPublic(FE);
-      if (!VerbatimSpelling.empty()) {
-        Results.push_back(VerbatimSpelling);
+      if (auto Verbatim = PI->getPublic(FE); !Verbatim.empty()) {
+        Results.emplace_back(Verbatim,
+                             Hints::PublicHeader | Hints::PreferredHeader);
         break;
       }
       if (PI->isSelfContained(FE) || FID == SM.getMainFileID())
         break;
 
       // Walkup the include stack for non self-contained headers.
       FID = SM.getDecomposedIncludedLoc(FID).first;
       FE = SM.getFileEntryForID(FID);
     }
     return Results;
   }
   case SymbolLocation::Standard: {
     for (const auto &H : Loc.standard().headers()) {
-      Results.push_back(H);
+      Results.emplace_back(H, Hints::PublicHeader);
       for (const auto *Export : PI->getExporters(H, SM.getFileManager()))
-        Results.push_back(Header(Export));
+        Results.emplace_back(Header(Export), IsPublicHeader(Export));
     }
+    // StandardLibrary returns headers in preference order, so only mark the
+    // first.
+    if (!Results.empty())
+      Results.front().Hint |= Hints::PreferredHeader;
     return Results;
   }
   }
   llvm_unreachable("unhandled SymbolLocation kind!");
 }
 
+llvm::SmallVector<Header> headersForSymbol(const Symbol &S,
+                                           const SourceManager &SM,
+                                           const PragmaIncludes *PI) {
+  // Get headers for all the locations providing Symbol. Same header can be
+  // reached through different traversals, deduplicate those into a single
+  // Header by merging their hints.
+  llvm::SmallVector<Hinted<Header>> Headers;
+  for (auto &Loc : locateSymbol(S))
+    Headers.append(applyHints(findHeaders(Loc, SM, PI), Loc.Hint));
+  // If two Headers probably refer to the same file (e.g. Verbatim(foo.h) and
+  // Physical(/path/to/foo.h), we won't deduplicate them or merge their hints
+  llvm::stable_sort(
+      Headers, [](const Hinted<Header> &LHS, const Hinted<Header> &RHS) {
+        return static_cast<Header>(LHS) < static_cast<Header>(RHS);
+      });
+  auto *Write = Headers.begin();
+  for (auto *Read = Headers.begin(); Read != Headers.end(); ++Write) {
+    *Write = *Read++;
+    while (Read != Headers.end() &&
+           static_cast<Header>(*Write) == static_cast<Header>(*Read)) {
+      Write->Hint |= Read->Hint;
+      ++Read;
+    }
+  }
+  Headers.erase(Write, Headers.end());
+
+  // Add name match hints to deduplicated providers.
+  llvm::StringRef SymbolName = symbolName(S);
+  for (auto &H : Headers) {
+    if (nameMatch(SymbolName, H))
+      H.Hint |= Hints::PreferredHeader;
+  }
+
+  // FIXME: Introduce a MainFile header kind or signal and boost it.
+  return ranked(std::move(Headers));
+}
 } // namespace clang::include_cleaner

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

std::string spellHeader(const Header &H) {
     }
     llvm_unreachable("Unknown Header kind");
   }
 
   void fillTarget(Ref &R) {
     // Duplicates logic from walkUsed(), which doesn't expose SymbolLocations.
     for (auto &Loc : locateSymbol(R.Sym))
       R.Locations.push_back(Loc);
-    for (const auto &Loc : R.Locations)
-      R.Headers.append(findHeaders(Loc, SM, PI));
+    R.Headers = headersForSymbol(R.Sym, 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)
       : OS(OS), Ctx(Ctx), SM(Ctx.getSourceManager()), HS(HS),

clang-tools-extra/include-cleaner/lib/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/Decl.h"
 #include "clang/AST/DeclBase.h"
-#include "clang/Basic/SourceLocation.h"
+#include "clang/AST/DeclCXX.h"
+#include "clang/AST/DeclTemplate.h"
 #include "clang/Tooling/Inclusions/StandardLibrary.h"
-#include "llvm/ADT/StringExtras.h"
-#include "llvm/Support/raw_ostream.h"
+#include "llvm/Support/Casting.h"
 #include <utility>
 #include <vector>
 
 namespace clang::include_cleaner {
 namespace {
 
-std::vector<SymbolLocation> locateDecl(const Decl &D) {
-  std::vector<SymbolLocation> Result;
+template <typename T> Hints completeIfDefinition(T *D) {
+  return D->isThisDeclarationADefinition() ? Hints::CompleteSymbol
+                                           : Hints::None;
+}
+
+Hints declHints(const Decl *D) {
+  // Definition is only needed for classes and templates for completeness.
+  if (auto *TD = llvm::dyn_cast<TagDecl>(D))
+    return completeIfDefinition(TD);
+  else if (auto *CTD = llvm::dyn_cast<ClassTemplateDecl>(D))
+    return completeIfDefinition(CTD);
+  else if (auto *FTD = llvm::dyn_cast<FunctionTemplateDecl>(D))
+    return completeIfDefinition(FTD);
+  // Any other declaration is assumed usable.
+  return Hints::CompleteSymbol;
+}
+
+std::vector<Hinted<SymbolLocation>> locateDecl(const Decl &D) {
+  std::vector<Hinted<SymbolLocation>> Result;
   // FIXME: Should we also provide physical locations?
   if (auto SS = tooling::stdlib::Recognizer()(&D))
-    return {SymbolLocation(*SS)};
+    return {{*SS, Hints::CompleteSymbol}};
+  // FIXME: Signal foreign decls, e.g. a forward declaration not owned by a
+  // library. Some useful signals could be derived by checking the DeclContext.
+  // Most incidental forward decls look like:
+  //   namespace clang {
+  //   class SourceManager; // likely an incidental forward decl.
+  //   namespace my_own_ns {}
+  //   }
   for (auto *Redecl : D.redecls())
-    Result.push_back(Redecl->getLocation());
+    Result.push_back({Redecl->getLocation(), declHints(Redecl)});
   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");
-}
-
-std::vector<SymbolLocation> locateSymbol(const Symbol &S) {
+std::vector<Hinted<SymbolLocation>> locateSymbol(const Symbol &S) {
   switch (S.kind()) {
   case Symbol::Declaration:
     return locateDecl(S.declaration());
   case Symbol::Macro:
-    return {SymbolLocation(S.macro().Definition)};
+    return {{S.macro().Definition, Hints::CompleteSymbol}};
   }
   llvm_unreachable("Unknown Symbol::Kind enum");
 }
 
 } // namespace clang::include_cleaner

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

 //===--- Types.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/Types.h"
+#include "TypesInternal.h"
 #include "clang/AST/Decl.h"
 #include "clang/Basic/FileEntry.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Support/raw_ostream.h"
 
 namespace clang::include_cleaner {
 
 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Symbol &S) {
llvm::SmallVector<const Include *> Includes::match(Header H) const {
   case Header::Verbatim:
     for (unsigned I : BySpelling.lookup(H.verbatim().trim("\"<>")))
       Result.push_back(&All[I]);
     break;
   }
   return Result;
 }
 
+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");
+}
+
+bool Header::operator<(const Header &RHS) const {
+  if (kind() != RHS.kind())
+    return kind() < RHS.kind();
+  switch (kind()) {
+  case Header::Physical:
+    return physical()->getName() < RHS.physical()->getName();
+  case Header::Standard:
+    return standard().name() < RHS.standard().name();
+  case Header::Verbatim:
+    return verbatim() < RHS.verbatim();
+  }
+}
 } // namespace clang::include_cleaner

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

+//===--- TypesInternal.h - Intermediate structures used for analysis 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef CLANG_INCLUDE_CLEANER_TYPESINTERNAL_H
+#define CLANG_INCLUDE_CLEANER_TYPESINTERNAL_H
+
+#include "clang/Basic/SourceLocation.h"
+#include "clang/Tooling/Inclusions/StandardLibrary.h"
+#include "llvm/ADT/BitmaskEnum.h"
+#include <cstdint>
+#include <utility>
+#include <variant>
+
+namespace llvm {
+class raw_ostream;
+}
+namespace clang::include_cleaner {
+/// 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 &);
+
+/// Represents properties of a symbol provider.
+///
+/// Hints represents the properties of the edges traversed when finding headers
+/// that satisfy an AST node (AST node => symbols => locations => headers).
+///
+/// Since there can be multiple paths from an AST node to same header, we need
+/// to merge hints. These hints are merged by taking the union of all the
+/// properties along all the paths. We choose the boolean sense accordingly,
+/// e.g. "Public" rather than "Private", because a header is good if it provides
+/// any public definition, even if it also provides private ones.
+///
+/// Hints are sorted in ascending order of relevance.
+enum class Hints : uint8_t {
+  None = 0x00,
+  /// Provides a generally-usable definition for the symbol. (a function decl,
+  /// or class definition and not a forward declaration of a template).
+  CompleteSymbol = 1 << 0,
+  /// Symbol is provided by a public file. Only absent in the cases where file
+  /// is explicitly marked as such, non self-contained or IWYU private
+  /// pragmas.
+  PublicHeader = 1 << 1,
+  /// Header providing the symbol is explicitly marked as preferred, with an
+  /// IWYU private pragma that points at this provider or header and symbol has
+  /// ~the same name.
+  PreferredHeader = 1 << 2,
+  LLVM_MARK_AS_BITMASK_ENUM(PreferredHeader),
+};
+LLVM_ENABLE_BITMASK_ENUMS_IN_NAMESPACE();
+/// A wrapper to augment values with hints.
+template <typename T> struct Hinted : public T {
+  Hints Hint;
+  Hinted(T &&Wrapped, Hints H) : T(std::move(Wrapped)), Hint(H) {}
+
+  /// Since hints are sorted by relevance, use it directly.
+  bool operator<(const Hinted<T> &Other) const {
+    return static_cast<int>(Hint) < static_cast<int>(Other.Hint);
+  }
+};
+
+} // namespace clang::include_cleaner
+
+#endif

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

 //===--- AnalysisTest.cpp -------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang-include-cleaner/Analysis.h"
+#include "AnalysisInternal.h"
 #include "clang-include-cleaner/Record.h"
 #include "clang-include-cleaner/Types.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/Basic/FileManager.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Frontend/FrontendActions.h"
 #include "clang/Testing/TestAST.h"
walkUsed(TopLevelDecls, Recorded.MacroReferences,
                  ASSERT_TRUE(RefLoc.isInvalid())
                      << "Expected only one 'target' ref loc per testcase";
                  RefLoc = Ref.RefLocation;
                }
              });
     FileID MainFID = SM.getMainFileID();
     if (RefLoc.isValid()) {
       EXPECT_THAT(RefLoc, AllOf(expandedAt(MainFID, Main.point("expand"), &SM),
-                                 spelledAt(MainFID, Main.point("spell"), &SM)))
           << T.Main;
     } else {
       EXPECT_THAT(Main.points(), testing::IsEmpty());
     }
   }
 }
 
+TEST(Hints, Ordering) {
+  struct Tag {};
+  auto Hinted = [](Hints Hints) {
+    return clang::include_cleaner::Hinted<Tag>({}, Hints);
+  };
+  EXPECT_LT(Hinted(Hints::None), Hinted(Hints::CompleteSymbol));
+  EXPECT_LT(Hinted(Hints::CompleteSymbol), Hinted(Hints::PublicHeader));
+  EXPECT_LT(Hinted(Hints::PublicHeader), Hinted(Hints::PreferredHeader));
+  EXPECT_LT(Hinted(Hints::CompleteSymbol | Hints::PublicHeader),
+            Hinted(Hints::PreferredHeader));
+}
+
 } // namespace
 } // namespace clang::include_cleaner

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

 //===--- FindHeadersTest.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 "AnalysisInternal.h"
-#include "clang-include-cleaner/Analysis.h"
+#include "TypesInternal.h"
 #include "clang-include-cleaner/Record.h"
 #include "clang-include-cleaner/Types.h"
 #include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/Basic/FileEntry.h"
 #include "clang/Basic/FileManager.h"
 #include "clang/Frontend/FrontendActions.h"
 #include "clang/Testing/TestAST.h"
 #include "clang/Tooling/Inclusions/StandardLibrary.h"
-#include "llvm/ADT/ArrayRef.h"
-#include "llvm/Support/raw_ostream.h"
-#include "llvm/Testing/Annotations/Annotations.h"
+#include "llvm/ADT/SmallVector.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include <memory>
 
 namespace clang::include_cleaner {
 namespace {
+using testing::ElementsAre;
 using testing::UnorderedElementsAre;
 
 std::string guard(llvm::StringRef Code) {
   return "#pragma once\n" + Code.str();
 }
 
 class FindHeadersTest : public testing::Test {
 protected:
Inputs.MakeAction = [this] {
 
         PragmaIncludes *Out;
       };
       return std::make_unique<Hook>(&PI);
     };
   }
   void buildAST() { AST = std::make_unique<TestAST>(Inputs); }
 
-  llvm::SmallVector<Header> findHeaders(llvm::StringRef FileName) {
+  llvm::SmallVector<Hinted<Header>> findHeaders(llvm::StringRef FileName) {
     return include_cleaner::findHeaders(
         AST->sourceManager().translateFileLineCol(
             AST->fileManager().getFile(FileName).get(),
             /*Line=*/1, /*Col=*/1),
         AST->sourceManager(), &PI);
   }
   const FileEntry *physicalHeader(llvm::StringRef FileName) {
     return AST->fileManager().getFile(FileName).get();
TEST_F(FindHeadersTest, NonSelfContainedTraverseExporter) {
   buildAST();
   // Verify that we emit exporters for each header on the path.
   EXPECT_THAT(findHeaders("fragment.inc"),
               UnorderedElementsAre(physicalHeader("fragment.inc"),
                                    physicalHeader("exported.h"),
                                    physicalHeader("exporter.h")));
 }
 
 TEST_F(FindHeadersTest, TargetIsExpandedFromMacroInHeader) {
   struct CustomVisitor : RecursiveASTVisitor<CustomVisitor> {
     const Decl *Out = nullptr;
     bool VisitNamedDecl(const NamedDecl *ND) {
       if (ND->getName() == "FLAG_foo" || ND->getName() == "Foo") {
         EXPECT_TRUE(Out == nullptr);
         Out = ND;
       }
       return true;
for (const auto &T : TestCases) {
     Inputs.Code = R"cpp(#include "declare.h")cpp";
     Inputs.ExtraFiles["declare.h"] = guard(T.DeclareHeader);
     Inputs.ExtraFiles["macro.h"] = guard(T.MacroHeader);
     buildAST();
 
     CustomVisitor Visitor;
     Visitor.TraverseDecl(AST->context().getTranslationUnitDecl());
 
-    llvm::SmallVector<Header> Headers = clang::include_cleaner::findHeaders(
+    auto Headers = clang::include_cleaner::findHeaders(
         Visitor.Out->getLocation(), AST->sourceManager(),
         /*PragmaIncludes=*/nullptr);
     EXPECT_THAT(Headers, UnorderedElementsAre(physicalHeader("declare.h")));
   }
 }
 
+MATCHER_P2(HintedHeader, Header, Hint, "") {
+  return std::tie(arg.Hint, arg) == std::tie(Hint, Header);
+}
+
+TEST_F(FindHeadersTest, PublicHeaderHint) {
+  Inputs.Code = R"cpp(
+    #include "public.h"
+  )cpp";
+  Inputs.ExtraFiles["public.h"] = guard(R"cpp(
+    #include "private.h"
+    #include "private.inc"
+  )cpp");
+  Inputs.ExtraFiles["private.h"] = guard(R"cpp(
+    // IWYU pragma: private
+  )cpp");
+  Inputs.ExtraFiles["private.inc"] = "";
+  buildAST();
+  // Non self-contained files and headers marked with IWYU private pragma
+  // shouldn't have PublicHeader hint.
+  EXPECT_THAT(
+      findHeaders("private.inc"),
+      UnorderedElementsAre(
+          HintedHeader(physicalHeader("private.inc"), Hints::None),
+          HintedHeader(physicalHeader("public.h"), Hints::PublicHeader)));
+  EXPECT_THAT(findHeaders("private.h"),
+              UnorderedElementsAre(
+                  HintedHeader(physicalHeader("private.h"), Hints::None)));
+}
+
+TEST_F(FindHeadersTest, PreferredHeaderHint) {
+  Inputs.Code = R"cpp(
+    #include "private.h"
+  )cpp";
+  Inputs.ExtraFiles["private.h"] = guard(R"cpp(
+    // IWYU pragma: private, include "public.h"
+  )cpp");
+  buildAST();
+  // Headers explicitly marked should've preferred signal.
+  EXPECT_THAT(findHeaders("private.h"),
+              UnorderedElementsAre(
+                  HintedHeader(physicalHeader("private.h"), Hints::None),
+                  HintedHeader(Header("\"public.h\""),
+                               Hints::PreferredHeader | Hints::PublicHeader)));
+}
+
+class HeadersForSymbolTest : public FindHeadersTest {
+protected:
+  llvm::SmallVector<Header> headersForFoo() {
+    struct Visitor : public RecursiveASTVisitor<Visitor> {
+      const NamedDecl *Out = nullptr;
+      bool VisitNamedDecl(const NamedDecl *ND) {
+        if (ND->getName() == "foo") {
+          EXPECT_TRUE(Out == nullptr || Out == ND->getCanonicalDecl())
+              << "Found multiple matches for foo.";
+          Out = cast<NamedDecl>(ND->getCanonicalDecl());
+        }
+        return true;
+      }
+    };
+    Visitor V;
+    V.TraverseDecl(AST->context().getTranslationUnitDecl());
+    if (!V.Out)
+      ADD_FAILURE() << "Couldn't find any decls named foo.";
+    assert(V.Out);
+    return headersForSymbol(*V.Out, AST->sourceManager(), &PI);
+  }
+};
+
+TEST_F(HeadersForSymbolTest, Deduplicates) {
+  Inputs.Code = R"cpp(
+    #include "foo.h"
+  )cpp";
+  Inputs.ExtraFiles["foo.h"] = guard(R"cpp(
+    // IWYU pragma: private, include "foo.h"
+    void foo();
+    void foo();
+  )cpp");
+  buildAST();
+  EXPECT_THAT(
+      headersForFoo(),
+      UnorderedElementsAre(physicalHeader("foo.h"),
+                           // FIXME: de-duplicate across different kinds.
+                           Header("\"foo.h\"")));
+}
+
+TEST_F(HeadersForSymbolTest, RankByName) {
+  Inputs.Code = R"cpp(
+    #include "fox.h"
+    #include "bar.h"
+  )cpp";
+  Inputs.ExtraFiles["fox.h"] = guard(R"cpp(
+    void foo();
+  )cpp");
+  Inputs.ExtraFiles["bar.h"] = guard(R"cpp(
+    void foo();
+  )cpp");
+  buildAST();
+  EXPECT_THAT(headersForFoo(),
+              ElementsAre(physicalHeader("bar.h"), physicalHeader("fox.h")));
+}
+
+TEST_F(HeadersForSymbolTest, Ranking) {
+  // Sorting is done over (canonical, public, complete) triplet.
+  Inputs.Code = R"cpp(
+    #include "private.h"
+    #include "public.h"
+    #include "public_complete.h"
+  )cpp";
+  Inputs.ExtraFiles["public.h"] = guard(R"cpp(
+    struct foo;
+  )cpp");
+  Inputs.ExtraFiles["private.h"] = guard(R"cpp(
+    // IWYU pragma: private, include "canonical.h"
+    struct foo;
+  )cpp");
+  Inputs.ExtraFiles["public_complete.h"] = guard("struct foo {};");
+  buildAST();
+  EXPECT_THAT(headersForFoo(), ElementsAre(Header("\"canonical.h\""),
+                                           physicalHeader("public_complete.h"),
+                                           physicalHeader("public.h"),
+                                           physicalHeader("private.h")));
+}
+
+TEST_F(HeadersForSymbolTest, PreferPublicOverComplete) {
+  Inputs.Code = R"cpp(
+    #include "complete_private.h"
+    #include "public.h"
+  )cpp";
+  Inputs.ExtraFiles["complete_private.h"] = guard(R"cpp(
+    // IWYU pragma: private
+    struct foo {};
+  )cpp");
+  Inputs.ExtraFiles["public.h"] = guard("struct foo;");
+  buildAST();
+  EXPECT_THAT(headersForFoo(),
+              ElementsAre(physicalHeader("public.h"),
+                          physicalHeader("complete_private.h")));
+}
+
+TEST_F(HeadersForSymbolTest, PreferNameMatch) {
+  Inputs.Code = R"cpp(
+    #include "public_complete.h"
+    #include "test/foo.fwd.h"
+  )cpp";
+  Inputs.ExtraFiles["public_complete.h"] = guard(R"cpp(
+    struct foo {};
+  )cpp");
+  Inputs.ExtraFiles["test/foo.fwd.h"] = guard("struct foo;");
+  buildAST();
+  EXPECT_THAT(headersForFoo(),
+              ElementsAre(physicalHeader("test/foo.fwd.h"),
+                          physicalHeader("public_complete.h")));
+}
+
+TEST_F(HeadersForSymbolTest, MainFile) {
+  Inputs.Code = R"cpp(
+    #include "public_complete.h"
+    struct foo;
+  )cpp";
+  Inputs.ExtraFiles["public_complete.h"] = guard(R"cpp(
+    struct foo {};
+  )cpp");
+  buildAST();
+  auto &SM = AST->sourceManager();
+  // FIXME: Symbols provided by main file should be treated specially.
+  EXPECT_THAT(headersForFoo(),
+              ElementsAre(physicalHeader("public_complete.h"),
+                          Header(SM.getFileEntryForID(SM.getMainFileID()))));
+}
+
+TEST_F(HeadersForSymbolTest, PreferExporterOfPrivate) {
+  Inputs.Code = R"cpp(
+    #include "private.h"
+    #include "exporter.h"
+  )cpp";
+  Inputs.ExtraFiles["private.h"] = guard(R"cpp(
+    // IWYU pragma: private
+    struct foo {};
+  )cpp");
+  Inputs.ExtraFiles["exporter.h"] = guard(R"cpp(
+    #include "private.h" // IWYU pragma: export
+  )cpp");
+  buildAST();
+  EXPECT_THAT(headersForFoo(), ElementsAre(physicalHeader("exporter.h"),
+                                           physicalHeader("private.h")));
+}
+
+TEST_F(HeadersForSymbolTest, PreferPublicOverNameMatchOnPrivate) {
+  Inputs.Code = R"cpp(
+    #include "foo.h"
+  )cpp";
+  Inputs.ExtraFiles["foo.h"] = guard(R"cpp(
+    // IWYU pragma: private, include "public.h"
+    struct foo {};
+  )cpp");
+  buildAST();
+  EXPECT_THAT(headersForFoo(), ElementsAre(Header(StringRef("\"public.h\"")),
+                                           physicalHeader("foo.h")));
+}
 } // namespace
 } // namespace clang::include_cleaner

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 "TypesInternal.h"
 #include "clang-include-cleaner/Types.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclBase.h"
 #include "clang/AST/RecursiveASTVisitor.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/Testing/Annotations/Annotations.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include <cstddef>
 #include <memory>
+#include <tuple>
 #include <unordered_map>
 #include <utility>
 #include <variant>
 #include <vector>
 
 namespace clang::include_cleaner {
 namespace {
+using testing::Each;
 using testing::ElementsAre;
 using testing::ElementsAreArray;
+using testing::Eq;
+using testing::Field;
 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.
LocateExample(llvm::StringRef AnnotatedCode)
           return Inputs;
         }()) {}
 
   const Decl &findDecl(llvm::StringRef SymbolName) {
     struct Visitor : RecursiveASTVisitor<Visitor> {
       llvm::StringRef NameToFind;
       const NamedDecl *Out = nullptr;
       bool VisitNamedDecl(const NamedDecl *ND) {
+        // Skip the templated decls, as they have the same name and matches in
+        // this file care about the outer template name.
+        if (auto *TD = ND->getDescribedTemplate())
+          ND = TD;
         if (ND->getName() == NameToFind) {
           EXPECT_TRUE(Out == nullptr || Out == ND->getCanonicalDecl())
               << "Found multiple matches for " << NameToFind;
           Out = cast<NamedDecl>(ND->getCanonicalDecl());
         }
         return true;
       }
     };

 
 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()));
 }
 
+MATCHER_P2(HintedSymbol, Symbol, Hint, "") {
+  return std::tie(arg.Hint, arg) == std::tie(Hint, Symbol);
+}
+TEST(LocateSymbol, CompleteSymbolHint) {
+  {
+    // stdlib symbols are always complete.
+    LocateExample Test("namespace std { struct vector; }");
+    EXPECT_THAT(locateSymbol(Test.findDecl("vector")),
+                ElementsAre(HintedSymbol(
+                    *tooling::stdlib::Symbol::named("std::", "vector"),
+                    Hints::CompleteSymbol)));
+  }
+  {
+    // macros are always complete.
+    LocateExample Test("#define ^FOO");
+    EXPECT_THAT(locateSymbol(Test.findMacro("FOO")),
+                ElementsAre(HintedSymbol(Test.points().front(),
+                                         Hints::CompleteSymbol)));
+  }
+  {
+    // Completeness is only absent in cases that matters.
+    const llvm::StringLiteral Cases[] = {
+        "struct ^foo; struct ^foo {};",
+        "template <typename> struct ^foo; template <typename> struct ^foo {};",
+        "template <typename> void ^foo(); template <typename> void ^foo() {};",
+    };
+    for (auto &Case : Cases) {
+      SCOPED_TRACE(Case);
+      LocateExample Test(Case);
+      EXPECT_THAT(locateSymbol(Test.findDecl("foo")),
+                  ElementsAre(HintedSymbol(Test.points().front(), Hints::None),
+                              HintedSymbol(Test.points().back(),
+                                           Hints::CompleteSymbol)));
+    }
+  }
+  {
+    // All declarations should be marked as complete in cases that a definition
+    // is not usually needed.
+    const llvm::StringLiteral Cases[] = {
+        "void foo(); void foo() {}",
+        "extern int foo; int foo;",
+    };
+    for (auto &Case : Cases) {
+      SCOPED_TRACE(Case);
+      LocateExample Test(Case);
+      EXPECT_THAT(locateSymbol(Test.findDecl("foo")),
+                  Each(Field(&Hinted<SymbolLocation>::Hint,
+                             Eq(Hints::CompleteSymbol))));
+    }
+  }
+}
+
 } // namespace
 } // namespace clang::include_cleaner