[clangd] Use pre-populated mappings for standard symbols

[ilya-biryukov]

Summary

This takes ~5% of time when running clangd unit tests.

To achieve this, move mapping of system includes out of CanonicalIncludes
and into a separate class

[ilya-biryukov]

Also considered moving the std symbol mapping into a separate (private-to-implementation) class, e.g. we don't use suffix mappings and symbol mappings outside system includes.
But decided to wait until suffix mapping are going away completely.

[hokein]

In D67172#1657590, @ilya-biryukov wrote:

Also considered moving the std symbol mapping into a separate (private-to-implementation) class, e.g. we don't use suffix mappings and symbol mappings outside system includes.
But decided to wait until suffix mapping are going away completely.

It took me a while to understand this patch. I'd suggest doing it in this patch as well (it should not require large effort to do it, I think?)
The CanonicalInclude is becoming complex now, and leading to some wire design (we introduce a new field pointing to another instance).

And I'm not sure whether it is possible to remove the suffix mapping completely -- for STL symbols it is possible, but for other symbols like GNU C headers, I didn't find out an automatic way to build a lookup table.

[ilya-biryukov]

Ok, agreed. Adding this indirection layer is probably making things a bit too complex. I'll update the patch to clearly separate the std symbol mapping and canonical includes.

In D67172#1660435, @hokein wrote:

And I'm not sure whether it is possible to remove the suffix mapping completely -- for STL symbols it is possible, but for other symbols like GNU C headers, I didn't find out an automatic way to build a lookup table.

It's because we don't have anything similar to cppreference.com for them? Maybe we could try scrapping man pages ?

[ilya-biryukov]

• Move system symbol mapping to a different class.

[ilya-biryukov]

Not sure whether the new code is a win overall, it's still a bit messy
Let me know what you think.

[hokein]

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

780

what's the interesting case where SystemSymbols is null?
I think it should be fine to always use the standard symbol mapping here? just use getStandardSymbolMapping()->mapHeader(), this would help to simplify the CanonicalInclude interface (no addSystemHeadersMapping and SystemSymbols members are needed).

[hokein]

In D67172#1660469, @ilya-biryukov wrote:

Ok, agreed. Adding this indirection layer is probably making things a bit too complex. I'll update the patch to clearly separate the std symbol mapping and canonical includes.

In D67172#1660435, @hokein wrote:

And I'm not sure whether it is possible to remove the suffix mapping completely -- for STL symbols it is possible, but for other symbols like GNU C headers, I didn't find out an automatic way to build a lookup table.

It's because we don't have anything similar to cppreference.com for them? Maybe we could try scrapping man pages ?

yes, cppreferences only provides symbols from C++/C standard libraries. Parsing man page is possible, but it requires some work (we have to write another tool to parse it).

[ilya-biryukov]

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

780

Fair question. I guess the only interesting case is unit tests - if we always have system include mapping, testing other things independently is impossible, therefore it's a bit more fragile.
But I don't think that's a real problem in practice.

Should we try to go even further, pass LangOptions to CanonicalIncludes on construction and always have a single defined mapping? I'll try to do that and update the patch accordingly. But let me know if you think that's a bad idea for some reason.

[sammccall]

I had the same reaction as Haojian to the original patch, thanks for clearing that up.

I do wonder whether we're microoptimizing for the tests too much, I don't think 5% on the tests is worth very much in itself, unless it's speeding up real workloads or improving the code (it may well be).

