unused header prototype

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/CompileCommands.h

 //===--- CompileCommands.h - Manipulation of compile flags -------*- 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_COMPILECOMMANDS_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_COMPILECOMMANDS_H
 
 #include "support/Threading.h"
 #include "clang/Tooling/ArgumentsAdjusters.h"
-#include "clang/Tooling/CompilationDatabase.h"
 #include "llvm/ADT/StringMap.h"
 #include <deque>
 #include <string>
 #include <vector>
 
 namespace clang {
 namespace clangd {
 

clang-tools-extra/clangd/Compiler.cpp

 //===--- Compiler.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 "Compiler.h"
 #include "support/Logger.h"
 #include "clang/Basic/TargetInfo.h"
 #include "clang/Lex/PreprocessorOptions.h"
 #include "clang/Serialization/PCHContainerOperations.h"
 #include "llvm/ADT/StringRef.h"
-#include "llvm/Support/Format.h"
-#include "llvm/Support/FormatVariadic.h"
 
 namespace clang {
 namespace clangd {
 
 void IgnoreDiagnostics::log(DiagnosticsEngine::Level DiagLevel,
                             const clang::Diagnostic &Info) {
   // FIXME: format lazily, in case vlog is off.
   llvm::SmallString<64> Message;

clang-tools-extra/clangd/ConfigCompile.cpp

 #include "support/Logger.h"
 #include "support/Path.h"
 #include "support/Trace.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringRef.h"
-#include "llvm/ADT/StringSwitch.h"
-#include "llvm/Support/Error.h"
 #include "llvm/Support/FileSystem.h"
-#include "llvm/Support/Format.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/Regex.h"
 #include "llvm/Support/SMLoc.h"
 #include "llvm/Support/SourceMgr.h"
 #include <string>
 
 namespace clang {

clang-tools-extra/clangd/ConfigFragment.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_CONFIGFRAGMENT_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_CONFIGFRAGMENT_H
 
 #include "ConfigProvider.h"
 #include "llvm/ADT/Optional.h"
-#include "llvm/ADT/STLExtras.h"
-#include "llvm/Support/Error.h"
 #include "llvm/Support/SMLoc.h"
 #include "llvm/Support/SourceMgr.h"
 #include <string>
 #include <vector>
 
 namespace clang {
 namespace clangd {
 namespace config {

clang-tools-extra/clangd/ConfigProvider.h

 //  - specifying different settings for different files
 // This file defines the structures used for this, that produce a Config.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_CONFIGPROVIDER_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_CONFIGPROVIDER_H
 
-#include "llvm/ADT/FunctionExtras.h"
 #include "llvm/ADT/StringRef.h"
-#include "llvm/Support/SMLoc.h"
 #include "llvm/Support/SourceMgr.h"
 #include <chrono>
 #include <string>
 #include <vector>
 
 namespace clang {
 namespace clangd {
 struct Config;

clang-tools-extra/clangd/ConfigYAML.cpp

 //===--- ConfigYAML.cpp - Loading configuration fragments from YAML files -===//
 //
 // 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 "ConfigFragment.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/SourceMgr.h"
 #include "llvm/Support/YAMLParser.h"
 #include <string>
 #include <system_error>
 
 namespace clang {

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>,
+                                     2>>
+        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/ClangTidyDiagnosticConsumer.h"
 #include "../clang-tidy/ClangTidyModuleRegistry.h"
 #include "AST.h"
 #include "Compiler.h"
 #include "Config.h"
 #include "Diagnostics.h"
 #include "FeatureModule.h"
 #include "Headers.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));
+  // For now, we only surface used includes as diagnostics.
+  if (Result.Diags) {
+    Result.computeUsedIncludes();
+    for (const auto &Inc : Result.getIncludeStructure().MainFileIncludes) {
+      if (!Inc.Used) {
+        Diag D;
+        D.Message = "included header is unused";
+        D.Name = "clangd-unused-include";
+        D.Range.start.line = Inc.HashLine;
+        D.Range.end.line = Inc.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
   FSTests.cpp
   FuzzyMatchTests.cpp
   GlobalCompilationDatabaseTests.cpp
   HeadersTests.cpp
   HeaderSourceSwitchTests.cpp
   HoverTests.cpp
   IndexActionTests.cpp
   IndexTests.cpp
+<<<<<<< HEAD
   InlayHintTests.cpp
+=======
+  IWYUTests.cpp
+>>>>>>> 7cd8eece296e (iwyu xxx)
   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