[clangd] NFC: Move stdlib headers handling to Clang

[kbobyrev]

Summary

This will allow moving the IncludeCleaner library essentials to Clang
and decoupling them from the majority of clangd.

The patch itself just moves the code, it doesn't change existing
functionality.

[sammccall]

The moved *.inc files are generated, the generator needs to be moved (and updated?) too I think.

Is having clangd continue to include the .inc files textually intended to stay that way, or is it a FIXME?

[sammccall]

This looks sensible to me, but as I wrote this code we should maybe get a second look (@kadircet?) that it makes sense to lift to clang::tooling.

Some positive experience: we've used it successfully in an internal clang-tidy check.

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

411–412

Recognizer test also needs to be moved

clang/include/clang/Tooling/Inclusions/StandardLibrary.h

2

This needs a copyright header and a file comment

8

namespace tooling { namespace stdlib {

14

what's the design around C vs C++?

e.g. are std::printf and ::printf distinct symbols, are C printf and C++ ::printf distinct symbols, similarly for headers.

(Fine if only C++ is implemented here, but the interface should probably say one way or the other)

In clangd we had a handle on all the callers, but here we have to worry about acquiring callers that e.g. can't easily provide language information.

clang/lib/Tooling/Inclusions/StandardLibrary.cpp

111

if D is std::chrono I think it just returns "chrono"?

(we should probably have a Recognizer test for this, sorry I left it out...)

[kbobyrev]

Move include-mapping generators to clang and re-generate the files.

[kadircet]

Regarding the include mapping generator, I think it would've been better if we had some sort of list directly from libc++ (as this is now being part of clang rather than just clangd), but having the current symbol mapping available for other tools too is definitely a useful improvement and implementation details can change later on.
I think we should have some "more public" documentation available around the limitations of current generator though, so that people are not surprised and aware of the caveats (like symbols might be missing, or in case of ambiguity they might be dropped, etc). Not sure where that belongs though, maybe header of the .inc file, or if we want it to be only used through the recognizer interface, maybe we can make the inc file "private" and document it there.

As for stdlib symbol/header/recognizer, I've got a couple questions around the functionality we are exposing:

• (briefly mentioned above) should we just make raw symbol mappings an implementation detail of stdlib recognizer and have applications depend on it?
• do we want headers/symbols to be created outside of the recognizer?

clang/include/clang/Tooling/Inclusions/StandardLibrary.h

16

can you clarify if Name can have quotes/angles ?

38

should scope have trailing :: ?

47

s/my/by

67

what about macros?

[kbobyrev]

Address review comments.

clang/include/clang/Tooling/Inclusions/StandardLibrary.h

38

This is consistent with the current behavior; we can probably change it later.

67

For now, I'm just moving the code without adding any new capabilities. The only change is in namespaceSymbols (to break the dependency on clangd helpers) that Sam pointed out.

[kbobyrev]

In D119130#3300780, @kadircet wrote:

Regarding the include mapping generator, I think it would've been better if we had some sort of list directly from libc++ (as this is now being part of clang rather than just clangd), but having the current symbol mapping available for other tools too is definitely a useful improvement and implementation details can change later on.
I think we should have some "more public" documentation available around the limitations of current generator though, so that people are not surprised and aware of the caveats (like symbols might be missing, or in case of ambiguity they might be dropped, etc). Not sure where that belongs though, maybe header of the .inc file, or if we want it to be only used through the recognizer interface, maybe we can make the inc file "private" and document it there.

As for stdlib symbol/header/recognizer, I've got a couple questions around the functionality we are exposing:

• (briefly mentioned above) should we just make raw symbol mappings an implementation detail of stdlib recognizer and have applications depend on it?
• do we want headers/symbols to be created outside of the recognizer?

Right, I agree that using libc++ directly would be better, but for now this just makes the functionality public. We can change it and update as we want afterwards.

[sammccall]

clang/include/clang/Tooling/Inclusions/StandardLibrary.h

38

Please document the behavior that's being added here.

(In clangd, "scope" fairly consistently includes "::" - I don't think that convention exists here)

57

I'm not sure what "the callers have to act accordingly..." means - can you drop it or elaborate?

67

Please add a mention of macros to the docs.

clang/lib/Tooling/Inclusions/StandardLibrary.cpp

120

Does this do the right thing for std::__1::chrono where __1 is inline?

clang/unittests/Tooling/StandardLibraryTest.cpp

62

should there be symbols in this NS and a test for them?

[kbobyrev]

Address the comments.

[kbobyrev]

Add a comment for the helper function.

[kbobyrev]

Fix the tests.

[kbobyrev]

Oh, and also regarding the Python generator scripts: they don't seem to work with the latest archives :( 2018 mentioned in the docs (works perfectly) but 2019 crashes. Probably not very relevant if we switch to libc++ eventually.

[kbobyrev]

Fix the test.

[sammccall]

In D119130#3304505, @kbobyrev wrote:

Oh, and also regarding the Python generator scripts: they don't seem to work with the latest archives :( 2018 mentioned in the docs (works perfectly) but 2019 crashes.

Yikes, we should fix that. Especially since the 2019 version is 3 years out of date already...

Probably not very relevant if we switch to libc++ eventually.

This seems pretty unlikely to me.

[sammccall]

clang/unittests/Tooling/StandardLibraryTest.cpp

51

maybe add a test for a C symbol?

[kbobyrev]

Add a test for C Standard Library symbol.

[kbobyrev]

In D119130#3307222, @sammccall wrote:

In D119130#3304505, @kbobyrev wrote:

Oh, and also regarding the Python generator scripts: they don't seem to work with the latest archives :( 2018 mentioned in the docs (works perfectly) but 2019 crashes.

Yikes, we should fix that. Especially since the 2019 version is 3 years out of date already...

Agreed! Though, the other problem is that it seems that nothing beyond 2019 version really exists. Which means that even if we support that one, it's unlikely to be up-to-date. For us to be relatively up-to-date we might need to ask someone working on cppreference for new archives and the format is likely to be different from 2019, too, so I don't know if we should fix the issue now vs. try to get newer archives and fix the issue after that.

Probably not very relevant if we switch to libc++ eventually.

This seems pretty unlikely to me.

[paulwalker-arm]

After this commit I am seeing the link time error

ld.lld: error: undefined symbol: clang::DeclContext::isInlineNamespace() const
>>> referenced by StandardLibrary.cpp:118 (/home/pmw/projects/upstream-llvm/llvm-project/clang/lib/Tooling/Inclusions/StandardLibrary.cpp:118)
>>>               tools/clang/lib/Tooling/Inclusions/CMakeFiles/obj.clangToolingInclusions.dir/StandardLibrary.cpp.o:(clang::tooling::stdlib::Recognizer::namespaceSymbols(clang::NamespaceDecl const*)::'lambda'()::operator()() const)

ld.lld: error: undefined symbol: clang::Decl::castFromDeclContext(clang::DeclContext const*)
>>> referenced by DeclBase.h:2562 (/home/pmw/projects/upstream-llvm/llvm-project/clang/include/clang/AST/DeclBase.h:2562)
>>>               tools/clang/lib/Tooling/Inclusions/CMakeFiles/obj.clangToolingInclusions.dir/StandardLibrary.cpp.o:(clang::cast_convert_decl_context<clang::Decl, false>::doit(clang::DeclContext*))
>>> referenced by DeclBase.h:2558 (/home/pmw/projects/upstream-llvm/llvm-project/clang/include/clang/AST/DeclBase.h:2558)
>>>               tools/clang/lib/Tooling/Inclusions/CMakeFiles/obj.clangToolingInclusions.dir/StandardLibrary.cpp.o:(clang::cast_convert_decl_context<clang::NamedDecl, false>::doit(clang::DeclContext const*))

If I revert this commit it goes away. I've tried a fresh cmake and build and get the same result.

[kbobyrev]

In D119130#3307333, @paulwalker-arm wrote:

After this commit I am seeing the link time error

ld.lld: error: undefined symbol: clang::DeclContext::isInlineNamespace() const
>>> referenced by StandardLibrary.cpp:118 (/home/pmw/projects/upstream-llvm/llvm-project/clang/lib/Tooling/Inclusions/StandardLibrary.cpp:118)
>>>               tools/clang/lib/Tooling/Inclusions/CMakeFiles/obj.clangToolingInclusions.dir/StandardLibrary.cpp.o:(clang::tooling::stdlib::Recognizer::namespaceSymbols(clang::NamespaceDecl const*)::'lambda'()::operator()() const)

ld.lld: error: undefined symbol: clang::Decl::castFromDeclContext(clang::DeclContext const*)
>>> referenced by DeclBase.h:2562 (/home/pmw/projects/upstream-llvm/llvm-project/clang/include/clang/AST/DeclBase.h:2562)
>>>               tools/clang/lib/Tooling/Inclusions/CMakeFiles/obj.clangToolingInclusions.dir/StandardLibrary.cpp.o:(clang::cast_convert_decl_context<clang::Decl, false>::doit(clang::DeclContext*))
>>> referenced by DeclBase.h:2558 (/home/pmw/projects/upstream-llvm/llvm-project/clang/include/clang/AST/DeclBase.h:2558)
>>>               tools/clang/lib/Tooling/Inclusions/CMakeFiles/obj.clangToolingInclusions.dir/StandardLibrary.cpp.o:(clang::cast_convert_decl_context<clang::NamedDecl, false>::doit(clang::DeclContext const*))

If I revert this commit it goes away. I've tried a fresh cmake and build and get the same result.

Thanks for reporting! This should be fixed in https://github.com/llvm/llvm-project/commit/e3ba831937189ec61e28ced0b0bfc1e41a3510f8, your issue looks the same I found in a failing buildbot; could you please try again and let me know if it's still broken?

[paulwalker-arm]

Yep, that did the trick. Many Thanks.

[thakis]

This makes clang-format depend on clang's AST library (because Format depends on Tooling/Inclusions, and this makes Tooling/Inclusions depend on AST), which it shouldn't.

Could this move into a dedicated library, or in some library that Format doesn't depend on?

[thakis]

Or, alternatively, maybe Recognizer could stay in clangd (or move to a separate lib); looks like that's the only thing in StandardLibrary.h that needs clang/AST/Decl.h.

[ilya-biryukov]

In D119130#3829816, @thakis wrote:

This makes clang-format depend on clang's AST library

Oops, definitely an unintended outcome.
Ping @kadircet, in case he missed this. He should know best who can fix this.

[kadircet]

yeah sorry for the mess here. i agree that we should move StandardLibrary to its own library. i'll try to take a stab at this tomorrow, if no one does it before then.

[kadircet]

sent out https://reviews.llvm.org/D135245

clang-tools-extra/clangd/Headers.h

 #include "clang/Basic/FileEntry.h"
 #include "clang/Basic/TokenKinds.h"
 #include "clang/Format/Format.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Lex/HeaderSearch.h"
 #include "clang/Lex/PPCallbacks.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Tooling/Inclusions/HeaderIncludes.h"
+#include "clang/Tooling/Inclusions/StandardLibrary.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseSet.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 {
-class Symbol;
-
-// 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 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;
+  llvm::DenseMap<tooling::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);
 
template <> struct DenseMapInfo<clang::clangd::IncludeStructure::HeaderID> {
   }
 
   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.FileKind = FileKind;
       Inc.Directive = IncludeTok.getIdentifierInfo()->getPPKeywordID();
       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)) {
+          if (auto StdlibHeader = tooling::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);
           }
       }
     }
 

 
 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

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INCLUDECLEANER_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INCLUDECLEANER_H
 
 #include "Headers.h"
 #include "ParsedAST.h"
 #include "clang/Basic/SourceLocation.h"
