[clangd] Add support for missing includes analysis.

[VitaNuo]

Address review comments. Make diagnostics symref-centered and attach them to each reference.

[VitaNuo]

Thanks for the extensive explanations! See the updated version, it should also take the discussions on the document into account.

clang-tools-extra/clangd/IncludeCleaner.cpp

503

Oh yeah makes sense.

504

Ok.

512

Ok, got it. We only use the include conversion for matching, and matching seems not to use line numbers. I guess it's the reason nothing fails.
I can't write a test for this function directly since it's in an anonymous namespace.

514

Ok I will skip unresolved includes. But I am not sure I fully understand. We do the following:

1. Convert clangd includes to include-cleaner includes.
2. Match include-cleaner includes with symbol providers.
3. If match found, symbol reference is satisfied.

How does it matter in this scenario if the include is resolved? AFAIU as long as the header is spelled in the main file + it's matched with a symbol provider, we should say that the symbol reference is satisfied.

Otherwise, it seems like we'll say that the header is missing, although it's there in the main file and unresolved.

I don't know if this is in any way a realistic scenario. I am just approaching it with general logic, and in this sense having more "satisfied" symbols seems better than having less => leads to less false positives. It can lead to false negatives, too, but AFAIU false negatives are much less of a risk for missing include management.

526

Sure. The new design does this, as well as skipping the header name.

526

Oh this is cool. Didn't realize we can do straight from a resolved include to the ID. Thanks.

540

Ok, sure. What's a PP-disabled region? Are you talking about #ifdef's and such?

547

Thank you for the great explanation!

552

Yes, storing per Symbol totally makes sense. Let's discuss specifics in the corresponding document.

558

Yes, this comment goes along the lines of the design discussion we are having at the moment.

again in big files it might be impossible to see the first range the diagnostic is attached to and people have a tendency to only care about the parts of the code they've touched

this is AFAIU in conflict with the suggestion that the diagnostic should only be attached to the first reference.

558

any reason for storing tokens?

I was primarily avoiding clang::Range since it requires llvm::Code to build ranges, and didn't want computeIncludeCleanerFindings to depend on anything but the AST. But syntax::FileRange sounds good.

581

Ok, great. Didn't know it was Ok to test std::optional directly in an if clause.

713

sure.

[kadircet]

clang-tools-extra/clangd/IncludeCleaner.cpp

343

unfortunately getFile returns an llvm::Expected which requires explicit error handling (or it'll trigger a crash). you can simply elog the issue:

if (!FE) {
  elog("IncludeCleaner: Failed to get an entry for resolved path {0}: {1}", Inc.Resolved, FE.takeError());
  continue;
}

467

this should also be either static or put into anon namespace

514

generateMissingIncludeDiagnostics should also be either static or put into anon namespace

514

How does it matter in this scenario if the include is resolved? AFAIU as long as the header is spelled in the main file + it's matched with a symbol provider, we should say that the symbol reference is satisfied.

It doesn't matter at a high-level view. But since the implementation recognizes headers based on the HeaderID and it's only defined for resolved includes, if we were to have any unresolved include matches somehow (e.g. it has spelling "foo/bar.h", but is unresolved, and we do a match based on spelling because some IWYU pragma pointed at this header), we would hit the assertion around HeaderID always having value.

515

i think it's better to use an llvm::ArrayRef instead of llvm::SmallVector for diag infos here, we don't need to copy.

519

nit: Result.push_back(std::move(D)), as D has lots of strings in it, it might be expensive to copy it around. Even better if you construct the Diag in place via Diag &D = Result.emplace_back(), you can achieve this by moving all the logic that might bail out (e.g. replacement generation) to the top of the loop, and start forming the diagnostic only after we're sure that there'll be one.

523

we've got Config::Diagnostics::Includes::IgnoreHeader that disables include-cleaner analysis on headers that match a pattern. we should be respecting those config options here too.

526

i feel like there's actually value in keeping the header name around, i.e. the user will have some idea about the action, without triggering an extra interaction. this helps especially in cases where the finding is wrong, they'll discover this sooner, hence we'll be more likely to receive bug reports. but don't really have a strong preference, so feel free to keep it that way.

540

What's a PP-disabled region

Yes, I was trying to say "preprocessor disabled region". e.g. in a piece of code like:

#if 0
#include "foo.h"
#endif

preprocessor won't actually trigger inclusion of "foo.h", but most of the heuristic parsers (most importantly the logic in HeaderIncludes) will treat this include as usual.

542

could you add a comment here, as this is subtle, something like We might suggest insertion of an existing include in edge cases, e.g. include is present in a PP-disabled region, or spelling of the header turns out to be the same as one of the unresolved includes in the main file

675

this also needs to be static or put into anon namespace

676

no need to copy the vector by taking a std::vector here, you can take an llvm::ArrayRef instead.

709

can you restore std::move?

712

nit: it might be worth re-writing the following section as:

std::vector<Diag> Result = generateUnusedIncludeDiagnostics(AST.tuPath(),
                Cfg.Diagnostics.UnusedIncludes == Strict ? computeUnusedIncludes(AST) : Findings.UnusedIncludes, Code);
llvm::move(generateMissingIncludeDiagnostics(AST, MissingIncludes, Code),
             std::back_inserter(Result));

and move the checks like if (Cfg.Diagnostics.MissingIncludes == Config::IncludesPolicy::Strict && !Cfg.Diagnostics.Suppress.contains("missing-includes")) into the specific function, e.g. generateUnusedIncludeDiagnostics, as they already do some of the diagnostic filtering logic.

718

s/AST.getSourceManager()/SM

725

can you introduce a trace::Span wrapping the call to walkUsed with name IncludeCleanerAnalysis so that we can collect some stats about latency here?

737

nit: drop either * or & (preferably &), having a reference vs a pointer doesn't make any differences performance wise, but creates a confusion (as we don't realy need a reference to a pointer here)

747

nit: we prefer early exits to extra nesting, e.g. rewriting this as:

if (Satisfied || Providers.empty() || Ref.RT != Explicit)
  continue;
const auto &TB = AST.getTokens();
auto SpelledTokens = TB.spelledForExpanded(...);
if (!SpelledTokens)
  continue;
...

increases readability by:

• reducing the nesting
• making it more explicit about under what assumptions the rest of the code is working

751

nit: auto Range = syntax::Token::range(SM, SpelledForExpanded->front(), SpelledForExpanded->back());

754–757

you don't need to explicitly copy Providers into ProviderHeaders, you can pass it directly to DiagInfo below.

766

we use llvm casts, specifically llvm::dyn_cast<NamedDecl*>(&Ref.Target.declaration())->getQualifiedNameAsString()

767

getQualifiedNameAsString is going to print names that are really ugly at certain times, but unfortunately that's a problem we don't have a great solution to. so no action needed ATM, but we might want to switch between qualified and unqualified name depending on the length at the very least (e.g. symbol is coming from a templated class, which has a nasty nested instantiation).

771

nit: MissingIncludes.emplace_back(std::move(SymbolName), Range, Providers);

777

nit: you'd want std::moves here, around both of them

clang-tools-extra/clangd/IncludeCleaner.h

37

it seems unfortunate that we're duplicating these strings for each diag we want to emit. it might be better to just store a Symbol here (similar to Header) and delay spelling until needed.

42

nit: std::tie(SymbolName, SymRefRange, Providers) == std::tie(Other.SymbolName, ...);

