[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

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

15

can you clarify if Name can have quotes/angles ?

37

should scope have trailing :: ?

46

s/my/by

66

what about macros?

[kbobyrev]

Address review comments.

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

37

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

66

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

37

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?

66

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

 
 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/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 {};

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

+#include "clang/AST/Decl.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/raw_ostream.h"
+
+namespace clang {
+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
+} // namespace clang
+
+namespace llvm {
+
+template <> struct DenseMapInfo<clang::stdlib::Header> {
+  static inline clang::stdlib::Header getEmptyKey() {
+    return clang::stdlib::Header(-1);
+  }
+  static inline clang::stdlib::Header getTombstoneKey() {
+    return clang::stdlib::Header(-2);
+  }
+  static unsigned getHashValue(const clang::stdlib::Header &H) {
+    return hash_value(H.ID);
+  }
+  static bool isEqual(const clang::stdlib::Header &LHS,
+                      const clang::stdlib::Header &RHS) {
+    return LHS == RHS;
+  }
+};
+
+template <> struct DenseMapInfo<clang::stdlib::Symbol> {
+  static inline clang::stdlib::Symbol getEmptyKey() {
+    return clang::stdlib::Symbol(-1);
+  }
+  static inline clang::stdlib::Symbol getTombstoneKey() {
+    return clang::stdlib::Symbol(-2);
+  }
+  static unsigned getHashValue(const clang::stdlib::Symbol &S) {
+    return hash_value(S.ID);
+  }
+  static bool isEqual(const clang::stdlib::Symbol &LHS,
+                      const clang::stdlib::Symbol &RHS) {
+    return LHS == RHS;
+  }
+};
+} // namespace llvm

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

+#include "clang/Tooling/Inclusions/StandardLibrary.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/StringRef.h"
+
+namespace clang {
+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) // Nullptr means the global namespace
+      return NamespaceSymbols->lookup("");
+    if (D->isAnonymousNamespace())
+      return nullptr;
+    // Get namespace symbols for the first non-inline parent.
+    if (D->isInlineNamespace())
+      if (auto *Parent = llvm::dyn_cast_or_null<NamespaceDecl>(D->getParent()))
+        return namespaceSymbols(Parent);
+    return NamespaceSymbols->lookup((D->getName() + "::").str());
+  }();
+  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 clang

