[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

85

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)

89

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

90

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.

93

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

95

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?

100

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).

103

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

25–42

nit: declHints?

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

161

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

266

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

84

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

85

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")

87

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.

90

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.

95

+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.

103

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

142–143

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

144

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")

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

45

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.

54

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)

63

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

89

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!)

100

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)

103

+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

171

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

176

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".

197

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

201

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

161

these tests seem to be in the wrong file

161

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

263

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.

266

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.

280

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

84

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

85

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.

90

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

93

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

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

89

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.

100

agreed, exports shouldn't really be boosted.

103

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

201

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

161

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?

266

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

133

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

84

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)

86

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

91

"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.

94

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

95

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.

110

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

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

38

just stable_sort(reverse(Headers))?

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

46

this signature seems unneccesarily complicated/hard to understand

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

60

debug stuff, and below

61

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)

118

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

130

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

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

114

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

161

Nope, I think I was just confused, sorry

256

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

133

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

114

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 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;
+
+  Header(std::in_place_t, 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
template <> struct DenseMapInfo<clang::include_cleaner::Macro> {
   }
   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 {std::in_place, Base::getEmptyKey()};
+  }
+  static inline Outer getTombstoneKey() {
+    return {std::in_place, 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

 
 #ifndef CLANG_INCLUDE_CLEANER_ANALYSISINTERNAL_H
 #define CLANG_INCLUDE_CLEANER_ANALYSISINTERNAL_H
 
 #include "clang-include-cleaner/Record.h"
 #include "clang-include-cleaner/Types.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Tooling/Inclusions/StandardLibrary.h"
+#include "llvm/ADT/BitmaskEnum.h"
 #include "llvm/ADT/STLFunctionalExtras.h"
 #include <variant>
 #include <vector>
 
 namespace clang {
 class ASTContext;
 class Decl;
 class HeaderSearch;
struct SymbolLocation {
   }
 
 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 touched 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, hence these are all expressed positively.
+///
+/// Hints are sorted in ascending order of relevance.
+enum class Hint : uint8_t {
+  None = 0x00,
+  /// Provides a generally-usable definition for the symbol. (e.g. 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, e.g. non self-contained or IWYU private
+  /// pragmas.
+  PublicHeader = 1 << 1,
+  /// Header providing the symbol is explicitly marked as preferred, e.g. with a
+  /// 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 types with hints.
+template <typename T> struct Hinted : public T {
+  Hint Hints;
+  Hinted(T &&Wrapped, Hint H) : T(std::move(Wrapped)), Hints(H) {}
+
+  /// Since hints are sorted by relevance, use it directly.
+  bool operator<(const Hinted<T> &Other) const {
+    return static_cast<int>(Hints) < static_cast<int>(Other.Hints);
+  }
+};
+
 /// 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 "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/BitmaskEnum.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 "llvm/Support/raw_ostream.h"
+#include <string>
+#include <utility>
 
 namespace clang::include_cleaner {
+namespace {
+llvm::SmallVector<Hinted<Header>>
+applyHints(llvm::SmallVector<Hinted<Header>> Headers, Hint H) {
+  for (auto &Header : Headers)
+    Header.Hints |= H;
+  return Headers;
+}
+
+llvm::SmallVector<Header> ranked(llvm::SmallVector<Hinted<Header>> Headers) {
+  llvm::stable_sort(Headers,
+                    [](const Hinted<Header> &LHS, const Hinted<Header> &RHS) {
+                      return RHS < LHS;
+                    });
+  return llvm::SmallVector<Header>(Headers.begin(), Headers.end());
+}
+
+llvm::SmallVector<Hinted<Header>>
+nameMatch(llvm::StringRef DeclName, llvm::SmallVector<Hinted<Header>> Headers) {
+  for (auto &H : Headers) {
+    llvm::StringRef SpelledH;
+    switch (H.kind()) {
+    case Header::Physical:
+      SpelledH = H.physical()->getName();
+      break;
+    case Header::Standard:
+      SpelledH = H.standard().name();
+      break;
+    case Header::Verbatim:
+      SpelledH = H.verbatim();
+      break;
+    }
+    llvm::errs() << "Checking name match for: " << SpelledH;
+    SpelledH = SpelledH.trim("<>\"");
+    if (auto LastSlash = SpelledH.rfind('/'); LastSlash != SpelledH.npos)
+      SpelledH = SpelledH.drop_front(LastSlash + 1);
+    // Drop everything after first `.` (dot).
+    // foo.h -> foo
+    // foo.cu.h -> foo
+    SpelledH = SpelledH.substr(0, SpelledH.find('.'));
+    if (SpelledH.equals_insensitive(DeclName))
+      H.Hints |= Hint::PreferredHeader;
+    llvm::errs() << " looks like: " << SpelledH << ' ' << DeclName
+                 << static_cast<int>(H.Hints) << '\n';
+  }
+  return Headers;
+}
+
+} // 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;
+  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, Hint::PublicHeader}};
+    auto IsPublicHeader = [&PI](const FileEntry *FE) {
+      return (PI->isPrivate(FE) || !PI->isSelfContained(FE))
+                 ? Hint::None
+                 : Hint::PublicHeader;
+    };
     while (FE) {
-      Results.push_back(Header(FE));
+      Hint 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,
+                             Hint::PublicHeader | Hint::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, Hint::PreferredHeader | Hint::PublicHeader);
     return Results;
   }
   }
   llvm_unreachable("unhandled SymbolLocation kind!");
 }
 