I'd also put the SymbolName match to be the last, as it's a string match and might be more costly (if we can bail out early)

49

I don't think we've much to gain by using SmallVector here, instead of std::vector

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

416

i don't think there's much value in testing out analysis here, we should rather focus on diagnostics generation, which isn't part of computeIncludeCleanerFindings. existing tests were focused on analysis, because legacy implementation for include-cleaner was actually performing these analysis itself.

so I'd rather suggest having trivial test cases (from include-cleaner analysis perspective, no need for complicated directory/file layouts) and rather test things out through calls to generateMissingIncludeDiagnostics to make sure diagnostics has the right ranges, text and fix contents.

right now we're not testing:

• header spelling
• symbol name generation
• ranges these diagnostics correspond to

and these are the main functionality we're adding on top of include-cleaner analysis.

you can take a look at the tests in llvm/llvm-project/clang-tools-extra/clangd/unittests/DiagnosticsTests.cpp to see how we're testing out diagnostics ranges, messages, fixes and what kind of helpers/matchers we have for them.

[VitaNuo]

Address review comments (apart from testing).

[VitaNuo]

Thanks for the comments! I should have addressed everything apart from testing.

clang-tools-extra/clangd/IncludeCleaner.cpp

343

It returns llvm::ErrorOr, if I am not mistaken. There was explicit error handling already (if (!FE) continue below), just without the elog. Are you trying to say it will crash without the logging? Not sure that's feasible :)
Added the logging.

467

sure, thanks.

514

Well then generateUnusedIncludeDiagnostics too, I guess.

514

Ah ok, makes sense.

519

Sure. Doing the in-place construction now.

523

Ok, added that. Please have a look. At the moment it's trying to run filters on the output of the spellHeader method.

526

Hm I'd expect we'll actually have a higher probability to receive a bug report if the user clicks on the "Quick fix" and gets a wrong header included, because that's annoying :)
Having a full message on hover, seeing that it's wrong and just ignoring it might not be annoying enough to file a bug ;-)

But this is a pure speculation ofc.
I think the point discussed on the design document makes sense: without mentioning the header name it will be a bit easier to extend this to suggesting multiple fixes. So if that's the general direction, I'd prefer to keep it the current way.

540

thanks.

542

Ok sure.

675

Ah didn't realize that you also left a comment here when replying to the identical comment on generateMissingIncludeDiagnostics. Should be done.

676

Oh this isn't even my code, but as long as it's a small change, sure :)

709

I'd rather do the emplacing, so that it's the same as in the generateMissingIncludeDiagnostics.

712

nit: it might be worth re-writing the following section as

This code seems to ignore the option Config::IncludesPolicy::None. It's saying to either return the old-style clangd results in case of Strict or include-cleaner results otherwise (incl. in case of None). Am I missing something?

and move the checks like ...

Ok, moved into generateMissingIncludeDiagnostics.

725

Sure.

767

Ok so for now no action, IIUC.

771

This does not compile. Seems like it needs a certain type of constructor to be present in MissingIncludeDiagInfo, whereas atm it's just a struct.

clang-tools-extra/clangd/IncludeCleaner.h

37

I'm not sure I can see your point re delaying spelling until needed.
Each MissingIncludeDiagInfo corresponds to one diagnostic.

Whether we resolve the Symbol to the SymbolName during analysis (i.e., walkUsed) or in diagnostic generation (i.e., generateMissingIncludeDiagnostics), does not change the fact that the same symbol will be resolved to its name multiple times.

As discussed in the doc, this results in simpler code than the version that maps a single Symbol object to multiple Ranges and Providers.
AFAICS, the implementation of Symbol to SymbolName resolution does not seem to be very expensive either.

42

Ok, sure. I can see your point with the string comparisons. But I don't fully see the point of using std::tie here. What is so great about creating an extra object, even if it only stores references? Is it a purely stylistic suggestion?

49

Sure. I'm not so clear on the preferences yet. AFAIU your point, stdlib is to be preferred unless the llvm alternative is clearly beneficial. Is that the case?

[kadircet]

clang-tools-extra/clangd/IncludeCleaner.cpp

291

can you also change the logic here to use isFilteredByConfig (we need the native call inside isFilteredByConfig as well to make sure it works on windows)

343

It returns llvm::ErrorOr, if I am not mistaken.

Ah you're right, I confused it with getFileRef. So in theory ErrorOr doesn't require explicit checking hence it won't trigger a crash if destroyed while containing an error.

Are you trying to say it will crash without the logging? Not sure that's feasible :)

Right, it isn't the logging that'll prevent the crash but rather a combination of the call to takeError and the way elog consumes Error objects. But it isn't relevant here, as ErrorOr doesn't require mandatory handling.

357

nit: you can directly define SpelledHeader at line 377

392

this shouldn't be spelling, it should be the resolved path of the include.

417

can you prefix this with IncludeCleaner: and rather say not diagnosing missing include {0}, filtered by config to add a bit more context about what specific interaction the log is coming from

445

nit:

auto &F = D.Fixes.emplace_back();
F.Message = ...;
F.Edits.push_back(replacementToEdit(...));

449

nit: it'd put this next to D.File above

526

I think the point discussed on the design document makes sense: without mentioning the header name it will be a bit easier to extend this to suggesting multiple fixes. So if that's the general direction, I'd prefer to keep it the current way.

Well, it's unclear when we'll get there, and moreover my suggestion was actually to still mention the header name when there's only a single provider (which will be the case most of the time).

But this is a pure speculation ofc.

But yeah, my point of view is also mostly speculation. So feel free to keep it this way, I'll just be grumpy :P

559

auto Range = syntax::Token::range(SM, SpelledForExpanded->front(), SpelledForExpanded->back());

561

as mentioned elsewhere, i think we should delay this symbol name spelling to diagnostic generation. to make sure core analysis we perform don't do work that might not get re-used (e.g. if we're not going to diagnose missing includes, or in the future when we don't care about spelling of all the symbols)

576

nit: I think logically it makes more sense for us to return set of Used includes here, and let the interaction that issues unused include diagnostics to derive this information from the set of used includes, and change the the missingincludes to a vector< tuple<Symbol, Ref, Providers> > (not only the unsatisfied ones) would represent the analysis better and make it more usable in the future (i.e. when we want to augment Hover responses, we can't re-use all the logic in here, we really need to implement another call to walkUsed because the analysis we get out of this call won't contain information for satisfied symbols.

no need to do it now though, we can perform that kind of refactoring as we're adding the features too (or maybe it'll actually look neater to just have another call in those features rather than try and re-use the logic here)

676

well, this is our code in the end :D

712

This code seems to ignore the option Config::IncludesPolicy::None. It's saying to either return the old-style clangd results in case of Strict or include-cleaner results otherwise (incl. in case of None). Am I missing something?

Well that was to be addressed by second part of the comment And move the checks like if (Cfg.Diagnostics.MissingIncludes == Config::IncludesPolicy::Strict && !Cfg.Diagnostics.Suppress.contains("missing-includes")) into the specific function, e.g. generateUnusedIncludeDiagnostics, as they already do some of the diagnostic filtering logic.
I was talking about both missing and unused include diagnostics generation (hence e.g.), similar to the early exit in generateMissingIncludeDiagnostics, we should have one that returns an empty set of diagnostics, when it's suppressed or not enabled.

777

oops, i forgot to put the surrounding {} it should've been MissingIncludes.emplace_back({...});