I'm nervous about requiring langopts, it's convenient in tests/prototypes/etc to be able to default-construct CanonicalIncludes (e.g. a test that doesn't actually care about standard library mappings).

[ilya-biryukov]

In D67172#1662888, @sammccall wrote:

I do wonder whether we're microoptimizing for the tests too much, I don't think 5% on the tests is worth very much in itself, unless it's speeding up real workloads or improving the code (it may well be).

Even though tests don't parse real C++ programs, I wouldn't call it a micro-optimization. Spending 5% on such a low-level operation is not ok, small things like that can add up and have a subtle effect on performance.
If there's an issue with making the code more complex, I'm happy to explore other ways to make it simpler. What would convince you that's a cleanup that improves things? What parts of the current version do you think are problematic?

I'm nervous about requiring langopts, it's convenient in tests/prototypes/etc to be able to default-construct CanonicalIncludes (e.g. a test that doesn't actually care about standard library mappings).

We can have a factory method that constructs with default lang opts for tests, I don't think this would be an issue in the actual application code. In fact, I think it'll make the application code better.

[sammccall]

In D67172#1662916, @ilya-biryukov wrote:

In D67172#1662888, @sammccall wrote:

I do wonder whether we're microoptimizing for the tests too much, I don't think 5% on the tests is worth very much in itself, unless it's speeding up real workloads or improving the code (it may well be).

Even though tests don't parse real C++ programs, I wouldn't call it a micro-optimization. Spending 5% on such a low-level operation is not ok, small things like that can add up and have a subtle effect on performance.

Only if it's 5% of something meaningful. If the denominator isn't something we care about, then it's really "spending XXX usec is not ok" - which depends on XXX I think.

If there's an issue with making the code more complex, I'm happy to explore other ways to make it simpler. What would convince you that's a cleanup that improves things? What parts of the current version do you think are problematic?

You'll note that I didn't say that *anything* about the current version was problematic :-)

One way this could be simpler is if suffix mappings were gone, then the StdIncludes class would go away and we'd just be left with a stringmap<string>. Then there'd be a performance win with almost no extra complexity.
The description says you're waiting for it to go away, but AFAIK nobody's working on this nor really knows how to eliminate it.

Some of the new complexity seems unneccesary even with this approach.
There's a lot of indirection around the initialization, an enum that gets passed around a bunch, constructors that switch over it.
I think this could be:

StdIncludes *getStdIncludes(LangOpts) {
    if (is c++) {
       static pair<...> entries[] = ...;
       static StdIncludes *CPP = new StdIncludes(entries);
       // the things that apply everywhere are in the StdIncludes constructor
       return CPP;
    } else if (is c) {
       ...
    } else {
      static StdIncludes *Others = new StdIncludes({});
      return Others;
    }
}

I'm nervous about requiring langopts, it's convenient in tests/prototypes/etc to be able to default-construct CanonicalIncludes (e.g. a test that doesn't actually care about standard library mappings).

We can have a factory method that constructs with default lang opts for tests, I don't think this would be an issue in the actual application code. In fact, I think it'll make the application code better.

I'm not saying that there's no way to work around it, or that it's fatal, but my opinion is that this would be worse than the current state.

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

22

Why C11 and not C?

[ilya-biryukov]

In D67172#1662945, @sammccall wrote:

Only if it's 5% of something meaningful. If the denominator isn't something we care about, then it's really "spending XXX usec is not ok" - which depends on XXX I think.

Agree, but unit-test time is meaningful clangd developers. Not saying this is more important than real use-cases, but keeping the unit tests enables us to iterate faster.

One way this could be simpler is if suffix mappings were gone, then the StdIncludes class would go away and we'd just be left with a stringmap<string>. Then there'd be a performance win with almost no extra complexity.
The description says you're waiting for it to go away, but AFAIK nobody's working on this nor really knows how to eliminate it.

We seem to know how to eliminate this in principle. See @hokein's comment, we could try parsing man pages or even the headers themselves and building a corresponding symbol map.
But this patch does not add suffix mapping, so I don't think that's relevant - this patch tries to avoid redundant initialization; not remove suffix maps.

Some of the new complexity seems unneccesary even with this approach.
There's a lot of indirection around the initialization, an enum that gets passed around a bunch, constructors that switch over it.
I think this could be:

Will update the patch. Although I find the current approach more direct, I will happily change the code according to your suggestion.

I'm nervous about requiring langopts, it's convenient in tests/prototypes/etc to be able to default-construct CanonicalIncludes (e.g. a test that doesn't actually care about standard library mappings).

We can have a factory method that constructs with default lang opts for tests, I don't think this would be an issue in the actual application code. In fact, I think it'll make the application code better.

I'm not saying that there's no way to work around it, or that it's fatal, but my opinion is that this would be worse than the current state.

If we care about having a default constructor, we can default to using StdIncludes with a default mapping. I'll avoid requiring LangOptions in the constructor in that case. Thanks for the early feedback!

[ilya-biryukov]

• Alternative approach - do not add extra classes, aim to minimize changes

[ilya-biryukov]

The new version looks very much like the older one, with a few additions to not re-initialize data twice.
PTAL and let me know what you think.

[ilya-biryukov]

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

734

Note that addSuffixMapping/findSuffixMapping are not paired anymore, which I personally find to be odd.
But let me know whether that's a concern someone else shares.

[sammccall]

LG, though if we can drop the struct and make MaxSuffixComponents a constant it'd be simpler still.

In D67172#1662957, @ilya-biryukov wrote:

In D67172#1662945, @sammccall wrote:

Only if it's 5% of something meaningful. If the denominator isn't something we care about, then it's really "spending XXX usec is not ok" - which depends on XXX I think.

Agree, but unit-test time is meaningful clangd developers. Not saying this is more important than real use-cases, but keeping the unit tests enables us to iterate faster.

Sure. This is going to win a couple of percent I guess: for these cases we care about walltime including rebuild and lit startup overhead. It's worth having (and thanks for doing this!) but I don't think we should pay much complexity.

One way this could be simpler is if suffix mappings were gone, then the StdIncludes class would go away and we'd just be left with a stringmap<string>. Then there'd be a performance win with almost no extra complexity.
The description says you're waiting for it to go away, but AFAIK nobody's working on this nor really knows how to eliminate it.

We seem to know how to eliminate this in principle. See @hokein's comment, we could try parsing man pages or even the headers themselves and building a corresponding symbol map.

"we could try" sounds like we *don't* know how to eliminate it. Parsing manpages aside, I thought the main problem was these symbols are nonstandard and an infinitely portable qname->header mapping simply didn't exist.

But this patch does not add suffix mapping, so I don't think that's relevant - this patch tries to avoid redundant initialization; not remove suffix maps.

This patch adds code shoveling around suffix maps, and so increases the cost of this feature. (Less so after latest changes). It also increases the scope of a future patch that would remove suffix maps. Sequencing this the other way would be better, if removing suffix mapping was straightforward. (I don't think it is)

Some of the new complexity seems unneccesary even with this approach.
There's a lot of indirection around the initialization, an enum that gets passed around a bunch, constructors that switch over it.
I think this could be:

Will update the patch. Although I find the current approach more direct, I will happily change the code according to your suggestion.

Thanks, this looks a lot better!
I think it can be simplified a little further, as the suffix maps are totally hardcoded now.

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

38

nit: can we write if (SuffixHeaderMapping) { ... } for consistency with above?

74

so this is a constant, and it's 3.

Can we avoid the calculation/propagation and defining a struct, and just add an assert(llvm::all_of(...)) after the initialization?

76

I think this could just be

static const auto *SystemHeaderMap = new llvm::StringMap<string>{
...
}

skipping the intermediate array, and doing the initialize-once here
(if we can drop the struct)

744

if you want to save CPU, move to the scope where it's used? Lit tests and many interesting subsets will never use C.

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

62–63

nit: maybe StdSuffixHeaderMapping to clarify the purpose, now these are std-only

[ilya-biryukov]

In D67172#1663096, @sammccall wrote:

LG, though if we can drop the struct and make MaxSuffixComponents a constant it'd be simpler still.

Done.

Sure. This is going to win a couple of percent I guess: for these cases we care about walltime including rebuild and lit startup overhead. It's worth having (and thanks for doing this!) but I don't think we should pay much complexity.

Agreed.

"we could try" sounds like we *don't* know how to eliminate it. Parsing manpages aside, I thought the main problem was these symbols are nonstandard and an infinitely portable qname->header mapping simply didn't exist.

I would expect qualified names to be more portable than paths, but might be mistaken. I recall that we might run into problems if folks define some names as macros instead of functions, but I would be interested to see how common is this.
We should probably write down the examples that are broken somewhere... It's hard to see why it doesn't work without having the concrete cases.
@hokein, do you have any examples that cannot be covered by qual-name-to-path mapping?

Thanks, this looks a lot better!
I think it can be simplified a little further, as the suffix maps are totally hardcoded now.

I think the simplest option is to always make the path suffix mapping available in the class.
That means we will always map the system paths to their shorter versions. It looks ok to me, but might make unit-testing a little more awkward.
WDYT?
I'll land this and send this out as a separate patch if everyone is happy with the approach.

[sammccall]

In D67172#1663179, @ilya-biryukov wrote:

"we could try" sounds like we *don't* know how to eliminate it. Parsing manpages aside, I thought the main problem was these symbols are nonstandard and an infinitely portable qname->header mapping simply didn't exist.

I would expect qualified names to be more portable than paths, but might be mistaken. I recall that we might run into problems if folks define some names as macros instead of functions, but I would be interested to see how common is this.

In practice, I expect almost all of these names to be C and thus unqualified.

Names are indeed more portable but unlike path mappings we can't just include both when different platforms want different things, or nothing.
e.g. are we willing to claim that any kind of symbol named ::open should be from <sys/stat.h>, even on windows?
Maybe it's OK, and I can't remember if we had specific bad examples in mind, but seems like there are dragons here.

Thanks, this looks a lot better!
I think it can be simplified a little further, as the suffix maps are totally hardcoded now.

I think the simplest option is to always make the path suffix mapping available in the class.
That means we will always map the system paths to their shorter versions. It looks ok to me, but might make unit-testing a little more awkward.
WDYT?
I'll land this and send this out as a separate patch if everyone is happy with the approach.

From a public API standpoint, it seems cleaner to only have these available once addSystemHeadersMapping has been called (with any argument), and delay assigning the pointer until then.
But if adds more than a few lines, it seems fine without.

[ilya-biryukov]

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

38

I'd prefer less nesting to consistency, but happy let me know if you feel that's very important.

74

The assertion is inside the loop that's adding the mappings instead of llvm::all_of.

744

Done. Also initialized everything directly as StringMap

[ilya-biryukov]

• Make MaxSuffixComponents a constant
• Put the suffix mapping into a single constant
• Initialize all StringMaps directly
• Rename to Std...Mapping

[ilya-biryukov]

Thanks for all suggestions. The final result is rather small and minimal.

clang-tools-extra/clangd/ParsedAST.cpp

Clang->getPreprocessor().addPPCallbacks(
           Clang->getSourceManager(), MainFileMacroExpLocs));
 
   // Copy over the includes from the preamble, then combine with the
   // non-preamble includes below.
   CanonicalIncludes CanonIncludes;
   if (Preamble)
     CanonIncludes = Preamble->CanonIncludes;
   else
-    addSystemHeadersMapping(&CanonIncludes, Clang->getLangOpts());
+    CanonIncludes.addSystemHeadersMapping(Clang->getLangOpts());
   std::unique_ptr<CommentHandler> IWYUHandler =
       collectIWYUHeaderMaps(&CanonIncludes);
   Clang->getPreprocessor().addCommentHandler(IWYUHandler.get());
 
   // Collect tokens of the main file.
   syntax::TokenCollector CollectTokens(Clang->getPreprocessor());
 
   if (llvm::Error Err = Action->Execute())

clang-tools-extra/clangd/Preamble.cpp

public:
   void AfterExecute(CompilerInstance &CI) override {
     if (!ParsedCallback)
       return;
     trace::Span Tracer("Running PreambleCallback");
     ParsedCallback(CI.getASTContext(), CI.getPreprocessorPtr(), CanonIncludes);
   }
 
   void BeforeExecute(CompilerInstance &CI) override {
-    addSystemHeadersMapping(&CanonIncludes, CI.getLangOpts());
+    CanonIncludes.addSystemHeadersMapping(CI.getLangOpts());
     SourceMgr = &CI.getSourceManager();
   }
 
   std::unique_ptr<PPCallbacks> createPPCallbacks() override {
     assert(SourceMgr && "SourceMgr must be set at this point");
     return std::make_unique<PPChainedCallbacks>(
         collectIncludeStructureCallback(*SourceMgr, &Includes),
         std::make_unique<CollectMainFileMacros>(*SourceMgr, &MainFileMacros));

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

 #include "llvm/Support/Regex.h"
 #include <mutex>
 #include <string>
 #include <vector>
 
 namespace clang {
 namespace clangd {
 
+class StdIncludes;
+
 /// Maps a definition location onto an #include file, based on a set of filename
 /// rules.
 /// Only const methods (i.e. mapHeader) in this class are thread safe.
 class CanonicalIncludes {
 public:
   CanonicalIncludes() = default;
 
-  /// Adds a string-to-string mapping from \p Path to \p CanonicalPath.
-  void addMapping(llvm::StringRef Path, llvm::StringRef CanonicalPath);
-
-  /// Maps files with last path components matching \p Suffix to \p
-  /// CanonicalPath.
-  void addPathSuffixMapping(llvm::StringRef Suffix,
-                            llvm::StringRef CanonicalPath);
-
-  /// Sets the canonical include for any symbol with \p QualifiedName.
-  /// Symbol mappings take precedence over header mappings.
-  void addSymbolMapping(llvm::StringRef QualifiedName,
-                        llvm::StringRef CanonicalPath);
-
   /// Returns the canonical include for symbol with \p QualifiedName.
   /// \p Header is the file the declaration was reachable from.
   /// Header itself will be returned if there is no relevant mapping.
   llvm::StringRef mapHeader(llvm::StringRef Header,
                             llvm::StringRef QualifiedName) const;
 
+  /// Adds a string-to-string mapping from \p Path to \p CanonicalPath.
+  void addMapping(llvm::StringRef Path, llvm::StringRef CanonicalPath);
+
+  /// Adds mapping for system headers and some special symbols (e.g. STL symbols
+  /// in <iosfwd> need to be mapped individually). Approximately, the following
+  /// system headers are handled:
+  ///   - C++ standard library e.g. bits/basic_string.h$ -> <string>
+  ///   - Posix library e.g. bits/pthreadtypes.h$ -> <pthread.h>
+  ///   - Compiler extensions, e.g. include/avx512bwintrin.h$ -> <immintrin.h>
+  /// The mapping is hardcoded and hand-maintained, so it might not cover all
+  /// headers.
+  void addSystemHeadersMapping(const LangOptions &Language);
+
 private:
   /// A map from full include path to a canonical path.
   llvm::StringMap<std::string> FullPathMapping;
-  /// A map from a suffix (one or components of a path) to a canonical path.
-  llvm::StringMap<std::string> SuffixHeaderMapping;
-  /// Maximum number of path components stored in a key of SuffixHeaderMapping.
-  /// Used to reduce the number of lookups into SuffixHeaderMapping.
-  int MaxSuffixComponents = 0;
-  /// A map from fully qualified symbol names to header names.
-  llvm::StringMap<std::string> SymbolMapping;
+  /// Precomputed mapping of std symbols. Ignored when null.
+  const StdIncludes *SystemSymbols = nullptr;
 };
 
 /// Returns a CommentHandler that parses pragma comment on include files to
 /// determine when we should include a different header from the header that
 /// directly defines a symbol. Mappinps are registered with \p Includes.
 ///
 /// Currently it only supports IWYU private pragma:
 /// https://github.com/include-what-you-use/include-what-you-use/blob/master/docs/IWYUPragmas.md#iwyu-pragma-private
 std::unique_ptr<CommentHandler>
 collectIWYUHeaderMaps(CanonicalIncludes *Includes);
 
-/// Adds mapping for system headers and some special symbols (e.g. STL symbols
-/// in <iosfwd> need to be mapped individually). Approximately, the following
-/// system headers are handled:
-///   - C++ standard library e.g. bits/basic_string.h$ -> <string>
-///   - Posix library e.g. bits/pthreadtypes.h$ -> <pthread.h>
-///   - Compiler extensions, e.g. include/avx512bwintrin.h$ -> <immintrin.h>
-/// The mapping is hardcoded and hand-maintained, so it might not cover all
-/// headers.
-void addSystemHeadersMapping(CanonicalIncludes *Includes,
-                             const LangOptions &Language);
+/// Exposed only for unit tests, an implementation detail of CanonicalIncludes.
+/// Handles mapping standard symbols and headers.
+class StdIncludes {
+public:
+  StdIncludes() = default;
+
+  enum class SymbolsFlavour;
+  /// Populates the mapping for a precomputed set of symbols. This constructor
+  /// is expensive, avoid calling it too much.
+  StdIncludes(SymbolsFlavour Language);
+
+  /// Try to find a corresponding standard library file to #include for file \p
+  /// Header and symbol named \p QualifiedName.
+  /// If the inputs are not recognized as part of the standard library, returns
+  /// None.
+  llvm::Optional<llvm::StringRef>
+  mapHeader(llvm::StringRef Header, llvm::StringRef QualifiedName) const;
+
+  /// Sets the canonical include for any symbol with \p QualifiedName.
+  /// Symbol mappings take precedence over header mappings.
+  void addSymbolMapping(llvm::StringRef QualifiedName,
+                        llvm::StringRef CanonicalPath);
+
+  /// Maps files with last path components matching \p Suffix to \p
+  /// CanonicalPath.
+  void addPathSuffixMapping(llvm::StringRef Suffix,
+                            llvm::StringRef CanonicalPath);
+
+private:
+  /// A map from fully qualified symbol names to header names.
+  llvm::StringMap<std::string> SymbolMapping;
+  /// A map from a suffix (one or components of a path) to a canonical path.
+  llvm::StringMap<std::string> SuffixHeaderMapping;
+  /// Maximum number of path components stored in a key of SuffixHeaderMapping.
+  /// Used to reduce the number of lookups into SuffixHeaderMapping.
+  int MaxSuffixComponents = 0;
+};
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_HEADERMAPCOLLECTOR_H

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

 //===-- CanonicalIncludes.h - remap #inclue headers--------------*- 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 "CanonicalIncludes.h"
 #include "Headers.h"
+#include "clang/Basic/LangOptions.h"
 #include "clang/Driver/Types.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/Path.h"
 #include <algorithm>
+#include <memory>
 
 namespace clang {
 namespace clangd {
-namespace {
-const char IWYUPragma[] = "// IWYU pragma: private, include ";
-} // namespace
-
-void CanonicalIncludes::addPathSuffixMapping(llvm::StringRef Suffix,
-                                             llvm::StringRef CanonicalPath) {
-  int Components = std::distance(llvm::sys::path::begin(Suffix),
-                                 llvm::sys::path::end(Suffix));
-  MaxSuffixComponents = std::max(MaxSuffixComponents, Components);
-  SuffixHeaderMapping[Suffix] = CanonicalPath;
-}
-
-void CanonicalIncludes::addMapping(llvm::StringRef Path,
-                                   llvm::StringRef CanonicalPath) {
-  FullPathMapping[Path] = CanonicalPath;
-}
-
-void CanonicalIncludes::addSymbolMapping(llvm::StringRef QualifiedName,
-                                         llvm::StringRef CanonicalPath) {
-  this->SymbolMapping[QualifiedName] = CanonicalPath;
-}
 
-llvm::StringRef
-CanonicalIncludes::mapHeader(llvm::StringRef Header,
-                             llvm::StringRef QualifiedName) const {
-  assert(!Header.empty());
-  auto SE = SymbolMapping.find(QualifiedName);
-  if (SE != SymbolMapping.end())
-    return SE->second;
-
-  auto MapIt = FullPathMapping.find(Header);
-  if (MapIt != FullPathMapping.end())
-    return MapIt->second;
-
-  int Components = 1;
-  for (auto It = llvm::sys::path::rbegin(Header),
-            End = llvm::sys::path::rend(Header);
-       It != End && Components <= MaxSuffixComponents; ++It, ++Components) {
-    auto SubPath = Header.substr(It->data() - Header.begin());
-    auto MappingIt = SuffixHeaderMapping.find(SubPath);
-    if (MappingIt != SuffixHeaderMapping.end())
-      return MappingIt->second;
-  }
-  return Header;
+enum class StdIncludes::SymbolsFlavour { Cpp, C11, Other };
+namespace {
+StdIncludes::SymbolsFlavour symbolsFlavour(const LangOptions &Language) {
+  if (Language.CPlusPlus)
+    return StdIncludes::SymbolsFlavour::Cpp;
+  if (Language.C11)
+    return StdIncludes::SymbolsFlavour::C11;
+  return StdIncludes::SymbolsFlavour::Other;
+const StdIncludes &getStandardSymbolMapping(const LangOptions &Opts) {
+  // FIXME: suffix path mappings can be reused across all three classes.
+  static const auto *ForCpp = new StdIncludes(StdIncludes::SymbolsFlavour::Cpp);
+  static const auto *ForC11 = new StdIncludes(StdIncludes::SymbolsFlavour::C11);
+  static const auto *ForOther =
+      new StdIncludes(StdIncludes::SymbolsFlavour::Other);
+
+  switch (symbolsFlavour(Opts)) {
+  case StdIncludes::SymbolsFlavour::Cpp:
+    return *ForCpp;
+  case StdIncludes::SymbolsFlavour::C11:
+    return *ForC11;
+  case StdIncludes::SymbolsFlavour::Other:
+    return *ForOther;
   }
-
-std::unique_ptr<CommentHandler>
-collectIWYUHeaderMaps(CanonicalIncludes *Includes) {
-  class PragmaCommentHandler : public clang::CommentHandler {
-  public:
-    PragmaCommentHandler(CanonicalIncludes *Includes) : Includes(Includes) {}
-
-    bool HandleComment(Preprocessor &PP, SourceRange Range) override {
-      llvm::StringRef Text =
-          Lexer::getSourceText(CharSourceRange::getCharRange(Range),
-                               PP.getSourceManager(), PP.getLangOpts());
-      if (!Text.consume_front(IWYUPragma))
-        return false;
-      // FIXME(ioeric): resolve the header and store actual file path. For now,
-      // we simply assume the written header is suitable to be #included.
-      Includes->addMapping(PP.getSourceManager().getFilename(Range.getBegin()),
-                           isLiteralInclude(Text) ? Text.str()
-                                                  : ("\"" + Text + "\"").str());
-      return false;
-    }
-
-  private:
-    CanonicalIncludes *const Includes;
-  };
-  return std::make_unique<PragmaCommentHandler>(Includes);
+  llvm_unreachable("unhandled SymbolFlavour");
 }
 
-void addSystemHeadersMapping(CanonicalIncludes *Includes,
-                             const LangOptions &Language) {
+StdIncludes::StdIncludes(SymbolsFlavour Language) {
   static constexpr std::pair<const char *, const char *> SymbolMap[] = {
-#define SYMBOL(Name, NameSpace, Header) { #NameSpace#Name, #Header },
-      #include "StdSymbolMap.inc"
+#define SYMBOL(Name, NameSpace, Header) {#NameSpace #Name, #Header},
 #undef SYMBOL
   };
   static constexpr std::pair<const char *, const char *> CSymbolMap[] = {
-#define SYMBOL(Name, NameSpace, Header) { #Name, #Header },
-      #include "CSymbolMap.inc"
+#define SYMBOL(Name, NameSpace, Header) {#Name, #Header},
 #undef SYMBOL
   };
-  if (Language.CPlusPlus) {
+  switch (Language) {
+  case SymbolsFlavour::Cpp:
     for (const auto &Pair : SymbolMap)
-      Includes->addSymbolMapping(Pair.first, Pair.second);
-  } else if (Language.C11) {
+      addSymbolMapping(Pair.first, Pair.second);
+    break;
+  case SymbolsFlavour::C11:
     for (const auto &Pair : CSymbolMap)
-      Includes->addSymbolMapping(Pair.first, Pair.second);
+      addSymbolMapping(Pair.first, Pair.second);
+    break;
+  case SymbolsFlavour::Other:
+    break;
   }
-  // FIXME: remove the std header mapping once we support ambiguous symbols, now
-  // it serves as a fallback to disambiguate:
+  // FIXME: remove the std header mapping once we support ambiguous symbols,
+  // now it serves as a fallback to disambiguate:
   //   - symbols with multiple headers (e.g. std::move)
   static constexpr std::pair<const char *, const char *> SystemHeaderMap[] = {
       {"include/__stddef_max_align_t.h", "<cstddef>"},
       {"include/__wmmintrin_aes.h", "<wmmintrin.h>"},
       {"include/__wmmintrin_pclmul.h", "<wmmintrin.h>"},
       {"include/adxintrin.h", "<immintrin.h>"},
       {"include/ammintrin.h", "<ammintrin.h>"},
       {"include/avx2intrin.h", "<immintrin.h>"},
       {"include/avx512bwintrin.h", "<immintrin.h>"},
       {"include/avx512cdintrin.h", "<immintrin.h>"},
static constexpr std::pair<const char *, const char *> SystemHeaderMap[] = {
       {"bits/ustat.h", "<sys/ustat.h>"},
       {"bits/utmp.h", "<utmp.h>"},
       {"bits/utmpx.h", "<utmpx.h>"},
       {"bits/waitflags.h", "<sys/wait.h>"},
       {"bits/waitstatus.h", "<sys/wait.h>"},
       {"bits/xtitypes.h", "<stropts.h>"},
   };
   for (const auto &Pair : SystemHeaderMap)
-    Includes->addPathSuffixMapping(Pair.first, Pair.second);
+    addPathSuffixMapping(Pair.first, Pair.second);
+}
+
+llvm::Optional<llvm::StringRef>
+StdIncludes::mapHeader(llvm::StringRef Header,
+                       llvm::StringRef QualifiedName) const {
+  auto SE = SymbolMapping.find(QualifiedName);
+  if (SE != SymbolMapping.end())
+    return llvm::StringRef(SE->second);
+
+  int Components = 1;
+  for (auto It = llvm::sys::path::rbegin(Header),
+            End = llvm::sys::path::rend(Header);
+       It != End && Components <= MaxSuffixComponents; ++It, ++Components) {
+    auto SubPath = Header.substr(It->data() - Header.begin());
+    auto MappingIt = SuffixHeaderMapping.find(SubPath);
+    if (MappingIt != SuffixHeaderMapping.end())
+      return llvm::StringRef(MappingIt->second);
+  }
+
+  return llvm::None;
+}
+
+void StdIncludes::addSymbolMapping(llvm::StringRef QualifiedName,
+                                   llvm::StringRef CanonicalPath) {
+  SymbolMapping[QualifiedName] = CanonicalPath;
+}
+
+void StdIncludes::addPathSuffixMapping(llvm::StringRef Suffix,
+                                       llvm::StringRef CanonicalPath) {
+  int Components = std::distance(llvm::sys::path::begin(Suffix),
+                                 llvm::sys::path::end(Suffix));
+  MaxSuffixComponents = std::max(MaxSuffixComponents, Components);
+  SuffixHeaderMapping[Suffix] = CanonicalPath;
+}
+
+namespace {
+const char IWYUPragma[] = "// IWYU pragma: private, include ";
+} // namespace
+
+void CanonicalIncludes::addMapping(llvm::StringRef Path,
+                                   llvm::StringRef CanonicalPath) {
+  FullPathMapping[Path] = CanonicalPath;
+}
+
+llvm::StringRef
+CanonicalIncludes::mapHeader(llvm::StringRef Header,
+                             llvm::StringRef QualifiedName) const {
+  assert(!Header.empty());
+  // Prefer a mapping from the system symbols.
+  if (SystemSymbols) {
+    if (auto Result = SystemSymbols->mapHeader(Header, QualifiedName))
+      return *Result;
+  }
+
+  auto MapIt = FullPathMapping.find(Header);
+  if (MapIt != FullPathMapping.end())
+    return MapIt->second;
+
+  return Header;
+}
+
+std::unique_ptr<CommentHandler>
+collectIWYUHeaderMaps(CanonicalIncludes *Includes) {
+  class PragmaCommentHandler : public clang::CommentHandler {
+  public:
+    PragmaCommentHandler(CanonicalIncludes *Includes) : Includes(Includes) {}
+
+    bool HandleComment(Preprocessor &PP, SourceRange Range) override {
+      llvm::StringRef Text =
+          Lexer::getSourceText(CharSourceRange::getCharRange(Range),
+                               PP.getSourceManager(), PP.getLangOpts());
+      if (!Text.consume_front(IWYUPragma))
+        return false;
+      // FIXME(ioeric): resolve the header and store actual file path. For now,
+      // we simply assume the written header is suitable to be #included.
+      Includes->addMapping(PP.getSourceManager().getFilename(Range.getBegin()),
+                           isLiteralInclude(Text) ? Text.str()
+                                                  : ("\"" + Text + "\"").str());
+      return false;
+    }
+
+  private:
+    CanonicalIncludes *const Includes;
+  };
+  return std::make_unique<PragmaCommentHandler>(Includes);
+}
+
+void CanonicalIncludes::addSystemHeadersMapping(const LangOptions &Language) {
+  assert(SystemSymbols == nullptr && "resetting the system headers mapping");
+  SystemSymbols = &getStandardSymbolMapping(Language);
 }
 
 } // namespace clangd
 } // namespace clang

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

IndexAction(std::shared_ptr<SymbolCollector> C,
         RefsCallback(RefsCallback), RelationsCallback(RelationsCallback),
         IncludeGraphCallback(IncludeGraphCallback), Collector(C),
         Includes(std::move(Includes)), Opts(Opts),
         PragmaHandler(collectIWYUHeaderMaps(this->Includes.get())) {}
 
   std::unique_ptr<ASTConsumer>
   CreateASTConsumer(CompilerInstance &CI, llvm::StringRef InFile) override {
     CI.getPreprocessor().addCommentHandler(PragmaHandler.get());
-    addSystemHeadersMapping(Includes.get(), CI.getLangOpts());
+    Includes->addSystemHeadersMapping(CI.getLangOpts());
     if (IncludeGraphCallback != nullptr)
       CI.getPreprocessor().addPPCallbacks(
           std::make_unique<IncludeGraphCollector>(CI.getSourceManager(), IG));
 
     return index::createIndexingASTConsumer(
         Collector, Opts, CI.getPreprocessorPtr(),
         /*ShouldSkipFunctionBody=*/[this](const Decl *D) {
           auto &SM = D->getASTContext().getSourceManager();

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

 //===-- CanonicalIncludesTests.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 "index/CanonicalIncludes.h"
+#include "clang/Basic/LangOptions.h"
+#include "llvm/Testing/Support/SupportHelpers.h"
 #include "gtest/gtest.h"
 
 namespace clang {
 namespace clangd {
 namespace {
 
+using llvm::ValueIs;
+using ::testing::Eq;
+
 TEST(CanonicalIncludesTest, CStandardLibrary) {
   CanonicalIncludes CI;
   auto Language = LangOptions();
   Language.C11 = true;
-  addSystemHeadersMapping(&CI, Language);
+  CI.addSystemHeadersMapping(Language);
   // Usual standard library symbols are mapped correctly.
   EXPECT_EQ("<stdio.h>", CI.mapHeader("path/stdio.h", "printf"));
 }
 
 TEST(CanonicalIncludesTest, CXXStandardLibrary) {
   CanonicalIncludes CI;
   auto Language = LangOptions();
   Language.CPlusPlus = true;
-  addSystemHeadersMapping(&CI, Language);
+  CI.addSystemHeadersMapping(Language);
 
   // Usual standard library symbols are mapped correctly.
   EXPECT_EQ("<vector>", CI.mapHeader("path/vector.h", "std::vector"));
   EXPECT_EQ("<cstdio>", CI.mapHeader("path/stdio.h", "std::printf"));
   // std::move is ambiguous, currently mapped only based on path
   EXPECT_EQ("<utility>", CI.mapHeader("libstdc++/bits/move.h", "std::move"));
   EXPECT_EQ("path/utility.h", CI.mapHeader("path/utility.h", "std::move"));
   // Unknown std symbols aren't mapped.
TEST(CanonicalIncludesTest, PathMapping) {
   CI.addMapping("foo/bar", "<baz>");
 
   EXPECT_EQ("<baz>", CI.mapHeader("foo/bar", "some::symbol"));
   EXPECT_EQ("bar/bar", CI.mapHeader("bar/bar", "some::symbol"));
 }
 
 TEST(CanonicalIncludesTest, SymbolMapping) {
   // As used for standard library.
-  CanonicalIncludes CI;
-  CI.addSymbolMapping("some::symbol", "<baz>");
+  StdIncludes SI;
+  SI.addSymbolMapping("some::symbol", "<baz>");
 
-  EXPECT_EQ("<baz>", CI.mapHeader("foo/bar", "some::symbol"));
-  EXPECT_EQ("foo/bar", CI.mapHeader("foo/bar", "other::symbol"));
+  EXPECT_THAT(SI.mapHeader("foo/bar", "some::symbol"),
+              ValueIs(StringRef("<baz>")));
+  EXPECT_THAT(SI.mapHeader("foo/bar", "other::symbol"), Eq(llvm::None));
 }
 
 TEST(CanonicalIncludesTest, Precedence) {
   CanonicalIncludes CI;
   CI.addMapping("some/path", "<path>");
-  CI.addSymbolMapping("some::symbol", "<symbol>");
+
+  LangOptions Language;
+  Language.CPlusPlus = true;
+  CI.addSystemHeadersMapping(Language);
 
   // Symbol mapping beats path mapping.
-  EXPECT_EQ("<symbol>", CI.mapHeader("some/path", "some::symbol"));
+  EXPECT_EQ("<vector>", CI.mapHeader("some/path", "std::vector"));
 }
 
 } // namespace
 } // namespace clangd
 } // namespace clang

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

EXPECT_THAT(Symbols.begin()->IncludeHeaders,
               UnorderedElementsAre(IncludeHeaderWithRef(TestHeaderURI, 1u)));
 }
 
 TEST_F(SymbolCollectorTest, CanonicalSTLHeader) {
   CollectorOpts.CollectIncludePath = true;
   CanonicalIncludes Includes;
   auto Language = LangOptions();
   Language.CPlusPlus = true;
-  addSystemHeadersMapping(&Includes, Language);
+  Includes.addSystemHeadersMapping(Language);
   CollectorOpts.Includes = &Includes;
   runSymbolCollector("namespace std { class string {}; }", /*Main=*/"");
   EXPECT_THAT(Symbols,
               Contains(AllOf(QName("std::string"), DeclURI(TestHeaderURI),
                              IncludeHeader("<string>"))));
 }
 
 TEST_F(SymbolCollectorTest, IWYUPragma) {