[clangd] collect symbol #include & insert #include in global code completion.

[ioeric]

Summary

o Collect suitable #include paths for index symbols. This also does smart mapping
for STL symbols and IWYU pragma (code borrowed from include-fixer).
o For global code completion, add a command for inserting new #include in each code
completion item.

[sammccall]

TL;DR:

• I think we can expose fewer types/abstractions in the header mapping, and put it all in one header. If we want some functionality to be global-index only, we should make it an option to the symbolcollector, not stash the logic somewhere else I think.
• regex seems like a big hammer, but we can revisit if this is on the hot path
• the overridden path should probably be an "include string" rather than a URI
• lots of naming nits as usual :-)
• I haven't reviewed the actual preprocessor/include-path madness yet :-)

clangd/ClangdLSPServer.cpp

204

The caveat from apply fix also applies here. Maybe we should combine the tail of this case and the tail of apply-fix (the part from WorkspaceEdit)? They're simple (and wrong) now, but will need the same changes.

clangd/ClangdServer.cpp

314

(I still want to look at this bit... on monday :-)

clangd/CodeComplete.cpp

255–256

contents is unused

290–291

not sure where this is shown, but maybe add "if needed"?

297

LSP says we should use additionalTextEdits instead.
I think we have OK reasons, but you probably want to mention it here.

859

What do you think about (redundantly) passing filename to the constructor, and stashing it in a member, instead of passing to all the methods here?
I think main purpose of having this class is not having the *primary* data flow obscured by all the various context variables.

If you don't like that, we could also pass the SemaCCInput struct to the constructor itself. The distinction between constrcutor params and run() params is pretty artificial.

(as noted above, I think/hope Contents is unused in any case)

clangd/Protocol.cpp

410

nit: drop braces consistent with the other code around here

clangd/Protocol.h

432

I would call this "header". At least in the current implementation, it's not a URI, and we we really don't want anyone trying to parse it.

433

I don't think this comment applies here?

452

nit: remove blank line (and below). These form a list.

463

Hmm, you could consider struct Command : public ExecuteCommandParams { std::string title; }

I guess it's a hack, but this repetition seems a little silly. You could then reuse some of the JSON stuff too.

clangd/global-symbol-builder/PragmaCommentHandler.h

1 ↗

