[clangd] IncludeCleaner as a library: Find all references to symbols in the file

[kbobyrev]

Summary

This is the first patch in an ongoing attempt of Include Cleaner: unused/missing
headere diagnostics, an IWYU-like functionality implementation for clangd. The
work is split into (mostly) distinct and parallelizable pieces:

• Finding all referenced locations (this patch).
• Finding all referenced locations of macros.
• Building IncludeGraph and marking headers as unused, used and directly used.
• Making use of the introduced library and add an option to use in clangd.

---

• Adding support for standard library headers (possibly through mapping genfiles).

Based on https://reviews.llvm.org/D100540.

[kbobyrev]

Significantly decrease the scope of this change. Focus on "IWYU as a library",
do not propagate into the other parts of clangd yet and keep the change
self-contained for the most part.

[kbobyrev]

Trim the patch even further: only extract locations, prune header marking logic
etc.

[kbobyrev]

Trim the patch even further: the scope is now simply findAllReferences
mechanism. Add more tests and improve functionality (handle using decls and
implicit types).

[kbobyrev]

Add one more test.

[kbobyrev]

Exclude std:: namespace handling.

[kbobyrev]

Improve comments, refactor some pieces, add more tests.

[kbobyrev]

Remove some code from the next chunk of IWYU work.

[kbobyrev]

Rebase on top of main.

[tschuett]

@kimgr

[sammccall]

First some thoughts on names... (hopefully to avoid some confusion)

IWYU might be used here to mean three things:

• the IWYU coding style/policy that says you should #include headers for the symbols you make use of, and no others
• the IWYU tool which applies IWYU style to files
• more generally, features that encourage hygiene policies for #includes ("IWYU functionality")

This work is about the last of these: putting header hygiene features in clangd. (Specifically, likely unused-include and missing-include warnings).
I think we should avoid the name "IWYU as a library" or "IWYU functionality" as it's ambiguous and also misleading:

• policy: we're likely to support policies other than the IWYU style
• tool: it's not likely to match the design or feature set of the IWYU tool

IncludeHygiene would be an ok name I think but a bit of a mouthful. WDYT?