clang/tools/include-mapping/cppreference_parser.py

 #!/usr/bin/env python
 #===- cppreference_parser.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
 #
 #===------------------------------------------------------------------------===#
 
 from bs4 import BeautifulSoup, NavigableString
 
 import collections
 import multiprocessing
 import os
 import re
 import signal
 import sys
 
 
 class Symbol:
 
   def __init__(self, name, namespace, headers):
     # unqualifed symbol name, e.g. "move"
     self.name = name
     # namespace of the symbol (with trailing "::"), e.g. "std::", "" (global scope)
     # None for C symbols.
     self.namespace = namespace
     # a list of corresponding headers
     self.headers = headers
 
 
 def _HasClass(tag, *classes):
   for c in tag.get('class', []):
     if c in classes:
       return True
   return False
 
 
 def _ParseSymbolPage(symbol_page_html, symbol_name):
   """Parse symbol page and retrieve the include header defined in this page.
   The symbol page provides header for the symbol, specifically in
   "Defined in header <header>" section. An example:
 
   <tr class="t-dsc-header">
     <td colspan="2"> <div>Defined in header <code>&lt;ratio&gt;</code> </div>
   </td></tr>
 
   Returns a list of headers.
   """
   headers = set()
   all_headers = set()
 
   soup = BeautifulSoup(symbol_page_html, "html.parser")
   # Rows in table are like:
   #   Defined in header <foo>      .t-dsc-header
   #   Defined in header <bar>      .t-dsc-header
   #   decl1                        .t-dcl
   #   Defined in header <baz>      .t-dsc-header
   #   decl2                        .t-dcl
   for table in soup.select('table.t-dcl-begin, table.t-dsc-begin'):
     current_headers = []
     was_decl = False
     for row in table.select('tr'):
       if _HasClass(row, 't-dcl', 't-dsc'):
         was_decl = True
         # Symbols are in the first cell.
         found_symbols = row.find('td').stripped_strings
         if not symbol_name in found_symbols:
           continue
         headers.update(current_headers)
       elif _HasClass(row, 't-dsc-header'):
         # If we saw a decl since the last header, this is a new block of headers
         # for a new block of decls.
         if was_decl:
           current_headers = []
         was_decl = False
         # There are also .t-dsc-header for "defined in namespace".
         if not "Defined in header " in row.text:
           continue
         # The interesting header content (e.g. <cstdlib>) is wrapped in <code>.
         for header_code in row.find_all("code"):
           current_headers.append(header_code.text)
           all_headers.add(header_code.text)
   # If the symbol was never named, consider all named headers.
   return headers or all_headers
 
 
 def _ParseIndexPage(index_page_html):
   """Parse index page.
   The index page lists all std symbols and hrefs to their detailed pages
   (which contain the defined header). An example:
 
   <a href="abs.html" title="abs"><tt>abs()</tt></a> (int) <br>
   <a href="acos.html" title="acos"><tt>acos()</tt></a> <br>
 
   Returns a list of tuple (symbol_name, relative_path_to_symbol_page, variant).
   """
   symbols = []
   soup = BeautifulSoup(index_page_html, "html.parser")
   for symbol_href in soup.select("a[title]"):
     # Ignore annotated symbols like "acos<>() (std::complex)".
     # These tend to be overloads, and we the primary is more useful.
     # This accidentally accepts begin/end despite the (iterator) caption: the
     # (since C++11) note is first. They are good symbols, so the bug is unfixed.
     caption = symbol_href.next_sibling
     variant = None
     if isinstance(caption, NavigableString) and "(" in caption:
       variant = caption.text.strip(" ()")
     symbol_tt = symbol_href.find("tt")
     if symbol_tt:
       symbols.append((symbol_tt.text.rstrip("<>()"), # strip any trailing <>()
                       symbol_href["href"], variant))
   return symbols
 
 
 def _ReadSymbolPage(path, name):
   with open(path) as f:
     return _ParseSymbolPage(f.read(), name)
 
 
 def _GetSymbols(pool, root_dir, index_page_name, namespace, variants_to_accept):
   """Get all symbols listed in the index page. All symbols should be in the
   given namespace.
 
   Returns a list of Symbols.
   """
 
   # Workflow steps:
   #   1. Parse index page which lists all symbols to get symbol
   #      name (unqualified name) and its href link to the symbol page which
   #      contains the defined header.
   #   2. Parse the symbol page to get the defined header.
   index_page_path = os.path.join(root_dir, index_page_name)
   with open(index_page_path, "r") as f:
     # Read each symbol page in parallel.
     results = [] # (symbol_name, promise of [header...])
     for symbol_name, symbol_page_path, variant in _ParseIndexPage(f.read()):
       # Variant symbols (e.g. the std::locale version of isalpha) add ambiguity.
       # FIXME: use these as a fallback rather than ignoring entirely.
       variants_for_symbol = variants_to_accept.get(
           (namespace or "") + symbol_name, ())
       if variant and variant not in variants_for_symbol:
         continue
       path = os.path.join(root_dir, symbol_page_path)
       results.append((symbol_name,
                       pool.apply_async(_ReadSymbolPage, (path, symbol_name))))
 
     # Build map from symbol name to a set of headers.
     symbol_headers = collections.defaultdict(set)
     for symbol_name, lazy_headers in results:
       symbol_headers[symbol_name].update(lazy_headers.get())
 
   symbols = []
   for name, headers in sorted(symbol_headers.items(), key=lambda t : t[0]):
     symbols.append(Symbol(name, namespace, list(headers)))
   return symbols
 
 
 def GetSymbols(parse_pages):
   """Get all symbols by parsing the given pages.
 
   Args:
     parse_pages: a list of tuples (page_root_dir, index_page_name, namespace)
   """
   # By default we prefer the non-variant versions, as they're more common. But
   # there are some symbols, whose variant is more common. This list describes
   # those symbols.
   variants_to_accept = {
       # std::remove<> has variant algorithm.
       "std::remove": ("algorithm"),
   }
   symbols = []
   # Run many workers to process individual symbol pages under the symbol index.
   # Don't allow workers to capture Ctrl-C.
   pool = multiprocessing.Pool(
       initializer=lambda: signal.signal(signal.SIGINT, signal.SIG_IGN))
   try:
     for root_dir, page_name, namespace in parse_pages:
       symbols.extend(_GetSymbols(pool, root_dir, page_name, namespace,
                                  variants_to_accept))
   finally:
     pool.terminate()
     pool.join()
   return symbols

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 live 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/tools/include-mapping/test.py

 #!/usr/bin/env python
 #===- test.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
 #
 #===------------------------------------------------------------------------===#
 
 from cppreference_parser import _ParseSymbolPage, _ParseIndexPage
 
 import unittest
 
 class TestStdGen(unittest.TestCase):
 
   def testParseIndexPage(self):
     html = """
  <a href="abs.html" title="abs"><tt>abs()</tt></a> (int) <br>
  <a href="complex/abs.html" title="abs"><tt>abs&lt;&gt;()</tt></a> (std::complex) <br>
  <a href="acos.html" title="acos"><tt>acos()</tt></a> <br>
  <a href="acosh.html" title="acosh"><tt>acosh()</tt></a> <span class="t-mark-rev">(since C++11)</span> <br>
  <a href="as_bytes.html" title="as bytes"><tt>as_bytes&lt;&gt;()</tt></a> <span class="t-mark-rev t-since-cxx20">(since C++20)</span> <br>
  """
 
     actual = _ParseIndexPage(html)
     expected = [
       ("abs", "abs.html", True),
       ("abs", "complex/abs.html", True),
       ("acos", "acos.html", False),
       ("acosh", "acosh.html", False),
       ("as_bytes", "as_bytes.html", False),
     ]
     self.assertEqual(len(actual), len(expected))
     for i in range(0, len(actual)):
       self.assertEqual(expected[i][0], actual[i][0])
       self.assertTrue(actual[i][1].endswith(expected[i][1]))
       self.assertEqual(expected[i][2], actual[i][2])
 
 
   def testParseSymbolPage_SingleHeader(self):
     # Defined in header <cmath>
     html = """
  <table class="t-dcl-begin"><tbody>
   <tr class="t-dsc-header">
   <td> <div>Defined in header <code><a href="cmath.html" title="cmath">&lt;cmath&gt;</a></code>
    </div></td>
   <td></td>
   <td></td>
   </tr>
   <tr class="t-dcl">
     <td>void foo()</td>
     <td>this is matched</td>
   </tr>
 </tbody></table>
 """
     self.assertEqual(_ParseSymbolPage(html, 'foo'), set(['<cmath>']))
 
 
   def testParseSymbolPage_MulHeaders(self):
     #  Defined in header <cstddef>
     #  Defined in header <cstdio>
     #  Defined in header <cstdlib>
     html = """
 <table class="t-dcl-begin"><tbody>
   <tr class="t-dsc-header">
     <td> <div>Defined in header <code><a href="cstddef.html" title="cstddef">&lt;cstddef&gt;</a></code>
      </div></td>
      <td></td>
     <td></td>
   </tr>
   <tr class="t-dcl">
     <td>void bar()</td>
     <td>this mentions foo, but isn't matched</td>
   </tr>
   <tr class="t-dsc-header">
     <td> <div>Defined in header <code><a href="cstdio.html" title="cstdio">&lt;cstdio&gt;</a></code>
      </div></td>
     <td></td>
     <td></td>
   </tr>
   <tr class="t-dsc-header">
     <td> <div>Defined in header <code><a href=".cstdlib.html" title="ccstdlib">&lt;cstdlib&gt;</a></code>
      </div></td>
     <td></td>
     <td></td>
   </tr>
   <tr class="t-dcl">
     <td>
       <span>void</span>
       foo
       <span>()</span>
     </td>
     <td>this is matched</td>
   </tr>
 </tbody></table>
 """
     self.assertEqual(_ParseSymbolPage(html, "foo"),
                      set(['<cstdio>', '<cstdlib>']))
 
 
   def testParseSymbolPage_MulHeadersInSameDiv(self):
     # Multile <code> blocks in a Div.
     # Defined in header <algorithm>
     # Defined in header <utility>
     html = """
 <table class="t-dcl-begin"><tbody>
 <tr class="t-dsc-header">
 <td><div>
      Defined in header <code><a href="../header/algorithm.html" title="cpp/header/algorithm">&lt;algorithm&gt;</a></code><br>
      Defined in header <code><a href="../header/utility.html" title="cpp/header/utility">&lt;utility&gt;</a></code>
 </div></td>
 <td></td>
 </tr>
 <tr class="t-dcl">
   <td>
     <span>void</span>
     foo
     <span>()</span>
   </td>
   <td>this is matched</td>
 </tr>
 </tbody></table>
 """
     self.assertEqual(_ParseSymbolPage(html, "foo"),
                      set(['<algorithm>', '<utility>']))
 
   def testParseSymbolPage_MulSymbolsInSameTd(self):
     # defined in header <cstdint>
     #   int8_t
     #   int16_t
     html = """
 <table class="t-dcl-begin"><tbody>
 <tr class="t-dsc-header">
 <td><div>
      Defined in header <code><a href="cstdint.html" title="cstdint">&lt;cstdint&gt;</a></code><br>
 </div></td>
 <td></td>
 </tr>
 <tr class="t-dcl">
   <td>
     <span>int8_t</span>
     <span>int16_t</span>
   </td>
   <td>this is matched</td>
 </tr>
 </tbody></table>
 """
     self.assertEqual(_ParseSymbolPage(html, "int8_t"),
                      set(['<cstdint>']))
     self.assertEqual(_ParseSymbolPage(html, "int16_t"),
                      set(['<cstdint>']))
 
 
 if __name__ == '__main__':
   unittest.main()

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 "llvm/Support/ScopedPrinter.h"
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+using ::testing::ElementsAre;
+
+namespace clang {
+namespace tooling {
+namespace {
+
+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));
+}
+
+} // namespace
+} // namespace tooling
+} // namespace clang