(On Diff #131782)

can this also be put in HeaderMap.h?

28 ↗

(On Diff #131782)

I'm not sure this class needs to be exposed, can we just expose a function unique_ptr<CommentHandler> collectHeaderMaps(HeaderMapCollector*)?

clangd/global-symbol-builder/STLPostfixHeaderMap.h

1 ↗

(On Diff #131782)

STL isn't really a name we want to be using :-)

Why isn't this in HeaderMapCollector.h?

clangd/index/HeaderMapCollector.h

9 ↗

(On Diff #131782)

context! what are header mappings, why do we use them (example)

23 ↗

(On Diff #131782)

I'm not sure "header mapping" is as descriptive as it should be, and "collector':

• we're mapping *to a canonical* representation
• the context is "how should we spell this in a #include"

"Collector" doesn't really describe the class - it both records and applies rules.

Maybe CanonicalIncludes?

25 ↗

(On Diff #131782)

these public typedefs and the explicit constructor seem leaky. Maybe just expose a public function addStandardLibraryMapping(CanonicalIncludes*)?

31 ↗

(On Diff #131782)

nit: just addMapping?

41 ↗

(On Diff #131782)

nit: just mapHeader?

41 ↗

(On Diff #131782)

what's the input? absolute path? working-directory-relative? include-path relative?

Similarly, what's the output?

(This also relates to addHeaderMapping, so might belong in the class desc)

48 ↗

(On Diff #131782)

This comment and the mutable are scary. We don't need to be threadsafe I think?

50 ↗

(On Diff #131782)

all the rules we have so far are suffix matches. It seems a little weird to allow arbitrary regexes (and prevents fast lookup by sorting the reversed strings).

But it's a small amount of code and I guess the table will stay small. Maybe a FIXME that performance could be improved here?

clangd/index/Index.h

160

I think we concluded this shouldn't be a URI but a literal include string. If absent, we should fall back to CanonicalDeclaration.

The reason is that we choose to interpret the target of IWYU directives as a literal string to include. Alternatively we could choose to resolve it somehow and store the URI to the resolved target, but that would be more work.

clangd/index/SymbolCollector.cpp

134

shouldn't this just be return SK != Namespace, to avoid duplication? Since we only get here if we're indexing this symbol?

[sammccall]

clangd/ClangdServer.cpp

321

Pull out a function to compute ToInclude from a uri/abspath?

328

Need high-level comments explaining what we're doing to determine the right include path.

336

temporary logs?

348

explain why? (this has implications for direct vs transitive includes I think)

350

hmm, why are we actually going to run the compiler/preprocessor?
It looks like we just get HeaderMapping out - can we "just" call ApplyHeaderSearchOptions instead?

368

do we handle the case that the suggestion is already included?
(including the case where it's included by a different name)

371

leftover?

393

maybe this fixme should just be to have more consistent style support in clangdserver?

[ioeric]

• Merge with origin/master
• Renamed and moved a bunch files according to review comments.
• Merge remote-tracking branch 'origin/master' into include
• Half way
• Merge with uri changes.
• merged with origin/master
• Merge with origin/master
• s/HeaderUri/IncludeURI/

[ioeric]

Thanks for the comments! I addressed comments in the symbol collect part (I think?). Will add tests in a followup patch.

clangd/index/HeaderMapCollector.h

48 ↗

(On Diff #131782)

mutable was here because of llvm::Regex. Matching again a llvm::Regex is not a constant operation, but we would still like the lookup function to be const.

clangd/index/Index.h

160

In our latest offline discussion, we concluded that this would be either URI of a file (in .inc case) or a literal string that is suitable to be inserted. I left resolving IWYU targets as a FIXME in this patch as it is more work and doesn't seem to cause any trouble at this point. Will revisit when it actually becomes a problem.

clangd/index/SymbolCollector.cpp

134

I think it'd be easier to justify the behavior with a white list. There are other symbols like NamespaceAlias etc, which we might or might not be collecting.

[ioeric]

This comment was removed by ioeric.

[ioeric]

• Added tests for IncludeURI and CanonicalIncludes and minor cleanup.

[ioeric]

• Merge with origin/master

[ioeric]

• Added tests for all components; more cleanup; s/IncludeURI/IncludeHeader/

[ioeric]

Thanks for the comments!

Sorry that I didn't clean up the code before sending out the prototype. I planned to deal with code structure and style issues after getting some early feedback, but I think the patch is ready for review now.

clangd/ClangdServer.cpp

348

Since we only need predecessor for HeaderSearch and don't really care about the actual code, I set this to false in the hope of speeding up the code. But in the latest revision, I simply use an empty file (as we only care about header search), so this option is no longer necessary.

350

I couldn't find an easy way to use ApplyHeaderSearchOptions... It requires an instance of HeaderSearch, which needs a preprocessor and a bunch of other objects (SourceManager, Target etc). And these objects are mostly initialized in BeginSourceFile. We could probably pull out the code that only initializes up to proprocessor, but this is not very trivial :(

368

Yes and no. The current implementation only does textual matching against existing #includes in the current file and inserts the header if no same header was found. This complies with IWYU. But we are not handling the case where the same header is included by different names. I added a FIXME for this.

clangd/CodeComplete.cpp

859

Passing filename to the constructor sounds good. Thanks!

[sammccall]

Some comments on the insert side, which looks pretty good. I'll take another look at indexing tomorrow.

clangd/ClangdServer.cpp

314

This has a fair amount of logic (well, plumbing :-D) and uses relatively little from ClangdServer.
Can we move shortenIncludePath to a separate file and pass in the FS and command?

I'd suggest maybe Headers.h - The formatting part of insertInclude could also fit there, as well as probably the logic from switchSourceHeader I think (the latter not in this patch of course).

This won't really help much with testing, I just find it gets hard to navigate files that have lots of details of unrelated features. ClangdUnit and ClangdServer both have this potential to grow without bound, though they're in reasonable shape now. Interested what you think!

316

maybe drop "via clang::HeaderSearch" (it's doc'd in the implementation) and add an example?

It might be worth explicitly stating that the result is an #include string (with quotes) - you just call it a "path" here.

"shortest" makes sense as a first implementation, but we may want to document something more like "best" - I know there are codebases we care about where file-relative paths are banned. Also I suspect we don't give "../../../../Foo.h" even if it's shortest :-)

325

This comment helps a lot. The subtext is: HeaderSearch is hard to construct directly, so we're doing this weird dance.
I think this is worth calling out even louder - when I read this sort of code I tend to take a *long* time to work out why the code seems to be doing unrelated work.

366

consume the optional IsSystem and use it to quote appropriately?

368

I can't see the FIXME? (There's one in the header, but it doesn't seem to really cover this case)

So this doesn't seem so hard: we can pass the file content, turn off recursive PP, and add PP callbacks to capture the names of each included file (the include-scanner patch does this).
I'm not sure it's worth deferring, at least we should fix it soon before we lose context.

But up to you, I'd suggest putting the fixme where we expect to fix it.

unittests/clangd/ClangdTests.cpp

821

Similarly, it'd be nice to pull these tests out into a test file parallel to the header.
(As with the other tests, often it's easiest to actually test through the ClangdServer interface - this is mostly just for navigation)

[ioeric]

• Addressed review comments.

[ioeric]

Thanks! PTAL

clangd/ClangdServer.cpp

314

Done.

I didn't move the formatting code, as half of the code is pulling out the style, which we might want to share/change depending on other clangd logics that might use style.

368

Since you prefer, I have included the change in the patch. I wanted to get to this as soon as this patch is landed.

unittests/clangd/ClangdTests.cpp

821

Done. I left a simple test for replacements.

[ioeric]

• fix a leftover bug

[sammccall]

Insertion side LGTM, feel free to split and land.
Sorry I need to take off and will need to get to indexing on monday :(

clangd/ClangdServer.cpp

314

I'd still think pulling out Expected<tooling::Replacement> insertInclude(File, Code, Header, VFS, Style) would be worthwhile here - the formatting isn't a lot of code, but it's a bit magic, plus the quote handling... it's a bit of code. It'd make it more obvious what the interactions with ClangdServer's state are. But up to you, we can always do this later.

316

"shortest" makes sense as a first implementation, but we may want to document something more like "best" - I know there are codebases we care about where file-relative paths are banned. Also I suspect we don't give "../../../../Foo.h" even if it's shortest :-)

I think this part wasn't addressed

clangd/Headers.cpp

75

comment is outdated now

115

can you include the Header in this log message? (and possibly File, but that might add more noise than signal)

clangd/Headers.h

31

header-already-included is not an error condition.

Suggest returning llvm::Expected<Optional<String>>, or returning "" for this case.

[ioeric]

• Addressed review comments.

clangd/ClangdServer.cpp

314

So it's just 2 lines for the replacement magic (+1 for comment) now after removing some redundant code.

I like shortenIncludePath better because it's more self-contained and easier to write tests against, and insertInclude doesn't seem to carry much more weight while we would need to handle replacements logic which has been tested in the tests.

316

I added a comment for this in the header. But I might be misunderstanding you suggestion. Did you mean we need a better name for the function?

[sammccall]

Insertion still LG (couple of nits, inline).

For indexing, my biggest questions:

• I worry CanonicalIncludes doesn't get enough information to make good decisions - passing the include stack in some form may be better
• CanonicalIncludes has slightly weird patterns of reads/writes - most writes are permanent and a few are transient, and it's not totally obvious how it works in a multithreading context (though your code is correct). I'm not sure whether this is worth fixing.

clangd/ClangdServer.cpp

316

I think the function name is fine as a shorthand, just that the comment is a bit overspecified and possibly inaccurate compared to e.g. "Determines the preferred way to #include a file, taking into account the search path. Usually this will prefer a shorter representation like 'Foo/Bar.h' over a longer one like 'Baz/include/Foo/Bar.h'".

I don't think the ../../../Foo.h case is worth explicitly calling out - I just meant it as an example of why we *don't* want an overly-specific contract here.

clangd/CodeComplete.cpp

290

whether

301

user-facing. unwrap?

clangd/clients/clangd-vscode/package.json

1 ↗

(On Diff #133635)

phab says you have ws-only changes in this file, which you might want to revert

clangd/global-symbol-builder/CMakeLists.txt

1 ↗

(On Diff #133635)

(and here - ws-only changes?)

clangd/global-symbol-builder/GlobalSymbolBuilderMain.cpp

102

Do we create one of these per TU or per thread? The former is "clean" but seems potentially wasteful (compiling all those system header regexes for each TU). The latter is "fast" but potentially non-hermetic (can't think of a triggering case though).

Maybe we should have a split between transient mappings (IWYU) and permanent ones?

clangd/index/CanonicalIncludes.cpp

52

I think this is

if (!Text.consume_front(IWYUPragma))
return false;

73

"STL" :-)

75

these aren't standard library - deserves a comment?

in general it looks like there's a bunch of standard library stuff, also posix stuff, and some compiler intrinsics.
If this is the case, maybe "system headers" is a better descriptor than "standard library".

Can we document approximately which standard libraries, which compiler extensions, and other standards (posix, but I guess windows one day) are included?

clangd/index/CanonicalIncludes.h

11

Can we split out the main ideas a bit? I think these are: a) what include mapping is, b) IWYU pragmas, c) standard library.
We should also probably call out the relationship with the stuff in clangd/Headers.h.

e.g.

At indexing time, we decide which file to #included for a symbol.
Usually this is the file with the canonical decl, but there are exceptions:

- private headers may have pragmas pointing to the matching public header.
  (These are "IWYU" pragmas, named after the include-what-you-use tool).
- the standard library is implemented in many files, without any pragmas. 
  We have a lookup table for common standard library implementations.
  libstdc++ puts char_traits in bits/char_traits.h, but we #include <string>.

The insert-time logic in clang/Headers.h chooses how to spell the
filename we emit here; this depends on the search path at the insertion site.

(I think .inc files are conceptually similar and should also be handled and mentioned here, commented below)

33

nit: \brief needed?

I'm not sure this class actually collects anything - that's the handler returned by collectIWYUHeaderMaps.

Maybe "Maps a definition location onto an #include file, based on a set of filename rules."?

45

Maps all files matching \p RE to \p CanonicalPath?

51

Just this comment is probably enough for the whole function...

53

So I'm a bit concerned this is too narrow an interface, and we really want to deal with SourceLocation here which would give us the include stack.

Evidence #1: .inc handling really is the same job, but because this class has a single-file interface, we have to push it into the caller.
Evidence #2: I was thinking about a more... principled way of determining system headers. One option would be to have a whitelist of public headers, and walk up the include stack to see if you hit one. (I'm not 100% sure this would work, but still...) This isn't implementable with the current interface.

One compromise would be to pass in a stack<StringRef> or something. Efficiency doesn't really matter because the caller can cache based on the top element.

57

do we need both tables? it seems the system headers (which are regex-based) will typically outnumber the IWYU pragmas by a bunch.
And if we care about performance at all, we can cache the results of mapHeader?

68

Explicitly mention that the mappings are registered with *Includes?

(interaction isn't totally obvious here because Includes has read and write methods)

clangd/index/SymbolCollector.h

46

const?

[ioeric]

• Addressed some review comments.

clangd/ClangdServer.cpp

316

I see. Thanks!

clangd/global-symbol-builder/GlobalSymbolBuilderMain.cpp

102

This is created per TU now. In an earlier revision, this was one-per-program because we statically constructed a regex map and passed the map into the CanonicalIncludes via the constructor, like we do in include-fixer (https://github.com/llvm-mirror/clang-tools-extra/blob/master/include-fixer/find-all-symbols/STLPostfixHeaderMap.cpp#L15). But with the current design, I didn't do this because one-per-TU approach seems to be cleaner, and the regex construction time seems to be relatively small comparing to the time spent on actually compiling a TU.

If we really want to squeeze performance here, we would probably need either an interface that takes a static regex mapping or one that takes pre-computed llvm::Regex. But I'm not really sure if it would be worth it since this is not a performance critical code path.

clangd/index/CanonicalIncludes.cpp

75

Switched both function and variable to "system headers" and updated the documentation.

clangd/index/CanonicalIncludes.h

11

Thanks for the suggestion!

We should also probably call out the relationship with the stuff in clangd/Headers.h.

I'm a bit inclined to not call out the relationship here as this doesn't seem to be a better place than the code where they interact, and the doc could easily be outdated if the interaction is changed from other libraries.

53

Evidence #1: .inc handling really is the same job, but because this class has a single-file interface, we have to push it into the caller.

I think this would depend on how you define the scope of this class. .inc handling is a subtle case that I'm a bit hesitated to build into the interface here.

Evidence #2: ....

This is actually very similar to how the hardcoded mapping was generated. I had a tool that examined include stacks for a library (e.g. STL) and applied a similar heuristic - treat the last header in the include stack within the library boundary as the "exporting" public header for a leaf include header, if there is no other public header that has shorter distance to that include. For example, if we see a stack like stl/bits/internal.h -> stl/bits/another.h -> stl/public_1.h -> user_code.cc, we say public_1.h exports bits/internal.h and add a mapping from bits/internal.h$ to public_1.h. But if we see another (shorter) include stack like stl/bits/internal.h -> stl/public_2.h -> user_code.cc, we say stl/public_2.h exports stl/bits/internal.h. This heuristic works well for many cases. However, this may produce wrong mappings when an internal header is used by multiple public headers. For example, if we have two include stacks with the same length e.g. bits/internal.h -> public_1.h -> user.cc and bits/inernal.h -> public_2.h -> user.cc, the result mapping would depend on the order in which we see these two stacks; thus, we had to do some manual adjustment to make sure bits/internal.h is mapped to the correct header according to the standard.

I am happy to discuss better solution here. But within the scope of this patch, I'd prefer to stick to interfaces that work well for the current working solution instead of designing for potential future solutions. I should be easy to iterate on the interfaces as these interfaces aren't going to be widely used in clangd after all. WDYT?

57

Makes sense.

[ioeric]

• Merged with origin/master

[sammccall]

LG apart from the .inc handling (happy to chat more)

clangd/index/CanonicalIncludes.h

53

I think this would depend on how you define the scope of this class. .inc handling is a subtle case that I'm a bit hesitated to build into the interface here.

Sure it's subtle, but it's clearly in the scope of determining what the canonical header is for a symbol, which is the job of this class. We wouldn't be building it into the interface - on the contrary, the *current* proposed interface codifies *not* handling .inc files.

But you're right that we should check in something that handles most cases.

My preference would be to drop .inc from this patch until we can incorporate it into the design, but I'm also OK with a FIXME to move it.

unittests/clangd/HeadersTests.cpp

30

This test would be clearer to me if you removed this helper and just did

FS.Files["sub/bar.h"] = ...

in the test.

Can we change buildTestFS in TestFS.cpp to call getVirtualTestFilePath on relative paths to allow this?

(I can do this as a followup if you like, but it seems like a trivial change)

unittests/clangd/SymbolCollectorTests.cpp

50

nit: this is only used once, as Not(HasIncludeHeader()). Just use IncludeHeader("")?
The slight difference in detail handling doesn't seem to matter (I'm not even sure if it's exactly the right assertion)

620

Took me a while to understand this test, and still not sure I get it. Maybe "class string" here?

[sammccall]

unittests/clangd/HeadersTests.cpp

30

I thought better of that change to TestFS, but did some renames in r325326.

So this would be FS.Files[testPath("sub/bar.h")) = ... which still seems more transparent - up to you.

[ioeric]

• Merged with origin/master
• Addressed review comments; removed .inc handling.

[ioeric]

Thank you for reviewing this!

clangd/index/CanonicalIncludes.h

53

Okay, I removed .inc handling from this patch ;)

unittests/clangd/HeadersTests.cpp

30

Thanks a lot!

[CarlosAlbertoEnciso]

Hi @ioeric:

Just to let you know that your submission seems to break a Windows test.

 FAIL: Extra Tools Unit Tests :: clangd/Checking/./ClangdTests.exe/SymbolCollectorTest.IWYUPragma (15474 of 36599)

C:\xxx\llvm\tools\clang\tools\extra\unittests\clangd\SymbolCollectorTests.cpp(620): error : Value of: Symbols [C:\xxx\build\check-all.vcxproj]

  Expected: has 1 element and that element (q name "Foo") and ((decl u r i "file:///C%3a/clangd-test/symbol.h") and (include header "\"the/good/header.h\""))

    Actual: { Foo }, where the following matchers don't match any elements:

  matcher #0: (q name "Foo") and ((decl u r i "file:///C%3a/clangd-test/symbol.h") and (include header "\"the/good/header.h\""))

  and where the following elements don't match any matchers:

  element #0: Foo

  [  FAILED  ] SymbolCollectorTest.IWYUPragma (113 ms)

  [----------] 1 test from SymbolCollectorTest (113 ms total)

Thanks

[CarlosAlbertoEnciso]

Thanks @aheejin

clangd/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Support
   )
 
 add_clang_library(clangDaemon
   ClangdLSPServer.cpp
   ClangdServer.cpp
   ClangdUnit.cpp
   CodeComplete.cpp
   CodeCompletionStrings.cpp
   CompileArgsCache.cpp
   Compiler.cpp
   Context.cpp
   DraftStore.cpp
   FuzzyMatch.cpp
   GlobalCompilationDatabase.cpp
+  Headers.cpp
   JSONExpr.cpp
   JSONRPCDispatcher.cpp
   Logger.cpp
   Protocol.cpp
   ProtocolHandlers.cpp
   SourceCode.cpp
   Threading.cpp
   Trace.cpp
   TUScheduler.cpp
   URI.cpp
   XRefs.cpp
+  index/CanonicalIncludes.cpp
   index/FileIndex.cpp
   index/Index.cpp
   index/MemIndex.cpp
   index/Merge.cpp
   index/SymbolCollector.cpp
   index/SymbolYAML.cpp
 
   LINK_LIBS

clangd/ClangdLSPServer.cpp

reply(json::obj{
              json::obj{
                  {"triggerCharacters", {"(", ","}},
              }},
             {"definitionProvider", true},
             {"documentHighlightProvider", true},
             {"renameProvider", true},
             {"executeCommandProvider",
              json::obj{
-                 {"commands", {ExecuteCommandParams::CLANGD_APPLY_FIX_COMMAND}},
+                 {"commands",
+                  {ExecuteCommandParams::CLANGD_APPLY_FIX_COMMAND,
+                   ExecuteCommandParams::CLANGD_INSERT_HEADER_INCLUDE}},
              }},
         }}}});
 }
 
 void ClangdLSPServer::onShutdown(ShutdownParams &Params) {
   // Do essentially nothing, just say we're ready to exit.
   ShutdownRequestReceived = true;
   reply(nullptr);
Server.addDocument(Params.textDocument.uri.file(),
                      Params.contentChanges[0].text);
 }
 
 void ClangdLSPServer::onFileEvent(DidChangeWatchedFilesParams &Params) {
   Server.onFileEvent(Params);
 }
 
 void ClangdLSPServer::onCommand(ExecuteCommandParams &Params) {
+  auto ApplyEdit = [](WorkspaceEdit WE) {
+    ApplyWorkspaceEditParams Edit;
+    Edit.edit = std::move(WE);
+    // We don't need the response so id == 1 is OK.
+    // Ideally, we would wait for the response and if there is no error, we
+    // would reply success/failure to the original RPC.
+    call("workspace/applyEdit", Edit);
+  };
   if (Params.command == ExecuteCommandParams::CLANGD_APPLY_FIX_COMMAND &&
       Params.workspaceEdit) {
     // The flow for "apply-fix" :
     // 1. We publish a diagnostic, including fixits
     // 2. The user clicks on the diagnostic, the editor asks us for code actions
     // 3. We send code actions, with the fixit embedded as context
     // 4. The user selects the fixit, the editor asks us to apply it
     // 5. We unwrap the changes and send them back to the editor
     // 6. The editor applies the changes (applyEdit), and sends us a reply (but
     // we ignore it)
 
-    ApplyWorkspaceEditParams ApplyEdit;
-    ApplyEdit.edit = *Params.workspaceEdit;
     reply("Fix applied.");
-    // We don't need the response so id == 1 is OK.
-    // Ideally, we would wait for the response and if there is no error, we
-    // would reply success/failure to the original RPC.
-    call("workspace/applyEdit", ApplyEdit);
+    ApplyEdit(*Params.workspaceEdit);
+  } else if (Params.command ==
+             ExecuteCommandParams::CLANGD_INSERT_HEADER_INCLUDE) {
+    auto &FileURI = Params.includeInsertion->textDocument.uri;
+    auto Code = Server.getDocument(FileURI.file());
+    if (!Code)
+      return replyError(ErrorCode::InvalidParams,
+                        ("command " +
+                         ExecuteCommandParams::CLANGD_INSERT_HEADER_INCLUDE +
+                         " called on non-added file " + FileURI.file())
+                            .str());
+    auto Replaces = Server.insertInclude(FileURI.file(), *Code,
+                                         Params.includeInsertion->header);
+    if (!Replaces) {
+      std::string ErrMsg =
+          ("Failed to generate include insertion edits for adding " +
+           Params.includeInsertion->header + " into " + FileURI.file())
+              .str();
+      log(ErrMsg + ":" + llvm::toString(Replaces.takeError()));
+      replyError(ErrorCode::InternalError, ErrMsg);
+      return;
+    }
+    auto Edits = replacementsToEdits(*Code, *Replaces);
+    WorkspaceEdit WE;
+    WE.changes = {{FileURI.uri(), Edits}};
+
+    reply("Inserted header " + Params.includeInsertion->header);
+    ApplyEdit(std::move(WE));
   } else {
     // We should not get here because ExecuteCommandParams would not have
     // parsed in the first place and this handler should not be called. But if
     // more commands are added, this will be here has a safe guard.
     replyError(
         ErrorCode::InvalidParams,
         llvm::formatv("Unsupported command \"{0}\".", Params.command).str());
   }

clangd/ClangdServer.h

public:
   formatOnType(StringRef Code, PathRef File, Position Pos);
 
   /// Rename all occurrences of the symbol at the \p Pos in \p File to
   /// \p NewName.
   void rename(PathRef File, Position Pos, llvm::StringRef NewName,
               UniqueFunction<void(Expected<std::vector<tooling::Replacement>>)>
                   Callback);
 
+  /// Inserts a new #include of \p Header into \p File, if it's not present.
+  /// \p Header is either an URI that can be resolved to an #include path that
+  /// is suitable to be inserted or a literal string quoted with <> or "" that
+  /// can be #included directly.
+  Expected<tooling::Replacements> insertInclude(PathRef File, StringRef Code,
+                                                StringRef Header);
+
   /// Gets current document contents for \p File. Returns None if \p File is not
   /// currently tracked.
   /// FIXME(ibiryukov): This function is here to allow offset-to-Position
   /// conversions in outside code, maybe there's a way to get rid of it.
   llvm::Optional<std::string> getDocument(PathRef File);
 
   /// Only for testing purposes.
   /// Waits until all requests to worker thread are finished and dumps AST for

clangd/ClangdServer.cpp

 //===--- ClangdServer.cpp - Main clangd server code --------------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===-------------------------------------------------------------------===//
 
 #include "ClangdServer.h"
 #include "CodeComplete.h"
+#include "Headers.h"
 #include "SourceCode.h"
 #include "XRefs.h"
 #include "index/Merge.h"
 #include "clang/Format/Format.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Frontend/CompilerInvocation.h"
 #include "clang/Tooling/CompilationDatabase.h"
 #include "clang/Tooling/Refactoring/RefactoringResultConsumer.h"
auto Action = [Pos](Path File, std::string NewName,
     return Callback(Replacements);
   };
 
   WorkScheduler.runWithAST(
       File,
       BindWithForward(Action, File.str(), NewName.str(), std::move(Callback)));
 }
 
+Expected<tooling::Replacements>
+ClangdServer::insertInclude(PathRef File, StringRef Code,
+                            llvm::StringRef Header) {
+  std::string ToInclude;
+  if (Header.startswith("<") || Header.startswith("\"")) {
+    ToInclude = Header;
+  } else {
+    auto U = URI::parse(Header);
+    if (!U)
+      return U.takeError();
+    auto Resolved = URI::resolve(*U, /*HintPath=*/File);
+    if (!Resolved)
+      return Resolved.takeError();
+
+    auto FS = FSProvider.getTaggedFileSystem(File).Value;
+    tooling::CompileCommand CompileCommand =
+        CompileArgs.getCompileCommand(File);
+    FS->setCurrentWorkingDirectory(CompileCommand.Directory);
+
+    auto Include =
+        shortenIncludePath(File, Code, *Resolved, CompileCommand, FS);
+    if (!Include)
+      return Include.takeError();
+    if (Include->empty())
+      return tooling::Replacements();
+    ToInclude = std::move(*Include);
+  }
+
+  auto Style = format::getStyle("file", File, "llvm");
+  if (!Style) {
+    llvm::consumeError(Style.takeError());
+    // FIXME(ioeric): needs more consistent style support in clangd server.
+    Style = format::getLLVMStyle();
+  }
+  // Replacement with offset UINT_MAX and length 0 will be treated as include
+  // insertion.
+  tooling::Replacement R(File, /*Offset=*/UINT_MAX, 0, "#include " + ToInclude);
+  return format::cleanupAroundReplacements(Code, tooling::Replacements(R),
+                                           *Style);
+}
+
 llvm::Optional<std::string> ClangdServer::getDocument(PathRef File) {
   auto Latest = DraftMgr.getDraft(File);
   if (!Latest.Draft)
     return llvm::None;
   return std::move(*Latest.Draft);
 }
 
 void ClangdServer::dumpAST(PathRef File,
                            UniqueFunction<void(std::string)> Callback) {
   auto Action = [](decltype(Callback) Callback,
                    llvm::Expected<InputsAndAST> InpAST) {
     if (!InpAST) {
       ignoreError(InpAST.takeError());
       return Callback("<no-ast>");
     }
     std::string Result;
 
     llvm::raw_string_ostream ResultOS(Result);
     clangd::dumpAST(InpAST->AST, ResultOS);
     ResultOS.flush();
 
     Callback(Result);
   };
 
   WorkScheduler.runWithAST(File, BindWithForward(Action, std::move(Callback)));
 }
 
 void ClangdServer::findDefinitions(
     PathRef File, Position Pos,
     UniqueFunction<void(llvm::Expected<Tagged<std::vector<Location>>>)>
         Callback) {
   auto TaggedFS = FSProvider.getTaggedFileSystem(File);
   auto Action = [Pos, TaggedFS](decltype(Callback) Callback,
                                 llvm::Expected<InputsAndAST> InpAST) {
     if (!InpAST)
       return Callback(InpAST.takeError());
     auto Result = clangd::findDefinitions(InpAST->AST, Pos);
     Callback(make_tagged(std::move(Result), TaggedFS.Tag));
   };
 
   WorkScheduler.runWithAST(File, BindWithForward(Action, std::move(Callback)));
 }
 
 llvm::Optional<Path> ClangdServer::switchSourceHeader(PathRef Path) {
 
   StringRef SourceExtensions[] = {".cpp", ".c", ".cc", ".cxx",
                                   ".c++", ".m", ".mm"};

clangd/CodeComplete.cpp

 //
 //===---------------------------------------------------------------------===//
 
 #include "CodeComplete.h"
 #include "CodeCompletionStrings.h"
 #include "Compiler.h"
 #include "FuzzyMatch.h"
 #include "Logger.h"
+#include "SourceCode.h"
 #include "Trace.h"
 #include "index/Index.h"
+#include "clang/Format/Format.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Frontend/FrontendActions.h"
 #include "clang/Index/USRGeneration.h"
 #include "clang/Sema/CodeCompleteConsumer.h"
 #include "clang/Sema/Sema.h"
+#include "clang/Tooling/Core/Replacement.h"
 #include "llvm/Support/Format.h"
 #include <queue>
 
 namespace clang {
 namespace clangd {
 namespace {
 
 CompletionItemKind toCompletionItemKind(CXCursorKind CursorKind) {
float score() const {
     case CXAvailability_NotAvailable:
       Score = 0;
       break;
     }
     return Score;
   }
 
   // Builds an LSP completion item.
-  CompletionItem build(const CompletionItemScores &Scores,
+  CompletionItem build(llvm::StringRef FileName,
+                       const CompletionItemScores &Scores,
                        const CodeCompleteOptions &Opts,
                        CodeCompletionString *SemaCCS) const {
     assert(bool(SemaResult) == bool(SemaCCS));
     CompletionItem I;
     if (SemaResult) {
       I.kind = toCompletionItemKind(SemaResult->Kind, SemaResult->CursorKind);
       getLabelAndInsertText(*SemaCCS, &I.label, &I.insertText,
                             Opts.EnableSnippets);
if (IndexResult) {
                            ? IndexResult->CompletionSnippetInsertText
                            : IndexResult->CompletionPlainInsertText;
 
       if (auto *D = IndexResult->Detail) {
         if (I.documentation.empty())
           I.documentation = D->Documentation;
         if (I.detail.empty())
           I.detail = D->CompletionDetail;
+        // We only insert #include for items with details, since we can't tell
+        // whether the file URI of the canonical declaration would be the
+        // canonical #include without checking IncludeHeader in the detail.
+        // FIXME: delay creating include insertion command to
+        // "completionItem/resolve", when it is supported
+        if (!D->IncludeHeader.empty() ||
+            !IndexResult->CanonicalDeclaration.FileURI.empty()) {
+          // LSP favors additionalTextEdits over command. But we are still using
+          // command here because it would be expensive to calculate #include
+          // insertion edits for all candidates, and the include insertion edit
+          // is unlikely to conflict with the code completion edits.
+          Command Cmd;
+          // Command title is not added since this is not a user-facing command.
+          Cmd.command = ExecuteCommandParams::CLANGD_INSERT_HEADER_INCLUDE;
+          IncludeInsertion Insertion;
+          Insertion.header = D->IncludeHeader.empty()
+                                 ? IndexResult->CanonicalDeclaration.FileURI
+                                 : D->IncludeHeader;
+          Insertion.textDocument.uri = URIForFile(FileName);
+          Cmd.includeInsertion = std::move(Insertion);
+          I.command = std::move(Cmd);
+        }
       }
     }
     I.scoreInfo = Scores;
     I.sortText = sortText(Scores.finalScore, Name);
     I.insertTextFormat = Opts.EnableSnippets ? InsertTextFormat::Snippet
                                              : InsertTextFormat::PlainText;
     return I;
   }

 //   - CompletionCandidates are the result of merging Sema and Index results.
 //     Each candidate points to an underlying CodeCompletionResult (Sema), a
 //     Symbol (Index), or both. It computes the result quality score.
 //     CompletionCandidate also does conversion to CompletionItem (at the end).
 //   - FuzzyMatcher scores how the candidate matches the partial identifier.
 //     This score is combined with the result quality score for the final score.
 //   - TopN determines the results with the best score.
 class CodeCompleteFlow {
+  PathRef FileName;
   const CodeCompleteOptions &Opts;
   // Sema takes ownership of Recorder. Recorder is valid until Sema cleanup.
   std::unique_ptr<CompletionRecorder> RecorderOwner;
   CompletionRecorder &Recorder;
   int NSema = 0, NIndex = 0, NBoth = 0; // Counters for logging.
   bool Incomplete = false; // Would more be available with a higher limit?
   llvm::Optional<FuzzyMatcher> Filter; // Initialized once Sema runs.
 
 public:
   // A CodeCompleteFlow object is only useful for calling run() exactly once.
-  CodeCompleteFlow(const CodeCompleteOptions &Opts)
-      : Opts(Opts), RecorderOwner(new CompletionRecorder(Opts)),
-        Recorder(*RecorderOwner) {}
+  CodeCompleteFlow(PathRef FileName, const CodeCompleteOptions &Opts)
+      : FileName(FileName), Opts(Opts),
+        RecorderOwner(new CompletionRecorder(Opts)), Recorder(*RecorderOwner) {}
 
   CompletionList run(const SemaCompleteInput &SemaCCInput) && {
     trace::Span Tracer("CodeCompleteFlow");
     // We run Sema code completion first. It builds an AST and calculates:
     //   - completion results based on the AST. These are saved for merging.
     //   - partial identifier and context. We need these for the index query.
     CompletionList Output;
     semaCodeComplete(std::move(RecorderOwner), Opts.getClangCompleteOpts(),
                      SemaCCInput, [&] {
                        if (Recorder.CCSema)
                          Output = runWithSema();
                        else
                          log("Code complete: no Sema callback, 0 results");
                      });
 
     SPAN_ATTACH(Tracer, "sema_results", NSema);
     SPAN_ATTACH(Tracer, "index_results", NIndex);
     SPAN_ATTACH(Tracer, "merged_results", NBoth);
     SPAN_ATTACH(Tracer, "returned_results", Output.items.size());
void addCandidate(TopN &Candidates, const CodeCompletionResult *SemaResult,
     Incomplete |= Candidates.push({C, Scores});
   }
 
   CompletionItem toCompletionItem(const CompletionCandidate &Candidate,
                                   const CompletionItemScores &Scores) {
     CodeCompletionString *SemaCCS = nullptr;
     if (auto *SR = Candidate.SemaResult)
       SemaCCS = Recorder.codeCompletionString(*SR, Opts.IncludeBriefComments);
-    return Candidate.build(Scores, Opts, SemaCCS);
+    return Candidate.build(FileName, Scores, Opts, SemaCCS);
   }
 };
 
 CompletionList codeComplete(PathRef FileName,
                             const tooling::CompileCommand &Command,
                             PrecompiledPreamble const *Preamble,
                             StringRef Contents, Position Pos,
                             IntrusiveRefCntPtr<vfs::FileSystem> VFS,
                             std::shared_ptr<PCHContainerOperations> PCHs,
                             CodeCompleteOptions Opts) {
-  return CodeCompleteFlow(Opts).run(
-      {FileName, Command, Preamble, Contents, Pos, VFS, PCHs});
+  return CodeCompleteFlow(FileName, Opts)
+      .run({FileName, Command, Preamble, Contents, Pos, VFS, PCHs});
 }
 
 SignatureHelp signatureHelp(PathRef FileName,
                             const tooling::CompileCommand &Command,
                             PrecompiledPreamble const *Preamble,
                             StringRef Contents, Position Pos,
                             IntrusiveRefCntPtr<vfs::FileSystem> VFS,
                             std::shared_ptr<PCHContainerOperations> PCHs) {

clangd/Headers.h

+//===--- Headers.h - Include headers -----------------------------*- C++-*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_HEADERS_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_HEADERS_H
+
+#include "Path.h"
+#include "clang/Basic/VirtualFileSystem.h"
+#include "clang/Tooling/CompilationDatabase.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Error.h"
+
+namespace clang {
+namespace clangd {
+/// Determines the preferred way to #include a file, taking into account the
+/// search path. Usually this will prefer a shorter representation like
+/// 'Foo/Bar.h' over a longer one like 'Baz/include/Foo/Bar.h'.
+///
+/// \param Header is an absolute file path.
+/// \return A quoted "path" or <path>. If \p Header is already (directly)
+/// included in the file (including those included via different paths), this
+/// returns an empty string.
+llvm::Expected<std::string>
+shortenIncludePath(PathRef File, llvm::StringRef Code, llvm::StringRef Header,
+                   const tooling::CompileCommand &CompileCommand,
+                   IntrusiveRefCntPtr<vfs::FileSystem> FS);
+
+} // namespace clangd
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_HEADERS_H

clangd/Headers.cpp

+//===--- Headers.cpp - Include headers ---------------------------*- C++-*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "Headers.h"
+#include "Compiler.h"
+#include "Logger.h"
+#include "clang/Frontend/CompilerInstance.h"
+#include "clang/Frontend/CompilerInvocation.h"
+#include "clang/Frontend/FrontendActions.h"
+#include "clang/Lex/HeaderSearch.h"
+#include "clang/Lex/PreprocessorOptions.h"
+#include "clang/Tooling/CompilationDatabase.h"
+
+namespace clang {
+namespace clangd {
+namespace {
+
+class RecordHeaders : public PPCallbacks {
+public:
+  RecordHeaders(std::set<std::string> &Headers) : Headers(Headers) {}
+
+  void InclusionDirective(SourceLocation /*HashLoc*/,
+                          const Token & /*IncludeTok*/,
+                          llvm::StringRef /*FileName*/, bool /*IsAngled*/,
+                          CharSourceRange /*FilenameRange*/,
+                          const FileEntry *File, llvm::StringRef /*SearchPath*/,
+                          llvm::StringRef /*RelativePath*/,
+                          const Module * /*Imported*/) override {
+    if (File != nullptr && !File->tryGetRealPathName().empty())
+      Headers.insert(File->tryGetRealPathName());
+  }
+
+private:
+  std::set<std::string> &Headers;
+};
+
+} // namespace
+
+/// FIXME(ioeric): we might not want to insert an absolute include path if the
+/// path is not shortened.
+llvm::Expected<std::string>
+shortenIncludePath(llvm::StringRef File, llvm::StringRef Code,
+                   llvm::StringRef Header,
+                   const tooling::CompileCommand &CompileCommand,
+                   IntrusiveRefCntPtr<vfs::FileSystem> FS) {
+  // Set up a CompilerInstance and create a preprocessor to collect existing
+  // #include headers in \p Code. Preprocesor also provides HeaderSearch with
+  // which we can calculate the shortest include path for \p Header.
+  std::vector<const char *> Argv;
+  for (const auto &S : CompileCommand.CommandLine)
+    Argv.push_back(S.c_str());
+  IgnoringDiagConsumer IgnoreDiags;
+  auto CI = clang::createInvocationFromCommandLine(
+      Argv,
+      CompilerInstance::createDiagnostics(new DiagnosticOptions(), &IgnoreDiags,
+                                          false),
+      FS);
+  if (!CI)
+    return llvm::make_error<llvm::StringError>(
+        "Failed to create a compiler instance for " + File,
+        llvm::inconvertibleErrorCode());
+  CI->getFrontendOpts().DisableFree = false;
+  // Parse the main file to get all existing #includes in the file, and then we
+  // can make sure the same header (even with different include path) is not
+  // added more than once.
+  CI->getPreprocessorOpts().SingleFileParseMode = true;
+
+  auto Clang = prepareCompilerInstance(
+      std::move(CI), /*Preamble=*/nullptr,
+      llvm::MemoryBuffer::getMemBuffer(Code, File),
+      std::make_shared<PCHContainerOperations>(), FS, IgnoreDiags);
+  auto &DiagOpts = Clang->getDiagnosticOpts();
+  DiagOpts.IgnoreWarnings = true;
+
+  if (Clang->getFrontendOpts().Inputs.empty())
+    return llvm::make_error<llvm::StringError>(
+        "Empty frontend action inputs empty for file " + File,
+        llvm::inconvertibleErrorCode());
+  PreprocessOnlyAction Action;
+  if (!Action.BeginSourceFile(*Clang, Clang->getFrontendOpts().Inputs[0]))
+    return llvm::make_error<llvm::StringError>(
+        "Failed to begin preprocessor only action for file " + File,
+        llvm::inconvertibleErrorCode());
+  std::set<std::string> ExistingHeaders;
+  Clang->getPreprocessor().addPPCallbacks(
+      llvm::make_unique<RecordHeaders>(ExistingHeaders));
+  if (!Action.Execute())
+    return llvm::make_error<llvm::StringError>(
+        "Failed to execute preprocessor only action for file " + File,
+        llvm::inconvertibleErrorCode());
+  if (ExistingHeaders.find(Header) != ExistingHeaders.end()) {
+    return llvm::make_error<llvm::StringError>(
+        Header + " is already included in " + File,
+        llvm::inconvertibleErrorCode());
+  }
+
+  auto &HeaderSearchInfo = Clang->getPreprocessor().getHeaderSearchInfo();
+  bool IsSystem = false;
+  std::string Suggested = HeaderSearchInfo.suggestPathToFileForDiagnostics(
+      Header, CompileCommand.Directory, &IsSystem);
+  if (IsSystem)
+    Suggested = "<" + Suggested + ">";
+  else
+    Suggested = "\"" + Suggested + "\"";
+
+  log("Suggested #include for " + Header + " is: " + Suggested);
+  return Suggested;
+}
+
+} // namespace clangd
+} // namespace clang

clangd/Protocol.h

 /// Serialize/deserialize \p URIForFile to/from a string URI.
 json::Expr toJSON(const URIForFile &U);
 bool fromJSON(const json::Expr &, URIForFile &);
 
 struct TextDocumentIdentifier {
   /// The text document's URI.
   URIForFile uri;
 };
+json::Expr toJSON(const TextDocumentIdentifier &);
 bool fromJSON(const json::Expr &, TextDocumentIdentifier &);
 
 struct Position {
   /// Line position in a document (zero-based).
   int line = 0;
 
   /// Character offset on a line in a document (zero-based).
   int character = 0;
struct WorkspaceEdit {
   llvm::Optional<std::map<std::string, std::vector<TextEdit>>> changes;
 
   /// Note: "documentChanges" is not currently used because currently there is
   /// no support for versioned edits.
 };
 bool fromJSON(const json::Expr &, WorkspaceEdit &);
 json::Expr toJSON(const WorkspaceEdit &WE);
 
+struct IncludeInsertion {
+  /// The document in which the command was invoked.
+  TextDocumentIdentifier textDocument;
+
+  /// The header to be inserted. This could be either a URI ir a literal string
+  /// quoted with <> or "" that can be #included directly.
+  std::string header;
+};
+bool fromJSON(const json::Expr &, IncludeInsertion &);
+json::Expr toJSON(const IncludeInsertion &II);
+
 /// Exact commands are not specified in the protocol so we define the
 /// ones supported by Clangd here. The protocol specifies the command arguments
 /// to be "any[]" but to make this safer and more manageable, each command we
 /// handle maps to a certain llvm::Optional of some struct to contain its
 /// arguments. Different commands could reuse the same llvm::Optional as
 /// arguments but a command that needs different arguments would simply add a
 /// new llvm::Optional and not use any other ones. In practice this means only
 /// one argument type will be parsed and set.
 struct ExecuteCommandParams {
   // Command to apply fix-its. Uses WorkspaceEdit as argument.
   const static llvm::StringLiteral CLANGD_APPLY_FIX_COMMAND;
+  // Command to insert an #include into code.
+  const static llvm::StringLiteral CLANGD_INSERT_HEADER_INCLUDE;
 
   /// The command identifier, e.g. CLANGD_APPLY_FIX_COMMAND
   std::string command;
 
   // Arguments
   llvm::Optional<WorkspaceEdit> workspaceEdit;
+
+  llvm::Optional<IncludeInsertion> includeInsertion;
 };
 bool fromJSON(const json::Expr &, ExecuteCommandParams &);
 
+struct Command : public ExecuteCommandParams {
+  std::string title;
+};
+
+json::Expr toJSON(const Command &C);
+
 struct ApplyWorkspaceEditParams {
   WorkspaceEdit edit;
 };
 json::Expr toJSON(const ApplyWorkspaceEditParams &);
 
 struct TextDocumentPositionParams {
   /// The text document.
   TextDocumentIdentifier textDocument;
struct CompletionItem {
   /// contain the position at which completion has been requested.
   llvm::Optional<TextEdit> textEdit;
 
   /// An optional array of additional text edits that are applied when selecting
   /// this completion. Edits must not overlap with the main edit nor with
   /// themselves.
   std::vector<TextEdit> additionalTextEdits;
 
+  llvm::Optional<Command> command;
   // TODO(krasimir): The following optional fields defined by the language
   // server protocol are unsupported:
   //
-  // command?: Command - An optional command that is executed *after* inserting
-  //                     this completion.
-  //
   // data?: any - A data entry field that is preserved on a completion item
   //              between a completion and a completion resolve request.
 };
 json::Expr toJSON(const CompletionItem &);
 
 bool operator<(const CompletionItem &, const CompletionItem &);
 
 /// Represents a collection of completion items to be presented in the editor.

clangd/Protocol.cpp

 }
 
 json::Expr toJSON(const URIForFile &U) { return U.uri(); }
 
 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const URIForFile &U) {
   return OS << U.uri();
 }
 
+json::Expr toJSON(const TextDocumentIdentifier &R) {
+  return json::obj{{"uri", R.uri}};
+}
+
 bool fromJSON(const json::Expr &Params, TextDocumentIdentifier &R) {
   json::ObjectMapper O(Params);
   return O && O.map("uri", R.uri);
 }
 
 bool fromJSON(const json::Expr &Params, Position &R) {
   json::ObjectMapper O(Params);
   return O && O.map("line", R.line) && O.map("character", R.character);

 
 bool fromJSON(const json::Expr &Params, WorkspaceEdit &R) {
   json::ObjectMapper O(Params);
   return O && O.map("changes", R.changes);
 }
 
 const llvm::StringLiteral ExecuteCommandParams::CLANGD_APPLY_FIX_COMMAND =
     "clangd.applyFix";
+const llvm::StringLiteral ExecuteCommandParams::CLANGD_INSERT_HEADER_INCLUDE =
+    "clangd.insertInclude";
 
 bool fromJSON(const json::Expr &Params, ExecuteCommandParams &R) {
   json::ObjectMapper O(Params);
   if (!O || !O.map("command", R.command))
     return false;
 
   auto Args = Params.asObject()->getArray("arguments");
   if (R.command == ExecuteCommandParams::CLANGD_APPLY_FIX_COMMAND) {
     return Args && Args->size() == 1 &&
            fromJSON(Args->front(), R.workspaceEdit);
+  } else if (R.command == ExecuteCommandParams::CLANGD_INSERT_HEADER_INCLUDE) {
+    return Args && Args->size() == 1 &&
+           fromJSON(Args->front(), R.includeInsertion);
   }
   return false; // Unrecognized command.
 }
 
+json::Expr toJSON(const Command &C) {
+  auto Cmd = json::obj{{"title", C.title}, {"command", C.command}};
+  if (C.workspaceEdit)
+    Cmd["arguments"] = {*C.workspaceEdit};
+  else if (C.includeInsertion)
+    Cmd["arguments"] = {*C.includeInsertion};
+  return std::move(Cmd);
+}
+
 json::Expr toJSON(const WorkspaceEdit &WE) {
   if (!WE.changes)
     return json::obj{};
   json::obj FileChanges;
   for (auto &Change : *WE.changes)
     FileChanges[Change.first] = json::ary(Change.second);
   return json::obj{{"changes", std::move(FileChanges)}};
 }
 
+bool fromJSON(const json::Expr &II, IncludeInsertion &R) {
+  json::ObjectMapper O(II);
+  return O && O.map("textDocument", R.textDocument) &&
+         O.map("header", R.header);
+}
+json::Expr toJSON(const IncludeInsertion &II) {
+  return json::obj{{"textDocument", II.textDocument}, {"header", II.header}};
+}
+
 json::Expr toJSON(const ApplyWorkspaceEditParams &Params) {
   return json::obj{{"edit", Params.edit}};
 }
 
 bool fromJSON(const json::Expr &Params, TextDocumentPositionParams &R) {
   json::ObjectMapper O(Params);
   return O && O.map("textDocument", R.textDocument) &&
          O.map("position", R.position);
json::Expr toJSON(const CompletionItem &CI) {
   if (!CI.insertText.empty())
     Result["insertText"] = CI.insertText;
   if (CI.insertTextFormat != InsertTextFormat::Missing)
     Result["insertTextFormat"] = static_cast<int>(CI.insertTextFormat);
   if (CI.textEdit)
     Result["textEdit"] = *CI.textEdit;
   if (!CI.additionalTextEdits.empty())
     Result["additionalTextEdits"] = json::ary(CI.additionalTextEdits);
+  if (CI.command)
+    Result["command"] = *CI.command;
   return std::move(Result);
 }
 
 bool operator<(const CompletionItem &L, const CompletionItem &R) {
   return (L.sortText.empty() ? L.label : L.sortText) <
          (R.sortText.empty() ? R.label : R.sortText);
 }
 

clangd/global-symbol-builder/GlobalSymbolBuilderMain.cpp

 //===--- GlobalSymbolBuilderMain.cpp -----------------------------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // GlobalSymbolBuilder is a tool to generate YAML-format symbols across the
 // whole project. This tools is for **experimental** only. Don't use it in
 // production code.
 //
 //===---------------------------------------------------------------------===//
 
+#include "index/CanonicalIncludes.h"
 #include "index/Index.h"
 #include "index/Merge.h"
 #include "index/SymbolCollector.h"
 #include "index/SymbolYAML.h"
+#include "clang/Frontend/CompilerInstance.h"
 #include "clang/Frontend/FrontendActions.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Index/IndexDataConsumer.h"
 #include "clang/Index/IndexingAction.h"
 #include "clang/Tooling/CommonOptionsParser.h"
 #include "clang/Tooling/Execution.h"
 #include "clang/Tooling/Tooling.h"
 #include "llvm/Support/CommandLine.h"
public:
   SymbolIndexActionFactory(tooling::ExecutionContext *Ctx) : Ctx(Ctx) {}
 
   clang::FrontendAction *create() override {
     // Wraps the index action and reports collected symbols to the execution
     // context at the end of each translation unit.
     class WrappedIndexAction : public WrapperFrontendAction {
     public:
       WrappedIndexAction(std::shared_ptr<SymbolCollector> C,
+                         std::unique_ptr<CanonicalIncludes> Includes,
                          const index::IndexingOptions &Opts,
                          tooling::ExecutionContext *Ctx)
           : WrapperFrontendAction(
                 index::createIndexingAction(C, Opts, nullptr)),
-            Ctx(Ctx), Collector(C) {}
+            Ctx(Ctx), Collector(C), Includes(std::move(Includes)),
+            PragmaHandler(collectIWYUHeaderMaps(this->Includes.get())) {}
+
+      std::unique_ptr<ASTConsumer>
+      CreateASTConsumer(CompilerInstance &CI, StringRef InFile) override {
+        CI.getPreprocessor().addCommentHandler(PragmaHandler.get());
+        return WrapperFrontendAction::CreateASTConsumer(CI, InFile);
+      }
 
       void EndSourceFileAction() override {
         WrapperFrontendAction::EndSourceFileAction();
 
         auto Symbols = Collector->takeSymbols();
         for (const auto &Sym : Symbols) {
           std::string IDStr;
           llvm::raw_string_ostream OS(IDStr);
           OS << Sym.ID;
           Ctx->reportResult(OS.str(), SymbolToYAML(Sym));
         }
       }
 
     private:
       tooling::ExecutionContext *Ctx;
       std::shared_ptr<SymbolCollector> Collector;
+      std::unique_ptr<CanonicalIncludes> Includes;
+      std::unique_ptr<CommentHandler> PragmaHandler;
     };
 
     index::IndexingOptions IndexOpts;
     IndexOpts.SystemSymbolFilter =
         index::IndexingOptions::SystemSymbolFilterKind::All;
     IndexOpts.IndexFunctionLocals = false;
     auto CollectorOpts = SymbolCollector::Options();
     CollectorOpts.FallbackDir = AssumedHeaderDir;
+    CollectorOpts.CollectIncludePath = true;
+    auto Includes = llvm::make_unique<CanonicalIncludes>();
+    addSystemHeadersMapping(Includes.get());
+    CollectorOpts.Includes = Includes.get();
     return new WrappedIndexAction(
-        std::make_shared<SymbolCollector>(std::move(CollectorOpts)), IndexOpts,
-        Ctx);
+        std::make_shared<SymbolCollector>(std::move(CollectorOpts)),
+        std::move(Includes), IndexOpts, Ctx);
   }
 
   tooling::ExecutionContext *Ctx;
 };
 
 // Combine occurrences of the same symbol across translation units.
 SymbolSlab mergeSymbols(tooling::ToolResults *Results) {
   SymbolSlab::Builder UniqueSymbols;

clangd/index/CanonicalIncludes.h

+//===-- CanonicalIncludes.h - remap #include header -------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// At indexing time, we decide which file to #included for a symbol.
+// Usually this is the file with the canonical decl, but there are exceptions:
+// - private headers may have pragmas pointing to the matching public header.
+//   (These are "IWYU" pragmas, named after the include-what-you-use tool).
+// - the standard library is implemented in many files, without any pragmas.
+//   We have a lookup table for common standard library implementations.
+//   libstdc++ puts char_traits in bits/char_traits.h, but we #include <string>.
+//
+//===---------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_CANONICALINCLUDES_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_CANONICALINCLUDES_H
+
+#include "clang/Lex/Preprocessor.h"
+#include "llvm/ADT/StringMap.h"
+#include "llvm/Support/Regex.h"
+#include <string>
+#include <vector>
+
+namespace clang {
+namespace clangd {
+
+/// Maps a definition location onto an #include file, based on a set of filename
+/// rules.
+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 all files matching \p RE to \p CanonicalPath
+  void addRegexMapping(llvm::StringRef RE, llvm::StringRef CanonicalPath);
+
+  /// \return \p Header itself if there is no mapping for it; otherwise, return
+  /// a canonical header name.
+  llvm::StringRef mapHeader(llvm::StringRef Header) const;
+
+private:
+  // A map from header patterns to header names. This needs to be mutable so
+  // that we can match again a Regex in a const function member.
+  // FIXME(ioeric): All the regexes we have so far are suffix matches. The
+  // performance could be improved by allowing only suffix matches instead of
+  // arbitrary regexes.
+  mutable std::vector<std::pair<llvm::Regex, std::string>>
+      RegexHeaderMappingTable;
+};
+
+/// 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. 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);
+
+} // namespace clangd
+} // namespace clang
+
+#endif //LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_HEADERMAPCOLLECTOR_H

clangd/index/CanonicalIncludes.cpp

+//===-- CanonicalIncludes.h - remap #inclue headers--------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "CanonicalIncludes.h"
+#include "llvm/Support/Regex.h"
+
+namespace clang {
+namespace clangd {
+namespace {
+const char IWYUPragma[] = "// IWYU pragma: private, include ";
+} // namespace
+
+void CanonicalIncludes::addMapping(llvm::StringRef Path,
+                                   llvm::StringRef CanonicalPath) {
+  addRegexMapping((llvm::Twine("^") + Path + "$").str(), CanonicalPath);
+};
+
+void CanonicalIncludes::addRegexMapping(llvm::StringRef RE,
+                                        llvm::StringRef CanonicalPath) {
+  this->RegexHeaderMappingTable.emplace_back(llvm::Regex(RE), CanonicalPath);
+}
+
+llvm::StringRef CanonicalIncludes::mapHeader(llvm::StringRef Header) const {
+  for (auto &Entry : RegexHeaderMappingTable) {
+#ifndef NDEBUG
+    std::string Dummy;
+    assert(Entry.first.isValid(Dummy) && "Regex should never be invalid!");
+#endif
+    if (Entry.first.match(Header))
+      return Entry.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 {
+      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()),
+                           Text.startswith("<") ? Text.str()
+                                                : ("\"" + Text + "\"").str());
+      return false;
+    }
+
+  private:
+    CanonicalIncludes *const Includes;
+  };
+  return llvm::make_unique<PragmaCommentHandler>(Includes);
+}
+
+void addSystemHeadersMapping(CanonicalIncludes *Includes) {
+  static const std::vector<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>"},
+          {"include/avx512dqintrin.h$", "<immintrin.h>"},
+          {"include/avx512erintrin.h$", "<immintrin.h>"},
+          {"include/avx512fintrin.h$", "<immintrin.h>"},
+          {"include/avx512ifmaintrin.h$", "<immintrin.h>"},
+          {"include/avx512ifmavlintrin.h$", "<immintrin.h>"},
+          {"include/avx512pfintrin.h$", "<immintrin.h>"},
+          {"include/avx512vbmiintrin.h$", "<immintrin.h>"},
+          {"include/avx512vbmivlintrin.h$", "<immintrin.h>"},
+          {"include/avx512vlbwintrin.h$", "<immintrin.h>"},
+          {"include/avx512vlcdintrin.h$", "<immintrin.h>"},
+          {"include/avx512vldqintrin.h$", "<immintrin.h>"},
+          {"include/avx512vlintrin.h$", "<immintrin.h>"},
+          {"include/avxintrin.h$", "<immintrin.h>"},
+          {"include/bmi2intrin.h$", "<x86intrin.h>"},
+          {"include/bmiintrin.h$", "<x86intrin.h>"},
+          {"include/emmintrin.h$", "<emmintrin.h>"},
+          {"include/f16cintrin.h$", "<emmintrin.h>"},
+          {"include/float.h$", "<cfloat>"},
+          {"include/fma4intrin.h$", "<x86intrin.h>"},
+          {"include/fmaintrin.h$", "<immintrin.h>"},
+          {"include/fxsrintrin.h$", "<immintrin.h>"},
+          {"include/ia32intrin.h$", "<x86intrin.h>"},
+          {"include/immintrin.h$", "<immintrin.h>"},
+          {"include/inttypes.h$", "<cinttypes>"},
+          {"include/limits.h$", "<climits>"},
+          {"include/lzcntintrin.h$", "<x86intrin.h>"},
+          {"include/mm3dnow.h$", "<mm3dnow.h>"},
+          {"include/mm_malloc.h$", "<mm_malloc.h>"},
+          {"include/mmintrin.h$", "<mmintrin>"},
+          {"include/mwaitxintrin.h$", "<x86intrin.h>"},
+          {"include/pkuintrin.h$", "<immintrin.h>"},
+          {"include/pmmintrin.h$", "<pmmintrin.h>"},
+          {"include/popcntintrin.h$", "<popcntintrin.h>"},
+          {"include/prfchwintrin.h$", "<x86intrin.h>"},
+          {"include/rdseedintrin.h$", "<x86intrin.h>"},
+          {"include/rtmintrin.h$", "<immintrin.h>"},
+          {"include/shaintrin.h$", "<immintrin.h>"},
+          {"include/smmintrin.h$", "<smmintrin.h>"},
+          {"include/stdalign.h$", "<cstdalign>"},
+          {"include/stdarg.h$", "<cstdarg>"},
+          {"include/stdbool.h$", "<cstdbool>"},
+          {"include/stddef.h$", "<cstddef>"},
+          {"include/stdint.h$", "<cstdint>"},
+          {"include/tbmintrin.h$", "<x86intrin.h>"},
+          {"include/tmmintrin.h$", "<tmmintrin.h>"},
+          {"include/wmmintrin.h$", "<wmmintrin.h>"},
+          {"include/x86intrin.h$", "<x86intrin.h>"},
+          {"include/xmmintrin.h$", "<xmmintrin.h>"},
+          {"include/xopintrin.h$", "<x86intrin.h>"},
+          {"include/xsavecintrin.h$", "<immintrin.h>"},
+          {"include/xsaveintrin.h$", "<immintrin.h>"},
+          {"include/xsaveoptintrin.h$", "<immintrin.h>"},
+          {"include/xsavesintrin.h$", "<immintrin.h>"},
+          {"include/xtestintrin.h$", "<immintrin.h>"},
+          {"include/_G_config.h$", "<cstdio>"},
+          {"include/assert.h$", "<cassert>"},
+          {"algorithm$", "<algorithm>"},
+          {"array$", "<array>"},
+          {"atomic$", "<atomic>"},
+          {"backward/auto_ptr.h$", "<memory>"},
+          {"backward/binders.h$", "<string>"},
+          {"bits/algorithmfwd.h$", "<algorithm>"},
+          {"bits/alloc_traits.h$", "<unordered_set>"},
+          {"bits/allocator.h$", "<string>"},
+          {"bits/atomic_base.h$", "<atomic>"},
+          {"bits/atomic_lockfree_defines.h$", "<exception>"},
+          {"bits/basic_ios.h$", "<ios>"},
+          {"bits/basic_ios.tcc$", "<ios>"},
+          {"bits/basic_string.h$", "<string>"},
+          {"bits/basic_string.tcc$", "<string>"},
+          {"bits/char_traits.h$", "<string>"},
+          {"bits/codecvt.h$", "<locale>"},
+          {"bits/concept_check.h$", "<numeric>"},
+          {"bits/cpp_type_traits.h$", "<cmath>"},
+          {"bits/cxxabi_forced.h$", "<cxxabi.h>"},
+          {"bits/deque.tcc$", "<deque>"},
+          {"bits/exception_defines.h$", "<exception>"},
+          {"bits/exception_ptr.h$", "<exception>"},
+          {"bits/forward_list.h$", "<forward_list>"},
+          {"bits/forward_list.tcc$", "<forward_list>"},
+          {"bits/fstream.tcc$", "<fstream>"},
+          {"bits/functexcept.h$", "<list>"},
+          {"bits/functional_hash.h$", "<string>"},
+          {"bits/gslice.h$", "<valarray>"},
+          {"bits/gslice_array.h$", "<valarray>"},
+          {"bits/hash_bytes.h$", "<typeinfo>"},
+          {"bits/hashtable.h$", "<unordered_set>"},
+          {"bits/hashtable_policy.h$", "<unordered_set>"},
+          {"bits/indirect_array.h$", "<valarray>"},
+          {"bits/ios_base.h$", "<ios>"},
+          {"bits/istream.tcc$", "<istream>"},
+          {"bits/list.tcc$", "<list>"},
+          {"bits/locale_classes.h$", "<locale>"},
+          {"bits/locale_classes.tcc$", "<locale>"},
+          {"bits/locale_facets.h$", "<locale>"},
+          {"bits/locale_facets.tcc$", "<locale>"},
+          {"bits/locale_facets_nonio.h$", "<locale>"},
+          {"bits/locale_facets_nonio.tcc$", "<locale>"},
+          {"bits/localefwd.h$", "<locale>"},
+          {"bits/mask_array.h$", "<valarray>"},
+          {"bits/memoryfwd.h$", "<memory>"},
+          {"bits/move.h$", "<utility>"},
+          {"bits/nested_exception.h$", "<exception>"},
+          {"bits/ostream.tcc$", "<ostream>"},
+          {"bits/ostream_insert.h$", "<ostream>"},
+          {"bits/postypes.h$", "<iosfwd>"},
+          {"bits/ptr_traits.h$", "<memory>"},
+          {"bits/random.h$", "<random>"},
+          {"bits/random.tcc$", "<random>"},
+          {"bits/range_access.h$", "<iterator>"},
+          {"bits/regex.h$", "<regex>"},
+          {"bits/regex_compiler.h$", "<regex>"},
+          {"bits/regex_constants.h$", "<regex>"},
+          {"bits/regex_cursor.h$", "<regex>"},
+          {"bits/regex_error.h$", "<regex>"},
+          {"bits/regex_grep_matcher.h$", "<regex>"},
+          {"bits/regex_grep_matcher.tcc$", "<regex>"},
+          {"bits/regex_nfa.h$", "<regex>"},
+          {"bits/shared_ptr.h$", "<memory>"},
+          {"bits/shared_ptr_base.h$", "<memory>"},
+          {"bits/slice_array.h$", "<valarray>"},
+          {"bits/sstream.tcc$", "<sstream>"},
+          {"bits/stl_algo.h$", "<algorithm>"},
+          {"bits/stl_algobase.h$", "<list>"},
+          {"bits/stl_bvector.h$", "<vector>"},
+          {"bits/stl_construct.h$", "<deque>"},
+          {"bits/stl_deque.h$", "<deque>"},
+          {"bits/stl_function.h$", "<string>"},
+          {"bits/stl_heap.h$", "<queue>"},
+          {"bits/stl_iterator.h$", "<iterator>"},
+          {"bits/stl_iterator_base_funcs.h$", "<iterator>"},
+          {"bits/stl_iterator_base_types.h$", "<numeric>"},
+          {"bits/stl_list.h$", "<list>"},
+          {"bits/stl_map.h$", "<map>"},
+          {"bits/stl_multimap.h$", "<map>"},
+          {"bits/stl_multiset.h$", "<set>"},
+          {"bits/stl_numeric.h$", "<numeric>"},
+          {"bits/stl_pair.h$", "<utility>"},
+          {"bits/stl_queue.h$", "<queue>"},
+          {"bits/stl_raw_storage_iter.h$", "<memory>"},
+          {"bits/stl_relops.h$", "<utility>"},
+          {"bits/stl_set.h$", "<set>"},
+          {"bits/stl_stack.h$", "<stack>"},
+          {"bits/stl_tempbuf.h$", "<memory>"},
+          {"bits/stl_tree.h$", "<map>"},
+          {"bits/stl_uninitialized.h$", "<deque>"},
+          {"bits/stl_vector.h$", "<vector>"},
+          {"bits/stream_iterator.h$", "<iterator>"},
+          {"bits/streambuf.tcc$", "<streambuf>"},
+          {"bits/streambuf_iterator.h$", "<iterator>"},
+          {"bits/stringfwd.h$", "<string>"},
+          {"bits/unique_ptr.h$", "<memory>"},
+          {"bits/unordered_map.h$", "<unordered_map>"},
+          {"bits/unordered_set.h$", "<unordered_set>"},
+          {"bits/uses_allocator.h$", "<tuple>"},
+          {"bits/valarray_after.h$", "<valarray>"},
+          {"bits/valarray_array.h$", "<valarray>"},
+          {"bits/valarray_array.tcc$", "<valarray>"},
+          {"bits/valarray_before.h$", "<valarray>"},
+          {"bits/vector.tcc$", "<vector>"},
+          {"bitset$", "<bitset>"},
+          {"ccomplex$", "<ccomplex>"},
+          {"cctype$", "<cctype>"},
+          {"cerrno$", "<cerrno>"},
+          {"cfenv$", "<cfenv>"},
+          {"cfloat$", "<cfloat>"},
+          {"chrono$", "<chrono>"},
+          {"cinttypes$", "<cinttypes>"},
+          {"climits$", "<climits>"},
+          {"clocale$", "<clocale>"},
+          {"cmath$", "<cmath>"},
+          {"complex$", "<complex>"},
+          {"complex.h$", "<complex.h>"},
+          {"condition_variable$", "<condition_variable>"},
+          {"csetjmp$", "<csetjmp>"},
+          {"csignal$", "<csignal>"},
+          {"cstdalign$", "<cstdalign>"},
+          {"cstdarg$", "<cstdarg>"},
+          {"cstdbool$", "<cstdbool>"},
+          {"cstdint$", "<cstdint>"},
+          {"cstdio$", "<cstdio>"},
+          {"cstdlib$", "<cstdlib>"},
+          {"cstring$", "<cstring>"},
+          {"ctgmath$", "<ctgmath>"},
+          {"ctime$", "<ctime>"},
+          {"cwchar$", "<cwchar>"},
+          {"cwctype$", "<cwctype>"},
+          {"cxxabi.h$", "<cxxabi.h>"},
+          {"debug/debug.h$", "<numeric>"},
+          {"deque$", "<deque>"},
+          {"exception$", "<exception>"},
+          {"ext/alloc_traits.h$", "<deque>"},
+          {"ext/atomicity.h$", "<memory>"},
+          {"ext/concurrence.h$", "<memory>"},
+          {"ext/new_allocator.h$", "<string>"},
+          {"ext/numeric_traits.h$", "<list>"},
+          {"ext/string_conversions.h$", "<string>"},
+          {"ext/type_traits.h$", "<cmath>"},
+          {"fenv.h$", "<fenv.h>"},
+          {"forward_list$", "<forward_list>"},
+          {"fstream$", "<fstream>"},
+          {"functional$", "<functional>"},
+          {"future$", "<future>"},
+          {"initializer_list$", "<initializer_list>"},
+          {"iomanip$", "<iomanip>"},
+          {"ios$", "<ios>"},
+          {"iosfwd$", "<iosfwd>"},
+          {"iostream$", "<iostream>"},
+          {"istream$", "<istream>"},
+          {"iterator$", "<iterator>"},
+          {"limits$", "<limits>"},
+          {"list$", "<list>"},
+          {"locale$", "<locale>"},
+          {"map$", "<map>"},
+          {"memory$", "<memory>"},
+          {"mutex$", "<mutex>"},
+          {"new$", "<new>"},
+          {"numeric$", "<numeric>"},
+          {"ostream$", "<ostream>"},
+          {"queue$", "<queue>"},
+          {"random$", "<random>"},
+          {"ratio$", "<ratio>"},
+          {"regex$", "<regex>"},
+          {"scoped_allocator$", "<scoped_allocator>"},
+          {"set$", "<set>"},
+          {"sstream$", "<sstream>"},
+          {"stack$", "<stack>"},
+          {"stdexcept$", "<stdexcept>"},
+          {"streambuf$", "<streambuf>"},
+          {"string$", "<string>"},
+          {"system_error$", "<system_error>"},
+          {"tgmath.h$", "<tgmath.h>"},
+          {"thread$", "<thread>"},
+          {"tuple$", "<tuple>"},
+          {"type_traits$", "<type_traits>"},
+          {"typeindex$", "<typeindex>"},
+          {"typeinfo$", "<typeinfo>"},
+          {"unordered_map$", "<unordered_map>"},
+          {"unordered_set$", "<unordered_set>"},
+          {"utility$", "<utility>"},
+          {"valarray$", "<valarray>"},
+          {"vector$", "<vector>"},
+          {"include/complex.h$", "<complex.h>"},
+          {"include/ctype.h$", "<cctype>"},
+          {"include/errno.h$", "<cerrno>"},
+          {"include/fenv.h$", "<fenv.h>"},
+          {"include/inttypes.h$", "<cinttypes>"},
+          {"include/libio.h$", "<cstdio>"},
+          {"include/limits.h$", "<climits>"},
+          {"include/locale.h$", "<clocale>"},
+          {"include/math.h$", "<cmath>"},
+          {"include/setjmp.h$", "<csetjmp>"},
+          {"include/signal.h$", "<csignal>"},
+          {"include/stdint.h$", "<cstdint>"},
+          {"include/stdio.h$", "<cstdio>"},
+          {"include/stdlib.h$", "<cstdlib>"},
+          {"include/string.h$", "<cstring>"},
+          {"include/time.h$", "<ctime>"},
+          {"include/wchar.h$", "<cwchar>"},
+          {"include/wctype.h$", "<cwctype>"},
+          {"bits/cmathcalls.h$", "<complex.h>"},
+          {"bits/errno.h$", "<cerrno>"},
+          {"bits/fenv.h$", "<fenv.h>"},
+          {"bits/huge_val.h$", "<cmath>"},
+          {"bits/huge_valf.h$", "<cmath>"},
+          {"bits/huge_vall.h$", "<cmath>"},
+          {"bits/inf.h$", "<cmath>"},
+          {"bits/local_lim.h$", "<climits>"},
+          {"bits/locale.h$", "<clocale>"},
+          {"bits/mathcalls.h$", "<math.h>"},
+          {"bits/mathdef.h$", "<cmath>"},
+          {"bits/nan.h$", "<cmath>"},
+          {"bits/posix1_lim.h$", "<climits>"},
+          {"bits/posix2_lim.h$", "<climits>"},
+          {"bits/setjmp.h$", "<csetjmp>"},
+          {"bits/sigaction.h$", "<csignal>"},
+          {"bits/sigcontext.h$", "<csignal>"},
+          {"bits/siginfo.h$", "<csignal>"},
+          {"bits/signum.h$", "<csignal>"},
+          {"bits/sigset.h$", "<csignal>"},
+          {"bits/sigstack.h$", "<csignal>"},
+          {"bits/stdio_lim.h$", "<cstdio>"},
+          {"bits/sys_errlist.h$", "<cstdio>"},
+          {"bits/time.h$", "<ctime>"},
+          {"bits/timex.h$", "<ctime>"},
+          {"bits/typesizes.h$", "<cstdio>"},
+          {"bits/wchar.h$", "<cwchar>"},
+          {"bits/wordsize.h$", "<csetjmp>"},
+          {"bits/xopen_lim.h$", "<climits>"},
+          {"include/xlocale.h$", "<cstring>"},
+          {"bits/atomic_word.h$", "<memory>"},
+          {"bits/basic_file.h$", "<fstream>"},
+          {"bits/c\\+\\+allocator.h$", "<string>"},
+          {"bits/c\\+\\+config.h$", "<iosfwd>"},
+          {"bits/c\\+\\+io.h$", "<ios>"},
+          {"bits/c\\+\\+locale.h$", "<locale>"},
+          {"bits/cpu_defines.h$", "<iosfwd>"},
+          {"bits/ctype_base.h$", "<locale>"},
+          {"bits/cxxabi_tweaks.h$", "<cxxabi.h>"},
+          {"bits/error_constants.h$", "<system_error>"},
+          {"bits/gthr-default.h$", "<memory>"},
+          {"bits/gthr.h$", "<memory>"},
+          {"bits/opt_random.h$", "<random>"},
+          {"bits/os_defines.h$", "<iosfwd>"},
+          // GNU C headers
+          {"include/aio.h$", "<aio.h>"},
+          {"include/aliases.h$", "<aliases.h>"},
+          {"include/alloca.h$", "<alloca.h>"},
+          {"include/ar.h$", "<ar.h>"},
+          {"include/argp.h$", "<argp.h>"},
+          {"include/argz.h$", "<argz.h>"},
+          {"include/arpa/nameser.h$", "<resolv.h>"},
+          {"include/arpa/nameser_compat.h$", "<resolv.h>"},
+          {"include/byteswap.h$", "<byteswap.h>"},
+          {"include/cpio.h$", "<cpio.h>"},
+          {"include/crypt.h$", "<crypt.h>"},
+          {"include/dirent.h$", "<dirent.h>"},
+          {"include/dlfcn.h$", "<dlfcn.h>"},
+          {"include/elf.h$", "<elf.h>"},
+          {"include/endian.h$", "<endian.h>"},
+          {"include/envz.h$", "<envz.h>"},
+          {"include/err.h$", "<err.h>"},
+          {"include/error.h$", "<error.h>"},
+          {"include/execinfo.h$", "<execinfo.h>"},
+          {"include/fcntl.h$", "<fcntl.h>"},
+          {"include/features.h$", "<features.h>"},
+          {"include/fenv.h$", "<fenv.h>"},
+          {"include/fmtmsg.h$", "<fmtmsg.h>"},
+          {"include/fnmatch.h$", "<fnmatch.h>"},
+          {"include/fstab.h$", "<fstab.h>"},
+          {"include/fts.h$", "<fts.h>"},
+          {"include/ftw.h$", "<ftw.h>"},
+          {"include/gconv.h$", "<gconv.h>"},
+          {"include/getopt.h$", "<getopt.h>"},
+          {"include/glob.h$", "<glob.h>"},
+          {"include/grp.h$", "<grp.h>"},
+          {"include/gshadow.h$", "<gshadow.h>"},
+          {"include/iconv.h$", "<iconv.h>"},
+          {"include/ifaddrs.h$", "<ifaddrs.h>"},
+          {"include/kdb.h$", "<kdb.h>"},
+          {"include/langinfo.h$", "<langinfo.h>"},
+          {"include/libgen.h$", "<libgen.h>"},
+          {"include/libintl.h$", "<libintl.h>"},
+          {"include/link.h$", "<link.h>"},
+          {"include/malloc.h$", "<malloc.h>"},
+          {"include/mcheck.h$", "<mcheck.h>"},
+          {"include/memory.h$", "<memory.h>"},
+          {"include/mntent.h$", "<mntent.h>"},
+          {"include/monetary.h$", "<monetary.h>"},
+          {"include/mqueue.h$", "<mqueue.h>"},
+          {"include/netdb.h$", "<netdb.h>"},
+          {"include/netinet/in.h$", "<netinet/in.h>"},
+          {"include/nl_types.h$", "<nl_types.h>"},
+          {"include/nss.h$", "<nss.h>"},
+          {"include/obstack.h$", "<obstack.h>"},
+          {"include/panel.h$", "<panel.h>"},
+          {"include/paths.h$", "<paths.h>"},
+          {"include/printf.h$", "<printf.h>"},
+          {"include/profile.h$", "<profile.h>"},
+          {"include/pthread.h$", "<pthread.h>"},
+          {"include/pty.h$", "<pty.h>"},
+          {"include/pwd.h$", "<pwd.h>"},
+          {"include/re_comp.h$", "<re_comp.h>"},
+          {"include/regex.h$", "<regex.h>"},
+          {"include/regexp.h$", "<regexp.h>"},
+          {"include/resolv.h$", "<resolv.h>"},
+          {"include/rpc/netdb.h$", "<netdb.h>"},
+          {"include/sched.h$", "<sched.h>"},
+          {"include/search.h$", "<search.h>"},
+          {"include/semaphore.h$", "<semaphore.h>"},
+          {"include/sgtty.h$", "<sgtty.h>"},
+          {"include/shadow.h$", "<shadow.h>"},
+          {"include/spawn.h$", "<spawn.h>"},
+          {"include/stab.h$", "<stab.h>"},
+          {"include/stdc-predef.h$", "<stdc-predef.h>"},
+          {"include/stdio_ext.h$", "<stdio_ext.h>"},
+          {"include/strings.h$", "<strings.h>"},
+          {"include/stropts.h$", "<stropts.h>"},
+          {"include/sudo_plugin.h$", "<sudo_plugin.h>"},
+          {"include/sysexits.h$", "<sysexits.h>"},
+          {"include/tar.h$", "<tar.h>"},
+          {"include/tcpd.h$", "<tcpd.h>"},
+          {"include/term.h$", "<term.h>"},
+          {"include/term_entry.h$", "<term_entry.h>"},
+          {"include/termcap.h$", "<termcap.h>"},
+          {"include/termios.h$", "<termios.h>"},
+          {"include/thread_db.h$", "<thread_db.h>"},
+          {"include/tic.h$", "<tic.h>"},
+          {"include/ttyent.h$", "<ttyent.h>"},
+          {"include/uchar.h$", "<uchar.h>"},
+          {"include/ucontext.h$", "<ucontext.h>"},
+          {"include/ulimit.h$", "<ulimit.h>"},
+          {"include/unctrl.h$", "<unctrl.h>"},
+          {"include/unistd.h$", "<unistd.h>"},
+          {"include/utime.h$", "<utime.h>"},
+          {"include/utmp.h$", "<utmp.h>"},
+          {"include/utmpx.h$", "<utmpx.h>"},
+          {"include/values.h$", "<values.h>"},
+          {"include/wordexp.h$", "<wordexp.h>"},
+          {"fpu_control.h$", "<fpu_control.h>"},
+          {"ieee754.h$", "<ieee754.h>"},
+          {"include/xlocale.h$", "<xlocale.h>"},
+          {"gnu/lib-names.h$", "<gnu/lib-names.h>"},
+          {"gnu/libc-version.h$", "<gnu/libc-version.h>"},
+          {"gnu/option-groups.h$", "<gnu/option-groups.h>"},
+          {"gnu/stubs-32.h$", "<gnu/stubs-32.h>"},
+          {"gnu/stubs-64.h$", "<gnu/stubs-64.h>"},
+          {"gnu/stubs-x32.h$", "<gnu/stubs-x32.h>"},
+          {"include/rpc/auth_des.h$", "<rpc/auth_des.h>"},
+          {"include/rpc/rpc_msg.h$", "<rpc/rpc_msg.h>"},
+          {"include/rpc/pmap_clnt.h$", "<rpc/pmap_clnt.h>"},
+          {"include/rpc/rpc.h$", "<rpc/rpc.h>"},
+          {"include/rpc/types.h$", "<rpc/types.h>"},
+          {"include/rpc/auth_unix.h$", "<rpc/auth_unix.h>"},
+          {"include/rpc/key_prot.h$", "<rpc/key_prot.h>"},
+          {"include/rpc/pmap_prot.h$", "<rpc/pmap_prot.h>"},
+          {"include/rpc/auth.h$", "<rpc/auth.h>"},
+          {"include/rpc/svc_auth.h$", "<rpc/svc_auth.h>"},
+          {"include/rpc/xdr.h$", "<rpc/xdr.h>"},
+          {"include/rpc/pmap_rmt.h$", "<rpc/pmap_rmt.h>"},
+          {"include/rpc/des_crypt.h$", "<rpc/des_crypt.h>"},
+          {"include/rpc/svc.h$", "<rpc/svc.h>"},
+          {"include/rpc/rpc_des.h$", "<rpc/rpc_des.h>"},
+          {"include/rpc/clnt.h$", "<rpc/clnt.h>"},
+          {"include/scsi/scsi.h$", "<scsi/scsi.h>"},
+          {"include/scsi/sg.h$", "<scsi/sg.h>"},
+          {"include/scsi/scsi_ioctl.h$", "<scsi/scsi_ioctl>"},
+          {"include/netrose/rose.h$", "<netrose/rose.h>"},
+          {"include/nfs/nfs.h$", "<nfs/nfs.h>"},
+          {"include/netatalk/at.h$", "<netatalk/at.h>"},
+          {"include/netinet/ether.h$", "<netinet/ether.h>"},
+          {"include/netinet/icmp6.h$", "<netinet/icmp6.h>"},
+          {"include/netinet/if_ether.h$", "<netinet/if_ether.h>"},
+          {"include/netinet/if_fddi.h$", "<netinet/if_fddi.h>"},
+          {"include/netinet/if_tr.h$", "<netinet/if_tr.h>"},
+          {"include/netinet/igmp.h$", "<netinet/igmp.h>"},
+          {"include/netinet/in.h$", "<netinet/in.h>"},
+          {"include/netinet/in_systm.h$", "<netinet/in_systm.h>"},
+          {"include/netinet/ip.h$", "<netinet/ip.h>"},
+          {"include/netinet/ip6.h$", "<netinet/ip6.h>"},
+          {"include/netinet/ip_icmp.h$", "<netinet/ip_icmp.h>"},
+          {"include/netinet/tcp.h$", "<netinet/tcp.h>"},
+          {"include/netinet/udp.h$", "<netinet/udp.h>"},
+          {"include/netrom/netrom.h$", "<netrom/netrom.h>"},
+          {"include/protocols/routed.h$", "<protocols/routed.h>"},
+          {"include/protocols/rwhod.h$", "<protocols/rwhod.h>"},
+          {"include/protocols/talkd.h$", "<protocols/talkd.h>"},
+          {"include/protocols/timed.h$", "<protocols/timed.h>"},
+          {"include/rpcsvc/klm_prot.x$", "<rpcsvc/klm_prot.x>"},
+          {"include/rpcsvc/rstat.h$", "<rpcsvc/rstat.h>"},
+          {"include/rpcsvc/spray.x$", "<rpcsvc/spray.x>"},
+          {"include/rpcsvc/nlm_prot.x$", "<rpcsvc/nlm_prot.x>"},
+          {"include/rpcsvc/nis_callback.x$", "<rpcsvc/nis_callback.x>"},
+          {"include/rpcsvc/yp.h$", "<rpcsvc/yp.h>"},
+          {"include/rpcsvc/yp.x$", "<rpcsvc/yp.x>"},
+          {"include/rpcsvc/nfs_prot.h$", "<rpcsvc/nfs_prot.h>"},
+          {"include/rpcsvc/rex.h$", "<rpcsvc/rex.h>"},
+          {"include/rpcsvc/yppasswd.h$", "<rpcsvc/yppasswd.h>"},
+          {"include/rpcsvc/rex.x$", "<rpcsvc/rex.x>"},
+          {"include/rpcsvc/nis_tags.h$", "<rpcsvc/nis_tags.h>"},
+          {"include/rpcsvc/nis_callback.h$", "<rpcsvc/nis_callback.h>"},
+          {"include/rpcsvc/nfs_prot.x$", "<rpcsvc/nfs_prot.x>"},
+          {"include/rpcsvc/bootparam_prot.x$", "<rpcsvc/bootparam_prot.x>"},
+          {"include/rpcsvc/rusers.x$", "<rpcsvc/rusers.x>"},
+          {"include/rpcsvc/rquota.x$", "<rpcsvc/rquota.x>"},
+          {"include/rpcsvc/nis.h$", "<rpcsvc/nis.h>"},
+          {"include/rpcsvc/nislib.h$", "<rpcsvc/nislib.h>"},
+          {"include/rpcsvc/ypupd.h$", "<rpcsvc/ypupd.h>"},
+          {"include/rpcsvc/bootparam.h$", "<rpcsvc/bootparam.h>"},
+          {"include/rpcsvc/spray.h$", "<rpcsvc/spray.h>"},
+          {"include/rpcsvc/key_prot.h$", "<rpcsvc/key_prot.h>"},
+          {"include/rpcsvc/klm_prot.h$", "<rpcsvc/klm_prot.h>"},
+          {"include/rpcsvc/sm_inter.h$", "<rpcsvc/sm_inter.h>"},
+          {"include/rpcsvc/nlm_prot.h$", "<rpcsvc/nlm_prot.h>"},
+          {"include/rpcsvc/yp_prot.h$", "<rpcsvc/yp_prot.h>"},
+          {"include/rpcsvc/ypclnt.h$", "<rpcsvc/ypclnt.h>"},
+          {"include/rpcsvc/rstat.x$", "<rpcsvc/rstat.x>"},
+          {"include/rpcsvc/rusers.h$", "<rpcsvc/rusers.h>"},
+          {"include/rpcsvc/key_prot.x$", "<rpcsvc/key_prot.x>"},
+          {"include/rpcsvc/sm_inter.x$", "<rpcsvc/sm_inter.x>"},
+          {"include/rpcsvc/rquota.h$", "<rpcsvc/rquota.h>"},
+          {"include/rpcsvc/nis.x$", "<rpcsvc/nis.x>"},
+          {"include/rpcsvc/bootparam_prot.h$", "<rpcsvc/bootparam_prot.h>"},
+          {"include/rpcsvc/mount.h$", "<rpcsvc/mount.h>"},
+          {"include/rpcsvc/mount.x$", "<rpcsvc/mount.x>"},
+          {"include/rpcsvc/nis_object.x$", "<rpcsvc/nis_object.x>"},
+          {"include/rpcsvc/yppasswd.x$", "<rpcsvc/yppasswd.x>"},
+          {"sys/acct.h$", "<sys/acct.h>"},
+          {"sys/auxv.h$", "<sys/auxv.h>"},
+          {"sys/cdefs.h$", "<sys/cdefs.h>"},
+          {"sys/debugreg.h$", "<sys/debugreg.h>"},
+          {"sys/dir.h$", "<sys/dir.h>"},
+          {"sys/elf.h$", "<sys/elf.h>"},
+          {"sys/epoll.h$", "<sys/epoll.h>"},
+          {"sys/eventfd.h$", "<sys/eventfd.h>"},
+          {"sys/fanotify.h$", "<sys/fanotify.h>"},
+          {"sys/file.h$", "<sys/file.h>"},
+          {"sys/fsuid.h$", "<sys/fsuid.h>"},
+          {"sys/gmon.h$", "<sys/gmon.h>"},
+          {"sys/gmon_out.h$", "<sys/gmon_out.h>"},
+          {"sys/inotify.h$", "<sys/inotify.h>"},
+          {"sys/io.h$", "<sys/io.h>"},
+          {"sys/ioctl.h$", "<sys/ioctl.h>"},
+          {"sys/ipc.h$", "<sys/ipc.h>"},
+          {"sys/kd.h$", "<sys/kd.h>"},
+          {"sys/kdaemon.h$", "<sys/kdaemon.h>"},
+          {"sys/klog.h$", "<sys/klog.h>"},
+          {"sys/mman.h$", "<sys/mman.h>"},
+          {"sys/mount.h$", "<sys/mount.h>"},
+          {"sys/msg.h$", "<sys/msg.h>"},
+          {"sys/mtio.h$", "<sys/mtio.h>"},
+          {"sys/param.h$", "<sys/param.h>"},
+          {"sys/pci.h$", "<sys/pci.h>"},
+          {"sys/perm.h$", "<sys/perm.h>"},
+          {"sys/personality.h$", "<sys/personality.h>"},
+          {"sys/poll.h$", "<sys/poll.h>"},
+          {"sys/prctl.h$", "<sys/prctl.h>"},
+          {"sys/procfs.h$", "<sys/procfs.h>"},
+          {"sys/profil.h$", "<sys/profil.h>"},
+          {"sys/ptrace.h$", "<sys/ptrace.h>"},
+          {"sys/queue.h$", "<sys/queue.h>"},
+          {"sys/quota.h$", "<sys/quota.h>"},
+          {"sys/raw.h$", "<sys/raw.h>"},
+          {"sys/reboot.h$", "<sys/reboot.h>"},
+          {"sys/reg.h$", "<sys/reg.h>"},
+          {"sys/resource.h$", "<sys/resource.h>"},
+          {"sys/select.h$", "<sys/select.h>"},
+          {"sys/sem.h$", "<sys/sem.h>"},
+          {"sys/sendfile.h$", "<sys/sendfile.h>"},
+          {"sys/shm.h$", "<sys/shm.h>"},
+          {"sys/signalfd.h$", "<sys/signalfd.h>"},
+          {"sys/socket.h$", "<sys/socket.h>"},
+          {"sys/stat.h$", "<sys/stat.h>"},
+          {"sys/statfs.h$", "<sys/statfs.h>"},
+          {"sys/statvfs.h$", "<sys/statvfs.h>"},
+          {"sys/swap.h$", "<sys/swap.h>"},
+          {"sys/syscall.h$", "<sys/syscall.h>"},
+          {"sys/sysctl.h$", "<sys/sysctl.h>"},
+          {"sys/sysinfo.h$", "<sys/sysinfo.h>"},
+          {"sys/syslog.h$", "<sys/syslog.h>"},
+          {"sys/sysmacros.h$", "<sys/sysmacros.h>"},
+          {"sys/termios.h$", "<sys/termios.h>"},
+          {"sys/time.h$", "<sys/select.h>"},
+          {"sys/timeb.h$", "<sys/timeb.h>"},
+          {"sys/timerfd.h$", "<sys/timerfd.h>"},
+          {"sys/times.h$", "<sys/times.h>"},
+          {"sys/timex.h$", "<sys/timex.h>"},
+          {"sys/ttychars.h$", "<sys/ttychars.h>"},
+          {"sys/ttydefaults.h$", "<sys/ttydefaults.h>"},
+          {"sys/types.h$", "<sys/types.h>"},
+          {"sys/ucontext.h$", "<sys/ucontext.h>"},
+          {"sys/uio.h$", "<sys/uio.h>"},
+          {"sys/un.h$", "<sys/un.h>"},
+          {"sys/user.h$", "<sys/user.h>"},
+          {"sys/ustat.h$", "<sys/ustat.h>"},
+          {"sys/utsname.h$", "<sys/utsname.h>"},
+          {"sys/vlimit.h$", "<sys/vlimit.h>"},
+          {"sys/vm86.h$", "<sys/vm86.h>"},
+          {"sys/vtimes.h$", "<sys/vtimes.h>"},
+          {"sys/wait.h$", "<sys/wait.h>"},
+          {"sys/xattr.h$", "<sys/xattr.h>"},
+          {"bits/epoll.h$", "<sys/epoll.h>"},
+          {"bits/eventfd.h$", "<sys/eventfd.h>"},
+          {"bits/inotify.h$", "<sys/inotify.h>"},
+          {"bits/ipc.h$", "<sys/ipc.h>"},
+          {"bits/ipctypes.h$", "<sys/ipc.h>"},
+          {"bits/mman-linux.h$", "<sys/mman.h>"},
+          {"bits/mman.h$", "<sys/mman.h>"},
+          {"bits/msq.h$", "<sys/msg.h>"},
+          {"bits/resource.h$", "<sys/resource.h>"},
+          {"bits/sem.h$", "<sys/sem.h>"},
+          {"bits/shm.h$", "<sys/shm.h>"},
+          {"bits/signalfd.h$", "<sys/signalfd.h>"},
+          {"bits/statfs.h$", "<sys/statfs.h>"},
+          {"bits/statvfs.h$", "<sys/statvfs.h>"},
+          {"bits/timerfd.h$", "<sys/timerfd.h>"},
+          {"bits/utsname.h$", "<sys/utsname.h>"},
+          {"bits/auxv.h$", "<sys/auxv.h>"},
+          {"bits/byteswap-16.h$", "<byteswap.h>"},
+          {"bits/byteswap.h$", "<byteswap.h>"},
+          {"bits/confname.h$", "<unistd.h>"},
+          {"bits/dirent.h$", "<dirent.h>"},
+          {"bits/dlfcn.h$", "<dlfcn.h>"},
+          {"bits/elfclass.h$", "<link.h>"},
+          {"bits/endian.h$", "<endian.h>"},
+          {"bits/environments.h$", "<unistd.h>"},
+          {"bits/fcntl-linux.h$", "<fcntl.h>"},
+          {"bits/fcntl.h$", "<fcntl.h>"},
+          {"bits/in.h$", "<netinet/in.h>"},
+          {"bits/ioctl-types.h$", "<sys/ioctl.h>"},
+          {"bits/ioctls.h$", "<sys/ioctl.h>"},
+          {"bits/link.h$", "<link.h>"},
+          {"bits/mqueue.h$", "<mqueue.h>"},
+          {"bits/netdb.h$", "<netdb.h>"},
+          {"bits/param.h$", "<sys/param.h>"},
+          {"bits/poll.h$", "<sys/poll.h>"},
+          {"bits/posix_opt.h$", "<bits/posix_opt.h>"},
+          {"bits/pthreadtypes.h$", "<pthread.h>"},
+          {"bits/sched.h$", "<sched.h>"},
+          {"bits/select.h$", "<sys/select.h>"},
+          {"bits/semaphore.h$", "<semaphore.h>"},
+          {"bits/sigthread.h$", "<pthread.h>"},
+          {"bits/sockaddr.h$", "<sys/socket.h>"},
+          {"bits/socket.h$", "<sys/socket.h>"},
+          {"bits/socket_type.h$", "<sys/socket.h>"},
+          {"bits/stab.def$", "<stab.h>"},
+          {"bits/stat.h$", "<sys/stat.h>"},
+          {"bits/stropts.h$", "<stropts.h>"},
+          {"bits/syscall.h$", "<sys/syscall.h>"},
+          {"bits/syslog-path.h$", "<sys/syslog.h>"},
+          {"bits/termios.h$", "<termios.h>"},
+          {"bits/types.h$", "<sys/types.h>"},
+          {"bits/typesizes.h$", "<sys/types.h>"},
+          {"bits/uio.h$", "<sys/uio.h>"},
+          {"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->addRegexMapping(Pair.first, Pair.second);
+}
+
+} // namespace clangd
+} // namespace clang

clangd/index/Index.h

struct Symbol {
   llvm::StringRef CompletionSnippetInsertText;
 
   /// Optional symbol details that are not required to be set. For example, an
   /// index fuzzy match can return a large number of symbol candidates, and it
   /// is preferable to send only core symbol information in the batched results
   /// and have clients resolve full symbol information for a specific candidate
   /// if needed.
   struct Details {
-    // Documentation including comment for the symbol declaration.
+    /// Documentation including comment for the symbol declaration.
     llvm::StringRef Documentation;
-    // This is what goes into the LSP detail field in a completion item. For
-    // example, the result type of a function.
+    /// This is what goes into the LSP detail field in a completion item. For
+    /// example, the result type of a function.
     llvm::StringRef CompletionDetail;
+    /// This can be either a URI of the header to be #include'd for this symbol,
+    /// or a literal header quoted with <> or "" that is suitable to be included
+    /// directly. When this is a URI, the exact #include path needs to be
+    /// calculated according to the URI scheme.
+    ///
+    /// If empty, FileURI in CanonicalDeclaration should be used to calculate
+    /// the #include path.
+    llvm::StringRef IncludeHeader;
   };
 
   // Optional details of the symbol.
   const Details *Detail = nullptr;
 
   // FIXME: add all occurrences support.
   // FIXME: add extra fields for index scoring signals.
 };

clangd/index/Index.cpp

static void own(Symbol &S, DenseSet<StringRef> &Strings,
 
   if (S.Detail) {
     // Copy values of StringRefs into arena.
     auto *Detail = Arena.Allocate<Symbol::Details>();
     *Detail = *S.Detail;
     // Intern the actual strings.
     Intern(Detail->Documentation);
     Intern(Detail->CompletionDetail);
+    Intern(Detail->IncludeHeader);
     // Replace the detail pointer with our copy.
     S.Detail = Detail;
   }
 }
 
 void SymbolSlab::Builder::insert(const Symbol &S) {
   auto R = SymbolIndex.try_emplace(S.ID, Symbols.size());
   if (R.second) {

clangd/index/Merge.cpp

mergeSymbol(const Symbol &L, const Symbol &R, Symbol::Details *Scratch) {
   if (O.Detail) {
     if (S.Detail) {
       // Copy into scratch space so we can merge.
       *Scratch = *S.Detail;
       if (Scratch->Documentation == "")
         Scratch->Documentation = O.Detail->Documentation;
       if (Scratch->CompletionDetail == "")
         Scratch->CompletionDetail = O.Detail->CompletionDetail;
+      if (Scratch->IncludeHeader == "")
+        Scratch->IncludeHeader = O.Detail->IncludeHeader;
       S.Detail = Scratch;
     } else
       S.Detail = O.Detail;
   }
   return S;
 }
 
 std::unique_ptr<SymbolIndex> mergeIndex(const SymbolIndex *Dynamic,
                                         const SymbolIndex *Static) {
   return llvm::make_unique<MergedIndex>(Dynamic, Static);
 }
 } // namespace clangd
 } // namespace clang

clangd/index/SymbolCollector.h

 //===--- SymbolCollector.h ---------------------------------------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
+#include "CanonicalIncludes.h"
 #include "Index.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/Decl.h"
 #include "clang/Index/IndexDataConsumer.h"
 #include "clang/Index/IndexSymbol.h"
 #include "clang/Sema/CodeCompleteConsumer.h"
 
 namespace clang {
struct Options {
     /// VFS that does not have absolute path), combine the fallback directory
     /// with symbols' paths to get absolute paths. This must be an absolute
     /// path.
     std::string FallbackDir;
     /// Specifies URI schemes that can be used to generate URIs for file paths
     /// in symbols. The list of schemes will be tried in order until a working
     /// scheme is found. If no scheme works, symbol location will be dropped.
     std::vector<std::string> URISchemes = {"file"};
+    bool CollectIncludePath = false;
+    /// If set, this is used to map symbol #include path to a potentially
+    /// different #include path.
+    const CanonicalIncludes *Includes = nullptr;
   };
 
   SymbolCollector(Options Opts);
 
   void initialize(ASTContext &Ctx) override;
 
   void setPreprocessor(std::shared_ptr<Preprocessor> PP) override {
     this->PP = std::move(PP);

clangd/index/SymbolCollector.cpp

 //===--- SymbolCollector.cpp -------------------------------------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "SymbolCollector.h"
 #include "../CodeCompletionStrings.h"
 #include "../Logger.h"
 #include "../URI.h"
+#include "CanonicalIncludes.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Index/IndexSymbol.h"
 #include "clang/Index/USRGeneration.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Path.h"
if (match(decl(allOf(Opts.IndexMainFiles
                                                      unless(isScoped())))))),
             *ND, *ASTCtx)
           .empty())
     return true;
 
   return false;
 }
 
+// We only collect #include paths for symbols that are suitable for global code
+// completion, except for namespaces since #include path for a namespace is hard
+// to define.
+bool shouldCollectIncludePath(index::SymbolKind Kind) {
+  using SK = index::SymbolKind;
+  switch (Kind) {
+  case SK::Macro:
+  case SK::Enum:
+  case SK::Struct:
+  case SK::Class:
+  case SK::Union:
+  case SK::TypeAlias:
+  case SK::Using:
+  case SK::Function:
+  case SK::Variable:
+  case SK::EnumConstant:
+    return true;
+  default:
+    return false;
+  }
+}
+
+/// Gets a canonical include (<header>  or "header") for header of \p Loc.
+/// Returns None if the header has no canonical include.
+/// FIXME: we should handle .inc files whose symbols are expected be exported by
+/// their containing headers.
+llvm::Optional<std::string>
+getIncludeHeader(const SourceManager &SM, SourceLocation Loc,
+                 const SymbolCollector::Options &Opts) {
+  llvm::StringRef FilePath = SM.getFilename(Loc);
+  if (FilePath.empty())
+    return llvm::None;
+  if (Opts.Includes) {
+    llvm::StringRef Mapped = Opts.Includes->mapHeader(FilePath);
+    if (Mapped != FilePath)
+      return (Mapped.startswith("<") || Mapped.startswith("\""))
+                 ? Mapped.str()
+                 : ("\"" + Mapped + "\"").str();
+  }
+  // If the header path is the same as the file path of the declaration, we skip
+  // storing the #include path; users can use the URI in declaration location to
+  // calculate the #include path.
+  return llvm::None;
+}
+
 // Return the symbol location of the given declaration `D`.
 //
 // For symbols defined inside macros:
 //   * use expansion location, if the symbol is formed via macro concatenation.
 //   * use spelling location, otherwise.
 llvm::Optional<SymbolLocation>
 getSymbolLocation(const NamedDecl &D, SourceManager &SM,
                   const SymbolCollector::Options &Opts,
const Symbol *SymbolCollector::addDeclaration(const NamedDecl &ND,
   getLabelAndInsertText(*CCS, &Label, &SnippetInsertText,
                         /*EnableSnippets=*/true);
   getLabelAndInsertText(*CCS, &IgnoredLabel, &PlainInsertText,
                         /*EnableSnippets=*/false);
   std::string FilterText = getFilterText(*CCS);
   std::string Documentation = getDocumentation(*CCS);
   std::string CompletionDetail = getDetail(*CCS);
 
+  std::string Include;
+  if (Opts.CollectIncludePath && shouldCollectIncludePath(S.SymInfo.Kind)) {
+    // Use the expansion location to get the #include header since this is
+    // where the symbol is exposed.
+    if (auto Header =
+            getIncludeHeader(SM, SM.getExpansionLoc(ND.getLocation()), Opts))
+      Include = std::move(*Header);
+  }
   S.CompletionFilterText = FilterText;
   S.CompletionLabel = Label;
   S.CompletionPlainInsertText = PlainInsertText;
   S.CompletionSnippetInsertText = SnippetInsertText;
   Symbol::Details Detail;
   Detail.Documentation = Documentation;
   Detail.CompletionDetail = CompletionDetail;
+  Detail.IncludeHeader = Include;
   S.Detail = &Detail;
 
   Symbols.insert(S);
   return Symbols.find(S.ID);
 }
 
 void SymbolCollector::addDefinition(const NamedDecl &ND,
                                     const Symbol &DeclSym) {

clangd/index/SymbolYAML.cpp

static void mapping(IO &io, SymbolInfo &SymInfo) {
     io.mapRequired("Lang", SymInfo.Lang);
   }
 };
 
 template <> struct MappingTraits<Symbol::Details> {
   static void mapping(IO &io, Symbol::Details &Detail) {
     io.mapOptional("Documentation", Detail.Documentation);
     io.mapOptional("CompletionDetail", Detail.CompletionDetail);
+    io.mapOptional("IncludeHeader", Detail.IncludeHeader);
   }
 };
 
 // A YamlIO normalizer for fields of type "const T*" allocated on an arena.
 // Normalizes to Optional<T>, so traits should be provided for T.
 template <typename T> struct ArenaPtr {
   ArenaPtr(IO &) {}
   ArenaPtr(IO &, const T *D) {

clangd/tool/ClangdMain.cpp

 #include "JSONRPCDispatcher.h"
 #include "Path.h"
 #include "Trace.h"
 #include "index/SymbolYAML.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/Program.h"
+#include "llvm/Support/Signals.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cstdlib>
 #include <iostream>
 #include <memory>
 #include <string>
 #include <thread>
 
 using namespace clang;

test/clangd/completion-snippets.test

 {"jsonrpc":"2.0","method":"textDocument/didOpen","params":{"textDocument":{"uri":"test:///main.cpp","languageId":"cpp","version":1,"text":"int func_with_args(int a, int b);\nint main() {\nfunc_with\n}"}}}
 ---
 {"jsonrpc":"2.0","id":1,"method":"textDocument/completion","params":{"textDocument":{"uri":"test:///main.cpp"},"position":{"line":2,"character":7}}}
 #      CHECK:  "id": 1
 # CHECK-NEXT:  "jsonrpc": "2.0",
 # CHECK-NEXT:  "result": {
 # CHECK-NEXT:    "isIncomplete": {{.*}}
 # CHECK-NEXT:    "items": [
-# CHECK-NEXT:    {
-# CHECK-NEXT:      "detail": "int",
-# CHECK-NEXT:      "filterText": "func_with_args",
+# CHECK:           "filterText": "func_with_args",
 # CHECK-NEXT:      "insertText": "func_with_args(${1:int a}, ${2:int b})",
 # CHECK-NEXT:      "insertTextFormat": 2,
 # CHECK-NEXT:      "kind": 3,
 # CHECK-NEXT:      "label": "func_with_args(int a, int b)",
 # CHECK-NEXT:      "sortText": "{{.*}}func_with_args"
 # CHECK-NEXT:    }
 # CHECK-NEXT:    ]
 # CHECK-NEXT:  }
 ---
 {"jsonrpc":"2.0","id":4,"method":"shutdown"}

test/clangd/initialize-params-invalid.test

 # CHECK-NEXT:      "documentHighlightProvider": true,
 # CHECK-NEXT:      "documentOnTypeFormattingProvider": {
 # CHECK-NEXT:        "firstTriggerCharacter": "}",
 # CHECK-NEXT:        "moreTriggerCharacter": []
 # CHECK-NEXT:      },
 # CHECK-NEXT:      "documentRangeFormattingProvider": true,
 # CHECK-NEXT:      "executeCommandProvider": {
 # CHECK-NEXT:        "commands": [
-# CHECK-NEXT:          "clangd.applyFix"
+# CHECK-NEXT:          "clangd.applyFix",
+# CHECK-NEXT:          "clangd.insertInclude"
 # CHECK-NEXT:        ]
 # CHECK-NEXT:      },
 # CHECK-NEXT:      "renameProvider": true,
 # CHECK-NEXT:      "signatureHelpProvider": {
 # CHECK-NEXT:        "triggerCharacters": [
 # CHECK-NEXT:          "(",
 # CHECK-NEXT:          ","
 # CHECK-NEXT:        ]
 # CHECK-NEXT:      },
 # CHECK-NEXT:      "textDocumentSync": 1
 # CHECK-NEXT:    }
 # CHECK-NEXT:  }
 ---
 {"jsonrpc":"2.0","id":3,"method":"shutdown"}
 ---
 {"jsonrpc":"2.0","method":"exit"}

test/clangd/initialize-params.test

 # CHECK-NEXT:      "documentHighlightProvider": true,
 # CHECK-NEXT:      "documentOnTypeFormattingProvider": {
 # CHECK-NEXT:        "firstTriggerCharacter": "}",
 # CHECK-NEXT:        "moreTriggerCharacter": []
 # CHECK-NEXT:      },
 # CHECK-NEXT:      "documentRangeFormattingProvider": true,
 # CHECK-NEXT:      "executeCommandProvider": {
 # CHECK-NEXT:        "commands": [
-# CHECK-NEXT:          "clangd.applyFix"
+# CHECK-NEXT:          "clangd.applyFix",
+# CHECK-NEXT:          "clangd.insertInclude"
 # CHECK-NEXT:        ]
 # CHECK-NEXT:      },
 # CHECK-NEXT:      "renameProvider": true,
 # CHECK-NEXT:      "signatureHelpProvider": {
 # CHECK-NEXT:        "triggerCharacters": [
 # CHECK-NEXT:          "(",
 # CHECK-NEXT:          ","
 # CHECK-NEXT:        ]

test/clangd/insert-include.test

+# RUN: clangd -lit-test < %s | FileCheck -strict-whitespace %s
+# RUN: clangd -lit-test -pch-storage=memory < %s | FileCheck -strict-whitespace %s
+{"jsonrpc":"2.0","id":0,"method":"initialize","params":{"processId":123,"rootPath":"clangd","capabilities":{},"trace":"off"}}
+---
+{"jsonrpc":"2.0","method":"textDocument/didOpen","params":{"textDocument":{"uri":"test:///main.cpp","languageId":"cpp","version":1,"text":"void f() {}"}}}
+---
+{"jsonrpc":"2.0","id":3,"method":"workspace/executeCommand","params":{"arguments":[{"header":"<vector>","textDocument":{"uri":"test:///main.cpp"}}],"command":"clangd.insertInclude"}}
+#      CHECK:    "id": 3,
+# CHECK-NEXT:    "jsonrpc": "2.0",
+# CHECK-NEXT:    "result": "Inserted header <vector>"
+# CHECK-NEXT:  }
+#      CHECK:    "method": "workspace/applyEdit",
+# CHECK-NEXT:    "params": {
+# CHECK-NEXT:      "edit": {
+# CHECK-NEXT:        "changes": {
+# CHECK-NEXT:          "file:///clangd-test/main.cpp": [
+# CHECK-NEXT:            {
+# CHECK-NEXT:              "newText": "#include <vector>\n",
+# CHECK-NEXT:              "range": {
+# CHECK-NEXT:                "end": {
+# CHECK-NEXT:                  "character": 0,
+# CHECK-NEXT:                  "line": 0
+# CHECK-NEXT:                },
+# CHECK-NEXT:                "start": {
+# CHECK-NEXT:                  "character": 0,
+# CHECK-NEXT:                  "line": 0
+# CHECK-NEXT:                }
+# CHECK-NEXT:              }
+# CHECK-NEXT:            }
+# CHECK-NEXT:          ]
+# CHECK-NEXT:        }
+# CHECK-NEXT:      }
+# CHECK-NEXT:    }
+# CHECK-NEXT:  }
+---
+{"jsonrpc":"2.0","id":4,"method":"shutdown"}

unittests/clangd/CMakeLists.txt

add_extra_unittest(ClangdTests
   Annotations.cpp
   ClangdTests.cpp
   ClangdUnitTests.cpp
   CodeCompleteTests.cpp
   CodeCompletionStringsTests.cpp
   ContextTests.cpp
   FileIndexTests.cpp
   FuzzyMatchTests.cpp
+  HeadersTests.cpp
   IndexTests.cpp
   JSONExprTests.cpp
   SourceCodeTests.cpp
   SymbolCollectorTests.cpp
   SyncAPI.cpp
   TestFS.cpp
   ThreadingTests.cpp
   TraceTests.cpp

unittests/clangd/ClangdTests.cpp

 //===-- ClangdTests.cpp - Clangd unit tests ---------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "ClangdLSPServer.h"
 #include "ClangdServer.h"
 #include "Matchers.h"
 #include "SyncAPI.h"
 #include "TestFS.h"
+#include "URI.h"
 #include "clang/Config/config.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/Regex.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
std::string replacePtrsInDump(std::string const &Dump) {
   return Result;
 }
 
 std::string dumpASTWithoutMemoryLocs(ClangdServer &Server, PathRef File) {
   auto DumpWithMemLocs = runDumpAST(Server, File);
   return replacePtrsInDump(DumpWithMemLocs);
 }
 
-} // namespace
-
 class ClangdVFSTest : public ::testing::Test {
 protected:
   std::string parseSourceAndDumpAST(
       PathRef SourceFileRelPath, StringRef SourceContents,
       std::vector<std::pair<PathRef, StringRef>> ExtraFiles = {},
       bool ExpectErrors = false) {
     MockFSProvider FS;
     ErrorCheckingDiagConsumer DiagConsumer;
ClangdServer Server(CDB, DiagConsumer, FS, /*AsyncThreadsCount=*/4,
                       /*StorePreamblesInMemory=*/true);
   Server.addDocument(FooCpp, SourceContentsWithErrors);
   StartSecond.wait();
   Server.addDocument(FooCpp, SourceContentsWithoutErrors);
   ASSERT_TRUE(Server.blockUntilIdleForTest()) << "Waiting for diagnostics";
   ASSERT_EQ(DiagConsumer.Count, 2); // Sanity check - we actually ran both?
 }
 
+TEST_F(ClangdVFSTest, InsertIncludes) {
+  MockFSProvider FS;
+  ErrorCheckingDiagConsumer DiagConsumer;
+  MockCompilationDatabase CDB;
+  ClangdServer Server(CDB, DiagConsumer, FS,
+                      /*AsyncThreadsCount=*/0,
+                      /*StorePreamblesInMemory=*/true);
+
+  // No need to sync reparses, because reparses are performed on the calling
+  // thread.
+  auto FooCpp = testPath("foo.cpp");
+  const auto Code = R"cpp(
+#include "x.h"
+
+void f() {}
+)cpp";
+  FS.Files[FooCpp] = Code;
+  Server.addDocument(FooCpp, Code);
+
+  auto Inserted = [&](llvm::StringRef Header, llvm::StringRef Expected) {
+    auto Replaces = Server.insertInclude(FooCpp, Code, Header);
+    EXPECT_TRUE(static_cast<bool>(Replaces));
+    auto Changed = tooling::applyAllReplacements(Code, *Replaces);
+    EXPECT_TRUE(static_cast<bool>(Changed));
+    return llvm::StringRef(*Changed).contains(
+        (llvm::Twine("#include ") + Expected + "").str());
+  };
+
+  EXPECT_TRUE(Inserted("\"y.h\"", "\"y.h\""));
+  EXPECT_TRUE(Inserted("<string>", "<string>"));
+}
+
+} // namespace
 } // namespace clangd
 } // namespace clang

unittests/clangd/HeadersTests.cpp

+//===-- HeadersTests.cpp - Include headers unit tests -----------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "Headers.h"
+#include "TestFS.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+namespace clang {
+namespace clangd {
+namespace {
+
+class HeadersTest : public ::testing::Test {
+public:
+  HeadersTest() {
+    CDB.ExtraClangFlags = {SearchDirArg.c_str()};
+    FS.Files[MainFile] = "";
+  }
+
+protected:
+  // Adds \p File with content \p Code to the sub directory and returns the
+  // absolute path.
+//  std::string addToSubdir(PathRef File, llvm::StringRef Code = "") {
+//    assert(llvm::sys::path::is_relative(File) && "FileName should be relative");
+//    llvm::SmallString<32> Path;
+//    llvm::sys::path::append(Path, Subdir, File);
+//    FS.Files[Path] = Code;
+//    return Path.str();
+//  };
+
+  // Shortens the header and returns "" on error.
+  std::string shorten(PathRef Header) {
+    auto VFS = FS.getTaggedFileSystem(MainFile).Value;
+    auto Cmd = CDB.getCompileCommand(MainFile);
+    assert(static_cast<bool>(Cmd));
+    VFS->setCurrentWorkingDirectory(Cmd->Directory);
+    auto Path =
+        shortenIncludePath(MainFile, FS.Files[MainFile], Header, *Cmd, VFS);
+    if (!Path) {
+      llvm::consumeError(Path.takeError());
+      return std::string();
+    }
+    return std::move(*Path);
+  }
+  MockFSProvider FS;
+  MockCompilationDatabase CDB;
+  std::string MainFile = testPath("main.cpp");
+  std::string Subdir = testPath("sub");
+  std::string SearchDirArg = (llvm::Twine("-I") + Subdir).str();
+};
+
+TEST_F(HeadersTest, InsertInclude) {
+  std::string Path = testPath("sub/bar.h");
+  FS.Files[Path] = "";
+  EXPECT_EQ(shorten(Path), "\"bar.h\"");
+}
+
+TEST_F(HeadersTest, DontInsertDuplicateSameName) {
+  FS.Files[MainFile] = R"cpp(
+#include "bar.h"
+)cpp";
+  std::string BarHeader = testPath("sub/bar.h");
+  FS.Files[BarHeader] = "";
+  EXPECT_EQ(shorten(BarHeader), "");
+}
+
+TEST_F(HeadersTest, DontInsertDuplicateDifferentName) {
+  std::string BarHeader = testPath("sub/bar.h");
+  FS.Files[BarHeader] = "";
+  FS.Files[MainFile] = R"cpp(
+#include "sub/bar.h"  // not shortest
+)cpp";
+  EXPECT_EQ(shorten(BarHeader), "");
+}
+
+TEST_F(HeadersTest, StillInsertIfTrasitivelyIncluded) {
+  std::string BazHeader = testPath("sub/baz.h");
+  FS.Files[BazHeader] = "";
+  std::string BarHeader = testPath("sub/bar.h");
+  FS.Files[BarHeader] = R"cpp(
+#include "baz.h"
+)cpp";
+  FS.Files[MainFile] = R"cpp(
+#include "bar.h"
+)cpp";
+  EXPECT_EQ(shorten(BazHeader), "\"baz.h\"");
+}
+
+} // namespace
+} // namespace clangd
+} // namespace clang
+

unittests/clangd/SymbolCollectorTests.cpp

 }
 MATCHER_P(Doc, D, "") { return arg.Detail && arg.Detail->Documentation == D; }
 MATCHER_P(Plain, Text, "") { return arg.CompletionPlainInsertText == Text; }
 MATCHER_P(Snippet, S, "") {
   return arg.CompletionSnippetInsertText == S;
 }
 MATCHER_P(QName, Name, "") { return (arg.Scope + arg.Name).str() == Name; }
 MATCHER_P(DeclURI, P, "") { return arg.CanonicalDeclaration.FileURI == P; }
+MATCHER_P(IncludeHeader, P, "") {
+  return arg.Detail && arg.Detail->IncludeHeader == P;
+}
 MATCHER_P(DeclRange, Offsets, "") {
   return arg.CanonicalDeclaration.StartOffset == Offsets.first &&
       arg.CanonicalDeclaration.EndOffset == Offsets.second;
 }
 MATCHER_P(DefRange, Offsets, "") {
   return arg.Definition.StartOffset == Offsets.first &&
          arg.Definition.EndOffset == Offsets.second;
 }
 
 namespace clang {
 namespace clangd {
 
 namespace {
 class SymbolIndexActionFactory : public tooling::FrontendActionFactory {
 public:
-  SymbolIndexActionFactory(SymbolCollector::Options COpts)
-      : COpts(std::move(COpts)) {}
+  SymbolIndexActionFactory(SymbolCollector::Options COpts,
+                           CommentHandler *PragmaHandler)
+      : COpts(std::move(COpts)), PragmaHandler(PragmaHandler) {}
 
   clang::FrontendAction *create() override {
+    class WrappedIndexAction : public WrapperFrontendAction {
+    public:
+      WrappedIndexAction(std::shared_ptr<SymbolCollector> C,
+                         const index::IndexingOptions &Opts,
+                         CommentHandler *PragmaHandler)
+          : WrapperFrontendAction(
+                index::createIndexingAction(C, Opts, nullptr)),
+            PragmaHandler(PragmaHandler) {}
+
+      std::unique_ptr<ASTConsumer>
+      CreateASTConsumer(CompilerInstance &CI, StringRef InFile) override {
+        if (PragmaHandler)
+          CI.getPreprocessor().addCommentHandler(PragmaHandler);
+        return WrapperFrontendAction::CreateASTConsumer(CI, InFile);
+      }
+
+    private:
+      index::IndexingOptions IndexOpts;
+      CommentHandler *PragmaHandler;
+    };
     index::IndexingOptions IndexOpts;
     IndexOpts.SystemSymbolFilter =
         index::IndexingOptions::SystemSymbolFilterKind::All;
     IndexOpts.IndexFunctionLocals = false;
     Collector = std::make_shared<SymbolCollector>(COpts);
-    FrontendAction *Action =
-        index::createIndexingAction(Collector, IndexOpts, nullptr).release();
-    return Action;
+    return new WrappedIndexAction(Collector, std::move(IndexOpts),
+                                  PragmaHandler);
   }
 
   std::shared_ptr<SymbolCollector> Collector;
   SymbolCollector::Options COpts;
+  CommentHandler *PragmaHandler;
 };
 
 class SymbolCollectorTest : public ::testing::Test {
 public:
   SymbolCollectorTest()
-      : TestHeaderName(testPath("symbol.h")),
+      : InMemoryFileSystem(new vfs::InMemoryFileSystem),
+        TestHeaderName(testPath("symbol.h")),
         TestFileName(testPath("symbol.cc")) {
     TestHeaderURI = URI::createFile(TestHeaderName).toString();
     TestFileURI = URI::createFile(TestFileName).toString();
   }
 
   bool runSymbolCollector(StringRef HeaderCode, StringRef MainCode,
                           const std::vector<std::string> &ExtraArgs = {}) {
-    llvm::IntrusiveRefCntPtr<vfs::InMemoryFileSystem> InMemoryFileSystem(
-        new vfs::InMemoryFileSystem);
     llvm::IntrusiveRefCntPtr<FileManager> Files(
         new FileManager(FileSystemOptions(), InMemoryFileSystem));
 
-    auto Factory = llvm::make_unique<SymbolIndexActionFactory>(CollectorOpts);
+    auto Factory = llvm::make_unique<SymbolIndexActionFactory>(
+        CollectorOpts, PragmaHandler.get());
 
     std::vector<std::string> Args = {"symbol_collector", "-fsyntax-only",
                                      "-std=c++11",       "-include",
                                      TestHeaderName,     TestFileName};
     Args.insert(Args.end(), ExtraArgs.begin(), ExtraArgs.end());
     tooling::ToolInvocation Invocation(
         Args,
         Factory->create(), Files.get(),
         std::make_shared<PCHContainerOperations>());
 
     InMemoryFileSystem->addFile(TestHeaderName, 0,
                                 llvm::MemoryBuffer::getMemBuffer(HeaderCode));
     InMemoryFileSystem->addFile(TestFileName, 0,
                                 llvm::MemoryBuffer::getMemBuffer(MainCode));
     Invocation.run();
     Symbols = Factory->Collector->takeSymbols();
     return true;
   }
 
 protected:
+  llvm::IntrusiveRefCntPtr<vfs::InMemoryFileSystem> InMemoryFileSystem;
   std::string TestHeaderName;
   std::string TestHeaderURI;
   std::string TestFileName;
   std::string TestFileURI;
   SymbolSlab Symbols;
   SymbolCollector::Options CollectorOpts;
+  std::unique_ptr<CommentHandler> PragmaHandler;
 };
 
 TEST_F(SymbolCollectorTest, CollectSymbols) {
   CollectorOpts.IndexMainFiles = true;
   const std::string Header = R"(
     class Foo {
       void f();
     };
std::string ConcatenatedYAML;
     SymbolsToYAML(Symbols2, OS);
   }
   auto ConcatenatedSymbols = SymbolsFromYAML(ConcatenatedYAML);
   EXPECT_THAT(ConcatenatedSymbols,
               UnorderedElementsAre(QName("clang::Foo1"),
                                    QName("clang::Foo2")));
 }
 
+TEST_F(SymbolCollectorTest, IncludeHeaderSameAsFileURI) {
+  CollectorOpts.CollectIncludePath = true;
+  runSymbolCollector("class Foo {};", /*Main=*/"");
+  EXPECT_THAT(Symbols,
+              UnorderedElementsAre(AllOf(QName("Foo"), DeclURI(TestHeaderURI),
+                                         IncludeHeader(""))));
+}
+
+#ifndef LLVM_ON_WIN32
+TEST_F(SymbolCollectorTest, CanonicalSTLHeader) {
+  CollectorOpts.CollectIncludePath = true;
+  CanonicalIncludes Includes;
+  addSystemHeadersMapping(&Includes);
+  CollectorOpts.Includes = &Includes;
+  // bits/basic_string.h$ should be mapped to <string>
+  TestHeaderName = "/nasty/bits/basic_string.h";
+  TestFileName = "/nasty/bits/basic_string.cpp";
+  TestHeaderURI = URI::createFile(TestHeaderName).toString();
+  runSymbolCollector("class string {};", /*Main=*/"");
+  EXPECT_THAT(Symbols, UnorderedElementsAre(AllOf(QName("string"),
+                                                  DeclURI(TestHeaderURI),
+                                                  IncludeHeader("<string>"))));
+}
+#endif
+
+TEST_F(SymbolCollectorTest, IWYUPragma) {
+  CollectorOpts.CollectIncludePath = true;
+  CanonicalIncludes Includes;
+  PragmaHandler = collectIWYUHeaderMaps(&Includes);
+  CollectorOpts.Includes = &Includes;
+  const std::string Header = R"(
+    // IWYU pragma: private, include the/good/header.h
+    class Foo {};
+  )";
+  runSymbolCollector(Header, /*Main=*/"");
+  EXPECT_THAT(Symbols, UnorderedElementsAre(
+                           AllOf(QName("Foo"), DeclURI(TestHeaderURI),
+                                 IncludeHeader("\"the/good/header.h\""))));
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang