[clangd] Basic IncludeCleaner support for c/c++ standard library

[sammccall]

Summary

There are some limitations here, so this is behind a flag for now (in addition
to the config setting for the overall feature).

• symbols without exactly one associated header aren't handled right
• no macro support
• referencing std::size_t usually doesn't leave any trace in the AST that the alias in std was used, so we associate with stddef.h instead of cstddef. (An AST issue not specific to stdlib, but much worse there)

[sammccall]

I can't remember how we discussed this offline, but my plan was to land this and address the limitations as followups rather than extend the scope of this patch.
So I think this is ready for review, though certainly not urgent.

[kbobyrev]

Mostly LG, few nits.

clang-tools-extra/clangd/Headers.h

35

Do we need a forward decl here?

46

nit: maybe mention the parameter name? it seems redundant but consistent with what we have around here.

76

What's the difference between header() and headers()? Without looking at the code below, I presume this is for symbols that could be defined in multiple headers?

345

maybe DenseMapInfo<unsigned>::getEmptyKey() and DenseMapInfo<unsigned>::getTombstoneKey() just like above?

clang-tools-extra/clangd/IncludeCleaner.cpp

155

Maybe pull this upstairs and use early return instead? It's either user code or Stdlib, so maybe add exclusively to one of the sets.

clang-tools-extra/clangd/IncludeCleaner.h

91

Not sure but: don't we want a config option instead? We can remove it just as easily since it's all "hidden" right now.

[sammccall]

(rebase before addressing comments)

[sammccall]

address comments

clang-tools-extra/clangd/Headers.h

35

Decl/NamespaceDecl are needed for the interface of the stdlib symbol recognizer, but we don't need to depend on any of the details of AST here.

Splitting the stdlib stuff into its own header seems possible if you'd prefer that?

345

empty/tombstone keys are reserved values, and we know what sensible reserved values are better than the traits for unsigned do.

I can fix the code above if you like.

clang-tools-extra/clangd/IncludeCleaner.h

91

I think we discussed this offline a bunch?

A config option is a bunch more plumbing, and we don't actually want to expose this option.

[kbobyrev]

LG with a nit, thanks!

clang-tools-extra/clangd/Headers.h

345

Okay, that makes sense! Yes, that would be great if you could fix the code above for consistency :)

clang-tools-extra/clangd/IncludeCleaner.h

91

Oh, right, thanks for reminding!

[thakis]

Breaks building on windows: http://45.33.8.238/win/51774/step_4.txt

Ptal!

[sammccall]

In D114077#3218006, @thakis wrote:

Breaks building on windows: http://45.33.8.238/win/51774/step_4.txt

Ptal!

Fixed (I think) in a61f34ea2502d900c57a332174d4c103b6963c80.
Clang successfully emulated MSVC's misunderstanding of the code :-(

clang-tools-extra/clangd/Headers.h

345

Done... yikes, the existing HeaderID empty key was zero... which is also the HeaderID for the main file!

Changed these to -1 and -2. Hopefully this is NFC, else maybe it fixed a scary bug...

[thakis]

Still broken on windows: http://45.33.8.238/win/51764/step_4.txt

[sammccall]

In D114077#3218446, @thakis wrote:

Still broken on windows: http://45.33.8.238/win/51764/step_4.txt

I think the builder is stuck, that build is some hours old and doesn't have the fix in it.
(Which leaves the possibility that i broke the bot somehow, I'm poking at some other bots trying to see if any of them are more broken than normal...)

[thakis]

Thanks for noticing that. It's back and happy now.

clang-tools-extra/clangd/Headers.h

 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/FileSystem/UniqueID.h"
 #include "llvm/Support/VirtualFileSystem.h"
 #include <string>
 
 namespace clang {
+class Decl;
+class NamespaceDecl;
 namespace clangd {
 
+// clangd has a built-in database of standard library symbols.
+namespace stdlib {
+
+// A standard library header, such as <iostream>
+// Lightweight class, in fact just an index into a table.
+class Header {
+public:
+  static llvm::Optional<Header> named(llvm::StringRef Name);
+
+  friend llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Header &H) {
+    return OS << H.name();
+  }
+  llvm::StringRef name() const;
+
+private:
+  Header(unsigned ID) : ID(ID) {}
+  unsigned ID;
+  friend class Symbol;
+  friend llvm::DenseMapInfo<Header>;
+  friend bool operator==(const Header &L, const Header &R) {
+    return L.ID == R.ID;
+  }
+};
+
+// A top-level standard library symbol, such as std::vector
+// Lightweight class, in fact just an index into a table.
+class Symbol {
+public:
+  static llvm::Optional<Symbol> named(llvm::StringRef Scope,
+                                      llvm::StringRef Name);
+
+  friend llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Symbol &S) {
+    return OS << S.scope() << S.name();
+  }
+  llvm::StringRef scope() const;
+  llvm::StringRef name() const;
+  // The preferred header for this symbol (e.g. the suggested insertion).
+  Header header() const;
+  // Some symbols may be provided my multiple headers.
+  llvm::SmallVector<Header> headers() const;
+
+private:
+  Symbol(unsigned ID) : ID(ID) {}
+  unsigned ID;
+  friend class Recognizer;
+  friend llvm::DenseMapInfo<Symbol>;
+  friend bool operator==(const Symbol &L, const Symbol &R) {
+    return L.ID == R.ID;
+  }
+};
+
+// A functor to find the stdlib::Symbol associated with a decl.
+//
+// For non-top-level decls (std::vector<int>::iterator), returns the top-level
+// symbol (std::vector).
+class Recognizer {
+public:
+  Recognizer();
+  llvm::Optional<Symbol> operator()(const Decl *D);
+
+private:
+  using NSSymbolMap = llvm::DenseMap<llvm::StringRef, unsigned>;
+  NSSymbolMap *namespaceSymbols(const NamespaceDecl *D);
+  llvm::DenseMap<const DeclContext *, NSSymbolMap *> NamespaceCache;
+};
+
+} // namespace stdlib
+
 /// Returns true if \p Include is literal include like "path" or <path>.
 bool isLiteralInclude(llvm::StringRef Include);
 
 /// Represents a header file to be #include'd.
 struct HeaderFile {
   std::string File;
   /// If this is true, `File` is a literal string quoted with <> or "" that
   /// can be #included directly; otherwise, `File` is an absolute file path.
public:
   // Root --> 0, #included file --> 1, etc.
   // Root is the ID of the header being visited first.
   llvm::DenseMap<HeaderID, unsigned>
   includeDepth(HeaderID Root = MainFileID) const;
 
   // Maps HeaderID to the ids of the files included from it.
   llvm::DenseMap<HeaderID, SmallVector<HeaderID>> IncludeChildren;
 
+  llvm::DenseMap<stdlib::Header, llvm::SmallVector<HeaderID>> StdlibHeaders;
+
   std::vector<Inclusion> MainFileIncludes;
 
   // We reserve HeaderID(0) for the main file and will manually check for that
   // in getID and getOrCreateID because the UniqueID is not stable when the
   // content of the main file changes.
   static const HeaderID MainFileID = HeaderID(0u);
 
   class RecordHeaders;

 } // namespace clangd
 } // namespace clang
 
 namespace llvm {
 
 // Support HeaderIDs as DenseMap keys.
 template <> struct DenseMapInfo<clang::clangd::IncludeStructure::HeaderID> {
   static inline clang::clangd::IncludeStructure::HeaderID getEmptyKey() {
-    return static_cast<clang::clangd::IncludeStructure::HeaderID>(
-        DenseMapInfo<unsigned>::getEmptyKey());
+    return static_cast<clang::clangd::IncludeStructure::HeaderID>(-1);
   }
 
   static inline clang::clangd::IncludeStructure::HeaderID getTombstoneKey() {
-    return static_cast<clang::clangd::IncludeStructure::HeaderID>(
-        DenseMapInfo<unsigned>::getTombstoneKey());
+    return static_cast<clang::clangd::IncludeStructure::HeaderID>(-2);
   }
 
   static unsigned
   getHashValue(const clang::clangd::IncludeStructure::HeaderID &Tag) {
     return hash_value(static_cast<unsigned>(Tag));
   }
 
   static bool isEqual(const clang::clangd::IncludeStructure::HeaderID &LHS,
                       const clang::clangd::IncludeStructure::HeaderID &RHS) {
     return LHS == RHS;
   }
 };
 
+template <> struct DenseMapInfo<clang::clangd::stdlib::Header> {
+  static inline clang::clangd::stdlib::Header getEmptyKey() {
+    return clang::clangd::stdlib::Header(-1);
+  }
+  static inline clang::clangd::stdlib::Header getTombstoneKey() {
+    return clang::clangd::stdlib::Header(-2);
+  }
+  static unsigned getHashValue(const clang::clangd::stdlib::Header &H) {
+    return hash_value(H.ID);
+  }
+  static bool isEqual(const clang::clangd::stdlib::Header &LHS,
+                      const clang::clangd::stdlib::Header &RHS) {
+    return LHS == RHS;
+  }
+};
+
+template <> struct DenseMapInfo<clang::clangd::stdlib::Symbol> {
+  static inline clang::clangd::stdlib::Symbol getEmptyKey() {
+    return clang::clangd::stdlib::Symbol(-1);
+  }
+  static inline clang::clangd::stdlib::Symbol getTombstoneKey() {
+    return clang::clangd::stdlib::Symbol(-2);
+  }
+  static unsigned getHashValue(const clang::clangd::stdlib::Symbol &S) {
+    return hash_value(S.ID);
+  }
+  static bool isEqual(const clang::clangd::stdlib::Symbol &LHS,
+                      const clang::clangd::stdlib::Symbol &RHS) {
+    return LHS == RHS;
+  }
+};
+
 } // namespace llvm
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_HEADERS_H

clang-tools-extra/clangd/Headers.cpp