+#include "clang/Tooling/Inclusions/StandardLibrary.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/STLFunctionalExtras.h"
 #include <vector>
 
 namespace clang {
 namespace clangd {
 
 struct ReferencedLocations {
   llvm::DenseSet<SourceLocation> User;
-  llvm::DenseSet<stdlib::Symbol> Stdlib;
+  llvm::DenseSet<tooling::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".
 /// - If \p Tokens is not nullptr, we also examine all identifier tokens in the
 ///   file in case they reference macros 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(const SourceManager &SM,
                                             ASTContext &Ctx, Preprocessor &PP,
                                             const syntax::TokenBuffer *Tokens);
 ReferencedLocations findReferencedLocations(ParsedAST &AST);
 
 struct ReferencedFiles {
   llvm::DenseSet<FileID> User;
-  llvm::DenseSet<stdlib::Header> Stdlib;
+  llvm::DenseSet<tooling::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.
 /// \p HeaderResponsible returns the public header that should be included given
 /// symbols from a file with the given FileID (example: public headers should be
 /// preferred to non self-contained and private headers).

clang-tools-extra/clangd/IncludeCleaner.cpp

for (const Decl *Redecl : D->redecls())
       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;
+  tooling::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 ReferencedFilesBuilder {
   ReferencedFilesBuilder(const SourceManager &SM) : SM(SM) {}
   llvm::DenseSet<FileID> Files;

 static bool mayConsiderUnused(const Inclusion &Inc, ParsedAST &AST) {
   if (Inc.BehindPragmaKeep)
     return false;
 
   // FIXME(kirillbobyrev): We currently do not support the umbrella headers.
   // 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))
+    if (AnalyzeStdlib && tooling::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(
findReferencedFiles(const ReferencedLocations &Locs, const SourceManager &SM,
   // 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> UserFiles;
   for (FileID ID : Builder.Files)
     UserFiles.insert(HeaderResponsible(ID));
 
-  llvm::DenseSet<stdlib::Header> StdlibFiles;
+  llvm::DenseSet<tooling::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)};
 }
 
 ReferencedFiles findReferencedFiles(const ReferencedLocations &Locs,
for (FileID FID : Files.User) {
     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 (tooling::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();
 

clang-tools-extra/clangd/index/CanonicalIncludes.cpp

collectIWYUHeaderMaps(CanonicalIncludes *Includes) {
   };
   return std::make_unique<PragmaCommentHandler>(Includes);
 }
 
 void CanonicalIncludes::addSystemHeadersMapping(const LangOptions &Language) {
   if (Language.CPlusPlus) {
     static const auto *Symbols = new llvm::StringMap<llvm::StringRef>({
 #define SYMBOL(Name, NameSpace, Header) {#NameSpace #Name, #Header},
-#include "StdSymbolMap.inc"
+#include "clang/Tooling/Inclusions/StdSymbolMap.inc"
         // There are two std::move()s, this is by far the most common.
         SYMBOL(move, std::, <utility>)
         // There are multiple headers for size_t, pick one.
         SYMBOL(size_t, std::, <cstddef>)
 #undef SYMBOL
     });
     StdSymbolMapping = Symbols;
   } else if (Language.C11) {
     static const auto *CSymbols = new llvm::StringMap<llvm::StringRef>({
 #define SYMBOL(Name, NameSpace, Header) {#Name, #Header},
-#include "CSymbolMap.inc"
+#include "clang/Tooling/Inclusions/CSymbolMap.inc"
         // There are multiple headers for size_t, pick one.
         SYMBOL(size_t, None, <stddef.h>)
 #undef SYMBOL
     });
     StdSymbolMapping = CSymbols;
   }
 
   // FIXME: remove the std header mapping once we support ambiguous symbols, now

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

 )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 &VectorNonstd = 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(&VectorNonstd), 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

std::vector<llvm::StringRef> Headers;
       {"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;
+    std::vector<tooling::stdlib::Symbol> WantSyms;
     for (const auto &SymName : Test.Symbols) {
       auto QName = splitQualifiedName(SymName);
-      auto Sym = stdlib::Symbol::named(QName.first, QName.second);
+      auto Sym = tooling::stdlib::Symbol::named(QName.first, QName.second);
       EXPECT_TRUE(Sym) << SymName;
       WantSyms.push_back(*Sym);
     }
-    std::vector<stdlib::Header> WantHeaders;
+    std::vector<tooling::stdlib::Header> WantHeaders;
     for (const auto &HeaderName : Test.Headers) {
-      auto Header = stdlib::Header::named(HeaderName);
+      auto Header = tooling::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());

clang/include/clang/Tooling/Inclusions/CSymbolMap.inc

 //===-- gen_std.py generated file -------------------------------*- C++ -*-===//
 //
 // Used to build a lookup table (qualified names => include headers) for C
 // Standard Library symbols.
 //
-// Automatically generated file, DO NOT EDIT!
+// This file was generated automatically by
+// clang/tools/include-mapping/gen_std.py, DO NOT EDIT!
 //
 // Generated from cppreference offline HTML book (modified on 2018-10-28).
 //===----------------------------------------------------------------------===//
 
 SYMBOL(ATOMIC_BOOL_LOCK_FREE, None, <stdatomic.h>)
 SYMBOL(ATOMIC_CHAR16_T_LOCK_FREE, None, <stdatomic.h>)
 SYMBOL(ATOMIC_CHAR32_T_LOCK_FREE, None, <stdatomic.h>)
 SYMBOL(ATOMIC_CHAR_LOCK_FREE, None, <stdatomic.h>)

clang/include/clang/Tooling/Inclusions/StandardLibrary.h

+//===--- StandardLibrary.h --------------------------------------*- 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
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// Provides an interface for querying information about C and C++ Standard
+/// Library headers and symbols.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLING_INCLUSIONS_STANDARDLIBRARY_H
+#define LLVM_CLANG_TOOLING_INCLUSIONS_STANDARDLIBRARY_H
+
+#include "clang/AST/Decl.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/raw_ostream.h"
+#include <string>
+
+namespace clang {
+namespace tooling {
+namespace stdlib {
+
+class Symbol;
+
+// A standard library header, such as <iostream>
+// Lightweight class, in fact just an index into a table.
+// C++ and C Library compatibility headers are considered different: e.g.
+// "<cstdio>" and "<stdio.h>" (and their symbols) are treated differently.
+class Header {
+public:
+  // Name should contain the angle brackets, e.g. "<vector>".
+  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 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.
+// C++ and C Standard Library symbols are considered distinct: e.g. std::printf
+// and ::printf are not treated as the same symbol.
+// The symbols do not contain macros right now, we don't have a reliable index
+// for them.
+class Symbol {
+public:
+  /// \p Scope should have the trailing "::", for example:
+  /// named("std::chrono::", "system_clock")
+  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 by 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
+} // namespace tooling
+} // namespace clang
+
+namespace llvm {
+
+template <> struct DenseMapInfo<clang::tooling::stdlib::Header> {
+  static inline clang::tooling::stdlib::Header getEmptyKey() {
+    return clang::tooling::stdlib::Header(-1);
+  }
+  static inline clang::tooling::stdlib::Header getTombstoneKey() {
+    return clang::tooling::stdlib::Header(-2);
+  }
+  static unsigned getHashValue(const clang::tooling::stdlib::Header &H) {
+    return hash_value(H.ID);
+  }
+  static bool isEqual(const clang::tooling::stdlib::Header &LHS,
+                      const clang::tooling::stdlib::Header &RHS) {
+    return LHS == RHS;
+  }
+};
+
+template <> struct DenseMapInfo<clang::tooling::stdlib::Symbol> {
+  static inline clang::tooling::stdlib::Symbol getEmptyKey() {
+    return clang::tooling::stdlib::Symbol(-1);
+  }
+  static inline clang::tooling::stdlib::Symbol getTombstoneKey() {
+    return clang::tooling::stdlib::Symbol(-2);
+  }
+  static unsigned getHashValue(const clang::tooling::stdlib::Symbol &S) {
+    return hash_value(S.ID);
+  }
+  static bool isEqual(const clang::tooling::stdlib::Symbol &LHS,
+                      const clang::tooling::stdlib::Symbol &RHS) {
+    return LHS == RHS;
+  }
+};
+} // namespace llvm
+
+#endif // LLVM_CLANG_TOOLING_INCLUSIONS_STANDARDLIBRARY_H

clang/include/clang/Tooling/Inclusions/StdSymbolMap.inc

 //===-- gen_std.py generated file -------------------------------*- C++ -*-===//
 //
 // Used to build a lookup table (qualified names => include headers) for CPP
 // Standard Library symbols.
 //
-// Automatically generated file, DO NOT EDIT!
+// This file was generated automatically by
+// clang/tools/include-mapping/gen_std.py, DO NOT EDIT!
 //
 // Generated from cppreference offline HTML book (modified on 2018-10-28).
 //===----------------------------------------------------------------------===//
 
 SYMBOL(Assignable, std::, <concepts>)
 SYMBOL(Boolean, std::, <concepts>)
 SYMBOL(Common, std::, <concepts>)
 SYMBOL(CommonReference, std::, <concepts>)

clang/lib/Tooling/Inclusions/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS support)
 
 add_clang_library(clangToolingInclusions
   HeaderIncludes.cpp
   IncludeStyle.cpp
+  StandardLibrary.cpp
 
   LINK_LIBS
   clangBasic
   clangLex
   clangRewrite
   clangToolingCore
   )

clang/lib/Tooling/Inclusions/StandardLibrary.cpp

+//===--- StandardLibrary.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 "clang/Tooling/Inclusions/StandardLibrary.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Casting.h"
+
+namespace clang {
+namespace tooling {
+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 "clang/Tooling/Inclusions/CSymbolMap.inc"
+#include "clang/Tooling/Inclusions/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 "clang/Tooling/Inclusions/CSymbolMap.inc"
+#include "clang/Tooling/Inclusions/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 && D->isAnonymousNamespace())
+      return nullptr;
+    // Print the namespace and its parents ommitting inline scopes.
+    std::string Scope;
+    for (const auto *ND = D; ND;
+         ND = llvm::dyn_cast_or_null<NamespaceDecl>(ND->getParent()))
+      if (!ND->isInlineNamespace() && !ND->isAnonymousNamespace())
+        Scope = ND->getName().str() + "::" + Scope;
+    return NamespaceSymbols->lookup(Scope);
+  }();
+  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 tooling
+} // namespace clang

clang/tools/include-mapping/gen_std.py

 #!/usr/bin/env python
 #===- gen_std.py -  ------------------------------------------*- python -*--===#
 #
 # 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
 #
 #===------------------------------------------------------------------------===#
 
 """gen_std.py is a tool to generate a lookup table (from qualified names to
 include headers) for C/C++ Standard Library symbols by parsing archieved HTML
 files from cppreference.
 
+The generated files are located in clang/include/Tooling/Inclusions.
+
 Caveats and FIXMEs:
   - only symbols directly in "std" namespace are added, we should also add std's
     subnamespace symbols (e.g. chrono).
   - symbols with multiple variants or defined in multiple headers aren't added,
     e.g. std::move, std::swap
 
 Usage:
   1. Install BeautifulSoup dependency, see instruction:

 import sys
 
 CODE_PREFIX = """\
 //===-- gen_std.py generated file -------------------------------*- C++ -*-===//
 //
 // Used to build a lookup table (qualified names => include headers) for %s
 // Standard Library symbols.
 //
-// Automatically generated file, DO NOT EDIT!
+// This file was generated automatically by
+// clang/tools/include-mapping/gen_std.py, DO NOT EDIT!
 //
 // Generated from cppreference offline HTML book (modified on %s).
 //===----------------------------------------------------------------------===//
 """
 
 def ParseArg():
   parser = argparse.ArgumentParser(description='Generate StdGen file')
   parser.add_argument('-cppreference', metavar='PATH',

clang/unittests/Tooling/CMakeLists.txt

add_clang_unittest(ToolingTests
   CastExprTest.cpp
   CommentHandlerTest.cpp
   CompilationDatabaseTest.cpp
   DependencyScannerTest.cpp
   DiagnosticsYamlTest.cpp
   ExecutionTest.cpp
   FixItTest.cpp
   HeaderIncludesTest.cpp
+  StandardLibraryTest.cpp
   LexicallyOrderedRecursiveASTVisitorTest.cpp
   LookupTest.cpp
   QualTypeNamesTest.cpp
   RangeSelectorTest.cpp
   RecursiveASTVisitorTests/Attr.cpp
   RecursiveASTVisitorTests/CallbacksLeaf.cpp
   RecursiveASTVisitorTests/CallbacksUnaryOperator.cpp
   RecursiveASTVisitorTests/CallbacksBinaryOperator.cpp

clang/unittests/Tooling/StandardLibraryTest.cpp

+//===- unittest/Tooling/StandardLibrary.cpp -------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Tooling/Inclusions/StandardLibrary.h"
+#include "clang/AST/Decl.h"
+#include "clang/AST/DeclarationName.h"
+#include "clang/Frontend/ASTUnit.h"
+#include "clang/Tooling/Tooling.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/ScopedPrinter.h"
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+using ::testing::ElementsAre;
+
+namespace clang {
+namespace tooling {
+namespace {
+
+const NamedDecl &lookup(ASTUnit &AST, llvm::StringRef Name) {
+  auto &Ctx = AST.getASTContext();
+  TranslationUnitDecl *TU = Ctx.getTranslationUnitDecl();
+  auto Result = TU->lookup(DeclarationName(&Ctx.Idents.get(Name)));
+  assert(!Result.empty() && "Lookup failed");
+  assert(Result.isSingleResult() && "Lookup returned multiple results");
+  return *Result.front();
+}
+
+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) {
+  std::unique_ptr<ASTUnit> AST = buildASTFromCode(R"cpp(
+    namespace std {
+    inline namespace inl {
+
+    template <typename>
+    struct vector { class nested {}; };
+
+    class secret {};
+
+    } // inl
+
+    inline namespace __1 {
+      namespace chrono {
+        inline namespace chrono_inl {
+        class system_clock {};
+        } // chrono_inl
+      } // chrono
+    } // __1
+
+    } // std
+
+    // C Standard Library structure defined in <stdlib.h>
+    struct div_t {};
+
+    class vector {};
+    std::vector<int> vec;
+    std::vector<int>::nested nest;
+    std::secret sec;
+    std::chrono::system_clock clock;
+
+    div_t div;
+  )cpp");
+
+  auto &VectorNonstd = lookup(*AST, "vector");
+  auto *Vec =
+      cast<VarDecl>(lookup(*AST, "vec")).getType()->getAsCXXRecordDecl();
+  auto *Nest =
+      cast<VarDecl>(lookup(*AST, "nest")).getType()->getAsCXXRecordDecl();
+  auto *Clock =
+      cast<VarDecl>(lookup(*AST, "clock")).getType()->getAsCXXRecordDecl();
+  auto *Sec =
+      cast<VarDecl>(lookup(*AST, "sec")).getType()->getAsCXXRecordDecl();
+  auto *CDivT =
+      cast<VarDecl>(lookup(*AST, "div")).getType()->getAsCXXRecordDecl();
+
+  stdlib::Recognizer Recognizer;
+
+  EXPECT_EQ(Recognizer(&VectorNonstd), llvm::None);
+  EXPECT_EQ(Recognizer(Vec), stdlib::Symbol::named("std::", "vector"));
+  EXPECT_EQ(Recognizer(Nest), stdlib::Symbol::named("std::", "vector"));
+  EXPECT_EQ(Recognizer(Clock),
+            stdlib::Symbol::named("std::chrono::", "system_clock"));
+  EXPECT_EQ(Recognizer(CDivT), stdlib::Symbol::named("", "div_t"));
+  EXPECT_EQ(Recognizer(Sec), llvm::None);
+}
+
+} // namespace
+} // namespace tooling
+} // namespace clang