(This work is definitely inspired by the IWYU tool and I'd used the name in discussions/prototypes, so this confusion is largely my fault! We also did this with clang-include-fixer which ended up as clangd/IncludeFixer.h, though the designs are much more similar)

[sammccall]

Thanks, this scope looks good for a first patch!

clang-tools-extra/clangd/IWYU.cpp

19

The first sentence doesn't mean much to me, I think we could just drop it?

64

Is this just "FIXME: should this behavior be configurable or tweaked?"

I think it's clear enough what "this behavior" is in context.
Whereas the rest of the comment adds some confusion (e.g. what's an "implicit type", what usage of auto are you talking about etc. And I think it's *way* too soon to say that it *should* be configurable - remember the application is unused-include, turning this off only grants the ability for headers to be marked unused even if they define the type of a subexpression.

I think it's more likely we'd tweak the heuristic in the future, e.g. only do this if it's a type that can be incomplete.

74

i usually add a private using Base = ... and refer to Base::TraverseType(T) - intent is clearer and often we end up with several of these

96

this name is a bit vague (why wouldn't we add it?), maybe isNew?

clang-tools-extra/clangd/IWYU.h

11

Related to the naming discussion, this should first say what the functionality is (warnings about header hygiene: misuse of transitive headers and unused includes).
Then definitely credit the IWYU tool and mention the differences.

18

I'm not sure we want to do this (or plan to do this) unless we have some idea of how discovery would work.

35

Maybe just "Finds locations of all symbols used in the main file"?

If you want to talk about traversal/impl strategy, that's OK but not in the first paragraph.

36

I'd be explicit that the returned locations may be macro expansions, and are not resolved to their spelling/expansion location.

39

I'm not quite sure what this is saying/who the audience for the comment is.
Maybe it's interesting to say something like

We use this to compute unused headers, so:

• we cover the whole file in a single traversal for efficiency
• we don't attempt to describe where symbols were referenced from
• in ambiguous cases (e.g. implicitly used symbols, multiple declarations) we err on the side of reporting all possible locations

42

It's a bit more general than this (e.g. multiple declaration). See previous comment for a wording suggestion

44

I actually don't think we'd use the same entrypoint for missing include, but rather duplicate it (and *maybe* share some impl details whose docs don't belong here).

The reason is we get to "throw away" different info in each case to make the data structures as tight as possible:

• for unused include, we can throw away the reference location and just track sets of locations and then files. This means we traverse first, build a bundle of locations, and then process them together.
• for missing include, we need the reference location, but don't need to associate them with specific #includes. So the tight data structure here is a set of allowed FileIDs plus a cache for macro FileIDs. Then we'll traverse last and query one symbol at a time, with early exit.

Comments about future plans can sometimes be useful I think, but this one seems pretty unlikely to pan out.

48

It's not obvious what this actually means.
Would be good to mention expanding macros

clang-tools-extra/clangd/unittests/IWYUTests.cpp

29

I think i'd be useful to have a comment in these for the node type or special case that's being tested

First few are

DeclRefExpr
RecordType
TypedefType
MemberExpr
Expr (type is traversed)
Redecls
CXXConstructExpr

85

I don't think so, IMO current behavior is fine.
B is not named, nor can its absence cause the type to be incomplete.

98

A bit more explicit about the bug?

When a type is resolved via a using declaration, the UsingShadowDecl is not referenced in the AST.
Compare to TypedefType, or DeclRefExpr::getFoundDecl().

[kbobyrev]

Thank you for the great suggestions! Indeed, we already have the confusion
regarding IWYU having the CLI flag and users are thinking we provide some sort
of integration/implementation. Having even more confusion (implementing
similar) functionality for our needs is not what we want (also, apologies for
confusion,"as a library" was more about the patch in this context - meaning not
a "usable" feature yet but a smaller scope where we just start the
implementation as the library that can only be used in tests for now). Hence,
renamed the feature to "Include Sanity" (close to Include Hygiene but sounds
better IMO, please let me know if you think otherwise).

I have addressed the review comments and will base my next patch on this (this
patch is probably mostly the blocker for the upcoming ones).

[kbobyrev]

Rename.

[kbobyrev]

Remove findReferencedFiles (to be introduced in the next patch) to preserve
proposed granularity.

[kbobyrev]

Fix tests name.

[kbobyrev]

[clangd] IncludeCleaner: Mark used headers.

Follow-up on D105426.

[kbobyrev]

Push back to the origin.

[sammccall]

clang-tools-extra/clangd/IncludeCleaner.cpp

65 ↗

(On Diff #366833)

I just realized this uses "T" if any expression has type "T*" even if never dereferenced, this is probably a gross overestimate. Nevertheless I guess fine for now.

101 ↗

(On Diff #366833)

this struct is not used in this patch

[kbobyrev]

Remove unused code.

clang-tools-extra/clangd/CMakeLists.txt

add_clang_library(clangDaemon
   FuzzyMatch.cpp
   GlobalCompilationDatabase.cpp
   Headers.cpp
   HeaderSourceSwitch.cpp
   HeuristicResolver.cpp
   Hover.cpp
   IncludeFixer.cpp
   InlayHints.cpp
+  IWYU.cpp
   JSONTransport.cpp
   PathMapping.cpp
   Protocol.cpp
   Quality.cpp
   ParsedAST.cpp
   Preamble.cpp
   RIFF.cpp
   Selection.cpp

clang-tools-extra/clangd/Headers.h

 // An #include directive that we found in the main file.
 struct Inclusion {
   tok::PPKeywordKind Directive; // Directive used for inclusion, e.g. import
   std::string Written;          // Inclusion name as written e.g. <vector>.
   Path Resolved; // Resolved path of included file. Empty if not resolved.
   unsigned HashOffset = 0; // Byte offset from start of file to #.
   int HashLine = 0;        // Line number containing the directive, 0-indexed.
   SrcMgr::CharacteristicKind FileKind = SrcMgr::C_User;
+  bool Used = true; // Was something from this used in the main file?
 };
 llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Inclusion &);
 bool operator==(const Inclusion &LHS, const Inclusion &RHS);
 
 // Contains information about one file in the build grpah and its direct
 // dependencies. Doesn't own the strings it references (IncludeGraph is
 // self-contained).
 struct IncludeGraphNode {
public:
   // Usually it should be SM.getFileEntryForID(SM.getMainFileID())->getName().
   llvm::StringMap<unsigned> includeDepth(llvm::StringRef Root) const;
 
   // This updates IncludeDepth(), but not MainFileIncludes.
   void recordInclude(llvm::StringRef IncludingName,
                      llvm::StringRef IncludedName,
                      llvm::StringRef IncludedRealName);
 
+  // Captures the filename corresponding to system includes like <vector>.
+  // This is used in for IWYU of the standard library as we want to check
+  // against where the spec *says* the symbols are.
+  void recordSystemInclude(llvm::StringRef Spelled,
+                           llvm::StringRef IncludedName);
+
+  // Classifying the main-file includes as "used" or "unused" is subtle
+  // (consider transitive includes), so we inject the algorithm.
+
+  // An AbstractIncludeGraph maps including files to included files.
+  using AbstractIncludeGraph = llvm::DenseMap<unsigned, SmallVector<unsigned>>;
+  // A UsedFunc decides whether each file included by EntryPoint is "used",
+  // based on the set of files that contain some referenced symbol.
+  using UsedFunc = llvm::DenseMap<unsigned, bool>(
+      const AbstractIncludeGraph &, llvm::DenseSet<unsigned> Referenced,
+      unsigned EntryPoint);
+  // Mark each MainFileIncludes with the decision yielded by the UsedFunc.
+  void markUsed(llvm::StringRef EntryPoint,
+                llvm::ArrayRef<StringRef> ReferencedFiles,
+                llvm::DenseSet<StringRef> ReferencedStdlib,
+                llvm::function_ref<UsedFunc>);
+
 private:
   // Identifying files in a way that persists from preamble build to subsequent
   // builds is surprisingly hard. FileID is unavailable in InclusionDirective(),
   // and RealPathName and UniqueID are not preserved in the preamble.
   // We use the FileEntry::Name, which is stable, interned into a "file index".
   // The paths we want to expose are the RealPathName, so store those too.
   std::vector<std::string> RealPathNames; // In file index order.
   unsigned fileIndex(llvm::StringRef Name);
   llvm::StringMap<unsigned> NameToIndex; // Values are file indexes.
   // Maps a file's index to that of the files it includes.
   llvm::DenseMap<unsigned, llvm::SmallVector<unsigned>> IncludeChildren;
+  // Index of standard library files, e.g. "vector".
+  llvm::DenseMap<llvm::StringRef, unsigned> StandardIncludes;
 };
 
 /// Returns a PPCallback that visits all inclusions in the main file.
 std::unique_ptr<PPCallbacks>
 collectIncludeStructureCallback(const SourceManager &SM, IncludeStructure *Out);
 
 // Calculates insertion edit for including a new header in a file.
 class IncludeInserter {

clang-tools-extra/clangd/Headers.cpp

if (File) {
         assert(SM.getBufferName(HashLoc).startswith("<") &&
                "Expected #include location to be a file or <built-in>");
         // Treat as if included from the main file.
         IncludingFileEntry = SM.getFileEntryForID(MainFID);
       }
       Out->recordInclude(IncludingFileEntry->getName(), File->getName(),
                          File->tryGetRealPathName());
     }
+    if (IsAngled && File)
+      Out->recordSystemInclude(FileName, File->getName());
   }
 
   void FileChanged(SourceLocation Loc, FileChangeReason Reason,
                    SrcMgr::CharacteristicKind FileType,
                    FileID PrevFID) override {
     switch (Reason) {
     case PPCallbacks::EnterFile:
       if (BuiltinFile.isInvalid() && SM.isWrittenInBuiltinFile(Loc)) {
private:
   // Set after entering the <built-in> file.
   FileID BuiltinFile;
   // Indicates whether <built-in> file is part of include stack.
   bool InBuiltinFile = false;
 
   IncludeStructure *Out;
 };
 
+// Map of unquoted to quoted
+const llvm::StringMap<llvm::StringRef> &allStandardIncludes() {
+  static llvm::StringMap<llvm::StringRef> Result = {
+#define SYMBOL(Name, Namespace, Header)                                        \
+  {llvm::StringRef(#Header).ltrim('<').rtrim('>'), #Header},
+#include "CSymbolMap.inc"
+#include "StdSymbolMap.inc"
+#undef SYMBOL
+  };
+  return Result;
+}
+
 } // namespace
 
 bool isLiteralInclude(llvm::StringRef Include) {
   return Include.startswith("<") || Include.startswith("\"");
 }
 
 bool HeaderFile::valid() const {
   return (Verbatim && isLiteralInclude(File)) ||
void IncludeStructure::recordInclude(llvm::StringRef IncludingName,
                                      llvm::StringRef IncludedRealName) {
   auto Child = fileIndex(IncludedName);
   if (!IncludedRealName.empty() && RealPathNames[Child].empty())
     RealPathNames[Child] = std::string(IncludedRealName);
   auto Parent = fileIndex(IncludingName);
   IncludeChildren[Parent].push_back(Child);
 }
 
+void IncludeStructure::recordSystemInclude(llvm::StringRef Spelled,
+                                           llvm::StringRef IncludedName) {
+  const auto &AllStandardIncludes = allStandardIncludes();
+  auto It = AllStandardIncludes.find(Spelled);
+  if (It == AllStandardIncludes.end())
+    return;
+  auto New = StandardIncludes.try_emplace(It->getValue());
+  if (New.second)
+    New.first->second = fileIndex(IncludedName);
+}
+
 unsigned IncludeStructure::fileIndex(llvm::StringRef Name) {
   auto R = NameToIndex.try_emplace(Name, RealPathNames.size());
   if (R.second)
     RealPathNames.emplace_back();
   return R.first->getValue();
 }
 
 llvm::StringMap<unsigned>
for (const auto &Parent : PreviousLevel) {
             Result[Name] = Level;
         }
       }
     }
   }
   return Result;
 }
 
+void IncludeStructure::markUsed(llvm::StringRef EntryPoint,
+                                llvm::ArrayRef<StringRef> ReferencedFiles,
+                                llvm::DenseSet<StringRef> ReferencedStdlib,
+                                llvm::function_ref<UsedFunc> Algorithm) {
+  auto Root = NameToIndex.find(EntryPoint);
+  if (Root == NameToIndex.end()) {
+    elog("IWYU: entrypoint {0} not found in include graph", EntryPoint);
+    return;
+  }
+
+  llvm::DenseSet<unsigned> Referenced;
+  Referenced.reserve(ReferencedFiles.size());
+  for (llvm::StringRef RefName : ReferencedFiles) {
+    dlog("{0} is REFERENCED", RefName);
+    auto It = NameToIndex.find(RefName);
+    if (It != NameToIndex.end())
+      Referenced.insert(It->second);
+  }
+  for (llvm::StringRef RefStdlib : ReferencedStdlib) {
+    auto It = StandardIncludes.find(RefStdlib);
+    if (It == StandardIncludes.end()) {
+      dlog("<{0}> is REFERENCED but missing!");
+      continue;
+    }
+    dlog("<{0}> is REFERENCED ({1})", RefStdlib, RealPathNames[It->second]);
+    Referenced.insert(It->second);
+  }
+
+  auto Decisions =
+      Algorithm(IncludeChildren, std::move(Referenced), Root->second);
+  auto RootChildren = IncludeChildren.find(Root->second);
+  assert(RootChildren != IncludeChildren.end());
+  llvm::DenseMap</*RealPath*/ StringRef, /*Index*/ unsigned> IncludeIndex;
+  for (const auto Index : RootChildren->second) {
+    if (!RealPathNames[Index].empty())
+      IncludeIndex[RealPathNames[Index]] = Index;
+  }
+  for (auto &MFI : MainFileIncludes) {
+    // FIXME: skip includes that are not self-contained.
+    auto It = IncludeIndex.find(MFI.Resolved);
+    if (It != IncludeIndex.end()) {
+      auto DIt = Decisions.find(It->second);
+      if (DIt != Decisions.end()) {
+        MFI.Used = DIt->second;
+        dlog("{0} is {1}", MFI.Written, MFI.Used ? "USED" : "UNUSED");
+      }
+    }
+  }
+}
+
 void IncludeInserter::addExisting(const Inclusion &Inc) {
   IncludedHeaders.insert(Inc.Written);
   if (!Inc.Resolved.empty())
     IncludedHeaders.insert(Inc.Resolved);
 }
 
 /// FIXME(ioeric): we might not want to insert an absolute include path if the
 /// path is not shortened.

clang-tools-extra/clangd/IWYU.h

+//===--- IWYU.h - Include-what-you-use 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 LLVM_CLANG_TOOLS_EXTRA_CLANGD_IWYU_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_IWYU_H
+
+#include "Headers.h"
+#include "ParsedAST.h"
+#include "clang/Basic/SourceLocation.h"
+#include "llvm/ADT/DenseSet.h"
+
+namespace clang {
+namespace clangd {
+
+struct ReferencedLocations {
+  llvm::DenseSet<SourceLocation> AllLocations;
+  llvm::DenseSet<llvm::StringRef> StandardLibraryHeaders;
+};
+ReferencedLocations findReferencedLocations(ParsedAST &AST);
+
+llvm::DenseSet<FileID>
+findReferencedFiles(const llvm::DenseSet<SourceLocation> &,
+                    const SourceManager &);
+
+inline llvm::DenseMap<unsigned, bool>
+directlyReferencedFiles(const IncludeStructure::AbstractIncludeGraph &Graph,
+                        llvm::DenseSet<unsigned> Referenced,
+                        unsigned EntryPoint) {
+  llvm::DenseMap<unsigned, bool> Result;
+  for (unsigned Inclusion : Graph.lookup(EntryPoint))
+    Result.try_emplace(Inclusion, Referenced.contains(Inclusion));
+  return Result;
+}
+
+} // namespace clangd
+} // namespace clang
+
+#endif

clang-tools-extra/clangd/IWYU.cpp

+//===--- IWYU.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 "IWYU.h"
+#include "support/Logger.h"
+#include "clang/AST/RecursiveASTVisitor.h"
+#include "clang/Basic/SourceLocation.h"
+
+namespace clang {
+namespace clangd {
+namespace {
+
+// If DC is a std namespace, returns e.g. "std::chrono".
+// If DC is top-level, returns "".
+// Else returns None.
+// Buf is used for storage if the namespace needs to be printed ('std' doesn't).
+llvm::Optional<llvm::StringRef> getStdNamespace(const DeclContext *DC,
+                                                std::string &Buf) {
+  const NamespaceDecl *FirstNamespace;
+  unsigned NamespaceCount = 0;
+  for (; !DC->isTranslationUnit(); DC = DC->getParent()) {
+    if (!DC->isTransparentContext()) {
+      if (DC->isNamespace()) {
+        if (!NamespaceCount)
+          FirstNamespace = cast<NamespaceDecl>(DC);
+        ++NamespaceCount;
+      } else {
+        return llvm::None;
+      }
+    }
+  }
+  if (!NamespaceCount)
+    return llvm::StringRef();
+  if (NamespaceCount == 1)
+    return FirstNamespace->getName();
+  Buf = printNamespaceScope(*FirstNamespace);
+  return llvm::StringRef(Buf).rtrim(":");
+}
+
+llvm::Optional<llvm::StringRef> getStdlibHeader(const NamedDecl &ND) {
+  log("looking up header for {0}", ND.getNameAsString());
+  const static auto &Lookup = [] {
+    // Lookup table is keyed first on the unqualified name, so we can bail out
+    // quickly without building strings if there's no match.
+    llvm::DenseMap</*Name*/ llvm::StringRef,
+                   llvm::SmallVector<std::pair</*Scope*/ llvm::StringRef,
+                                               /*Header*/ llvm::StringRef>>>
+        Result;
+#define SYMBOL(Name, Scope, Header) Result[#Name].emplace_back(#Scope, #Header);
+#include "CSymbolMap.inc"
+#include "StdSymbolMap.inc"
+#undef SYMBOL
+    for (auto &Unqual : Result)
+      for (auto &Qual : Unqual.second) {
+        // Swap "None" -> "", and "std::" -> "std", for easier lookup.
+        if (Qual.first == "None")
+          Qual.first = "";
+        else
+          Qual.first.consume_back("::");
+      }
+    return Result;
+  }();
+
+  // Bail out early in easy cases.
+  if (!ND.getDeclName().isIdentifier())
+    return llvm::None;
+  auto It = Lookup.find(ND.getName());
+  if (It == Lookup.end()) {
+    if (ND.getName() == "move" && ND.isInStdNamespace())
+
+      log("No match");
+    return llvm::None;
+  }
+
+  // OK, we have an unqualified name match. Does the namespace match?
+  std::string Buf;
+  auto NS = getStdNamespace(ND.getDeclContext(), Buf);
+  if (!NS)
+    return llvm::None;
+  log("with namespace {0}", *NS);
+  for (const auto &Pair : It->second)
+    if (*NS == Pair.first) {
+      log("found {0}", Pair.second);
+      return Pair.second;
+    }
+  return llvm::None;
+}
+
+class ReferencedLocationCrawler
+    : public RecursiveASTVisitor<ReferencedLocationCrawler> {
+  using Base = RecursiveASTVisitor<ReferencedLocationCrawler>;
+  llvm::DenseSet<const void *> Visited;
+  bool shouldAdd(const void *P) { return P && Visited.insert(P).second; }
+
+  void add(const Decl *D) {
+    if (!D || !shouldAdd(D->getCanonicalDecl()))
+      return;
+    for (const Decl *Redecl : D->redecls())
+      Result.AllLocations.insert(Redecl->getLocation());
+    if (const auto *ND = llvm::dyn_cast<NamedDecl>(D)) {
+      if (auto StdlibHeader = getStdlibHeader(*ND))
+        Result.StandardLibraryHeaders.insert(*StdlibHeader);
+      else if (ND->getDeclName().isIdentifier() && ND->getName() == "move" &&
+               ND->isInStdNamespace()) {
+        // Ugly special case: there are two `std::move`s.
+        const FunctionDecl *FD = ND->getAsFunction();
+        Result.StandardLibraryHeaders.insert(
+            FD && FD->getMinRequiredArguments() > 1 ? "<algorithm>"
+                                                    : "<utility>");
+      }
+    }
+  }
+
+public:
+  bool VisitDeclRefExpr(DeclRefExpr *DRE) {
+    add(DRE->getDecl());
+    add(DRE->getFoundDecl());
+    return true;
+  }
+
+  bool VisitMemberExpr(MemberExpr *ME) {
+    add(ME->getMemberDecl());
+    add(ME->getFoundDecl().getDecl());
+    return true;
+  }
+
+  bool VisitTagType(TagType *TT) {
+    add(TT->getDecl());
+    return true;
+  }
+
+  bool VisitCXXConstructExpr(CXXConstructExpr *CCE) {
+    add(CCE->getConstructor());
+    return true;
+  }
+
+  bool VisitTemplateSpecializationType(TemplateSpecializationType *TST) {
+    if (shouldAdd(TST)) {
+      add(TST->getTemplateName().getAsTemplateDecl()); // primary template
+      add(TST->getAsCXXRecordDecl());                  // specialization
+    }
+    return true;
+  }
+
+  bool VisitTypedefType(TypedefType *TT) {
+    add(TT->getDecl());
+    return true;
+  }
+
+#if 0
+  // Consider types of any subexpression used, even if the type is not named.
+  // This is helpful in getFoo().bar(), where Foo must be complete.
+  bool VisitExpr(Expr *E) {
+    TraverseType(E->getType());
+    return true;
+  }
+#endif
+
+  bool TraverseType(QualType T) {
+    if (shouldAdd(T.getTypePtrOrNull())) { // don't care about quals
+      Base::TraverseType(T);
+    }
+    return true;
+  }
+
+  ReferencedLocationCrawler(ReferencedLocations &Result) : Result(Result){};
+  ReferencedLocations &Result;
+};
+
+// Given a set of referenced FileIDs, determines all the potentially-referenced
+// files and macros by traversing expansion/spelling locations of macro IDs.
+// This is used to map the referenced SourceLocations onto real files.
+struct ReferencedFiles {
+  ReferencedFiles(const SourceManager &SM) : SM(SM) {}
+  llvm::DenseSet<FileID> Files;
+  llvm::DenseSet<FileID> Macros;
+  const SourceManager &SM;
+
+  void add(SourceLocation Loc) { add(SM.getFileID(Loc), Loc); }
+
+  void add(FileID FID, SourceLocation Loc) {
+    if (FID.isInvalid())
+      return;
+    assert(SM.isInFileID(Loc, FID));
+    if (Loc.isFileID()) {
+      Files.insert(FID);
+      return;
+    }
+    // Don't process the same macro FID twice.
+    if (!Macros.insert(FID).second)
+      return;
+    const auto &Exp = SM.getSLocEntry(FID).getExpansion();
+    add(Exp.getSpellingLoc());
+    add(Exp.getExpansionLocStart());
+    add(Exp.getExpansionLocEnd());
+  }
+};
+
+} // namespace
+
+ReferencedLocations findReferencedLocations(ParsedAST &AST) {
+  ReferencedLocations Result;
+  ReferencedLocationCrawler C(Result);
+  C.TraverseAST(AST.getASTContext());
+  // XXX macros
+  return Result;
+}
+
+llvm::DenseSet<FileID>
+findReferencedFiles(const llvm::DenseSet<SourceLocation> &Locs,
+                    const SourceManager &SM) {
+  std::vector<SourceLocation> Sorted{Locs.begin(), Locs.end()};
+  llvm::sort(Sorted); // This groups by FileID!
+  ReferencedFiles Result(SM);
+  for (auto It = Sorted.begin(); It < Sorted.end();) {
+    FileID FID = SM.getFileID(*It);
+    Result.add(FID, *It);
+    // Cheaply skip over all the other locations from the same FileID.
+    // This avoids lots of redundant Loc->File lookups for the same file.
+    do
+      ++It;
+    while (It != Sorted.end() && SM.isInFileID(*It, FID));
+  }
+  return std::move(Result.Files);
+}
+
+} // namespace clangd
+} // namespace clang

clang-tools-extra/clangd/ParsedAST.h

public:
   const SourceManager &getSourceManager() const {
     return getASTContext().getSourceManager();
   }
 
   const LangOptions &getLangOpts() const {
     return getASTContext().getLangOpts();
   }
 
+  void computeUsedIncludes();
+
   /// This function returns top-level decls present in the main file of the AST.
   /// The result does not include the decls that come from the preamble.
   /// (These should be const, but RecursiveASTVisitor requires Decl*).
   ArrayRef<Decl *> getLocalTopLevelDecls();
 
   const llvm::Optional<std::vector<Diag>> &getDiagnostics() const {
     return Diags;
   }

clang-tools-extra/clangd/ParsedAST.cpp

 #include "../clang-tidy/ClangTidyModuleRegistry.h"
 #include "AST.h"
 #include "Compiler.h"
 #include "Config.h"
 #include "Diagnostics.h"
 #include "FeatureModule.h"
 #include "Headers.h"
 #include "HeuristicResolver.h"
+#include "IWYU.h"
 #include "IncludeFixer.h"
 #include "Preamble.h"
 #include "SourceCode.h"
 #include "TidyProvider.h"
 #include "index/CanonicalIncludes.h"
 #include "index/Index.h"
 #include "support/Logger.h"
 #include "support/Trace.h"
if (Preamble)
       Diags->insert(Diags->end(), Preamble->Diags.begin(),
                     Preamble->Diags.end());
     // Finally, add diagnostics coming from the AST.
     {
       std::vector<Diag> D = ASTDiags.take(CTContext.getPointer());
       Diags->insert(Diags->end(), D.begin(), D.end());
     }
   }
-  return ParsedAST(Inputs.Version, std::move(Preamble), std::move(Clang),
+  ParsedAST Result(Inputs.Version, std::move(Preamble), std::move(Clang),
                    std::move(Action), std::move(Tokens), std::move(Macros),
                    std::move(ParsedDecls), std::move(Diags),
                    std::move(Includes), std::move(CanonIncludes));
+  // FIXME: Warn about missing includes.
+  if (Result.Diags) {
+    Result.computeUsedIncludes();
+    for (const auto &Include : Result.getIncludeStructure().MainFileIncludes) {
+      if (!Include.Used) {
+        Diag D;
+        D.Message = "Unused header";
+        D.Name = "clangd-unused-include";
+        D.Range.start.line = Include.HashLine;
+        D.Range.end.line = Include.HashLine + 1;
+        D.Fixes.emplace_back();
+        D.Fixes.back().Message = "Remove include";
+        D.Fixes.back().Edits.emplace_back();
+        D.Fixes.back().Edits.back().range = D.Range;
+        D.InsideMainFile = true;
+        D.File =
+            Result.getSourceManager()
+                .getFileEntryForID(Result.getSourceManager().getMainFileID())
+                ->getName()
+                .str();
+        D.Severity = DiagnosticsEngine::Warning;
+        Result.Diags->push_back(std::move(D));
+      }
+    }
+  }
+  return Result;
 }
 
 ParsedAST::ParsedAST(ParsedAST &&Other) = default;
 
 ParsedAST &ParsedAST::operator=(ParsedAST &&Other) = default;
 
 ParsedAST::~ParsedAST() {
   if (Action) {
ParsedAST::ParsedAST(llvm::StringRef Version,
   assert(this->Action);
 }
 
 llvm::Optional<llvm::StringRef> ParsedAST::preambleVersion() const {
   if (!Preamble)
     return llvm::None;
   return llvm::StringRef(Preamble->Version);
 }
+
+void ParsedAST::computeUsedIncludes() {
+  const auto &SM = getSourceManager();
+
+  auto Refs = findReferencedLocations(*this);
+  auto ReferencedFileIDs =
+      findReferencedFiles(Refs.AllLocations, getSourceManager());
+  std::vector<llvm::StringRef> ReferencedFilenames;
+  ReferencedFilenames.reserve(ReferencedFileIDs.size());
+  for (FileID FID : ReferencedFileIDs) {
+    const FileEntry *FE = SM.getFileEntryForID(FID);
+    if (!FE) {
+      elog("Missing FE for {0}", SM.getComposedLoc(FID, 0).printToString(SM));
+      continue;
+    }
+    ReferencedFilenames.push_back(SM.getFileEntryForID(FID)->getName());
+  }
+  Includes.markUsed(SM.getFileEntryForID(SM.getMainFileID())->getName(),
+                    ReferencedFilenames, Refs.StandardLibraryHeaders,
+                    directlyReferencedFiles);
+}
+
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/unittests/CMakeLists.txt

add_unittest(ClangdUnitTests ClangdTests
   FuzzyMatchTests.cpp
   GlobalCompilationDatabaseTests.cpp
   HeadersTests.cpp
   HeaderSourceSwitchTests.cpp
   HoverTests.cpp
   IndexActionTests.cpp
   IndexTests.cpp
   InlayHintTests.cpp
+  IWYUTests.cpp
   JSONTransportTests.cpp
   LoggerTests.cpp
   LSPBinderTests.cpp
   LSPClient.cpp
   ModulesTests.cpp
   ParsedASTTests.cpp
   PathMappingTests.cpp
   PreambleTests.cpp

clang-tools-extra/clangd/unittests/IWYUTests.cpp

+//===-- IWYUTests.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 "Annotations.h"
+#include "IWYU.h"
+#include "TestTU.h"
+#include "index/FileIndex.h"
+#include "index/Index.h"
+#include "index/MemIndex.h"
+#include "index/Merge.h"
+#include "index/Symbol.h"
+#include "clang/Index/IndexSymbol.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+namespace clang {
+namespace clangd {
+namespace {
+using testing::ElementsAreArray;
+
+TEST(ReferencedLocations, All) {
+  struct TestCase {
+    const char *HeaderCode;
+    const char *MainCode;
+  };
+  TestCase Cases[] = {{
+                          "int ^x();",
+                          "int y = x();",
+                      },
+                      {
+                          "class ^X;",
+                          "X *y;",
+                      },
+                      {
+                          "template <typename> class ^X;",
+                          "X<int> *y;",
+                      },
+                      {
+                          "using ^Integer = int;",
+                          "Integer x;",
+                      },
+                      {
+                          "struct X{int ^a;}; X ^foo();",
+                          "int y = foo().a;",
+                      },
+                      {
+                          "class ^X{}; X ^foo();",
+                          "auto bar() { return foo(); }",
+                      },
+                      {
+                          "class ^X; class ^X{}; class ^X;",
+                          "X *y;",
+                      },
+                      {
+                          // FIXME: should report the using decl too.
+                          // This information is not preserved in the AST.
+                          "namespace ns { class ^X; }; using ns::X;",
+                          "X *y;",
+                      }};
+  for (const TestCase &T : Cases) {
+    TestTU TU;
+    TU.Code = T.MainCode;
+    Annotations Header(T.HeaderCode);
+    TU.HeaderCode = Header.code().str();
+    auto AST = TU.build();
+
+    std::vector<Position> Points;
+    for (SourceLocation Loc : findReferencedLocations(AST).AllLocations) {
+      if (AST.getSourceManager().getBufferName(Loc).endswith(
+              TU.HeaderFilename)) {
+        Points.push_back(offsetToPosition(
+            TU.HeaderCode, AST.getSourceManager().getFileOffset(Loc)));
+      }
+    }
+    llvm::sort(Points);
+
+    EXPECT_EQ(Points, Header.points()) << T.HeaderCode << "\n---\n"
+                                       << T.MainCode;
+  }
+}
+
+TEST(ReferencedLocations, Stdlib) {
+  struct TestCase {
+    const char *HeaderCode;
+    const char *MainCode;
+    std::vector<std::string> StdlibHeaders;
+  };
+  TestCase Cases[] = {
+      {
+          "template<typename T, typename Allocator=int> class vector{};",
+          "std::vector<int> *x;",
+          {"<vector>"},
+      },
+      {
+          "namespace foo { class vector; }",
+          "std::foo::vector *x;",
+          {},
+      }};
+  for (const TestCase &T : Cases) {
+    TestTU TU;
+    TU.Code = T.MainCode;
+    TU.HeaderCode = std::string("namespace std {\n") + T.HeaderCode + "\n}";
+    auto AST = TU.build();
+
+    auto StdlibHeaders = findReferencedLocations(AST).StandardLibraryHeaders;
+    EXPECT_THAT(StdlibHeaders, ElementsAreArray(T.StdlibHeaders));
+  }
+}
+
+} // namespace
+} // namespace clangd
+} // namespace clang