if (isInsideMainFile(HashLoc, SM)) {
       Inc.Written =
           (IsAngled ? "<" + FileName + ">" : "\"" + FileName + "\"").str();
       Inc.Resolved = std::string(File ? File->tryGetRealPathName() : "");
       Inc.HashOffset = SM.getFileOffset(HashLoc);
       Inc.HashLine =
           SM.getLineNumber(SM.getFileID(HashLoc), Inc.HashOffset) - 1;
       Inc.FileKind = FileKind;
       Inc.Directive = IncludeTok.getIdentifierInfo()->getPPKeywordID();
-      if (File)
-        Inc.HeaderID = static_cast<unsigned>(Out->getOrCreateID(File));
       if (LastPragmaKeepInMainFileLine == Inc.HashLine)
         Inc.BehindPragmaKeep = true;
+      if (File) {
+        IncludeStructure::HeaderID HID = Out->getOrCreateID(File);
+        Inc.HeaderID = static_cast<unsigned>(HID);
+        if (IsAngled)
+          if (auto StdlibHeader = stdlib::Header::named(Inc.Written)) {
+            auto &IDs = Out->StdlibHeaders[*StdlibHeader];
+            // Few physical files for one stdlib header name, linear scan is ok.
+            if (!llvm::is_contained(IDs, HID))
+              IDs.push_back(HID);
+          }
+      }
     }
 
     // Record include graph (not just for main-file includes)
     if (File) {
       auto *IncludingFileEntry = SM.getFileEntryForID(SM.getFileID(HashLoc));
       if (!IncludingFileEntry) {
         assert(SM.getBufferName(HashLoc).startswith("<") &&
                "Expected #include location to be a file or <built-in>");

 }
 
 bool operator==(const Inclusion &LHS, const Inclusion &RHS) {
   return std::tie(LHS.Directive, LHS.FileKind, LHS.HashOffset, LHS.HashLine,
                   LHS.Resolved, LHS.Written) ==
          std::tie(RHS.Directive, RHS.FileKind, RHS.HashOffset, RHS.HashLine,
                   RHS.Resolved, RHS.Written);
 }
+
+namespace stdlib {
+static llvm::StringRef *HeaderNames;
+static std::pair<llvm::StringRef, llvm::StringRef> *SymbolNames;
+static unsigned *SymbolHeaderIDs;
+static llvm::DenseMap<llvm::StringRef, unsigned> *HeaderIDs;
+// Maps symbol name -> Symbol::ID, within a namespace.
+using NSSymbolMap = llvm::DenseMap<llvm::StringRef, unsigned>;
+static llvm::DenseMap<llvm::StringRef, NSSymbolMap *> *NamespaceSymbols;
+
+static int initialize() {
+  unsigned SymCount = 0;
+#define SYMBOL(Name, NS, Header) ++SymCount;
+#include "CSymbolMap.inc"
+#include "StdSymbolMap.inc"
+#undef SYMBOL
+  SymbolNames = new std::remove_reference_t<decltype(*SymbolNames)>[SymCount];
+  SymbolHeaderIDs =
+      new std::remove_reference_t<decltype(*SymbolHeaderIDs)>[SymCount];
+  NamespaceSymbols = new std::remove_reference_t<decltype(*NamespaceSymbols)>;
+  HeaderIDs = new std::remove_reference_t<decltype(*HeaderIDs)>;
+
+  auto AddNS = [&](llvm::StringRef NS) -> NSSymbolMap & {
+    auto R = NamespaceSymbols->try_emplace(NS, nullptr);
+    if (R.second)
+      R.first->second = new NSSymbolMap();
+    return *R.first->second;
+  };
+
+  auto AddHeader = [&](llvm::StringRef Header) -> unsigned {
+    return HeaderIDs->try_emplace(Header, HeaderIDs->size()).first->second;
+  };
+
+  auto Add = [&, SymIndex(0)](llvm::StringRef Name, llvm::StringRef NS,
+                              llvm::StringRef HeaderName) mutable {
+    if (NS == "None")
+      NS = "";
+
+    SymbolNames[SymIndex] = {NS, Name};
+    SymbolHeaderIDs[SymIndex] = AddHeader(HeaderName);
+
+    NSSymbolMap &NSSymbols = AddNS(NS);
+    NSSymbols.try_emplace(Name, SymIndex);
+
+    ++SymIndex;
+  };
+#define SYMBOL(Name, NS, Header) Add(#Name, #NS, #Header);
+#include "CSymbolMap.inc"
+#include "StdSymbolMap.inc"
+#undef SYMBOL
+
+  HeaderNames = new llvm::StringRef[HeaderIDs->size()];
+  for (const auto &E : *HeaderIDs)
+    HeaderNames[E.second] = E.first;
+
+  return 0;
+}
+
+static void ensureInitialized() {
+  static int Dummy = initialize();
+  (void)Dummy;
+}
+
+llvm::Optional<Header> Header::named(llvm::StringRef Name) {
+  ensureInitialized();
+  auto It = HeaderIDs->find(Name);
+  if (It == HeaderIDs->end())
+    return llvm::None;
+  return Header(It->second);
+}
+llvm::StringRef Header::name() const { return HeaderNames[ID]; }
+llvm::StringRef Symbol::scope() const { return SymbolNames[ID].first; }
+llvm::StringRef Symbol::name() const { return SymbolNames[ID].second; }
+llvm::Optional<Symbol> Symbol::named(llvm::StringRef Scope,
+                                     llvm::StringRef Name) {
+  ensureInitialized();
+  if (NSSymbolMap *NSSymbols = NamespaceSymbols->lookup(Scope)) {
+    auto It = NSSymbols->find(Name);
+    if (It != NSSymbols->end())
+      return Symbol(It->second);
+  }
+  return llvm::None;
+}
+Header Symbol::header() const { return Header(SymbolHeaderIDs[ID]); }
+llvm::SmallVector<Header> Symbol::headers() const {
+  return {header()}; // FIXME: multiple in case of ambiguity
+}
+
+Recognizer::Recognizer() { ensureInitialized(); }
+
+NSSymbolMap *Recognizer::namespaceSymbols(const NamespaceDecl *D) {
+  auto It = NamespaceCache.find(D);
+  if (It != NamespaceCache.end())
+    return It->second;
+
+  NSSymbolMap *Result = [&]() -> NSSymbolMap * {
+    if (!D) // Nullptr means the global namespace
+      return NamespaceSymbols->lookup("");
+    if (D->isAnonymousNamespace())
+      return nullptr;
+    if (D->isInlineNamespace()) {
+      if (auto *Parent = llvm::dyn_cast_or_null<NamespaceDecl>(D->getParent()))
+        return namespaceSymbols(Parent);
+      return nullptr;
+    }
+    return NamespaceSymbols->lookup(printNamespaceScope(*D));
+  }();
+  NamespaceCache.try_emplace(D, Result);
+  return Result;
+}
+
+llvm::Optional<Symbol> Recognizer::operator()(const Decl *D) {
+  // If D is std::vector::iterator, `vector` is the outer symbol to look up.
+  // We keep all the candidate DCs as some may turn out to be anon enums.
+  // Do this resolution lazily as we may turn out not to have a std namespace.
+  llvm::SmallVector<const DeclContext *> IntermediateDecl;
+  const DeclContext *DC = D->getDeclContext();
+  while (DC && !DC->isNamespace()) {
+    if (NamedDecl::classofKind(DC->getDeclKind()))
+      IntermediateDecl.push_back(DC);
+    DC = DC->getParent();
+  }
+  NSSymbolMap *Symbols = namespaceSymbols(cast_or_null<NamespaceDecl>(DC));
+  if (!Symbols)
+    return llvm::None;
+
+  llvm::StringRef Name = [&]() -> llvm::StringRef {
+    for (const auto *SymDC : llvm::reverse(IntermediateDecl)) {
+      DeclarationName N = cast<NamedDecl>(SymDC)->getDeclName();
+      if (const auto *II = N.getAsIdentifierInfo())
+        return II->getName();
+      if (!N.isEmpty())
+        return ""; // e.g. operator<: give up
+    }
+    if (const auto *ND = llvm::dyn_cast<NamedDecl>(D))
+      if (const auto *II = ND->getIdentifier())
+        return II->getName();
+    return "";
+  }();
+  if (Name.empty())
+    return llvm::None;
+
+  auto It = Symbols->find(Name);
+  if (It == Symbols->end())
+    return llvm::None;
+  return Symbol(It->second);
+}
+
+} // namespace stdlib
+
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/IncludeCleaner.h

 #include "ParsedAST.h"
 #include "clang/Basic/SourceLocation.h"
 #include "llvm/ADT/DenseSet.h"
 #include <vector>
 
 namespace clang {
 namespace clangd {
 
-using ReferencedLocations = llvm::DenseSet<SourceLocation>;
+struct ReferencedLocations {
+  llvm::DenseSet<SourceLocation> User;
+  llvm::DenseSet<stdlib::Symbol> Stdlib;
+};
+
 /// Finds locations of all symbols used in the main file.
 ///
 /// - RecursiveASTVisitor finds references to symbols and records their
 ///   associated locations. These may be macro expansions, and are not resolved
 ///   to their spelling or expansion location. These locations are later used to
 ///   determine which headers should be marked as "used" and "directly used".
 /// - We also examine all identifier tokens in the file in case they reference
 ///   macros.
 ///
 /// We use this to compute unused headers, so we:
 ///
 /// - cover the whole file in a single traversal for efficiency
 /// - don't attempt to describe where symbols were referenced from in
 ///   ambiguous cases (e.g. implicitly used symbols, multiple declarations)
 /// - err on the side of reporting all possible locations
 ReferencedLocations findReferencedLocations(ParsedAST &AST);
 
+struct ReferencedFiles {
+  llvm::DenseSet<FileID> User;
+  llvm::DenseSet<stdlib::Header> Stdlib;
+};
+
 /// Retrieves IDs of all files containing SourceLocations from \p Locs.
 /// The output only includes things SourceManager sees as files (not macro IDs).
 /// This can include <built-in>, <scratch space> etc that are not true files.
-llvm::DenseSet<FileID> findReferencedFiles(const ReferencedLocations &Locs,
-                                           const IncludeStructure &Includes,
-                                           const SourceManager &SM);
+ReferencedFiles findReferencedFiles(const ReferencedLocations &Locs,
 
 /// Maps FileIDs to the internal IncludeStructure representation (HeaderIDs).
 /// FileIDs that are not true files (<built-in> etc) are dropped.
 llvm::DenseSet<IncludeStructure::HeaderID>
-translateToHeaderIDs(const llvm::DenseSet<FileID> &Files,
+translateToHeaderIDs(const ReferencedFiles &Files,
                      const IncludeStructure &Includes, const SourceManager &SM);
 
 /// Retrieves headers that are referenced from the main file but not used.
 /// In unclear cases, headers are not marked as unused.
 std::vector<const Inclusion *>
 getUnused(ParsedAST &AST,
           const llvm::DenseSet<IncludeStructure::HeaderID> &ReferencedFiles);
 
 std::vector<const Inclusion *> computeUnusedIncludes(ParsedAST &AST);
 
 std::vector<Diag> issueUnusedIncludesDiagnostics(ParsedAST &AST,
                                                  llvm::StringRef Code);
 
+/// Affects whether standard library includes should be considered for removal.
+/// This is off by default for now due to implementation limitations:
+/// - macros are not tracked
+/// - symbol names without a unique associated header are not tracked
+/// - references to std-namespaced C types are not properly tracked:
+///   instead of std::size_t -> <cstddef> we see ::size_t -> <stddef.h>
+/// FIXME: remove this hack once the implementation is good enough.
+void setIncludeCleanerAnalyzesStdlib(bool B);
+
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INCLUDECLEANER_H

clang-tools-extra/clangd/IncludeCleaner.cpp

 #include "clang/Lex/HeaderSearch.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Tooling/Syntax/Tokens.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/Path.h"
 
 namespace clang {
 namespace clangd {
+
+static bool AnalyzeStdlib = false;
+void setIncludeCleanerAnalyzesStdlib(bool B) { AnalyzeStdlib = B; }
+
 namespace {
 
 /// Crawler traverses the AST and feeds in the locations of (sometimes
 /// implicitly) used symbols into \p Result.
 class ReferencedLocationCrawler
     : public RecursiveASTVisitor<ReferencedLocationCrawler> {
 public:
   ReferencedLocationCrawler(ReferencedLocations &Result,
public:
   }
 
 private:
   using Base = RecursiveASTVisitor<ReferencedLocationCrawler>;
 
   void add(const Decl *D) {
     if (!D || !isNew(D->getCanonicalDecl()))
       return;
+    if (auto SS = StdRecognizer(D)) {
+      Result.Stdlib.insert(*SS);
+      return;
+    }
     // Special case RecordDecls, as it is common for them to be forward
     // declared multiple times. The most common cases are:
     // - Definition available in TU, only mark that one as usage. The rest is
     //   likely to be unnecessary. This might result in false positives when an
     //   internal definition is visible.
     // - There's a forward declaration in the main file, no need for other
     //   redecls.
     if (const auto *RD = llvm::dyn_cast<RecordDecl>(D)) {
       if (const auto *Definition = RD->getDefinition()) {
-        Result.insert(Definition->getLocation());
+        Result.User.insert(Definition->getLocation());
         return;
       }
       if (SM.isInMainFile(RD->getMostRecentDecl()->getLocation()))
         return;
     }
     for (const Decl *Redecl : D->redecls())
-      Result.insert(Redecl->getLocation());
+      Result.User.insert(Redecl->getLocation());
   }
 
   bool isNew(const void *P) { return P && Visited.insert(P).second; }
 
   ReferencedLocations &Result;
   llvm::DenseSet<const void *> Visited;
   const SourceManager &SM;
+  stdlib::Recognizer StdRecognizer;
 };
 
 // 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) {}
+struct ReferencedFilesBuilder {
+  ReferencedFilesBuilder(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())
void findReferencedMacros(ParsedAST &AST, ReferencedLocations &Result) {
   // relying on MainFileMacros.
   for (const syntax::Token &Tok :
        AST.getTokens().spelledTokens(SM.getMainFileID())) {
     auto Macro = locateMacroAt(Tok, PP);
     if (!Macro)
       continue;
     auto Loc = Macro->Info->getDefinitionLoc();
     if (Loc.isValid())
-      Result.insert(Loc);
+      Result.User.insert(Loc);
+    // FIXME: support stdlib macros
   }
 }
 
-bool mayConsiderUnused(const Inclusion &Inc, ParsedAST &AST) {
+static bool mayConsiderUnused(const Inclusion &Inc, ParsedAST &AST) {
+  if (Inc.BehindPragmaKeep)
+    return false;
+
   // FIXME(kirillbobyrev): We currently do not support the umbrella headers.
-  // Standard Library headers are typically umbrella headers, and system
-  // headers are likely to be the Standard Library headers. Until we have a
-  // good support for umbrella headers and Standard Library headers, don't warn
-  // about them.
-  if (Inc.Written.front() == '<' || Inc.BehindPragmaKeep)
+  // System headers are likely to be standard library headers.
+  // Until we have good support for umbrella headers, don't warn about them.
+  if (Inc.Written.front() == '<') {
+    if (AnalyzeStdlib && stdlib::Header::named(Inc.Written))
+      return true;
     return false;
+  }
   // Headers without include guards have side effects and are not
   // self-contained, skip them.
   assert(Inc.HeaderID);
   auto FE = AST.getSourceManager().getFileManager().getFile(
       AST.getIncludeStructure().getRealPath(
           static_cast<IncludeStructure::HeaderID>(*Inc.HeaderID)));
   assert(FE);
   if (!AST.getPreprocessor().getHeaderSearchInfo().isFileMultipleIncludeGuarded(
ReferencedLocations findReferencedLocations(ParsedAST &AST) {
   trace::Span Tracer("IncludeCleaner::findReferencedLocations");
   ReferencedLocations Result;
   ReferencedLocationCrawler Crawler(Result, AST.getSourceManager());
   Crawler.TraverseAST(AST.getASTContext());
   findReferencedMacros(AST, Result);
   return Result;
 }
 
-llvm::DenseSet<FileID>
-findReferencedFiles(const llvm::DenseSet<SourceLocation> &Locs,
-                    const IncludeStructure &Includes, const SourceManager &SM) {
-  std::vector<SourceLocation> Sorted{Locs.begin(), Locs.end()};
+ReferencedFiles findReferencedFiles(const ReferencedLocations &Locs,
+                                    const IncludeStructure &Includes,
+                                    const SourceManager &SM) {
+  std::vector<SourceLocation> Sorted{Locs.User.begin(), Locs.User.end()};
   llvm::sort(Sorted); // Group by FileID.
-  ReferencedFiles Files(SM);
+  ReferencedFilesBuilder Builder(SM);
   for (auto It = Sorted.begin(); It < Sorted.end();) {
     FileID FID = SM.getFileID(*It);
-    Files.add(FID, *It);
+    Builder.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));
   }
+
   // If a header is not self-contained, we consider its symbols a logical part
   // of the including file. Therefore, mark the parents of all used
   // non-self-contained FileIDs as used. Perform this on FileIDs rather than
   // HeaderIDs, as each inclusion of a non-self-contained file is distinct.
-  llvm::DenseSet<FileID> Result;
-  for (FileID ID : Files.Files)
-    Result.insert(headerResponsible(ID, SM, Includes));
-  return Result;
+  llvm::DenseSet<FileID> UserFiles;
+  for (FileID ID : Builder.Files)
+    UserFiles.insert(headerResponsible(ID, SM, Includes));
+
+  llvm::DenseSet<stdlib::Header> StdlibFiles;
+  for (const auto &Symbol : Locs.Stdlib)
+    for (const auto &Header : Symbol.headers())
+      StdlibFiles.insert(Header);
+
+  return {std::move(UserFiles), std::move(StdlibFiles)};
 }
 
 std::vector<const Inclusion *>
 getUnused(ParsedAST &AST,
           const llvm::DenseSet<IncludeStructure::HeaderID> &ReferencedFiles) {
   trace::Span Tracer("IncludeCleaner::getUnused");
   std::vector<const Inclusion *> Unused;
   for (const Inclusion &MFI : AST.getIncludeStructure().MainFileIncludes) {

 // Is FID a <built-in>, <scratch space> etc?
 static bool isSpecialBuffer(FileID FID, const SourceManager &SM) {
   const SrcMgr::FileInfo &FI = SM.getSLocEntry(FID).getFile();
   return FI.getName().startswith("<");
 }
 #endif
 
 llvm::DenseSet<IncludeStructure::HeaderID>
-translateToHeaderIDs(const llvm::DenseSet<FileID> &Files,
+translateToHeaderIDs(const ReferencedFiles &Files,
                      const IncludeStructure &Includes,
                      const SourceManager &SM) {
   trace::Span Tracer("IncludeCleaner::translateToHeaderIDs");
   llvm::DenseSet<IncludeStructure::HeaderID> TranslatedHeaderIDs;
-  TranslatedHeaderIDs.reserve(Files.size());
-  for (FileID FID : Files) {
+  TranslatedHeaderIDs.reserve(Files.User.size());
+  for (FileID FID : Files.User) {
     const FileEntry *FE = SM.getFileEntryForID(FID);
     if (!FE) {
       assert(isSpecialBuffer(FID, SM));
       continue;
     }
     const auto File = Includes.getID(FE);
     assert(File);
     TranslatedHeaderIDs.insert(*File);
   }
+  for (stdlib::Header StdlibUsed : Files.Stdlib)
+    for (auto HID : Includes.StdlibHeaders.lookup(StdlibUsed))
+      TranslatedHeaderIDs.insert(HID);
   return TranslatedHeaderIDs;
 }
 
 std::vector<const Inclusion *> computeUnusedIncludes(ParsedAST &AST) {
   const auto &SM = AST.getSourceManager();
 
   auto Refs = findReferencedLocations(AST);
   auto ReferencedFileIDs = findReferencedFiles(Refs, AST.getIncludeStructure(),

clang-tools-extra/clangd/tool/ClangdMain.cpp

 //===--- ClangdMain.cpp - clangd server loop ------------------------------===//
 //
 // 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 "ClangdLSPServer.h"
 #include "CodeComplete.h"
 #include "Compiler.h"
 #include "Config.h"
 #include "ConfigProvider.h"
 #include "Feature.h"
+#include "IncludeCleaner.h"
 #include "PathMapping.h"
 #include "Protocol.h"
 #include "TidyProvider.h"
 #include "Transport.h"
 #include "index/Background.h"
 #include "index/Index.h"
 #include "index/Merge.h"
 #include "index/ProjectAware.h"
values(
                    "Insert the owning header for top-level symbols, unless the "
                    "header is already directly included or the symbol is "
                    "forward-declared"),
         clEnumValN(
             CodeCompleteOptions::NeverInsert, "never",
             "Never insert #include directives as part of code completion")),
 };
 
+opt<bool> IncludeCleanerStdlib{
+    "include-cleaner-stdlib",
+    cat(Features),
+    desc("Apply include-cleaner analysis to standard library headers "
+         "(immature!)"),
+    init(false),
+    Hidden,
+};
+
 opt<bool> HeaderInsertionDecorators{
     "header-insertion-decorators",
     cat(Features),
     desc("Prepend a circular dot or space before the completion "
          "label, depending on whether "
          "an include line will be inserted or not"),
     init(true),
 };
Opts.TweakFilter = [&](const Tweak &T) {
     if (T.hidden() && !HiddenFeatures)
       return false;
     if (TweakList.getNumOccurrences())
       return llvm::is_contained(TweakList, T.id());
     return true;
   };
   if (ForceOffsetEncoding != OffsetEncoding::UnsupportedEncoding)
     Opts.Encoding = ForceOffsetEncoding;
+  setIncludeCleanerAnalyzesStdlib(IncludeCleanerStdlib);
 
   if (CheckFile.getNumOccurrences()) {
     llvm::SmallString<256> Path;
     if (auto Error =
             llvm::sys::fs::real_path(CheckFile, Path, /*expand_tilde=*/true)) {
       elog("Failed to resolve path {0}: {1}", CheckFile, Error.message());
       return 1;
     }

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

 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Frontend/CompilerInvocation.h"
 #include "clang/Frontend/FrontendActions.h"
 #include "clang/Lex/PreprocessorOptions.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/Path.h"
+#include "llvm/Support/ScopedPrinter.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 namespace clang {
 namespace clangd {
 namespace {
 
 using ::testing::AllOf;
)cpp";
 
   auto Includes = collectIncludes();
   EXPECT_TRUE(Includes.isSelfContained(getID("pragmaguarded.h", Includes)));
   EXPECT_TRUE(Includes.isSelfContained(getID("includeguarded.h", Includes)));
   EXPECT_FALSE(Includes.isSelfContained(getID("nonguarded.h", Includes)));
   EXPECT_FALSE(Includes.isSelfContained(getID("pp_depend.h", Includes)));
 }
 
+TEST(StdlibTest, All) {
+  auto VectorH = stdlib::Header::named("<vector>");
+  EXPECT_TRUE(VectorH);
+  EXPECT_EQ(llvm::to_string(*VectorH), "<vector>");
+  EXPECT_FALSE(stdlib::Header::named("HeadersTests.cpp"));
+
+  auto Vector = stdlib::Symbol::named("std::", "vector");
+  EXPECT_TRUE(Vector);
+  EXPECT_EQ(llvm::to_string(*Vector), "std::vector");
+  EXPECT_FALSE(stdlib::Symbol::named("std::", "dongle"));
+  EXPECT_FALSE(stdlib::Symbol::named("clang::", "ASTContext"));
+
+  EXPECT_EQ(Vector->header(), *VectorH);
+  EXPECT_THAT(Vector->headers(), ElementsAre(*VectorH));
+}
+
+TEST(StdlibTest, Recognizer) {
+  auto TU = TestTU::withCode(R"cpp(
+    namespace std {
+    inline namespace inl {
+
+    template <typename>
+    struct vector { class nested {}; };
+
+    class secret {};
+
+    } // inl
+    } // std
+
+    class vector {};
+    std::vector<int> vec;
+    std::vector<int>::nested nest;
+    std::secret sec;
+  )cpp");
+
+  auto AST = TU.build();
+  auto &vector_nonstd = findDecl(AST, "vector");
+  auto *vec =
+      cast<VarDecl>(findDecl(AST, "vec")).getType()->getAsCXXRecordDecl();
+  auto *nest =
+      cast<VarDecl>(findDecl(AST, "nest")).getType()->getAsCXXRecordDecl();
+  auto *sec =
+      cast<VarDecl>(findDecl(AST, "sec")).getType()->getAsCXXRecordDecl();
+
+  stdlib::Recognizer recognizer;
+
+  EXPECT_EQ(recognizer(&vector_nonstd), llvm::None);
+  EXPECT_EQ(recognizer(vec), stdlib::Symbol::named("std::", "vector"));
+  EXPECT_EQ(recognizer(nest), stdlib::Symbol::named("std::", "vector"));
+  EXPECT_EQ(recognizer(sec), llvm::None);
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang

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

 //===--- IncludeCleanerTests.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 "IncludeCleaner.h"
+#include "SourceCode.h"
 #include "TestTU.h"
+#include "llvm/ADT/ScopeExit.h"
 #include "llvm/Testing/Support/SupportHelpers.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 namespace clang {
 namespace clangd {
 namespace {
 
 using ::testing::ElementsAre;
+using ::testing::ElementsAreArray;
 using ::testing::IsEmpty;
+using ::testing::Pointee;
 using ::testing::UnorderedElementsAre;
 
 std::string guard(llvm::StringRef Code) {
   return "#pragma once\n" + Code.str();
 }
 
 TEST(IncludeCleaner, ReferencedLocations) {
   struct TestCase {
TEST(IncludeCleaner, ReferencedLocations) {
   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 (const auto &Loc : findReferencedLocations(AST)) {
+    for (const auto &Loc : findReferencedLocations(AST).User) {
       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(IncludeCleaner, Stdlib) {
+  // Smoke tests only for finding used symbols/headers.
+  // Details of Decl -> stdlib::Symbol -> stdlib::Headers mapping tested there.
+  auto TU = TestTU::withHeaderCode(R"cpp(
+    namespace std { class error_code {}; }
+    class error_code {};
+    namespace nonstd { class error_code {}; }
+  )cpp");
+  struct {
+    llvm::StringRef Code;
+    std::vector<llvm::StringRef> Symbols;
+    std::vector<llvm::StringRef> Headers;
+  } Tests[] = {
+      {"std::error_code x;", {"std::error_code"}, {"<system_error>"}},
+      {"error_code x;", {}, {}},
+      {"nonstd::error_code x;", {}, {}},
+  };
+
+  for (const auto &Test : Tests) {
+    TU.Code = Test.Code.str();
+    ParsedAST AST = TU.build();
+    std::vector<stdlib::Symbol> WantSyms;
+    for (const auto &SymName : Test.Symbols) {
+      auto QName = splitQualifiedName(SymName);
+      auto Sym = stdlib::Symbol::named(QName.first, QName.second);
+      EXPECT_TRUE(Sym) << SymName;
+      WantSyms.push_back(*Sym);
+    }
+    std::vector<stdlib::Header> WantHeaders;
+    for (const auto &HeaderName : Test.Headers) {
+      auto Header = stdlib::Header::named(HeaderName);
+      EXPECT_TRUE(Header) << HeaderName;
+      WantHeaders.push_back(*Header);
+    }
+
+    ReferencedLocations Locs = findReferencedLocations(AST);
+    EXPECT_THAT(Locs.Stdlib, ElementsAreArray(WantSyms));
+    ReferencedFiles Files = findReferencedFiles(Locs, AST.getIncludeStructure(),
+                                                AST.getSourceManager());
+    EXPECT_THAT(Files.Stdlib, ElementsAreArray(WantHeaders));
+  }
+}
+
+MATCHER_P(WrittenInclusion, Written, "") {
+  if (arg.Written != Written)
+    *result_listener << arg.Written;
+  return arg.Written == Written;
+}
+
+TEST(IncludeCleaner, StdlibUnused) {
+  setIncludeCleanerAnalyzesStdlib(true);
+  auto Cleanup =
+      llvm::make_scope_exit([] { setIncludeCleanerAnalyzesStdlib(false); });
+
+  auto TU = TestTU::withCode(R"cpp(
+    #include <list>
+    #include <queue>
+    std::list<int> x;
+  )cpp");
+  // Layout of std library impl is not relevant.
+  TU.AdditionalFiles["bits"] = R"cpp(
+    #pragma once
+    namespace std {
+      template <typename> class list {};
+      template <typename> class queue {};
+    }
+  )cpp";
+  TU.AdditionalFiles["list"] = "#include <bits>";
+  TU.AdditionalFiles["queue"] = "#include <bits>";
+  TU.ExtraArgs = {"-isystem", testRoot()};
+  auto AST = TU.build();
+
+  auto Unused = computeUnusedIncludes(AST);
+  EXPECT_THAT(Unused, ElementsAre(Pointee(WrittenInclusion("<queue>"))));
+}
+
 TEST(IncludeCleaner, GetUnusedHeaders) {
   llvm::StringLiteral MainFile = R"cpp(
     #include "a.h"
     #include "b.h"
     #include "dir/c.h"
     #include "dir/unused.h"
     #include "unguarded.h"
     #include "unused.h"
TEST(IncludeCleaner, VirtualBuffers) {
   TU.ExtraArgs = {"-DCLI=42"};
   ParsedAST AST = TU.build();
   auto &SM = AST.getSourceManager();
   auto &Includes = AST.getIncludeStructure();
 
   auto ReferencedFiles =
       findReferencedFiles(findReferencedLocations(AST), Includes, SM);
   llvm::StringSet<> ReferencedFileNames;
-  for (FileID FID : ReferencedFiles)
+  for (FileID FID : ReferencedFiles.User)
     ReferencedFileNames.insert(
         SM.getPresumedLoc(SM.getLocForStartOfFile(FID)).getFilename());
   // Note we deduped the names as _number_ of <built-in>s is uninteresting.
   EXPECT_THAT(ReferencedFileNames.keys(),
               UnorderedElementsAre("<built-in>", "<scratch space>",
                                    testPath("macros.h")));
 
   // Should not crash due to FileIDs that are not headers.
TEST(IncludeCleaner, DistinctUnguardedInclusions) {
 
   ParsedAST AST = TU.build();
 
   auto ReferencedFiles =
       findReferencedFiles(findReferencedLocations(AST),
                           AST.getIncludeStructure(), AST.getSourceManager());
   llvm::StringSet<> ReferencedFileNames;
   auto &SM = AST.getSourceManager();
-  for (FileID FID : ReferencedFiles)
+  for (FileID FID : ReferencedFiles.User)
     ReferencedFileNames.insert(
         SM.getPresumedLoc(SM.getLocForStartOfFile(FID)).getFilename());
   // Note that we have uplifted the referenced files from non self-contained
   // headers to header-guarded ones.
   EXPECT_THAT(ReferencedFileNames.keys(),
               UnorderedElementsAre(testPath("foo.h")));
 }
 
TEST(IncludeCleaner, NonSelfContainedHeaders) {
 
   ParsedAST AST = TU.build();
 
   auto ReferencedFiles =
       findReferencedFiles(findReferencedLocations(AST),
                           AST.getIncludeStructure(), AST.getSourceManager());
   llvm::StringSet<> ReferencedFileNames;
   auto &SM = AST.getSourceManager();
-  for (FileID FID : ReferencedFiles)
+  for (FileID FID : ReferencedFiles.User)
     ReferencedFileNames.insert(
         SM.getPresumedLoc(SM.getLocForStartOfFile(FID)).getFilename());
   // Note that we have uplifted the referenced files from non self-contained
   // headers to header-guarded ones.
   EXPECT_THAT(ReferencedFileNames.keys(),
               UnorderedElementsAre(testPath("foo.h")));
 }
 
 TEST(IncludeCleaner, IWYUPragmas) {
   TestTU TU;
   TU.Code = R"cpp(
     #include "behind_keep.h" // IWYU pragma: keep
     )cpp";
   TU.AdditionalFiles["behind_keep.h"] = guard("");
   ParsedAST AST = TU.build();
 
   auto ReferencedFiles =
       findReferencedFiles(findReferencedLocations(AST),
                           AST.getIncludeStructure(), AST.getSourceManager());
-  EXPECT_TRUE(ReferencedFiles.empty());
+  EXPECT_TRUE(ReferencedFiles.User.empty());
   EXPECT_THAT(AST.getDiagnostics(), llvm::ValueIs(IsEmpty()));
 }
 
 } // namespace
 } // namespace clangd
 } // namespace clang