clang-tools-extra/clangd/IncludeCleaner.h

37

Whether we resolve the Symbol to the SymbolName during analysis (i.e., walkUsed) or in diagnostic generation (i.e., generateMissingIncludeDiagnostics), does not change the fact that the same symbol will be resolved to its name multiple times.

we might not generate those diagnostics always, e.g. missing-includes is disabled, but unused-includes is on, or maybe we're going to use these results for something else like Hover responses.

As discussed in the doc, this results in simpler code than the version that maps a single Symbol object to multiple Ranges and Providers.

I wasn't trying to suggest having a map here, I was suggesting just storing a Symbol S instead of string Name.

AFAICS, the implementation of Symbol to SymbolName resolution does not seem to be very expensive either.

Well, generating strings are usually expensive (not asymptotically but in practice, as they tend to require lots of memory allocations).

42

right, the comments with nit: prefix are usually things that won't matter much in practice, but reflects my (well, in the general case the reviewer's) or codebase's preference.

49

stdlib is to be preferred unless the llvm alternative is clearly beneficial

Right. llvm::SmallVector and std::vector have different use cases, we usually go for the former if we're sure that number of elements we want to store are going to be handful (literally less than 10) most of the time and the size of the objects themselves is not too big.

As SmallVector chooses to store objects internally (until it grows too much), rather than allocating a bunch of memory elsewhere and just storing a pointer (as std::vector does). This has benefits when your vector isn't going to grow beyond smallvector's limits (you don't need to pay for memory allocations, which are expensive), but has other costs (e.g. moving a std::vector is trivial as it's just assignment of a pointer and size, but moving a smallvector might not be as trivial (it at least needs to move all the elements) also the initial memory cost for smallvector is higher than std::vector (as it takes up the same space independent of it's fullness).

So in this example, we're unlikely to have a small number of MissingIncludes, MissingIncludeDiagInfo is a big enough struct (vector and filerange add up to more than 30 bytes). Hence std::vector feels like the better choice.

[VitaNuo]

Address review comments.

[VitaNuo]

Thanks for the comments!

clang-tools-extra/clangd/IncludeCleaner.cpp

343

thanks for the explanation.

392

Ok thanks.

676

Sorry, wrong wording. I meant to say that this is not the code that has been touched in this patch. It might sometimes get annoying when comments on the patch dig too deep into code that's not in the diff.

712

Ok, I've refactored more of the config checking logic inside generate.. functions.

777

No this seems to be even more wrong.
stl_vector.h(1303, 2): Candidate template ignored: substitution failure: deduced incomplete pack <(no value)> for template parameter '_Args'.

This is for the version with braces.

And this is for no braces:

/usr/bin/../lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/bits/new_allocator.h:175:23: error: no matching constructor for initialization of 'clang::clangd::MissingIncludeDiagInfo'
        { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }

It seems that it just doesn't cooperate with structs.

clang-tools-extra/clangd/IncludeCleaner.h

49

thanks!

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

416

Thank you, this makes sense. However, I believe we need to use issueIncludeCleanerDiagnosticsrather than generateMissingIncludeDiagnostics, since the latter is private.

[VitaNuo]

clang-tools-extra/clangd/IncludeCleaner.cpp

561

Ok should be done now.

576

Thanks. This might very well be the case, but this comment also seems to suggest some premature optimization (in a way). It totally makes sense to re-use what's re-usable, but this sort of refactoring really only makes sense once we have a clear use case (and get there :)

clang-tools-extra/clangd/IncludeCleaner.h

37

Ok, agreed. Storing symbols now. Having only unused include analysis on is a convincing use case.

[VitaNuo]

Upload once again.

[VitaNuo]

Merge upstream changes.

[kadircet]

thanks! looks amazing, we're missing a little bit of test coverage though

clang-tools-extra/clangd/IncludeCleaner.cpp

264

s/HeaderSpelling/HeaderPath

266

s/Path/NormalizedPath

391

what about just resolvedPath, if you'd rather keep the verb, i think get makes more sense than find. we're not really searching anything.

395

nit: you can directly return SymProvider.physical()->tryGetRealPathName(); (same for other 2 cases) and have an llvm_unreachable("Unknown symbol kind"); after the switch statement.

398

in this and the next case we need to trim <>"

407

same as above, either just symbolName or get

411

again you can just return here and below

411

getName is a StringRef, and unfortunately there are some platforms (like darwin) that don't support implicit conversion from stringrefs to std::string. so can you call .str() explicitly in the end?

714

i think for now this should be

if (Cfg.Diagnostics.MissingIncludes == Config::IncludesPolicy::Strict ||
  Cfg.Diagnostics.UnusedIncludes == Config::IncludesPolicy::Experiment) {

otherwise we'll run both legacy and new analysis for UnusedIncludes == Strict

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

415

this is pointing at the declaration inside b.h not to the reference inside the main file. are you sure this test passes?

435

can you also add a reference (and declaration) for std::vector, and have an IWYU private pragma in one of the headers to test code paths that spell verbatim and standard headers? also having some diagnostic suppressed via IgnoreHeaders is important to check

447

can you make one of these names qualified? e.g. namespace ns { struct Bar { void f(); }; }

[VitaNuo]

Improve test coverage.

[VitaNuo]

Thank you for all the thoughtful comments!

clang-tools-extra/clangd/IncludeCleaner.cpp

391

Ok, let's call it get. I do prefer verbs for methods, that's correct.

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

415

Yes, all the tests pass.
D is a Decl from the main file, otherwise it wouldn't have passed the safeguard if (!SM.isWrittenInMainFile(SM.getExpansionLoc(D->getLocation()))) continue; above.

435

Thank you for the great tips on improving test coverage!

In fact, I had to also introduce support for private pragmas, as they were not taken care of. Hopefully, the solution will make sense to you.

[kadircet]

thanks, looks great!

clang-tools-extra/clangd/IncludeCleaner.cpp

426

we should respect the style configurations (sorry for missing this in previous iterations).

you can get the relevant style with: clang::format::getStyle, which has an IncludeStyle. in case the getStyle fails, we should fallback to clang::format::getLLVMStyle as we do in other places. you can get at the relevant VFS instance through sourcemanager.

541

you can directly use !Pragmas->isPrivate(Inc->Resolved) here, instead of getpublic

541

this check seems to be new. what's the reason for rejecting private providers? I can see that we might want to be conservative by not inserting private providers, but treating symbols as unsatisfied when a private provider is already included doesn't feel right. e.g. the code being analyzed might be allowed to depend on this private header, because it's also part of the library, or it's the public header that's exposing this private header. in such a scenario we shouldn't try to insert the public header again. is there a more concrete issue this code is trying to address?

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

410

nit: braces

415

this is passing because bool BDeclFound; is uninitialized above, if you set it to bool BDeclFound = false; you should see the test fail.

there's no declaration for b inside the main file, it's declared in b.h and referenced inside the main file. you still need to search for the decl (without the constraint of being written in main file), use it to build an include_cleaner::Symbol, and use a clangd::Annotation range for the range of the reference.

it might be easer to write this as:

const NamedDecl* B = nullptr;
for (...) {
 ...
 B = D;
}
ASSERT_TRUE(B);
// build expected diagnostic info based on B and check that it's equal to what we've produced

423

i think the example for std::vector is solid, and IWYU pragma private needs a little adjustment.

436

we should include private.h through some indirection (not public.h) to check IWYU pragma private spellings are respected.

442

name this range as bar instead of d?

446

could you add a comment here saying this shouldn't be diagnosed?

[VitaNuo]

Address review comments.

[VitaNuo]

Thanks for the comments!

clang-tools-extra/clangd/IncludeCleaner.cpp

541

Ok makes sense. No, I guess I was just confused, because I understood that you wanted a test that includes "private.h" with a diagnostic generated saying that "public.h" should be included instead, so I assumed that was expected behaviour. But that's not what you meant, so I misunderstood.

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

415

Didn't know there was a difference between uninitialized and false..

Thanks for the idea with ASSERT_TRUE(Decl). Please check out the new version.

[kadircet]

clang-tools-extra/clangd/IncludeCleaner.cpp

429

creating a copy of LLVM style unnecessarily all the time is not really great, can you move this into the failure case instead?

also you can drop the clang:: here and elsewhere, as this code is already part of clang:: namespace.

430

as mentioned above we also need to make sure we're passing the relevant VFS instance inside the source manager, rather than using the real file system (as some clients rely on the VFS).

431

s/MainFile->getName()/AST.tuPath()/

to be consistent with other places.

433

can you also elog this error? as it should be rare and when this goes wrong, having this mentioned in the logs are really useful for debugging (since the failure is actually outside of clangd, it usually means a malformed config file somewhere)

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

393

nit: instead of using a point, can you use a range here instead (i.e. [[b]])? afterwards you can have a FileRange pointing at both offsets, rather than relying on the length of the identifier.

413

rest of the code here doesn't really belong to the for loop, can you take them out?

[VitaNuo]

Address review comments.

[VitaNuo]

Thanks for the comments.

[kadircet]

thanks for bearing with me, let's ship it!

clang-tools-extra/clangd/IncludeCleaner.cpp

429

nit: this could be shorter with

auto FileStyle = format::getStyle(..);
if (!FileStyle) {
  elog("...");
  FileStyle = format::getLLVMStyle();
}
tooling::HeaderIncludes HeaderIncludes(AST.tuPath(), Code, FileStyle->IncludeStyle);

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

415

nit:

size_t Start = llvm::cantFail(positionToOffset(MainFile.code(), Range.start));
size_t End = llvm::cantFail(positionToOffset(MainFile.code(), Range.end));

no need for EXPECT_FALSE(..takeError())s as llvm::cantFail will fail (no pun intended :P), static_casts are also redundant

425

it'd be better to ASSERT_TRUE(BDecl); right after the for loop, as rest of the code will crash (and even trigger undefined behavior because we're dereferencing nullptr in failure case).

difference between ASSERT_X and EXPECT_X macros are, the former will stop execution of the particular test (hence we'll never trigger a nullptr deref with ASSERT_TRUE), whereas the latter just prints the failure, but doesn't abort the execution of test (hence helps print multiple failures at once, when they're non fatal).

[VitaNuo]

Address review comments.

[VitaNuo]

Rebase to main.

[PiotrZSL]

This change broke regression, none-one read: "This revision was landed with ongoing or failed builds."
./ClangdTests.exe/IncludeCleaner/GenerateMissingHeaderDiags tests fails on windows

[thakis]

This breaks tests on windows: http://45.33.8.238/win/75486/step_9.txt

Please take a look and revert for now if it takes a while to fix.

[thakis]

Oh, that was reported a while ago already. Reverted in 2eb5ac99a76dbbf8ac68c538211fabeaa5ac0bfd for now.

[hokein]

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

429

Looks like this filter doesn't work on windows (the / vs \ path separator might be the root cause here), I think a fix can be

• change the check to return Header.endsWith("buzz.h")
• or return Header == testPath("buzz.h", llvm::sys::path::Style::posix).

[PiotrZSL]

@VitaNuo Why did you recommit this again without any fix, breaking regression again.

[VitaNuo]

Try to fix windows build.

[VitaNuo]

Try another approach.

[VitaNuo]

Fix formatting.

clang-tools-extra/clangd/Config.h

struct Config {
   /// Controls index behavior.
   struct {
     /// Whether this TU should be background-indexed.
     BackgroundPolicy Background = BackgroundPolicy::Build;
     ExternalIndexSpec External;
     bool StandardLibrary = true;
   } Index;
 
+  enum class MissingIncludesPolicy {
+    /// Diagnose missing includes.
+    Strict,
+    None,
+  };
   enum UnusedIncludesPolicy {
     /// Diagnose unused includes.
     Strict,
     None,
     /// The same as Strict, but using the include-cleaner library.
     Experiment,
   };
   /// Controls warnings and errors when parsing code.
   struct {
     bool SuppressAll = false;
     llvm::StringSet<> Suppress;
 
     /// Configures what clang-tidy checks to run and options to use with them.
     struct {
       // A comma-seperated list of globs specify which clang-tidy checks to run.
       std::string Checks;
       llvm::StringMap<std::string> CheckOptions;
     } ClangTidy;
 
     UnusedIncludesPolicy UnusedIncludes = None;
+    MissingIncludesPolicy MissingIncludes = MissingIncludesPolicy::None;
 
     /// IncludeCleaner will not diagnose usages of these headers matched by
     /// these regexes.
     struct {
       std::vector<std::function<bool(llvm::StringRef)>> IgnoreHeader;
     } Includes;
   } Diagnostics;
 

clang-tools-extra/clangd/ConfigCompile.cpp

if (F.UnusedIncludes)
                                                         **F.UnusedIncludes)
                   .map("Strict", Config::UnusedIncludesPolicy::Strict)
                   .map("Experiment", Config::UnusedIncludesPolicy::Experiment)
                   .map("None", Config::UnusedIncludesPolicy::None)
                   .value())
         Out.Apply.push_back([Val](const Params &, Config &C) {
           C.Diagnostics.UnusedIncludes = *Val;
         });
+
+     if (F.MissingIncludes)
+      if (auto Val =
+              compileEnum<Config::MissingIncludesPolicy>("MissingIncludes",
+                                                        **F.MissingIncludes)
+                  .map("Strict", Config::MissingIncludesPolicy::Strict)
+                  .map("None", Config::MissingIncludesPolicy::None)
+                  .value())
+        Out.Apply.push_back([Val](const Params &, Config &C) {
+          C.Diagnostics.MissingIncludes = *Val;
+        });
+             
     compile(std::move(F.Includes));
 
     compile(std::move(F.ClangTidy));
   }
 
   void compile(Fragment::StyleBlock &&F) {
     if (!F.FullyQualifiedNamespaces.empty()) {
       std::vector<std::string> FullyQualifiedNamespaces;

clang-tools-extra/clangd/ConfigFragment.h

struct DiagnosticsBlock {
     /// - warning categories (e.g. unused-result)
     /// - clang-tidy check names (e.g. bugprone-narrowing-conversions)
     ///
     /// This is a simple filter. Diagnostics can be controlled in other ways
     /// (e.g. by disabling a clang-tidy check, or the -Wunused compile flag).
     /// This often has other advantages, such as skipping some analysis.
     std::vector<Located<std::string>> Suppress;
 
-    /// Controls how clangd will correct "unnecessary #include directives.
+    /// Controls how clangd will correct "unnecessary" #include directives.
     /// clangd can warn if a header is `#include`d but not used, and suggest
     /// removing it.
     //
     /// Strict means a header is unused if it does not *directly* provide any
     /// symbol used in the file. Removing it may still break compilation if it
     /// transitively includes headers that are used. This should be fixed by
     /// including those headers directly.
     ///
     /// Valid values are:
     /// - Strict
     /// - None
     std::optional<Located<std::string>> UnusedIncludes;
 
+    /// Controls how clangd handles missing #include directives.
+    /// clangd can warn if a header for a symbol is not `#include`d (missing),
+    /// and suggest adding it.
+    ///
+    /// Strict means a header is missing if it is not *directly #include'd.
+    /// The file might still compile if the header is included transitively.
+    ///
+    /// Valid values are:
+    /// - Strict
+    /// - None
+    std::optional<Located<std::string>> MissingIncludes;
+
     /// Controls IncludeCleaner diagnostics.
     struct IncludesBlock {
       /// Regexes that will be used to avoid diagnosing certain includes as
       /// unused or missing. These can match any suffix of the header file in
       /// question.
       std::vector<Located<std::string>> IgnoreHeader;
     };
     IncludesBlock Includes;

clang-tools-extra/clangd/ConfigYAML.cpp

void parse(Fragment::DiagnosticsBlock &F, Node &N) {
     DictParser Dict("Diagnostics", this);
     Dict.handle("Suppress", [&](Node &N) {
       if (auto Values = scalarValues(N))
         F.Suppress = std::move(*Values);
     });
     Dict.handle("UnusedIncludes", [&](Node &N) {
       F.UnusedIncludes = scalarValue(N, "UnusedIncludes");
     });
+    Dict.handle("MissingIncludes", [&](Node &N) {
+      F.MissingIncludes = scalarValue(N, "MissingIncludes");
+    });
     Dict.handle("Includes", [&](Node &N) { parse(F.Includes, N); });
     Dict.handle("ClangTidy", [&](Node &N) { parse(F.ClangTidy, N); });
     Dict.parse(N);
   }
 
   void parse(Fragment::DiagnosticsBlock::ClangTidyBlock &F, Node &N) {
     DictParser Dict("ClangTidy", this);
     Dict.handle("Add", [&](Node &N) {

clang-tools-extra/clangd/IncludeCleaner.h

 #include <optional>
 #include <vector>
 
 namespace clang {
 namespace clangd {
 
 struct ReferencedLocations {
   llvm::DenseSet<SourceLocation> User;
   llvm::DenseSet<tooling::stdlib::Symbol> Stdlib;
 };
 
 /// Finds locations of all symbols used in the main file.
 ///
 /// - RecursiveASTVisitor finds references to symbols and records their
 ///   associated locations. These may be macro expansions, and are not resolved
 ///   to their spelling or expansion location. These locations are later used to
 ///   determine which headers should be marked as "used" and "directly used".
 /// - If \p Tokens is not nullptr, we also examine all identifier tokens in the
 ///   file in case they reference macros macros.
 /// We use this to compute unused headers, so we:
 ///
 /// - cover the whole file in a single traversal for efficiency
 /// - don't attempt to describe where symbols were referenced from in
 ///   ambiguous cases (e.g. implicitly used symbols, multiple declarations)
 /// - err on the side of reporting all possible locations
 ReferencedLocations findReferencedLocations(ASTContext &Ctx, Preprocessor &PP,
                                             const syntax::TokenBuffer *Tokens);
 ReferencedLocations findReferencedLocations(ParsedAST &AST);
 

 
 /// Retrieves headers that are referenced from the main file but not used.
 /// In unclear cases, headers are not marked as unused.
 std::vector<const Inclusion *>
 getUnused(ParsedAST &AST,
           const llvm::DenseSet<IncludeStructure::HeaderID> &ReferencedFiles,
           const llvm::StringSet<> &ReferencedPublicHeaders);
 
+std::vector<std::pair<std::string, unsigned>>
+computeMissingIncludes(ParsedAST &AST);
 std::vector<const Inclusion *> computeUnusedIncludes(ParsedAST &AST);
 // The same as computeUnusedIncludes, but it is an experimental and
 // include-cleaner-lib-based implementation.
 std::vector<const Inclusion *>
 computeUnusedIncludesExperimental(ParsedAST &AST);
 
+std::vector<Diag> issueMissingIncludesDiagnostics(ParsedAST &AST,
+                                                  llvm::StringRef Code);
 std::vector<Diag> issueUnusedIncludesDiagnostics(ParsedAST &AST,
                                                  llvm::StringRef Code);
 
 /// Affects whether standard library includes should be considered for
 /// removal. This is off by default for now due to implementation limitations:
 /// - macros are not tracked
 /// - symbol names without a unique associated header are not tracked
 /// - references to std-namespaced C types are not properly tracked:
 ///   instead of std::size_t -> <cstddef> we see ::size_t -> <stddef.h>
 /// FIXME: remove this hack once the implementation is good enough.
 void setIncludeCleanerAnalyzesStdlib(bool B);
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INCLUDECLEANER_H

clang-tools-extra/clangd/IncludeCleaner.cpp

 #include "clang-include-cleaner/Analysis.h"
 #include "clang-include-cleaner/Types.h"
 #include "index/CanonicalIncludes.h"
 #include "support/Logger.h"
 #include "support/Trace.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/ExprCXX.h"
 #include "clang/AST/RecursiveASTVisitor.h"
+#include "clang/Basic/FileEntry.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Lex/HeaderSearch.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Tooling/Syntax/Tokens.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/STLFunctionalExtras.h"
 #include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/Regex.h"
 #include <functional>
 #include <optional>
+#include <vector>
 
 namespace clang {
 namespace clangd {
 
 static bool AnalyzeStdlib = false;
 void setIncludeCleanerAnalyzesStdlib(bool B) { AnalyzeStdlib = B; }
 
 namespace {
bool VisitCXXConstructExpr(CXXConstructExpr *CCE) {
     add(CCE->getConstructor());
     return true;
   }
 
   bool VisitTemplateSpecializationType(TemplateSpecializationType *TST) {
     // Using templateName case is handled by the override TraverseTemplateName.
     if (TST->getTemplateName().getKind() == TemplateName::UsingTemplate)
       return true;
-    add(TST->getAsCXXRecordDecl());                  // Specialization
+    add(TST->getAsCXXRecordDecl()); // Specialization
     return true;
   }
 
   // There is no VisitTemplateName in RAV, thus we override the Traverse version
   // to handle the Using TemplateName case.
   bool TraverseTemplateName(TemplateName TN) {
     VisitTemplateName(TN);
     return Base::TraverseTemplateName(TN);
if (!Macro)
       continue;
     auto Loc = Macro->Info->getDefinitionLoc();
     if (Loc.isValid())
       Result.User.insert(Loc);
     // FIXME: support stdlib macros
   }
 }
 
 static bool mayConsiderUnused(const Inclusion &Inc, ParsedAST &AST,
                               const Config &Cfg) {
   if (Inc.BehindPragmaKeep)
     return false;
 
   // FIXME(kirillbobyrev): We currently do not support the umbrella headers.
   // System headers are likely to be standard library headers.
   // Until we have good support for umbrella headers, don't warn about them.
   if (Inc.Written.front() == '<') {
     if (AnalyzeStdlib && tooling::stdlib::Header::named(Inc.Written))
       return true;
static bool mayConsiderUnused(const Inclusion &Inc, ParsedAST &AST,
   // Headers without include guards have side effects and are not
   // self-contained, skip them.
   if (!AST.getPreprocessor().getHeaderSearchInfo().isFileMultipleIncludeGuarded(
           &FE->getFileEntry())) {
     dlog("{0} doesn't have header guard and will not be considered unused",
          FE->getName());
     return false;
   }
   for (auto &Filter : Cfg.Diagnostics.Includes.IgnoreHeader) {
     // Convert the path to Unix slashes and try to match against the filter.
     llvm::SmallString<64> Path(Inc.Resolved);
     llvm::sys::path::native(Path, llvm::sys::path::Style::posix);
     if (Filter(Inc.Resolved)) {
       dlog("{0} header is filtered out by the configuration", FE->getName());
       return false;
     }
   }
ReferencedLocations findReferencedLocations(ASTContext &Ctx, Preprocessor &PP,
   trace::Span Tracer("IncludeCleaner::findReferencedLocations");
   ReferencedLocations Result;
   const auto &SM = Ctx.getSourceManager();
   ReferencedLocationCrawler Crawler(Result, SM);
   Crawler.TraverseAST(Ctx);
   if (Tokens)
     findReferencedMacros(SM, PP, Tokens, Result);
   return Result;
 }
 
 ReferencedLocations findReferencedLocations(ParsedAST &AST) {
   return findReferencedLocations(AST.getASTContext(), AST.getPreprocessor(),
                                  &AST.getTokens());
 }
 
 ReferencedFiles findReferencedFiles(
     const ReferencedLocations &Locs, const SourceManager &SM,
     llvm::function_ref<FileID(FileID)> HeaderResponsible,
     llvm::function_ref<std::optional<StringRef>(FileID)> UmbrellaHeader) {
   std::vector<SourceLocation> Sorted{Locs.User.begin(), Locs.User.end()};
   llvm::sort(Sorted); // Group by FileID.
   ReferencedFilesBuilder Builder(SM);
   for (auto It = Sorted.begin(); It < Sorted.end();) {
     FileID FID = SM.getFileID(*It);
     Builder.add(FID, *It);
     // Cheaply skip over all the other locations from the same FileID.
     // This avoids lots of redundant Loc->File lookups for the same file.
     do
       ++It;
     while (It != Sorted.end() && SM.isInFileID(*It, FID));
   }
for (const auto &Header : Symbol.headers())
       StdlibFiles.insert(Header);
 
   return {std::move(UserFiles), std::move(StdlibFiles),
           std::move(PublicHeaders)};
 }
 
 ReferencedFiles findReferencedFiles(const ReferencedLocations &Locs,
                                     const IncludeStructure &Includes,
                                     const CanonicalIncludes &CanonIncludes,
                                     const SourceManager &SM) {
   return findReferencedFiles(
       Locs, SM,
       [&SM, &Includes](FileID ID) {
         return headerResponsible(ID, SM, Includes);
       },
       [&SM, &CanonIncludes](FileID ID) -> std::optional<StringRef> {
         auto Entry = SM.getFileEntryRefForID(ID);
         if (!Entry)
           return std::nullopt;
         auto PublicHeader = CanonIncludes.mapHeader(*Entry);
         if (PublicHeader.empty())
           return std::nullopt;
         return PublicHeader;
       });
 }
 
 std::vector<const Inclusion *>
 getUnused(ParsedAST &AST,
           const llvm::DenseSet<IncludeStructure::HeaderID> &ReferencedFiles,
           const llvm::StringSet<> &ReferencedPublicHeaders) {
   trace::Span Tracer("IncludeCleaner::getUnused");
   const Config &Cfg = Config::current();
   std::vector<const Inclusion *> Unused;
   for (const Inclusion &MFI : AST.getIncludeStructure().MainFileIncludes) {
     if (!MFI.HeaderID)
       continue;
     if (ReferencedPublicHeaders.contains(MFI.Written))
       continue;
     auto IncludeID = static_cast<IncludeStructure::HeaderID>(*MFI.HeaderID);
     bool Used = ReferencedFiles.contains(IncludeID);
     if (!Used && !mayConsiderUnused(MFI, AST, Cfg)) {
       dlog("{0} was not used, but is not eligible to be diagnosed as unused",
            MFI.Written);
       continue;
     }
     if (!Used)
       Unused.push_back(&MFI);
     dlog("{0} is {1}", MFI.Written, Used ? "USED" : "UNUSED");
   }
   return Unused;
 }
 
 #ifndef NDEBUG
 // Is FID a <built-in>, <scratch space> etc?
 static bool isSpecialBuffer(FileID FID, const SourceManager &SM) {
   const SrcMgr::FileInfo &FI = SM.getSLocEntry(FID).getFile();
   return FI.getName().startswith("<");
 }
 #endif
 
 llvm::DenseSet<IncludeStructure::HeaderID>
 translateToHeaderIDs(const ReferencedFiles &Files,
                      const IncludeStructure &Includes,
                      const SourceManager &SM) {
   trace::Span Tracer("IncludeCleaner::translateToHeaderIDs");
   llvm::DenseSet<IncludeStructure::HeaderID> TranslatedHeaderIDs;
   TranslatedHeaderIDs.reserve(Files.User.size());
   for (FileID FID : Files.User) {
     const FileEntry *FE = SM.getFileEntryForID(FID);
     if (!FE) {
       assert(isSpecialBuffer(FID, SM));
       continue;
     }
     const auto File = Includes.getID(FE);
     assert(File);
     TranslatedHeaderIDs.insert(*File);
   }
   for (tooling::stdlib::Header StdlibUsed : Files.Stdlib)
     for (auto HID : Includes.StdlibHeaders.lookup(StdlibUsed))
       TranslatedHeaderIDs.insert(HID);
   return TranslatedHeaderIDs;
 }
 
+std::vector<include_cleaner::SymbolReference>
+collectMacroReferences(ParsedAST &AST) {
+  const auto &SM = AST.getSourceManager();
+  //  FIXME: !!this is a hacky way to collect macro references.
+  std::vector<include_cleaner::SymbolReference> Macros;
+  auto &PP = AST.getPreprocessor();
+  for (const syntax::Token &Tok :
+       AST.getTokens().spelledTokens(SM.getMainFileID())) {
+    auto Macro = locateMacroAt(Tok, PP);
+    if (!Macro)
+      continue;
+    if (auto DefLoc = Macro->Info->getDefinitionLoc(); DefLoc.isValid())
+      Macros.push_back(
+          {Tok.location(),
+           include_cleaner::Macro{/*Name=*/PP.getIdentifierInfo(Tok.text(SM)),
+                                  DefLoc},
+           include_cleaner::RefType::Explicit});
+  }
+  return Macros;
+}
+
 // This is the original clangd-own implementation for computing unused
 // #includes. Eventually it will be deprecated and replaced by the
 // include-cleaner-lib-based implementation.
 std::vector<const Inclusion *> computeUnusedIncludes(ParsedAST &AST) {
   const auto &SM = AST.getSourceManager();
 
   auto Refs = findReferencedLocations(AST);
   auto ReferencedFiles =
       findReferencedFiles(Refs, AST.getIncludeStructure(),
                           AST.getCanonicalIncludes(), AST.getSourceManager());
   auto ReferencedHeaders =
       translateToHeaderIDs(ReferencedFiles, AST.getIncludeStructure(), SM);
   return getUnused(AST, ReferencedHeaders, ReferencedFiles.SpelledUmbrellas);
 }
-std::vector<const Inclusion *> computeUnusedIncludesExperimental(ParsedAST &AST) {
-   const auto &SM = AST.getSourceManager();
-   const auto &Includes = AST.getIncludeStructure();
-   // FIXME: this map should probably be in IncludeStructure.
-   llvm::StringMap<llvm::SmallVector<IncludeStructure::HeaderID>> BySpelling;
-   for (const auto &Inc : Includes.MainFileIncludes) {
+
+// Compute unused #includes using the include-cleaner-lib-based implementation.
+std::vector<const Inclusion *>
+computeUnusedIncludesExperimental(ParsedAST &AST) {
     if (Inc.HeaderID)
       BySpelling.try_emplace(Inc.Written)
           .first->second.push_back(
               static_cast<IncludeStructure::HeaderID>(*Inc.HeaderID));
-   }
-   // FIXME: !!this is a hacky way to collect macro references.
-   std::vector<include_cleaner::SymbolReference> Macros;
-    auto& PP = AST.getPreprocessor();
-   for (const syntax::Token &Tok :
-        AST.getTokens().spelledTokens(SM.getMainFileID())) {
-    auto Macro = locateMacroAt(Tok, PP);
-    if (!Macro)
-      continue;
-    if (auto DefLoc = Macro->Info->getDefinitionLoc(); DefLoc.isValid())
-      Macros.push_back(
-          {Tok.location(),
-           include_cleaner::Macro{/*Name=*/PP.getIdentifierInfo(Tok.text(SM)),
-                                  DefLoc},
-           include_cleaner::RefType::Explicit});
-   }
-   llvm::DenseSet<IncludeStructure::HeaderID> Used;
-   include_cleaner::walkUsed(
-       AST.getLocalTopLevelDecls(), /*MacroRefs=*/Macros,
-       AST.getPragmaIncludes(), SM,
-       [&](const include_cleaner::SymbolReference &Ref,
-           llvm::ArrayRef<include_cleaner::Header> Providers) {
-         for (const auto &H : Providers) {
-           switch (H.kind()) {
-           case include_cleaner::Header::Physical:
-             if (auto HeaderID = Includes.getID(H.physical()))
-               Used.insert(*HeaderID);
-             break;
-           case include_cleaner::Header::Standard:
-             for (auto HeaderID : Includes.StdlibHeaders.lookup(H.standard()))
-               Used.insert(HeaderID);
-             break;
-           case include_cleaner::Header::Verbatim:
-             for (auto HeaderID : BySpelling.lookup(H.verbatim()))
-               Used.insert(HeaderID);
-             break;
-           }
-         }
-       });
-   return getUnused(AST, Used, /*ReferencedPublicHeaders*/{});
+
+  std::vector<include_cleaner::SymbolReference> Macros =
+      collectMacroReferences(AST);
+
+  return getUnused(AST, Used, /*ReferencedPublicHeaders*/ {});
 }
 
+include_cleaner::Includes
+convertIncludes(const SourceManager &SM,
+                std::vector<Inclusion> MainFileIncludes) {
+  include_cleaner::Includes Includes;
+  for (const Inclusion &Inc : MainFileIncludes) {
+    llvm::ErrorOr<const FileEntry *> ResolvedOrError =
+        SM.getFileManager().getFile(Inc.Resolved);
+    const FileEntry *Resolved = nullptr;
+    if (bool(ResolvedOrError)) {
+      Resolved = ResolvedOrError.get();
+    }
+    SourceLocation HashLocation =
+        SM.getComposedLoc(SM.getMainFileID(), Inc.HashOffset);
+    llvm::StringRef WrittenRef = llvm::StringRef(Inc.Written);
+    bool Angled = WrittenRef.starts_with("<") ? true : false;
+    Includes.add(include_cleaner::Include{WrittenRef.trim("\"<>"), Resolved,
+                                          HashLocation, (unsigned)Inc.HashLine,
+                                          Angled});
+  }
+  return Includes;
+}
+
+// Compute missing #includes. Uses the include-cleaner-lib-based implementation.
+std::vector<std::pair<std::string, unsigned>>
+computeMissingIncludes(ParsedAST &AST) {
+  std::vector<include_cleaner::SymbolReference> Macros =
+      collectMacroReferences(AST);
+  std::vector<Inclusion> MainFileIncludes =
+      AST.getIncludeStructure().MainFileIncludes;
+
+  include_cleaner::Includes IncludeCleanerIncludes =
+      convertIncludes(AST.getSourceManager(), MainFileIncludes);
+  std::string FileName =
+      AST.getSourceManager()
+          .getFileEntryRefForID(AST.getSourceManager().getMainFileID())
+          ->getName()
+          .str();
+  if (FileName.find("foo") != std::string::npos) {
+    vlog("Include cleaner includes: {0}", IncludeCleanerIncludes.all().size());
+  }
+
+  std::vector<std::pair<std::string, unsigned>> Missing;
+  SourceManager &SM = AST.getSourceManager();
+  const FileEntry *MainFile = SM.getFileEntryForID(SM.getMainFileID());
+  include_cleaner::walkUsed(
+      AST.getLocalTopLevelDecls(), Macros, AST.getPragmaIncludes(), SM,
+      [&](const include_cleaner::SymbolReference &Ref,
+          llvm::ArrayRef<include_cleaner::Header> Providers) {
+        bool Satisfied = false;
+        for (const include_cleaner::Header &H : Providers) {
+          if (H.kind() == include_cleaner::Header::Physical &&
+              H.physical() == MainFile) {
+            Satisfied = true;
+          }
+          if (!IncludeCleanerIncludes.match(H).empty()) {
+            Satisfied = true;
+          }
+        }
+        if (!Satisfied && !Providers.empty() &&
+            Ref.RT == include_cleaner::RefType::Explicit) {
+          std::string SpelledHeader = include_cleaner::spellHeader(
+              Providers.front(), AST.getPreprocessor().getHeaderSearchInfo(),
+              MainFile);
+          std::pair<FileID, unsigned int> FileIDAndOffset =
+              AST.getSourceManager().getDecomposedLoc(Ref.RefLocation);
+          Missing.push_back({SpelledHeader, FileIDAndOffset.second});
+        }
+      });
+  return Missing;
+}
+
+std::vector<Diag> issueMissingIncludesDiagnostics(ParsedAST &AST,
+                                                  llvm::StringRef Code) {
+  const Config &Cfg = Config::current();
+  if (Cfg.Diagnostics.MissingIncludes == Config::MissingIncludesPolicy::None ||
+      Cfg.Diagnostics.SuppressAll ||
+      Cfg.Diagnostics.Suppress.contains("missing-includes")) {
+    return {};
+  }
+  // Interaction is only polished for C/CPP.
+  if (AST.getLangOpts().ObjC)
+    return {};
+  trace::Span Tracer("IncludeCleaner::issueMissingIncludesDiagnostics");
+  std::string FileName =
+      AST.getSourceManager()
+          .getFileEntryRefForID(AST.getSourceManager().getMainFileID())
+          ->getName()
+          .str();
+
+  unsigned FixLine = 0;
+  std::vector<Inclusion> MainFileIncludes =
+      AST.getIncludeStructure().MainFileIncludes;
+  if (!MainFileIncludes.empty())
+    FixLine = MainFileIncludes[MainFileIncludes.size() - 1].HashLine + 1;
+
+  std::vector<Diag> Result;
+  const auto &MissingIncludes = computeMissingIncludes(AST);
+  for (const std::pair<std::string, unsigned> &Missing : MissingIncludes) {
+    Diag D;
+    D.Message = llvm::formatv("header {0} is missing", Missing.first);
+    D.Name = "missing-includes";
+    D.Source = Diag::DiagSource::Clangd;
+    D.File = FileName;
+    D.Severity = DiagnosticsEngine::Warning;
+
+    D.Range = getDiagnosticRange(Code, Missing.second);
+    D.Fixes.emplace_back();
+    D.Fixes.back().Message = "add #include directive";
+    D.Fixes.back().Edits.emplace_back();
+    D.Fixes.back().Edits.back().newText = "#include " + Missing.first + "\n";
+    D.Fixes.back().Edits.back().range.start.line = FixLine;
+    D.Fixes.back().Edits.back().range.end.line = FixLine;
+    D.InsideMainFile = true;
+    Result.push_back(std::move(D));
+  }
+
+  return Result;
+}
+
 std::vector<Diag> issueUnusedIncludesDiagnostics(ParsedAST &AST,
                                                  llvm::StringRef Code) {
   const Config &Cfg = Config::current();
   if (Cfg.Diagnostics.UnusedIncludes == Config::UnusedIncludesPolicy::None ||
       Cfg.Diagnostics.SuppressAll ||
       Cfg.Diagnostics.Suppress.contains("unused-includes"))
     return {};
   // Interaction is only polished for C/CPP.
   if (AST.getLangOpts().ObjC)
     return {};
   trace::Span Tracer("IncludeCleaner::issueUnusedIncludesDiagnostics");
   std::vector<Diag> Result;
   std::string FileName =
       AST.getSourceManager()
           .getFileEntryRefForID(AST.getSourceManager().getMainFileID())
           ->getName()
           .str();
   const auto &UnusedIncludes =
       Cfg.Diagnostics.UnusedIncludes == Config::UnusedIncludesPolicy::Experiment
           ? computeUnusedIncludesExperimental(AST)
           : computeUnusedIncludes(AST);
for (const auto *Inc : UnusedIncludes) {
     // FIXME(kirillbobyrev): Add fix suggestion for adding IWYU pragmas
     // (keep/export) remove the warning once we support IWYU pragmas.
     D.Fixes.emplace_back();
     D.Fixes.back().Message = "remove #include directive";
     D.Fixes.back().Edits.emplace_back();
     D.Fixes.back().Edits.back().range.start.line = Inc->HashLine;
     D.Fixes.back().Edits.back().range.end.line = Inc->HashLine + 1;
     D.InsideMainFile = true;
     Result.push_back(std::move(D));
   }
   return Result;
 }
 
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/ParsedAST.cpp

ParsedAST::build(llvm::StringRef Filename, const ParseInputs &Inputs,
   ParsedAST Result(Filename, Inputs.Version, std::move(Preamble),
                    std::move(Clang), std::move(Action), std::move(Tokens),
                    std::move(Macros), std::move(Marks), std::move(ParsedDecls),
                    std::move(Diags), std::move(Includes),
                    std::move(CanonIncludes));
   if (Result.Diags) {
     auto UnusedHeadersDiags =
         issueUnusedIncludesDiagnostics(Result, Inputs.Contents);
+    auto MissingHeadersDiags =
+        issueMissingIncludesDiagnostics(Result, Inputs.Contents);
     Result.Diags->insert(Result.Diags->end(),
                          make_move_iterator(UnusedHeadersDiags.begin()),
                          make_move_iterator(UnusedHeadersDiags.end()));
+    Result.Diags->insert(Result.Diags->end(),
+                         make_move_iterator(MissingHeadersDiags.begin()),
+                         make_move_iterator(MissingHeadersDiags.end()));
   }
   return std::move(Result);
 }
 
 ParsedAST::ParsedAST(ParsedAST &&Other) = default;
 
 ParsedAST &ParsedAST::operator=(ParsedAST &&Other) = default;
 

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

EXPECT_THAT(
       UnorderedElementsAre(Pointee(writtenInclusion("\"unused.h\"")),
                            Pointee(writtenInclusion("\"dir/unused.h\""))));
   EXPECT_THAT(
       computeUnusedIncludesExperimental(AST),
       UnorderedElementsAre(Pointee(writtenInclusion("\"unused.h\"")),
                            Pointee(writtenInclusion("\"dir/unused.h\""))));
 }
 
+TEST(IncludeCleaner, GetMissingHeaders) {
+  llvm::StringLiteral MainFile = R"cpp(
+    #include "a.h"
+    #include "dir/c.h"
+    #include <e.h>
+
+    void foo() {
+      b();
+      d();
+      f();
+    })cpp";
+  // Build expected ast with symbols coming from headers.
+  TestTU TU;
+  TU.Filename = "foo.cpp";
+  TU.AdditionalFiles["foo.h"] = guard("void foo();");
+  TU.AdditionalFiles["a.h"] = guard("#include \"b.h\"");
+  TU.AdditionalFiles["b.h"] = guard("void b();");
+
+  TU.AdditionalFiles["dir/c.h"] = guard("#include \"d.h\"");
+  TU.AdditionalFiles["dir/d.h"] = guard("void d();");
+
+  TU.AdditionalFiles["system/e.h"] = guard("#include <f.h>");
+  TU.AdditionalFiles["system/f.h"] = guard("void f();");
+  TU.ExtraArgs.push_back("-isystem" + testPath("system"));
+
+  TU.Code = MainFile.str();
+  ParsedAST AST = TU.build();
+
+  std::vector<std::pair<std::string, unsigned>> MissingIncludes =
+      computeMissingIncludes(AST);
+
+  std::pair<std::string, unsigned> b{"\"b.h\"", 86};
+  std::pair<std::string, unsigned> d{"\"dir/d.h\"", 97};
+  std::pair<std::string, unsigned> h{"<f.h>", 108};
+  EXPECT_THAT(MissingIncludes, UnorderedElementsAre(b, d, h));
+}
+
 TEST(IncludeCleaner, VirtualBuffers) {
   TestTU TU;
   TU.Code = R"cpp(
     #include "macros.h"
 
     using flags::FLAGS_FOO;
 
     // CLI will come from a define, __cplusplus is a built-in. In both cases, they
     // come from non-existent files.
     int y = CLI + __cplusplus;
 
     int concat(a, b) = 42;
     )cpp";
   // The pasting operator in combination with DEFINE_FLAG will create
   // ScratchBuffer with `flags::FLAGS_FOO` that will have FileID but not
   // FileEntry.
   TU.AdditionalFiles["macros.h"] = R"cpp(
     #ifndef MACROS_H
     #define MACROS_H
 
     #define DEFINE_FLAG(X) \
     namespace flags { \
     int FLAGS_##X; \
     } \
 
     DEFINE_FLAG(FOO)
 
     #define ab x
     #define concat(x, y) x##y
 
     #endif // MACROS_H
TU.AdditionalFiles["foo.h"] = R"cpp(
     #define FOO_H
 
     #endif
   )cpp";
   TU.ExtraArgs.emplace_back("-xobjective-c");
 
   Config Cfg;
   Cfg.Diagnostics.UnusedIncludes = Config::Strict;
+  Cfg.Diagnostics.MissingIncludes = Config::MissingIncludesPolicy::Strict;
   WithContextValue Ctx(Config::Key, std::move(Cfg));
   ParsedAST AST = TU.build();
   EXPECT_THAT(AST.getDiagnostics(), llvm::ValueIs(IsEmpty()));
 }
 } // namespace
 } // namespace clangd
 } // namespace clang