+llvm::SmallVector<Header> headersForSymbol(const Symbol &S,
+                                           const SourceManager &SM,
+                                           const PragmaIncludes *PI) {
+  llvm::SmallVector<Hinted<Header>> Headers;
+  for (auto &Loc : locateSymbol(S))
+    Headers.append(applyHints(findHeaders(Loc, SM, PI), Loc.Hints));
+  // 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->Hints |= Read->Hints;
+      ++Read;
+    }
+  }
+  Headers.erase(Write, Headers.end());
+
+  // Add name match hints to deduplicated providers.
+  llvm::StringRef SymbolName;
+  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())
+        SymbolName = II->getName();
+    break;
+  case Symbol::Macro:
+    SymbolName = S.macro().Name->getName();
+    break;
+  }
+  // FIXME: Introduce a MainFile header kind or signal and boost it.
+  return ranked(nameMatch(SymbolName, 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/AST/DeclCXX.h"
+#include "clang/AST/DeclTemplate.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Tooling/Inclusions/StandardLibrary.h"
 #include "llvm/ADT/StringExtras.h"
+#include "llvm/Support/Casting.h"
 #include "llvm/Support/raw_ostream.h"
 #include <utility>
 #include <vector>
 
 namespace clang::include_cleaner {
 namespace {
 
-std::vector<SymbolLocation> locateDecl(const Decl &D) {
-  std::vector<SymbolLocation> Result;
+template <typename T> Hint completeIfDefinition(T *D) {
+  return D->isThisDeclarationADefinition() ? Hint::CompleteSymbol : Hint::None;
+}
+
+Hint 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 Hint::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, Hint::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, Hint::CompleteSymbol}};
   }
   llvm_unreachable("Unknown Symbol::Kind enum");
 }
 
 } // namespace clang::include_cleaner

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

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;
 }
 
+bool Header::operator<(const Header &RHS) const {
+  if (kind() != RHS.kind())
+    return kind() < RHS.kind();
+  switch (kind()) {
+  case Header::Physical:
+    return physical() < RHS.physical();
+  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/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 = [](Hint Hints) {
+    return clang::include_cleaner::Hinted<Tag>({}, Hints);
+  };
+  EXPECT_LT(Hinted(Hint::None), Hinted(Hint::CompleteSymbol));
+  EXPECT_LT(Hinted(Hint::CompleteSymbol), Hinted(Hint::PublicHeader));
+  EXPECT_LT(Hinted(Hint::PublicHeader), Hinted(Hint::PreferredHeader));
+  EXPECT_LT(Hinted(Hint::CompleteSymbol | Hint::PublicHeader),
+            Hinted(Hint::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 "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 "llvm/ADT/ArrayRef.h"
-#include "llvm/Support/raw_ostream.h"
-#include "llvm/Testing/Support/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) {
-    return include_cleaner::findHeaders(
+    auto Headers = include_cleaner::findHeaders(
         AST->sourceManager().translateFileLineCol(
             AST->fileManager().getFile(FileName).get(),
             /*Line=*/1, /*Col=*/1),
         AST->sourceManager(), &PI);
+    return {Headers.begin(), Headers.end()};
   }
   const FileEntry *physicalHeader(llvm::StringRef FileName) {
     return AST->fileManager().getFile(FileName).get();
   };
 };
 
 TEST_F(FindHeadersTest, IWYUPrivateToPublic) {
   Inputs.Code = R"cpp(
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")));
   }
 }
 
+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, RankingPreservesDiscoveryOrder) {
+  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("fox.h"), physicalHeader("bar.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.proto.h"
+  )cpp";
+  Inputs.ExtraFiles["public_complete.h"] = guard(R"cpp(
+    struct foo {};
+  )cpp");
+  Inputs.ExtraFiles["test/foo.proto.h"] = guard("struct foo;");
+  buildAST();
+  EXPECT_THAT(headersForFoo(),
+              ElementsAre(physicalHeader("test/foo.proto.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("\"public.h\""), physicalHeader("foo.h")));
+}
 } // namespace
 } // namespace clang::include_cleaner